Synthetic data shuffling accelerates the convergence of federated learning under data heterogeneity
Authors: Bo Li
Yasin Esfandiari
Mikkel N. Schmidt
Tommy Sonne Alstrøm
Sebastian U Stich
Venue: Accepted by TMLR ()

Abstract: In federated learning, data heterogeneity is a critical challenge. A straightforward solution is to shuffle the clients' data to homogenize the distribution. However, this may violate data access rights, and how and when shuffling can accelerate the convergence of a federated optimization algorithm is not theoretically well understood. In this paper, we establish a precise and quantifiable correspondence between data heterogeneity and parameters in the convergence rate when a fraction of data is shuffled across clients. We discuss that shuffling can, in some cases, quadratically reduce the gradient dissimilarity with respect to the shuffling percentage, accelerating convergence. Inspired by the theory, we propose a practical approach that addresses the data access rights issue by shuffling locally generated synthetic data. The experimental results show that shuffling synthetic data improves the performance of multiple existing federated learning algorithms by a large margin.

Published in Transactions on Machine Learning Research (03/2024)
Synthetic data shuffling accelerates the convergence of fed- erated learning under data heterogeneity
Bo Li*
blio ddu.. dk
Technical University of Denmark
Yasin Esfandiari
yasin.esfandiari@cciiuu.
CISPA Helmholtz Center for Information Security
Mikkel N. Schmidt
mnsc@dtu.dd dk
Technicol University of Denmark
Tommy S. Alstrom
tsal@dtu. dk
Technicol University of Denmark
Sebastian U. Stich
stich@cispo..c de
CISPA Helmholtz Center for Information Security
Reviewed on OpenReview: https: http:::///peneeeeeeeeeeee///// id c504HUypqm
Abstract
In federated learning, data heterogeneity is critical challenge. A straightforward solution is to shuffle the clients' data to homogenize the distribution. However, this may violate data access rights, and how and when shuffling can accelerate the convergence of a federated optimization algorithm is not thcoretically well understood. In this paper, we establish a precise and quantifiable correspondence between data heterogeneity and parameters in the convergence rate when a fraction of data shuffled across clients. We discuss that shuffling can in some cases quadratically reduce the gradient dissimilarity with respect to the shuffling percentage, accelerating convergence. Inspired by the theory, propose practical approach that addresses the data access rights issue by shuffling locally generated synthetic data. The experimental results show that shufiling synthetic data improves the performance of multiple existing federated learning algorithms by a large margin.
1 Introduction
Federated learning (FL) is emerging as fundamental distributed learning paradigm that allows central server model to be learned collaboratively from distributed clients without ever requesting the client data,
thereby dealing with the issue data access rights (Konečný et al. 2016 Kairouz et al., 2019 Wang et al. 2021 Sheller al. 2020). One of the most popular algorithms in FL is FedAvg (Konečný et al.) 2016): A server distributes a model the participating clients, who then update with their local data for multiple steps before communicating it to the server, where the reccived client models aggregated, finishing round of communication. Two main challenges in FedAvg optimization are 1) large data heterogeneity across clients and 2) limited available data on each client (Konečný et al. 2016).
Data hetcrogeneity refors to differences in data distributions among participating clients (Karrouz et al. 2019). Existing works typically characterize its impact on the convergence of FedAvg using bounds on the gradient dissimilarity, which suggests a slow convergence when the data heterogeneity is high (Karimireddy et a.l. 2020b; Koloskova al.) 2020). Many efforts have been made improve FedAvg's performance in
"work done CISPA

---

Published in Transactions on Machine Learning Research (03/2024)
this setting using advanced techniques such as control variates (Krrmireddy et al. 2020b Acar et al. 2021
Li et al. 2022a) and regularizers (Wang et al. 2020). Although these algorithms have demonstrated great success in many applications, they are insufficient under high data heterogeneity (Yu et al., 2022). On the other hand, many rescarchers (Zhao et al. 2018 Woodworth et al.) 2020) have observed that simply augmenting the dataset on each client. with a small portion of shuflled data collected from all clients can significantly accelerate the convergence of FodAvg. However, has yet to be well understood when and, in particular, by how much shuffling can accelerate the convergence.
Another challenge arises when the amount of available data each client is limited, especially when the number of classes or tasks is large. High-capacity deep neural networks (DNN) usually require largo-scale labelled datasets to avoid overfitting (He et al. 2016 Shrivastava et al. 2016). However, labelled data acqui- sition can be expensive and time--cossuiing (Shrivastava et al. 2016). Therefore, learning with conditionally
generated synthetic samples has been an active area of research (Schwag et al. 2022 Goetz & Tewari 2020;
Shrivastava et al.) 2016 Zhang et al., 2022 Zhu al.)
2021 Li ct al.) 2022b). Adapting the framework of
using synthetic data from centralized learning to FL is not trivial due to the unique properties of FL, such distributed datasets, high communication costs, and privacy requirements (Kairouz et al. 2019
In this work, we rigorously study the correspondence between the data heterogencity and the parameters in the convergence rate via shuffling. Specifically, we show that reducing data heterogeneity by shuffling in a small percentage of data from existing clients can give a quadratic reduction in the gradient dissimilarity in some scenarios and can lead to a super-linear reduction (a factor greater than the shuffle percentage) in the number of rounds to reach the target accuracy. Further, we show that it holds in both strongly-covver functions and non-convex DNN-based FL.
While we theoretically understand the optimization improvement from shuflling, gathering real data from clients goes against the goal of protecting privacy in FL. Therefore, we propose a more practical framework Fedssyn where we shuffle a collection of synthetic data from all the clients at the beginning of FL (see Fig. D. Each client learns a client-specific generator with a subset of its local data and generates synthetic data. The server then receives, shuflles, partitions, and redistributes the synthetic data to each client. Collecting visually interpretable synthetic data can be more transparent and secure than collecting the black-box generators. This transforms the issue into one concerning the assurance of privacy in the generalive model, an area of active research that already boasts some well-established techniques [Yoon] et al. 20119; Chen et al. (2020); Wang et al. (003)). Therefore, we also illustrate the benefit of Fedssyn in a differentially private setting with a small-scale experiment.
Contributions: We summarize our main results below:
We rigorously decompose the impact of shuffling on the convergence rate in FedAvg. Our careful discussion provides insights in understanding when and how shuffling can accelerate the convergence of FedAvg. We empirically verify our theoretical statements on strongly convex and DNN-based non-convex functions.
Inspired by the theoretical understanding of the elfects of data shuffling, we present a practical framework Fedssyn, that shuffess for privacy reasons locally generated synthetic data and can be coupled with ony FL algorithms.
We empirically demonstrate that using Fedssyn on top of several popular FL algorithms reduces commu- nication cost and improves the Top-1 accuracy. Results hold across multiple datasets, different levels of data heterogeneity, mumber of clients, and participation rates.
1.1 Related work
Federated optimization: FL is a fast-growing field (Wang et al. 2021 We here mainly focus on works
that address the optimization problems in FL. FedAvg Konečný et al. (2016) is one of the most commonly used optimization techniques. Despite its success in many applications, its convergence performance under
heterogencous data is still an active area of research (Karimireddy et al. 2020b Wang et al.) 2022a Khaled
et al. 2019 Sahu et al. 2018 Woodworth et al. 2020 et al. 2022a). The results suggest that the
2

---

Published in Transactions on Machine Learning Research (03/2024)
synthetic data
generator
synthetic data
client
client
FedAvg
0.8
Accurscy
0.6
0.4
Non-IID clients Shuffie 50% real data Shuffle 50% synthatic data Centralised
client data
dient data
0.2
10
20
30
40
Server: synthetic data aggregation & shuffling
Server: client model aggregation
Communication rounds
(a)
(b)
Our proposed framework. (a) Each client learns a generator with a subset of its local data and generates synthelic data, which are communicated to the server. The server then shuffles and sends the partitioned collection of the synthetic data to each client. (b) With the updated local data, any FT, algorithms can be used to learn a server model. (c) When the clients very heterogeneous, compared to shuffling the real data, shuffling synthetic data achieves similar accuracy while alleviating information leakage.
Figure 1:
drift caused by the data heterogeneity has a strong negative impact on FedAvg convergence. Several lines of work have been proposed to reduce the impact of data heterogeneity, including regularizers (Sahu et al. 2018), control variates for correcting gradients (Karimireddy et al., 2020b) |car et al. 2021 Li et al. 2022a
Mitra et al. 2021), and decoupled representation and classification (Collins al. [2022] Luo et al. 2021 Yu
et al. 2022). ) sophisticated aggregation strategies (Lin et al. 2020
2020a Wang et al, 2020 Reddi et al. 2020). However, such methods fall short in addressing high client heterogencity and fail to achieve accuracies on par with those in the IID setting (Yu et al. 2022)
Karimireddy
Synthetic data-based FL: Many works attempt to improve the performance of FL algorithms using synthetic data (Zhu et al. 2021 Goetz & Tewari, 2020). We can group them into 1) client-generator
G. (Xiong et al. 2023 Li et al. 2022b Wang el al. 2023), where a generalor trained locally and sent to the server for synthetic data generation, and 2) server-generane
(Zhu et al. 2021 Zhang et al. (022), where centralized generator helps with updating the server and/or client model. See Table below for summary. Transmitting the synthetic data at every round D(r) can incur extra communication costs. Updating the server model with the synthetic data x +- D requires the synthetic data to be of high quality Lin et al. (2020): Sehwag et al.] (0022,, as low-quality synthetic data or synthetic data with different distribution than the actual local data may discard the valuable information the server model has Iearned. Sending generators instead of synthetic data may be less secure, seeing that having access to the generator's parameters gives the server more powerful attacking abilities Wang et al. 2022b).
Local Gi
Server G D(r) x D Pseudo-label
FcdDM Xiong et al. 20033
EN Zhu et al. 2021
x
Dense Zhang et al. 2022
X
V
x
V
X
SDA- Li et al.
2022b
X
V
ours
X
X
X
X
Generative models: Generative models can be trained to mimic the underlying distribution of complex data modalitics [Goodfellow et al.) 2014). Generative Adversary Network (GANs) have achieved great success in generaling ing high-quality images (inha et al.) 2021 Zhao el al. 2020: Karras el al. 2020);; however, training GANs in a FL setup is challenging as each client only has limited data (Salimans et al. 2016 Konečný et al,, 2016). Diffusion models (Ho al.] (020)) have attracted much attention due the high diversity of the generated samples Schwag et al. (2022) and training efficiency (Ho et al. 2020). Therefore, we study to use DDPM our local generator in this paper.
3

---

