# Fine-grained Analysis of Stability and Generalization for Stochastic Bilevel Optimization

arXiv: https://arxiv.org/abs/2604.04090 · HTML: https://mlsanity.com/paper/2604.04090/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 30 of its 43 references that are in the map.
- First posted on arXiv 5 Apr 2026.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 30 of 30)

- [On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima](https://mlsanity.com/paper/1609.04836/) (2016)
- [Learning to Reweight Examples for Robust Deep Learning](https://mlsanity.com/paper/1803.09050/) (2018)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Meta-Learning with Implicit Gradients](https://mlsanity.com/paper/1909.04630/) (2019)
- [Bilevel Programming for Hyperparameter Optimization and Meta-Learning](https://mlsanity.com/paper/1806.04910/) (2018)
- [Meta-learning with differentiable closed-form solvers](https://mlsanity.com/paper/1805.08136/) (2018)
- [Train longer, generalize better: closing the generalization gap in large batch training of neural networks](https://mlsanity.com/paper/1705.08741/) (2017)
- [Adversarial Attacks on Graph Neural Networks via Meta Learning](https://mlsanity.com/paper/1902.08412/) (2019)
- [Approximation Methods for Bilevel Programming](https://mlsanity.com/paper/1802.02246/) (2018)
- [Forward and Reverse Gradient-Based Hyperparameter Optimization](https://mlsanity.com/paper/1703.01785/) (2017)
- [Bilevel Optimization: Convergence Analysis and Enhanced Design](https://mlsanity.com/paper/2010.07962/) (2020)
- [A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic](https://mlsanity.com/paper/2007.05170/) (2020)
- [Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent](https://mlsanity.com/paper/2006.08157/) (2020)
- [Self-Tuning Networks: Bilevel Optimization of Hyperparameters using Structured Best-Response Functions](https://mlsanity.com/paper/1903.03088/) (2019)
- [BOME! Bilevel Optimization Made Easy: A Simple First-Order Approach](https://mlsanity.com/paper/2209.08709/) (2022)
- [Data-Dependent Stability of Stochastic Gradient Descent](https://mlsanity.com/paper/1703.01678/) (2017)
- [A Generic First-Order Algorithmic Framework for Bi-Level Programming Beyond Lower-Level Singleton](https://mlsanity.com/paper/2006.04045/) (2020)
- [Stochastic Hyperparameter Optimization through Hypernetworks](https://mlsanity.com/paper/1802.09419/) (2018)
- [A Single-Timescale Method for Stochastic Bilevel Optimization](https://mlsanity.com/paper/2102.04671/) (2021)
- [Convergence of Meta-Learning with Task-Specific Adaptation over Partial Parameters](https://mlsanity.com/paper/2006.09486/) (2020)
- [Connecting Generative Adversarial Networks and Actor-Critic Methods](https://mlsanity.com/paper/1610.01945/) (2016)
- [Toward Better Generalization Bounds with Locally Elastic Stability](https://mlsanity.com/paper/2010.13988/) (2020)
- [Algorithmic stability and hypothesis complexity](https://mlsanity.com/paper/1702.08712/) (2017)
- [Stability and Generalization of Stochastic Gradient Methods for Minimax Problems](https://mlsanity.com/paper/2105.03793/) (2021)
- [Stability and Generalization of Bilevel Programming in Hyperparameter Optimization](https://mlsanity.com/paper/2106.04188/) (2021)
- [Improved Bilevel Model: Fast and Optimal Algorithm with Theoretical Guarantee](https://mlsanity.com/paper/2009.00690/) (2020)
- [Probabilistic Bilevel Coreset Selection](https://mlsanity.com/paper/2301.09880/) (2023)
- [Learner-aware Teaching: Inverse Reinforcement Learning with Preferences and Constraints](https://mlsanity.com/paper/1906.00429/) (2019)
- [On ℓp-hyperparameter Learning via Bilevel Nonsmooth Optimization](https://mlsanity.com/paper/1806.01520/) (2018)
- [Stability and Optimization Error of Stochastic Gradient Descent for Pairwise Learning](https://mlsanity.com/paper/1904.11316/) (2019)

## Built on by (most cited first, 3 of 3)

- [Meta Additive Model: Interpretable Sparse Learning With Auto Weighting](https://mlsanity.com/paper/2604.20111/) (2026)
- [On the Stability and Generalization of First-order Bilevel Minimax Optimization](https://mlsanity.com/paper/2604.20115/) (2026)
- [Quantifying Multimodal Capabilities: Formal Generalization Guarantees in Pairwise Metric Learning](https://mlsanity.com/paper/2605.01424/) (2026)

## Abstract (arXiv)

Stochastic bilevel optimization (SBO) has been integrated into many machine learning paradigms recently, including hyperparameter optimization, meta learning, and reinforcement learning. Along with the wide range of applications, there have been numerous studies on the computational behavior of SBO. However, the generalization guarantees of SBO methods are far less understood from the lens of statistical learning theory. In this paper, we provide a systematic generalization analysis of the first-order gradient-based bilevel optimization methods. Firstly, we establish the quantitative connections between the on-average argument stability and the generalization gap of SBO methods. Then, we derive the upper bounds of on-average argument stability for single-timescale stochastic gradient descent (SGD) and two-timescale SGD, where three settings (nonconvex-nonconvex (NC-NC), convex-convex (C-C), and strongly-convex-strongly-convex (SC-SC)) are considered respectively. Experimental analysis validates our theoretical findings. Compared with the previous algorithmic stability analysis, our results do not require reinitializing the inner-level parameters at each iteration and are applicable to more general objective functions.