Privately Learning High-Dimensional Distributions
Privately Learning High-Dimensional Distributions
复制标题
DOI：
--
复制
发表时间：
2018-05
期刊：
影响因子：
--
通讯作者：
Gautam Kamath;Jerry Li;Vikrant Singhal;Jonathan Ullman
中科院分区：
文献类型：
--
作者：
Gautam Kamath;Jerry Li;Vikrant Singhal;Jonathan Ullman
我们为两个基本的高维学习问题提供了新颖，计算高效和差异性私有算法：学习多元高斯和在总变化距离上学习在布尔利亚超立方体上的产品分布。我们算法的样本复杂性几乎与在广泛的参数中为这些任务的最佳非私有学习者的样本复杂性匹配，这表明隐私本质上是免费的。特别是，与以前的方法相比，我们的学习高斯人的算法不需要在参数范围内进行强大的先验界限。我们的算法引入了一种新型的技术方法，以降低我们称为递归私人预处理的估计程序的敏感性。
We present novel, computationally efficient, and differentially private algorithms for two fundamental high-dimensional learning problems: learning a multivariate Gaussian and learning a product distribution over the Boolean hypercube in total variation distance. The sample complexity of our algorithms nearly matches the sample complexity of the optimal non-private learners for these tasks in a wide range of parameters, showing that privacy comes essentially for free for these problems. In particular, in contrast to previous approaches, our algorithm for learning Gaussians does not require strong a priori bounds on the range of the parameters. Our algorithms introduce a novel technical approach to reducing the sensitivity of the estimation procedure that we call recursive private preconditioning.