On the Hardness of Conditional Independence Testing In Practice

We thank the reviewer for the positive review and constructive suggestions. Below, we address the reviewer's concerns and clarify how we will revise the manuscript accordingly.

More supporting experiments

We thank the reviewer for this constructive suggestion. We have run substantial additional simulations beyond those in the submitted paper, which we now present to demonstrate how expirical results align with our theory.

To begin with, we have additional simulation results for the settings already considered in the paper; we will discuss a new setting on images afterwards.

1. Setting of Section 4

We compared our power maximization (PM) approach against standard KCI across training sizes 200-1000 (only parts of them are shown due to space limit), using linear kernels on $A$ and $B$, with $\beta=3$ and test size equals to 200. All experiments are repeated 100 times. We report the mean ± standard error. The standard KCI use fixed-bandwidth conditioning kernel while PM use learned-bandwidth conditioning kernel:

Learning the conditioning kernel gives a huge improvement in test power, bringing Type II error from around 75% to almost 0. In this problem, it also maintains reasonable Type I error control, validating our theoretical analysis that the choice of $C$ kernel can be vital to empirical performance. On this problem, the bandwidth optimization stays in a region of reasonable Type I error, as shown in our Figure 2.

2. Complex 3-Dimensional Conditional Dependence Analysis (Setting of Appendix G.3)

In this setting, we have a three-dimensional $C = (C_1, C_2, C_3)$, and use Gaussian kernels on $A$ and $B$, with $\beta=2$. All kernels are Gaussian; power maximization chooses per-dimension bandwidths for the $C$ kernel.

Our analysis looks at two critical scenarios. However, due to space constraints, we present and discuss only one scenario here. This scenario follows the same setting as Appendix G.3 but includes more comprehensive results. The additional results will be provided in the appendix of the revised paper.

Scenario: Multi-coordinate dependence

Here $A$, $B$, and their conditional dependence use different coordinates, e.g. $A$'s marginal distribution depends on $C_1$, $B$'s on $C_2$, and their correlation depends on $C_3$.

With sufficiently trained regressors:

With poorly trained regressors:

