acceptodds
Under review as a conference paper at ICLR 2027

A New Approach to Bilevel Optimization: A Value-Centric Perspective via a Distributional Follower

Abstract

Classical bilevel optimization represents the lower-level response by a selected minimizer . This optimizer-centered formulation can be unstable in overparameterized or multimodal settings. Moreover, when multiple lower-level minimizers exist, it requires a response-selection rule that may be difficult to justify in practice. We propose an optimal-value-centered formulation that replaces the selected minimizer by a Gibbs distribution over lower-level solutions. Equivalently, this distribution solves an entropy-regularized lower-level problem over probability measures, while the upper level minimizes the expected outer objective. This representation motivates Value-Centric Hypergradient Descent (VCHD) algorithm, a double-loop method that samples from the decision-dependent Gibbs follower using mini-batch SGLD and updates the outer variable with a sample-based hypergradient estimator. We establish nonasymptotic convergence without assuming lower-level convexity and show that VCHD reaches an -stationary point with sample complexity. We conducted a thorough study of the empirical performance of the VCHD algorithm: a quadratic example examines how temperature and inner-loop length affect its performance, while a double-well example shows that VCHD can approach the correct outer solution even when the lower-level landscape is nonconvex and contains local minima. Results on the hyper-data-cleaning application further suggest that our optimal-value-centered hypergradient can preserve informative update signals when classical bilevel methods suffer from overfitting and vanishing hypergradients.

Primary area:
optimization
Keywords:
bilevel optimization, hypergradient, Stochastic Gradient Langevin Dynamics, nonconvex optimization

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_FGm5OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper replaces the lower-level optimizer with a Gibbs distribution and proposes VCHD, a Hessian-free method using covariance-based hypergradients and SGLD sampling. It establishes convergence under lower-level strong convexity outside a bounded region. Experiments on synthetic problems and data cleaning suggest benefits in handling multiple minima and vanishing hypergradients.

Critical strengths
  1. Clear formulation: The Gibbs follower provides a principled way to account for multiple lower-level solutions and their neighborhoods in nonconvex landscapes.

  2. Practical hypergradient computation: The expectation–covariance identity avoids explicit Hessian inversion and differentiation through the inner optimization trajectory.

  3. Substantial theoretical analysis: The convergence analysis explicitly accounts for SGLD discretization error, correlated samples, and hypergradient estimation error, while allowing lower-level nonconvexity within a bounded region.

Critical weaknesses
  1. Restrictive assumptions and an incomplete connection between theory and experiments.
    Although the analysis allows lower-level nonconvexity within a bounded region, it still requires strong convexity in the tails, global smoothness, and a bounded outer objective. These assumptions substantially restrict the class of problems covered, particularly for neural-network applications. Some experimental settings also fall outside these conditions: quartic double-well objectives violate global gradient Lipschitz continuity, quadratic outer losses are unbounded, and the neural-network experiment uses an Adam-based noisy update rather than the analyzed SGLD kernel.

  2. The relationship between the Gibbs formulation and the original bilevel problem needs further clarification.
    The main theorem establishes convergence to a stationary point of the fixed-temperature objective JτJ_\tau. This does not generally imply stationarity or optimality for the original bilevel problem.

  3. The complexity bound leaves the cost of low-temperature sampling unclear.
    The O(ε−3)O(\varepsilon^{-3}) guarantee treats temperature and mixing-related quantities as fixed constants. In a multimodal landscape, reducing the temperature can substantially slow transitions between modes and worsen these constants. Thus, the stated rate alone does not establish efficient sampling in the regime where the Gibbs follower concentrates near lower-level minimizers. An explicit analysis of the joint dependence on temperature, mixing time, and optimization accuracy would better explain the computational tradeoff.

  4. The explanation of vanishing classical hypergradients contains an incorrect bound.
    On page 9, the corresponding bound for the exact hypergradient should be

    \le \frac{1}{n} \\|\nabla_ \theta\ell_i\\|\ \\|[\nabla_ {\theta\theta}^ {2}\ell]^{-1}\\|_ {\mathrm{op}}\ \\|\nabla_ \theta f\\|.$$
  5. Gap in the warm-start analysis. The proof assumes an equality between conditional distributions that generally does not hold when reusing the previous chain’s endpoint. Therefore, the practical warm-start implementation requires additional theoretical justification.

Questions for authors

See weakness

6 comments

W1 We thank the reviewer for this point. We agree that the double-well experiment, as submitted, falls outside Assumptions 4.1 and 4.6. Below we first present a variant that satisfies them, and then provide discuss for the assumptions.

A double-well experiment that satisfies the assumptions. Following the idea of Proposition 4.3, we modify the problem only outside a ball that the chains never reach. Let U(θ)=(θ2−1)2U(\theta)=(\theta^2-1)^2, R=5R=5, and x=∣θ∣−Rx=\lvert\theta\rvert-R.

  • Inner loss: ℓ(v,θ)=U(θ)−vθ\ell(v,\theta)=U(\theta)-v\theta for ∣θ∣≤R\lvert\theta\rvert\le R, and ℓ(v,θ)=U(R)+U′(R)x+12U′′(R)x2−vθ\ell(v,\theta)=U(R)+U'(R)x+\tfrac12U''(R)x^2-v\theta for ∣θ∣>R\lvert\theta\rvert>R (a C2C^2 quadratic extension).
  • Outer loss: the θ2\theta^2 term of f(v,θ)=θ2+λ2v2f(v,\theta)=\theta^2+\tfrac{\lambda}{2}v^2 is kept for ∣θ∣≤R\lvert\theta\rvert\le R and is brought to the constant R2+RR^2+R by the C1C^1 piece R2+2Rx−Rx2R^2+2Rx-Rx^2 on R<∣θ∣≤R+1R<\lvert\theta\rvert\le R+1.

