{'fraction_non_alphanumeric': 0.037072558928769046, 'fraction_numerical': 0.008816260282562986, 'mean_word_length': 4.153992395437262, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 19, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Towards Flexible Device Participation in Federated Learning for Non-IID Data

Traditional federated learning algorithms impose strict requirements on the participation rates of devices, which limit the potential reach of federated learning. In this paper, we extend the current learning paradigm and consider devices that may become inactive, compute incomplete updates, and leave or join in the middle of training. We derive analytical results to illustrate how the flexible participation of devices could affect the convergence when data is not independently and identically distributed (IID), and when devices are heterogeneous. This paper proposes a new federated aggregation scheme that converges even when devices may be inactive or return incomplete updates. We finally discuss practical research questions an operator would encounter during the training, and provide answers based on our convergence analysis.


Introduction
Federated learning is a cutting-edge learning framework that allows distributed devices to train a shared machine learning model cooperatively without sharing the raw data. In recent years, federated learning has exhibited remarkable performance in many applications such as next word suggestion, fault detection, and learning on private medical data. General federated learning involves a coordinator and a collection of devices. The training procedure consists of multiple rounds, each of which includes the following three steps: • Synchronization: the coordinator synchronizes the latest global model with all devices.
• Local updates: each device trains a local model for a few local epochs, using samples from its local dataset. • Aggregation: the coordinator aggregates some, or all, of the local models to produce the next global model. and upload the results whenever they are selected. This is why the traditional federated learning paradigm requires participating devices to be dedicated to the training during the entire federated learning period. For example, the popular FedAvg algorithm assumes mobile users will participate only when their phones are currently plugged-in, and have unlimited WI-FI access [McMahan et al., 2016].
Considering that federated learning typically takes thousands communication rounds to converge, it is difficult to ensure that all devices will be available during the entire training in practice. Moreover, there are typically multiple apps running simultaneously on user devices, competing for already highly constrained hardware resources. As such, it cannot be guaranteed that devices will complete their assigned training tasks in every training round as expected. Even for cross-silo applications, where more powerful computers or cloud servers may be adopted, devices' availability can still be an issue due to the increasingly popular usage of preemptive cloud services such as AWS's spot instances, where the user process can be interrupted unexpectedly . While many other methods have been proposed to mitigate the workload of individual devices, such as weight compression and federated dropout [Caldas et al., 2018], they cannot completely remove the probability of confronting undesirable device behaviors during the training. This probability, intuitively, increases as more devices join the training. Therefore, in large scale federated learning, many lowend devices have to be excluded from joining federated learning in the first place, which restricts the potential availability of training datasets, and weakens the applicability of federated learning. Furthermore, the existing training procedure does not specify how to react when confronting irregular device behaviors, and also does not analyze the (negative) effects of such behaviors on the training progress.
In this paper, we relax these restrictions and allow more devices to follow more flexible participation patterns. Specifically, the paper incorporates four situations that are not yet well discussed in the literature: • In-completeness: devices submit only partially completed work in a round.
• In-activeness: devices do not respond to the coordinator in a round.
• Early departures: existing devices quit the training without finishing all training rounds.
• Late arrivals: new devices join after the training has already started.
The difference between in-activeness and departure is that inactive devices will temporarily disconnect with the coordinator, but are expected to come back in the near future. In contrast, departing devices will inform the coordinator that they are going to leave, and do not plan to rejoin the system. For example, if a user quits the app running federated learning, a message can be sent to the coordinator; the coordinator thus knows who is leaving. A possible solution to incorporate flexible device participation is through the online learning framework, where datasets keep changing and the training can last forever. Though there are some preliminary explorations in this direction [Chen et al., 2019], it has not generally been verified that online learning can actually work in the federated setting. Thus, in this paper, we consider traditional fixed time learning where the training must terminate before some deadline, i.e., maximum number of rounds. The results of our paper can help to answer the following research questions.
• How can we utilize the partially completed work? Federated learning requires the participating devices to run a certain number of local epochs between two aggregations. Due to resource competition as mentioned above, some devices may not be able to complete all local epochs as expected. An easy solution is to simply discard the partial work and re-start this round, which slows down the training progress. We will show that devices' partial work can be reused without greatly affecting the convergence compared to full completion by all devices if we properly scale the aggregating weight in the aggregation step. • Should we remove an inactive device? In the extreme case, a device may temporarily become inactive and fail to submit its update to the coordinator. We will show that a mild degree of in-activeness will not greatly affect the convergence. However, if a device is expected to be frequently inactive during the training period, we may want to kick it out and assume it quits the training, in order to prevent the device from interfering with the algorithm convergence. We answer the question: what kind of devices should be removed from training? • What to do if a device departs? When an existing device leaves early, the coordinator will no longer receive updates from it. The trained model will inevitably move away from the leaving device, which imposes additional bias on the training loss. This bias is less severe if the training is already close to the end. But if the leaving happens at an early stage, the bias may accumulate and cause the training to diverge. In this case, we can shift the objective to "forget" the influence of this device. After the shifting process, the trained model will no longer be applicable to the leaving dataset, but will have a higher accuracy on the remaining datasets. There thus exists a threshold time when we prefer shifting to sticking to the status quo.
• When should we admit an arriving device? When the training time is relatively long, more high-quality datasets can be discovered during the process. The operator may hope to include these devices to increase the generalizability of the trained model. Every time a device arrives, the current training progress will be interrupted, and we need to add a new term to the training objective that corresponds to the new device. In other words, the trained model, which is originally only intended for the old datasets, has to be updated so that it can work on the newly admitted data points. To establish the convergence of this process, sufficient training time must remain before the deadline so that the model can fully adapt to the new objective. In this work we will show how to find the latest possible time to admit a new device.
In Section 2, we will review relevant literature. In Section 3, we will give an convergence analysis that considers the four situations. Based on this analysis, we will answer our four research questions in Section 4, and compare our convergence rate analytically with other possible alternatives.

Related Works
The celebrated federated learning algorithm named FedAvg runs the stochastic gradient descent (SGD) algorithm in parallel on each device in the system and averages the updated parameters from a small set of end devices periodically. However, it lacks theoretical convergence guarantees in realistic settings, such as when the local data is not independent and identically distributed across devices (non-IID data). A few recent works provide theoretical results for the non-IID data case. For instance, in [Li et al., 2020], the authors analyze the convergence of FedAvg on non-IID data and establish an O( 1 T ) convergence rate for strongly convex and smooth optimization problems, where T is the number of rounds of local SGD updates. These works either simplify the heterogeneity of the devices, e.g., ignoring cases where some devices may partially finish some aggregation rounds or quit forever during the training [Li et al., 2020] [Zhao et al., 2018], or consider alternative objective functions for the SGD algorithm to optimize [Smith et al., 2017].
The algorithm FedAvg with non-IID data across devices has also been modified in specific edge computing scenarios to reduce the communication overhead [Liu et al.] or maintain a good training convergence under a resource budget constraint [Wang et al., 2019]. However, these works do not consider the possibility that the edge devices can be unavailable during the training process or join at different times, which are the main challenges of this work. An online learning framework is a possible way to enable flexible device participation in the federated learning scenario. For instance, [Chen et al., 2019] proposes an asynchronous federated learning algorithm to handle inbalanced data that arrives in an online fashion onto different devices. Although the asynchronous aggregation in their proposed algorithm can be naturally applied to randomly inactive devices, the authors do not analyze how their algorithm's convergence is affected by the device inactiveness or incompleteness and data heterogeneity.

Convergence Analysis
In this section, we establish the convergence bound for federated learning with flexible device participation patterns. Our analysis is based on the standard FedAvg algorithm where local devices use stochastic gradient descent (SGD) as the local optimizer. In the aggregation step, all devices are counted even if they cannot finish all local epochs. The analysis considers a non-IID data distribution and heterogeneous devices, i.e., some devices can be more stable than the others. We first derive the convergence bound with incomplete and inactive devices in Sections 3.1 to 3.3, and then we discuss the effects of device arrival and departure on the algorithm convergence in Section 3.4.

Algorithm Description
Suppose there are N devices, and that each device k wishes to minimize its local loss function F k (w). Here w represents the parameters of the machine learning model to be optimized, and F k (w) may be defined as the average loss over all data points at device k, as in typical federated learning frameworks [McMahan et al., 2016]. The global objective is to minimize F (w) = N k=1 p k F k (w), where p k = n k n , n k is the number of data points device k owns and n = N k=1 n k . Let w * be the minimizer of the global objective F , and denote by F * k the optimal value of F k . We quantify the degree to which data at each device k is distributed differently than that at other devices as Li et al., 2020]. We consider discrete time steps t = 0, 1, . . . . Model weights are synchronized when t is a multiple of E, i.e., each round consists of E time steps. Assume there are at most T rounds. For each round (say the τ th round), the following three steps are executed: • First, the coordinator broadcasts the latest global weight w G τ E to all devices. Each device updates its local weight so that: (1) Here η τ is a staircase learning rate that decays with τ , 0 ≤ s k τ ≤ E represents the number of local updates this device completes in this round, • Third, the coordinator aggregates the next global weight as (2) We define that a device k is inactive in round τ if s k τ = 0 (i.e., it completes no local updates), and say it is incomplete if 0 < s k τ < E. We treat each s k τ as a random variable that can follow an arbitrary distribution. For all devices, s k τ can generally be time-varying, i.e., it may follow different distributions at different time steps. Devices are heterogeneous if they have different distributions (series) of s k τ , and otherwise they are homogeneous. We also allow the aggregation coefficients p k τ to vary with τ . In Section 4, we will discuss different schemes of choosing p k τ and their impacts on the training convergence.
As a special case, traditional FedAvg assumes all selected devices can complete all E local epochs, so that s k τ ≡ E. Also, FedAvg with full device participation uses fixed aggregation coefficients p k τ ≡ p k , so that the right hand side of (2) can be written as N k=1 p k w k τ E , i.e., aggregating gradients is equivalent to aggregating the model parameters directly.

