@inproceedings{
wang2024lower,
title={Lower Bounds of Uniform Stability in Gradient-Based Bilevel Algorithms for Hyperparameter Optimization},
author={Rongzhen Wang and Chenyu Zheng and Guoqiang Wu and Xu Min and Xiaolu Zhang and JUN ZHOU and Chongxuan Li},
booktitle={The Thirty-eighth Annual Conference on Neural Information Processing Systems},
year={2024},
url={https://openreview.net/forum?id=u3mZzd0Pdx}
}
Gradient-based bilevel programming leverages unrolling differentiation (UD) or implicit function theorem (IFT) to solve hyperparameter optimization (HO) problems, and is proven effective and scalable in practice. 
To understand their generalization behavior, existing works establish upper bounds on the uniform stability of these algorithms, while their tightness is still unclear. 
To this end, this paper attempts to establish stability lower bounds for UD-based and IFT-based algorithms. 
A central technical challenge arises from the dependency of each outer-level update on the concurrent stage of inner optimization in bilevel programming. 
To address this problem, we introduce lower-bounded expansion properties to characterize the instability in update rules which can serve as general tools for lower-bound analysis. 
These properties guarantee the hyperparameter divergence at the outer level and the Lipschitz constant of inner output at the inner level in the context of HO.
Guided by these insights, we construct a quadratic example that yields tight lower bounds for the UD-based algorithm and meaningful bounds for a representative IFT-based algorithm.
Our tight result indicates that uniform stability has reached its limit in stability analysis for the UD-based algorithm.
Lower Bounds of Uniform Stability in Gradient-Based Bilevel Algorithms for Hyperparameter Optimization
Rongzhen Wang Chenyu Zheng Guoqiang Wu Xu Min Xiaolu Zhang JUN ZHOU Chongxuan Li