Research map / Optimization / Nonconvex and smooth optimization
Stability and Generalization Analysis of Decentralized SGD: Sharper Bounds Beyond Lipschitzness and Smoothness
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.
Gives on-average model stability and generalization/excess-risk bounds for decentralized SGD on convex smooth and nonsmooth (Hölder-gradient) losses, removing Lipschitz and bounded-variance assumptions.
Problem
Generalization of decentralized SGD (D-SGD) is poorly understood; existing stability bounds require Lipschitzness or bounded variance and fail to give fast rates in low-noise settings or optimal rates for nonsmooth problems.
Approach
Uses on-average model stability with an error decomposition exploiting co-coercivity of smooth convex losses to offset the neighboring consensus error, yielding stability bounds that involve training errors (so optimization helps generalization) without Lipschitz assumptions.
Key results
- For convex smooth losses, D-SGD is shown on-average model stable with bounds involving training errors, removing Lipschitzness and giving fast O(1/(mn)) excess risk under low noise.
- For convex Lipschitz losses, excess risk of order O(1/sqrt(mn)) is obtained, matching minimax rates, removing the bounded-variance and Lipschitz-based uniform convergence assumptions of prior work.
- For nonsmooth Hölder-gradient losses, the paper gives the first optimal stability-based generalization bounds for D-SGD.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| remove the Lipschitzness assumption from the smooth convex stability analysis | D-SGD · Convex and smooth problems | on-average model stability | Helped |
| use training-error-dependent stability bounds instead of bounds requiring bounded variance and Lipschitzness | D-SGD · Convex and smooth problems | generalization rate in the low-noise condition: O(1/(mn)) | Helped |
| use the proposed optimization analysis without a Lipschitzness assumption | D-SGD · Convex and smooth problems | optimization error in the interpolation setting: O(1/T) | Helped |
| apply the proposed stability and excess-risk analysis to convex Lipschitz problems without the uniform-convergence assumption | D-SGD · Convex and Lipschitz problems | excess risk: O(1/√mn); 1/(mn)^(1/3) | Helped |
Limitations
- Analysis restricted to convex problems; nonconvex settings such as neural networks left open
- Excess risk bounds only in expectation, not high-probability
- Some bounds rely on step size conditions (eta ≲ (1-λ)/L) and n ≲ TL
Experimental setup
Metrics: on-average model stability generalization gap excess risk optimization error
Baselines: Richards and Rebeschini (2020) Sun et al. (2021) Zhu et al. (2022) Le Bars et al. (2024) Taheri and Thrampoulidis (2023)
Builds on: Lei and Ying (2020) on-average model stability D-SGD (Lian et al., 2017) Richards and Rebeschini (2020) Le Bars et al. (2024) Taheri and Thrampoulidis (2023)
Closest papers by meaning
- Improved Stability and Generalization Guarantees of the Decentralized SGD Algorithm (ICML 2024 · similarity 0.95)
- Towards Stability and Generalization Bounds in Decentralized Minibatch Stochastic Gradient Descent (AAAI 2024 · similarity 0.92)
- Stability and Generalization of Asynchronous SGD: Sharper Bounds Beyond Lipschitz and Smoothness (NeurIPS 2024 · similarity 0.91)
- Error Analysis Affected by Heavy-Tailed Gradients for Non-Convex Pairwise Stochastic Gradient Descent (AAAI 2025 · similarity 0.90)
- Uniform Stability and Generalization Error of GD and SGD on Fixed-Point Parameters (NeurIPS 2026 · similarity 0.89)
- Algorithmic Stability Unleashed: Generalization Bounds with Unbounded Losses (ICML 2024 · similarity 0.88)
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.