Variance Reduction for Decentralized Stochastic Optimization with Multiple Local Updates
Abstract
Multiple local updates are widely used in decentralized optimization to enhance communication efficiency, often in conjunction with stochastic gradients when exact gradient computation is costly. However, such algorithms generally converge only to a neighborhood of the optimum, whose size depends on the stepsize and the variance of gradient noise. Variance reduction has been incorporated into ADMM-based methods to achieve exact convergence in expectation, but their stepsizes typically scale inversely with both the square root of the network size and the cube of the number of local updates, leading to slow convergence as the network size or the number of local updates increases. In this paper, we propose a novel primal-dual-based decentralized optimization algorithm that integrates variance reduction with multiple local updates, with a stepsize independent of the network size and inversely proportional to the number of local updates (rather than its cube), thereby enabling significantly larger stepsizes and faster convergence. Moreover, to the best of our knowledge, we establish the first linear convergence guarantee in expectation for decentralized optimization with multiple local updates under stochastic gradients in the strongly convex setting. Beyond the theoretical guarantee, the proposed method exchanges only one variable per round, halving the communication cost compared with gradient-tracking-based methods. Numerical experiments further demonstrate its advantages in convergence speed and accuracy.
Related
- Lower Bounds for Stochastic First-Order Algorithms with Variance Reduction in Nonconvex--Concave Minimax Optimization
- Accelerated Push-Pull with Local Updates for Decentralized Stochastic Optimization
- Near-Optimal Decentralized Stochastic Convex Optimization over Networks
- Dimension-Free Decentralized Nonsmooth Nonconvex Stochastic Optimization
- Resilient Decentralized Preconditioned Stochastic Proximal Optimization with Gradient Sketching over Time-Varying Networks
BibTeX
@misc{liu2026variance,
title = {{Variance Reduction for Decentralized Stochastic Optimization with Multiple Local Updates}},
author = {Jie Liu and Nicola Bastianello and Wenying Xu and Daniel W. C. Ho},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.41927},
eprint = {2610.41927},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.41927},
}
RIS
TY - UNPB
TI - Variance Reduction for Decentralized Stochastic Optimization with Multiple Local Updates
AU - Jie Liu
AU - Nicola Bastianello
AU - Wenying Xu
AU - Daniel W. C. Ho
PY - 2026
DA - 2026/10/30
PB - arXiv
DO - 10.48550/arxiv.2610.41927
UR - https://arxiv.org/abs/2610.41927
AB - Multiple local updates are widely used in decentralized optimization to enhance communication efficiency, often in conjunction with stochastic gradients when exact gradient computation is costly. However, such algorithms generally converge only to a neighborhood of the optimum, whose size depends on the stepsize and the variance of gradient noise. Variance reduction has been incorporated into ADMM-based methods to achieve exact convergence in expectation, but their stepsizes typically scale inversely with both the square root of the network size and the cube of the number of local updates, leading to slow convergence as the network size or the number of local updates increases. In this paper, we propose a novel primal-dual-based decentralized optimization algorithm that integrates variance reduction with multiple local updates, with a stepsize independent of the network size and inversely proportional to the number of local updates (rather than its cube), thereby enabling significantly larger stepsizes and faster convergence. Moreover, to the best of our knowledge, we establish the first linear convergence guarantee in expectation for decentralized optimization with multiple local updates under stochastic gradients in the strongly convex setting. Beyond the theoretical guarantee, the proposed method exchanges only one variable per round, halving the communication cost compared with gradient-tracking-based methods. Numerical experiments further demonstrate its advantages in convergence speed and accuracy.
ER -