# Cubic regularized subspace Newton for non-convex optimization

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 39 references that are in the map.
- First posted on arXiv 24 Jun 2024.

## Builds on (most cited first, 22 of 22)

- [Sub-sampled Cubic Regularization for Non-convex Optimization](https://mlsanity.com/paper/1705.05933/) (2017)
- [Stochastic Nested Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1806.07811/) (2018)
- [Stochastic Cubic Regularization for Fast Nonconvex Optimization](https://mlsanity.com/paper/1711.02838/) (2017)
- [Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Information](https://mlsanity.com/paper/1708.07164/) (2017)
- [RSN: Randomized Subspace Newton](https://mlsanity.com/paper/1905.10874/) (2019)
- [Stochastic Subspace Cubic Newton Method](https://mlsanity.com/paper/2002.09526/) (2020)
- [Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition](https://mlsanity.com/paper/2208.09585/) (2022)
- [Gradient Descent Finds the Cubic-Regularized Non-Convex Newton Step](https://mlsanity.com/paper/1612.00547/) (2016)
- [Second-order optimization with lazy Hessians](https://mlsanity.com/paper/2212.00781/) (2022)
- [Adaptive Newton Sketch: Linear-time Optimization with Quadratic Convergence and Effective Hessian Dimensionality](https://mlsanity.com/paper/2105.07291/) (2021)
- [Inexact Non-Convex Newton-Type Methods](https://mlsanity.com/paper/1802.06925/) (2018)
- [Stochastic Subspace Descent](https://mlsanity.com/paper/1904.01145/) (2019)
- [Inexact Tensor Methods and Their Application to Stochastic Convex Optimization](https://mlsanity.com/paper/2012.15636/) (2020)
- [First and zeroth-order implementations of the regularized Newton method with lazy approximated Hessians](https://mlsanity.com/paper/2309.02412/) (2023)
- [Efficient random coordinate descent algorithms for large-scale structured nonconvex optimization](https://mlsanity.com/paper/1305.4027/) (2013)
- [Theoretical analysis of the randomized subspace regularized Newton method for non-convex optimization](https://mlsanity.com/paper/2209.04170/) (2022)
- [A Note on Inexact Condition for Cubic Regularized Newton's Method](https://mlsanity.com/paper/1808.07384/) (2018)
- [Randomised subspace methods for non-convex optimization, with applications to nonlinear least-squares](https://mlsanity.com/paper/2211.09873/) (2022)
- [Inexact Tensor Methods with Dynamic Accuracies](https://mlsanity.com/paper/2002.09403/) (2020)
- [Sketch-and-Project Meets Newton Method: Global mathcal O(k-2) Convergence with Low-Rank Updates](https://mlsanity.com/paper/2305.13082/) (2023)
- [Adaptive Quasi-Newton and Anderson Acceleration Framework with Explicit Global (Accelerated) Convergence Rates](https://mlsanity.com/paper/2305.19179/) (2023)
- [Krylov Cubic Regularized Newton: A Subspace Second-Order Method with Dimension-Free Convergence Rate](https://mlsanity.com/paper/2401.03058/) (2024)

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

- [Improving Stochastic Cubic Newton with Momentum](https://mlsanity.com/paper/2410.19644/) (2024)
- [Gradient-Normalized Smoothness for Optimization with Approximate Hessians](https://mlsanity.com/paper/2506.13710/) (2025)
- [Blockwise Stabilized Adaptive Cubic Regularization with Subsolvers via Recurrence](https://mlsanity.com/paper/2608.22129/) (2026)

## Abstract (arXiv)

This paper addresses the optimization problem of minimizing non-convex continuous functions, which is relevant in the context of high-dimensional machine learning applications characterized by over-parametrization. We analyze a randomized coordinate second-order method named SSCN which can be interpreted as applying cubic regularization in random subspaces. This approach effectively reduces the computational complexity associated with utilizing second-order information, rendering it applicable in higher-dimensional scenarios. Theoretically, we establish convergence guarantees for non-convex functions, with interpolating rates for arbitrary subspace sizes and allowing inexact curvature estimation. When increasing subspace size, our complexity matches O(ε-3/2) of the cubic regularization (CR) rate. Additionally, we propose an adaptive sampling scheme ensuring exact convergence rate of O(ε-3/2, ε-3) to a second-order stationary point, even without sampling all coordinates. Experimental results demonstrate substantial speed-ups achieved by SSCN compared to conventional first-order methods.