Year: 2021

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.

heading: 1 INTRODUCTION
text: Synthesizing data under differential privacy (DP) (Dwork (2006; 2011); Dwork & Roth (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 (Takagi et al. (2020); Xie et al. (2018); Torkzadehmahani et al. (2019); Frigerio et al. (2019); Yoon et al. (2019); Chen et al. (2020); Harder et al. (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, Harder et al. (2021) has proposed DP-MERF, which first represents the sensitive data as random features in a DP manner and then learns a generator by minimizing the discrepancy between the (fixed) representation and generated data points. DP-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 to 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 ' 1.) We propose a private learning framework called PEARL (Private Embeddings and Adversarial Reconstruction Learning). In this framework, we have i) no limitation in learning iterations, and ii) well-reconstruction 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 a differentially private manner, then (3) the generative model is trained implicitly like GANs via the private embedding and auiliary information, where the learning is based on a stochastic procedure that generates data, and (4) a critic distinguishing between the real and generated data. The overview of PEARL is illustrated in Fig. 1.
As a concrete realization of PEARL, We first identify that the characteristic function (CF) representation of 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-using the original data. As will be explained in detail in later Sections, the generative modelling approach using CFs also
involves sampling “frequencies” from an ad hoc distribution, to project the data to the embedding. It is desirable to optimize the sampling distribution to better represent the data as an embedding, but the naive way of optimizing it would require re-accessing the data via sampling, coming at a cost of privacy budget. Henceforth, we also propose to incorporate a privacy-preserving critic to optimize the sampling strategy, which, through re-weighting, chooses the best representation from a fixed samples of frequencies without extra privacy costs.
To this end, we propose the following minimax optimization training objective:
inf θ∈Θ sup ω∈Ω k∑ i=1 ω(ti) ω0(ti) ∣∣Φ̃Pr (ti)− Φ̂Qθ (ti)∣∣2. (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 differentiability of the generator’s parameters, and continuity in weak topology. We also prove the consistency of our privacy-preserving sampling strategy at the asymptotic limit of infinite sampling. Empirical evaluations show that PEARL is able to high-quality synthetic data at reasonable privacy levels.
Related works. Traditional methods of synthesizing data are mainly concerned with discrete data or data preprocessed to the discrete form (Zhang et al. (2017); Qardaji et al. (2014); He et al. (2015); Chen et al. (2015); Cai et al. (2021); Zhang et al. (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. (2020); Xie et al. (2018); Torkzadehmahani et al. (2019); Frigerio et al. (2019); Yoon et al. (2019); Chen et al. (2020); Harder et al. (2021)). The private training of deep generative models is usually performed using gradient sanitization methods. An exception is DP-MERF (Harder et al. (2021)), which is closest to our work. There, random features used to approximate the maximum mean discrepancy (MMD) objective are privatized and utilized for training a generator. PEARL, which, as a realization, uses CFs, may be viewed as a generalization of DP-MERF. Additionally, PEARL has several distinctive features which are lacking in DP-MERF. The first lies in the introduction of a privacy-preserving critic, which leads to an improvement of performance. The second is the private selection of the parameter of the sampling distribution, which is also shown to be vital. Moreover, DP-MERF uses non-characteristic 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 et al. (2020)) .
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 use 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 ( ' 1).

heading: 2 PRELIMINARIES
text: This Section gives a brief review of essential preliminaries about differential privacy, characteristic function and the related notations.

heading: 2.1 DIFFERENTIAL PRIVACY
text: Definition 1 (( , δ)-Differential Privacy). Given privacy parameters ≥ 0 and δ ≥ 0, a randomized mechanism,M : D → R with domain D and rangeR satisfies ( , δ)-differential privacy (DP) if for any two adjacent inputs d, d′ ∈ D and for any subset of outputs S ⊆ R, the following holds:
Pr[M(d) ∈ S] ≤ e · Pr[M(d′) ∈ S] + δ. (2)
We next consider concrete ways of sanitizing certain outputs with DP. A typical paradigm of DP is applying the randomized mechanism,M, to a certain deterministic function f : D → R such that the output of f is DP. The noise magnitude added byM is determined by the sensitivity of f , defined as ∆f = supd,d′∈D ‖f(d)− f(d′)‖, where || · || is a norm function defined on f ’s output domain. d 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 & Roth (2014)): Definition 2 (Gaussian Mechanism). Let f : X → R be an arbitrary function with sensitivity ∆f . The Gaussian Mechanism,Mσ , parameterized by σ, adds noise to the output of f as follows: Mσ(x) = f(x) +N (0, σ2I). (3) One of the most important properties of DP relevant to our work is the post-processing theorem (Dwork & Roth (2014)): Theorem 1 (Post-processing Theorem). LetM : D → R be ( , δ)-DP and let f : R → R′ be an arbitrary randomized function. Then, f ◦M : D → R′ is ( , δ)-DP.
It ensures that the DP-sanitized data can be re-used without further consuming privacy budgets.

heading: 2.2 CHARACTERISTIC FUNCTIONS
text: 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 (1991)). The definition is as follows. Definition 3 (Characteristic Function). Given a random variable X ⊆ Rd and P as the probability measure associated with it, and t ∈ Rd, the corresponding characteristic function (CF) is given by
ΦP(t) = Ex∼P[eit·x] = ∫ Rd eit·xdP. (4)
Here, i 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 t. It is noted that we deal with the discrete approximation of CFs in practice. That is, given a dataset with n i.i.d. samples, {xj}nj=1 from P, the empirical CF is written as Φ̂P(t) = 1n ∑n i=j e
it·xj . We next introduce characteristic function distance (CFD) (Heathcote (1972); Chwialkowski et al. (2015)): Definition 4 (Characteristic Function Distance). Given two distributions P and Q of random variables residing in Rd, and ω a sampling distribution on t ∈ Rd, the squared characteristic function distance (CFD) between P and Q is computed as:
C2(P,Q) = Et∼ω(t)[ ∣∣ΦP(t)− ΦQ(t)∣∣2] = ∫
Rd ∣∣ΦP(t)− ΦQ(t)∣∣2ω(t)dt. (5) Notations. Let us make a short note on the notations before continuing. Let k be the number of t drawn from ω and P be the probability measure of a random variable. We group the CFs associated to P of different frequencies, (Φ̂P(t1), . . . , Φ̂P(tk))> more compactly as φ̂P(x). To make the dependence of φ̂P(x) on the sampled data explicit, we also use the fol-
lowing notation: φ̂P(x) = 1n ∑n j=1 φ̂P(xj). We notice that ‖φ̂P(x)‖2 ≡ √∑k m=1 |Φ̂P(tm)|2 =√∑k
m=1 | ∑n l=1 e itm·xl/n|2 ≤ √∑k m=1 | ∑n l=1 1/n|2 = √ k, where the norm is taken over the
(complex) frequency space. With a slight abuse of notation, we abbreviate φ̂P as φ̂ when there is no ambiguity in the underlying probability measure associated with the CF.

heading: 3 GENERATIVE MODEL OF PEARL
text: 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 Pr, and the output distribution of an implicit generative model Gθ by Qθ. Let n be the total number of real data instances and consider releasing k CFs from the dataset. Then, Gθ trained to optimize the empirical CFD, min
θ∈Θ Ĉ2(Pr,Qθ) with the CF
sanitized according to the Gaussian mechanism (Defn. 3) with sensitivity 2 √ k/n satisfies ( , δ)-DP, where σ ≥ √ 2 log(1.25/δ)/ .
Proof. In the following we give a detailed explanation of the above Proposition. The first step of PEARL is projecting the data to the CF as in Eq. 4, where the number of embeddings is the number of frequency drawn from ω(t).
We note that CF has several attractive properties. CF is uniformly continuous and bounded, as can be seen from its expression in Eq. 4. Unlike the density function, the CF of a 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. 3) to φ̂(x):
φ̃(x) = φ̂(x) +N (0,∆2 φ̂(x) σ2I), (6)
where we write the sanitized CF as φ̃(x); ∆φ̂(x) denotes the sensitivity of the CF, σ denotes the noise scale which is determined by the privacy budget, ( , δ).
The calculation of sensitivity is tractable (no ad-hoc clipping commonly required by gradient sanitization methods) Without loss of generality, consider two neighboring datasets of size n where only the last instance differs (xn 6= x′n). The sensitivity of φ̂(x) may then be calculated as
∆φ̂(x) = maxD,D′ ∥∥∥∥∥∥ 1n n∑ j=1 φ̂(xj)− 1n n∑ j=1 φ̂(x′j) ∥∥∥∥∥∥ 2 = max xn,x′n ∥∥∥ 1n φ̂(xn)− 1n φ̂(x′n)∥∥∥ 2 = 2 √ k n ,
where we have used triangle inequality and ‖φ̂(·)‖2 ≤ √ k. It can be seen that the sensitivity is proportional to the square root of the number of 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, as will be discussed in later Sections.
We would like to train a generative model where the CFs constructed from the generated data distribution, Y ⊆ Rd, matches those (sanitized) from the real data distribution, X ⊆ 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 θ, Gθ : Z → Rd, which takes a low-dimensional latent vector z ∈ Z sampled from a pre-determined distribution (e.g., Gaussian distribution) as the input.
In order to quantify the discrepancy between the real and generated data distribution, we use the CFD defined in Eq. 5. Empirically, when a finite number of frequencies, k, are sampled from ω, C2(P,Q) is approximated by
Ĉ2(P,Q) = 1 k k∑ i=1 ∣∣Φ̂P(ti)− Φ̂Q(ti)∣∣2 ≡ ∥∥∥φ̂P(x)− φ̂Q(x)∥∥∥2 2 , (7)
where Φ̂P(t) and Φ̂Q(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 θ ∈ Θ that minimizes the empirical CFD: min
θ∈Θ Ĉ2(Pr,Qθ). It can be shown via uniqueness theorem that as long as ω resides in
Rd, C(P,Q) = 0 ⇐⇒ P = Q (Sriperumbudur et al. (2011)). This makes CFD an ideal distance metric for training the generator.
Optimization procedure. The generator parameter, θ, is updated as follows. φ̂Pr (x) is first sanitized to obtain φ̃Pr (x), as in Eq. 6. This is performed only for once (one-shot). Then, at each iteration, m samples of z are drawn to calculate φ̂Qθ (x). Gradient updates on θ are performed by minimizing the
CFD, ∥∥∥φ̃Pr (x)− φ̂Qθ (x)∥∥∥
2 .
We note that only the first term, φ̃Pr (x), has access to the real data distribution, X , of which privacy is of concern. Then, by Thm. 1, Gθ trained with respect to φ̃Pr (x) is DP. Furthermore, unlike gradient sanitization methods, the training of Gθ is not affected by network structure or training iterations. Once the sanitized CF is released, there is no additional constraints due to privacy on the training procedure.
DP release of auxiliary information. Auxiliary information, e.g., hyperparameters regarding to the dataset useful for generating data with better quality may be obtained under DP. In our case, one may extract auxiliary information privately from the dataset to select good parameters for the sampling distribution ω(t). This will be discussed in 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 et al. (2019)). GMMs are trainable under DP using a DP version of the expectation-maximization algorithm (Park et al. (2017)). The total privacy budget due to multiple releases of information is accounted for using the Rényi DP composition. See App. A for the definition of Rényi DP.

heading: 4 ADVERSARIAL RECONSTRUCTION LEARNING
text: This Section is devoted to proposing a privacy-preserving critic for optimizing ω(t), while giving provable guarantees of performance.
Back to Eq. 5 and Eq. 7, we note that choosing a “good” ω(t) or a “good” set of sampled frequencies is vital at helping to discriminate between P and Q. For example, if the difference between P and Q lies in the high-frequency 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-optimized ω(t), 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 as a critic, where the empirical CFD is maximized by finding the best sampling distribution. We consider a training objective of the form
inf θ∈Θ sup ω∈Ω Ĉω
2 (Pr,Qθ), (8)
where Ω is some set of probability distribution space of which the sampling distribution ω lives in.
Privacy-preserving optimization. It is intractable to directly optimize ω 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 ω), optimization is performed without further spending the privacy budget. We believe that such a 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 as the dimensionality increases. We test if 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 is the most discriminative dimension for distinguishing the distributions. We consider three sets of
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. 2 shows the hypothesis rejection rate versus the number of dimensions for the three cases considered above. As can be observed, the “optimized” case gives overall the best test power. While this experiment is somewhat contrived, it can be understood that although both “unoptimized” and “optimized” sets of frequencies contain the discriminative t0, the re-weighting procedure of selecting the most discriminative CF improves the test power significantly. Even without re-sampling from a “better” ω(t), reweighting the existing frequencies can improve the test power. The fact that re-weighting can improve the test power is crucial privacy-wise because the altenative method, re-sampling, causes degradation in privacy.
Proposal. Recall that the empirical CFD, Ĉ2(Pr,Qθ) = 1k ∑k i=1 ∣∣Φ̃Pr (ti)− Φ̂Qθ (ti)∣∣2, is obtained by drawing k frequencies from a base distribution ω0. Our idea is to find a (weighted) set of frequencies that gives the best test power from the drawn set. We propose Eq. 1 as the optimization objective, restated below:
inf θ∈Θ sup ω∈Ω k∑ i=1 ω(ti) ω0(ti) ∣∣Φ̃Pr (ti)− Φ̂Qθ (ti)∣∣2. Note that the generator trained with this objective still satisfies DP as given in Prop. 1 due to Thm. 1. The following Lemma ensures that the discrete approximation of the inner maximization of Eq. 1 approaches the population optimum as the number of sampling frequency increases (k →∞): Lemma 1. Let ω0 be any probability distribution defined onRd, and let f : Rd → R′ be any function. Also let t ∈ Rd and ω∗ be the maximal distribution of ω with respect to Eω[f(t)] ≡ ∫ f(t)ω(t)dt.
Assume that the empirical approximation Êω[f(t)] → Eω[f(t)] at the asymptotic limit for any ω. Then, Êω0 [f(t) ω∗(t) ω0(t) ]→ Eω∗ [f(t)] at the asymptotic limit as well.
The proof is in App. B, and is based on importance sampling. Empirically, we find that treating ω(ti) 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 on 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 to {µ,σ} if ω is of the Gaussian form, N (µ,σ2). Performance guarantees. Let us discuss the theoretical properties of Eq. 8. The objective defined in Eq. 8 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 parameters. Second, the distance is continuous in weak topology, and thus provides informative feedback to the generator (different from, e.g., the JensenShannon 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 Gθ(z) is locally Lipschitz with respect to (θ, z); there exists L((θ, z) satisfying Ez [L(θ, z)] <∞; and supω∈Ω Eω [|t|] <∞ for all t. Then, the function supω∈Ω C2ω(Pr,Qθ) is continuous in θ ∈ Θ everywhere, and differentiable in θ ∈ Θ 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 Gθ to be trained via gradient descent. The theorem related to continuity in weak topology is the following: Theorem 3. Let P be a distribution on X and (Pn)n∈N be a sequence of distributions on X . Under the assumption supω∈Ω Eω(t) [‖t‖] < ∞, the function supω∈Ω C2ω(Pn,P) is continuous in the
weak topology, i.e., if Pn D−→ P, then supω∈Ω C2ω(Pn,P) D−→ 0, where D−→ denotes convergence in distribution.
Weakness is desirable as the easier (weaker) it is for the distributions to 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 eia) can be bounded as follows: |eia − eib| ≤ |a− b|, and showing that the function is locally Lipschitz, which ensures the desired properties of continuity and differentiability. See App. B for the full proofs.

heading: 5 EXPERIMENTS

heading: 5.1 EXPERIMENTAL SETUP
text: 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 (Dua & Graff (2017)). Neural networks constructed from convolutional and fully connected layers are utilized as the generator for image and tabular datasets respectively. Detailed setups are available in App. H.
Training Procedure. As our training involves minimax optimization (Eq. 1), we perform gradient descent updates based on the minimization and maximization objectives alternately. We use a zeromean diagonal standard-deviation Gaussian distribution, N (0,diag(σ2) as the sampling distribution, ω. Maximization is performed with respect to σ. Let us give a high-level description of the full training procedure: draw k frequencies from ω, 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. E. We further give the computational complexity analysis of our algorithm in App. F.
DP release of auxiliary information. We also note that applying maximization (re-weighting) on a randomly selected set of frequencies would not work well. We initially fix the inverse standard deviation of the base distribution, ω0, to be the DP estimate of the mean of the pairwise distance of the data, to obtain (privately) a spectrum of frequencies that overlaps with the "good" frequencies. This is motivated by the median heuristic (Garreau et al. (2018)). Mean is estimated instead of median as its sensitivity is more tractable when considering neighboring datasets. We obtain ∆ = 2 √ d/n as its sensitivity, where d and n are the data dimension and the number data instances respectively. See App. D for the derivation. 1 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. I, we show qualitative results, i.e., 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) (Bińkowski et al. (2018)) are used to evaluate the quantitative performance. For tabular data, we use the synthetic data as the training data of 10 scikit-learn 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 characteristics curve) and PRC (area under the precision recall curve) are the evaluation metrics. We provide the definitions and details of FID and KID in App. G.

heading: 5.2 EVALUATION DETAILS
text: MNIST and Fashion-MNIST. Privacy budget is allocated equally between the sanitization of CFs and the release of auxiliary information. 2 On a single GPU (Tesla V100-PCIE-32GB), training MNIST (with 100 epochs) requires less than 10 minutes.
1We note that DP-MERF also uses a sampling distribution. Since privacy budget is not allocated for calculating the parameters of the sampling distribution there, we fix its sampling distribution to beN (0, diag(1)).
2We 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 fairness reasons, as tuning the budget allocation would require re-using the private data and this can lead to privacy leakage.
Some of the generated images of ours and baseline models are shown in Fig. 3, and more (including baselines’) can be found in App. I. 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 a discriminator-like network as in the vanilla GAN framework. However, we notice that the quality of the images does not drop much as the privacy level increases (except at = 0.2, where the quality starts to degrade visibly) because the noise added to the CFs 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 ( , δ) = (1, 10−5). 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. (2021)). Particularly, the claim “values of that offer no meaningful theoretical guarantees” ( 1) can be chosen in practice has been “refuted” in general (Nasr et al. (2021)). This motivates us to perform evaluation at with meaningful theoretical guarantees ( ' 1). At this privacy region, we compare PEARL with models using gradient sanitization and DP-MERF (Harder et al. (2021)) as other methods do not produce usable images at single-digit . 3 We run the experiment five times (with different random seeds each time), and for each time, 60k samples are generated to evaluate the FID and KID. In Table 1, 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 to improvement in the scores.
Adult. The Adult dataset consists of continuous and categorical features. As data pre-processing, 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 CFs share equal budget of privacy, and we perform evaluation at ( , δ) = (1, 10−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 is able to model the real data better than DP-MERF, e.g., covering more modes in the categorical variable “marital-status” with less discrepancy in the frequency of each mode. PEARL is also able to better model the descending trend of the continuous variable
3In the gradient sanitized generative model literature, GS-WGAN (Chen et al. (2020)) is known to be the state-of-the-art, but we are unable to train a stable model at = 1. Thus, we make comparisons with other standard methods, namely DPGAN (Xie et al. (2018)) and DPCGAN (Torkzadehmahani et al. (2019)).
“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. I. Also, in App. I, we present experimental results of another tabular dataset (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.

heading: 6 CONCLUSION
text: 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. We comment on several potential future directions. 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, we note that, throughout the current work, we have taken the extreme limit where the sensitive data is transformed, sanitized, and released in a one-shot fashion. Allowing more accesses to the data could be more beneficial in terms of the privacy-utility trade-off. We intend to study this in the future.

heading: A ADDITIONAL DEFINITIONS AND PREVIOUS RESULTS
text: Definition 5 (Rényi differential privacy). A randomized mechanismM is said to satisfy ε-Rényi differential privacy of order λ, when
Dλ(M(d)‖M(d′)) = 1
λ− 1 logEx∼M(d) [( Pr[M(d) = x] Pr[M(d′) = x] )λ−1] ≤ ε
is satisfied for any adjacent datasets d and d′. Here, Dλ(P‖Q) = 1λ−1 logEx∼Q[(P (x)/Q(x)) λ] is the Rényi divergence. Furthermore, a ε-RDP mechanism of order λ is also (ε+ log 1/δλ−1 , δ)-DP.
Next, we note that the Gaussian mechanism is (λ, λ∆2f 2
2σ2 )-RDP Mironov (2017). The particular advantage of using RDP is that it gives a convenient way of tracking the privacy costs when a sequence of mechanisms is applied. More precisely, the following theorem holds Mironov (2017):
Theorem 4 (RDP Composition). For a sequence of mechanisms M1, ...,Mk s.t. Mi is (λ, εi)-RDP ∀i, the composition M1 ◦ ... ◦Mk is (λ, ∑ i εi)-RDP.
We use the autodp package to keep track of the privacy budget (Wang et al. (2019)).

heading: B PROOFS
text: B.1 PROOF OF THM. 2
Proof. Let Pr denote the real data distribution, Qθ denote the data distribution generated by Gθ using a latent vector, z sampled from a pre-determined distribution, and ω a sampling distribution. | · | denotes the modulus of ·. Then, the CFD between the distributions is
C2ω(Pr,Qθ) = Et∼ω(t) [ |ΦPr (t)− ΦQθ (t)| 2 ] ,
where ΦP(t) = Ex∼P [ eit·x ] is the CF of P. For notational brevity, we write ΦPr (t) as Φr(t), and ΦQθ (t) as Φθ(t) in the following.
We consider the optimized CFD, sup ω∈Ω C2ω(Pr,Qθ), and would like to show that it is locally Lipschitz, 4 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 or equal to the maximal difference of the two functions. Then, for any θ and θ′,∣∣∣sup
ω∈Ω C2ω(Pr,Qθ)− sup ω∈Ω C2ω(Pr,Qθ′) ∣∣∣ ≤ sup ω∈Ω ∣∣∣C2ω(Pr,Qθ)− C2ω(Pr,Qθ′)∣∣∣. (9) We note that the absolute difference of any two complex values represented in terms of its real-number amplitude (A,B) and phase (α, β) satisfies |Aeiα −Beiβ | ≤ |A|+ |B|. Writing the maximal ω as ω∗, the RHS of Eq. 9 can be written as∣∣∣C2ω∗(Pr,Qθ)− C2ω∗(Pr,Qθ′)∣∣∣ (10)
= Et∼ω∗(t) [(Cω∗(Pr,Qθ) + Cω∗(Pr,Qθ′)) (Cω∗(Pr,Qθ)− Cω∗(Pr,Qθ′))] = Et∼ω∗(t) [(|Φr(t)− Φθ(t)|+ |Φr(t)− Φθ′(t)|)(|Φr(t)− Φθ(t)| − |Φr(t)− Φθ′(t)|)] ≤ Et∼ω∗(t) [(2|Φr(t)|+ |Φθ(t)|+ |Φθ′(t)|)(|Φr(t)− Φθ(t)| − |Φr(t)− Φθ′(t)|)] (a) ≤ 4Et∼ω∗(t) [|Φr(t)− Φθ(t)| − |Φr(t)− Φθ′(t)|] (b) ≤ 4Et∼ω∗(t) [|Φθ(t)− Φθ′(t)|] ,
where we have used (a) |ΦP| ≤ 1, (b) triangle inequality. By interpreting a complex number as a vector on a 2D plane, and using trigonometric arguments, one can deduce that |eia − eib| = 2 sin(|a− b|/2) ≤ |a− b|. Then,
4Et∼ω∗(t) [|Φθ(t)− Φθ′(t)|] = 4Et∼ω∗(t) [ |Ez[eit·Gθ(z)]− Ez[eit·Gθ′ (z)]| ] (11)
(c) ≤ 4Et∼ω∗(t) [Ez[|t ·Gθ(z)− t ·Gθ′(z)|]] (d) ≤ 4Et∼ω∗(t)Ez [|t| · |Gθ(z)−Gθ′(z)|] .
4A function f is locally Lipschitz if there exist constants δ ≥ 0 and M ≥ 0 such that |x − y| < δ → |f(x)− f(y)| ≤M · |x− y| for all x, y.
In (c), we have also used the Jensen inequality. In (d), the Cauchy-Schwarz inequality has been applied. As we are assuming that Gθ is a L(θ, z)-Lipschitz function, we have
Et∼ω∗(t)Ez [|t| · |Gθ(z)−Gθ′(z)|] ≤ 4Et∼ω∗(t)[|t|] · Ez[L(θ, z)] · |θ − θ′|. (12)
Since we are also assuming that Et∼ω∗(t)[|t|],Ez[L(θ, z)] ≤ ∞, we have shown that sup ω∈Ω Cω is locally Lipschitz, as required. It is therefore continuous and differentiable almost everywhere, as discussed above.
B.2 PROOF OF THM. 3
Proof. We denote xn ∼ Pn and x ∼ P, and ω∗ the maximal function of ω. Notice that C2ω∗(Pn,P) = Et∼ω∗(t) [∣∣Exn [eit·xn]− Ex [eit·x]∣∣2]
= Et∼ω∗(t) [∣∣Exn [eit·xn]− Ex [eit·x]∣∣ · ∣∣Exn [eit·xn]− Ex [eit·x]∣∣]
(a) ≤ 2Et∼ω∗(t) [∣∣Exn [eit·xn]− Ex [eit·x]∣∣]
(b) ≤ 2Et∼ω∗(t) Exn,x [∣∣eit·xn − eit·x∣∣]
(c) ≤ 2Et∼ω∗(t) [|t|]Exn,x [|xn − x|] . (13)
Here, (a) uses |Aeiα − Beiβ | ≤ |A|+ |B| as argued above Eq. 10; (b) uses Jensen inequality; (c) uses the argument |eia − eib| = 2 sin(|a − b|/2) ≤ |a − b|, given above Eq. 11. Then, by weak convergence equivalence (Klenke (2013)), the RHS of Eq. 13 approaches zero as Pn
D−→ P, hence proving the theorem.
B.3 PROOF OF LEMMA. 1
Proof. Recall that for any two distributions, ω(t), ω0(t) and any function f(t), Eω[f(t)] = ∫ f(t)ω(t)dt
= ∫ f(t) ω(t)
ω0(t) ω0(t)dt
= Eω0 [f(t) ω(t)
ω0(t) ].
Hence, Eω(t)[f(t)] = Eω0 [f(t) ω(t) ω0(t) ]. Let ω∗ be the maximal probability distribution. It is then clear that Êω[f(t)]→ Eω[f(t)] implies Êω0 [f(t) ω∗(t) ω0(t) ]→ Eω∗ [f(t)], as desired.

heading: C EXPERIMENTAL SETUP OF TWO-SAMPLE TESTING ON SYNTHETIC DATA
text: Let us describe in more detail the experiment presented in Sec. 4. Data are generated from two unit-variance multivariate Gaussian distributions P,Q, where all dimensions but one have zero mean (P ∼ N (0d, Id), Q ∼ N ((1, 0, . . . , 0)>, Id)). We wish to conduct a two-sample test using the CF to distinguish between the two distributions, which gets more difficult as the dimensionality increases. We test if the null hypothesis where the samples are drawn from the same distribution is rejected.
Three sets of frequencies are considered. The number of frequncies in each set is set to 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 a zero-mean unitvariance multivariate Gaussian distribution. We denote the frequency with non-zero value in the first dimension by t0 without loss of generality. A “normal” set of frequencies is also considered for comparison, where the frequencies of all dimensions are sampled randomly from a multivariate Gaussian distributions. Finally, we consider an “optimized” set of frequencies, where from the
“unoptimized” set of frequencies, only t0 is selected to be used for two-sample testing. In other words, we re-weight the set of frequencies such that all but t0 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 to get the error bar).

heading: D DP ESTIMATE OF THE MEAN OF PAIRWISE DISTANCE
text: Median heuristic is applied widely in kernel methods applications to determine the bandwidth of the radial basis function (RBF) kernels (Garreau et al. (2018)). The bandwidth is taken to be the median of all pairwise distances of data samples. Here we give a DP estimation of the mean instead as the calculation of mean is more tractable. Let x be samples of a certain data distribution of dimension d and assume that the values lie in [0, 1]d. Given n samples, there is a total of n(n − 1)/2 pairwise distance pairs. Then, the mean of the pairwise distance of samples is
Dn(x) = 2
n(n− 1) n∑ i 6=j ‖xi − xj‖2.
where ‖ · ‖2 indicates the Euclidean norm. Consider a pair of neighboring datasets, D,D′. Without loss of generality, let xn 6= x′n and xi = x′i for i 6= n. Then, the sensitivity of Dn(x) is
∆Dn(x) = maxD,D′ ∥∥∥∥∥∥ 2n(n− 1) n∑ i6=j ‖xi − xj‖2 − 2 n(n− 1) n∑ i 6=j ‖x′i − x′j‖2 ∥∥∥∥∥∥ 2
(a) =
2
n(n− 1) max D,D′ ∥∥∥∥∥ n−1∑ i=1 ‖xi − xn‖2 − n−1∑ i=1 ‖xi − x′n‖2 ∥∥∥∥∥ 2
(b) =
2
n(n− 1) · (n− 1)
√ d
= 2 √ d
n .
In (a), we cancel out all terms unrelated to xn or x′n. In (b), we use the fact that ‖xi − xn‖2 and ‖xi − x′n‖2 lie in [0, √ d]. After obtaining the sensitivity, one can then applies the Gaussian mechanism as in Eq. 6 to obtain the DP estimate of the mean of the pairwise distance of samples.

heading: E TRAINING ALGORITHM
text: The pseudo-code of the proposed training algorithm is given in Algorithm 1.

heading: F COMPUTATIONAL COMPLEXITY ANALYSIS
text: PEARL is trained based on deep learning methods, which is efficient computation-wise using a GPU. Nevertheless, let us give a computational complexity analysis in a traditional sense by ignoring (partially) the parallel computing capability.
Time complexity. We sample k frequencies and calculate its inner product with data points (of dimension d), make a summation with respect to n data points to build k CFs. Since inner product takes d steps, summation n steps, and we do it for k times, the time complexity of generating CFs is nkd. We additionally train the generative model, requiring ttr. 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 n times the inference time, tinf . The total training and inference time is O(nkd+ ntinf + ttr).
Space complexity. We need to store the k CF values during training. We also need to store the generative model with m parameters. The space complexity is O(k +m).
Algorithm 1: PEARL Training Input: Sensitive data {x}ni=1, differential privacy noise scale σDP, number of frequencies k,
base sampling distribution variance σ0, training iterations T , learning rates ηC and ηG, number of generator iterations per critic iteration ngen, batch size B, latent distribution Pz
Output: Differentially private generator Gθ 1 Obtain auxiliary information (e.g., base sampling distribution variance σ0); 2 Sample frequencies {t}ki=1 with t ∼ N (0, diag(σ0)); 3 for i in {1, ..., k} do 4 Φ̂P(ti) = 1 n ∑n j=1 e iti·xj 5 Φ̃P(ti) = Φ̂P(ti) +N (0,∆2φ̂(x)σ 2 DPI) 6 end 7 Accumulate privacy cost ; 8 φ̃(x)← (Φ̃P(t1), . . . , Φ̃P(tk))> 9 Initialize generator Gθ, sampling distribution variance σ ;
10 for step in {1, ..., T} do 11 for t in {1, ..., ngen} do 12 Sample batch {zi}Bi=1 with zi ∼ Pz; 13 for i in {1, ..., k} do 14 Φ̂Q(ti) = 1 B ∑B j=1 e iti·Gθ(zj) 15 end 16 φ̂(z)← (Φ̂Q(t1), . . . , Φ̂Q(tk))> 17 θ ← θ − ηG · ∇θĈω 2 (φ̃(x), φ̂(z)) 18 end 19 Sample batch {zi}Bi=1 with zi ∼ Pz; 20 for i in {1, ..., k} do 21 Φ̂Q(ti) = 1 B ∑B j=1 e iti·Gθ(zj) 22 end 23 φ̂(z)← (Φ̂Q(t1), . . . , Φ̂Q(tk))> 24 σ ← σ + ηC · ∇σĈω 2 (φ̃(x), φ̂(z)) 25 end 26 Return Gθ

heading: G EVALUATION METRICS
text: 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) Bińkowski 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 a polynomial kernel of degree 3.
The precision definitions are as follows. Let {xri}ni=1 be samples from the real data distribution Pr and {xθi}mi=1 be samples from the generated data distribution Qθ. The corresponding feature vectors extracted from a pre-trained network (LeNet in our case) are {zri}ni=1 and {zθi}mi=1 respectively.
The FID and KID are defined as
FID(Pr,Qθ) =‖µr − µθ‖22 + Tr(Σr + Σθ − 2(ΣrΣθ)1/2), (14)
KID(Pr,Qθ) = 1
n(n− 1) n∑ i=1 n∑ j=1,j 6=i [ κ(zri , z r j) ]
+ 1
m(m− 1) m∑ i=1 m∑ j=1,j 6=i [ κ(zθi , z θ j ) ]
(15)
− 2 mn n∑ i=1 m∑ j=1 [ κ(zri , z θ j ) ] ,
where (µr, Σr) and (µθ, Σθ) are the sample mean & covariance matrix of the inception features of the real and generated data distributions, and κ is a polynomial kernel of degree 3:
κ(x,y) =
( 1
d x · y + 1
)3 , (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 5 library for training the generator, and the default subset for evaluation. For Adult, we follow the preprocessing procedure in Harder et al. (2021) to 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→ fc→ 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 the following architecture:
• fc→ bn→ relu→ fc→ bn→ relu→ fc→ tanh/softmax,
where tanh and softmax are the Tanh and softmax layers respectively. Network output corresponding to the continuous attribute is passed through the Tanh layer, whereas network output corresponding to 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,100) 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.

heading: I ADDITIONAL RESULTS
text: I.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 4 using the same classifiers as in the main text.
5https://pytorch.org/vision/stable/index.html
Three additional metrics/tasks are utilized: Range query. 1000 range queries containing three attributes are sampled randomly. The average l1 error between the original and synthetic datasets is evaluated. Marginal release. All 2-way marginals are calculated and the average l1 error is 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 (Pozzolo et al. (2015)). Our results comparing with DP-MERF as shown in Table 3 demonstrate that PEARL is competitive with various tasks and datasets.
I.2 MNIST AND FASHION-MNIST IMAGES
Fig. 5 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 HISTOGRAMS
We show more histogram plots for continuous and categorical attributes comparing our method with DP-MERF in Fig. 9 and Fig. 10.

Review summaries:
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. 

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).