The Generalised Kernel Covariance Measure

1. Problem Statement

The paper addresses the challenge of Conditional Independence (CI) testing, a fundamental task in statistics and causal discovery used to determine if random variables $X$ and $Y$ are independent given a set of conditioning variables $Z$ ($X \perp\!\!\perp Y \mid Z$).

Existing methods face two primary limitations:

• Residual-based tests (e.g., GCM, wGCM, PCM): While these offer uniform asymptotic level guarantees (controlling Type I error across a class of distributions), they often rely on "mean-zero" assumptions. This means they test if the expected conditional covariance is zero, rather than if the conditional covariance is zero almost surely. Consequently, they may fail to detect dependencies where the mean conditional covariance vanishes despite the existence of conditional dependence.
• Kernel-based tests (e.g., KCIT, KRESIT, RCIT): These embed variables into Reproducing Kernel Hilbert Spaces (RKHS) to detect a broader range of non-linear dependencies (almost surely zero tests). However, they exclusively rely on Kernel Ridge Regression (KRR) to estimate conditional mean embeddings. KRR is computationally expensive to tune (requiring hyperparameter optimization for kernel lengthscales and regularization) and yields poorly calibrated tests when left untuned. Furthermore, theoretical guarantees for uniform Type I error control in existing kernel-based tests have been lacking.

2. Methodology: The Generalised Kernel Covariance Measure (GKCM)

The authors propose GKCM, a novel CI test that combines the flexibility of kernel methods with the theoretical robustness of the Generalised Hilbertian Covariance Measure (GHCM) framework.

Core Concept

GKCM embeds $X$ and $Y$ into RKHSs ($\mathcal{F}$ and $\mathcal{G}$) using kernels $k$ and $l$, resulting in feature maps $\phi(X)$ and $\psi(Y)$. Instead of testing the raw variables, it tests the conditional independence of these embeddings given $Z$. The test targets the mean conditional covariance operator:
$$C_{XY \cdot Z} := \mathbb{E}\left[ (\phi(X) - \mathbb{E}[\phi(X)|Z]) \otimes (\psi(Y) - \mathbb{E}[\psi(Y)|Z]) \right]$$
If $C_{XY \cdot Z} = 0$, the variables are conditionally independent (under specific kernel assumptions).

Key Innovations

1. Regression Model Agnosticism: Unlike previous kernel-based tests that strictly use KRR, GKCM allows for arbitrary Hilbert space-valued regression estimators. This enables the use of powerful, non-parametric models like Random Forests (specifically Distributional Random Forests) to estimate the conditional mean embeddings $\mathbb{E}[\phi(X)|Z]$ and $\mathbb{E}[\psi(Y)|Z]$.
2. Theoretical Foundation (GHCM): The authors map the problem to the GHCM framework (Lundborg et al., 2022). They prove that under mild assumptions (Polish spaces, continuous/bounded kernels, injective feature maps), testing $X \perp\!\!\perp Y \mid Z$ is equivalent to testing $\phi(X) \perp\!\!\perp \psi(Y) \mid Z$.
3. Uniform Asymptotic Guarantees: The paper establishes sufficient conditions (Theorem 2) under which GKCM achieves uniform asymptotic Type I error control. The key condition is that the in-sample mean squared prediction errors of the regression models must vanish sufficiently fast uniformly over the subset of distributions.
4. Avoidance of Joint Embeddings: To prevent finite-sample Type I error inflation, GKCM avoids the "joint embedding" approach (embedding $(X, Z)$ together) used in some earlier kernel tests (like KCIT). Instead, it regresses the embeddings of $X$ and $Y$ separately on $Z$.

3. Key Contributions

• New Framework: Introduction of GKCM, the first kernel-based CI test that is agnostic to the regression model used, allowing for the integration of tree-based models and other flexible learners.
• Theoretical Rigor: Provision of the first proof of uniform asymptotic level guarantees for a kernel-based CI test, bridging the gap between the theoretical strengths of residual-based tests and the detection power of kernel-based tests.
• Practical Efficiency: Demonstration that using Random Forests (specifically Distributional Random Forests) within the GKCM framework eliminates the need for computationally expensive hyperparameter tuning (unlike KRR), while maintaining or improving statistical power.
• Comprehensive Evaluation: A rigorous simulation study comparing GKCM against state-of-the-art methods (GCM, wGCM, PCM, KCIT, RCIT, RCoT) across diverse data-generating processes.

4. Results

The authors conducted extensive simulations with sample sizes $n \in \{500, 1000, 1500, 2000\}$ across various null and alternative scenarios.

• Type I Error Control:

  • GKCM with Random Forests (GKCM RF) consistently maintained Type I error rates close to the nominal level (0.05) across all null settings, including challenging non-linear scenarios where other methods failed.
  • Existing kernel-based tests (KCIT, RCIT, RCoT) and residual-based tests (GCM, wGCM, PCM) frequently exhibited inflated Type I error rates, particularly in non-linear settings or when regression models were not perfectly tuned.
  • Even when KRR was used within GKCM (GKCM KRR), it performed well, but the Random Forest variant was more robust to the lack of hyperparameter tuning.

• Statistical Power:

  • In alternative settings involving non-linear dependencies, GKCM RF achieved power equal to or greater than all competing methods.
  • It successfully detected dependencies in scenarios where mean-zero tests (GCM, wGCM) failed (e.g., where $\mathbb{E}[\text{Cov}(X,Y|Z)] = 0$ but $X \not\perp\!\!\perp Y \mid Z$).
  • GKCM RF outperformed KRR-based kernel tests in settings where hyperparameter tuning was not feasible or suboptimal.

• Hyperparameter Sensitivity:

  • Additional simulations showed that while tuning KRR hyperparameters could improve the performance of other kernel-based tests, GKCM RF maintained superior or comparable performance without any tuning, highlighting its practical utility.

5. Significance

The paper represents a significant advancement in causal discovery and statistical inference:

1. Bridging Theory and Practice: It resolves the trade-off between theoretical guarantees (uniform error control) and practical detection power (sensitivity to complex non-linearities).
2. Computational Feasibility: By decoupling the CI test from the specific regression algorithm, it allows practitioners to use efficient, off-the-shelf models like Random Forests, avoiding the "tuning bottleneck" of kernel ridge regression.
3. Robustness: The method is shown to be robust across a wide variety of data distributions, making it a reliable tool for real-world causal inference tasks where the true data-generating process is unknown.

In conclusion, GKCM offers a state-of-the-art solution for conditional independence testing, providing strong theoretical guarantees while leveraging the flexibility and speed of modern machine learning regression models.