Spring 2019

Privately Learning High-Dimensional Distributions

Friday, March 8th, 2019 12:00 pm12:30 pm

Add to Calendar


Gautam Kamath (Massachusetts Institute of Technology)

We present novel, computationally efficient, and differentially private algorithms for two fundamental high-dimensional learning problems: learning a multivariate Gaussian in Rd 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 privacy 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.