Differentially Private Synthetic Data via Foundation Model APIs 1: Images
Authors: Zinan Lin
Sivakanth Gopi
Janardhan Kulkarni
Harsha Nori
Sergey Yekhanin
Venue: ICLR 2024 poster (2024)
Keywords: synthetic data
differential privacy
model API
foundation models
Primary area: generative models
TL;DR: Generating differentially private synthetic from foundation model APIs without any model training.

Abstract: Generating differentially private (DP) synthetic data that closely resembles the original private data is a scalable way to mitigate privacy concerns in the current data-driven world. In contrast to current practices that train customized models for this task, we aim to generate DP Synthetic Data via APIs (DPSDA), where we treat foundation models as blackboxes and only utilize their inference APIs. Such API-based, training-free approaches are easier to deploy as exemplified by the recent surge in the number of API-based apps. These approaches can also leverage the power of large foundation models which are only accessible via their inference APIs. However, this comes with greater challenges due to strictly more restrictive model access and the need to protect privacy from the API provider. 

In this paper, we present a new framework called Private Evolution (PE) to solve this problem and show its initial promise on synthetic images. Surprisingly, PE can match or even outperform state-of-the-art (SOTA) methods without any model training. For example, on CIFAR10 (with ImageNet as the public data), we achieve FID ≤ 7.9 with privacy cost ε = 0.67, significantly improving the previous SOTA from ε = 32. We further demonstrate the promise of applying PE on large foundation models such as Stable Diffusion to tackle challenging private datasets with a small number of high-resolution images. The code and data are released at https://github.com/microsoft/DPSDA.

Published as a conference paper at ICLR 2024
DIFFERENTIALLY PRIVATE SYNTHETIC DATA VIA FOUNDATION MODEL APIS 1: IMAGES
Zinan Lin
Sivakanth Gopi
Janardhan Kulkarni
Microsoft Research zinanl www.iiieeeeiett.omooooomoommmm com
Microsoft Research
Microsoft Research
gogo @mi www.eeemiictt.ooooooooooooooeeee com
eakulemicoosoft..o com
Harsha Nori Microsoft Research
Sergey Yekhanin
Microsoft Research yekhani n@mi crosoft. com
hanori @mi crosoft.com com
ABSTRACT
Generating differentially private (DP) synthetic data that closely resembles the original private data is a scalable way to mitigate privacy concerns in the current data-driven world. In contrast to current practices that train customized models for this task, we aim to generate DP Synthetic Data via APIs (DPSDA), where we treat foundation models as blackboxes and only utilize their inference APIs. Such API-based, training-free approaches are easier to deploy as exemplified by the recent surge in the number of API-based apps. These approaches can also leverage the power of large foundation models which are only accessible via their inference APIs. However, this comes with greater challenges due to strictly more restrictive model access and the need to protect privacy from the API provider.
In this paper, we present a new framework called Private Evolution (PE) to solve this problem and show its initial promise on synthetic images. Surprisingly, PE can match or even outperform state-of-thee (SOTA) methods without any model training. For example, on CIFAR1O (with ImageNet as the public data). we achieve FID with privacy cost 0.67, significantly improving the previous SOTA from e = 32. We further demonstrate the promise of applying PE on large foundation models such as Stable Diffusion tackle challenging private datasets with a small number of high-resolution images. The code and data are released at https: / / gi thub.
/DPSDA.
Prior work: Full model access
INTRODUCTION
O
While data-driven approaches have been successful, privacy is a major concern. For example, statistical queries of dataset may leak sensitive information about individual users (Dwork et al., 2014). Entire training samples can be reconstructed from deep learn- ing models (Haim et al., 2022; Fredrikson et al., 2015; Carlini et al., 2021a; 2023a;b; 2019; 202 lb; Choquette- Choo et al., 2021; Tramer et al., 2022; Wang et al., 2023). Differential privacy (DP) is the gold standard in quantifying and mitigating these concerns (Dwork et al., 2006). DP algorithms ensure that information about individual samples in the original data cannot be inferred with high confidence from algorithm outputs. holy grail of DP research (Hu et al., 2023; Jordon et al., 2019; Lin et al., 2020; Beaulieu-Jones et al., 2019; Dockhorn et al., 2022; Yin et al., 2022; Yu et al., 2021; He et al., 2022; Li et al., 2021; Ghalebikesabi et al., 2023; Yue et al., 2022: Harder et al., 2023; 2021; Savage, 2023; Lin, 2022; Tang et al., 2023). The goal is to generate a synthetic dataset that is statistically similar to the original data while ensuring DP. The benefits are: (1) Thanks the prot-srocsssing property of DP (Dwork et al., 2014), we can use any existing non-private algorithm (c.g., training machine learning (ML) models) as-is on the synthetic data without incurring additional privacy loss. This more scalable than redesigning and reimplementing every algorithm for DP. (2) Synthetic data can be shared freely with other parties without violating privacy. This useful situations when sharing data is neces- sary, such when organizations (e.g., hospitals) want to release datasets to support open research
Private data
DP Synthetic data
DP Synthetic Data via APls (DPSDA): Blackbox API access to pre-trained models
We consider the problem of gen- erating DP synthetic data with API access to pre-trained models without any model training. This is in contrast to prior work which assumes full access to pre-trained models and requires training.
Figure 1:
Differentially private synthetic data is the

---

Published as a conference paper at ICLR 2024
Initialization
Distribution (PDF)
Population
Private data
Intermediate generated data
Pre-trained generative models
Blackbox model
generation
Offspring
Perent selection
Private samples
APls
Parents
Figure 2: Private Evolution (PE) framework for DP synthetic data. Left: Intuition of PE. Though private data and pre-trained generative models have very different distributions, the support of the former is likely be covered by the support of the latter. We gradually shift the distribution of generated data toward private data through PE. Right: Algorithm of PE. We maintain a sample set (population), and iteratively select the most similar ones the private samples (parents) and mutate them to generate the next population (offspring). The initial population and offspring are generated with foundation model APIs. Parent selection is done DP using private samples.
80
Ours (uncond)
Qurs (cond)
DR-MEPF (uncond)
60
DP-MEPP (cand)
DP-GAN (uncond)
DP-Diffusion (cond)
@
40
20
0.125 0.25 0.5
8
16 32
Epsilon
Figure 4: FID (Heusel et al., 2017) (lower is bet- ter) v.s. privacy cost on CIFAR1O (ō 10-5). (Un)cond means (un)conditional generation. Ours achieves the best privacy-qualaa trade-off com- pared to DP-MEPF (Harder et al., 2023), DP- GAN, DP-Diffusion (Ghalebikesabi al., 2023).
Figure 3: Generated samples on CIFARI0 10 with (0.67, 100 - Each row corresponds to one class. FID=7.87. See App. J for real and generated images side-by-side.
initiatives (Beaulieu-Jones et al., 2019; Lin et al., 2020). (3) Since synthetic data is DP, developers can look at the data directly, which makes algorithm development and debugging a lot easier.
At the same time, with the recent advancement of large foundation models, API-based solutions gaining tremendous popularity, exemplified by the surge of GPT4-based upplications. In contrast to the traditional paradigm that trains/fine-tunes customized MLL models for each application, API- based solutions treat MI. models as blackboxes and only utilize APIs that provide the input/output functions of the models. In fact, many foundation models including GPT4, Bard, and DALLE2 only provide API access without releasing model weights or code. Key reasons for the success of API- based solutions are that APIS offer clean abstraction of ML and are readily available and scalable. Therefore, implementing and deploying these API-based algorithms is easier and faster even for developers without ML expertise. Such an approach can also leverage powerful foundation models that are only accessible through APIs. Unfortunately, SOTA DP synthetic data algorithms today are still in the old paradigm (Ghalebikesabi et al., 2023; Li et al., 2021): they need customized training process for each dataset, whose implementation requires significant ML engineering efforts ($ 3.1).
Motivated from these observations, we ask the following ambitious question (Fig. 1):
Can we generate DP synthetic data using blackbox APIs of foundation models?
We treat API providers as unirusted entities so we also want to protect user privacy from them, i.e., the API queries we make during generation should also be DP. If successful, we can potentially democratize the deployment of DP synthetic data in the industry similar to how API-based solutions have facilitated other applications. This a challenging task, however, as we do not have access to model weights and gradients by assumption. In this paper, we conduct the first exploration of the potential and limits of this vision on DP synthetic images. Surprisingly, we show that not only is such a vision realizable, but that it also has the potential to match improve SOTA training- based DP synthetic image algorithms despite more restrictive model access. Our contributions are:
See https: /ttptttaaatteetee/ form. openai i com/ docs/ intruuctioon for examples of APIs. For exam- ple, text completion API can complete text prompt using foundation model such as GPT4, An image variation API can produce variations of given image using foundation model such as DALLE2.

---

Published as a conference paper at ICLR 2024
(1) New problem ($ 3). We highlight the importance of DP Synthetic Data via APIs (DPSDA). Such algorithms are easy to implement and deploy and can leverage the foundation models behind APIs. (2) New framework ($ 4). We propose Private Evolution (PE) algorithm for achieving our goal (Fig. 2). We consider using 2 popular APIs: random generation and sample variation (i.e., generating a sample similar to the given one). 4.5 The key idea is to iteratively use private samples to vote for the most similar samples generated from the blackbox model and ask the blackbox models generate more of those similar samples. We theoretically prove that the distribution of the generated samples from PE will converge the private distribution under some modeling assumptions (App. E). PE only requires (existing) APIs of the foundation models, and does not need any model training.
(3) Experimental results ($ 5).² Some key results are: (a) Surprisingly, without any training, PE can still outperform SOTA training-basee
DP image generation approaches on some datasets (Figs. 3 and 4). For example, to obtain FID 7.9 on CIFAR1O 10 dataset, PE (with blackbox access to an -mageNet-pre-trainee model) only needs = 0.67. In contrast, DP fine-tuning of an ImageNet- pre-trained model (prior SOTA) requires e 32 (Ghalebikesabi al., 2023).
(b) We show that PE works even when there is significant distribution shift between private and public data. We create DP synthetic version (with 7.58) of Camelyon17. medical dataset for classification of breast cancer metastases, using the same ImageNet- DaaageNet-pre--tee pre-ttrained model. A down- stream classifier trained on our DP synthetic data achieves a classification accuracy of 79.56% (prior SOTA based on DP fine-tuning is 91.1% % with = 10 (Ghalebikesabi et al., 2023)).
(c) We set up new challenging benchmarks that the DP synthetic image literature has not studied before. We show that with powerful foundation models such as Stable Diffusion (Rombach et al., 2022), PE can work with high-resolution (512x512) image datasets with small size (100 images), which are common in practice but challenging for current DP synthetic image algorithms.
2 BACKGROUND AND RELATED WORK
Differential Privacy (DP). We say mechanism M is (e, 6)-DP if for any two neighboring datasets D and D' which differ in a single entry (i.e.. D' has one extra entry compared to D or vice versa) and for any set S of outputs of M, we have I (M (D) E S) e'P (M (D') E 5) + 5. Intuitively, this means that any single sample cannot influence the mechanism output too much.
DP synthetic data. Given a private dataset D. the goal is to generate DP synthetic dataset M (D) which is statistically similar to D. One method is to Irain generative models from scratch on private data (Lin et al., 2020: Beaulieu-Jones et al., 2019; Dockhorn et al., 2022) with DP-SGD (Abadi et al., 2016), DP variant of stochastic gradient descent. Later studies show that pre-training generative models on public data before fine-tuning them on private data with DP-SGD (Yin et al., 2022; Yu et al., 2021; He et al., 2022; Li et al., 2021; Ghalebikesabi et al., 2023; Yue et al., 2022) gives better privacy-utility trade-offss due to knowledge transfer from public data (Yin et al., 2022; Ganesh et al., 2023), smaller gradient spaces (Li et al., 2022), or better initialization (Ganesh et al., 2023). This approach achieves SOTA results on several data modalities such as text and images. In particular, DP-Diffusion (Ghalebikesabi et al., 2023) achieves SOTA results DP synthetic images by pre- training diffusion models (Sohl-Dickstein et al., 2015; Ho et al., 2020) on public datasets and fine- tuning them the private dataset. Some other methods do not depend on DP-SGD (Jordon al., 2019; Harder et al., 2023; 2021; Vinaroz et al., 2022; Cao et al., 2021). I). For example, DP-MEPF (Harder et al., 2023) trains generative models produce synthetic data that matches the (privatized) statistics of the private features.
Note that all these methods obtain generative models whose weights are DP, which can then be used to draw DP synthetic data. It is stronger than our goal which only requires DP synthetic data (Lin et al., 2021). In this paper, we do not do any model training and only produce DP synthetic data.
3 DP SYNTHETIC DATA VIA APIS (DPSDA)
3.1 MOTIVATION
As discussed in 2. SOTA DP synthetic data algorithms require training or fine-tuning generative models with DPD There are some obstacles to deploying them in practice.
(1) Significant engineering effort. Deploying normal ML training pipelines is hard; deploying DP training pipelines is even harder because most ML infrastructure is not built around this use case.
In the experiments of this paper, we only experimented with APIs from local models where the user has full control of the model weights and runs it in controlled environment.
3

---

