Algorithmically Effective Differentially Private Synthetic Data
Algorithmically Effective Differentially Private Synthetic Data
复制标题
DOI：
10.48550/arxiv.2302.05552
复制
发表时间：
2023-02
期刊：
影响因子：
--
通讯作者：
Yi He;R. Vershynin;Yizhe Zhu
中科院分区：
文献类型：
--
作者：
Yi He;R. Vershynin;Yizhe Zhu
我们提出了一种高效的算法方法，用于在有界度量空间中生成$\varepsilon$ -差分私有合成数据，在1-Wasserstein距离下具有接近最优的效用保证。特别是，对于超立方体$[0,1]^d$中的数据集$X$，我们的算法生成合成数据集$Y$，使得$X$和$Y$的经验测度之间的期望1-Wasserstein距离对于$d\geq 2$为$O((\varepsilon n)^{-1/d})$，对于$d=1$为$O(\log^2(\varepsilon n)(\varepsilon n)^{-1})$。对于$d\geq 2$，精度保证达到一个常数因子，对于$d=1$，精度保证达到一个对数因子。我们的算法对所有$d\geq 1$的运行时间为$O(\varepsilon dn)$，并且与（Boedihardjo et al., 2022）中对$d\geq 2$的方法相比，显示出更高的准确性。
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((\varepsilon n)^{-1/d})$ for $d\geq 2$, and is $O(\log^2(\varepsilon n)(\varepsilon n)^{-1})$ for $d=1$. The accuracy guarantee is optimal up to a constant factor for $d\geq 2$, and up to a logarithmic factor for $d=1$. Our algorithm has a fast running time of $O(\varepsilon dn)$ for all $d\geq 1$ and demonstrates improved accuracy compared to the method in (Boedihardjo et al., 2022) for $d\geq 2$.