Beating SGD Saturation with Tail-Averaging and Minibatching
arXiv:1902.08668
Abstract
While stochastic gradient descent (SGD) is one of the major workhorses in machine learning, the learning properties of many practically used variants are poorly understood. In this paper, we consider least squares learning in a nonparametric setting and contribute to filling this gap by focusing on the effect and interplay of multiple passes, mini-batching and averaging, and in particular tail averaging. Our results show how these different variants of SGD can be combined to achieve optimal learning errors, hence providing practical insights. In particular, we show for the first time in the literature that tail averaging allows faster convergence rates than uniform averaging in the nonparametric setting. Finally, we show that a combination of tail-averaging and minibatching allows more aggressive step-size choices than using any one of said components.
References in corpus (8)
- Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
- Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
- Parallelizing Stochastic Gradient Descent for Least Squares Regression: mini-batching, averaging, and model misspecification
- Optimal Rates for Spectral Algorithms with Least-Squares Regression over Hilbert Spaces
- Optimal Rates for Multi-pass Stochastic Gradient Methods
- Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passes
- Convergence of the Forward-Backward Algorithm: Beyond the Worst Case with the Help of Geometry
- Iterate averaging as regularization for stochastic gradient descent