mlsanityData to 7 Oct 2026

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

arXiv 2604.04090 ↗First posted 5 Apr 2026cs.LG cs.AIcited by 3

Not on the map. Why?

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.

Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 30 of its 43 references that are in the map. First posted on arXiv 5 Apr 2026.

Builds on

30 of 43 references.

References · 30

  1. 2016On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minimacited by 1,337
  2. 2018Learning to Reweight Examples for Robust Deep Learningcited by 670
  3. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
  4. 2019Meta-Learning with Implicit Gradientscited by 523
  5. 2018Bilevel Programming for Hyperparameter Optimization and Meta-Learningcited by 403
  6. 2018Meta-learning with differentiable closed-form solverscited by 395
  7. 2017Train longer, generalize better: closing the generalization gap in large batch training of neural networkscited by 278
  8. 2019Adversarial Attacks on Graph Neural Networks via Meta Learningcited by 261
  9. 2017Forward and Reverse Gradient-Based Hyperparameter Optimizationcited by 232
  10. 2018Approximation Methods for Bilevel Programmingcited by 231
  11. 2020Bilevel Optimization: Convergence Analysis and Enhanced Designcited by 219
  12. 2020A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Criticcited by 141
18 more
  1. 2020Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descentcited by 118
  2. 2019Self-Tuning Networks: Bilevel Optimization of Hyperparameters using Structured Best-Response Functionscited by 104
  3. 2022BOME! Bilevel Optimization Made Easy: A Simple First-Order Approachcited by 103
  4. 2017Data-Dependent Stability of Stochastic Gradient Descentcited by 90
  5. 2020A Generic First-Order Algorithmic Framework for Bi-Level Programming Beyond Lower-Level Singletoncited by 78
  6. 2018Stochastic Hyperparameter Optimization through Hypernetworkscited by 72
  7. 2021A Single-Timescale Method for Stochastic Bilevel Optimizationcited by 69
  8. 2020Convergence of Meta-Learning with Task-Specific Adaptation over Partial Parameterscited by 65
  9. 2016Connecting Generative Adversarial Networks and Actor-Critic Methodscited by 49
  10. 2020Toward Better Generalization Bounds with Locally Elastic Stabilitycited by 41
  11. 2017Algorithmic stability and hypothesis complexitycited by 39
  12. 2021Stability and Generalization of Stochastic Gradient Methods for Minimax Problemscited by 35
  13. 2021Stability and Generalization of Bilevel Programming in Hyperparameter Optimizationcited by 31
  14. 2020Improved Bilevel Model: Fast and Optimal Algorithm with Theoretical Guaranteecited by 27
  15. 2023Probabilistic Bilevel Coreset Selectioncited by 26
  16. 2019Learner-aware Teaching: Inverse Reinforcement Learning with Preferences and Constraintscited by 18
  17. 2018On ℓp-hyperparameter Learning via Bilevel Nonsmooth Optimizationcited by 9
  18. 2019Stability and Optimization Error of Stochastic Gradient Descent for Pairwise Learningcited by 8

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 3.

3 papers.

  1. 2026Meta Additive Model: Interpretable Sparse Learning With Auto Weightingcited by 0
  2. 2026On the Stability and Generalization of First-order Bilevel Minimax Optimizationcited by 0
  3. 2026Quantifying Multimodal Capabilities: Formal Generalization Guarantees in Pairwise Metric Learningcited by 0