Privately Estimating a Gaussian: Efficient, Robust, and Optimal

In this work, we give efficient algorithms for privately estimating a Gaussian distribution in both pure and approximate differential privacy (DP) models with optimal dependence on the dimension in the sample complexity.

• In the pure DP setting, we give an efficient algorithm that estimates an unknown ddimensional Gaussian distribution up to an arbitrary tiny total variation error using O(d 2 log κ) samples while tolerating a constant fraction of adversarial outliers. Here, κ is the condition number of the target covariance matrix. The sample bound matches best non-private estimators in the dependence on the dimension (up to a polylogarithmic factor). We prove a new lower bound on differentially private covariance estimation to show that the dependence on the condition number κ in the above sample bound is also tight. Prior to our work, only identifiability results (yielding inefficient super-polynomial time algorithms) were known for the problem.

• In the approximate DP setting, we give an efficient algorithm to estimate an unknown Gaussian distribution up to an arbitrarily tiny total variation error using O(d 2 ) samples while tolerating a constant fraction of adversarial outliers. Prior to our work, all efficient approximate DP algorithms incurred a super-quadratic sample cost or were not outlierrobust. For the special case of mean estimation, our algorithm achieves the optimal sample complexity of O(d), improving on a O(d 1.5 ) bound from prior work.