This problem satisfies Assumptions 4.1, 4.6, and 4.8 with explicit constants: −4≤∂θθ2ℓ≤296-4\le\partial^2_{\theta\theta}\ell\le296 (so LH=296L_H=296), ∂θθ2ℓ=296\partial^2_{\theta\theta}\ell=296 for ∣θ∣≥R\lvert\theta\rvert\ge R, ∣f∣≤34\lvert f\rvert\le34, Lf=10L_f=10, Lfℓv=79L_{f\ell_v}=79, and LJ=1.50L_J=1.50 (so β=0.05≤1/(2LJ)\beta=0.05\le1/(2L_J)). JτJ_\tau is strongly convex on V=[−4,4]\mathcal V=[-4,4] with unique minimizer v⋆=0v^\star=0. For every v∈Vv\in\mathcal V, the Gibbs density at ∣θ∣=R\lvert\theta\rvert=R is below e−1100e^{-1100} relative to its value at the mode, so πv\pi_v, JτJ_\tau, and ∇Jτ\nabla J_\tau are numerically identical to those of the original problem.

Under the settings of the paper, all methods produce the same results as those reported in Section 5.2: the variant differs from the original problem only for ∣θ∣>5\lvert\theta\rvert>5, and no iterate of any method ever exceeds ∣θ∣=4\lvert\theta\rvert=4, so the modified region is never visited.

Rerun with a step size that satisfies the theory. With LH=296L_H=296, condition (42) and h≤h4h\le h_4 require h≤1.3×10−4h\le1.3\times10^{-4}, which h=10−3h=10^{-3} does not meet. We therefore reran all methods with h=10−4h=10^{-4}, T=4000T=4000, and S=3000S=3000. We use 20 seeds, 10 with initial point θ0>0\theta_0>0 and 10 with θ0<0\theta_0<0, where θ0∼Unif[−4,4]\theta_0\sim\mathrm{Unif}[-4,4]. VCHD is run exactly as in Algorithm 1, with θk,0∼μ0=Unif[−4,4]\theta_{k,0}\sim\mu_0=\mathrm{Unif}[-4,4] redrawn at every outer iteration.

Methodmean ∣vk∣\lvert v_k\rvertJτ(vk)J_\tau(v_k)
VCHD, Algorithm 1 (independent restarts)0.026 ± 0.0090.8529 ± 0.0005
HPO-SGLD0.191 ± 0.0800.8905 ± 0.0274
AID-HG0.592 ± 0.0351.0694 ± 0.0217
HG-MS0.943 ± 0.4461.3787 ± 0.4351

For each seed, ∣vk∣\lvert v_k\rvert and Jτ(vk)J_\tau(v_k) are averaged over the last 50 of the 200 outer iterations. Each entry is the mean ± standard deviation of these per-seed averages over the 20 seeds. For reference, v⋆=0v^\star=0 and Jτ(v⋆)=0.8521J_\tau(v^\star)=0.8521.

Discussion on the assumptions

  • Strong convexity in the tails. Proposition 4.3 shows that this can be enforced by a tail regularizer without changing the lower-level solution sets, provided these sets are uniformly bounded.
  • Bounded outer loss. This assumption is natural for a minimization problem: a lower bound on ff is standard, and an upper bound is mild because the regions where ff is very large are not of interest when minimizing.
  • Global smoothness. This is used for the stability of the SGLD discretization, and it is a genuine restriction: for drifts of super-linear growth, Euler-type schemes can diverge, and one needs tamed or projected Langevin steps [1]. Extending the analysis in this direction is an important future work.

Neural-network experiment. The reviewer is right that the Adam-drift Langevin update of Section 5.3 is not the kernel we analyze. Appendix B.3 already states that we do not claim this chain preserves the exact Gibbs law, and we will state this limitation in the main text as well. Analyzing preconditioned or adaptive Langevin kernels is an important direction for future work.

[1] N. Brosse, A. Durmus, É. Moulines, and S. Sabanis. “The tamed unadjusted Langevin algorithm.” Stochastic Processes and their Applications, 129(10):3638–3663, 2019. arXiv:1710.05559.

W2: We thank the reviewer for this insightful comment. The reviewer is right that Theorem 4.10 establishes stationarity for the fixed-temperature objective JτJ_\tau, which is the objective of our value-centric formulation, and not for the optimistic or pessimistic bilevel problem. The two are related as follows.

1.Under Assumptions 4.1 and 4.6, the Gibbs objective is asymptotically sandwiched between the optimistic and pessimistic hyper-objectives as the temperature vanishes: for every v∈Vv \in \mathcal{V}, Φopt(v)≤lim inf⁡τ↓0Jτ(v)≤lim sup⁡τ↓0Jτ(v)≤Φpes(v).\Phi_{\mathrm{opt}}(v) \le\liminf_{\tau \downarrow 0} J_\tau(v) \le \limsup_{\tau \downarrow 0} J_\tau(v) \le \Phi_{\mathrm{pes}}(v).

When the lower-level solution is unique, S(v)={θ⋆(v)}S(v)=\{\theta^\star(v)\}, the two bounds coincide and lim⁡τ↓0Jτ(v)=f(v,θ⋆(v))=Φ(v)\lim_{\tau \downarrow 0} J_\tau(v) = f(v,\theta^\star(v)) = \Phi(v).

2.In the globally strongly convex case, Proposition 4.7 further shows that ∇Jτ(v)→∇Φ(v)\nabla J_\tau(v) \to \nabla \Phi(v) for every v∈int(V)v\in\mathrm{int}(\mathcal V). Hence, in the classical setting, the hypergradient estimated by VCHD is a consistent approximation of the implicit-differentiation hypergradient.

W3: We thank the reviewer for raising this point. Theorem 4.10 gives an O(ϵ−3)O(\epsilon^{-3}) sample-complexity bound for expected squared projected-gradient stationarity at a fixed temperature. In the revision, we will make explicit how the temperature τ\tau and the inner stepsize hh enter this bound and the cost of sampling from the Gibbs follower.

