$\textbf{A}^2\textbf{CiD}^2$: Accelerating Asynchronous Communication in Decentralized Deep Learning
Authors: Adel Nabli
Eugene Belilovsky
Edouard Oyallon
Venue: NeurIPS 2023 poster (2023)
Keywords: Decentralized Optimization for Deep Learning
Asynchronous Optimization
Distributed Training
Data-Parallel
TL;DR: We introduce a principled asynchronous, randomized, gossip-based algorithm which works thanks to a continuous momentum named \acid which induces a significant communication acceleration at no cost.

Abstract: Distributed training of Deep Learning models has been critical to many recent successes in the field. Current standard methods primarily rely on synchronous centralized algorithms which induce major communication bottlenecks and synchronization locks at scale. Decentralized asynchronous algorithms are emerging as a potential alternative but their practical applicability still lags. In order to mitigate the increase in communication cost that naturally comes with scaling the number of workers, we introduce a principled asynchronous, randomized, gossip-based optimization algorithm which works thanks to a continuous local momentum named $\textbf{A}^2\textbf{CiD}^2$. Our method allows each worker to continuously process mini-batches without stopping, and run a peer-to-peer averaging routine in parallel, reducing idle time. In addition to inducing a significant communication acceleration at no cost other than adding a local momentum variable, minimal adaptation is required to incorporate $\textbf{A}^2\textbf{CiD}^2$ to standard asynchronous approaches. Our theoretical analysis proves accelerated rates compared to previous asynchronous decentralized baselines and we empirically show that using our $\textbf{A}^2\textbf{CiD}^2$ momentum significantly decrease communication costs in poorly connected networks. In particular, we show consistent improvement on the ImageNet dataset using up to 64 asynchronous workers (A100 GPUs) and various communication network topologies.

