DELTA: Diverse Client Sampling for Fasting Federated Learning
Authors: Lin Wang
Yongxin Guo
Tao Lin
Xiaoying Tang
Venue: NeurIPS 2023 poster (2023)
Keywords: federated learning
client sampling
TL;DR: We propose an unbiased sampling method that characterizes the impact of client diversity, and provide a practical implementation of it. We provide complete theoretical proof and experimental verification for both theoretical and practical algorithms.

Abstract: Partial client participation has been widely adopted in Federated Learning (FL) to reduce the communication burden efficiently. However, an inadequate client sampling scheme can lead to the selection of unrepresentative subsets, resulting in significant variance in model updates and slowed convergence. Existing sampling methods are either biased or can be further optimized for faster convergence.
In this paper, we present DELTA, an unbiased sampling scheme designed to alleviate these issues. DELTA characterizes the effects of client diversity and local variance, and samples representative clients with valuable information for global model updates. In addition, DELTA is a proven optimal unbiased sampling scheme that minimizes variance caused by partial client participation and outperforms other unbiased sampling schemes in terms of convergence.  Furthermore, to address full-client gradient dependence, we provide a practical version of DELTA depending on the available clients' information, and also analyze its convergence. Our results are validated through experiments on both synthetic and real-world datasets.

DELTA: Diverse Client Sampling for Fasting Federated Learning
Lin Wang!.2 Yongxin Guo 1.2 Tao Lin Xiaoying Tangl. 1,2,3
School of Science and Engineering, The Chinese University of Hong Kong (Shenzhen)
2 The Shenzhen Institute of Artificial Intelligence and Robotics for Society
The Guangdong Provincial Key Laboratory Future Networks of Intelligence
'Research Center for Industries of the Future, Westlake University School of Engineering, Westlake University.
Abstract
Partial client participation has been widely adopted in Federated Learning (FL) reduce the communication burden efficiently. However, inadequate client sampling scheme can lead to the selection of unrepresentative subsets, resulting in significant variance in model updates and slowed convergence. Existing sampling methods are either biased or can be further optimized for faster convergence. In this paper, we present DELTA, an unbiased sampling scheme designed to alleviate these issues, DELTA characterizes the effects of client diversity and local variance, and samples representative clients with valuable information for global model updates. In addition, DELTA is proven optimal unbiased sampling scheme that minimizes variance caused by partial client participation and outperforms other unbiased sampling schemes in terms of convergence. Furthermore, to address full-client gradient dependence, we provide practical version of DELTA depending on the available clients* information, and also analyze its convergence. Our results are validated through experiments on both synthetic and real-world datasets.
1 Introduction
Federated Learning (FL) is a distributed learning paradigm that allows a group of clients to collaborate with central server to train model. Edge clients can perform local updates without sharing their data, which helps to protect their privacy. However, communication can be bottleneck in FL., as edge devices often have limited bandwidth and connection availability [58). To reduce the communication burden, only a subset clients are typically selected for training. However, an improper client sampling strategy, such as uniform client sampling used in FedAvg (38), can worsen the effects of data heterogeneity in FL. This is because the randomly selected unrepresentative subsets can increase the variance introduced by client sampling and slow down convergence.
Existing sampling strategies can be broadly classified into two categorics: biased and unbiased. Unbiased sampling is important because it can preserve the optimization objective. However, only a few unbiased sampling strategies have been proposed in FL, such as multinomial distribution (MD) sampling and cluster sampling- Specifically, cluster sampling can include clustering based on sample size and clustering based on similarity. Unfortunately, these sampling methods often suffer from slow convergence, large variance, and computation overhead issues (3]
To accelerate the convergence of FL with partial client participation, Importance Sampling (IS), an unbiased sampling strategy, has been proposed in recent literature [5 49). IS selects clients with a large gradient norm, as shown in Figure T. Another sampling method shown in Figure
Cooresponding author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Figure 1: Client selection illustration of dif- ferent methods. IS (left) selects high-gradient clients but faces redundant sampling issues. Cluster-based IS (mid) addresses redundancy, but using small gradients for updating continuously can slow down convergence. In contrast, DELTA (right) selects diverse clients with significant gradients without clustering operations.
Cheaer
Cutter
D
Negattiv
Inspotanco Sumpp ag
Choke beaod
DELTA (Durg
Liaition lampliing
Figure 2: Comparison of the convergence performance for different sampling methods. In this example, we use a logistic regression model on non-iid MNIST data and sample 10 out of 200 clients. We run 500 communication rounds and report the average of the best 10 accuracies at 100, 300, and 500 rounds. This shows the accuracy performance from initial training state convergence.
94
76
rouads
cluster-based IS, which first clusters clients according to the gradient norm and then uses IS to select clients with a large gradient norm within each cluster.
Though IS and cluster-basee IS have their advantages, 1) IS could be inefficient because can result in the transfer of excessive similar updates from the clients to the server. This problem has been pointed out in recent works [52 63 and efforts are being made to address it. One approach is to cluster-based IS, which groups similar clients together. This can help, but 2) cluster-based IS has its drawbacks in terms of convergence speed and clustering effect. Figure 2 iilustrates that both of these sampling methods can perform poorly times. Specifically, compared with cluster- based IS, IS cannot fully utilize the diversity of gradients, leading to redundant sampling and lack of substantial improvement in accuracy [52] 2) While the inclusion of clients from small gradient groups in cluster-based IS leads to slow convergence as it approaches convergence, as shown by experimental results in Figure 6 and [ in Appendix [.2] Furthermore, the clustering algorithm's 's performance tends to vary when applied to different client sets with varying parameter configurations,
such different numbers of clusters, observed in prior works 52 5T 56].
To address the limitations of IS and cluster-based IS, namely excessive similar updates and poor convergence performance, we propose novel sampling method for Federated Learning termed DivErse eLienT sAmpling (DELTA). Compared to IS and cluster-based IS methods, DELTA tends to select clients with diverse gradients, as shown in Figure [ This allows DELTA to utilize the advantages of a large gradient norm for convergence acceleration while also overcoming the issue of gradient similarity.
Additionally, we propose practical algorithms for DELTA and IS that rely on accessible information from partial clients, addressing the limitations of existing analysis based on full client gradients [35] We also provide convergence rates for these algorithms. We replace uniform client sampling with DELTA in FedAvg, referred to FedDELTA, and replace uniform client sampling with IS in FedAvg, referred to as FedIS. Their practical versions are denoted as FedPracDELTA and FedPracIS.
Toy Example and Motivation. We present toy example to illustrate motivation, where each client has a regression model. The detailed settings of each model and the calculation of each sampling algorithm's gradient are provided in Appendix [B. Figure shows that IS deviates from the ideal global model when aggregating gradients from clients with large norms. This motivates us to consider the correlation between local and global gradients in addition gradient norms when sampling clients. Compared to IS, DELTA selects clients with large gradient diversities, which exploits the clients' information of both gradient norms and directions, resulting in a closer alignment to the ideal global model.
Our contributions. In this paper, we propose an efficient unbiased sampling scheme in the sense that (i) It effectively addresses the issue of excessive similar gradients without the need for additional clustering, while taking advantage of the accelerated convergence of gradient-norm- based IS and (ii) it is provable better than uniform sampling or gradient norm- norm-based sampling. The sampling scheme is versatile and can be easily integrated with other optimization techniques, such as momentum, to improve convergence further.
As our key contributions,

---

Figure 3: Model update comparison: The closer to the ideal global update (black arrow), the better the sampling algorithm is. The small window shows the projection of clients' functions Fi, F2, in the X-Y plane, where V = (2, V = (4,1), V = (6. -3) at (1, 1). The enlarged image shows the aggregated gradients of FedAvg. IS, DELTA and idcal global gradient. Each algorithm samples two out of three clients: FedIS tends to select Client and with largeset gradient norms, DELTA tends to select Client 1 and with the largest gradient diversity and FedAvg is more likely to select Client and 2 compared to IS and DELTA. The complete gradient illustration with clients' gradient is shown in Figure 5 in Appendix.
poin
Fecting
We present DELTA, an unbiased FL sampling scheme based on gradient diversity and local variance. Our refined analysis shows that FedDELTA surpasses the state-of-the-ar FedAvg in convergence rate by eliminating the O(2/12/3) term and og-related term of (1//T1/3).
We present a novel theoretical analysis of nonconvex FedIS, which yields a superior convergence rate compared to existing works while relying on more lenient assumption. Moreover, our analysis eliminates the (11/2//)) term of the convergence rate, contrast to FedAvg.
We present practical algorithm for DELTA in partial participation settings, utilizing available information to mitigate the reliance on full gradients. We prove that the convergence rates of these practical algorithms attain the same order the theoretical optimal sampling probabilities for DELTA and IS.
2 Related Work
Client sampling in federated learning (FL) can be categorized into unbiased and biased methods [4] Unbiased methods, including multinomial sampling and importance sampling 30 49 ensure that the expected client aggregation is equivalent to the deterministic global aggregation when all clients participate. Unlike unbiased sampling. which has received comparatively little attention, biased sampling has been extensively examined in the context of federated learning, such as selecting clients with higher loss 7 or larger updates [48]. Recently, cluster-based client selection, which involves grouping clients into clusters and sampling from these clusters, has been proposed to sample diverse clients and reduce variance 41 12 (2). Nevertheless,te the clustering will require extra communication and computational resources. The proposed DELTA algorithm can be seen muted version of diverse client clustering algorithm without clustering operation.
While recent works [57 28 have achieved comparable convergence rates to ours using variance reduction techniques, is worth noting that these techniques are orthogonal ours and can be easily integrated with our approach. Although [60] achieved the same convergence rate as ours, but their method requires dependent sampling and mixing participation conditions, which can lead to security problems and exceed the communication capacity of the server. In contrast, our method avoids these issues by not relying on such conditions.
A more comprehensive discussion of the related work can be found in Appendix A
3 Theoretical Analysis and An Improved FL Sampling Strategy
This section presents FL preliminaries and analyzes sampling algorithms, including the convergence rate of nonconvex FedIS in Section 3.2 improved convergence analysis for FL sampling in
Section 3.3 and proposal and convergence rate of the DELTA sampling algorithm in Section 3.4
In FL. the objective of the global model is a sum-structured optimization problem:
(1) where Fi(z) = Eg,DD, (F1 {.)] represents the local objective function of client i over data
minggzd [f()) Σ w:F((=)].
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 randomly selects S.S
clients (n < m) to communicate and update model. Then the loss function of actual participating users in each round can be expressed as:
(x:) Eies, F((x))
(2)
3

---

Table I: Comparison of convergence rate for different sampling algorithms: Number of communication rounds required to reach e c + yp (e for unbiased sampling and c yp for biased sampling. where y is a non- convergent constant term) accuracy
FL.. d7 local variance bound, and bound is G² T is the distance of global optimum and the average of local optimum (Heterogeneity bound), P correspands
to strongly convex. and Ço is the gradient diversity.
Algorithm
Convexity
Partial
Unhiasedness
Convergence rate
Assumatioo
SGD
SIN
+DV
06. bound
FedDELTA
Assumption
FedPracDELTA
Assumption
an Assumption
FedIS (ours)
Assumption
FedlS (others)
Assumption
un Assuroption
FedlS (others) 36
haund
< o02
FedPracI8
Assumptio
nd Assumption
FodAvg 65
bound
FodAvg 21
Assumption
DivEL
Heterogenetty
Power-of-Choice X
Heserogenelty Gap
Fed/vg [55
de bound
Arbitrary Sampling 54
Mix
Assumptive
M 4Koa. AP of Kii "/w))rg. AY2 of 6Kog. A82
4KC2 AP KC Kog.
Convexiit: and abbreviations for strong convex and nonconvex, respoctively. p assurppioo: Bound the similarity among local gradients. Mix porticppaiin:: the number of particppating clienes random from none full participation.
For ease of theoretical analysis, we make the following commonly used assumptions:
3.1 Assumptions
Assumption 1 (L-Smooth). There exists constant L 0, such that [[ - VF(()) S L || yll, Vx, y E IRú, and i = 1,2...., m.
Assumption 2 (Unbiased Local Gradient Estimator and Local Variance). Let E be random local data sample in the round t at client i: E Fi [t) = v F; (z:,), Vi E [m]. The function Fi( Ei) 4 - V.((2))
has bounded local variance of L 0, satisfying E
of.; S oî.
Assumption 3 (Bound Dissimilarity). There exists constants Og 2 O and 2 0 such that (x)] < (A2 + 1)[[v + og. When all local loss functions are identical, 2 0
and og =
The above assumptions are commonly used in both non-convex optimization and FL literature, see e.g. 27 66).
We notice that Assumption 3 can be further relaxed by Assumption 2 of 24 We also provide Proposition C.4 in Appendix C to show all our convergence analysis, including Theorem 3.1 3.5
and Corollary 4.1 4.2 can be easily extended to the relaxed assumption while keeping the order of convergence rate unchanged.
3.2 Convergence Analysis of FedIS
As discussed in the introduction, IS faces an excessive gradient similarity problem, necessitating the development of novel diversity sampling method. Prior to delving into the specifics of our new sampling strategy, we first present the convergence rate of FL under standard IS analysis in this section; this analysis itself is not well explored, particularly in the nonconvex setting. The complete FedIS algorithm is provided in Algorithm of Appendix D which differs from DELTA only in sampling probability (line 2) by using p; I siall.
Theorem 3.1 (Convergence rate of FedIS). Let constant local and global learning rates Ti and be chosen as such that тı <. mán (1/(8K)), C"), where C is obtained from the condition (=nK(A2+)) +1)
that 2
12 + 1 y)m
M > 0 ,,and rj < 1 1/111. T.). In particular, suppose
2n
and n O (VKn), under Assumptions 7 the expected gradient norm of
I
VTKL FedIS algorithm will be bounded as follows:
(Fuxti) +0 (o2 (o2+ Koō
M
min E[V\(()))) L
+ onder
(3)
VnkT
T

---

where T is the total commumication round, K is the total local epoch times, f = f f = f(2.).
M = + + and the expectation is over the local dataset samples among clients.
The FedIS sampling probability p is determined by minimizing the variance of convergence with respect to pl. The variance term is:
Algorithm 1
FedDELTA and FedPracDELTA
Federated learning with unbiased diverse sampling
Require: initial weights Ta. global learning rate n,, local
5 KL KL* M² 2
TILL 2m
LTMEL 2nK
Var(
08), (4)
learning rate rj. number local epoch K, number of training rounds T
mp!
Ensure: trained weights .TT
where Var( (m)))))) is called update variance. By optimizing the update variance, we get the sampling probability FedIS:
I: for round f 1, ,,..., T do
2: Sampling clients using DELIA 13
3: Sampling clients using Practical DELTA (I6)
pl
(5)
j=
4: for each worker E S,,in parallel do
where of = E F 4i,) is the sum
5:
Fi.0 = 2t for k = 0, ...... K 1 do
6:
of the gradient updates of multiple local updates. The proof details of Theorem 3.1 and derivation of sampling probability FedIS are detailed in
7:
compute gi,u = Fiiizi Li.e)
8:
Local update:wi, = 2i,4 T.
Appendix D and Appendix F.
9: Let Dj = thK 02.0 = 171 Ex= -1
gi.k
Remark 3.2 (Explanation for the convergence rate). It is worth mentioning that although few works provide the convergence upper bound of FL with gradient- based sampling, several limi- tations exist in these analyses and results:
10: Server:
Receive i St
12:
mi Ai let A. [5. Eves,
ny!
13: Server update: T(+1 + n
14:
Broadcast 74-1 to clients
1) [49 35] analyzed FL with IS using strongly
convex condition, whereas we extended the analysis to the non-convex problem.
2) Our analysis results, compared to the very recent non-convex analysis of FedIS 5 and FedAvg, remove the term O(T )). although all these works choose learning rate of O Thus, our result achieves a tighter convergence rate when use O(1/T + 1/T2/3) (provided by (43)) as our lower bound of convergence (see Ta.
The comparison results in Table 7 reveal that even when GG is large and becomes dependency term for convergence rate, FedIS (ours) is still better than FedAvg and FedIS (others) since our result reduces the coefficient of OG in the dominant term (
Remark 3.3 (Novelty of our FedIS analysis). Despite the existence of existing convergence analysis of partial participant FL. 165] 47y, including FedIS that builds on this analysis [35] 4l, none of them take full advantage of the nature of unbiased sampling, and thus yield imprecise upper bound on convergence. To tighten the FedIS upper bound, we first derive a tighter convergence upper bound for unbiased sampling FL. By adopting uniform sampling for unbiased probability, achieve tighter FedAvg convergence rate. Leveraging this derived bound, we optimize convergence variance using IS.
Compared with existing unbiased sampling FL. works, including FedAvg and FedIS (others), our analysis FedIS entails: (1) A tighter Local Update Bound Lemma: We establish Lemma C.3 using Assumption 3 diverging from the stronger assumption || (x+))) - V (x I og (used
in [65 47)), and the derived Lemma achieees tighter upper bound than other works (Lemma
4 in [47]. Lemma 2 in (65)). (2) A tighter upper bound on aggregated model updates E'1 A; 2
By fully utilizing the nature of unbiased sampling, we convert the bound analysis of A₂ E E|A
equally to bound analysis of participant variance V 1 of and aggregated model update with full
mp!
user participation. In contrast, instead of exploring the property the unbiased sampling, 47 repeats to use Lemma 4 and [65] uses Lemma 2 for bound Ag. This inequality transform imposes a loose upper bound for Ag. resulting in a convergence variance term determined by n² which reacts to the rate order being OT ). (3) Relying
more lenient assumption: Beyond the aforementioned analytical improvement, our IS analysis obviates the necessity for unusual assumptions in other FedIS analysis such as Mix Participation (35] and psssumpption 4
Remark 3.4 (Extending FedIS to practical algorithm). The existing analysis oS IS algorithms [35
relies on information from full clients, which is not available in partial participution FL. We propose a practical algorithm for FedIS that only uses information from available clients and provide its convergence rate in Corollary 4.1 in Section 4
5

---

Despite its success in reducing the variance term in the convergence rate, FedIS is far from optimal due to issues with high gradient similarity and the potential for further minimizing the variance term (i.e., the global variance dg and local variance or in +). In the next section, we will discuss how to address this challenging variance term.
3.3
An Improved Convergence Analysis for FedDELTA
FedIS and FedDELTA have different approaches to analyzing objectives, with FedIS analyzing the global objective and FedDELTA analyzing a surrogate objective f(x) (cf. (7)). This leads to different convergence variance and sampling probabilities between the two methods. A flowchart (Figure in Appendix has been included to illustrate the differences between FedIS and FedDELTA.
The limitations of FedIS. As shown in Figure [ IS may have excessive similar gradient selection. The variance & in 4 reveals that the standard IS strategy can only control the update variance Var(?/(mp'))'' leaving other terms in Q, namely or, and ag. untouched. Therefore, the standard IS is ineffective at addressing the excessive similar gradient selection problem, motivating the need for new sampling strategy to address the issue of og and Øg.
The decomposition of the global objective. As inspired by the proof of Theorem [.1]]armm..]a as well as the corresponding Lemma C.1 (stated in Appendix) proposed for unbiased sampling, the gradient of global objective can be decomposed into the gradient of surrogate objective f(x))) and update gap,
E| El E (x.)
x²
where X =
Vx(x))) the update gap.
Intuitively, the surrogate objective represents the practical objective of the participating clients in each round, while the update gap Xi represents the distance between partial client participation and full client participation. The convergence behavior the update gap x² is analogous to the update
variance in Φ, and the convergence of the surrogate objective TE (x.( depends the other variance terms in h namely the local variance and global variance.
Minimizing the surrogate objective allows us to further reduce the variance of convergence, and we will focus on analyzing surrogate objective below. We first formulate the surrogate objective with arbitrary unbiased sampling probability.
Surrogate objective formulation. The expression of the surrogate objective relies on the prop- erty of IS. In particular, IS aims to substitute the original sampling distribution p(z) with another
arbitrary sampling distribution q(z) while keeping the expectation unchanged: Bg(x)) [F]( = Ep(x) (u(e)/p.(=>PP(((C)
According to the Monte Carlo method, when q(z) follows the uni- form distribution, we can estimate Egy==) [F](z)] by 1/m > Pi(z) and Ep(=) [a((s)/p((s)(((()] by 1/1 Eies, 1/mm, where m and |S|| = n are the sample sizes.
Based on IS property, we formulate the surrogate objective:
fs. (..) = - Eies, m (x.))
(7)
where m the total number of clients, |S|] = n is the number of participating clients in each round, and p is the probability that client is selected at round f.
As noted in Lemma
C.2 in the appendix, have
min E V 2(x))) min T
ElIV rE|ti
E|1x21 < min 2B 2z())((2))1
(8)
tE[T]
Then the convergence rate of the global objective can be formulated as follows:
Theorem 3.5 (Convergence upper bound of FedDELTA), Under Assumption 73 and let local and
global learning rates r and πΙ, satisfy nr. < 1/(2V10KL E. may and my, S 1/KL, the minimal gradient norm will be bounded as below:
minletr BIIV (xt)
ennz KT =
0-
(9)
With slight abuse of notation, the f(xx) for fs. (Ix) in this paper.

---

where f" f(x), is constant, and the expectation is over the local dataset samples among all workers. The combination of variance & 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:
51.2 2me
(o2., + 4KC8...) +
Lung 2n
1 o2. Lisi m²pt
(10)
For sampling with replacement,
K 201
ois (ax)) and let La be a upper bound for all i, i.e., Sa,s S Co. The be found in Appendix E
EE
1 (oi, 4KC2,..) + P.
Lugn 2n
Σ 1 m²
(11)
where Ca.ú. = V ((()))
proof details of Theorem 3.5
Remark 3.6 (The novelty of DELTA analysis). IS focuses minimizing V ( in convergence
variance & (Eq. (4)), while leaving other terms like and aG unreduced. Unlike IS roles to reduce the update gap, we propose analyzing the surrogate objective for additional variance reduction. Compared with FedIS, our analysis of DELTA entails: Focusing on surrogate objective, introducing a novel Lemma and bound: (1) we decompose global objective convergence into surrogate objective and update gap (6). For surrogate objective analysis, we introduce Lemma E.8 to bound local updates. (2) leveraging the unique surrogate objective expression and Lemmal E.8 we link sampling probability with local variance and gradient diversity, deriving novel upper bounds for A₁ and A2- (3) by connecting update gap's convergence behavior to surrogate objective through Definition [E.1 and Lemma C.2 along with (6), we establish & the new global objective convergence variance. Optimizing convergence variance through novel 4: FedIS aims to reduce the update variance term V( (1mp)) (t) in 4, while FedDELTA aims to minimize the entire convergence variance 4, which is composed of both gradient diversity and local variance. By minimizing & we get the sampling method DELTA, which further reduces the variance terms of & that cannot be minimized through IS.
3.4 Proposed Sampling Strategy: DELTA
The expression of the convergence upper bound suggests that utilizing sampling to optimize the convergence variance can accelerate the convergence. Hence, can formulate an optimization problem that minimizes the variance & with respect to the proposed sampling probability p/:
min Φ s.t. -
(12)
where & is linear combination of local variance LIs and gradient diversity Ça (cf. Theorem 3.5p Corollary 3.7 (Optimal sampling probability of DELTA). By solving the above optimization problem. the optimal sampling probability determined as follows:
/01Ct 1. t.20i,
pt
(13)
Σi= /
tage
where and 02 are constants defined as 20 L and a:2 = 5K Lmj + "-
Remark 3.8. We note that a tension exists between the optimal sampling probability setting of partial participation for FL. Thus, we also provide practical implementation version for DELTA and analyze its convergence in Section 4 In particular, we will show that the convergence rate of the practical implementation version keeps the same order with a coefficient difference.
13) and the
Corollary 3.9 (Convergence rate of FedDELTA). Let qL = = = (VKK)) and
substitute the optimal sampling probability (13 back to $. Then for sufficiently large T, the expected norm of DELTA algorithm [ satisfies:
min.g |T E[V 5 0 ((-Te)) + of
o7. + 1KC7
VnkT
KT
(14)
onder
7

---

Difference between FedDELTA and FedIS, The primary distinction between FedDELTA and FedIS lies in the difference between & and d. FedIS aims to decrease the update variance term Var()/(mp)))) in o while FedDELTA aims to reduce the entire quantity d which is composed of both gradient diversity and local variance. By minimizing क we can further reduce the terms of + that cannot be minimized through FedIS. This leads to different expressions for the optimal sampling probability. The difference between the two resulting update gradients is discussed in Figure Additionally, as seen in Table [ FedDELTA achieves a superior convergence rate of O compared to other unbiased sampling algorithms.
Compare DELTA with uniform sampling. According to the Cauchy-Schwarr inequuuualiiiiuuliiityyy DELTA is
m. ET (Vaioj +anla...)
at least better than uniform sampling by reducing variance:
Punilemn
2 1.
PDLLTA
[ 1h Vai s..
[E y Vo10 +a2 < m
This implies that DELTA does reduce the variance, especially when
> (Voint +o250...)
The significance of DELTA. (1) DELTA is the first unbiased sampling algorithm, to the best of our knowledge, that considers both gradient diversity and local variance in sampling, accelerating convergence. (2) Developing DELTA inspires an improved convergence analysis by focusing on the surrogate objective, leading to a superior convergence rate for FL.. (3) Moreover, DELTA can be seen as an unbiased version with the complete theoretical justification for the existing heuristic or biased diversity sampling algorithm of FI., such 2
4 FeLTAA and FedPracIS: The Practical Algorithms
The gradient- cocentt-orm-baaan based sampling method necessitates the calculation of the full gradient in every iteration I0 70. However, acquiring each client's gradient in advance is generally impractical in FL. To overcome this obstacle, we leverage the gradient from the previous participated round to estimate the gradient the current round, thus reducing computational resources [49].
For FedPracIS, at round 0, all probabilities are set to 1/m. Then, during the in iteration, once participating clients E St have sent the server their updated gradients, the sampling probabilities are updated as follows:
llāuell Eies, [ (1
Pi.
Σ pl.)) iesF
(15)
where the multiplicative factor ensures that all probabilities sum to The FedPracIS algorithm
shown in Algorithm of Appendix D
For FedPracDELTA, we use the average of the latest participated clients' gradients to approximate
the true gradient of the global model. For local variance, it is obtained by the local gradient's 's variance
over local batches. Specifically, Sa,,, = 9 f((xe)l.. where vf(x;) = 3/ Eies, I1.t =
R Etes, ΣK-1 F. Sk,)) and oZ., = Bi EeE [ Ese 3 where E the local data batch. Then the sampling probabilities are updated as follows:
Vaisans +220.
Pi.+1
(1- E JESŞ
(16)
Eies, V Vaile... + azoi..
The FedPracDELTA algorithm shown in Algorithm I Specifically, for a, the default value is 0.5, whereas GG and ar can be implemented by computing the locally obtained gradients.
Assumption 4 (Local gradient norm bound). The gradients V Fe(x)) are uniformly upper bounded (by a constant G > 0) [[)]( < G2, Vi.
Assumption
4 is a general assumption in IS community to bound the gradient norm 70 10 23
and it is also used in the FL community to analyze convergence 2 6881 This assumption tells us
a useful fact that will be used later: F {r,x)/ /V/ (I.,kr Eo,x) U. While, for DELTA, the
assumption used is more relaxed version of Assumption 4 namely, E VF(()) 2 < G (further details are provided in Appendix G).
Corollary 4.1 (Convergence rate of FedPracIS). Under Assumption
the expected norm of
FedPracIS will be bounded follows:
min El[Vf(x))11 s (frrft) +o (E(2]
of (VRTT
[x2) +0 (4f)) +0
)
(xUPog.)
vakT
(17)
8

---

Tosting
(a) 20
(b)
30
(c)
40
Figure 4: Performance different algorithms on the regression model. The loss is calculated by f(z y) I|y \=)) A 10, by The logarithm of global loss is reported for various degrees of gradient noise, v, and methods are well-tuner to yield the best results for each algorithm under cach sctting.
where M = of + 4Kog. aG. is the gradient dissimilarity bound of round 8, and [ (..) (xx))) S for all i and k. Corollary 4.2 (Convergence rate of FedPracDELTAA). Under Assumption 14 FedPracDELTA satisfies:
the expected norm of
mi [(=))l S (0 (f-
6 VaKT
(0o 4AKD
VoKT +
O
(18)
where Ü is constant that [[V V(E.)///VF( - Vs(xa)I S Ü, S Ú and L S U2 U.SU U, and Ça, is the gradient diversity bound of round for all clients.
Remark 4.3. The analysis of the FedPracIS and FedPracDELTA is independent of the unavailable information in the partial participation setting. The convergence rates are of the same order as that of our theoretical algorithm but with an added coefficient constant term that limits the gradient changing rate, as shown in Table
The complete derivation and discussion of the practical algorithm can be found in Appendix G
5 Experiments
In this section, we evaluate the efficiency of the theoretical algorithm FedDELTA and the practical algorithm FedPracDELTA on various datasets. Our code is available at https://gitubb.cmm/1 30300//ETTA.A00 FI.
Datasets. (1) We evaluate FedDELTA on synthetic data and splic-FashionMNISST. The synthetic
data follows = log ((A.z=b.)f//) /2) and "split" means letting 10% of clients own 90% of the data.
(2) We evaluate DedPracDELTA on non-iid FashionMNIST. CIFAR-10 and LEAF B.. Details of data generation and partitioning are provided in Appendix H.2
Baselines and Models. We compare our algorithm, Fed(PPa))DELTA (Algorithm []. with Fs (Algorithm 2 in Appendix [D), FedAVG (38), which uses random sampling, and Power-of- choice 77). which uses loss-based sampling and Cluster-based IS [52]. We utilize the regression model synthetic date, the CNN model on Bushion-MNIST and Leaf, and the ResNet-18 on CIFAR- 10. All algorithms are compared under the same experimental settings, such as Ir and batch size. Full details of the sampling process of baselines and the setup of experiments
provided in Appendix H.2
The maximum values reported in Table 2 are observed during the last 4% of rounds, where these algorithms have already reached convergence. The term 'maximum five accuracies' refers to the mean of the five highest accuracy values obtained within the plateau region of the accuracy curve.
Figure 4 illlustrates the theoretical FedDELTA outperforms other biased and unbiased methods in convergence speed on synthetic datasets. The superiority of the theoretical DELTA is also confirmed on Dalit-FahhooMNNISTT as shown in Appendix Hin Figure [4(a] Additional experimental results, which include range of different choices of regression parameters A,, b. noise v, and client numbers, are presented in Figure
Figure 12 and Figure 13 in Appendix H.
Table 2 shows the FedPracDELTA has better performance in accuracy, communication rounds, and training wall-clock times. Notably, FedPracDEL.TA significantly accelerates convergence by requiring fewer training rounds and less time achieve the threshold accuracy in FaShionMNIST.

---

Table Performance of algorithms various datasets. We run 500 communication rounds FashionM- NIST. CIFAR-I0. 10, FEMNIST, and CelebA for each algorithm. We report the mean of maximum 5 accuracies for test datasets and the average number of communication rounds and time to reach the threshold accuracy.
FashionMNIST
CIFAR-10
Algorithm
Acc (%)
Rounds for 70%
Time (s) for 70%
Acc (%)
Rounds for 54%
Time (5) for 54%
FedAvg
70.35:0.51
426 (1.0x)
1795.12 (1.0x)
54,28:0.29
338 (1.0x)
3283.14 (1.0x)
Cluster-based IS
71.21 +0.24
362 (1.17x)
1547.41 (1.16x)
54.81+0.02
323 (1.05x)
3188.54 (1.03x)
FedPracIS
71.69=0.43
404 (1.05x)
1719.26 (L04x)
55.05
313 (1.08x)
3085.05 (1.06x)
DedPA
72.10=0.49
322 (1.32x)
1372.33 (1.31x)
55.20 10.26
303 (1.12x)
2989.98 (1.1x)
FEMNIST
CelebA
Algorithm
Acc (%)
Rounds for 70%
Time (5) for 70%
Acc (%)
Rounds for 85%
Time (6) for 85%
FedAvg
71.82s0.93
164 (1,0x)
330.02 (1.0x)
85.92s0.89
420 (1.0x)
3439.81 (1,0x)
Clustcr-based IS
70.42:00.6
215 (0.76x)
453.56 (0.73x)
86.77a0.11
395 (1.06x)
3474.50 (1.01)
FedPracIS
80.11=0.29
110 (1.51x)
223.27 (1.48x)
88. 12:0.71
327 (1.28x)
2746 82 (1 (1.25x)
FedPracDELTA
81.4
98 (1.67x)
198.95 (1.66x)
89.67
306 (1.37x)
2607.12 (1.32x)
Table 3: Performance of sampling algorithms integration with other optimization methods on FEMNIST.
PracIS and PracDELTA are the sampling methods of Algorithm FedPracIS and FedPracDELTA, respectively, using the sampling probabilities defined equations ([5) and (16). For proximal and momentum methods, we use the default hyperparameter setting = 0.01 and
0.9.
Rockhone Sampling
Unitorm Sampling
Cluster-based
PractS
ProcDeLLIA
Acc (98)
Rounds
Acc (98)
Rocnds for 805S
(96)
Rouads 90%
Ace (8)
Rounds for
FodAvg
164 ffor 70%)
70.42:0..6
215 dex 7096)
80.1 20000
110 (fx 7096)
$1.44:0.28
98 (for 70%))
FedlAg momentum
80 88808.44 4.4
268 313
80 56:0.49
281
81.80 s0.05
246
82.58 60.44
200
Podiig proximal
81.41 +11.34
80.58 20.38
326
81 81,28:0.25
289
$2.54 =l..7
245
CIFAR- 10, FEMNIST, and CelebA. Additionally, on the natural federated dataset LEAF (FEMNIST and CelebA), our results demonstrate that both FedPracDELTA and FedPracIS exhibit substantial improvements over FedAvg. Figure [4(b) in Appendix H.3 illlutrats the superior convergence of FedPracDELTA, showcasing the accuracy curves of sampling algorithms on FEMNIST.
Table demonstrates that when compatible with momentum proximal regularization, our method keeps its superiority in convergence. We combine various optimization methods such as proximal regularization [29], momentum [34], and VARP [18] with sampling algorithms assess their performance on FEMNIST and FashionMNIST. Additional results for proximal and momentum on CIFAR-10, 10, and for VARP on FashionMNIST, are available in Table[4and Table in Appendix H..
A Ablation studies. We also provide ablation studies of heterogeneity in Table and and the impact of the number of sampled clients on accuracy in Figure 15 Appendix H.3
Conclusions, Limitations, and Future Works
This work studies the unbiased client sampling strategy to accelerate the convergence speed of FL by leveraging diverse clients. To address the prevalent issue of full-client gradient dependence in gradient-based FL [36 4. we extend the theoretical algorithm DELTA to a practical version that utilizes information from the available clients.
Nevertheless, addressing the backdoor attack defense issue remains crucial in sampling algorithms. Furthermore, there is still significant room for developing an efficient and effective practical algorithm for gradient-based sampling methods. We will prioritize this as a future research direction.
7 Acknowledgement
This work is supported in part by the National Natural Science Foundation of China under Grant No. 62001412, in part by the funding from Shenzhen Institute of Artificial Intelligence and Robotics for Society, in part by the Shenzhen Key Lab of Crowd Intelligence Empowered Low-Carbon Energy Network (Grant No. ZDSYS202206061 10660000001)))) and in part by the Guangdong Provincial Key Laboratory of Future Networks of Intelligence (Grant No. 2022B121201000 supported in part by the Research Center for Industries of the Future (RCIF) at Westlake University, and Westlake Education Foundation.
This work is also
10

---

References
[1] Guillaume Alain, Alex Lamb, Chinnadhurai Sankar, Aaron Courville, and Yoshua Bengio. Variance reduction in sgd by distributed importance sampling. arXiv preprint 1.. 2015.
[2] Ravikumar Balakrishnan, Tian Li, Tianyi Zhou, Nageen Himayat, Virginia Smith, and Jeff Bilmes. Diverse client selection for federated learning: Submodularity and convergence analysis. In ICML 2021 International Workshop on Federated Learning for User Privacy and Data Confidentiality, Virtual, July 2021.
[3] Sebastian Caldas, Sai Meher Karthik Duddu, Peter Wu, Tian Li, Jakub Konečný, H Brendan McMahan, Virginia Smith, and Ameet Talwalkar. Leaf: A benchmark for federated settings. arXiv preprint arXiv: 1812009// 2018.
[4] Wenlin Chen, Samuel Horvath, and Peter Richtarik. Optimal client sampling for federated learning. arXiv preprint arXiv:2010.1372., 2020.
[5] Wenlin Chen, Samuel Horváth, and Peter Richtárik. Optimal client sampling for federated learning. Transactions on Machine Learning Research, 2022.
[6] Yae Jee Cho, Samarth Gupta, Gauri Joshi, and Osman Yagan. Bandit-based communication- efficient client selection strategies for federated learning. In 2020 54th Asilomar Conference on Signals, Systems, and Computers, pages 1066-1069. IEEE, 2020.
[7] Yac Jee Cho, Jianyu Wang, and Gauri Joshi. Towards understanding biased client selection in federated learning. In International Conference Artificial Intelligence and Statistics, pages 10351-10375. PMLR, 2022.
[8] Yongheng Deng, Feng Lyu, Ju Ren, Huaqing Wu, Yuezhi Zhou, Yaoxue Zhang, and Xuemin Shen. Auction: Automated and quality-aware client selection framework for efficient federated learning. IEEE Transactions on Parallel and Distributed Systems, 3398)9199,,2009, 2022.
[9] Enmao Diao, Jie Ding, and Vahid Tarokh. Heterofl: Computation and communication efficient federated learning for heterogeneous clients. arXiv preprint arXiv:2010.01264 2020.
[10] Victor Elvira and Luca Martino. Advances in importance sampling. arXiv:2102.05407, 2021.
arXiv preprint
[11] Maximilian Fiedler and Peter Gritzmann. Coresets for weight-constrained anisotropic assign- ment and clustering. arXiv preprint arXiv:2203. 10864, 2022.
[12] Yann Fraboni, Richard Vidal, Laetitia Kameni, and Marco Lorenzi. Clustered sampling: Low- variance and improved representativity for clients selection federated learning, 2021.
[13] Yann Fraboni, Richard Vidal, Laetitia Kameni, and Marco Lorenzi. A general theory for client sampling in federated learning. In IJCAI 2022-31st International joint conférence on artificial intellignce, 2022.
[14] Yann Fraboni, Richard Vidal, Laetitia Kameni, and Marco Lorenzi. A general theory for client sampling in federated learning. In Trustworthy Federated Learning: First International Workshop, FL 2022, Held in Conjunction with IJCAI 2022, Vienna, Austria, July 23, 2022, Revised Selected Papers, pages 46-58. Springer, 2023.
[15] Yongxin Guo, Tao Lin, and Xiaoying Tang. Towards federated learning time-evolving heterogeneous data. arXiv preprint arXiv:21 13246, 2021.
[16] Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown. Measuring the effects of non-identical data distribution for federated visual classification. arXiv preprint arXiv:1909.0633 2019.
[17] Tiansheng Huang, Weiwei Lin, Li Shen, Keqin Li, and Albert Y. Zomaya. Stochastic client selec- tion for federated learning with volatile clients. IEEE Internet of Things Journal, 200))20055- 20070, 2022.
11

---

[18] Divyansh Jhunjhunwala, PRANAY SHARMA, Aushim Nagarkatti, and Gauri Joshi. Fedvarp: Tackling the variance due to partial client participation in federated learning. In The 38th Conference on Uncertainty in Artificial Intelligence, 2022.
[19] Tyler B Johnson and Carlos Guestrin. Training deep models faster with robust, approximate importance sampling. Advances in Neural Information Processing Systems, 31:7265-7275, 2018.
[20] Sai Praneeth Karimireddy, Martin Jaggi, Satyen Kale, Mehryar Mohri, Sashank J Reddi, Sebastian U Stich, and Ananda Theertha Suresh. Mime: Mimicking centralized stochastic algorithms in federated learning. arXiv preprint arXiv:2008.03600 2020.
[21] 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, pages 5132-5143, PMLR, 2020.
[22] Angelos Katharopoulos and François Fleuret. Biased importance sampling for deep neural network training. arXiv preprint arXiv:1706.00045 2017.
[23] Angelos Katharopoulos and François Fleuret. Not all samples are created equal: Deep learning with importance sampling. In International conference on machine learning, pages 2525-2534. PMLR, 2018
[24] Ahmed Khaled and Peter Richtárik. Better theory for sgd in the nonconvex world. arXiv preprint arXiv:2002.03332 2020.
[25] Yeongwoo Kim, Ezeddin Al Hakim, Johan Haraldson, Henrik Eriksson, José Mairton B da Silva, and Carlo Fischione. Dynamic clustering in federated learning. In ICC 2021-IEEE International Conference Communications, pages 1-6. IEEE, 2021.
[26] Haneul Ko, Jaewook Lee, Sangwon Seo, Sangheon Pack, and Victor C. M. Leung. Joint client selection and bandwidth allocation algorithm for federated learning. IEEE Transactions on Mobile Computing, pages 1-1, 2021.
[27] Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian Stich. A unified theory of decentralized sgd with changing topology and local updates. In International Conference on Machine Learning, pages 5381-5393, PMLR, 2020.
[28] Bo Li, Mikkel N Schmidt, Tommy S Alström, and Sebastian U Stich. Partial variance reduction improves non-convex federated learning on heterogeneous data. arXiv preprint arX1v:2212.02191, 2022
[29] Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. arXiv preprint arXiv: 181206177,, 2018.
[30] Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. Proceedings of Machine learning and systems, 2:429-450, 2020.
[31] Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang. and Zhihua Zhang. On the convergence of fedavg on non-iid data. arXiv preprint arXiv:1907.02116 2019.
[32] Shiyun Lin, Yuze Han, Xiang Li, and Zhihua Zhang, Personalized federated learning towards communication efficiency, robustness and fairness. Advances in Neural Information Processing Systems, 2022.
[33] Tao Lin, Lingjing Kong, Sebastian U Stich, and Martin Jaggi. Ensemble distillation for robust model fusion in federated learning. arXiv preprint arXiv:2006.07243 2020.
[34] Wei Liu, Li Chen, Yunfei Chen, and Wenyi Zhang. Accelerating federated learning via momen- tum gradient descent. IEEE Transactions on Parallel and Distributed Systems, 1754):175411766, 2020.
12

---

[35] Bing Luo, Wenli Xiao, Shiqiang Wang, Jianwei Huang, and Leandros Tassiulas. Tackling system and statistical heterogeneity for federated learning with adaptive client sampling. In IEEE INFOCOM 2022-IEEE Conference on Computer Communications, pages 1739-1748. IEFE, 2022.
[36] Bing Luo, Wenli Xiao, Shiqiang Wang, Jianwei Huang, and Leandros Tassiulas. Tackling system and statistical heterogeneity for federated learning with adaptíve client sampling. In IEEE INFOCOM 2022 IEEE Conference on Computer Communications, pages 1739-1748, 2022.
[37] Jiahua Ma, Xinghua Sun, Wenchao Xia, Xijun Wang, Xiang Chen, and Hongbo Zhu. Client selection based on label quantity information for federated learning. In 2021 IEEE 32nd Annual International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC), pages 1-6, 2021.
[38] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. ceattumiicatio-fffffiieeee learning of deep networks from decentralized data. In Artificial intelligence and statistics, pages 1273-1282. PMLR, 2017.
[39] Aritra Mitra, Rayana Jaafar, George Pappas, and Hamed Hassani. Achieving linear con- vergence in federated learning under objective and systems heterogeneity. arXiv preprint arXiv:2102.07053. 2021.
[40] Ihab Mohammed, Shadha Tabatabai, Ala Al-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-595 2021.
[41] Mahdi Morafah, Saeed Vahidian, Weijia Wang, and Bill Lin. Flis: Clustered federated learning via inference similarity for non-iid data distribution. IEEE Open Journal of the Computer Society, 4: 1:00 2023.
[42] Khalil Muhammad, Qinqin Wang, Diarmuid O' O'Reilly-Morgan, 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, pages 1234-1242, 2020.
[43] Kumar Kshitij Patel, Lingxiao Wang, Blake E Woodworth, Brian Bullins, and Nati Srebro. Towards optimal communication complexity in distributed non-convex optimization. Advances in Neural Information Processing Systems, 35:13316 13328, 2022.
[44] Jake Perazzone, Shiqiang Wang, Mingyue Ji, and Kevin S. Chan. Communication--ffiiieenn device scheduling for federated learning using stochastic optimization. In IEEE INFOCOM 2022 IEEE Conference on Computer Communications, pages 1449-1455 2022.
[45] Zhe Qu, Rui Duan, Lixing Chen, Jie Xu, Zhuo Lu, and Yao Liu. Context-aware online client selection for hierarchical federated learning, 2021.
[46] Zhe Qu, Rui Duan, Lixing Chen, Jie Xu, Zhuo Lu, and Yao Liu. Context-aware online client selection for hierarchical federated learning. IEEE Transactions on Parallel and Distributed Systems, (3(12)44333-4333 2022.
[47] Sashank Reddi, Zachary Charles. Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and Brendan McMahan. Adaptive federated optimization. arXiv preprint arXiv:2003.000 00295, 2020.
[48] Monica Ribero and Haris Vikalo. Communication-effiiinnn federated learning via optimal client sampling. arXiv preprint 2rXiv:2007.15197, 2020.
[49] Elsa Rizk, Stefan Vlaski, and Ali H Sayed. Federated learning under importance sampling. arXiv preprint arXiv:20/2.073388 2020.
[50] Yichen Ruan and Carlee Joe-Wong, Fedsoft: Soft clustered federated learning with proximal local updating. Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 1134-8131, 2022.
13

---

[51] Gaganpreet Sharma. Pros and cons of different sampling techniques. International journal of applied research, 3(7):749-752, 2017.
[52] 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 2at::2208.5133. 2022.
[53] Chengshuai Shi and Cong Shen. Federated multi-armed bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 9603-9611, 2021.
[54] Sebastian U Stich, Anant Raj. and Martin Jaggi. Safe adaptive importance sampling. arXiv preprint arXiv: 1.02637, 2017.
[55] Canh T. Dinh, Nguyen Tran, and Josh Nguyen. Personalized federated learning with moreau envelopes. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 21394 21405. Curran Associates, Inc., 2020.
[56] Steven K Thompson. Adaptive cluster sampling. Journal of the American Statistical Association, 85(412):1050-1055 1990.
[57] Alexander Tyurin and Peter Richtárik. A computation and communication efficient method for distributed nonconvex problems in the partial participation setting. arXiv preprint arXiv:220..15580 2022.
[58] Jianyu Wang, Zachary Charles, Zheng Xu, Gauri Joshi, H Brendan McMahan, Maruan Al- Shedivat, Galen Andrew, Salman Avestimehr, Katharine Daly, Deepesh Data, et al. field guide to federated optimization. arXiv preprint arXiv:2107.06917, 2021.
[59] 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.07481/ 2020.
[60] Shiqiang Wang and Mingyue Ji. A unified analysis of federated learning with arbitrary client participation, arXiv preprint arXiv:2205. 13648, 2022.
[61] Joel Wolfrath, Nikhil Sreekumar, Dhruv Kumar, Yuanli Wang, and Abhishek Chandra. Haces: Heterogeneity clustered client selection for accelerated federated learning. In 2022 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pages 985-995, 2022.
[62] Wenchao Xia, Tony QS Quek, Kun Guo, Wanli Wen, Howard H Yang, and Hongbo Zhu. Multi- armed bandit-based client scheduling for federated learning. IEEE Transactions on Wireless Communications, 19(1 1):7108 -123,, 2020.
[63] Han Xie, Jing Ma, Li Xiong, and Carl Yang. Federated graph classification over non-iid graphs. Advances in neural information processing systems,
2021.
[64] Xiaohui Xu, Sijing Duan, Jinrui Zhang, Yunzhen Luo, and Deyu Zhang. Optimizing federated learning on device heterogeneity with sampling strategy. In 202/ IEEF/ACM 29th International Symposium on Quality of Service (IWQOS), pages 1-10, 2021.
[65] 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.
[66] 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, pages 5693 5700, 2019.
[67] Hangjia Zhang, Zhijun Xie, Roozbeh Zarei, Tao Wu, and Kewei Chen. Adaptive client selection in resource constrained federated learning systems: A deep reinforcement learning approach. IEEE Access, 9:98423-9844 2021.
[68] Xinwei Zhang, Mingyi Hong, Sairaj Dhople, Wotao Yin, and Yang Liu. Fedpd: A feder- ated learning framework with optimal rates and adaptivity to non-iid data. arXiv preprint 20Xiv:2005.11418. 2020.
14

---

[69] Boxin Zhao, Ziqi Liu, Chaochao Chen, Mladen Kolar, Zhiqiang Zhang, and Jun Zhou. Adaptive client sampling federated learning via online learning with bandit feedback. arXiv preprint arXiv:21 14332, 2021.
[70] Peilin Zhao and Tong Zhang. Stochastic optimization with importance sampling for regularized loss minimization. In international conference on machine learning, pages 1-9. PMLR, 2015.
[71] Hongbin Zhu, Yong Zhou, Hua Qian, Yuanming Shi, Xu Chen, and Yang Yang. Online client selection for asynchronous federated learning with fairness consideration. IEEE Transactions on Wireless Communications, pages 1-1, 2022.
15

---

Contents of Appendix
An Expanded Version of The Related Work
16
Toy Example and Experiments for Illustrating Our Observation
17
B.1 Toy example
17
B.2 Experiments for illustrating our observation.
18
Techniques
19
Convergence of FedIS, Proof of Theorem 3.1 D.I
21
Proof for convergence rate of FedIS (Theorem 3.1 under Assumption 1H3
25
Convergence of DELTA. Proof of Theorem 3.5
26
E.1
Convergence rate with improved analysis method for getting DELTA
26
E.2 Proof for Theorem |E.2]|
28
F.2.1 Sample with replacement
28
E.2.2 Sample without replacement
32
F
Proof of the Optimal Sampling Probability
35
F.1
Sampling probability FedIS]
F2
Sampling probability of DELIA
36
Convergence Analysis of The Practical Algorithm
36
Additional Experiment Results and Experiment Details,
39
H.1
Experimental Environment
H.2
Experiment setup)
H.3
Additional Experimental Results
A An Expanded Version of The Related Work
de facto algorithm FL, in which multiple local SGD steps are executed on the available clients to alleviate the communication bottleneck. While communication efficient, heterogeneity, such as system heterogeneity [29 31 59 39 9) and statistical/ojjective heterogeneity [33 21
FedAvg is proposed by [38
29 559 151, results in inconsistent optimization objectives and drifted clients models, impeding federated optimization considerably.
Objective inconsistency in FL. Several works also encounter difficulties from the objective inconsistency caused by partial client participation [31 7 2 [3] 7 use the local-global gap - -. F to measure the distance between the global optimum and the average of all local personal optima, where the local-global gap results from objective inconsistency the final optimal point. In fact, objective inconsistency occurs in each training round, not only at the final optimal point. 2 also encounter objective inconsistency caused by partial client participation. However, they use Σ" (z))).) fz,)) < c as an assumption to describe such update inconsistency caused by objective inconsistency without any analysis on it. To date, the objective inconsistency caused by partial client participation has not been fully analyzed, even though it is prevalent in FL, even homogeneous local updates. Our work provides a fundamental convergence analysis on the influence of the objective inconsistency of partial client participation.
Client selection in FL. general, sampling methods in federated learning (FL) can be classified as biased or unbiased. Unbiased sampling guarantees that the expected value of client aggregation equal that of global deterministic aggregation when all clients participate. Conversely, biased sampling may result in suboptimal convergence. A prominent example of unbiased sampling in FL multinomial sampling (MD), which samples clients based on their data ratio [29 Additionally, importance sampling (IS), an unbiased sampling method, has been utilized in FL to reduce convergence variance. For instance, 4 use update norm as an indicator of importance to sample clients, 44 sample clients based on data variability, and [40] use test accuracy as an estimation of importance. Meanwhile, various biased sampling strategies have been proposed to speed up training, such as selecting clients with higher loss (7), as many clients as possible under threshold [45), clients
16

---

with larger updates [48, and greedily sampling based on gradient diversity [2. However, these biased sampling methods can exacerbate the negative effects of objective inconsistency and only converge to a neighboring optimal solution. Another line of research focuses on reinforcement learning for client sampling, treating each client as an agent and aiming to find the optimal action [69 62] 53 67].
There are also works that consider online FL., in which the client selection must consider the client's s
connection ability [44. 17 26
71
46 8]. Recently, cluster-based client selection has gained some 50
41 61]. Though clustering adds additional computation 52 show that it is helpful for sampling diverse clients and reducing variance. Although some studies employ adaptive cluster- based IS address the issue of slow convergence due to small gradient groups [52 [1, these approaches differ from our method as they still require an additional clustering operation. The proposed DELTA in Algorithm I can be viewed as a muted version of the diverse client clustering algorithm, while promising to be unbiased.
attention in FL 11 64
42
52
37
25
and memory overhead, [2]
Importance sampling. Importance sampling is a statistical method that allows for the estimation of certain quantities by sampling from distribution that is different from the distribution of interest. has been applied in a wide range of areas, including Monte Carlo integration I0 70
Bayesian
inference [22 23), and machine learning [54]
In recent parallel work, 449 demonstrated mean square convergence of strongly convex federated learning under the assumption of a bounded distance between the global optimal model and the local optimal models. [4] analyzed the convergence of strongly convex and nonconvex federated learning by studying the improvement factor, which is the ratio of the participation variance using importance sampling and the participation variance using uniform sampling. This algorithm dynamically selects clients without any constraints on the number of clients, potentially violating the principle of partial user participation. It is worth noting that both of these sampling methods are based on the gradient norm, ignoring the effect of the direction of the gradient. Other works have focused on the use of importance sampling in the context of online federated learning, where the client selection must consider the client's 's connection ability. For example, (69] proposed an adaptive client selection method based on reinforcement learning, which takes into account the communication cost and the accuracy of the local model when selecting clients to participate in training.
[62] also employed reinforcement learning for adaptive client selection, treating each client an agent and aiming to find the optimal action that maximizes the accuracy of the global model. (6) introduced a bandit- federated learning algorithm that uses importance sampling to select the most informative clients in a single communication round. (33) considered the problem of federated learning with imperfect feedback, where the global model is updated based on noisy and biased local gradients, and proposed an importance sampling method to adjust for the bias and reduce the variance of convergence.
B
Toy Example and Experiments for Illustrating Our Observation
B.1
Toy example
Figure 5 is a separate illustrated version of each sampling algorithm provided in Figure 3
We consider a regression problem involving three clients, each with a unique square function:
Fi y) = x + y²; F2 y) 4(x 1 2)² + FF y) 3x + 2 (y - 2)² Suppose (z,, ye) 11, at current round t. the gradients of three clients are V = (2, 2). VF22 = (4. 1). and VP (6, -3.. Suppose only two clients are selected to participate in training. The closer the selected user's update is to the global model, the better.
For ideal global model, V Falobal = + Ei FF = (4, which is the average over all clients.
For FedIS, Fredds = FVFg + F33) (5. -1): It tends to select Client and who have large gradient norms, as | F3l > F2 |V Fll.
For DELTA, VIDELTA A = _ [V V/3) = (4, -)::: It tends select Client and 3 who have the
largest gradient diversity than that of other clients pair, where the gradient diversity can be formulated
by diu; = F y1) V Fytobal (xt, yt)l 55 32
'Wit a slight abuse of the name, we use DELTA for the rest of the paper to denote either the sampling probability or the federated learning algorithm with sampling probability DELTA, does FedIS.
17

---

For FedAvg, Feeddgg = (VE + VF2) = (3, )): It assigns each client with equal sampling probability, Compared to FedIS and DELTA, FedAvg is more likely to select Client and 2. To facilitate the comparison, FedAvg is assumed to select Client and 2 here.
can observe that the gradient produced by DELTA is closest that of the ideal global model. Specifically, using L2 norm as the distance function D, we have DEVT A. V alobaa)) < Fearss,, globbt)) FFVFFedAvg: Viglobat). This illustrates the selection of more diverse clients better approaches the ideal global model, thereby making it more efficient.
From Figure 3
Clieut
Client
Clinat 2
Claas
Lallol!
3it Iafobst
21
21
KEILD
Cliret
Clirm
(a) Overview of different methods.
(b) FedAvg.
Clicat
Clicet
Client
Clien: 2
ReiipSIZA
Ra-iLFillSS
Climi a
Client a
(c) FedIS.
(d) DELTA.
Figure 5: 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 x++1 becomes .+11
(+1 Fed instead of x gtobaat resulting in objective inconsistency. Different sampling strategies can cause different surrogate objectives, thus causing different biases. From S(a) we can DELTA achieves minimal bias among the three unbiased sampling methods.
B.2 Experiments for illustrating our observation.
Experiment setting. For the experiments to illustrate our observation in the introduction, we apply a 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 to 0.01, and the local update time to 5 for all methods. We run 500 communication rounds for each algorithm. We report the average of each round's 's selected clients' gradient norm and the minimum of each round's 's selected clients' gradient norm.
Performance of 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 6(a) In addition, we also provide the minimal gradient norm comparison between IS and cluster-based IS in Figure ((b)
Performance of removing small gradient clusters. We report on comparison of the accuracy and loss performance between vanilla cluster- IS and the removal of cluster- IS with small gradient clusters. Specifically, we consider setting with two cluster centers. After 250 rounds, we replace the clients in the cluster containing the smaller gradient with the clients in the cluster containing the larger gradient while maintaining the same total number of participating clients. The experimental results are shown in Figure 7 We can observe that vanilla cluster-based IS performs
18

---

15 cluster-based IS
cluster-based IS
average gradient norm
gradiengradient norm
minimal gradient
mny
2
100
200
300
400
500
100
200
400
500
Rounds
Rounds
(a) Average gradient norm comparison
(b) Minimal gradient norm comparison
Figure 6: The gradient comparison. Both results indicate that cluster-hased IS selects clients with small gradients about half the training rounds compared to
worse than cluster-based IS without small gradients, indicating that small gradients are contributing factor to poor performance.
2.5
vanilla cluster-based cluster-based without gradients
2
Acc.aay
Loss
1.5
vanilla cluster-based cluster-based without small gradients
0.5
100
200
300
400
500
50
100
150
230
Rounds
203
200
350
430
402
500
Rounds
(a) Accuracy performance comparison
(b) Loss performance comparison
Figure 7: An illustration that cluster-based IS sampling from the cluster with small gradients will slow convergence. When the small gradient-norm cluster's clients replaced by the clients from the large gradient-norm cluster, the performance improvement of cluster-based IS.
C Techniques
Here, we present some technical lemmas that are useful in the theoretical proof. We substitute for n. to simplify the writing all subsequent proofs. ni the data ratio client All of our proofs can be casily extended from f(x)) = Em F((xe) to f(x,) = Σn ny F((x)).
Lemma C.1. (Unbiased Sampling). E(2 n Eies. mp: (F(().) m
Importance sampling is unbiased sampling. E (F(z)) no matter whether the sampling is with
1
replacement without replacement.
Lemma CT proves that the importance sampling is an unbiased sampling strategy, either in sampling with replacement sampling without replacement.
19

---

Proof.
For with replacement:
E
Σ
1
Σ E iES;
V(((T))
-
Σ
E
E
1
V (s) $))
mp!
mp!
n2
mp!
i
iES,
m
VF((or))
Σ
Vf(x)) V((x))
Pi
n1
mpl
n2
SES.
V=1
IES.
(19)
For without replacement:
m
E
VF((2))
E
Im
VF((ze))
= Σ EImm x E
(.(()))
mp:
71
mpt
mpl
S
Im)
x
E
()((2,))
= - n
x
(F((
72
mpf
mpi
1=1
1=1
1
m
m Σ
ripi
VFi(x;)
Vf(a:) (20)
71
mp
m
if xn E St. {
where Im a
otherwise.
In the expectation, there are three sources of stochasticity. They are client sampling, local SGD, and the filtration of x,. Therefore, the expectation is taken over all of these sources of randomness. Here, represents the sources of stochasticity other than client sampling. More precisely, S represents the filtration of the stochastic process æj.J = 2, at time t and the stochasticity of local SGD. O
Lemma C.2 (update gap bound).
E
Σ
mp VF((.))
() (x))| [v)(2)) E())(= (21)
VES.
where the first equation follows from B|r - [xx) = - and Lemma C.1
For ease of understanding, we give a detailed derivation of the Lemma
E (IVF(()-VV((())
fxx)) -E (IVf(==))* 1s) 2E (IVAA))II (s)
+ E [lvf(())) (S)
(22)
where [xx 5) means the expectation on over the sampling space. We have E (IV ((x)) 1s) = fa()) and E f 5) Vf )1 (I/V [z) is constant for stochasticity S and the expectation over constant is the constant itself.) Therefore, we conclude
E (IV)(()) Vf(D)ll (s) = E (IV](2))) (s) [x=)) S (IVi(2))) (
(23)
We can further take the expectation on both sides of the inequality according to our needs, without changing the relationship.
The following lemma follows from Lemma 4 of 47]. but with a looser condition Assumption 3 instead of og bound. With some effort, we derive the following lemma:
Lemma C.3 (Local updates bound.). For any step-size satisfying a S SLK we can have the following results:
E El 2xl12 < 5K 4Km)00) 20 (A² (
(24)
20

---

Proof.
Ee ||| 1 26
Bell=jjA-11 - -x - -
Bellvri - 1/1 -1
- VR(2)))
- (1 + 2K
k-1 - - + F
-
4KKE, [1 V (F,
V VF (4
1
S + 2K EE f 1- 2111² n..1 4K | 1211?
+ 4K 4 o8 + 4K 1Kn (A² f)
< (1 K
E ki1 - + 4K 4 4K((A V())) (25)
Unrolling the recursion, we obtain:
Ex | - xel12 <
+
K )" o 4K1208 4K(A² + V/(a))1
p=0
$ SK 1) (1
1
)k - [n:o] + 4K + 4<<AA + 1)),,.
K
5K +4K + 20K +f
(26)
In the following Proposition, we will demonstrate that the convergence rate in this paper with the relaxed version of Assumption remains unchanged.
Proposition C.4 (convergence under relaxed Assumption 3 tion in this paper is:
The relaxed version of Assump-
E 2B(f())
- +1)
(27)
Since we have substitute og with 2BF all analyses without altering the outcomes (one can directly conclude this from using the above bound in Lemma C.3). In the final convergence rate, it is straightforward to see that the convergence rate remains unchanged, yet the constant term ag becomes 2BF + OG-
S f < F, where F is a positive constant. This implies that we can
Thus, we can assert that we have furnished the analysis under the relaxed assumption condition.
D Convergence of FedIS, Proof of Theorem 3.1
The complete version of FedIS algorithm is shown below:
We first restate the convergence theorem (Theorem 3.1 more formally, then prove the result for the nonconvex case.
Theorem D.1. Under Assumptions 3 and the sampling strategy FedIS, the expected gradient norm will converge to a stationary point of the global objective. More specifically, if the number of communication rounds T is predetermined and the learning rate n and πy constant, then the expected gradient norm will be bounded follows:
F
mán E. f S LE[T]
T
(28)
CMLLK KT
where F = ((x) - f(x.), M of + 4Kog. and the expectation is over the local datasets samples among workers.
21

---

Algorithm 2 FedIS and FedPracIS Federated learning with importance sampling
Require: initial weights 20. global learning rate 1), local learning rate TR, number of training rounds
Ensure: trained weights 7T
I: for round f 1...., do
2: Select clients by using IS 5 or Practical IS 15
each worker Sn parallel do 27.0 2t
5:
for k 00
do
6:
compute gř,x Fa ko st,aa)
7:
Local update:zi z k NLIiN
Let A] zi,x 23.0 TI > k- 9i,k
Send gradient to server
10:
At Server:
11:
Receive ii,EE St
3 Dies, A np.
Server update: 2441 Ie + n
14:
Broadcast 2:-1 clients
Let U < min (1/(8LK), C., where C is obtained from the condition that 1022 12
1)mi
IL 0 D,and n S L)) it then holds that:
2n
1 5m L
MiL L
LAME V --))
(oî + 4Ko2)
of +
(29)
2m
2m
2nk
mp!
1=1
where e is a constant that satisfies 10L 10L2 + 1)
L'nK(A²-1)
2n
MT
c 0, and
V (G 9i) B'll
m L 11
Corollary D.2. Suppose yr, and π are such that the conditions mentioned above are satisfied,
UL = O VTKL) and O (K)) and let the sampling probability be FedIS 75 Then for
sufficiently large T, the iterates of Theorem 3.1 satisfy:
min E [[ T
= @V
Kod
of + 4Ko2
(30)
VnKT
KT
Proof.
(a1) E, [x(f((+11 I f(xx) +
xx}) L Eellsr++11 -
L "" B (.11
=s(x)) + (Vf( EI + AVf me mVKK((()))) +
L
f((x) n | ]| (V)z)) mLVf(x + E, 1
(31)
where (al) follows from the Lipschitz continuous condition. The expectation is conditioned on everything prior to the current step round f. Specifically, is taken over the sampling of clients, the sampling of local data, and the current round's model
22

---

Firstly we consider A1: A (vx)), B. (A. + nr. KV (x+)))
((())) E.
n.sii + (..KV((()))
St
mp
K-1
(2))
Vf(z.) E,
T (L(()) + +
2m
0
(KK)( VK
-
(a3)
M K
E,
m -
2
2K
K-1
Eell
2K
m
i=1 k=0
(o1) MLK
|| fxzz) 2| +
n
By 11 - x2.1
7L
E,l
K
2
2m
2K
k=0
1=1 R=0
M
1212 (A2 +1) [[]((;)]]+
5L2mZ
+ L0n
2
VB
(32)
2K
k=
where (a2) follows from Assumption 2 and Lemma C.I [||=||] + ||y| - |I y/|²] and (a4) comes from Assumption
(a3) is due to (α,
Then we consider Ag. Let of E gh. EK-1
A2
Ee || A, 1
K-1
1
Es
111 11
P2.k
mp
K-1 1
1
m
K K-1
E
gi.k
9i,k
mp!
m
k=0
k=0
m
K
22 E
9b (
m
0=
22 V
9
mp:
m
E
- + (F(
m
V
n
mp;
K-1
m
K-1
vi m
Σ
(l - VRR(EN))
E
m VB(
k=0
K
2 V ((=)))
K
+ 1
0f + 1
V (.
(33)
mp:
1=1 km0
23

---

The third equality follows from independent sampling.
Specifically, for sampling with replacement, due to every index being independent, we utilize Eljai + + v. 1 [ +... + |_a]]"].
For sampling without replacement:
B|
mp
i=
1
11
9
1
map
1=1
1
E
1
x P[L 1)
mp
m
E
9
I. 0
P(L =
n2a
mp:
m
i=1
1
P
9
11
mp
1=1
1 n
m
(34)
From the above, we observe that it is possible to achieve a speedup by sampling from the distribution that minimizes V
1 mpt Ø.) Furthermore, as we discussed earlier, the optimal sampling probability
1 For MD sampling (31), which samples according the data ratio, the optimal mm |لl|l
P.
4: |I where gi %
sampling probability is př, Er. "lsf
Now we substitute the expressions of A and A2:
Bx(f(1++1)] S f(x)) - K [V + (VS(()) + nr kVK((()))) + T. - E111,,1111
50m L2
< f1x)) K
107. K2 Ti K2
((A4+++)))) [
(0 4Kog)
1/ T2 KL
OL
2
V
1
9
MML
LTP'1
Ee
1
K-1
Σ
2m
2n
mp:
2K
1=1 km0
5m
K??
12 KL
Lu
ml
$ fz)) cmLLK|| V((E)(
(o + (Kog)
+
of +
V
g.)
2
2m
2n
mp
(35)
where the last inequality follows from
mg 2K
Laj vi.
2 0 if mm S 1
KL and (a9) holds because
there exists constant > 0 (for some 7TL) satisfying
10L m ΣTh K K2 (A2 1) >>>0.
Rearranging and summing from t O...., T 1.we have:
cmL KmL < f(xo) - f(ZT) + K)m
(36)
Which implies:
< So S.
män E B(( tE(T]
cmML KT Tb
(37)
24

---

where
5m K L²
Mi 2m
LimE
(o] + 44o +
L 2nK Vmpp si
V(
(38)
D.1 Proof for convergence rate of FedIS (Theorem 3.1 under Assumption 13
In this section, we compare the convergence rate of FedIS with and without Assumption For comparison, we first provide the convergence result under Assumption 4
First we show Assumption 4 can be used to bound the update variance V mpp (mpp sampling probability FedIS
si) and under the
K
K
V
of
K
E
Sk,)l
K2
map
(39)
While for using Assumption
instead of additional Assumption
we can also bound the update
variance:
K
1
V
-
K
VF Eu.
mp
N=
R=
k
+ K
Vf(x))
(40)
We replace the variance back to equation
35
E [[([(++))]] f(xx) MuL K [x))))
+ ((x))(
f(x))) - miLK
1
1
10L
1OLL3=210 1
(A2 +1) [[
L2
(o) +4K0g)
1/ KL
07.
Li
V
1
(2)
TNTL
Laiin
E,
V (F,
2m
2n
mp!
2K
k=0
LaMi (A² +1)
S {1(xx) - "/1,
1/2 101.3 10 12 (A² +1
|| [xx))]
2n
5पm T2
(oî + 4Kog) + n2 KT.
Lnp
07. +
K2
2
2m
2n
ML
m
K-1
E,
VF
2K
2
m
(41)
This shows that the requirement for nı is different. needs that there exists a constant c > 0 (for
some 7).)) satisfying 10L k 2/ (A2 + 1) K(A+k) > 0. One still guarantee
2n
that there exists constant for 7).. to satisfy this inequality according to the properties of quadratic functions. Specifically, for the quadratic equation - 100 22 LnK[A²+1) and 1 0. Based the solution of quadratic 2n equations, we can ensure that there exists a 7/ > 0 solution.
(A² + 1)ri. Lnk(A mr + 2/2
2n
know that 10z (AA 1) 0,
Then can substitute equation 35 with equation
and let m/r.
O - and "
VTKL
o ( (VKn), yielding the convergence rate of FedIS under Assumptions
min E V < so (P--T) +o
of VnkT
)
M T
Koy VnKT
+0
+
(42)
E
order 4
25

---

E Convergence of DELTA. Proof of Theorem 3.5
E.1 Convergence rate with improved analysis method for getting DELTA
As we see FedIS can only reduce the update variance term in D. Since we want to reduce the convergence variance as much as possible, the other term øz and og still needs to be optimized. However, it is not straightforward to derive the optimization problem from O. In order to further reduce the variance in + (cf. 4.. i.e., local variance (a))) and global variance (aG), divide the convergence of the global objective into a surrogate objective and an update gap and analyze them separately. The analysis framework is shown in Figure g
surrogate objective f(())
Lemma
Global objective (s:)
- +
(Lemma 82
Theorem 4.3
Objective Gap
xf
(())
bounded convergence quurggate objectiog
Convergence variance of global objective eq(12): = 4.o + A + Ag Var (ml al)
Convergence variance surrogate objective eq(7) eq(8):
Theorem
Bg Σ of + B3 Σ
Curotery E.1
Corolbrry 42]
FedIS: ş
DELTA: g/
In ((ee) Wici) En (ool) 9/(01P Fount Optimizing the variance term wxt to p!
Optimizing variance
Figure 8: Theoretical analysis flow. The figure shows the theoretical analysis flow of FedIS (left) and DELTA
(right), highlighting the differences in sampling probability due to variance.
As for the update gap, inspired by the expression form of the update variance, we formally define it as follows:
Definition E.1 (Update gap). order to measure the update inconsistency, we define the update gap:
X E [||//(x)) - -[[
(43)
Here, the expectation taken over the distribution of all clients. When all clients participate, we have x = 0. The update inconsistency exists as long only partial set of clients participate.
The update gap is direct manifestation of the objective inconsistency in the update process. The presence of an update gap makes the analysis of the global objective different from the analysis of the surrogate objective. However, by ensuring the convergence of the update gap, we can re-derive the convergence result for the global objective. Formally, the update gap allows us to connect global objective convergence and surrogate objective convergence as follows:
E| (==)) = B||J +
(44)
The equation follows from the property of unbiasedness, as shown in Lemma
To deduce the convergence rate of the global objective, we begin by examining the convergence analysis of the surrogate objective.
Theorem F.2 (Convergence rate of surrogate objective). Under Assumption D3
and let local and
global learning rates y) and Tι satisfy TL 1/L/4OK1, V ErE mi/ and MML 1/II, the minimal
gradient norm of surrogate objective will be bounded as below:
minie E. V (xx)
(45)
where 8 f(o)) ft= f(x)), the expectation is over the local dataset samples among workers.
0 is the new combination of variance, representing combinations of local variance and client gradient diversity.
For sampling without replacement:
T
Kni.
E b.
i= m o7.5
(46)
2mn
26

