Sample Complexity of Nonparametric Closeness Testing for Continuous Distributions and Its Application to Causal Discovery with Hidden Confounding
This work addresses the challenge of causal discovery in complex, real-world scenarios with hidden confounding, offering theoretical guarantees that could improve reliability in fields like epidemiology or economics, though it appears incremental by building on existing closeness testing methods.
The paper tackles the problem of closeness testing for continuous distributions and applies it to causal discovery with hidden confounding, achieving optimal parametric rates for the test and providing the first sample complexity guarantees for distinguishing cause and effect in multidimensional non-linear models with non-Gaussian continuous variables under unobserved confounding.
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.