When and Why Momentum Accelerates SGD: An Empirical Study

Jingwen Fu, Bohan Wang, Huishuai Zhang, Zhizheng Zhang, Zhi-Ming Ma, Wei Chen, Nanning ZhengSubmission to ICLR 2024 · Withdrawn

TL;DR

By introducing an "effective learning rate" that controls for update magnitude, this paper reveals that momentum only accelerates SGD once the effective learning rate surpasses a specific threshold. The authors explain why through the lens of the Edge of Stability (EoS): gradient descent slows down when its directional sharpness abruptly jumps, and momentum accelerates training precisely by delaying or preventing this transition.

What Problem Does This Paper Address?

Despite momentum being a core component of modern optimizers like SGDM and Adam, the literature offers contradictory explanations for when and why it helps. Traditional theories argue that momentum either:

  1. Dampens stochastic gradient noise (which fails to explain why momentum accelerates full-batch Gradient Descent, where noise is zero), or
  2. Mitigates high-curvature directions (which fails to explain why momentum's advantage varies with the learning rate under the same batch size).

Without a unified framework, comparing SGD and SGD with Momentum (SGDM) is apples-to-oranges, because adding momentum naturally scales up the effective step size.

Methods

  • Effective Learning Rate ($\eta_{ef}$): To isolate the true mechanism of momentum from trivial step-size amplification, the authors define: $$\eta_{ef}^k = \frac{1}{1 - \mu} \cdot \frac{k}{b} \cdot \eta$$ where $\mu$ is the momentum coefficient, $b$ is the mini-batch size, $k$ is a reference batch size, and $\eta$ is the base learning rate. This accounts for both the first-order momentum accumulation factor $\frac{1}{1-\mu}$ and the Linear Scaling Rule $\frac{k}{b}$.

  • Tracking Landscape Dynamics: The authors monitor the largest eigenvalue of the Hessian ($\lambda_{\max}$, sharpness) as well as the directional Hessian along the optimizer's update step: $$H(w_t, w_{t+1}-w_t) = \frac{(w_{t+1}-w_t)^\top \nabla^2 f(w_t) (w_{t+1}-w_t)}{\|w_{t+1}-w_t\|^2}$$

  • Theoretical Analysis via Quadratic Approximation: Analyzing the eigenspace alignment of gradient iterates under GD and GDM to quantify when the trajectory destabilizes.

Datasets

The authors evaluate their framework on standard deep learning benchmarks across computer vision and natural language processing:

  • Vision: CIFAR-10 (full set and a 5,000-sample subset), CIFAR-100, and ImageNet.
  • NLP: WikiText-2.
  • Architectures Tested: Fully-connected network with tanh activations (fc-tanh), VGG13, VGG13-BN, ResNet-18, Vision Transformer (ViT), and standard Transformer.

No new datasets were introduced.

Key Insights and Ideas

  • The Align-and-Deviate Pattern: When compared under the same effective learning rate, SGD and SGDM follow nearly identical loss trajectories at small $\eta_{ef}$. Acceleration only appears after $\eta_{ef}$ crosses a critical threshold—beyond this deviation point, SGDM consistently outperforms SGD.
  • Abrupt Sharpening as the Culprit for Slowdown: In standard GD/SGD, the directional Hessian stays near 0 during early iterations before abruptly jumping to $\approx \frac{2}{\eta}$, triggering loss oscillations and slowing convergence. The paper proves that this sudden jump is a natural consequence of the iterates aligning exponentially fast with the Hessian's top eigenspace once $\lambda_{\max} > \frac{2}{\eta_{ef}} - \lambda_{\min}$.
  • Momentum Defers the Edge of Stability: For GDM, abrupt sharpening only occurs when: $$\lambda_{\max} > \frac{2(1+\mu)}{(1-\mu)\eta_{ef}} - \lambda_{\min}$$ When $\mu = 0.9$, the stability threshold is roughly 19 times higher than standard GD. By dramatically raising the bar for instability, momentum keeps the directional Hessian low for longer, allowing stable, rapid progress.

  • Batch Size and Stochastic Noise Interplay: Small batch sizes introduce stochastic noise that also postpones abrupt sharpening. Consequently, momentum's acceleration is most pronounced at large batch sizes, where SGD prematurely stumbles into the EoS regime.

Key Results

  • Momentum Threshold: Across CIFAR-10, CIFAR-100, ImageNet, and WikiText-2, SGDM matches SGD performance at small $\eta_{ef}$ and diverges to significantly lower training loss once $\eta_{ef}$ is large.
  • Extended Linear Scaling: In large-batch training, SGD degrades beyond a critical batch size due to entering EoS. Adding momentum postpones this failure point, effectively expanding the range of batch sizes where linear learning rate scaling holds.
  • Generalizability: The align-and-deviate pattern also replicates for Nesterov accelerated gradient and Adam (comparing $\beta_1 \in \{0, 0.5, 0.9\}$).

Limitations and Future Work

  • Extreme Momentum ($\mu \to 1$): The theoretical and empirical benefits break down when $\mu$ approaches 1; empirically, training loss sharply deteriorates for $\mu > 0.9$.
  • Scope of Architectures: While tested on CNNs, ViTs, and language Transformers, the authors note that empirical validation across even broader model families and larger scales remains future work.

Summary updated

Abstract

Momentum has become a crucial component in deep learning optimizers, necessitating a comprehensive understanding of when and why it accelerates stochastic gradient descent (SGD). To address the question of ''when'', we establish a meaningful comparison framework that examines the performance of SGD with Momentum (SGDM) under the \emph{effective learning rates} $\eta_{ef}$, and offers a holistic view of the momentum acceleration effect. In the comparison of SGDM and SGD with the same effective learning rate and the same batch size, we observe a consistent pattern: when $\eta_{ef}$ is small, SGDM and SGD experience almost the same empirical training losses; when $\eta_{ef}$ surpasses a certain threshold, SGDM begins to perform better than SGD. Furthermore, we observe that the advantage of SGDM over SGD becomes more pronounced with a larger batch size. For the question of ``why'', we find that the momentum acceleration is closely related to \emph{edge of stability} (EoS), a recently discovered phenomenon describing that the sharpness (largest eigenvalue of the Hessian) of the training trajectory often oscillates around the stability threshold. Specifically, the misalignment between SGD and SGDM happens at the same moment that SGD enters the EoS regime and converges slower. Momentum improves the performance of SGDM by preventing or deferring the occurrence of EoS. Together, this study unveils the interplay between momentum, learning rates, and batch sizes, thus improving our understanding of momentum acceleration.
BibTeX
@misc{fu2023when,
  author = {Jingwen Fu and Bohan Wang and Huishuai Zhang and Zhizheng Zhang and Zhi-Ming Ma and Wei Chen and Nanning Zheng},
  title = {{When and Why Momentum Accelerates SGD: An Empirical Study}},
  year = {2023},
  eprint = {2306.09000},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2306.09000},
}
Figure