# The Structure of Optimal Private Tests for Simple Hypotheses

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

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Nov 2018.

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

- [Private High-Dimensional Hypothesis Testing](https://mlsanity.com/paper/2203.01537/) (2022)
- [Communication-constrained hypothesis testing: Optimality, robustness, and reverse data processing inequalities](https://mlsanity.com/paper/2206.02765/) (2022)
- [Simple Binary Hypothesis Testing under Local Differential Privacy and Communication Constraints](https://mlsanity.com/paper/2301.03566/) (2023)
- [The Test of Tests: A Framework For Differentially Private Hypothesis Testing](https://mlsanity.com/paper/2302.04260/) (2023)
- [Contraction of Locally Differentially Private Mechanisms](https://mlsanity.com/paper/2210.13386/) (2022)
- [The Sample Complexity of Simple Binary Hypothesis Testing](https://mlsanity.com/paper/2403.16981/) (2024)
- [Instance-Optimal Differentially Private Estimation](https://mlsanity.com/paper/2210.15819/) (2022)
- [Contraction of Private Quantum Channels and Private Quantum Hypothesis Testing](https://mlsanity.com/paper/2406.18651/) (2024)
- [Nonparametric extensions of randomized response for private confidence sets](https://mlsanity.com/paper/2202.08728/) (2022)
- [Federated Nonparametric Hypothesis Testing with Differential Privacy Constraints: Optimal Rates and Adaptive Tests](https://mlsanity.com/paper/2406.06749/) (2024)
- [An invitation to the sample complexity of quantum hypothesis testing](https://mlsanity.com/paper/2403.17868/) (2024)
- [Data Structures for Density Estimation](https://mlsanity.com/paper/2306.11312/) (2023)
- [Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivity](https://mlsanity.com/paper/2312.05645/) (2023)
- [Private Sequential Hypothesis Testing for Statisticians: Privacy, Error Rates, and Sample Size](https://mlsanity.com/paper/2204.04597/) (2022)
- [Why Train More? Effective and Efficient Membership Inference via Memorization](https://mlsanity.com/paper/2310.08015/) (2023)
- [Statistical-Computational Trade-offs for Density Estimation](https://mlsanity.com/paper/2410.23087/) (2024)
- [Optimal Algorithms for Augmented Testing of Discrete Distributions](https://mlsanity.com/paper/2412.00974/) (2024)
- [Optimal Differentially Private Ranking from Pairwise Comparisons](https://mlsanity.com/paper/2507.09388/) (2025)
- [Fiducial Matching: Differentially Private Inference for Categorical Data](https://mlsanity.com/paper/2507.11762/) (2025)
- [DP-SPRT: Differentially Private Sequential Probability Ratio Tests](https://mlsanity.com/paper/2508.06377/) (2025)
- [Optimal Rates for Differentially Private Hypothesis Testing with E-values](https://mlsanity.com/paper/2605.28952/) (2026)
- [The power of private likelihood-ratio tests for goodness-of-fit in frequency tables](https://mlsanity.com/paper/2109.09630/) (2021)
- [Nearly-Linear Time Private Hypothesis Selection with the Optimal Approximation Factor](https://mlsanity.com/paper/2506.01162/) (2025)
- [Near-Optimal Private Tests for Simple and MLR Hypotheses](https://mlsanity.com/paper/2601.21959/) (2026)
- [Privacy-Utility Tradeoffs in Quantum Information Processing](https://mlsanity.com/paper/2602.10510/) (2026)
- [Locally Private Parametric Methods for Change-Point Detection](https://mlsanity.com/paper/2602.13619/) (2026)

## Abstract (arXiv)

Hypothesis testing plays a central role in statistical inference, and is used in many settings where privacy concerns are paramount. This work answers a basic question about privately testing simple hypotheses: given two distributions P and Q, and a privacy level varepsilon, how many i.i.d. samples are needed to distinguish P from Q subject to varepsilon-differential privacy, and what sort of tests have optimal sample complexity? Specifically, we characterize this sample complexity up to constant factors in terms of the structure of P and Q and the privacy level varepsilon, and show that this sample complexity is achieved by a certain randomized and clamped variant of the log-likelihood ratio test. Our result is an analogue of the classical Neyman-Pearson lemma in the setting of private hypothesis testing. We also give an application of our result to the private change-point detection. Our characterization applies more generally to hypothesis tests satisfying essentially any notion of algorithmic stability, which is known to imply strong generalization bounds in adaptive data analysis, and thus our results have applications even when privacy is not a primary concern.