Year: 2021

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 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.

heading: 1 INTRODUCTION
text: Federated Learning (FL) has gained popularity in the last years as it enables different clients to jointly learn a global model without sharing their respective data. Among the different FL approaches, 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 Stochastic Gradient Descent (SGD) steps before sending it back to the server. The new global model is then created as the weighted average of 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 et al., 2020a; 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 a 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 a random subset of m clients at each FL round. It has been subsequently shown that, to ensure the convergence of FL to 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 & Mahdavi, 2019; Li et al., 2020b; Wang & Joshi, 2018; Fraboni et al., 2021). Nevertheless, when clients have identical amount of data, clients can also be sampled uniformly without replacement (Li et 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).
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-investigated. In (Fraboni et al., 2021), MD sampling was extended to account for collections of sampling distributions with varying 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 experimental improvement justified by lower variance of the clients’ aggregation weights. Another study investigated the convergence guarantees of FedAvg under different sampling schemes, through a penalized optimization framework (Li et al., 2020c). These studies reflect the ongoing interest and need for a theoretical framework to elucidate the impact of client sampling on FL convergence.
The main contribution of this work consists in deriving a decomposition theorem for the convergence of FL, 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, we 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 a given convergence step, thus enabling accurate quantification of the role of client sampling and heterogeneity in FL. From a practical point of view, we establish both theoretically and experimentally that client sampling schemes based on aggregation weights with sum different than 1 are less efficient. We also prove that MD sampling is 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 2, we provide formal definitions for FL, unbiased client sampling, and for the server aggregation scheme. In Section 3, we introduce our decomposition theorem (Theorem 1) 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 on the convergence speed, and conclude by recommending Uniform sampling for FL applications with identical client ratio, and MD sampling otherwise.

heading: 2 BACKGROUND
text: Before investigating in 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 formalization for unbiased client sampling.

heading: 2.1 AGGREGATING CLIENTS LOCAL UPDATES
text: In FL, we consider a set I of n clients each respectively owning a dataset Di composed of ni samples. FL aims at optimizing the average of each clients local loss function weighted by pi such that ∑n i=1 pi = 1, i.e.
L(θ) = n∑
i=1
piLi(θ), (1)
where θ represents the model parameters. The weight pi can be interpreted as the importance given by the server to client i in the federated optimization problem. While any combination of {pi} is possible, we note that in practice, either (a) every device has equal importance, i.e. pi = 1/n, or (b) every data point is equally important, i.e. pi = ni/M with M = ∑n i=1 ni. Unless stated otherwise, in the rest of this work, we consider to be in case (b), i.e. ∃i, 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 t, the server sends the current global model parameters θt to the clients. Each client updates the respective model by minimizing the local cost function Li(θ) through a fixed amount K of SGD steps initialized with θt. Subsequently each client returns the updated local parameters θt+1i to the
server. The global model parameters θt+1 at the iteration step t+1 are then estimated as a weighted average:
θt+1 = n∑ i=1 piθ t+1 i . (2)
To alleviate the clients workload and reduce the amount of overall communications, the server often considers m ≤ 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 ηg to better account for the clients update at a given iteration. We denote by ωi(St) the stochastic aggregation weight of client i given the subset of sampled clients St at iteration t . The server aggregation scheme can be written as:
θt+1 = θt + ηg n∑ i=1 ωi(St)(θ t+1 i − θ t). (3)

heading: 2.2 UNBIASED CLIENTS SAMPLING
text: While FedAvg was originally based on the uniform sampling of clients (McMahan et al., 2017), this scheme has been proven to be biased and converge to a suboptimal minima of problem (1) (Wang et al., 2020a; Cho et al., 2020; Li et al., 2020c). This was the motivation for Li et al. (2020c) to introduce the notion of unbiasedness, where clients are considered in expectation subject to their importance pi, according to Definition 1 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;c; Fraboni et al., 2021) are currently among the standard approaches to FL, as opposed to biased approaches, known to over- or under-represent clients and lead to suboptimal convergence properties (McMahan et al., 2017; Nishio & Yonetani, 2019; Jeon et al., 2020; Cho et al., 2020), or to methods requiring additional computation work from clients (Chen et al., 2020a). Definition 1 (Unbiased Sampling). A client sampling scheme is said unbiased if the expected value of the client aggregation is equal to the global deterministic aggregation obtained when considering all the clients, i.e.
ESt
[ n∑
i=1
wi(St)θ t i
] :=
n∑ i=1 piθ t i , (4)
where wj(St) is the aggregation weight of client j for subset of clients St.
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 l1, ..., lm to be the m iid sampled clients from a Multinomial Distribution with support on {1, ...,m} satisfying P(lk = i) = pi (Wang et al., 2020a; Li et al., 2020a;c; Haddadpour & Mahdavi, 2019; Li et al., 2020b; Wang & Joshi, 2018; Fraboni et al., 2021). By definition, we have ∑n i=1 pi = 1, and the clients aggregation weights take the form:
ωi(St) = 1
m m∑ k=1 I(lk = i). (5)
Uniform sampling. This scheme samples m clients uniformly without replacement. Since in this case a client is sampled with probability p({i ∈ St}) = m/n, the requirement of Definition 1 implies:
ωi(St) = I(i ∈ St) n
m pi. (6)
Table 1: Synthesis of statistical properties of different sampling schemes.
Sampling Var [ωi(St)] α Var [
∑n
i=1 ωi(St)] Full participation = 0 = 0 = 0 MD = − 1mp 2 i + 1 mpi = 1/m = 0
Uniform = ( n m − 1 ) p2i = n−m m(n−1) = n−m m(n−1) [n ∑n i=1 p 2 i − 1]
We note that this formulation for Uniform sampling is a generalization of the scheme previously used for FL applications with identical client importance, i.e. pi = 1/n (Karimireddy et al., 2020; Li et al., 2020c; Reddi et al., 2021; Rizk et al., 2020). We note that Var [ ∑n i=1 ωi(St)] = 0 if and
only if pi = 1/n for all the clients as, indeed, ∑n i=1 ωi(St) = m n m 1 n = 1
With reference to equation (3), we note that by setting ηg = 1, and by imposing the condition ∀St, ∑n i=1 ωi(St) = 1, we retrieve equation (2). This condition is 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 sampling is such that there exists an α such that ∀i ̸= j, Cov [ωi(St), ωj(St)] = −αpipj . We provide in Table 1 the derivation of α and the resulting covariance for these two schemes with calculus details in Appendix A. Furthermore, this property is common to a variety of sampling schemes, for example based on Binomial or Poisson Binomial distributions (detailed derivations can be found in Appendix A). Following this consideration, in addition to Definition 1, in the rest of this work we assume the additional requirement for a client sampling scheme to satisfy ∃α ≥ 0, ∀i ̸= j, Cov [ωi(St), ωj(St)] = −αpipj .

heading: 3 CONVERGENCE GUARANTEES
text: Based on the assumptions introduced in Section 2, in what follows we elaborate a new theory relating the convergence of FL to the statistical properties of client sampling schemes. In particular, Decomposition Theorem 1 describes the impact of client sampling on a single optimization step, while Theorem 2 quantifies the asymptotic relationship between client sampling and FL convergence.

