# NEON+: Accelerated Gradient Methods for Extracting Negative Curvature for Non-Convex Optimization

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Dec 2017.

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

- [Escape saddle points by a simple gradient-descent based algorithm](https://mlsanity.com/paper/2111.14069/) (2021)
- [Improved Complexity for Smooth Nonconvex Optimization: A Two-Level Online Learning Approach with Quasi-Newton Methods](https://mlsanity.com/paper/2412.02175/) (2024)
- [Zeroth-Order Negative Curvature Finding: Escaping Saddle Points without Gradients](https://mlsanity.com/paper/2210.01496/) (2022)
- [Improving Online-to-Nonconvex Conversion for Smooth Optimization via Double Optimism](https://mlsanity.com/paper/2510.03167/) (2025)
- [Tackling benign nonconvexity with smoothing and stochastic gradients](https://mlsanity.com/paper/2202.09052/) (2022)
- [A Newton-CG based barrier method for finding a second-order stationary point of nonconvex conic optimization with complexity guarantees](https://mlsanity.com/paper/2207.05697/) (2022)
- [A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization](https://mlsanity.com/paper/2301.04204/) (2023)
- [Sharp First-Order Lower Bounds for Higher-Order Smooth Nonconvex Optimization](https://mlsanity.com/paper/2606.05438/) (2026)
- [Newton-CG methods for nonconvex unconstrained optimization with H"older continuous Hessian](https://mlsanity.com/paper/2311.13094/) (2023)

## Abstract (arXiv)

Accelerated gradient (AG) methods are breakthroughs in convex optimization, improving the convergence rate of the gradient descent method for optimization with smooth functions. However, the analysis of AG methods for non-convex optimization is still limited. It remains an open question whether AG methods from convex optimization can accelerate the convergence of the gradient descent method for finding local minimum of non-convex optimization problems. This paper provides an affirmative answer to this question. In particular, we analyze two renowned variants of AG methods (namely Polyak's Heavy Ball method and Nesterov's Accelerated Gradient method) for extracting the negative curvature from random noise, which is central to escaping from saddle points. By leveraging the proposed AG methods for extracting the negative curvature, we present a new AG algorithm with double loops for non-convex optimization~footnotethis is in contrast to a single-loop AG algorithm proposed in a recent manuscript~citepAGNON, which directly analyzed the Nesterov's AG method for non-convex optimization and appeared online on November 29, 2017. However, we emphasize that our work is an independent work, which is inspired by our earlier work~citepNEON17 and is based on a different novel analysis., which converges to second-order stationary point x such that |nabla f(x)|≤ ε and nabla2 f(x)≥ -√ε I with widetilde O(1/ε1.75) iteration complexity, improving that of gradient descent method by a factor of ε-0.25 and matching the best iteration complexity of second-order Hessian-free methods for non-convex optimization.