Many problems in machine learning and operational research are inherently hierarchical. In a leader-follower game (or Stackelberg game), an upper-level agent (the leader) selects a strategy $x$, and a lower-level agent (the follower) responds by choosing a strategy $y$ that optimizes their own objective. This is formulated as a bilevel optimization problem:
$$\min_{x} f(x, y) \quad \text{subject to} \quad y \in \arg\min_{y'} g(x, y')$$
This nested structure is notoriously difficult to solve. To evaluate even a single choice of $x$, an optimizer must solve an entire inner optimization problem to find $y$. Furthermore, computing gradients for $x$ typically requires differentiating through the lower-level optimization process, demanding expensive second-order derivatives (such as Hessian inversions or hypergradients). When the lower-level landscape is non-convex or lacks a unique solution, standard gradient-based methods break down entirely.
To bypass this "nested loop" bottleneck, a prominent research direction focuses on bilevel-to-single-level reductions. By translating the implicit lower-level optimality condition ($y \in \arg\min g(x,y)$) into explicit constraints or penalty terms, researchers can flatten the hierarchy into a single, unified optimization problem. This allows the use of standard, highly efficient single-level solvers and first-order gradient methods.
Replacing Optimization with KKT Conditions
When the lower-level optimization problem is convex and differentiable, its global optimum can be completely characterized by its first-order optimality conditions. The most direct way to flatten a bilevel problem is to replace the lower-level problem with its Karush-Kuhn-Tucker (KKT) conditions or stationarity constraints, appending them directly to the upper-level problem.
Nested Structure:
Minimize f(x, y)
subject to: y solves Min g(x, y)
Flattened Structure:
Minimize f(x, y)
subject to: KKT Stationarity of g(x, y) == 0
Primal & Dual Feasibility
Complementary Slackness
This mathematical bridge was early extended to uncertain environments by Guangquan Zhang et al. in The Definition of Optimal Solution and an Extended Kuhn-Tucker Approach for Fuzzy Linear Bilevel Programming, demonstrating that leader-follower hierarchies could be solved using standard linear programming tools once the follower's response was encoded as a set of constraints.
In modern machine learning, this reduction is widely used to provide exact guarantees or solve adversarial games. For example, Mahalakshmi Sabanayagam et al. in Exact Certification of (Graph) Neural Networks Against Label Poisoning and Shike Mei et al. in Using Machine Teaching to Identify Optimal Training-Set Attacks on Machine Learners substitute the inner training objective of a learner with its KKT conditions, converting data-poisoning and robustness certification tasks into single-level constrained problems.
Linearization via the Big-M Method
While the KKT approach eliminates the nested loop, it introduces complementary slackness constraints (e.g., $\lambda \cdot h(y) = 0$), which are inherently non-linear and non-convex. To solve these efficiently, researchers frequently apply the Big-M method to linearize the complementarity constraints using auxiliary binary variables.
This strategy transforms the problem into a Mixed-Integer Linear Program (MILP) or Mixed-Integer Quadratic Program (MIQP), which can be solved globally by commercial branch-and-bound solvers. The authors of Proactive Demand Response for Data Centers: A Win-Win Solution applied this technique to power utility pricing, while Canqi Yao et al. utilized it in Incentive-aware Electric Vehicle Routing Problem: a Bi-level Model and a Joint Solution Algorithm to optimize fleet routing and customer incentives simultaneously.
The Value Function Reformulation
The KKT approach assumes the lower-level problem is convex. If the inner problem is non-convex, the KKT conditions only identify stationary points, meaning the upper level might optimize against a poor local minimum of the follower.
To overcome this, researchers use the value function reformulation. Let $\varphi(x) = \min_{y'} g(x, y')$ be the optimal value function, which returns the absolute minimum possible lower-level score for a given $x$. The statement "$y$ is an optimal response to $x$" is mathematically equivalent to saying that $y$ is feasible and its objective value matches the absolute minimum:
$$g(x, y) \le \varphi(x)$$
This single inequality constraint completely flattens the bilevel hierarchy without requiring lower-level convexity.
Bilevel Condition:
y ∈ argmin g(x, y')
Value Function Constraint:
g(x, y) ≤ φ(x) [where φ(x) is the optimal lower-level value]
By treating the problem as a standard constrained task, Risheng Liu et al. developed a gradient-based interior-point method in A Value-Function-based Interior-point Method for Non-convex Bi-level Optimization that avoids computing expensive Hessian-vector products. Building on this concept, Bo Liu et al. introduced BOME! Bilevel Optimization Made Easy: A Simple First-Order Approach, a purely first-order algorithm that utilizes value-based constraints to bypass implicit differentiation entirely, making large-scale deep learning applications like hyperparameter optimization and continual learning computationally practical.
Penalty Methods and Minimax Surrogates
Enforcing hard constraints like $g(x,y) \le \varphi(x)$ or KKT stationarity during gradient descent can be challenging because the resulting feasible region is often highly irregular or disconnected. An alternative strategy relaxes these hard constraints into soft penalties within a unified objective function.
Instead of forcing the lower-level optimality gap to be exactly zero, a penalty method minimizes the upper-level objective plus a penalty proportional to the inner gap:
$$\min_{x, y} f(x, y) + \lambda \left( g(x, y) - \varphi(x) \right)$$
As $\lambda$ increases, the optimizer is forced to choose variables where the lower-level gap shrinks to zero.
Akshay Mehra and Jihun Hamm leveraged this in Penalty Method for Inversion-Free Deep Bilevel Optimization, showing that optimizing this penalized single-level objective eliminates the need for Hessian inversions, drastically reducing memory overhead when training deep networks. To provide rigorous theoretical guarantees, Pengyu Chen et al. established explicit convergence rates in Penalty-based Methods for Simple Bilevel Optimization under Hölderian Error Bounds by bounding the distance between approximate solutions of the penalized objective and the true bilevel optimum.
Transitioning to Minimax Frameworks
Rather than managing a dynamic penalty parameter $\lambda$, the problem can be reframed as a structured minimax or saddle-point problem. Sanyou Mei demonstrates in First-order penalty methods for bilevel optimization that approximating hierarchical objectives as unified minimax frameworks allows them to be solved directly using standard saddle-point algorithms. Similarly, Kaiyi Ji et al. show in First-Order Minimax Bilevel Optimization that a Lagrangian-based minimax surrogate can resolve complex three-level optimization problems using only first-order gradient updates.
Duality-Driven Flattening
A final mathematical lever for single-level reduction is optimization duality. By taking the dual of the lower-level problem, the nested minimization can be merged directly with the upper-level constraints or objective function.
For non-smooth lower-level objectives common in machine learning (such as Lasso or Support Vector Machines), He Chen et al. introduced Lower-level Duality Based Reformulation and Majorization Minimization Algorithm for Hyperparameter Optimization. By applying Fenchel’s duality to the inner problem, the authors replaced the nested hierarchy with a single-level problem involving the conjugate functions of the loss and regularizers, completely bypassing implicit differentiation.
In network systems and adversarial settings, combining KKT conditions with strong or weak duality allows researchers to collapse complex min-max-min structures. For instance, the authors of Joint Estimation of OD Demands and Cost Functions in Transportation Networks from Data used weak duality alongside KKT conditions to recover traffic network parameters without nested loops. In adversarial network defense, Lei Zhang 0158 and Chang-Tien Lu showed in Network Interdiction Goes Neural that dualizing the follower's objective yields a unified mathematical structure that can be solved rapidly by graph neural networks.
Summary of Reduction Strategies
| Strategy | Core Mechanism | Primary Benefit | Key Limitation |
|---|---|---|---|
| KKT Reformulation | Replaces inner problem with its first-order stationarity constraints. | Highly compatible with standard mathematical solvers. | Requires the lower-level problem to be convex. |
| Value Function | Constrains the inner objective to be $\le$ the optimal value function $\varphi(x)$. | Handles non-convex lower-level problems globally. | $\varphi(x)$ can be non-smooth and difficult to compute. |
| Penalty Methods | Minimizes the upper objective plus a soft penalty on the inner optimality gap. | Inversion-free; enables pure first-order gradient descent. | Requires careful tuning of the penalty parameter $\lambda$. |
| Duality Flattening | Substitutes the inner problem with its Fenchel or linear programming dual. | Eliminates implicit loops for non-smooth objectives. | Limited to structures with tractable dual representations. |
Key Foundational Work
The Definition of Optimal Solution and an Extended Kuhn-Tucker Approach for Fuzzy Linear Bilevel Programming (2005) — contributed 2 concept elements to this direction.