Saving Gradient and Negative Curvature Computations: Finding Local Minima More Efficiently

Abstract

We propose a family of nonconvex optimization algorithms that are able to save gradient and negative curvature computations to a large extent, and are guaranteed to find an approximate local minimum with improved runtime complexity. At the core of our algorithms is the division of the entire domain of the objective function into small and large gradient regions: our algorithms only perform gradient descent based procedure in the large gradient region, and only perform negative curvature descent in the small gradient region. Our novel analysis shows that the proposed algorithms can escape the small gradient region in only one negative curvature descent step whenever they enter it, and thus they only need to perform at most $N_{\epsilon }$ negative curvature direction computations, where $N_{\epsilon }$ is the number of times the algorithms enter small gradient regions. For both deterministic and stochastic settings, we show that the proposed algorithms can potentially beat the state-of-the-art local minima finding algorithms. For the finite-sum setting, our algorithm can also outperform the best algorithm in a certain regime.

31 pages, 1 table

References in corpus (17)

• The Loss Surfaces of Multilayer Networks
• Identifying and attacking the saddle point problem in high-dimensional non-convex optimization
• Global Optimality of Local Search for Low Rank Matrix Recovery
• How to Escape Saddle Points Efficiently
• Stochastic Variance Reduction for Nonconvex Optimization
• Matrix Completion has No Spurious Local Minimum
• Variance Reduction for Faster Non-Convex Optimization
• The Power of Normalization: Faster Evasion of Saddle Points
• Accelerated Methods for Non-Convex Optimization
• 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
• Faster Eigenvector Computation via Shift-and-Invert Preconditioning
• Follow the Compressed Leader: Faster Online Learning of Eigenvectors and Faster MMWU
• First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time
• On the Gap Between Strict-Saddles and True Convexity: An Omega(log d) Lower Bound for Eigenvector Approximation

Cited by in corpus (4)

• Stochastic Recursive Variance-Reduced Cubic Regularization Methods
• Finding Local Minima via Stochastic Nested Variance Reduction
• On the Sublinear Convergence of Randomly Perturbed Alternating Gradient Descent to Second Order Stationary Solutions
• Third-order Smoothness Helps: Even Faster Stochastic Optimization Algorithms for Finding Local Minima