A Private and Computationally-Efficient Estimator for Unbounded Gaussians
A Private and Computationally-Efficient Estimator for Unbounded Gaussians
复制标题
DOI：
--
复制
发表时间：
2021-11
期刊：
影响因子：
--
通讯作者：
Gautam Kamath;Argyris Mouzakis;Vikrant Singhal;T. Steinke;Jonathan Ullman
中科院分区：
文献类型：
--
作者：
Gautam Kamath;Argyris Mouzakis;Vikrant Singhal;T. Steinke;Jonathan Ullman
我们给出了第一个多项式时间，多项式样本，差分私人估计的均值和协方差的任意高斯分布$\mathcal{N}（\mu，\Sigma）$在$\mathbb{R}^d$。所有以前的估计要么是非建设性的，无限的运行时间，或需要用户指定的参数$\mu$和$\Sigma$的先验界限。我们算法中的主要新技术工具是一个新的差分私有预处理器，它从任意高斯$\mathcal{N}（0，\Sigma）$中采样并返回一个矩阵$A$，使得$A \Sigma A^T$具有恒定的条件数。
We give the first polynomial-time, polynomial-sample, differentially private estimator for the mean and covariance of an arbitrary Gaussian distribution $\mathcal{N}(\mu,\Sigma)$ in $\mathbb{R}^d$. All previous estimators are either nonconstructive, with unbounded running time, or require the user to specify a priori bounds on the parameters $\mu$ and $\Sigma$. The primary new technical tool in our algorithm is a new differentially private preconditioner that takes samples from an arbitrary Gaussian $\mathcal{N}(0,\Sigma)$ and returns a matrix $A$ such that $A \Sigma A^T$ has constant condition number.