Year: 2020

Abstract:
Federated learning is a distributed optimization paradigm that enables a large number of resource-limited client nodes to cooperatively train a model without data sharing. Several works have analyzed the convergence of federated learning by accounting of data heterogeneity, communication and computation limitations, and partial client participation. However, they assume unbiased client participation, where clients are selected at random or in proportion of their data sizes. In this paper, we present the first convergence analysis of federated optimization for biased client selection strategies, and quantify how the selection skew affects convergence speed. We reveal that biasing client selection towards clients with higher local loss achieves faster error convergence. Using this insight, we propose POWER-OF-CHOICE, a communicationand computation-efficient client selection framework that can flexibly span the trade-off between convergence speed and solution bias. We also propose an extension of POWER-OF-CHOICE that is able to maintain convergence speed improvement while diminishing the selection skew. Our experiments demonstrate that POWER-OF-CHOICE strategies can converge up to 3× faster and give 10% higher test accuracy than the baseline random selection.

heading: 1 INTRODUCTION
text: Until recently, machine learning models were largely trained in the data center setting (Dean et al., 2012) using powerful computing nodes, fast inter-node communication links, and large centrally available training datasets. The future of machine learning lies in moving both data collection as well as model training to the edge. The emerging paradigm of federated learning (McMahan et al., 2017; Kairouz et al., 2019; Bonawitz et al., 2019) considers a large number of resource-constrained mobile devices that collect training data from their environment. Due to limited communication capabilities and privacy concerns, these data cannot be directly sent over to the cloud. Instead, the nodes locally perform a few iterations of training using local-update stochastic gradient descent (SGD) (Yu et al., 2018; Stich, 2018; Wang & Joshi, 2018; 2019), and only send model updates periodically to the aggregating cloud server. Besides communication limitations, the key scalability challenge faced by the federated learning framework is that the client nodes can have highly heterogeneous local datasets and computation speeds. The effect of data heterogeneity on the convergence of local-update SGD is analyzed in several recent works (Reddi et al., 2020; Haddadpour & Mahdavi, 2019; Khaled et al., 2020; Stich & Karimireddy, 2019; Woodworth et al., 2020; Koloskova et al., 2020; Huo et al., 2020; Zhang et al., 2020; Pathak & Wainwright, 2020; Malinovsky et al., 2020; Sahu et al., 2019) and methods to overcome the adverse effects of data and computational heterogeneity are proposed in (Sahu et al., 2019; Wang et al., 2020; Karimireddy et al., 2019), among others.
Partial Client Participation. Most of the recent works described above assume full client participation, that is, all nodes participate in every training round. In practice, only a small fraction of client nodes participate in each training round, which can exacerbate the adverse effects of data heterogeneity. While some existing convergence guarantees for full client participation and methods to tackle heterogeneity can be generalized to partial client participation (Li et al., 2020), these generalizations are limited to unbiased client participation, where each client’s contribution to the expected global objective optimized in each round is proportional to its dataset size. In Ruan et al. (2020), the authors analyze the convergence with flexible device participation, where devices can freely join or leave the
training process or send incomplete updates to the server. However, adaptive client selection that is cognizant of the training progress at each client has not been understood yet.
It is important to analyze and understand biased client selection strategies since they can sharply accelerate error convergence, and hence boost communication efficiency in heterogeneous environments by preferentially selecting clients with higher local loss values, as we show in our paper. This idea has been explored in recent empirical studies (Goetz et al., 2019; Laguel et al., 2020; Ribero & Vikalo, 2020). Nishio & Yonetani (2019) proposed grouping clients based on hardware and wireless resources in order to save communication resources. Goetz et al. (2019) (which we include as a benchmark in our experiments) proposed client selection with local loss, and Ribero & Vikalo (2020) proposed utilizing the progression of clients’ weights. But these schemes are limited to empirical demonstration without a rigorous analysis of how selection skew affects convergence speed.
Another relevant line of work (Jiang et al., 2019; Katharopoulos & Fleuret, 2018; Shah et al., 2020; Salehi et al., 2018) employs biased selection or importance sampling of data to speed-up convergence of classic centralized SGD – they propose preferentially selecting samples with highest loss or highest gradient norm to perform the next SGD iteration. In contrast, Shah et al. (2020) proposes biased selection of lower loss samples to improve robustness to outliers. Generalizing such strategies to the federated learning setting is a non-trivial and open problem because of the large-scale distributed and heterogeneous nature of the training data.
Our Contributions. In this paper, we present the first (to the best of our knowledge) convergence analysis of federated learning with biased client selection that is cognizant of the training progress at each client. We discover that biasing the client selection towards clients with higher local losses increases the rate of convergence compared to unbiased client selection. Using this insight, we propose the POWER-OF-CHOICE client selection strategy and show by extensive experiments that POWER-OF-CHOICE yields up to 3× faster convergence with 10% higher test performance than the standard federated averaging with random selection. POWER-OF-CHOICE is designed to incur minimal communication and computation overhead, enhancing resource efficiency in federated learning. In fact, we show that even with 3× less clients participating in each round as compared to random selection, POWER-OF-CHOICE gives 2× faster convergence and 5% higher test accuracy.

