acceptodds
Under review as a conference paper at ICLR 2027

Ghost Hypergradients: Value-Gap Oracles for Optimistic Bilevel Learning

Abstract

Optimistic bilevel learning is fragile when the lower-level problem has many minimizers: differentiating an arbitrary selected response can follow a solver-dependent branch rather than the validation-preferred one. We study a value-function alternative based on a vanishing validation tilt. Let be the lower-level training value and the value after adding times the validation loss to the lower objective. The scaled value gap converges, under standard compactness and continuity conditions, to the optimistic objective that minimizes validation loss over the training-optimal set. Building on value-function penalties and equilibrium propagation, we make this perturbation identity algorithmic: by differencing conservative adjoint selections for and , we obtain ghost hypergradients, exact conservative oracles for the ideal finite-tilt surrogate that avoid differentiating a set-valued argmin map. Read at one shared random outer point, their exact scaled difference is almost surely a surrogate gradient, and a certificate error bound lets solve residuals control the computed direction. We prove local surrogate-error bounds, sharpened to for , projected-stationarity convergence, and inexact-solve bounds, exposing the bias–accuracy tradeoff in . On an exact flat-valley diagnostic, Ghost preserves the optimistic direction while selected-response gradients are misaligned. In our empirical study, Ghost achieves the best final test accuracy/runtime tradeoff among the compared bilevel oracles. These results support value gaps as practical first-order oracles for nonsmooth optimistic bilevel learning.

Primary area:
optimization
Keywords:
optimistic bilevel optimization, hypergradient methods, value-function methods, nonsmooth optimization

Reviews

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

The paper addresses optimistic bilevel optimization problems where the lower-level problem may be nonsmooth and have multiple solutions. The authors propose to recast this problem using the value gap Δτ=(Vτ−G)/τ\Delta_\tau = (V_\tau - G)/\tau, where GG is the inner function and VτV_\tau the inner function penalized by the outer function. They show that Δτ\Delta_\tau converges to the optimistic objective at rate O(τθ/(1−θ))O(\tau^{\theta/(1-\theta)}) under a Hölderian error bound. They propose Ghost, an algorithm which performs projected approximate gradient descent on Δτ\Delta_\tau. They provide a convergence result to stationary points of Δτ\Delta_\tau assuming that Δτ\Delta_\tau is smooth. Numerical illustrations are provided on a toy problem and on data hyper-cleaning with SNLI.

Critical strengths
  • S1: This paper analyzes the value-gap approach with nonsmooth lower-level problems, where differencing two valid adjoints can give a wrong direction, and addresses it with compatible readouts at a shared random point. This analysis is new to my knowledge.
Critical weaknesses
  • W1 (Novelty and missing related work): The value-gap formulation is the basis of "value-function-based" or "fully first-order" bilevel methods [1,2,3,4,5], which recast the bilevel problem as min⁡x,yf(x,y)\min_{x, y} f(x,y) s.t. g(x,y)−min⁡y′g(x,y′)≤0g(x, y) - \min_{y'} g(x, y') \leq 0 [1,2], or penalize this gap with weight 1/δ1/\delta [3,4,5]. With f=Lvalf = L_{val}, g=Ltrg = L_{tr}, x=λx = \lambda, y=wy = w and δ=τ\delta = \tau, minimizing the penalized problem in yy gives exactly Δτ\Delta_\tau, and its gradient is exactly the ghost direction (3), already used in [3,4]. Moreover, [5] analyzes Δτ\Delta_\tau for the optimistic objective with multiple nonconvex lower-level solutions for smooth problems. None of these works is cited, and the novelty reduces to the treatment of nonsmooth lower-level problems.

  • W2 (Presentation): I personally find the writing extremely compressed and hard to follow. Many paragraphs (e.g., Sections 4.4 and 6.2) are sequences of standalone caveats with no connecting argument. Moreover, some notations are used before or without definition (Sτ(λ)S_\tau(\lambda), LτL_\tau).

[1] Bo Liu, Mao Ye, Stephen Wright, Peter Stone, and Qiang Liu. BOME! Bilevel Optimization Made Easy: A Simple First-Order Approach. NeurIPS 2022

