Fine-grained Analysis of Stability and Generalization for Stochastic Bilevel Optimization
This work addresses the generalization problem for SBO in machine learning applications like hyperparameter optimization, providing theoretical insights that are more general and less restrictive than prior analyses.
The paper tackles the lack of generalization guarantees for stochastic bilevel optimization (SBO) methods by establishing quantitative connections between on-average argument stability and generalization gaps, deriving upper bounds for stability in various settings (NC-NC, C-C, SC-SC) using single- and two-timescale SGD.
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.