# Accelerated Methods for Non-Convex Optimization

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Nov 2016.

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

- [Fast Federated Learning in the Presence of Arbitrary Device Unavailability](https://mlsanity.com/paper/2106.04159/) (2021)
- [Large-Scale Deep Learning Optimizations: A Comprehensive Survey](https://mlsanity.com/paper/2111.00856/) (2021)
- [Why Do Local Methods Solve Nonconvex Problems?](https://mlsanity.com/paper/2103.13462/) (2021)
- [Escaping Saddle Points Faster with Stochastic Momentum](https://mlsanity.com/paper/2106.02985/) (2021)
- [A Cubic-regularized Policy Newton Algorithm for Reinforcement Learning](https://mlsanity.com/paper/2304.10951/) (2023)
- [A Stochastic Newton Algorithm for Distributed Convex Optimization](https://mlsanity.com/paper/2110.02954/) (2021)
- [Fast quantum state reconstruction via accelerated non-convex programming](https://mlsanity.com/paper/2104.07006/) (2021)
- [From graphs to DAGs: a low-complexity model and a scalable algorithm](https://mlsanity.com/paper/2204.04644/) (2022)
- [Accelerating nuclear-norm regularized low-rank matrix optimization through Burer-Monteiro decomposition](https://mlsanity.com/paper/2204.14067/) (2022)
- [Simple and Optimal Stochastic Gradient Methods for Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2208.10025/) (2022)
- [Differentially Private Optimization for Smooth Nonconvex ERM](https://mlsanity.com/paper/2302.04972/) (2023)
- [Escaping Saddle Points for Nonsmooth Weakly Convex Functions via Perturbed Proximal Algorithms](https://mlsanity.com/paper/2102.02837/) (2021)
- [Tackling benign nonconvexity with smoothing and stochastic gradients](https://mlsanity.com/paper/2202.09052/) (2022)
- [Asynchronous Training Schemes in Distributed Learning with Time Delay](https://mlsanity.com/paper/2208.13154/) (2022)
- [Escaping Saddle Points with Compressed SGD](https://mlsanity.com/paper/2105.10090/) (2021)
- [Faster Perturbed Stochastic Gradient Methods for Finding Local Minima](https://mlsanity.com/paper/2110.13144/) (2021)
- [Beyond first-order methods for non-convex non-concave min-max optimization](https://mlsanity.com/paper/2304.08389/) (2023)
- [A randomized algorithm for nonconvex minimization with inexact evaluations and complexity guarantees](https://mlsanity.com/paper/2310.18841/) (2023)
- [DRSOM: A Dimension Reduced Second-Order Method](https://mlsanity.com/paper/2208.00208/) (2022)
- [Accelerated Optimization Landscape of Linear-Quadratic Regulator](https://mlsanity.com/paper/2307.03590/) (2023)

## Abstract (arXiv)

We present an accelerated gradient method for non-convex optimization problems with Lipschitz continuous first and second derivatives. The method requires time O(ε-7/4 log(1/ ε) ) to find an ε-stationary point, meaning a point x such that |nabla f(x)| ≤ ε. The method improves upon the O(ε-2 ) complexity of gradient descent and provides the additional second-order guarantee that nabla2 f(x) succeq -O(ε1/2)I for the computed x. Furthermore, our method is Hessian free, i.e. it only requires gradient computations, and is therefore suitable for large scale applications.