Research map / Optimization / Implicit bias and generalization
Improved Stability and Generalization Guarantees of the Decentralized SGD Algorithm
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.
Shows that decentralized SGD (both variants) recovers centralized-SGD-style on-average stability generalization bounds independent of the communication graph, and derives an optimization-dependent bound where poorly connected graphs can help generalization.
Problem
Generalization error of decentralized SGD (D-SGD) and whether the communication graph (poor connectivity) harms generalization, given contradictory prior results for the two D-SGD variants.
Approach
Uses on-average model stability with a tighter analysis of D-SGD Variant B that avoids controlling consensus distance, showing the generalization bound matches centralized SGD for any mixing matrix; further derives an optimization-dependent bound where graph choice can matter and sparse graphs may help.
Key results
- For convex and mu-strongly convex Lipschitz smooth losses, D-SGD Variant B obtains generalization bound T/(mn) (convex) and 1/(mu mn) (strongly convex), independent of the communication graph, matching centralized SGD.
- For bounded non-convex losses, the bound is T^{a}/(m^{1-a} n), removing the graph-dependent additive term of prior work.
- An optimization-dependent bound shows that for low-noise regimes, the identity graph (local SGD) gives the best empirical and bound-based generalization, so poorly connected graphs can help generalization.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace the prior Variant B stability analysis with the on-average model stability analysis | D-SGD Variant B · Convex | generalization error upper bound: \frac{T}{mn}+\frac{T}{\rho} -> \frac{T}{mn} | Helped |
| Replace the prior Variant B stability analysis with the on-average model stability analysis | D-SGD Variant B · Strongly convex | generalization error upper bound: \frac{1}{\mu mn}+\frac{1}{\mu\rho} -> \frac{1}{\mu mn} | Helped |
| Replace the prior Variant B stability analysis with on-average model stability | D-SGD Variant B · Non-convex | generalization error upper bound: \frac{T^{a}}{n} + C_\rho T^{a} -> \frac{T^{a}}{m^{1-a}n} | Helped |
| Use Variant B instead of Variant A | D-SGD · Convex and strongly convex | generalization error upper bound | No clear effect |
| Use Variant B instead of Variant A | D-SGD · Non-convex | generalization error upper bound | No clear effect |
| Use poorly-connected communication graphs rather than a connected graph | D-SGD worst-case generalization analysis · Convex, strongly convex, and non-convex | generalization error upper bound | No clear effect |
| Use an optimization-dependent bound instead of a worst-case bound | D-SGD · Low-noise regime | generalization error upper bound: \mathcal{O}(\frac{T}{mn}) -> \mathcal{O}(\frac{\sqrt{T}}{mn}) | Helped |
| Use the identity communication graph | D-SGD · Low-noise regime | empirical generalization error | Helped |
| Use different communication graphs | D-SGD · Noisy regime | empirical generalization error | No clear effect |
| Use the identity graph rather than the complete graph | D-SGD · Low-noise generalization | generalization error upper bound: C_W=0 for W=I; C_W=1 for W=\frac{1}{m}\1\1^T | Helped |
Surprising findings
- Poorly connected graphs, including the identity graph (local SGD), can be beneficial for generalization in low-noise regimes.
- A previously published D-SGD non-convex generalization bound (Sun et al.) contains a mistake in its proof.
Limitations
- Assumes Lipschitz and smooth losses, which may be relaxed in future work.
- Optimization error for the full empirical risk requires a connected graph, so the excess-risk picture still depends on the graph.
- Non-convex excess risk cannot be bounded with the same discussion as convex case.
Experimental setup
Metrics: generalization error bound empirical generalization gap
Baselines: Sun et al. 2021 D-SGD Variant B generalization bound Taheri & Thrampoulidis D-SGD bound Richards & Kuzborskij Variant A bound centralized SGD bounds (Hardt et al. 2016; Lei & Ying 2020)
Builds on: on-average model stability (Lei & Ying 2020) D-SGD (Lian et al. 2017) Richards & Kuzborskij decentralized stability analysis Sun et al. D-SGD generalization analysis
Closest papers by meaning
- Stability and Generalization Analysis of Decentralized SGD: Sharper Bounds Beyond Lipschitzness and Smoothness (ICML 2025 · similarity 0.95)
- Towards Stability and Generalization Bounds in Decentralized Minibatch Stochastic Gradient Descent (AAAI 2024 · similarity 0.94)
- Error Analysis Affected by Heavy-Tailed Gradients for Non-Convex Pairwise Stochastic Gradient Descent (AAAI 2025 · similarity 0.91)
- Uniform Stability and Generalization Error of GD and SGD on Fixed-Point Parameters (NeurIPS 2026 · similarity 0.91)
- Stability and Generalization of Zeroth-Order Decentralized Stochastic Gradient Descent with Changing Topology (AAAI 2025 · similarity 0.90)
- Stability and Generalization of Asynchronous SGD: Sharper Bounds Beyond Lipschitz and Smoothness (NeurIPS 2024 · similarity 0.89)
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.