A0258
Title: Mean estimation, differential privacy, and the sum of squares method
Authors: Sam Hopkins - Massachusetts Institute of Technology (United States) [presenting]
Abstract: Recent advances in computational and sample-efficient algorithms are discussed for high-dimensional parameter estimation subject to differential privacy. In particular, several recent works use semidefinite programming relaxations of data-depth problems (via the powerful sum of squares method) together with polynomial-time log-concave sampling algorithms to obtain efficiently-computable estimators for the mean of a high-dimensional distribution with information-theoretically optimal sample complexity. We will discuss these recent results and give an overview of the novel algorithmic techniques underlying them.
