PaperlayerView exact revision on arXiv

Source-linked AI summary

Differentially Private Synthetic Data via Generalized Moment Matching

Rundong Ding, Yiyun He, Yizhe Zhu

arXiv:2610.30196v2stat.MLcs.ITcs.LGmath.ITmath.PRmath.STstat.TH

TL;DR

Private synthetic data methods often target predefined workloads, while the paper seeks a general framework with utility measured by a specified IPM. It introduces generalized moment matching and reports sharp polynomial rates for several kernel and non-kernel metrics.

  • Problem

    The paper seeks a general private synthetic-data framework with utility guarantees for a specified IPM, beyond mechanisms tailored to predefined workloads.

    Source: §1 · p. 1, §1.1 · p. 2

  • Method

    Generalized moment matching privately estimates public moments, fits a probability measure, and samples equally weighted synthetic records.

    Source: §1.2 · p. 3

  • Results

    The paper reports sharp polynomial rates for Matérn MMD, sliced Wasserstein-1, and ReLU IPMs, with moment error converted into IPM error by a general theorem.

    Source: §1.2 · pp. 3–4

  • Takeaways & Limitations

    The framework unifies earlier private synthesis methods and applies beyond MMD to sliced Wasserstein-1 and norm-bounded two-layer ReLU networks.

    Source: §1.2 · p. 3

    The framework assumes moments control query error, and high-dimensional computational feasibility remains separate, with a stated Boolean-marginal impossibility under one-way functions.

    Source: §1.1 · p. 2, §1.2 · p. 4

Abstract

from arXiv · show

We study $(\varepsilon,\delta)$-differentially private synthetic data for arbitrary databases of $n$ records in $[-1,1]^d$ under a specified integral probability metric (IPM). We introduce generalized moment matching, which estimates moments privately, fits a probability measure, and samples synthetic records. A general error theorem applies when moment error controls the target IPM. This framework extends Chebyshev moment matching for $1$-Wasserstein distance and smooth queries. We apply the framework to maximum mean discrepancy with Matern and Laplace kernels and a two-layer ReLU neural tangent kernel. We also obtain guarantees for sliced Wasserstein-$1$ and the IPM induced by norm-bounded ReLU networks. With sufficiently many synthetic records,these rates are minimax optimal up to logarithmic factors for fixed dimension.

1 Introduction

The paper seeks a general framework for differentially private synthetic data whose utility is measured by a specified integral probability metric. Generalized moment matching estimates moments privately, fits a probability measure, and samples records, with applications to several kernel and non-kernel metrics.

1 Introduction

  • Synthetic data offers a complementary alternative to task-specific private mechanisms, allowing downstream analyses without additional privacy loss under postprocessing.The target is an arbitrary observed database; no sampling assumption on its records is made.Source: §1 · p. 1, §1.1 · p. 2

1.1 Private synthetic data and query accuracy

  • The framework targets a specified query class through an IPM, and the paper identifies computational feasibility as a separate challenge in high dimensions.Under the stated one-way-function assumption, rules out certain polynomial-time algorithms for preserving all two-way marginals on Boolean databases.Source: §1.1 · p. 2

Sliced Wasserstein distance

  • The framework’s applications include MMD, sliced Wasserstein-1, and the IPM induced by norm-bounded two-layer ReLU networks.For the ReLU IPM, the bound controls the expected largest change in average output across norm-bounded two-layer networks of any width.Source: §1.1 · p. 2, Sliced Wasserstein distance · p. 3
  • Sliced Wasserstein-1 bounds are relative to arbitrary input databases, have matching polynomial lower bounds, and improve the Wasserstein exponent for d ≥2.Sliced Wasserstein-1 averages one-dimensional transport costs over projections.Source: Sliced Wasserstein distance · p. 3

1.2 Generalized moment matching and main results

  • Generalized moment matching privately estimates public moments, fits a probability measure, and samples equally weighted records; its theorem converts moment error into IPM error.The framework unifies earlier private synthesis methods and the paper’s constructions.Source: §1.2 · p. 3
  • The synthesis error bound adds query-approximation, candidate-grid, private-estimation, fitting, and finite-sampling errors.The sampling term comes from drawing m records from the fitted measure.Source: §1.2 · p. 4

2 Setup and notation

The setup considers probability measures on the cube and private synthetic datasets whose empirical measures approximate the observed database. Query accuracy is expressed through a bounded class of continuous functions and its induced IPM.

2 Setup and notation

  • The domain is the cube [-1,1]^d with Euclidean distance, equipped with the Borel sigma-algebra of the weak topology.Source: §2 · p. 5
  • Databases are adjacent when one row is replaced; differential privacy bounds output-distribution changes for every adjacent pair and measurable event.When δ = 0, the guarantee is called pure differential privacy.Source: §2 · p. 6
  • The query class is nonempty, consists of bounded continuous functions, and induces the IPM used to measure accuracy.Source: §2 · p. 6
  • For a continuous positive definite kernel, MMD is the IPM over its RKHS unit ball and also measures the distance between kernel mean embeddings.A kernel is characteristic when zero MMD implies equality of the measures.Source: §2 · pp. 6–7

3 Specifications and minimax rates

This section specifies moment maps and private estimators for several IPMs, then derives upper and lower bounds for their synthetic-data error. The constructions cover kernel MMD, sliced Wasserstein-1, and ReLU-network IPMs.

3.1 Kernel feature moments

  • For Gaussian and polynomial kernels, the feature constructions keep Γ bounded and give e_tail+e_grid=O_d,K(N^-1_ε,δ), yielding the stated upper bounds.Orthogonal feature blocks allocate Gaussian noise according to block dimension and sensitivity; the Gaussian and polynomial examples also have near-minimax guarantees under stated settings.Source: §3.1 · pp. 7–8

3.2 Matérn, Laplace, and neural network kernels

  • For Matérn MMD, the privacy-error rate improves with smoothness ν until ν=d/2, then remains N^-1_ε,δ; sampling contributes m^-1/2.Wavelet moments exploit localization, and denoising reduces error in noisy fine-scale moments; the stated bounds require no density assumption.Source: §3.2 · pp. 8–10
  • Laplace and two-layer ReLU NTK MMD inherit Matérn-based bounds: Laplace uses ν=1/2, while an RKHS-norm equivalence transfers the Laplace bounds to the NTK.The NTK comparison uses its Sobolev-order equivalence on the cube.Source: §3.2 · p. 10

3.3 Sliced Wasserstein-1

  • For d ≥2, Laplace-kernel wavelet moments give sliced Wasserstein-1 upper bounds, and a separate geometric construction gives matching polynomial lower-bound rates.The comparison to Laplace MMD supplies the upper bound; the lower bound uses separated databases.Source: §3.3 · p. 11

3.4 ReLU IPMs

  • For norm-bounded two-layer ReLU IPMs, the privacy-error exponents match between upper and lower bounds in every fixed dimension under the common privacy regime.The upper-bound estimator privately approximates single-neuron averages on a public net, which controls every network in the class.Source: §3.4 · pp. 11–12

A Connection to earlier private synthesis methods

This section connects generalized moment matching to earlier private synthesis methods by expressing their constructions through moments of partition cells or Chebyshev polynomials.

Partition moments for PSMM and PMM

  • PSMM privately estimates cell probabilities with Laplace noise and fits them by linear programming; PMM uses repaired hierarchical counts, and both are pure ε-DP.For fixed database size, PMM keeps the root count at public value n and doubles the cited noise scales for replacement adjacency.Source: A Connection to earlier private… · p. 20
  • For d≥2, PSMM and PMM have e_priv=ẽ((nε)^-1/d) with partition diameter η ≍(nε)^-1/d under the cited public tuning.Theorem 1.2 is used to transfer these moment-estimation and grid choices into the stated error bound.Source: A Connection to earlier private… · p. 20

Chebyshev moments for multivariate smooth queries

  • The Chebyshev construction uses rescaled polynomial moments of degree at most J in each coordinate to handle multivariate smooth queries.Its cited query class has bounded derivatives through order k.Source: A Connection to earlier private… · p. 20

B Proofs for generalized moment matching

These proofs describe the Gaussian moment estimator and the sampling contribution when synthetic records are drawn from a private fitted measure.

B.1 Kernel means and the Gaussian mechanism

  • The Gaussian moment estimator adds covariance-shaped Gaussian noise to a public bounded moment map, with sensitivity controlled after covariance normalization.The passage states that the resulting estimator is (ε,δ)-DP and gives its error term in the Euclidean norm.Source: §B.1 · p. 21
  • Sampling m independent records from q yields an expected MMD error bound for their empirical measure.The sampling lemma uses independent draws and the feature-norm bound K(x,x)≤κ².Source: §B.1 · p. 21

B.2 General error bound and kernel features

The proof bounds IPM error by separating approximation, grid, private-estimation, fitting, and sampling contributions. It also explains projection-based fitting and finite-dimensional kernel feature choices.

