Research map / Optimization / Distributed and compressed
Unbiased Compression Saves Communication in Distributed Optimization: When and How Much?
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 |
|---|---|---|---|
| Assume worker compressors are mutually independent rather than only unbiased | Distributed optimization with unbiased compression · Generally-convex and strongly-convex functions | total communication cost: up to Θ(√min{n, κ}) | Helped |
| Use unbiased compression without assuming independence | Distributed optimization · Convex optimization | total communication cost: same order as without compression | No clear effect |
| Use independent rather than shared-randomness random-s compressors | ADIANA · Delicate quadratic problem | total communicated bits | Helped |
| Increase compression aggressiveness by using a larger ω | Independent random-s compressors · Delicate quadratic problem | total communicated bits | Helped |
| Refine the parameter choice and Lyapunov analysis without changing the algorithm | ADIANA · Strongly-convex functions | communication rounds: nearly matches the lower bound up to a ln(κ) factor | Helped |
| Use ADIANA with independent random-s compression | ADIANA · Synthetic least squares | total communication cost | Helped |
| Use ADIANA with independent random-s compression | ADIANA · a9a and w8a logistic regression | total communication cost | Helped |
Closest papers by meaning
- Lower Bounds and Nearly Optimal Algorithms in Distributed Learning with Communication Compression (NeurIPS 2022 · similarity 0.94)
- Improving the Worst-Case Bidirectional Communication Complexity for Nonconvex Distributed Optimization under Function Similarity (NeurIPS 2024 · similarity 0.92)
- Accelerated Methods with Compressed Communications for Distributed Optimization Problems Under Data Similarity (AAAI 2025 · similarity 0.92)
- Distributed Online Convex Optimization with Compressed Communication: Optimal Regret and Applications (NeurIPS 2026 · similarity 0.91)
- Towards Faster Decentralized Stochastic Optimization with Communication Compression (ICLR 2025 · similarity 0.90)
- Scalable Distributed Stochastic Optimization via Bidirectional Compression: Beyond Pessimistic Limits (NeurIPS 2026 · similarity 0.90)
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.