# Finding Approximate Local Minima Faster than Gradient Descent

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

## Key facts

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

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

- [Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion](https://mlsanity.com/paper/2302.03775/) (2023)
- [Stochastic Second-Order Methods Improve Best-Known Sample Complexity of SGD for Gradient-Dominated Function](https://mlsanity.com/paper/2205.12856/) (2022)
- [Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the O(ε-7/4) Complexity](https://mlsanity.com/paper/2201.11411/) (2022)
- [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)
- [Fast quantum state reconstruction via accelerated non-convex programming](https://mlsanity.com/paper/2104.07006/) (2021)
- [Simple and Optimal Stochastic Gradient Methods for Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2208.10025/) (2022)
- [Rethinking SIGN Training: Provable Nonconvex Acceleration without First- and Second-Order Gradient Lipschitz](https://mlsanity.com/paper/2310.14616/) (2023)

## Abstract (arXiv)

We design a non-convex second-order optimization algorithm that is guaranteed to return an approximate local minimum in time which scales linearly in the underlying dimension and the number of training examples. The time complexity of our algorithm to find an approximate local minimum is even faster than that of gradient descent to find a critical point. Our algorithm applies to a general class of optimization problems including training a neural network and other non-convex objectives arising in machine learning.