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.

本文分析了没有条件独立 (conditional independence) 武器下，因果探索算法的样本复杂度，以及领域专业知识在数据样本方面的价值，并通过数字实例证明了这些抽样率的准确性，并量化了稀疏先验和已知因果方向的好处。