Independence Testing for Bounded Degree Bayesian Networks
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 $\varepsilon$-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 $\tilde{\Theta}(2^{d/2}\cdot n/\varepsilon^2)$ samples are necessary and sufficient for independence testing.
Cite
Text
Bhattacharyya et al. "Independence Testing for Bounded Degree Bayesian Networks." Neural Information Processing Systems, 2022.Markdown
[Bhattacharyya et al. "Independence Testing for Bounded Degree Bayesian Networks." Neural Information Processing Systems, 2022.](https://mlanthology.org/neurips/2022/bhattacharyya2022neurips-independence/)BibTeX
@inproceedings{bhattacharyya2022neurips-independence,
title = {{Independence Testing for Bounded Degree Bayesian Networks}},
author = {Bhattacharyya, Arnab and Canonne, Clément L and Yang, Qiping},
booktitle = {Neural Information Processing Systems},
year = {2022},
url = {https://mlanthology.org/neurips/2022/bhattacharyya2022neurips-independence/}
}