# Heavy-ball Algorithms Always Escape Saddle Points

arXiv: https://arxiv.org/abs/1907.09697 · HTML: https://mlsanity.com/paper/1907.09697/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jul 2019.

## Built on by (most cited first, 13 of 13)

- [Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the O(ε-7/4) Complexity](https://mlsanity.com/paper/2201.11411/) (2022)
- [Leveraging Continuous Time to Understand Momentum When Training Diagonal Linear Networks](https://mlsanity.com/paper/2403.05293/) (2024)
- [Training Deep Neural Networks with Adaptive Momentum Inspired by the Quadratic Optimization](https://mlsanity.com/paper/2110.09057/) (2021)
- [Stochastic Gradient Langevin Dynamics with Variance Reduction](https://mlsanity.com/paper/2102.06759/) (2021)
- [The Role of Momentum Parameters in the Optimal Convergence of Adaptive Polyak's Heavy-ball Methods](https://mlsanity.com/paper/2102.07314/) (2021)
- [Inertial Proximal Deep Learning Alternating Minimization for Efficient Neutral Network Training](https://mlsanity.com/paper/2102.00267/) (2021)
- [TAIGen: Training-Free Adversarial Image Generation via Diffusion Models](https://mlsanity.com/paper/2508.15020/) (2025)
- [Adapting Step-size: A Unified Perspective to Analyze and Improve Gradient-based Methods for Adversarial Attacks](https://mlsanity.com/paper/2301.11546/) (2023)
- [AdaCubic: An Adaptive Cubic Regularization Optimizer for Deep Learning](https://mlsanity.com/paper/2604.09437/) (2026)
- [Accelerated Multiplicative Weights Update Avoids Saddle Points almost always](https://mlsanity.com/paper/2204.11407/) (2022)
- [DRSOM: A Dimension Reduced Second-Order Method](https://mlsanity.com/paper/2208.00208/) (2022)
- [Langevin Multiplicative Weights Update with Applications in Polynomial Portfolio Management](https://mlsanity.com/paper/2502.19210/) (2025)
- [Convergence of optimizers implies eigenvalues filtering at equilibrium](https://mlsanity.com/paper/2510.09034/) (2025)

## Abstract (arXiv)

Nonconvex optimization algorithms with random initialization have attracted increasing attention recently. It has been showed that many first-order methods always avoid saddle points with random starting points. In this paper, we answer a question: can the nonconvex heavy-ball algorithms with random initialization avoid saddle points? The answer is yes! Direct using the existing proof technique for the heavy-ball algorithms is hard due to that each iteration of the heavy-ball algorithm consists of current and last points. It is impossible to formulate the algorithms as iteration like xk+1= g(xk) under some mapping g. To this end, we design a new mapping on a new space. With some transfers, the heavy-ball algorithm can be interpreted as iterations after this mapping. Theoretically, we prove that heavy-ball gradient descent enjoys larger stepsize than the gradient descent to escape saddle points to escape the saddle point. And the heavy-ball proximal point algorithm is also considered; we also proved that the algorithm can always escape the saddle point.