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$).
- 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.
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