On the Impact of Client Sampling on Federated Learning Convergence
Authors: Yann Fraboni
Richard Vidal
Laetitia Kameni
Marco Lorenzi
Venue: ICLR 2022 Submitted (2022)
Keywords: Federated learning
client sampling
bias
convergence rate
distributed optimization
data heterogeneity

Abstract: While clients' sampling is a central operation of current state-of-the-art federated learning (FL) approaches, the impact of this procedure on the convergence and speed of FL remains under-investigated.In this work we introduce a novel decomposition theorem for the convergence of FL, allowing to clearly quantify the impact of client sampling on the global model update. Contrarily to previous convergence analyses, our theorem provides the exact decomposition of a given convergence step, thus enabling accurate considerations about the role of client sampling and heterogeneity. First, we provide a theoretical ground for previously reported experimental results on the relationship between FL convergence and the variance of the aggregation weights. Second, we prove for the first time that the quality of FL convergence is also impacted by the resulting \emph{covariance} between aggregation weights. Our theory is general, and is here applied to Multinomial Distribution (MD) and Uniform sampling, the two default client sampling schemes of FL, and demonstrated through a series of experiments in non-iid and unbalanced scenarios. Our results suggest that MD sampling should be used as default sampling scheme, due to the resilience to the changes in data ratio during the learning process, while Uniform sampling is superior only in the special case when clients have the same amount of data.

Under review as a conference paper at ICLR 2022
ON THE IMPACT OF CLIENT SAMPLING ON FEDER- ATED LEARNING CONVERGENCE
Anonymous authors
Paper under double-blind review
ABSTRACT
While clients' sampling is a central operation of current state-of-the-art feder- ated learning (FL) approaches, the impact of this procedure on the convergence and speed FL remains under-investigated In this work we introduce a novel decomposition theorem for the convergence of FL. allowing to clearly quantify the impact of client sampling on the global model update. Contrarily to previ- ous convergence analyses, our theorem provides the exact decomposition of a given convergence step, thus enabling accurate considerations about the role of client sampling and heterogencity. First, we provide a theoretical ground for pre- viously reported experimental results on the relationship between FL convergence and the variance of the aggregation weights. Second, that the quality of FL convergence is also impacted by the resulting covariance between aggregation weights. Our theory is general, and is here applied Multi- nomial Distribution (MD) and Uniform sampling, the two default client sampling schemes of FL, and demonstrated through series of experiments in non-iid and unbalanced scenarios. Our results suggest that MD sampling should be used as default sampling scheme, due to the resilience to the changes in data ratio during the learning process, while Uniform sampling is superior only in the special case when clients have the same amount of data.
prove for the first time
INTRODUCTION
Federated Learning (FL) has gained popularity in the last years as it enables different clients to jointly learn global model without sharing their respective data. Among the different FL ap- proaches, federated averaging (FedAvg) has emerged as the most popular optimization scheme (McMahan et al. 2017). An optimization round of FedAvg requires data owners, also called clients, to receive from the server the current global model which they update on a fixed amount of Stochas- tic Gradient Descent (SGD) steps before sending it back to the server. The new global model is then created as the weighted average the client updates, according to their data ratio.
FedAvg was first proven to converge experimentally (McMahan et al., 2017), before theoretical guarantees were provided for any non-iid federated dataset (Wang ct al. 2020aa Karimireddy et al. 2020 Haddadpour & Mahdavi 2019 Khaled et al. 2020). A drawback of naive implementations of FedAvg consists in requiring the participation of all the clients at every optimization round. As consequence, the efficiency of the optimization is limited by the communication speed of the slowest client, as well as by the server communication capabilities. To mitigate this issue, the original FedAvg algorithm already contemplated the possibility of considering random subset of m clients at each FL round. It has been subsequently shown that, to ensure the convergence of FL its optimum, clients must be sampled such that in expectation the resulting global model is identical to the one obtained when considering all the clients (Wang et al.] 2020a; Cho et al.) 2020). Clients sampling schemes compliant with this requirement are thus called unbiased. Due to its simplicity and flexibility, the current default unbiased sampling scheme consists in sampling m clients according to a Multinomial Distribution (MD), where the sampling probability depends
on the respective data ratio (Li et al.) 2020a; Wang et al.) 2020a Li et al. 2020c Haddadpour & ..Madaai 2019 Li et al., 2020bb Wang & Joshi 2018: 8 Fraboni et al. (202)) Nevertheless, when clients have identical amount of data, clients can also be sampled uniformly without replacement (Li jct al. 2020c. Karimireddy et al. 2020; Reddi et al. 2021 Rizk et al. 2020). In this case, Uniform sampling has been experimentally shown to yield better results than MD sampling (Li et al. 2020c).

---

