Sharp Constants in Uniformity Testing via the Huber Statistic. (arXiv:2206.10722v1 [stat.ML])

Web: http://arxiv.org/abs/2206.10722

Uniformity testing is one of the most well-studied problems in property
testing, with many known test statistics, including ones based on counting
collisions, singletons, and the empirical TV distance. It is known that the
optimal sample complexity to distinguish the uniform distribution on $m$
elements from any $\epsilon$-far distribution with $1-\delta$ probability is $n
= \Theta\left(\frac{\sqrt{m \log (1/\delta)}}{\epsilon^2} + \frac{\log
(1/\delta)}{\epsilon^2}\right)$, which is achieved by the empirical TV tester.
Yet in simulation, these theoretical analyses are misleading: in many cases, …

arxiv ml testing