heading: 3.1 DECOMPOSITION THEOREM
text: Assumption 1 (Unbiased Gradient and Bounded Variance). Every client stochastic gradient gi(x|B) of a model x evaluated on batch B is an unbiased estimator of the local gradient. We thus have EB [ξi(B)] = 0 and 0 ≤ EB [ ∥ξi(B)∥2 ] ≤ σ2, with ξi(B) = gi(x|B)−∇Li(x).
the following Decomposition Theorem highlights the impact of client sampling on a single FL optimization 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 1 (Decomposition Theorem). We consider yti,k the local model of client i after k SGD steps initialized on model θt. We consider the vector ξti of the gradient noises ξ t i,k = [gi(y t i,k) −
∇Li(yti,k)] satisfying Assumption 1, and ∆ti = ∑K−1
k=0 ∇Li(yti,k). We consider a client sampling scheme satisfying Definition 1, and such that Cov [ωi(St), ωj(St)] = −αpipj . For any given optimization round based on equation (3), the following equation holds:
Et [∥∥θt+1 − θ∗∥∥2] = ∥∥θt − θ∗∥∥2 − 2ηg ⟨ n∑
i=1
pi Et [ θt+1i − θ t ] ,θ∗ − θt⟩︸ ︷︷ ︸
Direction drift
+η2gη 2 l Q(θ t) (7)
with
Q(θt) = n∑ i=1 νi Et [∥∥ξti∥∥2]︸ ︷︷ ︸
Gradient Estimator Noise =Ni(θ t)
+ n∑ i=1 γi Et [∥∥∆ti∥∥2]︸ ︷︷ ︸
Local Model Drift =Li(θ t)
+(1− α)Et ∥∥∥∥∥ n∑
i=1
pi∆ t i ∥∥∥∥∥ 2 
︸ ︷︷ ︸ Global Model Drift =G({pi},θt)
, (8)
where θ∗ is the optimum of the optimization problem (1), νi = [ Var [ωi(St)] + p 2 i ] , γi = Var [ωi(St)] + αp 2 i , and Et [X] is the expected value of X conditioned on θt.
The Decomposition Theorem (proof in Appendix B) shows that FL convergence is impacted by a client sampling through the quantities Var [ωi(St)] and α, which both depend on the clients aggregation weights. These variables modulate three quantities, Ni(θt), Li(θt) and G({pi},θt), representing respectively the stochastic gradient estimator noise, and the local and global model drift from the current initialization, which are independent from client sampling. In particular, the quality of clients data impacts the convergence speed through Ni(θt). The Decomposition Theorem also provides a necessary condition for an optimization step to improve the current global model: the expected client contribution Et [∑n i=1 pi [ θt+1i − θt ]] needs to be collinear with the global direction of the optimum θ∗ − θt. To further clarify the influence of client sampling on the FL convergence we introduce the following property (proof in Appendix A.1) introducing the quantity Var [ ∑n i=1 ωi(St)], the variance of the sum of the aggregation weights, and showing its relationship with the variance of the clients aggregation weights Var [ωi(St)], and with the covariance parameter α. Property 1. For any client sampling, we have 0 ≤ α ≤ 1 and
Var
[ n∑
i=1
ωi(St)
] =
n∑ i=1 Var [ωi(St)]− α
[ 1−
n∑ i=1 p2i
] . (9)
Since 0 ≤ α ≤ 1, the global model drift G({pi},θt) contributes positively to equation (8), and the term Q(θt) is always positive. This means that Q(θt) is not negligible, and an appropriate sampling scheme should be defined such that Q(θt) is minimized. We note that the impact of a client sampling can always be mitigated by considering a smaller local learning rate ηl. Indeed, the client drift is proportional to ηl while Q(θt) is proportional to η2l .

heading: 3.2 ASYMPTOTIC FL CONVERGENCE WITH RESPECT TO CLIENT SAMPLING
text: To prove FL convergence with client sampling, our work relies on 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, ∀i ∈ {1, ..., n}, ∥∇Li(x)−∇Li(y)∥ ≤ L ∥x− y∥. Assumption 3 (Bounded Dissimilarity ). There exist constants β2 ≥ 1 and κ2 ≥ 0 such that for every combination of positive weights {wi} such that ∑n i=1 wi = 1, we have ∑n i=1 wi ∥∇Li(x)∥
2 ≤ β2 ∥∇L(x)∥2 + κ2. If all the local loss functions are identical, then we have β2 = 1 and κ2 = 0.
We formalize in the following theorem the relationship between the statistical properties of the client sampling scheme and the asymptotic convergence of FL (proof in Appendix C). Theorem 2 (FL convergence). Let us consider a client sampling scheme satisfying Definition 1 and such that for i ̸= j, Cov [ωi(St), ωj(St)] = −αpipj ≤ 0. Under Assumptions 1 to 3, and with sufficiently small local step size ηl, the following convergence bound holds:
1
T T−1∑ t=0 E [∥∥∇L(θt)∥∥2] ≤ O( 1 ηgηlKT ) +O ( η2l (K − 1)σ2 ) +O ( η2l K(K − 1)κ2 ) +O ( ηgηl [ Σ+
n∑ i=1 p2i
] σ2 ) +O ( ηgηlγ [ (K − 1)σ2 +Kκ2 ]) , (10)
where K is the number of local SGD, and
Σ = n∑ i=1 Var [ωi(St)] and γ = n∑ i=1 Var [ωi(St)] + α n∑ i=1 p2i . (11)
We first observe that any client sampling scheme satisfying the assumptions of Theorem 2 converges to its optimum. Through Σ and γ, equation (10) shows that our bound is proportional to the clients aggregation weights through the quantities Var [ωi(St)] and α, 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 2 does not require the sum of the weights ωi(St) to be equal to 1. Yet, for client sampling satisfying Var [ ∑n i=1 ωi(St)] = 0, we get α ∝ Σ. Hence, choosing 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 2 extends the work of Wang et al. (2020a) where, in addition of considering FedAvg with clients performing K vanilla SGD, we include a server learning rate ηg and integrate client sampling (equation (3)). With full client participation (Σ = γ = 0) and ηg = 1, we retrieve the convergence guarantees of Wang et al. (2020a). Furthermore, our theoretical framework can be applied to any client sampling satisfying the conditions of Theorem 2. In turn, Theorem 2 holds for full client participation, MD sampling, Uniform sampling, as well as for the other client sampling schemes detailed in Appendix A. Finally, the proof of Theorem 2 is general enough to account for FL regularization methods (Li et al., 2020a; 2019; Acar et al., 2021), other SGD solvers (Kingma & Ba, 2015; Ward et al., 2019; Li & Orabona, 2019), and/or gradient compression/quantization (Reisizadeh et al., 2020; Basu et al., 2019; Wang et al., 2018). For all these applications, the conclusions drawn for client samplings satisfying the assumptions of Theorem 2 still hold.

