On the Hardness of Conditional Independence Testing In Practice
Authors: Zheng He
Roman Pogodin
Yazhe Li
Namrata Deka
Arthur Gretton
Danica J. Sutherland
Venue: NeurIPS 2025 spotlight ()
Keywords: conditional independence
statistical testing
kernel methods
Primary area: general_machine_learning
TL;DR: Regression errors in estimating conditionals cause spurious dependence  under the null, violating asymptotic assumptions and leading to null calibration failure. Choosing the conditioning variable kernel helps power but makes bias worse.

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.

On the Hardness of Conditional Independence Testing In Practice
Zheng He UBC zhhe@cs www.uuc..o ca
Roman Pogodin McGill and Mila rmm pogodin@gmail..cmmmmm.mm.mmm.... com
Yazhe Li Microsoft AI yazheli@outlook.com com
Namrata Deka CMU ndekaβandrew. cmu edu
Arthur Gretton
Danica J. Sutherland UBC and Amii dsuth@cs wbc. ca
Gatsby Unit, UCL
arthur www.rrggggeettogalccoomm
Abstract
Tests of conditional independence (CI) underpin a number of important problems in machine learning and statisties, from causal discovery to evaluation of predictor fairness and out-of-distrin of-distribution robustness. Shah and Peters (2020) showed that, contrary 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 which we show the Generalized Covariance Measure underlying many recent tests is nearly special case and identify the major factors underlying its practical behavior. We highlight the key role of errors 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.
1 Introduction
Conditional independence (CI) testing is a fundamental task, required for almost any scientific hypothesis that "controls for" confounders; it is moreover a core subroutine in the standard PC algorithm for causal discovery and its many variants (Spirtes et al., 1993). Further recent major machine learning searning-specffic applications include checking or enforcing the fairness of a predictor or representation with equalized odds (Hardt et al., 2016), and relatedly for a predictor's 's domain invariance, particularly in "anticausal" settings (e.g. Iu et al., 2021).
When the conditioning variable takes small number of discrete values, the problem is simple to reduce to that of unconditional independence testing, for which there are many good methods: for instance, many based the Hillber-Schhiie Independence Criterion (HSIC) (Gretton al., (005) Gretton et al., 2007). When the conditioning variable is continuous, however, the situation is much more challenging: when testing whether A L B C' based on samples for continuously distributed I we will only observe one (A, B) pair for each value of C, and so we must make some form of assumption on the smoothness of the conditional distribution (A, B) C = C as function of c. Shah and Peters (2020) proved that doing so in total generality is impossible. Their lower bound, however, Section
an adversarial construction of particular distribution (discussed seem especially informative as to the widespread failures of CI tests in practical settings. Since the importance of the task means that, despite its impossibility general, we still want to pursue CI testing, must consider particular types of tests used in practice and when, and why, they fail.
which does not
Work done at Gatsby Unit, UCL.
'We will always use A 1 B C, since papers in this area use both X 1. Y Z and X 1 Z Y.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

There are a few major categories of techniques. One is the Kernel-based Conditional Independence (KCI) technique introduced by K. Zhang et al. (20IT). As kemel method, this technique applicable to data of any (potentially complex and structured) form. It has reputation, however, of doing poor job at controlling Type-I error: that is, it falsely identifies conditional dependence too often (Shah and Peters, [020] Pogodin et al., 2024). Recent extensions include CIRCE (Pogodin et al., 2023), which is useful as a regularizer for learning A but generally yields a much worse test, and Sp (Pogodin et al., (024), which helps reduce Type-I error rates, but is far from solving the issue. Related approaches include Scetbon et al. (2022), who characterize conditional independence using analytic kernel embeddings evaluated at finitely many locations, and Y. Zhang et al. (2025). who study conditional mean independence mudeendence--essenttalll the KCI statistic with a linear kernel on A.
A number of studies propose to test conditional independence by checking the covariance of residuals from regressions of and B on C (e.g.. H. Zhang et al., 2017] H. Zhang et al., 2018 Shah and Peters, 2020). We refer to this class of methods collectively as the Generalized Covariance Measure (GCM), following Shah and Peters (2020). While conceptually simple, GCM captures only linear covariance between residuals and averages the dependence over C, rather than evaluating the covariance conditional on specific values of C. Weighted GCM (Scheidegger et al., 2022) generalizes the GCM by applying weights based on C, allowing detection of a broader range of conditional dependencies. As we show in Section 3 the standard GCM corresponds to a special case of KCI with simple kernel choices, while Weighted GCM can be viewed as more flexible, though still constrained, setting of the C' kernel.
Having introduced measures of conditional independence, we revisit some theoretical work on the CI testing hardness in Section M where in particular we show that challenges in CI testing with kernel statistics arise specifically due to challenges in estimating the conditional mean embedding, kernel embedding of the conditional distribution that underpins the majority of such tests (Song et al., 2009; Grünewälder et al., 2012] Klebanov et al., 2020; Park and Muandet, 2020) Li et al., 2024). In Section we provide clear demonstration that choosing an appropriate kernel is vital to a sensitive KCI test in contrast to an implicit claim by K. Zhang et al. (201T) and the approach taken by Pogodin et al. (2023) and Pogodin et al. (2024). Following related work in other settings (e.g. Jitkrittum et al., 2016 Liu et al.. 2020 Xu et al., 2024), suggest method to select C' kernel which does help achieve more powerful tests. We observe, however, that this method can also make the problem of false rejection even more severe.
In Section 6 we investigate the problem of false rejections in KCI tests. We first analyze simple yet informative special cases, which allow analytical investigation of how regression errors in estimating conditional mean embeddings induce bias in the test statistic's moments. These insights motivate a more general theoretical analysis, where we derive formal bounds linking conditional mean estimation error to test validity. Together, the results clarify the root cause of false rejections and delineate the conditions under which KCI and GCM tests remain reliable.
2 Measuring Conditional Dependence
We first show how to measure conditional dependence with kernels. While the fundamental idea due to K. Zhang et al. (201T), our framing is somewhat different in terms of the novel Theorem 2.2
Conditional independence. We build on the characterization of Daudin 1980). To begin, we formalize the intuition that given C, A and B contain no additional information about one another: Definition 2.1 (Daudin, 1980). Random variables and B are conditionally independent given C, denoted A 1 B C, if for all square-integrable functions f E La and E L'Bc.
E f[A C) g(B,C) C) |C] = =[A,(CC) TE E[g(B,C) C) C] almost surely in C.
This definition is equivalent stating that the conditional joint distribution factorizes almost surely in C, PA.BIC = PAjo PrIc. by considering functions f and as indicators of events.
Building on this definition, we can derive the following equivalence for conditional independence: Theorem 2.2. Random variables A and B are conditionally independent given C if and only if
E C
(CC
E ABIC
[(((A) B[f(A) CJ) (g(B) E[g(B) CJ) |c]] 0.
(1)

---

for all square- intterrbeteerableeeooo functions
functioon f E LA L'g, and w E L
This result, proved in Appendix A extends the characterization of Daudin (1980) to particularly interpretable form: does any residual dependence between and B remain after accounting for C? The weighting function w(C) allows emphasizing specific regions of the support of C. Under A L C, the conditional covariances vanish C-almost surely; otherwise, there is some nonzero conditional covariance on a C-non-negligible region, which an appropriate w(C) can capture.
Kernel spaces. Since it infeasible to check all square-integrable functions for f. 9. and w, we instead focus on a restricted yet sufficiently rich class of "smooth" functions. Specifically, we consider functions that lie in reproducing kernel Hilbert spaces (RKHSs), which enable characterization of conditional dependence via kernel mappings.
reproducing kernel Hilbert space (RKHS) H. is particular space of functions A R; each RKHS is uniquely associated to a positive-definite kernel kA : A x A + R. This kernel can itself be written as (a, d') (ó (a), A A (a')),,, where Φ A + H. is known as a feature map. The defining reproducing property of an RKHS is that for all f H. and E A. f(a) = (f. (a)) We always assume that any RKHS we deal with is separable; this is guaranteed when & continuous and the underlying space A is separable (Steinwart and Christmann, 2008 Lemma 4.33).
KCI operator. The following operator, introduced (in a different form) by K. Zhang al. (201 will help us characterize conditional dependence: we reframe it, following Theorem 2.2 to explicitly incorporate conditional covariance structure f
We build this up in pieces.
First, the conditional mean embeddings ( == (A) C = c| E H. and (B|c(e) = Elóg [B) | C = c] Hy provide RKHS representations of the conditional distributions of and B given C = c. They satisfy the reproducing property (Ma(a(e), frH, (f)(A) C = =cl.
The conditional cross cross-cov operator, CaBIC, will capture the dependence structure between A and B with (f: (c))) = EABIC [([(A) - R[((4) CJ) (o(B) Rlg(B) CT) C c|:
CAB|C(C) == E ABIC
(o^(A) - (c)c((e) @ (on (B) (B))(c) C =cl E HS(Hs, H.)) (2)
Here HS(Hs, H.) denotes the space of Hilbert-Schmine operators from Hs to H.. and the outer product (a) 8 @b(b) E HS(Hs, HA) is defined by (da(a) @ @b(b)) g = (Øb(b), g)) d (a) for any g E Ng, analogous the outer product of vectors in unite-dimensional spaces.
The KCI operator aggregates these conditional covariances with information about the context C:
CςCI = N CABIC(C) vc(C)] E HS(HC, HS(HB, H.))-
For any test functions f E Hh. 9 Hy and He, the properties above give that
(f & g. Cкeι W)HS(HS. Ha) = 1o w(C)
E [(((A)) (E((A) C)) Blg(B) ICD]
ABCC
If the KCI operator is itself zero, then the quantity above is zero for any choice of f H.A. E H8. w E He. If the KCI operator nonzero, then there exist f.g. g. w for which is nonzero, implying that A J. B C. A natural measure of conditional dependence is then the magnitude of ExcI, as measured by its squared Cillbert-Shhiid norm:
KCI- |[Ckcillis
J |k((C,C") (C(C (CABIo(C), CABIc(C")) H)(())))))))))
The Hilleer-Schhiin norm of an operator is zero if and only the operator itself is the zero operator. If the RKHSs H.A Hg and He are L'-universal, meaning that they are dense in L then KCI = 0 if and only if A IL B C. Many standard choices, such as the Gaussian RBF kernel (a, a') exp(- aa Il (2))))) are L'-universal (cf. Sriperumbudur et al., 2011 Szabó and Sriperumbudur, 2018). where is the kernel lengthscale. Large values of KCI indicate strong evidence of conditional dependence, while values near zero suggest that any apparent dependence can be adequately explained by C.
TTo obtain this formulation from theirs: first, following Pogodin et al. (2023). remove the C' to C regression of the original version (also see Mastouri et al., 2021] Appendix B.9). Second, use a product kernel on (B, C); we are not aware of any that do not do this, and our framing of Theorem 2.2 makes the final product clearer.
3

---

