RelaySum for Decentralized Deep Learning on Heterogeneous Data
Authors: Thijs Vogels
Lie He
Anastasia Koloskova
Sai Praneeth Karimireddy
Tao Lin
Sebastian U Stich
Martin Jaggi
Venue: NeurIPS 2021 Poster (2021)
Keywords: decentralized optimization
distributed optimization
consensus
deep learning

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 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.

RelaySum for Decentralized Deep Learning on Heterogeneous Data
Thijs Vogels* EPFL
Lie He EPFL
Anastasia Koloskova
Tao Lin EPFL
EPFL
Sai Praneeth Karimireddy
Sebastian U. Stich EPFL
Martin Jaggi
EPFL
EPFL
Abstract
In decentralized machine learning, workers compute model updates their local data. Because the workers only communicate with few neighbors without cen- tral coordination, these updates propagate progressively paradigm enables distributed training on networks without all-to-all connectivity, helping protect data privacy as well distributed training in data centers. 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. 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:///t thwb. com http////mm/eelagg/pee
the network. This
reduce the communication cost of
1 Introduction
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 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-commected neighbors in network, without the help of server.
Decentralized learning offers strong promise for 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 in federated learning [12, improving robustness, security, and privacy. Even from 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
Equual contribution. Corresponding authors saajjs.vogessbeppfi ch and 1ie. hetepfl.ccc ch.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Gossip averaging
RelaySum
Worker
Wurkse
Worker
omigin
Figure To spread information across a decentralized network, classical gossip averaging diffuses information slowly through the network. The left figure illustrates the spread of information originating from the fourth worker in a chain network. In RelaySum, the messages are relayed without reweighting, resulting in uniform delivery of the information to every worker. When multiple workers broadcast simultaneously (not pictured), RelaySum can sum their messages and use the same bandwidth as gossip averaging.
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 to reach worker that is hops away, and when it first arrives, the update is exponentially weakened by repeated averaging with weights < 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 gossip averaging, which call RelaySum. RelaySum operates on spanning trees of the network, and distributes information exactly uniformly within a finite number of gossip steps equal 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 every hop. While naive all-to-all routing requires n² messages to be transmitted 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 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 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, 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 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.
graph. When the communication network can be chosen freely, the algorithm
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 22 In extensive tests on image- and text classification, RelaySGD performs better than both kinds of baselines at equal communication budget.

---

2
Related work
Out of the multitude of decentralized optimization methods. first-order algorithms that interleave local gradient updates with a form of gossip averaging [29] [MI show most promise for deep learning.
Such algorithms are theoretically analyzed for convex and non-convex objectives in 228 I1 29 and
[19 36 2 [20] demonstrate that gossip- based methods can perform well in deep learning.
In 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 doubly-
stochastic [29. 19 16), column-stochastic [38 26 39 2), row-stochastic (40 44], or combination [42 43 [2]. 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 independennn averaging weights [15 6. One can also achieve finite-tima 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 [[5] 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-narying communication scheme that yields exact consensus in a cycle of log 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 sparse graph into a Cully-connected graph with communication delays. Work on delayed consensus [27] and optimization (7 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 dis- tributed among workers. Because, in this case, workers pursue different optima, workers may drift [29] and this can harm convergence. There is 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
[3 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.
3 Method
Setup
We consider standard decentralized optimization with data distributed over n 2 nodes:
f minxeR [f(x) = - E. (x) = Eş-D, (x, Ex)]
Here Dj denotes the distribution of the data on node and fe: Rd - R the local optimization objectives. Workers are connected by a network respecting graph topology G = (V. E), where V == {l....,n] n denotes the set of workers, and the set of undirected communication links between them (without self loops). Each worker can only directly communicate with its neighbors N₁ C V.
Decentralized learning with gossip local gradient-based updates
We consider synchronous first-order algorithms that interleave
(6)
x
+ u
with message exchange between connected workers. For SGD with typical gossip averaging (DP- (t)
SGD 19). ), the local updates can be written as u V (())) and the messages exchanged
between pairs of connected workers (i,j) are m m (14))) e gd Each timestep, the workers average their model with received messages,
x;
(L+1)
W (1+1/2)
+ EjEN, W Wym (0)
(DP-SGD)
3

---

using averaging weights defined by gossip matrix W E R
In this scheme, an update u (fx) from any worker i will be linearly incorporated into the model (fz) later timestep l2 with weight (W(=-())p The gossip matrix must be chosen such that these weights asymptotically converge A, distributing all updates uniformly over the workers. This setup
appears in, for example, [19 [6]
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',
1 - (141/2)
Contrary to the decentralized scheme SPD this algorithm does not degrade in performance data is distributed heterogeneously across workers. In sparsely connected networks, however, all-reduce averaging requires routing messages through the network. On arbitrary networks, such routing protocol requires at least a number of communication steps equal to the network diameter Tmax the minimum number of hops some messages have to travel.
RelaySGD this paper, we approximate the all-reduce averaging update as
(++
= - (1/))
(RelaySGD)
where Tiy is minimum number of network hops between workers and (and Ty 0). Since it takes Tay steps to route a message from worker 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' (t) =Σ (t-Tus) to each worker in tree network, where the parcel pj is created by worker j at time l. 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 and w + 1, if those exist, and the delays are Taj - jl. We can then decompose
(t)
n
=p!
(t Tws)
Σ j=
((-Tw)) Pj
Pj
parcels from the 'left'
parcels from the "right"
The of parcels from the 'left' will be sent as one message (i(--))-w from worker to w, and the sum of data from the 'right' will be sent as one message ([(++)->w from w + 1 Neighboring workers 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.
compute these messages from the messages they received from
Algorithm T 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 I Tmax to correct for messages that have not yet arrived.
Spanning trees RelaySGD is formulated on tree networks, but it can be used any communication graph by constructing a spanning tree. In a truly decentralized setting, we can use the Spanning Tree Protocol [30] used in Ethernet find such trees in decentralized fashion. The protocol elects 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 333 used MPI and NCCL [00 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 balanced binary tree A, and communicate the even coordinates with complimentary tree B. The trees A and B are chosen such that internal nodes (with edges)

---

Algorithm RelaySGD
Input: Vi, (0) x Vij -11
(-1) counts 9-+3
0, learning rate ?/ tree network
1: for = 0, 1.......a do
2: for node in parallel
3:
x; ((+1/2) (0) ( (0)
(or Adam/momentum)
4:
for each neighbor j N, do
5:
ERE (t-1) Send m - 2, (1+\/))
k-s
(relay messages from other neighbors)
Send corresponding counters o =1 EKERN Vi1
6:
(t) Receive (m J- c_.,) from node j
7:
8:
end for
9:
n
(++1)
1+ E
JENs Grts
(n converges to the total number of workers)
10:
(141)
x;
1/2)
EjEM mj m
(= ト (t-Ta 1/2)
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 [4)), and it sends and receives the equivalent of 2 models (just like on ring).
4 Theoretical analysis
Since RelaySGD updates worker's ss models at time step 1 + using models from (at most) the past Tiax steps, we conveniently reformulate RelaySGD in the following way: Let ((), G [ x1) denote stacked worker models and gradients whose row vectors at index + represent
Y
X;
((-T)
t t2
[G
[G
(x
(t-r))
t t2 otherwise
(0)
otherwise
x())
for all times 2 delay T E [0, Tmax] and worker [n]. Then (RelaySGD) can be written as ((+1)) = wy WG
where W, W E + +1) are non-negative matrices whose elements are
0 and r' Tkj +1,
0 and 7' Taj
[W] Wnr
i i and
W
otherwise
otherwise
for all 7,7' [0, Tmax] and i,j E [m). The matrix W can interpreted as the mixing matrix of an 'augmented graph' (27] with additional virtual 'orwarding nodes'. W is row stochastic and its largest eigenvalue is 1. The vector of all ones In(rux +1) E R ( is a right eigenvector of W and let (1((mme++) be the left eigenvector such that In(mmx++1) 1.
We characterize the convergence rate of the consensus distance the following key lemma:
Lemma 1 (Key lemma). There existy an integer in m(W O such that for any X (T +1)xd we have
| - 1 X <
2 X 1x x|I2.
where p (1 1A2( (W))) is constant.
All the following optimization convergence results will only depend on the effective spectral gap 2. of W. We empirically observe that p (11/n) for variety of network topologies (see
Figure in Appendix(A]
Remark 2. The above key lemma is similar to 16 Assumption for gossip-type averaging with symmetric matrices. However, in our case W is just row stochastic matrix, and its spectral norm
5

---

[Wl2 1. In general, the consensus distance can increase after just one single communication step (multiplication by W). That why we need Perron-Frood Frobenius type theorem, and holds over several steps m instead of a single iteration. It means RelaySum defines consensus algorithm with linear convergence rate which pulls models closer.
The proof of the Lemma relies on
Our main convergence results hold under the following common assumptions, as e.g. 16
Assumption A (L-smoothness). For each [n). Fx(x, <) RR. S4 R is differentiable for each & E supp(D;) and there exists constant L 2 0 such that for each x,y E IR & supp(D:)):
(x. (y, E)ll & T|Ix -yll-
Assumption B (Uniform bounded noise). There exists constant o, such that for all x E Rd, i E [m].
Eg [VVF(( V S a².
Assumption C (f-coonvxxtt)) For i E [n], each function fi Rd - R is p-(strongly) convex for constant μ 2 0. That is, V x, E Rd
(x) (y) + =||x - y12 S ( y)-
Theorem I (RelaySGD). For any target accuracy 0 and optimal solution x*, (Convex:) under Assumptions A and with μ 2 0, it holds that 1 T+I Ei=o (f(x())-((x)) S
after
o² ngz
CvLa 2/2
CL
Rg
iterations. Here x(1) : (t) averages past models, Bg = ||x x1, and C = =
(Non-convex:) under Assumptions and
B holds that 7 Σ || | < after
aaa
LFo
ns?
2/2
iterations, where Fe = f(x(0)) f(x*).
The dominant term in convergence result, O nez 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 ç² in [16] Assumption 3b].
Definition D (Data heterogeneity). There exists a constant Ç² such that V i [n]. Rd
- - s
Remark 3. For convex objectives, Assumptions B and D can be relaxed only hold the opti- mum x*. weaker variant of Assumption A only uses L-smoothness of fa 116 Assumption 1b].
Comparing to gossip averaging for convex f, which has complexity O our rate for RelaySGD does not depend on ç² and has same leading term O
n (
+ (S
)
P2
vp
2
2/
pe
as D2
ngz
5
Experimental analysis and practical properties
5.1 Effect of network topology
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 fx(x) = |A, b, x|2 to precisely control all constants that appear in our theoretical analysis. The Hessians A; are initialized randomly, and their spectrum is scaled to achieve a desired smoothness L. and strong convexity μ.. The offsets b, ensure a desired level of heterogeneity Ç² and distance between optimum and initialization ro- Appendix B.4 describes the generation of these guadratics in detail.

---

Scalability on rings and trees Using these quadratics, FFiuuee 2/studies the number of steps required to reach suboptimality f(x) f(x)) S E 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- Masstnol weights [41]. both D and Gradient Tracking notably do not scale better than on 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.
0.01 (a little beterogenern))
( 1.0 (very beienggmeen))
5001
sxps to 710) 7000-((x)) ((x") (
400
Algorithm
Grndten trickng
300
SGP
Rokyy
200
Topalogy
100
hirrry
Bing dhrnn
Time-vorying expenorcal
0
30
40 60
50
100
20
40
90
100
Namber workers
Nundoa worlers
Figure 2: Time required to optimize random quadratics (o² = 0, = 1, 0.5) to suboptimality < 10-6 with varying numbers of workers with tuned constant learning rates. On ring (---), m D2 and RelaySGD require steps linear in the number of workers, and this number is independent of the data heterogeneiry. RelaySGD reduces this to log n on balanced tree topology (-), ), but trees do not improve D² or Gradient Tracking. For SGP with time-varying exponential topology (.....,, the number of steps does not consistently grow with more workers, but this number
becomes higher with more heterogeneity (left v.s. right plot).
5.2 Spanning trees compared to other topologies
RelaySGD cannot utilize all available edges in arbitrary networks communicate, but restricted to 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 Hatstngl weights 411, significantly faster than DP-SGD.
For decentralized learning used in 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)
5.3 Effect of data heterogeneity in decentralized deep learning
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 (D²
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 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 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, is a popular choice in the data center setting, where they use 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 220), practical method recently introduced to increase robustness to heterogeneous data.
7

---

100
Suhoplimaliy [(8]- f(x*)
10-2
10-4
10-1
1007
2003
300
400
500 0
200000
400000
6XXXB
50000
Steps
parameter veciors scnt rocdived
Figure 3: Performance of RelaySGD on spanning trees of the Social Network graph (32 nodes) found using Spanning Tree Protocol, compared
DP-SGD and D2 on the full network. Solid lines (-) indicate spanning trees while dashed lines (---) indicate the full graph. The figure on the right shows one spanning tree on top of the original network. Learning rates are tuned to reach suboptimality s 10-5 on random quadraties (ç² 0.1, 1, 0.1, = 1, L 1, 0.5). RelaySGD on spanning trees converges fast D2 on the full network, while the total communication on spanning trees is smaller than on the full graph.
Table 1: Cifar- 10 17 test accuracy with the VGG-11 architecture. We vary the data heterogene-
ity 20 between 16 workers. Each method sends/receives 2 models per iteration. We ring topology for DP-SGD and D2 because they perform better on rings than on trees. RelaySum with momentum achieves the best results across all levels of data heterogeneity.
Algorithm
Topology
1.00
0.1
a .01
(optimal Table
(most homogeneous)
heterngenooss)
All-reduce (baselinc)
fully connected
87.0%
87.0%
87.0%
+momentum
90.2%
90.2%
90.2%
RelaySGD
binary trees
87.4%
86.9%
84.6%
Local momentum
90.2%
89.5%
89.1%
DP-SGD [19
ring
87.4%
79.9%
53.9%
qquasi global
20
89.5%
84.8%
63.3%
D2
36
ring
87.2% F
84.0%
38.2%
momentum
0%
Stochastic gradient push
time-varying exponential t
87.45i
76.7%
86.7%
Hocal momenium
89.5%
89.2%
87.5%
Table I evvaluates RelaySGI in the fully-connected data center setting where we limit the communica- tion budget per iteration details outlined in Appendix B and hyper-parameter tuning procedure from Appendix C For this
models. We use 16-workers on Cifar- 10, following the experimental
experiment, we consider three topologies: (1) double binary trees described in secciin 3 (2) rings, and (3) the time-varying exponential scheme of Stochastic Gradient Push (SGP) [2]. Because SGP normally sends/receives only one model per communication round, we execute two synchronous communication steps per gradient update, increasing its latency. The various algorithms compared have different optimal topology choices. In Table we only include the optimal choice for each algorithm. Table 2) qualitatively compares the possible combinations. We opt for the VGG-11 11 archi- tecture because does not feature BatchNorm heterogeneity, and the search for alternatives is an active, and orthogonal, area of research [1
99. BatchNorm poses particular challenges to data
Even though RelaySGD does use time-varying topology, performs as well better than SGP, and RelaySGD with momentum suffers minimal accuracy loss to heterogeneity a 0.01, level higher than considered previous work [20] While D 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 confirmed ImageNet [ with the ResNet-20 2eeee22--vvooom 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 NLPP tasks, outperforms all compared algorithms.

---

Table 2: Motivation of topology choices. For each algorithm, compare 4 topologies configured to send/receive 2 models at each SGD iteration. The algorithms have different optimal topologies.
Algorithm
Ring
(= spanning tree ring)
Double binary trees
Time-varying exponential 2
RelaySGD
Unsupported
Worse than double b. trees (E.1)
Best result
Unsupported
DP-SGD
Best result
Worse than ring
Worse than ring
Unsupported
D²
Best result
Worse tham ring
Worse than ring
Unsupported
Equivalent
Equivalent DP-SGD
Equivalent
Best result
Figure 4: Test accuracy during training of work- ers with heterogeneous data (a = 0.01) on Cifar-10. Like, with the all-reduce baseline, all workers in RelaySGD double binary trees quickly reach good accuracy, while this takes longer for SGP with time-varying exponential topology and D² on a ring. DP-SGD does not reach good accuracy with such heterogeneous data.
Cifar 10 Test Accuracy
150 175 200
Epochs
Table Test accuracies on ImageNet, using 16 workers with heterogeneous data (a 0.1). Even when communicating over a simple chain network, RelaySGD performs similarly to SGP with their time-varying exponential communicating scheme. Methods default learning rates (Appendix
Algorithm
Topology
Top-1 Accuracy
Contralized (baseline)
fully-connected
69.7%
RelaySGD w/ momentum
double binary trees
60.0%
DP-SGD [19 quasi-global momentum
ring
55.8%
D [6 w/ momentum
ring
diverged epoch 65, at 49.5%
SGP
momenium
time varying expomential 2
58.5%
Algoritha
Topology
Top-1 Accuracy
Table DistilBERT
34 fine-tuning on AG news data [49] using 16 nodes with heteroge- neous data (a = 0.1). Transformers are usually trained with Adam, and RelaySGD naturally
Centralized Adam
fully connected
94.25 d. 0.1%
Relay-Adam
double binary trees
93.2%
DP-SGD Adam
ring
87.3%
0.6%
Quasi-global Adam 20
ring
88. 3%
0.7%
supports Adam updates. (Appendix) B.3
SGP Adam
time-varying exp.
88.3% 0.3%
Table 5: Robustness to unreliable networks. On Cifar-10/VGG-1 with 16 workers and heterogeneous
data (a 0.01), compare momentum versions of the best-performing algorithms from Table Like gossip- bassep algorithms, RelaySGD with the robust update rule can tolerate up to 10% dropped messages and converge full test accuracy. Without modification, 2 does not share this property.
Algorithm
Topology
Reliable octwork
1% dropped messages
10% dropped messages
RelaySGD w/ momentum
trees
89.2%
89.3%
89.3%
DP-SGD [V] quasi-global mom.
ring ring
78.3%
76.2%
76.9%
D2 momentum
87.4%
diverges
diverges 88.1%
SGP w/ momentum
lime-varying
88.5%
88.6%

---

5.4 Robustness to unreliable communication
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 D², that correct for local data biases, achieving such robustness is non-trivial. As 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 where line 10 is replaced by
(1) We count the number of models received as ñ, and substitute any missing models (< n) by the previous state x; (2) RelaySGD trains reliably to good test accuracy with up 10% deleted messages. This behavior is on par with a similarly modified SGP [2] that corrects for missing energy. In contrast, D becomes unstable with undelivered messages and diverges.
(1+1/2) + EjEN, m + (n-m
m. (1+1)) (1)
6
Conclusion
Decentralized learning has great promise as a building block in the democratization of deep learning. Deep learning relies large datasets, and while large companies 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 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 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 100020_200344 as well as EU project DIGIPREDICT, and Google PhD Fellowship.
We thank Yatin Dandi and Lenka Zdeborová for pointing out the similarities between this algorithm and Belief Propagation during 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.
References
[1] Alekh Agarwal and John C. Duchi. Distributed delayed stochastic optimization. In Proc. CDC, pages 5451-5452, 2012.
[2] Mahmoud Assran, Nicolas Loizou, Nicolas Ballas, and Michael G. Rabbat. Stochastic gradient push for distributed deep learning. In Proc. ICML, volume 97, pages 344-353, 2019.
[3] Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. ICLR, 2016.
[4] Allison Davis, Burleigh Bradford Gardner, and Mary R Gardner. Deep South: A social anthropological study of caste and class, Univ of South Carolina Press, 1930.
[5] Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Fei-Fei Li. Imagenet: large-scale hicrarchical image database. In Proc. CVPR, pages 248-255, 2009.
[6] Leonidas Georgopoulos. Definitive Consensus for Distributed Data Inference. PhD thesis, EPFL, 2011.
[7] Aric Hagberg. Pieter Swart, and Daniel S Chult. Exploring network structure, dynamics, and function using NetworkX. Technical report, Los Alamos National Lab(LAN)), Los Alamos, NM (United States), 2008.
10

---

[8] Julien M. Hendrickx, Raphaël M. Jungers, Alexander Olshevsky, and Guillaume Vankeerberghen. Graph diameter, eigenvalues, and minimum-tinee consensus. Automatica, 50(2):635-664, 2014.
[9] Sergey loffe and Christian Szegedy, Batch normalization: Accelerating deep network training by reducing internal covariate shift. In Proc. ICML, volume 37, pages 448 456, 2015.
[10] Sylvain Jeaugey. Massively scale your deep learning training with NCCL 2.4. https:/
devbloge dewbloge.nvidia.com www.iiiiiii.i.m wttaaaawocommmmamaaaee wwtp://ssssssalleeeeeeeeeeeee deepllernng--ee wraninngggraiiinni-en www.-nccl-------e- 2019. [Online;
accessed 21-May-2019],
[11] Bjöm Johansson, Maben Rabi, and Mikael Johansson. A randomized incremental subgradient method for distributed optimization in networked systems. SIAM J. Optim.. 20(3): 191-11157111 2009.
[12]
Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mchdi Bennis, Arjun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. L. D'Oli'Oviin Salim El Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaïd Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi. Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konecný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint. Yang Liu, Prateck Mittal, Mehryar Mohri, Richard Nock. Ayfer Özgür, Rasmus Pagh, Mariana Raykova, Hang Qi. Daniel Ramage, Ramesh Raskar, Dawn Song, Weikang Song, Schastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramer, Pranceth Vepakomma, Jianyu Wang, Li Xiong, Zheng Xu, Qiang Yang, Felix Yu, Han Yu, Sen Zhao. Advances and open problems in federated learning. arXiv, abs/1912.04977, 2019.
[13] David Kempe, Alin Dobra, and Johannes Gehrke. Gossip-based computation of aggregate information. In FOCS, pages 482-491, 491, 2003.
[14] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR, 2015.
[15] Chih-Kai Ko. On Matrix Factorization and Scheduling forFinite-time Average-consensus. PhD thesis, California Institute of Technology, 2010.
[16] Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian U. Stich. A unified theory of decentralized SGD with changing topology and local updates. In Proc. ICML, volume 119, pages 5381-5393, 2020.
[17] Alex Krizhevsky. Learning multiple layers features from tiny images. University of Toronto, 05 2012.
[18] Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar-10& (Canadian Institute for Advanced Research).
[19] Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? case study decentralized parallel stochastic gradient descent. In NewrIPS, pages 5330-53444 2017.
[20] Tao Lin, Sai Pranceth Karimireddy, Scbastian U. Stich, and Martin Jaggi. Quasi-global momentum: Accelcrating decentralized deep lcarning on heterogencous data. CoRR, abs/2102.04711, 2021.
[21] Hanxiao Liu, Andy Brock, Karen Simonyan, and Quoe Le. Evolving normalization-aativtiin layers. In NeurIPS, 2020.
[22] Paolo Di Lorenzo and Gesualdo Scutari. Next: In-network nonconvex optimization. IEEE Transactions on Signal and Information Processing over Networks, 2(2)) 2016.
[23] Yucheng Lu and Christopher De Sa. Optimal complexity in decentralized training. In Proc. ICML, volume 139, pages 7111-7123, 18-24 Jul 2021.
[24] Brendan McMahan, Eider Moore. Daniel Ramage, Seth Hampson, and Blaise Agüera y Arcas. Communication -efiiciennniiinnttte learning of deep networks from decentralized data. In Proc. ICOAL, volume 54, pages 1273-1282, 2017.
[25] Angelia Nedie. Distributed gradient methods for convex machine learning problems in networks: Dis- tributed optimization. IEFE Signal Process. Mag., 37(3)922-101, 2020.
[26] Angelia Nedic and Alex Olshevsky. Stochastic gradient-push for strongly convex functions on time-varying directed graphs. IEEE Trans. Autom. Control., 6111333936-3347, 2016.
[27] Angelia Nedić and Asuman Ozdaglar. Convergence rate for consensus with delays. Journal of Global Optimization, 47(3):437-455 2010.

---

[28] Angelia Nedic and Asuman E. Ozdaglar. Distributed subgradient methods for multi-agent optimization. IEEE Trans. Autom, Control., 54(1):48-61 61, 2009.
[29] Angelia Nedic, Alex Olshevsky, and Wei Shi. Achieving geometric convergence for distributed optimization over tame-varying graphs. SIAM J. Optim.. 27(4):2597-266) 2017.
[30] Radia J. Perlman. An algorithm for distributed computation of spanningtree in an extended LAN. In SIGCOMM, pages 44-53, 1985.
[31] Shi Pu and Angelia Nedic. Distributed stochastic gradient tracking methods. CoRR, ahs/1805.111 1454, 2018.
[32] Shi Pu, Wei Shi, Jinming Xu, and Angelia Nedic. Push-pull gradient methods for distributed optimization in networks. IEEE Trans. Autom. Control., 16:61))11,,, 2021.
[33] Peter Sanders, Jochen Speck, and Jesper Larsson Träff. Two-tree algorithms for full bandwidth broadcast, reduction and scan. Parallel Compur., 35(12):581-544 2009.
[34] Victor Sanh, Lysandre Dehut, Julien Chaumond, and Thomas Wolf. Distilbert, a distilled version of BERT: smaller, faster, cheaper and lighter. CoRR, abs/1910.01 108, 2019.
[35] Sebastian U. Stich. Unified optimal analysis of the (stochastic) gradient method. CoRR, abss/197..04222 2019.
[36] Hanlin Tang, Xiangru Lian, Ming Yan, Ce Zhang, and Ji Liu. D²: Decentralized training over decentralized data, Proc. ICML, volume 80, pages 4855 4863, 2018.
[37] Konstantinos Tsianos and Michael G. Rabbat. Distributed consensus and optimization under communi- cation delays. In Allerton, pages 974-982, 2011.
[38] Konstantinos Tsianos, Sean F. Lawlor, and Michael G. Rabbat. Push-sum distributed dual averaging for convex optimization. Proc. CDC, pages 5453-5458, 2012.
[39] Chenguang Xi and Usman A. Khan. DEXTRA: A fast algorithm for optimization over directed graphs. IEEE Trans, Automat. Contr, 6280044498,-4,9,, 2017.
[40] Chenguang Xi, Van Sy Mai, Ran Xin, Eyad H. Abed, and Usman A. Khan. Linear convergence in optimization over directed graphs with row-stochastic matrices. IEEE Trans, Autom. Control., 63(1)): 3558-3565, 2018.
[41] Lin Xiao and Stephen P. Boyd. Fast linear iterations for distrihuted averaging. Syst. Control. Lett., 53(1): 65-78, 2004.
[42] Ran Xin and Usman A. Khan, linear algorithm for optimization over directed graphs with geometric convergence. IEEE Control. Syst. Lett., 213):35--300 2018
[43] Ran Xin and Usman Khan. Distributed heavy-ball: A generalization and acceleration first-order methods with gradient tracking. IEEE Truns. Autom. Control., 6566)22627-2633,, 2020.
[44] Ran Xin, Chenguang Xi, and Usman A. Khan. FROST fast row-stochastic optimization with uncoordi- nated step-sizes. EURASIP J. Ady. Signal Process., 2019:1, 2019.
[45] Kun Yuan, Bicheng Ying, Xiaochuan Zhao, and Ali H. Sayed. Exact diffusion for distributed optimization and learning part I: algorithm development. IELE Trans. Signal Process. 67(3):708-723, 2019.
[46] Kun Yuan, Yiming Chen, Xinmeng Huang, Yingya Zhang, Pan Pan, Yinghui Xu, and Wotao Yin. Decent- lam: Decentralized momentum SGD for large-hatch deep training. CoRR, abs/2104: 1981, 2021.
[47] Mikhail Yurochkin, Mayank Agarwal, Soumya Ghosh, Kristjan H. Greenewald, Trong Nghia Hoang, and Yasaman Khazaeni. Bayesian nonparametric federated learning of neural networks. In Proc. ICML, volume 97, pages 7252-7261, 2019.
[48] Jiaqi Zhang and Keyou You. Decentralized stochastic gradient tracking for non-convex empirical risk minimization, 2020.
[49] Xiang Zhang, Junbo Jake Zhao, and Yann LeCun. Character-level convolutional networks for text classification. In NeurlPS, pages 649-657, 2015.
[50] Zhaorong Zhang, Kan Xie, Qianqian Cai, and Minyue Fu. A bp-like distributed algorithm for weighted average consensus. In Proc. ASCC, pages 728-733, 2019.
12


Reviews:
[{"review_id": "fGIuiiB0fPZ", "reviewer": "Reviewer_zW5E", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is easy to follow and well written. The investigated topic is particularly critical as decentralized learning has been demanding in the era of big data. However, several major issues came up to my mind when I reviewed the paper carefully.\n1.\tIssue of topology. The authors mentioned in line 121 that the key insight of this work 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. It looks like the RelaySGD has specifically been designed for such a structure of networks. Though the authors in lines 137 and 138 have emphasized that RelaySGD can be used in any communication graph if a corresponding spanning tree is constructed. However, throughout the paper, I have not seen any techniques of converting any communication graph into a spanning tree. Additionally, all experimental results have been shown in terms of spanning trees for RelaySGD. It is difficult to evaluate if RelaySGD really works for other communications graphs.\nFurther, as the additional memory is linear in the number of a worker’s direct neighbors, it means that for a large-scale network, the computational overhead will increase exponentially?\n2.\tUnfair comparison in experimental results. As shown in Table 1, the topologies considered for different algorithms are different. In the empirical results, the accuracies were obtained for different algorithms with different topologies, which rendered the unfair comparison. Probably as the authors suggested, some conversion can be done to turn any communication topology into a spanning tree, but the empirical results presented in the paper cannot convince myself that the proposed RelaySGD has superiority over existing methods. For example, in Table 3, RelaySGD w/ momentum seems to perform better than SGP w/ momentum. But it is difficult to tell if the different is just caused by the difference between topologies. Moreover, why for SGP w/ momentum and D^2 w/momentum (or DP-SGD w/ momentum), do they also need different topologies in this work?\n3.\tConfusing and/or problematic analysis. (a) In the supplementary materials, the authors introduced Assumption H for the bounded noise at the optimum. While the similar property has been defined in Assumption B. Any relation between these two? Why did the authors define such an assumption for the optimum point, which has not typically been seen in the previous works. (b) The complexity for strongly convex case in Theorem looks problematic. As the $\\epsilon$ has been used to signify the complexity, why did the authors still include the time $T$ in the complexity, which hasn’t been seen in any previous works? That way, the exact time $T$ required to achieve the $\\epsilon$-accuracy is not obtained. (c) In Assumption I, the authors defined $M$ to be 0. Why is this case? I think Assumption I has been quite generic in previous works. That way, could the authors directly define Assumption I at the beginning? Why is the motivation to define two slightly different assumptions in the work? (d) In the proof, a matrix is denoted by a capital bold letter. However, in Lemma 11 and Lemma 12, the authors just used capital letter, which can be confusing. Also, in terms the norm, the authors at the beginning have defined that $||\\cdot||$ is spectral norm for a matrix while 2-norm for a vector. It is easy to know that $||\\cdot||_F$ represents Frobenius norm. What is $||B||_2$? Also, Lemma 9 – Lemma 12 are trivial and typically the authors can only mention in the proof. There is no need to give formal statements for these. (e) In line 183, the authors mentioned that the dominant term is a function of $\\mathcal{O}(1/\\epsilon^2)$, while in line 191, the leading term became $\\mathcal{O}(1/\\epsilon)$. Is it a typo or anything else?\n4.\tIn lines 39 and 40, the authors said that the slow distribution of updates not only slows down training, but also makes decentralized learning sensitive to heterogeneity in workers’ data distributions. Why is this true? The second half may not be true. If each agent in a networked system has quite different data distributions, without effective techniques, even if the distribution of updates is fast, the performance is still poor. Since each agent tries to converge to its own optimal solution, the consensus among them enables a suboptimal solution to the global objective function. Therefore, regardless of the distribution rate of updates, decentralized learning is always sensitive to the heterogeneity.\n5.\tThe dependence of RelaySGD/Grad on the data heterogeneity is a bit surprising to me. Though the table before Algorithm 6 illustrates the difference between RelaySGD and RelaySGD/Grad, it is confusing to me why the authors have introduced the RelaySGD/Grad in the work. It is also not robust to lost messages and workers joining/leaving. What is the motivation here? Are there any scenarios in which RelaySGD/Grad has superiority? \nOverall, the paper in the current form still requires substantial changes, particularly for the experimental results and some theoretical complexity analysis. I hope my comments can help the authors address these potential issues.\n\n============Review Update=============\n\nAfter carefully reading the rebuttal from the authors, and other reviewers' comments, I decided to raise my score. The responses from the authors clarified most of my major comments. Hopefully the authors can include the corresponding changes in the final draft to make it solid.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have not adequately addressed the limitations and potential negative societal impact of their work. It would be great for the authors to add one paragraph to briefly discuss.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "Wpt7X-9MesS", "reviewer": "Reviewer_ja4W", "summary": "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).\n\n=== Review Update ===\n\nThank 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.\n\nAfter reading both the authors' response and the other reviewers' comments, I've decided to keep my score as-is.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality\n- Delayed optimization over a distributed network is not a new idea, see Distributed Delayed Stochastic Optimization (Duchi and Agarwal, 2011). This paper should have been cited and discussed in the related work, though I still lean towards acceptance in spite of this issue.\n- The paper's main idea is that messages are aggregated in a way that the memory and network costs are independent of network diameter (i.e. no need to maintain multiple delayed messages \"in-flight\"). I believe this is an original contribution.\n\nQuality\n- Wide coverage across multiple experimental factors: simulation vs real data, multiple competing baselines, various network toplogies, covers both SGD and Adam, and at least one model from CV (VGG, ResNet) and NLP (Bert).\n- Interesting and insightful experiments that go beyond mere benchmark-chasing\n- Theoretical proofs are sufficient and welcome, though I do not believe there is innovation in the proof techniques\n\nClarity\n- Clear organization of ideas, writing and illustrations are a cut above the typical NeurIPS paper\n- Minor issue: the main writing should state clearly that VGG is used for CIFAR10 experiments. This fact is only briefly mentioned in figure captions.\n\nSignificance\n- Reducing communication in distributed training is a crucial topic, especially when model sizes have grown several orders of magnitude over the last few years\n- However, even in Federated Learning, it is not clear to me if applications truly benefit from multiple communication hops. The issue is that topologies are usually \"virtual\" in peer-to-peer FL applications - it is up to the implementer to decide whether to use a fully connected topology (which does not need delayed communication) or not. Thus, the network topology is not an immutable constraint; it is merely a design choice.\n- In connection with the previous point: there is one ablation experiment that is missing from the paper, and that is to compare the method on different non-fully-connected topologies vs the state of the art on a fully-connected one, under realistic assumptions for peer to peer applications. Such an experiment would have made the paper much stronger\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No issues", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5"}, "extra_text": {}}, {"review_id": "CW0kCcS6xe", "reviewer": "Reviewer_D5b5", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The clarity of this paper can be improved, but ultimately, I found this work interesting and sufficiently significant. I do however have some questions about the correctness of the theory and significance of the results that I hope the authors can address in their rebuttal.\n\n- The proposed RelaySGD is equivalent (analytically) to running gossip SGD over an all-to-all graph with fixed delay along each edge based on the number of hops between nodes in your spanning tree. This may result in faster mixing than regular gossip, and the experiments are convincing. However, precisely demonstrating this result would strengthen the paper, for example by constructing an augmented graph (see Chapter 10 of \"Convex optimization in signal processing and communications\" 2010 by Nedic and Ozdaglar) with the appropriate mixing weights, and comparing the spectral radius of that augmented graph to the spectral radius of a regular doubly-stochastic gossip matrix over various topologies.\n\nOn the theory:\n- I may be missing something, but the matrix W does not look row-stochastic. Consider \\tau=0, i=0, j=1 in a chain. Then [W]_{0, n+1} = 1/n and the rest of the row is equal to 0. Therefore, the rows of W do not sum 1.\nNote that for the analysis you can simply apply known results in the literature for gossip with augmented graphs (e.g., see the reference about), hence I am not concerned about the empirical convergence of the method.\n\nPracticality:\n- Compared to regular gossip, the method requires each node to store one memory buffer for each neighbor, but has same communication cost, as parcels are summed before communicating. The memory overhead is not great, but as long as the number of neighbours remains small, this should be find and comparable to adaptive gradient methods like Adam.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No obvious negative societal limitations or impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents a new communication protocol for decentralized learning when the nodes have significant data heterogeneity. The reviewers all agreed about several of the positives of the current draft: good presentation, extensive experiments, interesting ideas. The main concern was the algorithmic novelty of the scheme (similar to tree-reduce, and gossip with delays), and the memory overhead proportional to the number of neighbors. However, it was agreed during discussions that this work carries enough technical depth to be interesting to the related communities (decentralized/fed learning).
Decision: Accept (Poster)