Research map / Probabilistic and scientific modeling / Causal discovery
On the sample complexity of conditional independence testing with Von Mises estimator with application to 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.
Proves an exponential concentration inequality for the Von Mises entropy estimator built on a kernel density estimate and uses it to build a CI test (VM-CI) with sample-complexity guarantees for PC and GS causal discovery on continuous variables.
Problem
Conditional independence testing for continuous variables in constraint-based causal discovery lacks sample complexity guarantees; existing approaches (kernel ridge regression/HSIC, KNN or MINE-based MI estimators) are either computationally expensive, lack exponential concentration, or require stro
Approach
Estimate conditional mutual information via four Von Mises entropy estimators built on a Legendre-kernel KDE (sample splitting), prove exponential concentration for this estimator, and derive a threshold CI test whose error decays exponentially in sqrt(n), yielding sample complexity bounds for PC and GS.
Key results
- VM-CI achieves lower combined type I+II error than KNN, MINE, OT and Gaussian CI tests on power-law data; only HSIC is comparable, and VM-CI matches HSIC for n >= 1500 while being significantly faster.
- Exponential concentration: P(|H_vm - H(p)| > eps) bounded by exponential terms in n^{2beta/(2beta+d)} eps and n^{1/2} eps, implying a dimension-free error bound for conditional mutual information.
- PC with VM-CI recovers the MEC with probability >= 1-alpha once n = Omega(((Delta+1)/I_min * log(m/alpha))^2).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use VM-CI instead of the other evaluated CI tests | CI testing on non-Gaussian power-law data · Synthetic conditional independence tests | sum of type I and type II errors | Helped |
| Use VM-CI instead of HSIC | CI testing on non-Gaussian power-law data · Synthetic conditional independence tests with n > 1500 | sum of type I and type II errors | No clear effect |
| Use VM-CI instead of HSIC | CI testing on non-Gaussian power-law data · Synthetic conditional independence tests | runtime | Helped |
| Use VM-CI instead of the OT-based method | CI testing on non-Gaussian power-law data · Synthetic conditional independence tests | performance and time complexity | Helped |
| Use VM-CI instead of MINE | CI testing · Synthetic conditional independence tests | sum of type I and type II errors: ∼ 2 × 10^6 | Helped |
| Use VM-CI instead of other evaluated CI tests | PC · Non-Gaussian synthetic SEM | overall loss | Helped |
| Use VM-CI instead of HSIC | PC · Non-Gaussian synthetic SEM with n ≥ 1500 | overall loss | No clear effect |
| Use VM-CI instead of HSIC | PC · Non-Gaussian synthetic SEM | runtime | Helped |
| Use VM-CI instead of the OT-based method | PC · Non-Gaussian synthetic SEM | overall loss | Helped |
| Use VM-CI instead of most other evaluated CI tests | GS · Non-Gaussian synthetic SEM | overall loss | Helped |
| Use VM-CI instead of HSIC | GS · Non-Gaussian synthetic SEM | runtime | Helped |
Surprising findings
- MINE performs very poorly at the sample sizes tested (total error close to 1), since it needs about 2x10^6 samples to begin converging.
- The OT-based method performs poorly in the PC causal discovery experiment despite its CI test being competitive in the single-test experiment.
Limitations
- Assumes compactly supported densities bounded below by p_min and Hölder smoothness, with parametric rate only for beta > d/2 type conditions.
- Sample complexity bounds rely on faithfulness and correct CI test outputs; a single CI error can change the whole PC/GS output.
- Experiments are limited to synthetic power-law and SEM data with small sample sizes and low dimensions.
Experimental setup
Datasets: synthetic power-law data synthetic SEM data for PC and GS
Benchmarks: synthetic power-law CI testing synthetic SEM causal discovery (PC and GS)
Metrics: sum of type I and type II errors overall graph loss (missing, extra, misoriented edges) runtime
Baselines: KNN-based estimator MINE HSIC-based CI test OT-based CI test Gaussian partial correlation test
Builds on: PC algorithm grow-shrink algorithm MINE Von Mises expansion Legendre kernels
Closest papers by meaning
- Signature Kernel Conditional Independence Tests in Causal Discovery for Stochastic Processes (ICLR 2025 · similarity 0.89)
- Foundations of Testing for Finite-Sample Causal Discovery (ICML 2024 · similarity 0.89)
- Causal Discovery with Fewer Conditional Independence Tests (ICML 2024 · similarity 0.88)
- Strong and Weak Identifiability of Optimization-based Causal Discovery in Non-linear Additive Noise Models (ICML 2025 · similarity 0.88)
- Differentiable Constraint-Based Causal Discovery (NeurIPS 2025 · similarity 0.88)
- Causal Discovery via Conditional Independence Testing with Proxy Variables (ICML 2024 · similarity 0.88)
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.