Learning discrete Bayesian networks in polynomial time and sample
  complexity
  In this paper, we study the problem of structure learning for Bayesian
networks in which nodes take discrete values. The problem is NP-hard in general
but we show that under certain conditions we can recover the true structure of
a Bayesian network with sufficient number of samples. We develop a mathematical
model which does not assume any specific conditional probability distributions
for the nodes. We use a primal-dual witness construction to prove that, under
some technical conditions on the interaction between node pairs, we can do
exact recovery of the parents and children of a node by performing group
l_12-regularized multivariate regression. Thus, we recover the true Bayesian
network structure. If degree of a node is bounded then the sample complexity of
our proposed approach grows logarithmically with respect to the number of nodes
in the Bayesian network. Furthermore, our method runs in polynomial time.
