Instance-Optimal Differentially Private Estimation

While the primary goal of statistical inference is to reveal properties of a population, many statistical estimators also reveal a significant amount of information about their sample, and this becomes a serious problem when the sample contains sensitive private information about individuals. As a response, differential privacy (Dwork et al., 2006) has emerged as a strong formal criterion for a statistical procedure to protect individual privacy. Differentially private algorithms are deployed in a variety of settings, from the public data products for the 2020 US decennial census to Google's keyboard prediction models (McMahan and Thakurta, 2022) and Apple device analytics (Apple Differential Privacy Team, 2017). Differential privacy is a constraint on an estimator that requires the distribution of the estimator's outputs to be insensitive to changing a single individual's data, and it offers a strong semantic guarantee that no attacker can infer much more about any individual than they could have inferred had that individual's data never been collected (Kasiviswanathan and Smith, 2008). This semantic guarantee does not rely on any assumptions about the adversary's background knowledge and capabilities. In contrast, alternative approaches to protecting privacy have often been undermined by underestimating the abilities of the attacker. Although differential privacy is a constraint that significantly limits inference with small sample sizes, most statistical tasks are compatible with differential privacy given a large enough sample. There is now a large body of work on differentially private estimation, which includes minimax optimal differentially private estimators for many estimation tasks (e.g.