Research map / Optimization / Distributed and compressed
A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the unified analysis for local SGD on convex objectives | Local SGD · Convex non-iid | iterations to ε accuracy | Helped |
| Use the unified analysis for local SGD on non-convex objectives | Local SGD · Non-convex non-iid | iterations to ε accuracy | No clear effect |
| Allow mixing topologies to change and be sampled over time | Decentralized SGD · Changing-topology decentralized optimization | convergence guarantee | Helped |
| Assume expected consensus progress over compositions of mixing steps rather than requiring progress at every step | Decentralized SGD · Time-varying or randomized networks | convergence guarantee | Helped |
| Increase function diversity between workers when stochastic noise is zero | Decentralized SGD · Strongly convex heterogeneous objectives | convergence rate: \tilde \cO \left( \frac{L \tau^2 \bar\zeta^2}{\mu^2 p^2 T^2} + \frac{L\tau R_0^2}{p} \exp\left[- \frac{\mu T p}{\tau L}\ | Hurt |
| Set worker function diversity and noise to zero | Decentralized SGD · Over-parametrized problems | convergence rate | Helped |
| Use a fully connected graph with one mixing step per iteration | Decentralized SGD · Strongly convex, τ = 1, p = 1 | convergence rate: \tilde\cO \left(\frac{\bar\sigma^2}{n \mu T} + \frac{L (\bar\zeta^2 + p \bar\sigma^2) (1 - p)}{\mu^2 p^2 T^2} + \frac{LR | Helped |
| Increase noise while holding network topology and function similarity fixed | Decentralized SGD · Strongly convex least-squares experiment | iterations to target accuracy | No clear effect |
| Increase function diversity by a factor of 10 with zero stochastic noise | Decentralized SGD · Strongly convex least-squares experiment, ring and torus | iterations to target accuracy: approximately by a factor of \sqrt{10} | Hurt |
| Use a ring rather than a torus topology | Decentralized SGD · Strongly convex least-squares experiment | iterations to target accuracy: approximately linear in the ratio of their mixing parameters p | Hurt |
Closest papers by meaning
- Improved Stability and Generalization Guarantees of the Decentralized SGD Algorithm (ICML 2024 · similarity 0.90)
- Enhancing Parallelism in Decentralized Stochastic Convex Optimization (ICML 2025 · similarity 0.90)
- Towards Stability and Generalization Bounds in Decentralized Minibatch Stochastic Gradient Descent (AAAI 2024 · similarity 0.89)
- Stability and Generalization of Zeroth-Order Decentralized Stochastic Gradient Descent with Changing Topology (AAAI 2025 · similarity 0.89)
- Decentralized Convex Finite-Sum Optimization with Better Dependence on Condition Numbers (ICML 2024 · similarity 0.89)
- Stability and Generalization Analysis of Decentralized SGD: Sharper Bounds Beyond Lipschitzness and Smoothness (ICML 2025 · 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.