Delayed Gradient Averaging: Tolerate the Communication Latency for Federated Learning
Authors: Ligeng Zhu
Hongzhou Lin
Yao Lu
Yujun Lin
Song Han
Venue: NeurIPS 2021 Poster (2021)
Keywords: distributed optimization
distributed training
federated learning
latency

Abstract: Federated Learning is an emerging direction in distributed machine learning that en-ables jointly training a model without sharing the data. Since the data is distributed across many edge devices through wireless / long-distance connections, federated learning suffers from inevitable high communication latency. However, the latency issues are undermined in the current literature [15] and existing approaches suchas FedAvg [27] become less efficient when the latency increases.  To over comethe problem, we propose \textbf{D}elayed \textbf{G}radient \textbf{A}veraging (DGA), which delays the averaging step to improve efficiency and allows local computation in parallel tocommunication. We theoretically prove that DGA attains a similar convergence rate as FedAvg, and empirically show that our algorithm can tolerate high network latency without compromising accuracy. Specifically, we benchmark the training speed on various vision (CIFAR, ImageNet) and language tasks (Shakespeare),with both IID and non-IID partitions, and show DGA can bring 2.55$\times$ to 4.07$\times$ speedup. Moreover, we built a 16-node Raspberry Pi cluster and show that DGA can consistently speed up real-world federated learning applications.

