# Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Construction

arXiv: https://arxiv.org/abs/2506.23836 · HTML: https://mlsanity.com/paper/2506.23836/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 28 of its 37 references that are in the map.
- First posted on arXiv 30 Jun 2025.

## Builds on (most cited first, 28 of 28)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimization](https://mlsanity.com/paper/1905.13727/) (2019)
- [The Convergence of Sparsified Gradient Methods](https://mlsanity.com/paper/1809.10505/) (2018)
- [On Biased Compression for Distributed Learning](https://mlsanity.com/paper/2002.12410/) (2020)
- [Lower Bounds for Finding Stationary Points I](https://mlsanity.com/paper/1710.11606/) (2017)
- [Distributed Learning with Compressed Gradient Differences](https://mlsanity.com/paper/1901.09269/) (2019)
- [Natural Compression for Distributed Deep Learning](https://mlsanity.com/paper/1905.10988/) (2019)
- [Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization](https://mlsanity.com/paper/2002.11364/) (2020)
- [MARINA: Faster Non-Convex Distributed Learning with Compression](https://mlsanity.com/paper/2102.07845/) (2021)
- [Optimal Complexity in Decentralized Training](https://mlsanity.com/paper/2006.08085/) (2020)
- [Uncertainty Principle for Communication Compression in Distributed and Federated Learning and the Search for an Optimal Compressor](https://mlsanity.com/paper/2002.08958/) (2020)
- [Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations](https://mlsanity.com/paper/2006.13476/) (2020)
- [Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimization](https://mlsanity.com/paper/2104.08708/) (2021)
- [Lower Bounds and Nearly Optimal Algorithms in Distributed Learning with Communication Compression](https://mlsanity.com/paper/2206.03665/) (2022)
- [Permutation Compressors for Provably Faster Distributed Nonconvex Optimization](https://mlsanity.com/paper/2110.03300/) (2021)
- [A Double Residual Compression Algorithm for Efficient Distributed Learning](https://mlsanity.com/paper/1910.07561/) (2019)
- [EF21-P and Friends: Improved Theoretical Communication Complexity for Distributed Optimization with Bidirectional Compression](https://mlsanity.com/paper/2209.15218/) (2022)
- [Optimal Time Complexities of Parallel Stochastic Optimization Methods Under a Fixed Computation Model](https://mlsanity.com/paper/2305.12387/) (2023)
- [DASHA: Distributed Nonconvex Optimization with Communication Compression, Optimal Oracle Complexity, and No Client Synchronization](https://mlsanity.com/paper/2202.01268/) (2022)
- [Faster Rates for Compressed Federated Learning with Client-Variance Reduction](https://mlsanity.com/paper/2112.13097/) (2021)
- [Unbiased Compression Saves Communication in Distributed Optimization: When and How Much?](https://mlsanity.com/paper/2305.16297/) (2023)
- [Shadowheart SGD: Distributed Asynchronous SGD with Optimal Time Complexity Under Arbitrary Computation and Communication Heterogeneity](https://mlsanity.com/paper/2402.04785/) (2024)
- [On the Optimal Time Complexities in Decentralized Stochastic Asynchronous Optimization](https://mlsanity.com/paper/2405.16218/) (2024)
- [Improving the Worst-Case Bidirectional Communication Complexity for Nonconvex Distributed Optimization under Function Similarity](https://mlsanity.com/paper/2402.06412/) (2024)

## Abstract (arXiv)

We consider centralized distributed optimization in the classical federated learning setup, where n workers jointly find an varepsilon-stationary point of an L-smooth, d-dimensional nonconvex function f, having access only to unbiased stochastic gradients with variance σ2. Each worker requires at most h seconds to compute a stochastic gradient, and the communication times from the server to the workers and from the workers to the server are τs and τw seconds per coordinate, respectively. One of the main motivations for distributed optimization is to achieve scalability with respect to n. For instance, it is well known that the distributed version of SGD has a variance-dependent runtime term frach σ2 L Deltan varepsilon2, which improves with the number of workers n, where Delta = f(x0) - f^*, and x0 ∈ Rd is the starting point. Similarly, using unbiased sparsification compressors, it is possible to reduce both the variance-dependent runtime term and the communication runtime term. However, once we account for the communication from the server to the workers τs, we prove that it becomes infeasible to design a method using unbiased random sparsification compressors that scales both the server-side communication runtime term τs d fracL Deltavarepsilon and the variance-dependent runtime term frach σ2 L Deltavarepsilon2, better than poly-logarithmically in n, even in the homogeneous (i.i.d.) case, where all workers access the same distribution. To establish this result, we construct a new "worst-case" function and develop a new lower bound framework that reduces the analysis to the concentration of a random sum, for which we prove a concentration bound. These results reveal fundamental limitations in scaling distributed optimization, even under the homogeneous assumption.