$\ell_0$-penalized maximum likelihood for sparse directed acyclic graphs

By Sara A. van de Geer, Peter Buhlmann. 2012

82 citations recorded by the source corpus.

We consider the problem of regularized maximum likelihood estimation for the structure and parameters of a high-dimensional, sparse directed acyclic graphical (DAG) model with Gaussian distribution, or equivalently, of a Gaussian structural equation model. We show that the $\ell_0$-penalized maximum likelihood estimator of a DAG has about the same number of edges as the minimal-edge I-MAP (a DAG with minimal number of edges representing the distribution), and that it converges in Frobenius norm. We allow the number of nodes p to be much larger than sample size n but assume a sparsity condition and that any representation of the true DAG has at least a fixed proportion of its nonzero edge weights above the noise level. Our results do not rely on the faithfulness assumption nor on the restrictive strong faithfulness condition which are required for methods based on conditional independence testing such as the PC-algorithm.

Subfields: Artificial Intelligence, Statistics and Probability, Causal Inference & Discovery

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

In Causal Inference & Discovery

Citations in the corpus

Identifiability of Gaussian structural equation models with equal error variances (2012, background): “Penalized maximum likelihood estimation does not need such an assumption [van de Geer and Bühlmann, 2013] but pays a price in terms of computational complexity.”
Learning Directed Acyclic Graphs with Penalized Neighbourhood Regression (2015, methodology): “To establish normalized ℓ2-consistency, van de Geer and Bühlmann (2013) assume that ǫ is sufficiently small but does not necessarily vanish asymptotically (their Condition 3.4).”
High-dimensional consistency in score-based and hybrid structure learning (2015, background): “Interestingly, van de Geer and Bühlmann (2013) proved high-dimensional consistency of the global optimum of the 0-penalized likelihood score function without assuming strong faithfulness, but assuming a permutation beta-min condition.”
High-Dimensional Statistics with a View Toward Applications in Biology (2014, methodology): “…(Chickering, 2002): in the high-dimensional setting where p n but the true underlying DAG is sparse, consistency of the estimation has been established for both the PC-algorithm (Kalisch and Bühlmann, 2007) and the `0-penalized maximum likelihood estimator (van de Geer and Bühlmann, 2013).”
High-dimensional learning of linear causal networks via inverse covariance estimation (2013, background): “A similar result is implicitly contained under some assumptions in van de Geer and Bühlmann (2013), but we provide a more general statement and additionally quantify a regime where the errors may exhibit a certain degree of heteroscedasticity.”