A polynomial-time algorithm for learning nonparametric causal graphs

Abstract

We establish finite-sample guarantees for a polynomial-time algorithm for learning a nonlinear, nonparametric directed acyclic graphical (DAG) model from data. The analysis is model-free and does not assume linearity, additivity, independent noise, or faithfulness. Instead, we impose a condition on the residual variances that is closely related to previous work on linear models with equal variances. Compared to an optimal algorithm with oracle knowledge of the variable ordering, the additional cost of the algorithm is linear in the dimension $d$ and the number of samples $n$. Finally, we compare the proposed algorithm to existing approaches in a simulation study.

arXiv commentTo appear at NeurIPS 2020

References in corpus (23)

• Distinguishing cause from effect using observational data: methods and benchmarks
• A simple approach for finding the globally optimal Bayesian network structure
• On the Identifiability of the Post-Nonlinear Causal Model
• CAM: Causal additive models, high-dimensional order search and penalized regression
• Identifiability of Gaussian structural equation models with equal error variances
• DAG-GNN: DAG Structure Learning with Graph Neural Networks
• ${\ell }_0$-penalized maximum likelihood for sparse directed acyclic graphs
• Causality for Machine Learning
• Causal Discovery with Reinforcement Learning
• High-dimensional learning of linear causal networks via inverse covariance estimation
• Nonparametric sparsity and regularization
• On Causal Discovery with Equal Variance Assumption
• Selection of variables and dimension reduction in high-dimensional non-parametric regression
• Learning Directed Acyclic Graphs with Penalized Neighbourhood Regression
• Causal Inference via Kernel Deviance Measures
• Score-based Causal Learning in Additive Noise Models
• Learning Identifiable Gaussian Bayesian Networks in Polynomial Time and Sample Complexity
• Gradient-Based Neural DAG Learning
• Tight conditions for consistent variable selection in high dimensional nonparametric regression
• Causal Discovery with General Non-Linear Relationships Using Non-Linear ICA
• Distinguishing Cause from Effect Using Quantiles: Bivariate Quantile Causal Discovery
• Causal Mosaic: Cause-Effect Inference via Nonlinear ICA and Ensemble Method
• Conditionally-additive-noise Models for Structure Learning