Learning Directed Acyclic Graphs with Penalized Neighbourhood Regression

Abstract

We study a family of regularized score-based estimators for learning the structure of a directed acyclic graph (DAG) for a multivariate normal distribution from high-dimensional data with $p\gg n$. Our main results establish support recovery guarantees and deviation bounds for a family of penalized least-squares estimators under concave regularization without assuming prior knowledge of a variable ordering. These results apply to a variety of practical situations that allow for arbitrary nondegenerate covariance structures as well as many popular regularizers including the MCP, SCAD, ${\ell }_0$ and ${\ell }_1$. The proof relies on interpreting a DAG as a recursive linear structural equation model, which reduces the estimation problem to a series of neighbourhood regressions. We provide a novel statistical analysis of these neighbourhood problems, establishing uniform control over the superexponential family of neighbourhoods associated with a Gaussian distribution. We then apply these results to study the statistical properties of score-based DAG estimators, learning causal DAGs, and inferring conditional independence relations via graphical models. Our results yield---for the first time---finite-sample guarantees for structure learning of Gaussian DAGs in high-dimensions via score-based estimation.

54 pages, 1 figure

References in corpus (6)

• Nearly unbiased variable selection under minimax concave penalty
• High-dimensional Ising model selection using ${\ell }_1$-regularized logistic regression
• Distinguishing cause from effect using observational data: methods and benchmarks
• A simple approach for finding the globally optimal Bayesian network structure
• Geometry of the faithfulness assumption in causal inference
• Ordering-Based Search: A Simple and Effective Algorithm for Learning Bayesian Networks

Cited by in corpus (16)

• Learning Large-Scale Bayesian Networks with the sparsebn Package
• Inferring large graphs using l1-penalized likelihood
• CASTLE: Regularization via Auxiliary Causal Graph Discovery
• Gradient-Based Neural DAG Learning
• A review of Gaussian Markov models for conditional independence
• Posterior Graph Selection and Estimation Consistency for High-dimensional Bayesian DAG Models
• DYNOTEARS: Structure Learning from Time-Series Data
• Complexity analysis of Bayesian learning of high-dimensional DAG models and their equivalence classes
• A polynomial-time algorithm for learning nonparametric causal graphs
• Structure learning in polynomial time: Greedy algorithms, Bregman information, and exponential families
• Multi-task Learning of Order-Consistent Causal Graphs
• A Bregman Method for Structure Learning on Sparse Directed Acyclic Graphs
• Deconfounded Score Method: Scoring DAGs with Dense Unobserved Confounding
• The neighborhood lattice for encoding partial correlations in a Hilbert space
• Consistent Bayesian Sparsity Selection for High-dimensional Gaussian DAG Models with Multiplicative and Beta-mixture Priors
• Sample Complexity of Nonparametric Semi-Supervised Learning