论文标题
鲁棒性意味着统计估算中的隐私
Robustness Implies Privacy in Statistical Estimation
论文作者
论文摘要
我们研究了高维算法统计数据中对抗性鲁棒性与差异隐私之间的关系。我们将第一个从隐私性减少到鲁棒性的黑盒减少，可以在样本复杂性，准确性和隐私之间产生私人估计量，以提供广泛的基本高维参数估计问题，包括平均值和协方差估计。我们表明，在某些重要的特殊情况下，可以在多项式时间内实施这种减少。特别是，使用基于平方体总和的高维高斯人的平均值和协方差，使用几乎最佳的多项式鲁棒估计器，我们为这些问题设计了这些问题的第一个多项式时间私人估计器，这些私人估计器几乎是优势的样本 - 准确性 - 准确性 - 挑战 - 挑战性挑战。我们的算法对于几乎最佳的对抗腐败样品也是强大的。
We study the relationship between adversarial robustness and differential privacy in high-dimensional algorithmic statistics. We give the first black-box reduction from privacy to robustness which can produce private estimators with optimal tradeoffs among sample complexity, accuracy, and privacy for a wide range of fundamental high-dimensional parameter estimation problems, including mean and covariance estimation. We show that this reduction can be implemented in polynomial time in some important special cases. In particular, using nearly-optimal polynomial-time robust estimators for the mean and covariance of high-dimensional Gaussians which are based on the Sum-of-Squares method, we design the first polynomial-time private estimators for these problems with nearly-optimal samples-accuracy-privacy tradeoffs. Our algorithms are also robust to a nearly optimal fraction of adversarially-corrupted samples.
