Generalization Bounds for Federated Learning: Fast Rates, Unparticipating Clients and Unbounded Losses
Authors: Xiaolin Hu
Shaojie Li
Yong Liu
Venue: ICLR 2023 poster (2023)
Keywords: Federated learning
Generalization error
Risk bound
Unbounded losses
Learning theory

Abstract: In {federated learning}, the underlying data distributions may be different across clients. This paper provides a theoretical analysis of generalization error of {federated learning}, which captures both heterogeneity and relatedness of the distributions. In particular, we assume that the heterogeneous distributions are sampled from a meta-distribution. In this two-level distribution framework, we characterize the generalization error not only for clients participating in the training but also for unparticipating clients. We first show that the generalization error for unparticipating clients can be bounded by participating generalization error and participating gap caused by clients' sampling. We further establish fast learning bounds of order $\mathcal{O}(\frac{1}{mn} + \frac{1}{m})$ for unparticipating clients, where $m$ is the number of clients and $n$ is the sample size at each client. To our knowledge, the obtained fast bounds are state-of-the-art in the two-level distribution framework. Moreover, previous theoretical results mostly require the loss function to be bounded. We derive convergence bounds of order $\mathcal{O}(\frac{1}{\sqrt{mn}} + \frac{1}{\sqrt{m}})$ under unbounded assumptions, including sub-exponential and sub-Weibull losses. 

Published as a conference paper at ICLR 2023
GENERALIZATION BOUNDS FOR FEDERATED LEARN- ING: FAST RATES, UNPARTICIPATING CLIENTS AND UNBOUNDED LOSSES
Yong Xiaolin Hu Shaojie LYng, Liu
'Gaoling School of Artificial Intelligence. Renmin University of China, Beijing, China Beijjng Key Laboratory of Big Data Management and Analysis Methods, Beijing, China (xiaolings inhu, jie5 hew.:ieeee,,nnnnnnee siuynnggsaieeeeeee..o....o e edu.eddu.cc cn
ABSTRACT
In federated learning, the underlying data distributions may be different across clients. This paper provides theoretical amalysis of generalization error of feder- ated learning, which captures both heterogeneity and relatedness of the distribu- tions. In particular, assume that the heterogeneous distributions are sampled from a meta-distribution. In this two-level distribution framework, we character- ize the generalization error not only for clients participating in the training but also for unparticipating clients. We first show that the generalization error for unparticipating clients can be bounded by participating generalization error and participating gap caused by clients' sampling. We further establish fast learning bounds of order O 1 + -21 for unparticipating clients, where m is the number of clients and is the sample size at each client. To our knowledge, the obtained fast bounds are state-of-the-ee in the two-level distribution framework. Moreover, previous theoretical results mostly require the loss function to be bounded. We de- rive convergence bounds of order O mmn
mn
+ 1) under unbounded assumptions, vm
including sub-ex uubeexponential and sub-Weibbe Weibull losses.
INTRODUCTION
In federated learning, common model is trained based the collaboration of the participating clients holding local data samples (McMahan et af.) 2017). Typically, the underlying distributions vary across clients since the data-generating processes are affected by the local environment. Fed- erated learning is heterogeneous in the scenario where local distributions are different (Wang et al.] 2021. Most existing experimental and theoretical results focus on the convergence of optimization on training datasets (Li et al. 2020b, Karimireddy et al. 2020 Mitra et al. 2021] Mishchenko et al.) 2022 Yun et al. 2022). The generalization error, which more natural and important in machine leanring, seems not to have been carefully examined in heterogeneous federated learning.
As key performance indicator of the machine learning model, generalization error measures the performance of trained model by its population risk with the corresponding distribution. However, existing generalization results are generally derived for clients participating the training, which only captures the performance of the learned model on seen distributions during training (Mohri cet al. 2019 Chen et al., 2021 Masiha et al. 2021).
In practice, the probability that client participates in the federated training is affected by many factors such as the reliability of network connections or the availability of the client. The realistic participation ratio may be slow and variety of clients never have chance to participate during the training process (Kairouz et al. 202T; Li et al., 2020a] Yuan et al., 202I). Though the training pro- cess is operated only participating clients, the trained model will be used by both unparticipating and participating clients. Since the data distributions of unparticipating clients are different from that of participating clients, is natural and emergent ask the following question:
Would the unparticipating clients benefit from the model trained by participating clients?
"Corresoonding Author.

---

