Efficient variance reduction for randomized Kaczmarz methods via residual-tracking control variates

Abstract

The randomized Kaczmarz (RK) method is a widely used and effective class of iterative algorithms for solving large-scale linear systems. For inconsistent systems, however, the persistent variance caused by randomization prevents the method from converging exactly to the least-squares solution. In this paper, we introduce a residual-tracking control variate framework for reducing this variance while retaining the row-action structure and low per-iteration cost of RK. The resulting variance-reduced RK method uses constant step sizes, accesses only sampled rows of the coefficient matrix, and requires $O(m+n)$ auxiliary storage. We prove that the proposed method converges linearly in expectation to the unique least-norm solution for general linear systems, including inconsistent and rank-deficient cases, with a convergence factor of the same order as that of the RK method. Furthermore, we incorporate the momentum acceleration into our framework and provide theoretical guarantees for its improved convergence rate. Numerical experiments illustrate the effectiveness of the proposed methods, particularly for ill-conditioned systems and high-accuracy computations.