Gautam Kamath and Mahbod Majid (University of Waterloo)

November 28, 2022

Title and Abstract

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

We give the first polynomial-time algorithm to estimate the mean of a d-variate probability distribution with bounded covariance from sim 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 sim 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 proof 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.

No familiarity with differential privacy will be assumed. Based on joint work in STOC 2022 with Samuel B. Hopkins. ArXiv preprint available at https:arxiv.orgabs2111.12981.

Bios

Gautam Kamath is an Assistant Professor at the David R. Cheriton School of Computer Science at the University of Waterloo, and a faculty affiliate at the Vector Institute. He has a B.S. in Computer Science and Electrical and Computer Engineering from Cornell University, and an M.S. and Ph.D. in Computer Science from the Massachusetts Institute of Technology. He is interested in reliable and trustworthy statistics and machine learning, including considerations such as data privacy and robustness. He was a Microsoft Research Fellow, as a part of the Simons-Berkeley Research Fellowship Program at the Simons Institute for the Theory of Computing. He is recipient of an NSERC Discovery Accelerator Supplement, and was awarded the Best Student Presentation Award at the ACM Symposium on Theory of Computing in 2012.

Mahbod Majid is a Master’s student at University of Waterloo, and an incoming PhD student at Carnegie Mellon University. He has a B.S. in Computer Engineering from Sharif University of Technology. He works on differential privacy and the sum-of-squares method. He was awarded the inaugural Waterloo CPI Cybersecurity and Privacy Excellence Graduate Scholarship.