Daniel Alabi, University of Illinois, Urbana-Champaign

Abstract

In this talk, we discuss the problem of learning a high-dimensional Gaussian subject to privacy and robustness constraints. We give efficient algorithms for privately estimating a Gaussian distribution in both pure and approximate differential privacy (DP) models with optimal dependence on the dimension in the sample complexity. We prove a new lower bound on differentially private covariance estimation to show that our sample complexity bound is also tight. Prior to our work, all DP algorithms incurred a super-quadratic sample cost, were not outlier-robust or required super-polynomial time. Our DP algorithms are based on a substantial upgrade of the method of stabilizing convex relaxations introduced in previous work and involve a novel mechanism for privately releasing covariance matrices.

See: https://theory.cs.rutgers.edu/theory_seminar