PaperlayerView exact revision on arXiv

Source-linked AI summary

DP-MERF: Differentially Private Mean Embeddings with Random Features for Practical Privacy-Preserving Data Generation

Frederik Harder, Kamil Adamczewski, Mijung Park

arXiv:2002.11603v5cs.LGstat.ML

TL;DR

Repeated access to sensitive data consumes privacy budget, motivating synthetic data that can be reused. DP-MERF privatizes a random-feature kernel mean embedding once and uses it to train a generator; the authors report quality samples with lower privacy budgets than GAN-based approaches across synthetic, tabular, and image datasets.

  • Problem

    Repeated access to sensitive data reduces the privacy guarantee, motivating synthetic datasets that can be reused without further privacy loss.

    Source: §1 · p. 1

  • Method

    DP-MERF uses random-feature kernel mean embeddings to separate the data-dependent term for one-time privatization from the synthetic-data term used in generator training.

    Source: §1 · p. 2

  • Results

    Across a synthetic dataset, eight tabular datasets, and two image datasets, DP-MERF produces quality samples with significantly lower privacy budgets than GAN-based approaches.

    Source: §7 · p. 9

  • Takeaways & Limitations

    Although evaluated with supervised-learning metrics, the authors state that DP-MERF is not limited to that application.

    Source: §7 · p. 9

    A low NLL score does not establish mode coverage and may also result from low sample variance.

    Source: §6 · p. 7

Abstract

from arXiv · show

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 only once 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.

1 Introduction

Repeated access to sensitive data consumes privacy budget, while query-specific synthetic data can limit flexibility. DP-MERF uses random-feature kernel mean embeddings to separate the data-dependent term for one-time privatization, then optimizes a generator using the private release.

1 Introduction

  • Random-feature kernel mean embeddings provide the MMD-based objective, separating the true-data embedding from the synthetic-data embedding.Only the data-dependent term requires privatization; the released private embedding can be reused while training the generator.Source: §1 · p. 2
  • Because the training objective uses a specific private data release, the method avoids privacy-induced limits on model choice and optimization and avoids GAN min-max training.The authors contrast this with DP-SGD constraints, including its requirement for well-defined sample-wise gradients.Source: §1 · p. 2
  • Norm-bounded random features give the mean embedding analytically tractable sensitivity, enabling a single low-sensitivity private release.The passage states that feature norms are bounded by 1 and sensitivity is on the order of 1 over the number of training points.Source: §1 · p. 2
  • At (0.2, 10−5)-DP, DP-MERF outperforms all GAN-based comparison methods trained with privacy guarantees of at most (9.6, 10−5)-DP.The introduction also describes the method as improving existing methods in privacy and utility.Source: §1 · p. 2
  • The theoretical error bound quantifies privacy-noise effects on the random-feature MMD objective and informs feature-dimension selection for a dataset size and privacy level.The method's stated hyperparameters are the number of random features, a kernel parameter, and the learning rate.Source: §1 · p. 2
  • DP-MERF jointly generates privacy-sensitive inputs and outputs and is designed for imbalanced, heterogeneous tabular data.The authors contrast joint generation with conditional-GAN methods that treat class distributions as non-sensitive.Source: §1 · p. 2

2 Background

The background introduces MMD as a distribution-comparison measure, random features as a computational approximation, and differential privacy as a guarantee for releasing information derived from sensitive data. These concepts motivate the DP-MERF setup.

2.1 Maximum Mean Discrepancy

  • MMD measures the distance between distributions' mean embeddings and, for characteristic kernels, is zero if and only if the distributions are equal.The conventional pairwise estimator has O(mn) computational cost, which is prohibitive for large datasets.Source: §2.1 · p. 3

2.2 Random feature mean embeddings

  • Finite-dimensional random features approximate the kernel inner product and reduce MMD-estimator computation to O(m + n).Random Fourier features apply to translation-invariant kernels.Source: §2.2 · p. 3
  • The particular random-feature MMD estimator described here is biased.The background also presents random Fourier features as a kernel approximation built from sampled frequencies.Source: §2.2 · p. 3

2.3 Differential privacy

  • The Gaussian mechanism perturbs a sensitive-data function according to its global sensitivity, and post-processing a private release does not weaken its guarantee.The text introduces DP-MERF as the forthcoming privacy-preserving data-generation algorithm.Source: §2.3 · p. 3

