Bilevel optimization models a hierarchical leader-follower game. An upper-level agent minimizes an objective $F(\lambda, w)$, but their choice of $\lambda$ influences a lower-level agent, who responds by optimizing their own objective:
$$\min_{\lambda} F(\lambda, w^*(\lambda)) \quad \text{subject to} \quad w^*(\lambda) \in \arg\min_w f(\lambda, w)$$
For decades, the standard mathematical convenience has been the Lower-Level Singleton (LLS) assumption: the belief that for any given upper-level parameter $\lambda$, the lower-level problem yields a single, unique optimal solution $w^*(\lambda)$.
When this assumption holds, $w^*(\lambda)$ behaves as a well-defined function. This allows algorithms to compute hypergradients $\frac{dF}{d\lambda}$ using the chain rule and implicit differentiation. By differentiating the lower-level optimality condition $\nabla_w f(\lambda, w^*) = 0$, we can compute how the follower's response shifts relative to the leader's actions.
In modern machine learning, however, this assumption routinely fails.
Why the Singleton Assumption Fails
In applications like hyperparameter tuning, meta-learning, and neural architecture search, the lower-level problem often involves training an overparameterized neural network. As Vicol et al. observe, overparameterization introduces severe underspecification. Instead of a single isolated minimum, the lower-level loss landscape contains flat valleys and infinitely many equivalent global minima.
This non-uniqueness breaks standard bilevel optimization in two fundamental ways:
- Geometric Ambiguity: If the lower level has multiple optimal solutions, the upper-level objective becomes ill-defined. Which optimal response $w^*$ will the follower choose? If the follower selects a solution that minimizes $f$ but maximizes $F$, the leader's performance degrades.
- Mathematical Breakdown: Implicit differentiation requires inverting the lower-level Hessian matrix $\nabla_{ww}^2 f(\lambda, w)$. Along a flat valley or a solution manifold, this Hessian becomes singular (non-invertible). As a result, hypergradients become ill-defined or numerically explosive.
As Liu et al. demonstrate, ignoring this issue and blindly applying standard first-order methods causes algorithms to converge to solutions that are highly suboptimal for the upper-level task. Without an explicit mechanism to navigate the lower-level solution space, the optimizer cannot guarantee it will find the specific lower-level optimum that also satisfies the leader.
Standard BLO (LLS Assumed):
λ ───> Unique w*(λ) ───> Well-defined Hypergradient ───> Stable Convergence
Non-Unique BLO:
λ ───> Set of {w*_1, w*_2, ...} ───> Singular Hessian ───> Algorithmic Failure
Mechanism 1: Value-Function and Penalty Reformulations
To bypass the singleton assumption, recent frameworks stop treating the lower level as an implicit function. Instead, they reformulate the nested structure into a single-level constrained optimization problem.
One prominent strategy is the Value-Function Approach. Let $f^*(\lambda) = \min_w f(\lambda, w)$ represent the optimal objective value of the lower level. We can rewrite the bilevel problem by replacing the argmin operator with a single inequality constraint:
$$\min_{\lambda, w} F(\lambda, w) \quad \text{subject to} \quad f(\lambda, w) \le f^*(\lambda)$$
Liu et al. leverage this formulation in their Bi-level Value-Function-based Interior-point Method (BVFIM). By applying a log-barrier penalty to the value-function constraint, they eliminate the need for unique lower-level solutions. This approach allows the algorithm to optimize both levels simultaneously while completely avoiding expensive and fragile Hessian-vector products.
Alternatively, the nested relationship can be enforced via a Penalty Method. Mehra et al. construct an unconstrained single-level objective by penalizing the gap between the follower's current loss and their optimal loss:
$$\min_{\lambda, w} F(\lambda, w) + \mu \left( f(\lambda, w) - f^*(\lambda) \right)$$
As the penalty parameter $\mu$ scales, this formulation naturally drives the optimization toward the optimistic bilevel solution—the specific parameter configuration within the lower-level optimal set that yields the lowest possible upper-level cost.
Mechanism 2: Smoothing and Stationarity Tracking
When the lower-level problem is non-convex, the optimal value function $f^*(\lambda)$ can be non-differentiable, introducing new optimization hurdles. To resolve this, researchers use regularization to smooth the underlying landscape.
Zhu Liu addresses this by applying a Moreau envelope to the lower-level objective. The Moreau envelope acts as a proximal smoothing operator, transforming a rugged, non-unique loss landscape into a continuously differentiable approximation. This allows single-loop, Hessian-free algorithms to achieve rigorous convergence guarantees without requiring lower-level uniqueness or convexity.
Another perspective shifts the target from global optimality to local equilibrium. Instead of searching for absolute minima, algorithms can track lower-level stationarity conditions directly. Nitay Suissa demonstrates that an augmented Lagrangian framework targeting smooth equilibrium constraints can successfully navigate non-unique solution spaces. By optimizing for stationarity rather than tracking a specific point, the algorithm moves fluidly across multiple valid follower responses without stalling or failing to converge.
Key Foundational Work
Linear programming analysis of loopy belief propagation for weighted matching (2007) — contributed 1 concept elements to this direction.
Uniqueness of the SVM Solution (1999) — contributed 1 concept elements to this direction.