# Decentralized Stochastic Proximal Gradient Descent with Variance Reduction over Time-varying Networks

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 35 references that are in the map.
- First posted on arXiv 20 Dec 2021.

## Builds on (most cited first, 16 of 16)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1705.09056/) (2017)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [Stochastic Gradient Push for Distributed Deep Learning](https://mlsanity.com/paper/1811.10792/) (2018)
- [Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphs](https://mlsanity.com/paper/1607.03218/) (2016)
- [Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization](https://mlsanity.com/paper/1709.08765/) (2017)
- [A Proximal Stochastic Gradient Method with Progressive Variance Reduction](https://mlsanity.com/paper/1403.4699/) (2014)
- [On the Linear Convergence of the ADMM in Decentralized Consensus Optimization](https://mlsanity.com/paper/1307.5561/) (2013)
- [An improved convergence analysis for decentralized online stochastic non-convex optimization](https://mlsanity.com/paper/2008.04195/) (2020)
- [Variance-Reduced Decentralized Stochastic Optimization with Accelerated Convergence](https://mlsanity.com/paper/1912.04230/) (2019)
- [Less than a Single Pass: Stochastically Controlled Stochastic Gradient Method](https://mlsanity.com/paper/1609.03261/) (2016)
- [DSA: Decentralized Double Stochastic Averaging Gradient Algorithm](https://mlsanity.com/paper/1506.04216/) (2015)
- [Privacy Preservation in Distributed Subgradient Optimization Algorithms](https://mlsanity.com/paper/1512.08822/) (2015)
- [PMGT-VR: A decentralized proximal-gradient algorithmic framework with variance reduction](https://mlsanity.com/paper/2012.15010/) (2020)
- [PANDA: A Dual Linearly Converging Method for Distributed Optimization over Time-Varying Undirected Graphs](https://mlsanity.com/paper/1803.08328/) (2018)

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

- [Event-Triggered Gossip for Distributed Learning](https://mlsanity.com/paper/2602.19116/) (2026)

## Abstract (arXiv)

In decentralized learning, a network of nodes cooperate to minimize an overall objective function that is usually the finite-sum of their local objectives, and incorporates a non-smooth regularization term for the better generalization ability. Decentralized stochastic proximal gradient (DSPG) method is commonly used to train this type of learning models, while the convergence rate is retarded by the variance of stochastic gradients. In this paper, we propose a novel algorithm, namely DPSVRG, to accelerate the decentralized training by leveraging the variance reduction technique. The basic idea is to introduce an estimator in each node, which tracks the local full gradient periodically, to correct the stochastic gradient at each iteration. By transforming our decentralized algorithm into a centralized inexact proximal gradient algorithm with variance reduction, and controlling the bounds of error sequences, we prove that DPSVRG converges at the rate of O(1/T) for general convex objectives plus a non-smooth term with T as the number of iterations, while DSPG converges at the rate O(frac1√T). Our experiments on different applications, network topologies and learning models demonstrate that DPSVRG converges much faster than DSPG, and the loss function of DPSVRG decreases smoothly along with the training epochs.