Efficient mean estimation with pure differential privacy via a sum-of-squares exponential mechanism
Efficient mean estimation with pure differential privacy via a sum-of-squares exponential mechanism
复制标题
通过平方和指数机制实现具有纯差分隐私的高效均值估计
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Mahbod Majid
中科院分区：
文献类型：
--
作者：
Samuel B. Hopkins;Gautam Kamath;Mahbod Majid
我们给出了第一个多项式时间算法估计的平均值的d-变量的概率分布与有界协方差从n（d）个独立的样本服从纯差分隐私。现有的算法要么导致指数运行时间，需要Ω（d1.5）的样本，或满足较弱的集中或近似差分隐私条件。特别是，所有以前的多项式时间算法都需要d1+Ω（1）个样本来保证小的隐私损失，具有“密码学”的高概率，1−2−dΩ（1），而我们的算法即使在这种严格的设置下也保持了n（d）个样本的复杂度。我们的主要技术是一种新的方法，使用强大的平方和方法（SoS）设计差分隐私算法。算法的SoS证明是最近高维算法统计中许多作品的一个关键主题-估计器显然需要指数运行时间，但其分析可以通过低阶平方和证明来捕获，可以自动转换为具有相同可证明保证的多项式时间算法。我们证明了一个类似的证明私有算法的现象：实例的主力指数机制，显然需要指数时间，但可以分析与低程度的SoS证明可以自动变成多项式时间差分私有算法。我们证明了一个元定理捕捉这种现象，我们希望在私人算法设计中得到广泛的使用。我们的技术还在高维的差异私人和强大的统计数据之间建立了新的联系。特别是，通过我们的证明，私人算法透镜，几个良好的研究从最近的作品在算法的鲁棒统计证明直接产生我们的差分私人均值估计算法的关键组成部分。
We give the first polynomial-time algorithm to estimate the mean of a d-variate probability distribution with bounded covariance from Õ(d) independent samples subject to pure differential privacy. Prior algorithms for this problem either incur exponential running time, require Ω(d1.5) samples, or satisfy only the weaker concentrated or approximate differential privacy conditions. In particular, all prior polynomial-time algorithms require d1+Ω(1) samples to guarantee small privacy loss with “cryptographically” high probability, 1−2−dΩ(1), while our algorithm retains Õ(d) sample complexity even in this stringent setting. Our main technique is a new approach to use the powerful Sum of Squares method (SoS) to design differentially private algorithms. SoS proofs to algorithms is a key theme in numerous recent works in high-dimensional algorithmic statistics – estimators which apparently require exponential running time but whose analysis can be captured by low-degree Sum of Squares proofs can be automatically turned into polynomial-time algorithms with the same provable guarantees. We demonstrate a similar proofs to private algorithms phenomenon: instances of the workhorse exponential mechanism which apparently require exponential time but which can be analyzed with low-degree SoS proofs can be automatically turned into polynomial-time differentially private algorithms. We prove a meta-theorem capturing this phenomenon, which we expect to be of broad use in private algorithm design. Our techniques also draw new connections between differentially private and robust statistics in high dimensions. In particular, viewed through our proofs-to-private-algorithms lens, several well-studied SoS proofs from recent works in algorithmic robust statistics directly yield key components of our differentially private mean estimation algorithm.
登录
查看更多内容
DOI：
--
发表时间：
2018-05
期刊：
--
影响因子：
--
作者：
Gautam Kamath;Jerry Li;Vikrant Singhal;Jonathan Ullman
通讯作者：
Gautam Kamath;Jerry Li;Vikrant Singhal;Jonathan Ullman
DOI：
--
发表时间：
2020
期刊：
37th International Conference on Machine Learning (ICML 2020
影响因子：
--
作者：
Wang, D.;Xiao, H.;Devadas, S.;Xu, J.
通讯作者：
Xu, J.
影响因子：
6
作者：
Kume S;Nagasu H;Nangaku M;Nishiyama A;Nakamoto H;Kashihara N
通讯作者：
Kashihara N
影响因子：
--
作者：
Yatharth Dubey;A. Korolova
通讯作者：
Yatharth Dubey;A. Korolova
从 Harish-Chandra–Itzykson–Zuber 密度中采样矩阵及其在量子推理和差分隐私中的应用
DOI：
10.1145/3406325.3451094
发表时间：
2021
期刊：
STOC 2021: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Leake, Jonathan;McSwiggen, Colin;Vishnoi, Nisheeth K.
通讯作者：
Vishnoi, Nisheeth K.