Accelerated Methods for NonConvex Optimization
Authors:
- Yair CarmonYCYair Carmon
- John C. DuchiJDJohn C. Duchi
- Oliver HinderOHOliver Hinder
- Aaron SidfordASAaron Sidford
Top Cited Papers
- 1 January 2018
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Optimization
- Vol. 28 (2) , 1751-1772
Abstract
We present an accelerated gradient method for nonconvex optimization problems with Lipschitz continuous first and second derivatives. In a time $O(\epsilon^{-7/4} \log(1/ \epsilon) )$, the method finds an $\epsilon$-stationary point, meaning a point $x$ such that $\|\nabla f(x)\| \le \epsilon$. The method improves upon the $O(\epsilon^{-2} )$ complexity of gradient descent and provides the additional second-order guarantee that $\lambda_{\min}(\nabla^2 f(x)) \gtrsim -\epsilon^{1/2}$ 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.
Keywords
All Related Versions
Funding Information
- PACCAR INC Fellowship
- National Science Foundation (NSF-CAREER-1553086)
- Stanford University
- Toyota USA
This publication has 21 references indexed in Scilit:
- Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic ProgrammingSIAM Journal on Optimization, 2013
- A note on the complexity of L p minimizationMathematical Programming, 2011
- Characterizations of Łojasiewicz inequalities: Subgradient flows, talweg, convexityTransactions of the American Mathematical Society, 2009
- Adaptive cubic regularisation methods for unconstrained optimization. Part I: motivation, convergence and numerical resultsMathematical Programming, 2009
- Cubic regularization of Newton method and its global performanceMathematical Programming, 2006
- Fast Curvature Matrix-Vector Products for Second-Order Gradient DescentNeural Computation, 2002
- On the complexity of approximating a KKT point of quadratic programmingMathematical Programming, 1998
- Fast Exact Multiplication by the HessianNeural Computation, 1994
- Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random StartSIAM Journal on Matrix Analysis and Applications, 1992
- Some NP-complete problems in quadratic and nonlinear programmingMathematical Programming, 1987