Assumptions
The analysis relies on the following five assumptions. The first four are standard [Li et al., 2020]. The last assumption excludes the extreme case of choosing infinitely large aggregation coefficients.
Assumption 3.1. F 1 , . . . , F N are all L-smooth, so that F is also L-smooth.
Assumption 3.3. The variance of the stochastic gradients is bounded: The expected squared norm of the stochastic gradients at each local device is uniformly bounded: E ξ g k t 2 ≤ G 2 for all k and t.
Assumption 3.5. There exists an upper bound for the aggregation coefficient p k τ /p k ≤ θ.

Convergence Bound
Assume the following expectations exist and can be computed or bounded: for all rounds τ and devices k, and assume E[ N k=1 p k τ s k τ ] = 0; intuitively, this last assumption ensures that some updates are aggregated in each round. Let z τ ∈ {0, 1} indicate the event that the ratio E[p k τ s k τ ]/p k take the same value for all k. We can obtain the convergence bound as follows: , so w G τ E will eventually converge to a globally optimal solution as τ → ∞ if M τ increases sub-linearly with τ . In the original FedAvg, p k τ s k τ ≡ p k E, thus z τ ≡ 0 and M τ ≡ 0 as per the definitions. When considering flexible device participation patterns, M τ may increase with τ . But as we will see in Section 4, by smartly choosing the aggregation coefficients p k τ , the increase can be controlled to ensure convergence.

