Generalization in Federated Learning: A Conditional Mutual Information Framework
Authors: Ziqiao Wang
Cheng Long
Yongyi Mao
Venue: ICML 2025 poster (2025)
Keywords: Generalization
Federated Learning
Information-theoretic generalization bounds
Primary area: theory->learning_theory
TL;DR: We provide conditional mutual information generalization bounds for federated learning

Abstract: Federated learning (FL) is a widely adopted privacy-preserving distributed learning framework, yet its generalization performance remains less explored compared to centralized learning. In FL, the generalization error consists of two components: the out-of-sample gap, which measures the gap between the empirical and true risk for participating clients, and the participation gap, which quantifies the risk difference between participating and non-participating clients. In this work, we apply an information-theoretic analysis via the conditional mutual information (CMI) framework to study FL's two-level generalization. Beyond the traditional supersample-based CMI framework, we introduce a superclient construction to accommodate the two-level generalization setting in FL. We derive multiple CMI-based bounds, including hypothesis-based CMI bounds, illustrating how privacy constraints in FL can imply generalization guarantees. Furthermore, we propose fast-rate evaluated CMI bounds that recover the best-known convergence rate for two-level FL generalization in the small empirical risk regime. For specific FL model aggregation strategies and structured loss functions, we refine our bounds to achieve improved convergence rates with respect to the number of participating clients. Empirical evaluations confirm that our evaluated CMI bounds are non-vacuous and accurately capture the generalization behavior of FL algorithms.