Dependence of the outer guarantee on τ\tau: Under the current assumption that LJL_J is bounded uniformly in τ\tau, a sufficient sample complexity in the low-temperature regime is O(τ−4e56eLHR2/τϵ−3)\mathcal O(\tau^{-4}e^{56eL_HR^2/\tau}\epsilon^{-3}). Under the additional regularity condition described in our response to Reviewer Zi6S’s Question 1, we obtain LJ(τ)=O(τ−2)L_J(\tau)=O(\tau^{-2}), and the sample complexity becomes O(τ−6e56eLHR2/τϵ−3)\mathcal O(\tau^{-6}e^{56eL_HR^2/\tau}\epsilon^{-3}).

Mixing cost: Fix vv and let δ\delta be the target Wasserstein distance to the Gibbs law πv\pi_v. Let D0D_0 denote the initial distance to the invariant law of SGLD, and let bτ(h)b_\tau(h) bound the distance between that invariant law and πv\pi_v, i.e., the discretization bias. Since the chain cannot be more accurate than this bias, we require δ>bτ(h)\delta>b_\tau(h), in which case tδGibbs=⌈1ch[log⁡c0D0δ−bτ(h)]+⌉t_{\delta}^{\mathrm{Gibbs}}=\left\lceil \frac{1}{ch}\left[\log\frac{c_0D_0}{\delta-b_{\tau}(h)}\right]_{+}\right\rceil updates suffice to reach accuracy δ\delta. For bounded D0D_0 and a stepsize satisfying bτ(h)≤δ/2b_\tau(h)\le\delta/2, substituting c0=eΓ/τc_0=e^{\Gamma/\tau} and c=(κ/2)e−Γ/τc=(\kappa/2)e^{-\Gamma/\tau} gives tδGibbs=O(1+eΓ/τh[Γτ+log⁡1δ]).t_\delta^{\mathrm{Gibbs}}=O\left(1+\frac{e^{\Gamma/\tau}}{h}\left[\frac{\Gamma}{\tau}+\log\frac{1}{\delta}\right]\right).

The factor eΓ/τ/τe^{\Gamma/\tau}/\tau captures the temperature dependence, and the factor 1/h1/h comes from time discretization. We will add this discussion to the revision.

Trade-off in τ\tau: The choice of τ\tau therefore involves a trade-off. A smaller τ\tau brings JτJ_\tau closer to the original bilevel problem, but it makes the hypergradient harder to estimate in two ways: the 1/τ1/\tau factor amplifies the sampling error of the covariance term, and our bound on the mixing time tδGibbst_\delta^{\mathrm{Gibbs}} grows as eΓ/τ/τe^{\Gamma/\tau}/\tau. Figure 3 is consistent with this trade-off: in the hyper-data cleaning experiment, VCHD achieves its best accuracy at the intermediate value τ=5×10−3\tau = 5\times 10^{-3}, outperforming both τ=2×10−3\tau = 2\times 10^{-3} and τ=10−2\tau = 10^{-2}.

We will make the dependence of the sample complexity on the mixing-related constant explicit, and we will discuss its joint dependence on the temperature, mixing time, and optimization accuracy in the revision.

Reviewer_AGmsOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes a distributional formulation of bilevel optimization, replacing the lower-level minimizer with a Gibbs distribution. The authors derive an expectation–covariance hypergradient and develop VCHD, which estimates this gradient using SGLD samples without differentiating through the sampling trajectory. The paper proves an O(ϵ−3)O(\epsilon^{-3}) sample complexity bound under nonconvex lower-level objectives with exterior strong convexity, and evaluates the method on quadratic, double-well, and MNIST data-cleaning problems.

Critical strengths

The covariance-based hypergradient is a simple and potentially useful alternative to implicit differentiation and unrolled differentiation. It avoids Hessian-vector products and does not require maintaining sensitivities through a long sampling trajectory. The experiments show promising results, especially on the data-cleaning task.

Critical weaknesses
  1. The experiments do not yet isolate the benefit of the proposed hypergradient estimator.

This is my main concern. In the double-well experiment, the comparison with HPO-SGLD uses its approximate sensitivity recursion. Appendix B.2 also considers an exact forward-mode variant and shows that restoring the omitted contraction factor removes the strong dependence on trajectory length. However, this stronger variant is absent from the main quantitative comparison.

This matters because the reported advantage may partly reflect the approximation used in the baseline rather than an inherent advantage of covariance-based differentiation.

The MNIST comparison raises a related issue. VCHD uses an Adam-based noisy inner update, whereas HPO-SGLD uses different sampling dynamics and noise scaling. The authors acknowledge that the practical VCHD sampler does not necessarily preserve the target Gibbs distribution. This is a reasonable implementation choice, but it makes it difficult to attribute the performance difference specifically to the proposed hypergradient.

A comparison using the same inner trajectories and sampling budget, changing only the hypergradient estimator, would be much more convincing.

  1. Theorem 4.10 analyzes independently restarted SGLD chains. The experiments instead use persistent chains, and the MNIST implementation additionally uses Adam-based drift.

The warm-start result in Appendix A.8 assumes the conditional-law identity μk,0=μk−1,T.\mu_{k,0}=\mu_{k-1,T}.

This should not be confused with the usual implementation θk,0=θk−1,T\theta_{k,0}=\theta_{k-1,T}. Conditional on the previous algorithmic history, the reused endpoint is already known, so its conditional distribution is generally a Dirac measure rather than the previous conditional terminal law.

The authors correctly formulate the appendix result at the distribution level, but it does not directly establish convergence of the persistent-chain implementation. I therefore find the theoretical justification for the practical method less complete than the presentation might suggest.

Moreover, the O(ϵ−3)O(\epsilon^{-3}) result concerns expected squared stationarity for a fixed-temperature Gibbs objective, with mixing-dependent constants hidden in the bound. Since multimodal inner objectives are a central motivation, some discussion or evidence about the practical mixing cost would strengthen the contribution.

  1. In Section 5.3 (p. 9, lines 447–452), the bound on the classical hypergradient appears incorrect. The preceding implicit-differentiation formula contains a factor (1/n) and the inverse Hessian of the full lower-level objective. The subsequent inequality instead introduces wiw_i and an individual-example Hessian. The bound should follow from

$ \left|\frac{\partial\Phi}{\partial w_i}\right| \le \frac1n |\nabla_\theta\ell_i| |(\nabla_{\theta\theta}^2\ell)^{-1}|{\mathrm{op}} |\nabla\theta f|. $

