# Stability and Generalization of Bilevel Programming in Hyperparameter Optimization

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

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 54 references that are in the map.
- First posted on arXiv 8 Jun 2021.

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

- [Gaussian Error Linear Units (GELUs)](https://mlsanity.com/paper/1606.08415/) (2016)
- [DARTS: Differentiable Architecture Search](https://mlsanity.com/paper/1806.09055/) (2018)
- [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)
- [Bilevel Programming for Hyperparameter Optimization and Meta-Learning](https://mlsanity.com/paper/1806.04910/) (2018)
- [Gradient-based Hyperparameter Optimization through Reversible Learning](https://mlsanity.com/paper/1502.03492/) (2015)
- [Optimizing Millions of Hyperparameters by Implicit Differentiation](https://mlsanity.com/paper/1911.02590/) (2019)
- [Residual Flows for Invertible Generative Modeling](https://mlsanity.com/paper/1906.02735/) (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)
- [Hyperparameter optimization with approximate gradient](https://mlsanity.com/paper/1602.02355/) (2016)
- [Bilevel Optimization: Convergence Analysis and Enhanced Design](https://mlsanity.com/paper/2010.07962/) (2020)
- [Truncated Back-propagation for Bilevel Optimization](https://mlsanity.com/paper/1810.10667/) (2018)
- [On the Iteration Complexity of Hypergradient Computation](https://mlsanity.com/paper/2006.16218/) (2020)
- [Self-Tuning Networks: Bilevel Optimization of Hyperparameters using Structured Best-Response Functions](https://mlsanity.com/paper/1903.03088/) (2019)
- [Stochastic Hyperparameter Optimization through Hypernetworks](https://mlsanity.com/paper/1802.09419/) (2018)
- [Scalable Gradient-Based Tuning of Continuous Regularization Hyperparameters](https://mlsanity.com/paper/1511.06727/) (2015)
- [Understanding Short-Horizon Bias in Stochastic Meta-Optimization](https://mlsanity.com/paper/1803.02021/) (2018)
- [Tuning Hyperparameters without Grad Students: Scalable and Robust Bayesian Optimisation with Dragonfly](https://mlsanity.com/paper/1903.06694/) (2019)
- [Convergence of Meta-Learning with Task-Specific Adaptation over Partial Parameters](https://mlsanity.com/paper/2006.09486/) (2020)
- [Lower Bounds and Accelerated Algorithms for Bilevel Optimization](https://mlsanity.com/paper/2102.03926/) (2021)
- [On Polynomial Approximations for Privacy-Preserving and Verifiable ReLU Networks](https://mlsanity.com/paper/2011.05530/) (2020)
- [DrMAD: Distilling Reverse-Mode Automatic Differentiation for Optimizing Hyperparameters of Deep Neural Networks](https://mlsanity.com/paper/1601.00917/) (2016)

## Built on by (most cited first, 30 of 31)

- [A Fully First-Order Method for Stochastic Bilevel Optimization](https://mlsanity.com/paper/2301.10945/) (2023)
- [On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximation](https://mlsanity.com/paper/2309.01753/) (2023)
- [PR-Attack: Coordinated Prompt-RAG Attacks on Retrieval-Augmented Generation in Large Language Models via Bilevel Optimization](https://mlsanity.com/paper/2504.07717/) (2025)
- [AutoLoRA: Automatically Tuning Matrix Ranks in Low-Rank Adaptation Based on Meta Learning](https://mlsanity.com/paper/2403.09113/) (2024)
- [Stability and Generalization of Stochastic Optimization with Nonconvex and Nonsmooth Problems](https://mlsanity.com/paper/2206.07082/) (2022)
- [Stability and Generalization Analysis of Gradient Methods for Shallow Neural Networks](https://mlsanity.com/paper/2209.09298/) (2022)
- [Bi-level Physics-Informed Neural Networks for PDE Constrained Optimization using Broyden's Hypergradients](https://mlsanity.com/paper/2209.07075/) (2022)
- [Flexora: Flexible Low Rank Adaptation for Large Language Models](https://mlsanity.com/paper/2408.10774/) (2024)
- [On the Complexity of First-Order Methods in Stochastic Bilevel Optimization](https://mlsanity.com/paper/2402.07101/) (2024)
- [Non-Convex Bilevel Optimization with Time-Varying Objective Functions](https://mlsanity.com/paper/2308.03811/) (2023)
- [A First-Order Multi-Gradient Algorithm for Multi-Objective Bi-Level Optimization](https://mlsanity.com/paper/2401.09257/) (2024)
- [BiDoRA: Bi-level Optimization-Based Weight-Decomposed Low-Rank Adaptation](https://mlsanity.com/paper/2410.09758/) (2024)
- [On the Condition Number Dependency in Bilevel Optimization](https://mlsanity.com/paper/2511.22331/) (2025)
- [A Fully First-Order Layer for Differentiable Optimization](https://mlsanity.com/paper/2512.02494/) (2025)
- [Fine-grained Analysis of Stability and Generalization for Stochastic Bilevel Optimization](https://mlsanity.com/paper/2604.04090/) (2026)
- [Learning Theory for Kernel Bilevel Optimization](https://mlsanity.com/paper/2502.08457/) (2025)
- [Few-Shot Learning in Video and 3D Object Detection: A Survey](https://mlsanity.com/paper/2507.17079/) (2025)
- [On the Difficulty of Learning a Meta-network for Training Data Selection](https://mlsanity.com/paper/2606.00571/) (2026)
- [On Stability and Generalization of Bilevel Optimization Problem](https://mlsanity.com/paper/2210.01063/) (2022)
- [Exploring the Generalization Capabilities of AID-based Bi-level Optimization](https://mlsanity.com/paper/2411.16081/) (2024)
- [Faster Gradient Methods for Highly-Smooth Stochastic Bilevel Optimization](https://mlsanity.com/paper/2509.02937/) (2025)
- [Stochastic variance reduced extragradient methods for solving hierarchical variational inequalities](https://mlsanity.com/paper/2602.13510/) (2026)
- [A Globally Convergent Gradient-based Bilevel Hyperparameter Optimization Method](https://mlsanity.com/paper/2208.12118/) (2022)
- [Decentralized and Privacy-Preserving Learning of Approximate Stackelberg Solutions in Energy Trading Games with Demand Response Aggregators](https://mlsanity.com/paper/2304.02086/) (2023)
- [Downstream Task Guided Masking Learning in Masked Autoencoders Using Multi-Level Optimization](https://mlsanity.com/paper/2402.18128/) (2024)
- [Riemannian Bilevel Optimization](https://mlsanity.com/paper/2405.15816/) (2024)
- [On the Convergence of Single-Loop Stochastic Bilevel Optimization with Approximate Implicit Differentiation](https://mlsanity.com/paper/2602.23633/) (2026)
- [Variational Rectification Inference for Learning with Noisy Labels](https://mlsanity.com/paper/2603.17255/) (2026)
- [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)

## Abstract (arXiv)

The (gradient-based) bilevel programming framework is widely used in hyperparameter optimization and has achieved excellent performance empirically. Previous theoretical work mainly focuses on its optimization properties, while leaving the analysis on generalization largely open. This paper attempts to address the issue by presenting an expectation bound w.r.t. the validation set based on uniform stability. Our results can explain some mysterious behaviours of the bilevel programming in practice, for instance, overfitting to the validation set. We also present an expectation bound for the classical cross-validation algorithm. Our results suggest that gradient-based algorithms can be better than cross-validation under certain conditions in a theoretical perspective. Furthermore, we prove that regularization terms in both the outer and inner levels can relieve the overfitting problem in gradient-based algorithms. In experiments on feature learning and data reweighting for noisy labels, we corroborate our theoretical findings.