Practical Kernel Selection for Kernel-based Conditional Independence Test
Authors: Wenjie Wang
Mingming Gong
Biwei Huang
James Bailey
Bo Han
Kun Zhang
Feng Liu
Venue: NeurIPS 2025 poster ()
Keywords: conditional independence testing
kernel method
causal discovery
Primary area: probabilistic_methods

Abstract: Conditional independence (CI) testing is a fundamental yet challenging task in modern statistics and machine learning. 
One pivotal class of methods for assessing conditional independence encompasses kernel-based approaches, known for assessing CI by detecting general conditional dependence without imposing strict assumptions on relationships or data distributions.
As with any method utilizing kernels, selecting appropriate kernels is crucial for precise identification. 
However, it remains underexplored in kernel-based CI methods, where the kernels are often determined manually or heuristically.
In this paper, we analyze and propose a kernel parameter selection approach for the kernel-based conditional independence test (KCI).
The kernel parameters are selected based on the ratio of the statistic to the asymptotic variance, which approximates the test power for the given parameters at large sample sizes. 
The search procedure is grid-based, allowing for parallelization with manageable additional computation time.
We theoretically demonstrate the consistency of the proposed criterion and conduct extensive experiments on both synthetic and real data to show the effectiveness of our method.

Practical Kernel Selection for Kernel-based Conditional Independence Test
Wenjie Wang'
Mingming Gong Biwei Huang"
James Bailey*
Bo Han
Kun Zhang Feng Liu
The University of Melbourne *Carnegie Mellon University "Mohamed bin Zayed University of Artificial Intelligence
University of California, San Diego HHon Kong Baptist University
www.uudeeee...mmlbbb....emmm..ee edu. wenjie ie. wangSāstudent. unimelb.
{mingming gong, feng. liw.lllllll Munimelb edu. au
Abstract
Conditional independence (CI) testing is fundamental yet challenging task in modern statistics and machine learning. One pivotal class of methods for assess- ing conditional independence encompasses kernel-based approaches, known for assessing CI by detecting general conditional dependence without imposing strict assumptions on relationships or data distributions. As with any method utilizing kernels, selecting appropriate kernels is crucial for precise identification. However, it remains underexplored in kernel-based CI methods, where the kernels often determined manually or heuristically. In this paper, we analyze and propose a kernel parameter selection approach for the kernel- kernel-based conditional independence test (KCI). The kernel parameters are selected based on the ratio of the statistic the asymptotic variance, which approximates the test power for the given pa- rameters at large sample sizes. The search procedure is grid-based, allowing for parallelization with manageable additional computation time. We theoretically demonstrate the consistency of the proposed criterion while explicitly accounting for model estimation bias, which is a distinctive challenge specific to CI testing task. Furthermore, we conduct extensive experiments both synthetic and real-world datasets to empirically validate the effectiveness of our method.
1 Introduction
Conditional independence (CI) test is a cornerstone of statistics and machine learning. Let X, and Z be the random variables, then the conditional independence relationship between X and Y given Z, denoted by X JL Y Z, indicates that knowing the values of Z, the knowledge of X does not yield any extra information about Y. This conditional independence relationship enables the removal of redundant variables when constructing probabilistic models for given variable set. Therefore, the utilization CI has expanded across diverse domains, including causality [Spirtes et al., 2000, 1995, Pearl et al., 2000, Huang et al., 2020, Chi et al., 2024], fairness representation learning [Mchrabi al., 2021, Han et al., 2025], feature selection [Fukumizu al., 2009, Song et al., 2012].
Traditional CI testing methods either address the discrete case [Margaritis, 2005] or rely on simplifying assumptions to handle the continuous case [Lawrance, 1976, Linton and Gozalo, 1996). These assumptions can be restrictive, and when violated or when data are limited, these methods often yield biased estimates and erroneous inferences, leading to unreliable conclusions. Daudin [1980] extended the concept of partial correlation to general scenarios involving nonlinear and non-Gaussian noise, redefining conditional independence as the zero correlation of any regression residual functions
"Corresponding Feng Liu. The code is available hutp://gihna.cmm/veeivaaaa////
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

within constrained L spaces. While this definition can identify general CI relationships, it requires considering all possible functions within these constrained L spaces, which is infeasible.
To make it practical, Zhang et al. [2011] relaxed the function spaces to reproducing kernel Hilbert spaces (RKHS) using kernel methods, simplifying computation while preserving the ability to capture general CI relationships. In kernel methods, there exists special class known as characteristic kernels, [Fukumizu al., 2007] such as the Gaussian and Laplace kernels, which are capable of measuring distributional homogeneity [Gretton et al., 2a, Song et al., 2009]. Building on this, Zhang et al. [2011] introduce the Kernel-based Conditional Independence (KCI) statistic, which replaces regression residuals with kernel- -eanel-based analogues. They adopt the framework of conditional mean embeddings (CME) [Song et al., 2009, Grünewälder et al., 2012] to model nonlinear relationships, and norm of the cross- coss-covariance operator between residuals in RKHS, replacing the original cross-covariance defined in I,2 space [Gretton et al., 2005a]. This formulation enables KCT to directly assess whether Px Pz = Px|z Pyiz Pz. without requiring explicit estimation of complex conditional marginals. Due to the reproducing property of kernels, a zero value of this statistic implies that all partial correlations between residual functions, represented in the RKHS induced by the chosen kernels, are also zero. Consequently, by employing characteristic kernels whose RKHS are dense in L [Sriperumbudur et al., 2008], KCI is capable of capturing broad class of conditional dependencies, extending beyond the linear relationships. However, as with all kernel-basee methods, the performance of KCI is highly sensitive to the choice of kernels.
define the test statistic as the
It is well known that the effectiivnesss of kernel-based methods critically depends on the choice of kernels across wide range of tasks [Brockmann et al., 1993, Chapelle and Vapnik, 1999], particularly the choice of kernel parameters [Schölkopf et al., 2002]. A commonly used strategy is the median heuristic, which sets the kernel bandwidth to the median of pairwise distances between data points. While simple and widely adopted, this approach is often suboptimal for a given dataset [Ramdas et al., 2015, Garreau et al., 2017]. Consequently, data-driven selection of kernel parameters is crucial for maximizing the performance of hernel-based methods. Gretton et al. [2012b] propose a statistic- to-variance ratio criterion that leverages the properties of U-statistics to estimate test power under given kernel parameters, and use this to guide kernel selection. Variants of this criterion have been extended to tasks such two-sample testing [Liu et al., 2021, Biggs et al., 2023] and unconditional independence testing [Albert et al., 2022], with some methods further incorporating deep kernels [Liu al., 2020, Xu al., 2024]. These approaches perform continuous optimization learn near-optimal or even oracle kernel choices for the tasks above. However, such optimization-bans based strategies are not directly applicable conditional independence testing, which requires additional consideration of regression-induced estimation bias-a distinguishing challenge unique to the CI test task. As result, suitable kernel selection methods for CI testing remain largely underexplored.
Contributions. In this paper, we propose a kernel selection method to optimize the kernel parameters involved in the widely used KCI statistic. Our criterion remains grounded in the torriiane ratio framework, but explicitly accounts for the characteristics of the CI task, which require indirect consideration of regression residuals and the associated estimation bias. To this end, we first decompose the original KCI statistic to isolate the kernel component associated with the conditioning set, which was previously entangled within the residuals. This decomposition effectively reduces such estimation bias, thereby enabling more effective kernel selection in subsequent steps. We use the ratio of the statistic to the asymptotic variance as criterion, which approximates the test power at large sample sizes. Then, the kernel parameters are selected based on the maximum ratio from a list of potential candidates using grid search approach. Unlike existing continuous optimization approaches, this practical search strategy accounts for regression estimation bias and leverages the parallelizability of regression learning under different kernel parameters. Theoretically, we provide the first convergence result for this power-based criterion under the conditional independence testing setting, explicitly accounting for model estimation bias. Extensive experiments on both synthetic and real data demonstrate the efficacy of our method with manageable computation time.
2 Preliminaries
2.1 Related Works
CI testing and its hardness. central difficulty in conditional independence (CI) testing fun- damental: without extra structure, a valid test cannot be uniformly powerful against all alternatives

---

[Shah and Peters, 2020]. This has led to two pragmatic lines. One imposes side information (e.g.. Model-X-stylee knowledge of part of the conditional law) to stabilize null simulation or calibration [Candes et al., 2018, Berrett et al., 2020, Doran et al., 2014]. The other residualizes X and/or Y on Z and then tests for remaining dependence; kernel-based embeddings to assess higher-order partial dependence without parametric assumptions [Fukumizu et al., 2007, Sun et al., 2007, Zhang et al., 2011, Huang et al., 2022]. In both cases, bias from estimat- ing conditionals (or their surrogates) flows directly into Type-I error control and power-unlike in two-sample or unconditional independence tests-So so reducing residualization error is both distinctive and pivotal in CI testing.
tests fall in this camp, using RKHS
Kernel selection. Kernll tests are highly sensitive to hyperparameters (often more than the kernel family), yet practice commonly defaults to the median-disten -istancee bandwidth, which can be suboptimal (Schölkopf et al., 2002]. Outside CI, data-driven criteria optimize kernels by maximizing a statistic or antiitic-to-varianne ratio that proxies power, yielding strong results in two-sample, unconditional independence, and goodness-of fit testing, including with deep kernels [Fukumizu et al., 2009, Gretton et al., 2012b, Liu et al., 2021, Biggs et al., 2023, Albert et al., 2022, Ren et al., 2024a,b, Liu et al., 2020, Xu et al., 2024]. CI, however, is qualitatively different: the target is conditional structure and the test statistic typically depends on regression residuals (e.g.. KCI/GCM), introducing additional estimation bias/variance beyond finite- sample variability of a direct discrepancy [Zhang et al., 201 1, Shah and Peters, 2020]. This distinction limits the direct transfer of existing selection rules and motivates Cl-aware kernel selection that explicitly couples kernel choice with the residualization step-ainne aimed at better Type-I control and power for kernel-based CI. For more related papers and discussion, please refer to Appendix A.
2.2 Kernel-based measures of conditional dependence
CI definition and testing procedure. Suppose there are three random variables X, Y and Z with observational points, and their joint distribution absolutely continuous with respect to Lebesgue measure with density P. The problem of testing CI between X and Y given Z can be written in the form of a hypothesis testing:
Ho D.XLYYI vs. :
CI testing typically involves the following steps: define a test statistic T and a significance level a (typically set at 0.05); compute the observed statistic Tp: calculate the p-value under Hg: and reject Ho if the p-value less than or equal a. We evaluate the performance of a CI testing method using Type I error (False Positive) and Type II error (False Negative): a reliable CI test controls the Type I error below the significance level while minimizing the Type error.
We provide the general characterization of conditional independence from the perspective of partial association:
Definition 1. [Daudin, 1980] Random variables X and Y are independent conditioned on Z, denoted X Y Z, if for all functions g Zz and h ε L2 we have almost surely in Z that
[[g(X, 2) M(Y) Z] F[g(XX, 2) Z]E(M(Y) Z].
Theorem 2. [Daudin, 1980] X 1 Y 2 if and only if
()))) Vg E1, h E2,
(I)
where E1 (g L2x2 ([ 2) =} and Eg (h LÝ ((((() [] 0).
Since ((X can represent any general relationship between X and Z, Theorem 2 can be intuitively understood as asserting that the residuals obtained from regressing any function mappings of (X, Z) and Y, defined in the L space, onto 2 are uncorrelated. Therefore, this definition can capture general CI relationships but requires considering all possible functions in 2
Kernel-based CI statistic (KCI). To use this characterization in practice, Zhang et al. [2011] introduce it within the RKHS. For the random variable X with its domain X,, we define the RKHS Hxx on with symmetrie positive-definite function kx X X + R. The kernel can be represented as an inner product in H. via mapping &z XX - Hx, which is lx (x(xxx)) (0x(x), dhr((')) And with the reproducing property, we have Vx E X and Vʃ E Hxx (xx) notation on X, we define
(f,0(()) Similar to the
Hy), (kz, (Z), Hz) and (kxz, Ons (X,2), Hxz) with
3

---

kxz == kxkz. Building upon the cross- covariance operator [Fukumizu et al., 2007], Zhang et al. [2011] then propose the Kernel-based Conditional Independence (KCI) statistic for CI testing, which is defined as follows:
ExyςZ = [[(( -xx2)))xxx22) @ (Y) (2)2((2)),,
where X == Z), is the tensor product, pxzz and ZYz represent the conditional mean 2) Z] and Jy z (Z) = , 2]. Utilizing the
embeddings given by (z) property that for any E Hxz and E My (see e.g. Gretton [2013, Lecture 5)), the tensor product operates (Øz= 0y)g و (0 g) Py. we can derive the following equation:
Exr (l(x(X 2) E[g(X, 2) Z)(A(Y) E[A(Y) Z])];
which holds for any g Hxz and h Hy. For class of kernel functions known characteristic kernels (such as Gaussian kernel), their RKHSs are dense in L spaces [Sriperumbudur et al., 2008]. With characteristic kernels employed, if X 0, Eq. 1 holds for any e Eg Hxz and h E Eg Hy, encompassing sufficient functions by continuity and density. This implies that Σxvz = 0 if and only if X n Y Z. Therefore, we can test conditional independence by evaluating whether the Hilbert-Schmidt norm of the operator zero, i.c. ||
3 Power-based kernel selection for conditional independence testing
In all kernel-involved methods, the choice of kernel parameters is crucial, and KCI is no exception. The original KCI relies on the median heuristic to determine its kemne parameters, which does not fully capture the inherent characteristics of the data. In this section, we introduce our power-based kernel selection method for KCI, named Power.
Decomposition of KCL We begin our method by decomposing the kerne mapping of the conditioning set Z from the concatenated dzz (X, 2) in its original form (i.c., Eq. 1), as suggested by Pogodin et al. [2022, 2024]. According to [Mastouri et al., 2021], the RBF kernels (e.g. the Gaussian and Laplace kernel) of é. (X, 2) can be decomposed into o, (X) @ o (2). For the conditional expectation,
E[Øx(X) @ (Z) Z] (X) Z] o2 (Z). Then, the decomposed form of the KCI statistic, which isolates da (Z) from the regression residual
derive that "xzzz(Z]
of (X, Z) with respect to Z, has the following form [Pogodin et al., 2024]:
Ex (X) - (x) @ (d) - priz @ (Z)].
This decomposition significantly reduces the estimation error of the conditional mean embedding involved KCI. Theoretically, it avoids estimating the identity operator μzzz = (0))=((Z) (ZZ), which is not norm-bounded and, therefore, not Hilbert-Schmidt operator, leading to ill-specified regression problem. Empirically, under finite samples, if we approximate it as a miiteeddmmensionl vector-valued regression, the estimation of j' Z|Z in its original form is much less smooth compared to ('xzz. This implies lower 3 value (slower decay rate of the function's 's cigenvalues) in vector-valued regression [Fischer and Steinwart, 2020, Li et al., 2022], which corresponds
lower learning rate and higher estimation eтror (See Appendix F.5 for further discussion with a toy example.)
Asymptotic Normality. Our kernel selection criterion for KCI is based the asymptotic normality of U-statistics. We denote the KCI statistic EExyiallis as Ckcr for clarity. Then, we express Cke as follows:
Oker B [22 z') a (8, (s,8")r,, ("r)
(4)
where s and s' represents two different and independent copies of (X, YY,Y Z) with s (x, (s) is the inner product of regression residuals given by Tal (s, (dx(T) -xx]z(x);; oz - -xxi(zz)) and similarly for (s,
Suppose we have n i.i.d. observational points S { with 8; = (I,, Vo. 2;) being the one sample of (X, Y,,Y We can intuitively give unbiased U-statistic estimator for CKeT given by:
C Ck = (n)z²² Σ has and hig F 15 (s,, 8.j43
(5)

---

where (s; 8,)
- (x)x (xx(z))xx(x<<<)) (x)) and (5.. are the estimated residuals with estimated ūxi2 and ūyyzz 2. Cecn has expectation zero under the null hypothesis Ho: X Y Z, and has positive expected value under H1.
For a sufficiently large sample size n. Okcto can be considered as the asymptotic average of independent and identically distributed random variables. Based on the properties of U-statistics (see, e.g., Lee [2019, Section 3.2.1J, the asymptotic distribution of Ckc can be given by the Central Limit Theorem. If E(h²) со (which holds true for bounded continuous kernels): under the alternative hypothesis H1, where X f Y Z, we have:
Vn (C - - $ $0
(6)
where of = Var[h (s)] is the asymptotic variance with h1 (s) (2, With the fact that E, [1 (s)] Cec we can derive that
of = Var[ha (x:) = TR,, ((hn((()))) E., [hr (s:)]) E.,, Eay [sy]] -kkc]
(7)
Test Power. Based on the asymptotic normality in Eq. 6, we can estimate the test power, which represents the probability of correctly rejecting Ho when H1 is true for given case. For large enough n, assuming that the conditional expectations are well estimated, the power thus, using Pr to denote the probability under H1.
n |n(Cke - -KRI) r- nC
Pr (nCkcl > r) Pri
KCIu
2/n01
2/no1
(8)
VTCC
201
2/
where the CDF of the standard normal distribution and r the rejection threshold, which is constant for specified significance level. The test power therefore can be maximized by maximizing the argument in Since Ce and the asymptotic variance o are also constant, for reasonable large sample size n, the power is asymptotically dominated by the first term, i.e. VnCkee//21
Kernel selection. Following [Gretton et al., 2012b, Liu et al., 2020, Sutherland et al., 2021], we adopt the ratio of Ckec σ as our criterion, which asymptotically estimates the test power for the given kernel parameters. Both Ckc and σ₁ depend not only the underlying distribution but also the kernel parameters. In practice, we use their empirical estimators from training samples to estimate the test power under the given kernels:
j(S,w) w) C
where w denotes the kernel parameters to selected, and d the estimated asymptotic variance:
- -lha(s)) C2 Cxcmn 12=
huy
- C2
(10)
We evaluate this criterion across a candidate set of kernel parameters and select the one that maximizes ((,ww, which corresponds to the highest estimated test power.
Grid search- based kernel selection. We adopt grid search for kernel parameter selection rather than continuous optimization. Specifically, we predefine candidate set of kernel parameters, estimate the test power for each using Fq. 9, and select the one that maximizes the criterion for the final CI test. This design is motivated by the unique challenges of the CI testing setting. On one hand, KCIT involves estimating CMEs, which introduce intrinsic model estimation bias. This bias renders gradient-based optimization unreliable for improving test power, as convergence is not guaranteed- limitation we also verify empirically in Appendix F.4. Consequently, power-based continuous optimization fails identify optimal kernel parameters, undermining one of its main advantages.
One may also consider using an HSIC-like unbiased estimator [Song et al., 2012, Theorem 5]; however, it more complex and analytically intractable. This added complexity arises from the centralization of the kernel matrix in HSIC, which unnecessary for KCI since the residuals already estimated to have zero mean.
5

---

Nevertheless, while gradient information may be unreliable, the criterion itself remains informative. In particular, we show theoretically that under sufficiently large sample size, the proposed criterion can still reliably rank candidate kernel parameters, even when continuous optimization is infeasible. the other hand, continuous optimization in CI testing involves repeated regression estimation, resulting in significant computational cost and rendering it impractical for real-world applications. In contrast, grid search naturally supports parallelization, providing a more tractable alternative. We therefore adopt grid search practical and effective strategy for kernel selection in CI testing. The complete procedure is detailed in Appendix B.
4 Theoretical Result
In this section, establish the convergence properties of the proposed kernel selection criterion. Since CI testing indirectly measures the dependence between residuals, it is essential to consider both the segression-inducee estimation bias introduced by regressions and the random error resulting from finite data.
Thus, we impose the following assumptions on the boundedness of the kernels and CME estimators:
(Boundedness) Under the kernel parameters (Wzz Why wz), the kernel kwa, the residuals "xj2"
by and their empirical counterparts P riz
rriz are bounded:
sup (2,))c(X,2)
Indla S v, X|2
sup (,,=)<()i,2)
|r X|zz $ u,
sup zeZ
ku, $ V25
sup (2,))c(X
1 xiz S
sup (v.2)=(),2)
| xiz S..
Then hig and haj are bounded within [- M=N²
(EVD) (p4) are the eigenvalues of the operator Czz B[ @ (Z)] in the kernel ridge regression. For some Cy > 0 and & (0, 1] and for all i I,
M4 S cpp 5/p 1/p
(SRC) There exists 1 < 3 S 2 such that
Mxiz E [HS Jriz é [HS,=
where [HS] denotes the interpolation space of the original HS space (also written as [HS]'), ), the eigenvalues decay of the functions in [HS] is lower bounded by B.
Assumption (Boundedness) imposes boundedness constraints on the kernel function and residual terms, which are mild and typically satisfied under appropriately chosen kernels and standard regression algorithms. Assumptions EVD and SRC are standard in pector-valuee regression theory [Fischer and Steinwart, 2020, Li al., 2022], and are widely used characterize the convergence behavior of conditional mean regressors. Following [Pogodin et al., 2024], we focus on the well- specified cases with 3 и (1,2), and the corresponding Hilbert space norm is well-defined. The parameter /3 reflects the smoothness of the regression functions, with larger values indicating higher regularity. The choice of wir and Wy in w will affect the corresponding value of 3. The following theorem provides the convergence rate of the proposed criterion.
Theorem 3. Assuming the above assumptions hold. Let Q. be the subset of kernel parameters of w such that the asymptotic variance of 2 è² for some constant e O. Then, for any w e Qe, with probability at least 8, we have constant K 0 independent of and 5 that:
G2 CkeTt
21 + Cyn
(11)
Ō1,
1l,
where Ci &
64
2 ( )u.u WuKh and C2 (== 8
2 2
303
303
8"

---

The complete proof is provided in Appendix D, where we decompose the total error of the statis- tic estimator into two components: the regression-induus induced estimation bias and the random error arising from finite sampling, assuming accurate regression. The result shows that, for fixed kernel parameters, the empirical criterion converges to population counterpart, with a convergence rate governed by both components. The first term reflects the regression bias, which is influenced by both the smoothness of the true conditional mean functions and the choice of kernel parameters. The second term corresponds to the random variation due to finite-sample effects. The appearance of the bias term is intrinsic to CI testing, which evaluates dependence between residuals-unlin standard testing problems [Gretton et al., 2012b, Albert et al., 2022], where only variance terms typically considered. Nevertheless, for reasonably large sample size, the empirical criterion remains sufficiently close to the population counterpart, providing reliable basis for comparing test power across different kernel choices.
5 Experimental Results
In this section, we empirically analyze our Power method and its variant on CI tests using synthetic and real benchmarks, compare with baseline methods, and assess its impact causal discovery.
Implementation details. We use Gaussian kernels for all the kernels involved. For the kernel parameters of Φz and oy. we use the median heuristic as the initial value and apply different weights. Specifically, we take the median heuristic as a sensible initialization and use the candidate weight list 0..1,0.3, 0.75, 0.88, 1, 1.25, 1.5, 3, 5, 10]. applying each weight bandwidth. For K₂ in the statistic, we decide it using the median heuristic without further selection. That is, our method considers 10x x 10 100 possible parameter combinations. We evenly divide all samples into a training set and a testing set. During the testing phase, we use the weighted sum of chi-squared to compute p-value. The significance level is set to the default value of 0.05. Please refer to Appendix E.1 for more implementation details.
multiplier the median- -based
5.1 Synthetic Data
In the synthetic experiment, we assume X and are dependent variables conditioned on Z. We analyzed our method's performance under varying dimensions of the conditioning set Z and different sample sizes. To examine Type errors, we generated X and Y, which should be independent given Z, using the following nonlinear additive functional model:
X S(WT 2) + 7F,
(12)
where W ~ (O, Ia.) and de represents the dimension of Z, f was randomly chosen from the linear, sin, cos. x², 2n and exp(x). When f is neither sin nor cos, an additional 1/Vd, is multiplied to J(WT Z) to balance the scale of the function and noise. The noise was randomly chosen from either Gaussian or uniform distribution with the noise scale y = 1. To examine Type II errors, we added an additional variable T both X and Y, making them conditionally dependent given Z. T (O, 1), and
X= S 2
E oT,
(13)
with a= 0.5. For each setting, we randomly repeated the process 1000 times to obtain Type and Type error. For further implementation details, please refer to Appendix E.2.
5.1.1 Comparison with baseline methods
Baselines. We first compare our proposed power-based based method with CI baselines. Our proposed method is denoted as Power, while the median heuristic-based method is denoted as Median. In Median, we still decompose o(x, =) into ((x) @ d(2), and the kernel bandwidth is determined by the median heuristic without selection. In Power, we perform a grid search to select the kernel bandwidths involved in Φ5 and oy. choosing the parameters with the highest criterion for testing on the test data. We further compare it with the kernel based CIRCE [Pogodin et al., 2022], which only considers the independence between one-sided residuals and the other dependent variable itself. Additionally, we compare with regression- based methods GCM[Shah and Peters, 2020] and RBPT2 [Polo et al., 2023], which conduct the regression in 122 space. (See Appendix E.4 for more details about CIRCE, GCM and RBPT2).
7

---

Power
Median
CIRCE
GCM
RBPT2
1.6
Type
Tyle ve.y.
0.5
0.8
Trpe 1era
0.3
0.4
0.1
0.44
0.05
6.2
0.05
0.05
5.0
2.5
D1 01102000n of 22
Orersda 2. 02
Durple A0C
Figure 1: Performance comparison on synthetic data. Left: Type I error (a) and Type error (b) when
increasing the dimension of Z dz, keeping the sample size n 500 and noise scale y 1. Middle: Type error (c) and Type II error (d) when increasing samples size, keeping dz 5 and ? = 0.5.
Right: Type error (e) and Type II error (f) across different noise scales 7 (dz 5, = 500).
On the dimension of Z. Figure I(a) and (b) illustrate the performance of Power and baseline methods, with increasing the dimension of Z. In terms of Type I error control, RBPT2 and CIRCE failed to maintain Type error below the given significance level, while GCM slightly exceeds the given significance level. KCI-based Median and Power successfully controlled it, demonstrating the robustness of KCI. Regarding Type II error, RBPT2 exhibited a slight increase in Type II error as the dimension of Z increased, performing almost like random guessing in general. CIRCE accepted all instances of H1, which consistent with the performance on Type I error. Both Median and Power exhibit an increasing Type II error d2 increases. However, Power maintains consistently lower Type II error than Median by substantial margin. With a similar lower Type I error, it demonstrate that Power can effectively select more proper kernel parameters with higher test power while maintaining Type I eтгоr control across different dimensions setting. The above results reflect the robustness of KCI in controlling the Type error across a range of dependency structures, as well as the improvement of our Power over the median heuristic Median.
On the sample size. We also evaluated the performance by varying the sample size n, shown in Figure I(c) and (d). The performance of GCM and CIRCE remains consistent with previous analysis, showing no clear convergence trend as the sample size increases. Meanwhile, the Type II error of RBPT2 decreases as n increases, but its Type error remains uncontrolled. In contrast, our Power consistently outperforms the median beuristic-based Median across different sample sizes, and the gap between them does not diminish as n increases.
On the noise scale. In Figure I(c) and (f), we also analyzed the performance under different noise scales 7, with the scale of the latent variable T fixed at a = 0.5 (in Eq. 49). From the results, we observe that when the noise scale is relatively low, Power struggles to achieve further improvements through kernel selection. Conversely, when y is too large, making it difficult to separate T from the noise variable, Power also loses its effectiveness. This indicates that the improvement of Power over Median primarily stems from its ability to handle the overlapping region between Ho and H,, where different parameter choices correspond to different levels of overlap. However, when the overlap is either too small (7y is very low) or too large (7 is too high), the region that can be adjusted by kernel parameters becomes insignificant, reducing the effectiveness of our method.
Due to space constraints, additional results are provided in the appendix: experiments on a world conditional independence benchmark (car insurance dataset) in Appendix F.1.1, extended baseline comparisons and results on non-additive synthetic data in Appendix F.2, and evaluations under high-dimensional conditioning settings in Appendix F.3.
5.1.2 Ablation Study
In this section, we take a closer look at our method by studying its variants, with the results presented in Figure 2.
On the selectable kernels. In Figure 2(a) and (b), we examine the impact of kernel selection on different components by selecting only d0z) in the statistic (but not in the regression), denoted as SelZ, while fixing <(x) and (yy) using the median heuristic. Similarly, we consider selecting only d(v), denoted as SelY. SelZ does not improve the Type II error compared to Median, whereas SelY reduces the Type II error relative to Median but still underperforms Power. This suggests that one-sided selection is somewhat effective, but joint selection, as in Power, provides the best performance.
8

---

Sencatte Sarsel Oypeil
Senctata Marvia
(2) Sarteiss www.
Ear oppan Tppe
Ui Ramalllll opea 7ypa
sell
Luaton Foorr
3.22
0.02
Demanbbn
Figure 2: Ablation study on the dimension of Z with n 500 and y= (a) and (b) Different choices on the selectable kernels. (c) and (d) Different variants of the statistic and selection criterion. (e) and (f) Different kernel types.
On the decomposition. Additionally, in Figure 2(c) and (d), we compare against the original form of KCI without decomposing (xx,) (i.c., Eq. 2), denoted Org. The kernel parameters in Org are determined using the median heuristic without selection. We also consider a variant, denoted as OrgP, which applies the proposed kernel selection strategy both Φx and by in Org. In terms of Type I error, Org and OrgP exceed the significance level, indicating poor error control. While Org achieves slightly lower Type II error than Median, this suggests it tends over-detect conditional dependence due to insufficient removal of Z's influence. The weaker CME performance likely results from slower convergence, consistent with Appendix F.5. This highlights that using the original KCI without decomposition introduces notable estimation bias, affecting both test outcomes and the accuracy of the proposed criterion.
On the criterion. Fukumizu et al. [2009] proposed directly maximizing the statistic for kernel selection. We follow their approach and perform kernel selection directly based on the statistic itself, denoted as Stat. The results in Figure 2(c) and (d) show that Stat performs even worse than Median, with larger Type II error, highlighting the importance of selecting kernel parameters that need to simultaneously consider minimizing the asymptotic variance.
On the kernel types. In Figure 2 (e) and (f), we compare the performance of using different kernel types individually as well as jointly. Our method can also be applied with other suitable kernels or used select among different kernel classes. According the definition of the cross-covariance operator, x and ky in KCIT need to be characteristic kernels [Fukumizu et al., 2007]. Therefore, we conduct experiments using Gaussian and Laplace kernels. We use the same median heuristic to initialize the bandwidth in the Laplace kernel, along with the same pawer-based selection strategy. Our Power are also able perform selection over multiple kernel types (with median-heuristic initialization and fixed, denoted as Multi-Median) as well as over the parameters selectable version, referred as Multi- Power. We observe that for both Laplace and Gaussian kernels, the power- based kernel selection effectively reduces the Type II error. The performance of Multi-Power is slightly worse than that of Gaussian-Powe Poweer, suggesting that the Gaussian kernel is generally a strong choice and performs better than the Laplace kernel in most cases. The observed performance drop may be attributed estimation errors in the power computation. Overall, our method demonstrates the ability to effectively select parameters across multiple kernel types.
Table 1: Average testing time (s) = standard deviation on different sample sizes.
Sample Size 200
400
600
800
1000
Power 0.595+0.02
1.758+0.14
3.86940.60
9.641+2.37
10.12.6.54
Median
0.302+0.06
0.91440.14
1.74240.32
4.422+1.99
4.358+2.45
5.1.3
Testing Time
Power involves more regression learning with different parameters; however, due to the grid- search and the independence of different regressions, it enables efficient parallel training. Table 1 presents the overall runtime of Power compared to Median for different sample sizes. It shows that the testing time of Power is approximately twice that of Median. Notably, this additional computational cost does not increase linearly with the number of searches but considers over 100 parameter combinations, making it manageable and ensuring that our method remains practical for real-world applications. For more details, please refer to Appendix E.3.

---

5.2 Comparison on causal discovery
Our method can also be directly extended causal discovery tasks [Glymour et al., 2019, Zhang et al., 2018]. Formally, given a set of observations of random variables, causal discovery methods seek to depict the causal relationships among these variables through a directed acyelic graph (DAG). CI testing is central to constraint-based pipelines [Pearl and Mackenzie, 201 8]: early CI outcomes drive adjacency pruning and orientation rules, so inaccuracies can propagate and reshape the inferred graph. The overall fidelity of these methods therefore hinges on CI procedures that are reliable and stable across varying conditioning sets and sample sizes.
We compared the performance of Power with Median using the PC algorithm[Spirtes et al., 2000] as the search method. We generated the synthetic causal graphs with varying graph densities ranging from 0.2 to 0.8. Each generated graph involves 10 variables with sample sizes of 500. For each variable X; the graph, the data was generated according to X; = (WTTPA) E,, where PA; are parent nodes of X; in the graph, W; ~ No, Tapa) and E, is the noise term and Sa was randomly selected. Additionally, we conducted experiments on the real-world causal discovery benchmarks SACHs [Sachs et al., 2005] and CHILD [Spiegelhalter et al., 1993]. We evaluate Power and Median using Fl score and higher Fl score indicates greater accuracy From Table 2. Power outperforms Median in most graph density settings, particularly on denser graphs. Power also outperforms the median heuristic on both SACHs and CHILD. This indicates that our proposed kernel selection method, Power, can benefit causal discovery tasks in general. For more implementation details and results on SACHs and CHILD, please refer to Appendix E. and Appendix F.1.2.
Table 2: Fl score on synthetic graph and on the real world benchmarks. Bold represents the better.
Graph Density
0.2
0.3
0.4
0.5
0.6
0.7
0.8
SACHs
CHILD
0.656
0.637
0.603
0.581
0.567
0.515
0.461
0.674
0.762
Power
#0.057
+0.062
+0.047
+0.052
+0.044
+0.032
+0.045
+0.032
+0.052
0.657
0.623
0.586
0.548
0.523
0.490
0.443
0.576
0.790
Median
#0.067
+0.077
#0.032
+0.045
+0.042
+0.043
#0.037
#0.022
+0.044
Conclusion and Future Work
In this paper, we propose a practical kernel selection method for KCI, replacing the coarse median heuristic. To address the model estimation bias inherent in CI testing, we decompose the KCI statistic and perform parameter selection via grid search based on the estimated test power. We provide a convergence analysis of the proposed criterion that explicitly accounts for estimation error, and experimental results validate the effectiveness of our approach.
Currently, the search procedure relies on a fixed grid, which does not guarantee optimal parameter selection. Moreover, the current theoretical framework does not yet provide formal Type I error control for KCI under general conditions, unlike results established in more restrictive settings such as additive models [Shah and Peters, 2020, Niu al., 2024]. This limitation stems from the fact that KCI addresses general CI relationships. leading to a more tractable null distribution with kernel components. And the null distribution of KCI remains complex and sensitive to estimation bias. A promising future direction is to establish uniform convergence results over kernel parameters and derive the conditions and convergence rates for valid Type error control. Such developments would pave the way for a more flexible and theoretically grounded adaptive kernel selection strategy: bringing KCI closer to achieving optimal kernel choice for CI testing.
Acknowledgements
We would like to acknowledge support from ARC (DP240102088, DP230101540, DE240101089, LP240100101), the NSF LDMS-2428058, Award No. 2229881), the RGC (Young Collaborative Research Grant No. C2005-24Y; General Research Fund No. 12200725). the AI Institute for Societal Decision Making (AI-SDM), the National Institutes of Health (R01 HL 159805), and grants from Quris AI, Florin Court Capital, the MBZUAI-WIS Joint Program, and the Al Deira Causal Education project, as well as the NSF&CSIRO Responsible AI program (Grant No. 2303037).
10

---

References
Peter Spirtes, Clark N Glymour, Richard Scheines, and David Heckerman. Causation, prediction, and search. MIT press, 2000.
Peter Spirtes, Christopher Meek, and Thomas Richardson. Causal inference in the presence of latent variables and selection bias. Proceedings of the Eleventh conference on Uncertainty artificial intelligence, pages 499-506, 1995.
Judea Pearl et al. Models, reasoning and inference. Cambridge, UK: CambridgeUnniveriiyPPrss,, 19 (2):3, 2000.
Biwei Huang, Kun Zhang, Jiji Zhang, Joseph Ramsey, Ruben Sanchez-Romera Clark Glymour, and Bernhard Schölkopf. Causal discovery from beterogeneous/nonstaiinnyyy data. Journal of Machine Learning Research, (1(89)11555 2020.
Haoang Chi, He Li, Wenjing Yang, Feng Liu, Long Lan, Xiaoguang Ren, Tongliang Liu, and Bo Han. Unveiling causal reasoning in large language models: Reality or mirage? Advances in Neural Information Processing Systems, 11196640-966777 2024.
Ninareh Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan. A survey on bias and fairness in machine learning. ACM computing surveys (CSUR), 54(6):1-35, 2021.
Bo Han, Jiangchao Yao. Tongliang Liu, Bo Li, Sanmi Koyejo. Feng Liu, et al. Trustworthy machine learning: From data to models. Foundations and Trends@ in Privacy and Security, 7(2-3):74-246, 2025.
Kenji Fukumizu, Francis R Bach, and Michael Jordan. Kernel dimension reduction in regression. The Annals of Statistics, 17(4):1871-1955, 2009.
Le Song, Alex Smola, Arthur Gretton, Justin Bedo, and Karsten Borgwardt, Feature selection via dependence maximization. Journal Machine Learning Research, 13(5), 2012.
Dimitris Margaritis. Distribution-free learning of bayesian network structure in continuous domains. In AAAI, volume 5, pages 825-830, 2005.
AJ Lawrance. On conditional and partial correlation. The American Statistician, 30(3): 1463):1461499 149, 1976.
Oliver B Linton and Pedro Gozalo. Conditional independence restrictions: testing and estimation. 1996.
JJ Daudin. Partial association measures and application to qualitative regression. Biometrika, 67 (3):581-590, 1980.
Kun Zhang, Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Kernel-based conditional independence test and application in causal discovery. In Proceedings of Conference on Uncertainty in Artificial Intelligence, pages 804-813, 2011.
Kenji Fukumizu, Arthur Gretton, Xiaohai Sun, and Bernhard Schölkopf. Kernel measures of conditional dependence. Advances in neural information processing systems, 20, 2007.
Arthur Gretton, Karsten M Borgwardt, Malte J Rasch, Bernhard Schoelkopf, and Alexander Smola. kernel two-sample test. Journal of Machine Learning Research, 13, 2012a.
Le Song, Jonathan Huang, Alex Smola, and Kenji Fukumizu. Hilbert space embeddings of condi- tional distributions with applications to dynamical systems. Proceedings of the 26th Annual International Conference Machine Learning, pages 961-968, 2009.
Steffen Grünewälder, Guy Lever, Luca Baldassarre, Sam Patterson, Arthur Gretton, and Massimilano Pontil. Conditional mean embeddings as regressors. In Proceedings of the 29th International Coference on International Conference Machine Learning, pages 1803-1810 2012.
Arthur Gretton, Olivier Bousquet, Alex Smola, and Bernhard Schölkopf. Measuring statistical dependence with hilbert-schmidt norms. International conference on algorithmic learning theory, pages 63-77. Springer, 2005a.

---

Bharath K Sriperumbudur, Arthur Gretton, Kenji Fukumizu, Gert Lanckriet, and Bernhard Schölkopf. Injective hilbert space embeddings of probability measures. In 21st Annual Conference on Learning Theory (COLT 2008), pages 111-122. Omnipress, 2008
Michael Brockmann, Theo Gasser, and Eva Herrmann. Locally adaptive bandwidth choice for kernel regression estimators. Journal of the American Statistical Association, 130--1333, 1993.
Olivier Chapelle and Vladimir Vapnik. Model selection for support vector machines. Advances in neural information processing systems, 12, 1999.
Bernhard Schölkopf, Alexander J Smola, Francis Bach, et al. Learning with kernels: support vector machines, regularization, optimization, and beyond. MIT Press, 2002.
Aaditya Ramdas, Sashank Jakkam Reddi, Barnabás Póczos, Aarti Singh, and Larry Wasserman. On the decreasing power of kernel and distance based nonparametrie hypothesis tests in high dimensions. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 29, 2015.
Damien Garreau, Wittawat Jitkrittum, and Motonobu Kanagawa. Large sample analysis of the median heuristic. arXiv preprint ( 2017.
Arthur Gretton, Bharath Sriperumbudur, Dino Sejdinovic, Heiko Strathmann, Sivaraman Balakrish- nan, Massimiliano Pontil, and Kenji Fukumizu. Optimal kernel choice for large-scale two-sample tests. In Proceedings of Conference on Advances in Neural Information Processing Systems, pages 1205-1216 1213, 2012b.
Feng Liu, Wenkai Xu, Jie Lu, and Danica Sutherland. Meta two-sample testing: Learning kernels for testing with limited data. Advances in Neural Information Processing Systems, 34:5848 15684,-5860, 2021.
Felix Biggs, Antonin Schrab, and Arthur Gretton. Mmd-fuse: Learning and combining kernels for two-sample testing without data splitting. Advances in Neural Information Processing Systems, 36: 75151-75188, 2023.
Mélisande Albert, Béatrice Laurent, Amandine Marrel, and Anouar Meynaoui. Adaptive test of independence based on hsic measures. The Annals of Statistics, 50(2):858 889888879778 879, 2022.
Feng Liu, Wenkai Xu, Jie Lu, Guangquan Zhang, Arthur Gretton, and Danica J Sutherland. Learning deep kernels for non-parametric two-sample tests. In International conference machine learning, pages 6316-6326. PMLR, 2020.
Nathaniel Xu, Feng Liu, and Danica J Sutherland. Learning deep kernels for non-parametric independence testing. arXiv preprint arXiv:2409 006800 2024.
Rajen D Shah and Jonas Peters. The hardness of conditional independence testing and the generalised covariance measure. The Annals of Statistics, 48(3):1514, 2020.
Emmanuel Candes, Yingying Fan, Lucas Janson, and Jinchi Lv. Panning for maddellxee-xx knockoffs for high dimensional controlled variable selection. Journal of the Royal Statistical Society Series B: Statistical Methodology, 80(3):551-577, 2018
Thomas B Berrett, Yi Wang, Rina Foygel Barber, and Richard J Samworth. The conditional permutation test for independence while controlling for confounders. Journal of the Royal Statistical Society Series B: Statistical Methodology, 82(1))115--19 197, 2020.
Gary Doran, Krikamol Muandet, Kun Zhang, and Bernhard Schölkopf. A permutation- kernel conditional independence test. In UAI, pages 132-141, 2014.
Xiaohai Sun, Dominik Janzing, Bernhard Schölkopf, and Kenji Fukumizu. A kernel-based causal learning algorithm. In Proceedings of the 24th international conference on Machine learning, pages 855 862, 2007.
Zhen Huang, Nabarun Deb, and Bodhisattva Sen. Kernel partial correlation coefficient- a measure of conditional dependence. Journal of Machine Learning Research, 23(216): 2022.
12

---

Yixin Ren, Yewei Xia, Hao Zhang, Jihong Guan, and Shuigeng Zhou. Learning adaptive kemness for statistical independence tests. In International Conference on Artificial Intelligence and Statistics, pages 2494-2502 PMLR, 2024a.
Yixin Ren, Yewei Xia, Hao Zhang, Jihong Guan, and Shuigeng Zhou. Efficiently learning significant fourier feature pairs for statistical independence testing. Advances in Neural Information Processing Systems, 111999000998333 2024b.
Arthur Gretton. Introduction rkhs, and some simple kernel algorithms. Adv. Top. Mach. Learn. Lecture Conducted from University College London, 16(5-3):2, 2013.
Roman Pogodin, Namrata Deka, Yazhe Li, Danica J Sutherland, Victor Veitch, and Arthur Gretton. Efficient conditionally invariant representation learning. In The Eleventh International Conference Learning Representations, 2022.
Roman Pogodin, Antonin Schrab, Yazhe Li, Danica J Sutherland, and Arthur Gretton. Practical kernel tests of conditional independence. arXiv preprint 1rXiv:2402.13/90 2024.
Afsaneh Mastouri, Yuchen Zhu, Limor Gultchin, Anna Korba, Ricardo Silva, Matt Kusner, Arthur Gretton, and Krikamol Muandet. Proximal causal learning with kernels: Two-stage estimation and moment restriction. In International conference on machine learning, pages 7512-7523, PMLR, 2021.
Simon Fischer and Ingo Steinwart. Sobolev norm learning rates for regularized least-squares algorithms. Journal of Machine Learning Research, 21(255): 2020.
Zhu Li, Dimitri Meunier, Mattes Mollenhauer, and Arthur Gretton. Optimal rates for regularized conditional mean embedding learning. Advances Neural Information Processing Systems, 35: 4433 4445,444,,222 2022.
AJ Lee. U-statistics: Theory and Practice. Routledge, 2019.
Danica J Sutherland, Hsiao-Yu Tung, Heiko Strathmann, Soumyajit De, Aaditya Ramdas, Alex Smola, and Arthur Gretton. Generative models and model criticism via optimized maximum mean discrepancy. In International Conference on Learning Representations, 2021.
Felipe Maia Polo, Yuekai Sun, and Moulinath Banerjee. Conditional independence testing under misspecified induetive biases. In Seirth-seventh Conference on Neural Information Processing Systems, 2023.
Clark Glymour, Kun Zhang, and Peter Spirtes. Review of causal discovery methods based graphical models. Frontiers in genetics, 10:524, 2019.
Kun Zhang, Bernhard Schölkopf, Peter Spirtes, and Clark Glymour. Learning causality and causality- related learning: some recent progress. National science review, 5(1):26-29, 2018.
Judea Pearl and Dana Mackenzie. The book of why: the new science of cause and effect. Basic books, 2018.
Karen Sachs, Omar Perez, Dana Pe'er, Douglas Lauffenburger, and Garry P Nolan. Causal protein- signaling networks derived from multiparameter single-cell data. Science, 308(5721):523-522) 2005.
David Spiegelhalter, A Philip Dawid, Steffen L Lauritzen, and Robert G Cowell. Bayesian analysis in expert systems. Statistical science, pages 219-247, 1993.
Ziang Niu, Abhinav Chakraborty, Oliver Dukes, and Eugene Katsevich. Reconciling model-x and doubly robust approaches to conditional independence testing. The Annals of Statistics, 52(3): 895-921, 2024.
Zhanrui Cai, Runze Li, and Yaowu Zhang. A distribution free conditional independence test with applications to causal discovery. Journal of Machine Learning Research, 23(85): 2022.
13

---

Wenqin Liu, Biwei Huang, Erdun Gao, Qiuhong Ke, Howard Bondell, and Mingming Gong. Causal discovery with mixed linear and nonlinear additive noise models: A scalable approach. In Causal learning and reasoning, pages 1237-1263. PMLR, 2024.
Yingyu Lin, Yuxing Huang, Wenqin Liu, Haoran Deng, Ignavier Ng. Kun Zhang, Mingming Gong, Yian Ma, and Biwei Huang. skewness based criterion for addressing heteroscedastic noise in causal discovery. In The Thirteenth International Conference on Learning Representations, 2024.
Cyrill Scheidegger, Julia Hörrmann, and Peter Bühlmann. The weighted generalised covariance measure. Journal of Machine Learning Research, 23(273): 2022.
Yue He, Peng Cui, Zheyan Shen, Renzhe Xu, Furui Liu, and Yong Jiang. Daring: Differentiable causal discovery with residual independence. In Proceedings of the 27th ACM SIGKDD conference on knowledge discovery & data mining, pages 596-605, 2021.
Shuai Li, Yingjie Zhang. Hongtu Zhu, Christina Wang, Hai Shu, Ziqi Chen, Zhuoran Sun, and Yanfeng Yang. K-nearest-neighhorr local sampling based conditional independence testing. Advances in Neural Information Processing Systems, 36:23321-23344 2023.
Rajat Sen, Ananda Theertha Suresh, Karthikeyan Shanmugam, Alexandros G Dimakis, and Sanjay Shakkottai. Model-powered conditional independence test. Advances in neural information processing systems, 30, 2017.
Yi Zhang, Linjun Huang, Yun Yang, and Xiaofeng Shao. Doubly robust conditional independence testing with generative neural networks. arXiv preprint arXiv:2407.17699 2024.
George Kour and Raid Saabne. Fast classification of handwritten on-line arabic characters. In Soft Computing and Pattern Recognition (SoCPaR), 2014 6th International Conference of. pages 312-318. IEEE, 2014. doi: 10.100/SOCPARR2014700588
Meyer Scetbon, Laurent Meunier, and Yaniv Romano. An asymptotic test for conditional indepen- dence using analytic kernel embeddings. In International Conference on Machine Learning, pages 19328-19346. PMLR, 2022.
Arthur Gretton, Olivier Bousquet, Alex Smola, and Bernhard Schölkopf. Measuring statistical dependence with hilbert-schmidt norms. In International conference on algorithmic learning theory, pages 63-77. Springer, 2005b.
Seung-Jean Kim, Alessandro Magnani, and Stephen Boyd. Optimal kernel selection in kernel fisher discriminant analysis. In Proceedings of the 23rd international conference on Machine learning. pages 472, 2006.
C-K Chu and James S Marron. Choosing kernel regression estimator. Statistical science, pages 404-414 (09,419,,0 1991.
Eva Herrmann, Theo Gasser, and Alois Kneip. Choice of bandwidth for kernel regression when residuals are correlated. Biometrika, 79(4)7783-795 1992.
Antonin
Schrab, Ilmun Kim, Benjamin Guedj, and Arthur Gretton. Efficient aggregated kernel tests using incomplete u-statistics. Advances in Neural Information Processing Systems, 35: 18793-18807, 2022.
Arthur Gretton, Kenji Fukumizu, Choon Teo, Le Song, Bernhard Schölkopf, and Alex Smola. A kernel statistical test of independence. Advances in neural information processing systems, 20, 2007.
Dong C Liu and Jorge Nocedal. On the limited memory bfgs method for large scale optimization. Mathematical programming, 45(1-3):503-522 1989.
Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirchner. Machine bias. In Ethics of data and analytics, pages 254-264. Auerbach Publications, 2022.
Jonas M Kübler, Vincent Stimper, Simon Buchholz, Krikamol Muandet, and Bernhard Schölkopf.
Automl two-sample test. Advances in Neural Information Processing Systems, 35:1 11115999999991 2022.
14

---

Jie Wang. Santanu S Dey. and Yao Xie. Variable selection for kernel two-sample tests. arXiv preprint arXiv:2302.07415..2 2023.
Appendices
In the appendix, we provide additional discussions on related work, the assumptions required for the theoretical guarantees, complete proofs of the main results, well as further experiments and analysis. The structure as follows:
Appendix A provides an overview related work relevant to our proposed method, including recent developments in kernel-based conditional independence testing.
Appendix describes the training and testing procedures used:
Appendix B.1: The kernel selection and test procedure overview.
Appendix B.2: Details of the testing pipeline.
Appendix C presents the theoretical assumptions required to ensure the validity of our convergence results and the consistency of the proposed criterion.
Appendix contains the complete proof of the convergence rate (Theorem 3), including:
Appendix D.1: The convergence rate of rj.
Appendix D.2: The convergence à.
Appendix D.3: Supporting results on conditional mean embedding (CME) convergence.
Appendix provides implementation and experimental setup details, including:
Appendix E.1: Model hyperparameter settings.
Appendix E.2: Synthetic data generation procedures.
Appendix E.3: Runtime benchmarking configurations.
Appendix E.4: Description of conditional independence testing baselines.
Appendix F includes additional experimental results and discussions beyond the main paper:
Appendix F.1: Real-data evaluation.
* Appendix F.1.1: Results on the car insurance dataset.
Appendix F.1.2: Causal discovery benchmarks.
Appendix F:2 More results on synthetic datasets.
Appendix F3: Analysis under high-dimensional conditioning.
Appendix F4:: Comparison with continuous kernel parameter optimization.
Appendix F.5: Toy example illustrations.
A
Related work
Conditional independence testing. Conditional independence (CI) testing serves as a fundamental building block in many machine learning and statistical inference tasks, especially causal discovery [Zhang et al., 2011, Cai al., 2022, Liu al., 2024, Lin et al., 2024]. There growing body of literature on conditional independence test, which can be roughly divided into three groups: (1) regression- based methods [Shah and Peters, 2020, Polo et al., 2023, Scheidegger et al., 2022, He et al., 2021]; J; (2) simulation-ball based methods [Doran et al., 2014, Candes et al., 2018, Berrett et al., 2020, Li et al., 2023, Sen et al., 2017, Zhang et al., 2024] and (3) bessel-based methods [Zhang et al., 2011, Fukumizu al., 2007, Kour and Saabne, 2014, Scetbon et al., 2022].
Regression-based methods require assumptions about the relationship and noise structure, well as the assumptions of removal of any information from the conditioning set Z by regression. When these assumptions hold, regression-battt error, otherwise, they do not. Another important category is simulation- based methods (also known as randomization-based methods), which primarily implicitly or explicitly approximate the conditional distributions Px]2 or Pylz to simulate the null distribution. A clear drawback is that such approaches often come with significant approximation errors, leading to an inflation of the type-I error and rendering the test invalid.
methods have been shown effectively control Type I
15

---

Kemne--based CI methods, on the other hand, do not require additional assumptions and can detect general dependence. By mapping variables into RKHS, kemnel functions enable the assessment of similarities between high-dimensional implicit functions, thereby capturing higher-order statistical moments. Utilizing characteristic kernels allows us to infer distribution properties such as homo- geneity [Gretton et al., 2012a], independence [Gretton et al., 2005b], and conditional independence [Fukumizu et al., 2007, Sun et al., 2007, Zhang et al., 201 I, Huang et al., 2022]. These properties make kernel-based methods capable of discerning conditional independence in CI tasks without the need to simulate intricate conditional distributions.
The hardness of CI testing. Due to the unique nature of CI testing, Shah and Peters [2020] demonstrated that a valid CI test does not have power against any alternatives. This implies that no method can simultancously control the Type I error rate at the given significance level while maintaining adequate power. This is due to the inherent nature of the CI testing task, which requires considering conditional distributions that are difficult to directly obtain and estimate from observed samples. As a result, CI testing inherently requires accounting for estimation errors, whereas other hypothesis testing tasks do not. Consequently, reducing estimation error is crucial for CI testing.
Based on this challenge, several assumptions have been proposed. The Model-X assumption [Candes et al., 2018] assumes that one side of the conditional distribution (or its likelihood) is known exactly, Another class of approaches, known as doubly robust methods [Shah and Peters, 2020], imposes stricter requirements on the convergence rate of estimation errors to ensure reliable testing. The kernel-based KCI can currently only achieve pointwise Type error control, and its underlying assumptions require further investigation. In this paper, we decompose the original KCI formulation, which has been shown to reduce the estimation error of residuals, thereby improving the validity and reliability of the test.
Kernel selection. Although kernel-based methods are capable of detecting general dependencies between variables, a critical aspect that significantly influences their effectiveness is the choice of kernel functions. This selection process primarily focuses on tuning kernel parameters, such as the bandwidth in radial basis function (RBF) kernel. which can often be more influential than the choice of the kernel family [Schölkopf al., 2002, Section 4.4.5]. Most existing kernel-involved methods rely on heuristic parameter selection, typically choosing the bandwidth of Gaussian kernels based on the median of pairwise distances in the data, a strategy commonly referred to as the median heuristic [Schölkopf et al., 2002]. [Kim et al., 2006] The selection of appropriate kernels remains an unresolved question in numerous studies [Chu and Marron, 1991, Herrmann et al., 1992 Chapelle and Vapnik, 1999, Kim et al., 2006]. Fukumizu et al. [2009] propose selecting kernel parameters by directly maximizing the MMD statistic itself, which is shown to be equivalent to minimizing the classification error under linear loss. However, Gretton et al. [2012b] argue that this approach is suboptimal, as it neglects the variance component of the test statistic. They instead propose using a Matisticcto-varte variance ratio criterion surrogate for the estimated test power under the current kernel parameters.
Variants of this criterion have been further developed and applied to tasks such as two-sample testing [Liu et al., 2021, Biggs et al., 2023], unconditional independence testing [Albert et al., 2022, Ren et al., 2024a,b], and goodness-of-fir testing [Schrab et al., 2022]. These methods support continuous optimization of kernel parameters and are capable of selecting near-optimal or even oracle kernel parameters. Furthermore, deep kernels parameterized by neural networks have also been proposed and integrated into these testing tasks, as in [Liu et al., 2020, Xu et al., 2024]. While these advances have shown promise, they are not directly applicable to CI testing task. Both two-sample testing and unconditional independence testing directly measure distributional differences between variables, where the main source of error typically arises from finite-sample variability. In contrast, CI testing is substantially more difficult, as it requires accounting for the conditional distributions, which may act latent sources of dependence. This often necessitates residualization procedures to remove the conditional effect, as implemented in methods such as KCI or GCM [Shah and Peters, 2020]. Therefore, for CI task, it possesses distinct characteristics, primarily involving the consideration of regression residuals, which inherently contain biases. And the choice of kernel is intuitively crucial for kernel-based CI methods, but has remained an open issue.
Both two-sample testing and unconditional independence testing directly assess distributional dif- ferences between variables, where the primary source of error typically arises from umite-sample variability. In contrast, CI testing is substantially more challenging, as it involves reasoning about
16

---

conditional distributions, which can act as latent sources of dependence. To address this, residu- alization procedures are often employed remove the conditional effect, after which conditional independence is assessed based on the resulting residuals, as in methods such as KCI or GCM [Shah and Peters, 2020].
result, CI testing presents distinct challenges- on regression residuals, which inherently introduce estimation bias. While the choice of kernel is intuitively critical for the performance of kernel-based CI methods, identifying principled strategies for kernel selection remains open and unresolved problem.
notably, the reliance
B
Procedure Details
B.1 Overall procedure
Algorithm 1: Overall Procedure of Power
Input:
Observations (X, Y, Z) for training St, ((1 We, 2;)) and for testing Sto; kernel types for 62, Py Φ2; candidate parameter weights.
Output: Test decision of X Y
Z. |
// Step 1: Initialize kernel parameters
Use median heuristic to compute initial kernel widths wr. Ws;
Generate candidate lists for w2 and wy by applying predefined weight multipliers;
3 Fix w, as the median heuristic value (no selection);
// Step 2-4 can be computed independently and thus parallelized foreach parameter combination w; (Wa,Wy) in parallel do
// Step 2: Compute conditional embeddings Compute kernel matrices Kx, Ky, Kz;
Estimate M = (K2 + -0:=7)1-pp00 (X));
(x)))
Estimate MY|2 (K =
// Step 3: Compute residual matrices
Compute projection operator Rz =(K + +el) Compute Rxiz = R2KxRz, Ry Rz Ky Rz:
// Step 4: Evaluate criterion
Compute (S,w. in Eq. 9;
// Step 5: Select optimal kernel parameters Choose Wmn arg max,, w(Sw;:);
// Step 6: Final testing
Perform the test using the selected parameters w., on test samples Szci
13 Refer to Appendix B.2 for test procedure details;
14 return Test result (reject/do not reject Ho: X LY| Z);
B.2 Testing procedure details
After selecting the kernel parameters with the maximum estimated test power on the training set, we follow the original KCI testing procedure to perform the testing process on the test set. With m testing points, the KCI statistic Cei has a biased HSIC-like estimator [Gretton et al., 2005b]:
ČkCL = n(n-1) Tr[( o R R)
(14)
We first compute the residual covariance matrices R and Rie and the kernel matrix K with the selected Wm- Then, we denote K R'e z @ K and L Kýjz and let the EVD decomposition of K and be K Vx Ax Vx and = Vz Ag (resp. A1) is the diagonal matrix containing non-negative eigenvalues λK, (resp. \t,i). Let t/x [v..1(x).-.. (=)] V 1/2 and
Φr. [dr,, 2y.z). &r,, =)]= = Vr.A And its null distribution can be approximated in two ways: (1) weighted (infinite) sum of variables, or through (2) Gamma approximation.
17

---

Weighted sum of x² approximation. Under Ho, X 11 Y Z, CkCI, has the same asymptotic distribution as
Tb n(n 1) k=1
A =k
(15)
where 2ạ ~ (O, 1) and where 'g are eigenvalues of ww and [Wi,",, with the vector w, obtained by stacking M, (x)) (n.,). conclusion primarily relies on the continuous mapping theorem, for details refer to [Zhang al., 2011, Theorem 3].
[ (Vr, 21....... ".. (Vt, =)] This
Gamma approximation. Following [Gretton et al., 2007], the null distribution for the KCI estimator
+ (T(LL) can also be approximated by a Gamma distribution, which is p(t) gh-1 e- parameters
with the ("06))
k 11
1 #= -=rr(ww")) and a² = Tr T n
with
(16)
ny
7
Therefore, one can use Monte Carlo simulation to approximate the null distribution according the two approaches mentioned above. The complete testing procedure is as follows: we first estimate the conditional means 2xl2 and Jy and learn the parameters in Φ on the training data and calculate the K Xx|z, Kyzz and Kz on the testing data and the eigenvalues and eigenvectors of K and T, defined above. Then we evaluate the statistic CkCI, according to Equation 14. And then we simulate the null distribution either by (1) weighted sum of x2 approximation (according to Eq. 15) or (2) Gamma approximation (with the parameters given by Eq. 16). We then obtain a set of statistics T (T,..., Tm) through sampling. Then the p-value is calculated the proportion of the statistic T3 in T that is greater than Č2 CCI, Finally, if the p-value is not greater than the given significance level a, we reject Ho and hold H1; otherwise, we hold Ho-
C Assumptions
To analyze the convergence rate of the statistic, we require some assumption follows under certain fixed kernel parameters = (We, Wyy Wz):
suly The kernel lww. the residuals "izz rriz and their corresponding estimates X222 Pyiz are uniformly bounded:
sup (x,)))(XX22
In 1x (2, (0), s
sup (v.=)e(U12)
In (v.3)))
sup kin, (2,2) S V22 se2
(Boundedness)
sup (,,2)c(21,2)
| (x, su,
sup (v.))(().2)
| (U. sv..
To simplify the notation, we denote C, v.v2. Consequently, hiy and his are bounded in the range [-C,, Cy].
We require some additional assumptions regarding the CMEs involved for the analysis of the con- vergence of the CMEs involved (μx z and (y]z). We directly adopt the framework and the regular assumptions from [Pogodin et al., 2024], which were originally introduced in [Fischer and Steinwart, 2020, Li al., 2022]. We use the same names for the following assumptions to align with those in [Fischer and Steinwart, 2020].
(uu)ier is the eigenvalues of the operator Czz E[) (2(). For some c, 0 and p e (0, 1] and for all i
P4 S
(EVD)
There exists 1 < <B3 5 such that
Mxjz [HS Myiz [HS
(SRC)
where [HS] represents the interpolation space of the original space HS (also written as [HS]*), and the eigenvalues decay of the functions in [HS] is lower bounded by B.
18

---

In [Fischer and Steinwart, 2020, Li et al.. 2022], there is another assumption embedding property (EMB), was introduced, which implies a polynomial eigenvalue decay of order 1/a for Czz. Since the EMB condition is always satisfied for 1 and bounded kernel kz, it follows that, under As- sumption Boundedness, the EMB condition consistently satisfied within our framework. Therefore, we do not repeat further here.
D Proof of Convergence Rate
Theorem 4. Assuming that we and Wy can parameterize uniformly bounded residuals 'xiz and My Let Qhe be the set of kernel parameters of w for which the asymptotic variance of 2 c² with a positive constant Under Assumptions (Boundedness), (EVD) and (SRC), and given that the kernel selection procedure exhibits density over See then with probability at least 1
C Ckem
O (Cin
#-1 Z1++p
C2n
(17)
Ō1,w
where Ci = (== 64v22A
4 and C2 (
8 3x3
2 8
) DUNv uK In
ln n
3c3
Proof. We denote C with the kernel parameters w = (War Wy, wz) as Tw: its unbiased estimator Ō as fuw for clarity, Similarly, the asymptotic variance 01, is shorten as ow with its corre- sponding regularized estimator 01, as ow. For reasonable large sample size no which holds eq. (46), we have ow 2 with high probability. Then with Assumption (Boundedness) that [hayl s Cz, we C2 and M s C.. We begin by decomposing
obtain | = |E] hee ]|
nw ow
P
Tl
1
b -02
1
<
+ -
1i nwl
ow
ww
Ow
ow
ow Tw &w ow
ow
(18)
C₁
4vgu²
102
nul
Miw
nwl+
100 - -02l-
(c+ 2
303
The convergence rate of ihs and oă proved in lemma 5 and lemma 6, respectively. Thus, with probability at least 1 - 6, the error is at most
G4 303
2 2 8 n
D. uK 5 z.n म[+p! (- )u,
12 (19)
3c3
D.I The convergence rate of iNw.
Lemma 5. Under Assumptions (Boundedness), (EVD) and (SRC), under the kernel parameters w. we have that with probability at least 1 6,
Niw Thwl s 2 21m( 4
8-1 NPr
2 5
2 2
n
(20)
Proof. The statistic The includes both estimation error and random error. We use T denote the estimate of nhe where the estimation error of the CMEs μx|z and Jy|z is removed on the finite samples S {s:) which is
i = n(n- 1)
Σ hij n(n-1) (i.5)eiz (iJ)ctz
Σ
kz 2i) (8 (1
(21)
where (x) 87) = (0x(2:) (xxz((2) (x,)) - - (x)z Then we can decompose hiw nul by
W - nod s hiw Fmol + 1iw nul
(22)
19

---

where hi Bue represents the estimation error (bias), while 1 nw is the random error (variance). should be noted that the two factors contribute the statistical estimation in a complex and mixed manner. We will separate them for more intuitive analysis.
Estimation bias. The estimated bias is given by
M nnl n(n - 1) 1.41
Σ hio higl
(23)
n(n
rx 2 (I,s 2 )r 2 (vt. To simplify the notation, we use Asy to replace xx 2 83) with Aij ixxzz (2i,, ,y), and use Big and Big to replace the corresponding ry 2 Vi) and Big = (xiz 8j), respectively, Then given kz (0, v2 we can derive that
with lho hurl= (2,, 2)) (x, 1))1 ( H2)
[hi hayl - 1z
A15 Bij ( A. Byy (2), (4)) A1)) + Ao B:y)). (24)
where
Ag
- (elta:/kkkkkiiinnnnmm)))o6)oo-/- -x1((z))++
(anpccahiiittt----nnmo))))aa4ana (x(z(z)))
-xx
(x)z(()) uxiz(z))).
(25)
According to the Cauchy-Schward Schwwaz inequality and the bound of CME in theorem we can derive that with probability at least - -T for 7
|Ay A.l s (x(:)) (xxx(2))--xxxx(() (xx(()))+( -xxx)))))) (axzz(x) (x)
52 V Kn 2TV 2ह....
(26)
The same notations B,y and Bij are also applied to with the same bound. Given the bound kz (0.vz). 14j] and |A:yl & we can derive that
hbg huy = K2 (2 24) Auy) (n B&y)
$ kz 2j) [1(A,; Aij) Biyl + |Ai (Bij - B1y) #11
(27)
2-1 s 2v. 2T vKn 2[कपा] 4TV v/ Kn [[2pp]
Therefore, we can give the estimate bias bound
Σ h nul n(n 1) 8,7m2
lhg her s 4TUgU² Kn 2(--p]
(28)
Random error. For the random error, first consider replacing S with s/z = (a'g- 3/2- 2{) and keep the remaining samples in the same. Given h and h are bounded in [-Cv, C. ) the difference between â. and the new substitution e with of is given by
McDiarmid's inequality obtain the bound. We
Ihite hixl + Σ lhws hasl izk
Σ
n( - 1)
jzk
(29)
2
4C,
Σ
Mlik his
n(n
izk
nl
20

---

Now using McDiarmid's inequality, for come certain and fixed w, with probality at least 1 8, the random error function (w(w) f... :h:
2
M nal 2v.u²
In
(30)
n
Finally, by combining Eq. 28 and Eq. 30 with In(4/6), finish the proof:
4 hiw nwl s 41m(
#-1 2.++o
)u.ut
Kn
In
8
(31)
21n 4 2vg
+ +VV
2
n
5
Since E (1, and p (0, 1]. 2(3+p) always holds. Therefore, even the well-specified cases, the еπrоr is primarily dominated by the estimation bias with its slower convergence rate. As for the misspecified scenario with slower learning rate O(( log 8-11) and é (0,1). the estimation error will become increasingly dominant.
D.2 The convergence of o...
Lemma 6. Under Assumptions (Boundedness), (EVD) and (SRC), under the kernel parameters w = (Wz,Wy), we have that with probability at least 6,
1o3 o22 20. 8hn V.uVuKn Mtppp
8ln -n Sw.
(32)
Proof. We analyze the convergence of a in the same way by decomposing into estimation error and random error, which is
10 - s +21+102 021. -021.
(33)
Ejer his n 1
Au and B, Ejer hij
Estimation bias. By denoting A, a is given by
n .w. The estimated bias of
Ejsi Rug
2
EEni hig 1/: )
1.2 62
Σ
i/w -
Σ AA
BB? s Σ 1A + Bil- -Bil
Ejes Rasj
Ejes hij
Ejes Rii
tnw Ejer Mig Tnw
Σ
i
i7w
n
n
(34)
Ejes (Pee -his)
Ejes Theg
hisl + 1i iual
Σ
-Pi + )
Ti
n
Ejer (Pee lois)
Σ
(ftw + The
2 leyyl
n-
1
Ejes (hij + his)
Exseos (fe + hal)
26
Σ
n
n
n 1)
21

---

where En [hez - hayl is derived in eq. (27). Since Exitok (hus + hal) = Exees Eler (hos + has) Eieo (h+ hn)) We can derive that
Ejax (heg + hiss)
Elee (ha had Exttd Eiet (Pesa + haa)
lo 0%6 s 2cn
n Σ
n(n-1)
m(n-1))
ren1 1 1)
(n 1) Ejes (hig + hug)
Exti Eler (hre + haa)
2cq Σ
n( 11
m(n-11
1
Ejzr (hej + Nsss)
1
Exei Eler (fes + hea))
(35)
$ 2cn
Σ
+2cq
Σ
n
n
n(n n(n-1)
(n - 1) -2
n(n n
-20
$ 220
7
+ 20
n(n
= 4C 16TV v VuKn" 2(++))
Random Error. We again use McDiarmid's incquality to obtain the bound for the random error of the asymptotic variance which (w(w) ) 10 -g where
o [را nw
(36)
and the estimate without the estiamate bias on finite sample set S, which is
Σ
Ej bij 2
02 Σ
(37)
n
We again consider replacing sy with s/ and keep the remaining samples the same with the counterpart
4C₂
notations ø', and i Given that [hayl & Cv. //dl s Cv, Ihst - N4y 2C, and h in eq. (29), we can derive that
Mil
proved
Eesi hig
1
Ejsi Mij
Σ
Tlu
-
New
n
n1
11
Ejui (hig + -Wbs))
Ejer |hee N6bsl
$ n
Σ
(i Tnv)
+ 1:7 VH(ul
n=
n-
1
Σjes (hey + :(is)
hhit - ngghl +li Riull
Σ
(Mw n
Σj*t (has + +Nks) 17 s#k
n
n
Σj+t l/ks - -hlesl n-1
(ii + nma)
17 -170- -thil)
(38)
71
n-1
(n (n- -1] (n-1))20,, +2C,) )
.22, 22,, 4C₂
$
+
1-1
n
1
(n - 1) -2c, + 22Cr 22G.) (1-11) 20c n2
4C
71
n-1 1
71
1
4C, (2C, + 4C,, 1 + 20, + 4C,
8Cy
n
n
Simply applying McDiamid's to 02. we obtain that with probability at least
In T 2
_ 3 40,
(39)
Now we consider the bound
[
By the definition, we can rewrite o and B[o with
1
Σ
E E[hathin:]
Σ [[hiyhea] and Gille
3
n
ak
(40)
1
2
Σ E[h12/as)
3
n
alk
22

---

where the number subscripts in o corresponding to i, J. k, and I are mutually distinct and E[h12h34] C2 E[h,yhaa] Cy
For the first term, we obtain
1 [[hahi
[[[122 < <11- n³
(n)s CC + c
=- (2--) 20
3 2
Σ
(41)
n2ah dk
n ak
n n²
The second term can be handled similarly:
n² (innn(n11)m 1)(n (n
11
Σ
B[hghsll nd ajUk
Σ
20, = (-
+
2C,
n
nd
n²
n
(42)
Therefore, since 13/n² Gn for a 2 1, we have
9
13 n
6
18C
[ a 20
(43)
72
n23
n
Combining eq. (39) and eq. (43), we can give the random error bound under the residuals can be well estimated, which is
2 In 12
2
18C2 n
J wل S 1
|B[ E[
4C,
(44)
8
And finally, we combine eq. (44) and eq. (35) to get the bound of estimate asymptotic variance which is
lot o31 16TU2 (6TrZ""VVKn
VuKn
d-1 40,,
2
In
2
18C
71
(45)
81n u2 u 2u,u0
vkn 20
81n 8 n 2 + 9C
Recall that is small positive constant, since o 2 c² on Qe, according to eq. (45), when the sample size ng holds:
8-1 x(tt))
20L
81n uu
u ukn
8 Sln no à + +C
(46)
we have ow 2 S with at least probalibity 1 8/2.
D.3 CME convergence.
The analysis of the learning rate in vector-valued regression depends on standard assumptions such (EVD) and (SRC), which impose constraints the input space, interpolation operators, and the smoothness of the target regression. These assumptions help to ensure that the model's convergence behavior is well-defined and that the learning rate reflects the complexity of the regression task, influenced by factors such as the smoothness of the target function and the properties of the interpolation operators.
In SRC, the eigenvalues associated with functions in [HS] decay at rate that is influenced by the parameter B. Specifically, when > 1, [HS] embedded within HS, and the eigenvalues decay faster than those in HS, reflecting increased smoothness of the functions in [HS] Conversely, when 0 < 1, [HS] includes HS as subset, and the eigenvalues decay more slowly, indicating larger function space compared to HS. Here, we follow Pogodin et al. [2024] and focus on well-specified cases with 3 21. For the misspecified case where 3 (0, 1), the corresponding convergence rates from [Li et al., 2022, Theorem 2] can be directly applied and will not be discussed in the paper. Theorem 7. Li al. [2022] Under the Assumption EVD, SRC and Boundedness, for the well- specified cases where ? = 1, a 1, 3 (1,2), there is constant K > independent of n 2 and T 2 then
lAxzz Pxiz 12 Kn S-2,
(47)
is satisfied sufficiently large with P prrobbbball not less than 1 -T
23

---

E
Implementation and Baseline Details
We present the implementation details of both our proposed method and the synthetic dataset for conditional independence test and the causal discovery tasks.
E.1 Model hyperparameter settings
Our method's parameters mainly exist in the kernel ridge regression, the process of learning the parameters in @3 and the final testing procedure. (1) For the kernel ridge regression, there are three trainable parameters, the amplitude A, the bandwidth involved in K Z. denoted as o and the regularization parameter E. To ensure stability during the training process, we have constrained their value ranges, and the amplitude A is limited to the range of [10-3 10 The bandwidth o is vector whose dimensions are the same as those of the conditioning variable Z, with values constrained to [10-2, 10a). The regularization parameter is constrained to [10- 10 1.. We use marginal likelihood as the loss function and the L-BFGS-B B algorithm [Liu and Nocedal, 1989] to optimize and update these parameters. the null distribution. Following the default setting in [Zhang et al., 2011], we drop all d which are smaller than 10- for computational efficiency. We sampled a total of 5000 T. values according to Eq. 15, and obtained the p-value which is the rate that T, Ć2 KCI,"
ff.
(2) In the final test stage, we use the weighted sum of x" approximation to simulate
E.2 Synthetic Data Generation Settings
Implementation details of Synthetic CI dataset. In the CI testing task, we assume X and Y are the dependent variable of Z. To examine Type I errors, X and Y were generated according to the following nonlinear additive function model:
X ((W
(48)
where W ~ ~N Taz) and dz represents the dimension of Z. f was randomly chosen from the linear, sin, cos, x2, 2d and exp(z) with the same probability of being selected. When f is neither sin nor cos, we multiply W Z by an additional 1/vdz to balance the scale of the function and noise. For linear case, the data generation process follows X/Y- = Z/Vdz E. The noise term E' was randomly generated from either a normal distribution (O, 1) or uniform distribution 1-), with equal probability. To test Type II error, we add the same latent variable T to both X and Y with T (0, 1). Then the dependent variable, e.g. X, is generated as follows:
X= J(W' Z) E + aT,
(49)
Y follows the same generating process with the same variable T.
Implementation details of graph dataset for causal discovery. In the synthetic graph data for causal discovery task, generate cases with varying graph densities. The graph density is measured by the ratio of the number of edges to the maximum possible number of edges in the graph; a smaller graph density indicates fewer edges in the graph, while larger density indicates denser graph. For each graph density, we generate 10 cases where the variables and relationships are randomly generated. For each cases involves 10 variables with sample sizes of 500, which are evenly divided into training data and testing data. For each variable X, in the graph, the data was generated according to
X = [(WTTA)) + E.,
(50)
where PA, represents the parent nodes of X; in the graph and the weight matrix W; ~ ~N, fa is equally likely be sampled from linear, sin, cos, exp and x². Each function class in fr all has the same probability of being selected, and within the equal probability of each parameters setting. If one the variables has no parent nodes in the graph, follows standard normal distribution. E, represents the noise variable, randomly following either Gaussian distribution (0, 1) or uniform distribution U(-1, with equal probability. For each graph density, we generated 20 realizations. We set the significance level of a 0.05. All the data is similarly divided into training and testing sets with the same number of samples. We also use the weighted sum of x² approximation to simulate the null distribution for testing on the testing data.
24

---

E.3 Configuration details for runtime benchmarking.
In Section 5.1.3, we use the default settings as described S: each kernel has 10 candidate parameter values, resulting in total of 10x 10 parameter combinations. Consequently, Power involves 20 CME, computations, whereas Median only requires 2. We leverage the joblib package, specifically Parallel and delayed, to parallelize the learning process for the 20 CMEs in Power and the 2 CMFs in Median. For each sample size, we randomly generate 50 cases. All experiments were conducted on an Intel 14700K CPU platform with 32GB of RAM, without GPU acceleration.
E.4 Conditional independence testing baselines
In this section, we provide brief overview of the baseline methods used in the main text, along with their parameter settings.
CIRCE (Conditional Independence Regression CovariancE, [Pogodin et al., 2022]) is a simplified version of KCI, which only considers the correlation between o, (Y) and the regression residuals of Z to 622 (x=(X, Z). i.e. (x) Z) = (x Z)- E[ X, Z) 2] with X = (X, Z). As explained in Theorem 2, any function g(X, 2) E T,2 can capture the general relationship between X and Z. Utilizing the reproducing property. the residual feature map @a) (X, effectively eliminates the influence of Z on X. Intuitively, this residual daI= (X, Z) thus represents the component of X that cannot be explained by Z. Thus, if daj= (X, Z) is independent of Y, then we can conclude that X and Y are conditionally independent given Z. Formally, CIRCE has the following form:
Terre o[ (Z) @ (Y) @ (dx(X) pxiz (xx]((2))]
(51)
Conresoondingly, CIRCE also has MMD-liK like biased estimator:
1
FeIRCE n (Ky Rx(z)).
(52)
and can similarly use weighted (infinite) sum of x² variables or Gamma approximation to estimate the null distribution for conducting CI testing.
In CIRCE, we follow the original settings of CIRCE: we use the median heuristic to initialize the parameters of Φ2. By and dh.. We also use Gaussian process to estimate the conditional mean embedding Px|z, with parameters set identical to those used in our Power method.
GCM (Generalised Covariance Measure, [Shah and Peters, 2020J) considers the relation in L space. For one sample pair (Ir,, Mi; 2;), it considers the product between residuals from the regression:
R₂ [x; f(x)]] [t+- }[=)),
where f is the estimates of the conditional mean f(2) Ez[ ZJ. and ğ is defined as the same. Then it defines the statistic with n observations:
VПΣズ1 R₁
(R,)2 ( Σこ R2) R²)))
And it p-value is computed as p 2(1 ((TT)) for the standard normal CDF 2. We use the default regression model and parameter settings from GCM 3, The conditional mean estimated using cross-validated linear Lasso with 5 folds. the significance level is set as 0.05 which is consistent with other approaches.
RBPT2 (The Rao- nho-Blackwellized Predictor Test, [Polo et al., 2023]) involve regression chain: it first needs to estimate gY, Z)= [X Y. 2.2]. Then with the trained gY, Z). estimates h(Z) [g(Y, 2)| | 2]. The statistic is defined to compare the difference between their predicted results and the residuals of the real value of X, which is
vn TE Tj
T, = (T)))))) ((g(v) 2.), S
E 1 Ed E where I is MSE loss ( (g - 2 and its p-value The p-value is then computed as p 1 (S). We follow its default model and parameter setting".
Σr T:)²)
25

---

F
More Experimental results and discussion
F.1
Real data.
F1111
Car insurance data.
Following the setup of [Polo et al., 2023], we test our methods on the car insurance dataset for conditional independence testing. The car insurance data' encompasses four US states (California, Illinois, Missouri and Texas) and includes information from numerous insurance providers compiled at the ZIP code granularity. The data offers a risk metric and the insurance price levied on hypothetical customer with consistent attributes from every ZIP code. ZIP codes are categorized as either minority or non-minority, contingent on the percentage of non- white residents. The variables in consideration are Z, denoting the driving risk; X, an indicator for minority ZIP codes; and the insurance price Y. pertinent question revolves around the validity of the null hypothesis Hg : X 1l Y Z, essentially questioning if demographic biases influence pricing.
Since this is real dataset, the full distribution and the true CI relationship between X and Y given Z are unknown. Therefore, following [Polo et al., 2023], we discretize the conditioning variable Z into 20 bins and shuffle the Y values corresponding to each discrete Z value. If test maintains Type-I eπror control, we expect it to reject Ho for at most a 0.05 of the companies in each state. In the second part, we use the unshuffled data for CI testing and focus on assessing the power of our methods. Following the default setting in Polo et al. [2023], the dataset is split 70/30% for training and testing. We conducted a total of 5 experiments, each time randomly selecting 10 seeds, and reported the average Type-I error rate and the average p-value. This experiment is to assess whether Ci methods can effectively control Type I error on the shuffled dataset, while determining on the unshuffled dataset whether the state exists where demographic biases influence pricing.
Figure 3a illustrates that both the Median and Power methods are generally effective in controlling Type error, with Power performing slightly better than Median. Specifically, the Type I error for the Median method in Missouri exceeds a 0.05, whereas Power maintains strict control 0.05. Figure 3b presents the test results on the original unshuffled data. All methods show relatively low p-values, leading to the conclusion that all states likely exhibit varying degrees of discrimination against minorities in ZIP codes. The severity, in descending order, is Illinois, Texas, Missouri, and California. This result is consistent with the findings from [Angwin et al., 2022], indicating that our method is capable of correctly identifying CI relationships in the real world.
015-
Calfema
Tinola
Massuri
Texasa
0.25
Do
Boass
Mosiall
Thals
Power
0.29
Puwer
0.10
0.23
0.05
0.25
0.00
(a) Performance on shuffled data.
(b) Performance on unshuffled data.
Figure 3: Performance comparison on car insurance dataset.
F.1.2 Causal Discovery Benchmarks.
In Section 5.2, we apply our method to two widely-used real-world causal discovery benchmarks. SACHs [Sachs et al., 2005] and CHILD [Spiegelhalter et al., 1993] datasets. SACHs dataset contains single-cell measurements of protein and phospholipid components in human immune system signaling pathways, originally collected to study causal protein interactions under different experimental conditions. Its network comprises 11 variables and 17 edges. CHILD network consists of 20 variables with 25 edges, and its graph is a medium-sized causal graph that models congenital heart discase in newborns. The ground-truth graph consists of 20 nodes and 25 edges. Some example variables in the graph include Birth Asphyxia, Lung Flow, and Chest X-ray.
'Dta description link
26

---

Following the default setting, the variables were extracted and preprocessed. In both benchmarks, the variables are discrete and take values ranging from 6. We evaluated the performance under different sample sizes. For each sample size, data were randomly sampled and the experiments were repeated 10 times. F1 score is weighted average of precision and recall, calculated as
2- recall precision
(53)
recall + precision
Table 2 reports the Fl score results for sample size N 500. Additional results for various sample sizes are presented in Table and 4. Across all sample sizes, Power with selected kernels consistently outperforms Median, demonstrating the effectiveness and applicability of our method in real-world relational networks.
Table 3: Fl score on SACHs with varying sample sizes N.
Fl Score
N = 200
400
600
800
1000
Median
0.416 +: 0.063
0.550
0.047
0.593
0.053
0.648 0.032
0.710 0.035
Power
0.445 + 0.062
0.590 0.058
0.652 0.060
0.732 = 0.037
0.794 0.027
Table 4: Fl score on CHILD across N,
F1 Score
N = 200
400
600
800
1000
Median
0.638 + 0.056
0.723 0.063
0.806 0.045
0.832 = 0.021
0.861 0.022
Power
0.673 0.069
0.779 0.038
0.835 0.030
0.848 = 0.022
0.018 0.018
F.2
More experiment result synthetic data
In this section, we present experiments with additional baseline methods and on data with non-additive relationships to better assess the effectiveness of the KCI method under general data relationships and to evaluate the improvements brought by our approach over the median heuristic-based KCI (i.e. Median).
Baselines, We additionally include three conditional independence testing methods as baselines, namely KNN [Li al., 2023], CCIT [Sen et al., 2017] and AKE [Scetbon al., 2022].
KNN [Li al., 2023] proposes a permutation--ased conditional independence test that leverages local K-nearest-neighhor sampling to approximate the conditional distribution and construct the null distribution for statistical inference. We used their default parameter settings, adopt XGBoost as the classifier, and set the number of repetitions B 200 and the neighbor order k 7.
CCIT [Sen et al., 2017] proposes model-powered, permutation-based conditional in- dependence test, which uses neural networks learn a representation of the conditional distribution and trains a classifier to distinguish between samples from the joint and null (permuted) distributions. We followed the default hyperparameter settings: we use 30 bootstrap iterations, and tuned the XGBoost classifier over the suggested grid of tree depths {6, 10, 13), number of boosting rounds {100, 200, 300), and column subsampling ratio fixed at 0.8.
AKE [Scetbon al., 2022] AKE is an asymptotic conditional independence test that estimates kernel-based covariance operators and derives the null distribution in closed form using operator- theoretic tools and analytic kernels. While shares similarities with KCIT in relying on kernel embeddings and asymptotic theory, it differs by explicitly exploiting the structure of analytie kernels to achieve improved computational efficiency and theoretical interpretability. We followed the default settings recommended in the original AKE implementation, using Gaussian processes as regressors. All kernel functions involved are Gaussian kernels, with bandwidth parameters selected via the median heuristic.
27

---

Nonlinear additive data. We first conduct experiments on the original synthetic data with nonlinear additive relationships (Eq. 48), generated in the same way as described in Appendix E.2. All methods are repeated 500 times for each setting.
The experimental results presented in Table 5. The last row of the table reports the testing time required by each method for single case: we evaluate on samples with dz 5, and compute the average testing time over 100 repetitions for each method and error type. As shown, both KNN and AKE effectively control the Type error at the given significance level, whereas CCIT fails to do so under this setting. In terms of Type II error, AKE outperforms KNN. Overall, KCI (i.e., Median) and its kernel-selected version, Power, achieve the best performance.
Table 5: Type and Type II Errors across different dz settings.
Method
dz
3
7
Testing time (s)
AKE
0.06
0.04
0.04
0.06
0.04
3.463 0.030
KNN
0.06
0.04
0.04
0.04
0.05
6.261 0.071
Type Error
CCIT
0.41
0.31
0.31
0.29
0.21
5.106 0.133
Median
0.04
0.03
0.05
0.04
0.03
1.270 0.061
Power
0.05
0.04
0.05
0.03
0.02
2.202 = 0.286
AKE
0.15
0.31
0.44
0.57
0.68
3.164 0.042
KNN
0.90
0.82
0.83
0.88
0.89
5.923 0.101
Type II Error
CCIT
0.32
0.25
0.48
0.73
0.67
5.436 0.221
Median
0.19
0.32
0.41
0.46
0.57
1.361 0.062
Power
0.13
0.25
0.31
0.34
0.46
2.437 0.399
Non-additive data. We further conduct experiments on synthetic dataset generated under non-additive functional relationship, defined as follows:
X= fW' Z Z)E).
(54)
where the weight matrix W, function S, and noise term F. follow the same type and distribution as those in Eq. 48. All parameter settings remain the same as before, and each setting is evaluated over 500 repeated trials.
The results are shown in Table 6. The methods GCM, RBPT2, and CIRCE have been introduced in Appendix E.4, and their parameter settings remain unchanged. From the results, CCIT fails to effectively control the Type I error under this setting, while RBPT2 slightly exceeds the significance level. The other methods maintain Type I eиror rates close the nominal level 0.05. In terms of test power, the best performance is again achieved by the KCI-based methods, Median and Power, with Power further reducing the Type error compared to Median.
E.3 High--dimensional data
We evaluate the performance of our method and the baseline methods when the conditioning set Z has high dimensionality assess their statistical limits and identify potential performance bottlenecks under challenging settings. It should be noted that the high-dimensional setting presents a challenging scenario for CI tasks, it introduces estimation bias that is difficult to mitigate, making it hard for models to learn accurate predictors or regressors [Shah and Peters, 2020]. We include all the baselines introduced carlier for comparison, including GCM, RBPT2, and CIRCE (introduced in Appendix E.4), as well as the additional methods KNN, CCIT, and AKE, described in Appendix F.2.
Setting. We conduct experiments the nonlinear additive synthetic data, according to Eq. 48, with parameter distributions remaining the same as in the default setting. The key difference is that we now the performance is evaluated under nigher-dimensions conditioning variables, with d2 = 10, 30, and 50.
Result. In Table 7, we provide experimental results nonlinear additive synthetic data under high-dimensional conditioning setting. When the dimensionality increases, all comparison methods either fail to effectively control the Type error (c.g., RBPT2, CIRCE, CCIT) exhibit little to no
28

---

Table Type and Type Errors across different dz settings with more baseline methods.
Method
dx
3
Testing time (s)
AKB
0.06
0.05
0.03
0.03
0.07
3.050 0.586
KNN
0.01
0.04
0.03
0.07
0.00
6.612 = 0.026
CCIT
0.39
0.34
0.38
0.25
0.17
5.314 0.010
GCM
0.06
0.05
0.05
0.07
0.06
1.213 3.126
Type Error
RBPT2
0.02
0.09
0.10
0.15
0.10
0.405 = 0.031
CIRCE
0.05
0.02
0.03
0.00
0.02
1.141 = 0.301
Median
0.04
0.05
0.05
0.06
0.06
1.436 = 0.359
Power
0.03
0.04
0.04
0.04
0.05
2.443 = 0.496
AKE
0.19
0.60
0.77
0.70
0.71
2.900 0.551
KNN
0.82
0.76
0.84
0.81
0.82
6.603 = 0.037
CCTT
0.15
0.36
0.37
0.46
0.57
5.252 = 0.006
GCM
0.05
0.21
0.48
0.45
0.31
1.371 = 3.032
Type II Error
RBPT2
0.56
0.64
0.72
0.80
0.81
0.265 = 0.045
CIRCE
0.21
0.52
0.74
0.66
0.68
1.005 = 0.320
Median
0.13
0.38
0.62
0.59
0.54
1.206 = 0.231
Power
0.07
0.32
0.53
0.50
0.37
2.461 = 0.394
power against any alternative (e.g., GCM, AKE, KNN, KCT,, which is consistent with the known hardness of CI testing [Shah and Peters, 2020, Polo et al., 2023]. Our proposed Power demonstrates effectiveness, showing slightly higher test power compared to Median when dz 10 and 30, though both methods nearly fail when dz increases to 50. The above results highlight the intrinsic challenges and distinctive nature of testing. Unlike unconditional independence testing and other classical hypothesis testing tasks-for which permutation tests provide correct calibration under the null- CI testing fundamentally more difficult. Due to the estimation errors involved conditioning on potentially high- nigh-dimensional variables, existing CI test can be guaranteed to perform valid hypothesis testing across arbitrary finite-sample scenarios while simultaneously maintaining correct control of the significance level and achieving valid test power.
Table
Performance on high-dimensional data.
Method
dz
GCM
RBPT2
CIRCE
AKE
KNN
CCIT
Median
Power
10
0.08
0.25
0.82
0.02
0.03
0.16
0.06
0.05
Type I Error
30
0.03
0.28
1.00
0.06
0,05
0.15
0.03
0,02
50
0.01
0.25
0.99
0.03
0.05
0.09
0.01
0.01
10
0.50
0.68
0.02
0.62
0.90
0.58
0.56
0.47
Type II Error
30
0.72
0.75
0.00
0.86
0.91
0.68
0.82
0.79
50
0.83
0.73
0.00
0.98
0.96
0.74
0.92
0.91
E4
Comparison with contginuous optimization-basee selection
In this section, we further discuss why, unlike in unconditional independence testing, we do adopt continuous optimization or deep kernels for kernel selection for CI testing. Existing methods for other testing tasks able perform kernel parameter selection via continuous optimization, such as in the two-sample test [Gretton et al., 2012b, Kübler et al., 2022] or in unconditional independence testing [Albert al., 2022, Ren et al., 2024a], and some works have further explored the use neural networks to parameterize deep kernels [Liu et al., 2020, Xu et al., 2024]. However, the CI testing task differs substantially from these settings, as it not only involves sampling variability but also suffers from model estimation errors. The latter leads to inaccurate gradients of the power-based criterion with respect the kernel parameters, which undermines the effectiveness of gradient-bant baseed optimization. This makes continuous optimization unstable or unable reliably select effective
29

---

kernel parameters, thereby failing to learn optimal kernels or oracle choices for CI testing tasks. To demonstrate this point, we conduct the following experiment using a two-stage optimization framework that performs gradient-basee continuous kernel parameter tuning for KCI.
Setting. We refer this two-stage baade method Grad. In the first stage, the Gaussian Process model shares the same configuration as in the previous methods. In the second stage, based on the regression models learned in the first stage, we compute the gradients of the power-based criterion with respect to the parameters of ky and ky, and perform parameter updates accordingly. For each iteration of the first-stage regression, one gradient update performed in the second stage. The ratio- based criterion (i.e., Eq. 9) is inherently more challenging to optimize due to its nonlinearity and potential instability. Following the recommendation of [Wang al., 2023], we reformulate it as regularized surrogate objective, which is given by:
= Ce KCIN,N \
(55)
where À is the regularization hyper-parameter and X 1.
We conduct experiments on synthetic datasets, where the data is generated following Eq. 48. We set the sample size to N = 500, with the data equally split into training and testing sets. In the second stage, we update the kernel parameters of kx and ky using the Adam optimizer with a learning rate of 0.01. We choose total iteration counts of epochs 10 and epochs = 100 to reflect the behavior of the optimization process at the early stage and after prolonged training, respectively. These two settings are referred to as Grad- 10 and Grad-100 and are compared against Median and Power selection strategies. The results are summarized in Table 8, where the last row reports the average test time when dy = 5.
As shown in the results, even with only a small number of updates (Grad-10), the performance in terms of Type II error already degrades compared to the Median baseline. As the optimization proceeds further, Grad- 100 still fails to select kernel parameters that lead to improved test power. This suggests that gradient- same way as they are used in other settings. We hypothesize that the estimation error inherent to CI testing leads to inaccurate gradients, and the resulting optimization difficulties further cause the procedure to get trapped in poor local minima, preventing it from identifying more effective kernel parameters than those selected by simple heuristics strategy. Moreover, the substantial time cost further renders continuous optimization methods impractical for real-world CI testing applications.
Result.
methods cannot be directly applied to KCIT for CI testing in the
Table 8: Comparison of grid search gradient- based approach for different dz.
Method
dz
3
7
Time (s)
Power
0.04
0.03
0.03
0.03
0.06
2.267 a 0.276
Median
0.03
0.04
0.04
0.04
0.05
1.301 # 0.186
Type I Error
Grad-10 10
0.04
0.06
0.05
0.04
0.06
11.86 + 4.136
Grad- 100
0.05
0.04
0.04
0.04
0.04
119.5 = 828.6
Power
0.14
0.16
0.24
0.32
0.48
2.286 + 0.177
Median
0.22
0.25
0.32
0.52
0.58
1.244 + 0.174
Type II Error
Grad-10
0.22
0.28
0.34
0.49
0.68
13.44 + 13.83
Grad-100
0.27
0.31
0.46
0.61
0.73
126.5 + 1019
F.5 Toy experiments.
In this section, we use a top example to demonstrate how the concatenated 6(z, 2) affects the regression learning rate. In vector-valued regression, the learning rate is influenced by the smoothness of the objective function, which is reflected through the parameter / (the convergence rate is formally similar to Theorem 7, but with different assumptions). A larger ,3 indicates a smoother objective function and also associated with faster decay rate of the eigenvalues of the objective function.
N(00, Is), where 215 represents 5-dimensional vector of ones. We randomly sampled 1000 sets of samples, obtaining the
Setting. We conducted an experiment assuming that the variable
30

---

corresponding kernel matrices K₂ and xxz. We performed eigenvalue decomposition on K₂ and K x, and the corresponding eigenvalues X were computed.
Result. The decay rates of the eigenvalues are shown in Figure 4. The decay rate of the eigenvalues corresponding d(x, 2) is significantly slower than that of ((x), which corresponds to slower learning rate and larger estimation bias under the same sample size.
200
150
50
5
10
30
35
index:
Figure 4: The eigenvalue decay rates for decomposed vs. non-decomposed regression.
31

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Please refer the last paragraph of Introduction (1).
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in 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 be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to 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 of the work performed by the authors?
Answer: [Yes]
Justification: In the Conclusion and Future Work section, we have outlined the limitations of our work and proposed directions for future research.
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 are encouraged to create separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect 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 few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not 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 used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't 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 proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
32

---

Justification: In the Theory section and Appendix C.3, we present the assumptions necessary for deriving the convergence rate of our method, along with a complete and rigorous proof. 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 if they appear in the supplemental material, the authors are encouraged to provide short proof sketch 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 ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provide detailed parameter settings for the experiments in the Appendix and include the code in the supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all 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) the contribution is a 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 be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
33

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
We provide the implementation code in the supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips) cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.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: //niss httppsccccpbccccccceececccccclcc /ttee/uuuueeeeoeSuubiiaeeee
/Cooeeeooiissseeeeeee wwsssonollicyy for more details.
The authors should provide instructions on data access and preparation, including how to 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 the paper) is recommended, but including URLs to data and code is 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 understand the results?
Question:
Answer: [Yes]
Justification: We provide details such as dataset splits and parameter settings in the Imple- mentation Details subsection of the Experiments section, well as in Appendix E.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, 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:
Our experimental results include the corresponding error bars.
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, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
34

---

The method for calculating the error bars should be explained (closed form formula, call 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.
is 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 of 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 range (e.g. negative enror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or 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 execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: We report the computational time comparison and the hardware specifications used in table I and further detail them in Appendix E.4.
Guidelines:
The answer NA means that the paper does 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 in the paper (e.g., preliminary or failed experiments that didn't I make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: /nnurrisss... cc cccppbblcc/eeeeeeeeeeeee ctt.:i/eeeeccscueeeeeeeeeeeeeee ines?
Answer: [Yes]
Justification: anonymity.
We affirm that the submission and supplementary materials maintain
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
Answer: [No]
Justification:
This paper aims to advance the fields of conditional independence testing and causal discovery. While our work may have various societal implications, we do not find any that require specific emphasis.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
35

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or 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 not 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 improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If 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 system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [No]
Justification: This work does not involve sensitive data, pretrained models, or other compo- nents that pose high risk of misuse.
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 to 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.
recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
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?
Question:
Answer: [Yes]
Justification: All datasets used in this paper are publicly available, have been properly cited, and are covered under appropriate licenses (e.g.. CC-BY 4.0).
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 or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
36

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
If assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswithcae thcode. com/ conddataset has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if 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
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [No]
Justification:
This submission does not introduce any new assets.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/model as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [No]
Justification:
This work does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing 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 NeurIPS 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.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: 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 equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [No]
Justification: This study does not involve any human participants, and therefore no potential participant risks were incurred, no disclosures were necessary, and IRB (or equivalent) approval was not required.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
37

---

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 we expect authors to adhere to 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
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
The core content of this paper does not rely on the use of LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: pettpa:/nnetee wttp///een...peeeeeee htt.:ppp...//ooeeeee////////222 for what should or should not be described.
38


Reviews:
[{"review_id": "ZcDBTAsyih", "reviewer": "Reviewer_USgq", "summary": "This paper addresses the problem of kernel selection in conditional independence testing. It introduces a test power–based criterion along with its corresponding finite-sample estimate. Based on this criterion, a grid search is performed to identify the optimal bandwidth. Experiments on both synthetic and real-world datasets demonstrate that the proposed kernel selection method improves test power compared to the original approach.", "questions": "1.what is \"K\" in line 216?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths：\n1. The paper provides solid theoretical support for the proposed methodology, and I did not identify any major issues regarding its correctness.\n2. The approach is straightforward and enhances efficiency by parallelizing the grid search process, making it practical for real-world applications.\n\nWeakness:\n1. While the focus on CI testing is appreciated, the underlying idea of optimizing bandwidth through power maximization has been previously considered in related contexts [1], which somewhat limits the novelty of the contribution.\n\n[1] Feng Liu, Wenkai Xu, Jie Lu, Guangquan Zhang, Arthur Gretton, and Danica J Sutherland. Learning deep kernels for non-parametric two-sample tests. In International conference on machine learning, pages 6316–6326. PMLR, 2020.\n\n2. In the “Overall Procedure”, ω_z  is the median heuristic value (no selection); Fixing ω_z without tuning may limit the flexibility of the kernel ridge regression step and reduce the adaptability of the method in different settings.\n\n3. The experiments are conducted solely using Gaussian kernels. While the proposed method works well under this setting, its applicability to more complex or adaptive kernel designs (e.g., deep kernels) appears limited.", "was_revised": true, "final_justification": "The authors' rebuttal has addressed my concerns, and I maintain my positive score.", "rebuttal": "Dear Reviewer USgq:\n\nWe sincerely thank you for your time and effort in reviewing our submission. Below, we provide our responses to your concerns and questions. \n\n>**W1.**  While the focus on CI testing is appreciated, the underlying idea of optimizing bandwidth through power maximization has been previously considered in related contexts [1], which somewhat limits the novelty of the contribution.\n\n**A.**    Thank you for your comment and for recognizing our focus on kernel selection in CI testing.\nWe agree that selecting parameters by maximizing estimated power has been explored in other testing settings, such as two-sample testing and unconditional independence testing. \nHowever, to the best of our knowledge, this idea has not been effectively extended to CI testing. \nThe main challenge lies in the uniqueness of CI testing, which typically requires residual estimation via regression models. \nThis additional model estimation step introduces non-negligible model estimation bias, a challenge not present in other testing tasks.\nTo address this issue, we propose several key modifications:\n\n(1) Decomposed variant of KCI: We adopt a decomposed form of KCI statistic. \nAs demonstrated in Appendix F.5, we find that the original KCI formulation significantly reduces the smoothness of the target function, which in turn slows down the convergence rate of the CME regression.\nThe resulting estimation bias compromises the reliability of the test statistic, leading to less effective power-based parameter selection, as demonstrated by the weaker performance of Org and OrgP in Figure 2(a) and 2(b).\nIn contrast, the decomposed KCI variant reduces estimation bias and yields more stable test performance.\n\n(2) Grid search instead of gradient-based optimization:  Instead of using gradient-based parameter tuning methods, including those based on neural networks, we adopt a \"classical\" grid search strategy.\nWe found that gradient-based selection methods are often ineffective, likely due to estimation bias introduced during the regression step. This bias distorts the true update direction and prevents reliable identification of effective kernel choices, as illustrated in Appendix F.4.\nTherefore, we adopt a parallelized grid search strategy that is simple, robust, and effective in practice, which serves as an approach well-suited to the unique challenges posed by CI testing.\n\nIn summary, while our method is motivated by the principle of test power maximization, it is specifically tailored to the CI testing problem.\nFurthermore, to the best of our knowledge, we are the first to provide convergence rate results for KCI. \nThis analysis explicitly accounts for model estimation bias, whereas prior work typically considers only finite-sample randomness.\n\n>**W2.** In the “Overall Procedure”, $\\omega_z$ is the median heuristic value (no selection); Fixing $\\omega_z$ without tuning may limit the flexibility of the kernel ridge regression step and reduce the adaptability of the method in different settings.\n\n**A.**  We appreciate the reviewer’s comment. \nThere appears to be a misunderstanding. The parameter $\\omega_z$ mentioned here refers to the kernel parameters associated with $\\phi(Z)$ in the decomposed statistic $\\phi(X, Z) = \\phi(X) \\otimes \\phi(Z)$. \nThat is, it corresponds to the kernel function $k_{\\mathcal{Z}}(\\cdot, \\cdot)$ defined in Eq.5 of the submission, which is not the kernel parameters involved in kernel ridge regression.\nThe bandwidth in KRR along with other parameters such the amplitude and the invertible regularization term $\\epsilon$ are all learnable.\nWe agree that this distinction was not clearly stated here and will clarify it in the revision.\n\n>**W3.** The experiments are conducted solely using Gaussian kernels. While the proposed method works well under this setting, its applicability to more complex or adaptive kernel designs (e.g., deep kernels) appears limited.\n\n**A.** We thank the reviewer for the suggestion regarding kernel choices. In Section 5.1.2 (\"On the kernel types\"), we compare the use of Gaussian kernels, Laplace kernels, and their combinations to demonstrate that our method can be extended to different kernel families.\nAccording to the definition of the cross-covariance operator (Theorem 3 in [2]), both $k_{\\mathcal{X}}$ and $k_{\\mathcal{Y}}$ are required to be characteristic kernels. Among the most widely used and well-understood characteristic kernels are the Gaussian and Laplace kernels, which we have already evaluated in our experiments.\n\nWhile deep kernels are also characteristic, they typically involve a large number of learnable parameters and rely on gradient-based optimization.\nHowever, as discussed in our response to W1, we observed that gradient-based methods struggle to reliably optimize even simple kernel parameters, such as the bandwidth of a Gaussian kernel.\nThis suggests that extending our method to deep kernels, which require optimizing a high-dimensional parameter space, is currently not feasible due to instability and inaccuracy in gradient estimation.\nWe therefore chose to focus on nonparametric kernel families where parameter selection can be performed reliably via grid search. \nExtending to deep kernels is an interesting direction, but it poses substantial challenges that we leave for future work.\n\n>**Q1.** What is \"K\" in line 216?\n\n**A.** Thank you for your careful review. The constant here $K > 0$ depends on the constants in the assumptions as well as the smoothness parameter $\\beta$ of the target function, but it is independent of the sample size $n$ and the confidence level $\\delta$.  We apologize for not providing an explanation here, and we will add a clarification in the revised version.\n\nWe hope our response can clarify the confusion and addressed your concerns. We would greatly appreciate it if you could kindly reconsider your score. Should you have any additional questions or suggestions, We’d be happy to clarify them further. Thank you. \n\n**Reference**\n\n[1] Feng Liu, Wenkai Xu, Jie Lu, Guangquan Zhang, Arthur Gretton, and Danica J Sutherland. Learning deep kernels for non-parametric two-sample tests. ICML 2020.\n\n[2] Fukumizu K, Gretton A, Sun X, et al. Kernel measures of conditional dependence, NeurIPS 2007."}, {"review_id": "PEqM4aRM81", "reviewer": "Reviewer_D99S", "summary": "This paper proposes a simple yet effective kernel selection method for conditional independence testing (CIT). The method enhances the power of CIT by maximizing the ratio of the KCI statistic to its variance. The authors also provide rigorous theoretical guarantees, establishing the convergence rate of their estimator. Empirical results demonstrate that selecting kernel parameters using the proposed approach improves performance by approximately 5%–10% over original methods without kernel selection. Overall, this paper is technically solid and constitutes a valuable contribution to the kernel-based CIT family.", "questions": "1. Is it possible to extend your method to scenarios where both X and Y are high-dimensional, despite the well-known fact that kernel methods generally suffer from the curse of dimensionality? Plus, will high-dimensional X, Y obstacle to the proof of theory\n2. Given that the topic of this paper is CI **testing**, it would be very beneficial to extend Theorem 3 to bound type I and type II errors of the tests with the tuned kernel.\n3. I am not quite clear on how the weight list in line 233 is chosen. Could you provide further explanation or clarification?\n4. From Figure 1,3, it can be observed that compared to the ‘Median’ approach, the ‘Power’ method achieves not only a lower type II error (which is the main improvement highlighted in the paper) but also a lower type I error (or at least does not worsen it). This seems somewhat counter-intuitive. This question may be correlated to Q2. Could the authors provide futher explanations for this phenomenon?\n5. To better show the improvement of 'Power' beyond 'Median' and other tests, it is recommended to show the densities/histograms of p-values.\n6. When developing your Th 3, you used yourTh 7 to handle the estimation error of CME. While Liu et al. developed their Th 6 in [1]. The first term in their error bound exhibits a convergence rate of $n^{-1/3}$. Could you elaborate on what advantages your result offers compared to theirs, in terms of the first term in your (11)?\n\n[1] Liu, Learning Deep Kernels for Non-Parametric Two-Sample Tests, ICML2020.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths: \n1. The method is very simple and intuitive in practice, yet proves to be effective. And the authors provided corresponding theoretical analysis.\n2. Cleverly leverage parallelization to carry out the parameter selection, without substantially increasing the overall computational time.\n3. Theorem 3 appears to make a significant contribution to the development of the KCI family of methods.\n\nWeakness: \n1. My primary concern is that the proposed method can only be applied to improve algorithms within the KCI family, and the improvement may not be substantial.\n2. My second concern pertains to the runtime of the algorithm when both the sample size and the dimensionality of Z are high (e.g., dz=30-50, n=1000-2000). The authors have only provided runtime results for cases where dz<10. Given the computational complexity of kernel methods (O(n^3)), I believe this issue could significantly impact the applicability of the proposed method to large-scale datasets.", "was_revised": true, "final_justification": "Most of my concerned have been solved. And the type one error remains to be a challenging open question.", "rebuttal": "Dear Reviewer D99S:\n\nWe sincerely thank you for your time and effort in reviewing our submission. Below, we provide our responses to your concerns and questions. \n\n>**W1.** My primary concern is that the proposed method can only be applied to improve algorithms within the KCI family, and the improvement may not be substantial.\n\n**A.** KCI is a widely used and robust approach for conditional independence testing, as it makes minimal assumptions about the data distribution or underlying functional relationships. Its effectiveness has inspired both methodological advances [1] and real-world scientific applications [2]. In this work, we provide, to the best of our knowledge, the first systematic study of kernel selection for KCI in the context of CIT task. Our method explicitly addresses the model estimation bias inherent in CI testing, leading to improved test power while incurring only moderate additional running time.\n\n>**W2.** My second concern pertains to the runtime of the algorithm when both the sample size and the dimensionality of Z are high. I believe computational complexity could significantly impact the applicability of the proposed method to large-scale datasets.\n\n**A.** Performing CIT in high-dimensional settings remains a highly challenging task. \nAs shown in Table 7 in Appendix F.3, not only KCI-based methods, but none of the methods are able to simultaneously control Type I error and achieve sufficient test power under such conditions.\nThe primary difficulty lies in the increased complexity of regression in high-dimensional spaces, which affects all regression-based CIT methods similarly.  For permutation-based methods, such setting also causes severe data sparsity during shuffling, limiting their effectiveness.\n\nRegarding the runtime of KCI, a major bottleneck lies in parameter estimation for KRR.\nWe have explored faster alternatives such as leave-one-out cross-validation with grid search [3], but found that they often yield poor testing performance due to residual dependence on $Z$.\nTherefore, we adopt Gaussian process (GPR), which, while more computationally intensive, offers better estimation quality.\nRecent advances like GPyTorch [4] provide opportunities for GPR acceleration and can benefit both the Median and Power variants of our method. Exploring the acceleration of KCI is part of our future work.\n\n>**Q1.** Is it possible to extend your method to scenarios where both X/Y are high-dimensional? Plus, will high-dimensional X, Y obstacle to the proof of theory?\n\n**A.** Our method can naturally be extended to cases where both $X$ and $Y$ are multivariate. \nWhile most existing CIT literature focuses on the setting where $X$ and $Y$ are univariate and the conditioning set $Z$ is multivariate, this is primarily because multivariate $X$ and $Y$ are often treated as collections of multiple univariate regressions.\n\nIn KCI-based methods, with using CME as the regressors, increasing the dimensionality of $X$ or $Y$ will potentially increase the complexity of the target function, effectively reducing the smoothness parameter $\\beta$. \nThis leads to slower convergence rates, as illustrated in Figure 5 in Appendix F.5. \nNevertheless, the theoretical analysis still holds under the our framework. \nIn the following, we evaluate our method with multivariate $X/Y$, extending Eq. 12 by applying an all-one transformation to the original scalar inputs and adding isotropic Gaussian noise.\nWe fix the sample size $N = 500$ and $d_Z = 9$, repeat 500 times.\nEmpirically, we observe elevated Type I error in high-dimensional settings, which aligns with our analysis.\n\n|               | $d_X, d_Y$| **1**  | **3**  | **5**  | **7**  | **9**|\n|---------------|------------|--------|--------|--------|--------|--------|\n| **Type I**    | Median     | 0.060  | 0.048  | 0.042  | 0.082  | 0.076  |\n|               | Power      | 0.062  | 0.026  | 0.056  | 0.074  | 0.070  |\n| **Type II**   | Median     | 0.512  | 0.070  | 0.092  | 0.082  | 0.078  |\n|               | Power      | 0.446  | 0.066  | 0.056  | 0.064  | 0.074  |\n\n\n>**Q2.** Given that the topic of this paper is CI testing, it would be very beneficial to extend Theorem 3 to bound type I and type II errors of the tests with the tuned kernel. \n\n**A.** In fact, our Theorem 3 does not provide formal guarantees on Type I error control or test power, unlike methods such as GCM [5].\nThis limitation arises from fundamental differences in assumptions: GCM relies on a nonlinear additive model, a special case of the general CI setting.\nSuch assumption simplifies the null distribution of the test statistic, enabling analytical tractability and formal Type I error and test power guarantees.\nIn contrast, KCI targets general CI relationships without assuming a specific functional form, resulting in a more complex and less tractable null distribution.\nThis null distribution is typically approximated by a weighted $\\chi^2$ distribution, where the weights depend on the eigenvalues of the estimated residual covariance matrix.\nHowever, the effect of estimation bias on these eigenvalues is intricate and difficult to analyze theoretically. \nAs such, establishing precise control over Type I error and test power for KCI remains an open and challenging yet highly valuable problem. \n\n>**Q3.** I am not quite clear on how the weight list in line 233 is chosen. Could you provide further explanation or clarification?\n\n**A.** Our candidate list is primarily guided by empirical intuition, with the parameter space restricted to a broad yet reasonable range.\nWe found that kernel parameters that are too large or too small can severely degrade the performance of CME-based regression and even cause numerical instability, which ultimately reduced the test's power.\nTo mitigate this, we use the median heuristic as a reference and sample multiple values around it to form the candidate list.\nThat said, the list can be further refined if prior knowledge about the target dataset is available.\n\n>**Q4.** From Figure 1,3, ‘Power’ achieves not only a lower type II error but also a lower type I error (or at least does not worsen it). Could the authors provide further explanations for this phenomenon?\n\n**A.** Thank you for your insightful question. \nAs we mentioned in our response to Q2, we are currently unable to provide the rigorous theoretical explanation for this phenomenon.\nIntuitively, however, we believe that the choice of $\\phi(X)$ should take into account both the dimensionality and the complexity of its dependence on the conditioning set $Z$.\nThis aspect is not adequately captured by the Median-based choice. \nAnd its fixed kernel choice may become increasingly misaligned as $d_Z$ grows, leading to degraded performance.\nIn contrast, Power allows flexible kernel parameter selection, enabling better adaptation under both $H_0$ and $H_1$ and thus improving testing performance.\nWe conjecture that the remaining deviation from the significance level, particularly when $d_Z$ is large, results from residual bias in estimating the Type I error.\nWith the bias improving, we think Power would likely exhibit even greater test power than currently observed.\n\n>**Q5.** It is recommended to show the densities/histograms of p-values.\n\n**A.**  Thank you for your valuable feedback. We will include them in future version.\n\n>**Q6.** While Liu et al. developed their error bound in [6] with exhibiting a convergence rate of \n$n^{-1/3}$. Could you elaborate on what advantages your result offers compared to theirs, in terms of the first term in your (11)?\n\n**A.** The first term in Eq.11 arises from the estimation error of the CME, which is specific to the CIT setting. In contrast, the task in [6] is for two-sample test task and does not involve this term. \nWe respectfully assume that your question refers to the second term in our bound, which has a convergence rate of $O(n^{-1/2})$, and may appear faster than the rate reported in [6]. \nThis is because [6] establishes a uniform convergence result under the additional assumption that the kernel parameterizations are Lipschitz continuous, whereas our result provides only pointwise convergence for fixed kernel parameters.\nWe chose not to pursue uniform convergence, as it would require assuming that the learned CME residuals are Lipschitz with respect to the kernel parameters, an assumption that is rather strong and difficult to justify in practice.\nIn particular, CME estimation involves matrix inversion operations, which are highly non-smooth and may violate global Lipschitz continuity.\nMoreover, since our method uses grid search rather than gradient-based optimization, pointwise convergence is sufficient for comparing relative test power, which is the central focus of our work.\n\n>**Typos** Check Table 2, column CHILD.\n\n**A.** Thank you for the careful review. We indeed mistakenly swapped the Power and Median result on CHILD, and we will fix it in the revised version.\n\nWe hope our response can clarify the confusion and addressed your concerns. We would greatly appreciate it if you could kindly reconsider your score. Should you have any additional questions or suggestions, We’d be happy to clarify them further. Thank you. \n\n**Reference**\n\n[1] Strobl et al. Approximate kernel-based conditional independence tests for fast non-parametric causal discovery. Journal of Causal Inference, 2019.\n\n[2] Kameneva et al. Single-cell transcriptomics of human embryos identifies multiple sympathoblast lineages with potential implications for neuroblastoma origin. Nature Genetics, 2021\n\n[3] Pogodin et al. Efficient Conditionally Invariant Representation Learning, ICLR 2023\n\n[4] Gardner et al. GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Acceleration, NeurIPS 2018\n\n[5] Shah et al. The hardness of conditional independence testing and the generalised covariance measure. The Annals of Statistics, 2020\n\n[6] Feng Liu et al. Learning deep kernels for non-parametric two-sample tests. ICML 2020"}, {"review_id": "EYT0GIH1JV", "reviewer": "Reviewer_PrW6", "summary": "The paper presents a new parameter selection method for Kernel Conditional Independencet (KCI) testing. Specifically, the kernel selection criterion is defined as the ratio of the estimates of $C^2_{KCI}$ and $2\\sigma_1$, which both depend on the proposed estimator \\hat{C}^2_{KCIu}. The convergence rate is provided in Theorem 3 and several experiments are conducted to demonstrate the empirical performance.", "questions": "First, I have some minor suggestions on writing/typos: \n- Eq.12: I believe it should X/Y \\sim f( . ) + E?\n- Line 100 - 102: the sentence starts with g(.) but ends with \"mappings of (X, Z) and Y onto Z\". I believe, (X, Z) --> Y is about h(.) not g(.)?\n\nSecond, two questions: \n- Line 199, the Boundedness assumption: Could you explain how we can obtain \"Then h_{ij} and \\hat{h}_{ij} are bounded within [−ν_z ν^2,ν_z ν^2]?\n- Of course It's already a lot of experiments and a lot of work for a conference paper, but have you considered checking the empirical performance on other causal structures, i.e., chain or collider?", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Although I cannot understand all the math involved, I like the research question a lot. Such (hyper)-paremeter-choice research questions resolve important practical challenges and potentially have a high impact both for practitioners and for researchers who focus on more applied research, yet are often neglected. \n\nStrength: \n- The paper is quite well-written and easy to follow. \n- I presume the convergence rate is not bad, i.e., C_2 n^{-1/2} + C_1 n^{-(beta -1) / (2(\\beta + p))}, considering the range of \\beta and $p$. \n- The experiment results are strong: within those methods that can effectively control type-I error, the proposed method \"Power\" achieves the lowest type-II error in general. \n\nWeakness:\n- I would apprecaite a more thorough related work review about kernel (paremeter) selection in the main body. \n- It's a bit unclear to me if the U-statistic (eq.5) has been considered by other previous work. I feel the writing a bit unclear here.", "was_revised": true, "final_justification": "All my major concerns have been addressed, and I think it is a good contribution to the field. \n\nThe paper is well-written, the theoretical results are solid to me, and the experiment results are strong.", "rebuttal": "Dear Reviewer PrW6:\n\nWe sincerely thank you for your time, effort, and recognition in reviewing our submission. Below, we provide our responses to your concerns and questions. \n\n\n>**W1.** I would apprecaite a more thorough related work review about kernel (paremeter) selection in the main body.\n\n**A.** Thank you for the feedback. Our discussion of related work is currently placed in Appendix A. We will include a more detailed discussion of existing kernel selection strategies in the main text in the revised version.\n\n>**W2.** It's a bit unclear to me if the U-statistic (eq.5) has been considered by other previous work. I feel the writing a bit unclear here.\n\n**A.** Thank you for sharing your concerns. \nTo the best of our knowledge, the form of the U-statistic used here (Eq. 5) is first used in KCI literature. \nIt is simple and can be directly derived from the population expectation form of the test statistic.\nKCI itself is an HSIC-like statistic, where the key difference lies in the use of regression residuals instead of raw inputs.\nAs we noted in Footnote 1 (under line 165), the U-statistic form of HSIC is more complex due to the requirement of double-centering the kernel matrices. \nIn contrast, since KCI operates on residuals, which are already mean-zero by regression, which eliminates the need for explicit centering. \nThis leads to a simpler U-statistic form that is not only computationally more efficient, but also more amenable to theoretical analysis.\n\n>**Q1.** Line 199, the Boundedness assumption: Could you explain how we can obtain \"Then $h_{ij}$ and $\\hat{h}_{ij}$ are bounded within $\\[ -{\\nu}_z {\\nu}^2,{\\nu}_z {\\nu}^2 \\]$ ? \n\n**A.** This bound follows directly from the definition\n$\\hat{h}\\_{ij} = k_\\mathcal{Z}(z_i, z_j) \\hat{r}\\_{x|z}(s_i, s_j) \\hat{r}\\_{y|z}(s_i, s_j)$.\nUnder the boundedness assumption, we assume that the inner product between any two residuals—both the population value and its empirical estimate—is uniformly bounded by a constant $\\nu$. \nThis is a standard assumption in the theoretical analysis of kernel ridge regression, often referred to as a moment condition (MOM) [1]. \nIn our submission, we adopt a simplified form of it.\nIn addition, the kernel on $Z$, $k_z(z_i, z_j)$, is assumed to be bounded within $[-\\nu_z, \\nu_z]$, which is a mild condition satisfied by most commonly used kernels.\nGiven these assumptions and the definition of $\\hat{h}\\_{ij}$, and $h\\_{ij}$ corresponds to the expectation form where the CMEs are well estimated, we can directly establish the bound on $\\hat{h}\\_{ij}$ and $h\\_{ij}$.\n\n>**Q2.** Of course It's already a lot of experiments and a lot of work for a conference paper, but have you considered checking the empirical performance on other causal structures, i.e., chain or collider?\n\n**A.** Thank you for your question. Below we provide the experimental results for the chain and collider structures.\nIn these experiments, the functional relationships between variables follow the same sampling procedure for $f$ as defined in Eq. (12) of our submission. \nThe additive noise is also sampled using the same scheme, with a fixed noise scale of $\\gamma = 1$.\nFor the collider structure, we define $Z = f_1(X) + f_2(Y) + \\epsilon$.\nWe set the sample size to 500 and repeat each experiment 500 times. \nAll variables are one-dimensional. \nThe results are summarized in the table below, where the first two columns correspond to the collider structure and the last two columns to the chain structure.\n\n| **Structure**       | (X     Z ← Y) | (X → Z ← Y) | (Z → X   Y) | (Z → X → Y) |\n|---------------------|---------------|-------------|-------------|-------------|\n| **Type**            | Type I        | Type II     | Type I      | Type II     |\n| **Median**          | 0.04          | 0.49        | 0.03        | 0.16        |\n| **Power**           | 0.03          | 0.37        | 0.02        | 0.13        |\n\n\n**Typos**: (1)  We thank the reviewer for the concerns about the notation in Eq. (12). In this case, our intention was to express a deterministic data generation process where $X$ is constructed from $Z$, rather than to specify a distributional assumption for $X$. For this reason, we believe that using the equality sign is more appropriate in this context.\n\n(2) Thank you for the suggestion. We agree that our original wording here was unclear, and we have revised the paragraph as follows: \n\"Theorem 2 can be intuitively understood as asserting that the residuals obtained from regressing any square-integrable functions $g(X, Z)$ and $h(Y)$ onto $Z$ are uncorrelated. Since $g(X, Z)$ can represent any general relationship between $X$ and $Z$, this definition is capable of capturing general CI relationships. However, it requires considering all functions in the $L^2$ space, which is infeasible in practice. \"\n\nWe hope our response can clarify the confusion and addressed your concerns. Should you have any additional questions or suggestions, We’d be happy to clarify them further. Thank you.\n\n**Reference**\n\n[1] Fischer S, Steinwart I. Sobolev norm learning rates for regularized least-squares algorithms. JMLR, 2020."}, {"review_id": "8z0FqiBeNg", "reviewer": "Reviewer_ik6S", "summary": "This paper proposes a kernel parameter selection method for kernel-based conditional independence (KCI) testing, serving as an alternative to the commonly used median heuristic. The method is theoretically proven to be consistent and explicitly accounts for model estimation bias. Extensive empirical studies on both synthetic and real-world datasets are conducted to validate the effectiveness of the proposed approach.", "questions": "Questions. 1. I suggest presenting the results of the ablation study for \"On the selectable kernels\" and \"On the decomposition\" separately, so that it is easier to see the impact of each component on the empirical results. \n\n2.The results on the CHILD dataset in Table 2 show that KCIT with the median heuristic for kernel parameter selection performs better. Why isn't it highlighted in bold?\n\n3.I suggest that the authors include the running times of other methods in the main experiments in Section 5.1.3. In addition, I am curious about the running times when these two KCI testing methods are used within the PC algorithm for causal discovery.\n\n4.I'm not sure how the candidate weight list in line 233 is chosen. Is it selected based on the theoretical results provided, or is it chosen empirically?\n\n5.Could you explain in more detail how the p-value of the test is computed in line 237? Is this based on the theoretical results provided in the paper?\n\n6.Why does SelZ not improve the Type II error compared to Median? Please provide an intuitive explanation.\n\nIf the authors can address my concerns, I will consider increasing my score.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths: 1. This paper investigates a valuable topic and provides a well-motivated problem statement. \n\n2. The KCI test is an important tool in machine learning and data analysis, and kernel parameter selection has long been a challenging research problem. This paper proposes a practical parameter selection method that can encourage the broader application of KCI methods in scientific research. \n\n3. The paper is well-structured and easy to follow, the mathematical descriptions are mostly clear and well-written. \n\n4. The paper provide both theoretical proofs and empirical evidence to validate the superiority of the proposed method.\n\nWeaknesses: 1. The comparison of baseline CI testing methods in the simulation study is unfair. To the best of my knowledge, the conditional mean in GCM is typically estimated using kernel ridge regression or XGBoost regression. However, in lines 863 to 864 of the paper, Lasso, a linear regression method, is used instead. This can lead to poor performance of the GCM method under nonlinear simulation settings, which is indeed reflected in its empirical results.\n\n2.The distinction between the methods in the figures is not very clear and requires very careful examination — for example, \"Power\" and \"Median\" in Figure 1, and \"Median\" and \"Org\" in Figure 2.\n\n3.There is no evidence provided for the parameter selection, such as the choice of the candidate weight list.", "was_revised": true, "final_justification": "The authors' rebuttal has addressed my concerns satisfactorily, and I consider this to be a solid paper.", "rebuttal": "Dear Reviewer ik6S:\n\nWe sincerely thank you for your time and effort in reviewing our submission. Below, we provide our responses to your concerns and questions.\n\n>**W1.** The comparison of baseline CI testing methods in the simulation study is unfair. The model in GCM is typically estimated using kernel ridge regression or XGBoost regression. However, in lines 863 to 864 of the paper, Lasso, a linear regression method, is used instead.\n\n**A.** Thank you for your comment. \nIn the following experiments, we modified the original GCM by replacing its regression model with two alternatives:\n(1) KRR using Gaussian processes, with the same parameter initialization and bound settings as in our method;\n(2) XGBoost with the default hyperparameters provided in its official R package, as suggested in the original paper.\nWe compared both variants against our Median and Power methods on synthetic datasets, and the results are summarized in the table below.\nWe observed that GCM with XGBoost shows substantial improvement in performance: in low-dimensional settings, it effectively controls Type I error while achieving relatively low Type II error.\nHowever, we also observed that in high-dimensional settings, its Type I error begins to increase. In particular, when $\\mathrm{dim}_Z > 7$, our method outperforms GCM-XGBoost.\nWe will update the corresponding results and discussion in the next revision of our submission.\n\n| **Type**   | **Model**      | **1**   | **3**   | **5**   | **7**   | **9**   |\n|------------|----------------|---------|---------|---------|---------|---------|\n| **Type I** | GCM-XGBoost    | 0.044   | 0.068   | 0.076   | 0.082   | 0.082   |\n|            | GCM-GPR        | 0.902   | 0.954   | 0.746   | 0.990   | 1.000   |\n|            | Median         | 0.030   | 0.036   | 0.062   | 0.064   | 0.040   |\n|            | Power (Ours)   | 0.048   | 0.062   | 0.054   | 0.056   | 0.036   |\n| **Type II**| GCM-XGBoost    | 0.072   | 0.196   | 0.278   | 0.406   | 0.502   |\n|            | GCM-GPR        | 0.000   | 0.026   | 0.122   | 0.014   | 0.000   |\n|            | Median         | 0.202   | 0.316   | 0.380   | 0.434   | 0.492   |\n|            | Power (Ours)   | 0.142   | 0.246   | 0.314   | 0.326   | 0.418   |\n\n\n>**W2. & Q1.** The distinction between the methods in the figures is not very clear and requires very careful examination.\n\n**A.** Thank you for the suggestion. We will revise the color scheme of the figures and consider splitting Figure 2 into more subplots, which we agree would make it clearer. Thanks again!\n\n>**W3. & Q4.**  I'm not sure how the candidate weight list in line 233 is chosen. Is it selected based on the theoretical results provided, or is it chosen empirically?\n\n**A.** Thank you for your review. \nOur candidate list here is primarily based on empirical intuition, where the parameter space is restricted to a relatively broad but reasonable range. \nWe observed that selecting kernel parameters (e.g., bandwidth) that are too large or too small can significantly degrade the performance of CME-based regression, and in some cases even lead to numerical instability. \nThis, in turn, adversely affects the final testing power.\nTherefore, we use the median heuristic as a reference point and construct the candidate list by sampling multiple values around it. \nThat said, the list can be further adjusted if prior knowledge about the dataset to be tested is available.\n\n>**Q2.** The results on the CHILD dataset in Table 2 show that KCIT with the median heuristic for kernel parameter selection performs better. Why isn't it highlighted in bold?\n\n**A.** Thank you for the careful review. We indeed mistakenly swapped the Power and Median result on CHILD in Table 2. As shown in Table 4 in Appendix F.1.2, Power remains improved over Median on the CHILD benchmark and other datasets.  We will correct it in the revised version, thanks again for pointing it out.\n\n\n>**Q3.** I suggest that the authors include the running times of other methods in the main experiments in Section 5.1.3. In addition, I am curious about the running times when these two KCI testing methods are used within the PC algorithm for causal discovery.\n\n**A.** Thank you for the suggestion. \nWe have included the running time of all baseline methods in Table 6 in Appendix F.2.\nCurrently, we did not include the full runtime comparison in the main text, as our primary goal was to highlight the trade-off between test power and runtime for the Median and Power.\nWe appreciate your comment and will consider moving the runtime comparison of all methods into the main text in the revised version.\nBelow, we report the runtime of Median and Power with PC on the SACHs dataset across different sample sizes.\n\n| **Runtime (s)** | **200**         | **400**         | **600**         | **800**         | **1000**        |\n|----------------------|-----------------|-----------------|-----------------|-----------------|-----------------|\n| **Median**           | 22.85 ± 4.25    | 57.70 ± 5.57    | 111.8 ± 13.9    | 270.0 ± 38.3    | 432.2 ± 48.0    |\n| **Power**            | 27.08 ± 6.78    | 74.59 ± 11.0    | 219.6 ± 18.7    | 556.7 ± 49.9    | 958.6 ± 87.7    |\n\n\n\n>**Q5.** Could you explain in more detail how the p-value of the test is computed in line 237? Is this based on the theoretical results provided in the paper?\n\n**A.** In our method, the testing procedure is the same as in the original KCI. After selecting the kernel parameters based on estimated power, we perform testing only once with the final selected parameters. Therefore, the final test can be regarded as a standard test under fixed kernel parameters.\n\nIn brief, the KCI testing procedure proceeds as follows: firstly, obtain the residuals with the selected kernel parameters. SVD is then applied to these residuals matrices to extract their principal components (or basis functions), which represent directions in the kernel feature space. According to the theory of partial association, under the null hypothesis $H_0: X \\perp Y \\mid Z$, the coefficients associated with these basis functions should be uncorrelated, zero-mean, and normally distributed. Consequently, under $H_0$, the KCI statistic approximately follows a weighted sum of zero-mean Gaussian variables, whose null distribution can be approximated by a weighted chi-squared distribution. A detailed derivation is provided in Appendix B.2 of our submission, or in Proposition 5 of the original KCI paper [1].\n\n>**Q6.** Why does SelZ not improve the Type II error compared to Median? Please provide an intuitive explanation.\n\n\n**A.** Thank you for the insightful question. We can answer this result from the definition of conditional cross-covariance operators. From a theoretical standpoint, incorporating $Z$ into the operator input—i.e., using $\\phi(X,Z)$ instead of just $\\phi(X)$—is necessary for correctly characterizing conditional independence. \nAs established in Theorem 8 and Corollary 9 in [2, Appendix A.3], the operator $\\Sigma_{Y X|Z} = 0$ only implies a weaker marginal condition ($P_{XY} = \\mathbb{E}\\_Z[P_{X|Z} \\otimes P_{Y|Z}]$), whereas $ \\Sigma_{Y(X,Z)|Z} = 0 \\iff X \\perp Y \\mid Z$.\n\nIn practice, however, we observe that the choice of kernel parameters for $\\phi(Z)$ is not particularly critical for the final testing performance.\nThat is, a median heuristic to determine $\\phi(Z)$ is often sufficient when using the above operator for general CI testing.\nFurthermore, only in special cases: $X$ and $Y$ are dependent given $Z$ but this dependence varies across different regions of $Z$ in such a way that it cancels out under the weighting induced by the current choice of $\\phi(Z)$ can the change of $\\phi(Z)$ critically affect the test. \nIn these cases, the residuals from kernel regression may appear uncorrelated on average, even though dependence exists locally. \nChanging the choice of $\\phi_Z$ (e.g., SelZ) may help to “unmask” this hidden structure by assigning different weights across the $Z$-space. \nBut such cancellation cases are rare, and in most scenarios, a reasonable $\\phi(Z)$ already suffices.\n\nWe hope our response can clarify the confusion and addressed your concerns. We would greatly appreciate it if you could kindly reconsider your score. Should you have any additional questions or suggestions, We’d be happy to clarify them further. Thank you.\n\n**Reference**\n\n[1] Zhang et al. Kernel-based Conditional Independence Test and Application in Causal Discovery, UAI 2011.\n\n[2] Fukumizu K, et al. Dimensionality reduction for supervised learning with reproducing kernel Hilbert spaces. JMLR 2004."}]

Author rebuttal:

Meta-review: This paper introduces a kernel parameter selection method for the Kernel-based Conditional Independence (KCI) test. Instead of relying on the median heuristic, it decomposes the KCI statistic to isolate the kernel applied on the conditioning set, treating its parameters as trainable. These parameters are optimized by maximizing the ratio of the estimated test statistic to its variance, a proxy for test power at large sample sizes. The resulting kernel choice enhances conditional independence test power with minimal added computational cost. Theoretically grounded consistency guarantees and empirical improvements, approximately a 5–10% gain in power on synthetic and real datasets, demonstrate its strong practical value.

In a kernel-based testing framework, kernel selection is an important issue. The proposed approach is interesting, and all the reviewers agreed on accepting the paper. Thus, I also vote for acceptance.
Decision: Accept (poster)