DELTA: Diverse Client Sampling for Fasting Federated Learning
Authors: Lin Wang
Yongxin Guo
Tao Lin
Xiaoying Tang
Venue: Submitted to ICLR 2023 (2023)
Keywords: federated learning
client sampling

Abstract: Partial client participation has been widely adopted in Federated Learning (FL) to efficiently reduce the communication burden. However, an improper client sampling scheme will select unrepresentative subsets, which will cause a large variance in the model update and slows down the convergence. Existing sampling methods are either biased or can be further improved to accelerate the convergence. In this paper, we propose an unbiased sampling scheme, termed DELTA, to alleviate this problem. In particular, DELTA characterizes the impact of client diversity and local variance and samples the representative clients who carry valuable information for global model updates. Moreover, DELTA is a provably optimal unbiased sampling scheme that minimizes the variance caused by partial client participation and achieves better convergence than other unbiased sampling schemes. We corroborate our results with experiments on both synthetic and real data sets.

Under review as a conference paper at ICLR 2023
DELTA: DIVERSE CLIENT SAMPLING FOR FASTING FEDERATED LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Partial client participation has been widely adopted in Federated Learning (FL) to efficiently reduce the communication burden. However, improper client sampling scheme will select unrepresentative subsets, which will cause large variance in the model update and slows down the convergence. Existing sampling methods are either biased or can be further improved to accelerate the convergence. In this paper, we propose an unbiased sampling scheme, termed DELTA, alleviate this problem. In particular, DELTA characterizes the impact of client diversity and local variance and samples the representative clients who carry valuable information for global model updates. Moreover, DELTA is provably optimal unbiased sampling scheme that minimizes the variance caused by partial client participation and achieves better convergence than other unbiased sampling schemes. We corroborate our results with experiments on both synthetic and real data sets.
INTRODUCTION
Federated Learning (FL) has recently emerged as critical distributed learning paradigm where number of clients collaborate with a central server to train a model. Edge clients finish the update locally without any data sharing, thus preserving client privacy. Communication can become the pri- mary bottleneck of FI. since edge devices have limited bandwidth and connection availability (Wang) ct al. 2022). order to reduce the communication burden, only portion of clients will be chosen for training in practice. However, an improper client sampling strategy, such as uniform client sampling adopted in FedAvg (McMahan et al. 2017), might exacerbate the issues of data heterogeneity in FL. as the randomly-selectes unrepresentative subsets can increase the variance introduced by client sampling and directly slow down the convergence.
Existing sampling strategies can usually be categorized into two classes: biased and unbiased. Considering the crucial unbiased client sampling that may preserve the optimization objective, only few strategies proposed, e.g., in terms of multinomial distribution (MD) sampling and cluster sampling, including clustering based on sample size and clustering based on similarity methods. However, these sampling methods usually suffer from slow convergence with large variance and computation overhead problems (Balakrishnan et al. 2021 Fraboni et al.) 20216).
To accelerate the convergence of FL with partial client participation, Importance Sampling (IS). another unbiased sampling strategy, is proposed in recent literature (Chen et al., 2020: Rizk et al. 2020). IS will select clients with the large gradient norm, shown in Fig ((a) As for another sampling method in Figure T(a), cluster-based IS will first cluster the clients according to the gradient norm and then use IS to select the clients with large gradient norm within each cluster.
Though IS, and cluster-based IS have their advantages, 1) IS suffers from learning inefficiency due to the transmission of excessive important yet similar updates from clients to the server. This problem has been pointed out in recent works (Fraboni et al., 2021a Shen et al., 2022). and some efforts are being conducted to solve this problem. One of them is cluster-based IS, which avoids redundant sampling of clients by first clustering similar clients into groups Though clustering operation can somewhat alleviate this problem, 2) vanilla cluster-based IS does not work well gradient is too complicated to be good clustering feature
because the high-dimensionas and can bring about poor clustering results, as pointed out by Shen et al. (2022). In addition, clustering is known to be susceptible to biased performance if the samples are chosen from group that clustered based on a biased opinion, as shown in SSharma (2017); Thompson (1990). From the above discussion, we know though IS and cluster-based IS have their own advantages in

---