A CiD Accelerating Asynchronous Communication in Decentralized Deep Learning
Adel Nabli
Eugene Belilovsky Concordia University, Mila
Concordia University, Mila
Sorbonne University, ISTR, CNRS .tl..nalllee
Edouard Oyallon Sorbonne University, ISIR, CNRS
Abstract
Distributed training of Deep Learning models has been critical to many recent successes in the field. Current standard methods primarily rely synchronous centralized algorithms which induce major communication bottlenecks and syn- chronization locks at scale. Decentralized asynchronous algorithms are emerging a potential alternative but their practical applicability still lags. In order to mitigate the increase in communication cost that naturally comes with scaling the number workers, we introduce a principled asynchronous, randomized, gossip-based op- timization algorithm which works thanks continuous local momentum named A² PCiD2. Our method allows each worker to continuously process miii-bbtchhes without stopping. and run peer-to peer-to-peet peer averaging routine in parallel, reducing idle time. In addition inducing significant communication acceleration cost other than adding a local momentum variable, minimal adaptation is required to incorporate A A to standard asynchronous approaches. Our theoretical analysis proves accelerated rates compared previous asynchronous decentralized baselines and we empirically show that using our A "Cii" momentum significantly decrease communication costs in poorly connected networks. In particular, we show consistent improvement on the ImageNet dataset using up to 64 asynchronous workers (A100 GPUs) and various communication network topologies.
Introduction
As Deep Neural Networks (DNNs) and their training datasets become larger and more complex, the computational demands and the need for efficient training schemes continues to escalate. Distributed training methods offer solution by enabling the parallel optimization of model parameters across multiple workers. Yet, many of the current distributed methods in use are synchronous, and have significantly influenced the design of cluster computing environments. Thus, both the environments and algorithms rely heavily on high synchronicity in machine computations and rear-instantancous communication in high- banddithh networks, favoring the adoption of centralized algorithms (
However, several studies (27 44 2 28) are challenging this paradigm, proposing decentralized asynchronous algorithms that leverage minor time-delays fluctuations between workers to hance the parallelization of computations and communications. Unlike centralized algorithms, decentralized approaches allow each node contribute proportionally its available resources, eliminating the necessity for a global central worker to aggregate results. Combined with asyn- chronous peer-to-peat peer (p2p) communications, these methods can streamline the overall training
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

process, mitigating common bottlenecks. This includes the Straggler Problem A42, the synchro- nization between computations and communications [2] or bandwidth limitations 47,, poten- tially due to particular network topologies like ring graph [3 However, due to the large number of parameters which are optimized, training DNNs with these methods still critically requires a considerable amount of communication [22] presenting an additional challenge [32
This work aims to address these challenges by introducing principled acceleration method for pair-wise communications in peer-to-peer training of DNNs, in particular for cluster com- puting. While conventional synchronous set- tings accelerate communications by integrating a Chebychev acceleration followed by Gradi- Descent steps [37, the potential of accel- erated asynchronous pair- wise gossip for Deep Learning (DL) remains largely unexplored. No- lably, the sophisticated theory of Stochastic Dif- ferential Equations (SDEs) offers an analytical framework for the design and study of the con- vergence of these algorithms [2]. We intro- duce novel algorithm A CiD2 (standing for Accelerating Asynchronous Communication in Decentralized Deep Learning) that requires minimal overhead and effectively decouples commu- nications and computations, accelerating pair-wise communications via a provable, accelerated, randomized gossip procedure based on continuous momentum (i.e., a mixing ODE) and time [12 34
6x
cont
WAPCO PCOO ACC
2 com'
Trinnin Toss
4x
3 1
2 10
2000
4000
10000
4grad steps per worker
Figure I: Adding CCCiD" has the same effect as doubling the communication rates on ImageNet on the ring graph with 64 workers. See Sec. 4
We emphasize that beyond the aforementioned hardware superiority, stochastic algorithms also allows us to theoretically reach sublinear rates in convex settings (10,, which opens the possibility to further principled accelerations. In practice, our method enables virtual doubling of the communication rate challenging network topologies without any additional cost, simply by maintaining local momentum variable in each worker (see Fig. D
as follows: (1) We extend the continuized framework 122 the non- convex setting, in order to obtain a neat framework to describe asynchronous decentralized DL training. (2) This framework allows us to refine the analysis of a baseline asynchronous decentralized optimization algorithm. (3) We propose a novel and simple continuized momentum which allows to significantly improve communication efficiency in challenging settings, which we name A A²CiD². (4) We demonstrate that our method effectively minimizes the gap between centralized settings in environments hosting up to 64 asynchronous GPUs. (5) Our code is implemented in Pytorch [35), remove locks put on previous asynchronous implementations by circumventing their deadlocks, and can be found in an open-source repository: httpp::/githuub.com com/ AablAAbii/ACD
Our key contributions
This paper is structured as follows: Sec. 3.1 outlines model for asynchronous decentralized learning, while Sec. 3.22 discusses the training dynamic used to optimize our Deep models. Sec. 3.4 offers comprehensive theoretical analysis of our method, which is validated empirically in Sec.
2 Related Work
Large-scale distributed DL. Two paradigms allow to maintain high-parallelization. On one side, padel-ppraallelism 9 25). which splits neural network on independent machines, allowing to use local learning methods [4] On the other hand data-parallelism, which accelerates learning by making use of larger mini-batch splitted across multiple nodes (38) maximally use GPU capacities. This parallelization entailing the use of larger batch-sizes, it requires an important process of adapting sapee--paramter. [6]. and in particular the learning rate scheduler. Developed for this setting, methods such as [16] 46) allow to stabilize training while maintaining good generalization performances. However, they have been introduced in the context of centralized synchronous training using All-Reduce schemes for communication, which still is the default setting of many approaches to data parallelism.
Decentralized DI.. of synchronous decentralized training strategies in practice. In terms of implementation in the cluster
The pioneer work (27] is one of the first study to suggest the potential superiority

---

setting, decentralized frameworks have been shown to achieve higher throughput than optimized All-Reduce strategies 45 38.. From the theoretical side, [2T] propose a framework covering many settings of synchronous decentralized learning. However, as it consistently relies on using global discrete iterations count, the notion of time is more difficult to exploit, which reveals crucial in our setting. Furthermore, no communication acceleration is incorporated in these algorithms. [22] provides a comprehensive methodology to relate the consensus distance, i.e. the average distance of the local parameters to the global average, to necessary communication rate to avoid degrading performance and could be easily applied to our method. [29] is a method focusing on improving performance via discrete momentum modification, which indicates momentum variables are key to decentralized DL.
Asynchronous Decentralized DL. There exist many attempts incorporate asynchrony in de- centralized training [88 5 21, which typically aim at removing lock barriers of synchronous decentralized algorithms. To the best of our knowledge, none of them introduce communication acceleration, yet they could be simply combined with our approach. Although recent approaches such 2 28 perform peer-to-peer averaging of parameters instead of gradients, thus allowing to communicate in parallel of computing (as there is no need to wait for the gradients before communi- cating), they are still coupled: parameter updates resulting from computations and communications are scheduled in specific order, limiting their speed. Furthermore, in practice, both those works only implement a periodic averaging on the exponential graph (more favorable, see (43) instead of investigating the influence of the graph's 'ss topology on the convergence of a randomized gossip method, as we do. In fact, AD-PSGD [28] the baseline algorithm in asynchronous decentralized DL, comes with major caveat to avoid deadlocks in practice: they require a bipartite graph and schedule p2p communications in a pseudo- random manner instead of basing the decision on worker's current availability, hindering the advantage given by asynchronous methods in the mitigation of stragglers. Contrary to them, our implementation allows to pair workers in real time based on their availability, minimizing idle time for communications.
Communication reduction. Reducing communication overhead is an important topic for scalability [36. For instance, [19] 20 allow to use of compression factor in limited bandwidth setting, and the local SGD communication schedule of 30 is shown to be beneficial. Those methods could be independently and simply combined with ours to potentially benefit from additional communication acceleration. By leveraging key properties of the resistance of the communication network [14), [2] showed that standard asynchronous gossip [6] can be accelerated, even give efficient primal algorithms in the convex setting [34]. However, this acceleration has never been deployed in the DL context, until now. RelaySum [41] is an approach which allow average exactly parameters produced by different time steps and thus potentially delayed. However, it requires either to use a tree graph topology, either to build ad-hoc spanning trees and has inherent synchronous locks averages neighbor messages in a specific order.
Notations: Let No and No an ambient dimension, for x (x ...., rz) E Di Rd. we write ã 1 Σ x' and 1 the tensor of ones such that _1T measure P. f(t) = (11) means there is a C > 0 such that for ł large enough, If < C, whereas O-notation hides constants and polylogarithmic factors..
.....""')
n 11Tz. xt E is probability space with
3
Method
3.1
Model for a decentralized environment
We consider network of workers whose connectivity is given by edges &. Local computations modeled as (stochastic) point-wise processes N;. and communications between nodes (i,j) E & as M.. We assume that the communications are symmetric, meaning that if a message is sent from node i to j. then the reverse is true. In practice, such processes are potentially highly correlated and could follow any specific law, and could involve delays. For the sake of simplicity, we do not model lags, though
possible to obtain guarantees via dedicated Lyapunov functions [R] In our setting, we assume that all nodes have similar buffer variables which correspond to a copy of a common
model (e.g., a DNN). For parameter v, we write o the model's parameters at node and time
and I; (x), ... xt?' their concatenation. In the following, we assume that each worker computes
3

---

Table 1: Comparison of convergence rates for strongly convex and non-convex objectives against concurrent works in the fixed topology setting. We neglect logarithmic terms. Observe that thanks to the maximal resistance X2 I X1, our method obtains substantial acceleration for the bias term. Moreover, while our baseline is strongly related AD-PSGD [28, our analysis refines its complexity when workers sample data from the same distribution.
Method
Strongly Convex
Non-Convex
Koloskova al.
np +
VL xitt/xio wivve
+ +xx1
Lo ne
LX1
I +62
AD-PSGD 28
Baseline (Ours)
g² x
L o ty
+ Lxa
CiD? (Ours)
+ Xixos"
1 XVX2X
Tixas"
+ LyxIXI
about 1 mimiimattee biini-batchee of gradient per unit of time (not necessarily simultancously), which is a standard homogeneity assumption [18), and we denote by X the instantancous expected frequency of edge (i,j), which we assume time homogeneous.
Definition 3.1 (Instantaneous expected Laplacian). We define the Laplacian A as:
Σ
xe - e,) -
(1)
(K,)EE
In this context, a natural quantity is the algebraic connectivity (6 given by:
X1
sup | I Ax
(2)
For connected graph (i.e. X1 < +00), we will also use the maximal resistance of the network:
A sup (e, (e) - 5 xt. X2
(i.j)EE
The next sections will show that it is possible to accelerate the asynchronous gossip algorithms from Xi to /xix2 X1, while [12 or [34] emphasize the superiority of accelerated asynchronous gossips over accelerated synchronous ones.
3.2 Training dynamic
The goal of typical decentralized algorithm is to minimize the following quantity:
" inf f(x) A inf 1 -0))) inf Σ f((1)) ZERA
ZER4 T2
=:= N
For this, we follow first order optimization strategy consisting in using estimates of the gradient fz(z)) via i.id unbiased Stochastic Gradient (SG) oracles given by (F,(,,,)) {,) s.t. [VF.
fzi)); The dynamic of updates of our model evolves as the following SDE, for 77, 7, ā some time-independent scalar thyper-parametery whose values are found in our theoretical analysis and used our implementation, and d. some point processes on R with intensity dt & dP:
dz = zt)dt
- a Σ JRRJ)EE
(xt - x! >
(4)
dæt - #t)dt 7 ()
Σ
(af wd))M
5.R.JEEE

---

We emphasize that while the dynamic Eq. Dis formulated using SDEs [ which brings the power of the continuous-time analysis toolbox, it is still event-based and thus discrete in nature. Hence, it can efficiently model practically implementable algorithms, as shown by Algo. The coupling {are, #t corresponds to momentum term which will be useful to obtain communication acceleration as explained in the next section. Again, Jg V (1). {,) (E.) will be estimated via i.i.d SGs sampled N2 spikes. Furthermore, if Ti fo. then, 3 Ie and obtain tracker of the average across workers which is similar to what is achieved through Gradient Tracking methods [9]] This is key advantage of our method obtain convergence guarantees, which writes as:
dī. -1 Σ
(5)
3.3 Informal explanation of the dynamic through the Baseline case
To give some practical intuition method, consider baseline asynchronous decentralized dynamic, close to AD-PSGD 28 By considering = 0, a = à the dynamic 4 simplifies to:
dxf = (I - Σ
(x) - x ddM
(6)
j.i,)EEE
In a DL setting, x' contains the parameters of the DNN hosted on worker i. Thus, (6) simply says that the parameters of the DNN are updated either by taking local SGD steps, or by pairwise averaging with peers j. (i, E. These updates happen independently. at random times: although assume that all workers compute gradients at the same speed average (and re-normalized time accordingly), the use of Poisson Processes model the inherent variability in the time between these updates. However, the p2p averaging depends the capabilities of the network, and we allow each link (i to have a different bandwidth, albeit constant through time, modeled through the frequency X The gradient and communication processes decoupled: there is need for the other, allowing to compute stochastic gradients uninterruptedly and run the p2p averaging in parallel, as illustrated by Fig 2 Finally, (4) adds momentum step mixing the local parameters xf and momentum buffer उ' before each type of update, allowing for significant savings in communication costs, as we show next.
wait for
Cuens selp
Camp, ddy
Comm
Cemp delry
kilg
Worker
Worker
Worker
Worker 2
Worker 3
Worker
Time
Time
Figure 2: Example of worker updates in synchronous (left) and asynchronous (right) optimization methods. We remark that our asynchronous algorithm reduces idle time, and allow to communicate in parallel of computing gradient, only synchronizing two workers at a time for averaging parameters. Here, one p2p communication is performed per computation in expectation.
3.4 Theoretical analysis of A C
We now provide an analysis of our decentralized, asynchronous algorithm. For the sake simplicity, we will consider that communications and gradients spike as Poisson processes:
Assumption 3.2 (Poisson Processes), NÝ. MM are independent, Point-wise Poisson Processes. The (Ni) have rate of 1, and for (i.j) E E, MD have rate X
We also assume that the communication network is connected during the training:
5

---

Assumption 3.3 (Strong connectivity). We assume that < oc.
We will consider two generic assumptions obtained from (21] which allow us specify our lemma to convex and non-convex settings. Note that the non-convex Assumption 3.5 generalizes the assumptions of (28). by taking M 0.
Assumption 3,4 (Strongly convex setting). Each fi is j--strongyy convex and L-smooth, and:
Be (l. - o² and Σ
[VI((*)) Vf(x*)]²
1=1
Assumption 3.5 (Non-convex setting). Each is L-smooth, and there exists P, M > 0 such that:
Va Rd
Vf(x)) v[()) 2 PIV
and,
n 1 Fn E Rd
M a Rg (F,(), - V)(x))l S s o²+
n Σ |VM())
We can now state our convergence guarantees. An informal way to understand our proposition, is that while gradient updates non-convex, the communication updates are linear and thus benefit from local convexity; its proof is delayed to Appendix[C
Proposition 3.6 (Convergence guarantees.). Assume that (11, 5e follow the dynamic Eq. 4 Aand that Assumption 3.2 3.3 are satisfied. Assume that 15g = 30 Ho and let the total running time. Then:
Non-accelerated setting, pick 77 0, â and set x X1.
Acceleration 2A CiD²), we set 2/-1X2 a 2 á = / X1 and x = vx122 $ X1.
Then, there exists constant step size y 0 such that if:
(strong-convexitty the Assumption 3.4 is satisfied, then 7 161(1+x) and:
0² + (1
E [|[TT - x1 Ô |100 x x²1|26 IoLLINI
12T
(non-convexity) the Assumption 3.5 is satisfied, then there is 0 which depends only P, M from the assumptions such that 7 S T(++] and:
1 T / E [IVS(())11) dt - -OLLLNN( f(x")
L(f(zo) f(x')) (02 + (1 (1+ x)
T
Also, the expected number of gradient steps is nil' and the number of communications is TrAT
Tab. compares convergence
with concurrent works. Compared every concurrent work, the bias term of A c is smaller by factor
2 1 at least. Yet, as expected, in the non-accelerated setting, we would recover similar rates to those. Compared to (20), the variance terms held variance reduction with the number of workers; however, this should not be issue in a DL setting, where it is well-known that variance reduction techniques degrade generalization during training [15. Comparing directly the results of 2 is difficult as they only consider the
asymptotic rate, even if the proof framework is similar to 28 and should thus lead to similar rates of convergence.
3.5 Informal interpretation and comparison with decentralized synchronous methods
Here, we informally discuss results from Prop. 3.6 and compare our communication rate with state- of- decentralized synchronous methods such DeTAG BI, MSDA (37] and OPAPC (3)

---

As we normalize time so that each node takes one gradient step per time unit in expectation, one time unit for us is analogous to one round of computation (one "step") for synchronous methods. Synchronous methods such as [31 37
Table 2: # of communications per "step"/time unit on several graphs.
Method
Star n/
Ring
Complete
Accelerated Synchronous (e.g., RII (k
n²
n2
23 perform multiple rounds of communications (their Accelerated Gossip procedure) between rounds of gradient computations by using inner loop inside their main loop (the one counting "steps"), so that the graph connectivity do not impact the total number of "steps" necessary to reach e-precision. As Prop. 3.6 shows, the quantity 1+ [A [A] is factor in convergence rate. A containing the information of both the topology & and the edge communication rates Xij. this is analogous to saying VxulA|x2/ A (11) for method [alAAxx
CiD
n n
n
(I.e., the graph connectivity does not impact the time to converge), which, given the graph's '' topology, dictates the communication rate, Appendix D more details. Tab. 2 compares the subsequent communication rates with synchronous methods.
4 Numerical Experiments
Now, we experimentally compare CiiD to a synchronous baseline All-Reduce SGD (AR-SGD, see (26)) and an asynchronous baseline using randomized pairwise communications (a variant of AD-PSGD 288, traditionally used state-of-the-arr decentralized asynchronous training of DNNs)
In our case, the asynchronous baseline corresponds to the dynamic Eq. (6) Our approach is standard: we empirically study the decentralized training behavior of our asynchronous algorithm by training ResNets [17 for image recognition. Following (2), we pick a ResNet18 for CIFAR- 10 [24] and
ResNet50 for ImageNet [IT]. To investigate how our method scales with the number of workers, we
run multiple experiments using up 64 NVIDIA A100 GPUs in cluster with 8 A100 GPUs per node using an Omni-PAre interconnection network at 100 Gb/s, and set one worker per GPU.
4.1 Experimental Setup
Table 3: Training times on CIFAR (# 6s).
slpper-prramters. Training a DNN using multiple workers a cluster requires several adaptations compared to the standard setting. As the effective batch-size grows linearly with the number of workers n,, we use the learning-ran raate schedule for large batch training of [16] in all our experiments. Following (30], fixed the local batch size to 128 on both CIFAR-10 and ImageNet.
n
4
8
16
32
64
Ours AR
t (min)
20.9
10.5
5.2
2.7
1.5
(min)
21.9
11.1
6.6
3.2
1.8
101
Workers
com//V
camn
All
10
Training loss
la distnee
16
32
10-1
10
64
10-1
5000
10000
15000
20000
25000
10-3
grad steps per worker
250
500
750
1000
1250
1550
1750
grdd steps per worker
(a)
(b)
Figure 3: (a) Training loss for CIFARIO with minibatch size 128 on the complete graph, w/o A CiiD.. As the number of worker increases, the loss degrades, especially for n = 64. (b) Focus on the training loss for the complete graph of size = 64, w/o A CCiD? As the rate of communication increases, the gap with All-Reduce decreases. With 2 com/V, a test accuracy of 94.6 + 0.04 is reached.
Our goal being to divide the compute load between the n workers, all methods access the same total amount of data samples, regardless of the number of local steps. On CIFAR- 10 and ImageNet, this
7

---

This algorithm block describes our implementation of our Asynchronous algorithm with A A'C on each local machine. p2p comm. and V comp. are run independently in parallel.
Algorithm 1:
Input:
On each machine i {I,..., n1), gradient oracle fi. parameters 7), a, 0i, 7,
Initialize on each machine E [1,,..,,ii n);;
in shared memory; Synchronize the clocks of all machines;
Initialize st, Ø' --
+x', =-,6' t- 0 and put x',"', "0,," /
In parallel on workers E (1,...,n) n),
while < T, continuously do:
In one thread on worker continuously do: & < clock(); Sample batch of data via & ~ E;
VP VPi(Zs, E.):
// Compute gradients
-1 7
exp
(t t')
10
x' f x² 79:
// Apply APCiD² // Take the grad step
Ø6 t- 3. 79:
12
t' tt;;
13
In one thread on worker i continuously do:
14
t clock(); ;
15
Find available worker j
/1 Synchronize workers i and j
16
mij (x' -x));
1/
Send x² to j and receive x from
(t (t-t") 1+) exp
-17
7
/1 Apply A
x² amijj
// p2p averaging
2 z. ámiz
20
return (si)isisn
number is set to 300 and 90 epochs respectively. following standard practice 22 To circumvent the fuzziness the notion of epoch in the asynchronous decentralized setting, we do not "split the dataset and re-shuffle it among workers each epoch" as done with our standard All-Reduce baseline. Rather, we give access to the whole dataset to all workers, each one shuffling it with a different random seed. We use SGD with base learning rate of 0. momentum value at 0.9 and 5 x 10-4 for weight decay. As advocated in [16], we do not apply weight decay on the learnable batch-norm coefficients. For ImageNet training with the SGD baseline, we decay the learning-rate by factor of 10 at epochs 30, 60, 80 (cpochs 50, 75 for CIFAR- 10), and apply an analogous decay schedule with our asynchronous decentralized methods. All of our neural network parameters are initialized with the default Pytorch settings, and one All-Reduce averaging is performed before and after the training ensure consensus at initialization and before testing. For our continuous momentum, we also need to set the parameters â. For all our experiments, we use the values given by Prop. (366] As advocated, the asynchronous baseline correspond to the setting without acceleration, i.e. with 7 0 and
ā 114 whereas using A C2iDD2 leads to consider 1) 2.
} ā } \ xa'
x1.
where X1. X2 are set to their theoretical value given by 2 (3)
depending on the communication rate and graph's topology, assuming that each worker chose their peers uniformly among their neighbors (we verify empirically that it is the case in practice, see Appendix E.2
Practical implementation of the dynamic. The dynamic studied in Eq. is model dis- playing many of the properties sought after in practice. our implementation, described in Algo. [ each worker i has indeed two independent processes and the DNN parame- ters and momentum variable (**,** are locally stored such that both processes can update them at any time. One process continuously performs gradient steps, while the other up- dates {x', via peer-to-peer averaging. The gradient process maximizes its throughput by computing forward and backward passes back to back. Contrary to All-Reduce based methods that require an increasing number of communications with the growing number of workers, inevitably leading an increasing time between two rounds of computations,
8

---

we study the case where each worker has a fixed communication rate, given as hyperparameter in our implementation. We implement 3 different graph topologies: complete, ring, and exponential [28] 2) see Appendix [.. for details. To emulate the P.P.Ps for the communications, each worker samples ran- dom number of p2p averaging to perform between each gradient computation, following a Poisson law using the communication rate mean. To minimize idle time of the communication process, workers are paired with one of their neighbors in "First In First Out" manner in an availability queue (a worker available when it finished its previous averaging and still has some to do before the next gradient step). To implement this, the availability queues and the graph topology (this lightweight cluster: the coordinator only exchanges integers with the workers), but it could be done in different ways, e.g. by pinging each other at high frequency. As we assumed unit time for the gradient process in our analysis, and that real time used in our algorithm to apply our A momentum (see Algo. 1.. maintain running average measure of the duration of the previous gradient steps to normalize time.
n-16
10a
ARCID
Teiinnn
10-1
10-1
wwi.fark
10-3
grad per worker
Figure 4: Training loss for CIFARIO using a minibatch size of 128. We display the train- ing loss with up to 64 workers, w/ and w/o A A²CiD? on the challenging ring graph.
central coordinator store
4.2 Evaluation on large scale datasets
Table 5: Accuracy ImageNet for batch- size of 128. We compared a vanilla asyn- chronous pairwise gossip approach with and without A CiD2 demonstrating the improve- ment of our method. We also varied the com- munication rate.
CIFARIO. This simple benchmark allows to under- stand the benefits of our method in well-controlled environment. Tab. reports on the test set of CIFAR10, with a standard deviation consid-
numerical accuracy
calculated over 3 runs. Three scenarios ered: a complete, an exponential and a ring graph. In Fig. (a), observe that with the asynchronous baseline on the complete graph, the more workers, the more the training loss degrades. Fig. (b) hints that it is in part due to an insufficient communication rate, as increasing allows to lower the loss and close the gap with the All-Reduce baseline. However, this not the only causative factor as Tab. + indicates that accuracy generally degrades as the number of workers increases even for AR-SGD, which is expected for large batch sizes. Surprisingly, even with
#Workers
#com/#grrd
16
32
64
AR-SGD buseline
75.5
75.2
74.5
Complete graph Asyne. baseline
74.6
73.8
71.3
Ring graph Asyne. baseline A ACCII2 "Asyni. baseline A'CiD'
74.8
71.6
64.1
74.7
73.4
68.0
74.8
"73.7"
73.7
'68.2"
75.3
74.4
71.4
worse training loss for = 64, the asynchronous baseline still leads to better generalization than
Table 4: Accuracy of our method on CIFARI0 for 128 batchsize with an equal number of pair- wise communications and gradient computations per worker. We compared vanilla asynchronous pairwise gossip approach with and without A CiD? demonstrating the improvement of our method.
#Workers
8
16
32
64
AR-SGD baseline
94.5+00.1
94.4+10.1
94.5.10.2
93.7.10.3
92.8-10.2
Complete graph Asyne. baseline
94.93++..11
94.01
94.86+00.01
94.55+0001
93.38-+0.21
Exponential graph
Asyne. baseline
95.07+0.01
94.89-0.01
9..8
94.44+0.02
93.41+00.2
ACiDD
95.17+0.04
95.04=0.01
94.87+0.02
94.56+0.01
93.47+0001
Ring graph
Asyne. baseline
95.02=0.06
95.01
95.00+0.01
93.95+0.11
91.90+0.10
A C
94.25+0.02
95.01 +0100
95.03+0.01
94.61+0.02
93.08+00.0

---

AR-SGD, and consistently improves the test accuracy across all tested values of n. The communica- tion rate being identified as critical factor large scale, we tested our continuous momentum on the ring graph, each worker performing one p2p averaging for each gradient step. Fig. 4 shows that incorporating A CiiD leads to significantly better training dynamic for a large number of workers, which translates into better performances test time as shown in Tab.
60
ARCID*
com comiy
ARGID* Wo
n1:12
wio "CCD?
10
1/ disisncce
101
10
2x
10P
10
10
10000
20000
30000
40000
50000
5000
10000
15000
20000
25000
gnd steps per worker
stops per
(a)
(b)
Figure 5: (a) Training loss for ImageNet using 128 batch size, with an equal number of communica- tions and computations per worker. We display the training loss for various number of workers (up to 64), using A Cii?? for the ring graph. (b) Comparison of consensus distances when A CCiD is applied versus doubling the rate of communications on the rign graph with 64 workers: applying A'CiD² has the same effect doubling communications.
ImageNet. For validating our method in real- life environment, we consider the large-scale ImageNet dataset. Tab. 6 confirms the advan- tage of asynchronous methods by allocating less compute to the slowest workers, leading to faster training times. Tab. reports our accuracy for the complete and ring graphs. As X1 X2 for the complete graph, we simply run our baseline asynchronous method for reference. The case of the ring graph is much more challenging: for n = 64 workers, the accuracy drops by 10% compared to the synchronous baseline given by AR-SGD. Systematically, with A the final accuracy increases: up to 4% absolute percent in the difficult = 64 setting. This is corroborated by Fig. 5 which indicates that incorporating A ACCiD signifi- cantly improves the training dynamic on ImageNet. However, for reducing the gap with the AR-SGD baseline, it will be necessary to increase the communication rate as discussed next.
Table 6: Statistics of runs on Imagenet with 64
workers (for ours, on the exponential graph).
Method
(min)
V
# V
slowest worker
fastest worker
AR-SGD
1.710"
14k
14k
Baseline (ours)
1.5 10a
13k
14k
('CrD((ours)
1.5 10
13k
14k
Consensus improvement. The bottom of Tab. as well as Fig. (b) study the virtual acceleration thanks to ACCDD" Not oolonl increasing communications combined with A ACCiD" allows to obtain competitive performance, but Fig. shows that doubling the rate of communication has an identical effect on the training loss than adding A CCii" This is verified in Fig. (b) by tracking the consensus distance between workers: A ACiD? significantly reduces it, which validates the results of Sec. 3.4
5 Conclusion
In this work, we confirmed that the communication rate is a key performance factor to successfully train DNNs at large scale with decentralized asynchronous methods. We introduced A² &CCiD a continuous momentum which only adds minor local memory overhead while allowing to mitigate this need. We demonstrated, both theoretically and empirically, that A A'CiD substantially improves performances, especially on challenging network topologies. As we only focused on data parallel methods for training Deep Neural Networks in a cluster environment, in future work, we would like to extend our empirical study to more heterogeneous compute and data sources, as our theory could encompass local SGD methods 39 and data heterogeneity inherent in Federated Learning [33].
10

---

Acknowledgements
ADONIS and EMERG- ADONIS from Alliance SU. This work was granted access the HPC/AI resources of IDRIS under the allocation AD011013743 made by GENCL EB and AN acknowledge funding and support from NSERC Discovery Grant RGPIN- 2021-04104, FRQNT New Scholar, and resources from Compute Canada and Calcul Quebec. In addition, the authors would like to thank Olexa Bilaniuk and Louis Fournier for their helpful insights regarding code implementation.
EO, AN, and EB's work was supported by Project
References
[1] L. Amold. Stochastic differential equations. New York, 1974.
[2] Assran, Loizou, Ballas, and Rabbat. Stochastic gradient push for distributed deep learning. In International Conference on Machine Learning, pages 344-353, PMLR, 2019.
[3] E. Belilovsky, M. Eickenberg, and E. Oyallon. Decoupled greedy learning of cnns. In International Conference on Machine Learning, pages 736-745. PMLR, 2020.
[4] E. Belilovsky, L. Leconte, L. Caccia, M. Eickenberg, and E. Oyallon. Decoupled greedy learning of cnns for synchronous and asynchronous distributed learning. arXiv preprint arXiv:2106.00 06401, 2021.
[5] M. Blot, D. Picard. M. Cord, and N. Thome Gossip training for deep learning. In Advances in Neural Information Processing Systems, volume 30, 2016.
[6] S. Boyd, A. Ghosh, B. Prabhakar, D. Shah. Randomized gossip algorithms. IEEE Transactions on Information Theory, 52(6):2508-25.5 2006.
[7] Chen, X. Pan, R. Monga, S. Bengio, and R. Jozefowicz. Revisiting distributed synchronous sgd. arXiv preprint Xrviv 1oXi:/664..0000 1604660941, 2016.
[8] J. Daily, A. Vishnu, C. Siegel, T. Warfel, and V. Amatya. Gossipgrad: Scalable deep learning using gossip communication based asynchronous gradient descent, 2018.
[9] J. Dean, G. Corrado, R. Monga, K. Chen, M. Devin, M. Mao, M. Ranzato, A. Senior, P. Tucker, K. Yang, et al. Large scale distributed deep networks. Advances in neural information processing systems, 25, 2012.
[10] A. Defazio, F. Bach, and S. Lacoste-Julien. Saga: A fast incremental gradient method with support for non-strongly convex composite objectives. Advances in neural information processing systems, 27, 2014.
[11] Deng, W. Dong. Socher, L.-J. Li, Li, and L. Fei-Fei. Imagenet: large-scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pages 248-255. leee, 2009.
[12] M. Even, R. Berthier, F. Bach, N. Flammarion, H. Hendrikx, P. Gaillard, L. Massoulié, and A. Taylor. A continuized view on nesterov acceleration for stochastic gradient descent and randomized gossip. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, 2021.
[13] M. Even, H. Hendrikx, and Massoulic. Decentralized optimization with heterogeneous delays: a continuous-time approach. arXiv preprint arXiv:2106.0335 2021.
[14] A. Ghosh, S. Boyd, and A. Saheri. Minimizing effective resistance of graph. SIAM Review, 50(1):37-66, 2008.
[15] R. M. Gower, M. Schmidt, F. Bach, and P. Richtárik. Variance-reduced methods for machine learning. Proceedings of the IEEE, 1968::1968-1183 2020.
[16] P. Goyal, P. Dollár, R. Girshick, P. Noordhuis, L. Wesolowski, A. Kyrola, A. Tulloch, Y. Jia, and K. He. Accurate, large minibatch sgd: Training imagenet in hour. arXiv preprint wwXiv:1706.0666 2017.
[17] K. He, X. Zhang, S. Ren, and Sun. Deep residual learning for image recognition. 2016 IEEE Conference on Computer Vision and Puttern Recognition (CVPR), pages 770-778, 2015.
[18] H. Hendrikx, F. Bach, and L. Massoulie. An accelerated decentralized stochastic proximal algorithm for finite sums. In H. Wallach. H. Larochelle, A. Beygelzimer, F. d Alché-Buc Buc. E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.

---

[19] A. Koloskova, T. Lin, and S. U. Stich. An improved analysis of gradient tracking for decentralized machine learning. Advances in Neural Information Processing Systems, 14:11422-11435, 2021.
[20] A. Koloskova, T. Lin, S. U. Stich, and M. Jaggi. Decentralized deep learning with arbitrary communication compression. arXiv preprint 1rXiv:1907.0000 197709336, 2019.
[21] A. Koloskova, N. Loizou, S. Boreiri, M. Jaggi, and S. Stich. unified theory of decentralized sgd with changing topology and local updates. In International Conference on Machine Learning, pages 5381-5393, PMLR, 2020.
[22] L. Kong, T. Lin, A. Koloskova, M. Jaggi, and S. Stich. Consensus control for decentralized deep learning. In International Conference Machine Learning, pages 5686-5696. PMLR, 2021.
[23] D. Kovalev, Salim, and P. Richtarik. Optimal and practical algorithms for smooth and strongly convex decentralized optimization. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 18342-18352 Curran Associates, Inc., 2020.
[24] A. Krizhevsky. Learning multiple layers of features from tiny images. 2009.
[25] A. Krizhevsky, I. Sutskever, and G. E. Hinton. Imagenet classification with deep convolutional neural networks. Commun, ACM, 64-6)84-90, may 2017.
[26] S. Li and Hoefler. Near-optimal sparse allreduce for distributed deep learning. Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 135- 149, 2022.
[27] X. Lian, C. Zhang, H. Zhang, C.-J. Hsieh, W. Zhang, and J. Liu. Can decentralized algorithms outperform centralized algorithus?? ? a case study for decentralized parallel stochastic gradient descent. Advances in neural information processing systems, 30, 2017.
[28] X. Lian, Zhang, C. Zhang, and Liu. Asynchronous decentralized parallcl stochastic gradient descent. In International Conference on Machine Learning, pages 3043-302 444-- PMLR, 2018.
[29] T. Lin, S. P. Karimireddy, S. U. Stich, and M. Jaggi. Quasi-global momentum: Accelerating decentralized deep learning on heterogeneous data. arXiv preprint 140,,401,,, 2021.
[30] T. Lin, S. U. Stich, K. K. Patel, and M. Jaggi. Don't ton't use large mini-batches, use local sgd. In International Conference on Learning Representations, 2020.
[31] Y. Lu and C. De Sa. Optimal complexity in decentralized training. In M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 7111-7123. PMLR, 18-2 24 Jul 2021.
[32] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas Communication--fliceenn learning of deep networks from decentralized data. In Artificial intelligence and statistics, pages 1273-1282, PMLR, 2017.
[33] H. B. McMahan, F. Moore, D. Ramage, S. Hampson, and B. A. Arcas. Communication-cfficenn learning of deep networks from decentralized data. International Conference on Artificial Intelligence and Statistics, 2016.
[34] A. Nabli and E. Oyallon. DADAO: Decoupled accelerated decentralized asynchronous optimization. In A. Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato, and J. Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 25604 226266. PMLR, 23 Jul 2023.
[35] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradhury, G. Chanan, Killeen, 7. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopf, E. Yang. Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala. Pytorch: An imperative style, high-performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 1024-8035
Curran Associates, Inc., 2019.
[36] Ryabinin. E. Gorbunov, Plokhotnyuk, G. Pekhimenko. Moshpit sgd: Communication-effice decentralized training on heterogeneous unreliable devices. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang. and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, Curran Associates, Inc., 2021.
pages
12

---

[37] K. Scaman, F. Bach, S. Bubeck, Y. T. Lee, and L. Massoulié. Optimal algorithms for smooth and strongly convex distributed optimization in networks. In Precup and Y. W. Teh, editors, Proceedings the 34th International Conference on Machine Learning, volume 70 Proceedings of Machine Learning Research. pages 1027-3036. PMLR, 06-11 Aug 2017.
[38] A. Sergeev and Balso. Horovod: fast and easy distributed deep learning TensorFlow. arXiv preprint w 2018.
[39] S. Stich. Local SGD converges fast and communicates little. International Conference on Learning Representations, 2019.
[40] S. Stich. Unified optimal analysis the (stochastic) gradient method, 2019.
[41] T. Vogels, L.. He, A. Koloskova, S. P. Karimireddy, T. Lin, S. U. Stich, and M. Jaggi. Relaysum for decentralized deep learning on heterogeneous data. Advances Neural Information Processing Systems, 34:28004-2888 28015, 2021.
[42] Y. Yakimenka, C.-W. Weng. H.-Y. Lin, Rosnes, and J. Kliewer. Straggler-resilient differentially-privaee decentralized learning. In 2022 IEEE Information Theory Workshop (ITW), pages 708-713. IEEE, 2022.
[43] Ying. Yuan, Chen, H. Hu, P. Pan, and W. Yin. Exponential graph is provably efficient for decentralized deep training, Advances in Neural Information Processing Syxtems, 34:13975-13987, 2021.
[44] B. Ying, K. Yuan, Hu, Chen, W. Yin. Bluefog: Make decentralized algorithms practical for optimization and deep learning, arXiv preprint arXiv2111.00287. 2021.
[45] B. Ying. K. Yuan, Hu, Chen, W. Yin. Bluefog: Make decentralized algorithms practical for optimization and deep learning. 2021.
[46] Y. You, Gitman, and B. Ginsburg. Large batch training of convolutional networks. arXiv preprint arXiv: 1ee::070888888 2017.
[47] Yuan, He, J. Davis, Zhang. T. Dao, B. Chen, P. Liang, Re, and C. Zhang. Decentralized training of foundation models heterogeneous environments, Advances in Neural Information Processing Systems, 35:25464-25477, 2022.
[48] S. Zhang, A. E. Choromanska, and Y. LeCun. Deep learning with clastic averaging sgd. In C. Cortes, N. Lawrence. D. Lee, M. Sugiyama, and R. Garnett, editors. Advances in Neurul Information Processing Systems, volume 28, Curran Associates, Inc., 2015.
13

---

Appendix
Table of Contents
Notations
14
B Technical Preliminaries
14
Proof the main result of this paper
C.I
Some useful upper-bounds)
17
Resolution: putting everything together
................................
20
Optimizing the step-size
22
Comparison with accelerated synchronous methods
Experimental details
24
E,1
Graph topologies
24
Unitorm neighbor selection check
24
A Notations
For n E N* the number of workers and d E N" an ambient dimension, for all > 0, the variable Te E Rexd is a matrix such that 2; = [xt, x; T with x Rd for all E {I,... n2.. We remind that 1 is the vector ones such that the matrix Frobenius norm, we write т = 11 the projection so that || = Σm ||,, 2
Σ 24 1 Rd. With I the identity and ||.
For continuously differentiable function f: Rd and a, b E TRd, the Bregman divergence defined with dy b) ʃ(a) f(b) (VS(b), b). For A E Raxx, we denote by A its pseudo
inverse. For positive semi-definite A E R and Raxd, introduce ||~=1] & Tr(x Ax) and 11/2 its square-root. We recall that the connectivity between workers is given by set of edges E, and denote by e; the jth basis vector of TR..
For Raxd, we introduce:
Fx)x) A [Vi(zz). (Z.)) Rad and VF(x & (1) Van [n)l" Raxd
Finally, to study the gradient steps taken each individual worker independently, we introduce:
Vi,(,, A [o,...0, VE(2,, (,, 0, ojT e 1xd
B Technical Preliminaries
We recall some basic properties that we will use throughout our proofs.
Lemma B.1 (Implications of Assumption 3.4p. If each f; is u-strongly corvex and L-smooth, we have, for any 0, b Rdd
Vf((a) V (a, - L
112..12
2L
and
/
2 a 2ll2 < dz. (a, b) <
1
V/((a) 2/
2μ
14

---

Lemma B.2 (Generalized triangle inequality). For any b, E R and continuously differentiable
function f R IR, by definition of the Bregman divergence, we have:
d)(0,b) + + v, -
Lemma B.3 (Variance decomposition). For a random vector a E R and any E Rd, the variance of can be decomposed as:
E [||a - E[a]]]]] = [|Ia b11 [[] b1l
Lemma B.4 (Jensen's inequality). For any vectors d1,--,, On E IRd, have:
Σ
|
a2
n8
Lemma B.S. For any vectors a, E IRd and >> 0:
2(a, b) S a |a||
Lemma B.6. For any vectors a, E d and 0:
||a - b112 < (1 + lall + +1+a 1bbB
Lemma B.7. For any A E Raxd and B Rax have:
|BA| 3 |
Lemma B.8 (Effective resistance contraction). For (i,j) E E and any Rxxd we have:
(le: e;)(e; -e,) =x) S xal((e= ez)(e; - -e,
Proof. Indeed, we note that, by definition of X2 3
[l(e, - e, =213= = Tr (x (e: - e,) - ez) A
(q. TA
e,)(e - xx)
(7)
S 2x2 (x (e: (e)e =x)
(8)
x2ll(er e;)(e; e 1= Tx1
Lemma B.9, For any x E nxd and A the Laplacian of a connected graph, we have:
x*I((e ((fle-e;))ee -x) 2||==||A
(UJ)E
Proof. Indeed, by definition of the Laplacian 3.1 we have:
Σ x e,)((e 221
Σ
Ar (=T -e)((e -e) -e,((e T2)
(6,))E
(i,
(10)
=2 Σ
A (x - c;)(es - -c,)
(11)
(WJ)EE
2Tr
TT Σ
(12)
(1J)EE
15

---

Lemma B.10. For any E R and A the Laplacian of connected graph, we have:
2TT v) S 7 1|l1 + 4x1llvIl
Proof. By property of the Laplacian a connected graph, we have that = (A+) Thus:
2 T.. y)
2(A xr, (A+)*//))
(13)
B.5
1A1/2x117 41((A+)/2211+
(14)
1 =| + 4x111112
(15)
C Proof of the main result of this paper
We remind that we study the following dynamie:
dæt = xz)dt 7 f VP.(() - a E (x - vf)dM
J((J)EE
dž. =n<xi zt)dt / VF((E) ā Σ - x/)dMM
SABJEE
which simplifies to:
dx = -7 / VF((s)
Σ (at x.)dM
JAFJEEE
if A CiD is not applied. We also recall the main proposition, which we prove next:
Proposition C.1 (Convergence guarantees.). Assume that {I,, Øe. follow the dynamic Eq. and that Assumption 3.2 3.3 satisfied. Assume that 15g = 20 = 5o and let T the total running time. Then:
Non-accelerated setting, we pick 17 0, â 2 and set x X1.
Acceleration (A (CD),, we set 2/xix2 2 ā = 1 // X3
and x vXX2 $ X1-
Then, there exists constant step size y 0 such that if:
(strong-convexitty the Assumption 3.4 4 is satisfied, then < TeL(1+x) and
[|| x 11
5 1100 x x11 I61(1x1]
12T
(non-convexity) the Assumption 3.3 is satisfied, then there is which depends only on P. M from the assumptions such that L(x+TJ and:
@ (11+ (f(zo) - f(x")) + T
1 T Jo
E [[V o
L(f(zo) - f(x')) (02 +1+ x1+
T
Also, the expected number of gradient steps is nil' and the number of communications TY
Ö O-notaaionn hides constants and polylogarithmic factors.
16

---

Proof. The core of the proof is to introduce the appropriate Lyapunov potentials @& (t, X), where X could be (z, .) x depending on whether we apply A CiD" or not. If we apply A CiD? we
introduce the momentum matrix A 7 - Then, by Ito's lemma, given that all the functions
are smooth, and remembering that all Point-wise Poisson Processes N2 have unit intensity, that the M have intensity A and that they are all independent, we obtain in similar fashion to [12 34
(T, (0) /- Otox(t, + (AX,, Ox (t, dt
lerrn
Φk t, t, - V ( (i, ())
ON Xt, dtd
1=1
variation independent gradient update
Φb (,
aale; - ( e,)(e; =z) ā(e; - ee)( =)) ) )
ox
(x)) Xz)
1 dt
(1,))E
variation due to cach independent p2p communication
+M,,
where M1 is a martingale. In the case where C'CiD is not applied, we set A = 0 to remove the momentum term, and all updates are done only along x as there is no ă. We remind that:
L. e du
(E -1 1)
(16)
now present our choice of potential for each cases:
For the convex case in the non-accelerated setting, we introduce:
<1,t,x) A A
x1 -
For the convex case with A CiDD we introduce:
(2 x, A Arl x11 + B,I π. B.lla
For the non-convex case in the non-accelerated setting, introduce:
x²) @ x) A,dy (ā, + By T
For the non-convex with A CiDD? we introduce:
(x(t.)) e Aid, B, 1T 1.
C.1
Some useful upper-bounds
As the same terms appear in several potentials, we now prepare some intermediary results which will be helpful for the proofs.
Study of the | - x² terms:
First, we study the variations in the || 22 term appearing in Φn and Φ2- As the up- dates due the communication in the orthogonal of 1, it is only necessary study the variations induced by the gradient steps. Thus, we define:
o
(V(((, - x²1
||
17

---

We note that (f((2,)) 1
(Z Et). which, using E; Vz((=*) 0, leads to:
n
2
( x², Vf((z))) + 23 (I
E En
Ax
(17)
11
21 (i- x² (z;) Vf((')) + 3/2 Eg (
(18)
Y1
1=1
34
0
+
Σ
29 i x¹, Vf(aa)) vf((=))) + -
V f(()))1
(19)
n²
-=1
82
2 0
+
Σ
n
27
[d (2, + (2",("" - dz + n2
[f(()))]1
11
n
i=1
(20)
B4
2
27
2
+
(d/. (z) + d, 221) (5, 2.))
11
n
i=1
27
27² V )?
f((")))
V (z,))
(21)
n2
n²
81
72
27²
27 (E, + dr (x" xx) (z, +
4T,
0²
d (x" 2x))
n
n
n
(22)
B1
702 2
2-
Ly
27
4
c² - 7111= - x²1 +
|
1/3 +
+
dg (x",,))
n
n
n
n²
i=1
(23)
Study of the d3 x²)
terms:
Next, using the same reasoning as for Aæ, we also need to only study the gradient updates in the non-convex setting for the first part of d3, Φ1. Thus, we set:
A A
Σ dz - - &i,,,,),,,,,)))) -dd--ddllo (z))
(24)
First, it is useful to note that under Assumption 3.5 using B.3), we have:
Es VV S no² + +1++ M) Σ [a,)))
(25)
Then, using E, fz(==") = 0 and the L-smoothness of f = E, ft. we get:
B Eo
[
Eldy
(V..(t)) 3 (\()
- VF (),,
(26)
B.T
I 2 [2
V
(x; 1P - 2 n2
(V)(E))) ()(T))
(27)
2n
25
T
0²
||
Σ
M+ (+(())))1
7
(Vf((a)) Vf.(2) ((())
2n
2n²
n
(28)
Tn²
2n
0²
+
2n
7
|
Tx
F
7
2
+
M+1
2n² I^² [
(29)
18

---

As we also have:
Vf(a))ll 3(1V).(()))
(30)
3L +
+ 3n 2 P)]
(31)
We get in the end:
E E [Af]
LS 0²22 +
3(M + 1)
222 +
(3(M + 1),
L3a2 +
-12
||
2n
2n
2n²
2n
3(M 1)
(1 P|
|VS(+)|
(32)
2n
Remark C.2. As observed in 5 note that for both the terms | - -0-x"11 and d ("),, we are
considering 7 and _11 π = 0, Poisson updates from the communication process amount to zero.
Moreover, as 1,11 (z Ø) 0, the update from the momentum is also null for these terms.
Study of the
| terms:
We get from the Poisson updates for the gradient processes:
Eg Egg.....n
Σ T| - -V,, - || 11 = (TT VF(x)) + Σ E E | (x)
(TZ VF(z)) + + E...... /F ().
and, using the definition of the Laplacian A (3.1 we get from the communication processes:
Σ 1 (1]( - a(e - e,)(es -e)) 1) T | = -2 Az) +
Σ
X - ee) ez)
(K))E
(K.)EE
B.Y
-2( Ax) + 2a 2|x11
2a< 1
Putting together both types of Poisson updates, we define:
E E[A,] A 2TT VF(x)) + + TE II 8)12 + 20(a - 1) |>|1=/11
(33)
B.ID
4x1 V + (1 (2-20(1 20(1 - an) ||~|1/ +, B Fr, 1)
(34)
For = 1 get:
[ S 4x
|| ? + 2
[VF(z,))
(35)
4x1
For 2 A2CiD2 we add the momentum term (n(a - x), 2mx)) to define:
A1 A 2n( nx) 2 (T(TT, VF(x)) + + 2 E...... (V(2, O) + +a(a
1)
(36)
6.5
? | + 2 > - 2a(1 - a)]l=l/AA + ?
(Z, πσ)
(37)
Study of the | terms:
19

---

These terms only appear in the Lyapunov potentials used when applying A CiCi?? the Poisson updates and momentum, we get:
From
A 2ny(2 - -- A (F( + + 2ā(TT,
+ á
Σ (E,))EE
(38)
Taking the expectation and using (B.9) B.8
B.
B.5
leads to:
2
E[AA] S XI + 2 "
|
A+
2
+
XI 7
( - 2ā(Tx, 3)
7
+ 2x20 |= + X1 2 E........
VF(x,
(39)
C.2 Resolution: putting everything together
In this part, we combine the terms for each potential. We remind that with Assumption 3.4
Es, (T,
no²
[f(+)))]
(40)
< no=2
2[(x)((>*> - +2
(41)
i=1
S no² + 2n + 4L Σ d,,
(42)
Convex case, no-aaceleratee.d
We remind that
$1 (t, xr 8) = A.I x²1 2 B, |=
Then, using
23
35
and defining v 0.01 (t,, X2) + E[4, Ar r + B, we have:
V
x² 122 (41 (n)
(43)
L A: - 4x1
|| 2 By +
B₁
(44)
n
(-2x))
2% A,
4L
(1 x1)
A₁ 4T. (4x17² +23)
+)3) B.
(45)
n²
7²02
27 (2)
A, + (m²20² 2n 2 (4x17? + +2)) B,
(46)
n
n
We pick a 3 B₁
Ar, with At = rt (we denote by the rate of the exponentials A,, B,).
Then
44p imply:
r r min(wry, 4x1
LT)
(47)
As we want 45) to be negative, we have:
2T
+ 7
2L(xx x 00
(48)
n
which leads to:
(49)
2L
1
4x1 +1)
n
and taking 7 S 1 21(3+4x1-1) 161(1+x1)
works. Now, as 4x1
1 1a
3
and W47 S
1 we
16x1
16x
pick pay. As have:
1/"' (A/lla,- x012 Bill + A.E Arl + B,E(Ar]) dt
E [0 (T, (T) hu 20,
(50)
using 46 and 16 leads to:
1 - + 02 n
{ 2 - 4x1 +D) (51)
E ā. x 11? I e rut |1ā0 --
n
20

---

Convex case with A'CiD'. We remind that
x, = ArI - x=12 + Be|| + B.
Then, using
37
39 and defining 1/2 _ 0z + E(A, + B, + B, we have:
2/2
S
x
(A, mt)
(52)
B + I7 A. 2
3 nB + B.)
||
(53)
|
(Bi ).
(54)
|| X2 - 20(1 a)) B1)
(55)
(ū,T))
(21 -2aB.)
(56)
(- 22
4
(272 +
(27²
df xx:)
A, +
Ar + 4T.
(Br + +Be+xIBi) xI
(57)
n²
"1
1=1
72002 +
27² {2)
27²
As
1n7202 2m²
(B, + 11)
(58)
n
Then, we assume a = 1.a ā =
XL X 11 = 2/x B = _,, B, = 1 Br, A. = e-r (we denote
V/
by the rate of the exponentials A,, B₁, Be), which satisfies (55) and (56). imply:
Then (52).
(53).
(5)
r min(wr 17 17
2'2 2'2
Ln) min(ur, 2 L7)
(59)
As we want 57 to be negative, we have:
2L
2
-1
+
AL
- +1
00
(60)
n1
1
which leads to:
1
7 S
(61)
2L 7 + 4 +2 7)
and taking 7 S 31(6+5+2)
works. Now, we have:
161 (oi(I+vixg) vxna
!- In 2
1
4XXIXe
3
(62)
2
4 XIx2
16 (1 Vx1x2)
X
As 2oy S 16l + xxxx
/
S 16xxxxx''
taking r = joy works. Finally, using (58) and 16 leads to:
Eli, - 2 < e uu
|1 - x 2²112+ + 2 2 m
+ ? 1
02 1 - 2) + 2c 1 + 8 8 + 2)
(63)
Non-convex case, non-accelerated. We remind that: (3(1,2)) A.d, (ā, x²) + Bel [
Here, we pick a = A, = B, = 4A, Thus, Ab = B = 0. Then, using 32 we obtain:
33
3
25
A,E|A BEE)) & |f
(-
7 Ae +
3 2n
I 1)(P + 1)A, 3n>2(4xx M + 1)(P 1)B,
(64)
1,2g
3
1
||
(1
+
(M +, + +M + +1)B
Bt
2n
n
4x1
(65)
+72 (02 - -3(M + +){3)
L
Ar mB..) 2
(66)
2n
21

---

Our goal is to use half of the negative term of (64) to cancel the positive ones, so that there remains at least (+)] in the end. Thus, we want:
y (M + ()(P + 11 (4XI + M +)(++))) < 2
(67)
2n
and taking S 1PP works. We verify that with > defined as such, 66 is also
negative. Finally, we upper bound (66) with 3L,² (o² + 3(M + +1+ 4x:) As we have:
(T (T, XT) - (0 20)) - [ (A,d)(E,, + B 12 + |,E + -) dl (68)
we note that if y S +Ix++1 for some constant c which depends on M, P, we will get:
7 | di - ||wool + + (1 x1)
(69)
4
which also writes:
1
4 7T (11=0=
T ( S
(70)
Non-convex case, with A CiD? We have:
Φ (1, x:) = A,dy (ī, x²) + B, |.:0 + B, 1
Here, pick = - अर A, 1, B, = #,,
B, Xi B, and identical reasoning to
the convex setting allows to say we can find constant e > 0 such that i S T(+/Xia)) then:
T 1 E (() = o (f)0o f(x)))(())))
Ly(o +1+ vxxxe)3))
(71)
C.3 Optimizing the step-size
In this part, follow 40 21 and optimize the step-size posteriori. We set X X1 for the non-accelerated setting and XxX2 with C
Strongly- cases: From 51 and
63
can write that, for < 16111+X] and initializing
Ti such that mzp have:
E
x²1
O
|1ā0
+0
(72)
Then, taking the proof of [4 and adapting the threshold, we consider two cases (with A
|/ - x I1:):
if 16L(1+x) log(max 2ooTr////")) then we set log(max( (2. T (o²))
In this case, gives:
1u2T (0² (1
B x
E
52 +1
(73)
Jog(max (2)(maax(2,n""1222 (2,1"
then we set y 16L(1+x)
16L(1+x)
af
Then,
722 gives:
Pr x
2 =
The ToLLLX +
(02 (2+x2((+00))
(74)
16L (1 + x)
The
AT
+ n²T
(02 + +2(
(75)
22

---

Non-convex cases: From 70 and (71) we can write that, for some constant >> 0 depending on M, such that y I [[+x) we have:
1 T VlV = (- f())) +1+++
(76)
Then, taking the proof of Lemma 17 in [1] and adapting the threshold, we consider two cases (with fo & f(xo) f(x*)):
1/2
if [[1+x) T
then we take 7 -(1+x)' giving:
7 / B[]
L(1 + x)
fo
1/2
du
T fo +
(02 + (1 (1+ +x++))
TI(02 (1+
(77)
[(1 +
Lfo (o² (1 (1+
=0
fo V
(78)
T
1/2
1/2
if [[1+X] z T
,then we take y (T((0+((+21333)
fo
giving:
T
So
TL(o² + (1 x)(3)
1/2
1.5o
T J |[[b)( di = 0
T
fo
+
V
T
(02 + (1 + x)63)
(79)
=0 =o(v Lfo (o2 (1 (1+x)(3)
(80)
D Comparison with accelerated synchronous methods
By definition of A 3.I our communication complexity (the expected number of communications)
per time unit. As discussed in Sec. 3.5 our goal is to replicate the behaviour of accelerated synchronous methods such as DeTAG BT MSDA (37] and OPAPC [23
simply given by
by communicating sufficiently so that the graph connectivity does not impact the time to converge, leading to the condition /xx[A|x2[A] = (1).
Now, let us consider gossip matrix W as in 31 37 23 its Laplacian C I, W. Then, using A (1).
(i.e., W is symmetric doubly stochastic) and Xi [C) [2 is sufficient for having Vxi
Synchronous methods: between two rounds of computations ("steps"), the number of
[gl communication edges used is Vi-o with 0 = max max [|Aa), [Aa]) the eigenvalues of W.
Ours: the number of communication edges used per time unit for our method is Tr(A)
1 Xi (C))
As, in
31
37 23 each communication edge is used at the same rate, can apply Lemma 3.3 of
34
stating:
vxi ())) VIl 1)[E We have:
Wi is stochastic:
|| 2.
the graph is connected: n 11 < [/].
definition Xı and 0 < x
Thus, \xi([)xa(41MM)) < V
VI-0" which proves that our communication complexity per time unit
is at least good any accelerated synchronous method.
23

---

E Experimental details
E.1 Graph topologies
30
Figure 6: The three types of graph topology implemented. From left to right: complete, exponential, cycle, all with nodes. From left to right, the approximate values (X) with a communication rate of "I p2p comm./V comp." for each worker are: 11, (2, 1), (13,
Fig. displays an example of each of the three graph topologies implemented. The exponential graph follows the architecture described in [28 2 Note the discrepancy between the values of X1 and X2 for the cycle graph, highlighting the advantage of using A "CiiD"i the asynchronous setting (to lower the complexity from X to /XIx2).
E.2 Uniform neighbor selection check
Heat-map of the communication history (showed through weighted adjacency matrix) during the asynchronous training on CIFAR10 with 32 workers. We display the results for the complete graph (left), exponential (centre) and ring (right) graph.
Figure 7:
Our asynchronous algorithm acts as follows: to reduce latency, the first two workers (i.e., GPUs) in the whole pool that declare they are ready to communicate (i.e., finished their previous communication and have to perform more before the next gradient step) are paired together for p2p communication they are neighbors the connectivity network. During training, we registered the history of the pairwise communications that happened. Fig. 7 displays the heat-map of the adjacency matrix, confirming that our assumption of "uniform pairing among neighbors" (used to compute the values of X1. X2) seems to be sound.
24


Reviews:
[{"review_id": "jRFYWGJFoa", "reviewer": "Reviewer_fkqi", "summary": "This work introduces a new method for decentralized optimization that leverages the notion of continuous momentum to speed up its convergence. The method is justified with theoretical analysis and large-scale experiments on the ImageNet dataset.", "questions": "* In L197, what is the connection speed between the nodes?\n* What was your motivation for choosing the ring graph topology in the experiments? Is this topology frequently used in practice for peer-to-peer networks?\n* Is it correct that you consider standard All-Reduce to be a centralized method? (e.g., L80) From my understanding, there is no central worker involved when aggregating updates with this family of algorithms", "limitations": "I did not see any explicit discussion of limitations of the work: I would be happy if they mentioned the applicability of their method to models with a larger parameter count (for example, Transformers with hundreds of millions or billions of parameters).", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "* The work studies an important problem of distributed training over communication-constrained networks\n* The results of authors have both theoretical justification and empirical validation in a large-scale setting\n* Overall, the approach is clearly explained and the contributions are easy to understand", "weaknesses": "* The primary disadvantage of the proposed method is its memory overhead. Having an additional copy of model parameters on each worker is quite expensive for models where the memory footprint of the parameters dominates that of the activations (in particular, for Transformer models). As a result, it might be quite difficult to apply A$^2$CiD$^2$ to models beside convolutional networks (for example, to train modern language models), which are a highly popular area of application for distributed training\n* I feel that the statement in L241 needs to be clarified. All-Reduce methods indeed require more *connections* with the growth in the number of workers, but the total amount of bandwidth is asymptotically independent of the network size for methods like Ring All-Reduce\n* From my understanding, momentum acceleration for decentralized DL has already been studied in the past (e.g., [1], which has been cited in the submission), although the underlying frameworks are clearly different. I think this work needs to more explicitly distinguish their approach from the QG-DSGDm and other results (e.g., [2]), and ideally include those methods as an additional baseline on top of AD-PSGD\n\n[1] Quasi-Global Momentum: Accelerating Decentralized Deep Learning on Heterogeneous Data. Tao Lin, Sai Praneeth Karimireddy, Sebastian U. Stich, Martin Jaggi. ICML 2021\n\n[2] SlowMo: Improving Communication-Efficient Distributed SGD with Slow Momentum. Jianyu Wang, Vinayak Tantia, Nicolas Ballas, Michael Rabbat. ICLR 2020", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer fkqi for acknowledging the importance of the problem studied and remarking that our theoretical and practical contributions are clear. Among those, we would like to emphasize that obtaining an accelerated rate of communication in the **asynchronous** setting is non-trivial, and mostly ignored in the literature. We thus consider our work to be an important contribution to the field.\n\n**Weaknesses:**\n\n*1) Memory overhead of an additional copy of the model dominates the activations memory*\n\n\nWe respectfully disagree with this statement. As their activations memory usually scales with the *squared of the sequence length*, the activations memory requirements of Transformers dominates the memory footprint, which led to many work to consider new methods to reduce this activation cost (see e.g,  [ [ 1, ]( https://arxiv.org/pdf/2111.11124.pdf ) [ 2 ]( https://arxiv.org/pdf/2205.05198.pdf ) ] ). We emphasize that our method only uses the second set of parameters as a *\"memory bank\"*: our second \"model\" does not perform any computation (no forward nor backward), and only one optimizer is needed (see eq. 4 and l.9 of Algorithm 1). Therefore, our method needs the memory requirement for only one set of activations and gradients. Thus, it is virtually at no cost in terms of speed (no additional heavy compute), and no cost in terms of memory (the memory for activations dominating the storing of parameters).\nFinally, remark that *any* algorithm that uses SGD with momentum is also doubling the number of parameters in memory: that is the cost of storing the momentum variable in the optimizer. Thus, our method is completely analogous to a standard momentum in that sense. \n\n*2) Bandwidth considerations of All-reduce and Ring reduce*\n\nThank you for pointing that out, we will clarify our statement. We are indeed interested in reducing the latency induced by each \"communication act\" between workers, and as stated in the Ring All-Reduce paper [ [3] ](https://www.cs.fsu.edu/~xyuan/paper/09jpdc.pdf ): *\"One limitation of the proposed algorithm is that it is only optimal in the bandwidth term, but not the latency term: the number of communication rounds is proportional to the number of processes.\"* An orthogonal (but crucial) line of work [ [8](https://arxiv.org/pdf/1610.02132.pdf ), [9](https://arxiv.org/pdf/1802.04434.pdf) ] is indeed to consider lowering the bandwidth in addition to the total number of communications, using compression schemes for example, to which our method can be independently combined with. Moreover, we stress that Ring All Reduce is **synchronous**, adding undesirable barriers that we remove by focusing on asynchronous methods. \n\n*3) Distinction from QG-SGD, SlowMo*\n\n* QG-DSGDm [ [4] ](https://arxiv.org/pdf/2102.04761.pdf ) introduces a momentum to lower the complexity of **synchronous rounds of computations-communications** in the **heterogeneous** setting. We are rather interested in explicitly lowering the **communication complexity** in the **asynchronous** and **homogeneous** setting. Moreover, in addition to being synchronous, their method requires gradients to be computed **before** communicating, meaning the latencies for computations and communications are **added**, whereas, being decoupled, our method allows running both processes **in parallel.**\n\n* SlowMo [ [5] ]( https://arxiv.org/pdf/1910.00643.pdf ) is also a **synchronous** algorithm.\n\nWe must emphasize that we study an **asynchronous** algorithm. This brings many practical advantages in the large-scale distributed setting, but also leads to specific technical challenges (for example, the Chebyshev scheme widely used to accelerate communications in decentralized methods is, by nature, synchronous and sequential). As such, the closest method to which we can compare is AD-PSGD [ [6] ]( http://proceedings.mlr.press/v80/lian18a/lian18a.pdf ), which we have done. *We stress that no other existing decentralized asynchronous method displays accelerated rates of communications in the training of deep neural networks*.\n\n**Questions:**\n\n* The cluster we used has an *Omni-PAth interconnection network 100 Gb/s*. We will add this point in the main text, thanks.\n* Our work aims at studying the impact of the network’s connectivity  (as measured by $\\chi_1, \\chi_2$) on the communication complexity in the decentralized training setup, and showing that $A^2CiD^2$ allows to reduce it. As the ring graph corresponds to one of the worst case settings, it is standard to use it in the decentralized literature, see e.g  [ [4, ](https://arxiv.org/pdf/2102.04761.pdf ) [ 7]( https://arxiv.org/pdf/1705.09056.pdf) ].\n* While it is technically true that there is no central worker performing the averaging in the *implementation* of modern All-Reduce methods, we still denote them as centralized as they require the computation of a *global* variable using information from *all* the workers. Put simply, although there are multiple ways to implement it, the requirement for waiting barriers and synchronized communication rounds corresponds exactly to a centralized framework.\n\n**Limitations:**\n\nWe emphasize that our evaluation is standard in the literature (see [ [10](https://arxiv.org/pdf/1808.07217.pdf), [11](https://arxiv.org/pdf/1811.10792.pdf) , [6]( http://proceedings.mlr.press/v80/lian18a/lian18a.pdf ) ]). While we agree that verifying experimentally that our method scales to training models with billions of parameters would be of interest, we are unfortunately not in the material capacity to do so, lacking the right computing infrastructures: we must stress that we work in **academia** with a **publicly funded cluster**. The open-source release of our code is planned to allow such experiments for other actors with more compute resources. However, we will aso report additional experiments with Vision Transformers shortly (experiments still ongoing at the time of writing), but we expect a similar behavior for these models."}, {"review_id": "14IiVkYC0s", "reviewer": "Reviewer_o6Xd", "summary": "This paper proposes an asynchronous gossip-based algorithm for decentralized deep learning by using a continuous momentum. Experiments on real datasets are used for evaluation.", "questions": "Is the formula between Line 139 and Line 140 correct?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The studied problem about accelerating communication in decentralized deep learning is interesting.\n\n2. The proposed algorithm accelerates the asynchronous baseline both theoretically and empirically.", "weaknesses": "1. The writing can be improved. There are many typos and grammatical errors. Furthermore, there are many informal representations, such as “We demonstrate its efficiency theoretically and numerically; empirically on the ring graph…” in abstract.\n\n2. The proposed method needs to store one more copy of the model, compared with baselines. Hence, it may not be suitable for large models.\n\n3. The experimental results are not convincing. The main baseline for comparison is All-Reduce SGD which has very high communication cost. There have existed many sophisticated decentralized methods, which should be adopted for comparison. \n\n4. This work only considers undirected network topology, which means that the communications are symmetric. But in recent years, directed topology has attracted more and more attention.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are glad that reviewer o6Xd finds the problem we study interesting and recognizes that our method accelerates previous algorithms both theoretically and empirically. We stress that our method is especially catered for large scale training of deep neural networks: the advantage of **asynchronous** algorithms grows with scale, and further accelerating them is not trivial.\n\n**Weaknesses:**\n\n1) We acknowledge that a few typos and drafting errors have slipped through our fingers, which we will correct in the final version of this work.\nTo mention a few, a spell-checker only found about 20 of those located at lines independent *(l36: communications -> communication), (l45: gossips->gossip),(l56: allow to->allows us to), (l58:  communication -> the communication), (l62: improve -> improves) (l66: time of -> the time of), (l73: independant -> independent), (l94: exists -> exist), (l103: to use strong -> to use of ), (l135: Next sections -> The next sections), (l159: allow to -> allow us to), (l176: step -> steps), (l186: technique degrade accurracy -> techniques degrade accuracy), (l199: adaptation -> adaptations), (l210: networks parameters-> network parameters), (l233: each others -> each other), (l238: allows -> allows us), (l280: finally-> final), (l281: the Fig. -> Fig.).* \nHowever, we believe this minor weakness does not diminish the significance of our scientific contribution.\nWe clarify the abstract as follows: *\"Our theoretical analysis proves accelerated rates compared to previous asynchronous decentralized baselines and we empirically show that adding $A^2CiD^2$ has the same effect as doubling the communication rate on the ring graph.\"*\n\n2) We respectfully disagree with this statement. First, remark that *any* algorithm that uses SGD with momentum is also doubling the number of parameters in memory: that is the cost of storing the momentum variable in the optimizer. Thus, our method is completely analogous to a standard momentum in that sense.\nPlus, in large models such as Transformers, the main memory cost does not reside in the storing of the parameters, but rather in the memory requirements for storing the activations and computing the gradients (see e.g,  [ [ 1, ]( https://arxiv.org/pdf/2111.11124.pdf ) [ 2 ]( https://arxiv.org/pdf/2205.05198.pdf ) ] ). As our method only uses the second set of parameters as a *\"memory bank\"* (our second \"model\" does not perform any computation: neither forward nor backward), it is virtually at no cost in terms of memory (the memory for activations in the original model dominating the storing of a second set of parameters).\n\n3) The main baseline for comparison we use is AD-PSGD [ [3] ]( http://proceedings.mlr.press/v80/lian18a/lian18a.pdf ): this is our “asynchronous baseline” in Tab.2 and Tab.4, which is quite standard and challenging to beat. Indeed, our primary objective is to minimize the communication overhead of asynchronous techniques, which are faster than synchronous methods as they aim at removing wait barriers from their implementation. However, we introduce All-Reduce SGD as a benchmark, establishing a target performance that an effective (asynchronous or synchronous/centralized or decentralized) method should achieve.While bringing many practical advantages in the large-scale distributed setting, asynchronous algorithms also lead to specific technical challenges compared to synchronous approaches. We stress that no other existing decentralized asynchronous method displays accelerated rates of communications in the training of neural networks and that any other scheme to reduce communication cost (e.g., compressed or quantized communications) can be added on top of our method. If we missed some, do you have in mind other **decentralized asynchronous** baselines to which we can compare ?\n\n4) We respectfully disagree: using asymmetric communication can be simply done in our case. Indeed, while the *implementation* of our method is indeed symmetric for simplicity’s sake, what our theoretical analysis says is more subtle: we only require that the *directed* and *expected* rates of communications between any two workers ($i$ to $j$ and $j$ to $i$) are the same. Thus, our algorithm could also work with non-symmetric communication schemes (i.e push or pull methods). We stress that, in practice, symmetric communications are often assumed for *asynchronous* schemes (see, e.g. [ [3] ]( http://proceedings.mlr.press/v80/lian18a/lian18a.pdf ) ).\n\n**Questions:**\n\nThe  formula is indeed correct, it is a very standard re-formulation of the decentralized optimization problem using the consensus constraint (see e.g eq. 10 in [ [4] ](https://arxiv.org/pdf/1702.08704.pdf) or eq. 2 in [ [5]](https://proceedings.neurips.cc/paper_files/paper/2020/file/d530d454337fb09964237fecb4bea6ce-Paper.pdf )). We’d be happy to provide further explanations if needed."}, {"review_id": "Yhe7TcMsQU", "reviewer": "Reviewer_fQ1m", "summary": "This work, A2CiD2, proposes a novel decentralized asynchronous training method that incurs only minimal overhead but effectively decouples communications and computations, accelerating pair-wise communications via a provable, accelerated, randomized gossip procedure based on continuous momentum and time.  A2CiD2 is also compatible with other asynchronous approaches. Across ResNet benchmarks on image classification, A2CiD2 is able to outperform AllReduce-SGD and AD-PSGD on a cluster of 64 asynchronous workers\nwith A100 GPUs, using various communication network topologies.", "questions": "See Weakeness", "limitations": "N/A", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "+. Proposed a decentralized asynchronous training algorithm that outperforms the SOTA approaches\n\n+. Demonstrated the advantage of the proposed approach both theoretically and empirically\n\n+. Provided code for reproducibility", "weaknesses": "-. Writing needs improvement. Hard to follow.\n\n-. Missing benchmark: \n1. only ResNet is evaluated (e.g., ResNet18 and ResNet50), how about more models like RNNs and larger models like GPT2?\n\n2. only image classification tasks is evaluated, how about more tasks like language modeling?\n\n-. Missing details in experiments: \n1. what is the network type and bandwidth?\n2. how many GPUs per machine? \n\n-. Missing evaluation: \n1. what is the time-to-accuracy or time-to-loss speedup for AC2CiD2 over AllReduce-SGD and ADPSGD?\n\n2. what is performance of AC2CiD2 with random stranger in the cluster?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer fQ1m for stressing that our method outperforms SOTA approaches, both theoretically and empirically. We emphasize that this paper is **not** about implementations tricks but rather about *fundamental research* on new strategies to speedup asynchronous training. Indeed, our work solves the important question of understanding how to accelerate communications in an asynchronous setting.\n\n**Weaknesses:**\n\n* We corrected a few typos and drafting errors in the revised version of our paper to clarify the writing. To mention a few, a spell-checker only found about 20 of those located at lines independent *(l36: communications -> communication), (l45: gossips->gossip),(l56: allow to->allows us to), (l58:  communication -> the communication), (l62: improve -> improves) (l66: time of -> the time of), (l73: independant -> independent), (l94: exists -> exist), (l103: to use strong -> to use of ), (l135: Next sections -> The next sections), (l159: allow to -> allow us to), (l176: step -> steps), (l186: technique degrade accurracy -> techniques degrade accuracy), (l199: adaptation -> adaptations), (l210: networks parameters-> network parameters), (l233: each others -> each other), (l238: allows -> allows us), (l280: finally-> final), (l281: the Fig. -> Fig.)* However, we believe this minor weakness does not diminish the significance of our scientific contribution.\n\n* For the image classification task, we will aso report additional experiments with Vision Transformers shortly (experiments still ongoing at the time of writing), but we expect a similar behavior for these models.We emphasize that our evaluation is standard in the literature (see [ [1](https://arxiv.org/pdf/1808.07217.pdf), [2](https://arxiv.org/pdf/1811.10792.pdf) , [3]( http://proceedings.mlr.press/v80/lian18a/lian18a.pdf ) ]). Moreover, we are unfortunately not able to train large language models such as GPT2 for lack of the right computing infrastructures. The open-source release of our code is planned to allow such experiments for other actors with more compute resources.\n\n* We will add the following details to the paper: all our experiments are done on an **academic** cluster with 8 A100 per node using an Omni-PAth interconnection network 100 Gb/s. In all our experiments, one worker amounts to one GPU (and not one node).\n\n* Thank you for raising interest on these metrics, we will provide additional figures in the revised version of our paper. In the meantime, we report some preliminary figures *(in the pdf attached to the global rebuttal)* showing that applying $A^2CiD^2$ is indeed worthwhile in terms of time.\n\n* We are not sure we understand the question. In the “complete graph” setting, our asynchronous algorithm acts as follows: to reduce latency, the first two workers (i.e., GPUs) in the whole pool that declare they are ready to communicate (i.e, finished their previous communication) are paired together for a p2p communication. In practice, as each worker has to perform a random number (following a poisson law) of communications between two gradient computations, this means that the pairs are completely random (no pair of workers can repeatedly synchronize at the same time). We verify that indeed, during the course of a training run, each edge in the complete graph appeared roughly the same amount of time *(see the pdf attached to the global rebuttal)*. We’d be happy to provide further explanations if required.\n\nWhile seemingly working in the High Performance Computing setting, we must stress that our experiments are mainly done to **simulate** a decentralized network (e.g, connected through the internet) and to highlight the potential of using $A^2CiD^2$ to reduce the communication cost in situations where it is a major bottleneck to train neural networks."}, {"review_id": "vfmyxt05zD", "reviewer": "Reviewer_LKYk", "summary": "This work discusses the challenges and potential solutions related to training complex Deep Neural Networks (DNNs), particularly regarding the computational and communication demands. The traditional synchronous, centralized approaches to DNN training, while widely used, face limitations in terms of efficiency and scalability, which can be tackled by distributed training methods.\n\nAsynchronous and decentralized methods are suggested as they allow for more efficient parallelization of computations and communications, using time-delay fluctuations between workers. Such methods eliminate the need for a central worker to aggregate results, allow nodes to contribute in proportion to their available resources, and use peer-to-peer communication to streamline training. However, the complexity of these methods and the large number of parameters in DNNs still pose considerable communication challenges.\n\nThe authors address these issues by introducing a novel acceleration method, A2CiD2 (Accelerating Asynchronous Communication in Decentralized Deep Learning), specifically for peer-to-peer DNN training. This method uses pair-wise gossip acceleration, which is largely unexplored for deep learning, and is supported by the analytical framework of Stochastic Differential Equations (SDEs). It decouples computations and communications, requiring minimal overhead and enhancing communication rates.\n\nKey contributions of this work include extending the asynchronous decentralized deep learning training framework to non-convex settings, proposing the A2CiD2 mechanism for improving communication efficiency, and minimizing the gap between centralized and decentralized settings in environments with up to 64 asynchronous GPUs. The method has been implemented in PyTorch and will be released as open-source upon publication.", "questions": "In addition to the issues delineated as weaknesses above, I would be grateful if you could respond to the following queries:\n\n1: In Section 3.1, \"Model for a Decentralized Environment,\" you presuppose the symmetry of communication. Could you elaborate on this assumption and explicate its implications for your model?\n\n2: In Section 3.3, \"Theoretical Analysis of A2CiD2,\" you propose a Poisson process. Nevertheless, the validity of this assumption remains nebulous. Could you furnish some justification or explanation for this assumption?\n\n3: In Section 4, \"Numerical Experiments,\" you cite the utilization of 64 A100 GPUs. Could you provide more details about the network configuration they are connected to, such as Infiniband? The performance of the network itself is likely to affect the results of this experiment, and this information would help elucidate the experimental setup.", "limitations": "N/A : No pertinent content is found in the paper.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The strengths of this paper are as follows:\n\n1: Within the realm of deep learning, the widespread use of High-Performance Computing (HPC) technology has made it possible to achieve exceptional performance in a synchronous and centralized environment. However, not everyone has the means to afford such costly setups, making the development and evaluation of distributed asynchronous algorithms crucial. The authors propose a cost-effective method that significantly enhances communication speed.\n\n2: The A2CiD2 algorithm effectively minimizes the discrepancy between centralized and distributed setups. It functions efficiently in environments hosting up to 64 asynchronous GPUs. This characteristic enhances the algorithm's scalability, rendering it suitable for large-scale machine learning tasks.\n\n3: This study broadens the analytical framework for investigating the design and convergence of these algorithms in non-convex settings. It provides new insights into asynchronous distributed deep learning training.\n\n4: The method proposed substantially improves communication efficiency in distributed learning environments. This could assist in addressing common challenges, such as the straggler problem, synchronization between computation and communication, and bandwidth limitations.", "weaknesses": "The weaknesses of this paper can be outlined as follows:\n\n1: While the theoretical analysis provided in Section 3.3 is well substantiated, its tightness with respect to the upper bound remains ambiguous. Further explanation is needed on how the asymptotic convergence corresponds with the experimental results for relatively smaller sizes, like those discussed in Section 4.\n\n2: The study mentions that the proposed A2CiD2 algorithm has been tested with up to 64 asynchronous GPUs. While this is quite remarkable, it may not comprehensively represent the broad array of hardware configurations and scales found in real-world applications. A broader evaluation of the method across different scales and architectures would be advantageous.\n\n3: The paper lacks a clear comparison with other existing distributed training methods, be they synchronous or asynchronous, in terms of computational cost, communication overhead, and performance. Such a comparison could help determine whether the proposed method truly surpasses other methods and under which specific conditions.\n\n4: The paper asserts that training Deep Neural Networks (DNNs) with decentralized methods necessitates substantial communications due to the large quantity of optimized parameters. It remains unclear whether the proposed acceleration method sufficiently addresses this issue and how it compares with other techniques that aim to reduce communication overhead.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer LKYk for highlighting the need for cost-effective methods enhancing communication speed in distributed training, and recognizing  that our method is a step towards rendering large-scale training possible in this setting by substantially improving  communication efficiency while providing new insight into asynchronous distributed deep learning training.\n\n**Weaknesses:**\n\n1) Lower bounds to minimize the sum of functions with randomized algorithms exist [ [1]( https://arxiv.org/pdf/1605.08003.pdf ), [2](https://arxiv.org/pdf/1805.10222.pdf) ] and we are probably not tight in that sense. However, we still provide a SOTA communication complexity, even compared to accelerated *synchronous* methods that use Chebychev acceleration as our rate depends on the maximal effective resistance of the graph instead of the spectral gap (see, e.g. [[3]]( http://proceedings.mlr.press/v202/nabli23a/nabli23a.pdf ) ). Note that, if we put $f=0$, then the problem reduces to satisfying the consensus constraint and our algorithm meets the fastest known rate for gossip algorithms [[7]]( https://proceedings.neurips.cc/paper/2021/file/ec26fc2eb2b75aece19c70392dc744c2-Paper.pdf ). Finally, remark that convergence rates in the smooth case are often put as a sanity check in the deep learning literature as they are vacuous in practice [[8]]( http://proceedings.mlr.press/v97/arora19a/arora19a.pdf ).\n\n2) We must stress that we work in **academia** with a **publicly funded cluster**. Thus, while we agree that verifying experimentally that our method is amenable to a wide range of hardware settings would be of interest, this is reasonably beyond the reach of the material capacity of our academic setting. Note that despite those constraints, our numerical experiments use a number of workers of the order of  state-of-the-art work [[9]]( http://proceedings.mlr.press/v97/assran19a/assran19a.pdf ). The open-source release of our code is planned to allow such experiments for other actors with more compute resources. In terms of network architecture, we will aso report additional experiments with Vision Transformers shortly (experiments still ongoing at the time of writing), but we expect a similar behavior for these models.\n\n3) We aim at reducing the communication cost of **asynchronous** methods, because they have the potential to be faster than synchronous ones due to the removal of wait barriers. While bringing many practical advantages in the large-scale distributed setting, asynchronous algorithms also lead to specific technical challenges compared to synchronous approaches. As such, the closest method to which we can reasonably compare is AD-PSGD [ [4] ]( http://proceedings.mlr.press/v80/lian18a/lian18a.pdf ), which we have done. We stress that no other existing decentralized asynchronous method displays accelerated rates of communications in the training of neural networks: AD-PSGD [ [4] ]( http://proceedings.mlr.press/v80/lian18a/lian18a.pdf ) has a complexity depending on the *spectral gap* $\\omega ,$ whereas ours depends on $\\sqrt{\\chi_1 \\chi_2}$ which is better (typically for the cycle graph, $\\omega = \\mathcal O (n^2)$ and $\\sqrt{\\chi_1 \\chi_2} = \\mathcal O (n)$).\n\n4) We believe that any method taken alone would probably not be sufficient to grow to arbitrarily scale and that our method is another tool to reduce the communication cost for the decentralized asynchronous training of neural networks. As we use a local momentum, our method is completely orthogonal to schemes aiming at reducing the bandwidth requirements through compressed or quantized communications, which can be added on top of $A^2CiD^2$.\n\n**Questions:**\n\n1) The symmetry of communications means that our communication network is undirected: when an edge $(i,j)$ “spikes”, both nodes $i$ and $j$ send their parameters to the other, such that both can compute the *average* of $(x_i, x_j)$. While our *implementation* of our method is indeed symmetric for simplicity’s sake, what our theoretical analysis says is a bit more subtle: we only require that the *directed* and *expected* rates of communications between any two workers ($i$ to $j$ and $j$ to $i$) are the same. Thus, our algorithm could also work with non-symmetric communication schemes (i.e push or pull methods). We stress that, in practice, symmetric communications are often assumed for *asynchronous* schemes (see, e.g. [ [4] ]( http://proceedings.mlr.press/v80/lian18a/lian18a.pdf ) ).\n\n2) The Poisson modeling of gossip algorithms is standard in decentralized peer-to-peer networks *(see, e.g., the seminal paper of Boyd et al. [[5]](https://web.stanford.edu/~boyd/papers/pdf/gossip.pdf) )*, we thus follow this literature. To gain more insight, this modeling consider that any individual link in the network has a fixed bandwidth, thus the time between  two communications is always *roughly* the same, and variations are taken into account by making this delay stochastic (following an exponential law). However, we agree that this model is not perfect, and some refinements have been made to move closer to reality (see, e.g. [ [6]](https://arxiv.org/pdf/2106.03585.pdf) ).\n\n3) We will add the following details to the paper: all our experiments are done on a cluster with 8 A100 per node using an Omni-PAth interconnection network 100 Gb/s. In all our experiments, one worker amounts to one GPU (and not one node)."}]

Author rebuttal:
We thank reviewers for recognizing that our method accelerates previous state of the art **asynchronous decentralized** methods both theoretically and empirically (reviewers fkqi, o6Xd, fQ1m) which is a good step towards addressing common challenges of large scale training of deep neural networks (reviewer LKYk). We would now like to address frequently raised comments, which we believe will clarify any previous concerns: 

* **The memory footprint of our method is not high.**
Our method is completely analogous to a standard momentum: **any** algorithm that uses SGD with momentum is also doubling the number of parameters in memory: that is the cost of storing the momentum variable in the optimizer. As for any momentum term, no additional heavy computation is performed with these parameters (no forward nor backward), making the cost in time and memory negligible for large models. For instance, *our method (SGD+momentum+$A^2CiD^2$) has the same memory footprint as Adam* (as it has 2 momentum variables).

* **Our academic cluster is not able to train models with billions of parameters, and our experiments are standard.**
We are *academic* researchers using a *publicly funded* cluster: we were surprised that reviewers requested us to train GPT-like models.
Moreover, training ResNets on CIFAR10 and ImageNet is standard in the decentralized training literature (see [ [1](https://arxiv.org/pdf/1808.07217.pdf), [2](https://arxiv.org/pdf/1811.10792.pdf) , [3]( http://proceedings.mlr.press/v80/lian18a/lian18a.pdf ) ]).

* **Cluster details.**
All our experiments are done on a cluster with 8 A100 per node using an Omni-PAth interconnection network 100 Gb/s. In all our experiments, one worker amounts to one GPU (and not one node). We will add these details in our paper.

* **A general remark on Communication Acceleration.**
Before this work, communication acceleration - enhancing the communication rate from $\gamma$ (the spectral gap of the matrix) to $\sqrt{\gamma}$ - was (almost) exclusively achieved via Chebychev acceleration, in the context of training DNNs. Thus, most previous studies don't dwell on this, as it simply corresponds to replacing a gossip matrix $W$ with $P(W)$ where $P$ is the corresponding Chebychev polynomial. However, Chebychev acceleration is inherently synchronous and sequential. Thus, such a process is absolutely undesirable in an asynchronous environment, underscoring the significance of our contribution. *It's essential for reviewers to grasp this distinction and recognize that, prior to our work, standard gossip algorithms that simply perform an averaging between node parameter values were the norm.* Thus, we believe our work to be an important contribution to the litterature of asynchronous training procedures for DNNs.


Meta-review: This paper studies the asynchronous parallel algorithm in the decentralized setting and proposes a random communication based approach. Both theoretical analysis and empirical evaluations are provided. While the theoretical results look reasonable, the empirical study is not sufficient to validate the proposed algorithm, which is an obvious weakness of this paper as pointed by multiple reviewers. We finally decide to accept this borderline paper given its contribution in theory, but strongly suggest this paper to improve the experiment section.

Specific suggestions include:

- experiment: study the practical performance for the proposed algorithm under different scenarios to validate the theory. In particular, we want to know when it outperforms the synchronous algorithms and AD-PSGD. More solid comparison to the synchronous approaches need to be included to justify the advantage of synchronization. The comparison to All-reduce (the most classic synchronous algorithm) need to be solid and fair. Authors may consider using existing distributed learning framework to implement the designed designed algorithm, avoid complicated and nontrivial system optimization, e.g., [1]

- theory: provide more comprehensive comparison to the synchronous algorithms for validating the tightness of the proposed analysis. The comparison to the asynchronous algorithm in the centralized setting needs to be compared, e.g., [2]. We believe this can be achievable in a relatively short term based on the author's response. 

- algorithm: some other related decentralized / asynchronous algorithm comparison needs to be included, e.g. [3-12]

References:

[1] BAGUA: Scaling up Distributed Learning with System Relaxations  https://github.com/BaguaSys/bagua

[2] Distributed Learning Systems with First-Order Methods: An Introduction

[3] Asynchronous Gradient-Push https://arxiv.org/pdf/1803.08950.pdf

[4] Optimal Complexity in Decentralized Training, ICML 2021

[5] Optimal Algorithms for Smooth and Strongly Convex Distributed Optimization in Networks, ICML 2017

[6] Optimal and Practical Algorithms for Smooth and Strongly Convex Decentralized Optimization, NeurIPS 2020.

[7] DADAO: Decoupled Accelerated Decentralized Asynchronous Optimization, ICML 2023.

[8] A Unified Theory of Decentralized SGD with Changing Topology and Local Updates, ICML 2020

[9] Stochastic Gradient Push for Distributed Deep Learning, ICML 2019

[10] Don’t use large mini-batches, use local SGD, ICLR 2020

[11] Asynchronous Decentralized Parallel Stochastic Gradient Descent, ICML 2018

[12] Consensus control for decentralized deep learning, ICML 2021
Decision: Accept (poster)