High-dimensional learning of linear causal networks via inverse covariance estimation
arXiv:1311.3492
Abstract
We establish a new framework for statistical estimation of directed acyclic graphs (DAGs) when data are generated from a linear, possibly non-Gaussian structural equation model. Our framework consists of two parts: (1) inferring the moralized graph from the support of the inverse covariance matrix; and (2) selecting the best-scoring graph amongst DAGs that are consistent with the moralized graph. We show that when the error variances are known or estimated to close enough precision, the true DAG is the unique minimizer of the score computed using the reweighted squared l_2-loss. Our population-level results have implications for the identifiability of linear SEMs when the error covariances are specified up to a constant multiple. On the statistical side, we establish rigorous conditions for high-dimensional consistency of our two-part algorithm, defined in terms of a "gap" between the true DAG and the next best candidate. Finally, we demonstrate that dynamic programming may be used to select the optimal DAG in linear time when the treewidth of the moralized graph is bounded.
arXiv comment41 pages, 7 figures
References in corpus (7)
- High-dimensional regression with noisy and missing data: Provable guarantees with nonconvexity
- A Transformational Characterization of Equivalent Bayesian Network Structures
- A simple approach for finding the globally optimal Bayesian network structure
- CAM: Causal additive models, high-dimensional order search and penalized regression
- Identifiability of Gaussian structural equation models with equal error variances
- -penalized maximum likelihood for sparse directed acyclic graphs
- Score-based Causal Learning in Additive Noise Models
Cited by in corpus (36)
- CAM: Causal additive models, high-dimensional order search and penalized regression
- On Causal Discovery with Equal Variance Assumption
- Learning Directed Acyclic Graphs with Penalized Neighbourhood Regression
- CASTLE: Regularization via Auxiliary Causal Graph Discovery
- Causal Fourier Analysis on Directed Acyclic Graphs and Posets
- Learning Sparse Nonparametric DAGs
- Identifying Best Interventions through Online Importance Sampling
- Gradient-Based Neural DAG Learning
- Estimating causal structure using conditional DAG models
- Learning Quadratic Variance Function (QVF) DAG models via OverDispersion Scoring (ODS)
- The Reduced PC-Algorithm: Improved Causal Structure Learning in Large Random Networks
- Beware of the Simulated DAG! Causal Discovery Benchmarks May Be Easy To Game
- A review of Gaussian Markov models for conditional independence
- High-Dimensional Joint Estimation of Multiple Directed Gaussian Graphical Models
- Causal Discovery with Unobserved Confounding and non-Gaussian Data
- Consistent Second-Order Conic Integer Programming for Learning Bayesian Networks
- Unsuitability of NOTEARS for Causal Graph Discovery
- A polynomial-time algorithm for learning nonparametric causal graphs
- Marginal integration for nonparametric causal inference
- Efficient Intervention Design for Causal Discovery with Latents
- Nonparametric causal structure learning in high dimensions
- Structure learning in polynomial time: Greedy algorithms, Bregman information, and exponential families
- A Bregman Method for Structure Learning on Sparse Directed Acyclic Graphs
- Intervention Efficient Algorithms for Approximate Learning of Causal Graphs
- Mixed Graphical Models for Causal Analysis of Multi-modal Variables
- Causal Structure Learning: a Bayesian approach based on random graphs
- The Effect of Noise Level on Causal Identification with Additive Noise Models
- Deconfounded Score Method: Scoring DAGs with Dense Unobserved Confounding
- Identifiability of Gaussian Structural Equation Models with Homogeneous and Heterogeneous Error Variances
- The neighborhood lattice for encoding partial correlations in a Hilbert space
- Graphical Fermat's Principle and Triangle-Free Graph Estimation
- Inference of Causal Effects when Control Variables are Unknown
- A New Statistical Framework for Genetic Pleiotropic Analysis of High Dimensional Phenotype Data
- Learning Bayesian Networks through Birkhoff Polytope: A Relaxation Method
- Learning Functional Dependencies with Sparse Regression
- Estimation Rates for Sparse Linear Cyclic Causal Models