Achieving Single-Level Complexity in Stochastic Bilevel Optimization

56 concepts46 papers1 proposal

The Hierarchical Bottleneck

Bilevel optimization models problems where one optimization task is nested inside another. Formally, we seek to minimize an upper-level objective function dependent on the optimal solution of a lower-level problem:

$$\min_{x} f(x, y^*(x)) \quad \text{subject to} \quad y^*(x) = \arg\min_{y} g(x, y)$$

This framework is essential for modern machine learning applications like hyperparameter tuning, meta-learning, and reinforcement learning. However, optimizing a bilevel objective is notoriously difficult. To compute the gradient of the upper-level objective—the hypergradient—we must account for how the inner optimal solution $y^*(x)$ shifts in response to changes in the outer variable $x$. By implicit differentiation, this hypergradient takes the form:

$$\nabla f(x, y^*(x)) = \nabla_x f(x, y^*(x)) - \nabla_{xy}^2 g(x, y^*(x)) \left[ \nabla_{yy}^2 g(x, y^*(x)) \right]^{-1} \nabla_y f(x, y^*(x))$$

In a stochastic setting, we do not have direct access to the true functions or their derivatives; we only observe noisy, sample-based estimates. This introduces a severe bias-variance-cost tradeoff. If we use a traditional "double-loop" approach—fully solving the lower-level problem to high precision before taking a single outer step—the sample complexity explodes. Conversely, if we update $x$ using an inaccurate or biased estimate of $y^*(x)$, the error cascades, destroying convergence guarantees.

For years, this structural dependency led to a persistent theoretical gap: stochastic bilevel algorithms required significantly more data samples to reach an $\epsilon$-stationary point than standard, single-level stochastic gradient descent (SGD).

The Parity Principle

The core insight uniting recent work in this domain is that the hierarchical structure of bilevel optimization does not inherently impose a sample complexity penalty. Through sophisticated algorithmic coupling and variance reduction, stochastic bilevel optimization can achieve the exact same asymptotic sample complexity as standard single-level optimization.

To find an $\epsilon$-stationary point of a smooth, non-convex objective:

  • Standard single-level SGD requires $\mathcal{O}(\epsilon^{-2})$ samples.
  • Advanced variance-reduced single-level methods require $\mathcal{O}(\epsilon^{-1.5})$ samples.

A series of recent breakthroughs has demonstrated that bilevel algorithms can match these lower bounds exactly, establishing a bilevel-to-single-level complexity parity.

Single-Timescale Tracking and Hidden Smoothness

To avoid the computational burden of fully solving the inner problem at every iteration, modern algorithms employ single-loop, single-timescale updates. Instead of waiting for the inner loop to converge, the outer variable $x$ and the inner variable $y$ are updated simultaneously.

The intuition behind why this works lies in treating the inner optimization as a dynamic tracking problem. If the lower-level update moves fast enough to track the drifting optimal solution $y^*(x)$, the tracking error can be controlled and shown to decay at the same rate as the outer gradient.

Tianyi Chen et al. uncovered a "hidden smoothness" within this nested structure. They proved that a simple alternating stochastic gradient method (ALSET) can achieve a sample complexity of $\mathcal{O}(\epsilon^{-2})$, matching the optimal rate of standard non-nested SGD.

Early iterations of these single-timescale proofs required restrictive, high-order derivative conditions (such as third-order smoothness of the lower objective $g$). To relax these assumptions, Tesi Xiao developed the Moving-Average StOchastic Bilevel Algorithm (MA-SOBA) in Optimal Algorithms for Stochastic Bilevel Optimization under Relaxed Smoothness Conditions, demonstrating that the $\mathcal{O}(\epsilon^{-2})$ parity bound holds under standard, relaxed smoothness conditions by utilizing a moving-average estimator to stabilize the coupled sequences.

Amortized Implicit Differentiation

Even if the inner variable tracks $y^*(x)$ perfectly, estimating the hypergradient still requires computing the inverse Hessian term $\left[ \nabla_{yy}^2 g \right]^{-1} \nabla_y f$. Solving this linear system from scratch at every step is computationally crippling and introduces massive stochastic variance.

To circumvent this, researchers reformulate the problem by treating the inner optimization, the associated linear system, and the outer variable as a single, jointly evolving dynamical system. By maintaining a running estimate of the inverse Hessian vector product, the cost of implicit differentiation is amortized across iterations.

