RelaySum for Decentralized Deep Learning on Heterogeneous Data
Year: 2022

Abstract:
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 study 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.

heading: 1 Introduction
text: Ever-growing datasets lay at the foundation of the recent breakthroughs in machine learning. Learning algorithms therefore must be able to leverage data distributed over multiple devices, in particular for reasons of efficiency and data privacy. There are various paradigms for distributed learning, and they differ mainly in how the devices collaborate in communicating model updates with each other. In the all-reduce paradigm, workers average model updates with all other workers at every training step. In federated learning [24], workers perform local updates before sending them to a central server that returns their global average to the workers. Finally, decentralized learning significantly generalizes the two previous scenarios. Here, workers communicate their updates with only few directly-connected neighbors in a network, without the help of a server.
Decentralized learning offers strong promise for new applications, allowing any group of agents to collaboratively train a model while respecting the data locality and privacy of each contributor [25]. At the same time, it removes the single point of failure in centralized systems such as in federated learning [12], improving robustness, security, and privacy. Even from a pure efficiency standpoint, decentralized communication patterns can speed up training in data centers [2].
In decentralized learning, workers share their local stochastic gradient updates with the others through gossip communication [41]. They send their updates to their neighbors, which iteratively
∗Equal contribution. Corresponding authors thijs.vogels@epfl.ch and lie.he@epfl.ch.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
propagate the updates further into the network. The workers typically use iterative gossip averaging of their models with their neighbors, using averaging weights chosen to ensure asymptotic uniform distribution of each update across the network. It will take τ rounds of communication for an update from worker i to reach a worker j that is τ hops away, and when it first arrives, the update is exponentially weakened by repeated averaging with weights < 1. In general networks, worker j will never exactly, but only asymptotically receive its uniform share of the update. The slow distribution of updates not only slows down training, but also makes decentralized learning sensitive to heterogeneity in workers’ data distributions.
We study an alternative mechanism to gossip averaging, which we call RelaySum. RelaySum operates on spanning trees of the network, and distributes information exactly uniformly within a finite number of gossip steps equal to the diameter of the network. Rather than iteratively averaging models, each node acts as a ‘router’ that relays messages through the whole network without decaying their weight at every hop. While naive all-to-all routing requires n2 messages to be transmitted at each step, we show that on trees, only n messages (one per edge) are sufficient. This is enabled by the key observation that the routers can merge messages by summation to avoid any extra communication compared to gossip averaging. RelaySum achieves this using additional memory linear in the number of edges, and by tailoring the messages sent to different neighbors. At each time step, RelaySum workers receive a uniform average of exactly one message from each worker. Those messages just originate from different time delays depending on how many hops they travelled. The difference between gossip averaging and RelaySum is illustrated in Figure 1.
The RelaySum mechanism is structurally similar to Belief Propagation algorithms for inference in graphical models. This link was made by Zhang et al. [50], who used the same mechanism for decentralized weighted average consensus in control.
We use RelaySum in the RelaySGD learning algorithm. We theoretically show that this algorithm is not affected by differences in workers’ data distributions. Compared to other algorithms that have this property [36, 31], RelaySGD does not require the selection of averaging weights, and its convergence does not depend on the spectral gap of the averaging matrix, but instead on the network diameter.
While RelaySum is formulated for trees, it can be used in any decentralized network. We use the Spanning Tree Protocol [30] to construct spanning trees of any network in a decentralized fashion. RelaySGD often performs better on any such spanning tree than gossip-based methods on the original graph. When the communication network can be chosen freely, the algorithm can use double binary trees [33]. While these trees have logarithmic diameter and scale to many workers, RelaySGD in this setup uses only constant memory equivalent to two extra copies of the model parameters and sends and receives only two models per iteration.
Surprisingly, in deep learning with highly heterogeneous data, prior methods that are theoretically independent of data heterogeneity [36, 31], perform worse than heuristic methods that do not have this property, but use cleverly designed time-varying communication topologies [2]. In extensive tests on image- and text classification, RelaySGD performs better than both kinds of baselines at equal communication budget.

