mlsanityData to 7 Oct 2026

A polynomial-time algorithm for learning nonparametric causal graphs

arXiv 2006.11970 ↗First posted 22 Jun 2020stat.ML cs.LG math.STcited by 29

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 29 papers in the map (data through 7 Oct 2026). First posted on arXiv 22 Jun 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 8; 2022: 4; 2023: 9; 2024: 5; 2025: 2; 2026: 1.

29 papers.

Sort:

  1. 2021Beware of the Simulated DAG! Causal Discovery Benchmarks May Be Easy To Gamecited by 159
  2. 2021Learning latent causal graphs via mixture oraclescited by 55
  3. 2021Efficient Bayesian network structure learning via local Markov boundary searchcited by 14
  4. 2022Optimal estimation of Gaussian DAG modelscited by 14
  5. 2021Structure learning in polynomial time: Greedy algorithms, Bregman information, and exponential familiescited by 10
  6. 2023DAG Learning on the Permutahedroncited by 9
  7. 2023Local Discovery by Partitioning: Polynomial-Time Causal Discovery Around Exposure-Outcome Pairscited by 9
  8. 2023Effective Causal Discovery under Identifiable Heteroscedastic Noise Modelcited by 8
  9. 2023Heteroscedastic Causal Structure Learningcited by 6
  10. 2024Markov Equivalence and Consistency in Differentiable Structure Learningcited by 6
  11. 2021Learning linear non-Gaussian directed acyclic graph with diverging number of nodescited by 5
  12. 2021A Fast Non-parametric Approach for Local Causal Structure Learningcited by 5
17 more
  1. 2024Scalable and Flexible Causal Discovery with an Efficient Test for Adjacencycited by 5
  2. 2023Order-based Structure Learning with Normalizing Flowscited by 4
  3. 2025BUILD with Precision: Bottom-Up Inference of Linear DAGscited by 4
  4. 2022Sequentially learning the topological ordering of causal directed acyclic graphs with likelihood ratio scorescited by 3
  5. 2023Differentiable Bayesian Structure Learning with Acyclicity Assurancecited by 3
  6. 2024Optimal estimation of Gaussian (poly)treescited by 3
  7. 2021Learning Sparse Fixed-Structure Gaussian Bayesian Networkscited by 2
  8. 2022NURD: Negative-Unlabeled Learning for Online Datacenter Straggler Predictioncited by 2
  9. 2024Probably approximately correct high-dimensional causal effect estimation given a valid adjustment setcited by 2
  10. 2023Recovering Linear Causal Models with Latent Variables via Cholesky Factorization of Covariance Matrixcited by 1
  11. 2024Enabling Causal Discovery in Post-Nonlinear Models with Normalizing Flowscited by 1
  12. 2025Learning Gaussian DAG Models without Condition Number Boundscited by 1
  13. 2021Identifiability of AMP chain graph modelscited by 0
  14. 2022Estimating large causal polytrees from small samplescited by 0
  15. 2023Learning nonparametric DAGs with incremental information via high-order HSICcited by 0
  16. 2023Distributionally Robust Skeleton Learning of Discrete Bayesian Networkscited by 0
  17. 2026Discrete Score Matching Enables Causal Discovery from Count Datacited by 0