Covariance-Aware Private Mean Estimation Without Private Covariance Estimation

A Google TechTalk, presented by Lydia Zakynthinou, 2021/11/3 Privacy in MLSeminars - ABSTRACT: We present two differentially private mean estimators for multivariate (sub)Gaussian distributions with unknown covariance. Our estimators are accurate with respect to the Mahalanobis loss and have nearly optimal sample complexity (up to logarithmic factors), which matches the one for the known covariance case. All previous estimators with the same guarantee either require strong a priori bounds on the covariance matrix or require that the number of samples grows superlinearly with the dimension of the data. Both estimators are based on simple, general approaches to designing differentially private mechanisms, but require preprocessing of the data and novel technical steps to establish privacy and sample-efficiency. Our first estimator samples a point with approximately maximum Tukey depth with respect to the dataset using the exponential mechanism, but restricted to the set of points with large Tukey depth. Our second estimator perturbs the empirical mean of the data set with noise calibrated to the empirical covariance, without releasing the covariance itself. Its sample complexity guarantees have a slightly worse dependence on the privacy parameter but hold more generally for subgaussian distributions. Joint work with Gavin Brown, Marco Gaboardi, Adam Smith, and Jonathan Ullman. Speaker Bio: Lydia Zakynthinou is a PhD student in the Khoury College of Computer Sciences at Northeastern University. She is interested in the theoretical foundations of machine learning and data privacy and their connections to statistics and information theory. She earned her ECE diploma from the National Technical University of Athens in 2015 and her MSc on Logic, Algorithms, and Theory of Computation from the University of Athens in 2017. Since Fall 2020, her research has been supported by a Facebook Fellowship.