Timezone: »

Towards Optimal Communication Complexity in Distributed Non-Convex Optimization
Kumar Kshitij Patel · Lingxiao Wang · Blake Woodworth · Brian Bullins · Nati Srebro

Thu Dec 01 09:00 AM -- 11:00 AM (PST) @ Hall J #936
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.

Author Information

Kumar Kshitij Patel (Toyota Technological Institute at Chicago)
Lingxiao Wang (Toyota Technological Institute Chicago)
Blake Woodworth (Inria)
Brian Bullins (Purdue University)
Nati Srebro (TTI-Chicago)

More from the Same Authors