Geometry-Adaptive Mechanisms for Private Synthetic Data
A private synthetic-data mechanism adapts Wasserstein error to data geometry, improving the rate from 1/d to 1/k.
Pure epsilon-differentially private synthetic data on the unit cube has expected 1-Wasserstein error of order (epsilon n)^{-1/d} for dimension d at least 2. The authors define a multiscale packing-growth dimension k and propose Adaptive Pruned-PMM, combining private depth selection with a pruned Private Measure Mechanism. For fixed privacy budgets and geometry, expected error scales as (epsilon n)^{-1/k} for k greater than 1, and a lower bound shows that exponent is sharp. Expected runtime is O(d(n+d) log(epsilon n)), near-linear in sample size for fixed dimension.
- Worst-case pure DP synthetic data has Wasserstein error of order (epsilon n)^{-1/d}.
- Packing-growth dimension k measures lower-dimensional geometric complexity.
- Adaptive Pruned-PMM achieves expected error of order (epsilon n)^{-1/k}.
- A matching lower bound shows the 1/k exponent is sharp.
- Runtime is near-linear in n for fixed dimension and privacy budget.
Full article198 words · extracted from arxiv.org · click to collapse
Generating differentially private synthetic data with meaningful Wasserstein utility guarantees is challenging in high dimensions. For datasets of size \(n\) on $[0,1]^d$ with $d\ge2$, existing pure \(\varepsilon\)-differentially private mechanisms achieve expected $1$-Wasserstein error of order $(\varepsilon n)^{-1/d}$, reflecting the curse of dimensionality. While this rate is optimal in the worst case, it can be overly pessimistic when the data are supported on a lower-dimensional set. We formalize this through a multiscale packing-growth dimension $k$, which captures the geometric complexity of the support via the growth of packing numbers across scales. We propose \emph{Adaptive Pruned-PMM}, a pure $\varepsilon$-differentially private mechanism that combines private depth selection with our pruned variant of the Private Measure Mechanism (PMM) of He et al.\ (2023). The mechanism supports deeper, geometry-adapted hierarchies with expected running time $O\!\left(d(n+d)\log(\varepsilon n)\right)$, which is near-linear in $n$ for fixed dimension and privacy budget. Under an external multiscale packing-growth condition with dimension $k$, we show that, for fixed positive privacy budgets and fixed geometry, the expected $1$-Wasserstein error is of order $(\varepsilon n)^{-1/k}$ for $k>1$ as $n$ grows. We also prove a lower bound under a corresponding internal packing-growth condition, showing that the exponent $1/k$ is sharp within this framework.
Text extracted automatically; images, tables and formatting may be missing. Original: https://arxiv.org/abs/2609.33363