Abstract
Stochastic Heavy Ball (SHB) and Nesterov’s Accelerated Stochastic Gradient (ASG) are popular momentum methods in optimization. While the benefits of these acceleration ideas in deterministic settings are well understood, their advantages in stochastic optimization are unclear. Several works have recently claimed that SHB and ASG always help in stochastic optimization. Our work shows that i.) these claims are either flawed or one-sided (e.g., consider only the bias term but not the variance), and ii.) when both these terms are accounted for, SHB and ASG do not always help. Specifically, for any quadratic optimization, we obtain a lower bound on the sample complexity of SHB and ASG, accounting for both bias and variance, and show that the vanilla SGD can achieve the same bound.
Introduction
In deterministic optimization, momentum is often viewed as a "magic wand." Methods like Stochastic Heavy Ball (SHB) and Nesterov’s Accelerated Stochastic Gradient (ASG) provide a provable "square-root" speedup, turning a slow crawl into a sprint by reducing iteration complexity from $O(\kappa \log 1/\epsilon)$ to $O(\sqrt{\kappa} \log 1/\epsilon)$, where $\kappa$ is the condition number.
Naturally, practitioners have carried these tools over to the stochastic world, such as training neural networks with noisy gradients. However, a recent study suggests that for a broad class of quadratic problems with persistent noise, the magic of momentum largely disappears. The core finding is that momentum methods do not improve the fundamental sample complexity over vanilla SGD when both bias and variance are properly accounted for.
Methodology: The Unified Framework
The authors analyze a unified framework called Linear Stochastic Approximation with Momentum (LSA-M), which generalizes SGD, SHB, and ASG into a single update rule. By varying parameters such as the momentum coefficient ($\beta$), the stepsize ($\alpha$), and the specific momentum type ($\eta$), the researchers can compare these algorithms on equal footing.
To make the analysis tractable, the authors employ a block diagonalization technique. They transform the complex $2d$-dimensional system into $d$ independent 2-dimensional systems, allowing them to derive rigorous lower bounds on the sample complexity of SHB and ASG and compare them against the upper bounds of vanilla SGD.
Key Insights: The Illusion of Speed
The perceived advantage of momentum in stochastic settings is often an artifact of incomplete comparisons. If one uses the same stepsize for SGD and SHB, SHB will initially appear faster because it reduces bias (the error from the starting point) more aggressively. However, it eventually settles at a significantly higher "noise floor" due to increased variance.
This paper introduces a rescaling argument: if the stepsize of vanilla SGD is increased to match the noise floor of a momentum method, the "slow" SGD becomes just as fast as the "accelerated" method.
In stochastic optimization with persistent noise, the variance limit acts as a leveler. While momentum helps with the initial "sprint" (bias decay), it does not help the algorithm stay "still" (variance) any better than properly tuned SGD.
Key Results
- Matching Complexity: The paper proves that for any quadratic optimization with persistent noise, the sample complexity for SHB and ASG is $\tilde{\Theta}(\frac{K}{\lambda_{min}^2 \epsilon})$.
- SGD is Sufficient: Vanilla SGD achieves this exact same bound.
- No Order Improvement: Unlike the deterministic case where momentum changes the complexity from $O(\kappa)$ to $O(\sqrt{\kappa})$, in the stochastic case with persistent noise, the dependency on the problem's parameters remains the same across all three methods.
Limitations and Future Work
While these results are definitive for quadratic objectives, the authors note several areas for further exploration:
- Non-convex Landscapes: Deep learning often involves highly non-convex landscapes where the quadratic approximation may only hold locally.
- Vanishing Noise: The "no-gain" result applies to persistent noise. In over-parameterized models where noise vanishes at the solution, momentum might still offer a distinct advantage.
- Stepsize Schedules: The study focuses on constant stepsizes; decaying schedules could provide additional nuances in convergence behavior.
In conclusion, if you are struggling with a noisy optimization problem, momentum may not be the solution. Often, the same performance gains can be achieved by simply increasing the stepsize of standard SGD.
Summary updated