Questions for authors
  1. Can the authors compare VCHD with exact forward-mode differentiation using matched SGLD trajectories, particularly in the main experimental comparisons? How much of VCHD's advantage remains when the sampling procedure is held fixed?

  2. Is there a convergence argument for the actual persistent-chain initialization used in the experiments, rather than the conditional-law warm-start assumption?

  3. Can the authors provide direct evidence that the estimated hypergradient remains informative, such as gradient norms or alignment with a reference gradient, rather than inferring this primarily from training curves?

5 comments

W1 & Q1: We thank the reviewer for these suggestions. We agree that these experiments are important, and we have now completed them. Before presenting the results, we would like to clarify our aim. We develop a route parallel to the unrolling-based method HPO-SGLD [1] for solving the same problem, one that offers a value-centric modeling perspective and comes with a sound theoretical guarantee. Since the two methods approximate the same hypergradient for the same problem, it is expected and reasonable that they perform comparably.

Broadly speaking, there are two main routes for computing hypergradients in bilevel optimization: algorithm unrolling and implicit differentiation. Unrolling [2] approximates the hypergradient by differentiating through the inner optimization trajectory. It often performs well empirically, but it can incur substantial memory costs, and its theoretical guarantees are often harder to establish. Implicit differentiation [3] instead derives and uses an explicit closed-form expression for the gradient of the hyper-objective, based on the inner optimality condition or, in our case, on the form of the distributional follower. This typically leads to more principled algorithms with stronger theoretical properties.

In this paper, we develop a method for bilevel optimization with a distributional follower within the implicit-differentiation framework, which can be viewed as a parallel development to HPO-SGLD [1]. Our method is based on a closed-form covariance-based hypergradient. It requires no second-order information, and it comes with a nonasymptotic convergence guarantee. Our intention is not to provide an algorithm that performs strictly better than HPO-SGLD. We regard the two as parallel routes to the same bilevel problem: both hypergradients target the same objective, so under a fair comparison their performance should in principle be comparable, and we neither expect nor observe that one is uniformly better.

Here provide the experiment details:

Double-well. We reran the double-well experiment with 20 seeds. All methods use the same θ0\theta_0 and the same SGLD sampler, so they differ only in the hypergradient. The optimum is v⋆=0v^\star=0, with Jτ(v⋆)=0.8521J_\tau(v^\star)=0.8521. We report three statistics over the last 50 of the K=200K=200 outer iterations and over 3 seeds: v~\tilde v, the mean distance of the iterates from v⋆v^\star; (2) mean sd, the standard deviation of vkv_{k} ; and (3) JτJ_\tau, mean of the outer objective.

Methodv~\tilde v (θ0>0\theta_0>0)v~\tilde v (θ0<0\theta_0<0)v~\tilde vmean sdJτ(vk)J_\tau(v_k)
VCHD0.0650.0760.0700.0480.857
HPO-SGLD (exact mode)0.1180.1140.1160.0960.867
HPO-SGLD0.2060.1880.1970.1660.892

Part of the gap reported in the paper is therefore due to the approximation, and we will state this clearly in the revision. VCHD nevertheless remains closer to the optimum and more stable than the exact variant.

In large-scale problems, however, the exact forward mode is impractical, and the first-order recursion is the practical choice. With θ∈Rdθ\theta\in\mathbb{R}^{d_\theta} and v∈Rdvv\in\mathbb{R}^{d_v}, the exact recursion requires storing a dθ×dvd_\theta\times d_v matrix and computing dvd_v Hessian-vector products per step, so both memory and cost grow linearly with dvd_v.

Data cleaning with the inner sampler held fixed. The result supports that: the advantage of VCHD reported in the paper comes largely from the inner sampler. Under the controlled setting, the performance of VCHD and HPO-SGLD is comparable. As explained above, this is what we expect, since the two hypergradients are two routes to the same objective.

HypergradientMean test errorValidation lossWeight separation
VCHD2.41 ± 0.310.187 ± 0.0040.921 ± 0.012
VCHD + cic_i2.20 ± 0.240.108 ± 0.0090.949 ± 0.010
HPO-SGLD, M=400M=4002.26 ± 0.300.086 ± 0.0090.985 ± 0.003
HPO-SGLD, M=100M=1002.15 ± 0.190.089 ± 0.0060.986 ± 0.004

All methods use the same inner update of VCHD and differ only in the hypergradient. For HPO-SGLD we use the first-order recursion of [1], since the exact mode has high memory cost. We report the results over 3 seeds and last 500 iterations. VCHD + cic_i uses the covariance estimator g^i=−1τSB∑t: i∈Bt(ft−fˉ) (ℓi(θt)−ci)\hat g_i=-\frac{1}{\tau SB}\sum_{t:\,i\in\mathcal B_t}(f_t-\bar f)\,(\ell_i(\theta_t)-c_i), where cic_i is a running average of sample ii's past losses. Weight separation is the fraction of training samples correctly identified as clean or corrupted by thresholding the learned weight at 0.5s.

Ref [1] M. Kim and T. M. Hospedales. A Stochastic Approach to Bi-Level Optimization for Hyperparameter Optimization and Meta Learning. AAAI, 2025.

[2] L. Franceschi, M. Donini, P. Frasconi, and M. Pontil. Forward and Reverse Gradient-Based Hyperparameter Optimization. ICML, 2017.

[3] S. Ghadimi and M. Wang. Approximation Methods for Bilevel Programming. arXiv:1802.02246, 2018.

W2 & Q2: We thank the reviewer for pointing out the gap between the persistent-chain initialization used in our implementation and the distribution-level warm-start assumption in our analysis. Under the assumptions of Theorem 4.10, we obtain the same convergence rate for the persistent-chain implementation θk,0=θk−1,T\theta_{k,0}=\theta_{k-1,T}.