Delayed Gradient Averaging: Tolerate the Communication Latency in Federated Learning
Ligeng Zhu'
Hongzhou Lin
Yao Lu
Yujun Lin
Song Han
MIT
²Amazon GGoogle
mitaammiteddu
Abstract
Federated Learning is emerging direction in distributed machine learning that ables jointly training model without sharing the data. Since the data is distributed across many edge devices through wireless/ long-distance connections, federated learning suffers from inevitable high communication latency. However, the latency issues are undermined in the current literature [15] and existing approaches such as FedAvg [27] become less efficient when the latency increases. To overcome the problem, we propose Delayed Gradient A Averggigg (DGA), which delays the averaging step to improve efficiency and allows local computation in parallel to communication. We theoretically prove that DGA attains a similar convergence rate as FedAvg, and empirically show that our algorithm can tolerate high network latency without compromising accuracy. Specifically, we benchmark the training speed on various vision (CIFAR, ImageNet) and language tasks (Shakespeare), with both IID and non-lID partitions, and show DGA can bring 2.55 to 4.07 speedup, Moreover, we built 16-node Raspberry Pi cluster and show that DGA can consistently speed up real-world federated learning applications.
Introduction
Federated Learning [18, 27] has gained growing attention as it enables multi-clients distributed training without exposing the data from private users. During the training, only the model updates exchanged between clients and servers, thus private training data never leave local devices, enhancing privacy. Many successful applications such next-word prediction [10], voice recognition [38], and health care applications [50] have been derived under the framework.
A significant difference between federated scenarios and typical in-center distributed settings [6, 8] is the networking condition. Unlike high-end in-cluster network infrastructures where high bandwidth (100~Gbps) and low latency (< (m)m)) network is available, edge devices usually connected through wireless and long-distance connection, thus the bandwidth and latency are strictly limited. This dwarfs the performance of federated systems and slows the development of related applications.
While the bandwidth constraints have been efficiently addressed by gradient compression [25], low- rank updates [18] and quantization techniques [43], the issue related to network latency is rarely studied in the recent literature [12, 15]. However, high network latency is inevitable in federated settings because of (1) wireless connections and (2) -ii-ttittncee transmission (Figure. I.(b)). On the one hand, the high-density urban office and home environments create a lot of contention, as dozens of devices compete for the same radio frequency. On the other hand, the multi multi-geogran seotrahhe located data entails a minimum latency cost: even with the speed of light, it requires hundreds milliseconds to send packet across the world. In either case, the high latency is hard barrier introduced by physical limits thus inevitable. If not handled specifically, such communication lag, in the magnitude of hundreds of milliseconds, even seconds, will significantly degrade the scalability of the learning algorithm as shown in the Figure. 1.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Latency:1us
1ms 500ms
10ms
100ms
1s
Throughpui
Wi Fi
Within Rack
Same Data Center
Wireless Connection
Across the World
(<lus)
(- 1ms)
(- 20ms)
[> 100ms)
(a) Conventional Scttings
Federated Settings
(c) Speed Comparison
The training settings of conventional distributed training v.s. federated learning very different. Right: High latency cost greatly degrades the FedAvg's [27] performance, proposing severe challenge to scale up the training system. The latency statistics is referenced from Verizon [46] and speedtest [42].
Figure I: Left, Middle:
In this paper, we propose Delayed Gradient Aggregation (DGA) to address the latency bottleneck. The key idea is to delay the gradient averaging future iteration thus the communication be pipelined with computation. By accepting stale average gradients for model updates, DGA allows the communication to execute in parallel with the computation, thus scalable latency. We prove that our DGA shares the same convergence as FedAvg and provide extensive experiments on image and language tasks in both i.i.d. and non-i.i.d settings. We demonstrate that (i) DGA speeds up FedAvg by factor 2.6x to 4.1 x over various datasets; (ii) no accuracy drop under extreme communication lag (e.g.. > second). We further set up Raspberry Pi cluster to simulate the real-world scenario and demonstrate that DGA is robust against network stragglers. Our contributions can be summarized as follows:
under extreme
We propose DGA, a novel distributed optimization method to tolerate the communication latency for federated learning. To our best knowledge, our algorithm is the first work that achieve scalable federated training under high latency (>ls).
We theoretically justify the convergence of DGA. We show that under reasonable delay interval, shares the same convergence rate FedAvg [51]. We also discuss its extension with momentum update to better suit modern federated optimizations.
We empirically evaluate the accuracy diverse datasets and benchmark the speed on different latency setups. Under an extremely high latency, DGA can show impressive improvement over previous algorithms while preserving similar performance on both i.id and non-i.i.d partitions.
We build up a Raspberry Pi cluster of 16 devices to evaluate our algorithm in real-world setting. Even with unpredictable packet loss and latency fluctuation, DGA still shows consistent speedup.
Delayed Gradient Averaging
2.1 Problem Setting, Preliminaries and Related Works
In this work, formalize the problem as the minimization of sum of stochastic functions,
N
1
min f(w)
E fi(w) N
with fi(w) = Eg, [w, (:),.
where N denotes the number of clients and f; represents the loss function i-th client. In the setting of empirical risk minimization, fi could be further expressed as finite sums and the random variable corresponds a mini-batch sample.
Computation and Communication cost Each client represents computational resource that can either perform local gradient updates exchange information with others. We model the computation and communication cost by:
We encounter computational cost Ty for each gradient/mini-binn batch evaluation.
The communication suffers cost per transmission. We further define the normalized com-
Te
munication cost:

---

In other words, one communication round takes the same amount of time D gradient updates. This normalized cost serves the main parameter in our discussion on the computation/conmmmiatttoo trade-off. Note that the communication cost usually depends on the bandwidth, amount of bits transmitted and the latency, we start revisiting FedAvg [27] to illustrate the effect on latency.
FedAvg and its variants One of the key components in Federated Learning is the step of parameter averaging. This step aggregates the model parameter across clients, without revealing personal training data, enhancing privacy. However, the averaging step is synchronous by design [3], in the sense that no local updates are allowed when the averaging takes place. Specifically, FedAvg [27] alternate the local updates and averaging step:
FedAvg: : averaging (communication) - K x xlocal updates averaging (communication)
where the parameter indicates the number of mini-batcher (gradients) locally updated between two averaging steps. The alternating structure of the update naturally decomposes the algorithm into rounds, with K local updates and one communication per round. The total running time of FedAvg after T rounds is given by
T FedAAg T(KT, + To) To)= =
) T
1o Tg
As we can see, the communication cost D inflates the total run time by a non-negligible factor, especially when D is large. For instance, if D K, half of the rumning time is indeed wasted, where clients sit and wait on the synchronization of averages, making the algorithm inefficient. The same drawback persists in all recent extensions of FedAvg [17, 21,211,2 22, 28, 51J, its momentum variants [5, 26, 47], variance reduced variant SCAFFOLD [16] and adaptive variant [34], etc.
techniques in FI. To improve communication efficiency, extensive efforts have been devoted to reducing the bits on gradient exchanges large-scale distributed training. Techniques such gradient quantization QSGD [1], Onebit [39]. Tengrad [49] and gradient compression DGC [25], Sparsification [48], DenseCommu [43], DoubleSqueeze [44] can safely reduce the amount of information transmitted by factor of 1000, while maintaining the high performance of the model. These techniques have been successfully applied to accelerate FL 35, enabling training mobile devices with limited bandwidth connection. Therefore, bandwidth is no longer a critical bottleneck on edge learning.
On the other hand, the latency issue is less discussed in the current FL literature [15] as it is hard physical barrier. To focus on such inherent and non-improvable subject, we assume that the bandwidth is sufficient," and the communication cost is dominated by network's 's latency. In this case, the running time of FedAvg and its variants in Eq.1 can still be significantly inflated by the latency, even compression/quantzattoo techniques are applied.
The ineffectiveness of the existing approaches to deal with the high latency setting motivates us to ask the following question: is it possible to design an algorithm that could scale up under high latency settings while keeping the accuracy? We provide a positive answer by introducing the delayed gradient averaging.
2.2 A step-by-step walk through Delayed Gradient Averaging
The main idea of our algorithm is allow local updates during the communication of the averaging. In FedAvg, clients send its parameter to each other at the end of each round, wait until the averaging (communication) ended, later starts the next round. In our algorithm, the averaging barrier delayed to a later iteration so that clients can immediately start the next round and an gradient correction term is designed to compensate the staleness:
1. Clients send updates to each other at the end of t-th round;
2. Clients continue performing local updates using the latest local parameter;
3. When other's t-th round info arrived, the client has already performed D extra local updates.
4. Delayed averaging step: replace the local gradients at the (-th round by the received averaging (we will detail this step right away).
"otherwise apply gradient compression techniques.
3

---

Algorithm Delayed Gradient Averaging (DGA)
1: Initialize each worker with wf.1 w1 for i [1, NJ, the number of local update K, the delayed parameter D 1. Define (D 1)//K the integer quotient.
2: for rounds t = 1, .... T do
3: for client in parallel do
4: Set w - w 1,1,, K++ as the last iterate at round (t 1)
5: for l = 1, ... K do
6:
Sample the stochastic gradient gi,8 the previous iterate w and update
w1, 7gi,
if 전 D (mod K) or - - < 1;
wi,
w nl9i, mi-1-s + m--1-s) if k = D (mod K) and
1.
where mi-1-s is the accumulated gradient (see line 8) at the earlier round t - M is the average of m among all clients, i.c. m4-1-s Nv2 E, mi-1-s
7:
end for
8:
Send the t-th round accumulated gradient mi = - Hi, all other clients."
9:
end for end for
10:
11:
Return Wr N Em= w T
The benefit is plain to see: we no longer freeze the local computation power during the communication. To make the discussion within the t-th round by wi, and the corresponding stochastic gradient as gi.k- In the very first round t 1, solely local updates are performed, hence the last iterate the first round can be expressed as
explicit, denote the parameter the i-th client at the k-th iteration
wf 1+++ = wi,k - n = = wi
91.-
k=
As the first round's computation has completed, send the accumulated gradient mi := Σk= g to all the clients, i.e. perform averaging. Right after the gradients are sent, we immediately proceed the second round's 's local updates, leaving the first round averages in transmission. By the time the already performed D extra local updates in the second round, starting from
average is received, the last iterate of first round wi, wiK
D Σ
w²DD T992DD last iterate before averaging
W 11K+1
7
32. =
11
Σ
gi
1
Σ g2
(2)
updates
1st round
2nd round
At this point, the average of the first round arrives
N
K
N
K I1.k:
mi
Fi,k
Fi.k
(accumulated averages)
N
N
N
k=
i=1
R=1
where 91,k represents the average gradient at k-tth iteration in the 1st round. With the averaging mi in hand, we substitute all the first round local gradients in Eq.2 by their averages, leading to:
K
wh
2 D+1
W1
JL.k
(delayed gradients averaging)
A=
common
2nd round unchanged
'The accumulated gradient is indeed implemented as m. + mi + gf.u under the for loop on ks which do not require extra memory store St.k-

---

1...
update rule grad(net, data)
it iter g 0: ir cend idmiter) eve recv(id-iter) ir (9 _vq__
Local updales communication performed sequentially.
Increase K can amortize the effect. suffer high latency.
Gradients Correction
(ii) K-2
(ii)
(a) Federated Averaging: K indicates how many local steps before the averaging starts.
diet storing stale
for in I...M:
grad(net, data)
iter $.2 x 1= and iter M v 1r
updates in parallel
delay the averaging adequately deal with high latency
with communication
sendin, id-iter)
Delay by
acc g
ellf iter F = Dr
5 1r
19 XI 1ter-51
avq_a
Correction
(i) K-1
(i) D-1,K-2
(ii) Pseudo code
(b) Delayed Gradient Averaging: indicates how many delayed steps before the averaging finishes.
We provide another interpretation of our algorithm DGA, iterating over the gradient iterations, for instance, the (LK- k-)th iteration in the pseudo code represents the 1-th round k-th iterations in Algorithm 1. The averaging occurs periodically with period K and the delay parameter D naturally shows up indicating the number of gradients between the sending and reception. The eyan cube in the visualization (a.b) indicates local computation and the yellow cube represents the transmission the averages. The red bar indicates when the averaging actually performed. In DGA, the transmission is in parallel to the computation, which is the main reason why DGA can tolerate high latency.
Figure 2:
Rewrite the update rule using the accumulated gradients mi and mi gives the compact form:
wh 22+++1 WL,D 'ISLDD
-mi
(compact DGA update)
gradient correction
serving as the main building block in our Algorithm 1.
In the most general setting, the delayed gradients could take several rounds before arriving. This happens when the latency is high, i.e. D > K. To take care of such cases, we express the delay parameter in the quotient/remainder form D sK quotient indicates the number of rounds skipped due to the latency. In this scenario, the gradients sent 1 round is received in the middle of the (-th round, which justifies
with 0 and r E [1, K]. The integer
in Algorithm 1. The example we discussed earlier in (compact DGA update) is a special case when 0, i.e. D K, where the gradients sent in the last round received in the current round.
call such operation as Delayed Gradients Averaging (DGA), as every round's averaging has been delayed to later rounds. With our designed gradient correction term in compact DGA update, blue part in Figure. 2b), each update ensures that all clients replace the previous round's local gradients by their averages, thus shares the same only differ on the most recent D gradients.
-rouu gradients. In another word, different workers
Last but not the least, in the ideal case when there is no delay, i.e. D = O. our algorithm DGA recovers the original Federated Averaging [27]. When > our algorithm DGA allows the clients to pipeline local updates with communication, and the divergence of Federated Average and DGA bounded by constant number. further clarify, we now conduct a sketch of the convergence analysis by bounding the staleness between different clients.
DGA requires to store the recent D) copies of gradients to perform the update. This can bring challenges to edge platforms when the model size is very large.
5

---

2.3 Theoretical Analysis
To start the convergence analysis, we assume that the objective function L-smooth:
Assumption (L-smoothhesss) Each function f((x) L-smooth, i.e. differentiable with L-Lipschitz gradient:
[|V/((>) V/(w))l = L| - yll- Vx, y E IR"
Remind that each individual function stochastic and we have access to an unbiased gradient g¹ such that BB(g [w)] (((ww) for any w and i. We further assume that g has bounded variance and second moment as in the analysis of FedAvg [51]:
Assumption 2 (Bounded gradients & variances). We assume that the unbiased gradients has bounded second moment and variance:
Ellg (w)ll S G?? and E -
s so² Vu,, Vi.
We now present main ingredients to drive the analysis. The first one is that no matter delayed gradient averaging is performed not, the average parameter across the clients always behaves as local gradient descent:
Lemma 2.1. Let us denote Wr.k = E wi k. as the average parameters across all clients at t-th round k-th iteration. Then always have
N
Y
W1
We.k
DiKk
N
The effect of the delayed averaging step is to align the gradient of the previous round across all clients, without changing Wr In other words, the delayed averaging step reduces the staleness between the clients and ensures the bounded variation given Assumption 2:
Lemma 2.2 (Bounded Variation). The difference between the i-th client and the average parameter across all clients is uniformly bounded:
E [|]
Wt, [| < 4n² + D2 Vi,ki
Comparing with FedAvg, the upper bound has an additional staleness D due to the delayed gradient averaging. Based on the bound, we can derive the following convergence result:
Theorem 2.3, Under Assumption and The sequence generated by DGA in Algorithm 1 with
stepsize 17 S satisfies
T
K
L + sou
fll 1=
- L
TK k=1
qTK
Our proof closely follows the analysis of FedAvg in the non-convex setting [51] and delay it to Appendix A.2. The upper bound on the right-hand-See rate of FedAvg, where (K 2)² taking places of K2 in [51]. Finally, when the number of rounds is large enough, we balance the terms by setting an appropriate stepsize:
is essentially the same as the convergence
Corollary 2.3.1. When the function f is lower bounded with f(wi) f pr S A and the number
rounds T is large enough such that T 2 N/(K D), then set the stepsize 1i LVT(K+D)
vN yields
1
T K
2LA +o²
D VNTK V K T
N(K
E =
TK
As long as D = O(K) and N(K - S /33 the first term dominates and our algorithm shares the same convergence speed /NT as the vanilla FedAvg. Meanwhile, as the communication is fully covered by computation, the total run time of DGA is TDGA TK Ty. which reduces the run time of FedAvg in (1) by a factor D In the high latency setting where delay can take multiple rounds, this run time improvement becomes significant.

---

DGA with momentum update To incorporate momentum update [31,33] in DGA, we combine the past gradients in an exponential weighted average:
- Bu Di,
where B is the momentum parameter, usually set as 0.9. Then we use it to perform the local update:
w W2,++1 { wi, nuii
if t: 전 D (mod K) or t - < 1;
wH,K n(ul,
1-90 1-3 (vi- -.a--------6 U--1-=)]
if k D (mod K) and 1 2 1.
where v/ = Ex=z The delayed gradient averaging step is calibrated carefully by a factor (1- 33/ B), due to the exponentially weighted averages. The derivation details are attached in Appendix. We remark that when 0, recover this to the vanilla update of DGA in Algorithm 1. For other other optimizers (c.g., Adam, RMSProp), such modification can be made similarly. We leave it of future work.
Comparison with Asynchronous While asynchronous methods remove synchronization lock and deal with heterogeneity between faster and slow workers, it does not take care of the latency issue. We first revisit the traditional ASGD [45]:
W :pull parameters - local evaluation - push gradients PS :collect gradients -> update parameters & send parameters
Each worker still suffers from high latency when pulling parameters, even though the central pa- rameter server asynchronous. In contrast, though our delayed averaging has a synchronization barrier (described in Figure 2b), it allows local gradient updates to be performed simultaneously as communication. other words, the workers (W) keep evaluating new local updates during the process of pulling/pushing parameters. The ability to pipeline communication with computation makes distinct differentiation between ASGD and DGA and allows us to achieve better training efficiency against high latency communication.
Comparison with FedAvg The delayed nature of our averaging step makes substantially different from the traditional averaging step. In FedAvg, the averaging step synchronizes the weights all clients, making sure that the next round starts with a common parameter. In contrast, our averaging happens in the middle of the second round, where additional local steps have been proceeded. Due to these D most recent local updates, the parameter w² 22, does not match w w2, after averaging, for distinct clients i * j. The encountered staleness is the trade-off for allowing computation during communication.
Comparison with SVRG For readers who are familiar with variance reduction techniques, the compact DGA update looks very similar to the update in SVRG [13]:
Wh-1 = we r (w
ff((w) + Vf()),
(SVRG update)
where to is snapshot reference point and V f is the full gradient. The introduction of such reference point in SVRG reduces the variance of stochastic gradient, leading to faster convergence analysis than vanilla SGD.
Although the two formulas share a common pattern, there is an intrinsic difference in the choice of the averaged gradients. In SVRG, the full gradient is evaluated at the reference point W, which must be common at all i; in contrast, the averaged gradients our algorithm is not a full gradient by any means, because of the staleness introduced by the extra local updates. Moreover, SVRG uses fixed reference point à inside the same round while as the vector my in our algorithm an accumulation of gradient of the entire round, (accumulated averages). Hence SVRG and DGA are incomparable from their starting point: while as SVRG aims to reduce variance based on a fixed reference point, DGA is targeting the latency, favoring staleness.
Perhaps the works closest to ours is delayed SGD [2, 14,23,52), where the update rule given by Wk+1 Wk (d)- In this case, the gradient updates delayed but there is no correction
7

---

Table Ablation studies about our gradient correction term. Without our correction term, using pure stale gradients suffers from significant accuracy drop. The accuracy is measured on CIFAR-10.
w/o gradient correction
w/ gradient correction
K=5, D=5
88.7
89.2
K=5, D=10
86.9
89.3
K=5, D=15
85.5
89.0
K=5, D=20
84.2
88.7
term as DGA. Though these studies show sub-linear convergence in theory, such simple method accumulates the staleness over iterations and hurts model performance especially when the delay steps is large as shown Table. Therefore, they cannot handle high latency network.
To summarize, we have introduced the delayed gradient averaging, which delays the averaging operation thus allows local updates to be pipelined with communication. We then design correction term to handle delayed gradients and compensate the staleness. We next conduct experiments showing that DGA speeds up FedAvg without losing accuracy.
3 Experiment
3.1 Accuracy Evaluation
We evaluate the effectiveness of DGA diverse tasks: Image classification CIFAR-10 [19] and ImageNet [20], next word prediction on Shakespheare [41]. We implement DGA in Py PyTorch framework [30] and choose Horovod [40] the distributed training backend. The task-specific details are described below.
On CIFAR- 10 [19], we train MobilenetVV2-0.2 [37] using 64 workers and each equips with single V100 GPU. The training epochs 200 and the batch size 64 per worker. The learning rate n is initially set to NUM MPUS x 0.0125 and momentum / is 0.9, The learning rate linearly increases during the first 5 epochs, following the warm-up strategy in [8], and then decays with cosine anneal schedule.
On ImageNet [7], evaluate ResNet-50 [11] with 64 worker nodes. The total mini-batch size is 2048, and we train the model for 150 epochs. We apply the warm-up strategy in [8] to schedule the learning rate and only random crop and flip are used as data augmentations the training. The learning rate adopts the same scaling strategy as CIFAR's.
On Shakespeare, adopt the 2-layer LSTM language model architecture with 1,500 hidden units per layer [32] and follow the preprocessing in Leaf [4]. We set the learning rate to 20 and clip gradients with larger than 0.25 avoid gradient explosion. The model trained with 40 epochs while the first epoch is used for warm-up.
Table 2: Comparison of FedAvg and our DGA's accuracy on 3 datasets with both i.i.d and non- i..d partitions. The speedup measured on latency with latency, Not only DGA demonstrates consistent training speedup, but also DGA maintains the accuracy, on both i.i.d and non-i.i.d partition.
FedAvg (K=5)
FedAvg (K=10)
FedAvg (K=20)
DGA
Datasets
Partition
(K=5, D=20)
Acc
Speedup
Acc
Speedup
Acc
Speedup
Acc
Speedup
i.dd 88.7
88.5
88.1
88.6
CIFAR
1x
1.51
2.05x
3.16x
non-i.id
48.2
47.2
43.9
48.0
iid 76.6
76.5
76.2
76.4
ImageNet
1x
1.43
1.81
2.55x
non-i.id
55.4
52.5
48.6
54.9
iidd 47.6
47.3
47.4
47.1
Shakespeare
1x
1.66x
2.51 x
4.07 x
non-i.i.d
36.9
34.3
30.1
36.3

---

For non-i..d. experiments, we follow the partition used in [2] to split the dataset. In CIFAR and ImageNet, we distribute the dataset such that each device only contains samples from two classes. In Shakespeare dataset, each role is considered as data source and each device only has two sources.
We show the accuracy and run time comparison when the latency is 1s in Table 2, the speed up is measured in run time, normalized by the run time of FedAvg (K=5);
When we compare FedAvg(K = 5) with DGA(K = 5, D = 20), DGA achieves a speed up from 2.5x to 4.07 x with almost no accuracy drop.
To strengthen the baseline, we increase K in FedAvg, which amortizes the effect of latency. However, increasing K reduces the communication frequency, degrading the model performance. especially in the non-i.i.d. setting. As the data distribution is usually non-i.i.d in federated learning, increasing too much K is not good idea to compensate communication cost.
Therefore, DGA is the clear winner which achieves notable speedup while maintaining accuracy in the high latency setting. This is because DGA (i) keeps the same communication frequency (ii) pipelines the communication and local updates, fully covering the latency by local computations. We attach the training curve and ablation studies of different D in Appendix. A.I.
3.2 Speedup Comparison
Throughout the derivation of DGA, have assumed that the latency remains constant. However, in the real-world scenario. latency may vary due to unstable connection and packet losses. One way to handle such potential fluctuation is to set a large delay parameter D, pretending the worst scenario happens. In other words, we will artificially set D to be a large number even though the actual latency is small. In this way, we can study how the variation on latency changes the performance of DGA.
In order simulate different network conditions, we evaluate the effectiveness of DGA in two different ways. We first experiment allows us to control the communication delays precisely. Then we build up a Raspberry Pi clus- ter consisting of 16 Model 4B+ devices and use Netgear R6300v2 to provide the connection, which reflects a realistic home Wi-Fi environment for federated learning as shown in Figure. 3.
set of synthetic latency controlled by Netem [29], which
In the Figure. 4a, we manually simulate the network latency from Ims to 5000ms via Netem [29], and plot the normalized run time. The run time normalized by FedAvg (K 5) with latency Ims, which serves as the baseline of in-cluster training. When the latency gradually increases, FedAvg slows down almost linearly. Though setting a larger number of local steps K can alleviate the degradation, the performance gap still growing. Moreover, let alone a too large K will hurt the final accuracy drastically as shown in Section 3.1. In contrast, DGA (solid red line) as shown in Figure 4a, consistently yields a stable speed as long as the latency is covered by the threshold D. Even under an extreme communication delay (e.g.. 5 seconds), the training speed is not much affected.
Next we benchmark Figure. 4a.. Instead of simulating different latency settings, we consider four representative cases for federated learning [i] wired [ii] (wireless) conducted on two racks. different rooms [iii] (wireless) different floors [iv] (wireless) different buildings, where the latency numbers are Ims, 16ms and 132ms and 470ms respectively. By placing the Pi cluster at different locations, we can emulate different quality of connection. Different from synthetic latency, the real wireless connection also suffers from unpredictable network stragglers and packet loss, thus the overall throughput on Pi-clusters is worse and FedAvg's 's performance degrades more quickly. Even under such challenging network, the throughput of DGA remains steady.
settings on the Raspberry Pi cluster in the
Figure 3: Our Raspberry Pi farm. Experiments are
We adopt small models LeNet and 2-layer istm for the benchmark. Given the limited computation budget of edge devices, the batch size is reduced to 1/8 of the original ones. To better evaluate our algorithm, we choose the most challenging settings where devices are linked through wireless connections from different buildings. With an average latency of 470ms, FedAvg's training is significantly slowed by the communication.
Figure. 5 shows the speedup ratio (scalability) on the Pi cluster.

---

0.8
Thouughut Degrotation
0.9
Thooghhus Degratatin
0.6
0.8
FedAvg, K-5
FedAvg. K-5
0.4
FedAvg, K-10
FodAvg, K-10
FedAvg. K-20
FedAvg. K-20
DGA K-5, D-20
DGA, K-5, D-20
10'
10"
10"
10
10'
10'
Lateney (ms)
Latency(ms))
(a) GPU with Netem [29] generated syn- thetic latency from Ims to 5000ms.
(b) Raspberry Pi cluster (16 nodes) with real-world latency (Ims, 16ms, 132ms, 470ms).
Figure 4: Benchmark FedAvg [27] and DGA on different communication latency. On both latency settings, FedAvg's performance starts to degrade when latency grows, while DGA shows stable performance even under extreme latency.
Vision
13.1
Language
Speedup
Speedup
3.7
3.9
1.01.0100
0.4
1.7
1.0
1.7
2.1
1.01.01.1
0.71.0
1.4
2.2
3.9
2
16
Number of Nodes
Number of Nodes
FedAvg (K=5)
FedAvg(K=10)
DGA (K=5, D=20)
The speedup comparison between FedAvg and DGA on Raspberry Pi cluster. On both vision and language tasks, DGA demonstrate consistent improvement over FedAvg.
Figure 5:
When scaling the training two devices, the speedup ratio is only 0.6, which is even slower than single devices. Instead, our proposed DGA demonstrates ideal scalability under a lige-lytency network. When scaling to eight devices, the speedup ratio about 13.1. This performance is close what conventional algorithms achieved inside data center.
4 Conclusion
In this paper, we propose Delay Gradient Averaging (DGA) to tolerate high network latency in federated learning. We have justified that the theoretical convergence is slower than FedAvg in non-convex settings. We further demonstrate that our algorithm is capable enjoying high scalability under poor network conditions and preserving accuracy especially on non-i.i.d partitions. Furthermore, on a realistic setup consisting of 16 Raspberry Pi devices, our algorithms demonstrate consistent speedup previous algorithms. We believe that our work will enable wide range of federated learning applications in high latency network.
Acknowledgement
We thank MIT-IBM Watson AI Lab, Samsung, Woodside Energy, and NSF CAREER Award #1943349 for supporting this research. Hongzhou Lin acknowledges that the work done prior to joining Amazon. Yao Lu acknowledges that the work is done prior to joining Google.
10

---

References
[1] Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovie. QSGD:
Communication--ffiiteee sgd via gradient quantization and encoding. Advances in Neural Information Processing Systems (NIPS), 2017. 3
[2] Yossi Arjevani, Ohad Shamir, and Nathan Srebro. A tight convergence analysis for stochastic
gradient descent with delayed updates. arXiv preprint arXiv: /806. 10188, 2018. 7
[3] Keith Bonawitz, Hubert Eichner, Wolfgang Grieskamp, Dzmitry Huba, Alex Ingerman, Vladimir Ivanov, Chloe Kiddon, Jakub Konečný, Stefano Mazzocchi, H Brendan McMahan, et al. Towards federated learning at scale: System design. arXiv preprint arXivv:902.0// 000400 2019.
[4] Sebastian Caldas, Sai Meher Karthik Duddu, Peter Wu, Tian Li, Jakub Konečný, H Brendan McMahan, Virginia Smith, and Ameet Talwalkar. Leaf: A benchmark for federated settings.
arXiv preprint arXiv: 1812.000/ 2018. 8, 9, 14
[5] Kai Chen and Qiang Huo. Scalable training of deep learning machines by incremental block training with intra- antra-block parallel optimization and blockwise model-update filtering. In 2016 ieee international conference on acoustics, speech and signal processing (icassp), pages 5880-
5884. IEEF, 2016. 3
[6] Jeffrey Dean, Greg S Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Quoc V Le, Mark Z Mao, Mare' Aurelio Ranzato, Andrew Senior, Paul Tucker, et al. Large scale distributed deep networks. In Advances in Neural Information Processing Systems (NIPS), 2012. 1
[7] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In IEEE Conference on Computer Vision and Puttern Recognition
(CVPR), 2009. 8
[8] Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch sgd: Training imagenet in 1 hour. arXiv preprint arXiv: arXiiv:776..22 1207.0267, 2017. 1, 8
[9] Farzin Haddadpour, Mohammad Mahdi Kamani, Aryan Mokhtari, and Mehrdad Mahdavi. Federated learning with compression: Unified analysis and sharp guarantees. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2021. 3
[10] Andrew Hard, Kanishka Rao, Rajiv Mathews, Swaroop Ramaswamy, Françoise Beaufays, Sean Augenstein, Hubert Fichner, Chloé Kiddon, and Daniel Ramage. Federated learning for mobile keyboard prediction. arXiv preprint arXiv: /8/ I. 1.03604, 2018.
[11] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Conference on Computer Vision and Pattern Recognition (CVPR), 2016.
[12] Kevin Hsieh, Aaron Harlap, Nandita Vijaykumar, Dimitris Konomis, Gregory R Ganger, Phillip B Gibbons, and Onur Mutlu, Gaia: Geo-distributed machine learning approaching LAN speeds. In 14th Symposium on Networked Systems Design and Implementation (NSDI 17), pages 629-647, 2017.1
[13] Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances neural information pr processing systems (NIPS), 2013.
[14] Pooria Joulani, Andras Gyorgy, and Csaba Szepesvári. Online learning under delayed feedback.
In International Conference on Machine Learning (ICML), 2013. 7
[15] Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Ar- jun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning. arXiv preprint arXiv:1912.0440) 1912.0477,
2019. 1,3
[16] Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conferences on Machine Learning (ICML), 2020. 3
(17) Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter theory for local sgd on identical and heterogeneous data. In International Conference on Artificial Intelligence and
Statistics (AISTATS), 2020. 3
[18] Jakub Konečný, H. Brendan McMahan, Felix X. Yu, Peter Richtarik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. In NIPS Workshop on Private Multi-Party Machine Learning, 2016.
[19] Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images.
Technical report, University of Toronto, 2009. 8

---

[20] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural neural networks. In Advances in Neural Information Processing Systems (NIPS).
2012. 8
[21] Tian Li, Maziar Sanjabi, Ahmad Beirami, and Virginia Smith. Fair resource allocation in federated learning. In International Conference on Learning Representations (ICLR), 2020.
[22] Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang. and Zhihua Zhang. On the convergence of fedavg on non-iid data. In International Conference on Learning Representations (ICIR),
2020. 3, 9
[23] Youjie Li, Mingchao Yu, Songze Li, Salman Avestimehr, Nam Sung Kim, and Alexander Schwing. Pipe-SGD: A decentralized pipelined sgd framework for distributed deep net training.
In Advances in Neural Information Prucessing Systems (NIPS), 2018. 7
[24] Zhize Li, Dmitry Kovalev, Xun Qian, and Peter Richtárik. Acceleration for compressed gradient descent in distributed and federated optimization. In International Conferences on Machine Learning (ICML). 2020.
[25] Yujun Lin, Song Han, Huizi Mao, Yu Wang, and William Dally. Deep gradient compression:
Reducing the communication bandwidth for distributed training. In International Conference on Learning Representations (ICLR), 2018 1,3
[26] Wei Liu, Li Chen, Yunfei Chen, and Wenyi Zhang. Accelerating federated learning via momen- tum gradient descent. IEEE Transactions on Parallel and Distributed Systems, 18):1774-1166
2020.
[27] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas
Communication-effiiee learning of deep networks from decentralized data. In International
Conference on Artificial Intelligence and Statistics (AISTATS), 2017. 1, 2, 3, 5,
[28] Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. In International Conference on Machine Learning, pages 4615-4625, PMLR, 2019. 3
[29] Netem network emulator. https:
9, 10
[30] Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang. Zachary De Vito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. In NIPS 2017 Autodiff Workshop, 2017. 8
[31] Boris T Polyak. Some methods of speeding up the convergence of iteration methods. USSR Computational Mathematics and Mathematical Physics, 4(5) 1964. 7
[32] Ofir Press and Lior Wolf. Using the output embedding to improve language models. arXiv preprint arXiv: 1rXivvv608..00 05859, 2016. 8
[33] Ning Qian. On the momentum term in gradient descent learning algorithms. Neural networks,
12(1):145-151, 1999. 7
[34] Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný. Sanjiv Kumar, and H Brendan McMahan. Adaptive federated optimization. In International Conference on Learning Representations (ICLR), 2021. 3
[35] Amirhossein Reisizadeh, Aryan Mokhtari, Hamed Hassani, Ali Jadbabaie, and Ramtin Pedarsani. Fedpaq: communication-efffieen federated learning method with periodic averaging and quantization. In International Conference on Artificial Intelligence and Statistics (AISTATS),
2020.
[36] Daniel Rothchild, Ashwinee Panda, Enayat Ullah, Nikita Ivkin, Ion Stoica, Vladimir Braverman, Joseph Gonzalez, and Raman Arora. Fetchsgd: Communication--effiiiee federated learning with sketching. International Conferences on Machine Learning (ICML), 2020.
[37] Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginov, and Liang- Chieh Chen. Mobilenety2: Inverted residuals and linear bottlenecks. In Conference on Computer Vision and
Pattern Recognition (CVPR), 2018. 8
[38] Felix Sautle,, Simon Wiedemann, Klaus-Robert Müller, and Wojeiech Samek. Robust and communication-efficcn
federated learning from non-iid data. IEEE transactions on neural networks and learning systems, 31(9):30003413, 2019.
[39] Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and its application to data-parallel distributed training of speech dnns. In Fifteenth Annual Conference of the International Speech Communication Association, 2014.
[40] Alexander Sergeev and Mike Del Balso. Horovod: fast and easy distributed deep learning in tensorflow. arXiv preprint ar Xrx:v: 008.80209999. 2018. 8
12

---

[41] The complete works of william shakespeare.
https://ww.. wtteeeooccceeeeeeeeeeeeeeeeeeeee kenm//wwwwbl//
com
shakespeareonline. 8
[42]
Speedtest global index. https://wwx
[43] Peng Sun, Wansen Feng, Ruobing Han, Shengen Yan, and Yonggang Wen. Optimizing network performance for distributed dnn training on gpu clusters: Imagenet/alexnet training in 1.5 minutes. arXiv preprint wtXiv:/902.06888
2019. 1,
[44] Hanlin Tang, Xiangru I. Lian, Tong Zhang, and Ji Liu. Doublesqueeze: Parallel stochastic gradient descent with double-pase
corpeccmmensttedd compression. In International Conferences on Machine Learning (ICML), 2019.
[45] John Tsitsiklis, Dimitri Bertsekas, and Michael Athans. Distributed asynchronous deterministic and stochastic gradient optimization algorithms. IEEE transactions on automatic control,
3 31()):8038112, 1986. 7
[46] Monthly ip latency data. https://www verizon. wtwpoounninnnettttttteeeeeeeeeee
2
[47] Jianyu Wang, Vinayak Tantia, Nicolas Ballas, and Michael Rabbat. Slowmo: Improving communication-efiiieett distributed sgd with slow momentum. In International Conference Learning Representations (ICLR), 2020. 3
[48] Jianqiao Wangni, Jialei Wang, Liu, and Tong Zhang. Gradient sparsification for commumication-effiiiii cessing Systems (NIPS), 2018.
distributed optimization. In Advances in Neural Information Pro-
[49] Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang. Yiran Chen, and Hai Li. Terngrad: Ternary gradients to reduce communication in distributed deep learning. In Advances in Neural Information Processing Systems (NIPS), 2017. 3
[50] Jie Xu, Benjamin Glicksberg, Chang Su, Peter Walker, Jiang Bian, and Fei Wang. Federated learning for healthcare informatics. Journal of Healthcare Informatics Research, 5(1):1-19,
2021.
[51] Hao Yu, Sen Yang, and Shenghuo Zhu. Parallel restarted sgd with faster convergence and less communication: Demystifying why model averaging works for deep learning. In Proceedings the AAAI Conference on Artificial Intelligence, 2019. 3,
[52] Martin Zinkevich, John Langford, and Alex J Smola. Slow learners are fast. In Advances in Neural Information Processing Systems (NIPS), 2009. 7
13


Reviews:
[{"review_id": "iIes9NiPC4c", "reviewer": "Reviewer_XyoU", "summary": "The work proposes to overlap the local gradient computation step on each client in a federated ML setup with the latency cost associated with communicating the averaged gradients from all clients. This is done by allowing the clients to proceed with computation of local gradients on K mini-batches for a new round (t+1) using the latest local parameter until the gradient average from the previous round (t) is received with a delay (aka, *Delayed Gradient Averaging*). In doing so, the client is said to have performed D extra local updates which are combined with the delayed gradient average. The work is said to be the first of its kind to consider high latency (>1s) situations to perform scalable federated learning without sacrificing performance.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Originality:**  \nThe work seems to belong to the field of asynchronous communication within Federated Machine Learning setups with a rich body of literature. However, the paper does not mention this direction as part of related work and how the proposed DGA framework is novel and unique. The introduction of communication cost D is interesting to characterize the number of additional local updates a client makes in each round.\n\n**Quality:** \n\nThe proposed work provides theoretical guarantees for convergence and how it is possible to recover the vanilla FedAVG [28] and SVRG [13]. The experiments support the theoretical analysis. Experiments with Raspberry Pi are a good contribution to characterize real-world latency effects on various algorithms. The authors mention in the checklist that they discuss the limitations of their work. It will be better if they can highlight it in the manuscript as I could not find the discussion.\n\n**Clarity:** \n\n1. Please clarify how this work is different from asynchronous communication setups to bring the novelty to work\n2. What is the relationship between periodic synchronization (averaging, denoted as K? as per Fig 2 caption) and delayed averaging period in this work? Is there a way to optimally compute the delayed averaging period and what should it be dependent on?\n\n- Line 264:  should be Figure 3b\n- Lines 235-236: must mention this is for Shakespeare dataset as per Table 1\n- Lines 272-280: Discussion is provided for Fig 4 (mobile net) while the reader is expected to draw the same analysis for LSTM. The paper must make similar references to the other figure\n\n\n**Significance:** \nThe work is interesting as it tries to show a simple delayed averaging could help overlap computation and communication in federated setups. I am not sure how it is different from asynchronous setups and the impact of staleness on final performance. A literature survey is missing for asynchronous FL setups.\n\n----------------------------\n**After Authors's Comments**\n\nThe above comparison between asynchronous and DGA must be a part of your manuscript to clarify the difference and misunderstanding the readers might face. The timing diagram further helps to understand better. Please use **Pipelining** as this is a proper technical term for overlapping and also gives more clarity to folks from Systems research to put your work in context. \n\n*Authors must clarify and highlight the limitations of the work in the manuscript as claimed in the checklist.* \n\nI am happy to increase my score from 4 to 6.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "*Authors must clarify and highlight the limitations of the work in the manuscript as claimed in the checklist.* ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "fPDLcbCQJA4", "reviewer": "Reviewer_ZCJE", "summary": "Authors propose a method that allows communication in federated learning to run in parallel with local gradient computation; practically removing the communication delay. Authors provide theoretical convergence bounds and compare their method with two different but similar algorithms (only in writing). Authors provide formulation for both with and without momentum on local gradient updates.\n Authors also provide experimental analysis on non-FL datasets (CIFAR, ImageNet, Shakespeare) that are sharded to adapt to FL settings. Authors also provide results from an implementation of the algorithm on eight raspberry pi devices.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Although paper suggests federated learning as the target problem, authors fail to provide an algorithm (or an experimentation result of one) that can be used in a real world fl setting. Here are some of the concerns I have:\n* In FL, local datasets can (and most likely will) have different number of examples, assuming that all clients go through K local updates is far from reality (this setting is only applicable to distributed training)\n* In my opinion, running FL algorithms on non-FL datasets is no longer acceptable for FL papers, I'd suggest running experiments with FL datasets like the ones in LEAF.\n* Authors have not considered weighted averaging between clients in FL.\n* The proposed method is not compatible with approaches that provide alternative losses for local devices, e.g. FedProx.\n* In the algorithm 1, authors mention that clients send gradients to each other in the communication phase, this is more close to peer-to-peer learning, in FL a central server maintains the model and handles communications.\n* Authors assume that all clients participate in all rounds, in real world settings usually there are many clients and a small sub set of them are selected for each round. \n* Authors do not mention privacy which should be at least discussed in every FL paper.\n* Assuming that all clients have the same computation power  is also an impractical assumption, i.e. local gradient computation takes Tg time for all clients\n* Although I was pleasantly surprised to see that the authors have tried their algorithms on Raspberry Pi devices, only doing the experiment on 8 devices is again more similar to what happens in distributed training rather than in FL where there are usually at least thousands of devices.\n\nI would suggest that authors re-write the paper having distributed training (or cross-silo FL) as the target problem and propose their solution for when the delay between the compute nodes is considerable, alternatively authors can address the comments and adapt their algorithm to FL settings.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "this work has no societal impact or limitations.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "PVcmKDwDJiA", "reviewer": "Reviewer_e8gp", "summary": "This paper propose a delayed gradient averaging method to hide communication latency behind computation in federated learning scenario to achieve better speedup. Theoretical and experimental results all show its advantage over FedAvg in some scenarios. The authors also carefully design simulate real federated learning environment to evaluate their method.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The overall writing of this paper is good and the description of their method is pretty clear.  The idea itself is simple but the author gives a detail convergence analysis. And the authors also design their experiments carefully. I have several questions and suggestions:\n1. It is well known that with the increasing of parallel workers, the accuracies of models trained by model-averaging like method will degrade a lot. In this paper, only models trained with 8 workers are evaluated. According to my experience, 8-worker is a pretty safe distributed training setting. Could you also give the model accuracies of other configs (1, 2, 4,16,32 ...) to compare the accuracy degradation levels of FedAvg and DGA? With these experiments, we can gain more insight about the true strength and shortcomings of DGA over FedAvg.\n2. In the main paper, the K for DGA is set to 5 and in the supplementary material, it is set to 1. But for FedAvg, K=5 10 and 20 are tried. Does it mean that DGA only works for small sync period due to the staleness introduced by delayed averaging ?  Acturally more frequent communication will bring additional money cost in real scenarios. Could you also add some experiments to show the influence of \"D\" ?\n3.  For distributed training with momentum, an important pioneer work is missing:\nChen K, Huo Q. Scalable training of deep learning machines by incremental block training with intra-block parallel optimization and blockwise model-update filtering[C]//2016 ieee international conference on acoustics, speech and signal processing (icassp). IEEE, 2016: 5880-5884.\n SlowMo extends this work to more tasks.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors should conduct more experiments with different number of workers, sync periods, and normalized communication cost, to show the true shortcomings and advantages of their method.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "FHSry9hJdz", "reviewer": "Reviewer_9p8v", "summary": "This paper presents a new distributed federate learning method, DGA, to overcome long communication latency. The authors provide theoretical analysis about DGA's convergence rate, which shows that DGA makes same convergence as FedAvg, and empirically show that DGA can tolerate long network latency without hurting the accuracy. DGA delays the gradient averaging to a future iteration so that the communication can be overlapped with local update computation, which enables scalability even under long latency and network stragglers. In detail, in DAG, a training is divided into communication rounds, and each round consists of K local updates and one synchronization (gradient averaging). DGA allows gradient averaging at i-th round to D-th updates in a future round. DGA achieves high speed-up without hurting the accuracy by allowing the same communication frequency while reducing latency by controlling D knob.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Thank you for submitting your work to NeurIPS 2021. Here is a summary of strengths of the paper. \n\n[+] This paper tries to address an important problem (long network latency bottleneck) in federate learning (enable efficient learning under long network latency)\n\n[+] algorithm description is easy to understand\n\n[+] experiment with Raspberry Pi for real world wireless communication environment.\n\nBut, I have a few serious concerns about the paper. \n\n[-] It looks that the technical depth is not mature enough for publication . The idea of overlapping communication for synchronization at i-th round and computation at (i+1)th round and allowing stale gradient values looks quite straightforward.\n\n[-] It seems that authors' assumption about network BW and latency might hold for very limited domains/use cases. How many application domains.use cases the author's assumptions about BW and latency, BW is enough but latency is long, hold for?  \n\n[-] Experiments with 8 workers looks insufficient. It would be great if the authors could provide experiment results with larger number of workers than 8.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "This paper does not have any ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4.5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes an approach to make Federated training more efficient by pipelining communication and computation. In particular, clients continue performing local updates on a previous model while they are communicating with the server. In addition to some theoretical convergence analysis for the smooth non-convex setting, the paper provides empirical evidence supporting the promise of this approach both in simulation and in an implementation using Raspberry PI’s. The approach seems especially well-suited for cross-silo federated learning when clients have unreliable communication channels or communication latency is otherwise a bottleneck.

While the reviewers raised some significant concerns in their initial reviews, the author responses largely addressed these in a satisfactory way, leading multiple reviewers to raise their scores. As a result, I’m happy to recommend that we accept this paper. When preparing the camera ready version, the authors are expected to implement the suggestions and corrections that were discussed during the rebuttal period. In particular, it is important to:
* Include the additional experiments (LEAF, CIFAR with 1k devices) either in supplementary material, or by moving other material to supplementary material, as you see fit, 
* Clarify terminology and concepts (e.g., using “pipelining”, differentiating from asynchronous methods)
* To include clarifications about the implementation using a centralized parameter server vs. peer-to-peer synchronization
* Clarify the limitations around privacy guarantees, additional storage, and challenges around supporting other optimizers
* Adding additional references suggested be reviewers
Decision: Accept (Poster)