Generalization Error Bounds for Optimization Algorithms via Stability
Qi Meng, Yue Wang, Wei Chen et al. · Proceedings of the AAAI Conference on Artificial Intelligence · 2017
Many machine learning tasks can be formulated as Regularized Empirical Risk Minimization (R-ERM), and solved by optimization algorithms such as gradient descent (GD), stochastic gradient descent (SGD), and stochastic variance reduction (SVRG). Conventional analysis on these optimization algorithms focuses on their convergence rates during the training process, however, people in the machine learning community may care more about the generalization performance of the learned model on unseen test data. In this paper, we investigate on this issue, by using stability as a tool. In particular, we decompose the generalization error for R-ERM, and derive its upper bound for both convex and nonconvex cases. In convex cases, we prove that the generalization error can be bounded by the convergence rate of the optimization algorithm and the stability of the R-ERM process, both in expectation (in the order of
Cited by 5 works. doi:10.1609/aaai.v31i1.10919
Authors
References
- Statistical Learning Theory
- Estimation of Dependences Based on Empirical Data.
- Numerical Optimization
- Introductory Lectures on Convex Optimization: A Basic Course
- The Tradeoffs of Large-Scale Learning
- Accelerating Stochastic Gradient Descent using Predictive Variance Reduction
- On the Generalization Ability of On-Line Learning Algorithms
- Communication Efficient Distributed Optimization using an Approximate Newton-type Method
- Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming
- Train faster, generalize better: Stability of stochastic gradient descent