# Priv'IT: Private and Sample Efficient Identity Testing

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Mar 2017.

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

- [Private High-Dimensional Hypothesis Testing](https://mlsanity.com/paper/2203.01537/) (2022)
- [The Test of Tests: A Framework For Differentially Private Hypothesis Testing](https://mlsanity.com/paper/2302.04260/) (2023)
- [Robust Kernel Hypothesis Testing under Data Corruption](https://mlsanity.com/paper/2405.19912/) (2024)
- [On Differentially Private U Statistics](https://mlsanity.com/paper/2407.04945/) (2024)
- [Optimal Algorithms for Augmented Testing of Discrete Distributions](https://mlsanity.com/paper/2412.00974/) (2024)
- [Replicable Distribution Testing](https://mlsanity.com/paper/2507.02814/) (2025)
- [Uniformity Testing in the Shuffle Model: Simpler, Better, Faster](https://mlsanity.com/paper/2108.08987/) (2021)
- [The power of private likelihood-ratio tests for goodness-of-fit in frequency tables](https://mlsanity.com/paper/2109.09630/) (2021)
- [Anonymized Histograms in Intermediate Privacy Models](https://mlsanity.com/paper/2210.15178/) (2022)
- [Nearly-Linear Time Private Hypothesis Selection with the Optimal Approximation Factor](https://mlsanity.com/paper/2506.01162/) (2025)
- [One-Shot Private Confidence Regions via Resampling](https://mlsanity.com/paper/2610.08460/) (2026)

## Abstract (arXiv)

We develop differentially private hypothesis testing methods for the small sample regime. Given a sample cal D from a categorical distribution p over some domain Sigma, an explicitly described distribution q over Sigma, some privacy parameter varepsilon, accuracy parameter α, and requirements βrm I and βrm II for the type I and type II errors of our test, the goal is to distinguish between p=q and d_rmTV(p,q) ≥ α. We provide theoretical bounds for the sample size |cal D| so that our method both satisfies (varepsilon,0)-differential privacy, and guarantees βrm I and βrm II type I and type II errors. We show that differential privacy may come for free in some regimes of parameters, and we always beat the sample complexity resulting from running the chi2-test with noisy counts, or standard approaches such as repetition for endowing non-private chi2-style statistics with differential privacy guarantees. We experimentally compare the sample complexity of our method to that of recently proposed methods for private hypothesis testing.