# Improved Stability and Generalization Guarantees of the Decentralized SGD Algorithm

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 36 references that are in the map.
- First posted on arXiv 5 Jun 2023.

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

- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1705.09056/) (2017)
- [A Unified Theory of Decentralized SGD with Changing Topology and Local Updates](https://mlsanity.com/paper/2003.10422/) (2020)
- [Information-theoretic analysis of generalization capability of learning algorithms](https://mlsanity.com/paper/1705.07809/) (2017)
- [User-friendly introduction to PAC-Bayes bounds](https://mlsanity.com/paper/2110.11216/) (2021)
- [Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses](https://mlsanity.com/paper/2006.06914/) (2020)
- [Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent](https://mlsanity.com/paper/2006.08157/) (2020)
- [High probability generalization bounds for uniformly stable algorithms with nearly optimal rate](https://mlsanity.com/paper/1902.10710/) (2019)
- [Data-Dependent Stability of Stochastic Gradient Descent](https://mlsanity.com/paper/1703.01678/) (2017)
- [Information-Theoretic Generalization Bounds for Stochastic Gradient Descent](https://mlsanity.com/paper/2102.00931/) (2021)
- [Exponential Graph is Provably Efficient for Decentralized Deep Training](https://mlsanity.com/paper/2110.13363/) (2021)
- [Consensus Control for Decentralized Deep Learning](https://mlsanity.com/paper/2102.04828/) (2021)
- [SGD Generalizes Better Than GD (And Regularization Doesn't Help)](https://mlsanity.com/paper/2102.01117/) (2021)
- [Topology-aware Generalization of Decentralized SGD](https://mlsanity.com/paper/2206.12680/) (2022)
- [Decentralized gradient methods: does topology matter?](https://mlsanity.com/paper/2002.12688/) (2020)
- [Stability of SGD: Tightness Analysis and Improved Bounds](https://mlsanity.com/paper/2102.05274/) (2021)
- [Refined Convergence and Topology Learning for Decentralized SGD with Heterogeneous Data](https://mlsanity.com/paper/2204.04452/) (2022)
- [A PAC-Bayesian Analysis of Randomized Learning with Application to Stochastic Gradient Descent](https://mlsanity.com/paper/1709.06617/) (2017)
- [Stability vs Implicit Bias of Gradient Methods on Separable Data and Beyond](https://mlsanity.com/paper/2202.13441/) (2022)
- [Generalization Properties and Implicit Regularization for Multiple Passes SGM](https://mlsanity.com/paper/1605.08375/) (2016)
- [Generalization Error Bounds with Probabilistic Guarantee for SGD in Nonconvex Optimization](https://mlsanity.com/paper/1802.06903/) (2018)
- [Graph-Dependent Implicit Regularisation for Distributed Stochastic Subgradient Descent](https://mlsanity.com/paper/1809.06958/) (2018)
- [On Generalization of Decentralized Learning with Separable Data](https://mlsanity.com/paper/2209.07116/) (2022)
- [Tight Risk Bounds for Gradient Descent on Separable Data](https://mlsanity.com/paper/2303.01135/) (2023)

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

- [Towards Understanding Generalization and Stability Gaps between Centralized and Decentralized Federated Learning](https://mlsanity.com/paper/2310.03461/) (2023)
- [DICE: Data Influence Cascade in Decentralized Learning](https://mlsanity.com/paper/2507.06931/) (2025)
- [Unveiling the Power of Multiple Gossip Steps: A Stability-Based Generalization Analysis in Decentralized Training](https://mlsanity.com/paper/2510.07980/) (2025)
- [Generalization Error Analysis for Attack-Free and Byzantine-Resilient Decentralized Learning with Data Heterogeneity](https://mlsanity.com/paper/2506.09438/) (2025)
- [Tight Analysis of Decentralized SGD: A Markov Chain Perspective](https://mlsanity.com/paper/2601.07021/) (2026)
- [On the Escaping Efficiency of Distributed Adversarial Training Algorithms](https://mlsanity.com/paper/2509.11337/) (2025)
- [Stability and Generalization of Adversarial Diffusion Training](https://mlsanity.com/paper/2509.19234/) (2025)
- [Decentralized SGD with Controlled Disagreement Finds Flatter Minima](https://mlsanity.com/paper/2602.02899/) (2026)
- [Stability and Generalization of Push-Sum Based Decentralized Optimization over Directed Graphs](https://mlsanity.com/paper/2602.20567/) (2026)
- [Dangerous Liaisons of Convex Learning and Non-Affine Aggregation](https://mlsanity.com/paper/2606.28123/) (2026)

## Abstract (arXiv)

This paper presents a new generalization error analysis for Decentralized Stochastic Gradient Descent (D-SGD) based on algorithmic stability. The obtained results overhaul a series of recent works that suggested an increased instability due to decentralization and a detrimental impact of poorly-connected communication graphs on generalization. On the contrary, we show, for convex, strongly convex and non-convex functions, that D-SGD can always recover generalization bounds analogous to those of classical SGD, suggesting that the choice of graph does not matter. We then argue that this result is coming from a worst-case analysis, and we provide a refined optimization-dependent generalization bound for general convex functions. This new bound reveals that the choice of graph can in fact improve the worst-case bound in certain regimes, and that surprisingly, a poorly-connected graph can even be beneficial for generalization.