# INSPECTRE: Privately Estimating the Unseen

arXiv: https://arxiv.org/abs/1803.00008 · HTML: https://mlsanity.com/paper/1803.00008/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Feb 2018.

## Built on by (most cited first, 4 of 4)

- [Contraction of Locally Differentially Private Mechanisms](https://mlsanity.com/paper/2210.13386/) (2022)
- [Private and Communication-Efficient Algorithms for Entropy Estimation](https://mlsanity.com/paper/2305.07751/) (2023)
- [Locally differentially private estimation of nonlinear functionals of discrete distributions](https://mlsanity.com/paper/2107.03940/) (2021)
- [Anonymized Histograms in Intermediate Privacy Models](https://mlsanity.com/paper/2210.15178/) (2022)

## Abstract (arXiv)

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 α and varepsilon, the goal is to estimate f(p) up to accuracy α, while maintaining varepsilon-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.