Differential privacy has emerged as a standard requirement in a variety of applications ranging from the U.S. Census to data collected in commercial devices, initiating an extensive line of research in accurately and privately releasing statistics of a database. An increasing number of such databases consist of data from multiple sources, not all of which can be trusted. This leaves existing private analyses vulnerable to attacks by an adversary who injects corrupted data. Despite the significance of designing algorithms that guarantee privacy and robustness (to a fraction of data being corrupted) simultaneously, even the simplest questions remain open. For the canonical problem of estimating the mean from i.i.d. samples, we introduce the first efficient algorithm that achieves both privacy and robustness for a wide range of distributions. This achieves optimal accuracy matching the known lower bounds for robustness, but the sample complexity has a factor of $d^{1/2}$ gap from known lower bounds. We further show that this gap is due to the computational efficiency; we introduce the first family of algorithms that close this gap but takes exponential time. The innovation is in exploiting resilience (a key property in robust estimation) to adaptively bound the sensitivity and improve privacy.

对于从共享数据中进行统计学习和分析，在保证隐私和鲁棒性两个主要问题中，PRIME是第一种同时实现了隐私性和鲁棒性的高效算法, 可以应用于广泛的分布。我们还使用了一个新的指数时间算法来提高PRIME的样本复杂度，达到接近最优的保证，并与已知的（非鲁棒）私有均值估计的下限相匹配，说明同时保证隐私和鲁棒性不需要额外的统计代价。

鲁棒性和差分隐私平均数估计