heading: 2 Related work
text: Out of the multitude of decentralized optimization methods, first-order algorithms that interleave local gradient updates with a form of gossip averaging [29, 11] show most promise for deep learning. Such algorithms are theoretically analyzed for convex and non-convex objectives in [28, 11, 29], and [19, 36, 2, 20] demonstrate that gossip-based methods can perform well in deep learning.
In a gossip averaging step, workers average their local models with the models of their direct neighbors. The corresponding ‘mixing matrix’ is a central object of study. The matrix can be doublystochastic [29, 19, 16], column-stochastic [38, 26, 39, 2], row-stochastic [40, 44], or a combination [42, 43, 32]. Column-stochastic methods use the push-sum consensus mechanism [13] and can be used on directed graphs. Our analysis borrows from the theory developed for those methods.
While gossip averages in general requires an infinite number of steps to reach exact consensus, another line of work identifies mixing schemes that yield exact consensus in finite steps. For some graphs, this is possible with time-independent averaging weights [15, 6]. One can also achieve finite-time consensus with time-varying mixing matrices. On trees, for instance, exact consensus can be achieved by routing updates to a root node and back, in exactly diameter number of steps [15, 6]. On some graphs, tighter bounds can be established [8]. For fully-connected networks with n workers, Assran et al. [2] design a sparse time-varying communication scheme that yields exact consensus in a cycle of log n averaging steps and performs well in deep learning.
The ‘relay’ mechanism of RelaySGD was previously used by Zhang et al. [50] in the control community for the decentralized weighted average consensus problem, but they do not use it in the context of optimization. Zhang et al. also introduce a modified algorithm for loopy graphs, but this modification makes the achieved consensus inexact. The ‘relay’ mechanism effectively turns a sparse graph into a fully-connected graph with communication delays. Work on delayed consensus [27] and optimization [37, 1] analyzes such schemes for centralized distributed algorithms. Those consensus schemes are, however, not directly applicable to decentralized optimization.
A fundamental challenge in decentralized learning is dealing with data that is not identically distributed among workers. Because, in this case, workers pursue different optima, workers may drift [29] and this can harm convergence. There is a large family of algorithms that introduce update corrections that provably mitigate such data heterogeneity. Examples applicable to non-convex problems are exact diffusion [45], Gradient Tracking [22, 31, 48], D2 [36], PushPull [32]. To tackle the same challenge, Lin et al. [20], Yuan et al. [46] propose modifications to local momentum to empirically improve performance in deep learning, but without provable guarantees. Lu and De Sa [23] propose DeTAG which overlaps multiple consecutive gossip steps and gradient computations to accelerate information diffusion. This technique could be applied to the RelaySum mechanism, too.

