The Hardness of Conditional Independence Testing and the Generalised Covariance Measure

Rajen D. Shah, Jonas PetersApollo 2019 · DOI

TL;DR

This paper proves that testing for conditional independence (CI) is fundamentally "untestable" in a strong sense: no valid statistical test can simultaneously control Type I error and have power against any alternative. To overcome this, they introduce the Generalised Covariance Measure (GCM), a novel CI test that relies on the predictive accuracy of regression models, making its validity more interpretable and practical.

What Problem Does This Paper Address?

Conditional independence (CI) is a cornerstone concept in statistics, crucial for understanding relationships in data, building graphical models, and performing causal inference. Testing CI, however, is notoriously difficult, especially when the conditioning variable(s) (Z) are continuous. Existing tests often struggle with controlling the Type I error (falsely rejecting the null hypothesis of CI) in finite samples. This paper tackles the theoretical limitations of CI testing, demonstrating that a universally valid CI test with guaranteed power against all alternatives is impossible. It then proposes a practical solution by shifting the burden from strict theoretical guarantees to the interpretability and performance of underlying regression models.

Methods

The paper's core contributions are twofold:

  1. Theoretical Impossibility Result: The authors prove a "no-free-lunch" theorem for CI testing. They show that for any valid CI test, there exists a distribution from the null hypothesis (where CI holds) that the test will reject with a probability exceeding the significance level. This implies that no test can simultaneously control Type I error and have non-zero power against any alternative.
  2. Generalised Covariance Measure (GCM): To address the practical need for CI tests, they introduce the GCM. This method involves:
  3. Nonlinearly regressing X on Z and Y on Z.
  4. Computing a test statistic based on the sample covariance of the residuals from these regressions.
  5. The validity of the GCM test relies on the weak condition that the regression procedures can estimate the conditional means E(X|Z) and E(Y|Z) at a "slow rate." This shifts the problem to one of prediction accuracy, which is often more tractable and interpretable.
  6. The authors provide theoretical guarantees for GCM when using kernel ridge regression and extend it to multivariate and high-dimensional settings.

Datasets

Not discussed in the paper. The paper focuses on theoretical results and simulations using synthetic data generated according to specific models.

Key Insights and Ideas

  • CI Testing is Inherently "Untestable": The most striking insight is the formal proof that a universally powerful and valid CI test is impossible. This highlights a fundamental limitation in statistical inference for CI.
  • Shifting the Burden to Prediction: The GCM cleverly reframes CI testing as a problem of predictive accuracy. If you can accurately predict X from Z and Y from Z, you can effectively test for CI. This makes the test's performance more interpretable based on the chosen regression method.
  • Weak Requirements for Validity: The GCM's validity hinges on relatively mild conditions for the underlying regression estimators, making it applicable in a broader range of scenarios than tests with stricter theoretical assumptions.
  • Domain Knowledge is Crucial: The "no-free-lunch" result underscores the necessity of domain knowledge to select appropriate CI tests or regression methods for the GCM.

Key Results

  • Theorem 2 (No-free-lunch): Proves that no non-trivial CI test with valid level can have power against any alternative.
  • Generalised Covariance Measure (GCM): A new class of CI tests proposed.
  • Theoretical Guarantees: The paper provides theoretical guarantees for the GCM, particularly when using kernel ridge regression, showing it can achieve valid level control under weak conditions.
  • Multivariate and High-Dimensional Extension: The GCM methodology is extended to handle more complex settings.
  • Simulation Study: Demonstrates that the GCM is competitive with state-of-the-art CI tests, particularly in terms of level control when sample sizes are sufficient.

Limitations and Future Work

  • Domain Knowledge Still Required: While the GCM makes suitability easier to judge, selecting the best regression method still requires domain expertise.
  • Computational Complexity: For high-dimensional settings, the computational cost of the regression and aggregation steps can be significant.
  • Future Work: The authors suggest exploring other regression techniques for the GCM, investigating the tradeoff between Type I and Type II errors more deeply, and studying power properties against specific classes of alternatives. They also mention potential extensions to mapped data for broader alternative coverage.

Summary updated

Abstract

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. 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 setting 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.
BibTeX
@inproceedings{shah2019hardness,
  author = {Rajen D. Shah and Jonas Peters},
  title = {{The Hardness of Conditional Independence Testing and the Generalised Covariance Measure}},
  booktitle = {Apollo},
  year = {2019},
  doi = {10.17863/cam.45267},
}
Figure