Published as a conference paper at ICLR 2024
Recently, there has been significant progress in making DP training more efficient (Li 2021; He et al., 2022) and easy to use (Opacus (Yousefpour et al., 2021) and Tensorflow Privacy). However, incorporating them in new codebases and new models is highly non-trivial. For example, Opacus requires us to implement our own per-sample gradient calculator for new layers. Common layers and loss functions that depend multiple samples (e.g., batch normalization) are often not supported.
(2) Inapplicability of API-only models. It may be appealing to take advantage of the powerful foundation models in DP synthetic data generation. However, due to the high commercial value of foundation models, many companies choose to only release inference APIs of the models but not the weights or code. Examples include popular models such as DALLE 2 (Ramesh et al., 2022) and GPT 3/4 (Brown et al., 2020; OpenAl, 2023) from OpenAl and Bard from Google. In such cases, existing training- based approaches are not applicable."
In contrast, DP synthetic data approaches that only require model inference APIs could potentially be deployed more easily, as they do not require ML or DP expertise conduct modifications inside the model and require minimal modifications when switching to different model (as long as they support the same APIs). In addition, such an approach is compatible with both the models running locally and the models behind APIs.
3.2 PROBLEM FORMULATION
We now give formal statement of DPSDA. We first define core primitive for DP synthetic data.
DP Wasserstein Approximation (DPWA). Given a private dataset Spriv = {2r; E [ (Npriv] with
N ppii samples (e.g., images), a distance function d(:: -) between samples and some 2 1, the goal to design an (c, 8)-DP algorithm M that outputs a synthetic dataset Sann = {ar : E [Nayn]] with Nayn samples (as multiset) whose distance to Spriv. (p(Spriv Sayn), is minimized. Here Wp is the Wasserstein p-distance w.r.t. the distance function d(.,-) (see App. B for the definition).
DPSDA. We want to solve DPWA where M is given blackbox access to foundation models trained on public data via APIs. API queries should also be (c, 6)- as API providers cannot be trusted.
In some applications, besides the raw samples I3, we may also care about some auxiliary information such as class labels of images. In such cases, we may write Spriy = {(x,, y.) : E [Appiie] (and Sayn {(11, s/) [)) where yi (and v/) is the auxiliary information of i-th sample.
When the distance function d(;;) :) is E (in the sample space), DPWA is closely related to DP Clus- tering (Ghazi et al., 2020; Su et al., 2016; Balcan et al., 2017) and DP Heatmaps (Ghazi et al., 2022). But direct application of them does not work in our setting; see App. H for more discussions.
3.3 SCOPE OF THIS WORK
Data type. In this paper, we instantiate the above framework on images. We consider both uncon- ditional (i.e., no y:) and conditional generation (c.g., Y: can be image categories such as cats/dogs). APIS. In our algorithm design and experiments, we use 2 APIs, both of which are either directly provided in the APIs of popular models (e.g., DALLE 2, Stable Diffusion") or can be easily imple- mented by adapting current APIs (e.g., using appropriate text prompts in GPT APis'):
(1) RANDOM (n)) that randomly generates n samples. Some APIs accept condition information such text prompts in text-to-image generation,4. 4.5 which we omit in the notation for simplicity.
(2) VARIATION AAI (S) that generates variations for each sample in S. For images, it means to gen- erate similar images to the given one, e.g., with similar colors objects.** 4.5 Some APIs also support setting the variation degree: VARIATION API (S, v), where larger indicates more variation." 6
4 PRIVATE EVOLUTION (PE)
Foundation models have broad and general model of our world from their extensive training data. Therefore, we expect that foundation models can generate samples close to private data with non-
'Some companies also provide model fine-tuning APIs, e.g., https: / form. openai com/ does/ / /ggucee///////// fine-tune tunggg. However, they do not support DP line-tuning and do not provide gradi- ents. Also, uploading sensitive data to these APIs controlled by other companies can lead to privacy violations.
'See attps: / /pttt form, openai. com/ docs/ guides/ cacaaags/usagee SSee
https: htatps://huggingge http://hhggggggggcgege co/ docs/ hilffussrs/ap//piiee sttl.//app
di Afffusinn auuiinn/overvies overview.
'If this is not implemented, can simply compose the VARIATION_API times achieve it.

---

Published as a conference paper at ICLR 2024
negligible probability. The challenge is that by naively calling the APIs, the probability of drawing such samples quite low. We need way to guide the generation towards private samples.
Inspired by evolutionary algorithms (EA) (Davis, 1987) (App. C), we propose Private Evolution (PE) framework for generating DP synthetic data via APIs. See Fig. 2 for the intuition behind PE. The complete algorithm is in Alg. 1. Below, we discuss the components in detail.
Algorithm 1: Private Evolution (PE)
Input :
Private samples: Spriv = { Npriv
Number of iterations: T Number of generated samples: Nayn Noise multiplier for DP Nearest Neighbors Histogram: Threshold for DP Nearest Neighbors Histogram:
Output: Synthetic data: Sayn
S1 RANDOM (Nsyn) for t 1 do
hislogram, < DP NN HISHOGRAM privv Se; H) // P. is distribution on S.
// See Alg.
P. < hislogram,, /sum (hinslgrilaaa
S c draw Neyn samples with replacement from P. // S is a multiset Si+1 + VARIATION (S))
return Sr
Algorithm 2: DP Nearest Neighbors Histogram (DP.NN.HISTOGRAN)
Input Private samples: Spriy
Generated samples: {=
Noise multiplier:
Threshold:
Distance function:
(..-)
Output: DP nearest neighbors histogram on
histogram + [0
for Tpriv Spriv do
== arg minye[m) d (Xprivv zj)
histogram [1] < histogrampp [i] +1
histogram +- histogram + N (0,
// Add noise to ensure 11 'max', \_ are Tlemettwiss
histogram t- max (histogram H,
7 return histogram
Initial population (Line 1). We use RANDOMLAPI to generate the initial population. If there is public information about the private samples (e.g., they are dog images), we can use this information as prompts the API to seed a better initialization.
Fitness function (Line Alg. 2). We need to evaluate how useful each sample the population is for modeling the private distribution. Our idea is that, if sample in the population is surrounded by many private samples, then we should give a high score. To implement this, we define the fitness function of a sample
the number of private samples whose nearest neighbor in the population is x. A higher fitness value means that more private samples are closest to it. More details are below:
(1) Distance function (Line 3, Alg. 2). To define "nearest neighbor",
need distance function that measures the similarity of two samples. A naive way is to use &g distance d (I, 2) = | =lIa- where & is from the private dataset and is from the population. However, it is well-known that & distance on pixel space is not good metric for images. For example, a small shift of an object can result high& & distance. We therefore compute the &g distance in the embedding space:
d (x, 2) = 1| (x) - +b (z)ll2
(1)
where & is network for extracting image embeddings such as inception embedding (Szegedy al., 2016) or CLIP embedding (Radford et al., 2021).
(2) Lookahead. The above approach gives high scores to the good samples in the current pop- ulation. However, as we will see later, these good samples will be modified through VARIA- TION_API for the next population. Therefore, it is better "look ahead" to compute the dis- tance based on the modified samples if they are kept in the population. We modify Eq. (1) to
5

---

Published as a conference paper at ICLR 2024
compute the distance between the embedding of x and the mean embedding of k. variations of 2: where k is called lookahead degree, and 2 ,..., , are vari- d (z, 2) = ② (z) E @ (2*) 2
ations of obtained via VARIATION API.
(3) N DP (Line 5, Alg. 2). Because this step utilizes private samples, we need to add noise to ensure DP. We add i..dd Gaussian noise from N' (0, o). The privacy analysis is presented in $ 4.3.
(4) Thresholding (Line 6, Alg. 2). When the number of generated samples is large, the majority of the histogram will be DP noise added above. To make the signal-noise ratio larger, we set a threshold H each bin of the histogram. Similar ideas have been used in DP set union (Gopi et al., 2020).
In summary, we called the above fitness function DP Nearest Neighbors Histogram. Note that is not the traditional "histogram" on a continuous space that requires binning. Instead, it is a histogram built on the generated samples: the value of i-th bin means the (privatized) number of private samples whose nearest neighbor among the generated ones is the i-th sample. See App. A for related work.
Parent selection (Line 5). We sample from the population according to the DP Nearest Neighbors Histogram so that a sample with more private samples around is more likely to be selected.
Offspring generation (Line 6). We use VARIATION to get variants of the parents as offisprings. Please see App. for the convergence analysis of PE.
4.1 CONDITIONAL GENERATION
The above procedure is for unconditional generation. To support conditional generation, i.c., each generated sample is associated with a label such as an image class (c.g., cats v.s. dogs), we take a simple approach: we repeat the above process for each class of samples in the private dataset separately. See Alg. for the full algorithm.
4.2 GENERATING UNLIMITED NUMBER OF SAMPLES
Our algorithm in Alg. I is preset with a fixed number of generated samples Nayn- What if users want more samples afterward? In prior training-based methods (Ghalebikesabi et al., 2023), this is easy to achieve: one can draw an arbitrary number of samples from the trained gen- erative models without additional privacy cost. In this section, we want to highlight that PE also do that, again with API access only. We can simply generate of samples by calling variation API multiple times, each with the generated dataset as input: [VARIATION API (Swen) ...., VARIATION API (Sayn)]- In 5.1.3, we will see that this simple algo- rithm is sufficient to provide more useful samples for downstream applications.
unlimited number
4.3 PRIVACY ANALYSIS
Unlike the analysis of DP-SGD which requires complicated DP composition theorems (e-g.. Gopi et al. (2021); Mironov (2017)) due to subsampling, PE does not have subsampling steps and there- fore the privacy analysis is rather straightforward. The DP guarantee of the unconditional version
of PE (Alg. 1) can be reasoned as follows:
Step 1: The sensitivity of DP Nearest Neighbors Histogram (Lines 1 to 4 in Alg, 2). Each pri- vate sample only contributes one vote. If we add or remove one sample, the resulting histogram will change by in the & norm. Therefore, the sensitivity is 1.
Step 2: Regarding each PE iteration
Gaussian mechanism. Line 5 adds i.idd Gaussian noise with standard deviation a to each bin. This is a standard Gaussian mechanism (Dwork et al., 2014) with noise multiplier 0.
Step 3: Regarding the entire PE algorithm as T adaptive compositions of Gaussian mech- anisms, as PE is simply applying Alg. 2 T times sequentially.
Step 4: Regarding the entire PE algorithm as one Gaussian mechanism with noise multi-
plier a/ /TVT. It is a standard result from Dong et al. (2022) (see Corollary 3.3 therein).
Step 5: Computing DP parameters e and 8. Since the problem is simply computing and o for standard Gaussian mechanism, we use the formula from Balle & Wang (2018) directly.
For the conditional version of PE (Alg. 3), since it does the unconditional version for each class separately (discussed in $ 4. 1), adding or removing one sample will only influence the results of one class. For that class, the impact due to the added/removed sample is also bounded, as seen in the privacy analysis above. Therefore, Alg. 3 is also DP. In fact, we can show that the privacy guarantee of Alg. 3 is the same as Alg. 1, and it protects the labels of samples in the same level as DP-SGD (Ghalebikesabi et al., 2023). Please refer to App. D for more details.

---

Published as a conference paper at ICLR 2024
This privacy analysis implies that releasing all the (intermediate) generated sets Si..... Sr also sat- isfies the same DP guarantees. Therefore PE provides the same privacy even from the API provider.
5 EXPERIMENTS
In 5.1, we compare PE with SOTA training-based methods standard benchmarks to understand its promise and limitations. In & 5.2, we present proof-of-concept experiments to show how PE can utilize the power of large foundation models. We did (limited) hyper-parameter tunings in the above experiments: following prior DP synthetic data work (Yu et al., 2021; Ghalebikesabi et al,, 2023), we ignore the privacy cost of sapem--ar tuning. However, as we will see in the ablation studies ($ 5.3 and App. N), PE stably outperforms SOTA across a wide range of hyper-pann parameters, and the results can be further improved with better hyper-parameters than what we used. Detailed hyper-parameter settings and more results such as generated samples and their nearest images in the private dataset are in Apps. to L.
5.1 COMPARISONS TO STATR-OF-THE-ART
Public information. We use standard benchmarks (Ghalebikesabi et al., 2023) which treat Ima- geNet (Deng et al., 2009) as public data. For fair comparisons, we only use ImageNet as public information in PE: (1) Pre-truined model. Unlike the SOTA (Ghalebikesabi et al., 2023) which trains customized diffusion models, we simply use public ImageNet pre-trained diffusion models (pure image models without text prompts) (Nichol & Dhariwal, (021). RANDOM_AP |API and VARIA- TIONLAPI are implemented using the same pre-trained model (see App. J). (2) Embedding (Eq. (1)). We use ImageNet inception embedding (Szegedy et al., 2016). PE is not sensitive to embedding choice though and we get good results even with CLIP embeddings (Fig. 41 in App. N).
Baselines. We compare with DP-Diffusion (Ghalebikesabi al., 2023), DP-MEPP (Harder al., 2023), and DP-GAN (Harder et al., 2023; Goodfellow et al., 2020). DP-Diffusion (Ghalebikesabi et al., 2023) the current SOTA that achieves the best results on these benchmarks. Baseline results are taken from their paper.
Outline. We test PE private datasets that are either similar to or differ a lot from ImageNet in
87.5
Test Test Accuracy
5.1.1 and 5.1.2. We demonstrate that PE can gener-
85.0
ate an unlimited number of useful samples in $ 5.1.3. We show that PE is computationally cheaper than based methods in App.
82.5
80.0
+-Ours (8-3.34)
-Ours (ensemble) (8=3.34)
77.5
DP-Diflusion (E = 10)
5.1.1 MODERATE
DP-Diffusion (ensemble) (E = 10)
DISTRIBUTION SHIFT (IMAGENET + CIFAR10)
75.0
0.25
0.50
0.75
1.00
We treat CIFARIO (Krizhevsky et al., 2009) as pri- vate data. Given that both ImageNet and CIFARIO are natural images, it is a relatively easy task for PE (and also for the baselines). Figs. to 5 show the results. Surprisingly, despite the fact that we con- sider strictly more restrictive model access and do not need training, PE still outperforms the SOTA training-based methods. Details are below.
Num of Generated Samples
le6
Downstream classification accu- racy (higher is better) on CIFARIO (5 10 10-5). The baseline results are taken from Ghalebikesabi et al. (2023). Two "ensemble" lines are from ensembles of 5 classifiers. The other two lines show the average accuracy of independently trained classifiers with error bars. Our PE achieves better accuracy across almost all settings with smaller privacy costs.
Figure 5:
Sample quality. Fig. 4 shows the trade-off between privacy cost and FID, a popular metric for image quality (Heusel et al., 2017). For either conditional or unconditional generation, PE outperforms the baselines significantly. For example, to reach FIDx 7.9, Ghalebikesabi et al. requires c = 32, Harder et al. cannot achieve it even with infinity c, whereas our PE only needs 0.67.
Downstream classification accuracy. We train a downstream WRN-40-4 classifier (Zagoruyko & Komodakis, 2016) from scratch on 50000 generated samples and test the accuracy on CIFARIO test set. This simulates how users would use synthetic data, and a higher accuracy means better utility. Fig. shows the results (focus on the left-most points with num of generated samples = 50000 for now). Harder et al. (2023) achieves 51% accuracy with e = 10 (not shown). Compared with the SOTA (Ghalebikesabl et al., 2023), PE achieves better accuracy (+6. (%) with less privacy cost. Further with an ensemble of 5 classifiers trained on the same data, PE is able to reach an accuracy of 84.8% For reference, the SOTA DP classifier pre-trained on ImageNet (without DP) and fine-tuned on CIFARIO (with DP) (De et al., 2022) achieves 94.8% and 95.4% accuracies with epsilon=1 and
7

---

Published as a conference paper at ICLR 2024
Real
Generated (99.92,3 3 10 -DP. FID=10.66)
Figure Real and generated images from Camelyon17. 7. More App. K.
2 respectively. It is not surprising that DP classifiers outperform PE (and other DP synthetic data approaches) classification tasks, as DP classifiers are targeted at and optimized for a single task whereas DP synthetic data is general-purpose.
The above results suggest that when private and public images are similar, PE is promising frame- work given its better privacy-utility trade-off and the API-only requirement.
5.1.2 LARGE DISTRIBUTION SHIFT (IMAGENET - CAMELYON17)
Next, we consider a hard task for PE, where the private dataset is very different from ImageNet. We use Camelyon17 dataset (Bandi et al., 2018; Koh et al., 2021) as private data which contains 302436 images of histological lymph node sections with labels on whether it has cancer (real images in Figs. and 22). Despite the large distribution shift, training-based methods can update the model weights to adapt to the private distribution (given enough samples). However, PE can only draw samples from APIs as is.
We find that even in this challenging situation, PE can still achieve non-trivial results. Following Ghalebikesabi et al. (2023), we train a WRN-40-4 classifier from scratch on 302436 generated sam- ples and compute the test accuracy. We achieve 80.33% accuracy with (10.00, 3 10 --D.. Prior SOTA (Ghalebikesabi et al., 2023) is 91.1% with (10.3 3 10 J-DDP. Random guess is 50%. Fig. (more in Fig. 21) shows that generated images from PE are very similar to Camelyon17 despite that the pre-trained model is on ImageNet. Fig. 23 further shows how the generated images are gradually moved towards Camelyon17 across iterations.
Why PE works under large distribution shifts. Even though the diffusion model is trained on nat- ural images, the support of the generated distribution spans the entire sample space. PE effective in guiding the model to generate samples from the region that is low-density in the original pre-trained distribution but high-density in the private distribution. See App. K for more explanations.
Limitation. These results demonstrate the effectiveness of PE. But when public models that are similar to private data are not available and when there is enough private data, the traditional training- based methods are still more promising at this point if the privacy-utility trade-off is the only goal. However, given the benefit of API-only assumption and the non-trivial results that PE already got, is worth further exploiting the potential of PE in future work. Indeed, we expect these results can be improved with further refinement of PE (App. N).
5.1.3 GENERATING UNLIMITED NUMBER OF SAMPLES
We use the approach in Š 4.2 to generate more synthetic samples from $ 5.1.1 and train classifiers on them. The results are in Fig. 5. Similar Ghalebikesabi et al. (2023), the classifier accuracy improves as more generated samples are used. With an ensemble of 5 classifiers, we reach 89.13% accuracy with IM samples. This suggests that PE has the same capability as training-busse bhased methods in generating an unlimited number of useful samples.
We also see two interesting phenomena: (1) The gap between PE and DP-Diffusion diminishes as more samples are used. We hypothesize that it is due to the limited improvement space: As shown in Ghalebikesabi et al. (2023), even using an ImageNet pre- pra-er classifier, the best accuracy DP- Diffusion achieves is close to the best points in Fig. 5. (2) The benefit of PE is more evident over ensembling, especially when having more generated samples. We hypothesize it due to different ways of generating more samples. In Ghalebikesabl et al. (2023), the newly generated samples are from the same distribution as the first 50000 samples. In contrast, the newly generated samples in PE are from different distribution (see $ 4.2), which could be more diverse and therefore are more beneficial for ensembling approaches.
5.2 MORE CHALLENGING BENCHMARKS WITH LARGE FOUNDATION MODELS We demonstrate the feasibility of applying PE on large foundation models with Stable Diffusion (Rombach et al., 2022).
Data. Ideally we want to experiment with a dataset that has no overlap with Stable Diffusion's training data. We take the safest approach: we construct two datasets with photos of the author's
"The training set of Stable Diffusion is public. However, it is hard to check if public image or its variants (e.g., cropped, scaled) have been used to produce images in it. Therefore, resort to private data.
8

---

Published as a conference paper at ICLR 2024
Real
Generated (6.62, 10 "-DP)
Real
Generated ((6.62, 10 1-DP)
Figure 8: Real & generated images from Cat Cookie (left) and Cat Doudou (right), More in App. L.
two cats that have never been posted online. Each dataset has 100 512x512 images. Such high- resolution datasets with a small number of samples represent a common need in practice (e.g. in health care), but challenging for DP synthetic data: to the best of our knowledge, prior training-based methods have reported results on datasets with a similar resolution or number of samples. The dataset is released at https: // /ggituu........//gg www.hhuw.oooooooooommmmmmo...eoe htm:/miccen wwworooott.ooommmmmmommmmmocc..o DDSDAA as a new benchmark. See App. L. for all images.
API implementation. We use off-the-shelf Stable Diffusion APIs (see App. L).
270M parameters
100M parameters
0 20
Results. We run PE for these two datasets with the same hyperparametens. Fig. 8 show examples of generated images for each of the cat datasets. We can see that Private Evolution correctly captures the key characteristics these two cats. See App. I. for all generated images.
10
0.5
1.0
1.5
2.0
2.5
Epsilon
Figure 7: Ablation studies on the pre-trained model. Both are public diffusion models trained on ImageNet (Nichol & Dhariwal, 2021). The 270M network conditional, whereas the 100M network is unconditional.
5.3 ABLATION STUDIES
Pre-trained network. Fig. 7 shows the results with two different ImageNet pre-trained networks: one is larger (270M) with ImageNet class labels as input: the other one is smaller (100M) without label input (see App. for implementation details). In all experiments in $ 5.1, we used the 270M network. Two takeaways are: (1) The 270M network (trained on the same dataset) improves the results. This expected as larger and more powerful models can learn public distributions better. This suggests the potential of PE with future foundation models with growing capabilities.
(2) Even with a relatively weak model (100M), PE can still obtain good results that beat the baselines (though with slower convergence speed), suggesting the effectiveness of PE.
More ablation studies the lookahead degree k, the number of generated samples Nayn the thresh- old H, and the embedding network are in App. N, where we see that PE obtains good results across a wide range of paaeerr-rameters, and the main results can be improved with better hyper-parametes parameters.
LIMITATIONS AND FUTURE WORK
Algorithms. (1) We did not take the number of API calls into account when optimizing PE. One
future work is to optimize the number of API calls along with privacy-utility tradeoffs. (2) We
considered two APIs: RANDOM and VARIATION_API. It is interesting to consider PE variants that leverage the large set of APIs. 4.5 (3) When the distributions of private data and foundation models are too different, PE achieved non- trivill classification results, but was still worse than SOTA ($ 5.1.2). It is interesting understand the limits of PE and explore potential improvements. (4) PE requires an embedding network (Eq. (1)) that projects the samples into space for measuring the similarity between samples. While for images there are plenty of open-source embedding networks to choose, it may not be the case for other modalities. (5) Recent papers show the phenomenon of Model Autophagy Disorder (MAD), where repeatedly training the next generative model using synthetic data from the previous one can result in degraded sample quality (Alemohammad et al., 2023). While PE also repeatedly uses synthetic data to create new synthetic data in the main loop (Alg. 1), it is different in two aspects: (a) Instead of purely relying on the synthetic data, PE utilizes the signals from private data to guide the generation; (b) PE does repeated inference instead of repeated training. It would be interesting study the MAD effect in the context of PE. (6) Solving DPSDA in the Local/Shuffle DP model and in federated learning settings.
vision applications that were previously challenging but are now possible due to PE's s capability of generating high- nigh-resolution DP synthetic images with small dataset sizes. (2) The use of PE in other data modalities beyond images such as texts, tabular data, and time series data. (3) Besides DP, there are other parallel/orthogonal privacy concerns, notions, and metrics (Issa al., 2019; Lin et al., 2022; 2023b; Commission). is interesting to study if PE can be used to generate peeayccpeeeriinggg synthetic data with respect these privacy notations.
Applications. (1) New

---

Published as a conference paper at ICLR 2024
7 ETHICS STATEMENT
PE uses the APIs of pre-trained models. The DP guarantee of PE is rigorous for the data used in the PE algorithm (i.e., Spriv). That being said, PE does not address the privacy of pre-training data of foundation models, which is different goal. PE has no control over the pre-training privacy breaches in the pre- pre-training data are attributable to the data holder (e.g.. leaking the data publicly) or the foundation model developer (c.g., using data without permission). However, as a PE user, it is advisable to ensure overlap between the pre-training data and Spriv for liability reasons. Depending on whether the APIS are from blackbox models, which can only be accessed through APIs (e.g., DALLE3), or local models, whose weights and architectures are accessible by the users (e.g., Stable Diffusion), it has different implications.
Using APIs from blackbox models. Since most blackbox models do not reveal their training dataset, it is safer to only consider Spriv that was never been shared or posted online. For in- stance. hospital who wants share a DP synthetic version of its proprictary medical records can safely run PE if it has never released these medical records to any other party, making it impossible for those records to be the pre-training data of any foundation model.
Using APIs from local models. For local models, we have full control over the model weights and architectures. We can pre-train the models on data that surely has no overlap with the private data. all experiments of the paper, we use local models including Improved Diffusion (Nichol & Dhariwal, 2021) and Stable Diffusion (Rombach et al., 2022). We directly take the pre- trainee models from prior work, and we make sure that the private data and the pre-training data have overlap.
ACKNOWLEDGEMENT
The authors would like to thank the anonymous reviewers for their valuable feedhack and sugges- tions. The authors would also like to thank Sepideh Mahabadi for the insightful discussions and ideas, and Sahra Ghalebikesabi for the tremendous help in providing the experimental details of DP- Diffusion (Ghalebikesabi et al., 2023). The authors would like to extend their heartfelt appreciation to Cat Cookie and Cat Doudou for generously sharing their adorable faces in the new dataset, as well as to Wenyu Wang for collecting and pre-proeessing the photos.
i This paper is the full version of our previous workshop paper (Lin et al., 2023a).
REFERENCES
Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 308-318, 2016.
Sina Alemohammad, Josue Casco- Mosso-Rodriguez, Lorenzo Luzi, Ahmed Imtiaz Humayun, Hossein Babaei, Daniel LeJeune, Ali Siahkoohi, and Richard G Baraniuk. Self-consuming generative models go mad. arXiv preprint arXiv:2307.01850, 2023.
Rohan Anil, Badih Ghazi, Vineet Gupta, Ravi Kumar, and Pasin Manurangsi. Large-scale differen- tially private bert. arXiv preprint arXiv:2108.0166 2021.
Martin Arjovsky, Soumith Chintala, and Léon Botto.. Wasserstein generative adversarial networks. In International conference on machine learning, pp. 214-223. PMLR, 2017.
Maria-Florine Balcan, Travis Dick, Yingyu Liang, Wenlong Mou, and Hongyang Zhang. Differ- entially private clustering in high dimennsinaii euclidean spaces. In International Conference Machine Learning, pp. 322-331. PMLR, 2017.
Borja Balle and Yu-Xiang Wang. Improving the gaussian mechanism for differential privacy: Ana- lytical calibration and optimal denoising. In International Conference Machine Learning, pp- 394 403. PMLR, 2018.
Peter Bandi, Osear Geessink, Quirine Manson, Marcory Van Dijk, Maschenka Balkenhol, Meyke Hermsen, Babak Ehteshami Bejnordi, Byungjae Lee, Kyunghyun Paeng, Aoxiao Zhong, et al.
10

---

Published as a conference paper at ICLR 2024
From detection of individual metastases to classification of lymph node status at the patient level: the camelyon17 challenge. IEEE transactions on medical imaging, 38(2):550-560, 2018.
Brett K Beaulicu-Jones, Zhiwei Steven Wu, Chris Williams, Ran Lee. Sanjeev P Bhavnani, James Brian Byrd, and Casey S Greene. Privacy-preservee generative deep neural networks sup- port clinical data sharing. Circulation: Cardiovascular Quality and Outcomes, 12(7):e005122, 2019.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
Tianshi Cao, Alex Bie, Arash Vahdat, Sanja Fidler, and Karsten Kreis. Don't generate me: Training differentially private generative models with sinkhorn divergence. Advances in Neural Informa- tion Processing Systems, 34: 12480-12492, 2021.
Nicholas Carlini, Chang Liu, Úlfar Erlingsson, Jemnj Kos, and Dawn Song. The secret sharer: Evaluating and testing unintended memorization in neural networks. In 28th USENIX Security Symposium, 2019.
Nicholas Carlini, Steve Chien, Milad Nasr, Shuang Song, Andreas Terzis, and Florian Tramer. Mem- bership inference attacks from first principles. arXiv preprint arXiv:21 2021a.
Nicholas Carlini, Florian Tramèr, Eric Wallace, Matthew Jagielski, Ariel Herbert- Voss, Katherine Lee, Adam Roberts, Tom Brown, Dawn Song, Ulfar Erlingsson, Alina Oprea, and Colin Raf- fel. Extracting training data from large language models. In 30th USENIX Security Symposium, USENIX Security 21, pp. 2633-2650. USENIX Association, 2021b.
Nicholas Carlini, Jamie Hayes, Milad Nasr, Matthew Jagielski, Vikash Sehwag, Florian Tramer, Borja Balle, Daphne Ippolito, and Eric Wallace. Extracting training data from diffusion models. arXiv preprint arXiv:2301. 13.00/113/800 /3888 2023a.
Nicholas Carlini, Daphne Ippolito, Matthew Jagielski, Katherine Lee, Florian Tramer, and Chiyuan Zhang. Quantifying memorization across neural language models. International Conference on Learning Representations, 2023b.
Alisa Chang and Pritish Kamath. Differentially private clustering in google's differential pri- vacy library. Google AI Blog, 2023. URL www.illyypiiiteeeeee html. atttps://aiie http::///a...gggllllogooooo 1001://0ppaaticaalddffeeeettttte pwtrrreentialllypivvatteeeeee priplly.-iivtatetttteeee. html.
com httpp///oo..ooo//////////// 2021/10/
Christopher A Choquette-Chov Florian Tramer, Nicholas Carlini, and Nicolas Papernot. Label-only membership inference attacks. In Proceedings of the 38th International Conference on Machine Learning. ICML '21, pp. 1964-19744 JMLR, Inc., 2021.
European Commission. Article 29 data protection working party.
Luke N Darlow, Elliot Crowley, Antreas Antoniou, and Amos Storkey. Cinic- 10 is not imagenet or c0f arXiv preprint 1rXiv:1810.03500 2018.
Lawrence Davis. Genetic algorithms and simulated annealing. 1987.
Soham De, Leonard Berrada, Jamie Hayes, Samuel Smith, and Borja Balle. Unlock- ing high-accuracy differentially private image classification through scale. arXiv preprint MxXiv:2204113500 2022.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hi- erarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pp. 248-255. Icee, 2009.
Prafulla Dhariwal and Alexander Nichol. Diffusion models beat gans on image synthesis. Advances in Neural Information Processing Systems, 34:8780-8794, 2021.

---

Published as a conference paper at ICLR 2024
Tim Dockhorn, Tianshi Cao, Arash Vahdat, and Karsten Kreis. Differentially private diffusion models. arXiv preprint arXi::2110009929, 2022.
Jinshuo Dong, Aaron Roth, and Weijie J Su. Gaussian differential privacy. Journal of the Royal Statistical Society Series B: Statistical Methodology, 84(1):3-37, 2022.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pp. 265-2844 Springer, 2006.
Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Foundations and Trendso Theoretical Computer Science, 9(3-4):211 107 2014.
Matt Fredrikson, Somesh Jha, and Thomas Ristenpart. Model inversion attacks that exploit confi- dence information and basic countermeasures. In Proceedings of the 22nd ACM SIGSAC confer- ence on computer and communications security, pp. 1322-1333, 2015.
Arun Ganesh, Mahdi Haghifam, Milad Nasr, Sewoong Oh, Thomas Steinke, Om Thakkar, Abhradeep Thakurta, and Lun Wang. Why is public pretraining necessary for private model training? arXiv preprint arXiv:2302. 09483, 2023.
Sahra Ghalebikesabi, Leonard Berrada, Sven Gowal, Ira Ktena, Robert Stanforth, Jamie Hayes, Soham De, Samuel L Smith, Olivia Wiles, and Borja Balle. Differentially private diffusion models generate useful synthetic images. arXiv preprint arXiv:2302.1386. 2023.
Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. Differentially private clustering: Tight approxi- mation ratios. Advances in Neural Information Processing Systems, 33:4040-4054, 2020.
Badih Ghazi, Junfeng He, Kai Kohlhoff, Ravi Kumar, Pasin Manurangsi, Vidhya Navalpakkam, and Nachiappan Valliappan. Differentially private heatmaps. arXiv preprint 233442221.. 2022.
Ian Goodfellow, Jean Pouget-Abadie, Mchdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial networks. Communications of the ACM, 63(11): 63(11)):13-144 2020.
Sivakanth Gopi, Pankaj Gulhane, Janardhan Kulkarni, Judy Hanwen Shen, Milad Shokouhi, and Sergey Yekhanin. Differentially private set union. In International Conference on Machine Learn- ing, pp. 3627-3636. PMLR, 2020.
Sivakanth Gopi, Yin Tat Lee, and Lukas Wutschitz. Numerical composition of differential privacy. Advances in Neural Information Processing Systems, 34:1 111111611111 1 1642, 2021.
Niv Haim, Gal Vardi, Gilad Yehudai, Ohad Shamir, and Michal Irani. Reconstructing training data from trained neural networks. arXiv preprint (tt.:2220007755. 2022.
Frederik Harder, Kamil Adamczewski, and Mijung Park. Dp-merf: Differentially private mean em- beddings with randomfeatures for practical privacy-preserviee data generation. In International conference on artificial intelligence and statistics, pp. 1819-1827. PMLR, 2021.
Frederik Harder, Milad Jalali, Danica Sutherland, and Mijung Park. Pre-trained perceptual features improve differentially private image generation. Transactions on Machine Learning Research, 2023.
Jiyan He, Xuechen Li, Da Yu, Huishuai Zhang, Janardhan Kulkarni, Yin Tat Lee, Arturs Backurs, Nenghai Yu, and Jiang Bian. Exploring the limits of differentially private deep learning with group-wise clipping. arXiv preprint arXiv:2212.01539, 2022.
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.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in Neural Information Processing Systems, 33:6840-6851, 2020.
12

---

Published as a conference paper at ICLR 2024
Junyuan Hong, Lingjuan Lyu, Jiayu Zhou, and Michael Spranger. Outsourcing training without uploading data via efficient collaborative open-source sampling. Advances in neural information processing systems, 35:20133 1101133-2100 201406 2022.
Charlie Hou, Hongyuan Zhan, Akshat Shrivastava, Sid Wang, Aleksandr Livshits, Giulia Fanti, and Daniel Lazar. Privately customizing prefinetuning to better match user data in federated learning. arXiv preprint arXiv:2302.0900 09002, 2023.
Yuzheng Hu, Fan Wu, Qinbin Li, Yunhui Long, Gonzalo Munilla Garrido, Chang Ge, Bolin Ding. David Forsyth, Bo Li, and Dawn Song. Sok: Privacy-preserving data synthesis. arXiv preprint arXiv:2307.02106, 2023.
Ibrahim Issa, Aaron B Wagner, and Sudeep Kamath. An operational approach to information leak- age. IEEE Transactions on Information Theory, (((3)))125-16577 2019.
James Jordon, Jinsung Yoon, and Mihacla Van Der Schaar. PATE-GAN: Generating synthetic data with differential privacy guarantees. In International conference on learning representations, 2019.
Pang Wei Koh, Shiori Sagawa, Henrik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Bal- subramani, Weihua Hu, Michihiro Yasunaga, Richard Lanas Phillips, Irena Gao, et al. Wilds: A benchmark of in-the-wild distribution shifts. In International Conference on Machine Learning, pp. 5637-5664. PMLR, 2021.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Xuechen Li, Florian Tramer, Perey Liang, and Tatsunori Hashimoto. Large language models can be
strong differentially private learners. arXiv preprint arXiv:2110.056 2021.
Xuechen Li, Daogao Liu, Tatsunori В Hashimoto, Huseyin A Inan, Janardhan Kulkarni, Yin-Tat Lee, and Abhradeep Guha Thakurta. When does differentially private learning not suffer in high dimensions? Advances in Neural Information Processing Systems, 35:28616-28630 2022.
Zinan Lin. Data Sharing with Generative Adversarial Networks: From Theory to Practice. PhD thesis, Carnegie Mellon University, 2022.
Zinan Lin, Alankar Jain, Chen Wang, Giulia Fanti, and Vyas Sekar. Using gans for sharing net- worked time series data: Challenges, initial promise, and open questions. In Proceedings of the ACM Internet Measurement Conference, pp. 464-483, 2020.
Zinan Lin, Vyas Sekar, and Giulia Fanti. On the privacy properties of gan-generated samples. In International Conference on Artificial Intelligence and Statistics, pp. 1522-1530. PMLR, 2021.
Zinan Lin, Shuaiqi Wang, Vyas Sekar, and Giulia Fanti. Distributional privacy for data sharing. In NeurlPS 2022 Workshop on Synthetic Data for Empowering ML Research, 2022.
Zinan Lin, Sivakanth Gopi. Janardhan Kulkarni, Harsha Nori, and Sergey Yekhanin. Differentially private synthetic data via foundation model APIs 1: Images. In NewrIPS 2023 Workshop on Synthetic Data Generation with Generative AI, 2023a. URL / forum? f TEvOS8.
Zinan Lin, Shuaiqi Wang, Vyas Sekar, and Giulia Fanti. Summary statistic privacy in data sharing. arXiv preprint arXiv:2303.020/ 02014, 2023b.
Chenlin Meng, Yang Song, Jiaming Song, Jiajun Wu, Jun- Yan Zhu, and Stefano Ermon. Sdedit: Im- age synthesis and editing with stochastic differential equations. arXiv preprint 200.:::000.00007:: 2021.
Ilya Mironov. Rényi differential privacy. In 2017 IEEE 30th computer foundation sympo- sium (CSF), pp. 263-277 275. IEEE, 2017.
Alexander Quinn Nichol and Prafulla Dhariwal. Improved denoising diffusion probabilistic models.
In International Conference on Machine Learning, pp. 8162-8171. PMLR, 2021.
13

---

Published as a conference paper at ICLR 2024
OpenAl. Gpt-4 technical report, 2023.
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. In International conference machine learning, pp- 8748-8763. PMLR, 2021.
Aditya Ramesh, Prafulla Dhariwal, Alex Nichol, Casey Chu, and Mark Chen. Hierarchical text- conditional image generation with clip latents. arXiv preprint arXiv:2204.0612. 2022.
Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Bjöm Ommer. High- resolution image synthesis with latent diffusion models. Proceedings of the IEEE/CVF Con- ference on Computer Vision and Pattern Recognition, pp. 10684-10695, 2022.
Neil Savage. Synthetic data could be better than real data. Nature, April 2023. doi: 10.1038/ 1411886003-00445--8 URL https: : //oiii.o..o org/ wtt.oo...////////.....eo 00100//4/16002200000000000000000 023-0145--8
Jascha Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsupervised learning using nonequilibrium thermodynamics. In International Conference on Machine Learn-
ing. pp. 2256-2265, PMLR, 2015.
Jiaming Song, Chenlin Meng, and Stefano Ermon. Denoising diffusion implicit models. arXiv preprint arXiv:2010.02502. 2020.
Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. Advances in neural information processing systems, 32, 2019.
Dong Su, Jianneng Cao, Ninghui Li, Elisa Bertino, and Hongxia Jin. Differentially private k-means clustering. In Proceedings of the sixth ACM conference on data and application security and privacy, pp. 26-37, 2016.
Christian Szegedy, Vincent Vanhoucke, Sergey loffe, Jon Shlens, and Zbigniew Wojna. Rethink- ing the inception architecture for computer vision. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2818-28222 2016.
Xinyu Tang, Richard Shin, Huseyin Inan, Andre Manoel, Fatemehsadat Mireshghallah, Zinan Lin, Sivakanth Gopi. Janardhan Kulkarni, and Robert Sim. Frivacy-preservvin in-context learning with differentially private few-shot generation. arXiv preprint arXiv:2309. 11765 2023.
Florian Tramèr, Reza Shokri, Ayrton San Joaquin, Hoang Le, Matthew Jagielski, Sanghyun Hong, and Nicholas Carlini. Truth serum: Poisoning machine learning models to reveal their secrets. arXiv preprint arXiv:2204.000: 00002022400000,,, 2022.
Margarita Vinaroz, Mohammad-Amm Amin Charusaie, Frederik Harder, Kamil Adamczewski, and Mi Jung Park. Hermite polynomial features for private data generation. In International Con- ference Machine Learning, pp. 22300-22324 PMLR, 2022.
Boxin Wang, Weixin Chen, Hengzhi Pei, Chulin Xie, Mintong Kang, Chenhui Zhang, Chejian Xu, Zidi Xiong, Ritik Dutta, Rylan Schaeffer, et al. Decodingtrust: A comprehensive assessment of trustworthiness in gpt models. arXiv preprint 1.Xiv:2306.11699 2023.
Yucheng Yin, Zinan Lin, Minhao Jin, Giulia Fanti, and Vyas Sekar. Practical gan-based synthetic ip header trace generation using netshare. In Proceedings of the ACM SIGCOMM 2022 Conference, pp. 458-472, 2022.
Ashkan Yousefpour, Igor Shilov, Alexandre Sablayrolles, Davide Testuggine, Karthik Prasad, Mani Malck, John Nguyen, Sayan Ghosh, Akash Bharadwaj. Jessica Zhao, Graham Cormode, and Ilya Mironov. Opacus: User-friendly differential privacy library in PyTorch. arXiv preprint 10Xiv:2/09.12298, 2021.
Da Yu, Saurabh Naik, Arturs Backurs, Sivakanth Gopi, Huseyin A Inan, Gautam Kamath, Janardhan Kulkarni, Yin Tat Lee, Andre Manoel, Lukas Wutschitz, et al. Differentially private fine-tuning of language models. arXiv preprint a1X0v:2110.06500, 2021.
14

---

Published as a conference paper at ICLR 2024
Da Yu, Sivakanth Gopi, Janardhan Kulkarni, Zinan Lin, Saurabh Naik, Tomasz Lukasz Religa, Jian Yin, and Huishuai Zhang. Selective pre-training for private fine-tuning. arXiv preprint arXiv:2305. 13865, 2023.
Xiang Yue, Huseyin A Inan, Xuechen Li, Girish Kumar, Julia McAnallen, Huan Sun, David Levitan, and Robert Sim. Synthetic text generation with differential privacy: simple and practical recipe. arXiv preprint arXiv:2210. 2022.
Sergey Zagoruyko and Nikos Komodakis. arXiv:1605.07146, 2016.
Wide residual networks.
arXiv preprint
15

---

Published as a conference paper at ICLR 2024
A MORE RELATED WORK
DP data selection. One key component in PE is to use private samples to select similar generated samples (Alg. 2). Prior work studied similar problems in different applications.
In the federated learning setting, Hou et al. (2023) select public datasets that are similar to the clients' data, and then pre-train the model on the selected datasets before federated fine-tuning. Hong et al. (2022) first cluster public data, and then use clients' data to select the closest cluster centers (using a similar histogram approach), so that models trained on the selected clusters can have better performance for the clients. In contrast to these works, PE selects generated samples at a sample-level, so that we can improve the generated data more fine-grained manner.
Similar to ours, Yu et al. (2023) also conduct sample-level data selection. They select public samples that are similar the private data for pre- pre-training the model, before DP fine-tuning the model on the private data (Yu et al., 2023). Their data selection rule does not provide guarantees the distance between the selected samples and the private samples, whereas our selection provides distribution convergence guarantees (App. E).
Nevertheless, given that all these methods deal with DP data selection, they can be interchangeably used in each application. It would be interesting study such extensions in future work.
Furthermore, we apply such data selection iteratively on the generated data. Together with the use of foundation model APIs,
generate DP synthetic data, which is not studied in prior work.
B DEFINITION OF WASSERSTEIN DISTANCE
Wasserstein distance is widely used metric in designing (Arjovsky al., 2017) and evaluat- ing (Heusel et al., 2017) generative models. Given probability distributions μ., on a metric space, the Wasserstein distance w.r.t. a distance function d(.--) is defined as Wp(,,v) inf, (B(x,)),,d( u) point sets S,T, use Wp Wp(S,T) T") to denote the W -distance between uniform distributions S and T.
1/P where the infimum is over all couplings 7 of (t, Also given discrete
C A BRIEF INTRODUCTION TO EVOLUTIONARY ALGORITHMS
Evolutionary algorithms (Davis, 1987) are inspired by biological evolution, and the goal is to pro- duce samples that maximize an objective value. starts with an initial population (i.e., a set of samples), which is then iteratively updated. In each iteration, it selects parents (i.e., subset of sam- ples) from the population according to the finness function which describes how useful they are in achieving better objective values. After that, it generates offsprings (i.e., new samples) by modifying the parents, hoping to get samples with better objective values, and puts them in the population. By doing the population will be guided towards better objective values.
We cannot directly apply existing EA algorithms to our problem. Firstly, our objective is to produce set of samples that are jointly optimal (i.e., closer to the private distribution, 3.2), instead of optimizing an objective calculated from individual samples in typical EA problems. In addition, the differential privacy requirement and the restrictive model API access are unique to our problem. These differences require us to redesign all components of EA.
D MORE DETAILS ON PRIVATE EVOLUTION
Alg. 3 shows the full algorithm that supports both unconditional data and conditional data. For simplicity, we assume that the private dataset Speiv balanced, i.e., has an equal number of samples in each label class. Otherwise, we can first estimate the counts using the Laplace mechanism and use these counts to generate synthetic data of appropriate size in each label class.
Privacy analysis. For ease of understanding the privacy guarantee of Alg. 3, we can consider modified version of Alg. 3 as in Alg. 4, where we switch the order of the two for loops over and Apparently, this modified algorithm gives the same outcome as Alg. 3. The only lines that touch
16

---

Published as a conference paper at ICLR 2024
Algorithm 3: Private Evolution (PE) for both labeled and unlabeled data.
Input:
The set of private classes: C (C = {0} if for unconditional generation)
Private samples: Spriv {( 34) )
Npriv where x; is sample and 5/s C its label
Number of iterations: T
Number of generated samples: Nayn (assuming Nayn mod |C*| 0)
Noise multiplier for DP Nearest Neighbors Histogram:
Threshold for DP Nearest Neighbors Histogram: H
Ssyn f- for e C C do
t- (xil(Is, 1/1) Spriv and yi = cf
Si < RANDOM_AR (Nayn/ (C1)
for 1 + I,..... do
histogram, + DP.NNLHISTOGRAM hwwpoo/aeoaapprooorreesssopppplo St, H.
// See
Alg. (aaigrrammmmummmstttggrrmmm (histogram.) P/P is distribution S, 5 t draw Neyn//Cr ||| samples with replacement from P. // Sy is a multiset.
P. histogram, /sum
S VARIATION.API(S)
Sayn + Sayn U ((,(( ST}
return Sayn
private data are Lines 5 and 6. The input to these lines is the entire private dataset, and the output a histogram with size Nayn. Same as step in the analysis Alg. ($ 4.3), each private sample sample, the resulting histogram
only contributes
vote in the histogram. If we add remove will change by in the le norm. Therefore, the sensitivity of these lines 1. The following privacy analysis follows exactly the same as steps 2-5 in $ 4.3, and therefore, the privacy guarantee of important to emphasize that even though Alg. 3 utilizes the
Alg. 3 is the same as Alg. 1. labels of the samples directly, the above analysis means that Alg. provides privacy protection to the label assignment of the samples (I.c., the labels each sample has) in the same way as the baaeed algorithms (Ghalebikesabl et al., 2023).
Algorithm 4: Private Evolution (PE) for both labeled and unlabeled data. (Modified from Alg. 3) for the case of privacy analysis.)
Input:
The set of private classes: C (C = {0} if for unconditional generation)
Private samples: Spriv = {(x,, "
Npri where z; is sample and y/ E its label
Number of iterations: T
Number of generated samples: Ngyn (assuming Nayn mod |C| 0)
Noise multiplier for DP Nearest Neighbors Histogram:
Threshold for Nearest Neighbors Histogram: H
Ssyn f- ST RANDOMLAPI (NNyn/ [C]) for each C private samples" + [z,](2,, y:) E Spri and yı c} for each E for t 1,..,, do for c do
histogram; <- DP DD..NN.HISTOGRAM (private Si, H) Alg. 2 for E C do P. t (saggrrrm//uummisttgrrrnn
// See
// P is distribution S
S. t draw Naya//Cr /C] samples with replacement from P, // St is a multiset
1+1 t VARIATION API
Sayn
Soy U (x,,))( C
12 return Sayn
17

---

Published as a conference paper at ICLR 2024
E THEORETICAL EVIDENCE FOR CONVERGENCE OF PE
In this section, we will give some intuition for why PE can solve DPWA.
Convergence of Non-Private Evolution. We first analyze Alg. I when noise is added to the histograms (i.e., we set a = O and H = O in Line 3). We show that in this case, the evolution algorithm does converge to the private distribution in ((d) iterations where d is the dimension of the embedding space. Under some reasonable modeling assumptions (see App. F), we prove the following theorem. Here D is the diameter of Spriv. s number of variations of each point in S that are added to S1+1 in Line 6 of Alg. 1.
Theorem 1. Assume that log L < d. With probability 2 1-T, the non-private evolution algorithm (Alg. I with a H 0) outputs Sayn with Wasserstein distance W Wp(Spriv: Sayn) S 1) after T iterations Vp E [1, oo] whenever
T dlog(D/n) log + log(Npriv/TT.
This theorem is nearly tight. In each iteration of PE, we get the voting information which is about Ö(Nrriv (T)) bits. To converge Spriv. we need least ((Npried)) bits of information. There- fore we do require at least (2d/ log L) iterations to converge. Here is some intuition for how the proof of Thm. 1 works. Fix some private point x E Spriv- Let 2" E St be its closest point in S,. In S.+1, we generate variations of z" using the VARIATION API (=*). We then prove that || - =01l 2 y). then one of the variations will get closer to than =" by factor of (1 (log L)/d with constant probability. Repeating this for T iterations as in Eq. (2), will bring some point in ST 17-close to
Convergence of Private Evolution. To get some intuition on the working of PE in the presence of noise, we make simplifying assumption. We will assume that there are B identical copies of each private point in Spriv. We call B as multiplicity. Note that for any DP algorithm to converge to Spriv. we need that the private data is well clustered with some minimum cluster size. Any cluster with too few points cannot be represented in Sayn: because that would violate DP. And when there is cluster of B private points and the generated points in S₁ are still far from this cluster, then it is likely that all the B private points will have a common closest point in S, 10 i.c.. they all vote for the same point in S, as single entity. Therefore multiplicity is a reasonable modeling assumption to make to understand the working of PE. Note that, actually it is very easy to find Spriv exactly using DP Set Union (Gopi et al., 2020) with the multiplicity assumption. The point of Thm. to give intuition about why PE works in practice; it is proved in App. F.2 under the same assumptions as in Thm.
Theorem 2. Let S E S log(1/26). Suppose each point in Spriv has multiplicity B. Then, with high probability (2 1 - T). Private Evolution (Alg. 1) with a > /Tlog(1/8)/ and H > o LoogTTTLNPpiii priv / when run for T iterations, satisfies (E, 6)- and outputs Sayn such that (Spiipr Sayn) S 1), Vp E [1, oo]. whenever T sutisfies Eg. (2) and multiplicity > H.
Ignoring polylogarithmic factors in d, L, lo /dlog(1/0)/ for Theorem 2 to hold. Thus, we should expect that PE will discover every cluster of private data of size >> /dlog(1/8)/s / in (dd) iterations. We now compare this to previous work on DP clustering. Ghazi al. (2020) gives an algorithm for densest ball, where they show an (c. 8DP algorithm which (approximately) finds any ball of radius r which has at least >> /dlog(1// private points. Thus intuitively, we see that PE compares favorably rithms (though we don't 't have rigorous proof of this fact). If this can be formalized, then PE gives very different algorithm for densest ball, which in turn can be used to solve DP clustering. More- over PE is very amenable to parallel and distributed implementations. We therefore think this is an interesting theory problem for future work.
we need T > d and B >
SOTA DP clustering algo-
'If log L >> d logg(D/n) n). i.e.. if we generate an exponential number of points then by simple epsilon-net argument we can prove that the algorithm will converge in single step.
9 Number of samples produced using VARIATION API per iteration is S L-r- -Nriv = L log(D/r) Npriv. II fact, it is easy formally prove that there will be common approximate nearest neighbor.
18

---

Published as a conference paper at ICLR 2024
Why Private Evolution works well in practice. We have seen that in the worst case, PE takes ((d) iterations to converge. In our experiments with CIFARIO and Camelyon17, where 2048 is the embedding dimension, we see that PE actually converges in only about 20 iterations which is much smaller than We offer one plausible explanation for this via intrinsic dimension. Suppose the (embeddings of) realistic images lie on low dimensional manifold M inside 12t of dimension diutrinsic < (see experimental results in App. G). Given an image 2, VARIATION (2) will create variations of which are also realistic images. Therefore the embeddings of these variations will also lie in the same manifold M, and PE is searching for the private points only inside the manifold M without ever going outside it. Therefore the d that matters for convergence is actually dintrinsic < d. In this case, we expect that PE converges in O(dittinssi)) iterations and discovers clusters of private points of size at least / diutrinsic (1/61/6)/E.
F PROOFS OF PE CONVERGENCE THEOREMS
We will slightly modify the algorithm as necessary to make convenient for our analysis. will make the following modeling assumptions:
The private dataset Spriv is contained in an l ball of diameter D and RANDOM API will also produce initial samples in the same ball of diameter D. This is a reasonable assumption in practice, as images always have bounded pixel values: for the original images in UINT8 data type, each pixel is in the range of [0, 255|: in diffusion models, they are usually nor- malized to [-1, (i.c., corresponds to and 255 corresponds to 1), and all generated images are guaranteed to be in this range.
The distance function used in Alg. 2 is just the l norm, d(z, 2) = 1|r-2112
The distribution of points we output is Sayn = Pr (i.e., we output a distribution of points).
S C supp(P:) = supp(histogram.e
Se+1 S u U.es; VARIATION API (z) where VARIATION API (z) samples L samples
each from Gaussian distributions ((2, I) for o; Dvlog & where I s and 2'd
r= log(D/r) D/n) where 1) > 0 is the final Wasserstein distance.
F.1 PROOF OF THM. 1
Proof.
Fix a point æ E Spriv and some iteration t. Suppose 2" E S₁ is the closest point to x. Since will vote for z* in histogram,, x" supp(Pt) C S%. Therefore VARIATION_API (z*) C S
Let V = VARIATION_API(22))
Claim 1. If | 2-1 2 n, then with probability least 1/2. some point in V will get noticeably
closer to I than x², i.e.,
(1
log L 4d
min
| 2112 =EV
| 2² 2=1
Proof. Let s -1=== and let E (01, 02,..,,,. or) such that ad/ Vlg T. E [s/2, s). Note that such o exists since E in, DJ. We will now prove that one of the L samples 21, ....... ZL N( La) will get noticeably closer to x than z". Let 2, = zz + ow; where wi ~ N 1a).
min |ar =E(L]
||
min (o² |/ 2o (xc - =,,w,)) FE(L)
<
max 2² ||
max 20 (x 2" ws) sE[L]
Note that ||wx 12 is a x3 random variable. By using upper tail bounds for x2 distribution and union bound over E [L], we can bound
Pr
max
| 11 2 3d/2 <
Lexp(-2(d)) < 1.
iE[L]
11 This may not be true in the original algorithm due to sampling, we need to modify it so that S 5 supp(P.).
19

---

Published as a conference paper at ICLR 2024
The distribution of (x - -=",,00 wn) is the same as || - -="112 Wi where w1...., wr are i..dd (0. 1) random variables. By using the fact that max of L i.i.d. Gaussians is at least Vlg L with probability least 3/4 (for L >> 1), we get that
1
Pr max (x - =", w)) S 8v
seelloog log L S
[EIL)
Combining everything we get:
2 Pr
min [E(T]
|a
zill2 2 8² (3/2)do² 2s0 / /log
Asv 2
[Asvlog L
2 Pr
min [E
x - 22112
max X
s² + (3/2)d
-2s
Vlog
d
d
log
2 Pr
min [E[
[ar zill z
+
max XE(1/2.1]
(31²/2 -21)
d
log L
2 Pr
min [E[L]]
[x
x112 2 8²
1
2d
log
)]
2 Pr
min
[a
2|l22 2 8
[E[L]
4d
where last inequality uses the fact that vI- t--tsin 1-1-1 fort
Now in T iterations, min.es, | - 2 will shrink by a factor of (1- log in at least T/4 it- erations with probability 1 exp(-S(TT) 2 ---
Nprv (by standard Chernoff bounds). Note that in iterations where it doesn't shrink, it doesn't grow either since Sy C S Similarly, if minges, || =||2 < 1) for some iteration, it will remain so in all subsequent iterations. Therefore log
after >>>>>>>>>>>>> dt dloo((/m)) iterations, minseS, || - = S 7) with probability at least 1 -_ Nym By union bounding over all points we get that, with probability at least - т, for every point æ E Spriv there is point in Sz which is closse. This proves that Wy Wy(Spriv Pr) S n7.
F.2 PROOF OF TIM.. 2
Proof. Since we are doing T iterations of Gaussian mechanism with noise level a, we need to set > (ogg((1/)) to satisfy (e, 8)-DP (Dwork et al., 2014) when S Tog(1 128). Let E Spriv be point with multiplicity B. If E St is the closest point to x, then will get votes. After adding (V00 noise, if B >> >> a LLNgg(LL then with probability at least -/((4TT), the noisy votes that x" gets is still above the threshold H. Therefore 2" will survive in St+1 well. Also since H > LV/lo(TLLNpzzi which do not get any votes (there are L.Nriiv of them) will not survive even after adding noise and thresholding by H. Therefore, by union bounding over all T iterations, with probability at least 1 - 7/2, the algorithm behaves identically to the non-private algorithm. Therefore by an identical proof in the non-private analysis, we can prove that after T' iterations (Sprivvv Pr) n with probability at least T-
with probability
T/(4T), points in S,
G INTRINSIC DIMENSION OF IMAGE EMBEDDINGS
To illustrate the intrinsic dimension of image embeddings, we use the following process:
1. We (randomly) take image from CIFARIO.
2. We use VARIATION API from App. obtain 3000 image variations of z: Fl, T3000, and their corresponding inception embeddings II...., 83000 E 20448 3000 is chosen so that the number of variations is larger than the embedding dimension.
3. We construct a matrix M = [g] J:...; 93000 :3000 g] E 3000xx0018 where g the
mean(g1..... (3000)
20

---

Published as a conference paper at ICLR 2024
4. We compute the singular values of M: 2 02 .... 20048
5. We compute the minimum number of singular values needed so that the explained variance ratio 2 E21 d² 2 0.8. Intuitively, this n describes how many dimensions are needed to reconstruct the embedding changes M with small error. We use it an estimated intrinsic dimension of the image variations.
We conduct [98, 96, 94, 92, 90, 88, 86, 84, 82, 80, 78, 76, 74, 72, 70, 68, 66, 64, 62, 60) utilized in the CIFARIO experiments (see App. J). We additionally add variation degree of 100 which is the highest variation degree in the API that was used to generate the initial samples. We plot the estimated intrinsic dimension v.s. variation degree in Fig. 9. The raw original singular values of M/ /3000 for variation degree=60 in Fig. 10 (other variation degrees have similar trend). Two key observations are:
the above process
with the variation degree
As the variation degree increases, the estimated intrinsic dimension also increases. This could because the manifold of image embeddings is likely to be non-linear, the above estimation of intrinsic dimension is only accurate when we perturb the image x small degree so that the changes in the manifold can still be well approximated by linear subspace. Using a larger variation degree (and thus larger changes in the embedding space) will overestimate the intrinsic dimension.
Nevertheless, we always see that the singular values decrease rapidly (Fig. 10) and the estimated intrinsic dimension is much smaller than the embedding size 2048 (Fig. 9), which supports our hypothesis in App. E.
190
Estimated Intrinsic
170
160
150
60
100
Variation Degree
Figure Estimated intrinsic dimension of inception embeddings of realistic images.
10
Singular Value
10-1
10-2
10a
10a
10a
Singular Value Index
Figure 10: Singular values of inception embeddings of image variations variation degree=60.
12See
http:///ww....cceceecccccccoaatt wtw.taato...ncccttttss..... html.
21

---

Published as a conference paper at ICLR 2024
H RELATION OF DPWA TO PRIOR WORK
Recall that in DPWA, we want a DP algorithm to output Sayn which is close to the distribution of Spety in Wasserstein distance w.r.t some distance function d(.-). When the distance function d(.,;) is just lg distance between the samples (i.e., &2 in the pixel space for images), then DPWA is closely related to DP Clustering (Ghazi et al., 2020; Balcan et al., 2017; Su et al., 2016) and DP Heatmaps (Ghazi et al., 2022).
In (Ghazi et al., 2022), to give an algorithm for DP Heatmaps, the authors study DP sparse EMD aggregation problem where we need to output distribution of points which approximates the distri- bution of private data in EMD distance (i.e., W1). They study this problem only in two dimensions and the running time of their algorithms (suitably generalized to higher dimensions) will be expo- nential in the dimension d.
The DP Clustering problem requires us to output a clustering of private data using DP. The most common clustering studied is k-means clustering where we should output is cluster centers such that k-means cost is minimized, where k-means cost is the sum of squares of lg fi-distance of each data point to its nearest cluster center. Note that DPWA, if the number of synthetic data points Noyn is specified to be k, then DP k-means clustering and DPWA with W2 metric are equivalent. In (Ghazi et al., 2022), a polynomial time DP Clustering algorithm with an additional k-means cost (over what non-privately possible) of / polyyog (aallloggggiviieee priv d)/e is given. This can be converted into an upper bound on the Wasserstein distance. But this is not a practical algorithm. The privacy-utilits tradeoffss are bad due to the large hidden constants in the analysis and the authors don't 't provide an implementation. There is practical DP Clustering algorithm (along with an implementation) given in (Chang & Kamath, 2023) (but with no theoretical guarantees).
H.1 WHY NOT JUST USE DP CLUSTERING?
We now explain why we can't 't just use prior work on DP Clustering to solve DPSDA say for images.
Clustering in the image space. We can use DP k-means Clustering cluster the images w.r.t. & metric in the pixel space. This doesn't t work because & distance in the pixel space doesn't capture semantic similarity. An image which is slightly shifted in pixel space gets very far in &2 distance. And the dimension of the images is too large for prior DP Clustering algorithms to work well. Their convergence and privacy-utility tradeoffs depend too strongly on the dimension.
Clustering in the embedding space. We can use DP k-means Clustering to cluster the image embeddings w.r.t. & metric the embedding space. Note that this the distance function we use in PE (Eq. (1)). Even after we find the cluster centers, it is hard to invert the embedding map (i.e.. find an image whose embedding is close to a given vector in the embedding space). 14 Moreover the dimension of the embedding space is still too large for the above methods to be practical.
Our PE algorithm does much better because:
1. Its distance function is & in the embedding space which captures semantic similarity,
2. It exploits the intrinsic dimension of the manifold of images in the embedding space which is much smaller than the embedding dimension (see App. E and App. G) and
3. There is no need invert points in embedding space to the image space.
In an early experiment, we have tried DP clustering in the CLIP embedding space using the practical DP Clustering algorithm in (Chang & Kamath, 2023). We then inverted the cluster centers (which are in the embedding space) using unCLIP. But we found the resulting images are too noisy com- pared to the images we get from PE and the FID scores are also significantly worse than that of PE.
13 Earth's Mover Distance, which the another name Wasserstein metric W1. "Some special embeddings such as CLIP embedding do have such an inverse map called unCLIP (Ramesh al., 2022).
22

---

Published as a conference paper at ICLR 2024
I IMPLEMENTATION DETAILS ON LABEL CONDITION
There are two meanings of "conditioning" that appear in our work:
1. Whether the pre-trained networks or APIs (e.g., ImageNet pre-trained diffusion models used in 5.1.1 and 5.1.2) support conditional input (e.g., ImageNet class label).
2. Whether the generated samples are associated with class labels from the private data.
In DP fine-tuning approaches, these two usually refer to the same thing: we want to generate class labels for generated samples, the common practice is to use pre-trattee pre-trained network that supports conditional input (Ghalebikesabi et al., 2023). However, in PE, these two are completely orthogonal.
Conditional pre-trained networks/APIs. We first explain our implementation when the pre-trained networks or APIS support conditional inputs such as class labels or text prompts. When generating the initial population using RANDOM IAPI (Line 1). we will either randomly draw labels from all possible labels when no prior public information is available (which is what we do in CIFARI 10 and Camelyon 17 experiments where we randomly draw from all possible ImageNet classes), or the public information as condition input (c.g., the text prompt used in Stable Diffusion experiments; see App. L). the subsequent VARIATION calls (Line 6), for each image, we will use its associated class label or text prompt as the condition information to the API, and the output samples from VARIATION API will be associated with the same class label or text prompt as the input sample. For example, if we use an image with "peacock" class to generate variations, all output images will be associated with "peacock" class for future VARIATION API calls. Note that throughout the above process, all the condition inputs to the pre-trained networks/APis are public information; they have nothing to do with the private classes.
Conditional generation. Conditional generation is achieved by Alg. 3, where separate the samples according to their class labels, and run the main algorithm (Alg. 1) on each sample set. We use either conditional unconditional pre-trained networks/APIs implement it.
Throughout the paper, "(un)condition"" refers to 2, expect the caption in Fig. which refers to 1.
J MORE DETAILS AND RESULTS ON CIFAR10 EXPERIMENTS
Pre-trained model. By default, we use the checkpoint imagenet 64 22___44______1111111111_11____2_ 2002222200000___ pt. released in (Nichol & Dhariwal, 2021)." 15 For the ablation study of the pre-trained network, we additionally use the checkpoint imagenet 64 64__ncond_ 10000000000 500.0tt..........
API implementation. RANDOM API follows the standard diffusion model sampling process. VARI- ATION _AP is implemented with SDEdit (Meng et al., 2021), which adds noise to input images and lets the diffusion model denoise them. We use DDIM sampler (Song et al., 2020) and the default noise schedule draw samples. Note that these choices are not optimal: our results can potentially be improved by using better noise schedules and the full DDPM sampling (Ho et al., 2020) which are known to work better. The implementation of the above APIs is straightforward without touch- ing the core modeling part of diffusion models and is similar to the standard API implementations Stable Diffusion (App. L).
Hyperparameters. We set number of iterations 7 20, lookahead degree k 8, and number of generated samples Nayn = 50000. For RANDOM _PI and VARIATION we use DDIM sam- pler with 100 steps. For VARIATION_AP! we use SDEEdit (Meng et al., 2021) by adding noise till [98, 96, 94, 92, 90, 88, 86, 84, 82, 80, 78, 76, 74, 72, 70, 68, 66, 64, 62, 60] timesteps for each iter- ation respectively. These timesteps can be regarded the parameter in $ 3.3.
For the experiments in Fig. 4, we use noise multiplier t E (5, 10, 20). and pick the the pareto frontier. Fig. 11 shows all the data points we got. Combining this figure with Fig. 4. we can that PE is not very sensitive to these with less optimal choices PE still outperforms the baselines.
L. v and threshold H = 21. for
and even
For the experiments in Fig. 5, we use noise multiplier o = 2 and threshold H = (i.e., = 1).
ffusion
23

---

Published as a conference paper at ICLR 2024
0 5v2, uncond
0 10v2, uncond
20
20v2, uncond
5v2, cond
15
10v 2, cond
20 2, cond
10
5
0.0
0.5
1.0
1.5
2.0
2.5
Epsilon
Figure 11: FID (lower is better) v.s. privacy cost e (6 = 10 on CIFARIO with different noise multipliers and thresholds. "(Un)cond" means (un)conditional generation. For the experiments in Figs. 3 and 13, (i.e.. f = 10) and the number of PE iteration is 5 (i.e., the point of "Ours (cond)" in Fig. 4 that has FID 7.9).
noise multiplier a 10.2 and threshold // 20
For downstream classification (Fig. 5), we follow (Ghalebikesabi et al., 2023) to use WRN-40-4 classifier (Zagoruyko & Komodakis, 2016). We use the official repo without changing any hyper- parameter except adding color jitter augmentation according to (Ghalebikesabi et al., 2023). The ensemble of the classifier is implemented by ensembling the logits.
FID evaluation. Compared to Fig, 4 in the main text, Fig. 12 shows the full results of two versions of (Harder et al., 2023). Baseline results are taken from (Harder al., 2023; Ghalebikesabi et al., 2023).
100
Ours (uncond)
Ours (cond)
80
DP-MEPF1 (uncond)
DEPMEPF2 (uncond)
DEPMEPF1 (cond)
60
DP-MEPFZ (cond)
FID
GA- (uncond)
OP-Diffusion (cond)
40
20
0
0.125 0.25
0.5
16 32
Epsilon
Figure 12: FID (Heusel et al., 2017) (lower is better) v.s. privacy cost CIFAR10 (Ō 10-5). Baseline results are taken from (Harder et al., 2023; Chalebikesabi et al., 2023). (Un)cond means (un)conditional generation. Ours achieves the best srivacy-qualiipe trade-off.
Classification accuracy. In & 5.1.1, we show the classification accuracy at single privacy budget é = 3.34. In Table 1, we further show how the classification accuracy evolves with respect to different es. These results are from the first PE iterations.
/https:/ h com/ ottp:///wooooooooooeooooaaaaaaa.
pytorch

---

Published as a conference paper at ICLR 2024
Accuracy
1.36
72. 72.46%
1.99
78. 78%7
2.50
80.83%
2,94
81.15%
3.34
81.74%
Table Classification accuracy v.s. privacy cost on CIFARIO 10-5).
Generated samples. See Figs. 13 and 14 for generated images and real images by-die.. Note that the pre-trained model we use generates 64x64 images, whereas CIFAR 10 is 32x32. In Fig. 3, we show the raw generated 64x64 images; in Fig. 13, we scale them down to 32x32 for better comparison with the real images.
Figure 13: Generated samples on CIFARIO with (0.67, 10 10-5))-PP Each row corresponds to one class. FID=7.87.
Figure 14: Real samples from CIFARIO.
Each row corresponds to one class.
Nearest samples in the private dataset Figs. 15 and 16 show generated images and their nearest neighbors in the private dataset evaluated using two distance metrics: & distance in the inception embedding space and the pixel space. We can see that the generated images are different from private images. This expected due to DP guarantee.
Distributions of the distances to nearest samples. Continuing the above experiments, we further show the distribution of the distances between (1) generated samples and their nearest real samples and (2) real samples and their nearest generated samples in Figs. 17 and 18 respectively. Two key observations are: (1) During the early PE iterations, the distances tend to decrease. This means that PE is effective in pushing the generated distribution be closer to the private distribution. (2) However, as PE continues, the distances stop decreasing. is expected, as DP upper bounds the probability of reconstructing any sample in the private dataset.
Samples with the highest and the lowest votes. Fig. 19 shows the samples with the highest and that
the lowest votes in DP Nearest Neighbors Histogram across different PE iterations. We DP Nearest Neighbors Histogram picks samples similar to the private data as desired. This is more obvious the first PE iterations, where DP Nearest Neighbors Histogram assigns high votes on the samples with correct classes and puts low votes on the samples with incorrect classes.
Distribution of counts in DP Nearest Neighbors Histogram. Fig. 20 shows that the standard deviation of counts in DP Nearest Neighbors Histogram tends to decrease with more PE iterations on CIFARI0. This means that the histogram becomes "more uniform" with more iterations. is expected for the following reasons. In the beginning, only few generated samples are close to the private data. Those generated samples get most of the votes from private samples, which results in concentrated histogram. PE will then pick those highly voted generated samples and do more
25

---

Published as a conference paper at ICLR 2024
variations over them. As result, private samples that voted for the same generated sample may now find different closest generated samples and distribute the votes, which results in a "more uniform" histogram.
26

---

Published as a conference paper at ICLR 2024
Figure 15: Nearest samples in the private dataset CIFAR10. In each row, the first column is a generated image (from Fig. 13), and the other columns are its nearest neighbors in the private dataset, sorted by the distance in ascending order. Every three rows correspond to generated image from one class. The distance metric is lz in the inception embedding space.
27

---

Published as a conference paper at ICLR 2024
Figure 16: Nearest samples in the private dataset CIFAR10. In each row, the first column is a generated image (from Fig. 13), and the other columns are its nearest neighbors in the private dataset, sorted by the distance in ascending order. Every three rows correspond to generated image from one class. The distance metric is lz in the pixel space.
28

---

Published as a conference paper at ICLR 2024
1.0
1.0
0.8
0.8
Iteration
Iteration
CDF
0.6
Iteration
0.6
Iteration
0.4
Iteration
0.4
Iteration
Iteration
Iteration
0.2
Iteration
0.2
Iteration
Iteration
Iteration
0.0
0.0
10
15
20
25
4000 Distance nearest neighbar
2000
Distance to nearest neighbor
(a) The distance metric is & in the inception embedding space.
(b) The distance metric is l in the pixel space.
Figure 17: CDF of the distributions between each generated sample and its nearest private sam- ples on CIFAR10 across different PE iterations. "Iteration 0" refers the initial random samples from Line 1 in Alg. 1.
1.0
1.0
0.8
Iteration
Iteration
CDF
0.6
Iteration
0.6
Iteration
Iteration
0.4
Iteration
Iteration
Iteration
0.2
Iteration
0.2
Iteration
Iteration
0.0
0.0
10
15
20
1000 2000 3000 4000 5000
Distance nearest neighbor
Distance to nearest neighbor
(a) The distance metric is &a in the inception embedding space.
(b) The distance metric is la in the pixel space.
Figure 18: CDF of the distributions between each private sample and its nearest generated sam- ples on CIFAR10 across different PE iterations. "Iteration 0" refers the initial random samples from Line 1 in Alg. 1.
29

---

Published as a conference paper at ICLR 2024
(a) Iteration=O.
(b) Iteration=1.
(c) Iteration=2.
(d) Iteration=3.
(e) Iteration=4.
(f) Iteration
Figure 19: Samples with the highest and the lowest counts in the DP Nearest Neighbors Histogram on CIFAR1O. In each subfigure, each row corresponds to one class; the left subfigure shows the samples with the highest counts and the right subfigure shows the samples with the lowest counts.
30

---

Published as a conference paper at ICLR 2024
12
DP counts
Std of counts in DP NN Histogram
10
8-
6-
4-
2
PE iteration
Figure 20: The standard deviation of counts in DP Nearest Neighbors Histogram across different PE
iterations on CIFARIO. "DP counts" refers to the counts after adding Gaussian noise and threshold- ing. "Non-DP counts" refer to the counts before adding Gaussian noise and thresholding.
31

---

Published as a conference paper at ICLR 2024
K
MORE DETAILS AND RESUTLS ON CAMELYON 17 EXPERIMENTS
Pre-trained model. We use the checkpoint imagenet _4 270M 250K, pt released in (Nichol & Dhariwal, 2021)."?
API implementation. Same App. J.
Hyperparameters. We set lookahead degree 8, and number of generated samples Nsyu 302436.
About the experiments in Fig. 21. For RANDOMLAPI and VARIATION we use DDIM sam- pler with 10 steps. For VARIATION API, we take a 2-stage approach. the first stage, we use DDIM sampler with 10 steps and use SDEEdit (Meng et al., 2021) by adding noise till [10, 10, 10, 10, 9, 9, 9, 9,9,9,8 8, 8, 8, 8, 8, 7, 7, 7, 7] timesteps for each iteration respectively. In the sec- ond stage, we use DDIM sampler with 40 steps and use SDEEdit (Meng et al., 2021) by adding noise till [20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 6, timesteps for each iteration respec- tively. These timesteps can be regarded as the v parameter $ 3.3. We use noise multiplier v2 2.2 and threshold = 4.
About the experiments in & 5.1.2. For RANDOMLAPI and VARIATION_AR we use DDIM sampler with 10 steps. For VARIATION we use DDIM sampler with 10 steps and use SDEEdit (Meng et al., 2021) by adding noise till [10, 10, 10, 10, 9, 9, 9] timesteps for each iteration respectively. These timesteps can be regarded as the parameter in $ 3.3. We use noise multiplier o 1.381 and threshold H 4.
Generated samples. See Figs. 21 and 22 for generated images and real images side-by-side Note that the real images in Camelyon17 dataset are 96x96 images, whereas the pre-trained network is 64x64. In Fig. 22, we scale them down to 64x64 for better comparison.
Fig. 23 shows the generated images in the intermediate iterations. We images are effectively guided towards Camelyon17 though it is very different from the pre-training dataset.
that the generated
Figure 21: Generated samples on Came- Iyon17 with (9.92.3 3- 10-9) -DP. The first five rows correspond to one class, and the rest correspond to the other class. FID=10.66.
Real samples from Camelyon The first five rows correspond to one class, and the rest correspond to the other class.
Figure 22:
Nearest samples in the private dataset Figs. 24 and 25 show generated images and their nearest neighbors in the private dataset evaluated using two distance metrics: & distance in the inception embedding space and the pixel space. Similar the results in CIFARIO, 10, we can see that the gener- ated images are different from private images. This is expected due to the DP guarantee.
ffusson
32

---

Published as a conference paper at ICLR 2024
Iteration=O.
(b) Iteration=1.
(c) Iteration=3.
(d) Iteration=5.
(e) Iteration=7.
(1) Iteration=9.
(g) Iteratio=11..
(h) Iteration=13. 13.
(i) Iteration= 15.
Iteration=17.
Iteration=19,
Iteratio=21.
(m) Iteration=23.
Iteration=25.
Iteration=27.
Figure 23: Generated samples on Camelyon17 at the first few iterations. We can see that the gener- ated images are gradually guided from ImageNet, the pre-training dataset, to Camelyon17, the (very different) private dataset. "Iteration=O" means the initial random samples from RANDOM API.
33

---

Published as a conference paper at ICLR 2024
Samples with the highest and the lowest votes. Fig. 26 shows the samples with the highest and the lowest votes in DP Nearest Neighbors Histogram across different PE iterations. We can see that DP Nearest Neighbors Histogram gradually picks samples with the right patterns as the private data, and drops samples with more different patterns. As Camelyon17 is further away from the pre-training dataset ImageNet than CIFARIO, we can see that it converges slower than the case in CIFARIO (Fig. 19).
Distributions of the distances to nearest samples. Continuing the above experiments, we further show the distribution of the distances between (1) generated samples and their nearest real samples and (2) real samples and their nearest generated samples in Figs. 27 and 28 respectively. Similar to the CIFAR10 experiments (Figs. 17 and 18), we see that: (1) During the early PE iterations, the inception distances tend to decrease. This means that PE is effective in pushing the generated distribution to be closer to the private distribution. (2) However, as PE continues, the inception distances stop decreasing. It is expected, as DP upper bounds the probability of reconstructing any sample in the private dataset. However, one difference to CIFARIO results is that the distance between each generated sample and its nearest private samples measured in the original pixel space (Fig. 27b) tends to increase. We hypothesize that it is be due to nature of this dataset that any shifts of the histological images are still in-distribution but can result in a high distance in the original pixel space.
Distribution of counts in DP Nearest Neighbors Histogram. Fig. 29 shows that the standard deviation of counts in DP Nearest Neighbors Histogram tends to decrease with more PE iterations on Camelyon17. This accords with the observations and takeaways messages in CIFARIO (Fig. 20).
Inspescting the ImageNet class labels of the generated samples. As discussed in App. I, each generated samples have an associated ImageNet label. Here, we inspect those labels to under- stand how PE works in this dataset. The list of the labels and their associated number of generated images are: "honeycomb" (164647), "velvet" (83999), "nematode, nematode worm, roundworm" (35045), "handkerchief, hankie, hanky, hankey" (14495), "bib" (3102), "head cabbage" (934), "bub- ble" (142), "stole" (72). We see that 54.4% images are with the label "honeycomb". Many honey- comb images in ImageNet have "net-like" structure, which shares some similarities with Came- lyon17. However, the details, colors, and structures are still different. We compute the FID between honeycomb images and CIFARIO. The FID score is 162.86, which is much higher than the FID score of the final generated images we get (10.66 in Fig. 21). These results show that the existence of the honeycomb class in ImageNet helps with PE, but PF does more than just picking this class.
Why PE works under large distribution shifts. The fact that PE is able to make ImageNet-pre. modees to generate Camelyon17 images may appear surprising to readers. Here, we provide intuitive explanations. Even though the diffusion model is trained on natural images, the support of the generated distribution could be very large due to the formulation. More concretely, let's look at two examples: ccore-based models (Song& & Ermon, 2019). which is closely related to diffusion models, and the diffusion model we used (Ho et al., 2020). For score-based models, its modeling target is distribution perturbed by Gaussian noise, and therefore, the generated distribution spans the entire sample space. For diffusion models (Ho et al., 2020), the latent space has the same size as the image, and the last denoising step is modeled as distribution derived from a Gaussian distribution that spans the entire pixel space (see Section 3.3 of Ho et al. (2020)). Therefore, the generated distribution of diffusion models also spans the entire sample space.
In other words, for any (trained) score- score-based models or diffusion models, it is theoretically possible to generate images similar to the private dataset (or in fact, generate any images). The problem is that the probability of generating such images is small if there is large distribution shift from the pre-training data to the private data. PE is effective in guiding the diffusion model to generate samples from the region that is low-density in the original pre-trained distribution but high-density in the private distribution.
To make it more concrete, we provide how the generated images evolve from natural images to Camelyon17 17 dataset Fig. 23 and the selected/filtered samples by PE in Fig. 26. At every iteration, PE selects the set of images that are most similar to Camelyon17 dataset (Fig. 26). Those images might still appear different from Camelyon17 in carly iterations. However, as long as we get im- ages that are more similar to Camelyon17 17 through VARIATION API at every iteration, we will make progress, and finally, we can get images similar to Camelyon17 (Fig. 21).
34

---

Published as a conference paper at ICLR 2024
We further experiment PE under different levels of distribution shifts. To do that, we take the Came- 1yon17 dataset and modify the saturation the images to create sequence of datasets, each with different saturation change. This way, we create sequence of datasets with different levels of distri- bution shifts from ImageNet. From Fig. 30, we can see that no matter what the level distribution shifts is, PE can consistently improve the generated distribution towards the private data.
35

---

Published as a conference paper at ICLR 2024
Figure 24: Nearest samples in the private dataset Camelyon17. In each row, the first column a generated image (from Fig. 21), and the other columns are its nearest neighbors the private dataset, sorted by the distance in ascending order. Every fifteen rows correspond generated image from one class. The distance metric is &g in the inception embedding space.
36

---

Published as a conference paper at ICLR 2024
Figure 25: Nearest samples in the private dataset Camelyon17. In each row, the first column a generated image (from Fig. 13), and the other columns are its nearest neighbors the private dataset, sorted by the distance ascending order. Every fifteen rows correspond generated image from one class. The distance metric is &g in the pixel space.
37

---

Published as a conference paper at ICLR 2024
(a) Iteration=O.
(b) Iteration=l.
(c) Iteration=2.
(d) Iteration=3.
(e) Iteration=4.
(f) Iteration=5.
Figure 26: Samples with the highest and the lowest counts in the DP Nearest Neighbors Histogram on Camelyon17. 17 In each subfigure, each row corresponds to one class; the left subfigure shows the samples with the highest counts and the right subfigure shows the samples with the lowest counts.
1.0
0.8
0.8
Iteration
Iteration
CDF
0.6
Iteration
0.6
Iteration Iteration
Iteration
0.4
0.4
Iteration
Iteration
0.2
Iteration
0.2
Iteration
Iteration
0.0
Iteration
0.0
Iteration
10
20
30
2000
4000
6000
8000
Distance to nearest neighbor
Distance to nearest neighbar
(a) The distance metric f2 in the inception embedding space.
(b) The distance metric is in the pixel space.
Figure 27: CDF of the distributions between each generated sample and its nearest private sam- ples on CIFAR10 across different PE iterations. "Iteration ()" refers to the initial random samples from Line 1 in Alg. 1.
1.0
1.0
0.8
0.8
CDF
0.6
Iteration
0.6
Iteration
0.4
Iteration
0.4
Iteration
Iteration
Iteration
0.2
Iteration
0.2
Iteration
Iteration
Iteration
0.0
0.0
5
10
15
20
0
10000 Distance nearest neighbor
5000
Distance to nearest neighbor
(a) The distance metrie is &2 in the inception embedding space.
(b) The distance metric is lz in the pixel space.
Figure 28: CDF of the distributions between each private sample and its nearest generated sam- ples on CIFAR10 across different iterations. "Iteration 0" refers the initial random samples from Line 1 in Alg. 1.
38

---

Published as a conference paper at ICLR 2024
120
Std of counts in DP NN Histogram
Non counts
100
60
40
10
PE iteration
Figure 29: The standard deviation of counts in DP Nearest Neighbors Histogram across different PE iterations on Camelyon17. "DP counts" refers to the counts after adding Gaussian noise and thresholding. "Non-DP counts" refer to the counts before adding Gaussian noise and thresholding.
300
Original Camelyon17
Saturation +100
Saturation +200
200
FID
100
PE iteration
Figure 30: FID vs. PE iterations under Camelyon17 variants with different levels of distribution shifts.
39

---

Published as a conference paper at ICLR 2024
L MORE DETAILS AND RESULTS ON STABLE DIFFUSION EXPERIMENTS
Dataset construction. We start with cat photos taken by the authors, crop the region around cat faces with a resolution larger than 512x512 manually, and resize the images to 512x512. We construct two datasets, each for one cat with 100 images. See Figs. 31 and 32 for all images. Note that having multiple samples from the same identity is not meaningful from the practical perspective of DP. Instead of regarding these datasets real-world cases, they should be treated as "toy datasets" for experimenting DP generative models with small number of high-resolution images.
Figure 31: All images from Cat Cookie dataset. The original resolution is 512x512; we resize them to 128x128 here for reducing the file size the paper.
API implementation. We use off-the-shelf open-sourced APIs of Stable Diffusion. For RAN- DOM_API, we use the text-to-ing eext-to-image generation 18 which is implemented by the standard diffu- sion models' guided sampling process. For VARIATION API, we use the image-to-image generation 19 which allows us to control the degree of variation. Its internal implementation is SDEdit (Meng al,, 2021), which adds noise the input images and runs diffusion models' denoising process.
Hyperparameters We lookahead degree 8, and number of generated samples Nayn 100. For RANDOMLAPI and VARIATION_API we use the default DDIM sampler with 50 steps. For RANDOM LAII, we use the prompt "A photo of ragdoll cat". This gives reaonable cat images but still far away from the private data (Fig. 35). For VARIATION we use variation de- grees [0.98, 0.96. 0.94, 0.92, 0.90, 0.88, 0.84, 0.8, 0.76, 0. 0.64, 0.6] for each iteration re-
cext2img http:///aaaaaaaoooo////.///////a
img2
40

---

Published as a conference paper at ICLR 2024
Figure 32: All images from Cat Doudou dataset. The original resolution is 512x512; we resize them to 128x here for reducing the file size of the paper.
spectively with the same prompt. We use noise multiplier a 2 and threshold H = 2. We use inception embedding for Eq. (1).
Generated images. We use the same hyper- paremeerrssssssss to run PE on two datasets separately. This also be regarded rumning the conditional version of PE (Alg. 3) on the whole dataset (with labels Cat Cookie or Cat Doudou) together. All generated images are in Figs. 33 and 34. While the two experiments
completely the same hyper-parametent and the initial random images different from the cats (Fig. 35), our PE can guide the generated distribution in the right direction and the final generated images do capture the key color and characteristies of each of the cats. This demonstrates the effectiveness of PE with large foundation models such as Stable Diffusion.
very
We also observe that the diversity of generated images (e.g., poses, face directions) is limited com- pared to the real data. However, given the small number of samples and the tight privacy budget, this an expected behavior: capturing more fine- ine-grained features of each image would likely violate DP.
Generated images with more diversity. To make the generated images more diverse, we can utilize the approach in $ 4.2, which passes the generated images through VARIATION API, We have demonstrated in 5.1.3 that this approach can generate more samples that are useful for downstream classification tasks. Here, we use it for a different purpose: enriching the diversity generated samples.
Figure Figs. 36 and show the results. We can see that this simple approach able to generate cats with a more diverse appearance. This is possible because the foundation model (Stable Diffusion) has good prior knowledge about cats learned from massive pre-training, and PE is able to utilize that effectively.
41

---

Published as a conference paper at ICLR 2024
Figure 33: All generated images from Cat Cookie dataset with (6.62, 10 10- The original reso- lution is 512x512; we resize them to 288 128 here for reducing the file size of the paper.
42

---

Published as a conference paper at ICLR 2024
Figure 34: All generated images from Cat Doudou dataset with (6.62, 10 10- -DDDP The original reso- lution is 512x512; we resize them to 128 here for reducing the file size of the paper.
43

---

Published as a conference paper at ICLR 2024
Figure 35: The initial random images from Stable Diffusion. The original resolution is 512x512; resize them to 128x 128 here for reducing the file size of the paper.
44

---

Published as a conference paper at ICLR 2024
Figure 36: Generated images with enhanced diversity using the approach in 4.2 on Cat Cookie.
The original resolution is 512x512; we resize them to 128x 128 here for reducing the file size of the paper.
45

---

Published as a conference paper at ICLR 2024
Figure 37: Generated images with enhanced diversity using the approach in $ 4.2 on Cat Doudou.
The original resolution is 512x512; we resize them to 128x 128 here for reducing the file size of the paper.
46

---

Published as a conference paper at ICLR 2024
M CINIC EXPERIMENTS
Given that PE is based on sampling from pre-trained foundation models, a natural baseline is to conditionally sample from the classes closest to the private data. For example, in the experiments of $ 5.1.1 (C 10 as private data, ImageNet as the public data), it would be interesting to con- sider baselines that conditionally sample from the same classes in CIFARIO 10 (with privacy) from foundation model trained on ImageNet. However, there could be many ways to implement such an algorithm, and the model and hyper-part parameeer choices could impact the result. To climinate the in- fluence of these arbitrariness choices, we conduct the following experiment which gives an estimate on the best FID such approach could achieve.
Experiment setup. We use CINIC1O dataset (Darlow et al., 2018), which contains CIFARIO images and the filtered images from ImageNet that belong CIFARIO categories. We compute the FID between (a) the subset of CINICIO images that come from ImageNet (i.e., excluding CIFARIO images from CINICIO dataset), and (b) CIFARIO dataset. This is to simulate the best case when the foundation model (1) learns the ImageNet dataset perfectly and (2) is able to draw only the samples from CIFARIO classes. In practice, the above two assumptions will certainly not hold; especially, achieving (2) would necessarily incur privacy costs as the knowledge of which samples belong to CIFAR1O is assumed to be private. Therefore, this process gives us lower bound of the FID (i.e., the best possible FID) we can get by such a baseline that samples the same classes as CIFARIO from an ImageNet model using an arbitrary privacy cost.
Results. The FID score from the above is 12.21. We can see from Fig. 4 that PE is able to achieve a smaller FID with e as small as 0.38. This result suggests that PE does a non-trivinn non-trivial job: it can achieve a lower FID score than simply sampling the same classes CIFARIO from an ImageNet model.
N MORE ABLATION STUDIES
All ablation studies are conducted by taking the default parameters in unconditional CIFARIO ex- periments and modifying one hyperparameter at time. The default noise multiplier 5- /2 and the default threshold H = 10.
Lookahead degree. Fig. 38 shows how the lookahead degree k ($ 4) impacts the results. We can see that higher lookahead degrees monotonically improve the FID score. However, the marginal benefits diminish as the lookahead degree goes beyond 8, and higher lookahead degree increases the required of API calls. Throughout all experiments, we used k = 8. This experiment suggests that better results can be obtained with a higher k. In practice, we suggest users set the lookahead degree as the highest value within their computation or API budget.
Lookahead=0
14
Lookahead-4
12
Lookahead=8
Lookahead=12
2
10
0.5
1.0
1.5
2.0
2.5
Epsiion
Figure 38: Ablation studies on the lookahead degree for DP Nearest Neighbors Histogram. Looka- head=0 means lookahead is not used (Eq. (1)).
Population size. Fig. 39 shows how the number of generated samples Neyn impacts the results in non-DP setting. We can see that, as the number of samples increases, FID score monotonically gets better. This expected because with more generated samples, there are higher chances to get samples similar to the private data. However, we want to point out that in the DP case, it may not be true, as large number of samples would flatten the DP Nearest Neighbors Histogram and thus decrease the signal noise ratio.
47

---

Published as a conference paper at ICLR 2024
Number 50mples=50000
Number of 8am0les-80000
Number sample=-100000
8
5
10
15
20
Step
Figure 39: Ablation studies on the number of generated samples Nayn in non-DP setting. Histogram threshold. Fig. 40 shows how the threshold H in DP Nearest Neighbors Histogram impacts the results. We can see that a large threshold results in faster convergence speed at the beginning. This is because, the early iterations, many samples are far away from the private data. A larger threshold can effectively remove those bad samples that have non-zero histogram count due the added DP noise. However, already close to the private data. A large threshold may potentially remove useful samples (e.g., the samples at low-density regions such as classifier boundaries). This may hurt the generated data, as shown in the increasing FID scores at threshold=15. In this paper, used fixed threshold across all iterations. These results suggest that an adaptive threshold that gradually decreases might work better.
later iteration, the distribution of generated samples is
Threshold=0
Threshold-5
20
10
Threshold=15
0 15
10-
5
0.5
1.0
1.5
2.0
2.5
Epsilon
Figure 40: Ablation studies on the threshold H for DP Nearest Neighbors Histogram.
Embedding. Fig. 41 compares the results with inception embedding CLIP embedding in Eq. (1)- The results show that both embedding networks work well, suggesting that PE is not too sensitive to the embedding network. Inception embedding works slightly better. One reason is that the inception network is trained on ImageNet, which is similar to a private dataset (CIFARIO). Therefore, it might be better at capturing the properties of images. Another possible reason is that FID score is caleu- lated using inception embeddings, which might lead to some bias that favors inception embedding.
The number of private samples. In this experiment, show how the number of private samples Npriv impacts the performance of PE. Specifically, on CIFARIO, we vary the number of samples N priv by sub-sampling. For each Npriv E (50000, 20000, 10000, 5000):
We fix Noyn/ /prive when running PF.
Inception embedding
12
Clip embedding
0.5
1.0
1.5
2.0
2.5
Epsilon
Figure 41: Ablation studies on the embedding network in Eq. (1) to use.
48

---

Published as a conference paper at ICLR 2024
After PS is done, we use the approach in $ 4.2 to augment the number of generated samples back to 50000, and compute the FID between the generated samples and CIFAR 10.
All other hyyer-parametent are set the same as the CIFARIO experiments in Fig. 3.
The results are shown in Table 2, which suggests that larger N ppriv helps the performance of PE, sim- ilar to the observation in DP-SGD (Anil et al., 2021). We hypothesize that the reason as follows. When we set /Nya//Npxs pziv togram remains constant, larger N does allow the generated samples to explore larger space, and therefore it is more likely to get a sample closer to the private data, which helps the convergence of PE. Our theorem in App. also shows that increasing the number of variations (which controlled by N Ngnn) speeds up the convergence.
although the signal-noise ratio in the DP Nearest Neighbors His-
Number of samples
FID
50000 (original CIFARIO)
7.87
20000 (2.5x smaller)
10.47
10000 (5x smaller)
12.51
5000 (10x smaller)
18.60
Table 2: FID vs. the size of the private dataset in CIFAR10.
0 GENERATING MORE SAMPLES
We discussed two ways of generating more samples after PE is done: (1) taking the final generated samples from PE and passing them through VARIATION to get more samples 4.2), and (2) using a larger Nayn when running PE (Fig. 39). While we see that both approaches are promising, they have a key difference: the first approach can be applied post hoc without the need to rerun PE, whereas the second approach requires rerunning PE. This difference would result in a very different number of API calls. More concretely, let's say we want to generate N more samples after PE is done. In the former approach, we simply take the final generated samples from PE and call VARIATION
times. contrast, the latter approach requires rerunning the entire PE process and would need to increase the number of API calls by N (k + 1), we will need to generate more samples at every iteration.
P COMPUTATIONAL COST EVALUATION
We compare the GPU hours of the SOTA DP fine-tuning method (Ghalebikesabl et al., 2023) and PE for generating 50k samples in $ 5.1.1. Note that PE is designed to use existing pre-trained models and we do so in all experiments. In contrast, DP fine-tuning methods usually require a careful se- lection of pre-trate pre-training datasets and architectures (c.g.. (Ghalebikesabi et al., 2023) pre-trained their own diffusion models), which could be costly. Even if we ignore this and only consider the compu- tational cost after the pre-training, the total computational cost of PE is only 37% of (Ghalebikesabi al., 2023) while having better sample quality and downstream classification accuracy ($ 5.1.1). See Fig. 42 for detailed breakdown of the computational cost. Note that PE's computational cost mostly the APIs.
The key takeaway is that even if practitioners want to run the APIs locally (i.e., downloading the foundation models and running the APIs locally without using public API providers). there still benefits of using PE: (1) The computational cost of PE can be smaller than training-base methods. (2) Implementing and deploying PE are easier because PE only requires blackbox APIs of the models and does not require code modifications inside the models.
Experimental details. In this experiment, we follow the setting in $ 5.1.1, where the user has private dataset of size Npriv 50000 and a pre-trained model (hosted locally, running on GPUs), and wants to generate a total number of Nayn
50000 synthetic data samples. For the DP fine- tuning baseline, the procedure includes (1) DP fine-tuning the pre-trained model, and then (2) using the fine-tuned model generate 50000 synthetic samples. Therefore, we break the time into these two parts. For PE, the procedure includes running PE with Nayn 50000. PE includes the steps
49

---

Published as a conference paper at ICLR 2024
of RANDOM API, VARIATION API, nearest neighbor search, and feature extraction. Therefore, we break down the time of PE into these four parts.
In the above evaluation, we did not consider the time of generating more samples beyond Neyn 50000, and we discuss its effect here. To generate more samples beyond Nayn 50000 samples, the DP fine-tuning method can directly use the fine-tuned model to generate more samples without more fine-tuning. PE can use the approach in $ 4.2, where we pass the generated Nayu samples through VARIATION to generate more samples (what did in 5.1.3; see results thereof). Note that, for the same size of the model, the same number of generated samples, the same diffusion sampler, and the same total number of denoising steps, the running time of PE to generate more samples is smaller than the DP fine-tuning baseline. The reason is as follows. Let's say we use a diffusion sampler with 100 steps in total. In the DP fine-tuning baseline, generated samples must take all 100 steps (i.e., starting from Gaussian noise, passing the image through the diffusion model 100 times iteratively get the final generated samples). For PE, VARIATION API is implemented by SDEdit (Meng et al., 2021) (see App. J). where we add noise to input images and let the diffusion model denoise them starting from the middle of the diffusion process (e.g., adding Gaussian noise to the image, then passing the image through the diffusion model starting from 20th denoising step for all the rest 80 steps iteratively to get the final generated samples). In other words, each generated does not need to go through all 100 steps, but only fraction of the steps (80 steps in the above example).
To ensure a fair comparison, we estimate the runtime of both algorithms using 1 NVIDIA V100 32GB GPU.
To evaluate the computational cost of (Ghalebikesabi et al., 2023), we take the open-source diffusion model implementation from (Dhariwal & Nichol, 2021)a0 and modify the prper-parameters accord- ing to (Ghalebikesabi et al., 2023). We obtain a model with 79.9M parameters, slightly smaller than the one reported in (Ghalebikesabi et al., 2023) (80.4M). This difference might be due to other implementation details that are not mentioned in (Ghalebikesabi et al., 2023). To implement DP training, we utilize Opacus library (Yousefpour al., 2021). To evaluate the fine-tuning cost, torch. cuda. Event instrumented before and after the core logic of forward and backward pass, ignoring other factors such as data loading time. We estimate the total runtime based on the mean runtime of 10 batches after 10 batches of warmup. We do not implement augmentation multiplicity with data and timestep (Ghalebikesabi et al., 2023); instead, we use multiplicity=1 (i.e., a vanilla diffusion model), and multiply the estimated runtime by 128, the multiplicity used in (Ghalebikesabi et al., 2023). To evaluate the generation cost, we use torch. cuda. Event instrumented before and after the core logic of sampling. We estimate the total runtime based on the mean runtime of 10 batches after batch of warmup.
To evaluate the computational cost of our PE, we use a similar method: we use torch. cuda. Event instrumented before and after the core logic of each component of our al- gorithm that involves GPU computation. RANDOMLAPI and VARIATION_API are estimated based on the mean runtime of 10 batches after batch of warmup. Feature extraction is estimated based on the mean runtime of 90 batches after 10 batch of warmup. The nearest neighbor search is timated based on run of the full search. We use faiss library for nearest neighbor search. Its implementation very efficient its computation time is negligible compared with the total time.
20 htt.pppr///tttaaccoco////o/////p htttee///hhaaaaccccccccootttttte
50

---

Published as a conference paper at ICLR 2024
1250
Fine-tuning (1210.7)
Generation (17.1)
1000
VARIATION API (440.4)
GPU Hours
RANDOM_AR LAI (10.4)
750
Nearest neighbor search (0.0)
Feature extraction (0.7)
500
250
DP-Diffusion
Ours
Figure 42: GPU hours (on 1 NVIDIA V100 32GB) required to obtain the samples for $ 5.1.1 with DP-Diffusion (Ghalcbikesabi et al., 2023) and ours. The legend denotes the steps and the GPU hours; (Ghalebikesabl et al., 2023) contains the fine-tuning and generation steps, whereas ours contains the other steps.
51


Reviews:
[{"review_id": "QHf7Ar03gp", "reviewer": "Reviewer_eX7J", "summary": "This paper studies the differentially private (DP) generation of image data through the black-box usage, namely via APIs, of pre-trained foundation generative models like Stable Diffusion. In particular, this work proposes using evolutionary algorithms that progressively refine the synthetic dataset/distribution to better align with the real private distribution. The real private distribution is represented as a histogram, , which quantifies how frequently each current synthetic sample is the nearest neighbor (determined by l2 distance in an embedding space) to real data samples from the private dataset. To achieve DP, noise is added to the histogram. Experimental evidence shows that the suggested application of pre-trained generative APIs yields noticeable improvements compared to previous methods that either do not use public data or utilize it within a pre-training & fine-tuning setup.", "questions": "- Several hyperparameters appear to be crucial for the proposed approach, including the threshold for DP NN and the lookahead degree. It would be helpful to provide further discussion on the selection of these hyperparameters. Specifically, insights into their transferability across different datasets and any computational trade-offs in practical scenarios would be beneficial.\n\n- I appreciate the qualitative results, such as the generated samples and their NN among real data. However, I would expect additional quantitative evaluation, perhaps in the form of histograms or average results, for the NN distances (both from real to closest generated and from generated to closest real). This may help provide critical insights into the fidelity of the generated samples, the approximated data likelihood, and the empirical privacy leakage.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The paper is generally well-written and easy to follow. \n- The idea of exploiting pre-trained foundation model APIs is natural and practical\n- The experimental findings are mostly encouraging and show promising results. The results are extensive and cover various key aspects regarding the usage of the proposed approach.", "weaknesses": "- The core DP component of the approach (i.e., adding DP noise to the histogram) is largely an existing idea/mechanism, which slightly diminishes the overall technical contribution of this submission.\n\n- While the proposed approach demonstrates encouraging results on Camelyon17 dataset where the distribution shifts between the public and private distribution is relatively large, its performance may start to fall short compared to the more straightforward pre-training and fine-tuning paradigm (as the curves look not saturating and only one privacy level is presented).  A more in-depth exploration of the limits (in terms of tolerance to distribution shifts) of the pure API method (potentially by considering other medical datasets) and a discussion on potential refinements or extensions of the proposed approach would further strengthen the submission.", "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": "", "extra_scores": {}}, {"review_id": "JYAXKB7Oxe", "reviewer": "Reviewer_yzwb", "summary": "This paper focuses on the problem of generating differentially private synthetic data. In particular, this paper proposes a DP Synthetic Data via APIs method to generate a DP synthetic dataset whose distance to private dataset is minimized by utilizing foundation model inference APIs while protecting privacy of private samples. The proposed method mainly works as follows: \n1) Calling RANDOM API to initialize the population through randomly generating samples; \n2) Differentially private evaluation of the usefulness of each sample in the population by computing the the noisy number of private samples whose nearest neighbor in the population is this particular sample; and\n3) Calling VARIATION API to generate variants of the useful samples.", "questions": "I have made some suggestions in the Weaknesses box. I am already happy with this submission, but willing to increase my score further if the authors can address those suggestions.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1)  A novel way of addressing the problem of generating differentially private synthetic data through iteratively using private samples to vote for the most similar samples generated from the blackbox model and ask the blackbox models to generate more of those similar samples;\n\n2) A nice application of leveraging the power of large foundation models;\n \n3) Providing theoretical analysis proving the convergence of the distribution of generated samples by the proposed method to the private distribution\n\n4) Very clear presentation and easy-to-follow\n\n5) Proposing a training-free approach while matching or even outperforming state-of-the-art (SOTA) methods that they need a customized training process and significant ML engineering efforts", "weaknesses": "1) Can you discuss the effect of the size of the private dataset on the performance of the proposed method?\n2) Incomplete downstream classification accuracy v.s. privacy. Figure 5 compares the downstream classification accuracy of the proposed method versus another DP synthetic data generation approach. Can you compare the proposed method with SOTA DP training models on raw data to see which one is better for the downstream classification tasks? \n3) Overclaim. Section 4 starts by saying \"Data type. While our framework above and our algorithms in § 4 are general for any data type, we focus on images in our experiments.\" However, it is not clear how this can be done for example for text because of the complexity of textual information and also for audio because of the lack of speech-based APIs. I would either remove this statement or try to discuss how this extension can be done.\n4) As this paper says in Section 4 \"Foundation models have a broad and general model of our world from their extensive training data.\" so how do you make sure the images that you consider as private (for example CIFAR-10 in your case) are not used in the training of foundation models of used APIs? I think this somehow affects the practicality of the proposed method in practice. After reading the experiment section, it seems this paper does not use real-world APIs and instead, this paper tries to simulate this in a controlled environment by considering pre-trained models.\n5) The claim of the proposed method being easier to deploy than existing methods is not supported. I would at least empirically validate this by measuring its costs in comparison to existing ones.\n6) It would be good to also talk about the limitations of DP synthetic data in general especially when data is distributed across users and cannot be centralised in one place.", "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": "", "extra_scores": {}}, {"review_id": "ShZvTD5Hun", "reviewer": "Reviewer_wkXZ", "summary": "The paper introduces a novel approach to generate differentially private (DP) synthetic data via API calls to a foundation model, focusing on image data. The authors present a framework named Private Evolution (PE) -- each evolution iteration involves building a privatized histogram, bootstrapping the distribution, and calling the API to generate more similar images. Experiments on CIFAR10 and a medical image dataset demonstrates compelling results.", "questions": "Most of the points in weaknesses are presented as questions. I'd appreciate it if the authors can provide corresponding responses.", "limitations": "", "rating": 6, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The paper introduces a novel approach to generating DP synthetic data without the need for training, which is a significant departure from traditional methods.\n2. The utilization of the foundation model APIs allow for easier deployment and the exploitation of the capability obtained in large-scale pre-training.\n3. The paper presents strong experimental results, particularly the improvement in privacy cost while achieving competitive FID scores on CIFAR10.", "weaknesses": "1. **Privacy guarantee**: 1) The query at each iteration depends on the output of the last iteration; such adaptive queries lead to correlated outputs. This may potentially amplify the privacy loss. 2) If the underlying model of the API memorizes information from the queries (and can even update the model based on user interactions, such as what OpenAI does for GPT-4), there could be long-term privacy implications, especially that at later iterations, the data fed back to the API are highly similar to the private data.\n2. **Generalization beyond images**: The algorithm in this paper is highly dependent on the capability of the API. In this work the authors only focused on the image data. Can the authors comment on the generalizability of the method on other data types, e.g., text data, tabular data, etc.?\n3. **Conditional generation**: The authors treat the conditional generation as unconditional generation for each class. This is a valid approach, but think about the scenario where there are many classes and only a few images per class (e.g., CelebA dataset with 10k classes and ~20 images per class), it may be better for the algorithm to not limit itself to one class of data. Can the authors comment on how they would adapt the algorithm for such type of data, and the utility? (One might expect that the threshold needs to be low to accommodate for the few number of images per class, but this means more noise).\n4. **Monetary cost of the algorithm**: The authors mentioned the foundation models \"including GPT4, Bard, and DALLE2 (that) only provide API access without releasing model weights or code\". For those models: 1) often the API calls are not inexpensive; 2) they may support fine-tuning access. Can the authors discuss the costs of the two routes (DPSDA vs. DP finetuning)? \n5. **Diversity-utility trade-off**: I'm curious about whether calling more VARIATION_API will hurt the utility. Apparently the diversity increases because there's no longer constraints in producing nearest neighbor images. But without this constraint, and without the knowledge of how the foundation model API produces a \"similar\" image, how can we be sure about retaining similar level of data utility? The results in Fig. 5 are encouraging results, but I'd appreciate more evaluation to directly corroborate the argument, e.g., using the initial 50k images to train a classifier, and compare with another 50k after calling the API for a few times.\n6. **Missing related work**: A few published works on DP synthetic data are missing, to name a few, [1,2,3].\n7. **Evaluation**:\n   1. Fig. 6 presented generated Camelyon17 images with (9.92, 3x10^{-6})-DP. I wonder why the authors didn't report the accuracy on this generated dataset while instead reported the numbers for the \\epsilon=7.58 dataset? Clearly it's more fair to compare the \\epsilon=9.92 results with the \\epsilon=10 results from the prior work. I appreciate it if the authors can add the result.\n   2. More details on ensemble in the main paper is appreciated. Are the 5 classifiers trained on disjoint datasets each of 0.2M samples? Is this the same setup as Ghalebikesabi et al.? (because 0.2M samples for a CIFAR classifier seem a lot.) \n   3. I appreciate the effort of the authors putting up their own private dataset for evaluation. However, I have reservations about the experimental setting in Sec 5.2. In its current form, Sec 5.2 only serves the visual demonstration purpose. But one dataset with datapoints contributed all by one single identity makes little sense when talking about DP. A dataset with e.g. 5 cats and 20 images each would be better. It would be possible to further evaluate the utility of the synthesized data then.\n8. **Minor**\n   1. Grammar issue: Sec 4.1, \"the (privatized) number of private numbers whose\"\n   2. The position and the order of the footnotes are messed up\n   3. It is not appropriate to use \"Cat Cookie\" and \"Cat Doudou\" in a research paper. Use Cat A and Cat B instead \n\n**References**\n\n[1] Vinaroz, M., Charusaie, M. A., Harder, F., Adamczewski, K., & Park, M. J. (2022, June). Hermite polynomial features for private data generation. In International Conference on Machine Learning (pp. 22300-22324). PMLR.\n\n[2] Hu, Y., Wu, F., Li, Q., Long, Y., Garrido, G., Ge, C., ... & Song, D. (2023, October). SoK: Privacy-Preserving Data Synthesis. In 2024 IEEE Symposium on Security and Privacy (SP) (pp. 2-2). IEEE Computer Society.\n\n[3] Cao, T., Bie, A., Vahdat, A., Fidler, S., & Kreis, K. (2021). Don’t generate me: Training differentially private generative models with sinkhorn divergence. Advances in Neural Information Processing Systems, 34, 12480-12492.", "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": "", "extra_scores": {}}, {"review_id": "pUUhaW3Xbz", "reviewer": "Reviewer_vg5F", "summary": "This work targets the problem of differentially private image synthesis. Unlike prior related works that need full model access in the training, this work chooses to utilize large foundation models, with only the access to APIs (without knowing model weights or even without the need of training).  The PE algorithm is inspired by the evolutionary algorithm, which essentially iteratively refines the generation result so that the generation is close to the private set. The FID and some downstream tasks show its effectiveness.", "questions": "1. I find it hard and a bit confusing to track the pretrained model information in the paper. The term \"pretrained model\" and \"API\" seem to be interchangeably used, but you have two APIs. For example, in App. I, you mentioned only one pretrained model, is that your random_API? In  API implementation, you mention both APIs, and the variation_API is SDEdit. Is it also pretrained on ImageNet?\n2. It makes no sense to compare the performance at different $(\\epsilon, \\delta)$-DP, such as the comparison in Sec 5.1.2. Why not targeting the same DP guarantee?\n3. In App. H - \"Conditional pre-trained networks/APIs\", it says that \"In the subsequent VARIATION API calls (Line 6), for each image, we will use its associated class label or text prompt as the condition information to the API, and the output samples from VARIATION API will be associated with the same class label or text prompt as the input sample.\" Do you use this strategy in Sec 5.1.2 experiment? If so, how did the label of ImageNet guide the generation of Camelyn17?\n4. Fig. 19(a) is the output of random_API (iteration=0), but some images look weirdly pink-ish, e.g. col 1 row 7, col 7 row 6, col 8 row 10, while the rest looks gray-ish. This is weird if the random_API is well pretrained. Do the authors have any interpretations?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. Large foundation models have attracted unprecedented attention in recent years. The authors give an example of how to apply the foundation APIs to a real problem.\n2. The experimental results look good.\n3. The writing is generally easy to follow.", "weaknesses": "1. This method is not generic, which only applies to powerful generative AI. If the foundation model is not good enough, I highly doubt the quality of the generation.\n2. Though the result looks nice, I am so unconvinced it is true. A generative model basically learns the training distribution, so that it can generate something similar to the training set. However, if the training distribution is different from what you want to generate, how is it possible? Sec 5.1.1 looks reasonable, because the distribution of CIFAR10 has a large overlap with (or maybe is even covered by) ImageNet. However, CAMELYON17 is totally different from ImageNet, why is a diffusion pretrained on ImageNet able to generate CAMELYON17 images? The authors did not give any formal or intuitive explanations on this point.\n3. Based on the second concern, it would be more clear and intuitive to highlight samples that are used to update the histogram in each iteration. For example, in Figure 19, iteration=0, what generative samples (I believe not all of them) are closer to the private set and thereby used to update the histogram? \n4. By reading Alg. 2, it looks to me that it is possible that the histogram will be more and more concentrated on some samples when the overlap between the generation set and the private set is small, thus implying that the variation of the generation can be low.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)