mlsanityData to 14 Oct 2026

Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems

arXiv 2405.05818 ↗First posted 9 May 2024cs.DS cs.LG cs.NAcited by 7

Not on the map. Why?

Abstract (arXiv)

Despite being a key bottleneck in many machine learning tasks, the cost of solving large linear systems has proven challenging to quantify due to problem-dependent quantities such as condition numbers. To tackle this, we consider a fine-grained notion of complexity for solving linear systems, which is motivated by applications where the data exhibits low-dimensional structure, including spiked covariance models and kernel machines, and when the linear system is explicitly regularized, such as ridge regression. Concretely, let kappaℓ be the ratio between the ℓth largest and the smallest singular value of n× n matrix A. We give a stochastic algorithm based on the Sketch-and-Project paradigm, that solves the linear system Ax = b, that is, finds barx such that |Abarx - b| ≤ ε |b|, in time bar O(kappaℓ· n2log 1/ε), for any ℓ = O(n0.729). This is a direct improvement over preconditioned conjugate gradient, and it provides a stronger separation between stochastic linear solvers and algorithms accessing A only through matrix-vector products. Our main technical contribution is the new analysis of the first and second moments of the random projection matrix that arises in Sketch-and-Project.

Key facts. Cited by 7 papers in the map (data through 14 Oct 2026). Builds on 44 of its 114 references that are in the map. First posted on arXiv 9 May 2024.

Builds on

44 of 114 references.

References · 44

  1. 2014Sketching as a Tool for Numerical Linear Algebracited by 288
  2. 2016Katyusha: The First Direct Acceleration of Stochastic Gradient Methodscited by 135
  3. 2013Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithmcited by 133
  4. 2016Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regressioncited by 64
  5. 2019Rates of Convergence for Sparse Variational Gaussian Process Regressioncited by 63
  6. 2015A Universal Catalyst for First-Order Optimizationcited by 54
  7. 2014Dimensionality Reduction for k-Means Clustering and Low Rank Approximationcited by 48
  8. 2015Input Sparsity Time Low-Rank Approximation via Ridge Leverage Score Samplingcited by 46
  9. 2017Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Informationcited by 41
  10. 2020Determinantal Point Processes in Randomized Numerical Linear Algebracited by 41
  11. 2019RSN: Randomized Subspace Newtoncited by 34
  12. 2023New Bounds for Matrix Multiplication: from Alpha to Omegacited by 34
32 more
  1. 2015Convergence rates of sub-sampled Newton methodscited by 33
  2. 2018Optimality and Sub-optimality of PCA I: Spiked Random Matrix Modelscited by 33
  3. 2018SEGA: Variance Reduction via Gradient Sketchingcited by 29
  4. 2021Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Updatecited by 23
  5. 2015Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimizationcited by 21
  6. 2015Universality laws for randomized dimension reduction, with applicationscited by 21
  7. 2020Stochastic Subspace Cubic Newton Methodcited by 21
  8. 2020Sparse sketches with small inversion biascited by 19
  9. 2022Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decompositioncited by 19
  10. 2017Stochastic Reformulations of Linear Systems: Algorithms and Convergence Theorycited by 16
  11. 2017Stability of the Lanczos Method for Matrix Function Approximationcited by 16
  12. 2016Solving Ridge Regression using Sketched Preconditioned SVRGcited by 15
  13. 2021A Continuized View on Nesterov Acceleration for Stochastic Gradient Descent and Randomized Gossipcited by 15
  14. 2013Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systemscited by 14
  15. 2020Sketched Newton-Raphsoncited by 14
  16. 2022On the fast convergence of minibatch heavy ball momentumcited by 13
  17. 2013An Accelerated Randomized Kaczmarz Algorithmcited by 12
  18. 2019Convergence Analysis of Block Coordinate Algorithms with Determinantal Samplingcited by 12
  19. 2023Solving Dense Linear Systems Faster Than via Preconditioningcited by 12
  20. 2018Accelerated Stochastic Matrix Inversion: General Theory and Speeding up BFGS Rules for Faster Second-Order Optimizationcited by 11
  21. 2023Optimal Embedding Dimension for Sparse Subspace Embeddingscited by 11
  22. 2020Solving Sparse Linear Systems Faster than Matrix Multiplicationcited by 10
  23. 2019The gradient complexity of linear regressioncited by 9
  24. 2022Asymptotics of the Sketched Pseudoinversecited by 9
  25. 2015Stochastic Dual Ascent for Solving Linear Systemscited by 8
  26. 2019Minimax experimental design: Bridging the gap between statistical and worst-case approaches to least squares regressioncited by 8
  27. 2019A Randomized Coordinate Descent Method with Volume Samplingcited by 8
  28. 2015Sparsified Cholesky and Multigrid Solvers for Connection Laplacianscited by 7
  29. 2017Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardnesscited by 5
  30. 2021textttRidgeSketch: A Fast sketching based solver for large scale ridge regressioncited by 4
  31. 2017Nesterov's Acceleration For Approximate Newtoncited by 3
  32. 2024Randomized Kaczmarz with geometrically smoothed momentumcited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 1; 2025: 4; 2026: 2.

7 papers.

  1. 2024Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learningcited by 11
  2. 2025Turbocharging Gaussian Process Inference with Approximate Sketch-and-Projectcited by 3
  3. 2025Worth Their Weight: Randomized and Regularized Block Kaczmarz Algorithms without Preprocessingcited by 2
  4. 2025Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structurecited by 2
  5. 2025A Sketch-and-Project Analysis of Subsampled Natural Gradient Algorithmscited by 2
  6. 2026Last-Iterate Convergence of Randomized Kaczmarz and SGD with Greedy Step Sizecited by 2
  7. 2026Perfect Parallelization in Mini-Batch SGD with Classical Momentum Accelerationcited by 0