math.OCOct 30, 2026

Variance Reduction for Decentralized Stochastic Optimization with Multiple Local Updates

Authors: Jie Liu, Nicola Bastianello, Wenying Xu, Daniel W. C. Ho, Karl H. Johansson

Organizations: School of Mathematics, Southeast University, Nanjing 211189, China · Department of Electronic and Electrical Engineering, University College London, United Kingdom · Department of Mathematics, City University of Hong Kong

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.

Figures & tables

Explore similar work

Jun 5, 2026

Accelerated Decentralized Stochastic Gradient Descent for Strongly Convex Optimization

Decentralized stochastic optimization is a fundamental paradigm for large-scale learning over networks, where agents communicate only with their neighbors and no central coordinator is required. For strongly convex problems, communication efficiency is mainly determined by the condition number κ=L/μκ=L/μ and the network spectral gap 1−β1-β. Although deterministic decentralized methods can simultaneously achieve accelerated κ\sqrtκ and 1/1−β1/\sqrt{1-β} dependences, no existing stochastic method attains both improvements at once. In this paper, we propose Multi-Gossip Accelerated DSGD (MG-ADSGD), a decentralized stochastic algorithm that combines Nesterov-type primal--dual extrapolation with multi-round fast gossip averaging. The key idea is to couple the gossip depth with the mini-batch size so that additional communication rounds simultaneously improve consensus accuracy and reduce gradient variance. We show that MG-ADSGD achieves the communication complexity O~ ⁣(σ2μnεlog⁡1ε+κ1−βlog⁡1ε),\widetilde{\mathcal O}\!\left( \frac{σ^2}{μnε}\log\frac{1}ε + \sqrt{\fracκ{1-β}}\log\frac{1}ε \right), where εε denotes the target accuracy, nn is the number of nodes, and σ2σ^2 is the gradient variance. To the best of our knowledge, this bound yields the best currently available communication complexity for decentralized stochastic strongly convex optimization, up to logarithmic factors that are independent of εε.
Jun 3, 2026

Near-Optimal Decentralized Stochastic Convex Optimization over Networks

We study decentralized stochastic smooth convex optimization, where MM workers minimize an average objective using local stochastic gradients and neighbor-only communication over a fixed gossip network. A central question in this setting is to determine the largest number of workers that can be used under a total budget of NN gradient samples while still preserving the centralized O(1/N)O(1/\sqrt N) statistical rate. We introduce an accelerated decentralized method that preserves this rate for up to M≲ρ N3/4\smash{M\lesssim \sqrtρ\,N^{3/4}} workers, where ρρ is the spectral gap of the gossip network, improving the best prior maximal scaling of M≲ρN\smash{M\lesssim ρ\sqrt N}. The method is based on a one-step-delayed stochastic acceleration scheme that enables workers to interleave minibatching with accelerated gossip while controlling residual disagreement, and its guarantee depends only logarithmically on the optimum-local heterogeneity. We also establish a matching lower bound for linear-span decentralized first-order methods, showing that the method is optimal up to logarithmic factors.
Apr 30, 2026

High-Probability Convergence in Decentralized Stochastic Optimization with Gradient Tracking

We study high-probability (HP) convergence guarantees in decentralized stochastic optimization, where multiple agents collaborate to jointly train a model over a network. Existing HP results in decentralized settings almost exclusively focus on the Decentralized Stochastic Gradient Descent (DSGD\mathtt{DSGD}) algorithm, which requires strong assumptions, such as bounded data heterogeneity, or strong convexity of each agent's cost. This is contrary to the mean-squared error (MSE) results, where methods incorporating bias-correction techniques are known to converge under relaxed assumptions and achieve better practical performance. In this paper we provide the first step toward bridging the gap, by studying HP convergence of DSGD\mathtt{DSGD} incorporating the gradient tracking technique, in the presence of noise satisfying a relaxed sub-Gaussian condition. We show that the resulting method, dubbed GT−DSGD\mathtt{GT-DSGD}, achieves order-optimal HP convergence rates for both non-convex and Polyak-Łojasiewicz costs, of order O(log⁡(1/δ)nT)\mathcal{O}\Big(\frac{\log(1/δ)}{\sqrt{nT}}\Big) and O(log⁡(1/δ)nT)\mathcal{O}\Big(\frac{\log(1/δ)}{nT}\Big), respectively, where nn is the number of agents, TT is the time horizon and δ∈(0,1)δ\in (0,1) is the confidence parameter. Our results establish that GT−DSGD\mathtt{GT-DSGD} converges in the HP sense under the same conditions on the cost as in the MSE sense, while achieving comparable transient times. To the best of our knowledge, these are the first HP guarantees for decentralized optimization methods incorporating bias-correction. Numerical experiments on real and synthetic data verify our theoretical findings, underlining the superior performance of GT−DSGD\mathtt{GT-DSGD} and highlighting that the benefits of incorporating bias-correction are also maintained in the HP sense.