Stochastic Variance-Reduced Cubic Regularization for Nonconvex Optimization

Abstract

Cubic regularization (CR) is an optimization method with emerging popularity due to its capability to escape saddle points and converge to second-order stationary solutions for nonconvex optimization. However, CR encounters a high sample complexity issue for finite-sum problems with a large data size. %Various inexact variants of CR have been proposed to improve the sample complexity. In this paper, we propose a stochastic variance-reduced cubic-regularization (SVRC) method under random sampling, and study its convergence guarantee as well as sample complexity. We show that the iteration complexity of SVRC for achieving a second-order stationary solution within $\epsilon$ accuracy is $O({\epsilon }^{-3/2})$, which matches the state-of-art result on CR types of methods. Moreover, our proposed variance reduction scheme significantly reduces the per-iteration sample complexity. The resulting total Hessian sample complexity of our SVRC is ${\Oc}(N^{2/3} ε^{-3/2})$, which outperforms the state-of-art result by a factor of $O(N^{2/15})$. We also study our SVRC under random sampling without replacement scheme, which yields a lower per-iteration sample complexity, and hence justifies its practical applicability.

Cited by in corpus (12)

• A Hybrid Stochastic Optimization Framework for Stochastic Composite Nonconvex Optimization
• Inexact Tensor Methods with Dynamic Accuracies
• A Distributed Cubic-Regularized Newton Method for Smooth Convex Optimization over Networks
• Escaping Saddle-Points Faster under Interpolation-like Conditions
• Two-Level K-FAC Preconditioning for Deep Learning
• Contrastive Weight Regularization for Large Minibatch SGD
• A Stochastic Objective-Function-Free Adaptive Regularization Method with Optimal Complexity
• Some Limit Properties of Markov Chains Induced by Stochastic Recursive Algorithms
• Optimization for Supervised Machine Learning: Randomized Algorithms for Data and Parameters
• Invexifying Regularization of Non-Linear Least-Squares Problems
• Escaping Saddle Points in Distributed Newton's Method with Communication Efficiency and Byzantine Resilience
• Communication-Efficient Network-Distributed Optimization with Differential-Coded Compressors