On the Efficacy of Server-Aided Federated Learning against Partial Client Participation
Authors: Haibo Yang
Peiwen Qiu
Prashant Khanduri
Jia Liu
Venue: Submitted to ICLR 2023 (2023)

Abstract: Although federated learning (FL) has become a prevailing distributed learning framework in recent years due to its benefits in scalability/privacy, there remain many significant challenges in FL system design. Notably, most existing works in the current FL literature assume either full client or uniformly distributed client participation. Unfortunately, this idealistic assumption rarely hold in practice. It has been frequently observed that some clients may never participate in FL training (aka partial/incomplete participation) due to a meld of system heterogeneity factors. To mitigate impacts of partial client participation, an increasingly popular approach in practical FL systems is the sever-aided federated learning (SA-FL) framework, where one equips the server with an auxiliary dataset. However, despite the fact that SA-FL has been empirically shown to be effective in addressing the partial client participation problem, there remains a lack of theoretical understanding for SA-FL. Worse yet, even the ramifications of partial worker participation is not clearly understood in conventional FL so far. These theoretical gaps motivate us to rigorously investigate SA-FL. To this end, we first reveal that conventional FL is {\em not} PAC-learnable under partial participation in the worst case, which advances our understanding of conventional FL. Then, we show that the PAC-learnability of FL with partial client participation can indeed be revived by SA-FL, which theoretically justifies the use of SA-FL for the first time. Lastly, to further make SA-FL communication-efficient, we propose the \alg (\ul{s}erver-\ul{a}ided \ul{f}ederated \ul{a}ve\ul{r}ag\ul{i}ng) algorithm that enjoys convergence guarantee and the same level of communication efficiency and privacy as state-of-the-art FL.

Under review as a conference paper at ICLR 2023
ON THE EFFICACY OF SERVER-AIDED FEDERATED LEARNING AGAINST PARTIAL CLIENT PARTICIPATION
Anonymous authors Paper under double-blind review
ABSTRACT
Although federated learning (FL) has become a prevailing distributed learning framework in recent years due to its benefits in scalability/privacy there remain many significant challenges FL system design. Notably, most existing works the current FL literature assume either full client or uniformly distributed client participation. Unfortunately, this idealistic assumption rarely holds in practice. It has been frequently observed that some clients may never participate in FL training (aka partial/incoppete participation) due to a meld of system heterogeneity factors. To mitigate impacts of partial client participation, in practical FL systems is the sever-aided federated learning (SA-FL) framework, where one equips the server with auxiliary dataset. However, despite the fact that SA-FL has been empirically shown to effective in addressing the partial client participation problem, there remains lack of theoretical understanding for SA-FL. Worse yet, even the ramifications of partial worker participation are not clearly understood conventional FL far. These theoretical gaps motivate us rigorously investigate SA-FL. To this end. we first reveal that conventional FL is not PAC-learnable under partial client participation in the worst case, which advances our understanding of conventional FL. Then, we show that the PAC-learnabiliity of FL with partial client participation can indeed be revived by SA-FL, which theoretically justifies the use of SA-FL for the first time. Lastly, to further make we propose the SAFARI (server-aided federated averaging) algorithm that enjoys convergence guarantees and the same level of communicattio efficiency and privacy as the state-of oft-th--rtttttt- FL.
increasingly popular approach
SA-FL communication--fficieee
INTRODUCTION
Since the seminal work by McMahan et al.] (2017). federated learning (FL) has emerged as powerful distributed learning paradigm that enables a large number of clients (e.g., edge devices) to collaboratively train a model under a central server's coordination. However, with FL gaining popularity, it has also become apparent that FL faces key challenge that is unseen in traditional distributed learning in datacenter settings system heterogeneiry. Generally speaking, system heterogeneity in Fl. is caused by the massively different computation and communication capabilities at each client (computational power, communication capacity, drop-out rate, etc.). Studies have shown that system heterogeneity can significantly impact client participation highly non-trivial fashion and severely degrade the learning performance of FL algorithms (Bonawitz et al. 20119] Yang al. 2021a). For example, is shown in (Yang al. 2021a) that more than 30% clients never participate in FL, while only 30% of the clients contribute to 81% of the total computation even if the server uniformly samples the clients. Exacerbating the problem is the fact that the client's 's status could be unstable and time-varying due to the aforementioned computation and communication constraints.
To mitigate the impact of partial client participation, one approach called server-aided federated learn- ing (SA-FL) has been increasingly adopted in practical FL systems in recent years (see, e.g., (Zhao) cet al. 2018 Wang et al., (021b)). The basic idea of SA-FL is to equip the server in FL with small auxiliary dataset that approximately mimics the population distribution, so that the distribution deviation induced by partial client participation can be corrected. To date, even though SA-FL has been empirically shown to be quite effective in addressing the partial client participation problem in practice, there remains a lack of theoretical understanding for SA-FL. This motivates us to rigorously investigate the efficacy of SA-FL against partial client participation in FL. in this paper.

---

