Near-Optimal Degree Testing for Bayes Nets

2023/04/13 by Arora, Vipul, Bhattacharyya, Arnab, Canonne, Clément L. +1 · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Machine Learning (cs.LG) #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.2304.06733

Abstract

This paper considers the problem of testing the maximum in-degree of the Bayes net underlying an unknown probability distribution P over \0,1\ⁿ, given sample access to P. We show that the sample complexity of the problem is Θ(2^n/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 χ² divergence, which are of independent interest.

Cited by

• Estimation of discrete distributions with high probability under χ²-divergence

Related

• Learnability of Parameter-Bounded Bayes Nets
• Testing Bayesian Networks
• Testing Bayesian Networks
• Optimal Testing for Properties of Distributions
• Learning Bayesian Nets that Perform Well