Conditional independence testing under misspecified inductive biases
Authors: Felipe Maia Polo
Yuekai Sun
Moulinath Banerjee
Venue: NeurIPS 2023 spotlight (2023)
Keywords: conditional independence
hypothesis testing
misspecification
TL;DR: We derive approximations for the testing errors of three regression-based conditional independence (CI) tests depending on misspecification. We introduce the Rao-Blackwellized Predictor Test (RBPT), a CI regression-based misspecification-robust test.

Abstract: Conditional independence (CI) testing is a fundamental and challenging task in modern statistics and machine learning. Many modern methods for CI testing rely on powerful supervised learning methods to learn regression functions or Bayes predictors as an intermediate step; we refer to this class of tests as regression-based tests. Although these methods are guaranteed to control Type-I error when the supervised learning methods accurately estimate the regression functions or Bayes predictors of interest, their behavior is less understood when they fail due to misspecified inductive biases; in other words, when the employed models are not flexible enough or when the training algorithm does not induce the desired predictors. Then, we study the performance of regression-based CI tests under misspecified inductive biases. Namely, we propose new approximations or upper bounds for the testing errors of three regression-based tests that depend on misspecification errors. Moreover, we introduce the Rao-Blackwellized Predictor Test (RBPT), a regression-based CI test robust against misspecified inductive biases. Finally, we conduct experiments with artificial and real data, showcasing the usefulness of our theory and methods.

Conditional independence testing under misspecified inductive biases
Felipe Maia Polo
Yuekai Sun Department of Statistics University of Michigan yuekai @umi edu
Moulinath Banerjee
Department of Statistics
Department of Statistics University of Michigan moul b@uui ch, edu
University of Michigan
fel wtp.mmmiaplll@@mmiaii..
Abstract
Conditional independence (CI) testing is fundamental and challenging task in modern statistics and machine learning. Many modern methods for CI testing rely powerful supervised learning methods to learn regression functions Bayes predictors as an intermediate step; we refer to this class of tests as regression- based tests. Although these methods guaranteed control Type-I error when the supervised learning methods accurately estimate the regression functions or Bayes predictors of interest, their behavior is less understood when they fail due to misspecified inductive biases; in other words, when the employed models are not flexible enough or when the training algorithm does induce the desired predictors. Then, we study the performance of regression- misspecified inductive biases. Namely, we propose new approximations up- per bounds for the testing errors of three regression-baie based tests that depend on misspecification errors. Moreover, we introduce the Rao- Mao-Blackwellizer Predictor Test (RBPT), a regression based CI test robust against misspecified inductive bi- ases. Finally, we conduct experiments with artificial and real data, showcasing the usefulness of our theory and methods.
CI tests under
1 Introduction
Conditional independence (CI) testing is fundamental in modern statistics and machine learning (ML). Its use has become widespread in several different areas, from (i) causal discovery [12, 24, 34, 11] and (ii) algorithmic faimess [28], to (iii) feature selection/importancee [5, 37] and (iv) transfer learning [25]. Due its growing relevance across different sub-fields of statistics and ML, new testing methods with different natures, from regression to simulation-based tests, are often introduced.
Regression-basee CI tests, i.e., tests based on supervised learning methods, have become especially attractive in the past years due to (i) significant advances in supervised learning techniques, (ii) their suitability for high-dimensional problems, and (iii) their simplicity and easy application. However, regression-batt based tests usually depend on the assumption that we can accurately approximate the regression functions or Bayes predictors of interest, which hardly true if (i) either the model classes are misspecified or if (ii) the training algorithms do not induce the desired predictors, i.e., if we have misspecified inductive biases. Misspecified inductive biases typically lead to inflated Type-I error rates but also can cause tests to be powerless. Even though these problems can frequently arise practical situations, more attention should be given to theoretically understanding the effects of misspecification on CI hypothesis testing. Moreover, current regression-based methods are usually not designed be robust against misspecification errors, making testing less reliable. In this work, we study the performance of thrce major regression-bastt based conditional independence tests under misspecified inductive biases and propose the Rao- Hto-BBackwellized Predictor Test (RBPT), which is more robust against misspecification.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

