# DSA: Decentralized Double Stochastic Averaging Gradient Algorithm

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

## Key facts

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

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

- [A Hybrid Variance-Reduced Method for Decentralized Stochastic Non-Convex Optimization](https://mlsanity.com/paper/2102.06752/) (2021)
- [Tackling Data Heterogeneity: A New Unified Framework for Decentralized SGD with Sample-induced Topology](https://mlsanity.com/paper/2207.03730/) (2022)
- [Networked Signal and Information Processing](https://mlsanity.com/paper/2210.13767/) (2022)
- [GT-STORM: Taming Sample, Communication, and Memory Complexities in Decentralized Non-Convex Learning](https://mlsanity.com/paper/2105.01231/) (2021)
- [Decentralized Composite Optimization with Compression](https://mlsanity.com/paper/2108.04448/) (2021)
- [Byzantine-Robust Decentralized Stochastic Optimization with Stochastic Gradient Noise-Independent Learning Error](https://mlsanity.com/paper/2308.05292/) (2023)
- [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)
- [A primal-dual perspective for distributed TD-learning](https://mlsanity.com/paper/2310.00638/) (2023)
- [Decentralized Sum-of-Nonconvex Optimization](https://mlsanity.com/paper/2402.02356/) (2024)
- [Fedivertex: a Graph Dataset based on Decentralized Social Networks for Trustworthy Machine Learning](https://mlsanity.com/paper/2505.20882/) (2025)
- [Exact Subspace Diffusion for Decentralized Multitask Learning](https://mlsanity.com/paper/2304.07358/) (2023)
- [Accelerating Distributed Optimization: A Primal-Dual Perspective on Local Steps](https://mlsanity.com/paper/2407.02689/) (2024)

## Abstract (arXiv)

This paper considers convex optimization problems where nodes of a network have access to summands of a global objective. Each of these local objectives is further assumed to be an average of a finite set of functions. The motivation for this setup is to solve large scale machine learning problems where elements of the training set are distributed to multiple computational elements. The decentralized double stochastic averaging gradient (DSA) algorithm is proposed as a solution alternative that relies on: (i) The use of local stochastic averaging gradients. (ii) Determination of descent steps as differences of consecutive stochastic averaging gradients. Strong convexity of local functions and Lipschitz continuity of local gradients is shown to guarantee linear convergence of the sequence generated by DSA in expectation. Local iterates are further shown to approach the optimal argument for almost all realizations. The expected linear convergence of DSA is in contrast to the sublinear rate characteristic of existing methods for decentralized stochastic optimization. Numerical experiments on a logistic regression problem illustrate reductions in convergence time and number of feature vectors processed until convergence relative to these other alternatives.