论文标题
差异私人协方差重新审视
Differentially Private Covariance Revisited
论文作者
论文摘要
在本文中，我们提出了两种在集中差异隐私（ZCDP）下进行协方差估计的新算法。第一个算法达到了$ \ tilde {o}（d^{1/4} \ sqrt {\ sqrt {\ mathrm {tr}}/\ sqrt {n} + \ sqrt {d}/n）$，其中$ \ mathrm matr a covar的frobenius错误。通过服用$ \ mathrm {tr} = 1 $，这也意味着$ \ tilde {o}（d^{1/4}/\ sqrt {n}）$的最差案例错误绑定，可改善标准高斯机械师的$ \ tilde {o} $（d/n）$ $ d> \widetildeΩ（n^{2/3}）$。我们的第二个算法提供了一种对尾敏感的界限，在偏斜的数据上可能会更好。相应的算法也很简单有效。实验结果表明，它们对先前的工作提供了重大改进。
In this paper, we present two new algorithms for covariance estimation under concentrated differential privacy (zCDP). The first algorithm achieves a Frobenius error of $\tilde{O}(d^{1/4}\sqrt{\mathrm{tr}}/\sqrt{n} + \sqrt{d}/n)$, where $\mathrm{tr}$ is the trace of the covariance matrix. By taking $\mathrm{tr}=1$, this also implies a worst-case error bound of $\tilde{O}(d^{1/4}/\sqrt{n})$, which improves the standard Gaussian mechanism's $\tilde{O}(d/n)$ for the regime $d>\widetildeΩ(n^{2/3})$. Our second algorithm offers a tail-sensitive bound that could be much better on skewed data. The corresponding algorithms are also simple and efficient. Experimental results show that they offer significant improvements over prior work.
