Finding Approximate Local Minima Faster than Gradient Descent
Not on the map. Why?
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.
Key facts. Cited by 8 papers in the map (data through 7 Oct 2026). First posted on arXiv 3 Nov 2016.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2021: 3; 2022: 3; 2023: 2.
8 papers.
- 2023Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversioncited by 42
- 2022Stochastic Second-Order Methods Improve Best-Known Sample Complexity of SGD for Gradient-Dominated Functioncited by 19
- 2022Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the O(ε-7/4) Complexitycited by 17
- 2021Large-Scale Deep Learning Optimizations: A Comprehensive Surveycited by 10
- 2021Why Do Local Methods Solve Nonconvex Problems?cited by 8
- 2021Fast quantum state reconstruction via accelerated non-convex programmingcited by 5
- 2022Simple and Optimal Stochastic Gradient Methods for Nonsmooth Nonconvex Optimizationcited by 5
- 2023Rethinking SIGN Training: Provable Nonconvex Acceleration without First- and Second-Order Gradient Lipschitzcited by 4
- 2023Rethinking SIGN Training: Provable Nonconvex Acceleration without First- and Second-Order Gradient Lipschitz23 Oct 2023
- 2023Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion7 Feb 2023
- 2022Simple and Optimal Stochastic Gradient Methods for Nonsmooth Nonconvex Optimization22 Aug 2022
- 2022Stochastic Second-Order Methods Improve Best-Known Sample Complexity of SGD for Gradient-Dominated Function25 May 2022
- 2022Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the O(ε-7/4) Complexity27 Jan 2022
- 2021Large-Scale Deep Learning Optimizations: A Comprehensive Survey1 Nov 2021
- 2021Fast quantum state reconstruction via accelerated non-convex programming14 Apr 2021
- 2021Why Do Local Methods Solve Nonconvex Problems?24 Mar 2021