Stochastic Cubic Regularization for Fast Nonconvex Optimization

MaRDI QIDQ6293656arXivFDO

Authors Nilesh Tripuraneni, Mitchell Stern, Chi Jin, Jeffrey Regier, Michael I. Jordan

Publication date 8 November 2017

Published in arXiv

arXiv classification

cs.LGmath.OCstat.ML

Abstract: 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 $mathcalildeO(epsilo{n}^{-3.5})$ stochastic gradient and stochastic Hessian-vector product evaluations. The latter can be computed as efficiently as stochastic gradients. This improves upon the $mathcalildeO(epsilo{n}^{-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.

Cited in

(1)

• Blockwise Stabilized Adaptive Cubic Regularization with Subsolvers via Recurrence

This page was built for publication: Stochastic Cubic Regularization for Fast Nonconvex Optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6293656)