Delayed Gradient Averaging: Tolerate the Communication Latency in Federated Learning
Year: 2022

Abstract:
Federated Learning is an emerging direction in distributed machine learning that enables 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 such as FedAvg [27] become less efficient when the latency increases. To overcome the problem, we propose Delayed Gradient Averaging (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-IID partitions, and show DGA can bring 2.55⇥ to 4.07⇥ speedup. Moreover, we built a 16-node Raspberry Pi cluster and show that DGA can consistently speed up real-world federated learning applications.

heading: 1 Introduction
text: 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 are exchanged between clients and servers, thus private training data never leave local devices, enhancing privacy. Many successful applications such as 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 (1ms) network is available, edge devices are 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], lowrank 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) long-distance transmission (Figure. 1.(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-geographic located data entails a minimum latency cost: even with the speed of light, it requires hundreds of milliseconds to send a packet across the world. In either case, the high latency is a hard barrier introduced by physical limits thus inevitable. If not handled specifically, such communication lag, in the magnitude of hundreds of milliseconds, or even seconds, will significantly degrade the scalability of the learning algorithm as shown in the Figure. 1.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
16x4 = 64 cards, batch size 32-2
latency(ms) Scalability speed
1us 1.00 504 501 5 1ms 0.99 501 503 10 10ms 0.94 472 472 20 100ms 0.70 352 447 50
500ms 0.29 145 399 100 1s 0.17 87 352 200
234 500
145 1000
87 2000 39 5000
Sp ee
du p
0.00
0.25
0.50
0.75
1.00
1us 1ms 10ms 100ms 500ms
98x worse4x worse
Across the World > 100ms Wireless Connection ~ 20ms Within a Rack <1us Within a Data Center ~ 1ms
(a) Conventional Distributed Settings (b) Federated Distributed Settings
(<1us) Within a Rack
(~1ms) Within a Data Center
(a) Conventional Distributed Settings
(b) Federated Distributed Settings
Sp ee
du p
0.00
0.25
0.50
0.75
1.00
1us 1ms 10ms 100ms 500ms
98x worse 4x worse
(c) System Performance Comparison
Within a Rack (<1us)
Within a Data Center (~1ms) World-wide (> 100ms)
Wireless (~ 20ms)
(a) Conventional Distributed Settings
(b) Federated Distributed Settings
(~20ms) Across the World
(> 100ms)
Wireless ConnectionWirel ss Connection (~20ms)
1
In this paper, we propose Delayed Gradient Aggregation (DGA) to address the latency bottleneck. The key idea is to delay the gradient averaging to a future iteration thus the communication can be pipelined with computation. By accepting stale average gradients for model updates, DGA allows the communic tion to execute par llel with the computation, thus scalable even under extreme 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 a factor 2.6⇥ to 4.1⇥ over various datasets; (ii) no accuracy drop under extreme communication lag (e.g., > 1 second). We further set up a 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:
• 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 can achieve scalable federated training under high latency (>1s).
• We theoretically justify the convergence of DGA. We show that under reasonable delay interval, it shares the same convergence rate as FedAvg [51]. We also discuss its extension with momentum update to better suit modern federated optimizations.
• We empirically evaluate the accuracy on 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.i.d and non-i.i.d partitions.
• We build up a Raspberry Pi cluster of 16 devices to evaluate our algorithm in a real-world setting. Even with unpredictable packet loss and latency fluctuation, DGA still shows consistent speedup.

heading: 2 Delayed Gradient Averaging

heading: 2.1 Problem Setting, Preliminaries and Related Works
text: In this work, we formalize the problem as the minimization of sum of stochastic functions,
min w
f(w) = 1
N
NX
i=1
fi(w) with fi(w) = E⇣i [Fi(w, ⇣i)],
where N denotes the number of clients and fi represents the loss function on i-th client. In the setting of empirical risk minimization, fi could be further expressed as finite sums and the random variable ⇣i corresponds to a mini-batch sample.
Computation and Communication cost Each client represents a computational resource that can either perform local gradient updates or exchange information with others. We model the computation and communication cost by:
• We encounter a computational cost ⌧g for each gradient/mini-batch evaluation. • The communication suffers a cost ⌧c per transmission. We further define the normalized com-
munication cost: D =
⇠ ⌧c
⌧g
⇡ .
2
In other words, one communication round takes the same amount of time as D gradient updates. This normalized cost D serves as the main parameter in our discussion on the computation/communication 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⇥local updates ! averaging (communication) · · · where the parameter K indicates the number of mini-batches (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
TFedAvg = T (K⌧g + ⌧c) = T
✓ K + ⌧c
⌧g
◆ ⌧g ⇡ T (K +D) ⌧g. (1)
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 running 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, 22, 28, 51], its momentum variants [5, 26, 47], variance reduced variant SCAFFOLD [16] and adaptive variant [34], etc.
Compression/Quantization techniques in FL To improve communication efficiency, extensive efforts have been devoted to reducing the bits on gradient exchanges in large-scale distributed training. Techniques such as 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 a factor of 1000, while maintaining the high performance of the model. These techniques have been successfully applied to accelerate FL [9, 24, 35, 36], enabling training on 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 a hard physical barrier. To focus on such inherent and non-improvable subject, we assume that the bandwidth is sufficient,* and the communication cost ⌧c is dominated by network’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/quantization 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.

heading: 2.2 A step-by-step walk through Delayed Gradient Averaging
text: The main idea of our algorithm is to 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 is 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 t-th round by the received averaging
(we will detail this step right away). *otherwise apply gradient compression techniques.
3
Algorithm 1 Delayed Gradient Averaging (DGA)
1: Initialize each worker with wi1,1 = w1 for i 2 [1, N ], the number of local update K, the delayed parameter D 1. Define s = (D 1)//K as the integer quotient. 2: for rounds t = 1, · · · , T do 3: for client i in parallel do 4: Set wit,1 = wit 1,K+1 as the last iterate at round (t 1) 5: for k = 1, · · · ,K do 6: Sample the stochastic gradient git,k at the previous iterate w i t,k and update
w i t,k+1 =
( w
i t,k ⌘git,k if k 6⌘ D (mod K) or t 1 s < 1;
w i t,k ⌘(git,k mit 1 s +mt 1 s) if k ⌘ D (mod K) and t 1 s 1.
where mit 1 s is the accumulated gradient (see line 8) at the earlier round t 1 s, mt 1 s is the average of mit 1 s among all clients, i.e. mt 1 s = 1 N P i m i t 1 s.
7: end for 8: Send the t-th round accumulated gradient mit = PK k=1 g i t,k to all other clients. †
9: end for 10: end for 11: Return wT = 1N PN i=1 w i T,K+1.
The benefit is plain to see: we no longer freeze the local computation power during the communication. To make the discussion more explicit, we denote the parameter on the i-th client at the k-th iteration within the t-th round by wit,k and the corresponding stochastic gradient as g i t,k. In the very first round t = 1, solely local updates are performed, hence the last iterate in the first round can be expressed as
w i 1,K+1 = w i 1,K ⌘gi1,K = · · · = w1 ⌘
KX
k=1
g i 1,k
| {z } :=mi1
.
As the first round’s computation has completed, we send the accumulated gradient mi1 := PK k=1 g i 1,k to all the clients, i.e. perform averaging. Right after the gradients are sent, we immediately proceed the second round’s local updates, leaving the first round averages in transmission. By the time the average is received, we already performed D extra local updates in the second round, starting from the last iterate of first round wi1,K+1:
w i 2,D ⌘gi2,D| {z }
last iterate before averaging
= · · · = wi1,K+1 ⌘ DX
k=1
g i 2,k
| {z } D updates
= w1 ⌘ KX
k=1
g i 1,k
| {z } 1st round
⌘ DX
k=1
g i 2,k
| {z } 2nd round
. (2)
At this point, the average of the first round arrives
m1 = 1
N
NX
i=1
m i 1 =
1
N
NX
i=1
KX
k=1
g i 1,k =
KX
k=1
1
N
NX
i=1
g i 1,k
! := KX
k=1
g1,k, (accumulated averages)
where g1,k represents the average gradient at k-th iteration in the 1st round. With the averaging m1 in hand, we substitute all the first round local gradients in Eq.2 by their averages, leading to:
w i 2,D+1 = w1 ⌘
KX
k=1
g1,k
| {z } common on all clients
⌘ DX
k=1
g i 2,k
| {z } 2nd round unchanged
(delayed gradients averaging)
†The accumulated gradient is indeed implemented as mt mt + git,k under the for loop on k, which do not require extra memory to store gt,k.
4
Computation Communication Synchronization Barrier
Increased latency slows the training!
Latency is amortized by multiple steps, but still slow the training! No longer blocks the training!
(1) Vanilla Synchronous SGD
for i in iters: L = loss(net, data, label) grad[i] = L.backward() send(grad[i], iter=i) avg_grad = recv(iter=i) W = W - lr * avg_grad
for i in iters: L = loss(net, data, label) grad[i] = L.backward() send(grad[i], iter=i) stale_avg_grad = recv(iter=i-d) W = W - lr * (grad[i] -
grad[i-d] + stale_avg_grad)
for i in iters: L = loss(net, data, label) grad[i] = L.backward() if (I+d) % k == 0:
send(grad[i], iter=i) If I % k == 0
stale_avg_grad = recv(iter=i-d) W = W - lr * (grad[i] -
grad[i-d] + stale_avg_grad) K 统⼀⼤写
(2) Federated Averaging (K=2)
(4) DGA (D=2, K=2)
Latency is amortized by multiple steps, but still slow the training!
High latency longer blocks the training!Delay the averaging High latency longer blocks the training!
(a) Federated Averaging (K=1)
(c) Delayed Averaging (D=2, K=1)
(b) Federated Averaging (K=2)
(d) Delayed Averaging (D=2, K=2)
(b) Delayed Gradient Averaging: D indicates how many steps the averaging receiving timing are delayed.
Computation Communication Synchronization Barrier
Increased latency slows the training!
Latency is amortized by multiple steps, but still slow the training! No longer blocks the training!
(1) Vanilla Synchronous SGD
for i in iters: L = loss(net, data, label) grad[i] = L.backward() send(grad[i], iter=i) avg_grad = recv(iter=i) W = W - lr * avg_grad
for i in iters: L = loss(net, data, label) grad[i] = L.backward() send(grad[i], iter=i) stale_avg_grad = recv(iter=i-d) W = W - lr * (grad[i] -
grad[i-d] + stale_avg_grad)
for i in iters: L = loss(net, data, label) grad[i] = L.backward() if (I+d) % k == 0:
send(grad[i], iter=i) If I % k == 0
stale_avg_grad = recv(iter=i-d) W = W - lr * (grad[i] -
grad[i-d] + stale_avg_grad) K 统⼀⼤写
(2) Federated Averaging (K=2)
(4) DGA (D=2, K=2)
Latency is amortized by multiple steps, but still slow the training!
High latency longer blocks the training!Delay the averaging High latency longer blocks the training!
(a) Federated Averaging (K=1)
(c) Delayed Averaging (D=2, K=1)
(b) Federated Averaging (K=2)
(d) Delayed Averaging (D=2, K=2)
Rewrite the update rule using the accumulated gradients mi1 and m1 gives the compact form:
w i 2,D+1 = w i 2,D ⌘(gi2,D mi1 +m1| {z }
gradient correction
), (compact DGA update)
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 + r, with s 0 and r 2 [1,K]. The integer quotient s indicates the number of rounds skipped due to the latency. In this scenario, the gradients sent at t 1 s round is received in the middle of the t-th round, which justifies our update rule in Algorithm 1. The example we discussed earlier in (compact DGA update) is a special case when s = 0, i.e. D  K, where the gradients sent in the last round are received in the current round. We 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 (t D)-round gradients. In another word, different workers only differ on the most recent D gradients.
Last but not the least, in the ideal case when there is no delay, i.e. D = 0, our algorithm DGA recovers the original Federated Averaging [27]. When D 1, our algorithm DGA allows the clients to pipeline local updates with communication, and the divergence of Federated Average and DGA is bounded by a constant number. To 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

heading: 2.3 Theoretical Analysis
text: To start the convergence analysis, we assume that the objective function is L-smooth:
Assumption 1 (L-smoothness). Each function fi(x) is L-smooth, i.e. differentiable with L-Lipschitz gradient:
||rfi(x) rfi(y)||  L||x y||. 8x, y 2 Rd
Remind that each individual function is stochastic and we have access to an unbiased gradient gi such that E[gi(w)] = rfi(w) for any w and i. We further assume that gi 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:
E||gi(w)||2  G2, and E||gi(w) rfi(w)||2  2, 8w, 8i.
We now present two main ingredients to drive the analysis. The first one is that no matter delayed gradient averaging is performed or not, the average parameter across the clients always behaves as a local gradient descent:
Lemma 2.1. Let us denote wt,k = 1 N PN i=1 w i t,k, as the average parameters across all clients at
t-th round k-th iteration. Then we always have
wt,k+1 = wt,k ⌘
N
NX
i=1
g i t,k.
The effect of the delayed averaging step is to align the gradient of the previous round across all clients, without changing wt,k. 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 ⇥ kwit,k wt,kk2 ⇤  4⌘2(K +D)2G2 8t, k, i.
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 1 and 2. The sequence generated by DGA in Algorithm 1 with stepsize ⌘  1L satisfies
1
TK
TX
t=1
KX
k=1
E[krf(wt,k)k2]  2
⌘TK (E[f(w1)] f(wT )) + 4⌘2L2G2(K +D)2 +
L N ⌘ 2
Our proof closely follows the analysis of FedAvg in the non-convex setting [51] and we delay it to Appendix A.2. The upper bound on the right-hand-side is essentially the same as the convergence rate of FedAvg, where (K +D)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:
Corollary 2.3.1. When the function f is lower bounded with f(w1) f⇤  and the number rounds T is large enough such that T N/(K +D), then set the stepsize ⌘ = p N
L p T (K+D) yields
1
TK
TX
t=1
KX
k=1
E[krf(wt,k)k2 = O 2L + 2p NTK · r 1 + D K + N(K +D) T ! .
As long as D = O(K) and N(K+D)  T 1/3, the first term dominates and our algorithm shares the same convergence speed O(1/ p NTK) as the vanilla FedAvg. Meanwhile, as the communication is fully covered by computation, the total run time of DGA is TDGA = TK⌧g, which reduces the run time of FedAvg in (1) by a factor K+DK . In the high latency setting where delay can take multiple rounds, this run time improvement becomes significant.
6
DGA with momentum update To incorporate momentum update [31, 33] in DGA, we combine the past gradients in an exponential weighted average:
u i t,k = u i t,k 1 + g i t,k,
where is the momentum parameter, usually set as 0.9. Then we use it to perform the local update:
w i t,k+1 =
( w
i t,k ⌘uit,k if k 6⌘ D (mod K) or t 1 s < 1;
w i t,k ⌘(uit,k 1 D 1 (v i t 1 s vt 1 s)]) if k ⌘ D (mod K) and t 1 s 1.
where vit = PK k=1 u i t,k. The delayed gradient averaging step is calibrated carefully by a factor (1 D)/(1 ), due to the exponentially weighted averages. The derivation details are attached in Appendix. We remark that when = 0, we recover this to the vanilla update of DGA in Algorithm 1. For other other optimizers (e.g., Adam, RMSProp), such modification can be made similarly. We leave it of as 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 parameter server is 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. In 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 it substantially different from the traditional averaging step. In FedAvg, the averaging step synchronizes the weights on 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 wi2,D+1 does not match w j 2,D+1 even after averaging, for distinct clients i 6= 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]:
wt+1 = wt ⌘ [rfi(wt) rfi(w̃) +rf(w̃)] , (SVRG update)
where w̃ is a snapshot reference point and rf(w̃) 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 in our algorithm is not a full gradient by any means, because of the staleness introduced by the extra local updates. Moreover, SVRG uses a fixed reference point w̃ inside the same round while as the vector mt in our algorithm is an accumulation of gradient of the entire round, see (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 is given by wk+1 = wk ⌘g(k d). In this case, the gradient updates are delayed but there is no correction
7
term as DGA. Though these studies show sub-linear convergence in theory, such a simple method accumulates the staleness over iterations and hurts model performance especially when the delay steps is large as shown in Table. 1. 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 a correction term to handle delayed gradients and compensate the staleness. We next conduct experiments showing that DGA speeds up FedAvg without losing accuracy.

heading: 3 Experiment

heading: 3.1 Accuracy Evaluation
text: We evaluate the effectiveness of DGA on diverse tasks: Image classification on CIFAR-10 [19] and ImageNet [20], next word prediction on Shakespheare [41]. We implement DGA in PyTorch framework [30] and choose Horovod [40] as the distributed training backend. The task-specific details are described below.
On CIFAR-10 [19], we train a MobilenetV2-0.25 [37] using 64 workers and each equips with single V100 GPU. The training epochs is 200 and the batch size 64 per worker. The learning rate ⌘ is initially set to NUM_GPUs ⇥ 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], we 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 in the training. The learning rate adopts the same scaling strategy as CIFAR’s.
On Shakespeare, we adopt the 2-layer LSTM language model architecture with 1500 hidden units per layer [32] and follow the preprocessing in Leaf [4]. We set the learning rate to 20 and clip gradients with a norm larger than 0.25 to avoid gradient explosion. The model is trained with 40 epochs while the first epoch is used for warm-up.
For non-i.i.d. experiments, we follow the partition used in [4, 22] 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 a 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.5⇥ to 4.07⇥ 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 a 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.1.

heading: 3.2 Speedup Comparison
text: Throughout the derivation of DGA, we 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 to simulate different network conditions, we evaluate the effectiveness of DGA in two different ways. We first experiment on a set of synthetic latency controlled by Netem [29], which allows us to control the communication delays precisely. Then we build up a Raspberry Pi cluster 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.
In the Figure. 4a, we manually simulate the network latency from 1ms to 5000ms via Netem [29], and plot the normalized run time. The run time is normalized by FedAvg (K = 5) with latency 1ms, 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 is 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 real-world settings on the Raspberry Pi cluster in the Figure. 4a.. Instead of simulating different latency settings, we consider four representative cases for federated learning [i] wired [ii] (wireless)
different rooms [iii] (wireless) different floors [iv] (wireless) different buildings, where the latency numbers are 1ms, 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 performance degrades more quickly. Even under such challenging network, the throughput of DGA remains steady.
Figure. 5 shows the speedup ratio (scalability) on the Pi cluster. We adopt small models LeNet and 2-layer lstm 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.
9
Th ro ug hp ut
D eg ra da tio n
(a) GPU servers with Netem [29] generated synthetic latency from 1ms to 5000ms.
Th
ro ug
hp ut
D eg
ra da
tio n
(b) Raspberry Pi cluster (16 nodes) with real-world latency (1ms, 16ms, 132ms, 470ms).
Latency:430ms
SSGD (3 µs) SSGD (100ms) FedAvg (K=5) FedAvg (K=5) FedAvg(K=10) FedAvg(K=10) DGA (K=5, D=20) DGA (K=5, D=20) Oracle
1 1 1.00520833333333 3.57053593744421 1.0 3.57053593744421 1.0 3.57053593744421 1 1
2 1.546875 0.341145833333333 5.70287995437696 0.61 6.14062020264047 0.91 6.14062020264047 1.71980350015352
2
4 2.895833333333330.729166666666667 11.3733295422235 1.51 10.7613666935701 1.87 13.0975769482646 3.66823837590047
4
8 5.268229166666671.39583333333333 21.4304848647201 2.619 21.4304848647201 3.79 25.3405131453912 7.09711751662971
8
16 4.16801 6.06318 11.295
16
MBv2 - 1.0 SSGD SSGD (100ms) DGA DGA(100ms) 1 node 1 0.9978813559322030.9830508474576270.976694915254237 2 nodes 1.870762711864410.3241525423728811.847457627118641.83686440677966 4 nodes 3.69703389830508.6504237288135593.62711864406783.61016949152542 8 nodes 7.012711864406781.230932203389837.112288135593227.09533898305085
VGG19 - Speedup SSGD SSGD (100ms) DGA DGA(100ms) 1 node 1 1.00704225352113 1 0.992957746478873 2 nodes 1.239436619718310.538732394366197.23239436619718.22535211267606 4 nodes 2.359154929577461.007042253521132.464788732394372.42253521126761 8 nodes 4.577464788732391.964788732394374.514084507042254.54929577464789
Sp ee
du p
0.0
4.0
8.0
12.0
16.0
1 2 4 8 16
FedAvg (K=5) FedAvg (K=10) DGA (K=5, D=20)
ResNet-50 SpeedUp
SSGD (3 µs) SSGD (100ms) DGA DGA(100ms) FedAvg FedAvg(100ms) Oracle
1 node 384 386 413 411 399 386 384
2 nodes 594 131 639 646 575 200 768
4 nodes 1112 280 1242 1247 1156 512 1536
8 nodes 2023 536 2267 2251 2077 917 3072
MBv2 - 1.0 Img/s
SSGD SSGD (100ms) DGA DGA(100ms) 1 node 472 471 464 461 2 nodes 883 153 872 867 4 nodes 1745 307 1712 1704 8 nodes 3310 581 3357 3349
VGG19 - Speedup-1
SSGD SSGD (100ms) DGA DGA(100ms) 1 node 426 429 426 423 2 nodes 528 229.5 525 522 4 nodes 1005 429 1050 1032 8 nodes 1950 837 1923 1938
Latency:5ms
SSGD (3 µs) SSGD (100ms) FedAvg (K=5) FedAvg (K=5) FedAvg(K=10) FedAvg(K=10) DGA (K=5, D=20) DGA (K=5, D=20) Oracle
1 1 1.00520833333333 1.0 1.0 1.076 1
2 1.546875 0.341145833333333 0.70 1.01
1.913 2
4 2.895833333333330.729166666666667 1.436 2.233
3.884 4
8 5.268229166666671.39583333333333 2.97 4.227
7.512 8
16 5.4210 7.7716
13.5111 16
MobilenetV2-0.25
Latency:430ms-1
SSGD (3 µs) SSGD (100ms) FedAvg (K=5) FedAvg (K=5) FedAvg(K=10) FedAvg(K=10) DGA (K=5, D=20) DGA (K=5, D=20) Oracle
1 1 1.00520833333333 3.57053593744421 1.0 3.57053593744421 1.0 3.57053593744421 1 1
2 1.546875 0.341145833333333 6.2363579669473 0.43 6.14062020264047 0.84 6.14062020264047 1.71980350015352
2
4 2.895833333333330.729166666666667 11.3733295422235 1.012 10.7613666935701 1.68 13.0975769482646 3.66823837590047
4
8 5.268229166666671.39583333333333 21.4304848647201 2.113 21.4304848647201 3.31 25.3405131453912 7.09711751662971
8
16 nodes 4.2263 6.77 13.12
16
When scaling the training to 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 high-latency network. When scaling to eight devices, the speedup ratio is about 13.1. This performance is close to what conventional algorithms achieved inside a data center.

heading: 4 Conclusion
text: 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 no slower than FedAvg in non-convex settings. We further demonstrate that our algorithm is capable of enjoying high scalability under poor network conditions and preserving accuracy especially on non-i.i.id 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 a wide range of federated learning applications in high latency network.

heading: 5 Acknowledgement
text: We thank MIT-IBM Watson AI Lab, Samsung, Woodside Energy, and NSF CAREER Award #1 4 349 for supporting this research. Hongzhou Lin acknowledges that the work is done prior to joining Amazon. Yao Lu acknowledges that the work is done prior to joining Google.
10

Review summaries:
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.  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.

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.

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.

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.