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

Xuelin Zhang; Hong Chen; Bin Gu; Tieliang Gong; Feng Zheng

cs.LGApr 5, 2026

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

Authors: Xuelin Zhang, Hong Chen, Bin Gu, Tieliang Gong, Feng Zheng

Organizations: College of Informatics, Huazhong Agricultural University, Wuhan 430070, China · Engineering Research Center of Intelligent Technology for Agriculture, Ministry of Education, Wuhan 430070, China · School of Artificial Intelligence, Jilin University, Jilin 130012, China · School of Computer Science and Technology, Xi’an Jiaotong University, Xi’an 710049, China ·

Abstract

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.

Figures & tables

Algorithms	Stability	SC-SC	C-C	NC-NC
SSGD	$l_{1}$	$\mathcal{O}\left(\frac{K}{m_{1}}\right)$	$\mathcal{O}\left(\frac{K^{C_{4}}\ln(K)}{m_{1}}\right)$	—
(Theorem 2 )	$l_{2}$	$\mathcal{O}\left(\frac{(m_{1}+K)K}{m_{1}^{2}}\right)$	$\mathcal{O}\left(\frac{(m_{1}+K)K^{2C_{4}-1}\ln^{2}(K)}{m_{1}^{2}}\right)$	—
TSGD	$l_{1}$	$\mathcal{O}\left(\frac{KT^{C_{5}}}{m_{1}}\right)$	$\mathcal{O}\left(\frac{\sqrt{2}^{K}T^{C_{6}}\ln(T)}{m_{1}K}\right)$	$\mathcal{O}\left(\frac{\sqrt{2}^{K}K^{C_{2}T^{1+C_{3}}}T}{m_{1}}\right)$
(Theorem 3 )	$l_{2}$	$\mathcal{O}\left(\frac{(m_{1}+K)KT^{2C_{5}}}{m_{1}^{2}}\right)$	$\mathcal{O}\left(\frac{(m_{1}+K)2^{K}T^{2C_{6}}\ln^{2}(T)}{m_{1}^{2}K^{2}}\right)$	$\mathcal{O}\left(\frac{(m_{1}+K)2^{K}K^{2C_{2}T^{1+C_{3}}}T^{2}}{m_{1}^{2}}\right)$
SSGD	$l_{1}$	$\mathcal{O}\left(\frac{1}{m_{1}}\right)$	$\mathcal{O}\left(\frac{1}{m_{1}}\right)$	$\mathcal{O}\left(\frac{K^{C_{1}}}{m_{1}}\right)$
(Proposition 1)	$l_{2}$	$\mathcal{O}\left(\frac{m_{1}+K}{m_{1}^{2}\sqrt{K}}\right)$	$\mathcal{O}\left(\frac{m_{1}+K}{m_{1}^{2}\sqrt{K}}\right)$	$\mathcal{O}\left(\frac{(m_{1}+K)K^{2C_{1}}}{m_{1}^{2}}\right)$

Table 1: Summary of the generalization bounds under different settings. For briefly,

l_{1}

(

l_{2}

) represents the

l_{1}

(

l_{2}

) on-average argument stability and

C_{1}-C_{6}

are positive constants.

m_{1}

is the number of validation samples;

K

and

T

are the total numbers of outer and inner iterations. Assume that the output model has a small empirical risk

\mathbb{E}\left[R_{D_{m_{1}}}(A(D_{m_{1}},D_{m_{2}}))\right]=\mathcal{O}(m_{1}^{-1})

Panel of Figure 1 — Figure 1: Results of hyperparameter optimization in data reweighting with varying $T$ and $K$

Panel of Figure 2 — Figure 2: Results of hyperparameter optimization in data reweighting with varying $K$ and $m_{1}$

Stochastic Bilevel Optimization

See all 15 papers

On the Stability and Generalization of First-order Bilevel Minimax Optimization
Apr 22, 2026Xuelin Zhang, Peipei YuanMin-Max Optimization Bilevel Optimization
College of Informatics, Huazhong Agricultural University, Wuhan, 430070, China · School of Artificial Intelligence, Jianghan University, Wuhan, 430056, China
A Single-Loop, Constant-Batch First-Order Penalty Method for Stochastic Bilevel Optimization
Oct 5, 2026Xingyu Chen, Ming Yang, Quanqi Hu +1Stochastic Bilevel Optimization Bilevel Optimization
Department of Computer Science and Engineering Texas A&M University, College Station, USA
Generalization Analysis of Biased Stochastic Gradient Methods for Minimax Problems
Oct 14, 2026Shuang Zeng, Yunwen Lei, Yiming YingMin-Max Optimization Generalization Bounds
Department of Mathematics, The University of Hong Kong, Hong Kong, China · School of Mathematics and Statistics, The University of Sydney, Sydney, Australia

Apr 22, 2026J/K move · Enter open · S save

On the Stability and Generalization of First-order Bilevel Minimax Optimization

Xuelin Zhang, Peipei Yuan

College of Informatics, Huazhong Agricultural University, Wuhan, 430070, China · School of Artificial Intelligence, Jianghan University, Wuhan, 430056, China

Min-Max Optimization Bilevel Optimization Stochastic Gradient Descent Generalization Bounds Stochastic Bilevel Optimization Algorithmic Generalization

Open paper AskPDF arXiv

Bilevel optimization and bilevel minimax optimization have recently emerged as unifying frameworks for a range of machine-learning tasks, including hyperparameter optimization and reinforcement learning. The existing literature focuses on empirical efficiency and convergence guarantees, leaving a critical theoretical gap in understanding how well these algorithms generalize. To bridge this gap, we provide the first systematic generalization analysis for first-order gradient-based bilevel minimax solvers with lower-level minimax problems. Specifically, by leveraging algorithmic stability arguments, we derive fine-grained generalization bounds for three representative algorithms, including single-timescale stochastic gradient descent-ascent, and two variants of two-timescale stochastic gradient descent-ascent. Our results reveal a precise trade-off among algorithmic stability, generalization gaps, and practical settings. Furthermore, extensive empirical evaluations corroborate our theoretical insights on realistic optimization tasks with bilevel minimax structures.

Abstract

Stochastic Bilevel Optimization

Explore similar work

On the Stability and Generalization of First-order Bilevel Minimax Optimization

A Single-Loop, Constant-Batch First-Order Penalty Method for Stochastic Bilevel Optimization

Generalization Analysis of Biased Stochastic Gradient Methods for Minimax Problems