Randomized Kaczmarz with tail averaging

The randomized Kaczmarz (RK) method is a well-known approach for solving linear least-squares problems with a large number of rows. RK accesses and processes just one row at a time, leading to exponentially fast convergence for consistent linear systems. However, RK fails to converge to the least-squares solution for inconsistent systems. This work presents a simple fix: average the RK iterates produced in the tail part of the algorithm. The proposed tail-averaged randomized Kaczmarz (TARK) converges for both consistent and inconsistent least-squares problems at a polynomial rate, which is known to be optimal for any row-access method. An extension of TARK also leads to efficient solutions for ridge-regularized least-squares problems.

The authors thank Haoxuan Chen, Zhiyan Ding, Michał Dereziński, Jamie Haddock, Jiang Hu, Lin Lin, Anna Ma, Christopher Musco, Deanna Needell, Kevin Shu, Joel Tropp, Roman Vershynin, and Jonathan Weare for helpful conversations. ENE acknowledges support from the Department of Energy under Award Number DE-SC0021110 and, under the aegis of Joel Tropp, from NSF FRG 1,952,777 and the Carver Mead New Horizons Fund. GG acknowledges support from the Department of Energy under Award Number DE-SC0023112.