PEARL: Data Synthesis via Private Embeddings and Adversarial Reconstruction Learning
Authors: Seng Pei Liew
Tsubasa Takahashi
Michihiko Ueno
Venue: ICLR 2022 Poster (2022)
Keywords: Differential Privacy
Generative Model

Abstract: We propose a new framework of synthesizing data using deep generative models in a differentially private manner.
Within our framework, sensitive data are sanitized with rigorous privacy guarantees in a one-shot fashion, such that training deep generative models is possible without re-using the original data.
Hence, no extra privacy costs or model constraints are incurred, in contrast to popular gradient sanitization approaches, which, among other issues, cause degradation in privacy guarantees as the training iteration increases.
We demonstrate a realization of our framework by making use of the characteristic function and an adversarial re-weighting objective, which are of independent interest as well.
Our proposal has theoretical guarantees of performance, and empirical evaluations on multiple datasets show that our approach outperforms other methods at reasonable levels of privacy.

Published as a conference paper at ICLR 2022
PEARL: DATA SYNTHESIS VIA PRIVATE EMBEDDINGS AND ADVERSARIAL RECONSTRUCTION LEARNING
Seng Pei Liew, Tsubasa Takahashi, Michihiko Ueno
LINE Corporation
(sengpei. liew, taaasaaaaaatt waakkkaashmmmiiiiiikko... michhiiiko ueno) [1 inncorp.ccom |
ABSTRACT
We propose new framework of synthesizing data using deep generative models in differentially private manner. Within our framework, sensitive data are sanitized with rigorous privacy guarantees in a one-shot fashion, such that training deep generative models possible without re-using the original data. Hence, no extra privacy costs or model constraints are incurred, in contrast to popular gradient sanitization approaches, which, among other issues, cause degradation in privacy guarantees the training iteration increases. We demonstrate realization of our framework by making use of the characteristic function and an adversarial re-weighting objective, which are of independent interest well. Our proposal has theoretical guarantees of performance, and empirical evaluations on multiple datasets show that our approach outperforms other methods at reasonable levels of privacy.
INTRODUCTION
Synthesizing data under differential privacy (DP) (Dwork (2006 2011): Dwork et al. (2014)) enables
us to share the synthetic data and generative model with rigorous privacy guarantees. Particularly, DP approaches of data synthesis involving the use of deep generative models have received attention lately (Tkagi et al. (2021); Xie et al. (2018); Torkzadehmaaann et al. (2099; Frigerio et al. (2019);
Jordon et 2019): Chen et (2200 Harder et (2021)).
Typically, the training of such models utilizes gradient sanitization techniques (Abadi et al. (2016)
that add noises to the gradient updates to preserve privacy. While such methods are conducive to deep learning, due to composability, each access to data leads to degradation in privacy guarantees, and as a result, the training iteration is limited by the privacy budget. Recently, [arder et al. (202I) has proposed DP-MERF, which first represents the sensitive data as random features in DP manner and then learns a generator by minimizing the discrepancy between the (fixed) representation and generated data points. DE-MERF can iterate the learning process of the generator without further consuming the privacy budget; however, it is limited in the learning and generalization capabilities due its fixed representation. In this work, we seek a strategy of training deep generative models privately that is able to resolve the aforementioned shortcomings, and is practical in terms of privacy (e.g., usable image data at e 1.)
We propose a private learning framework called PEARL (Private Embeddings and Adversarial Reconstruction Learning). In this framework, have i) no limitation in learning iterations, and ii) well-reconstruucion capability. Towards those preferable properties, our framework first obtains (1) informative embedding of sensitive data and (2) auxiliary information (e.g.. hyperparameters) useful for training, both in differentially private manner, then (3) the generative model is trained implicitly like GANs via the private embedding and auiliary information, where the learning based on stochastic procedure that generates data, and (4) critic distinguishing between the real and generated data. The overview of PEARL is illustrated in Fig. !
As concrete realization of PEARL, We first identify that the characteristic function (CF) representa- tion data can be sanitized as the private embedding of PEARL. Consequently, it is possible to train deep generative models using an appropriately defined metric measuring the discrepancy between the real (but sanitized) and generated data distribution based on the CF without re- re-using the original data. As will be explained in detail in later Sections, the generative modelling approach using CFs also

---

Published as a conference paper at ICLR 2022
Privately Embedded
Synthesized
Privately E Embedded
Synthesized
Adv. Recon. Learner
Data
Privately Embedded
Synthesized
DP flow (one shol)
(2)
Aux
Critic
Data flow (one-shot) Training loop
Figure 1: PEARL is a private learning framework that has no limitation in learning iterations, and ii) well-reconstruction capability. Towards those preferable properties, our framework first obtains (1) private embedding and (2) auxiliary information from the sensitive data, then (3) trains generator while (4) optimizing critic to distinguish between the real and generated data.
involves sampling "frequencies" from an ad hoc distribution, to project the data to the embedding. It desirable to optimize the sampling distribution better represent the data as an embedding, but the naive way of optimizing it would require re-accessing the data via sampling, coming privacy budget. Henceforth, we also propose to incorporate privacy-preserving critic to optimize the sampling strategy, which, through re- weighting, chooses the best representation from fixed samples of frequencies without extra privacy costs.
cost of
To this end, we propose the following minimax optimization training objective:
w(t;) (t.)
inf sup DEG WE
dp, (t.) Pes (t.))².
(1)
See later parts for notations and details. Theoretically, we show that our proposed objective has properties similar to those that are suited to training GANs, i.e., continuity and differentiaaility of the generator's parameters, and continuity weak topology. We also prove the consistency of our srivacy-preserving sampling strategy at the asymptotic limit of infinite sampling. Empirical evaluations show that PEARL is able high-quality synthetic data reasonable privacy levels.
Related works. Traditional methods of synthesizing data are mainly concerned with discrete data or data preprocessed to the discrete form (Zhang al. (2017); Qardaji et al. (2014); He et al. (2015):
Chen et al. (2015): Cai et al. (202T): ZZhng et (2021) )), whereas we are interested in more general methods involving continuous data. Deep generative models under the DP setting are suitable for this type of tasks (Takagi et al. [202]) Xie et al. (2018); Torkzadehmahani et al. (2019); Frigerio et al. (2019); Jordon al. (2019); Chen al. (2020); Harder et al. (2021)). The private training of deep generative models usually performed using gradient sanitization methods. An exception DP-MERF (Harder et al. (20IT)) which is closest to our work. There, random features used to approximate the maximum mean discrepancy (MMD) objective training a generator. PEARL, which, as a realization, uses CFs, may be viewed as generalization of DP-MERF. Additionally, PEARL has several distinetive features which are lacking in DP-MERE The first lies in the introduction of performance. The second the private selection of the parameter of the sampling distribution, which is also shown to be vital. Moreover, DP-MERF uses non con-chaaacteisttc kernels when treating tabular data, in contrast to ours, which is characteristic and has guarantees in convergence. We finally note that generative models using CFs but only non-privately have been explored before (Ansari et al. (2020): Li al. (2020)
privatized and utilized for
critic, which leads to an improvement of
Contributions. Our contribution in this paper is three-fold: (i) We propose a general framework called PEARL, where, unlike gradient sanitization methods, the generator training process and iteration are unconstrained; reliance on ad-hoc (non-private) hyperparameter tuning is reduced by extracting hyperparameters (auxiliary information) privately. (ii) We demonstrate a realization of our framework by making of the characteristic function and an adversarial re-weighting objective. (iii) Our proposal has theoretical guarantees of performance, and empirical evaluations show that our approach outperforms competitors at reasonable levels of privacy ~
2

---

Published as a conference paper at ICLR 2022
2 PRELIMINARIES
This Section gives a brief review of essential preliminaries about differential privacy, characteristic function and the related notations.
2.1 DIFFERENTIAL PRIVACY
Definition ((e, d)-Differnntial Privacy). Given privacy parameters e 2 and 8 2 0. a randomized mechanism, M D - R. with domain 'D and range RR satisfies (e, 8)-differential privacy (DP) for any two adjacent imputs d, d' E D and for any subset of outputs S _ RR the following holds:
Pr(M(d) E S] S .Pr(M(dd" E 6.
(2)
We next consider concrete ways of sanitizing certain outputs with DP. A typical paradigm of DP is applying the randomized mechanism, .,, to a certain deterministic function f :D such that the output of f is DP. The noise magnitude added by M is determined by the sensitivity of f. defined as (l - [(d')l II. where ||- I| is norm function defined on f's output domain. and d' are any adjacent pairs of dataset. Laplacian and Gaussian mechanisms are the standard randomized mechanisms. We primarily utilize the Gaussian mechanism in this paper (Dwork et al. (2144))
A - S
Definition 2 (Gaussian Mechanism). Lei f: X + I be an arbitrary function with sensitivity A The Gaussian Mechanism, Ma. parameterized by a, adds noise to the oulput of J as follows:
(a = f(x) + N0,,0 o0,,01). 1).
One of the most important properties of DP relevant to our work is the post post-processing theorem (Dwork et al. (2014)):
Theorem pPost-processing Theorem). Let M : D + R be (c, 8P and let f R + R' be an arbitrary randomized functiion Then, fo M D - R' is (c, 8)-
It ensures that the DP-sanitized data can be re-used without further consuming privacy budgets.
2.2 CHARACTERISTIC FUNCTIONS
Characteristic function (CF) is widely utilized in statistics and probability theory, and perhaps is best known to be used to prove the central limit theorem (Williams) (199T). The definition as follows. Definition (Characteristic Function). Given random variable X C Rd and P as the probability measure associated with it, and t E Rd the corresponding characteristic function (CF) is given by
( Ex-eleitx>
(4)
Here, is the imaginary number. From the signal processing point of view, this mathematical operation is equivalent to the Fourier transformation, and (p(t) is the Fourier transform at frequency noted that we deal with the discrete approximation of CFs in practice. That is, given a dataset
with n i.i.d. samples, {x, } from IP, the empirical CF is written as T - it-x, We next introduce characteristic function distance (CFD) (Heathcote
[1722; Chwialkowski et al. 2015)):
Definition (Characteristic Function Distance), Given two distributions IP and Q of random variables residing in Rd. and sampling distribution on t E TRd the squared characteristic function funcition distance (CFD) between P and Q is computed as:
(P, Q = E (elw()))///())) (t)) - (1)()))))_ ((())))
(5)
Notations. Let us make short note on the notations before continuing. Let k be the num- ber of t drawn from and be the probability measure of a random variable. We group the CFs associated to P of different frequencies, (#z(t)),.... (p(())) more compactly as He (x). To make the dependence of (e((x) on the sampled data explicit, we also use the fol- lowing notation: @p(x) 1 n E (x(x)). We notice that (x)2(x) V (
E Ei_ ei x: /n|2 V E Ei_ 1/n Vh, where the norm taken over the (complex) frequency space. With slight abuse of notation, we abbreviate op as & when there is no ambiguity in the underlying probability measure associated with the CF.
3

---

Published as a conference paper at ICLR 2022
3 GENERATIVE MODEL OF PEARL
Let us describe generative modelling under the PEARL framework. The realization is summarized by the following Proposition:
Proposition 1. Let the real data distribution be Py, and the output distribution of an implicit generative model Ga by Qg. Let be the total number of real data instances and consider releasing CF's from the dataset. Then, Gg trained to optimize the empirical CFD, min (F, Qo) with the CF
#e
sanitized according the Gaussian mechanism (Defn. with sensitivity 2/k/r satisfies (c, 8D- where a 2 22 (21g2(1.5//
Proof. In the following we give detailed explanation of the above Proposition. The first step of PEARL is projecting the data to the CF as in Eq. where the number embeddings is the number of frequency drawn from (t).
We note that CF has several attractive properties. CF uniformly continuous and bounded, as can be seen from its expression in Eq. 4 Unlike the density function, the CF of random variable always exists, and the uniqueness theorem implies that two distributions are identical if and only if the CFs of the random variables are equal (Lukacs (1972)).
The CF is sanitized with DP by applying the Gaussian mechanism (Defn. to ((x):
x(x) ((x) + NO0 A (x)) II),
where we write the sanitized CF as (x): A 3(x) denotes the sensitivity of the CF, a denotes the noise scale which is determined by the privacy budget, (E,
The calculation of sensitivity is tractable (no ad-hoc clipping commonly required by gradient sanitiza- tion methods) Without loss of generality, consider two neighboring datasets of size where only the last instance differs (Xn, # x, ). The sensitivity of o(x) may then be calculated
A ((x)
max D,D
Σ x(xx)
1 Σ
(xx)
= max x.. xx
- (xx( 2v
1
where we have used triangle inequality and ||ā(-)ll S Vk. It can be seen that the sensitivity is proportional the square root of the number embeddings (releasing more embeddings requires more DP noises to be added to Φ) but inversely proportional to the dataset size, which is important for controlling the magnitude of noise injection at practical privacy levels, will be discussed in later Sections.
We would like train generative model where the CFs constructed from the generated data distribution, y' C TRd, matches those (sanitized) from the real data distribution, X' C Rd. A natural way of achieving this is via implicit generative modelling (MacKay (1995); Goodfellow et al. (2014). We introduce a generative model parametrized by 0, Ga Z + Rd which takes a low-dimensional latent vector E Z sampled from a pre-determined distribution (e.g., Gaussian distribution) as the input.
In order quantify the discrepancy between the real and generated data distribution, we use the CFD defined in Eq. 5 Empirically, when finite number of frequencies, k. are sampled from w, CP( Q) approximated by
CPP Q
1 Σ @ - 2
- Se xx) (
where (t) and (t) are the empirical CFs evaluated from i.i.d. samples of distributions P and Q respectively. The training objective of the generator is to find the optimal 0 e θ that minimizes the empirical CFD: min (P,,, Qo). It can be shown via uniqueness theorem that long resides in
Rd, C(P, Q = + F = Q (Sriperumbudur et al. (011)). This makes CFD an ideal distance metric for training the generator.
4

---

Published as a conference paper at ICLR 2022
Optimization procedure. The generator parameter, 8, is updated follows. (x) is first sanitized to obtain Φr. (x), as in Eq. 6 This performed only for once (one-shot). Then, at each iteration, m samples of z are drawn to calculate Φ2, (x). Gradient updates on 0 are performed by minimizing the CFD, be (x) 2..
We note that only the first term, Φp. (x), has access to the real data distribution, X, of which privacy is of concern. Then, by Thm. | Gg trained with respect to &e. is DP. Furthermore, unlike gradient sanitization methods, the trainnng of Ge is not affected by network structure training iterations. Once the sanitized CF is released, there no additional constraints due to privacy on the training procedure.
DP release of auxiliary information. Auxiliary information, c.g., hyperparameters regarding to the dataset useful for generating data with better quality may be obtained under DP. our case, one may extract auxiliary information privately from the dataset to select good parameters for the sampling distribution (t). This will be discussed more detail in the next Sections.
Another example is the modelling of tabular data. Continuous columns of tabular data consisting of multiple modes may be modelled using Gaussian mixture models (GMMs) (Xu al. (2019). GMMs are trainable under DP using a DP version of the (2017)). The total privacy budget due to multiple releases of information is accounted for using the Rényi DP composition. See fooo the definition of Rényi DP.
algorithm (Park et al.
4 ADVERSARIAL RECONSTRUCTION LEARNING
This Section is devoted to proposing a privacy-preserving critic for optimizing w(t), while giving provable guarantees of performance.
Back to Eq. 5 and Eq. 7 we note that choosing a "good" w(t or "good" set of sampled frequencies vital at hilping discriminate between IP and Q. For example, if the difference between F and Q lies in the high-frequee frequecyyy region, one should choose to use t with large values to, in the language of two-sample testing, improve the test power.
Adversarial objective. If the resulting empirical CFD remains small due to under- under-optimized wt).. while the two distributions still differ significantly, the generator cannot be optimally trained to generate high-quality samples resembling the real data. Hence, we consider training the generator by. in addition to minimizing the empirical CFD, maximizing the empirical CFD using an adversarial objective which acts critic, where the empirical CFD is maximized by finding the best sampling distribution. We consider a training objective of the form
inf sup C. (Pr, west
where Ω is some of probability distribution space of which the sampling distribution w lives in.
Privacy-prees preserving optimization. It is intractable to directly optimize w in the integral form as in Eq. 5 In this work, we opt for a privacy-preserving one-shot sampling strategy where once the private data is released (by sampling from w), optimization is performed without further spending the privacy budget. We believe that such new formulation of distribution learning is of independent interest as well.
Effectiveness of the critic. To further motivate why it is preferable to introduce an adversarial objective as in Eq. 8 we present a simple demonstration through the lens of two-sample testing (Chwialkowski et al. (2015); Jitkrittum et al. (2016) using synthetic data generated from Gaussian distributions. We generate two unit-variance multivariate Gaussian distributions P. Q, where all dimensions but one have zero mean. We conduct a two-sample test using the CF to distinguish between the two distributions, which gets more difficult the dimensionality increases. We test the null hypothesis where the samples are drawn from the same distribution is rejected. Higher rejection rate indicates better test power.
Note that the first dimension (where the distribution differs) of the frequency used to construct CFs the most discriminative dimension for distinguishing the distributions. We consider three sets of
5

---

Published as a conference paper at ICLR 2022
frequencies: "unoptimized", "normal", and "optimized", where the set of "unoptimized" frequencies is optimized with re- weighting. More details can be found in App. C
Fig. shows the hypothesis rejection rate versus the number of dimensions for the three cases considered above. As can be observed, the "op- timized" case gives overall the best test power. While this experiment is somewhat contrived, it can be understood that although both "unop- timized" and "optimized" sets of frequencies contain the discriminative to. the re-weighting procedure of selecting the most discriminative CF improves the test power significantly. Even without re-sampling from "better" w(t), re- improve weighting the existing frequencies the test power. The fact that re- weighting can im- prove the test power is crucial privacy-wise be- cause the altenative method, re-sampling, causes degradation in privacy.
1.0
Rojecton Rate
0.6
0.4
UnouSmizsd
Normal
Optimized
0.0
Dimensione
Figure 2: Increased test power upon optimization
(green) in two-sample test.
Li=1 T (t:) Pe (t:)) is obtained by drawing k frequencies from base distribution Wg. Our idea is to find (weighted) set of frequencies that gives the best test power from the drawn set. We propose Eq. [aas as the optimization objective, restated below:
Proposal. Recall that the empirical CFD, (P,, Qv) Σ
w(ts) (t:)
inf sup RED WED
Tr. (t;) @ (t:))²²
Note that the generator trained with this objective still satisfies DP as given in Prop. [ due to Thm. The following Lemma ensures that the discrete approximation of the inner maximization of Eq. approaches the population optimum as the number of sampling frequency increases (k + oc):
Lemma 1. Let wa be any probability distribution defined on Rd, and let f RRd - R' be any function. Also let t E Rd and wt be the maximal distribution of with respect to E=]s(t)] = f(t (t)))
Assume that the empirical approximation [t)] - (t)] the asymptotic limit for any
Then, Ew,, (f() w (t)
(t) + Eu- [f()] at the asymptotic limit as well.
The proof is in App. B and is based importance sampling. Empirically, we find that treating w(t;) as a free parameter and optimizing it directly does not lead to improvement in performance. This may be due to the optimization procedure focusing too much uninformative frequencies that contain merely noises due to DP or sampling. We perform parametric optimization instead, that is, e.g., we perform optimization with respect {1,, J if w is of the Gaussian form, NN Ø²).
Performance guarantees. Let us discuss the theoretical properties of Eq. g The objective defined Eq. shares beneficial properties similar to those required to train good GANs, first formulated in (Arjovsky et al. (2017). First, the generator learns from a distance continuous and differentiable almost everywhere within the generator's 's parameters. Second, the distance is continuous in weak topology, and thus provides informative feedback to the generator (different from, e.g., the Jensen- Shannon divergence, which does not satisfy this property). We make assumptions similar to those given in (Arjovsky et al. (2017), ) and state the first theorem as follows.
Theorem 2. Assume that Gz(2) ) is locally Lipschitz with respect to (6,2), z); there exists L((0, 2) satis- fying Ez [L(0, =)] < oo; and supwest Eu [|t|] < do for all t. Then, the function supwen (P,, Qo) is continuous in E O everywhere, and differentiable in E O almost everywhere.
Note that the local Lipschitz assumptions are satisfied by commonly used neural network components, such as fully connected layers and ReLU activations. The continuity and differentiability conditions with respect to stated above allow Go to be trained via gradient descent. The theorem related to continuity in weak topology is the following:
Theorem 3. Let be a distribution on X and (P (Pn)nEN be a sequence of distributions on X. Under the assumption supweR Bustt [] < oo, the function supwed C2 (P,,, n, P) is continuous in the

---

Published as a conference paper at ICLR 2022
weak topology, ie.. Pn 2x P. then supwen (P,,,) Dx O, where 2a denotes convergence in distribution.
Weakness is desirable as the easier (weaker) it for the distributions converge, the easier it will be for the model to learn to fit the data distribution. The core ideas used to prove both of these theorems are the fact that the difference of the CFs (which is of the form e²x) can be bounded as follows: le ed I la b), and showing that the function is locally Lipschitz, which ensures the desired properties continuity and differentiability. See App. B for the full proofs.
5 EXPERIMENTS
5.1 EXPERIMENTAL SETUP
To test the efficacy of PEARL, we perform empirical evaluations on three datasets, namely MNIST (LeCun et al. (2010), Fashion-MNIST (Xiao et al. (2017)) and Adult (Asuncion Newman (2007))
Detailed setups are available in App.
Training Procedure. As our training involves minimax optimization (Eq. D. we perform gradient descent updates based on the minimization and maximization objectives alternately. We use a zero- mean diagonal standard-deviation Gaussian distribution, (O, diag(o") as the sampling distribution, w. Maximization is performed with respect to σ. Let us give a high-level description of the full training procedure: draw k frequencies from w, calculate the CFs with them and perform DP sanitization, train a generator with the sanitized CFs using the minimax optimization method. The pseudo-code of the full algorithm is presented in App. We further give the computational complexity analysis of our algorithm in App.
DP release of auxiliary information. We also note that applying maximization (re-weighting) on randomly selected set of frequencies would not work well. We initially fix the inverse standard deviation of the base distribution, wo. to be the DP estimate of the mean of the pairwise distance of the data, obtain (privately) a spectrum of frequencies that overlaps with the "good" frequencies. This is motivated by the median heuristic (Garreau et al. (2017)) Mean is estimated instead of median as its sensitivity is more tractable when considering neighboring datasets. We obtain A = 22/d/n as its sensitivity, where and are the data dimension and the number data instances respectively. See App. D for the derivation. [ Using this DP estimate, we also investigate as a ablation study the generator performance with minimization objective only (w/o critic). The full PEARL framework includes the use of the critic to find the "best" frequencies among the selected spectrum to distinguish the distributions (and overall perform a minimax optimization).
Evaluation Metrics. In the main text and App. we show qualitative results, i.c., synthetic images (image dataset) and histograms (tabular dataset) generated with PEARL. Furthermore, for image datasets, the Fréchet Inception Distance (FID) (Heusel et al. (2017) and Kernel Inception Distance (KID) (Binkowski et al.] (2018) are used to evaluate the quantitative performance. For tabular data, the synthetic data as the training data of 10 scikit-leam classifiers (Pedregosa et al. (2011)) and evaluate the classifiers' performances on real test data. The performance indicates how well synthetic data generalize to the real data distribution and how useful synthetic data are in machine learning tasks. ROC (area under the receiver operating characteristies curve) and PRC (area under the precision recall curve) are the evaluation metries, Definitions of FID and KID are in App.
5.2 EVALUATION DETAILS
MNIST and Fashion-MNIST. Privacy budget is allocated equally between the sanitization of CFs and the release of auxiliary information. [ On a single GPU (Tesla V100-PCIE-32GB), training MNIST (with 100 epochs) requires less than 10 minutes.
We note that OPMMERF also uses sampling distribution. Since privacy budget is not allocated for calculat- ing the parameters of the sampling distribution there, fix its sampling distribution be (0, diag(1)). We expect that CF sanitization requires more privacy allocation as it is involved in doing the heavy lifting of training the model. We find that allocating around 80-90% of the budget to CF sanitization can increase the performance by around 15%. Nevertheless, we utilize an equal share of privacy budget for faimesss reasons, as tuning the budget allocation would require re-using the private data and this can lead privacy leakage.
7

---

Published as a conference paper at ICLR 2022
8.
0
A3
5
1
7
f
1
0
3
0.7
7
0
2
3
8:
1
2
C
3
5
1
3
4
0
(8) c= 0.2 (MNIST)
(b)
< = (MNIST)
(c) 6 = 10 (MNIST)
(d) 9 = 0O (MNIST)
(c) 0.2 (FMNIST)
(f)
(FMNIST)
10 (FMNIST)
(h) (FMNIST)
Figure 3: Generated MNIST and MaSSIon-MNIST samples for various values of and 5 10-5
Datasets
Metrics
DPGAN
DPCGAN
DP-MERF
Ours (w/o critic)
Ours
MNIST
FID
22.1 1: 1.01
17.3 +: 2.90
49.9 +: 0.22
3.79 +: 0.06
3.52 : 0.06
KID (x10*)
573 41.2
286 = 69.5
148 46.2
77.8 9.88
70.5 + 10.3
Fashion-MNIST
FID
16.6 : 1.34
14.61 +: 1.75
37.0 - 0.15
1.99 + 0.04
1.92 1 0.04
KID (x10*)
535 61.5
425 + 64.2
1220 +: 36.1
24.0 = 6.90
26.9 6.80
Table 1: FID and KID (lower is better) on image datasets at (c, 6) = (1, 10 10-5).
Some of the generated images of ours and baseline models are shown in Fig. 3] and more (including baselines') can be found in App. [ At the non-private limit, the image quality is worse than other popular non-private approaches such as GANs due to two reasons. First, projecting data to a lower dimension causes information loss. Second, our architecture does not have diseriminator-like network as in the vanilla GAN framework. However, we notice that the quality of the images does drop much the privacy level increases (except e 0.2, where the quality starts to degrade visibly) because the noise added to the CF's is small as it scales inversely proportional to the total sample size. It also indicates that our approach works particularly well at practical levels of privacy.
We now provide quantitative results by performing evaluation at (c. 8) (1, 10-))) Note that we focus on this high privacy region despite the fact that many previous studies experimented with = 10, because recent analyses showed that realistic attacks can lead to privacy violations at low privacy (Jagielski et al. (2020): | Nasr et al. (202T)) Particularly, the claim "values of that offer meaningful theoretical guarantees" (e >> 1) can be chosen in practice has been "refuted" in general (Nasr et al. (021)). This motivates us to perform evaluation at e with meaningful theoretical guarantees (c 1).
At this privacy region, we compare PEARL with models using gradient sanitization and DP-MERF (Harder et al. 2222)) as other methods do not produce usable images single-digit the experiment five times (with different random seeds each time), and for each time, 60k samples generated evaluate the FID and KID. In Table [ the FID and KID (average and error) of DP-MERF, DPGAN, PEARL without critic, and PEARL are shown. It can be seen that PEARL outperforms DP-MERF significantly, and the critic leads improvement the scores.
We run
'In the gradient sanitized generative model literature, GS-W GS-WGAN Chen et al. (2020)) is known to be the state-of-the-art, but unable to train stable model 1. Thus, make comparisons with other standard methods, namely DPGAN (Xie et al. (2018) and DPCGAN (Torkzadchmahami al. (019)).
8

---

Published as a conference paper at ICLR 2022
Real data
DE-MERF
Ours
ROC
PRC
ROC
PRC
ROC
PRC
LR
0,788
0.681
0.661 1 0.059
0.342 1 0.041
0.752 1 1.0009
0.641 1 0.015
Gaussian NB
0.629
0,511
0.587 + 0.079
0.491 - 0.06
0.661 0.006
0.537 1 0.28
Bemoulli NB
0.769
0.651
0.588 +: 0.056
0.488 + 0.04
0.763 + 0.008
0.644 + 0.009
Linear SVM
0.781
0.671
0.568 1 0.091
1.009100006
0.752 1.00000000
0.640 1 0.015
Decision Tree
0.759
0.646
0.696 + 0.081
0.376
0.675 + 0.08
0.582 + 0.028
LDA
0.782
0.670
0.634 + 0.060
0.541 0.008
0.755 0.005
0.640 + 0.007
Adaboost
0.789
0.682
0.642 1 0.097
0.007
0.709 1.0031
0.628 1 0.024
Bagging
0.772
0.667
0.659 0.06
0.538
0.687 0.041
0.601 + 0.039
GBM
0.800
0.695
0.706 + 0.069
0.586 + 0.047
0.709 + 0.029
0.635 + 0.025
MLP
0.776
0.660
0.667 1 0.088
0.358 1. 0.063
0.744 0.012
0.635 1 0.015
Average
0.765
0.654
0.641 + 0.044
0.536 + 0.034
0.721 + 0.035
0.618 + 0.033
Table 2: Quantitative results for the Adult dataset evaluated at (e, 6) = (1, 10-5)
Dwn
Oun
(a) "marital-statur
(b) "occupation"
"relationship"
(d) "race"
(c) "age"
"capital-loss"
"capital-gain
(h) "fnlwgt"
Figure 4: Histogram plots for the the Adult dataset. Evaluation is performed at (c, = =1,,103)
Adult The Adult dataset consists of continuous and categorical features. As data pre-proepee rrepprocessing continuous features are scaled to [0, 1]. We also compare our results with DP-MERF, as DP-MERF performs best among other existing methods (e.g.. DPCGAN achieves ROC and PRC around 0.5; see Table 4) Again, auxiliary information and CFss share equal budget of privacy, and we perform evaluation at (c, (1, 10-3)- 5). 11k synthetic samples are generated for evaluation.
Histogram plots of the attributes comparing the real and synthetic data is shown in Fig. 4 As can be observed in the Figure, PEARL able to model the real data better than DP-MERF, e.g., covering more modes in categorical variables with less discrepancy in the frequency of each mode. PEARL is also able to better model the descending trend of the continuous variable "age". The average ROC and PRC scores (average and error) are shown in Table 2 ROC and PRC scores based on PEARL's training data are shown to be closer to those based on real training data compared to DP-MERF. More histogram plots in higher resolution are available in App.[] Also, in App. [ results of another tabular datasct (Credit), as well as evaluations with other metrics/tasks using the synthetic data. PEARL still performs favorably under these different conditions. Overall, we have demonstrated that PEARL is able to produce high-quality synthetic data at practical privacy levels.
we present experimental
6 CONCLUSION
We have developed a DP framework to synthesize data with deep generative models. Our approach provides synthetic samples at practical privacy levels, and sidesteps difficulties encountered in gradient sanitization methods. While we have limited ourselves to characteristic functions, it is interesting to adopt and adapt other paradigms to the PEARL framework as a future direction.
9

---

Published as a conference paper at ICLR 2022
REFERENCES
Martin Abadi, Andy Chu, lan Goodfellow, H Brendan McMahan, llya 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 308-318. ACM, 2016.
Abdul Fatir Ansari, Jonathan Scarlett, and Harold Soh. A characteristic function approach deep implicit generative modeling. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 7477-7483 2020.
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In International conference on machine learning, pp. 214-223. PMLR, 2017.
Arthur Asuncion and David Newman. Uci machine learning repository, 2007.
Mikotaj Binkowski. Dougal J Sutherland, Michael Arbel, and Arthur Gretton. Demystifying MMD GANs. arXiv preprint 1rXi::8001001001 2018.
Kuntai Cai, Xiaoyu Lei, Jianxin Wei, and Xiaokui Xiao. Data synthesis via differentially private markov random fields. Proceedings of the VLDB Endowment, 14(11):2190-2200 2021.
Dingfan Chen, Tribhuvanesh Orekondy, and Mario Fritz. Gs-wgan: A gradient- approach for learning differentially private generators. Advances Neural Information Processing Systems, 33:12673-1266 2020.
Rui Chen, Qian Xiao, Yu Zhang, and Jianliang Xu. Differentially private high- sigh-dimensional data publication via sampling-beee based inference. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 129-138, 2015.
Kacper P Chwialkowski, Aaditya Ramdas, Dino Sejdinovic, and Arthur Gretton. Fast two-sample testing with analytic representations of probability measures. Advances in Neural Information Processing Systems, pp. 1981-1989, 2015.
Andrea Dal Pozzolo, Olivier Caelen, Reid A Johnson, and Gianluca Bontempi. Calibrating prob- ability with undersampling for unbalanced classification. In 2015 IEEE Symposium Series on Computational Intelligence, pp. 159-166. IEEE, 2015.
Cynthia Dwork. Differential privacy. In Proceedings of the 33rd international conference on Automata, Languages and Programming- Volume Part 11, pp. 1-12, 2006.
Cynthia Dwork. A firm foundation for private data analysis. Communications of the ACM, 54(1): 86-95, 2011.
Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Found. Trends Theon Comput. Sci., 9(3-4)221-44 2014.
Herbert Federer. Geometric measure theory. Springer, 2014.
Lorenzo Frigerio, Anderson Santana de Oliveira, Laurent Gomez, and Patrick Duverger. Differentially private generative adversarial networks for time series, continuous, and discrete open data. In IFIP International Conference on ICT Systems Security and Privacy Protection, pp. 151-164. Springer, 2019.
Damien Garreau, Wittawat Jitkrittumm, and Motonobu Kanagawa. Large sample analysis of the median heuristic. arXiv preprint 1rXivv1707.072800 2017.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in Neural Information Processing Systems, pp. 2672-2680, 2014.
Frederik Harder, Kamil Adamczewski, and Mijung Park. Dp-merf: Differentially private mean embeddings with randomfeatures for practical pressevin data generation. In International conference on artificial intelligence and statistics, pp. 1819-1827. PMLR, 2021.
10

---

Published as a conference paper at ICLR 2022
Xi He, Graham Cormode, Ashwin Machanavajhaala Cecilia M Procopiuc, and Divesh Srivastava. Dpt: differentially private trajectory synthesis using hierarchical reference systems. Proceedings of the VLDB Endowment, 8(11):115-1116, 2015.
CE Heathcote. A test of goodness of fit for symmetric random variables. Australian Journal of Statistics, 14(2):172-11,, 1972.
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. Gans trained by a two time-scale update rule converge to a local nash equilibrium. Advances in neural information processing systems, 30, 2017.
Matthew Jagielski, Jonathan Ullman, and Alina Oprea. Auditing differentially private machine learning: How private private sgd? Advances in Neural Information Processing Systems, 33: 22205-22216,, 2020.
Wittawat Jitkrittum, Zoltán Szabó, Kacper P. Chwialkowski, and Arthur Gretton. Interpretable distribution features with maximum testing power. In Advances in Neural Information Processing Systems, pp. 181-189, 2016.
James Jordon, Jinsung Yoon, and Mihaela van der Schaar. PATE-GAN: generating synthetic data with differential privacy guarantees. In International Conference on Learning Representations, ICLR, 2019.
Achim Klenke. Probability theory: a comprehensive course. Springer Science & Business Media, 2013.
Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online]. Available: http:/lynn.lecun.cco http://www..ecc...c////e////iiie 2, 2010.
Shengxi Li, Zeyang Yu, Min Xiang, and Danilo P. Mandic. Reciprocal adversarial learning via
characteristic functions. In Advances in Neural Information Processing Systems, 2020.
Eugene Lukacs. A survey of the theory of characteristic functions. Advances in Applied Probability, 4(1):1-37, 1972.
David J.C. MacKay. Bayesian neural networks and density networks. Nuclear Instruments and Methods in Physics Research Section A: Accelerators, Spectrometers, Detectors and Associated Equipment, pp. 73-80, 1995.
Ilya Mironov. Rényi differential privacy. In 2017 IEEE 30th Computer Security Foundations Symposium (CSF), pp. 263-275. IEEE, 2017.
Milad Nasr, Shuang Songi, Abhradeep Thakurta, Nicolas Papemoti, and Nicholas Carlin. Adversary instantiation: Lower bounds for differentially private machine learning. In 2021 IEEE Symposium on Security and Privacy (SP), pp. 866 882. IEEE, 2021.
Mijung Park, James R. Foulds, Kamalika Choudhary, and Max Welling. DP-EM: differentially private expectation maximization. Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, pp. 896-904, 2017.
Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit-learn Machine learning in python. the Journal of machine Learning research, 12:2825-2830, 2011.
Wahbeh Qardaji. Weining Yang. and Ninghui Li. Priview: practical differentially private release of marginal contingency tables. In Proceedings of the 2014 ACM SIGMOD international conference on Management of data, pp. 1446-1446, 2014.
Bharath K Sriperumbudur, Kenji Fukumizu, and Gert RG Lanckriet. Universality, characteristic kerells and rkhs embedding of measures. Journal of Machine Learning Research, 12(7), 2011.
Shun Takagi, Tsubasa Takahashi, Yang Cao, and Masatoshi Yoshikawa. P3gm: Private high- dimensional data release via privacy preserving phased generative model. 2021 IEEE 37th International Conference Data Engineering (ICDE), pp. 169-180. IEFE, 2021.
11

---

Published as a conference paper at ICLR 2022
Reihaneh Torkzadehmahani, Peter Kairouz, and Benedict Paten. Dp-egan: Differentially private synthetic data and label generation. The IEEE Conference on Computer Vision and Pattern Recognition (CVPR) Workshops, June 2019.
Yu-Xiang Wang, Borja Balle, and Shiva Prasad Kasiviswanathan. Subsampled rényi differential privacy and analytical moments accountant. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1226-1233 1235. PMLR, 2019.
David Williams. Probability with martingales. Cambridge University Press, 1991.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mmist: a novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv: (70.::7770077444 2017.
Liyang Xie, Kaixiang Lin, Shu Wang, Fei Wang, and Jiayu Zhou. Differentially private generative adversarial network. arXiv preprint arXiv:1802.06679, 2018.
Lei Xu, Maria Skoularidou, Alfredo Cuesta- Infante, and Kalyan Veeramachaneni. Modeling tabular data using conditional gan. Advances Neural Information Processing Systems, volume 32, 2019.
Jun Zhang, Graham Cormode, Cecilia M Procopiue, Divesh Srivastava, and Xiaokui Xiao. Privbayes: Private data release via bayesian networks. ACM Transactions on Database Systems (TODS), 42 (4):1-41, 2017.
Zhikun Zhang, Tianhao Wang, Ninghui Li, Jean Honorio, Michael Backes, Shibo He, Jiming Chen, and Yang Zhang. PrivSyn: Differentially private data synthesis. In 30th USENIX Security Symposium (USENIX Security 27). pp. 929-946, 946, 2021.
12

---

Published as a conference paper at ICLR 2022
A ADDITIONAL DEFINITIONS AND PREVIOUS RESULTS
Definition 5 (Rényi differential privacy). A randomized mechanism M is said to satisfy e-Rényi differential privacy of order X, when
DxM(d)))Mdd) = x log M(d)
(PriM(d)=2) =
x
SE
satisfied for any adjacent datasets and d'. Here, Dx(PIIQ) x-1 log Ex ( (P()) [())) is the Rényi divergence. Furthermore, a s-RDP mechanism of order is also (e+ + log 1/5 A-1 -DP
Next, we note that the Gaussian mechanism is (A; 20th
Adaf2 J-RDP (Mironov 2017 The particular
advantage of using RDP is that it gives convenient way of tracking the privacy costs when sequence of mechanisms is applied. More precisely, the following theorem holds (Mironov (2017))
Theorem 4 (RDP Composition), For sequence of mechanisms MI.... Mr s.t. M, is (A, ei) RDP Vi, the composition M1 o Mg is (X, >i R-)-RDP.
We use the autodp package keep track of the privacy budget (Wang et al. (2019)
B PROOFS
B.1 PROOF OF THM.
Proof. Let Pr denote the real data distribution, Qe denote the data distribution generated by Go using latent vector, sampled from pre-determined distribution, and sampling distribution. denotes the modulus of :. Then, the CFD between the distributions is
Ca (Pr, Q2) Be
pp. (t) 22 (t))
pp, where Pt((t) = Exxx [e is the CF of IP. For notational brevity, we write Dp, (t) as (t),,, and & (t) as (t) in the following.
We consider the optimized CFD, supC Q9). and would like show that it is locally Lips- wEn
chitz. g which subsequently means that it is continuous. Since the Radamacher's theorem (Federer (2014) implies that any locally Lipschitz function is differentiable almost everywhere, the claim of differentiability is also justified once the Lipschitz locality is proven.
We first note that the difference of two maximal functions" values is smaller equal to the maximal difference of the two functions. Then, for any A and 6',
SupC2(P, Qo) wen
supC Qoo) sup -o) Qo.) wen
weft
We note that the absolute difference of any two complex values represented in terms of its real-number amplitude (A, B) and phase (a, ,3 satisfies Aeea Be < |A| + BB. Writing the maximal w as w", the RHS of Eq. 9 can be written as
C3. (P,, Q2) CB. (IPr, Qa
(10)
(P,, Ee)wr(() (t) [(Cu- (P,, Qv) + Cu- (C. Qo)
Cu. (P, Car)
= Ee)wr(() (t) ((] - [ + (,, - 2y (t)) Do(t)] - 1b, T (t)))
< E Be (4) (t) + [2)(t)] + (t)) - - 2 (t)))
4E Al (t) (t), +x(()] (t) tba (t))
(6)
< (E) (t) - 26 (t)]],
'A function f is locally Lipschitz if there exist constants 8 2 and M 2 0 such that J 7) 5 [f()) - f(v) 5 M |a yl for all n, y-
13

---

Published as a conference paper at ICLR 2022
where have used (a) | 1, (b) triangle inequality. By interpreting complex number as a vector on 2D plane, and using trigonometric arguments, one can deduce that le -eahl = 2 sin(la bl/2) S a bl. Then,
[ (E - E. 41E (t)) [[ Do (t)]] = 4E, (t)
(11)
tow (t) [R-lit Go(z) (z)ll
4 (t) Bz l|t| (Go(z) - Gor (z)].
In (c), we have also used the Jensen inequality. In (d), the Cauchy-Schward inequality has been applied. As we are assuming that Go is L(0, Li-sspcchtzzz function, we have
E Bz [|t]- (G((2) Go (=)]] - 4E, (c) E. z)] 10 0%
(12)
Since are also assuming that Be- (t) |||||, E. [L(0,2) 2)] cc, have shown that supC., is wEn
locally Lipschitz, as required. It therefore continuous and differentiable almost everywhere, as discussed above.
B.2 PROOF OF TIM.
Proof. We denote x,, ~ P,, and x ~ P, and w" the maximal function of w. Notice that
C (Pn, IP) = E Ex (t)
Exx [e [e]txx]] - Ex [ [txx 27
= Etow' (t)
[Ex,, [eltrx]]
- Ex [ctt(]] Bxx,
[e Ex [c]tb
(a)
E Exon" (t:)
Exxn [c
Ex [ettix]
(b)
< 2 Ex (t) Exx.x (leit - ettxx
(6) 2 Ex (t) [|t|] Ex,,x [|x,
-x|1-
(13)
Here, (a) uses Ae uses the argument le convergence equivalence Klenke (001)). the RHS of Eq. 13 approaches zero as IP, Dg P. hence proving the theorem.
B8 18
< A + B as argued above Eq. 10 (b) uses Jensen inequality; (c)
cib
2
sin a 61/2) la bl given above Eq. 11 Then, by weak
B.3 PROOF OF LEMMA.
Proof. Recall that for any two distributions, wtt), wo(t) and any function f(t).
E. [.[s(t)] = / ( (tt)
/ f(t)
w())
wo(t) wo())dt
w(t)
Ews (f() wb(()
Hence, [f(t)(((tt] = Ex,, (f(t) w(()) J. Let w" be the maximal probability distribution. It is then wn(t)] clear that [f)) [f)) implies E.,, [f(t) (f())="(() (() Eg- [f())), desired.
C EXPERIMENTAL SETUP OF TWO-SAMPLE TESTING ON SYNTHETIC DATA
Let describe in more detail the experiment presented in Sec. 4 Data generated from two unriivariance multivariate Gaussian distributions P. Q where all dimensions but one have zero mean (P (Oa. Ia), Q N 0, O) I2)).. We wish to conduct two-sample test using the CF to
14

---

Published as a conference paper at ICLR 2022
distinguish between the two distributions, which gets more difficult the dimensionality increases. We test if the null hypothesis where the samples are drawn from the same distribution is rejected.
Three sets of frequencies considered. The number of frequncies in each set is set 20. The first set is an "unoptimized" set of frequencies. The first dimension of all but one frequency has the value of zero. Other dimensions have values generated randomly from zero-mean unit- variance multivariate Gaussian distribution. We denote the frequency with non-zero value in the first dimension by to without loss of generality. A "normal" set of frequencies is also considered for comparison, where the frequencies of all dimensions are sampled randomly from multivariate Gaussian distributions. Finally, we consider an "optimized" set of frequencies, where from the "unoptimized" set of frequencies, only to is selected to be used for two-sample testing. In other words, we re-weight the set of frequencies such that all but to has zero weight. 1,000 samples are generated from each of P and Q. We repeat the problem for 100 trials to obtain the rejection rate (and repeat the whole experiment 5 times get the error bar).
D DP ESTIMATE OF THE MEAN OF PAIRWISE DISTANCE
Median heuristic is applied widely in kermel methods applications to determine the bandwidth of the radial basis function (RBF) kernels (Garreau et al. (2017). The bandwidth taken be the median of all pairwise distances of data samples. Here we give DP estimation of the mean instead as the calculation of mean more tractable. Let x be samples of certain data distribution of dimension and assume that the values lie in [0, 1j Given n samples, there is total of n 1)/2 pairwise distance pairs. Then, the mean of the pairwise distance of samples
2
(x,()) n(n 1)
||:
X1112-
where || |l2 indicates the Euclidean norm.
Consider pair of neighboring datasets, D, D' Without loss of generality, let x, * x", and x; = x/ for # n. Then, the sensitivity of D (x) is
2
A (x)
max D
x
x1112
|x} - x,112
nnn
n(n 1) itj
2
2
Σ
||x: - xn|12 1
n-1
Σ
|| x/1112
n( 1)
D,D
i=1
i=1
(b)
(n 1)vd
n(n 1)
2/d
n
In (a), we cancel out all terms unrelated to x, or Xn, In (b), we use the fact that ||x; xx,-x,ll 12 and | - x ll lie in [0, Vdl. After obtaining the sensitivity, one can then applies the Gaussian mechanism as 6 to obtain the DP estimate of the mean of the pairwise distance of samples.
E TRAINING ALGORITHM
The pseudo-code of the proposed training algorithm is given in Algorithm
F COMPUTATIONAL COMPLEXITY ANALYSIS
PEARL is trained based deep learning methods, which is efficient computation-wis using GPU, Nevertheless, let us give a computational complexity analysis in a traditional sense by ignoring (partially) the parallel computing capability.
15

---

Published as a conference paper at ICLR 2022
Algorithm 1: PEARL Training
Input:
Sensitive data {x]]= differential privacy noise scale ODP, number of frequencies k. base sampling distribution variance on, training iterations T, learning rates ne and J/. number of generator iterations per critic iteration Mgens batch size B, latent
distribution P=
Output: Differentially private generator Gø
Obtain auxiliary information (e.g., base sampling distribution variance do):
2 Sample frequencies {t)/=1 with NO, dnn)(
for i in {1....,A, }} do
(p,tt) = a -ド= x
@p((:) (t,) -V
A of !p! (xx)
end
7 Accumulate privacy cost E;
o(x) + (#=(t)), (t(()))
Initialize generator Gg. sampling distribution variance o
for step in (1. T) do
11
for in {1. Rgen } do
12
Sample batch [2: ==
with 2, ~ P2i
13
for i in (1..... k) do
(t,), B Σ 2==1
B
tt, Go(z,)
15
end
((z) < (fa(t)).... pt)tt))
16
0 < 0 na VoCu (Ø(x); [22)) end
Sample batch {2:) with z; P.i for i in {1. {1...., k} do
20
(t(t,) B j= ett,
end
Ō(Z) - (t)(t))..... TT(()))
23
- + Ic V VaCu (Ø(x),
end
26
Return Go
Time complexity. We sample k frequencies and calculate its inner product with data points (of dimension d), make a summation with respect data points build & CFs. Since inner product takes d steps, summation n steps, and we do it for & times, the time complexity of generating CFs is nkd. We additionally train the generative model, requiring fr- Note that unlike graphical models like PrivBayes, which gradually add nodes to the Bayesian network, our method can be parallelized efficiently with GPU. As we sample n records from the generative model during data generation, the time complexity of dataset generation is times the inference time, 4nz- The total training and inference time is O(nkd + ntinf + t.y).
Space complexity. We need store the k CF values during training. We also need to store the generative model with m parameters. The space complexity O(k + m).
G EVALUATION METRICS
We utilize evaluation metrics commonly used to evaluate GAN's performance, namely Fréchet Inception Distance (FID) (Heusel et al. (2017)) and Kernel Inception Distance (KID) Binkowski et al. (2018)). FID corresponds to computing the Fréchet distance between the Gaussian fits of the Inception features obtained from real and fake distributions. KID is the calculation of the MMD of the Inception features between real and fake distributions using polynomial kernel of degree 3.
16

---

Published as a conference paper at ICLR 2022
The precision definitions are follows. Let (x", 1)= be samples from the real data distribution Pr, and (x :] be samples from the generated data distribution Qo- The corresponding feature vectors extracted from pre-trained network (LeNet in our case) are {z' i) and {z" ) respectively. The FID and KID are defined
(I, Qo) = =11,, Mel
Tr(E, + Eg - 20,,E,))
(14)
(I Qa)
n(n 1) i= j=ljøi
[x(2) 25)1
(15)
m m(m
1)
j=1.j
2
m7
[x( 29)1
mn
where (Hr, Σ,) and (No, Eg) are the sample mean & covariance matrix of the inception features of the real and generated data distributions, and x a polynomial kernel of degree 3:
x(x,y) x
(16)
where d is the dimensionality of the feature vectors. We compute FID with 10 bootstrap resamplings and KID by sampling 100 elements without replacement from the whole generated dataset.
H IMPLEMENTATION DETAILS
Datasets. For MNIST and Fashion-MNIST. we use the default train subset of the torchvision library for training the generator, and the default subset for evaluation. For Adult, we follow the preprocessing procedure Harder al. (202T) make the dataset more balanced by downsampling the class with the most number of samples.
Neural networks. The generator for image datasets has the following network architecture:
fc - bn + + bn + upsamp - relu - upconv - sigmoid,
where fc, bn, upsamp, relu, upconv, sigmoid refers to fully connected, batch normalization, 2D bilinear upsampling, ReLU, up-convolution, and Sigmoid layers respectively. For tabular dataset, we use following architecture:
. fc + bn + relu + fc + bn + relu + fc + tanh/softmax,
where tanh and softmax the Tanh and softmax layers respectively. Network output corresponding to the continuous attribute is passed through the Tanh layer, whereas network output corresponding the categorical attribute is passed through the softmax layer, where the category with the highest value from the softmax output is set to be the generated value of the categorical attribute. We train both networks conditioned on the class labels. For DP-MERF, we use the same architectures for fair comparisons.
Hyperparameters. We use Adam optimizer with learning rates of 0.01 for both the minimization and maximization objectives. Batch size is 100 (1, for the image datasets (tabular dataset). The number of frequencies is set to 1,000 (3,000) for MNIST and tabular datasets (Fashion-MNIST), The training iterations are 6,000, 3,000, and 8,000 for MNIST, Fashion-MNIST, and tabular datasets respectively.
https://ppoocrooo.nnn/ssstttttts html
17

---

Published as a conference paper at ICLR 2022
Datasets
Methods
ROC
PRC
Range
Marginal
MMD
Adult
DP-MERF
0.64
0.54
0.10
1.37
2 10-3 1 x 10
Ours
0.72
0.62
0.06
0.71
Credit
DP-MERF
0.66
0.26
0.049
0.95
2 10-5 1 X 10
Ours
0.84
0.68
0.026
0.72
Table 3: Evaluation with ROC, PRC (higher is better), range query, marginal release and MMD (lower is better) on tabular datasets at (c, (1, 10-
Real data
DPCGAN
Ours
ROC
PRC
ROC
PRC
ROC
PRC
LR
0.788
0.681
0.501 1 0.0001
0.484 1. 0.001
0.752 1. 0.009
0.641 1. 0.0115
Gaussian NB
0.629
0.511
0.499 + 0.005
0.483 + 0.003
0.661 + 0.036
0.537 + 0.028
Bemoulli NB
0.769
0.651
0.482
0.159
0.498 + 0.091
0.763 + 0.008
0.644 + 0.009
Linear SVM
0.781
0.671
0.501 0.000
0.484 0.001
0.752 0.009
Decision Tree
0.759
0.646
0.546 + 0.056
0
0.582 0.028
LDA
0.782
0.670
0.501 0.002
0.484 0.002
0.755 + 0.005
0.640 + 0.007
Adaboost
0.789
0.682
0.523 4: 0.065
0.5 : 0.036
0.709 +: 0.031
0.628 1 0.024
Bagging
0.772
0.667
0.546 +: 0.082
0.516 + 0.058
0.687
0.601 + 0.039
GBM
0.800
0.695
0.544 + 0.101
0.518 + 0.066
0.709 0.029
0.635 + 0.025
MLP
0.776
0.503 0.004
0.486 + 0.004
0.744
0.635 0.015
Table 4: Quantitative results for the Adult dataset evaluated at (c,8) = (1, 10-9).
1 ADDITIONAL RESULTS
1.1 ADDITIONAL. TASKS AND DATASET FOR TABULAR DATA
We here present more results relevant to PEARL's generative modeling of tabular data. We first compare PEARL with DPCGAN in Table Jusing the same classifiers as in the main text.
Three additional metrics/tasks are utilized: Range query. 1000 range queries containing three attributes are sampled randomly. The average 1 eтror between the original and synthetic datasets is evaluated. Marginal release. All 2-way marginals are calculated and average error evaluated. MMD. The max mean discrepancy (MMD) between the original and synthetic dataset is evaluated. We use the MMD because it is a powerful measure that could in principle detect any discrepancy between two distributions. A Gaussian kernel is used in the evaluation.
Additionally, we perform evaluation on another tabular dataset: Credit (Dal Pozzolo et al. (015 Our results comparing with DP-MERF shown in Table B demonstrate that PEARL is competitive with various tasks and datasets.
1.2 MNIST AND FASHION- IMAGES
Fig and Fig. 6 show more enlarged images of MNIST and Fashion-MNIST at various level of generated with PEARL. We also show images generated by PEARL but without critic, and DPGAN. Note that we are unable to generate meaningful images from DP-MERF after taking privacy into account appropriately (see Sec. 5)
I.3 ADULT IISTOGRAMS
We show more histogram plots for continuous and categorical attributes comparing our method with DP-MERF in Fig. 9 and Fig. 10
18

---

Published as a conference paper at ICLR 2022
0 2
3
9
6
6
7
8 9
0 1
2
3
7 5
6
7
9
0 12220
4
6
7
8 0
01 J 2
3
11
5 6
7
8
9
0) 1 0
6
012.3
4 5 7
8
9
3123456760
O 0
3
/ 9
1
C 6123456729
0/2345t5
8
0 0 7
O 0123% 335679
8
4
O [ 2
3 9 5
6
8
0 0
3
J 5
6
7
8
0 3 4 01234
0
2
4
1
1
6
7
4
9 9
0 1
4
3
1 4
8
0
[
3
9
5
6
8
(a)
(b) 10
0 /
2
3
4
5
6
7
8 9
45 1 2.
3
1
4
5
7 9
01.33
41
5
2
9
0
4 4 89
0.1.2. 3
1
0123W2678 8
4
9 0 2
012347467
Q 2 8
7772456678
0 17331077
0 8
0 12214667
4 4123456 6
8
0 / 53445777
O 0
8 9
5 0
!
1 1 55
7
2 9
7
c=)=1
(d) 0.2
Figure Additional generated MNIST images various
19

---

Published as a conference paper at ICLR 2022
(a)
(b) c= 10
(c) 1=1
(d) 0.2
Figure 6: Additional generated Fashion-MNIST images at various c.
0
(a) 1, MNIST (DPGAN)
(b) 1, FMNIST(DPGAN)
Figure 7: Images generated by DPGAN at
0
2
7
4
6
7 -
9
0
2
3
4
0
6
7
t
9
0
1
3
7
4
5
6
7
0
9 0
0
7
1
6
7 7
7
4.
2
?
9
0
8
9
(a) 1, MNIST (Ours w/o critic)
(b) 1, (OUSST w/o critic)
Figure 8: Images generated by our proposal (PEARL) but without critic
20

---

Published as a conference paper at ICLR 2022
DP-MERF
Ours
real syntheic
10
10
10aa
10
Age
DP-MERF
Ours
synthetic
10
10a
10
10t
10
0.30
0.25
0.50
0.75
1.00
1.25
0.00
0.25
0.50
0.75
1.00
1.25
166
166
(b) fnlwgt
DP-MERF
Ours
real
10-4
10a4
10a4
10
10-5
10
10'7
20000
40000
60000
80000
100000
20000
40000
80000
80000
100000
(c) Capital Gain
DP-MERF
Ours
meil
10-4
10a4
10:4
10-4
1.000
2000
3000
4000
1000
2000
3000
4000
(d) Capital loss
Figure 9: Histograms of various continuous attributes of Adult dataset comparing real and synthetic data.
21

---

Published as a conference paper at ICLR 2022
Real
Real
127
DP-MERF
DP-MERF
categary
(a) Education
(b) Occupation
Real
Real
Ours
Ours
13P
DP-MERF
DP-MERF
134
2.0
6.0
5.0
2.0
5.0
ratepery
canegory
(c) Work class
(d) Relationship
Real
Ours
DP-MERF
DP MERF
6x100
0.0
1.0
(e) Sex
Race
Figure 10: Histograms of various categorical attributes of Adult dataset comparing real and synthetic data.
22


Reviews:
[{"review_id": "wtP8g4ubnFs", "reviewer": "Reviewer_Xui7", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The strengths and weaknesses of this paper are summarized as follows:\nStrengths:\n+ The problem studied in this paper is important and needs to be solved in data synthesis\n+ Good writing\n+ Sufficient theoretical analysis\n\nWeaknesses:\n- Need to include more related work that is highly important\n- Need more justifications about the novelty claims \n- Need to add more benchmark datasets\n- Need to add more advanced baselines\n- Lack of complexity analysis\n\nComments:\n1. The following important references are missing:\n\n[1] Zhang Z, Wang T, Li N, et al. Privsyn: Differentially private data synthesis[C]//30th {USENIX} Security Symposium ({USENIX} Security 21). 2021.\n\n[2] He, Xi, et al. \"DPT: differentially private trajectory synthesis using hierarchical reference systems.\" Proceedings of the VLDB Endowment 8.11 (2015): 1154-1165.\n\n[3] Cai, Kuntai, et al. \"Data synthesis via differentially private Markov random fields.\" Proceedings of the VLDB Endowment 14.11 (2021): 2190-2202.\n\n2. How to implement privacy-preserving optimization in this paper is vague. It would be better if the authors could add more details, especially how to perform one-shot sampling. In addition, the authors need to explain how the one-shot sampling strategy guarantees privacy.\n3. It would be better if the authors could add 1-2 more public datasets to verify the performance of the proposed framework. For example, the Colorado dataset is the census dataset of Colorado State in 1940, which is used in the final round of the NIST challenge.\n4. It would be better if the authors could add 1-2 more baseline schemes (e.g., PrivBayes, PGM, and PrivSyn) to verify the performance of the proposed framework.\n5. Like [1], it gives a detailed analysis of the computational complexity of the algorithm. Therefore, it would be better if the authors could give an analysis of the computational complexity of the proposed algorithm.\n6. In [1], the authors evaluated the statistical performance of the synthesized datasets on three data analysis tasks (i.e., Marginal Release, Range Query, and Classification). Therefore, it would be better if the authors could add more tasks to verify the proposed algorithm.\n7. The editorial quality of this paper is not always satisfactory. It contains quite a lot of inconsistent/non-precise descriptions, as also reflected in the above comments.\n", "summary_of_the_paper": "This paper studied an important topic in the field of data synthesis: how to train a private deep generative model without reusing the original data. In this paper, the authors proposed a new framework that uses deep generative models to synthesize data in different private ways. Unlike popular gradient cleaning methods, the framework proposed in this paper does not incur additional privacy costs or model constraints. In addition, in order to avoid the problem of reduced privacy guarantee as training iterations increase, this paper used feature functions and adversarial re-weighting objectives to solve the above problems. Both theory and extensive case studies verify the performance of the proposed framework. ", "summary_of_the_review": "The paper tackles a very interesting problem, and the many technical considerations and the experiments on various datasets and comparisons with existing data synthesis techniques are commendable. Some issues (unclear privacy-preserving optimization method, need to add baselines and benchmark datasets) still prevent me from recommending complete acceptance. More clarifications are necessary, and by adding some more \"realistic\" experiments, I believe the paper could be turned into a significant submission of ICLR. I recommend a \"5\", but my score can be easily increased to 6 by addressing the many clarifications expressed in my review. Further experiments and the concrete use-case would further improve my score.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "rmuhPMXAvVB", "reviewer": "Reviewer_kXZv", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "PEARL, a method to generate synthetic data with privacy preservation is proposed. Please see my detailed comments below:\n\n1. I am a bit confused by the auxiliary information release, is the total privacy budget split for this information and the training, or does information is \"free\"?\n\n2. I am also confused by the sensitivity calculation, especially the factor k, can authors explain where does that come from? Isee they have used it from l2 norm, but please explain how is that equal to k.\n\n3. I see no visible difference when epsilon is increased from 1-10-infinity, does PEARL's performance saturates at a privacy budget?\n\n4. It will be nice to compare PEARL with other generative methods such as PATE-GAN, CTGAN for tabular data etc.\n", "summary_of_the_paper": "Paper proposes a method for synthetic data generation called PEARL.", "summary_of_the_review": "Paper proposes a new method (PEARL) to generate synthetic data based on CFs. It is a nice approach that seems to work.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "p333PeSmmqQ", "reviewer": "Reviewer_qSyM", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The main strengths of the paper in my opinion are: \n1) The approach is quite well motivated and the paper is well written. \n2) The mathematical formulation is easy to follow and the approach is indeed quite novel \n3) At least in the few empirical evaluations, this approach compares favorably against the other approaches compared against. \n\nIt seems to me, the main weakness of the paper is the lack of thorough benchmarking. For tabular data, it would be nice to see how the approach against PATE-GAN and on more than one dataset. For image data, it would be nice to see the benchmarking done on at least one somewhat more complex dataset (maybe CIFAR-10). \n\nOne minor comment is that the authors should consider moving algorithm 1 to the main paper. ", "summary_of_the_paper": "In this paper, the authors propose a novel differentially private approach to generate both continuous as well as discrete valued synthetic data. The authors utilize a one shot approach to providing the privacy, by first generating privatized embedding of the sensitive dataset. The privatized embeddings are then iteratively compared against the synthetic samples generated by the generator module using the characteristic function distance. The approach is similar to and can be considered a generalization of another new approach DP-MERF and seems to compare favorably in empirical experiments against DP-MERF and DP-GAN (two popular alternative approaches). ", "summary_of_the_review": "The paper presents a novel and well motivated approach to privacy preserving generative modeling. The approach has nice theoretical properties and compares well against other approaches on the few benchmark scenarios that the authors have looked at. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents a new framework of synthesizing differential private data using deep generative models. Reviewers liked the significance of the problem. They raised some concerns which was appropriately addressed in the rebuttal.  We hope the authors will take feedback into account and prepare a stronger camera ready version.
Decision: Accept (Poster)