Skip to yearly menu bar Skip to main content


Poster

Entropy testing and its application to testing Bayesian networks

Clément L Canonne · Qiping Yang

West Ballroom A-D #5707
[ ]
[ Paper [ Slides [ OpenReview
Wed 11 Dec 4:30 p.m. PST — 7:30 p.m. PST

Abstract: This paper studies the problem of \emph{entropy identity testing}: given sample access to a distribution p and a fully described distribution q (both are discrete distributions over the support of size k), and the promise that either p=q or |H(p)H(q)|ε, where H() 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 Θ~(k/ε+1/ε2) for this problem, and show how to apply it to the problem of identity testing for in-degree-d n-dimensional Bayesian networks, obtaining an upper bound of O~(2d/2n3/2/ε2+n2/ε4). This improves on the sample complexity bound of O~(2d/2n2/ε4) from Canonne, Diakonikolas, Kane, and Stewart (2020), which required an additional assumption on the structure of the (unknown) Bayesian network.

Chat is not available.