A Private and Computationally-Efficient Estimator for Unbounded Gaussians

Abstract

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.

References in corpus (11)

• Privacy and Statistical Risk: Formalisms and Minimax Bounds
• The Cost of Privacy: Rates of Convergence for Parameter Estimation with Differential Privacy
• Differentially Private Confidence Intervals
• Learning discrete distributions: user vs item-level privacy
• Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Data
• Robust and Differentially Private Mean Estimation
• Covariance-Aware Private Mean Estimation Without Private Covariance Estimation
• On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussians
• On Differentially Private Stochastic Convex Optimization with Heavy-tailed Data
• Differentially private sub-Gaussian location estimators
• Optimal Private Median Estimation under Minimal Distributional Assumptions

Cited by in corpus (3)

• Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism
• Differential privacy and robust statistics in high dimensions
• Private and polynomial time algorithms for learning Gaussians and beyond