NIPS Proceedingsβ

Stochastic Cubic Regularization for Fast Nonconvex Optimization

Part of: Advances in Neural Information Processing Systems 31 (NIPS 2018) pre-proceedings

[PDF] [BibTeX] [Supplemental]


Conference Event Type: Oral


This paper proposes a stochastic variant of a classic algorithm---the cubic-regularized Newton method [Nesterov and Polyak]. The proposed algorithm efficiently escapes saddle points and finds approximate local minima for general smooth, nonconvex functions in only $\mathcal{\tilde{O}}(\epsilon^{-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}}(\epsilon^{-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.