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.
Related
- Optimistic Gradient Algorithms with Randomized Coordinate and Variance Reduction Strategies for Composite Inclusions
- On Convergence Behavior of Randomized Kaczmarz-type Methods for Solving Doubly Noisy Linear Systems
- Weighted Randomized Kaczmarz for Sparsely Corrupted Linear Systems
- Quantile Randomized Kaczmarz for Streaming Linear Systems with Massart Noise
- Variance Reduction Note 3: The Convergence of PAGE
BibTeX
@misc{xie2026efficient,
title = {{Efficient variance reduction for randomized Kaczmarz methods via residual-tracking control variates}},
author = {Jiaxin Xie and Hou-Duo Qi and Deren Han},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.39537},
eprint = {2610.39537},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.39537},
}
RIS
TY - UNPB
TI - Efficient variance reduction for randomized Kaczmarz methods via residual-tracking control variates
AU - Jiaxin Xie
AU - Hou-Duo Qi
AU - Deren Han
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.39537
UR - https://arxiv.org/abs/2610.39537
AB - 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.
ER -