On the Hardness of Conditional Independence Testing In Practice

AI summary

Overview

• Research area: Statistical machine learning, specifically hypothesis testing for conditional independence (CI) using kernel methods, with connections to causal discovery, fairness evaluation, and distribution shift.
• Technical level: Advanced. The paper relies on reproducing kernel Hilbert spaces (RKHSs), conditional mean embeddings, Hilbert–Schmidt operators, U-statistics, and asymptotic normality arguments.
• Scope: The paper dissects why kernel-based conditional independence tests such as KCI fail in practice — separating the role of conditional mean embedding estimation error from the role of the conditioning kernel choice — and shows that GCM-style tests are nearly a special case of KCI.

What This Paper Is About

Conditional independence testing asks whether two variables A and B carry information about each other once a third variable C is accounted for, and this is a core subroutine in causal discovery, fairness auditing, and robustness checks. Prior theory (Shah & Peters, 2020) proves the task is impossible to solve with nontrivial power in full generality, but that adversarial construction does not explain why tests in practice fail so often. This paper takes the most widely used practical test, the Kernel-based Conditional Independence (KCI) test, and isolates the concrete mechanisms — conditional mean estimation error and poorly chosen conditioning kernels — behind its inflated Type-I error and weak power.

Key Contributions

1. A re-framing of the KCI operator. The authors prove a new characterization (Theorem 2.2, extending Daudin, 1980) expressing conditional independence through conditional covariances weighted by a function w(C), and use it to define a KCI operator whose squared Hilbert–Schmidt norm is the KCI statistic.
2. A formal link between KCI and GCM. They show that the Generalized Covariance Measure of Shah & Peters (2020) is nearly a special case of KCI with linear kernels on A and B and a rank-one kernel on C, with Weighted GCM (Scheidegger et al., 2022) corresponding to a more flexible but still constrained C kernel.
3. A demonstration that the conditioning kernel is decisive. They show that using a regression kernel as the conditioning kernel — the implicit practice of Pogodin et al. (2023, 2024) — can be a very poor choice, construct a synthetic problem where GCM (equivalent to ℓ_C = ∞) cannot detect any dependence, and propose selecting the C kernel by maximizing an estimated signal-to-noise ratio on a training split.
4. A diagnostic account of false rejections. They analyze special cases and derive formal bounds connecting conditional mean estimation error to test validity, clarifying when KCI and GCM remain reliable and showing that kernel selection for power can itself inflate Type-I error.

Main Findings

• The impossibility result does not explain practical failures. Shah & Peters (2020) constructed adversarial null/alternative pairs — their example extracts the thirtieth decimal place of C and adds it to both A and B — but the authors argue this construction is not especially informative about why real CI tests break down.
• Estimation error in the conditional mean embedding is the root cause of Type-I error. The authors show that KCI's theoretical difficulties arise solely from estimating μ_{A|C} and μ_{B|C}, not from the statistic's structure.
• A valid test exists if the conditional mean embeddings are known. Proposition 4.1 gives a threshold t̃_n = 32 κ_A κ_B κ_C √(1/(n−1) · log(1/α)) yielding finite-sample level at most α and consistency against fixed alternatives, proved with Hoeffding's inequality for U-statistics — but it is highly conservative, since the correct threshold should be Θ(1/n).
• The conditioning kernel controls power, and short or long lengthscales both fail. In the synthetic problem of Eq. (7) with C ~ N(0,1), the analytic KCI equals ½ τ⁴ e^{−β²} √(ℓ_C²/(ℓ_C²+2)) (e^{2β²/(ℓ_C²+2)} − 1). If ℓ_C ≪ √2 the kernel term vanishes; if ℓ_C ≫ β the covariance term vanishes. An intermediate value of ℓ_C is required.
• GCM can be structurally blind to real dependence. Because GCM averages the conditional covariance over C (ℓ_C = ∞), it fails entirely on an example where Cov(A, B|C) alternates in sign and E_C[Cov(A, B|C)] = 0.
• Power-based kernel selection works under the alternative. The approximate rejection probability is Φ(√n · KCI_hat/σ̂_{H1} − √n · t_n/σ̂_{H1}), so the best kernel approximately maximizes SNR_hat = KCI_hat/σ̂_{H1}. The authors estimate this as the ratio of KCI_hat_n to its estimated standard deviation on a training split (Liu et al., 2020, Eq. (5)).
• Kernel selection can badly inflate Type-I error. The same procedure that maximizes power also tends to make false rejection more severe.
• Better regression shrinks the Type-I problem. In Figure 3, with training size m = 200, changing ℓ_C² noticeably moves the Type-I error; with m = 1000, the regression is better trained and Type-I error stays well controlled across all ℓ_C². The empirical power curve still depends strongly on both β and ℓ_C².
• Only one conditional distribution needs to be known. In the "model-X" setting (Candes et al., 2018; Berrett et al., 2019; Grünwald et al., 2024), knowing A|C and B|C makes the KCI test exactly valid; knowing only one suffices using CIRCE rather than KCI.
• Zhang et al.'s asymptotic claim has a gap. The paper notes that the χ²-mixture null result of Zhang et al. (2011) holds with the true conditional mean embeddings, and that personal communication with those authors confirmed "there is a gap" between their published sketch and a true proof for the ridge-regression-estimated version.