Under review as a conference paper at ICLR 2023
Somewhat counterintuitively, to fully understand SA-FL, one must be able to first see what happens SA-FL is not used and partial client participation is left untreated in conventional FL. In other words, we need to first answer the following fundamental question: "1) What are the impacts of partial client participation on FI. learning performance?" Upon answering this question, the next important follow-up question regarding SA-FL. is: "2) What benefits could SA-FI. bring and how could we theoretically characterize them? Also, since SA-FL still largely follows the server-client architecture that demands intensive communication between server and clients, the third fundamental question regarding SA-FL is: "3) Could we make SA-FL as commuicationn-ffen FL?" Indeed, answering these three questions constitutes the rest of this paper, where we address the first two questions through the lens of PAC (probably approximately correct) learnability, while resolving the third question by proposing a communication-efiee contributions in this work are summarized as follows:
as conventional
SA-FL, algorithm. Our major
By establishing a worst-case generalization error lower bound, we show that conventional FL is not PAC-learnable under partial client participation. In other words, no learning algorithm can approach zero generalization error under partial participation for conventional FL even in the limit of infinitely many data samples and training iterations. This insight, though being negative, warrants the necessity of developing new algorithmic techniques and system architectures (e.g.. SA-FL) to modify the conventional FL. framework to mitigate partial client participation.
Inspired by techniques from domain adaptation, we prove a new generalization error bound to show that SA-FL. can indeed revive the PAC learnahility of FL. under partial client participation. We note that this bound could reach zero asymptotically as the number data samples increase. This is much stronger than previous results in domain adaptation with non-vanishing small error (see Section 2 for details).
To make SA-FL communication--ffiiinn we propose a new training algorithm for SA-FL called SAFARI (server-aided federated averaging). By carefully designing the update coordination between the server and the clients, we show that SAFARI achieves an ( (I/VKKR) convergence rate, matching the convergence rate of state-of- offtthe-rtt conventional FL algorithms. We also conduct extensive experiments to demonstrate the efficacy and efficiency of our SAFARI algorithm.
The rest of this paper is organized follows. In Section 2 we review the literature to put our work in comparative perspectives. Section 3 presents the PAC learning analysis of standard FL under partial participation and our proposed SA-FL framework. We then propose SAFARI algorithm with convergence guarantees in Section
2 RELATED WORK
1) Client Participation in Federated Learning: The seminal FedAvg algorithm was first proposed
in (McMahan al., 2017) as a heuristic to improve communication efficiency and data privacy for FL.
Since then, there have been many follow-ups (e.g.. (Li et al.
2020a Wang et al. 2020 Zhang et al.
2020
Acar et al., | Karimireddy al. 2020 Luo et al.
2021 Mitra et al. 2202: Karimireddy
ct al.
2021 |021] Khanduri et al. [022]] Murata & Suzuki [021 Avdiukhin & Kasiviswanathan 2021) and
80 on) addressing the data heterogeneity challenge in FL. However, most of these works (e.g.. LLi
let al.
2020a| Wang et al. 2020 /hhan et al., 2020) Acar et al.) [202]] Karimireddy et al. 2020 Yang al.
2021bb) are based on the full or uniform (i.e., sampling clients uniformly at random) client participation assumption. The full or uniform participation assumptions are essential since they are required ensure that the stochastic gradient estimator unbiased in each round of update. Thus, even if "model drift" or "objective inconsistency" emerges due to local updates (Karimiredyy et al., 2020, Wang et al. 2020), the full/uniform client participation in each communication round averages them out in the long run, therefore, guaranteeing convergence.
related interesting line of works in FL different from full/uniform client participation focuses on proactively creating flexible client participation (see, e.g., (Xie et al. 2019 Ruan et al. 2021
Gu et al., 2021 Avdiukhin & Kasiviswanathan 2021: Yang et al.) 2022 Wang & Ji 2022 ) The main idea here is to allow asynchronous communication or fixed participation pattern (e.g., given probability) for clients to flexibly participate in training. Existing works in this area often require extra assumptions, such bounded delay (Ruan et al.) 2021 Gu et al.) 2021 Yang al. [022 Avdiukhin & Kasiviswanathan 202T) and identical computation rate (Avdiukhin & Kasiviswanathan (021).
Under these assumptions, although the stochastic gradients are longer unbiased estimators of the
2

---

Under review as a conference paper at ICLR 2023
full gradients, the deviation in each communication round remains bounded. For sufficiently many communication rounds, the impact of such deviation from full gradients vanishes asymptotically, since each client can still participate in FL in the long run. In contrast, this paper considers a more practical (or worst-case) scenario in FL. - partial client participation even in the long run, which can be caused by many real-world system heterogeneity factors as mentioned in Section --
2) Domain Adaptation: Since partial client participation induces a gap between the dataset distribu- tion used for FL training and the true data population distribution across all clients, our work is also related to the field of domain adaptation in learning. Domain adaptation focuses on the learnability of model trained in one source domain but applied to different and related target domain. The basic approach is to quantify the eπror in terms of the source domain plus the distance between source and target domains. Specifically, let P and Q be the target and source distributions, respectively. Then, the generalization error is expressed as ((((n)) + dist( P. Q), where A(nq) is an upper bound of the error dependent on the total number of samples in Q. Widely-used distance measures include da-divergence Devid et al. 2010 David et al. 2010) and J'-discrepancy (Mansour et al. 2009)] Mohri & Medinal 2012). We note, however, that results in domain adaptation cannot be directly applied in FL with partial client participation, since doing so yields overly pessimistic bound. Specifically, the error based on domain adaptation remains non zero for asymptotically small distance (P, Q) between P and Q even with infinite many samples in ni (i.e., A(no) - 0). In this paper, rather than directly using results from domain adaptation, we establish a much sharper upper bound (see Section 3). Another line of work in domain adaptation is using importance weights defined by the density ratios between P and Q2 to correct the bias and reduce the discrepancy (Sugiyama et al. 2007a b Cortes al. 2008). However, due FL privacy constraints, such density ratios are dillicult to estimate, which renders importance- importance-weights- -ased methods infeasible in FL. A closely related work is (Hanneke & Kpotufe| 2019), which proposed new notion of discrepancy between source and target distributions called transfer exponents. However, this work considers non-overlapping support between P and Q, while we focus on overlapping support (see Fig. in Section 3.3)
PAC-LEARNABILITY OF CONVENTIONAL FEDERATED LEARNING WITH PARTIAL CLIENT PARTICIPATION
In this section, we first focus on understanding the impacts of partial client participation on con- ventional FL in terms of PAC-learnaillity in Section 3.2 This will also pave the way for studying SA-FL later in Section 3.3 In what follows, we start with the conventional FL formulation and some definitions in statistical learning that are necessary to formulate and prove our main results.
3.1 PRELIMINARIES
The goal of FL is to minimize the following loss function F(x) (x-p(Fi(x)), where Fx(x) & Ee ~P; (f(x, {)] Here, P represents the distribution of the entire client population, x E Idd is the model parameter, (x) represents the local loss function at client and P. is the underlying distribution of the local dataset at client i. In general, P. + P,, if # j due to data heterogeneity. However, the loss function F(x) full gradient V Fx) can not be directly computed as the exact distribution of data is unknown in general. Instead, one often considers the following empirical risk minimization (ERM) problem in the form of finite-sum:
min F(x) XER"
Σ Caf((x). (E[M]
where Fx(x) A (1/1S,1) Eces, (), Here, M is the total number of clients, S; is the local dataset with cardinality [Ss), which is i.i.d. and sampled from distribution P., o; = |.S:/(E |S))) (hence Σie(M Og 1). For ease of presentation, consider the balanced dataset case: Oq 1/M, Vi E [M]. Next, we state several definitions from statistical learning theory Mohri et al. 2018).
Definition 1 (Generalization Error and Empirical Error). Given a hypothesis h E H. a target concept f. underlying distribution D and dataset S i.i.d. sampled from D (S D), the generalization error and empirical error of h are defined as follows: Ro(h, f) = (he,)) fxx) and RD f)= 1// -/55Dn ExesU(h(z) f2:)),, where 1(-) is some valid loss function.
3

---

