2024/05/09 by Michał Dereziński, Daniel LeJeune, Dereziński, Michał +5 · 3 citations
Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #Digital Image Processing Techniques #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Manufacturing Process and Optimization #Matrix Theory and Algorithms #Numerical Analysis (math.NA) #Optimization and Control (math.OC)
paper · pdf · doi:10.48550/arxiv.2405.05818
openalex publication_date 2024/05/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 κ_ℓ 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 x such that ‖Ax - b‖ ≤ ε‖b‖, in time O(κ_ℓ⋅ 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.