B.2 General error bound and kernel features

  • The general bound controls E d_F(p_X,q) by e_tail+C(2e_priv+e_grid+e_opt), then adds the sampling term s_F(m) for the released dataset.For MMD, sampling contributes at most κ/√m; Euclidean fitting can reduce the private-error coefficient from two to one.Source: §B.2 · pp. 21–22
  • The chosen block covariance minimizes total noise variance among the stated block covariances, with equality at the specified block weights.The proof also uses the triangle inequality and the grid bound to control the fitted moment vector's error.Source: §B.2 · pp. 21, 23

B.3 Convex optimization for moment fitting

  • Frank–Wolfe fitting iteratively mixes public candidates to approximate the projection onto the feasible moment set within tolerance e_opt.The supplied convergence bounds give a Euclidean distance at most 4B_0/√(t+2) after t iterations.Source: §B.3 · pp. 23–24

B.4 General moment selections

  • Kernel moments can use Nyström landmark coordinates or all public grid points; with all grid points, Δ≤2κ, e_tail≤2ρ, and e_grid≤ρ.Nyström coordinates represent projected features in an orthonormal basis and also compute the squared norm of the omitted feature component.Source: §B.4 · pp. 24–25

C General kernel lower bounds

The section proves a general lower bound for private kernel-mean estimation by encoding binary choices in databases and relating errors in recovering those choices to kernel-mean error. The argument applies to continuous positive definite kernels under stated privacy and sample-size conditions.

C General kernel lower bounds

  • The proof encodes independent bits by replacing groups of database records, then uses group privacy to limit how accurately a private estimator can recover those bits.The separation parameter λ converts bit-recovery errors into kernel-mean error.Source: C General kernel lower bounds · pp. 25–26
  • Theorem C.2 gives a lower bound for private kernel-mean estimation for any continuous positive definite kernel, under its stated conditions on ε, δ, n, and the chosen point pairs.It allows 1 ≤ k ≤ nε/2 pairs and uses their feature-map separation in the bound.Source: C General kernel lower bounds · pp. 25–26
  • A private probability-measure output can be postprocessed into a private kernel-mean estimator, so a lower bound for kernel-mean estimation also applies to the measure output.The proof reduces to an arbitrary private kernel-mean estimator and chooses the closest encoded mean to its output.Source: C General kernel lower bounds · p. 26

D Gaussian and polynomial kernels

  • For Gaussian and polynomial kernels, the construction adds Gaussian noise to feature averages and fits a probability measure on a public grid.The constructions specify the features, grid, and fitting tolerance.Source: D Gaussian and polynomial kernels · p. 26

D.1 Gaussian features

The Gaussian-kernel construction uses an explicit feature map, truncates its high-degree coordinates, and fits noisy feature averages over a public grid. Its error bound accounts for truncation, privacy noise, grid and fitting errors, and synthetic-data sampling.

D.1 Gaussian features

  • The Gaussian feature map has inner products equal to the Gaussian kernel and unit norm, enabling the kernel MMD construction to work with feature averages.Coordinates are grouped by degree, and the construction retains degrees below a chosen cutoff.Source: §D.1 · p. 27
  • Truncating the Gaussian feature map at a public degree cutoff controls the omitted coordinates, while the retained blocks satisfy a finite bound on Γ.The construction chooses the cutoff using public parameters.Source: §D.1 · p. 27
  • A public grid controls record-rounding error by limiting how far each record moves when rounded to its nearest grid value.Keeping only selected feature coordinates cannot increase that distance.Source: §D.1 · p. 28
  • The expected MMD bound combines omitted-coordinate, grid, fitting, Gaussian-noise, and sampling errors.The passage bounds the omitted-coordinate contribution by 2/Nε,δ, the grid and fitting contributions by 1/Nε,δ each, and sampling by m^-1/2.Source: §D.1 · pp. 27–28

D.2 Polynomial features

The polynomial construction uses finite feature coordinates, while the later sections connect Matérn MMD bounds to wavelet moments and Gaussian denoising. These tools support results for Laplace and ReLU neural tangent kernels and cover Matérn smoothness regimes that earlier bounds did not fully address.

D.2 Polynomial features

  • For fixed polynomial-kernel parameters, the general kernel lower bound gives error at least cK/(nε) for a suitable database.The proof uses the points 0 and e1, whose squared feature distance is positive for both Gaussian and polynomial kernels.Source: §D.2 · p. 29

