Robust and Differentially Private Mean Estimation
Robust and Differentially Private Mean Estimation
复制标题
DOI：
--
复制
发表时间：
2021-02
期刊：
影响因子：
--
通讯作者：
Xiyang Liu;Weihao Kong;S. Kakade;Sewoong Oh
中科院分区：
文献类型：
--
作者：
Xiyang Liu;Weihao Kong;S. Kakade;Sewoong Oh
在联邦学习和元学习等平台中越来越广泛采用的共享数据的统计学习和分析中，有两个主要问题：隐私和鲁棒性。每一个参与者都应该能够作出贡献，而不必担心泄露自己的敏感信息。同时，系统应该在恶意参与者插入损坏数据的情况下保持健壮。最近从共享数据中学习的算法进展集中在这些威胁中的任何一个，使系统容易受到另一个威胁的影响。我们弥合这一差距的典型问题估计的平均从i.i.d.样品我们介绍PRIME，这是第一个有效的算法，实现了广泛的分布的隐私性和鲁棒性。我们进一步补充这一结果与一种新的指数时间算法，提高了样本的复杂性PRIME，实现了接近最优的保证和匹配已知的下限（非鲁棒性）私人均值估计。这证明了同时保证隐私和鲁棒性没有额外的统计成本。
In statistical learning and analysis from shared data, which is increasingly widely adopted in platforms such as federated learning and meta-learning, there are two major concerns: privacy and robustness. Each participating individual should be able to contribute without the fear of leaking one’s sensitive information. At the same time, the system should be robust in the presence of malicious participants inserting corrupted data. Recent algorithmic advances in learning from shared data focus on either one of these threats, leaving the system vulnerable to the other. We bridge this gap for the canonical problem of estimating the mean from i.i.d. samples. We introduce PRIME, which is the first efficient algorithm that achieves both privacy and robustness for a wide range of distributions. We further complement this result with a novel exponential time algorithm that improves the sample complexity of PRIME, achieving a near-optimal guarantee and matching a known lower bound for (non-robust) private mean estimation. This proves that there is no extra statistical cost to simultaneously guaranteeing privacy and robustness.