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

Computer Science > Machine Learning arXiv:2604.04090 (cs) [Submitted on 5 Apr 2026] Title:Fine-grained Analysis of Stability and Generalization for Stochastic Bilevel Optimization Authors:Xuelin Zhang, Hong Chen, Bin Gu, Tieliang Gong, Feng Zheng View a PDF of the paper titled Fine-grained Analysis of Stability and Generalization for Stochastic Bilevel Optimization, by Xuelin Zhang and 3 other authors View PDF HTML (experimental) 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 ...