mlsanityData to 14 Oct 2026

RSN: Randomized Subspace Newton

arXiv 1905.10874 ↗First posted 26 May 2019math.OCcited by 34

Not on the map. Why?

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).

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 6; 2022: 6; 2023: 6; 2024: 8; 2025: 7; 2026: 1.

34 papers.

Sort:

  1. 2021Regularized Newton Method with Global O(1/k2) Convergencecited by 22
  2. 2022Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decompositioncited by 19
  3. 2021Adaptive Newton Sketch: Linear-time Optimization with Quadratic Convergence and Effective Hessian Dimensionalitycited by 14
  4. 2022Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergencecited by 14
  5. 2023Faster Differentially Private Convex Optimization via Second-Order Methodscited by 13
  6. 2024Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learningcited by 11
  7. 2022SketchySGD: Reliable Stochastic Optimization via Randomized Curvature Estimatescited by 8
  8. 2023Covering Number of Real Algebraic Varieties and Beyond: Improved Bounds and Applicationscited by 8
  9. 2021Curvature-Aware Derivative-Free Optimizationcited by 7
  10. 2021Stochastic Anderson Mixing for Nonconvex Stochastic Optimizationcited by 7
  11. 2024Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systemscited by 7
  12. 2021Global optimization using random embeddingscited by 6
22 more
  1. 2023Constrained Optimization via Exact Augmented Lagrangian and Randomized Iterative Sketchingcited by 5
  2. 2025SAPPHIRE: Preconditioned Stochastic Variance Reduction for Faster Large-Scale Statistical Learningcited by 4
  3. 2023Sketch-and-Project Meets Newton Method: Global mathcal O(k-2) Convergence with Low-Rank Updatescited by 3
  4. 2024Krylov Cubic Regularized Newton: A Subspace Second-Order Method with Dimension-Free Convergence Ratecited by 3
  5. 2024Online estimation of the inverse of the Hessian for stochastic optimization with application to universal stochastic Newton algorithmscited by 3
  6. 2024Regularized Gauss-Newton for Optimizing Overparameterized Neural Networkscited by 3
  7. 2024Cubic regularized subspace Newton for non-convex optimizationcited by 3
  8. 2025Turbocharging Gaussian Process Inference with Approximate Sketch-and-Projectcited by 3
  9. 2025Gradient-Normalized Smoothness for Optimization with Approximate Hessianscited by 3
  10. 2022A Randomised Subspace Gauss-Newton Method for Nonlinear Least-Squarescited by 2
  11. 2025Subspace-based Approximate Hessian Method for Zeroth-Order Optimizationcited by 2
  12. 2021Learning-Augmented Sketches for Hessianscited by 1
  13. 2022Augmented Newton Method for Optimization: Global Linear Rate and Momentum Interpretationcited by 1
  14. 2023Gathering and Exploiting Higher-Order Information when Training Large Structured Modelscited by 1
  15. 2024Newton Meets Marchenko-Pastur: Massively Parallel Second-Order Optimization with Hessian Sketching and Debiasingcited by 1
  16. 2022ALS: Augmented Lagrangian Sketching Methods for Linear Systemscited by 0
  17. 2023Limited-Memory Greedy Quasi-Newton Method with Non-asymptotic Superlinear Convergence Ratecited by 0
  18. 2024Subspace Langevin Monte Carlocited by 0
  19. 2025What is a Sketch-and-Precondition Derivation for Low-Rank Approximation? Inverse Power Error or Inverse Power Estimation?cited by 0
  20. 2025Online Statistical Inference of Constrained Stochastic Optimization via Random Scalingcited by 0
  21. 2025Simple Stepsize for Quasi-Newton Methods with Global Convergence Guaranteescited by 0
  22. 2026BROS: Bias-Corrected Randomized Subspaces for Memory-Efficient Single-Loop Bilevel Optimizationcited by 0