Accelerated Methods for Non-Convex Optimization

Abstract

We present an accelerated gradient method for non-convex optimization problems with Lipschitz continuous first and second derivatives. The method requires time $O({\epsilon }^{-7/4}\log (1/\epsilon ))$ to find an $\epsilon$-stationary point, meaning a point $x$ such that $\Vert \nabla f(x)\Vert \le \epsilon$. The method improves upon the $O({\epsilon }^{-2})$ complexity of gradient descent and provides the additional second-order guarantee that ${\nabla }^{2}f(x)⪰-O({\epsilon }^{1/2})I$ 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.

References in corpus (8)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Stochastic Variance Reduction for Nonconvex Optimization
• Variance Reduction for Faster Non-Convex Optimization
• When Are Nonconvex Problems Not Scary?
• A geometric alternative to Nesterov's accelerated gradient descent
• Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization
• A Second-Order Cone Based Approach for Solving the Trust Region Subproblem and Its Variants
• Faster Eigenvector Computation via Shift-and-Invert Preconditioning

Cited by in corpus (34)

• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• How to Escape Saddle Points Efficiently
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
• Non-convex Finite-Sum Optimization Via SCSG Methods
• On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization
• On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points
• Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Information
• Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
• Stochastic Cubic Regularization for Fast Nonconvex Optimization
• "Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions
• Towards Riemannian Accelerated Gradient Methods
• Exponential convergence rates for Batch Normalization: The power of length-direction decoupling in non-convex optimization
• Stochastic Variance-Reduced Cubic Regularized Newton Method
• On Noisy Negative Curvature Descent: Competing with Gradient Descent for Faster Non-convex Optimization
• An accelerated inexact proximal point method for solving nonconvex-concave min-max problems
• First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time
• Solving systems of phaseless equations via Riemannian optimization with optimal sampling complexity
• Stochastic Nonconvex Optimization with Large Minibatches
• Variance Reduced methods for Non-convex Composition Optimization
• Finding Local Minima via Stochastic Nested Variance Reduction
• Stabilized SVRG: Simple Variance Reduction for Nonconvex Optimization
• Cubic Regularization with Momentum for Nonconvex Optimization
• Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning
• Complexity of a quadratic penalty accelerated inexact proximal point method for solving linearly constrained nonconvex composite programs
• Saving Gradient and Negative Curvature Computations: Finding Local Minima More Efficiently
• NEON+: Accelerated Gradient Methods for Extracting Negative Curvature for Non-Convex Optimization
• Accelerated Stochastic Algorithms for Nonconvex Finite-sum and Multi-block Optimization
• Provable Accelerated Gradient Method for Nonconvex Low Rank Optimization
• The Global Optimization Geometry of Shallow Linear Neural Networks
• Third-order Smoothness Helps: Even Faster Stochastic Optimization Algorithms for Finding Local Minima
• Sample Efficient Stochastic Variance-Reduced Cubic Regularization Method
• A Newton-Based Method for Nonconvex Optimization with Fast Evasion of Saddle Points
• Optimality condition and complexity analysis for linearly-constrained optimization without differentiability on the boundary
• Adaptive Stochastic Gradient Langevin Dynamics: Taming Convergence and Saddle Point Escape Time