Optimal Rates for Multi-pass Stochastic Gradient Methods

Abstract

We analyze the learning properties of the stochastic gradient method when multiple passes over the data and mini-batches are allowed. We study how regularization properties are controlled by the step-size, the number of passes and the mini-batch size. In particular, we consider the square loss and show that for a universal step-size choice, the number of passes acts as a regularization parameter, and optimal finite sample bounds can be achieved by early-stopping. Moreover, we show that larger step-sizes are allowed when considering mini-batches. Our analysis is based on a unifying approach, encompassing both batch and stochastic gradient methods as special cases. As a byproduct, we derive optimal convergence results for batch gradient methods (even in the non-attainable cases).

Fixed a typo in Eq (66)

Cited by in corpus (22)

• Optimal Rates for Spectral Algorithms with Least-Squares Regression over Hilbert Spaces
• Theory of Deep Learning III: explaining the non-overfitting puzzle
• The Implicit Regularization of Stochastic Gradient Flow for Least Squares
• Representation, learning, and planning algorithms for geometric task and motion planning
• Generalization Error Bounds with Probabilistic Guarantee for SGD in Nonconvex Optimization
• Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent
• When Does Preconditioning Help or Hurt Generalization?
• Graph-Dependent Implicit Regularisation for Distributed Stochastic Subgradient Descent
• Generalization Properties of Doubly Stochastic Learning Algorithms
• Optimal Statistical Rates for Decentralised Non-Parametric Regression with Linear Speed-Up
• An Analysis of Stochastic Variance Reduced Gradient for Linear Inverse Problems
• Kernel Conjugate Gradient Methods with Random Projections
• On the Convergence of Stochastic Gradient Descent for Nonlinear Ill-Posed Problems
• Beating SGD Saturation with Tail-Averaging and Minibatching
• Improved Learning Rates for Stochastic Optimization
• Gradient Descent in RKHS with Importance Labeling
• Optimal Rates for Learning with Nyström Stochastic Gradient Methods
• Stochastic Gradient Descent Meets Distribution Regression
• Stochastic Gradient Descent in Hilbert Scales: Smoothness, Preconditioning and Earlier Stopping
• Optimal Rates of Sketched-regularized Algorithms for Least-Squares Regression over Hilbert Spaces
• Why Does Multi-Epoch Training Help?
• On the Saturation Phenomenon of Stochastic Gradient Descent for Linear Inverse Problems