Extrapolated Warm Starts for the Hidden Solvers in Bilevel Training

When a neural network contains an optimization problem inside it, each training step has to run two extra solvers besides the usual gradient computation. The first finds the inner solution. The second solves a linear system, called the adjoint system, that turns that solution into a gradient for the outer parameters. Examples include a hyperparameter tuner that must retrain a model, or a network layer that solves a quadratic program. Amortized Implicit Differentiation for Stochastic Bilevel Optimization (AmIGO) showed that most of this cost can be removed. Instead of re-solving both problems from scratch, it restarts them from where they ended at the previous outer step, and it takes only a few cheap iterations each time. That restart is zero-order: it assumes the answer has not moved. The outer parameters do move, though, and they move along a fairly smooth path. So the inner solution and the adjoint solution drift along smooth paths too.

This note proposes restarting both hidden solvers from a linear extrapolation of their last two end states, $z_{t-1} + \beta(z_{t-1} - z_{t-2})$. The damping weight $\beta$ is set online from a running estimate of mini-batch noise. The idea comes from optimistic gradient methods. Convergence Rate of O(1/k) for Optimistic Gradient and Extragradient Methods in Smooth Convex-Concave Saddle Point Problems shows that such methods use the difference of consecutive gradients to approximate a look-ahead step at no extra oracle cost. Here the same trick is aimed at a different target: the lag of a solver that is tracking a moving fixed point. The trick is not applied to the outer game itself. The claim is simple and testable. At equal numbers of gradient and matrix-vector calls, extrapolated tracking reaches a given outer validation loss faster than AmIGO's zero-order warm start whenever the outer trajectory is smooth relative to the noise. A noise-aware $\beta$ keeps it from ever doing meaningfully worse.

Core Claim

Take one outer step. The inner solvers run $K$ iterations of a method that contracts error by a factor $\rho<1$ per iteration. Let the target move from $z^*_{t-1}$ to $z^*_t$, and write $\Delta_t = z^*_t - z^*_{t-1}$. Under a zero-order warm start, the steady-state tracking error scales as

$$e_t^{\text{zero}} \approx \frac{\rho^K}{1-\rho^K}\,\|\Delta_t\|, \qquad e_t^{\text{extrap}} \approx \frac{\rho^K}{1-\rho^K}\,\|\Delta_t - \beta\Delta_{t-1}\| + \beta\,\rho^K\sigma.$$

The first expression follows from unrolling the recursion $e_t \le \rho^K(e_{t-1} + \|\Delta_t\|)$. The second follows from the same recursion with the predicted displacement subtracted. The symbol $\sigma$ is the per-step stochastic noise in the solver end states, which a difference of two noisy states amplifies. When the target's velocity changes slowly, the drift term becomes a second difference and is much smaller than $\|\Delta_t\|$. When noise dominates, the right choice is $\beta \to 0$, which recovers AmIGO exactly. The method sets $\beta_t$ by minimizing the bracketed bound. It plugs in exponential moving averages of $\|\Delta_t - \Delta_{t-1}\|$ and of the solver's residual variance, both estimated from quantities the solver already computes. Lower tracking error gives less biased hypergradients. AmIGO's analysis ties that bias directly to outer convergence. So the outer loop should benefit without any change to the outer optimizer.

This is also where the idea stops working, and the note says so up front. In decision-focused learning (training a predictor against the cost of the decisions a downstream solver makes), each training example has its own optimization problem. The same problem comes back only once per epoch, after many outer updates. The "previous two states" for that instance are then stale, and extrapolation should give nothing. The proposal treats this as a predicted negative result and tests it, rather than claiming broad coverage.

Relation to Prior Work

AmIGO supplies the method being modified. Its three-time-scale scheme updates the outer variable, the inner variable and the adjoint variable together, with warm starts, and achieves $O(\epsilon^{-1}\log\epsilon^{-1})$ complexity in the strongly convex stochastic setting. Its updates carry no extrapolation. The note changes only the initialization of the two fast variables.

The optimistic-gradient literature supplies the intuition and the proof tools. That work reads the correction $g_t - g_{t-1}$ as a cheap approximation of an implicit proximal step. Last-Iterate Convergence of Optimistic Gradient Method for Monotone Variational Inequalities contributes last-iterate arguments, which matter here because the solver states are used directly and are not averaged. These papers also constrain the design: their rates assume deterministic gradients, and the file flags stochastic variance as a known weakness of the linear extrapolation step. That is why $\beta$ is noise-adaptive and not fixed at 1.

Improving Sharpness-Aware Minimization by Lookahead motivates the gating choice. It moved optimistic reuse of past gradients into minimization and switches it on only when a measured quantity crosses a threshold. It never looked at solver-in-the-loop pipelines.

Two differentiable-layer papers leave the gap open. A Penalty Approach For Differentiation Through Black-box Quadratic Programming Solvers (dXPP) reduces the backward pass to a symmetric positive definite primal system but solves it fresh at every step. A Fully First-Order Layer for Differentiable Optimization (FFOLayer) replaces Hessians with finite differences on an active-set problem, but it treats the inner solver as a black box. In both, the adjoint solve could be done iteratively, for example with conjugate gradient, and warm-started with extrapolation. That is where the note applies them.

Contrastive Losses and Solution Caching for Predict-and-Optimize reuses stored solutions without any notion of trajectory. It is the relevant comparison for the per-instance regime where extrapolation is predicted to fail.

Research Program

