Near-Optimal Degree Testing for Bayes Nets
Vipul Arora, Arnab Bhattacharyya, Clément L. Canonne, Joy Qiping Yang · 2023
This paper considers the problem of testing the maximum in-degree of the Bayes net underlying an unknown probability distribution P over {0, 1}n, given sample access toP. We show that the sample complexity of the problem is Θ(2n/2/ε2). Our algorithm relies on a testing-by-learning framework, previously used to obtain sample-optimal testers; in order to apply this framework, we develop new algorithms for "near-proper" learning of Bayes nets, and high-probability learning under χ2divergence, which are of independent interest.1