The hardness of conditional independence testing and the generalised covariance measure

By Rajen Dinesh Shah, Jan Peters. 2018

381 citations recorded by the source corpus.

It is a common saying that testing for conditional independence, i.e., testing whether whether two random vectors $X$ and $Y$ are independent, given $Z$, is a hard statistical problem if $Z$ is a continuous random variable (or vector). In this paper, we prove that conditional independence is indeed a particularly difficult hypothesis to test for. Valid statistical tests are required to have a size that is smaller than a predefined significance level, and different tests usually have power against a different class of alternatives. We prove that a valid test for conditional independence does not have power against any alternative. Given the non-existence of a uniformly valid conditional independence test, we argue that tests must be designed so their suitability for a particular problem may be judged easily. To address this need, we propose in the case where $X$ and $Y$ are univariate to nonlinearly regress $X$ on $Z$, and $Y$ on $Z$ and then compute a test statistic based on the sample covariance between the residuals, which we call the generalised covariance measure (GCM). We prove that validity of this form of test relies almost entirely on the weak requirement that the regression procedures are able to estimate the conditional means $X$ given $Z$, and $Y$ given $Z$, at a slow rate. We extend the methodology to handle settings where $X$ and $Y$ may be multivariate or even high-dimensional. While our general procedure can be tailored to the setting at hand by combining it with any regression technique, we develop the theoretical guarantees for kernel ridge regression. A simulation study shows that the test based on GCM is competitive with state of the art conditional independence tests. Code is available as the R package GeneralisedCovarianceMeasure on CRAN.

Subfields: Computer Networks and Communications, Statistics and Probability, Probabilistic & Bayesian Methods

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Statistics and Probability

In Probabilistic & Bayesian Methods

Citations in the corpus

A Sober Look at the Unsupervised Learning of Disentangled Representations and their Evaluation (2020, background): “As quantifying statistical dependencies through independence testing is a challenging task (Shah and Peters, 2018) several approaches have been proposed.”
Toward Causal Representation Learning (2021, background): “Thus, while, in principle, the conditional independencies implied by the causal Markov condition hold irrespective of the complexity of the functions appearing in an SCM, for finite data sets, conditional independence testing is hard without additional assumptions [225].”
50 Years of Test (Un)fairness: Lessons for Machine Learning (2018, background): “Whereas correlation is a descriptive statistic, and so calculating requires few assumptions, estimating independence requires an the use of inferential statistics, which can in general be highly non-trivial [59].”
Towards Causal Representation Learning (2021, background): “So while, in principle, the conditional independencies implied by the causal Markov condition hold irrespective of the complexity of the functions appearing in an SCM, for finite datasets, conditional independence testing is hard without additional assumptions [225].”
Causality for Machine Learning (2019, background): “ thus has no nontrivial implications. 10We had studied this for some time with Kacper Chwialkowski, Arthur Gretton, Dominik Janzing, Jonas Peters, and Ilya Tolstikhin; a formal result was obtained by Shah and Peters (2018). 8 It turns out that both problems can be addressed by making assumptions on ”
Learning Neural Causal Models from Unknown Interventions (2019, neutral): “Established approaches for causal inference are often either relying on restrictive assumptions or on conditional independence testing, which is hard (Shah & Peters, 2018).”
Impossible inference in econometrics: Theory and applications (2016, neutral): “Under uniformly bounded moment conditions, Shah and Peters (2019) propose a test for such a null hypothesis that controls size and has non-trivial power in large samples.”
On Azadkia–Chatterjee’s conditional dependence coefficient (2021, background): “1) when X is continuous is a remarkably challenging task (Bergsma, 2004; Shah and Peters, 2020; Neykov et al., 2021).”
The conditional permutation test (2018, background): “Our work seeks to complement this fundamental result of Shah and Peters [17] by demonstrating that, given some additional knowledge, namely an approximation to the conditional distribution of X given Z , one can in fact derive conditional independence tests that are approximately valid in ﬁnite…”
Towards Out-Of-Distribution Generalization: A Survey (2021, methodology): “Markov boundary discovery is generally challenging because traditional methods [7, 8] are always based on the conditional independence test, which is a particularly difficult hypothesis to test for [231].”
D’ya Like DAGs? A Survey on Structure Learning and Causal Discovery (2021, background): “As noted by Peters et al. (2017) [190], the number of possible DAGs for 10 variables is > 4 × 10 18 .”
Minimax optimal conditional independence testing (2020, background): “In view of recent results on conditional independence testing [29], one cannot hope to design non-trivial tests, which control the type I error for all absolutely continuous conditionally independent distributions, while still ensuring power against interesting alternatives.”