Optimal Complexity in Decentralized Training. (arXiv:2006.08085v4 [cs.LG] UPDATED)

Web: http://arxiv.org/abs/2006.08085

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 …

arxiv complexity decentralized training