Can I read Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism on EtoBox?

Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism by Hopkins, Samuel B.; Kamath, Gautam; Majid, Mahbod is a scholarly article available to read on EtoBox.

What is Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism about?

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 to pure differential privacy. Prior algorithms for this problem either incur exponential running time, require $\Omega(d^{1.5})$ samples, or satisfy only the weaker concentrated or approximate differential privacy conditions. In particular, all prior polynomial-time algorithms require $d^{1+\Omega(1)}$ samples to guarantee small privacy loss with "cryptographically" high probability, $1-2^{-d^{\Omega(1)}}$, while our algorithm retains $\tilde{O}(d)$ sample complexity even in this stringent setting. Our main technique is a new approach to use the powerful Sum of Squares method (SoS) to design differentially private algorithms. SoS proofs to algorithms is a key theme in numerous recent works in high-dimensional algorithmic statistics -- estimators which apparently require exponential running time but whose analysis can be captured by low-degree Sum of Squares proofs can be automatically turned into polynomial-time algorithms with the same provable guarantees. We demonstrate a similar proofs to private algori

Author

Hopkins, Samuel B.; Kamath, Gautam; Majid, Mahbod

Published

2021

Language

EN