heading: 3.3 APPLICATION TO CURRENT CLIENT SAMPLING SCHEMES
text: MD sampling. When using Table 1 to compute Σ and γ close-form we obtain:
ΣMD = 1
m
[ 1−
n∑ i=1 p2i
] and γMD = 1
m , (12)
where we notice that ΣMD ≤ 1m = γMD. Therefore, one can obtain looser convergence guarantees than the ones of Theorem 2, independently from the amount of participating clients n and set of clients importance {pi}, while being inversely proportional to the amount of sampled clients m. The resulting bound shows that FL with MD sampling converges to its optimum for any FL application.
Uniform sampling. Contrarily to 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 1 to compute Σ and γ close-form we obtain
ΣU = [ n m − 1 ] n∑
i=1
p2i and γU = [ 1 + 1
n− 1 ] [ n m − 1 ] n∑
i=1
p2i , (13)
where we notice that γU = [ 1 + 1n−1 ] ΣU . Considering that ∑n i=1 p 2 i ≤ 1, we have ΣU ≤ nm − 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 ∑n i=1 p 2 i ≤ 1 accounts for every possible scenario of client importance {pi}, including the very heterogeneous ones. In the special case where pi = 1/n, we have ∑n i=1 p 2 i = 1/n, such that ΣU is inversely proportional to both n and m. Such FL applications converge to the optimum of equation (1) for any configuration of n, {pi} and m. Moreover, the comparison between the quantities Σ and γ for MD and Uniform sampling shows that Uniform sampling outperforms MD sampling when pi = 1/n. More generally, Corollary 1 provides 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 ΣU ≤ ΣMD, and γU ≤ γMD which is equivalent to
n∑ i=1 p2i ≤ 1 n−m+ 1 . (14)
Corollary 1 can be related to Var [ ∑n
i=1 ωi(St)], 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 pi = 1/n for all the clients.
A last point of interest for the comparison between MD and Uniform sampling concerns the respective time complexity for selecting clients. Sampling with a Multinomial Distribution has time complexity O(n + m log(n)), where O(n) comes from building the probability density function to sample clients indices (Tang, 2019). This makes MD sampling difficult to compute or even intractable for large cohorts of clients. On the contrary sampling m elements without replacement from n states is a reservoir sampling problem and takes time complexity O(m(1 + log(n/m))(Li, 1994). In practice, clients either receive identical importance (pi = 1/n) or an importance proportional to their data ratio, for which we may assume computation pi = O( 1n ). As a result, for important amount n 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. (2021) 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.

heading: 4 EXPERIMENTS
text: In this section we provide an experimental demonstration of the two main theorems of Section 3, by quantifying the correctness of Decomposition Theorem 1, and by verifying the convergence properties identified in Theorem 2.

heading: 4.1 SYNTHETIC EXPERIMENT
text: 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 a single FL optimization step.
We consider n = 10 clients jointly learning a model with m = 5 of them sampled by the server at each optimization step. Each client local loss function is Li(θ) = 12 ∥θ − θ ∗ i ∥
2 with optimum θ∗i ∼ N(0d, Id), where d = 20 is the number of parameters in the model. The optimum of the global loss function of equation (1) is θ∗ = ∑n i=1 piθ ∗ i . We consider varying p1, the importance of client 1, while giving identical importance to the remaining clients, i.e.
p1 = r and pi = (1− r)/(n− 1), i ̸= 1. (15)
By varying r between 0 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 a single FL optimization step initialized with a global model θ0 ∼ N(0d, Id). We compare the average distance of 1000 simulations obtained after a single FL round to the theoretical one provided by the Decomposition Theorem 1 (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 θ∗i = θ ∗ 1 , and a non-iid one, where every client local model is drawn independently.
The theoretical expected distance ∥∥θ1 − θ∗∥∥2 is plotted for iid and non-iid case in Figure 1a and 1b. The corresponding experimental distance resulting from the 1000 simulations is shown in Figure 1c and 1d. We note that there is a close match between theoretical and experimental results, demonstrating the validity of Decomposition Theorem 1. Figure 1 highlights the following properties:
Iid case (Figure 1a and 1c). In the iid setting the expected difference obtained with MD sampling is equivalent to the one obtained when all the clients are considered (Full). This demonstrates that in the iid case the covariance parameter α does not affect FL convergence (Section 3). Moreover, Uniform sampling leads to generally poor convergence results, thus confirming that the variance of
the sum of the clients stochastic weights, VarSt [ ∑n
i=1 ωi(St)], negatively impacts FL convergence. More precisely, the only case where Uniform sampling is comparable to the other schemes is when p1 = 0.1, which indeed corresponds to the special scenario in which pi = 1/n, and thus the variance associated to Uniform sampling is zero (cfr. Table 1).
Non iid case (Figure 1b and 1d). The conclusions drawn for the iid case still hold when the local optima are not identical across clients. Moreover, we can now appreciate the impact of the covariance parameter α on the convergence speed. Independently from the choice for p1, the minimum distance is obtained when considering all the clients. In this case we have both α = 0 and VarSt [ ∑n i=1 ωi(St)] = 0. When pi = 1/n = 0.1, both MD and Uniform sampling have null vari-
ance VarSt [ ∑n
i=1 ωi(St)]. In this case, the negative impact of the covariance through the parameter α penalizes MD sampling. The penalization of the covariance term on MD sampling is still relevant when p1 is close to the critical value of 0.1. Finally, for large enough values of p1, the variance term outweights the effect of the covariance, making MD better than Uniform sampling.
Diverging Uniform sampling. Consistently with Figure 1, in Appendix E we provide further examples showing that Uniform sampling can diverge in simple FL setting with heterogeneous client importance. We still consider n = 10 clients and sample m = 5 of them with p1 = r = 0.9. When sampled, clients perform K = 1 SGD to show that the divergence does not come from the clients local work K. Figure 4 of Appendix E shows that for this scenario, FL with MD sampling converges while FL with Uniform sampling diverges both for iid and non-iid client data distribution.

heading: 4.2 EXPERIMENT ON REAL DATA
text: We study a LSTM model for next character prediction on the dataset of The complete Works of William Shakespeare (McMahan et al., 2017; Caldas et al., 2018). We use a 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 a learned 8-dimensional space and outputs one character per training sample after 2 LSTM layers and a fully connected one.
When selected, a client performs K = 50 SGD steps on batches of size B = 64 with local learning rate ηl = 1.5. The server considers the clients local work with ηg = 1. We consider n ∈ {10, 20, 40, 80} clients, and sample half of them at each FL optimization step. While for sake of interpretability we do not apply a decay to local and global learning rates, we note that our theory remains unchanged even in presence of a learning rate decay. In practice, for dataset with important heterogeneity, considering ηg < 1 can speed-up FL with a more stable convergence.
Clients have identical importance [pi = 1/n]. We note that Uniform sampling consistently outperforms 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 2a). This result confirms the derivations of Section 3.
Clients importance depends on the respective data ratio [pi = ni/M ]. In this experimental scenario the aggregation weights for Uniform sampling do not always sum to 1, thus leading to the slow-down of FL convergence. Hence, we see in Figure 2b that MD always outperforms Uniform sampling. This experiment shows that the impact on FL convergence of the variance of the sum of the stochastic aggregation weights is more relevant than the one due to the covariance parameter α. 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, e.g. pi = 1/10± 0.13 for n = 10 and pi = 1/80± 0.017 for n = 80. We thus conclude that the difference between the effects of MD and Uniform sampling is mitigated with a large number of participating clients (Figure 2b).
Additional experiments on Shakespeare are provided in Appendix E. We show the influence of the amount of sampled clients m (Figure 6) and amount of local work K (Figure 8) on the convergence speed of MD and Uniform sampling.
Finally, additional experiments on CIFAR10 (Krizhevsky, 2009) are provided in Appendix E, where we replicate the experimental scenario previously proposed in Fraboni et al. (2021). In these applications, 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.

heading: 5 CONCLUSION
text: In this work, we derive a novel Decomposition Theorem demonstrating the impact on FL convergence speed of any unbiased client sampling scheme following the assumptions of Section 2. Moreover, Theorem 2 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 α. To the best of our 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 experimental standpoints. We established that when clients have approximately identical importance, i.e pi = 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 general 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 be 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 on the global optimization objective, further extensions may focus on the analysis of the impact of clients selection method on individual users’ performance, especially in presence of heterogeneity.

heading: ETHICS STATEMENT
text: 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, an 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.

heading: REPRODUCIBILITY STATEMENT
text: Every proposed theoretical result is carefully analyzed in Section 3 and proven in Appendix. Aggregation weight calculus can be found in Appendix A, Theorem 1 can be found in Appendix B, and Theorem 2 can be found in Appendix C.
The settings of the different experiments are specified in the paper and the code is provided. Furthermore, we use public datasets without any preprocessing.

heading: A CLIENTS SAMPLING SCHEMES CALCULUS
text: In this section, we calculate for MD, Uniform, Poisson, and Binomial sampling the respective aggregation weight variance Var [ωi(St)], the covariance parameter α such that Cov [ωi(St)), ωj(St)] = −αpipj , and the variance of the sum of weights Var [ ∑n i=1 ωi(St)]. We also propose statistics for the parameter N , i.e. the amount of clients the server communicates with at an iteration:
N = n∑ i=1 I(i ∈ St). (16)

heading: A.1 PROOF OF PROPERTY 1
text: Proof. Covariance parameter
Cov [ωi(St), ωj(St)] = E [ωi(St)ωj(St)]− pipj ≥ −pipj (17)

heading: Aggregation Weights Sum
text: Var
[ n∑
i=1
ωi(St)
] =
n∑ i=1 Var [ωi(St)] + ∑ i,j ̸=i Cov [ωi(St), ωj(St)] (18)
= n∑ i=1 Var [ωi(St)]− α ∑ i,j ̸=i pipj (19)
= n∑ i=1 [Var [ωi(St)]− αpi(1− pi)] (20)
= n∑ i=1 Var [ωi(St)]− α
[ 1−
n∑ i=1 p2i
] , (21)
where we use ∑n
i=1 pi = 1, equation (1), for the third and fourth equality. Using equation (20), we see that we can also get the following equality based on Decomposition Theorem 1:
Var
[ n∑
i=1
ωi(St)
] =
n∑ i=1 γi − α. (22)
Re-expressing α. Using equation (20), we get
Var
[ n∑
i=1
ωi(St)
] =
n∑ i=1 Var [ωi(St)]− α
[ 1−
n∑ i=1 p2i
] , (23)
which, with reordering, gives
α =
∑n i=1 Var [ωi(St)]−Var [ ∑n i=1 ωi(St)]
1− ∑n
i=1 p 2 i
. (24)

heading: A.2 NO SAMPLING SCHEME
text: When every client participate at an optimization round, we have ωi(St) = pi which gives VarSt [ωi(St)] = 0, α = 0, and N = n.

heading: A.3 MD SAMPLING
text: We recall equation (5),
ωi(St) = 1
m m∑ k=1 I(lk = i), (25)
which gives
E [ωi(St)ωj(St)] = 1
m2 ∑ k,l ̸=k E [I(lk = i)I(ll = j)] + 1 m2 m∑ k=1 E [I(lk = i)I(lk = j)] (26)
= 1
m2 ∑ k,l ̸=k pipj + 1 m2 m∑ k=1 E [I(lk = i)I(lk = j)] (27)
= m− 1 m pipj + 1 m E [I(l = i)I(l = j)] (28)
Variance(i = j). We get E [I(l = i)I(l = j)] = E [I(l = i)] = pi, which gives:
Var [ωi(St)] = − 1
m p2i +
1 m pi (29)
Covariance(i ̸= j). We get E [I(l = i)I(l = j)] = 0, which gives:
Cov [ωi(St), ωj(St)] = − 1
m pipj , (30)
and by definition we get
α = 1
m (31)
Aggregation Weights Sum. Using equation (29)) and (31) with Property 1, we get
Var
[ n∑
i=1
ωi(St)
] = 0. (32)
Amount of clients. Considering that p(i ∈ St) = 1− p(i /∈ St) = 1− (1− pi)m, we get:
E [N ] = n∑
i=1
P(i ∈ St) = n− n∑
i=1
(1− pi)m ≤ m (33)

