Sample Efficient Stochastic Variance-Reduced Cubic Regularization Method

Abstract

We propose a sample efficient stochastic variance-reduced cubic regularization (Lite-SVRC) algorithm for finding the local minimum efficiently in nonconvex optimization. The proposed algorithm achieves a lower sample complexity of Hessian matrix computation than existing cubic regularization based methods. At the heart of our analysis is the choice of a constant batch size of Hessian matrix computation at each iteration and the stochastic variance reduction techniques. In detail, for a nonconvex function with $n$ component functions, Lite-SVRC converges to the local minimum within $\tilde{O}(n+n^{2/3}/{\epsilon }^{3/2})$ Hessian sample complexity, which is faster than all existing cubic regularization based methods. Numerical experiments with different nonconvex optimization problems conducted on real datasets validate our theoretical results.

arXiv comment24 pages, 2 figures, 1 table. The first version of this paper was submitted to UAI 2018 on March 9, 2018. This is the second version with improved presentation and additional baselines in the experiments, and was submitted to NeurIPS 2018 on May 18, 2018

References in corpus (9)

• Matrix Completion has No Spurious Local Minimum
• Variance Reduction for Faster Non-Convex Optimization
• Accelerated Methods for Non-Convex Optimization
• Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Information
• Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
• Second-Order Optimization for Non-Convex Machine Learning: An Empirical Study
• Stochastic Variance-Reduced Cubic Regularized Newton Method
• Tracking the gradients using the Hessian: A new look at variance reducing stochastic methods
• Curvature-aided Incremental Aggregated Gradient Method

Cited by in corpus (2)

• Stochastic Recursive Variance-Reduced Cubic Regularization Methods
• A Stochastic Trust Region Method for Non-convex Minimization