mlsanityData to 14 Oct 2026

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

arXiv 2310.13553 ↗First posted 20 Oct 2023cs.LGcited by 4

Not on the map. Why?

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.

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

9 of 33 references.

References · 9

  1. 2018DAGs with NO TEARS: Continuous Optimization for Structure Learningcited by 752
  2. 2018MINE: Mutual Information Neural Estimationcited by 683
  3. 2013Causal Inference and Causal Explanation with Background Knowledgecited by 170
  4. 2019Causal Discovery with Reinforcement Learningcited by 145
  5. 2017Testing Conditional Independence of Discrete Distributionscited by 22
  6. 2021On the Sample Complexity of Causal Discovery and the Value of Domain Expertisecited by 9
  7. 2023Nystr"om M-Hilbert-Schmidt Independence Criterioncited by 5
  8. 2016Exponential Concentration of a Density Functional Estimatorcited by 4
  9. 2023Learning Causal Graphs via Monotone Triangular Transport Mapscited by 4

Built on by

Cited by year

Citing papers per year: 2024: 1; 2025: 3.

4 papers.

  1. 2025Efficient Ensemble Conditional Independence Test Framework for Causal Discoverycited by 5
  2. 2024Confounded Budgeted Causal Banditscited by 4
  3. 2025Sample Complexity of Nonparametric Closeness Testing for Continuous Distributions and Its Application to Causal Discovery with Hidden Confoundingcited by 0
  4. 2025Optimal structure learning and conditional independence testingcited by 0