Published as a conference paper at ICLR 2023
To answer this question theoretically, we take the participation gap into account in the analysis of generalization error, which is generally ignored by existing works.
In addition to the ignored participating gap, existing theoretical results the generalization error of heterogeneous federated learning have two more limitations to our knowledge. First, all previous learning rates in probability form are of the order O /mm) where m is the number of clients and
is the sample size at each client (Mohri et al. 2019 We note that faster rates of order O ( are derived in (Chen et al. 2021]. However, their learning rates are in expectation form. Faster learning rates in probability form haven't been derived even only for participating clients. The guarantees in-expectation form reflect the average performance of the model trained based on the randomly sampled datasets. The theoretical bounds in probability form, which focus in this paper, reflect the performance of a single sampling on datasets (Klochkov & Zhivotovskiy, [021]] Kanade ee al., 2022 Sefidgaran by assuming that the loss function is bounded. However, there are a variety of learning problems that do not satisfy this assumption. This includes regression problems where unbounded noise is added to labels (Kuchibhotla & Patral [0222] Kuchibhotla & Chakrabortty 2018 Zhang & Zhou, 2018). clustering tasks with heavy-tailed distribution (Paul et al.)
al., 2022a). Second, most previous generalization bounds are derived
al.] 2021] Vellal et | domain adaptation, and so on. Notable exception works in this direction include (Barnes et al. (0222 and (Sefidgaran al., 2022b). However, their results are established under the assumption that local clients are homogeneous, which is highly restrictive in the general federated scenario.
In this paper, we assume that data distributions of participating and unparticipating clients are drawn from meta-distribution P. We argue that this assumption is reasonable in practice. For instance, in cross-device federated learning, the number of total clients is generally large and it is natural to assume that there exists meta- mnta-distribution (Reisizadeh et al. 2020; Wang et al.) 2021). In this learning scenario, we assume that the total number of clients is M. Among all these M clients, only m clients have chance to participate in the training phase, which means that the training process only involves the m distributions {D: }mm Note that the total number M and the number of unpar- ticipating clients/distributiinn is generally larger than m (Hu et al.. 2022 Xu & Wang. 2020 Yang et al. 2020). Practically, the model is trained based on datasets (5 S where S, is the dataset located in client and sampled from D. This two-level framework not only captures the hetero- geneity of clients' distributions but also reflects the relatedness of the distributions. Thanks to this framework, we are allowed to characterize the generalization performance of both participating dis- tributions and unparticipating distributions. A similar framework has been used by recent literature (Yuan et al., 2021| Reisizadeh et al., 2020; Wang et al. (021). However, these works mainly focus on the optimization performance or only involve experimental results on the generalization. The objective of this work is to provide theoretical results on generalization error in this framework. Our contributions are summarized as follows.
We provide a systematic analysis of the generalization error of federated learning in the two-level framework, which captures the missed participating gap in the existing works. This two-level framework captures both heterogeneity and relatedness of clients' distribu- tions. Moreover, all learning bounds presented in this paper are in probability form instead of expectation form.
We derive fast learning rates in the empirical risk minimization setting. The unparticipating error is bounded by two terms. One is participating error. The other is the participation gap results from missing clients in the training, Our participating bounds and unparticipating bounds are of order O mm and O
m respectively.
We study the learning bounds for unbounded loss functions, including sub- gabbgaassiin, sub- exponential, and heavy-tailed losses. Small- ball methods and concentration inequalities for unbounded random variables are used in the unbounded setting. Our bounds are compara- ble with the existing results with bounded assumptions.
The rest of the paper is organized as follows. In Section 2, we describe the two-level distribution framework and provide basic theoretical results in this framework. In Section 3, we derive fast generalization bounds. In Section 4, we go beyond the bounded assumption and provide the gener- alization bounds for unbounded losses such as sub-exuuoe aubb-exonnntial and sub- Weibull losses. In Section 5, we discuss related work on the generalization analysis of heterogeneous federated learning. Finally, conclude this paper in Section 6. All proofs are postponed to the appendix.
2

---

Published as a conference paper at ICLR 2023
D
D
Client Sampling
Participation Gap!
(Client Relatedness)
D
D2
D...
Data Sampling (Data Heterogeneity)
Participating Error
8
S
S
Figure 1: Illustration of the participation gap and participation error.
TWO-LEVEL DISTRIBUTION FRAMEWORK
Let X' denote the input space and y IR the output space. For simplicity, we denote = Y) the random variable with support Z = X' x V. Let D denote the set of all probability distributions on 2 and P is veta-distribution on D. The assumption of meta-distribution is reasonable especially in cross-device federated learning scenario, where the local devices may be large population of mobile phones. As shown in Figure in this two-level distribution framework, we assume the total number of clients is M (may be infinity) and the number of clients participating in training is is worth emphasizing that M is generally larger than m owing to unreliable network connections. We denote by D; the distribution associated to client i and assume {Di.... Dm) } are independently sampled from D according to P. Data sample S, { located on participating client made of i..d realizations of following D,. The global model is trained based on { m and will be used by all M clients. Two-level distribution framework allows us to measure the performance of the global model with respect clients' distribution P. which quantifies both the participation gap (caused by client sampling) and participating error (caused by data sampling from participating distributions). Throughout the paper we denote J by F {= - E(h, h E H). Moreover, we use 7, (X,, Y,) to represent the random variables across two-level framework. That is, B[Z,] = ED EZ,,D, [.]]]
Let the hypothesis space H be family of real-valued functions defined on X. The loss function (: x + R+ a non-negative function. We denote the population risk CP () by Lp(h) ED.~P [Ez=D, [&(h(X), Y)],, where h H. represents the global hypothesis shared by all local clients. The population risk minimizer h" associated to population risk (p(h) is define as h* arg min Lr(h), However, it is impossible to minimize (r directly because the exact meta distribution and client local distributions are unknown to us. We have access to only a finite number of clients and finite training data at each client. The global objective function defined as population risk is often optimized by the form of empirical risk minimization (ERM) objective function defined as: (h) = 1 EE Σ ((h(X)), Y where (X/, represents the j-th training data the data point. Let S; = (2) )リ denotes the local training set at i-th participating client and S = S ... U. represent the global training set across all participating clients. The empirical risk minimizer condition on dataset S is define as h = arg min (h).. To analyze the generalization in our two-level framework, we further define semi-empirical distribution and the corresponding semi- empirical risk (h) by D = 1 -i=1 D, and (n(h) E Ez-D, [e(h, Z)] We extend the previous definitions and denote by ht the semi-empirical risk minimizer ht arg min LD (h).
point at i-th participating client. For simplicity, we denote Z =
The semi-excess risk for participating clients is defined as: LD( (h*). Semi-excess risk indicates the performance of the learned model fi the unseen data associated with semi-empirical distribution D. The excess risk for unparticipating clients defined as: Cr-(h) (h Excess risk indicates the performance of the learned model on the unseen clients distributed according to P. Note that the the excess risk (h) Lr(h") is defined across two-level distribution framework. It will be shown that, in analysis, all upper bound of excess risk Cr (r(h)) involves semi-
3

---

Published as a conference paper at ICLR 2023
excess risk LD(h) (h" ) or its upper bound. To understand this framework better, present our basic results excess risk as follows.
Definition 1 (VC dimension). Let (X, H) be a set system that consists of a set and a class H of subsets of X. A set system (X, H) shalters a set A if each subsel of A can be expressed as An for some h in H. The VC-dimension of is the size of the largest set shattered by H.
Definition 2 (VC subgraph of real valued function). The subgraph of a function h(E H) X - I the subset of X IR given by {xx,1) () < h(s)). Then the V C-dimension of the function class JF is defined the V CCC-iimenioon of the of subgraphs of functions in H.
Theorem (Generalization error for unparticipating clients). Let F. be a family of functions related hypothesis spuce H F = {z E(h,,) z) h H3. For the VC subgraph class F with VC dimension d. If the loss function is bounded by b, it follows that with probability at least - 25,
[m(1/8)
+ezby / bV
1n(1/5)
(h(h) Lp(1)) S 5p(1))aayy
---by bV
2mm
2m
where and 02 are constants.
Remark 1. Assume the total number of clients is M and P is a concrete meta-distribution on M different clients' distributions. The global model h is trained based on m participating clients. The excess risk measures the average performance of h on total M clients, which include participating and umparticipating clients. iinooremniidicttess that, increasing the number of participating clients m leads the decrease of excess risk (r(h) (h(h"). In cross-device federated learning, the number of participating clients m may be large enough such that the excess risk approaches zero. Based on these discussions, we can give a positive answer to the question asked in Introduction. This is, from the perspective of average performance, unparticipating clients would benefit from the model trained by participating clients.
Remark 2. Our theoretical results show that under some assumptions we are able to bound the excess risk Lr Lr(h"). In the cases when every client is completely different, Lr(h") will be large. Thus, the generalization error for unparticipating clients (h) will be large. This obser- vation indicates that, we can not expect one commen model works well when heterogeneity is high. We provide experimental results on EMINIST (Cohen et al. (017) and synthetic data in appendix. Though Theorem is derived for VC class, experiments of neural network justify our theory.
FAST LEARNING RATES IN TWO-LEVEL DISTRIBUTION FRAMEWORK
In this section, we present fast learning rates in two-level distribution framework. Recall that h is the empirical risk minimizer and h is the population risk minimizer. Our goal is to bound the semi-excess risk for participating clients (n - (D(h") and excess risk for unparticipating clients (n) (h"). To get faster learning rates in two-level distribution framework, we start by making some assumptions on loss function f, hypothesis space H. semi-empirical distribution D, and meta distribution P.
Assumption 1. Loss function e is L-Lipschitz in its first argument: |e(y1, E(yz, v) S
1y/1 y2l
Definition 3 (Bernstein condition). Let μ be distribution supported X y and let E be loss function with domain y x y. The tuple (p, e, H. h²) satisfies the (3, BBerssttn condition with parameter B > if the following holds for any h E H.
E (h(X) - (x))²² S BE (E(((h(X),)) ( (X),
well known that fast learning rates require extra assumptions. Bernstein condition widely used to get fast learning rates in the learning theory community (Xu & Zeevi 2020 van Erven et al.) 2015 Wu et al. 2022). We emphasize that is not too restrictive. For example, is directly implied by the boundedness property of functions with any probability distribution (Bartlett et al. 2004). Moreover, regression problems with strictly convex loss function satisfy the Bernstein condition if the function class is convex (Lecué & Mendelson, 2013). Other examples include excess risk functions with minimizer of population risk when the loss function is strongly convex and Lipschitz Klochkov & Zhivotovskiy 2021)
4

---

Published as a conference paper at ICLR 2023
Assumption 2. Theoretical analyses in our two-level frammennwo involve different rypes of Berssein conditons:
(a) The tuple (D,e, H, hi) satisfies the Bernstein condition with parameter B' 2 1,0 < S
1. That is, for any h E H. m. Lim E[b(X;) - h1* (x])) &
1
- Lo -
(b) The tuple (P, e, H. h²) satisfee the Bernstein condition with parameter B" 2 1,0 < 1"
1. That is. for any h E H. ED,-P(EX-D,, [h(x)- h- (X)) & ("( - (P) ))²²
For our purposes, we need to check that both (a) and (b) in Assumption 2 hold. A typical example satisfying Assumption 2 is quadratic loss with convex function class H. We provide some examples
satisfying Assumption 2 in appendix. For more details, we refer to (Xu & Zeevi 2020 Wu et al.,
2022
van Erven et al. 2015).
Assumption (Uniform entropy number Let H be family of bounded functions with uniformly entropy number log ((, H. llll. 112). Assume that there exist positive numbers ", d and p such that (c, (12) I d'log((1//) (1//c for any 0 <5-
Assumption 3 is mild assumption if the function classes are bounded. We list some popular function classes satisfying Assumption 3 (a) If the VC-dimension of H is finite, then H satisfies assumption 3 For instance, the function class of k-means methods has finite VC dimension. For
more details, we refer the reader to (Devroye et al.) 2013). (b) When we set E (0, 1), then all the unit Euclidean ball B C IRd satisfy assumption
(c) If 7 a RKHS with kernel k and the rank of
k is d, then H satisfies assumption 3
3.1 FAST LEARNING RATES FOR PARTICIPATING CLIENTS
In this subsection, we provide fast learning rates for participating clients in high probability, To obtain faster convergence rates, we focus on semi-excess risk (n) - (h)))).
Theorem 2 (Semi-excess risk for participating clients). Let F be family of functions bounded by
Under assumptions 7 3 and (a) of Assumption when mn 2 ed (mn), it follows that with
probability at least
log" (mg((m)
log (og(1/))
LD CD) c1
where 6j and 02 are constants depending on 7. P, L,, f3' and B,, respectively.
Remark 3. Theorem 2 shows that the convergence rate of semi-empirical excess risk ranges from O mmn to faster order O( (.). which corresponds to 3' = and 3 = respectively. It indicates that, under Bernstein condition, semi-empirical excess risk convergences faster when we increase the size of local dataset. We emphasize that our bounds in Theorem 2 in high probability form, which is more emergent and challenging, when compared to the previous results in expectation form (Chen el al. 2027 Fallah el al.) 2027]. The learning bounds in Theo- rem 2 are conducted for the empirical risk minimizer h. For the inexact minimizer of h, the proof technique and the final bounds only involve an extra optimization term. For more details about the optimization error, we refer to (Wang et al. 2027 Su et al. 2027 Khaled et al.) 2019)
the number of clients
3.2 FAST LEARNING RATES FOR UNPARTICIPATING CLIENTS
In this subsection we provide fast learning rates for unparticipating clients in high probability. To the best of our knowledge, this is the first result derived for unparticipating clients in heterogeneous federated learning.
3 and (b) of Assumption 2 when m 2 cd log" (mg), for any ō > O, it follows that with probability at least 1 6,
Theorem 3. Let F be a family of functtions bounded by b. Under assumptions
(lg" m
llog(1/0)
Cp(h)-Lp(h") co (CD(C) (CD(T)-Co(h)) + +1
+
m
where Co = K-37, C1 and C2 are constants depending on 7, Tr,3" and Bg, b, 3" respectively.
"The definition of uniform entropy number is provided in appendix
5

---

Published as a conference paper at ICLR 2023
Remark 4. Theorem is developed across the two-level distribution framework, which brings extra challenges to the analysis. It is shown that the upper bound derived in 3 include semi- empirical excess risk term Lp (h) (h*), which is an outcome of excess risk decomposition across two-level framework. Recall that 3' and 8" are constants defined in Assumption 2 In the cases where 3' = 1 and 3" 1, it can be shown that excess risk is of order Of + ) present Theorem [ we must construct sub-root function that links the expected local Rademacher complexity associated with meta-distribution P and uniform entropy number. However, the conventional Dudley's 's integral bounds are built under empirical construints Boucheron el al.) 2013). We tuckle this challenge by extending the techniques developed in (Lei et al. 2016) to our two-level distribution framework.
with high probability.
4 LEARNING RATES FOR
LOSSES
In this section, we provide generalization error bounds for unbounded losses in two-level distribution framework. In particular, focus loss functions satisfying sub-Weibull condition.
Definition 4 SSub-Weibull random variables). A random variable X is said to be sub- hebiill if there is constant [| < oo, such that
P( 2 1) < 2exp(- for all t 122200 2.
Sub-Gaussian and sub-exponential random variables are two special cases of Sub-Weibull random variables, which correspond to a = and a = 1, respectively.
The learning rates derived two-level framework for sub-exponential losses are deferred to the appendices. In the following use small-ball method establish learning rates for more heavy- tailed losses, where two-side concentration inequalities may fail to hold.
This subsection aims at establishing generalization bounds for unbounded losses that have heavier tails than sub-exponential distribution. Since the two side inequalities for empirical process fail to hold when the losses heavy-tailed, the analysis of heavy-tailed losses require relate empirical risk and population risk. In this subsection, we establish generalization bounds for heterogeneous federated learning by extending the small-ball method from i.i.d setting to level distribution framework. We consider the quadratic loss function in this section. The extension general losses can be achived by using the techniques presented in (Mendelson, 2018).
method to
In what follows. we denote by [[/lllzz for Banach spaces p)) Recall that D is the semi-empirical distribution and P is meta-distrriuttin. In particular, we have [| = (ED,~PEX~,, [1(X))))1/2 For the sake of clear exposition, we first introduce the small-ball condition.
>n Gi Ex=D, [ and [/alle,(0))
Assumption (Small-ball condition). Let H C (D2(D) be a closed and convex class of functions and H - H := (h W h. h H).
(a) Let Qmn(() (T) = infrEH P((((X)) 2 T]]Alle(())), where X represent the random sample at i-th participating client. There is a 2 0 for which Qua((T) > O.
(b) Let (T) inf ([E[)(X!)] sample at i-th participating client. There is 2 0 for which Qm P) 0.
(p))) where X represent the random
Assumption small-ball condition, has been assumed for i.i.d and dependent data-generating pro- cess. To obtain probbbbbbbiiityy theoretical guarantees, concentration techniques are widely used in the analysis of generalization error (Boucheron et al., 2013). Intuitively, empirical risk will con- centrate around population risk with high probability only when the loss function has well-behaved moments. However, this condition may fail to hold for heavy-tailed losses (Mendelson) 2015). As- sumption 4 appparrs first in the work of (Mendelson) 2015). Losses with any sort of moment equiv- alence satisfy small-ball condition, which weaker than concentration condition and can be used to model heavy-tailedness. For example, even weak condition || (2)() S c| cll,)),,, yields nontriv- ial small-ball estimate. Moreover, the equivalence between higher-order moments and second-order moment such as ||hll,,,p) & c|[h|] (p)))) also leads to small-ball condition (Lecué & Mendelson, 2016). Based these observations, condition (b) of Assumption
4 is generally implied when

---

Published as a conference paper at ICLR 2023
consider each local distribution D; as random variable according client distribution P. Let us discuss condition (a) of Assumption in more detail. Note that the establishment of this assumption Honly requires H. L2(D) with high probabilityy, where D is the semi-empirical distribution. This requirement is not too restrictive since the elements of D are i.i.d sampled from P. To our knowl- edge, this is the first time that small-ball condition is used under heterogeneous data generating assumption.
4
4.1 LEARNING RATES FOR PARTICIPATING CLIENTS WITH SMALL-BALL CONDITION
We first describe the basic idea of generalization analysis for participating clients. Recall that h the minimizer of coni-empirical risk (h(h) in H. In this subsection we focus on the measure ||/ ( which represents the distance between h and h with respect to semi-empirical distribution D. For quadratic loss and every h H. we have
(h) Ls(h)
(x(p)) - r!1 (x()))) xx?)²]
(1)
(h (x)))
2 e - -
(2)
mn
mm
where 5/ = =f'(x)) - Y.P Since πn is the minimizer of empirical risk (s(h), we have (s
(h() S 0. If on an event ||/- h (lz2(D) is large, then the summation of two terms in is larger than 0 with high probability. follows that with high probability ||] - 1 (L)) small since (h) (s())) S O.
(m..)) Let ((X), (D), Bay (1.1) be global data samples whose elements {(X}, y are i.d ran- dom pairs at i-th client. The analysis of the first term in 2 involves the following definition of Rademacher complexity.
Definition 5. We define H. 71- = {h- W h, E H} and denote by B the L2(D) unit ball
entered at hi, that is By = (h E H: 11h hr (Z2D) I 1]. For every 17 > 0, define
Wmn (n)) = inf > E:
sup NE(H- B
((((3))
$ _no
mn
where of are Rademacher random variables.
The quantity wma(1) measures the Rademcher complexity of the localized function set (H - H n sBr ). Note that Wmn (17) depends only on the hypothesis class H and global input samples are drawn from semi- cani-emprrical distribution D.
Theorem 4. Fix T > for which Qm (2T) > O and set 1j < m2 If every random variable v (x() E(g/h(X()) for all h E H. - h is Sub- Weibull. For sufficiently large mn, with probability at least 1 - 8mn exp (-mmQqau (2r)/2) one has
h 7 (L<((D) 2 max Wmm (TQma (2T)/16) (mm) 1tc
where 0
1/2 and 8mn expl- Em Ej=n V (aX...)sst..))sm...) V?
0177 (m)))+
ezn" (1mn)o(1/242))
}}
Remark 5. To the best of our knowledge, Theorem Aprovides the first result on the generalization error of heterogeneous federated learning with heavy-tailed losses. It suggests that both hypothe- sis 'size' and noise level play important roles in the generalization error of heterogeneous learning problems. In Theorem 4 the expression of 6mm dependents on the tail of sub- Weibull random vari- ables V?J Specificcl the heavier the tail of V? the larger 8mm will be. Note that in addition to IIV? llv., , 8mn also depends on (mm)) 4s, That is, the larger mn and i are, the smaller 8mn will be. To ensure that Theorem f holds with high probability, we must ensure that 8mm is small enough. Therefore, when mn is fixed, the heavier the tail of V²2 the larger should be. It can be seen from Theorem 4 that the larger is, the slower the convergence rate of 1 hh" L2)( is.
7

---

Published as a conference paper at ICLR 2023
4 for coovee class H. and sufficiently large mn, with probability at least 6mn exp ( one has
Corollary 1.
Under the same conditions of Theorem
T² --20 Qm Qm max (w (mQmmm(2))/BB)) 4
-n) - Ln) s (2+
where < <66
Remark 6. Corollary 7 provides the convergence rate of semi-empirical excess risk for Sub- Lab-Weibull losses. Compared to Theorem 2 it shows that the convergence rate of excess risk is slower than Vmn
(
4.2 LEARNING RATES FOR UNPARTICIPATING CLIENTS WITH SMALL-BALL CONDITION
In the analysis of generalization error for unparticipating clients, we focus on the measure ||/- ht ppy which represents the distance between h and hs with respect to meta-distribution P. The analysis of generalization error for unparticipating clients follows similar path the previous anal- ysis. Let {(x; Y be dataset whose elements are sampled across the two-level framework, that (X, YJ] = (X. [(X,, Y.)]. We present the different definitions of Rademacher complexity terms in the following.
Definition define H H = {h N1 h, E H} and denote by B2 the Lz(P) unit ball
entered at h². For every 1j > O, define
wm(()) == inf 8 8> O:
sup MECH RDnuB2
Σ ax.((.))
178,
where a, are Rademacher random variables.
The quantity wma (m)()) measures the localized complexity of {(H - H) 0 (sB2).
Theorem S. Fix > 0 for which Qm (2T) > O and set 1 < 72Q the random variable V; = h probability at least 8m cxp (- ( (2T) one has
for all h E H - h² [X,) is hub-Weibull. For sufficiently large m, with
(2T) <2mmm((2))))
I1h ht" (1L((P))) S 2 max Wm (m
where 0 < < and 6m = exp(-(1 m
mAXIgiS M }}
m2 2:)
Remark 7. Theorem Theovempproovide the first result on the generalization error of unparticipating clients heterogeneous federated learning with heavy-tailed losses.
Corollary 2. Assume for all E H -Tt the random variable V (X]))
Sub-
Weibull and the noise h² (X;) Y, independent of Xt. Under the same conditions of Theorem 5 for 0 17 < and sufficiently large mn, with probability at least 1 8' exp (-mnQ ) exp (-mQ? (27))/2 /2) one has
(h) - Lp(h") S max (W 7 (mmm(27)
), (mm) + max
w T mmm(TT]
) m 3
16
16
where =
<<<<<> and 8' = 8m + 8m + exp( 2_ 1-m
C. E
maxisism V }
can c (1l (1/2)))
in
Remark 8. Corollary 2 provides the convergence rate of excess risk for bub-Weibull losses. Com- pared to Theorem it shows that the convergence rate of excess risk is slower than O (tam vm L))
RELATED WORK
Generalization Error for Heterogeneous Federated Learning. Several attempts have been made in the analysis of generalization error for heterogeneous federated learning. We compare our results with most related works Table Complexity-bane bounds for participating clients are derived in the work of (Mohri et al. 2019) who present high probability slow rates of order O mm
8

---

