Loading [MathJax]/jax/output/CommonHTML/jax.js

Independence Testing for Bounded Degree Bayesian Networks

Part of Advances in Neural Information Processing Systems 35 (NeurIPS 2022) Main Conference Track

Bibtex Paper Supplemental

Authors

Arnab Bhattacharyya, Clément L Canonne, Qiping Yang

Abstract

We study the following independence testing problem: given access to samples from a distribution P over {0,1}n, decide whether P is a product distribution or whether it is ε-far in total variation distance from any product distribution. For arbitrary distributions, this problem requires exp(n) samples. We show in this work that if P has a sparse structure, then in fact only linearly many samples are required.Specifically, if P is Markov with respect to a Bayesian network whose underlying DAG has in-degree bounded by d, then ˜Θ(2d/2n/ε2) samples are necessary and sufficient for independence testing.