Generalization in Federated Learning:
A Conditional Mutual Information Framework
Ziqiao Wang'
Cheng Long²
Yongyi Mao
Abstract
1. Introduction
Federated learning (FL) has emerged as the most widely adopted distributed learning framework, enabling multiple (potentially spatially distributed) clients to collaboratively train global model (McMahan et al., 2017; Yang et al., 2019; Li et al., 2020; Kairouz et al.. 2021). Unlike central- ized learning, FL utilizes the computational resources of all participating clients while avoiding the need to aggregate all data in a single location before training. This not only re- duces the resource overhead associated with data collection but also enhances privacy protection.
Federated learning (FL) is a widely adopted privacy-preserving distributed learning frame- work, yet its generalization performance remains less explored compared to centralized learning. In FL, the generalization error consists of two components: the out-of-sample gap, which mea- sures the gap between the empirical and true risk for participating clients, and the participation gap. which quantifies the risk difference between par- ticipating and parttiicciii clients. In this work, apply an information-theorete analy- sis via the conditional mutual information (CMI) framework to study FL's two-level generalization. Beyond the traditional supersample-basee CMI framework, we introduce a superclient construc- tion to accommodate the two-level generaliza- tion setting in FL. We derive multiple CMI-based bounds, including hypothesis-band -asse CMI bounds, illustrating how privacy constraints in FL can im- ply generalization guarantees. Furthermore, we propose fast-rate evaluated CMI bounds that re- cover the best-known convergence rate for two- level FL generalization in the small empirical risk regime. For specific FL model aggregation strate- gies and structured loss functions, refine bounds to achieve improved convergence rates with respect to the number of participating clients. Empirical evaluations confirm that our evaluated CMI bounds are non-vacuous and accurately cap- ture the generalization behavior of FL algorithms.
In an FL framework, central server distributes global model to all participating clients for local training. In con- trast to centralized learning- where data typically follow a single distribution from heterogeneous distributions. The server then aggre- gates the updated local models to form new global model, which is redistributed for further training; this iterative pro- cess continues until convergence. While the convergence properties of FL have been extensively studied, such as in (Karimireddy et al., 2020; Li et al., 2020; Mitra et al., 2021; Yun et al., 2021; Wang & Ji, 2022), the study of its gen- eralization performance has only recently gained attention (Mohri al., 2019; Chen et al., 2021; Yagli et al., 2020;
data on different clients often arise
Barnes al., 2022; Hu et al., 2023; Huang et al., 2023; Sefidgaran et al., 2022; 2024; Sun et al., 2024; Gholami & Seferoglu, 2024) and remains relatively underexplored. Moreover, most FL generalization studies focus only on the generalization error of participating clients, overlooking the model's ability to generalize unseen clients.
Recently, Yuan et al. (2022) introduces a two-level gener- alization framework, where client distributions are drawn from a meta-distribution. Under this framework, the gen- eralization error is decomposed into two components: the out-of-sampel gap, measuring the gap between empirical and true risk for participating clients, and the participation gap, capturing the difference in true risks between partici- pating and uan--ariicipatingg clients. This broader definition extends the commonly used out-of-sample gap and is espe- cially relevant in cross-device FL scenarios, where clients are sampled from a large and dynamic population.
Schooo of Computer Science and Technology, Tongji Uni- versity, Shanghai, China 'Department of Applied Physics and Applied Mathematics, Columbia University. New York, USA "Shooo of Electrical Engineering and Computer Science, Uni- versity of Ottawa, Ottawa, Canada. Correspondence to: Ziqiao Wang <ziqiaowang @ @eoonji..duucc...
Proceedings of the 4nnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Conditional Mutual Information Framework for Federated Learning
Among many analytic tools, information-theoreti general- ization analysis, pioneered by (Russo & Zou, 2016; 2019; Xu & Raginsky, 2017), has the advantage of accounting for both the data distribution and the learning algorithm, often giving tighter generalization bounds compared to crrrbbttioo-nddeeddeenn or ggorithm-indeeendeen methods. The original mutual information (MI)-based generalization bounds in (Xu & Raginsky, 2017; Bu et al., 2020) have been applied to FL in (Yagli et al., 2020; Barnes et al., 2022; Zhang et al., 2024). However, it is well-known that these MI-based bounds suffer from unboundedness although the true generalization eπrоr can be small (Bassily et al., 2018). To address this issue, Steinke & Zakynthinou (2020) pro- poses the conditional mutual information (CMI) framework, which introduces a "supersample" construction. Here, an auxiliary "ghost sample" is drawn alongside the original training sample, and sequence of Bernoulli random vari- ables determines which data points are used for training. The CMI between these Bernoulli variables and the hypoth- esis (e.g., model parameters), conditioned on the supersam- ple, serves as a generalization measure. This construction ensures bounded CMI terms due to bounded entropy of Bernoulli variables, inherently leading to tighter generaliza- tion bounds compared to the standard MI-based methods, as shown in Haghifam et al. (2020). The CMI framework has seen multiple refinements, including fast-rate and numeri- cally tight bounds (Harrutunyan et al., 2021; Hellström & Durisi, 2022a; Wang & Mao, 2023a;e; 2024b; Dong et al., 2024). Despite the success of these CMI bounds, their effectiveness in capturing FL generalization is still not es- tablished.
eralization (cf. Lemma 3.2). In the special case of identical client data distributions, the bound reduces to a single CMI term (cf. Corollary 3.2), aligning with intuition. We also extend our framework to high- probability bounds (cf. Theorem 3.2) and excess risk analysis (cf. Theorem 3.3).
To improve the bound's convergence rate, we derive evaluated CMI (e-CMI) bounds (cf. Theorem 4.1), us- ing techniques from Wang & Mao (2023c). These bounds not only recover the best-known FL conver- gence rate in the low empirical risk regime, as shown in Hu et al. (2023), but also provide significant practi- cal advantages. Unlike hypothesis-basee CMI bounds that involve high-dimensional random variables, e- CMI bounds only require computing CMI between one-dimensional random variables, making them much easier to estimate in practice.
We extend our analysis to scenarios where model ag- gregation strategies (e.g., model averaging) and struc- tured loss functions play role. Specifically, follow- ing Barnes al. (2022), we derive a CMI bound un- der Bregman loss and show that both the participa- tion gap and out-of-sampll gap exhibit fast-rate con- vergence with respect to the number of participating clients (cf. Theorem 5.1). Further, inspired by Gho- lami & Seferoglu (2024), we establish a sharper CMI bound under strongly convex and smooth loss func- tions (cf. Theorem 5.2), demonstrating even faster de- cay rates for oft-of-sample gap.
In this work, we provide the first CMI generalization frame- work for FL in the two-level generalization setting. Inspired by the supersample-based CMI framework, we introduce an additional "superclient" construction, where clients are grouped into two sets, and Bernoulli random variables de- termine their participation. This symmetric structure en- ables CMI-based characterization of the participation gap, while the out-of-sample gap is analyzed using stan- dard supersample-bast based CMI techniques as in Steinke & Zakynthinou (2020). Our main contributions are as follows:
To verify our results, we conduct FL experiments us- ing FedAvg (McMahan et al., 2017) on two datasets. We show that our e e-CMI bounds are numerically non- vacuous and effectively capture the generalization be- havior FL.
2. Preliminaries
Notations Throughout this paper, unless otherwise stated, we use capital letters (e.g., X) to denote random vari- ables and the corresponding lowercase letters (c.g.. x) to denote realized values. Let Px be the distribution of X, and Pxir the conditional distribution of X given Y. When conditioning a specific realization, we write PxIy== or simply Px|N- We also use Ex and Erx in- terchangeably to denote the expectation over X ~ Px, whenever the underlying distribution is clear. Similarly, Exly=y (or Exlp) denotes the expectation with respect to X PxIY= Let DKL (PIlQ) be the HallbackkLeibblee (KL) divergence between P' and Q. Let L(X & be the mutual information (MI) be- tween X and Y, and I(X; Z)) the conditional mutual in- formation (CMI) between X and Y given Z. Following Ne-
Based on our superclient and supersamples construc- tion, we derive the first CMI-based generalization bound (cf. Theorem 3.1) for FL., consisting of two terms: (i) the CMI between the hypothesis and the Bernoulli variable governing client participation, and (ii) the CMI between the hypothesis and the Bernoulli variable governing training data membership. These terms reveal that FL models generalize well to un- seen clients when they leak minimal information about training data membership and client participation. Fur- thermore, we show that differential privacy constraints at both local and global levels naturally imply gen-
(P.y
2

---

Conditional Mutual Information Framework for Federated Learning
grea et al. (2019), we define the disintegrated mutual infor- mation for T=(X;) Y) A DEL (x. and note that [[;; 2| Ez (X:)).
average client empirical risk is given by
K Ls, (w) = Kn
1 K
[.s(w) A
kw, Zr.g):
Federated Learning Problem Setup We consider a fed- erated learning (FL) setup with K participating clients. Let 2 be the instance space, W the hypothesis space, and C a (possibly infinite) set of all potential clients. Each client E C has a local data distribution j4e on 2. Following Yuan et al. (2022), we assume that there is distribution 'D on C. referred to as "meetadiisrriuttion" in Yuan et al. (2022), and that K participating clients C12 C2...., CK are drawn independently from D. We will write client a (i E [K]) simply as i for simplicity, e-g.. write the distribution Me; P4
which serves as a practical proxy for the average client true risk of w because data distributions are unknown in real scenarios. Finally, for an FL algorithm A, we define its expected generalization error as
ED(A) - Ew [LD(W)] - Ew.s [Ls(
CMI Framework for FL. We now adapt the supersam- ple construction of Steinke & Zakynthinou (2020) to an FL setting by introducing superclient and corresponding supersamples for each client. Let jú be K x 2 matrix, namely the superclient, whose entries are drawn indepen- dently from the meta-distribution D. We index the columns of ju by {0, 1} and denote the i-th row by رr = (Hos (s,1)). Next, we construct a supersample for each client distribu- tion in j. For example, the supersample Z E zax2 for Pi,o has its entries drawn i.i.d from Hn.-- We index the columns of Z by {0, 1}. and write Z = (Z 2 for the j-th row. The same construction applies for all the other client distributions in j.. Thus, we have one su- perclient matrix jú and 2K supersample matrices in total. To determine which client distributions participate in the training, we introduce random variable V = {Vi) where each V; is drawn i.i.d. from (nif((0, 13) and is in- dependent of j.. If V, = 0. then the client distribution Ah. is included in the participating client set, and fu,11 is non- participating; if V; = 1, the opposite holds. For each client distribution, we further introduce U (U3 13-1 (with
of client as p4. Let S {Zm with Zr, iéd
denote the training dataset for client i, where for simplic- ity we have assumed that the training sets have the same size across all clients. In FL, each client i applies a local algorithm A, : - + W. described by the conditional distribution Pw.]s,- to produce a local model W; = (S;). Note that A; may differ across clients. These local models { are then transmitted plies an aggregation algorithm to produce global model W. Hence, an FL algorithm A is composed of all the lo- cal algorithms together with the model aggregation proce- dure. Denote S = S; The overall FL algorithm A is then conceptually characterized by a conditional dis- tribution Pwis. which takes the collective training sample as input and outputs hypothesis W W. Formally, A: zak + W. We measure the quality of W using loss function E: W x Z - Ey
central server, which ap-
E {0, 1)), where each U i.i.d Uni 1}) is indepen- dent of Z These variables specify which column in the supersample is used for training versus testing. For instance, when U/ 0, 2,0 part of the training set, and 2 is 240
We adopt the two-level generaliza- tion framework introduced in (Yuan al., 2022; Hu al., 2023), where the ultimate goal in FL is set to minimizing the true risk for unseen non- pon-patiicipating clients. Con- cretely, for any hypothesis w E W, the global true risk (or population risk) is defined as
Generalization Error
used for local testing: if UJS = 1, these roles are reversed. V. The set of participating client distribu-
Let V; tions is then pv { }KK and the set of corresponding supersamples is dentoed by ZV = {Z... 1K pon-taatiii client distributions are äy = {i |
(w)) & E LEw-DEZ-y [lW Z)].
Ji=1, while the
For the i-th participating client, we define its true risk and empirical risk as Ly, (w) & Ez-n, [[( 2)] and Ls, (w) A n "Σ= (ww Zi.s), respectively. For the sake of simplicity, we treat each client equally, then we define the average client true risk for the participating clients as
with supersamples ZV. Similarly, for each participating distribution Pa.., define U U : Its training sample (i.e. Sa) is Zyhh = 1 j. )/=1, and the corresponding test sample is 7lb (Zib
J. )
A 1 K Tup
Notably, the supersamples for the non-paaticipating clients, although well defined, are actually irrelevant, as none of those data are used in training. To improve readability, Ap- pendix A provides a visualization of our superclient and supersample construction (cf. Figure 2), along with a sum- mary of notations (cf. Table 1).
Typpe (10)
(w))
Σ
E Eziza, [[(
KL
where Z/ ~ (4 is an independent testing instance from the i-th participating client's distribution p4 Likewise, the
3

---

Conditional Mutual Information Framework for Federated Learning
3. tlyotheeis-based CMI Bound
symmetric-meaning W does not depend on the order of elements in the local training sets, a common assumption used in stabilitybassed generalization analysis (Bousquet & Elisseeff. 2002)-then the averaging over n. data points in (OG(A) can also be omitted.
As previously discussed, generalization in FL involves two levels: (i) generalizing from participating clients to unseen clients, and (ii) generalizing from the training data unseen data of the participating clients. Following (Yuan et al., 2022; Hu et al., 2023), we separate these two levels of generalization through the following decomposition:
3.1. First CMI Bound
The bounding steps for (AA) closely follow those in stan- dard centralized analysis, once Lemma 3.1 has been estab- lished.
(A() Ew [LD( - EW [Lnnng (W)
E Er (A):urriicccatiooonnn Gup
+ Ewrpcky Luung (W)] - E Ls(WW) (1)
We are now in a position to present the first CMI bound for FL..
Eog (f Gap
Theorem 3.1. Assume f(.,)) E [0, 1]. the following bound holds
The participation gap, denoted as (A)) quantifies the difference in test performance between non- non-partionn participating and participating clients. The out-le- gap (also called participation error in (Hu et al., 2023)), denoted as Eog (.A). represents the average of the local generalization gaps over the K participating clients. Note that most existing FL generalization studies focus primarily
K
ED(A))
1 S
Σ
E z) . V 21 (W:V))
K
K
E M. 21 (W:
+ Kn
Eog (A) (Yagli et al., 2020; Barnes et al., 2022: Chor et al., 2023; Sefidgaran et al., 2022; 2024; Sun et al., 2024).
The bound consists of two terms, each providing an up- per bound for (Aa(A) and Eog(A), respectively. No- tably, both CMI terms in the bound preserve the prop- erties of the standard CMI from Steinke & Zakynthinou (2020). For example, T² (W; Vi) S H(V*) = log 2 and (W:U, S H( = log 2, where H-)) denotes the Shannon entropy (Thomas & Joy, 2006). Consequently, unlike previous MI-based FL generalization bounds (Yagli et al., 2020; Barnes et al., 2022: Zhang et al., 2024) that can grow unbounded (see Bassily et al. (2018)), our CMI-based bound in Theorem 3.1 is strictly bounded.
Under our construction of the superclient and supersamples in FL. the following lemma will be handy in our analysis.
Lemma 3.1. The participation gap (PG(A) can be rewrit- ten as
K (-1)% ((WW ZW. Z 1.0 -(
1,0,0) )
E
KL
where the expectation is taken over P Pz.uu...v 7 (7:0, Z and U (U%0 ).
Furthermore, if both CMI terms are zero, then the algo- rithm's 's output is independent of its input (i.e., independent of the chosen participating clients and their local training data). In contrast, if they achieve their upper bounds, the algorithm reveals all membership information about the clients and their local training sets. Specifically, the first CMI term quantifies how well one can infer the membership of the "participating client set" from the output hypothesis when (2', u²) are known, whereas the second term quantifies how well one can infer the membership of the "local training set" when (#', ff,0;) are given. Clearly, if the FL algorithm A enforces privacy constraints that make these inferences (i.c. determining V, and U2:Vi) difficult, then both CMI terms small generalization error; in other words, privacy implies generalization in FL.. Inspired by (Cuff& & Yu, 2016; Barnes et al., 2022), when FL algo- rithms are differentially private (Dwork et al., 2006a;b), this connection is formally established in the following lemma.
The our-of-sample gap (AG(A) can be rewrilten
n E (-1)03%
<(W, - ZWW
Kn
where the expectation is taken over Pzz. Vo..u.
Remark 3.1. Notably, by the symmetric property of superclient and supersamples, Lemma 3.1 indicates that and E(W, 23,0))
R * (-1) (E(W, Zid Z.W. ((W, ((W, Z 21,07,0)
EK EE Kn.
((WW,
remain small, resulting
are unbiased estimators for (A) and Eog respec- tively. We remark that the subscript index "1 in z
1,
and 7 1 can be replaced with any other j E [n)], as the participation gap does not depend on the order of elements in the testing datasets. Furthermore, if the algorithm is
Lemma 3.2. If each local algorithum A, is e e--differentially private, and the overall FL. algorithm is d'differentially

---

Conditional Mutual Information Framework for Federated Learning
private, then
Corollary 3.2. If|c| 1, then we have
K
min (c', "e" 1)e²}
E u.
12:00(W sV
21(W;U
K
[ED(A))
Kn
min (e's - 1)
E B. (W: sV Σ TI
Corollary 3.2 recovers the standard CMI bound of Steinke & Zakynthinou (2020) when the total dataset size is Kn. also highlights that the first term in Corollary 3.1 quantifies the effect of heterogeneity on FL generalization.
n
1=1
Remark 3.2. Combining Lemma 3.2 with Theorem 3.1
implies the bound [ED(A)] S O ( *
showing that A admits a valid generalization guarantee under differential privacy. We remark that it is possible to obtain e' using all e, for certain FL algorithm, studied in Kairouz et al. (2015). If we let 6 for all i, then we ob-
3.2. High Probability CMI Bounds
Our previous bounds are all provided on the expected gen- eralization error. However, classical learning theory often focuses on high-probability (PAC-style) bounds (Shalev- Shwartz & Ben-David, 2014). In what follows, we establish high--proabiiltyy CMI-based generalization bound for FL. Specifically, the theorem below is the high-prood bigh-probbbility ana- log of Corollary 3.1, featuring a square-root dependence.
Barnes et al. (2022) also provides privacy- based result bounding Eog(A),
tain |ED(A)) S O VV&+V=)
showing that when certain model aggregation strategies and loss functions are used, (A) S O ( We will discuss their setting in Section 5.
Theorem 3.2. Assume ((.--) E [0, 1], and let Pwiž,u. be the the conditional distribution of W given (Z,U, V). Ev [Pwzzuv] and let Pwiž.y
Let Ō = 1 == (U be the collection of all Bernoulli variables for determining sample usage. The following CMI bound follows from Jensen's 's inequality and the chain rule of MI. (0, 11. then the following
M= be the collection of all supersamples and
Let P PwIZu Ey [Pwiz.v]] Then, with probability at least 8 under the draw of (Z, U,V). the generalization error Ew Z.u.v (LD(W)LsssW)) is upper bounded by
Corollary 3.1. Assume E(:,-) E bound holds
21(W: V(Ž,U) K
21(W: UIZ.V)
(Ep(A)) S
Kn
2DKL (Pwiz,u.llPPwzz (w + 2 log >/K
Hence, achieve rate of order' O ( (RR VKn Re-
K-1
cently, Zhang et al. (2024, Theorem 5.1) presents a MI- based FL bound of the form O I(W
2DkL Ml + 2 -2llggg VKn
(sW:S) Kn
+
Kn-
which is the input-output mutual information (IOMI) (Xu &
Raginsky, 2017) version of our Corollary 3.1. Since CMI is always no larger than the corresponding IOMI counterpart (Haghifam et al., 2020, Theorem 2.1), our bound is always tighter than Zhang et al. (2024, Theorem 5.1). Additionally, as a by-product, we also provide a novel IOMI bound for FL in Theorem C.2 in Appendix.
Notice that the second term in the bound has the rate O (()) matching the PAC-Bayesian bound of Sefidgaran et al. (2024, Theorem 3.1) for a bounded loss.
3.3. Excess Risk Bound
In addition to standard generalization error, we now study the excess risk for FL. Specifically, let w" arg mingew EnnDEEz~ [f(w, Z)] be a global risk mini- mizer under the meta-distribution D. Note that w" may not be unique. The expected excess risk is then
Before moving on, let us consider the i...d. (homogeneous) FL setting. Intuitively, if all clients share the same data dis- tribution, then the first CMI term which bounds (AA) should vanish. In particular, when each μ4 is identical, V; no longer influences the algorithm's 's output distribution once 7' and & are given. The corollary below formalizes this intuition.
EER(A) & Ew [LD(W)] - -EE-DEZ~p [e(w" Z)].
Moreover, we focus on the ERM setting, i.e., the FL algo- rithm A outputs a hypothesis W that minimizes the empiri- cal risk (s) for the participating clients. The expected generalization bound and high bighbbrobability generalization bound for ERM FL. algorithm's 's excess risk are given next.
'In this paper, due to the absence of explicit decay rates for the CMI or MI terms, we often follow previous works by simply treating these terms O() when stating order-wise behavior. However, it should be noted that the actual decay of the bound is likely to be faster than the rate presented.
5

---

Conditional Mutual Information Framework for Federated Learning
Theorem 3.3. Assume E(;,)) E [0, 1), then for any ERM FL learning algorithm A, the following bound holds
rem 4.1 such that the following bound holds,
Ew [ [Ls( + I(W; VIŽ,
O3K
21(W: V.VVVIZ.U)
NTWWUIZ.V
C)(W:U1Z,V) +
(ER(A) S
K
Kn
CjKn
When the average empirical risk Ew.s [W)) is suf- ficiently small, this bound suggests a fast rate of order O ( + xt)). Unlike (Barnes et al., 2022; Gholami & Seferoglu, 2024). our fast-rate result does not require any specific loss function structure beyond boundedness. Simi- lar fast-rate behavior of generalization error under additional conditions (e.g., Bernstein condition, uniform entropy on W) is also observed by Hu et al. (2023) for Lipschitz losses. In fact, we expect our fast-rate bounds could be extended (e.g., via the variance-based and sharpness- based analyses in (Wang& & Mao, 2023c; Dong et al., 2024) or binary-Kr bound in (Hellström & Durisi, 2022a;b; Hellström & Guedj, 2024)), relaxing the need for strictly small empirical risk.
Furthermore, with probability at least 1 - 8 under the draw of (Z,U,V),
log A
B B (LD(W) Ex [l(w", Z)]l S V
2Kn
where E is the upper bound given in Theorem 3.2.
Thus, in the absence of additional assumptions, the excess risk for the ERM algorithm exhibits an O ( + vkm) convergence rate.
4. Fast-rate Evaluated CMI Bounds
5. CMI Bounds for Model Aggregation in FL
The above bounds show a rate of O + Vkr)), we now improve this rate. Thanks to the symmetric property of su- perclient and supersamples, we are able to adopt the single- loss technique from Wang & Mao (2023c). This gives us variant of the evaluated CMI (e-CMI) bound (Steinke & Zakynthinou, 2020; Hellström & Durisi, 2022a).
In the previous analysis, the learning algorithm A is treated as a black-box, where only the inputs and outputs of the algorithm are considered. In this section, we extend the analysis to account for interactions and communications between clients by incorporating model aggregation in FL. Here, we follow the setting in Barnes et al. (2022), where the aggregation is simply the average of all local models, namely W = K dAvg algorithm (MeMahan et al., 2017). Note that the results obtained in this section can be easily generalized to the case of uneven weights, which corresponds the setting in agnostic federated learning (Mohri et al., 2019).
Theorem 4.1. Assume E(.,)) [0, 1]. Denote the random variables L E(W, 22.0 (, and L,+t =[(,, 2
1 ΣK W,, which corresponds to the Fe-
then there exist constants C₁ C2 C2,Ca, C4 E [C1, C2 >
1, C3, C4 > Ole- (0c=00s0r + 2Oss < 22050s + +e200 20s <
such that the following bound holds,
K Σ
I(L:VV)
To demonstrate that increasing the number of clients K can significantly reduce the generalization error of an FL algorithm in certain scenarios, Barnes et al. (2022) assumes Bregman loss. Specifically, for strictly convex function f : 12d + I. the Bregman divergence between x, y R² is defined as: Dy (z, y) & f(x) f(y) (V (v), y) (Bregman, 1967). A Bregman loss is then defined based on the Bregman divergence, i.e. E(w, 2) = (y
Ew [LD(W)] SC,CoB.. [Ws(W]]+ +
C&K
C,Kn
Notably, the square-root functions are removed from the CMI terms, at the cost of a multiplicative factor C2 C2 to the average client empirical risk Ew,s s [Ls (W)). Another advantage of the e-CMI bound is that it involves only one- dimensional random variables, unlike the hypothesis-based CMI bound, where W is high-dimensional random vari- able. This makes e- CMI significantly easier to estimate in practice. Moreover, by the data-procee processing inequality, a fast-rate hypothesis-base based CMI bound is established below.
While Barnes et al. (2022) proves that [Eo)(A) decays with a fast rate with respect to K, the following result shows that under a Bregman loss, the overall generalization er- ror (AA) for an FL algorithm using model averaging achieves such a fast convergence rate with respect to K, namely both (Eoc(A)) and (E))(A) exhibit this fast rate. Theorem 5.1. Let E(w, 2) = (w, z), and assume that
(i) (-1)%² (C(W., 2411 (,at.a) e(W,, 24.0 2(0.))) is of-sub- Gaussian under Pv: 69 Pw. at for any i,
Corollary 4.1. Assume f(..-) E [0, 1]. then there exist constants C1, C2, Ca, C4 satisfying the conditions in Theo-
6

---

Conditional Mutual Information Framework for Federated Learning
(i) (-1)01 (e(W,, shri) E(W,, 2/01) is oig-sud Gaussian under P Pu @ Pw. for any i. Then, for A using model averaging,
ity beyond nonparametric algorithms. Recently, Gholami & Seferoglu (2024) achieves an even faster decay rate for [A) by using smooth and strongly convex loss func- tion. Building on their assumptions and techniques, we extend this analysis in an information-theorrticc framework. Additionally, we assume that each participating client's 's lo- cal algorithm is an interpolating algorithm (i.e., achieving zero empirical risk). This leads to the following result.
K
(DD(A) -
2
Un Vi) V U
K2
K
+ Kan
E Z. V 20 M. (WW
Theorem 5.2. Let E(:.-) E [0,1] be I-smooth and a-- strongly convex in W, and let A, be an interpolating al- gorithm for each client i. Let 7 log2
21. then
Remark 5.1. The assumptions given in (i-ti) are weaker than the boundedness assumption for the loss function, if E is bounded, then the difference between two losses is also bounded, which is guaranteed to be sub-Gaussian. In the case of heavy-tailed losses, additional techniques such as truncation (Dong et al., 2024) would be required to ensure the results hold. Furthermore, Theorem 5.1 can be interpreted as an end-to-end generalization bound for single round of FedAvg. Extending it multi-round setting is straightforward by sollowing the same approach used in Barnes et al. (2022, Corollary 3).
S [E0G(A)]
IW: (7.
K
2/7 + K2n =1
K
E (eWW, Uw) Vi).
Clearly, the decay rate with respect to K in this bound is even faster than that for [A))(A) in Theorem 5.1. Note that the boundedness assumption can be relax to sub- uub-Gaussianity (i.e., an "almost bounded" case). The assumption of an in- terpolating algorithm is also practical due to the widespread use of overparameterized deep neural networks in modern deep learning scenarios.
Compared to the results in Section 3, Theorem 5.1 intro- duces two notable distinctions. First, the global CMI terms (i.e.. CMI based on W) are replaced by local CMI terms (i.e., CMI based Wt). Second, an additional K factor appears in the bound, resulting in a faster convergence rate. While the data- proccssinns inequality indicates that global CMI terms are smaller than local CMI terms, the specific model aggregation strategy and loss function allow us to explicitly observe this fast-rate behavior.
Regarding the local CMI term I(W;; Vi [2 Vi) in The- orem 5.2, note that in our single-round setting, the local model is trained independently and does not communicate with other clients. As a result, the CMI term associated with client i is, by construction, independent of the CMI terms of other elients. reflects only the relationship between a sin- gle client's data and its corresponding model and therefore does not, in general, provide direct definitive measure of cross-client data heterogeneity. However, if the data dis- tribution itself is governed by a heterogeneity parameter, as in the experimental setup of Sun et al. (2024), then the value of this CMI term may indeed vary with that parameter, as it ultimately depends on the underlying data distribution.
Particularly, in this setting, we rely solely on local pri- vacy constraints to guarantee generalization. For exam- ple, if each A, is e-differentially private for all i, then we obtain [AA) < O ( K /S), where the derivation is nearly the same to Lemma 3.2, and the max- imum value of the sub-Gat Gaussian variance proxies is con- sidered. This result clearly improves upon the bounds in Section (cf. Remark 3.2). Additionally, Barnes et al. (2022) also presents a communication constraint-based re- sult, which can also be applied to the overall FL general- ization error. Specifically, if each client i can only trans- mit B bits of information to the central server, then each W. can take at most 2n distinct values after quantization. In this case, 1 "0' (W;; Vi) < ((W)) S B log 2 and IWW;; U..V ()) < B log As result, the general- ization error is bounded by |ED(A)) S O x +
Moreover, the use of smooth and strongly convex loss func- tions, often employed to ensure the linear convergence of gradient descent (GD), has also been studied in the con- text of personalized FL generalization. For example. Chen et al. (2021) shows that if the data heterogeneity- measurd as the minimum average (squared) Le distance between global model parameters and optimal local parameters- is mild, then FedAvg achieves minimax optimality. In Theorem 5.2, data heterogeneity is captured by the factor E [&W, 21,))] in the second term of the bound. In fact, if A; does not interpolate the training data, this factor is replaced by E [e(W, Z,,)] - [[e(W,, Zz.)).. When this factor van- ishes, i.c., when data heterogeneity is negligible, the second term (which contains the square-root function) becomes neg-
Although many popular loss functions, such as the squared loss and KL divergence, can be regarded as special cases of Bregman divergence (Yamane et al., 2023), the Breg- man loss D (w, 2) used above requires w and & to have the same dimension. This requirement may limit its applicabil-
7

---

Conditional Mutual Information Framework for Federated Learning
ligible, and the first term (with faster rate, e.g.. O (x+) for communication constraint) dominates the bound. This observation aligns with Chen et al. (2021), showing that FedAvg performs better when data heterogeneity is low.
rounds (which reduces the commonly used 1000 rounds to lower computational costs). Additionally, we apply patho- logical non-lID data partitioning scheme as in McMahan et al. (2017); data are sorted by label, split into 200 shards of size 300, and each client is randomly assigned 2 shards, and we evaluate prediction error as our performance metric, i.e. we utilize the zero-one loss function to compute gener- alization error. During training, we use cross-entropy loss surrogate to enable optimization with gradient-based based methods. Since we pre-define the non-participating clients from the superclient, all participating clients are included in every round of training.
Additionally, we remark that extending a similar analysis to bound [E))(A) is not straightforward. This would require that, for each client, there exists minimizer that achieves a zero-gradient signal for any unseen local data, which is generally not guaranteed.
6. Empirical Verification
In this section, we empirically evaluate the effectiveness of our CMT bounds by comparing them to the expected gener- alization gap. Specifically, we estimate the fast-rate e-CMI bound for FL, as presented in Theorem 4. 1, referred to as the Fast-rate Bound in our experiments. Additionally, due to the challenges associated with estimating MI when deal- ing with high-dimensional random variables, we compute an evaluated version of the CMI bound from Theorem 3.1. This e-CMI bound, derived in Theorem G.I (in Appendix), serves as a lower bound for Theorem 3.1 and is denoted as the Square-root Bound in our experiments. Our experi- mental setup, particularly the construction of supersamples, closely follows previous works (Harutyunyan et al., 2021; Hellström & Durisi, 2022a; Wang & Mao, 2023c; 2024b; Dong et al., 2024), and we construct the superclient in a sim- ilar manner. For the FL learning process, we implement Fe- dAvg following the federated training protocol of McMahan et al. (2017), with modifications reduce computational overhead. We conduct image classification experiments two datasets: MNIST (LeCun et al., 2010) and CIFAR-10 (Krizhevsky, 2009). The details of our experimental setup and results are presented below.
The complete experiment details including other hyperpa- rameter settings and CMI estimation can be found in Ap- pendix H.
0.25
0.35
0.10
0.330
0.05
0.05
0.00
100
0.00
(a) MNIST (n)
(b) MNIST (K)
0.8
0.6
0.4
Scarr val
0.4
02
02
(c) CIFAR-IO (1)
(d) CIFAR-10 (K)
Figure 1: Verification of bounds on MNIST and CIFAR-
10. (a-b) Results on MNIST with different n and K. (c-d) Results on CIFAR-I0 with different n and K.
6.1. Experiment Setup
For the MNIST digit recognition task, we train a CNN with approximately 170K parameters. Each local training algorithm A, trains this model using GD. For CIFAR- 10, we use the same CNN model from McMahan et al. (2017), which has approximately 10 parameters. As also discussed in McMahan et al. (2017), the SOTA models, such as vision transformers (ViTs) (Dosovitskiy et al., 2021), achieve over 99% accuracy on CIFAR- However, since our focus is on verifying generalization bounds rather than achieving SOTA performance, training a ViT-scale model would be unnecessarily costly. Therefore, a simple CNN suffices for our purpose. Each local training algorithm A, trains the CNN model using mini-batch SGD.
6.2. Results
Figure 1 presents the estimated expected generalization gap alongside our CMI bounds. Notably, both CMI bounds are non-vacuous, meaning they remain below the upper bound of the loss function (i.c., 1). More importantly, they effectively capture the generalization behavior of the FL learning algorithm and are numerically very close to the ex- pected generalization gap. For MNIST, where the algorithm achieves a small training error, the fast-rate bound from The- orem 4.1 performs significantly better than the square-root CMI bound in Theorem 3.1 in this low empirical risk regime. On CIFAR-10, since we use a simple CNN model and limit the number of communication rounds, the empirical risk remains negliggigi In this case, we observe that the evaluated version of Theorem 3.1 outperforms Theorem 4.1
For both of the classification tasks, clients train locally for five epochs per round before sending their models to the central server, with training spanning 300 communication
8

---

Conditional Mutual Information Framework for Federated Learning
in most settings. While the tightness of e-CMI bounds in standard centralized i.i.d. learning has been observed in pre- vious works (Harutyunyan et al., 2021; Hellström& & Durisi, 2022a; Wang & Mao, 2023c; Dong et al., 2024), our results confirm that CMI bounds remain numerically tight in FL..
key difference in problem setup: their meta-learning frame- work requires the meta-learner (i.e., the global model W) to be further trained on the test tasks (i.e., previously non- participating clients), whereas in FL, the global model is evaluated directly on unseen clients without any additional local fine-tuning, To enable a direct comparison with Hell- ström Durisi (2022b), our CMI framework would need to be extended to the personalized FL setting, where local adaptation of the global model is permitted.
7. Other Related Literature
Federated Learning Methods FedAvg (McMahan al.,
2017) is one of the earliest and most widely used FL algo- rithms. However, its performance degrades significantly in non-i.id. settings, To mitigate this issue, FedProx (Li et al., 2020) introduces a regularization term, ||w - will, which helps stabilize updates and reduce divergence among local models. In fact, the squared form of this regularization term naturally arises in the derivation of our Theorem 5.2 (see Appendix F.2), and when the CMI term in Theorem 5.2 is small, this regularization term also tends to be small. An- other approach, SCAFFOLD (Karimireddy et al., 2020), tackles data heterogeneity using variance reduction tech- niques to improve convergence. FedOpt (Reddi et al., 2021) extends adaptive optimization methods to FL., enabling more efficient learning dynamics, while FedNova (Wang et al., 2020) introduces a normalized averaging scheme to mitigate objective inconsistencies while preserving fast training con- vergence. More recently, leveraging information -theoorrttt analysis, FedMDMI (Zhang et al., 2024) incorporates a global model-data MI term as a regularizer to improve gen- eralization performance. Beyond these methods, numerous other FL algorithms have been proposed, we refer readers to (Huang et al., 2024; Solans al., 2024) for recent advances.
8. Concluding Remarks
In this paper, we present novel CMI bounds for FL in the two-level generalization setting. Empirical results show that our e-CMI bounds are numerically non-vacuous. Future re- search directions include exploring the relationship between model aggregation frequency and local updates through CMI analysis, and extending our framework to accommo- date unbounded loss functions beyond the sub-Gaussianity.
Acknowledgements
The authors would like to thank the anonymous AC and reviewers for their careful reading and valuable suggestions. The authors acknowledge the use of GPT-4o to assist in polishing the language of this work. All Al-generated text was carefully reviewed and edited by the authors, who take full responsibility for the final content of the paper.
Impact Statement
The primary focus of our work is on advancing the theo- retical foundations of federated learning, aiming to deepen our understanding of this field. As with most theoretical work, it inherently presents challenges in explicitly high- lighting potential societal consequences. Meanwhile, the proposed theoretical framework, particularly in privacy con- straint based results, may find application in related research domains like trustworthy AL While the theoretical results in such domains could have positive societal impacts, it's cru- cial to acknowledge the potential for misuse. The research community plays a vital role in delivering guidance on re- sponsible and ethical applications to navigate the evolving landscape of technology responsibly.
Generalization Theory in Federated Learning Recent research has increasingly focused on understanding gener- alization in FL. In addition to works in (Chen et al., 2021; Hu et al., 2023; Yagli et al., 2020; Barnes et al., 2022; Gho- lami& & Seferoglu, 2024; Zhang et al., 2024), which we have discussed throughout the paper, several other studics pro- vide new insights. Sefidgaran et al. (2022; 2024) introduce wwdd--ttttoobbaseeeeee generalization bounds for FL, with Sefidgaran al. (2024) demonstrating that increasing the frequency of communication rounds does not always reduce generalization error and, in some cases, may even degrade generalization performance. Stability-based generalization analysis has also been explored in FL. For instance, Sun et al. (2024) analyze the impact of data heterogeneity, conclud- ing that greater heterogeneity leads to higher generalization error. It is also worth noting that generalization theory in meta-learming is closely related to FL. Particularly, personal- ized FL can be viewed as a variant of meta-learning (Fallah et al., 2020). In fact, our CMI framework is inspired in part by a recent Casebased generalization bound for meta- learning proposed in Hellström & Durisi (2022b). However, our results are not directly comparable to theirs due to a
References
Barnes, L. P., Dytso, A., and Poor, H. V. Improved informa- tion theoretic generalization bounds for distributed and federated learning. In 2022 IEEE International Sympo- sium Information Theory (ISIT), pp. 1470. IEEE, 2022.
Bassily, R., Moran, S., Nachum, I., Shafer, J., and Yehuday-

---

Conditional Mutual Information Framework for Federated Learning
off, A. Learners that use little information. In Algorithmic Learning Theory. PMLR, 2018.
Dwork, C., McSherry, F., Nissim, K., and Smith, A. Cal- ibrating noise sensitivity in private data analysis. In Theory of Cryptography; Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pp. 265-284. Springer, 2006b.
Bousquet, O. and Elisseeff, A. Stability and generalization. The Journal of Machine Learning Research, 2:499-526, 2002.
Fallah, A., Mokhtari, A., and Ozdaglar, A. Personalized federated learning with theoretical guarantees: A model- agnostic meta-learning approach. Advances in neural information processing systems, 33:3557-3563 2020.
Bregman, L. MM. The relaxation method of finding the com- mon point of convex sets and its application to the solu- tion of problems in convex programming. USSR com- putational mathematics and mathematical physics, 7(3): 200-217, 1967.
Gholami, and Seferoglu, H. Improved generalization bounds for communication efficient federated learning. arXiv preprint arXiv:2404. 1754, 2024.
Bu, Y., Zou, S., and Veeravalli, V. V. Tightening mutual information- based bounds on generalization error. IEEE Journal on Selected Areas in Information Theory, 1(1): 121-130, 2020.
Haghifam, M., Negrea, J., Khisti, A., Roy, D. M., and Dz- iugaite, G. K. Sharpened generalization bounds based conditional mutual information and application to noisy, iterative algorithms. Advances in Neural Informa- tion Processing Systems, 2020.
Chen, S., Zheng. Q., Long, Q., and Su, J. J. A theorem of the alternative for personalized federated learning. arXiv preprint arXiv:2 2021.
Chor, R., Sefidgaran, M., and Zaidi, A. More communi- cation does not result in smaller generalization error in federated learning. In 2023 IEFE International Sympo- sium on Information Theory (ISIT), pp. 48-53. IEEE, 2023.
Harutyunyan, H., Raginsky, M., Steeg. G. V., and Galstyan, A. Information-theorele generalization bounds for black- box learning algorithms. In Advances in Neural Informa- tion Processing Systems, 2021.
Hellström, F. and Durisi, G. A new family of generalization bounds using samplewise evaluated CMI. In Advances in Neural Information Processing Systems, 2022a.
Cuff, and Yu, L. Differential privacy mutual informa- tion constraint. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pp. 43-54, 2016.
Hellström, F. and Durisi, G. Evaluated CMI bounds for meta learning: Tightness and expressiveness. In Oh, A. H., Agarwal, A., Belgrave, D., and Cho, K. (eds.), Advances in Neural Information Processing Systems, 2022b. URL https:/ openreviewweeweeeeeeeeeeeereeewe net forum? id=5Cpune8BTW).
Dong, Y. Gong, T., Chen, H., Yu, S., and Li, C. Rethinking information-theorele generalization: Loss entropy in- duced PAC bounds. In The Twelfth International Confer- ence on Learning Representations, 2024. URL https: / //openreview wet.riiwweeeeeeeeee forum? wdd.dddiww2iuuu...........
Donsker, M. D. and Varadhan, S. S. Asymptotic evaluation of certain markov process expectations for large time. iv. Communications on pure and applied mathematics, 36 (2):183-212, 1983.
Hellström, F. and Guedj, B. Comparing comparators in generalization bounds. In International Conference on Artificial Intelligence and Statistics, pp. 73-81, PMLR, 2024.
Dosovitskiy, A., Beyer, L., Kolesnikov, A., Weissenbom, D., Zhai, X., Unterthiner, T., Dehghani, M., Minderer, M., Heigold, G., Gelly. S., Uszkoreit, J., and Houlsby, N. An image is worth 16x 16 words: Transformers for image recognition at scale. In International Conference on Learning Representations, 2021.
Hoeffding, W. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13 1963.
Hu, X., Li, S., and Liu, Y. Generalization bounds for fed- erated learning: Fast rates, unparticipating clients and unbounded losses. In The Eleventh International Confer- ence on Learning Representations, 2023. URL https: / // //openrevis ew net. forum? d= E.HoysUUU..
Dwork, C., Kenthapadi, K., McSherry, F., Mironov, I., and Naor, M. Our data, ourselves: Privacy via dis- tributed noise generation. In Advances in Cryptology- EUROCRYPT 2006: 24th Annual International Confer- ence on the Theory and Applications of Cryptographic Techniques, St. Petersburg, Russia, May 28-June 1, 2006. Proceedings 25, pp. 486-503. Springer, 2006a.
Huang, W., Shi, Y., Cai, Z., and Suzuki, T. Understand- ing convergence and generalization in federated learning through feature learning theory. In The Twelfth Interna- tional Conference on Learning Representations, 2023.
10

---

Conditional Mutual Information Framework for Federated Learning
Huang, W., Ye, M., Shi, Z., Wan, G., Li, H., Du, B., and Yang, Q. Federated learning for generalization, robust- ness, fairness: A survey and benchmark. IEEE Trans- actions on Pattern Analysis and Machine Intelligence, 2024.
Russo, D. and Zou, J. Controlling bias in adaptive data anal- ysis using information theory. In Artificial Intelligence and Statistics. PMLR, 2016.
Russo, D. and Zou, J. How much does your data explo- ration overfit? controlling bias via information usage. IEEE Transactions on Information Theory, 66(1):302- 323, 2019.
Kairouz, P., Oh, S., and Viswanath, P. The composition the- orem for differential privacy. In International conference on machine learning, pp. 1376- 1385. PMLR, 2015.
Sefidgaran, M., Chor, R., and Zaidi, A. Rate-distortion theoretic bounds on generalization error for distributed learning. Advances in Neural Information Processing Systems, 35:19687-19702, 2022.
Kairouz, P., McMahan, H. B., Avent, B., Bellet, A., Bennis, M., Bhagoji, A. N., Bonawitz, K., Charles, Z., Cormode, G., Cummings, R., et al. Advances and open problems in federated learning. Foundations and trends& in machine learning, 14(1-2)11-10,, 2021.
Sefidgaran, M., Chor, R.. Zaidi, A., and Wan, Y. Lessons from generalization error analysis of federated learning: You may communicate less often! In Forty-firs: Interna- tional Conference on Machine Learning, 2024.
Karimireddy, S. P., Kale, S., Mohri, M., Reddi, S., Stich, S., and Suresh, A. T. Scaffold: Stochastic controlled averag- ing for federated learning. In International conference machine learning, pp. 5143. PMLR, 2020.
Shalev-Shwartz, S. and Ben-David, S. Understanding ma- chine learning: From theory to algorithms. Cambridge university press, 2014.
Krizhevsky, A. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
Solans, D., Heikkila, M., Vitaletti, A., Kourtellis, N., Anag- nostopoulos, A., Chatzigiannakis, I., et al. Non-iid data in federated learning: A systematic review with taxon- omy, metrics, methods, frameworks and future directions. arXiv preprini arXiv:2411. 123777 2024.
LeCun, Y., Cortes, C., and Burges, C. Mnist hand- written digit database. ATT Labs [Online]. Available: http://yannleccun.cmmm cww..//////xddmiiisstt.. 2, 2010.
Li, T., Sahu, A. K., Zaheer, M., Sanjabi, M., Talwalkar, A., and Smith, V. Federated optimization in heterogeneous networks. Proceedings of Machine learning and systems, 2:429-450 2020.
Steinke, T. and Zakynthinou, L. Reasoning about general-
ization via conditional mutual information. In Conference on Learning Theory. PMLR, 2020.
Sun, Z., Niu, X., and Wei, E. Understanding generalization of federated learning via stability: Heterogeneity matters. In International Conference on Artificial Intelligence and Statistics, pp. 676-684. PMLR, 2024.
McMahan, B., Moore, F., Ramage, D., Hampson, S., and y Arcas, B. A. Communication-effiicee learning of deep networks from decentralized data. In Artificial intelli- gence and statistics, pp. 1273-1282. PMLR, 2017.
Thomas, M. and Joy, A. T. Elements of information theory. Wiley-Interscience, 2006.
Mitra, A., Jaafar, R., Pappas, G. J., and Hassani, H. Lin- car convergence in federated learning: Tackling client heterogeneity and sparse gradients. Advances in Neural Information Processing Systems, 34:1 11144666619999 2021.
Wainwright, M. J. High-dimensional statistics: A non- asymptotic viewpoint, volume 48, Cambridge university press, 2019.
Mohri, M., Sivek, G., and Suresh, A. T. Agnostic feder- ated learning. In International conference on machine learning, pp. 4615 4625-4625. PMLR, 2019.
Wang. J., Liu, Q., Liang, H., Joshi, G., and Poor, H. V. Tack- ling the objective inconsistency problem in heterogeneous federated optimization. Advances in neural information processing systems, 33:761 1-7623, 2020.
Negrea, J., Haghifam, M., Dziugaite, G. K., Khisti, A., and Roy. D. M. inormatioonthhorede generalization bounds for sgld via data detendeennddnt estimates. Advances in Neural Information Processing Systems, 2019.
Wang. S. and Ji, M. A unified analysis of federated learning with arbitrary client participation. Advances in Neural Information Processing Systems, 35:19124-19137, 2022.
Reddi, S. J., Charles, Z., Zaheer, M., Garrett, Z., Rush, K., Konečný, J., Kumar, S., and McMahan, H. B. Adap- tive federated optimization. In International Confer- ence on Learning Representations, 2021. URL https: / //openreview. net. wtw.e//ooooomdooeeeereeoa
Wang, Z. and Mao, Y. Sample-conditioned hypothesis stabil- ity sharpens anformation-theoreee generalization bounds. In seveth- Conference on Neural Information Pro- cessing Systems, 2023a.

---

Conditional Mutual Information Framework for Federated Learning
Wang, Z. and Mao, Y. Information-theoretic analysis of unsupervised domain adaptation. In International Con- ference Learning Representations, 2023b.
Wang, Z. and Mao, Y. Tighter information-theoreet gen- eralization bounds from supersamples. In International Conference Machine Learning. PMLR, 2023c.
Wang, Z. and Mao, Two facets of sde under an information-theorest lens: Generalization of sgd via training trajectories and via terminal states. Proceed- ings of the Fortieth Conference Uncertainty in Artifi- cial Intelligence, 2024a.
Wang. and Mao, Generalization bounds via conditional SfS-information. In The Thirty-eigtth Annual Conference on Neural Information Processing Systems, 2024b.
Xu, A. and Raginsky, M. Information-theone theoretic analysis of generalization capability of learning algorithms. Ad- vances Neural Information Processing Systems, 2017.
Yagli, S., Dytso, A., and Poor, H. V. Information theooretic bounds on the generalization error and privacy leakage in federated learning. 2020 IEEE 21st International Workshop on Signal Processing Advances Wireless Communications (SPAWC), pp. 1-5. IEEE, 2020.
Yamane, I., Chevaleyre, Y., Ishida, T., and Yger, F. Me- diated uncoupled learning and validation with bregman divergences: Loss family with maximal generality. In International Conference Artificial Intelligence and Statistics, pp. 3768-4801 PMLR, 2023.
Yang. Q., Liu, Y., Chen, T., and Tong, Y. Federated machine learning: Concept and applications. ACM Transactions on Intelligent Systems and Technology (TIST), 10(2):1-19, 2019.
Yuan, H., Morningstar, W. R., Ning, L., and Singhal, K. What we mean by generalization in federated learning? In International Conference on Learning Representations, 2022. URL https: http///pppeeeeeeecceeeee forum? id 1d=Vimg0q-i10
Yun, C., Rajput, S., and Sra, Minibatch vs local sgd with shufffing: Tight convergence bounds and beyond. arXiv preprint XrXiv:21 10. 10342, 2021.
Zhang, H., Li, C., Kan, N., Zheng,
Z., Dai, W., Zou, J., and Xiong, Improving generalization in federated learning with model-data mutual information regularization: A posterior inference approach. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
12

---

Conditional Mutual Information Framework for Federated Learning
Appendices
The structure of the Appendix is outlined as follows. The appendix begins with begins with figure illustrating the superclient and supersample construction, followed by table summarizing the key notations used throughout the paper. Section B presents collection technical lemmas essential for our analysis. In Section C, we provide IOMI generalization bounds for FL. Sections D, and F contain detailed proofs of our theoretical results. Additionally, an extra eCMI result presented in Section G. For further details regarding the experimental setup, refer to Section H.
A. Visualization of CMI Framework in FL and Notation Summary
Figure illustrates the superclient and supersample construction used in our CMI framework for FL.. For clarity and ease of reference, Table compiles the key notations used throughout the paper.
Meta-Distributio
Draw clients
Superclient jú
Vi
Ai..0
A1l1
V/3
Vx
Axo
Axa
Participating Clients (Selected by V)
Generate Supersamples
e.g., Supersample ZiVe ~ Pii.
Z%%%
%%%
Y v.
Z V.
Training Samples St
Test Samples
Figure 2: Illustration of the Superelient and Supersample Construction FL
B. Technical Lemmas and Additional Definitions
The following lemmas are widely used in our paper.
Lemma B.1 (Donsker- Varadhan variational representation of KL divergence (Donsker & Varadhan, 1983)). Let Q, be probability measures on e, for any bounded measurable functiion f θ -+ R, we have Dku(Q]]P) = sup, Es_q [f(()] In Egup (exp f()).
13

---

Conditional Mutual Information Framework for Federated Learning
Table I: Summary of Notations
Notation
Description
2, W.C
Instance space, hypothesis space, and set of all possible clients Meta-distribution over clients
D
14
Local data distribution for client
K,n n
Number of participating clients, dataset size per client
S
Training dataset of client i, union of all training datasets
A
Local learning algorithm, global FL algorithm Conditional distributions local and global models given training data Global true risk (population risk)
Pw,SS, Pwis (W)
(W)
True risk of participating client
Ls. (W), (W)
Empirical risk of client average empirical risk for all participating clients
(A(
Expected generalization error
(A)
Participation gap Out-of-sample gap
Eog(A)
(A)
Expected excess risk Superclient matrix drawn from meta-distribution D Supersample for client distribution j4,6 where b {0, 1} (740, 7(1)
zth
7'
Z
Collection of supersamples {
Vi
Bernoulli variable determining client participation in i-th row of Bernoulli variable determining training data in j-th row of supersample Zihb Bernoulli random variables indicating client participation (U )
Vib
V = (Vi)
U
U (UAK,
V. T 1=-1
Bernoulli random variables determining sample usage in supersamples
Complementary Bernoulli variables for participation and sample selection Training and test samples from supersample drawn from i-th row, b-th column of jz
T000 Tris
7/b 7.b
The j-th elements in training and test samples from i-th row, b-th column of jú
1.Ug J.8
W
Global model aggregated from local models (W))
W
Local model produced by client
w
Global risk minimizer under D
Lemma B.2 (Hoeffding's 's Lemma (Hoeffding, 1963)). Let X [a, be bounded random variable with mean μ.. Then, for all I IR, we have E. [e4X]= < clut o)
Lemma B.3 (Hoeffding's inequality (Hoeffding, 1963)). Let Xı,..., Xm be independent random variables with Xę taking values in (a,, for all E [m]. Then, for any >> O, the following inequalities hold for Sm. >m X,:
Pr (ISSSm - E(m.. 2 e) 2e
The original information-theoneti bound in Xu & Raginsky (2017) is for centralized learning, or a single data distribution cquivalently, and the key component in the bound is the mutual information between the output W and the entire input sample S. This result is given as follows:
Information- Theoretic Generalization Bound
Lemma B.4 (Xu & Raginsky (2017, Theorem 1.)). Let the size of training dataset S be n. Assume the loss f(w, 2) is " for any w E W, then the generalization error for the learning algorithm upper bounded by
202
(((A) < SSW
n
?A random variable is o-sub-Ciaussian if for any À E R, log E exp (A(X- EX)) X202/2 //. Note that bounded loss guaranteed to sub-Gaussian.
14

---

Conditional Mutual Information Framework for Federated Learning
Definition B.1 (Differential Privacy (Dwork et al., 2006b;a)). An algorithm A: 2" W is (e, 8) -differrentiall privale (DP) if. for any two data sets 8, E " that differ in single element and for any measurable set W C CW
Pr(A(s) w] S e Pr[A(s') E 6.
f = 0, A is e-differentially private.
C. Input-Output Mutual Information (IOMI) Generalization Bound
In fact, the IOMI bound in Lemma B.4 can be directly applied to the FL setting, leading to the following bound on (A))
Theorem C.1. For each i E [K], assume the loss E(w, 2) is o--subGaussian with respect to Z ~ p4 for any w E W. Let max max((; ) then the out-of-sampll gap of FL learning algorithm A is upper bounded by
20 nK
(oo((A) &
I(W;
(2)
Clearly, increasing the amount of data per client improves generalization performance. More importantly, the key term T(W; SI:K) in the bound suggests that the hypothesis W contains minimal information about the training data Si:k of the clients (i.e. I(W; S1:x) is small), then the FL. algorithm A will exhibit a small out-of-sample gap. This aligns with a desirable property of federated learning: good client privacy implies good generalization. This relationship also discussed in Lemma 3.2.
To further tighten the generalization bound for (A), adopt techniques introduced by Bu et al. (2020), along with similar developments from Wang & Mao (2023b) for bounding Erg(A).
Theorem C.2. For each i E [K], assume the loss f(w, Z) is o--subGaussian under any ~ DD for all w E W, then the generalization error of FL learning algorithm A is upper bounded by
K
1 K nK
(DDA S
Σ K 1=1
+ (K2lla)
I02I(W; Ziz);
(3)
1= j=1
where Pz is the data distribution induced by the meta dittaddistibution, e.g., Pz = =) I 11- =))
The proof of this theorem follows directly from the techniques in Bu al. (2020, Proposition 1) and Wang & Mao (2023b, Theorem 4.1).
Compared to the CMI bounds, this bound has its own distinctive advantage: the first term explicitly characterizes how the divergence between client distributions affects the participation gap. This provides a clearer understanding of how heterogeneity in client distributions impacts the generalization performance of FL algorithms. In addition, this result will ultimately lead to a maddient-norm-based regularizer when SGD or SGLD is used (Wang & Mao, 2024a) and hints at a potential feature alignment mechanism the KL sense for clients.
D. Omitted Proofs in Section
D.1. Proof of Lemma 3.1
Proof. First, due to the symmetric property of superclient construction, we have
(AG(A) =IE [TD(
TEW.HLK
[T (W)]
K
=Ew,n.2 ((WW2))
Σ
Ew....z [[(W, ZD]
K
E.W.V; [TTrer (W) L,,,, (W))
K
1
Ep.w.v [(-1)V: (Laaa (W) Lp (W))
(4)
K
15

---

Conditional Mutual Information Framework for Federated Learning
For example, if V O, then 1 (W) is the testing of non-participating client P4,1, and L (W) is the local testing error of participating client P4.0- In addition, Vi will switch the roles of clients (4,11 and j4,0- and still reflect the gap of testing errоrs between non-participating client and participating client. In other words, 1 K ) (La., (W) - La (W)) in Eq. (4) is an unbiased estimator of (Ac(
Furthermore, notice that, by definition, we have
Ep,w.v [(-1) Ip.. (W) -Ep.W.V.2-...
| (--1) 2)
-Bw.V. (-1) 2
(5)
and
w.w. [(-1)): L.. (W)] 2
(-1) 2)]
=B 2..
(-1) Z
(6)
where in both equations be arbitrary index from [n]. We will simply let j from now on.
Note that the expectation over does not need to explicitly appear in Eq. (5-6) evaluating function l does not rely the random variable jz.
Consequently, plugging Eq. (5-6) into Eq. (4) will give us the desired result:
K
(-1)% (RW. Z 1,7711 E(W, 2:.0 1,01
)}
|
EPo(A) = K
Σ Ez 2.u.s.
Then similarly, according the symmetric property of supersample construction, we have [LAI (W)]
(A) = -Ew,yyy
Ew.s [Ls]
K
E ((W,
Ew.p..ii [e(W, Zi,))]
Kn
1=1 j=1
Zz w.V. (-1)03% (e(W, 23:11 e(W, 27:11) )
This completes the proof.
D.2. Proof of Theorem 3.1
Proof. We start from bounding the participation gap.
Let g88, u², w, v.) (-1) (e(w, 24.1 (1,,,..) E(w, 24.0 :)) To apply Lemma B. we let let and let V/ be an independent copy of V, (i.e. Pvy = Pv, and V W|s w²), then
t.g for 0 Lemma B.1,
VI = U ut) ) + log Ew.yylas,u eeo(s",.t...VV))
Ew.y 19(2', u², W, V.)
< inf
1>0
Since V/' is independent of W, Zt and U², we have
By [0(3), wi w. V/)
Evy [-1))² (((w; l(w, 2 (,,
for any w. and w². Ergo,
Ewiz au [Ey [g(2", n², W, V,O] 0.
16

---

Conditional Mutual Information Framework for Federated Learning
In addition, the loss is bounded in [0, 1J. we know that ((>'')))) [-1,
Thus, g(8 u', W, Vi) is zero-mean random variable bounded in [-1, 1] for fixed pair of (z',u'). By Lemma B.2, have
Ew.yriasaa [elacer < Se
(9)
Plugging the above into Eq. (8),
I(W; Vi =))
B [g(2', W, vo) s inf
(10)
8>0
=V 21W Vil = =², v²),
where we choose t V 21(W; V. =0,7==8000 u²" in the last equation.
Recall the formulation of (A) in Lemma 3.1 and by Jensen's 's inequality for the absolute value function, the upper bound for participation gap is obtained:
K Ezgus . Ew.nizs,05 (-1))% (e(W, -
EpG(AA)
S
((W - :
K
i=1
K
<
1
E
E
V 21 UV;
(11)
K
We then process similar procedure for the out-of-sample gap.
Let h(2', Us; w, u () (-1)ri" (e(w, = E(w, 21,00 )): ) To apply Lemma B.1, let f t h for Lemma B.1, and let U be independent copy of U (i.e. Pú Pur and T I1 W|2 v2), then
> 0 in
I(W, u E 2t, V1 v.) + log E wor (h w.
E W [M(zt.u,
us W, u.u s inf 130
(12)
Since U' is independent W, 2t and Vi, we have
E Eyntin M2 ur u. U.) Eygrir (1-1)03) (e(w, ((1,,,,11) 25.11) E(w, 2/ 2/,0)) }]]
for any w, 36 and Us. Hence,
Ewiss [Porgpo M Us. W, W,U W.(Thj)]] =0.
Again, since the loss is bounded in [0, 1]. we know that ((.)))))) E [-1,
Thus, h(2', U4, W, "t ) is zero-mean random variable bounded in [-1, 1] for a fixed pair of (2), v.). By Lemma B.2, have
E Wwerr" (1 (( < <e
(13)
Plugging the above into Eq. (12),
IWW W.W.h.B. =. 2
E Bwu MM8',0, ug W. W.
< inf
(14)
t20
t
2T U/.
- 7= =
17

---

Conditional Mutual Information Framework for Federated Learning
where we choose? t V 2I(W; U, [ 34, V; 24) in the last equation.
Recall the formulation of (A) in Lemma 3.1 and by Jensen's inequality for the absolute value function, the upper bound for out-of-sample gap is obtained:
K
[-1]u; (Q(W, e(w, (3 )] ((w.
(oa((A)
S
E B
Kn
1=
K
21 (1:
E 2 vi V
(15)
Kn
j=
Combining Eq. (11) and Eq. (15), we have
[ED(A)) S (APG(A)) + (A)
K
K n
E Z .r V (W;
E v.
21 V. (W:Ujik).
Kn
This completes the proof.
D.3. Proof of Lemma 3.2
Proof. First, by the Jensen's inequality and the chain rule of MI, we have
2 21 21 SV
3 K II(W:VZ,U))
E 2
(16)
K
E 2M .v V 21 sv ILW V.).
(17)
The detailed application of Jensen's inequality and the chain rule of MI for obtaining the above inequalities are deferred to the proof for Corollary 3.1. In FL, given (ž', V.), U.V. - W. W forms Markov chain. Thus, by the data droc-pronsssing inequality, have
U Z2,) v)) <I(W; U. M 12, V.).
(18)
In addition, by the chain rule, we notice that
T(W: V. - -ww. [W, I(W; Z,U).
Since the training dataset S is determined by (V, UV, S 5= / Zyy we have I(W; V, IW:
S). Then, due to the non-negativity of MI, /(W; Ž, U) > 0, we have
I(W; V1, U) S(W:S).
(19)
Similarly, notice that
UWWU = UWW Zt, V.) + +(W,; 2'VV), Vi),
Since the training dataset S, is determined by (V, Zt, U.).). i.c. S. ZV.v. we have I(W;; V,, 2. Z,U.K. SW, V,, (.V) = S.). Then, due to the non-negativity of MI, I(W,; Z', Vi) 2 0, we have
Z.V
U V.) & (.W
(20)
18

---

Conditional Mutual Information Framework for Federated Learning
Recall that each local algorithm A, is e,-iiferenttilly private, and the overall FL algorithm A is e'-differentially private By the definition of differential privacy (see Definition B. for any two local datasets s; and st, differing by single data point, and for any two aggregated datasets and s/ differing by single data point, we have:
P(wx(s:) Se P(w))s()s
(21)
P(w]s) Se P(w]s').
(22)
The following development is similar to Barnes et al. (2022, Corollary 1).
f dP
(w, (), log dP(w)s)
I):
dP(w)
w.s
[ dP(w, 8) log Es [dP(w[S))
dP
$ [ dP(w, 8) log inf. dP(w)s))
dP(w)s)
dP(w, =é
w.a
where the last inequality is by Eq. (22). On the other hand,
1(W; S) DKL (Pw,sllPw Ps) + DKL (PwPsll Psssss..s))
I dP(w)dP(s)
(dP(wls) -1 log dP(w)
dP(w)s)
dP(w)
w,
dP((w(s) inf, dP(w(s') -1)
log dP s)
dP(w)dP(s)
wus
inf, dP (P(w(s')
dP(w)dP(s)( (e" (1) e'
< wu,s
-1)
Hence,
I(W:)) S min(c, 1)6}
(23)
The similar procedures can be applicd to I(W,; St), which will give us
IW S minfer, (E 1)
(24)
Putting Eq.21)) and Eq. (23-24) together, we have
E B . v 12:.0(W;V)) sv
min(c', 1)c'
K
K min(es, (e - 1)e,}
E Zz V 18. (W: sv
n
This completes the proof.
D.4. Proof of Corollary 3.1
Proof. We first apply Jensen's inequality to the bound in Theorem 3.1,
2 K
2 K n
ED(A) <
I(: ZW,
IWW V.).
(25)
K
Kn
j=1
19

---

Conditional Mutual Information Framework for Federated Learning
For the first term in Eq. (25), notice that
I(W UU) - HVV,W, H(V.W,,2.U)
T(W; - FTV,JW,,.U
Since conditioning reduces entropy, HVV, Z,U) HV, W. U have I(W; V, ,U)) I(W; I(W;V,/ZUU Then, by the chain-rule of mutual information, we have
I(W VWWVIZ,U)= I(W; U. ).
Given that V; is i.i.d. sampled and is independent of 7 and U, we know that (VV[-1); V/(2,U) 0. Hence,
T(WVV
T(W; V. V(-n) + T(V VI(2,)
IWW 1-1; V)
I(W; V2 2, U) 1VV V.l
VW,U),
where the last inequality is by the non-negativity of mutual information.
Consequently,
2
2 r(w 2 K
I(W; VI <
(26)
We then focus on the second term in Eq. (25), notice that
of 2., V,) = -H( - H(U) W, 2.,V)) Vi). U 1 V. = -H -HU Iw, |,, ž,V).
Since Ve is i.i.d. sampled and U..V. is independent of V Vi, i.e. the rest of V2 for k + i, we have H(U)) (V)) ( IV). Moreover, according to conditioning reduces entropy, H(U,. W, (W, Z, V) < H(U W, 2: V2),, we have I(W; U.V. I V.) I(W;U; V).
H
Then, by the chain-rule of mutual information, we have
I4W 2. Σ
For given V. U../ is i.i.d. sampled and independent of 7 and other U.V. for # i, we know that
20

---

Conditional Mutual Information Framework for Federated Learning
b-111 U 12 V)
0. Hence,
IW;U = I(W:U, j=1
J- 12,1)
I(W;U; v. 12, (uiiiii U (,,
(W.UF.I..V).
where the last inequality is by the non-negativity of mutual information. Therefore, we have
K a 2
2 K I(W: Unv ( V).
Σ
(27)
Kn
Kn
1=1
Let U² (UAN, U.V.), (UV.). then again by the chain-rule of mutual information, we have
K
K Σ I(W: 2, V. V.U(1-1)),
I(: Σ I(W
where the last equation is by the independence between W and U.V. namely (WWUU.V . V. U 11, (iv)) = O. Similarly, for given V, gr.V. is i.i.d. sampled and is independent of 2 and other Uk for to # i, we know that T(Uli",; V) = 0. Hence,
K I(W; UWV V.V. 2, 14 + 1(0 ž v)
IW:
I(w, 11- 11, U..V
UW; [2, v) + 1(111- Ui.i U U V.V.)
(.W:U
(28)
Thus, plugging Eq. (28) into Eq. (27), we have
2 K
21(WUUīZ, (2
V)
IW:
(29)
Kn
Kn
=
Combining Eq. (26) and Eq. (29) together will complete the proof.
21

---

Conditional Mutual Information Framework for Federated Learning
D.5. Proof of Corollary 3.2
Proof. Since all data in Z are ii.d., the conditional distribution I' W ,ri is now invariant Vi, namely P. o PwivV=1.2..u W WIV.0,,Z..0 + 2 WIV.=1,Z... Pwiz+.... Consequently,
IWW Vil V.IZ2 U*) E S0,0r V
dP(wlui, dP(wlu,Z'.U'" 20U0%
dP(w,
0,
(P(w]Zi,U')
which can imply the first term in Corollary 3.1 vanish.
D.6. Proof of Theorem 3.2
Proof. Again, we start from bounding the participation gap. We let
o(2,u,w.u) 2
1-1
Σ
K
(-1)
(R(w, g6. [,aaa) - f(w, 25.0 [10)f0))
2
K
Then, we apply Lemma B.I
E wivv,, U, U, w. s DKL (Pwiz.evllPwzz.)) + log Bwiz,u [eo2
(30)
Let V an independent copy of V. By Markov's inequality, we have the following bound with the probability at least 1 8 under the draw of (2.U.
W. 2.0 Ev. (ol(Z,,w..")))
E 2,v (0Z,u, s DKL (Pw12.e.llPww2..c) + log
(31)
Since V is independent of W, Z and U, the random variable = * (-1) (elw, z4, 1,af.a) - (ww, 21.0 o) has zero mean for any given ,w, namely Ev [c] Additionally, for the fixed (w, u). Ç is the the arithmetic average of K independent terms, each with bounded range [-1, 1]. Hence, is Sub-Gaussian random variable with variance proxy 1/VK. By Wainwright (2019, Thm. 2.6.(IV)), we have
E
S V.
Plugging the above inequality into Eq. (31), we have
E E U, < DKL. (Priz.cvlPMm)2.) log VK
Then by Jensen's inequality,
K-
1
E
E
1
Σ
K
(11)%
((W.Zi.)) 34,1
E(W, 200 (,0,00)
)))
DRL. (Pwizuxl/Pwzz.) + log
VK
2
K
Consequently, with probability at least 1 - 8.
K Σ
2D (Priz,u,vlll (l + +2log KK
Ew 2,0.v Lo(W)- K
((W,
Z
1,8 vv
(32)
K --1
Furthermore, for out-of-sample gap, we let
h(2,, u, w. v) nK -
K
[(-1)=² ((wu,2),1) E(w, 23,0 )1
E Mnng
Kn
i=1
1=1
22

---

Conditional Mutual Information Framework for Federated Learning
Applying Lemma B.1
R Z, (( SKKL. (PrIZ.C.vlPP22..) + log wizzv [.1..u...:..
(33)
Let U be an independent copy of U. By Markov's inequality, we have the following with the probability at least 1 under the draw of
w:2, Buy (e w..))
E v h/
<KL (PwizuvvlPPiizy) + log
(34)
5
Since U' is independent of W, 7 and V. the random variable Ç' = Kn E 2y= (e(w, 20,11 f(w, 25,0 has zero mean for any given (w, ž, v), namely Egy [5' = 0. Additionally, for the fixed (w, 2, u). S' is the the arithmetic average of Kn independent terms, each with bounded range [-1, 1]. Hence, Ç' a sub-Gaussian random variable with variance proxy 1/vKnn. By Wainwright (2019, Thm. 2.6.(IV)), we have
Ke-1 2'2
Ey e
S VKn.
Plugging the above inequality into Eq. (34), we have
Vn +og
E E
[(Z.
s DEL (PmizvvllPi11)
By Jensen's inequality,
Kn
K
1f (e(W, - (ww, s DRL. (Pwiz,vvlPWWzz.) + log
VKn
E
2
Kn
5
Therefore, with probability least 5,
K Kn
20el (Iwiz.urllPw + log vKn
Σ
((W, of e(W, -(w,
5
Kn-1
i= j=1
(35)
Combining Eq. (32) and Eq. (35), with probability at least 1 25 under the draw of (Z,U, V), we have
B (W) - Ls(W)]
1 k K
K
Ewiz,u,v LD(W)-
Σ
e(W, Z mn)
+ B
((W, ZI,K 20, vo
E(
Zan Zan
5. m.
Kn
t=1
j=L
2DKL (Purz.u.ylPPwee
+ 2 log VR
2DKL. (Pwiz.LN (Pwlz.v/ Kn-1 1
log vk=
1
Finally, let 5 + 5/2 will complete the proof.
23

---

Conditional Mutual Information Framework for Federated Learning
D.7. Proof of Theorem 3.3 Proof. We first notice that
(AR(A) -Ew [ (W)] - EE~DEE~u 1((w", [2]]
=Ew [W)] Ew,s [Ls (W)] + Ew,s [Ls( EnwDRRz 1e(w", Z)] SEw [LD( - Ew,s [ls(WW) + Es (L.s(w") - BywD R Ru (((=,,, 2)]
=ED(A),
where the first inequality is due to the fact that W is the empirical risk minimizer of S, and the last equality holds because Es [ww)] Kn Σ En= Ez., [e(w", Zi,)] Ez [<(w", Z)].
Recall the generalization bound in Corollary 3.1,
2T(W; VIZ,U)
2T(W: V)
EER(A) & ED(A) & (8D(A)) &
K
Kn
This gives us the expected excess risk bound. For the high-probability bound,
wuju,u (W) Ls(W)]
=R (W) EYNDBBzN [e(w", Z]] + EpwDDRnn 1 Z)] I.s(W)
wi,,uu (WD) - EyNDBB [l(w", Z}]] - (Bwiž,u.v (Ls( BEwDEEZN [1(w", 2)1l).
B.
Hence,
E (W) BRwDEENg [l(w", Z)]] E (LD(W)- Lss(W] B
The first gap in RHS, E FVjzu, (L) Ls (W))),, can be upper bounded by Theorem 3.2.
We further process the Bi term,
Bi =B [Ls) - Es [Ls(w")] + Es [Ls(w")) Ep-DBR- 1l(w", ((w":)) 2))]
<B (Ls(w)) EEnDEE Il(w", 2)]]
-s(ww)) BEnDBBN [e(w",
!ww, Zo.s) Ez [[(w"; Z)].
nk
where the inequality holds because Wi the empirical risk minimizer of S. Note that each Zi,j is independently drawn. Therefore, by Hoeffding's inequality (cf. Lemma B.3), have, with probability least 1 5,
log
B1 1
2nK
This completes the proof.
E. Omitted Proof in Section 4
E.1. Proof of Theorem 4.1
To prove Theorem 4. we first need the following lemma as the main ingredient.
24

---

Conditional Mutual Information Framework for Federated Learning
Lemma E.1. Let the constants C1, C2 >> The following equations hold for the weighted participation gap and weighted out-of-sample gap,
2+
K
Ew [LD(W) - (1 + Cw, [L))
Σ
B .s
B
[E,L,))
(36)
K
1=1
2+ C2
Ew.Hi]] Lunng (W) - (1 (1+ C2)EE,s [Ls(W)]
B
(37)
Kn
vi
respectively, where E; = (-1) c1 and Ey = (-1)0y%
C are two shifted Rademacher variable with the C1+2
C1
same mean
CL+2""
Proof of Lemma E.I. Let L5- L(W, Z 1,0%,11
)r then
Ew [LD - (1+ Ci C.) [ (W))
K
E
((W, ZiV. 1..7. (1+ Ci),(,, Zi v,,.,.1)))
K
Σ
E WWW.
(1+
(1
2
((ww (WW.Z.F..) (,.,,,) - 2/,
- euw b..
1.
C1
((W,
1.0%%
2+
C1
K
(- - C +2
C1 Li
[(-1)
C₁ 1
E BL,, .Vi
+ +BLIM
C C
2K
By the symmetric property of superclient, it easy to see that, no matter in the homogeneous setting or the heterogeneous (-
setting, BattingE,,,,, .v:
C. L. = BE vy: [- - C. holds, we then have
Ew (LD(W)
- (1 + C1) Ew [ (W)l
K
+ C1
(-1) L,--
C1 I,
E BL V.
K
C1+2
i=1
K
2 C1
EL . [
(38)
K
For the second part, the decomposition is nearly the same. In particular, let LJ- = -(W, 2,1 ), then
Ew.qp
[L (W)] - (1 + Bw, [W)]
K
Te(W; Z.V. - J.
E(W, EtW
E Ez.V.ofK w
3.00 3.0g..1
Kn
j=
2 + C2
[--])er Li
C2
[(-1)
C2
E2 w.w.i
1ij
+
13 v.....
1ttt
2Kn
C2 +2
C2 + 2
1=1
2+ C2
K
(-1)03" L.tt
C2 it
C2 2255
Kn 1=1 1=1
2 C2
K n ΣΣ
M. va
Kn 11
This completes the proof.
25

---

Conditional Mutual Information Framework for Federated Learning
We now ready prove Theorem 4.1.
Proof of Theorem 4.1. Recall Lemma B.1, let t(C] + 2),, and let E be an independent copy of éG, then
I V.) = [() =DRI. (Pi, 11.,. Pet)
SuppBt [M + 2),, - log R. & (0(1+2)
sup t>0
sup B [M(C] + 2]):Lt - -log B 21(++11
+ c
(39)
2
where we use the fact that ē is independent of Lt and P( 0,+2) P(e:
-2(C++1)) C1+2
)
2
Notice that e +1) + is the summation of two convex function, which is still convex function, so the maximum
value of this function is achieved at the endpoints of the bounded domain. Recall that L E [0, we now consider two cases:
when T O, we have e (1( + 2 2;
ii) when _,- 1, we select t such that e 21( + 2x < 2. Note that this inequality implies that t 1 log
Hence, let t = C3. and let the values of C₁, C3 be taken from the domain of {C1, Cs|C1, C3 > 0, 20s 2Cs < 2}, so the inequality
E L
20s(C(+1))
eZZLL!
1
(40)
2
will hold. Under this condition, by re-arranging the terms in Eq. (39), have
[();vV)
(C1 + 2) [&tt]] <
Css
Plugging the inequality above into Eq. (37), we have
2 C+ K
I(L::
Ew [L)(W)] - (1 + C1 Ew. [LMIN (W)] =
Σ
Ezt e [EL
K
C3m
Thus, the following inequality can be obtained,
K
i(Ltiv)
min Ew (W)) 3.,cs30,22344 20,0 (1+ C.) [T (W)]
(41)
Cym
Following the similar development, also obtain
EW. Luggg (W)) - (1 + (L)
2 C²C2 ΣΣ
E Sh . [
Kn
K 1
C,Kn
This is equivalent to
K n
Ew,nin Leqng (W))
min
(1+ E2 [s)] +
(42)
20
C2Kn
==
Finally, substituting Eq. (42) into Eq. (41) and re-assigning C1 C1 + and C2 = C2 + will complete the proof.
26

---

Conditional Mutual Information Framework for Federated Learning
E.2. Proof of Corollary 4.1
Proof. In fact, the generalization bound in Corollary 4.1 can be similarly proved in Theorem 4.1 with unpacking the random variables _ Z(W.Z 1,011-) and LjJ L(W, :) during the development, which are functions of (W, Z' U*)
and (W, Zz, Vi). respectively.
Alternatively. notice that
; - "",,",,,,,",
I(4+: -0, ((,
Since 1(V; 2 U²) = 0, we have 1 Vi) S 1(41; ;iiiv,,,,,, U*). By the data-processing inequality, we further obtain
; V (7) - T(W; VI (
Analogously, we can also obtain U of Corollary 3.1.
V. (V) s U/ IV,, Z*). The remaining steps are the same as in the proof
F. Omitted Proof in Section 5
F.I Proof of Theorem 5.1
The most important ingredient for proving Theorem 5.1 is the following lemma.
Lemma F.1. Let =(w,z) = Ds(w, 2). we have
(-1)) (e(W,, Z (() e(W,, - Z 21010)))))
EPG(A)
E
K
i=1
K
(A) = K2n
E Bo,.oo
(aW,, (, [(-))3t
- sew,-ew,,- 2(,,,
Proof of Lemma F.l. Considering the participation gap. The i-th participating client μ4, uses training sample St to train local model W,, then if this client is replaced by another client, n4, which uses its own training sample Sy then the provided local model is denoted as (i))) In this case, we denote the new aggregation model Wi) K EEaye We + W!).
Then, let 2/ = ZiV; V, be the testing data from non non-participatinn client V. and let 2, = Zi.,.. be the testing data 1.7%%
from participating client ju,,, Notice that
((W E(W, 2,) =((A(S), Z) - ((A(S), 2.)
((W 2) - e(w() 2/ =((AS)) 2) - ((A(S)))) 2),
where S = (S S U.
Under our assumption that the i-th client always uses the same algorithm As the key observation that Ey Eeg. Z..A (S(A(S), Z.)] Buggzord 2;A [((A(S)), 2 where, with an abuse the notation, we also use to denote the inherent randomness of algorithm. Then, we have the following
1
(Ao(A)
E
B... ((W,2))e(W, E(W, 2i)]
K
1
Bzs.o..wo... W.WOn [((W - (
K
27

---

Conditional Mutual Information Framework for Federated Learning
Recall that ((w,z) Dy (uc, 2). have
E [(W, Z - E(WW() .2))
-E [((W) - -((2) - (Vf(2,), W- - -Z,-
- - - -(() - -2)
=E (Vf(Z)), w( (((());)((---))) -w]]
where the last equation is due to the fact that W and W have the same marginal distribution, namely ED [f(W)]
EA [f(W())].
Since ( k (Eazs WA + w:) and W =
1 R Ex Ws, they only differ at i-th local model, we have W W
K (W:- - W.). Consequently,
e(w, Z - E(W()) |;)] [,)] E
1
E [(V f (2)), W/ Wi)]
K
- E [(V](Z), W - - -(W; - - + S(W.)
s(W]]]
K
E
[e(W,, Z(- 2.)].
K
where we use E [f(W,) = E [f(W]] in the second equality.
Therefore,
K
[(
((IW, ZiV. 1,0.1. e(W,, Z0H,
Epo(A)
E 22,00 ur W.V.
K2
i=1
K
(-1)%
((W 7 (( E - z )
E
K2
For out-of-sample gap, now consider keeping the i-th participating client (4; unchanged, but the j-th data in its training sample S; is replaced by another i..dd sampled data Di., p4. then the provided local model is denoted as W/y In this case, we denote the new aggregation model W(i-j) Exaes W& + W(.)
Recall that ((w,2) (w, 2), for each participating client ju,,y,, have
E [e(W, 7 E(W, Zz,)
Σ E [[(w, 21,s) ((W0)) [2,1
E [(()) - - (V (V]() W Eis)) ((2,)) WGO Zis)
E (V](Z)))) w(() w7].
where the last equation is by E [f([W] E [f(W(()))].
Since ((,)) = K EEnge We + WX.) and W & Dk W,, they still only differ at i-th local model, we have W(()))
28

---

Conditional Mutual Information Framework for Federated Learning
W * (W W.). Consequently,
E (t)) - (WW22)))
E [ ([V](ZZ))) W Why WWYl
Kn
1
E [[(V >) Why Z/-- -W, Z1,3)) + f(W.) s(W,))
Kn
1
E (((W..Z.)) - ((5)]
[e(W., Z1,)) - e(W,, Z(.)).
nk 1=1
where in the last equality we use the fact that E [e(W] [1,)] = =E [e Znyl. Therefore,
K
1
(A)
=
E.
(((WZ))) - e(W, 2n,s]
Kn
i=
jml
K
e(W; ZiV, 20,4.)) - E(Wi, Zo.
K2n
24.
1.0.2.15)
jml
1
(-1)07% ((WW,,2)1)) e.,,, - 2,,0)
2' v. ww;
K2n
This completes the proof.
Proof of Theorem 5.1. Having Lemma F.1 in hand, the development for proving the bound in Theorem 5.1 nearly follows the same procedure in the proof of Theorem 3.1.
The main difference lies in bounding the cumulant generating function, where Theorem 3.1 uses Lemma B.2 for bounded random vairable, i.e. Eq. (9) and Eq. (13), here we use the definition of sub-Gaussian random variable. We denote
A = (e(W, g4.1 (afta) - e(W, 24.0 21,220))
A2 =2=(-1)0 (e(W,,
2fr 2fr) E(W., 2/,01
Notice that due to the conditional independence between W, and V/, and the conditional independence W; and Uther A and Ag both have zero mean. Therefore, by the definition of sub-Gaussian random variable,
?2? Ew, [cLAi] SeT
(43)
120
E Ww.ugg [e/db] Se
(44)
Eq. (43-44) are used to replace Eq. (9) and Eq. (13), respectively. The remaining steps are the same with the proof of Theorem 3.1, see Appendix D.2, that is, can obtain that
(-1)% ((W,, 7411 1,77")) E(W., 71...o)
)]
E Ez
R Zz ur V 21 v (W.,
R Ey.,,, ( ((W,, 22,11 e(W,, (W3,
1)]
R Z.,u v.
2TZ.N. k.
Finally, plugging the above bounds into the inequalities in Lemma F.1 will complete the proof.
29

---

Conditional Mutual Information Framework for Federated Learning
F.2. Proof of Theorem 5.2
Proof. First, the smoothness and strong convexity of loss function indicate that, for any 2,
L
Smoothness: E(WI, 2) & f(w2, 2) + (Vi(u>, 2), wi -w2) +
Σ |w| - w2l 1?,
Ywi, W2 E W.
Strong Convexity: f(wi, =) 2 (ww2, =) + (Vé(w2, =), wi -w2) + a
w1 - w2ll
Vwi, 102 E W.
2
The following development is inspired by Gholami & Seferoglu (2024).
For each participating client V; we have
B [e(W, k,,)) E(W, 2155
E
E(WW))) [in1]
j=1
(E((W( Zly), W - -Wb-l) + w1 - 12
E
2
j=1
1 Kn
E
(VE(W(())) Z,y), W. - -WWb) +
L
n
E
[IW,
11
2K
E Σ j=1
| E -
E I|, - -|
Kn
2k n j=1
(45)
where the first inequality is by the smoothness of E(w, 2) and the last inequality is by Cauchy- inequality. Again, by the smoothness property and Ve(W",, 1..: Ziz)) = O, we have
E [ |1,5 11] =E || VE(E (4,)) ve(W 4in5 11]
S2LE (((W(()), (21) - <(W ]
-2LE [e(W, Z,,)) - E(W,, Z,
(46)
In addition, by the strong convexity and Ve(W 2in) = 0, we have
E
W - W/, 1/'
E [e(W,, (l,)) (WW) 41,1
a
2
E [e(W., ZZ,)) a(W, Z..)).
(47)
a
Plugging Eq. (46-47) into Eq. (45), we have
E [e(,, <(W, Zrs)]
2
((((W 7,.9) - EW., TR [[(W,, 2i,) - E(W,, Zir)] +
L
Σ
n
E
[e(W,, A,y) e(Ws, Z.,)]
Kn
aK²n
#=1
j=1
2
E Ee(W, 2n,)) - E(Wi, Zn. [11))3% 27,1, - E(W,, 27,7))
Kn
3=1
L
Σ E (- ((W,, - -(W,, /3 ).
+ aK2n
(48)
1=1
30

---

Conditional Mutual Information Framework for Federated Learning
The remaining task is to bound E (-1)0%% (EWW, Z <(W, ) Recall that each A, is an interpolating algorithm, we adapt similar techniques from Theorem 4.1, obtaining the following bound would straightforward
E (-1)) (e(W,, e(w,. 21(W;; 35 V2,
log 2
Here, the constant C4 2/2 arises from the fact that the empirical risk is zero (due to interpolation), allowing the multiplier C2 in Eq. (42) to become arbitrarily large and thus broadening the optimization range for C4. By solving the inequality e e22 + e²Ca < in the limit C2 + oo, we have C2 2
1og
Consequently, we have
K
1
(Ac(A)
E
[(W, 2 e(W, (.))
K
1=1
j=1
2
2L
E B(e(W, (,), (2 V.)++ ak log 2
2L
Σ
Σ I(W:U)
1 Vi).
K2n
a log
This completes the proof.
G. Additional Result: Loss-Difference CMI Version of Theorem 3.1
We apply the losf-difference (LD)-CMI technique from Wang & Mao (2023b) to derive tighter version of Theorem 3.1.
Let T E(W, 7,..0 1,7%.0) and T, E(W, 7 1. Let n e(W, ( 2) and I.J- ((W, Z, Denote AT,
L L L and AL; L3- Litt Using similar development as in the proof of Theorem 3.1, we obtain the following refined bound.
Theorem G.1. Assume ((,,)) E 10, 1}, then we have
K
K (A
ED(AA) S
K Σ
+ Kn
Ev,
=1j=
Proof Sketch. Following the proof of Theorem 3.1, the function g u,, w. v;) = (-1) (e(es, gfil ((( transforms into
- Elw, 21,0 2.0
o(AL,, V.) (-1)
Similarly, the function h(2", 0,, w. u;;;) = (- (e(w,2)))
- E(w, 23.01) now becomes
h(V, VV..ALJ.U. (-1) ALJ.
The remaining steps follow the same structure as the original proof, with the expectation now taken over the newly defined loss difference random variables.
By data-processing inequality and chain rule, Theorem G.1 is tighter than Theorem 3.1.
H. Additional Experiment Details
We adapt the code from http:/ihhhh..aoooaaaaaaaaa/////a for supersample construction and CMI computation, and we use the FL training code from httpss//shhlbbbccom/w/////sssfss Learntnn-d----------nn courning-in-Pypy experiment details below.
inriinn-i-PyyTrrrde Porch.. We now state the complete
31

---

Conditional Mutual Information Framework for Federated Learning
MNIST We train a CNN with approximately 170K parameters. The model consists of two x convolutional layers-the first with 32 channels and the second with 64-each followed by 2 x 2 max pooling. These followed by fully connected layer with 512 units and ReLU activation, and a final softmax output layer. Each local training algorithm A, trains this model using full-batch GD with an initial learning rate of 0.1, which decays by factor of 0.01 every 10 steps. At each FL. round, clients train locally for 5 epochs before sending their models to the central server. The entire training process spans communication 300 rounds between clients and the central server, reducing the commonly used 1000 rounds to lower computational costs.
CIFAR-10 We use the same CNN model from McMahan al. (2017), which has approximately 10 parameters. The architecture consists of two convolutional layers, followed by two fully connected layers and final linear transformation layer. The CIFAR-10 images horizontal flipping, and adjustments to contrast, brightness, and whitening. Each local training algorithm A, trains the CNN model using SGD with a mini-batch size of 50 and follows the same learning rate schedule as in the MNIST experiment. As in the MNIST setup, clients train locally for five epochs per round before sending their models to the central server, with training spanning 300 communication rounds.
preprocessed as part of the training pipeline, including cropping to 24 x 24, random
Non-IID Setting and Evaluation Metric For both of the classification tasks, we evaluate prediction error as our performance metric, i.e. we utilize the zero-one loss function to compute generalization error. During training, we use cross-entropy loss as a surrogate enable optimization with gradient-based methods. To introduce non-IID setting, we apply a pathological non-IID data partitioning scheme as in McMahan al. (2017). Specifically, all images are first sorted by their labels, divided into shards, and then assigned to clients such that each client receives two shards, resulting in most clients having examples from only two digit classes. Additionally, since we pre-define the non-participating clients from the superclient, all participating clients are included in every round of training.
CMI Estimation For supersample and superclient construction, when analyzing generalization behavior concerning the sample size n, we fix the superclient size at 100, leading 50 participating clients and 50 non-participating clients randomly selected by V. The sample size per client varies within n E {10, 50, 100, 250). When analyzing generalization behavior 100 for MNIST and number of clients K (10, 20, 30, 50). To estimate the CMI terms, for both tasks, we draw three samples of Z and V, and 15 samples of U for each given ă and In each experiment, for fixed sample size and client number, the individual CMI term I + V. Vi v;) is estimated using 15 samples, while I I(L;;; Vi) is estimated using 45 samples, utilizing simple mutual information estimator for discrete random variables as in Harutyunyan et al. (2021). In total, we conduct 720 runs of FedAvg for these classification tasks. All experiments are performed using NVIDIA A100 GPUs with 40 GB of memory.
with respect to the number of participating clients K, we set
50 for CIFAR-10, varying the
32


Reviews:
[{"review_id": "7oiJetsHwi", "reviewer": "Reviewer_XAJx", "summary": "This work studies the question of generalisation in federated learning (FL), where $K$ users aims to share some benefits of their learning phase via a central server without sharing their data. Authors propose novel generalisation bounds tailored to FL involving the Conditional Mutual Information (CMI) framework, yielding original information-theoretic results. Authors first focus on general in-expectation and high-probability generalisation bounds (Section 4), before proposing fast rates (Section 5). Finally, they involve the specificities of some popular aggregation algorithms used in FL in Section 6 and empirically study the tightness of their bounds in Section 7.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "We thank you sincerely for your valuable feedback on our paper. Our responses follow.\n\n>- you said in l.122-123 left column that your CMI framework is inspired by the meta-learning one of Hellstrom \\&Durisi 2022. Is it possible to precise what are the specificities of your derived results (e.g. those of Section 4) compared to theirs? It seems you control the same global true risk, due to the assumptions that all tasks are drawn according to $\\mathcal{D}$.\n\n**Response.** As mentioned in the paper, our construction is indeed inspired by the framework for meta-learning proposed by Hellström & Durisi (2022). However, our results are not directly comparable to theirs due to a key difference in problem setup: their meta-learning framework requires the meta-learner (i.e., the global model $W$) to be further trained on the test tasks (i.e., previously non-participating clients), whereas in FL, the global model is evaluated directly on unseen clients without any additional local fine-tuning. To enable a direct comparison with Hellström & Durisi (2022), the CMI framework presented in this paper would need to be extended to the personalized FL setting, where the global model is allowed further local adaptation. In that case, Lemma 4.1 would also need to be revised accordingly, as the hypothesis may no longer be invariant to the ordering of the \"test data\". We will include these discussions in the next revision.\n\n>- An important point: it seems that there is no comparison with existing bounds. For instance, how does your bound behave wrt those of, e.g., Sefidgaran et al. 2024? Is it challenging to plot their results?\n\n**Response.** The PAC-Bayesian and rate-distortion bounds in Sefidgaran et al. (2024) are indeed challenging to compute numerically for more complex neural networks, as they require estimating KL or MI between high-dimensional random variables, even when the model parameters are quantized. Notably, in their paper, the generalization bounds are not plotted for their ResNet experiments on CIFAR-10; instead, they only present the behavior of the generalization error to support the insights behind their bounds. In contrast, a key advantage of our results lies in the ease of estimating the e-CMI bound in the FL setting, making it more practical for empirical evaluation.\n\n>- In most of your results, you have a $O(1/\\sqrt{K})$ term. Would it be possbile to recover the influence of $n$ in such terms (maybe through the mutual information term)?\n\n**Response.** Yes, the reviewer raises a valid point. Indeed, the participation gap term seems to follow an $O(1/\\sqrt{K})$ behavior. At the same time, in the i.i.d. setting, increasing $n$ is also expected to reduce the participation gap. This effect is implicitly captured by the CMI term $I(W;V|\\widetilde{Z},U)$, as demonstrated in Corollary 4.2, where all clients share the same data distribution (i.e., there is only one client distribution). In the non-i.i.d. case, however, it is more challenging to explicitly characterize the impact of $n$ on the participation gap, as its quantitative effect depends on the degree of data heterogeneity, which can vary significantly across scenarios. We will include this discussion in the revised version.", "claims_and_evidence": "All theoretical results look reasonable and extend CMI bounds beyond batch learning to reach FL. The impact of their fast rate result compared to those of Section 4 is well established in Section 7.\n\nSomething which would gain to be clearer: you said in l.122-123 left column that your CMI framework is inspired by the meta-learning one of Hellstrom&Durisi 2022. Is it possible to precise what are the specificities of your derived results (e.g. those of Section 4) compared to theirs? It seems you control the same global true risk, due to the assumptions that all tasks are drawn according to $\\mathcal{D}$.", "methods_and_evaluation_criteria": "The experimental framework looks sound, with reasonably big CNNs (170K parameters), which is nice for a theoretical paper althouigh I did not check carefully the details.\n\nAn important point: it seems that there is no comparison with existing bounds. For instance, how does your bound behave wrt those of, e.g., Sefidgaran et al. 2024? Is it challenging to plot their results ?", "theoretical_claims": "I only looked at the proof of Theorem 4.1, which seems correct.", "experimental_designs_or_analyses": "I did not check in detail the experimental protocol.", "relation_to_broader_scientific_literature": "I do not know enough about either the FL or CMI literature to provide relevant feedback.", "essential_references_not_discussed": "I do not know enough about either the FL or CMI literature to provide relevant feedback.", "other_strengths_and_weaknesses": "None.", "other_comments_or_suggestions": "None.", "questions_for_authors": "- Something which would gain to be clearer: you said in l.122-123 left column that your CMI framework is inspired by the meta-learning one of Hellstrom&Durisi 2022. Is it possible to precise what are the specificities of your derived results (e.g. those of Section 4) compared to theirs? It seems you control the same global true risk, due to the assumptions that all tasks are drawn according to $\\mathcal{D}$.\n- It seems that there is no comparison with existing bounds. For instance, how does your bound behave wrt those of, e.g., Sefidgaran et al. 2024? Is it challenging to plot their results ?\n- In most of your results, you have a $O(1/\\sqrt{K})$ term. Would it be possbile to recover the influence of $n$ in such terms (maybe through the mutual information term)? \n\n\nIn conclusion, this work looks serious, theoretically well-grounded with plethora of new generalisation bounds and nice experiments (which would gain to be completed). However, I do not know much about either FL or CMI literature.", "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": "", "extra_scores": {}}, {"review_id": "C8FbPGLdEY", "reviewer": "Reviewer_4mA5", "summary": "The paper proves mutual information-based generalization bounds for a federated learning setting, that bounds both the out-of-sample gap (between the empirical and population distributions of the participating clients) and the participation gap (between the participating clients and the underlying meta distribution of clients). Theorem 4.1 includes the generalization bound as the sum of the bounds for the terms of out-of-sample and participation gaps, which is order-wise bounded in Remark 4.2 assuming a constant bound on the differential privacy degree of the FL algorithm. Next, in Theorem 4.2 the authors present a PAC-style generalization bound that bounds the gap with high probability. In section 5, the authors show fast rate bounds that decay as $ \\mathcal{O} \\left( \\frac{1}{\\sqrt{nK}}+\\frac{1}{\\sqrt{K}} \\right) $ for $K$ clients and $n$ samples per client. Section 7 discusses some numerical results for FedAvg trained models, which show the smaller generalization gap when increasing $K$ or $n$.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "We thank you sincerely for your valuable feedback on our paper. Our responses follow.\n\n>- ... why the MI-based ... will be useful and how ... lead to regularization ...\n>- ... uncertain about the practical role ...\n\n**Response.** We note that our bounds do have practical implications, e.g., as mentioned in the Related Work section (Line 84-90), if the CMI terms in Theorem 6.2 are small, then the norm $||w-w_i||$  is also small, which is the regularization term used in FedProx. Upon reflection, we realize that this discussion would be more appropriately placed directly after Theorem 6.2, to make the implication more explicit.\n\nWe understand that the reviewer may have been looking for new regularization schemes for reducing participation gap and out-of-sample gap, rather than connections to well-known ideas such as norm-based capacity control. In response, we recommend focusing on Theorem C.2 (which, while looser than the CMI bounds, is more interpretable). This result will ultimately lead to a gradient-norm-based regularizer when SGD or SGLD is used, and hints at a potential feature alignment mechanism in the KL sense for clients. We will elaborate on these implications in the revised version.\n\nFinally, regarding the practical implication, we would like to share a perspective based on our own research experience in learning theory. If the goal is to derive sharper generalization bounds with fast decay rates, i.e. to study learnability and learning rates of a problem, then practical applications may not follow directly. In this case, generalization bounds mainly serve to evaluate whether learning is theoretically possible. In the extreme case, the tightest generalization bound is the generalization error itself, which provides no new actionable insights for algorithm design. If the goal is to obtain actionable insights for algorithm design, then tightness of the bound becomes less critical. Generalization upper bounds, even if loose, can serve as a basis for designing regularizers. For example, penalizing weight norms is a widely used practice to improve generalization, despite the well-known fact that norm-based bounds are often vacuous and cannot explain generalization behavior in deep learning [R1, R2].\n\n[R1] Vaishnavh Nagarajan, and J. Zico Kolter. \"Uniform convergence may be unable to explain generalization in deep learning.\" NeurIPS 2019.\n\n[R2] Yiding Jiang, et al. \"Fantastic Generalization Measures and Where to Find Them.\" ICLR 2020.\n\n>- ... how the theoretical analysis ...?\n>- ... explain what extra challenges ...?\n\n**Response.** The bounding steps for the out-of-sample gap are indeed similar to those in standard centralized analysis, which is expected as each individual out-of-sample gap is close to an in-distribution generalization gap. The main challenges arise in bounding the participation gap. Compared to existing MI-based bounds, our contributions include: the construction of the superclient, the proof of its symmetry properties (Lemma 4.1), the shifted Rademacher representation of the weighted participation gap (Lemma E.1), and the leave-one-out argument for the participation gap (Lemma F.1). To clarify, the use of weighted generalization error and leave-one-out arguments is not new in the broader learning theory literature. However, their application in our setting is enabled by the superclient construction, which serves as the foundation for these results.\n\n>- ... on estimating the mutual information ...\n\n**Response.** Please notice that we use e-CMI bounds in experiments to avoid the difficulties of estimating MI between high-dimensional R.V.'s. The second sentence in Section 7 states: \"we estimate the fast-rate e-CMI bound for FL, as… Additionally, due to the challenges associated with estimating MI when dealing with high-dimensional random variables, we compute an evaluated version of the CMI bound from Theorem 4.1\".  Importantly, the e-CMI bound is computed between two one-dimensional variables (one of which is binary), making the estimation easy and eliminating the need for advanced MI estimators. Further details are in Appendix H.\n\n>- ... do not separately report ... \n>- ... the non-IID setting ... and the separated ...\n\n**Response.** The pathological non-IID data partitioning follows McMahan et al. (2017): data are sorted by label, split into 200 shards of size 300, and each client is randomly assigned 2 shards. We will include more details in the revision.\n\nAs for separate plots of the participation gap (PG) and out-of-sample gap (OG), we would like to clarify that our experiments are based on the e-CMI bound in Theorem 5.1, which consists of three components weighted by jointly optimizable coefficients $C_1, C_2, C_3, C_4$. These coefficients are optimized using the SLSQP algorithm implemented in the SciPy package. As a result, the e-CMI bound is not a simple addition of the individual bounds for PG and OG, which makes it difficult to present separate plots for these two quantities.", "claims_and_evidence": "The paper's theoretical claims on generalization bounds for federated learning seem correct. The current main text contains many theorems, which leads to less space for discussing the implications of the theorems. It would be better to dedicate more space for discussing why the MI-based generalization analysis for federated learning will be useful and how the approach can lead to regularization methods for reducing the out-of-sample gap and participation gaps. \n\nIn addition, I would like to ask the authors how the theoretical analysis in this paper goes beyond a direct application of the existing MI generalization bounds to the FL setting. I understand that the FL problem has two error terms to bound (out-of-sample and participation gaps). Still, the authors seem to apply the MI generalization bounds in a standard centralized-like seting to bound each of the error terms. Can the authors elaborate on how their analysis contributes beyond the existing MI-based generalization frameworks?", "methods_and_evaluation_criteria": "There is little discussion on estimating the mutual information terms in the generalization upper bounds when evaluating the generalization bounds in section 7. I want to ask the authors whether the bounded sample size of the clients is enough to estimate the mutual information terms in the generalization upper-bound. It seems to me that a challenge with MI generalization bounds is how to have a tight estimation of the mutual information term in the bound for the high-dimensional variables in the neural net layers.", "theoretical_claims": "Not in detail, but the results seem correct to me. As I asked before, can the authors explain what extra challenges their analysis addresses beyond the existing MI generalization results that can be applied to bound each of the out-of-sample and participation gaps?", "experimental_designs_or_analyses": "The experiments in Section 7 provide a reasonable sanity check that the bounds correlate with actual generalization error. However, the authors do not separately report the \"out-of-sample gap\" and \"participation gap.\" I wonder how fast the participation gap (when considered alone) decreases with $K$. Also, the non-IID setting should be explained in more detail (in the supplementary lines 1666-1672 several details on the frequencies and parameters are missing), and the separated out-of-sample and participation gaps should be reported to see how they change with $K$ and $n$.", "relation_to_broader_scientific_literature": "While the paper extends mutual information-based generalization analysis to federated learning, I am uncertain about the practical role of the proposed generalization bounds in improving FL algorithms. In statistical learning theory, generalization bounds often introduce a capacity norm or an implicit property of the hypothesis class, which can be explicitly or implicitly regularized to reduce the generalization gap. However, in this work, it is unclear whether the MI-based generalization bounds can translate into regularization methods to improve generalization.\n\nCan the authors clarify how their generalization bounds can be used to regularize and reduce the participation gap in FL? The numerical results seem to suggest that the only way to reduce the gap is to increase the number of samples and clients.", "essential_references_not_discussed": "Yes", "other_strengths_and_weaknesses": "See the previous comments.", "other_comments_or_suggestions": "See the previous comments.", "questions_for_authors": "See the previous comments.", "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": "", "extra_scores": {}}, {"review_id": "1jsLxzHHSN", "reviewer": "Reviewer_4cnC", "summary": "The paper studies the generalization error of the federated learning algorithm using the CMI framework. The goal is to capture the out-of-sample gap and the participation gap using this framework.  To do so, a federated learning setup is considered where each user observes data distributed according to a distribution sampled from a meta-distribution $\\mathcal{D}$.\n\nThe established bounds, including the fast-rate bounds, include two terms that capture the two above-mentioned gaps: the first term captures the effect of uncertainty in the choice of distribution, while the second term is a conditional mutual information term, as derived in the paper of Zakynthinou and Steinke.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "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": "We thank you sincerely for your valuable feedback on our paper. Our responses follow.\n\n>-... the bounds established do not capture any characteristic of FL ...\n\n**Response.** We respectfully disagree with the reviewer's claim that our bounds fail to capture key characteristics of FL, and the argument that the overall algorithm is ultimately treated as a black box is a misinterpretation of our results in Sections 4 & 5. To analyze FL in the two-level generalization setting using CMI, the introduction of the superclient is essential—a construction not needed in centralized learning and one that highlights the fundamental differences between the two settings. Moreover, treating the FL algorithm as a global mapping and construct a supersample of size $2nK$, would break the symmetry required for CMI analysis due to the non-i.i.d. nature.\n\nInstead, we believe the more accurate interpretation is that our results in Sections 4 & 5 are designed to apply to any FL algorithm, without being restricted to a particular instantiation. The goal of these sections is to establish a general framework for analyzing FL as a learning problem. This generality should not be viewed as a weakness.\n\nIn Section 6, we go beyond this generality by considering specific aggregation strategies and loss functions, allowing us to derive sharper insights such as faster learning rates and the benefits of interpolation in local training. Although we focus on the one-round setting, as noted in Remark 6.1, extending the results to the multi-round case is straightforward. We plan to include the multi-round  extension in the Appendix, as introducing it in the main text would further complicate the already dense notation.\n\n>- Main take-home message ... | main question ...|Q1. My main concern ...\n\n**Response.** The main goal of our paper is to frame FL as a learning problem and analyze its learning rate in a two-level setting using CMI. Without assuming any specific FL strategy, our general two-step CMI bounds obtain several insights: (1) strong client privacy (both globally and locally) implies generalization; (2) in homogeneous settings, the bounds reduce to standard CMI analysis, with $I(W; V | \\widetilde{Z}, U)$ capturing data heterogeneity; and (3) we identify conditions for fast learning rates.\n\nWhen applied to specific algorithms like FedAvg under certain loss assumptions, we show that FL can achieve even faster rates, thanks to model averaging and favorable loss properties. We believe this behavior extends to broader loss classes, though a formal proof remains open.\n\nCompared to existing bounds for FL, our e-CMI bound is notably easier to estimate and is the first  MI-based bound to give fast-rate guarantees for both the participation and out-of-sample gaps.\n\nLastly, we refer the reviewer to our first response to Reviewer 4mA5 for a discussion on the practical implications of our results, and the difference between using generalization bounds as indicators of learnability v.s. as sufficient conditions for generalization performance.\n\n>- their proof techniques are rather standard ...\n\n**Response.** We acknowledge that, following our superclient construction, our CMI bounds build on existing techniques, with some extensions to accommodate the two-level setting. However, developing a general CMI framework for FL does not require a complete overhaul of prior methods. As noted in the review guidelines, \"originality may arise from creative combinations of existing ideas\", and we believe this applies to our contribution.\n\n>- Q2. ... order-wise behavior is not correct.\n\n**Response.**We believe the reviewer raises a valid point regarding order-wise behavior, and we also share the concern that many prior works overlook MI, KL, or other complexity terms in such analyses. In the absence of clear decay rates, we think the stated rates should be seen as reflecting worst-case behavior. For example, $O(1/\\sqrt{K} + 1/\\sqrt{Kn}) = O(1/\\sqrt{K})$ implies that in highly heterogeneous settings, even with infinite local data ($n \\to \\infty$) for participating clients, FL may still fail to generalize to unseen clients—an intuitive outcome given the impact of extreme heterogeneity.\n\nRegardless of the exact decay of the CMI term, removing the square-root dependency remains desirable for faster convergence. We will clarify this in the revision.\n\n>- Q4. It is claimed that the bound ...\n\n**Response.** This seems to be a misinterpretation of our result. The CMI term in Theorem 6.2, unlike those in Sections 4 & 5, is a local CMI for each client, involving the local model $W_i$ rather than the global model $W$, and thus is not influenced by client heterogeneity.\n\nHowever, the reviewer’s intuition holds in a multi-round extension of Theorem 6.2, where $W_i$ may depend on other clients through repeated communication. We will clarify this in the revised version.", "claims_and_evidence": "1. The paper claims to study the generalization error of FL. However, I believe that the bounds established do not capture any characteristic of FL algorithms. In particular, \n\n   - The results obtained in Sections 4 and 5 are valid for \"any\" learning algorithm, and not necessarily for a federated learning algorithm, since in the end what is considered is the overall learning algorithm $\\mathcal{A}:\\mathcal{Z}^{nK} \\to \\mathcal{W}$, as a black box. Therefore, in my opinion, such results do not reflect any aspect specific to FL.\n\n   - The results of section 5 are valid for one-round aggregation and under simplifying assumptions (such as Bregman divergence). Therefore, they cannot be considered as FL.\n\n2. The claims about the behavior of Theorem 6.2. with respect to data heterogeneity do not seem to be precise enough. See questions.", "methods_and_evaluation_criteria": "While CMI framework seems interesting; but I could not get the main take-home message of the paper. See the questions.", "theoretical_claims": "The established results sound correct to me.", "experimental_designs_or_analyses": "The experimental results are limited, but I do not think this is the main weakness of the paper.", "relation_to_broader_scientific_literature": "Sufficiently discussed.", "essential_references_not_discussed": "The paper sufficiently addresses and discusses similar work. However, the precise advantage of the bounds obtained over the previous literature is not clear. More precisely, it is not clear what is the main question studied in this work.", "other_strengths_and_weaknesses": "Strengths: \n\n1. The issue of studying the generalization error of FL is important, and the use of the CMI framework looks interesting.\n2. A number of previously established results are adapted to this setup.\n3. The idea of considering supersamples, where each client's \"test\" dataset may have a different distribution (sampled independently from the meta-distribution $\\mathcal{D}$) than that client's training dataset distribution, to capture the effect of non-participating clients is interesting.\n\nWeaknesses: \n1. While the established bounds are correct, their proof techniques are rather standard extensions of CMI results to the distributed setup (similar to what has been considered in a number of papers for the mutual information based bounds) or to the setup where the distribution of each client comes from a metadistribution. The latter case is also not new; as considered for example in Theorem 5.1 in Zhang et al. (Neurips 2024). The established results are mainly an adaptation of the previous results; without any significant novelty.\n2. Many order-wise behaviors are not rigorous. See questions.", "other_comments_or_suggestions": "I found the notation very heavy and hard to follow. However, this may be partly unavoidable due to the complicated setup considered in this work.", "questions_for_authors": "1.\tMy main concern is with the implications of the bounds. What are the new conclusions we learn from these bounds for FL? What exactly is the message of this paper? I think the general argument that MI bounds can become vacuous but CMI bounds can never become unbounded is not sufficient for a new publication. The authors need to give concrete examples or study cases where their result brings a new insight or understanding.\n\n2.\tIn various places it is mentioned that the order is $\\mathcal{O}\\left(\\frac{1}{\\sqrt{K}}+\\frac{1}{\\sqrt{Kn}}\\right)$. However, if the order-wise behavior is examined, then $\\mathcal{O}\\left(\\frac{1}{\\sqrt{K}}+\\frac{1}{\\sqrt{Kn}}\\right)= \\mathcal{O}\\left(\\frac{1}{\\sqrt{K}}\\right)$. So the order-wise behavior of the bounds does not depend on $n$, which is a bad sign. Can you explain this?\n\n\n3.\tFollowing on from the above point, it seems that in various places the above conclusions implicitly assume that KL divergences (or mutual information) are $\\mathcal{O}\\left(1\\right)$, which is certainly not true in general. Therefore, the above order-wise behavior is not correct.\n\n4.\tIt is claimed that the bound of Theorem 6.2 becomes larger for more heterogeneous data. More precisely, it is mentioned that in the non-interpolating version of this result, the bound is proportional to $\\mathbb{E}[\\ell(W,Z_{i,j})]-\\mathbb{E}[\\ell(W_i,Z_{i,j})]$, and since this term becomes larger for more heterogeneous data, the bound then increases with heterogeneity. However, this argument is not sufficient because the second term of the bound is the square root of the product of this term and the conditional mutual information term. To evaluate the behavior of the bound with respect to heterogeneity, the behavior of this CMI term as a function of data heterogeneity must also be studied.", "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": "", "extra_scores": {}}, {"review_id": "32MQBL7FTv", "reviewer": "Reviewer_k9pd", "summary": "The paper introduces a novel information-theoretic framework to analyze generalization in federated learning (FL). By extending the supersample-based conditional mutual information (CMI) framework with a “superclient” construction, the authors decompose the generalization error into two components: the participation gap (between participating and non-participating clients) and the out‐of‐sample gap (local generalization error). They derive multiple CMI-based bounds, including high-probability and excess risk bounds, and show that differential privacy constraints naturally lead to tighter generalization guarantees. Experiments with FedAvg demonstrate that the evaluated CMI bounds are non-vacuous and reflect actual generalization behavior.\n\n## Update after rebuttal\nI will stay at my current score and recommend a (4): Accept", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "We thank you sincerely for your valuable feedback on our paper. Our responses follow.\n\n>- While the mathematical methods are solid, including more straightforward explanations or diagrams could help clarify the concepts for readers who may not be experts in the field. \n\n>- Another suggestion is to enhance the clarity of the presentation, perhaps through more diagrams or flowcharts, which would help readers unfamiliar with CMI techniques.\n\n**Response.** Thank you for your suggestion. We have included a visualization of our superclient and supersample construction, and we will also provide additional background on CMI techniques along with more accessible explanations of these concepts in the revised version.\n\n\n>- It would be beneficial if the paper discussed any limitations of these theoretical results, such as their dependence on the bounded loss function assumption.\n>-  Consider including a more detailed discussion of potential limitations or assumptions (e.g., reliance on bounded loss functions or the i.i.d. assumption in some cases). \n>- How sensitive are the bounds to deviations from the bounded loss assumption in practice?\n\n**Response.** Regarding the boundedness assumption, as noted in the paragraph immediately following Theorem 6.2 (Lines 361–362) in the paper, this assumption can be relaxed to a sub-Gaussian condition, where the loss function may be unbounded but exhibits Gaussian-like tail behavior. Under this relaxed assumption, all the theoretical results in our paper remain valid. In the case of heavy-tailed losses, additional techniques such as truncation would be required to ensure the results hold. We will elaborate further on these points in the revised version.\n\n>- The experimental work supports the theory; however, the paper could be improved by testing on more diverse datasets or different federated learning scenarios to provide a broader view of the approach’s effectiveness.\n\n**Response.** Thank you very much for the suggestion. We will include an additional dataset in the revised version, and if the reviewer has any specific dataset in mind, we would be happy to incorporate it.\n\n>- While the paper references key works in CMI and FL, a discussion comparing the new bounds with very recent developments in PAC-Bayesian approaches or alternative stability-based analyses could further contextualize the contributions.\n\n**Response.** Compared to PAC-Bayesian and stability-based bounds, our e-CMI bounds are significantly easier to estimate in practice. Moreover, existing PAC-Bayesian and stability-based bounds do not account for the participation gap and do not exhibit fast-rate behavior for overall generalization. We will include a more detailed discussion comparing our results with these existing bounds in the revised version.\n\n>- Could you provide further insight into how the e-CMI bounds might be estimated in high-dimensional settings beyond the one-dimensional case?\n\n**Response.** We note that the e-CMI bounds in our paper always involve mutual information between one-dimensional random variables by construction. Specifically, e-CMI refers to the mutual information between a single loss value (treated as a one-dimensional random variable, since the loss function maps inputs to real values) and a Bernoulli mask, which is a binary random variable. This low-dimensional structure makes e-CMI particularly easy to estimate, which is one of its key advantages.\n\n\n>- How do the derived bounds perform in non-i.i.d. client scenarios that are common in cross-device FL?\n\n**Response.** Our bounds hold under a non-i.i.d. setting in the sense that each client may have a different data distribution, which is typical in cross-device FL. However, we do assume that clients are sampled independently, and that within each client, data points are drawn i.i.d. If either of these assumptions does not hold, the generalization bounds would need to be refined using additional techniques to account for the dependencies, for example, by invoking graph-based dependencies among clients or modeling temporal (mixing) dependencies in the data. We will include this discussion in the revised version.", "claims_and_evidence": "The paper makes the following claims:\n- The superclient construction yields a two-level decomposition of generalization error with tight CMI-based bounds.\n- Differential privacy at both local and global levels ensures that CMI terms (and thus the generalization error) remain bounded.\n- Evaluated CMI (e-CMI) bounds can recover best-known FL convergence rates in low empirical risk regimes.\n\nThese claims are well supported by both detailed theoretical proofs (Theorems 4.1, 4.2, and 4.3) and empirical evaluations using standard FL frameworks such as FedAvg (discussed in Section 7).", "methods_and_evaluation_criteria": "The paper extends the existing conditional mutual information framework to federated learning. It introduces a new \"superclient\" construction along with supersamples to address the two levels of generalization error. The methods are rigorous, employing tools like KL divergence and concentration inequalities. \n\nWhile the mathematical methods are solid, including more straightforward explanations or diagrams could help clarify the concepts for readers who may not be experts in the field.", "theoretical_claims": "The authors make strong theoretical claims by breaking down the generalization error into two parts: the participation gap and the out-of-sample gap. They also show that differential privacy helps to keep these errors small. The detailed proofs build on well-known ideas from the literature. \n\nIt would be beneficial if the paper discussed any limitations of these theoretical results, such as their dependence on the bounded loss function assumption.", "experimental_designs_or_analyses": "The experimental work supports the theory; however, the paper could be improved by testing on more diverse datasets or different federated learning scenarios to provide a broader view of the approach’s effectiveness. \n\nThis suggestion is not a weakness (in terms of publication) but an opportunity for further validation.", "relation_to_broader_scientific_literature": "The work builds on established information-theoretic generalization analyses and extends them to the federated learning setting. It relates to recent advances in FL generalization and connects with the broader literature on differential privacy and meta-learning.", "essential_references_not_discussed": "While the paper references key works in CMI and FL, a discussion comparing the new bounds with very recent developments in PAC-Bayesian approaches or alternative stability-based analyses could further contextualize the contributions.", "other_strengths_and_weaknesses": "**Strengths:**\n- Innovative extension of the CMI framework with a superclient construction, addressing a gap in FL generalization analysis.\n- Rigorous theoretical derivations that are well-connected to existing literature.\n- Empirical validation that supports the theoretical claims.\n\n**Weaknesses:**\n- No major weaknesses were identified. The experimental section could be expanded to include more diverse FL settings or real-world datasets for broader validation", "other_comments_or_suggestions": "I do not have any major comments, and only have a few suggestions. Consider including a more detailed discussion of potential limitations or assumptions (e.g., reliance on bounded loss functions or the i.i.d. assumption in some cases). Another suggestion is to enhance the clarity of the presentation, perhaps through more diagrams or flowcharts, which would help readers unfamiliar with CMI techniques.", "questions_for_authors": "- How sensitive are the bounds to deviations from the bounded loss assumption in practice?\n- Could you provide further insight into how the e-CMI bounds might be estimated in high-dimensional settings beyond the one-dimensional case?\n- How do the derived bounds perform in non-i.i.d. client scenarios that are common in cross-device FL?\n\nProviding answers to these questions may help readers better understand and apply this framework to analyze their FL algorithms.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper introduces a novel theoretical framework based on Conditional Mutual Information (CMI) to analyze generalization in Federated Learning (FL), specifically addressing the two-level nature (out-of-sample and participation gaps) via a "superclient" construction. The work derives several CMI bounds within this framework and provides empirical estimations suggesting these bounds correlate with generalization behavior. The reviews present a split perspective: two reviewers strongly support the paper based on the theoretical novelty and framework extension, finding it a solid contribution despite potential looseness or lack of algorithm specificity. Conversely, two other reviewers express significant reservations, questioning the practical tightness, interpretability, and advantages over existing bounding techniques (like PAC-Bayes), while also criticizing the limited experimental scope and presentation clarity. The authors' rebuttal primarily defended the theoretical contribution and empirical methodology. While the concerns about the bounds' practicality and tightness are valid and characteristic of information-theoretic approaches, the consensus acknowledges the novelty of extending the CMI framework to FL's unique structure. Balancing the clear theoretical contribution against valid concerns about practical utility and experimental breadth, the paper appears to be a borderline case, leaning towards acceptance based on its novel framework for understanding FL generalization.
Decision: Accept (poster)