# Communication Complexity of Distributed Convex Learning and Optimization

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

## Key facts

- Cited by 60 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Jun 2015.

## Built on by (most cited first, 30 of 60)

- [A Field Guide to Federated Optimization](https://mlsanity.com/paper/2107.06917/) (2021)
- [ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!](https://mlsanity.com/paper/2202.09357/) (2022)
- [Moshpit SGD: Communication-Efficient Decentralized Training on Heterogeneous Unreliable Devices](https://mlsanity.com/paper/2103.03239/) (2021)
- [Lower Bounds and Nearly Optimal Algorithms in Distributed Learning with Communication Compression](https://mlsanity.com/paper/2206.03665/) (2022)
- [An Experimental Study of Byzantine-Robust Aggregation Schemes in Federated Learning](https://mlsanity.com/paper/2302.07173/) (2023)
- [The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication](https://mlsanity.com/paper/2102.01583/) (2021)
- [Asynchronous Upper Confidence Bound Algorithms for Federated Linear Bandits](https://mlsanity.com/paper/2110.01463/) (2021)
- [Decentralized Local Stochastic Extra-Gradient for Variational Inequalities](https://mlsanity.com/paper/2106.08315/) (2021)
- [Federated Deep AUC Maximization for Heterogeneous Data with a Constant Communication Complexity](https://mlsanity.com/paper/2102.04635/) (2021)
- [FedShuffle: Recipes for Better Use of Local Work in Federated Learning](https://mlsanity.com/paper/2204.13169/) (2022)
- [Memory Bounds for the Experts Problem](https://mlsanity.com/paper/2204.09837/) (2022)
- [Communication-efficient SGD: From Local SGD to One-Shot Averaging](https://mlsanity.com/paper/2106.04759/) (2021)
- [Faster federated optimization under second-order similarity](https://mlsanity.com/paper/2209.02257/) (2022)
- [Acceleration in Distributed Optimization under Similarity](https://mlsanity.com/paper/2110.12347/) (2021)
- [Efficient Convex Optimization Requires Superlinear Memory](https://mlsanity.com/paper/2203.15260/) (2022)
- [Federated Learning with Regularized Client Participation](https://mlsanity.com/paper/2302.03662/) (2023)
- [Unbiased Compression Saves Communication in Distributed Optimization: When and How Much?](https://mlsanity.com/paper/2305.16297/) (2023)
- [Communication Efficient Federated Learning for Generalized Linear Bandits](https://mlsanity.com/paper/2202.01087/) (2022)
- [FedChain: Chained Algorithms for Near-Optimal Communication Cost in Federated Learning](https://mlsanity.com/paper/2108.06869/) (2021)
- [Stochastic Distributed Optimization under Average Second-order Similarity: Algorithms and Analysis](https://mlsanity.com/paper/2304.07504/) (2023)
- [Lower Bounds and Accelerated Algorithms in Distributed Stochastic Optimization with Communication Compression](https://mlsanity.com/paper/2305.07612/) (2023)
- [Optimal Gradient Sliding and its Application to Distributed Optimization Under Similarity](https://mlsanity.com/paper/2205.15136/) (2022)
- [Communication-Efficient Distributed Optimization with Quantized Preconditioners](https://mlsanity.com/paper/2102.07214/) (2021)
- [Distributed Saddle-Point Problems Under Similarity](https://mlsanity.com/paper/2107.10706/) (2021)
- [Compression and Data Similarity: Combination of Two Techniques for Communication-Efficient Solving of Distributed Variational Inequalities](https://mlsanity.com/paper/2206.09446/) (2022)
- [Two Losses Are Better Than One: Faster Optimization Using a Cheaper Proxy](https://mlsanity.com/paper/2302.03542/) (2023)
- [Similarity, Compression and Local Steps: Three Pillars of Efficient Communications for Distributed Variational Inequalities](https://mlsanity.com/paper/2302.07615/) (2023)
- [Quadratic Memory is Necessary for Optimal Query Complexity in Convex Optimization: Center-of-Mass is Pareto-Optimal](https://mlsanity.com/paper/2302.04963/) (2023)
- [FedSSO: A Federated Server-Side Second-Order Optimization Algorithm](https://mlsanity.com/paper/2206.09576/) (2022)
- [Delayed Projection Techniques for Linearly Constrained Problems: Convergence Rates, Acceleration, and Applications](https://mlsanity.com/paper/2101.01505/) (2021)

## Abstract (arXiv)

We study the fundamental limits to communication-efficient distributed methods for convex learning and optimization, under different assumptions on the information available to individual machines, and the types of functions considered. We identify cases where existing algorithms are already worst-case optimal, as well as cases where room for further improvement is still possible. Among other things, our results indicate that without similarity between the local objective functions (due to statistical data similarity or otherwise) many communication rounds may be required, even if the machines have unbounded computational power.