[2] Daouda Sow, Kaiyi Ji, Ziwei Guan, and Yingbin Liang. A Primal-Dual Approach to Bilevel Optimization with Multiple Inner Minima. arXiv:2203.01123, 2022

[3] Jeongyeol Kwon, Dohyun Kwon, Stephen Wright, and Robert Nowak. A Fully First-Order Method for Stochastic Bilevel Optimization. ICML 2023

[4] Lesi Chen, Yaohua Ma, and Jingzhao Zhang. Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oracles. JMLR 2025

[5] Jeongyeol Kwon, Dohyun Kwon, Stephen Wright, and Robert Nowak. On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximation. ICLR 2024

Questions for authors
  • Q1: How does the proposed formulation compare to the existing literature on value-function-based methods (see W1)? What are the differences and similarities?
3 comments
AuthorsOpenReview ↗

Response to Reviewer ZziA

Thank you for your patience. We spent the past few days completing additional experiments to address your comments, and are now posting our response together with the revised manuscript.

Novelty and prior work

You're right: we share the value-gap formulation, and Kwon et al. (2024) already cover smooth, nonconvex inner problems with multiple solutions. We now cite all five papers and compare them in Appendix D, Table 9. Our contribution is nonsmooth readout compatibility.

Here's an example (Appendix D.2, Example 2). Let λ∈[−1,1]\lambda\in[-1,1] be the outer variable and τ>0\tau>0 the validation-loss weight. Write GG for the optimal training value and VτV_\tau for the optimal value after adding τ\tau times the validation loss:

V_\tau(\lambda)=|\lambda|+\frac{\tau\lambda^2}{2(2+\tau)}.$$ The surrogate is $$\Delta_\tau(\lambda):=\frac{V_\tau(\lambda)-G(\lambda)}{\tau} =\frac{\lambda^2}{2(2+\tau)},\qquad \Delta_\tau'(0)=0.$$ Implement $|\lambda|$ as $2r(\lambda)-\lambda$ in the base graph and $2r(-\lambda)+\lambda$ in the tilted graph, where $r(z)=\max(z,0)$ is ReLU for real $z$. At zero, the usual autodiff convention $r'(0)=0$ gives readouts $-1$ and $+1$. The computed direction $d$ is $$d=\frac{1-(-1)}{\tau}=\frac{2}{\tau},$$ Yet the surrogate derivative is zero, even with exact global inner solves. A shared continuously perturbed evaluation point removes the mismatch almost surely; our bound accounts for the displacement. A consistent unperturbed implementation also works in this example, which lies outside Kwon's smooth-input framework. Clarity and notation We've rewritten Section 4.4 and Sections 6.2-6.3 to connect the problem, construction, evidence and scope. Section 4.4 defines $L_\tau$ as a Lipschitz constant of the surrogate gradient on the evaluation neighborhood. Section 5, Eq. (13), defines $S_\tau(\lambda)$ as the global minimizer set of the tilted inner objective before use. We also separate the finite-SGD experiments from the theory's global-certificate assumptions.

I thank the authors for their response. Would it be possible to highlight the modifications in the manuscript, by using another color for instance? Otherwise, it hard to evaluate the revision.

Thank you for the suggestion. We have added Ghost_Annotated_Revision.pdf to the supplementary material to make the revisions easier to locate. The marked copy includes a legend on the first page: light blue indicates automatically identified additions or wording changes, orange highlights selected substantive changes, and margin notes point reviewers to passages relevant to their comments. It is intended as a navigation aid rather than an exhaustive, line-by-line diff; the clean revised manuscript remains the authoritative version.

In particular, the revised related-work discussion and Appendix D.1, Table 9 clarify the relationship to the five cited papers and the scope of our contribution. Appendix D.2, Example 2 illustrates the nonsmooth readout issue. We have also revised Section 4.4 and Sections 6.2–6.3 for clarity and clarified the definitions of LτL_\tau and SτS_\tau.

We hope the marked copy makes these changes easier to review, and thank you again for the helpful suggestion.

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

The paper studies bilevel learning when the training problem has many equally good solutions. Instead of differentiating through one selected training solution, it compares the optimal training value with and without a small validation term added, and uses the scaled difference as an update that favors the validation-preferred solution. The paper provides theoretical results, controlled examples, and data hyper-cleaning experiments.

