Natasha: Faster NonConvex Stochastic Optimization via Strongly NonConvex Parameter
[edit]
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:8997, 2017.
Abstract
Given a nonconvex function $f(x)$ that is an average of $n$ smooth functions, we design stochastic firstorder methods to find its approximate stationary points. The performance of our new methods depend on the smallest (negative) eigenvalue $\sigma$ of the Hessian. This parameter $\sigma$ captures how strongly nonconvex $f(x)$ is, and is analogous to the strong convexity parameter for convex optimization. At least in theory, our methods outperform known results for a range of parameter $\sigma$, and can also 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}$.
Related Material


