Bilevel optimization models a hierarchical game where an upper-level decision maker optimizes an objective function $F(x, y)$, subject to the condition that the lower-level variable $y$ is an optimal response to $x$. Mathematically, this is written as:
$$\min_{x} F(x, y^*(x)) \quad \text{s.t.} \quad y^*(x) \in \arg\min_{y} f(x, y)$$
This nested structure is exceptionally powerful. It underpins modern machine learning workflows such as hyperparameter tuning (where $x$ represents hyperparameters and $y$ represents network weights), meta-learning, neural architecture search, and adversarial training.
However, solving these problems at scale has traditionally required a massive theoretical crutch: the assumption of Lower-Level Strong Convexity (LLSC). Recent research is systematically dismantling this assumption, engineering new algorithms capable of navigating landscapes where the inner optimization problem is thoroughly nonconvex.
The Convexity Trap and Why It Breaks
To understand why nonconvexity at the lower level paralyzes classical algorithms, we have to look at how we compute gradients across the two levels.
If we want to update the upper-level variable $x$ using gradient descent, we need the total derivative of $F(x, y^*(x))$ with respect to $x$. By the chain rule, this "hypergradient" is:
$$\nabla_x F(x, y^*(x)) = \nabla_x F(x, y^*) + \nabla_y F(x, y^*) \cdot \nabla_x y^*(x)$$
The bottleneck is the term $\nabla_x y^*(x)$—how the optimal lower-level solution shifts when the upper-level variable changes. Under the classical framework, we assume $f(x, y)$ is strongly convex in $y$. This guarantees that for every $x$, there is exactly one unique, isolated global minimum $y^*(x)$. Because this minimum sits in a smooth, well-behaved bowl where $\nabla_y f(x, y^*(x)) = 0$, we can invoke the Implicit Function Theorem (IFT) to compute the derivative:
$$\nabla_x y^*(x) = - \left[ \nabla_{yy}^2 f(x, y^*) \right]^{-1} \nabla_{yx}^2 f(x, y^*)$$
In deep learning, however, the lower-level objective $f(x, y)$ is often a deep neural network landscape. This landscape is inherently nonconvex, riddled with multiple local minima, saddle points, and flat plateaus. When LLSC is violated, two catastrophic failures occur:
- Discontinuous Jumps: If the lower level has multiple global minima, a tiny, continuous change in $x$ can cause the optimal response $y^*(x)$ to instantly jump from one valley to another. At these points of discontinuity, the derivative $\nabla_x y^*(x)$ simply does not exist.
- Singular Hessians: Without strong convexity, the lower-level Hessian $\nabla_{yy}^2 f(x, y^*)$ can become singular (non-invertible) or negative definite, making the implicit gradient calculation mathematically undefined or numerically explosive.
As highlighted by Songtao Lu in Bilevel Optimization with Coupled Decision-Dependent Distributions and Quan Xiao et al. in Alternating Projected SGD for Equality-constrained Bilevel Optimization, relying on LLSC severely limits the applicability of bilevel optimization to modern deep architectures.
Strategy 1: Value-Function Reformulations
If the arg\min operator is the source of discontinuity, the most direct solution is to eliminate it entirely. We can achieve this by leveraging the lower-level value function, defined as the optimal objective value achieved for a given $x$:
$$v(x) = \min_{y} f(x, y)$$
Using this function, we can rewrite the nested bilevel problem as a single-level constrained optimization problem:
$$\min_{x, y} F(x, y) \quad \text{s.t.} \quad f(x, y) \le v(x)$$
This formulation completely bypasses the requirement for a unique lower-level solution. Even if there are thousands of global minima for a given $x$, they all satisfy the constraint $f(x, y) \le v(x)$.
Classical (IFT) Approach:
x ───► Unique y*(x) ───► Requires Inverting Hessian ∇²_yy f
Value-Function Approach:
x, y ───► Constraint: f(x,y) ≤ v(x) ───► No Hessian Inversion Required
In A Value-Function-based Interior-point Method for Non-convex Bi-level Optimization, Risheng Liu et al. operationalized this intuition by introducing the Bi-level Value-Function-based Interior-point Method (BVFIM). Instead of dealing with the hard constraint, they applied a log-barrier penalty to smoothly enforce $f(x, y) \le v(x)$.
By avoiding the implicit gradient entirely, this family of techniques eliminates the need to compute or invert expensive Hessian matrices. Building on this philosophy, Risheng Liu et al. also developed sl-BAMM in Averaged Method of Multipliers for Bi-Level Optimization without Lower-Level Strong Convexity, which blends the upper and lower objectives into a single-loop dual multiplier framework, proving that convergence can be achieved under general lower-level convexity constraints without requiring strong convexity.
Strategy 2: Smoothing via the Moreau Envelope
While value-function methods are elegant, the constraint $f(x, y) \le v(x)$ can still be mathematically challenging because the value function $v(x)$ itself is often non-smooth and nonconvex. To fix this, researchers have turned to a classic tool from optimization: the Moreau Envelope.
The Moreau envelope of a function is a regularized, smoothed approximation. Instead of looking at the raw lower-level objective $f(x, y)$, we define its Moreau envelope with respect to $y$ as:
$$e_\lambda f(x, y) = \min_{z} \left\{ f(x, z) + \frac{1}{2\lambda} \|z - y\|^2 \right\}$$
The addition of the quadratic penalty $\|z - y\|^2$ acts as a stabilizer. Even if $f(x, z)$ is highly nonconvex and jagged, choosing a sufficiently small parameter $\lambda$ smooths out the local wrinkles of the landscape.
This smoothing property allows researchers to construct single-loop algorithms that update both the upper and lower variables simultaneously, rather than waiting for the lower level to fully converge in an expensive inner loop.
In Rethinking Moreau Envelope for Nonconvex Bi-Level Optimization: A Single-loop and Hessian-free Solution Strategy (and its companion work Moreau Envelope for Nonconvex Bi-Level Optimization: A Single-Loop and Hessian-Free Solution Strategy), Risheng Liu et al. introduced MEHA. By substituting the Moreau envelope into the bilevel architecture, the authors proved that a first-order, single-loop algorithm can reliably find stationary points without needing any lower-level convexity or Polyak-Łojasiewicz (PL) conditions.
Taking this a step further, Songtao Lu proposed the Two-Sided Smoothed Primal-Dual (TSP) method in TSP: A Two-Sided Smoothed Primal-Dual Method for Nonconvex Bilevel Optimization. TSP applies smoothing to both sides of the optimization duality, achieving an optimal $\mathcal{O}(\epsilon^{-4})$ convergence rate to Karush-Kuhn-Tucker (KKT) solutions in fully nonconvex-nonconvex settings.
Strategy 3: Hessian-Free and First-Order Approximations
Even when algorithms successfully bypass the theoretical requirement of LLSC, practical scalability remains a massive hurdle. Traditional hypergradient methods require computing second-order derivatives (Hessian-vector and Jacobian-vector products), which demand immense memory and computation for large neural networks.
To bridge the gap between theory and large-scale deep learning, a parallel line of work focuses on Hessian-free stochastic optimization. The core intuition here is that second-order directional derivatives can be approximated using only first-order gradients evaluated at slightly perturbed points, via finite-difference approximations:
$$\nabla_{yx}^2 f(x, y) \cdot v \approx \frac{\nabla_x f(x, y + \delta v) - \nabla_x f(x, y - \delta v)}{2\delta}$$
By combining this finite-difference trick with momentum-based variance reduction, algorithms can achieve the same theoretical efficiency as second-order methods using only first-order oracle calls.
Second-Order Method:
Compute Explicit Hessian ──► Invert Matrix ──► O(d²) Memory/Time Overhead
Hessian-Free Method:
Evaluate Gradient at (y + δv) ──► Finite Difference ──► O(d) Memory/Time Overhead
In Achieving $\mathcal{O}(\epsilon^{-1.5})$ Complexity in Hessian/Jacobian-free Stochastic Bilevel Optimization (and the identical text Achieving O(ε-1.5) Complexity in Hessian/Jacobian-free Stochastic Bilevel Optimization), Yifan Yang et al. and Peiyao Xiao et al. introduced FdeHBO. This algorithm pairs a single-loop momentum structure with a projection-aided finite-difference step, achieving a state-of-the-art sample complexity of $\mathcal{O}(\epsilon^{-1.5})$ without ever materializing a second-order derivative matrix.
This shift to purely first-order operations is especially vital in distributed environments. In Federated Stochastic Bilevel Optimization with Fully First-Order Gradients, Yihan Zhang et al. designed FedSVRBGD-FO to handle federated bilevel learning across decentralized edge devices. By eliminating Hessian computations, they drastically reduced the communication and memory overhead per device, allowing edge hardware to participate in complex nested optimization tasks like federated meta-learning.
Mapping the Complexity Frontier
As these algorithmic paradigms mature, researchers are establishing the fundamental limits of what can be optimized without convexity. For a long time, it was unknown whether finding stationary points in fully nonconvex bilevel problems was even possible in polynomial time without strict structural assumptions.
Providing clarity on this front, Jincheng Cao et al. published the first discrete-time complexity analysis for finding stationary points in simple nonconvex bilevel optimization in On the Complexity of Finding Stationary Points in Nonconvex Simple Bilevel Optimization. By adapting a Dynamic Barrier Gradient Descent (DBGD) framework, the authors proved that first-order algorithms can converge to a joint stationarity point in polynomial time without requiring the lower level to satisfy convexity or the Polyak–Łojasiewicz condition.
By shifting from rigid local assumptions (like LLSC) to global geometric reformulations (like value functions and Moreau envelopes), the machine learning community is successfully decoupling bilevel optimization from its classical constraints, paving the way for robust, scalable hierarchical learning.
Key Foundational Work
A Value-Function-based Interior-point Method for Non-convex Bi-level Optimization (2021) — contributed 2 concept elements to this direction.
Achieving $\mathcal{O}(\epsilon^{-1.5})$ Complexity in Hessian/Jacobian-free Stochastic Bilevel Optimization (2023) — contributed 2 concept elements to this direction.
Achieving O(ε-1.5) Complexity in Hessian/Jacobian-free Stochastic Bilevel Optimization (2023) — contributed 1 concept elements to this direction.