Machine Learning

Sharp Bounds for Generalized Uniformity Testing

Tagged: ,

This topic contains 0 replies, has 1 voice, and was last updated by  arXiv 2 months, 2 weeks ago.


  • arXiv
    5 pts

    Sharp Bounds for Generalized Uniformity Testing

    We study the problem of 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 $Thetaleft(1/(epsilon^{4/3}|p|_3) + 1/(epsilon^{2} |p|_2) right)$.

    Sharp Bounds for Generalized Uniformity Testing
    by Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
    https://arxiv.org/pdf/1709.02087v1.pdf

You must be logged in to reply to this topic.