Under review as a conference paper at ICLR 2023
With slight abuse of notation, we omit f by using (D) and (D) for simplicity.
Definition 2 (Optimal Hypothesis). For a distribution 'D and a dataset S ~ DD we define hip =
argminRD(h) and hn argminRD(h)). NCH
kCH
Definition 3 (Excess Error). For hypothesis h and distribution D, the excess error and excess empiri- cal enror are defined as Ep(h) = (R - -Rp(hp)) and ( (Ro()) respectively,
3.2 CONVENTIONAL FEDERATED LEARNING UNDER PARTIAL CLIENT PARTICIPATION
With the above notations, we consider conventional FL under partial client participation. Consider an FL system with M clients in total. We let / denote the underlying joint distribution of the entire system, which can be decomposed into the summation of the local distributions at each client, i.e., P P= EiE X,P,, where X; > 0 and EiE[M] A; 1. We assume that each client i has training samples i.i.d. drawn from P., i.e., | n, Vi E [M]. Then, = (< V:), E [M n]) can be viewed as the dataset i.i.d. sampled from the joint distribution P. We consider a partial client participation setting, where m E [0, .M) clients participate in the FL training as result of some client sampling process F. We let F(S) represent the data ensemble actually used in training and D denote the underlying distribution corresponding to F(S). For convenience, we define the notion a = n7 as the FL system capacity (i.e.. only m clients participate in the training). For FL with partial client participation, we establish the following fundamental performance limit of any learner in general. For simplicity, we binary classification with zero-one loss here. We state the following impossibility result in Theorem in terms of PAC learnability:
m
Theorem 1 (Impossibility Theorem). Let H. be a non-trivial hypothesis space and C () (m)x)) - H be the learner for FL system. There exists client participation pro- cess F, distribution P. and target function f E H with minsCH Rp(h, f) = O, such that PSMP (RP(C(F(S),))) > 1- 1
20'
Sketch. The proof is based on the method of induced distributions in (Bshouty et al. 2002 Mohri et al. 2018 Konstantinov et al. 2020). We first show that the learnability of an FL system is equivalent to that of a system that arbitrarily selects mn out of Mn samples in the centralized learning. Then, for any learning algorithm, there exists a distribution P such that dataset F(S) resulting from partial participation and seen by the algorithm is always distributed identically for any target functions. Thus, no algorithm can learn better predictor than random guessing. Due to space limitation, we relegate the full proof to supplementary material.
Given the system capacity E (0, 1), the above theorem characterizes the worst-case scenario for FL with partial client participation. It says that for any learner (i.e., algorithm) L, there exists a bad client participation process F and distributions P. i E [M] over target function f, for which the error of the hypotheses returned by L is constant with non-zero probability. In other words, FL with partial client participation is not PAC-learnable. One interesting observation here is that the lower bound independent of the number of samples per client n. This indicates that even each client has infinitely many samples (n - 0o), it is impossible to have zero- zero- generation error learner under the partial client participation (a E (0, 1)). Note that this fundamental result relies on two conditions: heterogeneous dataset and arbitrary client participation. Under these two conditions, there exists a worst-case scenario where the underlying distribution 'D of the participating data Sp = F(S) deviates from the ground-truth P. thus yielding non-vanishing error. This result also sheds light on how to motivate client participation in FL effectively and efficiently; the participating client's 's data should be comprehensive enough to model the complexity of the joint distribution P to close the gap between D and P. Note that this result is not contradictory to previous works where the convergence of FedAvg is guaranteed, since this theorem is not applicable for homogeneous (i.i.d)) datasets or uniformly random client participation. As mentioned earlier, most of the existing works rely on at least one of these two assumptions. However, none of these two assumptions hold for conventional FL with partial client participation in practice.
3.3 THE PAC-LEARNABILITY OF SERVER-AIDED FEDERATED LEARNING (SA-FL)
The intuition of SA-FL is to utilize a dataset T i.i.d. sampled from distribution P with cardinality nr as vehicle correct potential distribution derivations due to partial client participation. By doing
4

---

Under review as a conference paper at ICLR 2023
so, the server steers the learning by small number of representative data, while the clients aid the learning by federation to leverage the huge amount of privately decentralized data (ng > nr). Note that the assumption of access to this dataset is not restrictive since such datasets are already available in many FL. systems: although not always necessary for training. an auxiliary dataset is often needed for defining FI. tasks (e.g., simulation prototyping) before training and model checking after training (e.g., quality evaluation and sanity checking) (McMahan et al., [021] Wang et al. 202 Also, obtaining an auxiliary dataset is affordable since the number of data points required is relatively small (of the order of hundreds, see our experimental results), and hence the cost is low. Then, SA-FL can be easily achieved or even with manually labelled data thanks its small size. It is also worth noting that many works use such auxiliary datasets in FL for security (Cao et al. 2021). incentive design (Wang et al. 2019), and knowledge distillation (Cho et al. 2021p.
For SA-FL, we consider the same partial client participation setting that induces a dataset Sp ~ 'D with cardinality ns and D * P. As a result, the learning process is to minimize Rp(h) by utilizing (X, )/, tns to learn hypothesis h E H. For notional clarity, we assume the joint dataset Sq = (Sp U T)- ~ Q with cardinality ny + ng for some distribution Q. Before deriving the generalization error bound for SA-FL, state the following assumption and definition.
Assumption 1 (Noise Condition). Suppose that hip and hi2 exist. There exist 3p, SQ E [0, [0.1] and
ap,00 > 0 such that the following hold: Pr-r((()) + hi(())) S arler(h))@r, (h)(()()) # (1)) S [c)=)(h)]
This assumption is a traditional noise model known as the Bernstein class condition, which has been widely used in the literature (Massart & Nédélec 2006 Koltchinskii 2006 Hanneke 2016).
Definition 4 ((,, (lr-33)) Positiielly-eeeatte
Distributions and Q are said to be (a. 33 posiitivvlll related if there exist constants a 2 and B 2 0 such that r Eq(h) S aleq(h)) wh E H.
Definition 4 specifies stronger constraint between distributions P and Q. It indicates that the difference of excess error for one hypothesis E H. between P and Q is bounded by the excess error of Q in some exponential form. With the above assumption and definition, we have the following generation error bound for SA-FL, which shows that SA-FL is PAC-learnable:
Theorem 2 (Generalization Error Bound for SA-FL), For an SA-FL system with arbitrary system and data heterogeneity, if distributions P and Q satisfy Assumption and are (a, -o-sosiiivellyeellee then with probability at least 1 - 8 for any 5 E (0, 1), it holds that
=p(h))== ((Tr
I-PG
dH
(1)
TTT
where du denotes the finite VC dimension for hypotheses class H. and parameters (P,Q, nr, us, B. (q) are defined the same before.
It is known that (see, e.g., (Hanneke 2016)) the generalization error bound of centralized learning is ((H))= (hiding logarithmic factors) with n samples in total and noise parameter 30. Note that when 3 2 1, the first term Eq. (I) dominates. Hence, Theorem 2inreemmimsssis implies that the generalization error bound for SA-FL matches that of centralized learning (with dataset size nr + ns). Mean- while, compared with solely training on server's dataset T, SA-FL exhibits an improvement from ((
"0 to Õ((
Note that SA-FL shares some similarity with the domain adaptation problem, where the learning is on Q but the results will be adapted to P. In what follows, we offer some deeper insights between the two by answering two key questions: 1) What the difference between SA-FI. and domain adaptation (a.k.a transfer learning)? and 2) Why is AA-FLfrom Q to P PAC-learnable, but FL D to P with partial client participation not PAC-learnable (as indicated in Theorem
To answer these questions, we illustrate the distribution relationships for domain adaptation and fed- erated learning, in Fig. D respectively. In domain adaptation, the target P and source Q distributions often have overlapping support but there also exists distinguishable difference. In contrast, the two distributions P and Q in SA-FL happen to share exactly the same support with different density, since Q is mixture of D and P. As result, the known bounds in domain adaptation (or transfer learning)
5

---

Under review as a conference paper at ICLR 2023
pessimistic in SA-FL. For example, the dist(P, Q) in dx-divergence and D'-divergence both have non-negligible gaps when applied to SA-FL. Here in Theorem [ we provide a generalization error bound in terms of the total sample size not + n. thus showing the benefit of SA-FL.
Moreover, for SA-FL, only the auxiliary dataset T Ltd. P is directly available for the server. The clients' datasets could be used in SA-FL training, but they are not directly accessible due to privacy constraints. Thus, previous methods in domain adaptation (e.g., impor- tance weights- based methods in covariate shift adapta- tion (Sugiyama et al. 2007a b)) are not applicable since they require the knowledge of density ratio between training and test datasets.
@
P
Domain Adaptation Federated Learning
The key difference between FL and SA-FL lies in rela- tions among D, P and Q. For FL., the distance between D and P under partial participation could be large due system and data heterogeneity in the worst-case. More specifically, the support of D could be narrow enough to miss some part of P, resulting in non-vanishing error as indicated in Theorem For SA-FL, distribution Q is a mixture of P and D (Q A1 Pr with )1 A2 2 0, λ1 + 1). thus having the same support with P. Hence, under Assumption ! the PAC-learnability is guaranteed.
Figure I: Diagram of distributions for do- main adaptation and federated learning.
Although we provide promising bound to show the PAC-learaabiltyy of SA-FL Theorem 2 the superiority of SA-FL over training solely with dataset T in server (i.e., ({{)))
pp is not always guaranteed as B - 0 (i.e., Q becomes increasingly different from P). In what follows, we reveal under what conditions between P and Q could SA-FL perform no worse than centralized learning in terms of generalization error.
Theorem (SA-FL Being No Worse Than Centralized Learning). Consider an SA-FL system with arbitrary system and data heterogeneity. !f Assumption holds and additionally Rh( S Rp(h)) and p (h2) (AA(TT 5)), where A(nT, 5) dx log nr + 13
log())), then with probability
ny
dy
least - 8 for any E (0, it holds that ep(h@) = Ō ((dx/nr)* p Other parameters are the same as defined in Theorem
Here, we remark that p())) ((A(TT, 0)) is a weaker condition than the p = 0 condition and the covariate shift assumption (Pyix = Qrix) used in the transfer learning literatures (Hanneke & Kpotufe, 2019 2020). Together with the condition Rr(h²) S (R(h))) the following intermedi- ate result holds: (ha) - (hp)) = ((A((T))))))))))) 6)) (see Lemma in the supplementary material). Intuitively, this states that "if P and Q share enough similarity, then the difference of excess empirical error between hiz and hü on P can be bounded." Thus, the excess error of hy shares the same upper bound that of hp in centralized learning. Therefore, Theorem jiplies that, under mild conditions, SA-FL guarantees the same generalization error upper bound as that of centralized learning with dataset T,, hence being "no worse than" centralized learning with dataset T.
4 THE SAFARI ALGORITHM
Although we have shown that SA-FL is PAC-learabbe under partial client participation, we note that SA-FL still follows the server-client architecture, which demands intensive communication between the server and clients. Hence, it is important to design communication-efficne with comparable level of communication complexity as that of conventional FL.. this section, we propose a new algorithm called SAFARI (server-aided federated averaging) algorithm for SA-FL and characterize its convergence guarantees.
algorithms for SA-FL
As shown in Algorithm D SAFARI iteratively performs the following three steps: 1) Server samples a subset of clients as in conventional FL and synchronize the latest global model x, with each participating clients (Line 3); 2) The server and all participating clients train the model based on local dataset (Lines 4-8). Specifically, client initializes its local model with x,, and then performs K local steps by the stochastic gradient descent method. Then, each client sends its locally accumulated

