- 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
-
Clear formulation: The Gibbs follower provides a principled way to account for multiple lower-level solutions and their neighborhoods in nonconvex landscapes.
-
Practical hypergradient computation: The expectation–covariance identity avoids explicit Hessian inversion and differentiation through the inner optimization trajectory.
-
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
-
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. -
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 . This does not generally imply stationarity or optimality for the original bilevel problem. -
The complexity bound leaves the cost of low-temperature sampling unclear.
The 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. -
The explanation of vanishing classical hypergradients contains an incorrect bound.
\le \frac{1}{n} \\|\nabla_ \theta\ell_i\\|\ \\|[\nabla_ {\theta\theta}^ {2}\ell]^{-1}\\|_ {\mathrm{op}}\ \\|\nabla_ \theta f\\|.$$
On page 9, the corresponding bound for the exact hypergradient should be -
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
W2: We thank the reviewer for this insightful comment. The reviewer is right that Theorem 4.10 establishes stationarity for the fixed-temperature objective , 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 ,
When the lower-level solution is unique, , the two bounds coincide and .
2.In the globally strongly convex case, Proposition 4.7 further shows that for every . 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 sample-complexity bound for expected squared projected-gradient stationarity at a fixed temperature. In the revision, we will make explicit how the temperature and the inner stepsize enter this bound and the cost of sampling from the Gibbs follower.
Dependence of the outer guarantee on : Under the current assumption that is bounded uniformly in , a sufficient sample complexity in the low-temperature regime is . Under the additional regularity condition described in our response to Reviewer Zi6S’s Question 1, we obtain , and the sample complexity becomes .
Mixing cost: Fix and let be the target Wasserstein distance to the Gibbs law . Let denote the initial distance to the invariant law of SGLD, and let bound the distance between that invariant law and , i.e., the discretization bias. Since the chain cannot be more accurate than this bias, we require , in which case updates suffice to reach accuracy . For bounded and a stepsize satisfying , substituting and gives
The factor captures the temperature dependence, and the factor comes from time discretization. We will add this discussion to the revision.
Trade-off in : The choice of therefore involves a trade-off. A smaller brings closer to the original bilevel problem, but it makes the hypergradient harder to estimate in two ways: the factor amplifies the sampling error of the covariance term, and our bound on the mixing time grows as . Figure 3 is consistent with this trade-off: in the hyper-data cleaning experiment, VCHD achieves its best accuracy at the intermediate value , outperforming both and .
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.
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)2, R=5, and x=∣θ∣−R.
This problem satisfies Assumptions 4.1, 4.6, and 4.8 with explicit constants: −4≤∂θθ2ℓ≤296 (so LH=296), ∂θθ2ℓ=296 for ∣θ∣≥R, ∣f∣≤34, Lf=10, Lfℓv=79, and LJ=1.50 (so β=0.05≤1/(2LJ)). Jτ is strongly convex on V=[−4,4] with unique minimizer v⋆=0. For every v∈V, the Gibbs density at ∣θ∣=R is below e−1100 relative to its value at the mode, so πv, Jτ, and ∇Jτ 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, and no iterate of any method ever exceeds ∣θ∣=4, so the modified region is never visited.
Rerun with a step size that satisfies the theory. With LH=296, condition (42) and h≤h4 require h≤1.3×10−4, which h=10−3 does not meet. We therefore reran all methods with h=10−4, T=4000, and S=3000. We use 20 seeds, 10 with initial point θ0>0 and 10 with θ0<0, where θ0∼Unif[−4,4]. VCHD is run exactly as in Algorithm 1, with θk,0∼μ0=Unif[−4,4] redrawn at every outer iteration.
For each seed, ∣vk∣ and Jτ(vk) 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⋆=0 and Jτ(v⋆)=0.8521.
Discussion on the assumptions
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.