Fast Federated Learning in the Presence of Arbitrary Device Unavailability
Year: 2021

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 beyond the control of the central server. 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 under 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 the devices. 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.

heading: 1 Introduction
text: Federated learning is a machine learning setting in which a central server coordinates with a large number of devices to collectively train a shared model [28, 34, 20, 33, 25, 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 can make use 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 on FL from an optimization perspective.
In FL, a device can differ from its peers in multiple aspects [17, 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, 18, 19, 42, 25]. We follow this line of work and formulate our optimization objective as a sum of stochastic functions on individual devices (See Eqn. (1)).
∗Equal contribution. †Corresponding author.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
A second variation among devices is caused by different computing and communication speeds. One natural way to formulate the variation in computation speeds is to allow asynchronous updates and model the updates as delayed responses. Lots of novel research has studied the problem with different delay models, e.g., [35, 4, 27, 11, 45, 1, 5, 13]. 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 patterns.
The third device heterogeneity caused by different availability patterns is less studied in optimization for federated learning problems. In this model, instead of making a 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, 17]. 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, 17, 30, 14].
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 [17, 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 if 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 to be non-stationary and even adversarial. Furthermore, our algorithm can achieve optimal convergence rates in 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 participation, which does not require each device to be online according to an (either known or unknown) distribution.
• We propose the Memory-augmented Impatient Federated Averaging (MIFA) algorithm that is agnostic to the availability pattern. It efficiently avoids excessive latency induced by inactive devices, successfully exploits the information about the descent direction in stale and noisy gradients, and corrects the gradient bias using the memorized latest updates.
• We prove that MIFA achieves minimax optimal convergence rates O ( τ̄T+1 NKT ) for smooth,
strongly convex functions, and O (√
ν̄+1 NKT
) for smooth, non-convex functions, and es-
tablish matching lower bounds. Here, N,K and T stand for the number of devices, local updates and communication rounds respectively. τ̄T and ν̄ characterize how actively devices participate in training (see formal definitions in Sections 3, 5 and 6). MIFA also achieves optimal convergence rates in the ideal case when all devices are active.
• We provide an explicit characterization of the improvement over baseline algorithms through a case study and empirically verify our results on real-world datasets.

heading: 2 Related work
text: Federated learning. Federated Averaging (FedAvg) was first proposed in [28]. [26, 19, 18, 42] provided convergence analysis for FedAvg on non-i.i.d. data and quantified how data heterogeneity degrades the convergence rate. Several variants of FedAvg were designed to deal with data heterogeneity. 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 [39, 31, 40]. 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 [18, 28, 42, 25, 14] or that the pattern of device availability is known [26, 17, 10, 30]. These results do not generalize to adversarial inactive patterns. [32] discussed the impact of device inactivity on convergence but their proposed algorithm diverges if there exists an inactive device in 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 [13]. One is the shared-data (i.i.d.) setting, where all workers can access the whole dataset. In this setting, the local gradient is an unbiased estimator of the global gradient [35, 4, 27, 11, 45, 1]. 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-data setting (non-i.i.d.), 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. [13] models the delay as stochastic and assumes that the server has knowledge of the distribution, but our formulation is distribution-free. [6] allows workers to 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.
Comparison with an independent work. While preparing the manuscript, we were unaware of an independent work [41] that investigated the same setup and proposed a similar algorithm called FedLaAvg. Their main theorem established the convergence rate of O (√ νmax N0.5T (G 2 + σ2) )
for smooth and non-convex problems, where G2 is the uniform upper bound for the squared norm of stochastic gradients and νmax is the maximum number of inactive rounds. In comparison, we prove
the minimax optimal rate ofO( √
ν̄ NKT σ 2) without the bounded gradient assumption, also improving νmax to ν̄. 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.

heading: 3 Problem Setup
text: We consider optimizing the following problem in a Federated Learning setting:
min w∈Rd
f(w) := 1N ∑N i=1 fi(w) := 1 N ∑N i=1 Eξi [fi(w, ξi)], (1)
where w is the optimization variable, e.g., parameters of a machine learning model, N is the number of participating devices, fi is the local loss function on device i, and ξi describes the randomness in local data distribution.
In the ideal federated learning setup (see Figure 1 (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 a delayed FL setup (see Figure 1 (b)), devices are always active upon the central server’s 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 [28, 17]. This motivates our setup in Figure 1 (c).
In our proposed setup, we use t to index the global communication rounds. We say a device participates or is active at round t if it 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 a 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 a subset of S devices randomly without replacement, and then waits until all devices in the subset S respond. This is how original FedAvg [28] addresses device unavailability. Note that over T communication rounds, the global model is updated less than T times due to waiting. This approach is prone to stragglers and we refer the readers to Section 5.1 for a detailed discussion.
• FedAvg with importance sampling [26, 13, 17]. 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 of each device is i.i.d. over rounds and it requires the knowledge of participation probabilities.

heading: 4 Memory-augmented Impatient Federated Averaging (MIFA)
text: In this section, we introduce our algorithm — Memory-augmented Impatient Federated Averaging (MIFA). MIFA maintains an update-array {Gi} 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 t, the server broadcasts the latest model parameter wt to all active devices A(t). After receiving wt, each active device, say, the i-th device, sets wit,0 = wt and performs K steps of SGD with respect to the local objective function to get wit,K :
wit,k+1 = w i t,k − ηt∇̃fi(wit,k), k = 0, · · · ,K − 1,
where ηt is the learning rate and ∇̃fi(wit,k) is the stochastic gradient evaluated on device i. Next, the server stores the received update 1ηt (wt − w i t,K) in G
i. Denote by {Git} the update-array after round t, then we have
Git = { Git−1, if i /∈ A(t), 1 ηt (wt − wit,K), if i ∈ A(t).
At the end of round t, the server updates the global model with the average of {Git} (line 9). In other words, our algorithm MIFA updates the model with the latest available accumulated gradients for all devices.
Algorithm 1 Memory-augmented Impatient Federated Averaging (MIFA) 1: Input: initial w1, learning rate {ηt} 2: Server executes: 3: initialize Gi ← 0, i ∈ [N ] 4: for t = 1, · · · , T − 1 do 5: broadcast wt to all active devices i ∈ A(t) 6: for each active device i do 7: Gi ← DeviceUpdate(i, wt, ηt) 8: end for 9: wt+1 ← wt − ηtN ∑N i=1G i 10: end for 1: DeviceUpdate(i, wt, ηt): 2: wit,0 ← wt 3: for local step k = 0, · · · ,K − 1 do 4: compute stochastic gradient ∇̃fi(wit,k) 5: wit,k+1 ← wit,k − ηt∇̃fi(wit,k) 6: end for 7: Return 1ηt (wt − w i t,K) to the server
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, 11, 45, 1, 13, 6] in that we 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 a 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 Git′i computed at round t′i in its local memory. When it becomes active and computes G i t, the device sends Git −Git′i to the server, which is the difference between the current update and the previous one. In this case, the server only needs to maintain the average Ḡ in the memory and updates it by Ḡt = Ḡt−1 + 1N ∑ i∈A(t)(G i t − Git′i) at round t. Then the server updates the global model by wt+1 = wt − ηtḠt.

heading: 5 Convergence Analysis for strongly convex objective functions
text: In this section, we present the convergence results for MIFA on µ-strongly convex L-smooth functions. Typical examples for the strongly convex case are `2 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 i at round t as τ(t, i) = t−max{t′ | t′ ≤ t, i ∈ A(t′)}, which is the difference between current round t and the latest round when device i is active.
It can be seen that τ(t, i) = 0 if device i is active at round t and τ(t, i) = τ(t− 1, i) + 1 otherwise. Also, t − τ(t, i) is the latest round when the device i is active. Next, we present the assumptions made for establishing our convergence theorem. Assumption 1. f1, · · · , fN are all L-smooth, i.e., for all w and v, fi(v) ≤ fi(w) + 〈∇fi(w), v − w〉+ L2 ‖w − v‖ 2.
Assumption 2. ∇̃fi(w) is an unbiased estimator of ∇fi with variance bounded by σ2, i.e., Eξ [ ∇̃fi(w) ] = ∇fi(w), Eξ [∥∥∥∇̃fi(w)−∇fi(w)∥∥∥2] ≤ σ2. Assumption 3. f1, · · · , fN are all µ-strongly convex: for all w and v, fi(v) ≥ fi(w) + 〈∇fi(w), v − w〉+ µ2 ‖w − v‖ 2.
Assumption 4. There exists a constant t0 > 0, such that for all t ≥ 1 and i ∈ [N ], the number of inactive rounds of device i at communication round t satisfies τ(t, i) ≤ t0 + 1b t, where b = 40 (L/µ) 1.5.
Assumptions 1, 2, and 3 are standard and common in the FL literature, e.g., [26, 18, 19, 42, 36]. In Assumption 2, we relax the bounded gradient assumption that is often required in prior work, e.g., [6, 26, 40, 1]. Lastly, Assumption 4 is a very mild assumption on device availability, since it allows the number of inactive rounds to grow as O(t). In contrast, existing results on asynchronous updates mostly assume a bounded or fixed latency, e.g., [6, 1, 5, 40, 35, 4].
We are now ready to present our first convergence result. Define D = 1N ∑N i=1 ‖∇fi(w∗)‖
2 to measure data dissimilarity, where w∗ = arg min f(w) is the global optimum. Also, define τ̄T and τmax,T to be the average and maximum numbers of inactive rounds τ(t, i) across all devices and rounds, respectively. That is,
τ̄T = 1
N(T − 1) T−1∑ t=1 N∑ i=1 τ(t, i), τmax,T = max i∈[N ] max 1≤t≤T−1 τ(t, i).
The following theorem summarizes the performance of MIFA in this case. Theorem 5.1. Assume that Assumptions 1 to 3 hold. Further assume that the device availability sequence τ(t, i) satisfies Assumption 4 and τ(1, i) = 0 for all i ∈ [N ]. By setting the learning rate ηt = 4µK(t+a) with a = max{100, 40t0}(L/µ)
1.5, after T − 1 communication rounds, MIFA satisfies:
Eξ [f(wT )]− f(w∗) = O
( τ̄T + 1
µNKT σ2 + τ2max,TA1 + (K − 1)2A2 +A3 µ2T 2
) ,
where wT is a weighted average of wt defined as:
wT = 1
WT T∑ t=1 (t+ a− 1)(t+ a− 2)wt, WT = T∑ t=1 (t+ a− 1)(t+ a− 2),
and A1 = L(D + Lσ2/µ), A2 = L(D/K2 + σ2/K3), A3 = t20L 3 ‖w1 − w∗‖2.
Our results hold under Assumption 4, which allows for arbitrary device availability sequences with τmax,T = O(T ). However, for MIFA to converge, we require τmax,T = o(T ) and t0 = o(T ). When T = Ω( NK(τ2max,T+t 2 0)
τ̄+1 ), the first term dominates and the impact of the second O(1/T 2) term is
negligible. In fact the first term in Theorem 5.1 is minimax optimal by our information-theoretic lower bound for the problem in the next proposition. Proposition 5.1. Let c0 > 0 be a universal constant. For any potentially randomized algorithm, there exists a stochastic strongly convex problem satisfying Assumptions 1 to 3, such that the output wT after T rounds of communication has expected sub-optimality lower bounded by
E[f(wT )− f(w∗)] ≥ c0 τ̄Tσ
2
µNKT .
The proof is based on the observation that the number of gradient evaluation can scale inversely with τ̄T and that the oracle complexity is tight even for centralized stochastic optimization problems. The optimality of the first term in Theorem 5.1 is independent of the distributed or the FL setup.
The second term in Theorem 5.1 converges at the rate O(1/T 2) and consists of three parts, where the first part reflects the slowdown caused by device unavailability through τmax,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, i) = 0 for all i and t, our setup reduces to FedAvg with full device participation, and we have τ̄T = 0 and τmax,T = 0. In this case, Theorem 5.1 yields
boundO ( σ2
µKNT + L(σ2/K+D+L2‖w1−w∗‖2) µ2T 2
) , matching the rateO ( σ2 log T µKNT + L(σ2/K+D)(log T )2 µ2T 2 +
µ ‖w1 − w∗‖2 exp(− µ48LT ) ) in [18] (Thm. V. B2 = 2,ηg = 1) up to logarithmic terms. Besides, in the general case, our O(τ2max,TA1/T 2) 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 at 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 w1 at the very beginning.

heading: 5.1 Case Study: i.i.d. Bernoulli participation
text: Though our algorithm can be applied to non-stationary and non-independent response patterns, we show in this subsection that even in the simple i.i.d. Bernoulli participation scenario our algorithm can achieve considerable improvement compared to known algorithms. In particular, we consider a setup where each device becomes active independently with a fixed probability pi. It serves as the first motivating example towards modeling the participation patterns of devices, and provides a clean view of how the heterogeneity of the device participation influences the Federated optimization algorithms.
We will show that in this scenario, Assumption 4 holds with high probability, and the terms involving the inactive rounds τ(t, i) in Theorem 5.1 can also be bounded. Furthermore, we theoretically demonstrate that algorithms such as FedAvg [28] and SCAFFOLD [18], which sample S devices for each global update, are more prone to stragglers than our algorithm.
Definition 5.2. Assume that for all i ∈ [N ], the i-th device is assigned with a probability pi. We say the participation of the devices follows i.i.d. Bernoulli participation model with participation probabilities {pi}, if (1). at the first round, all devices are active, and (2). at round t > 1, device i is active with probability pi, which is independent of the history and other devices.
Next theorem shows that under i.i.d. Bernoulli participation scenario, with high probability, τ(t, i) only grows logarithmically in t. Also Assumption 4 holds for a mild choice of t0.
Theorem 5.2. For i.i.d. Bernoulli participation model defined in Definition 5.2, given any δ > 0, with probability at least 1− δ, we have the following holds for all t ≥ 1 and i ∈ [N ] simultaneously,
τ(t, i) ≤ O ( 1 pi (log(Nt/δ) + 1) ) .
Furthermore, (1). Assumption 4 holds true if t0 = Ω (
1 pmin log bNpminδ
) , where pmin = min{pi}, and
b = 40(L/µ)1.5;(2). τmax,T can be upper bounded as
τmax,T ≤ O ( 1 pmin · ( log(TN/δ) + 1 )) .
The next theorem provides a high probability upper bound for τ̄T .
Theorem 5.3. For i.i.d. Bernoulli participation model defined in Definition 5.2, given any δ > 0 and T > 1, with probability at least 1− δ, we have
τ̄T ≤ ( 1 N N∑ i=1 1 pi ) · O ( 1 + log 1 δ ) .
By Theorem 5.2 and Theorem 5.3, we conclude that the dominant term of our convergence bound is Õ (
1 N ∑N i=1 1 pi · σ 2 µNKT ) . Therefore, to achieve accuracy, the dominant term of the number of the
required rounds is
T (MIFA) = Õ ( 1 N N∑ i=1 1 pi · σ 2 µNK ) . (2)
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 = Õ ( σ2
µSK
) . Notice that in our setting, to accomplish each global update, the server needs to
wait for a few rounds for the S devices to respond. Let 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 (S)]. For i.i.d. Bernoulli participation model, we have T (S) ≥ 1min{pi|i∈S} , and we can further show that ES [T (S)] ≥ 1pmin S N (see Appendix D.3 for details). Therefore,
E [ T (FedAvg,SCAFFOLD) ] ≥ S N 1 pmin Õ ( σ2 µSK ) = Õ ( 1 pmin · σ 2 µNK ) . (3)
By comparing Eqn. 2 and Eqn. 3, we see that both FedAvg and SCAFFOLD are more vulnerable to stragglers, that is, the devices with very small participation probabilities; on the contrary, the convergence rate of MIFA only depends on the average of 1/pi instead of 1/pmin. We also provide empirical experiments showing that MIFA converges faster than FedAvg in Section 7.

heading: 6 Convergence result for non-convex objective functions
text: 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). f1, · · · , fN are all ρ-Hessian Lipschitz: for all w and v,∥∥∇2fi(w)−∇2fi(v)∥∥ ≤ ρ ‖w − v‖. Assumption 6 (Bounded noise). The noise of the local stochastic gradients is upper bounded by a constant δ almost surely:
∥∥∥∇̃fi(w)−∇fi(w)∥∥∥ ≤ δ a.s., ∀ i ∈ [N ]. Assumption 7 (Bounded gradient dissimilarity). There exist α > 0 and βi > 0 such that for all w and i ∈ [N ]: ‖∇fi(w)‖2 ≤ α ‖∇f(w)‖2 + βi. Furthermore, we define β = 1N ∑N i=1 βi. Assumption 8. There exists a constant νi such that τ(t, i) ≤ νi, for all i ∈ [N ] and t ≥ 1. Furthermore, define ν̄ = 1N ∑N i=1 νi and νmax = maxi∈[N ] νi.
The analysis of non-convex functions is much more technically involved, and our results rely on strong assumptions that provide a finer control of the gradient difference (Assumption 5), gradient noise (Assumption 6), gradient dissimilarity among devices (Assumption 7), and device unavailability (Assumption 8). We remark that Assumption 5 is also made in [9, 16], and Assumption 7 is also made in [18, 39]. We leave it as future work to study whether and how MIFA converges for non-convex functions with weaker assumptions. Theorem 6.1. Assume that Assumptions 1, 2, and 5 to 7 hold. Further assume that the device availability sequence τ(t, i) satisfies Assumption 8 and τ(1, i) = 0 for all i ∈ [N ]. By using a learning rate η = √ N
KTL(1+ν̄) , for T ≥ max{32αLNK, 16LNK, 8KNν2max(L 2+ρδ) L }, after T − 1
communication rounds, MIFA satisfies:
min 1≤t≤T
Eξ [ ‖∇f(wt)‖2 ] = O
(√ (1 + ν̄)L
TKN (f(w1)− f∗ + σ2) + A4 +A5 T
) ,
where f∗ is the optimal value, and:
A4 = NKL
( ασ2ν̄ +
σ2νmax√ KN
+ σνmax √ β ) +
(L2 + ρδ)σ2νmax L ,
A5 = (K − 1)NL(β + σ2/K)
ν̄ + 1 .
Next, we show that the leadingO(1/ √ T ) term is theoretically optimal for zero-respecting algorithms.
Proposition 6.1. Let c0 > 0 be a universal constant. For any randomized zero-respecting algorithm, there exists a stochastic non-convex problem satisfying Assumption1, 2, 5 and 7, such that the output wT after T rounds of communication has expected sub-optimality lower bounded by
E[‖∇f(wT )‖2] ≥ E[‖∇f(wT )‖]2 ≥ c0
√ ν̄Lσ2(f(w0)− f∗)
NKT .
The above proposition show that when σ √
(f(w0)− f∗) ∼ σ2 + (f(w0) − f∗), the result in Theorem 6.1 is tight. However, note that the counter example we used requires the quantity δ 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 δ. Whether this requirement can be relaxed is left as an open problem.
Remark 6.1. When all νi = 0 (i.e. all the devices are active), our convergence bound reduces to O (√ L
TKN (f(w1)− f ∗ + σ2) + (K−1)NL(β+σ 2/K) T
) . This matches the result in [42] (Thm. 1,
η = 1, ηL = √ N KTL ).

heading: 7 Numerical Experiments
text: In this section, we conduct numerical experiments3. to 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 4. We remark that for a 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 {Gi}. Following [26, 25], we construct non-i.i.d. datasets from two commonly used computer vision datasets — MNIST [23] and CIFAR-10 [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 LeNet-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 `2 penalty. We use logistic models for MNIST dataset, while we use LeNet-5 for CIFAR-10. Our code is adapted from [26], which is under MIT License.
We model the availability of the devices as independent Bernoulli random trials. The i-th device is assigned with a probability pi, where at each time step, the device becomes active with probability pi. In our experiments, the pi’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 pi = pmin min(j, k)/9 + (1− pmin), where pmin controls the lower bound of the participation probabilities. 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 η0 = 0.1 and decay the learning rate as ηt = η0 · 1t . We set the weight decay to be 0.001. The local batch size is 100 and each local update consists of 2 epochs. Therefore, the actual number of local steps K depends on the size of the dataset. We run 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 2.
We observe that FedAvg with device sampling (FedAvg (S = 50) and FedAvg (S = 100) in Figure 2) is severely influenced by the straggling devices and makes progress relatively slowly compared to 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.

heading: 8 Conclusions and Discussions
text: 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 is unavailable. We theoretically analyze MIFA without any structural assumptions on the device availability and prove the convergence for strongly convex and non-convex 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 nonstationary and possibly adversarial pattern of device participation. Therefore, it is important to study how the number of inactive rounds influences the convergence rate. In Theorem 5.1, the dependency
3Our code is available at https://github.com/hmgxr128/MIFA_code/
upon τmax,T might be an artifact of our analysis, and a future direction is to study whether we can 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 Longbo Huang is supported in part by the Technology and Innovation Major Project of the Ministry of Science and Technology of China under Grant 2020AAA0108400 and2020AAA0108403. Xinran Gu would like to 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.

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

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.

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.