Differentially Private Synthetic Data via Foundation Model APIs 1: Images

Thank you so much for the great suggestions and comments! Please see the answers to all your questions below.

Q1: 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.

A1: We respectfully disagree with this assessment.

Firstly, we want to clarify that, in our main experiments (CIFAR10 and Camelyon17), we used a relatively old diffusion model (Nichol & Dhariwal, 2021), which is far from the current state-of-the-art. Secondly, we carefully designed the experiments so that PE uses similar pre-trained models to the ones used in the SOTA DP-fine-tuning method (Ghalebikesabi et al., 2023) for fair experimental comparisons. In particular, their numbers of parameters are similar, and they are pre-trained on the same dataset (ImageNet) (see Section 5.1). Therefore, we do not think that there is evidence suggesting that PE needs more powerful pre-trained foundation models than DP-fine-tuning approaches.

Moreover, as the foundation models are quickly evolving and the most powerful ones are mostly closed-source, API-based methods could potentially be more applicable in the future.

Q2: 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.

A2: Even though the diffusion model is trained on natural images, the support of the generated distribution could be very large due to the formulation and the large latent space (same size as images). More concretely, let’s look at two examples: score-based models (https://arxiv.org/abs/1907.05600, closely related to diffusion models) and the diffusion model we used (Nichol & Dhariwal, 2021). For score-based models, its modeling target is a 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 a 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-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 a 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 have provided how the generated images evolve from natural images to Camelyon17 dataset in Figure 19 in the original submission (Figure 23 in the revision) and the selected/filtered samples by PE in Figure 26 in the revision. At every iteration, PE selects the set of images that are most similar to the Camelyon17 dataset (Figure 26 in the revision). Those images might still appear different from Camelyon17 in early iterations. However, as long as we get images that are more similar to Camelyon17 through VARIATION_API at every iteration, we will make progress, and finally, we can get images similar to Camelyon17 (Figure 17 in the original submission or Figure 21 in the revision).

We added brief explanations in Section 5.1.2, and an expanded version in Appendix J in the revision. We also want to note that (1) we have provided theoretical justification of why PE works in Section D in the original submission, and (2) we have provided the source code for reproducing the experiments in the supplementary material.

Dear Reviewer vg5F,

Thank you again for your valuable time in reviewing our paper! Have we adequately addressed all your concerns? According to your suggestions, we visualized the images with the highest and the lowest counts in the DP NN Histogram, the distribution of the counts in DP NN Histogram, and added PE results with epsilon=10 on the Camelyon17 dataset. We also addressed your other concerns in the rebuttal and the revision.

If you have any further questions, please kindly inform us, and we will be happy to elaborate further before the Nov. 22 deadline.

Thank you!

The authors

Thank the authors for all the effort in additional experiments! The newly added figure 26 is very useful.

As a summary:

The technical novelty for achieving DP (adding noise to histogram) is limited by prior works, but I do acknowledge that the authors have done a smart application of foundation API in DP image synthesis.

Moreover, I still remain suspicious about the generation if there is great distribution shift between pretrained public dataset and private dataset. Figure 26 can possibly explain the success of generation on Camelyn17, i.e. the pretrained ImageNet contains a class honeycomb, which happens to look similar to the texture in Camelyn17 images, and the later iterations simply generate increasingly more pink-ish honeycombs, which moves closer to the samples in Camelyn17.

Plus, by saying that "this method only applies to powerful generative AI", I mean a well-pretrained model on a largely spanned public dataset. If your pretrained dataset is not diverse enough, this method is not going to work.

I will keep my score, because my original score would be 4 but there is no such option. Thanks again for authors' effort in addressing my questions.

Dear Reviewer vg5F,

We very much thank the reviewer for reading our rebuttal and sharing your thoughts! These discussions are very helpful for the paper. We understand that the reviewer has marked it as a “final response”. But we would like to post our response here in case the reviewer expect one.

• Novelty about “adding noise”. It was shown that any non-constant deterministic algorithm cannot be DP [1], so any DP algorithm has to introduce randomness. Adding noise, proposed back in 2006 [2], is used in many popular DP frameworks such as DP-SGD, PATE, etc. Therefore, we respectively disagree that "our technical novelty diminishes because we add noise". The key novelty/difference between these different algorithms is where they add noise. As we explained to Reviewer eX7J, we add noise to the Nearest Neighbor Histogram, which is new in this work.

  We also want to thank the reviewer for acknowledging that “the authors have done a smart application of foundation API in DP image synthesis”.

• Requiring a well-pretrained model on a largely spanned public dataset. Thank you for clarifying the question. We agree with the reviewer that a more diverse pretrained dataset is beneficial for PE. We illustrated this intuition in Figure 2 (left). This requirement accords with the current trend in foundation models, which are trained on larger and larger datasets. Please see the post “ To AC, Reviewers, and Public Readers” for more discussions about this point.

• How PE works in Camelyon17. Firstly, we would like to thank the reviewer for pointing out honeycomb class in ImageNet, which is very helpful in providing more insights about this experiment. According to the suggestion, we checked our results again. We found that the existence of this class is indeed helpful, but PE does more than just picking this class.

  • Finding 1: The ImageNet labels of generated samples contain other further-away categories. The ImageNet 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), “bubble” (142), “stole” (72). 54.4% images are indeed with label “honeycomb”, but others are from further away classes.
  • Finding 2: Simply picking images from honeycomb yields bad fidelity. We compute the FID between honeycomb images and CIFAR10. The FID score is 162.86, which is much higher than the FID score of the final generated images we get (10.66). Indeed, although honeycomb has a similar a “net-like” pattern as Camelyon17, the details, colors, and structures are still different (see https://images.cv/dataset/honeycomb-image-classification-dataset for a quick visualization of honeycomb images). Figure 26 (a) also suggests that the initial generated diffusion models from ImageNet are still very different from Camelyon17 and the final generated samples in Figure 21.

These findings are very interesting and are deeper than what we understood, and they add a lot value to the paper (thanks to the reviewer). We added the above findings to Appendix J. But we do not see contradictions between these findings and the messages we conveyed in the paper—if the reviewers notice any contradiction, please let us know and we are happy to modify them. Note that this Camelyon17 experiment follows the same experiment setting as the SOTA DP-fine-tuning work (Ghalebikesabi et al., 2023), i.e., both methods use the same pre-training data (ImageNet) and private data (Camelyon17) so they encounter the same challenge (large distribution shift) and the same advantage (the existence of honeycomb). Here, the wording “significant distribution shift” comes from Ghalebikesabi et al. (2023), and we just follow their terminology when describing this experiment (which refers to the large distance between the distributions of the pre-training data and private data).

Thank the reviewer again for this great insight!! Feel free to ping us with any more questions. If we have addressed your final questions satisfactorily, please consider raising the score.

[1] See page 16 of: Dwork, C. and Roth, A., 2014. The algorithmic foundations of differential privacy. Foundations and Trends® in Theoretical Computer Science, 9(3–4), pp.211-407.

[2] Dwork, Cynthia, 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-284. Springer Berlin Heidelberg, 2006.

Thank you so much for the great suggestions and comments! Please see the answers to all your questions below.

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

A1.1: We want to clarify that our privacy analysis already takes the adaptive queries into account. The related discussions are in Step 3 and Step 4 of the privacy analysis in Section 4.3. It is well known that differential privacy satisfies the adaptive composition theorem (see [1]), i.e., if $M_1$ and $M_2$ are two DP algorithms, then first running $M_1$ on database $D$ to get $M_1(D)$ and then running $M_2$ on $D$ as well as the output of $M_1$, i.e., $M_2(D,M_1(D))$ is still differentially private. (Here we need that $M_2(D,z)$ is DP for all values of z, which is true in our case.) This is how we can care of any correlations that arise.

In particular, in Step 3, we mention that PE can be regarded as $T$ (adaptive) compositions of the Gaussian mechanism. Then, in Step 4, we use the property that such composition can be regarded as one Gaussian mechanism with noise multiplier $\sigma/\sqrt{T}$. It is a standard result from Dong et al. (2022) (see Corollary 3.3 therein).

Please let us know if it is unclear, and we are happy to clarify further!

[1] Dwork, Cynthia, and Aaron Roth. "The algorithmic foundations of differential privacy." Foundations and Trends® in Theoretical Computer Science 9.3–4 (2014): 211-407.

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

A1.2: We want to clarify that releasing all the (intermediate) generated sets $S_1,\dots,S_T$ also satisfies the same DP guarantees as the final generated dataset. Note that the API only sees $S_1,\dots,S_T$ during the interaction. Therefore, even if the API memorizes all the previous queries and feeds them back at later PE iterations, it does not violate the DP guarantee. We discussed this point in Section 4.3; please let us know if you have further questions.

(Please see the last block for Q2)

Dear Reviewer wkXZ,

Thank you again for your valuable time in reviewing our paper! Have we adequately addressed all your concerns? According to your suggestions, we added the results of PE on text, and PE results with epsilon=10 on the Camelyon17 dataset. We also addressed your other concerns in the rebuttal and the revision.

If you have any further questions, please kindly inform us, and we will be happy to elaborate further before the Nov. 22 deadline.

Thank you!

The authors

Thank you so much for the great suggestions and comments! Please see the answers to all your questions below.

Q1: Can you discuss the effect of the size of the private dataset on the performance of the proposed method?

A1: In our experiments, the number of private samples varies widely, ranging from 100 (for the cat dataset) to 50,000 (for CIFAR10) and 302,436 (for Camelyon17). We observe that PE works reasonably well across all these cases.

Compared to the number of private samples ($N_{priv}$), the ratio between the number of generated samples ($N_{syn}$) and the number of private samples, i.e., $N_{syn}/N_{priv}$, is more important for the performance of PE. Note that $N_{priv}$ determines the total of the votes from the private samples in the DP NN histogram (Line 2-4 in Algorithm 2), and Gaussian noise is added to all positions in the DP NN histogram of size $N_{syn}$ (Line 5 in Algorithm 2). Therefore, if $N_{syn}/N_{priv}$ is too large, the true votes in the DP NN histogram will be destroyed by the Gaussian noise. In all our experiments, we set $N_{syn}/N_{priv}=1$ and it works well empirically across all datasets. Note that it does not mean that PE can only generate as many samples as the private dataset; as we illustrated in Sections 4.2 and 5.1.3, PE can generate unlimited (useful) samples in CIFAR10 by calling VARIATION_API on these N_{syn} samples.

Q2: 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?

A2: The SOTA DP classifier pre-trained on ImageNet (without DP) and fine-tuned on CIFAR10 (with DP) [1] achieves 94.8% and 95.4% accuracies with epsilon=1 and 2 respectively. It is not surprising that DP classifiers outperform PE (and other DP synthetic data approaches as well) on classification tasks, as DP classifiers are targeted at and optimized for a single task whereas DP synthetic data is general-purpose. See similar discussions in Section 5.2 of the SOTA DP Diffusion work (Ghalebikesabi et al., 2023).

We added the numbers and discussions in Section 5.1.1 of the revision.

[1] De, Soham, et al. "Unlocking high-accuracy differentially private image classification through scale." arXiv preprint arXiv:2204.13650 (2022).

Q4: 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.

A4: It is a great point! Your understanding is correct. We added the following discussions to Section 7 of the revision.

As PE does not provide DP guarantees for the pre-training data of the foundation models, one should be careful that data considered private is not used in pre-training. Depending on whether the APIs are from black box 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 black box models. Since most black box models do not reveal their training dataset, it is safer to only consider private data that was never been shared or posted online. This includes scenarios where hospitals generate synthetic medical images using their proprietary patient records.
• 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. In all experiments of the paper, we use local models including Improved Diffusion and Stable Diffusion. We directly take the pre-trained models from prior work, and we make sure that the private data and the pre-training data have no overlap.

Q5: 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.

A5: In Appendix O of the original submission and the revision, we provide experimental results showing that the computational cost of PE can be smaller than training-based methods under the same setting (e.g., using the same pre-trained model, generating the same number of generated samples). This means that if practitioners want to run the APIs locally (i.e., downloading the foundation models and running the APIs locally without using public API providers), PE provides computational benefits.

Q6: 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.

A6: Thanks for the great point. We agree that decentralized settings are more challenging to solve. In Section 6 of the original submission, we list it as one future work: “Solving DPSDA in the Local/Shuffle DP model and in federated learning settings.” We believe it is interesting to study how to extend PE to federated learning settings, In fact, PE is quite amenable to adapting to decentralized settings. Suppose each client/user has one private sample for simplicity. If we share the current iteration of generated samples with each user (these are differentially private anyway), then the user can vote for the nearest sample. These votes can be aggregated by a central server either by employing Differentially Private Frequency Estimation under Local Differential Privacy (such as in [1]) or by using frequency estimation under the shuffle-DP model which further amplifies the privacy guarantees as shown in [2].

[1] Private Frequency Estimation via Projective Geometry. Feldman et al. ICML 2022.

[2] Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling. Feldman et al. FOCS 2021.

Dear Reviewer yzwb,

Thank you again for your valuable time in reviewing our paper! Have we adequately addressed all your concerns? According to your suggestions, we added the results of PE on text, and the results of the DP fine-tuning baseline. We also addressed your other concerns in the rebuttal and the revision.

If you have any further questions, please kindly inform us, and we will be happy to elaborate further before the Nov. 22 deadline.

Thank you!

The authors

Q4: Firstly, please allow us to deviate a bit and clarify what we meant by “APIs”. When saying “APIs”, we do not exclusively refer to APIs of the black box models (e.g., DALLE2), but also include the APIs of local models. For example, Stable Diffusion is a local model, but it provides a bunch of APIs that users can directly use https://huggingface.co/docs/diffusers/api/pipelines/stable_diffusion/overview. PE applied on these local APIs also provides the benefit that users do not need to train a model.

Now, we go back to the question. We agree with the reviewer that we should clarify earlier in the paper that we only experimented with APIs of local models instead of public APIs. We added a clarification in the introduction and fixed relevant statements that may create confusion.

We also want to clarify the point “you did not provide a strong application/example where using APIs do not violate your privacy guarantees”. Does the reviewer refer to the “privacy guarantees” about the pre-training data of the foundation model, or the private data used to run the PE algorithm? If it is the latter, we want to clarify that, for the private data used to run the PE algorithm, we provide DP guarantees even from the API provider. See Section 4.3 and A1.2 to Reviewer wkXZ for the discussions.

Q1: When setting $N_{syn}/N_{priv}=1$, a smaller number of private samples $N_{priv}$ would mean that the number of generated samples from PE $N_{syn}$ is also smaller. These $N_{syn}$ samples could be of high quality, but there are fewer of them. That being said, the performance of PE is NOT independent of the number of samples. To generate more samples, we would then need to rely on the approach in Section 4.2, where we pass the samples through VARIATION_API to ”augment” these $N_{syn}$ samples (See Section 5.1.3 for the results).

We agree with the reviewer that it would be interesting to see how the results of PE change with respect to different numbers of private samples $N_{priv}$ of the same dataset. We launched the experiments and will update the results here once they are done. In the meantime, if the reviewer has other concerns and/or suggestions about this question/experiment, please let us know!

Dear Reviewer yzwb,

Have we addressed your final questions sufficiently? The discussion phase ends in 3.5 hours. If we have addressed your concerns satisfactorily, please consider raising the score.

Thank you again for your valuable time and suggestions!

The Authors

Thank you so much for the great suggestions and comments! Please see the answers to all your questions below.

Q1: 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.

A1: We agree with the reviewer that “adding DP noise to the histogram” is an existing idea. But we also want to mention that it is only one step among the other components we proposed, and the way we construct the histogram (using private samples to vote for the nearest generated samples) is different from the usual application of this idea (e.g., DP density estimation where the histogram is constructed by binning the private samples). Overall, our contributions are not on “adding DP noise to the histogram”, but on the following aspects:

• New problem: We highlight the importance of studying DP Synthetic Data via foundation model APIs.
• New framework: We propose Private Evolution, a new framework for generating DP synthetic data, that only requires APIs of the foundation models and does not need any model training.
• Promising results: Private Evolution can even outperform the SOTA DP-fine-tuning-based approaches on the privacy-utility trade-off in the CIFAR10 experiments.

Q2: 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.

A2: Following your suggestion, we conducted a new experiment showing how PE performs under different levels of distribution shifts. To do that, we take the Camelyon17 dataset and modify the saturation of the images to create a sequence of datasets, each with a different saturation change. This way, we create a sequence of datasets with different levels of distribution shifts from ImageNet. We decided to use this methodology because it is: (1) more controllable, as we can use saturation change to control the level of the distribution shifts, (2) more comparable, as these datasets are derived from the same base dataset, and (3) comprehensive, as we can show the performance under multiple levels of distribution shifts.

The results are shown in Figure 30 in the revision. We can see that among all levels of distribution shifts we test here, the FID scores decrease with more PE iterations. This means that PE is effective in pushing the generated distribution towards private data. At the time we post the rebuttal, the FID scores are still decreasing and have not converged yet; we will keep updating this figure as the experiment continues.

However, as we discussed in Section 5.1.2 and Section 6, larger distribution shifts do make the convergence slower and the results tend to be worse compared to the DP fine-tuning approaches. One possible improvement is to consider better variation degree ($v$ in Section 3.3) choices. Currently, we use a single variation degree in each step. As the theoretical analysis in Section D suggested, using multiple variation degrees (so that the variations can cover the entire space no matter whether the distribution shift is large or small) benefits convergence. It would be interesting to explore this direction in future work.

Dear Reviewer eX7J,

Thank you again for your valuable time in reviewing our paper! Have we adequately addressed all your concerns? According to your suggestions, we added the experiments of PE with various distribution shifts, and distribution plots of the nearest neighbor distances. We also addressed your other concerns in the rebuttal and the revision.

If you have any further questions, please kindly inform us, and we will be happy to elaborate further before the Nov. 22 deadline.

Thank you!

The authors

Dear Reviewer eX7J,

Have we addressed your concerns sufficiently? We have not heard back from you since we posted the rebuttal 4 days ago, and the discussion phase ends in 5 hours. If we have addressed your concerns, please consider raising the score.

Thank you again for your valuable time and suggestions!

The Authors