mlsanityData to 7 Oct 2026

Topology-aware Generalization of Decentralized SGD

arXiv 2206.12680 ↗First posted 25 Jun 2022cs.LG stat.MLcited by 37

Not on the map. Why?

Abstract (arXiv)

This paper studies the algorithmic stability and generalizability of decentralized stochastic gradient descent (D-SGD). We prove that the consensus model learned by D-SGD is O(N-1+m-1 +λ2)-stable in expectation in the non-convex non-smooth setting, where N is the total sample size, m is the worker number, and 1+λ is the spectral gap that measures the connectivity of the communication topology. These results then deliver an O(N-(1+α)/2+ m-(1+α)/2+λ1+α + φS) in-average generalization bound, which is non-vacuous even when λ is closed to 1, in contrast to vacuous as suggested by existing literature on the projected version of D-SGD. Our theory indicates that the generalizability of D-SGD is positively correlated with the spectral gap, and can explain why consensus control in initial training phase can ensure better generalization. Experiments of VGG-11 and ResNet-18 on CIFAR-10, CIFAR-100 and Tiny-ImageNet justify our theory. To our best knowledge, this is the first work on the topology-aware generalization of vanilla D-SGD. Code is available at https://github.com/Raiden-Zhu/Generalization-of-DSGD.

Key facts. Cited by 37 papers in the map (data through 7 Oct 2026). Builds on 53 of its 94 references that are in the map. First posted on arXiv 25 Jun 2022.

Builds on

53 of 94 references.

References · 53

  1. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  2. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,160
  3. 2014Very Deep Convolutional Networks for Large-Scale Image Recognitioncited by 15,267
  4. 2015Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shiftcited by 6,979
  5. 2016Identity Mappings in Deep Residual Networkscited by 1,960
  6. 2017Accurate, Large Minibatch SGD: Training ImageNet in 1 Hourcited by 1,479
  7. 2018Federated Learning with Non-IID Datacited by 1,099
  8. 2019Deep Leakage from Gradientscited by 1,004
  9. 2020Inverting Gradients -- How easy is it to break privacy in federated learning?cited by 707
  10. 2017The Implicit Bias of Gradient Descent on Separable Datacited by 649
  11. 2019On Exact Computation with an Infinitely Wide Neural Netcited by 572
  12. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
38 more
  1. 2017Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descentcited by 496
  2. 2020A Unified Theory of Decentralized SGD with Changing Topology and Local Updatescited by 361
  3. 2021See through Gradients: Image Batch Recovery via GradInversioncited by 320
  4. 2019Efficient and Accurate Estimation of Lipschitz Constants for Deep Neural Networkscited by 290
  5. 2018Gradient descent aligns the layers of deep linear networkscited by 182
  6. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 172
  7. 2014EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimizationcited by 160
  8. 2017Asynchronous Decentralized Parallel Stochastic Gradient Descentcited by 159
  9. 2018Stochastic Gradient Push for Distributed Deep Learningcited by 152
  10. 2018Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptroncited by 143
  11. 2018D2: Decentralized Training over Decentralized Datacited by 140
  12. 2017Network Topology and Communication-Computation Tradeoffs in Decentralized Optimizationcited by 119
  13. 2020Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descentcited by 118
  14. 2020The Early Phase of Neural Network Trainingcited by 114
  15. 2017Data-Dependent Stability of Stochastic Gradient Descentcited by 90
  16. 2021Information-Theoretic Generalization Bounds for Stochastic Gradient Descentcited by 84
  17. 2022DisPFL: Towards Communication-Efficient Personalized Federated Learning via Decentralized Sparse Trainingcited by 74
  18. 2019MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Samplingcited by 67
  19. 2020Optimal Complexity in Decentralized Trainingcited by 59
  20. 2021Exponential Graph is Provably Efficient for Decentralized Deep Trainingcited by 55
  21. 2018Stability and Convergence Trade-off of Iterative Optimization Algorithmscited by 53
  22. 2021Consensus Control for Decentralized Deep Learningcited by 49
  23. 2020The Implicit Bias for Adaptive Optimization Algorithms on Homogeneous Neural Networkscited by 43
  24. 2021A Unified and Refined Convergence Analysis for Non-Convex Decentralized Learningcited by 43
  25. 2020Toward Better Generalization Bounds with Locally Elastic Stabilitycited by 41
  26. 2020Recent advances in deep learning theorycited by 41
  27. 2017Algorithmic stability and hypothesis complexitycited by 39
  28. 2021RelaySum for Decentralized Deep Learning on Heterogeneous Datacited by 39
  29. 2021Non-IID data and Continual Learning processes in Federated Learning: A long road aheadcited by 36
  30. 2019Asynchronous Decentralized SGD with Quantized and Local Updatescited by 35
  31. 2019On the Influence of Bias-Correction on Distributed Stochastic Optimizationcited by 34
  32. 2022Achieving Personalized Federated Learning with Sparse Local Modelscited by 30
  33. 2020Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networkscited by 27
  34. 2022Beyond spectral gap: The role of the topology in decentralized learningcited by 27
  35. 2020Quantized Decentralized Stochastic Learning over Directed Graphscited by 24
  36. 2019Hypothesis Set Stability and Generalizationcited by 23
  37. 2021BlueFog: Make Decentralized Algorithms Practical for Optimization and Deep Learningcited by 16
  38. 2018Graph-Dependent Implicit Regularisation for Distributed Stochastic Subgradient Descentcited by 14

