We study the relationship between two desiderata of algorithms in statistical inference and machine learning: differential privacy and robustness to adversarial data corruptions. Their conceptual similarity was first observed by Dwork and Lei (STOC 2009), who observed that private algorithms satisfy robustness, and gave a general method for converting robust algorithms to private ones. However, all general methods for transforming robust algorithms into private ones lead to suboptimal error rates. Our work gives the first black-box transformation that converts any adversarially robust algorithm into one that satisfies pure differential privacy. Moreover, we show that for any low-dimensional estimation task, applying our transformation to an optimal robust estimator results in an optimal private estimator. Thus, we conclude that for any low-dimensional task, the optimal error rate for $\varepsilon$-differentially private estimators is essentially the same as the optimal error rate for estimators that are robust to adversarially corrupting $1/\varepsilon$ training samples. We apply our transformation to obtain new optimal private estimators for several high-dimensional tasks, including Gaussian (sparse) linear regression and PCA. Finally, we present an extension of our transformation that leads to approximate differentially private algorithms whose error does not depend on the range of the output space, which is impossible under pure differential privacy.

翻译：我们研究了统计推理和机器学习中两种算法的偏差关系:隐私和稳健性与对抗性数据腐败的不同。Dwork和Lei(STOC 2009)首先观察到了这两种算法的概念相似性。Dwork和Lei(STOC 2009)发现,私人算法符合稳健性,并给出了将稳健算法转换为私人算法的一般方法。然而,所有将稳健算法转换为私人算法的一般方法都会导致低于最佳误差率。我们的工作提供了第一个黑箱转换,将任何对抗性稳健算法转换为满足纯粹差异隐私权的黑箱转换。此外,我们展示了任何低维度估算任务,将我们转换为最佳稳健的估测算法结果,在最佳的私人估测算法中,对于任何低维度任务,我们得出最佳的误差率率率率率率率,对于目前无法进行精确度的私人变校正率,我们最终要进行最优化的私人测算。