3 Connecting KCI and GCM
Shah and Peters (2020) proposed Generalized Covariance Measure, which has been the basis of many recent CI tests (Hochsprung et al. 2023) Wieck-Sosa et al., (2025) For scalar A and B, GCM uses a studentized estimate of the average covariance between residuals, based on any regression method from C' to A. Scheidegger et al. (202)) extend the approach to Weighted GCM, which adds weighting function w; assuming perfect regressions, the population quantity becomes
E (A - E[A] [TA (B - TE| B [C]
With w(c) = 1, this is the quantity estimated by GCM; an appropriate choice of w function increases the sensitivity more types of dependence.
Consider KCI with scalar linear kernels (a a and @b( b. This makes the conditional mean embeddings (c) = (A) | C = c] E[ C = c), and similarly (Bc((c) E|B C c|. If we further pick the kernel kc c') = w(c)w((') so (c(() = w(c), then (3) becomes identical to (5) The difference is that GCM estimates the value of that expectation (normalized by the standard deviation of the estimates), while the KCI operator estimates the absolute value. This relationship is analogous to that between classifier two-sample tests and maximum mean discrepancy- -based tests (Liu et al., 2020, Section 4), and to that between variational mutual information- based independence tests and HSIC tests (Xu et al., 2024).
Consider instead A = pdd, B = Rd", with multivariate Linea@oA = (b(6) b and the same 6c w. The conditional cross-covariance (2) becomes the conditional cross-covariance matrix of shape dA x dg, and the KCI operator (3) is the w-weigtted average of that matrix. The multivariate (weighted) GCM again takes a studentized estimate of that matrix, and uses the maximum absolute value as its entry. KCI would instead use the Frobenius norm.
In this way, we can that (weighted) GCM is almost special case of KCI using simple kernels, further motivating our study of KCI in particular (especially with linear Φ. and ΦB). The advantage of the weighted over the unweighted statistic also foreshadows the importance of (o c').
4 Revisiting the Theoretical Hardness of CI Testing
In null hypothesis significance testing, we seek a test that rejects the null, i.e. claims that A.V. B C (the alternative), with no more than a probability (say 0.05) when the null hypothesis that A 1 B C is in fact true. Such rejections, also known false positives, are called Type-1 errors. A test has (finit-ssample) valid level if its Type-I error rate is at most a, while it has (pointwise) asymptotically valid level if for any null distribution, the Type-I error rate is asymptotically to reject the null when it does not hold is called a Type-Il error; the power of a test is the rate at which it does reject, i.e. one minus the Type-Il error rate. Among valid tests, the best one is the one with the highest power. A test is consistent against fixed alternatives if for any distribution where the null does not hold, the power approaches 1 as n + XC.
more than a. Failing
Impossibility result. Shah and Peters 2020) showed that if CI test has finite- sample valid level for all crteesuue-coninuuoon null distributions, then it has power no more than a for any Lebesgue- continuous alternative. This is in stark contrast to the unconditional case (or conditioning on a discrete variable), in which case there exist finite-sample valid, consistent tests (e.g. permutations based on HSIC; see Rindt et al., 2021).
Intuitively, when detecting unconditional dependence A L B, dependence can be missed (causing a Type-II error) but Type-I error arises only from sampling variability. By contrast, for A JL B C, it possible either to miss actual dependence (Type-II) or falsely detect dependence (Type-I) because subtle conditional effects of C have been overlooked. For the latter case, consider generating C, A'A B' AO0 1). extracting the thirtieth decimal place of C' as C3u E {0. 1, ......... 9), and then taking A = C3o + A', B = C3o - B'. Unless we know to look at the thirtieth decimal place of C. A and B will seem be strongly dependent and C irrelevant; in fact, however, all information that A carries about B is present in C, so A 1 B C. Shah and Peters (2020) show that for all
'The formulation as in ( should have (a) E H. i.e the function a' >> (a, a'): here and the following paragraph we identify _d with its dual by instead using a, which yields the same KCI value and other quantities.

---

test procedures, for any case which is truly conditionally dependent, the test has such a "blind spot" which is conditionally independent but "looks the same" to the test.
Interpretation with KCI. How do these issues manifest with KCI? We can show, in fact, that they arise solely because of the estimation the conditional mean embedding.
In practice, conditional independence testing relies on empirical estimates constructed from finite samples. Given observations {(a,, bi, [=) we first define the KCI statistic KCI, as U-statistic based on the true conditional mean embeddings PAIC and pac:
KCL,
1
Σ hig IS
where hig (Ke)is (K2)as (K
(6)
n(n
where (Ke)as = kolei ) is the kernel matrix for C, (K2)i. (0a ei), 02 (aj, HH) with 0% (ai,c:) (a(a:) MaIc(G) is the centered kernel matrix for A, and similarly (Ki)is (0% (br,, G.), cg)) He with o (b. (b, (Bj((s) is that for B.
To run a KCI-based test, we require test threshold f, and reject the null whenever the KCI statistic exceeds f.. This threshold i, is selected based on an estimate of the null distribution of the statistic, which depends on the sample size n, the choice of kernels, and the underlying data distribution. K. Zhang et al. (2011) show that when A T B C, nKCI, converges to a mixture of x² variables so i, could in principle be estimated by fitting the parameters of this limiting distribution. we know easily construct a finite-sample valid test with nontrivial power:
the true Pale and PB|C,
Proposition 4.1. Suppose suPae (a a) S K,. suPbEB (B b) S KB, supcec kc(c, S KC- Then test which rejects when KCI, > In = 32K V - log â has sample level at most a. Moreover, if each kernel I.2universal, the text consistent against fixed alternatives.
The proof, given in Appendix B is simple consequence of Hoeffding's inequality for U-statistics. Although the resulting test is highly conservative the correct threshold for the null distribution of KCI, should be (1/nn) (K. Zhang et al., 2011 Theorem 3), much smaller than the chosen f, the fact that avoids the impossibility result of Shah and Peters 2020) indicates that the main challenge lies in estimating conditional mean embeddings.
Relationship to model-X. The recently popular "model-X" setting (Candes et al., 2018 Berrett al. 2019 Grünwald al.. (224)) assumes that the conditional distribution of A is known. This corresponds to perfect knowledge of pAIC: for a characteristic (or a fortiori. L²-universal)
A Male uniquely corresponds to Law(A | C). Given knowledge of both A C and B C, the KCI-based test in Proposition 4.1 would be exactly valid; knowledge of only one is also sufficient using CIRCE rather than KCI (Pogodin et al., 2023 Pogodin et al., 2024). We discuss more aspects of the relationship to other CI tests in Appendix
Pitfalls of Kernel Choices for CI Testing in Practice
Since the true conditional mean embeddings are unknown, in practice must use the empirical KCI statistic KCI,, which substitutes these embeddings with estimates Alc and pByC- These embeddings are typically estimated via kernel ridge regression (Grünewälder et al., 2012) Li et al., 2024) with inputs 6; and labels A (a;) or d (b.). KCI requires a choice of as many as five kernels to operate. The original formulation (K. Zhang et al., 2011) used the same kernel for both regression steps, but Pogodin al. (2023) noted that high-quality regressions typically demand different kernels. They therefore proposed choosing separate kernels via leave-one-out validation, introducing two additional regression kernels, denoted kc-A and kc Pogodin et al. (2023) and Pogodin et al. (2024) then used ko either kCDA kc-B. implicitly assuming that good kernel for this regression will also be a good kernel for measuring dependence.
*Their Proposition makes stronger claim, that KCL, does so under fixed-regnn reculargulrizztionn ridge regression estimates for the conditional means; their argument (which was only sketched) appears to rely on property that does not clearly always hold for this estimator, but does hold with the true иAIC. HBjC. Personal communication with the authors confirmed that they agree "there is a gap" between the published sketch and proof.
5

---

CE(-1.1, -0.9)
cE(-0.1,0.1)
(E(0.9.1.1)
Marginal projection C)
CavlA, ccc]
CaviA, 00006
#. Cov(A, 0.88
.. C. =0000
-2
Figure 1: Motivating example. We simulate (BA.TB, C) following problem where T = 1 and the residual correlation 7(C) sin(C) introduces dependence that varies smoothly with C. The left three panels visualize the residuals for different slices of C, showing that Cov(A, B C)) changes substantially across C. The rightmost panel shows the residuals for all values of C, where the averaged conditional covariance Ec[Cov(A, [A, B CC] is zero. A kernel on C' with an appropriate lengthscale can focus on local regions where dependence strong: too long a lengthscale "blurs" the conditional covariance, while too short a lengthscale leaves too little data estimate it reliably,
We now demonstrate that the aforementioned choice for kc though computationally convenient can be a very poor choice for measuring dependence in complex situations. For an intuitive example, consider an engineering problem involving high-dimensional vibration data: we wish to know if the behavior of part A is connected to that of part B given vibration data C. While predicting the behavior of either A or B depends broad, long-term trends of C. the two parts may be coupled only by high- freuefrry sinusoidal resonances which require a substantially different kernel to efficiently detect. Using kc-> or kc B then results in high Type-II error.
Motivated by this, consider a synthetic problem where and B are determined as some functions of C' plus noise factors which are zero mean, but potentially conditionally correlated given C:
C C~ NO,,),,, 1), = fa(C" + TTA, == fB(() + where fA. fB are fixed functions, T, 3 O, and the additive residual terms (TA.TB) follow under So
(AA,B))CCrA (18)
1 (Nt) (.))).
(0
xC) (in( under 51.
We linear kernels for A and B, aligning closely to GCM, and lengthscale-Cc Gaussian kernel ===00) C; GCM corresponds to &c co.
ko (C, C*) = exp
Figure D iillsstrates this setup under 5): although the conditional covariance Cov C) 7² BBiraap |C] changes smoothly with C' and alternates in sign, its expectation Eg [Cov(A, B C)] zero. Methods based on this average, like GCM, thus fail to detect dependence, highlighting the need for kernels on C' that can localize to regions where the conditional covariance is nonzero.
The regressions estimating fA and fB should use kernels kc-+A and kc with lengthscales suited to those functions. In contrast, the kernel ke used for the residuals should target the lengthscale of the covariance function 7 (i.c., 1)3), which can differ substantially from the regression lengthscales.
In this setting, we can analytically evaluate the KCI, at least when using the true mean embeddings |AiC and PBjC. Details are given in Appendix F.1
We first see, using properties of Gaussians, that
KCI=
E ("CCCCC = -1 C.C²
(X.X)NNN1 [xx)(())
E
(8)
e +
for auxiliary variables (X, X') ~ Noc = =N (
12
Under the null, we
8++2
of course obtain KCI under the alternative, we can use trigonometric identities see
1 KCI
82
(288 (26
- -T 2
1
P. 22
When &o & 22 the square root term arising from (C, C*) vanishes, giving zero KCI; for la > B, the other term coming from the covariance of vanishes, yielding the same problem. Consequently,

---

Asymptotic Variance v' k
16-5
KCI
l--
SNR KClld
2.00
1.75
1.25
0.6
0.4
0.75
0.10
8-1.0.4
0.64
0.05
0.25
9-3.0.
-0.04
10.1
10"1
30
10"4
10"1
107
10"H
10
10
10"1
10"
101
10
10tH
10th
10
10"h
10"
10F
101
12
42
42
Figure 2: Effect of squared kernel lengthscale lg on KCI, asymptotic variance o and approximate test power (SNR) for different conditional covariance frequency 3, in the synthetie example under the alternative. The optimal & is selected by maximizing SNR. Different 3 values correspond to different & ranges yielding high approximate test power. Here we use noise scale T 0.1.
for each 8. the effective & lies at an intermediate value that balances these effects (see Figure left). GCM, with l 0o, cannot detect dependence here at all.
Selecting a conditioning kernel. How can we choose the right C' kernel for a given problem? One approach, following that taken in related settings (Jitkrittum al., 2016 Liu et al., 2020; Xu et al., 2024). is to maximize the approximate power of the test, based on the following asymptotic result:
Proposition 5.1. Under the alternative, there is a scalar à 2 so that as n + xc,
Vn(K - KCT) S (O 0.
As always, the hat here refers to the use of estimated mean embeddings. not to estimation of a quantity from samples; KCI and 62, depend the problem, the kernels, and the choice of JaaCc and TBjc. but not on n or any particular test sample. Under the alternative, we typically have o3 > which case the rejection probability is approximately
Prsy (KCI, > (n) ~ VvkCK
KCI
Titn
where means lim, a/b 1, Φ is the standard normal CDF, and fn is any rejection threshold. We expect In = (1/nn) following the null distribution of KCI,; the power is therefore dominated by the first term for reasonably large n, and the kernel yielding the most powerful test will approximately maximize the signal-to-noie ratio SNR KCI/0s..
We estimate SNR as the ratio of KCI, to its estimated standard deviation (Liu et al., 2020 Eq. (5)). and choose the kernel on training split that maximizes this value. (In independent work, Wang et al. (2025) used similar scheme, but with somewhat different estimator setup and with limited analysis; see Appendix C.I) We can then use the selected kernel on a testing split; as long as the two splits are independent, this will not break the independence assumptions of the test procedure.
For fixed PajC and Paic, SNR,, in fact generalizes, identifying good kernel:
Theorem 5.2 (Informal). Consider the U-statistic kernel in of KCI,; give it parameters such as the parameters of kc, in finite-dimensional Banach space such that h is smooth with respect to those parameters. Then SNR, converges uniformly to SNR over bounded sets of parameters with variance bounded away from zero; thus the maximizer of SNR,, approaches that of SNR.
This is modification of the result of Liu al. (2020) Theorem 6), since for fixed f AAcCs C Pa a the U U-stttistic structure is very similar; a detailed statement and proof are in Appendix
To evaluate whether maximizing the approximate test power is effective in practice, we compare the theoretical (approximate) power with the empirical power estimated from data. illuus trates how the analytic results KCI, 2f and the corresponding SNR vary with the squared kernel
7

---

Type-1 Error
Type-ll Emror
0.12
Frequency #=
Training size
--- m -0=00
0.8
1000
8 3
0.6
0.06
0.2
0.00
0.0
10.4
10
10-1 10
1.0
10- 150
82
Figure 3: Means and standard error (over 500 runs) of Type-I/Il errors on the synthetic example (7) with /A = cos, fn = exp, = 0.1 and different values of 3, plotted against the squared kernel lengthscale Eg The training sample size is m 200 (solid line with circles) or m 1000 (dashed line with squares): the independent test set has size 200. The significance level is set at a = 0.05. Details about testing procedure in Appendix H.1 Left: When m 200, varying eg noticeably affects the Type-I error, for certain values of E In contrast, when m = 1000, the regressor is better trained, and the Type-I error remains well-controlled for all lg. Right: The empirical test power depends strongly on both 3 and fz. indicating the the importance of proper kernel selection for kc-
lengthscale Eg in the synthetic example 77.. where the optimal l is obtained by maximizing the SNR. As shown in Figure 3 (right), the theoretical power curve (SNR vs. ( closely tracks the empirical power curve ((1 Type-Il error) vs. Ey), indicating that the selected & remains effective in practice under the alternative hypothesis.
Although maximizing test power is effective under the alternative, it can substantially inflate Type-I error in CI testing. In the unconditional settings of Liu al. (2020) and Xu et al. (2024), the null threshold is determined by permutation, ensuring exact Type-I ertor control: any chosen kernel rejects at most at rate a. In our case, no such procedure is available; instead, we rely on asymptotic null approximations, which depend sensitively on kernel choice and regression quality, making null calibration delicate. Train/test splitting prevents overfitting to the points used to select f2. yet lg can still overfit to the imperfect regressors PAIC and TBjC- As shown in Figure 3 (left), Type-I error remains controlled when these regressors are well trained; with limited training data, however, there exists range of EG values where it rises sharply. Power maximization tends to favor this region due to its higher SNR. The Eg is then selected to capture the spurious dependence caused by regression errors rather than the true signal. Hence, when the conditioning kernel is chosen based on noisy regressions, an inherent tension arises between Type-I error control and test power.
Relationship weighted GCM selection scheme. One approach of Scheidegger al. (2022) identifies a weight function by predicting the sign of residuals' product. If that prediction works perfectly, then it changes GCM from measuring the average residual correlation measuring its average absolute value, which is potentially much more powerful. As discussed, this is essentially equivalent to selecting kc, which they set as #1 indicator based on whether the residuals have the same predicted sign. While the scheme works differently than ours, it has essentially the same trade-offs as other approaches for kernel selection.
6 Type-I Error Inflation with Regression Errors
As shown by Proposition 4.1 and reinforced by the previous section's example, the fundamental challenges in conditional independence testing stem from the estimation of conditional mean em- beddings. To further illustrate this point, we examine the effect of regression errors by letting PAiC MAIC + AaiC and CBІC PBIC + ABIC. Under the null hypothesis, we can explicitly characterize KCI and its asymptotic variance in terms of A and A This enables us to quantify how regression errors distort the KCI statistic and, consequently, establish formal bounds that relate estimation error to test validity.
8

---

B is a more convenient form of textbook results about U-statistics (Serfling, 1980 Section 5.2.1) for kernel methods:
Effect on moments. The following result, proved in Appendix
Theorem 6.1. Let X') = (X), Φh (X')) with mean embedding μh Ex on (X) and the centered covariance operator C₁ = Ex (X) @ (, Yh @ ph. Define 1/1 = (pb, Enpir) and V22 ||e Ilis The corresponding U -statistic satisfies
1 Un n(n 1) 15$//5n
4 - Xy), BlU.] = -lllll Var(U,)
2 n(n 1)
12-
n
The function / in 66. for KCIn, has this form with dn (X) = =x)==x (A, C) C) and its mean 14n = Ex (on (X)] = E&g E (A,C) 6 (B, CJ @ @c(CC) is exactly CRCι in (3) Thus, under the null paa- = εксι = 0, we have E EKCI, = KCI = 0 and Var(KCI,,) == m)n V2-
KCI, has the same decomposition, except M4 = EC EABl (A, (B. | @ is now not zero if the error in Paic. Aaic is not exactly conditionally independent. As shown by Pogodin et al. (2024), with linear kernels KA and kB, under the null we have
E EKCI, KCI- E (ke(C, C²) (AAio(C), AAIc(C")) (BBc((C)ABIc(("))
(10)
As they note, we typically expect AACC and A to be relatively smooth functions of C; thus it is reasonable to expect that KCI can be nontrivial even though they were trained on independent datasets. Perhaps even more significantly. for fixed regression functions, it will generally be the case that 11= = (/gg E (,/%,) > O. This implies that the standard deviation decays only as (11/Vn),
rather than the faster ((/nn) obtained achieved A AlC. ABCC are zero. The exact variance of KCI,
in terms of AiC and A Bic is given in Appendix F22
Multi-dimensional C example. So far we implicitly presumed that the same features of C' are used both in the true/estimated conditional means and the dependence (C)) We thus extend our analysis to cases where C' is multi-dimensionn C' for both conditional means and dependence, and (2) using separate coordinates. This allows us to study how the information C drives spurious dependence. See Appendix [F.3 for the problem formulation and Appendix H.2 for the experimental setup and additional results.
considering two scenarios: (1) using the same coordinates of
Table 1: Comparison of Testing Results for Two Conditional Dependence Scenarios Scenario
Type-I Error Type-II Error
Scenario I: Shared coordinates
0.21
0.0
Scenario 2: Separate coordinates
0.10
0.08
As observed in [ Scenario 1 exhibits a notably higher Type-I error (0.21) compared to Scenario 2 (0. This increase arises from regression errors leaking correlated noise into the test statistic when regressions and dependence share the same coordinate. Consequently, Scenario I exhibits an increase in false positives. In contrast, Scenario 2, with independent dimensions, shows lower Type-I error but slightly higher Type-II error, illustrating trade-off driven by correlated regression enrors.
We further present real-world experiments in Appendix H. These observations motivate closer look at how regression errors affect the theoretical behavior of KCI, particularly its null calibration.
Effect on null calibration. Standard methods for setting a test threshold for KCI do not incorporate regression error; rather, they rely on the asymptotic distribution of KCI,, For instance, K. Zhang al. (211)) estimate the threshold using x² mixture or gamma approximation, while Pogodin et al. (2024) suggest wild bootstrap approach. In either case, the null threshold scales as (1/nn.
However, if regression errors remain fixed while the number of test points grows, KCI, = O(1) O,(1/ /n) will almost surely exceed the threshold, inflating Type-I error. This shows that regression errors must shrink as n grows, and motivates establishing the required decay rate.
Although derived under simplifying assumptions on data distribution, it extends directly since the result is independent of choices of (C()). fn(C',, and Gaussianity of residuals.

---

Asymptotics. When 11 > 0, vn(U, - U) converges to a normal distribution (Proposition 5.1 when 24 0 but 122 > O. nU,,, U) converges distribution a weighted mixture of centered X variables (Serfling. 1980 Section 5.5). We can thus ask: under the null, how likely is sample from KCI, to exceed a test threshold set according to the limiting distribution of nKCI,?
Theorem 6.2. Assume that A ALBI C. Let Z1 KCI, and Zz ~ N (KCI, Var(KCI,,)) be Zi. Let q > 0 and p (0, 1); define Ti =v(1 p)/p and T2 = 1- - -p), where T is the standard normal CDE Then the following holds for i E (1,
normal variable moment-matchern
Pr Z
S
i nnCk + T, V n2 Var Var(KKI,)..
The proof is in Appendix G.1 the case for KCI, is more precisely applicable, but using asymptotic normality gives better dependence on p. This theorem provides an upper bound on the probability that the inflated statistic KCI,, exceeds nominal null threshold. Intuitively, the bound shows that if the regression bias induced KCI or the variance Var(KCI,)) are non-negligible. the effective threshold
q/n must grow proportionally to KC1 + TVy Var(KCI,,) in order to maintain the level
In practice, we use the wild bootstrap to approximate the null distribution of the KCI statistic. Formally, it generates surrogate samples Y = Eizj hig E:Ej, where 6; are independent noise and his is defined as in (6) using AAic and PBCc. For given kernel matrix, Y has zero mean and variance closely matching that of nKCI, under the null. The following result, shown in Appendix G.2 bounds the approximation error between the wild bootstrap and moment-matched normal for rKCI,..
idd Theorem 6.3. Assume A L B C, and let Y = Σ has 6: Ej, where E; ~ NO0, 1). Let Ā be the matrix with entries has; assume ō = | | 1 1/2. Let Zn N MKCI, Var(KCT,))
Define the standardized mean shift bKei Var(k(i,.)
KCI and variance mismatch fiaar
VarlY it) n² Var(KCla))
Further define Rı 2x² (2m)-7/2 7/2, Then, for (xx) /2n" I exp(2TT.),
3 Skew(Y | H) = | 11/1 R2 = 2 5/4 and Rs =
VI-20
sup Pr(Y #ER
Zn S x))
v RR 3/2
b KCi
1/2 Nivar - 11) R2 1/2 R3,
Noting n² Var(KCI,) ~ 4n14 + 2,1 Theorem 6.3 is most meaningful if KCII = o(1/n), and 11 ol1/n), so that the standardized mean shift kRq + and the variance mismatch Kvar + 1. Consequently, Theorem 6.3 makes the asymptotic discrepancy between the wild-bootstrap statistic Y and its Gaussian approximation n.,, converge as n - oo to (Ra) + Rs + R2. This non-vanishing constant remains under perfect regression in part because of the mismatch between the normal Zn and the asymptotically wild bootstrap itself. Similarly, in Theorem 6.2] the asymptotic threshold behaves correctly when 4nv1 + 2v/2 + < (q/T.)², which is most easily achieved when V1 = o(1/n) and v/2 = O(1). Taken together, both bounds consistently require KCI = o(1 (m), v = =((1n)
KCL,, rather than (necessarily) errors in the
7 Discussion
We provided a novel framing of the KCI test, one which helped us connect it closely to GCM-based tests. We explained how this category of tests interacts with the famed hardness result of Shah and Peters (2020), identifying regression error the key difficulty, and showing bounds the excess Type-I error based on the amount of regression error. We showed that, contra the assumptions of most prior work, selecting kc kernel specifically for testing can be of vital importance in achieving test power, but that doing so can exacerbate Type-I error.
While CI testing remains fundamentally difficult, our work makes a step towards understanding how this difficulty manifests in practice, and demonstrates paths towards addressing it. This underscores that users of GCM- or KCI-type tests must carefully consider how to mitigate spurious residual dependence under the null-something that sample splitting alone does not resolve.
' 'Pogodin et al. (2024) suggest using Rademacher e;; we Gaussians in analysis.
10

---

Acknowledgments and Disclosure of Funding
The authors would like to thank Aaron Wei for productive discussions.
This work was supported in part by the Natural Sciences and Engineering Research Council of Canada, the Canada CIFAR AI Chairs program, the Gatsby Charitable Foundation, Calcul Québec, the BC DRI Group, the Digital Research Alliance of Canada, and a Google research gift.
References
Thomas B. Berrett, Yi Wang. Rina Foygel Barber, and Richard J. Samworth (2019). "The Conditional Permutation Test for Independence While Controlling for Confounders." Journal of the Royal
Statistical Society Series B: Statistical Methodology 82.1, pp. 175-197. DOr: 10. 1111/rrsbb
113400
Michael J Buckley and Geoffrey K Fagleson (1988). "An approximation to the distribution of quadratic forms in normal random variables." Australian Journal of Statistics 30.1, pp. 150-159. Emmanuel Candes, Yingying Fan, Lucas Janson, and Jinchi Ly (2018). "Panning for gold: 'model-X' knockoffs for high dimensional controlled variable selection." Journal of the Royal Statistical
Society Series B: Statistical Methodology 80.3, pp. 551-577.
J. Daudin (1980). "Partial association measures and an application qualitative regression."
Biometrika 67.3, 67.3, pp. 581-590.
Namrata Deka and Danica Sutherland (2023). "Mmd-b-fair Learning fair representations with sta- tistical testing." International Conference on Artificial Intelligence and Statistics. PMLR, pp. 9564- 9576.
Carl-Gustar Esseen (1945). "Fourier analysis of distribution functions. A mathematical study of the Laplace- Gaussia law." Acta Mathematica 77, pp. 1-125. DOT: 10. 1007 1007/BF02392223
Arthur Gretton, Karsten M. Borgwardt, Malte J. Rasch, Bernhard Schölkopf, and Alexander Smola (2012). "A Kernel Two-Sample Test." Journal of Machine Learning Research 13.25, pp. 723-773. Arthur Gretton, Olivier Bousquet, Alex J. Smola, and Bernhard Schölkopf (2005). "Measuring Statistical Dependence with Hilbert-Schmidt Norms." Algorithmic Learning Theory.
Arthur Gretton, Kenji Fukumizu, Choon Teo, Le Song, Bernhard Schölkopf, and Alex Smola (2007).
"A kernel statistical test of independence." " Advances in neural information processing systems (NeurIPS).
Steffen Grünewälder, Guy Lever, Luca Baldassarre, Sam Patterson, Arthur Gretton, and M Pontil (2012). "Conditional mean embeddings as regressors." 29th International Conference on Machine Learning (ICML), pp. 1823-1830.
Peter Grünwald, Alexander Henzi, and Tyron Lardy (2024). "Anytime-Valle Tests of Conditional Independence Under Model-X." Journal of the American Statistical Association 119.546, pp. 1554- 1565.
László Györfi and Harro Walk (2012). "Strongly consistent nonparametric tests of conditional independence." Statistics & Probability Letters 82.6, pp. 1145-1150. ISSN: 0167-7152. DOI:
10. 10160 spl. 2012.0220000 2012.02.00 023
Moritz Hardt, Eric Price, Eric Price, and Nati Srebro (2016). "Equality of Opportunity in Supervised Learning." Advances in neural information processing systems (NeurIPS). arXiv: [6100. 02413
Tom Hochsprung. Jonas Wahl, Andreas Gerhardus, Urmi Ninad, and Jakob Runge (2023). "Increasing effect sizes of pairwise conditional independence tests between random vectors." Uncertainty in
Artificial Intelligence (UAI). PMLR, pp. 879-888 8889
Wassily Hoeffding (1963). "On Sequences of Sums of Independent Random Vectors." Journal of the American Statistical Association 58.301, pp. 13-30.
J. P. Imhof (1961). "Computing the Distribution of Quadratic Forms in Normal Variables." Biometrika
48.3/4, pp. 419-426. DOI: 10. 1 1093/b3333 wwwt. 0tt13/333ee/448.44..4.1. 4.4.4199
Wittawat Jitkrittum, Zoltan Szabo. Kacper Chwialkowski, and Arthur Gretton (2016). "Interpretable Distribution Features with Maximum Testing Power." Advances in neural information processing systems (NeurIPS). arXiv: 1605. 06796
Ilmun Kim, Matey Neykov, Sivaraman Balakrishman, and Larry Wasserman (2022). "Local permu- tation tests for conditional independence." The Annals of Statistics 50.6, pp. 3388 3488.341...0 arXiv:
2112. 11666]
Ilja Klebanov, Ingmar Schuster, and Timothy John Sullivan (2020). "A rigorous theory of conditional mean embeddings." SIAM Journal on Mahematics of Data Science 2.3, pp. 583-606.
11

---

Anne Leucht and Michael H. Neumann (2013). "Dependent wild bootstrap for degenerate U- and V-statistics." " Journal of Multivariate Analysis 117. pp. 257-280. DO1: | 10. 1016/ jmmaa 2 2013
[33.003
Zhu Li, Dimitri Meunier, Mattes Mollenhauer, and Arthur Gretton (2024). "Towards Optimal Sobolev Regularized Least-Squares Algorithm." Journal of Machine Learning Research 25.18 55.181, L, pp. 1-51.
Norm Rates for the Vector-
Feng Liu, Wenkai Xu, Jie Lu, Guangquan Zhang, Arthur Gretton, and Danica J Sutherland (2020).
"Learning deep kernels for non-parametrie two-sample tests." " International conference on machine learning (ICML). PMLR, pp. 6316 63266632...mm arXiv: 2002. 09116
Chaochao Lu, Yuhuai Wu, José Miguel Hernández Bermández-Lobato, and Bernhard Schölkopf (2021). "Invariant causal representation learning for out-of-distributte generalization." International Conference on Learning Representations.
Afsaneh Mastouri, Yuchen Zhu, Limor Gultchin, Anna Korba, Ricardo Silva, Matt J. Kusner, Arthur Gretton, and Krikamol Muandet (2021). "Proximal Causal Learning with Kernels: Two-Stage Estimation and Moment Restriction." International conference on machine learning (ICML). arXiv:
F155.0
Robb J. Muirhead (2009), Aspects of Multivariate Statistical Theory. Revised. Wiley Series in Probability and Statistics. John Wiley & Sons, p. 712.
Junhyung Park and Krikamol Muandet (2020). "A meeaure-theoreete approach to kernel condi- tional mean embeddings." Advances in neural information processing systems (NeurIPS), Vol. 33,
pp. 21247-21259.
Roman Pogodin, Namrata Deka, Yazhe Li, Danica J. Sutherland, Victor Veitch, and Arthur Gretton (2023). "Efficient Conditionally Invariant Representation Learning." "
The Eleventh International
Conference on Learning Representations, ICLR. arXiv: 2212.08645
Roman Pogodin, Antonin Schrab, Yazhe Li, Danica Sutherland, and Arthur Gretton (2024).
Practical Kernel Tests of Conditional Independence. arXiv: 2402 13196
Felipe Maia Polo, Yuekai Sun, and Moulinath Banerjee (2023). "Conditional independence test- ing under misspecified inductive biases." Advances in nearal information processing systems (NeurIPS).
David Rindt, Dino Sejdinovic, and David Steinsaltz (2021). "Consistency of permutation tests of independence using distance covariance, HSIC and dHSIC." Stat 10.1, e364. Do1: 10. 1002/ sta4 364
Meyer Scethon, Laurent Meunier, and Yaniv Romano (2022). "An Asymptotic Test for Conditional Independence using Analytic Kernel Embeddings." International Conference on Machine Learning (ICML). PMLR.
Cyrill Scheidegger, Julia Hörrmann, and Peter Bühlmann (2022). "The weighted generalised covari-
ance measure." " Journal of Machine Learning Research 23.273, pp. 1-68.
Rajat Sen, Ananda Theertha Suresh, Karthikeyan Shanmugam, Alexandros G. Dimakis, and San-
jay Shakkottai (2017).
Conditional Independence Test." Advances in neural information processing systems (NeurIPS). arXiv: 1709.06138)
Robert J. Serfling (1980). Approximation Theorems of Mathematical Statistics. John Wiley & Sons.
Rajen Shah and Jonas Peters (2020). "The Hardness of Conditional Independence Testing and the Generalised Covariance Measure." Annals of Statistics 48.3, pp. 1514-1538. DOI: 10. 1214/19 AAS1855
Le Song, Jonathan Huang, Alex J. Smola, and Kenji Fukumizu (2009). "Hilbert Space Embeddings of Conditional Distributions." International conference on machine learning (ICML). Peter Spirtes, Clark Glymour, and Richard Scheines (1993), Causation, Prediction, and Search.
Springer New York. DOI: 10. 10001007777880 1-672-1-6611-- 274--9
Bharath K. Sriperumbudur. Kenji Fukumizu, and Gert R.G. Lanckriet (2011). "Universality, Char-
acteristic Kernels and RKHS Embedding of Mcasures." " Journal of Machine Learning Research
12.70. pp. 2389-2410.
Ingo Steinwart and Andreas Christmann 20088).Suppol
Vector Machines. Springer New York. Danica J. Sutherland, Hsiao-Yi Yu Tung, Heiko Strathmann, Soumyajit De, Aaditya Ramdas, Alex Smola, and Arthur Gretton (2017). "Generative Models and Model Criticism via Optimized Maximum Mean Discrepancy." International Conference on Learning Representations (ICLR).
Xixiv: 1611. 04488
Zoltán Szabó and Bharath K. Sriperumbudur (2018). "Characteristic and Universal Tensor Product
Kernels." Journal of Machine Learning Research 18.233.
12

---

Wenjie Wang, Mingming Gong, Biwei Huang, James Bailey, Bo Han, Kun Zhang. and Feng Liu (2025). "Practical Kemnel Selection for Kernel-based Conditional Independence Test." The Thirty- ninth Annual Conference on Neural Information Processing Systems (NeurIPS).
Michael Wieck-Sosa, Michel FC Haddad, and Aaditya Ramdas (2025). "Conditional independence testing with single realization of a multivariate nonstationary nonlinear time series." arXiv preprint drXiv:2504.21647.
Nathaniel Xu, Feng Liu, and Danica J. Sutherland (2024). Learning Deep Kernels for Non-Parametric
Independence Testing. arXiv: 2409 06890
Hao Zhang, Shuigeng Zhou, and Jihong Guan (2018). "Measuring conditional independence by independent residuals: Theoretical results and application in causal discovery." Proceedings of the AAAl conference artificial intelligence. Vol. 32. 1.
Hao Zhang, Shuigeng Zhou, Kun Zhang, and Jihong Guan (2017). "Causal discovery using regression- based conditional independence tests." Proceedings of the AAAI conference artificial intelligence.
Vol. 31. 1.
Jin-Ting Zhang (2005). "Approximate and asymptotic distributions of chi-squared type mixtures with applications." " Journal of the American Statistical Association 100.469, pp. 273-285,
Kun Zhang, Jonas Peters, Dominik Janzing, and Bernhard Schölkopf (2011). "Kernel-based condi- tional independence test and application in causal discovery." Proceedings of the Twenty-Seventh Conference on Uncertainty Artificial Intelligence (UAI). AUAI Press, pp. 804-813, ISBN: 9780974903972.
Yi Zhang, Linjun Huang, Yun Yang, and Xiaofeng Shao (2025). "Testing Conditional Mean Inde- pendence Using Generative Neural Networks." International conference machine learning (ICML).
Zhifei Zhang, Yang Song, and Hairong Qi (2017). "Age progression/regresionn by conditional adversarial autoencoder." Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 58 1810-5818.
13

---

A
Conditional Independence Decomposition
We recall and prove Theorem 2.2 which extends results of Daudin (1980). Theorem
2.2
Random variables A and B are conditionally independent given C' if and only if
(C(C)
E ABIC
-
CJ) (g(B) - Hlg(B) CJ) 10] =0,
(11)
for all square-integrable funciccn f E A g E B and w E L--
Proof. (i) Let A and B be conditionally independent given C. Let f E Dh and ğ E Be Then by
Definition 2.1 almost surely in C it holds that
E [[(A, C) O(B, C) = [ [ [C],
which is equivalent the statement that almost surely in C,
E ABIC
[(((A,C) -(AC)))EE(AAA (i C) - c =0.
Since this expectation is almost surely zero, it holds for any w E L3 that
(C) E ABIC
C)) (b C)
=
Given any f E L3 and any g E L. we can choose f(..c) = f and g(: = g to simply ignore the second argument. These functions satisfy f E 1a and g E L. Then, as desired,
W(C)
E (U((A))E((()) C)) (g(B) Elg(() [I((B) ABIC
(ii) Suppose (1I) holds for all functions f E L3 9 E L and V E L2. Let Pe denote the marginal distribution of C, and let PAICs Pric, and PABIC denote the conditional distributions of A, B, and (A, B) given C, respectively. Let Q be Borel subset of the image set of C. Pick w² 1 Lg. where 1g is the indicator function of Q. Substituting this choice into equation (II) yields
1
E ABIC
CI) - CI) C [dPc =0
Since this holds for all Borel sets Q, it follows that the integrand must vanish almost surely with respect to Pc. That is, for Po-almost every value of C, (TT) implies that
E @ - [ [[(B)
Given any f E L3 and any E L. for each C' = c in its domain, f(-.c) E L3 and g(-,c) c) E L3 for almost every c. Thus, for any f L' and any g E L LB we have for almost every c,
[[((A,)) o(B, C= c] = E c(A.)) C=cl E [g CC=
which is precisely Definition 2.1 This completes the proof.
B Finite-sample Valid Test with Exact Mean Embeddings
We recall and prove Proposition 4.1
Proposition 4.1. Suppose supae kala, a) S KA. supbes kb(b,b) b) S KB, supcec kolc, S KC- Then test which rejects when KCT, > in == 32K / / log has finite-sample level at most Moreover, if each kernel is L'-universal, the test is consistent against fixed alternatives.
14

---

Proof. KCI, is a U-statistic with kernel
(e (dx(a) - (Ajo(c), - - (dn(b) -Alo(()) (AIo(d))H
We have that
| = v(és(a). = Vhala,a) Vna
and by Jensen's inequality
[ajc(()) - [[0 C <l|| s Billo c= = S VRA.
so that ( Ma|c(e)l S 2VFA. Hence, by Cauchy-Schwars
(dx(a) (c) (a(a)) (A(C(()) Hall S 4KA
Similarly, (b) (c), (b((") ( )) < 4ng. Thus the kernel of the U-statistic KCI, has absolute value most 1.g.. Hoeffding (I963)'s inequality for U-statistics (c.f. Serfling, 1980 Section 5.6.1, Theorem A) thus shows that when KCI = 0,
2[m/2]
(- 1) <-
Pr (KCI, t.) S exp (- (16KABBKC)
S exp
((32KAKBNC))
a,
showing finite-sample validity of the test.
On the other hand, when A B C, since each kernel L we know that KC1 > 0. Thus symmetric application of Hoeffding's inequality tells that once n is large enough that tn KC1/2, we have that
Pr (KCI, tn)
Pr (KCI- - KCI, KCI-t.) - tm))
32KAKB ))
KCI -
2
KCI/2 A2K /FC )7
S exp
-(n 1)
I exp ((n-
and hence for any fixed alternative, the probability a Type-Il error goes to zero.
C Relationship to Other Testing Methods
Relationship other CI tests. One major category of conditional independence are based on variations of approximate permutation, i.c. that samples with similar C' values have similar A and B distributions, which can be exploited either by "swapping" samples with nearby C values (e.g. Sen et al., 2017; Berrett et al., 2019, Kim et al., 2022) or by producing bins of C' values and assuming the distribution is constant within (e.g. Györn and Walk, 2012). While this approach might seem fundamentally different than the regression or conditional mean embedding approaches, we emphasize that is not. For instance, Kim et (2022) assume that the Hellinger or Rényi distance between A C = and A C = é is at most constant times ||c- e'Il, and the same for B; similar assumptions underlie all methods this type. This smoothness justifies using the distribution A C = é' to estimate A C = c for some similar value of c' Bearing in mind the one-to-one correspondence between mean embeddings and distributions, this assumption essentially equivalent to using nearest-neighhor type estimator for Pajc PBjc.
Another recent CI test is the Rao- Blackwellized Predictor Test, RBPT (Polo et al., 2023). This method is regression based, but based on comparing predictors of B A, C' to an averaged predictor of B C. This structure makes harder compare the KCI-type tests directly, but we note that relies on good estimate of A C' and hence is essentially in the model-X X framework. Like most tests in this area, suffers from severe bias problems, as discussed by Pogodin al. (024)).
Smoothness of distributions. In the model-X setting where the conditional distribution is only approximately known, Berrett al. (2019) Section 5) bound the worst-case inflation of the Type-I error for two common model-X tests by at most the average conditional total variation distance between the true distribution and the approximation. Generic distribution modeling methods are likely to succeed in this sense only if the distribution changes slowly in total variation. Similarly, the bound of Kim et al. (2022) in a permutation case assumes that the distribution changes slowly in Hellinger distance; note that the total variation distance is upper-bounded by a constant times the
15

---

Hellinger distance, and so slow Hellinger change is a (slightly) stronger assumption than slow total variation change.
By contrast, while the precise conditions for effective conditional mean embedding estimation are complex (Li et al., 2024), we can roughly expect them to work when the mean embedding changes smoothly as function of C; that is, the maximum mean discrepancy, MMD (Gretton et al., 2012), between A C' = and A | = c changes slowly as a function of c. It is easy to see (e.g. Xu et al., 2024) that for bounded kernels, the MMD is lower bound on the total variation. Thus, in the settings where the bounds of Berrett et al. (2019) and Kim et al. (2022) are applicable, we can roughly expect that AAac. Pajc should also be learnable. The reverse, however, is not true: the total variation is a much stronger distance than the MMD. i.e. there are many cases where the MMD is quite small and the total variation is very large. For instance, the Gaussian- kernel MMD between two nearby point masses will be small, while for total variation and Hellinger it will be maximal.
C.1 KCI-Power method
Wang et al. (2025). in concurrent parallel work, propose selecting kernel parameters in KCI by maximizing a signal-to-noise ratio, using a scheme closely related to ours. Besides, they jointly tune the kernels ka, kR, and kc, whereas we optimize only ke: tuning A and kn would require retraining the regressions and thus incur substantially higher computational cost. They recommend grid search rather than continuous optimization, arguing that estimating conditional mean embeddings introduces intrinsic bias, making gradient-basee optimization unstable for improving test power. This limitation is consistent with our observations in Section However, while they attribute the difficulty to continuous optimization, our results show that the real issue is regression accuracy: once the conditional means are well estimated, gradient-based tuning is stable and effective. Although they also note that conditional mean bias can make kernel selection unreliable, our theory explicitly identifies these pitfalls and clarifies the underlying mechanism.
Methodologically, they use the generic unbiased KCI estimator for power maximization, as in (6) (which we use for analytical convenience). In practice, we recommend the HSIC-like unbiased estimator in (20); empirically, this centralized version mitigates conditional mean bias, preventing the selection of kernels that emphasize correlations between regression errors. They also calibrate the null using the Gamma approximation, while we rely on the wild bootstrap. Since Gamma calibration is known to be conservative (Pogodin et al., 2024, Appendix B.2), this accounts for their stronger Type-I control but substantially higher Type-Il error. We describe our testing procedure in detail in Appendix H.I
It is also worth noting that Wang et al. present decomposition of Ekcι identical to ours, although they derive it from the earlier formulation (as in Footnote 2 rather than from our first-principles derivation.
D Generalization Bound for SNR
For a formal version of Theorem 5.2 we generalize the proof of Liu et al. (2020 Theorem 6) to other second-order U-statistics.
Given a set of samples .I....,A X, and a function h, define
Un
Σ M(X,, Xy),
U EXXxX'X)),
n(n 1)
ISiFi5n
2
2
3 11.n
4 n
X(X,.xg))
4
Σ
n2
k(X,,x))
0f 4E Var Varlh(X, X') 1 xx]] x
3
n
SNBB.. == Un/v VO 0 +1,
SNRA- = U/V03, +
and let SNR = SNR.. We have constant À 2 0.
Here Un is the usual second-order U-statistie; we assume, without loss of generality, that (x x²) h(xx,, x) for all x, x'. We know from Section 5.2.1 of Serfling (1980) (also see Theorem 6. that Var(Un) = 4v1 + (LLnr)). The estimator Vi, follows the biased estimator used by Liu et al.
16

---

while Danica J. Sutherland et al. (2017) used an unbiased variance estimator, the biased estimator much simpler and also performs better this setting (Deka and Danica J Sutherland. 2023
(2000;
Note that with X = (A, C), substituting h in the above formulas with B, (A,,,, given by
(C, C*) (A) (A')) (Aac))))
we have U = KKCI, oh is 03 and SNR is SNR.
Theorem D.1. Let hw X x X - R. be a set of functions for each w E S2 such that:
(i) The has are uniformly bounded: supwen supa,a' ex (hw (2., x²)l S por some 1 S p < co.
(ii) Ot is a subset of some D-dimensional Banach space, and supwenllw|| - R.
(iii) The functions are Lipschitz in their parameterization: there is some L oo such that for all x, x' E X and w.w' ws E D2 (1, - h (x. x')) S L[[W-w' w'll
Use U and similar to denote the quantities defined above with the function hw- Let St S St be set of parameters for which (.m)) 8. Take x 1n-1/3, Then, with probability least 6,
sup
|SNR (w) R.A
SSNR
P
e
448p
2s
L+
2 log 4 5 +2D log log(4RVT))
72p² Vln
28
Vl
1/6
wEn,
Thus, treating p and l as constants, we have that
sup |SNR (4) - 10 wEit
-
1
+
+1+
S m2///)
1 L ++ D Dlog(Rr) Rn) + log 8
1/
This further implies that if SNNR has unique maximizer w Ua the sequence of empirical minimizers of SNR (w)
converges in probability to w*.
-
The assumptions in Theorem D.I agree with those of Liu et al. (020). Their Appendix A.4's bounds on L directly apply to the of KCI we only consider changing kc, as we do in our experiments. These techniques could be readily adapted to changing other parameters, whether k or kg (if the
regressions are also updated appropriately) or parameters inside PAIC and PBiC- We emphasize,
however, that doing so only increases SNR; any of these operations could increase the probability of rejecting the null under the alternative, but they will also increase the probability of rejecting the null under the null, further inflating Type-I error.
Proof. Let o nn = of
+ A and 0g
=o S + A. We begin with the decomposition
((w)
((w)
sup |SNR (w) wEf,
SNR(W) = sup
(w)
(w)
WEi,
5/1
((4))
(w)
(w)
U(w)
Ulwn
< sup wE
sup
sup WED,
(w)
(w)
(w)
(w)
(w)
(w)
"1.A
wEn,
D1.A
D1
D1
D1
Now notice that |
S p.
2 2 Vs²
(w)
+ X 2 s, and
D.
(w)
Vā. Hence the first term is
U&!ل) (w)
U,(4)
( )m )2 - (a (w)
|W(W]] WEl,
sup
sup
0 (w)
(w)
n
(w)
(w)
WEB,
0 Dimn,
Sind
Bmi - 0 Ain
sup 10 (w)
)mn,)) (o))))
VXVa X(v + + vX)
WEfl
P
sup (o(w) (w)
(2 2
(o {1
(o (w)
52 R
wEll
17

---

the second is
U (w)
(-())
(o >n,))² (o )2
pA
|
sup
(w)
σ (w)
sup
(w)
(w)
x + 0 (w)
(w)
23
wE
D1,2
wel,
91.A
91
and the third
((w)
U(w) - vlw) (w) D1
1 sup (r(W) - U
1
sup
(w)
(w))
sup
wEl,
we
8 well,
Thus we have reduced to needing uniform convergence of Un and of n..
Propositions 15 and 16 of Liu et al. (2020) show this, up to replacing their with our p/4, their Ro with our and their La with our L/ 4: this can be seen by inspecting the proofs. The results become
2
2 2
Pr
sup (T(w) - w(w) wEn
PV
+2D +2Dlog(ARvm)) + -
-
Vn
Pr sup WER
(w) m1 2 (o (w)
64
TV 2 log g
2
9p² 1 +2D log(( + 8Vn 22222222 tz2zo/
2116
vn
Combining the results, it holds with probability at least 1 - 8 that the worst-case error su,wen. [ (w) SNR(W) is most
pd
2p
448p
4
2
32p²
72p²
+
2 log 2D 2Doog(RVv))
+
svn +
L
2s3
8
82 A2
82 s²nin
821VX
Plugging in x = in yields
pl
2p
448p
V 2 4 + 2D 2Dlog(ARvm))
2
32p²
72p
+
2s 3
syn
V
syn
V
V
We assumption and that 448 > 32 to get slightly looser but simpler upper bound
of
pl
2p
448p²
4 + 2D log(4Rvn)
72p3
L + 2 log 5
+
2/3
Vls2n5766
which reduces to the result in the theorem statement.
The final result is a standard consequence of the prior statement, as in Corollary 12 Liu et al. (2020).
E U-Statistic Moments for Hilbert Space Kernels
Theorem 6.1. Let ((X, = (X)(X), (x()))) with mean embedding pa = Ex dh and the centered covariance operator Cn Ex (()(() @ (x() -th ph. Define vs (pn, Enjtr) and
U2 = e The corresponding U-statistic satisfies
1
2 n(n 1) 12-
Un n(n 1) ISiAiSn
((,,
EUU U 11pnn1? Var(U,) V1 +
n
Proof. Un is the definition of a second-order U-statistic. We have that
EU, E X(X,X')
x.X
E (x))). x. X.X.
(X), E. dr (x)) = (n) = 11
when Ph exists in the Bochner sense, gl (X)]l 60.
18

---

For the variance, it is a standard result that (e.g. Serfling, 1980
Section 5.2.1):
Var(Un)) = 4(n - 2) Var [x(X.') x + n(n - 1) n2n2 - 1) X Lx
Var
Using the law of total variance,
Var [b(X,,')] = Var E [h(X,x)) xx] E Var x(x, [x]] [x] XxxX X
and
n(n - 1) Var(Un)
4n - 6
Var E [x(X x') xx] [x
2
E
Var (xx xx]]
X
n(n 1) x
Lx
We can now compute that
x [x)
x] = (on (X),
Var
E x
[XX X')
xi]
I X
E (XX X') x
E E [XXXX) x7) X xxxx
X
( (X), ) (1h, Mar)
Fecu on (X)) (X), mn) - (un: pa) (pins man
Kun (0ha (X) @ (x) - -m s un)
-n (nn JE on (X) @ (x() p4n @ un) un) (enn, Capsn) = V/-
The remaining term is given by
MXX x] ( (XX,) xx) 2
Var Varlh (Xx, | x] = xxx
x1xx
(n())) (1H (0)
JE x1x
X (x), ox()) ((()))((om)) (on()),
E. xixx
(Du(x)) ( ( (x()') @ (X') ur pb) x1x
(X), (X))
E Var [MX,X') x] R((b(()) (X), Cnnph (X))
X XxIX
E(dn(X)= @ on (X), Cn)us
E (xn(()) (X) 2 dh (X), Cn HS
(Cn + pn @ ph, Cx) = 11 + 12.
Combining, we find that
4n - 6
4
2 n(n 1)
Var(Un)=
+ n(n - 1) (ur + U2) = v1 +
V2.
n(n 1)
F Analytical Example
F1
With correct regressions
KCI as an expectation under a bivariate Gaussian. Under the assumption of linear kernels
Φ (a) and @b(b) = b, the conditional cross-covariance operator with correct regressions can be
19

---

written as:
AABIC = E [A - -
c)
ABIC
E
[AA fa(C)) (B fs(()) [c]
ABIC
C.EAmcCrArz [c]
=7\(CC
Since C, C NV 1) independently, and ko(c,)) = exp (-leze-2 28%
then the KCI statistic
becomes:
KCI = 7 E
C.0º
Using the fact that C, C" are independent standard Gaussians, this becomes:
//
(c-d)²
KCI
exp
2
exp
26
rlc)(d)
4 //
(13 + +1)²
2od (l8 1)
(e)r(d)ded,,
exp
2T
2
Define the vector
and write the integrand as bivariate Gaussian density with covariance
matrix E. That is,
E P +2 J
/ ox(c,d)) dedd''
KCI
V
where Φy denotes the bivariate normal density with zero mean and covariance matrix
Σ
dct
+1
Eg
+2
We may thus express:
KCI = 74 V
E
[())(X)),
13 +2 (X.X))Nic
(10)
with auxiliary variables (X,X') ~ Noc = N
Exact expression for KCI We can analytically compute both the population KCI value and its variance to generate the theoretical curve shown in Figure 2 Under the alternative hypothesis, suppose conditional dependence takes the form 7X) = sin sin (3X). Then the KCI statistic becomes:
&
KCI = 4
E (X.X/NNic
[sin(3X) sin()
P 22
11
E (X.X"~~ic
[oos - (x)) c3occo3X +X)),,
2
& + 2
Now note that X - X' and X X' are linear functions of a jointly Gaussian vector and hence
Gaussian themselves. Since (X, X') ~ NN0,, E), the random variables Zi = X X', Z2 = X + are zero-mean and have variances:
2
Var Var(Z))= (Zi)= =2
Var(Zz) 2.
R. +2
20

---

We now compute the expectations using the identity for the cosine of a Gaussian: E[cos(82)] exp
32 Var ()) Thus,
Ex.x' [cos (3(X - -x')] = exp
-32
2
Pg +
Ex,x' [cos (3(X + X1)] exp (-83)
Substituting into the expression for KCI, we obtain:
KCI 74
OC + )²)
))
OC
exp
82
exp (-8+t)
2 cc +2
71
2.32
2 cxp(
V
OC +2
Oc
exp
OC +
Exact expression of variance of KCI,, The variance of the U-statistic KCI, can be decomposed into three components, described in Appendix We now provide exact expressions for each term under the alternative hypothesis.
(N E (TADC,AEE")ABCC)) A'B'
E2' ABC
(. E A'B'C
[" IABC))
2)
E ABC
E Barr''' 1c] 21
=r E
E 1r |
E kklcC,o) C")
C
- Eg
(1-27 2, (1-)) (g
27
7888
(1 (1+27((8X))
h(x))
1C6 1)(E + +3) X~N10,
2
XnNV(
S expl
18+1
82
1 1
(e' + 1)(e) +3) - exp
2,32
2,32 + +1) c +3
VIC + 1)(E' + 3)
+ 1 exp (-
282 + +2)
1
(-
2,32 cc
4
( +1( +3)
+
exp
(l6 + 1)((z + +3)
Besides,
Um = ABC,A' BCC
MAAC,,''B''))
KCP.
Also,
2/4 = [A(ABC.AAB
( P
=78 E. (C,
E
ITATB"
E Ir [C']]
C.
A.B
A
(C (C-C))
C')2
8 E
exp
(1+27 277(C"))
C,0º
c
4 4-2exp
(-
23 +2)
+exp ( (- 23
b2 +
1
Pg 2
8.32
22 + 4)
2 exp (Ce + 2) + +4) )
1
( -232g2
(-2 2exp
(6 + 2) + +4)
2 exp
l +
Therefore, the variance can be obtained by combining those three terms together:
Var(KCI,) (4n 8)4, (4n 6) Fm + 2v.
n(n - 1)
21

---

F.2
With regression errors
Suppose the conditional mean embeddings have errors, that AАiC = MaaC + Aaic and Anic MBIC + Anic. where Aii and Ancc denote the respective regression enrors. Then the conditional cross-covariance operator becomes:
CAB|C(C) - ABIC
[[A
- (B c]
= E
[(A fa(C) - -nIc(()) - ff((C) - Amc(C)) [
ABIC
-EABIC [(Tra ( (TrB- (BIC(C)) c|
=r²x(0)+ + AII((C)AB((())
The final equality follows from the assumption that the regression estimates are obtained using an independent training set, and are thus independent of the test-time noise ''A and rg. Consequently, the cross terms involving T A (C' and rB A (Cc(C) have zero conditional expectation.
Thus, under the null hypothesis (A B C), the KCI with noisy conditional means becomes
KCL= CC
Under the null hypothesis, the variance of the U-statistic KCI, decomposes into the following three components, noting that Eacr( (rx
and Egjc [aic|r="]] =
((
Ve
E ABC
ABB'C ko(C,
Anc((C)
(TTAA' - ATc"" - ]
(TrA- - (ana)AA(()P(mraaaAp))) CacCCo//msnncdoooyyy///CCCCCChaa (BI 2 ]
E ABC
E
(7² AAC ABC E [
Um
0C
2 Io (CC A (TTB Anc)))(()) (aCC::/--AMMaCTy------aAannaaaaa ABIC(C))
=E (C, + (C)( ACC + (C)) (C)))
Combining these three terms we get:
Var(KCIn)) (4n 8)ve (4n - 6) + 20
nnn 1)
F.3 Complex conditional dependence scenario (3-dimensional C)
We now extend our motivating example to a more complex setting by considering a three-dimensionnl conditioning variable C = (C1, C2, Ca). Specifically, we define random variables:
C Is), A fa(eA TC) TTT B fB(e C) TTB.
where e and é are indicator vectors selecting specific dimensions of (one entry equals 1, others 0), determining which dimension influences each variable. The additive noise terms (TA,TB) are conditionally dependent via on <(ec C"), as previously defined.
We employ generalized Gaussian kemnel for with dumension-speciffe (squared) lengthscales e
as commonly implemented libraries such as sklearn: kc,C,, C*) exp (-Σx
(C,-C/)
26
22

---

We assume regression models are trained specifically on the relevant dimensions (as selected by and n), effectively ignoring irrelevant noisy dimensions. Thus, ( C*
(e CC-
Majc(ea CC) and A ( TC C) = ( T C) - Paic(es T C)) depend only on the dimensions directly influencing A and B. The noisy KCI statistic KCI, using linear kernels for A and B, becomes:
KCI
=E Ioo(C
CC Tee (C) JC) E(ea <(eATC, eB Tdi)
cc c + 2
Xn) x X() X²))
T where Xc ec Xx XB) AAic(es XX) X). Similar to Appendix F.1 X is
an auxiliary variable, and for i = 1, we have X, X Nio..
Kernel lengthscale selection and regression errors critically influence test performance. We discuss two illustrative scenarios:
Scenario 1: Shared-coordinanl dependence (e. = eg ec): When A, B, and their condi- tional dependence all rely on the same coordinate (e.g., Cj). The KCI
3
KC1
II
E
+2
Specifically, under the null hypothesis, the regression error will leak "dependence" into the test,
KCI
E [[XX
+
Explicitly, this is:
Cx CC
KCI
II
E
Axc((Xi)AMc((() BIC(()))
Scenario 2: Soprraate dependence (distinct e EB, EB, ec) When A, B and their conditional dependence each utilize distinct coordinates (e.g., C1, C2, C3 respectively), because of the independence between (X A, Xn) and Xc, the KCI becomes:
CE: +2
KCI
II
E (Xa))
X2XXX
where we can further decompose the noise
[[ Xa) X3)] = E (
E [[ABc(Xx)AB AXI)
Under the null hypothesis, the KCI becomes
E. PC +
KCI
II
E (ACc())))))(()) [(ABc(X3)4BI((33)
G Type-I Bound Proofs
G.1 Moment-matched normal against a threshold
Theorem 6.2. Assume that A C. Let Zi KCI, and Zz N (RCI, Var(KCCI,)) be
normal variable noment-matcher to Z₁_ Let q > O and (0, 1); define Ti = /(1 p)/p and T2 = -- p), where tb is the standard normal CDF Then the following holds for E (1
Pr Z, > 9 <P n
ifq 2 nKCI + T, V n2 Var (.CC).
23

---

Proof. Notice that, when either bound is satisfied, we have that
_ - KCI /V Var(KCI,)) 2 T.
The result for KCI, follows by Cantelli's inequality, which slightly improves the better-known Chebyshev inequality for one-sided bounds; it says that for any random variable X,
Var(X) Var(X X) + X2 AA 0,
Pr(X 2 [[X] + A)
and so, equivalently,
EX Var(X)
Var(X)
1 1 +
Pr
2t) $
Var(X) t2 Var(X)
Plugging in T1 yields that
Pr KCI, 2 2 s Pr
KCL, KCI
1+ 1=2 P.
Var(KCl))
P
as desired. The bound for Z2 is similar:
Ze E Z2
Pr Z2 Pr
2 2 2- (1-11)) -p)
=1 - 11- p)) p.
(2)
G.2 Alignment to wild bootstrap
We provide bound on the distance between two null distributions used in testing:
1. Wild bootstrap distribution given the test dataset.
2. Normal approximation to the test statistic nKCI, when regression errors are present.
Setup. Let fl E |R" be the kernel matrix with noisy regression under the null hypothesis, with entries Hij = hij. We define random variable
Σ
hej
E
n
ISidiSn
where {e:)== are i..dd (N 1) variables. It known from the results of Imhof (1961) that the wild bootstrap distribution of A is the same as
(Y = = Σ X (X² 1);
where X,. ~ 1N( i..d., and {Ar}-= are the eigenvalues Á n.. This centered form (X? - 1) ensures that E[Q] = 0. The variance is Var(Q) -" n² tr( fT2). And the third central moment of Q is n X (133 (see Buckley and Eagleson, 1988). Moreover, the limit - 00, Q and nKCT, under "perfect regression" null converge to the same distribution (see Leucht and Neumann 2013 Theorem 2.1 and Pogodin et al. 2024] Theorem 4).
When regression errors are present, the errors include a small but nonzero leading variance term, and thus the null distribution of KCI, becomes slightly non-degenerate. By suitable central limit theorem argument (analogous to Theorem 5.1 KCI, approximately normal for large n:
[
KCI)
1).,
V Var(KCI,))
24

---

Recall that for recond-ordet U-statistic with kernel his = h(X,, Xÿ), standard formula (Serfling. 1980, Chapter 5.2) gives
4(n 2)
Var(KCI,,)
Var (ar[)(
+ n(n - 1) Var [ar[hsg]
n(n n - 1)
4(n 2)
2
2 nonn - 1)
nnn - 1) Var (Ka)
+ n(n - 1)
1E (12)
(E h1;)))
Meanwhile, for the wild-bootstrap statistie, have
Var(Y M) Var(Q) 2 Σ x = 2 tr(Af2 _ 2 [1 as n. + co.
n²
If the test correct regressions, under the null, E(hyy] Var, [Byss)) 0, then Var(Q) converges exactly to n² Var(KCI,) In the presence of regression errors, however, note in n² Var Var(K) that the factor 4 Var, [E, (hag) can remain substantial if Var;(E,,(hs) does vanish. This Var, (hag) term can contribute larger leading order when multiplied by n. Hence, if Var, (E, [E, (hi))] )] is non nogleegiig,,,e, for large n² Var(KCI,,) can be bigger than Var(Q).
In practice, we use wild bootstrap sample from the distribution of Y H under the noisy-regression null to determine a test threshold. Mcanwhile, the actual test statistic n KCI, can be approximated by normal variable
S s 2n ~ N (nKCI, n² Var(KCI,))
Hence, want to quantify the distance between the distribution of Y H and the distribution of n n.n. Concretely, we measure
sup Pr(Y A S x) - Pr(n Zn S x))
(12)
zER
A small supremum indicates that Y H (wild bootstrap) and nZn (normal approximation under regression error) produce nearly identical thresholds, while large value implies a more significant discrepancy between the two distributions.
Theorem 6.3. Assume A B C, and let Y = E hyye,e where E iid NOO, Let Ā be the matrix with entries haz; assume ö = |1 | 1 < 1/2. Let Zn ~ M(KC,, Var(KCI,))
Define the standardized mean shift kK Var(kC
KCI and variance mismatch Fiaar n² Var(KCI..)
VarlY H
Further define R1 = 2x Skew(Y H) = $ 122x² | HRI R2 = 2-0/4 7- and R3 = (2m) 7/2, Then, for (xx) = V2n x exp(2
3
VI-20
sup Pr(Y A < x) -P(nn Zn S sx) zER
s v R
3/2 + booo + π KKvar - 11) R2 1/2 RRa,
Proof. The overarching goal is to bound supzer Pr(Q x)) - Pr(S < x)), where Q is a centered weighted sum of chi-squared variables (which, as noted above, is exactly the distribution of Y H), and S rzZn is normal approximation to a U-statistic-based test statistic. The classical approach (Buckley and Eagleson, 1988; J. Zhang, 2005) utilizes characteristic functions (++()) and the Fourier inversion formula control the Kolmogorov distance between distributions.
Let T be a generic random variable with characteristic function u/ (t) = E. log( (t)
admits the power series expansion
(it) 1
log(s)(()) = Σ (T) 1=1
then the constants (T) for l f 1,2....) are the cumulants of T (Muirhead, 2009 Sec. 2.4). In particular: (T) = E[T] is the mean, (T) Var(T) is the variance, (T) E [[T))
is the third cumulants, with (T)) Skew(T') being the skewness.
25

---

Recall that Q = Σ== Ar (z? 1), where Z, ~ (O,, 1) i..d. and { are positive (eigenvalues of H/)). By construction,
(Q) 0, = = _ X K2(Q) Σ
= (1- d 2
Σ X (1 3).
Since {A, - are the eigenvalues of the Hermitian matrix H /n. the cumulants can be expressed in terms of the Schatten norms of H /n.. For simplicity, define H = H /n. The Schatten p-norm of H is
|
Σ
X
if S 0o, and | = max X
ISrSn
8| 8 which provides more interpretable way quantify Q's variance and skewness based on the spectrum of H. Define the normalized version Q" by
In particular, (Q) = 21| 111 and (Q)
Q' Q-
Q
Var(Q)
Vk²(
Hence, (Q"))) 0, 02 1, = 8 (Q) and for / 2 3,
K2(9)
k2(Q") = (K)
For ease of comparison with Q, define
S S
(K2 M n KKC n² Var(KCI..)
(Q)
K2(Q)
The distance sup, Pr(Q < x) Pr(S s x) equivalent to comparing Q' and S*:
suPzeR
Pr(Q"= S x) - Pr(S* < x)).
By results of Esseen 1945 page 33), we have
w/ (1) vs- +00 <
sup Pr(Q" <x) - Pr(S" xx)
sup
dt,
2m _oc
zER
t
where v and vis- are the characteristic functions of Q" and S respectively.
dr
(
(1--it
2d.
-1/2
Q (t)
exp
it
(122(())
K
k2/²(Q))
nKCT
22 n² Var(kCTn,)
Us (t)
exp
it
K2 x2)
(Q)
To handle the integral
ui (t)
ws (t)
dt,
is standard to split the domain at [t] = A for some positive A. Define
- (t)
wss (1)
w (t)
dl Is = / JMIA
v2g- (1)
I
dt, Iz jH|
dl.
1114
t
Then,
ve- (t) t)s- (t)
dt < I + I2 + Iz.
Optimizing over A balances these different regions. This is classical technique in Fourier-based proof's of Essceentyee inequalities.
26

---

Bounding 4. We decompose I based on the characteristic function ratio. Define
r(t)
log (Vge (t)) log (t)).
Then
/ I4SA
vq- (t)/ (t) - dt
11
1 (t)
exp(r(t)) -1 dt
JuSS
1 (1)
1 |r(1] exp((r(())) dt,
/
11bs- (t)
J4SA
|t]
where the last step comes from the inequality cxp(2) - 1| ||| exp(1=)).
We use the following expansion bound for real 0, which be easily verified using the mean-value theorem (see also Buckley and Eagleson, 1988: J.-T. Zhang, 2005):
0²
log(1 + i0)
10 +
- /0/
(13)
Concretely,
r(t) = (1t Er-1
(2()))1
d
+
Σ
log 1-it it
(Q)12
2
+ (it
Ko /2/2(()) (Q)
n KCI
8² n² Var (KII))
2 (Q)
r=1
By bounding each log(-) via the expansion
we obtain
1 Dm 12
n KC1
+ 12 2 X
n² Var(KCI,))
Ir(0) S 6
+ il
(Q)
K- (()
K2(Q)
(k)
Recognizing Kz(Q") = 8 E, 12/1K/222 (2) and Σ, X2 = k2())) we rewrite:
lr(1) s 1 1110 kg²)) + |8|
n KCI
12 n² Var(KCT..
+
(14)
6
K2 K22 (Q)
2 K₂(
Hence, for [t| A.
I exp(I((A)) /
- An² Var(kL..)) 2k2((1)
10 kg( (2x(00)))
1
cxpl
MSSA
6
nKČI
|t n² Var (KCI,)
- 11 dt.
(2)
(2)
This splits naturally into three integrals:
h S exp(Ir(A)))x, kz(Q"))()))))))))))))))))))))k /
1² expl 1apf-" Fn2 VarlkCln.) dt (e)
6
185A
+ exp(Ir(A)))
n Var(KCI,))
-1| 1/ / |t| expl
An2 Var( dt
(2)
111SA
(k2(
exp((r(A)))
n KKC (Q)
exp nnn Var(KCI..) dl.
(Q)
In each term, the integral is bounded by Gaussian-like tail and one can get explicit numerical constants:
3/2
1 S 1 exp((I(A))) kz(9")
K2(
+ eexp(Ir(A)1)
(2)
1
3 3V
n² Var(KCL,)
n2 Var(KCI,))
KCI
22 2n exp((r(A)))
(15)
V Var(KCT,.)
27

---

Boudning 1z. Recall
12 = / 111/
(t)(tt)
dt,
6
where
s- (t) = exp it K2(Q))172
RCI
nn² Var(kCIn)
(k,
Since | (f) exp(
e" n² Var(KCI,) ) we have (Q)
exp n Var(kCln) dt.
12
|1|> (t]
2kg(
Next, the fact that [t] A implies
12 Hence, 33.
12 -
A3 expl
t²
en Var(k)I..)
dt.
2kg(())
|t/
3/2
2m
K2(
(16)
A3
n22 Var(KCIn)
Bounding 1z. Recall
1QQ(()
I3 J
dt.
Following J.-T. Zhang (2005 (B.3)), we have
-4
11 (t)l S
Σ k=1
Th (2t2))
where Tk Ejishe Oj Ojs ... Oi and ar
22
X
Let 8 maxigrSn Or.
Σj 23
Using induction l we can prove that,
Th 2 k.
When < 1/2, n is at least 2, such that
| (t)l S T22
228) (2)))/
Recall that || (E* x2) and || maxigrsn A,. If 1/2, then the largest eigen- value contributes less than half of the total squared eigenvalue mass. Since 5 = ||/1///| [ |
11. 5 < 1/2 implies || 2 112
Assume d 1/2, follows that
/
vh- (1)
dt S 23/ 225) 28/-1/2
1-2 di -10) (17)
J
J1AA
Combing I1, Ig and 13. From 15). (16). and
we obtain
23/4
KCI
K2(
+ < VI- 31-28A4
2nT exp exp((r(AA))
+exp (exp((((A)))
V Var(KCI,))
Var(KCI,))
3/2
1 π
exp((r(A)) ks(0)) + V2T
(Q)
+
3V
3
A3
n2 Var(KCI,
(18)
28

---

Here A > is splitting parameter, which we leave unspecified but may be chosen arbitrarily, and the quantity [r(A)] bounded as in (14)
Final Assembly. Combining the pieces, have
vq- (t) ths- (t) dt S (11 12 13)
which in turn implies the Kolmogorov bound
1 (T 12 + Is).
sup EER
Pr(Q" S 2)) -
s S
2x
Putting everything together, the distributional distance satisfies:
sup FER
Pr(Q x)
Pr(S < x)
1
exp((r(A))) KG(Q") (x)())
1
(2(
3/2
21/4 π /(1 28)A
6v2T
n2 Var(KCI,)
exp (Ir(A)))
KCI
exp
(Ir(A))
K2(()
+
V2T
Var(KCI..)
2x
n2a Var(KCIn)
Here 8 = | and the parameter A > 0 is arbitrary. The exponential factor exp((r(AA) is
controlled by
exp(Ir(A))) < exp A2KG((0)) A RCI A² n² Var(KCCI) -100h))-))
x2/²(1) (Q)
(Q)
Recall that (Q) = Var(Q) Var(Y M) and KCg (Q") = Skew ((ee(() SYew(Y H). Define the standardized mean shift and variance mismatch scale by
KCI
Var(Y M
kci
Nivar
n² Var(KCI,)
V Var(KCI,,)
Var(Y Var(K)),,)
We now fix A = 2T /ivar 2T
With this choice.
2
3/2 + bRei + T (1Nivar-1) -1))
(sp(Ir(VEvar))) S exp
2x
Skew(Y
3
Consequently, obtain
sup Pr(Y H x) Pr(n Zn 5x) zER
exp(1r(, /ivar)
Skew(Y | mm2 + b 1k0 +
Kivar -
V2T
/2m
1/2
Kivat
25/4 2²
v(1
28)
(2x)
Finally, introducing the shorthand (xx) = v2x r exp(2Tx:). the bound can be written compactly as
sup Pr(Y A x) zER
Pr(n Zn s 2)
2n (Y
3/2 + bezi + π ///aarr - 11)
Kevas
1/2
< V
+
(2m)7/22 (19)
3
25/4 2 v(1 (1-28)
Interpretation of the terms in 19
29

---

Perfect regression. If the conditional mean embeddings are estimated without error, then k and Kvar In this regime, the bound reflects the intrinsic discrepancy between the wild bootstrap distribution and its Gaussian approximation.
Imperfect regression. When regression is imperfect, the bound is inflated by two effects: (i) the mean-shift term k which quantifies bias introduced by regression errors the KCI statistic, and (ii) the variance-mismatch term 6var. which captures deviations between the empirical variance and its wild bootstrap approximation. Both effects arise from noise in the conditional mean embedding estimates and directly degrade the quality of the wild bootstrap null calibration.
Finally, note that Var(Y | H)) the variance of weighted sum of chi-squared random variables, and Var(Y F)) + 2 [ Moreover, n.² Var(KCTT,) ~ 4nm + 2ve. If regression errors are well controlled so that KCI o(1/n) and ii = o(1/n), then n² Var(KCI,,) - 2 2B( and consequently
KCI
Var(Y H = =
o(1),
KCI
Kyar
Var(KCi.)
n² Var(KCI,))
which ensures that the leading error terms (99) remain controlled asymptotically,
With these expressions established, the proof is complete.
H
Experimental Setup and Results
In this section, we include additional experimental results. Code used in our synthetic data experi- ments is publicly available at: https://github. cww/he-oceeeeec http:/eehhhhe/ee -cadhhrdeeess
H.1 Testing procedure
Our testing pipeline follows the general structure of KCI, with modifications inspired by SplitKCI (Pogodin et al., 2024)). The data are divided into an independent training set of size m and a test set of size n. We first select kernels Kc-A and kc- using leave-one-out validation via kernel ridge regression as in SplitKCI, and estimate the conditional mean embeddings Paac and Bijc on the training data. Unlike SplitKCI, though, we do not further split the training set to obtain independent estimates T Alc and (22) evaluating any point the conditional mean embedding for A C is
AAc: instead, both C and "BIC are trained on the full training set. When
(C = x (KT + Alm) K
the training kernel matrix the ridge regression parameter, and K2r E R" is given by (KT) )= ke (C; c), where a; and c; denote the training samples. The conditional mean embedding for B C can be computed analogously.
The training feature matrix is T (1))) (s(am)) on C' ( = kc Cy),
When the power maximization technique is applied, we additionally maximize SNR using gradient descent on training data by selecting the kernel kg. Finally, given the chosen kernels, we compute the kernel matrices 2 Kg, and Kg on the test set to estimate KCI.
Although we use the unbiased estimator in (q. for analytical convenience, in practice is preferable use the HSIC-like unbiased estimator (Pogodin al., 2024] (21()
KCI, m(m 3) (I(KLL+ +
KTK1 (m 1)(m -2) 2) m - KKL
2
(20)
where 1 is the all-ones vector, K= estimator "centralizes" the kernel matrices, which helps average out some regression errors. While does not eliminate all errors, it improves the KCI estimate and stabilizes power maximization.
Rg. R K L=
Kc. and @ denotes elementwise product. This
30

---

To obtain p-values, we approximate the null distribution using the wild bootstrap with Rademacher variables. Following SplitKCI, we generate wild bootstrap statistics
K 1111111 L1
2
V3
tr tr(K.L)+ + (m 1)
m(m 3)
where K. qsd, @ Ra and (4+); = +1 independently with equal probability for all and The
p-value is then computed as
1
(KCL, V.).
S sml
H.2
Synthetic data
ID synthetic test case. We compare standard KCI, KCI with power-maximizing kernel selection, and GCM, using linear kernels for and B in all methods, on problem (7). FigureH shows that GCM, while maintaining low Type-I error, error, fails to detect conditional dependence in this setting. Standard KCI exhibits high Type-ll error, whereas power- moxer-maximized KCI achieves low Type-Il error. For both KCI variants, Type-I error decreases the training size increases.
Type-I Error
Type-Il Error
0.30
1.0
0.8
0.5
Mban
0.35
Power Maximized KC
GCM
0.30
0.06
0.2
900 Number of Training Points
420
500
800
1000
202
700
1000
Number Training Points
Figure 4: Mean and standard error (over 100 runs) of errors on the problem 77) with FA = cos, fB =
exp, 0.1 and [ = 3 across training sizes; the independent test set has size 200. The significance level set at a = 0.05
3D synthetic test case. We study the problems introduced in Appendix H3 Both scenarios used fA = cos, fø = cxp, noise scale T = 0.1, dependence frequency 3 2. Gaussian kernels are used for all kernels throughout. The significance level is set 0.05.
Table summarizes empirical results with 200 training points regression and 200 test points, averaged over 100 runs, with 500 training epochs. Kernel ridge regression with leave-one-out valida- tion seleets kernels for kC-+ and kc with per-dimension lengthscales. Power maximization is utilized to select kc kernel.
We further compare standard KCI with fixed lengthscales and KCI with power-maximized kernel selection across training sizes 100-1000, keeping the test size fixed at 200. Results are reported for regressors trained convergence (500 epochs) and with early stopping. Experiments are repeated 100 times, and we report mean and standard error.
We conduct experiments B depend on the same coordinate of C1 (see Figure 5). Scenario 2: separate-coordinate dependence, where A depends on C₁. B on C2, correlation on C3 (see Figure 6
two scenarios. Scenario 1: shared-coordinate dependence, where A and
In Scenario 1, Type-II error substantially lower than in Scenario 2, as regression errors along the same coordinate more strongly correlated, amplifying the apparent dependence. Power maximization in Scenario I slightly reduces Type-I error, probably because it focuses on only the coordinate C1, while ignoring other two dimensions, thereby reducing noise.
In Scenario Type-I error is lower overall since regression errors depend on separate coordinates and are less correlated. However, when conditional mean embeddings are undertrained, power maximization can further increase Type-I error, as mistakenly interprets the weak dependence between regression errors conditional dependence and amplifies it.
31

---

Type-1 Error
Type-Il Error
1.00
0.6
Standard KC
Power Maximized KC
0.4
0.00
Mean 3:
0.3
0.40
0.2
0.20
0.08
0.0
200
4.0
500
650
400
1000
100
1000
Number of Training Points
Number of Training Points
(a) Training to convergence.
Type-1 Error
Type-ll Error
Standard KCI
0.80
Power Maximized KC
SE
0.4
0.1
0.00
200
100
403
100
600
700
800
900
1050
230
4.00
500
600
800
600
1003
Number Training Points
Number Training
(b) Early stopping.
Figure 5: Chared-coording dependence. Means and standard errors (over 100 runs) of Type-I and Type-II errors on the 3D synthetic case with ʃA cos, I'n exp, and 0.1. All kernels are Gaussian, and the significance level set at a = 0.05.
H.3 Real data
We conducted experiments on the UTKKFace dataset (Z.. Zhang et al., 2017). following the setup of Y. Zhang et al. (2025). Although not described as such in their paper, this test is effectively KCI test. In particular, we used the cropped and aligned UTKFace dataset to test whether age (A) depends on the full face image (B) when conditioned on the same image with a specific region masked out (C). The null hypothesis [E[A C] E[A B, C), corresponding to linear kernel on A, where the conditional mean embedding can be estimated as regressor from C' to A via neural networks.
The dataset split into subsets, each with its own training and test partition. We reran their code and report both the resulting p-values for the conditional independence tests and the mean absolute error (MAF) of the age regressors AamaeeNet-pretraineee we also retrained the same network from scratch (random initialization) and report its MAE and corresponding test results. The results are shown in Figure
used in testing. For comparison,
In Y. Zhang et al. (2025), p-values remain above 5% when facial region is masked, suggesting that the region is not critical for age estimation. However, when the same network is trained from random initialization, the validation loss increases-indicatin a less accurate conditional mean embedding- and the resulting p-values drop consistently across all regions. This shows that test outcomes are highly sensitive to regressor quality: imperfect conditional mean estimation makes the test more prone to signal dependence.
32

---

Type-1 Error
Type-ll Error
Standard KC
0.5
Power Maximized KC
0.4
0.00
Moan
0.3
0.20
0.00
0.0
500
a50
500
Number Training
Number Training Points
(a) Training to convergence.
Type-I Error
Type-ll Error
1.00
0.6
Power Maximized
SE
0.0
0.2
0.20
200
300
400
500
600
700
800
100
1000
250
300
420
500
620
700
800 500
1000
Number of Training Points
Number of Training Points
(b) Early stopping.
Figure 6: Eeparate-coordinaee dependence. Means and standard errors (over 100 runs) of Type-I and Type-II errors on the 3D synthetic case with fA = cos, fB = exp, and T = 0.1. All kernels are Gaussian, and the significance level is set at 0.05.
0.80
Pvalues Pretrained (Boxplot)
Pvvauues (Boxplot)
-22
0.70
MAE Pretrained
Scratch
0.60
Pvalues (Boxplot)
0.53
0.20
0.10
0.85
0.00
Top Left
Nose
Mouth
Eye
Face
Figure 7: Box plots of p-vauues (left y-axis) and test MAE (right y-axis) across different facial regions in the age estimation task. "Pretrained" refers to using an ImageNet-pretraine age regressor, while "Scratch" indicates training the same model from random initialization.
33

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification:
The claims made cover what we did in the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
It fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
Throughout, especially e.g. following Theorems 6.2 and 6.3 and in the
supplement.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model sell-specification. asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't It acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proof's
34

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification:
Either in the theorem statement or the supplement.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: provided.
While we have few experiments, they are clearly described and code will be
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility.
35

---

In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
In the supplement.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
public/guides/ ottple/seeoooeueeessssssoooooooo
for more details.
While we encourage the release of code and data, we understand that this might be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https for more details.
/nippscc/ppll wttpcccppppccc.eeeeee..ee...leet wwwpeeegguueeeeeeee wetdeeSuumisssonooll..o
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: the supplement and the code.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
Experiments limited, but we have error bars.
36

---

Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification:
The amount of computation used was very limited by modern standards.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http:///////aca.....//////////ta
Answer: [Yes]
Justification:
No relevant issues.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader impacts
37

---

Question:
Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
This is a foundational theoretical paper and does not really propose new
algorithm.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: No such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
38

---

Answer: [NA]
Justification:
The only existing asset is code we built on, which we cite and specify in the source.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL
The name of license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperrsiiiaaaiiiiiiiai. thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [Yes]
Justification:
Our code (in the supplement) is documented.
Guidelines:
The answer NA means that the paper does release assets. Researchers should communicate the details of the dataset/code/model part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: No human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
39

---

15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: No human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMS if it is important, original, or non-standard component of the core methods this research? Note that the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: Not used in such ways.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to LLM policy for what should or should not be described.
40


Reviews:
[{"review_id": "gvCOuu7faL", "reviewer": "Reviewer_v1Tn", "summary": "This paper examines the practical hardness of conditional independence testing with kernels. Specifically, Shah and Peters give a result that conditional independence testing is statistically hard, however their constructive proof gives little insight as to why common kernel based tests fail. In this work, the authors examine the failure of these tests, demonstrating that if we had exact knowledge of the conditional mean embedding the testing problem becomes feasible, constructing a test that is consistent against any fixed alternative. They then study how the choice of kernel impacts the estimation of the conditional mean embedding, due to its centrality to the testing problem.", "questions": "- Is Theorem 2.2 he same as condition i) in Lemma 2.2 of [1]?\n\n- Can the authors comment on similarity to goodness of fit tests?\n\n- What would the authors feel are the key limitations of the paper?", "limitations": "The limitations are not discussed despite the fact that this box is checked in the checklist.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- I find the work to be interesting and novel, it plugs in my opinion a needed gap between the hardness result of Shah and Peters and practical conditional independence testing.\n\n- The observation that access to the true conditional mean embedding leads to a consistent test is a good one and is in line with the cited model X work. \n\nWeaknesses:\n\n- Theorem 2.2 is not new or an extension of Daudin 1980. In fact (without the weighting term) this is the same as condition i) in Lemma 2.2 of [1]. Seeing this classic result described as novel leads me to be concerned about the validity of the rest of the work and the authors familiarity with the area. \n\n-  Whilst I do agree that the observation that the true CME are enough for a valid test is an interesting one, it does seem to me that this result is an example of (or very closely related to) the idea of goodness of fit tests with kernels [2]. Specifically, having access to both $\\mu_{A|C}$ and $\\mu_{B|C}$ gives us access to $\\mu_{A,B|C}$ under the null distribution. Given this, conditional independence testing could be framed as a goodness of fit test for if samples $(a_i,b_i,c_i)$ are consistent with $\\mu_{A,B|C}$. In this light a consistent test feels unsurprising due to results of consistency of goodness of fit tests. \n\nOverall whilst this paper seems interesting and is a valid contribution to the literature, my current feeling is that it needs a bit more work before publication as evidenced by the claims of novelty of theorem 2.2 and the incomplete limitations section. Having said this if the authors provide strong arguments I would consider changing my score.\n\nSmall note: I would consider changing the phrase \"It has a reputation, however, of doing a poor job at controlling Type I error (that is, it falsely identifies conditional dependence too often).\" and ideally fine a citation or include an experimental result justifying this as without a strong familiarity with the area this statement is hard to verify.\n\n[1] - Kernel-based Conditional Independence Test and Application in Causal Discovery. Kun Zhang, Jonas Peters, Dominik Janzing, Bernhard Schoelkopf.\n[2] - A Kernel Test of Goodness of Fit. A Kernel Test of Goodness of Fit.", "was_revised": true, "final_justification": "Following discussion with the reviewers I now see their paper as a strong contribution to the conditional independence testing literature and so I am changing my score to accept.", "rebuttal": "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.\n\n## Clarification on the Novelty of Theorem 2.2: \n\nWe'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.\n\nTheorem 2.2 of our paper:\n> Random variables $A$ and $B$ are conditionally independent given $C$ if and only if\n>\n> $\\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$\n>\n> for all square-integrable functions $f \\in L^2_A$, $g \\in L^2_B$, and $w \\in L^2_C$.\n\nCompare with Lemma 2.2 of Zhang et al., which stated results of Daudin, rewritten in our notation:\n> The following conditions are equivalent to one another:\n>\n> (i) $A$ is conditionally independent of $B$ given $C$. \n>\n> (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$.\n>\n> (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}$.\n>\n> (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}$.\n>\n> (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}$.\n\nThe key difference is that all versions of Daudin's result depend on a centered function $\\tilde f$ of _both_ $A$ and $C$.\n\nZhang 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.\n\nWhile 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.\n\nThis 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.\n\nWe will add further clarification of these points in the revised version; thank you for raising the concern.\n\n[i] Pogodin, Roman, et al. \"Efficient Conditionally Invariant Representation Learning.\" *ICLR (2023).*\n\n[ii] Pogodin, Roman, et al. \"Practical kernel tests of conditional independence.\" *arXiv preprint arXiv:2402.13196 (2024).*\n\n[iii] Wang, Wenjie, et al. \"Practical Kernel Learning for Kernel-based Conditional Independent Test.\" *(2025).*\n\n---\n\n## Clarification on Relation to Goodness-of-Fit Testing\n\nWe 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:\n\n- 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.\n\n\n- 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.)\n\n- 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}$.\n\n\nWe 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.\n\nIn 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.\n\n---\n\n## Clarification on Limitations\n\nWe 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. \n\nAdditionally, 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.\n\nWe 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.\n\n---\n\n## Clarification on the Type I Error Statement\nWe 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.\n\nIn 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.\n\n[iv] Shah, Rajen D., and Jonas Peters. \"The hardness of conditional independence testing and the generalised covariance measure.\" *(2019)*\n\n[ii] Pogodin, Roman, et al. \"Practical kernel tests of conditional independence.\" *arXiv preprint arXiv:2402.13196 (2024).*\n\n---\n\nWe 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."}, {"review_id": "ytxa7UMlQw", "reviewer": "Reviewer_397d", "summary": "Aiming to improve the understanding and failure modes of conditional independence (CI) tests, this work provides several novel insights into the hardness of CI testing in practice.\n The authors mainly analyse the Kernel-based conditional independence test (KCI), noting that results also relate closely to the (weighted) Generalized Covariance Measure (GCM) under their formulation of the test in Thm. 2.2. The main insight is that the estimation of conditional mean embeddings presents the main practical limitation of KCI. Specifically, the well-known hardness result by Shah and Peters (2020) does not hold for KCI when using true mean embeddings (Prop. 3.1) but its practical issues arise from the finite-sample estimates of the embeddings. The authors show that this can be somewhat alleviated through the kernel choice (Section 4) but also acknowledge that this comes at the expense of inflating Type I errors, i.e., false positive rejections of independence (Figure 2).", "questions": "Minor suggestions and questions include \n\n- If space allows, the density of the text could be reduced. For example, an explanation of Fig. 1 (besides ln. 271) seems to be missing in the text, and some paragraphs could be expanded such as lines 327-335 to explain the insights given in Appendix G.2, G.3.  \n- a clearer separation of previous insights compared to those that are novel contributions could be helpful, e.g. some of the existing works could be postponed to the Appendix or a related work section.", "limitations": "No major unadressed limitations or societal impacts.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The work contributes several novel insights that are likely of interest to the literature. This includes the reframing of KCI to more closely relate it to GCM (Thm. 2); the insight on practical failures of KCI being related to conditional mean embedding estimation which, according to the authors, is not yet acknowledged in existing work; the discussion of appropriate kernel choices (Section 4); and the exploration and cautionary remarks regarding Type I errors (Section 5). Especially in light of the importance of CI testing and widespread use of KCI, this makes this work of solid significance, even though the practical contribution is perhaps limited.\nThere are no apparent issues regarding quality, all claims have thorough justifications. While some results are inspired from previous insights, such as the strategy motivated in Prop. 4.1. following related settings, the contributions can all in all judged to be of sufficient originality. \nRegarding clarity, the writing is dense  but overall well structured around the main claims, and all insights are placed in the context of previous work. \n\n Overall, this work advances the current understanding of the behavior of KCI and can be judged an important contribution.", "was_revised": true, "final_justification": "It seems that all concerns and questions raised during the rebuttal were resolved, such as\n\n- The initial concerns about the novelty of Thm. 2.2 compared to existing results by Daudin 1980 raised by Reviewer v1Tn. This was resolved after additional clarifications by the authors, (some of) which they promise to include in the revised version. \n- The arguably small empirical evaluation. In the rebuttal, the authors provided more extensive experiments on synthetic data as well as on real-world data. This strengthens the empirical contribution besides the already strong theoretical one. \n\nAll points raised by the reviewers can be addressed without substantial changes of the submitted manuscript.\nOverall, I maintain a positive impression of this work and raise the numerical score.", "rebuttal": "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.\n\n## Explanation of Figure 1 and Dense Text\nWe 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.\n\nWe 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.\n\n\n## Distinguish Contributions\n\nOn 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.\n\n---\nWe 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."}, {"review_id": "xFH8WWrc0S", "reviewer": "Reviewer_ZYGz", "summary": "This paper provides a comprehensive theoretical analysis of kernel-based conditional independence (KCI) testing. The authors first introduce the KCI framework, and re-interpret it from the perspective of generalized covariance measures (GCM), in a distinct way from [1]. Then, the paper presents an analytical example to illustrate the behavior of the proposed KCI statistic both with and without regression errors. Several simulations were conducted to emphasize the importance of selecting an appropriate kernel of conditioning variables. The theoretical contributions of the paper mainly focus on establishing an error bound of SNR estimator (the KCI statistic divided by its variance), as well as the bounds on the type I error of the test in the presence of regression error. Overall, the authors provide a theoretically sound and carefully argued analysis of KCI, supported by a few simulations that validate their theoretical insights.\n\n[1] Wenjie Wang et al. (2025), Practical Kernel Learning for Kernel-based Conditional Independent Test, Openreview.", "questions": "1. I strongly recommend to fix the y-axis when plotting Figure 3 (a), (b). In addition, it is quite surprising that the type II errors of blue and green lines increase with a larger sample size, when $l_C^2 = 10^{-5}$. Moreover, the standard deviation of the type I error becomes noticeably larger with larger sample size. Could the authors provide further explanation for these phenomena?\n2. Could you explain where the $\\lambda = \\ell n^{-1/3}$ in line 874 comes from? This is crucial for the first term in the convergence rate of the SNR. And I noticed Liu et al. also chose a similar $\\lambda$ in their Th 6 [2].\n3. Could the authors extend their discussion of KCI to also RCIT[3] and SCIT [4]? Given that these methods are highly correlated to GCM and KCI.\n\n[2] Feng Liu et al. (2020), Learning Deep Kernels for Non-Parametric Two-Sample Tests, ICML.\n\n[3] Hao Zhang et al. (2017), Causal Discovery Using Regression-Based Conditional Independence Tests, AAAI.\n\n[4] Hao Zhang et al. (2022), Residual Similarity Based Conditional Independence Test and Its Application in Causal Discovery, AAAI.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n1. The analyses of the example in Section 4 are detailed and valuable.\n2. The work improves understanding of KCI testing, and provides a solid foundation for further theoretical improvements.\n3. The authors gave the bound of type one error which is missing from [1].\n\nWeaknesses:\n1. It would be beneficial if the authors could provide more extensive simulations to further examine the the proposed CIT and theories. It would be better if the results could be supported by real data.\n2. I suggest that the authors consider moving some of the important theoretical results in the appendix into the main text, to better highlight the contributions of the paper. Conversely, certain parts of the main text could be condensed, or even moved to the appendix, such as some part of Section 2, 3.", "was_revised": true, "final_justification": "The authors finished the rebuttal nicely. They gave extensive extra experiments, tried to explain the abnormal place in their figures, clarified the convergence rate, and I also hope to read their further discussion about RCIT and SCIT. Overall, most of my problems are sloved.", "rebuttal": "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.\n\n## More Extensive Simulations and Real Data \nWe 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.\n\nTo begin with, we have additional simulation results for the settings already considered in the paper; we will discuss a new setting on images afterwards.\n\n### 1. Setting of Section 4\n\nWe 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.\nThe standard KCI use fixed-bandwidth conditioning kernel while PM use learned-bandwidth conditioning kernel:\n\n|Training Size|Type I Error (standard)|Type II Error (standard)|Type I Error (PM)|Type II Error(PM)|\n|-|-|-|-|-|\n|200|0.13±0.034|0.81±0.039|0.10±0.030|0.07±0.026|\n|400|0.11±0.031|0.77±0.042|0.11±0.031|0.01±0.010|\n|600|0.03±0.017|0.67±0.047|0.04±0.020|0.02±0.014|\n|1000|0.03±0.017|0.78±0.041|0.04±0.020|0.00±0.000|\n\n\nLearning 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.\n\n### 2. Complex 3-Dimensional Conditional Dependence Analysis (Setting of Appendix G.3)\n\nIn 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. \n\nOur 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.\n\n#### Scenario: Multi-coordinate dependence\nHere $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$.\n\nWith sufficiently trained regressors:\n|Training Size|Type I Error (Standard)|Type II Error (Standard)|Type I Error (PM)|Type II Error (PM)|\n|-|-|-|-|-|\n|200|0.13±0.034|0.22±0.041|0.14±0.035|0.04±0.020|\n|400|0.09±0.029|0.16±0.037|0.12±0.032|0.02±0.014|\n|600|0.07±0.026|0.18±0.038|0.06±0.024|0.00±0.000|\n|800|0.06±0.024|0.14±0.035|0.03±0.017|0.00±0.000|\n|1000|0.03±0.017|0.20±0.040|0.07±0.026|0.00±0.000|\n \nWith poorly trained regressors:\n|Training Size|Type I Error (Standard)|Type II Error (Standard)|Type I Error (PM)|Type II Error (PM)|\n|-|-|-|-|-|\n|200|0.49±0.050|0.15±0.036|0.59±0.049|0.09±0.029|\n|400|0.23±0.042|0.20±0.040|0.35±0.048|0.11±0.031|\n|600|0.10±0.030|0.24±0.043|0.15±0.036|0.11±0.031|\n|800|0.06±0.024|0.47±0.050|0.08±0.027|0.20±0.040|\n|1000|0.10±0.030|0.55±0.050|0.10±0.030|0.22±0.041|\n\nThe patterns agree well with our explanations that poorly-trained CMEs make Type I error explode compared to well-trained CMEs. \nWith 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.\n\nWe will expand on these and related observations in the final version.\n\n\n### 3. Real Data Experiments: UTKFace Age Prediction Study\n\nWe conducted experiments using the UTKFace dataset, following the methodology from a recent paper:\n\nY Zhang, Huang, Yang, and Shao. ``Testing Conditional Mean Independence Using Generative Neural Networks.'' *ICML 2025.*\n\nWhile 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.\n\nIn 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$). \n\nIn 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).\n\nWe 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.\n\nNow 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.\n\n---\n\n## Clarifying Figure 3 and Paper Organization\n\nThe reviewer's attention to detail with respect to this figure is very much appreciated!\n\nWith 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.\n\nFor 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.\n\nWe also thank the reviewer for the valuable suggestion on the paper organization. We will optimize it to better highlight our contributions.\n\n---\n\n## Could you explain where the $\\lambda = \\ell n^{-1/3}$ in line 874 comes from?\n\nThe 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.\n \n[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.\n\nIn 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.\n\nWe will add some discussion of this choice, which indeed goes by with absolutely no explanation in the current version.\n\n---\n\n## RCIT and SCIT\nWe thank the reviewer for suggesting the relationship to RCIT and SCIT.\n\nRCIT 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.\n\nSCIT, 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. \n\nWe will add a short discussion in the revised manuscript to highlight this connection.\n\n\n---\nWe 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."}, {"review_id": "3HnD9WGwyh", "reviewer": "Reviewer_web4", "summary": "This paper examines issues about conditional independence testing. It gives a good review of how this has been done over the ages and investigates kernel-based conditional independence as well as how to choose the best kernels and the associated pros and cons.", "questions": "In line 170, where you define $t_n$, what is $q$?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 4, "originality": 3, "strengths_and_weaknesses": "This paper presents a detailed background for all the key methods used in rich statistical formulations. However the paper could benefit from performing more experiments to prove the points they are establishing.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive review and constructive suggestions.\nBelow, we address the reviewer's concerns and clarify how we will revise the manuscript accordingly.\n\n## More supporting experiments\nWe 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.\n\n\n\nTo begin with, we have additional simulation results for the settings already considered in the paper; we will discuss a new setting on images afterwards.\n\n### 1. Setting of Section 4\n\nWe 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.\nThe standard KCI use fixed-bandwidth conditioning kernel while PM use learned-bandwidth conditioning kernel:\n\n|Training Size|Type I Error (standard)|Type II Error (standard)|Type I Error (PM)|Type II Error(PM)|\n|-|-|-|-|-|\n|200|0.13±0.034|0.81±0.039|0.10±0.030|0.07±0.026|\n|400|0.11±0.031|0.77±0.042|0.11±0.031|0.01±0.010|\n|600|0.03±0.017|0.67±0.047|0.04±0.020|0.02±0.014|\n|1000|0.03±0.017|0.78±0.041|0.04±0.020|0.00±0.000|\n\n\nLearning 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.\n\n### 2. Complex 3-Dimensional Conditional Dependence Analysis (Setting of Appendix G.3)\n\nIn 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. \n\nOur 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.\n\n#### Scenario: Multi-coordinate dependence\nHere $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$.\n\nWith sufficiently trained regressors:\n|Training Size|Type I Error (Standard)|Type II Error (Standard)|Type I Error (PM)|Type II Error (PM)|\n|-|-|-|-|-|\n|200|0.13±0.034|0.22±0.041|0.14±0.035|0.04±0.020|\n|400|0.09±0.029|0.16±0.037|0.12±0.032|0.02±0.014|\n|600|0.07±0.026|0.18±0.038|0.06±0.024|0.00±0.000|\n|800|0.06±0.024|0.14±0.035|0.03±0.017|0.00±0.000|\n|1000|0.03±0.017|0.20±0.040|0.07±0.026|0.00±0.000|\n \nWith poorly trained regressors:\n|Training Size|Type I Error (Standard)|Type II Error (Standard)|Type I Error (PM)|Type II Error (PM)|\n|-|-|-|-|-|\n|200|0.49±0.050|0.15±0.036|0.59±0.049|0.09±0.029|\n|400|0.23±0.042|0.20±0.040|0.35±0.048|0.11±0.031|\n|600|0.10±0.030|0.24±0.043|0.15±0.036|0.11±0.031|\n|800|0.06±0.024|0.47±0.050|0.08±0.027|0.20±0.040|\n|1000|0.10±0.030|0.55±0.050|0.10±0.030|0.22±0.041|\n\nWhile 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. \nWith insufficiently-trained CMEs, power maximization makes Type I error far worse under Scenario 2. \n\nWe will expand on these and related observations in the final version.\n\n\n### 3. Real Data Experiments: UTKFace Age Prediction Study\n\nWe conducted experiments using the UTKFace dataset, following the methodology from a recent paper:\n\nY Zhang, Huang, Yang, and Shao. Testing Conditional Mean Independence Using Generative Neural Networks. ICML 2025.\n\nWhile 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.\n\nIn 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$). \n\nIn 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).\n\nWe 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.\n\nNow 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.\n\n---\n\n\n## Clarifying what is $q$ when defining $t_n$\n\nUnder 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.\n\n\n---\n\nWe sincerely thank the reviewer for the encouraging evaluation and constructive feedback.  We believe the suggested additions will make the paper stronger and more comprehensive."}]

Author rebuttal:

Meta-review: This paper investigates the Kernel-based Conditional Independence (KCI) test and points out where the “practical hardness” of KCI comes from: the estimation of conditional mean embeddings. With oracle embeddings, a threshold yields a finite-sample valid, consistent test. The paper next analyzes kernel choice on C and shows that KCI’s power is exquisitely sensitive to the C-kernel bandwidth. Then the paper proposes selecting the C-kernel by maximizing an asymptotic signal-to-noise ratio criterion. Finally, the paper discusses the Type-I Error Inflation in the presence of regression errors.

Strengths：All reviewers agree that the paper contributes several novel insights and understandings, especially plugging the gap between the negative result of Shah and Peters and practical conditional independence testing. Reviewer 397d further emphasizes that the paper relates KCI more closely to GCM. Reviewer web4 appreciates that the paper presents a detailed background for unfamiliar readers. 

Weaknesses：
The paper would benefit from diverse real-world datasets. Reviewer 397d and ZYGz mentioned that some parts of the main text can be improved. 

The most important reasons for the decision：

I appreciate the novelty and insight this paper provided, including but not limited to:

1) Identify the major factors underlying KCI’s practical behavior. 

2) The connection between KCI and GCM. 

3) Help readers advance understanding of why CI tests fail in practice. 

4) The quantitative bounds pinpoint regression error as the bottleneck. 

The results will likely influence how CI is used in causal discovery and other related areas.

Summarization of the discussion and changes during the rebuttal period: 
Reviewer v1Tn raises the problem on the relation between Theorem 2.2 and Daudin’s work. After the rebuttal phase, the reviewer agrees with the novelty of their theorem. 

Overall comments: 

After the rebuttal phase, the paper received three accept and one borderline accept, resulting in unanimous acceptance. CI testing is a very fundamental area. This paper turns an impossibility result in CI testing into practical guidance. Rather than re-stating the Shah and Peters’s hardness theorem, the paper pinpoints where things go wrong in practice: errors in estimating conditional mean embeddings, which reframes “CI is impossible” into “CI is doable if you control specific estimation errors.” This core insight, together with the depth of the contribution, makes the work stand out. All reviewers agree that the proposed methods are both theoretically novelty and interesting. Overall, the quality of the work is high and solid, and it is likely to be of interest to the community. Therefore, I recommends acceptance as a spotlight.
Decision: Accept (spotlight)