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

Blake Woodworth; Brian Bullins; Ohad Shamir; Nathan Srebro

IJCAI 2022poster60 citations

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

Blake Woodworth, Brian Bullins, Ohad Shamir, Nathan Srebro

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.

Artificial Intelligence: General

BibTeX

@inproceedings{ijcai2022p751,
  title     = {The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication (Extended Abstract)},
  author    = {Woodworth, Blake and Bullins, Brian and Shamir, Ohad and Srebro, Nathan},
  booktitle = {Proceedings of the Thirty-First International Joint Conference on
               Artificial Intelligence, {IJCAI-22}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Lud De Raedt},
  pages     = {5359--5363},
  year      = {2022},
  month     = {7},
  note      = {Sister Conferences Best Papers},
  doi       = {10.24963/ijcai.2022/751},
  url       = {https://doi.org/10.24963/ijcai.2022/751},
}