Asynchronous Decentralized SGD with Quantized and Local Updates
Authors: Giorgi Nadiradze
Amirmojtaba Sabour
Peter Davies
Shigang Li
Dan Alistarh
Venue: NeurIPS 2021 Poster (2021)
Keywords: distributed optimization
quantization
asynchrony
decentralized optimization
non-blocking algorithms

Abstract: Decentralized optimization is emerging as a viable alternative for scalable distributed machine learning, 
but also introduces new challenges in terms of synchronization costs.  
To this end, several communication-reduction techniques, such as non-blocking communication, quantization, and local steps, 
have been explored in the decentralized setting. 
Due to the complexity of analyzing optimization in such a relaxed setting, 
this line of work often assumes \emph{global} communication rounds, which require additional synchronization. 
In this paper, we consider decentralized optimization in the simpler, but harder to analyze, \emph{asynchronous gossip} model, 
in which communication occurs in discrete, randomly chosen pairings among nodes. 
Perhaps surprisingly, we show that a variant of SGD called \emph{SwarmSGD} still converges in this setting, 
even if \emph{non-blocking communication}, \emph{quantization}, and \emph{local steps} are all applied \emph{in conjunction}, and even if the node data distributions and underlying graph topology are both \emph{heterogenous}. 
Our analysis is based on a new connection with multi-dimensional load-balancing processes. 
We implement this algorithm and deploy it in a super-computing environment, showing that it can outperform previous decentralized methods in terms of end-to-end training time, and that it can even rival carefully-tuned large-batch SGD for certain tasks. 

Asynchronous Decentralized SGD with Quantized and Local Updates
Giorgi Nadiradze IST Austria
Amirmojtaba Sabour IST Austria amsabour79@gaail.c com
Peter Davies University of Surrey
glorgi.nadiradzettin ac
pd00348aurrey. ac uk
Shigang Li ETH Zurich shigangli.. wttp:lii..smmmmm..oommmmmm
Dan Alistarh
IST Austria & Neural Magic dan. alistarh@ist.c ac.
Abstract
Decentralized optimization emerging as a viable alternative for scalable dis- tributed machine learning, but also introduces challenges in terms of synchro- nization costs. To this end, several communication-reducee non-blocking communication. quantization, and local steps, have been explored in the decentralized setting. Due to the complexity analyzing optimization in such a relaxed setting, this line of work often assumes global communication rounds, this paper, we consider decentralized optimization in the simpler, but harder to analyze, asynchromous gossip model, in which communication occurs discrete, randomly chosen pairings among nodes. Perhaps surprisingly, we show that variant of SGD called SwarmSGD still con- verges in this setting, even if non-blocking communication, quantization, and local steps are all applied in conjunction, and even if the node data distributions and un- derlying graph topology are both heterogenous. Our analysis is based on new connection with muutiidiimensionll load- boad-balancing processes. We implement this algorithm and deploy it in super-computing environment, showing that outperform previous decentralized methods in terms of end-to-end training time, and that it can even rival carefully-tuned large-batch SGD for certain tasks.
techniques, such as
which require additional synchronization.
Introduction
Decentralized optimization has recently emerged promising approach for scaling the distributed training machine learning models, particular via stochastic gradient descent (SGD) [Lian al.)
2017 Tang et al. 2018 Koloskova et al. 2019a Its key advantage is that it removes the need for central coordinator node in distributed training, and therefore it can allow for high scaling.
The general decentralized optimization setting is the following: we given nodes, each with subset of data from some distribution, which can communicate over some underlying graph topol- ogy. In each global round, each node samples some local data, performs local gradient step, and paired with neighbor, which may be chosen randomly. The nodes exchange model infor- mation pairwise, and then update their models, often via direct model averaging. Variants of this setting have been analyzed since pioneering work by Tsitsiklis [1984). for various estimation and optimization algorithms [Xiao and Boyd| 2004 Nedic and Ozdaglar 2009 Johansson et al. 20099 Shamir and Srebro 2014 and have seen renewed interest given upplicability to training deep neural networks (DNNs) at scale, c.g. [Lin et al. 2017 2018 Assran et al. 2018).
Recently, there has been significant focus on reducing the synchronization overheads for decentral- ized training, usually employing three approaches: 1) implementing faster non-blocking communi- cation between communication partners at round [Lian al. 2018 Assran et al., 2018), which may cause them to see stale versions of their models, 2) allowing nodes to take local sleps in between
35th Conference on Neural Information Processing Systems (NeurIPS 2021).

---

