mlsanityData to 7 Oct 2026

Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learning

arXiv 2406.11151 ↗First posted 17 Jun 2024cs.LG cs.NA math.NAcited by 11

Not on the map. Why?

Abstract (arXiv)

Large matrices arise in many machine learning and data analysis applications, including as representations of datasets, graphs, model weights, and first and second-order derivatives. Randomized Numerical Linear Algebra (RandNLA) is an area which uses randomness to develop improved algorithms for ubiquitous matrix problems. The area has reached a certain level of maturity; but recent hardware trends, efforts to incorporate RandNLA algorithms into core numerical libraries, and advances in machine learning, statistics, and random matrix theory, have lead to new theoretical and practical challenges. This article provides a self-contained overview of RandNLA, in light of these developments.

Key facts. Cited by 11 papers in the map (data through 7 Oct 2026). Builds on 98 of its 181 references that are in the map. First posted on arXiv 17 Jun 2024.

Builds on

98 of 181 references.

References · 98

  1. 2021A Survey of Quantization Methods for Efficient Neural Network Inferencecited by 798
  2. 2015An Introduction to Matrix Concentration Inequalitiescited by 391
  3. 2019PyHessian: Neural Networks Through the Lens of the Hessiancited by 291
  4. 2014Sketching as a Tool for Numerical Linear Algebracited by 285
  5. 2018Implicit Self-Regularization in Deep Neural Networks: Evidence from Random Matrix Theory and Implications for Learningcited by 211
  6. 2020ADAHESSIAN: An Adaptive Second Order Optimizer for Machine Learningcited by 201
  7. 2020FetchSGD: Communication-Efficient Federated Learning with Sketchingcited by 178
  8. 2013Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithmcited by 132
  9. 2024AI and Memory Wallcited by 89
  10. 2017FALKON: An Optimal Large Scale Kernel Methodcited by 82
  11. 2013Revisiting the Nystrom Method for Improved Large-Scale Machine Learningcited by 76
  12. 2015Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergencecited by 72
38 more
  1. 2015Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decompositioncited by 63
  2. 2019Rates of Convergence for Sparse Variational Gaussian Process Regressioncited by 62
  3. 2020Hutch++: Optimal Stochastic Trace Estimationcited by 62
  4. 2016Faster Kernel Ridge Regression Using Sketching and Preconditioningcited by 43
  5. 2019Learning-Based Low-Rank Approximationscited by 41
  6. 2020Determinantal Point Processes in Randomized Numerical Linear Algebracited by 41
  7. 2018On Fast Leverage Score Sampling and Optimal Learningcited by 40
  8. 2013A Statistical Perspective on Algorithmic Leveragingcited by 38
  9. 2016Exact and Inexact Subsampled Newton Methods for Optimizationcited by 38
  10. 2023Randomized Numerical Linear Algebra : A Perspective on the Field With an Eye to Softwarecited by 38
  11. 2015Optimal approximate matrix product in terms of stable rankcited by 37
  12. 2017Active Regression via Linear-Sample Sparsificationcited by 36
  13. 2019Exact expressions for double descent and implicit regularization via surrogate random designcited by 35
  14. 2014Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squarescited by 34
  15. 2019RSN: Randomized Subspace Newtoncited by 34
  16. 2015Convergence rates of sub-sampled Newton methodscited by 32
  17. 2018SEGA: Variance Reduction via Gradient Sketchingcited by 29
  18. 2019The Implicit Regularization of Ordinary Least Squares Ensemblescited by 25
  19. 2016Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh Distributions and Determinantal Point Processescited by 24
  20. 2019Stochastic Newton and Cubic Newton Methods with Simple Local Linear-Quadratic Ratescited by 24
  21. 2021Query Complexity of Least Absolute Deviation Regression via Robust Uniform Convergencecited by 24
  22. 2021Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Updatecited by 23
  23. 2014A Statistical Perspective on Randomized Sketching for Ordinary Least-Squarescited by 21
  24. 2016Sub-sampled Newton Methods with Non-uniform Samplingcited by 21
  25. 2020Stochastic Subspace Cubic Newton Methodcited by 21
  26. 2015Fast and Guaranteed Tensor Decomposition via Sketchingcited by 19
  27. 2017Lectures on Randomized Numerical Linear Algebracited by 19
  28. 2018Near Optimal Linear Algebra in the Online and Sliding Window Modelscited by 19
  29. 2019Exact sampling of determinantal point processes with sublinear time preprocessingcited by 19
  30. 2020Sparse sketches with small inversion biascited by 19
  31. 2017Sublinear Time Low-Rank Approximation of Positive Semidefinite Matricescited by 18
  32. 2017An Investigation of Newton-Sketch and Subsampled Newton Methodscited by 18
  33. 2020Sampling from a k-DPP without looking at all itemscited by 17
  34. 2022Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decompositioncited by 17
  35. 2019Distributed estimation of the inverse Hessian by determinantal averagingcited by 16
  36. 2016Solving Ridge Regression using Sketched Preconditioned SVRGcited by 15
  37. 2018Leveraged volume sampling for linear regressioncited by 15
  38. 2013Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systemscited by 14

50 most cited of 98 All 98 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 7; 2026: 3.

11 papers.

  1. 2025Position: Curvature Matrices Should Be Democratized via Linear Operatorscited by 9
  2. 2025Randomized Kaczmarz Methods with Beyond-Krylov Convergencecited by 7
  3. 2024Optimal Oblivious Subspace Embeddings with Near-optimal Sparsitycited by 4
  4. 2026Last-Iterate Convergence of Randomized Kaczmarz and SGD with Greedy Step Sizecited by 2
  5. 2025Fundamental Bias in Inverting Random Sampling Matrices with Application to Sub-sampled Newtoncited by 1
  6. 2025Accelerating Natural Gradient Descent for PINNs with Randomized Numerical Linear Algebracited by 1
  7. 2025Importance Sampling for Nonlinear Modelscited by 0
  8. 2025Sequential Least-Squares Estimators with Fast Randomized Sketching for Linear Statistical Modelscited by 0
  9. 2025Sketching Low-Rank Plus Diagonal Matricescited by 0
  10. 2026Low-Rank Compression of Pretrained Models via Randomized Subspace Iterationcited by 0
  11. 2026Accelerating Power Method with Fast Sketching for Stronger Low-Rank Approximationcited by 0