ECCC-Report TR17-132https://eccc.weizmann.ac.il/report/2017/132Comments and Revisions published for TR17-132en-usFri, 08 Sep 2017 14:00:33 +0300
Paper TR17-132
| Sharp Bounds for Generalized Uniformity Testing |
Ilias Diakonikolas,
Daniel Kane,
Alistair Stewart
https://eccc.weizmann.ac.il/report/2017/132We study the problem of {\em generalized uniformity testing}~\cite{BC17} of a discrete probability distribution: Given samples from a probability distribution $p$ over an {\em unknown} discrete domain $\mathbf{\Omega}$, we want to distinguish, with probability at least $2/3$, between the case that $p$ is uniform on some {\em subset} of $\mathbf{\Omega}$ versus $\epsilon$-far, in total variation distance, from any such uniform distribution.
We establish tight bounds on the sample complexity of generalized uniformity testing. In more detail, we present a computationally efficient tester whose sample complexity is optimal, up to constant factors,
and a matching information-theoretic lower bound. Specifically, we show that the sample complexity of generalized uniformity testing is $\Theta\left(1/(\epsilon^{4/3}\|p\|_3) + 1/(\epsilon^{2} \|p\|_2) \right)$.
Fri, 08 Sep 2017 14:00:33 +0300https://eccc.weizmann.ac.il/report/2017/132