Does Momentum Help in Stochastic Optimization? A Sample Complexity Analysis

Swetha Ganesh, Rohan Deb, Gugan Thoppe, Amarjit BudhirajaUAI 2023 · OpenReview

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.

Table 1: Parameter settings for the unified LSA-M framework, showing how SGD, SHB, and ASG are represented within the same mathematical structure.

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.

Figure 1: MSE comparison for SGD, SHB, and ASG. (a) At equal stepsizes, momentum methods converge faster but to a higher error floor. (b) Increasing the SGD stepsize allows it to match the performance of momentum methods. (c) At high stepsizes, all methods exhibit similar high-variance behavior.

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

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.
BibTeX
@inproceedings{ganesh2023does,
  author = {Swetha Ganesh and Rohan Deb and Gugan Thoppe and Amarjit Budhiraja},
  title = {{Does Momentum Help in Stochastic Optimization? A Sample Complexity Analysis}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2023},
  url = {https://openreview.net/forum?id=apxTSwT8gQ},
}
Figure