Decentralized SGD with Asynchronous, Local and Quantized Updates
Authors: Giorgi Nadiradze
Amirmojtaba Sabour
Peter Davies
Ilia Markov
Shigang Li
Dan Alistarh
Venue:  (2021)
Keywords: distributed machine learning
SGD
decentralized algorithms
quantization

Abstract: The ability to scale distributed optimization to large node counts has been one of the main enablers of recent progress in machine learning. To this end, several techniques have been explored, such as  asynchronous, quantized and decentralized communication--which significantly reduce the impact of communication and synchronization, as well as the ability for nodes to perform several local model updates before communicating--which reduces the frequency of communication. 
In this paper, we show that these techniques, which have so far  largely been considered independently, can be jointly leveraged to minimize distribution cost for training neural network models via stochastic gradient descent (SGD). 
We consider a setting with minimal coordination: we have a large number of nodes on a communication graph, each with a local subset of data, performing independent SGD updates onto their local models. After some number of local updates, each node chooses an interaction partner uniformly at random from its neighbors, and averages a (possibly quantized) version of its local model with the neighbor's model. 
Our first contribution is in proving that, even under such a relaxed setting, SGD can still be guaranteed to converge under standard assumptions. The proof is based on a new connection with parallel load-balancing processes, and improves existing techniques by handling decentralization, asynchrony, quantization, and local updates, into a single framework, and bounding their impact. 
On the practical side, we implement variants of our algorithm and deploy them onto distributed environments, and show that they can successfully converge and scale for large-scale neural network training tasks, matching or even slightly improving the accuracy of previous methods. 

Under review as a conference paper at ICLR 2021
DECENTRALIZED SGD WITH ASYNCHRONOUS, LOCAL, AND QUANTIZED UPDATES
ABSTRACT
The ability to scale distributed optimization to large node counts has been one the main enablers of recent progress in machine learning. To this end, several techniques have been explored, such as asynchronous, decentralized, or quantized significantly reduce the cost of synchronization, and the ability for nodes perform several local model updates before communicating- which reduces the frequency of synchronization.
communication-wine
In this paper, we show that these techniques, which have so far been considered be jointly leveraged minimize distribution cost for train- ing neural network models via stochastic gradient descent (SGD). We consider a setting with minimal coordination: munication graph, each with local subset of data, performing independent SGD updates onto their local models. After some number of local updates, each node chooses an interaction partner uniformly random from its neighbors, and aver- ages possibly quantized version of its local model with the neighbor's 's model. Our first contribution is in proving that, even under such relaxed setting, SGD can still be guaranteed to converge under standard assumptions. The proof is based new connection with parallel load-balancing processes, and improves exist- ing techniques by jointly handling decentralization, asynchrony, quantization, and local updates, and by bounding their impact. On the practical side, we imple- ment variants of our algorithm and deploy them onto distributed environments, and show that they can successfully converge and scale for large-scale image clas- sification and translation tasks, matching or even slightly improving the accuracy of previous methods.
independently,
have large number of nodes on
INTRODUCTION
Several techniques have been recently explored for scaling the distributed training of machine learn- ing models, such as communication-rrduction asynchronous updates, decentralized execution. For background, consider the classical data-parallel distribution strategy for SGD (Bottoul 2010), with the goal of solving standard empirical risk minimization problem. Specifically, we have set of samples S, and wish to minimize the d-dimensional function f : R2d IR, which is the average of losses over samples from S, by finding x= argmin Σ L E. (x)(S)). We have n compute nodes which can process samples in parallel. In data-parallel SGD, each node computes the gradient for one sample, followed by gradient exchange. Globally, this leads to the iteration:
T/ Σ (xt))
Je+1
where Ia is the value of the global parameter, initially of, 1) is the learning rate, and gl (xx) is the stochastic gradient with respect to the parameter It, computed by node at time t.
When executing this procedure at large scale, two major bottlenecks are communication, that is, the number of bits transmitted by each node, and synchronization, i.e., the fact that nodes need wait for each other in order to progress to the next iteration. Specifically, to maintain a consistent view of the parameter 2e above, the nodes need to broadcast and receive all gradients, and need to synchronize globally at the end of every iteration. Significant work has been dedicated to removing these two barriers. In particular, there has been progress on communication--eelceee variants of SGD, which propose various gradient compression schemes (Seide et al., 2014; Strom 2015) Alistarh et al. 2017 Wen et al. 2017]] Aji and Heafield 2017 Dryden et al. 2016 Grubic et al. 2018 Davies byratiinnb---teratte
synchronization (Recht et al. 2011 Sa et al. 2015) Duchi et al., 2015), as well as large-batch or periodic model
al. 2020). asyichronous variants, which relax the strict
averaging methods, which aim reduce the frequency of communication (Goyal et al. 2017 You

---

Under review as a conference paper at ICLR 2021
et al.
2017) and (Chen and Huo 2016 Stich 2018 or decentralized variants, which allow each node to maintain its own, possibly inconsistent, model variant (Lian et 2017] Tang et al. 2018 Koloskova et al. 2019). (We refer the reader to the recent surveys of (Ben-Nun and Hoefler 2019 Liu and Zhang 2020) for detailed discussion.) Using such techniques,
possible to scale SGD, even for complex objectives such as the training of deep neural networks. However, for modern large-scale models, the communication and synchronization requirements of these parallel variants of SGID can still be burdensome.
Contribution. In this paper, we take further step towards removing these scalability barriers, showing that all the previous scaling techniques techniques- decentralization, quantization. asynchrony, and local steps-can in fact be used in conjunction. We consider a highly decoupled setting with compute agents, located at vertices of connected communication graph, each of which can ex- ecute sequential SGD on its own local model, based some number of local optimization steps, a node can initiate a pairwise interaction with a uniform random neighbor. Our main finding is that this procedure can converge even though the nodes can take several local steps between interactions, may perform asynchronous communication, reading stale versions of each others' models, and may compress data transmission through quantization. However, both in theory and practice, we observe trade-off's between convergence rate and degree of synchronization, in that the algorithm may need to perform additional gradient steps in order to attain good solution, relative to the sequential baseline.
fraction of the data. Periodically, after
Our algorithm, called SWARMSGD, is decentralized in sense that each node maintains local version of the model, and two interacting nodes only see each others' models. We further allow that the data distribution at the nodes may not be i.i.d. Specifically, each node is assigned set of samples S and maintains its own parameter estimate z². Each node i performs local SGD steps on its model xf based on its local data, and then picks a neighbor uniformly random share information with, by averaging of the two models. (To streamline the exposition, we ignore quantization and model staleness unless otherwise specified.) Effectively, if node interacts with node j, node i's updated model becomes
H. L..H.
(1)
2
where is the total number of interactions performed by all nodes up to this point, j is the interaction partner of at step t + 1, and the input models zi,H. and ri,,, have been obtained by iterating the SGD step H; and H, times, respectively, locally from the previous interaction of either node. We assume that H; and Hj are random variables with mean H. that is, each node performs H local steps in expectation between two communication steps. The update for node j is symmetric, so that the two models match after the averaging step. In this paper, we analyze variants of the above SwarmSGD protocol.
The main intuition behind the algorithm that the independent SGD steps will allow nodes to explore local improvements to the objective function on their subset of the data, while the averaging steps provide a decentralized way for the models to converge jointly, albeit in a loosely coupled way. We show that, as long as the maximum number of local steps is bounded, this procedure still converges, in the sense that gradients calculated the average over all models are vanishing as increase the number of interactions.
Specifically, assuming that the nodes each take constant number of local SGD steps on average before communicating, we show that SwarmSGD has O (n) speedup to convergence in the non- convex case. This matches results from previous work which considered decentralized dynamics but which synchronized upon every SGD step, e.g. (Lian et al. 2017 2018). Our analysis also extends to arbitrary regular graph topologies, non-blocking (delayed) averaging of iterates, and quantization. Generally, we show that the impact of decentralization,, asynchrony, quantization, and local updates can be asymptotically negligible in reasonable parameter regimes.
On the practical side, we show that this algorithm can be mapped to distributed system setting, where agents correspond to compute nodes, connected by a dense communication topology. Specif- ically, we apply SwarmSGD to train deep neural networks on image classification and machine translation (NMT) tasks, deployed on the Piz Daint supercomputer (Piz, 2019). Experiments con- firm the intuition that the average synchronization cost of SwarmSGD per iteration is low: it stays around 10% or less of the batch computation time, and remains constant as we increase the number
2

---

Under review as a conference paper at ICLR 2021
of nodes. For example, using SwarmSGD deployed on 16 nodes, we are able to train a Transformer- XL (Vaswani et al., 2017) model on WMT17 (En-Ge) 1.5x faster than a highly-optimizzed large- batch SGD baseline, and to slightly higher accuracy, without additional hyper-parameter tuning. At the same time, our method appears be faster and more accurate than the previous practical decentralized methods, c.g. (Lian et al. 2017 2018 Assran et al., 2018), in the same setting.
Importantly, we also note a negative result: in less overparametrized settings such training residual CNNs (He et al., 2016) on ImageNet (Russakovsky et all 2013). nodes do need to perform more iterations over the dataset relative to the bascline in order to recover full accuracy. This is predicted by the analysis, and confirms similar findings in previous work (Assran et al., (2018). Overall, however, our family of methods should be well-suited to training very large modern models in large-scale settings, where global synchronization among all nodes prohibitively expensive.
Related Work. The study of decentralized optimization algorithms dates back to Tsitsiklis (1984). and is related to the study of gossip algorithms for information dissemination (Kempe et al, 2003 Xiao and 2004 Boyd et al. (006). 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, and asynchronous, where each node wakes up at times given by a local Poisson clock, and picks random neighbor interact with. The model we consider can be seen as equivalent to the asynchronous gossip model. The key differences between our work and averaging in the gossip model, e.g. [ooyd al. (2006), are that that 1) we consider local SGD steps, which would not make sense in the case of averaging fixed initial values; and 2) the gossip input model is static (node inputs are fixed, and node estimates must converge to the true mean), whereas we study a dynamicc setting, where models are continually updated via SGD. Several optimization algorithms have been analyzed Johansson et al. 2009; Shamir and Srebro 2014), while Tang et al. (018): Koloskova al. 2019 analyze quantization the synchronous gossip model.
in this setting (Nedic and Ozdaglar
2009
Lian et al. (2017 2018) and Assran et al. (2018) considered SGD-type algorithms in gossip-like models. Specifically, they analyze the SGD averaging dynamic in the non-convex setting but do not allow nodes to perform local updates or quantize. In particular, nodes perform pairwise averaging upon every SGD step. Table 2 in the Appendix provides thorough comparison of assumptions, results, and rates. Their results are phrased in the synchronous gossip model, in which nodes interact in a sequence of perfect matchings. for which they provide O(1/VTr) convergence rates under analytical assumptions. Lian et al. (2018) extends these results to variant of the gossip model where updates can be performed based on stale information, similarly our non-blocking extension.
Upon careful examination, one can find that their results can be extended to the asynchronous gossip setting consider, as long as nodes are not allowed to perform local SGD updates their models (corresponding to H = 1) or to quantize communication. Extending the analysis of distributed SGD to allow for local steps is challenging even in centralized models, see for instance Stich (2088). If we assume H 1, our technique yields similar or better bounds relative to previous work in the decentralized model, as our potential analysis is specifically-tailree to this dynamic interaction model. For instance, for Assran et al. (2018), the speedup with respect the number of nodes depends on a parameter C, which in turn, depends on 1) the dimension d of the objective function, 2) the number of iterations for the graph given by edge sets of all matrices used in averaging to be connected, and the 3) diameter of the aforementioned connected graph. In the dynamic interaction model we consider, the parameter C' will be at least linear in the number of nodes n, which will eliminate any speedup. We present a systematic comparison in Appendix [B]
In sum, relative to prior work on decentralized algorithms, our contributions are as follows. We are the first consider the impact of local updates, asynchrony, and quantization in conjunction with decentralized SGD. We show that the cost for the linear reduction in communication in H given by local steps is at worst squared variance increase in the parameter H. Our analysis technique relies on a fine-grained analysis of individual interactions, which is different than that of previous work, and can yield improved bounds even in the case where H 1. By leveraging the lattice-based quantization scheme of Daviess et al. (2020), we also allow for the implementation perspective, the performance of our algorithm is superior to that of previous methods, notably D-PSGD (Lian al. 2017), AD-PSGD (Lian et al. (018) and SGP (Assran al., 2018). mainly due to the ability to take local steps.
From
Wang and Joshi (2018) and Koloskova et al. (2020) provide analysis frameworks for the syn- chronous version of decentralized SGD with local updates, and possibly changing topologies. This is different setting from ours, since it requires each agent to take an equal number of gradient
3

---

Under review as a conference paper at ICLR 2021
steps before every interaction round, and therefore does not allow for agents progress different speeds (asynchrony). Further, we support quantization, and validate our analysis at scale.
PRELIMINARIES
The Distributed System Model. We consider a model which consists of n 2 2 anonymous agents, nodes, each of which is able perform local computation. We assume that communication network of nodes is a r-regular graph G with spectral gap X2. which denotes the second smallest eigenvalue of the Laplacian of G. This choice of communication topology models supercomputing and cloud networks, which tend to be regular, densely connected and low-diameter, mimicking regular expanders (Kim et al. 2008; Besta and Hoetler 2014).
The execution proceeds in discrete steps, where in each step sample edge of the graph G uni- formly at random and we allow the agents corresponding to the edge endpoints interact. Each of the two chosen agents updates its state according to state update function, specified by the algorithm. The basic unit of time is single pairwise interaction between two nodes. Notice however that in a real system (n) of these interactions could occur in parallel. Thus, a standard global 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 to convergence. We note that our model virtually identical to the population model of distributed computing (Angluin et al. 2006), or to asynchronous gossip models (Xiao and Boyd 2004).
Stochastic Optimization. We assume that the agents wish to minimize d-dimensional, differen- tiable function f Rd - R. Specifically, we will assume the empirical risk minimization setting, in which agents are given access to a set of m data samples S ( underlying distribution D, and to functions & Rd - R which encode the loss of the argument at the sample 8;. The goal of the agents is to converge on a model x* which minimizes the empirical loss over the m samples, that is
(51,..., sm coming from some
x² = argmin, = argmin, (1/m) Σ 4(x).
(2)
In this paper, we assume that the 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 stochastic gradients 9: of the function f, which are functions such that
E (x)) = Vzx)).
Stochastic gradients can be computed by each agent by sampling i.i.d. the distribution D, and computing the gradient of f at 6 with respect to that sample. (Our analysis can be extended the case where each agent is sampling from its own partition of data, see Section the Appendix.) We will assume the following conditions about the objective function (One of the extensions removes the second moment bound);
1. Smooth Gradients: The gradient V [xx) is L-Lipschitz continuous for some L > 0, i.e. for all F.y y E Rdd:
[V)()) ()() S L|
2. Bounded Second Moment: The second moment of the stochastic gradients is bounded by some
M > 0, i.e. for all x E IRd and agent i:
E
gi
S
M²
(5)
Note that throughout this paper for any random variable X, by X| we mean [|]]
3 THE SWARMSGD ALGORITHM
Algorithm Description. We now describe a decentralized variant of SGD, designed to be executed by population of nodes, interacting over the edges of r-regular graph G. We assume that each node i has access to local stochastic gradients 7' and maintains a model estimate X For simplicity, will assume that this initial model is 0d at each agent, although its value may be arbitrary. Each
4

