Intrinsic-Dimensional Wasserstein Guarantees for Private Synthetic Measures

We study an $\epsilon$-differentially private synthetic measure for $n$ points in $[0,1{]}^d$ by applying the existing PrivTree algorithm to construct an adaptive binary partition and then privately releasing its leaf masses. We consider the worst-case data model without any sampling or population-distribution assumption. The 1-Wasserstein error of the synthetic measure is ${\tilde{O}}_d((\epsilon n{)}^{-1\mathrm{/}d})$ for $d\ge 2$, which is optimal compared to the minimax lower bound up to a logarithmic factor. Moreover, for $d\ge 3$ and $2<s\le d$, if the data set has covering number at most $A{r}^{-s}$ over the relevant finite range of scales $r$, the expected error improves to ${\tilde{O}}_{d,s}((\epsilon n{)}^{-1\mathrm{/}s})$. Thus the rate depends on a finite-scale intrinsic dimension rather than the ambient dimension, without requiring the recovery of a low-dimensional manifold. We also introduce a shifting technique to further avoid the exponential dependence of the constant on the ambient dimension $d$.