mlsanityData to 7 Oct 2026

The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication

arXiv 2102.01583 ↗First posted 2 Feb 2021cs.LG math.OCcited by 30

Not on the map. Why?

Abstract (arXiv)

We resolve the min-max complexity of distributed stochastic convex optimization (up to a log factor) in the intermittent communication setting, where M machines work in parallel over the course of R rounds of communication to optimize the objective, and during each round of communication, each machine may sequentially compute K stochastic gradient estimates. We present a novel lower bound with a matching upper bound that establishes an optimal algorithm.

Key facts. Cited by 30 papers in the map (data through 7 Oct 2026). Builds on 27 of its 58 references that are in the map. First posted on arXiv 2 Feb 2021.

Builds on

27 of 58 references.

References · 27

  1. 2019Advances and Open Problems in Federated Learningcited by 3,021
  2. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
  3. 2018Local SGD Converges Fast and Communicates Littlecited by 595
  4. 2020A Unified Theory of Decentralized SGD with Changing Topology and Local Updatescited by 361
  5. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 303
  6. 2013Optimal rates for zero-order convex optimization: the power of two function evaluationscited by 190
  7. 2020Is Local SGD Better than Minibatch SGD?cited by 151
  8. 2020Minibatch vs Local SGD for Heterogeneous Distributed Learningcited by 147
  9. 2013Communication Efficient Distributed Optimization using an Approximate Newton-type Methodcited by 131
  10. 2017Lower Bounds for Finding Stationary Points Icited by 125
  11. 2018Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithmscited by 106
  12. 2019Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronizationcited by 106
15 more
  1. 2015An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedbackcited by 105
  2. 2020Federated Accelerated Stochastic Gradient Descentcited by 85
  3. 2015Communication Complexity of Distributed Convex Learning and Optimizationcited by 59
  4. 2015Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequalitycited by 50
  5. 2016Tight Complexity Bounds for Optimizing Composite Objectivescited by 47
  6. 2016AIDE: Fast and Communication Efficient Distributed Optimizationcited by 42
  7. 2018Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimizationcited by 34
  8. 2020Acceleration with a Ball Optimization Oraclecited by 31
  9. 2018New Convergence Aspects of Stochastic Gradient Algorithmscited by 30
  10. 2020Statistically Preconditioned Accelerated Gradient Method for Distributed Optimizationcited by 29
  11. 2018Global linear convergence of Newton's method without strong-convexity or Lipschitz gradientscited by 24
  12. 2021Accelerated, Optimal, and Parallel: Some Results on Model-Based Stochastic Optimizationcited by 14
  13. 2017Memory and Communication Efficient Distributed Stochastic Optimization with Minibatch-Proxcited by 12
  14. 2018On the Randomized Complexity of Minimizing a Convex Quadratic Functioncited by 5
  15. 2020On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functionscited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 7; 2022: 5; 2023: 7; 2024: 5; 2025: 3; 2026: 3.

30 papers.

Sort:

By area:

  1. 2022ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!cited by 134
  2. 2021Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspectivecited by 38
  3. 2021Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyondcited by 35
  4. 2022A Communication-Efficient Distributed Gradient Clipping Algorithm for Training Deep Neural Networkscited by 20
  5. 2022Federated Optimization Algorithms with Random Reshuffling and Gradient Compressioncited by 18
  6. 2022Faster federated optimization under second-order similaritycited by 18
  7. 2023ReSQueing Parallel and Private Stochastic Convex Optimizationcited by 17
  8. 2022Efficient Convex Optimization Requires Superlinear Memorycited by 14
  9. 2024The Limits and Potentials of Local SGD for Distributed Heterogeneous Learning with Intermittent Communicationcited by 12
  10. 2024Task Arithmetic Through The Lens Of One-Shot Federated Learningcited by 12
  11. 2021FedChain: Chained Algorithms for Near-Optimal Communication Cost in Federated Learningcited by 10
  12. 2021On Second-order Optimization Methods for Federated Learningcited by 9
18 more
  1. 2024The Sample-Communication Complexity Trade-off in Federated Q-Learningcited by 8
  2. 2023EPISODE: Episodic Gradient Clipping with Periodic Resampled Corrections for Federated Learning with Heterogeneous Datacited by 7
  3. 2023Similarity, Compression and Local Steps: Three Pillars of Efficient Communications for Distributed Variational Inequalitiescited by 7
  4. 2023Federated Online and Bandit Convex Optimizationcited by 7
  5. 2021A Stochastic Newton Algorithm for Distributed Convex Optimizationcited by 6
  6. 2024On the Necessity of Collaboration for Online Model Selection with Decentralized Datacited by 6
  7. 2023Quadratic Memory is Necessary for Optimal Query Complexity in Convex Optimization: Center-of-Mass is Pareto-Optimalcited by 5
  8. 2021Statistical Estimation and Inference via Local SGD in Federated Learningcited by 2
  9. 2023DualFL: A Duality-based Federated Learning Algorithm with Communication Acceleration in the General Convex Regimecited by 2
  10. 2023Distributed Extra-gradient with Optimal Complexity and Communication Guaranteescited by 2
  11. 2025On the Gradient Complexity of Private Optimization with Private Oraclescited by 2
  12. 2021On the Oracle Complexity of Higher-Order Smooth Non-Convex Finite-Sum Optimizationcited by 1
  13. 2025Characterizing the Accuracy-Communication-Privacy Trade-off in Distributed Stochastic Convex Optimizationcited by 1
  14. 2025Layer-wise Quantization for Quantized Optimistic Dual Averagingcited by 1
  15. 2024Accelerating Distributed Optimization: A Primal-Dual Perspective on Local Stepscited by 0
  16. 2026Distributed Direct Preference Optimizationcited by 0
  17. 2026Local MixVR: Breaking the Communication-Sample Dependence in Distributed Learningcited by 0
  18. 2026Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memorycited by 0