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

Abstract

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 algorithms phenomenon: instances of the workhorse exponential mechanism which apparently require exponential time but which can be analyzed with low-degree SoS proofs can be automatically turned into polynomial-time differentially private algorithms. We prove a meta-theorem capturing this phenomenon, which we expect to be of broad use in private algorithm design. Our techniques also draw new connections between differentially private and robust statistics in high dimensions. In particular, viewed through our proofs-to-private-algorithms lens, several well-studied SoS proofs from recent works in algorithmic robust statistics directly yield key components of our differentially private mean estimation algorithm.

66 pages, STOC 2022

References in corpus (11)

• Privacy and Statistical Risk: Formalisms and Minimax Bounds
• Better Agnostic Clustering Via Relaxed Tensor Norms
• Differentially Private Confidence Intervals
• A Primer on Private Statistics
• A Unified Approach to Robust Mean Estimation
• Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Data
• Robust and Differentially Private Mean Estimation
• Differential privacy and robust statistics in high dimensions
• A Private and Computationally-Efficient Estimator for Unbounded Gaussians
• Optimal Private Median Estimation under Minimal Distributional Assumptions
• Private and polynomial time algorithms for learning Gaussians and beyond