CMI Seminar

Tuesday January 22, 2019 4:00 PM

Privately Learning High-Dimensional Distributions

Speaker: Gautam Kamath, Simons Institute for the Theory of Computing
Location: Annenberg 314

Abstract: We present novel, computationally efficient, and differentially private algorithms for two fundamental high-dimensional learning problems: learning a multivariate Gaussian in R^d and learning a product distribution in {0,1}^d in total variation distance. The sample complexity of our algorithms nearly matches the sample complexity of the optimal non-private learners for these tasks in a wide range of parameters. Thus, our results show that private comes essentially for free for these problems, providing a counterpoint to the many negative results showing that privacy is often costly in high dimensions. Our algorithms introduce a novel technical approach to reducing the sensitivity of the estimation procedure that we call recursive private preconditioning, which may find additional applications.

Based on joint work with Jerry Li, Vikrant Singhal, and Jonathan Ullman.

Series Center for the Mathematics of Information Seminar Series

Contact: Linda Taddeo at 626-395-6704
For more information visit: