Data to 7 Oct 2026

Communication Complexity of Distributed Convex Learning and Optimization

arXiv 1506.01900 ↗First posted 5 Jun 2015cs.LG math.OC stat.MLcited by 59

Not on the map. Why?

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.

Key facts. Cited by 59 papers in the map (data through 7 Oct 2026). First posted on arXiv 5 Jun 2015.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 13; 2022: 13; 2023: 10; 2024: 9; 2025: 9; 2026: 5.

59 papers.

Sort:

2021A Field Guide to Federated Optimizationcited by 312
2022ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!cited by 134
2021Moshpit SGD: Communication-Efficient Decentralized Training on Heterogeneous Unreliable Devicescited by 36
2022Lower Bounds and Nearly Optimal Algorithms in Distributed Learning with Communication Compressioncited by 33
2023An Experimental Study of Byzantine-Robust Aggregation Schemes in Federated Learningcited by 32
2021Asynchronous Upper Confidence Bound Algorithms for Federated Linear Banditscited by 31
2021The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communicationcited by 30
2021Decentralized Local Stochastic Extra-Gradient for Variational Inequalitiescited by 25
2021Federated Deep AUC Maximization for Heterogeneous Data with a Constant Communication Complexitycited by 21
2022Memory Bounds for the Experts Problemcited by 20
2021Communication-efficient SGD: From Local SGD to One-Shot Averagingcited by 19
2022FedShuffle: Recipes for Better Use of Local Work in Federated Learningcited by 19

38 more

2022Faster federated optimization under second-order similaritycited by 18
2021Acceleration in Distributed Optimization under Similaritycited by 17
2022Efficient Convex Optimization Requires Superlinear Memorycited by 14
2023Unbiased Compression Saves Communication in Distributed Optimization: When and How Much?cited by 14
2022Communication Efficient Federated Learning for Generalized Linear Banditscited by 13
2023Federated Learning with Regularized Client Participationcited by 13
2023Stochastic Distributed Optimization under Average Second-order Similarity: Algorithms and Analysiscited by 11
2023Lower Bounds and Accelerated Algorithms in Distributed Stochastic Optimization with Communication Compressioncited by 11
2021FedChain: Chained Algorithms for Near-Optimal Communication Cost in Federated Learningcited by 10
2022Optimal Gradient Sliding and its Application to Distributed Optimization Under Similaritycited by 9
2021Distributed Saddle-Point Problems Under Similaritycited by 8
2022Compression and Data Similarity: Combination of Two Techniques for Communication-Efficient Solving of Distributed Variational Inequalitiescited by 8
2023Two Losses Are Better Than One: Faster Optimization Using a Cheaper Proxycited by 7
2023Similarity, Compression and Local Steps: Three Pillars of Efficient Communications for Distributed Variational Inequalitiescited by 7
2023Quadratic Memory is Necessary for Optimal Query Complexity in Convex Optimization: Center-of-Mass is Pareto-Optimalcited by 5
2022FedSSO: A Federated Server-Side Second-Order Optimization Algorithmcited by 3
2021Delayed Projection Techniques for Linearly Constrained Problems: Convergence Rates, Acceleration, and Applicationscited by 2
2021CDMA: A Practical Cross-Device Federated Learning Algorithm for General Minimax Problemscited by 2
2021Gradual Federated Learning with Simulated Annealingcited by 2
2022STSyn: Speeding Up Local SGD with Straggler-Tolerant Synchronizationcited by 2
2023DualFL: A Duality-based Federated Learning Algorithm with Communication Acceleration in the General Convex Regimecited by 2
2024Accelerated Stochastic ExtraGradient: Mixing Hessian and Gradient Similarity to Reduce Communication in Distributed and Federated Learningcited by 2
2024Accelerated Methods with Compressed Communications for Distributed Optimization Problems under Data Similaritycited by 2
2025On the Gradient Complexity of Private Optimization with Private Oraclescited by 2
2022SADAM: Stochastic Adam, A Stochastic Operator for First-Order Gradient-based Optimizercited by 1
2023Distributed Semi-Supervised Sparse Statistical Inferencecited by 1
2024Optimal Data Splitting in Distributed Optimization for Machine Learningcited by 1
2024Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networkscited by 1
2024Local Methods with Adaptivity via Scalingcited by 1
2024FedSlate:A Federated Deep Reinforcement Learning Recommender Systemcited by 1
2025Characterizing the Accuracy-Communication-Privacy Trade-off in Distributed Stochastic Convex Optimizationcited by 1
2025Constant Stepsize Local GD for Logistic Regression: Acceleration by Instabilitycited by 1
2025Non-Convex Federated Optimization under Cost-Aware Client Selectioncited by 1
2026Tight Analysis of Decentralized SGD: A Markov Chain Perspectivecited by 1
2026Information-Theoretic Lower Bounds for Bit-Constrained Stochastic Optimization via a Reduction to Compressed Gaussian Mean Estimationcited by 1
2022Parameter Averaging for Feature Rankingcited by 0
2024Near-Optimal Distributed Minimax Optimization under the Second-Order Similaritycited by 0
2024Refined Analysis of Federated Averaging and Federated Richardson-Rombergcited by 0

50 most cited of 59 All 59 (JSON)