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

Abstract

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(_ n^2 1/), for any = 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.

Tasks

Reproductions