Client Selection in Federated Learning: Convergence Analysis and Power-of-Choice Selection Strategies
Authors: Yae Jee Cho
Jianyu Wang
Gauri Joshi
Venue:  (2021)
Keywords: distributed optimization
federated learning
client selection

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 bias 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 communication- and 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 converge up to 3 $\times$ faster and give $10$% higher test accuracy than the baseline random selection. 

Under review as a conference paper at ICLR 2021
CLIENT SELECTION IN FEDERATED LEARNING: CONVERGENCE ANALYSIS AND POWER-OF-CHOICE SELECTION STRATEGIES
Anonymous authors Paper under double-blind review
ABSTRACT
Federated learning is a distributed optimization paradigm that enables a large number of resource-limited client nodes cooperatively train 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 communication- and computation-efficiie client selection framework that can flexibly span the trade-off between convergence speed and solution bias. We also propose extension of POWER-OF- OF-CO-CC that is able maintain convergence speed improvement while diminishing the selection skew. Our experiments demonstrate that POWER-OF-CHOLEE strategies converge up to 3x faster and give 10% higher test accuracy than the baseline random selection.
INTRODUCTION
Until recently, machine learning models were largely trained 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 moving both data collection as well as model training to the edge. The emerging paradigm of federated learning (McMahan et al.) [017]] mobile
Kairouz et al. 2019 Bonawitz et al., 2019) considers a large number of resource--onstrraine 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 few iterations of training using local-update stochastic gradient descent (SGD) Yuu 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 cocalee SGD is analyzed in several recent works (Reddi et al., 2020 Haddadpour & Mahdavi [019 Khaled
al. 2020 Stich & Karimireddy 2019 Woodworth et al. 2020 Koloskova al. 2020 Huo et 2020 Zhang et al. 2020) Pathak & Wainwright 2020 Malinovsky et al.) 2020 Sahu et al.) 2019)
and methods to overcome the adverse effects data and computational heterogeneity are proposed
in (Sahu et al. 2019 Wang al. 2020: Karimireddy et al. 2019), among others.
Partial Client Participation. Most of the recent works described above assume full client participa- tion, that is, all nodes participate in every training round. In practice, only small fraction of client nodes participate in each training round, which can exacerbate the adverse effects of data heterogene- ity. 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 limited 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

---

Under review as a conference paper at ICLR 2021
training process 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 sharply accelerate error convergence, and hence boost communication efficiency in heterogeneous environ- ments by preferentially selecting clients with higher local loss values,
show in our paper. This idea has been explored in recent empirical studies (Goetz et al. 2019 Laguel et al. [020] Ribero & Vikalo, 2020). Nishio & Yonetani (2019) proposed grouping clients based hardware and wireless resources in order to save communication resources. Goetz et al. (2019) (which we include as a benchmark 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 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, 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, propose the POWER-OF-CHOICE client selection strategy and show by extensive experiments that POWER-OF-CHOICE yields up to 3x 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 3x less clients participating in each round as compared to random selection, POWER OF-CCOCE gives 2 faster convergence and 5% higher test accuracy.
2 PROBLEM FORMULATION
Consider a cross-device federated learning setup with total K clients, where client k has a local dataset B& consisting [Bx| Da 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:
K
F(w)
S(w,
Px k=1
(1)
Σ
DR k= CEB
where f(w,E) E) is the composite loss function for sample & and parameter vector W. The term k=1 D& is the fraction of data at the k-th client, and (+(w)= [.. EeeB, f(w,g) {) is the local objective function of client k. In federated learning, the vectors w*, and w for I,..., K that minimize F F(w) and Fg (w( respectively can be very different from each other. We define F* min F F(w)= = F(w*) and Fø min F (w) = Fl(wt))
Pk = Dr/Ex=
Federated Averaging with Partial Client Participation. The most common algorithm to solve I 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 fraction C' of m CK clients participate the training. Each selected/active client performs т iterations of local SGD (Such 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 new set of active clients.
Formally, we index the local SGD iterations with 2 0. The set of active clients at iteration is denoted by (tt), Since active clients performs steps of local update, the active set S(t) also remains constant for every iterations. That is, if (I + 1) mod - 0, then g((+1) S(1+2)
S(t+))
2

---

Under review as a conference paper at ICLR 2021
[i(w)
F(w)
F2(w)
(i(w)
(
F(w)
F2(w)
w!
w
w (1)
w
W
w
w (4)
((5)
w
(4)
W
W
W
Fi (ww F w)
Fi(w) > (2(w)
client selected:
select
select 1
> 2 > 1
(a) Selecting Higher Loss Clients
(b) Random Client Selection
Figure 1: A toy example with (i(w), (2(w) as the local objective, and F(w) (Fi (w) /2 as the global objective function with global minimum w At each round, only one client is selected to perform local updates. (a): Model updates for sampling clients with larger loss; (b): Model updates for sampling clients uniformly random (we select client in the order of 2,2.1.1,2).
Accordingly, the update rule of FedAvg can be written as follows:
(t) W Te.9 W (W (1)
(e)
(1)
for (t 1) mod * Teg (w) 50 (,,,,,,)))) ( A w(+++) for 1) mod
(++1)
w k
(2)
m EjESO
where (++1) denotes the local model parameters of client is at iteration Te is the learning rate, and (1) () is the stochastic gradient over mini-batch e(t) of size b that
(t) k go ( (() = =Eee!" (
is randomly sampled from client k's local dataset B₁. Moreover, (+++1) denotes the global model at server. Although w(() is only updated after every iterations, for the purpose of convergence
analysis consider virtual sequence of w(() that is updated at each iteration follows
((++)) (()) -nig(") ((
Σ (w ((()) kES(()
(3)
(t) ) Note that in 2 and 3 we do not weight the client models by with = ExESO Io (w
their dataset fractions Pk because pı is considered in the chient selection scheme used to decide the set S(t), Our convergence analysis can be generalized to when the global model a weighted average instead of simple average of client models, and show in Appendix that our convergence analysis also covers the sampling uniformly at random without replacement scheme proposed by Li ct al. 22020). 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 (()) 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 [].. most current analysis frameworks (Li et al. 2020 Karimireddy et al.) 2019: Wang et al., 2020) consider strategy that selects the set (()) by sampling m clients at random (with replacement) such that client ie is selected with probability Pk. the fraction of data 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 Frand-
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 biased sampling scheme, with the normalizing aggregation
3

---

Under review as a conference paper at ICLR 2021
the update rule is unbiased. Henceforth, we state that paper encompasses both biased and unbiased update rules. In the two-client example in Figure we set ((++1) arg [ Fk (w()), ).
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 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 client selection strategy π as a function that maps the current global model w to a selected set of clients STT, w).
CONVERGENCE ANALYSIS
In this section we analyze the convergence of federated averaging with partial device participation for any client selection strategy defined above. This analysis reveals that biased client selection can give faster convergence, albeit at the risk having a non-vanishing gap between the true optimum w" arg min F F(w) and lim w( We use this insight Section 4 to design client selection strategies that strike balance between convergence speed and bias.
3.1 ASSUMPTIONS AND DEFINITIONS
First we introduce the assumptions and definitions utilized for our convergence analysis. Assumption 3.1. F1; Fs are all I, L--shotth, i..,, for all v and w, Fie()) S Fk(w) + (v W)' (w) + ||v w
Assumption 3.2. F1, Fs are all p-stroogly convex, i.e., for all and w. Fa(v) Fl(w)
w|? -
(v FV (w) + llv
Assumption 3.3. For the mini mini-batch εa uniformly sampled at random from Bg from user k. the resulting stochastic gradient is unbiased, that is, Elgs( (Ws, Cx. [x]]= FF&((s.). Also, the variance of stochastic gradients is bounded: [El]g((Wxss
V (w:))l S a² for all k k= 1...., K......
Assumption 3.4. The stochastic gradient's 's expected squared norm is uniformly bounded, i.e., Eligh (K. 12 < G2 for k K.....
The above assumptions are common in related literature, see Stich 2018 Basu et al, 2019 Li ct al. 2020 Ruan et al. 20200. Next, we introduce two metrics, the local-ght 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 F(w) and local optimum w arg minw Fi(w we define the local-global objective gap as
K
2 F
PuFt Σ
2 O.
(4)
Note that I' is an inherent property of the local and global objective functions, and it is independent of the client selection strategy. This definition was introduced previous literature by Li al. (2020) A larger T' implies higher data heterogeneity. If T O 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.I. 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 ls E S((T, w) define,
p(S(a, w). w') Es(k,w) 1 EkES(r w) (Fx(w') FE)
2 0,
(5)
F(w') E PA-IPPFF
which reflects the skew of a client selection strategy т. The first w in P(S(TT, w): w/) is the parameter vector that governs the client selection and w' is the point which F5 and F in the numerator and denominator respectively are evaluated. Note, Es( is the expectation over the randomness from the selection strategy n, since there can be multiple sets S that can map from specific
4

---

Under review as a conference paper at ICLR 2021
Since p(S(T, 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 conservative enror bound in the convergence analysis.
P -
min ((S(TT, w), w'), p max ((S(T,W), w),
(6)
where w' arg minw F(w). From 6 we have S foror any client selection sirulegy
Effect of the Client Selection Strategy on P and p. For the unbiased client selection strategy Trand we have
w), w') for all w and w' since the numerator and denominator of (5) become equal, and p = P = For client selection strategy и that chooses clients with higher Fs(w) more often, and will be larger (and > 1). In the convergence analysis we show that larger implies faster convergence, albeit with potential error gap, which is proportional to (ø/p 1). Motivated by this, in Section 4 we present an adaptive client selection strategy that prefers selecting clients with higher loss F) (w)) and achieves faster convergence speed with low solution bias.
3.2 MAIN CONVERGENCE RESULT
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 I,, and selection skew p, p.
Theorem 3.1 (Convergence with Decaying Learning Rate). Under Assumptions 3.1 to 3.4 for learning rate Ti. p((+>) with y n² iterations of federated averaging with partial device participation satisfies
4L and any client selection strategy म, the error after T
E[F(WW (w - -F
AL(32T + o
SL n22
L
W
(0)
w=1
7LI 3/
T +))
31²p
2
Vonialting Error
Non-vanishing blas, ((7.))
To the best of our knowledge, Theorem 3.1 provides the first convergence analysis of federated averaging with 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. (020). 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 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 7 in detail.
Large and Faster Convergence. A key insight from Theorem 3.1 is that larger selection skew results faster convergence at the rate O T7 Note that since we obtain p (defined in (6)) by taking
a minimum of the selection skew p(S(TT, w), w') over w, w', this is conservative bound on the true convergence rate. In practice, since the selection skew p(S(TT, 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 factor larger than and least equal to p.
Non-vanishing Bias Term. The second term Q(p. = 3LT
in denotes the solution
3
bias, which is dependent on the selection strategy. By the definitions of p and p. it follows that p 2 which implies that Qp,, p) > O. For unbiased selection strategy, we have 7 = 7
Q p)
and hence (7) recovers previous bound for unbiased selection strategy as (Li et al. 2020 For p > 1, while we gain faster convergence rate by factor p, we cannot guarantee Q p) O. 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(p, p) can be close to 0, and hence Q(, has negligible effect on the final error floor.

---

Under review as a conference paper at ICLR 2021
4 PROPOSED POWER-OF-CHOICE CLIENT SELECTION STRATEGY
From and 6 we discover that a selection strategy т that prefers clients with larger [+((w) (o(ww)/) F will result in a larger P. yielding faster convergence. Using this insight, naive client selection strategy can be choosing the clients with highest local loss F& (w). However, a larger selection skew p may result in a larger p/P. i.e., larger non-vanishing error term. This naive selection strategy has another drawback- - to find the current local loss Fs (w), it requires sending the current global model to all clients and having them evaluate F& and sending 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.
these insights regarding the trade-off between convergence speed, solution overhead to propose the POWER SEEERROF-CHEEE OF-CHOICE client selection strategy. POWER-OF OF-CHOICE is based on the power of d choices load balancing strategy (Mitzen macher, 1996), which is extensively used in queueing systems. In the POWER-OF-CHOICE client selection strategy (denoted by poow-d), the central server chooses the active client set S(1) as follows:
In this section, bias and communication//oopputiii
Sample the Candidate Client Set. The central server samples a candidate set A of (m S d S K) clients without replacement such that client l is chosen with probability Pk, the fraction of data at the k-th client for k = I....
2. Estimate Local Losses. The server sends the current global model w(() to the clients in set A, and these clients compute and send back to the central server their local loss F (w()).
3. Select Highest Loss Clients. From the candidate set A, the central server constructs the active client set ( by selecting m max(C'K, 1) clients with the largest values F& (W). with ties broken random. These (()) clients participate in the training during the next round, consisting of iterations + +,, T..
Variations of T.oo.dd The three steps of Tooo-d can be flexibly modified to take into account practical considerations. For example, intermittent client availability 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 Tooo-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 Too-- (see Appendix
F for their pseudo-codes).
Computation--fficienl Variant Tepow-d: To save local computation cost, instead of evaluating the (w)) by going through the entire local dataset B&, we use an estimate Σςe f
where E is the mini-bater of b samples sampled uniformly at random from By.
Communication- and Computation-efficient Variant Tapow-d: To save both local computation and communication cost, the selected clients for each round sends their accumulated averaged loss over local iterations, i.c., r1E Ei Egeeh f(w .) when they send their local models
to the server. The server uses the latest received value from each client as proxy for F&((w) to select the clients. For the clients that have not been selected yet, the latest value is set D0.
Adaptive Selection Skew Variant Tadapow-dd To minimize the non- non-vanig bias term in Theo- rem 3.1 while simultaneously gaining the benefit of convergence speed from P, we gradually reduce until = ! 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 ppper-paramttrs..
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 m we have random sampling without replacement proportion of pk. As d increases. the selection skew increases, giving faster emor convergence at the risk of a higher error floor. However, note that the convergence analysis replaces p(w, w') with to get a conservative error bound. In
Id = makes our proposed strategy, which has non-vanishing bias term.
strategy to become analogous to an unbiased sampling

---

Under review as a conference paper at ICLR 2021
le4
le4
rand
rand
rand
Global loss
pow-d, d-6
Global loss
pow-d, d-15
Global loss
10*
pow-d, d-15
pow-d, d-9
pow-d, d030
adapow-d
2
pow-d, d-30,
pow-d, d-100,
adapow-d
1
adapow-d
10
5000 10000
15000
5000 10000
15000
20000 Communication round (c) K 100 (log-scale)
40000
Communication round
Communication round
(a) K = 30
(b) K = 100
Figure 2: Global loss performance of Trand, pow-dd and Tadapow-d for the quadratic experiments with
C' 0.1. pow-d convergences faster than Trand for even selecting from a small pool of clients
(K = 30). As convergence speed increases, solution bias also increases for Tpow-d but Tadapow- d is able to eliminate this solution bias while gaining nearly identical convergence speed to Tpow-d-
practice, the convergence speed and the solution bias is dictated by p(W(TL!/T]) w()) which changes during training. With ppoo- which is biased towards higher local losses, we expect the selection skew p(w, w') reduce through the course of training. We conjecture that this is why "poo-d gives faster convergence as well as little or no solution bias in our experiments presented in Section
5 EXPERIMENTAL RESULTS
We evaluate our proposed 7 poo-d and its practical variants Tepow-d. Trpow-d, and Tadapow-d by three sets of experiments: (1) quadratic optimization, (2) logistic regression a synthetic federated dataset, Synthet i c(1,1) (Sahu et al. (219)) 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 ann Details of the experimental setup are provided in Appendix and the code for all experiments are shared in the supplementary material. To validate consistency our
results, we present additional experiments with DNN trained on non-iid partitioned EMNIST (Cohen
ct al. 2017 dataset sorted by digits with K- 500 clients. We present the results in Appendix G.4
Quadratic and Synthetic Simulation Results. In Fig- (a). even with few clients (K = 30), pooo- converges faster than Trand with nearly negligible solution bias for small d. The convergence speed increases with the in- crease in d, at the cost of higher error floor due to the solution bias. For K 100 in Figure T powo- shows convergence speed-up as with K 30, but the bias is smaller. Figure shows the theoretical values 7 and p/P which represents the convergence speed and the solution bias respectively in our convergence analysis. Compared to Trand: To has higher p for all d implying higher con- vergence speed than Trand- By varying d we can span different points on the trade-off between the convergence speed and bias. For d = 15 and K = 100, p/P of pow-d and Trand are approximately identical, but Pooo-d has higher P. implying that ग poo-- can yield higher convergence speed with negligible solution bias. In Appendix G.I] we present the clients' selected frequency ratio for Tow and Trand which gives novel insights regarding the dif- ference between the two strategies. For the synthetic dataset simulations, we present the global losses in Figure 4 for Trand and pow-d for different d and m. We show that poo-d converges approximately 3 x faster To the global loss R3 0.7 than Trand when d = 10m, with a slightly higher error floor. Even with d 2m, we get 2x faster convergence to global loss R 0.7 than Trand-
C-0.10
d-100
rand, K-100
rand, K=30
d-30
p (bias)
pow-d, K-100
pow-d, K-30
d-15
d=50
d=9
d=6
d-30
d=15
1.00
1.25
1.50
1.75
6 (convergence speed)
Figure 3: Estimated theoretical values P and p/ō for the quadratic simula- tion. The convergence speed (p) and bias (p/p) are consistent with the results shown in Figure Z for Frand and xpow-d-
Elimination of Selection Skew with Tadapow-d- For Tpow-d: the selection skew is the trade-ofi off for the convergence speed gain in Figure and Figure 4 For both simulations, Tpow-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 Tadapow d- In Figure 2 a))(b), Wadapow d shows
7

---

Under review as a conference paper at ICLR 2021
2.5
rind
rand
pow-d, d-2
2.0
pow-d, d-4
pow-d, dr6
Global loss
pow-d, d-10
Global loss
pow-d, d-20
Global loss
pow-d, d-30
adspow-d
1.5
adapow-d
1.5
adapow-d
1.0
converipes 3x faster to global loss= 0.7
0.5
0.5
250 500 750
250
500
750
0
250
500
750
Communication round
Communication round
Communication round
(a)
(b) m = 2
(c) m 3
Figure 4: Global loss for logistic regression on the synthetic dataset, Synthet c(1,1), with Trand-
Tpow-ds ds and Wulspow-d for d E (2m, 10m) where K =30, E 21, pooo converges approx- imately 3 x faster for d = 10m and 2 x faster for d = 2m than Trand to the global loss z 0.7.
Tadapow-d is able converge to the minimum global loss 3x faster than Trand-
K-100, C-0.03
K-100,
K-100, C-0.03
K-100, C-0.03
-0.
70
rand
rand
Test accuracy
Training loss
pow-d, d-6
Test accuracy
Training logs
pow-d, d-6
pow-d,
pow-d, d-9
S
rand
0.4
pow-d, d-15
rand
0.4
pow-d, d-15
pow-d, 6-6
pow-d, d-6
pow-d, d=9
0.3
pow-d, d=
u.
-30
pow-d, d=15
pow-d,
20
1070
400
400 Communication round
Communication round
Communication round
Communication round
(a) Test accuracy and training loss for =
(b) Test accuracy and training loss for a = 0.3
Figure 5: Test accuracy and training loss for different sampling strategies with K 100, C 0.03 for varying d on the FMNIST dataset. For both small and large Toow-d achieves at least 10% test accuracy improvement than Trand and the training loss converges at a much higher rate than Trand-
convergence speed similar to Toow-d: d = K. but has no selection skew, converging to the same minimum as Trand (see Figure (e). In Figure 4 Tndapow-d again shows convergence speed similar to Tpow-d; d = 10m, but has no adversarial selection skew. As matter of fact, Tadapow-d converges to the minimum global loss value least faster than Frand- Hence Tadapow-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 a deter- mines the data heterogeneity across clients. Smaller a 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 a = 0.3 and a = 2. Observe that Toos-d achieves approximately 10% and 5% higher test accuracy than Trand and Tan respectively for both a = and a = 0.3. For higher a (less data heterogeneity) larger d (more selection skew) performs better than smaller d.
Figure 5 ()) shows that this performance improvement due to the increase of d eventually converges. For smaller as in Figure b).. smaller d = 6 performs better than larger d which shows that too much solution bias adversarial to the performance in the presence of large data heterogeneity. The observations on training loss are consistent with the test accuracy results.
variants. Next, we evaluate Nepow-d and a which were introduced in Section 4 In Figure 6 for = 2, Tipow-d and Tepow each yields approximately 5% and 6% higher accuracy than Trand but both yield lower accuracy than poo-d that utilizes the highest computation and communication resources. For 0.3, Tepow-d and Trpow-d perform as well as po and give a 10% accuracy improvement over aand- Moreover, π Toow-d; Nepow-d and Tepow-d all have higher accuracy and faster convergence than Tal-
Performance of the Communication- and Computation-Efffiiee
We evaluate the communication and computation efficiency of POWER-OF-CHOOL OF-CHIICC by comparing different strategies in terms of Reo. the number of communication rounds required to reach test accuracy 60%, and tzomp 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
8

---

Under review as a conference paper at ICLR 2021
K-100, C=0.03
K-100, C-0.03
K-100, C-0.03
K- K-100, C-0.03
-0.
70
-02
rand
pow-d, d-15
-92
rand
pow-d, d=6
Tost accuracy
Training loss
033
spow-d, 1515
Tes accuran
-2
Training loss
9.
spow-d, d-6
rmnd
04
rpow d, d-50
S
rand
rpow-d, d-50
35
pow-d, d-15
afl
puw-d, d-6
spow-d, -d d-15
0.5
spow-d, d-6
spow-d, d-50
0.6
rpow-d, d-50
adl
afl
10
Communication round Communication round
Communication round
Communication round
(a) Test accuracy and training loss for
(b) Test accuracy and training loss for 0.3
Test accuracy and training loss for different sampling strategies including Tepow-d and Trpow-d- for K 100, C 0.03 on the FMNIST dataset. Tipow-d which requires no additional communication and minor computation, yields higher test accuracy than Tannd and Tan-
Figure 6:
Table 1: Comparison of REn. (sec) and test accuracy (%) for different sampling strategies with
0.3. In the parentheses show the ratio of each value with that for rand with C = 0.1.
C' == 0.1
C = 0.03
rand
rand
pow-d, d = 6
cpow-d, d =
rpow-d, d = 50
afl
Reo
172
234(1 1. 36)
89(0.52)
80 (0.47)
98 (0.57)
(21(0.70)
leomp
0.43
(..85
(1.13)
0.37 (0.88)
0.37 (0.85)
0.36(0.84)
Test Acc.
71.21
6..97
16.47
76.63
76.56.11.00
73.28.1
time for the d clients to compute their local loss values) and the time taken by selected clients to perform local updates. In Table I with only C' 0.03 fraction of clients, Tpow-d: Tepow-d; and Trpow-d have about 5% higher test accuracy than (Trand, C = 0.1). The Rao for Tpoo-dd Tepow-d: Trpow-d is 0.52, 0.47, 0.57 times that of (Trandd: C = 0.1) respectively. This implies that even for Tppow-d which does not incur any additional communication cost for client selection, we can get 2x reduction in the number of communication rounds using 1/3 of clients compared to (Frand, C' 0.1) and still get higher test accuracy performance. Note that the computation time /oomp for Tepow-d and Tpoowd with C' 0.03 is smaller than that of radd with = 0.1. In Appendix G.2 we show that the results for = 2 are consistent with the = 0.3 case shown in Table [ In Appendix G.5
we also show that
for C' 0.1, the results are consistent with the = 0.03 case.
Effect of Mini-batch Size and Local Epochs. We evaluate the effect of mini- size b and local epochs on the FMNIST experiments with different sets of apper-parameter: (b, 7) E (118,,3), (64, 100)}. Note that (b, r) 30) is the default parameee 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 Fand and aad is consistent with b 64 (see Figure 12 In Figure [4] for T = 100, with smaller data heterogeneity, the performance gap between Trand and Toowdd is consistent with that of r = 30. For larger data heterogeneity, however, increasing the local epochs results in Wrnnd and gow a performing similarly. This shows that with larger data heterogeneity, larger results in increasing the selection skew towards specific clients, and weakens generalization.
CONCLUDING REMARKS
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 1 where is the selection skew towards clients with higher local losses. Motivated by this insight, we propose the adaptive client selection strategy Extensive experiments validate that POWER-OF- convergence and 10% higher test accuracy than the baseline federated averaging with random selection. Even with using fewer clients than random selection, POWER-OF-CIION
TP
yields 3x faster
converges 2 x faster with high test performance, An interesting future direction is to improve the fairness (Li et al. 2019: Yu al.) 2020 Lyu et al. 2020 Mohri et all] 2019) and robustness (Pillutla et al. 2019) of the POWER-OF OF-ROIIICIC strategy by modifying step 3 of the POWER-OP SEFEER-FF-HHEE 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 Fg (w).

---

Under review as a conference paper at ICLR 2021
REFERENCES
Debraj Basu, Deepesh Data, Can Karakus, and Suhas Diggavi. Qsparse-local-sgt Distributed sgd with quantization, sparsification, and local computations. In Advances Neural Information Processing Systems, pp. 14695-14706, 2019.
Keith Bonawitz, Hubert Eichner, Wolfgang Grieskamp, Dzmitry Huba, Alex Ingerman, Vladimir Ivanov, Chloe Kiddon, Jakub Konecny, Stefano Mazzocchi, H. Brendan McMahan, Timon Van Overveldt, David Petrou, Daniel Ramage, and Jason Roselander. Towards Federated Learning at Scale: System Design. SysML, April 2019. URL https: //wp://wwwwww// www.waysml.com coccll//11////// 193. pdf]
Gregory Cohen, Saeed Afshar, Jonathan Tapson, and André van Schaik. EMNIST: an extension of MNIST to handwritten letters. arXiv preprint arXiv:1702.05375 2017.
Jeffrey Dean, Greg S. Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Quoc V. Le, Mark Z. Mao,
Mare' Aurelio Ranzato, Andrew Senior, Paul Tucker, Ke Yang, and Andrew Y. Ng. Large scale distributed deep networks. In Proceedings of the International Conference on Neural Information Processing Systems, pp. 1233-1231, 2012.
Jack Goetz, Kshitiz Malik, Duc Bui, Seungwhan Moon, Honglei Liu, and Anuj Kumar. Active federated learning. ArXiv, 2019.
Farzin Haddadpour and Mehrdad Mahdavi. On the convergence of local descent methods in federated learning. arXiv preprint 1910v: 14425, 2019.
Samuel Horváth and Peter Richtárik. A better alternative to error feedback for communication- efficient distributed learning, arXiv preprint arXiv:2006. 1077, 2020.
Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown. Measuring the effects of non- non-identical data distribution for federated visual classification. http:://arritsorr//b//////// 06335, September 2019.
Zhouyuan Huo, Qian Yang, Bin Gu, Lawrence Carin, and Heng Huang. Faster on-device training using new federated momentum algorithm. arXiv preprint arXiv:2002.02099, 2020.
Angela H. Jiang, Daniel L. K. Wong, Giulio Zhou, David G. Andersen, Jeffrey Dean, Gregory R. Ganger, Gauri Joshi, Michael Kaminksy, Michael Kozuch, Zachary Lipton, and Padmanabhan Pillai. Accelerating deep learning by focusing on the biggest losers, 2019.
Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurelien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. L. D'Oliveira. Salim El Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adria Gascon, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaid Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konecny, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrede Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Ozgur, Rasmus Pagh, Mariana Raykova, Hang Qi, Daniel Ramage, Ramesh Raskar, Dawn Song, Weikang Song. Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramer, Praneeth Vepakomma, Jianyu Wang. Li Xiong, Zheng Xu, Qiang Yang, Felix X. Yu, Han Yu, and Sen Zhao. Advances and open problems in federated learning. arXiv preprint (0Xiv:9912.04977 2019.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank J Reddi, Sebastian U Stich, and Ananda Theertha Suresh. SCAFFOLD: Stochastic controlled averaging for on-device federated learning. arXiv preprint arXiv:1910.06:: 2019.
A. Katharopoulos and F. Fleuret. Not all samples are created equal: Deep learning with importance sampling. In Proceedings of the International Conference on Machine Learning (ICML), volume 80 of Proceedings of Machine Learning Research, pp. 2525-2534, 2018.
A Khaled, K Mishchenko, and P Richtárik. Tighter theory for local SGD on identical and heteroge- neous data. In The 23rd International Conference on Artificial Intelligence and Statistics (AISTATS 2020), 2020.
10

---

Under review as a conference paper at ICLR 2021
Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian U Stich. A unified theory of decentralized SGD with changing topology and local updates. arXiv preprins arXiv:2003.10422 2020.
Yassine Laguel, Krishna Pillutla, Jérôme Malick, and Zaid Harchaoui. Device heterogeneity in federated learning: A superquantile approach. ArXiv, 2020.
Tian Li, Maziar Sanjabi, and Virginia Smith. Fair resource allocation in federated learning. arXiv preprint arXiv: 1905 10497, 2019.
Xiang Li, Kaixuan Huang, Wenhao Yang. Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data. In International Conference on Learning Representations (ICLR), July 2020. URL (ttpstts:: htraaaaxvv.rrrge abs/ 020899
Lingjuan Lyu, Jiangshan Yu, Karthik Nandakumar, Yitong Li, Xingjun Ma, Jiong Jin, Han Yu, and Kee Siong Ng. Towards Fair and Prrrccc-reesrving Federated Deep Models. IEEE Transactions Parallel and Distributed Systems, May 2020.
Grigory Malinovsky, Dmitry Kovalev, Elnur Gasanov, Laurent Condat, and Peter Richtárik. From local SGD local fixed point methods for federated learning. arXiv preprint arXlv:2004.01442 2020.
H. Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agoura y Arcas. Communication-Efice Learning of Deep Networks from Decentralized Data. International Conference on Artificial Intelligenece and Statistics (AISTATS), April 2017. URL https://
atxiv.org// abs 602 05629
M. Mitzenmacher. The power of two choices in randomized load balancing. PhD thesis, University of California Berkeley, CA, 1996.
Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 4615-4625, PMLR.
Long Beach, California, USA, 09-15 Jun PMLR.
Takayuki Nishio and Ryo Yonetani. Client selection for federated learning with heterogeneous resources in mobile edge. In IEEE International Conference on Communications, pp. 1-7, May 2019.
Reese Pathak and Martin J Wainwright, FedSplit: An algorithmic framework for fast federated optimization. arXiv preprint urXiv:2005.05238, 2020.
Krishna Pillutla, Sham M. Kakade, and Zaid Harchaoui. Robust aggregation for federated learning. arXiv preprint 1912.13445, 2019.
13445
Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and Brendan McMahan. Adaptive federated optimization. arXiv preprint arXiv:2003.00295. 2020.
Mónica Ribero and Haris Vikalo. Communication--fficceeen federated learning via optimal client sampling. ArXiv, 2020.
Yichen Ruan, Xiaoxi Zhang, Shu-Che Liang, and Carlee Joe- be-Wong. Towards flexible device partici- pation in federated learning for non-iid data. ArXiv, 2020.
Anit Kumar Sahu, Tian Li, Maziar Sanjabi, Manzil Zaheer, Ameet Talwalkar, and Virginia Smith. Federated optimization for heterogeneous networks. hutps://artivorggbb/////10.0001. January 2019.
Farnood Salehi, Patrick Thiran, and
Elisa
Celis.
Coordinate descent with
bandit sampling. 2018 URL
http: http:://papers..m nips. htt.ips..c/pppppe /aper/
7 band -aaddittmmmlllammmm wag.pling..pl

---

Under review as a conference paper at ICLR 2021
Vatsal Shah, Xiaoxia Wu, and Sujay Sanghavi. Choosing the sample with lowest loss makes sgd robust. In Proceedings of the 23rd Internationaal Conference on Artificial Intelligence and Statistics
(AISTATS 2020), 2020. BRLhhtps::/ /ttpss://aaxvvvi wwwpxiv.org/abag. wttp:/r//aabs.oo..1.// 03316
Sebastian U Stich. Local SGD converges fast and communicates little. arXiv preprint
0777777805 2018.
Sebastian U Stich and Sai Praneeth Karimireddy. The error-feedback framework: Better rates for SGD with delayed gradients and compressed communication. arXiv preprint (009,059000053330 2019.
Jianyu Wang and Gauri Joshi. Cooperative SGD: A unified framework for the design and analysis of communication-eficcentt SGD algorithms. arXiv preprint 1808 2018. URL
https://arxiv.cmm org/ abs/ 808 07576
Jianyu Wang and Gauri Joshi. Adaptive Communication Strategies for Best Error-Runtime Trade-off's in Communication-Elficcen Distributed SGD. In Proceedings of the SysML Conference, April 2019. URLpttts:://artt
absggaabs/11100 08313
Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and H. Vincent Poor. Tackling the Objective Inconsistency Problem in Heterogencous Federated Optimization. preprint, May 2020. URL
https::/azxiv..org// http:////.02000...... 2017000777773
Blake Woodworth, Kumar Kshitij Patel, Sebastian U Stich, Zhen Dai, Brian Bullins, H Brendan McMahan, Ohad Shamir, and Nathan Srebro. Is local SGD better than minibatch SGD? arXiv preprint arXiv:2002.07839 2020.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mmist: a novel image dataset for benchmarking machine learning algorithms. https///uxixoor//u/////700..0000 aug 2017.
Han Yu, Zelei Liu, Yang Liu, Tianjian Chen, Mingshu Cong. Xi Weng, Dusit Niyato, and Qiang Yang. A fairness-aware incentive scheme for federated learning. Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society, pp. 393-399 2020.
Hao Yu, Sen Yang, and Shenghuo Zhu. Parallel restarted SGD for non-convex optimization with faster convergence and less communication. arXiv preprint 1007v:1807.06629 2018.
Xinwei Zhang, Mingyi Hong, Sairaj Dhople, Wotao Yin, and Yang Liu. FedPD: federated learning framework with optimal rates and adaptivity to non-lID data, arXiv preprint arXiv:2005. 1418, 2020.
12

---

Under review as a conference paper at ICLR 2021
A
ADDITIONAL THEOREM
Theorem A.1 (Convergence with Fixed Learning Rate). Under Assumptions 3.1 to 3.4 a fixed learning rate yj I min 2pB iL above, the error after T iterations of federated averaging with partial device participation satisfies
1. where == =++ 3p and any client selection strategy π as defined
8
F F
W
F
4 32r + o² + + 2T P))
L
1 7i (1 1
3p I²²
F(wlo)) F
1
8+
Vanishing Term
4Ln 32 o² GPLL
8L 7) 118 + 3p)
118 + 3p)
Non-vanishing bios
As T' + 0o the first term in 8 goes to O and the second term becomes the bias term for the fixed learning rate case. For a small 7/, we have that the bias term for the fixed learning rate case in
Theorem A.1 is upper bounded by S/T
1-1 1) which is identical to the Secaying-learning rate case.
3p
The proof is presented in Appendix D
B PRELIMINARIES FOR PROOF OF THEOREM 3. AND THEOREM A.
We present the preliminary lemmas used for proof of Theorem 3.1 and Theorem A.I We will denote the expectation over the sampling random source S(t) as Est and the expectation over all the random sources as E.
Lemma B.1. Suppose F& is L L-smooth with global minimum at w then for any wa in the domain of Fk. we have that
[V& < 2L(Fx(ww) Fx(w))
(9)
Proof.
1 [FL(we) VFL(WW))
(L(w)) -
- -VVAW))(VVP We -w)) > 2L
(10)
Fa(WH) - Fk(w)) 2
2L [Fl(w>)]1
(11)
Lemma B.2 (Expected average discrepancy between ((()) and w for E Stt))
1
E0
[w(
( (01 ?G?
(12)
m
AESSO)
Proof.
Σ
[ww(t)
-000-w01111 12
w
(w() (())
(13)
kES
(ES())
(')((t)
1|
(1)
w 1
(14)
m
kES(O ReSii
[w(())
(t)
(1)
(15)
m 2
Righ k.kes
13

---

Under review as a conference paper at ICLR 2021
Observe from the update rule that k k' are in the same set S(t) and hence the terms where is = k' in the summation in (14) will be zero resulting in (15). Moreover for any arbitrary t there is to such that 0 - t to < that We (to) =
(to) since the selected clients are updated with the global model
at every т. Hence even for an arbitrary we have that the difference between || ke - - w=("1 is upper bounded by 7 updates. With non-increasing ?)2, over t and Tot S 2mp. (15) can be further bounded as,
1
|
10 W
Σ
now (w -5 9h ( . 1>
(16)
m²
m
kFk. K,K Estt)
K kt Esto)
t=
to+r-1
nio
[l (w (10) 9* ( -.l y)
(17)
m
kek! kt,k' (l(e))())
t
ta+r-1
nio
22 (w/) (0 )1 + (w ( . (18)
m
kek! k k Es(t)
t=
By taking expectation over
18
2no T mn
10 T--
i0)
WE
19119
E
(wl
( : =(001 + 1111l(9 (W/" 24 )1')
(
ky k, Es()))()
Right k. (.K'S(())
(19)
2nh T m²
futr-1
Egoll
Σ 2G immo
(20)
N. E()))
2nh, T Egt m²
Σ 2TG2
(21)
16m (m- 1)7222
(22)
m < 1677 GG2
(23)
where (2 is because there can be at most m(m 1) pairs such that + k in S(t).
Lemma B.3 (Upper bound for expectation over || wwI 1|2 for any selection strategy IT). With E[-]. the total expectation over all random sources including the random source from selection strategy we have the upper bound:
E ((()))
w
E
|w
w" w'1
(24)
m
kES
Proof.
[(]
(1)
w=] = [|| m
Σ
w
(0)
w 12] = [1|
Σ
(w (0) - ww
(25)
KESS
kE(
E
w
11
(26)
KES(
14

---

Under review as a conference paper at ICLR 2021
C PROOF OF THEOREM
With ((0) 1 in ExEso go (!) ) as defined in Section 2 we have that
k
[ w'1l2 = |/(l 17.8"" w' 1|
(t)
(27)
= -|(((0 1 (1) w'
TJ
VF
Th
Σ )1
(28)
m
m
AES
RESW))
-1|w (1)
w
Σ
VV
1|2 + The
Σ VFL(W - 10
)
m
m
SE
RESII)
+ 277 (w(t) (8)
w m
T/
(W
(8)
Σ ) (29)
m
RES
KESO
2n (w =1/w(0) w0
VF W
KES
+ 27 (w(1)
The Σ w'
(
1
Σ ( gg
RES(O)
KES())
Aa
+ mh
Σ
VWu (0 + nfl
1
-
(30)
kES(O
RES(O
A3
A4
First let's bound A1.
2m
- -2nc
w
(w
Σ (w -w", (W(
(31)
m
m
AESIC
KES())
277
(w(t) (F&(( w
217
Σ (w
w', (F&(((())
(32)
m
m
KES
wx 1 + m (VF (4) 1p) (w())
27
(w (0) 10---w , (w("))
m
1/t
m
kES
kEST
(33)
1
Σ
(l() 10 + ?
Σ
[VF
2n
Σ
(wh (t) w', (w)
m
KES())
KES())
kES
(34)
1 Σ
[w(())
w 11
2
Σ (Fa(w FE)
m
m
KES())
RES(O)
(35)
2tte
Σ
(w()) w", (FK(((
m
kES
(|((1)
w 10)11 112
2
(Fa(W Fi)
m
m
KES())
KES
(36)
2T/
(F)(W()) - Fx(w") )) + 11
1/W w11 12
(t)
m
2
kES())
2La
< 16 72
Σ
[w (t) w+1 +
Σ (0) FE) FFF)
m
m
kES
RES
(37)
2770
Σ (FL( Fk("))
m
kEStO
15

---

Under review as a conference paper at ICLR 2021
where (33 is due the AM-GM inequality and Cauchy-Schwarz inequality, 35 is due to
Lemma B.
36 is due to the j-convexity of Fk, and (37) due to Lemma B.2 Next, in ex-
pectation, E 2
due to the unbiased gradient. Next again with Lemma
B. we bound Ag as
follows:
1/1
Σ m kES
1
o kES 2L
Σ
(38)
m
(F&(w (1) ( FE)
-FF
(39)
kES
Lastly we can bound A4 using the bound of variance of stochastic gradients as,
Binll Σ
-
-
11
Bll
Σ
(ox
W -2 (W (40)
kESt
keStt)
"
soll
Σ
(wlg
(2) x(,) ( (2)
(41)
m²
(ES())
o2
(42)
m
Using the bounds of A1, A2, As, As above we have that the expectation of the LHS of is bounded as
[[[[w((++])
w=1
[B[[[
w1
Thp E m
l/ &
w1
162
RES())
0/
AL
E
(w& (1) -FE)]
27k E
Σ (Fa(w())-
Fx(w"))]
(43)
m
m
m
KES!!)
kES
S(1 Mefz)
[||[(( (t)
11-) + 72
112
02
4L
2n EE|
B Σ (Pa(w! FFE]
Σ
- Fx(w"))]
(44)
m
m
m
RES())
kESU
As
where is due to Lemma different form as:
B.3 Now we aim to bound As in
First we can represent A5 in
E
AL
Σ
(Fa(W
(1)
F2)
2nJ
Σ (Fa(W (1)) Fk(w"))]
RESU))
RES
EE m
4L
Σ
(w
(t)
2Tk Σ Fu(w
(9)
217
Σ (Fz - Fx(w"))
m
m
kES()
kESte
kES(
2m
Σ Fi
ALm
Σ Fil
(45)
m
kES
kESW
2mr
(2Lm
(Fi(w (1) FE)] + 2mp
Σ (Pa(w")-FH)
(46)
RESU)
kES(
Ae
16

---

Under review as a conference paper at ICLR 2021
Now with te < 1/LL)) and V4- 2n((1 2Lm)). we have that Ag can be rewritten and bounded as
Pt
Σ (F((w ) - Fx(W(() + Fk((W))) - Fi)
m
KESU))
Pt
E (Fo(WE) ()) Fa(w("))=
Ut Σ (Fe(w!!)) FFE)
(47)
m
m
kESU)
kES
Σ (VFL(W")), -w(')) + フー w/ (t) - w//)|]]
- Σ (Fi(W()) - FR)
KES
kES(()
(48)
11
mcL(E((W")) - -F()+ 217r
||
(1)
w(t) 12
Σ
(Fx(w(!)
F7
m
m
RES(
KES
(49)
M (1 - 1(L)
Σ (F((w())) - FF)
+
Vt.
Vil1
Σ
Iw (t) - w())pp
(50)
2mpm
2m
KESU!)
kES())
<
Pt (1 L)
Σ (Fi(w(0)) Fx)
1
Σ
l/
w01
(51)
m
kES
kES(1)
where 488 is due to po-convxity, (49) is due to Lemma B. and the AM-GM inequality and
Cauchy-Sehwarz Schwarz incquality, and 51 is due the fact that of As we can upper bound Aş as
1. Hence using this bound
2
E
4Lm
(Fx(W (1) FR)
2m7
Σ (F&(w (0) Fa(W"))]
m
m
kE)())
kE)())
1 E
1| (1) w1)
11 (1 17, LE
Σ (FL(W")) FX) -F
171
m
RES((O)
RES(O
217 E
+
(Fa(w") Fi)
(52)
m
kES
1t (1 - 1/p L Σ (F)(w())) - FF) + 2nkt E
Σ (Fe(w") - FX)
(53)
m
RES
KES(
K
=161 v1(1 - -n())E(ppS( W(FL//)) (FW)
Σ pk F2))
+ +21.Bi(SS(T, w0110/-11), w Σ PMF
(54)
Σ paFFt +2
(55)
Ay
17

---

Under review as a conference paper at ICLR 2021
where 54 is due to the definition of p(S(ST, (T., w). w') in Definition 3.2 and (55) is due to the definition
of I' in Definition 3.1 and the definitions of p. in Definition 3.2
We can expand A7 in 55 as
K
- (1 L) F( [
(56)
-1
L)
PM (BLFr(W(O) F -FFF
(57)
K
K
(1
17: pp
Pk
( 1 F*) - 11(1 - LT
Σ
Pk
(F*
Fi
(58)
k=1
(1
L pp E
F*) 11(1 LLDT
(59)
11
mi 1)p
E ((())
w" w01 - m1 1TD
(60)
[B|| w(()
w 119 - (1 - 2Lm )1 mu m:
(61)
8
37ppp
E w01 - 2np + 6n7 PLT
(62)
8
where (60) is due the 1 convexxiy 61 is due -1 (1 2T) (1 L, < - and 62 is
due to -1 21 - LL S -(1 (13Lm))
3mm. Hence we can finally bound As as
4T, E
Σ (F&(w (t)) Fi!)
21T m
Σ
(F Fs(("))]
kES(1)
KES!1)
3npp
|E|l w(th w/ (11 + 2nd (p - P) + ne (6pL1' +9
(63)
8
Now can bound |[[| [[|[w((+1))_ - w=113 as
3p
E| w((+1)
w11 s 1-71H TT [1
E B|| w
8
(64)
o²
+ 1/² 327 3272
+ +6pL[
+ +m - p))
m
By defining A.+1 = EE| | (++1) we have that
w+1 || B =
1
37 8
C 32- + +6PLI, D = (1 P).
A I - (1-nuBB)a A. + c + +
(65)
By setting A
S
B and
B >
pB > 0 by induction we have that
1
84y"
14y
/
max //|lw(0) 11
3uB (8 + DD((+ +
(66)
Then by the L-smoothness of F(.), we have that
L +
[[F(w(())] F*
<
A
<
(67)
2
2 2 +t
D PROOF OF THEOREM A.I
With fixed learning rate 17 17, we can rewrite 165 as
A++1 S (1- - nuB) A1- + 2C + nD
(68)
and with v S min 2 J7 using recursion of (68) we have that
n + nD
A s (1 nuB)'
(1 (1 - --nBB)
(69)
nuB
18

---

Under review as a conference paper at ICLR 2021
Using A $ [ (F(w(()) F*) and L-smoothness, we have that
11
F(w(())) - v -1 - (1-))n))((( F² + L(nC + D)
(1 - (1 nubb)))
(1-nn1B))) (70)
/
2uB
3p L mp 1+
(F(w - F²)) + 4L + +D) 118 + +3)
1 mhl II+ 3p
8 ]
(71)
8
E EXTENSION: GENERALIZATION TO DIFFERENT AVERAGING SCHEMES
While considered simple averaging scheme where (((+1) ExEsto (w!" (1)
nigh (w
we can extend the averaging scheme to any scheme q such that the averaging weights que are invariant in time and satisfies Lkes( Qh for any L. 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 q: p& K/m. With such averaging scheme q, we denote the global model for the averaging scheme q as w(!), where ((+1) &
Ekeste Us (w() mo.g((((")) and the update rule changes to
(t)
((+1)) w(() n(g((t) -w((
Th
Σ KESO)
(72)
where (*) Σ E la9k (w (1)
(()) We show that the convergence analysis for the averaging In the case of the averaging scheme q, we have that
scheme is consistent with Theorem 3.1
Lemma B.2 and Lemma B.3 shown in Appendix B each becomes
M (1)
(+) 1'1 S k
1)72G²
(73)
RES
E B[|l
w" 11
mE
Σ
gkllw/
(1)
(74)
kgS
Then, using the same method we used for the proof of Theorem
3.T we have that
E (++1)
w- 11] (1
M/H
E
((()
w
112] o0 16m22m (m 1)n2""
m
E
2L + m)
Σ
(F (t) - FX) 21P
Σ
qu (F(((WW))) ( Fx(w))
(75)
kESI
kEStO
M
By defining the selection skew for averaging scheme q similar to Definition 5l
(Q(S((T, ((S((T,),,w, w), w') Es(r.w) EKES(H.W)) 9:: (F& (Ww') F )
2 0,
(76)
F(w') xm=1 PxPF
and
Pq min Pq (S(r,, w), w')
(77)
w.w'
pq max Pq (S( w), w") max Es (S(s.w) LEkES w) gk (hee)aaFFFFFeFF (Fe(w*) - FF)
(78)
w
With 7, < <1/(2L(1 + m)), using the same methodology for proof of Theorem 3.1 we have that M
becomes upper bounded as
E
2L (1 + m)
Σ
qu (Fa FE)
-1t Σ (Fx((W (1)) Fk(ww)))
(79)
kE)
KE)(1)
niHPa
[l| (1)
- I Pa) 16m 1m 1)n 2L m)
2
(80)
19

---

Under review as a conference paper at ICLR 2021
Finally we have that
m + Pq )
Ell [([ (++1)
-w
- 1 77f4
E|1 (i(l) - w + 2n -Pa)
(81)
132m (m 1)r² + 22(2 + mm
By defining Ae+1 [B[ W (1+1) wx w*113], B =
3g 2:
C 32m (m 1)- + - 2T
T, = (pn pa). we have that
51 (o1--mpBBa + nH. + nnD
(82)
Again, by setting A 177 17t i-
3 and 1
? by induction we have that
nB"
+ max
>/|l w01
+DB(+++()))))
(83)
BuB
Then by the L-smoothness of F.)), we have that
+b
E [[F(w(())] F
S A
5
(84)
7
+
With 3 m. 7
8 4m(1+m)) and T) E441
we have that
1
E[F(W(T))
F*
Lmn' (32mm2 1) + +
2L2m(m + 2)r
L
w=12
(T' 7))
p²8a
122
(85)
Vanishing Error
2LT
Pq
+
P
Pa
Non-vanishing bias
which is consistent with Theorem 3.1
F EXPERIMENT DETAILS
Quadratic Model Optimization. For the quadratic model optimization, we set each local objective function as strongly convex as follows:
1
(w(w)= 2 w HAW - e 70 H e
(86)
H3 E Rex= is diagonal matrix H = I with h ~ 211 20) and e R is arbitrary vector. We set the global objective function as ((w) Ek= Pk: (w), where the data size pa follows the power law distribution P(æ; a) a= 0 < x < 1, a 3. We can easily show that the optimum for (w) and F(w) is w = H ey and w = (Ek Pa H 'EE p&ex) respectively. The gradient descent update rule for the local model of client l in the quadratic model optimization
w (1+1) W HH ek.
(87)
where the global model defined as w (++1) = + Σ Ske W (t+1) We sample m = KC clients for every round where for each round the clients perform gradient descent local iterations with fixed learning rate 1) and then these local models are averaged to update the global model. For the implementation of Tadapow-d- d was decreased half from K for every 5000 rounds. For all simulations we = 2, 5, 2 10
For the estimation of p and ñ for the quadratic model, we get the estimates of the theoretical P. values by doing grid search over large range of possible w, w' for p(S(m, w), w') and
20

---

Under review as a conference paper at ICLR 2021
((S(TT, w), w") respectively. The distribution of S(T,, w) is estimated by simulating 10000 iterations of client sampling for each π and w.
Logistic Regression Synthetic Dataset. We conduct simulations on synthetic data which allows precise manipulation of heterogeneity. Using the methodology constructed (Sahu et al. 2019), we the dataset with large data heterogencity, Synthetic(I.)), We assume in total 30 devices where the local dataset sizes for each device follows the power law. For the implementation of Tadspow-d- d was decreased to d = from d K half the entire communication rounds. We set the mini batch-size to 50 with T = 30, and 0.05, where is decayed to n/22 every 300 and 600 rounds.
DNN on FMNIST Dataset. We train 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 Dirx (a) (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
use mini-batch size of b 64, with r 30 and 0.005, where 7j is decayed by half for every 150, 300 rounds. We experiment with three different seeds for the randomness 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 one client in the federated learning setting. The algorithms are implemented by PyTorch.
Pseudo-code of the variants of pow-d: epow-d and rpow-d. We here present the pseudo-code for Tepow-d and T-pow-d- Note that the pseudo-code for Repow-d Algorithm I can be generalized the algorithm for po by changing
Eςeê. [(w,{) Fe(w).
Algorithm Pseudo code for epow-d: computation efficient variant of pow-d
1: Input: m, d, Pk for & E [K], mini-batch size = LEx for computing Eees, f(w,
2: Output: 8(t)
3: Initialize: empty sets S()) and
4: Global server do
5: Get - {d indices sampled without replacement from [K] by pa
6: Send the global model w()) to the d clients in
7: Receive [EW] Σeeê f(w, {) from all clients in A
8: Get (44) [m clients with largest
Eşee. f(w, (break ties randomly))
9: Clients in A in parallel do Create mini-batch & from sampling samples uniformly at random from B& and compute
[c,] EςeE fww. g) and send it to the server
11:
return (()
21

---

Under review as a conference paper at ICLR 2021
Algorithm 2 Pseudo code for rpow-d: computation & communication efficient variant of pow-d
1: Input: m, d. Pk for & [K]
2: Output: S(t)
3: Initialize: empty sets ((1) and A, and list Amp with K' elements all equal to inf
4: All client k E 1(t do
5: For t mod 0, send rb E Ei=t-r41 Egeeto f(wk .)) the server with its local model
6: Global server do
7: Receive and update Amplit [k] tob Ei EgEe! f(w
(1) .5) for S(t-1)
8: Get A = {d indices sampled without replacement from [K] by pa}
9: Get S(t) [m clients with largest values in [Amp[t] for A), (break ties randomly))
10: return ((()
G ADDITIONAL EXPERIMENT RESULTS
G.1 SELECTED CLIENT PROFILE
We further visualize the difference between our proposed sampling strategy poo-- and the baseline scheme Tand by showing the selected frequency ratio of the clients for K = 30, C' = 0.1 for the quadratic simulations in Figure ? Note that the selected ratio for Trand reflects each client's dataset size. We show that the selected frequencies of clients for poo. 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-OP HOWER-OF-CCOE OF-CHOICE that weighting the clients' importance based 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 Trand is less biased than pow.
rand
pow-d, d=6
Selected ratio
0.04
Selected ratio
0.05
0.0
0.00
0.00
20 26 59009 20
Client index
Client index
Selected client profile for Trand
(b) Selected client profile Tpoo-d
Figure 7: Clients' selected frequency ratio for optimizing the quadratic model for Frand and Too--d with K 30, C 0. The selected ratio is sorted in the descending order.
G.2 COMMUNICATION AND COMPUTATION EFFICIENCY LARGER IIETEROGENEITY
In Table 2 we show the communication and computation efficiency POWER-OF-CHOICE for
2, as we showed for a 0.3 in Table in Section 5 With C = 0.03 fraction of clients, Tpow-d: Tepow-d; and Trpow-d have better test accuracy of at least approximately 10% higher test accuracy performance than (Trand C 0.1). R&0 for Tooo-d: Tepow-d, Trpow-d is 0.61, 0.66. 0.73 times that of (Taand, 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 (Trand, C= 0.1) and still get higher test accuracy performance. The computation time foomp for Topow-d and Trpow-d with C' = 0.03 smaller than that of (Tandd C = 0.1).
22

---

Under review as a conference paper at ICLR 2021
Table 2: Comparison of Reo, toomp (sec), and test accuracy (%) for different sampling strategies with
2. The ratio Rso / (Rso for rand, C' = 0.1) and feomp / (eomp for rand, C = 0.1) are each shown in the parenthesis.
0.1
C 0.03
rand
rand
pow-d, d = 6
cpow-d, d = 6
rpow-d. d = 50
afl
Reo
135
136(1.01)
82 (0.61)
89 (0.66)
99(0.73)
(31(0.97)
feump
0.42
0.36(0.85)
0.46 (1.08)
0.38 (0.88)
(.36(0.86)
0.36(085
Test Acc.
63.50:12.74
66.0311.44
73.81 1.14
73.36:11.17
72.52:0.899
70.64:11.99
K- 100, C-0.03
K-100, C-0.03
K=100, C-0.03
K=100, C=0.03
rand
Tost aocursoy
100
Training loss
pow-d, d-15
rpow-d, d-20
Test accurra
S
Training loss
spow-d, d-20
pow-d, d-6
8.4
3.4
rund
rand
-30
pow-d d-15
d-6
poo-dd d, 8-20
poo-d. d-20
200
105
200
250
20
10%
200
4015
Communication round
Communication round
Communication round
Communication round
(a) Test accuracy and training loss a 2
(h) Test accuracy and training loss for a = 0.3
Figure 8: Test accuracy and training loss in the virtual environment where clients have intermittent availability for K = 100, C = 0.03 with Trand- Tpow-ds and Tppowdd on the FMNIST dataset. For both 2 and
3, pow-d achieves approximately 10% higher test accuracy than rand-
G.3 INTERMITTENT CLIENT AVAILABILITY
In real world scenarios, certain clients may not be available due to varying availability of resources such battery power or wireless connectivity. Hence we experiment with 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 more realistic client selection scenario where, for example, we have different time zones across clients. For each communication round, we select 0.1 portion 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 wireless connectivity. In Figure g we show that now and Trpow-d achieves 10% and 5% test accuracy improvement respectively compared to Frand for a = 2. For a = 3, both Toow.d and Tepow shows 10% improvement. Therefore, we demonstrate that a realistic scenario where clients are available intermittently.
also performs well in
G.4 RESULTS FOR DNN ON NON-IID PARTITIONED EMNIST DATASET
To provide further validation of the consistency in our results of π poo-- 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 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,
use 6 64, F 30, and 17 0.005 where 7) is decayed by half at round 300.
In Figure we show that Tpow-d performs with significantly higher test accuracy than Fand for varying d for both = 2 and 0.3. For = 2, Tan is able to follow the performance of p in the later communication rounds, but is slower achieving the same test accuracy than Tpow-d- Moreover, in Figure I0 show that Repow-d works good Tpow-d for both large and small data heterogeneity. The performance of ग Tepow falls behind pp d and Tepow for smaller data heterogeneity, whereas for larger data heterogeneity, appowd is able perform similarly with Tpow-d d and Repow-d-
23

---

Under review as a conference paper at ICLR 2021
K~500, Cm0.03
K 500,
C=0.03
K-500, C-0.03
K-500, C-0.03
pow-d,
2 S.
-1.2
pow pow-d, de30
Tost necuracy
30 8
Adc 24
Training loss
powed, d-75
Test accuracy
2
Training loss
0.4
pow-d, d-75 ui
aft
nind
rand
pow-d
30
g
pou-4, d 10
pow-d, d
pow-d, d 45
-g.
6-75
d:75
at
afl
-0.5
100
200
300
10 200
100
100
200
101
100
200
Communication round
Communication round
Communication round
Communication round
(a) Test accuracy and training loss for a
(b) Test accuracy and training loss a 0.3
Figure 9: Test accuracy and training loss for different sampling strategies for K = 500, C 0.03
with Trand Tpoowdd and Tan on the EMNIST dataset.
K=500, C=0.08
K-500, C-0.07
K-500, C-0.03
K-500, C-0.03
nnd
rand
4:30
-0.3
d:30
Tost aecuracy
Training loss
spew-d, d-30
Test accuracy
Training loss
spow d-10
3. E.S.
rpow-4, d-250
0.4
spow J:2
cad
mnd
12 = E
d-30
g.
spow-d, d-10
spowed,
sponsl, d 250
spored, d 250
Communication round
Communication round
Communication round
Communication round
(a) Test accuracy and training loss for
(b) Test accuracy and training loss for 0.3
Figure 10: Test accuracy and training loss for different sampling strategies for K 500, C 0.03 with Trand Tpow-ds Repow-ds Trpow-d, and Tan on the EMNIST dataset.
G.5 EFFECT OF THE FRACTION OF SELECTED CLIENTS
K-100, C-0.10
K-.10,C=D.10
K-100, C-0.10
K-100,C-0.10
80
-0.1
-0.1
Test acquracy
70
Training loss
-0.2
rand
pow-d, d-50
opow-d, d-50
Test Stctura
Training JONS
-02
rand
pow d, d-20
spow-d, d-20
bg
rand
rpow-d, d=50
rand
spow-d, d-50
pow-d, d=30
afl
pow-d, d-20
cpow-d, d=50
9.5
spow-d, d-20
rpow-d, d=50
0.6
rpow-d, d-50
all
all
10-0
105
200
400
230
1000
400 Communication round
200
Communication round
Communication round
Communication round
(a) Test accuracy and training loss for 2
(b) Test accuracy and training loss for 0.3
Figure 11: Test accuracy and training loss for different sampling strategies for K 100, C = 0.1
with Trand, dp Tepow Tipow and wall on the FMNIST dataset. For larger C = 0.1, Tow performs with 15% and 5% higher test accuracy than Taand for 2 and a 0.3 respectively.
In Figure IT for larger C 0.1 with 2, the test accuracy improvement for Too is even higher than the case of C 0.03 with approximately 15% improvement. Tepow-d performs slightly lower in test accuracy than Toow-d but still performs better than Trand and Tan- Tppow-d performs as well as Tan- For = 0.3, Toow-d: Repow-d: and Trpow-d have approximately equal test accuracy performance, higher than Frand by 5%. The POWER-OP COFERROFFOHOIEE strategies all perform slightly better than Tan. Therefore performs well for selecting larger fraction of clients, i.c., when we have larger C 0.1 > 0.03.
we show that POWER-OF-
G.6 EFFECT OF THE LOCAL EPOCHS AND MANI-BATCH SIZE
We present the experiment results elaborated in Section for the different parem-ear settings (b, r) E ((128,30), (64, 100)] in Figure 12 13
14 and 15 below.
24

---

Under review as a conference paper at ICLR 2021
K=100, C=0.03
K- K-100, C-0.03
K-100, C-0.03
K-100, C-0.03
72
rad
rand
pow-d, des
-22
pow-d, de5
Test accuracy
Training loss
pow-d, d-9
Test accuracy
Training loss.
pow-d, deg
pow-o, d-15
powed, d-15
red
04
af
cand
04
pow-d,
-30
pow- 4, dm5
pow-d, 6-9
20
pow- d-15
0.6
pow
0.
att
on
1010
120
200
-0.7
-0.7
200
300
Communication round
Communication round
Communication round
Communication round
(a) Test accuracy and training loss for =
(b) Test accuracy and training loss for 0.3
Figure 12: Test accuracy and training loss for randd 7 po and Faf for K 100, C 0.03 on the
FMNIST dataset with mini-batch size b = 128 and 30.
K=100, C=0.03
K-100,
C=0.03
K-100, C=0.03
K-100, C-0.03
-0.1
rand
Tos receuron Sornan 2
rad
d. d-15
powsd, den
Test aceuracy
Training loss
spewal d-15
Training lows
<pow-d,
pooedd d-50
mow-d d-30
spoe-d. d-15
pow d-15
4.5
puma-d, d-6
ded
0
20
mow d. 6:30
6.6
20
sponed, 4-50
uf
-0.0
1000
203
301
-0.7
2000 Communication round
100
200
102
100 2010
Communication cound
Communication round
Communication round
(a) Test accuracy and training loss for a =
(b) Test accuracy and training loss for a = 0.3
Figure 13: Test accuracy and training loss for Trand: Too ds Tepoo- ds Trpow and Tan for K
100, = 0.03 on the FMNIST dataset with mini-batch size 128 and 30.
K-100, C-0.03
K-100,
C-0.03
K-100, C-0.03
K-100, C-0.03
rad
rand
2
-2.2
dm6
-0.2
de6
Test accuracy
Tratning loss
pow-d, d, d-9
Test accuracy
Tramiing loss
pow-d d-9
d-15
pow-d, d-15
aft
04
off
rand
rand
30
pow-l d, d-6
pow-d, d-6
3.
d-9
pow d, d-15
pow d d-15
10
-0.
Communication round
Communication round
Communication round
Communication round
(a) Test accuracy and training loss for =
(b) Test accuracy and training loss for 0.3
Figure 14: Test accuracy and training loss for Frand x pow d. and Tan for K 100, C 0.03 on the
FMNIST dataset with mini-batch size b = 64 and 7 100.
K-100, C-0.33
K-100, C-0.03
K-100, C-0.03
K-100, C=0.03
50
12
pow-d, de15
pow d, dmd
Tost accuracy
Training loss
spon-d, d-15
Test aceuracy
2 2. "2
Training loss
spow-d, deo
spoud, d-50
rpow-d, d-30
30
8.A
all
rand
d-15
pow-d, deb
spor- d, d-15
2
spor
mow-d, d-50
aoww-d.d:50
100
200
300
100
200
300
100 200 300
Communication round
Communication round
Communication round
Communication round
(a) Test accuracy and training loss a =
(b) Test accuracy and training loss a = 0.3
Figure 15: Test accuracy and training loss for Taand Tpow-ds Tepow-ds Tipow-d. and Tat for K = 100, C 0.03 on the FMNIST dataset with mini-batch size b 64 and 7 = 100.
25


Reviews:
[{"review_id": "pPw-LZ4wSeA", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper analyzes the convergence of FedAvg with biased client selection strategies. And the new strategy power-of-choice is designed based on the convergence results. This new strategy is numerically compared with two benchmark strategies and shows faster convergence and higher testing accuracy.\n\nPros:\n1. The convergence analysis is new and novel. This paper provides the first convergence analysis for a general class of biased client selection strategies. New concept, selection skew, is introduced as the measure of strategies. Based on the new concept, the analysis quantifies how the bias of the strategy affects the convergence speed of FedAvg.\n2. New strategy pow-d is proposed based on the insights of the convergence analysis. The performance of pow-d is impressive in the FMNIST experiment, where it significantly improves the test accuracy under random selection strategy.\n\nCons:\n1. Although the analysis is interesting and insightful, the effect of \\rho seems to be limited. There are three constant terms in the vanishing error term in Eq.(7). And only the first term will be decreased when increasing \\bar{\\rho}. However, it is not obvious if the first term is the dominating term.\n2. Is it possible to give an exact or estimated values of \\bar\\rho and \\tilde\\rho for different strategies in the numerical experiments?", "extra_scores": {}, "extra_text": {}}, {"review_id": "heSQ9GVM9-t", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##########################################################################\n\nSummary:\n\nThe paper analyzes a biased client selection policy in the context of the federated learning paradigm. \nIn particular, instead of random selection of the clients with a probability that is proportional to \nthe size of the local dataset, clients with higher local loss values are selected.\nDespite being already used as heuristics, the authors claim that their work is the first one to \npropose a convergence analysis of a biased client selection mechanism in the context of federated\nlearning. Under some (quite stringent) assumptions, the authors derive a global bound for the expected \nerror after $T$ iterations. The bound is composed of two terms: a vanishing term and a non-vanishing one\nwhich comes as a consequence of the biased client selection mechanism. From Theorem 3.1 it emerges clearly \nthat the biased selection mechanism poses a trade-off: on one hand the non-vanishing term increases the more biased is the selection, on the other hand the vanishing one benefits from the biased selection mechanism since the more biased is the selection the faster it will decay to zero.     \nThe biased selection mechanism comes with some additional computational and communication costs with respect to a fully random selection: the authors propose a couple of heuristics to alleviate these extra-costs. \nIn the experimental section the proposed method is evaluated on different benchmarks and with different datasets.\n\n ##########################################################################\n\nReasons for score: \n\nThe paper is well-written and the theoretical results look correct. At the same time, there are some weaknesses\n(see the section on Cons).\n \n########################################################################## \n\nPros:\n \n1. The paper takes is well-written and really easy to follow.\n\n2. The authors attempt to provide a more rigorous analysis to an already-in-use heuristic and it is the first time that such \nanalysis is carried out in this context.  \n\n3. The paper has a good balance across the sections and it touches on theory and experimental part in a balanced way.\n\n##########################################################################\n\nCons: \n\n 1. The assumptions on which the theoretical analysis is based are quite stringent and could be further relaxed (especially\nstrong convexity). \n\n 2. Incoherent benchmarks: the authors are not reasoning regarding the introduced assumptions and whether they hold. It actually seems that at least in the DNN case the assumptions are not holding since the landscape is notoriously non-convex. \n\n 3. Experiments only show the behavior of the heuristics pow-d. What happens when d=K? In order for the experiment to be in line with the theoretical results this case should be analyzed at least once. Introducing the extra random selection of $m\\leq d\\leq K$ clients could indeed change the setting and therefore the convergence.\n\n 4. Way too strong and unjustified statements, i.e. faster convergence to a global minimum (according to Th.3.1. it does not converge), convergence up to 3 times faster (in one benchmark, might easily depend on hyperparameter settings or on the heuristic added on top on power-of-chance).\n\n5. All the statements regarding the test accuracy are pure speculations as there are no theoretical and/or consistent and extensive empirical evidence which suggest that the biased selection mechanism leads to better generalization. Intuitively adding a bias in the selection should lead more easily to overfitting.\n\n\n##########################################################################\n\nQuestions during rebuttal period: \n\nPlease address and clarify the cons above \n \n#########################################################################\n\nInteresting General Aspect Not Considered\n\n1. local SGD iterations: how does $\\tau$ impacts on the convergence? Is it beneficial to perform more local SGD steps or does it become harmful for the convergence? How does this relate with the biased selection mechanism?\n\n2. first random selection of $d$ clients based on proportions of dataset: unbalanced work load might create inefficiency since the general method described is synchronized.\n\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "_-yMeg0Wmyr", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nIn terms of the assumptions on the loss functions, there is no improvement as the same assumptions are used in recent works [4,5]. The Assumption 3.4 seems problematic as together with Assumption 3.3 it implies that gradients of local loss functions $F_k$ are uniformly bounded. This is in conflict with Assumption 3.2 as local losses $F_k$ are assumed to be strongly convex. For instance, in papers [1,2,3] the Assumption 3.4 is not needed. Can the current theory be extended by relaxing Assumption 3.4 ?\n\nFor Definition 3.1 on local-global objectivity gap, it should be mentioned that this notion was defined and used earlier in [4]. It should be credited properly.\n\nThe metrics $\\bar{\\rho}$ and $\\tilde{\\rho}$ describing the skewness of client selection strategy, and their explicit effect on convergence rate (7) are interesting. It is also nice that the theory, e.g. Theorem 3.1, recovers the result of unbiased client selection case without any solution bias. Since Theorem 3.1 is generic and works for any selection strategy, it does not explicitly show a clear benefit of biased selection strategy over unbiased one. Biased selection strategy reduces the vanishing error term by $\\bar{\\rho}$, and adds a non-vanishing bias $Q(\\bar{\\rho}, \\tilde{\\rho})=O(\\frac{\\tilde{\\rho}}{\\bar{\\rho}}-1)$. So, based on the rate given in Theorem 3.1, biased selection is beneficial only if $\\bar{\\rho}>1$ and the difference $\\tilde{\\rho}-\\bar{\\rho}$ is small (formally it should be $O((\\bar{\\rho}-1)/T))$. The question is, can such biased selection strategy be designed so that it is theoretically better (or at least not worse) than unbiased selection strategy ?\n\nThe proof of the main Theorem 3.1 largely follows the proof of Theorem 1 of [4]. It seems that the proof of Theorem 3.1 deviates from the proof of Theorem 1[4] only in derivations (53)-(63), where biased-ness of the client selection kicks in and skewness metrics get involved. Such overlaps in proof techniques should be mentioned and some discussion is needed to highlight the novelty of the proposed analysis. \n\nUsing insights from Theorem 3.1, the paper proposes a client selection strategy (with two practical variations), called power-of-choice, which aims to speed up the convergence of vanishing error by maximizing rho_bar. However, it is not clear how the other metric $\\tilde{\\rho}$ would behave in this selection strategy. Although inspired from Theorem 3.1, I view the power-of-choice selection strategy as a heuristic idea as (i) it focuses only on the vanishing error term and does nothing to minimize the bias term, (ii) no theoretical estimates are developed for the metrics $\\bar{\\rho}, \\tilde{\\rho}$ in this specific selection strategy.\n\nWith points made above, the theoretical contribution of the paper is weak. I think, the paper would largely improved if it were developed a way on how to avoid the bias term while using biased selection. One possible way is to design a suitable selection strategy which allows to bound the bias. For instance, from the experiment shown on Figure 2.b, it is tempting to show that for the proposed pow-d selection strategy the bias term $(\\frac{\\tilde{\\rho}}{\\bar{\\rho}} - 1)$ is $O(d/K)$, which can be controlled via parameter $d$. Another possible way might be to incorporate some mechanism on top of FedAvg algorithm similar to what error compensation(or error feedback) does for biased (contractive) compression operators.\n\nExperiments are okay, but they use up to 100 clients which is far from the scale of typical FL applications. In addition, in the experiment shown in Figure 4.b, the training loss seems to be decreasing steadily and non vanishing bias term is not dominated there. As the vanishing error term reduces by choosing larger $d$, why in this experiment smaller $d=6$ performs better than larger $d=15$ ?\n\n\n[1] A Khaled, K Mishchenko, and P Richtárik. Tighter theory for local SGD on identical and heterogeneous data. In The 23rd International Conference on Artificial Intelligence and Statistics (AISTATS 2020), 2020.\n\n[2] Blake Woodworth, Kumar Kshitij Patel, Sebastian U Stich, Zhen Dai, Brian Bullins, H Brendan McMahan, Ohad Shamir, and Nathan Srebro. Is local SGD better than minibatch SGD? arXiv preprint arXiv:2002.07839, 2020.\n\n[3] Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian U Stich. A unified theory of decentralized SGD with changing topology and local updates. arXiv preprint arXiv:2003.10422, 2020.\n\n[4] Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data. In International Conference on Learning Representations (ICLR), July 2020.\n\n[5] Yichen Ruan, Xiaoxi Zhang, Shu-Che Liang, and Carlee Joe-Wong. Towards flexible device participation in federated learning for non-iid data. ArXiv, 2020.", "extra_scores": {}, "extra_text": {}}, {"review_id": "LRZwkZai-hG", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##########################################################################\n\nSummary:\n\nThis paper studies federated learning (FL) and proposes nonuniform sampling of participating clients. Clients are selected according to their losses; clients with big losses are likely selected. The proposed algorithm has a rigorous convergence analysis. The proposed algorithm is demonstrated powerful on small scale datasets.\n\n\n\n##########################################################################\n\nReasons for score:\n\nI find this submission a borderline paper. I am fine with either acceptance or rejection. This paper has theoretical guarantees and strong empirical advantages. But the actually used algorithm may not be very useful. The experiments are conducted on small datasets. I am not confident whether this work will have an advantage on large-scale data.\n\n\n\n\n##########################################################################\n\nPros:\n\n+ The idea of choosing participating clients according to loss is an interesting and reasonable idea.\n\n+ The non-uniform sampling of clients is proved to converge.\n\n+ The nonuniform sampling algorithm has a strong empirical advantage.\n\n\n##########################################################################\n\nCons:\n\n1. The actually used algorithm is the power-of-choice strategy. It firstly uses a uniformly sampled set of $d$ clients to compute losses and then sample a subset of $m < d$ clients out of the $d$ clients.\nHere is my question: The server needs to communicate with the $d$ clients from the candidate set. The server must wait for their responses. So the $d$ clients are actually active. Why not use all the $d$ clients to compute gradients? Is the proposed strategy comparable to using all the $d$ clients? \n\n2 FMNIST seems to be the only used dataset. The dataset is not big enough. Even if it is big enough, I would like to see empirical results on other datasets, e.g., MNIST, CIFAR10, mini-ImageNet, etc. Admittedly, this work has an advantage on FMNIST. But I am not convinced that this work is better in general.\n\n\n\n##########################################################################", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: In federated learning, distributed and resource-limited client nodes cooperatively train a model without sharing their local data. The results thus far on analyzing the  convergence of federated learning are restricted to “unbiased” client participation, where the probability of a client c being selected is proportional to c’s data size. This work presents the first convergence analysis of federated learning for biased client selection, and quantifies the impact of selection skew on time to convergence. Specifically, biasing toward clients with higher local loss is shown to be beneficial, and a protocol is developed based on this, to trade between convergence time and solution bias.

The paper is in general well-written, and develops a natural idea. 

The strong-convexity assumption is a concern: how much can it be weakened? The authors are also asked to run experiments systematically on (much) larger datasets. The test-accuracy and possible-overfitting concerns also need to be addressed in more depth. The authors are also encouraged to see how much Assumption 3.4---uniformly-bounded stochastic gradients---can be dispensed with. 

Decision: Reject