Improved Stability and Generalization Guarantees of the Decentralized SGD Algorithm

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.

• Publication year

  2023

• Venue

  International Conference on Machine Learning

• Publication date

  2023-06-05

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 2306.02939
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Minimax Excess Risk of First-Order Methods for Statistical Learning with Data-Dependent Oracles

  2023cited by this paper
• Tight Risk Bounds for Gradient Descent on Separable Data

  2023cited by this paper
• On Generalization of Decentralized Learning with Separable Data

  2022influential reference
• Refined Convergence and Topology Learning for Decentralized SGD with Heterogeneous Data

  2022cited by this paper
• Topology-aware Generalization of Decentralized SGD

  2022influential reference
• Stability vs Implicit Bias of Gradient Methods on Separable Data and Beyond

  2022cited by this paper
• Information-Theoretic Generalization Bounds for Stochastic Gradient Descent

  2021cited by this paper
• SGD Generalizes Better Than GD (And Regularization Doesn't Help)

  2021cited by this paper
• Exponential Graph is Provably Efficient for Decentralized Deep Training

  2021cited by this paper
• User-friendly introduction to PAC-Bayes bounds

  2021cited by this paper
• Stability of SGD: Tightness Analysis and Improved Bounds

  2021cited by this paper
• Consensus Control for Decentralized Deep Learning

  2021cited by this paper
• Stability and Generalization of Decentralized Stochastic Gradient Descent

  2021influential reference
• Decentralized gradient methods: does topology matter?

  2020influential reference
• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates

  2020influential reference
• Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses

  2020cited by this paper
• Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent

  2020influential reference
• High probability generalization bounds for uniformly stable algorithms with nearly optimal rate

  2019cited by this paper
• Generalization Error Bounds with Probabilistic Guarantee for SGD in Nonconvex Optimization

  2018cited by this paper
• Graph-Dependent Implicit Regularisation for Distributed Stochastic Subgradient Descent

  2018influential reference
• Information-theoretic analysis of generalization capability of learning algorithms

  2017cited by this paper
• Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent

  2017influential reference
• Data-Dependent Stability of Stochastic Gradient Descent

  2017influential reference
• A PAC-Bayesian Analysis of Randomized Learning with Application to Stochastic Gradient Descent

  2017cited by this paper
• Generalization Properties and Implicit Regularization for Multiple Passes SGM

  2016cited by this paper
• Train faster, generalize better: Stability of stochastic gradient descent

  2015influential reference
• Convex Optimization: Algorithms and Complexity

  2014influential reference
• Learnability, Stability and Uniform Convergence

  2010cited by this paper
• Distributed Subgradient Methods for Multi-Agent Optimization

  2009cited by this paper
• PAC-BAYESIAN SUPERVISED CLASSIFICATION: The Thermodynamics of Statistical Learning

  2007cited by this paper
• Introduction to Statistical Learning Theory

  2004cited by this paper
• Stability and Generalization

  2002cited by this paper
• Matrix Analysis and Applied Linear Algebra

  2000influential reference
• Some PAC-Bayesian Theorems

  1998cited by this paper
• A PAC analysis of a Bayesian estimator

  1997cited by this paper

• Stability and Generalization of Push-Sum Based Decentralized Optimization over Directed Graphs

  2026cites this paper
• Controlled disagreement improves generalization in decentralized training

  2026cites this paper
• Tight Analysis of Decentralized SGD: A Markov Chain Perspective

  2026cites this paper
• Stability and Generalization of Nonconvex Optimization with Heavy-Tailed Noise

  2026cites this paper
• On the Escaping Efficiency of Distributed Adversarial Training Algorithms

  2025cites this paper
• Stability and Generalization of Adversarial Diffusion Training

  2025influential citation
• Unveiling the Power of Multiple Gossip Steps: A Stability-Based Generalization Analysis in Decentralized Training

  2025influential citation
• Generalization Guarantee of Decentralized Learning with Heterogeneous Data

  2025influential citation
• DICE: Data Influence Cascade in Decentralized Learning

  2025cites this paper
• Generalization Error Analysis for Attack-Free and Byzantine-Resilient Decentralized Learning with Data Heterogeneity

  2025influential citation
• Toward Understanding Generalization and Stability Gaps Between Centralized and Decentralized Federated Learning

  2023cites this paper
• Tight High-Probability Bounds for Nonconvex Heavy-Tailed Scenario under Weaker Assumptions

  year unknowncites this paper