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.

基于我们的估计器建立的多元分布的熵的非参数 Von Mises 估计器，在条件独立性测试这一关键步骤上受到启发，我们设计了一种基于估计器的条件独立性测试（VM-CI），在光滑性假设下达到了最优的参数速率。利用指数集中不等式，我们证明了 VM-CI 的总体误差的紧密上限。反过来，这使我们能够表征使用 VM-CI 进行条件独立性测试的任何基于约束的因果发现算法的样本复杂度。据我们所知，这是连续变量因果发现的首个样本复杂度保证。此外，我们经验证明，无论是时间复杂度还是样本复杂度（或两者兼有），VM-CI 在性能上优于其他常见的条件独立性测试，这也反映在结构学习中表现出更好的性能。