Efficient mean estimation with pure differential privacy via a sum-of-squares exponential mechanism
Samuel B. Hopkins, Gautam Kamath, Mahbod Majid · 2022
We give the first polynomial-time algorithm to estimate the mean of a d-variate probability distribution with bounded covariance from Õ(d) independent samples subject to pure differential privacy. Prior algorithms for this problem either incur exponential running time, require Ω(d1.5) samples, or satisfy only the weaker concentrated or approximate differential privacy conditions. In particular, all prior polynomial-time algorithms require d1+Ω(1) samples to guarantee small privacy loss with “cryptographically” high probability, 1−2−dΩ(1), while our algorithm retains Õ(d) sample complexity even in this stringent setting.