# Optimal Identity Testing with High Probability

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Aug 2017.

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

- [The Price of Tolerance in Distribution Testing](https://mlsanity.com/paper/2106.13414/) (2021)
- [Robust Testing and Estimation under Manipulation Attacks](https://mlsanity.com/paper/2104.10740/) (2021)
- [Near-Optimal Bounds for Testing Histogram Distributions](https://mlsanity.com/paper/2207.06596/) (2022)
- [Replicable Uniformity Testing](https://mlsanity.com/paper/2410.10892/) (2024)
- [Gaussian Mean Testing Made Simple](https://mlsanity.com/paper/2210.13706/) (2022)
- [Sharp Noisy Binary Search with Monotonic Probabilities](https://mlsanity.com/paper/2311.00840/) (2023)
- [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)
- [Sharp Constants in Uniformity Testing via the Huber Statistic](https://mlsanity.com/paper/2206.10722/) (2022)
- [Statistical Inference with Limited Memory: A Survey](https://mlsanity.com/paper/2312.15225/) (2023)
- [Instance-Optimal Uniformity Testing and Tracking](https://mlsanity.com/paper/2508.02637/) (2025)
- [Uniformity Testing in the Shuffle Model: Simpler, Better, Faster](https://mlsanity.com/paper/2108.08987/) (2021)
- [Reframing Data Value for Large Language Models Through the Lens of Plausibility](https://mlsanity.com/paper/2409.00284/) (2024)
- [New Statistical and Computational Results for Learning Junta Distributions](https://mlsanity.com/paper/2505.05819/) (2025)
- [Dimension Agnostic Testing of Survey Data Credibility through the Lens of Regression](https://mlsanity.com/paper/2508.20616/) (2025)
- [Relatively Smart: A New Approach for Instance-Optimal Learning](https://mlsanity.com/paper/2603.01346/) (2026)
- [Differentially Private Verification of Distribution Properties](https://mlsanity.com/paper/2604.10819/) (2026)
- [Entropy Equivalence Testing](https://mlsanity.com/paper/2605.23225/) (2026)
- [Bandit Multiclass PAC Learning: Corrected Lower Bounds, Exact Families, and a Confidence Direct-Sum Phenomenon](https://mlsanity.com/paper/2609.29694/) (2026)

## Abstract (arXiv)

We study the problem of testing identity against a given distribution with a focus on the high confidence regime. More precisely, given samples from an unknown distribution p over n elements, an explicitly given distribution q, and parameters 0< ε, δ < 1, we wish to distinguish, em with probability at least 1-δ, whether the distributions are identical versus varepsilon-far in total variation distance. Most prior work focused on the case that δ = Omega(1), for which the sample complexity of identity testing is known to be Theta(√n/ε2). Given such an algorithm, one can achieve arbitrarily small values of δ via black-box amplification, which multiplies the required number of samples by Theta(log(1/δ)). We show that black-box amplification is suboptimal for any δ = o(1), and give a new identity tester that achieves the optimal sample complexity. Our new upper and lower bounds show that the optimal sample complexity of identity testing is [ Thetaleft( frac1ε2left(√n log(1/δ) + log(1/δ) right)right) ] for any n, varepsilon, and δ. For the special case of uniformity testing, where the given distribution is the uniform distribution Un over the domain, our new tester is surprisingly simple: to test whether p = Un versus dmathrm TV(p, Un) ≥ varepsilon, we simply threshold dmathrm TV(widehatp, Un), where widehatp is the empirical probability distribution. The fact that this simple "plug-in" estimator is sample-optimal is surprising, even in the constant δ case. Indeed, it was believed that such a tester would not attain sublinear sample complexity even for constant values of varepsilon and δ.