Sample-Optimal Identity Testing with High Probability

By Ilias Diakonikolas, Themis Gouleakis, John Peebles, Eric Price. 2017

70 citations recorded by the source corpus.

We study the problem of testing identity against a given distribution (a.k.a. goodness-of-fit) 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< \epsilon, \delta < 1$, we wish to distinguish, with probability at least $1-\delta$, whether the distributions are identical versus $\epsilon$-far in total variation (or statistical) distance. Existing work has focused on the constant confidence regime, i.e., the case that $\delta = \Omega(1)$, for which the sample complexity of identity testing is known to be $\Theta(\sqrt{n}/\epsilon^2)$. Typical applications of distribution property testing require small values of the confidence parameter $\delta$ (which correspond to small "$p$-values" in the statistical hypothesis testing terminology). Prior work achieved arbitrarily small values of $\delta$ via black-box amplification, which multiplies the required number of samples by $\Theta(\log(1/\delta))$. We show that this upper bound is suboptimal for any $\delta = 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 \[ \Theta\left( \frac{1}{\epsilon^2}\left(\sqrt{n \log(1/\delta)} + \log(1/\delta) \right)\right) \] for any $n, \epsilon$, and $\delta$. For the special case of uniformity testing, where the given distribution is the uniform distribution $U_n$ over the domain, our new tester is surprisingly simple: to test whether $p = U_n$ versus $\mathrm{d}_{TV}(p, U_n) \geq \epsilon$, we simply threshold $\mathrm{d}_{TV}(\hat{p}, U_n)$, where $\hat{p}$ is the empirical probability distribution. We believe that our novel analysis techniques may be useful for other distribution testing problems as well.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Distributed Simulation and Distributed Inference (2018, methodology): “From the existence of uniformity testing algorithms using O ( √ k/ε 2 ) samples [Pan08, VV17, DGPP17], we obtain: Corollary 5.3.”
Inference Under Information Constraints II: Communication Constraints and Shared Randomness (2019, methodology): “in [41], [46], and the exact dependence on δ was later identified in [36], [22].”
Differentially Private Identity and Equivalence Testing of Discrete Distributions (2018, background): “It is known that q is the hardest distribution to distinguish from uniform among all distributions that are ✏-far (Paninski, 2008), without losing any constant factor (Diakonikolas et al., 2017a).”
Differentially Private Testing of Identity and Closeness of Discrete Distributions (2017, methodology): “We consider the test statistic studied by [23] which is simply the distance of the empirical distribution to the uniform distribution.”
Communication and Memory Efficient Testing of Discrete Distributions (2019, background): “…and Valiant (2014); Diakonikolas et al. (2015a); Acharya et al. (2015); Canonne et al. (2016); Diakonikolas and Kane (2016); Diakonikolas et al. (2016); Canonne et al. (2018); Goldreich (2017); Diakonikolas et al. (2017a); Batu and Canonne (2017); Diakonikolas et al. (2018); Canonne et al. (2017b).”