Moshpit SGD: Communication-Efficient Decentralized Training on Heterogeneous Unreliable Devices
Authors: Max Ryabinin
Eduard Gorbunov
Vsevolod Plokhotnyuk
Gennady Pekhimenko
Venue: NeurIPS 2021 Poster (2021)
Keywords: decentralized training
distributed training
optimization

Abstract: Training deep neural networks on large datasets can often be accelerated by using multiple compute nodes. 
This approach, known as distributed training, can utilize hundreds of computers via specialized message-passing protocols such as Ring All-Reduce.
However, running these protocols at scale requires reliable high-speed networking that is only available in dedicated clusters.
In contrast, many real-world applications, such as federated learning and cloud-based distributed training, operate on unreliable devices with unstable network bandwidth.
As a result, these applications are restricted to using parameter servers or gossip-based averaging protocols.
In this work, we lift that restriction by proposing Moshpit All-Reduce — an iterative averaging protocol that exponentially converges to the global average.
We demonstrate the efficiency of our protocol for distributed optimization with strong theoretical guarantees.
The experiments show 1.3x speedup for ResNet-50 training on ImageNet compared to competitive gossip-based strategies and 1.5x speedup when training ALBERT-large on preemptible compute nodes.

Moshpit SGD: Communication-ffficent Decentralized Training on Heterogeneous Unreliable Devices
Max Ryabinin" Yandex, Russia
Eduard Gorbunov*
Vsevolod Plokhotnyuk Yandex, Russia HSE University, Russia
MIPT, Russia
HSE University, Russia
HSE University, Russia Yandex, Russia
Gennady Pekhimenko
University of Toronto, Canada Vector Institute, Canada
Abstract
Training deep neural networks on large datasets can often be accelerated by using multiple compute nodes. This approach, known distributed training, utilize hundreds computers via specialized message-passeee paageeg protocols such as Ring All-Reduce. However, running these protocols scale requires reliable high-speed networking that is only available in dedicated clusters. In contrast, many real- world applications, such federated learning and cloud-based distributed training, operate on unreliable devices with unstable network bandwidth. As a result, these applications are restricted to using parameter servers or gossip-based averaging protocols. In this work, we lift that restriction by proposing Moshpit All-Reduce iterative averaging protocol that exponentially converges to the global average. We demonstrate the efficiency of our protocol for distributed optimization with strong theoretical guarantees. The experiments show 1.3x speedup for ResNet-50 training on ImageNet compared to competitive possip-based strategies and 1.5x speedup when training ALBERT-large on preemptible compute nodes.
Introduction
Many recent influential discoveries in deep learning were enabled by the trend of scaling model and dataset size, Over the last decade, computer vision has grown from training models with 60 million parameters [ on 1.3 million images [2] to 15 times more parameters 3 and 200 times more training data (4. In natural language processing, parameters are trained on over 570GB of texts, and even this does not saturate the model quality [6] Training these large models can take years even with a top-of-the-ling theeeee GPU server [7]. As a result, researchers and practitioners often have run distributed training with multiple machines (8).
with 175 billion state-of-the-art language models
The dominant approach to distributed deep learning is data-paralle training ( where each worker processes a fraction of the training batch and then exchanges its gradients with peers. If done naïvely, the gradient exchange step can overload the network as the number of workers increases. To combat this issue, modern distributed training algorithms take advantage of commumication-efiiciii protocols, such as all-reduce [0]. These protocols allow workers to collectively compute the global average gradient with constant communication overhead, regardless of the total number of peers.
Equul contribution. Correspondence mryabinino@@mail.comm com.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

However, this efficiency makes the protocols more fragile: if any single participant fails or takes too long to process its batch, all other nodes are stalled. Therefore, scaling all-reduce protocols beyond couple of servers requires specialized infrastructure with dedicated ultra-high bandwidth networking [8] This kind of infrastructure is notoriously expensive compared to regular GPU servers or preemptible cloud VMs (see Appendix A for details).
Hence, it is tempting to consider distributed training on cheap unreliable instances cost-eflicient alternative. A similar scenario arises in federated learning M.. where a single model is trained on heterogeneous devices due to privacy concerns. In both scenarios, workers use a shared network, where both latency and bandwidth can vary drastically due to interference from other users [12]. Furthermore, compute nodes are also subject failure (or preemption) caused by factors beyond the protocol's control.
Running large-scale distributed training in these circumstances requires fault- and latency-tolerant algorithms [1] 15]. Most of these algorithms replace all-reduce averaging with gossip: each participant periodically downloads the latest parameters from their neighbors in a sparsely connected communication graph and averages the results. The updates gradually propagate through the graph over multiple rounds of averaging. However, the communication required to perform gossip grows linearly with the number of neighbors. Hence, when scaling to hundreds of peers, decentralized SGD has to keep the communication graph sparse. slowing down the convergence.
In this work, we propose an alternative approach. Instead of relying on a predefined communica- tion graph, participants dynamically organize themselves into groups using a fully decentralized matchmaking algorithm called Moshpit All-Reduce. This strategy allows us to use communication- efficient all-reduce protocols that significantly reduce the network load compared gossip-based averaging, while still being able to operate in unreliable hardware and network conditions.
Our contributions can be summarized as follows:
We propose Moshpit All-Reduce a novel decentralized averaging protocol for large-scale training with unreliable communication-constee method has exponential convergence rate independent of network topology and size.
devices. According to analysis, this
Armed with this averaging protocol, we develop Mashpit SGD for distributed optimization. We derive convergence rates for this algorithm and establish its equivalence to Centralized (Local) SGD in terms of iteration complexity under realistic assumptions.
Our experiments demonstrate that Moshpit All-Reduce is significantly more efficient under network latency in realistic conditions. In particular, we train ResNet-50 on ImageNet to 75% accuracy 1.3 times faster than existing decentralized training algorithms and pretrain ALBERT-large 1.5 times faster on preemptible cloud VMs
2
Related Work
2.1 Data parallel training
The most popular way to accelerate neural network training with multiple devices is data-parallel training 9 16 17 On each optimization step, this strategy splits the training batch among partici- pants. Each participant then runs forward and backward passes to obtain gradients of the objective function on their part of the training batch. After that, we can aggregate the gradients from workers and perform an optimization step. There are two main strategies for this aggregation.
Historically, the first solution to gradient aggregation process or a dedicated server that keeps track model parameters and optimizer statistics. After each round, the PS accumulates the gradients from each worker and updates the model parameters using SGD or any other optimizer, such as Adam [9 Finally, the server distributes the updated model parameters workers.
Parameter Server (PS) [8] separate
This strategy is robust and easy to implement, but requires the server to regularly download full model gradients from every single worker. As result, the parameter server can quickly become a bottleneck for large-scale training [20). Since the original PS, researchers have proposed several modifications that reduce the communication load: accumulating multiple batches [22
compression 23 24], server sharding 25 26 A more detailed overview is given in Appendix
Immleeeenttiinn and code of experiments at ppperinnntsccaggggggt.bb.oooooae gtt.bbb.co//mmeeee.rrrerreeeeees

---

In turn, many practical distributed training systems have instead switched to averaging with All- Reduce [6 27 28 T7]. This name refers collection of protocols originally developed for HPC gradient more applications. Workers can follow these protocols to collectively compute the average gradient efficiently than with a central server.
2.2
Communication--ffiienn All-Reduce
There are several all-reduce protocols optimized for different network topologies. The simplest one is known Butterfly All-Reduce [T]. Each of N participants splits its local vector into N chunks. Then, i-th worker aggregates i-th chunk of data from all peers and sends back the averaged chunk.
Split
Scatter
Reduce
All-Gather
Worker
X1
May
Worker
Σ
Day
hur
Worker
Figure 1:
schematic illustration of Butterfly All-Reduce.
As long as the vector size is greater than N, this protocol uses O (s x Aw1)) total bandwidth on each worker. However, it requires all-to-all communication, which is not always practical for the HPC infrastructure due network contention [O]. As result, real-world systems typically use Ring or Tree All- IllRReduee, where each worker only communicates with small subset of its peers.
These protocols enable highly efficient and scalable averaging with O(1) Olog N) total commu- nication per worker, but they also share a common drawback: they cannot tolerate node failures or network instability. If any single participant fails to execute its part takes long respond, this paralyzes all other workers.
2.3 Distributed training in unstable conditions
Some distributed training applications must deal with unstable network bandwidth and/or unreliable workers. This issue is most prevalent in federated learning [T 29 30). When dealing with privacy- sensitive data distributed across multiple actors, such hospital servers B1
32 mobile phones [33
34], one must train the model using whichever hardware and network available to those actors.
Another important motivational factor is cost: HPC-grade infrastructure can be prohibitively expen- sive, pushing researchers and practitioners towards commodity servers or preemptible cloud VMs that are significantly cheaper (see Appendix A Another solution is to use volunteer computing 35 36) with abundant, but even less reliable, compute resources.
Training under these conditions requires specialized strategies. At small scale, one can deploy one few reliable parameter servers aggregate the updates from workers. This strategy can tolerate individual node failures (37), but scales poorly due to the reasons discussed in Section 2.1
2.4 Decentralized training
If there too many participants for PS, it can be advantageous to use decentralized SGD via gossip-based averaging [38 39 14]. In this scenario, participants form a sparse graph: each worker periodically downloads parameters from its neighbors and mixes them with local parameters.
In essence, gossip-based averaging removes the communication bottlenecks of PS at the cost of using different local parameters on each peer. That said, gossip-based optimization algorithms can match, and sometimes even outperform, their centralized counterparts in terms of training speed [40] 41 42 [4 43). However, the convergence properties of gossip averaging and gossip- based optimization methods significantly depend on the communication graph through the spectral
properties of the mixing matrix [4 42 or the Laplacian matrix of the network 45 46).
All- Reduce works with any commutative associative operation, such min, max, product.

---

Consequently, as the number of peers increases, gossip- averaging has to either increase the number of neighbors (hence more communication) or accept slower convergence speed. Because of this, gossip is less communication-effiienn than all-reduce algorithms reviewed in Section 2.2 However, gossip-based algorithms are more robust to changes, which makes them applicable to time-varying networks [47 48 49 50
and federated learning 51 52 53
3 Moshpit SGD
Large-scale training with unreliable participants requires protocol that is both communication efficient and fault-tolerant. Unfortunately, existing methods have only provide one of these properties. To better address our conditions, we propose Moshpit All-Reduce a fully decentralized averaging protocol that combines the efficiency of all-reduce and the fault tolerance of gossip-based averaging.
The rest of this section organized as follows:
describes the protocol and proves its correctness and communication efficiency; provides the analysis of the protocol and proves exponential convergence rate for averaging and the rate matching the one of centralized Local-SGD for optimization; contains implementation details for training with heterogeneous compute nodes.
Section 3.1
Section 3.2
Section
3.3
3.1 Moshpit All-Reduce
The core idea of Moshpit All-Reduce is that workers perform averaging in small independent groups. That way, single failed participant would only affect his current group. In turn, the composition of each group should be chosen dynamically to converge in the least number of steps. Ideally, if there 9 peers with local parameters 0, we average them in 2 rounds, as demonstrated in Figure
Algorithm Moshpit All-Reduce (for i-th peer)
First round
Second round
Input:
number of peers N, d, M, number of iterations T, peer index
parameters {0, J/V
Grup
Average 0 in groups
0 : 0,
Group
C :- gee_geeittttt initial_indexxx
for E E...
D ; [ add aadd(address;)
Matchmaking // wait for peers assemble
peers, == DHT get ( (C,--1
Figure Example averaging order for 9 peers in 2 rounds. On each round, peers split into 3 groups that run All-Reduce parallel.
0 AllReduce (0 (
peers,)
C (C) [1:] c // same eq. (1)
end for Return 07
To achieve this in a decentralized system, we use Distributed Hash Tables (DHT) a decentralized key-value storage: Appendix contains its more detailed description. On each averaging round:
Each worker computes its group key Cj;
Workers add their network addresses the DHT key corresponding Cs; Each worker can now fetch full list of peers that have the same C, and run All-Reduce with those peers.
Unfortunately, the averaging structure from Figure is impossible to maintain when participants constantly joining, leaving, and failing. However, we can achieve equivalent results without global structure using a simple rule: if two peers were the same group in round t, they must choose different groups in round 1+
natural way to enforce this rule to take advantage of the chunk indices from Butterfly All-Reduce (see Figure IT. Recall that each worker accumulates a unique chunk of parameters defined by an index e. By setting C, == C; we can guarantee that any workers that were in the same group at round will have different group indices in round 1+1.

---

This averaging scheme can be generalized to more than two dimensions in order to fit a larger number of peers or reduce the group size. For a d-dimensional hypercube. nodes should find groups of peers that they have not communicated with during d-1 previous rounds. To that end, we define C. as tuples containing chunk indices from d previous rounds (t. denotes the communication round):
C = (c) (c2-d+1, & dd ......)..
d+1
(I)
The above intuition can be formalized with Algorithm T Here, N peers form a virtual d-dimensional grid with . peers per row and average their parameters 0g over T rounds. DHT[.] is shorteut for using the DHT to add or retrieve values for a given key. The Matchmaking step corresponds to the decentralized matchmaking procedure that organizes active workers with the same index into groups, described in detail in Appendix E In turn, AllReduce denotes running all-reduce to compute the average 0 in a given group. The get_ iil.initti Amitiill_e titl_iinexx function takes the peer index and returns d-1 integers in range [o, M such that the size of initial groups does not exceed M. This way, the groups formed on subsequent rounds will also have at most M participants. One possible strategy is:
get get_initial (nndiitialiindx(()) = (Li/MØ-') mod M)
jE(L, ....) 4}
(2)
If N" and there are no node/network failures, Algorithm| is equivalent to Torus All-Reduce [54]. achieving the exact average after d rounds of communication (see Appendix C.T.p However, our typical use case is far from this perfect scenario; for example, some groups can have less than M members. Furthermore, a peer might fail during all-reduce, causing its groupmates to skip a round of averaging. Still, Moshpit All-Reduce is applicable even in these conditions:
Theorem 3.1 (Correctness), If all workers huve non-zero probubility of successfully running communication round and the order of peers, is random, then all local vectors ff converge to the global average with probability I:
Vi,
0
80
0.
(3)
N
Proof (sketch, complete in Appendix invariant N Σ, Σ, and reduces the deviation of f from the overall average.
C.2y. Running all-reduce with subset of peers preserves the
N
Complexity. The matchmaking protocol is implemented over Kademlia DHT (55), meaning that each read and write operation needs at most Ollog N) requests and O(M) bandwidth to load peers,
After the matchmaking is over, each group runs single all-reduce round to compute the average. In principle, Moshpit Averaging can use any general ceneral-purpose purpose all-reduce protocol. We opted for a butterfly-like version (Figure[], is simpler than Ring All-Reduce while still being communication- efficient. The communication complexity of this algorithm is O (max((, 8, M) x
M R-1),, where is
Ar
the size of vector 0. Thus, the total time complexity of Algorithm becomes:
o T x logg N + M + max(s, M) x
M
(4)
M
This compares favorably to gossip, where network load grows linearly with the number of neighbors.
3.2
Convergence analysis
3.2.1
Mixing properties of Moshpit Averaging
As stated in the previous section, Moshpit All-Reduce computes the exact average when N = Md. which cannot be guaranteed in practice. Therefore, additional analysis is needed to establish how quickly Moshpit Averaging approximates the actual average of N vectors stored on peers.
In the following theorem, we provide such analysis for simplified version of Moshpit Averaging. One can find the full proof in Appendix C.3)
Theorem 3.2. Consider modification of Moshpit All-Reduce that works as follows: at each iteration
k 2 1, 1) peers are randomly split in disjoint groups of sizes ....,..M M in such way that E. Ma = N and MtK 2 for all i 1,..., and 2) peers from each group compute their group average via All-Reduce. Let .I,..., O2 be the input vectors of this procedure and o7 .f.....88 By be the
outputs after T iterations. Also, let 0- N
1
EN 8 Then.
T
N
10 - 0112 =
T
110 - 0112.
(5)
N2
5

---

Algorithm 2 Moshpit SGD
1: Input: starting point 09, learning rate 7 communication period 2
2: for k == =. 1...,...0 do
3: for each peer E Pk+1 in parallel do
4: Compute the stochastic gradient 9fº at the current point 0 then
5: if k mod
6:
0.+11 Moshpit All-Reduce JEPL+1 (0) -795) for i-th peer (Algorithm) !
7:
else
8: gh+1 0, -9
9: end if
end for
11: end for
In particular, this result implies that even if workers are randomly split into pairs at each iteration, the simplified version of Moshpit Averaging makes the average distortion (the left-hand side of Equation 5) less than in expectation after O (log(//)) (7/s) iterations. That is, this algorithm finds e-accurate average on each node with the rate that does not depend on the spectral properties of the communication graph like gossip and its variants (see Section 2.4 and Appendix B.T. Since Moshpit Averaging prevents two peers from participating in the same groups during successive iterations, the actual algorithm should find E-accurate averages participating peers even faster than Equation predicts. Moreover, in Appendix [C33 we explain how this result can be generalized to the case when (M} R=1 and depends on & even is random. In Appendix C.4 we also provide the guarantees measuring how fast Algorithm| reduces the variance when averaging random vectors.
3.2.2 Moshpit SGD
We consider classical distributed optimization problem
1 N
min
f(0)
(6)
OER"
where NN is the number of workers and worker has access only to the function fi. We propose a new algorithm called Moshpit SGD solve this problem (see Algorithm 2 In this algorithm, workers perform independent local SGD steps and periodically synchronize their parameters 8 with other peers using Moshpit All-Reduce. Moreover, we define the indices of participating nodes at iteration i Pk+1 (Po (1, ......Ny NN) allowing peers to vanish.
First of all, list the key assumptions that
in the convergence analysis of Moshpit SGD).
Assumption 3.1 (Bounded variance). We assume that for all k 2 and 1,..., N stochastic gradients of satisfy go 0!] = V (0h)) and
I| F1(0))12 0.1 S o².
This assumption is classical the stochastic optimization literature [56 57
We notice that our
analysis can be generalized to the settings when the stochastic gradients satisfy less restrictive assumptions such as expected smoothness [58 or have more sophisticated structure similar to (59)
using the theoretical framework from [60].
The following assumption controls the averaging properties and the effect of the peers' vanishing.
Assumption 3.2 (Averaging quality & peers' vanishing). We assume that the vanishing of peers does not change the global average of the iterates of Moshpit SGD too much, i.e., Pe+1 C Ps and [P&| 2 Nmin all k Z 0, |Par S 2(Pa(r+1)) for all non-negative integers a 2 0, and there exist such 0 E B. and a sequence of non-negative numbers {A p 3 k20 that wh: 2 0
E [(t - - gh+l
T++1 -20)
< A puy convex;
(8)
E ( (V()))), gh+l - + 01 - -r- 112 < Aport non-conver, L-smooth, (Def. D.1
(9)
where N₂ PPel, gh+1= = New
1 Eie 1 and x++1 1111 No Eiery (0) ~ggt) for k 0.

---

Moreover, we assume that for some dag 2 0 and for all nen-tigative integers a 2 0.
E
1
Σ
10
-gar garl?
S 7 700
(10)
N OT
iEPur
If P; = Pk+1 = (1,.... N for a 2 i.e., peers do not vanish, then 6 Jh and properties (8
hold with Ap. pv = O for all 2 0. Moreover, according to the mixing properties of Moshpit Averaging established in Theorem 3.2 inequality I0 holds after O (log (1/+"62,) iterations Algorithm Therefore, the assumption above is natural and well-motivated.
Under these assumptions, we derive the convergence rates both for convex and non-convex problems. The full statements and complete proofs are deferred to Appendix [
Theorem 3.3 (Convex case). Let fi =... IN L. function f be ju-strongly convex (Def. D.2 and L-smooth (see Def. [.I). and Assumptions 3.1 and 3.2 hold with A 6pp,7"1eE1110 0"
728000. and 0 0", where 0" E aargminges.. 5(0) and 6pu, E 10, 1), 8pc 2 O. Then there exists choice of y such that T
((0") s(0r) s after K iterations of Moshpit SGD, where K equals
L
2 /
L((T 1((T-117 ([(T-1)02+
*V
11 0:
(11)
1p
(1
8pm,))eE
(1 pp- )
LR
R8
pu,2
+o²//mina
Ryy [I(T [((T-1)22 2
1 O,
(12)
g²
8//
where 0*
WyO. wy = (1- WK
>x= WK: Ro = 1100 0" and
k=U
VeP
(-) hides constant and log(2/: 2/) factors.
That is, if 6pe,1 S. 1/2, Nin = ((N 8p. O((")a)). and 82, = O((T - 1)o²). then Moshpit SGD has the same iteration complexity as Local-SGD in the homogeneous case [61 However, the averaging steps of Moshpit SGD are much faster than those of the parameter-server architecture when the number of peers is large. Also, unlike the state-of oftt----t-hht- convergence guarantees for Decentralized Local-SGD [63), our bounds do not depend on the spectral properties of the communication graph (see Appendix B. for the details).
IN = function f be L-smooth and bounded from below by f.. and Assumptions 3.1 and 3.2 hold with A
Theorem 3.4 (Non-convex case). Let f1
& /p f ((*))l + L^² 6p
po 5pu;1 E [0. 1/2),. 5pe.2 2 O. Then there exists such choice of that E [[[V (OK iterations of Moshpit SGD, where K equals
rand |[ & e² after K
0
LAn
1 /1 1- -2 pv,
By //minn (11-26 1)(2 ( 1)0
p0
Ao f(0") f(00) and @K
rand is chosen uniformly from (00 0 OK
0k defined in As. 3.2
Again, if 6pc,1 < 1/3, Nuin ((N), 22 O(o") and 82, O((r 1)o²), then the above theorem recovers the state-of-the -ht---rttt--tttt art results in the non-convex case for Local-SGD [64 63
3.3 Implementation details
Training on heterogeneous unreliable hardware also poses number of engineering challenges. The most obvious one is that the system must be able recover from node failures. To address this challenge, we use fully decentralized infrastructure where all information is replicated in Dis- tributed Hash Table; see Appendix B.5 for details. When a new worker joins midway through training. it can download the latest model parameters and metadata from any other peer (see (Appendix F). Another challenge arises when devices in a group have uneven network bandwidth. In that case, we dynamically adjust the communication load of each peer to avoid being bottlenecked. More information on this procedure can be found in Appendix G
7

---

4
Experiments
In this section, we conduct empirical evaluation of the proposed averaging protocol and its conre- sponding optimization algorithm. First, we check the theoretical properties of Moshpit All-Reduce in a controlled setup (Section[4.) 4.1). Then, we compare Moshpit SGD with other distributed methods on practical tasks of image classification and masked language model pretraining (Sections 4.2 and
4.1 Decentralized averaging
In this series of experiments. we aim to empirically verify the convergence and fault tolerance properties proven in Section 3.2 To measure this in a controlled setting, we create peers with parameters that are scalar values drawn from the standard Gaussian distribution. We study the convergence of different distributed methods with respect to the number of workers N and their individual failure rate for single iteration of averaging p (failed peers return in the next round).
We compare Moshpit Averaging with the following algorithms from prior work: All-Reduce (with restarts in case of node failures), Gossip, PushSum (equivalent the method described in (33). Also, we provide the results of averaging in random groups as a simpler version of our approach. However, the implementation of group averaging maintains approximately the same group size across all iterations: this property might be hard to achieve in decentralized setting, and as a result, the estimate of this method's 's performance should be considered highly optimistic.
We report the average squared difference between the worker parameters and the actual average of all values; the results are averaged across 100 restarts from different random initializations. We compare the convergence for 512-1024 peers and consider failure probabilities ranging from O to 0.01. For Moshpit Averaging and random group averaging, we use groups of size 32, which corresponds to M = 32 and 2 for Algorithm
1024, p=
N 1024, 0.005
N-768, p=0.006 0.0066
Menn sorrre entrr
10
All Reduce
All Redure
All Reduce
10
Gosup
Gossip
Gosslp
PuskSum
PusiSuu
PudiSum
10
Random groups
Random groups
Random groups
to
Moslipi Averagnng
Moslgit Averaging
Mosigit Averaging
0
2
10
10
Iterations
lterations
lterations
Figure 3: Convergence of averaging algorithms in different configurations.
Figure displlas the results of experiments for several combinations of N and p; the complete results with additional grid configurations are available in Appendix !
We make several key observations:
1. When the failure rate of each peer is zero, standard All-Reduce predictably computes the average faster than all other methods. However, as soon as p reaches a value of at least 0.005, the number of retries needed for the success becomes prohibitively high.
2. Previous decentralized averaging methods, such as Gossip or PushSum, require significantly more iterations for convergence to the global average than Moshpit All-Reduce, likely due to the structure of their communication graphs.
3. As discussed in Section 3.1
when the total number of peers is equal to the grid capacity and there are no failures, Moshpit All-Reduse matches the result of regular All- All-Reduce with the number of steps equal to the number of grid dimensions (2 in this case).
4. Averaging in random groups can perform comparably to Moshpit Averaging when the number of peers is less than half of the grid capacity. The reason for this behavior is that when the workers do not fully occupy the grid, the group sizes no longer guaranteed to be equal across groups and across iterations. In the worst case, there can be groups of only one peer for certain grid coordinates, which may significantly affect the convergence. However, the grid utilization grows, Moshpit Averaging starts to outperform random group averaging. Moreover, even if we use 512 peers, arranging them in a proper 8x8x8 grid leads to faster convergence.
8

---

Alk. SGD, Lomos
Tap -alibloe acCEIaO
Mudipe SGD, hatmng
Tap valdbare
50%
homngg
Al-SCEL hamag
AD 2orteg
AD-PSCID, horog
bartog
SCP: Iusau
Moelgti homeg
Medgin Stan, humag
AD PSGD, Seiang.
AD PSCDS betcing
sGit hassug.
SCP, hetensg
09
Mosigit STI browngg
0%5
Medigt SCaD,
Time
Time (2o00s))
Figure 4: (Left, Middle) ResNet-50 top-1 validation accuracy for ImageNet as a function of training time (left) and epochs (middle). (Right) Full training objective (MLM + SOP) of ALBERT-large on BookCorpus as function of training time.
4.2 ImageNet training
Here, we evaluate the performance of Moshpit SGD in distributed training. More specifically, we train ResNet-50 [65] on the ILSVRC ( dataset, following the training protocol of [16). Trainers SGD with Nesterov momentum with a batch size of 256 and 32-bit precision regardless of the GPU i
We evaluate the following training strategies:
All-Reduce SGD (AR-SGD) traditional distributed training with all-reduce gradient averaging;
Asynchronous Decentralized Parallel SGD (AD-PSGD) - parallel SGD that runs gossip communication in cycle: each worker averages parameters with neighbors (66). Communication rounds are overlapped with computation;
Stochastic Gradient Push (SGP) more advanced algorithm with an exponential communica- tion graph and push-based based communication [5]:
Moshpit SGD similar to SGP, but with 1 round of Moshpit Averaging instead of PushSum.
We report top-1 validation accuracy function of training time in two experimental setups:
Homogeneous: 16 servers with single Tesla V100-PCIe GPU, CPU cores, and 64GB RAM.
Heterogeneous: a total of 81 GPUs (V100, 1080Ti, and P40) across 64 servers and workstations
All servers and workstations communicate over the network with 1Gb/s Ethernet inon-dedicated symmetric bandwidth). The machines are located in two data centers and one office within 300 km of one another. The communication latency is 1-6ms depending on the location. To simulate shared usage, at the beginning of each communication round we inject additional latency sampled from the exponential distribution 67 with the mean of 100ms.
For Moshpit SGD, we use a two-dimensional "grid" with 4 and 8 groups for homogeneous and heterogeneous setups respectively. For AD-PSGD, attempt to compensate for slow convergence by training for 60 more epochs without changing the learning rate schedule. Finally, we only report AR-SGD the first setup, it unsuitable for heterogeneous hardware.
The results in Figure (Left) demonstrate that the two most efficient strategies for our setting are Moshpit SGD and SGP. In the homogeneous setup. Moshpit is only slightly more efficient than SGP, likely due to higher efficiency of all-reduce. This advantage increases to over 30% for the heterogeneous setup with 64 servers. In turn, AR-SGD demonstrates the best performance per iteration, but its training time by far the longest due to network latency (1.5x of Moshpit SGD). Finally, AD-PSGD predictably shows the best throughput (time per epoch), but achieves lower accuracy even after training for 150 epochs. We report results for smaller setups in Appendix ]
4.3 Masked Language Model training
Finally, we evaluate Moshpit All-Reduce training performance the wild with preemptible cloud tasks in modern deep learning unsupervised pretraining of Transformers [68 69 70, []. We opt for the ALBERT model (71) make better use of communication-consttaii parameters due to layer-wise weight sharing.
instances. For this experiment, we perform of the most pooource-eemndingg
devices. This model has fewer trainable
4 'oor GPUs that cannot fit this into memory, we accumulate gradients over batches of 128 examples.
We provide detailed configuration in Appendix H

---

Specifically, we train ALBERT-large (18M parameters) on the BookCorpus 72 dataset, following the training setup from the original paper. We minimize the masked language modeling loss (MLM) along with the sentence order prediction loss (SOP) using the LAMB optimizer [17 with global batch size of 4096 and sequence length 512. We measure convergence in terms of full training
loss 773 74). Similarly to Section 4.2 we use two training setups:
Homogeneous: single cloud instance with 8 Tesla V100-PCIe GPUs and 56 vCPUs; Heterogeneous: total of 66 preemptible GPUs, 32 of which are cloud T4, and the remaining 34 are various devices rented on a public marketplace.
Despite the fact that the latter setup has almost 3x more raw compute its hourly rent costs less than the homogeneous setup due to relying on preemptible instances" This instance type is much cheaper than regular cloud instances, but it can interrupted at any time. As a side-effect, the participants in heterogeneous setup are also spread across 3 continents with uneven network bandwidth, ranging from 100Mb/s to 1500Mb/s per worker. These limitations make it impractical to deploy conventional all-reduce protocols. By contrast, the fully decentralized nature of Moshpit SGD allows it to operate on unreliable nodes.
In this setup, the participants accumulate gradients over multiple local batches and use DHT to track the global batch size. Once the swarm collectively accumulates gradients over 4096 training samples, it runs 2 rounds of Moshpit All-Reduce with M-8 and d-2. Unfortunately, training with simple parameter averaging does not converge, likely due to diverging LAMB statisties. To mitigate this after averaging to update the optimizer statistics.
issue, workers recover "pseudo-gradients" 776 77
Figure 4 (right) demonstrates that Moshpit SGD with fully preemptible fleet of machines trains 1.5 times faster than the traditional data-parallel setup. The final loss achieved by two training strategies is the same within the margin of error. A closer investigation reveals that this speedup is entirely explained by the reduced iteration time. An interesting observation is that the iteration time of Moshpit SGD varies between 10-22 seconds, while AR-SGD consistently spends 25s per step. This can be explained by natural variation in the preemptible fleet size: there were 30-66 active participants depending on the resouree availability.
Conclusion and future work
In this work, we propose Moshpit All-Reduce, a decentralized averaging protocol intended for distributed optimization in unstable and network-constraineed environments. It has favorable theoreti- cal properties when compared to gossip-based approaches and achieves considerable speedups in distributed training for image classification and masked language modeling.
Our approach was primarily designed for doud-based training and federated learning, as well as for distributed training on unreliable instances; future work might explore additional settings, such as collaborative training of neural networks. Another potential research direction to study the interactions of Moshpit All-Reduce with other methods that improve communication efficiency of distributed optimization, such as gradient compression. Finally, the idea of arranging All- nodes into groups can be improved to address specific issues that may arise in practice, such as the varying number of workers and their geographical distribution.
Acknowledgements
We would like to thank Anastasia Koloskova, Liudmila Prokhorenkova and Anton Osokin for helpful feedback and discussions. We are also grateful to the anonymous reviewers for their suggestions on improving the paper. Finally, we would like to thank Dmitry Afanasiev, Vladimir Aliev, Anand Jayarajan and Michael Solotky for their suggestions on the technical aspects of our study. This project was supported in part by the Canada Foundation for Innovation JELF grant, NSERC Discovery grant, AWS Machine Learning Research Award, and Facebook Faculty Research Award. The paper was also partially supported by by a grant for research centers in the field of artificial intelligence, provided by the Analytical Center for the Government of the Russian Federation in accordance with the subsidy agreement (agreement identifier 800000D730321PPM Institute of Physics and Technology dated November 1, 2021 No. 70-2021-00133 38. The computational resources for the experiments were provided by the Amazon Research Awards program and Yandex.
and the agreement with the Moscow
6 Based on official performance benchmarks 75
7 Pleasee refer to Appendix H for full experimental setups.
10

---

References
[1] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. In Pereira, C. C. Burges, L. Bottou, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 25, pages 1097-1105. Curran Associates, Inc., 2012.
[2] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei. ImageNet: A Large-Scale Hierarchical Image Database. In CVPRO9, 2009.
[3] Alexander Kolesnikov, Lucas Beyer, Xiaohua Zhai, Joan Puigcerver, Jessica Yung. S. Gelly, and N. Houlsby. Big transfer (bit): General visual representation learning. In ECCV, 2020.
[4] Chen Sun, Abhinav Shrivastava, Saurabh Singh, and Abhinav Gupta. Revisiting unreasonable effectiveness of data in deep learning era. In ICCV, 2017.
[5] Tom B Brown. Benjamin Mann, Nick Ryder, Mclanie Subbiah, Jared Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. arXiv preprint arXiv:2005. 14165, 2020.
[6] Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B. Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models, 2020.
[7] Chuan Li. Demystifying gpt-3 language model: A technical overview, 2020. https
//1 //lambdalabs cwm hwoom//lg//aae dwwystiiyiing-eeeee gpt-3".
[8] Peter Mattson, Christine Cheng, Cody Coleman, Greg Diamos, Paulius Micikevicius, David Patterson, Hanlin Tang, Gu- Wei, Peter Bailis, Victor Bittorf, David Brooks, Dehao Chen, Debojyoti Dutta, Udit Gupta, Kim Hazelwood, Andrew Hock, Xinyuan Huang, Bill Jia, Daniel Kang, David Kanter, Naveen Kumar, Jeffery Liao, Guokai Ma, Deepak Narayanan, Tayo Ogun- tebi, Gennady Pekhimenko, Lillian Pentecost, Vijay Janapa Reddi, Taylor Robie, Tom St. John, Carole-Jean Wu, Lingjie Xu, Cliff Young, and Matei Zaharia. MLPerf Training Benchmark. In Proceedings of the 3rd Conference on Machine Learning and Systems (MLSys '2), 2020. [9] Leslie G Valiant. bridging model for parallel computation. Communications of the ACM, 3338):103-111, 1990.
[10] Pitch Patarasuk and Xin Yuan. Bandwidth optimal all-reduce algorithms for clusters of workstations. J. Parallel Distrib. Comput., 69(2):117-124 February 2009.
[11] Brendan McMahan, Eider Moore, Daniel Ramage. Seth Hampson, and Blaise Aguera y Arcas. Communication--efcccent learning of deep networks from decentralized data. In Artificial Intelligence and Statistics, pages 1273-1282, 2017.
[12] V. Persico, Marchetta, A. Botta, and A. Pescape. On network throughput variability in microsoft azure cloud. In 2015 IEEE Global Communications Conference (GLOBECÓM),
pages 1-6. 2015.
[13] Valerio Persico. Pietro Marchetta, Alessio Botta, and Antonio Pescapè. Measuring network throughput in the cloud: The case of amazon ec2. Computer Networks, 93:408 422, 2015. Cloud Networking and Communications II.
[14] Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. Can decen- tralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent. In Advances in Neural Information Processing Systems, pages 5330-5340, 2017.
[15] Mahmoud Assran, Nicolas Loizou, Nicolas Ballas, and Mike Rabbat. Stochastic gradient push for distributed deep learning. In Kamalika Chaudhuri and Ruslan Salakhutdinov, edi- tors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 343-353. PMLR, 09-15 Jun 2019.
[16] Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch sgd: Training imagenet in 1 hour, 2017.
[17] Yang You, Jing Li, Sashank Reddi, Jonathan Hseu, Sanjiv Kumar, Srinadh Bhojanapalli, Xiaodan Song, James Demmel, Kurt Keutzer, and Cho-Jui Hsieh. Large batch optimization for deep learning: Training bert in 76 minutes. In International Conference on Learning Representations, 2020.
11

---

[18] Mu Li. Scaling distributed machine learning with the parameter server. In Proceedings of the 2014 International Conference on Big Data Science and Computing. BigDataSeience 14, New York, NY, USA, 2014. Association for Computing Machinery.
[19] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In 3rd International Conference on Learning Representations, ICLR 2015, 2015.
[20] Salem Alqahtani and Murat Demirbas. Performance analysis and comparison of distributed machine learning systems, 2019.
[21] Joost Verbraeken, Matthijs Wolting, Jonathan Katzy, Jeroen Kloppenburg, Tim Verbelen, and Jan Rellermeyer. A survey on distributed machine learning. ACM Comput. Surv., 53(2), March 2020.
[22] Martin Zinkevich, Markus Weimer, Lihong Li, and Alex Smola. Parallelized stochastic gradient descent. In J. Lafferty, C. Willliam,, J. Shawe-Taylor, R. Zemel, and A. Culotta, editors, Advances in Neural Information Processing Systems, volume 23, pages 2595-2603.
Curran Associates, Inc., 2010.
[23] Yujun Lin, Song Han, Huizi Mao, Yu Wang, and Bill Dally. Deep gradient compression: Reducing the communication bandwidth for distributed training. In International Conference Learning Representations, 2018.
[24] Anastasia Koloskova, Sebastian Stich, and Martin Jaggi. Decentralized stochastic optimization and gossip algorithms with compressed communication. In Kamalika Chaudhuri and Ruslan Salakhutdinov. editors. Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 3478-3487, PMLR, 09-15 Jun 2019.
[25] Jeffrey Dean, Greg Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Mark Mao, Mare' aurelio Ranzato, Andrew Senior, Paul Tucker, Ke Yang, Quoc Le, and Andrew Ng. Large scale distributed deep networks. In F. Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 25, pages 1223-1231. Curran Associates, Inc., 2012.
[26] Yimin Jiang, Yibo Zhu, Chang Lan, Bairen Yi, Yong Cui, and Chuanxiong Guo. A unified architecture for accelcrating distributed DNN training in heterogeneous gpu/cpu clusters. In 14th USENIX Symposium Operating Systems Design and Implementation (OSDI 20), pages 463-479. USENIX Association, November 2020.
[27] Hiroaki Mikami, Hisahiro Suganuma, Pongsakorn U-chupala, Yoshiki Tanaka, and Yuichi Kageyama. Massively distributed sgd: Imagenet/resnet-50 training in a flash, 2019.
[28] Mohammad Shoeybi, Mostofa Patwary, Raul Puri, Patrick LeGresley, Jared Casper, and Bryan Catanzaro. Megatron-Im: Training multi-billion parameter language models using gpu model parallelism. arXiv preprint arXiv: 1909008330, 2019.
[29] Aaron Segal, Antonio Marcedone, Benjamin Kreuter, Daniel Ramage, H. Brendan McMahan, Karn Seth, K. A. Bonawitz, Sarvar Patel, and Vladimir Ivanov. Practical secure aggregation for privacy-presering machine learning. In CCS, 2017.
[30] K. A. Bonawitz, Hubert Eichner, Wolfgang Grieskamp, Dzmitry Huba, Alex Ingerman, Vladimir Ivanov, Chloé M Kiddon, Jakub Konečný, Stefano Mazzocchi, Brendan McMahan, Timon Van Overveldt, David Petrou, Daniel Ramage, and Jason Roselander. Towards federated learning scale: System design. In SysML 2019, 2019. To appear.
[31] Micah J. Sheller, Brandon Edwards, G. Anthony Reina, Jason Martin, Sarthak Pati, Aikaterini Kotrotsou, Mikhail Milchenko, Weilin Xu, Daniel Marcus, Rivka R. Colen, and Spyridon Bakas. Federated learning in medicine: facilitating multi-institutionll collaborations without sharing patient data. Scientific Reports, 10(1): Jul 2020.
[32] Wenqi Li, Fausto Milletari, Daguang Xu, Nicola Ricke, Jonny Hancox, Wentao Zhu, Maxim- ilian Baust, Yan Cheng, Sébastien Ourselin, M. Jorge Cardoso, and Andrew Feng. Privacy- Preserving Federated Brain Tumour Segmentation, pages 133.141. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioin- formatics). SPRINGER, January 2019. 10th International Workshop on Machine Learning in Medical Imaging, MLMI 2019 held in conjunction with the 22nd International Conference on Medical Image Computing and Computer-Assine Intervention, MICCAI 2019: Conference date: 13-10- 10-299 Through 13-10-2019.
12

---

[33] Andrew Hard. Chloé M Kiddon, Daniel Ramage, Francoise Beaufays, Hubert Eichner, Kan- ishka Rao, Rajiv Mathews, and Sean Augenstein. Federated learning for mobile keyboard prediction, 2018.
[34] Timothy Yang. Galen Andrew, Hubert Eichner, Haicheng Sun, Wei Li, Nicholas Kong, Daniel Ramage, and Françoise Beaufays. Applied federated learning: Improving google keyboard query suggestions, 2018.
[35] Ekasit Kijsipongse, Apivadee Piyatumrong, and Suriya U-ruckolan. A hybrid gpu cluster and volunteer computing platform for scalable deep learning. The Journal of Supercomputing, 04 2018.
[36] Max Ryabinin and Anton Gusev. Towards crowdsourced training of large neural networks using decentralized ofxture-of-experts. Advances Neural Information Processing Systems, 2020.
[37] Aaron Harlap, Alexey Tumanov, Andrew Chung, Gregory R. Ganger, and Phillip B. Gibbons. Proteus: Agile ml elasticity through tiered reliability in dynamic resource markets. In Proceed- ings of the Twelfth European Conference on Computer Systems, EuroSys 17, page 589-604, New York, NY, USA, 2017. Association for Computing Machinery.
[38] Stephen Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavrat Shah. Randomized gossip algorithms. IEEE transactions on information theory, 52(6):2508-2533 2006.
[39] John Nikolas Tsitsiklis. Problems in decentralized decision making and computation. Technical report, Massachusetts Inst of Tech Cambridge Lab for Information and Decision Systems, 1984.
[40] Kevin Scaman, Francis Bach, Sébastien Bubeck, Yin Tat Lee, and Laurent Massoulié. Op- timal algorithms for smooth and strongly convex distributed optimization in networks. In International Conference on Machine Leurning, pages 3027-3036, 2017.
[41] Kevin Scaman, Francis Bach, Sébastien Bubeck, Laurent Massoulié, and Yin Tat Lee. Optimal algorithms for non-smooth distributed optimization in networks. In Advances in Neural Information Processing Systems, pages 2740-2749, 2018.
[42] Kevin Scaman, Francis Bach, Sébastien Bubeck, Yin Lee, and Laurent Massoulié, Optimal convergence rates for convex distributed optimization in networks. Journal of Machine Learning Research, 20:1-31, 2019.
[43] Mahmoud Assran, Nicolas Loizou, Nicolas Ballas, and Mike Rabbat, Stochastic gradient push for distributed deep learning. In International Conference on Machine Learning, pages 344-353. PMLR, 2019.
[44] Lin Xiao and Stephen Boyd. Fast linear iterations for distributed averaging. Systems & Control Letters, 53(1):65-75 2004.
[45] Russell Merris. Laplacian matrices of graphs: survey. Linear algebra and its applications, 197:143-176, 1994.
[46] César A Uribe, Soomin Lee, Alexander Gasnikov, and Angelia Nedić. A dual approach for optimal algorithms in distributed optimization over networks. Optimization Methods and Software, pages 1-40, 2020.
[47] Angelia Nedić and Alex Olshevsky. Distributed optimization over time-varying directed graphs. IEEE Transactions on Automatic Control, 60(3):601-615 2014.
[48] Angelia Nedić and Alex Olshevsky. Stochastic gradient-push for strongly convex functions on time-varying directed graphs. IEEE Transactions on Automatic Control, 61((2))3936-3947, 2016.
[49] Angelia Nedié, Alex Olshevsky, and Michael G Rabbat. Network topology and communication- computation tradeoffs in decentralized optimization. Proceedings of the IEEE, 106(5):953-976. 2018.
[50] Alexander Rogozin and Alexander Gasnikov. Projected gradient method for decentralized optimization over time-varying networks. arXiv preprint arXiv:1911.08527, 2019.
[51] S Sundhar Ram, A Nedié, and Venugopal Veeravalli. Asynchronous gossip algorithms for stochastic optimization. In Proceedings of the 48h IEEE Conference Decision and Control (CDC) held jointly with 2009 28th Chinese Control Conference, pages 3581-3586. IEEE, 2009.
13

---

[52] Feng Yan, Shreyas Sundaram, SVN Vishwanathan, and Yuan Qi. Distributed autonomous online learning: Regrets and intrinsic preserring properties. IEEE Transactions on Knowledge and Data Engineering, 25(11):2483-245) 2012.
[53]
Kun Yuan, Qing Ling, and Wotao Yin. On the convergence of decentralized gradient descent. SIAM Journal on Optimization, 26(3): 835-1854, 2016.
[54] Paul Sack and William Gropp. Collective algorithms for multiported torus networks. ACM Trans. Parallel Comput., 1(2), February 2015.
[55] Petar Maymounkov and David Mazieres. Kademlia: A peer-to-pest peer information system based on the xor metric. In International Workshop on Peer-to- Systems, pages 53-65. Springer, 2002.
[56] Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochas- tic approximation approach to stochastic programming. SIAM Journal on optimization. 19(4):1574-1609, 2009.
[57] Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341-2368, 2013.
[58] Robert Mansel Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, and Peter Richtárik. Sgd: General analysis and improved rates. In International Conference Machine Learning, pages 5200-5209. PMLR, 2019.
[59] Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference on Machine Learning, pages 5132-5143. PMLR, 2020.
[60] Eduard Gorbunov, Filip Hanzely, and Peter Richtarik. Local sgd: Unified theory and new efficient methods. In Arindam Banerjee and Kenji Fukumizu, editors, Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 3556-3564. PMLR, 13-15 Apr 2021.
[61] Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter theory for local sgd on identical and heterogeneous data. In International Conference on Artificial Intelligence and Statistics, pages 4519-4529, PMLR, 2020.
[62] Blake Woodworth, Kumar Kshitij Patel, Sebastian Stich, Zhen Dai, Brian Bullins, Brendan Mcmahan, Ohad Shamir, and Nathan Srebro. Is local sgd better than minibatch sgd? In International Conference on Machine Learning, pages 10334-10343. PMLR, 2020.
[63] Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian Stich. A unified theory of decentralized sgd with changing topology and local updates. In International Conference on Machine Learning, pages 5381-5393. PMLR, 2020.
[64] Xiang Li, Wenhao Yang. Shusen Wang, and Zhihua Zhang. Communication efficient decen- tralized training with multiple local updates. arXiv preprint arXiv: 09166, 5, 2019.
[65] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 770-778, 2015.
[66] Xiangru Lian, Wei Zhang, Ce Zhang, and Ji Liu. Asynchronous decentralized parallel stochastic gradient descent. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 3043-3052. PMLR, 10-15 Jul 2018
[67] Andrei M Sukhov, MA Astrakhantseva, AK Pervitsky, SS Boldyrev, and AA Bukatov. Gener- ating a function for network delay. Journal of High Speed Networks, 22(4):321-3333 2016.
[68] Jacob Devlin, Ming-Woi Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. NAACL-HILT, 2019.
[69] Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized bert pretraining approach. ArXiv, abs/1907.1 1692, 2019.
[70] Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Lan- guage models are unsupervised multitask learners. 2019.
14

---

[71] Zhen-Zhone Lan, Mingda Chen, Sebastian Goodman, Kevin Gimpel, Piyush Sharma, and Radu Soricut. Albert: A lite bert for self-supervised learning of language representations. In International Conference on Learning Representations, 2020.
[72] Yukun Zhu, Ryan Kiros, Rich Zemel, Ruslan Salakhutdinov, Raquel Urtasun, Antonio Torralba, and Sanja Fidler. Aligning books and movies: Towards story-like visual explanations by watching movies and reading books. In Proceedings of the IEEE international conference on computer vision, pages 19-27. 2015.
[73] Jiahuang Lin, Xin Li, and Gennady Pekhimenko. Multi-node bert-pretraining: Cost-efficient approach, 2020.
[74] William Fedus, Barret Zoph, and Noam Shazeer. Switch transformers: Scaling to trillion parameter models with simple and efficient sparsity, 2021.
[75] NVIDIA. Nvidia data center deep learning product performance. https:// developer wwwiiiiii........
-il.niinnniifeeeeeeee ac-
cessed at 202 2021.02.03.
[76] Sashank J. Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and Hugh Brendan McMahan. Adaptive federated optimization. In International Conference on Learning Representationss 2021.
[77] Xiangyi Chen, Xiaoyun Li, and Ping Li. Toward communication efficient adaptive gradient method. In Proceedings of the 2020 ACM-IMS on Foundations of Data Science Conference, FODS '20, page 128, New York, NY, USA, 2020. Association for Computing Machinery.
[78] Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang. Squad: 100, 000+ questions for machine comprehension of text. In EMNLP, 2016.
[79] David Aldous and James Allen Fill. Reversible markov chains and random walks on graphs, 2002. unfinished monograph, recompiled 2014, 2002.
[80] Jinming Xu, Ye Tian, Ying Sun, and Gesualdo Scutari. Distributed algorithms for composite optimization: Unified and tight convergence analysis. arXiv preprint 2Xiv:2002.//5344 2020.
[81] Alireza Fallah, Mert Gurbuzbalaban, Asu Ozdaglar, Umut Simsekli, and Lingjiong Zhu. Robust distributed accelerated stochastic gradient methods for multi-agent networks. arXiv preprint 1911v:1910.08701, 2019.
[82] Dmitry Kovalev, Adil Salim, and Peter Richtárik. Optimal and practical algorithms for smooth and strongly convex decentralized optimization. Advances in Neural Information Processing Systems, 33, 2020.
[83] Yossi Arjevani and Ohad Shamir. Communication complexity of distributed convex learning and optimization. Advances in neural information processing systems, 28: 28:1756-1764 2015.
[84] Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and its application to data-parallel distributed training of speech dnns. In Fifteenth Annual Conference of the International Speech Communication Association, 2014.
[85] Dan Alistarh, Demjan Grubic, Jerry Z Li, Ryota Tomioka, and Milan Vojnovic. Qsgd: Communication-effiiiee sgd via gradient quantization and encoding. In Proceedings of the st International Conference on Neural Information Processing Systems, pages 1707-1718. 2017.
[86] Ananda Theertha Suresh, X Yu Felix, Sanjiv Kumar, and H Brendan McMahan. Distributed mean estimation with limited communication. In International Conference on Machine Learning, pages 3329-3337. PMLR, 2017.
[87] Ali Ramezani-Kebrya, Fartash Faghri, Ilya Markov, Vitalii Aksenov, Dan Alistarh, and Daniel M Roy. Nuqsgd: Provably communication-efficicee data-parallel sgd via nonuni- form quantization. Journal of Machine Learning Research, 22 221114): 2021.
[88] Fartash Faghri, Iman Tabrizian, Ilia Markov, Dan Alistarh, Daniel M Roy, and Ali Ramezani- Kebrya. Adaptive gradient quantization for data natal-l sgd. Advances in Neural Information Processing Systems, 33:3174 03:3174-3185,, 2020.
[89] Samuel Horvath, Chen- Yu Ho, Ludovit Horvath, Atal Narayan Sahu, Marco Canini, and Peter Richtarik. Natural compression for distributed deep learning. arXiv preprint arXiv: arXiv::905 1905. 10988, 2019.
15

---

[90] Aleksandr Beznosikov, Samuel Horváth. Peter Richtárik, and Mher Safaryan. On biased compression for distributed learning, arXiv preprint arXiv:2002. 1241100002.24100,, 2020.
[91] Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Temgrad: ternary gradients to reduce communication in distributed deep learning. In Proceedings of the s1 International Conference on Neural Information Processing Systems, pages 1508-1518, 2017.
[92] Konstantin Mishchenko, Eduard Gorbunov, Martin Takáč, and Peter Richtárik. Distributed learning with compressed gradient differences. arXiv preprint arXiv:1901.09200 2019.
[93] Samuel Horváth, Dmitry Kovalev, Konstantin Mishchenko, Sebastian Stich, and Peter Richtárik. Stochastic distributed learning with gradient quantization and variance reduction. arXiv preprint arXiv:1904.05115, 2019.
[94] Zhize Li, Dmitry Kovalev, Xun Qian, and Peter Richtarik. Acceleration for compressed gradient descent in distributed and federated optimization. In International Conference on Machine Learning, pages 5895-5904. PMLR, 2020.
[95] Eduard Gorbunov, Dmitry Kovalev, Dmitry Makarenko, and Peter Richtarik. Linearly converg- ing error compensated sgd. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 20889-20900. Curran Associates, Inc., 2020.
[96] Constantin Philippenko and Aymeric Dieuleveut. Artemis: tight convergence guarantees for bidirectional compression in federated learning. arXiv preprint arXiv:2006. /4591, 2020.
[97] Zhize Li and Peter Richtárik. A unified analysis of stochastic gradient methods for nonconvex federated optimization. arXiv preprint arXiv:2006.0700
2020.
[98] Farzin Haddadpour, Mohammad Mahdi Kamani, Aryan Mokhtari, and Mehrdad Mahdavi. Federated learning with compression: Unified analysis and sharp guarantees. arXiv preprint vrXiv:2007.0115:: 2020.
[99] Rudrajit Das, Abolfazl Hashemi, Sujay Sanghavi, and Inderjit S Dhillon. Improved convergence rates for non-convex federated learning with compression. arXiv preprint arXiv:20/2.04061, 2020.
[100] Eduard Gorbunov, Konstantin P. Burlachenko, Zhize Li, and Peter Richtarik. Marina: Faster non-convex distributed learning with compression. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 3788-3798. PMLR, 18-24 Jul 2021.
[101] Sebastian U Stich, Jean- -aan-Baptiste Cordonnier, and Martin Jaggi. Sparsified sgd with memory. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 4452-4463, 2018
[102] Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi. Error feedback fixes signsgd and other gradient compression schemes. In International Conference on Machine Learning, pages 3252-3261. PMLR, 2019.
[103] Xun Qian, Peter Richtárik, and Tong Zhang. Error compensated distributed sgd can be accelerated. arXiv preprint arXi::2010.0009 2020.
[104] Amirhossein Reisizadeh, Aryan Mokhtari, Hamed Hassani, and Ramtin Pedarsani. An exact quantized decentralized gradient descent algorithm. IEEE Transactions on Signal Processing. 67(19):9934-4MM 49477 2019.
[105] Dmitry Kovalev, Anastasia Koloskova, Martin Jaggi, Peter Richtarik, and Sebastian Stich. A linearly convergent algorithm for decentralized optimization: Sending less bits for free! In Arindam Banerjee and Kenji Fukumizu, editors, Proceedings of The 24th International Conference Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 4087-4095. PMLR, 13-15 Apr 2021.
[106] Anastasia Koloskova, Tao Lin, Sebastian U Stich, and Martin Jaggi. Decentralized deep learning with arbitrary communication compression. In International Conference on Learning Representations, 2020.
[107] Jakub Konečný, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint 1rXiv:1610005492, 2016.
16

---

[108] Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Ar- jun Nitin Bhagoji, Keith Bonawitz. Zachary Charles, Graham Cormode, Rachel Cummings. et al. Advances and open problems in federated learning. arXiv preprint arXiv: 1912.04977, 2019.
[109] Sebastian Urban Stich. Local SGD converges fast and communicates little. International Conference on Learning Representations (ICLR), page arXiv: 805.09667 2019.
[110] Tao Lin, Sebastian Urban Stich, Kumar Kshitij Patel, and Martin Jaggi. Don't use large mini-batches, use local SGD. ICLR, page arXiv: 18KK. 1808100.00000 0708007 2020.
[111] Blake Woodworth, Kumar Kshitij Patel, and Nathan Srebro. Minibatch vs local sgd for heterogencous distributed learning. arXiv preprint wrXiv:2006.04735, 2020.
[112] Honglin Yuan and Tengyu Ma. Federated accelerated stochastic gradient descent. Advances in
Neural Information Processing Systems, 33, 2020.
[113] Debraj Basu, Deepesh Data, Can Karakus. and Suhas Diggavi. Qsparse-local-SGD. Dis- tributed SGD with quantization, sparsification and local computations. In Advances in Neural Information Processing Systems, pages 1 14668-14679, 2019.
[114] Honglin Yuan, Manzil Zaheer, and Sashank Reddi. Federated composite optimization. arXiv preprint arXiv:201 1.02241111.444, 2020.
[115] Mahmoud Assran, Arda Aytekin, Hamid Reza Feyzmahdavian, Mikael Johansson, and Michael G Rabbat. Advances in asynchronous parallel and distributed optimization. Proceed- ings of the IEEE, 108(11):2013-203 2020.
[116] Benjamin Recht, Christopher Re, Stephen Wright, and Feng Niu. Hogwild: A lock-free approach to parallelizing stochastic gradient descent. In Advances in neural information processing systems, pages 693-701, 2011.
[117] Shen-Yi Zhao and Wu-Jun Li. Fast asynchronous parallel stochastic gradient descent: A lock-free approach with convergence guarantee. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.
[118] Rémi Leblond, Fabian Pedregosa, and Simon Lacoste-Julien. Asaga: asynchronous parallel saga. In Artificial Intelligence and Statistics, pages 46-54. PMLR, 2017.
[119] Zhimin Peng. Yangyang Xu, Ming Yan, and Wotao Yin. Arock: an algorithmic frame- work for asynchronous parallel coordinate updates. SIAM Journal on Scientific Computing, 3865):22811-A287, 2016.
[120] Konstantin Mishchenko, Franck Iutzeler, Jérôme Malick, and Massih- Amini, A delay- tolerant groximal-gradien algorithm for distributed learning. In International Conference on Machine Learning, pages 3587-3595. PMLR, 2018.
[121] Alekh Agarwal and John C Duchi. Distributed delayed stochastic optimization. In Proceedings of the 24th International Conference on Neural Information Processing Systems, pages 873-
881, 2011.
[122] Hamid Reza Feyzmahdavian, Arda Aytekin, and Mikael Johansson. An asynchronous mini- batch algorithm for regularized stochastic optimization. IEEE Transactions on Automatic Control, 61(11))3740-3755 2016.
[123] Yossi Arjevani, Ohad Shamir, and Nathan Srebro. A tight convergence analysis for stochastic gradient descent with delayed updates. In Algorithmic Learning Theory, pages 111-132.
PMLR, 2020.
[124] Hari Balakrishnan, M Frans Kaashoek, David Karger, Robert Morris, and Ion Stoica. Looking up data in p2p systems. Communications of the ACM, 46(2):43-48, 2003.
[125] Seymour Kaplan. Application of programs with maximin objective functions to problems of optimal resource allocation. Operations Research, 22 807 1974.
[126] Erling D. Andersen and Knud D. Andersen. The mosek interior point optimizer for linear programming: An implementation of the homogeneous algorithm. In Applied Optimization,
pages 197-232. Springer US, 2000.
[127] Anand Jayarajan, Jinliang Wei, Garth Gibson, Alexandra Fedorova, and Gennady Pekhimenko. Priority-base parameter propagation for distributed dnn training. In A. Talwalkar, V. Smith, and M. Zaharia, editors, Proceedings of Machine Learning and Systems, volume 1, pages
132 145, 2019.
17


Reviews:
[{"review_id": "sJeKgyYKMMa", "reviewer": "Reviewer_S2Ah", "summary": "This paper presents a new collective algorithm and associated implementation of SGD training that is optimized for distributed systems where some ranks will not participate in each training step.  The observation is that parameter servers are not scalable, and that most collective based (all-reduce) distributed algorithms are either not fault tolerant, or have significant performance impacts when there is load imbalance or system noise.  The proposed Moshpit all-reduce and SGD strive to overcome these challenges by breaking down the collective communication domains into many more \"sub-domains\" that can tolerate delays or absences of its participants.  However, it does so in a structured manner that is more communication efficient than a standard gossip, random, algorithm.  They show that despite stale gradients for each participant, the algorithm still converges and does so faster than SOTA algorithms.", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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": "Overall, the paper presents a clear and compelling description of the proposed algorithm.  Both the pseudo-code and block diagrams did a good job of conveying the algorithms details.  Evaluations were performed on both a standard visual network as well as a transformer based language model.  The paper also provides a detailed description of the convergence properties of the algorithm, which are empirically supported by the results shown in Figure 4.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "rBaVfhzKpGD", "reviewer": "Reviewer_XkgK", "summary": "The paper introduces a decentralized averaging scheme and uses it for distributed learning.\nThe averaging scheme falls somewhere in between typical gossip averaging and uniform all-reduce averaging.\nIt inherits some of the robustness to node failures from typical gossip averaging and some of the communication efficiency from all-reduce collectives.\n\nFor each communication step, nodes are divided into groups using a decentralized hash table, and perform all-reduce averaging within their group. If a node in one group fails or takes too long to respond, other communication groups can still complete their averaging reliably. \nIn the light of prior work, this method could be classified as a linear time-varying averaging scheme, with block-uniform averaging matrices.\n\nWhat I personally consider the most interesting contribution of the paper, is the match-making mechanism used to group the workers. By numbering the nodes in each group at timestep $t$, and using those numbers to group the nodes in the next round, workers are never grouped with the same peers in two consecutive communication rounds. I believe this is what gives the algorithm its name 'MoshPit' (although an explanation of this is missing from the paper).\n\nThe paper contains convergence rates for the algorithm with random grouping (not with moshpit match-making), and experiments show that the algorithm can reduce training time and cost, mainly in heterogeneous environments (bandwidth or compute capabilities).", "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": "I have enjoyed reading this paper, and I particularly found the moshpit match-making scheme clever and interesting.\nThe quality of the writing is good and the exposition is clear. \nWhile I have some hesitations regarding the experiments and focus of the paper (see below), I believe efficient decentralized averaging schemes can have great significance for peer-to-peer and large-scale training.\n\nWhile I think the match-making scheme described at the start of Section 3.1 is the most interesting contribution of this work (and gives the name to the proposed algorithm), I feel that this particular contribution does not receive the attention it deserves. The theory does not consider moshpit (repelling) grouping, and in the experiments, a many questions are unanswered:\n\n- (1) How much does moshpit matchmaking help over random grouping?\n- (2) Reliability to workers leaving and joining is presented as a benefit of this method. Will the group sizes remain balanced across iterations and groups if this happens? Is there a mechanism to achieve this?\n- (3) The comment \"wait for peers to assemble\" in Algorithm 1 hides some non-trivial details. How do the workers synchronize and know their group is 'complete'? Do they use time-outs? How are those time-outs set and what is their impact on the performance of this method?\n\nI also have some hesitations regarding the experimental setup:\n- (4) While the experiments convincingly show that there are settings in which this method works well, the setup seems a little artificial (with additional randomized latency). This is fine, but I believe experiments that test individual aspects of the model could be more valuable (suggestions below)\n- (5) For a group size of 2, the proposed method recovers something very much like the time-varying (torus) topology in Stochastic Gradient Push [15, 54]. For a group size of n, the method becomes all-reduce. I would like to see the impact of the choice of group size on the resilience to failures and communication efficiency. How should this be set in practice? Is there ever a benefit of using groups of size > 2 or smaller than $n$?\n- (6) The benefits in the heterogeneous case seem to come mainly from the load balancing details in Appendix E. Other baselines such as all-reduce would benefit from the same mechanism. I believe it would be better if the authors could separate this contribution from their proposed averaging scheme.\n\nWhile the theory in this paper is correct and relevant, it does considers a simplified algorithm (with random grouping) that does not include the match-making scheme I find most interesting about this paper.\nIt also seems that rates for this algorithm follow quite readily from prior work (e.g. Koloskova et al. [63]), by considering this method as time-varying linear gossip averaging with block-uniform matrices. Lines 248 and 249 compare the obtained rate to this paper. Could you please clarify the differences in the analysis?\n\nI would consider increasing my score if the authors can address most of the questions (1 - 6). Below, I include a few minor questions and comments.\n\n- The paper often claims that the method \"does not depend on the spectral properties of the graph\". I think this is misleading because the method requires a fully connected topology, and competing methods don't have such a dependence either in this case.\n- Theorem 3.1 shows that a simplification of Moshpit Averaging (with random groups) converges linearly, even with communication failures. The same seems true for retrying all-reduce. Would it be possible to characterize the gains in reliability?\n- For the claim about linear convergence in 131, I think you should list the key assumptions.\n- I am missing some training details such as learning rates, schedules, warmup, and whether typical optimizations are used, such as overlapping computation and communication in the backward pass (see PyTorch's DistributedDataParallel).\n- The paper mentions that all-to-all implementations of all-reduce are not always practical. While I can imagine this is because many messages are sent, I do not quite understand why this is problematic? Could you please elaborate a bit on this?\n- Section 2.4 has some incorrect use of articles. Check [a] PS and \"the changes\".\n\n__Edit:__ I have read the other reviews and the author's response. The authors have included significant new analysis. If the authors include this analysis in the paper, and commit to giving the proposed matchmaking procedure more attention in the mansucript, I would be fine with acceptance. I'll change my score from 5 to 6.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I do not see any societal impact or limitations that warrant discussion.", "review_text": "", "extra_scores": {"ethical_concerns": "I do not have any ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "UrZqa-MujDr", "reviewer": "Reviewer_5vXz", "summary": "Data parallel distributed NN training often depends on homogenous, well-provisioned networks and reliable end hosts.  This paper presents a scheme, Moshpit All-Reduce, that leverages a hybrid approach to communicating parameters (gradients) that combines elements of gossip with all-reduce to better withstand heterogeneous network environments and node failures.  The authors present their technique, and integrate it into a distributed SGD scheme (Moshpit SGD).  Microbenchmarks validate the extensive theoretical exploration of MAR, and the authors compare/contrast the system's effectiveness on both well-connected and distributed/heterogenous infrastructure.  They find that the scheme can tolerate varying network latencies and often more quickly converges by shortening training during individual epochs.   ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "++ Robust training on cheap(er) nodes/networks is an important challenge. \n\n++ Paper provides a novel communication algorithm for efficiently performing an all-reduce average.  Extensive analysis provides support for its convergence and robustness properties.\n\n++ Experiments on homogenous and heterogenous networks with varying network latencies illustrate its ability to quickly approximate the true average and support distributed SGD. \n\n++ The writing was clear and the notation consistent. \n\n-- Given the complexity of the theoretical analysis, the empirical validation of Moshpit All-Reduce was notably weak.  \n\n-- There was a lack of description of the competing techniques (related work) beyond all-reduce.  (S4.2).\n\n-- While the end-to-end training experiments are compelling, the experiment construction makes comparisons (and lessons learned) difficult.  \n\nOverall this appears to be an important problem and the novel communication protocol is well motivated.  Most of my concerns about the work lie within the empirical evaluation.   A key contribution here is MAR, but the simplistic, limited evaluation does the work a disservice.  While theoretical results (assuming the proofs are correct) are necessary, they may not always account for reality.   A key question (and contribution) then, would be to determine under what network conditions (latency, disconnections) and failure rates will Moshpit AR (and by association MSGD) succeed or fail?  Ultimately this feels like solid, important work, but it isn't sufficiently evaluated in the current work. \n\nBefore enumerating the kinds of experiments, there were a few places where the technical details were not clear. \n* In Algorithm 1, it would be useful to characterize the asynchrony.   For example, there is a wait for peers to assemble.  Essentially, this is view maintenance/consensus.   If a node \"joins late\" what occurs?   They must be kicked out of the all-reduce.   If a there is agreement on the peer set, and then peers experience failure, what is the impact on the latency of the round (internal all-reduce timeouts), what is the impact of that timeout on convergence?  Is it possible for certain network or failure conditions to allow butterfly all-reduce to end in an inconsistent state?\n* It would then seem to make sense to report the number of nodes that fail to participate in a round, as well as the distribution of round length (and variance of the aggregate). Theorem 3.2 maintains that the sum of all the groups is still N.  While the theorem explores an important relaxation of the initial assumptions, node failure/disconnections imply that rounds may proceed that violate that assumption. \n\nTo establish these properties the microbenchmarks should a.) plot the theoretical and competing systems (S4.2) results with the empirical results, b.) should change one aspect at a time (as opposed to changing N and p simultaneously), and c.) report performance statistics as a function of increasing node failure and (separately) connection latency.   Again, the point is to establish the claimed properties of MAR: faster (fewer rounds) and more efficient (less communication) convergence during failures and network performance.   \n\nSection 4.1 doesn't clearly state M or d (leaving the reader to parse \"32x32\" 'grid').   I'm assuming \"18 steps\" is T=18.  When failed peers return, do they return with the last returned parameters?   More importantly, failing for individual rounds seems contrived.   What about failing for some unspecified period of time (modeled with some distribution)?  In reality, peers aren't going to fail on nicely behaved round boundaries.  Also, I don't understand line 268.  Why does this experiment converge in two steps with failures?  Two steps are the minimum to achieve an exact answer without failure.   Were there no failures?    On that same graph, why would N=900 with no failures take so many steps (9) to converge to the true answer?   Clearly, even without failures, the true size of the groups must be << than 32.     \n\nA good section of the paper is taken up by showing that Moshpit AR can be used for distributed training (Moshpit SGD).   It isn't clear how many rejected distributed communications protocols have been the cause of SGD failures -- even the establishing of such theoretical bounds doesn't prevent MSGD from failing to converge during training in some situations (Section 4.3).   \n\n- Moshpit All-Reduce also takes into consideration network bandwidth.   Was this used in all experiments?  How was the bandwidth measured?   How often / was it stable?  How big an improvement did this provide and would it apply to other systems as well? \n- S4.2 says that additional latency is added per communication round.  Is this added per host link or is it added per communicating pair (emulating latency at the end host or in the middle of the network)?  Is this delay left on for the duration of the communication round?  \n- S4.2: The paper says AR-SGD is \"unsuitable for heterogenous hardware.\"  It would be better to provide data to support this statement, i.e., how bad is it? \n- S4.2:  The paper compares against a gossip approach that communicates with 2 neighbors.  This setting appears unmotivated and rather small.   What happens if it is set in a similar fashion to the different group sizes for MSGD (4 and 8 groups)?\n- S4.2 mentions \"efficiency\" but it's unclear what this represents.  Latency of each communication round? Number of messages? Number of bytes on the network? \n- While Figure 4 is interesting (though very small), it would also be enlightening to plot summary statistics for accuracy and latency of averaging per epoch, per mechanism.  In some ways, these are the metrics the paper discusses, but we are forced to deduce them from these end products (though the results should be directly available).     \n* In S4.2, you say Moshpit SGD has \"1 round of Moshpit averaging.\"  How does this relate to Algorithm 2?  \n\n* The heterogenous network is unspecified.  How many nodes were at each site?  \n* During actual model training it wasn't clear if there were node failures.\n* What is the distribution of M_k in these heterogenous situations?  How often are there incomplete groups? \n\nLike adjusting partition size based on bandwidth, one could also explore building the groups based on network coordinates (rack, container, data center, etc., locality). \n\n__Edit [comments on author's response] :__  First, thank you for taking the time to help explain your work to the reviewers and provide additional supporting evidence for the work.  If the author's revise their work by adding the missing clarity noted by the reviewers (e.g., implications of group/grid size, how to choose group size), and incorporate the new analysis (as they suggest they will do), it will significantly enhance the paper.   I would also love to see an improved discussion of the impact of incomplete groups and failures based on the additional detail you provided.   In light of the author's commitment to improving clarity in the technical and experimental parts of the work, I will improve my score.     \n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"ethical_concerns": "none", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6-8"}, "extra_text": {}}, {"review_id": "NE1AB6VqhB_", "reviewer": "Reviewer_LKRP", "summary": "This paper introduces Moshpit All-Reduce, a fully decentralized iterative averaging protocol for large-scale training under unstable communication conditions and/or with unreliable workers. The proposed protocol allows an exponential convergence to the global average. It is shown that Moshpit SGD, built on top of Moshpit All-Reduce, is equivalent to the centralized SGD in terms of iteration complexity.", "questions": "", "limitations": "", "rating": 7, "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 and Significance: This paper considers distributed learning over unreliable worker and communication channel. The topic is of significance in that the proposed method resolves the issues in the existing gossip based algorithms lifting the fundamental restriction and tradeoff between the communication required and convergence rate. \n\n* Technical quality: The technical contribution/quality of this paper overall looks good to me (didn't fully check the proof though). My only concern is that some part in the experiment section is not very clear to me. Please refer to the questions at the end of the comment (Miscellaneous). \n\n* Clarity in organization/writing: \n\n-- The organization and writing are mostly clear to me. I especially like the organization of the introduction and related work sections. I believe that It would be helpful for readers who just jumped into this area as it is easy to read and contains a fairly good list of references.\n\n-- Miscellaneous\n1) line 49: Can we quantitatively measure the additional burden for dynamically organizing workers? Do we need intervention of a moderator or any kind of centralized operation to do this? \n2) line 253: It is not clear what \"all information is replicated\" means. Please elaborate more.\n3) line 264: It seems that the authors use the gaussian noise to model errors added to the values of the original vectors. Please consider modifying this sentence to contain the full detail.\n4) Figure 3: Can we think of any tradeoffs from this figure? It was surprising that there is a fairly large gap in the behavior between the red and brown lines given the same p and a small difference in N. It would be better if the readers could get some more intuition behind the results shown in this figure.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "They addressed the limitations in Appendix. I agree with the authors that it is hard to assess potential negative societal impact of this work/application.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a novel approach to distributed data-parallel training, MoshpitSGD. The approach targets systems where fault tolerance and robustness important, e.g., when some worker nodes may fail, there is load imbalance, or other sources of heterogeneity in the system. This is a setting relevant to practitioners applying distributed training.

The reviewers agreed that the contribution is interesting and worthy of acceptance. While there were some questions and concerns raised in the initial reviews, the authors’s responses largely addressed these. In particular, the new empirical results nicely illustrate the tradeoff between messaging rounds and resilience to node failures. It is important that the camera-ready revision should include the points mentioned during the rebuttal to address questions raised by the reviewers to improve the clarity of the paper, especially around experimental setup and findings. We also strongly encourage the authors to include the additional experiments in the paper and make the experiments more focused on specific contributions (e.g., the proposed match-making scheme) in addition to highlighting performance of the method as a whole. This will likely involving moving/adding material to the supplementary material.

Decision: Accept (Poster)