{'fraction_non_alphanumeric': 0.0381300219138057, 'fraction_numerical': 0.01522603684765847, 'mean_word_length': 4.300352748860019, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 10, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Asynchronous Decentralized SGD with Quantized and Local Updates

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


Introduction
Decentralized optimization has recently emerged as a promising approach for scaling the distributed training of machine learning models, in particular via stochastic gradient descent (SGD) [Lian et al., 2017, Tang et al., 2018, Koloskova et al., 2019a. Its key advantage is that it removes the need for a central coordinator node in distributed training, and therefore it can allow for high scaling.
The general decentralized optimization setting is the following: we are given n nodes, each with a subset of data from some distribution, which can communicate over some underlying graph topology. In each global round, each node samples some local data, performs a local gradient step, and it is paired with a neighbor, which may be chosen randomly. The nodes exchange model information pairwise, and then update their models, often via direct model averaging. Variants of this setting have been analyzed since pioneering work by Tsitsiklis [1984], for various estimation and optimization algorithms [Xiao and Boyd, 2004, Nedic and Ozdaglar, 2009, Johansson et al., 2009, Shamir and Srebro, 2014 and have seen renewed interest given its applicability to training deep neural networks (DNNs) at scale, e.g. [Lian et al., 2017, 2018, Assran et al., 2018.
Recently, there has been significant focus on reducing the synchronization overheads for decentralized training, usually employing three approaches: 1) implementing faster non-blocking communication between communication partners at a round [Lian et al., 2018, Assran et al., 2018, which may cause them to see stale versions of their models, 2) allowing nodes to take local steps in between their communication rounds [Wang andJoshi, 2018, Koloskova et al., 2020], and 3) applying quantization to the communication [Lu and De Sa, 2020, Tang et al., 2018, Koloskova et al., 2019a.
The above impressive line of work contributes a rich set of algorithmic and analytic ideas; however, one common limitation is that the algorithms are usually set in the synchronous gossip model, which requires all nodes to perform their communication in lock-step rounds, and share a common notion of time, thus reducing their practicality. To mitigate this fact, some references, e.g. [Lian et al., 2018, Assran et al., 2018, Lu and De Sa, 2020 partially relax this requirement, although they do so at the cost of additional assumptions, or reduced guarantees, as we discuss in related work. Another relative limitation is that the analyses are usually customized to the bespoke communication-reduced methods being applied, and therefore are hard to generalize to other methods.
Our Contribution. In this paper, we consider decentralized SGD-based optimization in the simpler, but harder to analyze, asynchronous gossip model [Xiao and Boyd, 2004], in which communication occurs in discrete, randomly chosen pairings among nodes, and does not require a common notion of time. We prove that a new variant of SGD we call SwarmSGD converges in this setting, even though it supports all three communication-reduction approaches mentioned above in conjunction. Our analysis generalizes to heterogeneous data distributions and communication topologies.
At a high level, SwarmSGD works as follows. Each node i maintains a local model estimate X i based on which gradients are generated, and a shared buffer where quantized models are stored for communication with other nodes. In each step, node i first computes a sequence of H local gradient steps, which it does not yet apply. Next, the node chooses communication partner j, uniformly at random among its neighbors. Then, node i reads from its own communication buffer and from the communication buffer of j, obtaining quantized models Q i and Q j . A subtlety here is that Q i is not necessarily the quantized version of the model X i , since other nodes can write concurrently to i's buffer. The node i then averages Q i with Q j , and updates the neighbor's remote buffer to the quantized average. Finally, it applies its local gradient steps to the resulting average, adopts this as its next model X i , and a writes quantized version of it in its own shared buffer. This procedure can be implemented in a deadlock-free, nonblocking manner, by using either shared-memory or the remote direct-memory access (RDMA) calls supported by MPI [Woodall et al., 2006]. Importantly, the communication partner j does not need to block its computation during communication, and may be contacted by more than one interaction partner during a single local step, although we do assume that individual reads and writes are performed atomically.
A key component of this procedure is the quantization scheme: directly using an unbiased quantizer, e.g. [Alistarh et al., 2017] would destroy convergence guarantees, as the quantization error would be proportional to the model norm, which may not be bounded. Instead, we use a customized variant of the quantization scheme of Davies et al. [2021], whose error depends on the distance between the point being quantized (the model), and an arbitrary reference point, provided as a parameter. We prove that each node can reliably use its own model as a reference point to quantize and de-quantize messages placed in its buffer by other nodes. In turn, this requires care in the analysis.
Specifically, the key observation behind our analysis is exactly in showing that the nodes' local models stay well-enough concentrated around their mean throughout optimization to allow for correct decoding of quantized models, which in turn implies joint convergence by the nodes towards a point of vanishing gradient. This concentration follows via a non-trivial super-martingale argument. If nodes take a constant number of local SGD steps between communication steps, then SwarmSGD has Θ( √ n) speedup to convergence for non2convex objectives. This matches results from previous work which considered decentralized dynamics but with global synchronization [Lian et al., 2017].
Experimental Validation. 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 confirm the intuition that the average synchronization cost of SwarmSGD per iteration is low: it stays at less than 10% of the batch computation time, and remains constant as we increase the number of nodes. For example, using SwarmSGD, we are able to train a Transformer-XL [Vaswani et al., 2017] model on WMT17 (En-Ge) 1.5× faster than a highly-optimized large-batch SGD baseline, and to slightly higher accuracy, without additional hyper-parameter tuning. At the same time, due to the reduced communication frequency, Swarm also improves upon the speed of the previous practical decentralized methods, e.g. [Lian et al., 2017, 2018, Assran et al., 2018. Importantly, we also note that, in less overparametrized settings such as training residual CNNs [He et al., 2016] on ImageNet [Russakovsky et al., 2015], nodes do need to perform more iterations over the dataset relative to the baseline in order to recover full accuracy. This is predicted by the analysis, and confirms similar findings in previous work [Assran et al., 2018]. Overall, our method does appear well-suited to training large modern models at node counts where global synchronization among all nodes is prohibitively expensive.
Related Work. Decentralized optimization has a long history [Tsitsiklis, 1984], and is related to the study of gossip algorithms, e.g. [Kempe et al., 2003, Xiao and Boyd, 2004, Boyd et al., 2006. Gossip is usually studied in one of two models [Boyd et al., 2006]: synchronous, structured in global rounds, where each node interacts with a randomly chosen neighbor, forming a matching, and asyn-chronous, where each node wakes up at random times, e.g. given by a Poisson clock, and picks a random neighbor to interact with. Several classic optimization algorithms have been analyzed in the asynchronous gossip model [Nedic and Ozdaglar, 2009, Johansson et al., 2009, Shamir and Srebro, 2014. In this paper, we focus on analyzing decentralized SGD in this model.
As mentioned, the growing line of work on decentralized optimization for machine learning has mostly focused on variants of the synchronous gossip model. Specifically, Lian et al. [2017]  Lian et al. [2018] and Assran et al. [2018] focused specifically on reducing synchronization costs in this setting, and proposed algorithms with partially non-blocking communication, in which nodes may read a stale version of the interaction partner's information, modelling e.g. a communication buffer. However, the maximum staleness must be bounded by a global variable τ , which must be enforced throughout the execution. As observed by Assran et al. [2018], enforcing this bound can cause blocking, and therefore the authors of these works propose to implement a relaxed round-based model, in which nodes interact once per round in perfect matchings. Their algorithms provide O(1/ √ T n) convergence rates, under analytical assumptions.
Upon careful examination, we find that their analysis approach can be extended to the asynchronous gossip model we consider, by defining the "contact matrices" to correspond to pairwise interactions. However, this introduces two significant limitations. First, the analysis will not support local gradient updates to models nor quantized communication. If we remove these practical relaxations, our technique yields better bounds, as our potential analysis is specifically-tailored to this dynamic interaction model. Second, as we detail in the Appendix, some of their technical conditions imply existence of global synchronization. For Assran et al. [2018], as we detail in the Appendix, their analysis would not guarantee any non-trivial speedup due to parallelization in the asynchronous gossip model. We describe these issues in detail and present a systematic comparison in Appendix A.
Lu and De Sa [2020] provided a novel approach to analyze decentralized SGD with quantization and limited asynchrony: specifically, their algorithm requires blocking communication, i.e. nodes have to synchronize explicitly during interactions, but may see old versions of eachothers' models. More precisely, during each interaction, both parties are responsible for updating their local models, meaning that once node is woken up (we call it initiator node) and chooses interaction partner it has to block until the partner is woken up as well. In our case, initiator can update both its local model and the local model of its partner and proceed to the next step without blocking. Koloskova et al. [2019a] use a similar update rule in the synchronous model. Zhang and You [2021] recently proposed a decentralized algorithm which is fully-asynchronous as long as node activation rates and message delays are bounded. As noted earlier, bounding activation rates does imply blocking; however, tolerating (bounded) message delays does improve over our approach of updating models using atomic writes. The set-ting further differs in that they assume that nodes compute full (non-stochastic) gradients, as well as that the loss function satisfies the PL condition.
In sum, we are the first to explicitly consider the asynchronous gossip model, and the impact of local updates, asynchrony, and quantization used in conjunction together with decentralized SGD. Our technique is new, relies on a finegrained analysis of individual interactions, and can yield improved bounds even in the case where H = 1. Further, our algorithm is the first to allow for both communication-compression and non-blocking communication. From the implementation perspective, the performance of our algorithm matches or improves that of previous methods, notably D-PSGD [Lian et al., 2017], AD-PSGD [Lian et al., 2018] and SGP [Assran et al., 2018].

Preliminaries
The Distributed System Model. We consider a model which consists of n ≥ 2 nodes, each of which is able to perform local computation. We assume that communication network of nodes is a graph G with spectral gap λ 2 , which denotes the second smallest eigenvalue of the Laplacian of G. Let ρ max , ρ min be the maximum and minimum degrees in G, respectively. We will focus on densely-connected topologies, which model supercomputing and cloud networks: for instance, the standard Dragonfly topology [Kim et al., 2008, Besta andHoefler, 2014] is regular, densely connected and low-diameter, mimicking regular expanders.
The execution is modelled as occurring in discrete steps, where in each step a new node (the "initiator") is sampled, and can then contact one of its neighbors (the "responder") uniformly at random. (At the algorithm level, the initiator is "sampled" once it completes its current computational step, and seeks to interact with a neighbor.) We denote the number of steps for which we run by T . Globally, the communication steps can be seen as a sequence of sampled directed communication edges. Thus, the basic unit of time is a single pairwise interaction between two nodes. Notice however that in a real system Θ(n) of these interactions could occur in parallel. Thus, the standard global time measure is parallel time, defined as the total number of interactions divided by n, the number of nodes. Parallel time intuitively corresponds to the average number of interactions per node until convergence. This model is identical to the asynchronous gossip model [Xiao and Boyd, 2004], and to the population protocol model [Angluin et al., 2006].
Stochastic Optimization. We assume that the agents wish to jointly minimize a d-dimensional, differentiable function f : R d → R. Specifically, we will assume the empirical risk minimization setting, in which agents are given access to a set of m data samples S = {s 1 , . . . , s m } coming from some underlying distribution D, and to functions i : R d → R which encode the loss of the argument at the sample s i . The goal of the agents is to converge on a model x * which minimizes the empirical loss over the m samples, that is . We assume that each agent i has a local function f i associated to its fraction of the data, i.e ∀x ∈ R d : 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 i has access to unbiased stochastic gradients g i of the function f i , which are functions such that E[ g i (x)] = ∇f i (x). Stochastic gradients can be computed by each agent by sampling i.i.d. the distribution D, and computing the gradient of f at θ with respect to that sample. Our analysis also extends to the case where each agent is sampling from its own partition of data. We assume the following conditions about the objective function, although not all our results require the second moment bound: sends quantizations using an increasing number of bits, until v replies confirming that it has decoded successfully. The number of bits sent during communication is upper bounded by O d log( R x − y ), where x is a vector node u is sending and y is vector node v is using for decoding. In our setting, we use communication buffers which, so node u can simply append all of its potential messages together as Q R, (x).
Critically, notice that node u should append enough bits so that the decoding is possible (Since in our setting there is no way for v to acknowledge that it received enough number of bits). This can be done in two ways. If u knows the distance between x and y. then u can simply write O d log( R x − y bits in the register.
In the second case, u does not know the distance. Let T be the total number of times nodes communicate throughout our algorithm. We will show that with high probability all distances between encoded and decoding vectors will be at most T 17 R (dependence on T stems from the fact that we wish to show an upper bound with high probability, please see Lemma B.19 in the Appendix), and therefore at most O(d log T ) bits for quantization will suffice in the worst case. Thus, the node writes O(d log T ) bits in the register , but when v tries to decode, it does not need all those bits: it reads and uses only the first O log( R x − y bits.
Counting Communication Cost. We emphasize that, when we calculate the number of bits needed by quantization we actually aim to measure the number of bits exchanged between u and v. In the setting we consider, which has local registers/communication buffers, this is the number of bits spent to read from (or to write to) the non-local register. Since the second case above involves writing a relatively large number of bits, we will use it only when u is writing a quantized value to its own register/buffer, and so does not need to communicate the bits. Then, only the O log( R x − y bits read by v need to be communicated.
To summarize, in our algorithm we will always ensure that whenever some node u writes a quantized value, it either knows the key which will be used for decoding it, or is writing to its local register.

The SwarmSGD Algorithm
We now describe a decentralized variant of SGD, designed to be executed by a population of n nodes, interacting over the edges of communication graph G, as described above. The algorithm proceeds in individual communication steps, where in each step a node which has completed its local computation, seeks a random neighbor to communicate with. We will alternatively say that node gets activated (once it finished computation) and then becomes initiator of the interaction.
The Communication Registers. The communication buffer of each node i consists of two registers: one containing an encoded version of its own (possibly outdated) model, which will only be written to by node i itself, and one for holding an encoded version of its current model, which will only be written to by other nodes. (This second register can be seen as a "communication queue" for the nodes wishing to communicate with i.) Initially all registers contain zero vectors.
Parallel Execution. For simplicity we will skip the details of quantization, and assume that nodes write and read quantized models directly, without encoding and decoding steps. Both current and outdated models are zero vectors initially. Each node i computes a number of local gradients based on its last model view, and other nodes may update this model while i is computing. Hence, only after node i is done with computing local gradients does it read its updated current model. LetX i be the value of the outdated model and let X i be the value of the current model. Node i computes the average of quantized models Q(Xi)+Q(Xj ) 2 and writes it in a register which contains current model of node j. Next, it computes where η is a learning rate and h(X i ) is a sum of local gradients), and writes it in both of its local registers, one containing the current model and one containing the outdated model. Once the write is finished, it again proceeds to compute local gradients, based on the view . Sequential model. For the analysis, it is useful to map these parallel interactions to a sorted sequence of sequential ones. Thus, time steps track the interactions between agents, and each interaction consists of random number of local steps steps which activated node performs, plus one averaging step where activated node (or initiator node) contacts its random neighbour. The analysis assumes that nodes get activated randomly, by independent Poisson clocks, which leads to a uniform global sampling distribution. In practice, this could be approximated by having the number of local gradient steps executed by each node be a geometric random variable of mean H. For the sake of practicality, our experiments will take H to be a small constant, instead of a random variable, which yields similar results. The pseudocode from the point of view of a single node i which was activated at step t + 1 is given in Algorithm 1.
For t ≥ 0, let Enc(X i t ) and Enc(X i t ) be the values written in the registers containing the outdated and the current model of agent i after t steps, respectively. That is, X i t is the current model of agent i andX i t is the outdated model.
The Communication Procedure. Since i was activated at step t we will assume that it has already computed H i local gradients using the outdated modelX i t , where H i is a geometric random variable with mean H, as follows.
) be the q-th local gradient. Then, let h i (X i t ) = Hi q=1 h q i (X i t ) be the sum of all computed local gradients. Or alternatively, since we are in a sequential setting, we can assume that i does computation at step t. First, i retrieves Q(X i t ) (the quantized version of its current model), by decoding Enc(X i t ) using key Q(X i t ). We would like to note that i can obtain Q(X i t ) simply by decoding Enc(X i t ), using keyX i t (which it knows, to full precision, since it calculated the value itself), and this step does not cost any communication bits since all of the terms involved are local to i's registers.
Then, it contacts its interaction partner j. Node i calculates Q(X j t ) by decoding Enc(X j t ), again usingX i t as a key, and then it retrieves Next, node i calculates Enc(X i t+1 ) and writes to its own register for its 8 outdated models. Here, we use the first case for quantization using Corollary 2.1: i is not aware of the key that other nodes will use for decoding, but since it is writing to its own local register, it can afford to use the worst-case O(d log T ) bits. Additionally, it writes Enc(X i t+1 ) to its own register containing current model, so that there are enough bits for Q(X i t+1 ). (Note thatX i t+1 = X i t+1 has to be used as decoding key.) Finally, it calculates Enc(X j t+1 ) and writes it in the register which contains the current model of j, using enough bits that it can be decoded using Q(X j t+1 ) (we have thatX j t+1 =X j t ) . Notice that, the way our algorithm is specified, every node which tries to decode Enc(X j t+1 ) will use Q(X j t+1 ) as a key (which i knows), hence Corollary 2.1 holds in this case as well. We emphasize the fact that all this communication is one-way, as it does not require j's intervention. By Corollary 2.1 the total number of bits used is : (Recall that we count only reading and writing to other registers, and do not count operations i performs on its own registers.) We will show that we can make the probability of any instance of quantization failing less than 1/T c , for some sufficiently large constant c, by setting the constant factor in the number of bits sufficiently high. Then, we can take a union bound over all instances of quantization throughout the algorithm, to show that none fail with high probability in T . Henceforth, we will then be able to prove the convergence of our algorithm conditioned on this event.
Algorithm 1 Sequential SwarmSGD pseudocode for each interaction between nodes i and j.
1: % Let G be a communication graph. 2: % Initial models X 1 0 = X 2 0 = ... = X n 0 3: for t = 0 to T − 1 do 4: Sample the initiator node i uniformly at random. 5: Node i samples a node j, adjacent to it in G, uniformly at random. 6: Let t − τ i t be the last step at which node i was chosen as initiator. 7: Write Enc(X i t+1 ) to the registers containing current and outdated models of node i 14: Write Enc(X j t+1 ) to the register containing current model of node j 15: For k = i, j, X k t+1 = X k t . 16: end for Avoiding race conditions. An interesting question is what happens when multiple nodes contact j concurrently. For conciseness, our pseudocode assumes that the update sequence in lines 8-14 happens atomically, but this sequence can cause a data race. To mitigate this, we can use a bounded non-blocking queue [Michael and Scott, 1996] at each node instead of a single buffer. Thus, instead of updating the buffer value atomically, each node simply appends the corresponding quantized model mean to j's communication queue. In practice, this queue is extremely unlikely to be contended, since communication collisions are rare.

The Convergence of SwarmSGD
Let µ t = n i=1 X i t /n be the mean over node models at time t. Our main result is the following: for constant C, and uses O d log ρ 2 max ρminλ2 + log T expected communication bits per step.
Discussion. First, this notion of convergence is standard in the non-convex case [Lian et al., 2015[Lian et al., , 2017[Lian et al., , 2018, and each of the upper bound terms has an intuitive interpretation: 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 represents the noise due to stochasticity, and is naturally linear in H, as H steps are taken in expectation between two interactions. (Recall that in our model T is the number of interactions, and T H is the expected number of gradient steps.) The fourth term encodes overheads caused by local steps, quantization, and graph structure; however, it is usually seen as negligible (cf. [Lu and De Sa, 2020]), due to division by T .
The third term is the critical one, as it implies a dependence on the secondmoment bound. Intuitively, this term appears because our algorithm combines both non-blocking communication, and quantization: first, unlike prior work, we do not assume an explicit delay upper bound τ on communication; in conjunction with quantization, the unbounded delay this implies that our estimate on the model average µ t may become dependent on M for large delays, which causes this dependency. While this limitation appears inherent, we are able to remove it if we eliminate quantization: in this case, we get a negligible dependency on M . We formalize this in Corollary 4.2.
Second, if we focus on the total number of steps to reach some error bound, we notice an interesting trade-off between the linear reduction in H in the first term, due to local steps, and the linear increase in H in the other terms. Notice that, for dense and low-diameter graphs, such as the regular expanders popular in cluster networks, our convergence bound has no dependence in the graph parameters, and communication is linear in d. However, one limitation is that we could have a log n dependency in the communication for highly-irregular and poorly-connected graphs.
Finally, note that time T here counts total interactions. However, Θ(n) pairwise interactions occur independently in parallel, and so we can slightly abuse notation and replace T by nT in the above formula, to obtain optimal Θ( √ n) speedup in terms of wall-clock time. Yet, this speedup is dampened by the variance due to noisy local gradient steps, a fact which we will revisit in the experimental section.
Proof Overview. At a high level, the argument rests on two technical ideas. The first is that, in spite of noise and local steps, the nodes' parameters remain concentrated around the mean µ t . The second is to leverage this, and bound the impact of stochastic noise and model staleness on convergence. In particular, the main technical difficulty in the proof is to correctly "encode" the fact that parameters are well concentrated around the mean. A natural approach is to bound the model variance Γ t after t interactions. Formally, we , as before. We bound the expected evolution of Γ t over time, depending on the learning rate, number of local steps, quantization parameter and the bound provided by the assumption on the stochastic gradients (the bound M 2 ). The critical point is that the upper bound on the expectation of Γ t does not depend on the number of interactions t. More precisely, if all the above hyper-parameters are constant, we get that E[Γ(t)] = O(n). Our approach brings over tools from classic load-balancing [Berenbrink et al., 2009], to the multi-dimensional case.
Three key elements of novelty in our case are that (1) for us the load balancing process is dynamic, in the sense that new loads, i.e. gradients, get continually added; (2) the load-balancing process we consider is multi-dimensional, whereas usually the literature considers simple scalar weights; (3) the models can be outdated and quantized, which leads to a complex, noisy load-balancing process. We resolve the this third and most challenging issue by using carefully-defined auxiliary potentials.
Removing the Second-Moment Bound. Upon reflection, we notice that can render the dependency on M 2 negligible if we do not use quantization, but otherwise keep the algorithm the same: Corollary 4.2. Given the previous assumptions and learning rate η = n/ √ T , for some constant C, we have that the Algorithm 1 where quantization is the identity converges at rate Notice that in this case all the term containing the second moment bound M 2 is dampened by a factor of 1 T , hence we can assume that Algorithm 1 converges at close-to optimal rate . This result still improves upon previous analyses [Lian et al., 2018, Assran et al., 2018, Lu and De Sa, 2020 in the sense that communication is completely non-blocking (there is no τ ), and we allow for local steps.
Further, in the absence of quantization and assuming that the nodes perform single local gradient step, we can entirely remove assumption (4), when T is large enough (e.g for the fully connected graph we will need T ≥ Ω(n 3 )).
More precisely, we can attain convergence rate

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 supercomputing setting, in which we have a 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 synchronizing all nodes so they execute in lock-step can be very high, see e. As noted in previous work [Lian et al., 2017, 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 is justified theoretically, as the slower mixing can affect convergence, but also intuitively, as each model sees significantly fewer updates per epoch. Thus, we will allow the decentralized schemes to execute for more epochs, by a constant multiplier factor between 1 and 3. To reduce multipliers, we experimented with SlowMo [Wang et al., 2019]; we found that it improved results across methods on CIFAR-10, but not at ImageNet scale; therefore, the provided results do not include it. Once we have fixed the number of epochs, we do not alter the other training hyperparameters: in particular, the learning rate schedule, momentum and weight decay terms are identical to the standard values for sequential SGD, for each individual model.    (a) Convergence in time 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. The experiment is run on 32 nodes.  Convergence results and performance breakdown for ResNet18/ImageNet. recover full accuracy versus the sequential or large-batch SGD baselines. In Table 1 we provide an overview of parameter values to recover large-batch SGD accuracy (following Goyal et al. [2017]) using SwarmSGD, on the ResNet, Im-ageNet and CIFAR tasks. We execute for 32 nodes on ImageNet, and 8 nodes on CIFAR-10. (Local batch sizes are 128 for ResNet20 and ResNet50, and 128 for ResNet18. Quantization is not applied in these experiments.) The results show that Swarm can recover or slightly exceed the accuracy of the large-batch baselines, and that it has lower practical communication cost relative to existing methods (see Figure 2(b), where we separate the average computation cost per batch). However, Swarm requires significant additional passes over the data (up to 2.7×) to achieve full accuracy, which negates its performance benefits in this specific setting, relative to large-batch SGD. 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 large-batch SGD (LB-SGD) baseline (BLEU score 26.1 at 16 nodes) is a poor alternative at high node counts due to model size:  Table 1: Parameters for approximate Top-1 validation accuracy recovery 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 by all nodes.
its throughput is low, and drops catastrophically at 64 nodes due to the network becoming severely bandwdith-bottlenecked (see Figure 1(b)). At 16 nodes, Swarm slightly exceeds the baseline accuracy at 26.17 BLEU, for an end-to-end speedup of ∼ 1.5×. In the same setting, Swarm outperforms all other decentralized methods (the fastest previous method, AD-PSGD, is 30% slower, and less accurate), both in terms of BLEU score, and in terms of end-to-end time.(The objective loss graph is similar, and is provided in the Appendix). At 32 nodes, all decentralized methods reach lower scores (∼ 23.5) after 10 epochs. However, we observed experimentally that running Swarm for an additional 5 epochs (multiplier 1.5) at 32 nodes recovered a BLEU score of ∼ 25.72, which is 30% faster than the 16-node version in terms of end-to-end time (omitted for visibility).
In addition, 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 so, 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 to recover baseline accuracy on ResNet18/ImageNet for up to 4 local steps (see Figure 2(a)); 3) the impact of quantization on convergence, where we were able to recover accuracy when applying 8-bit model quantization to Swarm. We encourage the reader to examine the full experimental report in the Appendix, which contains data on these experiments, as well as additional ablation studies.
Discussion. Generally, the performance of SwarmSGD appears to be slighly superior to previous decentralized methods (see Figure 1 for an illustration, and Figure 2(b) for a performance breakdown). We investigated this advantage, and found that the per-step communication cost of Swarm, without quantization, is similar to AD-PSGD; however, our algorithm benefits from the reduction in communication frequency: nodes communicate at least 2x less often, and therefore incur lower average communication cost. In particular, a closer examination of the average batch times in Figure 2(b) shows that time per node per batch (including communication and computation) is largely constant as we increase the number of nodes, which suggests good scaling behaviour.
The main disadvantage of Swarm is that, similar to previous decentralized methods, it may need additional data passes in order to fully recover accuracy at high node counts. However, we also note that our method did not benefit from the high level of hyperparameter tuning applied to large-batch SGD, e.g. Goyal et al. [2017]. We find it interesting that this accuracy issue is less prevalent in the context of large, over-parameterized models, such as the Transformer, where Swarm can be a viable alternative to large-batch SGD within the same number of epochs.

6 Conclusions and Future Work
We analyzed the convergence of SGD in an extremely decoupled model of distributed computing, in which nodes mostly perform independent SGD updates, interspersed with intermittent pairwise averaging steps, which may be performed in an inconsistent and noisy manner. We showed that SGD still converges in this restrictive setting, even under consistency relaxations. Empirical results complement our analysis, showing that this method can outperform previous decentralized algorithms, and can even be competitive against large-batch SGD for very large models. A natural extension would be to generalize the bounds to arbitrary communication graphs. From the practical perspective, one extension would be to reduce the additional training epochs, and to experiment on large-scale decentralized testbeds.

A.1 Comparison with SGP
In Assran et al. [2018], all nodes perform gradient steps at each iteration, in synchronous rounds, but averaging steps can be delayed by τ iterations. Unfortunately, the mixing time of their algorithm depends on the dimension d (more precisely, it contains a √ d factor). Moreover, it depends on the delay bound τ , and on ∆, defined as the number of iterations over which the interaction graph is well connected. Additionally, their analysis will not extend to the random interaction patterns required by the asynchronous gossip models. Practically, their analysis works for deterministic global interactions, but where nodes may see inconsistent versions of eachothers' models. As noted in [Assran et al., 2018] and also in our Related Work section, enforcing the τ bound inherently implies that the algorithm may have to block in case a slow node may cause this bound to be violated.

A.2 Comparison with AD-PSGD
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. Due to asynchronous model, like ours, Lian et al.
[2018] allow agents to have outdated views during the averaging step. We would like to emphasize that in their case outdated models are assumed to come from the same step.
More precisely, at every step t, there exists τ ≤ τ max such that for every agent i,X i t = X i t−τ . As also noted by Assran et al. [2018], enforcing this will require the usage of global barrier (or some alternate method of blocking while waiting for the nodes whose models are outdated by more than τ max steps) once in every τ max steps. Their implementation section suggests to explicitly implement synchronous pairings at every step.
In our case, at each step t and agent i, the delay τ i t is a random variable , such that t − τ i is the last step node i was chosen as initiator. This implies naturally thatX i t = X i t−τ , since t − τ i is the last step node i updated its own model.

A.3 Comparison with Moniqua
Lu and De Sa [2020] consider a virtually identical model to AD-PSGD, but they also add quantization. The first difference between their work and ours is that we are using a random mixing matrix, thus we have to take the probability of models diverging (models diverge if the distance between them is larger then required by quantization algorithm) into account. Subsequently, this justifies our usage of Davies et al. [2021], since in this quantization method allows us to tolerate the larger distances between the models. This technical difference justifies the fact that our main bound has a non-trivial dependency on the second-moment bound M . As we showed, this dependency can be removed if we remove quantization. The second difference is that our interactions are one sided, that is, if i and j interact and i is initiator, i does not have to block while j is in compute.

A.4 Discussion
In summary, our algorithm is the first to explicitly consider the classic asynchronous gossip model [Xiao and Boyd, 2004], and show convergence bounds in its context. While AD-PSGD could be re-stated in this model, the corresponding bounds would be weaker than the ones we provide. At the practical level, to our knowledge we are the first to propose a fully non-blocking algorithm, which does not rely on a deterministic upper bound of τ max steps on the maximum delay between the nodes, and therefore remove the need for implementing global barrier-like communication to enforce τ max . However, we note that our 20 node activation model inherently implies a probabilistic bound on the expected maximum delay. In addition, we also allow for communication quantization and local steps, in the same asynchronous model.
The price we pay for this added generality is that the rate given in Theorem 4.1 has a dependency on the second-moment bound. As we showed in Corollary 4.2, this requirement can be removed if communication is not quantized.

B The Complete Analysis B.1 Technical Lemmas on Load Balancing and Graph Properties
In this section provide the useful lemmas which will help as in the later sections.
We are given a simple undirected graph G, with n nodes (for convenience we number them from 1 to n) and edge set E(G). Let ρ i be a degree of vertex i and let ρ i be a set of neighbours of i (|ρ i | = ρ i ). Also, we assume that the largest degree among nodes is ρ max and the smallest degree is ρ min .
Each node i of graph G keeps a local vector model X i t ∈ R d (t is the number of interactions or steps); let X t = (X 1 t , X 2 t , ..., X n t ) be the vector of local models at step t.
Let µ t = n i=1 X i t /n be the average of models at step t and let Γ t = n i=1 X i t − µ t 2 be a potential at time step t.
Let L be the Laplacian matrix of G and let let λ 2 be a second smallest eigenvalue of L. For example, if G is a complete graph λ 2 = n. In general we have that λ 2 ≤ 2ρ max .
First we restate the following lemma from Ghosh and Muthukrishnan [1996]:

Now, we show that Lemma B.1 can be used to lower bound
Proof. Observe that Also, notice that Lemma B.1 means that for every vector v = (v 1 , v 2 , ..., v n ) such that n i=1 v i = 0, we have: is a 0 vector, we can apply the above inequality to the each of d components of the vectors X 1 t − µ t , X 2 t − µ t , ..., X n t − µ t separately, and by elementary properties of 2-norm we prove the lemma.
Let ρ i be a degree of vertex i; we denote largest degree among nodes by ρ max and the smallest degree by ρ min .

B.2 Properties of the Quantization Scheme
In this section, we discuss and prove the properties of the quantization scheme we consider, as well as potential complications caused by using quantization in an asynchronous shared-register setting. We also provide a fully-detailed version of Algorithm 3, with respect to quantization.
We first describe how the quantization method of Davies et al. [2021] is adapted to the local register setting to give Corollary 2.1:

B.3 Proof of Corollary 2.1
From Interactive Communication to Non-blocking Communication Buffers. Lemma 23 of the full version of Davies et al. [2021] provides similar guarantees to Corollary 2.1, but in a different setting. Specifically, they assume interactive message-passing communication between an encoding node u and a decoding node v. However, in their setting, the messages sent by u are nonadaptive: u simply sends quantizations using an increasing number of bits, until v replies confirming that it has decoded successfully. In our setting, we implement communication buffers, so node u can simply append all of its potential messages together as Q R, (x u ).
Critically, notice that node u should append enough bits so that the decoding is possible. This can be done in two ways. If u knows the distance between X u and the vector v uses for decoding, which we call the decoding key key(v), then u can simply write bits in the register.
In the second case, u does not know the distance. We can show, however, that with high probability in the total number of steps T , all distances between encoded and decoding vectors will be at most · poly(T ), and therefore at most O(d log T ) bits for quantization will suffice in the worst case. Thus, the node writes O(d log T ) bits in the register (Recall that T is the total number of steps taken by our algorithm). But, when v tries to decodes, it does not need all those bits: it reads and uses only the first O log( R x u − key(v) bits. This follows by Lemma 23 of Davies et al. [2021].
Counting Communication Cost. We emphasize that, when we calculate the number of bits used by quantization we actually aim to measure the number of bits exchanged between u and v. In the setting we consider, which has local registers/communication buffers, this is the number of bits spent to read from (or to write to) the non-local register. Since the second case above involves writing a relatively large number of bits, we will use it only when u is writing a quantized value to its own register/buffer, and so does not need to communicate the bits. Then, only the O log( R x u − key(v) bits read by v need to be communicated. 22 To summarize, in our algorithm we will always ensure that whenever some node u writes a quantized value, it either knows key(v), or is writing to its local register. In the second case, we have to guarantee that O(d log T ) bits suffice in the worst case. That is, x u − key(v) = O (poly(T )) R . In the first case, there are no restrictions.

B.4 Notation and Auxiliary Potential Functions
Recall that t − τ i t is the last time i was chosen as initiator up to and including step t. We would like to emphasize that τ i t is a random variable and we do not make any additional assumptions about it. Initially, τ i 0 = 0 for every i. Then, if node i is chosen as initiator at step t + 1 we have that and for each τ j t+1 = τ j t + 1.
(8) Next, we provide the formal definition of the local steps performed by our algorithms. Recall that X i t is a local model of node i at step t. Let H i t be the number of local steps node i performs in the case when it is chosen for interaction at step t + 1. A natural case is for H i t to be fixed throughout the whole algorithm, that is: for each time step t and node i, H i t = H (or alternatively we might to try that H i t can be a geometric r.v with mean H). h 0 i (X i t ) = 0. and for 1 ≤ q ≤ H i t let: Note that stochastic gradient is recomputed at each step, but we omit the superscript for local step and global step for simplicity (Whenever we write g i , we mean that gradient is computed freshly by choosing sample u.a.r from the data available to node i). that is: be the expected value of h q i (X i t ) taken over the randomness of the stochastic gradient g i . Let h i (X i t ) be the sum of H i t local stochastic gradients we computed: In summary, omitting local step number q means that we compute the sum of all generated gradients (this is the entire update during compute). and omitting tilde sign, means that we compute expectation over the randomness of the samples.
Similarly, for simplicity we avoid using index t in the left side of the above definition, since it is clear that if the local steps are applied to model X i t we compute them in the case when node i is chosen as initiator at step t + 1.
In the case of outdated models this means that Potential Functions. In order to deal with asynchrony we define the potential function: Xi t − µ t 2 . This potential helps us to measure how far are the outdated models from the current average. In order to boundΓ t in expectation, we will need additional auxiliary potential functions: Notice that by definition ofX i t and Couchy-Schwarz inequality we get that

B.5 Properties of Local Steps
Lemma B.3. For any agent i and step t Proof.
Where in the last step we used Lemma B.4. For any agent 1 ≤ i ≤ n, number of local steps 1 ≤ K and step t, we have that Proof.
To finish the proof, we need to upper bound Next, we sum up the upper bound given by the above lemma and take the randomness of the number local steps into the account: Lemma B.5. For any step t, we have that Proof. Using lemma B.4 Notice that 25 Also, Where in the last step we used the definition ofΓ t and (3).
Lemma B.6. For any local step 1 ≤ q, and agent 1 ≤ i ≤ n and step t: Proof.
Lemma B.7. For any time step t.
Plugging this in the above inequality we get: To finish the proof we upper bound the above two terms on the right hand side. Note that: Where in the last step we used that n i=1 fi(x) n = f (x), for any vector x. Also: Where in the last step we used (Recall that H i t−τi is a geometric random 27 variable with mean H):

B.6 Upper Bounding Potential Functions
We proceed by proving the following lemma which upper bounds the expected change in potential: Lemma B.8. For any time step t we have: Proof. First we bound change in potential ∆ t = Γ t+1 − Γ t for some fixed time step t > 0.
For this, let ∆ i,j t be the change in potential when agent i wakes up (is chosen as initiator) and chooses neighbouring agent j for interaction. Let Next, we calculate probability of choosing edges from graph and upper bound ∆ t in expectation, for this we define E t as expectation conditioned on the entire history up to and including step t Now, we use the upper and lower bounds on the degree of vertices Now, we use lemma B.2: By setting α = λ2 8ρ 2 max , we get that: Next we remove the conditioning , and use the definitions of ∆ i and S i t (for S i t we also use upper bound which come from the properties of quantization).
Finally, we get the proof of the lemma after using ρ 2 max ρminλ2 ≥ 1 2 (See (5)) and regrouping terms.
This allows us to upper bound the potential in expectation for any step t.
Proof. We prove by using induction. Base case t = 0 trivially holds. For an induction step step we assume that H 2 M 2 η 2 . We get that : Lemma B.10. For any time step t: Proof. Recall that if node i is chosen as initiator at step t, then for each j = i, (7) and (8)). Thus, if E t is expectation conditioned on the entire history up to and including step t then After removing conditioning and regrouping terms we get the proof of the lemma Next, we upper bound A t in expectation Lemma B.11. For any time step t: Proof. By combining Lemmas B.9 and B.10 we get that: H 2 M 2 η 2 and the proof follows by using the same type of induction as in the proof of Lemma B.9 Next we provide two different versions of upper bounding E µ t+1 − µ t 2 , the first one will be useful for upper bounding E[B t ] and the second one will be used in the proof of convergence for SwarmSGD.
Lemma B.12. For any time step t: Proof. Let i be the agent which is chosen as initiator at step t + 1 and let j be the neighbour it selected for interaction, also let E t be expectation which is condition on the entire history up to and including step t We have that Where in the last step we used property of quantization and Lemma B.3. Since this upper bound holds for any agents i and j, after removing the conditioning, we get the proof of the lemma.
Lemma B.13. For any step t Proof. Following the same steps as the proof of Lemma B.12 and taking the randomness of agents i (the initiator) and j interacting at step t + 1 in to the account we get that Our next goal is to upper bound E[B t ], for which we will need the following lemma: Lemma B.14. For any time step t and agent i: Note that for any t − τ i t ≤ s ≤ t − 1 we can use Lemma B.12 to upper bound E τ i t µ s+1 − µ s 2 , since it uses quantization property and Lemma B.3 (which in turn uses (4) and the randomness of the number of local steps) which do not depend on τ i t . In fact, as proof of Lemma B.12 suggests, for any t−τ i t ≤ s ≤ t−1, 33 we could condition E µ s+1 − µ s 2 on the entire history up to and including step s (this history includes τ i t as well) and the upper bound would still hold. Thus, we get that Finally we remove the conditioning : Next, we proceed to prove the following lemma: Proof. For a fixed step s, let E s be an expectation conditioned on the entire history up to and including step s. If agent i is chosen as initiator at step s + 1 then τ i s+1 = 0 and otherwise τ i s+1 = τ i s + 1. Since i is chosen with probability 1 n , we have that Where in the last step we used that n ≥ 2.
Also, by using Cauchy-Schwarz inequality we get that Thus, Next, we remove the conditioning: Where in the last step with use Jensen's inequality and concavity of square root function. Finally, we finish the proof of the lemma using induction. Base case holds trivially, for induction step we assume that This finishes the proof of the Lemma.
Finally, we are ready to upper bound B t Lemma B.16. For any step t: Proof. Lemma B.14 gives us that After applying Lemma B.15 we get the proof of the Lemma.

The last lemma in this section upper bounds E[Γ t ]:
Lemma B.17. For any step t, we have that Proof. From (9), and Lemmas B.11 and B.16 we get that Where in the last step we used ρ 2 max ρminλ2 ≥ 1 2 (See (5)).

B.7 The Convergence of SwarmSGD
Theorem B.18. For learning rate η = n/ √ T , Algorithm 1 converges at rate: Proof. Let E t denote expectation conditioned on the entire history up to and including step t. By L-smoothness we have that First we look at If agent i is chosen as initiator at step t + 1 and it picks its neighbour j to interact, We have that Thus, in this case: Where we used unbiasedness of quantization and stochastic gradients. We would like to note that even though we do condition on the entire history up to and including step t and this includes conditioning onX i t , the algorithm has not yet used h i (X i t ) (it does not count towards computation of µ t ), thus we can safely use all properties of stochastic gradients. Hence, we can proceed by taking into the account that each agent i is chosen as initiator with probability 1 n : and subsequently Hence, we can rewrite (11) as: Next, we remove the conditioning This allows us to use Lemmas B.13 and B.7: 12H 3 L 2 M 2 η 3 n + 6(R 2 + 7) 2 2 n 2 + 3η 2 Hσ 2 n 2 To simplify the above inequality we assume that η ≤ 1 8H and also use the fact that n ≥ 2. We get: Here, important thing is that we used 18η 2 H 2 E ∇f (µt) 2 n 2 − HηE ∇f (µt) 2 4n ≤ 0.
Further, we use Lemma B.17: by summing the above inequality for t = 0 to t = T − 1, we get that 39H 3 L 2 M 2 η 3 T n + 6(R 2 + 7) 2 2 T n 2 Next, we regroup terms, multiply both sides by 2n ηHT and use the fact that HηT + 6η(σ 2 + 6Hς 2 ) n + 1600ρ 3 max (R 2 + 7) 2 2 L 2 ρ min λ 2 2 + 2496η 2 ρ 3 max H 2 L 2 M 2 ρ min λ 2 2 + 78H 2 L 2 M 2 η 2 + 12(R 2 + 7) 2 2 nηH Finally, we set η = n Xeon E5-2690v3 CPU and an NVIDIA Tesla P100 GPU, using a state-of-theart Aries interconnect. Please see Piz [2019] for hardware details. We implemented SwarmSGD in Pytorch and TensorFlow using NCCL/MPI respectively. Basically, each node implements a computation thread, and a communication thread, each of which stores a copy of the model. The "live" copy, which is being updated with gradients, is stored by the computation thread. A simplified version of the Pytorch implementation is provided as additional material. When interacting, the two nodes exchange model information via their communication threads. Our implementation closely follows the non-blocking algorithm description.
Hyperparameters. The only additional hyperparameter is the total number of epochs we execute for. Once we have fixed the number of epochs, we do not alter the other training hyperparameters: in particular, the learning rate schedule, momentum and weight decay terms are identical to sequential SGD, for each individual model. Practically, if sequential SGD trains ResNet18 in 90 epochs, decreasing the learning rate at 30 and 60 epochs, then SwarmSGD with 32 nodes and multiplier 2 would 90 * 2/32 5.6 epochs per node, decreasing the learning rate at 2 and 4 epochs. As mentioned, we have also tried to use SlowMo [Wang et al., 2019], but did not observe significant improvements in terms of accuracy on ImageNet.
Specifically, for the ImageNet experiments, we used the following hyperparameters. 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 2 local steps. We used the same hyper-parameters (initial learning rate 0.1, annealed at 1/3 and 2/3 through training, and standard weight-decay and momentum parameters).
For the WMT17 experiments, we ran a standard Transformer-large 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 one with multiplier 1.5 (i.e. 15/num nodes epochs per model) and registered the BLEU score for each.
Baselines. We consider the following baselines: • Data-parallel SGD: Here, we 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 et al., 2018: We follow the implementation of Lin et al. [2018], communicating globally every 5 SGD steps (which was the highest setting which provided good accuracy on 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 best performing alternative (AD-PSGD) is known to drop accuracy relative to the baselines, e.g. Assran 43 et al. [2018].
Our Pytorch implementation builds upon that of Assran et al. [2018].
Results. The accuracy results for ImageNet experiments are given in Table 1 and Figures 3(a) and 3(b). As is standard, we follow Top-1 validation accuracy versus number of steps. Figure 5: Average time per batch for previous methods, compared to SwarmSGD, on ResNet18/ImageNet, 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 on 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. We note that this comparison is performed in the framework of [Assran et al., 2018], and that we have considered the best-performing variant of D-PSGD, AD-PSGD and SGP, according to their implementation.
(a) Convergence versus time for ResNet18/Imagenet for the SGD baseline vs Swarm, executing at 32 nodes.   average time per batch, which is 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 can be up to half the cost of the full batch (for SGP and D-PSGD at large node counts). 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 communicates less often, and therefore the average cost of communication at a step is lower. Figure 3(b) shows the convergence versus time for ResNet18 on the ImageNet dataset, at 32 nodes, with 3 local steps per node, and ∼ 7 epochs per model.

Convergence versus
Steps and Epochs. Figure 4 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 preserves convergence even at 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 a much lesser degree.
Quantization. Finally, we show convergence and speedup for a WideResNet-28 model with width factor 2, trained on the CIFAR-10 dataset. We note 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 a < 0.3% drop in Top-1 accuracy.