Robust and Differentially Private Mean Estimation

When releasing database statistics on a collection of entries from individuals, we would ideally like to make it impossible to reverse-engineer each individual's potentially sensitive information. Privacy-preserving techniques add just enough randomness tailored to the statistical task to guarantee protection. At the same time, it is becoming increasingly common to apply such techniques to databases collected from multiple sources, not all of which can be trusted. Emerging data access frameworks, such as federated analyses across users' devices or data silos [51], make it easier to temper with this collected dataset, leaving private statistical analyses vulnerable to a malicious corruption of a fraction of the data. Differential privacy has emerged as a widely accepted de facto measure of privacy, which is now a standard in releasing the statistics of the U.S. Census data [2] statistics and also deployed in real-world commercial systems [76, 41, 42]. A statistical analysis is said to be differentially private if the likelihood of the (randomized) outcome does not change significantly when a single entry is replaced by another arbitrary entry (formally defined in §1.1). This provides a strong privacy guarantee: even a powerful adversary who knows all the other entries in the database cannot confidently identify whether a particular individual is participating in the database based on the outcome of the analysis, providing plausible deniability, central to protecting an individual's privacy. Despite more than a decade of literature focused in designing private mechanisms for various statistical and learning tasks, only recently have some of the most fundamental questions been resolved. In this paper, we focus on one of the most canonical problems in statistics: estimating the mean of a distribution from i.i.d.