Escaping Saddle Points Faster with Stochastic Momentum

Jun-Kun Wang, Chi-Heng Lin, Jacob D. Abernethy

Introduction

In deep learning optimization, reaching a first-order stationary point—where the gradient is zero—is often insufficient. The loss landscapes of neural networks are riddled with saddle points: regions where the gradient vanishes, but the surface curves upwards in some directions and downwards in others. While standard Stochastic Gradient Descent (SGD) can languish near these points, practitioners have long favored stochastic momentum (e.g., the Heavy-Ball method) for its empirical ability to accelerate training. However, a rigorous theoretical explanation for why momentum specifically aids in escaping saddle points has remained elusive.

This paper provides a formal proof that stochastic momentum accelerates the escape from saddle points by recursively amplifying the "escape signal" along directions of negative curvature.

The Mechanism: Escape Signal Amplification

The core insight of this work is that momentum acts as a recursive filter. When an optimizer encounters a saddle point, there exists at least one direction of negative curvature—an "exit" toward lower loss values. While standard SGD relies on random noise to eventually drift down these slopes, momentum accumulates these small directional components over time.

Comparison of SGD and SGD + momentum trajectories near a saddle point, illustrating how momentum aligns with the escape direction.

As shown in Figure 1, the momentum term biases the current update toward the direction of previous progress. In the vicinity of a saddle point, this leads to an exponential increase in the "push" out of the region compared to the isotropic jitter of standard SGD.

Theoretical Framework and the Role of $\beta$

To formalize this benefit, the authors introduce several key properties:

  • Correlated Negative Curvature (CNC): This assumes that stochastic noise is not entirely orthogonal to the direction of steepest descent at a saddle point.
  • APAG and APCG: New metrics describing how the momentum vector aligns with the gradient and local curvature.

A significant contribution of this analysis is the justification for using large momentum parameters, such as $\beta = 0.9$, which is standard practice in deep learning. The theory demonstrates that the time required to escape a saddle point is essentially proportional to $(1-\beta)$. As $\beta$ approaches 1, the effective "memory" of the optimizer increases, allowing it to sense and exploit the second-order geometry (the Hessian) of the landscape more effectively without explicit computation.

Empirical Results

The authors validated their theoretical findings using synthetic non-convex objectives and the classic phase retrieval problem. In both cases, increasing the momentum parameter $\beta$ led to a dramatic reduction in the time spent in "flat" regions associated with saddle points.

Function value optimization for different momentum parameters beta. Higher values of beta result in significantly faster escapes from the initial saddle point plateau.

As seen in Figure 3, the transition from a high-loss plateau to a lower-value region happens much earlier as $\beta$ increases from 0 (standard SGD) to 0.9. This "stark" acceleration confirms that momentum isn't just smoothing the trajectory; it is actively accelerating the discovery of descent directions.

Conclusion

By bridging the gap between theory and practice, this work provides a mathematical foundation for the success of stochastic momentum in non-convex optimization. The proof that escape time scales with $(1-\beta)$ offers a clear guideline for hyperparameter tuning and highlights momentum's role as an implicit exploiter of second-order landscape features. While the current iteration complexity bounds remain high, this research opens new avenues for understanding the efficiency of modern deep learning optimizers.

Summary updated

BibTeX
@inproceedings{wang2020escaping,
  author = {Jun-Kun Wang and Chi-Heng Lin and Jacob D. Abernethy},
  title = {{Escaping Saddle Points Faster with Stochastic Momentum}},
  booktitle = {International Conference on Learning Representations},
  year = {2020},
  url = {https://openreview.net/forum?id=7n3PbXmPPQ},
}
Figure