# Conditional independence testing under model misspecification

Felipe Maia Polo
Department of Statistics
University of Michigan
<EMAIL_ADDRESS>
&Yuekai Sun
Department of Statistics
University of Michigan
<EMAIL_ADDRESS>
&Moulinath Banerjee
Department of Statistics
University of Michigan
<EMAIL_ADDRESS>

###### Abstract

Conditional independence (CI) testing is fundamental and challenging 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. Although the methods are guaranteed to
control Type-I error when the supervised learning methods accurately estimate
the regression functions or Bayes predictors, their behavior is less
understood when they fail due to model misspecification. In a broader sense,
model misspecification can arise even when universal approximators (e.g., deep
neural nets) are employed. Then, we study the performance of regression-based
CI tests under model misspecification. 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 novel regression-based CI test robust
against model misspecification. Finally, we conduct experiments with
artificial and real data, showcasing the usefulness of our theory and methods.

##  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, 22, 32, 11] and (ii) algorithmic
fairness [26], to (iii) feature selection/importance [5, 35] and (iv) transfer
learning [23]. Due to 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-based CI tests 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-based tests usually depend on the assumption
that we can accurately approximate the regression functions or Bayes
predictors, which is hardly true if the models are misspecified. Model
misspecification can lead to inflated Type-I error rates or powerless tests.
Even though these problems can frequently arise in 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 to be robust against misspecification errors
making CI testing less reliable.

Contributions. Our main contributions are:

  * •

We present new robustness results for three relevant regression-based
conditional independence tests: (i) Significance Test of Feature Relevance
(STFR) [7], (ii) Generalized Covariance Measure (GCM) test [29], and (iii)
REgression with Subsequent Independence Test (RESIT)[39, 22, 12]. Namely, we
derive approximations or upper bounds for the testing errors that explicitly
depend on the misspecification of the prediction models.

  * •

