Optimal Client Sampling for Federated Learning
Authors: Wenlin Chen
Samuel Horváth
Peter Richtárik
Venue: Accepted by TMLR ()

Abstract: It is well understood that client-master communication can be a primary bottleneck in federated learning (FL). 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 participating 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 allows for secure aggregation and stateless clients, and thus does not compromise client privacy. We show both theoretically and empirically that for Distributed SGD (DSGD) and Federated Averaging (FedAvg), the performance of our approach can be close to full participation and superior to the baseline where participating clients are sampled uniformly. Moreover, our approach is orthogonal to and compatible with existing methods for reducing communication overhead, such as local methods and communication compression methods. 

Published in Transactions on Machine Learning Research (08/2022)
Optimal Client Sampling for Federated Learning
Wenlin Chen
wc3370cam.acc uk
Deportment of Engineering
University of Combridge Cambridge, CB2 1PZ, UK and Deportment of Empirical Inference Mas Planck Institute for Intelligent Systems Tübingen, 72076, Germany
Samuel Horváth
www.ee..horathh@@mbuuuc
Deportment of Machine Learning Mohamed bin Zayed University of Artificial Intelligence Masdar City, Abu Dhabi, UAF
Peter Richtárik
peter. www.rrrhtrrrkkkkst.eeeeee edu.
Computer, Electrical and Mathematical Science and Engineering Division King Abdullah Universily of Science and Technology Thwwal, 23955-6900, Saudi Arabia
Reviewed on OpenReview: https: // openreview. net/ forum? id= 8OURCWKHTL
Abstract
It is well understood that client-master communication can be primary bottleneck in federated learning (FL). 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 participating clients compute their updates, but only the ones with "important" updates communicate back 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 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 allows for secure aggregation and stateless clients, and thus does compromise client privacy. We show both thcoretically and empirically that for Distributed SGD (DSGD) and Foderated Averaging (FedAvg), the performance of our approach be close to full participation and superior to the baseline where participating clients sampled uniformly. Moreover, approach is orthogonal to and compatible with existing methods for reducing communicatio overhcad, such as local methods and communication compression methods.
1 Introduction
We consider the standard cross-device federated learning (FL) setting (Kairouz et al., 2019 where the objective of the form
min f(x) = Σ w. wil((z) zERd
(1)
where x ddd represents the parameters of statistical model we aim to find, is the total number of clients, each Je: I R is continuously differentiable local loss function which depends the data distribution

---

Published in Transactions on Machine Learning Research (08/2022)
Dj owned by client via f())) = Eg-D, {)], and w, 2 0 are client weights such that Σx= wi 1. We assume the classical FL. setup in which a central master (server) orchestrates the training by securely aggregating updates (Du & Atallah, 2001 Goryczka & Xiong 2015 Bonawitz et al. 2017 So et al. 2021) i.c, the master only has access to the sum of updates from clients without secing the raw data.
1.1 Motivation: Communication Bottleneck in Federated Learning
It is well understood that. communication cost can be a primary bottleneck in cross-device FL, since typical clients are mobile phones or different. ToT devices that have limited bandwidth and availability for connection (Van Berkel 2009 Huang et al.) 2013). Indeed, wireless links and other end-user internet connections typically operate at lower rates than intra-datacenter or inter-datacenter links and can be potentially expensive and unreliable. Moreover, the capacity of the aggregating master and other FI. system considerations imposes direct indirect constrains on the number of clients allowed to participate in cach communication round. These considerations have led to significant interest in reducing the communication bandwidth of FL systems.
Local Methods. One of the most popular strategics 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 (McMahan et al., 2017), an adaption of local-update to parallel SGD, where each client runs some number of SGD steps locally before local updates are averaged to form the global update for the global model on the master. The original work was heuristic, offering no theoretical guarantees, which motivated the community to try to understand the method and various existing and new variants
theoretically (Stich) 2019 Lin et al. 2018; Karimireddy et al. 2019 Stich & Karimireddy 2020 Khaled
et al. 2020 Hanzely & Richtárik 2020).
Communication Compression Methods. Another popular approach is to reduce the size of the object (typically gradients) communicated from clients to the master. This approach is referred to as gradi- ent/ /otecmmmmnicaton compression. In this approach, instead of transmitting the full-dimensional gradi- ent/update vector g E Rd, one transmits compressed vector C(g), where C R + 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). A particularly popular class of quantization operators is based on random dithering (Goodall] 1951; Roberts 1962); see Alistarr et al. (2017); ; Wen al. (2017): : Zhang et al. (2017); Ramczani-Kebryy et al. (2019). A new variant of random standard dithering. Sparse vectors can be obtained by random sparsification techniques that randomly mask the input vectors and preserve a constant number of coordinates (Wangni et al.) 2018 Konečný & Richtárik] 2018 Stich et al.) 2018
dithering developed in Horváth et al.] (2019) offers exponential improvement
Mishchenko et al.) 2019 Vogels et al. 2019). There is also a line of work (Horváth et al. 2019: Basu et al., 2019) which propose to combine sparsification and quantization to obtain a more aggressive combined effect
Client Sampling/Selectiann Methods. In the situation where partial participation desired and a budget on the number of participating clients is applied, a careful selection of the participating clients can lead to better communication complexity, and hence faster training. In other words, some clients will have "more informative" updates than others in any given communication round, and thus the training procedure will benefit from capitalizing on this fact by ignoring some of the worthless updates (see Figure []] We refer the readers to Section 4.1 for discussions on existing client sampling methods in FL and their limitations.
1.2 Contributions
We address the communication bandwidth issues appearing in FL by designing principled optimal client sampling scheme with client privacy and system practicalily in mind. We show that the ideas presented in the previous works on efficient sampling (Horváth & Richtárik] 2019 and sparsification (Wang et al. 2018 Wangni et al. 2018) can be adapted to be compatible with FL and can be used to construct a principled optimal client sampling scheme which is capable of identifying the most informative clients in any given communication round. Our contributions can be summarized follows:
2

---

