# Unveiling the Power of Multiple Gossip Steps: A Stability-Based Generalization Analysis in Decentralized Training

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 47 references that are in the map.
- First posted on arXiv 9 Oct 2025.

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

- [On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima](https://mlsanity.com/paper/1609.04836/) (2016)
- [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)
- [Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent](https://mlsanity.com/paper/2006.08157/) (2020)
- [Decentralized Federated Averaging](https://mlsanity.com/paper/2104.11375/) (2021)
- [Quasi-Global Momentum: Accelerating Decentralized Deep Learning on Heterogeneous Data](https://mlsanity.com/paper/2102.04761/) (2021)
- [Optimal Complexity in Decentralized Training](https://mlsanity.com/paper/2006.08085/) (2020)
- [Improving the Model Consistency of Decentralized Federated Learning](https://mlsanity.com/paper/2302.04083/) (2023)
- [Optimal and Practical Algorithms for Smooth and Strongly Convex Decentralized Optimization](https://mlsanity.com/paper/2006.11773/) (2020)
- [Topology-aware Generalization of Decentralized SGD](https://mlsanity.com/paper/2206.12680/) (2022)
- [DADAM: A Consensus-based Distributed Adaptive Gradient Method for Online Optimization](https://mlsanity.com/paper/1901.09109/) (2019)
- [Privacy Amplification by Decentralization](https://mlsanity.com/paper/2012.05326/) (2020)
- [A Survey on Decentralized Federated Learning](https://mlsanity.com/paper/2308.04604/) (2023)
- [Revisiting Optimal Convergence Rate for Smooth and Non-convex Stochastic Decentralized Optimization](https://mlsanity.com/paper/2210.07863/) (2022)
- [Understanding How Consistency Works in Federated Learning via Stage-wise Relaxed Initialization](https://mlsanity.com/paper/2306.05706/) (2023)
- [DeEPCA: Decentralized Exact PCA with Linear Convergence Rate](https://mlsanity.com/paper/2102.03990/) (2021)
- [Improved Stability and Generalization Guarantees of the Decentralized SGD Algorithm](https://mlsanity.com/paper/2306.02939/) (2023)
- [Decentralized Directed Collaboration for Personalized Federated Learning](https://mlsanity.com/paper/2405.17876/) (2024)
- [An Accelerated Method For Decentralized Distributed Stochastic Optimization Over Time-Varying Graphs](https://mlsanity.com/paper/2103.15598/) (2021)
- [Asymmetrically Decentralized Federated Learning](https://mlsanity.com/paper/2310.05093/) (2023)
- [Boosting the Performance of Decentralized Federated Learning via Catalyst Acceleration](https://mlsanity.com/paper/2410.07272/) (2024)
- [OledFL: Unleashing the Potential of Decentralized Federated Learning via Opposite Lookahead Enhancement](https://mlsanity.com/paper/2410.06482/) (2024)

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

- [A Unified Generalization Framework for Model Merging: Trade-offs, Non-Linearity, and Scaling Laws](https://mlsanity.com/paper/2601.21690/) (2026)
- [Data-Topology Compatibility Enables Personalization in Decentralized Learning](https://mlsanity.com/paper/2610.15126/) (2026)

## Abstract (arXiv)

Decentralized training removes the centralized server, making it a communication-efficient approach that can significantly improve training efficiency, but it often suffers from degraded performance compared to centralized training. Multi-Gossip Steps (MGS) serve as a simple yet effective bridge between decentralized and centralized training, significantly reducing experiment performance gaps. However, the theoretical reasons for its effectiveness and whether this gap can be fully eliminated by MGS remain open questions. In this paper, we derive upper bounds on the generalization error and excess error of MGS using stability analysis, systematically answering these two key questions. 1). Optimization Error Reduction: MGS reduces the optimization error bound at an exponential rate, thereby exponentially tightening the generalization error bound and enabling convergence to better solutions. 2). Gap to Centralization: Even as MGS approaches infinity, a non-negligible gap in generalization error remains compared to centralized mini-batch SGD (O(T^fraccβcβ +1/n m) in centralized and O(T^frac2cβ2cβ +2/n m^frac12cβ +2) in decentralized). Furthermore, we provide the first unified analysis of how factors like learning rate, data heterogeneity, node count, per-node sample size, and communication topology impact the generalization of MGS under non-convex settings without the bounded gradients assumption, filling a critical theoretical gap in decentralized training. Finally, promising experiments on CIFAR datasets support our theoretical findings.