Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems
This work addresses a key bottleneck in machine learning tasks like ridge regression and kernel machines by providing faster algorithms for linear systems with low-dimensional structure, though it is incremental in its approach.
The paper tackles the problem of solving large linear systems efficiently by introducing a fine-grained complexity measure based on singular value ratios, and presents a stochastic algorithm that achieves a time complexity of O(κ_ℓ·n² log 1/ε) for solving Ax = b, improving over preconditioned conjugate gradient methods.
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 $κ_\ell$ be the ratio between the $\ell$th largest and the smallest singular value of $n\times 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 $\bar{x}$ such that $\|A\bar{x} - b\| \le ε\|b\|$, in time $\bar O(κ_\ell\cdot n^2\log 1/ε)$, for any $\ell = O(n^{0.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.