INSPECTRE: Privately Estimating the Unseen

Abstract

We develop differentially private methods for estimating various distributional properties. Given a sample from a discrete distribution $p$, some functional $f$, and accuracy and privacy parameters $\alpha$ and $\epsilon$, the goal is to estimate $f(p)$ up to accuracy $\alpha$, while maintaining $\epsilon$-differential privacy of the sample. We prove almost-tight bounds on the sample size required for this problem for several functionals of interest, including support size, support coverage, and entropy. We show that the cost of privacy is negligible in a variety of settings, both theoretically and experimentally. Our methods are based on a sensitivity analysis of several state-of-the-art methods for estimating these properties with sublinear sample complexities.

References in corpus (8)

• Scalable Privacy-Preserving Data Sharing Methodology for Genome-Wide Association Studies
• The Noisy Power Method: A Meta Algorithm with Applications
• Optimal Testing for Properties of Distributions
• Revisiting Differentially Private Hypothesis Tests for Categorical Data
• Differentially Private Testing of Identity and Closeness of Discrete Distributions
• Local Private Hypothesis Testing: Chi-Square Tests
• A New Class of Private Chi-Square Tests
• Minimax Optimal Estimators for Additive Scalar Functionals of Discrete Distributions