![[Conference on Learning Theory Logo]](/image.pl?url=http%3a%2f%2fproceedings.mlr.press%2fv134%2fassets%2fimages%2flogo-pmlr.svg&f=jpg&w=240)
[edit]
The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication
Blake E Woodworth, Brian Bullins, Ohad Shamir, Nathan SrebroProceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:4386-4437, 2021.
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.
Cite this Paper
BibTeX
@InProceedings{pmlr-v134-woodworth21a, title = {The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication}, author = {Woodworth, Blake E and Bullins, Brian and Shamir, Ohad and Srebro, Nathan}, booktitle = {Proceedings of Thirty Fourth Conference on Learning Theory}, pages = {4386--4437}, year = {2021}, editor = {Belkin, Mikhail and Kpotufe, Samory}, volume = {134}, series = {Proceedings of Machine Learning Research}, month = {15--19 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v134/woodworth21a/woodworth21a.pdf}, url = {https://proceedings.mlr.press/v134/woodworth21a.html}, 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.}} Endnote
%0 Conference Paper%T The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication%A Blake E Woodworth%A Brian Bullins%A Ohad Shamir%A Nathan Srebro%B Proceedings of Thirty Fourth Conference on Learning Theory%C Proceedings of Machine Learning Research%D 2021%E Mikhail Belkin%E Samory Kpotufe%F pmlr-v134-woodworth21a%I PMLR%P 4386--4437%U https://proceedings.mlr.press/v134/woodworth21a.html%V 134%X 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. APA
Woodworth, B.E., Bullins, B., Shamir, O. & Srebro, N.. (2021). The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication.Proceedings of Thirty Fourth Conference on Learning Theory, inProceedings of Machine Learning Research 134:4386-4437 Available from https://proceedings.mlr.press/v134/woodworth21a.html.