INSPECTRE: Privately Estimating the Unseen

By Jayadev Acharya, Gautam Kamath, Ziteng Sun, Huanyu Zhang. 2018

23 citations recorded by the source corpus.

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

Subfields: Artificial Intelligence, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

Citations in the corpus

The Power of the Hybrid Model for Mean Estimation (2018, background): “However, DP mean estimation of distributions under both the TCM and LM has been studied since the models’ introductions [17, 21, 56], and continues to be actively studied to this day [2, 15, 18, 20, 22, 28, 29, 32, 37, 39–42].”
The structure of optimal private tests for simple hypotheses (2018, neutral): “Recently, [2] designed nearly optimal algorithms for estimating properties like support size and entropy.”
Private Mean Estimation of Heavy-Tailed Distributions (2020, background): “Acharya, Kamath, Sun, and Zhang [AKSZ18] focus on estimating properties of a distribution, such as the entropy or support size.”
Differentially private anonymized histograms (2019, background): “Recently, [26] proposed algorithms to estimate support size, support coverage and entropy with differential privacy.”
Differentially Private Testing of Identity and Closeness of Discrete Distributions (2017, methodology): “[5] uses our coupling argument to prove lower bounds for differentially private property estimation problems.”
Private Hypothesis Selection (2019, background): “Reference [33] focuses on estimating properties of a distribution, rather than the distribution itself.”
Privately Learning High-Dimensional Distributions (2018, background): “Recently, Acharya et al. (2018b) and Aliakbarpour et al. (2018) have given essentially optimal algorithms for goodness-of-fit and closeness testing of arbitrary distributions.”
Differentially Private Algorithms for Learning Mixtures of Separated Gaussians (2019, background): “[1] focuses on estimating properties of a distribution, rather than the distribution itself.”
Differentially Private Assouad, Fano, and Le Cam (2020, methodology): “Acharya et al. (2018b) developed a result similar to Theorem 1, which is used to establish sample complexity lower bounds for differentially private uniformity testing under total variation distance (Acharya et al.”