Algorithmically Effective Differentially Private Synthetic Data

MaRDI QIDQ6426137zbMATH OpenFDO

Authors Yiyun He, Roman Vershynin, Yizhe Zhu

Publication date 10 February 2023

Abstract: We present a highly effective algorithmic approach for generating $varepsilon$-differentially private synthetic data in a bounded metric space with near-optimal utility guarantees under the 1-Wasserstein distance. In particular, for a dataset $X$ in the hypercube $[0,1{]}^d$, our algorithm generates synthetic dataset $Y$ such that the expected 1-Wasserstein distance between the empirical measure of $X$ and $Y$ is $O((varepsilonn{)}^{-1/d})$ for $dgeq2$, and is $O(lo{g}^2(varepsilonn)(varepsilonn{)}^{-1})$ for $d=1$. The accuracy guarantee is optimal up to a constant factor for $dgeq2$, and up to a logarithmic factor for $d=1$. Our algorithm has a fast running time of $O(varepsilondn)$ for all $dgeq1$ and demonstrates improved accuracy compared to the method in (Boedihardjo et al., 2022) for $dgeq2$.

This page was built for publication: Algorithmically Effective Differentially Private Synthetic Data

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6426137)