Research map / Learning theory and algorithms / Prediction and decision losses
Improving the Worst-Case Bidirectional Communication Complexity for Nonconvex Distributed Optimization under Function Similarity
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 MARINA-P, a primal downlink compression method using correlated (Perm K) compressors whose server-to-worker communication complexity improves with the number of workers under a functional (L_A, L_B) similarity assumption, and M3, a bidirectional extension combining it with MARINA and momentum.
Problem
Server-to-worker (downlink) communication is often ignored or compressed in ways whose worst-case complexity does not improve with the number of workers in nonconvex distributed optimization.
Approach
Send different compressed messages to each worker using correlated compressors (Perm K whose average reconstructs the input exactly), so downlink cost can scale down with n under a function-similarity assumption; extend to bidirectional compression via MARINA-P plus MARINA uplink compression and a momentum step.
Key results
- MARINA-P with Perm K achieves s2w complexity O(d delta^0 L/(n eps) + d delta^0 L_A/eps), improving with n, versus GD's O(d delta^0 L/eps) lower bound for compressed methods.
- M3 achieves total (s2w + w2s) communication complexity O(d delta^0 L_max/(n^{1/3} eps) + d delta^0 L_A/eps).
- Experiments on quadratics with n in {10,100,1000} show MARINA-P with Perm K performs best and its rate improves with n, while EF21-P falls behind for n in {100,1000}.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use PermK instead of independent RandK compressors for downlink (ablation) | MARINA-P · Non-homogeneous quadratics | s2w communication complexity: $\frac{d \delta^0 \frac{1}{n} \sum_{i=1}^n \norm{\mathbf{A}_i}}{\sqrt{n} \varepsilon} + \frac{d \delta^0 \max_{i\in[n]} | Helped |
| Use PermK instead of sending the same RandK-compressed message to every worker (ablation) | MARINA-P · Quadratic optimization | gradient norm | Helped |
| Use independent RandK compressors instead of the same RandK-compressed message for all workers (ablation) | MARINA-P · Quadratic optimization | gradient norm | Helped |
| Increase the number of workers (ablation) | MARINA-P with PermK · Quadratic optimization | convergence rate | Helped |
| Increase the number of workers (ablation) | MARINA-P with independent RandK · Quadratic optimization | convergence rate | Helped |
| Increase the number of workers from 10 to 100 or 1000 (ablation) | EF21-P with TopK · Quadratic optimization | gradient norm | Hurt |
| Add a momentum step when combining MARINA-P with MARINA (ablation) | M3 · General nonconvex optimization | total communication complexity: $\mathcal{O}\left(\frac{d \delta^0 L_{\max}}{n^{1/3} \varepsilon} + \frac{d \delta^0 L_A}{\varepsilon}\right)$ | Helped |
| Use PermK downlink compression rather than SameRandK compression (ablation) | MARINA-P · General nonconvex optimization | s2w communication complexity | Helped |
Surprising findings
- EF21-P outperforms MARINA-P with independent Rand K for n=10 but falls behind for larger n.
- Naive combination of MARINA and MARINA-P without momentum gives no improvement over existing bounds.
Limitations
- Gains require small L_A (function similarity); no gain in worst case without similarity assumption.
- Perm K requires d >= n and divisibility assumptions in the main analysis.
- Experiments limited to synthetic quadratic problems.
Experimental setup
Benchmarks: synthetic quadratic optimization problem
Metrics: gradient norm vs number of coordinates sent from server
Baselines: GD EF21-P CORE MARINA DASHA Rand-MCM
Builds on: MARINA EF21-P Perm K Rand K
Closest papers by meaning
- 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)
- Towards Faster Decentralized Stochastic Optimization with Communication Compression (ICLR 2025 · similarity 0.89)
- Shadowheart SGD: Distributed Asynchronous SGD with Optimal Time Complexity Under Arbitrary Computation and Communication Heterogeneity (NeurIPS 2024 · similarity 0.88)
- Distributed Online Convex Optimization with Compressed Communication: Optimal Regret and Applications (NeurIPS 2026 · similarity 0.88)
- Near-Optimal Distributed Minimax Optimization under the Second-Order Similarity (NeurIPS 2024 · similarity 0.87)
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.