Stochastic Cubic Regularization for Fast Nonconvex Optimization

By Nilesh Tripuraneni, Mitchell Stern, Chi Jin, Jeffrey C. Regier, Michael I. Jordan. 2017

193 citations recorded by the source corpus.

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}}(\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.

Subfields: Artificial Intelligence, Computational Mechanics, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Computational Theory and Mathematics

Citations in the corpus

How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD (2018, methodology): “This is no slower than the best known stochastic version of Newton’s method in all parameter regimes [27].”
Negative eigenvalues of the Hessian in deep neural networks (2018, background): “In particular, most of these methods need to solve an inner-loop when close to a saddle point, either to ﬁnd the direction of most negative curvature (Allen-Zhu, 2017) or to solve the cubic regularized problem (Tripuraneni et al., 2017).”
A Subsampling Line-Search Method with Second-Order Results (2018, methodology): “Alternatively, one can extract second-order information and escape saddle points using accelerated gradient techniques in the stochastic setting [46].”
Stochastic Gradient Descent for Nonconvex Learning Without Bounded Gradient Assumptions (2019, methodology): “e rates of nonconvex SGD were established in Ghadimi and Lan [6], which was extended to stochastic variance reduction [7], stochastic proximal gradient descent [8] and stochastic cubic regularization [9]. However, these results require to impose a nontrivial boundedness assumption on the gradients a”
Natasha 2: Faster Non-Convex Optimization Than SGD (2017, methodology): “This includes stochastic cubic regularization [44] which gives T = O ( ε − 3 .”
Lower bounds for non-convex stochastic optimization (2019, methodology): “[47] provide a sub-sampled cubic regularization method that uses stochastic Hessian-vector products and attains a rate of −3.”
Adaptive norms for deep learning with regularized Newton methods (2019, background): “(1), the above condition can be met by random sub-sampling due to classical concentration results for sums of random variables (Xu et al., 2017b; Kohler & Lucchi, 2017; Tripuraneni et al., 2017).”
Do Subsampled Newton Methods Work for High-Dimensional Data? (2019, methodology): “SSN has also been applied to optimize nonconvex problem (Xu, Roosta Khorasan, and Mahoney 2017; Tripuraneni et al. 2018).”
SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator (2018, background): “Recently, many literature study the problem of how to avoid or escape saddle points and achieve an approximate local minimizer at a polynomial gradient cost (Ge et al., 2015; Jin et al., 2017a; Xu et al., 2017; Allen-Zhu & Li, 2017; Hazan et al., 2015; Levy, 2016; Allen-Zhu, 2017; Reddi et al., 2018”