CMI Seminar

Tuesday January 22, 2019 4:00 PM

Privately Learning High-Dimensional Distributions

Speaker: Gautam Kamath
Location: Annenberg 314

Privately Learning High-Dimensional Distributions

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: