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

Rong Ge, Sham M. Kakade, Rahul Kidambi, Praneeth NetrapalliNeurIPS 2019 · OpenReview

The Theory-Practice Gap in SGD

While theoretical machine learning often advocates for "iterate averaging" to achieve optimal convergence, practitioners almost always prefer the final iterate of Stochastic Gradient Descent (SGD). Theoretical results for SGD typically rely on averaging all the points visited during training, combined with polynomially decaying step sizes (e.g., $\eta_t \propto 1/\sqrt{t}$), to reach "minimax optimal" convergence rates.

However, in the real world, engineers usually just take the final iterate (the very last model weights) because it is simpler and often performs better in non-convex settings like deep learning. This paper asks a fundamental question: Can the final iterate of SGD actually be optimal for the classic "streaming least squares" problem? The authors find that with standard polynomial schedules, the answer is a resounding "no." These schedules are either too slow to converge or fail to reduce variance effectively at the end of training.

The Step Decay Solution

To address this, the authors analyze the Step Decay schedule and compare it against standard polynomial decay. The Step Decay algorithm runs for a fixed number of iterations $T$, dividing this time into logarithmic "epochs." In each epoch, the learning rate stays constant, but at the start of the next epoch, it is cut in half (decaying geometrically).

The authors provide rigorous mathematical proofs for both "strongly convex" (well-conditioned) and "non-strongly convex" (smooth) least squares problems, distinguishing between "anytime" algorithms (where the stopping time is unknown) and "fixed horizon" algorithms (where $T$ is known in advance).

Key Insights: Why Polynomial Decay Fails the Final Iterate

  • Polynomial Decay is Sub-optimal: For the final iterate, polynomial schedules are off the optimal rate by a factor of the condition number ($\kappa$) in the strongly convex case, and by a massive factor of $\sqrt{T}$ in the smooth case.
  • The Power of Geometric Decay: Step decay schedules are much more "aggressive." By keeping the learning rate constant for a while and then dropping it sharply, they manage to forget initial errors quickly while still suppressing noise effectively at the end. The paper shows that Step Decay is off the minimax optimal rate by only a logarithmic factor ($\log T$).
Function value error vs. condition number $\kappa$. Step decay avoids the severe penalty incurred by polynomial schedules.
  • The "Anytime" Penalty: One of the most surprising findings is that if you do not know the time horizon $T$ in advance, the final iterate will always be poor at some points in time. To get near-optimality for the final iterate, you must know when the algorithm will terminate.

Experimental Validation: From Least Squares to Deep Learning

The paper validates its theoretical findings using synthetic 2D linear regression (to precisely measure how the condition number $\kappa$ affects error) and CIFAR-10 image classification (training a ResNet-44 to see if linear insights hold for complex, non-convex tasks).

Even though the core theory is built on least squares, the experiments on CIFAR-10 show that exponential/step decay significantly outperforms polynomial decay in both training loss and test error.

Training loss and test error on CIFAR-10, demonstrating the empirical superiority of exponential/step decay over polynomial schedules.

Specifically, a continuous exponential decay achieved a test error of 7.58%, while the standard $1/t$ polynomial schedule lagged behind at 10.20% error. Furthermore, the authors found that "suffix averaging" (averaging only the last few iterates) actually hurt generalization compared to just using the final iterate with a good decay schedule.

Limitations and Future Work

  • Dimension Dependence: In the non-strongly convex (smooth) case, the authors' upper bound for Step Decay includes a dependence on the dimension $d$ that might be improvable.
  • Beyond Least Squares: While the lower bounds are powerful, the upper bounds are specifically proven for least squares. Extending these near-optimal guarantees to broader classes of smooth convex functions remains an open challenge.
  • Hyper-parameter Sensitivity: Schedules tuned for a specific horizon $T$ (e.g., 100 epochs) perform poorly if stopped early (e.g., at 33 epochs). This has significant implications for hyper-parameter optimization methods like Hyperband that rely heavily on early stopping.

Summary updated

Abstract

Minimax optimal convergence rates for numerous 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, the behavior of SGD’s final iterate has received much less attention despite the 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 that SGD is run for) is known in advance, the behavior of SGD’s final iterate with any polynomially decaying learning rate scheme is highly sub-optimal compared to the statistical 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) offer significant improvements over any polynomially decaying step size schedule. In particular, the behavior of the final iterate with step decay schedules is off from the statistical minimax rate by only log factors (in the condition number for the strongly convex case, and in T in 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 step size scheme employed. These results demonstrate the subtlety in establishing optimal learning rate schedules (for the final iterate) for stochastic gradient procedures in fixed time horizon settings.
BibTeX
@inproceedings{ge2019step,
  author = {Rong Ge and Sham M. Kakade and Rahul Kidambi and Praneeth Netrapalli},
  title = {{The Step Decay Schedule: A Near Optimal, Geometrically Decaying Learning Rate Procedure For Least Squares}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=taj75doK-7},
}
Figure