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.
Abstract (translated)
随机双层优化（SBO）近期已被整合进多种机器学习范式，包括超参数优化、元学习与强化学习。随着应用范围的不断拓展，学界对SBO的计算行为展开了大量研究。然而，从统计学习理论视角审视，SBO方法的泛化保证机制仍远未被充分理解。本文对基于一阶梯度的双层优化方法进行了系统性泛化分析。首先，我们建立了SBO方法平均论证稳定性与泛化间隙之间的定量关联。随后，我们在非凸-非凸（NC-NC）、凸-凸（C-C）及强凸-强凸（SC-SC）三种设定下，分别推导了单时间尺度随机梯度下降（SGD）与双时间尺度SGD的平均论证稳定性上界。实验分析验证了我们的理论发现。相较于既有算法稳定性分析，本研究结果无需在每轮迭代中重新初始化内层参数，且适用于更广泛的目标函数形式。
URL
https://arxiv.org/abs/2604.04090
