Research map / Optimization / Distributed and compressed
Enhancing Parallelism in Decentralized Stochastic Convex Optimization
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.
Proposes Decentralized Anytime SGD (DAT-SGD), which runs gossip-based Anytime SGD with gradients at slowly-moving averaged query points to reduce consensus bias, raising the decentralized parallelism bound from O(rho^{1/2} N^{1/4}) to O(rho sqrt(N)) for stochastic convex optimization.
Problem
Decentralized stochastic convex optimization suffers a parallelism limit: adding machines degrades convergence, and existing bounds leave a gap to centralized minibatch SGD even on well-connected topologies.
Approach
Extend Anytime SGD to the decentralized setting: each node computes stochastic gradients at averaged query points x_t that evolve more slowly than the iterates, and gossips both iterates and query points, which tightens the consensus-distance bias term and yields a larger parallelism threshold.
Key results
- Theory: DAT-SGD achieves rate O(sigma D/sqrt(MT) + D^{3/2} sqrt(L sigma~)/(rho T) + LD^2/T), giving parallelism bound M <= O(rho sqrt(N)) versus prior O(rho^{1/2} N^{1/4}) for D-SGD.
- Synthetic least squares: DAT-SGD's error keeps improving with more machines on torus and exponential graphs, and on the ring up to M=25, while D-SGD degrades from M=4 (ring) and M=9 (torus).
- Fashion MNIST with heterogeneous data (alpha=0.1): DAT-SGD outperforms D-SGD and D^2 on ring and Base-2 graph, but D-SGD and D^2 do better under homogeneous data.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use gradually shifting averaged query points for gradient evaluation, as in DAT-SGD rather than D-SGD | Decentralized SCO on ring and torus topologies · Decentralized SCO, ring and torus | parallelism bound: \mathcal{O}(N^{1/8}) -> \mathcal{O}(N^{1/6}); \mathcal{O}(N^{1/6}) -> \mathcal{O}(N^{1/4}) | Helped |
| Use gradually shifting averaged query points for gradient evaluation, as in DAT-SGD rather than D-SGD | Decentralized SCO on near-complete graphs · Decentralized SCO, near-complete graph | parallelism bound: \mathcal{O}(\rho^{1/2} N^{1/4}) -> \mathcal{O}(\rho\sqrt{N}) | Helped |
| Use DAT-SGD instead of prior decentralized methods | Decentralized SCO · Decentralized SCO | convergence rate | Helped |
| Use DAT-SGD instead of D-SGD | Synthetic least squares · Synthetic least squares, torus and 1-peer exponential graph | final error | Helped |
| Use DAT-SGD instead of D-SGD | Synthetic least squares · Synthetic least squares, ring | final error | Mixed |
| Use DAT-SGD instead of D-SGD and D² | LeNet on Fashion MNIST with heterogeneous data · Fashion MNIST, heterogeneous data (α=0.1), ring and Base-2 graph | test accuracy | Helped |
| Use DAT-SGD instead of D-SGD and D² | LeNet on Fashion MNIST · Fashion MNIST, nearly homogeneous data (α=10) | test accuracy | Hurt |
| Increase the number of machines using DAT-SGD rather than D-SGD or D² | LeNet on Fashion MNIST with heterogeneous data · Fashion MNIST, heterogeneous data (α=0.1), ring | test accuracy | Helped |
Surprising findings
- Under near-homogeneous data on Fashion MNIST, D-SGD and D^2 outperform DAT-SGD, contrary to the theory-driven expectation.
- On the ring topology the synthetic experiments show DAT-SGD eventually deteriorates beyond M between 25 and 49, consistent with the network-dependent term dominating.
Limitations
- Analysis restricted to convex, smooth objectives with symmetric doubly stochastic gossip matrices.
- Relies on bounded heterogeneity assumption; gradient tracking integration left open.
- Non-convex experiments use a heuristic momentum-like Anytime averaging without theory, and DAT-SGD underperforms under homogeneous data.
Experimental setup
Datasets: Fashion MNIST synthetic least squares
Benchmarks: Fashion MNIST synthetic least squares
Metrics: final error test accuracy
Baselines: D-SGD D^2 Minibatch SGD
Builds on: Anytime SGD Decentralized SGD D^2 gossip averaging
Closest papers by meaning
- Decentralized Non-convex Stochastic Optimization with Heterogeneous Variance (AAAI 2026 · similarity 0.91)
- Decentralized SGD and Average-direction SAM are Asymptotically Equivalent (ICML 2023 · similarity 0.91)
- Towards Stability and Generalization Bounds in Decentralized Minibatch Stochastic Gradient Descent (AAAI 2024 · similarity 0.90)
- A Unified Theory of Decentralized SGD with Changing Topology and Local Updates (ICML 2020 · similarity 0.90)
- Decentralized Convex Finite-Sum Optimization with Better Dependence on Condition Numbers (ICML 2024 · similarity 0.89)
- Improved Stability and Generalization Guarantees of the Decentralized SGD Algorithm (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.