BETA This research page is an early version. Explanatory text, figure selection, and presentation are still being revised.

CLeaR 2025

Sample Complexity of Nonparametric Closeness Testing for Continuous Distributions and Its Application to Causal Discovery with Hidden Confounding

Fateme Jamshidi · Sina Akbari · Negar Kiyavash

Proceedings of the Fourth Conference on Causal Learning and Reasoning · 2025

Paper CLeaR / PMLR OpenReview

Keywords.

causal discovery distribution testing sample complexity hidden confounding

TL;DR.

We derive a nonparametric closeness test for multidimensional continuous distributions using a von Mises estimator of KL divergence, obtain optimal parametric rates under smoothness, and use the test to give sample-complexity guarantees for distinguishing causal direction from hidden confounding.

Why this matters.

This connects a fundamental distribution-testing problem to causal discovery. It gives finite-sample guarantees for distinguishing cause, effect, and latent confounding in nonlinear, non-Gaussian, multidimensional continuous settings.

Abstract

We study the problem of closeness testing for continuous distributions and its implications for causal discovery. Specifically, we analyze the sample complexity of distinguishing whether two multidimensional continuous distributions are identical or differ by at least ϵ in terms of Kullback-Leibler (KL) divergence under non-parametric assumptions. To this end, we propose an estimator of KL divergence which is based on the von Mises expansion. Our closeness test attains optimal parametric rates under smoothness assumptions. Equipped with this test, which serves as a building block of our causal discovery algorithm to identify the causal structure between two multidimensional random variables, we establish sample complexity guarantees for our causal discovery method. To the best of our knowledge, this work is the first work that provides sample complexity guarantees for distinguishing cause and effect in multidimensional non-linear models with non-Gaussian continuous variables in the presence of unobserved confounding.

Main message. The paper turns nonparametric KL closeness testing into a causal-discovery primitive with explicit sample-complexity guarantees.

The paper at a glance

An informal guide to the problem, the idea, and the main results.

distribution testing sample complexity continuous distributions hidden confounding

1. The problem

Closeness testing asks whether two unknown continuous distributions are the same or meaningfully different. In causal discovery with hidden confounding, that question appears naturally inside decisions about whether environments or conditional distributions agree.

2. The key idea

We first solve the statistical testing problem, then use it as a subroutine in causal discovery. That makes the discovery guarantees depend on the fundamental sample complexity of the underlying nonparametric test.

3. Nonparametric closeness testing

Theory

We construct a KL-divergence estimator based on the von Mises expansion and prove concentration guarantees for the resulting closeness test. Under smoothness conditions, the test attains the optimal parametric rate.

4. Causal-discovery sample complexity

Theory

Using the closeness test as a building block, we derive finite-sample guarantees for distinguishing A → B, B → A, and A ← U → B with multidimensional nonlinear continuous variables and unobserved confounding.

5. How it works

Formulate the nonparametric closeness-testing problem precisely.
Derive upper and lower bounds on the required sample size.
Embed the resulting test into a causal-discovery procedure.
Translate testing difficulty into discovery guarantees.

What the theory gives us

Theoretical takeaway.

The main payoff is a finite-sample guarantee rather than a simulation benchmark. The causal-discovery procedure succeeds with constant probability using O(ϵ^−τ) observational and interventional samples, where τ = max{2, (2β + d)/(2β)}; the success probability can be boosted to 1 − δ with only a logarithmic-factor increase in sample complexity.

Where this helps

Good fit

You care about causal discovery with hidden confounding in continuous-data settings.
You want to understand how a low-level statistical testing problem limits a higher-level graph-learning problem.
You prefer nonparametric guarantees to parametric convenience.

Keep in mind

The result is fully nonparametric at the distribution-testing level and allows multidimensional, non-Gaussian continuous variables.
The same testing machinery also yields a version of the causal-discovery procedure that can operate using interventional samples without requiring observational samples.

Cite this paper

@InProceedings{pmlr-v275-jamshidi25a,
  title     = {Sample Complexity of Nonparametric Closeness Testing for Continuous Distributions and Its Application to Causal Discovery with Hidden Confounding},
  author    = {Jamshidi, Fateme and Akbari, Sina and Kiyavash, Negar},
  booktitle = {Proceedings of the Fourth Conference on Causal Learning and Reasoning},
  pages     = {1217--1238},
  year      = {2025},
  volume    = {275},
  series    = {Proceedings of Machine Learning Research},
  publisher = {PMLR},
  url       = {https://proceedings.mlr.press/v275/jamshidi25a.html}
}