Abstract
In deterministic convex optimization, momentum methods like Polyak’s Heavy Ball (HB) and Nesterov’s Accelerated Gradient (NAG) are known to significantly accelerate convergence. However, their performance in stochastic settings—where gradients are noisy—has been a subject of ongoing debate. This paper provides a rigorous theoretical analysis of sample complexity for quadratic optimization problems under persistent noise. By utilizing a unified framework, the authors demonstrate that momentum methods like Stochastic Heavy Ball (SHB) and Accelerated Stochastic Gradient (ASG) offer no fundamental sample complexity advantage over vanilla Stochastic Gradient Descent (SGD). Both classes of algorithms are shown to share the same optimal sample complexity order, $\Theta(\frac{K}{\epsilon \lambda_{min}^2})$, suggesting that the "free lunch" of momentum does not extend to the stochastic regime with non-vanishing noise.
Introduction
In the realm of deterministic optimization, momentum is a cornerstone for efficiency. It can improve convergence rates from $O(\kappa \log 1/\epsilon)$ to $O(\sqrt{\kappa} \log 1/\epsilon)$, where $\kappa$ represents the condition number of the problem. Naturally, these techniques were adapted for stochastic optimization (SHB and ASG) to handle the noisy gradients typical of machine learning.
Despite their widespread use, the theoretical benefits of momentum in stochastic settings have remained unclear. While some literature suggests a speedup, other studies indicate that momentum might even be detrimental. This paper addresses this ambiguity by asking a fundamental question: Does momentum actually reduce the number of iterations (samples) required to reach an $\epsilon$-optimal solution when noise is persistent?
The LSA-M Framework
To compare these algorithms fairly, the authors introduce a unified framework called Linear Stochastic Approximation with Momentum (LSA-M). This framework uses a generic update rule that can be specialized into SGD, SHB, or ASG by adjusting specific parameters: $\eta$ (momentum coefficient), $\beta$ (a parameter distinguishing HB and NAG types), and $\alpha$ (the step size).
This unified approach allows for a simultaneous analysis of the lower bounds for any LSA-M algorithm and the upper bounds for specific instances like SGD. The analysis assumes "persistent noise," where the variance of the stochastic gradients remains bounded away from zero even near the optimum—a realistic assumption for many modern machine learning tasks.
The Bias-Variance Tradeoff
The core insight of the paper lies in the interplay between bias and variance. In deterministic optimization, momentum effectively reduces the "bias" (the distance from the current iterate to the optimum) at an accelerated rate. However, in the stochastic setting, the algorithm must also contend with "variance" introduced by noisy gradients.
Through new proof techniques that jointly analyze bias and variance, the authors show that while momentum may speed up the reduction of bias, it simultaneously amplifies the variance or fails to reduce it faster than vanilla SGD. Consequently, the "acceleration" effect seen in deterministic settings essentially vanishes. The condition number $\kappa$, which receives a square-root improvement in deterministic momentum, does not see a similar improvement in the stochastic sample complexity.
Key Results and Complexity Bounds
The paper establishes two primary theoretical pillars:
- Lower Bounds (Theorem 2.1): For any choice of parameters within the LSA-M framework, the expected error cannot reach $\epsilon$ until at least $n_0 \approx \frac{K}{\epsilon \lambda_{min}^2}$ iterations have passed.
- Upper Bounds (Theorem 2.2): Vanilla SGD is proven to reach the $\epsilon$-optimal solution within this same order of iterations.
These results imply that for the entire family of quadratic optimization problems with persistent noise, SHB and ASG cannot outperform vanilla SGD in terms of sample complexity. The perceived benefits of momentum in these scenarios are often an artifact of analyzing only the deterministic component of the movement while ignoring the noise floor.
Conclusion and Limitations
This work provides a definitive answer for quadratic problems: momentum does not improve sample complexity in the presence of persistent noise. It also critiques previous "positive" results, noting they often relied on one-sided analyses that ignored variance or contained mathematical errors in asymptotic calculations.
While these findings are significant, they are currently limited to quadratic functions and constant step-size regimes. Future research may explore whether momentum provides advantages in non-convex landscapes, such as escaping saddle points, which are not captured by this sample complexity analysis. For now, the results suggest that in the stochastic world, the lunch is no longer free.
Summary updated