Natasha: Faster Non-Convex Stochastic Optimization Via Strongly Non-Convex Parameter

Abstract

Given a nonconvex function that is an average of $n$ smooth functions, we design stochastic first-order methods to find its approximate stationary points. The convergence of our new methods depends on the smallest (negative) eigenvalue $-\sigma$ of the Hessian, a parameter that describes how nonconvex the function is. Our methods outperform known results for a range of parameter $\sigma$, and can be used to find approximate local minima. Our result implies an interesting dichotomy: there exists a threshold ${\sigma }_0$ so that the currently fastest methods for $\sigma >{\sigma }_0$ and for $\sigma <{\sigma }_0$ have different behaviors: the former scales with $n^{2/3}$ and the latter scales with $n^{3/4}$.

V2-V5 corrected typos, polished writing, and added citations. (We mis-stated the complexity of the prior work repeatSVRG in V1-V4, and have fixed this mistake in V5.)

References in corpus (6)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Non-convex Finite-Sum Optimization Via SCSG Methods
• Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization
• Neon2: Finding Local Minima via First-Order Oracles
• Follow the Compressed Leader: Faster Online Learning of Eigenvectors and Faster MMWU
• Katyusha X: Practical Momentum Method for Stochastic Sum-of-Nonconvex Optimization

Cited by in corpus (19)

• Non-convex Finite-Sum Optimization Via SCSG Methods
• On the Convergence of Adaptive Gradient Methods for Nonconvex Optimization
• Stochastic Recursive Gradient Algorithm for Nonconvex Optimization
• Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Information
• Byzantine-Resilient Non-Convex Stochastic Gradient Descent
• Scaling-up Distributed Processing of Data Streams for Machine Learning
• Katyusha X: Practical Momentum Method for Stochastic Sum-of-Nonconvex Optimization
• Stochastic Nonconvex Optimization with Large Minibatches
• Improved Sample Complexity for Stochastic Compositional Variance Reduced Gradient
• Mini-Batch Stochastic ADMMs for Nonconvex Nonsmooth Optimization
• Lower Bounds for Smooth Nonconvex Finite-Sum Optimization
• Lower Bounds for Higher-Order Convex Optimization
• Local Optimality and Generalization Guarantees for the Langevin Algorithm via Empirical Metastability
• Accelerated Stochastic Algorithms for Nonconvex Finite-sum and Multi-block Optimization
• Variance Reduction on General Adaptive Stochastic Mirror Descent
• Escaping Saddle Points with Stochastically Controlled Stochastic Gradient Methods
• Multiplicative Weights Update as a Distributed Constrained Optimization Algorithm: Convergence to Second-order Stationary Points Almost Always
• DTN: A Learning Rate Scheme with Convergence Rate of $\mathcal{O}(1/t)$ for SGD
• Improved Oracle Complexity of Variance Reduced Methods for Nonsmooth Convex Stochastic Composition Optimization