The Step Decay Schedule: A Near Optimal, Geometrically Decaying Learning Rate Procedure For Least Squares

Abstract

Minimax optimal convergence rates for classes of stochastic convex optimization problems are well characterized, where the majority of results utilize iterate averaged stochastic gradient descent (SGD) with polynomially decaying step sizes. In contrast, SGD's final iterate behavior has received much less attention despite their widespread use in practice. Motivated by this observation, this work provides a detailed study of the following question: what rate is achievable using the final iterate of SGD for the streaming least squares regression problem with and without strong convexity? First, this work shows that even if the time horizon T (i.e. the number of iterations SGD is run for) is known in advance, SGD's final iterate behavior with any polynomially decaying learning rate scheme is highly sub-optimal compared to the minimax rate (by a condition number factor in the strongly convex case and a factor of $\sqrt{T}$ in the non-strongly convex case). In contrast, this paper shows that Step Decay schedules, which cut the learning rate by a constant factor every constant number of epochs (i.e., the learning rate decays geometrically) offers significant improvements over any polynomially decaying step sizes. In particular, the final iterate behavior with a step decay schedule is off the minimax rate by only $log$ factors (in the condition number for strongly convex case, and in T for the non-strongly convex case). Finally, in stark contrast to the known horizon case, this paper shows that the anytime (i.e. the limiting) behavior of SGD's final iterate is poor (in that it queries iterates with highly sub-optimal function value infinitely often, i.e. in a limsup sense) irrespective of the stepsizes employed. These results demonstrate the subtlety in establishing optimal learning rate schemes (for the final iterate) for stochastic gradient procedures in fixed time horizon settings.

arXiv commentAppears in the proceedings of the Conference on Neural Information Processing Systems (NeurIPS), 2019. 28 pages, 4 tables, 1 Algorithm, 7 figures

References in corpus (10)

• Adam: A Method for Stochastic Optimization
• 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
• Accelerating Stochastic Gradient Descent For Least Squares Regression
• A Universally Optimal Multistage Accelerated Stochastic Gradient Method
• Iterate averaging as regularization for stochastic gradient descent
• A Generic Acceleration Framework for Stochastic Composite Optimization
• A Markov Chain Theory Approach to Characterizing the Minimax Optimality of Stochastic Gradient Descent (for Least Squares)

Cited by in corpus (8)

• Towards Explaining the Regularization Effect of Initial Large Learning Rate in Training Neural Networks
• Review: Deep Learning in Electron Microscopy
• Closing the Generalization Gap of Adaptive Gradient Methods in Training Deep Neural Networks
• Learning an Adaptive Learning Rate Schedule
• A Selective Review on Statistical Methods for Massive Data Computation: Distributed Computing, Subsampling, and Minibatch Techniques
• From low probability to high confidence in stochastic convex optimization
• Last Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regression
• Primitive Agentic First-Order Optimization