First Order Methods for Scalable Bilevel Optimization

This direction is split into other directions: first-order bi-level optimization. Its last version stays readable and citable here.

Version 1 of 1134 papers172 conceptsfrozen 2026-10-04

Bilevel optimization (BLO) is often described as the "Inception" of machine learning: it is an optimization problem nested inside another. In this hierarchy, an "upper-level" leader makes a decision, and a "lower-level" follower responds by optimizing their own objective. This structure is essential for modern AI tasks like hyperparameter tuning, meta-learning, and aligning Large Language Models (LLMs).

However, BLO has historically been plagued by a massive computational bottleneck. To update the leader, one must typically calculate how the follower’s optimal response changes—a process that traditionally requires second-order derivatives (Hessians) or matrix inversions. For models with millions or billions of parameters, these calculations are mathematically elegant but practically impossible.

A new wave of research is moving the field toward fully first-order methods. By bypassing Hessians and relying solely on gradients, researchers are making complex hierarchical learning as scalable as standard neural network training.

The Hessian Bottleneck

The fundamental challenge in BLO is the "hypergradient." To minimize an upper-level objective $F(x, y^*(x))$, where $y^*(x)$ is the optimal solution to a lower-level problem, we need to know how $y^*$ shifts when $x$ changes.

Standard approaches use the Implicit Function Theorem, which involves the inverse of the lower-level Hessian. As Xuxing Chen notes in Decentralized Stochastic Bilevel Optimization with Improved per-Iteration Complexity, even using Hessian-vector products can be computationally demanding for extremely large models. The goal of recent work is to achieve "Hessian-free" optimization, reducing memory and time complexity to match simple first-order gradient descent.

Flattening the Hierarchy

One of the most effective ways to avoid second-order math is to "flatten" the nested structure into a single-level problem.

Minimax Reformulations

Instead of treating the lower level as a black-box optimization, researchers like Xiaoyu Wang and Rui Pan 0002 have shown that many BLO problems can be reformulated into a single minimax objective. In Effective Bilevel Optimization via Minimax Reformulation, they demonstrate that this decoupling allows for an order-of-magnitude speedup. This approach was recently scaled to LLMs with over 30 billion parameters in ScaleBiO, enabling automated data reweighting that was previously computationally prohibitive.

Value Function Methods

Another strategy involves using the "value function"—a map of the lower-level's optimal performance. Risheng Liu and colleagues have pioneered methods like BVFSM and BVFIM, which replace the lower-level optimality condition with a constraint based on this value function. By using penalty methods or interior-point strategies, they transform the bilevel problem into a constrained single-level task that can be solved using only first-order gradients.

Gradient Proxies and Smoothing

When a problem cannot be easily flattened, researchers use clever proxies to estimate the hypergradient without ever touching a Hessian.

Why It Works: Hidden Smoothness and Stability

The intuition behind why these first-order methods succeed—despite throwing away second-order information—lies in the "hidden smoothness" of the bilevel structure. Tianyi Chen and Wotao Yin proved in Closing the Gap that simple alternating stochastic gradient methods can achieve the same optimal sample complexity as standard SGD for non-nested problems.

Furthermore, first-order methods often provide better stability in adversarial or "heavy-tailed" noise environments. Zhuanghua Liu and Luo Luo introduced $N^2SBA$ in Stochastic Bilevel Optimization with Heavy-Tailed Noise, showing that combining penalized surrogate objectives with gradient clipping allows BLO to succeed even when traditional variance assumptions fail—a common scenario in Reinforcement Learning and LLM training.

Real-World Impact

The shift to first-order BLO is moving the technique from theoretical curiosity to a practical tool for high-stakes AI:

  1. Safety in Generative AI: Reza Shirkavand uses first-order BLO to simultaneously prune diffusion models and suppress unwanted concepts (like NSFW content), as detailed in Efficient Fine-Tuning and Concept Suppression for Pruned Diffusion Models.
  2. Reinforcement Learning: Mudit Gaur and Vaneet Aggarwal established the first sample complexity bounds for bilevel RL using Hessian-free algorithms in On the Sample Complexity Bounds of Bilevel Reinforcement Learning.
  3. Data Protection: In Game-Theoretic Unlearnable Example Generator, Shuang Liu uses first-order solvers to create "unlearnable" examples that protect personal data from unauthorized model training.

By treating the lower-level response as a dynamic constraint rather than a static matrix inversion problem, first-order methods have unlocked the ability to optimize hierarchical systems at the scale of modern deep learning.

Papers in this version

Showing 60 of 134 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_first_order_methods_for_scalable_bilevel_6249ba44,
  title = {First Order Methods for Scalable Bilevel Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/first-order-methods-for-scalable-bilevel-optimization/rdr_6249ba4419344733bf98649145f8a204},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_first_order_methods_for_scalable_bilevel_6249ba44_v1,
  title = {First Order Methods for Scalable Bilevel Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/first-order-methods-for-scalable-bilevel-optimization/rdr_6249ba4419344733bf98649145f8a204/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}