Stochastic Cubic Regularization for Fast Nonconvex Optimization

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 $\tilde{\mathcal{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 $\tilde{\mathcal{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.

The first two authors contributed equally

References in corpus (6)

• The Loss Surfaces of Multilayer Networks
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
• Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Information
• Accelerated Methods for Non-Convex Optimization
• Fast Black-box Variational Inference through Stochastic Trust-Region Optimization

Cited by in corpus (7)

• Negative eigenvalues of the Hessian in deep neural networks
• Byzantine-Resilient Non-Convex Stochastic Gradient Descent
• Saving Gradient and Negative Curvature Computations: Finding Local Minima More Efficiently
• Third-order Smoothness Helps: Even Faster Stochastic Optimization Algorithms for Finding Local Minima
• Convergence analysis of stochastic higher-order majorization-minimization algorithms
• A Stochastic Objective-Function-Free Adaptive Regularization Method with Optimal Complexity
• SingCubic: Cyclic Incremental Newton-type Gradient Descent with Cubic Regularization for Non-Convex Optimization