Stochastic Variance-Reduced Cubic Regularized Newton Method

Abstract

We propose a stochastic variance-reduced cubic regularized Newton method for non-convex optimization. At the core of our algorithm is a novel semi-stochastic gradient along with a semi-stochastic Hessian, which are specifically designed for cubic regularization method. We show that our algorithm is guaranteed to converge to an $(\epsilon ,\sqrt{\epsilon })$-approximately local minimum within $\tilde{O}(n^{4/5}/{\epsilon }^{3/2})$ second-order oracle calls, which outperforms the state-of-the-art cubic regularization algorithms including subsampled cubic regularization. Our work also sheds light on the application of variance reduction technique to high-order non-convex optimization methods. Thorough experiments on various non-convex optimization problems support our theory.

16 pages, 3 figures, 2 tables

References in corpus (16)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Matrix Completion has No Spurious Local Minimum
• A Linearly-Convergent Stochastic L-BFGS Algorithm
• Variance Reduction for Faster Non-Convex Optimization
• Convergence rates of sub-sampled Newton methods
• Sub-Sampled Newton Methods I: Globally Convergent Algorithms
• Sub-Sampled Newton Methods II: Local Convergence Rates
• Fast and Simple PCA via Convex Optimization
• Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Information
• Accelerated Methods for Non-Convex Optimization
• Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
• Second-Order Optimization for Non-Convex Machine Learning: An Empirical Study
• A Variance Reduced Stochastic Newton Method
• NEON+: Accelerated Gradient Methods for Extracting Negative Curvature for Non-Convex Optimization
• Tracking the gradients using the Hessian: A new look at variance reducing stochastic methods
• Curvature-aided Incremental Aggregated Gradient Method

Cited by in corpus (12)

• Global Convergence of Langevin Dynamics Based Algorithms for Nonconvex Optimization
• Stochastic Recursive Variance-Reduced Cubic Regularization Methods
• Finding Local Minima via Stochastic Nested Variance Reduction
• A Stochastic Trust Region Method for Non-convex Minimization
• Stochastic Variance-Reduced Prox-Linear Algorithms for Nonconvex Composite Optimization
• Stochastic Trust Region Methods with Trust Region Radius Depending on Probabilistic Models
• A Distributed Cubic-Regularized Newton Method for Smooth Convex Optimization over Networks
• Inexact Proximal Cubic Regularized Newton Methods for Convex Optimization
• Convergence analysis of stochastic higher-order majorization-minimization algorithms
• Sample Efficient Stochastic Variance-Reduced Cubic Regularization Method
• Escaping Saddle Points with Stochastically Controlled Stochastic Gradient Methods
• Escaping Saddle Points in Distributed Newton's Method with Communication Efficiency and Byzantine Resilience