# The Price of Tolerance in Distribution Testing

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 50 references that are in the map.
- First posted on arXiv 25 Jun 2021.

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

- [Optimal Algorithms for Testing Closeness of Discrete Distributions](https://mlsanity.com/paper/1308.3946/) (2013)
- [Optimal Testing for Properties of Distributions](https://mlsanity.com/paper/1507.05952/) (2015)
- [Testing Identity of Structured Distributions](https://mlsanity.com/paper/1410.2266/) (2014)
- [Optimal Identity Testing with High Probability](https://mlsanity.com/paper/1708.02728/) (2017)
- [Collision-based Testers are Optimal for Uniformity and Closeness](https://mlsanity.com/paper/1611.03579/) (2016)
- [Optimal Testing of Discrete Distributions with High Probability](https://mlsanity.com/paper/2009.06540/) (2020)
- [Which Distribution Distances are Sublinearly Testable?](https://mlsanity.com/paper/1708.00002/) (2017)
- [Hypothesis Testing for High-Dimensional Multinomials: A Selective Review](https://mlsanity.com/paper/1712.06120/) (2017)
- [Testing Closeness With Unequal Sized Samples](https://mlsanity.com/paper/1504.04599/) (2015)

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

- [Tolerant Algorithms for Learning with Arbitrary Covariate Shift](https://mlsanity.com/paper/2406.02742/) (2024)
- [PAC Verification of Statistical Algorithms](https://mlsanity.com/paper/2211.17096/) (2022)
- [Testing Closeness of Multivariate Distributions via Ramsey Theory](https://mlsanity.com/paper/2311.13154/) (2023)
- [Replicable Uniformity Testing](https://mlsanity.com/paper/2410.10892/) (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)
- [Mathematical Framework for Online Social Media Auditing](https://mlsanity.com/paper/2209.05550/) (2022)
- [Zero-Shot Attribution for Large Language Models: A Distribution Testing Approach](https://mlsanity.com/paper/2506.20197/) (2025)
- [Reframing Data Value for Large Language Models Through the Lens of Plausibility](https://mlsanity.com/paper/2409.00284/) (2024)
- [Are Two Datasets Close Enough With Statistical Significance? A Kernel Distributional Closeness Testing Approach](https://mlsanity.com/paper/2507.12843/) (2025)
- [Dimension Agnostic Testing of Survey Data Credibility through the Lens of Regression](https://mlsanity.com/paper/2508.20616/) (2025)
- [Differentially Private Verification of Distribution Properties](https://mlsanity.com/paper/2604.10819/) (2026)
- [When Are Trade-Off Functions Testable from Finite Samples?](https://mlsanity.com/paper/2605.10774/) (2026)
- [From Transformers to Weighted Automata: Towards the Verification of Large Language Models](https://mlsanity.com/paper/2610.04569/) (2026)

## Abstract (arXiv)

We revisit the problem of tolerant distribution testing. That is, given samples from an unknown distribution p over 1, dots, n, is it varepsilon1-close to or varepsilon2-far from a reference distribution q (in total variation distance)? Despite significant interest over the past decade, this problem is well understood only in the extreme cases. In the noiseless setting (i.e., varepsilon1 = 0) the sample complexity is Theta(√n), strongly sublinear in the domain size. At the other end of the spectrum, when varepsilon1 = varepsilon2/2, the sample complexity jumps to the barely sublinear Theta(n/log n). However, very little is known about the intermediate regime. We fully characterize the price of tolerance in distribution testing as a function of n, varepsilon1, varepsilon2, up to a single log n factor. Specifically, we show the sample complexity to be [tilde Thetaleft(frac√nvarepsilon22 + fracnlog n · max leftfracvarepsilon1varepsilon22,left(fracvarepsilon1varepsilon22right)!!2rightright),] providing a smooth tradeoff between the two previously known cases. We also provide a similar characterization for the problem of tolerant equivalence testing, where both p and q are unknown. Surprisingly, in both cases, the main quantity dictating the sample complexity is the ratio varepsilon1/varepsilon22, and not the more intuitive varepsilon1/varepsilon2. Of particular technical interest is our lower bound framework, which involves novel approximation-theoretic tools required to handle the asymmetry between varepsilon1 and varepsilon2, a challenge absent from previous works.