heading: 3 Method
text: Setup We consider standard decentralized optimization with data distributed over n ≥ 1 nodes: f? := minx∈Rd [ f(x) = 1n ∑n i=1 [fi(x) := Eξ∼Di Fi(x, ξi)] ] .
Here Di denotes the distribution of the data on node i and fi : Rd → R the local optimization objectives. Workers are connected by a network respecting a graph topology G = (V, E), where V = {1, . . . , n} denotes the set of workers, and E the set of undirected communication links between them (without self loops). Each worker i can only directly communicate with its neighbors Ni ⊂ V .
Decentralized learning with gossip We consider synchronous first-order algorithms that interleave local gradient-based updates
x (t+1/2) i = x (t) i + u (t) i
with message exchange between connected workers. For SGD with typical gossip averaging (DPSGD [19]), the local updates can be written as u(t)i = −γ∇fi(x (t) i , ξ (t) i ), and the messages exchanged between pairs of connected workers (i, j) are m(t)i→j = x (t+1/2) i ∈ Rd. Each timestep, the workers average their model with received messages,
x (t+1) i = Wiix (t+1/2) i + ∑ j∈Ni Wijm (t) j→i, (DP-SGD)
using averaging weights defined by a gossip matrix W ∈ Rn×n.
In this scheme, an update u(t1)i from any worker i will be linearly incorporated into the model x (t2) j at a later timestep t2 with weight (Wt2−t1)ij . The gossip matrix must be chosen such that these weights asymptotically converge to 1n , distributing all updates uniformly over the workers. This setup appears in, for example, [19, 16].
Uniform model averaging If the graph topology is fully-connected, any worker can communicate with any other worker, and it is ideal to use ‘all-reduce averaging’,
x (t+1) i = 1 n ∑n j=1 x (t+1/2) j .
Contrary to the decentralized scheme (DP-SGD), this algorithm does not degrade in performance if data is distributed heterogeneously across workers. In sparsely connected networks, however, all-reduce averaging requires routing messages through the network. On arbitrary networks, such a routing protocol requires at least a number of communication steps equal to the network diameter τmax—the minimum number of hops some messages have to travel.
RelaySGD In this paper, we approximate the all-reduce averaging update as
x (t+1) i = 1 n ∑n j=1 x (t−τij+1/2) j , (RelaySGD)
where τij is minimum number of network hops between workers i and j (and τii = 0). Since it takes τij steps to route a message from worker i to j, this scheme could be implemented using a peer-to-peer routing protocol like Ethernet. Of course, this naive implementation drastically increases the bandwidth used compared to gossip averaging. The key insight of this paper is that, on tree networks, the RelaySGD update rule can be implemented while using the same communication volume per step as gossip averaging, using additional memory linear in the number of a worker’s direct neighbors.
RelaySum To implement RelaySGD, we require a communication mechanism that delivers sums of delayed ‘parcels’ s(t)w = ∑n j=1 p (t−τwj) j to each worker w in a tree network, where the parcel p (t) j is created by worker j at time t. To simplify the exposition, let us first consider the simplest type of tree network: a chain. In a chain, a worker w is connected to workers w− 1 and w+ 1, if those exist, and the delays are τij = |i− j|. We can then decompose
s(t)w = n∑ j=1 p (t−τwj) j = p (t) w + w−1∑ j=1
p (t−τwj) j︸ ︷︷ ︸
parcels from the ‘left’
+ n∑ j=w+1
p (t−τwj) j︸ ︷︷ ︸ parcels from the ‘right’ .
The sum of parcels from the ‘left’ will be sent as one message m(w−1)→w from worker w − 1 to w, and the sum of data from the ‘right’ will be sent as one message m(w+1)→w from w + 1 to w. Neighboring workers can compute these messages from the messages they received from their neighbors in the previous timestep. Compared to typical gossip averaging, RelaySum requires additional memory linear in the number of neighbors, but it uses the same volume of communication.
Algorithm 1 shows how this scheme is generalized to general tree networks and incorporated into RelaySGD. Along with the model parameters, we send scalar counters that are used in the first few iterations of the algorithm t ≤ τmax to correct for messages that have not yet arrived.
Spanning trees RelaySGD is formulated on tree networks, but it can be used on any communication graph by constructing a spanning tree. In a truly decentralized setting, we can use the Spanning Tree Protocol [30] used in Ethernet to find such trees in a decentralized fashion. The protocol elects a leader as the root of the tree, after which every other node finds the fastest path to this leader.
On the other hand, when the decentralized paradigm is used in a data center to reduce communication, RelaySGD can run on double binary trees [33] used in MPI and NCCL [10]. The key idea of double binary trees is to use two different communication topologies for different parts of the model. We communicate odd coordinates using a balanced binary tree A, and communicate the even coordinates with a complimentary tree B. The trees A and B are chosen such that internal nodes (with 3 edges)
Algorithm 1 RelaySGD
Input: ∀ i, x(0)i = x(0); ∀ i, j,m (−1) i→j = 0, counts c (−1) i→j = 0, learning rate γ, tree network
1: for t = 0, 1, . . . do 2: for node i in parallel 3: x(t+
1/2) i = x (t) i −γ∇fi(x (t) i ) (or Adam/momentum)
4: for each neighbor j ∈ Ni do 5: Send m(t)i→j = x (t+1/2) i + ∑ k∈Ni\jm (t−1) k→i (relay messages from other neighbors)
6: Send corresponding counters c(t)i→j = 1 + ∑ k∈Ni\j c (t−1) k→i 7: Receive (m(t)j→i, c (t) j→i) from node j 8: end for 9: n̄(t+1)i = 1 + ∑ j∈Ni c (t) j→i (n̄ converges to the total number of workers)
10: xt+1i = 1
n̄ (t+1) i
( x
(t+1/2) i + ∑ j∈Ni m (t) j→i ) ( = 1n ∑n j=1 x (t−τij+1/2) j ) 11: end for 12: end for
in one tree are leaves (with only 1 edge) in the other. Using the combination of two trees, RelaySGD requires only constant extra memory equivalent to at most 2 model copies (just like the Adam optimizer [14]), and it sends and receives the equivalent of 2 models (just like on a ring).