Conditional on the history Gk\mathcal G_k at the start of outer iteration kk, the initial law is the Dirac measure μk,0=δθk−1,T\mu_{k,0}=\delta_{\theta_{k-1,T}}. The main change in the analysis is how we control the contribution of this initial law to the distributional bias W1(μk,t,πvk)W_1(\mu_{k,t},\pi_{v_k}) of the hypergradient estimate. The argument has two steps. First, the analysis of Lemma A.10 still applies and gives W1(μk,t,πvk)≤c0e−cht W1(δθk,0,πˉvk,h)+CbhW_1(\mu_{k,t},\pi_{v_k})\le c_0e^{-cht}\,W_1(\delta_{\theta_{k,0}},\bar\pi_{v_k,h})+C_b\sqrt h. Second, we establish a bound on E∥θk,t∥2\mathbb E\|\theta_{k,t}\|^2 that is uniform over all outer iterations and inner steps. Combined with the second-moment bound for πˉvk,h\bar\pi_{v_k,h}, this yields a bound on E[W1(δθk,0,πˉvk,h)2]\mathbb E[W_1(\delta_{\theta_{k,0}},\bar\pi_{v_k,h})^2] that is uniform in kk. The same moment bound also controls the variance of the retained-sample average when we take expectations of the within-block covariance estimates.

Although the initial term is O(1)O(1) rather than small, it decays geometrically in tt, so its contribution to the bias averaged over the retained window is O(1/(Sh))O(1/(Sh)). Under the parameter choices of Theorem 4.10, this is of the same order as the discretization term Cb2hC_b^2h. The mean-square hypergradient error is therefore again O(1/S+1/(Sh)+h)O(1/S+1/(Sh)+h), and the O(ϵ−3)O(\epsilon^{-3}) sample complexity is unchanged. Due to space limitations, we refer the reviewer to our response to W5 of Reviewer FGm5 for a more detailed proof sketch.

We will replace the argument in Appendix A.8 with this analysis of persistent-chain implementation. We will also clarify in the revision that the Adam-based inner and outer updates used in the MNIST experiment are an empirical variant.

Mixing-dependent constant and mixing cost. We thank the reviewer for raising this point. Theorem 4.10 gives an O(ϵ−3)O(\epsilon^{-3}) sample-complexity bound for expected squared projected-gradient stationarity at a fixed temperature. In the revision, we will make explicit how the temperature τ\tau and the inner stepsize hh enter this bound and the cost of sampling from the Gibbs follower.

Dependence of the outer guarantee on τ\tau: under the current assumption that LJL_J is bounded uniformly in τ\tau, a sufficient sample complexity in the low-temperature regime is O(τ−4e56eLHR2/τϵ−3)\mathcal O(\tau^{-4}e^{56eL_HR^2/\tau}\epsilon^{-3}). Under the additional regularity condition described in our response to Reviewer Zi6S’s Question 1, we obtain LJ(τ)=O(τ−2)L_J(\tau)=O(\tau^{-2}), and the sample complexity becomes O(τ−6e56eLHR2/τϵ−3)\mathcal O(\tau^{-6}e^{56eL_HR^2/\tau}\epsilon^{-3}).

Mixing cost: fix vv and let δ\delta be the target Wasserstein distance to the Gibbs law πv\pi_v. Let D0D_0 denote the initial distance to the invariant law of SGLD, and let bτ(h)b_\tau(h) bound the distance between that invariant law and πv\pi_v, i.e., the discretization bias. Since the chain cannot be more accurate than this bias, we require δ>bτ(h)\delta>b_\tau(h), in which case tδGibbs=⌈1ch[log⁡c0D0δ−bτ(h)]+⌉t_\delta^{\mathrm{Gibbs}}=\left\lceil \frac{1}{ch}\left[\log\frac{c_0D_0}{\delta-b_\tau(h)}\right]_+\right\rceil

updates suffice to reach accuracy δ\delta. For bounded D0D_0 and a stepsize satisfying bτ(h)≤δ/2b_\tau(h)\le\delta/2, substituting c0=eΓ/τc_0=e^{\Gamma/\tau} and c=(κ/2)e−Γ/τc=(\kappa/2)e^{-\Gamma/\tau} gives tδGibbs=O(1+eΓ/τh[Γτ+log⁡1δ]).t_\delta^{\mathrm{Gibbs}}=O\left(1+\frac{e^{\Gamma/\tau}}{h}\left[\frac{\Gamma}{\tau}+\log\frac{1}{\delta}\right]\right).

The factor eΓ/τ/τe^{\Gamma/\tau}/\tau captures the temperature dependence, and the factor 1/h1/h comes from time discretization. We will add this discussion to the revision.

Trade-off in τ\tau: the choice of τ\tau therefore involves a trade-off. A smaller τ\tau brings JτJ_\tau closer to the original bilevel problem, but it makes the hypergradient harder to estimate in two ways: the 1/τ1/\tau factor amplifies the sampling error of the covariance term, and our bound on the mixing time tδGibbst_\delta^{\mathrm{Gibbs}} grows as eΓ/τ/τe^{\Gamma/\tau}/\tau. Figure 3 is consistent with this trade-off: in the hyper-data cleaning experiment, VCHD achieves its best accuracy at the intermediate value τ=5×10−3\tau = 5\times 10^{-3}, outperforming both τ=2×10−3\tau = 2\times 10^{-3} and τ=10−2\tau = 10^{-2}.

W3 We thank the reviewer for carefully checking this derivation. We will correct the bound in the revised manuscript.

Reviewer_Zi6SOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper considers bilevel optimization problems where the lower-level response is modeled by a Gibbs distribution πv∝exp⁡(−ℓ(v,⋅)/τ)\pi_v \propto \exp(-\ell(v,\cdot)/\tau) over the lower-level variable, and the value function JτJ_\tau is the expectation of the outer objective ff under this distribution. The authors derive an expectation–covariance expression of the hypergradient and propose VCHD, a double-loop algorithm that samples from πv\pi_v with SGLD and estimates the hypergradient from these samples. They prove that VCHD reaches an ϵ\epsilon-stationary point with O(ϵ−3)\mathcal{O}(\epsilon^{-3}) sample complexity. Experiments on a quadratic problem, a double-well problem and a data cleaning task on MNIST illustrate the method.

