# RSN: Randomized Subspace Newton

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

## Key facts

- Cited by 34 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 May 2019.

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

- [Regularized Newton Method with Global O(1/k2) Convergence](https://mlsanity.com/paper/2112.02089/) (2021)
- [Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition](https://mlsanity.com/paper/2208.09585/) (2022)
- [Adaptive Newton Sketch: Linear-time Optimization with Quadratic Convergence and Effective Hessian Dimensionality](https://mlsanity.com/paper/2105.07291/) (2021)
- [Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence](https://mlsanity.com/paper/2204.09266/) (2022)
- [Faster Differentially Private Convex Optimization via Second-Order Methods](https://mlsanity.com/paper/2305.13209/) (2023)
- [Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learning](https://mlsanity.com/paper/2406.11151/) (2024)
- [SketchySGD: Reliable Stochastic Optimization via Randomized Curvature Estimates](https://mlsanity.com/paper/2211.08597/) (2022)
- [Covering Number of Real Algebraic Varieties and Beyond: Improved Bounds and Applications](https://mlsanity.com/paper/2311.05116/) (2023)
- [Curvature-Aware Derivative-Free Optimization](https://mlsanity.com/paper/2109.13391/) (2021)
- [Stochastic Anderson Mixing for Nonconvex Stochastic Optimization](https://mlsanity.com/paper/2110.01543/) (2021)
- [Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems](https://mlsanity.com/paper/2405.05818/) (2024)
- [Global optimization using random embeddings](https://mlsanity.com/paper/2107.12102/) (2021)
- [Constrained Optimization via Exact Augmented Lagrangian and Randomized Iterative Sketching](https://mlsanity.com/paper/2305.18379/) (2023)
- [SAPPHIRE: Preconditioned Stochastic Variance Reduction for Faster Large-Scale Statistical Learning](https://mlsanity.com/paper/2501.15941/) (2025)
- [Sketch-and-Project Meets Newton Method: Global mathcal O(k-2) Convergence with Low-Rank Updates](https://mlsanity.com/paper/2305.13082/) (2023)
- [Krylov Cubic Regularized Newton: A Subspace Second-Order Method with Dimension-Free Convergence Rate](https://mlsanity.com/paper/2401.03058/) (2024)
- [Online estimation of the inverse of the Hessian for stochastic optimization with application to universal stochastic Newton algorithms](https://mlsanity.com/paper/2401.10923/) (2024)
- [Regularized Gauss-Newton for Optimizing Overparameterized Neural Networks](https://mlsanity.com/paper/2404.14875/) (2024)
- [Cubic regularized subspace Newton for non-convex optimization](https://mlsanity.com/paper/2406.16666/) (2024)
- [Turbocharging Gaussian Process Inference with Approximate Sketch-and-Project](https://mlsanity.com/paper/2505.13723/) (2025)
- [Gradient-Normalized Smoothness for Optimization with Approximate Hessians](https://mlsanity.com/paper/2506.13710/) (2025)
- [A Randomised Subspace Gauss-Newton Method for Nonlinear Least-Squares](https://mlsanity.com/paper/2211.05727/) (2022)
- [Subspace-based Approximate Hessian Method for Zeroth-Order Optimization](https://mlsanity.com/paper/2507.06125/) (2025)
- [Learning-Augmented Sketches for Hessians](https://mlsanity.com/paper/2102.12317/) (2021)
- [Augmented Newton Method for Optimization: Global Linear Rate and Momentum Interpretation](https://mlsanity.com/paper/2205.11033/) (2022)
- [Gathering and Exploiting Higher-Order Information when Training Large Structured Models](https://mlsanity.com/paper/2312.03885/) (2023)
- [Newton Meets Marchenko-Pastur: Massively Parallel Second-Order Optimization with Hessian Sketching and Debiasing](https://mlsanity.com/paper/2410.01374/) (2024)
- [ALS: Augmented Lagrangian Sketching Methods for Linear Systems](https://mlsanity.com/paper/2208.06152/) (2022)
- [Limited-Memory Greedy Quasi-Newton Method with Non-asymptotic Superlinear Convergence Rate](https://mlsanity.com/paper/2306.15444/) (2023)
- [Subspace Langevin Monte Carlo](https://mlsanity.com/paper/2412.13928/) (2024)

## Abstract (arXiv)

We develop a randomized Newton method capable of solving learning problems with huge dimensional feature spaces, which is a common setting in applications such as medical imaging, genomics and seismology. Our method leverages randomized sketching in a new way, by finding the Newton direction constrained to the space spanned by a random sketch. We develop a simple global linear convergence theory that holds for practically all sketching techniques, which gives the practitioners the freedom to design custom sketching approaches suitable for particular applications. We perform numerical experiments which demonstrate the efficiency of our method as compared to accelerated gradient descent and the full Newton method. Our method can be seen as a refinement and randomized extension of the results of Karimireddy, Stich, and Jaggi (2019).