Implicit Bilevel Optimization: Differentiating through Bilevel Optimization Programming

Francesco Alesiani

Introduction

Many complex real-world scenarios are best modeled as "Stackelberg Games," where a leader makes a strategic move and a follower responds optimally. In the context of artificial intelligence, this dynamic appears frequently in robust control (a controller vs. environmental disturbances) and adversarial machine learning (a model vs. an attacker). These scenarios are mathematically defined as Bilevel Optimization Problems, where one optimization task is nested inside another.

While single-level optimization layers (such as OptNet) have been successfully integrated into neural networks, bilevel problems present significant hurdles. They are often NP-hard, and calculating the gradient—how the final output changes with respect to the input—is computationally intensive. For combinatorial (discrete) problems, the challenge is even greater because gradients are zero almost everywhere, making standard backpropagation impossible.

The BIGRAD Framework

This paper introduces BIGRAD (Differentiating through Bilevel Optimization Programming), a framework that allows neural networks to include complex bilevel optimization problems as differentiable layers. BIGRAD defines specific protocols for both the forward and backward passes of a neural network:

  1. Forward Pass: The layer utilizes specialized external solvers to find the optimal solution for the nested optimization problem.
  2. Backward Pass (Continuous): For smooth, continuous problems, BIGRAD employs the Implicit Function Theorem. Rather than "unrolling" the solver—a process that is memory-intensive and slow—it derives the gradient analytically. A "push-back" approach (vector-Jacobian product) is used to maintain computational efficiency.
Architecture of the BIGRAD bilevel layer, showing the forward pass through the optimization solver and the backward pass using implicit differentiation.

Handling Combinatorial Complexity

For discrete problems, such as the Traveling Salesman Problem (TSP) or pathfinding with interdiction, the authors propose two strategies to estimate gradients:

  • Differentiation of Black-Box Solvers: This method estimates the gradient by slightly perturbing the input and observing the resulting shift in the solution.
  • Straight-Through Gradient (STG): A simpler surrogate approach that avoids re-solving the problem during the backward pass, significantly reducing training time while maintaining high accuracy.

Experimental Evaluation

The paper evaluates BIGRAD across several distinct domains to test its robustness and generalization capabilities:

  • Optimal Control: A synthetic benchmark for robust stochastic control.
  • Adversarial ML (Discrete): Testing resilience on the CIFAR-10 dataset against attackers who can flip discrete features.
  • Shortest Path with Interdiction: Using Warcraft II tile maps where an "interdictor" attempts to block segments of the shortest path.
  • TSP with Interdiction: A setup where a salesman seeks the shortest route while an opponent removes specific connections.

Key Results and Insights

BIGRAD demonstrates a superior ability to model conflict directly within the network architecture. Unlike standard layers that simply minimize a loss, BIGRAD layers explicitly model an adversary, allowing the network to learn strategies that are inherently robust to interference.

Performance comparison in robust control: BIGRAD (red) achieves lower cost and faster convergence compared to AdvOptNet (blue).

In the Robust Control task, BIGRAD achieved an average cost of 0.2181, significantly outperforming the standard Linear Quadratic Regulator (2.736) and the single-level OptNet (0.2511).

In the Warcraft Shortest Path task, BIGRAD variants achieved 94-97% validation accuracy. Crucially, a standard ResNet18 (Supervised Learning) achieved 99% training accuracy but crashed to 14-26% on validation. This highlights a key finding: standard supervised learning often fails to learn the underlying "logic" of competition, whereas BIGRAD maintains high performance by capturing the interaction between the two levels of optimization.

Limitations and Future Work

While BIGRAD is a significant step forward, it currently treats continuous and discrete variables separately; future work may explore Mixed Integer Programming layers. Additionally, the framework's efficiency is tied to the availability of fast external solvers, and further research is needed to understand how approximate (rather than exact) solutions from these solvers impact gradient quality.

Summary updated

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.
BibTeX
@inproceedings{alesiani2023implicit,
  author = {Francesco Alesiani},
  title = {{Implicit Bilevel Optimization: Differentiating through Bilevel Optimization Programming}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  url = {https://openreview.net/forum?id=AFZcIdhYK0},
}
Figure