DP-MERF: Differentially Private Mean Embeddings with RandomFeatures for Practical Privacy-preserving Data Generation

Frederik Harder, Kamil Adamczewski, Mijung Park

Abstract

We propose a differentially private data generation paradigm using random feature representations of kernel mean embeddings when comparing the distribution of true data with that of synthetic data. We exploit the random feature representations for two important benefits. First, we require a minimal privacy cost for training deep generative models. This is because unlike kernel-based distance metrics that require computing the kernel matrix on all pairs of true and synthetic data points, we can detach the data-dependent term from the term solely dependent on synthetic data. Hence, we need to perturb the data-dependent term once and for all and then use it repeatedly during the generator training. Second, we can obtain an analytic sensitivity of the kernel mean embedding as the random features are norm bounded by construction. This removes the necessity of hyper-parameter search for a clipping norm to handle the unknown sensitivity of a generator network. We provide several variants of our algorithm, differentially-private mean embeddings with random features (DP-MERF) to jointly generate labels and input features for datasets such as heterogeneous tabular data and image data. Our algorithm achieves drastically better privacy-utility trade-offs than existing methods when tested on several datasets.

Introduction

Sharing sensitive datasets, such as medical records or financial transactions, is often restricted by privacy regulations. Differentially Private (DP) data generation offers a solution by creating synthetic versions of data that maintain statistical properties without compromising individual privacy.

Currently, the standard approach involves training Generative Adversarial Networks (GANs) using DP-SGD. However, DP-GANs face three significant challenges:

  1. Privacy Budget Depletion: Every training iteration that accesses real data consumes the privacy budget ($\epsilon$), limiting training duration.
  2. Hyperparameter Sensitivity: DP-SGD requires gradient clipping to bound sensitivity, but finding the optimal clipping norm is a difficult heuristic process that often destabilizes training.
  3. Training Instability: The adversarial min-max game in GANs is inherently unstable; adding DP noise frequently leads to non-convergence or mode collapse.

Methodology: The DP-MERF Approach

We introduce DP-MERF (Differentially Private Mean Embeddings with Random Features). Instead of an adversarial discriminator, we utilize the Maximum Mean Discrepancy (MMD) framework to compare distributions via their mean embeddings in a high-dimensional feature space.

Our method relies on two core innovations:

  • Random Fourier Features (RFF): RFFs provide a linear-time approximation of MMD. Crucially, they allow us to decouple the MMD objective into a term dependent only on real data and a term dependent only on synthetic data.
  • One-Shot Privatization: Because the terms are separated, we calculate the mean embedding of the real data exactly once, add Gaussian noise to it, and then discard the real data. The generator is subsequently trained to match this privatized target. This means the privacy cost is independent of the number of training iterations.

Furthermore, because RFFs are norm-bounded by construction, the sensitivity of the mean embedding is known analytically. This eliminates the need for the heuristic "clipping norm" search required by traditional DP-GANs.

Experimental Evaluation and Results

We evaluated DP-MERF across diverse data types, including synthetic 2D Gaussian mixtures, eight real-world tabular datasets (e.g., Adult, Census, Credit), and image benchmarks (MNIST, FashionMNIST).

Key Insights

  • Superior Utility at Low $\epsilon$: On MNIST, DP-MERF achieved 61% accuracy on downstream tasks at a strict $\epsilon=0.2$. In contrast, DP-GANs required a much weaker $\epsilon=9.6$ to reach only 48-50% accuracy.
  • Mode Preservation: DP-MERF excels at capturing the full distribution of data. In Gaussian mixture experiments, DP-CGAN variants began dropping clusters as privacy constraints tightened, while DP-MERF successfully captured all clusters even at $\epsilon=1$.
Visual comparison of mode preservation: DP-MERF maintains all 25 clusters at $\epsilon=1$, while DP-CGAN fails even at higher $\epsilon$ values.
  • Tabular Performance: Across tabular datasets, DP-MERF consistently achieved the highest ROC and F1 scores among private models, frequently approaching non-private performance levels.

Conclusion

DP-MERF provides a streamlined and stable alternative for privacy-preserving data generation. By decoupling privacy loss from training iterations and providing analytic sensitivity, it avoids the common pitfalls of DP-GANs. While future work remains in scaling to high-resolution images and refining variance estimation, DP-MERF represents a significant step forward in practical, high-utility private data synthesis.

Summary updated

Abstract

We propose a differentially private data generation paradigm using random feature representations of kernel mean embeddings when comparing the distribution of true data with that of synthetic data. We exploit the random feature representations for two important benefits. First, we require a minimal privacy cost for training deep generative models. This is because unlike kernel-based distance metrics that require computing the kernel matrix on all pairs of true and synthetic data points, we can detach the data-dependent term from the term solely dependent on synthetic data. Hence, we need to perturb the data-dependent term once and for all and then use it repeatedly during the generator training. Second, we can obtain an analytic sensitivity of the kernel mean embedding as the random features are norm bounded by construction. This removes the necessity of hyper-parameter search for a clipping norm to handle the unknown sensitivity of a generator network. We provide several variants of our algorithm, differentially-private mean embeddings with random features (DP-MERF) to jointly generate labels and input features for datasets such as heterogeneous tabular data and image data. Our algorithm achieves drastically better privacy-utility trade-offs than existing methods when tested on several datasets.
BibTeX
@inproceedings{harder2021dp,
  author = {Frederik Harder and Kamil Adamczewski and Mijung Park},
  title = {{DP-MERF: Differentially Private Mean Embeddings with RandomFeatures for Practical Privacy-preserving Data Generation}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2021},
  url = {https://openreview.net/forum?id=9FR3uiotbn},
}
Figure