Optimal estimation of Gaussian DAG models
  We study the optimal sample complexity of learning a Gaussian directed
acyclic graph (DAG) from observational data. Our main results establish the
minimax optimal sample complexity for learning the structure of a linear
Gaussian DAG model in two settings of interest: 1) Under equal variances
without knowledge of the true ordering, and 2) For general linear models given
knowledge of the ordering. In both cases the sample complexity is $n\asymp
q\log(d/q)$, where $q$ is the maximum number of parents and $d$ is the number
of nodes. We further make comparisons with the classical problem of learning
(undirected) Gaussian graphical models, showing that under the equal variance
assumption, these two problems share the same optimal sample complexity. In
other words, at least for Gaussian models with equal error variances, learning
a directed graphical model is statistically no more difficult than learning an
undirected graphical model. Our results also extend to more general
identification assumptions as well as subgaussian errors.