Critical strengths
  • S1: The proposed algorithm VCHD is novel to my knowledge and is shown to reach an ϵ\epsilon-stationary point with O(ϵ−3)\mathcal{O}(\epsilon^{-3}) sample complexity. This non-asymptotic rate does not require global strong convexity or a PL assumption for the lower level. The theoretical analysis is sound.
Critical weaknesses
  • W1: The optimal-value-centered formulation is claimed as a contribution (lines 93–94, see also the abstract). This is an overstatement since [1] already proposes this formulation (see Equations (2) and (5) in [1]), as acknowledged by the authors themselves (lines 120–121).

  • W2: In the data cleaning experiment, Diff+Neumann memorizes the corrupted labels (training accuracy of about 0.9 vs. 0.7 for VCHD) and has a much higher test error. However, no ablation separates the effect of the value-centric formulation from the regularizing effect of the noise injected in the inner loop, which is known to mitigate the memorization of noisy labels [2]. Running Diff+Neumann with the same noise injection, or an experiment on a task without label noise, would clarify where the gain comes from. Moreover, all results come from a single seed, which makes it hard to assess the significance of the reported differences.

[1] M. Kim & T. M. Hospedales, A Stochastic Approach to Bi-Level Optimization for Hyperparameter Optimization and Meta Learning, AAAI 2025

[2] Z. Xie et al., Artificial Neural Variability for Deep Learning: On Overfitting, Noise Memorization, and Catastrophic Forgetting, Neural Computation 2021

Questions for authors
  • Q1: Can the smoothness of JτJ_\tau (Assumption 4.8) be derived from Assumptions 4.1 and 4.6, as classically done in bilevel optimization in the strongly convex inner case? If so, how does LJL_J depend on τ\tau?
4 comments

W1 We thank the reviewer for the careful reading and for the suggested ablation. We apologize for the overstatement. The reviewer is right: the Gibbs-averaged objective already appears in Eqs. (2) and (5) of [1], and listing the formulation as our contribution was inconsistent with our own related-work section. We will revise the abstract, the introduction, and the contribution statement to say this clearly. This was not our intention, and we apologize for the confusion. Below we state our contribution more clearly.

Broadly speaking, bilevel optimization has two main routes for computing hypergradients: algorithm unrolling and implicit differentiation. Unrolling [2–4] approximates the hypergradient by differentiating through the inner optimization trajectory, possibly with truncation. It often performs well empirically, but it can incur substantial memory costs, and its theoretical guarantees are often harder to establish or require strong assumptions. Implicit differentiation [5–7] instead derives and uses an explicit closed-form expression for the gradient of the hyper-objective, based on the inner optimality condition or, in our case, on the form of the distributional follower. This typically leads to more principled algorithms with stronger theoretical properties, although their practical performance depends on how well the underlying assumptions hold.

In this paper, we develop what is, to the best of our knowledge, the first method for bilevel optimization with a distributional follower within the implicit-differentiation framework. It can be viewed as a parallel development to the existing unrolling-based approach [1]. Importantly, the two routes differ not only in their algorithmic treatment of the hypergradient but also in the interpretations they induce, even when starting from the same mathematical formulation. Specifically, the unrolling-based approach [1] differentiates through an optimization procedure and therefore naturally emphasizes the optimization trajectory and the role of uncertainty throughout that process. In contrast, our approach differentiates through the optimal solution of the distributional follower problem, leading to a more optimal-value-centered interpretation.

Concretely, taking the implicit-differentiation approach leads to a new algorithm and theoretical justification. (1) Covariance-based hypergradient estimator and the VCHD algorithm. We derive a closed-form covariance expression for the hypergradient of JτJ_\tau, which leads to VCHD. The algorithm requires neither differentiation through sampling trajectories nor Hessian-vector products. (2) Nonasymptotic convergence analysis. Our analysis accommodates nonconvex lower-level objectives under exterior strong convexity and explicitly accounts for finite-time mixing, discretization bias, and temporal dependence among the retained SGLD samples. By comparison, the analysis in Supplement B.1 of [1] assumes an infinitesimal inner step size and convergence of the SGLD iterates to the target distribution, which leaves the errors from finite sampling budgets and nonzero step sizes unquantified. We explicitly control the discrepancy between the SGLD sampling distribution and the target distribution, and establish an O(ϵ−3)O(\epsilon^{-3}) sample-complexity bound.

The algorithmic development and its interpretation are closely intertwined. We thank the reviewer for highlighting this distinction, and we will clarify both the connection to [1] and the differences in interpretation in the revised manuscript.

References

[1] M. Kim & T. M. Hospedales, A Stochastic Approach to Bi-Level Optimization for Hyperparameter Optimization and Meta Learning, AAAI 2025

[2] D. Maclaurin, D. Duvenaud, and R. P. Adams. Gradient-based Hyperparameter Optimization through Reversible Learning. ICML, 2015.

[3] L. Franceschi, M. Donini, P. Frasconi, and M. Pontil. Forward and Reverse Gradient-Based Hyperparameter Optimization. ICML, 2017.

[4] A. Shaban, C.-A. Cheng, N. Hatch, and B. Boots. Truncated Back-propagation for Bilevel Optimization. AISTATS, 2019.

[5] F. Pedregosa. Hyperparameter Optimization with Approximate Gradient. ICML, 2016.

[6] S. Ghadimi and M. Wang. Approximation Methods for Bilevel Programming. arXiv:1802.02246, 2018.

[7] J. Lorraine, P. Vicol, and D. Duvenaud. Optimizing Millions of Hyperparameters by Implicit Differentiation. AISTATS, 2020.

W2: We thank the reviewer for suggesting this ablation and we agree that the injected noise is what prevents memorizing the corrupted labels. In our formulation this noise is not an add-on: sampling the Gibbs follower at temperature is exactly noise injection, so avoiding memorization is an advantage, and a natural consequence, of the formulation in this application; the regularization effect described in [2] is another interpretation of why it works. We will add this discussion and [2] to Sec. 5.3 and drop the vanishing-hypergradient explanation.