Under review as a conference paper at ICLR 2022
In spite of the practical usage of sampling in FL, the impact of different unbiased client sampling schemes on the convergence and speed of FL remains to date under- ingestrrnvett...dd.. In (Fraboni et al, extended account for collections of sampling distributions with vary- ing client sampling probability, to define clustered sampling. From a theoretical perspective, this approach was proven to have identical convergence guarantees of MD sampling, with albeit experi- mental improvement justified by lower variance of the clients' aggregation weights. Another study investigated the convergence guarantees of FedAvg under different sampling schemes, through penalized optimization framework (Li et al. 2020c). These studies reflect the ongoing interest and need for theoretical framework elucidate the impact of client sampling on FL convergence.
202I), MD sampling
The main contribution of this work consists in deriving decomposition theorem for the convergence of FI., allowing to clearly quantify the impact of client sampling on the global model update at any FL. round. This contribution has important theoretical and practical implications. First, we demonstrate the dependence of FL. convergence on the variance of the aggregation weights. Second, prove for the first time that the convergence speed is also impacted through sampling by the resulting covariance between aggregation weights. Contrarily to the convergence bound illustrated in (Li et al. 2020c), our theorem provides the exact decomposition of given convergence step, thus enabling accurate quantification of the role of client sampling and heterogeneity in FL. From practical point of view, we establish both theoretically and experimentally that client sampling schemes based on aggregation weights with sum different than are less efficient. We also prove that MD sampling outperformed by Uniform sampling only when clients have identical data ratio. Finally, we show that the comparison between different client sampling schemes is appropriate only when considering a small number of clients. Our theory ultimately shows that MD sampling should be used as default sampling scheme, due to the favorable statistical properties and to the resilience to FL applications with varying data ratio and heterogeneity.
Our work is structured as follows. In Section we provide formal definitions for FL, unbiased client sampling, and for the server aggregation scheme. In Section 3 we introduce our decomposition theorem (Theorem [T relating the convergence of FL. to the aggregation weight variance of the client sampling scheme. Consistently with our theory, in Section 4 we experimentally demonstrate the importance of the clients aggregation weights variance and covariance the convergence speed, and conclude by recommending Uniform sampling for FL applications with identical client ratio, and MD sampling otherwise.
BACKGROUND
Before investigating Section 3 the impact of client sampling on FL convergence, we recapitulate in Section 2 the current theory behind FL aggregation schemes for clients local updates. We then introduce a Tormalization for unbiased client sampling.
2.1 AGGREGATING CLIENTS LOCAL UPDATES
In FL., we consider a set 1 of n clients each respectively owning a dataset Dj composed of n; samples. FL aims optimizing the average of each clients local loss function weighted by ps such that >1 = 1, i.e.
((0) = Σ (C).
(1)
where 0 represents the model parameters. The weight p: can be interpreted as the importance given by the server to client in the federated optimization problem. While any combination of {p:} is possible, note that in practice, either (a) every device has equal importance, i.e. pa 1/n,, (b) every data point is equally important, i.c. p: = n//M with M = Σ n.. Unless stated otherwise, in the rest of this work, we consider be in case (b), i.e. 3i, pi 1/n.
In this setting, to estimate a global model across clients, FedAvg (McMahan et al. 2017) is an iterative training strategy based on the aggregation of local model parameters. At each iteration step f, the server sends the current global model parameters Ht to the clients. Each client updates the respective model by minimizing the local cost function ()) through fixed amount K of SGD steps initialized with 0t. Subsequently each client returns the updated local parameters of+1 to the
2

---

Under review as a conference paper at ICLR 2022
server. The global model parameters G at the iteration step + are then estimated weighted average:
g
D.
(2)
To alleviate the clients workload and reduce the amount of overall communications, the server often considers m S n clients at every iteration. In heterogeneous datasets containing many workers, the percentage of sampled clients m/n can be small, and thus induce important variability in the new global model, as each FL optimization step necessarily leads to an improvement on the m sampled clients to the detriment of the non-sampled ones. To solve this issue, |Reddi et al.) (2021); Karimireddy et al. (2020); Wang et al. (2020b) propose considering an additional learning rate better account for the clients update aggregation weight of client given the subset of sampled clients St at iteration t. The server aggregation scheme can be written as:
given iteration. We denote by (r,(S) the stochastic
gt+1 o² + 7
wi (i - -²).
(3)
2.2 UNBIASED CLIENTS SAMPLING
While FedAvg originally based the uniform sampling of clients (MeMahan et al.
2017). this
scheme has been proven to be biased and converge to a suboptimal minima of problem (I) (Wang
al. 2020al, Cho al., 2020 Li et al., 2020c). This was the motivation for [i al. (2020c) to introduce the notion of umbiasedness, where clients are considered in expectation subject to their importance Pi. according to Definition below. Unbiased sampling guarantees the optimization of the original FL cost function, while minimizing the number of active clients per FL round. We note that unbiased sampling is not necessarily related to the clients distribution, as this would require to know beforehand the specificity of the clients' datasets.
Unbiased sampling methods (Li et al. 2020a Fraboni et al. 2021) are currently among the stan- dard approaches to FL, opposed to biased approaches, known to over- under-represent clients and lead to suboptimal convergence properties (McMahan et al.) 2017 Nishio Yonetani 2019; Jeon et al.) 2020, Cho al. 2020), to methods requiring additional computation work from clients (Chen et al. 2020a).
Definition (Unbiased Sampling). A client sampling scheme is said unbiased if the expected value of the client aggregation equal to the global deterministic aggregation obtained when considering all the clients, i.e.
a
ESS
Σ
we (s.))
= Σ P.O
where w;(S:) is the aggregation weight of client j for subset of clients Sz-
The sampling distribution uniquely defines the statistical properties of stochastic weights. In this setting, unbiased sampling guarantees the equivalence between deterministic and stochastic weights in expectation. Unbiased schemes of primary importance in FL are MD and Uniform sampling, for which we can derive a close form formula for the aggregation weights:
MD sampling. This scheme considers 41,..,4 to be the m iid sampled clients from Multinomial Distribution with support on (I..... m7) satisfying P(le = i) = p; (Wang et al., 2020a Li et al.
2020a c (Haddadpour & Mahdavi 2019 Li et al. 2020b Wang & Joshi (2018)
al. 2021
By definition, we have >x P: 1, and the clients aggregation weights take the form:
(x m
1(4 i).
(5)
Uniform sampling. This scheme samples m clients uniformly without replacement. Since in this case a client is sampled with probability p(li E S.)) m/n, the requirement of Definition implies:
w.(S)) = I(i E St) n P
(6)
m
3

---

Under review as a conference paper at ICLR 2022
Table 1: Synthesis of statistical properties of different sampling schemes. 12 1== Wi (St))
Sampling
Var [wt)
Var
Full participation
=
=
MD
m! P
+
1/m
Uniform
m 1) Pi m(n-1)
Ei=1 P m(n-1]
a-m
We note that this formulation for Uniform sampling is generalization of the scheme previously used for FL applications with identical client importance, i.c. P: = 1/nn (Karimireddy et al. 2020
Li al. 2020c. Reddi et al. 2021, Rizk et al. 2020). We note that Var >- (v 0 and
only if p; 1/n for all the clients as, indeed, Σ (St) m m
With reference to equation (3), we note that by setting 72 = 1. and by imposing the condition VS,, Σi= (.,) 1, we retrieve equation (2). This condition satisfied for example by MD sampling and Uniform sampling for identical clients importance.
We finally note that the covariance of the aggregation weights for both MD and Uniform sam- pling is such that there exists an such that Vi * j. Cov (4 = -aP:Pj- We provide in Table [ the derivation of a and the resulting covariance for these two schemes with calculus details in Appendix A Furthermore, this property is common to variety of sampling schemes, for example based on Binomial or Poisson Binomial distributions (detailed derivations can be found in Appendix AA.. Following this consideration, in addition to Definition [ in the rest of this work we assume the additional requirement for a client sampling scheme to satisfy Fo: 0, vi # j, Cov w. OP:P.-
3 CONVERGENCE GUARANTEES
Based the assumptions introduced in Section in what follows we elaborate theory relating the convergence of FI. to the statistical properties of client sampling schemes. In particular, Decom- position Theorem describes the impact of client sampling on a single optimization step, while Theorem quantifies the asymptotic relationship between client sampling and FL convergence.
3.1 DECOMPOSITION THEOREM
Assumption (Unbiased Gradient and Bounded Variance). Every client stochastic gradient () of a model x evaluated on batch B is an unbiased estimator of the local gradient. We thus have En [E:(B)] = 0 and 0 S EB [II:(B)]1²] S o², with C:(B) = ()( VL.(w).
the following Decomposition Theorem highlights the impact of client sampling on single FL op- timization step. For any optimization round, it provides an explicit link between the statistical properties of the sampling scheme (variance and covariance) and the expected distance between the global model and the related optimum.
Theorem (Decomposition Theorem). We consider yi,x the local model of client after k SGD steps initialized on model 0'. We consider the vector E of the gradient noises $ = [gs (9 (L,(y))) satisfying Assumption i and A = -K-1 (.. We consider a client sampling scheme satisfying Definition and such that Cov (wr(S)) w, (S,) -ap:Pj. For any given opti- mization round based equation (3), the following equation holds:
E, 0
0-1
||0¹ 0-
2ng
ps E, 1
80)
0 - 0²) +1) (7)
Direction drift
4

---

Under review as a conference paper at ICLR 2022
with
n Q(0')
Σ 1=1
V
E ||:
74 E.
-(1 a) Be
Σ Pe
(8)
i=1
Gradient Estimator Noise =N.
Local Model Drift
=Li
Globol Model Drift
=G((p.),0"
where 0" is the optimum of the optimization problem 1. 14== = [Var [sx) + 7 =
Var [S,) + api, and E, [X] is the expected value of X conditioned on 0".
The Decomposition Theorem (proof in Appendix B) shows that FL convergence is impacted by a client sampling through the quantities Var (St) and a, which both depend on the clients aggre- gation weights. These variables modulate three quantities, (0*),, (,")") and G([p,). 0*), rep- resenting respectively the stochastic gradient estimator noise, and the local and globul model drift from the current initialization, which are independent from client sampling. In particular, the quality of clients data impacts the convergence speed through (0*). The Decomposition Theorem also provides a necessary condition for an optimization step to improve the current global model: the ex- pected client contribution E2 E>= P; [0++] 0']] needs be collinear with the global direction of the optimum 0* -"- 0
To further clarify the influence of client sampling on the FL convergence we introduce the follow- ing property (proof in Appendix [A.1] introducing the quantity Var [> (;.)). the variance of the sum of the aggregation weights, and showing its relationship with the variance of the clients aggregation weights Var (S,),, and with the covariance parameter a.
Property 1. For any client sampling, we have 0 S a S 1 and
Var Σ (i(()))
Var [w)( - -
Since S the global model drift G(fp:), 0³) contributes positively equation 8). and the term Q(0") is always positive. This means that Q()") is not negligible, and an appropriate sampling scheme should be defined such that Q(0') minimized. We note that the impact of client sampling can always be mitigated by considering a smaller local learning rate Indeed, the client drift is proportional y while ((0") is proportional n/-
3.2
ASYMPTOTIC CONVERGENCE WITH RESPECT TO CLIENT SAMPLING
To prove FL convergence with client sampling, work relies the following two assumptions [Wang et al. 2020a Li et al. 2020a Karimireddy et al. 2020 Haddadpour & Mahdavi 2019 Wang
et al.
2019a b):
Assumption 2 (Smoothness). The clients local objective function is L-Lipschitz smooth, that is, Vi E (1,...,, n), [+) VL,(u)] L || yll-
Assumption (Bounded Dissimilarity ). There exist constants 332 2 and n² 2 0 such that for ev- ery combination of positive weights {w;} such that Di w; = 1, we have Σx [V < 8² [V((=) x². all the local loss functions are identical. then have 32 1 and k² 0.
We formalize the following theorem the relationship between the statistical propertics of the client sampling scheme and the asymptotic convergence of FL (proof in Appendix C
Theorem (FL convergence). Let us consider a client sampling scheme satisfying Definition 7 Nand such that for i # j, Cov (w:(S)), w (S.)) -oppp < O. Under Assumptions 7 to and with sufficiently small local step size m, the following convergence bound holds:
+ T-1
-I [|
so
1
+0
+
NORKT
+0
Σ
D
02
+ +0
(11777 [[K
1)o² + Kn&l), (10)
i=1
5

---

Under review as a conference paper at ICLR 2022
where K is the number of local SGD, and
Σ= Var [S)( and y
Var (ws + a Σ p
(11)
We first observe that any client sampling scheme satistying the assumptions of Theorem _ converges to its optimum. Through Σ and 7 equation (IO) shows that our bound is proportional to the clients aggregation weights through the quantities Var [w){S: and a, which thus should be minimized. These terms are non-negative and are minimized and equal to zero only with full participation of the clients to every optimization round. Theorem does not require the sum of the weights (St) to be equal to 1. Yet, for client sampling satisfying Var [Σi=] (S.)) = O, we get x Σ. Hence, choos- ing an optimal client sampling scheme amounts at choosing the client sampling with the smallest Σ. This aspect has been already suggested in Fraboni et al. (2021).
The convergence guarantee proposed in Theorem extends the work of Wang et al. (2020a) where, in addition of considering FedAvg with clients performing K vanilla SGD, we include server learning rate 77 and integrate client sampling (equation ( With full client participation (Σ = y = 0) and 1/g 1, retrieve the convergence guarantees of Waan et al.] (2020a). Furthermore, our theoretical framework can be applied to any client sampling satistying the conditions of Theorem 2 In turn, Theorem 2 holds for full client participation, MD sampling. Uniform sampling, well as for the other client sampling schemes detailed in Appendix [A] Finally, the proof of Theorem
2 is general enough account for FL regularization methods (Li al.) [020aa] 2019] AAar et al.)
2021]. other SGD solvers (Kingma & Ba 2015) Ward et al. 2019; Li & Orabona (2019), and/or gradient compressionqquantzziio (Reisizadeh et al., 2020 [Basu et al., [2099] Wang et al.) [0018). For all these applications, the conclusions drawn for client samplings satisfying the assumptions of
Theorem still hold.
3.3 APPLICATION TO CURRENT CLIENT SAMPLING SCIEEME
MD sampling. When using Table
! to compute E and y close-form we obtain:
1
n2
1
EMD
1
Σ
p and TMD
(12)
m
m
where we notice that EMD 1 = "MDD- Therefore, one obtain looser convergence guarantees than the ones of Theorem 2 independently from the amount of participating clients n and set of clients importance }p while being inversely proportional to the amount of sampled clients The resulting bound shows that FL with MD sampling converges to its optimum for any FL. application.
Uniform sampling. Contrarily MD sampling, the stochastic aggregation weights of Uniform sampling do not sum to 1. As a result, we can provide FL scenarios diverging when coupled with Uniform sampling. Indeed, using Table compute > and y close-form we obtain
1
Σ
pt and Tu
1 n
Σ
P
(13)
m
m
1 - Ey. Considering that Σi= P2 < 1, we have Ey S 1, which goes to infinity for large cohorts of clients and thus prevents FL with Uniform sampling to converge to its optimum. Indeed, the condition Σ Pf accounts for every possible scenario of client importance {pt). including the very heterogeneous ones. In the special case where ps = 1/n, we have Σ Pf = 1/n, such that Eg is inversely proportional both and m. Such FL applications converge to the optimum of equation (I) for any configuration of n, {p.} and m.
where we notice that 70
Moreover, the comparison between the quantities 2 and 7 for MD and Uniform sampling shows that Uniform sampling outperforms MD sampling when p: = 1 1/n. More generally, Corollary proovdes sufficient conditions with Theorem 2 for Uniform sampling to have better convergence guarantees than MD sampling (proof in Appendix C.7..
Corollary 1. Uniform sampling has better convergence guarantees than MD sampling when Ey S EDD. and yu I D which is equivalent to
Σ
<
(14)
n
m

---

Under review as a conference paper at ICLR 2022
Corollary I can be related to Var |-x=1 (s))),,, the variance for the sum of the aggregation weights, which is always null for MD sampling, and different of 0 for Uniform sampling except when p. = 1/n for all the clients.
A last point of interest for the comparison between MD and Uniform sampling concerns the re- spective time complexity for selecting clients. Sampling with Multinomial Distribution has time complexity On m log(n)), where (n) comes from building the probability density function to sample clients indices (Tang 2019). This makes MD sampling difficult to compute even in- tractable for large cohorts of clients. On the contrary sampling m elements without replacement from states reservoir sampling problem and takes time complexity (mm(1 + log(n/m))JLL 1994). In practice, clients either receive identical importance (p: 1/n) or an importance pro- portional to their data ratio, for which we may assume computation p. = ( As a result, for important amount of participating clients, Uniform sampling should be used as the default client sampling due to its lower time complexity. However, for small amount of clients and heterogeneous client importance, MD sampling should be used by default.
Due to space constraints, we only consider in this manuscript applying Theorem 2 to Uniform and MD sampling, which can also be applied to Binomial and Poisson Binomial sampling introduced in Section A] and satisfying our covariance assumption. To the best of our knowledge, we could only find clustered sampling introduced in Fraboni et al. (202I) not satisfying this assumption. Still, with minor changes, we provide for this sampling scheme a similar bound to the one of Theorem 2 (Appendix C.6), ultimately proving that clustered sampling improves MD) sampling.
EXPERIMENTS
In this section provide experimental demonstration of the two main theorems of Section 3. by quantifying the correctness of Decomposition Theorem I and by verifying the convergence properties identified in Theorem
4.1 SYNTHETIC EXPERIMENT
We consider a synthetic FL experiment where the clients models are defined by quadratic local loss functions. This choice enables closed-form computation of the global optimum, as well as of the expectation of the distance between global model and optimum during single FL optimization step.
We consider n = 10 clients jointly learning a model with m = of them sampled by the server at each optimization step. Each client local loss function is (. = 010 - 0; with optimum OF N (02, Ia), where d = 20 is the number of parameters in the model. The optimum of the global loss function of equation (1) is 0 Σ P.O.. : We consider varying pr, the importance of client 1, while giving identical importance to the remaining clients, i.e.
P1 = r and p; = (1 - r) 1), 11
(15)
By varying between and 1, we investigate scenarios with different level of heterogeneity for the clients importance. We perform full gradient descents, which makes client sampling the only source of randomness during optimization. Lastly, we only consider single FL optimization step initial- ized with global model 0 ~ (O,,, Ia). We compare the average distance of 1000 simulations obtained after a single FL round to the theoretical one provided by the Decomposition Theorem (see Appendix D for the closed form equation derived for the controlled example here proposed). The scenario above is tested in two different experimental settings: an iid one, where 0 07. and non-iid one, where every client local model is drawn independently.
The theoretical expected distance ||00 - |- plotted for iid and non-iid case in Figure and The corresponding experimental distance resulting from the 1000 simulations is shown in Figure and [d. We note that there is a close match between theoretical and experimental results, demon- strating the validity of Decomposition Theorem Figure highhights the following properties:
lid case (Figure Th and [e). In the iid setting the expected difference obtained with MD sampling is equivalent to the obtained when all the clients are considered (Full). This demonstrates that in the iid case the covariance parameter a does not affect FL convergence (Section 33. Moreover, Uniform sampling leads to generally poor convergence results, thus confirming that the variance of

---

Under review as a conference paper at ICLR 2022
(a)
(b)
(c)
(d)
4.0
4.0
4.0
4.0
Full
3.5
3.5
3.5
3.5
Uniform
3.0
3.0
3.0
2.5
2.5
2.5
2.5
2.0
2.0
2.0
1.5
2.0
1.5
1.5
1.0
1.5
1.0
0.0
0.5
0.0
0.5
0.0
0.5
0.0
0.5
P1
Pi
P1
Figure 1: Illustration of the Decomposition Theorem T for the synthetic scenario described in Section
4.1 for 10 clients when sampling m 5 of them. Panels (a) and (b) show the theoretical
distances between global model and FL optimum obtained with the Decomposition Theorem | in respectively iid and non-iid settings. Panels (c) and (d) show the distances estimated experimentally when averaging over 1000 simulations for iid and non-iid settings. We consider fl = 1, = 0.1, and 10.
the sum of the clients stochastic weights, Vars, (E (s.)), negatively impacts FL convergence. More precisely, the only case where Uniform sampling comparable the other schemes when P1 = 0.1, which indeed corresponds to the special scenario in which p. 1/n, and thus the variance associated to Uniform sampling is zero (cfr. Table
Non iid case (Figure Dp and Dt). The conclusions drawn for the iid case still hold when the lo- cal optima are not identical across clients. Moreover, we can now appreciate the impact of the covariance parameter
the convergence speed. Independently from the choice for P1. the min- imum distance obtained when considering all the clients. In this case we have both a = 0 and Vars, E (S.) 0. When p; 1/n 0.1, both MD and Uniform sampling have null vari- ance Vars, (E Wi (S:)]. In this case, the negative impact of the covariance through the parameter a penalizes MD sampling. The penalization of the covariance term on MD sampling is still relevant when p1 is close the critical value of 0.1. Finally, for large enough values of p1. the variance term outweights the effect the covariance, making MD better than Uniform sampling.
Diverging Uniform sampling. Consistently with Figure L in Appendix E we provide further amples showing that Uniform sampling can diverge in simple FL. setting with heterogeneous client importance. We still consider
of them with p1 sampled, clients perform K = 1 SGD to show that the divergence does not come from the clients local work K. Figure appendix([]shov that for this scenario, FL with MD sampling converges while FL with Uniform sampling diverges both for iid and non-iid client data distribution.
10 clients and sample
0.9. When
4.2 EXPERIMENT ON REAL DATA
We study LSTM model for next character prediction on the dataset of The complete Works of William Shakespeare (McMahan et al.) 2017: Caldas al.) 2018). We use two-layer LSTM classifier containing 100 hidden units with an 8 dimensional embedding layer. The model takes as an input a sequence of 80 characters, embeds each of the characters into learned 8-dimensional space and outputs one character per training sample after 2 LSTM layers and fully connected one.
When selected, a client performs K 50 SGD steps on batches of size B 64 with local learning rate
1.5. The server considers the clients local work with 7/2 1. We consider n [10, 20, 40, 80} clients, and sample half of them each FI. optimization step. While for sake of interpretability do not apply decay to local and global learning rates, note that theory remains unchanged even in presence heterogeneity, considering fy can speed-up FL with more stable convergence.
learning rate decay. In practice, for dataset with important
Clients have identical importance [p. = 1/n1. We note that Uniform sampling consistently out- performs MD sampling due to the lower covariance parameter, while the improvement between the resulting convergence speed is inversely proportional to the number of participating clients n (Figure 21). This result confirms the derivations of Section
8

---

Under review as a conference paper at ICLR 2022
(a) pi 1/v
(b) P AMM
0.15
0.10
-0.1
0.05
-02-
0.00
100
200
500
200
rounds
roundss
10 2. 40
Figure 2: Difference between the convergence of the global losses resulting from MD and Uniform sampling when considering E {10, 20, 40, 80} clients and sampling m = n/22 of them. In (a), clients have identical importance, i.e. Ps 1/n. (b), clients importance is proportional amount of data, i.e. p; n,/M. Differences in global losses are averaged across 30 FL experiments with different model initialization (global losses are provided in Appendix Eb.
their
Clients importance depends on the respective data ratio [p. n4/M]. In this experimental scenario the aggregation weights for Uniform sampling not always sum to thus leading to the slow-down of FL. convergence. Hence, we see in Figure 2p that MD always outperforms Uniform sampling. This experiment shows that the impact on FL convergence of the variance the sum of the stochastic aggregation weights is more relevant than the one due to the covariance parameter a. We also note that the slow-down induced by the variance is reduced when more clients do participate. This is explained by the fact that the standard deviation of the clients data ratio is reduced with larger clients participation, c.g. p. = 1/10 + 0.13 for n = 10 and p; = 1/80 = 0.017 for n = 80. We thus conclude that the difference between the effects of MD and Uniform sampling is mitigated with large number of participating clients (Figure
Additional experiments Shakespeare provided in Appendix [ We show the influence of the amount of sampled clients m (Figurel6) and amount of local work K (Figure 8 on the convergence speed of MD and Uniform sampling.
Finally, additional experiments on CIFAR1O (Krizhevsky) 2009) are provided in Appendix F| where replicate the experimental scenario previously proposed in Fraboni al. (2021). In these appli- cations, 100 clients are partitioned using a Dirichlet distribution which provides federated scenarios with different level of heterogeneity. For all the experimental scenarios considered, both results and conclusions are in agreement with those here derived for the Shakespeare dataset.
CONCLUSION
In this work, we derive novel Decomposition Theorem demonstrating the impact FL. vergence speed of any unbiased client sampling scheme following the assumptions of Section [ Moreover, Theorem highlights the asymptotic impact of client sampling on FL, and shows that the convergence speed is inversely proportional to both the sum of the variance of the stochastic aggregation weights, and to their covariance parameter a. To the best of knowledge, this work is the first one accounting for schemes where the sum of the weights is different from 1.
Thanks to our theory. we investigated MD and Uniform sampling from both theoretical and exper- imental standpoints. We established that when clients have approximately identical importance, i.c p: 1/n, Uniform outperforms MD sampling, due to the larger impact of the covariance term for the latter scheme. On the contrary, Uniform sampling is outperformed by MD sampling in more gen- eral cases, due to the slowdown induced by its stochastic aggregation weights not always summing to 1. Yet, in practical scenario with very large number of clients, MD sampling may be unpractical, and Uniform sampling could preferred due to the more advantageous time complexity. Finally, while the contribution of this work is in the study of the impact of clients sampling the global op- timization objective, further extensions may focus on the analysis the impact clients selection method individual users' performance, especially in presence of heterogeneity.

---

Under review as a conference paper at ICLR 2022
ETHICS STATEMENT
We read and acknowledged the ICLR Code of Ethics.
The experimental correctness of our method was evaluated on publicly available datasets. Datasets were properly referenced and their construction can be found in the associated references.
This work investigates client sampling, FL component already introduced in previous literature. Our work does not change the FL framework and thus does not propose additional client exposure.
There is no conflict of interest. The arguments used in this work are either theoretically proven, experimentally illustrated, or coming from peer-reviewed work.
Our method is centered around unbiased client sampling and thus does not induce bias in the global model.
REPRODUCIBILITY STATEMENT
Every proposed theoretical result carefully analyzed in Section 3 and proven in Appendix. Aggre-
gation weight calculus can be found in Appendix A Theorem can be found in Appendix B and Theorem can be found in Appendix
The settings of the different experiments are specified in the paper and the code is provided. Fur- thermore, we use public datasets without any preprocessing.
REFERENCES
Durmus Alp Emre Acar, Yue Zhao, Ramon Matas, Matthew Mattina, Paul Whatmough, and Venkatesh Saligrama. Federated learning based on dynamic regularization. In International Con-
ference Learning Representations, 2021.
Debraj Basu, Deepesh Data, Can Karakus, and Suhas Diggavi. Qsparse-local-sgd: Distributed sgd with quantization, sparsification and local computations. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché- Buch,,Bu E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
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. (NeurIPS):1-9,22) 2018.
Wenlin Chen, Samuel Horvath, and Peter Richtarik. Optimal Client Sampling for Federated Learn- ing. Workshop NeurlPS: Privacy Preserving Machine Learning, 2020a.
Wenlin Chen, Samuel Horvath, and Peter Richtarik. Optimal client sampling for federated learning. 2020b.
Yae Jee Cho, Jianyu Wang, and Gauri Joshi. Client selection federated learning: Convergence analysis and power-of-choice selection strategies, 2020.
Yann Fraboni, Richard Vidal, Laetitia Kameni, and Marco Lorenzi. Clustered sampling: Low- variance and improved representativity for clients selection in federated learning. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 3407-3416. PMLR, 18-24 Jul 2021.
Farzin Haddadpour and Mehrdad Mahdavi. On the convergence of local descent methods in feder- ated learning, 2019.
Tzu Ming Harry Hsu, Hang Qi, and Matthew Brown. Measuring the effects of non-identical data distribution for federated visual classification. arXiv, 2019.
Joohyung Jeon, Soohyun Park, Minseok Choi, Joongheon Kim, Young- BBn Kwon, and Sungrae Cho. Optimal user selection for bigf-performance and stabilized energy-efficient federated learning platforms. Electronics, 99),, 2020. ISSN 2079-9292. doi: 10.3990lelectronics9991133
10

---

Under review as a conference paper at ICLR 2022
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. SCAFFOLD: Stochastic controlled averaging for federated learning. In Hal Daumé III and Aarti Singh (eds.). Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 5132-5143.
PMLR, 13-18 Jul 2020.
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtarik. Tighter theory for local sgd iden- tical and heterogeneous data. In Silvia Chiappa and Roberto Calandra (eds.), Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statisticx, volume 108 of Proceedings of Machine Learning Research, pp. 4519-4529. PMLR, 26-28 Aug 2020.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR (Poster), 2015.
Alex Krizhevsky. Learning multiple layers of features from tiny images. 2009.
Kim-Hung Li. Reservoir-sampling algorithms of time complexity o(n(1 + log(n/n))). ACM Trans. Math. Softwe, 20(4))481-44) 1-493, December 1994. ISSN 0098-3500. doi: 10. 1 145/1984299 198435.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smithy. Feddane: A federated newton-type method. In 2019 53rd Asilomar Conference on Signals, Sys- lems, and Computers, pp. 1227-1231, 2019.
doi: 10.1 109/EEEECOTT44444009999999990
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. In I. Dhillon, D. Papailiopoulos, and V. Sze (eds.), Proceedings of Machine Learning and Systems, volume 2, pp. 429-450, 2020a.
Tian Li, Maziar Sanjabi, Ahmad Beirami, and Virginia Smith. Fair resource allocation in federated learning. In International Conference on Learning Representations, 2020b.
Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data. In International Conference on Learning Representations, 2020c.
Xiaoyu Li and Francesco Orabona. On the convergence of stochastic gradient descent with adaptive stepsizes. In Kamalika Chaudhuri and Masashi Sugiyama (eds.). Proceedings of the Twenty- Second International Conference on Artificial Intelligence and Statistics, volume 89 of Proceed- ings of Machine Learning Research, pp. 983 993.992.222 PMLR, 16-18 Apr 2019.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-Eiin Efficiint Learning of Deep Networks from Decentralized Data. In Aarti Singh and Jerry Zhu (eds.), Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Leurning Research, pp. 1273-1282, PMLR, 20-22 Apr 2017.
Takayuki Nishio and Ryo Yonetani. Client selection for federated learning with heterogeneous resources in mobile edge. In ICC 2019 2019 ICEE International Conference Communications (ICC), pp. 1-7, 2019. doi: 10. 00.10999C.22119.76111155
Sashank J. Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and Hugh Brendan McMahan. Adaptive federated optimization. In International Conference on Learning Representations, 2021.
Amirhossein Reisizadeh, Aryan Mokhtari, Hamed Hassani, Ali Jadbabaie, and Ramtin Pedarsani. Fedpaq: A communication-cfficicee federated learning method with periodic averaging and quan- tization. In Silvia Chiappa and Roberto Calandra (eds.), Proceedings of the Twenty Third Interna- tional Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pp. 2021-2031 10011 PMLR, 26-28 Aug 2020.
Elsa Rizk, Stefan Vlaski, and Ali H. Sayed. Dynamic federated learning. In 2020 IEEE 21st International Workshop on Signal Processing Advances in Wireless Communications (SPAWC), pp. 1-5, 2020. doi: 10.1 119/SPAWC488577 21t.22200...5322.
Daniel Tang. Efficient algorithms for modifying and sampling from a categorical distribution. CoRR, abs/1906.1 1700, 2019.
11

---

Under review as a conference paper at ICLR 2022
Hongyi Wang, Scott Sievert, Shengchao Liu, Zachary Charles, Dimitris Papailiopoulos, and Stephen Wright, Atomo: Communication--ffiiiii learning via atomic sparsification, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Gamett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018
Bengio,
Jianyu Wang and Gauri Joshi. Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efiin
SGD Algorithms. 2018.
Jianyu Wang, Anit Kumar Sahu, Zhouyi Yang, Gauri Joshi, and Soummya Kar. Matcha: Speed- ing decentralized sgd via matching decomposition sampling. In 2019 Sixth Indian Control Conference (ICC), pp. 299-300, 2019a. doi: 10.1 109/CC/47118 21147133.201999122299
Jianyu Wang. Qinghua Liu, Hao Liang, Gauri Joshi, and H. Vincent Poor. Tackling the objective in- consistency problem in heterogeneous federated optimization. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tices Lin (eds.), Advances in Neural In- formation Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020a.
Jianyu Wang, Vinayak Tantia, Nicolas Ballas, and Michael Rabbat. Slowmo: Improving communication--eficieein distributed sgd with slow momentum. In International Conference on Learning Representations, 2020b.
Shiqiang Wang, Tiffany Tuor, Theodoros Salonidis, Kin K. Leung, Christian Makaya, Ting He, and Kevin Chan. Adaptive Federated Learning in Resource Constrained Edge Computing Systems. IEEE Journal on Selected Areas in Communications, 37(6):1205-122) 2019b. ISSN 15580008. doi: 10.1109//SAC:2119.2000 9.2904348.
Rachel Ward, Xiaoxia Wu, and Leon Bottou. AdaGrad stepsizes: Sharp convergence over noncon- vex landscapes. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 6677-6686. PMLR, 09-15 Jun 2019.
12

---

Under review as a conference paper at ICLR 2022
A CLIENTS SAMPLING SCHEMES CALCULUS
In this section, we calculate for MD, Uniform, Poisson, and Binomial sampling the respective aggre- gation weight variance Var [w)(S))], the covariance parameter such that Cov (w)(S))), (S,))
-. and the variance of the sum of weights Var [2 (;t))]. We also propose statistics for the parameter N, i.e. the amount of clients the server communicates with an iteration:
N Σ I(i E S.).
(16)
A.1
PROOF OF PROPERTY
Proof. Covariance parameter
Cov (sy = E (s))s,, - P.P, 2 -PiPs
(17)
Aggregation Weights Sum
TV
n
Var
Σ
wi(Ss)
Var [w:)l +
Σ
Cov (S)(
(18)
Var [w:( -a a Σ
PiPj
(19)
Var (S:)] - ap, (1 p.)l
(20)
Var (S:)) - α - pk
(21)
1, equation for the third and fourth equality. Using equation 20 we see that we can also get the following equality based on Decomposition Theorem
where we use Σラ= =
Var
Σ (s.))
Σ a.
(22)
Re-expressing a. Using equation 20 we get
Var
Σ (i.))
Var [wi - 1
pi
(23)
which, with reordering, gives
EL Var [w)(S.)) - Var |E (S:)
(24)
A.2 No SAMPLING SCHEME
When every client participate Vars, (w.) = 0, a = 0, and N = n.
optimization round, we have wi(S)) Ps which gives
A.3 MD SAMPLING
We recall equation
w((S)) = I(lk = i),
(25)
13

---

Under review as a conference paper at ICLR 2022
which gives
B (5r
(S)))
1
Σ
E
[T(ee=
= i]T( = 5)]
1
Σ
R [T(4= = 2)T((A 5]
(26)
m
m k=1
1
Σ
paPj
1
E
[1( +)]((A+= = =
(27)
m
m² k=1
1
1
PiPj
+
[[[
i)I((I j)l
(28)
m
m
Variance(i = j). We get E [L(1 = 1)_((1 = -)] = E [1( = i)] = Pi, which gives:
1
Var (w:(S:) = --p pi Pi
(29)
m
Covariance(i + j). We get E [[( i)[(( -)] = 0., which gives:
1
Cov (S))
p.Pj.
(30)
m71
and by definition we get
(31)
Aggregation Weights Sum. Using equation 29
and
31 with Property I
we get
Var
(S,)
=
(32)
1=1
Amount of clients. Considering that p(i E Si) = - ppi & Si) 1 (1-P,) p.) we get:
E [N] Σ P(ie Si) = (1 - p.) S m
(33)
A.4 SAMPLING CLIENTS UNIFORMLY WITHOUT REPLACEMENT
We recall equation
w.(S)) 1(i E Si) S:) Pt. m
n
(34)
Variance. We first calculate the probability for client to be sampled, i.c.
P(i E S,) = P(i $ St) =
n a m
71
m
m
(35)
n n1
m
+
71
Using equation
35). we have
Vars, [w,(S)) _p) Pi m
2
Var [ S.)]
n² m
71
1)p²
(36)
m n
72
7
Covariance. We have
P((ijj] E S.) = IP(i E
P E S.)
(37)
=IP(i S.) +P S.) - (1 - P((i,)) $ S)),
(38)
and
n 2 2 n m
(n - m) m) (n - m - 1)
P( & S.)
(39)
n(n - 1)
14

---

Under review as a conference paper at ICLR 2022
Substituting equation 35 and (39) in equation 338 gives
P((i,) E St) = 2 m
+ (n m) mn(n m - 1)
2
(40)
n(n - 1)
22 1) n(n 1) + (n m)(n m 1)]
(41)
n(n - 1)
mmm 1)
(42)
n(n - 1)
Hence, we can express the aggregation weights covariance as
n² m(m - 1) m n(n PjPk PyPks
Cov (S.) =
(43)
which gives
Tt - m
m(n - 1) 0:
(44)
Aggregation Weights Sum. Combining equation
(3 and 44 with Property 1
gives
Var
Σ (S))
=
n
p
n m
Σ
P. - (1)
(45)
m(n
1)
1=1
1=1
n m
p
(46)
m(n n
1)
1=1
where we retrieve Var EE= (S.)] for identical client importance, i.e. E Pi n
Amount of Clients. N m.
A.5 POISSON BINOMIAL DISTRIBUTION
Clients are sampled according to Bernoulli with a probability proportional to their importance i.e.
(S,) B(mp:).
(47)
m
Hence, only 2 Pmiz can be sampled and retrieve E [w,(S:)] 1. mp: Pt.
Variance.
1
Vars, (w(( m mp; mp:) = Pp((1 mp:)
(48)
m
Covariance. Due to the independence of each stochastic weight, we also get:
Cov w, (S.)) 0
(49)
Aggregation Weights Sum. Using Property
we obtain
Var
(i()
p.
(50)
1=1
Amount of Clients.
E [ = m and Var [N] = m
m
p
(51)
15

---

Under review as a conference paper at ICLR 2022
A.6 BINOMIAL DISTRIBUTION
Clients are sampled according to a Bernoulli with identical sampling probability, i.e.
n
m Pss
(x
B
(52)
m
π
Hence, we retrieve E [S,)
m P: = P:-
Variance.
Vars, [w:)
n² m (1 m² n
)p
m
P..
(53)
m
Covariance. Due to the independence of each stochastic weight, we have: Cov (s 0.
(54)
Aggregation Weights Sum. Using Property gives
Var
(St)
n1 m
(55)
m
Amount of Clients.
m
E [N] m and Var [N] m
(56)
n
A.7 CLUSTERED SAMPLING
Clustered sampling (Fraboni al. 2021 is generalization of MD sampling where instead of sampling m clients from the same distributions, m clients are sampled from m different distributions [W each of them privileging a different subset of clients. We denote by т,es the probability of client to be sampled in distribution k. To satisfy Definition the original work (Fraboni et al. 2021 provides the conditions:
Vk (1,..,,, m), Σ - and Vi E {l,...,,)
n),
Σ Tku mp:.
(57)
k=1
The clients aggregation weights remain identical to the one of MD sampling, i.e.
(i(() I[(4=1) =).
(58)
k=1
where I(4+ are still independently distributed but identically.
We have
E (Se)
Σ
[ = 0)I(4 = =
E [144 = i)1((4 = 5)l
(59)
m
m
kllp
1=1
+ m
Σ
E [[4
E)I((4+ j)]
(60)
m
k.ly
k=1
m
m
PcP
E [1(2 i)1((o =]]
(61)
m
where we retrieve equation 288 when This = Ps.
Variance (i = j).. We get IE [I(4+ = i)1(44 = E [1(4 = i)] = Tk.i. which gives:
m
Var (Sxr)] = m 1=1
Σ
k S Var (SM
(62)
16

---

Under review as a conference paper at ICLR 2022
where the inequality comes from using the Schwartz inequality with equality if and only if all the m distributions are identical, i.c. Tk, = Ps.
Covariance (i # j). We get E [I(4
i)I((k+ -)] = O, which gives:
Cov (wa()))), (Sci)
Tka S Cov (SN(S wy
(63)
T
where the inequality comes from using the Cauuch-Schwarc inequality with equality if and only all the distributions are identical, i.e. Th,i = Pi.
A Aggregation Weights Sum
Var
Σ
(Sci)
O.
(64)
A.8 OPTIMAL SAMPLING
With optimal sampling (Chen et al. 2020b), clients are sampled according to Bernoulli distribution with probability qi, i.e.
wi(S.)
Pt B(:)).
(65)
qi
Hence, retrieve E [wr(S.)
q: 96 Pi-
Variance.
Vars, (St)
qi p.
(66)
9
Covariance. Due the independence of each stochastic weight, have:
Cov [w:) wy (S.)) 0.
(67)
Aggregation Weights Sum. Using Property gives
Var
Σ
(S:)
=
Σ 1=1
2
(68)
1=1
Amount of Clients.
n
[N]]
Σ 9: and Var [N] Σ
9: (1 qi).
(69)
17

---

Under review as a conference paper at ICLR 2022
Table 2: Common Notation Summary.
Symbol
Description
Number of clients.
K
Number of local SGD.
Local/Client learning rate. Global/Server learning rate.
ng
Effective learning rate, vi 1/77/--
e
Global model at server iteration t.
0
Optimum of the federated loss function, equation Db.
0
Local update of client on model 0*
Local model of client after SGD (V', = 0 and vf,o 8t)
P
Importance of client in the federated loss function, equation
Number of sampled clients
S.
Set of participating clients considered at iteration Aggregation weight for client given St. Covariance parameter.
(S.)
Y B, [
cf Section 3
Expected value conditioned on 6t
20
Federated loss function, equation !
4
Local loss function of client i.
9:
SGD. We have Eg, [g) = v-.(-) with Assumption Random batch of samples from client of size B. Lipschitz smoothness parameter, Assumption 2 Bound the variance of the stochastic gradients, Assumption Assumption parameters on the clients gradient bounded dissimilarity.
B, K
B DECOMPOSITION THEOREM
In Table we provide the definition of the different notations used in this work. We also propose in Algorithm the pseudo-code for FedAvg with aggregation scheme
Algorithm Federated Learning based on equation
1: The server sends to the n clients the learning parameters (K, Mit, B).
2:
for i {O,-... T 1) do
3: Sample a set of clients S, and get their aggregation weights d, (t).
4: Send to clients in S, the current global model 0
5: Receive each sampled client contributions (t()) = 0 - 0¹
6: Creates the new global model g++ 0' ng Σ" Σi_ (t)
7: end for
B. USEFUL LEMMA
We first introduce and prove the following useful lemma before introducing the proof of Theorem 1
Lemma 1. Let us consider vectors Di ..., En and client sampling satisfying Es. (w; and Cov (S))) op:ii. We have:
Esg
wi( )a:
Σ 7a | 1 (1 ax)
p:a0
(70)
where n Vars, (S:) + ap?
18

---

Under review as a conference paper at ICLR 2022
Proof.
Es
Σ (r
Σ Rs, (S.) | 10 +
Es, (s)(S)) m))- (71)
i=1
j
In addition, we have:
Es, (s,)w, Cov ( (S,)] + P.Pj 1
(72)
where the last equality comes from the assumption the client sampling covariance. We also have:
71
72
T2
72 p x 1?
p P,az))
Σ
(73)
Jeh
Substituting equation
72
and equation
73
equation 71 gives:
Es,
Σ (S.)aa =
Es, [s)( - (-a + 1)p | 12 (-a+1)
Σ
p:
1=1
(74)
Considering that we have Es. [S.)3] = Var (S:) + ps. we have:
Es, [S.) (a - 1)p? Vars, [ws(S:)] + opp,
(75)
Substituting equation in equation 774) completes the proof.
B.2
PROOF OF THE DECOMPOSITION THEOREM
Proof.
E2 - -0110] R [|( 0t) )+)+ + (0' 0²) 11
(76)
1100 11 + 2(EE, 10 0') 0' 0²) + E,
0011² |||0-t--0111
(77)
By construction (equation
). we have g 0 119 Σm= (1 (0 0²). The sampling
scheme follows Definition which gives Es, [0l+1 - 00| = 119 Σ P:(0/+1 0²). Hence, we
get:
E, |
0 0-1 + 27 > ps E, [0 0t 0¹ 0T)
n E,
Σ w/ (S,) 0¹)
(78)
=
Using Lemma
we express Q(0') as follow:
[]]
Qi((0)) Σ vi E, |10 - -0-13] + a) E,
Σ (0 0²)
(79)
By construction, have 05-1 - =-IK-
- n1g; (v/ Considering Assumption gives
E | 00|13] ?r E || + +E [||]
(80)
19

---

Under review as a conference paper at ICLR 2022
Similarly, by using twice Assumption for the global model drift, we have
27
ni E
Σ p
=
ní
E
Pi5i
+ tm
E
Σ p
(81)
pt TE || 2
+ E
(82)
where, for the last equality, Assumption Combining equation
gives [K]] {3)
[4:)
[5)] 0.
80 with equation
gives
Q(0')
Var (at) + pfl E [|
+
Σ Y
||
+ (1 - a)) E
pr A
(83)
Substituting equation
83 in equation
78 completes the proof.
B.3 ADAPTATION TO CLUSTERED SAMPLING
Instead of Lemma which requires Cov [w, (St), wy((s) -ap;Pj. we propose the following
Lemma for clustered sampling expressed in function of MD sampling covariance parameter aMD showing that a sufficient condition for MD sampling to perform as well Clustered sampling that all are identical, or that all the distributions are identical, i.e. Th, Pt-
Lemma 2.
Let us consider n vectors Di, ..., In and a client sampling satisfying Es, [wi(S)) = ps and Cov (s, = op.pp. We have:
Eser
Σ
xMD) |0011 2 + (1 aMD)
Σ
paa:
(84)
where () and aMD the aggregation weights statistics of MD sampling. Equation an equality if and only if E.= Tk = - T..
84 is
Proof. Substituting equation
62 in equation
71 gives
n
n Σ >
Eser
Σ
(S
Eser [wi(Sci) ||0, 12 12+
P.Ps (ap (x,,
==1 j=1 3942
(85)
3
Substituting equation
73
in equation gives:
n
n
Esct
wi (Sc))
Eser
Wi ( ||<0 2
Σ
pia
p
x 2
2
Σ
rk D
Σ
x ||
(86)
20

---

Under review as a conference paper at ICLR 2022
With rearrangements and using equation (57 get:
Esa
Var [wi(Sci)]
+
R
||
+
Σ
p;z;
m
k=1
k Z
(87)
Using the expression of clustered sampling variance for the first term (equation (63 and using Jensen's inequality the third term completes the proof. Jensen's inequality is an equality if and only if Ei=1 T = Σ== T.
21

---

Under review as a conference paper at ICLR 2022
C FL CONVERGENCE
Our work is based on the one of Wang et al. (2020a). We use the developed theoretical framework there proposed prove Theorem 2 The focus of our work (and Theorem 2 on FedAvg. Yet, the proof developed in this section, similarly to the one of Wang et al. (2020a), expresses in such way they can account for wide-range regularization method on FedAvg, or optimizers different from Vanilla SGDone. This proof can easily be extended to account for different amount of local work from the clients (Wang et al. 2020a).
Before developing the proof of Theorem in Section we introduce the notation we use in Section C.I some useful lemmas Section and Theorem generalizing Theorem 2 Section
C.I NOTATIONS
We define by y the local model of client i after k SGD steps initialized on 0', which enables us also define the normalized stochastic gradients di and the normalized gradient h defined as
K-1 0g (vi,)) and h
K-1
d:
Σ k=
0i V (V),))
(88)
where a; is an arbitrary scalar applied by the client its kthh gradient, a, [as,o. 0g 1"" and a; = ||a: In the special case of FedAvg, we have a, = [1.... 1] and in the one of FedProx, we have = [1 μ1) ..... 1] where is the FedProx regularization parameter.
With the formalism of equation 88 we can express a client contribution as 0 - 0³ -ma,d and rewrite the server aggregation scheme defined in equation
0
0
-7gg7
wrad
(89)
which in expectation over the set of sampled clients St gives
Es, [ - 0¹ =
p.a,d
(90)
i=1
Σ
Pitt
p:os
d
(91)
1== Pid
i=1
Koff
W:
We define the surrogate objective [(x) = Ei= wrL,(x), where Σi=1 W4 = 1.
In what follows, the norm used for a; can either be LI, ||-||, L2, |1-112, For other variables, the norm is always the euclidean one and ||-ll is used instead of ||-1|2- Also, regarding the client sampling metrics, for ease of writing, use w; instead of (S,) due to the independence of the client sampling statistics with respect to the current optimization round.
C.2 USEFUL LEMMAS
Lemma 3 (equation (87) in Wang et al. 2020a)) ). Under Assumptions 1o
we can prove
1 nf 2
w. VC'(0') - h1ll]]
<
Σ
wi
(la, 1
-
2 1
R
1=1
R33
RI?
V
+ 2(1 R)
E
+
(92)
2(1 R)
with R = =2n max:{[la;1| ((|aillı -ii--1) with a learning rate such that R 1.
22

---

Under review as a conference paper at ICLR 2022
Proof. The proof is in Section C.5 of Wang al. (2220a).
The bound here provided is slightly tighter in term of numerical constants than the one of Wang
et al. 2020a). Indeed, equation (70) in Wang et al. (2020a) uses the Jensen's 's inequality I|a + bll -
2 a|
+ 2|6 which could instead be obtained with:
E
EE
Σ assa (a:(vl.s) VL.(Ui.))
+B
Σ oi (vt.)
(93)
which uses Assumption giving IE with the same reasoning as for U in equation I1I..
(E== 0i,s (9:(v()))) - vC(()))))) EE= aiss vL.(
-0
Lemma 4. Under Assumptions
to
we can prove
L ||,
(1a:112 (a?.-1)
Yi
R
i=1
+2 2
R
+ +1
Σ naj
(32 E
(94)
1 R
where Rt' = 222 L2 max, [|].117) 1.
Proof.
Due to the definition of h1 we have:
K-1
27
E
a h
at E
ai,k
(B(
(95)
k==
K- 1
E [[V2.19(N)11
S 0
aik
(96)
Oj
k=0
Using Jensen inequality, we have E [|VA:WAW)
s 2 (L.()(, (0'() 2 [|V2((011]]
(97)
< <2L 1
011"] +2 |VCC(0)))
(98)
where the second equality comes from using Assumption 2 Also, Section C.5 of Wang et al. (2020a) proves
0i
E
vi,
0-13]] <
1 R
0² (1a:112 (o).-1)
1 R
E
L
1
R
k=
(99)
Plugging equation
98 and then equation
99 in equation 96,, we get:
K
E lach
|1
S
?
ai,k
2L
|
0-] + +2E |I (1)
(100)
04
K-1
= 2
ai,k
E
|1 081]3]
+ 2a E
( |²
(101)
ai
k=
< <2L
1
11
2
1ail12 (af
+ T2 i
R E
[0)
R
R
+ 20 E
||
(102)
< R'
o²
(la.112 (ai,-1) 2a²
R
+1
E
|VC
(103)
1 1- R
23

---

Under review as a conference paper at ICLR 2022
Summing gives
Σ ==1
7 E
S 221
1
1f 0²
Σ
na
||:il|2 - (a?
1 R
==1
R
+
na
(104)
1 R
Using Assumption 3 in equation (044) and R' < completes the proof.
C.3 INTERMEDIARY THEOREM
Theorem 3. The following inequality holds:
E t=0
|E(03) < <O (1- |
0(iA'o2 + O B')
(105)
where quantities A-E are defined in the following proof equation 122 to equation 126
Proof. Clients local loss functions are L-Lipschitz smooth. Therefore, i also L-Lisschitz smooth which gives
(((0tt)-((001) < (Vī())), 0h+1 -0))
g 1']]))
(106)
T
T
where the expectation is taken over the subset of randomly sampled clients S, and the clients gradient estimator noises E Please note that we use the notation E [-] instead of B(g;), for ease of writing.
BOUNDING T1
By conditioning on { and using equation 91
we get:
Ti = E (Vi(0'), Es, 10 - (0+1--0')] iKees EE (vi(0"), Σ winhi)
(107)
which, using 2(a, b) = ||a||2 + ||b||2 - ||a - 21l2 can be rewritten as:
Ti - E V2(0>)
Σ w
vi(0") - Σ w.h!
(108)
1=1
24

---

Under review as a conference paper at ICLR 2022
BOUNDING T₂
T2|S B
a |5c
(109)
of² E
wiaz (d) - 11.) + Σ
wiah
|St
(110)
i=1
7f² E
wiat (dş - -hi) |St
+ 1 E
waa
|St
+ 2n E
Wiat (df - n2)) D wra
(111)
Using Assumption 1 have E [[d]
11 hnyp
Hence, we get U and can simplify T2 as:
n
T- E w
a
EE
nill"]
+ 772 E
Σ wrah
(112)
Using Lemma on the second term, we get:
T2
1
E W
07
EE
df
17 Σ
7s E ||ah
+ - a)
Σ
peach
(113)
Finally, by bounding the first term using Assumption I and noting that pra; wiKesf for the second term, we get:
K
T2 1
L E
-
+
E | h |'] +
-1 - a)K²,1 E
Σ wihh h
(114)
t=1
[w]]]
|a 0² + 7
Σ
7 E
|ash!l [1
+ f a)
Σ w; h
1=
(115)
GOING BACK TO EQUATION 106
Substituting equation 108 and equation (115) back in equation (106). we get:
27
1() -((00] s - kk
V
+ RKKesB
+
Vī(
w, w
/ TiKess
Līi(1 a)) Kefs|
Σ wi ko
L -2
B [
[a;
12
2
L
7/ E
|laghi|1?]
(116)
2
2
1=1
25

---

Under review as a conference paper at ICLR 2022
We consider the learning rate to satisfy 1 Lnj(1 as O such that we can simplify equation 116 as: :
E (((0)))- - [(00]
+ 2 E
1
V2(0') Σ wih!
1 - 2
riKess
L
"
1
Σ
n
E [uf]]
a 0²
+ L " Keff
74 IE
[aah
(117)
2 Kess
1=1
1
| ||
+ ト
IE (L') - hill?
<
2
+ " Σ [u la:1122 0² + 2 Keff
L
Σ 74 IE
[aa. (118)
2 Keff
im1
where the last inequality uses the definition of the surrogate loss function E and the Jensen's 's in- equality.
Using Lemma and we get:
E ((0 -(())]
|
2
L222
Σ Wi
- -1
+ 2 1 1 R
ijKosf
2
1=1
R32
VŻ 11
Rk²
+ 2(1 R)
E
+
2(1 - R)
+ - 1
Σ
[wf]]
||a112 + 1- R Σ 78 (1a:113 - (af--1)) 0²
n
2 Kess
1==1
i=1
+ Lii
1
R
+1
Σ
na,
(8 | +
Keff
1-
R
1=1
(119)
If we assume that R < 1 and considering that 8 2 1, then we have
23"
1-R
1 S 1 +
232 S 2'
R T- - 1 and I-R V T +32
) J. We also define Ω L
1
3 (E )a??) B2 <
2' Substituting these terms in equation 119 gives
E ((00+1)- 2(04))
1 [1 12
V /|+
3 3 0²
Σ we (1a:11 - -
n
nKcl!
+ ž"² th L2 maxx(a k),=?
+
L 1
1
E [wi
1a.112
3 n
Σ
% (Ia.112 -oi o²
2 Keff
2
Li=1
t=1
+
3 Lî Kell
1
Σ
(120)
i=1
26

---

Under review as a conference paper at ICLR 2022
Averaging across all rounds, we get:
Ω T
|2
|9]
< - 2(0))
Tk 3.
Σ w/ -
i=1
+ 6nt L2 maxfaila - -4, -1,-1))
Li Kess
E
a 11 +3 Σ 78 (lail2 (a
(a2.-1))
0²
i=1
6L4
Σ naa
x2
(121)
Kefs
We define the following auxiliary variables
1
A = m
E
[
11.112 m
Var
[wi]] + +pe] la:112
(122)
Kefl
Ei=1 pid am1
2m
B = Σ wi
(la:113 122 - Σ
p:d:
- az (1a112-a?,-1)
(123)
j=1 Pjaj
C = max a1,-1))
(124)
1 D
max -1
1
C
Σ
Var [+s]
pf
(125)
Keff
8
Di=1 piaj
i=1
1=1
n
E
maxxfa?
Σ %/
2i=1 max(a?}
Σ
Var [wi]] + a
2
(126)
Keff
We define for A -E the respective quantities A'-E" such that X'
I- X. We have:
-(09)-20 -
+ Σ E
+2 + 3.
(1 1) (
+ i. +3TnDo + BINjRR
(127)
C.4 SYNTHESIS OF LOCAL LEARNING RATE πY CONDITIONS FOR THEOREM
A sufficient bound on the local learning rate rp for constraints on R for Lemma 3 and equation and constraint on R' for Lemma to be satisfied is:
119
2 [2.8 1] 7f T.2 max (l|a <.
(128)
Constraints on equation (166) can be simplified as
Lngh(1 K) < 1.
(129)
Constraints on Ω, equation 1199 give
3 T1 Kesl
Σ naa i=1
82 $1. S
(130)
27

---

Under review as a conference paper at ICLR 2022
C.5 THBOREM
With FedAvg, every client performs vanilla SGD, As such, we have di,k - 1 which gives K and ||a:||2 v K. In addition we consider a local learning rate yp such that 52 s 1/ as such we can bound A' as X < 2X.
Proof.
Finally, considering that the variables A to E can be simplified as
A m
Var [wm]] + p21
(131)
B (K 11,
(132)
C K(K 1),
(133)
D = -K-
Σ Var [wi] +
(134)
and
11 Var [ws] + a
E = K
Σ
E p$
(135)
2m1
the convergence bound of Theorem can be reduced
Σ B [|VC(00)]
5o
+ 17
Var [wi] pēl 0²)
7TTKK
+0 (K - -1)o?) + O (m K(K - 1)x?)
[KK- 10)-2 + kntl) (136)
Var [wi] + a Σ ps +0 Tl Σ
which completes the proof.
př. With full participation, we have 0. Q proportional to E= Var +o E.
_ However, with client sampling, all the terms in equation (136) are proportional with I-B Yet, we provide looser bound in equation (136) independent from the conclusions drawn are identical. Through Ω Σ Var [wi] and needs to be minimized. This fact is already visible by inspection of the quantities and
We note that equation (36) depends on client sampling through a², which is an indicator of the clients SGD quality, and n² which depends on the clients data heterogeneity. the special case where clients have the same data distribution and perform full gradient descent, based on the argu- ments discussed in the previous paragraph, we can still provide the following bound showing the influence of client sampling the convergence speed, while highlighting the interest of minimizing the quantities >n= Var [wx] and a.
T-1 Σ 1=
E [II[O0)))
so (0(00000))))0 KT <
+
(137)
When setting the server learning rate at 1, 7, = 1 with client full participation, i.c. Var [ar[w:] 0 and m n, we have E F = 0 and can simplify A to
=
Var D>e wi]
= n
(138)
28

---

Under review as a conference paper at ICLR 2022
Therefore, the convergence guarantee provide is D)k², which is identical to the one of Wang et al. (2020a) (equation (97) in their work), where Σx=1 Pf can be replaced by 1/n when clients have identical importance, i.e. ps 1/n.
77 KT
In the special case, where we use ?h convergence bound VKKT V KT 2i=1 D200² + T
=V mmmK// Wang et 2020a retrieve their asymptotic Kn.
C.6 APPLICATION TO CLUSTERED SAMPLING
We adapt Theorem to clustered sampling. Fraboni al. 2021 prove the convergence of FL with clustered sampling by giving identical convergence guarantees to the one FL with MD sampling. As result, their convergence bound does not depend of the clients selection probability in the different clusters Tk, The authors' claim was that reducing the variance of the aggregation weights provides faster FL convergence, albeit only providing experimental proofs was provided support this statement. Corollary hhere proposed extends the theory of Fraboni et al. (202I) by theoretically demonstrating the influence clustered sampling on the convergence rate. For easing the notation, Corollary 2 is adapted to FedAvg but can easily be extended to account for any local a; using the proof of Theorem i Section C.3
Corollary 2. Even with no a such that Cov (St), Wy
apppp the bound of Theorem wy (St))
still holds with B, C, and D) defined as in Section C.3 and
1
1 E (K-1) 1), and F = = K,
A = m
(139)
m
where E and F are identical to the for MD sampling and A is smaller than the one for Clustered sampling.
Proof. The covariance property required for Theorem 3 is only used for Lemma In the proof of
Theorem 3 Lemma D is only used in equation (113) We can instead use Lemma 2 and keep the
rest of the proof it in Section C.3 Therefore, the bound of Theorem 3 remains unchanged for clustered sampling where and I use the aggregation weight statistics of MD sampling instead of
clustered sampling. Statistics for MD sampling can be found in Section A.3 and give
1
Var
w((Sm))
0 and OMD m'
(140)
while the ones of clustered sampling Section A.7 give
Var (Sci)]
Var (wi(S
(141)
m
Jmm
C.7 PROOF OF COROLLARY
Proof. Combining equation
29
with equation
36
gives
ΣND
Ev
P5
pt
(142)
m
171
m
1
(n
+ 1)
pi
(143)
m
Therefore, we have
EMD S Ey $
Σ
(144)
177
i=1
29

---

Under review as a conference paper at ICLR 2022
Combining equation
31
32
44
and 46 gives
7MD
-70
Var [Sm(D + OArD Σ
P
Σ
Var
[wt + ou
Σ
ps
(145)
i=1
==1
1=1
n
m
n1
p.-
(146)
m(n
1)
1=1
Therefore, we have
7 YND
n
70 -
(147)
m
n
i=1
Noting that
71
-m7 + 1
3
(148)
mM8 +
n(n m) m + 1)
completes the proof.
30

---

Under review as a conference paper at ICLR 2022
D QUADRATIC
Proof. For every client, we consider local loss functions such that:
() 0-
(149)
where Of is client's i local minimum. By taking the derivative of the global loss function, equation [T) with these clients local loss function, gives:
0
P.O.
(150)
f is the local model obtained for client i after & SGD and satisfies
v',+11= vi nllli 03) (1 m)) n0
(151)
which, by induction, gives
0.+1 (1 11-mp m1)K 0² 0 Σ (1-mm) mn
(152)
We note that Ek=o (1 m1)* (1 mu) 1 1/m By defining = - (1 - m1)K we get:
0. 0² = (1 - mp 0² + [1 - (1 - m K 0: -0¹ = =0(0,- 0²).
(153)
Hence, we have
n
P0 0¹) 6(0" 0¹).
(154)
Using Decomposition Theorem
leads to
E ||0
1-] = (1 27) E |100 - 01|13]
+ n Σ
n
||0r 0; 12]
i=1
+ 11 a)D2 1100 -0- 1-11²]]
(155)
31

---

Under review as a conference paper at ICLR 2022
E
ADDITIONAL EXPERIMENTS
E.
SYNTHETIC EXPERIMENT
(a)
(b)
Full
Uniform
2
0.2
(c)
(d)
8
8
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
1.0
Figure 3: Additional plots for Figure Illustration of the Decomposition Theorem for the syn- thetic scenario described in Section 4.1 for n = 10 clients when sampling m = 5 of them. Panels (a) show the distances estimated experimentally when averaging over 1000 simulations for iid (Panels (a) and (c)), and non-iid settings, (Panels (b) and (d)), and with the associated standard deviation, (Panels (a) and (b)), and minimum and maximum distances, (Panels (c) and (d)). We
consider 17g 1, m 0.1, and K = 10.
1023
20a2
let- I
109
Full
10a
MD Uniform
10-5
10
10-19
10-20
200
400
600
800
1000
200
400
600
800
1000
t
Figure 4: We consider the synthetic scenario described in Section 4.1 for 100 clients when sampling m = 5 and r = 0.9. We show the distances estimated experimentally when averaging 1000 simulations for iid (Panel (a)), and non-iid settings (Panel (b)). We consider 7, 1, = 0.2, and K = 1. With K = 1, we show that the divergence does not come from asking too much work the local clients. Uniform sampling divergence be prevented by lowering the local learning rate (consistently with Theorem
E.2 SHAKESPEARE DATASET
The client local learning rate π) is selected in (0.1, 0.5, 1,, 1.5, 2,, 2.5} minimizing FedAvg with full participation, and 80 training loss at the end of the learning process.
32

---

Under review as a conference paper at ICLR 2022
10
(b) n
1.5
1.5
1.0
1.0
0.5
0.5
100
200
300
400
500
100
200
300
400
500
40
(d)
80
2.0
1.5
1.5
1.0
0
100
200
300
400
500
100
200
300
400
500
(e)
10
(f)
20
1.5
1.0
1.0
100
200
300
400
100
200
300
400
(g) n 40
(h) = 80
2.0
2.0
2109
1.5
1.5-
1.0
100
200
300
400
500
100
200
300
400
500
# rounds
rounds
Uniform
Clustered
Figure 5: Convergence speed of the global loss with MD sampling and Uniform sampling when considering 10 ((a) and (c)). n 20 ((b) and (f)), n 40 ((c) and (g)). and n 80 ((d) and (h)), while sampling m = n/2 of them. In (a-d). clients have identical importance, i.c. = 1/n, and, in (e-h), their importance proportional their amount of data, i.e. pt n//M. Global losses are estimated on 30 different model initialization.
p 1/n
(b) n.M
0.075
0.0
((0 c(ee)
0.050
0.1
0.025
0.2
0.000
0.3
-0.225
0.4
-0.550
200
300
400
200
300
400
rounds
m=4
m=
m=40
rounds
Figure 6: Difference between the convergence of the global losses resulting from MD and Uniform sampling when considering perform K 50 SGD steps. In (a), clients have identical importance, i.e. p: 1/n. In (b), clients importance is proportional their amount data, i.e. p; = n//M. Differences in global losses are averaged across 15 FL experiments with different model initialization (global losses are provided in Figure
80 clients and sampling
{4,8, 8, 40) of them while clients
33

---

Under review as a conference paper at ICLR 2022
(a) m
(b)
2.0
2.0
1.8
1.8
1.6
1.6
1.4
1.4
1.2
1.2
1.0
1.0
200
400
600
800
1000
200
400
600
800
1000
m
2.0
2.0
1.8
1.8
1.6
1.6
1.4
1.4
1.2
1.2
200
400
600
800
1000
200
400
600
800
1000
rounds
# rounds
Uniform
Clustered
Figure 7: Convergence speed of the global loss with MD sampling and Uniform sampling when considering = 80 clients while sampling m = ((a) and (c)), and m = 8 ((b) and (d)) while clients perform K 50 SGD steps. In (a-b), clients have identical importance, i.e. Pt 1/n, and, in (d-f), their importance is proportional to their amount of data, ie. n,/M. Global losses are estimated 15 different model initialization.
(a) 1/n
(b) p. n./M
0.04
0.02
<(0xo) - -((u))
0.02
0.02
0.04
0.00
-0.66
0.08
0.10
1000
1250
1500
1750
2000
2250
2500
1000
1250
1500
1750 # rounds
2000
2250
2500
# rounds
m=8
== 40
Figure 8: Difference between the convergence of the global losses resulting from MD and Uniform sampling when considering n 80 clients and sampling m {8, 40) of them while clients perform K SGD step. In (a), clients have identical importance, i.c. p; 1/n. In (b), clients importance proportional to their amount of data, i.c. p: n,/M Differences in global losses are averaged across 15 FL experiments with different model initialization (global losses are provided in Figure
34

---

Under review as a conference paper at ICLR 2022
(a)
(b)
4-
3
3
2
2
500
1000
1500
2000
2500
500
1000
1500
2000
2500
(c) m 8
(d)
40
4
4
3
2
2
500
1000
1500
2000
2500
500
1000
1500
2000
2500
rounds
rounds
MD
Uniform
Figure 9: Convergence speed of the global loss with MD sampling and Uniform sampling when considering 80 clients while sampling m = 4 ((a) and (d)), m = 8 ((b) and (e)). 40 ((c) and (I)) while clients perform 1/n, and, in (d-f), their importance is proportional to their amount of data, i.c. pt n,/M. Global losses are estimated on 15 different model initialization.
= 1 SGD steps.
(a-c) clients have identical importance, i.c.
35

---

Under review as a conference paper at ICLR 2022
E.3 CIFARIO 10 DATASET
We consider the experimental scenario used to prove the experimental correctness of clustered sam- pling in (Fraboni al. 2021 on CIFARIO (Krizhevsky) 2009). The dataset is partitioned clients using a Dirichlet distribution with parameter a = 0.1 as proposed in Harry Hsu et (2019).
100
10, 30, 30, 20 and 10 clients have respectively 100, 250, 500, 750, and 1000 training samples, and testing samples amounting to fifth of their training size.
(a) a 0.1
2.0
1.5
1.0
200
400
600
800
1000
(b)
0.01
2.5
cie
2.0
1.5
200
400
600
1000
(c) a
0.001
3.0
2.5
2.0
1.5
0
200
400
600
800
1000
rounds
MD
Uniform
Clustered
Figure 10: Convergence speed of the global loss with MD sampling and Uniform sampling when
considering n 100 clients, while sampling m = 10 them. Clients are partitioned using Dirichlet distribution with parameter 0.1 (a), 0.01 (b), and 0.001 (c). Global losses are estimated on 30 different model initialization.
36


Reviews:
[{"review_id": "l28OZTUSLBQ", "reviewer": "Reviewer_FJmg", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Pros**:\n- The paper is well-written\n- The theory is well-developed and is correct to my knowledge\n\n**Cons**:\nMy major concern is on the novelty of the theoretical analysis of clients' sampling.\n\n- Clients sampling in FL and mini-batch sampling in SGD are closely related to each other. Related works on the sampling strategy for SGD are not well-address, for example [1, 2]. The major difference between FL and mini-batch SGD is that FL runs more steps during the local update, but SGD performs a single step. But this difference should not cause too much trouble. It seems that the analysis of the sampling scheme for SGD can be directly applied to the context of FL. Could the author(s) elaborate on the challenge of applying importance sampling to FL?\n\n- Unbiased client sampling is closely related to unbiased gradient estimator, which is common knowledge in stochastic optimization. The discussion on unbiased sampling doesn't \nseem to be something new.\n\n- The authors emphasized the importance and novelty of Theorem 1. I read the proof, and it seems to me that Theorem 1 is a detailed expansion of the variance term \n(instead of just bounding the variance by some constant in the literature). It is also straightforward that the variance can be decomposed as the summation of covariance. \nThe Theorem feels somewhat incremental, and I am not sure if it is significant enough to be accepted in ICLR. \n\n- My comment on Theorem 2 is similar to the above comment for Theorem 1. The result is from a detailed expansion of the variance term, and I am not sure if it is significant enough. \n\nSome minor comments:\n- In eq. (1), is it necessary to introduce \"I\"? Can we just write as \\sum_{i=1}^n?\n- In the second paragraph of page 7. The author(s) said that MD has an additional O(n) cost to construct the distribution and could be expensive. I think we only need to run this operation once before the FL start. I doubt if constructing the probability density for MD will introduce non-trivial overhead.\n\n\n[1] Peilin Zhao, Tong Zhang. Stochastic Optimization with Importance Sampling for Regularized Loss Minimization. ICML 2015.\n\n[2] Dominik Csiba, Peter Richt´arik. Importance Sampling for Minibatches. JMLR 2018.\n", "summary_of_the_paper": "The author(s) studied the impact of the client sampling for FL. In particular, the author(s) proposed a decomposition theorem and used it to obtain an improved convergence analysis of FedAvg. Numerical simulations are conducted to support the author(s) theoretical analysis. ", "summary_of_the_review": "The paper is well-organized. But I am not convinced by the significance of the theoretical analysis of this paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "QNxtGb6rbGV", "reviewer": "Reviewer_LQPA", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n- The paper is very well written and very easy to understand and follow.\n- The paper studies a framework for studying the impact of client selection strategies for unbiased aggregation at the server. The framework separates the impact of client selection, client model drift, global model drift thereby providing new insights regarding the impact of client selection.\n- Through the framework, the authors provide theoretical and empirical evidence as to in which scenarios weighted sampling is preferrable over weighted sampling. Previously multiple papers had observed stable  convergence performance  with weighted sampling for cases  data sample is weighed equally. This framework validates those claims.\n- The experimental results back the theory.\n\nWeaknesses:\n- As showcased in Wang, et.al., \"Tackling objective inconsistency in federated learning\" (FedNova), the convergence rate in FL is affected by the objective inconsistency as well. It is not clear from the decomposition theorem, whether such an inconsistency is factored in.\n- It is not clear from the experiments what sort of data distribution was considered for the clients. It is not clear if the claims made in the paper continue to hold for both iid and non-iid distributions.\n- Moreover, the number of clients selected is roughly 50% of all clients present in the experiments. With unbiased aggregation, the variance is controlled with such a high selection rate. It is not clear if the number of clients are selected at a rate 5-10% clients per round or even lower, which is characterized by zero bias and high variance would have a different observation. With variance being the main deciding factor now, is there still a noticeable difference between sampling strategies? Also, how noticeable is the difference when each client undergoes just one step of SGD or likes of that as opposed to 50 steps of SGD. I would recommend the authors to add more experiments with only 5-10% clients being selected in each round.\n\nFinally, as a suggestion to the authors: In most practical systems, the server doesn't have the privilege to sample clients based on MD or uniform sampling. But, instead the sampling in practical FL system is mostly event triggered. In such a case, how would one go about sampling clients and ensure unbiasedness of aggregation schemes?", "summary_of_the_paper": "The paper studies a framework for studying the impact of client selection strategies for unbiased aggregation at the server for federated learning. The framework separates the impact of client selection, client model drift, global model drift thereby providing new insights regarding the impact of client selection. In particular, the paper proposed a decomposition theorem which quantifies  the dependence on client sampling. Finally, experimental results on Shakespeare back the theory and demonstrate the effectiveness of one sampling choice over another based on the loss function setup in a FL framework.", "summary_of_the_review": "This paper proposes a new framework to study the effect of client sampling strategies based on weighting of clients/samples in a federating learning setup. While the framework is new and provides new insights, there are some clarifications required in terms of the theoretical convergence results. The experimental results are also incomplete and not up to the mark. Additional experiments are required. The paper is in a good shape, but without the improvements above it's not a strong paper yet.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "KAy2sa1u0Nk", "reviewer": "Reviewer_Sg3m", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Structure.\n\nThis paper is well-written and it has a clear structure and narration. All assumptions are described and all variables are well defined. Proofs are also well-written and it is easy for a reader to follow. Proofs seem to be sound. \n\nHowever, in this paper pseudo-code of the considered algorithm is not provided. This might lead to confusion. It can be helpful for readers to have pseudo-code for better understanding. \n\nAuthors use the phrase \"after K SGD\". Does it mean that K SGD steps? This phrase is confusing. \n\nAssumptions.\n\nThe first assumption in this paper is Unbiased Gradient and Bounded Variance. \n\nAssumption 1 (Unbiased Gradient and Bounded Variance). Every client stochastic gradient $g_{i}(\\boldsymbol{x} \\mid B)$ of a model $\\boldsymbol{x}$ evaluated on batch $B$ is an unbiased estimator of the local gradient.\n\n We thus have $\\mathbb{E}_{B}\\left[{\\xi}_{i}(B)\\right]=0$ and $0 \\leq \\mathbb{E}_{B}\\left[\\left\\|{\\xi}_{i}(B)\\right\\|^{2}\\right] \\leq \\sigma^{2}$, with ${\\xi}_{i}(B)=g_{i}({x} \\mid B)-\\nabla \\mathcal{L}_{i}({x})$\n\nIn https://arxiv.org/pdf/2002.03329.pdf it was shown that this assumption is limited and the simple 1-D counterexample is provided in proposition 1. Instead of using the Bounded Variance assumption, it is better to use the Expected Smoothness assumption:\n\nAssumption (Expected smoothness). The second moment of the stochastic gradient satisfies\n$$\n\\mathbb{E}\\left[\\|g(x)\\|^{2}\\right] \\leq 2 A\\left(f(x)-f^{\\mathrm{inf}}\\right)+B \\cdot\\|\\nabla f(x)\\|^{2}+C\n$$\nfor some $A, B, C \\geq 0$ and all $x \\in \\mathbb{R}^{d}$ and function $f$ is bounded from below by an infimum $ f^{\\text {inf }} \\in \\mathbb{R}$. \n\nAnother questionable assumption is Assumption 3 (Bounded Dissimilarity ).\nThere exists constants $\\beta^{2} \\geq 1$ and $\\kappa^{2} \\geq 0$ such that for every combination of positive weights $\\left\\{w_{i}\\right\\}$ such that $\\sum_{i=1}^{n} w_{i}=1$, we have $\\sum_{i=1}^{n} w_{i}\\left\\|\\nabla \\mathcal{L}_{i}(x)\\right\\|^{2} \\leq$ $\\beta^{2}\\|\\nabla \\mathcal{L}(x)\\|^{2}+\\kappa^{2} .$ If all the local loss functions are identical, then we have $\\beta^{2}=1$ and $\\kappa^{2}=0$.\n\nThis means that analysis does not cover arbitrary heterogeneous cases. In https://arxiv.org/pdf/1910.14425.pdf it was shown that this assumption is also limited. It is described in Remark 3. \n\nTheory. \n\nIn this paper, there are two theorems. The first one is the decomposition theorem. This theorem provides several insights and it is an interesting result, which can lead to further improvement. However, in the statement, we have the phrase \"after K SGD\", which is not clear. However, FedAvg can be modeled not only by the local SGD method. There are many other approaches such as Federated Random Reshuffling (https://arxiv.org/abs/2102.06704, https://arxiv.org/pdf/2110.10342.pdf). It might be interesting to formulate similar theorems for other methods. \n\nThe second theorem provides convergence guarantees for local SGD. However, there is no epsilon complexity and comparison with other results. It might be useful for readers to have a table with different bounds. In http://proceedings.mlr.press/v130/gorbunov21a/gorbunov21a.pdf a lot of options and analyses are compared in Table 2.\n\nAdditionally, bounds for strongly convex and general convex cases are also desirable. \n\nExperiments. \n\nIn this section the comparison between Multinomial and Uniform Distribution. These plots are illustrative. However, it is also interesting to have a comparison with other methods used in Federated Learning. It is not clear why n \\in {10, 20, 40, 80}  are used and why only m = n/2 is considered. \n\nAdditionally, it might be interesting to apply analysis of client sampling to other methods for Federated Learning such as SCAFFOLD (https://arxiv.org/pdf/1910.06378.pdf), Federated Random Reshuffling (https://arxiv.org/pdf/2102.06704.pdf), Variance Reduced methods (http://proceedings.mlr.press/v130/gorbunov21a/gorbunov21a.pdf), but not only localSGD. \n\n\n", "summary_of_the_paper": "This paper analyses two client sampling strategies for federated learning algorithms. This work compares Multinomial distribution and Uniform distribution. The authors provide a decomposition theorem, that gives some insights into the impact of client sampling. Moreover, they provide convergence guarantees for the general non-convex case under some additional assumptions such as Bounded Dissimilarity. An experimental comparison of two sampling schemes is done at the end of the paper. ", "summary_of_the_review": "Overall, this paper introduces interesting ideas, but it needs significant revision. The assumptions are limited and analysis can be significantly generalized. In this paper, there are no theoretical and experimental comparisons with other methods. Moreover, only two distributions are compared, additional comparison with other distributions is needed. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "GCaHP_K13zV", "reviewer": "Reviewer_c4xq", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Main point:\nI don't see a sufficient contribution in this work for its acceptance. First of all, most of the results are straightforward. The results from Appendix A require no more than computing expectations and simple summations. Theorem 1 is not even a convergence result but rather a simple one-step recursion that can be obtained by expanding norms and scalar products. Theorem 2 is proved using standard techniques from prior work. Taking all of this into account, I feel like the technical contribution is extremely limited.\n\nIn addition, I do not see any significant insight into the convergence of FedAvg. The impact of client sampling has been studied before and optimal sampling strategies were proposed by Chen et al. (2020), and other works, for instance (Fraboni et al., 2021), have studied more forms of unbiased sampling. This work gives a bit more detail into how it all affects training but it all seems trivial, but without new improved strategies for sampling, it is hard to see the value of this study.\n\n### Minor concerns:\nI think it's a bit confusing to denote the constant in Assumption 3 as $\\kappa$ since $\\kappa$ is often used to denote the problem conditioning.\n\n### Typos:\n\"on a fix amount\" -> \"on a fixed amount\"  \n\"dependence of FL convergence from the variance\" -> \"dependence of FL convergence on the variance\"  \n\"through a fixed amount K of SGD initialized\" -> \"through a fixed amount K of SGD steps initialized\"  \n\"needs to be collinear with the global direction\" -> \"needs to be correlated with the global direction\"  \n\"Our work is structured as follow.\" -> \"Our work is structured as follows.\"  \nAssumption 3: \"There exists constants\" -> \"There exist constants\"  \nThe right-hand side of Equation (63) misses square brackets after \"Cov\".", "summary_of_the_paper": "This paper considers the problem of Federated Learning (FL) with a random selection of clients in order to minimize $\\sum_{i} p_i \\mathcal{L}_i(\\theta)$, where $\\mathcal{L}_i$ is the loss function of client $i$ and $p_i$ is its weight, which is often proportional to the dataset size on client $i$. The authors study the impact of assigning weights $\\omega_i(S_t)$ and probabilities $P(i\\in S_t)$ to client $i$ when averaging the result of running SGD for $K$ steps locally on each sampled device. The authors first prove a decomposition bound (Theorem 1), which establishes a simple recursion for the distance to the solution. As far as I can see, this result is never used to establish a convergence rate. In addition to Theorem 1, under smoothness, bounded variance, and bounded dissimilarity assumptions, the authors study convergence rates of unbiased client sampling in the nonconvex regime (Theorem 2). As a side contribution, the authors also consider using different stepsizes $\\eta_l, \\eta_g$ locally and globally.", "summary_of_the_review": "1. I see very little novelty in this work. Most results follow by combining some simple identities for expectations of random variables with convergence results for Local SGD from prior literature (Wang et al., 2020a), (Li et al., 2020c). Adding a global stepsize also does not change almost anything in the proofs.  \n2. The results do not have a clear significance. While Federated Learning is an important and challenging problem, and client sampling may play a big role in its efficient use in practice, the results in this paper provide us with little new insight.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "1rp51ZfTeO2", "reviewer": "Reviewer_mcBg", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1. The main theorem 1 (decomposition theorem) is somewhat too microscopic (as it only studies one round) and more like a direct corollary of the equation (3), and is independent with the other procedure in FL (e.g., local optimization steps). Hence, I would recommend calling theorem 1 \"decomposition theorem/lemma for client sampling\", rather than the \"decomposition theorem for the convergence of FL\" \n\n2. The decomposition in theorem 1 is somewhat incomplete as it involves $\\theta_i^{t+1}$ outside $Q(\\theta^t)$. This makes it hard to interpret the trade-off of the three terms in $Q(\\theta^t)$. \n\n3. The paper argues that MD sampling should be used as default case, while uniform sampling is superior only in the special case when clients have the same amount of data. I cannot find a theoretical justification of the first part of this sentence. It is only shown in corollary 1 that Uniform is better than MD in certain cases, but not the reverse side. From Theorem 1, it is clear to me how to argue when MD can be better than Uniform Sampling, as the third term in $Q(\\theta^t)$ is always larger in MD.\n4. The convergence theorem 2 only studies the regime with sufficiently small local ste\np size $\\eta_l$, which effectively reduces to the mini-batch regime. Is it possible to establish  the convergence without assuming sufficiently small local step size $\\eta_l$?\n\nMinor comment and suggestions:\n\n1. \"The decomposition theorem also provides a necessary condition for an optimization step to improve the current global model: the expected client contribution needs to be collinear with the global direction of the optimum\". This claim does not sound accurate. Collinear is neither sufficient or necessary for making progress. The only necessary condition we can read from (7) is the negative inner product. Also, an optimization algorithm does not need to always make progress in distance to optimum every step to \"improve\" the model.\n2. Table 1: the notation $\\alpha$ appears much earlier than it was first referenced in the main text (before §3). For better reading experience, it would be great if the authors can hint the semantic of $\\alpha$ in the caption of tale 1.", "summary_of_the_paper": "This work studies the effect of client sampling in the convergence of Federated Learning. This work clearly formulates the setup of client sampling and studies the effect of client sampling to FL progress.", "summary_of_the_review": "Overall I appreciate author's effort in formulating and understanding the nuances in client sampling. My main concern of this work lies in the significance of the results as well as the interpretation. As this time I think the paper is marginally below the acceptance threshold, but I am happy to re-evaluate the paper if the authors can address my concerns.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Dear authors,

I have carefully read the reviews, rebuttals, and the subsequent discussion. Most reviews provide high quality feedback, and the reviewers' combined opinion is strongly oriented towards recommending rejection. I have to concur with this recommendation. While essentially all reviewers agreed that the paper is well written, they also raised several key concerns. I will reiterate (and further elaborate) on some of them here:

1) I do not agree with the authors' claim that there is a significant difference between client sampling in FL and data sampling in SGD in terms of the underlying mathematics; at least not in the present form. The mathematical formulation of both problems is the same. While in SGD it is possible to access local information and construct more powerful sampling strategies using this information, it is also possible to forgo using this information and propose simpler data-agnostic strategies. Such strategies have been studies in the SGD literature before. I recommend the literature on *arbitrary sampling* pioneered by Richtarik and Takac ("Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function", Mathematical Programming, 2014) in the context of randomized coordinate descent. The same sampling approach was later adopted for SGD. The paper by Csiba and Richtarik (Importance sampling for minibatches, JMLR 2018) suggested by one of the reviewers is relevant here as it adopts the arbitrary sampling approach to (variance reduced) SGD. Such an arbitrary sampling paradigm is more general than the unbiased sampling strategy you study here (indeed, arbitrary sampling includes also biased samplings). The work of Chen et al mentioned by a reviewer is also more relevant than you appreciate. This work also mentions a couple decomposition statements. They work with the arbitrary sampling framework in the FL setting - and this seems more general than your framework since it includes biased samplings as well. Note that they then proceed to compute the optimal sampling out of all samplings, while you do not attempt to theoretically capture what samplings are best. This prior works thus addresses a similar problem, and goes deeper in this aspect. Also, the parameters $v_i$ in their Lemma 1 are simply just statistics of the sampling - and are unrelated to the data. Also, Lipschitz smoothness constant of the aggregate loss over all local data samples is not hard to estimate, and is needed anyway to set the stepsize correctly. So, your comments about the unavailability of these quantities in the FL setting seem incorrect.

2) Theorem 1 is indeed just a simple calculation / observation rather than a result. I agree with the reviewer who said that the value of this simple observation, without a deeper study of its consequences, and an explanation of how the consequences lead to new results that are in some sense interesting, is quite limited. As mentioned by one reviewer, sophisticated methods are often non-monotonic: they do *not* attempt to greedily reduce some simple potential (e.g., distance to the minimizer) as such a strategy may be suboptimal from a total convergence point of view. This observation by the reviewer seems to have been misunderstood by the authors. This limits the impact of Theorem 1 as Theorem 1 assumes that one is interested in a greedy method.

3) The bounded variance and bounded dissimilarity assumption *are* strong. The suggestion by one of the reviewers to consider a work on more accurate ways of modeling stochastic gradients (Khaled et al) was appropriate. I suggest the authors read the paper to see detailed reasoning explaining why the types of assumptions you make in this paper are problematic. The fact that some other papers use such problematic assumptions, even if they are well known, is not evidence that these assumptions are not problematic. It is merely evidence that many papers share the same issue. I also have to oppose the authors' view that non-peer-reviewed work should not be brought up. In my view, this is a deeply problematic and unscientific attitude to research that is available online. Peer review does not imply correctness, and vice versa. 

4) Experimental comparison with any other methods is missing. Why do you not compare with the optimal sampling strategy of Chen et al, for example? Does your framework suggest a better strategy in some sense? If yes, show it. If no, then in what sense are your sampling strategies interesting? In any case, all have been considered in the arbitrary sampling framework before as far as I can see.

5) There are more issues with have been identified by the reviewers. I strongly recommend the authors to take all of them seriously in their revision.

In summary, this is a solid paper. However, it has some serious issues and for this reason I cannot recommend it for acceptance. Having said that, I thank the authors for their submission and wish them best of luck in future research with this project.

Area Chair
Decision: Reject