---

Under review as a conference paper at ICLR 2021
agent performs SGD steps its local estimate X At random times given by clock of Poisson rate, we pick two neighboring agents i and j uniformly at random from G, and have them average their estimates. The interaction is precisely described in Algorithm |
For simplicity, the pseudocode is sequential, although in practice nodes perform their local SGD steps in parallel. Also, we have assumed a constant learning rate; we will detail the update procedure in the next section, as well more complex variants of this basic update.
Algorithm Sequential SwarmSGD pseudocode for each interaction between nodes i and j.
% Let G be r-regular graph.
% Sample an edge (i, of G uniformly random.
Require: agents and j chosen for interaction
% choose H, and Hj
% agent performs H; local SGD steps for q. to H; do
X X n (x+) end for
% agent performs Hj local SGD steps for q = 1 to H, do
x X n (X))
end for
%o agents average their estimates coordinate-wise
aug- t
X X + aog
THE CONVERGENCE OF SWARMSGD
We begin by analyzing the convergence of the baseline SwarmSGD algorithm. Fix an integer H 2 1. First, we will consider a variant where H; and H2 are independent. geometrically- variables, with mean H. This corresponds to interaction times being chosen by a Poisson clock of constant rate. To handle the fact that the number of local steps upon interaction is random variable, in this first case we will require stochastic gradients to satisfy the bounded second moment assumption, specified above. Intuitively, this is required since otherwise the "distance travelled" by a node could be virtually unbounded. In this setting, we prove the following:
random
Theorem 4.1. Let f be an non-convex, L-smooth function, whose stochastic gradients satisfy the bounded second moment assumption above. Let the number of local stochastic gradient steps per- formed by each agent upon interaction be a geometric random variable with mean H. Let the learning rate we use be n/.TT. Define = EE= Xi/n, where X; is a value of model i after t interactions, be the average of the local parameters. Then, for learning rate n n/vTT and any number of interactions T 2 n²:
E B[ 4(f(Ho) 4(F(Ho) (((oo)=(<=")) -f(x)) 2304H max LL,
A2 +1)
VTH
VT
Discussion. First, we note that this notion of convergence is standard in the non-convex case, c.g. (Lian et al., 2015 2017 2018), and that each of the upper bound terms has intuitive in- terpretation: the first represents the reduction in 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 rep- resents the influence of the variance of each individual local step multiplied by term which bounds the impact of the graph topology on the convergence. In particular, this term negatively impacts convergence for large values of H, L, and M. but gets dampened if the graph is well-connected (i.e. large X2). For example, in the case of the complete graph, we have X n.
Second, let us consider the algorithm's communication complexity, which we measure in terms of the total number of communication steps. We notice an interesting trade-off between the linear reduction in H in the first term of the bound, showing that the algorithm takes advantage of the local gradient steps, and the quadratic increase in the second variance term also due H. the second term. Hence, the end-to-end speedup of our algorithm versus the variant with H = 1 will depend on the relationship between these two terms, which depends on the parameter values.
5

---

Under review as a conference paper at ICLR 2021
Third, importantly, the time T in this bound counts the total number of interactions. However, in practice (()) pairwise interactions will occur in parallel, as they are independent. Therefore, we can replace T by nT in the above formula, to estimate the speedup in terms of wall-clock time, obtaining a speedup of @( @(yn). At the same time, notice that this speedup is dampened in the second term by the non-trivial additional variance due to noisy local gradient steps, a fact which we will revisit in the experimental section.
Fourth, although the requirement T 2 n appears restrictive, some non-trivial dependency between and T' is necessary, as gradient information has to "mix" well in the graph before global optimiza- tion can occur. Previous work requires stronger variants of this restriction: specifically, [Lian et al. 20188) require T 2 n², while Assran et al. (2018) requires T = ((nd)).
Proof Overview. At a high level, the argument rests on two technical ideas. The first idea is to show that, due to the pairwise averaging process, and in spite of the local steps, the nodes' parameters will have to remain concentrated around their mean μtz. The second is to show that, even though stochastic gradients are taken at perturbed, noisy estimates of this mean, the impact of this noise on convergence can be bounded.
In particular, the main technical difficulty in the proof is to correctly "encode" the fact that parame- ters are well concentrated around the mean. For this, we define the potential I,, which denotes the variance of models after t interactions. Formally,
Te = Σ | 10
(6)
where fr Ei= Xi/n. We bound the expected evolution of I3 in terms of r, the degree of nodes in the interaction graph G, and A2 the second smallest eigenvalue of the Laplacian of G. For both algorithm variants we consider, our bound depends on the learning rate, number of local steps, and the bound provided by the assumption on the stochastic gradients (the bound 2 The critical point is that the upper bound on the expectation of I does not depend on the number of interactions /. Our approach leverages techniques from the analysis of static load balancing schemes, e.g. [Berenbrink] iet al. (2009). Two key elements of novelty in our case are that (1) for us the load balancing process dynamic, in the sense that loads (gradients) get continually added; (2) the load-balancing process we consider is multi-dimensional, whereas usually the literature considers simple scalar weights. The complete argument is presented in the Appendix.
This technique is quite powerful, as it allows for a number of non-trivial extensions:
Extension 1: Removing the second-moment bound and allowing for non-i.i.d. local data. In the
first extension of the algorithm, we assume that the number of local steps performed by each agent is fixed and is equal to H. In this case, we are able to remove the bounded second moment assumption, and are able to prove convergence under standard assumptions for non-i.i.d data. Specifically, in the non-i.i.d. setting, we consider that each f((x) is the local function of agent (computed over the samples available to i). We will require that 1) the function f/ L-soohhh, and that 2) for each agent: i J. is unbiased estimate of J; and that 3) for any x, ( f [x)]l²] < o². We define f(x) = >im fi(x)/n and the bound Ex [[Vxx()) VS(=)
Theorem 4.2. Let f be an non-convex, L-smooth function whose minimum x² we are trying to find Assume the local functions of agents satisfy the conditions discussed above. Let H be the number of local stochastic gradient steps performed by each agent before interacting. Define pe = 1 Xi/n, where X3 is value of model i after t
via the SwarmSGI procedure given in Algorithm
interactions. For learning rate 1)
n and T = Ω n H22 max(1, 1.2) VT
( X5
+1)²
we have that:
EJ. E T
1 VTH E[f(Ho) - f(x"|++ 376H² max(1, (o2 + 442)
(1²+1).
(12 X3 +
&
VT
Please see Appendix H for the details of the proof; we note that we did not optimize for constants.
Relative to Theorem 4.1 we have the same quadratic dependency on the number of local steps H and on L. but now the second moment bound is replaced by the variance terms. We emphasize that for non-i.i.d data under second-moment bounds, the exact same bounds as in Theorem 4.1 will hold.
Extension 2: Non-blocking averaging. Algorithm T is blocking, in that it requires both nodes to complete their local iterations at the same time before they can interact. In practice, nodes can

---

Under review as a conference paper at ICLR 2021
average their local updates without synchronizing, as follows. Each node keeps two copies of the model: the live copy X; (on which local SGD iterations are applied) and the communication copy Y, which can be accessed asynchronously by communicating nodes. When completing its local steps, node first checks if some other node averaged against its communication copy Y, since its last communication step. If the answer is yes, it simply applies its its communication model Yú. updates the live copy so that X; Y,, and proceeds with the next iteration of local computation. If no other node has averaged against its communication copy, then the node actively seeks random communication partner J. and averages its live copy against its model y, updating both to (X; + /2) The node then proceeds with the next iteration of local computation. Please see Appendix [ for the precise definition of the algorithm, and for the formal convergence guarantee for this variant.
update to
Extension 3: Quantization. For large models, the cost of the averaging step can become significant, due to bandwidth constraints. To remove the bandwidth bottleneck, we allow the averaging step to be performed with respect to quantized versions of the two models. While communication compppiittiiooooopessiion has been considered in a decentralized context before, e.g. (Tang et al.) [2018: [u and Saj 2020). our approach is different. Instead of modifying the algorithm or maintaining neighbor information at every node, we make use of a quantization scheme with some useful properties by Davies et al. (2020), which we slightly adapt to our context.
The key issue when quantizing decentralized models is that for most known quantization schemes, e.g. (Alistarh et al. 2017). the quantization error depends on the norm of the inputs: here, the inputs are models, which are not necessarily close to the origin. Thus, the quantization error at each step would depend on the norm of the models, which would break our bound on re. Instead, we observe that the quantization scheme of Davies et al. (2020) has eπror which is bounded by the distance between impuls, rather than input norms. Crucially, we show that I can in fact be used bound the distance between models, so we can bound the quantization error in terms of D3 at each step. This allows us, with some care, to generalize the analysis to the case where the models are quantized. We provide a full description and proof of convergence in Appendix G
Specifically, quantization ensures the same convergence bounds as in Theorem but with an expected communication cost of O(d + log T) bits per step By contrast, non-quantized decen- tralized algorithms assume that nodes can exchange infinite-precssion real numbers, while the only other memory-less compression scheme (Lu and Sa 2020 induces a linear dependence in d in the rate. In our applications, d >> log T, and therefore our cost is essentially constant per dimension; specifically, show that we can quantize to 8 bits per coordinate without loss of accuracy.
EXPERIMENTAL RESULTS
In this section, we validate our analysis, by applying the algorithm to training deep neural networks for image classification and machine translation. We map the algorithm onto a multi-node supercom- puting setting, in which we have large number of compute nodes, connected by fast communication links. The key overhead in this setting is synchronization: at large node counts, the cost of synchro- nizing 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. SwarmSGD mitigates this overhead, since nodes synchronize only sporadically and in pairs. Harnessing the computational power of this large-scale distributed setting still an underexplored area (Ben-Nun and Hoefter 2019).
Target System and Implementation. We run SwarmSGD the CSCS Piz Daint supercomputer, which is composed of Cray XC50 nodes, each with a Xeon E5-2690v3 CPU and an NVIDIA Tesla P100 GPU, using a ofte-offthh-art Aries interconnect over a Dragonfly network topology, which is regular. Please see (Piz, 2019) for more details. We implemented SwarmSGD in Pytorch and TensorFlow using NCCL and MPi-based primitives. Both variants implement the version with non- blocking averaging. The Pytorch implementation on top of SGP framework (Assran et al. 2018). and uses SwarmSGD to train ResNets on the CIFAR-10/100 (Krizhevsky et al.) 2014) and Ima- geNet (Russakovsky et al.) 2015) datasets, while much larger Transformer-X XL model (Vaswani et af. (017)) on the WMT17 (En-Ge) dataset. We note that all algorithms used the same topology overlay (fully-connected with random pairings), and that SGP was run with overlap factor 1, as suggested by Assran et al. (011))
the TensorFlow implementation to train
'The unusual log T' factor arises because the quantization scheme of Davies al. 2020 canfail with some prohability, which we handle as part of the analysis.
7

---

Under review as a conference paper at ICLR 2021
Model / Datasct
SGD Top-1
LB SGD Top-1
SwarmSGD
Parameters
ResNer20/ CIFAR-10
91.7% (200 epochs)
91.5% (200 epochs)
91.79% (280 epochs)
local steps
ResNet18 ImageNet
69.76 % (90 epochs)
69. 17%1 (90 epochs)
69.79% (240 epochs)
local steps
ResNet50 ImageNet
76.14 14% (90 epochs)
75.43% (90 epochs)
75.68% (240 epochs)
local steps
Parameters for full Top-1 validation accuracy on CIFAR-10 and ImageNet 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.
Table I:
Rd's
200000
SGD
Uncased BLEU soore
20
Throughpue (tokensis)
160000
Alireducc SGD
AD-PSGD
SGP
120000
WwarSSGD
local SGD (16 rodes)
10-
AD-PGGD nodes)
SwarmSGD (16 nodes)
80000
local SGD (32 nodes)
SwarmSGO (32 nodes)
-D PDD-PSGDPP nodes)
1500
Training time (minutes)
16 nódes
(a) Convergence versus Time.
(b) Throughput vs previous work. Higher is hetter.
Figure 1: Convergence and Scalability on the Transformer/WMM MM Task with multiplier =
Training Process. Our training methodology follows data- aata-parallel training, with some differences due to decentralization, and is identical to previous work on decentralized and local SGD, e.g. (Lian 2018). Training proceeds in epochs, each of which
al. 2017 Assran et al. 2018 Lin corresponds to processes collectively performing a full pass over the dataset. At the beginning of each epoch, re-shuffle the dataset and partition it among processes (Lin al. 2018).
Assran et 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 by Theorems 4. and 4.2 which predict that the slower mixing (and higher local model variance) can affect convergence. Thus, in some experiments, we will allow the decentralized schemes execute for more epochs, by constant multiplier factor between 1 and 3. Once we have fixed the number of epochs, we do not alter the other training hyperparameterss in particular, the learning rate schedule, momentum and weight decay terms identical to sequential SGD, for each individual model.
As noted previous work (Lian et al. 2017
2018
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 param- eter values recover exceed large-batch SGD accuracy (following (Goyal et al. 2017) using SwarmSGD, on the ResNe//ImageNeu/IIAA nodes CIFAR- 10. (Local batch sizes are 256 for ResNet20 and ResNet18, and 128 for ResNet50. Quantization is not applied.) The results show that Swarm can recover or slightly exceed the ac- curacy 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). How- ever, Swarm requires significant additional passes over the data (up to 2.7 x) to achieve full accuracy, which negates its performance benefits in this specific setting, relative large-batch SGD. (Please see Appendix Figure 5 for an end-to-end time comparison. We do not take the cost of fine-tuning the hyperparameters for large-bates batch SGD into account in this example.) This finding is in line with previous work on decentralized methods (Assran et al. 2018).
tasks. We execute for 32 nodes on ImageNet, and
Next, we examine accuracy for the WMT17 task. The results are provided in Figure 1(a), in accuracy-vs-time format, for 16 and 32 nodes, executing for 10 global epochs. Here, the latch-batch SGD (LB-SGD) baseline (BLEU score 26.1 I at 16 nodes) a poor alternative at high node counts: its throughput is very low, due to the size of the model (see Figure 1(b)). At 16 nodes, Swarm
8

---

Under review as a conference paper at ICLR 2021
Test accuracy (Resnet 16)
Timing analysis
20 D3500
Swamioo
24
Accurccy
Time
06-
SearmpGo local (wor65d322 2 looal steps SwarmbG2 4 local stops
04-
34 Number
Time (hrs)
(a) Convergence in time versus number of local steps for R8 on ImageNet. All variants re- cover the target accuracy, but note the lower
(b) Average time per batch for previous methods, compared to SwarmSGD, on ResNetl 8/mageNee The base value the y axis (0.4) is the average computation time per batch, values above rep- resent average communication time per batch.
convergence of variants with more local steps.
The experiment run on 32 nodes.
Figure 2: Convergence results and performance breakdown for ResNet 8/ImageNet.
slightly exceeds the baseline accuracy 26.17 BLEU, for end-to-end speedup of ~ 1.5x. In the same setting. Swarm outperforms all other decentralized methods (the fastest previous method, AD-PSGI, is 30% slower, and less accurate), both in terms of BLEU score, and in terms of end- to-end time, (The objective loss graph is similar, and is given in Appendix Figure 7 all decentralized methods reach lower scores (~ 23.5) after 10 epochs. However, we observed ex- perimentally that running Swarm for an additional 5 epochs at 32 nodes recovered BLEU score of 25.9, 30% faster than the 16-node version in terms of end-to-end time (omitted for visibility).
At 32 nodes,
In addition, we 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, corroborating the claim that individual models tend to stay close to the mean; 2) the influence of the number of local steps on accuracy: perhaps surprisingly, we were able recover baseline accuracy on ResNet1 e/mageNet for up to 4 local steps (see Figure 2(a)); 3) the impact of quantization on convergence, where we were able 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 and accuracy of SwarmSGD are superior to previous de- centralized methods (see Figure 1 for an illustration, and Figure 2(b) for a performance breakdown). In particular, a closer examination of the average batch times in Figure 2(b) shows that time per node per batch (including communication and computation) is largely constant we increase the number of nodes, which gives our method close-to-ideal scaling behaviour. This advantage relative to pre- vious schemes, notably AD-PSGD, comes mainly from the reduction in communication frequency: Swarm communicates less often, and therefore incurs lower average communication cost.
The main disadvantage of Swarm is that, similar to previous decentralized methods, it may need additional data passes in order to fully recover accuracy at high node counts. However, also note that our method did not benefit from the high level of hyperparameter tuning applied to large- SGD, e.g. (Goyal et al. 2017). We find it interesting that this accuracy issue is less prevalent in the context of large, over-paramann parameterized models, such as the Transformer, where Swarm could be a practically -iiable alternative to large-bate batch SGD within the same number of epochs.
6 CONCLUSIONS AND FUTURE WORK
We analyzed the convergence of SGD in 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 con- verges in this restrictive setting, and under considerable consistency relaxations, and moreover can still achieve speedup in terms of iteration time. Empirical results in a supercomputing environment complement and validate our analysis, showing that this method can outperform previous proposals. A natural extension would be to generalize the bounds to arbitrary communication graphs, or in terms of the assumptions on the objective, or experiment on large-scale decentralized testbeds.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Léon Bottou. Large-scale machine learning with stochastic gradient descent. In Proceedings of COMPSTAT pages 177-186. Springer, 2010.
Seide, H. Fu, G. Jasha, and D. Yu. 1-bit stochastic gradient descent and application data- parallel distributed training of speech dnns. Interspeech, 2014.
Nikko Strom. Scalable distributed dnn training using commodity gpu cloud computing. In Sixteenth Annual Conference of the International Speech Communication Association, 2015.
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. QSGD: Randomized quantization for communication--effciient stochastic gradient descent. In Proceedings of NIPS 2017, 2017.
Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Terggrad: Ternar gradients reduce communication in distributed deep learning. In Advances in Neural Information Processing Systems, pages 1508-1518, 2017.
Alham Fikri Aji and Kenneth Heafield. Sparse communication for distributed gradient descent.
arXiv preprint arXiv: 170.001744 2017.
Nikoli Dryden, Sam Ade Jacobs, Tim Moon, and Brian Van Essen. Communication quantization for data-parallel training of deep neural networks. In Proceedings of the Workshop on Machine Learming in High Performance Computing Environments, pages 1-8. IEEE Press, 2016.
Demjan Grubic, Leo Tam, Dan Alistarh, and Ce Zhang. Synchronous multi-gpu deep learning with low-precision communication: An experimental study. In EDBT, 2018.
Peter Davies, Vijaykrishna Gurunathan, Niusha Moshreñi, Saleh Ashkboos, and Dan Alistarh. Dis- tributed variance reduction with optimal communication, 2020.
Benjamin Recht, Christopher Re, Stephen Wright, and Feng Niu. Hogwild: A lock-free approach to parallelizing stochastic gradient descent. In NIPS, pages 693-701, 2011.
C. M. De Sa. C. Zhang, K. Olukotun, and C. Re. Taming the wild: A unified analysis of hogwild- style algorihms. In Advances in Neural Information Processing Systems, 2015.
John C Duchi, Sorathan Chaturapruek, and Christopher Ré. Asynchronous stochastic convex opti- mization. arXiv preprint 150.
2015.
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 arXiv: 0006100067777771 2017.
Yang You, Igor Gitman, and Boris Ginsburg. Scaling sgd batch size to 32k for imagenet training. arXiv preprint arXiv: 1etiv:1708.. 700.078888.888888 2017.
Kai Chen and Qiang Huo. Scalable training of deep learning machines by incremental block training with intra-block parallel optimization and blockwise model-update filtering. In 2016 ieee interna- tional conference on acoustics, speech and signal processing (icassp), pages 5880-5884 IEEE, 2016.
Sebastian U Stich. Local sgd converges fast and communicates little. 10X.:01805.09767 2018
arXiv preprint
Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jio Hsieh, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent. arXiv preprint arXiv: 09056, 2017.
Hanlin Tang, Ce Zhang, Shaoduo Gan, Tong Zhang, and Ji Liu. Decentralization meets quantization. 2018.
arXiv preprint
Anastasia Koloskova, Sebastian U Stich, and Martin Jaggi. Decentralized stochastic optimization and gossip algorithms with compressed communication. arXiv preprint arXiv: 90X 2019.
10

---

Under review as a conference paper at ICLR 2021
Tal Ben-Nun and Torsten Hoefler. Demystifying parallel and distributed deep learning: An in-depth concurrency analysis. ACM Computing Surveys (CSUR), 52(4):1-43, 2019.
Ji Liu and Ce Zhang. Distributed learning systems with first-order methods. Foundations and
Trends(k) in Databases, 9()):1-100, 2020. ISSN 1931-7883. doi 10.1156/1110000000 URL
http: /xxx doi.
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.
The CSCS Piz Daint supercomputer. 2019. Accessed: 2020-1-25.
http:://ww...cccc..cccooooottttt
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, łukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pages 5998-6008, 2017.
Mahmoud Assran, Nicolas Loizou, Nicolas Ballas, and Michael Rabbat. Stochastic gradient push for distributed deep learning. arXiv preprint arXiv: 2018.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference computer vision and puttern 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, al. Imagenet large scale visual recognition challenge. International Journal of Computer Vision, 115(3):211-255 2015.
John Nikolas Tsitsiklis. Problems in decentralized decision making and computation. Technical report, Massachusetts Inst of Tech Cambridge Lab for Information and Decision Systems, 1984.
David Kempe, Alin Dobra, and Johannes Gehrke. Gossip-based computation of aggregate informa- tion. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. pages 482 491. IEEE, 2003.
Lin Xiao and Stephen Boyd. Fast linear iterations for distributed averaging. Systems & Control Letters, 53(1):65-78, 2004.
Stephen Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavrat Shah. Randomized gossip al- gorithms. IEEE/ACM Trans. Netw,, (4(S1:2508-2555 June 2006. ISSN 1063-6692.
URL.ttps:://d0 .or./oorg.o....... 1109/TIT TEE//TT..006... 874516
Angelia Nedic and Asuman Ozdaglar. Distributed subgradient methods for multi-agent optimiza- tion. IEEE Transactions Automatic Control, 54(1):48, 2009.
Björn Johansson, Maben Rabi, and Mikael Johansson. A randomized incremental subgradient method for distributed optimization in networked systems. SIAM Journal on Optimization, 20 13::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.
Jianyu Wang and Gauri Joshi. Cooperative sgd: A unified framework for the design and analysis of communication-effiiene sgd algorithms. arXiv preprint arXiv: (o0:::008005555 075668 2018.
Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian U Stich. A unified theory of decentralized sgd with changing topology and local updates. arXiv preprint 1044, 2020.
John Kim, Wiliam Dally, Steve Scott, and Dennis Abts. Technology-drivent highly-scalable drag- onfly topology. In 2008 International Symposium on Computer Architecture, pages 77-88. IEEE, 2008.
11

---

Under review as a conference paper at ICLR 2021
Maciej Besta and Torsten Hoefler. Slim fly: A 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 J Fischer, and René Peralta. Computation in networks of passively mobile sinite-state sensors. Distributed computing. 18(4):235-255) 253, 2006.
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- 2745, 2015.
Petra Berenbrink, Tom Friedetzky, and Zengjian Hu. A analytical method for parallel, diffusion- type load balancing. J. Parallel Distrib. Comput., 69(1):54-61, January 2009. ISSN 0743-7315. jpdc 2008 05.
URL URLLttass//aa..ogg111...
005
Yucheng Lu and Christopher De Sa. Moniqua: Modulo quantized communication in decentralized SGD. In Proc. International Conference Machine Learning (ICML), 2020.
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 10Xiv:/908.04207, 2019.
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. http://www.cc.trrom.. edu/kriz/effar.hmm, 55, 2014.
The cifar- 10 dataset.
online:
Tao Lin, Sebastian U Stich, Kumar Kshitij Patel, and Martin Jaggi. Don't use large mini-batches, use local sgd. arXiv preprint arXiv: 07217, 2018.
Bhaskar Ghosh and S. Muthukrishnan. Dynamic load balancing by random matchings. J. Comput. Syst. Sci., 53(3)357--70,, December 1996. ISSN 0022-0000. 1o. 199006666css119900077777 URL 1996.00755
httpss///oii.org/10...0000
12

---

do assume the second moment Under review as a conference paper at ICLR 2021
A
SUMMARY OF THE APPENDIX SECTIONS
Appendix contains the following sections:
In Section B compare SwarmSGD with some of the existing algorithms. We list
vergence bounds and the assumptions needed achieve them.
In Section C provide crucial properties for the load balancing the graph.
In Section D we provide definitions for the local steps we use in the later sections.
we provide the sketch of proof of Theorem 4. which shows the conver- gence of SwarmSGD assuming the second moment bound on the gradients. Recall that the number of local steps this case a geometric random variable with mean H.
Section D
In Section F provide the proof for the non-blocking version of the swarm SGD algo- rithm. We again assume the second moment bound on the gradients and that the number of local steps is geometric random variable with mean H.
In Section G we provide the proof for the quantized version the swarm SGD algorithm. We again assume the second moment bound on the gradients and that the number of local steps is a geometric random variable with mean H.
In Section H we prove Theorem 4.2 In this bound, data is not distributed identically and the number of the local steps performed by each agent is fixed number !.
In Section we provide additional experimental results for SwarmSGI).
B COMPARISON OF RESULTS
In this section we compare convergence rates of existing algorithms, while specifying the bounds they require for convergence. In the tables T fr-corresponds to the parallel time and n is number of processes. We use the following notations for needed bounds (or assumptions):
1. o² bound on the variance of gradient.
2. M bound on the second moment of gradient.
3. d bounded dimension.
4. A2 bounded spectral gap of the averaging matrix (interaction graph in case of SwarmSGD).
5. T bounded message delay.
6. r interaction graph is r-regular.
7. bounded diameter of interaction graph.
Algorithm
Assumptions
Convergence Rate
SwarmSGD
a² X2,r M X2, a² X2, T o². A,T
0(1 (T)/TT)
SwarmSGD
O(1/ (T)
AD-PSGI Lian et al. (0188)
O(1/TTn) ((1/TT))
SGP Assran et al. (0188)
Table 2: Comparison of theoretical results in the non-convex case.
Discussion. We compare in detail against Lian al. (2018) and Assran et al. (2018), since these are the only other papers which do not require explicit global synchronization of rounds. (By contrast, e.g. [Wng and Joshi (2018); Koloskova et al. (2020) require that nodes synchronize in rounds, so that at every point in time each node has taken the same number of steps.)
the form
In Assran et (2018). all nodes perform gradient steps at each iteration, but averaging steps can be del delayed by iterations. Unfortunately, in this case the mixing time depends the dimension
13

---

Under review as a conference paper at ICLR 2021
(more precisely, it contains vd factor!), the delay bound 7, and on A, defined the number of iterations over which the interaction graph is well connected. Additionally, the analysis is not suitable for random interactions. On the other hand, Lian et al. (2018) consider random interaction matrices and do not require the agents to perform the same number of gradient steps. Unlike our model, in their case more than two nodes can interact during the averaging step.
To circumvent the global synchronization issue, Lian et al. (2018) allow agents to have outdated views during the averaging step. Yet, we would like to emphasize that they require blocking during the averaging steps, while we allow some amount of non-blocking property. By some amount means that algorithm needs blocking only in the case when some node takes more than two consec- utive iterations to complete it's local gradient steps. This means that for each node to complete Hi local steps should not more take more then ((n) global steps (since each node interacts with probability n at each step), this assumption also holds for Lian et al. (2018).
In summary, algorithm reduces the synchronization required by averaging steps, by considering pairwise interactions and by introducing local steps and providing non- blocking version of the al- gorithm as well (in SGP and AD-PSGD, agents perform one local step and one averaging step per iteration). We would like point out that we also allow a random number of local steps between in- teractions in the case when we have second moment bound on the stochastic gradient, which reduces synchronization costs even further. Finally, our algorithm requires 2 O number of iterations achieve the convergence rate of (V//VT) in the case of blocking algorithm and T 22(n)) in general. (By contrast, Lian et al. (0118 requires T = (2(n)).)
C PROPERTIES OF THE LOAD BALANCING
In this section provide the useful lemmas which will help in the later sections.
We are given a simple undirected graph G, with n nodes (for convenience we number them from to n1) and edge set E. Each node is adjacent to exactly nodes.
Each node i of graph G keeps local vector model X E IR is the number of interactions or steps); let X, = (X) .?,,..,,? X?)) be the vector of local models at step L.
An interaction (step) is defined follows: pick an edge (u, of G uniformly random and update the vector models correspondingly.
Let 14 = Ei= X//n n be the average of models at step and let r, = Ex |X -1411 be potential at time step t.
Let L be the Laplacian matrix of G and let let A2 be second smallest eigenvalue of C. For example, if G is complete graph X₂
First we state the following lemma from Ghosh and Muthukrishnan (1996): Lemma C.1.
Cv
Σ 02 =
min (M)
Now, we show that Lemma C.1 can used to lower bound Σ || X
E(WEER
Lemma C.2.
| - x
Ao
x mill A
(8)
(EE)
Proof. Observe that
Σ
|X - X =
Σ
|lx; md) - (XP - 1
(9)
(UEE
(WEE
Also, notice that Lemma have:
C.I
means that for every vector v = (V1, D2 vn such that Ei= = 0,
Σ
(c:
13)
A2
(10)
(KJEE
14

---

Under review as a conference paper at ICLR 2021
Since [x= [4] is a 0 vector, apply the above inequality the each of d components of the vectors X M4, X?? Mt...., X 14 separately, and by elementary properties of 2-norm we prove the lemma.
D DEFINITIONS FOR THE LOCAL STEPS
In this section we provide the formal definition of the local steps performed by our algorithms. Recall that X; is a local model of node at step Let H; be the number of local steps node performs in the case when it is chosen for interaction at step t 1. A natural case is for Hi to be fixed throughout the whole algorithm, that is: for each time step and node i. H; H. However, optimal choice Hi depends on whether a second moment bound on gradients (5) is assumed. Let:
(x;) =
and for 1 S 995 S H; let:
mx()) x En (x)()
Note that stochastic gradient is recomputed at each step, but we omit the superscript for simplicity, that is: (x() = (x; Σi= (X;)). Further, for 1 S s Hj let
(x;)) = E
Σ -x
[xx ()((()))
be the expected value of (x:) taken over the randomness of the stochastic gradient g. Let h; (X/) be the sum of Hi local stochastic gradients we computed:
(x:) ((()))
Similarly, for simplicity we avoid using index / in the left side of the above definition, since it is clear that if the local steps are applied to model X; compute them in the case when node i interacts is (before averaging):
step t + 1. The update step in Swarm SGD (Algorithm
H
Hi
x x; (x;) = x
((()))
x;
Σ (xx() s=0
Notice that
(X;T( =
Σ
Assumption 5
M
(11)
E ANALYSIS UNDER SECOND MOMENT BOUND AND RANDOM NUMBER OF LOCAL STEPS
In this section consider Algorithm T where for each node i, H, is a geometric random variable with mean H. We also assume gradient second moment bound (5). We provide only a sketch of the proof since the proof for the non-blocking version of algorithm in Section F is more general. If nodes and interact at step t and their local models have values of X; and X after step Their new model values become:
X X = (X: + x n (x;
Recall that μe is average of the values of models after time step and H, Σn |X -41l2 First of all we can prove that (see Lemma F.T the result can be achieved even though algorithms differ):
X2 ) + (2+
4r )n² Σ (x;)),
ETT <
ET
(12)
2rn
Xa
15

---

Under review as a conference paper at ICLR 2021
We can further show that Lemma
F.2
and therefore Lemmas F3 and R4 also hold, yielding:
40r
80r
E
S
+
)ny
12
(13)
A
and
3/n
Σ B(VS(()) 2H1.2
V (m=))
12H
(14)
Next in the similar fashion as in the proof of Theorem
F.8 we can show that
n² Σ B Vf(m),, -xx)) + 20Ln H M
27
n
E[f(H+z)) [Blf())
+
(15)
n
This allows to show that:
Theorem 4.1, Let be an non-convex, L-smooth function, whose stochastic gradients satisfy the bounded second moment assumption above. Let the number of local stochastic gradient steps per- formed by each agent upon interaction be geometric random variable with mean H. Let the learning rate we use be n -n/VT Define 1e Σi= Xi/n, where Xi is a value of model i after t interactions, be the average of the local parameters. Then, for learning rate nj = n/VTT and any number of interactions T 2 n²:
BIVS(1)1 4(f(p)) - ff(x)) 2304H² max(1, I?)M² Σ T
T-1
,2 + +1).
VTH
VT
Proof. We again skip the calculations and follow steps from the proof of Theorem (note that constants can be improved, but for simplicity we keep them the same). After applying (3) and (14.. this results in:
160r
320
M
Hn
Blf(+++)) [[]((u)] <
X
n²
76/
L2
20L H
n²
once we sum up the above inequality recall that [[((UT) f(x") )):
0 to = T and massage terms we get (additionally
T-1
4m(5(1o) - (xx)))
640r
1280
Σ t=
)mj
t
THn
X
+ 80T
+ 304TH2
get the proof of the lemma. Note that the difference between this theorem and Theorem F.8 is that have lower bound of n* for T here, instead of n² (n + 2)?. The reason is that we are not required to use Lemmas F. and F.5 since our algorithm allows blocking and this means that interacting agents do not have incomplete values for the models.
Finally since 7) n/ nT/T= (because T
> n2
F ANALYSIS OF THE NONBLOCKING VARIANT, WITH SECOND MOMENT BOUND AND RANDOM NUMBER OF LOCAL STEPS
First we define how the non-blocking property changes our interactions. Let and j be nodes which interact at step + 1, we set
Xi
X²
X
1+122
2
2
X
X
1+1/2
2
2
16

---

Under review as a conference paper at ICLR 2021
and
X Xit1/2 - (x;), X/41 X X/41/22 -n)ū((x?),
where for each node k, if pt + is the last time interacting before and including step t:
X = Xi P x 1uhx (x+, X np (x p
(16)
Intuitively the last definition means that node & has computed X
1/21 but has not finished com-
puting X2 x2 hence when some other node tries to read X pf it reads the value which missing local gradient update step. but it does not have to wait for node & to finish computing. Since p + is the last step node k interacted we have that X = X pt
More formally:
Algorithm Sequential non-blocking SwarmSGD pscudocode for each interaction between nodes i j.d
% Let G be r-regular graph.
% Sample an edge (i, j) of uniformly at random.
Require: agents and j chosen for interaction, is initiator
% choose H, and H,
% agent i performs H; local SGD steps S X; for q = to H, do X X x=>nnn'nXX (X*)
end for % agent performs H, local SGD steps S + X²
for q 1 to H, do
x'+X² n (X+)
end for To agents update their estimates
X (S + X3 X2 (X'- 5
X - S + x S2)
Notice the differences between the main algorithm and non-blocking one: first, local gradient steps applied only after the averaging steps (this corresponds term - for node i), and second, nodes get access to the model of their interacting partner, which might not be complete for the reasons described above (for example, node i is forced to use X" instead of X in its averaging step). If node i is the initiator of the interaction and its chosen interaction partner is still computing the local gradients from its previous interaction, this algorithm allows node not to wait for j to finish computation. In this case, i simply leaves its value x" in j's memory. Notice that since i is finished computation it does not need to pass its outdated model to j. but assume the worst case.
We proceed by proving the following lemma which upper bounds the expected change in potential:
Lemma F.I. For any time step t we have:
B &
E[T
A2 ) + (2
4r A
Jn²
Σ
( + Eljă, (12)
4E
2rn
Proof. First we bound change in potential A, Pe+1 F, for some fixed time step > 0.
For this, let A be the change in potential when we choose agents (i.j) E E' for interaction
nhy x o!
(While calculating A assume that X, is fixed). Let R -xf)((X)) + and Rİ
17

---

Under review as a conference paper at ICLR 2021
wh: x
- (x/) +
We have that:
2
Xi + +
i+1
+ R2.
2
X/ ++1 = Xi + x²
+ R
2
R3 Rd.
M441 = 1t +
n
This gives us that:
X M141
X; +
X?
n1
R
R
pt.
2
X/+1 - M1+1
X + X²
11
R
1
R4
Pc.
2
11
For i we get that
X r+1 - Me+1
X
-R; + R2)) pr-
Hence:
X
+
X²
11
R
R
X - 14
2
X
+
X
n
R
1
R4 14
X - me
2
11
71
1
x 1e 1²)
+
Σ
(R)
R
mell
n
2
X3 Pt
X
Pe
X
M4
X 14
2
2
2
X1
Me
+
X
Pc:
R
R
π1
71
11 1
1
1
1
R
R
R
R
n
1
71
+
2
2
14:
(R
R
b + 12/11
+
Observe that:
n
x Mt: - - + RR)) = O.
After combining the above two equations, get that:
X
1
A
X
Me +
X²
Meg Ri R²
n1 n²
R
+
n2
2
+
11 1
Ri
1
Rij
+
1
R
R
71
Cauchy-Schwarz
||
X2112
+
x
+ x
p4,,
R2.
+ R2
2
+ 2
2
1
+
(n
- 1)2
(1 12
+ 11.2212)
(17)
n2
n
n2
18

---

Under review as a conference paper at ICLR 2021
nhe (x')
x and Ri. = -x]ū vih Xx
Recall that R2; = (x;) inequality we get that
Using Cauchy-Schwarz
2
||::||1 - 21/
h4 (x;)) + z
|, (xx pi: ) 11
2
|| 1 - 2n h (X )| + l1 x 112
2
Denote 21y²
[x;(
" 1h: X
|| by S and 217² [hx || + off 11 (x);) by St. Hence
can be rewritten as:
|
1/112
A
x - M: u + x - Me: R2 + R²)
+
2
11 - 2
1
(n 1)3
(5$ + Ss
+ 2
+ nt
+
n²
n²
|
1/112
+
x
- 1 + x - Me, 1i + R²
2
+ +2( 8 + St
Further:
Young A2
Xi
u4 + X?
-eell
2r
R2 +
R2
Xt pe + Xt-
Me. Rt R²)
Sr
A2
2
2
2
2
Cauchy Schwarz
Xx -
+
A2
X - u4
4r
R
+ 4r
R2
S
4r
A2
2
2
A2
X1
Me
+ A2
X2-
4r(S) 8t
+
4r
This gives us:
|X] - -X/12
A2
x; - 14
+ A2
x² 14
Ar(S; + S
Σ A i <
Σ
4r
A2
(1,))E
+ + + 5t))
2
Lemma
A2L,
+ Σ
(2r +
2
S
+
A2
X
2
A2
4
1=1
1=1
A2
T1
4r
(2r
Str
4
A2
Next, we use the above inequality to upper bound A, in expectation:
E[Ai X1, .......... X.]
1
Σ
BAA
No. X1, .1,,...K. X.]
rn/2
(K,))E
A2Tr
n
4v A2
(2r
+
E
XI,,,
rn/2
4
i=1
ArT
Sr
E
Si X Xi, X1
+
(4
+
2rm
X
7
1=1
19

---

Under review as a conference paper at ICLR 2021
Finally, remove the conditioning:
8r
[
E| B[E[A,|X, X1, xi]l S
+ (4+
2rn
A2
By considering the definition of A, and S; we get the proof of the lemma.
Next, we upper bound the second moment of local updates, for any step t and node i: Lemma F.2
El,),((x))11 $ 2n
Proof.
3
21
Σ
El,n 17² Σ
Pr H 0
g=1
17
Pr[H] = 0
Σ 11
E (x)))1
9=1
Pr H = ujuu Σ
M v 2nm2 22.
==1
Where in the last step we used
Pr[H = u/wu = =)(())(()))
2/12 H. 2H2
This allows us to upper bound the potential in expectation for any step t. Lemma F.3.
40r
80r
[T
mny 2 H2.
(18)
A2
X
Proof. We prove by using induction. Base case 0 trivially holds. For induction step step
assume that [[[ < (40r
+
80.2
)nn 122
We get that
x
B[T [[T.(1
A2 2rn
(2
4r
11
4E hy (X;111
EliT (xx: )12)
X2
Lemma
X2
40r
}E[T]]
+ (20
+
HH2 M2n
2rn
X2
X2
40r
80r
40 M2?
<(
+
22
2 + (20
+
2rm
A2
X₂
A2
40r
80r2
)nqj
H2M
A2
X2
The next lemma allows to upper bound En_ B(V (wx), -(x) which will be used later once we apply L-smoothness to upper bound I()++1). The intuition as follows: for each i, hy (XF)) was just sum of single stochastic gradient(HI, 1) by the unbiasedness property we would have to upper bound Σ ((V)),)), - fx(()) = Σm_ (E(V)())), vf(H)) Vf(X))
El V ((()))) which can be done by using L-smoothness and then definition of T.-
20

---

Under review as a conference paper at ICLR 2021
Lemma F.4. For any time step t.
3Hn BVVS(pa) i 2
E [f(x))] 12H =
(19)
Proof.
(VVS(()))))))) -x(xx)))-((xx))
ΣΣ
Pr[H; = u Σ (((x)))
i=1 uml
Pr[Mi = w] Σ
- -
1=1 a=1
0
Pr[M = m]
Σ
(f())
Vf()) vx(x;
Σ -
1=1
Using Young's inequality upper bound B(V
V/xx)
- by
V + E V - (xx))))
Plugging this in the above incquality we
get:
Pr[H u)
Σ
( Vx(x; Σ n)((()))
3
f((+)))?
q=1
3E
3E| (
H
Σ
L X3 + Σ (X:)))
s=0
Next we use Cauchy-Schward incquality on |B||
X + (x
B(V(()) Fx())))
8
9 + 2
3E
vf(1))1
Hr[
Σ
Σ (2
q=1
Term E| E nh (1 can be upper bounded by n² M² using Cauchy-Schware and assumption Hence:
(VS())) -xxx))))
3E V sum))l
Pr[H; u) Σ (2T -;]1 22
1=1
N
3E V {
Pr[ff uju 122
-
==1
Pr[Hi = ulu(uu 1) + 1)L 12
(20)
1=1 u=1
Note that:
72
Pr[ff x)u(2221Bl1e x2(12
3IE V (4)))11
3Hn
E
(1:))
(21)
21

---

Under review as a conference paper at ICLR 2021
Also:
2
Pr Pr[H; = ulu(u + 1) + 1)223
Pr H u 12
12H
(22)
Where in the last step we used (Recall that Hi is geometric random variable with mean H):
Σ Pr[H = uiju² = (H:) = 6H 6H² + S 6H
By plugging inequalities
and
into inequality 20 get the proof of the lemma.
Our next goal is to upper bound Σ -_ ((V)())) (x;;)) Lemma E.5.
5Hn B
EVTT(m) 2H1
Bllm: -x
12
(23)
Proof. The proof is very similar to the proof of lemma F.4 except that when subtract and add term E. E (V4)) in the proof it will eventually end up with a positive sign (After using Young's
inequality it will have factor of 1 + instead of factor of 1 1) and we have Σ Bllpe X l
p
instead of r Σ Ellp 12 Thus, omit the proof in this case.
Next step is upper bound Σ BlIu x for this will need the following lemma:
Lemma F... For any node and time step t,
Ellm Mpj 11 S 10
Proof. Notice that
1-1 Σ s=f
Blile - 1
Σ 1==0
Pripi +1
Mo+1 ======
Prip = t'] (((t-t))
Us+1 M4
(24)
where we used Cauchy-Schwarz inequality in the lastt step. Fix step s. Let u and v be nodes which interact at step 1. We have that
nyu
Xu
(X,)
X ny
E Bl|ls41
1oll2
E
2n
2n
4n² E Elih (X
4n²
E
(X?))
n
n2
" n²
Ru (X py )|
n
We again used the Cauchy-Schward inequality since the expectation is taken only over the random- ness sampling and number of local steps. We can use the approach from lemma to upper bound 1i (X.))
(X)) Il2 El),,, I8) (X )l and E (X²)
(In the lemma upper bound the sum of n similar terms, but with 172.) Henee:
u4 2
Ellp Mp:l" 112 <
Pripi = ('(( -
1 pott (()E)
===
Pripi e 1/)2 2012 H22 Σ
20n² 122 M²
El 1)
n12
n²
#=0==t'
22

