Poster
Entropy testing and its application to testing Bayesian networks
Clément L Canonne · Qiping Yang
West Ballroom A-D #5707
Abstract:
This paper studies the problem of \emph{entropy identity testing}: given sample access to a distribution and a fully described distribution (both are discrete distributions over the support of size ), and the promise that either or , where denotes the Shannon entropy, a tester needs to distinguish between the two cases with high probability. We establish a near-optimal sample complexity bound of ) for this problem, and show how to apply it to the problem of identity testing for in-degree- -dimensional Bayesian networks, obtaining an upper bound of . This improves on the sample complexity bound of from Canonne, Diakonikolas, Kane, and Stewart (2020), which required an additional assumption on the structure of the (unknown) Bayesian network.
Chat is not available.