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

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

## Key facts

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

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

- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [A Unified Theory of Decentralized SGD with Changing Topology and Local Updates](https://mlsanity.com/paper/2003.10422/) (2020)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [Optimal rates for zero-order convex optimization: the power of two function evaluations](https://mlsanity.com/paper/1312.2139/) (2013)
- [Is Local SGD Better than Minibatch SGD?](https://mlsanity.com/paper/2002.07839/) (2020)
- [Minibatch vs Local SGD for Heterogeneous Distributed Learning](https://mlsanity.com/paper/2006.04735/) (2020)
- [Communication Efficient Distributed Optimization using an Approximate Newton-type Method](https://mlsanity.com/paper/1312.7853/) (2013)
- [Lower Bounds for Finding Stationary Points I](https://mlsanity.com/paper/1710.11606/) (2017)
- [An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback](https://mlsanity.com/paper/1507.08752/) (2015)
- [Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization](https://mlsanity.com/paper/1910.13598/) (2019)
- [Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms](https://mlsanity.com/paper/1808.07576/) (2018)
- [Federated Accelerated Stochastic Gradient Descent](https://mlsanity.com/paper/2006.08950/) (2020)
- [Communication Complexity of Distributed Convex Learning and Optimization](https://mlsanity.com/paper/1506.01900/) (2015)
- [Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality](https://mlsanity.com/paper/1506.07216/) (2015)
- [Tight Complexity Bounds for Optimizing Composite Objectives](https://mlsanity.com/paper/1605.08003/) (2016)
- [AIDE: Fast and Communication Efficient Distributed Optimization](https://mlsanity.com/paper/1608.06879/) (2016)
- [Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization](https://mlsanity.com/paper/1805.10222/) (2018)
- [Acceleration with a Ball Optimization Oracle](https://mlsanity.com/paper/2003.08078/) (2020)
- [New Convergence Aspects of Stochastic Gradient Algorithms](https://mlsanity.com/paper/1811.12403/) (2018)
- [Statistically Preconditioned Accelerated Gradient Method for Distributed Optimization](https://mlsanity.com/paper/2002.10726/) (2020)
- [Global linear convergence of Newton's method without strong-convexity or Lipschitz gradients](https://mlsanity.com/paper/1806.00413/) (2018)
- [Accelerated, Optimal, and Parallel: Some Results on Model-Based Stochastic Optimization](https://mlsanity.com/paper/2101.02696/) (2021)
- [Memory and Communication Efficient Distributed Stochastic Optimization with Minibatch-Prox](https://mlsanity.com/paper/1702.06269/) (2017)
- [On the Randomized Complexity of Minimizing a Convex Quadratic Function](https://mlsanity.com/paper/1807.09386/) (2018)
- [On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions](https://mlsanity.com/paper/2002.03273/) (2020)

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

- [ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!](https://mlsanity.com/paper/2202.09357/) (2022)
- [Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspective](https://mlsanity.com/paper/2111.03741/) (2021)
- [Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond](https://mlsanity.com/paper/2110.10342/) (2021)
- [A Communication-Efficient Distributed Gradient Clipping Algorithm for Training Deep Neural Networks](https://mlsanity.com/paper/2205.05040/) (2022)
- [Federated Optimization Algorithms with Random Reshuffling and Gradient Compression](https://mlsanity.com/paper/2206.07021/) (2022)
- [Faster federated optimization under second-order similarity](https://mlsanity.com/paper/2209.02257/) (2022)
- [ReSQueing Parallel and Private Stochastic Convex Optimization](https://mlsanity.com/paper/2301.00457/) (2023)
- [Efficient Convex Optimization Requires Superlinear Memory](https://mlsanity.com/paper/2203.15260/) (2022)
- [The Limits and Potentials of Local SGD for Distributed Heterogeneous Learning with Intermittent Communication](https://mlsanity.com/paper/2405.11667/) (2024)
- [Task Arithmetic Through The Lens Of One-Shot Federated Learning](https://mlsanity.com/paper/2411.18607/) (2024)
- [FedChain: Chained Algorithms for Near-Optimal Communication Cost in Federated Learning](https://mlsanity.com/paper/2108.06869/) (2021)
- [On Second-order Optimization Methods for Federated Learning](https://mlsanity.com/paper/2109.02388/) (2021)
- [The Sample-Communication Complexity Trade-off in Federated Q-Learning](https://mlsanity.com/paper/2408.16981/) (2024)
- [EPISODE: Episodic Gradient Clipping with Periodic Resampled Corrections for Federated Learning with Heterogeneous Data](https://mlsanity.com/paper/2302.07155/) (2023)
- [Similarity, Compression and Local Steps: Three Pillars of Efficient Communications for Distributed Variational Inequalities](https://mlsanity.com/paper/2302.07615/) (2023)
- [Federated Online and Bandit Convex Optimization](https://mlsanity.com/paper/2311.17586/) (2023)
- [A Stochastic Newton Algorithm for Distributed Convex Optimization](https://mlsanity.com/paper/2110.02954/) (2021)
- [On the Necessity of Collaboration for Online Model Selection with Decentralized Data](https://mlsanity.com/paper/2404.09494/) (2024)
- [Quadratic Memory is Necessary for Optimal Query Complexity in Convex Optimization: Center-of-Mass is Pareto-Optimal](https://mlsanity.com/paper/2302.04963/) (2023)
- [Statistical Estimation and Inference via Local SGD in Federated Learning](https://mlsanity.com/paper/2109.01326/) (2021)
- [DualFL: A Duality-based Federated Learning Algorithm with Communication Acceleration in the General Convex Regime](https://mlsanity.com/paper/2305.10294/) (2023)
- [Distributed Extra-gradient with Optimal Complexity and Communication Guarantees](https://mlsanity.com/paper/2308.09187/) (2023)
- [On the Gradient Complexity of Private Optimization with Private Oracles](https://mlsanity.com/paper/2511.13999/) (2025)
- [On the Oracle Complexity of Higher-Order Smooth Non-Convex Finite-Sum Optimization](https://mlsanity.com/paper/2103.05138/) (2021)
- [Characterizing the Accuracy-Communication-Privacy Trade-off in Distributed Stochastic Convex Optimization](https://mlsanity.com/paper/2501.03222/) (2025)
- [Layer-wise Quantization for Quantized Optimistic Dual Averaging](https://mlsanity.com/paper/2505.14371/) (2025)
- [Accelerating Distributed Optimization: A Primal-Dual Perspective on Local Steps](https://mlsanity.com/paper/2407.02689/) (2024)
- [Distributed Direct Preference Optimization](https://mlsanity.com/paper/2605.20696/) (2026)
- [Local MixVR: Breaking the Communication-Sample Dependence in Distributed Learning](https://mlsanity.com/paper/2606.01128/) (2026)
- [Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory](https://mlsanity.com/paper/2607.24827/) (2026)

## 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.