What Do We Mean by Generalization in Federated Learning?
Authors: Honglin Yuan
Warren Richard Morningstar
Lin Ning
Karan Singhal
Venue: ICLR 2022 Poster (2022)
Keywords: Federated Learning
generalization
heterogeneity

Abstract: Federated learning data is drawn from a distribution of distributions: clients are drawn from a meta-distribution, and their data are drawn from local data distributions. Generalization studies in federated learning should separate performance gaps from unseen client data (out-of-sample gap) from performance gaps from unseen client distributions (participation gap). In this work, we propose a framework for disentangling these performance gaps. Using this framework, we observe and explain differences in behavior across natural and synthetic federated datasets, indicating that dataset synthesis strategy can be important for realistic simulations of generalization in federated learning. We propose a semantic synthesis strategy that enables realistic simulation without naturally partitioned data. Informed by our ﬁndings, we call out community suggestions for future federated learning works.

Published as a conference paper at ICLR 2022
WHAT Do WE MEAN BY GENERALIZATION IN FEDERATED LEARNING?
Honglin Yuan' Stanford University
hongl. - yuan@gmail com
Warren Morningstar, Lin Ning, Karan Singhal
Google Research (wmorning, linning, kazansinghaaljegoole..com
ABSTRACT
Federated learning data is drawn from a distribution of distributions: clients are drawn from a meta-distribution, and their data are drawn from local data distri- butions. Thus generalization studies in federated learning should separate perfor- mance gaps from unseen client data (out-of-sample gap) from performance gaps from unseen client distributions (participation gap). In this work, we propose a framework for disentangling these performance gaps. Using this framework, we observe and explain differences behavior across natural and synthetic federated datasets, indicating that dataset synthesis strategy be important for realistic simulations generalization in federated learning. We propose semantic syn- thesis strategy that enables realistic simulation without -aarttall--ptttiooneed data. Informed by our findings, we call out community suggestions for future federated learning works.
INTRODUCTION
Federated learning (FL) enables distributed clients to train a machine learning model collaboratively via focused communication with coordinating server. In cross-device FL settings, clients sampled from a population for participation each round of training (Kairouz et al., 2019; Li et al., 2020a). Each participating client possesses its data distribution, from which finite samples drawn for federated training.
Given this problem framing, defining generalization in FL Existing works generally characterize the difference between empirical and expected risk for clients participating training (Mohri al., 2019; Yagli et al., 2020; Reddi et al., 2021; Karimireddy et al., 2020; Yuan et al., 2021). However, in cross-device settings, which we focus on in this work, clients are sampled from a large population with unreliable availability. Many or most clients may never participate in training (Kairouz et al., 2019; Singhal et al., 2021). Thus it is crucial to better understand expected performance for non-participating clients.
obvious in centralized learning.
In this work, we model clients' data distributions as drawn from meta population distribution (Wang et al., 202 I), an assumption we argue is reasonable in real-world FL settings. We use this framing to define two generalization gaps to study in FL: the out-of-sample gap, the difference between empirical and expected risk for participating clients, and the participation gap, or the difference in expected risk between participating and non-participating clients. Previous works generally ignore the participation gap or fail to disentangle it from the out-of-sample gap. but we observe significant participation gaps in practice across six federated datasets (see Figure 1), indicating that the participation gap is an important but neglected feature of generalization in FL.
We present systematic study of generalization in FL across six tasks. We observe that focusing only on out-of-sample gaps misses important effects, including differences in generalization behavior across naturally- partiiioooe and synthetically partitioned federated datasets. We use our results to inform series of recommendations for future works studying generalization in FL.
sathetiialll-ppaattionndd
Work was completed while Google Research.

---

Published as a conference paper at ICLR 2022
ENNIST-LL
EMRIST-92
QIAR-10
DIFAR-100
0.2
Stacompprre
E28
Stac Lnvervor
5.003
624
0.33
2800
2000
3300
2330
1248
2033
Paric paling training
partic paling valdation
unparticipa.ing
Figure Federated training results demonstrating participation gaps for six different tasks. We conduct experiments on four image classification tasks and two text prediction tasks. As described Section I, the participation gap can be estimated as the difference in metrics between participating validation and unparticipating data (defined in Figure 2). Prior works either ignore the participation gap or fail to separate it from other generalization gaps, indicating the participation gap is a neglected feature of generalization in FL.
Our contributions:
Propose a three-way split for measuring out-of-sample and participation gaps in centralized and FL settings where data is drawn from distribution of distributions (see Figure 2).
Observe significant participation gaps across six different tasks (see Figure and perform empirical studies on how various factors, e.g. number of clients and client diversity, affect generalization performance (see Section 5).
generalization behavior across synthetically partitioned paatttiially-aaiiiioneeeddd federated datasets, and propose semantic partitioning, dataset synthesis strategy that enables more realistic simulations of generalization behavior in FL without requiring catuuallly-patttionne data (see Section 4).
Observe significant differences
and
Present model to define the participation gap (Section 2), reveal its connection with data heterogeneity (Section 3.2), and explain differences in generalization behavior between label- based partitioning and semantic partitioning (Section 4.2).
Present recommendations for future FL works, informed by our findings (see Section 6).
Release extensible open-source code library for studying generalization in FL (see Repro- ducibility Statement).
1.1
RELATED WORK
We briefly discuss primary related work here and provide a detailed review Appendix A. We refer readers to Kairouz et al. (2019); Wang et al. (2021) for more comprehensive introduction to federated learning in general.
Distributional heterogeneity in FL. Distributional heterogeneity is one of the most important patterns in federated learning (Kairouz et al., 2019; Wang et al., 2021). Existing literature on FL heterogeneity is mostly focused the impact of heterogeneity the training efficiency (convergence and communication) of federated optimizers (Karimireddy et al., 2020; Li et al., 2020b; Reddi al., 2021). In this work, we identify that the participation gap is another major outcome of the heterogeneity in FL, and recommend using the participation gap as natural measurement for dataset heterogeneity.
Personalized FL. In this work, we propose to evaluate and distinguish the generalization performance of clients participating and non- non-participating in training. Throughout this work, we focus on the classic FL setting (Kairouz et al.. 2019; Wang et al., 2021) in which single global model is learned from and served to all clients. In the personalized FL setting (Hanzely & Richtárik, 2020; Fallah et al., 2020; Singhal et al., 2021), the goal is to learn and serve different models for different clients. While related, our focus and contribution orthogonal to personalization. In fact, our three-way split framework can be readily applied in various personalized FL settings. For example, for personalization via fine-tuning (Wang et al., 2019; Yu et al., 2020), the participating clients can be defined as the clients that contribute to the training of the base model. The participation gap then defined as the difference in post-fine- fine-tuned performance between participating clients and unparticipating clients.
2

---

Published as a conference paper at ICLR 2022
Out-of-distribution generalization. In this work, propose to train models using set of par- ticipating clients and examine their performance on heldout data from these clients as well as an additional set of non partticciippainnggggg clients. Because each client has different data distribution, unpar- ticipating clients' data exhibits distributional shift compared to the participating clients' validation data. Therefore, our work is related the field of domain adaptation (Daumé III, 2009; Ben-David et al., 2007; Shimodaira, 2000; Patel et al., 2015), where model is explicitly adapted to make predictions on test set that is not identically distributed to the training set. The participation gap that we observe is consistent with findings from the out-of- of-distribution research community (Ovadia al., 2019; Amodei et al., 2016; Lakshminarayanan et al., 2016), which shows on centrally trained (non-federated) models that even small deviations in the morphology of deployment examples can lead to systematic degradations
performance. Our setting differs from these other settings in that our problem framing assumes data is drawn from a distribution of client distributions, meaning that the training and deployment distributions eventually converge as more clients participate in training. In contrast, the typical OOD setup assumes that the distributions will never converge (since the deployment data is -iit-iiiiiiiitinonn by definition it does not contribute to training). Our deta-distribution assumption makes the problem of generalizing to unseen distributions potentially more tractable.
2 SETUP FOR GENERALIZATION IN FL
We model each FL client as a data source associated with local distribution and the overall population destr-iistiibtionn over all possible clients.
Definition 2.1 (Federated Learning Problem). Let E be the (possibly infinite) collection of all the possible data elements, e.g., image-label pairs. For any parameters us in parameter space O we use f(w,E) E) to denote the loss at element & with parameter w.
2. Let C be the (possibly infinite) collection of all the possible clients. Every client C is associated with a local distribution De supported on E.
Further, we assume there is meta-distribution supported on client set e, and each client c is associated with a weight Pe for aggregation.
The goal optimize the following two-level expected loss as follows:
F(w) = Ee<P [pe (f=:
Similar formulations as in Equation (1) have been proposed in existing literature (Wang et al., 2021; Reisizadeh et al., 2020; Charles Konečný, 2020). To understand Equation (1), consider a random procedure that repeatedly draws clients e from the meta-distribution P and then evaluates the loss on samples & drawn from the local data distribution D.. Equation (1) then characterizes the weighted-average limit of the above process.
Remark. The selection of client weights {Pe De::C c }} depends on the desired aggregation pattern. For example, setting Pc. = 1 will equalize the performance share across all clients. Another common example is setting Pe. to be proportional the training dataset size contributed by client
Intuitive Justification. The formulation in Equation (1) is especially natural in cross-device FL settings, where the number of clients is generally large and modeling clients' local distributions meta-distribun distribution is reasonable. This assumption also makes the problem of generalization to non- participaating client distributions more tractable since samples from the meta- distribution are seen during training.
as sampled from meta-
Discretization. While the ultimate goal is to optimize the expected loss over the entire meta- distribution P and client local distributions {DD:: c E C) only finite training data and a finite number of clients are accessible during training. We call the subset of clients that contributes training data the participating clients, denoted as We assume is drawn from the meta-disttibbtion P. For each participating client c E C, we denote É. the training data contributed by client c. We call these data participating training client data and assume E. satisfies the local distribution D..-
3

---

Published as a conference paper at ICLR 2022
Definition 2.2. The empirical risk the participating training client data is defined by
Faatt centttrainn (w))
==
Pc
f(w; E)
CE
CEIS.1
Equation (2) characterizes the performance of the model (at parameter w) on the observed data possessed by observed clients.
There are two levels of generalization between Equation (2) and Equation (I): (i) the generalization from finite training data to unseen data, and (ii) the generalization from finite participating clients to unseen clients. To disentangle the effect of the two levels, a natural intermediate stage is consider the performance on unseen data of participating (seen) clients.
Definition 2.3. The semi-empirical risk on the participating validation client data is defined by
F yaart (w)
Ie [[w=
CEE
Equation (3) differs from Equation (2) by replacing the intra-client empirical loss with the expected loss over Dee- We shall also call F(w) defined in Equation (1) the unparticipating expected risk and denote it as Funpart(w)) ) for consistency. Now are ready to define the levels of generalization gaps formally.
Definition 2.4. The out-of-sample gap is defined as vaart.val(w) F prart.train (w))
Definition 2.5. The participation gap is defined as Funpart(us (w) - F' [apart_aa
Note that these gaps also meaningful in centralized learning settings where data is sampled from a distribution of distributions.
3
UNDERSTANDING GENERALIZATION GAPS
3.1 ESTIMATING RISKS AND GAPS VIA THE THREE- WAY SPLIT
Both vaart.val and Fumpart take an expectation over the distribution of clients or data. To estimate these two risks in practice, we propose splitting datasets into three blocks. The procedure is demonstrated in Figure Given dataset with client assignment, we first hold out percentage of clients (e.g.. 20%) as unparticipating clients, shown in the rightmost two columns (in purple). The remaining clients are participating clients. We refer to this split as inter-client split. Within each participating client, we hold out a percentage of data (e.g.. 20%) participating validation data, as shown in the upper left block (in orange). The remaining data is the participating training client data, as shown in the lower left block (in blue). We refer to this second split as intra-client split.
Particppatng
Figure 2: Illustration of the three-way split via a visualization of the EMNIST digits dataset. Each column corresponds to the dataset of one client. A dataset split into participating training, participating validation, and unparticipating data, which enables separate measurement of out-of-sample and participa- tion gaps (unlike other works). Note only present the digit "6" for illustrative purposes.
6
&
6
6
6
HLTA Portcippiing training
Un-par coattiipptinng
Existing FL literature and benchmarks typically conduct either inter-client intra-client train- validation split. However, neither inter-client nor intra-client split alone can reveal the participation gap.' To the best of our knowledge, this is the first work that conducts both splits simultaneously.
3.2 WITY IS THE PARTICIPATION GAP INTERESTING?
Participation gap is an intrinsic property of FL due to heterogeneity. Heterogeneity across clients is one of the most important phenomena in FL. We identify that the participation gap is another
'To see this, observe that inter-client split can only estimate Fpartatrain and Funpart, and intra-client split can only estimate Frait and F Fpart.al-
4

---

Published as a conference paper at ICLR 2022
outcome of heterogeneity in FL, in that the gap will not exist if data is homogeneous. Formally, can establish the following proposition.
Proposition 3.1. Df = D for any E E and Pe. = p. then for any participating clients é C C and in domain, the participation gap is always zero in that Funpart (w)) parrt_yll (w))
Proposition 3.1 holds by definition as
Ppart. (w)
Ip-
(B = Bewp (p- (ewD(f(w;;)) = Funport (w)
CEe
Remark. We assume unweighted risk with Pe = p. ease of exposition. Even if Pe are different, one can still show Feupass(99) (w) is always equal to a constant independent of w. Therefore the triviality of the participation gap for homogeneous data still holds in the logarithmitic sense.
Participation gap can quantify client diversity. The participation gap can provide insight into federated dataset since it provides a quantifiable measure of client diversity heterogeneity. With other aspects controlled, federated dataset with larger participation gap tends have greater heterogeneity. For example, using the same model and hyperparameters, we observe in Section 5 that CIFAR-100 exhibits larger participation gap than CIFAR-10. 10. Unlike other indirect measures (such as the degradation of federated performance relative to centralized performance). the participation gap is intrinsic in federated datasets and more consistent with respect to training hyperparameters.
Participation gap can measure overfitting on the population distribution. Just as generalization gap that increases over time centralized training can indicate overfitting on training samples, large or increasing participation gap can indicate training process is overfitting on participating clients. We observe this effect in Figure for Shakespeare and Stack Overflow tasks. Thus measuring this gap can be important for researchers developing models or algorithms to reduce overfitting.
Participation gap can quantify model robustness unseen clients. From a modeler's perspective, the participation gap quantifies the loss of performance incurred by switching from seen clients to unseen clients. The smaller the participation gap is, the more robust the model might be when deployed. Therefore, estimating participation gap may guide modelers to design more robust models, regularizers, and training algorithms.
Participation gap quantify the incentive for clients to participate. From client's perspec- tive, the participation gap offers a measure of the performance gain realized by switching from unparticipating (not contributing training data) to participating (contributing training data). This is fair comparison since both val and fumpart are estimated on unseen data. When the participation gap is large (e.g., only few clients participate), modelers might report the participation gap as well-justified incentive to encourage more clients to join federated learning process.
4 REFLECTIONS ON CLIENT HETEROGENEITY AND SYNTHETIC PARTITIONING
Since participation gaps can quantify client dataset heterogeneity, study how participation gaps vary for different types of federated datasets. Many prior works (McMahan et al., 2017; Zhao et al., 2018; Hsu et al., 2019; Reddi et al., 2021) have created synthetic federated versions of centralized datasets. These centralized datasets do not have aaturally-occurriig be synthetically partitioned into clients. Due the importance of heterogeneity in FL, partitioning schemes generally ensure client datasets are heterogeneous in some respect. Previous works typically impose heterogeneity the label level. For example, Hsu al. (2019) create heterogeneous federated datasets by assigning each client a distribution over labels, where each local distribution is drawn from a Dirichlet decaadistribution. Once conditioned on labels, the drawing process homogeneous. We refer to these schemes as label-based partitioning."
client partitions and thus need to
While label heterogeneity is generally observed in natural federated datasets, it is not the only observed form of heterogeneity. In particular, each client in natural federated dataset has its own
"To avoid confusion. throughout this work, we use the term "partition" to refer to assigning data with no client assignment into synthetic clients. The term "split" refers to splitting federated dataset (with existing client assignments) measure different metrics (e.g., way-si.....lit..
5

---

Published as a conference paper at ICLR 2022
separate data generating process. For example, for Federated EMNIST (Cohen et al., 2017), different clients write characters using different handwriting. Label-based partitioning does not account for this form of heterogeneity. To show this, in Figure 3 visualize the clustering of client data between natural and label-based partitioning (Hsu et al., 2019) for Federated EMNIST. We project clients from each partitioning into 2D space using T-SNE (Van der Maaten & Hinton, 2008) applied to the raw pixel data. Naturally partitioned examples clearly cluster more than label-based partitioned examples, which appear be distributed similarly the full data distribution.
Partitioning
Figure 3: T-SNE projection of different partitionings of EMNIST. The top panel shows the panel shows the label-based synthetic dataset. The gray points are the projec- tions of examples from each dataset, obtained by aggregating the data from 100 clients each. The blue points show projections of data from single client. The naturally-partitiooeed
dataset (partitioned by writer), the bottom
naturally partitioned client data appears much more tightly clustered, whereas the partitioned data appears similarly distributed as the overall dataset, indicating that label-based partitioning may not fully represent realistic client heterogeneity.
Partitioning
Interestingly, differences in heterogeneity also significantly affect generalization behavior. In Figure 4, we compare the training progress of the naturall-paartitions partitioning following the scheme by Hsu et al. (2019). Despite showing greater label heterogeneity (Fig. 4(a)), the label-based partitioning does not recover any significant participation gap, in sharp contrast to the natural partitioning (Fig. 4(d)). In Figure 5, we also see minimal participation gap in label-based partitioning for CIFAR. This motivates a client partitioning approach that better preserves the generalization behavior of iaturally-partitionns datasets.
EMNIST dataset with a label-based
dee13
1.000
0470
dgg
(a) Label histogram of (b) Learning progress of label-hased partitioning label-hased partitioning
(c) Label histogram of (d) Learning progress of natural partitioning
natural partitioning
Figure 4: Comparison of label-based synthetic partitioning and natural partitioning of EMNIST-10. Observe that label-based partitioning shows greater label heterogeneity (a) than natural partitioning (c), while the participation gap (part_val unpart) for label-based synthetic partitioning (b) is significantly smaller than that for the natural partitioning (d).
4.1 SEMANTIC CLIENT PARTITIONING AND THE PARTICIPATION GAP
To explore and remediate differences in client heterogeneity across natural and synthetic datasets, we propose semantics-basee framework assign semantically similar examples clients during federated dataset partitioning. We instantiate this framework via an example of an image classification task.
Our goal is to reverse- eeverse-engineer the federated sutaset-genneattin process described in Equation (1) so that each client possesses semantically similar data. For example, for the EMNIST dataset, we expect every client (writer) to (i) write in consistent style for each digit (intra-client intra-label similarity) and (ii) use a consistent writing style across all digits (intra-client inter-label similarity). A simple approach might be to cluster similar examples together and sample client data from clusters. However, if one directly clusters the entire dataset, the resulting clusters may end up largely correlated to labels. To disentangle the effect of label heterogeneity and semantic heterogeneity, propose the following algorithm to enforce intra-client intra-label similarity and intra-cliem inter-label similarity in two separate stages.

---

Published as a conference paper at ICLR 2022
Stage 1: For each label, we embed examples using pretrained neural network (extracting semantic features), and fit a Gaussian Mixture Model to cluster pretrained embeddings into groups. Note that this results in multiple groups per label. This stage enforces intra-client intra-label consistency.
Stage 2: To package the clusters from different labels into clients, aim to compute optimal multi-partite matching with cost-matrix defined by KL-divergence between the Gaussian clusters. To reduce complexity, we heuristically solve the optimal multi-partite matching by progressively solving the optimal bipartite matching at each time for randomly-chosen label pairs. This stage enforces intra-client inter-label consistency.
We relegate the detailed setup to Appendix D. Using this procedure we can generate clients which have similar example semantics. We show in Figure 5 that this method of partitioning preserves the participation gap. In Appendix D, we visualize several examples of our semantic partitioning on various datasets, which can serve as benchmarks for future works.
CIFA-10 (nbel partt on
CIFR-10 teemantic parittion
CIFAR-100 [casmmejaaee parition
CFAR-100] seranti partiion
6:25
0.55
6.
6.1
0:30
0.30
0.85
0.85
0.7
0.7
0.40
0.80
0.6
0.6
6.75
0.75
0.30
0.30
8.5
6.4
0.1
6.40
0.50
300
1000 round
1992
300
1003
1507
302
1000 round
1532
500
3003 round
3500
round
participating training
--- participating validation
unparticipating
Figure 5: Comparison of label-based partitioning and semantic partitioning (ours). Results for CIFAR-10 10 and CIFAR- 100 are shown. Observe that semantic partitioning recovers the participation gap typically observed in naturally partttiiood data.
4.2
EXPLAINING DIFFERENCES BETWEEN LABEL-BASED AND SEMANTIC PARTITIONING
To explain the above behavior, we revisit our mathematical setup and the definition of the participation gap. Recall that the participation gap is defined (we omit the weights by setting P.. for simplicity):
1 Σ [
part swp( = Funpart(au) - Fpart val(w) = Eeup [E=DD [f(w;
EE ffw; E)]] (4)
In order to express the ideas without diving into details of measure theory, we assume without loss of generality that the meta-distribution P is a continuous distribution supported on e with probability density function pp (c). We also assume that for each client c E C. the local distribution D. is continuous distribution supported on Egt with probability density function PD, (E). Therefore, the participation gap becomes
(1 PD. (E)p((((())d
participatiion (w) = - ((w;))
ΣrD, PD. (E) (0)
dg. (5)
EEE
CE
Therefore the scale of participation gap could depend (negatively) on the concentration speed [
from 1 Eecê PD.(E) (E) to Seee PD. (P)pp(c)) as j + oo.3 We hypothesize that for label-based partitioning, the concentration is fast because each client has large entropy as it can cover the entire distribution of a given label. On the other hand, for natural or semantic partitioning, the concentration is slower the local distribution of each client has lower entropy due to the (natural synthetic) semantic clustering.
We validate our hypothesis with an empirical estimation of local dataset entropy, shown in Figure 6. We observe that the clients generated by label-based partitioning demonstrate much higher entropy than the natural ones. Notably, our proposed semantic partitioning has a very similar entropy distribution across clients as the natural partitioning. This indicates that the heterogeneity in EMNIST mostly attributed to semantic heterogeneity.
Onee can make the above claim rigorous with standard learning theory approaches such as uniform conver- gence and Rademacher complexity (Vapnik, 1998).
7

---

Published as a conference paper at ICLR 2022
Figure 6: Kernel density estimates of the distribution of client entropy for naturally-parttioned clients (top), semantic- partitioned clients (middle), and label-based partitioned clients (bottom). While naturally and semantically partitioned clients appear to have approximately the same distribution of client entropies, the synthetically partitioned clients are distributed differently and have higher average entropy (48 Nats) than the other forms of partitioning (44 Nats). We refer readers to Appendix E for the detailed methodol- ogy for the estimation of the entropy.
Panstern
0.02
0.81
Labe Partieriingggg
6:2
661
80
Entropy
Table 1: Summary of experimental results. We perform federated and centralized training across six tasks. EMNIST, Shakespeare, and StackOverflow are parutally-artttioneed, and CIFAR is semantically partitioned. Observe that the participation gaps (gap between part.val and unpart) are consistent across tasks. We provide other metric statistics across clients (such percentiles of metries) in Table of Appendix B.2.
Federated Training
Centralized Training
part.train
part.val
unpart
part_train
part.val
unpart
EMNIST-10 10
100.0
99.6
98.9
100.0
99.5
98.9
EMNIST-62
91.8
86.3
85.4
93.8
87.1
86.
CIFAR-10
97.5
83.3
81.6
99.7
86.3
84.9
CIFAR-100
99.8
57.2
54.2
99.9
59.7
55,4
Shakespeare
58.8
56.5
56.2
60.7
57.2
56.8
StackOverflow
26.4
25.5
25.2
27.9
26.2
25.6
EXPERIMENTAL EVALUATION
We conduct experiments in six settings, including four image classification tasks: EMNIST-1O (digits only), EMNIST-62 (digits and characters) (Cohen et al., 2017; Caldas et al., 2019), CIFAR-10 and CIFAR-101 (Krizhevsky et al., 2009); and two next character/word prediction tasks: Shakespeare (Caldas et al., 2019) and StackOverflow (Reddi et al., 2021). We use FEDAVGM for image classifica- tion tasks and FEDA DAM for text-based tasks (Reddi al., 2021). The detailed setups (including model, dataset preprocessing. hyperparameter tuning) are relegated to Appendix C. We summarize our main results in Figure and Table 1. In the following subsections, we provide more detailed ablation studies exploring how various aspects of training affect generalization performance.
5.1 EFFECT
NUMBER OF PARTICIPATING CLIENTS
In this subsection study the effect of the number of participating clients the generalization performance on various tasks. this end, we randomly sample subsets clients of different scales participating clients, and perform federated training with the same settings otherwise. The results are shown Figure 7. As the number of participating clients increases, the unparticipating accuracy monotonically improves, and the participation gap tends to decrease. This is consistent with theoretical understanding, as the participating clients can be interpreted as a discretization of the overall client population distribution.
5.2 EFFECT OF CLIENT DIVERSITY
In this subsection, we study the effect of client diversity on generalization performance. Recall that in the previous subsection, we vary the number of participating clients while keeping the amount of training data per client unchanged. As result, the total amount of training data will grow proportionally with the number of participating clients.
To disentangle the effect of diversity and the growth of training data size, in the following experiment, we instead fix the total amount of the training data, while varying the concentration across clients. The
'In addition, we experimented with FEDYOGI on these tasks. The performance is comparable (in terms of both participating validation and unparticipating metrics). We also experimented with vanilla FEDAVG and FEDADAGRAR which are less effective than the other adaptive optimizers in these settings, but the participation gaps are generally consistent.
8

---

Published as a conference paper at ICLR 2022
EMNIST-10
EMNIST-62
Shakespeare
Stackoverflow
1,000
0.28
0.995
accuracy
accuracy
accuracy
0.575
accuracy
0.26
0.90
0.985
0.85
0.980
0.525
0.975
10?
10a
10a
10a
10a
107
10
participating participating training
participating clients
participating clients
participating clients
-
participating validation
unparticipating
Figure 7: Effect of the number of participating clients. See Section 5.1 for discussion.
Figure 8: Effect of diversity generalization. We fix the total amount of training data while varying the concentration across clients. The concentration varies from taking only 5% clients as participating clients where each client contributes 128 training data, the most diverse distribution with 80% clients as partic- ipating clients but each client only contributes 8 training data. Observe that while the total amount of training data is identical, the more diverse settings exhibit better performance in terms of both participating validation and unparticipating accuracy.
1.000
0.355
0.390
0.39
partidzeshhg maitigg
cepart gating
59 Eat. 12% eat. 22% pari
c0s par: 201 port
experiment conducted the EMNIST digits dataset. As shown in Figure 8, the training data from a new participating client can be more valuable than those contributed by the existing participating clients. The intuition can also be justified by our model in that the data from a new participating client is drawn from the overall population distribution Soge Pp(c)pp, (E)dc, whereas the data from existing clients are drawn from the distribution aggregated by existing clients J reveals the importance of client diversity in federated training.
[e] Ecee (E) This
5.3
OVERVIEW OF ADDITIONAL EXPERIMENTS APPENDICES
We provide more detailed analysis and further experiments in Appendices B and C, including:
Training progress of centralized optimizers on six tasks, see Appendix B.I.
Detailed analysis of metrics distributions across clients, see Appendices B.2 and B.3. We observe that the unparticipating clients tend exhibit longer tails on the lower side of accuracy.
Results on alternative hyperparameter choices, see Appendices C.1.1 and C.2.1.
Effect of multiple local epochs per communication round, see Appendix C.1.2.
Effect of the strength of weight decay, see Appendix C.2.2.
Effect of model depth, see Appendix C.2.3.
COMMUNITY SUGGESTIONS
In this work we have used the three-way-split, dataset partitioning strategies, and distributions of metrics systematically study generalization behavior in FL. Our results inform the following suggestions for the FL community:
Researchers can use the three-way way split to disentangle sut-ol-sample and participation gaps in empirical studies of FL algorithms.
When proposing new federated algorithms. researchers might prefer using naturally- partitioned or semantically plartiiaallyyyaatiioneeeee datasets for more realistic simulations of generalization behavior.
Distributions of metrics across clients (e.g., percentiles, variance) may vary across groups in the three- three-way split (see Table and Figure 10). We suggest researchers report the distribution of metrics across clients, instead of just the average, when reporting metrics for participating and con-patticipating clients. We encourage researchers to pay attention to the difference of two distributions (participating validation and unparticipating) may have fairness implications.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENTS
We would like to thank Zachary Charles, Zachary Garrett, Zheng Xu, Keith Rush, Hang Qi, Brendan McMahan, Josh Dillon, and Sushant Prakash for helpful discussions various stages this work.
REPRODUCIBILITY STATEMENT
We provide complete descriptions of experimental setups, including dataset preparation and prepro- cessing, model configurations, and hyperparameter tuning in Appendix C. Appendix D describes the detailed procedure for semantic partitioning. and Appendix presents the detailed approach for estimating the entropy that generates Figure 6.
We are also releasing an extensible code framework for measuring out-of-sample and participation gaps and distributions of metrics (e.g., percentiles) for federated algorithms across several tasks. We include all tasks reported this work; the framework is easily extended with additional tasks. We also include libraries for performing abbel-based and semantic dataset partitioning (enabling new benchmark datasets for future works, see Appendix D). This framework enables easy reproduction of results and facilitates future work. The framework is implemented using TensorFlow Federated (Ingerman & Ostrowski, 2019). The code is released under Apache License 2.0. We hope that the release of this code encourages researchers to take up our suggestions presented in Section 6.
REFERENCES
Alekh Agarwal, John Langford, and Chen-Ye Yu Wei. Federated Residual Learning, arXiv:2003.12880 [cs, stat], 2020.
Maruan Al-Shedivat, Jennifer Gillenwater, Eric Xing, and Afshin Rostamizadeh. Federated learning via Posterior Averaging: A New Perspective and Practical Algorithms. In International Conference Learning Representations, 2021.
Alyazeed Albasyoni, Mher Safaryan, Laurent Condat, and Peter Richtárik. Optimal Gradient Compression for Distributed and Federated Learning. arXiv:2010.03246 [cs, math), 2020.
Dario Amodei, Chris Olah, Jacob Steinhardt, Paul Christiano, John Schulman, and Dan Mané. Concrete problems in ai safety. arXiv preprint 1606:: 2016.
Maria-Florina Balean, Mikhail Khodak, and Ameet Talwalkar. Provable guarantees gradient-based meta- learning. In Proceedings of the 36th International Conference on Machine Learning, volume 97. PMLR, 2019.
Borja Balle, Peter Kairouz, Brendan McMahan, Om Dipakbhai Thakkar, and Abhradcep Thakurta. Privacy amplification via random check-ins. In Advances in Neural Information Processing Systems 33, volume 33, 2020.
Debraj Basu, Deepesh Data, Can Karakus, and Suhas Diggavi. Qsparse-local-sgle Distributed SGD with guantization, sparsification and local computations. Advances Neural Information Processing Systems 32. Curran Associates, Inc., 2019.
Shai Ben-David, John Blitzer, Koby Crammer, Fernando Pereira, al. Analysis representations for domain adaptation. Advances in neural information processing systems, 19:137, 2007.
Aleksandr Beznosikov, Samuel Horváth, Peter Richtárik, and Mher Safaryan. On Biased Compression for Distributed Learning. arXiv:2002. 12410 [cs. math, stat]. 2020.
llii Bistritz, Ariana Mann, and Nicholas Bambos. Distributed Distillation for On-Device Learning. In Advances in Neural Information Processing Systems 33, volume 33, 2020.
Gavin Brown, Mark Bun, Vitaly Feldman, Adam Smith, and Kunal Talwar. When is Memorization of Irrelevant Training Data Necessary for High-Accuracy Learning? arXiv:2012.06421 [cs], 2020.
Yuri Burda, Roger Grosse, and Ruslan Salakhutdinov. Importance weighted autoencoders. arXiv preprint arXiv: 1wX.000500000019 2015.
Please visit httph::t/////tt 1 -egeera zzt for the code repository.
10

---

Published as a conference paper at ICLR 2022
Sebastian Caldas, Sai Meher Karthik Duddu, Peter Wu, Tian Li, Jakub Konečný. H. Brendan McMahan, Virginia Smith, and Ameet Talwalkar. LEAF: Benchmark for Federated Settings, In NeurIPS 2019 Workshop on Federated Learning for Data Privacy and Confidentiality, 2019.
Zachary Charles and Jakub Konečný. On the outsized importance of learning rates in local update methods. arXiv preprint uxXiv2200000888, 2020.
Fei Chen, Mi Luo, Zhenhua Dong, Zhenguo Li, and Xiugiang He. Federated Meta-Learning with Fast Convergence and Efficient Communication. arXiv:1802.0780 1802.07876 [cx], 2019.
Hong-You You Chen and Wei-Lun Chao. FedBE: Making Bayesian Model Ensemble Applicable to Federated Learning. In International Conference on Learning Representations. 2021.
Xiangyi Chen, Steven Wu, and Mingyi Hong. Understanding gradient clipping in private SGD: A geometric perspective. In Advances in Neural Information Processing Systems 33, 2020.
Gregory Cohen, Saced Afshar, Jonathan Tapson, and André van Schaik. EMNIST: An extension MNIST to handwritten letters. CoRR, abs/1702.05373. 2017.
Hal Daumé III. Frustratingly easy domain adaptation. arXiv preprint arXiv:0907.1815 2009.
Yuyang Deng, Mohammad Mahdi Kamani, and Mehrdad Mahdavi. Adaptive Personalized Federated Learning. arXiv:2003. [cs, stat], 2020.
Enmao Dian, Jie Ding, and Vahid Tarokh. Heterofl: Computation and communication efficient federated learning for heterogencous clients. arXiv preprint 2rX1v:2010.01664, 2020.
Fartash Faghri, Iman Tabrizian, Lli Markov, Dan Alistarh, Daniel M Roy, and Ali Ramezani- Adap- tive gradient quantization for data parallel SGD. In Advances in Neural Information Processing Systems, volume 33. Curran Associates, Inc., 2020.
Alireza Fallah, Aryan Mokhtari, and Asuman E. Ozdaglar. Personalized federated lcarning with thcoretical guarantees: A model-agnostic meta-learning approach. In Advances in Neural Information Processing Systems 33, 2020.
Jonas Geiping. Hartmut Bauermeister, Hannah Dröge, and Michael Moeller. Inverting Gradients How easy is it
break privacy in federated learning? In Advances Neural Information Processing Systems 33, 2020.
Margalit Glasgow, Honglin Yuan, and Tengyu Ma. Sharp bounds for federated averaging (local sgd) and continuous perspective. arXiv preprint 111:22111.03741, 2021.
Eduard Gorbunov, Dmitry Kovalev, Dmitry Makarenko, and Peter Richtárik. Linearly converging compen- sated SGD. In Advances in Neural Information Processing Systems 33, volume 33, 2020.
Patrick J. Grother and Patricia A. Flanagan. NIST Handprinted Forms and Characters, NIST Special Database 19., 1995.
Farzin Haddadpour, Mohammad Mahdi Kamani, Mehrdad Mahdavi, and Viveck Cadambe. Trading redundancy for communication: Speeding up distributed SGD for non-convex optimization. In Proceedings of the 36th International Conference on Machine Learning, volume 97. PMLR, 2019a.
Farzin Haddadpour, Mohammad Mahdi Kamani, Mehrdad Mahdavi, and Viveck Cadambe. Local SGD with periodic averaging: Tighter analysis and adaptive synchronization. In Advances in Neural Information Processing Systems 32, Curran Associates, Inc., 2019b.
Filip Hanzely and Peter Richtárik. Federated Learning of a Mixture of Global and Local Models. arXiv:202.05511 [cs, math, stat), 2020.
Filip Hanzely, Slavomir Hanzely, Samuel Horváth, and Peter Richtárik. Lower bounds and optimal algorithms for personalized federated learning. In Advances in Neural Information Processing Systems 33, 2020.
Weituo Hao, Nikhil Mehta, Kevin J. Liang, Pengyu Cheng, Mostafa El-Khamy, and Lawrence Carin. WAFFLe: Weight Anonymized Factorization for Federated Learning. arX1v:2008.05687 [cs, star), 2020.
Chaoyang He, Murali Annavaram, and Salman Avestimehr. Group Knowledge Transfer: Federated Learning of
Large CNNs at the Edge. In Advances in Neural Information Processing Systems 33, volume 33, 2020.
Kaiming He, Xiangyu Zhang, Shanqing Ren, and Jian Sun. Deep Residual Learning for Image Recognition. In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016.
11

---

Published as a conference paper at ICLR 2022
Samuel Horváth and Peter Richtárik. A Better Altemative Error Feedback for Communication--ffiiciii Distributed Learning, a7Xiv:2006.10077 [cs, stat), 2020.
Kevin Hsich, Amar Phanishayee. Onur Mutlu, and Phillip B. Gibbons. The Non-IID Data Quagmire of Decentralized Machine Learning, arXiv:1910.00189 [cs, stat]. 2019.
Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown. Mcasuring the Effects of Non-Identical Data Distribution for Federated Visual Classification. MxXi:I9909006333 [cs, stat], 2019.
Baihe Huang, Xiaoxiao Li, Zhao Song, and Xin Yang. FL-NTK: A neural tangent kemel-based framework for federated learning analysis. In Proceedings of the 38th International Conference on Machine Learning, volume 139, PMLR, 2021.
Alex Ingerman and Krzys Ostrowski. Introducing TensorFlow Federated, 2019.
Rustem Islamov, Xun Qian, and Peter Richtárik. Distributed Second Order Methods with Fast Rates and Compressed Communication. ICML 2021, 2021.
Yihan Jiang, Jakuh Konečný, Keith Rush, and Sreeram Kannan. Improving Federated Learning Personalization via Model Agnostic Meta Learning. A909 12488 fes, stat], 2019.
Yuang Jiang, Shiqiang Wang. Victor Valls, Bong Jun Ko, Wei-Han Lee, Kin K. Leung, and Leandros Tassiulas. Model Pruming Enables Efficient Federated Learning on Edge Devices. arXiv: 12326 [cs, stat], 2020.
Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mchdi Bennis, Arjun Nitin Bhagoji, Keith Bonawitz, Zachary Charles. Graham Cormode, Rachel Cummings, Rafael G. L. O'ivveia,, Salim El Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaid Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konečný. Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateck Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Mariana Raykova, Hang Qi, Daniel Ramage, Ramesh Raskar, Dawn Song, Weikang Song. Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramèr, Pranceth Vepakomma, Jianyu Wang, Li Xiong, Zheng Xu, Qiang Yang, Felix X. Yu, Han Yu, and Sen Zhao. Advances and Open Prohlems in Federated I Learning. arXiv: N 29197777777777 [cs, stat], 2019.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank J. Reddi, Sebastian U. Stich, and Ananda Theertha Suresh. SCAFFOLD: Stochastic Controlled Averaging for Federated Learning. In Proceed- ings of the International Conference on Machine Learning I Pre-Proceedings (ICML 2020), 2020.
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter Theory for Local SGD on Identical and Hetterogenoous Data. In Proceedings the Twenty Third International Conference Artificial Intelligence and Statistics, volume 108. PMLR, 2020.
Mikhail Khodak, AariiaFlorina F Balcan, and Ameet S Talwalkar. Adaptive Gradient-Bass Meta-Learning Methods. In Advances in Neural Information Processing Systems 32, volume 32. Curran Associates, Inc.. 2019.
Diederik Kingma and Prafulla Dhariwal. Glow: Generative flow with invertible Ixl convolutions. arXiv preprint arXiv:1807.03030 2018
Diederik P Kingma and Max Welling. Auto-encoding variational bayes. arXiv preprint arXiv: 1rI.vv 2013.
Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi. and Sebastian U. Stich. A Unified Theory of Decentralized SGD with Changing Topology and Local Updates. Proceedings of the International Conference on Machine Learning Pre-Proceedings (ICMI. 2020), 2020.
Jakub Konečný, H. Brendan McMahan, Daniel Ramage, and Peter Richtárik. Federated Optimization: Distributed Machine Learning for On-Device Intelligence. arXiv:1610.00 [cs]. 2016.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Balaji Lakshminarayanan. Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. arXiv preprint 61211:1612.01174, 2016.
Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated Learning: Challenges, Methods, and Future Directions. IEEE Signal Processing Magazine, 37(3), 2020a.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogencous networks. In Proceedings of Machine Learning and Systems 2020, 2020b.
12

---

Published as a conference paper at ICLR 2022
Tian Li, Maziar Sanjabi, Ahmad Beirami, and Virginia Smith. Fair resource allocation in federated learning. In International Conference on Learning Representations. 2020c.
Xiang Li, Kaixuan Huang, Wenhao Yang. Shusen Wang, and Zhihua Zhang. On the convergence of FedAvg on non-iid data. International Conference on Learning Representations, 2020d.
Xiaoxiao Li, Meirui Jiang, Xiaofei Zhang, Michael Kamp, and Qi Dou. FedBN: Federated learning on Non-IID features via local batch normalization. In International Conference on Learning Representations, 2021.
Paul Pu Liang. Terrance Liu, Liu Ziyin, Nicholas B. Allen, Randy P. Auerbach, David Brent, Ruslan Salakhutdi- nov, and Louis- Phillipp Morency. Think Locally, Act Globally: Federated Learning with Local and Global Representations. 0rXiv:200100152. [cs, stat], 2020.
Tao Lin, Lingjing Kong, Sebastian U. Stich, and Martin Jaggi. Ensemble Distillation for Robust Model Fusion in Federated Learning. In Advances in Neural Information Processing Systems 33, 2020.
Ben London. PAC Identifiability in Federated Personalization. In NeurlPS 2020 Workshop on Scalability, Privacy and Security in Federated Learning (SpicyFI.), 2020.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas, Communication- efficient learning of deep networks from decentralized data. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54, PMLR, 2017.
Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. In Proceedings of the 36th International Conference on Machine Learning, volume 97. PMLR, 2019.
Alex Nichol, Joshua Achiam, and John Schulman. On First-Order Meta-Learning Algorithms. arXi::1803.02999 [cs], 2018
Yaniv Ovadia, Emily Fertig, Jie Ren, Zachary Nado, David Sculley, Sebastian Nowozin, Joshua V Dillon, Balaji Lakshminarayanan, and Jasper Snoek. Can you trust your model's uncertainty? evaluating predictive uncertainty under dataset shift. arXiv preprint arXiv:/906.025500 2019.
Vishal M Patel, Raghuraman Gopalan, Ruonan Li, and Rama Chellappa. Visual domain adaptation: A survey of recent advances. IEEE signal processing magazine, 32(3):53 69, 2015.
Reese Pathak and Martin J. Wainwright. FedSplit: An algorithmic framework for fast foderated optimization. In Advances in Neurul Information Processing Systems 33, 2020.
Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and H. Brendan McMahan. Adaptive Federated Optimization. In International Conference on Learning Representations, 2021.
Amirhossein Reisizadeh, Farzan Farnia, Ramtin Pedarsani, and Ali Jadbabaic. Robust federated learning: The case of affine distribution shifts. arXiv preprint arXiv:2006.08907, 2020.
Tim Salimans, Andrej Karpathy, Chen, and Diederik P Kingma. Pixelenn++: Improving the pixelenn with discretized logistic mixture likelihood and other modifications. arXiv preprint /7Xi::/701.055/7, 2017.
Hidetoshi Shimodaira. Improving predictive inference under covariate shift by weighting the log-likelhhood function. Journal of statistical planning and inference, 90(2):227-244, 2000.
Karan Singhal, Hakim Sidahmed, Zachary Garrett, Shanshan Wu, Keith Rush, and Sushant Prakash. Federated Reconstruction: Partially Local Federated Learning. Advances in Neural Information Processing Systems, 2021.
Virginia Smith, Chao-Kai Chiang, Maziar Sanjabi, and Ameet S Talwalkar. Federated multi-task learning. In Advances Neurul Information Processing Systems 30. Curran Associates, Inc., 2017.
Jinhyun So, Basak Guler, and Salman Avestimehr. A Scalable Approach for Preeee--Peeeiingg Collaborative
Machine Learning. In Advances in Neural Information Processing Systems 33, 2020.
Jy-yong Sohn, Dong-Jun Han, Beongjun Choi, and Jaekyun Moon. Election coding for distributed learning: Protecting SignSGD against byzantine attacks. In Advances in Neural Information Processing Systems 33, 2020.
Schastian U. Stich. Local SGD converges fast and communicates little. In International Conference on Learning Representations, 2019.
13

---

Published as a conference paper at ICLR 2022
Canh T. Dinh, Nguyen Tran, and Tuan Dung Nguyen. Personalized Federated Learning with Moreau Envelopes. In Advances in Neural Information Processing Systems 33, 2020.
Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 9(11), 2008
Vladimir Naumovich Vapnik. Statistical Learning Theory. Wiley, 1998.
Jianyu Wang and Gauri Joshi. Cooperative SGD: A unified Framework for the Design and Analysis of Communication--fiiee SGD Algorithms. arXiv: 1808.018080077777 [cs, stat], 2018.
Jianyu Wang. Vinayak Tantia, Nicolas Ballas, and Michael Rabbat. SlowMo: Improving communication-efficeent distributed SGD with slow momentum. In International Conference on Learning Representations, 2020a.
Jianyu Wang, Zachary Charles. Zheng Xu, Gauri Joshi, II Brendan McMahan. Maruan Al-Shedivat, Galen Andrew, Salman Avestimehr, Katharine Daly, Deepesh Data, et al. A field guide to federated optimization. arXiv preprint arXiv:2107.069) 2021.
Kangkang Wang. Rajiv Mathews, Chloé Kiddon, Hubert Eichner, Françoise Beaufays, and Daniel Ramage. Federated Evaluation of On-device Personalization. arXiv:1910.1023 [cs, stat], 2019.
Tianhao Wang. Johannes Rausch, Ce Zhang, Ruoxi Jia, and Dawn Song. A Principled Approach Data Valuation for Federated Learning. In Federated Learning, volume 12500. Springer International Publishing. 2020b.
Blake Woodworth, Kumar Kshitij Patel, and Nathan Srebro. Minibatch Local SGD for Heterogeneous Distributed Learning. In Advances in Neural Information Processing Systems 33, 2020.
Yuxin Wu and Kaiming He. Group normalization. In Proceedings of the European Conference on Computer Vision (ECCV), 2018.
Semih Yagli, Alex Dytso, and H. Vincent Poor. Information- Theooreti Bounds on the Generalization Error and Privacy Leakage in Federated Learning. In 2020 IEEE s International Workshop on Signal Processing Advances in Wireless Communications (SPAWC). IEEE, 2020.
Hao Yu and Rong Jin. On the computation and communication complexity of parallel SGD with dynamic batch sizes for stochastic non-convex optimization. In Proceedings of the 36th International Conference on Machine Learning, volume 97. PMLR, 2019.
Hao Yu, Rong Jin, and Sen Yang. On the linear speedup analysis of communication efficient momentum SGD for distributed non-convex optimization. In Proceedings of the 36th International Conference on Machine Learning, volume 97. PMLR, 2019.
Tao Yu, Eugene Bagdasaryan, and Vitaly Shmatikov. Salvaging Federated Learning by Local Adaptation. arXiv:2002.00 04758 [cs, stat), 2020.
Honglin Yuan and Tengyu Ma. Federated Accelerated Stochastic Gradient Descent. In Advances in Neural Information Processing Systems 33, 2020.
Honglin Yuan, Manzil Zaheer, and Sashank Reddi. Federated Composite Optimization. In Proceedings of the 38th International Conference on Machine Learning, 2021.
Xinwei Zhang, Mingyi Hong. Sairaj Dhople, Wotao Yin, and Yang Liu. FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity to Non-IID Data. arXiv:2005. [cs, stat], 2020.
Yue Zhao, Meng Li, Liangzhen Lai, Naveen Suda, Damon Civin, and Vikas Chandra. Federated learning with Non-IID Data. 1rXiv:1806.000 00582 [cs, stat], 2018.
Fan Zhou and Guojing Cong. On the convergence properties of k-step averaging stochastic gradient descent algorithm for nonconvex optimization. In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, 2018
Wennan Zhu, Peter Kairouz, Brendan McMahan, Haicheng Sun, Wei Li. Federated Heavy Hitters Dis- covery with Differential Privacy. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statisties, volume 108. PMLR, 2020.
14

---

Published as a conference paper at ICLR 2022
Appendices
LIST OF APPENDICES
A Additional Related Work
16
Additional Experimental Results
16
B.1 Training progress of centralized optimizers
16
B.2 Percentiles of metrics across clients
16
B.3 Federated training progress at the 25th percentile acorss clients
17
Additional Details on Experimental Setup and Task-Specific Experiments
18
C.1
EMNIST Hand-written Character Recognition Task
18
C.I.1
Consistency across various hyperparameters choices
18
C.1.2
Effect of multiple local epochs per communication round
19
C.2 CIFAR 10/100 Image Classification Task
19
C.2.1
Consistency across various hyperparameters choice
19
C.2.2
Effect of Weight Decay Strength
19
C.2.3
Effect of Model Depth
21
C,3
Shakespeare Next Character Prediction Task
C.4
Stackoverflow Next Word Prediction Task
21
Details of Semanticically Partitioned Federated Dataset
22
D.1 Details of the Semantic Partitioning Scheme
22
D.2 Visualization of Semanticically Partitioned CIFAR-100 Dataset ................................
22
D.3 Visualization of Semantically Partitioned MNIST Dataset
22
Methodology for Computing Entropy
24
15

---

Published as a conference paper at ICLR 2022
A ADDITIONAL RELATED WORK
Recent years have observed a booming interest in various aspects of Federated Learning, including
communication-effiicci learning (McMahan al., 2017; Konečný al., 2016; Zhou & Cong, 2018;
Haddadpour et al., 201 19: Wang & Joshi, 2018; Yu & Jin, 2019; Yu et al., 2019; Basu et al., 2019;
Stich, 2019; Khaled al., 2020; Yuan & Ma, 2020; Woodworth et al., 2020; Yuan et al., 2021;
Li et al., 2021: Huang et al., 2021: Glasgow et al.. 2021), model ensembling (Bistritz et al., 2020;
He et al., 2020; Lin et al., 2020: Chen & Chao, 2021). integration with compression (Faghri et al..
2020; Gorbunov et al., 2020; Sohn et al., 2020; Beznosikov et al., 2020; Horváth & Richtárik, 2020;
Albasyoni al., 2020; Jiang al., 2020; Islamov et al., 2021), systems heterogeneity (Smith et al., 2017; Diao et al., 2020), data (distributional) heterogeneity (Haddadpour et al., 2019b; Khaled et al.,
2020; Li et al.. 2020d: Koloskova et al., 2020; Woodworth et al., 2020; Mohri et al., 2019; Zhang et al., 2020: Li et al., 2020b; Wang al., 2020a; Karimireddy et al., 2020; Pathak & Wainwright, 2020; Al-Shedivat et al., 2021), fairness (Wang et al., 2020b; Li et al., 2020c; Mohri et al., 2019),
personalization (Smith et al., 2017; Nichol et al., 2018; Khodak al., 2019; Balcan et al., 2019;
Jiang et al., 2019; Wang et al., 2019 Chen et al., 2019; Fallah et al., 2020; Hanzely et al., 2020;
London, 2020; T. Dinh al., 2020; Yu et al., 2020: Hanzely & Richtárik, 2020; Agarwal al.,
2020; Deng et al., 2020; Hao et al.. 2020: Liang et al., 2020), and privacy (Balle et al., 2020; Chen al., 2020; Geiping et al., 2020: London, 2020; So al., 2020; Zhu al., 2020; Brown al., 2020). These works often study generalization and convergence for newly proposed algorithms. Huang et al. (2021) studied the generalization of Federated Learning in Neural-tangent kernel regime. But, to our knowledge, there is no existing work that disentangles out-of-sample and participation gaps federated training. We refer readers to (Kairouz et al., 2019; Wang et al., 2021) 1) for a more comprehensive survey on the recent progress in Federated Learning.
B ADDITIONAL EXPERIMENTAL RESULTS
In this section, we present several experimental results omitted from the main body due to space constraints. Additional task-specific ablation experiments can be found in Appendix C.
B.1 TRAINING PROGRESS OF CENTRALIZED OPTIMIZERS
In this subsection, we repeat the experiment in Figure 1 with centralized training. The results are shown in Figure 9. Observe that participation gap still exists with centralized optimizers. This is because the participation gap an intrinsic outcome of the heterogeneity of federated dataset.
EMNIST-10
EHNSS-62
CITAR-13
DFFR-100
peare
kovw fllow
6:54
6:12
099
paric palicpaiinggggo training
partic pating valdation
urparticipat.ng
Figure 9: Centralized training progress on six different federated tasks. Observe that the partici- pation gap still exists even with centralized optimizers. We refer readers to Table 1 for a quantitative comparison between federated optimizers and centralized optimizers.
B.2 PERCENTILES OF METRICS ACROSS CLIENTS
In this subsection, we report the detailed statistics of metrics across clients. Recall that in Table 1, we aggregated the metrics across clients by weighted averaging, where the weights are determined by the number of elements contributed by each client. In the following Table 2, we report five percentiles of metrics across clients: 95th T5th 50th (a.k.a. median), 25th and 5th These statistics provide detailed characterization on the metrics distribution across clients.
TTo make the percentiles comparable, we ensure the un-participating clients and participating validation clients have the same scale of elements per client.
16

---

Published as a conference paper at ICLR 2022
Table 2: Percentiles of metrics across clients on six federated tasks. We observe that the unpartici- pating clients tend to exhibit longer tails on the lower side of accuracy. For example, the participating clients of EMNIST- 10 have perfect (100%) accuracy even for clients at the 5th percentile, whereas the unparticipating clients only achieve 91.7%.
Federated Training
Centralized Training
percentile
part_val
unpart
part_val
unpart
95th
100.0
100.0
100.0
100.0
75th
100.0
100.0
100.0
100.0
EMNIST-10
50th
100.0
100.0
100.0
100.0
25th
100.0
100.0
100.0
100.0
5th
100.0
91.7
100.0
91.7
95th
100.0
100.0
100.0
100.0
75th
93.3
92.3
93.5
93.5
EMNIST-62
50th
88.2
87.1
87.5
87.5
25th
82.1
78.6
81.8
79.2
5th
66.7
64.7
71.4
70.6
95th
93.2
90.0
95.5
92.9
75th
88.2
86.0
90.9
89.1
CIFAR-10
50th
83.0
81.3
87.0
85.7
25th
79.2
76.7
82.1
81.5
5th
71.1
69.6
77.1
73.7
95th
65.4
62.4
66.7
62.6
75
61.1
56.7
64.2
56.6
CIFAR-100
50th
57.3
53.8
61.3
55.7
25th
53.9
51.9
55.5
52.8
5th
46.9
46.4
50.4
50.4
95th
68.4
71.4
70.1
71.4
t5th
60.8
60.0
61.7
61.1
Shakespeare
50th
57.3
56.8
58.2
57.5
25th
54.0
53.1
54.5
53.7
5th
38.4
38.2
42.6
40.9
95th
31.0
31.3
31.8
31.4
t5
27.7
27.7
28.8
27.9
StackOverflow
50th
25.6
25.4
26.3
25.9
25th
23.5
23.2
24.2
23.7
5th 20.1
20.0
20.8
20.7
B.3 FEDERATED TRAINING PROGRESS THE T5TH PERCENTILE ACORSS CLIENTS
To further inspect the distribution of metrics across clients, we plot the 25th percentile of accuracy across clients versus communication rounds (training progress). The results are shown in Figure 10.
EVNNST-10
EMNST-62
CIFAR-100
Shaksspaare
Stackovartiow
25th parcanale
$330
0.20
round
found
round
round
partcpating training
partic pating
Figure 10: Accuracies the client at the t5th percentile versus the communication rounds.
17

---

Published as a conference paper at ICLR 2022
C ADDITIONAL DETAILS ON EXPERIMENTAL SETUP AND TASK- EXPERIMENTS
In this section provide details of the experimental setup, including dataset preparation/ppepro- cessing, model choice and hyperparameter tuning. We also include task-specific experiments with ablations.
For every setting, unless otherwise stated, we tune the learning rate(s) to achieve the best sum of participating validation accuracy and unparticipating accuracy (so that the result will not be biased towards one of the accuracies).
C.I EMNIST HAND-WRITTER CHARACTER RECOGNITION TASK
Federated Dataset Description and Proprocessing, The EMNIST dataset (Cohen et al., 2017) is hand-written character recognition dataset derived from the NIST Special Database 19 (Grother & Flanagan, 1995). We used the Federated version of EMNIST (Caldas et al., 2019) dataset, which is partitioned based on the writer identification. We consider both the full version (62 classes) as well as the numbers-only version (10 classes). We adopt the federated EMNIST hosted by Tensorflow Federated (TFF). In TFF, federated EMNIST has default intra-client split, namely all the clients appeared in both the "training" and "validation" dataset. To construct three-way split, we hold out 20% of the total clients as unparticipating clients. Within each participating client, we keep the original training/validatioon split, i.e., the original training data that are assigned to participating clients will become participating training data. We tested the performance under various number of participating clients, as shown in Figure 7. The results reported in Table 1 for the case with 272 participating clients.
Model, Optimizer, and Hyperparameters. We train shallow convolutional neural network with approximately one million trainable parameters as in (Reddi et al., 2021). For centralized training, we run 200 epochs of SGD with momentum = 0.9 with constant learning rate with batch size 50. The (centralized) learning rate is tuned from {10-2.5, 1002...... ..... 10 0.5 J. For federated training, we run 3000 rounds of FEDAVGM (Reddi al., 2021) with server momentum 0.9 and constant server and client learning rates. For each communication round, we uniformly sample 20 clients to train for epoch with client batch size 20. The client and server learning rates are both tuned from
{10-2, 10 1).
C.1.1 CONSISTENCY ACROSS VARIOUS HYPERPARAMETERS CHOICES
In Table 1, only presented the best hyperparameter choice (learning rate combinations). In this subsubsection, we show that the pattern of generalization gap is consistent across various hyperparameter choices. The result is shown in Figure 11.
0g~10R0 10-10-18
fg-10-22 Q-10-25
(--10 10-10-11
1--10-13 a-100
accuracy
0.99
0.98
1000
1000
3000
2000
3000
2000
3000
round
round
raund
round
participating training
participating validation
unparticipating
Figure 11: Consistency of participation gaps across hyperparameter choice (learning rates configuration). We present the best four (4) combination of learning rates for federated training of EMNIST-10. Here Ne stands for client learning rate, and 7), stands for server learning rate. We observe that the participation gap is consistent across various configurations of learning rates.
18

---

Published as a conference paper at ICLR 2022
C.1.2 EFFECT OF MULTIPLE LOCAL EPOCHS PER COMMUNICATION ROUND
In the main experiments we by default let each sampled client run one local epoch every communica- tion round. In this subsubsection, we evaluate the effect of multiple local epochs the generalization performance. The result is shown in Figure 12.
epochs per round =1
opachs per round 2
ope per round
epochs per round 10
0.925
0.900
accuracy
0.875
0.850
0.825
0.800
1000
2000
3000
1000
2000
3000
1000
2000
3000
1000
2000
3000
round
round
raund
round
participating training
participating validation
unparticipating
Figure 12: Effect of multiple client epochs per round on EMNIST-62. We repeat the experiment on EMNIST-62 but instead let each sampled client multiple local epochs per communication round. The other settings (including the total communication rounds) remain the same. We observe that the participation gap is consistent across various settings of local epochs.
C.2 CIFAR 10/ 100 IMAGE CLASSIFICATION TASK
Federated Dataset Preprocessing. The CIFAR-10 and CIFAR-100 datasets (Krizhevsky et al., 2009) are datasets of natural images distributed into 10 and 100 classes respectively. Since the dataset does not come with user assignment, we first shuffle the original dataset and assign to clients by applying our proposed semantic synthesized partitioning. The CIFAR-10 and CIFAR-100 dataset are partitioned into 300 and 100 clients, respectively. For three-way split, we hold out 20% (60 for CIFAR- 10, 20 for CIFAR-100) clients unparticipating clients, and leave the remaining client as participating clients. Within each participating client, we hold out 20% of data as (participating) validation data.
Model, Optimizer, and Hyperparameters We train a ResNet-18 (He et al., 2016) in which the batch normalization is replaced by group normalization (Wu & He. 2018) for improved stability in federated setting, as recommended by Hsich et al. (2019). For centralized training, we run 200 epochs of SGD with momentum 0.9 with batch size 50, and decay the learning rate by 5x every 60 epochs. The initial learning rate is tuned from {10-2 22. 10-2 ..... 10 (0-0.)). For federated training, we run 2,000 rounds of FEDAVGM (Reddi et al., 2021) with server momentum 0.9, and decay the server learning rate by 5x every 600 communication rounds. For each communication round, we uniformly sample 10 clients (for CIFAR-100 100) or 30 clients (for CIFAR-I0), and each client train for local epoch with batch size 20. The client learning rate is tuned from {10 -2 10-1..5 ..... 1); the server learning rate tuned from {10 1.5, 10 ,..., 100.5).
C.2.1 CONSISTENCY ACROSS VARIOUS HYPERPARAMETERS CHOICE
In the main result Table I we only present the best hyperparameter choice (learning rate combina- tions). In this subsubsection, we show that the pattern of generalization gap is consistent across hyperparameter choice. The result is shown in Figures 13 and 14.
C.2.2 EFFECT OF WEIGHT DECAY STRENGTH
In the main experiments by default set the weight decay of ResNet-18 to be 10-4, In this subsubsection, we experiment various other options of weight decay from 10-5 to 10-2
The result is shown in Figure 15.
19

---

Published as a conference paper at ICLR 2022
0==100:
n==10-14
n==10Ps n==10-15
0==10P 1==10-14
n==10R5
accuracy
0.8
0.7
500
1000 round
1500
500 1000 1500
500 1000 round
1500
500 1000 1500
round
round
participating training
participating validation
unparticipating
Figure 13: Consistency participation gaps across hyperparameter choice (learning rates configuration). We present the best four (4) combination of learning rates for federated training of CIFAR-1O. Here lee stands for client learning rate, and T7e stands for server learning rate. We observe that the participation gap is largely consistent across various configurations of learning rates.
0,=10"3 ng-10-13
1==10p 1=110-10
0=110e n=-10--a
1w=10P3 n==10-2e
accuracy
round
round
round
round
participating training
participating validation
unparticipating
Figure 14: Consistency of participation gaps across hyperparameter choice (learning rates configuration). We present the best four (4) combination of learning rates for federated training of CIFAR-100. Here ne stands for client learning rate, and 1/s stands for server learning rate. We observe that the participation gap is consistent across various configurations of learning rates.
0.58
Figure 15: Effect of l weight decay on CIFAR-100 training. We federated train the ResNet-18 18 networks for CIFAR- 100 with vari- ous levels of weight decay ranging from 10-5 to 10-2 We observe that moderate scale of weight decay might improve the unparticipat- ing accuracy and therefore decrease the par- ticipation gap. However, an overlarge weight decay might hurt both participating validation and unparticipating performance.
0.57
accuracy
0.56
0.55
0.53
participating validation unparticipating
0.52
10
10
10-3
10
weight decay
20

---

Published as a conference paper at ICLR 2022
C.2.3 EFFECT OF MODEL DEPTH
In the main experiments we by default train a ResNet-18 for the CIFAR task. In this subsubsection, we experiment a deeper model (ResNet-50) for the CIFAR-I00. The result is shown in Figure 16.
Figure 16: Effect of a deeper ResNet on CIFAR-100 training. We federatedly train ResNet-50 for CIFAR-100 to compare with our default choice (ResNet-18). We apply constant learning rate (instead of step decay learning rate) for easy comparison. We observe that while using deeper model improves the overall accuracy, the participation gap is still reasonably large for ResNet-50.
CIFAR-100 Reshet-18
CIFAR-100 ResNie-00
6.823
0.375
0.332
0.325
6.455
6.153
0.42
2000
2500
paricipainng valning
paricpetinn valization
upparidpaating
C.3 SHAKEESPERE NEXT CHARACTER PREDICTION TASK
Federated Dataset Description and Preprocessing. The Shakespeare dataset (Caldas et al., 2019) is a next character prediction dataset containing lines from the Complete Works of William Shakespeare where each client is different character from one of the plays. We adopt the federated shakespeare dataset hosted by Tensorflow Federated (TFF). In TFF, the federated shakespeare dataset was by default split intra-cliently, namely all the clients appeared in both the "training" and "validation" dataset. To construct a three-way split, we hold out 20% of the total clients as unparticipating clients, and leave the remaining (80%) clients participating clients (which gives the result reported in Table 1). Within each participating client, we keep the original aaining/validatin original training data that are assigned these participating clients will become participating training data. We also tested the performance under other numbers of participating clients, as shown in Figure 7.
split, e.g., the
Model, Optimizer, and Hyperparameters We train the same recurrent neural network as in (Reddi et al., 2021). For centralized training, we run 30 epochs of Adam (with c = 10-4) with batch size 20. We tune the centralized learning rate from {10-3 2,10-2., ..... 10 }. For federated training, we run 3,000 rounds FEDADAM (Reddi et al., 2021) with server e = 10-4, For each communictaion round, we uniformly sample 10 clients, and let each client train for 1 local epoch with batch size 10. Both client and server learning rates are tuned from {10-2, 1.. ,...,.]. "............
C.4 STACKOVERFLOW NEXT WORD PREDICTION TASK
Federated Dataset Description and Preprocessing. The Stack Overflow dataset consists of ques- tions and answers taken from the website Stack Overflow. Each client is a different user of the website. We adopt the stackoverflow dataset hosted by Tensorflow Federated (TFF). In TFF, the federated stackoverflow dataset is splitted inter-cliently, namely the training data and validation data belong two disjoint subsets of clients. To construct a three-way split, we will treat the original "validation" clients as unparticipating clients. Within each participating client, we randomly hold out the max of 20% or 1000 elements (participating) validation data, and the max of 80% 1000 elements as (participating) training data. Due to the abundance of stackoverflow data, we randomly sample subset of clients from the original "training" clients as participating clients. The result shown in Table is for the case with 3425 participating clients. We also tested other various levels of participating clients, shown in Figure 7.
Model, Optimizer, and Hyperparameters We train the same recurent neural network as in (Reddi et al., 2021). For centralized training, we run 30 epochs of Adam (with = 10 4) with batch size 200. We tune the centralized learning rate from 110-3, 10.5. ..... 10 1.5 J. For federated training, we run 6,000 rounds of FEDADAM (Reddi et al., 2021) with server e = 10 For each communictaion
round, randomly sample 100 clients, and let each client train for I local epoch with batch size 50.
Both client and server learning rates are tuned from {10-2 10,10-1. 1.5 ..... 1). The client learning rate is
tuned from (10-3, 10-1. ...., 10-1): the server learning rate is tuned from (10-2, 10-1.5 ..... 1).
21

---

Published as a conference paper at ICLR 2022
D DETAILS OF SEMANTICICALLY PARTITIONED FEDERATED DATASET
D.I DETAILS OF THE SEMANTIC PARTITIONING SCHEME
In this section provide the details of the proposed algorithm semantically partition a federated dataset for CIFAR-10 and CIFAR-100 For clarify, we use to denote the number of classes, and C denote the number of clients partitioned into.
The first stage aims to cluster each label into C' clusters.
1. Embed the original inputs of dataset using pretrained EfficientNetB3. This gives embedding of dimension 1280 for each input.
2. Reduce the dimension of the above embeddings to 256 dimensions via PCA.?
For each label, fit the corresponding input with a Gaussian mixture model with C' clusters. This step yiclds C' gaussian distribution for each of the K labels. Formally, we let D denote the (Gaussian) distribution of the cluster c of label k.
The second stage will package the clusters from different labels across clients. We aim to compute an optimal multi-partit matching with cost-matrix defined by KL-divergence between the Gaussian clusters. To reduce complexity, we heuristically solve the optimal multi-partite matching by pro- gressively solving the optimal bipartite matching at each time for some randomly-chosen label pairs. Formally, run the following procedure
Initialize Suumstched <- {1...., K}
2: Randomly sample a label l from S Sunmatched, and remove is from Summatched-
3: while Sunmatched * do
4: Randomly sample a label k' from Sunmatcheds and remove k' from Summatched-
5: Compute cost matrix A of dimension C' x C, where Aij f- DRL (D/ [[ ).
6: Solve and record the optimal bipartite matching with cost matrix A.
7: Set k <- k'
8: return the aggregation of all the bipartite matchings computed.
D.2 VISUALIZATION SEMANTICICALLY PARTITIONED CIFAR- DATASET
clent
clint
28
23
15
11
22
15
25
23
Figure 17: Visualization of semantic partitioning of CIFAR-100. We partition the CIFAR-100
dataset into 100 clients without resorting to external user information (such as writer identification). Here we show 10 out of 100 clients featuring the label "apple".
D.3 VISUALIZATION SEMANTICALLY PARTITIONED MNIST DATASET
"Reducing the dimension purely a computational issue since original embedding dimension (1280) too large for downstream procedures such as GMM fitting and optimal matching (measured by KL divergence). While there may be other complicated dimension reduction technique. we found PCA to be simple enough to generate reasonable results. The dimension of 256 is trade-off of (down-stream) computational complexity and emhedding information.
22

---

Published as a conference paper at ICLR 2022
0
2
D
D
D
D
0
0
O
0
(
V
1
I
7
2
2
2
2
2
2
3
2
2
2
2
3
3
3
3
3
3
3
3
3
7
3
8
3
8
7
4
4
4
+
//
/
5
5
5
5
5
5
5
7
6
6
6
6
+
6
6
7
7
7
0
7
7
7
7
8
8
7
8
Y
9
9
9
Figure 18: Visualization of semantic partitioning of MNIST. We partition the (classic) MNIST dataset into 300 clients without resorting to external user information (such as writer identification). Here we show out of 300 clients. Observe that the images within each client demonstrates consistent writing styles both within label and across labels.
23

---

Published as a conference paper at ICLR 2022
E METHODOLOGY FOR COMPUTING ENTROPY
We hypothesize that a participation gap exists for naturally partitioned datasets and not for synthet- ically partitioned datasets because the naturally partitioned datasets inherently contain correlated inputs not drawn IID from the full data generating distribution. Put another way, the entropy of the input data for a given label from a naturally partitioned client lower than the entropy for that same label from a synthetically partitioned client. To evaluate this claim, we need to (approximately) infer the data generating distribution for each client, and then measure the entropy of this distribution, defined as:
( = -R log ((x))
To infer the client data generating distribution, we used deep generative models. Because our clients possess relatively few training examples (10) for particular class), many deep generative models such as Glow (Kingma Dhariwal, 2018) or PixelCNN (Salimans al., 2017) will not be able to learn reasonable density model. We instead used Variational Autoencoder (Kingma & Welling, 2013) to approximate the deep generative process. This model is significantly easier to train compared to the much larger generative models, but does not have tractable log-evidence measurement. Instead, models are trained by minimizing the negative Evidence Lower Bound (ELBO).
We filtered each client to contain data only for single label. Because of the sparseness of the data after filtering, we found that 2 dimensional latent space was sufficient to compress our data without significant losses. We used Multivariate Normal distribution for our posterior and prior, and an Independent Bernoulli distribution for our likelihood. The posterior was given a full covariance matrix to account for correlations in the latent variable. All models were trained for 10 training steps.
In order evaluate our models, used stochastic approximation to the log-evidence, given by 1000 sample IWAE (Burda et al., 2015). IWAE is a lower bound on the Bayesian Evidence that becomes asymptotically tight when computed with a large number of samples. We evaluated the entropy for 100 clients from naturally partitioned, syntactically partitioned, and synthetically partitioned datasets, and computed the average across clients our estimate for the client data entropy. We find that synthetic partitioning results in an average client entropy of 50 Nats, while Natural partitioning results in clients with only 40 Nats of entropy. Syntactic partitioning falls in between these two, having 45 Nats of entropy.
24


Reviews:
[{"review_id": "xyABX5fy5v", "reviewer": "Reviewer_bfMQ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper points out an often overlooked issue in federated learning: when clients are sampled for averaging, some clients may hold deprecated models. Those clients will have a worse performance than their recently averaged fellows. The paper shows that for homogeneous local data distributions, this error vanishes in expectation, but remains an issue for heterogeneous distributions. These insights are valuable.\n\nThe main contributions of the paper, however, are fairly straight-forward and the theoretical result (Prop. 3.1) is trivial. The proposed three-way-split is a straight-forward estimator that gives little novel insights. The semantic partitioning of data into heterogeneous local datasets is interesting, but the advantage of the method over other strategies (simple distance based clustering, or using semantically similar datasets (e.g., MNIST, MNIST-M, SVHN, USPS, and SynthDigits)) remains unclear. The empirical evaluation is sound and confirms the effect of participating clients on the overall performance, but yield little novel insights.\n\nRegarding the community suggestions, I feel that (at least in my bubble) these suggestions are not novel. Using naturally partitioned datasets is fairly common in personalized FL or FL from heterogeneous data sources (e.g., in FedBN [1]). The semantic partitioning might be an interesting new technique, but from this paper its benefits remain unclear. Suggesting to report the distribution of metrics seems particularly odd, since this is common practice in most ML papers (at least, reporting standard deviation or variance). In FL, the variance of local client performances is also often reported, or visually illustrated. Only the first suggestion - to analyze the participation gap - seems appropriate, but is limited to approaches where clients are sampled and - as the experiments suggest - the sampling probability for individual clients is sufficiently low.\n\nGiven this lack of novelty, I do not think this paper is ready for publication.\n\nDetailed comments:\n- Why is it sound to equate the expected risk over all clients with the expected risk over unparticipating clients? Doesn't that convolute the issues? It seems to me that there are two issues: the difference in risk between participating and unparticipating clients and the difference in risk between participating clients and all clients.\n- Regarding generalization, there is work on quantifying the generalization gap in federated learning from heterogeneous datasets (cf. [2]) \n- Sec. 4.1.: How can you ensure that the pre-trained neural network captures semantically relevant features? How does the embedding vary with different networks? \n- Sec. 4.1./App. D: Why does the dimension have to be further reduced, why is PCA the right method, why should it be reduced to exactly 256 dimensions, and why is it not better to train some neural network with a 256-dimensional representation right away? \n- Sec. 4.1.: Why are mixtures created per label? How would the splits look if the mixtures where created independent of the label?\n\n[1] Li, Xiaoxiao, et al. \"FedBN: Federated Learning on Non-IID Features via Local Batch Normalization.\" International Conference on Learning Representations. 2021.\n[2] Huang, Baihe, et al. \"Fl-ntk: A neural tangent kernel-based framework for federated learning analysis.\" International Conference on Machine Learning. PMLR, 2021.\n\n************* after rebuttal ******************\n\nGiven that I misunderstood a key concept in my original review and that we had an interesting discussion in this rebuttal period, I feel compelled to write a second review. \n\nSummary Of The Paper:\nIn many federated learning applications, not all clients participate in the averaging process, but are, e.g., randomly sampled from the potentially infinite set of available clients, each endowed with its own local data distribution. This paper studies the decomposition of the generalization gap into the out-of-sample gap, i.e., the generalization ability of participating clients to unseen data drawn from their local distribution, and the participation gap, i.e., the difference between the generalization ability on unseen data drawn from the local distributions of participating clients to data drawn from all possible local distributions. The paper proposes a three-way-split of clients and local datasets to estimate these two quantities separately. \n\nMain Review:\nIn many federated learning applications, local data distributions are not homogeneous. This fact has been studied extensively and methods have been proposed to address the difficulties in training on such heterogeneous distributions. In case the set of clients is large (or potentially infinite) and each client has a (potentially) different local data distribution, then at any given time, only a subset of those clients will have participated in federated learning. Current estimations of a federated learning system's generalization performance only assess it on data similar to the data seen by those participating clients. This overlooks the error on data drawn from a distribution from a client that not yet participated. While this error in general cannot be measured, it can be approximated if clients are drawn iid by holding out a subset of clients as \"validation clients\" to assess this participation gap. Naturally, this allows to also assess the level of heterogeneity in the local data distributions.\n\nThe main contribution of this paper hinges on the assumption of a potentially infinite number of clients, each endowed with its own, distinct local data distribution. Given this assumption, the proposed three-way-split is a straight-forward and sound (and fairly practical) method to assess the participation gap. This can indeed provide valuable insights about the performance and nature of the overall federated learning system.\n\nSince standard benchmark datasets for non-iid distributions provide only a very limited number of different data distributions (e.g., the quintuple MNIST, MNIST-M, SVHN, USPS, and SynthDigits), the paper proposes a semantic partitioning of data. This allows one to simulate the setting of a very large set of clients each with a different local data distribution. \n\nMy main concern with the paper is that this contribution is not presented clearly enough and that its main assumption and limitations are not discussed in detail. Thanks to the great discussion with the authors, I am now convinced that the decomposition of the generalization gap into out-of-sample and participation gap has merits in the setting considered. It has also become clear that this is not so meaningful in case of a limited number of potential clients or a (small) finite number of potential distributions. Thus, in its current form the paper falls behind its potential. \n\nI suggest the following improvements:\n(i) Clearly point out the setting considered and its limitations. This includes separating it from cross-silo scenarios (where the number of potential clients is usually small) or many internet of things scenarios (where the number of potential types of devices is limited and devices of the same type share the same data distribution). I guess, the typical scenario is learning on mobile devices where the number of potential clients is indeed huge and local distributions are typically heterogeneous. Still, it would be great to discuss this assumption in a bit more detail: results from humanities (sociology and psychology) suggest that human behavior clusters around a fairly limited amount of archetypes, so it stands to reason that distributions obtained from human interaction with a device might also cluster around such archetypes. In the discussion with the authors, we established that in this case, the behavior or a federated learning system could quickly converge towards one with only a limited number of potential local data distributions. \nWhile these discussions seem to limit the applicability of the paper, I think they greatly improve its significance, since it gives rise to interesting questions for future studies. \n(ii) The empirical evaluation shows that the participation gap can be observed in practice. Here, the results on the naturally partitioned data are the most significant and should be pointed out more. \n(iii) Since the results are not applicable to all federated learning settings, I suggest incorporating the community suggestions into a discussion section, such that these suggestions are properly contextualized within the assumptions and limitations of the approach.\n\n\nThese issues require some extensive changes to the manuscript that usually go beyond what is considered minor revisions. However, given that the discussion contained most of these points already, I am willing to trust that the authors can make it. The theoretical contributions remain straight-forward and the three-way-split is fairly natural. Thus, I am on the fence about this paper. Since the paper addresses a novel issue, I slightly tend towards acceptance. I have changed my score accordingly.\n", "summary_of_the_paper": "In many federated learning applications, not all clients participate in the averaging process, but are, e.g., randomly sampled from the set of available clients. This paper proposes to study not only the generalization gap in federated learning, i.e., the difference between risk and empirical risk, but also the difference between the risk of clients that participate and those that do not participate in the current averaging round, which is called participation gap in this paper. The paper formally equates the risk of unparticipating clients with the expected risk over all clients, where the expectation is over the sampling probability of each client. The paper then proposes a set of data splits to estimate those gaps with a focus on heterogeneous local data distributions. ", "summary_of_the_review": "The issue of the different performance of participating and non-participating clients in federated learning - in particular for heterogeneous datasets - is interesting. The proposed contributions of this paper are a straight-forward data split strategy, a proposed strategy to split data into heterogeneous local datasets, and an empirical evaluation of the performance of participating and non-participating clients that confirms the intuitive expectations on the effect of participating clients. While the issue the paper addresses is interesting, the proposed contributions are fairly straight-forward and provide little novel insights. Thus, I vote for rejection. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "ufo6VFdaksX", "reviewer": "Reviewer_dKHn", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Decomposing the performance gap into out-of-sample gap and participation gap is not new. The very simple way is to split the whole dataset into training and validation sets, and the training data is distributed across workers, then training data on each worker is further split into local training and local validation data. In this way, the local validation loss could be viewed as the out-of-sample gap and the global validation loss can be viewed as the participation gap. Evaluating the loss on local data can be found in [1,2].\n\nAnother question is if some clients never participate in training, how can we evaluate the participation gap since the loss should be calculated on these data?\n\nThe experimental results are trivial from the view of the commonly-used data splitting described in the first paragraph. Could the authors please elaborate on the novelty of this paper? How can we deal with the performance gap due to data heterogeneity?\n\n\n[1] Liang, Paul Pu, et al. \"Think locally, act globally: Federated learning with local and global representations.\" arXiv preprint arXiv:2001.01523 (2020).\n[2] Hao, Weituo, et al. \"WAFFLe: Weight Anonymized Factorization for Federated Learning.\" arXiv preprint arXiv:2008.05687 (2020).\n\n-------------------\nAfter reading all the reviews and the rebuttal, some of my concerns have been addressed, I am willing to increase the grade.", "summary_of_the_paper": "The paper proposes a framework for disentangling the performance gap in federated learning into out-of-sample gap and participation gap, which should serve as a better tool for explaining the model generalization performance. They also give a semantic synthesis strategy that enables realistic simulation to create more natural federated data splitting. More analysis on the relationship between gaps and data heterogeneity is provided to support the validity of the proposed splitting framework.", "summary_of_the_review": "I feel the idea and the experimental results are trivial if we view it from a commonly-used federated data splitting perspective. If the authors can propose some remedy to this participation gap, this will be an interesting piece of paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "nbXXfEpuDoy", "reviewer": "Reviewer_TBV6", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nStrengths\n\n-The paper analyzes performance measurements in the popular federated learning paradigm. The proposal is sensible and addresses an important problem. \n-The experiments are thorough and use best practice\n-The authors discuss releasing a code base for running their experiments\n\nWeakness/Comments\n\n-The experiments are done using FedAVGM. First of all this is not even mentionedi n the main paper. I think it would be interesting for the proposed study to revisits how different methods perform under the evaluation protocol and also use SOTA methods (e.g. FedYogi), perhaps conclusions might be different about which method is best. \n-In some federated settings the distribution shift is in the labels, how do the authors consider this case in ther analysis of non participating clients. For example a natural non-participating client might have a label unseen in other clients, yet the model is relevant,\n-(Minor) Figure 2 makes it hard to notice the per column similarity in the digits (and thus the distribution shift). I would suggest to instead do something more obvious (different color digit or using a different digit in each row altogether)\n", "summary_of_the_paper": "The authors propose a different view of performance in federated learning, by measuring separately the performance out of sample  and the performance on novel (but related distributions) from a “non-participating” client. They propose one approach of structuring experiments that allows these kins of measurements using a three way split. They then study how the dataset, client number and diversity affects the perforamnce.\n", "summary_of_the_review": "\nOverall the paper addresses important topic and has conclusions that could benefit the community. The experiments seem too be well done and rigorous. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "H-Bburze0s1", "reviewer": "Reviewer_b9Rh", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "- **Pros**\n    - The paper is well written and easy to understand for most parts.\n    - To the best of my knowledge, existing works do not take into account the participation gap in their analysis or in their datasets split, therefore this work can be an important contribution to the FL community.\n    - the authors provide all the necessary information about the results of the experiments, the hyperparameters tuning and the specifications to reproduce them, making this work a reference benchmark for future extensions.\n    - the proposed framework is scalable and easily adaptable to the existing state-of-the-art strategies and methods.\n    - assumptions and hypotheses are verified either theoretically or empirically.\n    - release of an open-source framework for semantic-based dataset partitioning and participation gaps measurement.\n- **Cons**\n    - In Sec. 3, the authors propose the initial analysis on EMNIST-62 and then continue on CIFAR datasets, without explaining what happens to the previous setting (label-based or natural partitioning) when their contribution is introduced (semantic-based partitioning).\n- **Questions**\n    1. On results consistency to model size and hyperparams:\n        - 1a) By looking at supp C1.1 and the consistency of results for different LR choices, I was wondering if the participation gaps are sensitive to the choice of the server optimizer.\n        - 1b) Actually, more in general I think that the analysis would be much more complete if you included experiments with recent methods that have been developed to reduce heterogeneity issue in federate learning. eg. MIME, FedDyn, Scaffold, FedProx, FedBN,  etc.. It would be great to see if the participation gap is sensitive to the algorithm or optimization method. \n        - 1c) Is the partecipation gap sensitive to the choice of the number of clients sampled at each communication round?\n        - \"1d) \"the participation gap is still reasonably large for ResNet-50.\" Results in C2.3 figure 16 for resnet50 are not at final convergence. Is this claim valid at the end of training? Also, I imagine that these gaps should be independent on the choice of the architecture e.g efficientNet or others. Have you verified that?\n        - 1e) very deep learner question: I'm curious to see how these gaps behave on large scale datasets as Inaturalist or Google Landmarks, but this is out of the scope of the paper.\n    2. it would be interesting to see how the experiments in Fig 4 change when EMNIST is created with the semantic partitioning\n    3. In the label-partitioned CIFAR, which is the chosen alpha for the Dirichlet’s distribution?\n    4. Table 1: looking at the plots in Appendix B.1, the part_train accuracy on Shakespeare looks close to 0.62, where does the 60.7 in the table come from?\n    5. How are the datasets balanced between clients (i.e. mean and stdev of data distributions among clients)?\n    6. In Appendix C, you provide detailed information on the experimental setup. The best learning rates chosen for the experiments in Table 1 are not clear.\n- **Minors**\n    - Section 5.1, third row: typo “participating” is misspelled\n", "summary_of_the_paper": "- The authors propose a study on generalization in Federated Learning (FL). They focus on the cross-device setting, where the clients are sampled from a large population and are characterized by unreliable availability, which implies that many clients may actually never take part in the training process. Driven by such realistic assumptions, they distinguish between participating and non-participating clients and identify two generalization gaps: \n    - the __out-of-sample__ __gap__, i.e. the difference between the empirical and expected risk for participating clients, or the gap in performance of the model when tested on previously unseen data; \n    - the __participation gap__, i.e. the difference in expected risk between the participating and non-participating clients, or the model drop in performance when faced with unseen distributions (i.e. new clients).  This is a direct consequence of the heterogeneity in FL: in heterogeneous settings, clients have access to different data distributions, leading the model to worse performance when new distributions are introduced. So the gap becomes a natural measurement for dataset heterogeneity, capability of the model to generalize and client diversity.\n- The authors propose a three-way split for federated datasets in order to  perform an estimation of the risks and gaps: by identifying participating and non-participating clients first, and then training and validate data within the participating clients’ local data distribution.\n- Finally, they also point out how federated datasets are usually split based on the labels distribution (each client is assigned a distribution on the labels), or on some natural information, e.g. the writer of a character, and show that this __label-based partitioning__ may not fully represent realistic client heterogeneity. \n    - Therefore, they propose a semantics-based framework for partitioning the dataset, which behaves similarly to the natural and more realistic method, without requiring naturally-partitioned data.\n- Their extensive analysis is tested on six different tasks and all information for experiments reproducibility are provided. Studies on the hyperparameters tuning are proposed as well.\n", "summary_of_the_review": "A very nice paper. It proposes to measure both out-of-sample generalization and participation gaps and give several recommendations for training federated learning models following a new protocol. It also proposes a new way to create synthetic federated datasets that reflect heterogeneity in a more natural way than label-based split.  The experimental analysis is very concrete and the results look solid. I recommend acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents some insightful suggestions for researchers studying generalization in federated learning by separating two types of performance gaps between training and test performance, the participation gap (due to partial client participation) and the performance gap (due to data heterogeneity). They suggest that federated learning researchers use a three-way split between participating clients' training data, participants clients' validation data, and non-participating clients' data to measure the generalization performance of an FL model. The paper presents thorough experiments to support their conclusions. A common concern about the paper is that the authors' suggestions, although relevant and reasonable, are somewhat unsurprising and have been noted in different forms in other works in federated learning. Another concern is that the conclusions are purely based on experiments and are not supported by theoretical justification. Despite these concerns, the reviewers commended the overall insights presented in the paper. 

There was a healthy post-rebuttal discussion and some reviewers reevaluated the paper and raised their initial scores. Therefore, I recommend acceptance of the paper. I encourage the authors to take the reviewer's constructive suggestions into account when preparing the final version of the paper.
Decision: Accept (Poster)