The Price of Tolerance in Distribution Testing

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.