---

Under review as a conference paper at ICLR 2023
Algorithm 1 The SAFARI Algorithm for SA-FL.
Initialize Xo-
2: for r 0,...
do 3: The server samples subset S, clients with |S,] and send current model zt-
4: for Each client E S, do
5: Synchronization: x = Xy.
6: Local updates: for k = 0,... 1: x = - S7,
7: Send A = Ek= VFi(X (7,6) to server.
- K-
8: end for
9:
for Server do
10:
Local updates: for = 0, ...9 , 1:
xx,+1 = - S.,k)
A - 2k= VF <0
11:
Receive 2, E Sr, and normalize it:
A = 12:--19111
A:-
12: Server Update:
X,+1 = X, + ( [..] Eies, 4
13:
end for end for
14:
update A; back to the server. Note the server simultaneously takes K local steps based on its auxiliary dataset (in Line 10). 3) Server aggregates and updates the global model (Lines 11-12). Upon receiving the local update A, the server normalizes and rescales it by saper-parameter C,, Then, the server updates the global model by aggregating the normalized update Á and the server's update A based on its own auxiliary dataset. Compared to FedAvg (McMahan et al., 2017) in FL., SAFARI shares the same communication and computation process from the client's s perspective. Hence, it enjoys the same level communication efficiency and privacy benefits. Before conducting the convergence performance analysis, we first state two commonly used assumptions in the FL literature.
Assumption 2. (L-Lipschitz Continuous Gradient) There exists a constant L > 0, such that IRd.
[VF(() Fy S L||x [i|x- ylI. Vx,
Assumption 3. (Unbiased Stochastic Gradient with Bounded Variance) The stochastic gradient is unbiased, i.e, F(vF(x,E)) Fx) and B[I[FF(x, VF(() < o² parrtill
With the assumptions above, we now in the position to analyze the convergence of SAFARI.
Theorem 4 (Convergence Rate for SAFARI ). Under Assumptions and let constant learning rate 1) satisfy ( 4LK1 21LK)-20K(L (L + 4K L)))??> > O. Then, the sequence {xr} generated by the SAFARI algorithm satisfies:
1 R-1
F(xo) F(xx))
B
<
+ [5 20K + +Lm) 02]
nR
1
Ln
R
Rz
R
t=0
where C is a constant and x" denotes an optimal solution.
Theorem implies an O(1/R) /R) convergence rate to neighborhood of stationary point. Furthermore, by choosing parameters {cr} and the learning rate y) appropriately, we have the following convergence rate to a stationary point:
Corollary ! R-1 &e bounded and learning rate 1 VKR the convergence rule of SAFARI is:
1
1
1/2
R1/2
K2R
13/2
R3/2
In Theoremp and Corollary[I [ we show the convergence guarantee of SAFARI under no extra assump- tions on the data and system heterogeneity (client participation), which corroborates the learnability
7

---

distribute the Under review as a conference paper at ICLR 2023
0.6
0.9
Test Accuracy
Test Accuracy acy
0.5
0.4
0.7
0.3
SAFARI+ Datasize 500
SAFARI+ Server Dalasize 1000
Incomplete Client Participation Index: 0
0.2
0.6
SAFARI+ Server Datasize 5000 FedAvg
Incomplate Client Participation Index: 2
Incomplete Client Participation Index:
0.1
0.5
10
2
0
5000 1000 1500 2000 2500 3000 3500 4000 Communication Round
Non-IID Index (p)
(a) FedAvg on MNIST
(b) SAFARI on CIFAR-I0 with & = and
Figure 2: Test accuracy of FedAvg on MNIST and SAFARI on CIFAR-10 with partial client partici- pation. Larger partial client participation index means less clients participate in the training, and smaller non-i.idd index p means the data across clients are more heterogeneous.
analysis in Section 3 Hence, in the worst-case scenarios, convergence rate (L1((K/2R1/2)) is achieved for sufficiently large R and K < R. In comparison, consistently for the same setting in FI. (Yang et al. 2022). This verifies the superiority of SA-FL conventional FL with partial client participation. Note that Corollary requires requiree convergent series (c².. This can be relaxed to ΣØ=1 ef O RR, R. K3/2 to maintain the same (LL/(K1/ R2/2)) rate. It can be readily verified that p-series (c, = P) satisfies the condition.
vanishing error term emerges
Also, we will see later in numerical results that, compared to FedAvg, convergence as the size of auxiliary server dataset increases. is also worth noting that SA-FL can be used to mitigate Byzantine attacks to FL systems. For example, empirical success of utilizing an auxiliary dataset and normalization at the server has been shown in (Cao et al. 2021) in defending against Byzantine attacks in FL systems. Lastly, note that the convergence rate bound in Corollary | does not explicitly depend on the number of participating clients m. It is thus an interesting future work to study whether there exist algorithms for SA-FL. that theoretically guarantee "linear speedup effect" as the number of participating clients increases under partial client participation.
SAFARI has faster
5 NUMERICAL RESULTS
In this section, we conduct numerical experiments to verify our theoretical results using 1) logistic regression (LR) on MNIST dataset (LeCun al. 1998) and 2) convolutional neural network (CNN) on CIFAR-10 10 dataset (Krizhevsky al.) 2009). To simulate data heterogeneity,
data into each client evenly in a based partition, following the same process as in previous works (e.g., (McMahan et al. 2017 Yang al. 2021b Li ei al. (020b)). As result, we can use parameter p to represent the classes of labels in each client's dataset, which serves as an index of data heterogeneity level (non-i.i.d. index). The smaller p-value, the more heterogeneous the data among clients. To mimic partial client participation, we force clients to be excluded. We can use as index to represent the degree of such partial client participation. In our experiments, there are M = 10 clients in total, and m clients participate in the training in each communication round, who are uniformly sampled from the M clients. We use two algorithms as baselines to compare with our algorithm: i) the FedAvg algorithm without any auxiliary dataset at the server; and ii) the SGD algorithm for centralized learning with dataset only at the server (without any clients). Due to space limitation, we highlight four key observations in this section, and relegate the details of the experiments and additional experiments to the supplementary material.
1) Performance Degradation of Partial Client Participation: We first show the test accuracy of FedAvg on MNIST for different values of non-i.i.d. index and partial client index s in Fig. 2(a) 5), partial client participation has negligible
For nearly homogeneous data (e.g., from p 10 impacts on test accuracy. However, for highly non-i.i.d. cases, partial client participation results in dramatic performance degradation. Specifically, for p 1, the test accuracy for = 4 is only 57%
8

---

Under review as a conference paper at ICLR 2023
Table 2:
Test accuracy improvement (%) for
Table 1: Test accuracy improvement (%) for SAFARI compared with FedAvg on MNIST with partial client participation means "no statistical difference within 2%
SAFARI under partial client participation s = 4 com- pared with SGD in centralized learning on MNIST. Smaller non-i.i.d. index means the data across clients is more heterogeneous. '-' means "no statistical dif- ference within 2% error bar"..
4. '-'
error bar".
SERVER
NON-IIID INDEX (p)
SERVER
NON-IID INDEX (p)
DATASIZR
10
5
2
DATASIZE
10
5
2
50
12.32
50
28.94
19.65
9.32
3.69
100
5.24
16.48
100
20.46
14.84
8.58
-3.42
500
9.40
27.55
500
6.13
3.92
2.09
1000
-10.88
28.78
1000
3.79
3.16
yielding a large degradation (35%) compared to that of 8 = 0. This is consistent with the worst-case analysis in Theorem T and also the main motivation of SA-FL.
2) Improvement of the SAFARI Algorithm under Partial Client Participation: In Table | we show the test accuracy improvement of our SAFARI algorithm compared with that of FedAvg in standard FL. The key observation is that, with a small amount of auxiliary data at the server, there a significant increase of test accuracy for our SAFARI algorithm. For example, with only 50 data samples at the server (0.1% of the total training data), there is 12.32% test accuracy increase. With 500 data samples, the improvement reaches 27.55%. This verifies the effectiveness of our SA-FI framework and our SAFARI algorithm. Another observation is that for nearly homogeneous case (e.g., from p = 10 to = 5). there is no statistical difference with or without auxiliary data at the server (denoted by +-' in Table I This is consistent with the previous observations of negligible degradation in cases with homogeneous data across clients.
3) Benefits of Collaboration Even with Partial Client Participation: In Table show the comparison between our SAFARI algorithm under partial client participation (s 4) and SGD for centralized learning (i.e., only with data the server). This comparison is illustrate the benefit of collaborations from the clients. We can see these collaborations from the clients significantly improve the performance for the nearly homogeneous case, especially when the size of the server dataset is small (cf. the columns of 10 and 5). However, for highly heterogeneous cases, it shows no obvious improvement from the collaboration of clients if participation is partial. This confirms our theoretical analysis in Theorem 2 Specifically, highly partial client participation and heterogeneous data render a small 8-value, and there is no clear benefit of collaboration in FL over centralized learning only on small auxiliary dataset due to the significant distribution deviation.
Convergence Speedup of SAFARI with Larger Server Dataset: this experiment, we illustrate the speedup effect of SAFARI numerically as the size of server dataset increases. In Fig. 2(b) we show the convergence processes of SAFARI on CIFAR-I0 for partial client participation (s = 4) and non-i.i.d. data (p 1). We can see clearly that the convergence of SAFARI is accelerating and the test accuracy increases as more data are employed at the server. In this experiment setting, we also plot the convergence of FedAvg in Fig, 2(b) It can be seen that all three cases of SAFARI converge faster than FedAvg in this experiment.
6 CONCLUSION
In this paper. we rigorously investigated the server-aided federated learning (SA-FL) framework. which has been increasingly adopted in practice to mitigate the impacts of partial client participation in conventional FL. In SA-FL., the key idea to deploy an auxiliary dataset at the server to reduce the distribution deviation induced by partial client participation. To characterize the benefits of SA-FL, we first showed that conventional FL not PAC-learnable under partial client participation by establishing a fundamental generalization error lower bound. Then, we showed that SA-FL is able to revive the PAC-leamabilityy of conventional FL under partial client participation. Upon resolving the PAC-learaaillity challenge, proposed new SAFARI (server-aided federated averaging) algorithm that enjoys convergence guarantee and the same level of communication efficiency as that of conventional FL. Extensive numerical results also validated theoretical findings.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Durmus Alp Emre Acar, Yue Zhao, Ramon Matas Navarro, Matthew Mattina, Paul N Whatmough, and Venkatesh Saligrama. Federated learning based on dynamic regularization. In International Conference on Learning Representations, 2021.
Dmitrii Avdiukhin and Shiva Kasiviswanathan. Federated learning under arbitrary communication patterns. In Marina Meila and Tong Zhang (eds.), Proceedings the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 425-435. PMLR, 18-24 Jul 2021.
Shai Ben-David John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wortman Vaughan. A theory of learning from different domains. Machine learning, 79(1):151-175, 2010.
Keith Bonawitz, Hubert Eichner, Wolfgang Grieskamp, Dzmitry Huba, Alex Ingerman, Vladimir Ivanov, Chloe Kiddon, Jakub Konecný, Stefano Mazzocchi, H Brendan McMahan, et al. Towards federated learning at scale: System design. arXiv preprint arXiv:
2019.
Nader Bshouty, Nadav Eiron, and Eyal Kushilevitz. Pac learning with nasty noise. Theoretical Computer Science, 288(2):255-275 2002.
Xiaoyu Cao, Minghong Fang, Jia Liu, and Neil Zhenqiang Gong. Fltrust: Byzantine-robust feder- ated learning via trust bootstrapping. ISOC Network and Distributed Systems Security (NDSS) Symposium, abs/2012. 13995, 2021.
Yae Jee Cho, Jianyu Wang, Tarun Chiruvolu, and Gauri Joshi. Personalized federated learning for heterogeneous clients with clustered knowledge transfer. arXiv preprint urXiv:2109.00) 19, 2021.
Corinna Cortes, Mehryar Mohri, Michael Riley, and Afshin Rostamizadeh. Sample selection bias correction theory. In International conference on algorithmic learning theory, pp. 38-53. Springer, 2008.
Shai Ben David, Tyler Lu, Teresa Luu, and Dávid Pál. Impossibility theorems for domain adaptation. In Proceedingy of the Thirteenth International Conference Artificial Intelligence and Statistics, pp. 129-136. JMLR Workshop and Conference Proceedings, 2010.
Xinran Gu, Kaixuan Huang, Jingzhao Zhang, and Longbo Huang. Fast federated learning in the presence of arbitrary device unavailability. Thirty-Fifth Conference on Neural Information Processing Systems, 2021.
Steve Hanneke. Refined error bounds for several learning algorithms. The Journal of Machine Learning Research, 17(1)4667-4421, 2016.
Steve Hanneke and Samory Kpotufe. On the value of target data in transfer learning. In NeurIPS. 2019.
Steve Hanneke and Samory Kpotufe. A no-free-lunch theorem for multitask learning. arXiv preprint arXiv:2006.1570 15785, 2020.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. SCAFFOLD: Stochastic controlled averaging for federated learning. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 5132-5143. PMLR, 13-18 Jul 2020.
Sai Praneeth Karimireddy, Martin Jaggi. Satyen Kale, Mehryar Mohri, Sashank J. Reddi, Sebastian U Stich, and Ananda Theertha Suresh. Breaking the centralized barrier for cross-device federated learning. In Thirty-Fifth Conference on Neural Information Processing Systems, 2021.
Prashant Khanduri, PRANAY SHARMA, Haibo Yang, Mingyi Hong. Jia Liu, Ketan Rajawat, and Pramod Varshney. STEM: A stochastic two-sided momentum algorithm achieving optrmal sample and communication complexities for federated learning. In Thirty- Fifth Conference on Neural Information Processing Systems, 2021.
10

