In this paper, we present three new error bounds, in terms of the Frobenius norm, for covariance estimation under differential privacy: (1) a worst-case bound of $\tilde{O}(d^{1/4}/\sqrt{n})$, which improves the standard Gaussian mechanism $\tilde{O}(d/n)$ for the regime $d>\widetilde{\Omega}(n^{2/3})$; (2) a trace-sensitive bound that improves the state of the art by a $\sqrt{d}$-factor, and (3) a tail-sensitive bound that gives a more instance-specific result. The corresponding algorithms are also simple and efficient. Experimental results show that they offer significant improvements over prior work.
翻译：在本文中,我们从Frobenius规范的角度提出了三个新的误差界限,用于不同隐私下的共变估算:(1) 最坏的误差界限$tilde{O}(d ⁇ 1/4}/\sqrt{n})$,这改进了该制度标准的Gaussian机制$tilde{O}(d/n)$(d/n)$;(2) 微调敏感界限,它通过$\sqrt{d}$-macoral改进了工艺状态;(3) 尾部灵敏度约束,它带来更具体实例的结果。相应的算法也简单而有效。实验结果显示,它们比先前的工作有很大改进。
相关内容
微信扫码咨询专知VIP会员