Published in Transactions on Machine Learning Research (03/2024)
Differentially private learning in neural networks: Differentially private stochastic gradient descent (DP-SGD) bounds the influence of any single imput the output of machine learning algorithms to preserve privacy (McMahan et al. 2018 Shokri & Shmatikov 2015; Abadi et al. 2016 Xie et al., 2018 Chen et al, 2020 Yoon et al. 2019). For example, Dockhorn et al. (2022) have proposed to train diffusion models with differential privacy guarantees that. can alleviate privacy leakage.
2 Influence of the data heterogeneity on the convergence rate
We formalize the problem as minimizing the expectation of a sum of stochastic functions (e.g. the loss associated with cach datapoint)::
f(x, f(x, D.) :- EE (x)
min XER
where D, represents the distribution of & on client i and we use D= U, D, to denote the uniform distribution over the joint data. We assume gradient dissimilarity, bounded noise, and smoothness of the function, following Koloskova et al. (2020 : Stich 2019):
Assumption (gradient dissimilarity). We assume that there exists C² 2 0 such that Vx E Rd:
EM
Vs(x < c²
Assumption (stochastic noise). We assume that there exist o 2 0 and 0² > 0 such that Vx e Rdd E [N]:
BE-D/IIVF(x - vx(x, D.)1 < o², BE - vs(x, D)11 & dawy-
Assumption (smoothness). We assume that each F(x, {) for & E D,, [N] is L-smooth, i.e.,:
| fxx, D.ll -
yll,
MxyeKK
These assumptions are standard in the literature (ef. Koloskova et al. 2020 et al. 2020 We further denote by Lavg I L the smoothness of f(x, D), and by Lmax S L a uniform upper bound on the smoothness of each single f(x, D)), for all i [N].
Woodworth et al. 2020 Khaled
2.1
Motivation
Data heterogeneity is unavoidable in real-world FL applications since each client often collects data individ- ually (Konečný et al.) 2016). One simple but effective strategy to address data heterogeneity to replace a small fraction (e.g. 10%) of the client's data with shuffled data collected from other clients. WWodworth al.)
(2020 Zhao et al. (2018) have observed that shuffling can vastly reduce the reached error. In the following, focus on explaining this empirically tremendous optimization improvement from theoretical perspective. However, emphasize that this is not a practical approach, data sharing may be diametrically at odds with the fundamentals of FL.
2.2 Modelling Data Shuffling and Theoretical Analysis
We formally describe the data heterogeneity scenario as follows: We assume each client has access to data with distribution D, that is non-iid across clients and we denote by D = U, Dj the uniform distribution over the joint data. We can now model our shuflling scenario where the server mixes and redistribules a small p fraction of the data by introducing new client distributions (1 11-p) D)D, + pD for a shuffling parameter p E [0.1]. If = 0, the local data remains unchanged, and p 1, the data is uniform across clients.
We argued that in practice it might be infeasible to assume access to the distribution D. Instead, only approximation (e.g. syuthetic data) might be available, which denote by D. Accordingly, define Jang similarly as Assumption 2 but with g ~ D instead of & ~ D and define L similarly as Lavg but D. We denote the client distribution after shuffling by D, p)D; pD and quantify the data
4

---

Published in Transactions on Machine Learning Research (03/2024)
distribution differences by new parameter 8. Note that in an idealized scenario when D D; then ó 0. See Appendix A.1 for more details. Assumption 4 (distribution shift). We assume that there exists 82 2 0 such that Vx E Rd:
() fx(x D)) 8
We now characterize how shuffling p fraction of data to each client impacts the problem difficulty. For clarity, we will use the index p to denote how stochastic noise og gradient dissimilarity CB and the smoothness constant Lp can be estimated for the new distributions D. resulting after shuflling.
Lemma 1. If Assumption
i
A hold, then in expectation over potential randomness in selecting D:
E p < (1 p)o²² po + p(11-)< p)c² p(1ppppppp)
EG S (1 (1-p)
E 2 (1 Lman + +Laagg
Lemma shows the effective stochastic noise, gradient dissimilarity, and function smoothness when each client i contains a fraction p of shuffled data (sce Appendix A.1 for the proof). We observe that the gradient dissimilarity decays quadratically with respect to p. When = 1, the gradient dissimilarily 0 as expected, since data iid across workers. We also characterize the impact of the distribution shift from D to D on the effective stochastic noisc
We now demonstrate the impact of these parameters on the convergence rate of FedAvg. We assume that there are N clients. In each communication round, each client updates the received server model for т local steps using stochastic gradient descent (SGD). The updated model is then sent back to the server for aggregation, finishing one round of communication. We repeat this process for R rounds (See Algorithm II for more information). We state the convergence rate using the convergence bounds that are well-studied and established in Koloskova et al. (2020); Woodworth et al. (2020); Khaled al. (2020) and combining them with our Lemmall
Corollary I (Convergence rate after shuffling). We consider: p as the fraction of shuffled data on each client; T as local steps; under Assumption 1 4 for any target accuracy E > O, there erists (constant) stepsize such that the accuracy can be reached after at most T := R. iterations (in erpectation):
63
VL(TGo + VFop)
Lr
1
1
j-strongby-comwer: : T=
+
log
MNNe
MVEE
E
Lo2
L(TTr + VTōp)
LT
Non-conver: T O
+
Ne2
E312
From Corollary I that if 03 0, the convergence rate is asymptotically dominated by the first term, ie. o (NNe) which can be bounded by O (1I=)))²+0 + pp(l-p><3 +p(1 p)) This shows a mixed effect
Nue
between the stochastic noise, gradient dissimilarity, and the distribution shift. Shuffligg can have less of impact on the convergence in the high noise regime. When o² O, or in general in the early phases of the training (when the target accuracy is not too small), for problems where Lemma | holds, then the number of ilerations T to achieve accuracy e can be super-linearly reduced by factor larger than with the increasing ratio of the shuffled data as T' is proportional to &o and v vL, in expectation for strongly convex functions. We next present a numerical example to verify this.
2.3 Illustrative experiments on convex functions
We here formulate a quadratic example to vorify that our thcorctical results when we shuffic a fac- tion of the local data. Following! Koloskova el al. (2020). we consider a distributed least squares ob- jective f(x) == - E
Σラ= || 1 with Aij iId, μ, ~ ((d) and where x² controls the function similarity and o² controls the stochastic noise
2n,
bij of (id)
"matching parameters in Corollary [ We depict the influence of shuffling on the convergence in Fig. 2
In contrast. Koloskova et 2020: that consider the online setting, we generate here finite of samples on each client.
5

---

Published in Transactions on Machine Learning Research (03/2024)
(a) 2 10
(b) ~0: -²=0
10
D=0.0
D-0.0
In Fig. aa, we observe that in the high noise regime
(o² 1000), shuflling gives a smaller reduction on
Errot
p P-0.4
0=0.8
-NC 0=0.8
0.4
p=0.4
p=0.0
p=0.2
=0=000
the optimal error than when o² = In Fig. 2
10-5_
(b), we tune the stepsize to reach target accuracy
1.1 -10 with fewest rounds. Fig. 2 (b) shows that the empirical speedup matches the theoretical speedup as the observed and theoretical number of rounds (vertical bars) to reach are very close- however, only when we replace L in the theoretical bounds by Lp. This experiment shows that the prac- tical performance of Avg can depend on Ipp (note in this experiment D D). which hints that the pessimistic worst-case bounds from other works have applied in Cor. | can potentially be improved.
10
10a
102
10
102
Rounds
Figure 2: Convergence of |x= (a) With
a fixed ( and step size, shullling reduces the opti- mal error more when the stochastic noise is low (b) When gradient dissimilarity Ç² dominates the conver- gence, obtain super-linear speedup in the mum- ber of rounds to reach & by shuffling more data. The vertical bar shows the theoretical number of rounds lo reach e. The stepsize is luned in (b).
3 Synthetic data shuffling
We have theoretically and empirically verified the benefit of adding shuffled data to each client. However, collecting data from clients goes against the goal of protecting user rights in FL. To still enjoy the benefit of shuffling and alleviate information leakage, we propose a practical framework that shuffles aggregated and more interpretable synthetic images from all the clients (see Fig. 1 shifting the problem into one of assuring privacy the generator.
Algorithm I Fedssyn
A Algorithm II Federated Averaging (FedAvg)
1: procedure SYNTHETIC DATA GENERATION
1:
procedure FEDAVG
2: for client i= 1,,...,,NN N in parallel do
2: for ror.:1,..., do
3: sample p data points from D;
3: Sample clients S C (1,..,,
4: train a generulor G;
4: Send server model x all clients E for client i S in parallel do initialise local model y: +-x for k == 1, ......7 do y, + y, VVF()))
5: generate D; with ñ samples
6:
6:
Communicate D. to the server
6:
end for
7:
8: Server shuffles the aggregated synthetic data
8:
and split it to N parts ((D.:))
9:
end for
9:
Server distribudes Des ([D.il= = ū) to each client
10: end for
10: Run FL algorithm with the updated client dataset
11:
x 1 Exes
on each client D. = D. D...
12: end for
11:
end procedure
13:
end procedure
We denote the client dataset, client generated synthetic dataset, and shuffled synthetic dataset by D,, D; and D (in accordance with the notation for the data distributions in Sec. D. On each client i, we uniformly subsample p- n, data points from the local dataset D,, given p (0, 1] and n, [Dyl, which we use to locally train class-conditional generator. Using a subset rather than the entire dataset can alleviate the exposure of the class distribution from cach client. Given the trained local generator, we generate D, with [D, = n synthetic data, matching the class frequency in the subset. We assume that all the clients are willing to send their synthetic dataset to the server. The server then shuffles the aggregated synthetic datasets UsE[N], and distributes the data uniformly among the clients. In practice, when the number of synthetic data is large, their statistical dependency negligible, and the synthetic data can be considered nearly iid. Reflecting this, we denote the partilioned shuflled synthetic dataset as D.s on each client, and the proportion of the A synthetic dataset is calculated p nभ (see Algorithm I).
We then run FL algorithms with the updated dataset on each client D, Das. Our framework has no requirements for the FL algorithm, so we here briefly describe one of the most common FL algorithms: FedAvg (Konččný et al.) 20016). as shown in Algorithm II. FedAvg mainly has two steps: local model updating and server aggregating. We initialize the server with model x. In each communication round,
6

---

Published in Transactions on Machine Learning Research (03/2024)
each participating client S S updates (e-g.: K steps SGD). The updated model y; is then sent to the server. FedAvg calculates the server model by averaging over the received client models, finishing one round of communication. We repeat this for R rounds or until the target accuracy is achieved.
[N] receives copy of the server parameter x and performs K steps local
Advantages of sending synthetic data rather than a generator for one-round: 1) sending syn- thetic data can be more secure than sending the generator to the server since having access to generator's parameters gives the server more powerful attacking abilitics (Wang et al.) 2022b) 2) the clients can cas- ily inspect the information shared with the server as the syuthetic images are visually more interpretable than black-box generators 3) one-round synthetic data communication can be more secure than multi-round generalor/syytheete data transmission (Xiong et al., 2023 Zhu et al. 2021 as the server cannot infer the local data distribution by identifying the difference between the updated synthetic data 4) depending on the generator, sending synthetic data can incur less communication cost, for example, transmitting the syn- thetic data leads to a 2x-30x reduction on the number of paramcters communicated than transmitting the generator in our experiment.
4 Experimental setup
We show the effectiveness of our proposed method on CIFARIO and CIFAR100 (Krizhevsky 2009) image classification tasks. We partition the training datasct using Dirichlet distribution with concentration parameter to simulate the heterogeneous scenarios following Lin et al. (2020). Smaller a corresponds to higher data heterogeneity. We pick a E (0.01,0.1) as they are commonly used (Yu et al. 2022 Lin let al. 2020). Each client has a local dataset, kept fixed and local throughout the communication rounds. Experiments using MNIST and dSprites are in Appendix A.3.1 and A.4
We use class-conditional DDPM Ho et al. (2020) on each client. We assume that all the clients participate in training DDPM by using 75% of their local data as the training data. Each client trains DDPM with a learning rate of 0.0001, 1000 diffusion time steps, 256 batch size, and 500 epochs. These hyperparameters are the same for all experiments. Once the training finishes, each client simulates ń 50000 training images in CIFAR10 and CIFAR100) synthetic images with the label, which are then sent to the server. The server shuflles the aggregated synthetic data and then distributes it to each client equally.
N (there are 50K
We then perform federated optimization. We experiment with some of the popular FL algorithms including FedAvg (Končený et al. 2016). FodProx (Sahu et al. 2018), SCAFFOLD (Karimireddy et al.] 2020b), FedDyn (Acar al.] (021), ,, and FedPVR (Li et al.) 2022a)). We use VGG-11 for all the experiments. We train the FL algorithm with and without using the synthetic dataset to demonstrate the speedup obtained from using synthetic dataset quantitatively.
We use N E {10, 40, 100} as the number of clients and C E (0.1, 0.2, 0.4, as the participation rate. For partial participation, we randomly sample N C clients per communication round. We use a batch size of 256, 10 local epochs, and the number of gradient steps 256 We tune the learning rate from {0.01, 0.05, 0.1} with the local validation dataset. The results are given as an average of three repeated experiments with different random initializations. Note that the reported accuracy is calculated the real server test dataset.
10n,
5 Experimental results
We show the performance of Fedssyn here. Our main findings are: 1) Sampling shuffled synthetic data into each client can significantly reduce the number of rounds used to reach a larget accuracy (1.6x-23x) and increase the Top-1 accuracy. 2) Fedssyn can reduce the number of communicated parameters to reach the target accuracy up to 95% than vanilla FedAvg. 3) Fedssyn is more robust across different levels of data heterogeneity compared to other synthetic-data based approaches 4) The quantified gradient dissimilarity and stochastic noise in DNN match the theoretical statements
Improved communication efficioncy We first report the required number of communication rounds to reach the target accuracy in Table [ The length of the grey and red colour bar represents the required number of rounds to reach accuracy when the local dataset is D, and D, U D.,, respectively. The speedup
7

---

Published in Transactions on Machine Learning Research (03/2024)
is the ratio between the mumber of rounds in these two settings. We observe that adding shuffled synthetic data to each client can reduce the number of communication rounds to reach the target accuracy for all the cases. See Table A.1 for the actual number of rounds required to reach m-accuracy.
Table 1: The required number of rounds to reach larget accuracy m. m is chosen such that most of the FL algorithms can reach such accuracy within 100 rounds. The length of the grey and red bar equals to the number of rounds for experiments without the synthotic datasct (D:) and with the shuffled synthotic dataset (D; D..), respectively. We annotate the length of the red bar, and the speedup (x) is the ratio wet the number of rounds these two settings. ">" " means experiments with D; as the local data cannot reach accuracy m within 100 communication rounds. Using shuffled synthetic dataset reduces the required number of communication round to reach the target accuracy in all cases.
Full participation
Partial participation
N=10
N=10 (C=10%)
N= 10 (C=20%)
N=100 (C=10%)
a 0.01
a 0.1
a 0.01
a 0.1
a = 0.01
a = 0.1
0.01
= 0.1
CIFARIO
m 44%
m 66%
m 44%
In1 = 66%
m = 44%
m = 68%
m 44%
m 66%
FedAvg
4((2x)
8(8.5x)
1(> 25x)
8(5.6x)
12(8.3x) 3x)
21(2.8x0 8x))
19(4.9x)
38(>> 2.6x)
Staflold
((9.3xx)
76..1x)
5(> 20x)
10(2.6xx)
12(6.8x)
20(2. 7x)
19(> 5.3x)
31(277x))
FedProx
4(23.5xx)
8(5.3x)
1(> 26xx)
9(8.2x)
9(> 11.1x)
15(4.7x)
31(> 3.2x)
37(>> 2.7%)
Fyd
3(16.3x)
5(14.8x)
4(16.8x)
7(10.7x)
7(> 14.3x)
12(> 5.3x)
171> 5.9h)
31(> 8.2x)
FodPVR
3(19.3x)
7(4.3x)
4(> 26x)
8(9.5x)
10(8.5x)
21(2.8x)
21(> 4.8x)
35(> 2.9x)
CIFAR100
m
30%
m
40%
m
20%
20%
m 30%
mu 40%
m 30%
m 30%
FedAvg
15(5. 9x)
19(> 5.2x)
17(> 5.9x)
21(> 1.8x)
37(> 2.7x)
89(> 1.xx)
70(>> 1.4x)
50(>> 1.7x)
Staffold
14(2.9x)
19(2.9x)
15(3.6x)
21(1.8x)
24(> 4.2x)
71(> 144x)
61(1.6x)
52(>> 1.9x)
Pro
17((5.9x)
23(4.3x)
17(> 5.6x))
m
23(> 4.3x)
33(> 3.0x)
100 (-)
75(> 1.3x)
60(> 1.7x)
FodDya
10(3.6x)
12(5.5x)
13(> 7.7x)
15(6.7x)
25(> 4x)
78(> 1.3x)
61(> 1.6x)
60(> 1.7x)
FedPVR
14(6.1x)
19(2.0x)
15(> 6.6x)
20(5.0x)
23(> 4.3x))
59(> 1.7x)
71(> 1.4x)
58(> 1.7x)
Reduced communication cost Following Acar et al. 2021). we define the communication cost as the
total number of parameters communicated between the clients and the server to reach a target accuracy. Assune the size of the synthetic data is M, and the size of the FL model is Mo, then the communication cost is calculated as 2M, + 2RM,, where R is the number of rounds to reach the target accuracy as shown in Table [ In our experiment, M, is 2x-24x smaller than Me, together with the drastically reduced number of communication rounds as shown in Table 1 we can save the communication cost up to 95%. See Table A.2 in the Appendix for the communication cost.
Higher Top-1 accuracy To verify that the accuracy improvement is mainly due to the changes in the convergence parameters rather than the increased number of images on each elient, we compare experiments where the local dataset is D., the mixture between local real and local synthetic data D. U D,D,,, the mixture between local real and shuffled synthetic data D, U D.i-
In Fig. 3 we observe that using the shuffled synthetic data can significantly improve the Top-1 accuracy in nearly all the cases compared to other baselines, indicates that the vast performance improvement is mainly due to the changes in the parameters in the convergence rate. We see that adding local synthetic data can sometimes lower the accuracy (e.g. local+local synthetic in CIFARIO (a = 0.01)). This is primarily because the local synthetic data amplifies the heterogeneity further and makes it more challenging for an FL algorithm to converge. Additionally, the large jump from using local synthetic data when the number of clients is large (c.g. CIFAR100 with 100 elients) mainly because the incrcased number of data points per client can assist in local training. We observe a smaller performance improvement when the number of clients is large (N = 100) using Fedssyn, we can however further improve this by generating and shuffling more synthetic images.
Sensitivity analysis We here depict the sensitivity of FedAvg on the quality of the synthetic data using CIFAR1O in Fig. ! Fig. | (a) shows that the number of images for training DDPM has a substantial impact on FL performance, which reasonable, as we can acquire higher-quality synthetic images we use more images to train the generator. Fig. | (b) shows that when the number of clients is low, the synthetic images extracted from the early training checkpoints (E=50) already have high quality. However, when the number
8

---

Published in Transactions on Machine Learning Research (03/2024)
N N=10(C=100 1.0)
N=100CC0.4)
N=40(C=0.2)
N=100(C=0.1)
CIFAR1O (a=0.01)
0
CIFAR10 (a=0.1)
Accuracy
0
CiRARÍ00 (a=0.01)
0
CIFAR100 (a=0.1)
0
Avg Prox Scaf Dyn PVR Avg Prox Scaf Dyn PVR Avg Prox Scaf Dyn PVR Avg Prox Scaf Dyn PVR
Local
Local+Local Synthetic
Local+Shullle Shuflled Synthetic Central Synthetic Central Real
Figure 3: Top-1 accuracy. We compare the experiments where the local dataset is Di, (1 -1- p)D; + pD. Hoocll+local synthetic data), and (1 - p-p + pD,; (local+shuffled synthetic data). The black and green dotted lines represent the accuracy using the centralised real and synthetic data, respectively. Using shuflled synthetic data (red bar) boosts the Top-1 accuracy, and in some cases, even matches the centralised accuracy,
(a)
(b)
(c)
N=10
N=10
N=40
N=10
89
80
562
87
IID
80
Non-IID
85
NOn-IID
DDPM
1125
83
60
E-50
NDA
83
SOS accur
E-250
60
DGAN
pm
4500 3375 2250
83 84 84
E-450
DCTGAN
ByyeeAAN
79
40
40
MM M Mww
83 84
77
83
84
86 86
75
20
20
74
.60
0.10.20.5
2
x5000
25
50
0
25 50
20
40
60
Communication round
Figure 4: Sensitivity analysis using FedAvg and CIFARIO: (a) the influence of the number of images used for training the generator p- n- and the number synthetic images per client ñ (a = 0.1). We annotate the combination that performs better than the contralized bascline (b) influence of the number of training epochs for the generator with 10 and 40 clients (a=0.01). (c) the influence of using different. generators (a 0.01). We obtain better performance using DDPM than other generators.
of clients is high, the longer train the generator, the better FL performance we can achieve, i.e., obtain significantly better accuracy when train the generator for 450 epochs (E-450) than 50 epochs (E-50). Note, in our experimental setup, higher number of clients means [D,] is smaller as 50,000 where N is the number of clients. Fig. (c) shows that using DDPM is slightly better than GAN-based generators in terms of accuracy.
Comparison against other synthetic-data based approaches We compare Fedssyn (FefAvg+ synthetic data) with FodGEN (Zhu al.) (021) and DENSE (Zhang al. (0022) Table 2 We train
FedGEN and DENSE using the default hyperparameters described in Zhu et al. (202)) Zhang et al.
9

---

Published in Transactions on Machine Learning Research (03/2024)
2022). Following the setup in DENSE (Zhang et al.) 2022 use 10 clients with full participation, which is a commonly used FI, setup in the literature (Li et al. 2022a 2021 Yu et al. 2022 We can potentially improve the performance with more careful tuning. Comparably, Fedssyn achieves better Top-1 performance and is more robust against data heterogeneity levels. Compared to FedGEN which transmits the generator in every round, we only communicate the synthetic data once, which can be more secure and consume less cost. For example, we calculate the ratio between the required memory cost to reach the target accuracy (2M,-M,1R, for Fedssyn and FedGEN (last column in Table 2 with 2MM 2MM.+2M,, where Mg is the size of the generator (~ 1.2 1.4BB,, Rg and R are the number of round to reach the target accuracy using FedGEN and Fedssyn, respectively, and Mc- = 37.2MB the transmitted synthetic dala. We consume less communication cost than FedGEN reach the same level of the target accuracy.See Appendix A.2 for more information regarding the training details and Fig. A.1 for the accuracy over communication rounds.
the size of the classification model, M2 = 15.5MB the size of
Parameters in the convergence rate We investigate the impact of using shuffled synthetic data on the parameters in the convergence rate for DNN-based FedAvg in Fig. 5 We use CIFAR1O, 10 clients with full participation, a = 0.1. We observe that (1-p)o" dominates over other terms in the effective stochastic noise, which means the first term in the convergence rate for non-convex function in Corollary can be simplified as O p)ppr in this experimental setup. For Sg, the empirical result. also matches the theory. These results show that in this experimental setup, adding shuffled synthetic data reduces both stochastic noise and function dissimilarity, and lead to a greater accuracy improvement and vast reduction on the number of rounds to reach the target accuracy. See Appendix A.3.5) for more information.
Fedssyn
FedGEN DENSE
MPndaayn MESIGEN
102
pla?
CIFARIO (a=0.01)
83.0 (4) 47.6 (70) 15.2 (-)
6%
R2
CIFAR1O (a=0.1) 84.1
(8) 78.6 (17) 40.1 (-)
49%
100
p(1 pk
p²
(1
=p??
CIFAR100 (a=0.01) 52.0
(15) 35.1 (52) 10.3 (-)
29%
P(1
CIFAR100 (a=0.1) 54.4 (19) 41.0 (84) 13.5
23%
20
40
60
20
40
60
Communication rounds
Top-1 accuracy (number of rounds to reach tar- get accuracy m in parentheses), and the ratio between the memory cost to reach m. We obtain higher Top-1 accuracy and require lower memory cost compared to other synthetic data-based methods to reach accuracy m.
Table 2:
Figure 5: The empirical observation of stochas- tic noise and gradient dissimilarity matches the theoretical statement (experiment. using CI- FAR10, 10 clients, a = 0.1, p-0.06)
Practical implications Our proposed framework Fedssyn is more suitable for applications such as discase diagnosis and explosives detection that usually require high precision and clients have enough computation resources seeing that Fedssyn can even reach the centralized accuracy in some of the high data heterogeneily scenarios and the saved communication cost is enormous (up to 95%). Suppose the client is resource- constraint, a good strategy is to start with generating fewer synthetic images since shuffling even a small percentage (e.g. p=0.06) of the synthetic images into each client can already improve the Top-1 accuracy by 14%-20% (Fig. and a larger p usually corresponds to a better accuracy until saturates, e.g. reach the iid accuracy. Additionally, the client has the option of checking the synthetic images and only sharing the less sensitive synthetic images to the server to alleviate the information leakage.
Limitations Training the generator locally may pose a computation requirement for each device. We can mitigate this issue with methods such as quantization (Alistarh et al. 2016) and compression (Li et al. 2020 Mishchenko et al.) 2019). Sending the synthetic images may also leak the training data distribution. One possible solution to improve the utility of Fedssyn is to make the generator differential private Yoon et al. (2021 2019); Abadi et al. (016)). We next provide a small-scale experiment that illustrates the performance of Fedssyn when the generator is differentially private given EDP = 10 (Abadi el. al. 2016 Dockhorn et. al.
2022
10

---

Published in Transactions on Machine Learning Research (03/2024)
6 Towards differentially private Fedssyn
We have shown the benefits of Fedssyn on top of multiple FL algorithms and across different. datasets. However, sending synthetic data to the server may cause a certain level of privacy leakage. To address this issue, we train the data generator differentially private so that the shared synthetic images are privacy- friendly and are respecting the rigorous DP guarantee.
Specifically, we train the diffusion model with rigorous DP guarantees based on DP-SGD (Abadi et al. 2016) by clipping and adding noise to the gradients during training. Following Dockhorn et al. 2022). we train the DP-DDPM for 500 epochs under the private setting (EDP = 10, 5 = Le 5) with the noise multiplier as 1.906 and clipping threshold 1.0 based on Opacus (Yousefpour et al. 2021 on each client. We use CIFAR10, ten clients with full client participation, and a = 0.1. We show the incurred privacy cost, examples of synthetic images, and the corresponding lederated learning performance Fig.
B
See Fig. A.6 for the performance
of using SCAFFOLD as the baseline federated learning algorithm.
Privacy cost
Epoch=50
Server accuracy
8
0.6
#poch=499
0.4
Vaniall FedAvg
0.2
+synthelic data, 550 +synthetic E-ta,
+synthelic data, E=4
0
200
400
20
40
60
80
Training epochs (DP-DDPM)
Generated synthetic images
Communication round
Figure 6: Performance of differentially private Fedssyn. From left to right, we show the privacy cost for training the differentially private DDPM, examples of synthetic images generated from two model check- points (annotated by dots in the left figure), and the corresponding federated learning performance. Shuffling differentially private synthetic images to each client can accelerate the convergence and improve the perfor- mance of vanilla FedAvg when the clients are heterogeneous in this experiment.
We observe that as the training of DP-DDPM progresses, the privacy cost increases. We then generate the synthotic images using three model checkpoints from different training stages (50 epochs, 250 epochs, and 499 epochs) on each client to illustrate the influence of the quality of the synthetic images on the performance of Fedssyn. Some example synthetic images are shown the middle of Fig. 6 We can see that the synthetic images are distorted and more privacy-friendly. We then aggregate, shufile, and distribute these synthetic images back to the clients and train Fedssyn following the procedure described in section 4. We observe that shuffling privacyy synthetic data, which are generated by the DDPM trained under the privacy budget CDp = 10, can accelerate convergence and improve accuracy compared to vanilla FedAvg. Different privacy budget and number of training images for training the DDPM can result in a different convergence behaviour. More extensive and fine grained experiments are needed to fully address this challenge. We leave this as our future work.
7 Conclusion
In this paper, we have rigorously analyzed the relation between data heterogeneity and the parameters in the convergence rate in FedAvg under standard stochastic noise and gradient dissimilarity assumptions. While previous works usually qualitatively represent data heterogeneity with gradient dissimilarity, we proposod a more quantifiable and precise characterization of how the changes in the data heterogeneity impact the parameters in the convergence rate using shuffling.
11

---

Published in Transactions on Machine Learning Research (03/2024)
Our work paves the way for better understanding of the seemingly unreasonable effect of data heterogeneity in FT. The theoretical findings inspired us to present more practical framework, which shuffles locally generated synthetic data, achieving nearly as good performance as centralized learning, even in some cases when the data heterogencity is high. Our work reveals the importance of data distribution matching in FL, opening up future research directions.
Reproducibility Statement
We provide downloadable source code as part of the supplementary material. This code allows to reproduce our experimental evaluations show in the main part of the manuscript. The code for the additional verification on the dSprites dataset in Appendix A.4 is not part of the submitted file. We will make this code and the available on a public github repository.
genenerated datasets (such as in Figure A.10
Acknowledgement
Bo Li, Mikkel N. Schmidt, and Tommy S. Alstrom thank for financial support from the European Union's Horizon 2020 research and innovation programme under grant agreement no. 883390 (H2020-SU-SECU- 2019 SERSing Project). Sebastian Stich thanks for partial financial support from Meta Privacy Enhancing Technologies Research Award 2022. Bo Li thanks for the financial support from the Otto Mensted Foundation and appreciates the discussion with Xiaowen Jiang.
References
Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Πyya Mironov, Kunal Talwar, and Li Zhang, Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 308-318, 2016.
Durmus Alp Emre Acar, Yue Zhao, Ramon Matas Navarro, Matthew Mattina, Paul N. Whatmough, and Venkatesh Saligrama. Federated learning based on dynamic regularivation. In 9th International Conference on Learning Representattins, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021.
URL http::///ppaaaeeeeeeeo////e/etta
Dan Alistarh, Jerry Li, Ryota Tomioka, and Milan Vojnovic. QSGD: randomized quantization for communiestion-opiinnnal stochastic gradient descent. CoRR, abs/1610.02132, 2016. URI. http://
ardivorrg/ab//1110002122
Christopher P. Burgess, Irina Higgins, Arka Pal, Loic Malthey, Nick Watters, Guillaume Desjardins, and Alexander Lerchner. Understanding disentangling in beta-vae, 2018. URL https://arriv.rrgabbb.
1804.03599
Dingfan Chen, Tribhuvanesh Orekondy, and Mario Fritz. GS-WGAN: A gradient-sanitized approach for learning differentially private generators. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Balcan, and Hsuan-Tien Lin (eds.). Advances in Neural Information Pro- cessing Systems 33: Annual Conference on Newral Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. URL htttp:://proceeeee hetp://s...uuipppccc/p//////0000 hash/////hhha//////// ABWFaabb551220777rc/77111122222
Hadsell,
Liam Collins, Hamod Hassani, Aryan Mokhtari, and Sanjay Shakkottai. Fodavg with fine tuning: Local updates lead to representation learning. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advonces in Neural Information Processing Systems, 2022. URL https:///penreviee..ne//
forum
Tim Dockhorn, Tianshi Cao, Arash Vahdat, and Karsten Kreis. Differentially Private Diffusion Models. urXin:2210.09922 2022.
12

---

Published in Transactions on Machine Learning Research (03/2024)
Jack Goetz and Ambuj Tewari. Federated learning via synthetic data. CoRR, abs/2008.04489, 2020. URL
https://arxiv.org/ www.://rgg//.//.....00000 2048804499
Tan Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger (eds.), Advances in Newral Information Processing Systems, vol- umee 27. Curran Associates, Inc., 2014. URL httes///pooedliggooooo//ccccpppp Ga22901220111106444777711.cc..
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016, Los Vegas, NV, USA, June 27-30, 2016, pp. 770-77 778. TEFE Computer Society, 2016. doi: 10.1 10.1109/CVPR.201.000 URL
Jonathan Ho, Ajay Jain, and Picter Abbeel. Denoising diffusion probabilistic models. arXiv preprint aroiv:2006. 1 11239, 2020.
Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista A. Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. L. D'Oliveira, Salim EI Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaïd Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konečný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateek 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, Praneeth Vepakomma, Jianyu Wang, Li Xiong, Zheng Xu, Qiang Yang, Felix X. Yu, Han Yu, and Sen Zhao. Advances and open problems in federated learning. CoRR, abs//bl2//00 11912.04977, 2019. URL http://arxxivoor/ abs/ abs/1912.04977
Sai Praneeth Karimireddy, Martin Jaggi, Salyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian U. Stich, and Ananda Theertha Suresh. Mime: Mimicking centralized stochastic algorithms in federated learning. CoRR, ////20008.00006 2020a. URL https://aarx....rg//aatttt
03606
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. SCAFFOLD: Stochastic controlled averaging for federated learning. In Hal Daumé III and Aarti Singh (ods.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 5132 5143. PMLR, 13 18 Jul 2020b. URL
Tero Karras, Miika Aittala, Janne Hellsten, Samuli Laine, Jaakko Lehtinen, and Timo Aila. Train- ing generative adversarial networks with limited data. CoRR, abs/2006.06676, 2020. URL https:
//axxvvorrg/ba//000000666
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Better communication complexity for local SGD. CoRR, abs/ 111110999444444 2019. URL http:://arrivvorr/bb//19999 04746)
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárík. Tighter theory for local sgd on identical and heterogeneous data. In International Conference on Artificial Intelligence and Statistics, pp. 4519 4529. PMLR, 2020.
Diederik P. Kingma and Max Welling, Auto-encoding variational bayes. CoRR, abs/1312.6114, 2013.
Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian Stich. A unified the- ory of decentralized SGD with changing topology and local updates. In Hal Daumé III and Aarti Singh (ods.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 5381-5393. PMLR, 13-18 Jul 2020. URL https: (/poceaiigglllpppee////////oooop
13

---

Published in Transactions on Machine Learning Research (03/2024)
Jakub Konečný, H. Brendan McMahan, Daniel Ramage, and Peter Richtárik. Federated optimization: Distributed machine learning for on-device intelligence. CoRR, abs/1610.02527, 2016. URL. http://
axxiv.org/abs/111000022
Alex Krizhevsky. Learning multiple layers of features from tiny images. 2009.
Bo Li, Mikkel N. Schmidt, Tommy S. Alstrom, and Sebastian U. Stich. Partial variance reduction improves non-convex federated learning heterogeneous data. CoRR, abs/2212.02191, 2022a. doi: 10.48550/ URL https:: httpp:///di.org// www.0///r....2222...rr
Qinbin Li, Bingsheng He, and Dawn Song. Model-contrastive federated learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pottern Recognition, 2021.
Zhize Li, Dmitry Kovalev, Xun Qian, and Peter Richtárik. Acceleration for compressed gradient descent in distributed and federated optimization. In Proceedings of the 37th International Conference Machine Learning, TCML, 2020, 13-18 July 2020, Virlual Evenl, volume 119 of Proceediiggs of Machine Learning Research, pp. 5895 5904. PMLR, 2020. URL
Zijian Li, Jiawei Shao, Yuyi Mao, Jessie Hui Wang, and Jun Zhang. Federated learning with GAN-based data synthesis for non-IID clients, 2022b. URL httpgs///ppppoerrrss.sss///rr/sp
Tao Lin, Lingjing Kong, Sebastian U. Stich, and Martin Jaggi. Ensemble distillation for ro- bust model fusion in federated learning. In Hugo Larochelle, Marc'Aurelio Ranzato, Raia Had- sell, Maria-Florina Balcan, and Hsuan-Tien Lin (ods.), Advances in Newral Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. URL http:///ppoooodggggguouoocc/pppp
Mi Luo, Fei Chen, D. Hu, Yifan Zhang, Jian Liang, and Jiashi Feng. No fear of heterogeneity: Classifier calibration for federated learning with non-iid data. In Neural Information Processing Systems, 2021.
Loic Matthey Irina Higgins, Demis Hassabis, and Alexander Lerchner. dsprites: Disentanglement testing 2017.
sprites dataset. https///ggthabcccoo////ennnn/n/ wwwp///eeimdspppreedeeeeeem
com
H. B. McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera y Arcas. Communication- efficient learning of deep networks from decentralized data. In International Conference Artificial Intelligence and Statistics, 2016.
H. Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. In International Conference on Learning Represenlations, 2018. URL
Konstantin Mishchenko, Eduard Gorbunov, Martin Takác, and Peter Richtárik. Distributed learning with compressed gradient differences. CoRR, abs/1901 0tt//9901.09263 2019. URL http://aaxx....r////aaaa/////// abt///00.009/99
Aritra Mitra, Rayana Jaafar, George J. Pappas, and Hamed Hassani. Lincar convergence in federated Iearn- ing: Tackling client. heterogeneily and sparse gradients. In M. Ranzalo, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neurol Information Processing Systems, volume 34, pp. 14606-14619. Curran Associates, Inc., 2021. URL .ddf.
2021/ wttp:eeeedding...nuuipreeeeeeeee
Sashank J. Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and H. Brendan McMahan. Adaptive federated optimization. CoRR, abs/ hos/22033.0225, 2020. URL
Anit Kumar Sahu, Tian Li, Maziar Sanjabi, Manzil Zaheor, Amoet Talwalkar, and Virginia Smith. On the convergence of federated optimization in heterogencous networks. CoRR, abs/1812.06127,, 2018. URL http://aaxx.vorr//hha//111....1
14

---

Published in Transactions on Machine Learning Research (03/2024)
Tim Salimans, Ian Goodfellow, Wojeiech Zaremba, Vicki Cheung, Alec Radford, Xi Chen, and Xi Chen. Improved techniques for training gans. In D. Lee, M. Sugiyama, U. Luxburg, 1. Guyon, and R. Garnett (eds.), Advances in Neural Information Processing Systems, vol- ume 29. Curran Associates, Inc., 2016. URL aa30aaar992222276666600006677779
Vikash Sehwag, Saeed Mahloujifar, Tinashe Handina, Sihui Dai, Chong Xiang, Mung Chiang, and Prateek Mittal. Robust learning meets generative models: Can proxy distributions improve adversarial robust- noss? In International Conference on Learning Representations, 2022. URL httpss://pperrevie..nt forum VWVVVVVENV
Micah J. Sheller, Brandon Edwards, G. Anthony Reina, Jason Martin, Sarthak Pati, Aikaterini Kotrotsou, Mikhail Milchenko, Weilin Xu, Damiel Marcus, Rivka R. Colen, and Spyridon Bakas. Federated learning in medicine: facilitating multi-institational collaborations without sharing patient data. Scientific Reports, 10 (1):12598, Jul 2020. ISSN 2045-2322. doi: 0011088/$4199. 000-008502206605--1111 URL http:::/ddol.org/1010030 841598--00-69950-11
Reza Shokri and Vitaly Shmatikov. Privacy-preservine deep learning. In Proceedings of the 22nd ACM SIGSAC Conference on Compuler and Communications Securily, CCS '15, pp. 1310-1321, New York, NY, USA, 2015. Association for Computing Machinery. ISBN 9781450338325. doi: 211145//81000322813666 URL http:::/dbb..rgg/0.04445////////
2813687
Ashish Shrivastava, Tomas Pfister, Oncel Tuzel, Josh Susskind, Wenda Wang, and Russell Webb. Learning from simulateddeddeeeeeeeeea and unsupervised images through adversarial training. CoRR, abs/1612.00 abs/1612.07828, 2016. URL
http://aax.v..rrr/a////112222.
Abhishek Sinha, Kumar Ayush, Jiaming Song, Burak Uzkent, Hongxia Jin, and Stefano Ermon. Negative
data augmentation. In International Conference. on Learning Representations, 2021. URL https://
Sebastian U. Stich. Unified optimal analysis of the (stochastic) gradient method. CoRR, abs/ 1907.04232, 2019. URL http:///axxii.oorgaa//////...../
Hui-Po Wang, Dingfan Chen, Raouf Kerkouche, and Mario Fritz. Fed-gloss-dp: Federated, global learning using synthetic sets with record level differential privacy. ar preprint urXiw:2302.011 010668 2023.
Jianyu Wang, Qinghma Liu, Hao Liang, Gauri Joshi, and H. Vincent Poor. Tackling the objective in- consistency problem in heterogeneous federated optimization. CoRR, abs/2007.07450) 2020. URL
.07481
Jianyu Wang, Zachary Charles, Zheng Xu, Gauri Joshi, H. Brendan McMahan, Blaise Agüera y Arcas, Maruan Al-Shedivat, Galen Andrew, Salman Avestimchr, Katharine Daly, Deepesh Data, Suhas N. Dig- gavi, Hubert Eichner, Advait Gadhikar, Zachary Garrett, Antonious M. Girgis, Filip Hanzely, Andrew Hard, Chaoyang He, Samuel Horváth, Zhouyuan Huo, Alex Ingerman, Martin Jaggi, Tara. Javidi, Pe- ter Kairouz, Satyen Kale, Sai Praneeth Karimireddy, Jakub Konečný, Sanmi Koyejo, Tian Li, Luyang Liu, Mehryar Mohri, Hang Qi, Sashank J. Reddi, Peter Richtárik, Karan Singhal, Virginia Smith, Mahdi Soltanolkotabi, Weikang Song, Ananda Theertha Suresh, Sebastian U. Stich, Ameet Talwalkar, Hongyi Wang, Blake E. Woodworth, Shanshan Wu, Felix X. Yu, Honglin Yuan, Manzil Zaheer, Mi Zhang, Tong Zhang, Chunxiang Zheng, Chen Zhu, and Wennan Zhu. A field guide to federated oplimization. CoRR, abs/2207..00 2617006777. 2021. URL
Jianyu Wang, Rudrajit Das, Gauri Joshi, Satyen Kale, Zheng Xu, and Tong Zhang. On the unreasonable effectiveness of federated averaging with heterogeneous data, 2022a.
Yixiang Wang, Jiqiang Liu, Xiaolin Chang, Ricardo J. Rodríguez, and Jianhua Wang. Di-aa: An inter- pretable whito-box attack for fooling deep neural networks. Information Sciences, 610:14-32, 2022b. ISSN 0020-0255. doi: https///d..ogg//..000////.i sciaree/Arrtcce///////0002222222
URL ttpp:://ww..cienodddrrcttt..
15

---

Published in Transactions on Machine Learning Research (03/2024)
Blake E Woodworth, Kumar Kshitij Patel, and Nati Srebro. Minibatch local sgd for het- erogeneous distributed learning. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and Н. Lin (eds.), Advances in Newral Information Processing Systems, volume 33, pp. 6281 6292. Cur- ran Associates, Inc., 2020. URL
http:///aaapppeeeeee/e//r/////// Filee//paper/2222//11.
457 45713f6Ff204133fffeee 10715566700135511a77778888-----2 pdf
Liyang Xie, Kaixiang Lin, Shu Wang, Fei Wang, and Jiayu Zhou. Differentially privale generative adversarial network. CoRR, abs/1802.06633 2018. URL http://azxx...rrr//////10..0.0
Yuanhao Xiong, Ruochen Wang, Minhao Cheng, Felix Yu, and Cho-Jui Hsieh. FedDM: Tterative distribution
matching for communictiion-efficeeett federated learning, 2023. TTt./heppe///peeeeeeeeeea//rrorr
4ORNVZSoCQD
Jinsung Yoon, James Jordon, and Mihacla van der Schaar. PATE-GAN: Generating synthetic data with
differential privacy guarantees. In International Conference on Learning Represenlations, 2019. URL
Tehrim Yoon, Sumin Shin, Sung Ju Hwang, and Eunho Yang. Fedmix: Approximation of mixup under mean augmented federated learning. In International Conference on Learning Representations, 2021.
URL http::///pppaaaeee.eeseeeses//ep
Ashkan Yousefpour, Igor Shilov, Alexandre Sablayrolles, Davide Testuggine, Karthik Prasad, Mani Malek, John Nguyen, Sayan Ghosh, Akash Bharadwaj, Jessica Zhao, Graham Cormode, and Ilya Mironov. Opa- cus: User-friendly differential privacy library in PyTorch. arXiv preprint Xiv:20109. 1 12298, 2021.
Yaodong Yu, Alexander Wei, Sai Praneeth Karimireddy, Yi Ma, and Michael Jordan. TCT: Convexifying federated learning using bootstrapped neural tangent kernels. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (ods.), Advances in Neural Information Processing Systems, 2022. URL
htttp:://openevvies fortt/formm?m ddd
Jie Zhang, Chen Chen, Bo Li, Lingjuan Lyu, Shuang WU, Shouhong Ding, Chunhua Shen, and Chao Wu. DENSE: Data-free one-shot federated learning. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL https:
Shengyu Zhao, Zhijian Liu, Ji Lin, Jun-Yan Zhu, and Song Han. Diffeeenntabllcc for data-cfficient GAN training. CoRR, abs/ /22//22000..3. 2020. URL http:://aarrdi.orrr/bb////0..113
Yue Zhao, Meng Li, Liangzhen Lai, Naveen Suda, Damon Civin, and Vikas Chandra. Federated learning with non-iid data. arXio preprint 1rX6x:186.. 00582, 2018.
Zhuangdi Zhu, Junyuan Hong, and Jiayu Zhou. Data-free knowledge distilaaoo for heterogeneous federated learning. CoRR, abs/2105.1000 10056, 2021. URL https///aarxk.oorr//////11.0...0
16

---

Published in Transactions on Machine Learning Research (03/2024)
A
Appendix
We first provide the proof for the lemma. We then show the comparison with other synthetic-data based works. Following that, we show the extra experimental details and experimental results on two other dataset MNIST and dSprites.
A.1 Proof
We study the distributed stochastic optimization problem:
f(x, D) == (gwD[[((xx E)), f() == (F
where & can be a random data point or a random function, D; denotes the distribution of & on client i and D denotes the distribution of & over all the clients.
We argue that is possibly not be feasible to assume access to the distribution D as collecting data from clients goes against the goal of protecting privacy in federated learning. Instead, (c.g. synthetic data) D for carrying out the proof. We will demonstrate the impact of the difference between DD and D in the following sections.
approximation
Given the effective data D, D on each client we can formulate the optimization problem as:
F(x, ~ D(UD))) == F(x,8~ D, b= 0) [ 1)
with probability 1-p
(A.1)
with probability
where a random variable that indicates where a data point is drawn from. When b (with probability 1-p), p), we assume that we draw from a worker's own data D,. When b (with probability p), we assume that draw from the uniform distribution D. Take the expectation with respect to b, we have:
F(x. ~ Dj D.DD) Eo(F(x, = (1 F)x, Dj) + pF(x ~ D
(A.2a)
f(x.D,UD) EE. (x, {)] = -1- p)) [x f + pk [(xx E)
(A.2b)
-1- D.) pff(x,
D(x,DUD) = E.- [((x {)] = (1 - E>E [x, {) + + PB (F(x
(A.2c)
p)) D) + D)(
Lemma A-1 (variance with probability). If the random variable X is discrete with each element appearing with a probability Pt such that p(r;) = Pi, then:
n pal n11 1 == n
E X 1112
p.
Lemma A-2 (shuffled gradient dissimilarity). If Assumption 1 holds, then Vx Rd:
2 = =/V//(X D. DDD DU 2)II < (1-
where here the expectation is taken over a random inder E [N].
Proof. Given the definition from Eq. A.2 we have:
23 = -/XX,U
(T= - -1--)))(((xxxx,x//) -11-)=>>>>// D) - (x
(A.3)
s <(1-p)
17

---

Published in Transactions on Machine Learning Research (03/2024)
Lemma A-3 (shuffled stochastic noise). If Assumption
1
2
and hold and let dang being the stochastic then VX E R.d, we have:
noise from using D such that Bg=Dl BgnD|IVF( [VF( () f(x, D)
anga
0z = D (F [V((
V/(x, D, || 2 p)o² + po pp(1-))lVf[e
D)1lV Vfx (()
E $ (1 - pp + poo ang + p(1 pp5² + pp)
Proof. Based on the definition in Eq. A. 2
we have:
og BB 5) (x D; U 1
(1 p) BE (F) - V DDIII tp RD D;
We use Lemma A-1 in the last equality. We next give the bound for Ai and A2.
A : = EEWD, [V((x {) - Vf(x, V D.) - Vf(x, D, U D112
EE-D, (x <) - Vʃ(x, +IV//// D.) Vf(x, D: U 1
< 0² + [V D:) - (1
D111
$ o²² + p" Vx D2) - ff1x,,)11
Similarly, we can bound A₂ as:
A : = D (x {) Vf(x,
= BE [F <) - Tf(x [IV Vf(x U D)I
S avg + +|V/ D) - (1 - ())())(x (x) - px D2
avg + - 11 D,) - ff((x,)]'
Taking the bound for Ai and A back the expression of p. we have:
o < (1 p)o² + poa.g + +(1 v)1lV5(xx D)]
If we take the expectation w.r.t the clients for both sides, we then have:
E El < (1 p)o² + po + p(1 p) D:) - vf(x, 12
= (1 - p)o² + 2o + p(1 /) D.) - Vf(x, D) + D) V D)12 D)11
= (1 p)o² + avg
avg + p(1 /) D.) - Vf(x D) -|//-//-pp>///x>//>>>/-//>/>/>>>
D) ffxx (A.4)
< (1 p)o² 1o + p(1 r² + r(1 /)/ D) D)x
< (1 o) po avg + p(1 - 2)<² + p(1 p)8²
The inequalities use the Assumption 1 and 4 Df = D, then 82 = 0 by definition. We can then rewrite the bound for the stochastic noise as Elo v (1
o)o² + po + p(1 p)c²
Lemma A-4 (shullled smoothness)). Let Limax and Long denole the marimum and average smoolhness, i.e. it holds
VV)( vf(y, D:)1 < Lmax ||x - -ll
Vx, E Rd [r),
and and
|V D) V FfyyDD)l S Lavy |x-xxl
Vx,y e Rd.
V D)
Vfly, Vf(y,D\l|= s Lavy ||x yll
Vx,y e Rd
Then we have:
EL, S (1 Tmmax + pLeany
where Elyp denotes an upper bound on the smoothness constant. of f(x, D, UD)
18

---

Published in Transactions on Machine Learning Research (03/2024)
Proof. Given the client index i, by definition, we have fxx, D, = (1- - + px((x:)
(V V [I(1 P.) + V
= - p) - (2 vf(y; D))
S (1 p)l Vx,, -/ll -V((; D)
Σ ((1 p) Lmmxx + pplaag ||x y -
A.2 Extra related work comparison
Experimental details for replicating the FedGEN and DENSE results For FodGEN, we follow the default hyperparameter setup described in the paper Zhu et al. (021 | and the official repository. We tune the optimal stepsize from {0.05, 0.1, 0.2]. We run FedGEN for 100 communication rounds and report the final Top-1 accuracy using the server model on the test dataset. For DENSE, we follow the hyperparameter setup as described in the paper Zhang et al. (022) and the official GitHub repository. We have tried our best to improve the quality of the server model obtained after one round of communication as have done in Zhang et al. (2022). However, we still observe that such server model is not sufficiently good for the global distillatonn learning, especially when the data heterogeneity is high (a = 0.01). Therefore, we performed ten rounds of communication and then used the server model for global distillation learning. We can possibly improve the performance of FedGEN and DENSE with more careful tuning of the random seeds and other hyperparameters.
cilar10
cifar100
0.8
0.5
0.7
0.4
Test accuracy
0.6
I syytheee data (a=0.01)
0.5
FedGEN (a=0.01)..............
0.3
syathit data (a=0.10)
0.4
FedGEN (a=0.10)
0.2
0.3
FodAAg+syatthe data (a=0.01)
FedGEN (a=0.01)
0.2
FedAvg+ data 0.10)
FedGEN (a=0.10)
0.1
0
20
40
60
80
20
40
60
80
Communication round
Communication round
Figure A.1: Test accuracy for two methods FedAvg + synthetic data and FedGEN. FedGGE..Copaarblly our proposed method reaches to better test accuracy faster than FedGEN, The unstable performance of when a 0.01 CIFAR10 datasct using FodGEN can be potentially improved with more careful hyperparameter tuning.
Experimental details for replicating the FedDM results For FedDM Xiong et al. 2023 we follow the hyperparameter setup as described in the paper Xiong et al. (2023) and also the downloadable supplementary file from?] We choose the non-differentially private FedDM with ten clients. We run the experiment on the CIFAR10 datasct with a being 0.01 and 0.1. We use the same classification model VGG-11 as in experiment. We run each experiment two times with different initializations and report the averaged test accuracy. Note that we can possibly improve the performance of FedDM using a different classification model.
In Fig. A.2 we observe that FedDM initially outperfomms our approach. However, as training progresses, our method demonstrates a significant. improvement over FedDM. Additionally, FedDM seems more robust against different levels of data heterogeneity as the test accuracy gap between when a 0.01 and 0.1 is
19

---

Published in Transactions on Machine Learning Research (03/2024)
small. Comparably, method needs to communicate 30,070 MB of parameters (over 40 rounds), whereas FedDM only needs to communicate 22,508 MB of parameters (over 30 rounds, with each round transmitting around 750 MB of parameters) between the client and the server to achieve a stabilized test accuracy.
cifar10
0.8
0.7
accuracy
0.5
0.4
0.3
syathett data (a=0.01)....
FedDM (a=0.01)
0.2
syatheti data 0.10010)
FedDM (a- 0.10)
0.1
0
10
15
20
25
30
35
40
Communication round
Figure A.2: Test accuracy for two methods FedAvg + synthetic data and FedDM. Comparably, FedDM performs better than our approach at the beginning. However, as the communication round increases, our method performs significantly better than FedDM. FedDM is more robust against different levels of data heterogeneity, seeing that the test accuracy gap between different levels of data heterogencity small.
A.3 Extra experimental details
Table A.1: Extension of Table 1 The required number of communication rounds for Fedssyn (for vanilla FL algorithms) to reach the target accuracy is chosen that most FL algorithms get such accuracy within 100 communication rounds. The numbers in the parenthesos represent the number of rounds required for the vanilla FL algorithms to reach m-accuracy.
Full participation
Partial participation
N=10
N=10
(C=40%)
N=40
(C=20%
N=100
(C=10%)
0.01
0.1
0.01
0.1
0.01
0.1
0.01
0.1
CIFAR10
m=44%
m=66%
m=44%
m=66%
m=44%
m=66%
m=44%
m=66%
FedAvg
(88)
(68)
4 (>100)
8 (45)
12 (100)
21 (59)
19 (93)
38 (> 100)
Scaffold
(37)
(43)
(0100)
10 (26)
12 (82)
20 (54)
19 (>100)
31 (84)
FedProx
(94)
(43)
4 (>100)
9 (74)
9 (>100)
15 (71)
31 (>~100)
37 (>100)
FedDyn
(49)
5 (74)
4 (67)
7 (75)
7 (>>100
12 (>100)
17 (>1100
31 (>100)
FodPVR
(58)
(30)
4 (>100)
8 (76)
10 (85)
(59)
(>100)
35 (>100)
CIFAR100
m=30%
40%
m=20%
m=20%
m=30%
m=40%
m=30%
m=30%
FedAvg
15 (89)
19 (> (>100)
17 (>100)
21 (>=100)
37 (>100)
89 (>=10)
70 (>100)
59 (>100)
Scaffold
14 (41)
19 (55)
15 (54)
21 (100)
24 (>100)
71 (>100)
61 (100)
52 (>100)
FedProx
17 (100)
23 (99)
(>100)
23 (>-100)
33 (>100)
>100 (-)
75 (>-10)
60 (>110)
FedDyn
10 (36)
12 (66)
13 (>100)
15 (100)
25 (>100)
78 (>100)
61 (>100)
60 (>100)
FedPVR
14 (85)
19 (38)
15 (>100)
20 (100)
23 (>100)
59 (>100)
71 (>100)
58 (>100)
20

---

Published in Transactions on Machine Learning Research (03/2024)
A.3.1 Experimental results on MNIST dataset
We consider a distributed multi-class classification problem on MNIST dataset given (Ai, by) as the dataset on worker with:
y; softmax(A(x)), A; ~ R X R 784x10
.Y. E IR
(A.5a)
1
f(() =
Σ
bigk log(y;z)))
(A.5b)
74
10
We construct the training dataset by subsampling 1024 images from each class from the MNIST training dataset. We use the test dataset to evaluate the performance of the server model (10000 images). We consider two scenarios for splitting the dataset across workers: 1) iid, where each worker has a similar number of images across classes 2) split by class, where each worker can only see images from a single class. We set 10 workers, and each worker has 1024 images n, = 1024. We experiment with a different number of local epochs E on cach worker and shuffling percentage p. For a given p. we subsample n&p data points randomly from each worker and allocate them in D. We then shuflle D and distribute it equally to all workers such that each worker has n.p shuffled data points and n₂ -p) local data points. We choose to control the stochastic noise 6² by adding Gaussian noise to every gradient:
Yi y (V + +8,,
~~ N(0,
(A.6)
784
Split by class E=2
IID
E=1
E=5
E=1
E=2
E=5
P=0
1.0
0.5
Loss
2=10
0=0.0p=00
1.0
1=
p 0.2p 0.5
0.5
10"
101
10
10
10
10
10
10
10a
101
10
10
Communication round
Figure A.3: Test loss using the model communication rounds. When the dataset is IID across workers, adding shuflled dataset does not influence the learning speed. However, when workers have hetero- geneous datasets (split by class), shuffling small percentage of the dataset can improve the convergence speed, especially when the number of local epochs is high (e.g., E= 5)
Fig. A.3 shows the results. When the dataset is IID across workers, adding the shuffled dataset to each worker does not influence the learning speed. This agrees with the lemmas that have shown in the main text. When the dataset is non-iid across workers, shufiling a small percentage of the local dataset can highly improve the convergence, especially when the number of local epochs is high, e.g., E = 5. We can achieve a slightly better speedup when the stochastic noise is non-zero, which most the cases in the neural network training where we use mini-batch SGD.
A.3.2 Extra explanation for F
We consider a distributed least squares objective f(x) = - = E 11 b with Ag ila μ4 ~ No (id)) La)), and b, ~ NN4,, ( L2), and x² controls the stochastic noise (matching parameters in Corollary T). On each worker, we generate
(id)) where Ç² controls the function similarity
21

---

Published in Transactions on Machine Learning Research (03/2024)
2==10
10 d'=0
Rp AAT +Bp
1.0
10
P=
P=0.4
p=0.0
P=04
101
p=0.0
Ply P
p=0.8 0.8
P=0.8
10-1
P=0.4
D=0.2
0.8
Theory
Error
10-2
d =000
Rabie
0.6
10-4
10-3
Estimate
0.4
10
0.2
10
102
10
102
0.00
0.25
0.50
0.75
Rounds (a)
Rounds (b)
shuffle percentage (p) (c)
Figure A.4: Convergence of : Ei= |x|-xx11 x1. (a) With fixed (² and step size, shuffling reduces the optimal error more when the stochastic noise is low (b) When gradient dissimilarity Ç dominates the convergence, we obtain a super-linear speedup in the number of rounds to reach E by shuffling more data. The vertical bar shows the theoretical number of rounds to reach e (c) The estimated ratio matches the theoretical ratio when
Lave comes from the Lipschitz constant the shuffle percentage is small (e.g., p S 0.6). The term V 1 p+ + tmax
ralio
Lp
Lp=o
n 100 pairs of (Aij. bij} with d= 25. We randomly sample p n, pairs of {Aij, bij} from all the clients. We then aggregate, shuffle, and redistribute them equally to each client such that the number of functions per client is still n,, We depict the influence of shuffling on different paramcters in Fig. A.4 To conciscly match out theory, we need to consider that also the curvature of the function changes and measure Lp. Timax = max; 1 Σj= AT, Aijl and Tavg == EE Σ AT, Atil-
Fig. A.4 (a) shows the influence of shullling when we vary the stochastic noise given fixed Ç² and stepsize. We observe that in the high-noise regime, shuffling gives a smaller reduction on the optimal error than when σ²
(1-p)o²+ + Avg tends to dominate no matter how much data we shuffle. Fig. A.4 (b) shows the
influence of shuffling when o² and o ( (Epp(1--ps dominates the convergence. We tune the step size for ve
each experiment to reach the target accuracy = 1.1 10-9) with the fewest rounds. The theoretical number of rounds required to reach E, indicated by the vertical bars, were determined by calculating R2 = & + By.
where A= VIprdp is the cocfficient that depends on 5² and Ly. To estimate Ap, we mcasure the number of rounds to reach different accuracies and fit linear line between Rp and 1 Fig. A.4 (b) shows that VE the empirical speedup matches the theoretical speedup as the observed and theoretical number rounds to reach the target accuracy are very close. For better visualization, we compare the theoretical and estimated ratio in Fig. A.4 (c) given 2² = 0. Fig. A.4 shows the ratio between the cocfficient Ap. which boils down
Ap=o
to o (- VT.ger
Vlg=akomo The nearly matching lines in Fig. A.4 (c). especially when p is small, verify our theoretical
statement about the impact of data helerogeneity on the convergence parameters. When p is large, o² and the constant term tend to dominate the convergence. A linear line between Rp and /e explain the convergence rate.
1 is incomplete to
A.3.3 Communication cost
We calculate the number of transmitted parameters when FedAvg is used in Table A.2 which shows that we can reduce the number of transmitted parameters up to 95% to achieve a certain level accuracy. For methods such as SCAFFOLD Karimireddy et al. (2020b) and FedPVR Li al.] (2022a), we also need take into account the transmitted control variates when we calculate the number of transmitted parameters per round.
22

---

Published in Transactions on Machine Learning Research (03/2024)
The saved communication cost of using Fedssyn compared to the vanilla FedAvg (percentage between the number of transmitted parameters). M, the size of the transmitted synthetic data and M, is the size of the FL model. Mc in our experiment is around 37.2 MB. Fedssyn transmits significantly less number of parameters compared to the vanilla FodAvg to reach the same level of accuracy.
Table A.2:
Number of client (participation rate)
CIFARIO
CIFAR100
0.01
0.1
0.01
0.1
N=10 (C=1.0) (M, 15.5MB)
95.0%
87.6%
82.5%
80022
N=10 (C=0.4) (M, 15.5MB)
>95.6%
80.9%
>82.6%
>78.6%
N=40 (C=0.2) (M, 0.39MB)
87.9%
63.8%
62.6%
>8.2%
N=100 (C=0.1) (M, = 0.16MB)
79.6%
-61.2%
288.6
>41.0%
clients Epoch=50
clients Epoch=250
clients Epach=450
Figure A.5: Example simulated images from different training epochs on CIFARIO. The number of training images per client 875. When the number clients is high, the longer we train the DDPM, the better images we can obtain.
Synthetic E=50
Synthetic data, F=499
0.8
Server test accuracy
0.4
Vanilla SCAFFOLD
0.2
+ synthetic data, E=50 Ea synthetic data, E=200
synthetic data, E-499
25
50
75
Figure A.6: Example of the differentially private synthetic images from when the DP-DDPM has been trained for 50 epochs (B=50) and for 499 epochs (B=499), with respectively. The performance of Fedssyn using SCAFFOLD as the bascling is shown on the right. We achieve better performance and converge slightly laster than the vanilla SCAFFOLD even if the synthetic images are privacy friendly.
A.3.4
Differentially private synthetic images
A.3.5
Convergence parameters in DNN experiments
We here investigate the impact of using shuffled synthetic data on the parameters in the convergence rate for DNN-based FedAvg in Fig. A.7 We use CIFAR10, 10 clients with full participation, p mh 4500. We observe that when p 0.06, though the stochastic noise oy remains similar, & has reduced by half and we improve the Top-1 accuracy by 20%. When p 0.5, obtain much smaller o? and 23. Consequently, we achieve an even better Top-1 accuracy than the IID experiment. However, the parameters in Fig. A.7 (b) and (c) are evaluated with different server models xp.r, so it is less comparable to Lemma 1 where it requires the upper bound and the same server model. Therefore, we evaluate the gradient dissimilarity 22 and stochastic noise of using D, D.s and the corresponding o² and ç² using D, with the server model x, in each round in Fig. A.7 (d). We observe that (1 p)o² dominates over other terms
0.1, and
23

---

Published in Transactions on Machine Learning Research (03/2024)
in the effective stochastic noise, which means the first term in the convergence rate for non-convex function in Corollary I can be simplified as o (-pplof6e) in this experimental setup. For Sp the empirical result also matches the theory. These results show that in this experimental setup, adding shuffled synthetic dataset
mel
reduces both stochastic noise and function dissimilarity, and lead to greater accuracy improvement.
(a): Accuracy
(b):
(c): X²
(d): Analytical vs Empirical
x100
x10
80
10
60
10
p(1 - ppc 001 - p162
40
IID
Non-IID
0=0.06
20-
(1 (1-p)p7
20
p=0.20
p=0.5
p¹?
0
0
25
50
20
40
60
20
40
60
20
40
60
Communication rounds
Figure A.7: Influence of using shuffled synthetic dataset on the stochastic noise 0² and function dissimilarity ?² (CIFAR10, 10 clients, a = 0.1). The percentage of shuffled data in (d) 0.06. The empirical obscrvation of 6² and 2² matches the theoretical statements.
A.3.6 Influence of the 8 parameter in DNN experiments
We show the impact of the 8 parameter (I|V)(x, - Vf(x, D)11 S 8²) on the convergence parameters d² and (² here, We quantify the values of the stochastic noise and gradient dissimilarity following the procedure described above. In Fig. A.8 E: 50 means the synthetic data shuffled to each client is generated with the DDPM that has been trained for 50 epochs. Note that Fig. A.S only serves as an illustration. We cannot directly match Fig. A.8 with Lemma as we here show the precise quantified value using different server models along the communication round rather than an upper bound. Under the same server model (i.e., vertical line in each figure), we observe that ō contributes less to the effective stochastic noise than other parameters such as o² and Ø². However, it is worth remembering that d also can influence the effectiveness of the server model (see the server accuracy in Fig. A.8p and DD is different across different FI, experiments (i.e., from E:50 to E:450), so we cannot compare the curves horizontally.
A.4 Experimental results on dSprites dataset
In this section, we demonstrate the effectiveness of our proposed framework on the dSprites dataset Matthey et al. (2017). We here perform slightly different synthetic data generation process. Rather than using the DDPM Ho et al. 2200)), we generate the synthetic dataset on each client with B-VAE (urgoss et al. (0018) We then aggregate and shuffle the collected synthetic dataset on the server and distribute them to clients following the same procedure as described in Sec. 3 and Sec. 4.
A.4.1 Training details
The dSprites dataset Matthey et al. (0177) contains three different types of shapes with different colours, scales, rotations, and locations.
Data preparation We first randomly select 10% of the images from the dSprites dataset to formulate the test set. We leave the test set on the server to evaluate the performance of the server model. For the rest of the dataset, we split them among 12 clients (N = 12) based on the four spatial locations (top-left, bottom-left, top-right, or bottom-right) and three shapes (square, ellipse, or heart) such that each client only sees single type of shape from one of the four pre-defined locations. The number of images on each client is the same (n: = 55296). We consider each shape as class and perform shape classification.
24

---

Published in Transactions on Machine Learning Research (03/2024)
E: 50
E: 250
E: 450
Server accuracy
10a
0.7
10A
6P
0.6
E: 8::50
(1 -
11 -l
10
po
po
E: 450
P 2 p(1
p PIZZ
p PK?
FedAyg
pIo2
p(1
pIo
p(1 p/02
10-1
70
60
(1 (1-p)Rp
(1 (1-pPP
0.4
50
p²
p²
40
30
0.3
20
10
0.2
20
30
50
60
Communication rounds
Figure A.8: The movement of the convergence parameters given synthetic images that are extracted from different stages of training, e-g., 50 means the synthetic data shuffled to each client in Fedssyn generated with the DDPM that has been trained for 50 epochs. We use CIFAR10, 40 clients, 0.01, p 0.57 here.
2769
12
66
66
5529
Epooh
70
8299
99
98
100
68
60
98
99
99
99
50
11039
99
98
-50
1105
2211
4423
8847
17694
35389
55286
2211
4423
8847
17604
35389
55296
pr
pm
Figure A.9: Performance on the dSprites test datasct. Left: the influence of the number of training epochs and training images (pn,) training the generator on the FL performance. Right: the influence of the number of synthetic images (f,) on the FL performance. When we use fewer training images to train the generator (e.g. 2211), it beneficial train the generator longer and sample more synthetic images.
Synthetic data generation We use VAE with the same architecture as Burgess et al. (2018) following publicly available implementation We train an individual 3-VAE Burgess al. (2018) on cach client
with batch size 256, latent dimension 10. To evaluate the sensitivity of the federated learning optimization the quality of the generator, train the generator using different fractions of data pn, with p being (1%, 2%, 4%, 8%, 32%, 64%, 100%} on each client. When = 100%, train 3-VAE with the entire dataset from each client.
Many works have demonstrated that the latent variables in 8- 3-V can encode disentangled representative features of the input images Burgess al. (2018); Matthey et al. 22017) Kingma & Welling (2013), and ma- nipulating single latent dimension can result in substantial changes of the corresponding factor of variation, obtain diverse synthetic images by interpo-
e.g., scale, in the output from the decoder. Therefore,
25

---

Published in Transactions on Machine Learning Research (03/2024)
Epochs fraction
Epochs fraction
Epechs fraction
552
552
552
11.5
1105
1105
2211
2211
4423
4423
8841
8847
17694
17694
17694
55296 35188
55296 35389
Clent
Ciient
Clent
Figure A.10: Example synthetic images from clients 5, and 11. The x-axis shows the training fraction of 360 epochs, and the y-axis shows the number of training images used to train the generator. The number of training images has a more substantial influence on the quality of the synthetic data.
lating the extracted latent representations. To achieve this, we extract the averaged latent representations for each class, specifically the mean of the posterior distribution He Burgess al. (2018). We then sample ñn latent codes from the Gaussian distribution paramcterised by mean Pe and standard deviation 1. The sampled latent codes are then passed as the input for the decoder from 3-VAE to generate synthetic images. We collect the synthetic images from all the clients, which are then shuffled and distributed equally to each client such that the local dataset on cach client is pD; + (1 -p)D.. An example of the generated synthetic image shown in Fig, A.10 With the updated dataset on each client, we follow the same procedure as documented in Sec. 4 to perform federated optimization with FedAvg McMahan et al. (2016).
A.4.2 Discussion
We show the sensitivity of FedAvg's performance on the quality of the synthetic images in Fig, A.9 The left image shows that training the VAE longer does not necessarily provide better quality synthetic images when we use fewer training images. However, when we use more training images (higher p), the images extracted from early checkpoints, c.g., 50% epochs, are already of high quality. We observe a similar pattern in the right image Fig. A.9 where the number of training images has more substantial influence on the performance of FedAvg than the number of generated synthetic images.
26


Reviews:
[{"review_id": "v5YRyEYOmU", "reviewer": "Reviewer_Zsfa", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "1. The first contribution regarding convergence of FedAvg with data shuffling seems theoretically supported. However, certain terms are not referenced before clearly defined, which makes the work hard to follow. For example, in corollary I, the author defined \"local steps\" as $\\tau$ yet the term \"local steps\" were not explicitly defined. The $\\tau$ also did not appear in Algorithm II either. \n\n2. The idea of using synthetic dataset for shuffling seems novel to me. The authors also integrated differential privacy with their algorithm which is appreciated. It would be appreciated if the authors could provide theoretical notes on FedSynn --- for example, how many local data are required to train a sufficiently closed synthetic dataset?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work claime two contributions: 1. the authors quantified the importance of data shuffling for Federated Averaging which may boost convergence superlinearly and 2. propose an algorithm Fedssyn that shuffle synthetic data instead of the actual data, which improves data access preservation.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "My main concern is about the bullet point 1 above. I would recommend the authors to restructure their theoretical statements by clearing define the algorithms/symbols/terms first before referencing them. Currently it is to painful to guess the correct semantics of these notations.", "broader_impact_concerns": "There is no broader impact concern for this work/", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "poAqg3SxcA", "reviewer": "Reviewer_748X", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The paper uses class-conditional DDPM to generate synthetic data which is then used to improve federated learning on heterogenous data distribution. \n2. The paper presents the convergence rate guarantees after shuffling. \n3. The paper presents exhaustive experimental results comparing Fedssyn with other popular FL algorithms (designed for non-iid data) and synthetic data-based approaches. The experimental results show that Fedssyn reaches a target accuracy much faster than the baseline algorithm (saves the communication cost by up to 95%).\n4. The paper analyses the impact of training the generator using a differentially private algorithm and shows that the generator can produce differentially private synthetic images.\n5. An ablation study on the number of samples used to train the generator and the number of synthetic images generated is presented.\n6. Limitations of the proposed methods are discussed.\n7. The paper is well written.\n\nWeaknesses/Questions:\n1. The proposed method requires each client to train a generator adding additional compute overhead on each client. \n2. Each client needs to store these additional synthetic images which requires additional memory.\n3. Training the generator with a differentially private algorithm becomes necessary to avoid data leak and this could make generator training difficult especially when a client has limited local data.\n4. There is a possibility that some of the images produced by the generator are not useful. Any insights on filtering mechanisms that can be used to discard the bad (in terms of utility) images at each client before sending them to the server? \n5. How did you choose the target accuracy m?\n6. \"Server shuffles the aggregated synthetic data randomly into N parts\". Are there better ways to split the synthetic data for each client given that we know the class distribution for each client from the received synthetic data?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The synthetic data shuffling to improve federated learning under data heterogeneity. The proposed Fedssyn algorithm trains a class-conditional DDPM on each client at the beginning of the training to generate synthetic images. The server aggregates the synthetic images generated by each client, shuffles them, and splits them across the clients. Fedssyn then runs an FL algorithm with an updated dataset on each client. The paper presents theoretical guarantees for the impact of shuffling on the convergence rate in FedAvg.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Table 1 is hard to follow. It would be better to use actual numbers instead of bars and use multiple tables if required. \n2. It would interesting to add the memory and compute overheads to Table 2. This helps in understanding the cost of synthetic image generation and storage for various synthetic-data based approaches.\n3. Table A.1 can be moved to the main paper. Provide more discussion on the pros and cons of fedssyn compared to other synthetic-data based approaches.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "iNzWBbwVKV", "reviewer": "Reviewer_NCv5", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\nIt proposes the use of synthetic data shuffling as a solution, offering a way to homogenize data distribution without violating data access rights​​. The authors analyze the impact of synthetic data shuffling on the convergence rate of the FedAvg optimization algorithm. They establish relationship between data heterogeneity and convergence parameters, providing valuable theoretical insights into the mechanics of FL optimization under data heterogeneity conditions​​. Fedssyn shows significant improvements in terms of communication efficiency, Top-1 accuracy, and robustness against varying levels of data heterogeneity. The framework's compatibility with different FL algorithms enhances its practical applicability​​.\n\nWeakness:\nTraining local generators for synthetic data generation can be computationally intensive for each client device. And the main concern is that while the approach mitigates direct data sharing issues, there remains a severe risk of indirect leakage of the training data distribution through synthetic images. This aspect needs further theoretical and empirical investigation to ensure privacy-preserving practices in FL deployments​​. The utility of the Fedssyn framework may heavily rely on implementing DP.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper presents an data shuffling approach to addressing data heterogeneity in federated learning through generating synthetic data using the local data. It demonstrates significant improvements in convergence rate and accuracy, the approach's computational demands and potential privacy concerns present areas for further refinement.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The authors should provide a deeper analysis of the privacy protection aspects inherent to Federated Learning (FL). Given that FL is fundamentally designed to reduce privacy breaches, it is crucial for the paper to offer a more comprehensive exploration of the extent to which privacy is safeguarded. This should include a theoretical framework or proof demonstrating the level of privacy protection that can be reliably achieved using their proposed method. The generators can be possibly to learn the distribution of the data so that it would be dangerous to transmit data to not just the server but also other clients.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All the reviewers agree that the claims made in the paper are supported by provided evidence, and that this is of interest to at least some subset of TMLR. The paper thus meets the criteria for acceptance to TMLR. Some suggestions for future work made by the reviewers are to account for the need for DP at the generator in the theory and reducing computational requirements.
Decision: Accept (poster)