Stability and Generalization of Bilevel Programming in Hyperparameter Optimization
arXiv:2106.04188
Abstract
The (gradient-based) bilevel programming framework is widely used in hyperparameter optimization and has achieved excellent performance empirically. Previous theoretical work mainly focuses on its optimization properties, while leaving the analysis on generalization largely open. This paper attempts to address the issue by presenting an expectation bound w.r.t. the validation set based on uniform stability. Our results can explain some mysterious behaviours of the bilevel programming in practice, for instance, overfitting to the validation set. We also present an expectation bound for the classical cross-validation algorithm. Our results suggest that gradient-based algorithms can be better than cross-validation under certain conditions in a theoretical perspective. Furthermore, we prove that regularization terms in both the outer and inner levels can relieve the overfitting problem in gradient-based algorithms. In experiments on feature learning and data reweighting for noisy labels, we corroborate our theoretical findings.
References in corpus (13)
- Practical Bayesian Optimization of Machine Learning Algorithms
- Gaussian Error Linear Units (GELUs)
- Residual Flows for Invertible Generative Modeling
- Scalable Gradient-Based Tuning of Continuous Regularization Hyperparameters
- Stochastic Hyperparameter Optimization through Hypernetworks
- Approximation Methods for Bilevel Programming
- Tuning Hyperparameters without Grad Students: Scalable and Robust Bayesian Optimisation with Dragonfly
- Understanding Short-Horizon Bias in Stochastic Meta-Optimization
- Bilevel Optimization: Convergence Analysis and Enhanced Design
- Convergence of Meta-Learning with Task-Specific Adaptation over Partial Parameters
- On Polynomial Approximations for Privacy-Preserving and Verifiable ReLU Networks
- Lower Bounds and Accelerated Algorithms for Bilevel Optimization
- DrMAD: Distilling Reverse-Mode Automatic Differentiation for Optimizing Hyperparameters of Deep Neural Networks