Federated Learning from Small Datasets
Authors: Michael Kamp
Jonas Fischer
Jilles Vreeken
Venue: ICLR 2023 poster (2023)
Keywords: federated learning
distributed
sparse data
daisy chain
small datasets

Abstract: Federated learning allows multiple parties to collaboratively train a joint model without having to share any local data. It enables applications of machine learning in settings where data is inherently distributed and undisclosable, such as in the medical domain. Joint training is usually achieved by aggregating local models. When local datasets are small, locally trained models can vary greatly from a globally good model. Bad local models can arbitrarily deteriorate the aggregate model quality, causing federating learning to fail in these settings. We propose a novel approach that avoids this problem by interleaving model aggregation and permutation steps. During a permutation step we redistribute local models across clients through the server, while preserving data privacy, to allow each local model to train on a daisy chain of local datasets. This enables successful training in data-sparse domains. Combined with model aggregation, this approach enables effective learning even if the local datasets are extremely small, while retaining the privacy benefits of federated learning.

Published as a conference paper at ICLR 2023
FEDERATED LEARNING FROM SMALL DATASETS
Michael Kamp
Jonas Fischer Harvard T.H. Chan School of Public Health
Institute for Al in medicine (IKIM)
University Hospital Essen, Essen Germany, and Ruhr-University Bochum, Bochum Germany, and Monash University, Melbourne, Australia de
Department of Biostatistics
Boston, MA, United States jficher@hsph harvard edu
michael. kamp@kk-pekeeeee
Jilles Vreeken
CISPA Helmholtz Center for Information Security Saarbrücken, Germany vreeken@cispa.de
ABSTRACT
Federated learning allows multiple parties to collaboratively train a joint model without having to share any local data. It enables applications of machine learning in settings where data is inherently distributed and undisclosable, such as in the medical domain. Joint training is usually achieved by aggregating local models. When local datasets are small, locally trained models can vary greatly from a globally good model. Bad local models can arbitrarily deteriorate the aggregate model quality, causing federating learning to fail in these settings. We propose a novel approach that avoids this problem by interleaving model aggregation and permutation steps. During permutation step we redistribute local models across clients through the server, while preserving data privacy, to allow each local model to train on a daisy chain of local datasets. This enables successful training data-sparse domains. Combined with model aggregation, this approach enables effective learning even the local datasets are extremely small, while retaining the privacy benefits of federated learning.
INTRODUCTION
How can we learn high quality models when data inherently distributed across sites and cannot be shared or pooled? In federated learning, the solution is to iteratively train models locally each site and share these models with the server to be aggregated to a global model. As only models shared, data usually remains undisclosed. This process, however, requires sufficient data to be available at each site in order for the locally trained models to achieve a minimum quality- even a single bad model can render aggregation arbitrarily bad (Shamir and Srebro, 2014). In many relevant applications this requirement is not met: In healthcare settings we often have as little as a few dozens of samples (Granlund et al., 2020: Su et al., 2021; Painter et al., 2020). Also in domains where deep learning is generally regarded as highly successful, such as natural language processing and object detection, applications often suffer from lack of data (Liu al., 2020; Kang et al., 2019).
To tackle this problem, we propose new building block called laisi-chaining for federated learning in which models are trained on one local dataset after another, much like daisy chain. nutshell, at each client model is trained locally, sent to the server. and then inne-innted of aggregating local models- sent to a random other client as is (see Fig. 1). This way, each local model exposed to daisy chain of clients and their local datasets. This allows us to learn from small, distributed datasets simply by consecutively training the model with the data available at each site. Daisy-chaining alone, however, violates privacy, since a client can infer from a model upon the data of the client it received it from (Shokri et al., 2017). Moreover, performing daisy-chaining naively would lead to overfitting which can cause learning to diverge (Haddadpour and Mahdavi, 2019). In this paper, we propose to combine daisy chaining of local datasets with aggregation of models, both orchestrated by the server, and term this method federated daisy-chaining (FRDDC).

---

Published as a conference paper at ICLR 2023
Jederated averaging
local training
daisy chaining
Client
Server
Model
Communication
Figure 1: Federated learning settings. standard federated learning setting with training of local models at clients (middle) with aggregation phases where models are communicated to the server, aggregated, and sent back to each client (left). We propose to add daisy chaining (right), where local models are sent to the server and then redistributed to a random permutation of clients as is.
We show that our simple, yet effective approach maintains privacy of local datasets, while it prov- ably converges and guarantees improvement of model quality in convex problems with suitable aggregation method. Formally, we show convergence for FEDDC on non-convex problems. We then show for convex problems that FEDDC succeeds on small datasets where standard federated learning fails. For that, we analyze FEDDC combined with aggregation via the Radon point from PAC-learning perspective. We substantiate this theoretical analysis for convex problems by showing that FEDDC practice matches the accuracy of model trained on the full data of the SUSY binary classification dataset with only samples per client, outperforming standard federated learning by wide margin. For non-convex settings, we provide an extensive empirical evaluation, showing that FEDDC outperforms naive daisy- daisy-chaining, vanilla federated learning FEDAVG (McMahan et al., 2017), FEDPROX (Li et al., 2020a), FEDADAGRAD, FEDADAM, and FEDYOGI (Reddi et al., 2020) on low-sample CIFAR 10 (Krizhevsky, 2009), including non-iid settings, and, more importantly, on two real-world medical imaging datasets. Not only does FEDDC provide a wide margin of improve- ment over existing federated methods, but it comes close to the performance (centralized) neural network of the same architecture trained on the pooled data. To achieve that, it requires small communication overhead compared to standard federated learning for the additional daisy-chaining rounds. As often found in healthcare, we consider tross-SILO scenario where such small communication overhead is negligible. Moreover we show that with equal communication, standard federated averaging still underperforms in our considered settings.
gold-standard
In summary, our contributions are (i) FEDDC, a novel approach to federated learning from small datasets via a combination of model permutations across clients and aggregation, (ii) formal proof of convergence for FEDDC, (iii) a thcoretical guarantee that FEDDC improves models terms of d-guarantees which standard federated learning can not, (iv) discussion of the privacy aspects and mitigations suitable for FEDDC, including an empirical evaluation of differentially private FEDDC, and (v) an extensive set of experiments showing that FEDDC substantially improves model quality on small datasets compared to standard federated learning approaches.
RELATED WORK
Learning from small datasets is well studied problem in machine learning. In the literature, we find both general solutions, such using simpler models and transfer learning (Torrey and Shavlik, 2010), and more specialized ones, such as data augmentation (Ibrahim et al., 2021) and few-shot learning (Vinyals et al., 2016; Prabhu et al., 2019). In our scenario overall data is abundant, but the problem is that data is distributed into small local datasets at each site, which we are not allowed to pool. Hao et al. (2021) propose local data augmentation for federated learning, but their method requires sufficient quality of the local model for augmentation which is the opposite of the scenario we are considering. Huang et al. (2021) provide generalization bounds for federated averaging via the NTK frr-ferm.wokk, but requires one-layer infinite-width NNs and infinitesimal learning rates.
Federated learning and its variants have been shown to learn from incomplete local data sources, e.g., non-iid label distributions (Li et al.. 2020a; Wang et al., 2019) and differing feature distributions (Li et al., 2020b; Reisizadeh et al., 2020a), but fail in case of large gradient diversity (Haddadpour and Mahdavi, 2019) and strongly dissimilar label distribution (Marfoq et al., 2021). For small
2