Shifts in the Global Objective
When a device k quits at some τ 0 < T , no more updates will be received from it. Thus, s k τ = 0 for all τ > τ 0 . As a result, the ratio E[p k τ s k τ ]/p k must take different values for different k, when τ > τ 0 , since otherwise all p k τ will equal zero. Therefore, z τ = 1 for all τ > τ 0 . According to (3), w G τ E then cannot converge to the global optimal w * as M T ≥ T − τ 0 . This can be intuitively explained as follows: When the data distribution is non-IID, one device must contribute sufficiently more updates in order for its data's characteristics to be absorbed by the trained model. After a device leaves, the remaining training steps will wash out the model's previous memory about the leaving device, and push the model towards the data at the remaining devices. Thus, the output model may not still be applicable to the leaving device, especially when it leaves early in the training (τ 0 ≪ T ). This result suggests that we may wish to discard a departing device if we cannot guarantee the trained model will perform well on it, and that the earlier a device quits, the more likely we are to discard it.
Furthermore, once we decide to discard the departing device (say the lth device) and exclude it from the training, sticking to the original learning objective F = N k=1 p k F k is meaningless. Instead, it is more reasonable to update F asF = N k=1,k =l p k F k , i.e., to remove F l from the learning objective. As a result, the optimal weight w * will shift to somew * that minimizesF . Generally,w * is different from w * , which produces an additional offset to the convergence bound in Theorem 3.
A sufficient number of updates are then required for w G τ E , which is originally moving towards w * , to converge to the new optimalw * . The same argument holds when a new device arrives; admitting this device will require changing the global objective function to include the loss on its data. The learning rate also needs to be increased after shifting the objective. Intuitively, if the shift happens at a large time τ 0 , when w G τ0E is close to the old optimal w * and η τ0 is close to zero, reducing the latest difference w G τ0E −w * ≈ w * −w * with such a small learning rate is unreasonable. Thus, a greater learning rate is required, which is equivalent to initiate a fresh start after the shift. Nevertheless, even with a larger learning rate, there still must be enough time left for the model to fully absorb the new device.
The following theorem bounds the offset of the optimal weight due to the objective shift: Theorem 3.2. Consider the objective shift F →F , w * →w * . LetΓ k = F k (w * ) − F * k quantify the degree of non-IID data with respect to the new objective. Then in the device departure case and in the arrival case Here l indexes the departing/arriving device, and n is the total number of data points before the shift.
As we can intuitively expect, the difference reduces when the data becomes more IID (Γ l → 0), and when the departing/arriving device owns fewer data points (n l → 0).

