Last Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regression
arXiv:2110.06198
Abstract
Stochastic gradient descent (SGD) has been shown to generalize well in many deep learning applications. In practice, one often runs SGD with a geometrically decaying stepsize, i.e., a constant initial stepsize followed by multiple geometric stepsize decay, and uses the last iterate as the output. This kind of SGD is known to be nearly minimax optimal for classical finite-dimensional linear regression problems (Ge et al., 2019). However, a sharp analysis for the last iterate of SGD in the overparameterized setting is still open. In this paper, we provide a problem-dependent analysis on the last iterate risk bounds of SGD with decaying stepsize, for (overparameterized) linear regression problems. In particular, for last iterate SGD with (tail) geometrically decaying stepsize, we prove nearly matching upper and lower bounds on the excess risk. Moreover, we provide an excess risk lower bound for last iterate SGD with polynomially decaying stepsize and demonstrate the advantage of geometrically decaying stepsize in an instance-wise manner, which complements the minimax rate comparison made in prior works.
arXiv comment35 pages, 2 figures, 1 table. In ICML 2022
References in corpus (12)
- Benign Overfitting in Linear Regression
- Optimal Distributed Online Prediction using Mini-Batches
- Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
- Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)
- Parallelizing Stochastic Gradient Descent for Least Squares Regression: mini-batching, averaging, and model misspecification
- Benign overfitting in ridge regression
- The Step Decay Schedule: A Near Optimal, Geometrically Decaying Learning Rate Procedure For Least Squares
- A Markov Chain Theory Approach to Characterizing the Minimax Optimality of Stochastic Gradient Descent (for Least Squares)
- A Generic Acceleration Framework for Stochastic Composite Optimization
- Benign Overfitting of Constant-Stepsize SGD for Linear Regression
- Last iterate convergence of SGD for Least-Squares in the Interpolation regime
- The Benefits of Implicit Regularization from SGD in Least Squares Problems