---

Published as a conference paper at ICLR 2023
datasets, local empirical distributions may vary greatly from the global distribution: the difference of empirical to true distribution decreases exponentially with the sample size (e.g., according to the -ee---iffer-oofowwi inequality), but for small samples the difference can be substantial, in particular if the distribution differs from a Normal distribution (Kwak and Kim, 2017). Shamir and Srebro (2014) have shown the adverse effect of bad local models on averaging, proving that even due to single bad model averaging can be arbitrarily bad.
different approach to dealing with biased local data is by learning personalized models at each client. Such personalized FL (Li et al., 2021) can reduce sample complexity, e.g., by using shared representations (Collins et al.. 2021) for client-specific models, e.g., in the medical domain (Yang et al., 2021). or by training sample-efficien personalized Bayesian methods (Achituve et al., 2021). It not applicable, however, to settings where you are not allowed to learn the biases or batch effects of local clients, e.g., in many medical applications where this would expose sensitive client information. Kiss and Horvath (2021) propose a decentralized and communication-efin learning that migrates models over a decentralized network, storing incoming models locally at each client until sufficiently many models are collected on each client for an averaging step, similar to Gossip federated learing (Jelasity et al., 2005). The variant without averaging is similar simple daisy- chiinich which we compare to in Section 7. FEDDC is compatible with any aggregation operator, including the Radon machine (Kamp et al., 2017), the geometric median (Pillutla et al., 2022), or neuron-clustering (Yurochkin et al., 2019), and can be straightforwardly combined with approaches to improve communication-efficiin and model quantization (Reisizadeh et al., 2020b). We combine FEDDC with averaging, the Radon machine, and FedProx (Li et al., 2020a) in Sec. 7.
variant of federated
such as dynamic averaging (Kamp al., 2018),
PRELIMINARIES
We assume iterative learning algorithms (cf. Chp. 2.1.4 Kamp, 2019) A: X x x H - H that update a model h E H using a dataset D C X x y from an input space X' and output space y, i.c., h4+1 = A(D, ht). Given a set of m E N clients with local datasets D DI...., Dm C X x y drawn iid from a data distribution D and loss function L: y x y - R. the goal is to find a single model (E(h() v)]. In centralized learning, datasets are pooled as D Uie(m, D' and A is applied to D until convergence. Note that applying A on D can be the application to any random subset, e.g., as in mini-batch training, and convergence is measured in terms of low training loss, small gradient, or small deviation from previous iterate. In standard federated learning (McMahan al., 2017), A is applied in parallel for b E N rounds on each client locally to produce local models ht ...., ...,,," These models are then centralized and aggregated using an aggregation operator agg 7 + H. i.e., h = agg(h" ..... "...,..))) )) The aggregated model is then redistributed to local clients which perform another b rounds of training using h as starting point. This is iterated until convergence of h. When aggregating by averaging, this method is known as federated averaging (FEDAvG). Next, we describe FEDDC.
h" E H that minimizes the risk (h)
4 FEDERATED DAISY-CHAINIS
We propose federated daisy chaining as an extension to federated learning in setup with m clients and one designated sever! We provide the pseudocode of our approach as Algorithm
The client:
Each client trains its local model in each round on local data (line 4), and sends its model to the server every b rounds for aggregation, where & is the aggregation period, and every d rounds for daisy chaining, where d is the daisy-chaining period (line 6). This re-distribution of models results in each individual model conceptually following a daisy chain of clients, training on each local dataset. Such daisy chain is interrupted by each aggregation round.
The server: Upon receiving models, in a daisy- round (line 9) the server draws a random permutation of clients (line 10) and re-distributes the model of client to client x (i) (line 11), while in an aggregation round (line 12), the server instead aggregates all local models and re-distributes the aggregate to all clients (line 13-14).
'This star-topology can be extended to hierarchical networks in straightforward manner. Federated learning also be performed in decentralized network via gossip algorithms (Jelasity et al., 2005).
3

---