---

For sampling with replacement:
32 Σ P (o2,, + 4KC +
Lou? 2m
Ei=1 m o2.
(47)
where (a.s represents client gradient diversity: Ça. (z.)
Vz(x)) and is constant.
The proof of Theorem E.2 is provided in Appendix E.2. and Appendix E.2.2 Specifically, the proof for sampling with replacement is shown in Appendix E.2.1 while the proof for sampling without replacement is shown in Appendix F.2.2
Remark E.3. We observe that there is no update variance in & but the local variance and global variance are still present. Additionally, the new combination of variance & can be minimized by optimizing the sampling probability, as will be shown later.
Derive the convergence from surrogate objective to global objective. As shown in Lemma C.
unbiased sampling guarantees that the expected partial client updates are equal to the participation
of all clients. With sufficient training rounds, unbiased sampling can ensure that the update gap x² will converge to zero. However, we still need to know the convergence speed of x² to recover convergence rate of the global objective. Fortunately, by the convergence rate of the surrogate objective according to Definition E.1 and Lemma C.2 This means that the update gap can achieve at least the same convergence rate as the surrogate objective.
can bound the convergence behavior of xi
Corollary E.4 (New convergence rate of global objective). Under Assumption and based on the above analysis that update variance is bounded, the global objective will converge to stationary point. Its gradient is bounded as:
mine Ty V f(x:)l min,e E(VV(()))I** Elxx2l| & min 2E f(x)))
8- cmi.KT KT
(48)
Theorem E.5 (Restate of Theorem 3.5). Under Assumptions and the same conditions as in Theorem 3.7 the minimal gradient norm of the surrogate objective will be bounded as follows by setting nL -TKL and 1/V Kn. Let the local and global learning rates nj and Ti satisfy
IL
V40RL - mp!
and mI S 1.
KL-
Under Assumptions 1 and with partial worker
participation, the sequence of outputs xn generated by Algorithm satisfies:
F
min E VS(D)) TE
$
(49)
KT
c
where F F= (xx), and the expectation is over the local dataset samplings among workers. c is constant. SG.s is defined as client gradient diversity: Ça.+ = [[ - fxx()))
For sample with replacement: H 5L"
Σ
(of, 4KC2.) + LML Σ m² 2..
2m
2
For sampling without replacement: +
5L.Kni
Σm 2 4KCO.)
LaLa
Em
oL.
2mn
2n
Remark E.6 (Condition of 1T.)) Here, though the condition expression for ne relies dynamic sampling probability pl, we can still guarantee that there constant q) satisfies this condition.
Er Vanaa Caraa,aaaaae
Specifically, one can substitute the optimal sampling probability 1
P.
back to the above inequality condition. As long the gradient Villa)) is bounded, max, Vaisa, tazo7 min, 20,
1 m² Em L Vaisa,, tazol., Vaice.. t0
S G. therefore 2 C, where G and C are
we can ensure
E t
togo Voisg, to
2 10
1010
Em
positive constants. Thus, we can always find constant to satisfy this inequality under dynamic sampling probability pi:
'In the Appendix, we abbreviate Ca,s. to Co. for the sake of simplicity in notation, without any loss of generality.
27

