## Independence Testing for Bounded Degree Bayesian Networks

### Arnab Bhattacharyya · Clément L Canonne · Qiping Yang

##### Hall J #818

Keywords: [ distribution testing ] [ bayesian network ] [ Probabilistic Graphical Model ]

[ Abstract ]
[ [ [ [
Tue 29 Nov 2 p.m. PST — 4 p.m. PST

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.

Chat is not available.