Under review as a conference paper at ICLR 2023
Cluster
Cluster B
Postive
Gradient Selected Client
Gradient of Not Selecied Client
Gradient of Global Model
Negative
Importance Samping
Cludder baned
DELTA (Ous)
(b)
Figure I: Difference between IS. cluster-based 1S, and our sampling scheme DELTA.
56
Lnifoom saarpling
Figure 2: We logistic regression model to show the performance of different methods iid MNIST. We sample out of 200 500 communication rounds. We report the average of the best 10 accuracies under 100, 300, and 500 rounds, which shows the accuracy performance from the initial training state convergence.
I8
eluster hased
54
and run
acsuracy
78
76
counds
500
sampling, they both face their own limitations well. Specifically, IS has utilized the large gradient norm to accelerate convergence while meeting redundant sampling problems due to excessive similar updates, and (luster-based IS alleviate the similar update problem but face slow convergence due to poor clustering effect and biased performance. Figure Fillustrates both these two sampling methods have times when they perform poorly.
To address the above challenges of IS and cluster-based IS, namely excessive similar updates and poor performance due to poor cluster effect and biased grouping, we propose a novel sampling method for Federated Learning, termed DivErse cLienT sAmpling (DELTA). To simplify the notion, in this paper, we term FL with IS as FedIS. Compared with FedIS and cluster- based IS methods, show in Figure ((b) that DELTA tends to select clients with diverse gradient w.r.t global gradient. In this way, DELTA not only utilizes the advantages of large gradient norm for convergence acceleration but also overcomes the gradient similarity issue.
1.1 CONTRIBUTIONS
In this paper, we propose an efficient unbiased sampling scheme based on gradient diversity and local variance, in the sense that (i) it can effectively solve the excessive similar gradient problem without additional clustering operation, while taking advantage of the accelerated convergence of gradient- norm-based IS and (ii) is provable better than uniform sampling gradient norm based sampling. The sampling scheme is completely generic and can be easily compatible with other advanced optimization methods, like Fedprox (Li et al. 2018) and momentum (Karimireddy al. 2020a).
As our key contributions.
we present an unbiased sampling scheme for FL based on gradient diversity and local variance, a.k.a. DELTA. problem of over-selection of clients with similar gradients at the beginning of training when that gradient of the global model is relatively large. Compared with the SOTA rate of FedAvg. its conver- gence rate removes the term (1/22/5) well as a o -related term in the numerator of (1/22/))) We provide theoretical proof of convergence for nonconvex FedIS. Unlike existing work, our analysis is based on more relaxed assumption and yields no worse results than the existing convergence rates. Its rate removes the term (1//2//3 from that of FedAvg.
take advantage of the clients who select a large gradient norm and solve the
2 RELATED WORK
FedAvg is proposed by McMahan al. (2017) de facto algorithm of FL. in which multiple local SGD steps are executed on the available clients to alleviate the communication bottleneck. While communication efficient, heterogeneity, such system heterogeneity (Li al.) 2018 Wang et al.
2

---

Under review as a conference paper at ICLR 2023
2020 Mitra et al. 2021 Diao et al.
2020). and statistical/objective heterogeneity (Lin al. 2020
Karimireddy et al. 2020b Li et al.
2018 Wang et al.) 2020; Guo et al. (021), results in inconsistent
optimization objectives and drifted clients models, impeding federated optimization considerably.
Objective inconsistency in FI.. Objective inconsistency is not rare in FL. due to the heterogeneity
of clients' data and the difference in computing ability. For instance, (aang et al. (2020) first identify
an objective inconsistency caused by hetcrogeneous local updates. There also exist several works that encounter the difficulty from the objective inconsistency caused by partial client participation (Li
jet al., 2019 Cho et al.) 2020 Balakrishnan et al., (021). Li et al. (2019); Cho et al. (2020) use
local-globar gap f 21 >x= F to measure the distance between global optimum and average of all local personal optimum, where the local-global gap results from objective inconsistency at the final optimal point. In fact, objective inconsistency occurs in each training round, not only the final optimal point. [Balakrishnan et al. (202T) also encounter objective inconsistency caused by partial client participation. However, they use Σx=1 (z,( fz+))l I E as an assumption to describe such update inconsistency caused by objective inconsistency without any analysis on it. So far, the objective inconsistency caused by partial client participation has not been analyzed though it is prevalent in FL., even in homogeneous local updates. Our work gives the fundamental convergence analysis on the influence of the objective inconsistency of partial client participation.
Client selection in FL. In general, the sampling method can be divided into biased and unbiased sampling. Note that unbiased sampling guarantees the same expected value of the client aggregation as the global deterministic aggregation with all clients' participation. In contrast, biased sampling will lead converging to sub-optimal. The most famous unbiased sampling strategy in FL multinomial sampling (MD). that samples according to client data ratio (Wang et al., 2020: Fraboni al. 2021a). Besides, IS, an unbiased sampling method, is recently used in FL to reduce the convergence variance. [Chen et al. (2020) uses update norm as importance to sampling clients, Rizk et al. (2000) samples clients based on data variability and Mohammed et al. (202I) uses test accuracy an estimation of importance. Meanwhile, many biased sampling strategies have been proposed for accelerating training. such as sampling clients with higher loss (Cho et al., 2020). sampling clients as many possible under the limitation of threshold (Qu et al.) 2021). sampling clients with larger updates (Ribero & Vikalo, (220)) and greedy sampling according to gradient diversity (Balakrishnan et al. 2021). However, all these biased sampling methods can exacerbate the negative effects of objective inconsistency and promise to converge to only a neighbor of optimum. Recently, cluster-based client selection has draw some attentions FL (Fraboni et al. 202 Xu et al. 2021 Muhammad et al. 2020 (Shnn et al. 2022). Though cluster operation needs additional clustering operation, and causes computation and memory overhead, Fraboni et al. (2021a); Shhn
et al. (2022) show clustering is helpful for sampling diverse clients and benefits for reducing variance. The proposed DELTA in Algorithm [ can be viewed as a muted version of the diverse client clustering algorithm while promising to be unbiased.
THEORETICAL ANALYSIS AND AN IMPROVED FL SAMPLING STRATEGY
In FL. the objective of the global model is sum-structured optimization problem:
minger [f(x) = Σ. wxFF(xx)]
(1)
where F((z) = Eg,-D,
{ represents the local objective function of client í over data
distribution D,, and & means the sampled data of client i. m is the total number of clients and w; represents the weight of client i. With partial client participation, FedAvg (McMahan et al., 2017 randomly selects [S.1 clients (n m) communicate and update modef. Then the loss Tunction of actual participating users in each round can be expressed as:
fs, (x,) = 1 Eies, F((x:).
(2)
To ease the theoretical analysis of our work, we use the following widely used assumptions.
3.1 ASSUMPTIONS
Assumption (L-Smooth). The client's 's local objective function is Lipschitz smooth, i.e., there is a constant I. > 0, such that [VV:(()) Fi())) & T. || vll. Vx, y E IRd, and i 1,2, ...... m.
3

---

Under review as a conference paper at ICLR 2023
Table I: Number of communication rounds required to reach e or e e op (c for unbiased sampling and e yp for biased sampling, where yp is a non-convergent constant term) accuracy for FL. σr, is local variance bound, and de bound is (() V V/(+)ll v ag. I' is the distance of global optimum and the average of local optimum((Heeeeet Heterogeeettt bound), I corresponds y strongly convex. G is the client's gradient bound, and Ça mcans the gradient diversity.
Alporichm
Convexity
Partal Worker
Unbizsed Sampling
Convergence rate
Asumptiin
Stvagly/Noocwwve
parke (57
DRLTA
Noncomex
Asumptian
(ours]
Noncoovex
Assumptian
FollS (others) Cloi al. 2020
Nonconvex
Assumpiin
an Bound
Yang
2021
Nonconvex
402
Karimineddl etal.
56%
Assumption
Blankisttaa 0 3.
4024
Strongly conves
Heterogeselly Gup
Cho al.
2020
Stroegly conves
Hetzrogencity Cap
Yong et al
2021
Noncomves
mo bound
Karinireedy et
20200
Strougly Coness
Assumptio
JanAce
M= oz + 4Kog. 1/9 = oi KIl - jeg. X7 = o2 + 6K
MP 02 4K:2
uusumption: A bound of the similarity umong local gradients in [Chen el nl. 2020 Another PedliStothers) (Chen et al. 3020 has the same convergence rale
Karmttedlly al. N022h under the assunptionn While FedlS(cuss) mses looser Assiintico and accieves fisler rale liam Clan al 3120
Algorithm DELTA
Require: initial weights no, global learning rate 7,, local learning rate Ty. number of training rounds
Ensure: trained weights øT
I: for round f = 1....,7 T..,,
do
2: Select subset of clients according to the proposed sampling probability of DELTA II
3: for each worker i E St,in parallel do
4: Fi.u = 21
5:
for = 0, 0.........
do
6:
compute g². = (.
7:
Local update:zi, = F m1
8:
Let A] = zi,x 22,0 = - Ti. En=o 9e.6
9:
Send gradient to server
10:
At Server:
11:
Receive E St
12:
let A. | Eies, up? A;
13: Server update: T4+1 = xι + 7
Broadcast _ to clients
Assumption (Unbiased Local Gradient Estimator and Local Variance). let çi be a random local data sample in the round t at client i: E [VF,(I {t] (F,(z)) vi E [m], where the expectation is over the local datasets sample. The function F, {t) has LL 0 bounded local variance,
i... E
([ 4 (P((=))) =o., Soz
Assumption 3 (Bound Dissimilarity). There exists constant OG 2 0 and A 2 O... E VF( (A2+ + 1)]VV + a. When all local loss functions are identical, A 0 and o
The above assumptions are commonly used in both non-convex optimization and FL literature, see e.g. Karimireddy et al. (2020b); Yang et al. (2021); Koloskova et al. (2020); Wang et al. (2020); Cho et (2020): ; Li al. (2019) For Assumption if all local loss functions are identical, then
we have A and dG
3.2 CONVERGENCE RATE FEDIS
As discussed in the introduction, IS has excessive gradient similarity problem, which may cause redundant sampling resulting in training inefficiency. As discussed in the introduction, IS has the issue of high gradient similarity, requiring us to design a new diversity sampling method. Before going to the details of our new sampling strategy, we first provide the convergence rate of FL under standard IS analysis in this section; the analysis itself not well explored, especially for the nonconvex setting. 3 and sampling strategy FedIS -K-1 of ΣK- Fi 4i.) is the sum of the gradient updates
Theorem 3.1 (Convergence rate of FedIS). Under Assumptions
pf Em 11031
|
where gf
> k=
4

---

Under review as a conference paper at ICLR 2023
of multiple local updates. Let constant local and global learning rates π and n be chosen as such that ML < min (1/(L C)2, where C is obtained from the condition that 1 12 11
IL > 0 ,and 1j S 1/(11 L),, the expected gradient norm will be bounded as follows: 1
2n
min [ 00
((-1")
VakT)
+0
of VnKT
O
M T
+
VnKT
Kog
(3)
order where f = f(x)) f(x)),,,, M of 4K and the expectation is over the local dataset samples among workers.
| Ey=n llafll
The FedIS sampling probability o gence w.r.t. p!. The variance is
is derived from minimizing the variance of conver-
KL²
KL 2
MILL 2m
LAmE
+
M
07.
Var(
0:),
(4)
2nK
mp
where Var((/mm)))))) called update variance. The proof details of Theorem 3.1 and derivation of sampling probability FedIS are detailed in Appendix Oppendix(Caand Appendix[E.]
Remark 3.2. It is worth mentioning that although a few works provide the convergence upper bound for FedIS, several limitations exist these analyses and results.
Rizk et al. (2020g; Luo et al. (2022) applied IS in FL to solve a convex/strongly convex problem, while we solved nonconvex problem.
2) In Rizk et al. (2020), their analysis result and sampling probability rely on the assumption of knowing the optimum J., which not feasible in practice.
3) Our analysis uses the common Assumption 7 while Chen et al. (2020) provides the convergence rate of nonconvex FL under a stronger assumption of gradient similarity bound. Compared with Chen et al. (2020), prove tighter convergence upper bound for FedIS. Specifically, our convergence
rate for FedIS improves from O VnkT +
T4/3) to O
+) (c.f. Table Iv.
VvkTT
Despite the success of FedIS in reducing the variance term in the convergence rate, is far from optimal, due to the issue of high gradient similarity and the improvement space further minimizing the variance term (i.e., global variance ag and local variance σr in 4). We will discuss how to address this challenging variance term in the next section.
3.3 AN IMPROVED CONVERGENCE ANALYSIS
To ease the understanding of the theoretical difference between FedIS and DELTA, as well as a better illustration of our design choice, we include an analysis flowehart in FigureBJt help understand the difference between FedIS and DELTA while strengthening the motivation. Specifically, based on the
convergence variance of FedIS, we find it is important to reduce the variance beyond Var( (/(mp))))) Furthermore, we connect the important variance with the convergence of surrogate objective f (xx). Unlike FedIS, which analyzes the global objective, DELTA focuses on analyzing the surrogate objective and therefore obtains different convergence variance and sampling probabilities than FedIS.
The limitations FedIS. As identified by the Theorem 3.1 discussed above, suffers from excessive similar gradient selection. The variance & in shows that the standard IS strategy can only control the update variance Var(H/(mp[1g/), while leaving other terms in O untouched, i.e., dr, and ag. Thus, the standard IS fails to handle the excessive similar gradient selection problem, and motivates us to give a new sampling strategy below to address the issue of az and aa-
The decomposition of the global objective. As inspired by the proof of Theorem 3.1 as well the corresponding Lemma B.I (stated in Appendix) proposed for unbiased sampling, the global objective can be decomposed into surrogate objective and update gap,
E [((a) 2
E (x))
+x2-
(5)
5

---

Under review as a conference paper at ICLR 2023
where Xt = [ - vf(xe)
the update gap.
Intuitively, the surrogate objective is the practical objective of the participating clients in each round, while the update gap Xt means the update distance between partial client participation and full client participation. The convergence behavior of the update gap X corresponds to the update variance
in O and the convergence of surrogate objective E [ (az)
is dependent on the other variance
terms in Q, i.e., local variance and global variance.
Minimizing the surrogate objective allows us further to reduce the variance term in the convergence rate, and focus on the convergence analysis of the surrogate objective below. For the purpose of analysis, we use IS property to formulate the surrogate objective with an arbitrary unbiased sampling probability.
Surrogate objective formulation. The expression of the surrogate objective relies the prop- erty of IS. In detail. aims to substitute the original sampling distribution p(2) with another arbitrary sampling distribution (2) while keeping the expectation unchanged: Eg(=) [F]
Ep(=) (s)) According to the Monte Carlo method, when ((z) follows the uni- form distribution, can estimate Egt=) [F)( by 1/m Ee= Pi(z) and Ep(x) [=<<s/pp(e))P(( by i/n Eies, 1/mp, Fz()). respectively, where m and |St| are sample sizes.
Based on the IS property, we formulate the surrogate objective as below:
(T.) = E. mp: (x,))
(6)
where is the total number of clients, |S.] = is the number of participating clients in each round, and pt is the probability that client is selected at round t.
An improved rate for the global objective. Following the fact (c.f. Lemma B.2 appendix) that
min ((x)) min + s min 2 2 f(z)))1
(7)
LE[T)
LE[T]
[E[2]
the convergence rate of the global objective can be formulated follows:
Theorem 3.3 (Convergence rate). Under Assumption 3 and les local and global learning rates n and nu satisfy πn < 1/(220kL 1 Em mpt) and MML S 1/XL, the minimal gradient norm will be bounded as below:
mineetry E BI (x)Il* S
f-- =
(8)
where g (wo). p"= (xx.), is constant, and the expectation over the local dataset samples among all workers. The combination of variance 4 represents combinations of local variance and client gradient diversity.
We derive the convergence rates for both sampling with replacement and sampling without replace- ment. For sampling without replacement:
KLP
Di
(o2, + +KK(2)) + Lug >m
mo o
(9)
For sampling with replacement,
Kn
(oi.- + 4K(2.) + LayE Σ m oi.
(10)
2mn
where (G.1 = VV (z))
fzx))l and let (a be a upper bound for all i, i.c., (a, S Ca. The proof details of Theorem can be found in Appendix D
3.4 OUR PROPOSED SAMPLING STRATEGY: DELTA
The update difference between the surrogate objective and the global objective can be defined as objective inconsistency. As demonstrated Figure different sampling methods lead to different degrees of objective inconsistency, and such inconsistency can be alleviated by choosing clients with a small updating gap. Figure (a) uses a toy example of square functions illustrate the objective inconsistency when two out of three clients are selected for training, where DELTA would sample
With slight abuse of notations, the f(x)) for fs, (2:a) in this paper.

---

Under review as a conference paper at ICLR 2023
surrogate objective
(
Lemma
Global objective (*²)
+x
Lemma
Theorem
Update Gap
8.2
xf = ElIV/(2)))
Var bounded by the convergence of currogate objective
Convergence variance global objective
Convergence variance of surrogate objective
eq(4):
eq(9) eq(10): T B1 Σ of + Bg Σ C8
Theorem 3.
Aro7 Age + Ag Var (mr oi)
Conollary
Corollary 34
FediS: pl
Y Ioj
1
DELTA: p/
2i (P(e)-//(e))-=oppp/ll Optimizing the variance term w.r. to
Optimizing variance
Figure 3: Sketch of theoretical analysis flow (Compared with FedIS). The left side represents the analysis flow of FedIS. while the analysis of DELTA is shown the right. The sampling probability difference comes from the difference in variance.
Clsent
Re- PeddAe
Rig
Clieee
T,0
Hiel global
Xy-LO8I74
Redi,
Clerr TAA
Clirn 3
(a) Objective inconsistency and update gap.
(b) Illustration of different sampling methods.
Figure 4: (a): Overview of objective inconsistency and update gap. Here is three square functions with expression y 10x and y 8) and gradient calculated at 22 The detail enlargement shows the objective inconsistency. (b): Illustration of different sampling methods. client's ' update is shown by grey arrow and the ideal global update is the black arrow. shows our DELTA is hetter than FedIS and FedAvg.
diverse clients, leading to small update gap. Figure 4(b) shows the one single round update process of different sampling schemes: IS tends to select client 2 and client 3 whose gradient norm large, while diversity sampling DELTA tends to select client 1 and client 3. Therefore, compared with IS, the sampled clients of DELTA have smaller bias from the global objective, illustrating a better sampling scheme of DELTA.
To derive our sampling strategy DELTA, is equivalent to solving an optimization problem that minimizes the variance & w.r.t the proposed sampling probability p/:
min d s.t. EmA
where O is a linear combination of local variance LL.s and gradient diversity Ça.s (cf. Theorem 3.3 Corollary 3.4 (Optimal sampling probability for DELTA). By solving the above optimization problem. the optimal sampling probability can be formulated as:
(11)
where On and 02 are constants defined as = 20K and oz = 5K T.ps + 2
Let 1T. 0 (Vikz) n (2O((K)) and substitute the optimal sampling probability III)
back
to Φ. Then for sufficiently large T. the iterates of Theorem 3.3 satisfy:
minse/ry E[ s 50( ( (1-11) VnkT
of
0. + 1K<2
+
+o
VnkT
KT
(12)
order of

---

Under review as a conference paper at ICLR 2023
3.5 DISCUSSIONS
Difference between DELTA and FedIS. The difference between DELTA and FedIS comes mainly from the difference between & and Φ. FedIS aims to reduce the update variance term Vap(Y(mpb)))) in 4, while DELTA aims to reduce the whole & which is composed of the gradient diversity and the local variance. Minimizing & corresponds further minimizing the terms of & that can be minimized by FedIS. Solving different optimization problems leads to different sampling probability expressions. As shown in Figure 4 DELTA selects the more diverse Client 1 and Client for participation, while FedIS tends to select Client 2 and Client 3 which have large gradient norms. It can be seen that the selection of DELTA leads to a smaller bias than FedIS. Moreover, as shown in Table T1 based on our convergence rate results, DELTA achieves a better convergence rate with O(G"/E higher than other unbiased sampling algorithms.
Compare DELTA with uniform sampling. According to the Cauchy-Schwarz inequality, DELTA is m 2 (Vorz +
at least better than uniform sampling by reducing variance: PIELIA
Paniior
2 1.
(E Vo10
This implies that DELTA does reduce the variance, especially when (E v (aizzaa23
< m.
E (eeiiVan +o288))
Remark 3.5. DELTA ensures the convergence of FL. with purtial clien! participation to a stationary point without any gap. Our results can be considered as a theoretical explanation for the heuristic of gradient diversity sampling algorithm in FL, and DELTA encourages the global model acquire more knowledge in each round. Specifically, the server will give more weight to the clients with larger gradient diversity and local variance. These clients are representative, and sampling these clients can accelerate training given the more diverse and informative data to reflect the global data distribution. However, DELTA may fail identify the attacked clients and even tends select them when it comes to user attack scenarios. We will leave the solution for this scenario in our future work.
4 PRACTICAL IMPLEMENTATION FOR DELTA AND FEDIS
Gradient-norm-baat sampling method requires the computation of the full gradient each iteration (Elvira & Martino 202 Zhao & Zhang 2015). However, obtaining each client's gradient in advance is generally inadmissible in FL. For practical purposes, a series of IS algorithms estimate the current round's gradient by the historical gradient (Cho et al., 2020 Katharopoulos & Fleuret 2017). Similarly, we utilize the gradient from the previous training iteration to estimate the gradient of the current round to reduce the computing resources (Rizk et al. 2020), where the previous iteration refers to the one in which the client participates.
In particular, iteration 0, all probabilities are set to 1/m, then during the ith iteration, after the participating clients i E St send the server their updated gradients, the sampling probabilities are 19.1 updated as: pi Eies, [|st,e|| (1 Eies; Pi.,), where the multiplicative factor follows from
ensuring all the probabilities sum to 1. Specifically, we use the average of the latest participated clients' gradients to approximate the true gradient of the global model for DELTA. In this way, is not necessary to obtain all clients' gradients in each round. The convergence analysis of our practical algorithm is provided in Appendix
EXPERIMENTS
In this section, we use both synthetic dataset and split FEMNIST to demonstrate our theoretical results. To show the validity of the practical algorithm, we run experiments on FEMNIST and CIFAR-10, and show that DELTA converges faster and achieve higher accuracy than other baselines.
Synthetic datasets. We first examine our theoretical results through logistic regression on synthetic datasets. In details, we randomly generate (x,, y) by y = log (Aa-6))/2) with given A, and h, as training data for clients, and each client's 's local dataset contain 1000 samples. In each round, 10 out of 20 clients are selected to participate in training (we also provide the results of 10 out of 200 clients in Appendix G To simulate the gradient noise, in each training step, we calculate the gradient of client i by gi V f((,,, b;, D2) + Pú, where A, and b, are model parameters, D; is the local dataset of client i, and ia is zero-mest mero-mean random variable which control the heterogeneity of client i. The larger the E||us|| !? the larger the heterogeneity of client
8

---

Under review as a conference paper at ICLR 2023
Taclog
Fachig Hedy
Hel3
(a) 20
(b) 30
(c)
40
Figure 5: Performance of different algorithms on the regression model. The loss is calculated by f(z; v) ||v log((Ara-hh)"/a)) A= 10, 1. We report the logarithm of global loss with different degrees of gradient noise All methods are well-tuned, and we report the best result of each algorithm under each setting. Table 2: Performance algorithms.
run 500 communication rounds on FEMNIST and CTFAR10 for each algorithm. We report the mean of maximum 5 accuracies for test datascts and the average number of communication rounds to reach the threshold accuracy.
Algerittnn
Roads
Tinets
Tincets
Fodlog owr unifeen sampling)
70,35 0.51
425 (LDx)
(1.0g)
$4.28 0.29
338 (1.00
3253 (1.0x)
Clustor besed 15
7L21 2 0.24
362 (L.1XX
1547.1 11 16x)
54.83200 0.02
ASX3
3188.54 BBX3
FadlS
71
(0
(1.32)
(37233
55.20
(1.(1.12))
(3.3x))
Figure 5 demonstrates that these empirical results align with our theoretical analysis. Additional experiments of different functions and different settings, and the detailed sampling strategies of these different sampling algorithms can be found in Appendix G
DELTA and FedIS outperform other biased and unbiased methods in convergence speed. We can see both DELTA and FedIS converge faster than both FedAvg and Power of-choice sampling. The larger the noise (variance), the more obvious the convergence speed advantage of DELTA and FedIS. For v = 30, FedIS can achieve near twice faster than FedAvg, and for 40, DELTA can achieve nearly 4x times faster than FedAvg.
DELTA outperforms FedIS. In experiments, DELTA converges about twice faster as FedIS in Figure 5(a) As all results show, DELTA can reduce more variance than FedIS and thus converge smaller loss.
Split FEMNIST this section, we consider the split FEMNIST. We let 10% clients own 90% data and the detailed split algorithm is provided in Appendix G Figure shows that when the data distribution highly heterogeneous, Our DELTA algorithm converges faster than other baselines.
FEMNIST and CIFAR-10. We also verify our practical algorithm FEMNIST and CIFAR-10. We summarize our numerical results Table 2 Compared with other baselines, DELTA achieves higher accuracy and has an improvement in conver- gence rate both in terms the number of iterations and the wall-clock time.
0.8
Accuraay
0.5
0.4
0.3
We also test different choices of the number of participated clients n and test on different hetero- geneity a, and observe the consistent improvement of DELTA. The detailed setting and additional ex- periments are in Appendix
FalIS
Clustar-bseed IS
FedAvg
250
rounds
Figure 6: Performance different sampling methods on Split FEMNIST dataset
CONCLUSION AND FUTURE WORK
In this work, we studied the optimal client sampling strategy that addresses the data heterogeneity to accelerate the convergence speed of FL. We obtain new tractable convergence rate for nonconvex FL algorithms with arbitrary client sampling probabilities. Based on the bound, we solve an optimization problem with respect to sampling probability and thus develop novel unbiased sampling scheme that characterizes the impact of client diversity and local variance on the sampling design. Experimental re- sults validated the superiority of our theoretical and practical algorithms compared to several baselines.
As we point out, when user attacks occur, DELTA requires some changes to be able to identify and avoid selecting users from these attacks.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Ravikumar Balakrishnan, Tian Li, Tianyi Zhou, Nageen Himayat, Virginia Smith, and Jeff Bilmes. Diverse client selection for federated learning: Submodularity and convergence analysis. ICML 2021 International Workshop on Federated Learning for User Privacy and Data Confidentiality, Virtual, July 2021.
Wenlin Chen, Samuel Horvath, and Peter Richtarik. Optimal client sampling for federated learning. arXiv preprint arXiv:2010. 13723, 2020.
Yae Jee Cho, Jianyu Wang, and Gauri Joshi. Client selection in federated learning: Convergence analysis and power-of-choice selection strategies. arXiv preprini arXiv:2010.01243, 2020.
Enmao Diao, Jie Ding. and Vahid Tarokh. Heterofl: Computation and communication efficient federated learning for heterogeneous clients. arXiv preprint arXiv:2010.01264 2020.
Víctor Elvira and Luca Martino. Advances in importance sampling. arXiv preprint arXiv:2102.05400, 2021.
Yann Fraboni, Richard Vidal, Laetitia Kameni, and Marco Lorenzi. Clustered sampling: Low-variance and improved representativity for clients selection in federated learning, 2021a.
Yann Fraboni, Richard Vidal, Laetitia Kameni, and Marco Lorenzi. A general theory for client sampling in federated learning, 2021b. URL http:/ttt/ttiiiiiiee org/ wttpaaawwww...rrraa////..1111 12211
Yongxin Guo, Tao Lin, and Xiaoying Tang. Towards federated learning on time-evolving heteroge- neous data, arXiv preprint arXiv:2112.13246. 2021.
Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown. Measuring the effects of non-identical data distribution for federated visual classification. arXiv preprint (eXXii::900000 2019.
Divyansh Jhunjhunwala, PRANAY SHARMA, Aushim Nagarkatti, and Gauri Joshi. Fedvarp: Tack- ling the variance due to partial client participation in federated learning. In The 38th Conference on Uncertainty in Artificial Intelligence, 2022.
Sai Praneeth Karimireddy, Martin Jaggi, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian U Stich, and Ananda Theertha Suresh. Mime: Mimicking centralized stochastic algorithms in federated learning. arXiv preprint arXiv:2008.0300 03606, 2020a.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference on Machine Learning, pp. 5132-5143. PMLR, 2020b.
Angelos Katharopoulos and François Fleuret. Biased importance sampling for deep neural network training. arXiv preprint 1xXiv:7006.000 2017.
Angelos Katharopoulos and François Fleuret. Not all samples created equal: Deep learning with importance sampling. In International conference on machine learning, pp.
PMLR,
2018.
Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian Stich. A unified theory of decentralized sgd with changing topology and local updates. International Conference on Machine Learning, pp. 5381-5399 PMLR, 2020.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. arXiv preprint /1/.::/8/2.06/2., 2018.
Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of fedavg non-iid data. arXiv preprint arXiv:1907.02180 2019.
Tao Lin, Lingjing Kong, Sebastian U Stich, and Martin Jaggi. Ensemble distillation for robust model fusion in federated learning. arXiv preprint arXiv22006.07242, 2020.
10

---

Under review as a conference paper at ICLR 2023
Bing Luo. Wenli Xiao, Shiqiang Wang, Jianwei Huang, and Leandros Tassiulas. Tackling system and statistical heterogeneity for federated learning with adaptive client sampling. In JEEE INFOCOM 2022-IEEE Conference on Computer Communications, pp. 1739-1748 IEEE, 2022.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera Arcas. Communication-effiiieee learning of deep networks from decentralized data. In Artificial intelli- gence and statistics, pp. 1273-1282. PMLR, 2017.
Aritra Mitra, Rayana Jaafar, George Pappas, and Hamed Hassani. Achieving linear convergence in federated learning under objective and systems heterogeneity. arXiv preprint arXiv:2102.07053, 2021.
Ihab Mohammed, Shadha Tabatabai, Ala AI-Fuqaha, Faissal El Bouanani, Junaid Qadir, Basheer Qolomany, and Mohsen Guizani. Budgeted online selection of candidate iot clients to participate in federated learning. IEEE Internet of Things Journal, 8(7):5938-599 5952, 2021. doi: 10. 1099/IT/
2020.3036157.
Khalil Muhammad, Qinqin Wang, Diarmuid O'Reilly-Morgaan Elias Tragos, Barry Smyth, Neil Hurley, James Geraci, and Aonghus Lawlor. Fedfast: Going beyond average for faster training of federated recommender systems. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, pp. 1234 1242, 2020.
Zhe Qu, Rui Duan, Lixing Chen, Jie Xu, Zhuo Lu, and Yao Liu. Context-aware online client selection for hierarchical federated learning, 2021.
Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and Brendan McMahan. Adaptive federated optimization. arXiv preprint 1rXiv:2003.00295 2020.
Monica Ribero and Haris Vikalo. Communication- effficienn federated learning via optimal client sampling. arXiv preprint arXiv:2007.15197, 2020.
Elsa Rizk, Stefan Vlaski, and Ali H Sayed. Federated learning under importance sampling. arXiv preprint arXiv:2012.07383 2020.
Gaganpreet Sharma. Pros and cons of different sampling techniques. International journal of applied research, 3(7):749-752, 2017.
Guangyuan Shen, Dehong Gao, DuanXiao Song, Xukai Zhou, Shirui Pan, Wei Lou, Fang Zhou, et al. Fast heterogeneous federated learning with hybrid client selection. arXiv preprint arXiv:2208.05133. 2022.
Steven K Thompson. Adaptive cluster sampling. Journal of the American Statistical Association, 85 1412):1050-1059, 1990.
Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and H Vincent Poor. Tackling the objective inconsistency problem in heterogeneous federated optimization. arXiv preprint arXiv:2007.0744 07.488. 2020.
Jianyu Wang. Zachary Charles, Zheng Xu, Gauri Joshi, H Brendan McMahan, Maruan Al-Shedivat, Galen Andrew, Salman Avestimehr, Katharine Daly, Deepesh Data, al. field guide federated optimization. arXiv preprint 107.::2007.06917 2021.
Xiaohui Xu, Sijing Duan, Jinrui Zhang, Yunzhen Luo, and Deyu Zhang. Optimizing federated learning on device heterogeneity with sampling strategy. 202/ IEEE/ACM 29th International Symposium on Quality of Service (IWQOS), pp. 1-10, 2021. doi: 10. 109///0005529922221111 9521361.
Haibo Yang, Minghong Fang. and Jia Liu. Achieving linear speedup with partial worker participation in non-iid federated learning. arXiv preprint arXiv:2101.11203 2021.
Hao Yu. Sen Yang. and Shenghuo Zhu. Parallel restarted sgd with faster convergence and less communication: Demystifying why model averaging works for deep learning. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pp. 5693-5700, 2019.
11

---

Under review as a conference paper at ICLR 2023
Xinwei Zhang, Mingyi Hong. Sairaj Dhople, Wotao Yin, and Yang Liu. Fedpd: A federated learning framework with optimal rates and adaptivity to non-iid data. arXiv preprint arXiv:2005.11415 2020.
Peilin Zhao and Tong Zhang. Stochastic optimization with importance sampling for regularized loss minimization. In international conference on machine learning, pp. 1-9. PMLR, 2015.
12

---

Under review as a conference paper at ICLR 2023
A
TOY CASE
In Figure 7
we give a detailed toy case to show that DELTA is more effective than FedIS.
Clicet
Cliend 2
Clienn
27
21
KH-LDRGZA
Clico
Clion 8
(a) Overview of different methods.
(b) FedAvg.
Clieet
Clicet
Client
Clien:
Clieal a
Clieni 3
(c) FedIS.
(d) DELTA.
Figure 7: Overview of objective inconsistency. The intuition of objective inconsistency in FL is caused by client sampling. When Client 1 & 2. are selected to participate the training, then the model # becomes 2+11 instead of x r_+1 giolali resulting in objective inconsixtency. Different sampling strategies can cause different surrogate objectives. thus causing different biases. From Fig 7aa we can see DELTA achieves minimal bias among the three unbiased sampling methods.
Experiments for illustrating our observation. For the experiments to illustrate our observation of the introduction, apply logistic regression model the non-iid MNIST dataset. 10 clients are selected from 200 clients to participate in training in each round. We set 2 cluster centers for cluster-based IS. And we set the mini batch-size to 32, the learning rate 0.01, and the local update time to for all methods. We run 500 communication rounds for each algorithm. We report the average of each round's selected clients' gradient norm and the minimum of each round's ''s selected clients' gradient norm.
We report the gradient norm performance of cluster-based IS and IS to show that cluster-based IS selects clients with small gradients. As we mentioned in the introduction, the cluster-based IS always selects some clients from the cluster with small gradients, which will slow the convergence in some cases. We provide the average gradient norm comparison between IS and cluster-based IS in Figure ((a) Besides, we also provide the minimal gradient norm comparison between IS and cluster-based IS in Figure 8(b)
We report the comparison of accuracy and loss performance between vanilla cluster-based IS and the removal of cluster-based IS with small gradient clusters. Specifically, we consider the setting with two cluster centers. And after 250 rounds, we replace the clients in the cluster containing the smaller gradient with the clients the cluster containing the larger gradient while keeping the total number of the participated clients the same. The experiment result is shown in Figure 9 We can observe that the vanilla cluster- blsserr-based IS performs worse than cluster- buster--asedd IS without small gradients, which indicates that the small gradient is reason for poor performance.
13

---

Under review as a conference paper at ICLR 2023
15 cluster-based IS
cluster b-aedd I5
average gradient norm
minimal gradient norm
mng
100
200
300
400
500
100
200
400
Rounds
R Rounds
(a) Average gradient norm comparison
(b) Minimal gradient norm comparison
Figure The gradient norm comparison. Both results indicate that cluster-based IS selects clients with small gradients after about half the training rounds compared to IS.
2.5
vanilla cluster-based IS
cluster-based IS without small gradients
0.7
0.6
Acunnc
0.5
0.4
03
vanilla cluster-based IS
02
cluster-based IS without small gradients
01
400
250
Rounds
Rounds
(a) Accuracy performance comparison
(b) Loss performance comparison
Figure An illustration that cluster-based IS sampling from the cluster with small gradients will slow convergence. When small gradient-norm cluster's 's clients are replaced by clients the large gradient- norm cluster, we see the performance improvement of cluster-based IS.
B TECHNIQUES
Here we show some technical lemmas which are helpful in the theoretical proof. We substitute for N to simplify writing in all following proofs. N is the data ratio of client i. All our proof can be easily extended from fæ; = 1 1 Fi(zz) to f(x)) = NN Fxx).
Lemma B.1. (Unbiased Sampling). Importance sampling is unbiased sampling. >' VF((.) no matter whether the sampling is with
E iis mps replacement or without replacement.
- (x,(z))
Lemma B.I proves that the importance sampling is unbiased sampling strategy, either in sampling with replacement or sampling without replacement.
Proof. with replacement:
E
(F((1t))
VF((Te))
Σ
F.
E
VF
V
$)
72
mpf
11
mp'
7
mp!
SESS.
iES.
iES.
p
VFi(Te))
=
1
vf(xz) vf(x,),
mpl
1=1
iES.
(13)
14

---

Under review as a conference paper at ICLR 2023
without replacement:
E
Σ 1 VV.(a))
Im
1
VF((Er)
-
-
Σ
B(lm)
E (Pi(z.))
71 S
mi:
71
1=1
mip
11
1=1
mp
m
m
Im)
E
vFi(xz))
n
Pi
(z((
71
mpf
n
mpii
1=1
1
1 m
npi
VF((x))
(F((z)) Vf(x))) (14)
mpl
where Im - is x E St. [1 0 otherwise.
In the expectation, there are three origins of stochasticity. They are client sampling, local data SGD, and filtration of 2t. Therefore, the expectation is over all these randomnesses. Here, S represents the origins of stochasticity except for client sampling. Rigorously, S represents the filtration of the stochastic process { 1.., J at time f and the stochasticity of local SGD.
Lemma B.2 (update gap bound).
x²
=/\ - B(.)(= (15)
T1
mp,
iES.
where the first equation follows from E[r E[=)] B[2?] [B(x)] and Lemma B.1
To increase readability, we give detailed derivation of the Lemma B.2
E ( =E (IV |
ff(x)))
(s) -2E (1 [I)
+ (IV)((=))) (S) (16)
where E(x S) means the expectation on over the sampling space. And we use E (Iv)())) = (x(x)) and E (IVV ( 5) = /V (IV [x=)) a constant for stochasticity S and the
expectation over constant is the constant itself.)
Therefore, we conclude
E ( - 1s) = EE (IVF(2)))
[z)) S (IVf(E)) > 11s
(17)
We can further take the expectation on both sides of the inequality according to our needs, but without changing the relationship.
The following lemma follows from Lemma 4 of Reddi al. (2020). but with a looser condition
Assumption 3 instead of og bound. With some effort, we can derive the following lemma:
Lemma B.3 (Local updates bound.). For any step-size satisfying TIL following results:
ST. we can have the
E El xtl12 < 5K 4K 20K + 1) (2:)).
(18)
15

---

Under review as a conference paper at ICLR 2023
Proof.
Bellai xzll 1|?
_ell=/2n-1 - It - 1|2
Ee Eellzi,N-1 - It - M2 (9h, - -
1
$ +
24
2K -
+ 44KE, [| ( P. K K-1) VB V
< (1 + 2k -
] ]Bel| k - 11 1102
4K 14K1/00. 4K (1/
1
< (1 + K
1 - o
21
4K oK 4K(A +
(19)
(20)
Unrolling the recursion, we get:
k-1
Eg | - xell?
Σ
+
)2 [n + 44Kn + 4K(A2 V))l [(x))]
(21)
p=
$ (K - 11 (1
K - )k
1
[n: + +4K + 4K V))
(22)
s 5KKnioo + 4Kk) 20K + +11))(
(23)
n
C CONVERGENCE OF FEDIS, PROOF OF THEOREM 3.1
We first restate the convergence theorem (Theorem more formally, then prove the result for nonconvex case.
Theorem C.1. Under Assumptions 7 and sampling strategy FedIS, the expected gradient norm will converge to stationary point of the global objective. More specifically, if commumicttin rounds T is pre-determined and the learning rate and ny is constant learning rates, then the expected gradient norm will be bounded as follows:
F +
min F)
(24)
LE[T]
CTyLKT KT
where F (2ro) f(x.), M of + 4Koz and the expectation is over the local datasets samples among workers.
Let TL < min (1/(8KK), C),, where C is obtained from the condition that 1022
LAn +1)
1)mî
7 > ,,and n S L)) then holds that:
2n
1 5u 1.2K m
mi L
LAML V
(o 4Kog)
o7 +
9f))
(25)
c
2m
2m
2nK
mp!
where C is constant that satisfies (22 + 1)
L'nK(A? 2n
ML
0, and
V (n 9:) = E'll 1 - 112
Corollary C.2. Suppose пL and n are such that the conditions mentioned above are satisfied,
MT VTKL and 1 O (VKn) and let the sampling probability be FedIS 82 Then for
sufficiently large T, the iterates of Theorem 3.1 satisfy:
(
ot Koy
+ of, + 4Kog
min V/ T
(26)
VnKT
KT
16

---

Under review as a conference paper at ICLR 2023
Proof.
(o1) [x(((1411 - f(x)) (. x1)) + -
- -
=s(x)) + (z.()))) B. + (VKK((()))) + L " [1 1.17
- ( -- m. + t"1 B B.1..
Aa (27)
where (al) follows from Lipschitz continuous condition. The expectation is conditioned everything before current step k of round t. Specifically, it is over clients' sampling, local data sampling, and the current round's model zz- Firstly we consider A
A1 = (Vf(2), EA + KVK
K-1
(x())) E.I
nLSi, + nL V(((a))))
SSc
mp
LES.
km= 0
K-1
(22)
Vf(a.), E.
V + +,.
K=U
K
VnLKVS(a))
VIL E
-
VK
i=1 k=0
K-1
(03) Mr
+
E,
Σ
-
2
2K
1=1
k=0
nL
E,
2K
(o4)
111. K
[V
+ T11 12
2m Σ
m K
Ee |0 - xx
11.
Ezl
K
2
2K
m
i=1 k=0
1=1
k=
M1
10K I, (12 +1)) [[+f(=))]1++
51.210
K2 + 10
2
2
K-1
E,ll
Σ VF(
(28)
2K
i=1 k=0
where (a2) follows from Assumption and Lemma B.1
(a3) is due to (x.1)
[|| + ||r| || =1|²] and (a4) comes from Assumption
17

---

Under review as a conference paper at ICLR 2023
Next consider A2. Let of
Ek= Ph.s
Ekso (P.
A2 = Ee E 1|
K 1
1
E
AL
Pi,k
T1
map
VES.
Omm
K-1
K 1
1
m/.
E,
Pi,k
9i,k
mp R=
1=1
k=0
K 1
Rt
Da (1(
0=
"I V
9
mp
m
K
+ VF((2/))11
V
map:
K
K 1
11
(l - VRR(EN))1
+ E
112
1=1
k=0
2 V mp:
9
+
K
o2
+ M
1 m
Σ
K-1
V F (z 111
(29)
The third equality follows from independent sampling, Specifically, for sampling with replacement, due to every index being independent, we utilize E|[æ{ +... In 1| = B[[|>] 1 +... + ||,,, 11 For sampling without replacement:
m
9
12
(30)
72
mp:
m
m
1
m
E
11
9
12
(31)
n2
mp
m
m
9
1 1 =
x P[L = 1)
(32)
mp
m
m
(
9
1. =0
P(4 0)
(33)
mp
m
1=1
1 m
93
9
(34)
71
mp
m7
1
(35)
mp
From above, we observe that it is possible to gain a speedup by sampling from the distribution that minimizes V( mp: g.) Moreover, as we have discussed before, the optimal sampling probability
|l P. Σ || For MD sampling (Li al. 2019), which samples according to date ratio, the 9:1 1:l
optimal sampling probability is pl.,- Σr "
where q. 24
18

---

Under review as a conference paper at ICLR 2023
Now substitute the expression of A1 and A2:
Beff(r(+1) f(z)) - k [V + (V)( E, KVVI(()) (xX + T.
"f "
f(()) MLLK (
5m T22
100 K (7
(0 + +4K0))
1 12ni,KL KL
0L
Li ni
V(
9
ML
In
Ee
1
K-
Σ
(..(
2m
2n
mp:
2K
m
5m
L2K²
s7 n KL
L V
L
$ f(()) - cmLKK (f(x))
(oî + 4Kog))
+
o
+
9
2
2m
2n
mp,
(36)
where the last inequality follows from
MiL 2K
Lay n
2 0 if nm S 1 and (a9) holds because
KZ
there exists constant c > 0 (with some ar satisfying
100 - K2 R2n (A² + 1) >>> 00
Rearranging and summing from t = O,...,T 1,we have:
cmpL KE V/ s f(x)) f(TT) + T(mLK)Ø
(37)
Which implies:
min B (((x))] < fo f. TE(T]
cmmr, KT Φ
(38)
where
4
5 KI2
(o + 4Ko8)
Mi of
2m
LAMi v
2nK
"mp
Ril
(39)
C.I PROOF FOR CONVERGENCE OF FEDIS (THEOREM 3.1 UNDER ASSUMPTION
For comparison, we first provide the convergence result under Assumption 4 The Assumption) is formally defined below:
Assumption 4 (Gradient bound), The stochastic gradient's 's expected squared norm uniformly bounded, i.e., V 0l. < G2 for all and k.
First show Assumption 4 can be used to bound the update variance V
(mp Φt). and under the
sampling probability FedIS 80
of
E
El Ew.)1
K2G²
mp
m
m
(40)
While for using Assumption variance:
instead of additional Assumption we can also bound the update
K
V
<
E
V
K
VVV (o Ex.)
mp!
m
1=1
N=
Rm
R² 0
+ k2 2
1)
(41)
19

---

Under review as a conference paper at ICLR 2023
We replace the variance back to equation (36
E,If(x++1]] - f(x,) - mi [V + 17 (V.) + KV + "EE,1AA
+ 5mm L22
S f(()) - mILK
10L K2
1/ (1)++ |++[(
(02 + 4Ko2)
2
2
0%
V(
91)
MIL
LIpaLL
Ee
K-1
VF
2m
2n
mp:
2K
2
m7
1
Lepr.K
+ +1)
5mm 1,2
$ {xxe) - -MIKK
K
10T.2K2m1
(12 +1
+
(o) + 4Kog)
2n
2
KL
2m L
K2 0
M7L 2K
Lap
E₁
1
K-1
2n
2
R=0
(42)
This shows that the requirement for T7L. is different. It needs that there exists a constant c 0(with some MT) satisfying 2 (42 + 1) - L > > 0. One can still guarantee 2n
that there exists constant for 1js. to satisfy this inequality according to the properties of quadratic functions. Specifically, for quadratic equations - -101.2 10L=*=(A*++>inr))
LnK[A' f|r. + 1. we know
- - 1) < 0, [1](A++1) and 1 > 0. According to the solution of quadratic equations,
we can make sure there exists a AL > 0 solution.
O ( (viRT)
and 17 = 0 (v (VKn)
Then can substitute equation (36) by equation
42 and me
we get the convergence rate of FedIS under Assumption
min [[V so ( (PE-T) E
+0
(
of (vnKT)
M T
Koē VnKT
+0
+0
+o
(43)
order +
D CONVERGENCE OF DELTA. PROOF OF THEOREM 3.3
D.1 CONVERGENCE RATE WITH IMPROVED ANALYSTS METHOD FOR GETTING DELTA
As we see FedIS can only reduce the update variance term in +. Since we want to reduce the convergence variance as much as possible, the other term d and de still needs to be optimized. However, it is not straightforward to derive the optimization problem from 4. In order to further reduce the variance in & (cf. 4. i.e., local variance (ar.) and global variance (aa), we divide the convergence of the global objective into a surrogate objective and an update gap, and analyze each term separately. The analysis framework is shown in Figure [0]
While for the update gap. as inspired by the expression form of update variance, we formally define it as below.
Definition D.1 (Update gap). order to measure the update inconsistency, we define the update gap:
X = E [[//)()))- (((e))
(44)
Here the expectation is over all clients' distribution. When full clients participate, we have xi The update inconsistency exists as long as partial client participation.
The update gap is direct embodiment of the objective inconsistency in the update process. The existence of update gap makes the analysis of global objective different from the analysis of surrogate objective. However, once we promise the convergence of the update gap, we can re-derive the convergence result for the global objective. Formally, the update gap can help us to connect global objective convergence and surrogate objective convergence as follows:
E| (=))) = B|/J((>))"" +x².
(45)
The equation follows from the property of unbiasedness, see Lemma B.1
In order to deduce the convergence rate of the global objective, we start from the convergence analysis of the surrogate objective.
20

---

Under review as a conference paper at ICLR 2023
surrogate objective V/(z))
Lemma 8.1
Global objective (=,)
BIVS BII
Lemma
Theorem
Objective Gap X:
x² S E/|V /
4.3
bounded convergence of qurrogate objecting
Convergence variance of global objective
Convergence variance surrogate objective
eq()): = A Ago + Ag Var( mag (
eq(7) or eq(8):
Thearom
B1 Σ rq o7 + Bg X mp SD
Carallar
corollary 42]
FediS: pl
Egia Io]
DELTA: p/
En y (8)(()) ([te)-(([]]]))))) v/(e]P Optimizing the variance term wint p/
/o PMe) V/tef ro
Optimizing the variance term w.Ft P
Figure 10: Sketch of theoretical analysis flow (Compared with FedIS). The left side represents the analysis flow of FedIS, while the analysis of DELTA is shown the right. The sampling probability differenec comes from the difference in variance.
Theorem D.2 (Convergence rate of surrogate objective), Under Assumption 73 and let local and
global learning rales y and yı. satisfy 1r. <///2OKL v EP- V mis) and qpr 1/KL, the minimal
gradient norm of surrogate objective will be bounded below:
minigm E [m))
SMIRT
6-
(46)
where p0= ((ro). f = f(x,), ) the expectation is over the local dataset samples among workers. is the new combination of variance, representing combinations of local variance and client gradient diversity.
For sample without replacement:
AL 2mn
Em p.
(o2,
Lnc Em m
(47)
For sampling with replacement:
kt. 2m
+ (o2, 4KC8,) + Lagn Li=1 mp oi.
(48)
(..,) - V (xx))l, ē is a constant. The proof of Theorem D.2 is shown in Appendix D.2 and Appendix D.3 Specifically, the proof for sampling with replacement is shown Appendix D.2 while the proof for sampling without replacement is shown in Appendix
where Sa.; represents client gradient diversity: Ca.i =
Remark D.3. We notice that there no update variance in & but the local variance and global variance remain in Furthermore, the new combination of variance & can be minimized by optimizing w.r. sampling probability, is shown later.
Derive the convergence from surrogate objective to global objective. As shown in Lemma B. unbiased sampling promises partial client updates in expectation are equal to the participation of all clients. With enough training rounds, unbiased sampling can guarantee that the update gap x2 will converge to zero. However, we still need the convergence speed of x² recover the convergence rate of the global objective. Fortunately, we can bound the convergence behavior of x² by the convergence rate surrogate objective according to Definition D.I I and Lemma B.2 Therefore, the update gap can achieve at least the same convergence rate as the surrogate objective.
Corollary D.4 (New convergence rate of global objective). Under Assumption I and based on the above analysis that update variance is bounded, the global objective will converge to a stationary point. Its gradient is bounded as:
mineer (+x))1 = minterr El /( + Ellxill $ mineer 2
-- ep9 KT
(49)
21

---

Under review as a conference paper at ICLR 2023
Under Assumption 3 and the same conditions as theo- 3.1 the minimal gradient norm of surrogate objective will be bounded as follows by setting TL = VTKL and nyKK Let local and global learning rates lt and au satisfy I'
Theorem D.5 (Restate of Theorem 3.3
Kn
V20K 1/ E mpf
and mM S KI- Under Assumption 3 and with partial worker parlicipation, the sequence of outputs Ik generated by Algorithm satisfies:
1.
min E V/
$ C
(50)
EETT]
CT
where F= - - and the expectation is over the local dataset samplings among workers. c constant. ÇG.i is defined as client gradient diversity: GG,i = Fi (x(x)))
For sample with replacement: H
E (o
4K 4KC2.) +
LUL E m
oZ
2m
2n
For sampling without replacement: &-
E (o 4K 4Z
LALa E
m Remark D.6 (Condition nL). Here, though the condition expression for Te relies on a dynamic sampling probability pi. we can still guarantee that there constant U₁ satisfies this condition.
2mn
2n
Specifically, one can substitute the optimal sampling probability 1 25 Vo
P.
Varka CassG,tton tooa
back to the above inequality condition. As long the gradient (F(( is bounded, max, , mins Ca,
1 E1s Vaisa, tazgi.. Varca, +as0
we can ensure
m Eis
S G. therefore
2 2C, where G and C are pos-
3T90 Vaisa, to2e2...
20(A*11jKL,
2
Vaist, storatt
itive constants. Thus, we can always find a constant Ti to satisfy this inequality under dynamic sampling probability pt:-
Corollary D.7. Suppose ai and y) are such that the conditions mentioned above are satisfied, and 1j O (VKn). Then for sufficiently large T, the iterates of Theorem 3.3
VTK.
satisfy:
F
of
oZ + 4K (0L
min E V S 5
+
+
(51)
EE[T]
VnKT
VnKT
KT
Lemma D.8. For any step-size satisfying nT. S SLK
1
we can have the following results:
E El 12l1 < 5k + +Knnisa.) 20 +
f(
(52)
where Sa.s = (z.) (xx))) and the expectation is over local SGD and filtration of me. without the stochasticity of client sampling.
Proof.
E Eellar, 2zel" 11?
Eelloi,A-1 Ft -
Bellvi,--1 - Ice - 1/1 (gi - -
1
< (1 2K Bell=z
+ 4K E, Il VV
V V (-)
V 1
1
$ (1 + 2K -
4K 2 SG.3
4Knj
2 (=
1
< (1 +
E|
2, 2 .
4Kn 4K(A2 + vf(z))
(53)
K -
(54)
22

---

Under review as a conference paper at ICLR 2023
Unrolling the recursion, we get:
1
E, E|1=2,1 1 2z
(1+
)2 [m
(55)
K
p=0
K K-1 k - 1
s (K- (1 (1+
inoo +
(56)
- 5K(noo7 4k) + 20K + 1(
(57)
In Section D.2 for sampling with replacement is shown in Appendix D.2 while the proof for sampling without replacement is shown in Appendix D.3
D22 and Section D.3, we provide the proof for Theorem D.2
Specifically, the proof
D.2 SAMPLE WITH REPLACEMENT
min E| (()))) v fo fo
1
-
(58)
TT
cmp KT
C
where 5
k22 2m
El=1 pl
(of + 4KC
+
Loc 2n
E m²pp oz.
1
Proof.
(a1) f(2x+1) S f(x1) + (v)(z)), Exle11
- zdl) + _ Eoll|ze+1--2 - 211
=i(xz) + (Vi(zz), + mmpl:/AAmm....ii -ww. + "/ A. 12
= =((x)) mack vf(zz) + n (Vi(at)) + ((KK((t)))) + - T2 E.11
Aa
(59)
Where (al) follows from Lipschitz continuous condition. Here the expectation is over local data SGD and filtration of x4. However, in the next analysis, the expectation over all randomness, i.e., client sampling is included. Firstly consider A
A1
v
+ EL
v f(ze), EE
Σ
nL9i, k + NLKKKE ((xi))
mep
Ve
k=
K
(x2)
V V(Cr), E.[
n (F( + nt AV
S
mp
iESt
k=0
V KmL ff)t)
ML
E,
VF(()(,))) XVi(aa))
VK
n2
mp
ies,
k=
(03)
KiLL (2
+ 2K
Er
1-
|
V(((T))) + +KV(()I))
mp
iES.
k=0
K
1T Egll
1
(60)
2K
71
mp
K=
23

---

Under review as a conference paper at ICLR 2023
where (a2) follows from Assumption 2 and (a3) is due to (2. = |||=||2 + +llvll - || yll?
for
(f(xs and y K Eies, mp: Σ KK1
vTL 1.
k=0 (F(() + KVf(=))).
In order to bound A1, we need to bound the following part:
Ed Σ
(=(
n
mpp
iES,
k=
1 Σ
= Bell
72
mp
72
mp
iES.
k=0
iES
k=0
(n4)
K
Eill (VF())))) VF
71
mp
X.S
K
K-
1
(
S)}
mp;
k=0
K
TR
p -VF((1)))VV((())))
n
VES,
K=U
K
E, (F(( [F(xx)11
m²pp
km
(05)
K2
E
Elaa 12
m
Pi
1=1
(00)
L²K²
(5K + 44 + (A2 + 1)mi VV
m2
1=1
5L2K3 3 ni.
m
fo + 4Koa) + 20L K 1 (A2 1)
Σ 1
(61)
m²
m²
where (a4) follows from the fact that E m + ...
+ xnll2 S nE (1|:011 112 .... + 11xm,119) (a5) is due
to Assumption [ and (a6) is due Lemma D.8
Combining the above formulations, we have:
A S
Kyn 2
[f))2))
W
5I,23, Vi
_1 (oL 4K(2,)+
m
201.2 K'1 1,,,, (A2 +1)
m
vf(x))]1
2K
m²
m²
pi
K-1
ML
F.ll
1 Σ
(62)
2K
SES.
k=0
24

---

Under review as a conference paper at ICLR 2023
Next consider to bound Ag:
A2
A, |
K-1 1
R
mpp
VESI
k=
K-1
1
1 Σ
Br
Mi
V
F. (1
+ t E
VF (1t,,)
17
mp!
mp!
n2
mp
IES.
K-1
K-1
2
111 n
E
(F,(((()))
+ +1 E
mp
mp!
mp!
Om
iES:
km0
K-1
K
2
nr. n
E2
E
(F((2) )
15
+ m E
P (zt
mp,
mp
k=
iES.
k=0
nr. n2
Σ k=0
E2
||
Σ
(E(,))))
m2pf
mp
iES.
k=
(a7)
K 7
m
Σ iES.
K Σ k=
1 + 2 Er
(63)
m pf
mp:
where S represents the whole sample space and (a7) is due to Assumption 2
Now substitute the expression of A and Ag and take the expectation over client sampling distribution on both sides. It should be noted that the derivation of A, and A in above is based on considering the expectation over sampling distribution:
f(1(11) S fz())) - ML
\f(xi)
+ Tn (Vf(z), A, (. 1|
+
2 E.
L
S f(+) KYML
1
m 10K22 (A2 11)
E₂
Vf(a.))
||
+
5T.22
"1
m
1
(al + +K(())
2
m²
2m2
p
(64)
Iniin² K
m
1
of.
MIL
Laj
Eg
1
K
2n
m²pi
2K
2
T2 iES.
mp!
(a8)
10,
+ 1)
3L2K2mhn1 1
5 f111) - KiIs.
E.
V )1
(or. + 4KC2,
11.
2m2
1=1
(65)
Tafi K
Σ m m2pi of
m
1
+ 2n
(a9)
5L2K2m ""
Σ -110 (oz 4K((.)
m
L K
m
[(x))
mm F. (1=)))1
oz
2m2
2n
m2
pl
1=1 (66)
where (a8) follows from
mL 2K
2
2 0 1M S RI:
1
and (a9) holds because there exists a con-
2
10K² n7 L2(A4+1)
stant e > 0 satisfying (1
0f
n²²
v 20 /20AA2+1KKI
> mp
Rearranging and summing from t t= =00,... -......" T 1, we have:
((x < f(xo) - f(xr) + T(maa)
55. Knf
(o2 + + +
Tm m
2 o
1
2m²
1=1 pt
2n
1=1
(67)
25

---

Under review as a conference paper at ICLR 2023
Which implies:
min E (=xx))1 TE
fo -o-fa fa cmpr KT
$
(68)
where +-
Kn 2m22
El= } pi
+ + + Lern Di=1 m2 o2.
D.3 SAMPLE WITHOUT REPLACEMENT
min E V [xx))111 v fo -e TT
1 -
(69)
KT c
where E-
5LL 2mn
Ei=1 pl
(of. + 4K(
+
Loig 2n
Ei=1 mapp 07.
Proof.
f(1141) S f(x)) + (Vf(z)). - xi)) + Ee 1el1 - x2ll]
2
= f((x)) + (Vi(az), + +m. (ma -m, + ~ " R 17
f(xz) muk vf(zz)
|| + 7 EdA. + + + + Eg E.1..
L
A2
(70)
Where the first inequality follows from Lipschitz continuous condition. Here the expectation is over local data SGD and filtration of z4. However, in the next analysis, the expectation is over all randomness, i.e., client sampling included.
Similarly, we consider A₁ first:
A
V (art), E, + nI KV f(x)))
V((e)) R.
m... + nr. Nr.KV
SSt
mp
VES.
E,
nL
1Pt
mp
iES,
K-1
VKnLVf(z))
VIL VK
E,
Σ
VF +
mp
ieS.
k=0
KTL
MI
VF(((L) +KV}(z))
2
2K
T1
mp
iES.
a 2K
E,
VF (xt.M)
(71)
mp
iES.
K=U
Since are sampled from S, without replacement, this causes pairs 2,12 to no longer be indepen- dent. We introduce the activation function by:
{ is x St
Im
00 otherwise.
(72)
26

---

Under review as a conference paper at ICLR 2023
Then get the following bound:
Ex
( KV
mp
iES.
m
vF((3),)) 1
K
E₁
4m
Vi((
mpi
72
mpi
k=0
(61)
m
E
K-1
(V -VE(E)))
112
mpi
K-1
Et
I
Vi, (a(1 - VF,, (12)
I
(VF) - V (2x)
11
mpl
mpla k=0
11
k=0
m
E,
Im
1
(
1 VFi(()))
mp
mpi
k=
2
E2
(F((
Imm 1 [
P( =1)
(73)
2
mp!
mpi
K-1 vii(a),))) mpf
2
1 Vii(ot))
+
E,
IIm 0
x P(Im = 0])
mipi
k==
K
K-1
2
m7
E
E
(F(()),))
Σ
n
mpi
mpl
1=1
k=
k=
(b2)
L K
K-1
m
Σ
Elaak xel12
mn
Pi
(ba)
L 2
I
m
1
m (o + +00 + +D2 1
Σ
5K
(74)
n
m
pi
pi
where (b1) follows from || E> t/l2 Eme()) ||ta|1 + Eie tt) 1 Eiem) ml|t//2
Eifj ||+, - t, 12 (where (c1) is due to (z. v) = 1 ||||| + ||v/l - || - y ). and (b2) is due to
E||21 + +... + z.,ll 2| < nE (1 1| +... 1|) and (b3) is from Lemma D.8
Therefore, we have the bound of A₁:
A S
Km
(1))) +
LLLK
5K
T
1
(ol + +KK2,)
+ 20K + +1)2211// 111
-
2
2n
m
1=1
K-
2
7 F
1 Σ
F (xf
(75)
2K
n
mp
IES.
k=0
27

---

Under review as a conference paper at ICLR 2023
And Ag has the following expression:
Ag
E/ |
K-
E
mp,
iE
k=
K-1
n Br
Ki,k
1
V (F(
+ 1 F
1 Σ
Σ
11
mp:
mp!
ni
iES. mp
K-1
K
1
EE
1m
LgL - vE((((,)))
+ Lr
112
my!
mp
k=0
EE
k=0
K
K-1
E2
m
mpf
(g', - (..(
M E
mp!
V
Fi
k=0
km0
K-1 Σ
n
B
Σ
(=(()()))))
+ +n
Σ mp
(
mpf
k=0
iES.
k=0
K S m
m
o + n
Ex
Σ
K-1
(
(76)
mPpp
n
TE iES.
k=
Now substitute the expression of A and A2 and take the expectation over client sampling distribution on both sides. It should be noted that the derivation of A, and A2 in above is based on considering the expectation over sampling distribution:
|| + ME, (Vf(z), A. + mKVi(z))
I.
f(z(11) S f(x) ML
+ 2
(14) S
1
10 + 19m2
2K 2x22mm, L2
(xx)
-ME K
2
E2
(x 12
(oz (ok
mm
2nm
Lni K
1
MIL
E,
2n
Pi
2K
2
71
mp
iES.
k=0
2K
L
m
Ln
K
m
1 p oL
S f(x)) - ( [V
+
(o2
+ 4K (
+
2ne
pi
2n
(77)
Also, for (b4), step sizes need to satisfy
mg 2K
Lnjnn
2 Of mm S 1
KL. and there exists constant
>>00 0 satisfying ( 10 (A*+))
Σm
1
> >>>> Oi
m7
pl
220A244TjLL / / !
Rearranging and summing from t t= ==....,, 1.we have:
cmp (nnKKE]j((x))]] s ((x0) - f(xT) + T(mi
(78)
Which implies:
< fo fx
1
min E V
(79)
(E[T]
emni KT
where क-
Σm
(o + 4K(2.) +
Lاgg Σm map 07
2mn
P.
2n
28

---

Under review as a conference paper at ICLR 2023
E PROOF OF OPTIMAL SAMPLING PROBABILITY
E.
SAMPLING PROBABILITY FEDIS
Corollary E.1 (Optimal sampling probability for FedIS),
min +
s.t. =1
pi
pf
1=1
Solving the above optimization problem, we give the expression of optimal sampling probability:
19
(80)
where of - Ek=O 9k. is the gradient updates sum of multiple updates.
Recall theorem 3.1 only the last variance term in the convergence term 4 is affected by sampling. In other words, we need to minimize the variance term with respect probability. We formalized it as below:
min P PE Df
V mp,
of +
min pf
(81)
m
This problem can be solved in closed form by the KKT condition. It is easy verify that the solution of the above optimization is:
p
Vi E 1.2...., m. m.
(82)
E Σ gi,kl
Under optimal sampling probability, the variance will be:
Σ
TI
V
E
E
(83)
mp!
m
m
km
Therefore, the variance term is bounded by:
E ( S K2G²
(84)
my
Remark: If the uniform distribution is adopted p m stochastic gradient bounded by Σm |le.1
it is easy observe that the variance the
According to Seuchy-Schwarc inequality,
m
l 11 D. |ل -i E
Tr
1 ll@:ll)²
21,
(85)
m
m
This implies that importance sampling does improve convergence rate, especially when |9
19g
m.
E.2 SAMPLING PROBABILITY OF DELTA
Our result is the following form:
min E Vf So f. EE
+
(86)
CmMLK KT
it's easy see that the sampling strategy only affects + for enhancing the convergence rate, we need to minimize & with respect pf. As is shown, the expression of क in with and without replacement
29

---

Under review as a conference paper at ICLR 2023
similar, only differ in number and Here we just consider with replacement case. Specifically, we need to solve this optimization problem:
min Pi
- (
K 2m
m
(o (KC +
LM 2n
Σ
m
p² L.i)
s.t.
M
pi
1.
Solving this optimization problem, we can find the optimal sampling probability to be:
/ 5 + 4KC2.) + -
(87)
E 5KIn + 4KC).) 2
For simplicity's sake, we rewrote the optimal sampling probability as
aaie. + a227..i
(88)
Ei Vaisa.. + t22
where = 200 = Liy + 2.
Remark: Now we compare with the uniform sampling strategy:
E1=1 v 01 2 + a22
Lap
T DELTA =
(89)
2c
m
For uniform Pl
Tapp Eiml ( ago
Puni form
(90)
2c
m
According to Cauchy-Schwaad inequality:
2
2
Σm
+ (a
E Seivani /aites + azo
m m mm
( a2o
2 1
2
t L=
/aiGa. t22
(91)
implies that importance sampling does improve convergence rate (importance sampling- based approach might be n-times faster in convergence than uniform), especially when (E Va t << m.
EE (Vare,)
F CONVERGENCE ANALYSIS OF THE PRACTICAL ALGORITHM
For providing the convergence rate of applying the practical algorithm, we need an additional Assumption:
Assumption (Local gradient norm bound). The gradients F(())) are uniformly upper bounded (by a constant G > 0) F(()) < G² Vi.
Assumption is general assumption in IS community to bound the gradient norm (Zhao & Zhang 2015) Elvira & Martino 2021] Katharopoulos Fleuret, 2018), and it also used in the FL community to analyze convergence (Balakrishnan et al. 2021 Zhang et al. 2020). This assumption tells us a useful fact that will be used later:
F Er,)) / F. 5 5 U for all and k, where subscribe refers to the lasted partici- pated round of client i, and U a constant upper bound. It tells us that the client's 's gradient norm change bounded.
30

---

Under review as a conference paper at ICLR 2023
In general, the gradient norm tends to be smaller training progresses, thus leading the (..F,......./VEEE.
Sa,a)] goes to zero, Even if there are some oscillations in the gradi- ent norm, the gradient will vary within limited range and will not appear to be infinite.
Based on Assumption 5 and Assumption 3] we can re-derive the convergence analysis for both
convergence variance (4) and क (47). ). As for Assumption 3 (R) ( & (4² + {+))
oG), we use aG and aG, instead of unified ag for the sake of comparison.
Specifically, +- 1
Gnf L2K
DE + 4Ko2) +
wi o2. +
Eina
ming 9.)1, where of
c
2m
2m
2n
EKE (ii( (k.S). With the practical sampling probability yf of FedIS, the term
m
m
v
mp: 2b
9
Sll EI
Σ 931.
(92)
mp?
m
mp,
According to Assumption 5
we know
0 12
F. oo (F
SUa
Then we get
Eis
m
m
K
gi
1
1
S m
U E
V
Filk 31
mp,
171
K
U
m
K
E
B
F2
(T
(93)
m
kmm
Similar to the previous proof, based on Assumption
3
we can get the new convergence rate:
min FIV O ((xxt) (E[T]
+0
o.. VnkT
M²
(94)
T
VnKT
order of
where M = o 4Ko
Remark F.I. It is worth noting that F. (Lk)) Ea,k) is usually relatively small
because the gradient tends to go to zero as training processing. means U can be relatively small, more specifically, U < 1 in the upper bound term O the practical algorithm is better than the theoretical algorithm because the ag is different, stated at the beginning. Usually, dG.s of the practical algorithm is larger than OG.b, which also comes from the fact that the gradient tends to go to zero as training processing. Besides, due to the presence of the summation over both i and k. the gap between ag.s and oG, is multiplied, T.- Thus, the practical algorithm leads to slower convergence than the
KU aa.
However, it does not mean
VnkT
and o..s/a..t ~ m² K2 1 theoretical algorithm.
Similarly, as long as the gradient is consistently bounded, we can assume VF((0)) vf(=))// - vf(x,)) & Un < and |0L,//L,sl < Ug S Ú where of,s = E [[ [2,, ( (F.(=.)]] for all i. Then we can get similar conclusion following the same analysis on +.
1 (ai5a,, a20 where aj and 02 are constants defined in For the sake of comparison of different participated rounds s and I, we rewrite the symbol as C2 and
Specifically, +-
L Σm
p.
L..- Then use the practical sampling probability p of DELTA, and let R we have
v aa + a2o 2
LaE 2m
m
TmE.
(?)2 R
m
Tmp
m
R R
2
き =
(
R
R
2m
c
2m²c c
1=1
==1
j=1
j=1
2
LALL 0
m
LTL 02
m Σ
LAL
R Σ
R3
R
<
i2m m
(R
2m²e
2m
2m
1=1
1=1
1=1
LaL (5K + 4KC
<
(95)
2c
31

---

Under review as a conference paper at ICLR 2023
Yower sfchenc
-1
1550
200
52
30
3000
250
150
12
21
A
8, b
20
(b) A
8, b
2,
30
-1
roverste storcie
Fonis of who
D0LTA
26
76 10M
19th 198 172
20
126 1an 1900 wands
760 100
1960 196 1792
(d) 10, 1, 20
(0)
10, 1, 30
A 10, 1,
Figure 11: Performance of different algorithms on the regression model. The loss calculated by f(x; v)
log( ( ||
we report the logarithm of global loss with different degree of gradient noise v. All methods are well-tuned, and we report the hest result of each algorithm under each setting.
Therefore, compared with the theoretical algorithm of DELTA, the practical algorithm of DELTA has convergence rate follows:
UZoL. VnkT
T. 4KU
mineemy E| [ S
8-C
+
+0
SG
VnKT
KT
(96)
order of
This discussion of the effect Ü convergence rate is the same U in Remark F.1
G EXPERIMENT DETAILS.
G.1 ADDITIONAL EXPERIMENTS
Synthetic dataset We demonstrate the experiment different functions with different A and Each function is set with the noise of 20,30,40 40 to illustrate our theoretical results. As for constructing different functions, we assign = 8, 10 and b =2, respectively to see the convergence behavior of different functions.
We choose 10 out of 20 clients each round. All the algorithms run in the same environment with fixed learning rate of 0.001. We train each experiment for 2000 rounds to make global loss have a stable convergence performance. We display the log of global loss in Fig [1] where the Power-of-Choice is biased sampling strategy that selects clients with higher loss (Cho et al., 2020).
We also show the convergence behavior of different sampling algorithms under small noise, as shown F2g
And to be consistent with the cross-device scenario, we further expanded the number of clients from 20 to 200, keeping 10 clients selected to participate in each round. The results in Fig 13 show the effectiveness of DELTA.
The implementation detail of different sampling algorithms The power-of-choice sampling method is proposed by Cho et al.) (2020). The sampling strategy is that it first samples 20 clients randomly from all clients, and then chooses clients. FedAvg samples clients according to their data ratio. Thus, FedAvg promises to be unbiased, which is given in Fraboni et al. (2021at: : Li et al. (019)) to be an unbiased sampling method. As for FedIS, the sampling strategy follows (82). And for DELTA, the sampling probability follows (II). For practical implementation FedIS and DELTA, the sampling probability follows the strategy we described in Section 4
the 20 clients with the largest loss as selected
32

---

Under review as a conference paper at ICLR 2023
yourrs moie
pover of
DOL7A
DELTA
-10
1150
220
123
70
3000
250
150
251
12
21
1200
126
(a)
10
(b)
(c) 1
Soaer more
Dover code
FedS
250
300
721
2000
120
1900
175t
200
(d) V 0.5
(e)
0.1
Figure 12: Performance of different algorithms on the regression model with different (small) noise setting.
boog twrt
Keing prANericii CELTA
Sonyy D1174
10
-25
225
3731
1250
(a) V 30
(b) V/ 20
(c) V/ 10
-30
(d) V 5
(e) V
Figure 13: Performance of different algorithms on synthetic data with different noise setting. Specifically. for testing the large client number setting, each round 10 of 200 clients selected to participate in training.
Split FEMNIST In this section, we consider the split FEMNIST. We let 10% clients own 90% data and the detailed split data process is shown below.
Divide the dataset by labels, for example, divide FEMNIST into 10 groups, and assign each client one label
Random select one client
Reshuffle the data in the selected client
Equally divided into 100 clients
FEMNIST and CIFAR-10 Specifically, we train a two-layer MLP on the Split-FEMNIST and resnet 18 Split-CIFAR-10 respectively. CIFARIO is composed of 32x32 images with three RGB channels of 10 different classes with 60000 samples. The "split" follows the idea introduced in Yu al. (2019); Hsu et al. (2019), where leverage the Latent Dirichlet Allocation (LDA) to control the distribution drift with the dirichlet parameter a. Larger a indicates smaller drifts. Unless otherwise stated, we set dirichlet parameter a 0.5.
Unless specifically mentioned otherwise, our studies use the following protocol. All datasets are split with parameter 0.5, the server choose 20 clients according proposed probability from
33

---

Under review as a conference paper at ICLR 2023
2.4
FedAvg
2.2
2
1.8
1.6
1.4
1.2
0.8
0.8
50
100
150
200
250
300
350
400
450
500
communication rounds
Figure 14: Loss performance of= DELTA, FedIS and FedAvg FEMNIST.
the total of m 300 clients, and each trained for T 500 communication rounds with K local epoches. The default local dataset batch size is 32. The learning rates are set the same in all algorithmss, specifically gyglobel 1 and Iriocal 0.01.
All algorithms use FedAvg as the backbone. We compare DELTA and FedIS with FedAvg in different datasets with different settings.
Loss performance of FEMNIST We compare the loss of DELTA, FedIS and uniform sampling on the non-iid FEMNIST dataset in Fig 14 It shows that DELTA and FedIS converges faster than FedAvg, while DELTA even achieves lower loss than FedIS.
For CIFAR-10, we report the mean of the best 10 test accuracies on global test data here. In Table 2 we compare the performance of DELTA, FedIS, and FedAvg on non-IID FEMNIST and CIFAR- 10. Specifically. we use a 0.1 for FEMNIST and a 0.5 for CIFAR-10 to split dataset. As for Multinomial Distribution (MD) sampling (Li et al. 2018 samples based on clients' data ratio and average aggregates. It is symmetric in sampling and aggregation with FedAvg, with similar performance. It can be seen that DELTA has better accuracy than FedIS, while DELTA and FedIS both outperform FedAvg with the same communication round.
In T we demonstrate that DELTA and FedIS is compatible with other FL optimization algo- rithms, e.g., Fedprox (Li et al. 2018) and FedMime (Karimireddy et al. 2020a). Moreover, DELTA keeps its superiority in this setting.
Table 3: Performance of algorithms with momentum and prox. We run 500 communication rounds on CIFAR1O for each algorithm. We report the mean of maximum accuracies for test datasets and the number of communication rounds to reach the threshold accuracy.
CIFAR-10 + momentum
CIFAR-I0 + prox
Algorithm
Acc (%)
Rounds for 65%
Acc (%)
rounds for 65%
FedAvg (w/ uniform sampling)
0.6567
390
0.6596
283
FedIS
0.6571
252
0.661
266
DELTA
0.6604
283
0.6677
252
In Table we demonstrate that DELTA and FedIS is compatible with other variance reduction algorithms, like FedVARP Jhunjhhnwala et al.) 2022).
is worth noting that FedVARP utilizes the historic update to approximate the unparticipated clients' updates. However, in this setting, the improvement of the sampling strategy the results is somewhat reduced. This is because the sampling strategy is slightly redundant when all users are involved. So when VARP and DELTA/FedIS are combined, instead of reassigning weights in the aggregation step,
34

---

Under review as a conference paper at ICLR 2023
use or to select the current round update clients and then average aggregate the updates of all clients. One can see that the combination DELTA/FedIS and VARP can still show the advantages of sampling.
Table 4: Performance of DELTA/FedIS in combination with Fed VARP We run 500 communication rounds FEMNIST with 0.1 for each algorithm. We report the of maximum 5 accuracies for datasets the number communication rounds to reach threshold accuracy.
FEMNIST
Algorithm
Acc (%)
Rounds for 73%
Ved FedIS FedVARP
73.81 + 0.18
470
73.96 + 0.14
452
DELTA +FedVARP
74.22 0.14
436
We also experiment with different choices of heterogeneity in CIFAR-10. The parameter of heterogeneity a changes from 0.1 to 0.5 to We observe the consistent improvement of DELTA in Table
Table 5: Performance of algorithms under different We 500 communication rounds CIFARIO for each algorithm (with momentum). We report the mean of maximum accuracies test datasets and number of communication rounds to reach the threshold accuracy.
Algorithm
Ace (%)
Rounds 42%
Ace (%)
rounds for 65%
Acc (%)
rounds for 71%
FedAvg (w/ uniform sampling)
0.4209
263
0.6567
283
0.7183
246
FedIS
0.427
305
0.6571
252
0.7218
239
DELTA
0.4311
209
0.6604
0.7248
221
Besides, we also experiment with various client numbers to examine the efficiency of DELTA in FEMNIST dataset. Here we set a = 1, and participated client number choose from n 10, 30, 50. As shown in Table [6, DELTA maintains its supremacy with different participating client numbers.
Table 6: Performance of algorithms under different participated client number We run 500 communica- tion rounds FEMNIST for each algorithm. We report the mean of maximum S accuracies for test datasets and number communication rounds to reach threshold accuracy.
Algorithm
n
10
n
n
50
Acc (%)
Rounds for 85%
Acc (%)
rounds for 85%
Acc (%)
rounds 85%
FedAvg (w/)
0.8717
263
0.8727
267
0.8729
239
FedIS
0.8739
305
0.8734
0.8751
DELTA
0.8741
209
0.8746
270
0.8747
212
35


Reviews:
[{"review_id": "mzB15s0PB_", "reviewer": "Reviewer_xCAd", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors explore the use of importance sampling (IS) its extensions for selecting clients in FL, where IS is based off gradient norms. They first provide a convergence analysis for standard IS sampling (sampling proportional to size of gradients). They then propose an alternative IS sampling which captures both gradient magnitude, as well as gradient diversity (the difference between the client's gradient and the global objective function gradient). They provide a convergence analysis for this sampling scheme and compare the scheme with the original FedIS.", "summary_of_the_review": "This paper extends the analysis of IS for FL, and proposes a principled extension which (at least partially) solves a well known diversity issue that is common to IS in general (though it's certainly even more pronounced in FL). The clear theoretical analysis is a valuable contribution to the field of client selection for FL. ", "strength_and_weaknesses": "Strengths\n- Strong theoretical analysis. \n- Theory is interpretable and illuminating about the nature of the problem.\n\nWeaknesses\n- Experimental results are somewhat weak, with only a marginal improvement over FedIS in experiments on real datasets. ", "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": "mhHJ9TxhRB", "reviewer": "Reviewer_LBTW", "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": "", "summary_of_the_paper": "This paper proposes novel client sampling strategies to accelerate the convergence of \nfederated averaging methods with partial client participation. The idea is to determine \nthe sampling strategies to minimize variance from the worst-case convergence bounds of the methods.", "summary_of_the_review": "I think this paper considers the problem of broad interest. However, the contributions seem to be unclear, due to unclear motivation on why and how the authors design optimal sampling strategies which are better than existing strategies. In addition, some of the proposed strategies cannot be implemented in practice, thus raising the issue on how they modify the strategies to be implementable in the experiments. \n", "strength_and_weaknesses": "Designing optimal client sampling strategies is a problem of broad interest for designing scalable federated learning methods. \nThe authors attempt to **design optimal client sampling strategies in theory and practice** to accelerate the convergence of commonly used federated averaging methods. \n\nHowever, I would like to state the following **major concerns**: \n\n1. **Limitations of using the optimal sampling for DELTA.** \n\nFrom Corollary 3.4, the optimal sampling depends on $\\Vert \\nabla F_i(x) - \\nabla f(x) \\Vert$. This strategy cannot be implemented in practice, mainly because the gradient of the whole objective $\\nabla f(x)$ cannot be accessed usually for problems over huge amounts of data.\n\nTherefore, the authors should state how this strategy is modified to be able to implement it in their experiments.\n\n2. **Redundant assumptions for deriving the convergence results for FedIS and DELTA.**\n\nAssumptions 2 and 3 are commonly used for deriving convergence guarantees for federated methods. This is because Assumption 2 states how different the local stochastic gradient and the local full gradient is, and Assumption 3 implies how different the local full gradient and the whole full gradient is. \n\nHowever, Assumption 4 seems to be redundant to Assumption 2, since both of them impose the property of local stochastic gradients. Therefore, the stated convergence results for FedIS and DELTA seem too restricted. \n\n3. **Lack of motivation on how to design the optimal client sampling strategies for FedIS and DELTA.** \n\nSince FedIS or Algorithm 3 from (Chen et al., 2020) looks similar to DELTA, the proof techniques between these methods should be similar. Hence, I am not sure how the variance from convergence guarantees for FedIS and DELTA is different. Can the authors elaborate on this and perhaps add the motivation before stating theoretical results?  \n\n4. **Numerical evaluations against other unclear existing sampling strategies.** \n\nIn the experiments, the authors compared their sampling strategies against others, e.g. the power of choice, norm, and heterogeneity. However, these strategies are not clearly stated (i.e. what is $p_i^t$)? Are they existing sampling strategies, e.g., from (Chen et al., 2020)? \n\nSince different $p_i^t$ lead to different additional computational costs, it would be also more interesting to compare performance of the algorithms using different sampling with respect to the wall-clock time. \n\nFurthermore, I have the following **small concerns**: \n\n1. The step-size condition in Theorem 3.1 for $\\eta_L$ and $\\eta$ can be simplified to improve readability of this theorem. \n\nThe authors can write $\\eta_L < \\min\\( 1/(8LK), C \\)$ where the constant $C$ is obtained from the condition that\n$1/2 - (10L^2/m)\\sum_{i=1}^m K^2\\eta_L^2(A^2+1)>0$. Then, the author can state the condition for $\\eta$ which is $\\eta \\leq 1/(\\eta_L L)$.\n\nHowever, the constant $A$ is not clearly stated. Does it depend on the index of the client $i = 1,2,\\ldots,m$?\nCan the authors check this? \n\n2. The legend in Figure 5 includes FedSRC-G and FedSRC-D. I believe that they refer to DELTA and FEDIS. Can the authors check and edit the legend? \n\n3. Fedprox from (Li et al., 2018) does not use variance-reduction techniques to design federated optimization methods.\nTherefore, the authors should revise this part of the text which is in their contribution section.\n\n**Typo(s) I can spot:** \n- the data heterogeneity to **fast** the convergence speed $\\rightarrow$  the data heterogeneity to **accelerate** the convergence speed.\n\nNote that due to limited time, I cannot check convergence proofs carefully. \n", "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": "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": "kKngt5h7Kqu", "reviewer": "Reviewer_N8Mo", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper considered the problem of client sampling in federated learning (FL) to improve the convergence speed of FL training. The authors proposed a new client sampling scheme called DELTA, which is unbiased and able to sample more diverse clients that carry valuable information for global model updates. The authors conducted a theoretical convergence rate performance analysis and verified the theoretical convergence performance of their proposed algorithm through simulation experiments.", "summary_of_the_review": "This paper studied the problem of client sampling in FL. The authors proposed a new client sampling algorithm called DELTA, which could achieve both unbiasedness and capture diverse client information. The authors provided rigorous theoretical performance analysis and also provided new insights for FedIS, which is also a new contribution. However, the authors didn't provide any theoretical performance analysis for DELTA with stochastic gradient approximation. Also, some experimental results on convergence speed comparisons may be unfair.", "strength_and_weaknesses": "Strengths:\n1. The client sampling problem in FL is a timely and important problem in FL.\n2. The proposed DELTA client sampling scheme captures diverse clients similar to the federated importance sampling (FedIS) scheme while offering unbiased client sampling performance.\n3. The new and tighter convergence results for FedIS contribute to new understandings of FedIS.\n\nWeaknesses:\n1. The bounded stochastic gradient assumption in Assumption 4 is a bit restrictive and no longer needed in many state-of-the-art FL algorithms' convergence analyses. It may be interesting to see whether this assumption can be relaxed for the DELTA client sampling scheme.\n\n2. The sampling probability $p_i^t$ in Eq. (11) requires full gradient evaluations, which are difficult to implement in practice (also admitted by the authors). To address this challenge, the authors proposed the use of stochastic gradients to approximate the computations. However, the authors didn't theoretically analyze the impacts of the approximation errors on the convergence rate performance, which is somewhat disappointing.\n\n3. The experiment comparisons in Section 5 may be unfair. In the comparisons between DELTA, FedAvg, and FedIS, the authors only compared the convergence speeds in terms of iterations. However, the proposed DELTA method requires rather complicated calculations of $p_i^t$ in Eq. (11) compared to simple uniform sampling in FedAvg and relatively straightforward calculations of $p_i^t$ in FedIS. That is, the per-iteration complexities of these methods are quite different. Thus, it may be better to also compare the wall-clock convergence time between these methods.", "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": "Z5HcbBbrJ9Y", "reviewer": "Reviewer_Yzew", "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": "", "summary_of_the_paper": "This paper proposes a new method to improve previous (cluster-based) important client sampling methods in federated learning. The new method is motivated by the insight that it would be beneficial to select clients from diverse groups. Convergence analysis are also provided and the authors claim they improve over existing ones. At last, experiments on FEMNIST and CIFAR-10 are provided to validate the performance.", "summary_of_the_review": "I suspect that this paper has mistakes in the proof. The theoretical results may not be valid.", "strength_and_weaknesses": "Strength\n- The idea of sampling from diverse gradient groups is a novel idea and seems to be promising.\n- The authors make the proposed sampling algorithm to be unbiased.\n\nWeakness\n- The writing of this paper should be improved. There are many vague statements. For example, in the introduction, the authors explain why previous works are not good. But all the explanations are just intuitions or conjectures. They cannot be used to support the observations in Figure 2. We do not know whether these conjectures are true or not (e.g. whether cluster-IS really select clients with small gradients and whether this is the core reason causing slow convergence).\n- Also, many mathematical expressions are wrong. For example, in equation 2 and 6, the function $f$ should also have some subscripts because its form changes when we sample different clients. Also, in equation (5), the authors define $E|\\nabla f(x)|^2 = E|\\nabla \\tilde{f}(x)|^2 + \\chi^2$. However, in equation (15), they wrote $E|\\nabla \\tilde{f}(x)|^2 = E|\\nabla f(x)|^2 + \\chi^2$. It is obvious these two equations are conflict with each other.\n- The proof may not be correct. I didn't find any proof details for Theorem D.2, which I suspect is wrong due to the above mistakes.\n- Remark 3.2 (3) is not accurate. \"Chen (2020) ... with additional gradient similarity bound\". This sounds like this paper did not do this and remove this assumption. But in fact, the authors define it in Assumption 3 and also use it.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "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": {}}]

Author rebuttal:

Decision: Reject