Fast Federated Learning in the Presence of Arbitrary Device Unavailability
Authors: Xinran Gu
Kaixuan Huang
Jingzhao Zhang
Longbo Huang
Venue: NeurIPS 2021 Poster (2021)
Keywords: Federated Learning
Distributed Optimization

Abstract: Federated learning (FL) coordinates with numerous heterogeneous devices to collaboratively train a shared model while preserving user privacy. Despite its multiple advantages, FL faces new challenges. One challenge arises when devices drop out of the training process. In this case, the convergence of popular FL algorithms such as FedAvg is severely influenced by the straggling devices. To tackle this challenge, we study federated learning algorithms in the presence of arbitrary device unavailability and propose an algorithm named Memory-augmented Impatient Federated Averaging (MIFA). Our algorithm efficiently avoids excessive latency induced by inactive devices, and corrects the gradient bias using the memorized latest updates from them. We prove that MIFA achieves minimax optimal convergence rates on non-i.i.d. data for both strongly convex and non-convex smooth functions. We also provide an explicit characterization of the improvement over baseline algorithms through a case study, and validate the results by numerical experiments on real-world datasets.

Fast Federated Learning in the Presence of Arbitrary Device Unavailability
Xinran Gu"
Kaixuan Huang"
IMIS Tsinghua University
ECE Princeton University kai maixuud@prinneton.eed
gxr21 @mammmmllam..mmm tsinghua. edu
Jingzhao Zhang
Longbo Huang!
EECS
III Tsinghua University longbohuang@tsiigghe edu. cn
Massachusetts Institute of Technology jzhzhang@mit. edu
Abstract
Federated Learning (FL) coordinates with numerous heterogeneous devices collaboratively train shared model while preserving user privacy. Despite its multiple advantages, FL faces new challenges. One challenge arises when devices drop out of the training process beyond the control of the central server. this case, the convergence of popular FL algorithms such FedAvg is severely influenced by the straggling devices. To tackle this challenge, we study federated learning algorithms under arbitrary device unavailability and propose algorithm named Memory-augmente efficiently avoids excessive latency induced by inactive devices, and corrects the gradient bias using the memorized latest updates from the devices. We prove that MIFA achieves minimax optimal convergence rates non-iiid. data for both strongly convex and non-convex smooth functions. We also provide an explicit characterization of the improvement baseline algorithms through a case study, and validate the results by numerical experiments on real-world datasets.
Impatient Federated Averaging (MIFA). Our algorithm
Introduction
Federated learning is machine learning setting in which a central server coordinates with a large number of devices to collectively train shared model [28 34
26] Practical advantages of this training scheme are mainly twofold. First, each device keeps the private data locally and hence preserves its data privacy. Second, federated learning make of idle computing resources and lower computation costs. Although federated learning successfully scales up with data sizes and accelerates training via more affordable computing power [43 38 36), the collaborative setup leads to new challenges due to large variations among individual computing devices. Our work aims to formulate and investigate the impact of device variations FL from optimization perspective.
20
33
25
In FL, a device can differ from its peers multiple aspects [7 25). First, the data distribution and local task can be different among devices. To address the data variation, non-i.i.d. objective models were proposed and analyzed by [26 [8 [9 42 25). We follow this line work and formulate our optimization objective sum of stochastic functions individual devices (See Eqn. (T).
Equal contribution. Corresponding author.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

A second variation among devices is caused by different computing and communication speeds. One natural way to formulate the variation computation speeds is allow asynchronous updates and model the updates as delayed responses. Lots of novel research has studied the problem with different However, the delayed setup assumes that all devices make roughly the same number of (delayed) responses in the end. This behavior may deviate largely from the FL practice, where each device, e.g., personal cell phones, can have very different active duration when participating in the FL training, and hence make different numbers of responses. For this reason, our work aims to address this third discrepancy among devices caused by individual availability patters..
delay models, e.g., [35 4 27
45 1 [3]
The third device heterogeneity caused by different availability patterns is less studied in optimization for federated learning problems. In this model, instead of making delayed response, devices can abort the training halfway, e-g., due to battery level, incoming calls, etc, and fail to return their responses upon the central server's requests [28] 7 [7 To handle missing responses, researchers propose algorithms where the central server may collect responses from only a fraction of the devices
and make updates [18 28 42
25 26
30 [4].
Previous works on collecting responses from a fraction of devices can be divided into two categories. When the response distribution is known, one could collect only the fastest responses and re-weight according to their response probability [7 26 30 This model can be restrictive, as in practice, the exact distribution may not be available and may evolve. Another line of work assumes that the server can arbitrarily decide and sample a set of devices to collect responses accordingly in every communication round [18 28 42 25 14]. This model does not require knowing the response possibility. However, the response time can be very long the selected subset contains unavailable devices.
In this work, we address the above limitations by studying federated learning in the presence of arbitrary device unavailability. Within this practical setup, we propose an algorithm that automatically accommodates for the underlying unavailability and allows patterns of the device unavailability be non-stationary and even adversarial. Furthermore, our algorithm can achieve optimal convergence rates the presence of device inactivity and automatically reduce to best-known rates if all devices are active. Our contributions are summarized as follows.
We investigate the federated learning problem with a practical formulation of device partici- pation, which does not require each device to be online according an (either known or unknown) distribution.
We propose the Memory-augmented Impatient Federated Averaging (MIFA) algorithm that agnostic to the availability pattern. It efficiently avoids excessive latency induced by inactive devices, successfully exploits the information about the descent direction stale and noisy gradients, and corrects the gradient bias using the memorized latest updates.
We prove that MIFA achieves minimax optimal convergence rates O
(rrt1) for smooth, (KT))
strongly convex functions, and O (v 7-1 for smooth, non-convex functions, and es- NKT
tablish matching lower bounds. Here, N, and T' stand for the number of devices, local updates and communication rounds respectively. Fr and characterize how actively devices participate in training (see formal definitions in Sections 3 5 and 6b. MIFA also achieves optimal convergence rates in the ideal case when all devices are active.
We provide explicit characterization of the improvement over baseline algorithms through a case study and empirically verify our results on real-world datasets.
2
Related work
Federated learning. Federated Averaging (FedAvg) was first proposed in 28]] 26
19 18
provided convergence analysis for FedAvg on non-i.idd data and quantified how data heterogeneity degrades the convergence rate. Several variants of FedAvg were designed to deal with data hetero- geneity. FedProx (25) adds a proximal term to local objective functions, while FSVRG 21 and SCAFFOLD [18 employ variance reduction techniques.
One line of work focused on variations in computation capabilities among devices (3 These models assume that responses are delayed but not missing. To address the missing response some

---

work assumes that the server can actively sample a subset of devices to respond [88 28
42
25 14
or that the pattern of device availability is known 226 TO 30]. These results do not generalize to adversarial inactive patterns. [32] discussed the impact of device inactivity on convergence but their proposed algorithm diverges there exists an inactive device each round of communication. However, our setup allows adversarial patterns under certain non-distributional assumptions (see Section 5) while our proposed algorithm still achieves convergence.
Asynchronous distributed optimization. Our work is related to literature in the field of traditional asynchronous distributed optimization in that our proposed algorithm uses stale gradients. The problem setup for asynchronous distributed algorithms can be divided into two categories [33]. One is the shared-data (i.i..) setting, where all workers can access the whole dataset. In this setting, the local gradient is an unbiased estimator of the global gradient [35] 27 45 D. In contrast, we assume each worker has non-i.i.d. data, and hence the local stochastic gradient can not be viewed as an unbiased estimator of the global gradient.
The other less studied setting in distributed optimization is the distributed setting (non-i.id.), where data are partitioned among workers. Specifically. [5] proposed an asynchronous incremental aggregated gradient algorithm that uses buffered gradients to update the global model. Unlike our setup, this algorithm evaluates full local gradients, performs only one local step, and was analyzed under the bounded delay assumption. [3] models the delay as stochastic and assumes that the server has knowledge the distribution, but our formulation distribution- perform multiple local steps and communicate with the server at different times, but the authors assume that all workers are available and compute at the same rate.
[6] allows workers to
Comparison with an independent work. While preparing the manuscript, we were unaware of an independent work [4] that investigated the same setup and proposed a similar algorithm called FedLaAvg. Their main theorem established the convergence rate of O NO3T
Mmax
(G + o²)) for
smooth and non-convex problems, where G2 is the uniform upper bound for the squared norm of stochastic gradients and Vmar is the maximum number of inactive rounds. In comparison, prove
the minimax optimal rate of O(V P o2 without the bounded gradient assumption, also improving Vmax to V. Furthermore, our result achieves a linear speedup in N and K.
Apart from non-convex functions, we also derive the minimax optimal rates for strongly convex smooth functions under the mild assumption that allows for arbitrary and unbounded number of inactive rounds. Both of our results achieve linear speedups in terms of N and K, and automatically recover the best-known rates of FedAvg when all devices are active. We also show that our proposed algorithm achieves acceleration over unbiased baseline algorithms in the presence of stragglers.
Problem Setup
We consider optimizing the following problem Federated Learning setting:
min [(w) : + MA fiww) 1/2 ΣE Rg, (i,, WEBd
(1)
where w is the optimization variable, e.g., parameters of machine learning model, N is the number of participating devices, fa is the local loss function on device i, and & describes the randomness in local data distribution.
In the idcal federated learning setup (see Figure (a)), all devices return responses within similar time, and hence the central server collects all the local updates. In this case, the computation cost is usually measured by the number of local stochastic oracle evaluations, which is proportional to the number of rounds. In delayed FL setup (see Figure (b)), devices are always active upon the central server's ss request but may return responses with a delay. Here, all devices return almost the same number of responses in the long term.
(
As we discussed, the above setups do not depict a real-world scenario in which a device can have a longer inactive duration than active duration. In such cases, the communication interval is much longer than the local computation time required for each update, and each device generates an unequal number of responses 228 [7]. This motivates our setup in Figure (c).
3

---

Round
IRunnd Pi
Round
Round
1Round 1W
Server
Server
Whe2
Server
Device
Device
Device
Desice
Device N
Device N
(a) Ideal setup
(b) Delayed setup
(c) Our setup
Broadcast from
Attempted broadcast
Unavaiability
computation outiide continnication interval
Upload from device
Model aggregation
Local comoutation
communication interval
An illustration of setup. (a) Ideal setup: all devices return their responses within similar time. (b) Delayed setup: devices are available, but may return responses with a delay. (c) Our setup: devices can be unavailable arbitrarily, and the communication interval is long enough for active devices return responses.
Figure 1:
In proposed setup, use to index the global communication rounds. We say a device participates or is active at round if can complete the computation task and send back the update at the end of round t. We define A(t) as the set of all active devices at round t. Notice that we make no assumptions on the distribution of the participation patterns of devices and allow them to be arbitrary.
Directly applying FedAvg to the proposed setup can be problematic due to the existence of inactive devices. To accommodate for inactive devices, we discuss three natural variants of FedAvg and their limitations. The detailed algorithms can be found in Appendix A
Biased FedAvg. At each communication round, the global model is updated with direct average of local updates from the active devices. This naive approach induces bias when data distribution and response patterns vary among devices.
FedAvg with device sampling. The server selects subset of S devices randomly without replacement, and then waits until all devices the subset respond. This is how original FedAvg (28) addresses device unavailability. Note that over 7 communication rounds, the global model updated less than T times due to waiting. This approach prone to stragglers and we refer the readers to Section 5. for a detailed discussion.
The local updates from the active devices are weighted by the reciprocal of the participation probabilities to avoid bias. This approach is only applicable when the response each device i.i.d. over rounds and requires the knowledge of participation probabilities.
FedAvg with importance sampling 26 13
4 Memory-augmente Impatient Federated Averaging (MIFA)
In this section. we introduce our algorithm - Memory-augmentel Impatient Federated Averaging (MIFA). MIFA maintains an update-arras {G') in the memory that stores the latest updates for all devices. As the name suggests, MIFA has two components. First, the algorithm is impatient and avoids waiting for any specific device when facing heterogeneous devices with arbitrary availability. Second, the algorithm augments the received updates of the active devices with the stored updates of the inactive devices to perform averaging.
Specifically, at the beginning of round f, the server broadcasts the latest model parameter w, to all active devices A()). After receiving wx. each active device, say, the i-th device, sets wf, wy and performs K steps of SGD with respect to the local objective function to get wi.k:
w wi,+1
- -- V ((((.))))) = 1,
where 7) the learning rate and ( is the stochastic gradient evaluated on device i. Next, the server stores the received update f, then we have
1 (w, w(xx) in G Denote by {Gi} the update-array after round n
G Gi-1:
if é A(L), if E A(t).
G
1 [w: w/,k),

---

At the end of round t, the server updates the global model with the average of {G₂} (line 9), In other words, our algorithm MIFA updates the model with the latest available accumulated gradients for all devices.
Algorithm 1 Memory-augmentee Impatient Federated Averaging (MIFA)
1: Input: initial w1, learning rate (nt
2: Server executes:
1: DeviceUpdateli, Wi, 71))
3: initialize G + 0,i [N]
2: w f- Wyr
4: for t 1..
do
3: for local step 0,... K do
5: broadcast Wi to all active devices i E A(t)
4: compute stochastic gradient V ((((w
6: for each active device do
5: w Wi,k+11 + w T/ V fi(((,))
7: G¹ t DeviceUpdater W/, 17))
6: end for
8: end for
7: Return 1 1 w to the server
9: W++11 + N DM G
T/t
end for
MIFA efficiently progresses without waiting for inactive devices and re-uses their latest updates as the surrogate for missing responses. Being impatient accelerates convergence, whereas memory augmentation corrects the update bias. Our algorithm differs from asynchronous algorithms in traditional distributed optimization [35] 4 27 [1] 45 | [3] 6 in that utilize the noisy updates of inactive devices more than once to avoid biasing against stragglers. In the following part of the paper, we show that MIFA successfully exploits information about the descent direction contained in the stale and noisy gradients.
Discussion on implementation. In practice, to implement MIFA, the server needs to maintain huge array to store the latest update for each device, which scales with the model size and the total number of devices. To avoid exhausting the server's memory, one strategy is to distribute the memory consumption among devices. Specifically, each device, say the i-th, stores its previous update G
computed round in its local memory. When it becomes active and computes G the device sends G; G to the server, which the difference between the current update and the previous one. In this case, server only needs to maintain the average G the memory and updates by G. G.-1 + EiEAt) G at round I. Then the server updates the global model by Wr+1 = wi - - Gr.
Convergence Analysis for strongly convex objective functions
In this section, present the convergence results for MIFA on je-strongly convex L-smooth functions. Typical examples for the strongly convex case are & regularized logistic regression and linear regression problems.
In order to capture how the unavailability of devices affects algorithm performance, we introduce the following notion to quantify the dynamics of devices in our setting.
Definition 5.1 (Number of inactive rounds). We define the number of inactive rounds of device at round as (t,, =t max t' S t, E A(t))) which is the difference between current round and the latest round when device i is active.
can be seen that Tt, i) = 0 if device is active at round and r(t,4) = =(t - 1, + otherwise. Also, f (t.. i) is the latest round when the device i is active. Next, we present the assumptions made for establishing our convergence theorem.
1,,1
Assumption 1. f1, .N are all I-smooth, i.e., for all and v. fi(e) S Se(w) (Vf((w), w) 1 | =1l
2
Assumption 2. (se(w) is unbiased estimator of V. with variance bounded by o², iee Eg [()) = (w)) E (i((w)
Assumption 3. fi,... ... fN are all y-strongly convex: for all w and v, f(()) 2 f((w) +
(Vf((w) w) #/ || 2
5

---

Assumption 4. There exists constant to > O, such that for all t 2 and i E [M]. the number of inactive rounds of device at communication round satisfies T(t, S to + st. where b
40 (L/p)
Assumptions
2 and 3 are standard and common in the FL literature, e.g., 26
18
19
42
36). In
Assumption we relax the bounded gradient assumption that is often required in prior work, e.g., 26 40 Lastly, Assumption 4 is very mild assumption
device availability, since it allows the number of inactive rounds to grow as (t).. J. In contrast, existing results on asynchronous updates
mostly assume bounded or fixed latency, e.g., 66 5 40
B5 4.
We are now ready to present our first convergence result. Define = * (w.)l to measure data dissimilarity, where w, = arg min f(w) is the global optimum. Also, define Fy and T be the average and maximum numbers of inactive rounds T(t, i) across all devices and rounds, respectively. That is,
T-I N
TT N(T Σ
Σ 11
Tmax,T = max max =(t, e). T(,
iE ISTST-1
The following theorem summarizes the performance of MIFA in this case. Theorem 5.1. Assume that Assumptions 7 to hold. Further assume that the device availability
sequence T(1,)) i) satisfies Assumption 4 and T (1 = 0 for all i E [N]. By setting the learning
rate 1h = pk(eta] with a = max (100, 40% (L. after T communication rounds, MIFA
(100,
satisfies:
TT + 1
T A
A1 + (K (K-11 -2) As
TE [/(TTT)] - f(w.) 0
0²
HNKT
122
where Wr is a weighted average of w, defined
1 Σ 1)(4 - WT Σ (1 + 1)(1+ a 2),
WT
and A, = L(D Lo /p). A2 = - As = = 12L3 ||00 - w.ll
Our results hold under Assumption 4 which allows for arbitrary device availability sequences with T =O(T). However, for MIFA converge, we require Tmax,7 oTT) and tu o(T). When
t()). the first term dominates and the impact the second O(1/T²) term negligible. In fact the first term in Theorem 5.T minimax optimal by our information-theoreti lower bound for the problem in the next proposition.
21 (N 7+1
Proposition 5.1. Let co > be a universal constant. For any potentially randomized algorithm. there exists stochastic strongly convex problem satisfying Assumptions to such that the output
wr after rounds of communication has expected sub-optimality lower bounded by
OTO²
Elf(wT) f(w")(( Co
KT
The proof is based on the observation that the number of gradient evaluation can scale inversely with ir and that the oracle complexity is tight for centralized stochastic optimization problems. The optimality of the first term Theorem 5.1 is independent of the distributed or the FL setup.
The second term in Theorem 5.1 converges at the rate (1/TT²) and consists of three parts, where the first part reflects the slowdown caused by device unavailability through Tmax, T, the second part shows the effect of multiple (K > 1) local steps, and the third part tells how the initial error decreases.
Remark 5.1. When T(t, vice participation. and we have 7r = O and Tmax,T = O. In this case, Theorem 5.7 yields bound O [KKNT" [ Llo2/K+D+L (ww)))))))) matching the rate O o² log 1272
for all i and t, our setup reduces to FedAvg with full de-
NKNT [[o2/K+DD]] TY? 12T2
||w w.ll expl 48L T) in (88 (Thm. V. B² 2.1g = 1) up to logarithmic terms. Besides, in the general case, our 2 A term matches the last term in (6] (Cor. 5).

---

Remark 5.2. Our analysis relies on the technical assumption that all devices respond in the first round. Intuitively, this is because we need least one valid stochastic gradient evaluation for each device to get a complete picture of the global objective, or otherwise any update would be biased. In practice, this can be achieved by waiting for the updates from all devices on w at the very beginning.
5.1 Case Study: ii.d. Bernoulli participation
Though algorithm can be applied to non-stationary and non- -on-independent response patterns, show in this subsection that even in the simple i.i.d. Bernoulli participation scenario our algorithm achieve considerable improvement compared known algorithms. In particular, a setup where each device becomes active independently with a fixed probability p;- It serves as the first motivating example towards modeling the participation patterns of devices, and provides clean view of how the heterogeneity of the device participation influences the Federated optimization algorithms.
consider
We will show that in this scenario, Assumption holds with high probability, and the terms involving the inactive rounds r(t, i) in Theorem [.. also be bounded. Furthermore, we theoretically demonstrate that algorithms such as FedAvg 28 and SCAFFOLD [88, which sample S devices for each global update, more prone stragglers than algorithm.
Definition 5.2. Assume that for all E [N], the i-th device is assigned with probability pt. We say the participation of the devices follows i.i.d Bernoulli participation model with participation probabilities {p;}. if (1). at the first round, all devices are active, and (2). round > device i is active with probability ps. which is independent of the history and other devices.
Next theorem shows that under i.i.d. Bernoulli participation scenario, with high probability, 7(t, only grows logarithmically in t. Also Assumption 3 holds for a mild choice of to-
Theorem 5.2. For i..d. Bernoulli participation model defined in Definition 5.2 given any d > O, with probability least 6, we have the following holds for all t and E [N] simultaneously.
T(t, (1,,)s50 0 (log(Nt/0) + +1))
Furthermore, (1). Assumption holds true lo = 22 Pman b = (0(LLL))2-::12 Tmax,7 can be upper bounded as
(0((11 log Penand where Pmii = (p:), and
maxx T SO s0(( 5 (log(TN/8)++) +118))+))
Pmii
The next theorem provides high probability upper bound for Fr-
Theorem 5.3. For i.i.d. Bernoulli participation model defined in Definition 5.2
given any 5 >> 0 and
1, with probability at least we have
N
0 + log ))
By Theorem 5.2 and Theorem 5.3 we conclude that the dominant term our convergence bound is Therefore, achieve accuracy, the dominant term the number of the
δ Σ> N required rounds is
(MMIPA) Ō
PNKe)
Pt
For both FedAvg and SCAFFOLD that sample S devices uniformly at random, 18 (Thm I. & III.) showed that the dominant term of the number of global updates needed to achieve accuracy is R. μSKE) Notice that in our setting, to accomplish each global update, the server needs to wait for a few rounds for the devices to respond. T(S) be the expected rounds for which the server needs to wait for the selected devices S to be active. Then the expected total rounds to achieve

---

accuracy is R. Es [T))]. For ii.d. Bernoulli participation model, we have T(S) 2 min(pi)ieS)) and we can further show that Eg (T(S)]
S N
(see Appendix D.3 for details). Therefore,
Pmin
a²
Puii
USKE
Pmin
JN Ke
By comparing Eqn. 2 and Eqn. 3 we see that both FedAvg and SCAFFOLD are more vulnerable stragglers, that is, the devices with very small participation probabilities; on the contrary, the convergence rate MIFA only depends on the average p/p; instead of //Pmin- We also provide empirical experiments showing that MIFA converges faster than FedAvg in Section
6 Convergence result for non-convex objective functions
In this section, we present the convergence guarantee of MIFA for the non-convex case. First we list the additional assumptions as below.
Assumption 5 (Hessian Lipschitz). J are all p-Hessian Lipschitz: for all and [V - [(b) S p || 10---j) w/[.
Assumption 6 (Bounded noise). The noise of the local stochastic gradients is upper bounded by V(((w) Assumption 7 (Bounded gradient dissimilarity). There exist and E [M]: f( S a [lIVf(w)]l + B,. Furthermore, we define N Σ Br. Assumption 8. There exists a constant v; such that r(t, 1) S Vo for all E [ and t 2 1. Furthermore, define ú b= Ei Vs and Maxx maxie[N] Vi.
constant å almost surely:
(i() ([([w)-(((())) S 8 a.s., Vi [N].
and B3 0 Ouch that for all
The analysis of non-convex functions is much more technically involved, and our results rely on strong assumptions that provide finer control of the gradient difference (Assumption (5). gradient noise (Assumption 6). gradient dissimilarity among devices (Assumption) 7), and device unavailability (Assumption S) We remark that Aasumptionn]ia is also made [6] and Assumption iis also made in [18 39]. We leave it future work to study whether and how MIFA converges for non-convex functions with weaker assumptions.
Theorem 6.1. Assume that Assumptions
and to 7 hold. Further assume that the device availability sequence T(,,i) i) satisfies Assumption and T1, = 0 for all [N]. By using learning rate n KTLL+oy- for max LNLL 16LNK, 8K Noa mon (12 (12 +p6) }. after T communication rounds, MIFA satisfies:
[[V](W)))]] = (V
A4 + As
min Be IStST
TKN (f(w)) - +z)
T
where 8 is the optimal value, and:
d²vmaax
(L² + o Vmax
2
A4 LNKL
a0²D +
aVma VB
VKN
Aş (K 1)NT(3 -
D D+1
Next, we show that the leading O(1/VT) term theoretically optimal for zero-respecting algorithms. Proposition 6.1. Let > 0 be universal constant. For any randomized zero-respecting algorithm, there exists a stochastic non-convex problem satisfying Assumption[ Z such that the output wT after T rounds of communication has expected sub- sub-optimality lower bounded by
(L ff)
E ( [(]]V("WT]]I== 2 eav
NKT
fo) 0² (f(wp) f*), the result in Theorem 6. tight. However, note that the counter example we used requires the quantity 8 in Assumption 6 to scale with T, hence requiring å to be large enough. This does not change the optimality of the first term as the first term is independent of J. Whether this requirement can be relaxed is left as open problem.
The above proposition show that when o. /
8

---

Remark 6.1. When all = 0 (i.e. all the devices are active), our convergence bound reduces L TKN (f(w)) f + 02) )+ + [K-1)NL[B+0 /k)) ) This matches the result in 42 (Thm. 1,
to 0 OV
T
" = 11 KTT.
N
7 Numerical Experiments
In this section, we conduct numerical experiments] verify our theoretical results and investigate how the heterogeneity of the device availability influences the Federated optimization algorithms. We compare the performance of the following four algorithms: FedAvg with importance sampling (FedAvg-IS), Biased FedAvg, FedAvg with device sampling. and our proposed MIFA. For the detailed discussions of the algorithms, we refer the readers to Sections 3 and We remark that for fair comparison, we deliberately include the first few rounds that MIFA needs to wait to receive responses from all devices for initializing the update-array {G*).
Following 126 25 we construct non-i.i.d. datasets from two commonly used computer vision
datasets MNIST 23 and CIFAR-I0 [22] Specifically, we divide the data into N = 100 devices with each device holding samples of only two classes, which creates a high level of data heterogeneity. For simplicity, we ensure that each device holds the same number of samples. We do not use any data augmentation. We use multinomial logistic regression as the convex model and LcNet-5 [24] with ReLU activations as the non-convex model. For all experiments, we use weight decay in the training process, which corresponds to adding & penalty. We use logistic models for MNIST dataset, while we use LeNet-5 for CIFAR-10. Our code is adapted from 266. which under MIT License.
We model the availability of the devices as independent Bernoulli random trials. The i-th device assigned with probability pt, where at each time step, the device becomes active with proba- bility pt. In our experiments, the pt's are chosen such that devices holding data of smaller labels participate less frequently. Specifically, if the i-th device holds the data of label j and k, we set Pmin min (j. k)/9 + (1 Pmim), where Pmin controls the lower bound of the participation prob- abilities. The correlation between the participation patterns and local datasets increases the difficulty of the problem [17]. To investigate this phenomenon, we repeat the experiments for Pmin = 0.1 and 0.2. We control the randomness of device participation when testing different algorithms.
In all the experiments, we set the initial learning rate to be YJo = 0.1 and decay the learning rate as We set the weight decay to be 0.001. The local batch size is 100 and each local update consists of epochs. Therefore, the actual number of local steps K depends on the size of the dataset. We all the experiments with 4 GPUs of type GeForce RTX 2080 Ti. We repeat the experiments for 5 different random seeds, and all of the experiments exhibit similar training curves. We report the averaged training loss and test accuracy with error bars in Figure
N 1/u
We observe that FedAvg with device sampling (FedAvg (S = 50) and FedAvg (S = 100) in Figure 2) severely influenced by the straggling devices and makes progress relatively slowly compared the other algorithms. Although biased FedAvg converges fast at the beginning, this simple algorithm is biased, and the optimality gaps are prominent for the harder CIFAR-10 dataset and when Pmin is small. On the contrary, our proposed MIFA avoids waiting for stragglers, converges fast without bias, and is competitive with FedAvg with importance sampling, which requires knowledge of the participation probabilities. We refer the readers to Appendix G for additional experiments on CIFAR-10.
8 Conclusions and Discussions
In this paper, we study FL algorithms in the presence of arbitrary device unavailability and propose MIFA, which avoids waiting for straggling devices and re-uses the memorized latest updates as the surrogate when the device unavailable. We theoretically analyze MIFA without any structural assumptions on the device availability and prove the convergence for strongly convex and non-conver smooth functions. Different from the literature that studies oracle complexity in terms of stochastic gradient evaluations, we argue that in federated learning system, the bottleneck lies in the non- stationary and possibly adversarial pattern of device participation. Therefore, is important to study how the number of inactive rounds influences the convergence rate. In Theorem 5.1 the dependency
Our code is available at htttttts://gittii http///ngxr11//MAAAA.com

---

Tedtng (on TedAng (Se50) Feldig
Fe
hosd Labbeg
boaed Hodkeg
28 unimantaaiionoooo Fozzd
Piiin 0.1
(h) Pmin 0.1
(c) Pmin 0.2
Pmain 0.2
mead
comtuntcatioo DozEd
(c) Praio 0.1
Priin = 0.1
g Punin 0.2
(h) Pmin = 0.2
Figure 2: Training losses and test accuracies. Fig. 2aa)
logistic models on non-iid MNIST. 50) and FedAvg (S 100) refer to FedAvg with device sampling that samples S devices for each global update. FedAvg-IS is short for FedAvg with importance sampling, which requires knowledge of the participation probabilities.
2(
Fig. 2(h) LeNet-5 non-iid CIFAR-10. FedAvg (S
upon T might be an artifact of our analysis, and a future direction is to study whether we remove this dependency. Another important direction is to analyze algorithms for non-convex functions under weaker assumptions.
Acknowledgments and Disclosure of Funding
The work of Xinran Gu and Longho Huang is supported in part by the Technology and Innovation Major Project the Ministry of Science and Technology of China under Grant 2020AA And2020AAA0108AM
Xinran Gu would like thank Kaifeng Lyu for the discussion on the convergence analysis. The authors would like to thank Sai Praneeth Karimireddy for the discussion on the problem settings.
References
[1] Alekh Agarwal and John C Duchi. Distributed delayed stochastic optimization. In 2012 IEEE 5 IEEE Conference on Decision and Control (CDC), pages 5451-5452. IEEE, 2012.
[2] Alekh Agarwal, Martin J Wainwright, Peter Bartlett, and Pradeep Ravikumar. Information- theoretic lower bounds the oracle complexity of convex optimization. Advances in Neural Information Processing Systems, 22:1-9, 2009.
[3] Yossi Arjevani, Yair Carmon, John C. Duchi, Dylan J. Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization, 2019.
[4] Yossi Arjevani, Ohad Shamir, and Nathan Srebro. A tight convergence analysis for stochastic gradient descent with delayed updates. In Algorithmic Learning Theory, pages 111-132. PMLR, 2020.
[5] Arda Aytekin, Hamid Reza Feyzmahdavian, and Mikael Johansson. Analysis and implemen- tation of an asynchronous optimization algorithm for the parameter server. arXiv preprint 12X1::6610005001 2016.
[6] Debraj Basu, Deepesh Data, Can Karakus, and Suhas Diggavi. Qsparse-local-sgd: Distributed sgd with quantization, sparsification, and local computations. arXiv preprint /90.v3/906.02367, 2019.
[7] Keith Bonawitz, Hubert Fichner, Wolfgang Grieskamp, Dzmitry Huba, Alex Ingerman, Vladimir Ivanov, Chloé Kiddon, Jakub Konečný, Stefano Mazzocchi, Brendan McMahan, Timon
10

---

Van Overveldt, David Petrou, Daniel Ramage, and Jason Roselander. Towards federated learning at scale: System design. In A. Talwalkar, V. Smith, and M. Zaharia, editors, Proceed- ings of Machine Learning and Systems, volume 1, pages 374-388, 2019.
[8] Sébastien Bubeck, Nicolo Desa-Bianchi, and Gábor Lugosi. Bandits with heavy tail. IEEE Transactions on Information Theory. 59(11):7111-7711, 2013.
[9] Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Accelerated methods for nonconvex optimization. SIAM Journal on Optimization, 28(2):155-11772 2018.
[10] Hubert Eichner, Tomer Koren, Brendan McMahan, Nathan Srebro, and Kunal Talwar. Semi- cyclic stochastic gradient descent. In International Conference Machine Learning, pages 1764-1773. PMI.R, 2019.
[11] Hamid Reza Feyzmahdavian, Arda Aytekin, and Mikael Johansson. An asynchronous mini- batch algorithm for regularized stochastic optimization. IEEE Transactions Automatic Control, 61(12):3700-375, 2016.
[12] Saeed Ghadimi and Guanghui Lan. Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization i: A generic algorithmic framework. SIAM Journal on Optimization, 22(4):1469-111 1492, 2012.
[13] Margalit Glasgow and Mary Wootters. Asynchronous distributed optimization with stochastic delays. arXiv preprint vrXiv:2009.10711 2020.
[14] Eduard Gorbunov, Konstantin P. Burlachenko. Zhize Li, and Peter Richtarik. Marina: Faster non-convex distributed learning with compression. Marina Meila and Tong Zhang, edi- tors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 3788-3798- PMLR, 18-24 Jul 2021.
[15] Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown. Measuring the effects of non-identical data distribution for federated visual classification. arXiv preprint arXiv:1909.00
2019.
[16] Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael I Jordan. How to escape saddle points efficiently. In International Conference on Machine Learning, pages 1724-1732. PMLR, 2017.
[17] 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.49977, 2019.
[18] Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference on Machine Learning. pages 5132-5143. PMLR, 2020.
[19] 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, pages 4519-45299 PMLR, 2020.
[20] Jakub Konečný, Brendan McMahan, and Daniel Ramage. Federated optimization: Distributed optimization beyond the datacenter. arXiv preprint arXiv:1511.03577 2015.
[21] Jakub Konečný, H Brendan McMahan, Daniel Ramage, and Peter Richtárik. Federated optimiza- tion: Distributed machine learning for on-device intelligence. arXiv preprint arXiv: 1610.02527, 2016.
[22] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[23] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 86(11))2278-233 1998.
[24] Yann LeCun al. Lenet-5, convolutional neural networks. com/exdb/lenet, 20,5):14, 2015.
URL:: http://yann. lecun.

---

[25] Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. In Dhillon, D. Papailiopoulos, and V. Sze, editors, Proceedings of Machine Learning and Systems, volume 2, pages 429 4500, 2020.
[26] 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, 2020.
[27] Xiangru Lian, Yijun Huang. Yuncheng Li, and Liu. Asynchronous parallel stochastic gradient for nonconvex optimization. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015.
[28] Brendan McMahan, Fider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication--ffiiiee. learning of deep networks from decentralized data. In Artificial Intelligence and Statistics, pages 1273-1282. PMLR, 2017.
[29] Arkadij Semenovič Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983.
[30] Constantin Philippenko and Aymeric Dieuleveut. Bidirectional compression in heterogeneous settings for distributed or federated learning with partial participation: tight convergence guarantees. arXiv preprint arXiv:2006. 14591, 2020.
[31] Amirhossein Reisizadeh, Isidoros Tziotis, Hamed Hassani, Aryan Mokhtari, and Ramtin Pedarsani. Straggler-resilien federated learning: Leveraging the interplay between statistical accuracy and system heterogeneity. arXiv preprint 2rXiv:2012.14453, 2020.
[32] Yichen Ruan, Xiaoxi Zhang. Shu- Shu-Che Liang, and Carlee Joe- Wong. Towards flexible device participation in federated learning. In International Conference on Artificial Intelligence and Statistics, pages 3403-3411. PMLR, 2021.
[33] Felix Sattler, Simon Wiedemann, Klaus-Robert Müller, and Wojciech Samek. Robust and communication-efficci federated learning from non-iid data. IEEE transactions on neural networks and learning systems, (1(9)3440-34433 2019.
2019.
[34] Virginia Smith, Chao-Kai Chiang, Maziar Sanjabi, and Ameet Talwalkar. Federated multi-task learning. arXiv preprint arXiv: 1705. 10467, 2017.
[35] Sebastian U Stich and Sai Praneeth Karimireddy. The error-feedback framework: Better rates for sgd with delayed gradients and compressed updates. Journal of Machine Learning Research, 21:1-36, 2020.
[36] Sebastian Urban Stich. Local sgd converges fast and communicates little. In ICLR 2019- International Conference on Learning Representations, number CONF, 2019.
[37] Roman Vershynin. High--iieensional probability: An introduction with applications in data science, volume 47, Cambridge university press, 2018
[38] Jianyu Wang and Gauri Joshi. Cooperative sgd: A unified framework for the design and analysis of communication--efiiien sgd algorithms. In ICML Workshop on Coding Theory for Machine Learning, 2019.
[39] Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and H Vincent Poor. Tackling the objective inconsistency problem heterogeneous federated optimization. Advances in Neural Information Processing Systems, 33, 2020.
[40] Cong Xie, Sanmi Koyejo, and Indranil Gupta. Asynchronous federated optimization. arXiv preprint 1rXiv: 03934, 2019.
[41] Yikai Yan, Chaoyue Niu, Yucheng Ding, Zhenzhe Zheng, Fan Wu, Guihai Chen, Shaojic Tang, and Zhihua Wu. Distributed non-convex optimization with sublinear speedup under intermittent client availability, arXiv preprint XrXiv:2002.07390 2020.
[42] Haibo Yang, Minghong Fang, and Jia Liu. Achieving linear speedup with partial worker participation in non-iid federated learning, arXiv preprint 2101 2021.
12

---

[43] Hao Yu, Rong Jin, and Sen Yang. On the linear speedup analysis of communication efficient momentum sgd for distributed non-convex optimization. In International Conference on Machine Learning, pages 7184-7193. PMIR, 2019.
[44] Jingzhao Zhang. Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank Reddi, Sanjiv Kumar, and Suvrit Sra. Why are adaptive methods good for attention models?, 2020.
[45] Xin Zhang, Jia Liu, and Zhengyuan Zhu. Taming convergence for asynchronous stochastic gradient descent with unbounded delay in non-convex learning. In 2020 59th IEEE Conference on Decision and Control (CDC), pages 3580-3585. IEEE, 2020.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 8
(c) Did you discuss any potential negative societal impacts of your work? [N/A] Our work mainly theoretical and targets at providing theoretical analysis of the FL algorithms, which has almost no negative societal impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] The assump- tions are rigorously stated in Section [ and Section
(b) Did you include complete proofs of all thcoretical results? [Yes] All the proofs are deferred to the appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] Our code will be included in the supplemental material. The datasets
public. The instructions needed to reproduce the main experimental results are clearly stated in Section 7
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section 7
(c) Did you report error bars (c.g., with respect the random seed after running experi- ments multiple times)? [Yes] See Section 7
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [Yes] See Section 7
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] See Section
(b) Did you mention the license of the assets? [Yes] See Section 7
(c) Did you include any new assets either in the supplemental material as URL? [Yes] We include our code for reproducing the experiments in the supplemental material.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A] We choose the commonly MNIST and CIFAR-10 10 datasets. (e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A] We choose the commonly-used MNIST and CIFAR-10 datasets.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "s8xTffIBL0L", "reviewer": "Reviewer_nrJT", "summary": "For a heterogeneous distributed optimization setting in which data of different characteristics is available to different workers, the paper proposes the usage of the latest reported updates from workers when unavailable. As claimed in the paper, this amends the bias introduced when utilizing only data from available workers (as in the previous state of the art methods), improves the convergence bounds for convex and non-convex smooth optimization settings, and does not require up-front knowledge of the workers-unavailability statistics.", "questions": "", "limitations": "", "rating": 6, "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": "Well written paper, clearly presenting the state of the art and the problems addresses by the proposed approach. The proposed algorithm nevertheless, although claimed to be adaptive, requires upfront knowledge of the smoothness and strong convexity ($L$ and $\\mu$ respectively), or searching for the correct values (i.e., to set the learning rate). Finally, although illustrating the superiority of the proposed methods over state of the art, the experimental section seems somewhat limited. To gain more confidence in the method and the related bounds, such experiments should have been run over several meta-parameters and unavailability schemes, datasets and model types.\n\nA few comments and questions:\nThe results presented in the introduction (lines 63, 64) use notation yet to be defined. \nThe notion of a communication round (as first mentioned in the introduction - line 48) is not reflected in Algorithm 1. E.g., how is the set of active devices determined? is there a watchdog/timeout to be employed? when is a 'round' declared? what if an update arrives later, out of the round (that is, a combination of the delayed setup and 'our setup' of Figure 1)?\nTypos? - founded (line 119), till (line 124).\n\n  ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"ethical_concerns": "no", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "n5xGTqJSGJO", "reviewer": "Reviewer_LFYH", "summary": "The paper tries to overcome the challenge of federated learning that devices may drop out of the training process arbitrarily ( which doesn't follow any known or unknown distribution). This paper proposes the Memory-augmented Impatient Federated Averaging (MIFA) algorithm and provides its theoretical analysis under arbitrary device unavailability. Experiments have been done to show the advantages of the proposed 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": "Originality:  The assumption on the device availability ( similar to Assumption 4 and 8) has been widely used in the theoretical analysis for asynchronous algorithms. It is new to see the assumption is used in FL to analyze arbitrary device unavailability. \n\nQuality:  The submission technically sound and the claims are well supported by theoretical analysis and experimental results.  Theoretical analyses with convex and nonconvex functions are provided. This is a complete piece of work. \n\n\nClarity: The submission is clearly written and well organized. \n\nSignificance:  The analysis with assumption 4 is new and significant to federated learning. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Given assumption 4, we have $\\tau_{max, T} =O(T)$, So, in Theorem 5.1, there is a constant term $A_1/\\mu^2$. It means the MIFA converges to the optimal solution with a constant error term, right? Similarly,  Proposition 5.1 has the same question.\n\nIn the experiment section, the initial learning rate only uses 0.1 and the weight delay only checks 0.001.  So, the comparison of performance among all methods may be unfaired.  It is better to check other learning rates and weight delays, and select the best performance for each method. \n\nIn Figure 2(a-d), FedAvg-IS always gives the best performance in terms of communication round, rather than the proposed MIFA method. Instead of using communication round, the authors may want to show running time, since the intuitive advantage of the proposed method MIFA (or \"asynchronous method\") is the better running time since it doesn't need to wait for unavailable devices. \n\n\n\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "N/A"}, "extra_text": {}}, {"review_id": "abLoODPTDc", "reviewer": "Reviewer_JW3q", "summary": "This work studies federated learning setup where clients might participate and drop out from the training arbitrarily. Broadly speaking, this is partial participation setup for FL, where there is no direct control on device availability. For such a setup, this paper designs MIFA algorithm, which stores latest gradients from devices and does not wait for strugglers during the training. The method is analyzed for strongly convex and non-convex cases with an additional (weak) assumption on device participation.", "questions": "", "limitations": "", "rating": 6, "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": "Partial participation (PP) is one of the characterizing aspects of federated learning (FL) as clients participate during the training only when they are available. Prior works usually model PP by assuming that a small portion of the devices (generated randomly) are available for the training. However, this ignores possibilities that some (or most and maybe even all) selected devices will be off, and in such case the ongoing communication round is failed. To overcome device unavailability, this work designs MIFA algorithm, which tracks the latest gradient information from each device and, in case of strugglers, updates the global model using stale gradient information of unavailable clients. This approach of handling device unavailability seems interesting.\n\nAny explanation on why $b = 40(L/\\mu)^{1.5}$ form is needed in Assumption 4 ? While the number of inactive rounds grow as ${\\cal O}(t)$, it seems to grow slowly because of the value $b$.\n\nThe discussion in lines 252-262 are not completely fair comparison against FedAvg/SCAFFOLD, since $\\frac{S}{N}\\frac{1}{p_{\\min}}$ iterations for FedAvg/SCAFFOLD are an extra waiting time, but for MIFA it is a normal iteration with communication rounds. In this context, are those waiting rounds counted in the experiments with FedAvg ?\n\nWhy the case that all devices are active is referred to as degenerated in line 66 ?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "Rl31NMuBwVt", "reviewer": "Reviewer_gyQJ", "summary": "The article introduces a new algorithm called MIFA (Memory-augmented Impatient Federated Averaging) for Federated learning with arbitrary device participation. They derive theoretical guarantees in terms of average convergence of the algorithm, which are proved minimax for strongly and non strongly convex smooth losses. Numerical experiments illustrate the empirical behaviour of the method in comparison to a baseline FL algorithm.", "questions": "", "limitations": "", "rating": 6, "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": "The paper is sound, well written and clear, the theoretical results are also precise.  My one main concern is about the novelty of the setting, as detailed below. \n- The authors claim that existing methods only consider delayed responses of devices rather than full drop out, but I am not sure it is true. There are several FL algorithms, more recent thatn FedAvg, which handle partial participation of devices, including with missing devices (see, e.g. [1] and [2]), and I am not sure whether the setting you describe is really new. Please clarify.\n- It is a bit frustrating that the obtained theoretical rates are not compared qualitatively to existing work. \n- It is also a bit frustrating that the method is empirically challenged only with FedAvg, when many algorithms have been proposed since then, including with partial device participation (see references [1] and [2]).\n\n\n[1] Eduard Gorbunov, Konstantin Burlachenko, Zhize Li, Peter Richtarik (2021). MARINA: Faster Non-Convex Distributed Learning with Compression. ICML.\n[2] [1]Philippenko, C. and Dieuleveut, A., “Bidirectional compression in heterogeneous settings for distributed or federated learning with partial participation: tight convergence guarantees”, <i>arXiv e-prints</i>, 2020.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors focus on addresses some new challenges in Federated Learning. In particular they focus on the effect of straggler devices that may dropout which severely affect convergence of popular FL baselines. To ovecome this challenge they propose a new algorithm called Memory-augmented Impatient Federated Averaging (MIFA). The authors claim that their approach avoids the latency of inactive devices and can effectively correct for such gradient bias by using memorized updates from devices. The authors also show that this approaches achieve a minimax optimal convergence rate for non-i.i.d. data in certain cases. They also corroborate their theoretical findings with a variety of experiments. Most reviewers thought the paper was well written with a clearly presented approach to tackle a well motivated problem. The reviewers raised a variety of technical concerns some of which were addressed during the rebuttal. The conclusion of the discussion was that while the paper is not extremely novel/original and falls into the marginal category is a solid contribution and merits acceptance. I agree with this assessment and recommend acceptance with the condition that the authors clearly address the valid concerns raised by the reviewers.
Decision: Accept (Poster)