Non-Convex Bilevel Games with Critical Point Selection Maps

Michael Arbel, Julien Mairal

Abstract

Bilevel optimization problems involve two nested objectives, where an upper-level objective depends on a solution to a lower-level problem. When the latter is non-convex, multiple critical points may be present, leading to an ambiguous definition of the problem. In this paper, we introduce a key ingredient for resolving this ambiguity through the concept of a selection map which allows one to choose a particular solution to the lower-level problem. Using such maps, we define a class of hierarchical games between two agents that resolve the ambiguity in bilevel problems. This new class of games requires introducing new analytical tools in Morse theory to extend implicit differentiation, a technique used in bilevel optimization resulting from the implicit function theorem. In particular, we establish the validity of such a method even when the latter theorem is inapplicable due to degenerate critical points. Finally, we show that algorithms for solving bilevel problems based on unrolled optimization solve these games up to approximation errors due to finite computational power. A simple correction to these algorithms is then proposed for removing these errors.

Introduction

Bilevel optimization is structured as a "leader-follower" game where an upper-level agent (the leader) optimizes an objective $f(x, y)$ that depends on the optimal response $y$ of a lower-level agent (the follower) minimizing $g(x, y)$. This framework is foundational for hyperparameter tuning, meta-learning, and dataset distillation.

Standard approaches typically assume the follower has a unique optimal response, often requiring strong convexity of the lower-level objective. However, in deep learning, loss landscapes are notoriously non-convex with numerous symmetries and flat regions, leading to multiple equally valid solutions. This creates an ambiguity: which solution should the leader anticipate? Traditional "optimistic" or "pessimistic" frameworks assume the follower either assists or hinders the leader, which is often unrealistic. Furthermore, standard tools like the Implicit Function Theorem (IFT) fail when these solutions are "degenerate" (i.e., the Hessian is singular).

Bilevel Games with Selection (BGS)

To resolve this ambiguity, we introduce Selection Maps ($\phi$). Instead of assuming a unique solution, a selection map picks a specific critical point of the lower-level objective based on the current state of the game. This transforms an ill-defined optimization problem into a well-defined Bilevel Game with Selection (BGS).

Bilevel Game with Selection and its corresponding selection map.

Handling Degeneracy with Morse-Bott Theory

A significant challenge arises when the lower-level objective has "flat" regions where the Hessian is singular. We employ Parametric Morse-Bott Theory to prove that if the objective satisfies certain geometric properties, the selection map remains differentiable even at these degenerate points. This allows the extension of implicit differentiation using pseudo-inverses, providing a robust gradient estimate where the standard IFT would fail. In practice, common techniques like "warm-starting" the follower from the previous iteration's solution can be viewed as physical realizations of these selection maps.

Algorithmic Correction for Unrolled Optimization

Popular "unrolled optimization" algorithms approximate the follower's response by taking $T$ gradient steps. We demonstrate that these methods are essentially trying to solve BGS problems but suffer from a systematic bias due to finite computation. To address this, we introduce an Implicit Gradient Correction term based on our new implicit differentiation formula. This correction removes the bias without requiring an infinite number of unrolling steps.

The BGS-Opt algorithm incorporating the gradient correction term.

Experimental Evaluation

We evaluated the proposed correction on two distinct tasks:

  1. Synthetic Quadratic Problem: A toy problem where the lower-level objective has a manifold of solutions. Standard unrolled optimization (Iterative Target Differentiation - ITD) failed to converge to the true equilibrium without a massive number of steps ($T=1000$). With our correction, convergence was achieved in just $T=10$ steps.
  2. Dataset Distillation on CIFAR-10: The goal was to learn a synthetic dataset of 100 images to train a ResNet-18. Adding the correction term significantly improved performance, reaching 54.19% test accuracy compared to 48.6% for the standard unrolled version, proving that accurate gradient estimates lead to superior synthetic data.

Conclusion

This work provides a rigorous framework for non-convex bilevel optimization by introducing selection maps and leveraging Morse-Bott theory. The proposed algorithmic correction offers a practical way to improve gradient accuracy in deep learning tasks. Future work includes reducing the computational overhead of the Hessian-based correction and extending the theory to non-smooth objectives or stochastic settings.

Summary updated

Abstract

Bilevel optimization problems involve two nested objectives, where an upper-level objective depends on a solution to a lower-level problem. When the latter is non-convex, multiple critical points may be present, leading to an ambiguous definition of the problem. In this paper, we introduce a key ingredient for resolving this ambiguity through the concept of a selection map which allows one to choose a particular solution to the lower-level problem. Using such maps, we define a class of hierarchical games between two agents that resolve the ambiguity in bilevel problems. This new class of games requires introducing new analytical tools in Morse theory to extend implicit differentiation, a technique used in bilevel optimization resulting from the implicit function theorem. In particular, we establish the validity of such a method even when the latter theorem is inapplicable due to degenerate critical points. Finally, we show that algorithms for solving bilevel problems based on unrolled optimization solve these games up to approximation errors due to finite computational power. A simple correction to these algorithms is then proposed for removing these errors.
BibTeX
@inproceedings{arbel2022non,
  author = {Michael Arbel and Julien Mairal},
  title = {{Non-Convex Bilevel Games with Critical Point Selection Maps}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=7UaaOffSRC},
}
Figure