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

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

Abstract: We give the first polynomial-time algorithm to estimate the mean of a d-dimensional probability distribution with bounded covariance from ~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 approximate differential privacy condition. Some interesting connections with robust statistics are uncovered along the way.No familiarity with most of the words in the title (differential privacy, sum of squares, etc.) is assumed. Based on joint work in STOC 2022 with Samuel B. Hopkins and Mahbod Majid. ArXiv preprint available at https://arxiv.org/abs/2111.12981.

Bio:  Gautam Kamath - Assistant Professor at Waterloo, David R. Cheriton School of Computer Science.  Gautam was a PhD student at MIT, affiliated with the Theory of Computing group at CSAIL. He is interested in principled tools for statistical data science, with a focus on settings that are common in settings of modern data analysis (high-dimensions, robustness, and privacy). He was a Simons-Berkeley Research Fellow at the Simons Institute for the Theory of Computing for the fall 2018 semester program on Foundations of Data Science and the spring 2019 semester program on Data Privacy: Foundations and Applications.