Geometry-Adaptive Mechanisms for Private Synthetic Data
Not on the map. Why?
Abstract (arXiv)
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≥2, 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 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.
Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 16 of its 39 references that are in the map. First posted on arXiv 27 Sep 2026.
Builds on
16 of 39 references.
References · 16
- 2016Deep Learning with Differential Privacycited by 2,728
- 2021A Universal Law of Robustness via Isoperimetrycited by 151
- 2016Minimax Optimal Procedures for Locally Private Estimationcited by 107
- 2021Winning the NIST Contest: A scalable and general approach to differentially private synthetic datacited by 102
- 2021A Dynamical System Perspective for Lipschitz Neural Networkscited by 60
- 2022Private Synthetic Data for Multitask Learning and Marginal Queriescited by 35
- 2015Differentially Private k-Means Clusteringcited by 27
- 2013Efficient Algorithms for Privately Releasing Marginals via Convex Relaxationscited by 17
- 2023Algorithmically Effective Differentially Private Synthetic Datacited by 11
- 2021Privacy of synthetic data: a statistical frameworkcited by 10
- 2021Private sampling: a noiseless approach for generating differentially private synthetic datacited by 8
- 2021Covariance's Loss is Privacy's Gain: Computationally Efficient, Private and Accurate Synthetic Datacited by 7
4 more
- 2023Certified private data release for sparse Lipschitz functionscited by 7
- 2023Differentially Private Low-dimensional Synthetic Data from High-dimensional Datasetscited by 4
- 2024Metric geometry of the privacy-utility tradeoffcited by 3
- 2024Differentially Private Synthetic Data with Private Density Estimationcited by 2
Built on by
Not cited yet.