Towards Optimal Communication Complexity in Distributed Non-Convex Optimization
Kumar Kshitij Patel, Lingxiao Wang, Blake Woodworth, Brian Bullins, Nathan Srebro
Abstract
We study the problem of distributed stochastic non-convex optimization with intermittent communication. We consider the full participation setting where $M$ machines work in parallel over $R$ communication rounds and the partial participation setting where $M$ machines are sampled independently every round from some meta-distribution over machines. We propose and analyze a new algorithm that improves existing methods by requiring fewer and lighter variance reduction operations. We also present lower bounds, showing our algorithm is either $\textit{optimal}$ or $\textit{almost optimal}$ in most settings. Numerical experiments demonstrate the superior performance of our algorithm.
BibTeX
@inproceedings{
patel2022towards,
title={Towards Optimal Communication Complexity in Distributed Non-Convex Optimization},
author={Kumar Kshitij Patel and Lingxiao Wang and Blake Woodworth and Brian Bullins and Nathan Srebro},
booktitle={Advances in Neural Information Processing Systems},
editor={Alice H. Oh and Alekh Agarwal and Danielle Belgrave and Kyunghyun Cho},
year={2022},
url={https://openreview.net/forum?id=SNElc7QmMDe}
}