While the patterns are a little difficult to see in this tabular form (we'll put a figure in the revised paper), they agree well with our explanations that poorly-trained CMEs make Type I error explode compared to well-trained CMEs. With insufficiently-trained CMEs, power maximization makes Type I error far worse under Scenario 2.

We will expand on these and related observations in the final version.

3. Real Data Experiments: UTKFace Age Prediction Study

We conducted experiments using the UTKFace dataset, following the methodology from a recent paper:

Y Zhang, Huang, Yang, and Shao. Testing Conditional Mean Independence Using Generative Neural Networks. ICML 2025.

While Zhang et al. did not describe it this way, this test in fact is a KCI test; rather than estimating conditional mean embeddings with ridge regression, however, they use neural networks.

In particular, we (following their setup) took the cropped and aligned UTKFace dataset, and ran a CI test checking whether the age ($A$) is dependent on the whole face image ($B$) when conditioned on the image with the mouth region blacked out ($C$).

In their paper, p-values are above the 5% level when the mouth is covered, suggesting that this region is "not critical for age estimation". They use ImageNet-pretrained neural networks to perform the regression task, achieving a mean absolute error on validation points of around 6 years. When we reran their code and evaluated on only 400 test samples (single run), the resulting p-value was 0.068 (above the significance level).

We train the same network architecture from random initialization, rather than fine-tuning from ImageNet. This gave a higher validation loss, around 8 years, corresponding to a somewhat worse conditional mean embedding estimate. When we tested on the same 400 samples, the p value dropped to just 0.015, indicating that these tests' Type I error behavior can radically depend on small changes in the quality of the CME estimate.

Now that we have set up the machinery to run these kinds of tests, we will add repeated runs and a more thorough exploration of these comparisons across different test sets, and add the results in the revised version.

---

Clarifying what is $q$ when defining $t_n$

Under the null, $n \mathrm{KCI}_n$ converges in distribution to a mixture of chi-squared variables; $q$ is the $1-\alpha$th quantile of that limiting distribution, so that $t_n = q / n$ is the right rejection threshold for $\mathrm{KCI}_n$. We'll clarify this in the text.

---

We sincerely thank the reviewer for the encouraging evaluation and constructive feedback. We believe the suggested additions will make the paper stronger and more comprehensive.

We thank the reviewer for the thoughtful feedback and for recognizing that our work "improves understanding of KCI testing" and "provides a solid foundation for further theoretical improvements." Below, we address the specific comments and outline the improvements we will make based on these suggestions.

More Extensive Simulations and Real Data

We thank the reviewer for this constructive suggestion. We have run substantial additional simulations beyond those in the submitted paper, which we now present to demonstrate how expirical results align with our theory.

To begin with, we have additional simulation results for the settings already considered in the paper; we will discuss a new setting on images afterwards.

1. Setting of Section 4

We compared our power maximization (PM) approach against standard KCI across training sizes 200-1000 (only parts of them are shown due to space limit), using linear kernels on $A$ and $B$, with $\beta=3$ and test size equals to 200. All experiments are repeated 100 times. We report the mean ± standard error. The standard KCI use fixed-bandwidth conditioning kernel while PM use learned-bandwidth conditioning kernel:

Learning the conditioning kernel gives a huge improvement in test power, bringing Type II error from around 75% to almost 0. In this problem, it also maintains reasonable Type I error control, validating our theoretical analysis that the choice of $C$ kernel can be vital to empirical performance. On this problem, the bandwidth optimization stays in a region of reasonable Type I error, as shown in our Figure 2.

2. Complex 3-Dimensional Conditional Dependence Analysis (Setting of Appendix G.3)

In this setting, we have a three-dimensional $C = (C_1, C_2, C_3)$, and use Gaussian kernels on $A$ and $B$, with $\beta=2$. All kernels are Gaussian; power maximization chooses per-dimension bandwidths for the $C$ kernel.

Our analysis looks at two critical scenarios. However, due to space constraints, we present and discuss only one scenario here. This scenario follows the same setting as Appendix G.3 but includes more comprehensive results. The additional results will be provided in the appendix of the revised paper.

Scenario: Multi-coordinate dependence

Here $A$, $B$, and their conditional dependence use different coordinates, e.g. $A$'s marginal distribution depends on $C_1$, $B$'s on $C_2$, and their correlation depends on $C_3$.

With sufficiently trained regressors:

With poorly trained regressors:

The patterns agree well with our explanations that poorly-trained CMEs make Type I error explode compared to well-trained CMEs. With insufficiently-trained CMEs, power maximization makes Type I error far worse under this scenario. Though we only focus on one scenario here, we can also provide additional explanations highlighting the differences between the two scenarios, which will be included in the revised appendix.

We will expand on these and related observations in the final version.

3. Real Data Experiments: UTKFace Age Prediction Study

We conducted experiments using the UTKFace dataset, following the methodology from a recent paper:

Y Zhang, Huang, Yang, and Shao. ``Testing Conditional Mean Independence Using Generative Neural Networks.'' ICML 2025.

While Zhang et al. did not describe it this way, this test in fact is a KCI test; rather than estimating conditional mean embeddings with ridge regression, however, they use neural networks.

In particular, we (following their setup) took the cropped and aligned UTKFace dataset, and ran a CI test checking whether the age ($A$) is dependent on the whole face image ($B$) when conditioned on the image with the mouth region blacked out ($C$).

In their paper, p-values are above the 5% level when the mouth is covered, suggesting that this region is "not critical for age estimation". They use ImageNet-pretrained neural networks to perform the regression task, achieving a mean absolute error on validation points of around 6 years. When we reran their code and evaluated on only 400 test samples (single run), the resulting p-value was 0.068 (above the significance level).

We train the same network architecture from random initialization, rather than fine-tuning from ImageNet. This gave a higher validation loss, around 8 years, corresponding to a somewhat worse conditional mean embedding estimate. When we tested on the same 400 samples, the p value dropped to just 0.015, indicating that these tests' Type I error behavior can radically depend on small changes in the quality of the CME estimate.

Now that we have set up the machinery to run these kinds of tests, we will add repeated runs and a more thorough exploration of these comparisons across different test sets, and add the results in the revised version.

---

Clarifying Figure 3 and Paper Organization

The reviewer's attention to detail with respect to this figure is very much appreciated!

With respect to the standard deviations: since these are averages of binary data points (did the test reject or not), the standard deviation is actually a function only of the mean ($\sqrt{p (1-p)}$). Here, as the caption says, we plot the standard error, which further divides by the square root of the number of runs. Looking into Figure 3, we accidentally ran a total of 500 runs for panel (a) and only 100 for panel (b), explaining the difference; we've increased the number of runs to 500 for all settings to ensure consistency across experiments. Although we cannot present all results here due to space constraints, we will update the results in the revised version.

For the slight increase in Type II error with more training numbers, at very small or very large lengthscales, we don't have a clear explanation for this phenomenon. It might be related to detecting subtle errors in CME estimation in this setting, but it's not clear why that would happen with $\beta \ne 0$ but not with $\beta = 0$, since the distributions given to the CME regression problem are identical.

We also thank the reviewer for the valuable suggestion on the paper organization. We will optimize it to better highlight our contributions.

---

Could you explain where the $\lambda = \ell n^{-1/3}$ in line 874 comes from?

The bound in line 893 works for any choice of $\lambda$; the question, then, is which $\lambda$ to choose to get the best bound. Choosing $\ell n^{-1/3}$ balances between the first $\lambda$ term and the middle two $1 / \sqrt{\lambda n}$ terms, with the $1/\sqrt{n}$ and $1/(n \sqrt\lambda)$ terms not asymptotically relevant. A smaller choice of $\lambda$ would yield a worse rate from the first term, while a larger choice would make the later terms worse. Thus, this choice of $\lambda$ gives the best asymptotic bound.

[6] chose to use simply $\lambda = n^{-1/3}$, concerning themselves only with the asymptotics. Here, we scaled by an arbitrary $\ell$ to emphasize that the theory does not really predict a particular amount of regularization to be optimal (unless we know all the problem-dependent constants, but even then, the constants in the bounds are surely loose enough that this won't be the actually-best choice of regularizaton). The best $\ell$ would be some function of the other problem constants like $\rho$, $s$, $D$, etc.

In fact, the optimal choice of $\lambda$ would have slightly different $n$ dependence, to account for the $1/\sqrt n$ and $1 / (n \sqrt\lambda)$ terms. This would be much more complicated, for no asymptotic advantage.

We will add some discussion of this choice, which indeed goes by with absolutely no explanation in the current version.

---

RCIT and SCIT

We thank the reviewer for suggesting the relationship to RCIT and SCIT.

RCIT is proposed specifically for causal discovery, under the assumption that the data-generating procedure follows additive noise models. Using this assumption, it relaxes the test of $A ⊥ B \mid C$ to simpler unconditional independence tests of $A − f(C) ⊥ B − g(C)$, and $A − f(C) ⊥ C$ or $B − g(C) ⊥ C$. Since RCIT uses GCM-type statistics on regression residuals $A - f(C)$ and $B - g(C)$, our analysis applies broadly to it.

SCIT, at first glance, seems different enough that it might be difficult to frame in our analysis. It seems more related to the permutation-type tests discussed in Appendix C, which while closely related are hard to directly analyze in the same way in our framework. We'll think more about it.

We will add a short discussion in the revised manuscript to highlight this connection.

---

We thank the reviewer for the thorough comments, which have led to real improvements in the paper in formal content, experiment, and explanation. Hopefully the reviewer agrees that this has improved our "theoretically sound and carefully argued analysis of KCI" and will consider raising the numerical score for our submission.

We thank the reviewer for the detailed and positive assessment of our paper. We greatly appreciate the reviewer for recognizing the significance of our insights regarding conditional mean embeddings and their role in the practical failures of KCI. Below, we address the minor suggestions and clarify how we will revise the manuscript accordingly.

Explanation of Figure 1 and Dense Text

We fully agree with these suggestions for improvement. In the revised version, we will expand the explanation of figures and tables to clearly highlight the intuition behind the experiment and its implications. Additionally, we will slightly reduce text density and restructure some parts to make the narrative more accessible without sacrificing rigor.

We also agree that the insights from Appendices G.2 and G.3 are presented too briefly in the main text. In the revision, we will expand their explanation and integrate a clearer discussion to highlight the key findings and their implications more effectively.

Distinguish Contributions

On reflection, we also agree that our contributions are not always as distinct as they should be from summaries of prior work. We will revise to address this, including moving some of the discussion of prior work that is currently mixed in Sections 2 and 3 to integrate with the discussion in Appendix C, and further emphasizing in text which results are novel.

---

We thank the reviewer for recognizing our work as providing "novel insights," "solid theoretical justification," and "important contribution." We have carefully addressed all minor suggestions and will implement the revisions as described above. We believe that with these revisions, the clarity and accessibility of this paper are further improved, although we can't show the exact revisions in the review process here. Hopefully the reviewer agrees that these minor changes are all that is needed for this "important contribution" and can consider raising the numerical score.

We sincerely thank the reviewer for recognizing our work to be "novel," "interesting" and a "valid contribution to the literature." We greatly appreciate the constructive feedback provided and will address each question and suggestion in detail below.

Clarification on the Novelty of Theorem 2.2:

We'd like to clarify that our Theorem 2.2 is in fact meaningfully different from the results of Daudin, which were repeated as Lemma 2.2 of Zhang et al. The difference is a little obfuscated by the notational decisions of Daudin that were also used by Zhang et al., in not explicitly writing out the arguments to the functions in question. Let's restate the results in the same terms, to compare.

Theorem 2.2 of our paper:

Random variables $A$ and $B$ are conditionally independent given $C$ if and only if

$\mathbb E_C\Bigl[ w(C) \; \mathbb E\bigl[ (f(A) - \mathbb E[ f(A \mid C)]) \, (g(B) - \mathbb E[ g(B \mid C)]) \bigr] \Bigr] = 0$

for all square-integrable functions $f \in L^2_A$, $g \in L^2_B$, and $w \in L^2_C$.

Compare with Lemma 2.2 of Zhang et al., which stated results of Daudin, rewritten in our notation:

The following conditions are equivalent to one another:

(i) $A$ is conditionally independent of $B$ given $C$.

(ii) $\mathbb E\Bigl[ \tilde f(A, C) \tilde g(B, C) \Bigr] = 0$ for all $\tilde f \in L^2_{AC}$ with $\mathbb E[ \tilde f(A, C) \mid C] = 0$ and $\tilde g \in L^2_{BC}$ with $\mathbb E[ \tilde g(B, C) \mid C] = 0$.

(iii) $\mathbb E\Bigl[ \tilde f(A, C) g(B, C) \Bigr] = 0$ for all $\tilde f \in L^2_{AC}$ with $\mathbb E[ \tilde f(A, C) \mid C] = 0$ and $g \in L^2_{BC}$.

(iv) $\mathbb E\Bigl[ \tilde f(A, C) \bigl( g'(B) - \mathbb E[g'(B) \mid C] \bigr) \Bigr] = 0$ for all $\tilde f \in L^2_{AC}$ with $\mathbb E[ \tilde f(A, C) \mid C] = 0$ and $g' \in L^2_{B}$.

(v) $\mathbb E\Bigl[ \tilde f(A, C) \, g'(B) \Bigr] = 0$ for all $\tilde f \in L^2_{AC}$ with $\mathbb E[ \tilde f(A, C) \mid C] = 0$ and $g' \in L^2_{B}$.

The key difference is that all versions of Daudin's result depend on a centered function $\tilde f$ of both $A$ and $C$.

Zhang et al. construct the KCI statistic through centering in an RKHS on $(A, C)$, which they denote $\ddot{X}$. They use a product kernel on $(A, C)$; the recent papers of Pogodin et al. (2023, 2024) noticed that this allows separating out the $C$ dependence, as done in the statements of "the KCI operator" in those papers. (This also helped substantially in avoiding the need for regressing the identity function on $C$, an ill-posed regression problem in rich kernel spaces that can actually cause serious problems; see discussion in Appendix B.1 of Pogodin et al. 2024.) Wang et al. (2025) did the same split decomposition of KCI in their equation (3), yielding the same formula.

While we end up with the same result, the advantage of Theorem 2.2 is that it allows a far more direct path to justifying the formula, rather than the roundabout method through product kernels. The role of the $C$ kernel as roughly "selecting" $C$ values for consideration, we think, is much easier to see in the Daudin-style characterization with explicit test functions, rather than relying on a connection to L2-universal product kernels.

This result also helps provide a much more direct connection to, and direct justification for, weighted GCM. In particular, it makes it easier to consider distribution-level properties and finite-sample estimators separately for GCM and weighted GCM than the approach used by Scheidegger et al; our Theorem 2.2 makes clear that the "distribution-level" weighted GCM with sufficiently rich regression and weighting functions can characterize conditional independence.

We will add further clarification of these points in the revised version; thank you for raising the concern.

[i] Pogodin, Roman, et al. "Efficient Conditionally Invariant Representation Learning." ICLR (2023).

[ii] Pogodin, Roman, et al. "Practical kernel tests of conditional independence." arXiv preprint arXiv:2402.13196 (2024).

[iii] Wang, Wenjie, et al. "Practical Kernel Learning for Kernel-based Conditional Independent Test." (2025).

---

Clarification on Relation to Goodness-of-Fit Testing

We appreciate the connection between our test and kernel-based goodness-of-fit testing [2]. Below, we briefly clarify why our construction and the test discussed in [2] differ conceptually and practically:

• The construction described by the reviewer indeed starts from conditional mean embeddings (CMEs) $\mu_{A|C}$ and $\mu_{B|C}$, then attempts to use them directly to obtain $\mu_{A,B|C}$ under the null. However, note that this would also require explicit knowledge of $\mu_{C}$, to reconstruct the joint embedding $\mu_{A,B,C}$. Such explicit knowledge (or estimation) of $\mu_C$ goes slightly beyond the assumptions typically made for conditional independence testing.

• The goodness of fit test of [2] is designed specifically for continuous distributions with a known score function or gradient information. In contrast, in our conditional independence setting, no explicit model providing gradient information is available. The KSD-based tests from [2], then, don't really make sense here. (The tests of [2] also provide only pointwise asymptotic validity, but this problem is fixable.)

• Alternatively, one might consider an MMD-based goodness of fit test, comparing the estimated embedding $\hat\mu_{A,B,C}$ to the known embedding $\mu_{A,B,C}$ (assuming, as before, that we also know $\mu_C$, or by estimating it). Indeed, such an MMD-based approach combined with a permutation test might offer finite-sample level control, and this could be another way to test conditional independence in the setting where we know $\mu_C$, $\mu_{A\mid C}$, and $\mu_{B \mid C}$.

We intentionally presented Proposition 3.1 as a straightforward consequence of Hoeffding’s inequality for U-statistics (hence labeling it a Proposition rather than a Theorem), not as a surprising or controversial result. Rather, its purpose is precisely to highlight clearly the importance of accurately estimating the conditional mean embeddings and illustrate explicitly why inaccuracies in their estimation degrade test performance.

In short, we fully agree that the reviewer’s suggested viewpoint casting conditional independence testing as a goodness of fit test is an insightful alternative interpretation – but this interpretation complements, rather than undermines, our main point about the central role of accurate CME estimation. We will add a discussion of these connections in the revised manuscript.

---

Clarification on Limitations

We agree with the reviewer that the limitations section deserves explicit expansion, and we will do so in our revised manuscript. In particular, we see our main limitation as the one identified in the last sentence of the main body of the submission: while we have clearly identified and rigorously analyzed a core issue underlying KCI-like methods (the crucial role of accurately estimating conditional mean embeddings), we have not yet provided a definitive solution to fully overcome this challenge.

Additionally, our analysis does not cover all existing conditional independence tests. Although we demonstrated that our analysis broadly applies to the class of KCI-type tests (explicitly including methods similar to the Generalized Covariance Measure, GCM), there remain popular CI tests that appear outside this framework -- for instance, the RBPT test discussed in Appendix C. While we think the underlying ideas should also apply to RBPT-type tests, given the different structure, doing so would require further analysis.

We will make these limitations explicit and elaborate clearly upon them in the revised manuscript. We thank the reviewer for highlighting this valuable aspect for improvement.

---

Clarification on the Type I Error Statement

We appreciate the reviewer’s suggestion regarding the statement: "It has a reputation, however, of doing a poor job at controlling Type I error (that is, it falsely identifies conditional dependence too often)." Without reference to clear empirical evidence or citations, this claim does appear unsubstantiated to the reader.

In the revised manuscript, we will explicitly support this claim by citing relevant recent studies, including Shah and Peters (2019) and Pogodin et al. (2024). Additionally, we provide empirical evidence in Appendix G.3 Table 1 (see also our rebuttal of empirical results to reviewer ZYGz), which demonstrates concrete scenarios in which KCI fails to properly control Type I error at nominal significance levels. We will revise to make the justification for this statement clearer.

[iv] Shah, Rajen D., and Jonas Peters. "The hardness of conditional independence testing and the generalised covariance measure." (2019)

[ii] Pogodin, Roman, et al. "Practical kernel tests of conditional independence." arXiv preprint arXiv:2402.13196 (2024).

---

We have made every effort to address all questions raised and believe that the revisions respond to the reviewer’s concerns. If the reviewer feels that these clarifications resolve the issues, we would be grateful if the reviewer might consider raising the score. If there are any remaining uncertainties, we would be glad to provide further explanations or discussion to resolve them.