Accelerated Methods for NonConvex Optimization

Authors:
  • YCYair Carmon
    Yair Carmon
  • JDJohn C. Duchi
    John C. Duchi
  • OHOliver Hinder
    Oliver Hinder
  • ASAaron Sidford
    Aaron Sidford

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.
Funding Information
  • PACCAR INC Fellowship
  • National Science Foundation (NSF-CAREER-1553086)
  • Stanford University
  • Toyota USA

This publication has 21 references indexed in Scilit: