Optimal Client Sampling for Federated Learning
Authors: Wenlin Chen
Samuel Horváth
Peter Richtárik
Venue: NeurIPS 2021 Submitted (2021)
Keywords: Federated Learning
Distributed Optimization

Abstract: It is well understood that client-master communication can be a primary bottleneck in Federated Learning. In this work, we address this issue with a novel client subsampling scheme, where we restrict the number of clients allowed to communicate their updates back to the master node. In each communication round, all participated clients compute their updates, but only the ones with "important" updates communicate back to the master. We show that importance can be measured using only the norm of the update and give a formula for optimal client participation. This formula minimizes the distance between the full update, where all clients participate, and our limited update, where the number of participating clients is restricted. In addition, we provide a simple algorithm that approximates the optimal formula for client participation which only requires secure aggregation and thus does not compromise client privacy. We show both theoretically and empirically that our approach leads to superior performance for Distributed SGD (DSGD) and Federated Averaging (FedAvg) compared to the baseline where participating clients are sampled uniformly. Our approach is orthogonal to and compatible with existing methods for reducing communication overhead, such as local methods and communication compression methods.

27 It is well understood that cost of communication can be the primary bottleneck in Federated Learning. Indeed, wireless links and other end-user internet connections typically operate lower rates than intra-datacenter or inter-datacenter links and can be potentially expensive and unreliable. Moreover, 30 the capacity of the aggregating master and other FL system considerations impose direct indirect Optimal Client Sampling for Federated Learning
Anonymous Author(s) Affiliation Address
email
Abstract
It well understood that client-master communication can be primary bottleneck in Federated Learning. this work, we address this issue with novel client sub- sampling scheme, where restrict the number of clients allowed to communicate their updates back to the master node. In each communication round, all partici- pated clients compute their updates, but only the ones with "important" updates communicate back to the master. We show that importance can be measured using only the norm of the update and give formula for optimal client participation. This formula minimizes the distance between the full update, where all clients participate, and limited update, where the number of participating clients is restricted. In addition, we provide a simple algorithm that approximates the optimal formula for client participation which only requires secure aggregation and thus does not compromise client privacy. We show both thcoretically and empirically that our approach leads to superior performance for Distributed SGD (DSGD) and Federated Averaging (FedAvg) compared to the baseline where participating clients are sampled uniformly. Our approach is orthogonal to and compatible with ex- isting methods for reducing communication overhead, such as local methods and communication compression methods.
2
10
11
12
13
14
15
17
Introduction
18
We consider the standard cross-device Federated Learning (FL) setting [3] where the objective is of 20 the form
min
f(x)
Σ 1=1
w.fi (z)
(1)
21 where x E RRd represents the parameters statistical model we aim to find, the total number of clients, fs: Rd + IR is continuously differentiable local loss function which depends on the data D; 23 owned by client via f, Eg-D; [fx [)], and w; 2 0 are client weights such that Σ wi We assume the classical FL setup in which central master (server) orchestrates the training by securely aggregating updates from clients without seeing the raw data.
25
26
1.1
Communication as the Bottleneck
28
29
31 constrains on the number of clients that are allowed to participate in each communication round.
32 These considerations have led significant interest in reducing the communication bandwidth of FL systems.
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.

---

34
1.1.1
Local Methods
35 One of the most popular strategies is to reduce the frequency of communication and put more emphasis on computation. This is usually achieved by asking the devices to perform multiple local steps before communicating their updates. A prototype method in this category is the Federated Averaging (FedAvg) algorithm [23]. The original work was a heuristic, offering no theoretical guarantees, which motivated the community to try to understand the method and various existing and
36
37
36
39
40
new variants theoretically [35
41
1.1.2
Communication Compression
42
Another popular approach is to reduce the size of the object (typically gradients) communicated from clients the master. These techniques usually referred to as gradien/commmuicattion compression. In this approach, instead of transmitting the full-dimensional gradient/update vector g E Id one transmits a compressed vector C(g), where C E2 + Rd is a (possibly random) operator chosen such that C(g) can be represented using fewer bits, for instance by using limited bit representation (quantization) or by enforcing sparsity (sparsification).
44
45
46
47
particularly popular class of quantization
operators is based on random dithering 7 [30; see [1 42 (8)) A new variant of random dithering developed in [IO] offers an exponential improvement on standard dithering. Sparse vectors can be obtained by random sparsification techniques that randomly mask the input vectors and preserve a constant number of coordinates only [40 18 36 24
48
49
50
51
39] There is also line of work [T0 3 where a combination of sparsification and quantization was proposed to obtain more aggressive combined
52
53
effect.
1.2
Related Work
Importance sampling methods for optimization have been studied extensively in the last few years in several contexts, including convex optimization and deep learning. LASVK developed in (5), which is an online algorithm that uses importance sampling to train kernelized support vector machines. The first importance sampling for randomized coordinate descent methods was proposed in seminal paper in [26). It was showed in 29 that the proposed sampling is optimal. Later, several extensions 38) Another branch of work studies sample complexity. 43 the authors make a connection with the variance of the gradient estimates of SGD and show that the optimal sampling distribution is proportional to the per-sample gradient norm. In terms 63 of computation, obtaining this distribution is as hard as the computation of the full gradient, thus is not practical. For simpler problems, one can sample proportionally to the norms of the inputs,
55
57
59
and improvements followed 33 20
61 In 25
82
64
85 which can be linked to the Lipschitz constants of the per-sample loss function for linear and logistic
86 regression. For instance, it was shown in [11] that static optimal sampling can be constructed even for mini-batches and the probability is proportional to these Lipschitz constants under the assumption
87
68 that these constants of the per-sample loss function are known. Unfortunately, importance measures
69 such as smoothness of the gradient are often hard to compute/estimate for more complicated models such as those arising in deep learning, where most of the importance sampling schemes are based
70
71 on heuristics. A manually designed sampling scheme was proposed in [4. It was inspired by the
72 perceived way that human children learn; in practice, they provide the network with examples of increasing difficulty in an arbitrary manner. In a diametrically opposite approach, it is common for
73
74 deep embedding learning to sample hard examples because of the plethora of casy non- non-informative a history of losses for previously seen samples to create the 76 sampling distribution and sample either proportionally to the loss or based on the loss ranking [31 22).
ones 32 B4]. Other approaches
In (6), the authors propose sample based on the gradient norm of small uniformly sampled
78 subset of samples.
79 In our work, we avoid all the aforementioned problems as our motivation is not to reduce computation,
80 which is not the main bottleneck of Federated Learning, but to use importance sampling to decrease 81 the number of bits communicated. This, as we show in Section 2 allows to construct optimal 82 adaptive sampling: that is, we do not need to rely on any heuristics, historical losses, or partial information.
2

---

92 In particular, we propose principled optimal client sampling scheme capable of identifying the most informative clients in any given communication round. Our scheme works by minimizing the variance of the stochastic gradient produced by the partial participation procedure, which then translates to 84 1.3
Contributions
as In this work, we propose new approach to addressing the communication bandwidth issues appearing 86 in FL. Our approach is based on the observation that in the situation where partial participation is desired and budget on the number of participating clients is applied, careful selection of the
87
88 participating clients can lead to betler communication complexity, and hence faster training. In other
89 words, we claim that in any given communication round, some clients will have "more informative" updates than others and that the training procedure will benefit from capitalizing on this fact by ignoring some of the worthless updates.
90
91
93
94
95 a probable reduction in the number of communication rounds. To the best of our knowledge, this
96 approach was not considered before. Moreover. our proposal is orthogonal to and hence combinable with existing approaches to communication reduction such as communication compression or local updates (Section 3.2).
97
98
99
Our contributions can be summarized as follows:
100
we propose a novel adaptive partial participation strategy for reducing communication in FL. that works by careful selection of the clients that are allowed to communicate their updates to the master node in any given communication round;
102
103
our adaptive client sampling procedure optimal in the sense that minimizes the variance of the master update;
104
105
we propose an approximation to our optimal adaptive sampling strategy which only requires aggregation, thus allows for secure aggregation and stateless clients;
106
107
we show theoretically that our approach allows for larger learning rates for Distributed SCD and FedAvg algorithms than the baseline which performs uniform client sampling, and as a result leads to better communication complexity.
108
110
we show empirically that the performance of our approach is superior to uniform sampling and close to full participation.
111
2
Smart Client Sampling for Reducing Communication
112
113
We now describe our client sampling strategy for reducing the communication bottleneck in Federated Learning. Each client participating in round &s computes an update vector U E Ed, For simplicity and ease of exposition, we assume that all clients E [m] == {1, 21,2.... n1} are available in each round. However, we would like point out that this is not limiting factor, and all presented theory can be
114
115
116
117
easily extended to the case of partial participation with an arbitrary distribution. In our framework, only a subset of clients communicates their updates to the master node in each communication round
118
119
in order to reduce the number of transmitted bits.
120
In order to provide analysis in this framework, we consider a general partial participation frame- work 12), where we assume that the subset of participating clients is determined by an arbitrary random set-valued mapping S (a "sampling") with values in 2 A sampling S is uniquely defined by assigning probabilities to all 2" subsets of [n]. With each sampling 3 we associate probability matrix P E R defined by Pij ;= Prob [t. j} C S). The probability vector associated with is the vector composed of the diagonal entries of P:p= (Pi......P.. E R where p; Prob(i E S). We say that S is proper if p. > 0 for all i. It easy to show that b == E [[S]] Trace (P) Σ Pi. and hence b can be seen the expected number of clients participating in each communication round. [0, 1). consider a random set $ C [rx] generated as follows: for each i [n], we include in S with probability p.. This is called independent sampling, since the event i E S is independent of j E S for any i + j.
121
122
123
124
126
127
128
Given parameters Pl,- ....... Pr. E
129
130
While our client sampling strategy can be adapted to essentially any underlying learning method, we give details here for DSCD:
132
z k+1 = -
G
=
Σ
Wi
U
(2)
P
3

---

where 8 ~ Sh and U = o is an unbiased estimator of Vf( The scaling factor P.
1 is necessary
133
in order to obtain an unbiased estimator of the true update, i.e., Es= [G*] > we U
135
2.1
Optimal Client Sampling
We start with simple observation that the variance of our gradient estimator Go can be decomposed
138
137
as
E [[(G=> E |0t
wy U
+
Σ w. U v ((x
138
Note that the second term on the right-hand side is independent of the sampling procedure and the first term is zero if every client sends its update (i.e., if p = 1 for all i). In order to provide meaningful results. we restrict the expected number of clients to communicate in each round by bounding 8 = Ei=1 Pt by some positive integer m n. This raises the following question: What is the sampling procedure that minimizes for any given m.? We answer this question using the following technical lemma:
140
142
Lemma 1. Let S2, .... Sn be vectors in Rd and WL, w2...., Wn be non-negative real numbers such that Ei=1 W4 1. Define Ç = Ei=1 wift. Let S be proper sampling. Ifv E RR is such that
P pp 1 Diag(pr (pL U1, P222. ... pnun),
(3)
then
E
WeCi
2 Pi
11
(4)
pi
BES
147
where the expectation is taken over S. Whenever
holds, it must be the case that v2 2
148
turns out that given probabilities {pi}. among all samplings satisfying p; Prob(i E S), the independent sampling minimizes the left-hand side of (4. This is due to two nice properties: a) any
149
150
p; for all i, and b) for independent sampling (4) holds as equality. In the context of our method, these properties can be written as
independent sampling admits optimal choice of u, i.e., D;
G
w.
U
= E
W
(5)
152 It now only remains to find the parameters (p/) defining the optimal independent sampling, i.e., one
153 that minimizes (5) subject to the constraints 0 I pf < 1 and b* = Eimr < m. It turns out that
154 this problem has the following closed-form solution:
(m + n1
if $ A
p
1,
if A*
155 where Ü. = w/ UR, and
is the j-th largest value in {||77
| n
I is the largest integer for
Σl
156 which 0 < m + n 5
(note that this incquality at least holds for I = n m + 1), and
A contains indices such that Ü
( (0+= We summarize this procedure in Algorithm
157
158
2.2
Secure Aggregation
10
Note that in the case n, the optimal probabilities P Eー= can be computed easily: the
159
180
master aggregates the norm each update and then sends the sum back to the clients. However,
1 < n, in order to compute optimal probabilities, the master would need to identify the norm of every

---

Algorithm 1 Optimal Client Sampling (OCS).
1: Input: expected batch size m
2: each client computes a local update U (in parallel)
3: each client i sends the norm of its update uº = w; |/ ||
|| to the master (in parallel)
4: master computes optimal probabilities p using equation (
5: master broadcasts Pf to all clients
6: each client sends its update "t U to the master with probability P (in parallel)
162
update and perform partial sorting, which can be computationally expensive and also slightly violates the privacy requirements of clients in FL..
163
164
Therefore, we develop an algorithm for approximately solving the problem, which only requires to perform aggregation at the master node without compromising privacy of any client. The construction of this algorithm is similar
[4)] We first set p. 6 and p. min( 1]. In an ideal situation, this would be sufficient. However, due the truncation operation, the expected minibatch m [
168
167
168
m can be strictly less than m if 5 > 1 holds true for at least one i. Hence, we employ an iterative procedure to fix this gap by rescaling the probabilities which are smaller than 1, summarized in Algorithm|2 2 This algorithm is much easier to implement and computationally more efficient on parallel computing architectures. In addition, it only requires a secure aggregation procedure on the master, which is essential in privacy preserving FL, and thus is compatible with existing FL software and hardware. We realize that Algorithm [brings some extra communication costs, but this is not an issue as it only requires communicate (fmax) extra floats for each client. We pick Jmax (1), and thus it is negligible for large models of size d. Remark 1. We realize that our algorithm requires two communication rounds per optimization round, but the first round is negligible due the minimal number of communicated bits as argued above.
size b² = E.= S Ei=
169
170
171
172
173
174
175
178
177
3
Convergence Guarantees
178
179
In this section, we provide convergence analysis of DSGD and FedAvg with our optimal client sampling technique and compare it with full participation and independent uniform sampling of m clients. We use standard assumptions [14 and assume throughout that I has a unique minimizer xf with f(=*) > -0. We further assume that f is j--strongly convex and ft's are L-smooth and convex. Detailed definitions of convexity and smoothness can be found in the Appendix. Note that nothing prevents us from extending the results in this section to convex and non-convex cases with a similar standard analysis, since our proposed method only affects the aggregation step as described in Section 2 which is independent of the strong convexity assumption.
180
181
182
f
183
184
185
186
Assumption 1 (Gradient oracle for DSGD). The stochastic gradient estimator g. ff((x*) + c of
187
the local gradient V fa(*))) ), for each round & and all i = I,..., n, satisfies
188
E [
and
E. [[Lct]] lor| This further implies that E [ Σn of x*1 vf(=*).
M
( 2 + o², for some M 2 0.
(8)
Assumption (Gradient oracle for FedAvg). The stochastic gradient estimator g: (
191
192
V Vv ) + Eh of the local gradient (v,,) for each round k. each local step r = 0,..., R and all i = 1, 1,... n, satisfies
198
ck = 0
(9)
and
E [|Ist.rl 112 [vtir] < M V V. I|( + +o?
for some M 2 0,
(10)
where v = * and v v mo(()t)))
1,..., R...R.
5

---

Algorithm 2 Approximate Optimal Client Sampling (AOCS).
1: Input: expected batch size maximum number of iteration Jmax
2: each client computes an update U (in parallel)
3: each client sends the norm of its update uº = w; | to the master (in parallel)
4: master aggregates u Σi= u
5: master broadcasts u to all clients
6: each client computes p = min myy wn .1} (in parallel)
7: for 1.... .ma do
8: each client sends 1/ = (1, to the master if pf < 1; else sends e = -0,0) (in parallel)
9: master aggregates (1 P6) -i= t
master computes C (m (m-n+1*)
10:
pc
11:
master broadcasts C* to all clients
each client recalibrates p m 13 if pf < (in parallel)
13:
if C < 1 then
14: break
15: end if
16: end for
each clients sends its update wis + to master with probability P (in parallel)
198
We also define two quantities, which appear in our convergence guarantees:
R2 f;=
(1I)
197
where f is the functional value of fi its optimum. R, represents the mismatch between the local and global minimizer, and n* captures the distance of the current point the minimizer of S.
198
199
Equipped with these assumptions, we are ready to proceed with our convergence guarantees. We start with the definition of the improvement factor
E
Erest U. p
Ein wi U.U
k
(12)
Eietr
U
En wi U.!
p!
where S g with pf defined in O6) and U U is an independent uniform sampling with D m/n. By construction, at is less than or equal to one, as S minimizes the variance term. In addition, " can reach zero in the case where there are at most m non-zero updates. If a = 0, our method performs as all updates were communicated. In the worst-case a² = 1, our method performs as if we picked updates uniformly at random, and one cannot do better due to the structure of the updates U In the following subsections, we analyze specific methods for solving the optimization problem (T) under the aforementioned assumptions. The proofs and detailed description are deferred to the Appendix.
203
204
206
207
208
Based on sampling strategy, it might be tempting assume that the obtained solution could exhibit fairness issues. In our convergence analysis, we show that this not the case, as our proposed methods converge the optimal solution. Hence, long the original objective has inherent issue with fairness, our methods do not exhibit any faimess issues. Besides, our algorithm be used in conjunction with other "more fair" objectives, e.g., tilted ERM [9
Fairness.
210
212
214
3.1
Distributed SGD with Optimal Client Sampling
215
We begin with the convergence analysis for DSGD (see (2) with optimal client sampling.

---

Algorithm 3 FedAvg with Optimal Client Sampling.
Input: initial global model xt, global and local step-sizes ngg '
2: for each round k L, ...... . K do
3: master broadcasts x to all clients E [n]]
4: for each client E [n|] (in parallel) do
5: initialize local model v²." + x*
6: for ro do
compute mini-batch gradient y: (w/, 8: update yf.r + vi.r-1 1/i go (v/
7:
9: end for
compute U = Ay,"" x² yfR
11: compute p using Algorithm Or
12: send p. Ayy to master with probability p
13:
end for
14:
Ay master computes Ar Eiest p.
15: master updates global model k+ t- x² mi Ax
end for
216
Theorem Let be L-smooth and convex all ,,...., n. Let u-strongly convex. Suppose that Assumption I holds. Choose T/² (0, (1+maxeelm) (wx (wx))))))
where
m E
m 111 k k= - 1-
= a m) + m
218 Define
n
Bi Σ (2L(1+ MDR; + +z) and B2 = 2L Σ wł R.
219
Then, the iterates of DSGD with optimal client sampling 6 satisfy
E [| & (1 - j175 E
+ (17 B2
31 7
(13)
220
Interpretation. order to understand the results of Theorem we first look the best and worst case scenarios. In the best case scenario, we have ** for all k. This implies that there is no loss of speed comparing to the method with full participation. obtained recursion recovers the best-known rate of DSGD in the full participation regime [8]. Similarly, in the worst case, we have n = '//n for all k's, which corresponds to uniform sampling with sample size and recursion recovers the best-know rate for DSGD in this regime. This is expected as (12) implies that each update U equivalent, thus we cannot hope for better rate than obtain recursion sits somewhere between full and uniform partial participation, where the actual position is determined by >* which capture the distribution of updates (here gradients) clients. For instance, with larger number of n tending
222
indeed confirmed by our theory
224
226
the uniform sampling. In the general scenario,
228
229
to 1, we are closer to full participation regime. Similarly, with more R tending to m/n, we are 230
closer to the rate of partial participation.
232
3.2
FedAvg with Optimal Client Sampling
233
One of the most common approaches to optimization for Federated Learning is Federated Averaging (FedAvg) (3), an adaption of local-update to parallel SGD. FedAvg, each client runs some
234
number of SGD steps locally, and then local updates are averaged to form the global update which is
296
then used for the global model on the master. Pseudo-code that adapts the standard FedAvg algorithm to our framework is given in Algorithm
7

---

Dataset: 132,906 training images totall
Dataset 2 (29.906 traininng mages sotal!
Dacaset (27, 599 training Images total)
91750
0
10% lente heed 6b% tmsh tmager
1175
2003
chaata hold p0% braniig
2
2230
50% hold park toainig
1550
1593
1 11500
7 1223
3 11000
11293
1003
Wand 1an01
1000
12350
730
752
750
500
5.0
230
250
302 The Namber of (Twiriing Images Client lidds
The Number of Treninn Images Clast Hilds
The Number Traiiig Images Cleett lonls
Figure 1: Distributions of the three datasets considered.
Figure 2: (Dataset 1) validation accuracy and (local) training loss function of the number of communication rounds and the number of bits communicated from clients to the master.
238 Theorem 3. Assume that fü L-smooth and u-strongly convex for all i adll=i,.... 1,..., and Assumption holds. Let r7th = Roffng be the effective step-size and n/
where
Σ, w
m
a
(n - m) + m
240 1f < min M(2 (1+max;clml) 1wy [1+M/R))] j.
then the iterates of FedAvg (R 2 2) with
241
optimal client sampling (6) satisfy
1
(1- pnf
(1
||~ 17th
[1
3
32,
where
20
M R
M R
8 = R
ii
4L
+
Σ ofR, Rs and 82 32:-721
1+
w,R.
243
Interpretation. Similar to DSGD, the convergence guarantees of FedAvg with optimal client sam- pling (Algorithm(3) sits somewhere between the performances of those with full and uniform partial participations, where the actual position is again determined by the distribution of updates which (best case) > n/n (worst case), we recover the state-of-the-art complexity guarantees provided in [55 in both regimes. 15 assumes M 0 and we 1/n.
245
directly impact a that linked 7*'s. the edge cases, i.e. )
246
247
248
Note that our results are slightly more general,
4 Experiments
249
250
In this section, we empirically evaluate our optimal client sampling method, comparing it with 1) the baseline where participating clients are sampled uniformly from available clients in each round and 2) full participation where all available clients participate. We simulate the cross-device FL setting and train models using TensorFlow Federated (TFF For all three methods, we report validation accuracy and (local) training loss (vertical axis) as a function of the number of communication rounds and the number of bits communicated from clients the master (horizontal axis). Each figure displays the mean performance with standard error over independent runs. For a fair comparison, use the same random seed for the three compared methods in single run and vary random seeds across different runs.
252
254
256
258
Setup. We conclude evaluation FedAvg where we extend the TFF implementation of FedAvg to fit our framework. For the model, we use the two-layer Convolutional Neural Network (CNN)
280
httpp//sswh.toooooeetcc//crrr/tp examples/ssippe_ffeaaa

---

Figure 3: (Dataset 2) validation accuracy and (local) training loss function of the number of communication rounds and the number of bits communicated from clients to the master.
Figure 4: (Dataset 3) validation accuracy and (local) training loss as function of the number of communication rounds and the number of bits communicated from clients to the master.
provided in the implementation. The default dataset is Federated EMNIST with only digits, but as this is a well-balanced dataset with mostly the same quality data on each client, we modify it by removing some clients or some of their training images, in order better simulate conditions in which our proposed methods bring significant theoretical improvements. As a result, we produce 3 unbalanced
262
263
264
265
datasets as summarized in Figure I on which we train the CNN model. For validation, we use the unchanged validation set in the Federated EMNIST dataset, which consists of 40, 832 validation images. In each communication round of FedAvg, n 32 clients are sampled uniformly from the client pool, each of which then performs several SGD steps on its local training images for 1 epoch with batch size 20, For partial participation, the expected number of clients allowed to communicate their updates back to the master is set to m = 3 for all the experiments. We use constant step sizes, where we set ng and tune 17, from the set of values {2 1 2.2.--3
286
267
268
269
270
3.2 2-22,, 4.2 2- -5] using a holdout
271
set. We implement our sampling procedure using Algorithm 2 as this supports stateless clients and secure aggregation. We include extra communication costs in our results, where we set Jmax 4.
273
274
More details of the hyper- parameters that we use can be found in the Appendix.
275
Results and Diseussions. As predicted by our theory, the performance of FedAvg with our proposed optimal client sampling strategy is in between the performances of that with full and uniform partial participation. Figures and 4 (red curves: optimal sampling: blue curves: uniform sampling; green curves: full participation) show that, for all three datasets, the optimal sampling strategy performs slightly worse than but still competitive with the full participation strategy in terms of the number of communication rounds it almost reached the performance of full participation while only less than 10% of the available clients communicate their updates back to the master. Note that the uniform sampling strategy performs significantly worse, which indicates that a careful choice of sampling probabilities can go long way towards closing the gap between the performance of naive uniform sampling and full participation.
278
277
278
279
280
281
283
285
More importantly, and this was the main motivation of our work, our optimal sampling strategy is significantly better than both the uniform sampling and full participation strategies when we compare validation accuracy as function of the number of bits communicated from clients the master. For instance, in case of Dataset (Figure while our optimal sampling approach reached around 85% validation accuracy after 2 x 10 communicated bits, neither the full nor the uniform sampling strategies are able to exceed 40% validation accuracy within the same communication budget. Indeed, to reach the same 85% validation accuracy, full participation approach needs to communicate more than 29 x 10 bits, i.e., 8x more, and uniform sampling approach needs to communicate about the same number bits as full participation or even more. The results for Datasets 2 and are of a similar qualitative nature, showing that these conclusions are robust across the datasets considered.
286
287
288
289
290
291
292
293
285
In the Appendix, we include additional figures which show the current best validation accuracy as function of the number of communication rounds and the number of bits communicated from clients
296
297
to the master.

---

References
296
290
[1] Dan Alistarh, Jerry Li, Ryota Tomioka, and Milan Vojnovic, QSGD: Randomized quantization for communication-opiiall stochastic gradient descent. arXiv preprint arXiv:1610.02133 2016.
[2] Zeyuan Allen-Zhu, Zheng Qu, Peter Richtárik, and Yang Yuan. Even faster accelerated coordinate descent using non-uniform sampling. In International Conference on Machine Learning, pages 1110-1119, 2016.
302
[3] Debraj Basu, Deepesh Data, Can Karakus, and Suhas Diggavi. Qsparse- loaisse-ooca-SGDD Dis- tributed SGD with quantization, sparsification and local computations. In Advances in Neural Information Processing Systems, pages 14668-14679, 2019.
305
[4] Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. Curriculum learning. In Proceedings of the 26th annual international conference on machine learning, pages 41-48, 2009.
308
[5]
Antoine Bordes, Seyda Ertekin, Jason Weston, and Léon Bottou. Fast kernel classifiers with online and active learning. Journal of Machine Learning Research, 67591):157--1619, 2005.
311
312
[6] Olivier Fercoq and Peter Richtárik. Accelerated, parallel, and proximal coordinate descent.
313
SIAM Journal on Optimization, 25(4):1997-2023 2015.
77]
WM Goodall. Television by pulse code modulation. Bell System Technical Journal, 30(1):33 49,
315
1951.
316
[8]
Robert Mansel Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, and Peter Richtárik. SGD: General analysis and improved rates. Proceedings of the 36th International Conference on Machine Learning, Long Beach, Califormia, 2019.
318
319
99] Filip Hanzely and Peter Richtárik, Federated learning of a mixture of global and local models.
320
arXiv:2002.05576, 2020.
321
[10] Samuel Horváth, Yu Ho, L'uoovit Horváth, Atal Narayan Sahu, Marco Canini, and Peter Richtárik. Natural compression for distributed deep learning. arXiv preprint arXiv: 10988, 2019.
322
323
324
[1]] Samuel Horváth and Peter Richtárik. Nonconvex variance reduced optimization with arbitrary sampling. Proceedings of the 36th International Conference on Machine Learning, 2019.
325
328
[12] Samuel Horváth and Peter Richtárik. A better alternative to error feedback for communication- efficient distributed learning. arXiv preprint urXiv:2006.110%1 2020.
327
328
[13] Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurelien Bellet, Mehdi Bennis, Ar- jun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, al. Advances and open problems in federated learning. arXiv preprint 191.09791 2019.
329
330
331
332
[14] Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal-
333
gradient methods under the tojjsiswwjai condition. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 795 811. Springer, 2016.
334
335
[15] 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: 1ex.vv/9100.00 190000637, 2019.
336
338
[16] Angelos Katharopoulos and François Fleuret. Not all samples are created equal: Deep learning 2018
339
with importance sampling. arXiv preprint
340
[17] Ahmed Khaled, Konstantin Mishchenko, and Peter 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.
342
[18] Jakub Konečný and Peter Richtárik. Randomized distributed mean estimation: Accuracy vs. 343
communication. Frontiers in Applied Mathematics and Statistics, 4:62, 2018.
10

---

345
[19]
Tian Li, Ahmad Beirami, Maziar Sanjabi, and Virginia Smith. Tilted empirical risk minimization. In International Conference on Learning Representations, 2021.
348
347
[20]
Qihang Lin, Zhaosong Lu, and Lin Xiao. An accelerated proximal coordinate gradient method. In Advances in Neural Information Processing Systems, pages 3059-3067, 2014.
348
349
[21]
Tao Lin, Sebastian U Stich, Kumar Kshitij Patel, and Martin Jaggi. Don't 't use large bati-b use local SGD. arXiv preprint arXiv: 0720807717, 2018.
350
351
[22] Ilya Loshchilov and Frank Hutter. Online batch selection for faster training of neural networks. arXiv preprint 1rXiv:1511.063 2015.
352
353
[23] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication -efffiifiaato-eeffiiitetttt learning of deep networks from decentralized data. In Artificial Intelligence and Statistics, pages 1273-1282 1282, 2017.
354
355
356
[24] Konstantin Mishchenko, Filip Hanzely, and Peter Richtárik. 99% of parallel optimization is inevitably a waste of time. arXiv preprint arXiv:1901.09437, 2019.
357
358
[25]
Deanna Needell, Rachel Ward, and Nati Srebro. Stochastic gradient descent, weighted sampling. and the randomized kaczmarz algorithm. In Advances in neural information processing systems, pages 1017-1025, 2014.
359
360
361
[26]
Yu Nesterov. Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM Journal on Optimization, (2(2):341-362 2012.
382
363
[27] Zheng Qu, Peter Richtárik, and Tong Zhang. Quartz: Randomized dual coordinate ascent with arbitrary sampling. In Advances in Neural Information Processing Systems 28, pages 665-873, 2015.
364
385
366
(28) Ali Jamezani-Kebryal Fartash Faghri, and Daniel M Roy. NUQSGD: Improved communication
367
efficiency for data-part data-parallel SGD via nonuniform quantization. arXiv preprint reXiv:/908.000 2019.
368
[29] Peter Richtárik and Martin Takáë. Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function. Mathematical Programming, 144(1-2):1-38, 2014.
370
[30] Lawrence Roberts. Picture coding using pseudo-random noise. Transacctts on Information Theory, 8(2): 155,, 1962.
373
374
[31] Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver. Prioritized experience replay. arXiv preprint urXiv:/511.088 2015.
376
[32] Florian Schroff, Dmitry Kalenichenko, and James Philbin. Facenet: A unified embedding for face recognition and clustering. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 815-823, 2015.
377
378
379
[33] Shai Shalev-Shwartz and Tong Zhang. Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization. In International conference on machine learning, pages
380
64-72, 2014.
[34] Edgar Simo-Serra, Eduard Trulls, Luis Ferraz, lasonas Kokkinos, Pascal Fua, and Francesc Moreno-Noguer. Discriminative learning of deep convolutional feature point descriptors. In Proceedings of the IEEE International Conference on Computer Vision, pages 118-126, 2015.
383
[35] Sebastian U Stich. Local SGD converges fast and communicates little. ICLR 2019 International Conference on Leurning Representations, 2019.
386
387
[36]
Sebastian U Stich, Sean-Baptiste Cordonnier, and Martin Jaggi. Sparsified SGD with memory. In Advances in Neural Information Processing Systems, pages 4447-4458, 2018.
[37] Sebastian U Stich and Sai Praneeth Karimireddy. The error-feedback framework: Better rates for SGD with delayed gradients and compressed communication. ICLR 2020- International Conference Learning Representations, 2020.
390

---

382
[38]
Sebastian U Stich, Anant Raj, and Martin Jaggi. Safe adaptive importance sampling. In Advances Neural Information Processing Systems, pages 4381-4391, 2017.
393
394
[39] Thijs Vogels, Sai Praneeth Karimireddy, and Martin Jaggi. PowerSGD: Practical low-rank gra- dient compression for distributed optimization. In Advances in Neural Information Processing Systems, pages 11236-14245 2019.
396
397
[40] Jianqiao Wangni, Jialei Wang, Ji Liu, and Tong Zhang. Gradient sparsification for communication-effcicett distributed optimization. In Advances in Neural Information Pro- cessing Systems, pages 1299-1309, 2018.
389
400
[41] Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Terngrad: Ternary gradients reduce communication distributed deep learning. In Advances in Neural Information Processing Systems, pages 1509-15199 2017.
402
[42] Hantian Zhang, Jerry Li, Kaan Kara, Dan Alistarh, Ji Liu, and Ce Zhang. Zipml: Training linear models with end-to-end low precision, and little bit of deep learning. In Proceedings of the 34th International Conference Machine Learning- Volume 70, pages 4035-4043. JMLR. org, 2017.
404
406
407
[43] Peilin Zhao and Tong Zhang. Stochastic optimization with importance sampling for regularized loss minimization. In international conference machine learning, pages 1-9, 2015.
12

---

Checklist
409
410
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
412
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Remark [ where we acknowledge that our algorithm requires two (although the first one is negligible) communication rounds per iteration.
413
414
415
416
(c) Did you discuss any potential negative societal impacts of your work? [Yes] We discussed potential fairness issues in Section 3.
417
418
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
420
2. If you are including theoretical results...
421
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section 3 and Appendix A.
422
425
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix C-F for complete proofs. We also provided interpretations of our theorems in the main paper and discussed the relationship between our results and related results in the literature.
425
428
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL.? [Yes) See supplemen- tal material.
428
429
430
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section 4 and Appendix B
431
(c) Did you report error bars (c.g., with respect the random seed after running experi- ments multiple times)? [Yes] We ran every experiment times with different random seeds and reported results with error bars.
433
435
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A] Since we only run simulations, this is not applicable.
438
437
4. If you are using existing assets (e.g., code, data, models) or curating/releusing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] See Section 4 (b) Did you mention the license of the assets? [Yes] All the data and assets used in this manuscript are open-source.
441
442
(c) Did you include any new assets either in the supplemental material or as URL? [Yes] We included an anonymized URL in the supplemental material for the datasets used.
443
444
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
447
448
5. If you used crowdsourcing or conducted research with human subjects...
449
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
450
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
452
453
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
454
13


Reviews:
[{"review_id": "oSR61ssi_IP", "reviewer": "Reviewer_xb8E", "summary": "The paper proposes to use importance sampling in client sampling in federated learning to improve convergence behavior and reduce communication. \nContribution:\n1. A new importance sampling scheme based on the norm of gradients/updates.\n2. Experiments show the proposed sampling scheme outperforms uniform sampling.", "questions": "", "limitations": "", "rating": 5, "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": "Strengths:\n1. Theoretical optimality of the new client sampling method is given to motivate it.\n2. The proposed client sampling method outperforms uniform client sampling.\n\nWeaknesses:\n1. The major concern is there is no comparison with other importance sampling methods. There is a large amount of literature on importance sampling methods for optimization algorithms to improve convergence, the proposed importance sampling scheme should be properly compared with existing literature and highlight the novelty of the proposed scheme. For example, [1] is a well-known importance sampling scheme for SGD to reduce update variance, the sampling probabilities depend on the magnitude of gradient (which will become update magnitude if trivially adapted to federated learning setting). The authors have a one-sentence argument that the difficulty of using [1] is the complexity is equivalent to using the full-batch gradient, which I think is because estimating the sampling probabilities requires computing all per-sample gradients. However, in the authors' setting, estimating sampling probabilities require estimating updates from all clients or at least some selected clients, though it might be practical, why can't one apply the importance sampling method in [1] with the sampling candidates being all clients or the selected clients (instead of the per-sample gradient)? Also, I feel the importance sampling technique in [1] is quite similar to the proposed importance sampling method, though the proposed scheme has some special adaptation to distributed settings (Algorithm 2). In a word, my concern is that the novelty of the proposed sampling scheme is unclear compared with other existing importance sampling methods for SGD. I hope the authors could add a more clear discussion on this point especially the difference and improvement compared with [1] since the sampling scheme is the main contribution.\n\n2. There is not much in-depth analysis on the improvement of the proposed client sampling method over uniform client sampling. The convergence analysis relates the convergence rate with \\alpha^k (12) but the discussion on how \\alpha^k changes with gradient/update distribution are very limited.  I think the most important thing is to get an in-depth understanding of how the reduction of variance depends on gradient/update distribution, which is not given enough attention in the paper. Instead, the paper focus on the convergence analysis of algorithms. However, in my impression, many convergence analysis of SGD and FedAvg directly depends on the variance of the update (I am pretty sure this is the case for SGD, but for some advanced sharp analysis for FedAvg it might be different), with importance sampling applied, when the estimator is unbiased, the only thing that is changed in the convergence analysis could be the variance term, so the new analysis could be just directly substituting the variance term into the existing analysis which is kind of trivial. If the convergence analysis is non-trivial, it could be great to point out the difficulties in analysis when using importance sampling to highlight the challenges and avoid giving the readers an impression of trivialness.\n\nSummarizing my two points, I think the novelty of the proposed scheme is not clear to me. I have an impression that the proposed importance sampling scheme is not much different from traditional importance sampling methods for SGD and the convergence analyses are not much different from existing ones. If my impression is true, it makes the contribution of this paper being the application of importance sampling in FedAvg which I believe is not enough to pass the acceptance bar for NeurIPS. I am willing to change my score if the authors could convince me of the novelty of the paper.\n\n[1]. Zhao, Peilin, and Tong Zhang. \"Stochastic optimization with importance sampling for regularized loss minimization.\" international conference on machine learning. PMLR, 2015.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "igToRHl9Ld5", "reviewer": "Reviewer_DC2U", "summary": "The authors propose an efficient client (sub) sampling scheme for federated learning (FL) which relies on the quality of the update of each (sampled) client. The authors justify their construction by designing the (sub) sampling strategy that minimizes the gradient variance over the whole network (or sampled clients). The authors analytically show the convergence of DSGD and FedAvg under their sampling strategy which improves on the uniform sampling strategy. Finally, the authors empirically validate the proposed sampling algorithm by showing considerable communication gains compared to both and uniform client sampling strategies. ", "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": " \nCommunication is a bottleneck for large-scale FL applications and the design of efficient sampling strategies is, therefore, an important problem. The authors consider the sampling design problem from the viewpoint of minimizing the variance of the estimated gradient. The paper is well written and the presentation is sufficiently clear. The experiments presented in the paper show that the proposed sampling algorithm can reduce the communication requirements of the standard algorithms considerably compared to the baselines. Below some of the concerns and comments are listed which the authors should address, especially, the technical concerns:\n\n1.\tThe discussion from lines 148 to 149 is not clear. Specifically, it is not clear why the authors claim the optimality of the proposed client sampling strategies. In inequality (4), the authors present an upper bound of the client sampling strategy and show that i) the upper bound is minimized for the independent sampling strategy (via the choice of $v_i$’s) and ii) the inequality will be equality for independent sampling. It seems to me that the above-discussed sampling strategy will minimize the upper bound on the r.h.s. of equation (4) rather than minimizing the variance of the sampled gradient. Please make the above discussion clear and verify the claims.   \n\n2.\tThe first equation in Section 2.1 will hold if the expectation of the inner product between the two terms $G^k - \\sum_{i=1}^n w_i U_i^k$ and $ \\sum_{i=1}^n w_i U_i^k - \\nabla f(x^k)$ is zero. This will happen only if conditioned on  $U^k_i$ the estimate $G^k$ is unbiased (the probabilities $p_i^k$ are dependent on $U^k_i$ as from Algorithms 1 and 2 the distribution of $S^k$ changes with $p_i^k$). Please clarify this in the paper. It would be helpful if the authors can explain the expectations.  \n\n3.  The goal of the paper is to minimize the communication requirement but the authors only try to minimize the gradient variance as the authors also state in Lines 93-95 that their scheme “probably” leads to communication reduction. So, I am not sure if calling the proposed sampling strategies optimal is justified.  \n  \n4.\tThe authors should give intuition behind the approximate Algorithm 2, specifically, why it will approximately minimize the variance. Moreover, it appears that Algorithm 2 can be fully executed at the server which might alleviate some of the communication requirements.  \n\n5.\tFor FedAvg (Algorithm 3), the $U_i^k$ used for sampling the clients is different from the one discussed in Section 2. Do the proposed analysis and the discussion of Section 2 still work, and again, can the authors claim optimality for their sampling strategy?   \n\n6.\tFL algorithms as well as the experiments authors conduct are on non-convex losses. So, it would be interesting to see the performance of the proposed sampling strategies for non-convex losses.  \n\n7.\tThe approach proposed by the authors is closely related to event-triggered distributed algorithms. The authors should discuss the advantages/drawbacks compared to event-triggered problems.\n \nMinor Comments:\n1.\tIn Theorem 2 strong convexity of $f_i$’s is not required, however, in Theorem 3 it is required. Why?\n2.\tDiscussion in Line 203: “at most $m$ non-zero updates” is not clear\n3.\tIn Line 166-167, what is the ideal situation authors are referring to?\n4.\tIn the 4th contribution bullet the authors say that a larger learning rate leads to better communication complexity. Why is that so? Because of faster convergence? Also, if relevant please discuss this in detail with the main results.\n5.\tPlease correct, Line 142: “the sampling procedure that minimizes (3)” \n6.\tIn the abstract line 4: correct participated to participating\n7.\tIn the abstract, instead of “formula” probably use “expression”  \n8.\tLine 22: $\\mathcal{D}_i$ is data or distribution of data. Also, define $\\xi$.\n9.\tPlease add some references to the claims made in Section 1.1 of the Introduction. \n10.\tSection 1.2: Lines 58-59 are not clear. It was shown in [29] that the sampling in [26] is optimal? Please clarify\n11.\tLine 83: replace “addressing” by “address”\n12.\tUpdate the discussion from Lines 148-151\n13. Is it standard to have the dependence of the step-sizes on $\\alpha^k$?\n\n-----------\nUpdated the score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "\nyes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "I_Dh0mY9z9K", "reviewer": "Reviewer_LDVA", "summary": "The paper works on strategies of client subsampling for federated learning. Specifically, it proposes an adaptive partial participation strategy, which can carefully sample clients in each round to sending their updates to the server. More importantly, the paper proposes a practical approximation to optimal sampling strategy. Theoretical analyses are given for the proposed sampling scheme, which shows better performance than existing FedAvg with uniform sampling.", "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": "Originality:  The paper has proposed a client sampling scheme, which shows better convergence performance for federated learning algorithms.  However, the new sampling scheme heavily depends on Lemma 1, which has been well studied in papers for arbitrary sampling. \n\n\nQuality: The submission technically is sound. Claims are well supported by theoretical analysis or experimental results.\n\nClarity: The submission is clearly written and well organized.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Lemma 1 has been studied in other literature for arbitrary sampling, for example, \"S. Horvath and P. Richtarik, “Nonconvex variance reduced optimization ´ with arbitrary sampling,” in International Conference on Machine Learning, 2019, pp. 2781–2789\". The authors should cite the related works for reviewers to better position the paper.  What's more, can authors show difficulties and challenges encountered during theoretical analysis?\n\nThe theoretical results need the assumption of strong convexity.  However, in experiments, two-layer CNN is used, which is nonconvex. Therefore, in order to be consistent and verify theoretical findings, the authors should either show theoretical results for nonconvex function or run experiments with linear or logistic regression etc.\n\nIn experiments, only Fderated EMNIST data is used. The authors should also include more experiments. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "N/A"}, "extra_text": {}}, {"review_id": "5a-rvK1fkL", "reviewer": "Reviewer_XEVR", "summary": "This paper proposes a strategy to _optimally_ sample clients on a given FL global round. The sampling strategy selects more informative updates by their magnitude. This criterion minimizes the variance of the sampling scheme. \n\nExperiments show this method outperforms uniform sampling. \n", "questions": "", "limitations": "", "rating": 5, "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": "\n**Originality**\n- The paper proposes a nice closed formula deriving a sampling scheme with good properties: minimizing variance. However, it is missing relevant references in the field, particularly the following paper which has a really similar strategy:\n--  Rizk, Elsa, Stefan Vlaski, and Ali H. Sayed. \"Federated learning under importance sampling.\" arXiv preprint arXiv:2012.07383 (2020).\nThis paper seems to derive the same sampling strategy and apply it both to client selection and, within each client, datapoint selection.\n- The related work section misses several client sampling strategies in FL.\n-- [1] Li, Xiang, et al. \"On the convergence of fedavg on non-iid data.\" arXiv preprint arXiv:1907.02189 (2019).\nChen, Tianyi, et al. \"LAG: Lazily aggregated gradient for communication-efficient distributed learning.\" arXiv preprint arXiv:1805.09965 (2018).\n-- Cho, Yae Jee, Jianyu Wang, and Gauri Joshi. \"Client selection in federated learning: Convergence analysis and power-of-choice selection strategies.\" arXiv preprint arXiv:2010.01243 (2020).\n-- Ribero, Monica, and Haris Vikalo. \"Communication-efficient federated learning via optimal client sampling.\" arXiv preprint arXiv:2007.15197 (2020).\n-- N. Singh, D. Data, J. George, and S. Diggavi. Sparq-sgd: Event-triggered and compressed communication in decentralized stochastic optimization. arXiv preprint arXiv:1910.14280, 2019.\n\n**Quality**\n- Line 116 affirms that this method _easily_ extends to an arbitrary availability distribution. This is not vlear to me since previous work has found that, for example under a cyclic distribution, SGD can diverge. How does this extend?\n- How to control in practice the number of participant users m?\n- How to deal with a large number of clients? In practice not all users can train since the number of clients is in the order order of millions…\n- Theorem 2 implies that there is no convergence? since \\eta^k is fixed the last term won’t vanish\n- Experiments are limited and only compare with uniform sampling and full participation. However, it has been shown in [1] that sampling proportionally to p_i can have better performance. How would this method compare with this sampling strategy? \n- The experimental setting is limited and only tested on variations of EMNIST. It would be interesting to see how this sampling behaves in different tasks. \n\n**Clarity**\n- The introduction is clear but as it advances the paper could improve the phrasing, it is easy to get lost in the convergence guarantees. \n- Small comments:\n-- In line 170 is it p_is that are larger or smaller?\n-- Line 227 It should be “our obtained”. In general this paragraph needs some editing, there are several typos. \n\n**Significance**\n-  In certain FL settings, client sampling can improve the accuracy of the model while reducing communication. This paper proposes a sampling scheme theoretically motivated. However, the proposed strategy (or similar ones mentioned above) have already been proposed by previous work. I would recommend the authors to clearly state how their work differentiates from these works that select clients for training - particularly approaches relying on update norm and/or importance sampling. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, this is a theoretical paper and societal impacts,  besides fairness that is addressed in the paper, are out of the scope of this work. I would recommend clarifying and being more specific about the fairness metric used, I am assuming it means just accuracy for all clients? In this case it should be justified why the global optimum is more fair than other solutions. \n", "review_text": "", "extra_scores": {"ethical_concerns": "None. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this work, the authors propose an efficient client sampling scheme for federated learning (FL) which relies on the quality of the update of each (sampled) client. The sampling strategy is designed based on  minimizing the gradient variance over clients. The authors provided convergence analysis for the DSGD and FedAvg algorithms under the proposed sampling strategy. Finally, the authors showed that numerically, considerable communication gains can be achieved compared  the uniform client sampling strategies.

Pros:

1) A new importance sampling scheme has been introduced to the FL setting, which is based on the norm of gradients/updates. Theoretical optimality of the new client sampling method is given to motivate it.

2) Convergence analysis has been conducted. 

3) Experiments show the proposed sampling scheme outperforms uniform sampling.


Cons:

1) Many reviewers have pointed out, that the authors have not made a fair comparison with [43]. The optimal sampling scheme is strongly motivated by the sampling scheme in [43], but the authors fail to point this out in the paper. This has caused a lot of confusion about the main contribution of the paper. 

2) Analytical improvement of the proposed client sampling method over uniform client sampling is not clear. 


3) Claims about extensions, for example to client intermittency, non-convex losses, have been mentioned, but these claims are somewhat misleading since they should be either analytically or empirically justified.

4) Finally, despite the fact that large gains have been shown, the empirical result is a bit limited compared to typical FL papers (which include multiple datasets and tasks).

Overall, the most important reason for rejecting this paper is that, the AC and the reviewers remain not convinced about the main contribution of this work. I would suggest the authors to take these comments into consideration, and thoroughly compare their scheme with [43], and clearly demonstrate that their approach is non-trivial extension of the existing optimal sampling scheme. 

Decision: Reject