E Matérn, Laplace, and neural tangent kernels

  • The wavelet proof covers every ν > 0, including noninteger s, whereas the cited earlier bound for 0 < ν < d/2 requires s = ν + d/2 to be an integer.For ν ≥ d/2, the cited earlier result gives the matching lower-bound rate O(N^-1_ε,δ).Source: §D.2 · p. 29

E.1 Wavelet coefficients and MMD

  • Matérn MMD is controlled through weighted wavelet-coefficient errors, with higher-level omitted coefficients bounded by a summable tail.The wavelet norm comparison and spectral bounds support the MMD comparison; the tail bound follows by summing over levels above J.Source: §E.1 · p. 30

E.2 Reducing Gaussian noise

  • For Gaussian noise on an ℓ1-bounded moment vector, a public choice among returning zero, keeping the noisy vector, and soft-thresholding yields a denoising bound.The choice depends only on the public dimension, radius, and noise level.Source: §E.2 · p. 31

E.3 Proof of the Mat´ern upper bound

The Matérn upper-bound proof privately releases noisy wavelet moments, denoises them according to smoothness, and fits a probability measure. The resulting error is bounded by a rate depending on Nε,δ, with synthetic-data sampling controlled by choosing m sufficiently large.

E.3 Proof of the Matérn upper bound

  • The construction bounds the expected MMD of its probability measure q by Cb_Nε,δ under the stated parameter conditions.The bound is established by controlling tail, privacy, grid, and fitting errors.Source: §E.3 · pp. 32–33
  • The private moment release adds Gaussian noise to wavelet averages, with public level weights determining the noise allocation.The release is differentially private, and the subsequent estimator is obtained by postprocessing.Source: §E.3 · p. 32
  • When 0 < ν < d/2, levelwise denoising splits coarse and fine wavelet scales, yielding a block-error sum bounded by CN^-2s/d_ε,δ.The proof uses different error bounds for levels on either side of the split j*.Source: §E.3 · p. 33
  • Sampling m records from q contributes at most m^-1/2 to MMD, and the stated choice of m keeps this no larger than q’s MMD bound.This completes the upper bound in Theorem 3.3.Source: §E.3 · p. 34

E.4 Proof of Mat´ern lower bounds

The Matérn lower-bound proof constructs record pairs that make the relevant feature coefficients distinguishable. Applying Theorem C.2 in two smoothness regimes establishes (17), with constants independent of the algorithm’s wavelet basis.

E.4 Proof of Matérn lower bounds

  • For 0 < ν < d/2, k ≍ nε disjointly supported wavelet translates and paired records yield a least singular value λ ≳d,ν,ℓ k^−ν/d.The construction sets s = ν + d/2 and chooses the wavelet scale so 2^(jd) ≍d,ν k.Source: §E.4 · p. 34
  • For ν ≥ d/2, a single record pair (0, e1) has positive squared feature distance because the Matérn spectral density is strictly positive.This lets Theorem C.2 handle the higher-smoothness case with k = 1.Source: §E.4 · p. 34
  • Together, the two cases prove (17) with a constant depending only on d, ν, and ℓ, not on the algorithm’s wavelet basis.Source: §E.4 · p. 34

E.5 ReLU feature kernel and neural tangent kernels

The appendix relates ReLU feature and neural tangent kernels to Sobolev and Matérn spaces, then characterizes sliced Wasserstein-1 through projected one-dimensional queries. These connections yield a Laplace-MMD upper bound for sliced Wasserstein-1.

E.5 ReLU feature kernel and neural tangent kernels

  • H^(d+3)/2(Ω) embeds continuously into the RKHS of the ReLU feature kernel K_RF.The proof uses an even Sobolev extension to the sphere and avoids the kernel’s zero eigenvalues at odd degrees j ≥ 3.Source: §E.5 · p. 36
  • The neural tangent kernel RKHS is H^(d+1)/2(Ω) with equivalent norms, and its norm is comparable to the length-scale-1 Laplace-kernel RKHS norm.The Laplace kernel is the Matérn kernel with ν = 1/2.Source: §E.5 · pp. 36–37

F Sliced Wasserstein distance

  • Sliced Wasserstein-1 averages the one-dimensional Wasserstein-1 distances between distributions projected along directions on the sphere.For zero-mass µ = p − q, the projected CDF difference Hµ gives SW1(p, q) = ∥p − q∥SW.Source: F Sliced Wasserstein distance · p. 38