Discussion
Based on the convergence analysis in Section 3, in this Section, we will answer the research questions in Section 1 associated with the four flexible participation patterns.

Schemes of Choosing p k τ
According to Theorem 3.1, the convergence bound is controlled by expectation of p k τ and its functions. Below we discuss three schemes of choosing p k τ , and compare their convergence rates in Table  1.
• Scheme A: Only aggregate parameters from clients who complete all E local epochs, with weight p k τ = N p k Kτ q k τ , where K τ is the number of complete devices, q k τ ∈ {0, 1} denotes if client k is complete, i.e., it completes E epochs. If K τ = 0, this round is discarded.
• Scheme B: Allow clients to upload incomplete work, with fixed weight p k τ = p k . • Scheme C: Accept partial work, with adaptive weight p k τ = E s k τ p k , or 0 if s k τ = 0.
Schemes A and B are natural extensions of FedAvg. Scheme C assigns a greater aggregation coefficient to devices that complete fewer local epochs. Though this seems counter-intuitive, as fewer local updates might lead to less optimal parameters, it turns out to be the only scheme that guarantees convergence when device participation is heterogeneous. Corollary 4.0.1. Table 1 gives the convergence rates of Schemes A, B, and C when device updates may be incomplete. The reason for enlarging the aggregation coefficients in Scheme C can be understood by observing from (2) that increasing p k τ is equivalent to increasing the learning rate of device k. Thus, by assigning devices that run fewer epochs a greater aggregation coefficient, these devices effectively run further in each local step, compensating for the additional epochs other devices completed.

Homogeneous Devices Heterogeneous Devices
Next we consider inactive devices. In the homogeneous setting, inactive devices do not affect the convergence bound in Theorem 3.1, except that in-activeness should be considered when calculating the expectations of s t and its functions. In the heterogeneous setting, the convergence rate for Scheme C includes an offset term that equals O τ −1 t=0 ytD τ E+E 2 . Here y t indicates if there are any inactive devices in round t. This term converges to zero if y t < O(τ ). In other words, a mild degree of device in-activeness will not impede the convergence.
In practice, due to network or battery outage, a device can frequently become inactive. In this case, permanently removing the device may lead to a more accurate model as the training will be guaranteed to converge. Specifically, we will remove the device if doing so will result in a smaller training loss when the training terminates at the deadline T . The decision entails predicting future probability of in-activeness for the target device, and the participation patterns of other devices. Thus, we assume that devices' participation is invariant with time, and that all other devices are active.
With Scheme C, suppose in each round, a device l becomes inactive with probability 0 ≪ y l < 1. Let f 0 (τ ) be the convergence bound if we keep the device, and f 1 (τ ) be the bound if it is removed at τ 0 . For f 0 , with sufficiently more steps, the second term in (3) shrinks to zero, and the first term converges to y l D, so f 0 ≈ y l D. For f 1 , as is discussed in Section 3.4, removing the device is equivalent to initiating a fresh start after the objective shift, hence f 1 (τ ) =Ṽ τ (E(τ −τ0)+γ) 2 for somẽ V τ andγ. The first term on D does not appear in f 1 because other in-activeness were omitted. We thus have the following corollary: If we further assume V τ ≈Ṽ τ = τ V and γ ≈γ (so the departing device does not significantly affect the overall SGD variance and the degree of non-IID), then (6) becomes Note that T E represents the total number of local epochs a device is expected to run in the training. Thus, the more epochs the training runs, the more sensitive it is to the in-activeness.

