Research map / Optimization / Distributed and compressed

Scalable Distributed Stochastic Optimization via Bidirectional Compression: Beyond Pessimistic Limits

NeurIPS 2026 · Optimization › Distributed and compressed · approach: Communication complexity theory · 0 citations (OpenAlex)

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 Inkheart SGD (homogeneous) and M4 (heterogeneous) bidirectionally compressed stochastic methods that, under a Functional (L_A, L_B) inequality, beat the pessimistic lower bound and let both communication and statistical terms scale with the number of workers n.

Problem

Finding an epsilon-stationary point in distributed/federated stochastic nonconvex optimization with bidirectional communication costs; prior work shows a time-complexity lower bound that prevents communication and statistical terms from scaling with n under random sparsification.

Approach

Introduce a Functional (L_A, L_B) inequality on gradient differences that is necessary to escape the lower bound, and use it to design bidirectionally compressed methods (with probabilistic full synchronization and momentum-based gradient estimators) whose time complexities scale with n when L_A is small.

Key results

• Inkheart SGD achieves time complexity O(max{h, tau, kappa} L_max Delta/epsilon + d kappa L_A Delta/epsilon) in the homogeneous setting, which does not depend on d or sigma^2/epsilon when L_A is approximately 0.
• Proposition shows L_A = 0 for quadratic functions and L_A can be 20-200 times smaller than L in a CNN experiment.
• M4 extends the improvement to heterogeneous stochastic gradients with a time complexity that scales with n when L_A is small.

Surprising findings

• Under the standard assumptions the paper cites, the pessimistic lower bound implies that Synchronous SGD with minibatching cannot be beaten by random-sparsification methods alone.

Limitations

• Improvement depends on the structural assumption that L_A is small; worst case L_A = L gives no gain over baselines.
• Heterogeneous-time result can blow up if one worker's computation or communication time is very large, motivating a subset-selection algorithm.

Experimental setup

Metrics: time complexity iteration complexity

Baselines: Synchronous SGD SGD MARINA DASHA DIANA

Builds on: QSGD DIANA MARINA DASHA

Closest papers by meaning

• EF21-P and Friends: Improved Theoretical Communication Complexity for Distributed Optimization with Bidirectional Compression (ICML 2023 · similarity 0.92)
• Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization (ICML 2020 · similarity 0.91)
• Accelerated Methods with Compressed Communications for Distributed Optimization Problems Under Data Similarity (AAAI 2025 · similarity 0.91)
• Improving the Worst-Case Bidirectional Communication Complexity for Nonconvex Distributed Optimization under Function Similarity (NeurIPS 2024 · similarity 0.90)
• Distributed Online Convex Optimization with Compressed Communication: Optimal Regret and Applications (NeurIPS 2026 · similarity 0.90)
• Towards Faster Decentralized Stochastic Optimization with Communication Compression (ICLR 2025 · similarity 0.90)