# A Newton-Based Method for Nonconvex Optimization with Fast Evasion of Saddle Points

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Jul 2017.

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

- [A Single-Timescale Method for Stochastic Bilevel Optimization](https://mlsanity.com/paper/2102.04671/) (2021)
- [Doubly Adaptive Scaled Algorithm for Machine Learning Using Second-Order Information](https://mlsanity.com/paper/2109.05198/) (2021)
- [A Scalable Second Order Method for Ill-Conditioned Matrix Completion from Few Samples](https://mlsanity.com/paper/2106.02119/) (2021)
- [A Cubic-regularized Policy Newton Algorithm for Reinforcement Learning](https://mlsanity.com/paper/2304.10951/) (2023)
- [Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimization](https://mlsanity.com/paper/2108.01772/) (2021)
- [FLECS-CGD: A Federated Learning Second-Order Framework via Compression and Sketching with Compressed Gradient Differences](https://mlsanity.com/paper/2210.09626/) (2022)
- [Quantization Avoids Saddle Points in Distributed Optimization](https://mlsanity.com/paper/2403.10423/) (2024)
- [Series of Hessian-Vector Products for Tractable Saddle-Free Newton Optimisation of Neural Networks](https://mlsanity.com/paper/2310.14901/) (2023)
- [Avoiding strict saddle points of nonconvex regularized problems](https://mlsanity.com/paper/2401.09274/) (2024)
- [Don't Be So Positive: Negative Step Sizes in Second-Order Methods](https://mlsanity.com/paper/2411.11224/) (2024)
- [Boundary Conditions for Linear Exit Time Gradient Trajectories Around Saddle Points: Analysis and Algorithm](https://mlsanity.com/paper/2101.02625/) (2021)
- [Gradient Descent and the Power Method: Exploiting their connection to find the leftmost eigen-pair and escape saddle points](https://mlsanity.com/paper/2211.00866/) (2022)

## Abstract (arXiv)

Machine learning problems such as neural network training, tensor decomposition, and matrix factorization, require local minimization of a nonconvex function. This local minimization is challenged by the presence of saddle points, of which there can be many and from which descent methods may take inordinately large number of iterations to escape. This paper presents a second-order method that modifies the update of Newton's method by replacing the negative eigenvalues of the Hessian by their absolute values and uses a truncated version of the resulting matrix to account for the objective's curvature. The method is shown to escape saddles in at most 1 + log3/2 (δ/2varepsilon) iterations where varepsilon is the target optimality and δ characterizes a point sufficiently far away from the saddle. This base of this exponential escape is 3/2 independently of problem constants. Adding classical properties of Newton's method, the paper proves convergence to a local minimum with probability 1-p in Oleft(log(1/p)) + O(log(1/varepsilon)right) iterations.