  In decentralized machine learning, workers compute model updates on their
local data. Because the workers only communicate with few neighbors without
central coordination, these updates propagate progressively over the network.
This paradigm enables distributed training on networks without all-to-all
connectivity, helping to protect data privacy as well as to reduce the
communication cost of distributed training in data centers. A key challenge,
primarily in decentralized deep learning, remains the handling of differences
between the workers' local data distributions. To tackle this challenge, we
introduce the RelaySum mechanism for information propagation in decentralized
learning. RelaySum uses spanning trees to distribute information exactly
uniformly across all workers with finite delays depending on the distance
between nodes. In contrast, the typical gossip averaging mechanism only
distributes data uniformly asymptotically while using the same communication
volume per step as RelaySum. We prove that RelaySGD, based on this mechanism,
is independent of data heterogeneity and scales to many workers, enabling
highly accurate decentralized deep learning on heterogeneous data. Our code is
available at http://github.com/epfml/relaysgd.
