Randomized iterative sketch-and-project methods as efficient large-scale linear solvers

Randomized Kaczmarz methods — popular special case of the sketch-and-project optimization framework — solve linear systems through iterative projections onto randomly selected equations, resulting in exponential expected convergence via cheap, local updates. While known to be effective in highly overdetermined problems or under the restricted data access, identifying generic scenarios where these methods are advantageous compared to classical solvers remained open.
I will talk about better ways to quantify the convergence of the sketch-and-project methods and present our recent work showing that — if properly designed — these methods outperform Krylov-based solvers complexity-wise for both square and rectangular systems. Since the proposed solvers quickly capture the large outlying singular values of the linear system, they are particularly advantageous for approximately low-rank systems common in machine learning (e.g., kernel matrices, signal-plus-noise models). Our approach combines novel spectral analysis of randomly sketched projection matrices with classical numerical analysis techniques, such as including momentum, adaptive regularization, and memoization.