Methodology in Plain English

The authors proceed in four stages. First, they recast the KCI statistic as the squared Hilbert–Schmidt norm of a single operator built from two ingredients: the conditional cross-covariance of A and B given C, and a kernel embedding of C. This reformulation makes the role of the C kernel explicit and lets them prove an equivalence (Theorem 2.2) that any conditional dependence must show up as a nonzero weighted conditional covariance.

Second, they show algebraically that GCM drops out of this framework when A and B are scalars and linear kernels are used, with the C kernel set to the rank-one product w(c)w(c'). The only difference is that GCM estimates a signed, studentized quantity while KCI estimates an absolute-valued norm; the authors draw an analogy to classifier two-sample tests versus maximum mean discrepancy tests, and to variational mutual information tests versus HSIC.

Third, to study kernel choice they build a synthetic Gaussian problem where the conditional correlation γ(C) = sin(βC) oscillates and averages to zero. Because the setup is Gaussian, they can compute the population KCI in closed form as a function of the C kernel lengthscale ℓ_C, and also compute the asymptotic variance, giving an explicit approximate power curve.

Fourth, they validate on simulations: 500 runs of the synthetic example with f_A = cos, f_B = exp, τ = 0.1, varying β and ℓ_C², a training split of size m = 200 or 1000, an independent test set of size 200, and significance level α = 0.05. They compare the theoretical SNR curve against the empirical power curve to check that the selected ℓ_C²* remains effective. Finally, they turn to the Type-I error side, analyzing simple special cases analytically and deriving general bounds linking conditional-mean estimation error to validity of the test.

Why This Matters

• Impact on research: The paper reframes the practical difficulty of CI testing. Instead of treating the Shah & Peters impossibility result as the explanation for failures, it points to a concrete, addressable statistical object — the conditional mean embedding — as the bottleneck, and gives a machine for reasoning about which parts of a CI test can be improved and which cannot.
• Real-world applications:
  • Causal discovery: CI tests are a core subroutine of the PC algorithm and its variants, which are used to recover causal graphs from observational data.
  • Fairness auditing: checking whether a predictor or representation satisfies equalized odds requires CI testing between the prediction and a protected attribute given the target.
  • Out-of-distribution robustness: verifying that a predictor is domain-invariant, particularly in "anticausal" settings, is stated as a conditional independence question.
  • Engineering diagnostics: the authors' motivating example is high-dimensional vibration data where two mechanical parts may be coupled only through high-frequency resonances that a regression kernel would miss.
• Industry relevance: Tools such as GCM, Weighted GCM, CIRCE, and SplitKCI are used in production-style pipelines (Hochsprung et al., 2023; Wieck-Sosa et al., 2025), and the paper's message is that a default choice of conditioning kernel can silently destroy power or silently produce false positives. It also connects to the model-X framework used for variable selection with false discovery rate guarantees.

Future Directions

1. Kernel selection that controls Type-I error. The authors' SNR-maximizing procedure improves power but inflates false rejections; a selection criterion balancing both is left open.
2. Better conditional mean embedding estimation. Since Proposition 4.1 shows a valid, consistent test is possible when the embeddings are known, closing the estimation gap — including validating the ridge-regression-regularized version of Zhang et al.'s χ²-mixture result — is the central open problem.
3. Extending the GCM–KCI bridge. The paper shows GCM covers only a constrained region of the KCI framework; whether more of that space can be exploited by practical, computationally tractable tests is unresolved.
4. Beyond the linear-residual setting. The synthetic analysis uses scalar A and B with linear kernels, aligning with GCM; generalization to nonlinear feature maps and multivariate outcomes is not established.

Target Audience

Statisticians and machine learning researchers working on kernel methods, hypothesis testing, causal discovery, or distribution shift; practitioners who deploy CI tests inside causal discovery or fairness pipelines and need to understand why default kernel and threshold choices can fail; and theoretically inclined readers interested in the gap between impossibility results and observed empirical behavior.

Authors’ abstract

Tests of conditional independence (CI) underpin a number of important problems in machine learning and statistics, from causal discovery to evaluation of predictor fairness and out-of-distribution robustness. Shah and Peters (2020) showed that, contrary to the unconditional case, no universally finite-sample valid test can ever achieve nontrivial power. While informative, this result (based on "hiding" dependence) does not seem to explain the frequent practical failures observed with popular CI tests. We investigate the Kernel-based Conditional Independence (KCI) test - of which we show the Generalized Covariance Measure underlying many recent tests is nearly a special case - and identify the major factors underlying its practical behavior. We highlight the key role of errors in the conditional mean embedding estimate for the Type-I error, while pointing out the importance of selecting an appropriate conditioning kernel (not recognized in previous work) as being necessary for good test power but also tending to inflate Type-I error.