Research map / Probabilistic and scientific modeling / Causal discovery
Adaptive Online Experimental Design for Causal Discovery
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a track-and-stop algorithm for fixed-confidence causal discovery that adaptively picks interventions from a graph separating system, with a problem-dependent bound on expected interventional samples.
Problem
Causal discovery with a limited number of interventional samples: existing methods assume infinite interventional data or are restricted (e.g., trees), and waste samples on non-adaptive intervention choices.
Approach
Formalizes causal discovery as fixed-confidence pure exploration: adaptively selects interventions from a graph separating system via allocation matching (AdaHedge-based online optimization), stops when a KL-based confidence condition holds, and proves an asymptotically matching lower bound on expected samples for general CPDAGs.
Key results
- Track-and-stop achieves lower SHD than random, DCT, adaptive sensitivity search, and GIES baselines at the same interventional sample counts on random chordal graphs.
- On SACHS (13 nodes, 17 edges), the method yields significantly lower SHD for the same number of samples than baselines.
- Proves the practical algorithm matches an asymptotic lower bound on expected interventional samples, with exact version achieving c(D*) and practical version a lower-bound constant.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use adaptive track-and-stop intervention selection instead of the baseline methods | Causal discovery on complete Erdős–Rényi random chordal graphs with 5, 6, and 7 vertices · Complete Erdős–Rényi random chordal graphs | SHD | Helped |
| Use adaptive track-and-stop intervention selection instead of the baseline methods | Causal discovery on Erdős–Rényi random chordal graphs with varying graph density · Erdős–Rényi random chordal graphs | SHD | Helped |
| Use adaptive track-and-stop intervention selection instead of the baseline methods | Causal discovery on the SACHS Bayesian network · SACHS | SHD | Helped |
Surprising findings
- Sample requirement of the proposed method grows only slowly with graph density, while baselines' sample needs increase significantly for denser graphs.
Limitations
- Assumes causal sufficiency, discrete variables, and access to the true observational distribution / correct CPDAG.
- Exact algorithm requires enumerating exponentially many DAGs in the MEC.
- Experiments limited to small graphs (5-7 nodes) and SACHS.
Experimental setup
Datasets: SACHS Bayesian network (bnlearn) random Erdos-Renyi chordal graphs
Benchmarks: random complete ER chordal graphs (5-7 nodes) SACHS Bayesian network
Metrics: structural hamming distance vs number of interventional samp
Baselines: random interventions within graph separating system Directed Clique Trees active structure learning adaptive sensitivity search GIES
Builds on: track-and-stop (Garivier and Kaufmann) AdaHedge PC algorithm Meek rules
Closest papers by meaning
- Sample Efficient Bayesian Learning of Causal Graphs from Interventions (NeurIPS 2024 · similarity 0.93)
- Foundations of Testing for Finite-Sample Causal Discovery (ICML 2024 · similarity 0.90)
- Interventional Causal Discovery in a Mixture of DAGs (NeurIPS 2024 · similarity 0.90)
- Partial Structure Discovery is Sufficient for No-regret Learning in Causal Bandits (NeurIPS 2024 · similarity 0.89)
- Characterization and Learning of Causal Graphs from Hard Interventions (NeurIPS 2025 · similarity 0.89)
- CausalTab: Pretraining Across Causal Environments for Tabular Causal Discovery (NeurIPS 2026 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.