Timezone: »

 
Poster
Optimal Complexity in Decentralized Training
Yucheng Lu · Christopher De Sa

Tue Jul 20 09:00 AM -- 11:00 AM (PDT) @
in Poster Session 1 »

Decentralization is a promising method of scaling up parallel machine learning systems. In this paper, we provide a tight lower bound on the iteration complexity for such methods in a stochastic non-convex setting. Our lower bound reveals a theoretical gap in known convergence rates of many existing decentralized training algorithms, such as D-PSGD. We prove by construction this lower bound is tight and achievable. Motivated by our insights, we further propose DeTAG, a practical gossip-style decentralized algorithm that achieves the lower bound with only a logarithm gap. Empirically, we compare DeTAG with other decentralized algorithms on image classification tasks, and we show DeTAG enjoys faster convergence compared to baselines, especially on unshuffled data and in sparse networks.

Keywords: Distributed and Parallel Optimization

Author Information

Yucheng Lu (Cornell University)
Christopher De Sa (Cornell)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors