Geometry-Adaptive Mechanisms for Private Synthetic Data

arXiv:2609.33363v1 Announce Type: cross 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 dge2, existing pure (arepsilon)-differentially private mechanisms achieve expected 1-Wasserstein error of order (arepsilon 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 arepsilon-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(arepsilon 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 (arepsilon 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.

Source: arXiv cs.LG | 2026-09-29