Critical strengths

The paper addresses a meaningful problem. Differentiating an arbitrary training solution can give the wrong direction for validation, and the value-gap approach provides an interesting alternative. The analysis explains how the perturbation size and errors in the inner solves affect the update. The controlled examples help make these results understandable.

Critical weaknesses

The two main weaknesses for me are:

  1. The tuning procedures differ across methods. The baselines reuse settings tuned in an earlier comparison suite, while Ghost uses a configuration picked from a small number of pilot runs that were not fully logged, and no common tuning budget is reported. Ghost’s margin over the strongest baseline is only about half a point, so a comparison under the same tuning procedure is needed before the advantage can be judged.
  2. The clean-validation experiment is the only SNLI run that uses the shared perturbation of Algorithm 1, since the main runs read both adjoints at the unperturbed iterate. It is also the only comparison with HG-MS and SQ-G. The paper does not report the hyperparameters or per-seed results for this experiment, and the gains over HG-MS and SQ-G are within the seed spread. This makes the comparison difficult to assess.
Questions for authors
  1. Which metric were Ghost’s pilot runs selected on, and how many configurations were tried? Can all methods be tuned with the same validation protocol and budget, reporting test accuracy at the validation-selected setting?
  2. For the clean-validation experiment, can you report the hyperparameters of every method and how they were selected? Can you also give per-seed results with seed-matched paired differences and intervals for Ghost against HG-MS, SQ-G and UniBiO, as you do for the digits control?
  3. If HG-MS and SQ-G were reimplemented, do the implementations reproduce published results on a setting from the original papers?
  4. Were the five shared baselines in Table 6 rerun under this protocol? Their numbers are within 0.06 points of Figure 4.
1 comment
AuthorsOpenReview ↗

Response to Reviewer CTbH

Thank you for your patience. We spent the past few days completing additional experiments to address your comments, and are now posting our response together with the revised manuscript.

Fair tuning (W1, Q1)

Each method gets six search hours on one A100 80GB, the same tuning set and criterion, and its own predefined space. We try the base configuration first, then a deduplicated random candidate list frozen before evaluation. Both learning rates use base-rate multipliers 0.25, 0.5, 1, 2 or 4. We select by mean final tuning accuracy over search seeds 101/102 and freeze settings for five matched runs. Loading, evaluation and failed/interrupted trials count; queue time doesn't. See Appendix E.4, Tables 15-17, for counts, tie-breaking, spaces and selected settings.

We keep the two-layer, width-4096 RNN, 20% training-label noise and disjoint training/meta/tuning/test splits of 10,000/4,922/4,920/9,824 examples. Runs use two warmup, 100 outer and one refit epoch; test accuracy uses this fixed refit, without test-based selection.

GHOST reaches 70.82 +/- 0.21%, versus 70.27 +/- 0.10% for UniBiO (mean +/- sample SD over five runs). The paired gain is 0.550 percentage points, with 95% confidence interval [0.263, 0.836]. Final-run costs are reported separately from search (Table 1; Appendix C.4, Tables 6-8).

Clean-validation details (W2, Q2)

All eight methods were rerun with six-hour budgets. GHOST uses nonzero shared perturbations here and zero radius in the main comparison. Appendix E.1 gives the protocol; E.4 separates base from selected initial rates. HG-MS's inner/outer bases are 0.02/0.01; SQ-G's are 0.02/0.0269838. Both selected multipliers 1/1, so selected rates equal bases before decay.

HG-MS and SQ-G are SNLI adaptations. HG-MS uses AdamW for candidate and outer updates and the author's CG recurrence through finite negative curvature. SQ-G uses normalized Gaussian directions and dimension-scaled, two-sided differences with common random numbers. E.4 specifies optimizer parameters, CG stopping and the estimator.

MethodTest accuracy (%)GHOST gain (pp), 95% intervalFive-run GPU-hours
GHOST shared71.08 +/- 0.18--12.1
HG-MS70.72 +/- 0.24+0.358 [0.279, 0.438]29.3
SQ-G70.56 +/- 0.28+0.519 [0.390, 0.648]44.7
UniBiO70.21 +/- 0.11+0.869 [0.786, 0.952]15.3