Departure and Arrival: The Time of Change
As is discussed in Section 3.4, when a device leaves, one can decide to either discard this device and shift the objective, or keep it and stick to the old objective. The decision depends on the time at which the device leaves. When keeping the device, the first term in Theorem 3.1's convergence bound (3) will increase and the second term will decrease. Thus, the convergence bound will first decrease then increase, or strictly increase as the time of departure increases. On the other hand, if the device is discarded, there will be an immediate increase in the convergence bound as in Theorem 3.2. But afterwards, the bound will decrease and eventually the parameters will converge to the new global objective.
Suppose a device leaves at τ 0 < T . Assume there is no in-activeness and no other departing/arriving devices, and suppose devices' participation is invariant with time. Let f 0 (τ ) be the convergence bound if we keep the device, and f 1 (τ ) be the bound if it is discarded. We can obtain f 0 (τ ) = HereM τ ,Ṽ τ ,γ are defined analogously to M τ , V τ , γ but they exclude the departing device. A device is discarded if by doing so, a smaller training loss can be obtained at the deadline T , which is concluded in the following corollary: Further assumeṼ τ = V τ = τ V,γ = γ as in Corollary 4.0.2. (8) can then be written as: From (9), in order to discard the leaving device, the remaining training time T − τ 0 must be at least O( √ τ 0 ). The duration changes with τ 0 because as τ 0 increases, the learning rate without shift gets smaller, mitigating the increase of the training loss from the leaving device.
Since device arrival and departure are symmetric, the same analysis can also be applied to the arriving devices. Thus, we need to guarantee at least O(τ 0 ) of training time in order to admit an arriving device. Solving T − τ 0 = V D τ 0 , the latest time to admit a device is O(T − √ T ).

Conclusion
This paper extends the classic federated learning paradigm to incorporate more flexible device participation patterns. The analysis shows that incomplete local device updates can be utilized by scaling the corresponding aggregation coefficients. Furthermore, a mild degree of device in-activeness will not impact the convergence, but the tolerance to in-activeness diminishes as the training time increases. Finally, the paper provides the number of rounds one must reserve in order to discard a departing device, or admit an arriving device, without impacting model convergence. We plan to empirically validate these results in training on image recognition datasets.
A Proof of Theorem 3.1

A.1 Equivalent View
For ease of the analysis, we introduce for each client k and each global round τ a sequence of virtual variables α k τ E , α k τ E+1 , . . . , α k (τ +1)E−1 . Here each α k t ∈ {0, 1} and E i=0 α k τ E+i = s k τ . If s k τ is a random variable, then α k t 's are also random variables, and the distributions of α k t 's determine the distribution of s k τ . For example, if α k t iid ∼ Bernoulli(p), then s k τ ∼ Bin(E, p). In general, we do not make any assumption on the distributions and correlations of α k t 's. Our results are thus valid for any realization of s k τ . With the definition of α k t 's, we can rewrite (1)(2) as: Note that w g t is visible only when t is a multiple of E. To generalize it to arbitrary t, we definew t such thatw 0 = w g 0 , andw Proof. We will prove by induction. By definition,w 0 = w g 0 . Supposew τ E = w g τ E , then Thus, in the following analysis we will just usew t to denote the global weight.

A.2 Key Lemmas
We first present a couple of important lemmas: Since each client is running independently, the covariance Proof. Note that w k τ E =w τ E for all k.
By the convexity of l 2 norm Plug (34)(35) to (33) Plug (32)(36) to (30) Thus, Thus, Plug (42) to (39) we have Plug (43) to (29), Define Thus, Apply the lemmas we have For convenience we write ∆ τ E+i = w τ E+i − w * 2 , and∆ τ E+i = E[∆ τ E+i ], where the expectation is taken over all random variables up to τ E + i. where We then seek to find a lower bound for ∆ τ E+i .
Define h τ E+i = N k=1 p k τ α k τ E+i g k τ E+i . Thus, Plug (53) to (49) we can get Apply Lemma A.2, Lemma A.3 and Assumption 3.4, we have (p k τ ) 2 s k τ σ 2 k + 2(2 + θ)L Let z τ = 0 indicate the event that for all k, E[p k τ s k τ ] = c τ p k for come constant c τ that does not depend on k, otherwise z k τ = 1. Note that if z τ = 0, then N k=1 p k τ s k τ (F k (w * ) − F k (w τ E+l )) = c τ (F (w * ) − F (w τ E+l )) ≤ 0. Otherwise, we have N k=1 p k τ s k τ (F k (w * ) − F k (w τ E+l )) = N k=1 p k τ s k τ (F k (w * ) − F * k Γ k Put it together N k=1 p k τ s k τ (F k (w * ) − F k (w τ E+l )) ≤ z τ N k=1 p k τ s k τ Γ k (60) Assume η τ ≤ 4 µEθ ≤ 4 µ N k=1 p k τ s k τ , divide both sides with 1 + 1 4 µη τ N k=1 p k τ s k τ in (58) we can get Note that p k τ , s k τ are independent with∆ τ E . Taking expectation over p k τ and s k τ we get A.5 Proof of Theorem 3.1 We prove by induction. Let