Published as a conference paper at ICLR 2023
Algorithm 1: Federated Daisy-Chaining FEDDC
Input:
daisy-chaining period d, aggregation period b, learning algorithm A, aggregation operator
agg, m clients with local datasets D ..... D", total number of rounds T Output: final model aggregate hTT initialize local models hi- ..... hg
2 Locally at client at time t do sample S from D
A(S, ((S,h)111 1)
if mod d = d 1 or mod b = b then
send ht to server receive new hę from server
// receives either aggregate he or some h!
At server at time t do if mod d = d 1 then draw permutation of [1.m] at random for all E [m] send model hū to client ri)) else if mod = b then ..... ......... ,,TT)
// daisy chaining
10
11
12
// aggregation
h4 agg [h,
send Tú, to clients
14
Communication complexity: Note that we consider cross-SILO settings, such as healthcare, were communication not a bottleneck and, hence, restrict ourselves to a brief discussion in the interest of space. Communication between clients and server happens in O 2 + { many rounds, where T the overall number of rounds. Since FEDDC communicates every dth and bth round, the amount of communication rounds is similar to FEDAVG with averaging period FedA
min d,, 6). That is, FEDDC increases communication over FEDAVG by constant factor depending on the setting of b and d. The amount of communication per communication round is linear in the number of clients and model size, similar to federated averaging. We investigate the performance of FEDAVG provided with the same communication capacity FEDDC in our experiments and in App. A.3.6.
THEORETICAL GUARANTEES
In this section, formally show that FEDDC converges for averaging. We, further, provide theoretical bounds on the model quality in convex settings, showing that FEDDC has favorable generalization error in low sample settings compared standard federated learning. More formally, we first show that under standard assumptions on the empirical risk, it follows from result of Yu al. (2019) that FEDDC converges when using averaging as aggregation and SGD for learning-a standard setting in, e.g., federated learning of neural networks. We provide all proofs in the appendix.
Corollary 1. Let the empirical risks (l) = E( ((,(()),) y) at each client i E [m] be L-smooth with 0² -b-bodded gradient variance and G2 -bounded second moments, then FEDDC with averaging and SGD has convergence rate of O(1/ /mI'), where T is the number of local updates.
Since model quality in terms of generalization error does not necessarily depend on convergence of training (Haddadpour and Mahdavi, 2019; Kamp et al., 2018), we additionally analyze model quality in terms of probabilistic worst-case guarantees on the generalization eтror SShalev-Shwards and Ben-David, 2014). The average of local models can yield as bad generalization error as the worst local model, hence, using averaging aggregation scheme in standard federated learning can yield arbitrarily bad results (cf. Shamir and Srebro, 2014). As the probability of bad local models starkly increases with smaller sample sizes, this trivial bound often carries over to considered practical settings. The Radon machine (Kamp et al., 2017) is a federated learning approach that overcomes these issues for wide range of learning algorithms and allows us analyze (non-trivial) quality bounds of aggregated models under the assumption of convexity. Next, we show that FEDDC improve model quality for small local datasets where standard federated learning fails to do
Radon point (Radon, 1921) of a set of points from a space is similar to the geometric median-2 a point in the convex hull of S with high centrality (i.e., Tukey depth (Tukey, 1975;
4

---

Published as a conference paper at ICLR 2023
0.9
0.9
0.9
centralized (test)
0.8
0.8
0.7
0.6
0.6
0.5
0.5
0.5
0.4
Irain
test
0.4
0.4
100
200
300
400
500
100
200
300 rounds
400
300
100
200
300
400
500
rounds
rounds
(a) FEDDC with Radon point with (b) Federated learning with Radon (c) Federated leamingg with Radon point with 50.
= 50.
point with
Figure 2: Results SUSY. We visualize results in terms of train (green) and test error (orange) for (a) FEDDC (d =d 1,b 50) and standard federated learning using Radon points for aggregation with (b) b= L, i... the same amount of communication as FEDDC, and (c) 50, i.c. the same aggregation period as FEDDC. The network has 441 clients with 2 data points per client. The performance of a central model trained on all data is indicated by the dashed line.
Gilad-Bachrace et al., 2004) of at least 2). For Radon point to exist, S C X has to have minimum size r E N called the Radon number of X' For S Id the radon number + 2. Here, the set of points S are the local models, or more precisely their parameter vectors. We make the following standard assumption (Von Luxburg and Schölkopf, 201 1) on the local learning algorithm A.
Assumption ((e, -ugarraane, The learning algorithm applied on dataset drawn iid from D of size 2 E N produces a model h E H. s.t. with probability E (0, 1] it holds for e >> 0 that (c(h) > c) < 5. The sample size na is monotonically decreasing in 8 and (note that typically no is polynomial in c and log )))
Here e(h) is the risk defined Sec. 3. Now let E N be the Radon number of H. A be a learning algorithm as in assumption and risk be convex. Assume 2 nd many clients with h E N. For > 0, E (0, 1J assume local datasets DI...., Dm of size larger than no(e, 8) drawn iid from D, and hi...... hm local models trained on them using A. Let ta be the iterated Radon point (Clarkson et al., 1996) with h iterations computed on the local models (for details, see App. A.2). Then it follows from Theorem 3 in Kamp et al. (2017) that for all i [m] holds that
(I) where the probability over the random draws of local datasets. That is, the probability that the smaller than the probability that local model is bad.
PP (E(TA)
> e) S (r (=(h)) > e))
aggregate is bad is Note that in PAC-learning, the eгror bound and the probability of the bound to hold are typically linked, so that improving one can be translated to improving the other (Von Luxburg and Schölkopf, 2011). Eq. implies that the iterated Radon point only improves the guarantee on the confidence
compared to that for local models if 5 <r-1, i.e. IP (e(tx) > e) s Pr (s(h)) > )))²² (rd)²" < only holds for rō < 1. Consequently, local models need to achieve minimum quality for the federated learning system improve model quality.
Let H. be model space with Radon number N, convex risk, and A a learning algorithm with sample size nole, 8). Given e >> O and any h E N, if local datasets Di...., Dm with n smaller than no(c, (-,r then federated learning using the Radon point does improve model quality in terms of (e, -guarantees.
Corollary 3.
In other words, when using aggregation by Radon points alone, an improvement in terms of (e, 6)- guarantees is strongly dependent on large enough local datasets. Furthermore, given d >>>>>>>>> -1, the guarantee can become arbitrarily bad by increasing the number of aggregation rounds.
Federated Daisy- Chaining given in Alg. 1 permutes local models at random, which is in theory cquivalent to permuting local datasets. Since the permutation is drawn at random, the amount of permutation rounds T necessary for each model to observe minimum number of distinct datasets with probability problem as T d (Hm H Hm-k), where Hm is the m-th harmonic number Lm. 5 in
can be given with high probability via a variation the coupon collector
5

---

Published as a conference paper at ICLR 2023
App. A.5 for details. It follows that when we perform chisy-chaining with m clients and local datasets of size for at least dmp-= (Hm Hn-k) rounds, then each local model will with probability least 1 - p be trained on at least kn distinct samples. For an c, 6-guarantee, we thus need to set b large enough so that kn 2 mn(e, vō) with probability at least - vō. This way, the failure probability is the product of not all clients observing k distinct datasets and the model having risk larger than e, which is v8v8- 6.
Proposition 4. Let H be model space with Radon number r E N, E a convex risk, and A learning algorithm with sample size no(e, 6). Given 6 > 0, ô E (0, 11) and any h N, and local datasets Di...., Dm of size E N with m 2 rh, then Alg. I using the Radon point with aggr. period
b b d m
Hmm Hm-[n 2no(cww3)))
6 2m
improves model quality terms of (c, 8) -ugarraateees.
This result implies that if enough daisy- chisn-chaining rounds are performed in-between aggregation rounds, federated learning via the iterated Radon point improves model quality in terms of (e, --guaranttess: the resulting model has generalization error smaller than with probability at least - 8. Note that the aggregation period cannot be arbitrarily increased without harming convergence. To illustrate the interplay between these variables, we provide numerical analysis of Prop. 4 in App. A.5.1.
This theoretical result also evident in practice, as we show in Fig. 2. There, we compare FEDDC with standard federated learning and equip both with the iterated Radon point on the SUSY binary classification dataset (Baldi et al., 2014). We train a linear model on 441 clients with only samples per client. After 500 rounds FEDDC daisy-chaining every round (d = 1) and aggregating every fifty rounds (6 = 50) reached the test accuracy of a gold-standard model that has been trained on the centralized dataset (ACC=0.77). Standard federated learning with the same communication complexity using b = 1 is outperformed by a large margin (ACC=0.68). We additionally provide results of standard federated learning with b = 50 (ACC=0.64), which shows that while the aggregated models perform reasonable, the standard approach heavily overfits on local datasets if not pulled to global average in every round. More details on this experiment can be found App. A.3.2. In Sec. 7 show that the empirical results for averaging aggregation operator similar to those for the Radon machine. First, we discuss the privacy-aspects of FEDDC.
DATA PRIVACY
major advantage of federated over centralized learn- ing is that local data remains undisclosed to anyone but the local client, only model parameters are exchanged. This provides natural benefit to data privacy, which the main concern applications such as healthcare. However, attacker can make inferences about lo- cal data from model parameters (Ma et al., 2020) and model updates gradients (Zhu and Han, 2020). In the daisy-chaining rounds of FEDDC clients receive a model that was directly trained on the local data of an- other client, instead of a model aggregate, potentially facilitating membership inference attacks (Shokri et al., (1l7))reconstructtoon attacks (Zhu and Han, 2020) remain difficult because model updates cannot be in- ferred since the server randomly permutes the order of clients in daisy-chaining rounds.
0.8
accurayy
0.6
0.4
FIDDC
0.2
DP FRDDD (5 - 2, 0.01)
DP-FrDDC (5 0.02)
0.
DP-FEDDC
0.05)
10
10 10 rounds
15 10 20 10
Figure 3: Differential privacy results. Com- parison of FEDDC (top solid line) to FEDDC with clipped parameter updates and Gaussian noise (dashed lines) on CIFARIO with 250 clients.
Should malicious client obtain model updates
through additional attacks, a common defense is applying appropriate clipping and noise before sending models. This guarantees e, d-differential privacy for local data (Wei et al., 2020) at the cost of a Biggh-to-mmderrte loss in model quality. This technique is also proven to defend against backdoor and poisoning attacks (Sun et al., 2019). Moreover, FEDDC is compatible with standard defenses against such attacks, such as noisy or robust aggregation (Liu et al., 2022)-FEDDC with the Radon machine an example of robust aggregation. We illustrate the effectiveness of FEDDC

---

Published as a conference paper at ICLR 2023
centralized (tes)
1
0.8
0.8
0.8
accurityy
0.G
0.6
0.6
0.4
0.4
0.4
0.2
0.2
0.2
train
test
200
400
600
800
1,000
200
400
600
800 1,000
200
400
600 800
1,000
rounds
rounds
rounds
(a) FEDDC with
200.
(b) FEDAVG with b 1.
(c) FEDAVG with b 200.
Figure 4: Synthetic data results. Comparison of FEDDC (a), FEDAVG with same communication (b) and same averaging period (c) for training fully connected NNs on synthetic data. We report mean and confidence accuracy per client in color and accuracy of central learning as dashed black line.
with differential privacy in the following experiment. We train small ResNet on 250 clients using FEDDC with d = and 10, postponing the details on experimental setup to App. A. and A.1.2. Differential privacy is achieved by clipping local model updates and adding Gaussian noise as proposed by Geyer et al. (2017). The results as shown in Figure indicate that the standard trade-off between model quality and privacy holds for FEDDC as well. Moreover, for mild privacy settings the model quality does not decrease. That is, FEDDC is able to robustly predict even under differential privacy. We provide extended discussion the privacy aspects of FEDDC in App. A.7.
EXPERIMENTS ON DEEP LEARNING
Our approach FEDDC, both provably and empirically, improves model quality when using Radon points as aggregation which, however, require convex problems. For non-convex problems, in particular deep learning, averaging is the state-of-the-ar aggregation operator. We, hence, evaluate FEDDC with averaging against the state of the art in federated learning synthetic and real world data using neural networks. As baselines, we consider federated averaging (FEDAVG) (McMahan al., 2017) with optimal communication, FEDAVG with equal communication as FEDDC, and simple daisy-chaining without aggregation. We further consider the 4 state-of-the-an methods FEDPROX (Li al., 2020a), FEDADAGRAD. FEDYOGI, and FEDADAM (Reddi al., 2020). As datasets consider a synthetic classification dataset, image classification in CIFAR 10 (Krizhevsky, 2009), and two real medical datasets: MRI scans for brain tumors? and chest X-rays for pneumonia We provide additional results on MNIST in App. A.3.8. Details on the experimental setup are in App. A.1.1.A.1.2, code publicly available at https: / /g thub. com x kampmi chael FeedDC
Synthetic Data: We first investigate the potential of FEDDC a synthetic binary classification dataset generated by the skleam (Pedregosa et al., 2011) make classiff iessifiiatt fication ion function with 100 features. On this dataset, we train simple fully connected neural network with hidden layers on m 50 clients with n 10 samples per client. We compare FEDDC with daisy-chaining period and aggregation period
200 to FEDAVG with the same amount of communication b = and the same averaging period b = 200. The results presented in Fig. 4 show that FEDDC achieves a test accuracy of 0.89. This is comparable to centralized training on all data which achieves a test accuracy of 0.88. It substantially outperforms both FEDAVG setups, which result in an accuracy of 0.80 and 0.76. Investigating the training of local models between aggreation periods reveals that the main issue of FEDAvG is overfitting of local clients, where FEDAVG train accuracy reaches 1.0 quickly after each averaging step. With these promising results on vanilla neural networks, we next turn real-world image classification problems typically solved with CNNs.
As first challenge for image classification, consider the well-known CIFAR10 image benchmark. We first investigate the effect of the aggregation period b on FEDDC and FEDAVG, separately optimizing for optimal period for both methods. We use a setting of 250 clients with
CIFAR10:
7

---

Published as a conference paper at ICLR 2023
small version of ResNet, and 64 local samples each, which simulates our small sample setting, drawn at random without replacement (details in App. A.1.2). We report the results in Figure 5 and set the period for FEDDC to 10, and consider federated averaging with periods of both b = 1 (equivalent communication to FEDDC with d = b = 10) and = 10 (less communication than FRDDC by factor of 10) for all subsequent experiments.
Next, we consider a subset of 9600 samples spread across 150 clients (i.e. 64 samples per client), which corresponds to our small sample setting. Now, each client is equipped with a
I FENDC FEDAVG
0.8
accuracy
0.6
0.4
larger, untrained 18. Note that the com-
0.2
bined amount of examples only one fifth of the original training data, hence we cannot ex- pect typical CIFARIO performance. To obtain gold standard for comparison, we run cen- tralized learning CENTRAL, separately optimiz- ing its hyperparameters, yielding an accuracy of around 0.65. All results are reported in Ta- ble 1, where we report FEDAVG with b = 1 and b= 10, as these were the best performing set- tings and b = corresponds to equal amounts of communication as FEDDC, We use a daisy chaining period of d d= for FEDDC throughout all experiments for consistency, and provide results for larger daisy chaining periods in App. A.3.5, which, depending on the data distribution, might be favorable. We observe that FEDDC achieves substantially higher accuracy over the baseline set by federated averaging. In App. A.3.7 we show that this holds also for client subsampling. Upon further inspection, we see that FEDAVG drastically overfits, achieving training accuracies of 0.97 (App. A.3.1), a similar trend as on the synthetic data before. Daisy-chaining alone, apart from privacy issues, also performs worse than FEDDC. Intriguingly, also the state of the art shows similar trends. FEDPROX, run with optimal b = 10 and 1 0.1, only achieves an accuracy of 0.51 and FEDADAGRAD FEDYOGI, and FEDADAM show even worse performance of around 0.22, 0.31, and 0.34, respectively. While applied successfully on large-scale data, these methods seem to have shortcomings when it comes small sample regimes.
1
10
20 50
100
200
500
00
averaging period
Figure 5: Averaging periods on CIFARIO. For 150 clients with small ResNets and 64 samples per client, we visualize the test accuracy (higher better) of FEDDC and FEDAVG for different aggregation periods b.
To model different data distributions across clients that could occur in for example our healthcare setting, we ran further experiments on simulated non-iid data, gradually increasing the locally available data, as well as on non-privacy preserving decentralized learning. We investigate the effect of non-iid data on FEDDC by studying the "pathological non-IID partition of the data" (McMahan et al., 2017). Here, each client only sees examples from 2 out of the 10 classes of CIFARIO 10. We again use a subset of the dataset. The results in Tab. show that FEDDC outperforms FEDAVG by a wide margin. It also outperforms FEDPROX, method specialized on heterogeneous datasets in our considered small sample setting. For a similar training setup as before, we show results for gradually increasing local datasets in App. A.3.4. Most notably, FEDDC outperforms FEDAVG even with 150 samples locally. Only when the full CIFARIO dataset distributed across the clients, FEDAVG is on par with FEDDC (see App. Fig. 7). We also compare with distributed training through gradient sharing (App. A.3.3), which discards any privacy concerns, implemented by mini- SGD with parameter settings corresponding to our federated setup as well as a separately optimized version. The results show that such an approach is outperformed by both FEDAVG as well as FEDDC, which in line with previous findings and emphasize the importance of model aggregation.
As a final experiment on CIFARIO, we consider daisy-chaining with different combinations of aggregation methods, and hence its ability to serve as building block that can be combined with other federated learning approaches. In particular, we consider the same setting as before and combine FEDPROX with daisy chaining. The results, reported in Tab. 2, show that this combination is not only successful, but also outperforms all others in terms of accuracy.
Medical image data: Finally, we consider two real medical image datasets representing actual health related machine learning tasks, which are naturally of small sample size. For the brain MRI scans, we simulate 25 clients (c.g., hospitals) with 8 samples each. Each client is equipped with a CNN
*Due hardware restrictions we limited training 150 ResNets, hence 9600 samples across 155 clients.
8

---

Published as a conference paper at ICLR 2023
CIFARIO
MRI
Pneumonia
CIFARIO
FEDDC (ours)
62.9 10.02
78.4 10.61
83.2 10.84
FEDDC
62.9 10.02
DC (haseline)
58.4 +0.85
57.7 11.5
79.8 +0.99
FEDDC +FEDPROX
63.2 20.38
FEDAVG (h=1)
55.8 10.78
74.1 11.68
80.1 1:.33
Non-IID
FEDAVG (b=10)
18.7 10.87
75.6 11.18
79.4 11.11
FEDDC
34.2 =0.61
FEDPROX
51.1 +0.80
76.5 +0.50
80.0 #0.36
FEDAVG (b=l)
30.2 1:2.11
PEDADAGRAD
21.8 #0.01
45.7 #1.25
62.5 #0.01
FEDAVG (b=10)
24.9 #1.95
FEDYOGI
31.4 +4.37
71.3 #1.62
77.6 #0.64
FEDPROX
32.8 1.0.0
FEDADAM
34.0 +0.23
73.8 #1.98
73.5 #0.36
FEDADAGRAD
11.7 1..00
CENTRAL
65.1 11.44
82.1 1:1000
84.1 13.31
FEDADAM
13.0 10.00
FEG
12.5 +0.04
Table 1: Results image data, reported is the average test accuracy of the final model over three runs (= denotes maximum deviation from the average).
Table 2: Combination of FEDDC with FEDAVG and FEDPROX and non-iid results on CIFARIO.
(see App. A.I.I). J. The results for brain tumor prediction evaluated on test set of 53 of these scans are reported in Table Overall, FEDDC performs best among the federated learning approaches and is close to the centralized model. Whereas FEDPROX performed comparably poorly on CIFAR1O. 10, it now outperforms FEDAVG. Similar before, we observe considerable margin between all competing methods and FEDDC. To investigate the effect of skewed distributions of sample sizes across clients, such as smaller hospitals having less data than larger ones, we provide additional experiments in App. A.3.5. The key insight is that also in these settings, FEDDC outperforms FEDAVG considerably, and is close to its performance on the unskewed datasets.
For the pneumonia dataset, we simulate 150 clients training ResNet18 (see App. A.1.I) with 8 samples per client, the hold out test set are 624 images. The results, reported Table 1, show similar trends for the other datasets, with FEDDC outperforming all baselines and the state of the art, and being within the performance of the centrally trained model. Moreover it highlights that FEDDC enables to train ResNet18 high accuracy with little samples per client.
DISCUSSION AND CONCLUSION
We propose to combine daisy-chaining and aggregation to effectively learn high quality models in a federated setting where only little data is available locally. We formally prove convergence of our approach FEDDC, and for convex settings provide PAC-like generalization guarantees when aggregating by iterated Radon points. Empirical results on the SUSY benchmark underline these theoretical guarantees, with FEDDC matching the performance of centralized learning. Extensive empirical evaluation shows that the proposed combination of daisy-chaining and aggregation enables federated learning from small datasets practice. When using averaging, improve upon the state of the art for federated deep learning by large margin for the considered small sample settings. Last but not least, we show that daisy-chaining is not restricted to FEDDC, but can be included in FEDAVG, Radon machines, and FEDPROX as a building block, too.
FEDDC permits differential privacy mechanisms that introduce noise model parameters, offering protection against membership inference, poisoning and backdoor attacks. Through the random permutations in faisy-chaining rounds, FEDDC is also robust against reconstruction attacks. Through the daisy-chaining rounds, we see linear increase in communication. As we are primarily interested in healthcare applications, where communication is not bottleneck, such an increase communi- cation is negligible. Importantly, FEDDC outperforms FEDAVG in practice also when both use the same amount of communication. Improving the communication efficiency considering settings where bandwidth is limited, e.g., model training on mobile devices, would make for engaging future work.
We conclude that dhiiinn lends itself as simple, yet effective building block to improve federated learning, complementing existing work to extend to settings where little data is available per client. FEDDC, thus, might offer solution to the open problem of federated learning in healthcare, where very few, undisclosable samples are available each site.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
The authors thank Sebastian U. Stich for his detailed comments on an earlier draft. Michael Kamp received support from the Cancer Research Center Cologne Essen (CCCE). Jonas Fischer is supported by grant from the US National Cancer Institute (R35CA220523).
REFERENCES
Idan Achituve, Aviv Shamsian, Aviv Navon, Gal Chechik, and Ethan Fetaya. Personalized feder- ated learning with gaussian processes. Advances Neural Information Processing Systems, volume 34, Curran Associates, Inc., 2021. 3
Giuseppe Ateniese, Luigi V Mancini, Angelo Spognardi, Antonio Villani, Domenico Vitali, and Giovanni Felici. Hacking smart machines with smarter ones: How to extract meaningful data from machine learning classifiers. International Journal of Security and Networks, 10(3):137-150, 2015. 22
Pierre Baldi, Peter Sadowski, and Daniel Whiteson. Searching for exotic particles high-energy physics with deep learning. Nature communications, 5(1):1-9, 2014. 15
Arjun Nitin Bhagoji, Supriyo Chakraborty, Prateek Mittal, and Seraphin Calo. Analyzing federated learning through an adversarial lens. In International Conference on Machine Learning, pages 634 643. PMLR, 2019. 22
Kenneth I. Clarkson, David Eppstein, Gary I. Miller, Carl Sturtivant, and Shang-Hua Teng. Approxi- mating center points with iterative radon points. International Journal of Computational Geometry & Applications, 6(03):357-377, 1996. 5, 15
Liam Collins, Hamed Hassani, Aryan Mokhtari, and Sanjay Shakkottai. Exploiting shared representa- tions for personalized federated learning. In Marina Mcila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 2089-200 2089-2099. PMLR, 18-24 Jul 2021.
Robin C Geyer, Tassilo Klein, and Moin Nabi. Differentially private federated learning: A client level perspective. arXiv preprint arXiv:1712.075577 2017.
Ran Gilad Baaad-BBacrrch,,,, Amir Navot, and Naftali Tishby. Bayes and tukey meet at the center point. In International Conference on Computational Learning Theory, pages 549 563. Springer, 2004. 5
Kristin L Granlund, Sui-Seng Tee, Hebert Vargas, Serge Lyashchenko, Ed Reznik, Samson Fine, Vincent Laudone, James A Eastham, Karim A Touijer, Victor E Reuter, et al. Hyperpolarized mri of human prostate cancer reveals increased lactate with tumor grade driven by monocarboxylate transporter 1. Cell metabolism, 31(1):105-114 2020.
Farzin Haddadpour and Mehrdad Mahdavi. On the convergence of local descent methods in federated learning. arXiv preprint 1xXiv:1910.14422. 2019. 1,
Weituo Hao, Mostafa El-Khamy, Jungwon Lee, Jianyi Zhang, Kevin Liang, Changyou Chen, and Lawrence Carin Duke. Towards fair federated learning with zero-shot data augmentation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 3310-3319, 2021. 2
Baihe Huang, Xiaoxiao Li, Zhao Song, and Xin Yang. Fl-ntk: A neural tangent kernel-based framework for federated learning analysis. In International Conference on Machine Learning. pages 4423 4434. PMLR, 2021.
Marwa Ibrahim, Mohammad Wedyan, Ryan Alturki, Muazzam Khan, and Adel Al-Jumaily. Augmentation in healthcare: Augmented biosignal using deep learning and tensor representation. Journal of Healthcare Engineering, 2021, 2021.
Márk Jelasity, Alberto Montresor, and Ozalp Babaoglu. Gossip- basii- aggregation in large dynamic networks. ACM Transactions on Computer Systems (TOCS), 23(3):219-252, 2005.
10

---

Published as a conference paper at ICLR 2023
Michael Kamp. Black-Bor Box Parallelization for Machine Learning. PhD thesis. Rheinische Friedrich- Wilhelms- Wiilhlmm-Universsttil Universiäät Bonn, Universitäts-um Landesbibliothek Bonn, 2019.
Michael Kamp, Mario Boley, Olana Missura. and Thomas Gärtner. Effective parallelisation for machine learning. In Advances in Neural Information Processing Systems, volume 30, pages 6480-6491, Curran Associates, Inc., 2017. 3, 4, 14, 15
Michael Kamp, Linara Adilova, Joachim Sicking, Fabian Hüger, Peter Schlicht, Tim Wirtz, and Stefan Wrobel. Efficient decentralized deep learning by dynamic model averaging. Joins European Conference Machine Learning and Knowledge Discovery in Databases, pages 499-409. Springer, 2018. 3, 4
Bingyi Kang, Zhuang Liu, Xin Wang, Fisher Yu, Jiashi Feng, and Trevor Darrell. Few-shot object detection via feature reweighting. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 8420-8429, 2019.
Péter Kiss and Tomas Horvath. Migrating models: A decentralized view federated learning. In Proceedings of the Workshop on Parallel, Distributed, and Federated Learning. Springer, 2021.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, University of Toronto, Toronto, 2009. 2,
Sang Gyu Kwak and Jong Hae Kim. Central limit theorem: the cornertoone of modern statistics.
Korean journal of anesthesiology, 70(2):144, 2017.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recogmition. Proceedings of the IEEE, 86( 86(11):22782232/ 1998. 18
Qinbin Li, Bingsheng He, and Dawn Song. Model-contrastive federated learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10713-10722, 2021.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization heterogeneous networks. In Conference on Machine Learning and Systems, 2020a, 2020a. 3,
Xiaoxiao Li, Meirui Jiang, Xiaofei Zhang, Michael Kamp, and Qi Dou. Fedbn: Federated learning non-iid features via local batch normalization. In International Conference Learning Representations, 2020b.
Pei Liu, Xuemin Wang, Chao Xiang, and Weiye Meng. survey of text data augmentation. In 2020 International Conference on Computer Communccation and Network Security (CCNS), pages 191-195. IEBE, 2020.
Pengrui Liu, Xiangrui Xu, and Wei Wang. Threats, attacks and defenses to federated learning: issues, taxonomy and perspectives. Cybersecurity, 5(1):4 2022. 6, 22
Chuan Ma, Jun Li. Ming Ding, Howard H Yang. Feng Shu. Tony QS Quek, and H Vincent Poor. On safeguarding privacy and security in the framework of federated learning. IEEE network, 34(4): 142-248, 2020. 6, 22
Othmane Marfoq, Giovanni Neglia, Aurélien Bellet, Laetitia Kameni, and Richard Vidal. Federated multi-task learning under a mixture of distributions. In Advances in Neural Information Processing Systems. Curran Associates, Inc., 2021. 2
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera Arcas. Communication-efficieenn learning of deep networks from decentralized data. Artificial Intelli- gence and Stafistics, pages 1273-1282, 2017. 3,
Peter Neal. The generalised coupon collector problem. Journal of Applied Probability, 45(3): 621-629, 2008. 20
11

---

Published as a conference paper at ICLR 2023
Corrie A Painter, Esha Jain, Brett N Tomson, Michael Dunphy, Rachel E Stoddard, Beena S Thomas, Alyssa L Damon, Shahrayz Shah, Dewey Kim, Jorge Gómez Tejeda Zañudo, et al. The angiosar- coma project: enabling genomic and clinical discoveries in rare cancer through autient-partneree research. Nature medicine, 26(2):
2020. 1
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research,
12:2825-2830 2011. 7, 14
Krishna Pillutla, Sham M Kakade, and Zaid Harchaoui. Robust aggregation for federated learning. IEEE Transactions on Signal Processing. 70:1 142-114,,,, 2022. 3
Viraj Prabhu, Anitha Kamnan, Murali Ravuri, Manish Chaplain, David Sontag, and Xavier Amatriain. Few-shot learning for dermatological disease diagnosis. In Machine Learning for Healthcare Conference, pages 532-552. PMLR, 2019.
Johann Radon. Mengen konvexer Körper, die einen gemeinsamen Punkt enthalten. Mathematische Annalen, 83(1):113-115 1921. 4, 15
Sashank J Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and Hugh Brendan McMahan. Adaptive federated optimization. In International Conference on Learning Representations, 2020. 2, 7, 14
Amirhossein Reisizadeh, Farzan Farnia, Ramtin Pedarsani, and Ali Jadbabaie. Robust federated learning: The case of affine distribution shifts. In Advances in Neural Information Processing Systems, volume 33, pages 21554-20 21565. Curran Associates, Inc., 2020a. 2
Amirhossein Reisizadeh, Aryan Mokhtari, Hamed Hassani, Ali Jadbabaie, and Ramtin Pedarsani. Fedpaq: A communication--effiieee federated learning method with periodic averaging and quan- tization. In International Conference on Artificial Intelligence and Statistics, pages 2021-2031. PMLR, 2020b. 3
Shai Shalev-Shwart and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014. 4
Ohad Shamir and Nathan Srebro. Distributed stochastic optimization and learning. In 2014 52nd Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 850- 857. IEEE, 2014. 3, 4, 16
Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference attacks against machine learning models. In 2017 IEEE Symposium on Security and Privacy (SP), pages 3-18. IEEE, 2017. 1, 6,
Xiaoping Su, Xiaofan Lu, Sehrish Khan Bazai, Eva Compérat, Roger Mouawad, Hui Yao, Morgan Rouprêt, Jean-Philipee Spano, David Khayat, Irwin Davidson, et al. Comprehensive integrative profiling of upper tract urothelial carcinomas. Genome biology, 22(1):1 2021.
Ziteng Sun, Peter Kairouz, Ananda Theertha Suresh, and H Brendan McMahan. Can you really backdoor federated learning? arXiv preprint arXiv:1911.0796. 2019. 6, 22
Lisa Torrey and Jude Shavlik. Transfer learning. In Handbook of research on machine learning applications and trends: algorithms,, methods, and techniques, pages 242-264. IGI global, 2010.
John W Tukey, Mathematics and picturing data. In Proceedings of the International Congress of Mathematics, volume 2, pages 523-531, 1975.
Oriol Vinyals, Charles Blundell, Timothy Lillicrap, Daan Wierstra, al. Matching networks for one shot learning. In Advances in neural information processing systems, volume 29, pages 3630-3638. Curran Associates, Inc., 2016.
Ulike Von Luxburg and Bernhard Schölkopf. Statistical learning theory: Models, concepts, and results. In Handbook of the History of Logic, volume 10, pages 651-706. Elsevier, 2011.
12

---

Published as a conference paper at ICLR 2023
Hongyi Wang, Mikhail Yurochkin, Yuekai Sun, Dimitris Papailiopollos, and Yasaman Khazaeni. Fed- erated learning with matched averaging. In International Conference on Learning Representations, 2019. 2
Kang Wei, Jun Li, Ming Ding, Chuan Ma, Howard H Yang, Farhad Farokhi, Shi Jin, Tony QS Quek, and H Vincent Poor. Federated learning with differential privacy: Algorithms and performance analysis. IEEE Transactions on Information Forensics and Security, 15:3454-344 -469,, 2020. 6, 22
Qian Yang, Jianyi Zhang, Weituo Hao, Gregory Spell, and Lawrence Carin. Flop: Federated learning on medical datasets using partial networks. In Proceedings of the 27th ACM SIGKDD Con- ference on Knowledge Discovery and Data Mining, page 3845-3853, Association for Computing Machinery, 2021. 3
Hao Yu, Sen Yang, and Shenghuo Zhu. Parallel restarted sgd with faster convergence and less communication: Demystifying why model averaging works for deep learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 5693-5700, 2019. 4, 19
Mikhail Yurochkin, Mayank Agarwal, Soumya Ghosh, Kristjan Greenewald, Nghia Hoang, and Yasaman Khazaeni. Bayesian nonparametric federated learning of neural networks. In International Conference on Machine Learning, pages 7252-7261. PMLR, 2019.
Chengliang Zhang. Suyi Li, Junzhe Xia, Wei Wang. Feng Yan, and Yang Liu. Batcherypt: Effi- cient homomorphic encryption for cross-silo federated learning. In USENIX Annual Technical Conference, pages 493-506, 2020. 22
Ligeng Zhu and Song Han. Deep leakage from gradients. In Federated learning, pages 17-31. Springer, 2020.
13


Reviews:
[{"review_id": "zeHp-qj6-R", "reviewer": "Reviewer_WcDr", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposed to tackle data insufficiency in Federated Learning through daisy-chain training, which interchanges model aggregation and model permutation across clients. A theoretical convergence guarantee is provided. Empirical results show that the proposed algorithm FedDC outperforms FedAvg and other baselines on certain benchmarks with small data samples per client.", "summary_of_the_review": "This paper tackles data insufficiency in FL by interleaving model aggregation and permutation. The approach outperforms traditional FL on small dataset scenarios, although the approach is not tested on more practical cases, such as FL with straggler users or with data heterogeneity.\n", "strength_and_weaknesses": "Strengths:\n\n+ tackles a practical & important issue in FL: small datasets\n+ provides proofs of convergence property;\n+ promising empirical results compared with traditional FL on certain small data settings.\n\n\nCons:\n- My biggest concern about this work is that it is not tested on the most common scenario with*straggler* users. In both the proposed algorithm and empirical experiments, **all** clients have participated in local training and model aggregation/permutation in each round. This is a too strong assumption.\n- Under the straggler user scenario, the efficiency of 'permutating models across clients' would largely drop, and the model performance will theoretically and empirically degrade given the same learning rounds. Authors should provide experiments given different ratios of active users.\n- Another untouched issue in this work is data heterogeneity, which could be a more challenging problem than small datasets. In the experiments, each client data distribution is still i.i.d when they are assigned with samples randomly drawn from a global view. It is not surprising that FedDC would perform well given such data distributions. I am curious how FedDC would perform compared with FedAvg/FedProx when there is data heterogeneity among clients.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "uB5u1Us9aCS", "reviewer": "Reviewer_L65q", "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": "", "summary_of_the_paper": "This paper points out the negative impact of small client data on FedAvg: small data results in poor local models; and aggregating with poor local models will impact the performance of FedAvg. \n\nTo mitigate this impact, the authors introduce a number of model permutation steps between two model aggregation steps & defining the aggregation operator as computing the Radon point of the set of local models. Before the local models are aggregated, we pair them with a permuted list of clients and send each model to its corresponding paired-up client so that after a few of such permuted redistribution, a local model can draw benefit from multiple local datasets instead of one. \n\nThe paper also provides an interesting theoretical analysis which explicitly details the minimum interval between two consecutive aggregation steps (in terms of the sample complexity of the local learning algorithm & the interval between two consecutive permutation steps) -- see Lemma 4 & Proposition 5 -- so that the chance that the generalized error of the aggregated model exceeds a user-specified threshold is doubly-exponentially smaller (see Eq. 2) than that of any local models.\n\nThe theory also points out that without the permutation step, the above will not happen if the size of local datasets is smaller than the sample complexity of the local learning algorithm (see Corollary 3). \n\nThe empirical results indeed show that the proposed method perform better than other baselines in several low-data simulations derived from several benchmark datasets such as CIFAR10, MRI & Pneumonia.", "summary_of_the_review": "This is an interesting paper presenting a good mix of elegant theoretical results & new algorithmic ideas. The idea is very different from what has been explored in the literature. The current form of the paper is acceptable to me if the concerns above can be addressed convincingly. At this moment, I am rating this work at weak accept mainly because of the well-developed theory that could potentially inspire more interesting development in the future; but I still remain a bit doubtful of its practical impact -- see my comments above.", "strength_and_weaknesses": "Strengths:\n\n+ The paper is very well-written -- I like how the theory is presented in a very organized manner which makes it comfortable to follow \n+ The solution is novel and opens up a new different perspective for FL with low client data\n+ There are rigorous analysis of the proposed idea formalized in forms of concrete theoretical results\n\nWeaknesses:\n\n- Lack of comparison with variants that communicate gradients instead of model updates -- more on this below\n- Lack of comparison with baselines in the full-data regime (in addition to what has been demonstrated in low-data regime)\n- Developed theory is restricted to convex loss -- would be good to discuss directions to expand towards more general losses -- i think unless the model is linear, the loss will not be convex in the model parameter\n- Lack of intuition on what are the advantages Radon point & Radon machine have over a simple weighted average for the aggregation step (other than that the former elicit interesting theoretical results)", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "e14kR6tgDu", "reviewer": "Reviewer_LWYx", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper considers the interesting problem of cross-silo FL with very small datasets, with some devices having only two samples per device. With an aptly crafted aggregation scheme, the authors propose to interleave model aggregation and permutation steps, which lets every model to be trained through multiple local datasets before aggregation. For the proposed algorithm FedDC, strong theoretical bounds are derived. Finally experimental results demonstrate the usefulness of the approach.", "summary_of_the_review": "The cross-silo setting in FL with devices containing small number of samples is a problem of particular interest. The authors propose FedDC and provide a well rounded justification in terms of theoretical and experimental evaluation. The paper is in a pretty good shape. Adding some experimental evidence in terms of dealing with devices with unequal number of samples would only strengthen the paper.", "strength_and_weaknesses": "Strengths:\n+ The paper is very well written and the problem under consideration is super well motivated.\n+ While device selection is not taken into account, the authors restrict their attention to cross-silo settings, where approaches which involve full device participation scale well. The theoretical results are comprehensive in terms of convergence, coverage in terms of local datasets and model improvement.\n+ The experimental results are also comprehensive in terms of various aspects of non-iidness and beats considered baselines consistently.\n+ One of the weaknesses of FedDC because of daisy chaining is because of each device having an opportunity of reconstructing data from model updates from other devices. The authors acknowledge the shortcoming and propose to address it through the usage of gradient clipping and Gaussian mechanism.\n\nWeaknesses:\n- Inspite of using DP related techniques, the exposure of model updates to each individual device allows a malicious client to retain the model and engage in a data reconstruction attack and subsequently do so for each client effectively. It is not clear what level of Gaussian mechanism would be able to alleviate such a privacy loss and what would be the effect of such a scheme on the performance of the algorithm.\n- The other concern is regarding experiments where in each empirical evaluation the number of samples across clients is the same. Its not clear as to what would be the impact of daisy chaining, when encountering clients which have fewer samples. None of the experiments in the paper seem to study that.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "HNNzlQL-_k", "reviewer": "Reviewer_mrq4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this work, a practical and efficient FL learning framework is proposed for improving aggregation performance over multiple clients. The core step of this model is to use the interleaving model aggregation and permutation steps so that the proposed federated daisy-chaining method can work well for data sparse problems. Multiple experimental results show that FedDC outperforms the state-of-the-art methods significantly, e.g., FedAvg.", "summary_of_the_review": "In summary, this paper proposes an efficient training framework, FedDC, for dealing with the data sparse problem, but the theoretical justification of the convergence and generalization contains a gap, which weakens the contributions of this work. \n\n\n\n====================== after Zoom Meeting ===================\n\nAfter the discussion with the AC and other reviewers, I suppose that there are some merits of this work and increase the score, even 1) the setting of the convergence part is not consistent with the PAC analysis and there is no condition of step size to ensure the convergence; 2) tuning the multiple hyper-parameters to satisfy the theoretical conditions is a very difficult task, 3) and there is still a gap between the theory and practical implementation for the PAC part. ", "strength_and_weaknesses": "Strength: this work considers a practical issue of data sparse in the FL systems. It further provides theoretical analysis results on convergence, generalization performance evaluation, requirements on communications, and massive numerical results on classification problems.\n\nWeaknesses: even the work is new and encouraging, there are still some major concerns as follows:\n\n1) A convergence result is given in Corollary 1, which basically uses Yu et al. (2019)' result. How does the permutation affect the convergence is not analyzed. Does Yu et al. (2019)'s analysis covers the client permutation? Note that there is a significant difference between the selection with and without replacement. There is a gap between the FedDC and the analysis.\n\n2)  In the convergence result, $b$ needs to be less than a threshold, but eq.(2) $b$ is required to be large than a threshold. Is there an overlap between these?\n\n3) This work assumes that the risk considered is convex while their convergence result is borrowed from the nonconvex. A consistent argument is encouraged.\n\n4)  The authors claimed that FedDC can perform better in the data sparse case, however, the theory seems uncorrelated with any parameters regarding the data sample size (Lemma 4). In Prop. 5, if m is small and n is large, will $b$ be a negative number? A sufficient discussion of the theoretical results should be provided.\n\n5) $m$ is assumed to be large enough so that the local model can improve the performance. Will this method also work for $m$ is small in the sense that the same as FedAvg or will diverge? also, how decide $r$ in practice?\n\n6) The theoretical results seem completely independent on which federated learning algorithm adopted, proxFed, or adam based algorithm. In other word, the convergence rate of the algorithm will not affect the $b$ and $T$, right?\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "-BXvwAPbwcu", "reviewer": "Reviewer_9XFM", "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": "", "summary_of_the_paper": "The authors propose FEDDC, a new scheme for training federated learning systems. The main idea is that at each communication round a client can either receive the model of another random client (daisy chaining round) or an aggregated model (aggregation round). The authors show convergence rate and generalization bound for their method in the convex case.", "summary_of_the_review": "This is a nice paper with interesting approach, yet I think that the comparison to baseline method is severely lacking.", "strength_and_weaknesses": "Strength:\n* Interesting paper with a novel method for sharing models in FL systems.\n* Seems to work well compared to baseline methods, especially when the number of samples per client is low.\n* The theoretical guarantees are a nice addition; although they feel a bit contrived. \n\nWeaknesses:\n* Although the communication cost of both FedAvg and FEDDC is linear in the number of clients, in FedAvg we usually sample a subset of the clients while in FEDDC at each round all clients participate. So in practice, FEDDC is substantially more expensive than FedAvg and its variants (and not only by a slight increase).\n* As the authors state, their method is susceptible to a new kind of attack which is a malicious client. I admire the authors for being honest about that, nevertheless, this is still a major concern in FL systems.\n* The authors claim to compare against SoTA methods, but all baseline methods are obsolete (most recent ones are from 2020). I believe that this is not nearly enough to showcase the authors' claim. In particular, the authors should compare to other methods that were designed for small datasets as well.", "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": {}}]

Author rebuttal:

Decision: Accept: poster