Private synthetic data with error adapted to data geometry
Geometry-Adaptive Mechanisms for Private Synthetic Data
Data Structures and AlgorithmsCryptography and SecurityMachine Learning
Summary
Creating private fake data that looks like real data is hard when there are many features. Current methods get less accurate as the number of features grows, which is called the curse of dimensionality. The authors designed a method that adjusts to the real geometric complexity of the data, not just the number of features, making private synthetic data more accurate when data lies on simpler shapes. Their method picks geometric scales adaptively and runs efficiently, giving better accuracy guarantees based on the actual data structure.
What this means in practice
- •For privacy engineers: Generate private synthetic datasets that better preserve data structure for large-scale high-dimensional data with improved accuracy guarantees.
- •For machine learning practitioners: Use geometry-adaptive synthetic data generation to train models on privacy-protected data with reduced error when data has low intrinsic dimension.
Authors
Raoof Zare Moayedi, Amir R. Asadi, Mohammad Hossein Yassaee, Gholamali Aminian
Abstract
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.