# The Sample Complexity of Simple Binary Hypothesis Testing

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 24 references that are in the map.
- First posted on arXiv 25 Mar 2024.

## Builds on (most cited first, 6 of 6)

- [Private Hypothesis Selection](https://mlsanity.com/paper/1905.13229/) (2019)
- [Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality](https://mlsanity.com/paper/1506.07216/) (2015)
- [Inference under Information Constraints I: Lower Bounds from Chi-Square Contraction](https://mlsanity.com/paper/1812.11476/) (2018)
- [The Structure of Optimal Private Tests for Simple Hypotheses](https://mlsanity.com/paper/1811.11148/) (2018)
- [Inference under Information Constraints II: Communication Constraints and Shared Randomness](https://mlsanity.com/paper/1905.08302/) (2019)
- [Communication-constrained hypothesis testing: Optimality, robustness, and reverse data processing inequalities](https://mlsanity.com/paper/2206.02765/) (2022)

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

- [Fast Convergence of Phi-Divergence Along the Unadjusted Langevin Algorithm and Proximal Sampler](https://mlsanity.com/paper/2410.10699/) (2024)
- [Contraction of Private Quantum Channels and Private Quantum Hypothesis Testing](https://mlsanity.com/paper/2406.18651/) (2024)
- [An invitation to the sample complexity of quantum hypothesis testing](https://mlsanity.com/paper/2403.17868/) (2024)
- [Binary Hypothesis Testing for Softmax Models and Leverage Score Models](https://mlsanity.com/paper/2405.06003/) (2024)
- [Query Complexity of Classical and Quantum Channel Discrimination](https://mlsanity.com/paper/2504.12989/) (2025)
- [Bounding Neyman-Pearson Region with f-Divergences](https://mlsanity.com/paper/2505.08899/) (2025)
- [Nearly-Linear Time Private Hypothesis Selection with the Optimal Approximation Factor](https://mlsanity.com/paper/2506.01162/) (2025)
- [Tight Information Complexity of the Coin Problem in the Broadcast Model](https://mlsanity.com/paper/2608.02776/) (2026)

## Abstract (arXiv)

The sample complexity of simple binary hypothesis testing is the smallest number of i.i.d. samples required to distinguish between two distributions p and q in either: (i) the prior-free setting, with type-I error at most α and type-II error at most β; or (ii) the Bayesian setting, with Bayes error at most δ and prior distribution (π, 1-π). This problem has only been studied when α = β (prior-free) or π = 1/2 (Bayesian), and the sample complexity is known to be characterized by the Hellinger divergence between p and q, up to multiplicative constants. In this paper, we derive a formula that characterizes the sample complexity (up to multiplicative constants that are independent of p, q, and all error parameters) for: (i) all 0 ≤ α, β ≤ 1/8 in the prior-free setting; and (ii) all δ ≤ π/4 in the Bayesian setting. In particular, the formula admits equivalent expressions in terms of certain divergences from the Jensen--Shannon and Hellinger families. The main technical result concerns an f-divergence inequality between members of the Jensen--Shannon and Hellinger families, which is proved by a combination of information-theoretic tools and case-by-case analyses. We explore applications of our results to (i) robust hypothesis testing, (ii) distributed (locally-private and communication-constrained) hypothesis testing, (iii) sequential hypothesis testing, and (iv) hypothesis testing with erasures.