---

Under review as a conference paper at ICLR 2021
t př is a geometric random variable with mean n/2 (because the probability that node i interacts Et
2/n every step). Thus, [[( t) = 2 xf1)2 10n² H²?.
pl] - ./. Thus, Ellee Myp 11?
Finally we can show that:
Lemma E.7. For any node and time step t,
80r X2
160r²
Bllme =
20
+
)n²
X2
Proof. Using Sauchy-Schwart inequality we get:
Bl
X 11
<
22E Mpi 11: 2B|upt
-x2:113)
2m
80r
160r
(2 11 - Mpp 11?
2 pal) - 20mH2 +
)n²
M².
A2
A
Where the last inequality comes from Lemmas
Fi3 and F.6
Now we are ready to prove the main theorem.
Theorem F.8. Let be an non-convex, L-smooth, function satisfying assumption whose minimum
x² we are trying to find via the non-blocking version of SwarmSGD procedure (See. algorithm 2 Let the number of local stochastic gradient steps performed by each agent upon interaction be
geometric random variable with mean H. Let the learning rate we use be n n/VT. Define
Nr - Xi/n, where Xi is the value of model after interactions. Then, for learning rate
r n/vT and any T n² + 1)2:
T
E [f 4(f(po) - f(x))) 2304//² max (1, L2)M²
,2 X3
+1).
T 0=
VTH
VT
Proof. Let E, denote expectation conditioned on (Xi, X2. x By L- L-smoothness we have that
L E,ff )1 S E.) m²) + B.llleett Hell
After removing conditioning:
L (Bllut1--ii - mell. (25)
[[[()++1) = [E ([((4))))))))))))))))))))))){))) ( - (4)) +
First we look Eluc+1 mr.. If agents and j interact, (which happens with probability m//z)) We
have that pc+1 Ht (x+) (x/) + n (X
+ n
(X Hence we get that
2n
pf
2n
Ee(pe+1 Me] rn/2
1
Σ
E, Ea(-"T.(x3 (x:) 7h, (x()) 1X
T (X (x
n
E
2
Σ
Σ (x)))
n
and
2n
Me]] = E[E,
me]] =
B (X²) n2
(x ))-
n
23