2 Background

  • Differential privacy bounds information revealed about an individual, while composability accounts for privacy degradation across repeated mechanisms and post-processing preserves the guarantee for data-independent mappings.The Gaussian mechanism adds noise calibrated to a function's global sensitivity.Source: §2.3 · p. 3

3 Vanilla DP-MERF for unlabeled data

Vanilla DP-MERF trains an unlabeled-data generator by minimizing a random-feature approximation to MMD, privatizing only the true-data mean embedding. The accompanying bound characterizes objective error from privacy noise and random-feature approximation, guiding the choice of feature dimension.

3 Vanilla DP-MERF for unlabeled data

  • DP-MERF minimizes random-feature MMD between true and generated distributions, privatizing the true-data embedding while leaving the synthetic-data embedding data-independent.The Gaussian mechanism releases the true-data embedding; post-processing then allows generator training without further direct access to data.Source: §3 · pp. 3–4

3.1 Bound on the expected absolute error

  • The expected absolute error bound covers both privacy noise and random-feature randomness, rather than directly quantifying noise’s effect on the learned generator.The paper notes that the effect on an arbitrary neural-network generator is challenging to quantify, so it bounds objective error instead.Source: §3.1 · p. 4
  • Increasing the feature dimension reduces MMD-approximation error but increases the privacy-noise term, creating a trade-off in the bound.The paper reports that for its relatively large datasets, D ≈ 10,000 yields relatively small error even at small ϵ.Source: §3.1 · p. 4
  • The bound guides dimension choice: when m > D, error remains relatively small, while too-small D can increase random-feature approximation error.The guidance depends on the dataset size m and desired privacy level ϵ.Source: §3.1 · p. 4

4 Extension of the vanilla DP-MERF

The paper extends DP-MERF from unlabeled data to labeled, imbalanced, and heterogeneous data. These variants adapt the embedding or kernel to represent labels, class imbalance, and mixed numerical-categorical inputs.

4 Extension of the vanilla DP-MERF

  • The extensions address labeled, class-imbalanced, and heterogeneous data beyond the vanilla unlabeled-data setting.The variants adapt the DP-MERF objective and embeddings to these data settings.Source: §4 · p. 4

4.1 DP-MERF for labeled data

  • For labeled data, a product kernel combines input-feature and one-hot-label kernels, yielding a joint input-label embedding with sensitivity 2/m.The input kernel is Gaussian and the label kernel is order-1 polynomial; the resulting kernel is described as characteristic.Source: §4.1 · pp. 4–5

4.2 DP-MERF for imbalanced data

  • For imbalanced data, DP-MERF releases class counts and reweights class-wise embeddings so infrequent classes contribute equally to the objective.The two releases—the mean embedding and class counts—compose to determine total privacy loss; generated labels are sampled proportional to released class sizes.Source: §4.2 · p. 5

4.3 DP-MERF for heterogeneous data

  • For heterogeneous inputs, the method sums numerical and categorical kernels, normalizing the categorical kernel to match their importance in the embeddings.The passage states that this sum-kernel construction does not implicitly assume independence between the two variable types.Source: §4.3 · p. 5
  • At ϵ = 1, DP-MERF captures all modes in the Gaussian-mixture example, whereas DP-CGAN drops some modes.The figure caption says the difference is also reflected in negative log likelihood.Source: Figure 1 · p. 6

5 Related work

Related work includes query-based private data release, query-independent methods focused on discrete data, and private GANs. The paper positions DP-MERF as a general data-release approach that also uses random-feature mean embeddings for generative modeling.

Differentially private data release

  • Learning-theory approaches to differentially private data release provide utility bounds, but rely on strong assumptions about executed-query types or intractable computation, making this line of research less relevant to their approach.Source: §5 · p. 6
  • Many query-independent methods focus on discrete or discretizable data, using selected marginals; the paper compares with only in supplementary material.Such methods featured among winners of the NIST 2018 challenge, which focused on discrete datasets.Source: §5 · p. 6

GAN-based private data release

  • Private GAN comparisons address general data release, but several methods either generate unlabeled data or condition on labels without learning their distribution.DP-GAN [35] and PATE-GAN generate unlabeled data; DP-CGAN [30] and GS-WGAN [5] condition on labels.Source: §5 · p. 6

Random feature kernel methods with differential privacy

  • Prior random-feature mean-embedding work applied differential privacy to data sharing or distributed summarization, not generative modeling.The passage says the reduced-set method [4] performs poorly as data dimension grows; [24] addresses covariate shifts in distributed summarization.Source: §5 · p. 6

