Research map / Optimization / Distributed and compressed
Towards Faster Decentralized Stochastic Optimization with Communication Compression
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 MoTEF, a decentralized SGD method combining momentum tracking with error feedback and contractive compression, achieving distributed-SGD asymptotic rate under arbitrary data heterogeneity without large batches, plus a STORM-based variance-reduced variant MoTEF-VR.
Problem
Decentralized non-convex stochastic optimization with contractive communication compression suffers from strong assumptions (bounded heterogeneity or gradients), large-batch requirements, and failure to achieve linear speedup with the number of clients.
Approach
Integrates error feedback (EF21-style gossip) with momentum tracking, where the gradient tracking step is applied to a Polyak momentum term rather than raw gradients, yielding convergence under arbitrary heterogeneity, small batches and linear speedup; a STORM-type variance-reduced variant further improves the rate.
Key results
- MoTEF attains asymptotic rate O(sigma^2/(n eps^4)) matching distributed SGD under arbitrary heterogeneity without large batches.
- MoTEF's convergence is much less sensitive to spectral gap rho than the 1/rho^3 theory suggests in experiments.
- MoTEF outperforms BEER, Choco-SGD, DSGD and D2 in communication complexity on non-convex logistic regression and MLP/CNN training on MNIST.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add momentum tracking and Error Feedback | Decentralized stochastic optimization with contractive compression · Non-convex, arbitrary data heterogeneity | asymptotic iteration complexity: \mathcal O(\nicefrac{\sigma^2}{n\varepsilon^4}) | Helped |
| Add momentum-based STORM-type variance reduction | MoTEF · Non-convex with mean-squared-smooth objectives | asymptotic iteration complexity: \frac{\ell F^0\sigma^2}{n\varepsilon^3} | Helped |
| Increase the number of clients | MoTEF · Synthetic least squares | error | Helped |
| Increase the number of clients | BEER · Synthetic least squares | error | No clear effect |
| Increase the momentum parameter λ (ablation) | MoTEF · Synthetic least squares, noisy regime | error | Hurt |
| Set λ=1, recovering BEER (ablation) | MoTEF · Synthetic least squares with noise in local gradients | convergence | Hurt |
| Remove EF21-type Error Feedback or Gradient Tracking (ablation) | MoTEF · Decentralized learning with heterogeneous data | data heterogeneity requirements | Hurt |
| Increase data heterogeneity | MoTEF · Synthetic least squares | performance | No clear effect |
| Increase data heterogeneity | Choco-SGD · Synthetic least squares | performance | Hurt |
| Change the network topology | MoTEF · Non-convex logistic regression | convergence | No clear effect |
| Use momentum tracking rather than BEER's approach | MoTEF · MNIST MLP | test accuracy communication complexity | Helped |
Surprising findings
- Empirical convergence of MoTEF is much less sensitive to the spectral gap than the theoretical 1/rho^3 dependence predicts.
- Choco-SGD performance degrades as data heterogeneity increases while BEER and MoTEF are unaffected.
Limitations
- Spectral gap dependence 1/rho^3 is sub-optimal in theory for the deterministic term.
- Large constants in step size and Lyapunov choices (e.g., c_eta=1e-5) found via trial and error and symbolic verification.
- MoTEF-VR rate under Polyak-Lojasiewicz condition not analyzed.
Experimental setup
Datasets: synthetic least squares LibSVM datasets MNIST
Benchmarks: synthetic least squares non-convex logistic regression on LibSVM MNIST MLP MNIST CNN
Metrics: error / suboptimality training gradient norm test accuracy communication complexity
Baselines: BEER CHOCO-SGD DSGD D2 CEDAS DoCoM
Builds on: EF21 BEER CHOCO-SGD STORM gradient tracking
Closest papers by meaning
- Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication (ICML 2019 · similarity 0.93)
- Accelerated Methods with Compressed Communications for Distributed Optimization Problems Under Data Similarity (AAAI 2025 · similarity 0.90)
- Scalable Distributed Stochastic Optimization via Bidirectional Compression: Beyond Pessimistic Limits (NeurIPS 2026 · similarity 0.90)
- Distributed Online Convex Optimization with Compressed Communication: Optimal Regret and Applications (NeurIPS 2026 · similarity 0.90)
- Revisiting Decentralized Online Convex Optimization with Compressed Communication (NeurIPS 2026 · similarity 0.89)
- Improving the Worst-Case Bidirectional Communication Complexity for Nonconvex Distributed Optimization under Function Similarity (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.