On the convergence of doubly stochastic block gradient descent method for linear inverse problems
Abstract
Stochastic gradient descent (SGD) and randomized block coordinate descent (RBCD) belong to two fundamentally different classes of stochastic iterative regularization methods, and are promising and popular for solving large-scale inverse problems, due to their excellent scalability with respect to data size and signal size, respectively. In this work, we propose a doubly stochastic block gradient descent (DSBGD) method with early stopping, by integrating the updating strategies of both SGD and RBCD, for solving linear inverse problems in infinite-dimensional Hilbert spaces. At each iteration, the method randomly selects one data pair to obtain a stochastic gradient estimate, and then uses it to update one randomly selected block coordinate. We prove the regularizing property of DSBGD under a priori stopping rules and then derive its convergence rates with the additional source condition and a condition on the forward operator. To the best of our knowledge, these are the first convergence rate results of randomized coordinate descent-type iterative methods for inverse problems from the perspective of regularization theory. We also prove that the DSBGD iteration can be stopped by the classical discrepancy principle in finitely many steps with high probability, and that the mean squared error decreases monotonically before stopping. Several numerical experiments are provided to complement the theoretical analysis.
Related
- A Rate Transfer Method: Convergence Rates in Stochastic Gradient Descent via Stochastic Calculus
- Convergence rate of stochastic gradient descent under Łojasiewicz type condition and polynomially controlled noise
- Large-Step Last-Iterate Convergence of Random-Reshuffling Stochastic Gradient Descent
- Convergence of stochastic gradient descent for learning linear neural networks
- Non-asymptotic Convergence of Stochastic Gradient Descent in Score-based Generative Models
BibTeX
@misc{xia2026convergence,
title = {{On the convergence of doubly stochastic block gradient descent method for linear inverse problems}},
author = {Yuxin Xia and Zehui Zhou},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.15399},
eprint = {2610.15399},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.15399},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - On the convergence of doubly stochastic block gradient descent method for linear inverse problems
AU - Yuxin Xia
AU - Zehui Zhou
PY - 2026
DA - 2026/10/11
PB - arXiv
DO - 10.48550/arxiv.2610.15399
UR - https://arxiv.org/abs/2610.15399
AB - Stochastic gradient descent (SGD) and randomized block coordinate descent (RBCD) belong to two fundamentally different classes of stochastic iterative regularization methods, and are promising and popular for solving large-scale inverse problems, due to their excellent scalability with respect to data size and signal size, respectively. In this work, we propose a doubly stochastic block gradient descent (DSBGD) method with early stopping, by integrating the updating strategies of both SGD and RBCD, for solving linear inverse problems in infinite-dimensional Hilbert spaces. At each iteration, the method randomly selects one data pair to obtain a stochastic gradient estimate, and then uses it to update one randomly selected block coordinate. We prove the regularizing property of DSBGD under a priori stopping rules and then derive its convergence rates with the additional source condition and a condition on the forward operator. To the best of our knowledge, these are the first convergence rate results of randomized coordinate descent-type iterative methods for inverse problems from the perspective of regularization theory. We also prove that the DSBGD iteration can be stopped by the classical discrepancy principle in finitely many steps with high probability, and that the mean squared error decreases monotonically before stopping. Several numerical experiments are provided to complement the theoretical analysis.
ER -