Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism

Samuel B. Hopkins, Gautam Kamath, Mahbod Majid

We give the first polynomial-time algorithm to estimate the mean of a $d$-variate probability distribution with bounded covariance from $\tilde{O}(d)$ independent samples subject t…