Here pp means percentage points. Gains average GHOST-minus-baseline differences over five matched pairs (initialization, data and random streams). Intervals are pointwise, two-sided paired Student t intervals with four degrees of freedom. All three intervals exclude zero; Holm-adjusted p-values are below 0.001 across these three comparisons. This supports positive gains in this setting. Table 2 lists all eight methods; Tables 10-13 give individual results, costs, paired differences and statistics. R1-R5 label repetitions, not numerical seed IDs.

Original-benchmark checks (Q3)

HG-MS on MNIST and SQ-G on its two-dimensional optimistic toy give means close to published values:

Method and metricPublished meanOur meanRuns
HG-MS accuracy (%)66.0866.105
SQ-G absolute parameter error0.0090.0091010

Appendix E.3, Table 14, reports uncertainty, individual runs, code versions and adaptations. HG-MS uses the last iterate after the 120-second training timer, 500 validation examples, AdamW at both levels and initial inner/outer rates 0.02/0.1, versus CLEAN's 0.02/0.01. SQ-G uses the stated lower-tail/best-so-far adaptation. Published error bars are 95% confidence-interval halfwidths, not SDs. These checks don't guarantee that the SNLI adaptations are correct.

Shared-baseline reruns (Q4)

Yes. UniBiO, VRBO, MA-SOBA, TTSA and StocBiO were rerun alongside GHOST, HG-MS and SQ-G under the CLEAN protocol, including its cubic regularizer and stated precision. Every row in Table 2 uses these runs, not Table 1's quadratic-regularizer comparison. Appendix E gives configurations and all matched repetitions.

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

The paper studies optimistic bilevel learning with nonunique lower-level solutions. It constructs a value-gap surrogate using unperturbed and validation-tilted training objectives, and computes directions by differencing compatible value adjoints. The analysis establishes approximation and inexact-oracle bounds, with stationarity guarantees for a smooth fixed-tilt surrogate. Experiments include analytical diagnostics and SNLI data hyper-cleaning.

Critical strengths
  1. The distinction between solver-selected responses and optimistic solutions is well motivated. The flat-valley diagnostic clearly demonstrates why this distinction matters.

  2. The compatible-readout analysis identifies a meaningful issue with differencing nonsmooth value adjoints. The shared-point construction and sharpened finite-tilt bounds provide useful technical insights.

Critical weaknesses
  1. The incremental contribution is insufficiently established. Kwon et al. (2024) already introduce the same scaled value-gap objective for fixed lower-level feasible sets and consider nonconvex, nonunique lower solutions. Without a direct comparison, it is difficult to assess the significance of the conservative-field and compatibility extensions.

  2. The practical evidence does not sufficiently validate the certified oracle. The theory requires global value-function certificates, whereas the main SNLI implementation uses two SGD steps per inner problem and omits shared perturbations. Table 6 evaluates compatible readouts, but its code, configurations, and per-seed logs are explicitly not provided. These gaps weaken the evidence connecting the theoretical contribution to the reported practical gains.

Questions for authors
  1. Which assumptions and guarantees distinguish your approach from the approach of Kwon et al. (2024), particularly regarding nonsmoothness, certificate requirements, and stationarity of the surrogate versus the original optimistic objective?

  2. Can you provide the missing Table 6 materials and precisely specify the independent-pair implementation?

  3. Can a matched continuation control separate validation-induced changes from ordinary training progress? Specifically, compare tilted and untilted branches initialized from the same checkpoint with equal additional SGD steps and matched training randomness.

3 comments
AuthorsOpenReview ↗

Response to Reviewer RLV7

Thank you for your patience. We spent the past few days completing additional experiments to address your comments, and are now posting our response together with the revised manuscript.

Novelty and guarantees (W1, Q1)

