Tyurin (2025) — ARXIV-2506.23836
Key takeaways
This paper proves a nearly tight lower bound showing that, even in the homogeneous (i.i.d.) setting, no algorithm using unbiased random sparsification compressors can simultaneously scale both the server-to- worker communication cost (tau_s * d * LDelta/eps) and the variance- dependent cost (h * sigma^2 * LDelta / eps^2) better than poly- logarithmically in the number of workers n. The result is established via a new worst-case function construction F_{T,K,a} and a novel proof framework reducing the bound to a concentration inequality for a random sum.
- Theorem 1.6 / Theorem 4.2 (main lower bound). Any zero-respecting algorithm using U(omega) compressors requires at least Omega(tau_s * d * LDelta / (eps * log^4(n))) + Omega(h * sigma^2 * LDelta / (eps^2 * log^6(n))) time, even in the homogeneous i.i.d. setting with n workers. Holds when: Non-convex L-smooth objective; n workers; unbiased random sparsification compressors with variance parameter omega; tau_s > 0 S2W communication cost; gradient variance sigma^2; Delta = f(x_0) - f*.
- Corollary (tau_s ≈ tau_w regime). When server-to-worker bandwidth equals worker-to-server bandwidth, no compression algorithm achieves asymptotically better complexity than Batch Synchronized SGD without compression. Holds when: tau_s = tau_w; homogeneous i.i.d. setting; unbiased sparsification compressors.
What the evidence does not cover
- The lower bound applies specifically to unbiased random sparsification compressors; the paper conjectures but does not prove the bound holds for all unbiased compressors (the uncertainty principle provides a partial argument).
- The bound is tight only up to poly-logarithmic factors (log^4 to log^6 in n); whether logarithms can be eliminated is an open problem.
- The lower bound is for nonconvex objectives; convexity or second-order smoothness may allow stronger scalability and break the pessimistic bound.
- The result applies to zero-respecting algorithms; non-zero-respecting algorithms (unusual in practice) are not covered.
- Practical compressors like Top-K and Rank-K often perform much better than worst-case analysis predicts, so the bound may be overly pessimistic for specific architectures.
Standing in the anthology
Read — the reading is NOTE-107. Arrived in the imported batch, which brought in the communication-compression branch.