heading: 2 PROBLEM FORMULATION
text: Consider a cross-device federated learning setup with total K clients, where client k has a local dataset Bk consisting |Bk| = Dk data samples. The clients are connected via a central aggregating server, and seek to collectively find the model parameter w that minimizes the empirical risk:
F (w) = 1∑K
k=1Dk K∑ k=1 ∑ ξ∈Bk f(w, ξ) = K∑ k=1 pkFk(w) (1)
where f(w, ξ) is the composite loss function for sample ξ and parameter vector w. The term pk = Dk/ ∑K k=1Dk is the fraction of data at the k-th client, and Fk(w) = 1 |Bk| ∑ ξ∈Bk f(w, ξ) is the local objective function of client k. In federated learning, the vectors w∗, and w∗k for k = 1, . . . ,K that minimize F (w) and Fk(w) respectively can be very different from each other. We define F ∗ = minw F (w) = F (w∗) and F ∗k = minw Fk(w) = Fk(w ∗ k).
Federated Averaging with Partial Client Participation. The most common algorithm to solve (1) is federated averaging (FedAvg) proposed in McMahan et al. (2017). The algorithm divides the training into communication rounds. At each round, to save communication cost at the central server, the global server only selects a fraction C of m = CK clients to participate in the training. Each selected/active client performs τ iterations of local SGD (Stich, 2018; Wang & Joshi, 2018; Yu et al., 2018) and sends its locally updated model back to the server. Then, the server updates the global model using the local models and broadcasts the global model to a new set of active clients.
Formally, we index the local SGD iterations with t ≥ 0. The set of active clients at iteration t is denoted by S(t). Since active clients performs τ steps of local update, the active set S(t) also remains constant for every τ iterations. That is, if (t+ 1) mod τ = 0, then S(t+1) = S(t+2) = · · · = S(t+τ).
Accordingly, the update rule of FedAvg can be written as follows:
w (t+1) k =
{ w
(t) k − ηtgk(w (t) k , ξ (t) k ) for (t+ 1) mod τ 6= 0
1 m ∑ j∈S(t) ( w (t) j − ηtgj(w (t) j , ξ (t) j ) ) , w(t+1) for (t+ 1) mod τ = 0 (2)
where w(t+1)k denotes the local model parameters of client k at iteration t, ηt is the learning rate, and gk(w (t) k , ξ (t) k ) = 1 b ∑ ξ∈ξ(t)k ∇f(w(t)k , ξ) is the stochastic gradient over mini-batch ξ (t) k of size b that is randomly sampled from client k’s local dataset Bk. Moreover, w(t+1) denotes the global model at server. Although w(t) is only updated after every τ iterations, for the purpose of convergence analysis we consider a virtual sequence of w(t) that is updated at each iteration as follows
w(t+1) = w(t) − ηtg(t) = w(t) − ηt  1 m ∑ k∈S(t) gk(w (t) k , ξ (t) k )  (3) with g(t) = 1m ∑ k∈S(t) gk(w (t) k , ξ (t) k ). Note that in (2) and (3) we do not weight the client models by their dataset fractions pk because pk is considered in the client selection scheme used to decide the set S(t). Our convergence analysis can be generalized to when the global model is a weighted average instead of a simple average of client models, and we show in Appendix E that our convergence analysis also covers the sampling uniformly at random without replacement scheme proposed by Li et al. (2020). The set S(t) can be sampled either with or without replacement. For sampling with replacement, we assume that multiple copies of the same client in the set S(t) behave as different clients, that is, they perform local updates independently.
Client Selection Strategy. To guarantee FedAvg converges to the stationary points of the objective function (1), most current analysis frameworks (Li et al., 2020; Karimireddy et al., 2019; Wang et al., 2020) consider a strategy that selects the set S(t) by sampling m clients at random (with replacement) such that client k is selected with probability pk, the fraction of data at that client. This sampling scheme is unbiased since it ensures that in expectation, the update rule (3) is the same as full client participation. Hence, it enjoys the same convergence properties as local-update SGD methods (Stich, 2018; Wang & Joshi, 2018). We denote this unbiased random client selection strategy as πrand.
In this paper, we consider a class of biased client selection strategies that is cognizant of the global training progress which (to the best of our knowledge) has not been worked on before. Note that for any aggregation scheme and sampling scheme with partial client participation, if the expectation over the sampling scheme for the update rule of the global model is equal to the case of the update rule for full client participation, we distinguish this as an unbiased client participation scheme. For example in Horváth & Richtárik (2020), even with a biased sampling scheme, with the normalizing aggregation
the update rule is unbiased. Henceforth, we state that our paper encompasses both biased and unbiased update rules. In the two-client example in Figure 1, we set S(t+1) = arg maxk∈[K] Fk(w(t)), a single client with the highest local loss at the current global model. In this toy example, the selection strategy cannot guarantee the updates (3) equals to the full client participation case in expectation. Nevertheless, it gives faster convergence to the global minimum than the random one. Motivated by this observation, we define a client selection strategy π as a function that maps the current global model w to a selected set of clients S(π,w).

heading: 3 CONVERGENCE ANALYSIS
text: In this section we analyze the convergence of federated averaging with partial device participation for any client selection strategy π as defined above. This analysis reveals that biased client selection can give faster convergence, albeit at the risk of having a non-vanishing gap between the true optimum w∗ = arg minF (w) and limt→∞w(t). We use this insight in Section 4 to design client selection strategies that strike a balance between convergence speed and bias.

heading: 3.1 ASSUMPTIONS AND DEFINITIONS
text: First we introduce the assumptions and definitions utilized for our convergence analysis.
Assumption 3.1. F1, ..., Fk are all L−smooth, i.e., for all v and w, Fk(v) ≤ Fk(w) + (v − w)T∇Fk(w) + L2 ‖v −w‖ 2 2. Assumption 3.2. F1, ..., Fk are all µ−strongly convex, i.e., for all v and w, Fk(v) ≥ Fk(w) + (v −w)T∇Fk(w) + µ2 ‖v −w‖ 2 2. Assumption 3.3. For the mini-batch ξk uniformly sampled at random from Bk from user k, the resulting stochastic gradient is unbiased, that is, E[gk(wk, ξk)] = ∇Fk(wk). Also, the variance of stochastic gradients is bounded: E‖gk(wk, ξk)−∇Fk(wk)‖2 ≤ σ2 for all k = 1, ...,K. Assumption 3.4. The stochastic gradient’s expected squared norm is uniformly bounded, i.e., E‖gk(wk, ξk)‖2 ≤ G2 for k = 1, ...,K.
The above assumptions are common in related literature, see (Stich, 2018; Basu et al., 2019; Li et al., 2020; Ruan et al., 2020). Next, we introduce two metrics, the local-global objective gap and the selection skew, which feature prominently in the convergence analysis presented in Theorem 3.1.
Definition 3.1 (Local-Global Objective Gap). For the global optimum w∗ = arg minw F (w) and local optimum w∗k = arg minw Fk(w) we define the local-global objective gap as
Γ , F ∗ − K∑ k=1 pkF ∗ k = K∑ k=1 pk(Fk(w ∗)− Fk(w∗k)) ≥ 0. (4)
Note that Γ is an inherent property of the local and global objective functions, and it is independent of the client selection strategy. This definition was introduced in previous literature by Li et al. (2020). A larger Γ implies higher data heterogeneity. If Γ = 0 then it implies that the local and global optimal values are consistent, and there is no solution bias due to the client selection strategy (see Theorem 3.1). Next, we define another metric called selection skew, which captures the effect of the client selection strategy on the local-global objective gap.
Definition 3.2 (Selection Skew). For any k ∈ S(π,w) we define,
ρ(S(π,w),w′) = ES(π,w)[ 1m
∑ k∈S(π,w)(Fk(w ′)− F ∗k )]
F (w′)− ∑K k=1 pkF ∗ k
≥ 0, (5)
which reflects the skew of a client selection strategy π. The first w in ρ(S(π,w),w′) is the parameter vector that governs the client selection and w′ is the point at which Fk and F in the numerator and denominator respectively are evaluated. Note, ES(π,w)[·] is the expectation over the randomness from the selection strategy π, since there can be multiple sets S that π can map from a specific w.
Since ρ(S(π,w),w′) is a function of versions of the global model w and w′, which change during training, we define two related metrics that are independent of w and w′. These metrics enable us to obtain a conservative error bound in the convergence analysis.
ρ , min w,w′ ρ(S(π,w),w′), ρ̃ , max w ρ(S(π,w),w∗) (6)
where w∗ = arg minw F (w). From (6), we have ρ ≤ ρ̃ for any client selection strategy π.
Effect of the Client Selection Strategy on ρ and ρ̃. For the unbiased client selection strategy πrand we have ρ(S(πrand,w),w′) = 1 for all w and w′ since the numerator and denominator of (5) become equal, and ρ = ρ̃ = 1. For a client selection strategy π that chooses clients with higher Fk(w) more often, ρ and ρ̃ will be larger (and ≥ 1). In the convergence analysis we show that a larger ρ implies faster convergence, albeit with a potential error gap, which is proportional to (ρ̃/ρ− 1). Motivated by this, in Section 4 we present an adaptive client selection strategy that prefers selecting clients with higher loss Fk(w) and achieves faster convergence speed with low solution bias.

heading: 3.2 MAIN CONVERGENCE RESULT
text: Here, we present the convergence results for any client selection strategy π for federated averaging with partial device participation in terms of local-global objective gap Γ, and selection skew ρ, ρ̃.
Theorem 3.1 (Convergence with Decaying Learning Rate). Under Assumptions 3.1 to 3.4, for learning rate ηt = 1µ(t+γ) with γ = 4L µ , and any client selection strategy π, the error after T iterations of federated averaging with partial device participation satisfies
E[F (w(T ))]− F ∗ ≤
1
(T + γ)
[ 4L(32τ2G2 + σ2/m)
3µ2ρ +
8L2Γ µ2 + Lγ‖w(0) −w∗‖2 2 ] ︸ ︷︷ ︸
Vanishing Error Term
+ 8LΓ
3µ
( ρ̃ ρ − 1 )
︸ ︷︷ ︸ Non-vanishing bias,Q(ρ,ρ̃) (7)
To the best of our knowledge, Theorem 3.1 provides the first convergence analysis of federated averaging with a biased client selection strategy π. We also show the results for fixed learning rate in Appendix A. The proof is presented in Appendix C. The first part of our proof follows techniques presented by Li et al. (2020). Then we introduce the novel concept of selection skew to the proof, and analyze the effect of biased client selection strategies that has not been seen before in previous literature. We highlight that our convergence result is a general analysis that is applicable for any selection strategy π that is cognizant of the training progress. In the following paragraphs, we discuss the effects of the two terms in (7) in detail.
Large ρ and Faster Convergence. A key insight from Theorem 3.1 is that a larger selection skew ρ results in faster convergence at the rate O( 1Tρ ). Note that since we obtain ρ (defined in (6)) by taking a minimum of the selection skew ρ(S(π,w),w′) over w,w′, this is a conservative bound on the true convergence rate. In practice, since the selection skew ρ(S(π,w),w′) changes during training depending on the current global model w and the local models w′, the true convergence rate can be improved by a factor larger than and at least equal to ρ.
Non-vanishing Bias Term. The second term Q(ρ, ρ̃) = 8LΓ3µ ( ρ̃ ρ − 1 ) in (7) denotes the solution bias, which is dependent on the selection strategy. By the definitions of ρ and ρ̃, it follows that ρ̃ ≥ ρ, which implies that Q(ρ, ρ̃) ≥ 0. For an unbiased selection strategy, we have ρ = ρ̃ = 1, Q(ρ, ρ̃) = 0, and hence (7) recovers previous bound for unbiased selection strategy as (Li et al., 2020). For ρ > 1, while we gain faster convergence rate by a factor of ρ, we cannot guarantee Q(ρ, ρ̃) = 0. Thus, there is a trade-off between the convergence speed and the solution bias. Later in the experimental results, we show that even with biased selection strategies, the term ρ̃ρ − 1 in Q(ρ, ρ̃) can be close to 0, and hence Q(ρ, ρ̃) has a negligible effect on the final error floor.

heading: 4 PROPOSED POWER-OF-CHOICE CLIENT SELECTION STRATEGY
text: From (5) and (6) we discover that a selection strategy π that prefers clients with larger Fk(w)− F ∗k will result in a larger ρ, yielding faster convergence. Using this insight, a naive client selection strategy can be choosing the clients with highest local loss Fk(w). However, a larger selection skew ρ may result in a larger ρ/ρ̃, i.e., a larger non-vanishing error term. This naive selection strategy has another drawback – to find the current local loss Fk(w), it requires sending the current global model to all K clients and having them evaluate Fk and sending it back. This additional communication and computation cost can be prohibitively high because the number of clients K is typically very large, and these clients have limited communication and computation capabilities.
In this section, we use these insights regarding the trade-off between convergence speed, solution bias and communication/computation overhead to propose the POWER-OF-CHOICE client selection strategy. POWER-OF-CHOICE is based on the power of d choices load balancing strategy (Mitzenmacher, 1996), which is extensively used in queueing systems. In the POWER-OF-CHOICE client selection strategy (denoted by πpow-d), the central server chooses the active client set S(t) as follows:
1. Sample the Candidate Client Set. The central server samples a candidate set A of d (m ≤ d ≤ K) clients without replacement such that client k is chosen with probability pk, the fraction of data at the k-th client for k = 1, . . .K.
2. Estimate Local Losses. The server sends the current global model w(t) to the clients in set A, and these clients compute and send back to the central server their local loss Fk(w(t)).
3. Select Highest Loss Clients. From the candidate set A, the central server constructs the active client set S(t) by selecting m = max(CK, 1) clients with the largest values Fk(w), with ties broken at random. These S(t) clients participate in the training during the next round, consisting of iterations t+ 1, t+ 2, . . . t+ τ .
Variations of πpow-d. The three steps of πpow-d can be flexibly modified to take into account practical considerations. For example, intermittent client availability can be accounted for in step 1 by constructing set A only from the set of available clients in that round. We demonstrate the performance of πpow-d with intermittent client availability in Appendix G.3. The local computation cost and server-client communication cost in step 2 can be reduced or eliminated by the following proposed variants of πpow-d (see Appendix F for their pseudo-codes).
• Computation-efficient Variant πcpow-d: To save local computation cost, instead of evaluating the Fk(w) by going through the entire local dataset Bk, we use an estimate ∑ ξ∈ξ̂k f(w, ξ)/|ξ̂k|,
where ξ̂k is the mini-batch of b samples sampled uniformly at random from Bk. • Communication- and Computation-efficient Variant πrpow-d: To save both local computation
and communication cost, the selected clients for each round sends their accumulated averaged loss over local iterations, i.e., 1 τ |ξ(l)k | ∑t l=t−τ+1 ∑ ξ∈ξ(l)k f(w (l) k , ξ) when they send their local models to the server. The server uses the latest received value from each client as a proxy for Fk(w) to select the clients. For the clients that have not been selected yet, the latest value is set to∞.
• Adaptive Selection Skew Variant πadapow-d: To minimize the non-vanishing bias term in Theorem 3.1 while simultaneously gaining the benefit of convergence speed from ρ, we gradually reduce d until d = m1. This enables convergence speed up in the initial training phase, while eventually diminishing the non-vanishing bias term when d = m. Which d to start with and how gradually we decrease d to m is flexible, analogous to setting the environment and hyper-parameters.
Selection Skew of POWER-OF-CHOICE Strategy. The size d of the candidate client set A is an important parameter which controls the trade-off between convergence speed and solution bias. With d = m we have random sampling without replacement in proportion of pk. As d increases, the selection skew ρ increases, giving faster error convergence at the risk of a higher error floor. However, note that the convergence analysis replaces ρ(w,w′) with ρ to get a conservative error bound. In
1d = m makes our proposed POWER-OF-CHOICE strategy to become analogous to an unbiased sampling strategy, which has no non-vanishing bias term.
practice, the convergence speed and the solution bias is dictated by ρ(w(τbt/τc),w(t)) which changes during training. With πpow-d which is biased towards higher local losses, we expect the selection skew ρ(w,w′) to reduce through the course of training. We conjecture that this is why πpow-d gives faster convergence as well as little or no solution bias in our experiments presented in Section 5.

heading: 5 EXPERIMENTAL RESULTS
text: We evaluate our proposed πpow-d and its practical variants πcpow-d, πrpow-d, and πadapow-d by three sets of experiments: (1) quadratic optimization, (2) logistic regression on a synthetic federated dataset, Synthetic(1,1) (Sahu et al., 2019), and (3) DNN trained on a non-iid partitioned FMNIST dataset (Xiao et al., 2017). We also benchmark the selection strategy proposed by Goetz et al. (2019), active federated learning, denoted as πafl. Details of the experimental setup are provided in Appendix F, and the code for all experiments are shared in the supplementary material. To validate consistency in our results, we present additional experiments with DNN trained on a non-iid partitioned EMNIST (Cohen et al., 2017) dataset sorted by digits with K = 500 clients. We present the results in Appendix G.4.
Quadratic and Synthetic Simulation Results. In Figure 2(a), even with few clients (K = 30), πpow-d converges faster than πrand with nearly negligible solution bias for small d. The convergence speed increases with the increase in d, at the cost of higher error floor due to the solution bias. For K = 100 in Figure 2(b), πpow-d shows convergence speed-up as with K = 30, but the bias is smaller. Figure 3 shows the theoretical values ρ and ρ̃/ρ which represents the convergence speed and the solution bias respectively in our convergence analysis. Compared to πrand, πpow-d has higher ρ for all d implying higher convergence speed than πrand. By varying d we can span different points on the trade-off between the convergence speed and bias. For d = 15 and K = 100, ρ̃/ρ of πpow-d and πrand are approximately identical, but πpow-d has higher ρ, implying that πpow-d can yield higher convergence speed with negligible solution bias. In Appendix G.1, we present
the clients’ selected frequency ratio for πpow-d and πrand which gives novel insights regarding the difference between the two strategies. For the synthetic dataset simulations, we present the global losses in Figure 4 for πrand and πpow-d for different d and m. We show that πpow-d converges approximately 3× faster to the global loss ≈ 0.7 than πrand when d = 10m, with a slightly higher error floor. Even with d = 2m, we get 2× faster convergence to global loss ≈ 0.7 than πrand. Elimination of Selection Skew with πadapow-d. For πpow-d, the selection skew is the trade-off for the convergence speed gain in Figure 2 and Figure 4. For both simulations, πpow-d converges slightly above the global minimum value due to the selection skew. We eliminate this selection skew while maintaining the benefit of convergence speed with πadapow-d. In Figure 2(a)-(b), πadapow-d shows a
convergence speed similar to πpow-d, d = K, but has no selection skew, converging to the same minimum as πrand (see Figure 2(c)). In Figure 4, πadapow-d again shows a convergence speed similar to πpow-d, d = 10m, but has no adversarial selection skew. As a matter of fact, πadapow-d converges to the minimum global loss value at least 3 × faster than πrand. Hence πadapow-d gains the benefit of both worlds from biased client selection: convergence speed and elimination of selection skew.
Experiments with Heterogeneously Distributed FMNIST. As elaborated in Appendix F, α determines the data heterogeneity across clients. Smaller α indicates larger data heterogeneity. In Figure 5, we present the test accuracy and training losses for the different sampling strategies from the FMNIST experiments with α = 0.3 and α = 2. Observe that πpow-d achieves approximately 10% and 5% higher test accuracy than πrand and πafl respectively for both α = 2 and α = 0.3. For higher α (less data heterogeneity) larger d (more selection skew) performs better than smaller d.
Figure 5(a) shows that this performance improvement due to the increase of d eventually converges. For smaller α, as in Figure 5(b), smaller d = 6 performs better than larger d which shows that too much solution bias is adversarial to the performance in the presence of large data heterogeneity. The observations on training loss are consistent with the test accuracy results.
Performance of the Communication- and Computation-Efficient variants. Next, we evaluate πcpow-d and πrpow-d which were introduced in Section 4. In Figure 6, for α = 2, πrpow-d and πcpow-d each yields approximately 5% and 6% higher accuracy than πrand, but both yield lower accuracy than πpow-d that utilizes the highest computation and communication resources. For α = 0.3, πcpow-d and πrpow-d perform as well as πpow-d and give a 10% accuracy improvement over πrand. Moreover, πpow-d, πrpow-d and πcpow-d all have higher accuracy and faster convergence than πafl.
We evaluate the communication and computation efficiency of POWER-OF-CHOICE by comparing different strategies in terms of R60, the number of communication rounds required to reach test accuracy 60%, and tcomp, the average computation time (in seconds) spent per round. The computation time includes the the time taken by the central server to select the clients (including the computation
time for the d clients to compute their local loss values) and the time taken by selected clients to perform local updates. In Table 1, with only C = 0.03 fraction of clients, πpow-d, πcpow-d, and πrpow-d have about 5% higher test accuracy than (πrand, C = 0.1). The R60 for πpow-d, πcpow-d, πrpow-d is 0.52, 0.47, 0.57 times that of (πrand, C = 0.1) respectively. This implies that even for πrpow-d which does not incur any additional communication cost for client selection, we can get a 2× reduction in the number of communication rounds using 1/3 of clients compared to (πrand, C = 0.1) and still get higher test accuracy performance. Note that the computation time tcomp for πcpow-d and πrpow-d with C = 0.03 is smaller than that of πrand with C = 0.1. In Appendix G.2, we show that the results for α = 2 are consistent with the α = 0.3 case shown in Table 1. In Appendix G.5, we also show that for C = 0.1, the results are consistent with the C = 0.03 case.
Effect of Mini-batch Size and Local Epochs. We evaluate the effect of mini-batch size b and local epochs τ on the FMNIST experiments with different sets of hyper-parameters: (b, τ) ∈ {(128, 30), (64, 100)}. Note that (b, τ) = (64, 30) is the default hyper-parameter setting for the previous results. The figures are presented in Appendix G.6. For b = 128, we observe that the performance improvement of πpow-d over πrand and πafl is consistent with b = 64 (see Figure 12). In Figure 14, for τ = 100, with smaller data heterogeneity, the performance gap between πrand and πpow-d is consistent with that of τ = 30. For larger data heterogeneity, however, increasing the local epochs results in πrand and πpow-d performing similarly. This shows that with larger data heterogeneity, larger τ results in increasing the selection skew towards specific clients, and weakens generalization.

heading: 6 CONCLUDING REMARKS
text: In this work, we present the convergence guarantees for federated learning with partial device participation with any biased client selection strategy. We discover that biasing client selection can speed up the convergence at the rate O( 1Tρ ) where ρ is the selection skew towards clients with higher local losses. Motivated by this insight, we propose the adaptive client selection strategy POWER-OF-CHOICE. Extensive experiments validate that POWER-OF-CHOICE yields 3× faster convergence and 10% higher test accuracy than the baseline federated averaging with random selection. Even with using fewer clients than random selection, POWER-OF-CHOICE converges 2 × faster with high test performance. An interesting future direction is to improve the fairness (Li et al., 2019; Yu et al., 2020; Lyu et al., 2020; Mohri et al., 2019) and robustness (Pillutla et al., 2019) of the POWER-OF-CHOICE strategy by modifying step 3 of the POWER-OF-CHOICE algorithm to use a different metric such as the clipped loss or the q-fair loss proposed Li et al. (2019) instead of Fk(w).

heading: A ADDITIONAL THEOREM
text: Theorem A.1 (Convergence with Fixed Learning Rate). Under Assumptions 3.1 to 3.4, a fixed learning rate η ≤ min{ 12µB , 1 4L} where B = 1 + 3ρ 8 , and any client selection strategy π as defined above, the error after T iterations of federated averaging with partial device participation satisfies
F (w(T ))− F ∗
≤ L µ
[ 1− ηµ ( 1 + 3ρ
8
)]T F (w(0))− F ∗ − 4 [ η ( 32τ2G2 + σ 2 m + 6ρLΓ ) + 2Γ(ρ̃− ρ) ]
8 + 3ρ  ︸ ︷︷ ︸
Vanishing Term
+ 4Lη
( 32τ2G2 + σ 2 m + 6ρLΓ )
µ(8 + 3ρ) + 8LΓ(ρ̃− ρ) µ(8 + 3ρ)︸ ︷︷ ︸
Non-vanishing bias
(8)
As T → ∞ the first term in (8) goes to 0 and the second term becomes the bias term for the fixed learning rate case. For a small η, we have that the bias term for the fixed learning rate case in Theorem A.1 is upper bounded by 8LΓ3µ ( ρ̃ ρ − 1 ) which is identical to the decaying-learning rate case. The proof is presented in Appendix D.

heading: B PRELIMINARIES FOR PROOF OF THEOREM 3.1 AND THEOREM A.1
text: We present the preliminary lemmas used for proof of Theorem 3.1 and Theorem A.1. We will denote the expectation over the sampling random source S(t) as ES(t) and the expectation over all the random sources as E. Lemma B.1. Suppose Fk is L−smooth with global minimum at w∗k, then for any wk in the domain of Fk, we have that
‖∇Fk(wk)‖2 ≤ 2L(Fk(wk)− Fk(w∗k)) (9)

heading: Proof.
text: Fk(wk)− Fk(w∗k)− 〈∇Fk(w∗k),wk −w∗k〉 ≥ 1 2L ‖∇Fk(wk)−∇Fk(w∗k)‖2 (10)
Fk(wk)− Fk(w∗k) ≥ 1
2L ‖∇Fk(wk)‖2 (11)
Lemma B.2 (Expected average discrepancy between w(t) and w(t)k for k ∈ S(t)). 1 m E[ ∑ k∈S(t) ‖w(t) −w(t)k ‖ 2] ≤ 16η2t τ2G2 (12)
Proof.
1
m ∑ k∈S(t) ‖w(t) −w(t)k ‖ 2 = 1 m ∑ k∈S(t) ‖ 1 m ∑ k′∈S(t) (w (t) k′ −w (t) k )‖ 2 (13)
≤ 1 m2 ∑ k∈S(t) ∑ k′∈S(t) ‖w(t)k′ −w (t) k ‖ 2 (14)
= 1
m2 ∑ k 6=k′,
k,k′∈S(t)
‖w(t)k′ −w (t) k ‖ 2 (15)
Observe from the update rule that k, k′ are in the same set S(t) and hence the terms where k = k′ in the summation in (14) will be zero resulting in (15). Moreover for any arbitrary t there is a t0 such that 0 ≤ t− t0 < τ that w(t0)k′ = w (t0) k since the selected clients are updated with the global model at every τ . Hence even for an arbitrary t we have that the difference between ‖w(t)k′ −w (t) k ‖2 is upper bounded by τ updates. With non-increasing ηt over t and ηt0 ≤ 2ηt, (15) can be further bounded as,
1
m2 ∑ k 6=k′,
k,k′∈S(t)
‖w(t)k′ −w (t) k ‖ 2 ≤ 1 m2 ∑ k 6=k′,
k,k′∈S(t)
‖ t0+τ−1∑ i=t0 ηi(gk′(w (i) k′ , ξ (i) k′ )− gk(w (i) k , ξ (i) k ))‖ 2 (16)
≤ η2t0τ
m2 ∑ k 6=k′,
k,k′∈S(t)
t0+τ−1∑ i=t0 ‖(gk′(w(i)k′ , ξ (i) k′ )− gk(w (i) k , ξ (i) k ))‖ 2 (17)
≤ η2t0τ
m2 ∑ k 6=k′,
k,k′∈S(t)
t0+τ−1∑ i=t0 [2‖gk′(w(i)k′ , ξ (i) k′ )‖ 2 + 2‖gk(w(i)k , ξ (i) k )‖ 2] (18)
By taking expectation over (18),
E[ 1
m2 ∑ k 6=k′,
k,k′∈S(t)
‖w(t)k′ −w (t) k ‖
2] ≤ 2η2t0τ
m2 E[ ∑ k 6=k′,
k,k′∈S(t)
t0+τ−1∑ i=t0 (‖gk′(w(i)k′ , ξ (i) k′ )‖ 2 + ‖gk(w(i)k , ξ (i) k )‖ 2)]
(19)
≤ 2η2t0τ
m2 ES(t) [ ∑ k 6=k′,
k,k′∈S(t)
t0+τ−1∑ i=t0 2G2] (20)
= 2η2t0τ
m2 ES(t) [ ∑ k 6=k′,
k,k′∈S(t)
2τG2] (21)
≤ 16η 2 t (m− 1)τ2G2
m (22)
≤ 16η2t τ2G2 (23)
where (22) is because there can be at most m(m− 1) pairs such that k 6= k′ in S(t).
Lemma B.3 (Upper bound for expectation over ‖w(t)−w∗‖2 for any selection strategy π). With E[·], the total expectation over all random sources including the random source from selection strategy we have the upper bound:
E[‖w(t) −w∗‖2] ≤ 1 m E[ ∑ k∈S(t) ‖w(t)k −w ∗‖2] (24)

heading: Proof.
text: E[‖w(t) −w∗‖2] = E[‖ 1 m ∑ k∈S(t) w (t) k −w ∗‖2] = E[‖ 1 m ∑ k∈S(t) (w (t) k −w ∗)‖2] (25)
≤ 1 m E[ ∑ k∈S(t) ‖w(t)k −w ∗‖2] (26)

heading: C PROOF OF THEOREM 3.1
text: With g(t) = 1m ∑ k∈S(t) gk(w (t) k , ξ (t) k ) as defined in Section 2, we have that
‖w(t+1) −w∗‖2 =‖w(t) − ηtg(t) −w∗‖2 (27)
=‖w(t) − ηtg(t) −w∗ − ηt m ∑ k∈S(t) ∇Fk(w(t)k ) + ηt m ∑ k∈S(t) ∇Fk(w(t)k )‖ 2 (28)
=‖w(t) −w∗ − ηt m ∑ k∈S(t) ∇Fk(w(t)k )‖ 2 + η2t ‖ 1 m ∑ k∈S(t) ∇Fk(w(t)k )− g (t)‖2
+ 2ηt〈w(t) −w∗ − ηt m ∑ k∈S(t) ∇Fk(w(t)k ), 1 m ∑ k∈S(t) ∇Fk(w(t)k )− g (t)〉 (29)
=‖w(t) −w∗‖2−2ηt〈w(t) −w∗, 1
m ∑ k∈S(t)
∇Fk(w(t)k )〉︸ ︷︷ ︸ A1
+ 2ηt〈w(t) −w∗ − ηt m ∑ k∈S(t) ∇Fk(w(t)k ), 1 m ∑ k∈S(t) ∇Fk(w(t)k )− g (t)〉
︸ ︷︷ ︸ A2
+ η2t ‖ 1
m ∑ k∈S(t) ∇Fk(w(t)k )‖ 2
︸ ︷︷ ︸ A3
+ η2t ‖ 1
m ∑ k∈S(t) ∇Fk(w(t)k )− g (t)‖2
︸ ︷︷ ︸ A4
(30)
First let’s bound A1.
− 2ηt〈w(t) −w∗, 1
m ∑ k∈S(t) ∇Fk(w(t)k )〉 = − 2ηt m ∑ k∈S(t) 〈w(t) −w∗,∇Fk(w(t)k )〉 (31)
= −2ηt m ∑ k∈S(t) 〈w(t) −w(t)k ,∇Fk(w (t) k )〉 − 2ηt m ∑ k∈S(t) 〈w(t)k −w ∗,∇Fk(w(t)k )〉 (32)
≤ ηt m ∑ k∈S(t) ( 1 ηt ‖w(t) −w(t)k ‖ 2 + ηt‖∇Fk(w(t)k )‖ 2 ) − 2ηt m ∑ k∈S(t) 〈w(t)k −w ∗,∇Fk(w(t)k )〉
(33)
= 1
m ∑ k∈S(t) ‖w(t) −w(t)k ‖ 2 + η2t m ∑ k∈S(t) ‖∇Fk(w(t)k )‖ 2 − 2ηt m ∑ k∈S(t) 〈w(t)k −w ∗,∇Fk(w(t)k )〉
(34)
≤ 1 m ∑ k∈S(t) ‖w(t) −w(t)k ‖ 2 + 2Lη2t m ∑ k∈S(t) (Fk(w (t) k )− F ∗ k )
−2ηt m ∑ k∈S(t) 〈w(t)k −w ∗,∇Fk(w(t)k )〉
(35)
≤ 1 m ∑ k∈S(t) ‖w(t) −w(t)k ‖ 2 + 2Lη2t m ∑ k∈S(t) (Fk(w (t) k )− F ∗ k )
−2ηt m ∑ k∈S(t) [ (Fk(w (t) k )− Fk(w ∗)) + µ 2 ‖w(t)k −w ∗‖2 ] (36)
≤ 16η2t τ2G2 − ηtµ
m ∑ k∈S(t) ‖w(t)k −w ∗‖2 + 2Lη 2 t m ∑ k∈S(t) (Fk(w (t) k )− F ∗ k )
−2ηt m ∑ k∈S(t) (Fk(w (t) k )− Fk(w ∗)) (37)
where (33) is due to the AM-GM inequality and Cauchy–Schwarz inequality, (35) is due to Lemma B.1, (36) is due to the µ-convexity of Fk, and (37) is due to Lemma B.2. Next, in expectation, E[A2] = 0 due to the unbiased gradient. Next again with Lemma B.1 we bound A3 as follows:
η2t ‖ 1
m ∑ k∈S(t) ∇Fk(w(t)k )‖ 2 = η2t m ∑ k∈S(t) ∥∥∥∇Fk(w(t)k )∥∥∥2 (38) ≤ 2Lη 2 t
m ∑ k∈S(t) (Fk(w (t) k )− F ∗ k ) (39)
Lastly we can bound A4 using the bound of variance of stochastic gradients as,
E[η2t ‖ 1
m ∑ k∈S(t) ∇Fk(w(t)k )− g (t)‖2] = η2tE[‖ ∑ k∈S(t) 1 m (gk(w (t) k , ξ (t) k )−∇Fk(w (t) k ))‖ 2] (40)
= η2t m2 ES(t) [ ∑ k∈S(t) E‖gk(w(t)k , ξ (t) k )−∇Fk(w (t) k )‖ 2] (41)
≤ η 2 t σ 2
m (42)
Using the bounds ofA1, A2, A3, A4 above we have that the expectation of the LHS of (27) is bounded as
E[‖w(t+1) −w∗‖2]
≤E[‖w(t) −w∗‖2]− ηtµ m E[ ∑ k∈S(t) ‖w(t)k −w ∗‖2] + 16η2t τ2G2
+ η2t σ 2
m + 4Lη2t m E[ ∑ k∈S(t) (Fk(w (t) k )− F ∗ k )]− 2ηt m E[ ∑ k∈S(t) (Fk(w (t) k )− Fk(w ∗))] (43)
≤(1− ηtµ)E[‖w(t) −w∗‖2] + 16η2t τ2G2
+ η2t σ 2
m + 4Lη2t m E[ ∑ k∈S(t) (Fk(w (t) k )− F ∗ k )]− 2ηt m E[ ∑ k∈S(t) (Fk(w (t) k )− Fk(w ∗))]
︸ ︷︷ ︸ A5
(44)
where (44) is due to Lemma B.3. Now we aim to bound A5 in (44). First we can represent A5 in a different form as:
E[ 4Lη2t m ∑ k∈S(t) (Fk(w (t) k )− F ∗ k )− 2ηt m ∑ k∈S(t) (Fk(w (t) k )− Fk(w ∗))]
=E[ 4Lη2t m ∑ k∈S(t) Fk(w (t) k )− 2ηt m ∑ k∈S(t) Fk(w (t) k )− 2ηt m ∑ k∈S(t) (F ∗k − Fk(w∗))
+ 2ηt m ∑ k∈S(t) F ∗k − 4Lη2t m ∑ k∈S(t) F ∗k ] (45)
=E[ 2ηt(2Lηt − 1)
m
∑ k∈S(t) (Fk(w (t) k )− F
∗ k )︸ ︷︷ ︸
A6
] + 2ηtE[ 1
m ∑ k∈S(t) (Fk(w ∗)− F ∗k )] (46)
Now with ηt < 1/(4L) and νt = 2ηt(1− 2Lηt), we have that A6 can be rewritten and bounded as
− νt m ∑ k∈S(t) (Fk(w (t) k )− Fk(w (t)) + Fk(w (t))− F ∗k )
=− νt m ∑ k∈S(t) (Fk(w (t) k )− Fk(w (t)))− νt m ∑ k∈S(t) (Fk(w (t))− F ∗k ) (47) ≤− νt m ∑ k∈S(t) [ 〈∇Fk(w(t)),w(t)k −w (t)〉+ µ 2 ‖w(t)k −w (t)‖2 ] − νt m ∑ k∈S(t) (Fk(w (t))− F ∗k )
(48)
≤νt m ∑ k∈S(t) [ ηtL(Fk(w (t))− F ∗k ) + ( 1 2ηt − µ 2 ) ‖w(t)k −w (t)‖2 ] − νt m ∑ k∈S(t) (Fk(w (t))− F ∗k )
(49)
=− νt m (1− ηtL) ∑ k∈S(t) (Fk(w (t))− F ∗k ) + ( νt 2ηtm − νtµ 2m ) ∑ k∈S(t) ‖w(t)k −w (t)‖2 (50)
≤− νt m (1− ηtL) ∑ k∈S(t) (Fk(w (t))− F ∗k ) + 1 m ∑ k∈S(t) ‖w(t)k −w (t)‖2 (51)
where (48) is due to µ−convexity, (49) is due to Lemma B.1 and the AM-GM inequality and Cauchy–Schwarz inequality, and (51) is due to the fact that νt(1−ηtµ)2ηt ≤ 1. Hence using this bound of A6 we can upper bound A5 as
E[ 4Lη2t m ∑ k∈S(t) (Fk(w (t) k )− F ∗ k )− 2ηt m ∑ k∈S(t) (Fk(w (t) k )− Fk(w ∗))]
≤ 1 m E[ ∑ k∈S(t) ‖w(t)k −w (t)‖2]− νt m (1− ηtL)E[ ∑ k∈S(t) (Fk(w (t))− F ∗k )]
+ 2ηt m E[ ∑ k∈S(t) (Fk(w ∗)− F ∗k )] (52)
≤16η2t τ2G2 − νt m (1− ηtL)E[ ∑ k∈S(t) (Fk(w (t))− F ∗k )] + 2ηt m E[ ∑ k∈S(t) (Fk(w ∗)− F ∗k )] (53)
=16η2t τ 2G2 − νt(1− ηtL)E[ρ(S(π,w(τbt/τc)),w(t))(F (w(t))− K∑ k=1 pkF ∗ k )]
+ 2ηtE[ρ(S(π,w(τbt/τc)),w∗)(F ∗ − K∑ k=1 pkF ∗ k )] (54)
≤16η2t τ2G2−νt(1− ηtL)ρ(E[F (w(t))]− K∑ k=1 pkF ∗ k )︸ ︷︷ ︸
A7
+2ηtρ̃Γ (55)
where (54) is due to the definition of ρ(S(π,w),w′) in Definition 3.2 and (55) is due to the definition of Γ in Definition 3.1 and the definitions of ρ, ρ̃ in Definition 3.2. We can expand A7 in (55) as
− νt(1− ηtL)ρ(E[F (w(t))]− K∑ k=1 pkF ∗ k ) (56)
=− νt(1− ηtL)ρ K∑ k=1 pk(E[Fk(w(t)]− F ∗ + F ∗ − F ∗k ) (57)
=− νt(1− ηtL)ρ K∑ k=1 pk(E[Fk(w(t)]− F ∗)− νt(1− ηtL)ρ K∑ k=1 pk(F ∗ − F ∗k ) (58) =− νt(1− ηtL)ρ(E[F (w(t))]− F ∗)− νt(1− ηtL)ρΓ (59)
≤− νt(1− ηtL)µρ 2 E[‖w(t) −w∗‖2]− νt(1− ηtL)ρΓ (60) ≤− 3ηtµρ 8 E[‖w(t) −w∗‖2]− 2ηt(1− 2Lηt)(1− ηtL)ρΓ (61) ≤− 3ηtµρ 8 E[‖w(t) −w∗‖2]− 2ηtρΓ + 6η2t ρLΓ (62)
where (60) is due to the µ−convexity, (61) is due to −2ηt(1− 2Lηt)(1− ηtL) ≤ − 34ηt, and (62) is due to −(1− 2Lηt)(1− ηtL) ≤ −(1− 3Lηt). Hence we can finally bound A5 as
4Lη2t m E[ ∑ k∈S(t) (Fk(w (t) k )− F ∗ k )− 2ηt m ∑ k∈S(t) (Fk(w (t) k )− Fk(w ∗))]
≤− 3ηtµρ 8 E[‖w(t) −w∗‖2] + 2ηtΓ(ρ̃− ρ) + η2t (6ρLΓ + 16τ2G2) (63)
Now we can bound E[‖w(t+1) −w∗‖2] as E[‖w(t+1) −w∗‖2] ≤ [ 1− ηtµ ( 1 + 3ρ
8
)] E[‖w(t) −w∗‖2]
+ η2t
( 32τ2G2 + σ2
m + 6ρLΓ
) + 2ηtΓ(ρ̃− ρ)
(64)
By defining ∆t+1 = E[‖w(t+1)−w∗‖2], B = 1+ 3ρ8 , C = 32τ 2G2 + σ 2
m +6ρLΓ, D = 2Γ(ρ̃−ρ), we have that
∆t+1 ≤ (1− ηtµB)∆t + η2tC + ηtD (65)
By setting ∆t ≤ ψt+γ , ηt = β t+γ and β > 1 µB , γ > 0 by induction we have that
ψ = max { γ‖w(0) −w∗‖2, 1 βµB − 1 ( β2C +Dβ(t+ γ) )} (66)
Then by the L-smoothness of F (·), we have that
E[F (w(t))]− F ∗ ≤ L 2 ∆t ≤ L 2 ψ γ + t (67)

heading: D PROOF OF THEOREM A.1
text: With fixed learning rate ηt = η, we can rewrite (65) as
∆t+1 ≤ (1− ηµB)∆t + η2C + ηD (68)
and with η ≤ min{ 12µB , 1 4L} using recursion of (68) we have that
∆t ≤ (1− ηµB)t∆0 + η2C + ηD
ηµB (1− (1− ηµB)t) (69)
Using ∆t ≤ 2µ (F (w (t))− F ∗) and L-smoothness, we have that
F (w(t))− F ∗ ≤ L µ (1− ηµB)t(F (w(0))− F ∗) + L(ηC +D) 2µB (1− (1− ηµB)t) (70)
= L
µ
[ 1− ηµ ( 1 + 3ρ
8
)]t (F (w(0))− F ∗) + 4L(ηC +D)
µ(8 + 3ρ)
[ 1− [ 1− ηµ ( 1 + 3ρ
8
)]t] (71)

heading: E EXTENSION: GENERALIZATION TO DIFFERENT AVERAGING SCHEMES
text: While we considered a simple averaging scheme where w(t+1) = 1m ∑ k∈S(t) ( w (t) k − ηtgk(w (t) k ) )
, we can extend the averaging scheme to any scheme q such that the averaging weights qk are invariant in time and satisfies ∑ k∈S(t) qk = 1 for any t. Note that q includes the random sampling without replacement scheme introduced by Li et al. (2020) where the clients are sampled uniformly at random without replacement with the averaging coefficients qk = pkK/m. With such averaging scheme q, we denote the global model for the averaging scheme qk as ŵ(t), where ŵ(t+1) ,∑ k∈S(t) qk ( w (t) k − ηtgk(w (t) k ) ) , and the update rule changes to
ŵ(t+1) = ŵ(t) − ηtĝ(t) = ŵ(t) − ηt  ∑ k∈S(t) qkgk(w (t) k , ξ (t) k )  (72) where ĝ(t) = ∑ k∈S(t) qkgk(w (t) k , ξ (t) k ). We show that the convergence analysis for the averaging scheme q is consistent with Theorem 3.1. In the case of the averaging scheme q, we have that Lemma B.2 and Lemma B.3 shown in Appendix B, each becomes
1 m E[ ∑ k∈S(t) ‖ŵ(t) −w(t)k ‖ 2] ≤ 16η2tm(m− 1)τ2G2 (73)
E[‖ŵ(t) −w∗‖2] ≤ mE[ ∑ k∈S(t) qk‖w(t)k −w ∗‖2] (74)
Then, using the same method we used for the proof of Theorem 3.1, we have that E[‖ŵ(t+1) −w∗‖2] ≤ (
1− ηtµ m
) E[‖ŵ(t) −w∗‖2] + η2t σ2m+ 16m2(m− 1)η2t τ2G2+
E 2Lη2t (1 +m) ∑ k∈S(t) qk(Fk(w (t) k )− F ∗ k )− 2ηt ∑ k∈S(t) qk(Fk(w (t) k )− Fk(w ∗))  ︸ ︷︷ ︸
M
(75)
By defining the selection skew for averaging scheme q similar to Definition 5 as
ρq(S(π,w),w′) = ES(π,w)[
∑ k∈S(π,w) qk(Fk(w ′)− F ∗k )]
F (w′)− ∑K k=1 pkF ∗ k
≥ 0, (76)
and ρq , min
w,w′ ρq(S(π,w),w′) (77)
ρ̃q , max w
ρq(S(π,w),w∗) = maxw ES(π,w)[
∑ k∈S(π,w) qk(Fk(w
∗)− F ∗k )] Γ
(78)
With ηt < 1/(2L(1 +m)), using the same methodology for proof of Theorem 3.1 we have that M becomes upper bounded as
E 2Lη2t (1 +m) ∑ k∈S(t) qk(Fk(w (t) k )− F ∗ k )− 2ηt ∑ k∈S(t) qk(Fk(w (t) k )− Fk(w ∗))  (79) ≤ −
ηtµρq 2 E[‖ŵ(t) −w∗‖2] + 2ηtΓ(ρ̃q − ρq) + 16m2(m− 1)η2t τ2G2 + 2Lη2t (2 +m)ρqΓ (80)
Finally we have that E[‖ŵ(t+1) −w∗‖2] ≤ [ 1− ηtµ ( 1
m + ρq 2
)] E[‖ŵ(t) −w∗‖2] + 2ηtΓ(ρ̃q − ρq)
+η2t [32m 2(m− 1)τ2G2 + σ2m+ 2L(2 +m)ρqΓ]
(81)
By defining ∆̂t+1 = E[‖ŵ(t+1)−w∗‖2], B̂ = 1m + ρq 2 , Ĉ = 32m 2(m− 1)τ2G2 +σ2m+ 2L(2 + m)ρqΓ, D̂ = 2Γ(ρ̃q − ρq), we have that
∆̂t+1 ≤ (1− ηtµB̂)∆̂t + η2t Ĉ + ηtD̂ (82)
Again, by setting ∆̂t ≤ ψt+γ , ηt = β t+γ and β > 1 µB̂ , γ > 0 by induction we have that
ψ = max { γ‖w(0) −w∗‖2, 1
βµB̂ − 1
( β2Ĉ + D̂β(t+ γ) )} (83)
Then by the L-smoothness of F (·), we have that
E[F (w(t))]− F ∗ ≤ L 2 ∆̂t ≤ L 2 ψ γ + t (84)
With β = mµ , γ = 4m(1+m)L µ and ηt = β t+γ , we have that
E[F (ŵ(T ))]− F ∗ ≤
1
(T + γ)
[ Lm2(32m(m− 1)τ2G2 + σ2)
µ2ρq +
2L2m(m+ 2)Γ µ2 + Lγ‖w(0) −w∗‖2 2 ] ︸ ︷︷ ︸
Vanishing Error Term
+ 2LΓ
ρqµ ( ρ̃q ρq − 1 )
︸ ︷︷ ︸ Non-vanishing bias
(85)
which is consistent with Theorem 3.1.

heading: F EXPERIMENT DETAILS
text: Quadratic Model Optimization. For the quadratic model optimization, we set each local objective function as strongly convex as follows:
Fk(w) = 1 2 w>Hkw − e>k w + 1 2 e>kH −1 k ek (86)
Hk ∈ Rv×v is a diagonal matrix Hk = hkI with hk ∼ U(1, 20) and ek ∈ Rv is an arbitrary vector. We set the global objective function as F (w) = ∑K k=1 pkFk(w), where the data size pk follows the power law distribution P (x; a) = axa−1, 0 ≤ x ≤ 1, a = 3. We can easily show that the optimum for Fk(w) and F (w) is w∗k = H −1 k ek and w ∗ = ( ∑K k=1 pkHk) −1( ∑K k=1 pkek) respectively. The gradient descent update rule for the local model of client k in the quadratic model optimization is
w (t+1) k = w (t) k − η(Hkw (t) k − ek) (87)
where the global model is defined as w(t+1) = 1m ∑ k∈S(t) w (t+1) k . We sample m = KC clients for every round where for each round the clients perform τ gradient descent local iterations with fixed learning rate η and then these local models are averaged to update the global model. For the implementation of πadapow-d, d was decreased half from d = K for every 5000 rounds. For all simulations we set τ = 2, v = 5, η = 2× 10−5. For the estimation of ρ and ρ̃ for the quadratic model, we get the estimates of the theoretical ρ, ρ̃ values by doing a grid search over a large range of possible w,w′ for ρ(S(π,w),w′) and
ρ(S(π,w),w∗) respectively. The distribution of S(π,w) is estimated by simulating 10000 iterations of client sampling for each π and w.
Logistic Regression on Synthetic Dataset. We conduct simulations on synthetic data which allows precise manipulation of heterogeneity. Using the methodology constructed in (Sahu et al., 2019), we use the dataset with large data heterogeneity, Synthetic(1,1). We assume in total 30 devices where the local dataset sizes for each device follows the power law. For the implementation of πadapow-d, d was decreased to d = m from d = K at half the entire communication rounds. We set the mini batch-size to 50 with τ = 30, and η = 0.05, where η is decayed to η/2 every 300 and 600 rounds.
DNN on FMNIST Dataset. We train a deep multi-layer perceptron network with two hidden layers on the FMNIST dataset (Xiao et al., 2017). We construct the heterogeneous data partition amongst clients using the Dirichlet distribution DirK(α) (Hsu et al., 2019), where α determines the degree of the data heterogeneity across clients (the data size imbalance and degree of label skew across clients). Smaller α indicates larger data heterogeneity. For all experiments we use mini-batch size of b = 64, with τ = 30 and η = 0.005, where η is decayed by half for every 150, 300 rounds. We experiment with three different seeds for the randomness in the dataset partition across clients and present the averaged results.
All experiments are conducted with clusters equipped with one NVIDIA TitanX GPU. The number of clusters we use vary by C, the fraction of clients we select. The machines communicate amongst each other through Ethernet to transfer the model parameters and information necessary for client selection. Each machine is regarded as one client in the federated learning setting. The algorithms are implemented by PyTorch.
Pseudo-code of the variants of pow-d: cpow-d and rpow-d. We here present the pseudo-code for πcpow-d and πrpow-d. Note that the pseudo-code for πcpow-d in Algorithm 1 can be generalized to the algorithm for πpow-d, by changing 1|ξ̂k| ∑ ξ∈ξ̂k f(w, ξ) to Fk(w).
Algorithm 1 Pseudo code for cpow-d: computation efficient variant of pow-d 1: Input: m, d, pk for k ∈ [K], mini-batch size b = |ξ̂k| for computing 1|ξ̂k| ∑ ξ∈ξ̂k f(w, ξ)
2: Output: S(t) 3: Initialize: empty sets S(t) and A 4: Global server do 5: Get A = {d indices sampled without replacement from [K] by pk} 6: Send the global model w(t) to the d clients in A 7: Receive 1|ξ̂k| ∑ ξ∈ξ̂k f(w, ξ) from all clients in A
8: Get S(t) = {m clients with largest 1|ξ̂k| ∑ ξ∈ξ̂k f(w, ξ) (break ties randomly)}
9: Clients in A in parallel do 10: Create mini-batch ξ̂k from sampling b samples uniformly at random from Bk and compute
1 |ξ̂k| ∑ ξ∈ξ̂k f(w, ξ) and send it to the server
11: return S(t)
Algorithm 2 Pseudo code for rpow-d: computation & communication efficient variant of pow-d 1: Input: m, d, pk for k ∈ [K] 2: Output: S(t) 3: Initialize: empty sets S(t) and A, and list Atmp with K elements all equal to inf 4: All client k ∈ S(t−1) do 5: For t mod τ = 0, send 1τb ∑t l=t−τ+1 ∑ ξ∈ξ(l)k f(w (l) k , ξ) to the server with its local model
6: Global server do 7: Receive and update Atmp[k] = 1τb ∑t l=t−τ+1 ∑ ξ∈ξ(l)k f(w (l) k , ξ) for k ∈ S(t−1) 8: Get A = {d indices sampled without replacement from [K] by pk} 9: Get S(t) = {m clients with largest values in [Atmp[i] for i ∈ A], (break ties randomly)}
10: return S(t)

heading: G ADDITIONAL EXPERIMENT RESULTS

heading: G.1 SELECTED CLIENT PROFILE
text: We further visualize the difference between our proposed sampling strategy πpow-d and the baseline scheme πrand by showing the selected frequency ratio of the clients for K = 30, C = 0.1 for the quadratic simulations in Figure 7. Note that the selected ratio for πrand reflects each client’s dataset size. We show that the selected frequencies of clients for πpow-d are not proportional to the data size of the clients, and we are selecting clients frequently even when they have relatively low data size like client 6 or 22. We are also not necessarily frequently selecting the clients that have the highest data size such as client 26. This aligns well with our main motivation of POWER-OF-CHOICE that weighting the clients’ importance based on their data size does not achieve the best performance, and rather considering their local loss values along with the data size better represents their importance. Note that the selected frequency for πrand is less biased than πpow-d.

heading: G.2 COMMUNICATION AND COMPUTATION EFFICIENCY WITH LARGER DATA HETEROGENEITY
text: In Table 2, we show the communication and computation efficiency of POWER-OF-CHOICE for α = 2, as we showed for α = 0.3 in Table 1 in Section 5. With C = 0.03 fraction of clients, πpow-d, πcpow-d, and πrpow-d have better test accuracy of at least approximately 10% higher test accuracy performance than (πrand, C = 0.1). R60 for πpow-d, πcpow-d, πrpow-d is 0.61, 0.66, 0.73 times that of (πrand, C = 0.1) respectively. This indicates that we can reduce the number of communication rounds by at least 0.6 using 1/3 of clients compared to (πrand, C = 0.1) and still get higher test accuracy performance. The computation time tcomp for πcpow-d and πrpow-d with C = 0.03 is smaller than that of (πrand, C = 0.1).
G.3 INTERMITTENT CLIENT AVAILABILITY
In real world scenarios, certain clients may not be available due to varying availability of resources such as battery power or wireless connectivity. Hence we experiment with a virtual scenario, where amongst K clients, for each communication round, we select clients alternately from one group out of two fixed groups, where each group has 0.5K clients. This altering selection reflects a more realistic client selection scenario where, for example, we have different time zones across clients. For each communication round, we select 0.1 portion of clients from the corresponding group uniformly at random and exclude them from the client selection process. This random exclusion of certain clients represents the randomness in the client availability within that group for cases such as low battery power or wireless connectivity. In Figure 8 we show that πpow-d and πrpow-d achieves 10% and 5% test accuracy improvement respectively compared to πrand for α = 2. For α = 3, both πpow-d and πrpow-d shows 10% improvement. Therefore, we demonstrate that POWER-OF-CHOICE also performs well in a realistic scenario where clients are available intermittently.

heading: G.4 RESULTS FOR DNN ON NON-IID PARTITIONED EMNIST DATASET
text: To provide further validation of the consistency in our results of πpow-d and its variants on the FMNIST dataset, we present additional experiment results on the EMNIST dataset sorted by digits with K = 500, C = 0.03. We train a deep multi-layer perceptron network with two hidden layers on the dataset partitioned heterogeneously across the clients in the same way as for the FMNIST dataset. For all experiments, we use b = 64, τ = 30, and η = 0.005 where η is decayed by half at round 300.
In Figure 9, we show that πpow-d performs with significantly higher test accuracy than πrand for varying d for both α = 2 and 0.3. For α = 2, πafl is able to follow the performance of πpow-d in the later communication rounds, but is slower in achieving the same test accuracy than πpow-d. Moreover, in Figure 10, we show that πcpow-d works as good as πpow-d for both large and small data heterogeneity. The performance of πrpow-d falls behind πpow-d and πcpow-d for smaller data heterogeneity, whereas for larger data heterogeneity, πrpow-d is able to perform similarly with πpow-d and πcpow-d.

heading: G.5 EFFECT OF THE FRACTION OF SELECTED CLIENTS
text: In Figure 11, for larger C = 0.1 with α = 2, the test accuracy improvement for πpow-d is even higher than the case of C = 0.03 with approximately 15% improvement. πcpow-d performs slightly lower in test accuracy than πpow-d but still performs better than πrand and πafl. πrpow-d performs as well as πafl. For α = 0.3, πpow-d, πcpow-d, and πrpow-d have approximately equal test accuracy performance, higher than πrand by 5%. The POWER-OF-CHOICE strategies all perform slightly better than πafl. Therefore we show that POWER-OF-CHOICE performs well for selecting a larger fraction of clients, i.e., when we have larger C = 0.1 > 0.03.

heading: G.6 EFFECT OF THE LOCAL EPOCHS AND MINI-BATCH SIZE
text: We present the experiment results elaborated in Section 5 for the different hyper-parameter settings (b, τ) ∈ {(128, 30), (64, 100)} in Figure 12, 13, 14, and 15 below.

Review summaries:
This work investigates federated optimization considering data heterogeneity, communication and computation limitations, and partial client participation. In contrast to past works, this paper focuses on deeper understanding of the effect of partial client participation on the convergence rate by considering biased client participation. The paper provides convergence analysis for any biased selection strategy, showing that the rate is composed of vanishing error term and non-vanishing bias term. The obtained rates explicitly show the effect of client selection strategy and the trade-off between convergence speed and the solution bias. Then it proposes a parametric family of biased selection strategy, called power-of-choice, which aims to speed up the convergence of the error term at the cost of possibly bigger bias term. Experiments are provided to highlight the benefits of the proposed pow-d strategy over the standard unbiased selection strategies.