You're right: Kwon et al. (2024) already study the scaled value gap with smooth, nonconvex, nonunique inner problems. Our contribution is nonsmooth readout compatibility: when readout differences are valid generalized gradients and how their errors propagate. Example 2 in Appendix D.2 gives a nonzero direction at zero surrogate derivative despite exact global inner solves. This lies outside Kwon's smooth-input assumptions. Table 9 compares assumptions and guarantees. The readout analysis requires locally Lipschitz, definable data and admissible conservative readouts. Our assumptions aren't uniformly weaker than Kwon's. Outer convergence requires a smooth fixed-tilt surrogate, global-certificate error bounds, a closed convex outer domain and the stated step/error conditions. We establish projected stationarity only for that surrogate (Sections 4-5; Appendix A.6).

Theory and practice (W2)

Agreed: two SGD steps don't certify global optimality. Shared perturbation addresses compatibility; a coherent unperturbed implementation can also work. We separate exact controlled examples from finite-SGD SNLI results: GHOST uses zero radius in the main comparison and nonzero shared perturbations in the clean-validation comparison and pairing control (Sections 4.3-4.4, 6.2-6.3).

Materials and pairing (Q2)

We've added five matched repetitions and paired statistics/costs (Appendix E, Tables 10-13), tuning and implementation details (E.4, Tables 15-17), MNIST checks (E.3) and pairing definitions (E.5). We'll organize and release the complete code upon acceptance.

Let k=0,1,…k=0,1,\ldots index outer updates, N=10,000N=10{,}000 be the training-set size and λk∈RN\lambda_k\in\mathbb R^N be training-weight logits. Set rk=0.001/k+1r_k=0.001/\sqrt{k+1} and draw independent uk,vku_k,v_k uniformly from the unit Euclidean ball in RN\mathbb R^N. With validation-loss weight τ=0.05\tau=0.05, superscripts 00 and τ\tau denote base and tilted evaluation points:

Shared: λk0=λkτ=λk+rkuk.\text{Shared: }\lambda_k^0=\lambda_k^\tau=\lambda_k+r_ku_k.

Independent: λk0=λk+rkuk,λkτ=λk+rkvk.\text{Independent: }\lambda_k^0=\lambda_k+r_ku_k,\quad\lambda_k^\tau=\lambda_k+r_kv_k.

Both arms match initialization, training/meta batches, model randomness and SGD budgets. Within each branch, the solve and derivative readout use the same unprojected point. The independent arm reuses the shared-selected configuration without retuning (Appendix E.1, E.5).

Across five matched repetitions, shared versus independent accuracy is 71.079 +/- 0.176% versus 70.409 +/- 0.343% (mean +/- sample SD). The paired gain is +0.670 percentage points, with 95% confidence interval [0.463, 0.876]. Five-run costs are 12.05 versus 11.65 A100 GPU-hours. Table 18 lists all pairs; R1-R5 label repetitions, not numerical seed IDs.

Matched continuation (Q3)

We forked each shared arm's final-refit checkpoint, fixed its training-weight logits and gave both branches four extra SGD steps at learning rate 0.1. Starting weights, fresh momentum-free optimizers, training minibatches and model randomness were matched. Only the tilted branch added τ=0.05\tau=0.05 times the clean-meta loss.

MetricMean tilted-minus-untilted difference95% confidence interval
Meta cross-entropy-0.0122[-0.01324, -0.01116]
Tuning cross-entropy-0.0054[-0.00682, -0.00398]
Test accuracy (percentage points)+0.1832[+0.1632, +0.2032]

All intervals are pointwise paired Student t intervals over five pairs (four degrees of freedom). Negative loss differences and positive accuracy differences favor tilt. All three continuation tests pass Holm correction together. Tuning data selected configurations earlier but didn't enter these extra updates; the test set is separate. Section 6.3 and Appendix E.5, Tables 19-21, give endpoints and costs. This isolates a small validation-induced benefit beyond equal extra training.

Thank you for your detailed response. My concerns about Q1 and Q3 have been resolved. However, it remains unclear whether the two SGD steps used in the main SNLI experiment achieve the inner-solve accuracy required by the theory. Overall, I will keep my score.

Thank you for the follow-up. We are glad that our response resolved Q1 and Q3. We have not verified that two SGD steps meet the theory’s inner-solve accuracy requirements on SNLI. As Appendix C.2 explains, a small local gradient residual does not certify global inner-solve accuracy in a nonconvex network. The SNLI comparison evaluates the methods under a matched compute budget; the theoretical guarantee applies when the stated inner-solve certificates are available.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.