Published in Transactions on Machine Learning Research (08/2022)
...
Optimal client sampling: in each communication round, all participating clients compute their updates, but only the ones with "important" updates communicate back to the master.
Figure 1:
Inspired by Horváth & Richtárik 2019 we propose adaptive partial participation strategy for reducing communication in FL. This stralegy relies on careful selection of clients that are allowed to communicate their updates back to the master in any given communication round, which then translates to a reduction in the number of communicated bits. We obtain this strategy by properly applying the sampling procedure from Horváth & Richtárik (2099) to the FL framework.
Specifically, building upon the importance sampling results in Horváth & Richtárik (2019 Lemina 1), we obtain an optimal adaptive client sampling procedure in the sense that it minimizes the variance of the master update for any budget m on the number of participating clients, which generalizes the thcoretical results in Zhao & Zhang 2015 that only applics to m 1.
Inspired by the greedy algorithm from Wangni et al. 20118 Algorithm 3) which was originally designed for gradient sparsification, we obtain an approximation to our optimal sampling strategy which only requires aggregation, fulfilling two core privacy requirements of FL: to our knowledge, our method is the first principled importance client sampling stratogy that is compatible with both secure aggregation and slateless clients.
Our optimal sampling method is orthogonal to and hence compatible with existing approaches to communication reduction such as communication compression and/or local updates (cf. Section 3.2
We provide convergence guarantees for our approach with Distributed SGD (DSGD) and Federated Averaging (FedAvg), relaxing number of strong assumptions employed in prior works. We show both theoretically and empirically that the performance of our approach is superior to uniform sampling and can be close to full participation.
We show both theoretically and empirically that our approach allows for larger learning rates than the baseline which performs uniform client sampling, which results in better communication complezity and hence faster convergence.
1.3 Organization of the Paper
Section _ describes the proposed optimal client sampling strategy for reducing the communication bottleneck in federated learning. Section 3 provides convergence analyses for DSGD and FedAvg with our optimal client sampling scheme in both convex and non-convex sottings. Scction 4 reviews prior works that are closely or broadly related our proposed method. Section empirically evaluates our optimal client sampling method standard federated datasets. Section summarizes the paper and lists some directions for future work.
3

---

is necessary in order Published in Transactions on Machine Learning Research (08/2022)
2 Smart Client Sampling for Reducing Communication
This section describes the proposed optimal client sampling strategy for reducing the communication bottleneck in fedcrated learning.
Before proceeding with our theory, we provide an intuition by discussing the problem setting and introducing the arbitrary sampling paradigm. In FL, each client participating in round computes an update vector U E Rd. For simplicity and case of exposition, we assume that all clients i [x] == 21, n) are available in each round In our framework, only subset of clients communicates their updates to the master node in each communication round in order to reduce the number of transmitted bits.
In order to provide an analysis in this framework, we consider a general partial participation frame- work (Horváth Richtárik 2020), where we assume that the subset of participating clients is determined by an arbitrary random set-valued mapping $ (i.c., a "sampling") with values in 2 A sampling & is uniquely defined by assigning probabilities to all 2n subsets of [n]. With each sampling S we associate probability matrir P R=*= defined by Pe == Prob((i,j) C The probability vector associated with S is the vector composed of the diagonal entries of P: p (pI....,PP, Pn)) R", where pa == Prob(i E S). We say that & is proper if p; > 0 for all i. It is casy to show that b = E [[S]] Trace (P) = Σi= Pt. and hence b can be seen as the expected number of clients participating in each communication round. Given parameters Pr. E [0, 1], consider a random set S S [n] generated as follows: for each E [rz], we include in S with probability pi. This is called independent sampling, since the event E is independent of j for any + j.
While our elient sampling strategy can be adapted to essentially any underlying learning method, we give details here for DSGD as an illustrative example, where the master update in each communication round is of the form
A+1 - = with G =
Wi
U
(2)
YES*
where 5 ~ sh and U = ot is an unbiased estimator of Vf((**). The scaling factor 1 p
to obtain unbiased estimator of the true update, i.e., Ega G > we U.UU
2.1 Optimal Client Sampling
A simple observation is that the variance of our gradient estimator G can be decomposed into
E |
E -
+
Σ
u v f(x*))
(3)
where the sccond term on the right-hand side is independent of the sampling procodure, and the first term is zero if every client sends its update (i.e,, if r¹ = for all i). In order to provide meaningful results, we restrict the expected number clients to commmicate in each round by bounding bt = >E=P? Pf by some
positive integer m I n. This raises the following question: What is the sampling procedure that ménimizes (3) for any given m!?
To answer this question, we connect Equation 3 to previous works on importance sampling (Horváth &
Richtárik 2019) and gradient sparsification (Wangui et al. 2018 Wang et al. 2018 2 Despite difference in motivation, these works solve up to a scale the equivalent mathematical problem, based on which we answer
the aforementioneed question by the following technical lemma (see Appendix A for a prool):
Lemma 1. (Generalization Horváth & Richtárik (2019. Lemma 1)) Let Çi, C2. Sn be vectors in Rd and w1, U2, ... Wn. be non-negative real numbers such that 1 W/ = 1. Define Ç == Ei= WiGi. Let S be a proper sampling. If u In is such that
P-ppT Diag(pre1,p22... un)
(4)
TThis is not limiting factor, as all presented thcory can be casily extended the case of partial participation with arbitrary proper sampling distribution. See Appendix for a proof sketch. Wangni et all (2018) consider slightly different problem, where they minimize the communication budget with constraints the variance.
4

---

Published in Transactions on Machine Learning Research (08/2022)
Algorithm Optimal Client Sampling (OCS).
1:
Input: expected batch size m
each client computes local update U (in parallel)
each client i sends the norm of its update u wi | to the master (in parallel)
master computes optimal probabilities p using equation 7
5: master broadcasts p to all clients
6:
each client i sends its update p. U to the master with probability p (in parallel)
then
WaC
U2 ||<: 11?
E
(5)
Pi
pi
iES
where the expectation is taken over S. Whenever
44 holds, it must be the case that 2 1 Ps-
It turns out that given probabilitics {pi). among all samplings S satisfying p; = Prob(i E S), the independent sampling (i.e., Pij = Prob(i,j E S) = Prob(i E 5) Prob(j E S) = PcPj) minimizes the left-hand side of 5 This is due to two nice properties: a) any independent sampling admits the optimal choice of e, ie., U 1 p; for all i, and b) ( holds equality for independent sampling. In the context of our method,
these properties can be written as
1 W
P
U
G
wi U
=
E
(6)
It now only remains to find the parameters (pt) defining the optinal independent sampling, i.e., one that minimizes (6) subject to the constraints 0 < p. < and b² = Em= P S m. It turns out that this problem has the following closed-form solution (see Appendix for a proof):
(m (m+1
10
i $ A
p
(7)
5-1
1.
if i
where Ü/ = w; U.U and [tk
the j-th smallest value in {110%²11 |B is the largest integer for which |/ (note that this inequality always holds for -= m + 1), and A contains indices i such that ||č;7|| Ü //// We summarize this procedure in Algorithm Intuitively, our method can be thought of as uniform sampling with ni E [m, nı] effective sampled clients, while only m clients are actually sampled in expectation, which indicates that it cannot be worse than uniform sampling and can be as good as full participation. The actual value of m depends on the updates.
0 << <<++l-n < E 11
Remark 2 (Optimality). Optimizing the left-hand side of (5) does not guarantee the proposed sampling to be optimal with respect to the right-hand side of (5) in the general case. For this to hold, our sampling needs to be independent, which is not very restrictive condition, especially considering that enforcing independent sampling across clients accommodales the privacy requirements of FL. In addition, since (5) is tight, our sampling is optimal if one is allowed to communicate only norms (i.e., one float per client) as extra information. We stress that requiring optimality with respect to the left-hand side of (5) in the full general case is not practical, as it cannot be obtoined without revealing, i.e., commanicating, all clients' full updotes to the master.
2.2 Ensuring Compatibility with Secure Aggregation and Stateless Clients
In the case n, the optimal probabilities of m mn| 11 |1,,|| can be computed casily: the master aggregates the norm of each update and then sends the sum back to the clients. However, if < n, in order
5

---

Published in Transactions on Machine Learning Research (08/2022)
Algorithm Approximate Optimal Client Sampling (ADCS).
1: Input: expected batch size m, maximum number of iteration Jmax
each client computes an update U (in parallel)
each client i sends the norm of its update ut wy |
to the master (in parallel)
master aggregates uº >i= uf
5: master broadcasts u to all clients
6: each client i computes p = min mxx
13 (in parallel)
7: for j = 1; .maa do
8: each client i sends the = (1, p..) to the master if p 1; else sends t = (0,0) (in parallel)
9: master aggregates (Ik, Pk) = E
10: master computes C m-n+!"
11:
master broadcasts C* to all clients
12: each client i recalibrates p.c min ( 13 if p. < (in parallel)
13: if O* < 1 then
14: break
15: end if
16: end for
17: cach clients i sends its update w: U to master with probability pf (in parallel)
to compute optimal probabilities, the master would need to identify the norm of every updale and perform partial sorting, which can be computationally expensive and also violates the client privacy requirements in FL, i.c., one cannot use the secure aggregation protocol where the master only sees the sum of the updates. Therefore, we create an algorithm for approximately solving this problem, which only requires to perform aggregation at the master node without compromising the privacy of any client. The construction of this algorithm is built upon the greedy algorithm from Wangni et al. 2018 Algorithm 3) which was originally designed for gradient sparsification but solves up to scale an equivalent mathematical problem. We first set o = 1// solution 7 this would be sufficient. However, due to the truncation operation, the expected number of sampled clients b² = Em= pf < E m||6; "r]1::
and 2t = min 1}. In the ideal situation where every o equals the optimal
m can be strictly less than m if p > 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, as summarized in Algorithm 2 This algorithm is much easier to implement and computationally more efficient on parallel computing architectures. In addition, only requires a secure aggregation procedure on the master, which is essential in privacy preserving FL, and thus it compatible with existing FL software and hardware.
Remark 3 (Extra communications in Algorithm 2j. We acknowledge that. Algorithm 2 brings extra commun- nication costs, as it requires all clients to send the norms of their updates of 's and probabilities p 's in each round. However, since these are single floats, this only costs O(juax) extra floats for each client. Picking Jmax = 01), this is negligible for large models of size d. We also acknowledge that engaging in meuliiple synchronous rounds of communication (as in Algorithm ? can be a bottleneck [Huba et al., (022). This is not an issue in our work, as we focus on reducing the total communication cost. However, Algoritim may be less useful under other setups metrics.
Remark 4 (Fairness). Based on our sampling strategy, it might be tempting to assume that the obtained solution could exhibil fairness issues. In our convergence analyses below, we show that this is not the case, as our proposed methods converge to the optimal solution of the original problem. Hence, as long as the original objective has no inherent issue with fairness, our method does not exhibit any fairness issues. Besides, our algorithm can be used in conjunction with other "more fair" objectives, e.g., Tilted ERM Li et al. 2021), if needed.

---

Published in Transactions on Machine Learning Research (08/2022)
3 Convergence Guarantees
This section provides convergence analyses for DSGD and FedAvg with our optimal client sampling scheme in both convex and non-convex settings. We compare the convergence results of our scheme with those of full participation and independent uniform sampling with sample size m. We match the forms of our convergence bounds to those of the existing bounds in the literature to make them directly comparable. We do not compare the sample complexities of these methods, as such comparisons would be difficult due to their dependence on the actual updates which are unknown advance and do not follow a specific distribution in general.
We use standard assumptions (Karimi al. 2016 assuming throughout that. f has unique minimizer at with f== f(x*) > -o0 and fi's are L-smooth, i.e, fi's have L-Lipschitz continuous gradients. We first define convex functions and L-smooth functions.
Definition 5 (Convexity). f: IRd R is p-strongly conver with p if
1 f(v) 2 f(x)(( (Vf(x). 2) 2 1ly x11 Vx, E Rd.
(8)
F: + is conver if it satisfies
8 with μ = O.
Definition 6 (Smoothness). f IRd R is L-smooth if
[V V((iill s || - vll, Vz,y Rd.
(9)
We now state standard assumptions of the gradient oracles for DSCD and FedAvg.
Assumption 7 (Gradient oracle for DSGD). The stochastic gradient estimator g V[((a*+ et of the local gradient V li fa(a"), for each round k and all n,..., n, satisfies
[ct]] =
(10)
and
E [|cc 2 lat < M [[(((>) 1 +o?, for some M 2 0.
(11)
This further implies that E A Dín of 1 = fz*h).
Assumption 8 (Gradient oracle for FedAvg). The stochastic gradient estimator gi(vit)) Vii(y,, + + of the local gradient V fi for each round k, each local step O,..., , R and all 1,..., n, satisfies
(12)
and
E [[lst,.ll ltr.]] S M /
)1 +0², for some M 2 0,
(13)
where vi.o x and whr vhr-1 moilt))) for ,,... R.
For non-convex objectives, one can construct counter-oxamples that would diverge for both DSGD and FedAvg if the sampling variance is not bounded. Therefore, we need to employ the following standard assumption of local gradients for bounding the sampling variance
Assumption 9 (Similarity among local gradients). The gradients of local loss functions ft satisfy
Σ w: (V/(()) v/(x) s p, for some p 2 0.
(14)
3This assumption required convex objectives, as can show that the sampling variance is bounded using smoothness and convexity.

---

Published in Transactions on Machine Learning Research (08/2022)
Remark 10 (Interpretation of Assumption Some works employ more restrictive assumption which requires [ V((=a))l S p. vi, from which Assumplion con be derived, since Σi=1 =1 Therefore, Assumption 9 con be seen as an assumption on similarity among local gradients. Furthermore, this assumption does not require w, 's to be lower-bounded, as clients with w; = will never be sampled and thus can be removed from the objective.
We now define some important quantities for our convergence analyses.
Definition 11 (The improvement factor). We define the improvement factor of optimal client sampling over uniform sampling:
E. EiEse U Pi
Ei= U;
a
(15)
Eieut U Σ wy U+
where S ~ ~* with pt defined in 7 and U* ~ U is an independent uniform sampling with p = m/n. By construction, 0 I a* 1, as S minimizes the variance term (see Appendiz B for a proof). Note that a can reach zero in the case where there are at most m non-zero updates. If a = O, our method performs as if all updates were communicated. In the worst-case a = =, our method performs as if we picked m updates uniformly at random, and one could not do better in theory due to the structure of the updates U.. The actual value of a* will depend on the updates U. We also define the relative improvement factor:
tht an m) + m
[m. k K
(16)
Definition 12 (Simplifted notation). For simplicity of nolation, we define the following quantilies which will be useful for our convergence analyses:
W == max(wuc, <E(m)
Z, = f((x²) - ft. ,
(17)
where 17 is the functional value of Jt al ils oplimuum, Z₁ represents the mismatch between the local and global minimizer, and 2h captures the distance between the current point and the ménimizer of f-
We are now ready to proceed with our convergence analyses. In the following subsections, we provide
convergence analyses of specific methods for solving the optimization problem ①I The proofs of the thcorems
are deferred to Appendices C and D
3.1 Distributed SGD (DSGD) with Optimal Client Sampling
This subsection presents convergence analyses for DSGD 2 with optimal client sampling in both convex and non-convex settings.
Theorem 13 (DSGD, strongly-convex). Let Si be L-smooth and conver for i = I,..., n. Let f be p-strongly convez. Suppose that Assumption holds. Choose r/ e (o, (14WM))) Define
B1 = Σ W (2T + M)Z, + 0²),
(18)
B2 2L n
w Zi.
(19)
The iterates of DSGD with optimal client sampling
7 satisfy
[1 (1 ((---n))r
| ||a]
11 (}- + (11²
(T -82)
(20)
8

---

Published in Transactions on Machine Learning Research (08/2022)
Remark 14 (Interpretation of Theorem 13). We first look at the best and worst case scenarios. In the best case scenario, we have 7 =1 for all k. k's. This implies that there is no loss of speed comparing to the method with full participation. It is indeed confirmed by our theory as our obtained recursion recocers the best-known rate of DSGD in the full participation regime (Gower et al.) 2019 Theorem 3.1). To provide a better intuition, we include a full derivation in this case. To match their (stronger) assumplions, we let M =0 and we = 1/n. In full participation, we have gh =1 for all k's. Then, taking the same step size oj for all leads to
+ n/ 202
[|] =1 un) E
(21)
Applying the above inequality recursively yields
17 σ²
E [| s <1 (1- pm)
" E [|]]
+
(22)
un
which equivalent. to the resull in Gower el al.) 2019 Theorem 3.1). Similarly, the worst case, we have 7h = m//n for all k k's, which corresponds to uniform sampling with sample size m, and our recursion recovers the best-known rate for DSGD in this regime. This is expected as (15) implies that every update U is equivalent, and thus it is theorelically impossible to oblašn beller vale than that of uniform sampling in the worst case scenario. In the general scenario, our obtained recursion sits somewhere between full and uniform partial participation, where the actual position is determined by 7h 's which capture the distribution of updates (here gradients) on the clients. For instance, with a larger number of 7t tending to 1, we are closer to the full participation regime. Similarby, with more ahe tending to m/n, we are closer to the rate of uniform partial participation.
Theorem 15 (DSGD, non-convex). Let fú be L-smooth for i I....,,. n. Suppose that Assumptions 7 and 9 hold. Let Ty be the step size and define
L 27
(1-
n Σ u
(23)
The iterates of DSGD with optimal client sampling
7
satisfy
E [f(xkt])] s E [f(())]]] -17² 178 (1- (1+
ML
E || f( + (3
(24)
2
24 recovers the standard form of the conwergence resull of DSGD for one recursion slep in the non-conver selling. Similar to the previous results, this convergence bound sits between the best-known rate of full participation and uráform sampling [Bottou et al. 2018 Theorem 4.8).
Remark 16 (Interpretation of Theorem 15). The iterate
3.2 Federated Averaging (FedAvg) with Optimal Client Sampling
Pseudo-code that adapts the standard FedAvg algorithm to our framework is provided in Algorithm 3 This subsection presents convergence analyses for FedAvg with optimal client sampling in both convex and non-convex settings.
Theorem 17 (FedAvg, strongly-couvesy Let fo be L-smooth and u-stronnly convex for i = I,...,n. n. Suppose
that Assumption 8 holds. Let 1/² untngg be the effective step-size and n 2 1 Σ x
Choose n¹a e
w?
(0.3) g min M/24 (+W(1+M/m))L
202 72
M
n
o =
W + 4L
2
+
Σ
w Zi.
(25)
R
R
8 = 7212
(1+
M
W WrZy
(26)
R
i=1
9

---

Published in Transactions on Machine Learning Research (08/2022)
Algorithm FedAvg with Optimal Client Sampling.
1: Input: initial global model w², global and local step-sizes 1g. 1/
2: for each round k ,,..., K do master broadcasts x to all clients E [n]] for each client E [n] (in parallel) do
initialize local model vio + **
for r ,,..., R do compute mini-batch gradient 9:(1( update yhrr + v Th gi (1) end for
7:
10:
compute U = Aut = x² -
11:
compute pt using Algorithm or send _h Ay, to master with probability x
12:
13: end for
master computes Ar = Eiest Ay! vi 15: master updates global model phtl + x Tl Art
14:
16: end for
The ittrates of FedAvg (R 2 2) with optimal client sampling
satisfy
a E [(((x))) [T] z 7 (1 pnf
1
||
[112) + 3 (3
(27)
x7t
Theorem 18 (FedAvg, non-convex). Let Js be L-smooth for all I....,n. Suppose that Assumplions
and 9 hold. Let 1/* = Rof n be the effective step-size and nt 2
E. wp Choose n/² E (0: BL(2+
Define
8h 8h= (
W L.
(28)
The iterates of FedAvg (R 2) with optimal client sampling
satisfy
3r7* (1- 10r L
E [[((+tt)]] < < [f(x)]]
PP [[ + (3/
(29)
Remark 19 (Interpretation of Theorems and 18 The convergence guarantees from Theorems 17 and 18 sit somewhere between those for full and uniform partial participation. The actual position is again determined by the distribution of the updates which are linked to ** 's. In the edge cases, i.e., 7tt == 1bestt case) or y m//n (worst case), we recover the state-of- thetr-rrt complexity guaranlees provided in (Karimireddy el al. 2019 Theorem 1) in both regimes. Note that our results are slightly more general, as Karimireddy et al. [2019] assumes M 0 and w; 1/n.
4 Related Work
This section reviews prior works that closely broadly related to proposed method.
4.1
Importance Client Sampling in Federated Learning
Several recent works have studied efficient importance client sampling methods in FL (Cho al.) 2020
Nguyen et al.] 2020 Ribero & Vikalo 2020 Lai et al.] 2021 Luo al. 2022 Unfortunately, of
10

---

Published in Transactions on Machine Learning Research (08/2022)
these methods is principled, as they rely on heuristics, historical losses, or partial information, which can be seen as proxies for our optimal client sampling. Furthermore, they violate at least one of the core privacy requirements of FL (secure aggregation and/or stateless clients). Specifically, the client selection strategy propased by Lai et al. (2021) is based on the hcuristic of system and statistical utility of clients, which reveals the identity of clients; Ribero& & Vikalo (2020) propose to model the progression of the model parameters by an Trastein-Uhlenbedd process based on partial information, where the master needs to process the raw update from each client. The work of Cho et al. (2020) biases client selection towards clients with higher local losses, which reveals the state of each individual client.
In contrast, our proposed method is the first principled optimal client sampling strategy in the sense that it minimizes the variance of the master update and is compatible with core privacy requirements of FL. We note that the client sampling/selecttoon techniques mentioned in this section could be made compatible with our framework presented in Section 2 but they would not lead to the optimal method as they are only proxies for optimal sampling.
4.2 Importance Sampling in Stochastic Optimization
Importance sampling methods for optimization have been studied extensively in the last few years in several contexts, including convex optimization and deep learning. LASVM developed in Bordes et al. (2005) is an online algorithm that uses importance sampling to train kernclized support vector machines. The first importance sampling for randomized coordinate descent methods was proposed in the seminal paper of Nesterov (0012). It was showed by Richtárik & Takáe (2014) that the proposed sampling is optimal. Later, several extensions and improvements followed, e.g.. Shalev-Shward & Zhang (2014); Lin et al. (2014); Fercog & Richtárik (2015): Qu et al. (2015); |Allen Zhu et al. (2016); Stich et al. (2017). Another branch of work studies sample complexity. Tn Needell et al. (2014), Zhao & Zhang (2015), the authors make 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. However, obtaining this distribution is as expensive as computing the full gradient in terms of computation, and thus it is not practical. For simpler problems, one can sample proportionally to the norms of the inputs, which can be linked to the Lipschitz constants of the per-sample loss function for linear and logistic regression. For instance, it was shown by Horváth & Richtárik (2019) that static optimal sampling can be constructed even for mini-batches and the probability is proportional to these Lipschitz constants under the assumption that these constants of the per-sample loss function are known. Unfortunately, importance mcasures such as smoothness of the gradient are often hard to compute/cstimate for more complicated models such as those arising in deep learning, where most of the importance sampling schemes are based on heuristics. For instance, manually designed sampling scheme was proposed in Bengio let al. (209)). It was inspired by the 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 common for deep embedding learning to sample hard examples because of the plethora of easy non-informative ones (Schroff et al.) 2015 Simo-Serra et al., 2015). Other approaches use history of losses for previously seen samples to ereate the sampling distribution and sample either proportionally to the loss based on the loss ranking (Schaul et al. 2015 Loshchilov & Hutter 2015). [Kahhaoppoloss & Fleurel 2018 propose to sample based on the gradient norm of a small uniformly sampled subset of samples.
Although our proposed optimal sampling method adapts and extends the importance sampling results from Horváth & Richtárik (2019) to the distributed setting of FL, it does not suffer from any of the limitations discussed above, since the motivation of our work is to reduce communication rather than reduce computation. In particular, our method allows for any budge m n on the number of participating clients, which generalizes the theoretical results from Zhao & Zhang 2015) which only applies to the case m= 1.
5 Experiments
This section empirically evaluates our optimal client sampling method on standard foderated datasets from LEAF (Caldas et al. 2018).
11

---

Published in Transactions on Machine Learning Research (08/2022)
Dataset 1 (32,90) 906 training images total)
Dataset 2 (29,906 training images in total)
Dataset (27,599 training images in total)
[ 17550
2000
19% dients hnld 52% rrining imags
2000
1750
20% clients hole 90% training images
$
2000
1750
50% clients holl 96% training images
11500
1300
11250
12500
+1250
1000
10000
11000
750
750
250
The
250
The
250
20
40
60
80
100
120
0
20
60
80
100
120
0
20
40
60
60
100
120
The Number of Training Images Client Holds
The Number Training Images Client Holds
The Number Training Imragss Client Holds
Figure 2: Distributions of the three modified Federated EMNIST training sets.
5.1 Setup
We compare our method with 1) full participation where all available clients participate in each round; and 2) the baseline where participating clients are sampled uniformly from available clients in each round. We chose not to compare with other client sampling methods, as such comparisons would be unfair. This is because they violate the privacy requirements of FL: our method is the only importance client sampling strategy that, is deployable to real-world FL systems (cf. Section 4.1
We simulate the cross-device FL distributed setting and train our models using TensorFlow Federated (TFF) We conclude our evaluations using FedAvg with Algorithm 2 as it supports stateless clients and secure aggregation We extend the TFF implementation of FedAvg to fit our framework. For all three methods, we report 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 Each figure displays the mean performance with standard deviation over 5 independent runs for each of the three compared methods. For a fair comparison, we use the same random seed for all three methods in a single run and vary random seeds across different runs. Detailed experimental settings and extra results can be found in Appendices F. and F.2 Our code together with datasets can be found at sttps://githun com cctm///Smmelllovvvtttt--ootooaae weienllceeettttllllp.
5.2 Federated EMNIST Dataset
We first evaluate our method on the Federated EMNIST (FEMNIST) image dataset for image classification. Since it is a well-balanced dataset with data of similar quality on each client, we modify its training set by removing some images from some clients, in order to better simulate the conditions in which our proposed method brings significant. theoretical improvements. As a result, we produce three unbalanced training sets as summarized in Figure 2 We use the same CNN model as the one used in (McMahan et al. 2017). For validation, we the unchanged EMNIST validation set, which consists of 40, 832 images. In cach communication round, = 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 E {3, 6). We use vanilla SGD optimizers with constant step sizes for both clients and the master, with f2 = and m tuned on a holdout set. For full participation and optimal sampling, it turns out that n = 2 is the optimal local step size for all three datasets. For uniform sampling, the optimal is m = 2- for Dataset and m = 2- for Datasets 2 and 3. We set jmax 4 and include the extra communication costs in our results. The main results are shown in Figures 3 and
"We compared the results of Algorithms 1 and 2 for all experiments as a subroutine. Their results are identical, so we only show results for Algorithm 2 and argue that the performance loss caused by its approximation is negligible.
"The communicaatin from the master to clicuts is not considered as bottleneck and thus not iucluded in the results. This is standard consideration for distributed systems, as one-to-many communication primitives (i.e., from the master to clients) are several orders of magnitude faster than many-to-one communication primitives (i.e., from clients to the master). This gap is further exacerbated in FL due to the large number of clients and slow client connections.
TThe aim of creating various unbalanced datasets to show that optimal sampling has more performance gains over uniform sampling on
unbalanced datascts, since a (defined in Equation 15 are more likely to be close to in this case. created using the following procedure. Let C (0, and a, N4, with < For given client with examples, we keep this client unchanged if ne S a ne 2 b, otherwise remove this client from the dataset with probability or only keep a randomly sampled examples this client with probability s.
These datasets
12

---

Published in Transactions on Machine Learning Research (08/2022)
1.5
5/0
0.5g
20
14395
Figure 3: (FEMNIST Dataset 1, n 32) Validation accuracy and (local) training loss function of the number of communication rounds and the number of bits communicated from clients to the master.
208
$20
64
5.5
1.0
solo
6/4g
0.5
from Gleets Mamte (x329)
www.wnnattddedeoooooooooo Matterocto
Figure 4: (FEMNIST Dataset 2, n= 32) Validation accuracy and (local) training loss function of the number of communication rounds and the nunber of bits communicated from clients to the master.
3.2
2.5
21.
22.0
6.0g
6.5
0.0
Cormiuntaaion loard
Conturke: Roure
D8a Commanteeeed from Glarta to Master (x02))
Biu Cormommaraaaeee from Chara toe Masaarrach
Figure (FEMNIST Dataset 3, n 32) Validation accuracy and (local) training loss as a function of the number of communication rounds and the number of bits communicated from clients to the master.
5.3 Shakespeare Dataset
We also evaluate our method on the Shakespeare text dataset for next character prediction. Unlike in the FEMNIST experiments, we do not change the number of examples held by each client this dataset. The vocabulary for this task consists of 86 unique characters. The dataset contains 715 clients, each corresponding to character in Shakespeare's 's plays. We divide the text into batches such that each batch contains 8 example sequences of length 5. We
two-hidden-layer GRU model with 256 units in each hidden layer. We set E {32, 128), m {2, 4. 6, 12}, Jmaz 4, and run several SGD steps for 1 epoch on each client's local dataset in every communication round. We use vanilla SGD optimizers with constant step sizes, with f7 = and 7) tuned on a holdout set. For full participation and optimal sampling, turns out that the optimal is vι = 2-2 For uniform sampling, the optimal is r = --, The main results are shown in Figures 0 and 7
5.4 Discussions
As predicted by our theory, the performance FedAvg with our proposed optimal client sampling strategy is in between that with full and uniform partial participation. For all datasets, the optimal sampling strategy performs slightly worse than but is still competitive with the full participation strategy in terms of the number of communicatio 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 (in the cases 2. As we increase the expected number m of sampled clients, the performance of optimal sampling increases accordingly, which is consistent with our theory (e.g., Theorem 18) and with the observations from Yang et al. (2021), and quickly becomes almost identical to that of full participation. Note that the uniform sampling strategy performs significantly worse, which indicates that careful choice sampling probabilities can go a long way towards closing the gap between the performance of naive uniform sampling and full participation.
13

---

Published in Transactions on Machine Learning Research (08/2022)
1.00
60
22
Ciema Hattr 1904
Cormuntatte ton Clanta Master
21
20
Figure 6: (Shakespeare Dataset, n = 32) Validation accuracy and (local) training loss as a function of the number of communication rounds and the number of bits communicated from clients to the master.
502
120 1.0 163
100 125
20
Cierssto buur)
22
Figure 7: (Shakespeare Dataset, 128) 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.
Also, it can be seen that the performances of our optimal client sampling strategy with m = and m = 12 match the performances of full participation in the cases n = 32 and n = 128, respectively, in terms of the number of communication rounds. We therefore conjecture that m (Vvñ) is sufficient for our optimal client sampling strategy to obtain identical validation accuracy to that of full participation in terms of the nunber of communication rounds.
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 a function of the number of bits commmicateed from clients to the master. For instance, on FEMNIST Datasel 1 (Figure 3). while our optimal sampling approach with m 3 reached around 85% validation accuracy after 26 10th communicated bits, neither the full sampling strategy nor the uniform sampling strategy with
3 is 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.c., 8x more, and uniform sampling approach needs to communicate about the same number of bits as full participation or even more. The results for FEMNIST Datasets 2 and 3 and for the Shakespeare dataset are of a similar qualitative nature, showing that these conclusions are robust across the datasets considered.
Finally, it also worth noting that the empirical results from Sections 5.2 and 5.3 confirm that our optimal sampling strategy allows for larger step sizes than uniform sampling, the hyperparameter search returns larger step sizes Y) for optimal sampling than for uniform sampling.
In Appendix G we present an additional experiment on the Federated CIFAR100 dataset from LEAF. The Federated CIFAR100 dataset is a balanced dataset, where every client holds the same number of training images. this setting, letting all clients perform 1 epoch of local training means that all clients have the same number of local steps each round. We show that our optimal client sampling scheme still achieves better performance than uniform sampling this balanced dataset.
6 Conclusion and Future Work
In this work, we have proposed principled optimal client sampling strategy to address the communication bottleneck issue of federated learning. Our optimal client sampling can be computed using a closed-form formula by aggregating only the norms the updates. Furthermore, our method the first principled importance client sampling strategy that is compatible with statcless clients and sccure aggregation. We have obtained convergence guarantees for our method with DSGD and FedAvg with relaxed assumptions, and have performed empirical evaluations of our method federated datasets from the LEAF database. The
14

---

Published in Transactions on Machine Learning Research (08/2022)
empirical results show that method is superior to uniform sampling and close to full participation, which corroborates our theoretical analysis. We believe that our proposed optimal client sampling scheme will be useful in reducing communication costs in real-world FL systems.
Some directions for future work are as follows:
A straightforward extension would be to combine our proposed optimal sampling approach with communication compression methods to further reduce the sizes of communicated updates.
In the settings where the communication latency is high, our proposed method may not be effective in reducing the real communication time. It would be interesting to extend our optimal client sampling strategy to take into account the constraints of local clients (e.g., computational speed, network bandwidth, and communication latency).
Acknowledgments
We thank Jakub Konečný for helpful discussions and comments. Most the work was done when WC was a research intern at KAUST and when SH was a PhD student at KAUST.
References
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. Qsgd: Communication sgd via gradient quantization and encoding. Advances in Neural Information Processing Systems, 30, 2017.
Zeyuan Allen-Zhu, Zheng Qu, Peter Richtárik, and Yang Yuan. Even faster accelerated coordinate descent. using non-umiform sampling. In International Conference on Machine Learning, pp. 1110 1119, 2016.
Debraj Basu, Doepesh Data, Can Karakus, and Suhas Diggavi. Qsparso-local-SGD: Distributed SGD with quantization, sparsification and local computations. In Advances in Newral Information Processing Systems, pp. 14668-14679, 2019.
Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. Curriculum learning. In Proceedings of the 26th annual international conference machine learning, pp. 41-48, 2009.
Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H Brendan McMahan, Sarvar Patel, machine
Daniel Ramage, Aaron Segal, and Karn Seth. Practical secure aggregation for learning. Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pp. 1175 1175-1191, 2017.
Antoine Bordes, Seyda Ertekin, Jason Weston, and Léon Bottou. Fast kernel classifiers with online and active learning. Journal of Machine Learning Research, 6(Sep))1579-1619, 2005.
Léon Bottou, Frank E. Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. Siam Review, 60(2):223 311, 2018.
Sebastian Caldas, Sai Meher Karthik Duddu, Peter Wu, Tian Li, Jakub Koneěný, H Brendan McMa- han, Virginia Smith, and Ameet Talwalkar. Leaf: A benchmark for federated settings. arXiv preprint arXiv:1812.01099 2018.
Yac Joe Cho, Jianyu Wang, and Gauri Joshi. Client selection in federated learning: Convergence analysis and power-of-choice selection strategies. arXio preprint arXim:2010.00 0123,,,0..... 2020.
Wenliang Du and Mikhail J Atallah. Secure multi-party computation problems and their applications: a review and open problems. Tn Workshop on New Security Poradigms, 2001.
Olivier Fercoq and Peter Richtárik. Accelerated, parallel, and proximal coordinate descent. SIAM Journal on Optimization, 25(4):1997-20) 2015.
WM Goodall. Television by pulse code modulation. Bell System Technicol Journal, 30(1):33 49, 1951.
15

---

Published in Transactions on Machine Learning Research (08/2022)
Slawomir Goryezka and Li Xiong. A comprehensive comparison of multiparty secure additions with differential privacy. IEEE Transactions on Dependable and Secure Compuling, 14:463-44 -406-34-7--- 2015.
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, California, 2019.
Filip Hanzely and Peter Richtárik. Federated lcarning of a mixture of global and local models. arXi::2002.05516, 2020.
Samuel Horváth and Peter Richtárik. Nonconvex variance reduced optimization with arbitrary sampling. Proceedings of the 36th International Conference on Machine Learning, 2019.
Samuel Horváth and Peter Richtárik. A better alternative to error feedback for communication-effiiieei distributed learning. arXiv preprint Xiv:22000. 11077, 2020.
Samuel Horváth, Chen- Yu Ho, Ludovit Horváth, Atal Narayan Sahu, Marco Canini, and Peter Richtárik. Natural compression for distributed deep learning. arXiv preprint arXiv:1905. 10988, 2019.
Junxian Huang, Feng Qian, Yihua Guo, Yuanyuan Zhou, Qiang Xu, Z Morley Mao, Subhabrata Sen, and Oliver Spatscheck. An in-depth study of LTE: Effect network protocol and application behavior on performance. SIGCOMM Computer Communication Review, 43:363-311 2013.
Dzmitry Huba, John Nguyen, Kshitiz Malik, Ruiyu Zhu, Mike Rabbat, Ashkan Yousefpour, Carole-Jean Wu,, Hongyuan Zhan, Pavel Ustinov, Harish Srinivas, et al. Papaya: Practical, private, and scalable federated learning. Proceedings of Machine Learning and Systems, 4:814-832, 2022.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mchdi Bennis, Arjun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning. Xixie preprint 3xXim:1912.0497 2019.
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and groximal-gradiens methods under the polyak-lojasiewizz condition. In Joint European Conference on Machine Learning and Knowledge Discovery in Dalabases, pp. 795 811. Springer, 2016.
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 arXic:1910.000 0037006778,,.1.1 2019.
Angelos Katharopoulos and François Fleuret. Not all samples are created equal: Deep learning with importance sampling. arviv preprinl Xrii:11803.0094,, 2018.
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter theory for local SGD on identical and heterogeneous data. Tn The 23rd International Conference on Artificial Intelligence and Statistics (AISTATS 2020), 2020.
Jakub Konečný and Peter Richtárik. Randomized distributed mean estimation: Accuracy vs. communication. Frontiers in Applied Mathematics and Slatistics, 4:62, 2018
Fan Lai, Xiangfeng Zhu, Harsha V Madhyastha, and Mosharaf Chowdhury. Oort: Efficient fodcrated
learning via guided participant selection. In 15th (USENIX) Symposium on Operating Systems Design and Implementation ((OSDT) 21), pp. 19-35, 2021.
Tian Li, Ahmad Beirami, Maziar Sanjabi, and Virginia Smith. Tilted empirical risk minimization. Tn International Conference on Learning Representations, 2021. URL http::///pppeeeeeeeeeeeefrrreeee K5YasWXZ130
Qihang Lin, Zhaosong Lu, and Lin Xiao. An accelerated proximal coordinate gradient method. In Advances in Neural Information Processing Systems, pp. 3059-3067, 2014.
16

---

Published in Transactions on Machine Learning Research (08/2022)
Tao Lin, Sebastian U Stich, Kumar Kshitij Patel, and Martin Jaggi. Don't use large mimi-batches, use local SGD. arxiv preprint arXiv: 18888888.71111 2018.
Lya Loshchilov and Frank Hutter. Online batch selection for faster training of neural networks. arXiv preprint arXis:1511.06343 2015.
Bing Luo, Wenli Xiao, Shiqiang Wang, Jianwei Huang, and Leandros Tassiulas. Tackling system and statistical heterogeneity for federated learning with adaptive client sampling. In IEEE INFOCOM 2022- IEEE Conference on Computer Communications, pp. 1739-1748. IEEE, 2022.
Brendan McMahan, Eider Moore, Danicl Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communicttion efficient. learning of deep networks from decentralized data. In Artificial Intelligence and Slatistics, pp-
2017.
Konstantin Mishchenko, Filip Hanzely, and Peter Richtárik. 99% of parallel optimization is inevitably a waste of time. arXiv preprint 5XXi:1901.09433 2019.
Deanna Needell, Rachel Ward, and Nati Srebro. Stochastic gradient descent, weighted sampling, and the randomized kaczmarz algorithm. In Advances in neural information processing systems, pp. 1017-1025, 2014.
Yu Nesterov. Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM Journal on Optimization, (2(2):341-33) 362, 2012.
Hung T Nguyen, Vikash Sehwag, Seyyedali Hosseinalipour, Christopher G Brinton, Mung Chiang, and H Vincent Poor. Fust-convergent federated learning. IEFE Journal on Selected Areas in Communications, 29(1):201 218, 2020.
Zheng Qu, Peter Richtárík, and Tong Zhang. Quartz: Randomized dual coordinate ascent with arbitrary sampling. In Advances in Neural Information Processing Systems 28, pp. 865-873, 2015.
Ali Ramezani-Kebrya, Fartash Faghri, and Daniel M Roy. NUQSGD: Improved communication efficiency for data-parallel SGD via nonuniform quantization. arXiv preprint
2019.
Monica Ribero and Haris Vikalo. Commmicatioon-ffiieett foderated learning via optimal client sampling. 2020.
arxiv preprinl ar orXi:20077.51111
Peter Richtárik and Martin Takáč. Iteration complexity of randomized minimizing composite function. Mathematical Programming, 144(1-2):1 2014.
descent methods for
Lawrence Roberts. Picture coding using pseudo-random noise. IRF Transactions on Information Theory, 8 (2):145-155 154,,15,,1111 1962.
Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver. Prioritized experience replay. arXiv preprint urXiv:1511.05055 2015.
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, pp. 115-823,110 2015.
Shai Shalev-Shwartz and Tong Zhang. Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization. In International conference on machine learning, pp. 64-72, 2014.
Edgar Simo-Serra, Eduard Trulls, Luis Ferraz, Iasonas Kokkinos, Pascal Fua, and Francesc Moreno-Nogues Discriminative learning of deep convolutional feature point descriptors. In Proceedings of the IEEE International Conference on Computer Vision, pp. 118 126, 2015.
Jinhyun So, Başak Güler, and Salman Avestimchr. Turbo-aggrogate: Breaking the quadratic aggregation barrier in secure federated learning. IEEE Journal on Selected Areas in Information Theory, 2(1):479-45) 489, 2021.
17

---

Published in Transactions on Machine Learning Research (08/2022)
Sebastian U Stich. Local SGD converges fast and communicates little. ICLR 2019 International Conference on Learning Representations, 2019.
Sebastian Stich and Sai Praneeth Karimireddy. The orror-feedback framework: Better rates for SGD with delayed gradients and compressed communication. ICLR 2020 International Conference Learning Representations, 2020.
Sebastian Stich, Anant Raj, and Martin Jaggi. Safe adaptive importance sampling. In Advances in Neural Information Processing Systems, pp. 4381-4391, 2017.
Sebastian Stich, Jean-Baptiste Cordonnier, and Martin Jaggi. Sparsified SGD with memory. In Advances 2018.
in Newral Information Processing Systems, pp.
CH Van Berkel. Multi-core for mobile phones. In Conference Design, Automation and Test in Europe, 2009.
Thijs Vogels, Sai Praneeth Karimireddy, and Martin Jaggi. PowerSGD: Practical low-rank gradient compres- sion for distributed optimization. In Advonces in Neural Information Processing Systems, pp. 14236 14245, 2019.
Hongyi Wang, Scott Sievert, Shengchao Liu, Zachary Charles, Dimitris Papailiopoulos, and Stephen Wright. Atomo: Conmunicationn-eficien learning via atomic sparsification. Advances in Neural Information Processing Systems, 31, 2018.
Jianqiao Wangni, Jialei Wang, Ji Liu, and Tong Zhang, Gradient sparsification for communicationn-fiiceee distributed optimization. In Advances in Newral Information Processing Systems, pp. 1229-11300 2018
Wei Wen, Cong Xu, Feng Yan, Chumpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Terngrad: Ternary gradients to reduce communication in distributed deep learning. In Advances in Neural Information Processing Systems, pp. 1509 1519, 2017.
Haibo Yang, Minghong Fang, and Jia Liu. Achieving lincar speedup with partial worker participation in non-iid federated learning. arXiv preprint arXiv:2101.11203 2021.
Hantian Zhang, Jerry Li, Kaan Kara, Dan Alistarh, 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, pp. 4035-4043. JMLR. org, 2017.
Peilin Zhao and Tong Zhang. Stochastic optimization with importance sampling for regularized loss mini- mization. In international conference on machine learning, pp. 9, 2015.
18

---

Published in Transactions on Machine Learning Research (08/2022)
A Proof of Lemma 1
Proof. Our proof technique can be seen as an extended version of that in (Horváth & Richtárik 2019 Let
1 = 1 if E S and 1ies = otherwise. Likewise, let lijes = 1 if i, E $ and 1ijes = otherwise. Note that E. [1es] Ps and E. [T.jes] Pij- Next, let us compute the mean of X = Dies wili
E E = E
waCi
E
wiSi
Lies
wist Pi
E [Lesl = Σ wi =Ç
Pi
Pi
EES
Let A= [ai..... an) E Rdxn, where w.S: and let be the vector of all ones in R We now write the variance of X in form which will be convenient to establish bound:
1[II
E
[[]]|
|
|[[[]]|
E
3
||
Ps
wiGi
wiSi
E.
lijes
-|211
Pi
Pj
(30)
WiS. Wiym
Σ
w.w So
Pij
Pi
Pj
1
i.j
Σ (pij - p.P;)aa aj
i
e ((P pp T A A)c.
Since, by assumption, have P pp 3 Diag(por), can further bound
e (PP-p))) A A A)e < e (Diag(Doopp A A A)e = Σ Pad |a.11
To obtain 5 it remains to combine this with
30
The incquality vi 1 p. follows by comparing the
diagonal elements of the two matrices in Consider now the independent sampling. Clearly,
(1 Pi)
P2 p2)
0
P- pp T
Diag(prei, .nn
0
Pn Pw)
which implics 0, Pt.
B The Improvement Factor for Optimal Client Sampling
By Lemma I the independent sampling (which operates by independently flipping coin and with probability Pi includes element into 8) is optimal. In addition, for independent sampling. (5) holds as equality. Thus, letting U* = wy: U we have
āg.h =
Σ iESt
Σ
=E
Σ
E
(31)
RESk
The optimal probabilities are obtained by minimizing and 2 1/
w.r.t. {pf 1 subject to the constraints 0 p.
19

---

Published in Transactions on Machine Learning Research (08/2022)
Lemma 20. The optimization problem
min
as (1p s.t. OS 1,, Vi= = 1, n and m 2
Σ Ps
(32)
has the following closed-form solution:
10
(m (m+ 11)
i $ A if A
pt
(33)
5-
1,
where | is the j-th largest value among the values |0 | ..... || 1 is the largest inleger for
which 0 < m + I- - < Σ 1
(note that this inequality at least holds for L = + 1), and A contains
indices i such that | 2
Ü (-
Proof. This proof uses an argument similar to that in the proof of Lemma 2 in Horváth & Richtárik (2019) We first show that (33) is the solution to the following optimization problem:
min Ogt (1p.) E
s.t. OS S 1, Vi = n and 2 pr
The Lagrangian of this optimization problem given by
n
n
a
1l (1. (ui]i y) Qg (frt)E2))
Σ
Aap Σ
u p.) - m
y
p
Since all constraints linear and the support of {p/ is convex, the KKT conditions hold. Therefore, the solution (33 can be deduced from the KKT conditions. Now, notice that ås* (fpt)= and Ug (fp! (p)))
are equal up to a constant E Σ ||0+1]]]
a (1r/ Ogn (p.)))) E
0 1
This indicates that
133 is also the solution to the original optimization problem
32
Plugging the optimal probabilities obtained in
33 into
31 gives
2 |]
az. n
10,11
m (n 1)
With m (m)) < D ==
| ||
we have
|
Σ
1
E
m Σ
n
|13111
(1-m) m
Σ
110811
EE 1|0
m
27
E
mm
20

---

Published in Transactions on Machine Learning Research (08/2022)
For independent uniform sampling U ~ U (p)
for all i), we have
Ōeyzk == E
Σ PEU
Wi
U
Σ W U
E
n
1
n
m
1 2
m
m
Putting them together gives the improvement factor:
mn U Ei= 0 E. Erest
of
U
E
( i=1
|) |
a
gh
S 1.
E
Eiece t
U
شي wy U
The upper bound is attained when all || are identical. Note that the lower bound 0 can also be attained in the case where the number of non-zero updates is at most m. These considerations are discussed in the main paper.
C DSGD with Optimal Client Sampling
C.1 Proof of Theorem 13
Proof. L-smoothness of fo and the assumption on the gradient imply that the inequality
E
||
s 2L(1 + M)(f((**) - fx(x*) + Z,) + +
holds for all O. We first take expectations over x1+1 conditioned on zt and over the sampling Sh:
|
27
E
1 11- 2
Σ gr nd)
wi
+ (
Σ It
Wi Pe
iESA
= =|/d 2n (Vf(x*), r²) + (n7))²
E
Σ
Wi D
9
Wigt
+ E
Σ
wigt
BESt
s (1 - wn)²) ||, 21 (f(a*) - 1*) + (1/3/2
E
Σ
Wc
9
wagh
k
+
Σ wist
Pi
iESt
2=1
where
27
n
n
Wi Hr
11
9 2
Wig
iESt pd
m
10? (111 </((==))1 1| [|(
m
(1157)12 2 +1((((=))19)
m
1:
(2L M)(((=)) - f((x)= + Z,) + 03)
< k.
2WL(1+ -ft) Σ
w ( M) M)2; 1012++00) +00)
1=1
21

---

Published in Transactions on Machine Learning Research (08/2022)
and
vf(a+)) 1] + +|\
ws V/i 11] + ||
E
1=1
Σ
||s 19] + +|
- +2 f*)
2L (1 WM - Σ (2LMZ + +
Therefore, we obtain
E |1 5 (1 - - |1 -21 (f(**)- -f*)
(n7))2 21 + (1 - -5²) Σ w (2LMZ; -09)
(1/))a² n m
2WT(11 +M( 5*) Σ m (2T(11 M) + 03)
$ (1 uun |1r0 -21 (1-1) (a (n- - (n=
(11m-m)- + m))+)((1 + (1(x*)- - -5)
m
+ (1)²)2 a (n -m) +
Σ
w w2 + MyZ M)2,+ (1) >
w
m
1=1
Now choose any 0 < x²* <
m (m and define
B1 " (1 + M)Z, + +00), 82 2L
>
w Zi, atth
m
E
m
a - m) + m
Taking full expectation yields the desired result:
E [1 [|]] s (1 - --1=m)))) E || + (174)2
{3
:/2
(T
C.2 Proof of Theorem
15
Proof. Using equation 2 we have
f(a f(a* r/ G
(r²) " (c+, ((Ee)))))))) for some 2t E Rd.
f(**) n (G*, vf(t))
Since all fi' are L-smooth, f is also L-smooth. Therefore, we have -LI - (²f(2) = LI for all x E Rd. Combining this with the fact that Gk is an unbiased estimator of vf(x*), we have
E [[((a+]]] s S(())) +,* || + (nt)²2
2 B ||
(34)
22

---

Published in Transactions on Machine Learning Research (08/2022)
where the expectations are conditioned on x². In Appendix C.1 the last term in equation 34
already obtained the upper bound for
E
[||
M)a
n
M
Σ u
[/((+>)|| + - mn
o²
m
i=1
1 + M
+
1 Σ 7t
w + |f(2
i=1
By Assumption we further bound
n S W Σ w/ |[
i (i((">>>''
wi |[/[((tt)) + +|(s(a*))1)
S W
+
W
Combining the incqualitics above and taking full expectation yiclds equation 24
D FedAvg with Optimal Client Sampling
Lemma 21 (Karimireddy et al. 2019 ) For any L-smooth and u-strongly conver function h Rd + and any I, U. 2 R", the following incquality holds
(Vh(z), =
- y) 2 l1(z) h((v) + lly - ==12 2-12- 1|=
x1|² -
(35)
Proof. For any given v, y, and 2, the two inequalities below follows by the smoothness and strong convexity of the function h:
(vh(z), - 1(2)) h(x)
2 || - 2
(Vh()) - v) 2 h(x)) h(()) + yyy x
Further, applying the relaxed triangle inequality gives
" 1v x11 ll =11a 2
1 || - =||2
Combining all these inequalities together have
L p
(Vh(x), v) 2 h(2) Mw)) ly 211²
||2 x²12
2
The lemma follows by L>
D.1 Proof of Theorem 17
Proof. The master update during round A can be written (superscript is dropped from here onward)
Ng Ar
7 Σ
wi (y
and E [[nAAr]
= " Σ w,E (1
R iEST
R
1.r
23

---

Published in Transactions on Machine Learning Research (08/2022)
Summations are always over [n] and r [R] unless stated otherwise. Taking expectations over conditioned on the results prior to round & and over the sampling S gives
E
|| A x*1p]]
=
||
x²11
2n
Σ
ww) fd
x²)
E
Σ iES,r
W D (v
R
R2
Pi
3,
A
Applying Lemma 21 with h wifss x 15 y x² and gives
2m Σ (wsf((x) w,fe(x*) wi 1 1100 x=11² we L 1|e vi.r
A1 S R
$ 22 ((xx) - f*+ + 1
$/4 | x² 112) - 2TmE,
where E is the drift caused by the local updates on the clients:
Σ W.E o yt.
111--112 112
(36)
Bounding A2, we obtain
27
1
A2 =
W:
De (
Σ
wi R
Σ
gi
+
Σ
wi R
Σ
9 (3
172
R
iES
27
< 0
m
Σ
W
R
Σ
ge (16.--1))
+E
Σ
Wi R
Σ
gl (Vi,rr)11)
m
27
m
E
Eir-1
+
fo
m
R
R
1
+ F
Σ
Wi: R
Σ
-
+
Σ
Wi
Vi
24

---

Published in Transactions on Machine Learning Research (08/2022)
Using independence, zero mean and bounded second moment of the random variables E,r; we obtain
1
A2
S
a
n
m
1 E
Σ
|16
11]
+E
f
m
R2
R
+
i
E
|16
1P]
+E Σ
Wi R
Vi(()er-1)
R
m
Σ
((#²
[M
1
Σ E
V 1)1
0²
Q
ii
+
m
R
R
+
M
Σ
E
( |1
+
0² R
+E
W R
1
Vi((
R²
0²
W
+
M
+
M
+1
a m
m
Σ
wi
1
E
Ry
R
R
R
E
Σ
Wi
1
V
fi 1) vf((2)) + V=)
R
0²
+
M
+
M
+1
a m
m
Σ ui
2 Σ E ( + 2E [IVAGN))))
Ry
R
R
|
+
+E
Σ uc
1
V f(
-
-
+E [
Combining the smoothness of ft's, the definition of &, and Jenson's inoquality with definition y we obtain
== a(n ((n-m)+mm +m
1
A2
0²
Σ
10
2
+
M.
M
+1
n n-m )
21 Σ wf 74
17
Ry
R
m
+ 22L + 4L(f(z) f(xx))
Ry Σ w + 2T.2 (1- (1-W)+ W) + 7 R
0²
W
M +1
11 M
(M
+1) - Σ up Zu
-
E + 4L
R
+ W M
γ R - 1) (f(z) (T).
+ 4L (1 - W) (1-W)+
Putting these bounds on Ai and A2 together and using the fact that 1- W & 1/7 yields
E 8|1cc- Ar 2*11]] s (1
2) || 1=1 112--22 2n
(1
(1-21" 21_²
w
M
+1
+1)) (f(x) - )
R
+ 172
0²
Σ w/ + 4L
M
+1 - Σ
w u Zi
Ry
7 R
W
M
+1))) 2LME.
+ 1| (1- W) +
+ 1
γ
R
Let S (/-W(()//)))>> then
3 < 1 - 21 !
M
W
R +1 + +1).
4
7
25

---

Published in Transactions on Machine Learning Research (08/2022)
which in turn yields
E | 1e---i M1 Ar
- (1- pm)
10 x 112
3/ (5(z) - -5²
33
+ r/
0²
E
uf + 4L
1 M
+1 1 Σ wfZi
-
Riy
7
R
W
M
+1 +1))) 2T.E..
+
1 + nT.
(1- W) (1-W)++ +
(37)
R
Next, need to bound the drift E. For R 2 2, we have
E [1vir - x||3] = E |1 x mgr (i::(vi.r-111
[1be.-11 - x- - 11 ( }|1]]
+ (M [V/((+)-))) +02)
1
1 + R- 1
E
|1 - [||
+ (R + M)n
1
- x=|²]
1 +
M
n/²
1100
1 + R
E
+
1
R
RM
R2ng
1
E
[1eA.r-1 - x1|2] +
+
M
211²
-
R 1
R
Rm
MY
2112
[+:{( + 17022
+
1
R
Rmy
Ren2
S
1
1
+
+
M
2n
|1wir-1 - <|1²]
+
011 1+
M
2n²²
|V
+
11002
R
R-1 1
R
Rog
R
Rog
If we further restrict S 8/(2+M/R) then for any fg 2 1, we have
M
2
2L
1
1 1+
5
<
S
R
Bog
Rog
64L
32R
32 - 1)'
and therefore,
E [1uer 1aar-x111 x0|²] 5
1+
33
E
[[NA-r-1 xx|]| + (1+
M
2T²
+ 17202
32(R
- 1)
R
Riy
R2ng
33
(((11 (1++
M
2n²
n²022
1
f1())) +
32(R
1)
R
12211
T=0
< 8R
(1+
M
2n
1²202
R
Rnz
R2m
1+ M
8n²0²
16
2
R
26

---

Published in Transactions on Machine Learning Research (08/2022)
Hence, the drift is bounded by
M
Σ me [V][( + 811²0²
33 16
+ R
1
Rmg
M
r T. Σ (i(fi(x)- - fi) + 81f202
S 32
1 R
Riig
1+ M
M
81)20²
32
1/ L(f(z) -f)+ 32 1+ R
1/² L Σ
w,Z, +
R
Rig
<nn(f(z) f*) + 32 1+
M
n/2L Σ
w. Zz
811²0²
R
Rug
Due to the upper bound on the step size 11 S (1224/88)
we have the inequalities
1 1+ (1- W) + 7 R +1
W
- and 8 < 1.
(38)
Plugging these to
37 we obtain
|| - 7o Ax 2112]] $ 5
pn
| -
2 (g(((()) -rm)
3
+ 17²
0²
7
+
Σ i
+ 4L
M
+ 1 - 7) Σ w Z;
RR
R
+ T2L2
(1+
M
Σ
wi Zi.
R
Rearranging the terms in the last inequality, taking full expectation and including superscripts lead to
3 (
-
1
1
E
||
2111"]
1
- x²11"] [||+tt1=++11
2
n
+ n³
o²
+
Σ m
+ 4T,
M
+ +1--9
- x+) >
Ew33 u/ 7e
R
19
R
+ (TT))7222
(1+
M
Σ
Zi-
R
Plugging the assumption 1/
x
into the RHS of the above inequality completes the proof.
Σ m
D.2 Proof of Theorem
18
Proof. We drop superscript and write the master update during round k as:
ng Ar
7
Σ
Wi
(v = n
R
SES
27

---

Published in Transactions on Machine Learning Research (08/2022)
Summations are always over e [n] and r E [R] unless stated otherwise. Taking expectations conditioned on x and using a similar argument as in the proof in Appendix C.2 we have
2²L E
B - ( Ax)]] s f(x) - 7 (Vf(2)
)
2
= f(x) 7 [V)(( + 17 (z)) Vf(²) - E [E + n E
A |]
|
$ f(x) - 2 [+((=)] + " [|] - Es [1]1 21 + E
" L
|
2
2
where the last incquality follows since (a s 1 lall + 1 |b8 Va,bER" Since ft's are L-smooth, by the (relaxed) Iriangular inequality, we have
7 |V/(c) - B| = E
Σ wi (Vi((z) - (ilrrr--))
n
i,
122 w,EE
nT?
1
Σ
||0 - Vi, 11
2 E,
2R
where& & is the drift caused by the local updates on the clients as defined in (36
In Appendix D.1 we already obtained the upper bound for A2 = E ||
E
21 S ||||
: +
2W
M
M
+1
(m))) )
n m m
13'7+ + Σ wi [V +21 (1LEE+21VV(>II+
Ry
R
R
Together with Assumption g
that
Σ
= Σ uh -V]( sp sp
we have
E ||
0² Ry
2W M
+ +1) (128+ [+]())))+ + +T. - 2 2(
R
Combining the above inequalities gives
E Elf(x ngArr] < f(x) + 7 212 Σ
2 + nL?
nn (1
W)
+ W (1+ M) ))
+ 1) 8
?
nT (1 (1-W) W) + W
M
+ 1
+
||{{())11
γ
R
2
+ n nL (1- () + W
M
1
+
-nL
nL
γ
R
Now, applying inequality
18 gives
E[f(x - ngA=]l S f(x)+ +
Σ
+
1.
8 ε
31
[Vf(2)1 + '1(1 LL_8L)).
2Ry
8
In Appendix D.1
we also obtained the upper bound for the drift E:
M
W [V)( + 812202
E 16
1+
n
R
M
(z) 2 + p) + 817202
< 16
1+
V
R
Rng
28

---

Published in Transactions on Machine Learning Research (08/2022)
Since 8nL - SnL(1 + M/R)= 1, we have
5 & $ 10n
) (1 (IVf(2)]1* + +)
1.2
1
R
Rng
(IV] +) 5n2
4
8R
This further simplifies the iterate to
E ((x)
3 8"
31113
(1
3
10
n
|V)(())] + 1 51 2nL) p+
o2OZL
57 40
Σ
2Ry
Applying the assumption that f/
50 V 1 Σ,
and taking full expectations completes the proof:
(I 1, [[f(x)]
8"
3
(1-3 (1-
[1
10
E [[V](E))]]
af +1p + (
o² a
w
L.
Ro
E A Sketch of Results on Partial Participation
This section discusses how analysis can be extended to the case where not all clients are available to participate in each round. As an illustrative example, we consider Distributed SGD (DSGD), i.c., U = =
If not all clients are available to participate in each communication round, we will assume that there is a known distribution of client availability Q such that in each step a subset @+ ~ Q clients are available to participate in a given communication round We denote the probability that client i is available in the current run by q. i.c., q Prob(i e º²). Under this setting, we can apply twice tower property of the expectation and obtain the following variance decomposition:
G (f(a))]1
E
E
G
wi 9i
U
@*
E
Σ
W:
U
Σ
a
wi
U
+
n w
U
vf((at)
qi
iegi
iEQ
(39)
where we update the definition of &
W
(40)
iE 9.P.
Note that 5 * all clients are available, the above equations become identical to the ones that present in the main paper.
only sample from available clients. Furthermore, in the particular case where
Upper-bounding Equation 139 in an analogous way as we proceed in our analysis in Appendices C and
would complete the proof of convergence for these settings.
F
Experimental Details
F.1 Federated EMNIST Dataset
We detail the
used in the experiments on the FEMNIST datasets. For each experiment, we 151 communication rounds, reporting (local) training loss every round and validation accuracy every
29

---

Published in Transactions on Machine Learning Research (08/2022)
1.0
Validation Accuracy
0.8
Validation Accuracy
0.8
0.6
0.4
optmall samplng (m-3, 22]2)
0.4
uniform
semplng
0.2
uniform sampling (m-a, n=22)
full partiopation (mn32, n2)
0.0g
20
40
60
80
100
120 140
160
0.0
2
2
Communication Round
Bits Communicated from Clients to the Master (x10*)
Figure 8 (FEMNIST Dataset 32) current best validation accuracy function of the number of communication rounds and the number of bits communicated from clients to the master.
1.0
1.0
Validation Accuracy
0.8
Validation Accuracy
0.8
0.6
0.6
0.4
0.4
sampling
0.2
optmal sampling
0.2
uniform sampling (m-6, 223
full partkipation 1m-32. n=1
0.0g
20
40
60
80
100
120 140
160
0.0
24
29
2
2
Communication Round
Bits Communicated from Clients to the Master (x10*)
Figure (FEMNIST Dataset 2, 32) current best validation accuracy as a function of the number of communication rounds and the number of bits communicated from clients to the master.
1.0
1.0
Validation Accuracy
Validation Accuracy
0.8
0.6
0.6
optmal sampling
0.4
uniferm sampling n==3)
0.2
optmal sampling (m-6, 22)
0.2
unifrrm sampling (m-6,, nm32)
full parikipation (m=32.
0.0
0.0
2
2
26
2
2
Communication
Communicated Clients to Master (x10*)
Figure 10: (FEMNIST Datasel 3, n = 32) current best validation accuracy as function of the number of communication rounds and the number of bits communicated from clients the master.
0.4
Validation Accuracy
Validation Accurary
0.3
0.2
0.2
0.1
oonel troit nwayy sumoll rnve mid2l
awimmcaae cavelii greck nwi0
0.1
antornnniing (m- med2)
sarticbution (e-02 me22
0.0g
200
40
100 Communication Round
60
120
140
160
0.0
24
2
2
210
Bits Communicated from Clients to the Master (x100)
Figure 11: (Shakespeare Datasct, 32) current best validation accuracy as function of the number of communication rounds and the number of bits communicated from clients to the master.
30

---

Published in Transactions on Machine Learning Research (08/2022)
0.4
Validation Accuracy
Validation Accuracy
0.3
0.3
0.2
0.2
0.1
-etinol Lavelin troed meca
Ledim canull (1od 120
0.1
ostimal ramoling 10
semorig /end m-220)
pl 2n-128 1-220
0.0g
20
40
60
80
100
120
140
160
0.0
2
2
2
2
2
2
Communication Round
Bits Communicated from Clients to the Master (x10*)
Figure 12: (Shakespeare Dataset, n = 128) current best validation accuracy function of the number of communication rounds and the number of bits communicated from clients to the master.
5 rounds. In each round, 32 clients are sampled from the client pool, each of which then performs SGD for 1 epoch on its local training images 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 E {3, 6}. We use vanilla SGD and constant step sizes for all experiments, where we set 72 = 1 and tune fr from the set of value 12- $,2 2.... If the optimal step size hits a boundary value, then we try one more step size by extending that boundary and repeat this until the optimal step size not a boundary value. For full participation and optimal sampling, it turns out that 1II 2- is the optimal local step size for all three datasets. For uniform sampling, the optimal is m 2 for Dataset and f2- = 2 for Datasets 2 and 3. For the extra communications in Algorithm 2 we set Imax = 4.
We also present some additional figures of the experiment results. Figures and 10 show the current. best validation accuracy as a function of the number of communication rounds and the number of bits communicated from clients to the master on Datasets 1, 2 and 3, respectively.
F.2 Shakespeare Dataset
We detail the hyper-parameters used in the experiments on the Shakespeare dataset. For each experiment, we run 151 communication rounds, reporting (local) training loss every round and validation accuracy every rounds. In each round, n E (32, 128} clients are sampled from the client pool, each of which then performs SGD for epoch its local training data with batch size 8 (each batch contains 8 example sequences of length 5). For partial participation, the expected number of clients allowed to communicate their updates back to the master is set to E {2, 6, 12}. We use vanilla SGD and constant step sizes for all experiments, where we set f1 = and tune from the set of value {2-1 2-..2-2. 2,.2-, 2.2 If the optimal step size hits a boundary value, then we try one more step size by extending that boundary and repeat this until the optimal step size is not a boundary value. For full participation and optimal sampling, turns out that π = 2- is the optimal local step size. For uniform sampling, the optimal is rp = 2-3 For the extra communications Algorithm
2 we set Jmaz 4.
We also present additional figure of the experiment result. Figures and 12 show the current best validation accuracy as function of the number of communication rounds and the number of bits communicated from clients to the maste for the cases = 32, 128, respectively.
G Additional Experiment on Federated CIFAR100 Dataset
We evaluate our method on the Federated CIFAR100 image dataset for image classification. The Federated CIFAR100 datasct is balancod datasct, where every client holds the same number of training images. In each communication round, 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. This means that all clients have the same number of local steps in cach round. For partial participation, the expected number of clients allowed to communicate their updates back to the master is set to m 3. We use vanilla SGD optimizers with constant step sizes for both clients and the master, with fg = 1 and y tuned holdout.
31

---

Published in Transactions on Machine Learning Research (08/2022)
2020
24.6
15
2011
6.10
3030
2.00
30.s
8.00
2%5
21 Communtanio Mester
Cant
Figure 13: (CIFARI00 Datasel, 32) Validation accuracy and (local) training loss function of the number of communication rounds and the number of bits communicated from clients to the master.
set. For full participation and optimal sampling, it turns out that Y = 1 x 10-3 is the optimal local step size. For uniform sampling, the optimal is f = 10-4 We set Jmax = and include the extra communication costs in our results. The main results are shown Figure [3] can be seen that our optimal client sampling scheme achieves better performance than uniform sampling on this balanced dataset. The performance gains of our method over uniform sampling come from the fact that the norms of the updates from some clients larger than those from other clients even if all clients run the same nunber of local steps in each round.
32


Reviews:
[{"review_id": "B9GwMvkiJm", "reviewer": "Reviewer_k75y", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n1. The authors pointed out all the previous client sampling schemes are not compatible with stateless clients and MPC protocols. They also come up with some strategies to overcome this limitation. This part is very novel and can be interest of future researchers.\n2. The proposed client sampling strategy has convergence guarantee. The theory shows that the proposed method can have better convergence guarantee than vanilla FedAvg.\n\n**Weaknesses**\n1. The title \"optimal client sampling for federated learning\" is very controversial. I understand that the proposed sampling strategy is optimal because it minimizes the gradient variance.So we can say it is an optimal strategy to minimize the gradient variance. However, there can be a lot of different client sampling strategies for federated learning. Instead of minimizing the gradient variance, one can also propose some other strategies to minimize other metrics. It does not make sense to claim this particular method with minimal gradient variance is optimal among all client sampling strategies.\n2. In theory, the improvements from the proposed client sampling scheme seem to be marginal. Specifically, it just changes the constant factor of the non-dominant term in the error upper bound. When the number of communication rounds are sufficiently large, the proposed method should have the same convergence rate as the vanilla FedAvg.\n3. I do not think the experimental results are convincing. The theory assumes all clients have the same number of local steps. But the experiments do not. In particular, the authors let all clients perform 1 epoch of local training but clients have drastically different amount of local data. As a result, the number of local steps are different across clients. It is likely that the clients with more local steps would have larger norms of local updates. So they would get more chances to be selected by the server. The proposed sampling method just prefers those clients with more data. I guess when all clients have the same number of local steps, maybe the benefit of the proposed method can be very incremental? since all clients may have the same level of local-update norms.\n4. Although the proposed method can reduce the communication bandwidth, it still requires all available clients to communicate with the server. So the communication latency or the delay in establish communication links between server and clients are not saved. In the settings where the comm. latency is quite high, the proposed method may not be effective in reducing the real communication time.\n5. In the introduction, the authors first overview two methods of reducing communication cost in federated learning (allowing local updates and compression). Then, they suddenly jumped into contribution and said \"we propose a new approach to address the communication bandwidth issue\". This sounds like the idea of client sampling is first proposed in this paper. But it does not. It has appeared in the original FedAvg paper and a lot of subsequent client sampling papers. The idea \"careful selection of clients can lead to better communication complexity\" also appears in many previous literature, as the authors discussed in the related works section.\n6. In the experiments, this is just one specific value of $m$ for each dataset. I feel it is necessary to understand how the performance of the proposed method changes along with $m$.", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies how to reduce the communication cost in federated learning by allowing the server to communicate with only \"important\" clients. Based on this insight, the authors proposed a new client sampling strategy which can minimizes the gradient variance, and is compatible with stateless clients and MPC protocols. Convergence analysis and experimental results further validate the effectiveness of the proposed method.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "1. Change the title and related discussions in the paper. The method is optimal in reducing variance but it is not the optimal among all client sampling strategies.\n2. $R$ denotes the number of local steps in FedAvg. But $R_i$ is defined as $f_i(x^*)-f_i^*$. It would be better to change one of these notation.\n3. The experiments should be conducted in an environment where all clients perform the same number of local steps. \n4. Revise the introduction to reflect the fact that the idea of using client sampling to reduce communication is not new.\n5. More experiments on each dataset to show how the performance changes with $m$.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "6hGlPJfCbQ", "reviewer": "Reviewer_hTeJ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nAn efficient client sampling scheme with theoretically motivated has been introduced to reduce communication costs, one of the primary challenges in FL settings. \nThe convergence analysis for the proposed approach is provided with some reasonable assumptions.\nThe proposed algorithms are compatible and can be adapted to existing local update methods (DSGD, FedAvg) which keeps the nature of secure aggregation and privacy-preserving in FL.\nNumerical results show the proposed sampling scheme communication gains compared to uniform sampling approaches in a wide range of datasets.\nThe paper is well written and the concepts are explained in technical detail.\n\nWeaknesses:\n- Although experiments show that the results of the paper outperform uniform sampling, there is no comparison with existing research [1] and [2]. \n- Authors should make a comparison with existing research which are capable of adaptively finding w_i such as [3] and [4]. If we consider client selection objective function as a problem of looking for clients obtaining high impact on accuracy, [3] and [4] can point out clients who have significant contributions to the global model. Furthermore, [4] show that it not only achieves good performance in terms of accuracy but also reduces the number of communication between servers and clients. \n- Experiments show that the number of selected clients for training has an impact on the accuracy of the global model. It is expected that authors should make more experiments for illustrating the effect of m on communication and processing costs in terms of bit at the central server.\n- With non-i.i.d. data, some clients may hold data that other clients do not have. It is reasonable that clients holding a minor proportion of datasets still play an important role in the global model. Therefore, uniform sampling may have higher performance than the proposed method in this scenario.\n- I do not feel this paper made sufficient novel contributions as the sampling scheme is designed mainly based on Lemma 2.1, an extension of the existing optimal sampling scheme that has been studied extensively in other literature.\nS. Horvath and P. Richtarik, “Nonconvex variance reduced optimization with arbitrary sampling,” in International Conference on Machine Learning, 2019, pp. 2781–2789 (Lemma 1)\n- The authors only compare their proposed method with uniform sampling and full participation, and \"chose not to compare with other client sampling methods, as such comparisons would be unfair\". It's quite not convincing me as many efficient client sampling approaches for improving FL in the existing literature.\n\nLuo, B., Xiao, W., Wang, S., Huang, J., & Tassiulas, L. (2021). Tackling System and Statistical Heterogeneity for Federated Learning with Adaptive Client Sampling. ArXiv, abs/2112.11256. \nH. T. Nguyen, V. Sehwag, S. Hosseinalipour, C. G. Brinton, M. Chiang, and H. V. Poor, “Fast-convergent federated learning,” IEEE Journal on Selected Areas in Communications, vol. 39, no. 1, pp. 201–218, 2021.\nH. Yang, M. Fang, and J. Liu, “Achieving linear speedup with partial worker participation in non-iid federated learning,” arXiv preprint, arXiv:2101.11203, 2021.\nDiverse Client Selection for Federated Learning: Submodularity and Convergence Analysis, ICML2021\nPeilin Zhao and Tong Zhang. Stochastic optimization with importance sampling for regularized loss minimization. In International Conference on Machine Learning, pp. 1–9, 2015\n", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this paper, the authors propose a new statistical client sampling approach to tackle the communication bottleneck issue of Federated Learning (FL) which relies on the updates of \"more informative\" clients in each communication round. \nThe proposed “optimal” sampling strategy is formulated based on minimizing the variance of the estimated gradient over (independent sampling) clients which then can be solved by a closed-form formula using only the norms of the updates.\nTheoretical analyses and convergence guarantees are provided for the proposed strategy with the Distributed SGD and FedAvg algorithms.  \nExperimentally, the authors show that their strategy performs betters in terms of communication complexity than the uniform client sampling strategies.\n", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "- I would recommend the authors clearly state the novelty and the differences of their proposed problem formulation from other works on importance sampling. Furthermore, to make the experiment results to be more convincing, the authors should compare their work with other client sampling baselines. ", "broader_impact_concerns": "N/A. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "h8U9KPdcSv", "reviewer": "Reviewer_w6Qr", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is generally well-written, and easy to follow. The analysis of the client sampling mechanism is elegant and encourages the reader to follow along in the reduction of the problem to something tractable. While the convergence analysis requires a bit more machinery and a variety of technical constants, the authors do a good job of putting forward intuitive interpretations of their results. Finally, the experimental section is well-documented and, as best as I can tell, fully reproducible (save for the partitions of EMNIST they use, as I will discuss below).\n\nOverall, I found this paper compelling from a message standpoint. The authors clearly outline realistic, practical methods for reducing total communication costs in FL (though there is some nuance here which I discuss below) and do a great job of transitioning these goals into interesting theoretical questions. The authors clearly support most of the claims made at the beginning of the work (save for one notable exception which I detail below). There are sections which I found more interesting and compelling than others. As such, I have separated my review according to the 3 major sections of the paper (2, 3, and 5).\n\n### Section 2 - Sampling Schemes and Optimality\n\nI will preface this discussion with the fact that I think Section 2 is well-written, concise, and well-motivated. Moreover, I enjoy that while the work is primarily a theoretical analysis, the authors do a good job of trying to design algorithms with SecAgg and system practicality in mind.\n\nThe primary weakness of this portion of the work is that most of the optimality results have been derived by previous works, namely [1, 2]. While these works were not directly about FL, the idea of minimizing variance of some linear combination subject to a sparsity constraint is more general, and the exact same sampling scheme, with proofs of optimality, has been shown previously in [2]. Optimal sampling schemes for the reverse problem (minimize sparsity subject to a variance constraint) are similar, and have been derived in [1]. The observation that independent sampling schemes are optimal among all set sampling schemes is interesting and not present in those works however. It is also worth mentioning that Algorithm 2 is a minor modification of Algorithm 3 in [1]. While I really like the writing, clarity, and pertinence to FL of Section 2, I believe that its current positioning by the authors does a disservice to the paper.\n\nThat is, instead of trying to argue that the authors provide a \"novel adaptive partial participation strategy\" (section 1.2) and that they \"obtain an approximation to our optimal sampling strategy which...[fulfills] the privacy requirements of FL\" (section 1.2), I think that the core interesting observation of the paper is that sparsification schemes/algorithms previously designed in the literature have renewed (and perhaps increased) relevance in the context of FL, especially methods that are compatible with SecAgg.\n\nOne last note on Section 2 - I think it does a good job of discussing some aspects of FL (eg. why compatibility with SecAgg makes certain problems much more challenging) it makes some assumptions about realistic systems that may or may not hold in practice. In particular, the authors explicitly tackle \"total amount of communication per round\" as the metric to minimize (see Section 2.2, \"Extra Communication Costs\"). However in practice, engaging in multiple synchronous rounds of communication (as in Algorithm 2) can also be a bottleneck [3]. I do not think this is a problem that needs to be solved by the authors. Rather, I like the focus on total communication cost, and would like to see some acknowledgment that if this is not the metric you want, then you may not want to use Algorithm 2.\n\n### Section 3 - Convergence Analysis\n\nSection 3 and the convergence analysis therein is the strongest part of this work. In particular, the authors relax a number of strong assumptions that many other works make (such as a uniformly bounded dissimilarity, instead of a bounded dissimilarity on average, see Assumption 3.5). I also greatly appreciated the less technical \"Interpretation\" sections, which capture useful historical comparisons to great effect (though I would request that the authors use equations to spell out what convergence rates in other works are, just to make the comparisons easier to parse).\n\nOne slight weakness of the section is the relative opacity of the results on FedAvg. While some of the edge cases are more interpretable, the overall results involve a number of interrelated terms that make it difficult to reason about which parts dominate the convergence result. While this is to some extent unavoidable, an expanded discussion of the FedAvg convergence results could be useful here. Similarly, a brief sketch of the how the proofs go (in particular, how does the sampling scheme alter existing convergence theory of FedAvg) would go a long way.\n\n### Section 5 - Experimental Results\n\nSection 5 is thorough in many ways, and conveys to good effect the utility of the method, but stops short in a few important ways. I will preface this with saying that given the theoretical focus of the work, I do not think that the authors need to provide a comprehensive comparison of their method to many other proposed sampling schemes, especially in light of the focus on SecAgg-compatibility.\n\nThat being said, I think there are 2 notable weaknesses of this section. First, as best as I can tell the authors do not describe how they partition the FEMNIST dataset into Datasets 1, 2, and 3. While I appreciate why they do this split (in order to simulate more interesting environments for this kind of approach), they simply say that they go about \"removing some images from some clients.\" I believe that the mechanism by which this was done should be more explicit.\n\nSecond, I would have liked to see experiments with different values of $m$. In both the FEMNST and Shakespeare settings, $m$ is set to be relatively small ($m  \\in \\{2, 3\\}$) or else is set to the number of participants $n$. Understanding the transition between small and large $m$ would be useful. For example, one natural type of question is what kind of relation between $m, n$ is sufficient to obtain nearly identical results to $m = n$ (eg. constant factor, square root, logarithmic, etc.). This kind of investigation would also benefit from other values of $n$.\n\n### Review References\n\n[1] Wangni et al. \"Gradient sparsification for communication-efficient\ndistributed optimization.\" NeurIPS 2018.\n\n[2] Wang et al. \"Atomo: Communication-efficient learning via atomic sparsification.\" NeurIPS 2018.\n\n[3] Huba et al. \"PAPAYA: Practical, Private, and Scalable Federated Learning.\" MLSys 2022.", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper analyzes strategies for reducing the amount of client-to-server communication in federated learning (FL) via client sampling. This work gives a client sampling mechanism that is optimal (in terms of its variance). Since this optimal mechanism is not always compatible with the secure aggregation protocol (SecAgg), the authors also give a variant that employs iterative clipping that is compatible with SecAgg.\n\nThe authors then perform convergence analyses of Federated Averaging (FedAvg) and Distributed SGD (DSGD) when using the optimal client sampling mechanism. Finally, the authors give empirical comparisons of FedAvg on two primary tasks. Notably, these empirical comparisons show that the optimal client sampling mechanism achieves better accuracy for less communication, while maintaining accuracy comparable to that of not employing any sampling mechanism.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "## Critical Changes (Necessary for Acceptance)\n\n### Adjusting Discussion of Contributions in Section 2\n\nAs discussed above, I believe that the contributions of Section 2 must be rephrased, especially to reference past works [1, 2] above. In particular, avoiding reference to the optimal sampling mechanism being proposed in this work. While I'd like to leave the authors with some leeway here, I believe that this section needs to be reworked in a way that differentiates it from other works, either through a broader exploration of prior work on sampling and why various methods are useful/not useful for FL, or some kind of improved analysis (eg. a variance analysis of the iterative thresholding in Algorithm 2).\n\n### More Nuanced Discussion of Privacy\n\nThe authors mention that their scheme (particularly Algorithm 2) does not compromise client privacy, and that they \"fulfill the privacy requirements of FL.\" This is a bit too broad of a characterization of privacy in FL, and could benefit from more nuance. In particular, SecAgg-compatibility is only one form of privacy. Differential privacy (DP) is yet another. While I don't believe this paper needs to consider DP, the contributions of this work should be clarified to say that the authors propose algorithms that are compatible with SecAgg. In general, the privacy requirements of FL are a fluid, application-dependent thing, and in some cases SecAgg-compatibility is not enough to be considered privacy-preserving. In this vein, please consider changing the title of Section 2.2 to something like \"Ensuring Compatibility with Secure Aggregation\" to be more clear.\n\n### Improving Experimental Reproducibility\n\nI would request that the authors detail how Datasets 1, 2, and 3 were created from FEMNIST in the paper itself. While the datasets are available through a link in a README in the supplement, the method for creating these splits could be important for related types of research in the future.\n\n## Recommended Changes\n\n### Sketching Results on Partial Participation\n\nFootnote 1 is an important note to consider, as the settings where client aggregation is a bottleneck are also often settings where there is only partial participation of clients. While I am convinced that the results in the manuscript can be extended to this setting, I think it would be beneficial to have a limited sketch of this in the appendix for the interested reader. Notably, while the extension of the client sampling scheme to this setting is effectively trivial, incorporation into the actual convergence rates is slightly less trivial and deserves (in my opinion) some elucidation.\n\n### Avoiding Brevity to Improve Readability\n\nThe work could benefit from being slightly more verbose than in its current phase, especially given the lack of a page limit in TMLR. For example, the \"Interpretation\" paragraphs in Section 3 are extremely useful, and could be expanded upon to improve readability. For instance, in the paragraph after Theorem 3.6, the authors refer to specific specializations of equation 17. I believe that this would be improved by actually plugging in the specializations and referencing specific equations in past works that mirror these (eg. what theorem in Gower et al., 2019 is being referenced. Similarly, I believe that the interpretation section after Theorem 3.9 could be significantly expanded. For example, Theorem 3.8 involves somewhat complicated $\\beta_i$ terms that could be discussed at least at a high level.\n\nRelated to the above (though perhaps more specific) would be brief sketches of the proofs of theorems in Section 3. In particular, given the wide array of existing analyses of DSGD and FedAvg, trying to disambiguate why the arguments are more than simply plugging in the variance estimates from Section 2.2 to existing results would be useful.\n\nThis same issue manifests in Section 4, which could use a bit more explanation. For example, it is not immediately clear based only on this work why the sampling schemes of Cho et al., 2020 are not compatible with SecAgg. For example, one way to bias towards clients with higher losses would be to sum all the client losses (which is SecAgg compatible) send the result back to the clients, and have clients report back with probability proportional to the ratio of their loss to the total loss. Maybe a better way to approach this would be to outline the selection strategy in Cho et al., 2020 a bit more explicitly explain why it isn't SecAgg compatible.\n\n## Minor Requests\n\n* In Section 1, you mention that you study cross-device FL, and give the objective function (1). This is slightly pedantic, but that objective is relevant to both cross-device and cross-silo FL. My interpretation is that the focus on cross-device is because you are concerned with the amount of client-to-server communication. This would be useful to clarify (maybe even introducing briefly what cross-device FL is).\n*  Adding a reference to systems-level discussion of FL to back up the discussion on communication bottlenecks in Section 1.1 would be appreciated. Related to the above, it would be useful to clarify that this is generally a cross-device FL issue, not cross-silo.\n*  Please add citations related to the SecAgg protocol, and define explicitly what SecAgg compatiblity means in this context (ie. that the server can only take sums of client values) for readers who may not know.\n*  There is a missing close parenthesis in equation 16.\n*  The authors have a few instances (eg. on page 10) where footnotes are appended to numbers, making it look like an exponent. If possible consider slightly changing these for readability.\n*  The citation formatting is slightly inconsistent (eg. whether or not to capitalize all words in a conference title). Please standardize them.\n*  At least one of the papers being cited (QSGD) exists in published form, but the arXiv version is cited. Please cite the published form when possible.\n*  Since federated learning is a concept (like machine learning) it should not be capitalized unless in a title.\n*  There is a reference to (unchanged) before the Shakespeare dataset (Section 5.1.2). Is this simply a reference to the fact that you do not change the number of examples held by clients? This might be useful to clarify.", "broader_impact_concerns": "I have no concerns in this regard.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Based on the reviews, the author response/revision, the subsequent discussion and the reviewers' recommendations, my decision recommendation for this paper is **Accept with minor revision**.

The rationale behind this decision is that it that the only point that remains unaddressed in the revised version is the lack of experiments where all clients perform the same number of local updates. While the paper would be stronger with this additional experiment, I do not think this warrants rejection because, even if the proposed approach turns out to be less effective in this setup, the contribution remains valuable as per TMLR's criteria.

For the paper to be accepted, **the authors must add the experiment promised in their response to reviewer k75y**:
> We will run experiments with a balanced (each client has the same amount of data) CIFAR100 dataset and also analyze the norm of the updates to provide better evidence for the practical performance of our method.
Decision: Accept (poster)