# Theoretical analysis of the randomized subspace regularized Newton method for non-convex optimization

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Sep 2022.

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

- [Constrained Optimization via Exact Augmented Lagrangian and Randomized Iterative Sketching](https://mlsanity.com/paper/2305.18379/) (2023)
- [Natural GaLore: Accelerating GaLore for memory-efficient LLM Training and Fine-tuning](https://mlsanity.com/paper/2410.16029/) (2024)
- [Cubic regularized subspace Newton for non-convex optimization](https://mlsanity.com/paper/2406.16666/) (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)

While there already exist randomized subspace Newton methods that restrict the search direction to a random subspace for a convex function, we propose a randomized subspace regularized Newton method for a non-convex function {and more generally we investigate thoroughly the local convergence rate of the randomized subspace Newton method}. In our proposed algorithm using a modified Hessian of the function restricted to some random subspace, with high probability, the function value decreases even when the objective function is non-convex. In this paper, we show that our method has global convergence under appropriate assumptions and its convergence rate is the same as that of the full regularized Newton method. %We also prove that Furthermore, we can obtain a local linear convergence rate under some additional assumptions, and prove that this rate is the best we can hope, in general, when using random subspace. We furthermore prove that if the Hessian at the local optimum is rank defficient then superlienar convergence holds.