Globally optimal score-based learning of directed acyclic graphs in high-dimensions

We prove that (s log p) samples suffice to learn a sparse Gaussian directed acyclic graph (DAG) from data, where s is the maximum Markov blanket size.