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

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

## 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 (most cited first, 30 of 44)

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Katyusha: The First Direct Acceleration of Stochastic Gradient Methods](https://mlsanity.com/paper/1603.05953/) (2016)
- [Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm](https://mlsanity.com/paper/1310.5715/) (2013)
- [Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regression](https://mlsanity.com/paper/1602.05419/) (2016)
- [Rates of Convergence for Sparse Variational Gaussian Process Regression](https://mlsanity.com/paper/1903.03571/) (2019)
- [A Universal Catalyst for First-Order Optimization](https://mlsanity.com/paper/1506.02186/) (2015)
- [Dimensionality Reduction for k-Means Clustering and Low Rank Approximation](https://mlsanity.com/paper/1410.6801/) (2014)
- [Input Sparsity Time Low-Rank Approximation via Ridge Leverage Score Sampling](https://mlsanity.com/paper/1511.07263/) (2015)
- [Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Information](https://mlsanity.com/paper/1708.07164/) (2017)
- [Determinantal Point Processes in Randomized Numerical Linear Algebra](https://mlsanity.com/paper/2005.03185/) (2020)
- [RSN: Randomized Subspace Newton](https://mlsanity.com/paper/1905.10874/) (2019)
- [New Bounds for Matrix Multiplication: from Alpha to Omega](https://mlsanity.com/paper/2307.07970/) (2023)
- [Convergence rates of sub-sampled Newton methods](https://mlsanity.com/paper/1508.02810/) (2015)
- [Optimality and Sub-optimality of PCA I: Spiked Random Matrix Models](https://mlsanity.com/paper/1807.00891/) (2018)
- [SEGA: Variance Reduction via Gradient Sketching](https://mlsanity.com/paper/1809.03054/) (2018)
- [Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update](https://mlsanity.com/paper/2107.07480/) (2021)
- [Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization](https://mlsanity.com/paper/1506.07512/) (2015)
- [Universality laws for randomized dimension reduction, with applications](https://mlsanity.com/paper/1511.09433/) (2015)
- [Stochastic Subspace Cubic Newton Method](https://mlsanity.com/paper/2002.09526/) (2020)
- [Sparse sketches with small inversion bias](https://mlsanity.com/paper/2011.10695/) (2020)
- [Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition](https://mlsanity.com/paper/2208.09585/) (2022)
- [Stochastic Reformulations of Linear Systems: Algorithms and Convergence Theory](https://mlsanity.com/paper/1706.01108/) (2017)
- [Stability of the Lanczos Method for Matrix Function Approximation](https://mlsanity.com/paper/1708.07788/) (2017)
- [Solving Ridge Regression using Sketched Preconditioned SVRG](https://mlsanity.com/paper/1602.02350/) (2016)
- [A Continuized View on Nesterov Acceleration for Stochastic Gradient Descent and Randomized Gossip](https://mlsanity.com/paper/2106.07644/) (2021)
- [Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systems](https://mlsanity.com/paper/1305.1922/) (2013)
- [Sketched Newton-Raphson](https://mlsanity.com/paper/2006.12120/) (2020)
- [On the fast convergence of minibatch heavy ball momentum](https://mlsanity.com/paper/2206.07553/) (2022)
- [An Accelerated Randomized Kaczmarz Algorithm](https://mlsanity.com/paper/1310.2887/) (2013)
- [Convergence Analysis of Block Coordinate Algorithms with Determinantal Sampling](https://mlsanity.com/paper/1910.11561/) (2019)

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

- [Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learning](https://mlsanity.com/paper/2406.11151/) (2024)
- [Turbocharging Gaussian Process Inference with Approximate Sketch-and-Project](https://mlsanity.com/paper/2505.13723/) (2025)
- [Worth Their Weight: Randomized and Regularized Block Kaczmarz Algorithms without Preprocessing](https://mlsanity.com/paper/2502.00882/) (2025)
- [Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structure](https://mlsanity.com/paper/2507.11724/) (2025)
- [A Sketch-and-Project Analysis of Subsampled Natural Gradient Algorithms](https://mlsanity.com/paper/2508.21022/) (2025)
- [Last-Iterate Convergence of Randomized Kaczmarz and SGD with Greedy Step Size](https://mlsanity.com/paper/2604.09909/) (2026)
- [Perfect Parallelization in Mini-Batch SGD with Classical Momentum Acceleration](https://mlsanity.com/paper/2605.18609/) (2026)

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