---

Under review as a conference paper at ICLR 2023
Vladimir Koltchinskii. Local rademacher complexities and oracle inequalities in risk minimization. The Annals of Statistics, 34(6):2593-22) 2656, 2006.
Nikola Konstantinov, Elias Frantar, Dan Alistarh, and Christoph Lampert. On the sample complexity of adversarial multi-source pac learning. In International Conference on Machine Learning, pp. 5416-5425, PMLR, 2020.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. 2009.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278 (1::):22222222 1998.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. In I. Dhillon, D. Papailiopoulos, and V. Sze (eds.), Proceedings of Machine Learning and Systems, volume 2, pp. 429-450, 2020a.
Xiang Li, Kaixuan Huang, Wenhao Yang. Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data. In International Conference on Learning Representations, 2020b.
Mi Luo, Fei Chen, Dapeng Hu, Yifan Zhang, Jian Liang, and Jiashi Feng. No fear of heterogeneity: Classifier calibration for federated learning with non-lID data. In Thirty-Fifth Conference on Neural Information Processing Systems, 2021.
Yishay Mansour, Mehryar Mohri, and Afshin Rostamizadeh. Domain adaptation: Learning bounds and algorithms. arXiv preprint arXiv:0902.3430, 2009.
Pascal Massart and Élodie Nédélec. Risk bounds for statistical learning. The Annals of Statistics, 34 (5):2326-23)) 2006.
Brendan McMahan, Fider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera Arcas. Communication-elficieet learning of deep networks from decentralized data. In Artificial intelli- gence and statistics, pp. 1273-1282. PMLR, 2017.
Brendan McMahan et al. Advances and open problems in federated learning. Foundations and Trends@ in Machine Learning, 14(1), 2021.
Aritra Mitra, Rayana Jaafar, George J. Pappas, and Hamed Hassani. Linear convergence federated learning: Tackling client heterogeneity and sparse gradients. In Thirty-Fifth Conference Neural Information Processing Systems, 2021.
Mehryar Mohri and Andres Munoz Medina. New analysis and algorithm for learning with drifting distributions. International Conference on Algorithmic Learning Theory, pp. 124-138. Springer, 2012.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
Tomoya Murata and Taiji Suzuki. Bias-variance reduced local sgd for less heterogeneous federated learning. arXiv preprint arXiv:2102.03// /98, 2021.
Yichen Ruan, Xiaoxi Zhang, Shu-Che Liang, and Carlee Joe- bonn Towards flexible device partici- pation in federated learning. In International Conference on Artificial Intelligence and Statistics, pp. 3403-3411. PMLR, 2021.
Masashi Sugiyama. Matthias Krauledat, and Klaus-Robert Müller. Covariate shift adaptation by importance weighted cross validation. Journal of Machine Learning Research, 8(5), 2007a.
Masashi Sugiyama, Shinichi Nakajima, Hisashi Kashima, Paul Von Buenau, and Motoaki Kawanabe. Direct importance estimation with model selection and its application to covariate shift adaptation. In NIPS, volume 7, pp. 1433-1440. Citeseer. 2007b.
Guan Wang. Charlie Xiaoqian Dang, and Ziye Zhou. Measure contribution of participants in federated learning. 2019 IEEE International Conference on Big Data (Big Data), pp. 2597-2604, 2019.
11

---

Under review as a conference paper at ICLR 2023
Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and H Vincent Poor. Tackling the objective inconsistency problem in heterogeneous federated optimization. Advances in Neural Information Processing Systems, 33, 2020.
Jianyu Wang, Zachary Charles, Zheng Xu, Gauri Joshi, H Brendan McMahan, Maruan Al-Shedivat, Galen Andrew, Salman Avestimehr, Katharine Daly, Deepesh Data, et al. A field guide to federated optimization. arXiv preprint arXiv:2107.06917, 2021a.
Lixu Wang, Shichao Xu, Xiao Wang, and Qi Zhu. Addressing class imbalance in federated learning. In Proceedings of the AAAI Conference Arlificial Intelligence, volume 35, pp. 10165-10173, 2021b.
Shiqiang Wang and Mingyue Ji. A unified analysis of federated learning with arbitrary client participation. arXiv preprint 2rX1v:2205.13668, 2022.
Cong Xie, Sanmi Koyejo, and Indranil Gupta. Asynchronous federated optimization. arXiv preprint arXiv:1903.03954, 2019.
Chengxu Yang, Qipeng Wang, Mengwei Xu, Zhenpeng Chen, Kaigui Bian, Yunxin Liu, and Xuanzhe Liu. Characterizing impacts heterogeneity federated learning upon large-scale smartphone data. In Proceedings of the Web Conference 2021, pp. 935-946, 2021a.
Haibo Yang. Minghong Fang, and Jia Liu. Achieving linear speedup with partial worker participation in non-llI) federated learning. In International Conference on Learning Representations, 2021b.
Haibo Yang, Xin Zhang, Prashant Khanduri, and Jia Liu. Anarchic federated learning. In International Conference on Machine Learning, pp. 25331 -23663. PMLR, 2022.
Xinwei Zhang, Mingyi Hong, Sairaj Dhople, Wotao Yin, and Yang Liu, Fedpd: federated learning framework with optimal rates and adaptivity to non-iid data. arXiv preprint arXiv:2005. 2020.
Yue Zhao, Meng Li, Liangzhen Lai, Naveen Suda, Damon Civin, and Vikas Chandra. Federated learning with non-iid data, arXiv preprint 1rx.v:/806.00588 2018.
12