Mathieu Dagréou et al. introduced SABA, a framework that updates all variables jointly such that every update direction is a sum of individual sample derivatives. This allows the algorithm to achieve a $\mathcal{O}(1/T)$ convergence rate, matching the efficiency of state-of-the-art single-level methods. In a similar vein, Michael Arbel et al. proposed AmIGO, which uses warm-starts for both the inner solution and the implicit gradient estimation. The authors proved that this amortization allows the algorithm to match the theoretical complexity of an unbiased gradient oracle, effectively eliminating the speed penalty of the nested structure.

Double-Momentum and Variance Reduction

To push the sample complexity down from $\mathcal{O}(\epsilon^{-2})$ to the accelerated single-level rate of $\mathcal{O}(\epsilon^{-1.5})$, algorithms must simultaneously suppress the variance of both the upper-level hypergradient and the lower-level tracking sequence. This requires integrating variance reduction or momentum into both levels of the optimization.

Prashant Khanduri et al. introduced SUSTAIN, a single-timescale algorithm that applies recursive momentum to both the upper and lower-level gradient updates. This double-momentum mechanism cancels out the accumulated variance from the nested dependencies, allowing SUSTAIN to hit the optimal $\mathcal{O}(\epsilon^{-1.5})$ sample complexity while completely avoiding expensive Hessian matrix inversions.

Concurrently, Junjie Yang et al. proposed two accelerated algorithms—MRBO (using recursive momentum) and VRBO (using variance reduction)—confirming that managing hypergradient variance yields a provable jump to $\mathcal{O}(\epsilon^{-1.5})$.

To achieve this optimal rate in general expectation settings without requiring large, precision-dependent batch sizes, Tianshu Chu et al. designed SPABA. By adapting the Probabilistic Gradient Estimator (PAGE) to a decoupled bilevel framework, the authors proved that the addition of momentum to stochastic updates is the critical factor that closes the theoretical complexity gap, allowing nested optimization to reach convergence as fast as single-level non-convex optimization.

Generalizing Parity to Constraints and Compositions

The principle of single-level complexity parity has recently been extended to more complex optimization landscapes, including constrained boundaries and multi-level functional compositions.

Constrained Bilevel Landscapes

When the upper or lower levels feature constraints, traditional projection steps become prohibitively expensive. To maintain parity, algorithms must be projection-free.

Ruichen Jiang et al. developed CG-BiO for simple bilevel problems, utilizing local linear approximations of the lower-level solution set to achieve a non-asymptotic convergence rate of $\mathcal{O}(1/\epsilon)$ for convex upper objectives. For more general constraints, Nazanin Abolfazli et al. introduced the Inexact Bilevel Conditional Gradient (IBCG) method, proving that constrained bilevel optimization can match the convergence rates of single-level projection-free optimization for both convex and non-convex objectives. Even when equality constraints are imposed on both the upper and lower levels, Quan Xiao et al. demonstrated with AiPOD that a sample complexity of $\mathcal{O}(\epsilon^{-2})$ remains achievable, proving that constraints do not inherently degrade the fundamental convergence scaling.

Multi-Level Compositional Depth

A natural extension of bilevel optimization is multi-level compositional optimization, which features multiple layers of nested functions: $f_1(f_2(\dots f_k(x)))$. Naively, one might expect the required sample complexity to scale exponentially with the depth of the nesting $k$.

Wei Jiang et al. challenged this assumption by introducing Stochastic Multi-level Variance Reduction (SMVR). By simultaneously managing the variance of both function values and Jacobians across all layers, the authors proved that multi-level compositions can match the theoretical lower bounds of single-level stochastic optimization ($\mathcal{O}(\epsilon^{-3})$ for non-convex settings) using small, constant-sized batches. This level-independence ensures that deep hierarchical models do not suffer from a data explosion, cementing the reality of single-level complexity parity across complex, nested structures.

Key Foundational Work

A Near-Optimal Algorithm for Stochastic Bilevel Optimization via Double-Momentum (2021) — contributed 3 concept elements to this direction.
Randomized Stochastic Variance-Reduced Methods for Stochastic Bilevel Optimization (2021) — contributed 1 concept elements to this direction.
Closing the Gap: Tighter Analysis of Alternating Stochastic Gradient Methods for Bilevel Problems (2021) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_optimal_sample_complexity_96bd8101,
  title = {optimal sample complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/optimal-sample-complexity/rdr_96bd81019d50403c9b31fa82c0c3fc57},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_optimal_sample_complexity_96bd8101_v1,
  title = {optimal sample complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/optimal-sample-complexity/rdr_96bd81019d50403c9b31fa82c0c3fc57/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake