论文标题

隐私会引起鲁棒性:信息计算差距和稀疏平均估计

Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimation

论文作者

Georgiev, Kristian, Hopkins, Samuel B.

论文摘要

我们建立了鲁棒和差异性算法之间的简单连接:私有机制以非常高的概率表现良好的私人机制自动稳健,即使它们所收到的样本的恒定分数也受到了对抗性损坏,即使它们保持准确性也是如此。由于最佳机制通常会达到这些高成功概率,因此我们的结果表明,许多基本统计问题的最佳私人机制是强大的。 我们研究了该观察结果对不同统计问题的算法和计算复杂性的后果。假设Brennan-Bresler Secret-Leakage种植了集团的猜想,我们证明了计算效率,隐私泄漏和稀疏平均值估计的成功概率之间的基本权衡。尚不清楚与此折衷的私有算法 - 我们通过平方符号方法在多项式大量参数范围内实现了(取决于聚类因子)。 为了建立用于私人稀疏平均值估计的信息计算差距,我们还必须使用少于有效算法的样品设计新的(指数时间)机制。最后,我们为其他几个统计和学习问题提供了隐私引起的信息计算差距的证据,包括PAC学习奇偶校验功能以及对多元高斯的平均值的估计。

We establish a simple connection between robust and differentially-private algorithms: private mechanisms which perform well with very high probability are automatically robust in the sense that they retain accuracy even if a constant fraction of the samples they receive are adversarially corrupted. Since optimal mechanisms typically achieve these high success probabilities, our results imply that optimal private mechanisms for many basic statistics problems are robust. We investigate the consequences of this observation for both algorithms and computational complexity across different statistical problems. Assuming the Brennan-Bresler secret-leakage planted clique conjecture, we demonstrate a fundamental tradeoff between computational efficiency, privacy leakage, and success probability for sparse mean estimation. Private algorithms which match this tradeoff are not yet known -- we achieve that (up to polylogarithmic factors) in a polynomially-large range of parameters via the Sum-of-Squares method. To establish an information-computation gap for private sparse mean estimation, we also design new (exponential-time) mechanisms using fewer samples than efficient algorithms must use. Finally, we give evidence for privacy-induced information-computation gaps for several other statistics and learning problems, including PAC learning parity functions and estimation of the mean of a multivariate Gaussian.

扫码加入交流群

加入微信交流群

微信交流群二维码

扫码加入学术交流群,获取更多资源