# Stochastic Variance-Reduced Cubic Regularized Newton Method

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Feb 2018.

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

- [Knowledge Removal in Sampling-based Bayesian Inference](https://mlsanity.com/paper/2203.12964/) (2022)
- [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)
- [Distributed Learning Systems with First-order Methods](https://mlsanity.com/paper/2104.05245/) (2021)
- [Escape saddle points by a simple gradient-descent based algorithm](https://mlsanity.com/paper/2111.14069/) (2021)
- [Escaping Saddle Points in Distributed Newton's Method with Communication Efficiency and Byzantine Resilience](https://mlsanity.com/paper/2103.09424/) (2021)
- [A Momentum Accelerated Adaptive Cubic Regularization Method for Nonconvex Optimization](https://mlsanity.com/paper/2210.05987/) (2022)
- [A Stochastic Quasi-Newton Method for Non-convex Optimization with Non-uniform Smoothness](https://mlsanity.com/paper/2403.15244/) (2024)
- [Sharp First-Order Lower Bounds for Higher-Order Smooth Nonconvex Optimization](https://mlsanity.com/paper/2606.05438/) (2026)
- [Escaping Saddle Points with Stochastically Controlled Stochastic Gradient Methods](https://mlsanity.com/paper/2103.04413/) (2021)

## Abstract (arXiv)

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 (ε,√ε)-approximately local minimum within tildeO(n4/5/ε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.