Research map / Probabilistic and scientific modeling / Causal discovery
Foundations of Testing for Finite-Sample 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.
Frames finite-sample causal discovery as structured multiple testing and builds anytime-valid e-process tests for edge orientation that combine via Meek rules, plus a multi-constraint bandit algorithm for causal verification.
Problem
Causal discovery under finite samples, where a node intervention gives only stochastic evidence rather than revealing edge orientations, so the update step (deciding which edges to orient) needs valid anytime testing.
Approach
Views edge orientation as anytime-valid hypothesis testing using e-processes built from sub-Gaussian mean-shift evidence, combines edge e-processes via Meek-rule implications to increase power, and reduces causal verification to multi-constraint bandit optimization.
Key results
- Anytime e-process test keeps miscoverage below alpha in every simulated setting (ER graph n=30, p=0.5, alpha=0.2), while the fixed-time z-test often shows high miscoverage.
- Combining e-values via Meek rules is more useful in large data/graph regimes, while base e-values are more effective in small regimes (chain graph experiments).
- Algorithm 3 for causal verification as multi-constraint bandits has regret bound of order O~(M/b + sqrt((b+M)M/b)) times OPT plus O~(M sqrt(T)/b + nM).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use the anytime-valid e-process test instead of the fixed-time test | Finite-sample causal discovery · Erdos-Renyi graphs (n=30, p=0.5) | miscoverage rate | Helped |
| use the anytime-valid e-process test instead of the fixed-time test | Finite-sample causal discovery · Erdos-Renyi graphs (n=30, p=0.5) | number of oriented edges | Mixed |
| combine edge e-values using propagation rules rather than use base e-values | Causal discovery · Chain graphs | number of oriented edges | Mixed |
Surprising findings
- The fixed-time test is not conservative enough and leads to high miscoverage, while the anytime test orients fewer edges to attain error control.
Limitations
- Assumes causal sufficiency and known graph skeleton in the main worst-case setting.
- Requires minimal causal effect size b to be known and faithfulness assumption.
- Experiments are limited to simulated linear Gaussian graphs.
Experimental setup
Benchmarks: simulated Erdos-Renyi and tree graphs
Metrics: miscoverage rate number of oriented edges
Baselines: fixed-time z-test p-value baseline
Builds on: Greenewald et al. (2019) finite-sample causal discovery setup Ramdas et al. (2023) e-processes Meek rules PC algorithm structured bandits (Badanidiyuru et al., 2018)
Closest papers by meaning
- Causal Discovery with Fewer Conditional Independence Tests (ICML 2024 · similarity 0.91)
- On Causal Discovery in the Presence of Deterministic Relations (NeurIPS 2024 · similarity 0.90)
- Adaptive Online Experimental Design for Causal Discovery (ICML 2024 · similarity 0.90)
- Sample Efficient Bayesian Learning of Causal Graphs from Interventions (NeurIPS 2024 · similarity 0.90)
- Characterization and Learning of Causal Graphs from Hard Interventions (NeurIPS 2025 · similarity 0.89)
- Interventional Causal Discovery in a Mixture of DAGs (NeurIPS 2024 · 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.