Published as a conference paper at ICLR 2023
Generalization Bounds for Heterogeneous Federated Learning. SC, Pro, and Exp denote Strong convexity, In probability, and In expectation. Sub-expon denotes sub-exponential.
Table 1:
Reference
Loss
Assumption
Part
Unpart
Type
Mohri et al.
2019)
Bounded
Bi-Classifier
O Vmnn
Pro
Chen et al.
2021
Bounded
Smooth, SC
O
1 man
Exp
Fallah et al.
2021
Bounded
Smooth, SC
O min
Exp
Our Results
Sub-expon
Lipschitz
1 V/mr
0
1
Pro
Vmn
vm
Our Results
Bounded
Bernstein Con
I
0
1
Pro
Our Results
Sub-Weibull
Small-ball
O 2
(mn)
((mm)
2
2
Pro
for bounded losses. Fast rates bounds are obtained based on stability tools in (Chen et al. 2021 Fallah al. 202T). However, their results are in expectation form. Among the existing theoretical work, different measurements are used to model the heterogeneity of local distributions. These measurements include gradient dissimilarity and parameter dissimilarity of local optimal models. Here we argue that it is more natural to make assumption from the perspective of the data- generating process. Therefore, in this paper, we assume that the local distributions are sampled from higher meta- distribbitiii..nn..
A similar two-level distribution framework has been used the analysis meta-lcarning. However, the learning scenarios and objectives of federated learning different from that of meta-learning. The goal meta-learning is to choose an optimal hypothesis space H from the hypothesis space family H. Ideally, the chosen hypothesis H. should contain good hypothesis tribution D, sampled from the meta distribution P. In this paper, we focus on the performance of common model h trained by participating clients. The performance of the common model is mea- sured by the population risk with respect to meta distribution P. Another line of research closely related to heterogeneous federated learning is domain addetaaioongeneraaiizaiion In this line, possi- bly the results
H for each dis-
(Li et al. 2022) are most relevant to ours.
Generalization error for Unbounded losses. The unbounded assumption brings two major chal- lenges to complexity-base ities do not hold when the losses are heavy-tailed. The other is that the standard techniques used to upper bound the complexity of hypothesis space are developed for bounded losses. The straight- forward way avoid these two challenges is to assume there exists envelope function with respect to the underlying distribution and hypothesis class (Adamczak) 2008) Lecué & Mendelson, 2012). Small-ball method is first proposed to replace the concentration tools for empirical process in (Mendelson, 2015) and further developed in (Mendelson) 2018). Inspired by the small- method, Offset Rademacher complexity -based method provides another replacement for two-side concentration inequality (Liang et al.) 2015). However, most existing generalization bounds for unbounded losses are derived the i.i.d setting. [Roy et al. (202T) extend the small-ball method in the dependent data setting. In this paper, we focus on the heterogeneous federated learning scenario with unbounded losses, where the samples are independent but non- con-identically distributed.
generalization analysis. One is that the two-side concentration inequal-
CONCLUSION
We present a systematic generalization analysis of heterogeneous distributed learning. Our analysis captures the generalization performance of the learned model on both participating and unparticipat- ing clients. To our knowledge, this is the first theoretical analysis under the assumption that the local distributions sampled from meta-distribution. We recover the current state of art guarantees without using bounded assumptions. Moreover, under the empirical risk minimization setting, we derive fast generalization rates in our two-level distribution setting.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENTS
We appreciate all the anonymous reviewers for their insightful and constructive comments, espe- cially one reviewer's 's suggestion add more discussion and explanation. This work is supported by National Natural Science Foundation of China NO. 62076234; the Beijing Natural Science Founda- tion No. 4222029: the Intelligent Social Governance Interdisciplinary Platform, Major Innovation & Planning Interdisciplinary Platform for the "Double-Fine First Class" Initiative, Renmin University of China; the Beijing Outstanding Young Scientist Program NO. BBJWZYYHH12019100000
the Beijing Key Laboratory of Big Data Management and Analysis Methods, Gaoling School of Artifi- cial Intelligence, Renmin University of China, Beijing 100872, China; the Public Computing Cloud, Renmin University of China; the Fundamental Research Funds for the Central Universities, and the Research Funds Renmin University China NO. 202 2021030199; the Huawei-Remmin University joint program on Information Retrieval; the Unicom Innovation Ecological Cooperation Plan; and the CCF-Huawei Populus Grove Fund.
REFERENCES
Radoslaw Adamezak. A tail inequality for suprema of unbounded empirical processes with applica- tions to markov chains. Electronic Journal of Probability, 13:1000-1033 2008.
Ingerman Alex and Ostrowski Krzys. Introducing tensorflow federated. 2019.
L. Barnes, Alex Dytso, and H. Vincent Poor. Improved information theoretic generalization
bounds for distributed and federated learning. In IEEE International Symposium Information Theory, ISIT 2022, Espoo, Finland, June July I, 2022, pp. 1465-1470. IEEE, 2022. doi: 10. WWWII/TT50566222229933344 URL /ooiiiiiooo org 10 1109 1w..0//SSSS555556600 2022. 9834700
Peter L Bartlett, Shahar Mendelson, and Petra Philips. Local complexities for empirical risk minimization. International Conference on Computational Learning Theory, pp. 270-284. Springer, 2004.
Peter I. Bartlett, Olivier Bousquet, and Shahar Mendelson. Local rademacher complexities. The Annals of Statistics, 199-)57497- 2005.
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities: nonasymp-
totic theory of independence. Oxford university press, 2013.
Shuxiao Chen, Qinqing Zheng, Qi Long, and Weijie Su. A theorem of the alternative for person- alized federated learning. arXiv preprint arXiv:2103.01900) 2021.
Gregory Cohen, Saeed Afshar, Jonathan Tapson, and Andre Van Schaik. Emnist: Extending mnist to handwritten letters. In 2017 international joint conference on neural networks (IJCN), pp-
IEEE, 2017.
Lue Devroye, László Györfi, and Gábor Lugosi. A probabilistic theory of pattern recognition, vol- ume 31. Springer Science & Business Media, 2013.
Richard M Dudley. Central limit theorems for empirical measures. The Annals of Probability, pp- 899-929, 1978.
Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. Generalization of model-agnostic meta- learning algorithms: Recurring and unseen tasks. Advances Neural Information Processing Systems, 34:5469-5480, 2021.
David Haussler. Decision theoretic generalizations of the pac model for neural net and other learning applications. The Mathematics of Generalization, pp. 37-116. CRC Press, 2018.
Miao Hu. Di Wu, Yipeng Zhou, Xu Chen, and Min Chen. Incentive-awant autonomous client participation in federated learning. JEEE Transactions on Parallel and Distributed Systems, 33 (10):2612-2627, 2022.
10

---

Published as a conference paper at ICLR 2023
Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista A. Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. L. D'Oliveira, Hubert Eichner, Salim El Rouayheb, David Evans, Josh Gardner, Zachary Gar- rett, Adrià Gascón, Badih Ghazi, Phillip B. Gibhons, Marco Gruteser, Zaïd Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konečný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateck Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Hang Qi. Daniel Ramage, Ramesh Raskar, Mariana Raykova, Dawn Song, Weikang Song, Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramèr, Praneeth Vepakomma, Jianyu Wang. Li Xiong. Zheng Xu, Qiang Yang, Felix X. Yu, Han Yu, and Sen Zhao. Advances and open problems in federated learning. Found. Trends Mach, Learn. 14(1-2):1-210 2021. doi: 10. 10.1561/220000008 URL wtttts:://oi...... 10. 0et.l.16112220000 022212000000033
Varun Kanade, Patrick Rebeschini, and Tomas Vaskevicius. Exponential tail local rademacher complexity risk bounds without the bernstein condition. CoRR, 01122022.1146,,, 2022. URL
org/ 2200 11461
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference on Machine Learning, pp. 5132-5143, PMLR, 2020.
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. First analysis of local gd on hetero- geneous data. arXiv preprint arXiv: D.XXiv1909.04715: 2019.
Yegor Klochkov and Nikita Zhivotovskiy. Stability and deviation optimal risk bounds with convergence rate So(1/n)S. In Marc' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang and Jennifer Wortman Vaughan (eds.), Advances in Neural In- formation Processing Systems 34: Anmual Conference on Neural Information Pro- cessing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pp. 5065- 5076, 2021. URL
cc//paper/222/hhatt/ 26677633222e0ee552222211118 http://ssttatttttttttttt.ttttt html
Abstract
Arun Kuchibhotla and Rohit K Patra. On least squares estimation under heteroscedastic and heavy-tailed errors. The Annals Statistics, 50(1):277-333) 2022.
Arun Kumar Kuchibhotla and Abhishek Chakrabortty. Moving beyond sub-gaussianity in high- dimensional statistics: Applications in covariance estimation and linear regression. arXiv preprint arXiv:1804.02605. 2018
Guillaume Lecué and Shahar Mendelson. General nonexact oracle inequalities for classes with subexponential envelope. The Annals of Statistics, 40(2):832-86) 2012.
Guillaume Lecué and Shahar Mendelson. Learning subgaussian classes: upper and minimax bounds (2013). Topics in Learning Theory-Societe Mathematique de France, Boucheron and N. Vayatis Eds.), 2013.
Guillaume Lecué and Shahar Mendelson. Performance of empirical risk minimization in linear aggregation. Bernoulli, 1203311500-1544 2016.
Yunwen Lei, Lixin Ding, and Yingzhou Bi. Local rademacher complexity bounds based on covering numbers. Neurocomputing. 218:320-330, 2016.
Da Li, Henry Gouk, and Timothy Hospedales. Finding lost dg: Explaining domain generalization via model complexity, arXiv preprint 2221v:2202.00563, 2022.
Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Challenges, methods, and future directions. IEEE Signal Process. Mag., 37(3):50 60, 2020a. doi: 10.1 109/ MSP.2020.2975749. URL https: doi. org/ 10. 1109 /SPP .2055...220 0000022000 2975749
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. Proceedings of Machine Learning and Sys- fems, 45429-450, 2020b.
11

---

Published as a conference paper at ICLR 2023
Tengyuan Liang, Alexander Rakhlin, and Karthik Sridharan. Learning with square loss: Localiza- tion through offset rademacher complexity. In Conference on Learning Theory, pp. 1260-1285. PMLR. 2015.
Mohammad Saeed Masiha, Amin Gohari, Mohammad Hossein Yassaee, and Mohammad Reza Aref. Learning under distribution mismatch and model misspecification, In IEEE International Sympo- sium on Information Theory, ISIT 2021, Melbourne, Australia, July 12-20, 2021, pp. 2912 2917. IEEE, 2021. doi: 10. 10.10999SSST45574.22201191777779
URL /ttp://::///.i..//..///00/// 1109/
ISTT451 74. 2021 7517732
Andreas Maurer and Massimiliano Pontil. Concentration inequalities under sub-gaussian and sub- exponential conditions. Advances in Neural Information Processing Systems, 34:7588-7597, 2021.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-efficiee learning deep networks from decentralized data. In Artificial intelli- gence and statistics, pp. 1273-1282. PMLR, 2017.
Shahar Mendelson. Learning without concentration. Journal of the ACM (JACM), 62(3):1-25,
Shahar Mendelson. Learning without concentration for general loss functions. Probability Theory and Related Fields, 171(1):459-555 502, 2018.
Konstantin Mishchenko, Grigory Malinovsky. Sebastian Stich, and Peter Richtárik.
Proxskip: Yes!
local gradient steps provably lead to communication accelcration! finally! arXiv preprint NtV.:2002.0357., 2022.
Aritra Mitra, Rayana Jaafar, George J Pappas, and Hamed Hassani. Linear convergence in federated learning: Tackling client heterogeneity and sparse gradients. Advances in Neural Information Processing Systems, 34:14606-14619, 2021.
Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. In Interna- tional Conference on Machine Learning, pp. 4615-4625. PMLR, 2019.
Debolina Paul, Saptarshi Chakraborty, Swagatam Das, and Jason Xu. Uniform concentration bounds toward unified framework for robust clustering. Advances in Neural Information Processing Systems, 34:8307-8319 2021.
David Pollard. Convergence of stochastic processes. Springer Science & Business Media, 2012.
Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and H Brendan McMahan. Adaptive federated optimization. arXiv preprint arXiv:2003.00295, 2020.
Amirhossein Reisizadeh, Farzan Farnia, Ramtin Pedarsani, and Ali Jadbabaie. Robust federated learning: The case of affine distribution shifts. Advances in Neural Information Processing Sys- tems, 33:21554-21565, 2020.
Abhishek Roy, Krishnakumar Balasubramanian, and Murat A Erdogdu. On empirical risk minimiza- tion with dependent and heavy-tailed data. Advances in Neural Information Processing Systems, 34:8913 8926, 2021.
Milad Sefidgaran, Romain Chor, and Abdellatif Zaidi. Rate-distortion theoretic bounds on general- ization error for distributed learning. CoRR, abs/2206.02604, 2022a. doi: 10.485500arXiv.22066 02604. URL htt.t::t////////t org/10 485544 2206. 02604
Milad Sefidgaran, Romain Chor, and Abdellatif Zaidi. Rate-distortion theoretic bounds on general- ization error for distributed learning, arXiv preprint arXiv:2206.02604 2022b.
Lili Su, Jiaming Xu, and Pengkun Yang. Achieving statistical optimality of federated learning: Beyond stationary points. arXiv preprint 1rXiv:2106.15221 2021.
Aad W. der Vaart and Jon A. Wellner. Weak Convergence, pp. 16-28. Springer New York,
New York, NY, 1996. ISBN 978-1-4757-2245-2- 1007
doi: 10. 11111//97771--477-55555555 3. URL
12

---

Published as a conference paper at ICLR 2023
Tim van Erven, Peter D. Grünwald, Nishant A. Mehta, Mark D. Reid, and Robert C. Williamson. Fast rates in statistical and online learning. CoRR, /aw/100700259, 2015. URL http:
Adithya Vellal, Saptarshi Chakraborty, and Jason Q Xu. Bregman power k-means for clustering exponential family data. In International Conference on Machine Learning, pp. 22103-22119,
PMLR, 2022.
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 feder- ated optimization. arXiv preprint arXiv:2 069777 2021.
Xuetong Wu, Jonathan H Manton, Uwe Aickelin, and Jingge Zhu. Fast rate generalization error bounds: Variations theme. arXiv preprint 2205::2200003331,,, 2022.
Jie Xu and Heqiang Wang. Client selection and bandwidth allocation in wireless federated learning networks: A long-term perspective. IEEE Transactions on Wireless Communications, 20(2): 1188 1200, 2020.
Yunbei Xu and Zeevi. Towards problem--dpenndnt optimal learning rates. Advances Neural Information Processing Systems, 33:2196-2200 2020.
Howard H Yang, Ahmed Arafa, Tony QS Quek, and H Vincent Poor. Age-based scheduling pol- icy for federated learning in mobile edge networks. ICASSP 2020-2020 IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP), pp. 8743-8747. IEEE, 2020.
Niloofar Yousefi, Yunwen Lei, Marius Kloft, Mansooreh Mollaghasemi, and Georgios C Anagnos- topoulos. Local rademacher complexity-base -based learning guarantees for multi-task leamiig. The Journal of Machine Learning Research, 19(1): 1385):3881133,, 2018.
Honglin Yuan, Warren Morningstar, Lin Ning, and Karan Singhal. What we mean by generaliza- tion in federated learning? arXiv preprint arX1v:2110.12216, 2021.
Chulhee Yun, Shashank Rajput, and Suvrit Sra. Minibatch local SGD with shuffling: Tight convergence bounds and beyond. In The Tenth International Conference on Learning Represen- tations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022. URL https: wwBp
//openzeview.
Huiming Zhang and Haoyu Wei. Sharper sub-weibull concentrations. Mathematics, 10(13):2252, 2022.
Lijun Zhang and Zhi-Hua Zhou. l-rrgression with heavy-tailed distributions. Advances in Neural Information Processing Systems, 31, 2018.
13