heading: A.4 SAMPLING CLIENTS UNIFORMLY WITHOUT REPLACEMENT
text: We recall equation (6),
ωi(St) = I(i ∈ St) n
m pi. (34)
Variance. We first calculate the probability for a client to be sampled, i.e.
P(i ∈ St) = 1− P(i /∈ St) = 1− n− 1 n ... n−m n−m+ 1 = 1− n−m n = m n . (35)
Using equation (35), we have
VarSt [ωi(St)] = [ n m pi ]2 Var [I(i ∈ St)] = n2 m2 m n (1− m n )p2i = ( n m − 1)p2i (36)
Covariance. We have
P({i, j} ∈ St) = P(i ∈ St) + P(j ∈ St)− P(i ∪ j ∈ St) (37) = P(i ∈ St) + P(j ∈ St)− (1− P({i, j} /∈ St)), (38)
and
P({i, j} /∈ St) = n− 2 n ... n−m− 1 n−m+ 1 = (n−m)(n−m− 1) n(n− 1) . (39)
Substituting equation (35) and (39) in equation (38) gives
P({i, j} ∈ St) = 2 m n − 1 + (n−m)(n−m− 1) n(n− 1) (40)
= 1
n(n− 1) [2m(n− 1)− n(n− 1) + (n−m)(n−m− 1)] (41)
= m(m− 1) n(n− 1) . (42)
Hence, we can express the aggregation weights covariance as
Cov [ωi(St), ωj(St)] = n2 m2 m(m− 1) n(n− 1) pjpk − pjpk, (43)
which gives
α = n−m
m(n− 1) . (44)
Aggregation Weights Sum. Combining equation (36) and (44) with Property 1 gives
Var
[ n∑
i=1
ωi(St)
] =
n∑ i=1 [ n m − 1 ] p2i − n−m m(n− 1) n∑ i=1 pi(1− pi) (45)
= n−m
m(n− 1)
[ n
n∑ i=1 p2i − 1
] , (46)
where we retrieve Var [ ∑n i=1 ωi(St)] = 0 for identical client importance, i.e. ∑n i=1 p 2 i = 1 n .
Amount of Clients. N = m.

heading: A.5 POISSON BINOMIAL DISTRIBUTION
text: Clients are sampled according to a Bernoulli with a probability proportional to their importance pi, i.e.
ωi(St) = 1
m B(mpi). (47)
Hence, only m ≥ p−1max can be sampled and we retrieve E [ωi(St)] = 1mmpi = pi. Variance.
VarSt [ωi(St)] = 1
m2 mpi(1−mpi) =
1 m pi(1−mpi) (48)
Covariance. Due to the independence of each stochastic weight, we also get:
Cov [ωi(St), ωj(St)] = 0 (49)
Aggregation Weights Sum. Using Property 1 we obtain
Var
[ n∑
i=1
ωi(St)
] = 1
m − n∑ i=1 p2i . (50)
Amount of Clients.
E [N ] = m and Var [N ] = m−m2 n∑
i=1
p2i . (51)

heading: A.6 BINOMIAL DISTRIBUTION
text: Clients are sampled according to a Bernoulli with identical sampling probability, i.e.
ωi(St) = n
m B(
m n )pi. (52)
Hence, we retrieve E [ωi(St)] = nm m n pi = pi.
Variance.
VarSt [ωi(St)] = n2 m2 m n (1− m n )p2i = n−m m p2i . (53)
Covariance. Due to the independence of each stochastic weight, we have:
Cov [ωi(St), ωj(St)] = 0. (54)
Aggregation Weights Sum. Using Property 1 gives
Var
[ n∑
i=1
ωi(St)
] =
n−m m n∑ i=1 p2i . (55)
Amount of Clients.
E [N ] = m and Var [N ] = m− m 2
n . (56)

heading: A.7 CLUSTERED SAMPLING
text: Clustered sampling (Fraboni et al., 2021) is a generalization of MD sampling where instead of sampling m clients from the same distributions, m clients are sampled from m different distributions {Wk}mk=1 each of them privileging a different subset of clients. We denote by rk,i the probability of client i to be sampled in distribution k. To satisfy Definition 1, the original work (Fraboni et al., 2021) provides the conditions:
∀k ∈ {1, ...,m}, n∑
i=1
rk,i = 1 and ∀i ∈ {1, ..., n}, m∑
k=1
rk,i = mpi. (57)
The clients aggregation weights remain identical to the one of MD sampling, i.e.
ωi(SCl) = 1
m K∑ k=1 I(lk = i), (58)
where I(lk = i) are still independently distributed but not identically.
We have
E [ωi(St)ωj(St)] = 1
m2 ∑ k,l ̸=k E [I(lk = i)I(ll = j)] + 1 m2 m∑ k=1 E [I(lk = i)I(lk = j)] (59)
= 1
m2 ∑ k,l ̸=k rk,irl,j + 1 m2 m∑ k=1 E [I(lk = i)I(lk = j)] (60)
= pipj − 1
m2 m∑ k=1 rk,irk,j + 1 m2 m∑ k=1 E [I(lk = i)I(lk = j)] , (61)
where we retrieve equation (28) when rk,i = pi.
Variance (i = j). We get E [I(lk = i)I(lk = j)] = E [I(lk = i)] = rk,i, which gives:
Var [ωi(SCl)] = 1
m pi −
1
m2 m∑ k=1 r2k,i ≤ Var [ωi(SMD)] , (62)
where the inequality comes from using the Cauchy-Schwartz inequality with equality if and only if all the m distributions are identical, i.e. rk,i = pi.
Covariance (i ̸= j). We get E [I(lk = i)I(lk = j)] = 0, which gives:
Cov [ωi(SCl), ωj(SCl)] = − 1
m2 m∑ k=1 rk,irk,j ≤ Cov [ωi(SMD), ωj(SMD)] , (63)
where the inequality comes from using the Cauchy-Schwartz inequality with equality if and only if all the m distributions are identical, i.e. rk,i = pi.

heading: Aggregation Weights Sum
text: Var
[ n∑
i=1
ωi(SCl)
] = 0. (64)

heading: A.8 OPTIMAL SAMPLING
text: With optimal sampling (Chen et al., 2020b), clients are sampled according to a Bernoulli distribution with probability qi, i.e.
ωi(St) = pi qi B(qi). (65)
Hence, we retrieve E [ωi(St)] = piqi qi = pi.
Variance. VarSt [ωi(St)] =
1− qi qi p2i . (66)
Covariance. Due to the independence of each stochastic weight, we have:
Cov [ωi(St), ωj(St)] = 0. (67)
Aggregation Weights Sum. Using Property 1 gives
Var
[ n∑
i=1
ωi(St)
] =
n∑ i=1 1− qi qi p2i . (68)
Amount of Clients.
E [N ] = n∑
i=1
qi and Var [N ] = n∑
i=1
qi(1− qi). (69)

heading: B DECOMPOSITION THEOREM 1
text: In Table 2, we provide the definition of the different notations used in this work. We also propose in Algorithm 1 the pseudo-code for FedAvg with aggregation scheme (3).
Algorithm 1 Federated Learning based on equation (3) 1: The server sends to the n clients the learning parameters (K, ηl, B). 2: for t ∈ {0, ..., T − 1} do 3: Sample a set of clients St and get their aggregation weights di(t). 4: Send to clients in St the current global model θt. 5: Receive each sampled client contributions ci(t) = θt+1i − θt. 6: Creates the new global model θt+1 = θt + ηg ∑n i=1 di(t)ci(t).
7: end for

heading: B.1 USEFUL LEMMA
text: We first introduce and prove the following useful lemma before introducing the proof of Theorem 1.
Lemma 1. Let us consider n vectors xi, ...,xn and a client sampling satisfying ESt [ωi(St)] = pi and Cov [ωi(St), ωj(St)] = −αpipj . We have:
ESt ∥∥∥∥∥ n∑
i=1
ωi(St)xi ∥∥∥∥∥ 2  = n∑
i=1
γi ∥xi∥2 + (1− α) ∥∥∥∥∥ n∑
i=1
pixi ∥∥∥∥∥ 2 , (70)
where γi = VarSt [ωi(St)] + αp 2 i .

heading: Proof.
text: ESt ∥∥∥∥∥ n∑
i=1
ωi(St)xi ∥∥∥∥∥ 2  = n∑
i=1
ESt [ ωi(St) 2 ] ∥xi∥2 + n∑ i=1 n∑ j=1 j ̸=i ESt [ωi(St)ωj(St)] ⟨xi,xj⟩. (71)
In addition, we have:
ESt [ωi(St)ωj(St)] = Cov [ωi(St), ωj(St)] + pipj = (−α+ 1)pipj , (72) where the last equality comes from the assumption on the client sampling covariance.
We also have: n∑
i=1 n∑ j=1 j ̸=i ⟨pixi, pjxj⟩ = ∥∥∥∥∥ n∑ i=1 pixi ∥∥∥∥∥ 2 − n∑ i=1 p2i ∥xi∥ 2 , (73)
Substituting equation (72) and equation (73) in equation (71) gives:
ESt ∥∥∥∥∥ n∑
i=1
ωi(St)xi ∥∥∥∥∥ 2  = n∑
i=1
[ ESt [ ωi(St) 2 ] − (−α+ 1)p2i ] ∥xi∥2 + (−α+ 1) ∥∥∥∥∥ n∑
i=1
pixi ∥∥∥∥∥ 2 ,
(74) Considering that we have ESt [ ωi(St) 2 ] = Var [ωi(St)] + p 2 i , we have :
ESt [ ωi(St) 2 ] + (α− 1)p2i = VarSt [ωi(St)] + αp2i , (75)
Substituting equation (75) in equation (74) completes the proof.

heading: B.2 PROOF OF THE DECOMPOSITION THEOREM 1

heading: Proof.
text: Et [∥∥θt+1 − θ∗∥∥2] = Et [∥∥(θt+1 − θt) + (θt − θ∗)∥∥2] (76)
= ∥∥θt − θ∗∥∥2 + 2⟨Et [θt+1 − θt] ,θt − θ∗⟩+ Et [∥∥θt+1 − θt∥∥2] , (77)
By construction (equation (3)), we have θt+1 − θt = ηg ∑n i=1 ωi(St)(θ t+1 i − θt). The sampling
scheme follows Definition 1 which gives ESt [ θt+1 − θt ] = ηg ∑n i=1 pi(θ t+1 i − θt). Hence , we get:
Et [∥∥θt+1 − θ∗∥∥2] = ∥∥θt − θ∗∥∥2 + 2ηg⟨ n∑
i=1
pi Et [ θt+1i − θ t ] ,θt − θ∗⟩
+ η2g Et ∥∥∥∥∥ n∑
i=1
ωi(St)(θ t+1 i − θ t) ∥∥∥∥∥ 2 
︸ ︷︷ ︸ =η2l Q(θ t)
. (78)
Using Lemma 1, we express Q(θt) as follow:
η2l Q(θ t) = n∑ i=1 γi Et [∥∥θt+1i − θt∥∥2]+ (1− α)Et ∥∥∥∥∥ n∑ i=1 pi(θ t+1 i − θ t) ∥∥∥∥∥ 2  . (79)
By construction, we have θt+1i − θt = − ∑K−1 k=0 ηlgi(y t i,k). Considering Assumption 1 gives
E [∥∥θt+1i − θt∥∥2] = η2l [E [∥∥ξti∥∥2]+ E [∥∥∆ti∥∥2]] . (80)
Similarly, by using twice Assumption 1 for the global model drift, we have
η2l E ∥∥∥∥∥ n∑
i=1
pid t i ∥∥∥∥∥ 2  = η2l E ∥∥∥∥∥ n∑
i=1
piξ t i ∥∥∥∥∥ 2 + η2l E ∥∥∥∥∥ n∑
i=1
pi∆ t i ∥∥∥∥∥ 2  (81)
= η2l  n∑ i=1 p2i E [∥∥ξti∥∥2]+ E ∥∥∥∥∥ n∑ i=1 pi∆ t i ∥∥∥∥∥ 2  , (82)
where, for the last equality, Assumption 1 gives E [ ⟨ξti , ξtj⟩ ] = E [ξti ] T E [ ξtj ] = 0.
Combining equation (80) with equation (82) gives
Q(θt) = n∑ i=1 [ Var [ωi(St)] + p 2 i ] E [∥∥ξti∥∥2]
+ n∑ i=1 γi E [∥∥∆ti∥∥2]+ (1− α)E ∥∥∥∥∥ n∑ i=1 pi∆ t i ∥∥∥∥∥ 2  . (83)
Substituting equation (83) in equation (78) completes the proof.

heading: B.3 ADAPTATION TO CLUSTERED SAMPLING
text: Instead of Lemma 1 which requires Cov [ωi(St), ωj(St)] = −αpipj , we propose the following Lemma for clustered sampling expressed in function of MD sampling covariance parameter αMD showing that a sufficient condition for MD sampling to perform as well as Clustered sampling is that all xi are identical, or that all the distributions are identical, i.e. rk,i = pi. Lemma 2. Let us consider n vectors xi, ...,xn and a client sampling satisfying ESt [ωi(St)] = pi and Cov [ωi(SCl), ωj(SCl)] = −αpipj . We have:
ESCl ∥∥∥∥∥ n∑
i=1
ωi(SCl)xi ∥∥∥∥∥ 2  ≤ n∑
i=1
γi(MD) ∥xi∥2 + (1− αMD) ∥∥∥∥∥ n∑
i=1
pixi ∥∥∥∥∥ 2 , (84)
where γi(MD) and αMD are the aggregation weights statistics of MD sampling. Equation (84) is an equality if and only if ∑n i=1 rk,ixi = ∑n j=1 rk,jxj .
Proof. Substituting equation (62) in equation (71) gives
ESCl ∥∥∥∥∥ n∑
i=1
ωi(SCl)xi ∥∥∥∥∥ 2  = n∑
i=1
ESCl [ ωi(SCl) 2 ] ∥xi∥2 + n∑ i=1 n∑ j=1 j ̸=i pipj⟨xi,xj⟩
− 1 m2 m∑ k=1 n∑ i=1 n∑ j=1 j ̸=i rk,irk,j⟨xi,xj⟩, (85)
Substituting equation (73) in equation (71) gives:
ESCl ∥∥∥∥∥ n∑
i=1
ωi(SCl)xi ∥∥∥∥∥ 2  = n∑
i=1
ESCl [ ωi(SCl) 2 ] ∥xi∥2 + ∥∥∥∥∥ n∑
i=1
pixi ∥∥∥∥∥ 2 − n∑
i=1
p2i ∥xi∥ 2
− 1 m2 m∑ k=1 ∥∥∥∥∥ n∑ i=1 rk,ixi ∥∥∥∥∥ 2 − n∑ i=1 r2k,i ∥xi∥ 2  . (86)
With rearrangements and using equation (57) we get:
ESCl ∥∥∥∥∥ n∑
i=1
ωi(SCl)xi ∥∥∥∥∥ 2  = n∑
i=1
[ Var [ωi(SCl)] + 1
m2 m∑ k=1 r2k,i
] ∥xi∥2 + ∥∥∥∥∥ n∑
i=1
pixi ∥∥∥∥∥ 2
− 1 m2 m∑ k=1 ∥∥∥∥∥ n∑ i=1 rk,ixi ∥∥∥∥∥ 2 . (87)
Using the expression of clustered sampling variance for the first term (equation (63)), and using Jensen’s inequality on the third term completes the proof. Jensen’s inequality is an equality if and only if ∑n i=1 rk,ixi = ∑n j=1 rk,jxj .

heading: C FL CONVERGENCE
text: Our work is based on the one of Wang et al. (2020a). We use the developed theoretical framework there proposed to prove Theorem 2. The focus of our work (and Theorem 2) is on FedAvg. Yet, the proof developed in this section, similarly to the one of Wang et al. (2020a), expresses ai in such a way they can account for a wide-range of 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 2 in Section C.5, we introduce the notation we use in Section C.1, some useful lemmas in Section C.2 and Theorem 3 generalizing Theorem 2 in Section C.3.

heading: C.1 NOTATIONS
text: We define by yti,k the local model of client i after k SGD steps initialized on θ t, which enables us to also define the normalized stochastic gradients dti and the normalized gradient h t i defined as
dti = 1
ai K−1∑ k=0 ai,kgi(y t i,k) and h t i = 1 ai K−1∑ k=0 ai,k∇Li(yti,k), (88)
where ai,k is an arbitrary scalar applied by the client to its kth gradient, ai = [ai,0, .., ai,K−1]T , and ai = ∥ai∥1. In the special case of FedAvg, we have ai = [1, ..., 1] and in the one of FedProx, we have ai = [(1− µ)K−1, ..., 1] where µ is the FedProx regularization parameter.
With the formalism of equation (88), we can express a client contribution as θt+1i − θt = −ηlaidti and rewrite the server aggregation scheme defined in equation (3) as
θt+1 − θt = −ηgηl n∑
i=1
ωiaid t i, (89)
which in expectation over the set of sampled clients St gives
ESt [ θt+1 − θt ] = −η̃ n∑ i=1 piaid t i (90)
= −η̃
( n∑
i=1
piai ) ︸ ︷︷ ︸
Keff
n∑ i=1 ( piai∑n i=1 piai ) ︸ ︷︷ ︸
wi
dti. (91)
We define the surrogate objective L̃(x) = ∑n i=1 wiLi(x), where ∑n i=1 wi = 1.
In what follows, the norm used for ai can either be L1, ∥·∥1, or L2, ∥·∥2, For other variables, the norm is always the euclidean one and ∥·∥ is used instead of ∥·∥2. Also, regarding the client sampling metrics, for ease of writing, we use ωi instead of ωi(St) due to the independence of the client sampling statistics with respect to the current optimization round.