With more details, our main contributions are:
We present new robustness results for three relevant regression-basees conditional independence tests: (i) Significance Test of Feature Relevance (STFR) [7], (ii) Generalized Covariance Measure (GCM) test [31], and (iii) REgression with Subsequent Independence Test (RESIT) [42, 24, 12]. Namely, we derive approximations or upper bounds for the testing errors that explicitly depend on the level of misspecification.
We introduce the Rao- Blackwellized Predictor Test (RBPT), a modification of the Significance Test of Feature Relevance (STFR) [7] test that is robust against misspecified inductive biases. In contrast with STFR and previous lagression/immllaiionbbane bassed' methods, the RBPT does nor require models to be correctly specified to guarantee Type-I error control. We develop theoretical results about the RBPT, and experiments show that RBPT is robust when controlling Type-I error while maintaining non-trivial power.
2 Preliminaries
Conditional independence testing. Let (X, Z) be a random vector taking values in X' x yx x Z S Rdxxdy and P be fixed family of distributions on the measurable space (X' x B, where B ==B(A x y x 2) is the Borel o-algebra. Let (x, Y. Z) ~ P and assume e P. If Po C P is the set of distributions in such that X 1 Y Z, the problem of conditional independence testing can be expressed in the following way:
Ho P Po
H1 : PiP
In this work, we also write Ho : X 1 Y Z and H1 : A Y Z. We assume throughout that we have access to a dataset D(n+m) = {(X,, Y,, 2 independent and identically distributed (i.idd) as (X, Y, 2), where D(n+m) splits into a test set D = {(X,, Yi, 2.) and a training set D("T) = (X., Y,, 20 For convenience, we use the training set to fit models and the test set to conduct hypothesis tests, even though other approaches are possible.
Misspecified inductive biases in modern statistics and machine learning. Traditionally, misspeci- fied inductive biases in statistics have been linked to the concept of model misspecification and then strictly related to the chosen model classes. For instance, if the best (Bayes) predictor for given X, linear function to predict Y, then we say our model
f", is a non-linear function of X, but is misspecified because f* is not in the class of linear functions. In modern machine learning and statisties, however, it is known that the training algorithm also plays crucial role in determining the trained model. For example, it is known that training overparameterized neural networks using stochastic gradient descent bias the models towards functions with good generalization [14, 33). In addition, D' Amour et al. [9] showed that varying hyperparameter values during training could result in significant differences in the patterns learned by the neural network. The researchers found, for instance, that models with different random initializations exhibit varying levels of -iitt--diitribttion accuracy in predicting skin health conditions for differrnnt skin types, indicating that each model learned distinct features from the images. The sensitivity of the trained model concerning different training settings suggests that even models capable of universal approximation may not accurately estimate the target predictor if the training biases do not induce the functions we want to learn.
We present toy experiment empirically demonstrate how the training algorithm can prevent us from accurately estimating the target predictor even when the model class is correctly specified, leading invalid significance tests. We work in the context of a high-dimensional (overparameterizee) regression with a training set of 250 observations and 500 covariates. We use the Generalized Covariance Model (GCM) test [31] to conduct the CI test. The data are generated
2 ~ N(, Iswa), X Z 213 and Y X, Z N(8) 2)
where the first five entries of fx are set to 20, and the remaining entries are zero, while the last five entries of By are set 20, and the remaining entries are zero. This results X and Y being condition- ally independent given Z and depending on Z only through a small number of entries. Additionally. E[X| Z] 2 and E|Y| /
26 Z, indicating that the linear model class is correctly specified. To
I Simulation- tests usually rely on estimating conditional distributions.
"See Appendix A.3 for more details
2

---

perform the GCM test, we use LASSO (1-11, penalization term added to empirical squared error) and the minimum-nowe norm least-squares solution fit linear models that predict and Y given Z. In this problem, the LASSO fitting approach provides the correct inductive bias since 3x and By are sparse. We set the significance level to a = 10% and estimate the Type-I error rate for 100 different training sets. Figure provides the Type-I error rate empirical distribution and illustrates that, despite using the same model class for both fitting methods, the training algorithm induces an undesired predictor in the minimum-norm case, implying an invalid test most of the time. On the other hand, the LASSO approach has better Type-I error control. In Appendix A, we give similar example but using the Significance Test of Feature Relevance (STFR) [7].
LASSO
40
Mmtmmm-nom
Ueraity
20-
In this work, we formalize the idea of misspecified inductive biases in the following way. Assume that a training algorithm A
03
02
Type-t error rate
03
0.4
0.5 0.5 07
used to choose a model gg(m) A(D! from the class glm). We further assume that the sequence (g converges to a
Figure 1: Type-I error rate is con- tingent on the training algorithm and not solely on the model classes, Un- like the minimum- norm solution, the LASSO fit gives the correct induc- tive bias in high-dimensional regres- sion, providing better Type-I error control.
limiting model g" in a relevant context context-dependent sense. We use different notions of convergence depending on the specific problem under consideration, which will be clear in the following sections. We say that 9 "carries misspecified inductive biases" if it does not equal the target Bayes predictor or regression function f". There are two possible reasons for g carrying misspecified biases: either the limiting model class is small and does not include f", or the training algorithm A cannot find the best possible predictor, even asymptotically.
Notation. We write Ep and Varp for the expectation and variance of statistics computed using i..d. copies of (X, Y. Z) P. Consequently, (P((A) = E. where IA is the indicator of an event A. If E. and Varp are conditioned on some other statistics, we assume those statistics are also computed using i.i.d. samples from P. As usual, & is the N(0, 1) distribution function. If (am)meN and (bm)mEN are sequences of scalars, then am = o(b..) is equivalent to 0m/bn, /mm + 0 as 0o and am bm + o(1 means o... 6m. = o(1). If (V((m))) where v(m) as constructed using i.i.d. samples of p(m) E P for each m, then (i) ((m) = (1(
a sequence of random variables,
means that for every > means that for every e > 0 there exists a M > 0 such that suPmen Ip pom ((m(()))))) > M) < s, (iii)
have IP Pptm (
e) - 0 m - 0o, (ii) ((m)
O,())
V(m) = Am + o1( means ((m)) am = (1), (iv) ((m) = op(am) means (7(m) /am = (1), and (v) ((m) = Op(am) means (/m) (mmm = (1)).. Finally, let (V(T)) "EN be a family of random variables that distributions explicitly depend on N and P E We give an example to clarify what we mean by "explicitly" depending on a specific distribution. Let v
E (X, (p)) where pP Ep [X. Here, V/() explicitly depends P because of the quantity pr. In this example, X,'s outside the expectation can have an arbitrary distribution (unless stated), i.e. could be determined by P or any other distribution. With this context, (i) V/(m) = (1(1) means that for every 8 >> 0 we have suprer (r(((())) > E) 0 as m + co, (ti) VLL = Op(1) means that for every >> 0 there exists a M > 0 such that SuPmeN,PEp P > M) < e, (iii) v(()) op(am) means (((m) /am. (1),
and (iv) m/(²
Op (am) means v/(m) /aam = Op (1).
Related work. There is a growing literature on the problem of conditional independence testing regarding both theoretical and methodological aspects'. From the methodological point of view, there is a great variety of tests with different natures. Perhaps, the most important groups of tests are (i) simulation-base tests [5, 3, 4, 32, 35, 20], (ii) regression- brasee tests [40, 24, 42, 38, 31, 71, (iii) kernel-based tests [10, 8, 34, 30], and (iv) information-theon
based tests [29, 16. 39]. Due to the advance of supervised and generative models in recent years, regression and simulation-base based tests have become particularly appealing, especially when Z is not low-dimensional or discrete. A related but different line of research is constructing a lower confidence bound for conditional dependence of X and Y given Z [41]. In that work, the authors propose a method that relies on computing the conditional expectation of a possibly misspecified regression model, which can be related to
*See, for example, Marx and Vreeken [21], Shah and Peters [31], Li and Fan [19]. Neykov et al. [23]. Watson and Wright [37], Kim et al. [15]. Shi et al. [32], Scetbon et al. [30], Tansey et al. [35], Zhang et al. [39], Ai et al. [1]
3

---

The STFR method studied by Dai al. [7] offers scalable approach for conducting conditional independence testing by comparing the performance of two predictors. To apply this method, we first train two predictors g(TT), X x Z + ) and 9¹ 2 + y on the training set D(r") to predict Y given our method presented in Section 4. Despite the relationship between methods, their motivations, assumptions, and contexts are different.
Simulation- based tests depend on the fact that we can, implicitly or explicitly, approximate the conditional distributions Px|z Priz. Two relevant simulation-based methods are the conditional randomization and conditional permutation tests (CRT/CPT) [5. 3, 4, 35J. For these tests, Berrett al. [4] presents robustness results showing that we can approximately control Type error even if our estimates for the conditional distributions are not perfect and we are under finite-sample also clear from their results that CRT and CPT might not control Type I error asymptotically when models for conditional distributions are misspecified. On the other hand, regression- based tests work under the assumption that we can accurately approximate the conditional expectations [[[] Z] and H[ Z] or other Bayes predictors, which is hardly true if the modeling and training inductive biases are misspecified. To the best of our knowledge, there are no published robustness results for regression-basee CI tests like those presented by Berrett et al. [4]. We explore this literature gap.
regime. However,
Regression-based conditional independence tests under misspecified inductive biases
This section provides results for the Significance Test of Feature Relevance (STFR) [7]. Due limited space, the results for the Generalized Covariance Measure (GCM) test [31] and the REgression with Subsequent Independence Test (RESIT) [42, 24, 12] are presented in Appendix Appendix A, one can easily derive double robustness property for both GCM and RESIT, implying that not all models need to be correctly specified or trained with the correct inductive biases for Type-I error control.
From the results in
3.1 Significance Test of Feature Relevance (STFR)
(X, Z) and Z, respectively. We assume that candidates for 92 ((m) are models in the same class as o(m! but replacing X with null entries. Using samples from the test set (( we conduct the test rejecting Ho X 1 Y Z if the statistic (n.m) & VnI(tn.m/// (f(m.m) exceeds Ta a -- a). depending on the significance level a E (0, 1). We define ((),m) and g((.m) as
(1 E4 m 27 1/2
T(n.m) A 1 Σi= r!!T) and a (n.m)
1 T n
(T
(3.1)
with Tr(m) & E(g!")) (m) (2.), ((0) C(0)m)) (X,, Z.), +e, Here, is a loss function, typically used during the training phase, and {s sd ((0,p²)) are small artificial random noises that do not let (m).) vanish with growing training set, thus allowing the asymptotic distribution of (m,m) to be standard
normal under Ho : X T Z. If the p-value is defined as p(D(1) D(())) = =1 (a(m))))) the test is equivalently given by
{
1, p(D D( S
STER (D(m), D(m))
(3.2)
0, otherwise
The rationale behind STFR is that if Ho : X XILY similar performance in the test On the other hand, if Ho does not hold, expect ofm) to have significantly better performance, and then we would reject the null hypothesis. Said that, to control STFR's Type-I error, it is necessary that the risk gap between gf and "!()) 1("") - Ep {(g(m) (X, 2), Y) D( under Ho vanishes as the training set size increases. Moreover, we need the risk gap be positive for the test have non-trivial power. These conditions can be met
holds, then ((m)) and a(m) should have
(2),
if the risk gap of oi,r and gi.r, the limiting models of g(()) and a(()) is the same the risk gap of the Bayes' predictors
fi arg min,, (x] Y)) and fip A arg min,, Er(((//Z))))) Y)).

---

where the minimization is done over the set of all measurable functions". However, the risk gap between glmh and 92 under Ho. In general, we should expect şi.P perform better than gi.p because the second predictor does not depend on X. Furthermore, their risk gap can be non non-positive even if fī,r performs better than f. In Appendix A.2, we present two examples in which model misspecification plays an important role when conducting STFR. The examples show that Type-I error control and/or power can be compromised due to model misspecification.
(m) will typically not vanish if gi and 92.p are not the Bayes' predictors even
To derive theoretical results, we adapt the assumptions from Dai et al. [7]: Assumption 3.1. There are functions gi.P. 92,P, and a constant 7 > 0 such that
Ep (Z), [D("") - Ep (((..,
[p [e(ol (x, 2) DD EE -Xx(
-Op(m77 >)
Assumption 3.2. There exists a constant l: such that
Ep [1T("))2+ [D[""] = (p(1) as m oc
Assumption 3.3. For every P E P, there exists a constant of > 0 such that Varp[T][m) D - o = (1) as m + do and inf o > 0
PEP
Finally, we present the results for this section. We start with an extension of Theorem presented by Dai et al. [7] in the case of misspecified inductive biases.
Theorem 3.4. Suppose that Assumptions 3.1, 3.2, and 3.3 hold. If n. is a function of m such that and n = )(m²") ) as m + 00, then
Eplp (D(a) D(m)) = 1 ((.
V T +o(1)
where o(1) denotes uniform convergence over all E as m - oo and
SP STER Er(((s,,((2), E, Ep Y),
Theorem 3.4 demonstrates that the performance of STER depends on the limiting models gi.p and gå.r- Specifically, if STTTER > 0, then Ey (TTT (D).) D( - even Ho 1. Y. holds. In practice, we should expect 223 > 0 because of how we set the class for a In contrast, we could have 52). < 0, and then (<> D(T") )[=))] o even if the gap between Bayes' predictors positive. See examples in Appendix A.2 for both scenarios. Next, provide Corollary 3.6 to clarify the relationship between testing and misspecification errors. This corollary formalizes the intuition that controlling Type-I error is directly related misspecification of gi,p, while minimizing Type-II error is directly related to misspecification of gi.p-
Eyl
Definition 3.5. For distribution P' and loss function É, define the misspeciification gaps: AI. Ep (XX,, 2), B)) Z),Y) Y)] and A.. 2 (2))))oo
The misspecification gaps defined in Definition 3.5 quantify the difference between the limiting predictors gi, p and gi. p and the Bayes predictors fī, and fi,e. i.e., give a misspecification measure for gi.e and 92, p. Corollary 3.6 implies that the STFR controls Type-I error asymptotically if A = 0, and guarantees non-trivial power the degree of misspecification of gi.r is not large compared to the performance difference of the Bayes predictors Ar, that is, when Ar Air > 0. Corollary 3.6 (Bounding testing errors). Suppose we are under the conditions of Theorem 3.4.
(Type-I error) If Ho X 1 Y Z holds, then EplysTR (D(a) p(")) ) @ - aep)
+ +
where o(1) denotes uniform convergence over all E Pu as m + xc.
(Type-Il error) In general, we have
1 - Lrllya (D(a) D(m)) < + (T
1 (Ar Air)) + o(1)
where o(1) denotes uniform convergence over all P E P as m + 0o and Ar 2 Ep((((f,r(())
Ep pXx L))Y
We assume fî and fū,r be well-defined and unique
5

---

4 A robust regression-based conditional independence test
This section introduces the Rao-Blackwellized Predictor Test (RBPT), a misspecification robust conditional independence test based on ideas from both regression and simulation- based CI tests. The RBPT assumes that we can implicitly or explicitly approximate the conditional distribution of | Z and does not require inductive biases to be correctly specified. Because RBPT involves comparing the performance of two predictors and requires an approximation of the distribution of X 7. we can directly compare with the STFR [7] and the conditional randomization/permuaaii tests (CRT/CPT) [5, 4]. The RBPT can control Type-I error under relatively weaker assumptions compared to other tests, allowing some misspecified inductive biases.
The RBPT can be summarized as follows: (i) we train gfm) that predicts Y given (X, Z) using D(r); (ii) we obtain the Rao-Blackweliized predictor A ((m) by smoothing g(m). i.e.
fm)) (z) = (
(z, 2)d
then (iii) compare its performance with g gom)s using the test set D(m) and convex loss function é (not necessarily used to train 9 g(m)), and (iv) if the performance of g g(m) is statistically better than A (m)ss ss
T Y z. The proce- dure described here bears resemblance to the Bao-BBackwwllliztton of estimators.
we reject Ho
Algorithm 1: Obtaining v-vuuee for the RBPT
In classical statistics, the mao-Blackwell, theorem [17] states that by taking the con- ditional expectation of an estimator with re- spect to a sufficient statistic, we can obtain a better estimator if the loss function is con-2 vex. In our case, the variable can be seen "sufficient statistic" for Y under the as- sumption of conditional independence Ho : x LLY Z. If Hu holds and the loss {(g. y) is convex in its first argument, we can show using Jensen's 's inequality that the resulting model h (m)) has a lower risk relative to the initial model g mm)) i.e., Ep [e(h (mm) (Z), Y) D("") - (m (m) (X, Z). Y) D
Input: (i) Test set D!")) = ((X;, Yi, Z (ii) initial predictor g gmm) (iii) conditional distribution
estimate Q (iv) convex loss function E;
Output: p-value p: For each E [ri]. get
get ((m) (Z.) = J g gf(m) (z, Z, Z
2-
Compute E(n.m) A vnrla.m) /a(n.m) where
T(m.m) & + T.(m)) with
T.(m) A e(h (m) (Z.), {(} (m) (X., 2.), Yi)
and g (m.m) being (T:) 's sample std dev (Eq. 3.1). Then, the risk gap in RBPT is non-positive return p (3(mm))
under Ho in contrast with STFR's risk gap,
which we should expect to be always non-negative given the definition of m(m) in that case. That fact negatively biases the RBPT test statistic, enabling better Type-I error control.
In practice, we cannot compute (mm) exactly because Pxzz is usually unknown. Then, we use an approximation @(m)) which can be given explicitly, e.g., using probabilistic classifiers or conditional density estimators [13], implicitly, e.g., using generative adversarial networks (GANs) [22, 3]. We assume that Q @mm) is obtained using the training set. The approximated ((m) is
(x) $ f (x, 2md (2)
where the integral can be solved numerically in case ((m) has known probability mass function or Lebesgue density (e.g., via trapezoidal rule) via Monte Carlo integration in case we can only sample from @(m)) Finally, for fixed significance level (0, 1), the test y RAPT is given by Equation 3.2 where the v-value is obtained via Algorithm 1.
Before presenting RBPT results, we introduce some assumptions. Let Qxiz represent the limiting model for & (m) The conditional distribution Qxiz depends on the underlying distribution P. but we omit additional subscripts for ease of notation. Assumption 4.1 defines the limiting models and fixes a convergence rate.
'The loss function f(j. 3) needs to be convex with respect to its first entry (0) for all y. Both the test set and training set sizes, and the loss function can be chosen using the heuristics introduced by Dai et al. [7].

---

Assumption 4.1. There is a function gi, conditional distribution Q'12 and a constant 7 > 0 s.t.
Ep (m) (Z) -
(mm) = Op(mm>) and Ep [drvl
(m) Qxiz) (mm) = =Op(m))
where drv denotes the total variation (TV) distance. Additionally, assume that both Q and Qxiz are dominated by common o-finite measure which does not depend on Z or m.
The common dominating measure in Assumption 4.1 could be, for example, the Lebesgue measure in R Next, Assumption 4.2 imposes additional constraints on the limiting model Qx Under that assumption, the limiting misspecification level must be uniformly bounded over all P E P.
Assumption 4.2. For all P E P, the chi-square divergence
x² (Qx(221PP(22) e
dQxiz
TPxiz dQxiz -1
a well-defined integrable random variable and supper Ep Ix" (Qx1z [Px|z]] < co.
Now, assume g(m) is chosen from a model class g(m). Assumption 4.3 imposes constraints on the model classes (g(m)) and loss function f.
2)),, S M <, for some real and positive M > 0, uniformly for all m, and (ii) that E a T.- Lipschiizz loss function (with respect to its first argument) for certain I, > 0, i.e., for any ú. 8' V, we have that [[( E(ÿ' v) S T. ll f l1z
Assumption 4.3. Assume (i) gupgegtms sup( (x.))xxxxx
Assumption 4.3 is valid by construction since we choose ((m)) and the loss function E. That assumption satisfied when, for example, (a) models in gm.g(m) are uniformly bounded, (b) ( v) = 11 - vll with p 2 1, and (c) y is bounded subset of Rdy, i.e., in classification problems and most of the practical regression problems. The loss {ūj. 3) 1 yl with p 2 1, is also convex with respect to its first entry and then a suitable loss for RBPT. is important to emphasize that & does not need to be the same loss function used during the training phase. For example, in classification problems, where is a one-hot encoded class label and ý is a vector of predicted probabilities given by a model trained using the cross-entropy loss.
could use E(ÿ, y) |1@ y
Theorem 4.4. Suppose that Assumptions 3.2, 3.3, 4,1, 4.2, and 4.3 hold. If is a function of m such that n + co and n = o(m²) as m + xc, then
(D(a) (n) D( = + Ep(g (e
+ +0(
o
where o(1) denotes uniform convergence over all P P as m 00 and DRANT
S DBBPT with
SRATT & Er [e gf) Z)Q2x (()))(xxx)))))))) r)] - Er [ (J ( 2)dx122()))) Y)]
and
RBPT
EP [e(eloi(Xx Y) Er [f gi Z)d 2)dPx12(s), Y)]
Jonsen's & gap
When Ho : X Y | 7 holds and f a strictly convex loss function (w.rtt. its first entry), we have that 22 0, allowing" some room for the "incorrectness" of Qxiz- That is, from Theorem 4.4, as long as DREPT < 0, i.e,, if Q'iz's incorrectness (measured by QPATT) is not big as Jensen's 's gap Pp2. RBPT has asymptotic Type-I error control. Uniform asymptotic Type-I error control is possible if suprep, SROPT < 0. This is a great improvement of previous work (e.g., STFR, GCM, RESIT. CRT, CPT) since there is no need for any model to converge to the ground truth if S2 < SREET which weaker condition. See however that a small 2722 reduces the room for Qx incorrectness. In the extreme case, when gb is the Bayes predictor, and therefore does not depend on X under Ho. we need Qxiz = Pxiz almost surely. On the other hand, if gp is close to the Bayes predictor, RBPT has better power. That imposes expected trade-off between Type-I error control and
'In practice, do not need é to be strictly convex for the Jensen's gap be positive. Assuming that g² depends on under Ho is necessary, though. That condition is usually true when ge not the Bayes predictor. In this case, Assumption 3,3 is not true. We need to include artificial noises in the definition of as it was done in STFR by Dai et al. [7] in case have high confidence that models converge to the ground truth.
7

---

1.0
de-
1.0
d2
1.0
y- D
y-
0.3
Type- error
0.0
0.6
0.5
0.6
0.4
0.4
0.4
0.4
0.2
0.0
0.0
0 0.0
0.00
0.01
0.02
0.00
0.01
0.02
0
R0PT
R2PT2
Figure 2: Type-I error rates 0). In the first plots, set A 0 for RBPT, permitting Type-I error control across different dz values (Thcorem 4.4), while RBPT2 allows Type-I error control moderate dz. All baselines fail to control Type-I emors regardless of dz. The last two plots illustrate that CRT emerges as the least robust test this context, succeeded by RBPT and CPT.
power. To make a comparison with Berrett et al. [4] 's results in the case of CRT and CPT, we can express remark in terms of the TV distance between Qxiz and Px|z- It can be shown that if Ep [ddddd (Qxiz Px|2]] 1 (2M L), then Type-I error control is guaranteed (see Appendix A.5). This contrasts with Berrett et al. [4] 's results because Ep.drv (dv((Q) Px]2]] 0 is not needed.
We conclude this section with some relevant observations related to the RBPT.
On RBPT's power. Like STFR, non-trivial power guaranteed if the predictor gp good enough. Indeed, the second part of Corollary 3.6 can be applied for an upper bound on RBPT's Type-ll error.
Semi-supervised learning. Let Y denote label variable. Situations in which unlabeled samples (X,, Z:) are abundant while labeled samples (X;, Y, Z:) are scarce happen in real upplications of conditional independence testing [5, 4]. RBPT is well suited for those cases because the practitioner can use the abundant data to estimate Pxiz flexibly. The semi-supervised learning scenario also applies RBPT2, which describe next.
Running RBPT when it is hard estimate Pxj2: the RBPT2. There might be situations in which it is hard to estimate the full conditional distribution Pxiz. An alternative approach would be estimating the Rao- Bho-Blaacweelieed predictor directly using a second regressor. After training g(m), we could use the training set, organizing it in pairs ((Z, g (Z, x,))), train a second predictor ((m)) to predict g(m² (Z, X) given Z. That predictor could be trained to minimize the mean-squared error. The model i (m) should be more complex than g(m) the sense that we should hope that the first model performs better than the second under Ho in predicting Y. Consequently, this approach is effective when unlabeled samples are abundant, and we can train using both unlabeled data and the given training set. After obtaining (mm), the test is conducted normally. We name this version of RBPT as "RBPT2". We include a note on how to adapt Theorem 4.4 for RBPT2 in Appendix A.6.
Experiments
We empirically* analyze RBPT/RBPT2 in the following experiments and compare them with relevant benchmarks, especially when the used models are misspecified. We assume = 10% and {() v) - 3)² The benchmarks encompass STFR [7], GCM [31], and RESIT [42], which represent regression-based CI tests. Furthermore, we examine the conditional randomizaaiion/permuattiooo tests (CRT/CPT) [5, 4] that necessitate the estimation of Pxiz-
Artificial data experiments. Our setup takes inspiration from Berrett et al. [4], and the data is generated as
Z ~~ N
2 2)),), Y 2 (eX + a x 1).
Here, dz denotes the dimensionality of Z. a and are sampled from N (0, Laz) ). the constant e deter- mines the conditional dependence of X and Y on Z, and the parameter dictates the hardness of conditional independence testing: a non-zero implies potential challenges
Type-I error control as there might be pronounced marginal dependence between X and Y under No. Moreover, the training (resp. test) dataset consists of 800 (resp. 200) entries, and every predictor we employ operates on linear regression. RESIT employs Spearman's 's correlation between residuals as test statistic while
Code in bettps:/ggthhin

---

CRT and CPT deploy STFR's test statistic, all of them with y-values determined by conditional sam- pling/permutations executed 100 times (B 100), considering Qxiz = ((b z)² 0, 1). The value of gives the error level in approximating Pxiz- To get in the two variations of RBPT, we either use Q (RBPT) or kernel ridge regression (KRR) equipped with a polynomial kernel to predict 0x(X, X Z) from Z (RBPT2). We sample generative parameters (a, 6) five times using different random seeds, and for each iteration, we conduct 480 Monte Carlo simulations to estimate Type-I error and power. The presented results are the average (+ standard deviation) estimated Type-I error/power across iterations.
In Figure 2 (resp. 4) we compare our methods' Type- error rates (with c = 0) (resp. power) against bench- marks. Regarding Figure 2, we focus regression- based tests (STFR, GCM, and RESIT)
1.0
1000
(errr rate (ADPT2)
the first two plots and on simulation-based tests (CRT and CPT) in the last two plots. Regarding the first two plots, it is not straightforward to compare the level of misspecifi- cation between our methods and the benchmarks, so we use this an opportunity to illustrate Theorem 4.4 and results from Section 3 and Appendix A. Fixing 0 = O for RBPT, the Rao- Rao-Blackwelllnn Blackwellized predictor is perfectly obtained, permitting Type-I error control regardless of the chosen dz. Using KRR for RBPT2 makes h close to h when dz is not big and permits Type-I error control. When dz is big, more data is needed fit h, which can be accomplished using unlabeled data, as demonstrated in Figure 3 and commented in Section On the other hand, Type-I error control is always violated for STFR, GCM, and RESIT when 7 grows. Regarding the final two plots, we can more readily assess the robustness of the methods when discrepancies arise between Qxiz and Pxjz as influenced by varying Fig- ure 2 illustrates that CRT is the least robust test in this context, succeeded by RBPT and CPT. In Figure 4, we investigate how powerful RBPT and RBPT2 can be practice when dz = 30. We compare our methods with CPT (when 0 0), which seems to have practical robustness against misspecified inductive biases. Figure shows that RBPT2 and CPT have similar power while RBPT is slightly more conservative.
0.6
0.4
0.0
0.010 0.015
Y
Figure Making RBPT2 more robust using unlabeled data. With dz 40, we gradually increase the unlabeled sample size from 0 to 1000 when fitting h. The results show that larger unlabeled sample size leads to effective Type-I error control. Even though we present this result for RBPT2, the same pattern is expected for RBPT the presence of unlabeled data.
Some concluding remarks are needed. First, RBPT and RBPT2 have shown to be practical and robust alternatives to condi- tional independence testing, exhibiting reasonable Type-I error control, mainly when employed in conjunction with a large unlabeled dataset, and power. Second, while CPT demonstrates notable robustness and relatively good power, its practicality falls short compared to RBPT (or RBPT2). This is because CPT needs a known density functional form for Qx1z (plus the execution of MCMC chains) whereas RBPT (resp. RBPT2) can rely on conventional Monte Carlo integration using samples from Qxiz (resp. supervised learning).
RAPT
RBFT2
0.8
Power
0.4
0.2
0.0
0.1
0.2
0.3
0.4
Figure 4: Power curves for different methods. We compare our methods with CPT (when = 0), which seems to have practical robustness against mis- specified inductive biases. RBPT2 and CPT have similar power, while RBPT slightly more conservative.
Real data experiments. For our subsequent experiments, we employ the car insurance dataset examined by Angwin et al. [2]. This dataset 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 risk metric and the insurance price levied on a 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 Y. signifying the insurance price. A pertinent question revolves around
For CPT execution, the Python script at http: http///wwwssse stat, uchicago. edu/"rina/ cptpppt.... html was used, operating single MCMC chain and preserving all other parameters defined by the original authors.

---

0.30
0.30
ROPT
STRR
CRT
RDPT
STTR
0.25
0.25
RBP72
Type-1 error rate
0.20
0:20
D-value
0.15
0.15
0.10
0.10
0.05
0.00
0.00
Califoria
Iliio's
Missouri
Texas
California
Illinis
Missouri
Texas
Figure 5: Type-I error control and power analysis using car insurance data [2]. The first plot shows that RBPT and RBPT2 have better control over Type-I errors compared to all other methods, including CPT. The second plot reveals that all methods give the same qualitative result, corroborating the findings of Angwin et al. [2], suggesting that RBPT and RBPT2 can have good power while being more robust to Type-I error.
the validity of the null hypothesis Ho X T Y Z, essentially questioning if demographic biases influence pricing.
We split our experiments into two parts. the initial part, our primary goal is to compare the Type-I rate across various tests. To ensure that Ho is valid, we discretize Z into twenty distinct values and shuffle the Y values corresponding to each discrete Z value. If test maintains Type-l error control, we expect it to reject Ho for most part, we focus on assessing the power of our methods. Given our lack of ground truth, we qualitatively compare RBPT and RBPT2 findings with those obtained by baseline methods and delineated by Angwin et al. [2], utilizing a detailed and multifaceted approach. In this last experiment, we aggregate the analysis for each state without conditioning on the firm. We resort to logistic regression for estimating the distribution of X Z used by RBPT, GCM. CRT, and CPT. For RBPT2, we use CatBoost regressor [26] to yield the Rao- Blackwellized predictor. We omit RESIT in this experiment as the additive model assumption is inappropriate. Both CRT and CPT methods utilize the same test metrics as STER. The first plot of Figure 5 shows that RBPT and RBPT2 methods have better control over Type-I errors compared to all other methods, including CPT. The second plot reveals that all methods give the same qualitative result that discrimination against minorities in ZIP codes most evident in Illinois, followed by Texas, Missouri, and California. These findings corroborate with those of Angwin et al. [2]. indicating that our methodology has satisfactory power while maintaining robust Type-I error control.
10% of the companies in each state. In the second
6 Conclusion
In this work, we theoretically and empirically showed that widely used regression- bassed conditional independence tests sensitive to the specification of inductive biases. Furthermore, we introduced the Rao-Bla Blackwellized Predictor Test (RBPT), misspecificationnrobiee test. RBPT is theoretically grounded and has been shown perform well in practical situations compared to benchmarks.
conditional independence
I Limitations and future work. Two limitations of RBPT are that (i) the robustness of RBPT can lead to more conservative test, as we have seen in the simulations; moreover, (ii) requires the estimation of the conditional distribution Pxiz. which can be challenging. To overcome the second problem, introduced a variation of RBPT, named RBPT2, in which the Rao- Blackwellized predictor is obtained in supervised fashion by fitting second model h Z + y that predicts the outputs of the first model 9 : X' x Z + V. However, this solution only works h is better than ğ in predicting Y under Ho, which ultimately depends the model class for h and how that model is trained. Future research directions may include (i) theoretically studying the power of RBPT more detail and (ii) better understanding RBPT2 from theoretical or methodological point of view, e.g., answering questions on how to choose and train the second model.
7 Acknowledgements
This paper is based upon work supported by the National Science Foundation (NSF) under grants no. 1916271, 2027737, 2113373, and 21 13364.
We run the experiment for 48 different random seeds and report the average Type-I error rate.
10

---

References
[1] Chunrong Ai, Li-Hsien Sun, Zheng Zhang, and Liping Zhu. Testing unconditional and condi- tional independence via mutual information. Journal of Econometrics, 2022.
[2] Julia Angwin, Jeff Larson, Lauren Kirchner, and Surya Mattu. Minor- ity neighborhoods pay higher car insurance premiums than white areas with the same risk, April 2017.
URL https://www http://wwwwwoppbicc...cc org/article/ sinority-net neigherrooodds hoioorooods-hhheerre higher- car www--aaarrnnneeeeeeee www.-nnnsuaneeeee - white- areas- sameesssaeeeeee mase-risk. [Online; last accessed in 09- Se0teembrr--0222
[3] Alexis Bellot and Mihaela der Schaar. Conditional independence testing using generative adversarial networks. Advances in Neural Information Processing Systems, 32, 2019.
[4] Thomas B Berrett, Yi Wang. Rina Foygel Barber, and Richard Samworth. The conditional permutation test for independence while controlling for confounders. Journal of the Royal Statistical Society: Series B (Statistical Methodology). 82(1):175-197, 2020.
[5] Emmanuel Candes, Yingying Fan, Lucas Janson, and Jinchi Lv. Panning for gold: model- x x'knockoffs for high dimensional controlled variable selection. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 80(3):551-577, 2018.
[6] Olivier Cappé, Eric Moulines, and Tobias Rydén. Inference in hidden markov models. In Proceedings EUSFLAT conference, pages 14-16, 2009.
[7] Ben Dai, Xiaotong Shen, and Wei Pan. Significance tests of feature relevance for a black-box learner. IEEE Transactions on Neural Networks and Learning Systems, 2022.
[8] Gary Doran, Krikamol Muandet, Kun Zhang, and Bernhard Schölkopf. A permutation-bass kernel conditional independence test. In UAI, pages 132-141, 2014.
[9] Alexander D' Amour, Katherine Heller, Dan Moldovan, Ben Adlam, Babak Alipanahi, Alex Beutel, Christina Chen, Jonathan Deaton, Jacob Eisenstein, Matthew D Hoffman, et al. Un- derspecification presents challenges for credibility in modern machine learning. Journal of Machine Learning Research, 2020.
[10] Kenji Fukumizu, Arthur Gretton, Xiaohai Sun, and Bernhard Schölkopf. Kernel measures of conditional dependence. Advances in neural information processing systems, 20, 2007.
[11] Clark Glymour, Kun Zhang, and Peter Spirtes. Review of causal discovery methods based on graphical models. Frontiers in genetics, 10:524, 2019.
[12] Patrik Hoyer, Dominik Janzing, Joris M Mooij. Jonas Peters, and Bernhard Schölkopf. Nonlinear causal discovery with additive noise models, Advances in neural information processing systems, 21, 2008.
[13] Rafael Izbicki and Ann B. Lee. Converting high-dimensional regression to high-dimensional conditional density estimation. 2017.
[14] Dimitris Kalimeris, Gal Kaplun, Preetum Nakkiran, Benjamin Edelman, Tristan Yang. Boaz Barak, and Haofeng Zhang. Sgd on neural networks learns functions of increasing complexity. Advances neural information processing systems, 32, 2019.
[15] Ummn Kim, Matey Neykov, Sivaraman Balakrishnan, and Larry Wasserman. Local permutation tests for conditional independence. arXiv preprint 2 1666, 2021.
[16] Mariusz Kubkowski, Jan Mielniczuk, and Pawel Teisseyre. How to gain on power: Novel conditional independence tests based on short expansion conditional mutual information. Mach. Learn. Res., 22:62-1,2022
[17] Erich L. Lehmann and George Casella. Theory of point estimation. Springer Science & Business Media, 2006.
[18] Erich Leo Lehmann, Joseph Romano, and George Casella. Testing statistical hypotheses, volume 3. Springer, 2005.

---

[19] Chun Li and Xiaodan Fan. On nonparametric conditional independence tests for continuous variables. Wiley Interdisciplinary Reviews: Computationall Statistics, 12(3))e1489 2020.
[20] Molei Liu, Eugene Katsevich, Lucas Janson, and Aaditya Ramdas, Fast and powerful conditional randomization testing via distillation. Biomelrika, 109(2):277-293, 2022.
[21] Alexander Marx and Jilles Vreeken. Testing conditional independence on discrete data using stochastic complexity. In The 22nd International Conference Artificial Intelligence and Statistics, pages 496-505. PMLR, 2019.
[22] Mehdi Mirza and Simon Osindero. Conditional generative adversarial nets. arXiv preprint 11X.4:1411.1784, 2014.
[23] Matey Neykov, Sivaraman Balakrishnan, and Larry Wasserman. Minimax optimal conditional independence testing. The Annals of Statistics, 49(4):2151-2177, 2021.
[24] Jonas Peters, Joris M Mooij, Dominik Janzing, and Bernhard Schölkopf. Causal discovery with continuous additive noise models. Journal of Machine Learning Research, 15:2009-200 2053, 2014.
[25] Felipe Maia Polo, Rafael Izbicki, Evanildo Gomes Lacerda Jr, Juan Pablo Ibieta-Jimenez, and Renato Vicente. A unified framework for dataset shift diagnostics. Information Sciences, 649; 119612, 2023.
[26] Liudmila Prokhorenkova, Gleb Gusev, Aleksandr Vorobev, Anna Veronika Dorogush, and Andrey Gulin. Catboost: unbiased boosting with categorical features. Advances in neural information processing systems, 31, 2018.
[27] Sidney Resnick. A probability path. Springer, 2019.
[28] Ya'acov Ritov, Yuekai Sun, and Ruofei Zhao. On conditional parity as notion of non- discrimination in machine learning. arXiv preprint arXiv: 2017. 2017.
[29] Jakob Runge. Conditional independence testing based on nearest-neighbor estimator of conditional mutual information. In International Conference on Artificial Intelligence and Statistics, pages 938 947. PMLR, 2018
[30] Meyer Scetbon, Laurent Meunier, and Yaniv Romano. An asymptotic test for conditional independence using analytic kernel embeddings. arXiv preprint arX1v:2110.14868, 2021.
[31] Rajen D Shah and Jonas Peters. The hardness of conditional independence testing and the generalised covariance measure. The Annals of Statistics, 48(3):1514-1533 2020.
[32] Chengchun Shi, Tianlin Xu, Wicher Bergsma, and Lexin Li. Double generative adversarial networks for conditional independence testing. J. Mach. Learn. Res., 22:285-1, 2021.
[33] Samuel Smith, Erich Elsen, and Soham De. On the generalization benefit of noise in stochastic gradient descent. In International Conference on Machine Learning, pages 2020.
PMLR,
[34] Eric V Strobl, Kun Zhang, and Shyam Visweswaran. Approximate kernel-based conditional independence tests for fast pormmmrretrtri causal discovery. Journal of Causal Inference, 7(1), 2019.
[35] Wesley Tansey, Victor Veitch, Haoran Zhang, Raul Rabadan, and David M Blei. The holdout randomization test for feature selection in black box models. Journal of Computational and Graphical Statistics, 31(1):151-16,, 2022.
[36] Alexandre Tsybakov. Introduction to nouparametric estimation, 2009.
URL
https://di..rr/100 1007/000133300 13794. Revised and extended from the, 9(10), 2004.
[37] David Watson and Marvin N Wright. Testing conditional independence in supervised learning algorithms. Machine Learning. 1107 2021.
12

---

[38] Hao Zhang, Shuigeng Zhou, Jihong Guan, and Jun Huan. Measuring conditional independence by independent residuals for causal discovery. ACM Transactions on Intelligent Systems and Technology (TIST), 10(5):1-19, 2019.
[39] Hao Zhang. Shuigeng Zhou, Kun Zhang, and Jihong Guan. Residual similarity based conditional independence test and its application in causal discovery. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 5942-5949) 2022.
[40] Kun Zhang, Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Kemnel-based conditional independence test and application in causal discovery. arXiv preprint arXiv: 2012.
[41] Lu Zhang and Lucas Janson. Floodgate: inference for model-free variable importance. arXiv preprint vrXiv:2007.01288: 2020.
[42] Qinyi Zhang, Sarah Filippi, Seth Flaxman, and Dino Sejdinovie. Feature-to-feature regression for a two-step conditional independence test. In 33rd Conference on Uncertainty in Artificial Intelligence, UAI 20/7. Association for Uncertainty in Artificial Intelligence (AUAI), 2017.
13

---

A Extra content
A.1 Misspecified inductive biases in modern statisties and machine learning
We present a toy experiment to empirically demonstrate how the training algorithm can prevent from accurately esti- mating the Bayes predictor even when the model class is correctly specified, leading to invalid significance tests, We work in the context of high-dimensional (overparameter- ized) regression with training set of 250 observations and 2 300 covariates. We use the Significance Test of Feature Relevance test" (STFR) [7] conduct the CI test. The data are generated as
30
LASSO
PCR
25-
Density
15
19
0.0
0.2
0.4
0.0
0.8
1.0
Z (0, z ~ N(8 1, Y x N(8" 2,
Type-l orror rate
Figure 6: Type-I error rate is contin- gent on the training algorithm and not solely on the model classes. Un- like PCR, the LASSO fit provides the correct inductive bias in high- dimensional regression, controlling Type-I error.
where the first thirty entries of 3 are set to 1, and the remain- ing entries are zero. See that X 1l Y Z and that Y is linearly related to Z and (X, Z), and then the class of linear predictors is correctly specified when predicting Y from Z or (X, Z). LASSO (II-l1, penalization term added to empirical squared error) and principal compo- nents regression (PCR) to train the linear predictors. Since B is sparse, the LASSO fit provides the correct inductive bias while PCR leads to misspecification. We set the significance level to a 1% and estimate the Type-I error rate for 100 different training sets. Figure 6 provides the Type-I error rate empirical distribution and illustrates that, despite using the same model class for both fitting methods, the training algorithm induces the wrong model in the PCR case, implying an invalid test most of the time.
To perform the STFR test,
A.2 Examples on when STFR fails
Examples A.I and A.2 show simple situations in which Type-I error control is compromised or the conditional independence test has no power due to model misspecification. As we see in the next examples, Type-I error control is directly related to G2 misspecification, while Type-Il error minimization directly relates to 9i misspecification.
Example A.1 (No Type-I error control). Suppose Y 2 222 + Ey and 22 + Ex, where En -N (0, 1) are independent noise variables and Z has finite variance. Consequently, X L Y Z. Let 9n and G2 be the classes of linear regressors with no intercept, i.e.,
G1 = (g)
3.x + 3.z 9a, E R} and G2 {gx(2)= = B2 E
If E denotes the mean squared error, we have that Ep [[fg[ggp( (2), Y)] EpiElgi (X, Z),Y) > 0 because the model class G2 misspecified, that is, does not contain the Bayes predictor given by the conditional expectation Ely Z).
Example A.2 (Powerless test). Suppose Y 7 sin(X) + Eyy where Z, X, 4d N(O, 1). Conse- quently, X L Y Z. Define Gi and G2 as in Example A.1. If denotes the mean squared error, we have t Ex(((gi.p Y)] Bp[((gi, p(X, 2), = even though the different Bayes' predictors have a difference in performance. This happens because the model gi.p is not close enough to the Bayes predictor Ey | X, Z].
A.3 Generalized Covariance Measure (GCM) test
In the GCM test proposed by Shah and Peters [31], the expected value of the conditional covariance between X and Y given Z is estimated and then tested to determine if it equals zero. To simplify the exposition, we consider X and Y univariate and work in a setup similar to the STFR's. (X, Y, Z) P, the GCM test relies on the observation that
always write
x fi.((Z +e and Y = (2) + 7.
11 See Section 3.1 for more details
Because Er[x) Er[X]] [r Br[X 0) 0.
14

---

where (2, = Ep[X 2 and [2, = Bp[y Z] while the error terms {e. 1) have zero mean when conditioned on Z. Consequently, we can write Ex(Covp(X, Z) Ex To
estimate [Pp[oov((X) Y Z]], we can first fit two models gimm) + X' and 92 ((m) Z + V, that approximate fi and fi using the training set D(r") and then compute an empirical version of Ep(er) = -Ee((X - fi,(())(( [2,,(2]) using g ((m)) (m))) and a
In the GCM test, we reject He X Y Z if the statistic r(n.)) & |VTTT(n.m) jā (((mm)) exceeds Ta/2 A (1 - ax/2,, depending on the test significance level E (0. 1). Here, T(m.m) and ā ((m.m) (Z:)).
are defined as in 3.1 with z.mm A (X, p(D!") D D(m)) 2(1 ((T(nm)))) the test PaCM(D) ,D(")) is analogously given by Equation 3.2. Like the STER, the GCM test depends on the models' classes and implicitly on the training algorithm. If the limiting models gi,r and 92, not p and p, then Type-I error control is not guaranteed.
(2.)) (Z))) If the p-value is defined as
We introduce definitions and assumptions. Assumption A.3 gives a rate of convergence for the models 0 in the mean squared error sense. Definition A.4 gives a definition for the misspecification gaps. Assumption A.3. There are functions gi.r, 92, p. and constant 7 such that
EP [10] (0) (Z) - (Z)) p = Op(m0')mm))))))ppppp) for = 1,2
Definition A.4. For each j [1,2), define the misspecification gap as م - 93, SJ
In the next result, we approximate GCM test Type-I error rate and power using the gaps in Definition A.4 and Assumptions A.3, 3.2, and 3.3 applied to this context.
Theorem A.5. Suppose that Assumptions 3.2. 3.3, and A.3 hold. If is function of such that n + do and n = o(m") as m + oc, then
(e((aaM(D D(r))) ] = & Fa/2
GCM o
1b
Ta/2
V o
20C (())
where o(1) denotes uniform convergence over all P E P as and 2 CCCM Ep(Covr(X,Y 2) + Bpl (Z)62.
From Theorem A.5, it possible verify that if (2, zero for at least one j E (1, i.e., if at least one model converges to the conditional expectation, the GCM test asymptotically controls Type-I error. This can be seen as double-robustneet property of the GCM, which is not present in Shah and Peters [31]. If Ep P (2) * O. then Erly 8CM (D(1) D( > as w -> oo even when Ho X IL Y Z. Under the alternative, if 12 o 0, Type-II eтror approaches 0 asymptotically.
A.4 REgression with Subsequent Independence Test (RESIT)
As revisited by Zhang et al. [42], the idea behind RESIT is to first residualize Y and X given Z and then test dependence between the residuals. It is similar to GCM, but requires the error terms and to be independent. When that assumption is reasonable, one advantage of RESIT over GCM is that it has power against broader set of alternatives. In this section, we use permutation test [18, Example 15.2.3] to assess the independence of residuals. We analyse RESIT's Type-I error control.
If (X,Y, ~ P and (X,Y) can be modeled as an additive noise model (ANM), that is, we can write
x = fi, +e and Y= = (Z) 7
(A.1)
where (Z) Ep[X| | 21, (2, Ep(y | 2), and the error terms (c, are independent of Z. is possible to show that X LY 1 +> c 1 n. To facilitate our analysis we consider first fitting two models g((") and g((")) that approximate fī.p and fī,e using the training set D( and then test the independence of the ! & X; g (2.) and i Y; "(5)) (Zt) using the test set D(a) Define (i) (2, n) & {(,, {= (test set residuals vertically stacked in matrix form) and (ii) (2, f)
Thiis property is clear in our result because we consider data splitting. "In practice, data splitting is not necessary. However, this procedure helps when theoretically analyzing the method.
We omit the residuals superscript to ease notation.
15

---

as one of the B permutations, i.e., consider that we fix and permute v row-wise. Let w be test statistic and v((é. and (((e, () its evaluation on the original residuals and the b-the permuted set. If the permutation p-value is given by
1 1+ 1 ( )) 2 (((é,)))
p(D D(
(A.2)
1 B
test &a aiming level a E (0, 1) is given by Equation 3.2.
Similarly to STFR and GCM, we consider gi.r and g2.r to be the limiting models for 01 ((m) and gfm) Different from GCM, both models gi and 92, P multi-output since X and Y not necessarily
univariate.
Now, we introduce some assumptions before we present our result for RESIT. Assumption A.6 gives rate of convergence for the models 9)m) in the mean squared error sense.
Assumption A.6. There are models gi,r. F2.r, and a constant 7 > 0 such that
Ep |1 (2) 93. 02,((2 D(m)) Op, 7) == 1,2
Assumption A.7 puts structure the distributions of the error terms (c, and is mild assumption.
Assumption A.7. Assume that for all P E Po, the distribution of (c,n), Puay is absolutely continuous with respect to the Lebesgue measure in IRxx x Rdy with L-Lipschitz density Pa,, for a certain > That is, for any ex, ez B and hu, lva Bdy we have
|penlei, hi) -eennee (ennle,,aa))) L Llleee, h1) (e2, h2)l12
We assume that L does not depend on P.
Assumption A.8 states that some of the variables we work with are uniformly almost surely bounded over all P E Po. This assumption is realistic in most practical cases.
Assumption A.8. There is bounded Borel set A E B(R'x ((y) such that
inf PP ((X,Y) EA) PEPo
and
inf inf Pr ((o A) 1 PEP691.99
Here, inf is taken over the model classes we consider (if the model classes vary with m, consider the union of model classes). In the following. we present the result for RESIT. For that result, let: (i) e" å e ((x)) and n" $ 7 d2, where the misspecification gaps are given as in Definition A.4; (ii) drv represent the total variation (TV) distance between two probability distributions [36]; and (iii) the superscript e.g., in P represent a product measure.
Theorem A.9. Under Assumptions A.6, A.7, and A.8, if Ho X V Z holds and a function of oc, then
such that and o(m
Ep Erlp
RESIT (n) D("")) < a (in of Ph d.d P...)) p..,)) + +(()
where o(1) denotes uniform convergence over all P e Po as + oc.
see that if at least one of the misspecification gaps 81, or d2, is null, then E RESIT (D(m) D(m")) < under Ho X Y Z. This can be seen as a double-rabusiness property the RESIT. If none of the misspecification gaps are null, we do have any guarantees on RESIT's Type-I error control. It can be shown that the proposed upper bound converges 1.
From Theorem A.9,
16

---

A.5 RBPT extra derivation
Let μu be dominating measure of Qxiz and 2xi2 that does not depend on Z. Let 4xi2 (resp. px(2) be Qxi2 (resp. 2xiz) density with respect to μa.
(f ob(z, 2)1Qx) - (f) 2)
ROPT Pp1
Ep 8
/ gp(z, 2)d((12(x)) / gr(2z 2) 2)dPxiz
$ L Ep
/ g 2)Q0((((())
/ 2d(s,
L Ep
/ gb () Px12(=|2))d4xx
L. Ep
< L- Er
2) -xx 1
/
MT. Ep
- -xx
2ML 1117-BBldd@@xx Px1z)]
Ep|drv(Qx12 Pxiz]] - 0P2 (22L)
then
BBPT 5 0
A.6
How to obtain result for RBPT2?
We informally give some ideas on extending Theorem 4.4. Theorem 4.4 states that
Erlpa (D(() (D(")))] (
RBPT
1 Ta
RBPT
+ o(1)
V op
where S2
Spp with
RBPT
Ep [f of(2
(fot 21Qx(1(0))) Ep
and
OP2 & EE( Ep
If we wanted to adapt that result for RBPT2, we would have to redefine Q The analogue of Q for RBPT2 would be
QRRPTZ
Ep e (Er (x,( 21 Ep E(E (9P()9p(X Y)
where Ep [x, Z 2] denotes the limiting regression model predict gi 2) given Z. If we assume the existence a big unlabeled dataset, deriving a result might be casier as we can avoid the asymptotic details the convergence of the second regression model by assuming that the limiting Rao- Blackwellizztiion model, for a fixed initial predictor, is known. The only challenge is proving the convergence of Ep [ύ(X, Z) Z] to Ep [gi Z) Z].
17

---

B Technical proofs
B.1
STFR
Lemma B.I. Assume we are under the conditions of'hhrrem 3.4. Then:
( Varp (
[[(= = :o::0pp1) op(1) as m 00
Proof. First, that for an arbitrary there must be sequence of probability measures in P. (p(m)) mEER such that
sup Pp [[olamm) PEP
Var (m))
D((r)
>
S P
pim)
[(atummt) Varppm) (m))
(m²)
> 8 + 1
m
Pick one of such sequences. Then, to prove that (d(m.m))² Varp(T? it suffices to show that
(m/)
op (1) as m + oc,
P Pptm
(
Var p(m) [T(m] D(m)) >
- 0 as m 00
Now, expanding (a (2) we get
(
1
Σ T((m)
(T.(m)) Ep(m) (TT [D(
+ E Ep(m) (ppm)](TTT))) [(T(m)) D(ni)
Σ Te(me)
11
(T.(m)) pp(m) ((T(m))3 D!
Tn(m)))
B pp(m) (T(m)
D(mii)
n
T (mm) p(m) [T(m)] D((m) (B (T( Dimi))? + Var p(mp
[T(mm) (m) DD D!!"!
2
1=1
1
(2 ? E p(m) [(T(m)) D!!m!!
Σ Tm(m) E Bpim) [r(mm) D(mm))
2Bp(mm Tm ((mb 1 mm
Epens (Tim)) (D(m))
+ Var Vamp D!!!)
Then.
(g(n.)))²_ - Var [T(m)) D
-1 a n Σ
2 p((m) -E (m) (((m))
(T((m))2 - Bprms (TT(m))² Dimml]
n
n T (m) Epin) (T(m D(m)))
2E p(m) (mn)
Using a law of large numbers for triangular arrays [6, Corollary 9.5.6] (we comment on needed conditions to use this result below) and the continuous mapping theorem, we have that
Σ (I!m Ep(m)] [(T( [p(m)[(T((m))) [[(m)]] = (1)
(1 "m (m(m) - Eppm) (m(m) ()()))) o1(1)
pmmm (T)
(m)
(((r) (m))
En 7m/)) E ( (m)) D(
= (1)
(1) (Assumption 3.2)
"Because of the definition of sup.
18

---

and then
sup Pp PEP
| (f(mm))) Varp ((()) | > s P Prim
D(ro))
( - Var (T(mm) (m))
>
1 m
+
m 00, i.e.,
(a(mmi)) ( (2
D(r")
(1()) as m
00
Conditions to use the law of large numbers. Let (p(m)) be an arbitrary sequence of probability
measures in P. Define our triangular arrays as [V(m)) ]
Jssssn and (v(mm) Jisign where V/(1")
T((m) ppon (T(m) D((") and yrlm) & (T((m)²² pems [(T(m)] D(")) Now, we comment on the 1.2
conditions for the law of large numbers [6, Corollary 9.5.6]:
1. This condition naturally applies by definition and because of Assumption 3.2.
From Assumption 3.2 and Resnick [27, Example 6.5.2].
(
D(rr) (m))
[
((o)) pptm) (T! D((r)) I 2E pEpim)
[r/mm D(!") Ox(1)
E Epim)
< Ep(n))
and
((m))
p(m) ((T 2 D( =1,(1)
E Eptm)
S p(m)))
Fix any é > 0 and let & be defined as in Assumption 3.2. See that
E Epim)
1[ 2 en]
D |(!"
ppom
(/(m)
I((V) (((v))""(((e))))
1] D(!")
1
[ (D(
(ne)* Epim)
(ne)a Ep(m)
[ Epim (m) DI 1 14h D(m))
Eppm) ( [m)] 14t + Bpin)
|
D(mm)
(nc)*
(me)* Op(1)
(1)
where the third inequality is obtained via Minkowski Inequality [27] and the fifth step is an application of Assumption 3.2 and Resnick (27, Example 6.5.2). Analogously, define k' = k/2 and see that
Epccn)
(m) 12
2 en]
Eptns
((m)
1 [(VV (m))
(((en)) 2 21] D
1,2
(ne) T Pppcms
(D(T
(ne) E ppmm)
m Ep(n)) m(r(m))
D D(m))
1+K
S (ne)
Bp(m)
(T.(0m) 2(1+6))) ((o))
+ B2 Bpmm)
(T((0))) 2 ((o)))
(T((m) D(m))
E Eprn) (IT!m)) D(
B Bpim)
(nc)**
(x(1)
(ne)
(1())
19

---

Theorem 3.4. Suppose that Assumptions 3.1, 3.2, and 3.3 hold. If n. is a function of m such that " oo and n = o(m as + xc, then
Eplva (D!..) D! =
Sp
o(1)
op
where o(1) denotes uniform convergence over all P P
and
PP STER
Ep (2)) - E, P Z),
Proof. First, note that there must be a sequence of probability measures P, (p(m) JMEN. such that
EplP STER (D!a), D( } - 1 1b To
STER S2
ppm) (Pa
STFR
(D D( - 1 1 To
STER 2
sppmm
+
PEP
0 ppcm)
Then, suffices to show that the RHS vanishes when we consider such a sequence (p(m))mEk.
Now, let us first decompose the test statistic (m,m)) in the following way:
(nTmm))
(mmm)
Vn ((),m)
pp(m) (T(m) ((()))
VnE pemo (T(m)) (D (m) ((r.))
((m.m
v (m.m))
E Ep(m) [2(m) (
@(n,m;
E Eptms (1(02 (m)) (2)), Elog p(m))
plmm) (Zz), Yi) D(mm)) (BBp(m) (( Z1). -(0 (X1, Z1) D!!"
((n,m))
T (ppm)) (0(g)) (Z1), vi)l - Eptm) (C(g] (((g) (X1, Yi)l
+
6(n.m)
V7aW(m) (m)
Vmw-(m)
VnsssT p(m)
1.P(m)
2.P(m)
((u.m)
((,m)
(m.m))
Given that is function of m, omit it when writing the W(m) 1.pims 's. Define
pp(m)
(m)
A
Var 7((m) ( and see that
Epini (pa ( (D(a) )( p(m) (p(2(()) ( al
1 +b (A (n.m)
Ppmm)
S
P p(m)
A (m.m) Ta
VnW (m)
Vn) 2.P(m)
STHR pim)
1.p(m)
P p(m)
m(r,m)
g(n,m)
((,,m)
To
(m)(mm) 1.P(m)
Vnl 2.P(m)
VISLSTER p(m)
② (n,m)
p(m)
To
Ta
p(mn)
pp(m)
0 p(mm)
Opim)
VnW((m)
Vnw((m)
IP p(m)
1.p(m) o p(m)
pp(m)
pp(m)
2.p(m)
To
[(m) (m)
(m,,))
pp(m)
p(m)
To
STFR SIFR p(m)
p((m))
p(m)
p(m)
To
2 p(m)
STER
+ +o(1)
(B.1)
Because of the definition of sup.
20

---

Implying that
sup
Bp (D(a) D(m))) 11 + +
STIR
Ta
o(1)
PEP
op
Justifying step B.I. First, from central limit theorem for triangular arrays [6, Corollary 9.5.11],
have that
Wr(m 1,p(m) v
((nm.)
Epimi [1] (m) ((m) (m) p(mn)
(D(m))
)
T (m)
B8 p(mm)
(2)mm
(
vn
N(0,
(mm)
p(m)
p(m))
we comment on the conditions to use this theorem below.
Second, we have that
(nW(a) 1.P(m)
Vew (m))
(m) ppim)
(n.m) (m)
1,p(m)
2.p(m)
plm)
p(m)
(mn)
p(m)
ppmm)
+
pptin
Ta
Ta
p(m)
(mx)
2 pp(m)
pp(m)
[m]
1,P(m)
(p(m)
(m) prmm)
Vnll(m))
Op(m)
p(m)
Ta
Ô (n.m)
(m) p(m)
o
p(m))
p(mm
[m)
-1
(m) pp(m)
-1
Ta
(n.m)
(m) p(m)
=1p(1) as m -> 0
To see why the random quantity above converges to zero in probability, see that because of Assumption 3.3, Lemma B.I, and continuous mapping theorem, we have that
8 (n.m)
(1))
1= (1) and
=1= (1( as m + cc
(m)
O p(n))
p(m)
Additionally, because of Assumptions 3.1, 3.3 and condition o(m²>), have that
Vnlll)) 2.p(m))
1o(m")0ppm
(0(m")0,(mm
(1)
pim)
pp(m)
infrePop
Finally,
(m)(m) (m)
Vnw((m) (,p(m)
(n.m)
(m)
((m)
p(m)
p(m3
p(m)
(m)
p(mm)
T p(m)
Ta Ta
pimm
(m)
Tp(m)
Vraw-m)
1.P(m)
(m))(m)
I.P(m)
Vni((m) (m)
1,p(m)
p(m)
(mn)
VnoW
2.P(m)
(m.m)
p(m))
(m))
plm)
(m)
(m) plmm
p(m)
(mn)
pp(m)
ppmm
+ To
To
(m)
p(m)
(m))
1.P(m)
+o,(1) 1).
(m)
p(m)
by Slutsky's theorem. Because N(0, is continuous distribution, we have uniform convergence of the distribution function [27][Chapter 8, Exercise 5] and we not have to worry about the fact that
Vussiaa
p(m) depends on m.
Te
plmm)
Conditions to apply the central limit theorem. Now, we comment on the conditions for the central
limit theorem I6, Corollary 9.5.11]. Define our triangular array (2(m) where y:(m)
mo(m) m3
p(m) (r. [p(
p(m)
1. This condition naturally applies by definition and because of Assumption 3.2.
2. See that, for any m, we have that
E Ep(m) (m)y2 D(
21

---

3. Fix any > 0 and let & be defined as in Assumption 3.2. See that
Eptn)
2 end D(
-Epto)
[ 2 11 (m))
$ (me)t Bp(m)
1
[ 2+) D!
Tm p(m) (T(m)
D(m)
124
(me)a P.p(m)
1
((m))
{ B [IT (
D((m))
2+r
+ Epim)
(1nmimg D(
2-
(ne)*
(o (om) )a4k
(( 2+t + +bp(1) { Epim)
p D(m))
27x
E ppm))
[TT-||| D(mm)
2+
(ne)*
1
(in[PePOp)2tt + t00(1) 02(1)
(ne)*
O₂(1)
(mE)*
=1)
where the third inequality is obtained via Minkowski Inequality [27] and the last inequality is an application of Assumption 3.2 and Resnick [27, Example 6.5.2].
Corollary 3.6. Suppose we are under the conditions of Theorem 3.4.
(Type-I error) If Ho : X L Y Z holds, then
STER Eplpa (D) (1)) (Tm)) x + Tu
D..
+ +(1)
o
where (1) denotes uniform convergence over all E Po as m + xc.
(Type-Il error) In general, we have
1 Eply SHE (D( (m)) s Φ
(Ap (Ap- A1,e)) o(1))
To
op
where o(1) denotes uniform convergence over all P and AP R=((((f.r(()))) (x, Y)).
Proof. Under the conditions of Theorem 3.4, start proving that
1. Ap AI, & QASEER holds;
Under Hu, 2TST < Ag,p holds.
For (I), see that,
2 EE((( (X, Y))
(2
+ (,, P).
2 Ep(e(fi,p(X, -X
Ap-A1. A1,
22

---

Now, for (2):
(2) (x, 2)
[2) (p) V)]
[r((((ii((x,2),)) - Brll(ii,r( 2),
(<
[p((((f2((2)))) (x)
(= 0, because Ho holds)
3 (p)) (2),
A2.r
Finally, see that
Ta
$
To
12.r
op
and
71
n
11
oz
Combining these observations with Theorem 3.4, we get the result.
B.2 GCM
Theorem A.5. Suppose that Assumptions A.3, 3.2, and 3.3 hold. If is a function of m such that n 00 and n = o(m?) as m -> oo, then
Erlya 2CM (D(2) D(T)) )
Ta/2
GCM
-Ta/2
2
+o()
op
where (1) denotes uniform convergence over all m + and aPC Epp(ovp(XXY Z) + (2)6
Proof. First, note that there must be sequence of probability measures in P. (p(m) MEN. such that
Ep Iya (D(") (1) D(1))) 1+ Ta/2
GCM
Stp
+ Ta/2
o%
1 oz
PEP
E Eppmy (CM D(m))] +
GCM
1
Ta/2
-Ta/2
p(m)
ppim)
p(m)
Then, suffices to show that the RHS vanishes when consider such sequence (p(m)) mee.. Now, let us first decompose the test statistic p(n.)) in the following way:
(n..m)
(m.m)
(m,m)
Vn 7 m))
E Ep(m) (T(m) ((fr))
/ /nE /nmp (m((m)
((m,m)
(n,m)
(()m)
E. Ep(m) (T((m) D(m)))
/TE pm ((05 (mmm)(())) (Zi)
(Zi))(E{ (Zi) (Z))
92 (Z1)) (Z1)) D(m))
g pim)
(().m)
δ ((..)
p(n) [[g] (m) (Z1) -i p(m)
(2)) 22, (21) D(mm)
VTBppm)) 1 (Zi) (m)) (Zi) 92 (21)) D(
G(n.m)
m(n.m)
Vnn2CM g(a,m)
(m)
(m) (m)
(m) 3,p(m)
(on) 4,p(m)
CCM p(m))
(,P(m)
p(m()
(n.,0)
((..))
mtn.m)
(n.m))
18 Because of the definition of sup.
23

---

The terms involving one of the and y were all zero and were omitted. Given that n is function of mi, we omit it when writing the W(m) s.p(m) 's. Define (m)
Varrpmm) (T]
D (m)) and see that
pim)
Erlpa a (Die), D!
-Prlp(Di to
(n)) D(m)) (m)) $ <a]
Pp + (m)m)
0/22
Pp pp(m.) 2 Ta/2
(n)(m)) 1.P(m)
vnW(() (
VnW(m) mmm(m
vnW(m))
Vnl2ppm
Pp
4.r(m)
+
pim)
$ Ta/2 +
(n,m)
g(nm)
((n.m)
((n,m)
ő ((n,m)
VnW(mm 1.p(m)
Vnllm)) 2,p(mn)
VnWimm 3,pim)
vnl-mm)
VnS200M pimm)
4,P(m)
+Pp
((mmm)
((n,m))
((n,m)
(m,m)
((n,m)
Ta/2
Vml-lm) 1,m()
(m)
Vnw(mn 2,P(m)
Vil(mm 3,p(m)
(reW(mm) 4,p(m)
((m,) (m)
Vnitacu p(m)
p(m)
pim)
=Pr
Ta/2 Ta/2 5 -Taf2 a p(mi
p(m)
(m)
pp(m)
pim)
ppmm
0 p(mm
p(m)
(m)
p(m)
+ PP
VnW(mm
of p(m) 1.P(m)
vr(W(mm) 2.P(m)
Vnlllm) 3,P(m)
VnW-(m)
4.p(m)
(n.m))
pim)
(m)
Ta/2 Ta/2 2 Ta/2
v V GCM
p(m)
σ p(m)
(m)
p(m)
pp(m)
p(m)
p(m)
(m) pim)
p(mm
p(m)
1 db Ta/2
V of pim)
+ $
TTa/2 V po
+ oo(1)
(B.2)
Implying that
GCM Ep Eplva (MMMMMM (D(m) ((()))] 1+ 4
(n)
Ta/2
of
S2
+
(Ta//2
V
22
o(1 as m
Justifying step B.2. First, from a central limit theorem for triangular arrays [6, Corollary 9.5.11], we have that
Vn
(m)m) 1.P(m) Vn
F(m.m)
E pp(m) (m)
[T] (mn)
D(or)
(mm)
p(m)
[T
(mn)
(nn))
N(0.
(m)
p(m)
p(m)
pim)
The conditions for the central limit theorem [6, Corollary 9.5.11] can be proven hold like in Theorem 3.4's proof.
Second, have that
(m)(m) 1.p(m)
(m)
(m)(m)
(m)(m) 3.p(m)
(m)(
(n.m) o (m)
1.p(m)
(pim)
2.p(m)
4.p(m)
p(mm)
Taf2 + Ta/2 (m)
p(m)
(m)
p(m)
(m)
ppim)
ppim)
ppin)
ppims
p(m) o p(m)
(m) p(m)
vril-(m) 2.p(m)
(al((m) 3.P(m)
Vnl-lm) 4.pim)
1.Pim)
plmm)
[m]
pp(m)
ap(m)
pp(m)
pp(m)
m))
σ (m)
p(m)
-1 + Fa12
σ (m))
pim)
+ Ta/2
1
+ Ta/2
1
(m)
pp(m)
ppim)
(m) o p(m)
p(m)
opp as m
oo
and
24

---

Vnl,(m) I.P(m)
Vrew 1.P()) ppim)
Vnl 2.plm)
Vnly(m) 3.pim)
VnW.(m)
((mm) (m))
4.plon)
p(m)
plm)
p(m)
(m)
pim)
pp(m)
pp(m)
p(m)
4 Ta/2
Ta/2 (m)
o p(m)
p(m)
Vnw-(m)
(ir) p(mm)
Vwow-lmm 2.P(m)
vnw((m) 3.P(m)
vnw((m) 4.Pim)
1.P(m)
ppim)
(m)
ppmm)
ppim)
p(()
pp(m)
g(nm)
(mu)
(m)
g(n.m)
Ta/2
[mm
1) Ta/2 p(m)
p(m)
ppmm)
p(m)
+ Tn/2
(m)
p(m)
p(m)
= =0p(1) as m + 00
To see why the random quantities above converge to zero in probability, see that because of Assump- B.I, and continuous mapping theorem, we have that
tion 3.3, Lemma"
(n,m)
(m)
(m) (p(1) and plmm)
p(n)
= (1(1) as m oo
Additionally, because Assumptions A.3, 3.3, Cauchy-Schwarz inequality, and condition n = o(m?), have that
VnW(mg 2,p(m)
p(mi (Zz) D p(m) (Zi)) (T)) (Zz) pg ((1)) D(
ppim)
p(m3
nBB p(n) [19]
((g(m)(()) (2i) - p(m)) (Zi))3 D JE p (m)) (Z1) 92 p(m) (Z1))2 D!r
inf PEP op
(p(m2))
(1)
VnW(m) 3.p(m)
VnlBppm) pim)
(C0m ((olm)(2)) - p(m)) (21)) (2z) D(m))
plmm
p(m)
V /nEp p(m)
(21)
pipt (21))² D( 1 [p [6 p(m) (21))a)
inf Pnp
(o(mm))p(m=)))
inf op = =1)
VaW(m) 4.p(m)
VnlBpim (Zr) p(m) (Z1)),, (.am)s) (())) D(
plmm
① p(m)
V /nEpmm
pipp (Zi))a D("" D Eptio ((d, (Z1))²
inf
(o(m))),(mm-1)
= (1)
We can apply this STFR's lemma because it still holds when consider GCM's test statistic.
25

---

Finally,
VTlWim) 1,P(m)
p(m)
VaWlon 2.plm)
v Vnl(()) 3.P(m)
VnW
4.p(m)
o ((n.))
of p(m]
Taf2 + Ta/2
p(m)
(m))
p(m)
pp(m)
p(m)
p(mm
d [m)
p(rn) p(m)
(n)((m) 1.p(m)
I.p(m)
VmW 1,p(m)
(mn)
(m)
pim)
(DW(())
2.p(m)
VnW (m))
3.p(m)
VnW(m))
4.p(m)
δ (n.m)
Tu/2 + Ta/2 d p((m)
(m)
(m)
ppmm)
σ plmm)
pp(m)
ppim
p(m)
p(m)
p(m)
(m)
1,P(m)
+ #p(11) 1)(,,)
[m]
p(m)
and
Vn)(m)) (m) 1.p(m)
VnW(m)
Vnw(m) 3.p(m)
VnW(m)
p(m)
2.p(m
4.rlm)
x(n.m) o p(m)
+ Ta/2
Ta/2 (m)
p(m)
p(m)
Opim)
ppim
ppim)
o
p(m)
Opim)
(nw(m)
Vaw(())
VnW
(m)
VnW(m)
Vnw (m)
vnW(())
(m)
p(m)
1.P(m)
(m))
L.P(m)
p(m)
(m)
1.p(m)
pim))
pim)
plmm
2,p(m
ppim)
3,p(m)
ppims
4.r(m)
+ To.2
Ta/2
o p(m))
(msW(m)
1,P(m)
+ (101
(m)
p(m)
by Slutsky's theorem. Because N(0, 1) continuous distribution, we have uniform convergence of the distribution function [27][Chapter 8, Exercise 5] and we do not have to worry about the fact that " ppmm) depends on m. Sppm, or -Ta/2 ptm)
Taf2
plm
B.3 RESIT
Lemma B.2. Let Pu.v and Po,y be two distributions on (u x V,B x VJ), XXV S Rdy with du, dv 2 Assume Py and P/2 are dominated by common o-finit measure μ and that Pviu== Pviu=u is dominated by a-finite measure Vn. for all E Rdu, Then,
drv(Pu.v Pl.v) dru Pb)
where dyy denotes the total variation distance between two probability measures.
Proof. Let pu and pu denote the densities of Py and P/ w.rt. μ4, and let ( denote the density of Pviu== = PVIe= w.r.t Vu. From Scheffe'ss theorem [36][Lemma 2.1], we have that:
drv(Pu,v, P(.v) 1/ (w) u) p' (w)pvja u) del (v)dp(()
2 / (/ lev lev wilde(()) Ioo (u) (w)((((()
/ / (ʃ (fviuoll
w)dun(u) [ Ipu (u) - (u)(dp())
ʃ (po(u) - pu (u)ldu(u)
drv Pt)
Lemma B.3. For all i E (n), consider
(Ee, (c) D(m)) P. Peeopp(i)s (es,f.) D!m)) ~ ~P <.opp(?"s (ê,,)) D(!)) (.enDD(m))
where é, = (6,,((2))
(01" (Z,) - ((..r( and ft = m 62,p(Zt) (85") (Zx)
(Za) - - (Z.)
26

---

Under Assumption A.7 and Ho : X IL Y Z, we have that
) Eplp. RESIT (D! D(r)) | | S a + min { drv (P" ((iDD!m)) P (mp ,drv drv (P (oliimm Par (mpp!m))
Eplp-
where dry denotes the total variation distance between two probability measures.
Proof. Let us represent the stacked residuals (in matrix form) as (é, () = {(ēi, H.) See that
(2. (E, ()) (e, f) (E, 2/."))
((e.)))) (e, (e. (c. (c. m) D(r
Then, because the random quantities above are conditionally discrete, their distribution is dominated by a counting measure depending on (E, 77). Because the distribution of (e, 7) is absolutely continuous with respect to the Lebesgue measure, (f) D(T)) and (e, D((") also absolutely continuous for every training set configuration, and then we can apply Lemma B.2 to get that
drv ((c. i). (E, (E, ()) .... (()))) D ((e, f) (e, ()) ... (e., (c..))())) D!!T) drv (E. D/T") (c. n) D(!))
In the last step, we abuse TV distance notation: by the TV distance of two random variables, we mean the TV distance of their distributions.
Now, define the event
Aa $ ((e,)) (e.,(e)))))))))))))))))))))))))) 1+ [V((e,))()) 2 (((e,))) sa
1 B
By the definition of the TV distance, we have that (under Ha): Er Ey RESIT
(D(2), D(r)) D( Pr (()
(B)) E Ao D!!m))
S Pp ((c, (c, (c, ") ( 7) E Aa (D(m) + drv (c, ( (m)
S + drv (2, f) D(m)) (c, D(m))
=a drv
(pm (. <.ipp(m)))
p"
where the last equality holds from the fact that, given the training set, rows of (ē, and (e, i..d.. See that Pr ((c, f). (c, ...., (e,
(B) Aa D(()) I a because Ho holds and therefore
L vi D((") (making the permuted samples exchangeable).
Using symmetry, we have that
RESIT (D("), D(m)) "((") <a + min drrv (pm (miii! Pe ("MlD!m))) ,drv (pm Colplmys Pn (mmp)))))) )
Eplpa
Lemma B.4, For any i E [n], consider that
(2, D(m) P (crr1)) D(()) P papp) (E,,)) D(m) P enjppt
(c),1)) ~ Perant, (c.,1) ~ Pent; (c). ~ Per
where & = 6 (2,) (((m)(()) - (Z.) c = 6, - d1,((Z)), G: = = 82,r
( 95, (Z.), and nī (2,) Then, under Ho X 1 Y Z and Assumptions
Givvn any training set configuration, the vectors (ês, 9.). (e,, fj.), (é,, m) are given by the sum of two independent random vectors where at least one of them is continuous because of Assumption A.7 and therefore the sum must be continuous, e.g., (&,, f)) = (c., m))+ ((i g(t) (Z,) ((:)), (Z.) -Z:)- g (Z.) 82, (2.)). See Lemma B.4 for proof.
27

---

A.6 and A.7, all six distributions are absolutely continuous with respect to the Lebesgue measure and their densities are given by
PrrniD(m (e, D((r)) = Er Pe (e+ t 9i.r(2))
pr (h (2, + 1 (Z) (b.r(2)) D((r))
P Pe.n/D/mm (e, / D((r)) p.(e) Ep pyy (h 12 + |/2mm (2) (2.r(2) D
Panii(/om (e, h. (m)))) Er Pe (e (e+ (1. + 01 (m) (Z) li.)(Z)) D(!r) (h)
Pei,n" ht) Ep (pe (e + 61,r(2)) pr (h + (2,)(
Peat (e, P1) p-(e) Ep la (h + (2))
(e Ep jo. (e + òn p(2)) ph(
Additionally, we have that
sup (a.))Rd kay (Pr.aIgsmo (e, D(m))) - Pc of (e, (e) = (mm(m)))
sup (e.))c2dxxdy xay (PewsIrs,,s (e, ((())) - Pen (e, (e)
(m)(m=))
sup (m6))="*xdy xdy (pempp (e,h D(T))) - (e) -po(m
Proof. Assume we are under Ho. In order to show that P p./p is absolutely continuous w.r.t.
Lebesgue measure (for each training set configuration) and that its density is given by
Panppims (e, D(()) Er pc (e 51, + ))m)(() ri,r pr (h 62, + gp (2,r(2)) (((m))
suffices to show that
Pp((e, A A(D(
= = U)Bp (pc (u+ +z) -2)_()))(((1)) pa (u+ (2) + gir(2)) D!m!] d(u, v)
for any measurable set A. Using Fubini's theorem, we get
Pp((é, 1) A ((
= EEp
La(e- - 61.((7) (m) (z). (i) 8
81 92) pZ)) D(T))
Ep
(m) ",
1 -
h) ((m)
ʃ 1 |,
Ep
Dim))
/ La(u,U)p 1 ( Pr v (2+ (2) 1
- -2))())))) d(u, v) D(m))
Ep
=/ L)(u,))Br (2 ا ri) Pr (1 1 (2)+) + -grr(2)) D! d(u,))
The proof is analogous to the other distributions.
28

---

Now, we proceed with the second part of the lemma. Using Assumptions A.6 and A.7, we get
(Penn (e, (( Pe pe (e,.n
[Ep =Epp
(e (1))) + 81 (Z) - gi.r(2)) (1+ (2, (2) + (Z) - (2.r(2))
)2,r(()) 1)
Pe (c +lc+d1,1 d1.r
S 1.?
Ep
01 (Z) si (i( (Z) - (z)
|1, (D(mm))
L
Ep
(1 ( (Z) 0i(2))02 (Z) (
11 D!
L
[10m)(() 01.r(2) D(m) E3
||of5)
r2,(() D(!))
-O (m
where the last inequality is obtained via Jensen's inequality. Because the upper bound obtained through Lipschitzness does depend on (e, h), we get
(Pa.sI((m) (e, D("")) - pe (e, 11)) Or (m²))
sup (e. xdy
The results for the other converging quantities are obtained in the same manner.
Theorem A.9. Under Assumptions A.6, A.7, and A.8, if Ho X 1 Y Z holds and n is a function of m such that n + co and n = o(m as m + oc, then
Ep(pa RESIT (D(a) D(r))) I a min pr Par
where o(1 denotes uniform convergence over all E Po as m co.
Proof. We are trying prove that
Brle (D(=), D(r)) (p drv P P.) o(1)
sup PEPp
00
First, see that using Lemma B.3 we get
Ep lFa
RESIT (D(a) (((r))
Ep Ep[Bp[p. RESIT (D(a) D(m))) D!
< a Ep min div p (mlppmo pm
div (PinIDgo)) P" (
< a min
Ep div (pn siiiiti pa (mip(!)))
Ep div (pm (aiDsm Pm [m)p("))]
5 a min
Ep drv pm Enippmm pa ((lD()))) )
(p drv m: P
Ep drv pm Ciippro (nii((m))
pa
drv . + drv ( , Po Po..))
p { E (dvv (pn emppfn (mp)(())
5 a min
d P(,-))
P,
Ep div (pm fisipmm) pa (hippgo:) div(PP PP drv Pf PP..)
and
RESIT (D(a), (D( (P PP
P mw]]
sup 1(m)
sup PEP4
PEP
(B.3)
29

---

where
A (m) A min
[B [div (pr pog P. [:sip!m)) div (P (r ) mr
Er drv (pn (EMDDtt P. (iID)( )]
+ m Pa
min(drr(PPo..)) ). dTv P
It suffices to show that PeP Amm) o(1) co. Next step is to show that
sup
Ep drv (p ( pm (AID)())))
in P...') o(1)
PEPo
and
sup
Ep drv (PT, (aiDim P
drv P o(1)
PEPa
+ 00. Given the symmetry, focus the first problem.
By the triangle inequality, we obtain
(PT ("Eii p ("ilD) ]] Ep ddvv (pin pfa + (P ddrv (Pen.. P" ((ip)
Ep drv
and consequently
Ep ddv pn (mgpo(e> p [csio[mo)] div (p s piny))
sup PEPp
s sup Ep drv pnn Peippmis P Po.n)) + sup Ep dTv (pn (eAipso Pe PePo
PePo
We treat these terms separately.
(I) Consider sequence of probability distributions (p(m) Jen in Po such that
sup Ep ddv (1")) m())) P )] Bp(n) (drv (plm)r EnIiD!
plm)n
en m
PEPo
Here, the distributions P and p(m) determine not only the distribution associated with D(TT)) but also the distribution of (e, ""n"). :n"). Because we have that
pm (PeA)ifmi) P...)) drv
n div (P: (Pr.IDD(m) .e....))
(Subadditivity of TV distance)
a / | ( (e, D(m)) Pe (e) (e) d(u,
(Scheffe's theorem [36][Lemma 2.1])
2
VV
(u.))RR<x xdy Pasipp (e, h D(m)) - Pe (e, hi
(Assumption A.8)
sup
2
n 22
1/2
(e ( - pe- (c,
sup (mx))xdxxdy,
(m))) 1/2
(Lemma B.4)
(1)
where V is the volume of ball containing the support of the RVs (existence of that ball is due Assumption A.8), we also have that dry (pin) (())(()) p(m)a o,(1), when 2fT") samples come from the sequence ( (p(m))mex. By the Dominated Convergence Theorem (DCT) [27, Corollary 6.3.2], we have
sup Ep (drv (pm (impppms P. (r s Epin) [div (ptm)n PePo
p(m) " enjlD//))
(-."r)) m
=(()
30

---

To see why we can use the DCT here, realize that when samples come from p(m), w(m)
drv (p(m)r e.Ipffr,, pfm) et,n") can be seen measurable function going from an original probability space some other space. Different distributions {P(m)) are due to different random variables while the original probability measure fixed. Because that,
ddvv (p(m) (mID()) p(m) "i.m = [w(m]]
pp(m)
for the bounded random variable W(m), where the last expectation taken in the original probability space. We apply the DCT in [(m)).
(II) Following the same steps as in part (I), we obtain
sup Ep drv (P" <.)))/))) P..--)
)] o(1)
PEPO
Going back to step B.3, consider another sequence of probability distributions (Q(")))ev in Po such that
sup A (m)
(m² ((m)
P
PEPo
where
(m) ((m) =
min
|Ragios drv (o (.)p)(m)) @ (m)"
"("",,,)i"" ,.i)/((m) )] drv (Q(m))
Q(m))
"n (m)) ",-) ) + d)v(Q(m))
"Ti , Q(mja k.y )
Bagims drv (Q(m)) fnpptm) (
(mID((m)) (m)
drv()(m))
"nnp "nnn , (m)) x.,0) ) drv " Q ((m)" "",0)
(m)))) "" Q(m)" enn dTv(Q(m)) (m) .n 1.r, (m))
Because of continuity of min and
Ep (drv (Pe p PM (mppp( div(Pe P(,.)) ) o(1)
sup
PEPo
and
Ep drv (pm (AnDD
pn (wiDD(m)) ) div(Pr (Prr.n", P p = o(1)
sup PEPo
we have that
(mL) Q(m)
min min(drv (Q -m Q( (mm)
---)) + o(1), (m)
" (mm) Q(m)) -. +(1))
min (mn(ddi(QQ (m))
(()) (. d,vi(( mm)
S0m)o (m)) ",,
min(drv (m)
cip (m) ",, dny.),dv(((Q))) (m)
cnp (m) Q(m))" )}}
en min (dinndvv(2))) (m) ((m)a
am ) ( (m))
c ((m) ( + o(1)
o(1)
Finally implying, from step B.3,
Erlp
RESIT (D("), D("")) (P ). d Pb.n)]] o(1) as 00
sup PEP
B.4 RBPT
Theorem 4.4. Suppose that Assumptions 4.2, 4.3, 3.2, and 3.3 hold. If n is function of such that n + oo and o(m") ) as m + oc, then
REPT (D(N) D(m))) = + Erke
Ta
QRBPT
+ o(1)
op
31

---

where o(1) denotes uniform convergence over all P' E P as m
and
OREPT Stp
with
SP Ep & (f ((00te)22002x)et)..)) - -e
and
RBPT PP222
- Ep (
Jensen's &
Proof. First, note that there must be a sequence of probability measures P, (P(N)))EN. such that
sup PEP
RDPT Ep Eplpa (D(()) D(-")) ) -1 1
St
RDPT
(o (e (((()) D(m))) ) $
V
Vopc ppm)
/
St
RBPT ppmm
1
Then, suffices to show that the RHS vanishes when we consider such a sequence (pfim)mEx. Now, let us first decompose the test statistic = in the following way:
(m.().))
)n.m))
vn (().m)
Epin)
(T(m) (D(m)))
Vn p(m) (T(m))
(D(
(n.m)
(a.m)
Vn (n,,))
p((m)
(T(m) (((m))
nE pim) [e(h (m) (1)) Vi) ((g(m)) (X1, 21), D(
(n.m)
((u.m)
v (m.m)
Ep(m) [2] (m))) (D(m)))
/TEp(m) (()) Z1 Zi)d (m)
x1z (x), - ((G(m)) (X1, 21), (((0))
@n,m,
m(n.m)
Vn ((n.m)
Epims] (T(m) (D(m)))
(m.m)
VnE pim) pelEpmmm[[f g (m) (x,
((m) (zx 1
@(n.m)
VnB [8[ g (m)) (x, Zz) (1)dQ((z())) Yi) {[ Sp(m (2. Zi)dQ' ((m)
g(n.m)
/nEp pe (X2, Zz), Y1) (m)
(m) (m,,, Zz), (x), D(!))
g(n.))
J(mmm E Ep(m)
[e(ʃ 9 9pcm 21 )dQ (102 -e(
spems ) 9pems
(2, Zi)dkkm) (x), Y)
[e(
Spims (1, Zi (2),
llgp(m (X1 (X1, (x,, 21),
(n)(m)
1.p(m)
V(l((m) (m,m)
2.
Vnl(m)
3.p(m)
vnw(m) d.p(m)
Vnst p(m)
+
((n.)
g(n,m
6(n.m)
6(n,m)
Because of the definition of sup.
32

---

Given that n is a function of n. we omit it when writing the W
S.p(n 's. Define (in)
p(m)
Varpom ((m) [ and see that
Ep(m) (Pa
RBPT (Die), p(
(B.4)
P p(mm)
(p(
(n) D(m))
-Pp(m)
① mm)
P((m)
(n.m) To
VnW (m)
(wWW(m) 2.p(m)
Vrellm)
Vns2 p(m)
1,p(m)
3,p00)
4.p(m)
p(m)
((n,m)
((n,m)
@(n.m)
6(a.m)
6(n.m)
Ta
(m)(mm) 1.P(m)
Vml((m) 2,P(m)
(iww(m) 3,p(m)
VroW((m) 4,P(m)
VnS2ppm p(m)
(n.m)
P p(m)
To
Ta
pim)
pp(m)
pplm)
p(mm)
pp(m)
p((m)
VnW(mm)
1.p(m) p(m)
VnW(m) 2.p(m)
(nw(m)) 3.p(m)
VnW(m)
4.p(m)
+ (n.m) o p(mn)
V REPT p(m)
P p(m)
2
(m)) p(m)
p(m)
p(m)
pim)
ppmm
(m) p(m)
ppmm)
p(m)
Ta
GRUPT p(m)
+ +11
(B.5)
Implying that
sup PEP
Eplya
RBPT (D(a), (a((a D(mi))
1
SP op
n
RBPT
o(1) as m
cc
Justifying step B.5, First, from central limit theorem for triangular arrays [6. Corollary 9.5.1
have that
Vn
Wr(m) 1,m(m) v
(m.m) Epimi (T(m)
(m) (m)
(((m)
(m))
E
Bpin (m)
(mn)
N(O, 1)
(m))
Vn
p(m)
p(m)
p(m)
The conditions for the central limit theorem [6, Corollary 9.5.11] can be proven to hold like in Theorem 3.4's proof.
Second, we have that
(n)((m) 1.p(m)
Vnwiim)
1.p(m)
(m)
p(m)
Vnl((m)
2,p(m)
VnW(mm) 3.pkm)
VnW((m)
4.p(mn)
(n.m) o p(m) To (m)
+
+ To
(m)
p(m)
(m)
p(m)
plm)
ppin)
p((n)
ppin)
o p(m))
pptm)
VraW(m))
(m) pimm)
(m) 2.p(m)
(m) 3.P(m)
(m)
1.P(m)
4.p(m)
(m)
ppim)
pplm)
pp(m)
pp(m)
(m.m))
о p(m)
(m)
-1
+
(m)
p(m))
-1
(m,m))
-1
(m)
p(m)
ppim)
Op(m)
o p(m)
(m)
(1) as m + 0o
To see why the random quantity above converges to zero in probability, see that because of Assumption 3.3, Lemma 1. and continuous mapping theorem, we have that
I (n.m) - 1 (1) and p((m)
(m)
pim)
- 1 = op(1) as m co
(m))
p(m)
Additionally, because of Assumptions 4.1, 4.2, and 4.3 and condition n = o(m"), we have that
We can apply this STFR's lemma because it still holds when consider GCM's test statistic.
33

---

VT
W W(m) (m)
vn
e {f mm (x, Zi)d (00) (1).
-( (1,
D(
E p((m)
2.p(m)
p(m)
p(m)
vn
E Epim)
1
( gmm) (a, (1)d 21)d (x).
( (f (x. 21 21)d2xx (2),
D ((m))
p((m)
LV
pp(m)
||/ glmi (x,, 21)d / g(m0 Zi)dQx (3))
(
p(m)
L/n
Ep(m)
glml (xr, 2i)d / (x))
Zi Zi)d
(D( (m)
p(m)
LV
1 1om (or, zi)11, 10 (x12 |
Eppm)
plim)
LM Eptm) If (x)) 2) - exx2 (x) 2)(d D(())
plim)
2LM /n Eppm) (drv(2
(m)) x/2 2x12) D(
infrEPop (o(m²))0p(m -21) 2/22
2LM
o1(1)
vn
((m))
B Bpin)
[
8 (m)) (a, ZidQQ' x(0).)) - (f Dirims (xc, Zi 21)dQx12(0))) D((.)
p(mm
p(m(m)
vi
Epim>
e
(mm) (z. Z1) 21)0(x12(()))) -e (foamm (z. Zi)d x (2))
D(m))
plan)
LVT
g(m)) (xx, Zz) Zz)dQ'i / Opcms (2r, Zo 21) D(m))
B.ptm)
p(mm
LVn
Ep(m)
gim) (a., Z1) spmm (z. Zi)dQxxxe 12 (2r)
|D(
p(()
Lvn
Bp(m) / ( (xr, Zz) - gprm (z. 21)
<
dQxi2 (x) (
plmm
Lvn
[ (m)) (1) Spim (z, Z1
dQ'iz (x)dPxx12()) D(m))
Ep(m)
p(m)
dl'xiz
LVT
|1 (X1, 71) 9p(m) (X1, 71)
dQ'xzz (X1) D(())
Bppm))
p(m)
dPxiz
Lvn
E Ept(m)
(m) 7n) gpmm) (X1, 7i
/|3 2
Epp(m)
dQxiz
(xi)
)7)
1/2
plm)
dPxiz
LVi
E Ep(m)
2 | (X1, 71) sp(m) (X1, Z,)
((m)
Ep(m) /
dd'x2z
dPxiz (c)))(23/2(())
)) 1/2
plm)
LVJ
Ep(m)
[10(m)
(xim)((1,22) (X1, 21) gp(m) (X1, Z7) D(m)
E Ep(m)
[x" (((xxxz1Pxx22 + 11)
1/2
p((m)
LRvT
E Epiim
(x), [1
apmm) (X,, (x1, Z,) //) D(m))
1/2
PEP
LR
(m(m)),((m=>))) 1/2
ipf
(1)
34

---

Vn W(m)
= ppim) [e (x.)) E (X1, D(
p.p(m)
pp(m)
V Bpiim) [|e (1((m)) (Xi, (x1, - (0p(m) (Xi, (Xi, 21), vi) (D(m)) (m))
ppmm
Lv
Bptm) (X,; gp(m) (X2, 21) (
ppim)
Lvv
(Eptin) (x1,)) gp(m) (X1, (x1 (((m) ))
1/2
PP
L
(o(m))0p(mm)))
onf
(1)
where M is an upper bound for the sequence (166m0(0 (2., (0r mEN
(Assumption 4.3) and R is an upper
bound for the sequence ((Eptm) [x2 (Qx1zl1Pxx) 11)1/2 Finally,
(Assumption 4.2).
meN
vnl((m)
(m)
VnWllm) 2,p(m)
(m)) p.p(m
VnW((m)
(n,,)) o pim)
L.p(m)
p(m)
4,p(m)
(mn)
pp(m)
ppmm
ppm)
ppim)
+ Ta
Ta (m)
p(m) ppmm
p(m)
Vuw(()
1im)m)
Vawlm) 1,Pim)
((m)
(m)
p(m)
(mw(m)
p.p(m)
Vnw((m) p.p)m)
Vnl(mn)
4.p(m)
δ ((,,0)
(m)
p(m)
p(m)
[m]
p(m)
p(m)
pim)
σ p(()
pp(m)
ppmm
+ Ta
To
p(m)
(m)
d p((m)
(ml(mm)
1.P(m)
0p((1) 1)0
[m]
p(m)
by Slutsky's theorem. Because ((0, 1) is a continuous distribution, we have uniform convergence of the distribution function [27][Chapter Exercise 5], and do not have worry about the fact that
p(m)
depends
p(()
35

---

C Experiments
C.1 Running times
Artificial-date experiments. Regarding running times (average iteration), RBPT took 5- 10 run, RBPT2 took 1.9s, STFR took 7.5 ss, RESIT took 1.3 10 ss, GCM took 10- CRT took 1.7 10 s, and CPT took 6.2 10 all in a MacBook Air 2020 MI.
Real-data experiments. Regarding running times (average per iteration), RBPT took 1.11-00- run, RBPT2 took 2.4 1, STFR took 10 10" GCM took 10-3s, CRT took 2.5 1 and CPT took 7.2 10010-0.0 's, all in a MacBook Air 2020 MI.
C.2 Extra results
We include extra experiments in which Y X, Z has skewed normal distributions with location J cX + Z >bbb'' Z) scale and shape 3 (shape lead the normal distribution). From the following plots, we can learn that the skewness often impacts negatively in Type-I error control.
de 30
dz- 40
D
0.02
Type-1 error rate
0.8
0.8
0.8
0.8
0.6
0.4
0.1
0.4
0.4
0.2
0.2
0.2
0.0
0.0
0.00
0.01
0.02
0.00
0,01
0.02
2
0
Y
RUP12
STR
RESIT
GCM
RBPT CRT
CPT
Figure 7: Type-I error rates (c = 0). In the first two plots, we set for RBPT, permitting Type-I error control across different dz values (Thcorem 4.4), while RBPT2 allows Type-I error control for moderate dz- All the baselines fail to control Type-I errors regardless of dz. The last two plots illustratc that CRT emerges as the least robust
this context, succeeded by RBPT and CPT.
d2
1.0
1000
1.0
Type-1 arror rate [RBPT2)
82:5 aydwe es Unllbeled
RBFT2
0.8
800
CPT
2.6
Power
0.5
0.4
400
0.4
2.0
0.0
0.000
0.005
0.010
0.015
0.020
Figure 8: (i) Making RBPT2
robust using unlabeled data. With dz 40, gradually increase the unlabeled sample size from 0 to 1000 when fitting h. The results show that a larger unlabeled sample size leads effective Type-I error control. Even though present this result for RBPT2. the pattern expected for RBPT the presence unlabeled data. (ii) Power curves different methods. compare our methods with CPT (when f 0), which seems to have practical robustness against misspocificd inductive biases. RBPT2 and CPT have similar power while RBPT is slightly more conservative.
36


Reviews:
[{"review_id": "cSEE5nzscN", "reviewer": "Reviewer_zPGB", "summary": "The paper under review offers a thoughtful exploration of how model misspecification influences conditional independence testing. The significance and practical applications of such testing are aptly underscored in the introduction. The use of a toy example to demonstrate the impact of model misspecification on Type I error is a compelling approach that effectively propels their study. However, the paper's structure could be improved for better readability. While the work is technically exhaustive and appears sound, the layout requires refinement. For instance, the discussion and conclusion section seems truncated due to an overflow of technical details, presumably in an attempt to conform to the page limit.\n\nAdditionally, the paper presents an insightful study on Type I error bounds and illuminates how factors in model misspecification might influence the performance of our model. This is examined across three leading methods of regression-based conditional independence testing, STFR, GCM, and RESIT; a commendable breadth of investigation. On the other hand, there lies a lot of  ingenuity in the application of sufficient statistics and the Rao-Blackwell theorem to devise a conditional independence test - an approach that stands out as particularly clever.\n\nDespite the paper's notable theoretical contribution and illumination of model misspecification implications, its current state warrants a rejection recommendation. The primary rationale lies in the sparse experimental validation, which leaves room for further expansion. While a more comprehensive set of experimental results could potentially sway my assessment towards endorsement, the manuscript, as it stands, along with the limited set of experiments, doesn't quite meet the high standards necessary for acceptance. Thus, my score, on balance, falls on the lower side.\n", "questions": "1. Regarding eq. (3.1), it seems to me that $\\hat{\\sigma}$ mismatches the sample standard deviation of $T_i^{(m)}$; it is incorrectly expressed as a biased estimator. For simplicity, you might want to just denote $\\bar{T}^{(n,m)}$ and $\\hat{\\sigma}^{(n, m)}$ as the sample mean and variance estimators and not include any formulas, referencing Dei et al. for looking up the exact derivations.\n2. In the experiments section, especially concerning figure 2, I have several points of interest:\n* It would be insightful to observe how RBPT behaves in terms of Type I error when $Q$ is misspecified. For instance, a scenario where $c=0$, $\\theta=1$, and $\\gamma$ is progressively increased could be worth examining. Alternatively, to evaluate how sensitive RBPT is to such misspecification, setting $\\gamma$ to a larger value (say 0.02), and sweeping through different $\\theta$ values to assess Type I error might be valuable. I believe this experiment is of extreme importance since, in most real-world situations, the total variation between $Q^*(X|Z)$ and $P(X|Z)$ is significant and may not be bounded by the Jensen gap. Assessing this sensitivity is pivotal to demonstrating the robustness of the setting. The second plot, where $\\gamma = 0$, may not adequately reflect this robustness.\n* It would be beneficial to include the values of other hyperparameters set in the caption of Figure 2. This would prevent the need to navigate back and forth through the text to understand the setup; also, I assumed that for the third plot $\\gamma = \\theta = 0$, but it was not mentioned in the main text.\n3. Why hasn't the power of RBPT been directly compared with the baselines for the real-world examples? The reasons for not contrasting RBPT are somewhat elusive to me. While I concur that both RBPT and RBPT2 theoretically establish bounds for Type I error control under model misspecification, a quantitative comparison with baselines is still essential due to the trade-off between Type I and Type II errors. Although we don't expect RBPT to outperform other models in terms of power, it would be interesting to see if it possesses comparable power, as suggested by the third plot in Figure 2.\n4. I am perplexed by the stark disparity between the performance of RBPT2 in low versus high-dimensional settings. It appears that an increase in the dimension of Z invariably leads to rejection of the null hypothesis, resulting in a rise in both power and Type I error rate. Could this be attributed to the need for a dimension normalization term in $b$? How are $b$ and $a$ generated per experiment, and how does $b^T Z$ scale with the dimension? Why doesn't this impact RBPT or CPT? After all, one of the main applications of regression-based conditional independence tests are high-dimensional settings, and it is important to address such concerns.\n", "limitations": "1. In the RBPT methodology, model misspecification is conceptualized as the difference between $Q^*(X|Z)$ and $P(X|Z)$, and between $g^*(x, y)$ and $f^*(x, y)$. This deviates from prior methods where the misspecification is solely defined between $g_1^*$ and $f_1^*$, and $g_2^*$ and $f_2^*$. While the latter defines misspecification between functions, the former is defined on an entire distribution.\nNotably, even if we posit that the disparity between the predicted $\\hat{Q}(X|Z)$ and $Q^*(X|Z)$ is infinitesimal, the divergence between $Q^*(X|Z)$ and $P(X|Z)$ remains far from negligible. Furthermore, the effectiveness of the entire method hinges on this misspecification gap ($\\Omega_{P,1}^{\\text{RBPT}}$) being smaller than the Jensen's gap, which places stringent restrictions on its applicability. While theoretically, this method relaxes the bound on the expected total variation between $Q^*$ and $P$ and sets it to $\\frac{\\Omega_{P,2}^{\\text{RBPT}}}{M \\cdot L}$, the $M$ and $L$ coefficients will be pretty large in practice. On the other hand, while RBPT2 appears to circumvent this issue, its theoretical grounding isn't as robust as that of RBPT, thereby reducing its perceived solidity.\nI believe this issue will become more prominent in real-world settings and the toy experiments do not reveal this core flaw of the method. Therefore, the authors should have mentioned this limitation or run extra experiments to show the effect of this gap.\n2. A prominent constraint associated with RBPT2 appears to be its performance when scaling $Z$. Unfortunately, this aspect is not addressed within the main paper text. It would be beneficial to incorporate some commentary on this issue, as it pertains to the most plausible plug-and-play application. Furthermore, I harbor concerns regarding the potential for error from the initial regression to percolate into the subsequent one, which could potentially escalate the overall margin of error. This is pointed out in Appendix A.6, and with the empirical results acting strangely with scaling (I also mentioned in the “Questions” section), I am concerned as to how much this can hinder the performance of RBPT2.\n", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 1, "contribution": 3, "strengths": "1. The paper exhibits a robust theoretical foundation, ingeniously leveraging the principles of sufficient statistics and the Rao-Blackwell theorem to address conditional independence testing. This innovative application, to the best of my understanding, introduces a novel concept and forms a significant contribution.\n2. The paper provides extensive misspecification bounds that comprehensively span across various regression-based methods. Moreover, the experiments also benchmark against simulation-based approaches.\n3. The exploration of examples in Appendix A.2 is highly instructive, where model misspecification can influence and Type I error of our test significantly. In addition, the choice of synthetic experiments adapted from Berrett et al. serves as a fitting means of demonstrating the concept in this study.\n4. In an innovative deviation from the traditional setting, this paper presents proofs across a series of models that converge to a pre-established class of models, thereby aligning well with contemporary machine learning paradigms\n", "weaknesses": "1. Acknowledging that the paper's paramount contribution resides in its theoretical development, I must express my reservations regarding the experimental element, which appears somewhat insufficient. To bolster the validation process, I've proposed additional experimental situations in the \"Questions\" section. As it stands, the validation primarily leans on a single toy experimental setup, and a comprehensive benchmarking across different methods in a real-world setup is lacking.\n2. In terms of presentation, the paper could benefit from some refinement. Notably, a significant portion of the proof concepts across different Conditional Independence Testing methods appears to overlap. A majority of these proofs could have been concisely presented by adopting lemmas that generalize across multiple methods, thus increasing reader engagement. Also, the main body is currently dense with scattered technical terms that could be better consolidated.\n3. Just a minor point of clarification, I'd like to delve into the details of the conducted toy experiments. Developing a unified framework that frames functions as a sequential path towards a distinct model group is truly commendable. Nonetheless, there's scope for refining its presentation. Specifically, the introduction gave the impression that this was a broad generalization of model misspecification, which it doesn't appear to be.\nUpon incorporating regularization terms during training, it's important to note that while the overarching model class remains constant, the subset of models that surface must adhere to the regularization-imposed limits. Consequently, the model's prime focus may deviate from merely minimizing the Bayes predictor loss.\nThis deviation could result from either integrating regularization terms into the optimization formula, thus modifying the loss characteristics, or from imposing these terms as constraints, effectively limiting the model class.\nConsidering these factors, I'd suggest positioning your model misspecifications as a tool to tailor the concept to real-world machine learning environments, rather than representing it as a broad generalization of the concept of model misspecification itself.\n4. One of the method's most significant practical implications, in my view, is the potential for semi-supervised learning on unlabeled data - a scenario where RBPT is likely to outshine RBPT2. Given its importance in practical real-world settings, this deserves an additional set of experiments. An easy experiment to consider would be to add a large set of unlabeled data to the toy experiment.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Thank you\n\nThank you for your time and constructive feedback. Your suggestions made our paper more complete.\n\nWe believe we have addressed your requests and questions in our comments. Please let us know if you have further concerns.\n\nBest regards,\n\nAuthors\n\n--------------\n\n## Rebuttal\n\n**Semi-supervised learning.** Both RBPT and RBPT2 have the potential to improve performance when a large unlabeled dataset is available. This also applies to RBPT2 because fitting the second predictor does not necessitate any labels. Please check the new experiments.\n\n**Dimensionality of $Z$ and its effects on the testing procedure.** You have astutely noted that escalating the dimension of $Z$ could detrimentally influence RBPT2. Nevertheless, as demonstrated in our new experiments, this complication can be mitigated by employing a large unlabeled dataset to train the second predictor. Moreover, it is crucial to emphasize that a growing $d_Z$ is also likely to adversely impact STFR, GCM, CPT, CRT, and any other regression or simulation-based conditional testing procedures. This effect arises primarily because these methods initially necessitate the estimation of regression functions or conditional distributions, tasks that become increasingly complex with higher dimensions. In our older experiments, the impact of a growing $d_Z$ on RBPT and CPT is not apparent, largely due to our approach of not estimating $P_{X|Z}$ in artificial data experiments. Instead, we introduce \"misspecification\" via modifications in $\\theta$. We acknowledge the importance of addressing this point and will ensure to include a discussion about it in our manuscript. \n\n**On the percolation of initial regression errors.** While your concerns about the potential cascading of errors from the initial regression to the subsequent one are understandable, it's important to note that this issue may not necessarily pose a problem given a sufficiently competent second model. This is a direct implication of Jensen's inequality: for an *arbitrary* initial model $g(x,z)$ and a convex loss function $\\ell$, under $H_0$ we find that \n$$\n\\\\mathbb{E}[\\\\ell(h(Z),Y)] \\\\leq \\\\mathbb{E}[\\\\ell(g(X,Z),Y)] \n$$\n\nwhere $h(z)\\triangleq \\\\mathbb{E}[g(X,Z)|Z=z]$ is the Rao-Blackwellized predictor. If our second predictor performs well, $h$ will be estimated accurately, and the Type-I error will be controlled. This concept is empirically validated in our new experiment, where we demonstrate that by increasing the size of the unlabeled sample - thus keeping the first predictor unaffected - the second predictor's performance improves, and the Type-I error rate is effectively controlled.\n\n**Comparing power in real data experiment.** We added the benchmarks when analyzing power; please check our third new experiment.\n\n**New experiments:** In response to your valuable feedback, we have conducted three additional experiments, the details of which can be found below and in the uploaded PDF document. These experiments address your concerns, shedding light on the capabilities and robustness of RBPT/RBPT2.\n\n1. *High-dimensional $Z$ and use of unlabeled data:* With $d_Z=40$ (a challenging scenario for RBPT2, as seen in the appendix), we gradually increased the unlabeled sample size from 0 to 500. The results, detailed in the uploaded PDF, show that a larger unlabeled sample size effectively controls the Type-I error rate, indicating a successful approximation of the Rao-Blackwellized predictor even when $d_Z$ is big.\n\n2. *RBPT robustness in challenging scenarios:* Simultaneously adjusting $\\gamma$ and $\\theta$ across a range of values, we observed that RBPT outperformed CPT in robustness for $\\theta\\leq 4$. However, for $\\theta>4$, RBPT encountered challenges controlling the Type-I error rate for large $\\gamma$ values. Despite this, the full set of experiments underscores RBPT's robustness, making it an especially favorable approach in instances where it is challenging to estimate the functional form of $p_{X|Z}$ (density of $P_{X|Z}$). Contrary to CPT, RBPT sidesteps this challenge using Monte Carlo integration combined with GAN-like sampling techniques. Furthermore, CPT is more sensitive in experiments with real data.\n\n3. *Detecting discrimination against minorities using fully real data.* In this experiment, we compare the output of different conditional independence tests regarding power. Roughly speaking, the methods point to the same qualitative result that discrimination against minorities in ZIP codes is most evident in Illinois, followed by Texas, Missouri, and California. These findings corroborate Angwin and colleagues' findings, indicating that our methodology has satisfactory power while maintaining Type-I error control (which the benchmarks violate).\n\n**About RBPT2.** We acknowledge the limitations of RBPT2 you have highlighted (in point 1 of the \"Limitations\" section) and will ensure they are discussed in the subsequent version of our paper. We appreciate your attention to this detail.\n\n**Caption of Figure 2.** We are going to incorporate the values of the parameters within the figure caption and will also embed the observation \"$\\gamma=\\theta=0$\", which you accurately inferred, into the body of the manuscript. Thank you for your input!\n\n**Presentation and general clarifications.** We greatly value your input on refining our paper's presentation. We'll certainly consider your suggestions for enhancing readability and conciseness in the paper's next version.\n\n**Observation about sample standard deviation.** The bias in $\\\\hat{\\\\sigma}^{(n,m)}$ is asymptotically negligible and does not impact our results. Still, we appreciate your suggestion of referencing Dai's paper and will consider it for the upcoming revision.\n\n--------------------\n### References\n\n[1] Julia Angwin, Jeff Larson, Lauren Kirchner, and Surya Mattu. Minority neighborhoods pay higher car insurance premiums than white areas with the same risk, April 2017. \n\n\n\n\n"}, {"review_id": "b3ZAyrPiPJ", "reviewer": "Reviewer_t2AA", "summary": "This paper discusses the challenges of conditional independence (CI) testing in modern statistics and machine learning. The authors note that many modern methods for CI testing rely on supervised learning methods to learn regression functions or Bayes predictors, but these methods can be unreliable when the models are misspecified. The paper proposes new approximations or upper bounds for the testing errors of three regression-based tests that depend on misspecification errors. The authors present new robustness results for three relevant regression-based CI tests and derive approximations or upper bounds for the testing errors that explicitly depend on the misspecification of the prediction models. The paper concludes that more attention should be given to theoretically understanding the effects of misspecification on CI hypothesis testing and that current regression-based methods are usually not designed to be robust against misspecification errors, making CI testing less reliable.", "questions": "Why are regression-based and simulation-based tests more appealing than the other two tests?\n\nWhat is type-I error?\n\nWhy there are no result on Illinois and Texas in p-value of Figure 3?\n\nIn Figure 2, why you did not have results of RBPT2 on \\theta VS Type-I error rate?\n\nSince you compared your designed method with STFP, why not choose the same dataset as STFP to show the efficiency of your method?", "limitations": "N/A", "rating": 6, "confidence": 1, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The writing is good.\n\nThe introduction on model misspecification is good.", "weaknesses": "Lack of introducing conditional independence testing.\n\nRBPT2 is powerful but it cost much more time compared with other methods, such as STFR, GCM. Lack of analysis the time complexity of each designed method.\n\nOnly one real dataset. This method should be applied on more real application and dataset, like STFR which is applied on MNIST handwritten digits, Mechanisms of Action (MoA) prediction for new drugs and Chest X-rays for pneumonia diagnosis.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Thank you\n\nThank you for your time and work on our paper.\n\nWe believe we have addressed your concerns and questions in our comments. Please let us know if you have any other questions.\n\nBest regards,\n\nAuthors\n\n______________\n\n## Rebuttal\n**Time complexity of RBPT and RBPT2.** The running times of RBPT and RBPT2 primarily hinge on the underlying supervised or generative models we employ, mirroring the situation in STFR, GCM, CRT, CPT, and similar methods. Once the training step is completed, testing is conducted in linear time (in the number of testing samples) for RBPT, RBPT2, STFR, GCM, etc.\n\n**Results for Illinois and Texas.** The p-values for Illinois and Texas are nearly zero, rendering them practically invisible on the plot.\n\n**Results for RBPT in the second plot of Figure 2.** This is because $\\theta$ is intrinsically tied to the misspecification of the model for $P_{X|Z}$. Fitting that model is not required for RBPT2, hence the omission.\n\n**Regression and simulation-based tests.** Regression-based and simulation-based tests hold appeal as they take advantage of the most recent and powerful supervised and generative methods. These tests are also known for their scalability with large datasets in terms of features and samples.\n\n**Definition for Type-I error.** Type-I error arises in hypothesis testing when a true null hypothesis gets wrongly rejected, leading to false discovery.\n\n**Real data applications.** Our goal in the experiments section is to benchmark RBPT/RBPT2 against a range of methods, including STFR, GCM, RESIT, CPT, and CRT, each of which uses different datasets in their original papers. We decided to use the car insurance dataset, which represents a key application area for conditional independence tests and is compatible with almost all these methods (except RESIT)."}, {"review_id": "yNhAj8IH8G", "reviewer": "Reviewer_8LZA", "summary": "This paper presents new robustness results for three regression-based conditional independence (CI) tests, namely, Significance Test of Feature Relevance (STFR), Generalized Covariance Measure (GCM) test, and REgression with Subsequent Independence Test (RESIT). It introduces a new CI test, the Rao-Blackwellized Predictor Test (RBPT), designed to be more robust to model misspecification. Theoretical findings and experimental results show that the RBPT is able to control Type-I error effectively even when models are misspecified.", "questions": "- In the eq. between lines 76, and 77. Why do you write \" Y | X, Z ~ ... \" and not just \" Y | Z \" ? \n", "limitations": "n.a.", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- Well written and structured. Thanks\n- Great intro to related work.\n- Addresses a significant problem\n- Provides theoretical and empirical insights.", "weaknesses": "- The authors make a long and good argument, that misspecification needs to account for the training algorithm. It seems that this is a natural result of the model posing a non-convex or underspecified optimization problem for training. Therefore, I'm not sure this needs to be demonstrated in such depth. (Please correct me, if I'm misunderstanding this)\n- Could have more empirical validation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Thank you\n\nWe greatly appreciate your feedback on our paper.\n\nThank you for your questions. We have addressed them below. Please let us know if you have any other comments or questions.\n\nBest regards,\n\nAuthors\n\n------------------\n\n## Rebuttal\n\n**Misspecification discussion.** You're correct that it is indeed a natural outcome. However, given the centrality of model misspecification in our paper, we felt a comprehensive discussion was necessary, especially since our definition of \"misspecification\" differs from the conventional one in the statistics literature.\n\n**Question about math notation.** The notation $Y|X, Z \\sim$ was used as opposed to $Y|Z  \\sim$ to highlight that $Y$ and $X$ are conditionally independent when given $Z$. That is evident because the distribution of $Y|X, Z$ does not depend on $X$ even though we included that variable in \"$Y|X, Z$.\"\n\n**More empirical evaluation.**  We have conducted three additional experiments, the details of which can be found below and in the uploaded PDF document. \n\n1. *High-dimensional $Z$ and use of unlabeled data:* With $d_Z=40$ (a challenging scenario for RBPT2, as seen in the appendix), we gradually increased the unlabeled sample size from 0 to 500. The results, detailed in the uploaded PDF, show that a larger unlabeled sample size effectively controls the Type-I error rate, indicating a successful approximation of the Rao-Blackwellized predictor even when $d_Z$ is big.\n\n2. *RBPT robustness in challenging scenarios:* Simultaneously adjusting $\\gamma$ and $\\theta$ across a range of values, we observed that RBPT outperformed CPT in robustness for $\\theta\\leq 4$. However, for $\\theta>4$, RBPT encountered challenges controlling the Type-I error rate for large $\\gamma$ values. Despite this, the full set of experiments underscores RBPT's robustness, making it an especially favorable approach in instances where it is challenging to estimate the functional form of $p_{X|Z}$ (density of $P_{X|Z}$). Contrary to CPT, RBPT sidesteps this challenge using Monte Carlo integration combined with GAN-like sampling techniques. Furthermore, CPT is more sensitive in experiments with real data.\n\n3. *Detecting discrimination against minorities using fully real data.* In this experiment, we compare the output of different conditional independence tests regarding power. Roughly speaking, the methods point to the same qualitative result that discrimination against minorities in ZIP codes is most evident in Illinois, followed by Texas, Missouri, and California. These findings corroborate Angwin and colleagues' findings, indicating that our methodology has satisfactory power while maintaining Type-I error control (which the benchmarks violate).\n\n"}, {"review_id": "jwGAlWCVyH", "reviewer": "Reviewer_Hib1", "summary": "The authors study model-based tests of conditional independence under conditions where the models may be biased. They propose new approximations and bounds on testing errors resulting from bias in model-based CI tests. They also introduce RBPT, a new model-based CI test and evaluate it against several alternatives.\n", "questions": "(none)", "limitations": "There appear to be relatively few negative impacts to the authors' work. Indeed, it facilitates *avoiding* important classes of errors that could have substantial negative impacts.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written and provides substantial theoretical derivation of the Type I error rate and power of the proposed test.\n\nThe authors address a very important problem that is under-appreciated. Many researchers would assume (mistakenly) that non-parametric conditional independence testing is a solved problem. In reality, there exists no generally accepted solution, despite substantial prior work.\n\nFurthermore, the authors work on a very important aspect of the problem. Model misspecification, as they term it, appears to be both ubiquitous and difficult to detect and diagnose. Making model-based CI tests that are robust to this source of bias would represent a major step forward. \n\nThe authors correctly point out that, despite a variety of deep models being *capable* of being universal function approximators, that does not mean that unbiased models are *actually learned in practice*.\n\nEmpirical evaluation of CI tests is difficult, at best. However, the authors provide both simulation and real-data experiments that provide some evidence that their approach delivers on its promises.", "weaknesses": "As the authors note, the term “model misspecification” has a long history in statistics (and some parts of machine learning), and it seems a stretch to expand that term to include non-optimal parameter settings due to the limitations of a given training algorithm. There is certainly an issue here, but calling it “model misspecification” is likely to cause some initial confusion for readers. The authors are quite clear that they are redefining the term, but seeking an alternative term may be more helpful to readers. Some options include “non-optimal training”, “underspecification”, and “non-identifiability”, though I suspect there is an even better term.\n\nIn the caption of Figure 3, the authors state that “RBPT and RBPT2 have better Type-I error control compared to other methods.” However, STFR fairly clearly outperforms RBPT2 in terms of absolute error with respect to the 0.10 gold standard and STFR usually outperforms RBPT.\n\nOne minor correction: The text describing Figure 1 says that the Type I error rate was set to 0.01, but the figure shows that it was set to 0.10. Furthermore, that text refers to Figure 4, which does not appear to exist in the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Thank you\n\nWe greatly appreciate your work on our paper.\n\nThank you for the raised points. We have addressed them below. Please let us know if you have any other comments or questions.\n\nBest regards,\n\nAuthors\n\n---------------------\n\n## Rebuttal\n\n**Superiority of RBPT/RBPT2 over STFR in the real data experiment.** Indeed, if we consider the \"absolute error\" as the metric, your observation holds. However, significance testing procedures often prioritize maintaining control over the Type-I error (having a Type-I error rate less than the significance level $\\\\alpha$). Consequently, falling below the $\\\\alpha=10\\\\%$ threshold (as RBPT/RBPT2 in most cases) is more desirable than above (as  STFR  in most cases).\n\n**Terminology.** We acknowledge your valuable input regarding the possible confusion that might arise from our use of the term \"model misspecification,\" given its traditional connotations in the field. We will certainly consider your advice and reassess our terminology choices in the next version of this paper.\n\n**Typos.** Thank you for pointing out the typos. We will correct the main text."}, {"review_id": "qbiNKo6d47", "reviewer": "Reviewer_hFX5", "summary": "The paper proposes a new Rao-Blackwellized Predictor Test which is a regression-based conditional independence test. It was shown to be robust in misspecification settings. ", "questions": "I would like a clarification for the phrase \"even models capable of universal approximation may not accurately estimate the Bayes predictor...\". What is exactly meant? Do you mean that if some hyper-parameters are not well-chosen then even a well-specified model does not approach the Bayes error? Even asymptotically? However, in an asymptotic case hyper-parameters do not play any role?\n\nOn page 3, Figure 4 is mentioned. Where is it? \n\nIn Section 5, \"real data experiments\": X represents the driving risk and X is a minority indicator, but what is Y? Is it the price? It would be helpful to write it explicitly. \n\n\"For RBPT2, we use a CatBoost regressor...\": could you detail how you apply the CatBoost to get the Rao-Blackwellized predictor? What kind of modifications are made to the original CatBoost?\n", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper is in general well-written and considers an important scenario which is not covered by standard conditional independence tests. The new approach guarantees Type-1 error control (asymptotically). ", "weaknesses": "The paper is quite technical (what is good), however, a number of important details are in the Appendix what is not always practical. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Thank you\n\nWe want to thank you for your time and work on our paper.\n\nWe believe we have addressed your questions in our comments. Please let us know if you have further questions or comments.\n\nBest regards,\n\nAuthors\n\n--------------\n\n## Rebuttal\n\n**Question about universal approximators.** We intend to communicate here that regardless of the model's capacity for universal approximation, the training algorithm essentially narrows the potential model class to a smaller class of \"feasible\" models (perhaps not in the hard-constraints sense), even in the asymptotic case. This bias can make the Bayes error unreachable. Therefore, choosing hyperparameters is a crucial step.\n\n**Figure 4 missing.** It was a typo that will be corrected. We wanted to mention Figure 1 instead. Thanks for pointing this out.\n\n**Meaning of $Y$ in the real data experiments.** In that case, $Y$ is the insurance price. We will make it more explicit.\n\n**Question about CatBoost.** We appreciate your interest in the implementation details of the Rao-Blackwellized predictor using CatBoost in our RBPT2 methodology. In this context, CatBoost is employed to predict the output of the initial predictor, $\\\\hat{g}(X,Z)$, utilizing $Z$ as the input to the boosting algorithm. We have not made any modifications to the standard CatBoost algorithm, but we apply it in a way that aids the execution of the RBPT2 test when estimating $P_{X| Z}$ proves challenging. For a more comprehensive explanation of this process and the underlying rationale, we invite you to consult the paper subsection \"Running RBPT when it is hard to estimate $P_{X| Z}$: the RBPT2.\"\n"}]

Author rebuttal:
We extend our sincere thanks to all reviewers and chairs. We have responded to all the points raised by reviewers individually and have attached a PDF containing additional experiments. The first of these experiments demonstrate that the robustness of RBPT2 in higher dimensions can be improved through the use of unlabeled data (data pairs consisting of $X$ and $Z$ only). The second experiment examines RBPT in more challenging scenarios and supports the assertion that it offers a practical and robust solution for conditional independence testing. The third one shows that RBPT/RBPT2 output on the car insurance experiment aligns with other methods and previous literature, indicating that our methodology has satisfactory power while maintaining Type-I error control (which the benchmarks violate).


Meta-review: The paper studies model-based tests of conditional independence when models may be biased (misspecified). They derive bounds on testing errors resulting from forms of misspecification in model-based CI tests and also introduce RBPT, a robust, model-based CI test. Some initial reviews highlighted the need for more empirical evaluation particularly when the conditioning set is high-dimensional; the authors during the discussion phase provided an updated empirical evaluation studying the effect of the dimensionality of the conditioning variable, the robustness of the test and the performance of baselines on real data.

This is a well written paper that tackles an important problem that is often brushed under the rug. Please do include the additional results in the pdf presented and incorporate a discussion of the same into the main paper/supplement. With that, I think this will be a very strong addition to the conference proceedings.
Decision: Accept (spotlight)