# Variance-Reduced Decentralized Stochastic Optimization with Accelerated Convergence

arXiv: https://arxiv.org/abs/1912.04230 · HTML: https://mlsanity.com/paper/1912.04230/

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Dec 2019.

## Built on by (most cited first, 30 of 33)

- [Quasi-Global Momentum: Accelerating Decentralized Deep Learning on Heterogeneous Data](https://mlsanity.com/paper/2102.04761/) (2021)
- [Decentralized Gossip-Based Stochastic Bilevel Optimization over Communication Networks](https://mlsanity.com/paper/2206.10870/) (2022)
- [Decentralized Gradient Tracking with Local Steps](https://mlsanity.com/paper/2301.01313/) (2023)
- [A Hybrid Variance-Reduced Method for Decentralized Stochastic Non-Convex Optimization](https://mlsanity.com/paper/2102.06752/) (2021)
- [Over-the-Air Decentralized Federated Learning](https://mlsanity.com/paper/2106.08011/) (2021)
- [Tackling Data Heterogeneity: A New Unified Framework for Decentralized SGD with Sample-induced Topology](https://mlsanity.com/paper/2207.03730/) (2022)
- [Decentralized Composite Optimization with Compression](https://mlsanity.com/paper/2108.04448/) (2021)
- [Distributed Random Reshuffling over Networks](https://mlsanity.com/paper/2112.15287/) (2021)
- [Confederated Learning: Federated Learning with Decentralized Edge Servers](https://mlsanity.com/paper/2205.14905/) (2022)
- [The Effectiveness of Local Updates for Decentralized Learning under Data Heterogeneity](https://mlsanity.com/paper/2403.15654/) (2024)
- [DoCoM: Compressed Decentralized Optimization with Near-Optimal Sample Complexity](https://mlsanity.com/paper/2202.00255/) (2022)
- [Near-Optimal Decentralized Momentum Method for Nonconvex-PL Minimax Problems](https://mlsanity.com/paper/2304.10902/) (2023)
- [Communication-Efficient Stochastic Distributed Learning](https://mlsanity.com/paper/2501.13516/) (2025)
- [Review of Mathematical Optimization in Federated Learning](https://mlsanity.com/paper/2412.01630/) (2024)
- [Distributed stochastic proximal algorithm with random reshuffling for non-smooth finite-sum optimization](https://mlsanity.com/paper/2111.03820/) (2021)
- [Variance reduced stochastic optimization over directed graphs with row and column stochastic weights](https://mlsanity.com/paper/2202.03346/) (2022)
- [Communication Compression for Decentralized Learning with Operator Splitting Methods](https://mlsanity.com/paper/2205.03779/) (2022)
- [Byzantine-Robust Decentralized Stochastic Optimization with Stochastic Gradient Noise-Independent Learning Error](https://mlsanity.com/paper/2308.05292/) (2023)
- [Communication-Efficient Federated Optimization over Semi-Decentralized Networks](https://mlsanity.com/paper/2311.18787/) (2023)
- [Communication Efficient ConFederated Learning: An Event-Triggered SAGA Approach](https://mlsanity.com/paper/2402.18018/) (2024)
- [Distributed Policy Gradient with Variance Reduction in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2111.12961/) (2021)
- [Decentralized Stochastic Proximal Gradient Descent with Variance Reduction over Time-varying Networks](https://mlsanity.com/paper/2112.10389/) (2021)
- [Stochastic Gradient Methods with Compressed Communication for Decentralized Saddle Point Problems](https://mlsanity.com/paper/2205.14452/) (2022)
- [Push--Pull with Device Sampling](https://mlsanity.com/paper/2206.04113/) (2022)
- [Harnessing the Power of Federated Learning in Federated Contextual Bandits](https://mlsanity.com/paper/2312.16341/) (2023)
- [Decentralized Sum-of-Nonconvex Optimization](https://mlsanity.com/paper/2402.02356/) (2024)
- [High-Probability Convergence Guarantees of Decentralized SGD](https://mlsanity.com/paper/2510.06141/) (2025)
- [Federated Multi-Level Optimization over Decentralized Networks](https://mlsanity.com/paper/2310.06217/) (2023)
- [A Hybrid Stochastic Gradient Tracking Method for Distributed Online Optimization Over Time-Varying Directed Networks](https://mlsanity.com/paper/2508.20645/) (2025)
- [Beyond Scaffold: A Unified Spatio-Temporal Gradient Tracking Method](https://mlsanity.com/paper/2512.01732/) (2025)

## Abstract (arXiv)

This paper describes a novel algorithmic framework to minimize a finite-sum of functions available over a network of nodes. The proposed framework, that we call~GTVR, is stochastic and decentralized, and thus is particularly suitable for problems where large-scale, potentially private data, cannot be collected or processed at a centralized server. The GTVR~framework leads to a family of algorithms with two key ingredients: (i) textitlocal variance reduction, that enables estimating the local batch gradients from arbitrarily drawn samples of local data; and, (ii) textitglobal gradient tracking, which fuses the gradient information across the nodes. Naturally, combining different variance reduction and gradient tracking techniques leads to different algorithms of interest with valuable practical tradeoffs and design considerations. Our focus in this paper is on two instantiations of the~GTVR framework, namely~textbftextttGT-SAGA and~textbftextttGT-SVRG, that, similar to their centralized counterparts (SAGA~and~SVRG), exhibit a compromise between space and time. We show that both~textbftextttGT-SAGA and~textbftextttGT-SVRG achieve accelerated linear convergence for smooth and strongly convex problems and further describe the regimes in which they achieve non-asymptotic, network-independent linear convergence rates that are faster with respect to the existing decentralized first-order schemes. Moreover, we show that both algorithms achieve a linear speedup in such regimes, in that, the total number of gradient computations required at each node is reduced by a factor of 1/n, where n is the number of nodes, compared to their centralized counterparts that process all data at a single node. Extensive simulations illustrate the convergence behavior of the corresponding algorithms.