Natasha: Faster Non-Convex Stochastic Optimization Via Strongly Non-Convex Parameter
Zeyuan Allen-Zhu · arXiv (Cornell University) · 2017
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 $σ