The work has three parts. The first is analysis: extend AmIGO's strongly convex stochastic analysis to extrapolated initialization. The goal is a bound in which hypergradient bias depends on the second difference of the target path plus a $\beta\sigma$ noise term, and a proof that the adaptive $\beta_t$ is never worse than zero-order by more than a constant factor.

The second part is implementation. The extrapolated warm start goes into AmIGO's gradient-descent and conjugate-gradient variants for both the inner and adjoint variables. It also goes into an iterative conjugate-gradient version of dXPP's backward system, and into the inner first-order solves of FFOLayer. Each of these costs two stored vectors per hidden solver and no extra oracle calls.

The third part is diagnosis. On every task the program logs the true tracking error against a high-precision reference solve, the measured $\|\Delta_t\|$ and $\|\Delta_t-\Delta_{t-1}\|$, and the chosen $\beta_t$. These logs show whether any gain comes from the mechanism claimed.

Baselines

The naive reference point is cold-start implicit differentiation, the AID-BiO style method named in AmIGO's comparisons. It solves the inner and adjoint problems from scratch to a fixed tolerance at every outer step, and its cost per step is what amortization is meant to remove. The strongest existing method is AmIGO itself, with zero-order warm starts, in both its gradient-descent and conjugate-gradient forms. It is the published method for this exact bottleneck, and it is the one our change modifies. On the file's benchmarks, AmIGO-CG reached lower 20Newsgroup validation loss "significantly faster than competitors like AID-BiO or ITD", and it was one of the few methods that optimized MNIST dataset distillation at all. No numeric wall-clock or loss value for AmIGO was found on Lacuna, so we will reproduce it ourselves under the settings in its paper.

A second strong competitor spends the budget differently. It gives AmIGO one or two extra inner iterations per outer step, tuned so that its total oracle calls match or exceed ours. This checks whether extrapolation is merely a cheap stand-in for more work. For the layer experiments, the reference is dXPP with a direct Cholesky backward solve, which is exact for a given smoothing parameter. It is compared against the conjugate-gradient backward solve with zero-order and with extrapolated warm starts.

All methods share data, architectures, outer optimizer, step-size schedules and random seeds. Each gets the same hyperparameter search budget over step sizes and $K$, and results are plotted against oracle calls as well as wall-clock time.

Ablations isolate the key ingredient. They compare extrapolating the inner variable only against the adjoint variable only, a fixed $\beta=1$ against adaptive $\beta_t$, and adaptive $\beta_t$ against a $\beta$ tuned by grid search. Beating AmIGO means one of two things. The method could reach AmIGO's final validation loss using at least 25% fewer oracle calls, averaged over five seeds with non-overlapping confidence intervals. Or, at a matched budget, it could show lower measured hypergradient error. A second condition must also hold: the method must not be worse than AmIGO on any task by more than seed noise.

Why not just…?

Why not just take more inner steps, or warm-start as AmIGO already does? More inner steps shrink tracking error geometrically, but each step costs a full oracle call. Extrapolation attacks the drift term at zero oracle cost. The matched-compute baseline above settles this directly. It is a real threat on tasks where the outer path is erratic. The logged $\|\Delta_t - \Delta_{t-1}\|/\|\Delta_t\|$ ratio should predict when the threat wins, and if it wins everywhere the claim is false.

Why not just put momentum or Adam on the inner and adjoint solvers? Momentum speeds convergence toward a fixed target within one outer step, but each outer step still starts from a stale point. Extrapolation instead predicts where the target will be across outer steps. The two mechanisms are distinct and can be combined. We will run heavy-ball conjugate-gradient-style solvers with and without extrapolated initialization to show whether the gains add up or overlap.

Why not just cache solutions, as in predict-and-optimize? Caching fits the per-instance regime, where each problem returns once per epoch and trajectories are too sparse to extrapolate. The solution-caching paper reports order-of-magnitude training speedups there with comparable regret. We expect caching, not extrapolation, to win in that setting, and we include it to confirm the boundary of the method rather than to beat it.

Proposed Experiments

The first experiment uses AmIGO's synthetic strongly convex quadratic bilevel problems, with controlled noise $\sigma$ and a controlled smoothness of the outer path. There the tracking error can be computed exactly and the predicted crossover in $\beta$ checked against the bound. The main experiments are 20Newsgroup hyperparameter optimization, which has more than 100,000 regularization parameters, and MNIST dataset distillation. The metric is validation loss against oracle calls and against wall-clock time, over five seeds.

For layers, the dXPP multi-period portfolio task on 2011–2024 ETF daily returns is run at horizon $H=200$. The learned objective and constraint parameters are shared across steps, and the adjoint systems for a fixed rolling window are revisited often, so the trajectory structure is present. The metric is the relative gradient error against exact KKT gradients. The dXPP paper reports this error between $10^{-7}$ and $10^{-4}$ across most tests, and our method must stay within that band while cutting conjugate-gradient iterations. The metric also includes backward time per step.

The decisive negative control is the energy-cost-aware scheduling task on Irish SEMO data. It is trained with SPO-relax, the linear-programming relaxation from Smart Predict-and-Optimize for Hard Combinatorial Optimization Problems, and solutions are warm-started per instance across epochs. Here we predict that adaptive $\beta_t$ collapses toward zero and that solution caching beats extrapolation.

Three results would count as clear evidence for the idea. On the smooth-path tasks, extrapolation should beat matched-compute AmIGO. The chosen $\beta_t$ should track the measured drift-to-noise ratio. And on the per-instance control, extrapolation should cause no harm. Failure on the second or third would falsify the claimed mechanism even if the first showed a gain.