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

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, H2(P,Q), between P and Q is upper bounded by the sum, sumv H2(P_v cup Piv, Q_v cup Piv), of the square Hellinger distances between the marginals of P and Q on every node v and its parents Piv 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 drm TV(P,Q)>ε can be performed from tildeO(|Sigma|3/4(d+1) · n/ε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 tildeO(|Sigma|4.5 n/ε2), whose dependence on n, ε is optimal up to logarithmic factors. Lastly, if P and Q are product distributions over 0,1n and Q is known, the sample complexity becomes O(√n/ε2), which is optimal up to constant factors.