6 Experiments

Experiments compare private synthetic data across a Gaussian-mixture task, tabular datasets, and image datasets using distributional or downstream predictive measures. The reported results favor DP-MERF in downstream performance, including under strong privacy settings.

2D Gaussian mixtures

  • For the reported NLL measure, a low score does not establish mode coverage and can also result from low sample variance.A high NLL indicates that many samples lie in low-density regions; underfitting can make lower NLL preferable.Source: §6 · p. 7
  • On the Gaussian-mixture task, DP-MERF preserves all modes and places few samples in low-density regions, while its low NLL may reflect underestimated variance.The comparison reports that DP-CGAN loses modes as privacy increases.Source: §6 · p. 7

Real world data evaluation

  • Real-world evaluation trains predictive models on private synthetic data and tests them on real data, but comparison scores are not directly comparable because some reference hyperparameters were unavailable.Scores are averages over five independent runs; tabular metrics include ROC or PRC for binary labels and accuracy or F1 for multiclass labels, depending on balance.Source: §6 · pp. 7–8

Image data

  • At ϵ = 0.2, DP-MERF significantly outperforms other methods on image test accuracy, and it maintains good performance at (1, 10−5)-DP and (0.2, 10−5)-DP.The comparison methods use privacy levels reported in their papers because they did not produce usable samples at ϵ ≤1.Source: Table 3 · p. 8, §6 · p. 8

Tabular data

  • DP-MERF achieves higher evaluation metrics than comparison methods at the same privacy level across tabular datasets, with the table reporting the best private-model scores on most datasets.Tabular scores average 12 predictive models across five runs.Source: Table 1 · p. 7, §6 · p. 8

Image data

  • In image comparisons, DP-MERF samples at ϵ = 0.2 look noisier than GS-WGAN and DP-CGAN samples but achieve higher downstream accuracy.The authors suggest distinctive data features remain preserved despite the noisy appearance.Source: §6 · p. 8, Figure 2 · p. 8

7 Summary and Discussion

DP-MERF is presented as a practical random-feature mean-embedding algorithm for private data generation, evaluated on synthetic, tabular, and image datasets. Its reported metrics target supervised learning, though the method is not limited to that application.

7 Summary and Discussion

  • DP-MERF produces quality samples with a significantly lower privacy budget than GAN-based approaches across a synthetic dataset, eight tabular datasets, and two image datasets.The evaluation metrics target supervised learning, but the authors state that the method is not limited to that application.Source: §7 · p. 9

Supplementary Material: Differentially Private Random Feature Mean Embeddings for

The supplement introduces random Fourier feature representations of kernel mean embeddings for differentially private data generation. It reviews distance measures used in generative modeling and derives an expected-error bound for a noisy random-feature MMD estimate.

A Background on distance measures for DP data generation

  • MMD compares probability measures through their mean embeddings, and its squared form is a metric for characteristic kernels.The passage also notes that MMD has a closed-form estimator computed using pairwise kernel evaluations.Source: A Background on distance measures for… · p. 12
  • Random Fourier feature representations of kernel mean embeddings are proposed for differentially private data generation.The background identifies MMD as a distance measure based on differences between probability measures’ mean embeddings.Source: A Background on distance measures for… · p. 12

B Derivation of the bound on the expected absolute error

  • The supplement derives a bound on expected absolute error between noisy random-feature squared MMD and squared MMD.The bound is stated for samples drawn from two probability distributions; the supplied passage does not expose its full expression.Source: B Derivation of the bound on the… · p. 13

B.1 Randomness due to random features

This supplement analyzes error from random features and privacy noise, derives sensitivity results for labeled data, and discusses kernel choices for heterogeneous variables. It also explains that the sum-kernel representation accounts for correlations while using fewer Fourier features than the product-kernel representation.

B.1 Randomness due to random features

  • The random-feature MMD has a probabilistic error bound relative to MMD, and its expectation equals MMD.The bound concerns randomness from the random features.Source: §B.1 · pp. 13–14

B.2 Randomness due to noise for privacy

  • A lemma bounds the first-moment error between privatized and non-privatized random-feature MMD proxies.The privatized proxy adds Gaussian noise to the random-feature mean embedding.Source: §B.2 · p. 14

E Sensitivity of class counts

  • For neighboring datasets, class counts can differ in at most two entries, each by at most one, when the labels differ.When the labels are the same, the class-count vectors are unchanged.Source: E Sensitivity of class counts · p. 15

F Sensitivity of ˆµP with homogeneous data

  • For homogeneous labeled data, the sensitivity argument reduces neighboring datasets to their distinct datapoints and uses the unit norm of random features.The passage states that labeled and unlabeled embeddings have the same sensitivity.Source: F Sensitivity of ˆµP with homogeneous… · p. 15

G Sensitivity of µP with heterogeneous data

  • For heterogeneous data, the sensitivity analysis treats numerical and categorical components separately, using unit-norm random features and binary categorical inputs.The supplied passages do not provide a complete sensitivity expression.Source: G Sensitivity of µP with heterogeneous… · p. 16

I Variables in heterogeneous data are not treated as independent

  • The sum-kernel embedding accounts implicitly for correlations between variable types and uses dx + dy Fourier features, versus dx · dy for a product kernel.The sum-kernel embedding concatenates the two component embeddings; the authors choose it for computational tractability.Source: I Variables in heterogeneous data are… · p. 16

K.2 Detailed results for binary class dataset

The supplement points to detailed binary-class dataset comparisons and describes the image datasets used in the experiments. The supplied table captions identify the comparison scope and reporting format, but do not provide score values.

K.2 Detailed results for binary class dataset

  • The detailed binary-class results include highest-in-five-run and average-performance comparisons for Credit and Intrusion.The captions identify Credit tables 5–6 and Intrusion tables 7–8; the passage specifies average F1-score reporting for Intrusion.Source: §K.2 · p. 18, Table 5 · p. 18, Table 6 · p. 19
  • The Credit tables report performance comparisons, with one caption specifying the highest performance across five runs and another the average.The captions identify the dataset and run aggregation, but not the table’s score values.Source: Table 5 · p. 18, Table 6 · p. 19

L.1 Datasets

  • The digit and fashion MNIST datasets each contain 60,000 samples across 10 nearly balanced classes, with 28x28-pixel images.The passage describes these image datasets as substantially higher-dimensional than the tested tabular data.Source: §L.1 · p. 20

L.2 Detailed results

The detailed image results show DP-MERF outperforming other approaches across models, with two stated MNIST exceptions. A separate comparison reports decreasing embedding distance as the number of synthetic datapoints increases.

L.2 Detailed results

  • GS-WGAN performs slightly better for Gaussian Naive Bayes on MNIST, while DP-CGAN performs slightly better for XGBoost on MNIST.These are the exceptions to DP-MERF’s reported cross-model pattern.Source: §L.2 · p. 20
  • DP-MERF consistently outperforms other approaches across models on digit and fashion MNIST, except for two stated model-dataset cases.The exceptions are Gaussian Naive Bayes on MNIST, where GS-WGAN performs slightly better, and XGBoost on MNIST, where DP-CGAN performs slightly better; results average five runs.Source: Table 9 · p. 20, §L.2 · p. 20, Table 10 · p. 21

M.1 Comparison with [4].

  • As the number of synthetic datapoints increases, the method reduces the distance between the true kernel mean embedding and that of the released dataset.The comparison uses simulated data from a five-dimensional mixture of Gaussians; the passage contrasts neural-net generator training with the reduced-set approach in [4].Source: §M.1 · p. 21

M.2 Comparison with PrivBayes [38].

On Adult and Census, PrivBayes performs better at ϵ=1, the methods are roughly tied at ϵ=0.3, and DP-MERF has lower error at ϵ=0.1. The authors also describe DP-MERF as more general because it needs no discretization and scales to higher dimensionality and arbitrary domains.

M.2 Comparison with PrivBayes [38].

  • At ϵ=1 PrivBayes performs better, at ϵ=0.3 the methods are roughly tied, and at ϵ=0.1 DP-MERF has lower error.The comparison uses Adult and Census datasets and the best-performing usefulness parameter θ.Source: §M.2 · p. 21
  • Unlike PrivBayes, DP-MERF does not require discretization and scales to higher dimensionality and arbitrary domains.Source: §M.2 · p. 21
  • For binarized MNIST with d=784 features, testing PrivBayes with any k>2 is infeasible.The authors attribute this boundary to PrivBayes’s restriction to small k when dimensionality is large.Source: §M.2 · p. 22

Related papers

Loading 2002.11603v5…