arXiv preprint ·
Intrinsic-Dimensional Wasserstein Guarantees for Private Synthetic Measures
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We study an $\varepsilon$-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 $\widetilde O_d((\varepsilon n)^{-1/d})$ for $d\ge2$, which is optimal compared to the minimax lower bound up to a logarithmic factor. Moreover, for $d\ge3$ and $2<s\le 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 $\widetilde O_{d,s}((\varepsilon 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$.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
A quantitative tree-likeness bound from average hyperbolicity
Approximating Measures on Function Spaces: Transport and Truncation
Preservation of Log-Concavity and Convergence of Wasserstein-Fisher-Rao Gradient Flows
Critical and near-critical influence bounds for ferromagnetic Ising models
Total Variation Distance Estimation through Domain Reduction
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.