Learning Directed Acyclic Graphs with Penalized Neighbourhood Regression

By Bryon Aragam, Arash Ali Amini, Qing Zhou. 2015

47 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Statistics and Probability, Graph Learning, 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

1. Simon Lacoste-Julien
2. Sébastien Lachapelle
3. Philippe Brouillard
4. Eric P. Xing
5. Tristan Deleu
6. Bryon Aragam
7. Pradeep Ravikumar
8. Yoshua Bengio

In Statistics and Probability

1. Eric P. Xing
2. Bryon Aragam
3. Sébastien Lachapelle
4. Simon Lacoste-Julien
5. Pradeep Ravikumar
6. Philippe Brouillard
7. Xun Zheng
8. Tristan Deleu

In Graph Learning

1. Simon Lacoste-Julien
2. Sébastien Lachapelle
3. Philippe Brouillard
4. Tristan Deleu
5. Eric P. Xing
6. Pradeep Ravikumar
7. Bryon Aragam
8. Xun Zheng

In Causal Inference & Discovery

1. Simon Lacoste-Julien
2. Sébastien Lachapelle
3. Eric P. Xing
4. Pradeep Ravikumar
5. Bryon Aragam
6. Philippe Brouillard
7. Xun Zheng
8. Tristan Deleu

Citations in the corpus

• Gradient-Based Neural DAG Learning (2019, background): “Even though the authors do not discuss explicitly identifiability issues, they point out consistency results for their LS score in [34, 1, 19].”
• DAGs with NO TEARS: Continuous Optimization for Structure Learning (2018, background): “In this paper, we focus on linear SEM and the least-squares (LS) loss `(W”
• DYNOTEARS: Structure Learning from Time-Series Data (2020, background): “By construction, this formulation of the BA model generates DAGs.”