their communication rounds [Wang and Joshi rization to the communication [L and De Sa 2020 Tang al., 2018 Koloskova et al. 2019abb b).
2018 Koloskova et al. 2020], and 3) applying quan-
The above impressive line of work contributes a rich set of algorithmic and analytic ideas; however, one common limitation is that the algorithms are usually set in the synchronous gossip model, which requires all nodes to perform their communication in lock-step rounds, and share common notion of time. thus reducing their practicality. To mitigate this fact, some references, e.g. (Lian et al. 2018 [Asran et al. 2018 Lu and De Sa 2020] partially relax this requirement, although they do so the cost of additional assumptions, or reduced guarantees, as we discuss in related work. Another relative limitation is that the analyses are usually customized to the bespoke communication-reduuee methods being applied, and therefore are hard to generalize to other methods.
Our Contribution. In this paper, we consider decentralized SGD-based optimization in the simpler, but harder analyze, asyrchronous gossip model (Xiao and Boyd 2004], J, in which communication occurs in discrete, randomly chosen pairings among nodes, and does not require a common notion of time. We prove that new variant of SGD we call SwarmSGD converges in this setting. even though it supports all three communication reduucioon approaches mentioned above in conjunction. Our analysis generalizes to heterogeneous data distributions and communication topologies.
At a high level, SwarmSGD works as follows. Each node i maintains a local model estimate X; based on which gradients are generated, and shared buffer where quantized models are stored for communication with other nodes. In each step, node i first computes a sequence of H local gradient steps, which it does not yet apply. Next, the node chooses communication partner j, uniformly at random among its neighbors. Then, node reads from its own communication buffer and from the communication buffer of j. obtaining quantized models Q; and Qj- A subtlety here is that Q; is not necessarily the quantized version of the model X,, since other nodes can write concurrently to i's buffer. The node i then averages Qi with Qj. and updates the neighbor's remote buffer to the quantized average. Finally, applies its local gradient steps to the resulting average, adopts this as its next model X, and writes quantized version of it in its own shared buffer. This procedure can be implemented in a deadlock-free, non- blo-kioc manner, by using either shared-memory or the remote direct-memory access (RDMA) calls supported by MPI [Woodall et al.) [006]. Importantly, the communication partner does not need to block its computation during communication, and may be contacted by more than one interaction partner during single local step, although we do assume that individual reads and writes are performed atomically.
A key component of this procedure is the quantization scheme: e.g. [Alistarh et al. 2017] would destroy convergence guarantees, as the quantization error would be proportional to the model norm, which may not be bounded. Instead, we use a customized variant of the quantization scheme Davies et al. 2021]. J. whose error depends on the distance between the point being quantized (the model), and an arbitrary reference point, provided as a parameter. We prove that each node can reliably use its own model reference point to quantize and de-quantize messages placed in its buffer by other nodes. In turn, this requires care in the analysis.
directly using an unbiased quantizer,
Specifically, the key observation behind our analysis is exactly in showing that the nodes' local mod- els stay well-enough concentrated around their mean throughout optimization to allow for correct decoding of quantized models, which in turn implies joint convergence by the nodes towards point of vanishing gradient. This concentration follows via non-trivial super-martingale argument. If nodes take a constant number of local SGD steps between communication steps, then S SwarmSGID has ((vn) speedup to convergence for non2-convex objectives. This matches results from previous work which considered decentralized dynamics but with global synchronization [Lia et al. 2017].
Experimental Validation. We apply SwarmSGD to train deep neural networks on image classifi- cation and machine translation (NMT) tasks, deployed on the Piz. Daint supercomputer (Piz 2019). Experiments confirm the intuition that the average synchronization cost of SwarmSGD per itera- tion is low: it stays at less than 10% of the batch computation time, and remains constant as we increase the number of nodes. For example, using SwarmSGD, we are able to train a Transformer- XL (Vaswani et al.) 2017] model on WMT17 (En-Ge) 1.5x faster than a highly-optimizee large- batch SGD baseline, and to slightly higher accuracy, without additional hyper- param-par tuning. At the same time, due to the reduced communication frequency, Swarm also improves upon the speed of the previous practical decentralized methods, e.g. (Lian et al., 2017 2018 Assran et al.) 2018). Importantly, we also note that, in less overparametrized settings such as training residual CNNs (He et al., 2016) on ImageNet (Russakovsky et al. 2013), nodes do need to perform more iterations over the dataset relative to the baseline in order to recover full accuracy. This is predicted by the analy- sis, and confirms similar findings in previous work [Assran et al. 2018 Overall, our method does
2

---

appear well-suited to training large modern models at node counts where global synchronization among all nodes prohibitively expensive.
Related Work. Decentralized optimization has long history [iissiklis 1984 and is related to the study of gossip algorithms, e.g. [Kempe et al., 2003 Xiao and B 2004 Boyd et al. 2006].
Gossip is usually studied in one of two models [Boyd et al. 2006|: : synchronous, structured in global rounds, where each node interacts with a randomly chosen neighbor, forming a matching, and asynchronous, where each node wakes up at random times, e.g. given by a Poisson clock, and picks random neighbor to interact with. Several classic optimization algorithms have been analyzed in the asynchronous gossip model (edic and Ozdaglan lar 2009 Johansson et al.) 2009. Shamir and Srebro 2014). In this paper, foeus analyzing decentralized SGD in this model.
As mentioned, the growing line of work on decentralized optimization for machine learning has mostly focused on variants of the synchronous gossip model. Specifically, Lian et al.. 2017 con- sidered this setting in the context of DNN training, while and Tang et al. (2018) and Koloskova
ct al. [ also analyzed decentralized optimization with quantization in the synchronous model.
Wang and Joshi [0188] and Koloskova et al. [2020) provided analysis frameworks for synchronous decentralized SGD with local updates, and possibly changing topologies.
Lian et al. 2018 and Assran et al. [2018) focused specifically on reducing synchronization costs in this setting, and proposed algorithms with partially non-blocking communication, in which nodes may read a stale version of the interaction partner's information, modelling e.g. a communication buffer. However, the maximum staleness must be bounded by global variable т, which must be enforced throughout the execution. As observed by [Assran al. [2088), enforcing this bound can cause blocking, and therefore the authors of these works propose to implement relaxed round- based model, in which nodes interact once per round in perfect matchings. Their algorithms provide
O(I/VTn) convergence rates, under analytical assumptions.
Upon careful examination, we find that their analysis approach can be extended to the asynchronous gossip model we consider, by defining the "contact matrices" to correspond to pairwise interactions. However, this introduces two significant limitations. First, the analysis will not support local gra- dient updates to models nor quantized communication. If we remove these practical relaxations, our technique yields better bounds, as our potential analysis is seeiffically-tillore to this dynamic interaction model. Second, as we detail in the Appendix, some of their technical conditions imply existence of global synchronization. For Assran et al. (2018), as we detail in the Appendix, their analysis would not guarantee any non-trivial speedup due parallelization in the asynchronous gos- sip model. We describe these issues in detail and present a systematic comparison in Appendix [A]
Lu and De Sa [020 provided a novel approach to analyze decentralized SGD with quantization and limited asynchrony: specifically, their algorithm requires blocking communication, i.e. nodes have synchronize explicitly during interactions, but may see old versions of eachothers' models. More precisely, during each interaction, both parties are responsible for updating their local models, meaning that once node is woken up (we call it initiator node) and chooses interaction partner it has to block until the partner is woken up as well. In our case, initiator can update both its local model and the local model of its partner and proceed to the next step without blocking. Koloskoval ctt al. [019a] use a similar update rule in the synchronous model. Zhang and You| [202]] recently proposed a decentralized algorithm which is fully-asynchronous as long node activation rates and message delays are bounded. As noted earlier, bounding activation rates does imply blocking; however, tolerating (bounded) message delays does improve over our approach of updating models using atomic writes. The setting further differs in that they assume that nodes compute full (non- stochastic) gradients, as well as that the loss function satisfies the PL condition.
In sum, we are the first to explicitly consider the asynchronous gossip model, and the impact of local updates, asynchrony, and quantization used in conjunction together with decentralized SGD. Our technique new, relies on fine-grained analysis of individual interactions, and can yield improved bounds even in the case where H = 1. Further, our algorithm is the first to allow for both communication-comme compression and non-blocking communication. From the implementation per- spective, the performance of our algorithm matches or improves that of previous methods, notably D-PSGD [Lian et al. 2017]. AD-PSGD [Lian al. 2018 and SGP [Assran al. 2018).
2 Preliminaries
The Distributed System Model. We consider a model which consists of n 2 2 nodes, each of which is able to perform local computation. We assume that communication network of nodes is
3

---

a graph G with spectral gap X2, which denotes the second smallest eigenvalue of the Laplacian of G. Let Pmax: Pmin be the maximum and minimum degrees G. respectively. We will focus on densely-connected topologies, which model supercomputing and cloud networks: for instance, the standard Dragonfly topology [Kim et al. 2008 Besta and Hoefler 2014] is regular, densely connected and low-diameter mimicking regular expanders.
The execution modelled as occurring in discrete steps, where each step a new node (the "initia- tor") is sampled, and can then contact one of its neighbors (the "responder") uniformly at random. (At the algorithm level, the initiator is "sampled" once it completes its current computational step, and seeks to interact with a neighbor.) We denote the number of steps for which we run by T. Glob- ally, the communication steps can be seen sequence of sampled directed communication edges. Thus, the basic unit of time is a single pairwise interaction between two nodes. Notice however that in real system (nn) of these interactions could occur in parallel. Thus, the standard global time measure is parallel time, defined as the total number of interactions divided by n. the number of nodes. Parallel time intuitively corresponds to the average number of interactions per node until convergence. This model is identical to the asynchronous gossip model [Xiao and Boyd 2004). and to the population protocol model [Angluin et al. 2006].
Stochastic Optimization. We assume that the agents wish to jointly minimize a d-dimensional, differentiable function f IR + R. Specifically, we will assume the empirical risk minimization setting, in which agents are given access to a set of m data samples S = {si,..., 5m) coming from some underlying distribution D, and functions & Rd + E which encode the loss of the argument at the sample s,. The goal of the agents is to converge on model x² which minimizes the empirical loss over the m samples, that is x argmin,
argmin, Σx ((x).. We assume that each agent i has local function f. associated to its fraction of the data, i.c Yx Rd.
f(z)= = >> i=1 fi(z)/n.
Agents employ these samples to run a decentralized variant of SGD, described in detail in the next section. For this, we will assume that each agent has access to unbiased stochastic gradients g: of the function fi. which are functions such that (x)) computed by each agent by sampling i.i.d. the distribution D, and computing the gradient of f at with respect to that sample. Our analysis also extends to the case where each agent is sampling from its own partition of data. We assume the following conditions about the objective function, although not all our results require the second moment bound:
V (z). Stochastic gradients can be
1. Smooth Gradients: The gradient V (x) is L-Lipschitz continuous for some I. >> 0, i.e. for all x, y E Rdd and agent i:
(v) - V)((i) < L||= - yll-
2. Bounded Variance: The variance of the stochastic gradients is bounded by some 0² > 0, i.e. for all Rd and agent i:
(=) ( 5o.
E
3. Bounded Local Function Variance: There exists x² > 0, such that for all Rd:
(V(x))-VAl (z)
4. Bounded Second Moment: The second moment of the stochastic gradients is bounded by some M > 0, i.c. for all x E ddd and agent
IE
9
(x)
2
(4)
Note that throughout this paper for any random variable X, by ||| we mean ||]
Each node has a communication buffer, which, for simplicity. we assume can be read and written atomically by each node; Importantly, buffers can only hold quantized quantized vectors.
Quantization Procedure. We use quantization function which follows from Lemma 23 in (the full version of) Davies al. [202T].
Corollary 2.1. (Quantization for Communication Buffers) Fix parameters R and 0. There exists a quantization procedure defined by an encoding function Enca, Rdd + {0, 13" and a decoding function DecR,E = Bd x {0, + dd such that, for any vector x E Rd which we trying to quantize, and any vector y which is used by decoding, which we call the decoding

---

key, if || v|1 S Re then with probability at least 1 - log log( |--سا| JO d), the function QR.e(T) = DecR, EncR, (x)) has the following properties:
1. (Unbiased decoding) RI = [E(DCCR, EnCR, =x;
2. (Error bound) [[Qn,e(=)) - ==I - (R² T)c;
3. (Conmunication bound) To compute Decn,cly, EnCR,(())), only the first B bits of Enen,)()) are needed, where B = log( R || -
Proof. Lemma 23 of the full version of Davies et al. 2021 provides similar guarantees as the ones we want to prove, but they assume interactive message- -aatgggg-asnggggg communication between an encoding node and decoding node v. However, in their setting, the messages sent by u are non- non-adaptive: simply sends quantizations using an increasing number of bits, until replies confirming that it has decoded successfully. The number of bits sent during communication
upper bounded by O (dlog( [| ell)), where is vector node u is sending and y is vector node is using for decoding. In our setting, we use communication buffers which, so node u can simply append all of its potential messages together as (z)
Critically, notice that node u should append enough bits so that the decoding is possible (Since in our setting there is no way for to acknowledge that it received enough number of bits). This can be done in two ways. If u knows the distance between æ and y. then u can simply write O (dlog( (1 yll) bits in the register.
In the second case, u does not know the distance. Let T be the total number of times nodes com- municate throughout our algorithm. We will show that with high probability all distances between encoded and decoding vectors will be at most <I" (dependence on T stems from the fact that we R wish to show an upper bound with high probability, please see Lemma therefore at most (dd log 7) bits for quantization will suffice in the worst case. Thus, the node writes O log T') bits in the register, but when v tries decode, it does not need all those bits: it reads and uses only the first O (log( _ || vil) bits.
the Appendix), and
Counting Communication Cost. We emphasize that, when we calculate the number of bits needed by quantization we actually aim to measure the number of bits exchanged between and v. In the setting we consider, which has local registen/communication buffers, this is the number of bits spent to read from (or to write to) the non-local register. Since the second case above involves writing a relatively large number of bits, we will use it only when is writing quantized value to its own register/buffer, and does not need communicate the bits. Then, only the O (log( bits read by u need to be communicated.
@ B| vll
To summarize, in our algorithm we will always ensure that whenever some node u writes quantized value, it either knows the key which will be used for decoding it, or is writing to its local register. O
3 The SwarmSGD Algorithm
We now describe a decentralized variant of SGD, designed to be executed by a population of n nodes, interacting over the edges of communication graph G, as described above. The algorithm proceeds in individual communication steps, where in each step a node which has completed its local computation, seeks random neighbor to communicate with. We will alternatively say that node gets activated (once it finished computation) and then becomes initiator of the interaction.
The Communication Registers. The communication buffer of each node i consists of two registers: one containing an encoded version of its own (possibly outdated) model, which will only be written to by node itself, and one for holding an encoded version of its current model, which will only be written to by other nodes. (This second register can be seen as a "communication queue" for the nodes wishing to communicate with i.) Initially all registers contain zero vectors.
Parallel Execution. For simplicity we will skip the details of quantization, and assume that nodes write and read quantized models directly, without encoding and decoding steps. Both current and outdated models are zero vectors initially. Each node computes a number of local gradients based on its last model view, and other nodes may update this model while i is computing. Hence, only after node is done with computing local gradients does it read its updated current model. Let X; be the value of the outdated model and let X; be the value of the current model. Node i computes the average of quantized models ((X.)+((X,) and writes it in register which contains current model 2
5

---

()x)X.)) (where v) is a learning rate and h(x)) is sum of local gradients), and writes it in both of its local registers, one containing the current model and one containing the outdated model. Once the write is finished, it again proceeds to compute local gradients, based on the view ((x.)+((x)) m))()))
of node j. Next, it computes Q(x.)+Q(X))
2
Sequential model. For the analysis, it is useful to map these parallel interactions to a sorted se- quence of sequential ones. Thus, time steps track the interactions between agents, and each in- leraction consists of random number of local steps steps which activated node performs, plus one averaging step where activated node (or initiator node) contacts its random neighbour. The analysis assumes that nodes get activated randomly, by independent Poisson clocks, which leads to a uniform global sampling distribution. In practice, this could be approximated by having the number of local gradient steps executed by each node be a geometric random variable of mean H. For the sake of practicality, experiments will take H to be small constant, instead of random variable, which yields similar results. The pscudocode from the point of view of a single node which was activated at step t ++1 is given in Algorithm [
For 2 let Eine( ( and Eno(X;) be the values written in the registers containing the outdated and the current model of agent after t steps, respectively. That is, X; is the current model of agent
i and X is the outdated model.
The Communication Procedure. Since was activated at step we will assume that it has already computed H; local gradients using the outdated model Xt where H; is geometric random variable with mean H, as follows. Let (x:)) = 04; for indices I S Hi, let ((())) = (X; Ee=o nyh (Xt)) be the q-th local gradient. Then, let (x;) Σx= h? (X;) be the sum of all computed local gradients. Or alternatively, since we are in sequential setting, we can assume that i does computation at step t. First, retrieves Q(X;) (the quantized version of its current model), by decoding Enc(X;) using key Q(X;). . We would like to note that i can obtain Q(;:) simply by decoding Enn((;i, using key X3 (which it knows, to full precision, since it calculated the value itself), and this step does not cost any communication bits since all of the terms involved are local to i's registers.
Then, it contacts its interaction partner j. Node calculates Q(x{) ) by decoding Enc(X;), again using X as a key, and then it retrieves Q(x²) by decoding Ene(Xp) (X/) with key Q(x?). Then, i calculates X = 2(x;) ((x?) (X;) and X 4+1 2(x?) 2(x))
Next, node i calculates Enc(X; and writes its own register for its outdated models. Here, we use the first case for quantization using Corollary 2.1 i is not aware of the key that other nodes will use for decoding, but since it is writing its own local register, it can afford use the worst-case (ld log T') bits. Additionally, it writes Enc(Xi+1) to its own register containing current model, so that there are enough bits for Q(((+1). (Note that X X has to be used decoding key.)
Finally, it calculates Enc(Xi+4) and writes in the register which contains the current model of j. using enough bits that it can be decoded using Q( (we have that X X/). Notice that, the way our algorithm is specified, every node which tries to decode Ene(X;+1) will use Q(X:+1) as key (which i knows), hence Corollary(2.1 holds in this case well. We emphasize the fact that all this communication is one-way, as does not require j's intervention. By Corollary 2. the total number of bits used is:
(dllog( -x1x)xx11) (
R [((())) ( -x(())
(Recall that we count only reading and writing other registers, and do not count operations i performs on its own registers.)
We will show that we make the probability of any instance of quantization failing less than 1/T for some sufficiently large constant c, by setting the constant factor in the number of bits sufficiently high. Then, we can take union bound over all instances of quantization throughout the algorithm, to show that none fail with high probability in T. Henceforth, we will then be able to prove the convergence of our algorithm conditioned on this event.
Avoiding race conditions. An interesting question is what happens when multiple nodes contact j concurrently. For conciseness, our pscudocode assumes that the update sequence in lines 8-

---

Algorithm Sequential SwarmSGD pseudocode for each interaction between nodes i and j.
1: % Let G' be communication graph.
2: % Initial models X X6
X6
3: for f
do Sample initiator node uniformly at random.
4:
5:
Node i samples a node j. adjacent to in G, uniformly at random.
6:
Let - 7ス be the last step at which node was chosen as initiator.
7:
Let Xi = x its model from that step.
8:
Q(X:) (ec(Q(Xi), Enc(Xi))
9:
Q(x)) < Dec( Fmo((())
10:
Q(X') + Dec(Q(X))) Enc(X)))
11:
Xi+1 < Q(x;)/2 -(xx)))--(
X/41 + Q(x;)/2 Q
13:
Write Enc( ( the registers containing current and outdated models of node i
14:
Write Ene(X(+1) to the register containing current model of node
15:
For l: # i,j. X X
16:
end for
14 happens atomically, but this sequence can cause a data race. mitigate this, we can use a bounded non-blocking queue [Michael and Scott, 1996 at each node instead of single buffer. Thus, instead of updating the buffer value atomically, each node simply appends the corresponding quantized model mean to j's communication queue. In practice, this queue is extremely unlikely to be contended, since communication collisions are rare.
4 The Convergence of SwarmSGD
Let μ4 = >E= Xi/n n be the mean over node models at time t. Our main result is the following:
Theorem 4.1. Assume the total number of steps T 2 10n, learning rate = nn/TT, quantization
parameters R 2 + T and nHM Then, with probability least ( have that (R*47)-
Algorithm 7 converges rate
6(0² + (HH)) E|] 2(f(Ho) f(x)))
12HM
+ C Pmiaa H
+
HVT
VT
VT
T Pmmin
t=0
for constant C. and uses O (dlog
Pmag Prennds
+ log log expected communication bits per step.
Discussion. First, this notion of convergence is standard in the non-convex case [Lian et al. 2015 2017 2018). and each of the upper bound terms has an intuitive interpretation: the first represents the reduction loss relative to the initialization, and gets divided by the number of local steps H, since progress is made in this term in every local step; the second represents the noise due to stochasticity, and is naturally linear in H, as H steps are taken in expectation between two interactions. (Recall that in our model T is the number of interactions, and TH is the expected number of gradient steps.) The fourth term encodes overheads caused by local steps. quantization, and graph structure; however, it usually seen as negligible (cf. (Lu and De Sa 2020)), ), due to division by T.
The third term the critical one, itively, this term appears because our algorithm combines both non-blocking communication, and quantization: first, unlike prior work, we do not assume an explicit delay upper bound on com- munication; in conjunction with quantization, the unbounded delay this implies that our estimate on the model average 14 may become dependent on M for large delays, which causes this dependency. While this limitation appears inherent, we are able to remove it we eliminate quantization: in this case, get negligible dependency M. We formalize this in Corollary 4.2
implies a dependence on the second-momen bound. Intu-
Second, if we focus on the total number of steps to reach some error bound, we notice an interest- ing trade-off between the linear reduction in H in the first term, due local steps, and the linear increase in H in the other terms. Notice that, for dense and low-diameter graphs, such as the regu- lar expanders popular in cluster networks, parameters, and communication is linear in d. However, one limitation is that we could have a log n dependency in the communication for highly-irregulle and poorly conneced graphs.
convergence bound has no dependence in the graph
7

---

Finally, note that time T here counts total interactions. However, (()) pairwise interactions oc- cur independently in parallel, and so we can slightly abuse notation and replace T by nI in the above formula, to obtain optimal @( speedup in terms of wall-clock time. Yet, this speedup dampened by the variance due to noisy local gradient steps, fact which we will revisit in the experimental section.
Proof Overview, At a high level, the argument rests on two technical ideas. The first is that, in spite of noise and local steps, the nodes' parameters remain concentrated around the mean (4. The second is to leverage this, and bound the impact of stochastic noise and model staleness convergence. In particular, the main technical difficulty in the proof is to correctly "encode" the fact that parameters well concentrated around the mean. A natural approach is to bound the model variance r after t interactions. Formally, we define r = Ei=1 X - pell?, where b4 = - Xt/n, as before.
We bound the expected evolution of T, over time, depending on the learning rate, number of local steps, quantization parameter and the bound provided by the assumption on the stochastic gradients (the bound ²) The critical point is that the upper bound on the expectation of I' does not depend on the number of interactions t. More precisely, if all the above
are constant, we get that [t)] = Onn). Our approach brings over tools from classic load-balancing [ereenbrink cct al. 2009), to the multi-dimensional case.
Three key elements of novelty in our case are that (1) for the load balancing process is dynamic, in the sense that new loads, i.c. gradients, get continually added; (2) the balancinng process we consider is multi-dimensional, whereas usually the literature considers simple scalar weights; (3) the models can be outdated and quantized, which leads to a complex, noisy load-balancing process. We resolve the this third and most challenging issue by using carefully-define defined auxiliary potentials. Bound. Upon reflection, we notice that can render the dependency
Removing the on M negligible if we do not use quantization, but otherwise keep the algorithm the same:
Corollary 4.2. Given the previous assumptions and learning rate 1 n/ TT, for some constant C, we have that the Algorithm Where quantization is the identity converges at rate
T T
2(((m)) - I(x))) 6( + +6Hs²) HVT
Cnēpmazz H2
E BIVS(M))
+
VT
T Tpmin X2
Notice that in this case all the term containing the second moment bound M2 is dampened by a factor of T, hence we can assume that Algorithm | converges at close-to optimal rate
O (((())) (1= 6666) This result still improves upon previous analyses [Lian et al. HVT
/T
2018 Assran et al., 2018 Lu and De Sa 2020) in the sense that communication completely non-
blocking (there is no T), and we allow for local steps.
Further, in the absence of quantization and assuming that the nodes perform single local gradient step, we can entirely remove assumption 4 when T is large enough (e.g for the fully connected
graph we will need T 2 {(n")). More precisely, we can attain convergence rate of of (((m)) + (o² (o2+
VT
n² Prugg 12(00²+2)) We leave the proof of this last extension to the full version of this work.
Tpmin A
5 Experimental Results
In this section, we validate our analysis, by applying the algorithm to training deep neural net- works for image classification and machine translation. We map the algorithm onto multi-node supercomputing setting, in which we have a large number of compute nodes, connected by fast com- munication links. The key overhead in this setting is synchronization: at large node counts, the cost of synchronizing all nodes so they execute in lock-step can be very high, see e.g. [Li et al., 2019) for numerical results on different workloads. Transmission cost also becomes significant at large node counts and large model sizes. Decentralized methods can mitigate this overhead, since nodes synchronize only sporadically and in pairs.
Target System and Implementation. We run SwarmSGD on the CSCS Piz Daint supercomputer, which is composed of Cray XC50 nodes, each with Xeon E5-2690v3 CPU and an NVIDIA Tesla P100 GPU, using a -fate-of-the-ar Aries interconnect over a Dragonfly network topology, which is regular. Please see Piz [2019] for more details. We implemented SwarmSGD in Pytorch and Tensor- Flow using MPI-based primitives, with non-blocking averaging. The Pytorch implementation is on top of SGP framework [Assran et al. 2018). and uses SwarmSGD to train ResNets on the CIFAR-
8

---

200000
Uiraased BLEU score
Thrughpus (eolereee
160000
Alreduce
local SGD
SGP
WAMSSGD
local nodes)
10-
AD-P5GD
SwarmBGD
80000
SGD (32 nodes)
BGD redie))
40000
AD- PSCDPSDD(( (52 modwa)
són Training time (minates))
1960
1500
0-
nodes
nodes
64 nodes
(a) Convergence versus Time.
(b) Throughput comparison. Higher better.
Figure 1: Convergence and Scalability on the Transformer/MMT Task with multiplier 1.
Test accuracy (Resnet 1.0)
Timing ans yas
Suardlo Liard SUMMOGD lotti Pig!
10
(a) Convergence in time versus number of local steps for 8 on ImageNet. All variants recover the target accuracy, but note the lower convergence of variants with more local steps. The periment is run on nodes.
(b) Average time per batch for previous methods, compared to SwarmSGD, on ResNet (.NNet18/mmageet The base value the axis (0.4) is the average computation time per batch, values ahove represent average communication time per batch.
Figure 2: Convergence results and performance breakdown for ResNet 8/ImageNet.
10/100|u Krizhevsky et al. [2014] and ImageNet [Russakovsky et al. 2015] datasets, while we use the TensorFlow implementation train the original version of the Transformer-Xi model [Vaswani ctt al. 20177] on the WMT17 (En-Ge) dataset. All algorithms use the same topology overlay, which fnlly-coneected: according to their theory and experiments, this well-connected overlay should maximize convergence speed. SGP was run with overlap factor 1, following (Assann et al. [2018).
Training Process. Our training methodology follows data-paralle training, with some differences due to decentralization, and is identical to previous work on decentralized and local SGD, c.g. Lian et al. (017), Assran et al. (2018), Lin et al. 2018). Training proceeds in epochs, each of which corresponds to processes collectively performing a full pass over the dataset. At the beginning of each epoch, we re-shuffle the dataset and partition it among processes [Lin et al., 2018).
As noted previous work [Lian et al., 2017 2018 Assran al.) 2018 variants of decentralized SGD are not always able to recover sequential SGD accuracy within the same number of epochs as this baseline. This justified theoretically, as the slower mixing can affect convergence, but also intuitively, as each model sees significantly fewer updates per epoch. Thus, we will allow the decentralized schemes to execute for more epochs, by constant multiplier factor between 1 and 3. To reduce multipliers, we experimented with SlowMo [Wang et al., 2019]; we found that it improved results across methods on CIFAR-IO, but not ImageNet scale: therefore, the provided results do not include it. Once we have fixed the number of epochs, we do not alter the other training hyperparameters: in particular, the learning rate schedule, momentum and weight decay terms identical to the standard values for sequential SGD, for each individual model.
Accuracy and Speed. We first examined whether SwarmSGD can in fact recover full accuracy versus the sequential or large-batch SGD baselines. In Table [ we provide an overview of parameter values to recover harge-batch SGD accuracy (following Goyal al. (2017) using SwarmSGD, on the ResNet, ImageNet and CIFAR tasks. We execute for 32 nodes on ImageNet, and 8 nodes on CIFAR-10. (Local batch sizes 128 for ResNet20 and ResNet50, and 128 for ResNet18. Quan- tization is not applied in these experiments.) The results show that Swarm can recover or slightly exceed the accuracy of the large-batch baselines, and that it has lower practical communication cost relative to existing methods (see Figure 2(b), where we separate the average computation cost per batch). However, Swarm requires significant additional passes over the data (up to 2.7x) to achieve

---

Model/ / Dataset
SGD Top-1
LB SGD Top-1
SwammSGD
Parameters
/ CIFAR-10
91.7% (200 epochs)
91.57% (200 epochs)
91.59% (300 epochs)
local steps
ResNet18/ ImageNet
69.76 % (90 epochs)
69.17% (90 epochs)
69. 69% (240 epochs)
local steps
ResNet50 ImageNet
76.14% (90 epochs)
76.01% % (90 epochs)
76.08% (240 epachs) local steps
Parameters for approximate Top-1 validation accuracy recovery on CIFAR-I0 and Ima- geNet running on 32 nodes. Swarm step count represents local SGD steps per model between two averaging steps, and epochs are counted in terms of total passes over the data by all nodes.
Table 1:
full accuracy, which negates its performance benefits in this specific setting, relative to large-batch SGD. (Please see the Supplementary for end-to-end time comparisons.) This partly negative finding is in line with previous work on decentralized methods [Assran et al. 2018).
Next, we examine accuracy for the WMT17 task. The results are provided in Figure I(a), in accuracy-vs-time format, for 16 and 32 nodes, executing for 10 global epochs. Here, the large-batch SGD (LB-SGD) baseline (BLEU score 26.1 1 at 16 nodes) is a poor alternative at high node counts due to model size: its throughput is low, and drops catastrophically at 64 nodes due to the network becoming severely mandwwithh-bttleneekk.
(see Figure 1(b)). At 16 nodes, Swarm slightly exceeds the baseline accuracy at 26.17 BLEU, for an end-to-end speedup of ~ 1.5x. In the same setting, Swarm outperforms all other decentralized methods (the fastest previous method, AD-PSGD, is 30% slower, and less accurate). both in terms of BLEU score, and in terms of end-to-end time.(The objec- tive loss graph is similar, and is provided in the Appendix). At 32 nodes, all decentralized methods reach lower scores (~ 23.5) after 10 epochs. However, we observed experimentally that running Swarm for additional epochs (multiplier 1.5) 32 nodes recovered a BLEU score of ~ 25.72, which is 30% faster than the 16-node version in terms of end-to-end time (omitted for visibility).
In addition, investigated 1) the accuracy of the real average of all models throughout training: it is usually more accurate than an arbitrary model, but not significantly so, corroborating the claim that individual models tend to stay close the mean; 2) the influence of the number of local steps on accuracy: perhaps surprisingly, we were able to recover baseline accuracy on ResNetl 8/ImageNet for up to 4 local steps (see Figure 2(a)); 3) the impact of quantization on convergence, where were able to recover accuracy when applying 8-bit model quantization to Swarm. We encourage the reader to examine the full experimental report in the Appendix, which contains data on these experiments, as well as additional ablation studies.
Discussion. Generally, the performance of SwarmSGD appears to be slighly superior to previous decentralized methods (see Figure 1 for an illustration, and Figure 2(b) for a performance break- down). We investigated this advantage, and found that the per-step communication cost of Swarm, without quantization, is similar to AD-PSGD; however, our algorithm benefits from the reduction in communication frequency: nodes communicate at least 2x less often, and therefore incur lower average communication cost. In particular, a closer examination of the average batch times in Fig- ure 2(b) shows that time per node per batch (including communication and computation) is largely constant as we increase the number of nodes, which suggests good scaling behaviour.
The main disadvantage of Swarm is that, similar to previous decentralized methods, it may need additional data passes order to fully recover accuracy at high node counts. However, we also note that our method did not benefit from the high level of hyperparameter tuning applied to large-bar batch SGD, e.g. Goyal et al. 2017]. We find interesting that this accuracy issue is less prevalent in the models, such as the Transformer, where Swarm can be a viable
context of large, over-parameteriin alternative to large-batch SGD within the same number of epochs.
Conclusions and Future Work
We analyzed the convergence of SGD in an extremely decoupled model of distributed computing, in which nodes mostly perform independent SGD updates, interspersed with intermittent pairwise averaging steps, which may be performed in an inconsistent and noisy manner. We showed that SGD still converges in this restrictive setting, even under consistency relaxations. Empirical re- sults complement our analysis, showing that this method can outperform previous decentralized algorithms, and can even be competitive against large-batch SGD for very large models. A natural extension would be to generalize the bounds to arbitrary communication graphs. From the practical perspective, one extension would be to reduce the additional training epochs, and to experiment on large-scale decentralized testbeds.
10

---

Acknowledgments and Disclosure of Funding
We gratefully acknowledge funding from the European Research Council (ERC) under the European Union's s Horizon 2020 research and innovation programme (grant agreement No 805223 ScaleML). PD partly conducted this work while at IST Austria and was supported by the European Union's 's Horizon 2020 programme under the Marie Sklodowska-Curie grant agreement No. 754411. SL was funded in part by European Research Council (ERC) under the European Union's Horizon 2020 programme (grant agreement DAPP, No. 678880, and EPIGRAM-HS, No. 801039).
References
Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jio Hsieh, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? case study for decentralized parallel stochastic gradient descent. arXiv preprint FrXxv:/705.09000 2017.
Hanlin Tang, Ce Zhang, Shaoduo Gan, Tong Zhang, and Ji Liu. Decentralization meets quantization. arXiv preprint arXiv: 1803.0644,, 2018.
Anastasia Koloskova, Tao Lin, Sebastian U Stich, and Martin Jaggi. Decentralized deep learning with arbitrary communication compression. arXiv preprint arXiv: aett:-907009595 2019a.
John Nikolas Tsitsiklis. Problems in decentralized decision making and computation. Technical report, Massachusetts Inst of Tech Cambridge Lab for Information and Decision Systems, 1984.
Lin Xiao and Stephen Boyd. Fast linear iterations for distributed averaging. Systems & Control Letters, 53(1):65-78, 2004.
Angelia Nedic and Asuman Ozdaglar. Distributed subgradient methods for multi-agent optimiza- tion. IEEE Transactions on Automatic Control, 54(1):48, 2009.
Bjöm Johansson, Maben Rabi, and Mikael Johansson. A randomized incremental subgradient method for distributed optimization in networked systems. SIAM Journal on Optimization, 20 (3):1157-1170 2009.
Ohad Shamir and Nathan Srebro. Distributed stochastic optimization and learning. In 2014 52nd Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 850- 857. IEEE, 2014.
Xiangru Lian, Wei Zhang, Ce Zhang, and Ji Liu. Asynchronous decentralized parallel stochastic gradient descent. In International Conference on Machine Learning, pages 3043-3052. PMLR, 2018.
Mahmoud Assran, Nicolas Loizou, Nicolas Ballas, and Michael Rabbat. Stochastic gradient push for distributed deep learning. arXiv preprint arXiv:1811.10792. 2018.
Jianyu Wang and Gauri Joshi. Cooperative sgd: A unified framework for the design and analysis of communication-efficiaee sgd algorithms. arXiv preprint arXiv: 180800760 2018.
Anastasia Koloskova, Nicolas Loizou, Sadra Borciri, Martin Jaggi, and Sebastian U Stich. A unified theory of decentralized sgd with changing topology and local updates. arXiv preprint arXiv:2003.10422 10422, 2020.
Yucheng Lu and Christopher De Sa. Moniqua: Modulo quantized communication in decentralized SGD. In Proc. International Conference on Machine Learning (ICML), 2020.
Anastasia Koloskova, Tao Lin, Sebastian U Stich, and Martin Jaggi. Decentralized deep learning with arbitrary communication compression. arXiv preprint 190i::1907.099
2019b.
Tim S Woodall, Galen M Shipman, George Bosilca, Richard L Graham, and Arthur B Maccabe. High performance rdma protocols in hpc. In European Parallel Virtual Muchine/Message Passing Interface Users' Group Meeting, pages 76-85. Springer, 2006.
Dan Alistarh, Demjan Grubic. Jerry Li, Ryota Tomioka, and Milan Vojnovic. QSGD: Randomized quantization for commuuication-efffcccci stochastic gradient descent. In Proceedings of NIPS 2017, 2017.
11

---

Peter Davies, Vijaykrishma Gurunathan, Niusha Moshrefi, Saleh Ashkboos Ashkboos, and Dan Alistarh. Distributed variance reduction with optimal communication. In Proceedings of the International Conference on Learning Representations, ICLR 2021. Full version available at 2xXi:22002.09268. 2021.
The CSCS Piz Daint supercomputer. http://www.eecec.hh//ootttrrstss daint 2019. Ac- cessed: 2020-1-25.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Eukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pages 5998-6008, 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang. Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al. Imagenet large scale visual recognition challenge. International Journal of Computer Vision, 115(3):211 252, 2015.
David Kempe, Alin Dobra, and Johannes Gehrke. Gossip- computation of aggregate informa- tion. In 44th Annual IEEE Symposium Foundations of Computer Science, 2003. Proceedings. pages 482 491. IEEE, 2003.
Stephen Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavrat Shah. Randomized gossip al- gorithms. IEEE/ACM Trans. Netw, 14(S1)2508822300 June 2006. ISSN 1063-6692. doi: 100.1119//TT.220000 200677711 874516 URL wttp:/...///...111.....1........ 2006. 874516
Jiaqi Zhang and Keyou You. Fully asynchronous distributed optimization with linear convergence in directed networks, 2021.
John Kim, Wiliam J Dally, Steve Scott, and Dennis Abts. Technology-driven, scalabe drag- onfly topology. 2008 International Symposium on Computer Architecture, pages 77-88. IEEE, 2008.
Maciej Besta and Torsten Hoefler. Slim fly: cost effective low-diameter network topology. In SC' Proceedings of the International Conference for High Performance Computing, Network- ing, Storage and Analysis, pages 348-359. IEEE, 2014.
Dana Angluin, James Aspnes, Zoë Diamadi, Michael Fischer, and René Peralta. Computation in networks of passively mobile finite-state sensors. Distributed computing, 18(4):235-25) 2006.
Maged M. Michael and Michael Scott. Simple, fast, and practical non-blocking and blocking concurrent queue algorithms. In Proceedings of the 15th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 267-275, 1996.
Xiangru Lian, Yijun Huang, Yuncheng Li, and Ji Liu. Asynchronous parallel stochastic gradient for nonconvex optimization. In Advances in Neural Information Processing Systems, pages 2737- 2015.
Petra Berenbrink, Tom Friedetzky, and Zengjian Hu. A new analytical method for parallel, diffusion- type load balancing. J. Parallel Distrib. Comput., 69 69(1):4461, January 2009. ISSN 0743-7315. 11l.10..1166..jpc..... 2008.05.00 005
URL URLhtttss://// https:///oi.i..../ http///ooooor////////o/ 1016/j jpdc. 2008 05. 005
Shigang Li, Tal Ben-Nun, Salvatore Di Girolamo, Dan Alistarh, and Torsten Hoefler. Taming un- balanced training workloads in deep learning with partial collective operations. arXiv preprint a90iv:1908.0 04207, 2019.
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. http://www.cc..orooto.. edu/kriz/efar.hmml 55, 2014.
The cifar-10 dataset.
online:
Tao Lin, Sebastian U Stich, Kumar Kshitij Patel, and Martin Jaggi. Don't 't use large mini batche, use local sgd. arXiv preprint arXiv:1808.07211 2018.
12

---

Jianyu Wang, Vinayak Tantia, Nicolas Ballas, and Michael Rabbat. Slowmo: Improving coamuuiication-effiiiee distributed sgd with slow momentum. arXiv preprint arXi::9110.0044,, 2019.
Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, An- drew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch sgd: Training imagenet in hour. arXiv preprint
02677, 2017.
Bhaskar Ghosh and S. Muthukrishnan. Dynamic load balancing by random matchings. J. Comput. Syst. Sci., 53(3)357-3770 December 1996. ISSN 0022-0000. 10.100.0 199100006 URL
https://doi.. 1/t///00.06//css.... 1996.0075
Sebastian U Stich. Local sgd converges fast and communicates little.
arXiv preprint
1805008800 2018.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's 's con- tributions and scope? [Ys]]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms them?
[Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're re us-
ing/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable in- formation offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
Did you include the full text of instructions given participants and screenshots, if applica-
ble? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "lfPWS9fDBxH", "reviewer": "Reviewer_Zmf3", "summary": "This paper discusses a new variant for asynchronous decentralized SGD called SwarmSGD. Different from many previous algorithms SwarmSGD does not suffer from deadlocks. A new compression algorithm is used in SwarmSGD, which is different from commonly used ones such as stochastic rounding. Convergence rates of SwarmSGD are given with discussion on the assumption of second moment bound on the gradients, and experiments on language modeling and ImageNet are conducted.", "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 paper addresses an important question in asynchronous decentralized optimization, and is well written. The content is generally easy to follow. \n\nPros:\n==\n- The application of (Davies et al., 2021) in decentralized optimization seems interesting. The idea of compressing the distance of model rather than model itself is well-motivated. \n\n- The paper provides detailed comparison to previous algorithms such as AD-PSGD and SGP (some of them are in the appendix), which clearly states the contribution and the challenges.\n\n- I didn't check all the proof line by line, but the overall logic and the asymptotic complexity seems reasonable to me.\n\n- The experiments are comparatively large-scale compared to other algorithm-type papers in the community.\n\nCons:\n==\n- In Theorem 4.1, the last term in the convergence rate is a little counter-intuitive. If SwarmSGD runs on a fully connected graph, it is expected to converge faster since the spectral gap increases. However, if we replace $\\rho_{max}=n$ from complete graph into the last term, it becomes $O(n^5)$; and if in such case we need the $1/\\sqrt{T}$ to be the leading term, we would require $T\\geq O(n^{10})$. This seems a little diverged from reality, could you elaborate why using a better graph worsen the convergence rate?\n\n- I'm a little confused by the statement of non-blocking and staleness in this paper. For starters, if worker $i$ is updating the communication buffer of worker $j$ while worker $j$ needs to read from its communication buffer for interacting with worker $m$, it should be waiting for $i$ to finish writing the buffer. Otherwise, it causes additional error like the Hogwild setting. A completely asynchronous execution should be one-sided writing such as ADDP algorithm in this paper: (https://arxiv.org/pdf/1901.08215.pdf). In fact, the line 4 in Algorithm 1 already implicitly assumes some sort of blocking: two workers cannot be sampled simultaneously and the updates in one iteration is completely atomic. Same thing applies to the staleness: if node $i$ is sampled uniformly, a staleness bound is implicitly placed. \n\n- In the abstract the author states the algorithm works for heterogeneous data case, which does not seem to hold in the main theorem. Specifically, a bound of $\\varsigma^2$ is still assumed in Equation (3) and shown in all the convergence rate. An algorithm robust to the heterogeneous case should be invariant to this bound. See the Theorem 2 of D$^2$: http://proceedings.mlr.press/v80/tang18a/tang18a.pdf. \n\n-  A minor concern: In AD-PSGD, the $T$ is the number of query to gradient oracles while in this paper, $T$ is defined as the total number of interactions. Since each node is performing $H$ local steps. For fair comparison, the $T$ in convergence rate should be replaced by $TH$. However, this calibrated rate seems to have an additional $\\sqrt{H}$ term on the sample complexity term $\\sigma^2$. Why having local steps if it compromises the convergence rate while not having explicit benefits in the experiments?\n\n**Updates**\n\nI thank the authors for adequately addressing my concerns. I suggest including some of these points in the paper to make it clearer.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I don't see any potential negative societal impact of this paper.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "cqNrdLuqbR2", "reviewer": "Reviewer_9ppy", "summary": "The paper introduces SwarmSGD, a novel method that makes use of a graph of computational workers without central synchronisation. To minimize synchronisation overhead but maintain consistency between the workers' versions of the model, asynchronous, non-blocking random peer-to-peer averaging takes place every few local gradient steps, and quantization is supported.\nThe paper then provides theoretical analysis (under fairly restrictive assumptions), illustrating in which regime this extremely decentralised algorithm can be expected to converge (in average).\nFinally, a thorough experimental section on significant benchmarks is run, demonstrating the actual potential of the method.", "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": "Generally speaking, the paper is clearly written, and is easy to follow. The authors provide valuable insights both in the description of the methods themselves, in the theoretical results and (perhaps most importantly) in their proofs. The Discussions part are very appreciated, and this type of analysis should become a staple for this type of paper.\n\nThe presented algorithm is novel and presents some very interesting characteristics, leading to potential gains in real-world ML workloads.\n\nThe experimental section contains very large scale experiments (at least for a paper in this theme), and demonstrate real potential.\n\nThere remains a few weaknesses in the paper, which I believe can be addressed with a bit more work.\n\nThe first one is some clarity issues. \n- In the initial description of the algorithm, it's hard to understand whether the general model is quantized or not. (l65 does not reference the crucial dequantization step before applying the gradient steps)\n- l85 'convergence for non-convex objectives' is not defined, making the statement harder to interpret.\n- some assumptions are not explicit: being able to simply replace T by nT in the bound relies on the strong assumption that computing gradients on different devices takes the same time.\n- how expensive the quantization/dequantization steps are compared to computing gradients is not explicited. That would be quite helpful to assess how useful quantization is.\n- that the optimal speedup is O(sqrt(n)) is not explained. Typically, using n machines one expects the optimal speedup to be O(n). This is the case even when analyzing linearly convergent algorithms. If we were to instead rely on the dependency in T, the optimal speedup there would be O(exp(n)).\n\nThe second issue is that there appears to be some overclaiming in terms of the theoretical results. While the paper promises non-blocking  updates, these are later supposed to be atomic. Similarly, the assumption l254 that Xi_t and Enc(Xi_t) are 'simutaneous' seems like a pretty strong assumption. Of course it simplifies the analysis but the crucial question is: can the proof be carried out without it? If not, then it is an integral assumption, which should be made explicit.\nThe results also suffer from fairly restrictive assumptions. While not unheard of, the necessary bounds are strong restrictions.\n\nFinally, perhaps not enough space is devoted to the experimental section.\n- It would be nice to describe the exact models trained in more details. The WMT model is in particular rather elliptically referred to.\n- the WMT results for SGD are quite surprising: why does the 32-devices run converge to a worse performance than the 16 one? It could conceivably be slower, but as it's got a bigger batch size should converge to a better end BLEU performance\n- BLEU is referred to several times as 'accuracy'. It's not an accuracy, it's a score.\n- for machine translation tasks using transformers, practitioners typically do not use SGD but Adam instead. Is there a clear path to SwarmAdam?\n\nAll told, this is a nice paper, whose potential is not quite fully exploited in its current form. I recommend acceptance, and would be willing tu upgrade my score depending on the authors' response.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Could lead to faster network training, which would reduce the energy footprint.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}, {"review_id": "ABGZ0MwSPu2", "reviewer": "Reviewer_GmDi", "summary": "This paper proposes a decentralized optimization method, SwarmSGD, for reducing the communication overhead in distributed deep learning. The proposed method combines asynchronous pair-wise gossip, quantized communication, and local updates into a single method and a unified analysis. Convergence guarantees are provided for smooth non-convex function, using the quantizer from Davies et al., 2021, and a bounded second moment assumption. Numerical results are provided on image classification (CIFAR, ImageNet) and machine translation (WMT En-Ge) tasks.", "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 and Significance\nThis paper mostly combines many related ideas from the literature (asynchronous pair-wise gossip, quantized communication, local updates) into a single method and so originality is limited. However, there is significance in the work since it is necessary for all these orthogonal communication reduction techniques to eventually be integrated together. In this sense, this paper fits nicely in the literature.\n\n### Quality\nI only have a couple of concerns about the quality of the empirical and theoretical contribution, and would appreciate if the authors could address these in their rebuttal.\n\nThe assumptions made consist of\n- Static communication graph\n- L-smooth\n- Bounded variance\n- Bounded second moment\n- Poisson point process for asynchronous activation of nodes\n\nTo the best of my knowledge, the analysis applies standard tools from the literature, e.g., the supermartingale-esque iteration, used heavily in the analysis of subgradient push methods, as well as perron-frobenius for consensus. However, in my opinion the bounded second momentum assumption is a non-trivial limitation of the theoretical contribution. It may be ok in a quantized setting, but this assumption is still used in Corollary 4.2 after removing the quantization effects.\n\nThe Poisson point process assumption is *fine* for the theoretical assumptions, but then it is approximated in practice by setting the number of local gradient steps for each node to be a geometric random variable, which I would expect to impractically degrade performance in practice, since more frequent asynchronous non-blocking communication is likely to result in better convergence.\n\nThe baseline numbers for SwarmSGD seem good and consistent with the literature. Specifically, the proposed method looks to recover standard numbers for the chosen benchmarks. However the timing comparison with other gossip-based methods looks highly misleading. For example, it seems odd to use a fully-connected topology for the comparison of general gossip-based methods like SGP and D-PSGD with the pair-wise methods like SwarmSGD. Especially since the whole motivation for gossip-based deep learning methods is to reduce communication overhead by leveraging sparse topologies.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There don't seem to be any obvious negative societal implications of this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "-i4eHNFQdez", "reviewer": "Reviewer_PXLA", "summary": "In this paper, authors propose the asynchronous algorithm for convex optimization in distributed decentralized model. This algorithm consists of two major components - local model estimation and quantization mechanism.", "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": "In this paper, authors propose the asynchronous algorithm for convex optimization in distributed decentralized model that's main idea is to decrease the communication complexity of the algorithm and figure out the communication bottleneck. The idea of the algorithm is the following: we randomly select some node $i$ in the network graph G and then randomly select one of its neighbors $j$.  After this, for node $J$ we save the average of quantized values for $i$ and $j$; however, for node $i$ we also update the model estimator via the local model update. This combination of local updates together with quantization technique allows to gain in communication complexity in comparison with local SGD that was shown in the experimental part of the paper. \n\n\nThe presented algorithm is not restricted to some specific quantization techniques since the requirement to the Encoding and Decoding procedure is quite soft. However, it makes harder to follow the intuition without any example of applicable quantizations (only reference to the another article is provided). \n\nDue to the Corollary 4.2 the theoretical result is close to the optimal one that is a strong point of the paper. Also, the experimental results show that the SwarmSGD algorithm works well in practice too; however, I found figures too  small and hard to read.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"ethical_concerns": "no", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1-3 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a gossip-style method to perform distributed optimization of a sum of individual functions, combining stochastic gradient updates with quantization mechanisms. In addition to a theoretical guarantee on the scheme's convergence, the paper reports on experiments training i) ResNets in pytorch on CIFAR-10/100 and ImageNet datasets, and a larger Transformer-XL model in tensor flow on the WMT17 dataset. 
The reviews for this paper all recommend acceptance, being especially laudative about the scale of the experiments performed to validate the proposed approach. The reviews also point to an implicit assumption of atomic updates in the algorithm's operation, which the authors acknowledge and will make explicit in the final version.

The authors' experimental work is indeed quite significant. It is nice to have a theoretical guarantee; a discussion of the meaning in theory and in the experiments of the assumptions (especially the 'Bounded Local Function Variance' assumption) would be enlightening.
Decision: Accept (Poster)