---

Corollary E.7 (Convergence rate of DELTA), Suppose and are such that the conditions and nj = (VKn) Then for sufficiently large T,
mentioned above are satisfied, aL =
VTKL
the iterates of Theorem 3.3 satisfy:
F VnkT
of VnkT
o + 4K
min EE[T]
S
+0
+0
(50)
KT
Lemma E.8. For any step-size satisfying Vi S SLK- we can have the following results:
B| =a 5K
+ +
(51)
where Cc., [z))))) f( and the expectation is over local SGD and filtration of zo
without the stochasticity of client sampling.
Proof.
Bell=r - xz 1|
Ee Bell - -1 1|?
$ (1 + 2K - [1
BBll=i Iit 1/2 (g
VR()))
4KKE | | V (-) + V
1
< 2K EE 1 k- 2, 11 2 + 4K 1 x1
+ 44KK2 + 4K (A²
I (1 + K
E -
21 + n + 4K. + 4A + +1)mm
(52)
Unrolling the recursion, we get:
k-
E,|l=/, - 2el1? < Σ (1+
[1 + +4K +4K + 1)
K
p=0
s (K- 1) (1 K )k -1
[nioi 4Kr2 + V(x,)1
< 5K 5K + 4K (2. 20 (()))
(53)
E.2 Proof for Theorem
E.2
In Section for sampling with replacement is shown in Appendix E.2.1 while the proof for sampling without replacement is shown in Appendix E.2.2
E.2. and Section 2
provide the proof for Theorem E.2
Specifically, the proof
E.2.1 Sample with replacement
fo fa
1
min E (f(x))1
$
(54)
CTTLKT
c
where 5h
5L2 2mn
Em
pr
(02
+ 4KC
+
2n
Dm
m
D
28

---

Proof.
(o1) Bx]f(r++1) - f(x+)= + E, zil) E + - -. 11 -
i((n)) + ( (Vi(at)) E. (M + mm. WH KVj(()))) + "
- -((a))-m.h mm v(()) + (V((a.)) + mKVf((o))
- E.
Aa
A1
(55)
Where (al) follows from the Lipschitz continuity condition. Here, the expectation is the local data SGD and the filtration of zt. However, in the next analysis, the expectation is over all randomness, including client sampling ,his is achieved by taking expectation on both sides of the above equation over client sampling.
To begin, let consider A1:
A
f(at), E, + + MV
((x)) E.
nL + nL HVKKKK ((x)))
St
map
VES.
k=0
K-1
(a2)
V (xxx), Ra[
n. +
mp!
sES.
KnLVf(x))
VII VK
E,
(F(())))) +
mp
iES:
k=0
(a3)
KmL
V (xx)))
+
M
Er
( + +KV((aI)))
2K
mp
sES,
k=0
?h Exll
-
1
Σ
vR(GW11
(56)
2K
TI
mp
EE
k=0
where (a2) follows from Assumption
and (a3) due to (r. = = [||=]]2 + |1v/12
1| - y/I for
J (kn V V(()) and y
Eies, mp! IK-1 (.r(aa) + KVJ(x)).
K
29

---

To bound A1, we need to bound the following part:
K-1
Edll
1
Σ
VF kVf(z))
n1
iES, mp,
k=
K
vP(()N)))) 1
=Eall
(F((1))
=
mp
mp
iE
k=0
iES.
k=0
(n4)
K
K-1
Exll (VR(2))) -VF()+))-V((.)]]]
71
mp!
SES
k=0
K-1
K
B& (1
(VF((z) ( [)}
mp:
iES; km0
K
K-1
VFi( - vF(2))1
π
m
IES, K=0
1=1
K-1 m
K
E, (2)()) VF((,))11
(05)
K
1
El 12a12
Pl
(a6)
L
Σ
(5K(n207 44K)) + 20K (A2 + +1m1 (
12
Pi
1=1
SL2K2m7
1i
(02 + 44K0)) + 20L 1
[f(())1
(57)
m
m²
1=1
where (a4) follows from the fact that E| +...+,,'' nE (Iar) 12 + + 1x,,1)) 12) (a5)
consequence of Assumption [ and (a6) is a result of Lemma E.8 Combining the above expressions, obtain:
KuL
33 ni
A 5
V (zxx)))
Σ
(oL +4K()))
2
2K
m
p/:
20L K 1/ (A² + 1) m
V (xx)))
7L
Eell
Σ
K-1
VE((W1) (58)
m
2K
mp
iES.
k=
30

---

Next, we consider bounding A2:
A2
Be|1
Σ
E
T
9i,k
my!
S
k=0
K
1
1
1
E
Pi,k
V
F.
(2 (c(,
+ B
VF (2
π
mp,
mp!
n E
mp
Am 0
C
k=0
K
2
K
gi
(Mt,))
. Rt
(
2
mp!
mp!
71
mp:
VES.
k=0
IES.
k=0
K
K-1
2
Σ
E2
E
Loi
- v(((((,))) )
18
+ n2 E
VE(T(A)
mm:
mpp
K=
iES.
K-1
K-1
1
111
E2
+ E
n
m²pp
mp!
k=
iES:
k=
(07)
K
m
o
+
E, o
Σ
K-1
(59)
n
m2pi pi
n EE
mp!
k=
where S represents the whole sample space and (a7) is due to Assumption 2
Now we substitute the expressions for Ai and Ag and take the expectation over the client sampling distribution on both sides. It should be noted that the derivation of A and A2 above is based on considering the expectation over the sampling distribution:
L /i( + Tn (vi(z), A. + ML kVf((()))
f(8411) S (31)) -MLK
+ " "
(a8)
1
20K 1/2 I.2 (A22 +1)
m
V [((E)) |?
S f(zz)
KTML
E,
2
m?
pi
51,2 2 11
m
(ol + (K.))))
2m2
pl
1n12,12K K
Lnfan
K-1
of
1971.
E
V (
2n
m Pi
2K
2
mp!
iES,
k=0
(09)
20K2 1/ (A2 + +1)
m
1 f(xz)
KNMLL
E. f(
2
m²
51.2 K2 x2n2nn1
m
Tn K
m
(OL + (KK))
m²pi o7.
2m2
pi
2n
(a10)
f(x))
cKuma, Fyj [xx))1
5L.22210 11
1
(oz +
AK +
L K
1
0i:
2m2
Pl
2n
m
m2pp
pt
(60)
where (a8) comes from Lemma C.2
(a9) follows from
MNL 2K
Laj² n9.
> Of mm
-
1 and (a10)
2
KI
holds because there exists a constant 0 satisfying
(1
20 n/ 1.² (1p
Σm
1=1 +
}>>>>01 0ff
m²
I < 22/10(24+1)KL 1 Em
31

---

Rearranging and summing from t == O,....T - 1, we have:
.T.
T-1
onu om.,EilV(a.))" f(x0)) f(xr)
5L2
K)
Σ 2m² 1=1 pi
(o + +KKGa,)
Σ
oi
(61)
2n
m
1=1
Which implies:
fo - fa
1 -
min E| (f(x))1
(62)
T
emp KT
where 4-
Kn)
Di=1
(o + 4 +
Lagg 2n
Ei= mapp
2m
Pl
E.2.2 Sample without replacement
So So
min E V (2 - TE
(63)
CT
where & 5L*Kni
2mn
E pl
(o + 4K( +
LaGn 2n
1== m pr
O..
Proof.
Blaet1 (((r))))((ett -m1) L
B[((x+t)) S ((x) (vi())),
F. [1,101 [1 -x:1]
= f(xx) (Vf(z,) In f + I. "
= f(xx) mL K v + (V(()), E. + M ML f(x)))
L + 7 EIA (64)
Where the first inequality follows from Lipschitz continuous condition. The expectation here is taken over both the local SGD and the filtration of xg. However, in the subsequent analysis, the expectation is taken over all sources of randomness, including client sampling. Similarly, consider A₁ first:
A
(xxz). E.lA, + (LKV
MLSiA + nLKVi(ED)) ))
Sel
mp
iES.
(.(())))))) + (m.k)((.
I..
SSP
mp
K-1
(((( +
E,
VK
mp
iES,
km
V fxz))
MT. E
VF(((,)) +KV](x))
2
2K
n2
mp
E,
(..(
(65)
2K
11
mp
iES.
k=0
32

---

Since z; are sampled from S, without replacement, this causes pairs zu and z22 to no longer be independent. We introduce the activation function as follows:
1m - {
if E St
(66)
otherwise.
Then we obtain the following bound:
K
E2
(.(()) BHOD--Viiin KVi(a))
mp
ieSt
k=0
m
v(((T(,)) 1 m
E
Fi (11))
71
map
71
mep
km
(61)
K-1 Σ
E
(VF((E)))) -F(((()
72
mpi
K-1
- VFi, (z2)) (F,, (
Eg
Im
12
mpn
11
Tm
mpl
k==
VF((22)) )
Ee
T
mpi
mpf
k=
Imm = 1
Ee
Im
VFi(E))
1
P(um = 1)
mpi
mpt
K-1
2
+
E,
(
1
VFi(ze))
1 0
x P( 0))
mpp
mpf
K-1
1 K-1
m
E
vF((zt)
2
mpi
mp
k=0
(b2)
L
K-1 m
BI 12
mn
1m
(b3)
T22K2
I
m
1
m
5K
(o, + 4 + + 1)
(67)
n
m
Pi
m pl
where (b1) follows from Em t1l2 = E ||ta|| + (t.
2 Σie(m m ml|tt/12
Eigg ||4 12 ((el) here is due to (2, v) 1/2 [||[|| + |4y 1- ||
/ 21) ). (b2) is due to
E||21 + +... + 22 < nE (1 112 + +... + || )l²), and (b3) comes from Lemma E.8
Therefore, we have the bound of Ai:
A <
KiL [2x 2
n2 L
5K
M
Σ
m 1
(0) + 4K(G.)
2n
m
1=1
m
222 + 1)
E,
V((((())) (68)
2K
T1
mpp
iE
k=
33

---

The expression for A2 is as follows:
A2 = Eg || |
E
- IL V1
Pi,k
mp
k=U
K-1 1
K
= 2 E
Di,k
(
+ rz E
v
mp:
mp
mpp
1E 1=0
iESt
k=
Ex
( - [F((x(+)))
+ M
(ot,))
mp!
mp
iES,
k=0
m
K
K-1 (a(())
n n
2 E
(gr.1
+ E
mp!
n
mp!
k=0
iES.
k=0
K Σ
22
K-1
1
= n n
Σ
B
G - (F(((()))))
+ 1
Σ
mp,
n1
mp
1=1
k=0
iES.
k=0
K m
+ mp
of +
Ee
(69)
n
m²
iE
k==
Now we substitute the expressions for A₁ and A₂ and take the expectation over the client sampling distribution on both sides. It should be noted that the derivation of Ai and A2 above is based on considering the expectation over the sampling distribution:
f(1(11) S f(x)) - -MLKEE [ (b1) S f(x)) - MMLK
1|"
+ +E (.
+ kKK((()) + +22 "'''
20L 22 (AA2 + 1)m2
Rel {xx))( + 2k² L2
(0z
nm
2nm
p1
+4K(2.) + LnZnn K
Ln
K-
MLL
E,
2n
2K
2
my
iES:
k=0
2K mm2 L
L
K
S f((z)) - KB
(of, + +4K +4,(2.)
of.
2nm
pf
2n
p
(70)
Also, for (b4), step sizes need to satisfy
70 2k
Lnf'
S kT. and there exists constant
>>> 0 satisfying
(1)
20x², n (AA +1)
D1=1 pl
c> 0f
17213
2 2/10 EE mi)
Rearranging and summing from t t= =.....,T 1,we have:
cmp KE (m.KK - ((o))) + T)m
(71)
Which implies:
fo f
min E V 21 v :E[T]
+ $
(72)
KT
C
where +-
Kn,
2mn
Σm
Fl
(o + 4K
+
Lang
2n
Di=1 mdp T.
34

---

Remark E.9. {G used in DELTA can be easily transformed into related term, thus it is fair compare DELTA with FedIS. particular, by taking the expectation on Sa. it equates to ((( Vf(x)) 12 As demonstrated in [1], one can derive E. F. V (xx))l ( (+))l I A[+]](=)] + oz. Shifting (T)]l to the left side of the convergence result, Sa can be directly transformed into aG-
E
E
Proof of the Optimal Sampling Probability
F.1
Sampling probability FedIS
Corollary F.1 (Optimal sampling probability for FedIS).
min +
s.t.
=1
p|=
pf
1=1
Solving the above optimization problem, we obtain the expression for the optimal sampling probabil- ity:
(73)
1a
where 9
Ek=o 9k is the sum of the gradient updates across multiple updates.
Recall Theorem 3.1 only the last variance term in the convergence term & is affected by sampling. In other words, we need to minimize the variance term with respect to probability. We formalize this follows:
min
V
gt) +
min P/E E =1 m
10
(74)
mp,
This optimization problem can be solved in closed form using the KKT conditions. It is straightfor- ward verify that the solution to the optimization problem is:
K-1 k
P
Vi 1,2, m.
(75)
k=
Under the optimal sampling probability, the variance will be:
Σ
Σ
K
E
VF Ek.)l
(76)
mp:
m
m
Therefore, the variance term is bounded by:
m
9
E
( < K2G
(77)
map
m
km
Remark: If the uniform distribution adopted with p 1 it is easy to observe that the variance m
Istl?
of the stochastic gradient bounded by According to Sauchy-Schwar inequality,
m 11? DE [ل+.1l -== 11 E Il@
T
1,
(78)
m
m
this implies that importance sampling does improve convergence rate, especially when [oo
Lima 19:
< <<1 m.
35

---

F.2 Sampling probability of DELTA
Our result is of the following form:
< fo - CTJTEE KT
man B Vf(x,)) E
(79)
It is easy to see that the sampling strategy only affects क. To enhance the convergence rate, need to minimize & with respect to pl. As shown, the expression for & with and without replacement is similar, and only differs in the values of n and m. Here, we will consider the case with replacement. Specifically, we need to solve the following optimization problem:
min Pi
-(
1 5L2
Σ
m
1 (oL. + 4KC2.) +
LALn
Σ
m
s.l.
M
pj
2m
2n
m2
Solving this optimization problem, we find that the optimal sampling probability is:
5KLNL + 4K(2,) 222,
Pi,
(80)
EE 5K LKLn + 4k 4KC2.) + 2o
For simplicity, we rewrite the optimal sampling probability as:
V an C3. + +02022
P
(81)
Ei= / + 022
where 01 = 20K LML, 02 = 5K + -.
Remark: Now, we will compare this result with the uniform sampling strategy:
Ei=1 v 01S3, + az
LALL 2c
DELTA
(82)
For uniform Pl 1.
Σm (Vaisa. + t2oz 2
LM
T Puniform
(83)
2c
According to Cauchy-Sehee Schwarz inequality:
Σm (Vaca azo7
mm Di=1
Vaise, + a2o
2
m Em (vanca + a2o7,
m
Em Vaise + a2
(84)
this implies that our sampling method does improve the convergence rate (our sampling approach might be n times faster in convergence than uniform sampling), especially when
(E t020
<< m.
EE, to1
G Convergence Analysis of The Practical Algorithm
In order to provide the convergence rate of the practical algorithm, we need an additional Assumption (x>)] G Vi). This assumption tells useful fact that will be used later:
can be shown that V FT // Fa refers to the last round in which client participated, and U is constant upper bound. This tells us
S U for all and k; where the subscript
36

---

Narm gradient
Norm gradient
5.55
(a) FedIS's gradient norm MNIST
(b) FedIS gradient norm on FashionM-
NIST
Figure 9: Performance of gradient of FedIS. We evaluate the performance of FedIS on MNIST and
MNSST datasets. In each round, we report the maximal and minimal gradient norm among all clients.
Norm gradient diversity
Norm of gradient diverstty
858868
Medredram
(a) Gradient diversity norm of DELTA on (b) Gradient diversity norm of DELTA on MNIST
FashionMNIST
Figure 10: Performance of gradient diversity norm of DELTA. We evaluate the performance of DELTA on MNIST and FashionMNIST datasets. In each round, report the maximal and minimal gradient diversity norm among all clients.
that the change in the norm of the client's gradient is bounded. U comes from the following inequality constraint procedure:
1 211
1 gf
V
03
E
94
<
EV
E
|103
|I
mp?
map
mp
|9
i=1
1o 1 1|2
1|
K
< E
|لواا
I m²
U²
m
K
E
(TK, Ex.0))?
(85)
km
We establish the upper bound U based on two factors: (1) Assumption 4, and (2) the definition of importance sampling (F)=)(((())) Ep(=) (=)) where there exists positive
2 7, we can easily ensure !g:ill U constant y such that p+(=) 2 7 0. Thus, for p Σ, 55 since 0 > 0 is consistently bounded.
To Il
In general, the gradient norm tends become smaller as training progresses, which leads to Ex,k)) going to zero. Even if there are some oscillations in the gradient norm, the gradient will vary within limited range and will not diverge to infinity. Figures and and Figure Io depict the norms of gradients and gradient diversity across all clients in each round. Notably, these figures demonstrate that in the case of practical IS and practical DELTA, the change ratio of both gradient and gradient diversity remains limited, with the maximum norm being under 8 and the minimum norm exceeding 0.5.
(Z
Based on Assumption and Assumption 3 we can re-derive the convergence analysis for both convergence variance + and Φb (46). In particular, for Assumption F < (A12 + 1))(2 + o.), we use OG.s and GG. instead of a unified oG for the sake of comparison.
Specifically, &- 1 5n 5 L
(o), + 4Kog) + maLoo +
Lam V (f where of 2nk
2m
Σ (. (R.s). With the practical sampling probability pf of FedIS:
m
9 m
V
0:
-E
9
9 <
El|
03
(86)
mp?
mp,
m
mp!
m 9
1=1
37

---

According to Assumption
we know
S SU2
Then we get
D
K
of
E
9
I 1
U
v
mp
91
m
km
U2
K
E
Fi St,,))
(87)
m
Similar to the previous proof, based on Assumption
we can get the new convergence rate:
((V) S O (fTRT) +0
of vnkT
M
KUZGG
min E
+0
+0
(88)
T
VnKT
onder of
where M = of 4Koa...
Remark G.1 (Discussion on U and convergence rate.). It is worth noting that I F ( ( Exa)ll is typically relatively small because the gradient tends to go to zero as the training process progresses. This means that U can be relatively small, more specifically, U
the upper bound term O KKU /KU"oG.
VnkT Howeeer, this does not necessarily mean that the practical algorithm is better than the theoretical algorithm because the values of ag are different, as we stated at the beginning. Typically, the value of aG.s for the practical algorithm is larger than the value of oG.u which also comes from the fact that the gradient tends to go zero as the training process progresses. Additionally, due to the presence of the summation over both and k. the gap between oG.s and aG,t is multiplied, and oG NG..//G,t m2 K² U2. Thus, the practical algorithm leads to a slower convergence than the theoretical algorithm.
Similarly, as long as the gradient consistently bounded, we can assume that [ (x(x))] VV. Vx(x)) I Ú, S Ú and ||ate// S U2 I Ü for all i, where oZ.. = - VI. { (x.))l Then, we can obtain a similar conclusion by following
the same analysis Φ.
Specifically, we have कb Lag m 2m
Li=1 pr (a152. + a202,,) where on and are constants defined
in 13 For the sake of comparison of different participation rounds and I, rewrite the symbols as CG. and oi.-- Then, using the practical sampling probability pt of DELTA, and letting R
V Vaisa..
2 + a2ot 2
we have:
= 2m
LALL
m
(R))
2m
LM
(R
R
Σ (R2)²
2m
LAL
R R
R
R2
1=1
1=1
j=1
LA (2
La i2
LA
<
R
R
Σ
R
2mm
(R
2m²c
2m
2m2c
1=1
iml
im1
< LAL ( (ot.,, + 4KC2.)
! "
(89)
2c
Therefore, compared to the theoretical algorithm of DELTA, the practical algorithm of DELTA has the following convergence rate:
( VnkT
Üi + 2
min E// So
(f-r) VnkT
+0
SG,4
KT
(90)
This discussion of the effect of ú on the convergence rate is similar to the discussion of U in Remark [.1
38

---

H Additional Experiment Results and Experiment Details.
H.1
Experimental Environment
For all experiments, we use NVIDIA GeForce RTX 3090 GPUs. Each simulation trail with 500 communication rounds and three random seeds.
H.2
Experiment setup
Setup for the synthetic dataset. To demonstrate the validity of our theoretical results, we first conduct experiments using logistic regression on synthetic datasets. Specifically, we randomly generate (a, v) pairs using the equation y log (Am-b)² with given values for A₃ and b; as training data for clients. Each client's 's local dataset contains 1000 samples. In each round, we select 10 of 20 clients participate in training (we also provide the results of 10 of 200 clients in Figure 13).
To simulate gradient noise, we calculate the gradient for each client i using the equation gi ff((A, b;, D:) + V/, where A, and b, are the model parameters, D; is the local dataset for client i, and 14 a zero-mean random variable that controls the heterogeneity of client i. The larger the value of || the greater the heterogeneity of client i.
We demonstrate the experiment on different functions with different values of and Each function set with noise levels of 20, 30, and 40 illustrate theoretical results. To construct different functions, we set = 8, 10 and b = 2, respectively, to observe the convergence behavior of different functions.
All the algorithms run the same environment with a fixed learning rate of 0.001. We train each experiment for 2000 rounds to ensure that the global loss has stable convergence performance.
Setup for FashionMNIST and CIFAR-10. To evaluate the performance of DELTA and FedIS, train two-layer CNN the non-iid FaSHionMNIST dataset and ResNet- 18 the non-iid CIFAR-10 dataset, respectively. CIFAR-10 is composed 32 x 32 images with three RGB channels, belonging 10 different classes with 60000 samples.
The "non-iid" follows the idea introduced [66 [6], where we leverage Latent Dirichlet Allocation (LDA) to control the distribution drift with the Dirichlet parameter a. Larger indicates smaller drifts. Unless otherwise stated, we set the Dirichlet parameter a = 0.5.
Unless specifically mentioned otherwise, our studies use the following protocol: all datasets are split clients according to our proposed probability
with parameter of 0.5, the server chooses from the total of m = 300 clients, and each is trained for T = 500 communication rounds with K ==5 local epochs. The default local dataset batch size 32. The learning rates are the same for all algorithms, specifically ir globbbal = 1 and traeat = 0.01.
All algorithms use FedAvg as the backbone. We compare DELTA, FedIS and Cluster-based IS with FedAvg on different datasets with different settings.
Setup for Spli--PahiioMMNIST. FashionMNIST dataset. In particular, we let 10% clients own 90% of the data, and the detailed split data process is shown below:
this section, we evaluate our algorithms on the split-
Divide the dataset by labels. For example, divide FashionMNIST 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
To test our algorithm's efficiency diverse real datasets, we use the non-llI FEMNIST dataset and non-III CelebA dataset in LEAF, as given in [] All baselines use a 4-layer CNN for both datascts with learning rate of Irsocat 0.1. batch size of 32, sample ratio of 20% and
Setup for LEAF.
39

---

Yower sfchenc
PowerorCaope CRLAA
1550
200
30
2000
250
150
12
21
V
20
(b) A
8,
2,
30
=
Fowi of chote
Bects
90
1943
126)
76 26 100
12
20 020 70 1966
(d) 10, 1, 20
(0) A 10, 6 1,
(f) 10, 1, 40
Figure 11: Performance of different algorithms the regression model. The loss is calculated by f(x, y) 1 log( (A,a-1,) 14)2 report the logarithm of the global loss with different degrees of gradient noise
All methods are well-tunes and we report the best result of each algorithm under cach setting.
communication round of T = 500. The reported results are averaged over three runs with different random seeds.
The implementation detail of different sampling algorithms. The power-of-choice sampling method proposed by 77.. The sampling strategy is to first sample 20 clients randomly from all clients, and then choose 10 of the 20 clients with the largest loss the selected clients. FedAvg samples clients according to their data ratio. Thus, FedAvg promises to be unbiased, which given in to be unbiased sampling method. As for FedIS, the sampling strategy follows Equation (5). For cluster-based IS, it first clusters clients following the gradient norm and then uses the importance sampling strategy similar FedIS in each cluster. And for DELTA, the sampling probability follows Equation (13). For the practical implementation of FedIS and DELTA, the sampling probability follows the strategy described in Section 4
12 3D
H.3 Additional Experimental Results
Performance of algorithms on the synthetic dataset. We display the log of the global loss of where the Power-of-Choice is biased
different sampling methods on synthetic dataset in Figure 1I sampling strategy that selects clients with higher loss 7
We also show the convergence behavior of different sampling algorithms under small noise, shown in Figure 12
To simulate a large number of clients, we increased the client number from 20 to 200, with only 10 clients participating in each round. The results in Figure demonstrate the effectiveness of DELTA.
Convergence performance of theoretical DELTA Paiit-FashionMNNITT and practical DELTA on FEMNIST. Figure 14(a) illustrates the theoretical DELTA outperforms other methods conver- gence speed. Figure 14(b) indicates that cluster-based IS and practical DELTA exhibit rapid initial accuracy improvement, while practical DELTA and practical IS achieve higher accuracy in the end.
shows the accuracy performance of practical DELTA algorithms on FEMNIST with different sampled numbers of clients. In particular, the larger number of sampled clients, the faster the convergence speed is. This consistent with our theoretical result (Corollary 4.2
Ablation study for DELTA with different sampled numbers. Figure 15
40

---

poaereicnope DOL'A
pover mo30
DELTA
-10
200
123
70
2000
250
150
251
12
1200
(a)
10
(c)
NEWer more
Dover 2o30
FedS
280
900
2000
120
1900
1256
200
(d) V 0.5
(e) 0.1
Figure 12: Performance of different algorithms the regression model with different (small) noise settings.
poanta mone
poANericao DELTA
cowerd D1174
-40
10
1150
200
70
3000
1218
100
221
100
1200
(a)
30
(b) V
(c)
10
DILLA
350
750
1230
1203
1000
1750
2006
-10
250
2000 1250
1756
20
(d)
(e) V
Figure 13: Performance of different algorithms synthetic data with different noise settings. Specifically, for testing the large client number setting, in each round, 10 out of 200 clients selected participate in training.
Performance on FashionMNIST and CIFAR-10. For CIFAR-10, we report the mean of the best 10 test accuracies test data. In Table 2 compare the performance of DELTA, FedIS, and FedAvg on noD-IID FNSH and CIFAR-IO datasets. Specifically, we use 0.1 for FaShionMNIST and 0.5 for CIFAR-IO to split the datasets. As for Multinomial Distribution (MD) sampling [29], it samples based on the clients' data ratio and average aggregates. It is symmetric sampling and aggregation with FedAvg. with similar performance. can be seen that DELTA has better accuracy than FedIS, while both DELTA and FedIS outperform FedAvg with the same number of communication rounds.
Assessing the Compatibility of FedIS with Other Optimization Methods. In Table 4 we demonstrate that DELTA and FedIS are compatible with other FL. optimization algorithms, such as Fedprox 29 and FedMIME [20). Furthermore, DELTA maintains its superiority in this setting.
41

---

0.8
0.8
0.6-
0.5
0.5
0.2
Custerbaste basedbbeeddd 15
TecAwg
tecihacis
0.2
Chasteraases
Pedhig
Pestreed
0.1
z5o
10o
563
100
450
(a) Performance of algorithms FashionMNIST
on
split-
(b) Performance algorithms on FEMNIST
Figure 14: Performance comparison of accuracy using different sampling algorithms.
6.8
0.6
6.5
6.3
samplee nunber-5
sampled mumber- 10
sampled number=20
6.1
sampled number-40
0.0
100
200
300
400
500
Round
Figure 15: Ablation study of the number sampled clients.
Table Performance sampling algorithms integrated with momentum prox. We run 500 communi- cation rounds on CIFAR-10 for each algorithm. report the mean of maximum 5 accuracies for test datasets and the number of communication rounds to reach the threshold accuracy.
Sumpling momentum
Sampling proximal
Algorithm
Ace (%)
Rounds for 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 5 we demonstrate that DELTA and FedIS are compatible with other variance reduction algorithms, like FedVARP (18]
It is worth noting that FedVARP utilizes the historic update approximate the unparticipated clients' updates. However, in this setting, the improvement of the sampling strategy on the results is somewhat reduced. This is because the sampling strategy is slightly redundant when all users are involved. Thus, when VARP and DELTA/FedIS are combined, instead of reassigning weights in the aggregation step, we use (75) or (3) select the current round update clients and then average aggregate the updates of all clients. One can see that the combination of DELTA/FedIS and VARP can still show the advantages of sampling.
Table 5: Performance DELTA/FedIS in combination with Fed We 500 communication rounds on FashiouMNIST with 0.1 for each algorithm. We report the mean of maximum accuracies for test datasets and the number of communication rounds to reach the threshold accuracy.
FashionMNIST
Algorithm
Acc (%)
Rounds for
FedVARP
73.81 +: 0.18
470
FedIS FedVARP
73.96 1: 0.14
452
DELTA +FedVARP
74.22- 0.14
436
42

---

In addition to the above optimization methods like VARP, we also conduct experiments on LEAF (FEMNIST and CelebA) with other non-vanilla SGD algorithms, namely Adagrad and Adam, to show that the proposed client selection framework be applied to federated learning algorithms other than vanilla SGD. The results are shown Table and Table
Table 6: Performance of sampling algorithms integrated with Adagrad and Adam FEMNIST. We
1000 communication rounds on FEMNIST for each algorithm. particular, we set the global learning rate 7 = 0.01 to ensure convergence of Adagrad Adam. We report mean of the maximum 5 accuracies for test datasets and the average number of communication rounds that reach the threshold accuracy 80%.
Sampling Adagrad
Sampling Adam
Algorithm
Acc (%)
Rounds for 80%
Acc (%)
rounds 80%
FedAvg
80.93 0.08
893 (1.0x)
80.04 +
882 (1.0x)
Cluster-bused IS
80. 00.69900.42
760 (1.17%)
79.11=
FedIS
80,96 0.31
723 (1.24x)
80.10 #0.25
787 (L.12x)
DELTA
81.79 0.09
612 (1.46x)
80.92 #0.27
600 (147x)
Table Performance of sampling algorithms integrated with Adagrad and Adam on CelchA. We run 1000 communication rounds on CelebA for each algorithm. In particular, we set the global learning rate 7 = 0.01 to ensure convergence of Adagrad and Adam. We report the mean of the maximum of accuracies for test datasets and the average number of communication rounds that reach the threshold accuracy 80%.
Sampling Adagrud
Sumpling Adum
Algorithm
Acc (5)
Rounds for 80%
Acc (%)
rounds 80%
FedAvg
88.92 0.08
329 (1.0x)
89.04 # 0.22
244 (1.0x)
Cluster-based IS
89.71=0.10
329 (1.0x)
89.262 0.19
164 (1.49x)
FedIS
90.14 + 0.01
243 (1.35%)
89.92 +0.05
140 (1.74x)
DELTA
90.38 0.02
214 (1.54)
90.58 +0.07
109 (2.24x)
Table 8 provide results under some common thresholds, including 50% for CIFAR-10 and 80% for CelebA, to replace 54% for CIFAR-10 and 85% for CelebA in Table 2
Table 8: Performance of sampling algorithms under the common thresholds. We report the results of algorithms CIFAR-I0 with 50% threshold and on CelebA with 80% threshold. We run 500 communication rounds each algorithm. report mean of maximum 5 accuracies for test datasets and the average number of communication rounds that reach the threshold accuracy.
CIFAR- 10
CelebA
Algorithm
Acc (%)
Rounds for 50%
Acc
rounds for 80%
FedAvg
54,28 0.29
181 (1.0x)
85.92 + 0.89
339 (1.0x)
Cluster-based IS
54.83+ 0.02
187 (0.91x)
86.77= 0.11
303 (l.1x))
FedIS
$5.05 0.27
168 (1.07x)
89.12 10.71
261 (1.29x)
DELTA
55.20 0.26
151 (1.20x)
89.67 +0.56
257 (1.32x)
Albation study for a. In Table g we experiment with different choices of heterogeneity a in the CIFAR- 10 dataset. The parameter of heterogeneity changes from 0.1 to 0.5 to 1. We observe consistent improvement of DELTA compared the other algorithms. This shows that DELTA is robust to changes in the level of heterogeneity in the data distribution.
Table 9:
Performance of algorithms under different a. We run 500 communication rounds on CIFAR 10 for each algorithm (with momentum). We report the mean of maximum 5 accuracies for test datasets and the number of communication rounds reach the threshold accuracy.
Algorithm
Acc (%)
Rounds for 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
283
0.7248
221
43


Reviews:
[{"review_id": "ol2x0LHaDn", "reviewer": "Reviewer_71Y7", "summary": "This paper studies the sampling schemes in federated learning. In particular, the authors first develop a new analysis method for important sampling (IS) strategy, which achieves a better convergence rate and then they propose a new sampling approach called DELTA, which can outperform the IS scheme. In addition, the authors also proposed a practically implementable version of DELTA and the performance is evaluated using experiments.", "questions": "1. The improvement of the proposed analytical approach is unclear. It seems all the approach achieve a $O(1/\\epsilon^2)$ of the communication complexity. \n\n2. When IS is analyzed, Assumption 3 is used, whereas DELTA is analyzed, it seems that Assumption 3 is not used while the gradient diversion $\\zeta_{G,i,t}$ is used, since $\\sigma_G$ is not part of Theorem 3.4. From Corollary 3.7 and compare it to Theorem 3.1, it seems the advantage of DELTA is to eliminate the term of $\\sigma_G$. If it is correct, it seems that it is a little bit unfair to use different assumptions to analyze the two different approaches. \n\n3. The novelty of the analysis has to be more elaborated. Please clearly state the main differences between the proposed analysis and other analysis in the literature such as IS and many works related to FedAvg. To me, it is a pretty standard \"by round\" analysis for nonconvex objective functions.", "limitations": "The authors discussed the limitations of the work in the end.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The authors develop a new convergence analysis for IS for nonconvex objective functions. \n\n2. The authors propose a new sampling approach called DELTA and propose a practically implementable version of DELTA.\n\n3. The proposed algorithm is evaluated using experiments.", "weaknesses": "1. The novelty of the analysis is unclear. It seems a standard \"by round\" analysis. Since the authors claim the analysis is one of the major contributions of this paper. I suggest the authors to elaborate this point in detail. \n\n2. The Assumption 4 seems strong and can significantly simplify the analysis in general. In addition, it  can be violated easily in practice. \n\n3. The wring of the paper is not careful enough. Many parameters are presented without explanation although it is not very hard to figure them out. For example, in Theorem 3.1, many parameters such as K and T are not explained. In addition, instead of just mentioning some lemmas and assumptions in the appendix or other papers, it will be much better to state them in the main paper to make the reading easier.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer 71Y7 , we would like to thank you for your time spent reviewing our paper and for providing constructive comments. Please kindly find our responses to your raised questions below:\n\n> The novelty of the analysis is unclear. Please clearly state the main differences between the proposed analysis and other analysis in the literature such as IS and many works related to FedAvg.\n> \n\nThanks for your suggestion, we would like to elaborate on the novelty of our analysis. Please see “Reply to All Reviewers” for details.\n\n> Assumption 4 seems strong and can significantly simplify the analysis in general. In addition, it can be violated easily in practice.\n> \n\nThank you for your comment. We would like to explain the soundness of Assumption 4:\n\n- This assumption is essential for IS methods [1,2,3]. Furthermore, it finds common usage in the FL community for convergence analysis [4,5,6,7].\nIn particular, according to the definition of IS, $E_{q(x)}[h(x)]=E_{p(x)}\\left[\\frac{q(x)}{p(x)} h(x)\\right]$, where $q(x)$ is the given sampling distribution, $p(x)$  is our proposed sampling distribution and $h(x)$  is the value function. With a little work (similar to our Corollary F.1), one can prove the variance is minimized when $p^*(x) \\propto q(x)\\|h(x)\\|$. If $\\|h(x)\\|$ is not consistently bounded, $p(x)$ is meaningless.\n- We would like to clarify that in our practical algorithm of DELTA, the used assumption is gradient heterogeneity bound: $E|| \\nabla F_i(x_t)-\\nabla f(x_t)||^2 \\leq G^2$ instead of Assumption 4, as used in eq (89) of the convergence analysis of the practical algorithm. This is a looser assumption than Assumption 4.\n- Figure 1 in the one-page response PDF demonstrates the gradient norm of FedIS on MNIST and FashionMNIST datasets, suggesting gradient can be bounded.\n\n> The writing of the paper is not careful enough.\n> \n\nSorry for any confusion arising from the simplicity of the symbols.\n\n- While we define the terms in Algorithm 1, we will also add the meanings of K and T in Theorem 3.1: T is the total communication round and K is the total local epoch times.\n- Due to the page limit, we present the lemma details in the Appendix. We will include the lemmas in the main paper along with streamlined explanations.\n\n> The improvement of the proposed analytical approach is unclear. It seems all the approach achieve a $\\mathcal{O}(\\frac{1}{\\epsilon^2})$ of the communication complexity.\n> \n\nWe would like to clarify the concise communication complexity of these approaches is $\\mathcal{O}(\\frac{1}{\\epsilon^2}+\\frac{1}{\\epsilon})$ or $\\mathcal{O}(\\frac{1}{\\epsilon^2}+\\frac{1}{\\epsilon}+\\frac{1}{\\epsilon^{3/2}})$, as shown in Table 2 of [8] and Table 1 of our paper. The relevance of the additional terms becomes significant when the dominant term $\\mathcal{O}(\\frac{1}{\\epsilon^2})$ is the same for all approaches.\n\nWe provide a convergence rate table for comparison, highlighting the improvement in our approach when all these algorithms share a dominant communication complexity of $\\mathcal{O}(\\frac{1}{\\epsilon^2})$ ($\\mathcal{O}(\\frac{1}{\\sqrt{T}})$).\n\n| Algorithm | Convergence upper bound $\\min_{t \\in[T]} E\\left[\\|\\|\\nabla f\\left(x_{t}\\right)\\|\\|_{2}^{2}\\right] \\leq$ | Rate improvement |\n| --- | --- | --- |\n| FedAvg[9] | $\\frac{1}{c}\\left(\\frac{f^{0}-f^{*}}{\\sqrt{nKT}}+\\frac{\\sigma_L^2+3K\\sigma_G^2}{2\\sqrt{nKT}}+\\frac{5(\\sigma_L^2+6K\\sigma_G^2)^2}{2KT}+\\frac{15(\\sigma_L^2+6K\\sigma_G^2)}{2\\sqrt{nKT^3}}\\right)$ | -- |\n| FedIS(others)[7] | $\\frac{1}{c}\\left(\\frac{(f^{0}-f^{*})B^2}{\\sqrt{n K T}}+\\frac{2F \\sigma_{L}^{2}+2F(1-n/m)K\\sigma_G^2}{2\\sqrt{n K T}}+\\frac{B^2F}{T}+\\frac{F^{2/3}\\sigma_G}{T^{2/3}}\\right)$ | reduce the coefficient of $\\sigma_G$ |\n| FedIS(ours) | $\\frac{1}{c}\\left(\\frac{f^{0}-f^{*}}{\\sqrt{n K T}}+\\frac{\\sigma_{L}^{2}+K \\sigma_G^{2}}{2\\sqrt{n K T}}+\\frac{5(\\sigma_L^2+4K\\sigma_G^2)}{2T}\\right)$ | remove $\\mathcal{O}(\\frac{1}{T^{2/3}})$ and reduce the coefficient of $\\sigma_G$ |\n| DELTA | $\\frac{1}{c}\\left(\\frac{f^{0}-f^{*}}{\\sqrt{n K T}}+\\frac{\\sigma_{L}^{2}}{2\\sqrt{n K T}}+\\frac{5(\\sigma_{L}^{2}+4 K \\zeta_{G}^{{2}})}{2K T}\\right)$ | further improve the coefficient of $\\mathcal{O}(\\frac{1}{T^{1/2}})$ |\n\n> When IS is analyzed, Assumption 3 is used, whereas DELTA is analyzed, it seems that Assumption 3 is not used while the gradient diversion $\\zeta_G$ is used,it seems that it is a little bit unfair to use different assumptions to analyze the two different approaches.\n> \n\nThank you for your suggestion. We would like to clarify that the term $\\zeta_G$ of DELTA can be easily transformed into a  $\\sigma_G$ related term, thus it is fair.\n\nIn particular, by taking the expectation on $\\zeta_G$, it equates to $E||\\nabla F_i(x_t) - \\nabla f(x_t)||^2$. As demonstrated in [10], one can derive $E||\\nabla F_i(x_t)-\\nabla f(x_t)||^2 = E||\\nabla F_i(x_t)||^2 -||\\nabla f(x_t)||^2 \\leq A||\\nabla f(x_t)||^2 + \\sigma_G^2$. Shifting $A\\|\\nabla f(x_t)\\|^2$ to the left side of the convergence result, $\\zeta_G$ can be directly transformed into $\\sigma_G$.\n\n[1]Stochastic optimization with importance sampling for regularized loss minimization, ICML 2015\n\n[2]Not all samples are created equal: Deep learning with importance sampling. ICML 2018\n\n[3]Low-Cost Lipschitz-Independent Adaptive Importance Sampling of Stochastic Gradients. ICPR, 2021\n\n[4]Diverse client selection for federated learning: Submodularity and convergence analysis. ICML 2021\n\n[5]On the effectiveness of partial variance reduction in federated learning with heterogeneous data. CVPR. 2023\n\n[6]Sharper convergence guarantees for asynchronous sgd for distributed and federated learning. NIPS, 2022\n\n[7]Optimal client sampling for federated learning. TMLR, 2022.\n\n[8]Scaffold: Stochastic controlled averaging for federated learning. ICML 2020.\n\n[9]Achieving linear speedup with partial worker participation in non-iid federated learning. ICLR 2021.\n\n[10]A unified theory of decentralized sgd with changing topology and local updates. ICML 2020."}, {"review_id": "NusnqM41nR", "reviewer": "Reviewer_1Yft", "summary": "The paper proposes a novel unbiased client sampling scheme called DELTA for Federated Learning (FL). The authors address the issue of unrepresentative client subsets in FL, which can lead to  significant variance in model updates and slow convergence. They show that existing unbiased sampling methods have limitations in terms of convergence speed and redundancy. In contrast, DELTA selects diverse clients  with significant gradients without clustering operations. The authors also propose practical algorithms for DELTA and Importance Sampling (IS) that rely on accessible client information. The results are validated through experiments  on both synthetic and real-world datasets.", "questions": "See the weakness part above. ", "limitations": "The paper does not explicitly address the limitations and potential negative societal impacts of the proposed work, but I do not think that this is a major issue. ", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The paper presents a novel unbiased sampling scheme for FL that addresses the limitations of existing methods. The approach of selecting diverse clients based on gradient diversity without  clustering operations appears to be new and promising.\n2. The paper provides theoretical analyses and experimental results to support the proposed sampling schemes. The convergence rates of the practical algorithms are shown to attain the same  order as the theoretical optimal sampling probabilities.\n3. The paper is well-organized and clearly presents the motivation, methodology, and results of the study. The figures effectively illustrate the concepts and comparisons between different sampling methods. ", "weaknesses": "1. In Corollary 4.2, the convergence rate of the practical algorithm depends on a term $\\tilde{U}$, which can be very large if $\\left\\|\\nabla F_i\\left(x_s\\right)-\\nabla f\\left(x_s\\right)\\right\\|$ is small. \n\n2. Can the proposed client selection framework be applied to federated learning algorithms other than vanilla SGD. I believe a unified theoretical analysis would show the effectiveness of the proposed method.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer 1Yft, we sincerely appreciate your thorough review of our paper. We have diligently incorporated your feedback to enhance the quality of our work. Kindly find our comprehensive responses to your questions outlined below:\n\n\n> In Corollary 4.2, the convergence rate of the practical algorithm depends on a term $\\tilde{U}$, which can be very large if $||∇F_i(x_s)−∇f(x_s)||$ is small.\n> \n\nWe would like to clarify that $\\tilde{U}$ will not be very large. $\\tilde{U}$ are determined by $U_1=\\frac{||\\nabla F_i(x_t)-\\nabla f(x_t)||}{||F_i(x_s)-\\nabla f(x_s)||}$  and $U_2=\\frac{||\\sigma_{L,i,t}||}{||\\sigma_{L,i,s}||}$, where $t$ represents the current training round and $s$ represent the last participated round of client $i$. Specifically,\n\n- $U_1=E(\\frac{||\\nabla F_i(x_t)-\\nabla f(x_t)||}{||F_i(x_s)-\\nabla f(x_s)||})$ represents the gradient diversity change ratio between rounds. As training progresses, gradient diversity typically diminishes, leading to a change ratio smaller than 1.\n- Additionally, Figure 2 in the one-page response PDF illustrates the minimum and maximum norms of gradient diversity per round across all clients. Even in the most adverse scenario where $||\\nabla F_i(x_t) - \\nabla f(x_t)||$ is chosen as its maximum and $||\\nabla F_i(x_s) - \\nabla f(x_s)||$ is chosen as its minimum, $U_1$ is constrained. The minimum value across all rounds exceeds 0.5, while the maximum value remains below 8.\n- In addition to $U_1$, the local variance-related term $U_2$ also contributes to the overall value of $\\tilde{U}$. The precise expression for $\\tilde{U}$ is $E\\left|\\left|\\frac{R_i^t}{R_i^s}\\right|\\right|$, where $R_i^s = \\sqrt{\\alpha_1||\\nabla F_i(x_s) - \\nabla f(x_s)|| + \\alpha_2\\sigma_{L,s}}$. Therefore, due to the presence of $\\sigma_{L,s}$, the denominator remains sufficiently nontrivial, preventing an excessive increase in the value of $\\tilde{U}$.\n\nThe above discussion regarding $\\tilde{U}$ is provided in Remark G.1 and eq (89) of Appendix G, and we refer to the discussion in the paper L283. \n\n> Can the proposed client selection framework be applied to federated learning algorithms other than vanilla SGD. I believe a unified theoretical analysis would show the effectiveness of the proposed method.\n> \n\nWe appreciate your suggestion. In addition to the results already presented in Table 2, which include momentum, prox, and VARP, we are willing to provide additional experimental results. \n\nSpecifically, we conduct experiments on LEAF (FEMNIST and CelebA) with other non-vanilla SGD algorithms, namely Adagrad and Adam. The results are shown in the below Table:\n\n| Algorithm on FEMNIST | Adagrad  |  | Adam |  |\n| --- | --- | --- | --- | --- |\n|  | Accuracy (%) | Rounds for 80% | Accuracy (%) | Rounds for 80%  |\n| FedAvg | 80.93 ± 0.08 | 893 (1.0$\\times$) | 80.04 ± 0.15  |  882  (1.0$\\times$) |\n| Cluster-based IS | 80.69±0.12 | 760 (1.17$\\times$)  | 79.11± 0.18 | - |\n| FedIS | 80.96 ± 0.03 | 723 (1.24$\\times$) | 80.10 ±0.25 | 787 (1.12$\\times$) |\n| DELTA | 81.79  ± 0.09 | 612 (1.46$\\times$) | 80.92 ±0.07 | 600(1.47$\\times$) |\n\n| Algorithm on CelebA | Adagrad  |  | Adam |  |\n| --- | --- | --- | --- | --- |\n|  | Accuracy (%) | Rounds for 80% | Accuracy (%) | Rounds for 80%  |\n| FedAvg | 88.92 ± 0.08 | 329 (1.0$\\times$) | 89.04 ± 0.22  |  244  (1.0$\\times$) |\n| Cluster-based IS | 89.71±0.10 | 329 (1.0$\\times$)  | 89.26± 0.19 | 164 (1.49$\\times$) |\n| FedIS | 90.14 ± 0.01 | 243 (1.35$\\times$) | 89.92 ±0.05 | 140 (1.74$\\times$) |\n| DELTA | 90.38  ± 0.02 | 214 (1.54$\\times$) | 90.58 ±0.07 | 109 (2.24) |\n\nAnalogous to [1], our analysis seamlessly extends to FedAdagrad and FedAdam. The divergence between these algorithms and SGD originates from the learning rate adaptation, which doesn't alter the convergence analysis steps.\n\nSpecifically, the difference in analysis arises with $x_{t+1}=x_t+\\eta \\frac{\\Delta_t}{\\sqrt{v_t}+\\tau}$ replacing $x_{t+1}=x_t+\\eta \\Delta_t$, where $v_t=\\beta v_{t-1}+\\left(1-\\beta\\right) \\Delta_t^2$. As demonstrated in Corollary 1 and Corollary 2 of [1], following the very similar steps of vanilla SGD, Adam's convergence rate order is the same as that of SGD.\n\n[1] Adaptive federated optimization. ICLR 2021."}, {"review_id": "3NMHOPGjko", "reviewer": "Reviewer_stNZ", "summary": "This paper proposes a client sampling scheme in federated learning for faster convergence. The authors argue that the previous client sampling method based on importance sampling ignores gradient diversity. Convergence analysis is provided, as well as experiments on four image datasets. ", "questions": "See weakness.", "limitations": "The authors didn't really discuss limitation, even though it has a limitation session. ", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "The problem of client selection in federated learning is interesting and worth investigating. ", "weaknesses": "[1] The paper overall is not well-written. Both organization and writing could be improved. There are multiple grammar errors even in the Introduction. \n\n[2] Both theoretical and main method seems to rely on gradient information. However, gradient information is usually unavailable in a federated learning setting. It is unclear to me what's the contribution of this paper either theoretically or practically. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer stNZ, thanks for your time in reviewing our paper, please find our responses to your raised questions:\n\n> Both theoretical and main method seems to rely on gradient information. However, gradient information is usually unavailable in a federated learning setting. It is unclear to me what's the contribution of this paper either theoretically or practically.\n> \n\nWe have carefully checked our writing according to your suggestions. \n\n**Regarding gradient information in FL:**\n\n- This paper’s gradient information is the same as the model difference, differing only by a learning rate $\\eta_L$ multiplier $\\Delta_t^i=x_{t,K}^i-x_{t,0}^i=-\\eta_L\\sum_{k=0}^{K-1} g_{t,k}^i$. Our implementation aligns with the majority of works in FL community, which necessitate user-provided gradients (or model difference), such as [1,2,3,4,5,6,7,8].\n- Gradient privacy protection stands as a distinct research direction from the sampling algorithm studied in this paper. Furthermore, privacy protection techniques like secret sharing and encryption protocols [9] are orthogonal to our sampling algorithm and can be directly employed for information preservation.\n\n**Clarify our contribution:**\n\nPlease see “Reply to All reviewers”, in which we clarify our contribution item by item.\n\n[1]Communication-efficient learning of deep networks from decentralized data. AIS 2017\n\n[2]Tackling the objective inconsistency problem in heterogeneous federated optimization. NIPS 2020\n\n[3]Federated learning under importance sampling. IEEE Transactions on Signal Processing 2022\n\n[4]Can 5th Generation Local Training Methods Support Client Sampling? Yes! ICAIS 2023\n\n[5]Optimal client sampling for federated learning. TMLR 2022\n\n[6Fast heterogeneous federated learning with hybrid client selection. UAI, 2023\n\n[7]Federated optimization in heterogeneous networks. MLS 2020\n\n[8]Scaffold: Stochastic controlled averaging for federated learning. ICML 2020\n\n[9]A privacy preserving federated learning scheme using homomorphic encryption and secret sharing. Telecommunication Systems, 2023"}, {"review_id": "EBnoCcBmax", "reviewer": "Reviewer_yPdX", "summary": "The authors introduce DELTA (Diverse Client Sampling) which is an unbiased method for client selection in Federated Learning (FL). DELTA is  heavily inspired by Importance Sampling (IS) and cluster-based IS, resulting in sampling diverse clients with significant gradients however without the clustering. They provide convergence rate analysis of FL under IS scheme (FedIS) and then of FL under their DELTA scheme (FedDELTA) and closed form expressions for the sampling probabilities are given and discussed. Practical versions of those algorithms FedPracIS and FedPracDELTA are also analyzed. In the experiments loss profiles, accuracies and timings of proposed algorithms against baselines (including FedAvg, Power-of-Choice and cluster-based IS) and over a collection of real and synthetic datasets are presented and discussed, exhibiting the empirical advantages of the sampling scheme.\n", "questions": "- In the experiments, there seems to be a variety of thresholds (70%, 54%, 85%, 80%) for different experiments and metrics in Tables 2 and 3. I would expect a more uniform way of presentation, some common threshold.\n\n- On a related topic: Since for Table 2, 500 communication rounds were completed for all (dataset, algorithm) pairs why mean of maximum five accuracies? Are all these maximum values observed within the last x% of rounds? How do these accuracy profiles evolve? Have they saturated after 500 rounds or there is still room for improvements? I mean some short comment summarizing the full profile plots (similar to Figures 12a and 12b in the appendix) would be more than sufficient.\n\n- How do you implement a sampling strategy like that of Equation (16) for FedPracDELTA in the experiments. There are parameters like alpha's, sigma's and zeta's in those: it would be great to include or refer to brief hints on how you choose values for those for conducting the empirical evaluation.\n", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- Comprehensive and nicely structured, easy to follow presentation, with a good balance of theoretical, practical and intuitive/explanatory information.\n\n- Rich empirical results also communicating the benefits of proposed, analyzed sampling approaches.\n\n- Simplicity of resulting FL algorithm: Basically the well-known, seminal FedAvg idea/template with a novel client sampling scheme (DELTA, PracticalDELTA) on top (Algorithm 1).   \n", "weaknesses": "- Minor: \"developing an efficient and effective practical algorithm for gradient-based sampling methods\" in future work section (Section 6) could confuse the reader (since DELTA is exactly such an algorithm). Perhaps  a different wording, emphasizing room of improving over this new/existing development?\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer yPdX, thank you very much for your appreciation of our work. Please find our responses to your raised questions below:\n\n> Minor: \"developing an efficient and effective practical algorithm for gradient-based sampling methods\" in future work section (Section 6) could confuse the reader (since DELTA is exactly such an algorithm). Perhaps a different wording, emphasizing room of improving over this new/existing development?\n> \n\nThanks for your suggestion, we would like to use the statement “further improve the efficiency of the existing gradient-based sampling methods” to enhance clarity.\n\n> In the experiments, there seems to be a variety of thresholds (70%, 54%, 85%, 80%) for different experiments and metrics in Tables 2 and 3. I would expect a more uniform way of presentation, some common threshold.\n> \n\nThanks for your suggestion, we are willing to provide results under some common thresholds in the below table, including 50% for CIFAR-10 and 80% for CelebA, to replace 54% for CIFAR-10 and 85% for CelebA.\n\nIn addition, we would like to clarify that we use these thresholds (like 54%) in our paper because they are the best integer accuracies that FedAvg can achieve in our experiments. \n\n|  | CIFAR-10 |  | CelebA |  |\n| --- | --- | --- | --- | --- |\n|  Algorithm | Accuracy (%) |  Communication Rounds for 50%  | Accuracy (%)  | Communication Rounds for 80%  |\n| FedAvg | 54.28±0.29 | 181 (1.0$\\times$) | 85.92±0.89 | 339 (1.0$\\times$) |\n| Cluster-based IS | 54.83±0.02  | 187 (0.91$\\times$) | 86.77±0.11 | 303 (1.11$\\times$) |\n| FedIS | 55.05±0.27 | 168 (1.07$\\times$) | 88.12±0.71 | 261 (1.29$\\times$) |\n| DELTA  | 55.20 ±0.26 |  151 (1.20$\\times$) | 89.67 ±0.56 | 257 (1.32$\\times$) |\n\n> On a related topic: Since for Table 2, 500 communication rounds were completed for all (dataset, algorithm) pairs why mean of maximum five accuracies? Are all these maximum values observed within the last x% of rounds? How do these accuracy profiles evolve? Have they saturated after 500 rounds or there is still room for improvements? I mean some short comment summarizing the full profile plots (similar to Figures 12a and 12b in the appendix) would be more than sufficient.\n> \nWe appreciate your suggestion. We would like to include comments about Table 2 in the experiment section as follows:\n\nThe maximum values reported in Table 2 are observed during the last 4% of rounds, where these algorithms have already reached convergence. The term 'maximum five accuracies' refers to the mean of the five highest accuracy values obtained within the plateau region of the accuracy curve. By computing the average of these values, we aim to minimize error and variance.\n\n> How do you implement a sampling strategy like that of Equation (16) for FedPracDELTA in the experiments. There are parameters like alpha's, sigma's and zeta's in those: it would be great to include or refer to brief hints on how you choose values for those for conducting the empirical evaluation.\n> \n\nThank you for your constructive suggestion. We would like to clarify the implementation of sampling algorithms:\n\nWe introduce the setting of parameters in Appendix H.2 in the submission. Specifically, for $\\alpha$, the default value is 0.5, whereas $\\sigma$ and $\\zeta$ are not hyperparameters but rather can be implemented by computing the locally obtained gradients, as elaborated in L262, L263, and eq(16).\n\nWe are willing to include brief hints on how to set these hyperparameters in the main paper of our revised version."}, {"review_id": "TGZY7eM0hJ", "reviewer": "Reviewer_9Bi1", "summary": "The paper proposed an unbiased client sampling method in Federated Learning. The proposed method is motivated by considering both variance and gradient diversity when doing client sampling. The authors theoretically proved that the proposed sampling method can achieve better convergence rate for non-convex objective functions. Besides, the authors also demonstrated its practical advantages by numerical experiments.", "questions": "1.\tMay the authors discuss what will happen if Assumption 4 does not hold?\n2.\tHow large is U used in the theory of practical IS and practical DELTA?\n3.\tMay the authors discuss what is the key intuition of theoretical advantage of the new IS analysis? In my understanding, the importance sampling can only improve the constants rather than the convergence order. Thus, I find the theoretical result quite surprising. Unfortunately, I do not have enough time to check the correction of the theory.", "limitations": "The authors mentioned that their proposed method does not address the backdoor attack concern.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "Considering gradient diversity is a novel idea in FL client sampling research. The paper demonstrates its proposed method by both theory and experiments. The motivation is clear, and the paper is in general good writing. Given that client sampling is an important problem of federated learning and the claimed advantage of the proposed method, the paper can have significant impact on the area.", "weaknesses": "Assumption 4 is a very strong assumption. It can be violated in many problems. For example, the simple least square regression problem can violate this assumption.\n\nBesides, the paper seems to have too much content for a nine-page paper. As a result, the key theoretical result is lack of intuition.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer 9Bi1, thank you for providing constructive feedback. We have fully revised our manuscript and have addressed all of the comments, as well as added new experiments to further strengthen our work. Please find our responses to your raised questions below:\n\n> Assumption 4 is a very strong assumption. It can be violated in many problems. For example, the simple least square regression problem can violate this assumption.\n> \n\nThank you for your suggestion. We would like to explain the soundness of Assumption 4:\n\n- This assumption is essential for IS methods [1,2,3]. Furthermore, it finds common usage in the FL community for convergence analysis [4,5,6,7].\nIn particular, according to the definition of IS, $E_{q(x)}[h(x)]=E_{p(x)}\\left[\\frac{q(x)}{p(x)} h(x)\\right]$, where $q(x)$ is the given sampling distribution, $p(x)$  is our proposed sampling distribution and $h(x)$  is the value function. With a little work (similar to our Corollary F.1), one can prove the variance is minimized when $p^*(x) \\propto q(x)\\|h(x)\\|$. If $\\|h(x)\\|$ is not consistently bounded, $p(x)$ is meaningless.\n- We would like to clarify that in our practical algorithm of DELTA, the used assumption is gradient heterogeneity bound: $E|| \\nabla F_i(x_t)-\\nabla f(x_t)||^2 \\leq G^2$ instead of Assumption 4, as used in eq (89) of the convergence analysis of the practical algorithm. This is a looser assumption than Assumption 4.\n- Figure 1 in the one-page response PDF demonstrates the gradient norm of FedIS on MNIST and FashionMNIST datasets, suggesting gradient can be bounded.\n\nFor the least square regression problem, the gradient becomes unbounded only if the model parameters are at infinity in the parameter space. In other words, when the model parameters are normally distributed in the parameter space, the gradient is always finite-large and therefore bounded.\n\n> May the authors discuss what will happen if Assumption 4 does not hold?\n> \n\nWe would like to clarify the consequence/meaning of Assumption 4 not holding and explain it :\n\n- If Assumption 4 doesn’t hold:\n    1. All IS-type methods become inapplicable in FL, given that this assumption forms an inherent prerequisite for utilizing IS to attribute meaning to the expression $p^*(x)\\propto ||\\nabla F_i(x)||$.\n    2. FL algorithms may falter in training since a lack of gradient bounding implies that gradients can assume \"nan\" values, thereby disrupting the deep learning training process.\n    3. For the practical FedIS algorithm, employing the user's last round participation gradient to approximate the current gradient will introduce an unbounded, significant noise.\n- Figure 1 in the one-page response PDF showcases the gradient norm of FedIS on MNIST and FashionMNIST datasets, indicating that the gradient can be bounded, as its norm remains below 8.\n\n> How large is U used in the theory of practical IS and practical DELTA?\n> \n\nWe would like to clarify $U$ in practical IS and $\\tilde{U}$ in practical DELTA possess limited magnitudes. We also provide the experimental results to illustrate it.\n\n- Intuitively, $U=||\\nabla F_i(x_{t,k},\\xi_{t,k}) / \\nabla F_i(x_{s,k},\\xi_{s,k})||$ (same to $\\tilde{U}$) tends to be smaller than 1 since the gradient tends to be zero as training processing, where index $t$ represent the current communication round and $s$ represent the last participated round of client $i$. The discussion of $U$ is provided in Remark G.1, Appendix G.\n- Figures 1 and 2 in the one-page response PDF depict the norms of gradients and gradient diversity across all clients in each round. Notably, these figures demonstrate that in the case of practical IS and practical DELTA, the change ratio of both gradient and gradient diversity remains limited, with the maximum norm being under 8 and the minimum norm exceeding 0.5.\n\n> May the authors discuss what is the key intuition of theoretical advantage of the new IS analysis?\n> \n\nThank you for your comment. We are willing to share with you the intuition of our theoretical advantage of IS analysis. \n\nFirst, we clarify that the rate improvement comes from our improved analysis of unbiased sampling in federated learning, including FedAvg. IS then reduces variance.\n\n***Intuition:***\n\n- The intuition of unbiased sampling FL: Though the existing analysis for partial user participation in FL (including FedAvg) can be extended to unbiased sampling scenarios, *the failure to leverage the unbiased property leads to imprecise upper bounds on convergence for unbiased sampling FL [1,2,3].*\n- The intuition of FedIS: Following the unbiased sampling FL analysis, we optimize the convergence variance with respect to sampling probability.\n\nFor details explanation and evidence, please see “Reply to All Reviewers, Elaborate on the novelty and contribution of our analysis below”.\n\n[1]Stochastic optimization with importance sampling for regularized loss minimization, ICML 2015\n\n[2]Not all samples are created equal: Deep learning with importance sampling. ICML 2018\n\n[3]Low-Cost Lipschitz-Independent Adaptive Importance Sampling of Stochastic Gradients. ICPR, 2021\n\n[4]Diverse client selection for federated learning: Submodularity and convergence analysis. ICML 2021\n\n[5]On the effectiveness of partial variance reduction in federated learning with heterogeneous data. CVPR. 2023\n\n[6]Sharper convergence guarantees for asynchronous sgd for distributed and federated learning. NIPS, 2022\n\n[7]Optimal client sampling for federated learning. TMLR, 2022."}]

Author rebuttal:
We thank all the reviewers for their time and efforts in reviewing our paper. 
We are encouraged they found our motivation and idea to be interesting(stNZ, yPdX), novel (1Yft, yPdX, 9Bi1), and promising (1Yft, yPdX).  We have carefully considered their suggestions and incorporated them into our revised manuscript.

For convenience, we have prepared a one-page response PDF, containing two Figures and three Tables of ***new experiments***.

1. Figure 1 and 2 show the norm of gradient and gradient diversity on MNIST and FashionMNIST. 
2. Table 1 and 2 are the results of sampling algorithms integrated with the non-vanilla SGD algorithms (Adagrad and Adam) on FEMNIST and CelebA. 
3. Table 3 shows the results of sampling algorithms under common thresholds, i.e., 50% accuracy for CIFAR-10 and 80% accuracy for CelebA. 

Our ***contributions*** are concluded as follows：

1. We are the first to propose DELTA, the diverse gradient-based unbiased sampling for FL.  Our analysis shows  DELTA surpasses the SOTA FedAvg in convergence rate by eliminating $\mathcal{O}\left(1 / T^{2 / 3}\right)$ term and a $\sigma_G^2$-related term of $\mathcal{O}\left(1 / T^{1 / 2}\right)$. 
2. Our nonconvex FL convergence analysis with IS outperforms existing FedIS analysis, employing a more lenient assumption. Notably, we eliminate the $\mathcal{O}\left(1 / T^{2 / 3}\right)$ term from the convergence rate compared to existing unbiased sampling analysis, including FedIS and FedAvg.
3. We present a practical DELTA algorithm to mitigate the reliance on full gradients, along with a theoretical convergence guarantee.
4. Extensive experiments across datasets confirm DELTA's superiority over existing FL unbiased sampling methods and its compatibility with other optimization algorithms.

### ***Elaborate on the novelty and contribution of our analysis below:***

1. Regarding FedIS analysis, 
    1. **Existing challenges:** Despite the existence of existing convergence analysis of partial participant FL [1,2,3], including FedIS that builds on this analysis [4, 5], none of them take full advantage of the nature of unbiased sampling, and thus yield an imprecise upper bound on convergence. 
    2. **Our solution:**  To tighten the FedIS upper bound, we first derive a tighter convergence upper bound for unbiased sampling FL. By adopting uniform sampling for unbiased probability, we achieve a tighter FedAvg convergence rate. Leveraging this derived bound, we optimize convergence variance using IS. 
    
    *Compare with existing unbiased sampling FL works, including FedAvg and FedIS (others), our analysis on FedIS entails:*
    
    - **A tighter Local Update Bound Lemma:** We establish Lemma C.3 using Assumption 3, diverging from the stronger assumption $||\nabla F_i(x_t))-\nabla f(x_t)||^2 \leq \sigma_G^2$ (used in [1,2]), and the derived Lemma C.3 achieves a tighter upper bound than other works (Lemma 4 in [1], Lemma 2 in [2]).
    - **A tighter upper bound on aggregated model updates $E||\Delta_t||^2$:** By fully utilizing the nature of unbiased sampling, we convert the bound analysis of $A_2=E||\Delta_t||^2$ equally to a bound analysis of participant variance $V\left(\frac{1}{m p_i^t} \hat{g}_i^t\right)$ and aggregated model update with full user participation (Eq. (33) and Eq. (34)). In contrast, instead of exploring the property the unbiased sampling,  [1] repeats to use Lemma 4 and [2] uses Lemma 2 for bound $A_2$. This inequality transform imposes a loose upper bound for $A_2$,  resulting in a convergence variance term determined by $\eta_L^3$, which reacts to the rate order being $\mathcal{O}(T^{-\frac{ 2}{3}})$.
    - **Relying on a more lenient assumption:** Beyond the aforementioned analytical improvement, our IS analysis obviates the necessity for unusual assumptions in other FedIS analysis such as Mix Participation [3] and $\rho$-Assumption [4].
2. Regarding DELTA analysis, 
    1. **Existing challenge:** IS focuses on minimizing $V\left(\frac{1}{m p_i^t} \hat{g}_i^t\right)$ in convergence variance $\Phi$ (Eq. (4)), while leaving other terms like $\sigma_L$ and $\sigma_G$ unreduced. 
    2. **Our solution:** Unlike IS roles to reduce the update gap [5], we propose analyzing the surrogate objective for additional variance reduction.
    
    *Compared with FedIS, our analysis of DELTA entails:*
    
    - **Focusing on surrogate objective, introducing a novel Lemma and bound:**
        1. We decompose global objective convergence into surrogate objective and update gap (Eq. (6)). For surrogate objective analysis, we novelly introduce Lemma E.8 to bound local updates. 
        2. Leveraging the unique surrogate objective expression and Lemma E.8, we link sampling probability with local variance and gradient diversity, deriving novel upper bounds for $A_1$ and $A_2$ (Eq. (57), Eq. (59)). 
        3. By connecting update gap's convergence behavior to surrogate objective through Definition E.1 and Lemma C.2, along with (Eq. 6), we establish $\tilde{\Phi}$ (Eq. (10),(11))) as the new global objective convergence variance.
    - **Optimizing convergence variance through novel $\tilde{\Phi}$:**
    FedIS aims to reduce the update variance term $V(\frac{1}{(mp_i^t)}\hat{g}_i^t)$ in $\Phi$, while FedDELTA aims to minimize the entire convergence variance $\tilde{\Phi}$, which is composed of both gradient diversity and local variance. By minimizing $\tilde{\Phi}$, we get the sampling method DELTA, which further reduces the variance terms of $\Phi$ that cannot be minimized through IS.

[1]Adaptive federated optimization. ICLR 2021.

[2]Achieving linear speedup with partial worker participation in non-iid federated learning. ICLR 2021.

[3]Scaffold: Stochastic controlled averaging for federated learning. ICML, 2020.

[4]Tackling system and statistical heterogeneity for federated learning with adaptive client sampling. IEEE INFOCOM 2022.

[5]Optimal client sampling for federated learning. TMLR, 2022.

Meta-review: The paper introduces a new unbiased client sampling technique for Federated Learning (FL) called DELTA. Motivated by the need to consider both variance and gradient diversity, the authors propose this method as a means to achieve improved convergence rates for non-convex objective functions in FL. To support their proposal, they offer theoretical proofs and evidence from numerical experiments. The paper aims to show that by considering gradient diversity in client sampling, a significant impact can be made on federated learning, addressing a crucial challenge in client sampling.

The authors have adequately addressed concerns from reviews, resulting in reviewers increasing their scores. At this point, I believe that any remaining minor issues can be addressed in the final camera ready version of the paper.
Decision: Accept (poster)