---

Under review as a conference paper at ICLR 2021
Next we look at Bllpe+1 mell? If agents i and interact, (which happens with probability /4/ +
We have that pe+1 Mt - (X (x{(
xX, my ). Hence we get that
p/
2n
Bellee+1 Hell? rn/2 (t,))E
Σ E.
" (X:)
n (x?) +
7 (x())) +
" (x*)
Il
2n m/!
π
2n
Cauchy- Schwarz
AE
AL (x;,, + 4E, 1 ا
rn/2 ((J)EE
n²
1x 11
2
2
h1 (x;)11
+
2
Σ
r
[X )1
T
n2
71
n²
i=1
Lemma
16n 16m22122 M2
Σ
(x
p. 11?
n²
n
and
Bllpe+1
pell = [|ee1111++110 |ell31]
16
+
Σ
"
Bl
E
(X
p. )1
Lemma
S
F2 20n/² H²M
n²
n
n²
1=1
Hence, we can rewrite
25 as:
20 Bif(pe+1) & [[)( +
Σ
E vf(m)). (
-xx(x))
+ 7 Σ
E (VF(()))
n
n² x
20 H2M
n²
Next, we use Lemmas
F.4 and
F.5
2m
3Hn E { 12/H2
[[f(u++1] s (m))
2H
n2
+ n
2H
Σ
Elim
x
12 +
5Hn
E E| 12H -
4
4om H2M
n²
2H12'1 Σi= Bllm - xx)
4H AHLTTEET. = [[f(m]]
Hn E 4n
V (wx))
n² 36H L2
n²
H²M 20Lri²
n
n²
We use Lemmas F3 and
F7
to upper bound E[T,] and Σ Ellme - X p/
12 respectively:
160r
320r²
1/s 222 22 + n)
Hn
<
E V {(+))
A2
X
n²
76H
20 H²M²
n²
by summing the above inequality for t= 0 to 1 = - 1, we get that
T
160r
320r
17 22 +1)
nH
E[f(pr)] - f(Hu)= <
+
4n E E
A
X
t=
7611 L2 20 22
n²
24

---

Under review as a conference paper at ICLR 2021
From this get that
T-1 n BIVS(u)) S ((m)) [[f(UT)] + Σ
160r
320r²
T/ T
MPL
4n
X2
X
20
76T H6,
n²
n
Note that [[f(pr)] 2 fz=",, hence after multiplying the above inequality by nHT we get that
in
T
An(f(Ho) -((x))
640r
1280,2
B B
+
(
T
THn
A2
X
80L
304H
Observe that = n/VV < M(+ since T (n + 1)2. This allows us to finish the proof:
T
E V 4m(f(wo) - f(x*))
640r
1280,
L2
+
T
THn
A2
X
80
30
n1
n I. H2
(4f(m0) (4f(H)) f(x'))
640r
1280r
+
VTH
A
X3
VT
304H² L 80LHM2
VT
VT
4(f(mn) - 4(f())) f((x))) 2304H max(1, (
,2
+ 1).
VTH
VT
G ANALYSIS OF QUANTIZED AVERAGING, ASSUMING SECOND MOMENT BOUND AND RANDOM NUMBER OF LOCAL STEPS
First we define how quantization of models changes our interactions. Both the algorithm and the analysis in this case are similar to those of Section F t 1, we set
Let i and j be nodes which interact at step
X
X
X X
112
+
2
2
X3
Xy²
x
1+1/2 2 +
2
and
X/41 X/+1/2 - ,7,())),,
X = X2+1/2 (X?),
where for each node k, X is quantized version of the model X/. We use the quantization provided in Davies et al. (022)). The key property of this quantization scheme is summarized below:
Lemma G.1. Let g be a parameter we will fix later. the inputs x²,,, x² at nodes u and v, respectively satisfy || - x=|| < 98 e, then with probability at least 1 - log log( I|aa x²ll) O(q-a), the quantization algorithm of Davies el al. 2020 provides node v with an unbiased estimate x of x with ||2 z² I 24² 7)c, and uses O (d (1 x² ()) bits do
25

---

Under review as a conference paper at ICLR 2021
For our purposes, x" and x" are the local models of the nodes u and v and d is their dimension (we omit the time step here). In the following, we refer to the above lemma as the quantization lemma. Recall that in section E for each node k; if pt + 1 is the last time interacting before and including step
X X 2/11/2 X + (x p.
(26)
Analysis Outline. The crucial property we used in the analysis is that E(ha p2 )1 S 2H²
(see Lemma F.2 We also used that for (x*², we use the smoothness property (4) in
In our case we plan to use the quantization lemma above. For this, first notice that the estimate is unbiased: this means that E[x, = X eliminating the need to use Lemma Xi
Lemmas
F.5 and F.7
FS and subsequently F.7 since > 1-1 ( (1ee
X²') 0 in our case. Secondly if we set (q + 7)E HnMM we also satisfy Lemma F.2 This means that entire analysis can be replicated,
and even further as in the case of section E we will only need T 2 n²* (In one case we do not use Lemma F.3 at all, and in the second case upper bound can be replaced by 0, which is the same as
not using it). Now we concentrate on calculating the probability that ||I0 - x=Il || S ga" (which we call the distance criterion) required by the quantization lemma to hold over T steps and each pair of nodes. We also need to calculate the probability with which we fail to decode.
Assume that Lemma Lemma F we omit the proof since it will be exactly the same given that the conditions we discuss above hold). That is: ETT.]
holds for step
in the proof of this lemma will use induction and
40r X
80م2
>mn 1
X
Notice that for a pair of nodes u and v, ||x1- - X S 2I, (Using Cauchy-Schwarz), Hence we need calculate the probability that T, (9" d e)2/2. Using Markov's inequality, the probability of this happening is at most:
[T.
80r
160r
nlq² + +7
80r A2
160r X
n(q² + +7
(g 6)2
A2
X
(9at c)2
(g9²)2
We set q= 2+ this means that (g²")2 2 27 So given that T 2 n²", we have that Pr[T, 2 (q*') e)2/2] < O(1/T*) (note that r n 1 and A2 ((1/n2) since our graph is connected). Hence the distance criterion is satisfied with probability 1 - O(1/T²). Given that it is satisfied, we also have failure probability log ( - x/ 0gg O log ( T
So, the total probability of failure, either due to contravening the distance criterion by probabilistic failure, is at most O 2). Hence with probability - ((1/T22 we can use Lemma F.1 and prove that
40r
80r
B[T++]] S
+
nn 222
A/2
X
What is left is to union bound over T steps and we get that with probability 1 - 0(IT)) =
1 - O(1/n*) the quantization algorithm never fails and the distance criterion is always satisfied. The total number of bits used per step is Odd q) = O(d + log
With this we can state the main theorem:
Theorem G.2. Let be an non-convex, L-smooth function, whose stochastic gradients satisfy the bounded second moment assumption above. Consider the quantized version of the algorithm [ Let the number of local stochastic gradient steps performed by each agent upon interaction be geometric random variable with mean H. Let the learning rate we use be b = =n/V.. Define ps= = - where X is value of model i after t interactions, be the average of the local parameters. Then, for learning rate n n and any number of interactions T 2 n², with probability at least
we have that:
T 1 EIVS(P)) 4(F(Ho) f(x))) + /TH
2304H max L2)M2
(12
(1=+1). X3
VT
and additionally we use O(d + log T) communication bits per step.
NNote that we do not need to union bound over all pairs of and since can assume that and u are the ones which interact step f+1
26

---

Under review as a conference paper at ICLR 2021
H FIXED NUMBER OF LOCAL STEPS WITH VARIANCE BOUND AND NON-IDENTICALLY DISTRIBUTED DATA
We again deal with non-convex L-smooth function, but we no longer require a second moment bound, and no longer assume that data is distributed identically.
We use a constant learning rate 1y and fixed local steps sizes Hi = H, for each node and step I. Each agent i has access to local function fi such that:
1. For each agent i, the gradient V (z) is L-Lipschitz continuous for some > 0, i.e. for all x;, y E Rd.
[V - ((((vll - L||=
yyl-
(27)
2. for every a E Rd:
A(z)/n=((a)
(28)
3. For each agent and x E Rd:
(29)
4. For each agent and x E Rd there exist 0² such that:
[l] V f((x)]1 < 0².
(30)
5. For each x Rd there exist o² such that:
(V((z)- - Vf(x)| S spp Σ
(31)
Notice that since data is not distributed identically, for 1 1 S H, we no longer have that
- = = (x; (x))) Σ (x:))
Instead,
Σ -
Σ nhe (Xi)).
We proceed by proving the following lemma which upper bounds the expected change in potential: Lemma H.l. For any time step t, we have;
A2
8r
E
E[T++1] S (1
ET +
(2
+
2rn
A2
Proof. First we bound change in potential A, = T2+1 - T2 for some fixed time step >> 0.
For this, let A be the change in potential when we choose agents (i,j) E E. for interaction.
We have that:
X/41 = (X) (X
X/41 = (,
M4+1 = p4 + +
This gives us that:
X 14+1
X + x
+
2
11 (X:)
--2n
n n-
1/h (X:) p4.
2n
2n
X 14++1
X X
+
2
(X:)
-
111((X)) 14--
2n
2n
27

---

Under review as a conference paper at ICLR 2021
For h + H.j we get that
X Me+1 = X² - 1 (x)) + ,x²))x))) mc.
Hence:
A = |xx + x/)/2+ +
n- (x,,( + (x(() 1e| 1 xi M4
2n
+ |xt + +x/)/2+
n
(x/x(x))) + (x²)) - me|
| - m4
2n
Σ (1x²
(nx((())) + nh, (x?)) - mell - -| - mel 10ll²)
1
+
n
2
X3 14
X²
Mt
2
x: 44
2
-1 x7
-||x - 44 1|
2
2
2 Th. (X:) + 2n nx,(xx))
+ +2 X 14
+ X²- 14,
2n
+ 2(
11 2
11lmm, + nh, (X/ )
2n
2 x - M1: 1
+ n (1))))
+
1 (x)) + (X²))1
+
Observe that:
1 (nx,(x))) (x²))) -. n
x pt:
After combining the above two equations, we get that:
XX
X2112
+ Xxi - ue + Xx - ne, (x.)) + -x
2
+ (2( 12 12m + (n - -) (m-2)) |17T, nT,,
2n
Cauchy-Schwarz 5
1 - X2112
+ (x: 1h + x - Me 1 + (x
2
+ +2 2( 12 2= + (n - 22) (IT77
2n
|x - X/112
+ Xx: - + xi - Mc:
+ +x,,,,,)) (x/))
2
+ (1x6, + (x
This gives us:
28

---

Under review as a conference paper at ICLR 2021
|X
x/11?
Σ A S
Σ
+ x2 -
+4+ + X2 - Me, (x;) + (x,))
14
2
(N))
(b,))E
|x,,( + =1(7)((2))P))
+
Lemma
A²T
[lnn;((;)))
2
1=1
+
Σ
Xi
Mr + X Me: (x;) + (xx))xxxxxxxxxx(
(NJ)E
Young
A2I2
S
+
(X:))²
2
1=1
X2
Xi
Me
Xi - mell2
2r
(is (x{)
+
Σ
+
8r
22
(,,))E
Cauchy- Schwarz
A2D
I
+
rlnn (X;))
2
i=1
X2
Xi-
Me
+ X2
4r
(WEE
1
4r
+ 4r
A2
12
Xi ue
A2T
2
4
1=1
4r
A2
Next, we use definition I':
Σ
Agl't
4r2
(x)
(32)
(UJ)E
Next, we use the above inequality to upper bound A, in expectation:
E E/Ae|Xo, XI...., X1]
Σ
EAA
Xo.
X,.
rn/2
(1))
A
2
(x;1( XI, Xi,.., x.))
rn/2
X2
XaT'
8r
E
[|x,
Xo, XI,.... X2
(2 +
n
2rn
A2
Finally, we remove the conditioning:
8r )r)
E (x)) 12 2
E E EE XI, ..., X.I] <
(2
2rn
n
By considering the definition of A,, we get the proof of the lemma.
29

---

Under review as a conference paper at ICLR 2021
Lemma H.2. For any S q H and step t, we have that
a
"
9-1
E - 2T. Σ
21
Σ
h (x:)11
Proof.
B Bi - (xx)1 Σ BlV - V
Σ
(x:)))
B X X
Cauchy- Sacny-SSehl Schwerz n
2L 2 - pell2 + Σ 2 | Σ (X(x1
9-
= 22 + Σ 2
Σ (2
s=0
Lemma H.3. For any S q S H and step T, we have that
E (()(()))) S no² + 4np²
20 Σ
+ 16L 16L
(x)))) + 4m Σ /x(x))/ml1.
1=1
s=0
Proof.
E B - E The
E
(X)) & E 00² (EIN(( = no? +
1=1
1=1
no² 2
+
E
Vfi(X - - v)((m)) + vA(m)) v)(m)) + Σ ff(pd/nn
V Σ n Σ
V Σ nTz((x
1=1
j=1
==0
Sehwwars
n
n
no²
4E V (m.) 10(x))11 4mE1
(V)(()) n((x1))/m112
+ 4nE
hy (x)))/111l +4
VV((m) vf(Me)11
==1
Saauchy-Schurre
31
<
no
2 + 4np²
(ee) - xx(x))11 +4E|| Σ hx( /nl
Lemma
2 2 + Amp² + 161.
Σ 16L
>
T1(x))1+++ 4nB Σ /xxx)/
Next the above lemma to show the upper bound for Σ# Σi= (x;
30

---

Under review as a conference paper at ICLR 2021
Lemma H.4. For 7) S 6LH we have that
n
E BX) S 2Hn(o2 + 4p²) 32HLL
8n
E
1 (x:)/1111
9=1
Proof.
Notice that if S 6T.H the Lemma H.3 gives that
[1 2 nn(o² + 4p²) + 16L B[T]]
(33)
Σ
E Σ
(xx)) 4nE Σ
M mx)))/|l|
2H
En(o² + + + 167 2 + Σ
B
(x;)(
+ 4mL Σ
(x()))/
2H1
1=1
i=1
S _n(o² + + + 161 +
>
/8(x))/n13
(34)
2H
1=1
5=0
For S 9 H,
Rg
(x))11
2=1
Observe that the inequality 33 can be rewritten as:
Rg Ry S
2H Rg - n(o² 4p²) 16L + 4nlBI Σ
1
nx(x))/nl13
2=1
which is the same as
Rg S (1 2H
1 + + 4p²) 16L 16L3E[[]] 4nl Σ /xxx))/1l13
By unrolling the recursion we get that
H-1
RH <
Σ (1+ +
1a (n(02 + +
4nE| Σ
1 (x:)//111)
2H
q=0
1=1
Since,
(1+ 2H
H - (e = <2 22
we have that
H
H
Rg = EE <
Σ
nn022 + 4p²) + 16 + 4nE Σ (g(((t//ll)))
g=1mm
2Hn(o² 4p²) 32HHLEET.++ 8n
\xxx))/
9=1
Next derive the upper bound for ΣT E.I: Lemma H.5. For 17 S
we have that
10HL 2r
BTT <
8nrn (0² + H 2T
(2 +
8r
+
32nrn 2
H
8r
Σ
H
EE
Σ
(x(x)/n113
A
A2
A2
A2
31

---

Under review as a conference paper at ICLR 2021
Proof. By Lemma H.1
get that:
H
A2
8r
B[T S (1
]
+
(2
+
2rn
22
i=1
Lemma 114
A2 EE[T
2rn
H
11
(2 +
8r,
(2Hn(o² + + 8n Σ
E
1 ((x))/ml1²)
n
X2
q=1
i=1
A2
8r
32H 22
8r
(1
|[ + 2nj (o² + 4p²) (2
(2
2rn
A2
22
H
8r
+ 81j 2 H2
E
Notice that for v <
we can rewrite the above inequality as
12 / /
H
A2
E[T,] + +27 + 4p H (2+ 8r ) 80
B[T++1] S (1
H2
E
(x;))
4nr
X2
X2
i=1
since
Di=o (1
De )a <
we get that:
Anr
1-(1- 22
A2
H
Anr
8r
4r
B[T <
2(12² + +40²) 2
(2
H
+
E
k((x))/ll)
A2
A2
A2
t=0
q=1
S + H
8r
32nrn 2H H
8r
T
H
(2 A2
+
+
(2
E
A2
A2
A2
Now, we are ready to prove the following theorem:
Theorem 4.2 Let I be an non-convex, L-smooth function whose minimum x² we are trying to find the SwarmSGD procedure given in Algorithm 7 Let local functions of agents satisfy conditions 427. (28 (29. (30) and (37). Let H be the number of local stochastic gradient steps performed E. Xi/n, where X is a value of model after
by each agent upon interaction. Define Mt
interactions. For learning rate
n. and T 2 57600m H² (1,) + 112 we have that: VT
Σ IT- -T-'EISS(PO)P T
1 Blf(po) - f(2z)] + 376H² max(1, (² + 4p²) VTH
72
+ 1).
VT
X
Proof. Let E, denote expectation conditioned on (Xt, X X2:.., ..., X.). By L-smoothness we have that
Ee[[(He+ _ f(r) E. P++ - me) + + Bellee+1 - 1=l
(35)
First we look at E. [2r+111 - me.. If agaentss i and j interact (which happens with probability rn/2 ). we
have that pC+1 - (xt) (x/)))) Hence we get:
El/H+11 1e] =
Σ
E. (T
(x,(x/1] 2 71
Σ
E. 2h (X
rn/2
n
n
n
(E,))E
1=1
2n
21
E, The (x:)
n 1=1
n
32

---

Under review as a conference paper at ICLR 2021
Using the above inequality we have:
H
By (V)))) Mu+1 - 14)) = (VS(M)) Belu+1 mel) = (VS(M)))
2n
Σ>
Σ R2 [x(
n
1= q=1
11
[BrlV[((+)) Σ - R+ll Σ
A (x(()1/111)
71
28
E2
Vfi(m))) 1((x3))mmll -VV/000) - B.ll
M (xx))
1
V((u)) - -,0000) (8 Eyll > /xx:)//1ll))
71 9=1
Here we used Cauchy-Schwarc inequality at the last step. Next we look at Eellpe+1 - If i and j interact, (which happens with probability mn/2). We have that M4+11 Me (X;)
5h,(Xg (XF). Hence get that
Bellet41 - 1
Σ
Ee (x:))
"h (x,)) ||
rn/2
n
n
(id)EE
Cauchy- Sounhyy-Snne Schwarz
1
2 2E, (
2E,1l "n (x?)))
rn/2
n
n
(NJ)E
2 12
211 2
Cauchy Schwars
4 H
H
(X:))
71
n2
So, we can rewrite (35) as:
E.[[(pet)]] S S11)) + ! Σ
Ee || Σ V)())) (x
9=1
||f E,ll Σ /((x3t/mll²)
2Ta2H H
n
H
E, (
n
1=1
33

---

Under review as a conference paper at ICLR 2021
Next, we remove conditioning: [[f()++1) = ((4-)i)
- H
S <BIf(He)] +
V f.(e)) - (X))1
[[ - E Σ kg(x:)/mlP))
2 1
(X))I
3
h
Lemma
B[s(ma)] + 7 Σ
(2 B[. + Σ
2
Σ
(x))1
1=1
.=0
Bl V[(+))] B1| >
h (x()) /mll²)
" H
n
i=1 q=1
Lemma H.
2
BI| Hn B|| V V (wm)ll
Blf(we)] +
[E[T.]
n²
n
(2Hn(o²+ + 4p²) 32.1, + 8n
EE|
1 (xx3)//ll3)
n²
9=1
2
2Hn + + 32H 8n
E
h ,x(x3)/mll
H
7
E
M(x)//1112
Next we choose 17 oz. and 1 SOLH so that 16L3,² S a and 16IHH? < 2. This together with x
n2 the above inequalities allows us to derive the following upper bound for [[f( (we eliminate terms with positive multiplicative factor E| Σ h2 (x))///nll3):
5n
Bif( )] S ([)(H))) + 21L²H H
B[T.] 11 E()
n²
21,2m1
(2Hn(o²² + +4p² 32H L
n²
2T,
(2Hn(02 + + + 32HL'ETT.))
n
3m
E
(x(:))/ll
5n
We proceed by summing up the above inequality for 5 T 1:
4L" + 40²)T
41 + +42)1
Blf( < Σ B[((He)]
n
n²
2nL2111 11
T
64L E +
64L 12
E
Σ ETd
n²
n²
2
T
31
H
H
M((x))
E (144)1
(36)
5m
1=1
1=1
34

---

Under review as a conference paper at ICLR 2021
Next use Lemma H.5
2 2 H
T-1
64L*H1 T-1
H42 T-1
E +
B[T,]+ +
n²
n²
n
1-
00
2 H
(8arn + 4 HT²T
8r
(2 +
n²
22
X2
32nrn 2 H
8r
T-1
(2+
E1
h (xxx)//lll
A2
1=1 q=1
i=1
64L Hnp
8nri) + +40²) + H
8r
(2+
n
X2
X2
32nrT²
8r (2+
T-1
n
Σ Σ
h
n((x:)/mlll
A2
A2
q=1
QAI.322p
8
+ 4 + H2T
8r 22
+
(2 +
3
A2
32mr7 2
8r
T-1
EE Σ /
(2
A2
X2
t=1
By choosing
"
<
18HLL22//2+55-11X
122 and
7
22
1/3
we can eliminate terms with the multiplicative factor
H
E
E
1
(x))) in the inequality (36)
T-1 nH [[f(H(] - Σ 1=1
B[f(p++1] S
E V 1
1=
4L 4p²)T
4LH2 + 4
n²
16 2 + 4p²)
(2r/)2 +8r² 3/²//2)
n
7, (a2 4p2)
(2r/>2 + 802/13)
π
4 + 41²
(2r A2 + 88/2 8/2//2))
n²
After rearranging terms and dividing by yT' we get that
E
+ 4LHnno²2 + Ap2)
< "
7TH - ((a)
T
+ 11
+ 10 (2r))) +8/2/13
512"11370'00 40²)
2r 22 + 873/13)
35

---

Under review as a conference paper at ICLR 2021
Next 77 S 1/n and 17 aHT.
E E V (1+))
4T,3//022 + 4p2)
4T.Hn(0² + 4p2)
v 7TH
B[f(Ho) - [(m)]] +
T
7
n
16n HT? + 4p²) n
(2r/)2 4r² /22)
3841,4 H2 (0² + 4p²)
(2r/12 + 8r 123)
384L 11 1200 +
(2r A2 + 8/2/12)
4L2 + 4p²) n
4LHn(o² + 4p²)
B()()) [(re]]
rHH
16 (0² + 4p²)
(2r/ A2 81 112)
n
15L3 4p²))
(2r /2 + 8/
n
15LH/00
+
(2r/)2 + +8/2113)
n1
Recall that 17 =
n to get:
vT
ET- V f(1)11
Elf(Ho) - f(H)] + (0 + 402
(LH + +
<
T
VTH
VT
VT
161. (0 + 4p2))
(2r/>2 + 8/2/12)
VT
102 + 4p²)
15LHO²
(2r/>2 + 8/2
(2r/A2 + 8///22)
VT
VT
VTH E[f(Ho) - f(m)]] + 376H2 max(1 1, (2) + +4p²)
+1)
VT
VTH E[S(HO) [(x))] + 376/12 max 1, L2) L²) + 4p²)
+ 1).
VT
where in the last step we used f(n) 2 f(x*). Notice that all assumptions and upper bounds on 7) are satisfied if
1
S 240nH max 1) +1)
(37)
which is true
22
T 57600n 112 max 2
+1
(38)
X2
I ADDITIONAL EXPERIMENTAL RESULTS
We validated our analysis, by applying the algorithm to training deep neural networks for image classification and machine translation.
Target System and Implementation. We run SwarmSGD on the CSCS Piz Daint supercomputer, which is composed of Cray XC50 nodes, each with a Xeon E5-2690y3 CPU and an NVIDIA Tesla P100 GPU, using state-of-the-art Aries interconnect. Please (Piz 2019) for hardware details.
36

---

Under review as a conference paper at ICLR 2021
Test accuracy (Resnet50)
Test acruracy (Reenet 18)
Accurcty 060
26
Assurarry (54)
Swarddd 1 iecr stess
SwarddDD 2 sca stees
12-
buceline
Targer
20000
oriice
Stops
(a) Convergence of ResNer50/lmageeet versus number of gradient steps. SwarmSGD is able to recover the baseline top accuracy.
(b) Convergence versus number of local steps for ResNet18 on ImageNet. All variants recover the target accuracy, but we note the lower convergence of variants with more local steps.
Figure 3: Additional convergence results for ImageNet dataset.
We implemented SwarmSGD Pytorch and TensorFlow using NCCL/MPI respectively. Basically, each node implements a computation thread, and communication thread, each of which stores a copy of the model. The "live" copy. which being updated with gradients, stored by the computation thread. Periodically, the threads synchronize their two models. When interacting, the two nodes exchange model information via their communication threads. Our implementation closely follows the non-blocking Swarm algorithm description.
We used Swa to train ResNets the classic CIFAR-10//maceh datasets, and Trans- former Vaswani et al. (2017) on the WMT17 dataset (English- -ereis. The code will be made available upon publication.
Hyperparameters. The only additional hyperparameter is the total number of epochs we execute for. Once have fixed the number of epochs, do not alter the other training hyperparameters: in particular, the learning rate schedule, momentum and weight decay terms are identical to sequen- tial SGD, for each individual model. Practically, if sequential SGD) trains ResNet1 8 in 90 epochs, decreasing the learning rate 30 and 60 epochs, then SwarmSGD with nodes and multiplier would 90 x 2/32 ~ 5.6 epochs per node, decreasing the learning rate at 2 and 4 epochs.
Specifically, for the ImageNet experiments, we used the following hyper- parem-parameeess. For ResNet18 and ResNet50, we ran for 240 total parallel epochs using 32 parallel nodes. The first communicated every 3 local steps, whereas the second communicated every local steps. We used the same hyper- parameters (initial learning rate 0. annealed at 1/3 and 2/3 through training, and standard weight- decay and momentum parameters).
For the WMT17 experiments, we ran standard Transformer-ae model, and executed for 10 global epochs at 16, 32, and 64 nodes. We ran a version with multiplier 1 (i.e. 10/NUM_NODES epochs per model) and with multiplier 1.5 (i.e. 15/NUM NODES epochs per model) and regis- tered the BLEU score for each.
Baselines. We consider the following baselines:
Data-parallel SGD:
Here, consider both the small-batch (strong scaling) version, which executes a global batch size of 256 on ImageNet/CIFAR experiments, and the large- batch (weak-scaling) baseline, which maximizes the batch per GPU. For the latter version, the learning rate is tuned following Goyal et al. (2017).
Local SGD: Stich 2018); Lin al. 2018)) We follow the implementation of Lin et al.
(2018), communicating globally every SGD steps (which was the highest setting which provided good accuracy the WMT task).
Previous decentralized proposals: We experimented also with D-PSGD Lian et al. (2017), AD-PSGD Lian et al. (2018), and SGP Assran et al. (2018). Due to computational constraints, we did not always measure their end-to-end accuracy. Our method matches the sequential large-batch accuracy for the models we consider within 1%. We note that the
37

---

Under review as a conference paper at ICLR 2021
best performing alternative (AD-PSGD) is known to drop accuracy relative to the baselines, e.g. (Assran et al., 2018).
Results.
The accuracy results for ImageNet experiments are given in Table | and Figures (3a)
and B(b)
As is standard, we follow Top-1 validation accuracy versus number of steps.
Timing analysis
SGP
AD-SCD
-8" Snar1502
044-
04
Figure 4: Average time per batch for previous methods, compared to SwarmSGD, on ResNet18/ImageNee across 1000 repetitions with warm-up. Notice that 1) the time per batch of SwarmSGD stays constant relative to the number of nodes; 2) it is lower than any other method. This is due to the reduced communication frequency. Importantly, the base value the y axis of this graph (0.4) is the average computation time per batch. Thus, everything above 0.4 represents the average communication time for this model.
Test accuracy (Resnet 18)
Accunayy Noa
SAamORE 2 kexl dagn SCD Bundin:
Time thrst
Figure 5: Convergence versus time for ResNet 8/Imagenet for the SGD baseline vs Swarm, execut- ing 32 nodes. We note that Swarm iterates for 2.7x more epochs for convergence, which explains the similar runtime despite the better scalability of Swarm.
Communication cost. We now look deeper into SwarmSGD's performance. For this, we examine in Figure 4 the average time per batch of different methods when executed on our testbed. The base value on the y axis (0.4s) exactly the average time per batch, which the same across all methods. Thus, the extra values on the y axis equate roughly to the communication cost of each algorithm. The results suggest that the communication cost be up to twice the batch cost (SGP and D-PSGD). Moreover, this cost is increasing when considered relative to the number of workers (X axis), for all methods except SwarmSGD.
This reduced cost is justified simply because our method reduces communication frequency: it com- municates less often, and therefore the average cost of communication at a step is lower. We can therefore conclude that our method is scalable, in the sense that its communication cost remains constant relative to the total size of the system. Figure (3b) shows the convergence versus time for ResNet18 on the ImageNet dataset, at 32 nodes, with local steps per node, and epochs per model.
Convergence versus Steps and Epochs. Figure & shows and discusses the results of additional ablation studies with respect to the number of nodes/processes and number of local steps / total epochs on the CIFAR-10 dataset / ResNet20 model. In brief, the results show that the method still
38

---

Under review as a conference paper at ICLR 2021
15 Canwergence
Convergence results
Eyeeoue M01
15rpecs
Spata
(a) Convergence model) for CIFAR-I0/ReSNr120 at node counts between and 256. We note that algorithm converges and recovers SGD accuracy (91.35% Top-1) for all node counts, although there are oscillations at high node counts.
number epochs (per
(b) Accuracy versus local epochs and local steps for CIFAR- N0/Res The original schedule for this model
epochs, and this experiment executed on 8 nodes. the convergence scaling were perfect, 300/8 = 37.5 epochs would have been sufficient to converge. However, in this case we need an epoch mul- tiplier of 2, leading to 75 epochs to recover full accu- racy (which in this case 91.35%
Figure 6: Additional convergence results for CIFAR-10 dataset, versus number of nodes (left), and local steps (right).
10.0
Loss
local SGD (16 nodes] 5warmSG
AD DDDD (16 nodes)
2.5
500
1000
1500
Training time (minutes)
Figure 7: Objective loss versus time for the Transformer-XL/WWTT experiime..... for various methods, executing at 16 nodes.
preserves convergence even very high node counts (256), and suggest a strong correlation between accuracy and the number of epochs executed per model. The number of local steps executed also impacts accuracy, but to much lesser degree.
Quantization. Finally, we show convergence and speedup for WideResNet-28 model with width factor 2. trained on the CIFAR-10 dataset. We that the epoch multiplier factor in this setup is 1, i.e. Swarm (and its quantized variant) execute exactly the same number of epochs as the baseline. Notice that the quantized variant provides approximately 10% speedup in this case, for 0.3% drop in Top-1 accuracy.
39

---

Under review as a conference paper at ICLR 2021
Canargenca Excors de Rishld 28 Dlaan))
Contrgaran arra Time Mik Rachel 28 Clartts
Cumtioi 2-1
(a) Convergence versus number of steps for the quan- tized variant.
(b) Convergence versus time
Figure 8: Convergence results for quantized 2xResNet28 trained on the CIFAR-10 dataset, versus iterations (left), and time (right).
40


