Research map / Optimization / Distributed and compressed
Communication complexity theory
Prove lower bounds and communication-optimal distributed algorithms with compression.
35 accepted papers at ICML, NeurIPS, ICLR, CVPR and AAAI (2017–2026) · an approach in Distributed and compressed, keyword cluster “communication distributed · gradient compression · error feedback”
State History Tried Checklist Preprints Who Export
Where it stands
Not enough benchmark data Fewer than four papers report the same benchmark, so there is no record to follow.
6 papers in 2023–24 and 8 in 2025–26 (at ICML, NeurIPS, ICLR, CVPR and AAAI); its share of the topic grew, from 8.5% to 10.7%.
How this is decided
A benchmark is tracked when at least four papers of this approach report their own method on the same dataset and metric in at least two different years. Its record is the best number reported up to 2024 compared with the best reported in 2025–26: still improving means at least 1% better, flat means at most 0.2% better with at least two papers from 2025–26 trying. Numbers on a different scale from the rest (a fraction among percentages) and far outliers are left out. Results come from different papers with different setups, so they are signals, not head-to-head comparisons. The share of papers is counted at ICML, NeurIPS, ICLR, CVPR and AAAI.
How it got here
Most cited paper of each year
- 2017 · Communication-Efficient Stochastic Gradient Descent, with Applications to Neural Networks (NeurIPS 2017 · 4 citations)
- 2018 · Gradient Sparsification for Communication-Efficient Distributed Optimization (NeurIPS 2018 · 205 citations)
- 2019 · Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication (ICML 2019 · 177 citations)
- 2020 · Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization (ICML 2020 · 64 citations)
- 2021 · Linear Convergent Decentralized Optimization with Compression (ICLR 2021 · 21 citations)
- 2022 · 3PC: Three Point Compressors for Communication-Efficient Distributed Training and a Better Theory for Lazy Aggregation (ICML 2022 · 6 citations)
- 2023 · EF21-P and Friends: Improved Theoretical Communication Complexity for Distributed Optimization with Bidirectional Compression (ICML 2023 · 0 citations)
- 2024 · Det-CGD: Compressed Gradient Descent with Matrix Stepsizes for Non-Convex Optimization (ICLR 2024 · 0 citations)
- 2025 · Distributed Retraction-Free and Communication-Efficient Optimization on the Stiefel Manifold (ICML 2025 · 0 citations)
- 2026 · Convergence Analysis of the Lion Optimizer in Centralized and Distributed Settings (ICML 2026 · 0 citations)
Earliest papers here
- Communication-Efficient Stochastic Gradient Descent, with Applications to Neural Networks (NeurIPS 2017 · 4 citations)
- Gradient Sparsification for Communication-Efficient Distributed Optimization (NeurIPS 2018 · 205 citations)
- Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication (ICML 2019 · 177 citations)
What has been tried
27 papers here report 232 measured changes (a component added, removed or swapped, compared with a baseline): helped 68%, no clear effect 12%, hurt 16%, mixed 3%. Papers mostly publish changes that helped, so "helped" is over-represented.
Ablations in recent papers
| What was changed | Measured on | Result | Effect | Paper |
|---|---|---|---|---|
| use vanilla gradient compression without error feedback | Deterministic single-node Stiefel optimization · convergence to a stationary solution | Hurt | Distributed Retraction-Free and Communication-Efficient Optimization on the Stiefel Manifold (ICML 2025 · 0 citations) | |
| Increase the number of local steps K | Quadratic Games with stronger interaction · convergence per synchronization round | Helped | Decoupled SGDA for Games with Intermittent Strategy Communication (ICML 2025 · 0 citations) | |
| Increase the momentum parameter λ | Synthetic least squares, noisy regime · error | Hurt | Towards Faster Decentralized Stochastic Optimization with Communication Compression (ICLR 2025 · 0 citations) | |
| Add momentum to C-SOBA | Distributed bilevel optimization · convergence rate | C-SOBA: \mathcal{O}(1/\sqrt{nK}); CM-SOBA: \mathcal{O}(1/\sqrt{nK}) | Helped | Distributed Bilevel Optimization with Communication Compression (ICML 2024 · 0 citations) |
| Use a constant power policy instead of time-varying policies | CIFAR-10 · accuracy | Helped | LASER: Linear Compression in Wireless Distributed Optimization (ICML 2024 · 0 citations) |
What reviewers will expect
Datasets and baselines named in the 7 papers of this approach from 2024–2026 that have a full-text summary. Leaving out the common ones is a frequent review question.
Datasets
- MNIST · 4 of 7 papers
- CIFAR-10 · 4 of 7 papers
Recent preprints
Loading recent arXiv preprints…
Who publishes on it
Institutions on the most papers of this approach since 2023 (of 14 papers; from OpenAlex and the papers' affiliations).
- King Abdullah University of Science and Technology · 4 papers
- KAUST · 3 papers
- Peking University · 2 papers
Use it
Download BibTeX of 30 key papersOpen the topic in the interactive map
Get alerts. Describe your idea in scime atlas and save it (free scime account): you get a weekly email when new preprints land close to it.
Related approaches
Same keyword cluster
- Gradient quantization and sparsification (57 papers)
- Error feedback theory (17 papers)
Elsewhere in the topic
- Decentralized optimization algorithms (94 papers)
- Local and asynchronous SGD (84 papers)
- Byzantine-robust learning (32 papers)
- Compressed distributed optimization (30 papers)
Benchmark numbers, ablations and baseline numbers are extracted by AI from each paper's full text and can be wrong; the paper is the authority. Data: results index of 2026-11-02, citation counts from OpenAlex (2026-10-09).