"Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions

Abstract

We develop and analyze a variant of Nesterov's accelerated gradient descent (AGD) for minimization of smooth non-convex functions. We prove that one of two cases occurs: either our AGD variant converges quickly, as if the function was convex, or we produce a certificate that the function is "guilty" of being non-convex. This non-convexity certificate allows us to exploit negative curvature and obtain deterministic, dimension-free acceleration of convergence for non-convex functions. For a function $f$ with Lipschitz continuous gradient and Hessian, we compute a point $x$ with $\Vert \nabla f(x)\Vert \le \epsilon$ in $O({\epsilon }^{-7/4}\log (1/\epsilon ))$ gradient and function evaluations. Assuming additionally that the third derivative is Lipschitz, we require only $O({\epsilon }^{-5/3}\log (1/\epsilon ))$ evaluations.

References in corpus (4)

• Supervised Dictionary Learning
• Qualitatively characterizing neural network optimization problems
• Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow
• Accelerated Methods for Non-Convex Optimization

Cited by in corpus (22)

• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• Non-convex Finite-Sum Optimization Via SCSG Methods
• Escaping Saddles with Stochastic Gradients
• Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
• Last-iterate convergence rates for min-max optimization
• The proximal point method revisited
• Towards Riemannian Accelerated Gradient Methods
• Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron
• Catalyst Acceleration for Gradient-Based Non-Convex Optimization
• Finding Local Minima via Stochastic Nested Variance Reduction
• Saving Gradient and Negative Curvature Computations: Finding Local Minima More Efficiently
• Lower Bounds for Higher-Order Convex Optimization
• Provable Accelerated Gradient Method for Nonconvex Low Rank Optimization
• Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations
• A Log-Barrier Newton-CG Method for Bound Constrained Optimization with Complexity Guarantees
• Escaping Saddle Points for Nonsmooth Weakly Convex Functions via Perturbed Proximal Algorithms
• Third-order Smoothness Helps: Even Faster Stochastic Optimization Algorithms for Finding Local Minima
• On the Regret Minimization of Nonconvex Online Gradient Ascent for Online PCA
• Cutting plane methods can be extended into nonconvex optimization
• The Minimax Complexity of Distributed Optimization
• First-Order Algorithms Without Lipschitz Gradient: A Sequential Local Optimization Approach
• Escaping Saddle Points with Compressed SGD