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

arXiv1612.03164MaRDI QIDQ6280652FDOQ6280652

Authors: Constantinos Daskalakis 

Publication date: 9 December 2016

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, $su{m}_v{H}^2(P_{vcupP{i}_v},Q_{vcupP{i}_v})$, of the square Hellinger distances between the marginals of $P$ and $Q$ on every node $v$ and its parents $P{i}_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_{mTV}(P,Q)>epsilon$ can be performed from $ildeO(|Sigma{|}^{3/4(d+1)}cdotn/epsilo{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 $ildeO(|Sigma{|}^{4.5}n/epsilo{n}^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(sqrtn/epsilo{n}^2)$, which is optimal up to constant factors.

This page was built for publication: Square Hellinger Subadditivity for Bayesian Networks and its Applications to Identity Testing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6280652)