Reviews:
[{"review_id": "weinGFmrdW0", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "# Contributions:\n1. This paper analyzes the convergence of decentralized SGD with asynchronous updates, quantization and local updates, which is novel and challenging.\n\n2. The proposed algorithm requires significantly less communications to converge.\n\n3. The authors have done extensive analysis of the convergence under different settings with detailed proofs.\n\n4. The authors have done some large-scale experiments and show their algorithm performs great in practice.\n\n\n# Strong points:\n\n1. The authors have done concrete non-trivial analysis.\n\n2. The algorithm is very general, several existing algorithms can be its special cases by different choice of parameters.\n\n3. The experiment section provides a large amount of empirical evidence.\n\n\n# Weak points:\n\n1. Assumptions are too strong for Theorem 4.1 and 4.2: \n\n\t- Assuming each node can sample from global data is too strong. Section I removes this assumption but without highlighting key steps.\n\n\t- Step size requires the knowledge of the number of total steps.\n\n\t- Number of total steps needs to be larger than $n^4$. Even nodes don't communicate, the algorithm should still converge because the global sampling.\n\n2. The benefit of local steps is not clear. For example, if we optimize the convergence rate in Theorem 4.1 over $H$, the best choice is $H = \\Big(\\frac{\\lambda_2^2}{r^2} \\cdot \\frac{f(\\mu_0) - f^*}{L^2 M^2} \\Big)^{1/3}$. That is, the optimal $H$ is smaller when $r$ is larger.\n\n3. The $H^2$ term in Theorem 4.1 and 4.2 may not be good enough. If set $H \\to \\infty$, then this bound should reduce to the single-machine SGD. However, the $H^2$ term will go to $\\infty$.\n4. Theorem 4.2 requires $T \\sim O(*)$. Does it work if $T$ is greater?\n\n\n5. Definition of $T$ is confusing.\n\n6. Arguments for acceleration is not convincing. The algorithm only have one pair of nodes communicate, it's not clear how to replace $T$ with $nT$.\n\n\n# Recommendation: \n\nWeak reject. As of the current version, the proofs need to be improved. However, I believe the authors can improve in the next version.\n\n\n\n# Further questions:\n\n1. Is it possible to merge Section I with Theorem 4.1 or show the proof? I think there will be one term that depends on $\\rho^2$. When $\\rho^2 = 0$, Section I will reduce to Theorem 4.1.\n\n2. Lemma F.3 is confusing. I think $\\Gamma_t$ should decrease with $t$, or use diminishing step size $\\eta_t$ to control this term. Then there's no need to set $\\eta \\sim \\frac{1}{\\sqrt{T}}$.\n\n3. Can you also show the run time plot for ResNet?\n\n\n# Optional improvements:\n\n 1. It may be better to remove some small terms to make rate more clearer. For example,\n\t - For Theorem 4.1, use $1 \\leq \\frac{r^2}{\\lambda_2^2}$ can get rid of the constant $1$.\n\t - For (14) and (19), use $\\frac{r}{\\lambda_2} \\leq \\frac{r^2}{\\lambda_2^2}$ to get rid of the first order term.\n\n2. The 3rd equation in Section D, $\\tilde h_i^s$ also depends on $\\tilde g_i$, which is not reflected.\n\n3. The 1st equation in Section E has an extra '-'.\n\n4. Is the coefficient $\\frac{n - 2}{n}# in Eq (18) missing?\n\n# Update\n\nThanks for the authors to address my questions. However, if the analysis can not explain why more local updates can reduce communications, I would not recommend to accept.", "extra_scores": {}, "extra_text": {}}, {"review_id": "mp_d1DhkyYe", "reviewer": "AnonReviewer1", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper considers several techniques to minimize decentralized cost for training neural network models via stochastic gradient descent (SGD). These techniques include asynchronization, local updates, and quantized communication. Theoretical convergence analyses are provided, and numerical experiments are shown. \n\nStrength:\n\n- The provided convergence rate is well-separated and well-explained, though the reviewer did not check the correctness of all the proofs. \n- Combining these techniques into decentralized SGD is new to the best of the reviewer's knowledge. \n\nWeakness:\n\n- The number of graphs satisfying the property is very limited. It requires an r-regular graph. That is, the number of edges connected to one node is the same for all nodes. This condition is very difficult to satisfy in applications. Therefore, the application would be limited too. \n- The quantization part is limited comparing to the other two parts. What does the effect of quantization on the convergence rate and the communication cost? What is the benefit of using the quantization method in Davies et al. (2020)?\n- In the proposed algorithm, each time an edge is activated and the two nodes connected through the edge are updated. Therefore, there is still synchronization in Alg. 1. Whether is it possible to update one node based on the results from multiple connected nodes (i.e., one node is activated)? \n- Algorithm 2 is unclear. 'avg' is computed but not used. What are j' and 'i''? \n\n\n## Update\n\nThe authors' response addresses some concerns, and I would like to keep the initial scores. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "kv0J-YZvBxR", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: This paper combines the existing scaling techniques to reduce the communication cost of distributed SGD among a large number of computing nodes. These techniques include asynchronous, decentralized, or quantized communication. The authors prove that this combined algorithm converges to a local optimal point. In the experiments, this algorithm also successfully converges and scales for big data. The authors claim that this is the first work to consider decentralization, local updates, asynchrony, and quantization in conjunction. \n\nOverall, the contribution of this paper is relatively marginal. The algorithm simply combines many different existing techniques and does not lead to any substantial new development. Below are some comments and questions. \n\n(1) The first two paragraphs of the introduction look wordy. They introduced the distributed SGD problem and listed the scaling techniques as well as the relevant literature, but the meaning of these techniques is unclear. How these techniques are applied and combined is also unclear. \n\n(2) The meaning of n and T are not formally defined. \n\n(3) In Theorem 4.1, the assumption that T>=n^4 (n^4 can be very large) is the disadvantage of this algorithm because the same convergence rate O(1/sqrt(T)) has been achieved without such assumption in some distributed settings, including plain distributed SGD, federated average, etc.\n\n(4) The claim in the abstract that the new algorithm can converge to local minima is not supported, since the theorems only imply gradient convergence. \n\n(5) In the theoretical part, I did not see in which measure does this new algorithm excel the existing ones. The authors should clarify this. In the experiments, the objective function value of interest is not compared. \n\n(6) On page 2, the authors said “SwarmSGD has a Θ(n) speedup in the non-convex case, matching results from previous work which considered decentralized dynamics but which synchronize upon every SGD step.” What is the measure, is it the number of communications, local SGD iterations or gradient evaluations? “Matching results” can be interpreted as equal to the previous rate, which seems to contradict with Θ(n) speedup. Please clarify this. \n\n(7) In the contribution part, the authors mention that their new algorithm has lower average synchronization cost per iteration but more iterations in the experiments, how about the total synchronization cost?  \n\n(8) The authors use multiple variables to denote the number of nodes, including n, P and m. Please use only one. \n\n(9) The space around the section captions is too narrow. This is not suggested in general. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "9UWnXgSHY-5", "reviewer": "AnonReviewer4", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "### Summary\nThe paper proposes and analyses a distributed learning algorithm for training with Stochastic Gradient Descent a global model on a regular graph, that allows for local and asynchronous gradient updates. Nodes continuously update their local models $X^i$ by gradient descent, while they communicate with their peers (a peer at a time) and update their local model with the pair model average $\\frac{X^i + X^j}{2}$. Three extensions of the algorithm are also proposed to relax different constraints, while maintaining the convergence guarantees:\n1. synchronous updates and decentralized data: if the number of local gradient updates $H_i$ before an edge update is constant, convergence guarantees hold for decentralized data, as long as partitions are i.i.d. from the original distribution;\n1. asynchronous updates: the number of local gradient updates $H_i$ can vary between nodes and between every edge update;\n3. reduced communication: model exchanges can be quantized to reduce communication complexity.\nExperiments in the distributed setting are carried out for image classification and speech recognition, showing that the algorithm is generally able to achieve performance comparable to a model trained in the centralized setting at increased execution time, but faster than state-of-the-art distributed SGD methods.\n\n### Significance and clarity\nContributions are significant and novel, to the best of my knowledge. They consider several settings, which are all theoretically founded. However, the paper is generally hard to follow, also because it has many contributions that are cited in the main text but deferred to the appendix. Still, it would help to clarify the following points from the beginning:\n1. what the authors mean by decentralized, later explained as decentralized model updates, but centralized/distributed data for the experiments;\n2. define $T$ (global number of edge updates) and $H$ (number of local updates in between edge communication);\n3. where and when quantization is applied and why it helps in reducing communication complexity in the main text.\n\n### Remarks on theoretical analysis\nTheorem 4.1 shows that the average second moment of the loss gradient evaluated at the average model $\\mu_t$ is bounded and decreases with $T$, proving that the model updates converge to a local minimum. This bound however stands for the average of all models obtained at each global step $t$, meaning that it is not necessarily a tight bound for the second moment of the last obtained model, which is the bound we are ultimately interested in.\nIt would be also interesting to report communication complexities, with and without quantization, and compare them to state-of-the-art methods.\n\n### UPDATE\nI thank the authors for addressing my concerns and confirm my initial rating.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviews were a bit mixed: on one hand, by combining and adapting existing techniques the authors obtained some interesting new results that seem to complement existing ones; on the other hand, there is some concern on the novelty and on the interpretation of the obtained results. Upon independent reading, the AC agrees with the reviewers that this paper's presentation can use some polishing. (The revision that the authors prepared has addressed some concerns and improved a lot compared to the original submission.) Overall, the analysis is interesting but the significance and novelty of this work require further elaboration. In the end, the PCs and AC agreed that this work is not ready for publication at ICLR yet. Please do not take this decision as an under-appreciation of your work. Rather, please use this opportunity to consider further polishing your draft according to the reviews. It is our belief that with proper revision this work can certainly be a useful addition to the field. 

Some of the critical reviews are recalled below to assist the authors' revision:

(a) The result in Theorem 4.1 needs to be contrasted with a single machine setting: do we improve the convergence rate in terms of T here? do we improve the constants in terms of L and M here? What is the advantage one can read off from Theorem 4.1, compared to a single machine implementation? How should we interpret the dependence of (optimal) H on r and lambda_2? 

(b) The justification for $T \geq n^4$ is a bit  weak and requires more thoughts: one applies distributed SGD because n is large. What happens if T does not satisfy this condition in practice, as in the experiments?

(c) Extension 1 perhaps should be more detailed as its setting is much more realistic than Theorem 1. One could use Theorem 1 to motivate and explain some high level ideas but the focus should be on Extension 1-3. In extension 2, the final bound seems to be exactly the same as in Theorem 1, except a new condition on T. Any explanations? Why asynchronous updates only require a larger number of interactions but retain the same bound? These explanations would make the obtained theoretical results more accessible and easier to interpret.
Decision: Reject