Title: 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}$.