heading: 4 Theoretical analysis
text: Since RelaySGD updates worker’s models at time step t+1 using models from (at most) the past τmax steps, we conveniently reformulate RelaySGD in the following way: Let Y(t),G(t) ∈ Rn(τmax+1)×d denote stacked worker models and gradients whose row vectors at index n·τ + i represent[
Y(t) ]> nτ+i =
{ x
(t−τ) i t ≥ τ
x(0) otherwise ,
[ G(t) ]> nτ+i = { ∇Fi(x(t−τ)i ; ξ (t−τ) i ) t ≥ τ x(0) otherwise
for all times t ≥ 0, delay τ ∈ [0, τmax] and worker i ∈ [n]. Then (RelaySGD) can be written as
Y(t+1) = WY(t) − γW̃G(t)
where W,W̃ ∈ Rn(τmax+1)×n(τmax+1) are non-negative matrices whose elements are
[W]nτ+i,nτ ′+j =  1 n τ = 0 and τ ′ = τij 1 i = j and τ = τ ′ + 1 0 otherwise , [ W̃ ] nτ+i,nτ ′+j = { 1 n τ = 0 and τ ′ = τij 0 otherwise
for all τ, τ ′ ∈ [0, τmax] and i, j ∈ [n]. The matrix W can be interpreted as the mixing matrix of an ‘augmented graph’ [27] with additional virtual ‘forwarding nodes’. W is row stochastic and its largest eigenvalue is 1. The vector of all ones 1n(τmax+1) ∈ Rn(τmax+1) is a right eigenvector of W and let π ∈ Rn(τmax+1) be the left eigenvector such that π>1n(τmax+1) = 1. We characterize the convergence rate of the consensus distance in the following key lemma: Lemma 1 (Key lemma). There exists an integer m = m(W) > 0 such that for any X ∈ Rn(τmax+1)×d we have
‖WmX− 1π>X‖2 ≤ (1− p)2m‖X− 1π>X‖2,
where p = 12 (1− |λ2(W)|) is a constant.
All the following optimization convergence results will only depend on the effective spectral gap ρ := pm of W. We empirically observe that ρ = Θ(1/n) for a variety of network topologies (see
Figure 5 in Appendix A).
Remark 2. The above key lemma is similar to [16, Assumption 4] for gossip-type averaging with symmetric matrices. However, in our case W is just a row stochastic matrix, and its spectral norm
‖W‖2 > 1. In general, the consensus distance can increase after just one single communication step (multiplication by W). That is why we need m > 1. The proof of the Lemma relies on a Perron-Frobenius type theorem, and holds over several steps m instead of a single iteration. It means RelaySum defines a consensus algorithm with linear convergence rate which pulls models closer.
Our main convergence results hold under the following common assumptions, as e.g. [16].
Assumption A (L-smoothness). For each i ∈ [n], Fi(x, ξ) : RD × Ωi → R is differentiable for each ξ ∈ supp(Di) and there exists a constant L ≥ 0 such that for each x,y ∈ Rd, ξ ∈ supp(Di):
‖∇Fi(x, ξ)−∇Fi(y, ξ)‖ ≤ L‖x− y‖ .
Assumption B (Uniform bounded noise). There exists constant σ̄, such that for all x ∈ Rd, i ∈ [n],
Eξ ‖∇Fi(x, ξ)−∇fi(x)‖2 ≤ σ̄2.
Assumption C (µ-convexity). For i ∈ [n], each function fi : Rd → R is µ-(strongly) convex for constant µ ≥ 0. That is, ∀ x,y ∈ Rd
fi(x)− fj(y) + µ2 ‖x− y‖ 2 2 ≤ ∇fi(x)>(x− y) .
Theorem I (RelaySGD). For any target accuracy ε > 0 and an optimal solution x?, (Convex:) under Assumptions A, B and C with µ ≥ 0, it holds that 1T+1 ∑T t=0 ( f(x(t))−f(x?) ) ≤ ε
after O ( σ̄2 nε2 + C √ Lσ̄ ε3/2 + CLε ) R20
iterations. Here x(t) := π>Y(t) averages past models, R20 = ‖x0 − x?‖2, and C = O( 1ρτ 3/2 max). (Non-convex:) under Assumptions A and B, it holds that 1T+1 ∑T t=0 ‖∇f(x (t))‖2 ≤ ε after
O ( σ̄2
nε2 + Cσ̄ ε3/2 + Cε
) LF0
iterations, where F0 := f(x(0))− f(x?).
The dominant term in our convergence result, O ( σ̄2
nε2
) matches with the dominant term in the
convergence rate of centralized (‘all-reduce’) mini-batch SGD, and thus can not be improved.
In contrast to other methods, the presented convergence result of RelaySGD is independent of the data heterogeneity ζ2 in [16, Assumption 3b].
Definition D (Data heterogeneity). There exists a constant ζ2 such that ∀ i ∈ [n],x ∈ Rd
‖∇fi(x)−∇f(x)‖22 ≤ ζ2 .
Remark 3. For convex objectives, Assumptions B and D can be relaxed to only hold at the optimum x?. A weaker variant of Assumption A only uses L-smoothness of fi [16, Assumption 1b].
Comparing to gossip averaging for convex fi which has complexityO( σ̄ 2 nε2 + ( ζ ρ + σ̄√ ρ ) √ L ε3/2 + Lρε )R 2 0, our rate for RelaySGD does not depend on ζ2 and has same leading term O( σ̄ 2
nε2 ) as D 2.

heading: 5 Experimental analysis and practical properties

heading: 5.1 Effect of network topology
text: Random quadratics To efficiently investigate the scalability of RelaySGD with respect to the number of workers, and to study the benefits of binary tree topologies over chains, we introduce a family of synthetic functions. We study random quadratics with local cost functions fi(x) = ‖Aix − b>i x‖2 to precisely control all constants that appear in our theoretical analysis. The Hessians Ai are initialized randomly, and their spectrum is scaled to achieve a desired smoothness L and strong convexity µ. The offsets bi ensure a desired level of heterogeneity ζ2 and distance between optimum and initialization r0. Appendix B.4 describes the generation of these quadratics in detail.
Scalability on rings and trees Using these quadratics, Figure 2 studies the number of steps required to reach a suboptimality f(x̄)− f(x?) ≤ ε with tuned constant learning rates. On ring topologies with uniform (1/3) gossip weights (and chains for RelaySum), all compared methods require steps at least linear in the number of workers to reach the target quality. RelaySGD and D2 empirically scale significantly better than Gradient Tracking, these methods are all independent of data heterogeneity. On a balanced binary tree network with Metropolis-Hastings weights [41], both D2 and Gradient Tracking notably do not scale better than on a ring, while RelaySGD on these trees requires only a number of steps logarithmic in the number of workers. SGP with their time-varying exponential topology scales well, too, but it requires more steps on more heterogeneously distributed data.

heading: 5.2 Spanning trees compared to other topologies
text: RelaySGD cannot utilize all available edges in arbitrary networks to communicate, but is restricted to a spanning tree of the graph. We empirically find that this restriction is not limiting. In Figure 3, we take an organic social network topology based on the Davis Southern Women graph [4] from NetworkX [7], and construct random spanning trees found by the Spanning Tree Protocol [30]. On any such spanning tree, RelaySGD optimizes random heterogeneous quadratics as fast as D2 on the full graph with Metropolis-Hastings weights [41], significantly faster than DP-SGD.
For decentralized learning used in a fully-connected data center for communication efficiency, the deep learning experiments below show that RelaySGD on double binary trees outperforms the most popular non-tree-based communication scheme used in decentralized deep learning [2].

heading: 5.3 Effect of data heterogeneity in decentralized deep learning
text: We study the performance of RelaySGD in deep-learning based image- and text classification. While the algorithm is theoretically independent of dissimilarities in training data, other methods (D2, RelaySGD/Grad) that have the same property often lose accuracy in the presence of high data heterogeneity [20]. To study the dependence of RelaySGD in practical deep learning, we partition training data strictly across 16 workers and distribute the classes using a Dirichlet process [47, 20]. The Dirichlet parameter α controls the heterogeneity of the data across workers.
We compare RelaySGD against a variety of other algorithms. DP-SGD [19] is the most natural combination of SGD with gossip averaging, and we chose D2 [36] to represent the class of previous work that is theoretically robust to heterogeneity. We extend D2 to allow varying step sizes and local momentum, according to Appendix D.4, and make it suitable for practical deep learning. Although Stochastic Gradient Push [2] is not theoretically independent of data heterogeneity, it is a popular choice in the data center setting, where they use a time-varying exponential scheme on 2d workers that mixes exactly uniformly in d rounds (Appendix D.6). We also compare to DP-SGD with quasi-global momentum [20], a practical method recently introduced to increase robustness to heterogeneous data.
Even though RelaySGD does not use a time-varying topology, it performs as well as or better than SGP, and RelaySGD with momentum suffers minimal accuracy loss up to heterogeneity α = 0.01, a level higher than considered in previous work [20]. While D2 is theoretically independent of data heterogeneity, and while some of its random repetitions yield good results, it is unstable in the very heterogeneous setting. Moreover, Figure 4 shows that workers with RelaySGD achieve high test accuracies quicker during training than with other algorithms.
These findings are confirmed on ImageNet [5] with the ResNet-20-EvoNorm architecture [21] in Table 3. On the BERT fine-tuning task from [20], Table 4 demonstrates that RelaySGD with the Adam optimizer, customary for such NLP tasks, outperforms all compared algorithms.
Algorithm Topology Top-1 Accuracy
Centralized Adam fully-connected 94.2%± 0.1% Relay-Adam double binary trees 93.2%± 0.6% DP-SGD Adam ring 87.3%± 0.6% Quasi-global Adam [20] ring 88.3%± 0.7% SGP [2] Adam time-varying exp. 88.3%± 0.3%

heading: 5.4 Robustness to unreliable communication
text: Peer-to-peer applications are a central use case for decentralized learning. Decentralized learning algorithms must therefore be robust to workers joining and leaving, and to unreliable communication between workers. Gossip averaging naturally features such robustness, but for methods like D2, that correct for local data biases, achieving such robustness is non-trivial. As a proxy for these challenges, in Table 5, we verify that RelaySGD can tolerate randomly dropped messages. The algorithm achieves this by reliably counting the number of models summed up in each message. For this experiment, we use an extended version of Algorithm 1, where line 10 is replaced by
x (t+1) i = 1 n
( x
(t+1/2) i + ∑ j∈Ni m (t) j→i + (n− n̄ (t+1) i )x (t) i ) . (1)
We count the number of models received as n̄, and substitute any missing models (< n) by the previous state x(t)i . RelaySGD trains reliably to good test accuracy with up to 10% deleted messages. This behavior is on par with a similarly modified SGP [2] that corrects for missing energy. In contrast, D2 becomes unstable with undelivered messages and diverges.

heading: 6 Conclusion
text: Decentralized learning has great promise as a building block in the democratization of deep learning. Deep learning relies on large datasets, and while large companies can afford those, many individuals together can, too. Of course, their data does not follow the exact same distribution, calling for robustness of decentralized learning algorithms to data heterogeneity. Algorithms with this property have been proposed and analyzed theoretically, but they do not always perform well in deep learning.
In this paper, we propose RelaySGD for distributed optimization over decentralized networks with heterogeneous data. Unlike algorithms based on gossip averaging, RelaySGD relays models through spanning trees of a network without decaying their magnitude. This yields an algorithm that is both theoretically independent of data heterogeneity, but also high performing in actual deep learning tasks. With its demonstrated robustness to unreliable communication, RelaySGD makes an attractive choice for peer-to-peer deep learning and applications in large-scale data centers.
Acknowledgments and Disclosure of Funding
This project was supported by SNSF grant 200020_200342, as well as EU project DIGIPREDICT, and a Google PhD Fellowship.
We thank Yatin Dandi and Lenka Zdeborová for pointing out the similarities between this algorithm and Belief Propagation during a poster session. This discussion helped us find the strongly related article by Zhang et al. [50] that we missed initially.
We thank Renee Vogels for proofreading of the manuscript.

Review summaries:
This work presents a novel decentralized deep learning algorithm on heterogeneous data. Specifically, the authors develop a RelaySum protocol for handling the information propagation in the networked systems with spanning trees, and RelaySGD for optimizing the learning problems. Different from the popular gossip averaging, RelaySum enables to relay messages through the whole network without decaying each node’s weight at every hop. The authors theoretically prove that RelaySGD is not affected by differences in workers’ data distributions, and that its convergence does not rely on the spectral gap of the graph, but instead on the network diameter. To validate the proposed algorithm, a few baselines and different datasets are used for the comparison. The empirical results show that RelaySGD outperforms baselines in terms of accuracy and convergence speed.

A method to reduce communication costs when performing distributed training in networks where communication between nodes requires more than one hop. The trade off is increased memory usage and delayed communication (parameters arrive at a later iteration).  === Review Update ===  Thank you for the clarifications. In particular, it is true that all virtual topologies used by modern distributed ML systems are sparse, so I retract my comment regarding "comparison on fully-connected" topologies as it certainly does not make sense.  After reading both the authors' response and the other reviewers' comments, I've decided to keep my score as-is.

This paper proposes a decentralized SGD method, RelaySGD, for faster mixing in distributed deep learning, with the aim of improving performance on nodes with heterogeneous data sources. Convergence guarantees are provided for smooth non-convex functions under the weak growth condition, as well as for smooth strongly convex functions under the weak growth condition. The method relies on undirected, static, spanning-tree graphs.