Stochastic Cubic Regularization for Fast Nonconvex Optimization
This provides a faster algorithm for nonconvex optimization, which is incremental as it builds on a classic method but improves efficiency for machine learning practitioners.
The paper tackles the problem of fast nonconvex optimization by proposing a stochastic cubic-regularized Newton method, which finds approximate local minima in Õ(ε^{-3.5}) stochastic evaluations, improving upon the Õ(ε^{-4}) rate of stochastic gradient descent.
This paper proposes a stochastic variant of a classic algorithm---the cubic-regularized Newton method [Nesterov and Polyak 2006]. The proposed algorithm efficiently escapes saddle points and finds approximate local minima for general smooth, nonconvex functions in only $\mathcal{\tilde{O}}(ε^{-3.5})$ stochastic gradient and stochastic Hessian-vector product evaluations. The latter can be computed as efficiently as stochastic gradients. This improves upon the $\mathcal{\tilde{O}}(ε^{-4})$ rate of stochastic gradient descent. Our rate matches the best-known result for finding local minima without requiring any delicate acceleration or variance-reduction techniques.