Stochastic Recursive Variance-Reduced Cubic Regularization Methods

Abstract

Stochastic Variance-Reduced Cubic regularization (SVRC) algorithms have received increasing attention due to its improved gradient/Hessian complexities (i.e., number of queries to stochastic gradient/Hessian oracles) to find local minima for nonconvex finite-sum optimization. However, it is unclear whether existing SVRC algorithms can be further improved. Moreover, the semi-stochastic Hessian estimator adopted in existing SVRC algorithms prevents the use of Hessian-vector product-based fast cubic subproblem solvers, which makes SVRC algorithms computationally intractable for high-dimensional problems. In this paper, we first present a Stochastic Recursive Variance-Reduced Cubic regularization method (SRVRC) using a recursively updated semi-stochastic gradient and Hessian estimators. It enjoys improved gradient and Hessian complexities to find an $(\epsilon ,\sqrt{\epsilon })$-approximate local minimum, and outperforms the state-of-the-art SVRC algorithms. Built upon SRVRC, we further propose a Hessian-free SRVRC algorithm, namely SRVRC${}_{\text{free}}$, which only requires stochastic gradient and Hessian-vector product computations, and achieves $\tilde{O}(dn{\epsilon }^{-2}\wedge d{\epsilon }^{-3})$ runtime complexity, where $n$ is the number of component functions in the finite-sum structure, $d$ is the problem dimension, and $\epsilon$ is the optimization precision. This outperforms the best-known runtime complexity $\tilde{O}(d{\epsilon }^{-3.5})$ achieved by stochastic cubic regularization algorithm proposed in Tripuraneni et al. 2018.

arXiv comment34 pages, 1 figure, 2 tables

References in corpus (20)

• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• Global Optimality of Local Search for Low Rank Matrix Recovery
• How to Escape Saddle Points Efficiently
• Neon2: Finding Local Minima via First-Order Oracles
• Fast and Simple PCA via Convex Optimization
• On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points
• Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Information
• Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
• SDCA without Duality, Regularization, and Individual Convexity
• Stochastic Variance-Reduced Cubic Regularized Newton Method
• Sharp Analysis for Nonconvex SGD Escaping from Saddle Points
• Analysis of Krylov Subspace Solutions of Regularized Nonconvex Quadratic Problems
• Convergence Rate Analysis of a Stochastic Trust Region Method via Submartingales
• Finding Local Minima via Stochastic Nested Variance Reduction
• Adaptive Stochastic Variance Reduction for Subsampled Newton Method with Cubic Regularization
• A Stochastic Trust Region Method for Non-convex Minimization
• Saving Gradient and Negative Curvature Computations: Finding Local Minima More Efficiently
• Third-order Smoothness Helps: Even Faster Stochastic Optimization Algorithms for Finding Local Minima
• Sample Efficient Stochastic Variance-Reduced Cubic Regularization Method

Cited by in corpus (9)

• On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points
• Sharp Analysis for Nonconvex SGD Escaping from Saddle Points
• Stochastic Newton and Cubic Newton Methods with Simple Local Linear-Quadratic Rates
• A Hybrid Stochastic Optimization Framework for Stochastic Composite Nonconvex Optimization
• Accelerating Mini-batch SARAH by Step Size Rules
• On the Oracle Complexity of Higher-Order Smooth Non-Convex Finite-Sum Optimization
• Faster Stochastic Quasi-Newton Methods
• Escaping Saddle Points with Compressed SGD
• GO Hessian for Expectation-Based Objectives