F.1 Query functions and upper bound

  • The IPM over averages of one-dimensional Lipschitz functions across projection directions equals sliced Wasserstein-1.The proof establishes both inequalities between d_FSW and SW1.Source: §F.1 · p. 38
  • Sliced Wasserstein-1 is bounded above by a dimension-dependent constant times MMD for the length-scale-1 Laplace kernel.This comparison supports the private wavelet estimator’s sliced Wasserstein upper bound.Source: §F.1 · pp. 38–39

F.2 Proof of the lower bound in Theorem 3.5

The lower-bound proof builds many databases whose records move within separate cells, then uses privacy to show an output cannot approximate most of them closely. It obtains a sliced Wasserstein-1 lower-bound scale of ρ ≍d (nε)^−(d+1)/(2d).

F.2 Proof of the lower bound in Theorem 3.5

  • ρ ≍d (nε)^−(d+1)/(2d) is the lower-bound scale, and some database has expected error at least ρ/2.The proof shows error greater than ρ with probability above 1/2 for a random database in its constructed family.Source: §F.2 · pp. 40, 45
  • The construction moves groups of records inside disjoint cells and linearizes the movements to create a large family of separated databases.It controls the geometry of their projected CDFs before applying the privacy argument.Source: §F.2 · pp. 39–40
  • The lower-bound construction first smooths the cell perturbations, using that convolution with ψh cannot increase sliced distance.Source: §F.2 · p. 40
  • Under 0 < ε ≤ 1 and 0 ≤ δ ≤ ε/100, changing one cell’s parameter changes r copied records, enabling a group-privacy information bound.The records are placed within Ω, and the privacy argument limits information about the independently selected cell parameters.Source: §F.2 · pp. 43–44

G ReLU IPMs

  • For ReLU IPMs, the upper bound uses four private releases to estimate ReLU averages, while the lower bound compares against Matérn MMD.Allowed neurons and networks are bounded and integrable, and the network IPM equals the neuron IPM by the stated argument.Source: G ReLU IPMs · p. 45

G.1 Estimating neuron averages privately

This section studies differentially private estimation of ReLU neuron averages, describing a four-release estimator and its error analysis. It gives dimension-dependent error rates, a minimax lower bound under the same privacy conditions, and bounds the error from sampling synthetic records.

G.1 Estimating neuron averages privately

  • PREM’s error has a relative part proportional to the true query mean and an additive floor; a shared-histogram expansion uses at most |G| binary queries per original query, with no approximation error or added privacy cost.Source: §G.1 · pp. 46–47
  • A private histogram selects representative directions by combining parameter distance with activation disagreement, yielding at most K ≤ Cd h^-d selected directions.The selection is postprocessing of the private histogram; the stated accuracy comparison also relies on PREM and sampling bounds.Source: §G.1 · p. 49
  • Two Gaussian releases estimate the selected neurons’ mean outputs and chosen subgradients, with sensitivity bounded by 2/n for each release.The mechanism uses factorizations with small column norms to bound sensitivity and row norms to control Gaussian noise.Source: §G.1 · pp. 50–51
  • The bounds are eA ≤ CdL max{1, K^((d−3)/(2d))}/Nε,δ and eB ≤ CdL K^((d−1)/(2d))/Nε,δ, with failure probability at most 2N^-2.Source: §G.1 · p. 51
  • A fourth PREM release estimates nonnegative linearization remainders, which are combined with neuron and subgradient estimates and clipped to [0, Rd] to recover neuron averages.The releases compose to give (ε, δ) privacy, including for adaptive histories.Source: §G.1 · p. 52
  • For d ≤ 3, both error terms are O_d(L/N_{ε,δ}); for d ≥ 4, both have order (L/N_{ε,δ})^((d+3)/(2d)).Since L = Λ^5 and the exponent is at most one, the logarithmic factor is at most Λ^5 in every dimension.Source: §G.1 · p. 53
  • The expected sampling error is at most sqrt(2 log(2(d + 1))/m), uniformly in q.Symmetrization and ReLU contraction reduce the bound to the largest absolute value among d + 1 coordinate sums; sampling adds at most s_FNN(m).Source: §G.1 · p. 53

G.2 Minimax lower bound

  • The ReLU feature-kernel squared MMD equals average squared neuron discrepancy, enabling a comparison with the Matérn kernel and a proof of lower bound (25) via Theorem 3.3.The comparison uses ReLU homogeneity to relate neuron discrepancy to the constrained neuron IPM, under the same privacy conditions.Source: §G.2 · p. 53

Related papers

Loading 2610.30196v2…