# On the Sample Complexity of Causal Discovery and the Value of Domain Expertise

arXiv: https://arxiv.org/abs/2102.03274 · HTML: https://mlsanity.com/paper/2102.03274/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 27 references that are in the map.
- First posted on arXiv 5 Feb 2021.

## Builds on (most cited first, 6 of 6)

- [Causal Inference and Causal Explanation with Background Knowledge](https://mlsanity.com/paper/1302.4972/) (2013)
- [Learning and Testing Causal Models with Interventions](https://mlsanity.com/paper/1805.09697/) (2018)
- [Testing Conditional Independence of Discrete Distributions](https://mlsanity.com/paper/1711.11560/) (2017)
- [Causal Inference via Kernel Deviance Measures](https://mlsanity.com/paper/1804.04622/) (2018)
- [An Algorithm for Deciding if a Set of Observed Independencies Has a Causal Explanation](https://mlsanity.com/paper/1303.5435/) (2013)
- [Testing Conditional Independence on Discrete Data using Stochastic Complexity](https://mlsanity.com/paper/1903.04829/) (2019)

## Built on by (most cited first, 9 of 9)

- [Provably Efficient Causal Model-Based Reinforcement Learning for Systematic Generalization](https://mlsanity.com/paper/2202.06545/) (2022)
- [Identifiability Guarantees for Causal Disentanglement from Purely Observational Data](https://mlsanity.com/paper/2410.23620/) (2024)
- [Exploiting Causal Graph Priors with Posterior Sampling for Reinforcement Learning](https://mlsanity.com/paper/2310.07518/) (2023)
- [On sample complexity of conditional independence testing with Von Mises estimator with application to causal discovery](https://mlsanity.com/paper/2310.13553/) (2023)
- [Probably approximately correct high-dimensional causal effect estimation given a valid adjustment set](https://mlsanity.com/paper/2411.08141/) (2024)
- [Learning Dynamic Bayesian Networks from Data: Foundations, First Principles and Numerical Comparisons](https://mlsanity.com/paper/2406.17585/) (2024)
- [Sample Complexity of Nonparametric Closeness Testing for Continuous Distributions and Its Application to Causal Discovery with Hidden Confounding](https://mlsanity.com/paper/2503.07475/) (2025)
- [PAC-Causal Learnability: From Identification to Finite-Sample Guarantees](https://mlsanity.com/paper/2507.18903/) (2025)
- [Causal Preference Elicitation](https://mlsanity.com/paper/2602.01483/) (2026)

## Abstract (arXiv)

Causal discovery methods seek to identify causal relations between random variables from purely observational data, as opposed to actively collected experimental data where an experimenter intervenes on a subset of correlates. One of the seminal works in this area is the Inferred Causation algorithm, which guarantees successful causal discovery under the assumption of a conditional independence (CI) oracle: an oracle that can states whether two random variables are conditionally independent given another set of random variables. Practical implementations of this algorithm incorporate statistical tests for conditional independence, in place of a CI oracle. In this paper, we analyze the sample complexity of causal discovery algorithms without a CI oracle: given a certain level of confidence, how many data points are needed for a causal discovery algorithm to identify a causal structure? Furthermore, our methods allow us to quantify the value of domain expertise in terms of data samples. Finally, we demonstrate the accuracy of these sample rates with numerical examples, and quantify the benefits of sparsity priors and known causal directions.