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

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 $-σ$ of the Hessian, a parameter that describes how nonconvex the function is. Our methods outperform known results for a range of parameter $σ$, and can be used to find approximate local minima. Our result implies an interesting dichotomy: there exists a threshold $σ_0$ so that the currently fastest methods for $σ>σ_0$ and for $σ<σ_0$ have different behaviors: the former scales with $n^{2/3}$ and the latter scales with $n^{3/4}$.