Research map / Optimization / Distributed and compressed
Unveiling the Power of Multiple Gossip Steps: A Stability-Based Generalization Analysis in Decentralized Training
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Derives stability-based generalization and excess-error bounds for decentralized SGD with multiple gossip steps (DSGD-MGS) in non-convex settings without bounded gradients, showing exponential benefit from more gossip steps but a persistent gap to centralized mini-batch SGD.
Problem
Why multiple gossip steps (MGS) improve decentralized training and whether increasing gossip steps can close the generalization gap between decentralized and centralized SGD.
Approach
Uses l2 on-average model stability (instead of uniform stability) to bound generalization error of DSGD-MGS without bounded gradients, linking generalization to optimization error under a PL condition, which yields an exponential MGS benefit and a non-vanishing gap to centralized SGD.
Key results
- Generalization error bound for DSGD-MGS decays exponentially in the number of gossip steps Q, approximately O(exp(-delta*gamma*Q/4)) (per the paper's remark).
- As Q grows, DSGD-MGS bound approaches O(T^{2cβ/(2cβ+2)}/(n m^{1/(2cβ+2)})), still worse than centralized mini-batch SGD's O(T^{cβ/(cβ+1)}/(mn)).
- Experiments on CIFAR-10 (LeNet, Dir 0.3, 50 nodes, ring) show MGS=5 roughly halves weight distance versus MGS=1; even 20 gossip steps still underperform centralized mini-batch SGD.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase MGS steps from 1 to 5 | DSGD-MGS · CIFAR-10, LeNet, Dirichlet α=0.3 | weight distance | Helped |
| Increase MGS steps | DSGD-MGS · CIFAR-10 | generalization error | Helped |
| Increase MGS steps to 20 | DSGD-MGS · CIFAR-10, LeNet, Dirichlet 0.3, 50 nodes, ring topology | test accuracy | Hurt |
| Increase MGS steps to 20 | DSGD-MGS · CIFAR-10, LeNet, Dirichlet 0.3, 50 nodes, ring topology | training loss | Hurt |
| Use a smaller learning rate | DSGD-MGS · CIFAR-10 | generalization error | Helped |
| Use a smaller learning rate | DSGD-MGS · CIFAR-10 | excess error | Mixed |
| Increase the number of clients | DSGD-MGS · CIFAR-10 | generalization error | Helped |
| Increase per-client data size | DSGD-MGS · CIFAR-10 | excess error | Helped |
| Increase data heterogeneity | DSGD-MGS · CIFAR-10 | excess error | Hurt |
| Use a smaller spectral gap | DSGD-MGS · CIFAR-10 | generalization error | Mixed |
Surprising findings
- Even with arbitrarily many gossip steps, a non-vanishing generalization gap to centralized mini-batch SGD remains.
Limitations
- Optimization-error bound relies on the Polyak-Łojasiewicz condition for the last iterate, which is an added assumption.
- Experiments are limited to small models and CIFAR datasets with a LeNet architecture.
Experimental setup
Datasets: CIFAR-10 CIFAR-100
Benchmarks: CIFAR-10 CIFAR-100
Metrics: weight distance loss distance (test loss minus train loss) test accuracy test loss
Baselines: Mini-batch SGD DSGD-MGS with fewer gossip steps
Builds on: D-SGD on-average model stability uniform stability analysis of D-SGD Ye et al. heterogeneous D-SGD generalization
Closest papers by meaning
- On The Surprising Effectiveness of a Single Global Merging in Decentralized Learning (ICLR 2026 · similarity 0.91)
- Stability-Based Generalization Analysis of the Asynchronous Decentralized SGD (AAAI 2023 · similarity 0.89)
- Stability and Generalization Analysis of Decentralized SGD: Sharper Bounds Beyond Lipschitzness and Smoothness (ICML 2025 · similarity 0.88)
- Optimal Complexity in Decentralized Training (ICML 2021 · similarity 0.87)
- Towards Stability and Generalization Bounds in Decentralized Minibatch Stochastic Gradient Descent (AAAI 2024 · similarity 0.86)
- Achieving Linear Speedup and Near-Optimal Complexity for Decentralized Optimization over Row-stochastic Networks (ICML 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.