Intrinsic-Dimensional Wasserstein Guarantees for Private Synthetic Measures
Abstract
We study an ε-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 Õd((ε n)−1/d) for d≥2, which is optimal compared to the minimax lower bound up to a logarithmic factor. Moreover, for d≥3 and 2<s≤ d, if the data set has covering number at most Ar−s over the relevant finite range of scales r, the expected error improves to Õd,s((ε n)−1/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.
Related
- Intrinsic Contraction Theory and Stabilization of Probability Measures on the Wasserstein Space
- Diffusion Flow Matching: Dimension-Improved KL Bounds and Wasserstein Guarantees
- Differentially Private Distributed Optimization via the Intrinsic Randomness of Zeroth-Order Estimators: Sampling Geometry, Convergence, and Privacy Guarantees
- Wasserstein bounds for invariant measures in the Smoluchowski-Kramers approximation with stable noise
- Dimension-free Convergence Rate in Sliced Wasserstein Distance for Empirical Measures of Markov Processes
BibTeX
@misc{he2026intrinsicdimensional,
title = {{Intrinsic-Dimensional Wasserstein Guarantees for Private Synthetic Measures}},
author = {Yiyun He},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.17624},
eprint = {2609.17624},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.17624},
}
RIS
TY - UNPB
TI - Intrinsic-Dimensional Wasserstein Guarantees for Private Synthetic Measures
AU - Yiyun He
PY - 2026
DA - 2026/09/15
PB - arXiv
DO - 10.48550/arxiv.2609.17624
UR - https://arxiv.org/abs/2609.17624
AB - We study an ε-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 Õ_d((ε n)^−1/d) for d≥2, which is optimal compared to the minimax lower bound up to a logarithmic factor. Moreover, for d≥3 and 2<s≤ d, if the data set has covering number at most Ar^−s over the relevant finite range of scales r, the expected error improves to Õ_d,s((ε n)^−1/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.
ER -