To verify this, we followed the suggestion and added the same noise to Diff+Neumann. The Diff+Nuemann+noisy and VCHD share the same inner chain (τ\tau, hh, TT, batch size, data and seed) and differ only in the hypergradient: a Neumann-series implicit hypergradient at the final inner iterate θk,T\theta_{k,T} versus the expectation–covariance estimator. Test error is the mean value over the last 500 outer iterations. Acc. on corrupted labels is the training-batch accuracy measured against the corrupted labels over the last 500 outer iterations. All entries are mean ± standard deviation over three seeds; each seed also redraws the training subset, the validation split and the corruption pattern.

Inner settingMethodTest error (%)Acc. on corrupted labelsValidation loss
h=5×10−3h=5\times10^{-3}, T=500T=500, τ=2×10−3\tau=2\times10^{-3}Diff+Neumann + noise, K=10K=102.81 ± 0.330.684 ± 0.0010.125 ± 0.013
Diff+Neumann + noise, K=50K=502.68 ± 0.120.684 ± 0.0010.114 ± 0.002
VCHD2.41 ± 0.310.683 ± 0.0020.187 ± 0.004

With the noise, Diff+Neumann also stops memorizing (accuracy on corrupted labels is around 0.68, about the same as VCHD), Diff+Neumann’s accuracy on the corrupted labels falls from 0.83 to 0.68, and its test error drops from about 14% to 2.7–2.8%, which confirms that the gain comes from the injected noise. In the revision, we will state this explicitly and clarify that the advantage comes mainly from the distributional inner follower, which is realized through noise-injected sampling.

Multi-seed result. We agree that single-seed results are not conclusive, so we have rerun all 22 configurations in Table 2 with three seeds each. Each seed redraws the training subset, the validation split and the label corruption, in addition to all algorithmic randomness. The table below gives each method's best configurations.

MethodConfigurationBest test error (%), seeds 1 / 2 / 3Test error Mean ± sdLast 500 iterations, mean ± sdTrain acc. on corrupted labels
VCHDT=500T=500, h=5×10−3h=5\times10^{-3}, τ=2×10−3\tau=2\times10^{-3}1.55 / 1.63 / 2.021.73 ± 0.252.41 ± 0.310.683 ± 0.002
HPO-SGLDM=500M=500, τ=5×10−3\tau=5\times10^{-3}3.42 / 3.05 / 3.233.23 ± 0.194.82 ± 0.800.725 ± 0.008
Diff+NeumannK=10K=1012.66 / 11.43 / 10.7811.62 ± 0.9514.00 ± 0.990.825 ± 0.003
Diff+NeumannK=50K=5011.09 / 12.17 / 13.1112.13 ± 1.0114.34 ± 1.180.828 ± 0.008
HG-MSN=10N=10, λ=10−3\lambda=10^{-3}, γ=10\gamma=1016.12 / 15.07 / 15.9415.71 ± 0.5620.38 ± 0.480.607 ± 0.002

The ranking of the four methods is the same on every seed. The memorization gap also reproduces on every seed: Diff+Neumann's (no inner injected noise) accuracy on the corrupted labels is 0.83 (0.90 ± 0.01 for K=500K=500) against 0.68 for VCHD. The other VCHD configurations are similarly stable in terms of the test error, for example 2.80 ± 0.09% at T=100T=100, h=10−3h=10^{-3}, τ=5×10−3\tau=5\times10^{-3} and 2.00 ± 0.02% at T=500T=500, h=10−3h=10^{-3}, τ=5×10−3\tau=5\times10^{-3}.

We thank the reviewer for this question. Assumptions 4.1 and 4.6 alone are insufficient to derive smoothness of JτJ_\tau. We will strengthen Assumption 4.6 by requiring that there exists Lvv<∞L_{vv}<\infty such that \|\nabla_v f(v,\theta)-\nabla_v f(v',\theta)\| \le L_{vv}\|v-v'\|, v,v'\in\mathcal V, \theta\in\mathbb R^d.\tag{R1} This condition is implied by the joint Lipschitz continuity of ∇f\nabla f assumed in Assumption 2 of Ji, Yang, and Liang, Bilevel Optimization: Convergence Analysis and Enhanced Design.

Under Assumptions 4.1, 4.6, and (R1), one choice of the smoothness constant is Lτ=Lvv+CfLHτ+(2LfvLHτ+2CfLH2τ2)b+dτaL_\tau=L_{vv}+\frac{C_fL_H}{\tau}+\left(\frac{2L_{f_v}L_H}{\tau}+\frac{2C_fL_H^2}{\tau^2}\right)\frac{b+d\tau}{a}. Here a,ba,b are the constants in Lemma 4.4; LHL_H is from Assumption 4.1; and Lfv,CfL_{f_v},C_f are from Assumption 4.6.

We provide the derivation sketch below. First, Lemma 4.4 gives $\langle\theta,\nabla_\theta\ell(v,\theta)\rangle \ge a|\theta|^2-b$. Integrating on both side of ∂∂θi(θipv(θ))=pv(θ)−1τθi∂ℓ(v,θ)∂θipv(θ)\frac{\partial}{\partial \theta_i}\left(\theta_i p_v(\theta)\right) = p_v(\theta) - \frac{1}{\tau}\theta_i \frac{\partial \ell(v,\theta)}{\partial \theta_i}p_v(\theta) yields $\mathbb E_{\pi_v} \langle\theta,\nabla_\theta\ell(v,\theta)\rangle=d\tau$. Thus, sup⁡v∈VEπv∥θ∥2≤Mτ:=b+dτa\sup_{v\in\mathcal V}\mathbb E_{\pi_v}\|\theta\|^2\le M_\tau:=\frac{b+d\tau}{a}.

We next provide the bound for the covariance for functions under the Gibbs distribution πv\pi_v, which will be used later. For LψL_\psi-Lipschitz function ψ\psi, with independent Θ,Θ′∼πv\Theta,\Theta'\sim\pi_v, we have Eπv∥ψ−Eπvψ∥2=12E∥ψ(Θ)−ψ(Θ′)∥2≤Lψ22E∥Θ−Θ′∥2≤Lψ2Mτ\mathbb E_{\pi_v}\|\psi-\mathbb E_{\pi_v}\psi\|^2 =\frac12\mathbb E\|\psi(\Theta)-\psi(\Theta')\|^2 \le \frac{L_\psi^2}{2}\mathbb E\|\Theta-\Theta'\|^2 \le L_\psi^2M_\tau. Then, for LχL_\chi-Lipschitz function χ\chi, applying Cauchy–Schwarz and the above bound we have

