# Variance Reduced EXTRA and DIGing and Their Optimal Acceleration for Strongly Convex Decentralized Optimization

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Sep 2020.

## Built on by (most cited first, 13 of 13)

- [Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization](https://mlsanity.com/paper/2104.02596/) (2021)
- [Robust Decentralized Learning with Local Updates and Gradient Tracking](https://mlsanity.com/paper/2405.00965/) (2024)
- [An Efficient Stochastic Algorithm for Decentralized Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2212.02387/) (2022)
- [Communication-Efficient Stochastic Distributed Learning](https://mlsanity.com/paper/2501.13516/) (2025)
- [Decentralized Stochastic Variance Reduced Extragradient Method](https://mlsanity.com/paper/2202.00509/) (2022)
- [Variance-reduced accelerated methods for decentralized stochastic double-regularized nonconvex strongly-concave minimax problems](https://mlsanity.com/paper/2307.07113/) (2023)
- [Robust Online Learning over Networks](https://mlsanity.com/paper/2309.00520/) (2023)
- [A Proximal Gradient Method With Probabilistic Multi-Gossip Communications for Decentralized Composite Optimization](https://mlsanity.com/paper/2312.11861/) (2023)
- [On the Complexity of Finite-Sum Smooth Optimization under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/2402.02569/) (2024)
- [Achieving Linear Speedup with ProxSkip in Distributed Stochastic Optimization](https://mlsanity.com/paper/2310.07983/) (2023)
- [Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks](https://mlsanity.com/paper/2405.18031/) (2024)
- [Jointly Computation- and Communication-Efficient Distributed Learning](https://mlsanity.com/paper/2508.15509/) (2025)
- [Decentralized Stochastic Nonconvex Optimization under the (L0,L1)-Smoothness](https://mlsanity.com/paper/2509.08726/) (2025)

## Abstract (arXiv)

We study stochastic decentralized optimization for the problem of training machine learning models with large-scale distributed data. We extend the widely used EXTRA and DIGing methods with variance reduction (VR), and propose two methods: VR-EXTRA and VR-DIGing. The proposed VR-EXTRA requires the time of O((kappas+n)logfrac1ε) stochastic gradient evaluations and O((kappab+kappac)logfrac1ε) communication rounds to reach precision ε, which are the best complexities among the non-accelerated gradient-type methods, where kappas and kappab are the stochastic condition number and batch condition number for strongly convex and smooth problems, respectively, kappac is the condition number of the communication network, and n is the sample size on each distributed node. The proposed VR-DIGing has a little higher communication cost of O((kappab+kappac2)logfrac1ε). Our stochastic gradient computation complexities are the same as the ones of single-machine VR methods, such as SAG, SAGA, and SVRG, and our communication complexities keep the same as those of EXTRA and DIGing, respectively. To further speed up the convergence, we also propose the accelerated VR-EXTRA and VR-DIGing with both the optimal O((√nkappas+n)logfrac1ε) stochastic gradient computation complexity and O(√kappabkappaclogfrac1ε) communication complexity. Our stochastic gradient computation complexity is also the same as the ones of single-machine accelerated VR methods, such as Katyusha, and our communication complexity keeps the same as those of accelerated full batch decentralized methods, such as MSDA.