We introduce the Rao-Blackwellized Predictor Test (RBPT), a modification of
the Significance Test of Feature Relevance (STFR) [7] test that is robust
against model misspecification. In contrast with STFR and previous regression
and simulation-based methods, the RBPT does not 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,Y,Z)$ be a random vector taking
values in
$\mathcal{X}\times\mathcal{Y}\times\mathcal{Z}\subseteq{\mathbb{R}}^{d_{X}\times
d_{Y}\times d_{Z}}$ and $\mathcal{P}$ be a family of distributions on the
measurable space
$(\mathcal{X}\times\mathcal{Y}\times\mathcal{Z},\mathcal{B})$, where
$\mathcal{B}=\mathcal{B}(\mathcal{X}\times\mathcal{Y}\times\mathcal{Z})$ is
the Borel $\sigma$-algebra. We assume $\mathcal{P}$ is given for the rest of
this work. If $(X,Y,Z)\sim P$ and $\mathcal{P}_{0}\subset\mathcal{P}$ is the
set of distributions in $\mathcal{P}$ such that $X\mathchoice{\mathrel{\hbox
to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}Y\mid Z$, the problem of conditional
independence testing can be expressed in the following way:

$\displaystyle H_{0}:P\in\mathcal{P}_{0}$ $\displaystyle
H_{1}:P\in\mathcal{P}\backslash\mathcal{P}_{0}$

In this work, we also write $H_{0}:X\mathchoice{\mathrel{\hbox
to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}Y\mid Z$ and
$H_{1}:X\not\mathchoice{\mathrel{\hbox to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}Y\mid Z$. We assume throughout that we have
access to a dataset
$\mathcal{D}^{(n+m)}=\\{(X_{i},Y_{i},Z_{i})\\}_{i=1}^{n+m}$ independent and
identically distributed (i.i.d.) with distribution in $\mathcal{P}$, where
$\mathcal{D}^{(n+m)}$ splits into a test set
$\mathcal{D}^{(n)}_{te}=\\{(X_{i},Y_{i},Z_{i})\\}_{i=1}^{n}$ and a training
set $\mathcal{D}^{(m)}_{tr}=\\{(X_{i},Y_{i},Z_{i})\\}_{i=n+1}^{n+m}$. For
convenience, we use the training set to fit models and the test set to conduct
hypothesis tests, even though other approaches are possible.

Model misspecification in modern statistics and machine learning.
Traditionally, the concept of model misspecification has been closely linked
to the chosen model class. For instance, if the best (Bayes) predictor for $Y$
given $X$, $f^{*}$, is a non-linear function of $X$, but we use a linear
function to predict $Y$, then we say our model is misspecified because $f^{*}$
is not in the class of linear functions. However, we argue that this
definition is inadequate for our purposes. In modern machine learning and
statistics, it is well-established that the training algorithm also plays a
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 [13, 31]. In
addition, D’Amour et al. [9] showed that varying hyperparameter values during
training can 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 out-of-distribution
accuracy in predicting skin health conditions for different skin types,
indicating that each model learned distinct features from the images. The
sensitivity of the trained model with respect to different training settings
suggests that even models capable of universal approximation may not
accurately estimate the Bayes predictor if the training inductive biases do
not induce the patterns or functions we are trying to learn.

Figure 1: Type-I error rate is contingent on the training algorithm and not
solely on the model classes. Unlike the minimum-norm solution, the LASSO fit
provides the correct inductive bias in high-dimensional regression,
controlling Type-I error.

We present a toy experiment to empirically demonstrate how the training
algorithm can prevent us from accurately estimating the Bayes predictor even
when the model class is correctly specified, leading to invalid significance
tests. We work in the context of a high-dimensional (overparameterized)
regression with a training set of $250$ observations and $500$ covariates. We
use the Generalized Covariance Model (GCM) test111See Appendix A.3 for more
details [29] to conduct the CI test. The data are generated as

$Z\sim N(0,I_{500}),~{}X\mid Z\sim N(\beta_{X}^{\top}Z,1),~{}Y\mid X,Z\sim
N(\beta_{Y}^{\top}Z,1)$

where the first five entries of $\beta_{X}$ are set to $20$, and the remaining
entries are zero, while the last five entries of $\beta_{Y}$ are set to $20$,
and the remaining entries are zero. This results in $X$ and $Y$ being
conditionally independent given $Z$ and depending on $Z$ only through a small
number of entries. Additionally, ${\mathbb{E}}[X\mid Z]=\beta_{X}^{\top}Z$ and
${\mathbb{E}}[Y\mid Z]=\beta_{Y}^{\top}Z$, indicating that the linear model
class is correctly specified. To perform the GCM test, we use LASSO
($\left\|\cdot\right\|_{1}$ penalization term added to empirical squared
error) and the minimum-norm least-squares solution to fit linear models that
predict $X$ and $Y$ given $Z$. In this problem, the LASSO fitting approach
provides the correct inductive bias since $\beta_{X}$ and $\beta_{Y}$ are
sparse. We set the significance level to $\alpha=10\%$ and estimate the Type-I
error rate for $100$ different training sets. Figure 4 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 model
misspecification in the minimum-norm case, implying an invalid test most of
the time. In Appendix A, we give a similar example but using the Significance
Test of Feature Relevance (STFR) [7].

Given the context, we expand the notion of model misspecification to account
for the role of the training algorithm. Assume that a training algorithm
$\mathcal{A}$ is used to choose a model
$\hat{g}^{(m)}=\mathcal{A}(\mathcal{D}^{(m)}_{tr})$ from the class
$\mathcal{G}^{(m)}$. We further assume that the sequence
$(\hat{g}^{(m)})_{m\in\mathbb{N}}$ converges to a limiting model $g^{*}$ in a
relevant 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 $g^{*}$ is misspecified if it does not
equal the Bayes predictor $f^{*}$ almost surely. Therefore, there are two
possible reasons for model misspecification: either the limiting model class
is small and does not include $f^{*}$, or the training algorithm cannot find
the best possible predictor.

Notation. We write ${\mathbb{E}}_{P}$ and ${\sf Var}_{P}$ for the expectation
and variance of statistics computed using i.i.d. copies of $(X,Y,Z)\sim P$.
Consequently, ${\mathbb{P}}_{P}(A)={\mathbb{E}}_{P}\mathds{1}_{A}$, where
$\mathds{1}_{A}$ is the indicator of an event $A$. If ${\mathbb{E}}_{P}$ and
${\sf Var}_{P}$ are conditioned on some other statistics, we assume those
statistics are also computed using i.i.d. samples from $P$. As usual, $\Phi$
is the $N(0,1)$ distribution function.

If $(a_{m})_{m\in\mathbb{N}}$ and $(b_{m})_{m\in\mathbb{N}}$ are sequences of
scalars, then $a_{m}=o(b_{m})$ is equivalent to $a_{m}/b_{m}\to 0$ as
$m\to\infty$ and $a_{m}=b_{m}+o(1)$ means $a_{m}-b_{m}=o(1)$. If
$(V^{(m)})_{m\in\mathbb{N}}$ is a sequence of random variables, where
$V^{(m)}$ as constructed using i.i.d. samples of $P^{(m)}\in\mathcal{P}$ for
each $m$, then (i) $V^{(m)}=o_{p}(1)$ means that for every $\varepsilon>0$ we
have ${\mathbb{P}}_{P^{(m)}}(|V^{(m)}|>\varepsilon)\to 0$ as $m\to\infty$,
(ii) $V^{(m)}=\mathcal{O}_{p}(1)$ means that for every $\varepsilon>0$ there
exists a $M>0$ such that
$\sup_{m\in\mathbb{N}}{\mathbb{P}}_{P^{(m)}}(|V^{(m)}|>M)<\varepsilon$, (iii)
$V^{(m)}=a_{m}+o_{p}(1)$ means $V^{(m)}-a_{m}=o_{p}(1)$, (iv)
$V^{(m)}=o_{p}(a_{m})$ means $V^{(m)}/a_{m}=o_{p}(1)$, and (v)
$V^{(m)}=\mathcal{O}_{p}(a_{m})$ means $V^{(m)}/a_{m}=\mathcal{O}_{p}(1)$.

Finally, let $(V^{(m)}_{P})_{m\in\mathbb{N},P\in\mathcal{P}}$ be a family of
random variables that distributions explicitly depend on $m\in\mathbb{N}$ and
$P\in\mathcal{P}$. We give an example to clarify what we mean by "explicitly"
depending on a specific distribution. Let
$V^{(m)}_{P}=\frac{1}{m}\sum_{i=1}^{m}(X_{i}-\mu_{P})$, where
$\mu_{P}={\mathbb{E}}_{P}[X]$. Here, $V^{(m)}_{P}$ explicitly depends on $P$
because of the quantity $\mu_{P}$. In this example, $X_{i}$’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_{P}^{(m)}=o_{\mathcal{P}}(1)$ means that for every $\varepsilon>0$ we have
$\sup_{P\in\mathcal{P}}{\mathbb{P}}_{P}(|V_{P}^{(m)}|>\varepsilon)\to 0$ as
$m\to\infty$, (ii) $V_{P}^{(m)}=\mathcal{O}_{\mathcal{P}}(1)$ means that for
every $\varepsilon>0$ there exists a $M>0$ such that
$\sup_{m\in\mathbb{N}}\sup_{P\in\mathcal{P}}{\mathbb{P}}_{P}(|V_{P}^{(m)}|>M)<\varepsilon$,
(iii) $V_{P}^{(m)}=o_{\mathcal{P}}(a_{m})$ means
$V_{P}^{(m)}/a_{m}=o_{\mathcal{P}}(1)$, and (iv)
$V_{P}^{(m)}=\mathcal{O}_{\mathcal{P}}(a_{m})$ means
$V_{P}^{(m)}/a_{m}=\mathcal{O}_{\mathcal{P}}(1)$.

Related work. There is a growing literature on the problem of conditional
independence testing regarding both theoretical and methodological
aspects222See, for example, Marx and Vreeken [20], Shah and Peters [29], Li
and Fan [18], Neykov et al. [21], Watson and Wright [35], Kim et al. [14], Shi
et al. [30], Scetbon et al. [28], Tansey et al. [33], Zhang et al. [37], Ai et
al. [1]. 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-based [5, 3, 4, 30, 33, 19], (ii) regression-based [38, 22, 39,
36, 29, 7], (iii) kernel-based [10, 8, 32, 28], and (iv) information-theoretic
based [27, 15, 37]. Due to the advance of supervised and generative models in
recent years, regression and simulation-based tests have become particularly
appealing, especially when $Z$ is not low-dimensional or discrete.

The simulation-based tests depend on the fact that we can, implicitly or
explicitly, approximate the conditional distributions $P_{X\mid Z}$ or
$P_{Y\mid Z}$. Two relevant simulation-based methods are the conditional
randomization and conditional permutation tests (CRT/CPT) [5, 3, 4, 33]. For
tests, Berrett et al. [4] presents robustness results showing that we can
approximately control Type I error even if our estimates for the conditional
distributions are not perfect and we are under a finite-sample regime.
However, it is 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
${\mathbb{E}}[X\mid Z]$ and ${\mathbb{E}}[Y\mid Z]$ or other Bayes predictors,
which is hardly true if the models are misspecified. To the best of our
knowledge, there are no published robustness results for regression-based CI
tests like those presented by Berrett et al. [4]. We explore this literature
gap.

##  3 Regression-based conditional independence tests under model
misspecification

This section provides the results of the Significance Test of Feature
Relevance (STFR) [7]. Due to limited space, the findings for the Generalized
Covariance Measure (GCM) test [29] and the REgression with Subsequent
Independence Test (RESIT) [39, 22, 12] are presented in Appendix A. From the
results in Appendix A, one can easily derive a double robustness property for
both GCM and RESIT, implying that not all models need to be correctly
specified for Type-I error control.

###  3.1 Significance Test of Feature Relevance (STFR)

The STFR method studied by Dai et al. [7] offers a scalable approach for
conducting conditional independence testing by comparing the performance of
two predictors. To apply this method, we first train two predictors
$\hat{g}^{(m)}_{1}:\mathcal{X}\times\mathcal{Z}\to\mathcal{Y}$ and
$\hat{g}^{(m)}_{2}:\mathcal{Z}\to\mathcal{Y}$ on the training set
$\mathcal{D}^{(m)}_{tr}$ to predict $Y$ given $(X,Z)$ and $Z$, respectively.
We assume that candidates for $\hat{g}^{(m)}_{2}$ are models in the same class
as $\hat{g}^{(m)}_{1}$ but replacing $X$ with null entries. Using samples from
the test set $\mathcal{D}^{(n)}_{te}$, we conduct the test rejecting
$H_{0}:X\mathchoice{\mathrel{\hbox to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}Y\mid Z$ if the statistic
$\Lambda^{(n,m)}\triangleq\sqrt{n}\bar{T}^{(n,m)}/\hat{\sigma}^{(n,m)}$
exceeds $\tau_{\alpha}\triangleq\Phi^{-1}(1-\alpha)$, depending on the
significance level $\alpha\in(0,1)$. We define $\bar{T}^{(n,m)}$ and
$\hat{\sigma}^{(n,m)}$ as

$\displaystyle\textstyle\bar{T}^{(n,m)}\triangleq\frac{1}{n}\sum_{i=1}^{n}T^{(m)}_{i}\text{
and
}\hat{\sigma}^{(n,m)}\triangleq\left[\frac{1}{n}\sum_{i=1}^{n}(T^{(m)}_{i})^{2}-\left(\frac{1}{n}\sum_{i=1}^{n}T^{(m)}_{i}\right)^{2}\right]^{1/2}$
(3.1)

with
$T^{(m)}_{i}\triangleq\ell(\hat{g}^{(m)}_{2}(Z_{i}),Y_{i})-\ell(\hat{g}^{(m)}_{1}(X_{i},Z_{i}),Y_{i})+\varepsilon_{i}$.
Here, $\ell$ is a loss function, and
$\\{\varepsilon_{i}\\}_{i=1}^{n}\overset{iid}{\sim}N(0,\rho^{2})$ are
artificial random noises that do not let $\hat{\sigma}^{(n,m)}$ vanish with a
growing training set, thus guaranteeing that the asymptotic distribution of
$\Lambda^{(n,m)}$ is standard normal under $H_{0}:X\mathchoice{\mathrel{\hbox
to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}Y\mid Z$. If the $p$-value is defined as
$p(\mathcal{D}^{(n)}_{te},\mathcal{D}^{(m)}_{tr})=1-\Phi(\Lambda^{(n,m)})$,
the test is equivalently given by

$\varphi^{\textup{STFR}}_{\alpha}(\mathcal{D}^{(n)}_{te},\mathcal{D}^{(m)}_{tr})\triangleq\begin{cases}&1,\text{if
}p(\mathcal{D}^{(n)}_{te},\mathcal{D}^{(m)}_{tr})\leq\alpha\\\
&0,\text{otherwise }\end{cases}$ (3.2)

The rationale behind STFR is that if $H_{0}:X\mathchoice{\mathrel{\hbox
to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}Y\mid Z$ holds, then $\hat{g}^{(m)}_{1}$ and
$\hat{g}^{(m)}_{2}$ should have similar performance in the test set. On the
other hand, if $H_{0}$ does not hold, we expect $\hat{g}^{(m)}_{1}$ 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 $\hat{g}^{(m)}_{1}$ and $\hat{g}^{(m)}_{2}$,
${\mathbb{E}}_{P}[\ell(\hat{g}^{(m)}_{2}(Z),Y)\mid\mathcal{D}^{(m)}_{tr}]-{\mathbb{E}}_{P}[\ell(\hat{g}^{(m)}_{1}(X,Z),Y)\mid\mathcal{D}^{(m)}_{tr}]$,
under $H_{0}$ vanishes as the training set size increases. Moreover, for the
test to have non-trivial power, we need the risk gap to be positive. These
conditions can be met if the risk gap of $g^{*}_{1,P}$ and $g^{*}_{2,P}$, the
limiting models of $\hat{g}^{(m)}_{1}$ and $\hat{g}^{(m)}_{2}$, is the same as
the risk gap of the Bayes’ predictors

$\displaystyle
f^{*}_{1,P}\triangleq{\arg\min}_{f_{1}}{\mathbb{E}}_{P}[\ell(f_{1}(X,Z),Y)]\text{
and
}f^{*}_{2,P}\triangleq{\arg\min}_{f_{2}}{\mathbb{E}}_{P}[\ell(f_{2}(Z),Y)],$

where the minimization is done over the set of all measurable functions333We
assume $f^{*}_{1,P}$ and $f^{*}_{2,P}$ to be well-defined and unique..
However, the risk gap between $\hat{g}^{(m)}_{1}$ and $\hat{g}^{(m)}_{2}$ will
typically not vanish if $g^{*}_{1,P}$ and $g^{*}_{2,P}$ are not the Bayes’
predictors even under $H_{0}$. In general, we should expect $g^{*}_{1,P}$ to
perform better than $g^{*}_{2,P}$ because the second predictor does not depend
on $X$. Furthermore, their risk gap can be non-positive even if $f^{*}_{1,P}$
performs better than $f^{*}_{2,P}$. 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.

To derive theoretical results, we adapt the assumptions from Dai et al. [7]:

######  Assumption 3.1.

There are functions $g^{*}_{1,P}$, $g^{*}_{2,P}$, and a constant $\gamma>0$
such that

$\displaystyle{\mathbb{E}}_{P}\big{[}\ell(\hat{g}^{(m)}_{2}(Z),Y)\mid\mathcal{D}_{tr}^{(m)}\big{]}-{\mathbb{E}}_{P}\big{[}\ell(g^{*}_{2,P}(Z),Y)\big{]}-\Big{(}{\mathbb{E}}_{P}\big{[}\ell(\hat{g}^{(m)}_{1}(X,Z),Y)\mid\mathcal{D}_{tr}^{(m)}\big{]}-{\mathbb{E}}_{P}\big{[}\ell(g^{*}_{1,P}(X,Z),Y)\big{]}\Big{)}$
$\displaystyle=\mathcal{O}_{\mathcal{P}}(m^{-\gamma})$

######  Assumption 3.2.

There exists a constant $k>0$ such that

${\mathbb{E}}_{P}\big{[}|T^{(m)}_{1}|^{2+k}\mid\mathcal{D}_{tr}^{(m)}\big{]}=\mathcal{O}_{\mathcal{P}}(1)\text{
as }m\to\infty$

######  Assumption 3.3.

For every $P\in\mathcal{P}$, there exists a constant $\sigma_{P}^{2}>0$ such
that

${\sf
Var}_{P}[T^{(m)}_{1}\mid\mathcal{D}_{tr}^{(m)}]-\sigma_{P}^{2}=o_{\mathcal{P}}(1)\text{
as }m\to\infty\text{ and }\inf_{P\in\mathcal{P}}\sigma_{P}^{2}>0$

Finally, we present the results for this section. We start with an extension
of Theorem 2 presented by Dai et al. [7] in the case of model
misspecification.

######  Theorem 3.4.

Suppose that Assumptions 3.1, 3.2, and 3.3 hold. If $n$ is a function of $m$
such that $n\to\infty$ and $n=o(m^{2\gamma})$ as $m\to\infty$, then

$\displaystyle\textstyle{\mathbb{E}}_{P}[\varphi^{\textup{STFR}}_{\alpha}(\mathcal{D}^{(n)}_{te},\mathcal{D}_{tr}^{(m)})]=1-\Phi(\tau_{\alpha}-\sqrt{\frac{n}{\sigma_{P}^{2}}}\Omega_{P}^{\textup{STFR}})+o(1)$

where $o(1)$ denotes uniform convergence over all $P\in\mathcal{P}$ as
$m\to\infty$ and

$\Omega_{P}^{\textup{STFR}}\triangleq{\mathbb{E}}_{P}[\ell(g^{*}_{2,P}(Z),Y)]-{\mathbb{E}}_{P}[\ell(g^{*}_{1,P}(X,Z),Y)]$

Theorem 3.4 demonstrates that the performance of STFR depends on the limiting
models $g^{*}_{1,P}$ and $g^{*}_{2,P}$. Specifically, if
$\Omega_{P}^{\textup{STFR}}>0$, then
${\mathbb{E}}_{P}[\varphi^{\textup{STFR}}_{\alpha}(\mathcal{D}^{(n)}_{te},\mathcal{D}_{tr}^{(m)})]\to
1$ even if $H_{0}:X\mathchoice{\mathrel{\hbox
to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}Y\mid Z$ holds. In practice, we should expect
$\Omega_{P}^{\textup{STFR}}>0$ because of how we set the class for
$\hat{g}^{(m)}_{2}$. In contrast, we could have
$\Omega_{P}^{\textup{STFR}}\leq 0$, and then
${\mathbb{E}}_{P}[\varphi^{\textup{STFR}}_{\alpha}(\mathcal{D}^{(n)}_{te},\mathcal{D}_{tr}^{(m)})]\leq\alpha+o(1)$,
even if the gap between Bayes’ predictors is positive. See examples in
Appendix A.2 for both scenarios. Next, we provide Corollary 3.6 to clarify the
relationship between testing errors and model misspecification. This corollary
formalizes the intuition that controlling Type-I error is directly related to
misspecification of $g^{*}_{2,P}$, while minimizing Type-II error is directly
related to misspecification of $g^{*}_{1,P}$.

######  Definition 3.5.

For a distribution $P$ and a loss function $\ell$, define the misspecification
gaps:

$\Delta_{1,P}\triangleq{\mathbb{E}}_{P}[\ell(g^{*}_{1,P}(X,Z),Y)]-{\mathbb{E}}_{P}[\ell(f^{*}_{1,P}(X,Z),Y)]\text{
and
}\Delta_{2,P}\triangleq{\mathbb{E}}_{P}[\ell(g^{*}_{2,P}(Z),Y)]-{\mathbb{E}}_{P}[\ell(f^{*}_{2,P}(Z),Y)]$

The misspecification gaps defined in Definition 3.5 quantify the difference
between the limiting predictors $g_{1,P}^{*}$ and $g_{2,P}^{*}$ and the Bayes
predictors $f_{1,P}^{*}$ and $f_{2,P}^{*}$, i.e., give a misspecification
measure for $g^{*}_{1,P}$ and $g^{*}_{2,P}$. Corollary 3.6 implies that STFR
controls Type-I error asymptotically if $\Delta_{2,P}=0$, and guarantees non-
trivial power if the degree of misspecification of $g^{*}_{1,P}$ is not large
compared to the performance difference of the Bayes predictors $\Delta_{P}$,
that is, when $\Delta_{P}-\Delta_{1,P}>0$.

######  Corollary 3.6 (Bounding testing errors).

Suppose we are under the conditions of Theorem 3.4.

(Type-I error) If $H_{0}:X\mathchoice{\mathrel{\hbox
to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}Y\mid Z$ holds, then

$\displaystyle\textstyle{\mathbb{E}}_{P}[\varphi^{\textup{STFR}}_{\alpha}(\mathcal{D}^{(n)}_{te},\mathcal{D}_{tr}^{(m)})]\leq
1-\Phi(\tau_{\alpha}-\sqrt{\frac{n}{\sigma_{P}^{2}}}\Delta_{2,P})+o(1)$

where $o(1)$ denotes uniform convergence over all $P\in\mathcal{P}_{0}$ as
$m\to\infty$.

(Type-II error) In general, we have

$\displaystyle\textstyle
1-{\mathbb{E}}_{P}[\varphi^{\textup{STFR}}_{\alpha}(\mathcal{D}^{(n)}_{te},\mathcal{D}_{tr}^{(m)})]\leq\Phi(\tau_{\alpha}-\sqrt{\frac{n}{\sigma_{P}^{2}}}(\Delta_{P}-\Delta_{1,P}))+o(1)$

where $o(1)$ denotes uniform convergence over all $P\in\mathcal{P}$ as
$m\to\infty$ and
$\Delta_{P}\triangleq{\mathbb{E}}_{P}[\ell(f^{*}_{2,P}(Z),Y)]-{\mathbb{E}}_{P}[\ell(f^{*}_{1,P}(X,Z),Y)].$

##  4 A robust regression-based conditional independence test

In this section, we introduce the Rao-Blackwellized Predictor Test (RBPT), a
misspecification robust conditional independence test based on comparing the
performance of two predictors. The RBPT assumes that we can implicitly or
explicitly approximate the conditional distribution of $X\mid Z$ and does not
require models to be well specified. Because RBPT involves comparing the
performance of two predictors and requires an approximation of the
distribution of $X\mid Z$, we can directly compare it with the STFR [7] and
the conditional randomization/permutation tests (CRT/CPT) [5, 4]. In summary,
RBPT can control Type-I error under relatively weaker assumptions compared to
those and other regression-based tests. Namely, we allow some model
misspecification and can still guarantee (asymptotic) Type-I error control.

The RBPT can be summarized as follows: (i) we train $\hat{g}^{(m)}$ that
predicts $Y$ given $(X,Z)$ using $\mathcal{D}^{(m)}_{tr}$ and some training
algorithm; (ii) we obtain the Rao-Blackwellized predictor $h$ by smoothing
$\hat{g}^{(m)}$,

$h(z)\triangleq{\mathbb{E}}_{P}[\hat{g}^{(m)}(X,Z)\mid
Z=z,\mathcal{D}^{(m)}_{tr}],$

1 Input: (i) Test set
$\mathcal{D}^{(n)}_{te}=\\{(X_{i},Y_{i},Z_{i})\\}_{i=1}^{n}$, (ii) initial
predictor $\hat{g}^{(m)}$, (iii) conditional distribution estimate
$\hat{Q}^{(m)}_{X\mid Z}$, (iv) convex loss function $\ell$;

2Output: p-value $p$;

3For each $i\in[n]$, get
$\hat{h}(Z_{i})=\int\hat{g}^{(m)}(x,Z_{i})d\hat{Q}^{(m)}_{X\mid Z=Z_{i}}(x)$;

4Compute $\Xi^{(n,m)}\triangleq\sqrt{n}\bar{T}^{(n,m)}/\hat{\sigma}^{(n,m)}$
where $\bar{T}^{(n,m)}\triangleq\frac{1}{n}\sum_{i=1}^{n}T^{(m)}_{i}$ with
${T^{(m)}_{i}\triangleq\ell(\hat{h}(Z_{i}),Y_{i})-\ell(\hat{g}^{(m)}(X_{i},Z_{i}),Y_{i})}$
and $\hat{\sigma}^{(n,m)}$ being $\\{T_{i}\\}$’s sample std dev (Eq. 3.1).

return $p=1-\Phi(\Xi^{(n,m)})$.

Algorithm 1 Obtaining $p$-value for the RBPT

then (iii) compare its performance with $\hat{g}^{(m)}$’s using the test set
$\mathcal{D}^{(n)}_{te}$ and a convex loss444In practice, both the (i) test
set and training set sizes, and (ii) the loss function $\ell$ can be chosen
using the heuristic introduced by Dai et al. [7]. function $\ell$ (not
necessarily used to train $\hat{g}^{(m)}$), and (iv) if the performance of
$\hat{g}^{(m)}$ is statistically better than $h$’s, we reject
$H_{0}:X\mathchoice{\mathrel{\hbox to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}Y\mid Z$. The procedure described here bears a
resemblance to the Rao-Blackwellization of estimators. In classical
statistics, the Rao-Blackwell theorem [16] states that by taking the
conditional expectation of an estimator with respect to a sufficient
statistic, we can obtain a better estimator if the loss function is convex. In
our case, the variable $Z$ can be viewed as a "sufficient statistic" for $Y$
under the assumption of conditional independence
$H_{0}:X\mathchoice{\mathrel{\hbox to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}Y\mid Z$. If $H_{0}$ holds and the loss $\ell$
is convex in its first argument, we can show using Jensen’s inequality that
the resulting model $h$ has a lower risk relative to the initial model
$\hat{g}^{(m)}$, i.e.,
${\mathbb{E}}_{P}[\ell(h(Z),Y)\mid\mathcal{D}^{(m)}_{tr}]-{\mathbb{E}}_{P}[\ell(\hat{g}^{(m)}(X,Z),Y)\mid\mathcal{D}^{(m)}_{tr}]\leq
0$. Then, the risk gap in RBPT is non-positive under $H_{0}$ in contrast with
STFR’s risk gap, which we should expect to be always non-negative given the
definition of $\hat{g}_{2}^{(m)}$ in that case. That fact negatively biases
the RBPT test statistic, enabling better Type-I error control and robustness
against misspecification.

In practice, we cannot compute $h$ exactly because $P_{X\mid Z}$ is usually
unknown. Then, we use an approximation $\hat{Q}^{(m)}_{X\mid Z}$, which can be
given explicitly (e.g., using probabilistic classifiers or conditional density
estimators) or implicitly (e.g., using GANs). We assume that
$\hat{Q}^{(m)}_{X\mid Z}$ is obtained using the training set. Thus, the
approximated Rao-Blackwellized predictor is given by

$\displaystyle\textstyle\hat{h}(z)=\int\hat{g}^{(m)}(x,z)d\hat{Q}^{(m)}_{X\mid
Z=z}(x)$

where the integral can be solved numerically in case $\hat{Q}^{(m)}_{X\mid Z}$
has a known density or via Monte Carlo integration in case we can only sample
from $\hat{Q}^{(m)}_{X\mid Z}$. Finally, for a fixed significance level
$\alpha\in(0,1)$, the test $\varphi^{\textup{RBPT}}_{\alpha}$ is given by
Equation 3.2 where the $p$-value is obtained via Algorithm 1.

Before RBPT results, we introduce some assumptions. Let $Q^{*}_{X|Z}$
represent the limiting model for $\hat{Q}^{(m)}_{X\mid Z}$. It is true that
$Q^{*}_{X|Z}$ 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.

######  Assumption 4.1.

There is a function $g^{*}_{P}$, a conditional distribution $Q^{*}_{X|Z}$, and
a constant $\gamma>0$ s.t.

$\displaystyle{\mathbb{E}}_{P}\left[\left\|\hat{g}^{(m)}(Z)-g^{*}_{P}(Z)\right\|_{2}^{2}\Big{|}~{}\mathcal{D}_{tr}^{(m)}\right]=\mathcal{O}_{\mathcal{P}}(m^{-\gamma})\text{
and }{\mathbb{E}}_{P}\left[d_{\text{TV}}(\hat{Q}^{(m)}_{X\mid
Z},Q^{*}_{X|Z})\mid\mathcal{D}_{tr}^{(m)}\right]=\mathcal{O}_{\mathcal{P}}(m^{-\gamma})$

where $d_{\text{TV}}$ denotes the total variation (TV) distance. Additionally,
assume that both $\hat{Q}^{(m)}_{X\mid Z}$ and $Q^{*}_{X\mid Z}$ are dominated
by a common $\sigma$-finite measure which does not depend on $Z$ or $m$. For
example, that common dominating measure could be the Lebesgue measure in
${\mathbb{R}}^{d_{X}}$

Assumption 4.2 imposes additional constraints on the limiting model
$Q^{*}_{X|Z}$. Under that assumption, the limiting models’ misspecification
must be uniformly bounded.

######  Assumption 4.2.

For all $P\in\mathcal{P}$

$\displaystyle\textstyle\chi^{2}\left(Q^{*}_{X|Z}||P_{X\mid
Z}\right)\triangleq\int\frac{dQ^{*}_{X|Z}}{dP_{X\mid Z}}dQ^{*}_{X|Z}-1$

is a well-defined integrable random variable and
$\sup_{P\in\mathcal{P}}{\mathbb{E}}_{P}\left[\chi^{2}\left(Q^{*}_{X|Z}||P_{X\mid
Z}\right)\right]<\infty$.

Assume $\hat{g}^{(m)}$ is chosen from a model class $\mathcal{G}^{(m)}$.
Assumption 4.3 imposes constraints on the model classes
$\\{\mathcal{G}^{(m)}\\}$ and loss function $\ell$.

######  Assumption 4.3.

Assume (i)
$\sup_{g\in\mathcal{G}^{(m)}}\sup_{(x,z)\in\mathcal{X}\times\mathcal{Z}}\left\|g(x,z)\right\|_{1}\leq
M<\infty$, for some $M>0$ for all $m$, and (ii) that $\ell$ is a $L-$Lipschitz
loss function (with respect to its first argument) for a certain $L>0$, i.e.,
for any $\hat{y},\hat{y}^{\prime},y\in\mathcal{Y}$, we have that
$|\ell(\hat{y},y)-\ell(\hat{y}^{\prime},y)|\leq
L\left\|\hat{y}-\hat{y}^{\prime}\right\|_{2}$.

Assumption 4.3 is valid by construction since we choose $\mathcal{G}^{(m)}$
and the loss function $\ell$. That assumption is satisfied when, for example,
(a) models in $\cup_{m}\mathcal{G}^{(m)}$ are bounded, (b)
$\ell(\hat{y},y)=\left\|\hat{y}-y\right\|^{p}_{p}$ with $p\geq 1$, and (c)
$\mathcal{Y}$ is a bounded subset of ${\mathbb{R}}^{d_{Y}}$, i.e., in
classification problems and most of the practical regression problems. The
loss $\ell(\hat{y},y)=\left\|\hat{y}-y\right\|^{p}_{p}$, with $p\geq 1$, is
also convex with respect to its first entry and then a suitable loss for RBPT.
It is important to emphasize that $\ell$ does not need to be the same loss
function used during the training phase. For example, we could use
$\ell(\hat{y},y)=\left\|\hat{y}-y\right\|_{1}$ in classification problems,
where $y$ is a one-hot encoded class label and $\hat{y}$ is a vector of
predicted probabilities given by a model trained using the cross-entropy loss.

######  Theorem 4.4.

Suppose that Assumptions 3.2, 3.3, 4.1, 4.2, and 4.3 hold. If $n$ is a
function of $m$ such that $n\to\infty$ and $n=o(m^{\gamma})$ as $m\to\infty$,
then

$\displaystyle\textstyle{\mathbb{E}}_{P}[\varphi^{\textup{RBPT}}_{\alpha}(\mathcal{D}^{(n)}_{te},\mathcal{D}_{tr}^{(m)})]=1-\Phi(\tau_{\alpha}-\sqrt{\frac{n}{\sigma_{P}^{2}}}\Omega_{P}^{\textup{RBPT}})+o(1)$

where $o(1)$ denotes uniform convergence over all $P\in\mathcal{P}$ as
$m\to\infty$ and
$\Omega_{P}^{\textup{RBPT}}=\Omega_{P,1}^{\textup{RBPT}}-\Omega_{P,2}^{\textup{RBPT}}$
with

$\displaystyle\Omega_{P,1}^{\textup{RBPT}}\triangleq{\mathbb{E}}_{P}$
$\displaystyle\textstyle\left[\ell\left(\int
g_{P}^{*}(x,Z)dQ^{*}_{X|Z}(x),Y\right)\right]-{\mathbb{E}}_{P}\left[\ell\left(\int
g_{P}^{*}(x,Z)dP_{X\mid Z}(x),Y\right)\right]$

and

$\displaystyle\underbrace{\Omega_{P,2}^{\textup{RBPT}}}_{\text{Jensen's
gap}}\triangleq{\mathbb{E}}_{P}$
$\displaystyle\textstyle\big{[}\ell(g_{P}^{*}(X,Z),Y)\big{]}-{\mathbb{E}}_{P}\left[\ell\left(\int
g_{P}^{*}(x,Z)dP_{X\mid Z}(x),Y\right)\right]$

When $H_{0}:X\mathchoice{\mathrel{\hbox
to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}Y\mid Z$ holds and $\ell$ is a strictly convex
loss function, we have that $\Omega_{P,2}^{\textup{RBPT}}>0$, allowing555In
practice, we do not need $\ell$ to be strictly convex for the Jensen’s gap to
be positive. Assuming that $g_{P}^{*}$ depends on $X$ under $H_{0}$ is
necessary, though. That condition is usually true when $g_{P}^{*}$ is
misspecified. some room for $Q^{*}_{X|Z}$ misspecification. That is, from
Theorem 4.4, as long as $\Omega_{P}^{\textup{RBPT}}\leq 0$, i.e., if
$Q^{*}_{X|Z}$’s misspecification (measured by $\Omega_{P,1}^{\textup{RBPT}}$)
is not as big as Jensen’s gap $\Omega_{P,2}$, RBPT has asymptotic Type-I error
control. Uniform asymptotic Type-I error control is possible if
$\sup_{P\in\mathcal{P}_{0}}\Omega_{P}^{\textup{RBPT}}\leq 0$. This is a great
improvement of past work (e.g., STFR, GCM, RESIT, CRT, CPT) since there is no
need for the correct specification of any model if
$\Omega_{P,1}^{\textup{RBPT}}\leq\Omega_{P,2}^{\textup{RBPT}}$, which is a
weaker condition. See however that a small $\Omega_{P,2}^{\textup{RBPT}}$
reduces the room for $Q^{*}_{X|Z}$ misspecification. In the extreme case, when
$g_{P}^{*}$ is the Bayes predictor, and therefore does not depend on $X$ under
$H_{0}$, we need666In this case, Assumption 3.3 is not true. We need to
include artificial noises in the definition of $T_{i}$ as it was done in STFR
by Dai et al. [7]. the correct specification of $Q^{*}_{X|Z}$ as well. On the
other hand, if $g_{P}^{*}$ is close to the Bayes predictor, RBPT has better
power. That imposes an expected trade-off between Type-I error control and
power. To make a comparison with Berrett et al. [4] ’s results in the case of
CRT and CPT, we can express our remark in terms of the TV distance between
$Q^{*}_{X|Z}$ and $P_{X\mid Z}$. It can be shown that if
${\mathbb{E}}_{P}[d_{\text{TV}}(Q^{*}_{X|Z},P_{X\mid
Z})]\leq\Omega_{P,2}^{\textup{RBPT}}/(2ML)$, then Type-I error control is
guaranteed (see Appendix A.5). This contrasts with Berrett et al. [4] ’s
results because ${\mathbb{E}}_{P}[d_{\text{TV}}(Q^{*}_{X|Z},P_{X\mid Z})]=0$
is not needed for a valid test.

We end this section with some relevant observations related to the RBPT.

On RBPT’s power. Like STFR, non-trivial power is guaranteed if the predictor
$g_{P}^{*}$ is good enough. Indeed, the second part of Corollary 3.6 can be
applied for an upper bound on RBPT’s Type-II error.

Semi-supervised learning. Let $Y$ denote a label variable. Situations in which
unlabeled samples $(X_{i},Z_{i})$ are abundant while labeled samples
$(X_{i},Y_{i},Z_{i})$ are scarce happen in real applications of conditional
independence testing [5, 4]. RBPT is well suited for those cases because the
practitioner can use the abundant data to estimate $P_{X\mid Z}$ flexibly.

Running RBPT when it is hard to estimate $P_{X\mid Z}$: the RBPT2. There might
be situations in which it is hard to estimate the full conditional
distribution $P_{X\mid Z}$. An alternative approach would be estimating the RB
predictor directly using a second regressor. After training $\hat{g}^{(m)}$,
we could use the training set, organizing it in pairs
$\\{(Z_{i},\hat{g}^{(m)}(Z_{i},X_{i}))\\}$, to train a second predictor
$\hat{h}$ to predict $\hat{g}^{(m)}(Z,X)$ given $Z$. That predictor could be
trained to minimize the mean-squared error. The model class for $\hat{h}$
should be more complex than those for $\hat{g}^{(m)}$, and then this approach
is effective when unlabeled samples are abundant. After obtaining $\hat{h}$,
the test is conducted normally. We call this version "RBPT2". We include a
note on how to adapt Theorem 4.4 for RBPT2 in Appendix A.6.

##  5 Experiments

In the following experiments, we compare the performance of RBPT/RBPT2 against
relevant benchmarks when the employed predictors are misspecified. We consider
$\alpha=10\%$ and $\ell(\hat{y},y)=(\hat{y}-y)^{2}$. Our benchmarks include
STFR [7], GCM [29], and RESIT [39], which are regression-based CI tests
discussed in detail earlier in this work. Additionally, we consider the
conditional randomization/permutation tests (CRT/CPT) [5, 4], which require
the estimation of $P_{X\mid Z}$.

Simulations. This setup is adapted from Berrett et al. [4]. The data is
obtained as follows:

$\displaystyle\textstyle Z\sim N\left(0,I_{d_{Z}}\right),~{}~{}~{}X\mid Z\sim
N\left((b^{\top}Z)^{2},1\right),~{}~{}~{}Y\mid X,Z\sim
N\left(cX+a^{\top}Z+\gamma(b^{\top}Z)^{2},1\right),$

Figure 2: Type-I error control and power analysis. RBPT, RBPT2, and CPT
generally have better Type-I error control; among the three, RBPT2 and CPT
seem to have better power over RBPT.

where the vectors $a,b\overset{iid}{\sim}N\left(0,I_{d_{Z}}\right)$ and $c$ is
a constant controlling the degree of conditional dependence of $X$ and $Y$
given $Z$. Moreover, $\gamma$ is a parameter that controls how hard
conditional independence testing is: if $\gamma\neq 0$, then Type-I error
control becomes more challenging since $X$ and $Y$ might have a strong
marginal dependence even under $H_{0}$. The training and test sets have sample
sizes of 800 and 200 data points. All predictors we use are linear regressors.
RESIT uses Spearman’s correlation for the test statistic with $B=100$. In
contrast, CRT and CPT use STFR’s test statistic where the $p$-values are given
by conditionally sampling/permuting $100$ times777To run CPT, we use the
Python code in http://www.stat.uchicago.edu/~rina/cpt.html, one MCMC chain,
and kept all the other parameters as used by the authors. assuming
$\hat{Q}_{X\mid Z}=N\left((b^{\top}Z)^{2}+\theta,1\right)$, where $\theta$
controls the level of error when approximating $P_{X\mid Z}$. To obtain
$\hat{h}$ for RBPT, we use either $\hat{Q}_{X\mid Z}$ or a kernel ridge
regression (KRR) with the polynomial kernel to predict $\hat{g}_{1}(X,Z)$ from
$Z$ (RBPT2). To compare methods, we sample the generative parameters $(a,b)$
sample $10$ times, and for each one, we use run $48$ Monte Carlo simulations
to estimate Type-I error rate and power. We report the average ($\pm$ std.
deviation) estimated Type-I error rate/power across the $10$ repetitions. We
include extra results, with different values for $d_{Z}$ and skewed
distribution for $Y\mid X,Z$, in Appendix C.

In the first plot of Figure 2, we set $c=0$ and compare RBPT and RBPT2 with
STFR, GCM, and RESIT. Because it is not straightforward to compare the level
of misspecification between our methods and the benchmarks, we use this as an
opportunity to illustrate Theorem 4.4 and results from Section 3. Fixing
$\theta=0$ for RBPT and using KRR for RBPT2 make $\hat{h}$ close to the actual
$h$ and permits Type-I error control. On the other hand, because the
predictors are misspecified, Type-I error control is violated for STFR, GCM,
and RESIT when $\gamma$ grows. In the second plot, we set $c=\gamma=0$ and
compare RBPT with CRT and CPT, where a robustness comparison can be easily
obtained by introducing errors in $\hat{Q}_{X\mid Z}$ by changing values of
$\theta$. In this case, we can see that RBPT and CPT are more robust to errors
in $\hat{Q}_{X\mid Z}$. Now, we investigate how powerful RBPT and RBPT2 can be
in practice. We compare our methods with CPT, which seems to have practical
robustness against model misspecification. The third plot of Figure 2 shows
that RBPT2 and CPT have similar power while RBPT is slightly more
conservative. We consider that to be a good achievement since it is relatively
hard to use CPT in practice, i.e., we need to know the functional form of the
density function of $\hat{Q}_{X\mid Z}$ and then run an MCMC algorithm, which
can be time-consuming and might not scale well to large problems. Per
iteration, RBPT took $6\cdot 10^{-4}s$ to run, RBPT2 took $5.5\cdot 10^{-1}s$,
STFR took $10^{-3}s$, RESIT took $1.2\cdot 10^{-1}s$, GCM took $6\cdot
10^{-4}s$, CRT took $2.3\cdot 10^{-2}s$, and CPT took $7.7\cdot 10^{-1}s$, all
in a MacBook Air 2020 M1.

Real data experiments. These experiments utilize the car insurance dataset
analyzed by Angwin et al. [2]. The dataset covers four US states (California,
Illinois, Missouri, and Texas) and many companies and aggregates at the ZIP
code level. It includes a risk measure and the insurance cost paid by a
hypothetical customer, with fixed characteristics, from each ZIP code. Each
ZIP code is classified as minority or non-minority based on the proportion of
non-white individuals living in that area. The variables are $Z$, which
represents the driving risk variable; $X$, an indicator of minority ZIP code;
and $Y$, the insurance price. One natural question is whether the null
hypothesis $H_{0}:X\mathchoice{\mathrel{\hbox
to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}Y\mid Z$ holds, i.e., whether there is
discriminatory pricing based on demographics.

---
Figure 3: The first panel shows the Type-I error rates for different methods
in a semi-synthetic setup. RBPT and RBPT2 have better Type-I error control
compared to other methods. The second panel uses the raw data to display the
$p$-value when testing the conditional independence of $X$ and $Y$ given $Z$
across different states. Discrimination against minorities in ZIP codes is
most evident in Illinois, followed by Texas, Missouri, and then California.
Our results align with Angwin et al. [2]’s, suggesting that our method has
good power.

We split the real data experiments into two parts. In the first part, we aim
to compare the Type-I error rate of different methods. To ensure that $H_{0}$
holds, we discretize $Z$ into twenty different values and shuffle the values
of $Y$ for each value of the discrete $Z$. If a method controls Type-I error,
we expect it to reject $H_{0}$ for at most $\alpha=10\%$ of the companies in
each state. In the second part, we aim to evaluate our methods’ power. Since
we do not know the ground truth, we qualitatively compare our results with
those obtained by Angwin et al. [2] in a careful and multi-faceted analysis.
Also, other methods cannot control Type-I error in this dataset; then it does
not make sense to compare with extra baselines here. In this last experiment,
we aggregate the analysis for each state without conditioning on the firm. We
use logistic regression to estimate the distribution of $X\mid Z$ for RBPT,
GCM, CRT, and CPT methods. For RBPT2, we use a CatBoost regressor [24] to
obtain the Rao-Blackwellized predictor. The CRT and CPT methods use the same
test statistics as STFR. We do not include RESIT in this experiment as the
additive model assumption is inappropriate. The first panel888We run the
experiment for 48 different random seeds and report the average Type-I error
rate. of Figure 3 shows that RBPT and RBPT2 methods have better control over
Type-I errors compared to all other methods. The second panel reveals that the
conditional dependence of $X$ and $Y$ given $Z$ (discrimination against
minorities in ZIP codes) was most evident in Illinois, Texas, and Missouri.
The evidence for California is weaker. These results are similar to those
obtained by Angwin et al. [2]; thus, we consider our method to have good
power. Per iteration, RBPT took $10^{-1}s$ to run, RBPT2 took $3\cdot
10^{-1}s$, STFR took $10^{-3}s$, GCM took $10^{-3}s$, CRT took $2.8\cdot
10^{-2}s$, and CPT took $7.9\cdot 10^{-1}s$, all in a MacBook Air 2020 M1.

##  6 Summary and discussion

In this work, we showed theoretically and empirically that widely-used tests
of conditional independence are sensitive to model inductive bias
misspecification. Focusing on the SFTR, we develop a modification based on
Rao-Blackwellization whose Type I error control is more robust to model and
inductive bias misspecification. Potential future research directions may
include developing new extensions to the RBPT, which can make it more
powerful, and understanding how to properly choose the model class for the
RBPT2.

## References

  * Ai et al. [2022] Chunrong Ai, Li-Hsien Sun, Zheng Zhang, and Liping Zhu.  Testing unconditional and conditional independence via mutual information.  _Journal of Econometrics_ , 2022.
  * Angwin et al. [2017] 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.  URL https://www.propublica.org/article/minority-neighborhoods-higher-car-insurance-premiums-white-areas-same-risk.  [Online; last accessed in 09-September-2022].
  * Bellot and van der Schaar [2019] Alexis Bellot and Mihaela van der Schaar.  Conditional independence testing using generative adversarial networks.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Berrett et al. [2020] Thomas B Berrett, Yi Wang, Rina Foygel Barber, and Richard J Samworth.  The conditional permutation test for independence while controlling for confounders.  _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ , 82(1):175–197, 2020.
  * Candes et al. [2018] Emmanuel Candes, Yingying Fan, Lucas Janson, and Jinchi Lv.  Panning for gold:‘model-x’knockoffs for high dimensional controlled variable selection.  _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ , 80(3):551–577, 2018.
  * Cappé et al. [2009] Olivier Cappé, Eric Moulines, and Tobias Rydén.  Inference in hidden markov models.  In _Proceedings of EUSFLAT conference_ , pages 14–16, 2009.
  * Dai et al. [2022] 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\.
  * Doran et al. [2014] Gary Doran, Krikamol Muandet, Kun Zhang, and Bernhard Schölkopf.  A permutation-based kernel conditional independence test.  In _UAI_ , pages 132–141, 2014.
  * D’Amour et al. [2020] Alexander D’Amour, Katherine Heller, Dan Moldovan, Ben Adlam, Babak Alipanahi, Alex Beutel, Christina Chen, Jonathan Deaton, Jacob Eisenstein, Matthew D Hoffman, et al.  Underspecification presents challenges for credibility in modern machine learning.  _Journal of Machine Learning Research_ , 2020.
  * Fukumizu et al. [2007] Kenji Fukumizu, Arthur Gretton, Xiaohai Sun, and Bernhard Schölkopf.  Kernel measures of conditional dependence.  _Advances in neural information processing systems_ , 20, 2007.
  * Glymour et al. [2019] Clark Glymour, Kun Zhang, and Peter Spirtes.  Review of causal discovery methods based on graphical models.  _Frontiers in genetics_ , 10:524, 2019.
  * Hoyer et al. [2008] 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.
  * Kalimeris et al. [2019] 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 in neural information processing systems_ , 32, 2019.
  * Kim et al. [2021] Ilmun Kim, Matey Neykov, Sivaraman Balakrishnan, and Larry Wasserman.  Local permutation tests for conditional independence.  _arXiv preprint arXiv:2112.11666_ , 2021.
  * Kubkowski et al. [2021] Mariusz Kubkowski, Jan Mielniczuk, and Pawel Teisseyre.  How to gain on power: Novel conditional independence tests based on short expansion of conditional mutual information.  _J. Mach. Learn. Res._ , 22:62–1, 2021.
  * Lehmann and Casella [2006] Erich L Lehmann and George Casella.  _Theory of point estimation_.  Springer Science & Business Media, 2006.
  * Lehmann et al. [2005] Erich Leo Lehmann, Joseph P Romano, and George Casella.  _Testing statistical hypotheses_ , volume 3.  Springer, 2005.
  * Li and Fan [2020] Chun Li and Xiaodan Fan.  On nonparametric conditional independence tests for continuous variables.  _Wiley Interdisciplinary Reviews: Computational Statistics_ , 12(3):e1489, 2020.
  * Liu et al. [2022] Molei Liu, Eugene Katsevich, Lucas Janson, and Aaditya Ramdas.  Fast and powerful conditional randomization testing via distillation.  _Biometrika_ , 109(2):277–293, 2022.
  * Marx and Vreeken [2019] Alexander Marx and Jilles Vreeken.  Testing conditional independence on discrete data using stochastic complexity.  In _The 22nd International Conference on Artificial Intelligence and Statistics_ , pages 496–505. PMLR, 2019.
  * Neykov et al. [2021] Matey Neykov, Sivaraman Balakrishnan, and Larry Wasserman.  Minimax optimal conditional independence testing.  _The Annals of Statistics_ , 49(4):2151–2177, 2021.
  * Peters et al. [2014] 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–2053, 2014\.
  * Polo et al. [2022] Felipe Maia Polo, Rafael Izbicki, Evanildo Gomes Lacerda Jr, Juan Pablo Ibieta-Jimenez, and Renato Vicente.  A unified framework for dataset shift diagnostics.  _arXiv preprint arXiv:2205.08340_ , 2022.
  * Prokhorenkova et al. [2018] 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.
  * Resnick [2019] Sidney Resnick.  _A probability path_.  Springer, 2019.
  * Ritov et al. [2017] Ya’acov Ritov, Yuekai Sun, and Ruofei Zhao.  On conditional parity as a notion of non-discrimination in machine learning.  _arXiv preprint arXiv:1706.08519_ , 2017.
  * Runge [2018] Jakob Runge.  Conditional independence testing based on a nearest-neighbor estimator of conditional mutual information.  In _International Conference on Artificial Intelligence and Statistics_ , pages 938–947. PMLR, 2018.
  * Scetbon et al. [2021] Meyer Scetbon, Laurent Meunier, and Yaniv Romano.  An asymptotic test for conditional independence using analytic kernel embeddings.  _arXiv preprint arXiv:2110.14868_ , 2021.
  * Shah and Peters [2020] Rajen D Shah and Jonas Peters.  The hardness of conditional independence testing and the generalised covariance measure.  _The Annals of Statistics_ , 48(3):1514–1538, 2020.
  * Shi et al. [2021] 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.
  * Smith et al. [2020] Samuel Smith, Erich Elsen, and Soham De.  On the generalization benefit of noise in stochastic gradient descent.  In _International Conference on Machine Learning_ , pages 9058–9067. PMLR, 2020.
  * Strobl et al. [2019] Eric V Strobl, Kun Zhang, and Shyam Visweswaran.  Approximate kernel-based conditional independence tests for fast non-parametric causal discovery.  _Journal of Causal Inference_ , 7(1), 2019.
  * Tansey et al. [2022] 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–162, 2022.
  * Tsybakov [2004] Alexandre B Tsybakov.  Introduction to nonparametric estimation, 2009.  _URL https://doi.org/10.1007/b13794. Revised and extended from the_ , 9(10), 2004.
  * Watson and Wright [2021] David S Watson and Marvin N Wright.  Testing conditional independence in supervised learning algorithms.  _Machine Learning_ , 110(8):2107–2129, 2021.
  * Zhang et al. [2019] 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.
  * Zhang et al. [2022] 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.
  * Zhang et al. [2012] Kun Zhang, Jonas Peters, Dominik Janzing, and Bernhard Schölkopf.  Kernel-based conditional independence test and application in causal discovery.  _arXiv preprint arXiv:1202.3775_ , 2012.
  * Zhang et al. [2017] Qinyi Zhang, Sarah Filippi, Seth Flaxman, and Dino Sejdinovic.  Feature-to-feature regression for a two-step conditional independence test.  In _33rd Conference on Uncertainty in Artificial Intelligence, UAI 2017_. Association for Uncertainty in Artificial Intelligence (AUAI), 2017\.

##  Appendix A Extra content

###  A.1 Model misspecification in modern statistics and machine learning

Figure 4: Type-I error rate is contingent on the training algorithm and not
solely on the model classes. Unlike PCR, the LASSO fit provides the correct
inductive bias in high-dimensional regression, controlling Type-I error.

We present a toy experiment to empirically demonstrate how the training
algorithm can prevent us from accurately estimating the Bayes predictor even
when the model class is correctly specified, leading to invalid significance
tests. We work in the context of a high-dimensional (overparameterized)
regression with a training set of $250$ observations and $\geq 300$
covariates. We use the Significance Test of Feature Relevance test999See
Section 3.1 for more details (STFR) [7] to conduct the CI test. The data are
generated as

$Z\sim N(0,I_{300}),~{}X\mid Z\sim N(\beta^{\top}Z,1),~{}Y\mid X,Z\sim
N(\beta^{\top}Z,1)$

where the first thirty entries of $\beta$ are set to 1, and the remaining
entries are zero. See that $X\mathchoice{\mathrel{\hbox
to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}Y\mid 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)$. To perform the STFR test,
we use LASSO ($\left\|\cdot\right\|_{1}$ penalization term added to empirical
squared error) and principal components regression (PCR) to train the linear
predictors. Since $\beta$ is sparse, the LASSO fit provides the correct
inductive bias while PCR leads to misspecification. We set the significance
level to $\alpha=1\%$ and estimate the Type-I error rate for $100$ different
training sets. Figure 4 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 model misspecification in the PCR
case, implying an invalid test most of the time.

###  A.2 Examples on when STFR fails

Examples A.1 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 $\mathcal{G}_{2}$ misspecification, while Type-II error
minimization directly relates to $\mathcal{G}_{1}$ misspecification.

######  Example A.1 (No Type-I error control).

Suppose $Y=Z+Z^{2}+\varepsilon_{y}$ and $X=Z^{2}+\varepsilon_{x}$, where
$\varepsilon_{y},\varepsilon_{x}\sim N(0,1)$ are independent noise variables
and $Z$ has finite variance. Consequently, $X\mathchoice{\mathrel{\hbox
to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}Y\mid Z$. Let $\mathcal{G}_{1}$ and
$\mathcal{G}_{2}$ be the classes of linear regressors with no intercept, i.e.,

$\mathcal{G}_{1}=\\{g_{1}(x,z)=\beta_{x}x+\beta_{z}z:\beta_{x},\beta_{z}\in{\mathbb{R}}\\}\text{
and }\mathcal{G}_{2}=\\{g_{2}(z)=\beta_{z}z:\beta_{z}\in{\mathbb{R}}\\}.$

If $\ell$ denotes the mean squared error, we have that
${\mathbb{E}}_{P}[\ell(g^{*}_{2,P}(Z),Y)]-{\mathbb{E}}_{P}[\ell(g^{*}_{1,P}(X,Z),Y)]>0$
because the model class $\mathcal{G}_{2}$ is misspecified, that is, it does
not contain the Bayes predictor given by the conditional expectation
${\mathbb{E}}[Y\mid Z]$.

######  Example A.2 (Powerless test).

Suppose $Y=Z+\sin(X)+\varepsilon_{y}$, where
$Z,X,\varepsilon_{y}\overset{iid}{\sim}N(0,1)$. Consequently,
$X\not\mathchoice{\mathrel{\hbox to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}Y\mid Z$. Define $\mathcal{G}_{1}$ and
$\mathcal{G}_{2}$ as in Example A.1. If $\ell$ denotes the mean squared error,
we have that101010Because
${\mathbb{E}}_{P}[XY]={\mathbb{E}}_{P}[X{\mathbb{E}}_{P}[Y|X]]={\mathbb{E}}_{P}[X\cdot
0]=0$.
${\mathbb{E}}_{P}[\ell(g^{*}_{2,P}(Z),Y)]-{\mathbb{E}}_{P}[\ell(g^{*}_{1,P}(X,Z),Y)]=0$
even though the different Bayes’ predictors have a difference in performance.
This happens because the model $g^{*}_{1,P}$ is not close enough to the Bayes
predictor ${\mathbb{E}}_{P}[Y\mid X,Z]$.

###  A.3 Generalized Covariance Measure (GCM) test

In the GCM test proposed by Shah and Peters [29], 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. If
$(X,Y,Z)\sim P$, the GCM test relies on the observation that we can always
write

$X=f_{1,P}^{*}(Z)+\epsilon~{}~{}\text{ and }~{}~{}Y=f_{2,P}^{*}(Z)+\eta,$

where $f_{1,P}^{*}(Z)={\mathbb{E}}_{P}[X\mid Z]$ and
$f_{2,P}^{*}(Z)={\mathbb{E}}_{P}[Y\mid Z]$ while the error terms
$\\{\epsilon,\eta\\}$ have zero mean when conditioned on $Z$. Consequently, we
can write ${\mathbb{E}}_{P}[{\sf Cov}_{P}(X,Y\mid
Z)]={\mathbb{E}}_{P}[\epsilon\eta]$. To estimate ${\mathbb{E}}_{P}[{\sf
Cov}_{P}(X,Y\mid Z)]$, we can first fit two models
$\hat{g}^{(m)}_{1}:\mathcal{Z}\to\mathcal{X}$ and
$\hat{g}^{(m)}_{2}:\mathcal{Z}\to\mathcal{Y}$, that approximate $f^{*}_{1,P}$
and $f^{*}_{2,P}$, using the training set $\mathcal{D}^{(m)}_{tr}$, and then
compute an empirical version of
${\mathbb{E}}_{P}[\epsilon\eta]={\mathbb{E}}_{P}[(X-f^{*}_{1,P}(Z))(Y-f^{*}_{2,P}(Z))]$
using $\hat{g}^{(m)}_{1}$, $\hat{g}^{(m)}_{2}$, and $\mathcal{D}^{(n)}_{te}$.

In the GCM test, we reject $H_{0}:X\mathchoice{\mathrel{\hbox
to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}Y\mid Z$ if the statistic
$\Gamma^{(n,m)}\triangleq|\sqrt{n}\bar{T}^{(n,m)}/\hat{\sigma}^{(n,m)}|$
exceeds $\tau_{\alpha/2}\triangleq\Phi^{-1}(1-\alpha/2)$, depending on the
test significance level $\alpha\in(0,1)$. Here, $\bar{T}^{(n,m)}$ and
$\hat{\sigma}^{(n,m)}$ are defined as in 3.1 with
$T^{(m)}_{i}\triangleq(X_{i}-\hat{g}^{(m)}_{1}(Z_{i}))(Y_{i}-\hat{g}^{(m)}_{2}(Z_{i}))$.
If the $p$-value is defined as
$p(\mathcal{D}^{(n)}_{te},\mathcal{D}^{(m)}_{tr})=2(1-\Phi(\Gamma^{(n,m)}))$,
the test
$\varphi_{\alpha}^{\text{GCM}}(\mathcal{D}^{(n)}_{te},\mathcal{D}^{(m)}_{tr})$
is analogously given by Equation 3.2. Like the STFR, the GCM test depends on
the models’ classes and implicitly on the training algorithm. If the limiting
models $g_{1,P}^{*}$ and $g_{2,P}^{*}$ are not $f_{1,P}^{*}$ and
$f_{2,P}^{*}$, then Type-I error control is not guaranteed.

We introduce definitions and assumptions. Assumption A.3 gives a rate of
convergence for the models $\hat{g}_{j}^{(m)}$ in the mean squared error
sense. Definition A.4 gives a definition for the misspecification gaps.

######  Assumption A.3.

There are functions $g^{*}_{1,P}$, $g^{*}_{2,P}$, and a constant $\gamma>0$
such that

$\displaystyle{\mathbb{E}}_{P}\big{[}(\hat{g}_{j}^{(m)}(Z)-g^{*}_{j,P}(Z))^{2}\mid\mathcal{D}_{tr}^{(m)}\big{]}=\mathcal{O}_{\mathcal{P}}(m^{-\gamma}),\text{
for }j=1,2$

######  Definition A.4.

For each $j\in\\{1,2\\}$, define the misspecification gap as
$\delta_{j,P}\triangleq g_{j,P}^{*}-f_{j,P}^{*}$.

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 $n$ is a function of $m$
such that $n\to\infty$ and $n=o(m^{\gamma})$ as $m\to\infty$, then

$\displaystyle{\mathbb{E}}_{P}[\varphi^{\textup{GCM}}_{\alpha}(\mathcal{D}^{(n)}_{te},\mathcal{D}^{(m)}_{tr})]$
$\displaystyle=1-\Phi\left(\tau_{\alpha/2}-\sqrt{\frac{n}{\sigma_{P}^{2}}}\Omega_{P}^{\textup{GCM}}\right)+\Phi\left(-\tau_{\alpha/2}-\sqrt{\frac{n}{\sigma_{P}^{2}}}\Omega_{P}^{\textup{GCM}}\right)+o(1)$

where $o(1)$ denotes uniform convergence over all $P\in\mathcal{P}$ as
$m\to\infty$ and

$\Omega_{P}^{\textup{GCM}}\triangleq{\mathbb{E}}_{P}[{\sf Cov}_{P}(X,Y\mid
Z)]+{\mathbb{E}}_{P}[\delta_{1,P}(Z)\delta_{2,P}(Z)]$

From Theorem A.5, it is possible to verify that if $\delta_{j,P}(Z)$ is zero
for at least one $j\in\\{1,2\\}$, 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 a double-robustness property of the GCM, which is not
present111111This property is clear in our result because we consider data
splitting. in Shah and Peters [29]. If
${\mathbb{E}}_{P}[\delta_{1,P}(Z)\delta_{2,P}(Z)]\neq 0$, then
${\mathbb{E}}_{P}[\varphi^{\textup{GCM}}_{\alpha}(\mathcal{D}^{(n)}_{te},\mathcal{D}^{(m)}_{tr})]\to
1$ as $m\to\infty$ even when $H_{0}:X\mathchoice{\mathrel{\hbox
to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}Y\mid Z$. Under the alternative, if
$\Omega_{P}^{\textup{GCM}}\neq 0$, Type-II error approaches $0$
asymptotically.

###  A.4 REgression with Subsequent Independence Test (RESIT)

As revisited by Zhang et al. [39], 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 $Z$ to be
independent. When that assumption is reasonable, one advantage of RESIT over
GCM is that it has power against a broader set of alternatives. In this
section, we use a permutation test [17, Example 15.2.3] to assess the
independence of residuals. We analyse RESIT’s Type-I error control.

If $(X,Y,Z)\sim P$ and $(X,Y)$ can be modeled as an additive noise model
(ANM), that is, we can write

$\displaystyle X=f_{1,P}^{*}(Z)+\epsilon~{}~{}\text{ and
}~{}~{}Y=f_{2,P}^{*}(Z)+\eta,$ (A.1)

where $f_{1,P}^{*}(Z)={\mathbb{E}}_{P}[X\mid Z]$,
$f_{2,P}^{*}(Z)={\mathbb{E}}_{P}[Y\mid Z]$, and the error terms
$(\epsilon,\eta)$ are independent of $Z$, it is possible to show that
$X\mathchoice{\mathrel{\hbox to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}Y\mid
Z\Leftrightarrow\epsilon\mathchoice{\mathrel{\hbox
to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}\eta.$ To facilitate our analysis121212In
practice, data splitting is not necessary. However, this procedure helps when
theoretically analyzing the method., we consider first fitting two models
$\hat{g}^{(m)}_{1}$ and $\hat{g}^{(m)}_{2}$ that approximate $f^{*}_{1,P}$ and
$f^{*}_{2,P}$ using the training set $\mathcal{D}^{(m)}_{tr}$ and then test
the independence of the residuals131313We omit the residuals superscript to
ease notation. $\hat{\epsilon}_{i}=X_{i}-\hat{g}^{(m)}_{1}(Z_{i})$ and
$\hat{\eta}_{i}=Y_{i}-\hat{g}^{(m)}_{2}(Z_{i})$ using the test set
$\mathcal{D}^{(n)}_{te}$. Define (i)
$(\bm{\hat{\epsilon}},\bm{\hat{\eta}})\triangleq\\{(\hat{\epsilon}_{i},\hat{\eta}_{i})\\}_{i=1}^{n}$
(test set residuals vertically stacked in matrix form) and (ii)
$(\bm{\hat{\epsilon}},\bm{\hat{\eta}})^{(b)}$ as one of the $B$ permutations,
i.e., consider that we fix $\bm{\hat{\epsilon}}$ and permute $\bm{\hat{\eta}}$
row-wise. Let $\Psi$ be a test statistic and
$\Psi((\bm{\hat{\epsilon}},\bm{\hat{\eta}}))$ and
$\Psi((\bm{\hat{\epsilon}},\bm{\hat{\eta}})^{(b)})$ its evaluation on the
original residuals and the $b$-the permuted set. If the permutation $p$-value
is given by

$\displaystyle
p(\mathcal{D}^{(n)}_{te},\mathcal{D}^{(m)}_{tr})=\frac{1+\sum_{b=1}^{B}\mathds{1}[\Psi((\bm{\hat{\epsilon}},\bm{\hat{\eta}})^{(b)})\geq\Psi((\bm{\hat{\epsilon}},\bm{\hat{\eta}}))]}{1+B}$
(A.2)

a test $\varphi^{\textup{RESIT}}_{\alpha}$ aiming level $\alpha\in(0,1)$ is
given by Equation 3.2.

Similarly to STFR and GCM, we consider $g_{1,P}^{*}$ and $g_{2,P}^{*}$ to be
the limiting models for $\hat{g}^{(m)}_{1}$ and $\hat{g}^{(m)}_{2}$. Different
from GCM, both models $g_{1,P}^{*}$ and $g_{2,P}^{*}$ are multi-output since
$X$ and $Y$ are not necessarily univariate.

Now, we introduce some assumptions before we present our result for RESIT.
Assumption A.6 gives a rate of convergence for the models $\hat{g}_{j}^{(m)}$
in the mean squared error sense.

######  Assumption A.6.

There are models $g_{1,P}^{*}$, $g_{2,P}^{*}$, and a constant $\gamma>0$ such
that

$\displaystyle{\mathbb{E}}_{P}\left[\left\|\hat{g}_{j}^{(m)}(Z)-g^{*}_{j,P}(Z)\right\|_{2}^{2}\Big{|}~{}\mathcal{D}_{tr}^{(m)}\right]=\mathcal{O}_{\mathcal{P}_{0}}(m^{-\gamma}),~{}~{}j=1,2$

Assumption A.7 puts more structure on the distributions of the error terms
$(\epsilon,\eta)$ and is a mild assumption.

######  Assumption A.7.

Assume that for all $P\in\mathcal{P}_{0}$, the distribution of
$(\epsilon,\eta)$, $P_{\epsilon,\eta}$, is absolutely continuous with respect
to the Lebesgue measure in ${\mathbb{R}}^{d_{X}}\times{\mathbb{R}}^{d_{Y}}$
with $L$-Lipschitz density $p_{\epsilon,\eta}$ for a certain $L>0$. That is,
for any $e_{1},e_{2}\in{\mathbb{R}}^{d_{X}}$ and
$h_{1},h_{2}\in{\mathbb{R}}^{d_{Y}}$, we have

$\displaystyle|p_{\epsilon,\eta}(e_{1},h_{1})-p_{\epsilon,\eta}(e_{2},h_{2})|\leq
L\left\|(e_{1},h_{1})-(e_{2},h_{2})\right\|_{2}$

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\in\mathcal{P}_{0}$. This assumption is
realistic in most practical cases.

######  Assumption A.8.

There is bounded Borel set $A\in\mathcal{B}({\mathbb{R}}^{d_{X}\times d_{Y}})$
such that

$\inf_{P\in\mathcal{P}_{0}}{\mathbb{P}}_{P}\left((X,Y)\in A\right)=1$

and

$\inf_{P\in\mathcal{P}_{0}}\inf_{g_{1},g_{2}}{\mathbb{P}}_{P}\left((g_{1}(Z),g_{2}(Z))\in
A\right)=1$

Here, $\inf_{g_{1},g_{2}}$ 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)
$\epsilon^{*}\triangleq\epsilon-\delta_{1,P}(Z_{i})$ and
$\eta^{*}\triangleq\eta-\delta_{2,P}(Z_{i})$, where the misspecification gaps
are given as in Definition A.4; (ii) $d_{\text{TV}}$ represent the total
variation (TV) distance between two probability distributions [34]; and (iii)
the superscript $n$, e.g., in $P^{n}_{\epsilon^{*},\eta^{*}}$, represent a
product measure.

######  Theorem A.9.

Under Assumptions A.6, A.7, and A.8, if $H_{0}:X\mathchoice{\mathrel{\hbox
to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}Y\mid Z$ holds and $n$ is a function of $m$
such that $n\to\infty$ and $n=o(m^{\frac{\gamma}{2}})$ as $m\to\infty$, then

$\displaystyle{\mathbb{E}}_{P}[\varphi^{\textup{RESIT}}_{\alpha}(\mathcal{D}^{(n)}_{te},\mathcal{D}^{(m)}_{tr})]\leq\alpha+\min\\{d_{\text{TV}}(P^{n}_{\epsilon^{*},\eta^{*}},P^{n}_{\epsilon,\eta^{*}}),d_{\text{TV}}(P^{n}_{\epsilon^{*},\eta^{*}},P^{n}_{\epsilon^{*},\eta})\\}+o(1)$

where $o(1)$ denotes uniform convergence over all $P\in\mathcal{P}_{0}$ as
$m\to\infty$.

From Theorem A.9, we can see that if at least one of the misspecification gaps
$\delta_{1,P}$ or $\delta_{2,P}$ is null, then
${\mathbb{E}}_{P}[\varphi^{\textup{RESIT}}_{\alpha}(\mathcal{D}^{(n)}_{te},\mathcal{D}^{(m)}_{tr})]\leq\alpha$
under $H_{0}:X\mathchoice{\mathrel{\hbox
to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}Y\mid Z$. This can be seen as a double-
robustness property of the RESIT. If none of the misspecification gaps are
null, we do not have any guarantees on RESIT’s Type-I error control. It can be
shown that the proposed upper bound converges to $1$.

###  A.5 RBPT extra derivation

Let $\mu_{X}$ be a dominating measure of $Q^{*}_{X\mid Z}$ and $P_{X\mid Z}$
that does not depend on $Z$. Let $q^{*}_{X\mid Z},p_{X\mid Z}$ be
$Q^{*}_{X|Z},P_{X\mid Z}$ densities with respect to $\mu_{X}$.

$\displaystyle\Omega_{P,1}^{\textup{RBPT}}$
$\displaystyle={\mathbb{E}}_{P}\Bigg{[}\ell\left(\int
g_{P}^{*}(x,Z)dQ^{*}_{X|Z}(x),Y\right)-\ell\left(\int g_{P}^{*}(x,Z)dP_{X\mid
Z}(x),Y\right)\Bigg{]}$ $\displaystyle\leq L\cdot{\mathbb{E}}_{P}\left\|\int
g_{P}^{*}(x,Z)dQ^{*}_{X|Z}(x)-\int g_{P}^{*}(x,Z)dP_{X\mid Z}(x)\right\|_{2}$
$\displaystyle\leq L\cdot{\mathbb{E}}_{P}\left\|\int
g_{P}^{*}(x,Z)dQ^{*}_{X|Z}(x)-\int g_{P}^{*}(x,Z)dP_{X\mid Z}(x)\right\|_{1}$
$\displaystyle=L\cdot{\mathbb{E}}_{P}\left\|\int
g_{P}^{*}(x,Z)(q^{*}_{X|Z}(x|Z)-p_{X\mid Z}(x|Z))d\mu_{X}(x)\right\|_{1}$
$\displaystyle\leq
L\cdot{\mathbb{E}}_{P}\int\left\|g_{P}^{*}(x,Z)\right\|_{1}|q^{*}_{X|Z}(x|Z)-p_{X\mid
Z}(x|Z)|d\mu_{X}(x)$ $\displaystyle\leq
ML\cdot{\mathbb{E}}_{P}\int|q^{*}_{X|Z}(x|Z)-p_{X\mid Z}(x|Z)|d\mu_{X}(x)$
$\displaystyle=2ML\cdot{\mathbb{E}}_{P}[d_{\text{TV}}(Q^{*}_{X|Z},P_{X\mid
Z})]$

If

${\mathbb{E}}_{P}[d_{\text{TV}}(Q^{*}_{X|Z},P_{X\mid
Z})]\leq\Omega_{P,2}^{\textup{RBPT}}/(2ML)$

then

$\Omega^{\textup{RBPT}}_{P}\leq 0$

###  A.6 How to obtain a result for RBPT2?

We informally give some ideas on extending Theorem 4.4. Theorem 4.4 states
that

$\displaystyle{\mathbb{E}}_{P}[\varphi^{\textup{RBPT}}_{\alpha}(\mathcal{D}^{(n)}_{te},\mathcal{D}_{tr}^{(m)})]=1-\Phi\left(\tau_{\alpha}-\sqrt{\frac{n}{\sigma_{P}^{2}}}\Omega_{P}^{\textup{RBPT}}\right)+o(1)$

where
$\Omega_{P}^{\textup{RBPT}}=\Omega_{P,1}^{\textup{RBPT}}-\Omega_{P,2}^{\textup{RBPT}}$
with

$\displaystyle\Omega_{P,1}^{\textup{RBPT}}\triangleq{\mathbb{E}}_{P}$
$\displaystyle\Bigg{[}\ell\left(\int
g_{P}^{*}(x,Z)dQ^{*}_{X|Z}(x),Y\right)\Bigg{]}-{\mathbb{E}}_{P}\Bigg{[}\ell\left(\int
g_{P}^{*}(x,Z)dP_{X\mid Z}(x),Y\right)\Bigg{]}$

and

$\displaystyle\Omega_{P,2}^{\textup{RBPT}}\triangleq{\mathbb{E}}_{P}$
$\displaystyle\big{[}\ell(g_{P}^{*}(X,Z),Y)\big{]}-{\mathbb{E}}_{P}\Bigg{[}\ell\left(\int
g_{P}^{*}(x,Z)dP_{X\mid Z}(x),Y\right)\Bigg{]}$

If we wanted to adapt that result for RBPT2, we would have to redefine
$\Omega_{P,1}^{\textup{RBPT}}$. The analogue of $\Omega_{P,1}^{\textup{RBPT}}$
for RBPT2 would be

$\displaystyle\Omega_{P,1}^{\textup{RBPT2}}\triangleq{\mathbb{E}}_{P}$
$\displaystyle\Bigg{[}\ell\left(\tilde{{\mathbb{E}}}_{P}\left[g_{P}^{*}(X,Z)\mid
Z\right],Y\right)\Bigg{]}-{\mathbb{E}}_{P}\Bigg{[}\ell\left({\mathbb{E}}_{P}\left[g_{P}^{*}(X,Z)\mid
Z\right],Y\right)\Bigg{]}$

where $\tilde{{\mathbb{E}}}_{P}\left[g_{P}^{*}(X,Z)\mid Z=z\right]$ denotes
the limiting regression model to predict $g_{P}^{*}(X,Z)$ given $Z$. If we
assume the existence of a big unlabeled dataset, deriving a result might be
easier as we can avoid the asymptotic details on the convergence of the second
regression model by assuming that the limiting Rao-Blackwellization model, for
a fixed initial predictor, is known. The only challenge is proving the
convergence of $\tilde{{\mathbb{E}}}_{P}\left[\hat{g}(X,Z)\mid Z\right]$ to
$\tilde{{\mathbb{E}}}_{P}\left[g_{P}^{*}(X,Z)\mid Z\right]$. With the proper
assumptions and sufficient structure, the result can be achieved.

##  Appendix B Technical proofs

###  B.1 STFR

######  Lemma B.1.

Assume we are under the conditions of Theorem 3.4. Then:

$(\hat{\sigma}^{(n,m)})^{2}-{\sf
Var}_{P}[T^{(m)}_{1}\mid\mathcal{D}_{tr}^{(m)}]=o_{\mathcal{P}}(1)\text{ as
}m\to\infty$

###### Proof.

First, see that for an arbitrary $\varepsilon>0$, there must be141414Because
of the definition of $\sup$. a sequence of probability measures in
$\mathcal{P}$, $(P^{(m)})_{m\in\mathbb{N}}$, such that

$\displaystyle\sup_{P\in\mathcal{P}}{\mathbb{P}}_{P}\left[\left|(\hat{\sigma}^{(n,m)})^{2}-{\sf
Var}_{P}[T^{(m)}_{1}\mid\mathcal{D}_{tr}^{(m)}]\right|>\varepsilon\right]\leq{\mathbb{P}}_{P^{(m)}}\left[\left|(\hat{\sigma}^{(n,m)})^{2}-{\sf
Var}_{P^{(m)}}[T^{(m)}_{1}\mid\mathcal{D}_{tr}^{(m)}]\right|>\varepsilon\right]+\frac{1}{m}$

Pick one of such sequences. Then, to prove that
$(\hat{\sigma}^{(n,m)})^{2}-{\sf
Var}_{P}[T^{(m)}_{1}\mid\mathcal{D}_{tr}^{(m)}]=o_{\mathcal{P}}(1)\text{ as
}m\to\infty$, it suffices to show that

${\mathbb{P}}_{P^{(m)}}\left[\left|(\hat{\sigma}^{(n,m)})^{2}-{\sf
Var}_{P^{(m)}}[T^{(m)}_{1}\mid\mathcal{D}_{tr}^{(m)}]\right|>\varepsilon\right]\to
0\text{ as }m\to\infty$

Now, expanding $(\hat{\sigma}^{(n,m)})^{2}$ we get

$\displaystyle(\hat{\sigma}^{(n,m)})^{2}$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}(T^{(m)}_{i})^{2}-\left(\frac{1}{n}\sum_{i=1}^{n}T^{(m)}_{i}\right)^{2}$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\left[(T^{(m)}_{i})^{2}-{\mathbb{E}}_{P^{(m)}}[(T^{(m)}_{1})^{2}\mid\mathcal{D}_{tr}^{(m)}]\right]+{\mathbb{E}}_{P^{(m)}}[(T^{(m)}_{1})^{2}\mid\mathcal{D}_{tr}^{(m)}]-\left(\frac{1}{n}\sum_{i=1}^{n}T^{(m)}_{i}\right)^{2}$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\left[(T^{(m)}_{i})^{2}-{\mathbb{E}}_{P^{(m)}}[(T^{(m)}_{1})^{2}\mid\mathcal{D}_{tr}^{(m)}]\right]-\left(\frac{1}{n}\sum_{i=1}^{n}T^{(m)}_{i}-{\mathbb{E}}_{P^{(m)}}[T^{(m)}_{1}\mid\mathcal{D}_{tr}^{(m)}]\right)^{2}$
$\displaystyle~{}~{}~{}~{}-2\left(\frac{1}{n}\sum_{i=1}^{n}T^{(m)}_{i}{\mathbb{E}}_{P^{(m)}}[T^{(m)}_{1}\mid\mathcal{D}_{tr}^{(m)}]-({\mathbb{E}}_{P^{(m)}}[T^{(m)}_{1}\mid\mathcal{D}_{tr}^{(m)}])^{2}\right)+{\sf
Var}_{P^{(m)}}[T^{(m)}_{1}\mid\mathcal{D}_{tr}^{(m)}]$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\left[(T^{(m)}_{i})^{2}-{\mathbb{E}}_{P^{(m)}}[(T^{(m)}_{1})^{2}\mid\mathcal{D}_{tr}^{(m)}]\right]-\left(\frac{1}{n}\sum_{i=1}^{n}T^{(m)}_{i}-{\mathbb{E}}_{P^{(m)}}[T^{(m)}_{1}\mid\mathcal{D}_{tr}^{(m)}]\right)^{2}$
$\displaystyle~{}~{}~{}~{}-2{\mathbb{E}}_{P^{(m)}}[T^{(m)}_{1}\mid\mathcal{D}_{tr}^{(m)}]\left(\frac{1}{n}\sum_{i=1}^{n}T^{(m)}_{i}-{\mathbb{E}}_{P^{(m)}}[T^{(m)}_{1}\mid\mathcal{D}_{tr}^{(m)}]\right)+{\sf
Var}_{P^{(m)}}[T^{(m)}_{1}\mid\mathcal{D}_{tr}^{(m)}]$

Then,

$\displaystyle(\hat{\sigma}^{(n,m)})^{2}-{\sf
Var}_{P^{(m)}}[T^{(m)}_{1}\mid\mathcal{D}_{tr}^{(m)}]=$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\left[(T^{(m)}_{i})^{2}-{\mathbb{E}}_{P^{(m)}}[(T^{(m)}_{1})^{2}\mid\mathcal{D}_{tr}^{(m)}]\right]-\left(\frac{1}{n}\sum_{i=1}^{n}T^{(m)}_{i}-{\mathbb{E}}_{P^{(m)}}[T^{(m)}_{1}\mid\mathcal{D}_{tr}^{(m)}]\right)^{2}$
$\displaystyle~{}~{}~{}~{}-2{\mathbb{E}}_{P^{(m)}}[T^{(m)}_{1}\mid\mathcal{D}_{tr}^{(m)}]\left(\frac{1}{n}\sum_{i=1}^{n}T^{(m)}_{i}-{\mathbb{E}}_{P^{(m)}}[T^{(m)}_{1}\mid\mathcal{D}_{tr}^{(m)}]\right)$

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

  * •

$\frac{1}{n}\sum_{i=1}^{n}\left[(T^{(m)}_{i})^{2}-{\mathbb{E}}_{P^{(m)}}[(T^{(m)}_{1})^{2}\mid\mathcal{D}_{tr}^{(m)}]\right]=o_{p}(1)$

  * •

$\left(\frac{1}{n}\sum_{i=1}^{n}T^{(m)}_{i}-{\mathbb{E}}_{P^{(m)}}[T^{(m)}_{1}\mid\mathcal{D}_{tr}^{(m)}]\right)^{2}=o_{p}(1)$

  * •

$\underbrace{2{\mathbb{E}}_{P^{(m)}}[T^{(m)}_{1}\mid\mathcal{D}_{tr}^{(m)}]}_{\mathcal{O}_{p}(1)\text{
(Assumption
\ref{assump:assump2_stfr})}}\left(\frac{1}{n}\sum_{i=1}^{n}T^{(m)}_{i}-{\mathbb{E}}_{P^{(m)}}[T^{(m)}_{1}\mid\mathcal{D}_{tr}^{(m)}]\right)=o_{p}(1)$

and then

$\displaystyle\sup_{P\in\mathcal{P}}{\mathbb{P}}_{P}\left[\left|(\hat{\sigma}^{(n,m)})^{2}-{\sf
Var}_{P}[T^{(m)}_{1}\mid\mathcal{D}_{tr}^{(m)}]\right|>\varepsilon\right]\leq{\mathbb{P}}_{P^{(m)}}\left[\left|(\hat{\sigma}^{(n,m)})^{2}-{\sf
Var}_{P^{(m)}}[T^{(m)}_{1}\mid\mathcal{D}_{tr}^{(m)}]\right|>\varepsilon\right]+\frac{1}{m}\to
0$

$\text{ as }m\to\infty$, i.e.,

$(\hat{\sigma}^{(n,m)})^{2}-{\sf
Var}_{P}[T^{(m)}_{1}\mid\mathcal{D}_{tr}^{(m)}]=o_{\mathcal{P}}(1)\text{ as
}m\to\infty$

Conditions to use the law of large numbers. Let $(P^{(m)})_{m\in\mathbb{N}}$
be an arbitrary sequence of probability measures in $\mathcal{P}$. Define our
triangular arrays as $\left\\{V^{(m)}_{i,1}\right\\}_{1\leq i\leq n}$ and
$\left\\{V^{(m)}_{i,2}\right\\}_{1\leq i\leq n}$, where
$V^{(m)}_{i,1}\triangleq
T^{(m)}_{i}-{\mathbb{E}}_{P^{(m)}}[T^{(m)}_{1}\mid\mathcal{D}_{tr}^{(m)}]$ and
$V^{(m)}_{i,2}\triangleq(T^{(m)}_{i})^{2}-{\mathbb{E}}_{P^{(m)}}[(T^{(m)}_{1})^{2}\mid\mathcal{D}_{tr}^{(m)}]$.
Now, we comment on the conditions for the law of large numbers [6, Corollary
9.5.6]:

  1. 1.

This condition naturally applies by definition and because of Assumption 3.2.

  2. 2.

From Assumption 3.2 and Resnick [25, Example 6.5.2],

$\displaystyle{\mathbb{E}}_{P^{(m)}}\left[\left|V^{(m)}_{i,1}\right|\mid\mathcal{D}_{tr}^{(m)}\right]\leq{\mathbb{E}}_{P^{(m)}}\left[\left|T^{(m)}_{i}\right|\mid\mathcal{D}_{tr}^{(m)}\right]+\left|{\mathbb{E}}_{P^{(m)}}[T^{(m)}_{1}\mid\mathcal{D}_{tr}^{(m)}]\right|\leq
2{\mathbb{E}}_{P^{(m)}}\left[\left|T^{(m)}_{i}\right|\mid\mathcal{D}_{tr}^{(m)}\right]=\mathcal{O}_{p}(1)$

and

$\displaystyle{\mathbb{E}}_{P^{(m)}}\left[\left|V^{(m)}_{i,2}\right|\mid\mathcal{D}_{tr}^{(m)}\right]\leq
2{\mathbb{E}}_{P^{(m)}}\left[(T^{(m)}_{i})^{2}\mid\mathcal{D}_{tr}^{(m)}\right]=\mathcal{O}_{p}(1)$

  3. 3.

Fix any $\epsilon>0$ and let $k$ be defined as in Assumption 3.2. See that

$\displaystyle{\mathbb{E}}_{P^{(m)}}\left[\left|V^{(m)}_{i,1}\right|\mathds{1}[|V^{(m)}_{i,1}|\geq\epsilon
n]\mid\mathcal{D}_{tr}^{(m)}\right]$
$\displaystyle={\mathbb{E}}_{P^{(m)}}\left[\left|V^{(m)}_{i,1}\right|\mathds{1}[(|V^{(m)}_{i,1}|/(\epsilon
n))^{k}\geq 1]\mid\mathcal{D}_{tr}^{(m)}\right]$
$\displaystyle\leq\frac{1}{(n\epsilon)^{k}}{\mathbb{E}}_{P^{(m)}}\left[|V^{(m)}_{i,1}|^{1+k}\mid\mathcal{D}_{tr}^{(m)}\right]$
$\displaystyle=\frac{1}{(n\epsilon)^{k}}{\mathbb{E}}_{P^{(m)}}\left[|T^{(m)}_{i}-{\mathbb{E}}_{P^{(m)}}[T^{(m)}_{1}\mid\mathcal{D}_{tr}^{(m)}]|^{1+k}\mid\mathcal{D}_{tr}^{(m)}\right]$
$\displaystyle\leq\frac{1}{(n\epsilon)^{k}}\left\\{{\mathbb{E}}_{P^{(m)}}\left[|T^{(m)}_{i}|^{1+k}\mid\mathcal{D}_{tr}^{(m)}\right]^{\frac{1}{1+k}}+{\mathbb{E}}_{P^{(m)}}\left[|T^{(m)}_{i}|\mid\mathcal{D}_{tr}^{(m)}\right]\right\\}^{1+k}$
$\displaystyle=\frac{1}{(n\epsilon)^{k}}\mathcal{O}_{p}(1)$
$\displaystyle=o_{p}(1)$

where the third inequality is obtained via Minkowski Inequality [25] and the
fifth step is an application of Assumption 3.2 and Resnick [25, Example
6.5.2]. Analogously, define $k^{\prime}=k/2$ and see that

$\displaystyle{\mathbb{E}}_{P^{(m)}}\left[\left|V^{(m)}_{i,2}\right|\mathds{1}[|V^{(m)}_{i,2}|\geq\epsilon
n]\mid\mathcal{D}_{tr}^{(m)}\right]$
$\displaystyle={\mathbb{E}}_{P^{(m)}}\left[\left|V^{(m)}_{i,2}\right|\mathds{1}[(|V^{(m)}_{i,2}|/(\epsilon
n))^{k^{\prime}}\geq 1]\mid\mathcal{D}_{tr}^{(m)}\right]$
$\displaystyle\leq\frac{1}{(n\epsilon)^{k^{\prime}}}{\mathbb{E}}_{P^{(m)}}\left[|V^{(m)}_{i,2}|^{1+k^{\prime}}\mid\mathcal{D}_{tr}^{(m)}\right]$
$\displaystyle=\frac{1}{(n\epsilon)^{k^{\prime}}}{\mathbb{E}}_{P^{(m)}}\left[|(T^{(m)}_{i})^{2}-{\mathbb{E}}_{P^{(m)}}[(T^{(m)}_{1})^{2}\mid\mathcal{D}_{tr}^{(m)}]|^{1+k^{\prime}}\mid\mathcal{D}_{tr}^{(m)}\right]$
$\displaystyle\leq\frac{1}{(n\epsilon)^{k^{\prime}}}\left\\{{\mathbb{E}}_{P^{(m)}}\left[(T^{(m)}_{i})^{2(1+k^{\prime})}\mid\mathcal{D}_{tr}^{(m)}\right]^{\frac{1}{1+k^{\prime}}}+{\mathbb{E}}_{P^{(m)}}\left[(T^{(m)}_{i})^{2}\mid\mathcal{D}_{tr}^{(m)}\right]\right\\}^{1+k^{\prime}}$
$\displaystyle=\frac{1}{(n\epsilon)^{k^{\prime}}}\left\\{{\mathbb{E}}_{P^{(m)}}\left[(T^{(m)}_{i})^{2+k}\mid\mathcal{D}_{tr}^{(m)}\right]^{\frac{1}{1+k^{\prime}}}+{\mathbb{E}}_{P^{(m)}}\left[(T^{(m)}_{i})^{2}\mid\mathcal{D}_{tr}^{(m)}\right]\right\\}^{1+k^{\prime}}$
$\displaystyle=\frac{1}{(n\epsilon)^{k^{\prime}}}\mathcal{O}_{p}(1)$
$\displaystyle=o_{p}(1)$

∎

Theorem 3.4. Suppose that Assumptions 3.1, 3.2, and 3.3 hold. If $n$ is a
function of $m$ such that $n\to\infty$ and $n=o(m^{2\gamma})$ as $m\to\infty$,
then

$\displaystyle{\mathbb{E}}_{P}[\varphi^{\textup{STFR}}_{\alpha}(\mathcal{D}^{(n)}_{te},\mathcal{D}_{tr}^{(m)})]=1-\Phi\left(\tau_{\alpha}-\sqrt{\frac{n}{\sigma_{P}^{2}}}\Omega_{P}^{\textup{STFR}}\right)+o(1)$

where $o(1)$ denotes uniform convergence over all $P\in\mathcal{P}$ as
$m\to\infty$ and

$\Omega_{P}^{\textup{STFR}}\triangleq{\mathbb{E}}_{P}[\ell(g^{*}_{2,P}(Z),Y)]-{\mathbb{E}}_{P}[\ell(g^{*}_{1,P}(X,Z),Y)]$

###### Proof.

First, note that there must be151515Because of the definition of $\sup$. a
sequence of probability measures in $\mathcal{P}$,
$(P^{(m)})_{m\in\mathbb{N}}$, such that

$\displaystyle\sup_{P\in\mathcal{P}}\left|{\mathbb{E}}_{P}[\varphi^{\textup{STFR}}_{\alpha}(\mathcal{D}^{(n)}_{te},\mathcal{D}_{tr}^{(m)})]-1+\Phi\left(\tau_{\alpha}-\sqrt{\frac{n}{\sigma_{P}^{2}}}\Omega_{P}^{\textup{STFR}}\right)\right|\leq\left|{\mathbb{E}}_{P^{(m)}}[\varphi^{\textup{STFR}}_{\alpha}(\mathcal{D}^{(n)}_{te},\mathcal{D}_{tr}^{(m)})]-1+\Phi\left(\tau_{\alpha}-\sqrt{\frac{n}{\sigma_{P^{(m)}}^{2}}}\Omega_{P^{(m)}}^{\textup{STFR}}\right)\right|+\frac{1}{m}$

Then, it suffices to show that the RHS vanishes when we consider such a
sequence $(P^{(m)})_{m\in\mathbb{N}}$.

Now, let us first decompose the test statistic $\Lambda^{(n,m)}$ in the
following way:

$\displaystyle\Lambda^{(n,m)}\triangleq$
$\displaystyle\triangleq\frac{\sqrt{n}\bar{T}^{(n,m)}}{\hat{\sigma}^{(n,m)}}$
$\displaystyle=\frac{\sqrt{n}\Big{(}\bar{T}^{(n,m)}-{\mathbb{E}}_{P^{(m)}}[T^{(m)}_{1}\mid\mathcal{D}_{tr}^{(m)}]\Big{)}}{\hat{\sigma}^{(n,m)}}+\frac{\sqrt{n}{\mathbb{E}}_{P^{(m)}}[T^{(m)}_{1}\mid\mathcal{D}_{tr}^{(m)}]}{\hat{\sigma}^{(n,m)}}$
$\displaystyle=\frac{\sqrt{n}\Big{(}\bar{T}^{(n,m)}-{\mathbb{E}}_{P^{(m)}}[T^{(m)}_{1}\mid\mathcal{D}_{tr}^{(m)}]\Big{)}}{\hat{\sigma}^{(n,m)}}+$
$\displaystyle~{}~{}+\frac{\sqrt{n}\Big{(}{\mathbb{E}}_{P^{(m)}}[\ell(\hat{g}_{2}^{(m)}(Z_{1}),Y_{1})-\ell(g_{2,P^{(m)}}^{*}(Z_{1}),Y_{1})\mid\mathcal{D}_{tr}^{(m)}]-\big{(}{\mathbb{E}}_{P^{(m)}}[\ell(\hat{g}_{1}^{(m)}(X_{1},Z_{1}),Y_{1})-\ell(g_{1,P^{(m)}}^{*}(X_{1},Z_{1}),Y_{1})\mid\mathcal{D}_{tr}^{(m)}]\big{)}\Big{)}}{\hat{\sigma}^{(n,m)}}$
$\displaystyle~{}~{}+\frac{\sqrt{n}\Big{(}{\mathbb{E}}_{P^{(m)}}[\ell(g_{2,P^{(m)}}^{*}(Z_{1}),Y_{1})]-{\mathbb{E}}_{P^{(m)}}[\ell(g_{1,P^{(m)}}^{*}(X_{1},Z_{1}),Y_{1})]\Big{)}}{\hat{\sigma}^{(n,m)}}$
$\displaystyle=\frac{\sqrt{n}W^{(m)}_{1,P^{(m)}}}{\hat{\sigma}^{(n,m)}}+\frac{\sqrt{n}W^{(m)}_{2,P^{(m)}}}{\hat{\sigma}^{(n,m)}}+\frac{\sqrt{n}\Omega_{P^{(m)}}^{\textup{STFR}}}{\hat{\sigma}^{(n,m)}}$

Given that $n$ is a function of $m$, we omit it when writing the
$W^{(m)}_{j,P^{(m)}}$’s. Define $\sigma_{P^{(m)}}^{(m)}\triangleq\sqrt{{\sf
Var}_{P^{(m)}}[T^{(m)}_{1}\mid\mathcal{D}_{tr}^{(m)}]}$ and see that

$\displaystyle{\mathbb{E}}_{P^{(m)}}[\varphi^{\textup{STFR}}_{\alpha}(\mathcal{D}^{(n)}_{te},\mathcal{D}_{tr}^{(m)})]$
$\displaystyle={\mathbb{P}}_{P^{(m)}}[p(\mathcal{D}^{(n)}_{te},\mathcal{D}_{tr}^{(m)})\leq\alpha]$
$\displaystyle={\mathbb{P}}_{P^{(m)}}\left[1-\Phi\left(\Lambda^{(n,m)}\right)\leq\alpha\right]$
$\displaystyle={\mathbb{P}}_{P^{(m)}}\left[\Lambda^{(n,m)}\geq\tau_{\alpha}\right]$
$\displaystyle={\mathbb{P}}_{P^{(m)}}\left[\frac{\sqrt{n}W^{(m)}_{1,P^{(m)}}}{\hat{\sigma}^{(n,m)}}+\frac{\sqrt{n}W^{(m)}_{2,P^{(m)}}}{\hat{\sigma}^{(n,m)}}+\frac{\sqrt{n}\Omega_{P^{(m)}}^{\textup{STFR}}}{\hat{\sigma}^{(n,m)}}\geq\tau_{\alpha}\right]$
$\displaystyle={\mathbb{P}}_{P^{(m)}}\left[\frac{\sqrt{n}W^{(m)}_{1,P^{(m)}}}{\sigma_{P^{(m)}}}+\frac{\sqrt{n}W^{(m)}_{2,P^{(m)}}}{\sigma_{P^{(m)}}}+\frac{\sqrt{n}\Omega_{P^{(m)}}^{\textup{STFR}}}{\sigma_{P^{(m)}}}+\tau_{\alpha}-\tau_{\alpha}\frac{\hat{\sigma}^{(n,m)}}{\sigma_{P^{(m)}}}\geq\tau_{\alpha}\right]$
$\displaystyle={\mathbb{P}}_{P^{(m)}}\left[\frac{\sqrt{n}W^{(m)}_{1,P^{(m)}}}{\sigma_{P^{(m)}}^{(m)}}\frac{\sigma_{P^{(m)}}^{(m)}}{\sigma_{P^{(m)}}}+\frac{\sqrt{n}W^{(m)}_{2,P^{(m)}}}{\sigma_{P^{(m)}}}+\tau_{\alpha}-\tau_{\alpha}\frac{\hat{\sigma}^{(n,m)}}{\sigma_{P^{(m)}}^{(m)}}\frac{\sigma_{P^{(m)}}^{(m)}}{\sigma_{P^{(m)}}}\geq\tau_{\alpha}-\frac{\sqrt{n}\Omega_{P^{(m)}}^{\textup{STFR}}}{\sigma_{P^{(m)}}}\right]$
$\displaystyle=1-\Phi\left(\tau_{\alpha}-\sqrt{\frac{n}{\sigma_{P^{(m)}}^{2}}}\Omega_{P^{(m)}}^{\textup{STFR}}\right)+o(1)$
(B.1)

Implying that

$\displaystyle\sup_{P\in\mathcal{P}}\left|{\mathbb{E}}_{P}[\varphi^{\textup{STFR}}_{\alpha}(\mathcal{D}^{(n)}_{te},\mathcal{D}_{tr}^{(m)})]-1+\Phi\left(\tau_{\alpha}-\sqrt{\frac{n}{\sigma_{P}^{2}}}\Omega_{P}^{\textup{STFR}}\right)\right|=o(1)\text{
as }m\to\infty$

Justifying step B.1. First, from a central limit theorem for triangular arrays
[6, Corollary 9.5.11], we have that

$\sqrt{n}\left(\frac{W^{(m)}_{1,P^{(m)}}}{\sigma_{P^{(m)}}^{(m)}}\right)=\sqrt{n}\left(\frac{\bar{T}^{(n,m)}-{\mathbb{E}}_{P^{(m)}}[T^{(m)}_{1}\mid\mathcal{D}_{tr}^{(m)}]}{\sigma_{P^{(m)}}^{(m)}}\right)=\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\left(\frac{T_{i}^{(m)}-{\mathbb{E}}_{P^{(m)}}[T^{(m)}_{1}\mid\mathcal{D}_{tr}^{(m)}]}{\sigma_{P^{(m)}}^{(m)}}\right)\Rightarrow
N(0,1)$

we comment on the conditions to use this theorem below.

Second, we have that

$\displaystyle\frac{\sqrt{n}W^{(m)}_{1,P^{(m)}}}{\sigma_{P^{(m)}}^{(m)}}-\left(\frac{\sqrt{n}W^{(m)}_{1,P^{(m)}}}{\sigma_{P^{(m)}}^{(m)}}\frac{\sigma_{P^{(m)}}^{(m)}}{\sigma_{P^{(m)}}}+\frac{\sqrt{n}W^{(m)}_{2,P^{(m)}}}{\sigma_{P^{(m)}}}+\tau_{\alpha}-\tau_{\alpha}\frac{\hat{\sigma}^{(n,m)}}{\sigma_{P^{(m)}}^{(m)}}\frac{\sigma_{P^{(m)}}^{(m)}}{\sigma_{P^{(m)}}}\right)=$
$\displaystyle=\frac{\sqrt{n}W^{(m)}_{1,P^{(m)}}}{\sigma_{P^{(m)}}^{(m)}}\left(1-\frac{\sigma_{P^{(m)}}^{(m)}}{\sigma_{P^{(m)}}}\right)-\frac{\sqrt{n}W^{(m)}_{2,P^{(m)}}}{\sigma_{P^{(m)}}}+\tau_{\alpha}\left(\frac{\hat{\sigma}^{(n,m)}}{\sigma_{P^{(m)}}^{(m)}}-1\right)\left(\frac{\sigma_{P^{(m)}}^{(m)}}{\sigma_{P^{(m)}}}-1\right)+\tau_{\alpha}\left(\frac{\sigma_{P^{(m)}}^{(m)}}{\sigma_{P^{(m)}}}-1\right)+\tau_{\alpha}\left(\frac{\hat{\sigma}^{(n,m)}}{\sigma_{P^{(m)}}^{(m)}}-1\right)$
$\displaystyle=o_{p}(1)\text{ as }m\to\infty$

To see why the random quantity above converges to zero in probability, see
that because of Assumption 3.3, Lemma B.1, and continuous mapping theorem, we
have that

$\frac{\hat{\sigma}^{(n,m)}}{\sigma_{P^{(m)}}^{(m)}}-1=o_{p}(1)\text{ and
}\frac{\sigma_{P^{(m)}}^{(m)}}{\sigma_{P^{(m)}}}-1=o_{p}(1)\text{ as
}m\to\infty$

Additionally, because of Assumptions 3.1, 3.3 and condition
$n=o(m^{2\gamma})$, we have that

$\left|\frac{\sqrt{n}W^{(m)}_{2,P^{(m)}}}{\sigma_{P^{(m)}}}\right|=\left|\frac{o(m^{\gamma})\mathcal{O}_{p}(m^{-\gamma})}{\sigma_{P^{(m)}}}\right|\leq\left|\frac{o(m^{\gamma})\mathcal{O}_{p}(m^{-\gamma})}{\inf_{P\in\mathcal{P}}\sigma_{P}}\right|=o_{p}(1)$

Finally,

$\displaystyle\frac{\sqrt{n}W^{(m)}_{1,P^{(m)}}}{\sigma_{P^{(m)}}^{(m)}}\frac{\sigma_{P^{(m)}}^{(m)}}{\sigma_{P^{(m)}}}+\frac{\sqrt{n}W^{(m)}_{2,P^{(m)}}}{\sigma_{P^{(m)}}}+\tau_{\alpha}-\tau_{\alpha}\frac{\hat{\sigma}^{(n,m)}}{\sigma_{P^{(m)}}^{(m)}}\frac{\sigma_{P^{(m)}}^{(m)}}{\sigma_{P^{(m)}}}=$
$\displaystyle=\frac{\sqrt{n}W^{(m)}_{1,P^{(m)}}}{\sigma_{P^{(m)}}^{(m)}}-\left[\frac{\sqrt{n}W^{(m)}_{1,P^{(m)}}}{\sigma_{P^{(m)}}^{(m)}}-\left(\frac{\sqrt{n}W^{(m)}_{1,P^{(m)}}}{\sigma_{P^{(m)}}^{(m)}}\frac{\sigma_{P^{(m)}}^{(m)}}{\sigma_{P^{(m)}}}+\frac{\sqrt{n}W^{(m)}_{2,P^{(m)}}}{\sigma_{P^{(m)}}}+\tau_{\alpha}-\tau_{\alpha}\frac{\hat{\sigma}^{(n,m)}}{\sigma_{P^{(m)}}^{(m)}}\frac{\sigma_{P^{(m)}}^{(m)}}{\sigma_{P^{(m)}}}\right)\right]$
$\displaystyle=\frac{\sqrt{n}W^{(m)}_{1,P^{(m)}}}{\sigma_{P^{(m)}}^{(m)}}+o_{p}(1)\Rightarrow
N(0,1)$

by Slutsky’s theorem. Because $N(0,1)$ is a continuous distribution, we have
uniform convergence of the distribution function [25][Chapter 8, Exercise 5]
and we do not have to worry about the fact that
$\tau_{\alpha}-\frac{\sqrt{n}\Omega_{P^{(m)}}^{\textup{STFR}}}{\sigma_{P^{(m)}}}$
depends on $m$.

Conditions to apply the central limit theorem. Now, we comment on the
conditions for the central limit theorem [6, Corollary 9.5.11]. Define our
triangular array as $\left\\{V^{(m)}_{i}\right\\}_{1\leq i\leq n}$, where
$V^{(m)}_{i}\triangleq\frac{T_{i}^{(m)}-{\mathbb{E}}_{P^{(m)}}[T_{i}^{(m)}\mid\mathcal{D}_{tr}^{(m)}]}{\sigma_{P^{(m)}}^{(m)}}$.

  1. 1.

This condition naturally applies by definition and because of Assumption 3.2.

  2. 2.

See that, for any $m$, we have that

${\mathbb{E}}_{P^{(m)}}[(V^{(m)}_{i})^{2}\mid\mathcal{D}_{tr}^{(m)}]=1$

  3. 3.

Fix any $\epsilon>0$ and let $k$ be defined as in Assumption 3.2. See that

$\displaystyle{\mathbb{E}}_{P^{(m)}}\left[(V^{(m)}_{i})^{2}\mathds{1}[|V^{(m)}_{i}|\geq\epsilon
n]\mid\mathcal{D}_{tr}^{(m)}\right]=$
$\displaystyle={\mathbb{E}}_{P^{(m)}}\left[(V^{(m)}_{i})^{2}\mathds{1}[(|V^{(m)}_{i}|/(\epsilon
n))^{k}\geq 1]\mid\mathcal{D}_{tr}^{(m)}\right]$
$\displaystyle\leq\frac{1}{(n\epsilon)^{k}}{\mathbb{E}}_{P^{(m)}}\left[|V^{(m)}_{i}|^{2+k}\mid\mathcal{D}_{tr}^{(m)}\right]$
$\displaystyle=\frac{1}{(n\epsilon)^{k}}{\mathbb{E}}_{P^{(m)}}\left[\left|\frac{T_{i}^{(m)}-{\mathbb{E}}_{P^{(m)}}[T_{i}^{(m)}\mid\mathcal{D}_{tr}^{(m)}]}{\sigma_{P^{(m)}}^{(m)}}\right|^{2+k}\mid\mathcal{D}_{tr}^{(m)}\right]$
$\displaystyle\leq\frac{1}{(n\epsilon)^{k}}\frac{1}{(\sigma_{P^{(m)}}^{(m)})^{2+k}}\left\\{{\mathbb{E}}_{P^{(m)}}\left[|T^{(m)}_{i}|^{2+k}\mid\mathcal{D}_{tr}^{(m)}\right]^{\frac{1}{2+k}}+{\mathbb{E}}_{P^{(m)}}\left[|T^{(m)}_{i}|\mid\mathcal{D}_{tr}^{(m)}\right]\right\\}^{2+k}$
$\displaystyle=\frac{1}{(n\epsilon)^{k}}\left[\frac{1}{(\sigma_{P^{(m)}})^{2+k}}+o_{p}(1)\right]\left\\{{\mathbb{E}}_{P^{(m)}}\left[|T^{(m)}_{i}|^{2+k}\mid\mathcal{D}_{tr}^{(m)}\right]^{\frac{1}{2+k}}+{\mathbb{E}}_{P^{(m)}}\left[|T^{(m)}_{i}|\mid\mathcal{D}_{tr}^{(m)}\right]\right\\}^{2+k}$
$\displaystyle\leq\frac{1}{(n\epsilon)^{k}}\left[\frac{1}{(\inf_{P\in\mathcal{P}}\sigma_{P})^{2+k}}+o_{p}(1)\right]\mathcal{O}_{p}(1)$
$\displaystyle=\frac{1}{(n\epsilon)^{k}}\mathcal{O}_{p}(1)$
$\displaystyle=o_{p}(1)$

where the third inequality is obtained via Minkowski Inequality [25] and the
last inequality is an application of Assumption 3.2 and Resnick [25, Example
6.5.2].

∎

Corollary 3.6. Suppose we are under the conditions of Theorem 3.4.

$\bullet$ (Type-I error) If $H_{0}:X\mathchoice{\mathrel{\hbox
to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}Y\mid Z$ holds, then

$\displaystyle{\mathbb{E}}_{P}[\varphi^{\textup{STFR}}_{\alpha}(\mathcal{D}^{(n)}_{te},\mathcal{D}_{tr}^{(m)})]\leq
1-\Phi\left(\tau_{\alpha}-\sqrt{\frac{n}{\sigma_{P}^{2}}}\Delta_{2,P}\right)+o(1)$

where $o(1)$ denotes uniform convergence over all $P\in\mathcal{P}_{0}$ as
$m\to\infty$.

$\bullet$ (Type-II error) In general, we have

$\displaystyle
1-{\mathbb{E}}_{P}[\varphi^{\textup{STFR}}_{\alpha}(\mathcal{D}^{(n)}_{te},\mathcal{D}_{tr}^{(m)})]\leq\Phi\left(\tau_{\alpha}-\sqrt{\frac{n}{\sigma_{P}^{2}}}(\Delta_{P}-\Delta_{1,P})\right)+o(1)$

where $o(1)$ denotes uniform convergence over all $P\in\mathcal{P}$ as
$m\to\infty$ and
$\Delta_{P}\triangleq{\mathbb{E}}_{P}[\ell(f^{*}_{2,P}(Z),Y)]-{\mathbb{E}}_{P}[\ell(f^{*}_{1,P}(X,Z),Y)]$.

###### Proof.

Under the conditions of Theorem 3.4, we start proving that

  1. 1.

$\Delta_{P}-\Delta_{1,P}\leq\Omega_{P}^{\textup{STFR}}$ holds;

  2. 2.

Under $H_{0}$, $\Omega_{P}^{\textup{STFR}}\leq\Delta_{2,P}$ holds.

For (1), see that,

$\displaystyle\Omega_{P}^{\textup{STFR}}$
$\displaystyle={\mathbb{E}}_{P}[\ell(g_{2,P}^{*}(Z),Y)]-{\mathbb{E}}_{P}[\ell(g_{1,P}^{*}(X,Z),Y)]$
$\displaystyle={\mathbb{E}}_{P}[\ell(g_{2,P}^{*}(Z),Y)]-{\mathbb{E}}_{P}[\ell(f_{2,P}^{*}(Z),Y)]~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}(\geq
0)$
$\displaystyle+{\mathbb{E}}_{P}[\ell(f_{1,P}^{*}(X,Z),Y)]-{\mathbb{E}}_{P}[\ell(g_{1,P}^{*}(X,Z),Y)]$
$\displaystyle+{\mathbb{E}}_{P}[\ell(f_{2,P}^{*}(Z),Y)]-{\mathbb{E}}_{P}[\ell(f_{1,P}^{*}(X,Z),Y)]$
$\displaystyle\geq{\mathbb{E}}_{P}[\ell(f_{1,P}^{*}(X,Z),Y)]-{\mathbb{E}}_{P}[\ell(g_{1,P}^{*}(X,Z),Y)]+\Delta_{P}$
$\displaystyle=\Delta_{P}-\Delta_{1,P}$

Now, for (2):

$\displaystyle\Omega_{P}^{\textup{STFR}}$
$\displaystyle={\mathbb{E}}_{P}[\ell(g_{2,P}^{*}(Z),Y)]-{\mathbb{E}}_{P}[\ell(g_{1,P}^{*}(X,Z),Y)]$
$\displaystyle={\mathbb{E}}_{P}[\ell(g_{2,P}^{*}(Z),Y)]-{\mathbb{E}}_{P}[\ell(f_{2,P}^{*}(Z),Y)]$
$\displaystyle+{\mathbb{E}}_{P}[\ell(f_{1,P}^{*}(X,Z),Y)]-{\mathbb{E}}_{P}[\ell(g_{1,P}^{*}(X,Z),Y)]~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}(\leq
0)$
$\displaystyle+{\mathbb{E}}_{P}[\ell(f_{2,P}^{*}(Z),Y)]-{\mathbb{E}}_{P}[\ell(f_{1,P}^{*}(X,Z),Y)]~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}(=0\text{,
because $H_{0}$ holds})$
$\displaystyle\leq{\mathbb{E}}_{P}[\ell(g_{2,P}^{*}(Z),Y)]-{\mathbb{E}}_{P}[\ell(f_{2,P}^{*}(Z),Y)]$
$\displaystyle=\Delta_{2,P}$

Finally, see that

$1-\Phi\left(\tau_{\alpha}-\sqrt{\frac{n}{\sigma_{P}^{2}}}\Omega_{P}^{\textup{STFR}}\right)\leq
1-\Phi\left(\tau_{\alpha}-\sqrt{\frac{n}{\sigma_{P}^{2}}}\Delta_{2,P}\right)$

and

$\Phi\left(\tau_{\alpha}-\sqrt{\frac{n}{\sigma_{P}^{2}}}\Omega_{P}^{\textup{STFR}}\right)\leq\Phi\left(\tau_{\alpha}-\sqrt{\frac{n}{\sigma_{P}^{2}}}(\Delta_{P}-\Delta_{1,P})\right)$

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 $n$ is a
function of $m$ such that $n\to\infty$ and $n=o(m^{\gamma})$ as $m\to\infty$,
then

$\displaystyle{\mathbb{E}}_{P}[\varphi^{\textup{GCM}}_{\alpha}(\mathcal{D}^{(n)}_{te},\mathcal{D}^{(m)}_{tr})]$
$\displaystyle=1-\Phi\left(\tau_{\alpha/2}-\sqrt{\frac{n}{\sigma_{P}^{2}}}\Omega_{P}^{\textup{GCM}}\right)+\Phi\left(-\tau_{\alpha/2}-\sqrt{\frac{n}{\sigma_{P}^{2}}}\Omega_{P}^{\textup{GCM}}\right)+o(1)$

where $o(1)$ denotes uniform convergence over all $P\in\mathcal{P}$ as
$m\to\infty$ and

$\Omega_{P}^{\textup{GCM}}\triangleq{\mathbb{E}}_{P}[{\sf Cov}_{P}(X,Y\mid
Z)]+{\mathbb{E}}_{P}[\delta_{1,P}(Z)\delta_{2,P}(Z)]$

###### Proof.

First, note that there must be161616Because of the definition of $\sup$. a
sequence of probability measures in $\mathcal{P}$,
$(P^{(m)})_{m\in\mathbb{N}}$, such that

$\displaystyle\sup_{P\in\mathcal{P}}\left|{\mathbb{E}}_{P}[\varphi^{\textup{GCM}}_{\alpha}(\mathcal{D}^{(n)}_{te},\mathcal{D}_{tr}^{(m)})]-1+\Phi\left(\tau_{\alpha/2}-\sqrt{\frac{n}{\sigma_{P}^{2}}}\Omega_{P}^{\textup{GCM}}\right)-\Phi\left(-\tau_{\alpha/2}-\sqrt{\frac{n}{\sigma_{P}^{2}}}\Omega_{P}^{\textup{GCM}}\right)\right|\leq$
$\displaystyle\leq\left|{\mathbb{E}}_{P^{(m)}}[\varphi^{\textup{GCM}}_{\alpha}(\mathcal{D}^{(n)}_{te},\mathcal{D}_{tr}^{(m)})]-1+\Phi\left(\tau_{\alpha/2}-\sqrt{\frac{n}{\sigma_{P^{(m)}}^{2}}}\Omega_{P^{(m)}}^{\textup{GCM}}\right)-\Phi\left(-\tau_{\alpha/2}-\sqrt{\frac{n}{\sigma_{P^{(m)}}^{2}}}\Omega_{P^{(m)}}^{\textup{GCM}}\right)\right|+\frac{1}{m}$

Then, it suffices to show that the RHS vanishes when we consider such a
sequence $(P^{(m)})_{m\in\mathbb{N}}$.

Now, let us first decompose the test statistic $\Gamma^{(n,m)}$ in the
following way:

$\displaystyle\Gamma^{(n,m)}\triangleq\Bigg{|}\frac{\sqrt{n}\bar{T}^{(n,m)}}{\hat{\sigma}^{(n,m)}}\Bigg{|}=$
$\displaystyle=\Bigg{|}\frac{\sqrt{n}\Big{(}\bar{T}^{(n,m)}-{\mathbb{E}}_{P^{(m)}}[T^{(m)}_{1}\mid\mathcal{D}_{tr}^{(m)}]\Big{)}}{\hat{\sigma}^{(n,m)}}+\frac{\sqrt{n}{\mathbb{E}}_{P^{(m)}}[T^{(m)}_{1}\mid\mathcal{D}_{tr}^{(m)}]}{\hat{\sigma}^{(n,m)}}\Bigg{|}$
$\displaystyle=\Bigg{|}\frac{\sqrt{n}\Big{(}\bar{T}^{(n,m)}-{\mathbb{E}}_{P^{(m)}}[T^{(m)}_{1}\mid\mathcal{D}_{tr}^{(m)}]\Big{)}}{\hat{\sigma}^{(n,m)}}+\frac{\sqrt{n}{\mathbb{E}}_{P^{(m)}}[(\hat{g}^{(m)}_{1}(Z_{1})-g^{*}_{1,P^{(m)}}(Z_{1}))(\hat{g}^{(m)}_{2}(Z_{1})-g^{*}_{2,P^{(m)}}(Z_{1}))\mid\mathcal{D}_{tr}^{(m)}]}{\hat{\sigma}^{(n,m)}}$
$\displaystyle+\frac{\sqrt{n}{\mathbb{E}}_{P^{(m)}}[(\hat{g}^{(m)}_{1}(Z_{1})-g^{*}_{1,P^{(m)}}(Z_{1}))\delta_{2,P^{(m)}}(Z_{1})\mid\mathcal{D}_{tr}^{(m)}]}{\hat{\sigma}^{(n,m)}}+\frac{\sqrt{n}{\mathbb{E}}_{P^{(m)}}[\delta_{1,P^{(m)}}(Z_{1})(\hat{g}^{(m)}_{2}(Z_{1})-g^{*}_{2,P^{(m)}}(Z_{1}))\mid\mathcal{D}_{tr}^{(m)}]}{\hat{\sigma}^{(n,m)}}$
$\displaystyle+\frac{\sqrt{n}\Omega_{P^{(m)}}^{\textup{GCM}}}{\hat{\sigma}^{(n,m)}}\Bigg{|}$
$\displaystyle=\Bigg{|}\frac{\sqrt{n}W^{(m)}_{1,P^{(m)}}}{\hat{\sigma}^{(n,m)}}+\frac{\sqrt{n}W^{(m)}_{2,P^{(m)}}}{\hat{\sigma}^{(n,m)}}+\frac{\sqrt{n}W^{(m)}_{3,P^{(m)}}}{\hat{\sigma}^{(n,m)}}+\frac{\sqrt{n}W^{(m)}_{4,P^{(m)}}}{\hat{\sigma}^{(n,m)}}+\frac{\sqrt{n}\Omega_{P^{(m)}}^{\textup{GCM}}}{\hat{\sigma}^{(n,m)}}\Bigg{|}$

The terms involving one of the $\epsilon$ and $\eta$ were all zero and were
omitted. Given that $n$ is a function of $m$, we omit it when writing the
$W^{(m)}_{j,P^{(m)}}$’s. Define $\sigma_{P^{(m)}}^{(m)}\triangleq\sqrt{{\sf
Var}_{P^{(m)}}[T^{(m)}_{1}\mid\mathcal{D}_{tr}^{(m)}]}$ and see that

$\displaystyle{\mathbb{E}}_{P}[\varphi^{\textup{GCM}}_{\alpha}(\mathcal{D}^{(n)}_{te},\mathcal{D}_{tr}^{(m)})]=$
$\displaystyle={\mathbb{P}}_{P}[p(\mathcal{D}^{(n)}_{te},\mathcal{D}_{tr}^{(m)})\leq\alpha]$
$\displaystyle={\mathbb{P}}_{P}\left[1-\Phi\left(\Gamma^{(n,m)}\right)\leq\alpha/2\right]$
$\displaystyle={\mathbb{P}}_{P}\left[\Gamma^{(n,m)}\geq\tau_{\alpha/2}\right]$
$\displaystyle={\mathbb{P}}_{P}\left[\frac{\sqrt{n}W^{(m)}_{1,P^{(m)}}}{\hat{\sigma}^{(n,m)}}+\frac{\sqrt{n}W^{(m)}_{2,P^{(m)}}}{\hat{\sigma}^{(n,m)}}+\frac{\sqrt{n}W^{(m)}_{3,P^{(m)}}}{\hat{\sigma}^{(n,m)}}+\frac{\sqrt{n}W^{(m)}_{4,P^{(m)}}}{\hat{\sigma}^{(n,m)}}+\frac{\sqrt{n}\Omega_{P^{(m)}}^{\textup{GCM}}}{\hat{\sigma}^{(n,m)}}\leq-\tau_{\alpha/2}\right]+$
$\displaystyle~{}~{}~{}+{\mathbb{P}}_{P}\left[\frac{\sqrt{n}W^{(m)}_{1,P^{(m)}}}{\hat{\sigma}^{(n,m)}}+\frac{\sqrt{n}W^{(m)}_{2,P^{(m)}}}{\hat{\sigma}^{(n,m)}}+\frac{\sqrt{n}W^{(m)}_{3,P^{(m)}}}{\hat{\sigma}^{(n,m)}}+\frac{\sqrt{n}W^{(m)}_{4,P^{(m)}}}{\hat{\sigma}^{(n,m)}}+\frac{\sqrt{n}\Omega_{P^{(m)}}^{\textup{GCM}}}{\hat{\sigma}^{(n,m)}}\geq\tau_{\alpha/2}\right]$
$\displaystyle={\mathbb{P}}_{P}\left[\frac{\sqrt{n}W^{(m)}_{1,P^{(m)}}}{\sigma^{(m)}_{P^{(m)}}}\frac{\sigma^{(m)}_{P^{(m)}}}{\sigma_{P^{(m)}}}+\frac{\sqrt{n}W^{(m)}_{2,P^{(m)}}}{\sigma_{P^{(m)}}}+\frac{\sqrt{n}W^{(m)}_{3,P^{(m)}}}{\sigma_{P^{(m)}}}+\frac{\sqrt{n}W^{(m)}_{4,P^{(m)}}}{\sigma_{P^{(m)}}}+\frac{\hat{\sigma}^{(n,m)}}{\sigma^{(m)}_{P^{(m)}}}\frac{\sigma^{(m)}_{P^{(m)}}}{\sigma_{P^{(m)}}}\tau_{\alpha/2}-\tau_{\alpha/2}\leq-\tau_{\alpha/2}-\frac{\sqrt{n}\Omega_{P^{(m)}}^{\textup{GCM}}}{\sigma_{P^{(m)}}}\right]+$
$\displaystyle~{}~{}~{}+{\mathbb{P}}_{P}\left[\frac{\sqrt{n}W^{(m)}_{1,P^{(m)}}}{\sigma^{(m)}_{P^{(m)}}}\frac{\sigma^{(m)}_{P^{(m)}}}{\sigma_{P^{(m)}}}+\frac{\sqrt{n}W^{(m)}_{2,P^{(m)}}}{\sigma_{P^{(m)}}}+\frac{\sqrt{n}W^{(m)}_{3,P^{(m)}}}{\sigma_{P^{(m)}}}+\frac{\sqrt{n}W^{(m)}_{4,P^{(m)}}}{\sigma_{P^{(m)}}}-\frac{\hat{\sigma}^{(n,m)}}{\sigma^{(m)}_{P^{(m)}}}\frac{\sigma^{(m)}_{P^{(m)}}}{\sigma_{P^{(m)}}}\tau_{\alpha/2}+\tau_{\alpha/2}\geq\tau_{\alpha/2}-\frac{\sqrt{n}\Omega_{P^{(m)}}^{\textup{GCM}}}{\sigma_{P^{(m)}}}\right]$
$\displaystyle=1-\Phi\left(\tau_{\alpha/2}-\sqrt{\frac{n}{\sigma_{P^{(m)}}^{2}}}\Omega_{P^{(m)}}^{\textup{GCM}}\right)+\Phi\left(-\tau_{\alpha/2}-\sqrt{\frac{n}{\sigma_{P^{(m)}}^{2}}}\Omega_{P^{(m)}}^{\textup{GCM}}\right)+o(1)$
(B.2)

Implying that

$\displaystyle\sup_{P\in\mathcal{P}}\left|{\mathbb{E}}_{P}[\varphi^{\textup{GCM}}_{\alpha}(\mathcal{D}^{(n)}_{te},\mathcal{D}_{tr}^{(m)})]-1+\Phi\left(\tau_{\alpha/2}-\sqrt{\frac{n}{\sigma_{P}^{2}}}\Omega_{P}^{\textup{GCM}}\right)-\Phi\left(-\tau_{\alpha/2}-\sqrt{\frac{n}{\sigma_{P}^{2}}}\Omega_{P}^{\textup{GCM}}\right)\right|=o(1)\text{
as }m\to\infty$

Justifying step B.2. First, from a central limit theorem for triangular arrays
[6, Corollary 9.5.11], we have that

$\sqrt{n}\left(\frac{W^{(m)}_{1,P^{(m)}}}{\sigma_{P^{(m)}}^{(m)}}\right)=\sqrt{n}\left(\frac{\bar{T}^{(n,m)}-{\mathbb{E}}_{P^{(m)}}[T^{(m)}_{1}\mid\mathcal{D}_{tr}^{(m)}]}{\sigma_{P^{(m)}}^{(m)}}\right)=\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\left(\frac{T_{i}^{(m)}-{\mathbb{E}}_{P^{(m)}}[T^{(m)}_{1}\mid\mathcal{D}_{tr}^{(m)}]}{\sigma_{P^{(m)}}^{(m)}}\right)\Rightarrow
N(0,1)$

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

$\displaystyle\frac{\sqrt{n}W^{(m)}_{1,P^{(m)}}}{\sigma_{P^{(m)}}^{(m)}}-\left(\frac{\sqrt{n}W^{(m)}_{1,P^{(m)}}}{\sigma_{P^{(m)}}^{(m)}}\frac{\sigma_{P^{(m)}}^{(m)}}{\sigma_{P^{(m)}}}+\frac{\sqrt{n}W^{(m)}_{2,P^{(m)}}}{\sigma_{P^{(m)}}}+\frac{\sqrt{n}W^{(m)}_{3,P^{(m)}}}{\sigma_{P^{(m)}}}+\frac{\sqrt{n}W^{(m)}_{4,P^{(m)}}}{\sigma_{P^{(m)}}}-\tau_{\alpha/2}+\tau_{\alpha/2}\frac{\hat{\sigma}^{(n,m)}}{\sigma_{P^{(m)}}^{(m)}}\frac{\sigma_{P^{(m)}}^{(m)}}{\sigma_{P^{(m)}}}\right)=$
$\displaystyle=\frac{\sqrt{n}W^{(m)}_{1,P^{(m)}}}{\sigma_{P^{(m)}}^{(m)}}\left(1-\frac{\sigma_{P^{(m)}}^{(m)}}{\sigma_{P^{(m)}}}\right)-\frac{\sqrt{n}W^{(m)}_{2,P^{(m)}}}{\sigma_{P^{(m)}}}-\frac{\sqrt{n}W^{(m)}_{3,P^{(m)}}}{\sigma_{P^{(m)}}}-\frac{\sqrt{n}W^{(m)}_{4,P^{(m)}}}{\sigma_{P^{(m)}}}+$
$\displaystyle~{}~{}~{}~{}~{}+\tau_{\alpha/2}\left(1-\frac{\hat{\sigma}^{(n,m)}}{\sigma_{P^{(m)}}^{(m)}}\right)\left(\frac{\sigma_{P^{(m)}}^{(m)}}{\sigma_{P^{(m)}}}-1\right)+\tau_{\alpha/2}\left(1-\frac{\sigma_{P^{(m)}}^{(m)}}{\sigma_{P^{(m)}}}\right)+\tau_{\alpha/2}\left(1-\frac{\hat{\sigma}^{(n,m)}}{\sigma_{P^{(m)}}^{(m)}}\right)$
$\displaystyle=o_{p}(1)\text{ as }m\to\infty$

and

$\displaystyle\frac{\sqrt{n}W^{(m)}_{1,P^{(m)}}}{\sigma_{P^{(m)}}^{(m)}}-\left(\frac{\sqrt{n}W^{(m)}_{1,P^{(m)}}}{\sigma_{P^{(m)}}^{(m)}}\frac{\sigma_{P^{(m)}}^{(m)}}{\sigma_{P^{(m)}}}+\frac{\sqrt{n}W^{(m)}_{2,P^{(m)}}}{\sigma_{P^{(m)}}}+\frac{\sqrt{n}W^{(m)}_{3,P^{(m)}}}{\sigma_{P^{(m)}}}+\frac{\sqrt{n}W^{(m)}_{4,P^{(m)}}}{\sigma_{P^{(m)}}}+\tau_{\alpha/2}-\tau_{\alpha/2}\frac{\hat{\sigma}^{(n,m)}}{\sigma_{P^{(m)}}^{(m)}}\frac{\sigma_{P^{(m)}}^{(m)}}{\sigma_{P^{(m)}}}\right)=$
$\displaystyle=\frac{\sqrt{n}W^{(m)}_{1,P^{(m)}}}{\sigma_{P^{(m)}}^{(m)}}\left(1-\frac{\sigma_{P^{(m)}}^{(m)}}{\sigma_{P^{(m)}}}\right)-\frac{\sqrt{n}W^{(m)}_{2,P^{(m)}}}{\sigma_{P^{(m)}}}-\frac{\sqrt{n}W^{(m)}_{3,P^{(m)}}}{\sigma_{P^{(m)}}}-\frac{\sqrt{n}W^{(m)}_{4,P^{(m)}}}{\sigma_{P^{(m)}}}+$
$\displaystyle~{}~{}~{}~{}~{}+\tau_{\alpha/2}\left(\frac{\hat{\sigma}^{(n,m)}}{\sigma_{P^{(m)}}^{(m)}}-1\right)\left(\frac{\sigma_{P^{(m)}}^{(m)}}{\sigma_{P^{(m)}}}-1\right)+\tau_{\alpha/2}\left(\frac{\sigma_{P^{(m)}}^{(m)}}{\sigma_{P^{(m)}}}-1\right)+\tau_{\alpha/2}\left(\frac{\hat{\sigma}^{(n,m)}}{\sigma_{P^{(m)}}^{(m)}}-1\right)$
$\displaystyle=o_{p}(1)\text{ as }m\to\infty$

To see why the random quantities above converge to zero in probability, see
that because of Assumption 3.3, Lemma171717We can apply this STFR’s lemma
because it still holds when we consider GCM’s test statistic. B.1, and
continuous mapping theorem, we have that

$\frac{\hat{\sigma}^{(n,m)}}{\sigma_{P^{(m)}}^{(m)}}-1=o_{p}(1)\text{ and
}\frac{\sigma_{P^{(m)}}^{(m)}}{\sigma_{P^{(m)}}}-1=o_{p}(1)\text{ as
}m\to\infty$

Additionally, because of Assumptions A.3, 3.3, Cauchy-Schwarz inequality, and
condition $n=o(m^{\gamma})$, we have that

$\displaystyle\left|\frac{\sqrt{n}W^{(m)}_{2,P^{(m)}}}{\sigma_{P^{(m)}}}\right|=\left|\frac{\sqrt{n}{\mathbb{E}}_{P^{(m)}}[(\hat{g}^{(m)}_{1}(Z_{1})-g^{*}_{1,P^{(m)}}(Z_{1}))(\hat{g}^{(m)}_{2}(Z_{1})-g^{*}_{2,P^{(m)}}(Z_{1}))\mid\mathcal{D}_{tr}^{(m)}]}{\sigma_{P^{(m)}}}\right|$
$\displaystyle\leq\frac{\sqrt{n{\mathbb{E}}_{P^{(m)}}[(\hat{g}^{(m)}_{1}(Z_{1})-g^{*}_{1,P^{(m)}}(Z_{1}))^{2}\mid\mathcal{D}_{tr}^{(m)}]{\mathbb{E}}_{P^{(m)}}[(\hat{g}^{(m)}_{2}(Z_{1})-g^{*}_{2,P^{(m)}}(Z_{1}))^{2}\mid\mathcal{D}_{tr}^{(m)}]}}{\inf_{P\in\mathcal{P}}\sigma_{P}}$
$\displaystyle=\frac{\sqrt{o(m^{\gamma})\mathcal{O}_{p}(m^{-2\gamma})}}{\inf_{P\in\mathcal{P}}\sigma_{P}}$
$\displaystyle=o_{p}(1)$
$\displaystyle\left|\frac{\sqrt{n}W^{(m)}_{3,P^{(m)}}}{\sigma_{P^{(m)}}}\right|=\left|\frac{\sqrt{n}{\mathbb{E}}_{P^{(m)}}[(\hat{g}^{(m)}_{1}(Z_{1})-g^{*}_{1,P^{(m)}}(Z_{1}))\delta_{2,P^{(m)}}(Z_{1})\mid\mathcal{D}_{tr}^{(m)}]}{\sigma_{P^{(m)}}}\right|$
$\displaystyle\leq\frac{\sqrt{n{\mathbb{E}}_{P^{(m)}}[(\hat{g}^{(m)}_{1}(Z_{1})-g^{*}_{1,P^{(m)}}(Z_{1}))^{2}\mid\mathcal{D}_{tr}^{(m)}]{\mathbb{E}}_{P^{(m)}}[(\delta_{2,P^{(m)}}(Z_{1}))^{2}]}}{\inf_{P\in\mathcal{P}}\sigma_{P}}$
$\displaystyle=\frac{\sqrt{o(m^{\gamma})\mathcal{O}_{p}(m^{-\gamma})}}{\inf_{P\in\mathcal{P}}\sigma_{P}}$
$\displaystyle=o_{p}(1)$
$\displaystyle\left|\frac{\sqrt{n}W^{(m)}_{4,P^{(m)}}}{\sigma_{P^{(m)}}}\right|=\left|\frac{\sqrt{n}{\mathbb{E}}_{P^{(m)}}[(\hat{g}^{(m)}_{2}(Z_{1})-g^{*}_{2,P^{(m)}}(Z_{1}))\delta_{1,P^{(m)}}(Z_{1})\mid\mathcal{D}_{tr}^{(m)}]}{\sigma_{P^{(m)}}}\right|$
$\displaystyle\leq\frac{\sqrt{n{\mathbb{E}}_{P^{(m)}}[(\hat{g}^{(m)}_{2}(Z_{1})-g^{*}_{2,P^{(m)}}(Z_{1}))^{2}\mid\mathcal{D}_{tr}^{(m)}]{\mathbb{E}}_{P^{(m)}}[(\delta_{1,P^{(m)}}(Z_{1}))^{2}]}}{\inf_{P\in\mathcal{P}}\sigma_{P}}$
$\displaystyle=\frac{\sqrt{o(m^{\gamma})\mathcal{O}_{p}(m^{-\gamma})}}{\inf_{P\in\mathcal{P}}\sigma_{P}}$
$\displaystyle=o_{p}(1)$

Finally,

$\displaystyle\left(\frac{\sqrt{n}W^{(m)}_{1,P^{(m)}}}{\sigma_{P^{(m)}}^{(m)}}\frac{\sigma_{P^{(m)}}^{(m)}}{\sigma_{P^{(m)}}}+\frac{\sqrt{n}W^{(m)}_{2,P^{(m)}}}{\sigma_{P^{(m)}}}+\frac{\sqrt{n}W^{(m)}_{3,P^{(m)}}}{\sigma_{P^{(m)}}}+\frac{\sqrt{n}W^{(m)}_{4,P^{(m)}}}{\sigma_{P^{(m)}}}-\tau_{\alpha/2}+\tau_{\alpha/2}\frac{\hat{\sigma}^{(n,m)}}{\sigma_{P^{(m)}}^{(m)}}\frac{\sigma_{P^{(m)}}^{(m)}}{\sigma_{P^{(m)}}}\right)=$
$\displaystyle=\frac{\sqrt{n}W^{(m)}_{1,P^{(m)}}}{\sigma_{P^{(m)}}^{(m)}}-\left[\frac{\sqrt{n}W^{(m)}_{1,P^{(m)}}}{\sigma_{P^{(m)}}^{(m)}}-\left(\frac{\sqrt{n}W^{(m)}_{1,P^{(m)}}}{\sigma_{P^{(m)}}^{(m)}}\frac{\sigma_{P^{(m)}}^{(m)}}{\sigma_{P^{(m)}}}+\frac{\sqrt{n}W^{(m)}_{2,P^{(m)}}}{\sigma_{P^{(m)}}}+\frac{\sqrt{n}W^{(m)}_{3,P^{(m)}}}{\sigma_{P^{(m)}}}+\frac{\sqrt{n}W^{(m)}_{4,P^{(m)}}}{\sigma_{P^{(m)}}}-\tau_{\alpha/2}+\tau_{\alpha/2}\frac{\hat{\sigma}^{(n,m)}}{\sigma_{P^{(m)}}}\right)\right]$
$\displaystyle=\frac{\sqrt{n}W^{(m)}_{1,P^{(m)}}}{\sigma_{P^{(m)}}^{(m)}}+o_{p}(1)\Rightarrow
N(0,1)$

and

$\displaystyle\left(\frac{\sqrt{n}W^{(m)}_{1,P^{(m)}}}{\sigma_{P^{(m)}}^{(m)}}\frac{\sigma_{P^{(m)}}^{(m)}}{\sigma_{P^{(m)}}}+\frac{\sqrt{n}W^{(m)}_{2,P^{(m)}}}{\sigma_{P^{(m)}}}+\frac{\sqrt{n}W^{(m)}_{3,P^{(m)}}}{\sigma_{P^{(m)}}}+\frac{\sqrt{n}W^{(m)}_{4,P^{(m)}}}{\sigma_{P^{(m)}}}+\tau_{\alpha/2}-\tau_{\alpha/2}\frac{\hat{\sigma}^{(n,m)}}{\sigma_{P^{(m)}}^{(m)}}\frac{\sigma_{P^{(m)}}^{(m)}}{\sigma_{P^{(m)}}}\right)=$
$\displaystyle=\frac{\sqrt{n}W^{(m)}_{1,P^{(m)}}}{\sigma_{P^{(m)}}^{(m)}}-\left[\frac{\sqrt{n}W^{(m)}_{1,P^{(m)}}}{\sigma_{P^{(m)}}^{(m)}}-\left(\frac{\sqrt{n}W^{(m)}_{1,P^{(m)}}}{\sigma_{P^{(m)}}^{(m)}}\frac{\sigma_{P^{(m)}}^{(m)}}{\sigma_{P^{(m)}}}+\frac{\sqrt{n}W^{(m)}_{2,P^{(m)}}}{\sigma_{P^{(m)}}}+\frac{\sqrt{n}W^{(m)}_{3,P^{(m)}}}{\sigma_{P^{(m)}}}+\frac{\sqrt{n}W^{(m)}_{4,P^{(m)}}}{\sigma_{P^{(m)}}}+\tau_{\alpha/2}-\tau_{\alpha/2}\frac{\hat{\sigma}^{(n,m)}}{\sigma_{P^{(m)}}}\right)\right]$
$\displaystyle=\frac{\sqrt{n}W^{(m)}_{1,P^{(m)}}}{\sigma_{P^{(m)}}^{(m)}}+o_{p}(1)\Rightarrow
N(0,1)$

by Slutsky’s theorem. Because $N(0,1)$ is a continuous distribution, we have
uniform convergence of the distribution function [25][Chapter 8, Exercise 5]
and we do not have to worry about the fact that
$\tau_{\alpha/2}-\sqrt{\frac{n}{\sigma_{P^{(m)}}^{2}}}\Omega_{P^{(m)}}^{\textup{GCM}}$
or
$-\tau_{\alpha/2}-\sqrt{\frac{n}{\sigma_{P^{(m)}}^{2}}}\Omega_{P^{(m)}}^{\textup{GCM}}$
depends on $m$.

∎

###  B.3 RESIT

######  Lemma B.2.

Let $P_{U,V}$ and $P^{\prime}_{U,V}$ be two distributions on
$\big{(}\mathcal{U}\times\mathcal{V},\mathcal{B}(\mathcal{U}\times\mathcal{V})\big{)}$,
$\mathcal{U}\times\mathcal{V}\subseteq{\mathbb{R}}^{d_{U}\times d_{V}}$, with
$d_{U},d_{V}\geq 1$. Assume $P_{U}$ and $P^{\prime}_{U}$ are dominated by a
common $\sigma$-finite measure $\mu$ and that $P_{V\mid U=u}=P^{\prime}_{V\mid
U=u}$ is dominated by a $\sigma$-finite measure $\nu_{u}$, for all
$u\in{\mathbb{R}}^{d_{U}}$. Then,

$d_{\textup{TV}}(P_{U,V},P^{\prime}_{U,V})=d_{\textup{TV}}(P_{U},P^{\prime}_{U})$

where $d_{\text{TV}}$ denotes the total variation distance between two
probability measures.

###### Proof.

Let $p_{U}$ and $p^{\prime}_{U}$ denote the densities of $P_{U}$ and
$P^{\prime}_{U}$ w.r.t. $\mu$, and let $p_{V|U}(\cdot\mid u)$ denote the
density of $P_{V\mid U=u}=P^{\prime}_{V\mid U=u}$ w.r.t. $\nu_{u}$. From
Scheffe’s theorem [34][Lemma 2.1], we have that:

$\displaystyle d_{\textup{TV}}(P_{U,V},P^{\prime}_{U,V})$
$\displaystyle=\frac{1}{2}\int\int|p_{U}(u)p_{V|U}(v\mid
u)-p^{\prime}_{U}(u)p_{V|U}(v\mid u)|d\nu_{u}(v)d\mu(u)$
$\displaystyle=\frac{1}{2}\int\left(\int|p_{V|U}(v\mid
u)|d\nu_{u}(v)\right)|p_{U}(u)-p^{\prime}_{U}(u)|d\mu(u)$
$\displaystyle=\frac{1}{2}\int\left(\int p_{V|U}(v\mid
u)d\nu_{u}(v)\right)|p_{U}(u)-p^{\prime}_{U}(u)|d\mu(u)$
$\displaystyle=\frac{1}{2}\int|p_{U}(u)-p^{\prime}_{U}(u)|d\mu(u)$
$\displaystyle=d_{\textup{TV}}(P_{U},P^{\prime}_{U})$

∎

######  Lemma B.3.

For all $i\in[n]$, consider

$(\hat{\epsilon}_{i},\hat{\eta}_{i})\mid\mathcal{D}^{(m)}_{tr}\sim
P_{\hat{\epsilon},\hat{\eta}\mid\mathcal{D}^{(m)}_{tr}},~{}~{}(\epsilon_{i},\hat{\eta}_{i})\mid\mathcal{D}^{(m)}_{tr}\sim
P_{\epsilon,\hat{\eta}\mid\mathcal{D}^{(m)}_{tr}},~{}~{}(\hat{\epsilon}_{i},\eta_{i})\mid\mathcal{D}^{(m)}_{tr}\sim
P_{\hat{\epsilon},\eta\mid\mathcal{D}^{(m)}_{tr}},$

where
$\hat{\epsilon}_{i}=\epsilon_{i}-\delta_{1,P}(Z_{i})-\left(\hat{g}^{(m)}_{1}(Z_{i})-g^{*}_{1,P}(Z_{i})\right)$
and
$\hat{\eta}_{i}=\eta_{i}-\delta_{2,P}(Z_{i})-\left(\hat{g}^{(m)}_{2}(Z_{i})-g^{*}_{2,P}(Z_{i})\right)$.

Under Assumption A.7 and $H_{0}:X\mathchoice{\mathrel{\hbox
to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}Y\mid Z$, we have that

$\displaystyle{\mathbb{E}}_{P}[\varphi^{\textup{RESIT}}_{\alpha}(\mathcal{D}^{(n)}_{te},\mathcal{D}^{(m)}_{tr})\mid\mathcal{D}^{(m)}_{tr}]\leq\alpha+\min\left\\{d_{\textup{TV}}\left(P_{\hat{\epsilon},\hat{\eta}\mid\mathcal{D}^{(m)}_{tr}}^{n},P_{\epsilon,\hat{\eta}\mid\mathcal{D}^{(m)}_{tr}}^{n}\right),d_{\textup{TV}}\left(P_{\hat{\epsilon},\hat{\eta}\mid\mathcal{D}^{(m)}_{tr}}^{n},P_{\hat{\epsilon},\eta\mid\mathcal{D}^{(m)}_{tr}}^{n}\right)\right\\}$

where $d_{\text{TV}}$ denotes the total variation distance between two
probability measures.

###### Proof.

Let us represent the stacked residuals (in matrix form) as
$(\bm{\hat{\epsilon}},\bm{\hat{\eta}})=\\{(\hat{\epsilon}_{i},\hat{\eta}_{i})\\}_{i=1}^{n}$.
See that

$\bigg{(}(\bm{\hat{\epsilon}},\bm{\hat{\eta}})^{(1)},\cdots,(\bm{\hat{\epsilon}},\bm{\hat{\eta}})^{(B)}\mid(\bm{\hat{\epsilon}},\bm{\hat{\eta}})=(\bm{\bar{\epsilon}},\bm{\bar{\eta}}),\mathcal{D}^{(m)}_{tr}\bigg{)}\overset{d}{=}\bigg{(}(\bm{\epsilon},\bm{\hat{\eta}})^{(1)},\cdots,(\bm{\epsilon},\bm{\hat{\eta}})^{(B)}\mid(\bm{\epsilon},\bm{\hat{\eta}})=(\bm{\bar{\epsilon}},\bm{\bar{\eta}}),\mathcal{D}^{(m)}_{tr}\bigg{)}$

Then, because the random quantities above are conditionally discrete, their
distribution is dominated by a counting measure depending on
$(\bm{\bar{\epsilon}},\bm{\bar{\eta}})$. Because the distribution of
$(\epsilon,\eta)$ is absolutely continuous with respect to the Lebesgue
measure, $(\hat{\epsilon},\hat{\eta})\mid\mathcal{D}^{(m)}_{tr}$ and
$(\epsilon,\hat{\eta})\mid\mathcal{D}^{(m)}_{tr}$ are also absolutely
continuous181818Given any training set configuration, the vectors
$(\hat{\epsilon}_{i},\hat{\eta}_{i})$, $(\epsilon_{i},\hat{\eta}_{i})$,
$(\hat{\epsilon}_{i},\eta_{i})$ 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.,
$(\hat{\epsilon}_{i},\hat{\eta}_{i})=(\epsilon_{i},\eta_{i})+(g^{*}_{1,P}(Z_{i})-\hat{g}^{(m)}_{1}(Z_{i})-\delta_{1,P}(Z_{i}),g^{*}_{2,P}(Z_{i})-\hat{g}^{(m)}_{2}(Z_{i})-\delta_{2,P}(Z_{i}))$.
See Lemma B.4 for a proof. for every training set configuration, and then we
can apply Lemma B.2 to get that

$d_{\textup{TV}}\bigg{(}((\bm{\hat{\epsilon}},\bm{\hat{\eta}}),(\bm{\hat{\epsilon}},\bm{\hat{\eta}})^{(1)},\cdots,(\bm{\hat{\epsilon}},\bm{\hat{\eta}})^{(B)})\mid\mathcal{D}^{(m)}_{tr},((\bm{\epsilon},\bm{\hat{\eta}}),(\bm{\epsilon},\bm{\hat{\eta}})^{(1)},\cdots,(\bm{\epsilon},\bm{\hat{\eta}})^{(B)})\mid\mathcal{D}^{(m)}_{tr}\bigg{)}=d_{\textup{TV}}\bigg{(}(\bm{\hat{\epsilon}},\bm{\hat{\eta}})\mid\mathcal{D}^{(m)}_{tr},(\bm{\epsilon},\bm{\hat{\eta}})\mid\mathcal{D}^{(m)}_{tr}\bigg{)}.$

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

$A_{\alpha}\triangleq\left\\{((\bm{e},\bm{h}),(\bm{e},\bm{h})^{(1)},\cdots,(\bm{e},\bm{h})^{(B)}):\frac{1+\sum_{b=1}^{B}\mathds{1}[\Psi((\bm{e},\bm{h})^{(b)})\geq\Psi((\bm{e},\bm{h}))]}{1+B}\leq\alpha\right\\}$

By the definition of the TV distance, we have that (under $H_{0}$):

$\displaystyle{\mathbb{E}}_{P}[\varphi^{\textup{RESIT}}_{\alpha}(\mathcal{D}^{(n)}_{te},\mathcal{D}^{(m)}_{tr})\mid\mathcal{D}^{(m)}_{tr}]$
$\displaystyle={\mathbb{P}}_{P}\left(((\bm{\hat{\epsilon}},\bm{\hat{\eta}}),(\bm{\hat{\epsilon}},\bm{\hat{\eta}})^{(1)},\cdots,(\bm{\hat{\epsilon}},\bm{\hat{\eta}})^{(B)})\in
A_{\alpha}\mid\mathcal{D}^{(m)}_{tr}\right)$
$\displaystyle\leq{\mathbb{P}}_{P}\left(((\bm{\epsilon},\bm{\hat{\eta}}),(\bm{\epsilon},\bm{\hat{\eta}})^{(1)},\cdots,(\bm{\epsilon},\bm{\hat{\eta}})^{(B)})\in
A_{\alpha}\mid\mathcal{D}^{(m)}_{tr}\right)+d_{\textup{TV}}\bigg{(}(\bm{\hat{\epsilon}},\bm{\hat{\eta}})\mid\mathcal{D}^{(m)}_{tr},(\bm{\epsilon},\bm{\hat{\eta}})\mid\mathcal{D}^{(m)}_{tr}\bigg{)}$
$\displaystyle\leq\alpha+d_{\textup{TV}}\bigg{(}(\bm{\hat{\epsilon}},\bm{\hat{\eta}})\mid\mathcal{D}^{(m)}_{tr},(\bm{\epsilon},\bm{\hat{\eta}})\mid\mathcal{D}^{(m)}_{tr}\bigg{)}$
$\displaystyle=\alpha+d_{\textup{TV}}\left(P_{\hat{\epsilon},\hat{\eta}\mid\mathcal{D}^{(m)}_{tr}}^{n},P_{\epsilon,\hat{\eta}\mid\mathcal{D}^{(m)}_{tr}}^{n}\right)$

where the last equality holds from the fact that, given the training set, rows
of $(\bm{\hat{\epsilon}},\bm{\hat{\eta}})$ and
$(\bm{\epsilon},\bm{\hat{\eta}})$ are i.i.d.. See that
${\mathbb{P}}_{P}\left(((\bm{\epsilon},\bm{\hat{\eta}}),(\bm{\epsilon},\bm{\hat{\eta}})^{(1)},\cdots,(\bm{\epsilon},\bm{\hat{\eta}})^{(B)})\in
A_{\alpha}\mid\mathcal{D}^{(m)}_{tr}\right)\leq\alpha$ because $H_{0}$ holds
and therefore $\epsilon_{i}\mathchoice{\mathrel{\hbox
to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}\hat{\eta_{i}}\mid\mathcal{D}^{(m)}_{tr}$
(making the permuted samples exchangeable).

Using symmetry, we have that

$\displaystyle{\mathbb{E}}_{P}[\varphi^{\textup{RESIT}}_{\alpha}(\mathcal{D}^{(n)}_{te},\mathcal{D}^{(m)}_{tr})\mid\mathcal{D}^{(m)}_{tr}]\leq\alpha+\min\left\\{d_{\textup{TV}}\left(P_{\hat{\epsilon},\hat{\eta}\mid\mathcal{D}^{(m)}_{tr}}^{n},P_{\epsilon,\hat{\eta}\mid\mathcal{D}^{(m)}_{tr}}^{n}\right),d_{\textup{TV}}\left(P_{\hat{\epsilon},\hat{\eta}\mid\mathcal{D}^{(m)}_{tr}}^{n},P_{\hat{\epsilon},\eta\mid\mathcal{D}^{(m)}_{tr}}^{n}\right)\right\\}$

∎

######  Lemma B.4.

For any $i\in[n]$, consider that

$\displaystyle(\hat{\epsilon}_{i},\hat{\eta}_{i})\mid\mathcal{D}^{(m)}_{tr}\sim
P_{\hat{\epsilon},\hat{\eta}\mid\mathcal{D}^{(m)}_{tr}},~{}~{}(\epsilon_{i},\hat{\eta}_{i})\mid\mathcal{D}^{(m)}_{tr}\sim
P_{\epsilon,\hat{\eta}\mid\mathcal{D}^{(m)}_{tr}},~{}~{}(\hat{\epsilon}_{i},\eta_{i})\mid\mathcal{D}^{(m)}_{tr}\sim
P_{\hat{\epsilon},\eta\mid\mathcal{D}^{(m)}_{tr}}$
$\displaystyle(\epsilon^{*}_{i},\eta^{*}_{i})\sim
P_{\epsilon^{*},\eta^{*}},~{}~{}(\epsilon_{i},\eta^{*}_{i})\sim
P_{\epsilon,\eta^{*}},~{}~{}(\epsilon^{*}_{i},\eta_{i})\sim
P_{\epsilon^{*},\eta}$

where
$\hat{\epsilon}_{i}=\epsilon_{i}-\delta_{1,P}(Z_{i})-\left(\hat{g}^{(m)}_{1}(Z_{i})-g^{*}_{1,P}(Z_{i})\right)$,
$\epsilon^{*}_{i}=\epsilon_{i}-\delta_{1,P}(Z_{i})$,
$\hat{\eta}_{i}=\eta_{i}-\delta_{2,P}(Z_{i})-\left(\hat{g}^{(m)}_{2}(Z_{i})-g^{*}_{2,P}(Z_{i})\right)$,
and $\eta^{*}_{i}=\eta_{i}-\delta_{2,P}(Z_{i})$. Then, under
$H_{0}:X\mathchoice{\mathrel{\hbox to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}Y\mid Z$ and Assumptions A.6 and A.7, all six
distributions are absolutely continuous with respect to the Lebesgue measure
and their densities are given by

$\displaystyle
p_{\hat{\epsilon},\hat{\eta}\mid\mathcal{D}^{(m)}_{tr}}(e,h\mid\mathcal{D}^{(m)}_{tr})={\mathbb{E}}_{P}\left[p_{\epsilon}\left(e+\delta_{1,P}(Z)+\hat{g}^{(m)}_{1}(Z)-g^{*}_{1,P}(Z)\right)p_{\eta}\left(h+\delta_{2,P}(Z)+\hat{g}^{(m)}_{2}(Z)-g^{*}_{2,P}(Z)\right)\mid\mathcal{D}^{(m)}_{tr}\right]$
$\displaystyle
p_{\epsilon,\hat{\eta}\mid\mathcal{D}^{(m)}_{tr}}(e,h\mid\mathcal{D}^{(m)}_{tr})=p_{\epsilon}(e)\cdot{\mathbb{E}}_{P}\left[p_{\eta}\left(h+\delta_{2,P}(Z)+\hat{g}^{(m)}_{2}(Z)-g^{*}_{2,P}(Z)\right)\mid\mathcal{D}^{(m)}_{tr}\right]$
$\displaystyle
p_{\hat{\epsilon},\eta\mid\mathcal{D}^{(m)}_{tr}}(e,h\mid\mathcal{D}^{(m)}_{tr})={\mathbb{E}}_{P}\left[p_{\epsilon}\left(e+\delta_{1,P}(Z)+\hat{g}^{(m)}_{1}(Z)-g^{*}_{1,P}(Z)\right)\mid\mathcal{D}^{(m)}_{tr}\right]\cdot
p_{\eta}(h)$ $\displaystyle
p_{\epsilon^{*},\eta^{*}}(e,h)={\mathbb{E}}_{P}\left[p_{\epsilon}\left(e+\delta_{1,P}(Z)\right)p_{\eta}\left(h+\delta_{2,P}(Z)\right)\right]$
$\displaystyle
p_{\epsilon,\eta^{*}}(e,h)=p_{\epsilon}(e)\cdot{\mathbb{E}}_{P}\left[p_{\eta}\left(h+\delta_{2,P}(Z)\right)\right]$
$\displaystyle
p_{\epsilon^{*},\eta}(e,h)={\mathbb{E}}_{P}\left[p_{\epsilon}\left(e+\delta_{1,P}(Z)\right)\right]\cdot
p_{\eta}(h)$

Additionally, we have that

$\displaystyle\sup_{(e,h)\in{\mathbb{R}}^{d_{X}\times
d_{Y}}}\left(p_{\hat{\epsilon},\hat{\eta}\mid\mathcal{D}^{(m)}_{tr}}(e,h\mid\mathcal{D}^{(m)}_{tr})-p_{\epsilon^{*},\eta^{*}}(e,h)\right)^{2}=\mathcal{O}_{\mathcal{P}_{0}}(m^{-\gamma})$
$\displaystyle\sup_{(e,h)\in{\mathbb{R}}^{d_{X}\times
d_{Y}}}\left(p_{\epsilon,\hat{\eta}\mid\mathcal{D}^{(m)}_{tr}}(e,h\mid\mathcal{D}^{(m)}_{tr})-p_{\epsilon,\eta^{*}}(e,h)\right)^{2}=\mathcal{O}_{\mathcal{P}_{0}}(m^{-\gamma})$
$\displaystyle\sup_{(e,h)\in{\mathbb{R}}^{d_{X}\times
d_{Y}}}\left(p_{\hat{\epsilon},\eta\mid\mathcal{D}^{(m)}_{tr}}(e,h\mid\mathcal{D}^{(m)}_{tr})-p_{\epsilon^{*},\eta}(e,h)\right)^{2}=\mathcal{O}_{\mathcal{P}_{0}}(m^{-\gamma})$

###### Proof.

Assume we are under $H_{0}$. In order to show that
$P_{\hat{\epsilon},\hat{\eta}\mid\mathcal{D}^{(m)}_{tr}}$ is absolutely
continuous w.r.t. Lebesgue measure (for each training set configuration) and
that its density is given by

$p_{\hat{\epsilon},\hat{\eta}\mid\mathcal{D}^{(m)}_{tr}}(e,h\mid\mathcal{D}^{(m)}_{tr})={\mathbb{E}}_{P}\left[p_{\epsilon}\left(e+\delta_{1,P}(Z)+\hat{g}^{(m)}_{1}(Z)-g^{*}_{1,P}(Z)\right)p_{\eta}\left(h+\delta_{2,P}(Z)+\hat{g}^{(m)}_{2}(Z)-g^{*}_{2,P}(Z)\right)\mid\mathcal{D}^{(m)}_{tr}\right],$

it suffices to show that

$\displaystyle{\mathbb{P}}_{P}((\hat{\epsilon},\hat{\eta})\in
A\mid\mathcal{D}^{(m)}_{tr})=$
$\displaystyle=\int\mathds{1}_{A}(u,v){\mathbb{E}}_{P}\left[p_{\epsilon}\left(u+\delta_{1,P}(Z)+\hat{g}^{(m)}_{1}(Z)-g^{*}_{1,P}(Z)\right)p_{\eta}\left(v+\delta_{2,P}(Z)+\hat{g}^{(m)}_{2}(Z)-g^{*}_{2,P}(Z)\right)\mid\mathcal{D}^{(m)}_{tr}\right]d(u,v)$

for any measurable set $A$.

Using Fubini’s theorem, we get

$\displaystyle{\mathbb{P}}_{P}((\hat{\epsilon},\hat{\eta})\in
A\mid\mathcal{D}^{(m)}_{tr})=$
$\displaystyle={\mathbb{E}}_{P}\left[\mathds{1}_{A}(\epsilon-\delta_{1,P}(Z)-\hat{g}^{(m)}_{1}(Z)+g^{*}_{1,P}(Z),\eta-\delta_{2,P}(Z)-\hat{g}^{(m)}_{2}(Z)+g^{*}_{2,P}(Z))\mid\mathcal{D}^{(m)}_{tr}\right]$
$\displaystyle={\mathbb{E}}_{P}\left[\int\mathds{1}_{A}(e-\delta_{1,P}(Z)-\hat{g}^{(m)}_{1}(Z)+g^{*}_{1,P}(Z),h-\delta_{2,P}(Z)-\hat{g}^{(m)}_{2}(Z)+g^{*}_{2,P}(Z))p_{\epsilon,\eta}(e,h)d(e,h)\mid\mathcal{D}^{(m)}_{tr}\right]$
$\displaystyle={\mathbb{E}}_{P}\left[\int\mathds{1}_{A}(e-\delta_{1,P}(Z)-\hat{g}^{(m)}_{1}(Z)+g^{*}_{1,P}(Z),h-\delta_{2,P}(Z)-\hat{g}^{(m)}_{2}(Z)+g^{*}_{2,P}(Z))p_{\epsilon}(e)p_{\eta}(h)d(e,h)\mid\mathcal{D}^{(m)}_{tr}\right]$
$\displaystyle={\mathbb{E}}_{P}\left[\int\mathds{1}_{A}(u,v)p_{\epsilon}\left(u+\delta_{1,P}(Z)+\hat{g}^{(m)}_{1}(Z)-g^{*}_{1,P}(Z)\right)p_{\eta}\left(v+\delta_{2,P}(Z)+\hat{g}^{(m)}_{2}(Z)-g^{*}_{2,P}(Z)\right)d(u,v)\mid\mathcal{D}^{(m)}_{tr}\right]$
$\displaystyle=\int\mathds{1}_{A}(u,v){\mathbb{E}}_{P}\left[p_{\epsilon}\left(u+\delta_{1,P}(Z)+\hat{g}^{(m)}_{1}(Z)-g^{*}_{1,P}(Z)\right)p_{\eta}\left(v+\delta_{2,P}(Z)+\hat{g}^{(m)}_{2}(Z)-g^{*}_{2,P}(Z)\right)\mid\mathcal{D}^{(m)}_{tr}\right]d(u,v)$

The proof is analogous to the other distributions.

Now, we proceed with the second part of the lemma. Using Assumptions A.6 and
A.7, we get

$\displaystyle\left(p_{\hat{\epsilon},\hat{\eta}\mid\mathcal{D}^{(m)}_{tr}}(e,h\mid\mathcal{D}^{(m)}_{tr})-p_{\epsilon^{*},\eta^{*}}(e,h)\right)^{2}=$