# On sample complexity of conditional independence testing with Von Mises estimator with application to causal discovery

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 33 references that are in the map.
- First posted on arXiv 20 Oct 2023.

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

- [DAGs with NO TEARS: Continuous Optimization for Structure Learning](https://mlsanity.com/paper/1803.01422/) (2018)
- [MINE: Mutual Information Neural Estimation](https://mlsanity.com/paper/1801.04062/) (2018)
- [Causal Inference and Causal Explanation with Background Knowledge](https://mlsanity.com/paper/1302.4972/) (2013)
- [Causal Discovery with Reinforcement Learning](https://mlsanity.com/paper/1906.04477/) (2019)
- [Testing Conditional Independence of Discrete Distributions](https://mlsanity.com/paper/1711.11560/) (2017)
- [On the Sample Complexity of Causal Discovery and the Value of Domain Expertise](https://mlsanity.com/paper/2102.03274/) (2021)
- [Nystr"om M-Hilbert-Schmidt Independence Criterion](https://mlsanity.com/paper/2302.09930/) (2023)
- [Exponential Concentration of a Density Functional Estimator](https://mlsanity.com/paper/1603.08584/) (2016)
- [Learning Causal Graphs via Monotone Triangular Transport Maps](https://mlsanity.com/paper/2305.18210/) (2023)

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

- [Efficient Ensemble Conditional Independence Test Framework for Causal Discovery](https://mlsanity.com/paper/2509.21021/) (2025)
- [Confounded Budgeted Causal Bandits](https://mlsanity.com/paper/2401.07578/) (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)
- [Optimal structure learning and conditional independence testing](https://mlsanity.com/paper/2507.05689/) (2025)

## Abstract (arXiv)

Motivated by conditional independence testing, an essential step in constraint-based causal discovery algorithms, we study the nonparametric Von Mises estimator for the entropy of multivariate distributions built on a kernel density estimator. We establish an exponential concentration inequality for this estimator. We design a test for conditional independence (CI) based on our estimator, called VM-CI, which achieves optimal parametric rates under smoothness assumptions. Leveraging the exponential concentration, we prove a tight upper bound for the overall error of VM-CI. This, in turn, allows us to characterize the sample complexity of any constraint-based causal discovery algorithm that uses VM-CI for CI tests. To the best of our knowledge, this is the first sample complexity guarantee for causal discovery for continuous variables. Furthermore, we empirically show that VM-CI outperforms other popular CI tests in terms of either time or sample complexity (or both), which translates to a better performance in structure learning as well.