From Robustness to Privacy and Back
From Robustness to Privacy and Back
复制标题
DOI：
10.48550/arxiv.2302.01855
复制
发表时间：
2023-02
期刊：
影响因子：
--
通讯作者：
Hilal Asi;Jonathan Ullman;Lydia Zakynthinou
中科院分区：
文献类型：
--
作者：
Hilal Asi;Jonathan Ullman;Lydia Zakynthinou
我们研究了统计推理和机器学习中算法的两个要求之间的关系：差别保密性和对敌意数据破坏的稳健性。Dwork和Lei(STEC 2009)首先观察到它们在概念上的相似性，他们观察到私有算法满足健壮性，并给出了将健壮算法转换为私有算法的一般方法。然而，所有将健壮算法转换为私有算法的通用方法都会导致次优错误率。我们的工作给出了第一个黑盒变换，它将任何敌对的健壮算法转换为满足纯差分隐私的算法。此外，我们还证明了对于任何低维估计任务，将我们的变换应用于最优稳健估计会导致最优私人估计。因此，我们得出结论：对于任何低维任务，$/varepsilon$-差分私有估计量的最优错误率本质上与对$1/varepsilon$训练样本具有健壮性的估计量的最优错误率相同。我们应用我们的变换来获得几个高维任务的新的最优私人估计器，包括高斯(稀疏)线性回归和主成分分析。最后，我们给出了我们的变换的一个扩展，它导致了近似差分私有算法，其误差不依赖于输出空间的范围，这在纯差分保密下是不可能的。
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.