On randomized batch-sampling coordinate descent methods for solving linear least-squares problems
Abstract
This paper refines randomized block coordinate descent by introducing a coordinate-level batch-sampling distribution characterization, yielding a fine-grained randomized batch-sampling coordinate descent framework, which applies to any block coordinate descent method under an arbitrary static stochastic sampling rule for solving large-scale linear least-squares problems. Based on this framework, we derive new linear convergence rate bounds that are invariant to the column scaling of data matrices. Theoretical analysis and numerical experiments validate that the new bounds are significantly sharper than existing results and better aligned with the practical convergence rate. Furthermore, we proposed a learning-based sampling strategy by parameterizing the batch-sampling distribution and optimizing its parameters through gradient-based training. Preliminary numerical results on computed tomography (CT) reconstruction problems demonstrate that the resulting method converges significantly faster than variants using other fixed sampling rules, and outperforms tested adaptive coordinate descent methods and full gradient descent in computational efficiency, confirming that learned sampling distributions can effectively capture problem-specific structure to accelerate convergence within the framework.
Related
- Randomized average block coordinate descent method with heavy-ball momentum for tensor least squares problem under the t-product
- Averaged Mirror Descent and Dual Gradient Methods: Convergent Algorithms for Entropic Gromov-Wasserstein Problems
- Globally Convergent Block Coordinate Descent Algorithms for Semi-Nonnegative Independent Component Analysis
- How to Train Your Intercept: A Comparison of Intercept Update Strategies in Coordinate Descent
- Boundary Geometry and Global Rates of Cyclic Coordinate Descent for SVM Duals
BibTeX
@misc{xie2026randomized,
title = {{On randomized batch-sampling coordinate descent methods for solving linear least-squares problems}},
author = {Dong-Yue Xie and Xi Yang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.04685},
eprint = {2610.04685},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.04685},
}
RIS
TY - UNPB
TI - On randomized batch-sampling coordinate descent methods for solving linear least-squares problems
AU - Dong-Yue Xie
AU - Xi Yang
PY - 2026
DA - 2026/10/03
PB - arXiv
DO - 10.48550/arxiv.2610.04685
UR - https://arxiv.org/abs/2610.04685
AB - This paper refines randomized block coordinate descent by introducing a coordinate-level batch-sampling distribution characterization, yielding a fine-grained randomized batch-sampling coordinate descent framework, which applies to any block coordinate descent method under an arbitrary static stochastic sampling rule for solving large-scale linear least-squares problems. Based on this framework, we derive new linear convergence rate bounds that are invariant to the column scaling of data matrices. Theoretical analysis and numerical experiments validate that the new bounds are significantly sharper than existing results and better aligned with the practical convergence rate. Furthermore, we proposed a learning-based sampling strategy by parameterizing the batch-sampling distribution and optimizing its parameters through gradient-based training. Preliminary numerical results on computed tomography (CT) reconstruction problems demonstrate that the resulting method converges significantly faster than variants using other fixed sampling rules, and outperforms tested adaptive coordinate descent methods and full gradient descent in computational efficiency, confirming that learned sampling distributions can effectively capture problem-specific structure to accelerate convergence within the framework.
ER -