50 most cited of 53 All 53 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 16; 2024: 8; 2025: 8; 2026: 5.

37 papers.

Sort:

  1. 2023Improving the Model Consistency of Decentralized Federated Learningcited by 45
  2. 2023Decentralized Learning Made Easy with DecentralizePycited by 18
  3. 2023Decentralized SGD and Average-direction SAM are Asymptotically Equivalentcited by 15
  4. 2023AEDFL: Efficient Asynchronous Decentralized Federated Learning with Heterogeneous Devicescited by 15
  5. 2023Improved Stability and Generalization Guarantees of the Decentralized SGD Algorithmcited by 10
  6. 2023Lookaround Optimizer: k steps around, 1 step averagecited by 9
  7. 2024Decentralized Directed Collaboration for Personalized Federated Learningcited by 9
  8. 2023Beyond Exponential Graph: Communication-Efficient Topologies for Decentralized Learning via Finite-time Convergencecited by 8
  9. 2023Towards More Suitable Personalization in Federated Learning via Decentralized Partial Model Trainingcited by 8
  10. 2023Stability and Generalization of the Decentralized Stochastic Gradient Descent Ascent Algorithmcited by 8
  11. 2024Impact of network topology on the performance of Decentralized Federated Learningcited by 7
  12. 2023DFedADMM: Dual Constraints Controlled Model Inconsistency for Decentralized Federated Learningcited by 6
25 more
  1. 2023DePRL: Achieving Linear Convergence Speedup in Personalized Decentralized Learning with Shared Representationscited by 5
  2. 2024Robustness of Decentralised Learning to Nodes and Data Disruptioncited by 5
  3. 2024Generalization Error Matters in Decentralized Learning Under Byzantine Attackscited by 4
  4. 2023Decentralized Adversarial Training over Graphscited by 3
  5. 2023Towards Understanding Generalization and Stability Gaps between Centralized and Decentralized Federated Learningcited by 3
  6. 2024On the Trade-off between Flatness and Optimization in Distributed Learningcited by 3
  7. 2025DICE: Data Influence Cascade in Decentralized Learningcited by 2
  8. 2023Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithmscited by 1
  9. 2024OledFL: Unleashing the Potential of Decentralized Federated Learning via Opposite Lookahead Enhancementcited by 1
  10. 2024Exploring the Generalization Capabilities of AID-based Bi-level Optimizationcited by 1
  11. 2025Distribution-Aware Mobility-Assisted Decentralized Federated Learningcited by 1
  12. 2025Generalization Error Analysis for Attack-Free and Byzantine-Resilient Decentralized Learning with Data Heterogeneitycited by 1
  13. 2025Unveiling the Power of Multiple Gossip Steps: A Stability-Based Generalization Analysis in Decentralized Trainingcited by 1
  14. 2026Decentralized Federated Learning by Partial Message Exchangecited by 1
  15. 2023Accelerated Distributed Aggregative Optimizationcited by 0
  16. 2023Towards Understanding the Generalizability of Delayed Stochastic Gradient Descentcited by 0
  17. 2024Technical Report: On the Convergence of Gossip Learning in the Presence of Node Inaccessibilitycited by 0
  18. 2025Deep-Relative-Trust-Based Diffusion for Decentralized Deep Learningcited by 0
  19. 2025DFed-SST: Building Semantic- and Structure-aware Topologies for Decentralized Federated Graph Learningcited by 0
  20. 2025On the Escaping Efficiency of Distributed Adversarial Training Algorithmscited by 0
  21. 2025Mobility-Assisted Decentralized Federated Learning: Convergence Analysis and A Data-Driven Approachcited by 0
  22. 2026Decentralized SGD with Controlled Disagreement Finds Flatter Minimacited by 0
  23. 2026Stability and Generalization of Push-Sum Based Decentralized Optimization over Directed Graphscited by 0
  24. 2026Stability and Generalization for Decentralized Markov SGDcited by 0
  25. 2026Unveiling High-Probability Generalization in Decentralized SGDcited by 0