---

Published as a conference paper at ICLR 2023
CONTENTS
Introduction
2
Two-level Distributin Framework
3
Fast Learning Rates in Two-level Distribution Framework
Fast Learning rates for participating clients
3.2
Fast Learning rates for unparticipating clients
4
Learning Rates for Sub- Weibull Losses
4.1
Learning rates for participating clients with small-ball condition
4.2
Learning rates for unparticipating clients with small ball condition
8
5
Related Work
6 Conclusion
Setting, definitions
15
B Proof of Theorem
15
B. Proof of Theorem
15
Proofs of fast rates with bounded losses
19
Examples Satislying Assumplion
19
C.I.I Example
19
C.1.2 Example 2
20
2 Proof of Theorem
21
3 Proof of Theorem
25
D Proofs of the results with sub-exponential losses
27
D.I Learning Rates for Sub-exponential Losses
27
Proofs of Small-ball based Method
31
of Theorem
Proof of Theorem
36
Experimental Results
40
Convolutional Neural Networks for EMNIST Task
40
:22
Federated Linear Regression with Synthetic Data
41
14

---

Published as a conference paper at ICLR 2023
A SETTING, DEFINITIONS
We denote the population risk Lr(h) by
Cp(h) EDOP DE [((h(X).
where h H represents the global hypothesis shared by all local clients, L x y - R is the non-negative loss function. The population risk minimizer h define as
h arg min CP
NEN
In practice, the global objective function is often optimized by the form of empirical risk minimiza- tion (ERM) objective function, which is defined as:
m
Cs(h)
((()))
where (X² Y?) represents the j-th training data point at i-th participating client. We also use Z = (X,, Y to denote the data point. Let S; = { }リ= denotes the local training set i-th participating client and S S; U.... U.S.S Sm the global training set. The empirical risk minimizer 7. is define as
h arg min (h) NER
The semi-empirical distribution D is defined as D = 1 D -i=1 Dj. Moreover, the corresponding semi-empirical risk (h) is defined as:
(D(h) Ez [E(h, Z))
We denote by h the semi- remi-empirical risk minimizer
h arg min (h).
kCH
The semi-excess risk for participating clients is defined as:
Lo (h) (h()).
Semi-excess risk indicates the performance of the learned model h on the participating clients. The excess risk for unparticipating clients is defined as:
(r( (r(h)).
Excess risk indicates the performance of the learned model h the unparticipating clients.
In the following, we denote F by F= represent the random variables across two-level framework. That is,
= {z + E(h, 2) h E H}. Moreover, we use Z; = (X,, Y2) to
E|Z| = ED.~P [2,,D,
B PROOF OF THEOREM
B. PROOF OF THEOREM I
We first show that semi-excess risk (n(h) Ln(hh)) can be upper bounded by supremum of the empirical process indexed by H:
(D(h) LD < CD - (s()) (ht) - (T( s sup (hD(h) (s()),, (3)
heht
where the first inequality follows from the fact that i is the empirical minimizer.
15

---

Published as a conference paper at ICLR 2023
Next, decompose excess risk (h) Lp(h") ) in two-level framework:
Cp(h) -pp(h() - sup
[p((h) - (b(h)) + sup bcH
(LD(h) Cs(h))
hER
In details:
Cp(h) Cp(h") Lp(h) Cp(h") (Cs(h) Cs(h'))
Cp(h) (D) + CD(h²) Lp(h") + LD (ss)) Ls(h") -
sup {1Cp(h) CD(h)) +2 + {1C Cs(h)l}
BER
NEH
where the first inequality uses (h) Ls(h*) S 0 since is the minimizer of (s))). Note that the first term supжcи [Lp(h) - (h) in the upper bound of excess risk quantifies the participation gap. The second term SuPдEи (h) (h))) quantifies the generalization error for participating clients.
first provide theoretical bounds on the term Sリрдеи (LD(h) - Ch()). Then we move to the participating gap supлeи (Cp(h) - (f))-
Based these observations,
Let a {or be(m).jemmm be a collection of independent Rademacher variables, this is random variables taking values uniformly in [+1,-1) -1). We define the generalized rademacher complex- ity Rmn (F) used in heterogeneous federated learning as follows:
Rmn (F) =
sup hEH
Σ ofe(h, Z() 1=1
Lemma (Generalization error for participating clinets), Let F be a family of functions related to hypothesis space H == {2 E(h, h E H}. Assume that loss function é is bounded by M. Then, for any 2 with probability least 1 8. have
In(1/8)
sup (h) - (1)) < 2R (F) + +M NEH
2mn
Lemma 1 provide high probability theoretical guarantees for participating clients under bounded assumption. Compared to the classical i.i.d setting in learning theory, the results in Lemma in under independent but non-identically distributed setting.
Since each local distribution D; is sampled independently from P. we regard local population risk [EEzD, D. [e(h, 1em a collection iid random variables. Let {ar (o:)emm)) be a collection of independent Rademacher variables, the rademacher complexity used in the analysis of participating gap is defined as:
1
Rm (F)
E Di. DD
sup hET 2=1
Σ o B.EEZD 18(1, Z)]
Lemma 2 (Participation gap). Let F. be a family of functions related to hypothesis space H. F = (z E(h, 2) H). Assume that loss function bounded by Then, for any "2 with probability at least - 8. we have
sup (h)))- LD(A)) < (R) + 3by (nn(1/)) New
2m
The participation gap in Lemma 2 quantifies the error caused by missing clients during training. The Rademacher complexity term RR, (F) indicates the "size" of hypothesis class, which can be future bounded by convering number VC dimension of the choosen hypothesis.
PROOF OF LEMMA
Proof. We first create sample set S' from S by changing one sample point. Without loss gener- ality, assume the data point Zk in S is changed into 7.kk Next we define +(S) by +(S)
16

---

Published as a conference paper at ICLR 2023
SUPNEH (h) Ls(h) By the definition of 5' and S, we have
((S)
sup (|Cn(1i) - (h)]3 - sup bER
(L) - (1)B
heR
S
sup (1 (1i) - -isr - -(CD(h)) -Ls(h))) 13
hER
1 sup /e (h, 2,) - (h, Z I.
sup (ICs(h) L.s (ss((h))3 mn hEH NEW
By assuming that loss function e is bounded by b, then we have $ (5") +( ك ط We apply McDiarmid's inequality and obtain, for any fixed E (0, 1), it follows that with probability at least 1 1-8 6
[*() bV ln(2/0)
(S)
S
E
SL.
2mn
Next we consider the expectation of (S)). By symmetrization, we have
E [+(S]]
=
E
sup
(h) - (t)
S
$1.7
LhE
e(h, 2/)) )
1
1 Σ
E
sup hEH
EzzD (e(h, 2)]
t=1
j=1
E
sup
1
E
Σ
((hh, ((hh - E(h, 221)
S1. .m
NEH
81
S
1=1
j=1
1
E(h, z(²) - E(h, (210222
E
sup
S S.
NEW m
n
i=1
j=l
m
n Jsj
e(h, 211)
E
sup
S
NEW
mn
j=1j=1
T
n
O5 - E(h,, (e(, 231)
E
sup
S
NEW mn
S S
j=1
0
m
Biy ongelhh 2()
sup
8 St.
hEH mn
i=1 1=1
m sup
+ S1 S1,-",Sm.o
- 2
NEH mn
j=l
1 n m
2 E
sup
Jrj (b, zt)
ST .. Sm.
NEW mn
== | (F)
2 E St, Sm
where Ron (F) E supREh mn E Ey Ch, z²)] Replacing one data point of S
b. S:U... make Rmn (F) vary at most u.. then applying McDiarmid's incquality again, with probability least 1 we have
In(2/8)
RRmm (F) S Rmn (F)+ + bV 2mn
S,.
17

---

Published as a conference paper at ICLR 2023
PROOF OF LEMMA 2
We create distributions set D' from D by changing one client distribution. With- out loss generality, assume the k-th D3 in D is changed into D2 then define (D) by
Proof of Lemma 2
T = sup Lr(h) (D()).
AEH
From the definition of D' and D, we have
4 (D') (D)
sup (Cp(h) (b)( - sup {Cp(h) CD(h))
kEw
DER
sup (1Cp(h) CD. (Cp(h) - (b)))}
hEW
1 sup (CD(h) - (b)( = sup hEH
(EzDD. [e(h, 2)] - Bz (1h,, 211)
NEM
By assuming that loss function f is bounded by b. then we have $ (D") +(D) < A. According
to McDiarmid's inequality, for all d E (0, 1), with probability at least 1 - 6, we have
In(2/8)
(DD) S E
[()]] bV
D. mm
2m
Now deal with the expectation of (D). By symmetrization, we have
E [+(D]]
E
sup Cp(h) LD((1)
D Dm
DEE
sup (E pm LEH
Di... Dm
sup (LD -Lo(hi)
E
D Dm
Di. D'
(CD((h) (o,((a)) (C)(()))Co
sup NEw m
Dr.
D D'm
as (LD;(h) - (1)
sup
Di.n,Dm Di. D'm
NEW m iml
E Di. Di.r.,Dm.a Dm.a
sup
1
o, LD (h)
+
Dg. E
sup
Σ 1=1
m
0, LDLDD (h)
beh m
D
1=1
2
E
sup NEW
ozLD, (1)
D D
Thus, we have
1 m
E
[DD)
sup heи m
Σ (1)
Dr. Dm
Dr. Dm.o Di...,Dm..
m J, D. (e(h, 2:)]
sup NEW m
Di. Dm..o Di...,Dm.o
1 m
E 5 ZL,.. 2m.
sup kEH m
Σ oi [e(h, Z+)]
E
Rm(C)
2 .. Zi
18

---

Published as a conference paper at ICLR 2023
where Ry (C)
E supnex E oze(h, Z.)]- Replacing one point of Z {Z make
Rm (C) vary at most we have
then applying McDiarmid's inequality again, with probability at least m
In(2/5)
E 2 2m
RRm (m)(C)] S R. (C) + bV 2m
The goal of Theorem is to present theoretical bounds of excess risk Lp Lp(h"), ), has been
shown that excess risk can be bounded by participation gap suP (|Cr(h) LD (D)()) and partic- ipating error suPseh (h)
(h)b) To show the explicit form the rademacher complexity we take VC class an example.
terms Lemmal I
and Lemmal
PROOF THEOREM
Proof. We use subgraph dimension(aka pseudo dimension) and Dudley's theorem to bound the empirical rademacher complexity (H)). According Dudley/ (1978): Pollard (2012): Haus- sler (2018). the uniform matric entropy of real valued function class JF with subgraph dimension VC d can bounded
log (c, 11- & cd (1/c).
where F is the envolop function of F. Then by Dudley's Theorem (Dudley 1978 van der Vaart & Wellner 1996). have
d (m)(F) dbv m
d
Rmn (F) S dby
mn' and
Combining the results of Lemma
leads to the final results.
C PROOFS OF FAST RATES WITH BOUNDED LOSSES
Covering number can be used give tighter estimate on the hypothesis size. Here we provide the definition of convering number and uniform entropy number.
Definition 7 (Convering number). Let (g, p) be a metric space and F F For any E 2 0, F. is an e-cover of F with respect of if for all f F, can find f Fe such that p(f. S The covering number (,,FF.p) is defined as the minimum size of an c-cover:
N(e == min([Fel: ; F, is an e-cover of F w.r. p}.
Definition 8 (Uniform entropy number). The entropy number is defined as the logaritium of the covering number. Let (G. p) be a normed space with p(f.f') 11,f- [ Let F be an envelope function of F such that [s() < F(Z), for all Z and f. We further define uniform entropy number of F as: (e, measures with S QF22 < co.
(12) = supo log (e, - where Q is taken over all probability
Definition 9. A function v(r) (0, oo) 00) is sub-root function if is nondecreasing and r + p /r is nonincreasing for > 0.
C.1 EXAMPLES SATISFYING ASSUMPTION
C.1.1 EXAMPLE
In this subsection, we show that when the hypothesis class contains the 7i* and ht,, Assumption holds.
E [(h((),))) ((),
m
E
(((x)))xx+9) (h (X+) -x,))x
(XYY>
m
2
E [((x))= - -xx(x))
19

---

Published as a conference paper at ICLR 2023
Next show that
E (X -16())))))
1
E ( - (x,) x2
[Mxx:))T=(x11)) -xx)))
Thus, if h- E H. we have
E (x-))
-
< E [(x)) - (xx:))=
L
2 (X,Y)~
(e(h(x),)) - (x),
Thus, the tuple Hi,
H, hi
satisfies the Bernstein condition with parameter B2 such that
Σ B -xx
B2 E -
Similarly, we can prove that
E - = (²B(M(X))A((XX)))
= P'Bxxx---(((((),, (X), Y)].
Thus, the tuple (P, h²) satisfies the Bernstein condition with parameter B1 = 1 such that
E(A(X,) - 11" (x,))) BBBxxx))(((( (000))-((--00000 (X),
C.1.2 EXAMPLE 2
In this example, we show that even when the hypothesis class does not include h and h² As- sumption still holds. If F is a nonempty, closed and convex subset of Hilbert space with inner product
(f.g) (xx))=o((((x)))(xx,,,
where h is the projection of Y in the space F. By the definition we have (Y - (x))
hx(x)) $ 0.
E (ax=:)((((T,)))30000,,000
e(x E(XYID - M(x))² (8 -( -
= [(((X) - (x)) + + (x))
1.2
E [(X!) - (x;)))
Thus, for regression problems with square loss function, where (ht $ H), we have
- - (x),
E (X,Y)D
L
E [xxx)) - - [xx))]
m
i=1
L E (e(l((),)) ((Ti -
(
Similarly, we can prove that
-(B -x((((x) -,
20

---

Published as a conference paper at ICLR 2023
C.2 PROOF OF THEOREM
Lemma (Theorem 2.1 in (Bartlett et al. 2005)). Let be a family of functions satisfying Vf E F, E (z() S b. If fur #. 2i=1 E [Z,)] r, then, for any ó 2 0 and any 0, with probability al least 1 5,
2r 1r(((1/))
(1 3
bln(1/6)
sup fET
[[)( f(2,)) 2 + (a)((Rm(()) (F)) +
+
m
m
a
m
where Rm (F) su 1 m E oz.)
Lemma 4 (Theorem I in (Yousefi et al. 2018). Let F be family of functions satisfying Vf e F, P. E 2,1f(Z)) & b. sf E Ej=1 E[f S r, then, for any 8 2 0 and any
2 0, with probability at least 6,
- - [(23)]
111/(1 mn
(1 1+
2 a
4b (1100) mn
sup JCP
2(1 + [a)
m
where Rmn (H) = E SEF mn E. i 1j=1 of T(
Lemma 5 (Lemma B.1 in YYuueef et al. 2018). Let c1, > 0 and 8 > q O. Then the equation x= C139 C2 has a unique positive solution To satisfying
8C2
To S
Ci
Moreover, for any x 2 To. we have x² 2 c,2 + Cz.
Lemma 6 (Corollary 1 in Lei et al. (0066). Let F be a function class with sup su ll I b. Assume that there exist three positive numbers 7, d. p such that log N (e, (1la) S d dlog (7/E) for any O < S 7, then for any 0 < S 72 and n 2 7- there holds that
ER, (fEF: Pf sr] < c(b,p.)) 7) min [(v
d dllog" (2
dr log" (2yr- 1/2)
dlog (2mm1/2)
rd log (2)
Proof of Theorem
First we define
(X,Y) + ((1(x), (() EHH.
Step One:
Combining Assumption
(a) for any f E F we derive that
E
m
m 1
[x(x)) - 7 (xx))]
m
Σ B'T
E
Let V(f) = 1 Σm [(MMx)),x)) {, B BB
m
Consider the function class G, associated with F and r 2 0:
9, = 9= max(r, v(1) ((x(),V(I)) 1 fEA
rf
21

---

Published as a conference paper at ICLR 2023
We denote V by
m
V
Blo(Z,)]
-
sup gEs,
min
i=1 j=1
Let K> 1,0 < 1 1 and B 2 1. We first prove that, if Vi+ -
111
BK then
Vf m
Σ
m
[[((Z))
K
m
[((2)]
+
-1/0
(4)
(m - B)
K
==1
If V r, then g= = f. It follows that with the assumption V S rl/a
BK we have
m Σ
m
rl/3
mn E[f(Z!)
[(2))] +
(5)
m
BK
j=1
m
+ 1/3
[1(22)
(6)
(mm)(K- - 3) i=1
K
If V 2 r, then g- =rr/V(J). It follows that with the assumption V,+
S
12/8 BK we have
1 Σ
1
[(Z))] + rd=(((f)
mn
BK
+ -
(1 m
[((2)]]
Σ B(f(Z)1)
(8)
mn j=
K
B 1 m
(1 9)r
ΣΣ
[[())]
Σ
[[((Z))]
+
mn
K m
K
==
where the second inequality follows from Bernstein Condition and the third inequality follows from
Lemma 5
The obtained inequality can be rewritten as
B[((Z)))
< (mn) K - B)
K
[((:)]
+
(1r
(10)
(K 3)
K
m7
n
[(())]
+ r
(11)
(mm) - B)
K
j=1
where the second inequality is due to b- < a for < b Sa a.
Step Two: By the construction of Gr. it can be varified that
mn
In details:
If V S r, we have g = f. It follows that
1
E E()(Zz))22 1 m
Σ 2
1 m
Σ
? <V() Sr.
(12)
=1j=1
If V > r, we have g -=rgg//// (f) It follows that
m
12
1 m
2
m
,
Elo(z))]2= = m Σ
E0((Z))22 = m[V
B[ <
Sr. (13)
[
mn
1=
22

---

Published as a conference paper at ICLR 2023
Combining the boundness of G, and Lemma 4 with probability at least 1 - 8, 96 2 0, Va 2 0, we
have
sup gEer
Elo(Z!)) 1 o(2?)]
< 21 + (R)
(9.))
8r In(1/16)
+ (1
2 a
4b In (1/8)
17722
mn
mn
where Rmn (9.) E suppEs, - mn Σ プラー o. {0(Z
Next we apply "peeling" technique to bound (G)]]. Given A > 1, let (u, F u S (f) I o. and denote k as the smallest integer such that r rx+t1 2 Bb
Then
E|Rmn (g. = E 5.0
sup gea,
1
=
E 8,0
sup JEf.
max(r, v(n) AJ(Zz)
mn
mn
m
N
E
sup
o(f(Z()
+ E
sup
S.0
[E (0,r)
mn f=1
JE (r, (r,
mn
sup
E
sup
j=1 2((2)
8,0
mn
8,0
mn
sup (o,))
ΣΣ Al((
Σ
E
sup
Σ oo(((
mn
-=
(0.2+4)))
mn
(=
(r)
k
(+X
B
B
j=0
By the property of sub-root function it follows that we have (0r) S (r)) for any 0 1. Then,
(r)
[+ [++VX>> x- $ ))
s (()r
(1 1+ (1+ v
E[R)m.((G.)] (9.)
B
B
1=0
Taking x = 4 it follows that F[ S 5rb(r)/B. B.
Combining with the property (((r <
(r=)) = vrr". The following inequality can be
obtained with probability at least 1 - 8, v0 0.
[[g(Z))) - [lo(z)))) -
< 10(1 + a))
8r1n(1/8)
+ (1 2 4b (m108)
sup -
VIr +
B
ma
where r" is the fixed point of sub-root function (r)).
Step Three:
Recall that the condition we get inequality
(4) is
m
1// BK
V sup gEG,
B[g(Z])] 9
mn
j=1
We denote A and C' Cy
10(1+ + a)
8 1l1(1/8)
2
46 In(1/0)
A =
Vr +
C=
1 1
B
mm
me
Next, we need to solve AVr + that is
,/9 BK
,1// Assume ro is the positive solution of A + C
BK
ro ABKr BKC = 0,
(14)
Then by Lemma
5 we have
ro < (ABK) S + 2BKC
2-8
< (BK) 2ラス ش
(
10 + a)
22
(1))zt +
8 8m1(1/))
+ (1+ 2
8 8BKbln(1/8)
B
mn
(2
3)mn
23

---

Published as a conference paper at ICLR 2023
where the second inequality follows from (x y) => 20 (x" + y
1/0
If r* S rn. take ro- Then have V s Avro +C= Bx
Combining inequality 4
we get
Σ B[((Z))]
K
[(2))| + /K
(mm)(( B) i=
K
[(ZZ)]
+2K) (10(1 a)) (r*)2in
(m - B5 i=1
28+3 B 3xxxx
(1+ (B/a)))Bblm(()
+
(2- 3-3)m
(1 BK-
If frr² > ro. we can take r = r". Then we have V S Avr" +C=
Combining inequality
wc get
Σ
B[((2))
K
[(2))] + +(r))
(mm)((
3)
Step Four:
Note that (vr) is set to satisfy the following conditon,
((rr BR (F*
where = B2L2 and
Clearly Gr e Fma(f) S r., where T (f) 1 E EZND [f(Z)) Thus.
B[Rmn (G))
=
E
sup gEG,
(,9(Z9))
S1, Sm
;=1
E S1. Sm.a
sup Tma Sr
of d(((
==
SEF
Runn (F ,r).
Lemma immples that the sub-root function can be chosen as
(brr dlogg (27(mm)2/2) mn
log" (2)) mn
In a similar way to Lei et al. (2016), let ri.m be its fixed point then we know that dloge (27(mn)2/2)
rinn logg (27(mn)2/2) mi
mn
Solving this equality gives rm I cd(mm) -1 lloo
- (x)))) x?)] < 0 and the result of Combining the fact that ビi=1 Σ step three, we get the following results
(h) - (T(
1 E [((((x)) Y2) -(hr)
S (2K) 2 (10(1 a)) max((r) 2'. (r))
20+3 1 B² +
(1 + (2/1)))B11((11))
mn
(2 8)
24

---

Published as a conference paper at ICLR 2023
When mn 2 cal log"(mnn) we have max((r)) (r+)²)= (r:)) Thus,
log (og)(mmn)
2-1
log( log(1/6)
3-17
Lo) s a
+
02
mn
mn
C.3
PROOF OF THEOREM
3
Proof.
First we define F : {f (X, (((()) - ((h" h) H}}.
Step One:
Combining Assumption 2 (b)
for any F=, we have
ED YI] ED [ -, ((h" YI]
EDD, (((h(x), - XX)
[(((h(X1)) ((h" (XG), ?
-M) S (B - -pp(h)) ()(²
Let V(J) == E ((N(X),) - (X), Y))² B = B2
Consider the function class G, associated with F and r 2 0:
g = {0 9 = max(r, ((F) 1 EEF
rs
9:
We denote V++ by
T
V+ sup gEg. m
Egg Z.)] E[g( (Z+)1]
Let K > 1,0
and B 2 1. We first prove that, if V <
+/8
BK then
K
1/8
vf E F
E[f(Zi)] S m(K- - 3)
B
[f()))]
(15)
K
1/2
If V() r, then g = f. It follows that with the assumption VI+ S
we have
BK
r1/0
B[f(Z) <
E [f(2))] +
(16)
BK
K
Σ
m
[B(()))] +
1/8
(17)
m(K K
B)
K
If V()) 2 r, then g g= /=r//V()) It follows that with the assumption Vi+ S 1/8
BK we have
-
B[f(Z+)] <
E [f(Z])] +
(18)
BK
E [f(z))] + ト
K (E[f(Zi)))
(19)
(1-3)rt
E [s(z]]] + K B[((Z))] +
(00)
K
where the second inequality follows from Bernstein Condition and the third inequality follows from Lemma
5
25

---

Published as a conference paper at ICLR 2023
The obtained inequality can be rewritten
K
(1- 3)r
B[f(zi)) S
[f(z]]] +
(21)
m(k 3)
(K 13)
i=1
r3
K
[s(Z;)] +
(22)
m(K 3)
K
Step Two: By the construction of Gr, it can be varified that
ED.P (2..:(121-0.0(22 s..
In details:
First, we have
1
E [B 1 Σ Blg(Z.)) (23)
ED, <
If V() S r, we have g = f. follows that
1
[[ =I/2
(24)
m
If V() r, we have g = rf/ It follows that
1
m
22 [V(]]
y2
Σ
[V(A) (i)(2,)) S
Sr.
(25)
m
Combining the boundness of G, and Lemma have
with probability at least - 5,50 > 0, Va >
we
m
[[g(Z.)] [[g(Z $ 2(1 + a)
o, o,E 2) ~ (s( 22)1
sup ,EG, m
sup DEG, m
D Dm.o
t=1
2r 2r1n(1/0)
1
bln(1/))
m
a
m
Thus, we get
1
2r In(1/8)
1
1
b bl((1/5
sup geG,
[[g(Z.)] [] 2(1 + a)E(R...G.)). +
+
+
3
m
where Rm (G.) supgEg. [
By "peeling" technique and similar following steps in the proof of Theorem probability at least 1 - o, A8 2 0
2 it follows with
Blg(Z()) o(2?)]
10(1 a)
2r ln(1/8)
6ln(1/8) m
sup 9EGr
mm
m
where r" is the fixed point of sub-root function (tr).
Step Three: Then by Lemma
5 we have
T (BK) 2
(
10(1 + a)
(r))== +
221(1/5)
1
2BKb In(1/8) 8mm
+
+
B
mn
3
a
(2
26

---

Published as a conference paper at ICLR 2023
Let FF be the loss function class. We consider the functional T(f) Pf here. The structural result on covering numbers implies that
log Fr ll (12) s ( H, l12) s dloo"(7L//e)
Lemma 6 implies that the sub-root function can be chosen as
(br) d dog (2ym²/2)
rd (2)m
m
m
In similar way to
Lei al. (2016), let rmm be its fixed point then we know that
mmm dlog (2
r*d log" (2ym
m
m
Solving this equality gives rm S odm In similar way to the proof of Theorem we have
log" (m).
K
log (m)
2-3
log log (1/))
2-87
B[f(Z))] S m(K 3r)
[s(z))] +c1
+
(26)
That is,
Cr(h) -(fi)-Lrle (r(1)) S
K 3" (LD(M)) - LD((1)) +
K
log log)(m)
b 5m
log (1/)
02
Using the fact that
(D( LD(h") = LD(Pt) ) + S - CD(P)))
S LD
we get
Lp(h)-Lo((h) K K-3" 3" (Cn(T) Co(hrt) +c1
K
logg (mg)
1og(1/15
2
62
m
m
Combining with Theorem
2 we complete the proof.
D PROOFS OF THE RESULTS WITH SUB-EXPONENTIAL LOSSES
D.1 LEARNING RATES FOR SUB- SUB-EXPONENTIAL LOSSES
We state our results on the convergnece rate generalization emror for sub-exponential losses. First,
consider the participating clients. Let S { (i.j=1,11 be global data samples whose subsets S, \ include i.idd random variables i-th client.
(m..)
Theorem 6 (Participating error for sub-exponential losses). Suppose 72, take valued in a Banach
space (Z, ||l [I) and each || is sub-exponential distributed. We denote by F 12 + {(h, Z) (003)=[(2]]] [(=')l < L||= z/1l. For any > 0, if
E H. such that, Vʃ F and Vz, E Z, [f(=) -
mn 2 ln(1/8) In 2, then with probability at least 1 8, we have
2 ln((1/))
sup (h) Ls(h) NER
< 2E (F))
max 16e 2 IIl ie(m)
mn
where Rmn (F) = SuP 1 LE (2)(
Remark 9. Theorem 6 can be used to bound semi-empirical excess by applying standard uni-
formly supremum of h E H. It is worth emphasizing that the bounds derived in Theorem include Rademacher complexity term and ||||Z] Illls measuring the tails of input data samples (m.m) {2() (iJ=L,1 Intuitively, regression problems, as the noise added the lables increases, expected that participating error increase as well. This phenomenon ignored under the previous bounded assumption losses.
27

---

Published as a conference paper at ICLR 2023
Example 1 (Linear regression with unbounded loss). Let 2 = (X, R), where X' is a Hilbert-space with norm || || We denote by (X;, Y each sub-exponential random variables in H and TR. respectively. Let loss function E be a I-Lipschitz function (absolute function or Huber loss) and F == (x, y) + f(x.y) (( - y) ||l| S LJ. If mm 2 In(1/0) z In2, it follows with
probability at least 1 -
+ max II|| IIlles) ) (1+ Bey Inl
sup hEH
-c((()) v /mn
max
L [|||xx||llv
(remm
ve(m)
Theorem 7 (Participation gap with unbounded loss). Under the same conditons as Theorem 6 and we have
Example i
(LIl + +IIx (1+ 3e 3ey In( (m( mm
8
sup [Cp(h) - CD(h)) NEH
where X1 is random vector with expectation across two-level distribution. This is, E||| PBy ||
Pn,,PEx, Similarly,
Remark 10. Combining the results of Theorempaane Theorem 7 it can be shown that upper bound of excess risk is of order O(7mm + V.m). Though this bound is derived under the unbounded assumption, its order is comparable with basic results derived in Theorem [ Note that the upper bounds in Theorem ( include terms such as || and [|Yil|. whose underlying distributions are across our two-level framework. This reflects that the participation gap captures the generalization error caused by client sampling.
Lemma (Theorem 3.1 in Maurer & Pontil 2021); ). Let f X" + a random vector whose elements are independent and take values in a space X. Then for any t 2 0
RR and (X X,) be
-t2
P -
S exp
4ea
En (X)
+ 2e max
[|(((X)]
t
PROOF OF THEOREM
Proof. We first define a vector space
B 9 F R: sup)g( 0
SEF
By definition, B is normed space with norm |19|| sup fEF l9()), For each Z3 E 2, we define ())() Thus, ||2,| 0, and
sup
2 (f) by
ΣΣ 2
ΣΣ ((())
sup FEF
mi
85
From Lemma
we have
ΣΣ
24
-
ΣΣ
21
< Σ 21 - E ΣΣ 2
i
85
S max Se mm |1 211(1 xE/ml
Observe that
|||| 2
||all
1
sup lEF
E [(Z2))
((
2]|
sup E -[((2))-(22))) S(2 feF
mn
mn
4/
L
z
2
2L
mn
mn
28

---

Published as a conference paper at ICLR 2023
Therefore, get mm
||||2;
||
[
2L
|II| Z
(il and
2 2l((1/0)
ΣΣ
22
E
ΣΣ 2
max 16e ||
EE [m
ma
8
3
B
By symmetrization, we have
ΣΣ
E
2
< E
Rmm (F) = 2 EE
E
sup FEF
1Z Z
S .m
S Sm
18
=1j=1
PROOF OF EXAMPLE 1
Proof.
n
m
12
m
Ryn (F) =E
sup
Ozj S (2?)
= EF.
sup
aszl((w, x²) Y.
feJ mn
||ell| 1t LL mn
j=1
j=1
n (w, Tiy X/)
1
E
sup
+E
Ti
Y!
|| SL
mn
mn
j=1
m
122
E
sup
(w,
Jij Xy)
+E
E
oi Y
|| SL
mn
mn
L
E
X
||
E
Y.
mn
mn
Next, using Jensen's inequality we can see that
E
E
1
E
ΣΣΣ
o
x
;=1Ø=1
1=1j=1
i=1 j=1
j=1
By the assumption that 01,1,
Om. are independent, then we have
(m.n)
(m.n)
E
Jity
X
E
Σ
H
(1-5)= (1.1) (1.1)=(1,1)
(m.n)
E
Σ
Oijost (X/,
+E
Σ
of ox
(..))
(1,)=
(m,))
E
(x
Σ
(1.))((11)
(1.1)
Thus, we have
E
Σ 1=
x2yXi11H
|| 112
(8,)
Similarly, we have
n
m
E
Fz Y!
<
Σ Y
{=1
1=
(1.5)
29

---

Published as a conference paper at ICLR 2023
Therefore,
L
Rmn (F)
||x:
|2?
mn
(b,5)
(1,5)
Since "I, X independent and
||
12 211
|1: we get
2L
1
E Rmn (H) I max
/mm |||
Illl
+ max
|||I I1l
<c [m]
sc(m) vin
PROOF OF THEOREM
Proof. We first define vector space
+ R suplo(f)) 00 ) F
B 9
fet
By definition, B is normed space with norm ||A|| sup (9(s),, Let ((D,) =E2)~D,1((3]) and EDf( ED,-P(BB 1E For each Z 2, we define 2, by (1/m)([f(Di)
([)(),))) Thus, [[[2] = 0, and
Σ
Z
E(((D.) - B((DDD)
sup JEF
From Lemma
we have
Σ 2
Z
Σ 24
Σ 2,
18
18
18
88vmll
||| Zu |1 v 2l((1/0).
Observe that
1
1
||||
sup
E (f f(D)) D]
sup E (lf(D.) f D
m
fEF
m
feJ
1
E
sup LET
IS(D:) - S(D)) D
W
1
sup FET
IS(D)) - S(D:))
m
E
sup If(D)) - ff
sup /EF
If(2,) f(Z))
S E |L Z111P].
/EF
Therefore
|ss
f(D))],,
| 1| -illlpp and
|sup seF (f(D,) f(D))
|| 12,
7:1llyp,
Then we get |1|
|1s p/
<
21
2 01 and
m
Σ Σ
2
Σ
2
16e 1 v.
2 2ln(1/8)
By symmetrization, we have
Σ 2
< 2 E
E
sup SEF mn
o.f(D.) | D
D DE Dm
B2
< 2 E
B.
sup
azf(Z)) 7
21 ... Zm
1=1
8
< 2
RRm (F)
(L]II |II| llle. + +II|X
Z15 7m
Vm
30

---

Published as a conference paper at ICLR 2023
E PROOFS OF SMALL-BALL BASED METHOD
Definition 10. Let H C L2(D) be a closed and convex class of functions and H. : {h- h². h, h H}.
1. Let Qu(T) infneH P((h(())) 2 7]/A)lZ2(D)) where X3 represent the random sample at i-th participating client.
2. Let Qu(T, P) = inf IP ([E[)(X))] =l|M)lza(P)), where X represent the random sample at i-th participating client.
Definition 11. We denote by B the L2(D) unit ball entered at h", that is B = {h E
||b - 7- (L2) $ 11. For every > O, define
Wimn (H, = inf 8 :
sup KEROIBT
of ((()
S 1188
where of are Rademacher random variables.
Definition 12. We denote by B2 the (P)P) unit ball entered h² For every O, define
Wm (H, = inf s > E:E
sup hE
(x)(()))
E
m
where are Rademacher random variablex.
Lemma 8 (Theorem 1 in (Zhang & Wei 2022 [X are independent centralized random 0, then for any weight vector
variables such that (Xilll... < for all SIS n and some w (wi,...; Wn) E R2,, the following bounds holds true:
{-(2:
c Σn wP ||xell
Con maxicign wa ||x 11
wi x
$ 22cxp/
E. PROOF OF THEOREM
Proof. Step One:
(s(h) Ls(hi)
(1(x)) - x21² -h-'((()) - Y?79]
(27)
mm
1 mn
(h (x7)
2 - ((hh)))(x)))
(28)
mn
The second term of the RHS of (28) is determined by the underline semi-empirical distribution D and the hypothesis space H. therefore we focus on the first term in the following. For any h E H. and a 0,
(((.)): M(x)) w) (I(()))22))
Also,
m
12
1 m
(1((x))222n)
(1xx)122))
VI
m
m E
(1((2))22>)
Ex
mm
m
j=l
31

---

Published as a conference paper at ICLR 2023
Let Ou : IR + [0, 1] be the function
0 S u
Ou(t)=
L 1 S t S 2u,
(29)
2 2u.
Note that for every / E B. (1) 2 11 (1220) and (l()) S [tzu). Thus,
77
m
(1(())221))
E
(1((X)1222)
mn
m
m
m
S (u((((2)))
Σ
E (b(()(())
mA
j=1
inf (X)
) 2n)
NEW
m Σ 2=1
m Σ E EX-D [(n(((()))]]
S (b((((())))
sup ACи
mm
j=l
Since function (() is bounded by 1, using Mediarmid's inequality, we get that, for every 8 > 0. with probability at least eexp(-252),
sup bEW
Du (1((2))
E
do (M(?))))
< E sup kEH
Su
E
o ([((D))
+ Vmn
mn
1=1 1=
By the Lipschitz property of (It) and the symmetrization theorem, have
m
m
m
E sup NEH
(X?))
m Σ
S E sup MEH
M(()
mn
u
mi
j=1
Therefore, for every h E H. it follows that with probability at least 1 - 2 eexp(-28")
we have
m
(100/1220)
2 inf ((I((X)) 2n) NEw
4
sup AEH
o(M(x?)
(30)
WIT
mm
=11=1
1=1
Step Two:
The first term the RHS be bounded by small ball condtion. Let H² 7 - h.. We first prove
that H- star-share shaped around 0. For every h E H" and 0 S X < 1, we have X(h h²)
Xh + (1 A)h* h Since H is convex, it follows that Ah + (1 Δ)h- E H. Then the claim follows because A(h - h)*) H -h"
Assume that these exsits > for which Qu (2t) > 0. The for every 2 w(H , TQx (27)/16). we have
TQH:
E
sup AER"NNB"
o(!(??)
<
16 8.
mI
1=1
Let G be a function class associated with H-
h
g =
h E H" (
C Bm
32

---

Published as a conference paper at ICLR 2023
where By is the unit ball with respect with L2( and D is the semi semi-empirical distribution.
m [()(
1
h(x!)
TQ 7Q
=QQ
sup SEG
E sup
8
16
16
where the last inequality follows from Qg 2 Qn (2T).
By equation (30) applied to the function class 9, it follows that with prohability at least 1
2 2exp(-22 --2
1
(lx(X))22)
2 inf ((19(X;)) 2 2u) - E sup gEG
mm
geg
MA
mn
1= 1=
j=1
2 Q2(2u)
sup gEg
o!9(X?)
mm
mmn
t=
==1
TQgg
8
2 Qc(2u)
" 16
Vmn
Now, setting
u T 8 (m
it follows that with probability at least 1 - 2 exp( (2Tn2g(TT//2
11 (1(x)))27) Qc(2T) Qg(2T)
Qg((r) Qc(2T)
4
2
4
Using the condition Qg(2T) 2 Qn- (2T), for every 2 ,HH",,QHH (2T)/16), it follows that with probability least 1 exp( Texxp(-mnQQa mm (2r) we get
m
1 (1o(x)117) mnQg((T)
mnQu- (2T)
inf (((.j) lg(x > r}|= Σ sEG
(31)
4
4
For every h - h-- 71 that satisfies |/ - h- (()(()) 2 since H - h is star-shaped around O, we
have (s/ Ih (s/lh-hi*
h (1))())) (h- h-) E 76 SsB Thus, (h / h- (11(22()) G.
Combining equation (31. if s 2 w(H", TQu- (2r)/16) then for every h E H. that satisfies || h ()))) 2 8, if follows that with probability least 1 2 2exp(-mmQQ (2r)/2), one has
[(0.)) ((h - Xx(() T1th ih |LL00)))
mnQu (2r)
4
Therefore, on that event, we get
72 Qu (2T) h1'122(p)- 4
(h >
(32)
Note that H2 C H- is, if 2 wH.., 7QH (2r))6))) then for every h E H. that satisfies |// - h ( 2 s, if follows that with probability at least 1 - 2 (xxp==mmxx==(27)//
H. the same conclusion holds with Qu-H(22 replacing the larger Qu- That
one has
-2
(h -
>
Q# Qu- H (2T) 1
7 11
mn
4
Step Three:
Combining equation 2p. with the same conditions we get
?2 QH Q2 - hr
Ls(h) - Ls(h²)
el(h - )x)) +
(33)
mn
4
33

---

Published as a conference paper at ICLR 2023
Since 1 m E {(h - (x:))
2 then we have
m
m
c -h- {x?)
c0 - -x))())))))
m Σ
Ex-D:
- (xt))]))(()
mm
mm
According to Lemma
we have
P
m
2 ((h-h)((2))
1
E
Ex~D, <(h C(hh-ho)4 -()-)))))))
2 2n/h - -7011221D)
mn
m
j=1
(1))(mm)) |11 - 11, (D)
c27 1| 1:-11220 L2(D)
< 2 exp
Σm i== Σラ=1 1/21 13/100 (.)())))) V2'
mn
where
V e/ ((h-)>)(())) - -=)))))))()3]
We denote C1, C2 by
ード V 1i
V2
C2 (ax(1))5(())(mmmm
C
4
C2
Then we have
P
(h -
-x))))
m Σ
1
Ex ExnD, [5(h - -ht)(())
2 n//h - h 1
mm
i=1j=1
(m(mm)l
h li
(mm) -f-
}
< exx
^
C2
C2
To make sure that the probability tends to zero as mn increase, we could chose ||h 7 (le 2 (mm)= ++ where 0 < 4.
Then with probability at least
1=1-2exe {- (m(n))
17 (mm) x01+4))
-
^
Ci
O2
have
TI
m
(h {x?)
m Σ ExwD. E(h-7'))(7)
S -
(34)
mm
1=1==1
Combining
2 and 34p.
if ||/ 7o- L2(D) 2 max(Ni, s), it follows that with probability at least
1 1-8 2ea exp
mnQu
(2T)/2),
Ls(h) Ls((h)) 2 11 11 1 11 ( (= 41)
Consider 7) ( 16, get
Ls(h) - (x(h²) 20.
On the same event, we have
17e - To" (L)) S max(K, 8) = max((mm) 7+c -4+ w(H H. H.TQU=H(22 (x=
34

---

Published as a conference paper at ICLR 2023
PROOF OF COROLLARY 1
Proof. Let s w(H H. 1 (2T)/66)) and (mm)- where 0 <<<< 1.2 By theorem we have
11 - h (12)())) S max(k, s).
Therefore, it suffices to show that for quadratic loss have
m
(b) LD(()))
T (1((2))
- x2)² - (x,)
(35)
E
[(--)))((3))
2 m ΣΣ
[e(h - (((h-hh'(()) {()())
(36)
3=
Note that for E H either
2 m
n
- (r)'))
5 mn
E (h- - 1T' [1)-))))((3)]
j=1
or
m
(D) CD((t))
E c 1ia---i0 (x?))
mn
1=
For the first case, we have
- -o)))-Lo(h)) s -
11)) - S 2 max(1??, 52).
For the second case,
(h) Ls(ht) = mn 1=1 j=1
1
Σ
(M(x)) - 12/² - ( (x/) - vイ)}
(h (x/)+
< - xx))))
2
< - To [xx]
E
mn
i=1
f=
2
c/(h - -
2
-
E (2
m
mn
For convex function class H. we have Eie (x) 2 0. On the same condition that inequality 34 holds, we get
(h) Ls(1'))
2
E
c/ - - (x})]]
mn
;=1
2
ΣΣ ch hx))
m
mn
mn
i=
i=1 j=1
2 (CD(h) Lo(h')) 72Q 1 - (
1
2
8
1
(hD(h) - LD(h')) -2Q (2T)
2 2
max(k? $2)
Since Ls(h) - Cs())) < 0, it follows that
(LD(h) (p(())) < (2 4
m
35

---

Published as a conference paper at ICLR 2023
E.2 PROOF OF THEOREM 5
Proof. For quadratic loss, have
LD(h) Eo(h)-Lb(hh)
E (Mxx))) 1!12 (x!) y!
(37)
1=1
m
B((h - (x))(x
Σ
Big (h (x)))))
(38)
Step One:
For any h E H and u > 0,
Hi [[M( u/1 = Σ (
Also,
1
=
E D
((IEThx23)1 2201
17
m
1 (BBX))))
E D,~P
((EMM()))222))
m
Let du IR + [0, 1] be the function
S u,
(t)
t 1 u S s 2M,
(39)
2 2u.
Note that for every t E R, (t) 2 1l (1220)) and (t(t) S (12u). Thus,
(RA()))22)) 2
D
Sa (B[(((I))))))
D.>P (X)((((
m
2 inf bEH
P(IE[[ 2 2u)
sup NEW
S (E)((X) D
E (ET((())
Since function (t) is bounded by 1, using Mediarmid's inequality, get that, for every 8 0, with probability at least 2 (-22).
1 m du (E(N()))
(eT((((
sup bEи
7
D
m
E sup
du ([((())I)
E (B D
m
m
By the Lipschitz property of on (lt)) and the symmetrization theorem, we have
4 E sup
E sup KEH
(IE((()))) 1=1
E ([E((((()) D
ox)((X,)
hEH
where X; is the random sampled across two-level distribution framework.
Therefore, for every h E H. it follows that with probability least 1 2exp(-288 we have
36

---

Published as a conference paper at ICLR 2023
1 m
2 inf ((IE(((X)) 2 2u) E sup NEW
Σ
m
,zh(Xi)
8
(40)
DEH
m i=1
vm
The first term on the RHS can be bounded by small ball condtion. proved that H is star-shaped around 0.
Let HC
H - h²," we have
Assume that these exsits T 0 for which Qx (2T, Wm (H. , TTu (2T, P)/16) we have
>
0.
Then for every 8 2
1 Σ
TQH (2T, P)
E sup bEH-naBm
oxt)
I
16
2m
Let be a function class associated with 7.
g -= { h
h E 7t ns
C Bm,
where Bm is the unit ball with respect with (P) and P is the population distribution.
1 m
h(X.)
< TQu (2T,
TQq P)
Esup SEG
(X.) 1=1
= E sup
16
16
1=1
where the last inequality follows from Qo(2T, Z QH- (2T, P). By applying inequality (40) to the function class G, it follows that with probability at least - 2 exp( 2
4
m
8
(E(((())))
2 inf P( 2 2u) 9EG
E sup
(X))
u
3Eg
m
vm
1
8
2 Q2 P)
E sup
oig
(X+)
gEg
m
v m
4 T g P)
8
2 Q2(2n, P)
16
Vm
Now, setting
u 8= /mQg P)
it follows that with probability at least 1 - 2 (mapp P)/2)
Qg P) Qg(2T, P) Qg(2T, P)
1 ((MXI)22 2 Qo(T P)
4
4
Using the condition (2r, P) 2 QH-(2n P), for every 8 2 Wml'', , (2r, P)/16), follows that with probability at least 1 - 2 2exp(-mQxx (2T, P))2), we get
Σ 1 ((E((())))) mQq(2TTP)) P)
mQ=-(2T,F
inf Hi: [B|g(X|)| 7) gEG
(41)
4
4
For every - h1" E H' that satisfies ||A ht" (12 2 s. since H. h² is star-shaped around 0, we have (s/ 11"11 (I.))))) (h h²) E 7- n BB.. Thus, (h - 11") / h ht" (12((P) E G.
Combining equation 44 if 3 2 wm (H," -T.T (2r, P)/16) then for every E H. that satisfies ||h - h² (l)) 2 it follows that with probability at least 1 2 exxp(mmQu (2r, P)/2), one has
mQH (2r,
[(:: B[hh h (*)(IIII > T1lh- h²" |
4
Therefore, that event, get
1 E (hh
1
Σ
-
72 Qu (2r, P)] 1011 (42)
37

---

Published as a conference paper at ICLR 2023
Note that Ht"h C H H. the same conclusion holds with Qu-H(2T, P) replacing the larger Qu- (2T, P). That is, if 2 Wm(H", TQ,--((2, P)/16), then for every h H. that satisfies || he (1))(P) s, if follows that with probability at least 1 - 2exp(-mQQH (2T, ()T, one has
112
_ Qu-u(2r, P)1h- h0" 1P
E(ch-
772
With the same conditions we get
(1(h) Lp(h")
2
Σ E [ct 11 [xx)]
72 Q2- P)]lh 10" (Lacee
(43)
Since
D.
[ (h- h+)({)} 2 0, then we have
118
1 m
E (X
(c h² (x)))
E 2 (X
(h (ith-h")a (xx))
m
m
E PD ( (x!))
According to Lemma
we have
[ - (thh-h"(()))) [x)( -E..,,........... 15(h - (1)h-)))(xx))) 2 71/h - h1" 1=112,(0)
m D
c172m I1- - l1: 11'1(1((P) c2n | 10Pm@11---i0
111h 1 L2(P)
< 2eep
-i=1 ||Vill
maxisism Vill
m
where
V= (X,,))),,
- (()[))))(x)) -E 15(h - ((fh-1))(X)) (x)((
We denote C1. C2 by
C1 2i=1 V dia
maxigism V
C2
C1
C2
Then we have
m
PE VIND, 15(h - 11" [xx)) 2 n/1h - >²'1(aac))
(X
mmmllh (12(()))
n
htt 1122 (2(())
$ 2exp
C1
C2
To make sure that the probability tends to zero as m increase, we could chose | - h- hles()))) 2 K m th, where 0 < <<< }.
If || 1'1leg()) > m) it follows that with probability at least 6m 2 eexp(-mQur (2T, P)/2),
[ (2)
(h) LD(h") > |1 1h-11112 -h
where 6m exp(- -
2
can" c (11/212))
}} Consider 7 22 P)/16,
maxisism l[V.l.._
get
LD(h) LD(h") 2 0.
On the same event, we have
| - 1t" (12P))) S max(F, 8) = max(mm - ( - H, (2xxx(22))/6))
(44)
38

---

Published as a conference paper at ICLR 2023
PROOF OF COROLLARY 2
Proof. Since excess risk is defined across our two-level framework, the steps in the proof of Corol- lary 1 can not be applied directly to derive Corollary 2
The key step to derive Corollary 2 is to
bound || h" 10 (P) First, this term can be decomposed as
I1 h (12,CP)) S 2 h 11 + 211h" h [[)((P))
Note that | h" (P) has been bounded by Theorem following decomposition:
we use the To bound | Rh" (12
1 - R (m) = =1ih-7'112,(r) - 1l 1'112(()) + 11 - h- (2)()))
Note that h (1 has been bounded by Theorem
According to Lemma 7 we have
(h- -1))))(()))]
ED [1h-
2 2nlh - -h- (
mm//m// - (1
c2n I 7o" 12 La(P)
)}
exp
1 E
Vi5ll
maxisism Vill
where
V12 =
E
(h (h-1i))((x))
-n ( (
(X
We denote C1, C2 by
1
i== [
C2 maxigism Vil
C1 m
C1
C2
Then have
m
(h-)tt)((x)) -ED-PEEX..Y)D - [(h-)()((x.)] D,
n/1h 70 ((1h11p))
m
(1 mm ||h
m/mmllh -1
(1))(())
h (122(p))
< exp
C₁
C2
To make sure that the probability tends to zero as m increase, we could chose || TT 2 m àtt, where 0 < < 1
By following the similar steps of proof of Theorem can be proved that with probability at least
{
m
C27"M a(144)
exp
1 i=1 1i
maxicism ViVll
one has
1h - 1r112_(P)) - 11 7o
1l S nn h (1,.(p))
Thus,
[ - R 11-112,pP) _
1
[7 To- 11122
1-
Moreover,
2 -1 Tn" 11 [1 + 2 - - 112.)P)))
j 1' S T-
170
If h*(X)) Y, is independent of X, then BlEi(h 12 nx)(x,)] =
39

---

Published as a conference paper at ICLR 2023
m Σ B [1((1)) xi) (x.) -x)²
Cp(h) Lr(h')=
(45)
1-1
n
(h (((h-h(((())) [x))( + 2
m Σ E 5.1h - 8 [xx]
(46)
Σ (h ht (x))]
(47)
Thus,
1 m
Cp(h)-Lp(h Lp(h")
E((h (x)))
(48)
1
11 h 11'l 112((p)
(49)
2 hh 11' + +2 h- ([2)
(50)
Combining inequality 50 with Theorem 4 and Theorem
we complete the proof.
F EXPERIMENTAL RESULTS
F.1 CONVOLUTIONAL NEURAL NETWORKS FOR EMNIST TASK
To check the validity of our theory for over-parameterized models, we train convolutional neural network for EMINIST task (Cohen al. 2017). In particular, use FedAdam (Reddi et al.) 2020) with server momentum = 0.9. The participating and unparticipating clients are split based on the methods proposed in (Yuan al. 2021). We set the unparticipating rate as 0.2. Our experiments are based on Tensorflow Federated (TFF) (Alex & Krzys 2019).
MNIST
MNIST
1.00
0.25
0.99
0,20
0.15
0.98
loss
aCC
0.10
0.97
0.05
0.96
0.00
0.95
1.5
2.0
2.5
3.0
1.5
2.0
2.5
3.0
log (#participating clients)
log (#participating clients)
participating training
participating vali dalidation
unparticipating
Figure 2: Generalization error versus the number of participating clients.
In Figure 2 we show how generalization errors for unparticipating clients and participating clients convergence when increase the number of participating clients Here we fix = 100. It can be seen that the convergence rate of participating error is slower than that of unparticipating error. This phenomenon matches our theretical results in Theorem T well. In our results, the convergence rate of unparticipating error is of order O( /mn + vm Compared to the convergence rate of participating
error, which is of order O mmn ), unparticipating error is expected to have faster convergence rate.
In Figure 3 we show how generalization errors for unparticipating clients and unparticipating clients convergence when increase n. Here we fix 20. It can be seen that the convergence rates
40

---

Published as a conference paper at ICLR 2023
MNIST
MNIST
1.00
1.50
0.95
1.25
1.00
0.85
0.75
0.80
0.50
0.75
0.00
0.70
20
#samples participating client
#samples per participating client
participating training
-B-
participating validation
.-- unparticipating
Figure Generalization error versus the number samples per participating client.
of participating emror and unparticipating error similar. This phenomenon matches theretical is same as the order of results in theorem as well. When m is fixed, the order of O Vinn Vm)
F.2 FEDERATED LINEAR REGRESSION WITH SYNTHETIC DATA
In Figure we show the numerical experiments results based on the linear regression model. We first describe our linear regression setting as follows. For client i E [m]] the dataset given as
S: = (x: y with n samples. Let be the dimensionality of the input space. We focus on the
setting:
y X ~ N N o,, ox)
Vj I.... n
where of is noise parameter. In our experiments, we set o; 0.05. For excess risk, fix n 20. For semi-excess risk we fix m 40.
-0.
-1.5
B00------SSSSSS risc)
log (oxcess not
-0.6
log (semi- (semi-oxcoss
-0.7
-3.0
-35
-4.
2.0
2.2
1.8
2.0
2.4
2.6
log (#participating clients)
log
per participating client)
Figure 4: Excess risk versus and Semi-excess risk versus
41


Reviews:
[{"review_id": "wf8hqZQ2RFM", "reviewer": "Reviewer_8Tvp", "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  data distributions of participating and unparticipating clients are drawn\nfrom a meta-distribution and use classic Rademacher complexity- and local Rademacher complexity-based generalisation bounds to develop excess risk bounds for unparticipating clients and fast semi-excess risk bounds for participating clients.  \n", "summary_of_the_review": "The authors  did a good job in terms of going beyond convergence analyses and developing (semi) excess risk bounds for participating and unparticipating clients. However, there are major concerns regarding the considered model, the correctness of results, and conditions under which main theorems hold. ", "strength_and_weaknesses": "Strength: Studying federated learning in terms of learning is certainly an important direction, which has not been addressed in the current literature. I think the paper is well-written and the authors  did a good job in terms of going beyond convergence analyses and using known Rademacher complexity-based generalization bounds to obtain (semi) excess risk bounds. \n\n-----\n\nWeakness: Although the authors emphasized much about the relevanece of their bounds to FL in practical settings, in particular cross-device FL with a large pool of unparticipating clients, there are major concerns regarding the considered model, the correctness of results, and conditions under which main theorems hold, which will be elaborated in the following. Also, it is unfortunate that the paper lacks convincing experimental results to validate that the developed bounds indeed explain whether \"unparticipating clients benefit from the model trained by participating clients?\" \n\n-----\nDetailed comments: \n\n \"We argue that this assumption is reasonable in practice. For instance, in cross-device federated learning, the number of total clients is generally large and it is natural to assume that there exists a meta-distribution\"\n\nThis is not really convincing. What if some clients have data distributions that are quite different from others. Also what if the distribution of clients changes over time.  Another major issue is  how should such meta-distribution be modelled? Will you use parametric or non-parameteric models? Given that the authors emphasize much about practical scenarios and settings where several clients may not even participate in training, how can one model/estimate the meta distribution? Imagine that a practitioner does not have even a sample drawn from distributions for the major of clients (unparticipating clients).  \n\n-----\n\nThe symmetrization step in the proof of Lemma 1 should be expanded. BTW, the first line after \"By symmetrization, we have\" cannot be an equality. \n\nMore importantly, the definitions for ${\\cal R}_{mn}({\\cal F})$ in pages 14 and 15 are different, which makes the proof hard to read. The same issue exists in Lemma 2. In addition, $Z_1$,..., $Z_m$ in the proof of Lemma 2 are undefined. So I am not confident about the correctness of the results. \n\n-----\n\nTheorem 2 requires $n=\\Omega(d)$, which does not hold for typical overparameterized models whose number of parameters far exceed the number of training data.  This is even worse in Theorem 4 where $m$, which is claimed to be relatively small is required to be larger than $d$. \n\n-----\n\nThe techniques used to prove Theorem 2 are pretty standard based on (Bartlett et al., 2002, Sridharan et al., 2009, Yousefi et a.., 2018). Is there any technical difficulty in the problem of bounding semi-excess risk compared to previous work?\n\n\nKarthik  Sridharan, Shai Shalev-Shwartz, and Nathan Srebro. \"Fast rates for regularized objectives.\" Advances in neural information processing systems (NeurIPS),  2008.\n\n\nPeter L. Bartlett, Olivier Bousquet, and Shahar Mendelson. \"Localized rademacher complexities.\" International Conference on Computational Learning Theory (COLT), 2002.\n\nNiloofar Yousefi, Yunwen Lei, Marius Kloft, Mansooreh Mollaghasemi, and Georgios C Anagnostopoulos. Local rademacher complexity-based learning guarantees for multi-task learning. The Journal of Machine Learning Research, 19(1):1385–1431, 2018.\n\n\n\n-----\n\nWhy not considering the excess risk instead of semi-excess risk for participating clients? It seems that the bounds will not be better than those for unparticipating clients.\n\n-----\n \nThe bound in Theorem 1 will be vacuous when using overparameterized models and a small $m$. The authors emphasized that $m$ is a moderate value in their settings.  which does not lead to a meaningful generalization results.  \n\n-----\n\nAssumption 2: $X_i^1$ in Assumption 2 is drawn from $D_i$, which is not $D$. Assumption 2 (a) does not seem to be compatible with Definition 1.  \n\n-----\n\n\nIt will be nice if the authors elaborate on what specific problems in ML lead to sub-Weibull loss  distributions with $\\alpha\\neq 1,2$ for $h$ as in Theorems 5 and 6. Also it is a bit confusing since in the introduction the authors claim that they consider sub-Weibull loss functions while they indeed consider sub-Weibull classifiers in Theorem 5,6. \n\n-----\n\nThe definition of  VC major class, which is the main building block of Theorem 1 should be provided in the main paper. ", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "smviZE10Wu", "reviewer": "Reviewer_zSzo", "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 studies generalization bounds in federated learning with unparticipating clients. A two-level distribution framework is proposed, where the data distribution of each client is sampled according to a meta distribution, then the data samples at each client is sampled from the client's data distribution. Afterwards, upper bounds on the generalization error are shown for two classes of loss functions. ", "summary_of_the_review": "Nice theoretical work, but it would be helpful if connections to practical federated learning systems and new insights can be discussed.", "strength_and_weaknesses": "Strength:\n- The analysis of generalization in federated learning is interesting and not often seen in the literature.\n- This paper is a solid piece of theoretical work which may inspire future work in this direction, although checking all the details is beyond my capacity.\n- The consideration of unbounded and heavy-tailed losses is an interesting theoretical contribution. \n\nWeakness:\n- It is not clear how clients are selected to participate or not participate. My conjecture is that the participating clients are selected independently from the underlying data distribution. If so, this setup does not fully consider some practical scenarios, such as where certain populations may generally have low-end phones or poor connections so that it is difficult for them to participate in federated learning. It would be more realistic if participation can be modeled as correlated to the underlying dataset, but I also understand the difficulty here.\n- The results depend on VC dimension, which is a way of quantifying the complexity of classical models but it generally does not capture the empirical behaviors of deep neural networks. Therefore, the theoretical bounds may not reflect what will really happen when training deep neural networks. \n- In Section 3, the assumptions are much stronger than what is usually used in the analysis of SGD-based federated learning algorithms. So the paper should not emphasize too much on obtaining 'fast' rates, as it is not fair to compare the rates obtained under different assumptions.\n- The paper considers clients that either participate or do not participate. For the participating clients, it assumes that the minimum empirical risk can be obtained by $\\hat{h}$. In reality, some clients may participate in more rounds and other clients may participate in less rounds, which may result in an inaccurate $\\hat{h}$ that does not give the true minimum of empirical risk. Such varying degrees of participation has not been considered in this paper.\n- The paper is mathematically heavy and lacks discussions on new findings and insights that can guide the understanding and design of practical federated learning systems. More discussions on what the bounds tell us intuitively (in plain words) about how federated learning algorithms will behave would be very useful.\n", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "kcZ42dw43JR", "reviewer": "Reviewer_yZwY", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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, my main concerns have been resolved.\n-------------\nThis paper studies the generalization bounds for federated learning (FL) with heterogeneous local data. Similar to recent works (e.g. Yuan et al. 2021), a two-level distribution framework is considered, i.e. the local distribution is drawn from the meta-distribution, and the local data is drawn from the local distribution. Compared to previous works on the generalization of FL, this work can decouple the generalization bounds for participating and nonparticipating clients while showing fast rates under different sets of assumptions. ", "summary_of_the_review": "In summary, this paper presents some interesting results on the generalization properties of FL. However, some technical claims seem to be problematic to me (especially the first bullet in the \"Clarity\" section). Disclaimer: This is probably due to my limited time for reviewing (It was assigned to me too late) and my lack of expertise on this topic. I am more than happy to raise my score if concerns are resolved.", "strength_and_weaknesses": "\n**Strength**\n- The problem studied in this paper is interesting and challenging. \n- Proof techniques seem to be new in the context of the generalization property of FL. Some open problems seem to be answered (e.g. unbounded loss, high-probability bounds).\n- The assumptions come with examples to back them up (e.g. Appendix B.1 for Assumption 2). Since this paper uses different assumptions compared to previous work, the examples make me better understand the contributions. \n\n**Weakness**\n- Some statements and claims in this paper are confusing to me (see the \"Clarity\" section below). \n- No empirical verifications (although this is not a big issue for a theory paper).\n\n\n\n\n\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "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": "ibWDBsec7p", "reviewer": "Reviewer_QQ79", "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": "This paper studied generalization of federated learning. They first consider Bernstein function class, and achieve faster rate in risk bound: $O(1/mn)$ for participating clients and $O(1/mn)+O(1/m)$ for nonparticipating clients. They further proceed to the unbounded loss setting, with small-ball condition assumptions. To prove generalization in the bounded loss setting, they borrow the standard local Rademacher complexity based analysis from [1], where they controlled the variation of the loss function i.e., $Pf^2$ and relating localized class to full class. For unbounded loss setting, they borrow the technique from seminal work Learning without concentration~[2][3], where they assume a small ball condition on hypothesis class.  \n", "summary_of_the_review": "In summary, this paper introduces classic finer generalization analysis technique to federated learning, and does achieve better rates, but I am not sure how much the technical contribution are novel in the context of  existing works as discussed above.", "strength_and_weaknesses": "Strength\n\n1. This paper used a bi-level distribution framework to model the federated learning, and assume the nonparticipating client's distribution comes from meta-distribution $P$. Then, they treat the generalization risk on nonparticipating distribution as the expected risk on a distribution sampled from $P$.  This formulation looks novel to me, even though I still have some concern about this setting which I will discuss later. \n\n2. To get sharper risk bound, they employed seminal local Rademacher complexity based generalization analysis. To my best knowledge, in federated learning community, these techniques are new (analysis on Bernstein class, local Rademacher complexity, small ball method etc), and no one before use them to analyze FL's generalization bound.\n\nWeakness\n\n1. Assuming all clients' distributions obeys the same meta distribution, and assuming clients are sampled i.i.d. from this meta distribution are strong. Hence, in the risk bound for nonparticipating clients, we cannot see the impact of discrepancy between distributions used in training and target client distribution. To show the dependency of distribution discrepancy in nonparticipating client's risk bound is important, since based on that we can design domain adaptation algorithms to make nonparticipating client benefits more from collaborative learning. \n\n\n2. From a technical perspective, the novelty in the proof is limited. To me this paper is more like applying existing generalization analysis of Bernstein class, and small ball condition class on federated learning. The only difference is that here we are not drawing samples from one distribution but $m$ of them. However, this does not change the game too much since it is still an unbiased sampling: we draw a multi-sample from the product of distributions, and we examine the population risk also on the product of these distributions. For examples, when the authors prove Theorem 2, they borrow the proof procedure of Theorem B.3, Theorem 9 of [1], controlling the variance of the loss function i.e., $Pf^2$, bounding the local Rademacher complexity, and relating the local class to full function class. The proof without a bounded loss setting is also similar to seminal work [2][3]. I suggest the authors can elaborate more on their technical contributions beyond these existing works [1][2][3].\n\nQuestions:\n\n - In Theorem 2, should not the first term in the risk bound depend on VC dimension?\n\n- At the beginning of Page 19, the definition of $V(f) = \\frac{L^2}{m}\\sum_{i=1}^m \\mathbb{E}(h(X) -\\hat{h}^*(X) )^2$ , it seems that the index of $X$ is missing? I guess the expectation is taken over $X \\sim D_i$.\n \n- The typo right after the computation of $R(F^*,r)$: Condiser $\\mapsto$ Consider\n  \n- At the beginning of Page 25, definition of $B$ norm, should not it be $\\|g\\|_{B}=\\sup_{f\\in F} |g(f)|$?\n\n[1] Yousefi, Niloofar, et al. \"Local rademacher complexity-based learning guarantees for multi-task learning.\" The Journal of Machine Learning Research 19.1 (2018): 1385-1431.\n\n[2] Mendelson, Shahar. \"Learning without concentration.\" Journal of the ACM (JACM) 62.3 (2015): 1-25.\n\n[3] Mendelson, Shahar. \"Learning without concentration for general loss functions.\" arXiv preprint arXiv:1410.3192 (2014).\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "c17Y0m3G7q", "reviewer": "Reviewer_KoJF", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors study the generalization behavior of federated learning in a meta-distribution framework by characterizing two error terms: the empirical-population gap on clients that participate in training as well as the gap between participating-population at the clients level. They establish such bounds for bounded losses, but also unbounded losses for the case of least squares regression with sub-Weibull noise condition and a small ball inequality. \n\n**EDIT**: I have raised my score from 5 to 6 after the rebuttal.", "summary_of_the_review": "While the setting of the paper is very timely and there are many technical difficulties in the process, I feel like this paper is still a work in progress. These results look very much like intermediate results to me and are missing a final level or two of translation into statements that are more directly applicable in the federated learning setting. I would urge the authors to take steps to make the paper more accessible and specialize the results to interpretable special cases. \n\n", "strength_and_weaknesses": "I should start with the disclaimer that I only have a passing familiarity in the techniques used in this work. \n\n**Strengths**: \n- First work to consider generalization of a federated learning to clients that do not participate in learning. Assuming a meta-distribution over clients is a natural idea for cross-device federated learning that has been suggested in the literature yet a precise analysis of this generalization has eluded us. \n- Studying unbounded losses in this setting is technically challenging. It is possible to sweep under the rug subtle differences across clients with bounded loss/gradient assumptions in the federated setting. Avoiding such assumptions is a plus. \n\n**Weaknesses**: \n\n(W1) Interpretability: The biggest weakness for me is the lack of interpretability of the results, especially in Section 4. \n- The unparticipating generalization bound must show some measure of the *spread* of $P$ as a bound on the heterogeniety. In the degenerate case that every client is completely different from each other, it should not be possible to bound the unparticipating gap. Likewise, if also the clients are identical, this gap should be 0. \n- My best guess is that these details are hidden in the $\\kappa_m$ and $\\omega_m$ objects (or in the previous sections, in the bound on the loss). It would be extremely helpful if the authors could elaborate on this dependence. \n- More details on this below. \n\n(W2) Lack of clarity: it is nearly impossible to understand this paper without a deep familiarity with a fairly advanced and niche area in learning theory. To make the paper more accessible to the federated learning community, it would be helpful to precisely define all of the mathematical objects used (at least in the appendix), point to textbooks for a condensed background (if applicable), and discuss several simple special cases such as linear regression and binary logistic regression. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "FosJCT3zcXR", "reviewer": "Reviewer_zYTD", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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 is a theoretical work on the analysis of the generalization error in federated learning with heterogeneity of the losses and partial participation of the clients in the training process. The authors address the question: \"Would the unparticipating clients benefit from the model trained by participating clients?\". They provide a statistical analysis of the generalization error. The main assumption behind is that  the local distributions are sampled from a meta-distribution.", "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. The paper studies the impact of partial participation from the mathematical/statistical point of view. These findings are interesting but there is no contribution from an algorithmic point of view, on how to mitigate the effects of partial participation.", "strength_and_weaknesses": "The paper provides interesting theoretical insights about heterogeneity and the important challenge of partial participation in federated learning (FL).\n\nI am an optimizer, not a statistician. I develop optimization algorithms for FL and I am not familiar with these aspects. With this disclaimer in mind, I have the following questions:\n1) Is there a connection between your setting and the literature on personalized FL? Indeed, from the point of view of the nonparticipating clients, the obtained model is not personalized enough. I am thinking for instance of the paper Hanzely et al. \"Lower Bounds and Optimal Algorithms for Personalized Federated Learning\"\n2) I have come across the paper \"With a Little Help from My Friend: Server-Aided Federated Learning with Partial Client Participation\" of Yang et al. (https://openreview.net/forum?id=xT6d2Ghtkv) which also studies the generalization error of heterogeneous FL with partial participation, and study server-aided FL as a possible remedy. Could you comment on their findings?\n3) Characterizing heterogeneity is important, as well as the study of the convergence speed of learning algorithms, depending on the amount of heterogeneity: intuitively, convergence is faster in the homogeneous setting, since there is redundancy, than in the heterogeneous setting. For instance in the paper \"Permutation Compressors for Provably Faster Distributed Nonconvex Optimization\"\nby Szlendak et al., they introduce the notion of \"Hessian variance\", which characterizes the similarity between the individual loss functions of the clients. Since the losses are date-fit terms with respect to the individual datasets, this is directly related to the amount of heterogeneity. Could you comment on this aspect?", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "78UhsHcnCz", "reviewer": "Reviewer_Uj7L", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the generalization property of federated learning under the two-level distribution framework: client D_i is sampled from a meta-distribution P, and sample Z_i^j is sampled from D_i. Excess risk for unseen clients and semi-excess risk for seen data are analyzed under various conditions in high probability form. For VC major class, O(1/\\sqrt{mn} + 1/\\sqrt{m}) rate is  established; for stronger Bernstein condition, O(1/{mn} + 1/m) is achieved; for sub-Weibull/heavy tailed losses, O(1/{mn}^{1/4} + 1/m^{1/4}) rate is achieved. \n", "summary_of_the_review": "I like the topic of the paper, and the results seem to be reasonable. I would encourage authors to provide stronger motivation for analyzing generalization in FL under the proposed conditions, and the insights from these analysis. I will try to read in more detail for technical correctness and understand the difficulty of the analysis. \n", "strength_and_weaknesses": "The paper is generally well written and clear. I appreciate the summary in Table 1. Though I did not check the details of the proof, the results look reasonable. \n\nGeneralization in federated learning is a timely topic, and the two-level distribution analysis makes a lot of sense. \n\nI have a few “cliche” comments for a theoretical paper. \n\nMaybe I missed it, could the authors comment more on the connection to practice. Specifically, in table 1, compared to assumptions in previous papers, do new assumptions make more sense in practice? I understand that the results themselves are interesting: Lipschitz is probably more general than bi-classifiation; Bernstein can be more general than smoothness+SC (maybe?) and a probability form rather than expectation form is shown; sub-Weibull/heavy tailed losses are analyzed for the first time for FL. \n\nAnother bonus point: what are the main insights for federated learning? – it is nice to know that the risk gaps close when clients m and samples n are increased, but anything more? For example, what is the role of heterogeneity for seen and unseen clients? For semi-excess risk, why m and n seem to play a similar role? How does the assumptions interact with two-level distribution – any common or difference compared to centralized setting? \n", "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": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster