Square Hellinger Subadditivity for Bayesian Networks and its Applications to Identity Testing

Abstract

We show that the square Hellinger distance between two Bayesian networks on the same directed graph, $G$, is subadditive with respect to the neighborhoods of $G$. Namely, if $P$ and $Q$ are the probability distributions defined by two Bayesian networks on the same DAG, our inequality states that the square Hellinger distance, $H^2(P,Q)$, between $P$ and $Q$ is upper bounded by the sum, ${\sum }_v{H}^2(P_{\{v\}\cup {\Pi }_v},Q_{\{v\}\cup {\Pi }_v})$, of the square Hellinger distances between the marginals of $P$ and $Q$ on every node $v$ and its parents ${\Pi }_v$ in the DAG. Importantly, our bound does not involve the conditionals but the marginals of $P$ and $Q$. We derive a similar inequality for more general Markov Random Fields. As an application of our inequality, we show that distinguishing whether two Bayesian networks $P$ and $Q$ on the same (but potentially unknown) DAG satisfy $P=Q$ vs $d_{\mathrm{TV}}(P,Q)>\epsilon$ can be performed from $\tilde{O}(|\Sigma {|}^{3/4(d+1)}\cdot n/{\epsilon }^2)$ samples, where $d$ is the maximum in-degree of the DAG and $\Sigma$ the domain of each variable of the Bayesian networks. If $P$ and $Q$ are defined on potentially different and potentially unknown trees, the sample complexity becomes $\tilde{O}(|\Sigma {|}^{4.5}n/{\epsilon }^2)$, whose dependence on $n,\epsilon$ is optimal up to logarithmic factors. Lastly, if $P$ and $Q$ are product distributions over $\{0,1{\}}^n$ and $Q$ is known, the sample complexity becomes $O(\sqrt{n}/{\epsilon }^2)$, which is optimal up to constant factors.

References in corpus (2)

• High-dimensional structure estimation in Ising models: Local separation criterion
• Faster and Sample Near-Optimal Algorithms for Proper Learning Mixtures of Gaussians

Cited by in corpus (10)

• Learning and Testing Causal Models with Interventions
• Property Testing of Joint Distributions using Conditional Samples
• Private Identity Testing for High-Dimensional Distributions
• Near-Optimal Learning of Tree-Structured Distributions by Chow-Liu
• Sharp Bounds for Generalized Uniformity Testing
• GANs with Conditional Independence Graphs: On Subadditivity of Probability Divergences
• Testing Product Distributions: A Closer Look
• The Sample Complexity of Robust Covariance Testing
• On Distribution Testing in the Conditional Sampling Model
• Perturbation Analysis of Markov Chain Monte Carlo for Graphical Models