# Sub-sampled Cubic Regularization for Non-convex Optimization

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

## Key facts

- Cited by 63 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 May 2017.

## Built on by (most cited first, 30 of 63)

- [Friendly Sharpness-Aware Minimization](https://mlsanity.com/paper/2403.12350/) (2024)
- [Generative Sliced MMD Flows with Riesz Kernels](https://mlsanity.com/paper/2305.11463/) (2023)
- [Global Neighbor Sampling for Mixed CPU-GPU Training on Giant Graphs](https://mlsanity.com/paper/2106.06150/) (2021)
- [Stochastic Second-Order Methods Improve Best-Known Sample Complexity of SGD for Gradient-Dominated Function](https://mlsanity.com/paper/2205.12856/) (2022)
- [Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization](https://mlsanity.com/paper/2408.11974/) (2024)
- [Second-order optimization with lazy Hessians](https://mlsanity.com/paper/2212.00781/) (2022)
- [Scalable Primal-Dual Actor-Critic Method for Safe Multi-Agent RL with General Utilities](https://mlsanity.com/paper/2305.17568/) (2023)
- [Kernel-based Unsupervised Embedding Alignment for Enhanced Visual Representation in Vision-language Models](https://mlsanity.com/paper/2506.02557/) (2025)
- [SP2: A Second Order Stochastic Polyak Method](https://mlsanity.com/paper/2207.08171/) (2022)
- [Finding Second-Order Stationary Points in Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2110.04814/) (2021)
- [Unified Convergence Theory of Stochastic and Variance-Reduced Cubic Newton Methods](https://mlsanity.com/paper/2302.11962/) (2023)
- [Replicable Learning of Large-Margin Halfspaces](https://mlsanity.com/paper/2402.13857/) (2024)
- [Do Vendi Scores Converge with Finite Samples? Truncated Vendi Score for Finite-Sample Convergence Guarantees](https://mlsanity.com/paper/2410.21719/) (2024)
- [Accumulation of Sub-Sampling Matrices with Applications to Statistical Computation](https://mlsanity.com/paper/2103.04031/) (2021)
- [A safe exploration approach to constrained Markov decision processes](https://mlsanity.com/paper/2312.00561/) (2023)
- [Understanding Retrieval-Augmented Task Adaptation for Vision-Language Models](https://mlsanity.com/paper/2405.01468/) (2024)
- [Towards an Explainable Comparison and Alignment of Feature Embeddings](https://mlsanity.com/paper/2506.06231/) (2025)
- [Escaping Saddle Points Faster with Stochastic Momentum](https://mlsanity.com/paper/2106.02985/) (2021)
- [Pseudo-Spherical Contrastive Divergence](https://mlsanity.com/paper/2111.00780/) (2021)
- [Time-Uniform Confidence Spheres for Means of Random Vectors](https://mlsanity.com/paper/2311.08168/) (2023)
- [Improving Stochastic Cubic Newton with Momentum](https://mlsanity.com/paper/2410.19644/) (2024)
- [MARL with General Utilities via Decentralized Shadow Reward Actor-Critic](https://mlsanity.com/paper/2106.00543/) (2021)
- [A Cubic Regularization Approach for Finding Local Minimax Points in Nonconvex Minimax Optimization](https://mlsanity.com/paper/2110.07098/) (2021)
- [Differentially Private Optimization for Smooth Nonconvex ERM](https://mlsanity.com/paper/2302.04972/) (2023)
- [Fair Streaming Principal Component Analysis: Statistical and Algorithmic Viewpoint](https://mlsanity.com/paper/2310.18593/) (2023)
- [SAPPHIRE: Preconditioned Stochastic Variance Reduction for Faster Large-Scale Statistical Learning](https://mlsanity.com/paper/2501.15941/) (2025)
- [ACT as Human: Multimodal Large Language Model Data Annotation with Critical Thinking](https://mlsanity.com/paper/2511.09833/) (2025)
- [Escaping Saddle Points in Distributed Newton's Method with Communication Efficiency and Byzantine Resilience](https://mlsanity.com/paper/2103.09424/) (2021)
- [Cubic regularized subspace Newton for non-convex optimization](https://mlsanity.com/paper/2406.16666/) (2024)
- [Concept learning of parameterized quantum models from limited measurements](https://mlsanity.com/paper/2408.05116/) (2024)

## Abstract (arXiv)

We consider the minimization of non-convex functions that typically arise in machine learning. Specifically, we focus our attention on a variant of trust region methods known as cubic regularization. This approach is particularly attractive because it escapes strict saddle points and it provides stronger convergence guarantees than first- and second-order as well as classical trust region methods. However, it suffers from a high computational complexity that makes it impractical for large-scale learning. Here, we propose a novel method that uses sub-sampling to lower this computational cost. By the use of concentration inequalities we provide a sampling scheme that gives sufficiently accurate gradient and Hessian approximations to retain the strong global and local convergence guarantees of cubically regularized methods. To the best of our knowledge this is the first work that gives global convergence guarantees for a sub-sampled variant of cubic regularization on non-convex functions. Furthermore, we provide experimental results supporting our theory.