Abstract
Bilevel Optimization Programming is used to model complex and conflicting interactions between agents, for example in Robust AI or Privacy-preserving AI. Integrating bilevel mathematical programming within deep learning is thus an essential objective for the Machine Learning community. Previously proposed approaches only consider single-level programming. In this paper, we extend existing single-level optimization programming approaches and thus propose Differentiating through Bilevel Optimization Programming (BiGrad) for end-to-end learning of models that use Bilevel Programming as a layer. BiGrad has wide applicability and can be used in modern machine learning frameworks. BiGrad is applicable to both continuous and combinatorial Bilevel optimization problems. We describe a class of gradient estimators for the combinatorial case which reduces the requirements in terms of computation complexity; for the case of the continuous variable, the gradient computation takes advantage of the push-back approach (i.e. vector-jacobian product) for an efficient implementation. Experiments show that the BiGrad successfully extends existing single-level approaches to Bilevel Programming.
Introduction
In many real-world scenarios, decision-making involves a "leader-follower" dynamic. Whether it is a defender anticipating an attacker’s move in Adversarial AI or a government setting tax rates to which citizens respond in Economics, these interactions are best modeled as Bilevel Optimization Problems (BOPs). In a BOP, an "outer" optimization problem depends directly on the optimal solution of an "inner" optimization problem.
While the machine learning community has successfully integrated single-level optimization (such as linear programming) as differentiable layers within neural networks, bilevel problems remain a significant challenge. They are often NP-hard, and differentiating through the nested optimization process is computationally expensive and mathematically complex. Without a method to backpropagate through these strategic interactions, deep learning models cannot effectively learn to reason about agents that react optimally to their choices.
The BiGrad Framework
This paper introduces BiGrad (Differentiating through Bilevel Optimization Programming), a framework that treats bilevel optimization as an implicit layer. By viewing the solution of the bilevel problem as a fixed point or an equilibrium, BiGrad enables end-to-end training across both continuous and combinatorial domains.
Continuous Bilevel Optimization
For smooth, continuous functions, BiGrad leverages the Implicit Function Theorem (IFT). Rather than differentiating through every iteration of an iterative solver—which is both slow and memory-intensive—BiGrad computes the gradient based on the optimality conditions of the final solution. To ensure scalability, the authors implement a "push-back" approach using Vector-Jacobian Products (VJPs). This reduces memory requirements from $O(n^2)$ to $O(n)$, making it feasible for integration into modern deep learning architectures.
Combinatorial Bilevel Optimization
Discrete problems, such as the Traveling Salesman Problem (TSP) or shortest path calculations, present a different challenge: their gradients are zero almost everywhere. BiGrad addresses this by employing surrogate gradient estimators. By adapting techniques from black-box combinatorial solvers and "Straight-Through" estimators, BiGrad approximates how a change in the input would likely shift the discrete output. This allows the network to learn through non-differentiable logic by estimating the direction of improvement.
Experimental Evaluation
The authors evaluated BiGrad across several challenging benchmarks to test its robustness and strategic awareness.
- Robust Optimal Control: In synthetic stochastic control tasks, BiGrad achieved an average cost of 0.2181, significantly outperforming the state-of-the-art single-level approach, OptNet, which achieved 0.2511. This demonstrates BiGrad's superior ability to capture noise-control interactions.
- Combinatorial Reasoning (Warcraft II): Using tile maps from Warcraft II, the model was tasked with finding the shortest path while an "interdictor" attempted to block segments. BiGrad (using the BB variant) achieved 97.8% validation accuracy, whereas single-level approaches reached ~96.3%. Notably, simple supervised learning models failed to generalize to this strategic task, dropping to ~14% accuracy.
- Adversarial Defense: On the CIFAR-10 dataset, BiGrad was used to implement a bilevel discretization layer. This layer significantly improved the model's resilience against PGD and FGSM adversarial attacks compared to standard convolutional neural networks.
Discussion and Insights
The primary advantage of BiGrad is its strategic awareness. By embedding the inner agent's optimal response directly into the loss landscape, the model "knows" how its environment will react. This leads to more robust solutions than traditional "two-step" approaches that treat the levels independently.
Furthermore, BiGrad provides a unified bridge between classical mathematical programming—which excels at logic and constraints—and deep learning, which excels at perception. By utilizing implicit differentiation, the framework remains efficient, avoiding the need to store the entire history of the optimization solver.
Limitations and Future Work
While BiGrad is a significant step forward, it remains dependent on the efficiency of external solvers for the bilevel problem. If the underlying solver is slow, the training process scales accordingly. Additionally, the continuous case requires second-order derivatives (Hessians), which can be complex to implement for arbitrary functions. Future research will likely explore Mixed-Integer Programming (MIP) layers, where continuous and discrete variables are optimized simultaneously within the same bilevel structure.
Summary updated