${\ell }_0$-penalized maximum likelihood for sparse directed acyclic graphs

Abstract

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.

Published in at http://dx.doi.org/10.1214/13-AOS1085 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (5)

• Estimating high-dimensional intervention effects from observational data
• A simple approach for finding the globally optimal Bayesian network structure
• Identifiability of Gaussian structural equation models with equal error variances
• Geometry of the faithfulness assumption in causal inference
• Strong Faithfulness and Uniform Consistency in Causal Inference

Cited by in corpus (42)

• CAM: Causal additive models, high-dimensional order search and penalized regression
• Identifiability of Gaussian structural equation models with equal error variances
• Geometry of the faithfulness assumption in causal inference
• Valid Post-Selection and Post-Regularization Inference: An Elementary, General Approach
• High-dimensional learning of linear causal networks via inverse covariance estimation
• Confidence sets in sparse regression
• On the Role of Sparsity and DAG Constraints for Learning Linear DAGs
• Learning Large-Scale Bayesian Networks with the sparsebn Package
• Learning Directed Acyclic Graphs with Penalized Neighbourhood Regression
• CASTLE: Regularization via Auxiliary Causal Graph Discovery
• Penalized Estimation of Directed Acyclic Graphs From Discrete Data
• Gradient-Based Neural DAG Learning
• Direct Estimation of Differences in Causal Graphs
• Ordering-Based Causal Structure Learning in the Presence of Latent Variables
• Comparative Benchmarking of Causal Discovery Techniques
• A review of Gaussian Markov models for conditional independence
• High-Dimensional Joint Estimation of Multiple Directed Gaussian Graphical Models
• Posterior Graph Selection and Estimation Consistency for High-dimensional Bayesian DAG Models
• A polynomial-time algorithm for learning nonparametric causal graphs
• Structure Learning for Cyclic Linear Causal Models
• Complexity analysis of Bayesian learning of high-dimensional DAG models and their equivalence classes
• DYNOTEARS: Structure Learning from Time-Series Data
• Identifiability Assumptions and Algorithm for Directed Graphical Models with Feedback
• Marginal integration for nonparametric causal inference
• Structure learning in polynomial time: Greedy algorithms, Bregman information, and exponential families
• Multi-task Learning of Order-Consistent Causal Graphs
• Sparse Cholesky covariance parametrization for recovering latent structure in ordered data
• A Bregman Method for Structure Learning on Sparse Directed Acyclic Graphs
• Estimation of Gaussian directed acyclic graphs using partial ordering information with an application to dairy cattle data
• Combinatorial and algebraic perspectives on the marginal independence structure of Bayesian networks
• The neighborhood lattice for encoding partial correlations in a Hilbert space
• PenPC: A Two-step Approach to Estimate the Skeletons of High Dimensional Directed Acyclic Graphs
• Learning Gaussian Graphical Models via Multiplicative Weights
• A permutation-based Bayesian approach for inverse covariance estimation
• Learning Bayesian Networks through Birkhoff Polytope: A Relaxation Method
• Temporal Point Process Graphical Models
• Estimation Rates for Sparse Linear Cyclic Causal Models
• Corrected score methods for estimating Bayesian networks with error-prone nodes
• On the uniform convergence of empirical norms and inner products, with application to causal inference
• Why did the distribution change?
• Testing Mediation Effects Using Logic of Boolean Matrices
• Testing Directed Acyclic Graph via Structural, Supervised and Generative Adversarial Learning