\le L_{\psi}L_{\chi}M_{\tau}. \tag{R2}$$Now fix $v_1,v_2\in\mathcal V$, and define $\Delta:=v_2-v_1$, $D:=\|\Delta\|$, $v_s:=v_1+s\Delta$ and $\nu_s:=\pi_{v_s}$. For a given function $\psi(\theta)$, Lemma A.17 gives $$\frac{d}{ds}\mathbb{E}_{\nu_s}[\psi]= -\frac{1}{\tau}\operatorname{Cov}_{\nu_s}(\psi,q_s).\tag{R3}$$ where \$q_s(\theta):= \langle\nabla_v\ell(v_s,\theta),\Delta\rangle\$. Assumption 4.1 implies $\operatorname{Lip}_\theta(q_s)\le L_H D$. For $i=1,2$, we use $\pi_i:=\pi_{v_i}$, $F_i:=f(v_i,\cdot)$, $A_i:=\nabla_v f(v_i,\cdot)$ and $B_i:=\nabla_v\ell(v_i,\cdot)$. So the covariance-based hypergradient is \$\nabla J_\tau(v_i)=\mathbb E_{\pi_i}[A_i] -\frac1\tau \operatorname{Cov}_{\pi_i}(F_i,B_i)\$. We first bound the difference of the expectation terms. Applying (R2), (R3), and $\operatorname{Lip}_{\theta}(A_1)\le L_{f_v}$, gives $\\|\mathbb{E}_{\pi_1}A_1-\mathbb{E}_{\pi_2}A_1\\|\le \frac{L_{f_v}L_H M_{\tau}}{\tau}D$. Condition (R1) gives $\\|\mathbb{E}_{\pi_2}(A_1-A_2)\\|\le L_{vv}D$. Combining the above two bounds gives $$\\|\mathbb{E}_{\pi_1}A_1-\mathbb{E}_{\pi_2}A_2\\|\le\left(L_{vv}+\frac{L_{f_v}L_H M_{\tau}}{\tau}\right)D.\tag{R4}$$ Next, to bound $\operatorname{Cov}_{\pi_1}(F_1,B_1)-\operatorname{Cov}_{\pi_2}(F_2,B_2)$. Differentiating the covariance of $F_1,B_1$ gives \$\\frac{d}{ds}\\operatorname{Cov}\_{\\nu\_s}(F\_1,B\_1)=-\\frac{1}{\\tau}\\mathbb{E}\_{\\nu\_s}\\!\\left[ (F\_1-\\mathbb{E}\_{\\nu\_s}F\_1)(B\_1-\\mathbb{E}\_{\\nu\_s}B\_1)(q\_s-\\mathbb{E}\_{\\nu\_s}q\_s)\\right].\$ Since $|F_1-\mathbb{E}_{\nu_s}F_1|\le 2C_f$, the moment bounds used in (R2), together with Cauchy–Schwarz, $\operatorname{Lip}_{\theta}(B_1)\le L_H$, and $\operatorname{Lip}_{\theta}(q_s)\le L_H D$, imply\$\\left\\|\\frac{d}{ds}\\operatorname{Cov}\_{\\nu\_s}(F\_1,B\_1)\\right\\|\\le\\frac{2C\_f L\_H^2M\_{\\tau}}{\\tau}D\$. Integrating over $s\in[0,1]$ gives $$\\|\operatorname{Cov}_{\pi_1}(F_1,B_1)-\operatorname{Cov}_{\pi_2}(F_1,B_1)\\| \le\frac{2C_f L_H^2M_{\tau}}{\tau}D.\tag{R5}$$ Now we bound the remaining difference $\operatorname{Cov}_{\pi_2}(F_1,B_1)-\operatorname{Cov}_{\pi_2}(F_2,B_2)$. For $F_1-F_2$, we have $F_2(\theta)-F_1(\theta)=\int_0^1\langle\nabla_v f(v_s,\theta),\Delta\rangle ds$, so Assumption 4.6 implies $\operatorname{Lip}_{\theta}(F_1-F_2)\le L_{f_v}D$. Applying (R2) and $\operatorname{Lip}_{\theta}(B_1)\le L_H$ gives $\\|\operatorname{Cov}_{\pi_2}(F_1-F_2,B_1)\\| \le L_{f_v}L_H M_{\tau}D.$ Moreover, Assumption 4.1 gives $\sup_{\theta}\\|B_1(\theta)-B_2(\theta)\\|\le L_H D$. Applying Cauchy–Schwarz and $|F_2|\le C_f$ yields $\\|\operatorname{Cov}_{\pi_2}(F_2,B_1-B_2)\\|\le C_f L_H D.$ Combining above bounds with (R4), (R5) and (R6), $$\\|\nabla J_{\tau}(v_1)-\nabla J_{\tau}(v_2)\\|\le\left[L_{vv}+\frac{2L_{f_v}L_H M_{\tau}+C_f L_H}{\tau}+\frac{2C_f L_H^2M_{\tau}}{\tau^2}\right]\\|v_1-v_2\\|.$$

I thank the authors for their response.

I still have a concern regarding W2. You claim that “the gain comes from the injected noise”, but this noise only affects the inner problem resolution, independently of the bilevel formulation. It is therefore not clear that any gain comes from the distributional formulation of the bilevel problem, i.e., the reweighting. Is the reweighting actually better with this formulation than with the classical bilevel formulation of data reweighting? Since the main contribution of the paper is distributional bilevel optimization, the current experiments do not properly validate the proposed method.

For this reason, I keep my score.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.