A Private and Computationally-Efficient Estimator for Unbounded Gaussians
This solves a fundamental problem in private data analysis for statisticians and machine learning practitioners, representing a significant advance over previous nonconstructive or bounded methods.
The paper tackles the problem of estimating the mean and covariance of an arbitrary Gaussian distribution under differential privacy constraints, achieving the first polynomial-time and polynomial-sample estimator without requiring prior bounds on parameters.
We give the first polynomial-time, polynomial-sample, differentially private estimator for the mean and covariance of an arbitrary Gaussian distribution $\mathcal{N}(μ,Σ)$ 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 $μ$ and $Σ$. The primary new technical tool in our algorithm is a new differentially private preconditioner that takes samples from an arbitrary Gaussian $\mathcal{N}(0,Σ)$ and returns a matrix $A$ such that $A ΣA^T$ has constant condition number.