Non-Convex Bilevel Games with Critical Point Selection Maps

Michael Arbel, Julien Mairal

TL;DR

Bilevel optimization—where one model's training depends on the output of another—is notoriously difficult when the "inner" problem is non-convex and has multiple solutions. This paper introduces Bilevel Games with Selection (BGS), a framework that uses "selection maps" to resolve this ambiguity, and provides a novel mathematical way to calculate gradients even when the optimization landscape is "flat" or degenerate.

What Problem Does This Paper Address?

Bilevel optimization is the backbone of modern machine learning tasks like hyperparameter tuning, meta-learning, and neural architecture search. It involves a "Leader" (upper-level) and a "Follower" (lower-level). The Leader wants to optimize a goal (like validation accuracy) that depends on the Follower’s optimal response (like trained model weights).

The standard mathematical assumption is that the Follower has one unique, perfect response. However, in deep learning, the Follower’s landscape is often non-convex and "degenerate," meaning there are many equally good solutions or "flat" regions where the gradient is zero. This creates two problems:

  1. Ambiguity: If there are many solutions, which one should the Leader expect?
  2. Mathematical Breakdown: The standard tool for calculating gradients in these problems—the Implicit Function Theorem—requires the landscape to be "curved" (non-degenerate). When the landscape is flat, the math literally divides by zero.

Methods

The authors propose a new framework called Bilevel Games with Selection (BGS).

Selection Map and Bilevel Game
  • Selection Maps: Instead of assuming a unique solution, they define a "selection map" $\phi(x, y)$. This map essentially says: "Given where the Follower started ($y$), and the Leader's current parameters ($x$), this is the specific solution the Follower will settle on." They show that if the Follower uses a standard process like gradient descent, this selection map is well-defined.
  • Morse-Bott Theory: To handle the "flat" regions where standard math fails, the authors turn to Morse-Bott theory—a branch of differential topology. They prove that as long as the Follower's objective function follows certain geometric properties (common in ML), the selection map remains differentiable.
  • Degenerate Implicit Differentiation: They derive a new formula for calculating gradients that uses the Moore-Penrose pseudo-inverse of the Hessian matrix. This allows them to "skip over" the flat directions and only calculate gradients where the information is meaningful.
  • Algorithmic Correction: Most people solve these problems by "unrolling" the Follower's optimization for a few steps. The authors show this creates a systematic bias. They introduce a "simple correction" term that can be added to existing algorithms to recover the true equilibrium without needing infinite computational power.
BGS-Opt Algorithm

Key Insights and Ideas

  • Selection as a Process: The "aha moment" is realizing that the ambiguity of multiple solutions is naturally resolved by the path the optimizer takes. By modeling the solution as a result of a gradient flow, the problem becomes well-defined again.
  • Warm-Starting Matters: The paper highlights that "warm-starting" (starting the next round of Follower training from the previous round's result) isn't just a trick for speed—it's a fundamental part of defining which solution the model selects.
  • Implicit Differentiation is Resilient: A major takeaway is that implicit differentiation—previously thought to be unusable in non-convex, degenerate settings—can be salvaged with the right mathematical tools (Morse-Bott theory and pseudo-inverses).

Key Results

  • Theorem 2 (Degenerate Implicit Differentiation): The authors successfully extend the implicit differentiation formula to cases where the Follower's Hessian is non-invertible.
  • Bias Identification: They prove that Iterative Differentiation (ITD), a popular method that "unrolls" the optimizer, only finds an approximate equilibrium.
  • The "Simple Correction": They demonstrate that by adding an implicit gradient correction (Algorithm 1), they can find the exact equilibrium of the Bilevel Game with Selection, effectively bridging the gap between two major families of algorithms (ITD and AID).

Limitations and Future Work

  • Smoothness Requirements: The theory currently requires the Follower's objective function to be three times continuously differentiable ($C^3$), which might not hold for models using non-smooth components like ReLU activations without modification.
  • Local vs. Global: The selection map is proven to be differentiable near local minima, but the behavior near complex saddle points or during global transitions in the landscape remains a challenge.
  • Stochasticity: The current work focuses on deterministic gradient flows. A natural next step is extending these "selection maps" to stochastic gradient descent (SGD), which is the standard in large-scale machine learning.

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