# Stochastic Recursive Variance-Reduced Cubic Regularization Methods

arXiv: https://arxiv.org/abs/1901.11518 · HTML: https://mlsanity.com/paper/1901.11518/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Jan 2019.

## Built on by (most cited first, 12 of 12)

- [Stochastic Second-Order Methods Improve Best-Known Sample Complexity of SGD for Gradient-Dominated Function](https://mlsanity.com/paper/2205.12856/) (2022)
- [Revisiting Gradient Normalization and Clipping for Nonconvex SGD under Heavy-Tailed Noise: Necessity, Sufficiency, and Acceleration](https://mlsanity.com/paper/2410.16561/) (2024)
- [How to escape sharp minima with random perturbations](https://mlsanity.com/paper/2305.15659/) (2023)
- [Escape saddle points by a simple gradient-descent based algorithm](https://mlsanity.com/paper/2111.14069/) (2021)
- [On the Oracle Complexity of Higher-Order Smooth Non-Convex Finite-Sum Optimization](https://mlsanity.com/paper/2103.05138/) (2021)
- [Escaping Saddle Points with Compressed SGD](https://mlsanity.com/paper/2105.10090/) (2021)
- [Efficiently Escaping Saddle Points for Policy Optimization](https://mlsanity.com/paper/2311.08914/) (2023)
- [Noise is All You Need: Private Second-Order Convergence of Noisy SGD](https://mlsanity.com/paper/2410.06878/) (2024)
- [AdaCubic: An Adaptive Cubic Regularization Optimizer for Deep Learning](https://mlsanity.com/paper/2604.09437/) (2026)
- [Sharp First-Order Lower Bounds for Higher-Order Smooth Nonconvex Optimization](https://mlsanity.com/paper/2606.05438/) (2026)
- [HOUDINI: Escaping from Moderately Constrained Saddles](https://mlsanity.com/paper/2205.13753/) (2022)
- [Faster Riemannian Newton-type Optimization by Subsampling and Cubic Regularization](https://mlsanity.com/paper/2302.11076/) (2023)

## Abstract (arXiv)

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 (ε, √ε)-approximate local minimum, and outperforms the state-of-the-art SVRC algorithms. Built upon SRVRC, we further propose a Hessian-free SRVRC algorithm, namely SRVRCfree, which only requires stochastic gradient and Hessian-vector product computations, and achieves tilde O(dnε-2 land dε-3) runtime complexity, where n is the number of component functions in the finite-sum structure, d is the problem dimension, and ε is the optimization precision. This outperforms the best-known runtime complexity tilde O(dε-3.5) achieved by stochastic cubic regularization algorithm proposed in Tripuraneni et al. 2018.