The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication (Extended Abstract)

Blake E. Woodworth, Brian Bullins, Ohad Shamir, Nathan Srebro

IJCAI 2022 pp. 5359-5363

doi:10.24963/IJCAI.2022/751 /ijcai/2022/woodworth2022ijcai-min/

Abstract

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.

PDF IJCAI Semantic Scholar

Cite

Text

Woodworth et al. "The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication (Extended Abstract)." International Joint Conference on Artificial Intelligence, 2022. doi:10.24963/IJCAI.2022/751

Markdown

[Woodworth et al. "The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication (Extended Abstract)." International Joint Conference on Artificial Intelligence, 2022.](https://mlanthology.org/ijcai/2022/woodworth2022ijcai-min/) doi:10.24963/IJCAI.2022/751

BibTeX

@inproceedings{woodworth2022ijcai-min,
  title     = {{The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication (Extended Abstract)}},
  author    = {Woodworth, Blake E. and Bullins, Brian and Shamir, Ohad and Srebro, Nathan},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2022},
  pages     = {5359-5363},
  doi       = {10.24963/IJCAI.2022/751},
  url       = {https://mlanthology.org/ijcai/2022/woodworth2022ijcai-min/}
}