heading: C.2 USEFUL LEMMAS
text: Lemma 3 (equation (87) in Wang et al. (2020a)). Under Assumptions 1 to 3, we can prove
1
2 n∑ i=1 wi E [∥∥∇Li(θt)− hti∥∥2] ≤ 12 η2l L2σ21−R n∑ i=1 wi ( ∥ai∥22 − a 2 i,−1 ) + Rβ2 2(1−R) E [∥∥∥∇L̃(θt)∥∥∥2]+ Rκ2 2(1−R) , (92)
with R = 2η2l L 2 maxi{∥ai∥1 (∥ai∥1 − ai,−1)} with a learning rate such that R < 1.
Proof. The proof is in Section C.5 of Wang et al. (2020a).
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 inequality ∥a+ b∥2 ≤ 2 ∥a∥2 + 2 ∥b∥2 which could instead be obtained with:
E ∥∥∥∥∥ k−1∑ s=0 ai,sgi(y t i,s) ∥∥∥∥∥ 2  = E ∥∥∥∥∥ k−1∑ s=0 ai,s ( gi(y t i,s)−∇Li(yti,s) )∥∥∥∥∥ 2 +E ∥∥∥∥∥ k−1∑ s=0 ai,s∇Li(yti,s) ∥∥∥∥∥ 2  ,
(93) which uses Assumption 1, giving E [ ⟨ ∑k−1 s=0 ai,s ( gi(y t i,s)−∇Li(yti,s ) , ∑k−1 s=0 ai,s∇Li(yti,s⟩ ] = 0 with the same reasoning as for U in equation (111).
Lemma 4. Under Assumptions 1 to 3, we can prove n∑
i=1
γi E [∥∥aihti∥∥2] ≤ 11−Rσ2 n∑ i=1 γi ( ∥ai∥22 − (a 2 i,−1) ) + 2 [ R
1−R + 1 ]( n∑ i=1 γia 2 i )( β2 E [∥∥∥∇L̃(θt)∥∥∥2]+ κ2) , (94) where R′ = 2η2l L 2 maxi{∥ai∥21} < 1.
Proof. Due to the definition of hti, we have:
E [∥∥aihti∥∥2] = a2i E ∥∥∥∥∥ K−1∑ k=0 1 ai ai,k∇Li(yti,k) ∥∥∥∥∥ 2  (95)
≤ a2i K−1∑ k=0 1 ai ai,k E [∥∥∇Li(yti,k)∥∥2] . (96) Using Jensen inequality, we have
E [∥∥∇Li(yti,k)∥∥2] ≤ 2E [∥∥∇Li(yti,k)−∇Li(θt)∥∥2]+ 2E [∥∥∇Li(θt)∥∥2] (97)
≤ 2L2 E [∥∥yti,k − θt∥∥2]+ 2E [∥∥∇Li(θt)∥∥2] , (98)
where the second equality comes from using Assumption 2.
Also, Section C.5 of Wang et al. (2020a) proves
1
ai K−1∑ k=0 ai,k E [∥∥yti,k − θt∥∥2] ≤ 11−Rη2l σ2 (∥ai∥22 − (a2i,−1))+ 1L2 R1−R E [∥∥∇Li(θt)∥∥2] .
(99)
Plugging equation (98) and then equation (99) in equation (96), we get:
E [∥∥aihti∥∥2] ≤ a2i K−1∑
k=0
1 ai ai,k
[ 2L2 E [∥∥yti,k − θt∥∥2]+ 2E [∥∥∇Li(θt)∥∥2]] (100) = 2L2a2i
K−1∑ k=0 1 ai ai,k E [∥∥yti,k − θt∥∥2]+ 2a2i E [∥∥∇Li(θt)∥∥2] (101) ≤ 2L2a2i [ 1
1−R η2l σ
2 ( ∥ai∥22 − (a 2 i,−1) ) + 1
L2 R 1−R E [∥∥∇Li(θt)∥∥2]]
+ 2a2i E [∥∥∇Li(θt)∥∥2] (102)
≤ R ′ 1−R σ2 ( ∥ai∥22 − (a 2 i,−1) ) + 2a2i [ R 1−R + 1 ] E [∥∥∇Li(θt)∥∥2] . (103)
Summing over n gives
n∑ i=1 γi E [∥∥aihti∥∥2] ≤ 2L2 11−Rη2l σ2 n∑ i=1 γia 2 i ( ∥ai∥22 − (a 2 i,−1) ) + 2 [ R
1−R + 1 ] n∑ i=1 γia 2 i E [∥∥∇Li(θt)∥∥2] . (104)
Using Assumption 3 in equation (104) and R′ < 1 completes the proof.
C.3 INTERMEDIARY THEOREM
Theorem 3. The following inequality holds:
1
T T−1∑ t=0 E [∥∥∥∇L̃(θt)∥∥∥2] ≤ O( 1 (1− Ω)η̃ ( ∑n i=1 piai)T ) +O(η̃A′σ2 1 m ) +O(η2l σ2B′)
+O(η2l C ′κ2) +O(η̃D′σ2) +O(η̃E′κ2), (105)
where quantities A-E are defined in the following proof from equation (122) to equation (126).
Proof. Clients local loss functions are L-Lipschitz smooth. Therefore, L̃ is also L-Lipschitz smooth which gives
E [ L̃(θt+1)− L̃(θt) ] ≤ E [ ⟨∇L̃(θt),θt+1 − θt⟩ ] ︸ ︷︷ ︸
T1
+ L 2 E [∥∥θt+1 − θt∥∥2]︸ ︷︷ ︸
T2
, (106)
where the expectation is taken over the subset of randomly sampled clients St and the clients gradient estimator noises ξti . Please note that we use the notation E [·] instead of E{ξti},St [·] for ease of writing.

heading: BOUNDING T1
text: By conditioning on {ξti} and using equation (91), we get:
T1 = E [ ⟨∇L̃(θt),ESt [ θt+1 − θt ] ⟩ ] = −η̃Keff E [ ⟨∇L̃(θt), n∑ i=1 wih t i⟩ ] , (107)
which, using 2⟨a, b⟩ = ∥a∥2 + ∥b∥2 − ∥a− b∥2 can be rewritten as:
T1 = − 1
2 η̃Keff E ∥∥∥∇L̃(θt)∥∥∥2 + ∥∥∥∥∥ n∑
i=1
wih t i ∥∥∥∥∥ 2 − ∥∥∥∥∥∇L̃(θt)− n∑
i=1
wih t i ∥∥∥∥∥ 2  . (108)

heading: BOUNDING T2
text: T2|St = η̃2 E ∥∥∥∥∥ n∑
i=1
ωiaid t i ∥∥∥∥∥ 2 |St  (109) = η̃2 E ∥∥∥∥∥ n∑
i=1
ωiai ( dti − hti ) + n∑ i=1 ωiaih t i ∥∥∥∥∥ 2 |St  (110) = η̃2 E ∥∥∥∥∥ n∑
i=1
ωiai ( dti − hti )∥∥∥∥∥ 2 |St + η̃2 E ∥∥∥∥∥ n∑ i=1 ωiaih t i ∥∥∥∥∥ 2 |St  + 2η̃ E [ ⟨
n∑ i=1 ωiai ( dti − hti ) , n∑ i=1 ωiaih t i⟩|St ] ︸ ︷︷ ︸
U
. (111)
Using Assumption 1, we have E [ ⟨dti − hti, htj⟩ ] = 0. Hence, we get U = 0 and can simplify T2 as:
T2 = η̃ 2 n∑ i=1 E [ ω2i ] a2i E [∥∥dti − hti∥∥2]+ η̃2 E ∥∥∥∥∥ n∑ i=1 ωiaih t i ∥∥∥∥∥ 2  . (112)
Using Lemma 1 on the second term, we get:
T2 = η̃ 2 n∑ i=1 E [ ω2i ] a2i E [∥∥dti − hti∥∥2]+ η̃2 n∑ i=1 γi E [∥∥aihti∥∥2]+ η̃2(1− α)E ∥∥∥∥∥ n∑ i=1 piaih t i ∥∥∥∥∥ 2  .
(113)
Finally, by bounding the first term using Assumption 1, and noting that piai = wiKeff for the second term, we get:
T2 = η̃ 2 n∑ i=1 E [ ω2i ]K−1∑ k=0 a2i,k E [∥∥gi(yti,k)−∇Li(yti,k)∥∥2]
+ η̃2 n∑
i=1
γi E [∥∥aihti∥∥2]+ η̃2(1− α)K2eff E ∥∥∥∥∥ n∑
i=1
wih t i ∥∥∥∥∥ 2  (114)
≤ η̃2 n∑
i=1
E [ ω2i ] ∥ai∥22 σ 2 + η̃2 n∑
i=1
γi E [∥∥aihti∥∥2]+ η̃2(1− α)K2eff E ∥∥∥∥∥ n∑
i=1
wih t i ∥∥∥∥∥ 2  . (115)

heading: GOING BACK TO EQUATION (106)
text: Substituting equation (108) and equation (115) back in equation (106), we get:
E [ L̃(θt+1)− L̃(θt) ] ≤ −1
2 η̃Keff ∥∥∥∇L̃(θt)∥∥∥2 + 1 2 η̃Keff E ∥∥∥∥∥∇L̃(θt)− n∑
i=1
wih t i ∥∥∥∥∥ 2 
− 1 2 η̃Keff [1− Lη̃(1− α)Keff ]E ∥∥∥∥∥ n∑
i=1
wih t i ∥∥∥∥∥ 2 
+ L
2 η̃2 n∑ i=1 E [ ω2i ] ∥ai∥22 σ 2 + L 2 η̃2 n∑ i=1 γi E [∥∥aihti∥∥2] , (116)
We consider the learning rate to satisfy 1−Lη̃(1−α)Keff > 0 such that we can simplify equation (116) as :
E [ L̃(θt+1)− L̃(θt) ] η̃Keff ≤ −1 2 ∥∥∥∇L̃(θt)∥∥∥2 + 1 2 E ∥∥∥∥∥∇L̃(θt)− n∑
i=1
wih t i ∥∥∥∥∥ 2 
+ L
2 η̃
1
Keff n∑ i=1 E [ ω2i ] ∥ai∥22 σ 2 + L 2 η̃ 1 Keff n∑ i=1 γi E [∥∥aihti∥∥2] (117)
≤ −1 2 ∥∥∥∇L̃(θt)∥∥∥2 + 1 2 n∑ i=1 wi E [∥∥∇Li(θt)− hti∥∥2]
+ L
2 η̃
1
Keff n∑ i=1 E [ ω2i ] ∥ai∥22 σ 2 + L 2 η̃ 1 Keff n∑ i=1 γi E [∥∥aihti∥∥2] , (118)
where the last inequality uses the definition of the surrogate loss function L̃ and the Jensen’s inequality.
Using Lemma 4 and 3, we get:
E [ L̃(θt+1)− L̃(θt) ] η̃Keff ≤ −1 2 ∥∥∥∇L̃(θt)∥∥∥2 + 1 2 η2l L 2σ2 1−R n∑ i=1 wi ( ∥ai∥22 − a 2 i,−1
) + Rβ2 2(1−R) E [∥∥∥∇L̃(θt)∥∥∥2]+ Rκ2 2(1−R)
+ L
2 η̃
1
Keff
[ n∑
i=1
E [ ω2i ] ∥ai∥22 + 1
1−R n∑ i=1 γi ( ∥ai∥22 − (a 2 i,−1) )] σ2
+ Lη̃ 1
Keff
[ R
1−R + 1 ]( n∑ i=1 γia 2 i )( β2 E [∥∥∥∇L̃(θt)∥∥∥2]+ κ2) . (119)
If we assume that R ≤ 12β2+1 , and considering that β 2 ≥ 1, then we have 11−R ≤ 1 + 1 2β2 ≤ 3 2 ,
R 1−R ≤ 1 2 , and
Rβ2 1−R ≤ 1 2β2+1 (1 + 1 2β2 )β 2 = 12 . We also define Ω = Lη̃ 1 Keff 3 2 (∑n i=1 γia 2 i ) β2 ≤
1 2 . Substituting these terms in equation (119) gives
E [ L̃(θt+1)− L̃(θt) ] η̃Keff ≤ −1 4 [1− Ω] ∥∥∥∇L̃(θt)∥∥∥2 + 3 4 η2l L 2σ2 n∑
i=1
wi ( ∥ai∥22 − a 2 i,−1 ) + 3
2 η2l L 2 max i {ai(ai − ai,−1)}κ2
+ L
2 η̃
1
Keff
[ n∑
i=1
E [ ω2i ] ∥ai∥22 + 3
2 n∑ i=1 γi ( ∥ai∥22 − (a 2 i,−1) )] σ2
+ 3
2 Lη̃
1
Keff
( n∑
i=1
γia 2 i
) κ2. (120)
Averaging across all rounds, we get:
1− Ω T T−1∑ t=0 E [∥∥∥∇L̃(θt)∥∥∥2] ≤ 4 L̃(θ0)− L̃(θ∗) η̃KeffT + 3η2l L 2σ2 n∑ i=1 wi ( ∥ai∥22 − a 2 i,−1 ) + 6η2l L
2 max i {ai(ai − ai,−1)}κ2
+ Lη̃ 1
Keff
[ 2
n∑ i=1 E [ ω2i ] ∥ai∥22 + 3 n∑ i=1 γi ( ∥ai∥22 − (a 2 i,−1) )] σ2
+ 6Lη̃ 1
Keff
( n∑
i=1
γia 2 i
) κ2. (121)
We define the following auxiliary variables
A = m 1
Keff n∑ i=1 E [ ω2i ] ∥ai∥22 = m 1∑n i=1 piai n∑ i=1 [ Var [ωi] + p 2 i ] ∥ai∥22 , (122)
B = n∑ i=1 wi ( ∥ai∥22 − a 2 i,−1 ) = n∑ i=1 piai∑n j=1 pjaj ( ∥ai∥22 − a 2 i,−1 ) , (123)
C = max i
{ai(ai − ai,−1)}, (124)
D = 1
Keff max i {ai(ai − ai,−1)} n∑ i=1 γi = 1∑n i=1 piai C
( n∑
i=1
Var [ωi] + α n∑ i=1 p2i
) , (125)
E = 1
Keff max i {a2i }
( n∑
i=1
γi
) =
1∑n i=1 piai max i {a2i }
( n∑
i=1
Var [ωi] + α n∑ i=1 p2i
) . (126)
We define for A -E the respective quantities A′-E′ such that X ′ = 11−ΩX . We have:
1
T T−1∑ t=0 E [∥∥∥∇L̃(θt)∥∥∥2] ≤ 4 L̃(θ0)− L̃(θ∗) (1− Ω)η̃ ( ∑n i=1 piai)T + 2Lη̃A′σ2 1 m + 3η2l L 2σ2B′
+ 6η2l L 2C ′κ2 + 3Lη̃Dσ2 + 6Lη̃Eκ2, (127)
C.4 SYNTHESIS OF LOCAL LEARNING RATE ηl CONDITIONS FOR THEOREM 3
A sufficient bound on the local learning rate ηl for constraints on R for Lemma 3 and equation (119), and constraint on R′ for Lemma 4 to be satisfied is:
2 [ 2β2 + 1 ] η2l L
2 max i {∥ai∥21} < 1. (128)
Constraints on equation (116) can be simplified as
Lηgηl(1− α)Keff < 1. (129)
Constraints on Ω, equation (119), give
3Lηgηl 1
Keff
( n∑
i=1
γia 2 i
) β2 ≤ 1. (130)

heading: C.5 THEOREM 2
text: Proof. With FedAvg, every client performs vanilla SGD. As such, we have ai,k = 1 which gives ai = K and ∥ai∥2 = √ K. In addition we consider a local learning rate ηl such that Ω ≤ 12 as such we can bound A′-E′ as X ′ ≤ 2X . Finally, considering that the variables A to E can be simplified as
A = m n∑ i=1 [ Var [ωi] + p 2 i ] , (131)
B = (K − 1), (132)
C = K(K − 1), (133)
D = (K − 1)
( n∑
i=1
Var [ωi] + α n∑
i=1
p2i
) , (134)
and
E = K
( n∑
i=1
Var [ωi] + α n∑ i=1 p2i
) , (135)
the convergence bound of Theorem 3 can be reduced to
1
T T−1∑ t=0 E [∥∥∇L(θt)∥∥2] ≤ O( 1 ηgηlKT ) +O ( ηgηl n∑ i=1 [ Var [ωi] + p 2 i ] σ2 ) +O ( η2l (K − 1)σ2 ) +O ( η2l K(K − 1)κ2
) +O ( ηgηl ( n∑
i=1
Var [ωi] + α n∑ i=1 p2i
)[ (K − 1)σ2 +Kκ2 ]) , (136)
which completes the proof.
Ω is proportional to ∑n i=1 γi = ∑n i=1 Var [ωi]+α ∑n i=1 p 2 i . With full participation, we have Ω = 0. However, with client sampling, all the terms in equation (136) are proportional with 11−Ω . Yet, we provide a looser bound in equation (136) independent from Ω as the conclusions drawn are identical. Through Ω, ∑n i=1 Var [ωi] and α needs to be minimized. This fact is already visible by inspection of the quantities E and F .
We note that equation (136) depends on client sampling through σ2, which is an indicator of the clients SGD quality, and κ2, which depends on the clients data heterogeneity. In the special case where clients have the same data distribution and perform full gradient descent, based on the arguments discussed in the previous paragraph, we can still provide the following bound showing the influence of client sampling on the convergence speed, while highlighting the interest of minimizing the quantities ∑n i=1 Var [ωi] and α.
1
T T−1∑ t=0 E [∥∥∇L(θt)∥∥2] ≤ O( 1 (1− Ω)ηgηlKT ) , (137)
When setting the server learning rate at 1, ηg = 1 with client full participation, i.e. Var [ωi] = Var [ ∑n i=1 ωi] = α = 0 and m = n, we have E = F = 0 and can simplify A to
A = n n∑ i=1 p2i . (138)
Therefore, the convergence guarantee we provide is 1ηlKT +ηl ∑n i=1 p 2 iσ
2+η2l (K−1)σ2+η2l K(K− 1)κ2, which is identical to the one of Wang et al. (2020a) (equation (97) in their work), where∑n
i=1 p 2 i can be replaced by 1/n when clients have identical importance, i.e. pi = 1/n. In the special case, where we use ηl = √
m/KT (Wang et al., 2020a), we retrieve their asymptotic convergence bound 1√ mKT + √ m KT ∑n i=1 p 2 iσ 2 + mT σ 2 + mT Kκ 2.

heading: C.6 APPLICATION TO CLUSTERED SAMPLING
text: We adapt Theorem 2 to clustered sampling. Fraboni et al. (2021) prove the convergence of FL with clustered sampling by giving identical convergence guarantees to the one of FL with MD sampling. As a result, their convergence bound does not depend of the clients selection probability in the different clusters rk,i. The authors’ claim was that reducing the variance of the aggregation weights provides faster FL convergence, albeit only providing experimental proofs was provided to support this statement. Corollary 2 here proposed extends the theory of Fraboni et al. (2021) by theoretically demonstrating the influence of 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 ai using the proof of Theorem 3 in Section C.3.
Corollary 2. Even with no α such that Cov [ωi(St), ωj(St)] = −αpipj , the bound of Theorem 2 still holds with B, C, and D defined as in Section C.3 and
A = m
[ 1
m − 1 m2 n∑ i=1 m∑ k=1 r2k,i + n∑ i=1 p2i
] , E = 1
m (K − 1), and F = 1 m K, (139)
where E and F are identical to the one 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 1. In the proof of Theorem 3, Lemma 1 is only used in equation (113). We can instead use Lemma 2 and keep the rest of the proof as it is in Section C.3. Therefore, the bound of Theorem 3 remains unchanged for clustered sampling where E and F 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
Var
[ n∑
i=1
ωi(SMD) ] = 0 and αMD = 1
m , (140)
while the ones of clustered sampling in Section A.7 give n∑
i=1
Var [ωi(SCl)] = 1 m − 1 m2 n∑ i=1 m∑ k=1 r2k,i ≤ n∑ i=1 Var [ωi(SMD)] . (141)

heading: C.7 PROOF OF COROLLARY 1
text: Proof. Combining equation (29) with equation (36) gives
ΣMD − ΣU = [ − 1 m n∑ i=1 p2i + 1 m ] − ( n m − 1 ) n∑ i=1 p2i (142)
= − 1 m
[ (n−m+ 1)
n∑ i=1 p2i − 1
] . (143)
Therefore, we have
ΣMD ≤ ΣU ⇔ n∑
i=1
p2i ≤ 1
n−m+ 1 . (144)
Combining equation (31), (32), (44), and (46) gives
γMD − γU = n∑
i=1
Var [ωi(SMD)] + αMD n∑ i=1 p2i −
( n∑
i=1
Var [ωi(SU )] + αU n∑ i=1 p2i
) (145)
= 1 m − n−m m(n− 1) n n∑ i=1 p2i . (146)
Therefore, we have
γMD ≤ γU ⇔ n∑
i=1
p2i ≤ 1 n−m n− 1 n . (147)
Noting that 1
n−m+ 1 − 1 n−m n− 1 n = −m+ 1 n(n−m)(n−m+ 1) ≤ 0, (148)
completes the proof.

heading: D QUADRATIC
text: Proof. For every client, we consider local loss functions such that:
Li(θ) = 1
2 ∥θ − θ∗i ∥ 2 , (149)
where θ∗i is client’s i local minimum. By taking the derivative of the global loss function, equation (1), with these clients local loss function, gives:
θ∗ = n∑ i=1 piθ ∗ i . (150)
yti,k is the local model obtained for client i after k SGD and satisfies
yti,k+1 = y t i,k − ηl(yti,k − θ∗i ) = (1− ηl)yti,k + ηlθ∗i , (151)
which, by induction, gives
θt+1i = (1− ηl) Kθt + K−1∑ k=0 (1− ηl)kηlθ∗i . (152)
We note that ∑K−1
k=0 (1− ηl)k = [1− (1− ηl)K ]/ηl. By defining ϕ = 1− (1− ηl)K , we get:
θt+1i − θ t = (1− ηl)Kθt + [ 1− (1− ηl)K ] θ∗i − θt = ϕ(θ∗i − θt). (153)
Hence, we have n∑
i=1
pi(θ t+1 i − θ t) = ϕ(θ∗ − θt). (154)
Using Decomposition Theorem 1 leads to
E [∥∥θt+1 − θ∗∥∥2] = (1− 2η̃)E [∥∥θt − θ∗∥∥2]+ η2g n∑
i=1
γiϕ 2 E [∥∥θt − θ∗i ∥∥2]
+ η2g(1− α)ϕ2 E [∥∥θt − θ∗∥∥2] . (155)

heading: E ADDITIONAL EXPERIMENTS

heading: E.1 SYNTHETIC EXPERIMENT

heading: E.2 SHAKESPEARE DATASET
text: The client local learning rate ηl is selected in {0.1, 0.5, 1., 1.5, 2., 2.5} minimizing FedAvg with full participation, and n = 80 training loss at the end of the learning process.

heading: E.3 CIFAR10 DATASET
text: We consider the experimental scenario used to prove the experimental correctness of clustered sampling in (Fraboni et al., 2021) on CIFAR10 (Krizhevsky, 2009). The dataset is partitioned in n = 100 clients using a Dirichlet distribution with parameter α = 0.1 as proposed in Harry Hsu et al. (2019). 10, 30, 30, 20 and 10 clients have respectively 100, 250, 500, 750, and 1000 training samples, and testing samples amounting to a fifth of their training size.

Review summaries:
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.

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. 

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.

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.