Reviews:
[{"review_id": "fg7Gg8W7ZOi", "reviewer": "Reviewer_m3ZD", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "> After the rebuttal: Some of my concerns have been resolved. However, the optimization theory still does not explain why $c_t = 0$ is not the optimal one. Since no theory shows that the generalization error of SA-FL is better than centralized learning. The whole story does not explain the empirical results.\n\nIn this paper, the authors study the PAC-learnability of Federated Learning (FL) with or without an auxiliary dataset on the central server. In the regime of FL with an auxiliary dataset on the central server (called SA-FL), they propose a new algorithm called SAFARI in which the central server computes the next round's initial model by both the aggregated model updates from local servers and the model update based on its own dataset.", "summary_of_the_review": "This paper is the first to establish some theoretical guarantees of a practically used framework called server-aided federated learning (SA-FL). However, the concerns in the \"Strength And Weaknesses\" section make me unsure about the contributions of this paper. \n\n\n", "strength_and_weaknesses": "**Strength**:\n- This paper provides theoretical guarantees for a Federated Learning framework that has been adopted in practice.\n- The ablation study in Section 5 is insightful. \n\n**Weakness**:\n\nI have several concerns about the theoretical results of this paper. \n\nMajor concerns: \n- In the paragraph below Theorem 2, it says \"Note that when $\\beta\\geq 1$, the first term in Eq. (1) dominates.\" This is not true unless $n_T + n_S > d_{\\mathcal{H}}$. However, we cannot expect $n_T + n_S > d_{\\mathcal{H}}$ to hold for FL with deep neural networks. For example, Bartlett et al. [1] show that $d_\\mathcal{H} \\geq \\Omega(WL\\log(W/L))$ for ReLU neural networks, where $W$ and $L$ are numbers of parameters and layers, respectively. If $n_T + n_S \\leq d_{\\mathcal{H}}$, the bound in Theorem 2 becomes vacuous. This should be explicitly mentioned.\n- The assumption on \"$(\\alpha,\\beta)$-Positively-Related\" does not seem to be mild/natural. The authors did not justify it or give any example to explain when this condition might hold. \n- As far as I can tell, SA-FL degenerates into FL when $n_T = 0$. If we plug $n_T = 0$ into Theorem 2, the result shows that FL is also PAC-learnable under the same assumptions. This seems to contradict the main story of this paper. \n- The authors mention that \"For example, it is shown in (Yang et al., 2021a) that more than 30% of clients never participate in FL, while only 30% of the clients contribute to 81% of the total computation even if the server uniformly samples the clients.'' However, this paper does not characterize the generalization bounds for participating and nonparticipating clients separately as suggested in [2]. \n- To ensure convergence, the proposed algorithm SAFARI needs $c_t$ decreases to 0 quickly enough (or even setting $c_t= 0$), which implies that the contribution of the local model updates diminishes to (or is) zero and the algorithm approaches (or is) the centralized training on the auxiliary data. Then, it is not surprising that the convergence guarantee does not depend on heterogeneity. \n\nMinor concerns:\n- There is a $K^2\\eta^3$ term in Theorem 4. If we choose $\\eta = \\frac{1}{\\sqrt{KT}}$, the term becomes $K^2 \\frac{1}{K^{3/2}T^{3/2}} = \\frac{K^{1/2}}{T^{3/2}}$, which does not appear in the convergence rate shown in Corollary 1.\n- Why the error bars are not shown in Figure 2?\n- Only comparing SAFARI to FedAvg (LocalSGD) is not enough. More modern baselines such as SCAFFOLD (Karimireddy et al. 2019), FedProx (Li et al. 2018), and Nastya (Malinovsky et al. 2022) are needed to be compared with for showing the effectiveness of the proposed algorithm.\n\n[1] Bartlett, Peter L., Nick Harvey, Christopher Liaw, and Abbas Mehrabian. \"Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks.\" The Journal of Machine Learning Research 20, no. 1 (2019): 2285-2301.\n\n[2] Yuan, Honglin, Warren Richard Morningstar, Lin Ning, and Karan Singhal. \"What Do We Mean by Generalization in Federated Learning?.\" In International Conference on Learning Representations. 2021.\n\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "SMCS81TS4E", "reviewer": "Reviewer_dvBg", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors consider FL problem in the scenario where some nodes do not participate in the learning and provide a theory that analysis this scenario. Moreover, the authors consider SA-FL: the server takes part in the optimization process to mitigate the corruption from partial participation of the nodes.", "summary_of_the_review": "The statistical part (Section 3) of the paper seems to be solid. However, I have some questions about Assumption 1 and Definition 4 that are not fully justified.\n\nAt the same time, the optimization part (Section 4) is weak and does not provide a method that would solve the main problem.\n\nSection 3 seems to be somewhere between \"marginally above the acceptance threshold\" and \"accept, good paper.\" But Section 4 definitely should be improved.", "strength_and_weaknesses": "Before I start, I should acknowledge that I'm not an expert in statistical learning theory, so in this part of the paper, I can easily miss some important things. I am closer to the theory of optimization methods.\n\nThe first part is devoted to the statistical learning theory of FL under the partial participation setting. The motivation is clear and very important. In the beginning, the authors prove the \"Impossibility Theorem\" which is very interesting. It states the vanilla FedAvg will fail under the authors' setting. So that is why the authors analyze the idea of SA-FL.\n\nFrom this point, I see the first weakness that I would like the authors to clarify:\n\n1. The server has access to the dataset $T.$ So, in total, we have access to the dataset $Q = D \\cup T.$ Not going into the details, the motivation of SA-FL is based on two assumptions: Assumption 1 and Definition 4, which introduce some similarity between datasets $Q$ and $P.$ The main motivation of the paper is to consider the case when $D \\neq P.$ But from the assumption intuitively the authors require that $D \\approx P.$ Moreover, is it possible to provide the \"Impossibility Theorem\" under these assumptions? The assumptions can be too strong.\n2. Theorem 3: the assumption $\\varepsilon_P(h^*_Q) \\leq O(A(...))$ seems to be strong. They say that the optimal hypothesis from $Q$ is almost the optimal hypothesis from $P.$\n\nIn total, the statistical part I would evaluate with \"marginally above the acceptance threshold.\"\n\nNow, I move to Section 4.\nThe authors provide the SAFARI algorithm that has the following weaknesses:\n1. From Theorem 4, it is clear that we have to take $c_t = 0$ to get the best convergence rate. It is not clear why we should take $c_t > 0.$\n2. In line 3, the algorithm samples nodes uniformly. The main idea of the paper is to consider the setting with more complex samplings such that some nodes do not participate!\n3. In line 10, the algorithm calculates gradients of the full function $F!$ The main point of FL is that server does not have access to $F!$ In the proof, the authors use the fact that $E_T \\nabla F(x, \\xi^0) = \\nabla F(x) = E_P \\nabla F(x, \\xi).$ But in the previous section, the authors say that the server has access only to a small subset $T = (\\xi^0_i)_i^k,$ so $E_T \\nabla F(x, \\xi^0) = \\frac{1}{k} \\sum_i \\nabla F(x, \\xi^0_i)$ and, in general, it does not equal to  $\\nabla F(x).$ All it means is that the server has access to the function $F.$\n\nTheoretically, the SAFARI algorithm does not solve the main problem of the paper.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "R65HqNoXTk", "reviewer": "Reviewer_fscs", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper is about dealing with partial participation in federated learning. Indeed, in the heterogeneous setting, there is a drift in the obtained solution if not all clients participate. the authors study this discrepancy and propose new algorithms to mitigate it. They consider the idea of sever-aided federated learning (SA-FL), which is to equip the server with a small auxiliary dataset that approximately mimics the population distribution. They provide new results on SA-FL and propose a new algorithm, called SAFARI, which handles partial participation and is communication-efficient.", "summary_of_the_review": "The paper provides some new insights on partial participation, which is a timely and important problem in modern distributed learning settings. It is nice to obtain theoretical findings on SA-FL, which was so far heuristic.", "strength_and_weaknesses": "The paper provides interesting theoretical insights about heterogeneity and the important challenge of partial participation in FL.\n\nSAFARI converges sublinearly to a neigborhood of a stationary point. \nI have a question: in Assumption 3: what is partial at the end? In any case, the bounded gradient assumption is restrictive and there seems to be no way to study linear convergence under strong convexity, for instance, since this is not compatible with this assumption.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "DXOkmaO_FCr", "reviewer": "Reviewer_uhzS", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work theoretically analyzes that conventional Federated Learning (FL), heterogeneous and arbitrary client participation, is not Probably Approximately Correct (PAC) learnable. And then explore the reason and the fact that the server-aided federated learning (SA-FL) framework uses an auxiliary server dataset to reduce the distribution deviation induced by partial client participation (I will abbreviate it as PP), leading to the PAC-learnability. Besides, an algorithm SAFARI is proposed, which guarantees convergence. Ablation studies on MNIST and CIFAR10 verify the efficiency of the proposed algorithm. ", "summary_of_the_review": "This work is an interesting paper that theoretically explores partial client participation in federated learning. The theories are inspiring, but more comprehensive experiments should be conducted. I would like to increase my score if the above concerns are resolved. ", "strength_and_weaknesses": "Strength:\n1. This paper theoretically proves conventional FL under the heterogeneous and arbitrary client participation setting is not PAC-learnable even in the limit of infinitely many data samples and training iterations. This could be a very interesting exploration. \n2. Based on conventional FL, SA-FL is theoretically analyzed and shown to be PAC-learnable under a few strong assumptions. \n3. SAFARI algorithm is proposed for handling SA-FL and achieves almost the same convergence rate as the state-of-the-art conventional FL algorithm under particular conditions. \n\nConcerns:\n1. It's unclear whether the Assumption. 1 (noise condition) holds on real datasets, which may have very large noise. E.g., it would be interesting if some real example could be shown that the noise condition is satisfied. \n2. It's unclear whether different training protocols influence performance in SA-FL. Given client-distributed dataset $S_D$ with cardinality $n_S$ and server-persisted dataset $T$ with cardinality $n_T$, whether different training strategies affect the robustness and convergence? More concretely, will the following two strategies lead to the same behavior? a) using $S_D$ as a whole for fixed iterations $T^d>0$ and then consider $T$ only (without future averaging) for the following interactions; b) same as above but after $T^d$, do more averaging. What if $T^d=0$?\n3. More comprehensive experiments should be provided. In Tab. 1 and Tab. 2 in the main content, only the \"improvement\" of SAFARI over FedAvg and SGD is provided; I'm curious about the absolute performance. Are SAFARI, FedAvg, and SGD fine-tuned? How are the hyper-parameters selected? Besides, I checked Fig. 4 in the appendix, e.g., (d), SAFARI is always no better than SGD; more analysis should be provided. \n4. Seversize data size seems to be too large. MNIST and CIFAR10 both have 60K images, and in this paper, 50-1000 data size from the distribution $p$ is selected; it seems the proportion is too large and not representative in practice. I believe SA-FL/FL is similar to the difference between few-shot learning and zero-shot learning, but only 1, 2, or at most 10 samples per class are provided for the latter. I'm concerned with the performance of a smaller server data size, which is more practical and interesting. \n5. In Sec. 5, \"to simulate data heterogeneity, distribute the data into each client evenly.\" I'm unsure if each client has the same data distribution in this setting. What if a different and more heterogeneous data-splitting scheme is applied? Since this paper mainly focuses on the heterogeneous data setting, this should be more carefully considered. \n\nAdditional comment:\n1. Regarding the difference between FL and SA-FL, the authors may illustrate it with zero-shot and few-shot learning, which is almost the same case. This could be an interesting thinking perspective. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject