# Pearson Chi-squared Conditional Randomization Test

Adel Javanmard Data Sciences and Operations Department, University of Southern
CaliforniaA. Javanmard is partially supported by the Sloan Research Fellowship
in mathematics, an Adobe Data Science Faculty Research Award and the NSF
CAREER Award DMS-1844481. Mohammad Mehrabi11footnotemark: 1 The names of the
authors are in alphabetical order.

###### Abstract

Conditional independence (CI) testing arises naturally in many scientific
problems and applications domains. The goal of this problem is to investigate
the conditional independence between a response variable $Y$ and another
variable $X$, while controlling for the effect of a high-dimensional
confounding variable $Z$. In this paper, we introduce a novel test, called
‘Pearson Chi-squared Conditional Randomization’ (PCR) test, which uses the
distributional information on covariates $X,Z$ and constructs randomizations
to test conditional independence. Our proposal is motivated by some of the
hard alternatives for the vanilla conditional randomization test [CFJL18].

We also provide a power analysis of the PCR test, which captures the effect of
various parameters of the test, the sample size and the distance of the
alternative from the set of null distributions, measured in terms of a notion
called ‘conditional relative density’. In addition, we propose two extensions
of the PCR test, with important practical implications: $(i)$ parameter-free
PCR, which uses Bonferroni’s correction to decide on a tuning parameter in the
test; $(ii)$ robust PCR, which avoids inflations in the size of the test when
there is slight error in estimating the conditional law $P_{X|Z}$.

##  1 Introduction

Understanding the statistical relationship between random variables is a
cornerstone of many scientific experiments. During the last few decades,
various measures of dependency were developed to capture the association
between two random variables, such as the mutual information and information
theoretic coefficients [RRF+11], the kernel-based measures [PBSP18, ZFGS18],
the correlation coefficients that are based on sample ranks [DHS18, DS21,
WDM18], and the dependency metrics that are based on copulas [Zha19, SE21]; We
refer to this survey [JH13] for other dependency coefficients.

In many modern data science problems, answering profound questions, such as
inferring causal links between different variables, requires a more thorough
analysis. In particular, a desired analysis must control for the presence of
what is known as confounding factors. This happens when an (often unmeasured)
factor $Z$ effects both of the variables of interest (say $X$ and $Y$), and
hence can lead to misleading conclusions about the association of the
variables. For example, in genome-wide association studies (GWAS), researchers
are interested in finding loci that are causal for the trait. However,
spurious association can arise due to ancestry-induced correlations between
causal and non-causal loci, or when ancestry is correlated with both the
genotype and the trait [COL+05, BJCT17].

Conditional independence (CI) testing controls for the effect of such
confounding factors. To further highlight the significance of the CI problem,
it is worth noting that many important problems in statistics can indeed be
cast as a CI testing problem, with examples ranging from the classic concepts
of sufficient and ancillary statistics [Daw79], to the well-known concepts in
graphical models [KF09, Fri04, DHJ+04], and the causal discovery problems
[P+00, ZPJS12, PJS17], where at the heart of all these settings, one can find
a CI testing problem.

In the recent work of [SP20], it is argued that the CI testing is provably a
hard problem without assumptions being placed on the distribution of
variables. Concretely, [SP20] shows that no uniformly valid test111a test that
controls the type I error at a predetermined significance level $\alpha$ for
all absolutely continuous (with respect to the Lebesgue measure) random
variables $(X,Z,Y)$ that are conditionally independent can have nontrivial
power (power exceeding $\alpha$) against any alternative hypothesis (a triple
$(X,Z,Y)$ that are not conditionally independent). By and large, this
impossibility result can be perceived as a consequence of an interesting
phenomenon that happens in the CI testing problem: while the space of the null
distributions are separated from the alternatives, in fact the convex hull of
the null space is a dense set in the alternative space with respect to the
total variation metric [SP20].

The discouraging result of [SP20] highlights the crucial role of the
assumptions on the distribution of $(X,Z,Y)$ in the CI testing problem. This
is a noteworthy observation that such assumptions may make the null space
smaller, so the aforementioned no-free-lunch theorem can not be applied
anymore. During the past few years, several methods have been developed for CI
testing under different setups, such as [NBW20] for one-dimensional variables
satisfying certain smoothness assumptions, and [CDKS18] for discrete
variables. Also there exists quite a large body of work on model-specific
methods, where a parametric model is assumed between the response and the
covariates (assumptions on the law $\mathcal{L}(Y|X,Z)$) [LLZ18, CWZM18,
BCH14]. There is also other concurrent work which goes beyond testing for the
conditional independence and aims at measuring the strength of dependency when
the CI hypothesis does not hold (e.g., [ZJ20, AC19])

Another complimentary line that has been pursued in the past few years is the
model-X perspective [CFJL18]. In this framework, contrary to the classic setup
no assumption is made on the conditional law $\mathcal{L}({Y|X,Z})$, rather it
shifts the focus on $(X,Z)$ and requires an extensive knowledge on the law
$\mathcal{L}({X,Z})$. To emphasize the importance of the model-X setup, one
should note that a set of CI tests that have been developed for a certain
family of distribution $\mathcal{L}({Y|X,Z})$ leads to type I error inflation
under model misspecification. On the other hand, in many settings, you may
have access to abundant unlabeled data which allows for good approximation of
$\mathcal{L}({X,Z})$. For example, in genetic studies [PCS+16, CRC+13] the
joint distribution of covariates can be well approximated. In particular,
[WS10] proposed an estimator to approximate the covariance matrix of
covariates for the genome-wide association study (GWAS), in which genetic
distance information is used.

In this paper, we will focus on CI testing in the model-X setup. In this
setting, we would like to examine the independence of a covariate
$X\in{\mathbb{R}}$ and a response value $Y\in{\mathbb{R}}$, while controlling
for the effect of a potentially high-dimensional confounding covariate vector
$Z\in{\mathbb{R}}^{q}$. This is formalized via a hypothesis testing problem:

$H_{0}:X\perp\\!\\!\\!\perp Y|Z\,,\quad\quad H_{A}:X\not\\!\perp\\!\\!\\!\perp
Y|Z\,.$ (1)

In the model-X CI testing problem, we are given access to the conditional law
$P_{X|Z}$ along with $n$ i.i.d. observations $(X_{i},Y_{i},Z_{i})$ as data,
while the conditional laws $Y|X,Z$ or $Y|Z$ are unknown. A large body of
proposed CI tests in the model-X setup, such as the conditional randomization
test (CRT) [CFJL18], and the holdout-randomization test (HRT) [TVZ+18] are
based on constructing counterfeit data sets, and then scoring them by a
certain score function $T$. In the next step, the normalized rank of the
original data score among the counterfeits is considered as the test
statistic. Under the null hypothesis, the constructed test statistic follows a
uniform distribution, provided that the number of counterfeits is sufficiently
large. The reason is that under $H_{0}$, and conditional on $Y,Z$, the
original and counterfeit scores are i.i.d and so exchangeable. Also, working
with $M$ counterfeits, the smallest value the normalized rank can achieve is
$1/(M+1)$. Therefore, we need sufficiently large $M$ to test at small
significance level $\alpha$. The CRT perceives the extreme values of the
normalized rank (close to 0 or 1) as evidence against the null hypothesis;
however, as we discuss later, it is possible that under alternative hypothesis
the deviation from the uniform distribution occurs at the central range; so
less likely to observe extreme values, hurting the power of CRT. We next
illustrate this point by a concrete example.

###  1.1 Why CRT may fail?: An illustrative example

For a data set $(\mathbf{X},\mathbf{Z},\mathbf{Y})$ consisting of $n$
independent samples with $\mathbf{X}\in{\mathbb{R}}^{n}$,
$\mathbf{Z}\in{\mathbb{R}}^{n\times q}$ an $\mathbf{Y}\in{\mathbb{R}}^{n}$,
the CRT constructs $M$ counterfeits
$(\widetilde{\mathbf{X}}_{1},\mathbf{Z},\mathbf{Y}),...,(\widetilde{\mathbf{X}}_{M},\mathbf{Z},\mathbf{Y})$
where $\widetilde{\mathbf{X}}_{j}$ is sampled independently from the
conditional law $P_{\mathbf{X}|\mathbf{Z}}(\cdot|\mathbf{Z})$. (By
independence of samples, this means that the entries
${\widetilde{X}}_{j,\ell}$ are drawn independently from the law $X|Z$, for
$\ell\in\\{1,2,\dotsc,n\\}$.) Then, for score function $T$ define the
normalized rank:

$p=\frac{1+\sum\limits_{j=1}^{M}{\mathbb{I}}_{\\{T(\mathbf{X},\mathbf{Z},\mathbf{Y})\geq
T(\widetilde{\mathbf{X}}_{j},\mathbf{Z},\mathbf{Y})\\}}}{M+1}\,.$ (2)

We can either reject the null hypothesis for $p$ smaller than $\alpha$
(interpret it as a $p$-value) or reject two extreme $\alpha/2$ tails (two-
sided CRT [WJ20]). Given that
$\widetilde{\mathbf{X}}|\mathbf{Z},\mathbf{Y}\sim\mathcal{L}(\mathbf{X}|\mathbf{Z})$,
under the null hypothesis we have

$T(\mathbf{X},\mathbf{Z},\mathbf{Y})\stackrel{{\scriptstyle
d}}{{=}}T(\widetilde{\mathbf{X}},\mathbf{Z},\mathbf{Y})|\mathbf{Z},\mathbf{Y}\,,$

so $p$ is uniformly distributed in $[0,1]$, and the (one-sided) cutoff
$\alpha$ or the (two-sided) cutoff $\alpha/2$ give valid tests. On the other
hand, the power of the test relies merely on observing extremely small or
large values of $p$, which reflects a restricted outlook on deviation from the
uniform distribution. In particular, this class of CI tests falls short in
capturing the inflations on central values and results in a lower statistical
power (See Figure 2 for a schematic representation). To illustrate this point,
we provide a simple independence testing problem with two real-valued random
variables $X,Y$ from the following probability laws (for the sake of
simplicity, we assume $Z=\emptyset$):

$\displaystyle X$ $\displaystyle\sim\mathsf{N}(0,1)\,,$ $\displaystyle Y$
$\displaystyle=\frac{1}{\sqrt{10^{-6}+X^{2}}}+{\varepsilon},\quad{\varepsilon}\sim\mathsf{N}(0,1)\,.$
(3)

Obviously $X$, $Y$ are dependent, and the null hypothesis 1 is not true.
Assume the original data set $(\mathbf{X},\mathbf{Y})$ consists of $n=1000$
data points, and let the score function $T$ be the $\ell_{2}$-square loss
$T(\mathbf{X},\mathbf{Y})=\|\mathbf{Y}-\mathbf{X}\|^{2}_{2}$. We run the two-
sided CRT at significance level $\alpha=0.1$ with $M=1000$ counterfeits. The
statistical power of CRT, averaged over $N=10,000$ experiments, is zero! The
histogram for the normalized rank (2) is depicted in Figure 1. As can be seen
from the plot, most of the p-values are around 0.5. In other words, the
deviation from a uniform distribution is occurring at the central range
instead of the $\alpha/2$ tails, and CRT fails to discern the dependency
between $X,Y$. We refer to Section 9.2 for further details and the intuition
behind the construction of this example. We extend this example in section 2
in that we show for a class of regression problems $y=g(x)+{\varepsilon}$,
with ${\varepsilon}\sim\mathsf{N}(0,1)$ and $g$ satisfying certain conditions,
CRT provably has power smaller than $\alpha/2$. The ratio $1/2$ here is for
simplicity, and can be made arbitrarily small for specific functions $g$.

Figure 1:  Histogram of the normalized rank $p$ given by (2), with $M=1000$
and the $\ell_{2}$-square loss
$T(\mathbf{X},\mathbf{Y})=\|\mathbf{Y}-\mathbf{X}\|^{2}_{2}$ as the score
function. The original data set have $n=1000$ data points
$\\{(X_{i},Y_{i})\\}_{i=1}^{n}$ which are generated from (1.1). The histogram
is obtained by considering $N=10,000$ realizations of the data. The horizontal
purple line represents the uniform distribution. As observed, the normalized
ranks are mostly in the central range, leading the CRT to have zero
statistical power.

(a) One-sided inflation

(b) Two-sided inflation

(c) Middle-value inflation

Figure 2: Schematic representations of the distribution of the normalized rank
$p$ under alternative hypothesis. The horizontal purple line indicates the
uniform distribution. In (a), (b), the non-null p-value has higher tail
compared to the null uniform distribution and the CRT (one-sided for (a) and
two-sided for (b)) would have descent power. In (c), the non-null p-value is
more likely to fall in the middle range which causes the CRT to have low power

###  1.2  Related work on model-X CI tests

The Conditional Randomization Test (CRT) was originally proposed by [CFJL18]
as a generic framework that exploits the distributional information $X|Z$ to
control the type I error for any score function, and number of data points
(valid finite-sample results). This flexibility of the CRT allows for using
any advanced black box predictive model, which plays a key role in achieving
high statistical power for the CI testing problem. In [WJ20] the authors
analyze the power of CRT in a high-dimensional linear regression setting for
three different score functions: marginal covariance based scores, the
ordinary least square coefficient and the LASSO [Tib96]. Further, [KR20] shows
that the CRT with a likelihood-based score function is the most powerful
model-X CI test against a point alternative.

On the computational side, using advanced black box predictive models in the
CRT can be prohibitively daunting, due to the repetitive fittings of the score
function on the resampled data. This issue is even exacerbated in multiple
testing, where the CRT is used for the feature selection problem. In this
approach, the CRT is run for each covariate separately to test its relevance
to the response, conditioned on the other covariates. Such multiple usage of
the CRT is computationally prohibitive in high-dimensional problems.
Alternatively, one can use the model-X knockoff approach proposed by [CFJL18]
to circumvent this issue, which of course assumes the knowledge of the
covariates joint distribution. Several recent works extended this procedure
beyond the multivariate Gaussian distribution for a broader range of the
covariates joint population, see [SSC17] for hidden Markov models, and
[BCJW20] which introduced the Metropolis knockoff sampling for cases where the
covariates are continuous and follow a graphical model. Despite the fact that
the model-X knockoff procedure has alleviated the CRT computational burden,
this benefit often comes at the cost of a lower statistical power [CFJL18,
Section 5.3]. For high-dimensional linear models, [WJ20] shows that the CRT
provably dominates model-X knockoffs in the variable selection problem. More
precisely, they show that under the high-dimensional linear setup, when the
Benjamini–Hochberg (BH) procedure [BH95], or the adaptive p-value thresholding
(AdaPT) procedure [LF18] is applied on the CRT p-values, a higher statistical
power is achieved in comparison to the model-X framework.

Several other methods have also been proposed recently to improve the heavy
computational cost of CRT, such as the Holdout Randomization Test (HRT)
[TVZ+18] and the Conditional Randomization Test with Distillation (dCRT)
[LKJR20]. In [BWBS20] the authors have proposed the Conditional Permutation
Test (CPT) to enhance the robustness of CRT with respect to approximation
errors in the law of $X|Z$.

###  1.3 Summary of contributions

In this paper, we introduce a novel method called the Pearson Chi-squared
Conditional Randomization (PCR) test, which is a general method for
investigating the conditional independence of two variables $X,Y$ in the
presence of a high-dimensional confounding variable $Z$. The proposed method
is designed for model-X framework where the conditional law $X|Z$ is assumed
to be known, but the method assumes nothing whatsoever about $Y|(X,Z)$. The
PCR test is inspired by shortcoming of the conditional randomization test
(CRT) [CFJL18] in rejecting specific alternative distributions. Similar to
CRT, the PCR test uses randomization to construct multiple counterfeits of the
data and rank the original data among their counterfeits according to a score
function. The score function can be based on arbitrary (potentially complex)
predictive models. In contrast to CRT, the PCR test works at the sample levels
and label each sample based on its rank among the corresponding counterfeits
while CRT works at dataset level. The PCR test includes a Pearson
$\chi^{2}$-test at heart which allows to scrutinize the entire support of the
ranks distribution to detect statistically significant deviations from the
discrete uniform, while the CRT focuses on the deviations at the tails of the
distribution. As we show in numerical experiments, the PCR test achieves
relatively high power even with a small number of counterfeits, while other
model-X CI tests require substantially a large number of counterfeits to
achieve high power.

The rest of the paper presents the following contributions:

  1. 1.

Section 2: We discuss some alternatives which while stands far from the null
distribution (i..e, the response value $Y$ and the covariate $X$ are highly
dependent), yet the CRT is provably powerless in rejecting them, even with
arbitrarily large sample size and number of counterfeits.

  2. 2.

Section 3: We present the PCR test statistic, and provide two rejection
thresholds for it to control the size of the test under a target level
$\alpha$. One threshold indicated by $\theta_{L,\alpha}^{\mathsf{finite}}$ is
guaranteed to control the size even in finite-sample regime, while the other
threshold $\theta_{L,\alpha}^{\mathsf{asymp}}$ controls the size for large
enough sample size (asymptotic regime). Of course, the former turns out to be
more conservative and in our numerical study we observe that for $n$ of order
a few hundreds, the size of test is already controlled using the threshold
$\theta_{L,\alpha}^{\mathsf{asymp}}$.

  3. 3.

Section 4: We provide a power analysis of the PCR test. Distance of
alternative distributions to the set of null distributions is measured via a
notion called ‘conditional relative density’, which depends on both the joint
law $\mathcal{L}(X,Y,Z)$ as well as the score function. Our analysis reveals
the role of different factors, such as sample size, number of counterfeits and
number of labels which are the input parameters for the PCR test.

  4. 4.

Section 5: As our power analysis reveals, the number of labels ($L$) used in
the PCR test effects its power in a non-trivial ways. Here, we suggest to run
PCR test for different choices of $L$ and then use Bonferroni’s correction to
combine the resulting $p$-values into a valid $p$-valid for the conditional
independence hypothesis.

  5. 5.

Section 6: While in the model-X framework it is assumed that the conditional
law $\mathcal{L}(X|Z)$ is known, in practice one may need to estimate this
distribution (e.g., from unlabeled data). In this section, we provide a more
conservative version of the PCR test which is more robust to errors in
estimating $\mathcal{L}(X|Z)$, and avoids inflation in the type I error.

  6. 6.

Section 8: We evaluate the performance of the PCR test on several simulated
data and on the Capital Bikeshare data set.

Notations. Throughout the paper, we use the shorthands $[n]=\\{1,2,...,n\\}$
for an integer $n\geq 1$, also $a\wedge b=\min\\{a,b\\}$. We use the capital
letters for random variables and the small letters for the specific values
they may take. We use bold symbols for vectors and matrices. For random
variables or vectors $U,V$, $\mathcal{L}(U)$ represents the probability law
(distribution) of $U$ and $\mathcal{L}(U|V)$ represents the conditional
distribution of $U$ given V. We write $U\stackrel{{\scriptstyle d}}{{=}}V$ to
indicate that $U$ and $V$ have the same distribution. For an event $E$, we
denotes its probability by ${\mathbb{P}}(E)$. We use $\stackrel{{\scriptstyle
p}}{{\Rightarrow}}$ to indicate convergence ‘in probability’ and
$\stackrel{{\scriptstyle d}}{{\Rightarrow}}$ for convergence ‘in
distribution’. Throughout, $\phi(t)=e^{-t^{2}/2}/\sqrt{2\pi}$ is the Gaussian
density and $\Phi(u)=\int_{-\infty}^{u}\phi(t){\rm d}t$ is the Gaussian
distribution.

##  2 Why CRT may fail?: A formal result

In this section, we delineate the two problems associated with CRTs for CI
testing in a model-X setup. Before getting into details, let us briefly recall
the CRT procedure and introduce some notations. Assume we are given $n$ i.i.d.
data points $(X_{i},Y_{i},Z_{i})_{i=1}^{n}$, and denote the original data set
by $\mathcal{D}=(\mathbf{X},\mathbf{Y},\mathbf{Z})$. We use a score function
$T$ to score each data set. This can be a simple squared error loss
$T(\mathcal{D})=||\mathbf{Y}-\mathbf{X}||^{2}$, or a more complicated
function, for example the absolute value of the coefficient for $\mathbf{X}$
fitted by the Lasso on $\mathcal{D}$, or even more advanced models, such as
deep neural networks or random forests. In model-X setup, we assume having
access to the conditional law $\mathcal{L}_{\mathbf{X}|\mathbf{Z}}$, and
construct counterfeit data sets
$\widetilde{\mathcal{D}}_{1}=(\widetilde{\mathbf{X}}_{1},\mathbf{Y},\mathbf{Z}),...,\widetilde{\mathcal{D}}_{M}=(\widetilde{\mathbf{X}}_{M},\mathbf{Y},\mathbf{Z})$,
for sufficiently large $M$, where $\widetilde{\mathbf{X}}_{j}$, $j\in[M]$ are
sampled independently from $\mathcal{L}({\mathbf{X}|\mathbf{Z}})$. In the next
step, we construct the normalized rank statistic given by

$p=\frac{1+\sum\limits_{j=1}^{M}{\mathbb{I}}_{\\{T(\mathcal{D})\geq
T(\mathcal{D}_{i})\\}}}{M+1}\,.$

Under the null hypothesis $X\perp\\!\\!\\!\perp Y|Z$, and $\mathbf{X}$ can be
perceived as another draw from $\mathcal{L}(\mathbf{X}|\mathbf{Z})$
independently from $\mathbf{Y}$. This implies exchangeability of the scores
and that the statistic $p$ follows a uniform distribution over the set
$\\{1/(M+1),2/(M+1),...,M/(M+1),1\\}$. The first problem can be noticed here:
in order to make any rejection we require $M$ to be at least $1/\alpha$, and
for small significance $\alpha$ this may cause computational hurdle since you
need to compute the score of each counterfeit. The second problem about the
CRT is the rejection region. Since under the null hypothesis, the statistic
$p$ follows a uniform distribution, observing its extreme values (close to 0
or 1) can be interpreted as evidence against the CI hypothesis. Now if under
an alternative, the statistic $p$ deviates from uniform distribution by
showing an inflation on the central range and deflation on the tails, then
this deviation is not detected by CRT. In particular this may cause CRT to
have power less than $\alpha$ (worse than random guessing).

Our next theorem demonstrates such behavior in a regression setting. For
simplicity, it considers $Z=\emptyset$ and proposes a setting where CRT
provably gets power less than $c_{0}\alpha$, for any arbitrarily small but
fixed $c_{0}>0$. Before proceeding to the theorem, we prove a concentration
result for the CRT p-statistic given by (2).

######  Proposition 2.1.

Consider an even function $g$, and a dataset $(\mathbf{X},\mathbf{Y})$ of $n$
i.i.d pairs $\\{(X_{i},Y_{i})\\}_{i=1}^{n}$, with
$X_{i},Y_{i}\in{\mathbb{R}}$, generated from the following regression model:

$\displaystyle X$ $\displaystyle\sim\mathsf{N}(0,1)\,,$ $\displaystyle Y$
$\displaystyle=g(X)+{\varepsilon}\,,\quad{\varepsilon}\sim\mathsf{N}(0,1)\,.$
(4)

For the score function
$T(\mathbf{X},\mathbf{Y})=\||\mathbf{X}-\mathbf{Y}\||_{2}^{2}$, and
counterfeit datasets $\widetilde{\mathbf{X}}_{j}\sim\mathsf{N}(0,I_{n})$,
recall the CRT $p$ statistic:

$\displaystyle
p^{(M)}_{n}=\frac{1+\sum\limits_{j=1}^{M}{\mathbb{I}}_{\\{T(\mathbf{X},\mathbf{Y})\geq
T(\widetilde{\mathbf{X}}_{j},\mathbf{Y})\\}}}{M+1}\,.$ (5)

Then, the statistic $p^{(M)}_{n}$ concentrates around $1/2$. In particular,
for any $\delta>0$ and $M>1/\delta$, we have

$\lim\limits_{n\rightarrow\infty}{\mathbb{P}}\left(\left|p^{(M)}_{n}-1/2\right|\geq\delta\right)\leq\frac{1}{\left(\delta-1/M\right)^{2}}\left(\frac{1}{4M}+\frac{M-1}{M}\Big{(}{\mathbb{E}}_{Z\sim\mathsf{N}(0,1)}[\Phi^{2}(\eta
Z)]-\frac{1}{4}\Big{)}\right)\,,$

with
$\eta=\left(\frac{3+2{\mathbb{E}}[X^{2}g(X)^{2}]}{3+2{\mathbb{E}}[g(X)^{2}]}\right)^{1/2}$.

We refer to Section 9.3 for the proof of this proposition.

The next corollary considers a set of even functions parametrized by $\theta$
and shows that for every significance level $\alpha$, by having $\theta$ small
enough (depending on $\alpha$), the power of CRT is smaller than $\alpha/2$.

######  Theorem 2.2.

For an even function $g$, consider the following model between the response
variable $Y$ and covariate $X$:

$\displaystyle X$ $\displaystyle\sim\mathsf{N}(0,1)\,,$ $\displaystyle Y$
$\displaystyle=g(X)+{\varepsilon}\,,\quad{\varepsilon}\sim\mathsf{N}(0,1)\,,$

with the regression function $g(x)=\frac{1}{\sqrt{\theta^{2}+x^{2}}}$ Then,
the followings hold:

  * $(a)$

For any $\alpha\in(0,1/2)$, and small enough $\theta$ such that
$\theta\leq\alpha^{2}/500$, the two-sided CRT at significance level $\alpha$
(reject $\alpha/2$-th upper and lower quantiles) has power smaller than
$\alpha/2$. Formally,

$\lim\limits_{M\rightarrow\infty}\lim\limits_{n\rightarrow\infty}{\mathbb{P}}\Big{(}\Big{|}p_{n}^{(M)}-\frac{1}{2}\Big{|}\geq\frac{1-\alpha}{2}\Big{)}\leq\alpha/2\,.$

  * $(b)$

For any $\alpha\in(0,1/2-\gamma)$ with $\gamma>0$, and for small enough
$\theta$ such that $\theta\leq\gamma^{4}\alpha^{2}/2$, the one-sided CRT at
significance level $\alpha$ (rejecting either $\alpha$-th upper or lower
quantile) has power smaller than $\alpha/2$. Formally,

$\displaystyle\lim\limits_{M\rightarrow\infty}\lim\limits_{n\rightarrow\infty}{\mathbb{P}}\left(p_{n}^{(M)}\geq
1-\alpha\right)\leq\frac{\alpha}{2}\,,\quad\lim\limits_{M\rightarrow\infty}\lim\limits_{n\rightarrow\infty}{\mathbb{P}}\left(p_{n}^{(M)}\leq\alpha\right)\leq\frac{\alpha}{2}\,.$

We refer to Section 9.4 for the proof of Theorem 2.2.

##  3 Pearson Chi-squared randomization (PCR) test

Motivated by the issues of CRT discussed in the previous section, in this work
we propose a novel test, called Pearson $\chi^{2}$ conditional randomization
(PCR) test. We start by describing the PCR test and its test statistic. We
then characterize the null distribution of its statistic by which we propose
two rejection thresholds, for finite and infinite sample regimes.

###  3.1 PCR test statistic

We construct the PCR test statistic in three main steps:

Counterfeit sampling.

This is a common step in model-X conditional independence testing methods,
where for each data point $(X_{j},Y_{j},Z_{j})$ several counterfeits of the
form $({\widetilde{X}}_{j},Y_{j},Z_{j})$ are constructed by sampling
${\widetilde{X}}_{j}\sim\mathcal{L}_{X|Z}$ while keeping $Y_{j},Z_{j}$ intact.
As we will discuss a main distinction of our PCR test with other CRT approach
is that the PCR test works with few number of counterfeits while, in CRT
approach, one requires a large number of counterfeits (at least of order
$1/\alpha$), given that the normalized rank statistic (2) is intrinsically
discrete.

Score and label.

Given a score function $T$, we score each data point $(X_{j},Y_{j},Z_{j})$ and
then label the data points based on the relative location of the score of the
original data point among the scores of its counterfeits. Specifically, we
partition the range of possible ranks in to $L$ subsets, $S_{1},\dotsc,S_{L}$,
of equal size and assign label $\ell$ to data points whose score rank falls in
$S_{\ell}$. Special cases of this idea (with $L=2$ labels and unbalanced
groups) can be traced in conformal inference literature [VGS05, LGR+18, LW14,
RPC19], where the sample quantile of the non-conformity scores are compared to
a certain threshold to construct prediction intervals.

Uniformity testing in a multinomial model.

Under the null hypothesis (1), by using the exchangeability of data scores and
their counterfeits scores, it is straightforward to see that each label occurs
with equal frequency (with expected count of each label being $n/L$). In this
step, we use the Pearson Chi-squared test statistic $U_{n,L}$ to test
uniformity of label occurrences in a multinomial model with $n$ samples and
$L$ labels. Note that, in general $L$ can scale with $n$, and as discussed in
[BW+19], the $\chi^{2}$ test can have bad power due to the fact that the
variance of the $\chi^{2}$ statistics is dominated by small entries of the
multinomial. A truncated version of $\chi^{2}$ statistic has been proposed by
[BW+19] to mitigate this issue by limiting the contribution to the variance
from each label. However, when testing for a uniform distribution, as in our
case, the truncation becomes superfluous. This implies that in this case, the
usual $\chi^{2}$ statistic inherits several appealing properties of the
truncated $\chi^{2}$ statistic. In particular, [BW+19] showed that truncated
$\chi^{2}$ test is globally minimax optimal for the multinomial problem. It is
worth noting that for the multinomial testing problem in high dimension ($L$
growing with $n$), the upper and lower bounds on the critical radius
${\varepsilon}$ has been established in [Pan08, VV17]. Concretely, it has been
shown that $O(\sqrt{L}/{\varepsilon}^{2})$ number of samples are sufficient
and information-theoretically necessary for distinguishing uniform
distributions from alternatives that are ${\varepsilon}$ far in the
$\ell_{1}$-ball, with success probability larger than $2/3$.

A detailed description for construction of the PCR statistic is given in
Algorithm 1.

0: $n$ data points
$(X_{j},Y_{j},Z_{j})\in{\mathbb{R}}\times{\mathbb{R}}\times{\mathbb{R}}^{q}$,
a real-valued score function
$T:{\mathbb{R}}\times{\mathbb{R}}\times{\mathbb{R}}^{q}\mapsto{\mathbb{R}}$,
and integers $K,L\geq 1$ (let $M=KL-1$).

0: Test statistics $U_{n,L}$ for testing the conditional independence
hypothesis (1).

for  _$j\in[n]$_ do

  * •

Draw $M$ i.i.d. samples
${\widetilde{X}}_{j}^{(1)},...,{\widetilde{X}}_{j}^{(M)}$ from
$\mathcal{L}_{X|Z}(\cdot|Z_{j})$.

  * •

Use $T$ to score the initial data point $(X_{j},Y_{j},Z_{j})$ and its $M$
counterfeits $({\widetilde{X}}_{j}^{(1:M)},Y_{j},Z_{j})$:

$\displaystyle T_{j}$ $\displaystyle=$ $\displaystyle T(X_{j},Y_{j},Z_{j})\,,$
$\displaystyle\widetilde{T}_{j}^{(i)}$ $\displaystyle=$ $\displaystyle
T({\widetilde{X}}_{j}^{(i)},Y_{j},Z_{j}),\quad\text{ for }i\in[M]\,.$

  * •

Let $R_{j}$ denote the rank of $T_{j}$ among
$\\{T_{j},\widetilde{T}_{j}^{(1)},...,\widetilde{T}_{j}^{(M)}\\}$:

$R_{j}=1+\sum\limits_{i=1}^{M}{\mathbb{I}}_{\left\\{T_{j}\geq\widetilde{T}_{j}^{(i)}\right\\}}$

  * •

Partition $[M+1]=S_{1}\cup\dotsc\cup S_{L}$ with
$S_{\ell}:=\\{(\ell-1)K+1,\dotsc,\ell K\\}$. Assign label
$\ell_{j}\in\\{1,2,...,L\\}$ to sample $j$ if $R_{j}\in S_{\ell_{j}}$.

end for

for  _$\ell\in\\{1,2,\dotsc,L\\}$_ do

  * •

Let $W_{\ell}$ be the number of samples with label $\ell$:
$W_{\ell}:=\Big{|}\big{\\{}j\in\\{1,2,...,n\\}:\ell_{j}=\ell\big{\\}}\Big{|}\,.$

end for

  * •

Define the test statistic $U_{n,L}$ as follows

$\displaystyle
U_{n,L}=\frac{L}{n}\sum\limits_{\ell=1}^{L}\left(W_{\ell}-\frac{n}{L}\right)^{2}\,.$
(6)

Algorithm 1 PCR test statistic

###  3.2 Decision rule

We introduce two rejection thresholds for the hypothesis testing problem (1)
with the statistic $U_{n,L}$ given by (6). At significance level $\alpha$, the
decision rule is based on the test statistic:

$\phi\left(\mathbf{X},\mathbf{Z},\mathbf{Y}\right)=\begin{cases}1&U_{n,L}\geq\theta_{L,\alpha}\quad(\text{reject
}H_{0})\,,\\\ 0&\text{otherwise}\quad~{}~{}(\text{accept
}H_{0})\,.\end{cases}$ (7)

For the threshold $\theta_{L,\alpha}$ we consider two proposals:

$\displaystyle\theta_{L,\alpha}^{\mathsf{asym}}:=\chi^{2}_{L-1}(1-\alpha),\quad\theta_{L,\alpha}^{\mathsf{finite}}=L+\sqrt{\frac{2L}{\alpha}}\,,$
(8)

where $\chi^{2}_{L-1}(1-\alpha)$ denotes the $1-\alpha$ quantile of a
$\chi^{2}$ distribution with $L-1$ degrees of freedom. As we show in the next
section, the size of PCR test is controlled asymptotically (as $n\to\infty$)
with using $\theta_{L,\alpha}^{\mathsf{asym}}$. In addition, by using
$\theta_{L,\alpha}^{\mathsf{finite}}$, we prove that the size is controlled at
finite sample settings.

As clear form its description, and similar to the CRT, the PCR test looks for
statistically significant deviations between the distribution of the rank of
original scores and the uniform distribution. While CRT only examines the
tails of the distributions, the PCR test examines the entire support by
comparing the two distributions on $L$ bins (corresponding to labels) of equal
size and is able to capture deviations occurring in the middle range as well
as at the tails.

Revisiting the numerical example in Section 1.1.  Recall the numerical example
in Section 1.1, with $n=1000$ data points
$\\{(X_{i},Z_{i},Y_{i})\\}_{i=1}^{n}$ generated from the conditional laws
(1.1). As we saw, the CRT is powerless in this setting. Here, we run the PCR
test on the same example, with $L=5$ and different values for $K$. The number
of counterfeits per each sample is therefore $M=5K-1$. We consider both of the
rejection thresholds $\theta^{\mathsf{asym}},\theta^{\mathsf{finite}}$ for
decision rule (7). Table 1 reports the power of PCR test for different values
of $K$ (so different values of counterfeits.) As we see, it has high power
with both of the thresholds and for various choices of $K$. This is an
illustration of the PCR test overcoming the issues with the CRT test as
discussed in Section 1.1.

Setup | $K=1$ | $K=4$ | $K=10$ | $K=20$
---|---|---|---|---
$\chi^{2}$-CI test with $\theta^{\mathsf{finite}}_{L,\alpha}$ | 0.8856 | 0.9941 | 0.9981 | 0.9993
$\chi^{2}$-CI test with $\theta^{\mathsf{asym}}_{L,\alpha}$ | 0.9926 | 1.00 | 1.00 | 1.00
Table 1: Statistical power of the PCR test applied to a dataset of size
$n=1000$ generated according to the regression setting in Section 1.1. PCR
test is used with two rejection thresholds
$\theta_{L,\alpha}^{\mathsf{finite}}$, $\theta_{L,\alpha}^{\mathsf{asymp}}$
with number of labels $L=5$ and at significance level $\alpha=0.1$. Different
values of $K$ are chosen which determine the number of counterfeits per each
sample as $M=KL-1$. Reported values are averaged out over $10000$ experiments.

###  3.3 Size of the PCR test

Under the null hypothesis, the original and counterfeit scores are coming from
a similar population. Our next assumption on the continuity of random
variables ensures that the different data points achieve distinct score
values, with probability one. This symmetry on distinct values implies that
each data point gets label $\ell\in[L]$ uniformly at random. In short, we
change the problem of conditional independence testing into the uniformity
testing problem on data points coming from a multinomial distribution.

######  Assumption 3.1.

For a score function $T$, assume that the following conditional cumulative
distribution functions are continuous, for every pair $(y,z)$:

$\displaystyle F_{T|ZY}(t;z,y)$ $\displaystyle:=$
$\displaystyle{\mathbb{P}}_{{X|ZY}}\left(T(X,z,y)\leq t|Z=z,Y=y\right)\,,$ (9)
$\displaystyle F_{T|Z}(t;z,y)$ $\displaystyle:=$
$\displaystyle{\mathbb{P}}_{{X|Z}}\left(T(X,z,y)\leq t|Z=z,Y=y\right)\,.$ (10)

Note that both $F_{T|ZY}$ and $F_{T|Z}$ are conditional on $Y,Z$, and
randomness is coming from $X$. The difference is that in $F_{T|ZY}$, we have
$X\sim\mathcal{L}(X|ZY)$, while in $F_{T|Z}$, we have $X\sim\mathcal{L}(X|Z)$.

It is worth noting that the above assumption, which is used to transform the
conditional independence testing problem into a multinomial uniformity testing
problem, is indeed a weak assumption. It is used to avoid ties when ranking
the scores, and alternatively one can use a random tie-breaking decision rule
and remove this assumption.

In the next theorem, we show that by using $\theta_{L,\alpha}^{\mathsf{asym}}$
in the decision rule (7) asymptotic control on type I error is guaranteed. It
is an immediate consequence of characterizing the asymptotic distribution of
$U_{n,L}$ statistic in Algorithm 1. Furthermore, we show that deploying the
rejection threshold $\theta_{L,\alpha}^{\mathsf{finite}}$ results in finite-
sample control on the type I error.

######  Theorem 3.2.

Under the null hypothesis (1) and Assumption (3.1) , the statistic $U_{n,L}$
constructed in Algorithm 1 will converge to $\chi^{2}$ distribution with $L-1$
degrees of freedom, for $L\geq 2$:

$U_{n,L}\overset{d}{\Rightarrow}\chi^{2}_{L-1},\quad\text{ as
}n\rightarrow\infty\,.$

In addition, for every $n\geq 1$, we have

${\mathbb{P}}\left(U_{n,L}\geq\theta_{L,\alpha}^{\mathsf{finite}}\right)\leq\alpha\,,$

with $\theta_{L,\alpha}^{\mathsf{finite}}=L+\sqrt{\frac{2L}{\alpha}}$.

We refer to Section 9.5 for the proof of Theorem 3.2.

Based on the above characterization of the null distribution, in finite sample
and asymptotic regimes, we can construct the following $p$-values for the
testing problem (1):

$P^{\mathsf{finite}}_{n,L}=\begin{cases}1,&U_{n,L}\leq L\,,\\\
\min\left\\{\dfrac{2L}{(U_{n,L}-L)^{2}},1\right\\},&\text{otherwise}\,.\end{cases}$
(11) $P^{\mathsf{asym}}_{n,L}=1-{\sf F}_{L-1}(U_{n,L})\,,$ (12)

where ${\sf F}_{k}$ is the cdf of a chi-squared random variable with $k$
degrees of freedom.

Note that under the null hypothesis, $p$-value $P^{\mathsf{asym}}_{n,L}$ is
asymptotically uniform, whereas $P^{\mathsf{finite}}_{n,L}$ is super-uniform
for finite $n$. Formally, for all $t\in[0,1]$

$\displaystyle\lim\limits_{n\rightarrow\infty}{\mathbb{P}}\left(P^{\mathsf{asym}}_{n,L}\leq
t\right)=t\,,$ $\displaystyle{\mathbb{P}}\left(P^{\mathsf{finite}}_{n,L}\leq
t\right)\leq t\,,\quad\forall n\geq 1\,.$

##  4 A power analysis of the PCR test

We next provide a power analysis of the PCR test . To this end, we need a
notion of distance between a probability density function $p_{XZY}(x,z,y)$ and
its corresponding conditional independence density
$p_{X}(x)p_{Z|X}(z|x)p_{Y|Z}(y|z)$, where $p_{Y|Z}(y|z)$ is obtained by
marginalizing out $X$, i.e., $p_{Y|Z}(y|z)=\int
p_{Y|XZ}(y|x,z)p_{X|Z}(x|z){\rm d}x$. As expected, the larger this distance,
the easier to discern the conditional dependency. The metric that we use here
to analyze the power of PCR test is a generalization of the notion of _ordinal
dominance curve_ (ODC) [HT+96, Bam75]. For two densities $p$ and $q$ defined
on the real line, the ODC is given by $F_{p}(F_{q}^{-1}(t))$, where
$F_{p},F_{q}$ respectively denote the cdfs corresponding to $p$ and $q$. In
other words, the ODC is the population analogous of the PP plot. The
derivative of the ODC (if exists) is given by
$f_{p}(F_{q}^{-1}(t))/f_{q}(F^{-1}_{q}(t))$ and is called the _relative
density function_ ([Tha10], Section 2.4).

We next define the conditional ODC and the conditional relative density
function, along with two assumptions. Let us emphasize that the upcoming
assumptions are made to facilitate the power analysis, and the validity of the
PCR test (control on type I error) holds even without these assumptions.

######  Definition 4.1.

(Conditional ODC and relative density function). For a score function $T$,
recall the conditional cdfs $F_{T|ZY}(t;z,y)$ and $F_{T|Z}(t;z,y)$ given by
equations (9) and (10). We define the conditional ordinal dominance curve
$\mathsf{R}_{T}:[0,1]\rightarrow[0,1]$ as follows:

$\mathsf{R}_{T}(u)={\mathbb{E}}_{(Z,Y)\sim\mathcal{L}(Z,Y)}\left[F_{T|ZY}\left(F_{T|Z}^{-1}\big{(}u;Z,Y\big{)};Z,Y\right)\right]\,.$

For Differentiable $\mathsf{R}_{T}$, we call its derivative the conditional
relative density function: $\mathsf{r}_{T}(u):=\frac{\partial}{\partial
u}\mathsf{R}_{T}(u)\,,$ for $u\in(0,1)$.

######  Assumption 4.2.

Assume the conditional relative density function $\mathsf{r}_{T}(u)$ is
$C$-Lipschitz continuous. This also implies that $\mathsf{r}_{T}(u)$ is
uniformly bounded, i.e.,

$\sup\limits_{u\in[0,1]}|\mathsf{r}_{T}(u)|\leq B\,,$

for some constant $B>0$.

Our next assumption is a sufficient condition to replace the order of the
expectation and the derivative in the definition of $\mathsf{r}_{T}(u)$ (see
(45)).

######  Assumption 4.3.

We assume that

$\int_{0}^{1}{\mathbb{E}}_{(Z,Y)\sim\mathcal{L}(Z,Y)}\Big{[}\Big{|}\frac{\partial}{\partial
u}F_{T|ZY}\Big{(}F_{T|Z}^{-1}\big{(}u;Z,Y\big{)};Z,Y\Big{)}\Big{|}\Big{]}{\rm
d}u<\infty\,.$

We are now ready to define a distance between the distribution of $(X,Z,Y)$
and $({\widetilde{X}},Z,Y)$ where ${\widetilde{X}}\sim\mathcal{L}(X|Z)$,
independently of $Y$. Note that the two densities match under the null
hypothesis (1).

######  Definition 4.4.

For a score function $T$ and its relative density function
$\mathsf{r}_{T}(.)$, define conditional dependency power as

$\Delta_{T}(\mathcal{L}(X,Z,Y))=\int\limits_{0}^{1}|\mathsf{r}_{T}(u)-1|{\rm
d}u\,.$

We next state some properties of the measure $\Delta_{T}(\mathcal{L}(X,Z,Y))$.
Recall that for two random variables $U,V$ with density functions $p,q$ (with
respect to the Lebesgue’s measure), the total variation distance is defines as

$d_{\mathsf{TV}}=\frac{1}{2}\int_{-\infty}^{\infty}|p(t)-q(t)|{\rm d}t\,.$

######  Remark 4.5.

The followings hold for the measure $\Delta_{T}(\mathcal{L}(X,Z,Y))$.

  * (a)

Under the null hypothesis (1), for any score function $T$ satisfying
Assumption 3.1 we have $\Delta_{T}(\mathcal{L}(X,Z,Y))=0$.

  * (b)

The following upper bound holds in general:

$\Delta_{T}(\mathcal{L}(X,Z,Y))\leq{\mathbb{E}}_{(Z,Y)\sim\mathcal{L}(Z,Y)}\left[2d_{\mathsf{TV}}\left((T({\widetilde{X}},Z,Y)|Z,Y),(T(X,Z,Y)|Z,Y)\right)\right],$

with $X\sim\mathcal{L}(X|Z,Y)$ and ${\widetilde{X}}\sim\mathcal{L}(X|Z)$.

We refer to Section 9.6 for the proof of Remark 4.5.

As discussed earlier, the PCR test transforms the conditional independence
problem into the problem of uniformity testing under a multinomial model. That
said, in order to analyze the power of PCR test we focus on the later problem.
We use the results of [BW+19] which characterize the power of truncated
$\chi^{2}$-test for a high-dimensional multinomial model, in terms of the
$\ell_{1}$ distance between the nominal probabilities and the uniform
distribution over the categories. However, it is not clear how the nominal
probabilities in the multinomial model are related to the distribution of
$(X,Z,Y)$ in the original conditional independence testing problem. Our next
proposition answers this question and relates the $\ell_{1}$ distance between
the nominal probabilities and the discrete uniform distribution, in the
multinomial problem, to the measure $\Delta_{T}(\mathcal{L}(X,Z,Y))$ given in
Definition 4.4.

######  Proposition 4.6.

Under Assumption 4.3, in Algorithm 1, each data point
$(X_{i},Z_{i},Y_{i})\sim\mathcal{L}(X,Y,Z)$ admits label
$s\in\\{1,2,...,L\\}$, independently from other data points with probability

${p}_{s}=\sum\limits_{j=(s-1)K}^{sK-1}\binom{M}{j}\int\limits_{0}^{1}u^{j}\big{(}1-u\big{)}^{M-j}r_{T}(u){\rm
d}u\,,$ (13)

where $\mathsf{r}_{T}(.)$ is the conditional relative density function given
by Definition 4.1. Under the null hypothesis (1), we have $p_{s}=\frac{1}{L}$.
In addition, under Assumption 4.2, the partial sums of
$\\{p_{s}\\}_{s=1}^{\ell}$ satisfies the following bounds:

  1. i)

For every $\ell\in[L]$, we have

$\sum\limits_{s=1}^{\ell}p_{s}\geq\mathsf{R}_{T}\left(\frac{\ell}{L}\right)\,,$
(14)

where $\mathsf{R}_{T}(u)$ is the conditional dominance curve given by
Definition 4.1.

  2. ii)

Let $D=C/2+2B$ with $B,C$ given according to Assumption 4.2 and introduce
$\nu_{K}:=2\left(\frac{4D^{2}\log{K}}{\sqrt{K}}\right)^{2/5}$. Then for $K$
sufficiently large such that $\nu_{K}<1$, we have

$\sum\limits_{s=1}^{\ell}p_{s}\leq\mathsf{R}_{T}\left(\frac{\ell}{L}\right)+\nu_{K}\,.$
(15)

  3. iii)

We have

$\sum\limits_{s=1}^{L}\Big{|}p_{s}-\frac{1}{L}\Big{|}\geq\left(\Delta_{T}(\mathcal{L}(X,Z,Y))-L\nu_{k}-\frac{C}{L}\right)\,.$
(16)

Proof of Proposition 4.6 is given in Section 9.7.

With Proposition 4.6 in place, we are now ready to state the main result about
the statistical power of our PCR test. We start by analyzing the power of the
PCR test when it is used with the finite-sample threshold
$\theta^{\mathsf{finite}}_{L,\alpha}$.

######  Theorem 4.7.

Let $U_{n,L}$ be the PCR test statistic– output of Algorithm 1, with the
number of labels $L$, and number of counterfeits per sample $M$, where
$M=KL-1$, and a score function $T$ that satisfies Assumptions 4.2 and 4.3 with
parameters $B,C$. Suppose that for some $\beta>0$, the conditional dependency
power $\Delta_{T}(\mathcal{L}(X,Z,Y))$ satisfies the following:

$\Delta_{T}(\mathcal{L}(X,Z,Y))\geq\frac{32{L}^{1/4}}{\sqrt{n}}\left(\frac{1}{\sqrt{\alpha}}\vee\frac{1}{\beta}\right)^{1/2}+\frac{C}{L}+L\nu_{K}\,,$
(17)

with $\nu_{K}=2\left(\frac{4(C/2+2B)^{2}\log{K}}{\sqrt{K}}\right)^{2/5}$, for
$K$ sufficiently large such that $\nu_{K}<1$. Then the PCR test, used with the
finite-sample threshold $\theta^{\mathsf{finite}}_{L,\alpha}$, achieves a
power of at least $1-\beta$. More precisely, for all distributions
$\mathcal{L}(X,Z,Y)$ satisfying (17), we have

${\mathbb{P}}\left(U_{n,L}\geq L+\sqrt{\frac{2L}{\alpha}}\right)\geq
1-\beta\quad\,.$

The proof of Theorem 4.7 follows from Proposition 4.6 and is given in Section
9.8.

We next analyze the PCR test power when it is employed with the asymptotic
threshold $\theta^{\mathsf{asym}}_{L,\alpha}$.

######  Theorem 4.8.

Let $U_{n,L}$ be the PCR test statistic– output of Algorithm 1, with the
number of labels $L$, and number of counterfeits per sample $M$, where
$M=KL-1$, and a score function $T$ that satisfies Assumptions 4.2 and 4.3 with
parameters $B,C$. In addition, suppose that the following lower bound holds
for the conditional dependency power $\Delta_{T}(\mathcal{L}(X,Z,Y)$:

$\Delta_{T}(\mathcal{L}(X,Z,Y))\geq\frac{L^{1/4}}{\sqrt{n}}\cdot\max\left(\sqrt{3\log\frac{1}{\beta}}+\left(3\log\frac{1}{\beta}+2\sqrt{\log\frac{1}{\alpha}}+2\log\frac{1}{\alpha}\right)^{1/2},~{}1\right)+\frac{C}{L}+L\nu_{K}\,,$
(18)

with $\nu_{K}=2\left(\frac{4(C/2+2B)^{2}\log{K}}{\sqrt{K}}\right)^{2/5}$, for
$K$ sufficiently large such that $\nu_{K}<1$. Then the PCR test deployed with
the asymptotic threshold $\theta_{L,\alpha}^{\mathsf{asym}}$ has asymptotic
statistical power at least $1-\beta$. Formally, for all distributions
$\mathcal{L}(X,Z,Y)$ satisfying (18), the following holds

$\lim\limits_{n\rightarrow\infty}{\mathbb{P}}\left(U_{n,\ell}\geq\chi^{2}_{L-1}(1-\alpha)\right)\geq
1-\beta\,.$

Proof of Theorem 4.8 also uses the results of Proposition 4.6 and is deferred
to Section 9.9.

The next result provides guidelines on the choice of the number of labels $L$,
as the number of samples $n$ grows to infinity.

######  Remark 4.9.

Note that the lower bounds (17) and (18) on $\Delta_{T}(\mathcal{L}(X,Z,Y))$
are minimized for $L\asymp n^{2/5}$. This suggests that optimal scaling for
the number of labels $L$ in the PCR test (with both the asymptotic threshold
and the finite-sample threshold) is $L\asymp n^{2/5}$ which achieves non-
trivial power when $\Delta(\mathcal{L}(X,Z,Y))\gtrsim n^{-2/5}$.

##  5 Parameter-free PCR test

The PCR test statistic described in Algorithm 1 takes the parameters $K$ and
$L$ as input. In general, having a large $K$ (for fixed value of $L$) results
in large value of $M$ (the number of counterfeits) and hence increases the
statistical power of the test because we can better discern the discrepancy
between the distribution of the ranks and the discrete uniform distribution.
This benefit of course comes at a higher computational cost for constructing
the test statistic. The choice of $L$ (total number of labels) is however more
subtle. On the one hand, a large value of $L$ implies that many of the labels
occur rarely, which makes it challenging to point out significant deviations
from the discrete uniform distribution (too many weak effects). On the other
hand, a small value of $L$ results in a few bins over which we are comparing
the test statistic with discrete uniform. In this case the test may miss sharp
deviations as they are aggregated by the relatively large number of other
points in the same bin. Similar observation can be made from the results of
Theorem 4.7 (and Theorem 4.8) where the right-hand side of (17) (and (18)) has
a term decreasing in $L$ and a term increasing in $L$. Therefore, the
parameter $L$ should be perceived as a tuning parameter in Algorithm 1.

As we showed in Theorem 3.2, any choice of $L$ results in a test with type I
error control; however different choices of $L$ gives different statistical
powers. A natural approach is to run the PCR test multiple times, each time
with a different value of $L$, and then ‘pick’ the one that results in the
smallest (most significant) $p$-value. However, this approach clearly violates
the validity of the reported $p$-value, as we should account for the ‘cherry-
picking’. Also, note that the obtained $p$-values (with different choices of
$L$) are dependent as they are constructed from a common data set. To properly
combine the $p$-values, we use the Bonferroni’s method. Algorithm 2 describes
this idea and presents a parameter-free version of Algorithm 1.

0: $n$ data points
$(X_{j},Y_{j},Z_{j})\in{\mathbb{R}}\times{\mathbb{R}}\times{\mathbb{R}}^{q}$,
significance level $\alpha\in(0,1)$, a real-valued score function
$T:{\mathbb{R}}\times{\mathbb{R}}\times{\mathbb{R}}^{q}\mapsto{\mathbb{R}}$,
$K\geq 1$ and a gird of $N$ values $\\{L_{1},...,L_{N}\\}$.

0: Decision on the conditional independence hypothesis (1).

for  _$i\in[N]$_ do

  * •

Run Algorithm 1 with $L=L_{i}$ labels to get test statistic $U_{n,L_{i}}$.

  * •

Construct $p$-value $P_{i}$ using (11) (for finite sample) or (12) (for
asymptotic case).

end for

  * •

Reject the null hypothesis if $P^{*}:=N\min\limits_{i\in[N]}P_{i}\leq\alpha$.

Algorithm 2 Parameter-free PCR test

The next theorem follows readily from Theorem 3.2 along with union bounding
for the Bonferroni’s correction.

######  Theorem 5.1.

Under the null hypothesis (1), the p-value $P^{*}$ constructed in Algorithm 2
is super-uniform, i.e ${\mathbb{P}}\left(P^{*}\leq t\right)\leq t$, for all
$t\in[0,1]$.

##  6 Robustness of the PCR test

In this section, we investigate the conditional independence problem when the
exact conditional distribution $P_{X|Z}$ is not available; rather we use
$\widehat{P}_{X|Z}(\cdot|Z)$ an estimate of $P_{X|Z}(\cdot|Z)$ for sampling
the counterfeits. We would like to modify the PCR test so it still controls
the type I error, when access to the exact conditional law $P_{X|Z}(\cdot|Z)$
is not feasible. To this end, the next theorem introduces a new test statistic
which is based on the discrepancy between conditional laws $P_{X|Z}(\cdot|Z)$
and $\widehat{P}_{X|Z}(\cdot|Z)$ along with the rejection thresholds for both
the asymptotic setting and the finite-sample setting. We use the expected
total variation metric to assess the distance between conditional laws.

######  Theorem 6.1.

Let $W_{s}$, for $s\in[\ell]$, be the number of data points with label $s$ as
defined in Algorithm 1. For $\delta$ such that
${\mathbb{E}}_{Z}\left[d_{\mathsf{TV}}\left(P_{X|Z}(.|Z),\widehat{P}_{X|Z}(.|Z)\right)\right]\leq\delta$,
introduce

$\begin{split}U_{n,L}(\delta):=\min_{\\{p_{s}\\}_{s\in[L]}}\quad&\frac{L}{n(1+L\delta)}\sum\limits_{s=1}^{L}{\left(W_{s}-np_{s}\right)^{2}}\\\
{\rm s.t.}\quad\quad&p_{s}\geq 0,\quad|p_{s}-1/{L}|\leq\delta,\quad\textrm{
for }s\in[L]\,,\\\ &{\rm and}\;\;\sum\limits_{s=1}^{L}p_{s}=1\,.\\\
\end{split}$ (19)

Recall the thresholds $\theta^{\mathsf{finite}}_{L,\alpha}$ and
$\theta^{\mathsf{asym}}_{L,\alpha}$ from (8). Under the null hypothesis, we
have the following relations:

$\displaystyle{\mathbb{P}}\left(U_{n,L}(\delta)\geq\theta^{\mathsf{finite}}_{L,\alpha}\right)\leq\alpha\,,$
(20)
$\displaystyle\lim\limits_{n\rightarrow\infty}{\mathbb{P}}\left(U_{n,L}(\delta)\geq\theta^{\mathsf{asym}}_{L,\alpha}\right)\leq\alpha\,.$
(21)

We refer to Section 9.10 for the proof of Theorem 6.1. Note that optimization
(19) is a quadratic programming and can be solved efficiently. Also, statistic
$U_{n,L}(\delta)$, given as the optimal value of this optimization, is a
decreasing function with respect to $\delta$ and when there is no mismatch
between the true and the approximate version ($\delta=0$), we recover the
primary statistic $U_{n,L}$ that was given by Algorithm 1.

As an immediate corollary of Theorem 6.1 we can construct valid $p$-value for
testing the conditional independence (i.e., super-uniform under the null
hypothesis (1)), following the same recipe given by (11-12), but using
$U_{n,L}(\delta)$ instead of $U_{n,L}$.

##  7 Discussion

In this work, we introduced the PCR test procedure to examine conditional
independence of two variables in the presence of a high-dimensional
confounding variable, in a model-$X$ setup where the distributional
information on the covariate population is available. The proposal of the PCR
test was inspired by some of the alternative distributions for which the CRT
(and its variants) are powerless. The PCR test is generally more flexible in
capturing the conditional dependency, and under some alternatives can result
in much higher statistical power compared to the CRT. We also provided a power
analysis of the PCR test in terms of the so-called conditional dependency
power of the joint law $\mathcal{L}(X,Z,Y)$, sample size $n$ and the number of
labels $L$ used in constructing the PCR test statistic.

We also proposed two extensions of the PCR test: $(i)$ _Parameter-free PCR
test_ , which consists of multiple runs of PCR test with different choices of
number of labels $L$, and then using Bonferroni’s method to combine the
obtained $p$-values. $(ii)$ _Robust PCR test_ , which improves the robustness
of the test against errors in estimating the conditional distribution
$P_{X|Z}$. Both of these extensions would have important practical
implications.

It is worth noting that many of the extensions made to improve the
computational complexity of CRT (e.g., hold-out randomization test (HRT)
[TVZ+18] or the distilled CRT [LKJR20]) can also be adapted and applied to our
proposed PCR test.

We next describe a generalization which unifies both the PCR test and the CRT.
Specifically, instead of running PCR at sample level, we first partition the
samples into $N$ smaller datasets of equal size. On each of these datasets, we
follow a similar approach to CRT in that we draw counterfeits and rank the
original dataset among its counterfeits using a score function. We then apply
the PCR test at the sub-datasets level, where we label each of these ‘sub-
datasets’ based on their ranks and use the test statistic in Algorithm 1 to
examine differences between ranks distribution and the discrete uniform.
Notably, when the sub-datasets are singletons this reduces to the PCR test,
while in the other extreme where there is no partitioning $(N=1)$, this
recovers the CRT. We will implement and discuss this generalization further in
the BikeShare example in Section 8.

##  8 Numerical Experiments

In this section, we evaluate the performance of PCR test and its extensions on
synthetic datasets.

Size of PCR test. We start by showing that the size of PCR test is controlled
at the desired level, under various choices of input parameters $L$ and $K$.
Assume $n=100$ data points $\\{(X_{i},Z_{i},Y_{i})\\}_{i=1}^{n}$ are generated
i.i.d. from the following model: First draw two vectors
$v,u\in{\mathbb{R}}^{p}$ with i.i.d standard normal entries and $p=20$. Then,

$\displaystyle Z$ $\displaystyle\sim\mathsf{N}(0,I_{p}),\quad\text{ for
}Z\in{\mathbb{R}}^{p}\,,$ $\displaystyle X|Z$
$\displaystyle\sim\mathsf{N}(v^{\sf T}Z,1),\quad\text{ for
}X\in{\mathbb{R}}\,,$ (22) $\displaystyle Y|X,Z$
$\displaystyle\sim\mathsf{N}\left((u^{\sf T}Z)^{2},1\right)\,.$

Clearly $X\perp\\!\\!\\!\perp Y|Z$ and the null hypothesis holds. We assume
that the dependency rule $X|Z$ and the vector $v$ are known, and therefore for
every given $Z$ we can easily sample from $\mathsf{N}(v^{\sf T}Z,1)$ to
construct the counterfeit variables. Tables 2 and 3 exhibit the performance of
the PCR test with thresholds $\theta^{\mathsf{finite}}_{\ell,\alpha}$ and
$\theta^{\mathsf{asym}}_{\ell,\alpha}$, respectively. As expected, the
$\theta^{\mathsf{finite}}_{\ell,\alpha}$ threshold is conservative and
controls the size at a level lower than $\alpha$. The
$\theta^{\mathsf{asym}}_{\ell,\alpha}$ threshold also controls the size,
albeit $n$ being only $100$.

| $\alpha=0.05$ | $\alpha=0.1$ | $\alpha=0.15$
---|---|---|---
$K$ $L$ | $2$ | $3$ | $5$ | $10$ | $2$ | $3$ | $5$ | $10$ | $2$ | $3$ | $5$ | $10$
$1$ | 0.0009 | 0.0012 | 0.0009 | 0.0006 | 0.0035 | 0.0042 | 0.0042 | 0.0049 | 0.0062 | 0.0094 | 0.0101 | 0.0109
$4$ | 0.0008 | 0.0006 | 0.0006 | 0.0002 | 0.0029 | 0.0035 | 0.0039 | 0.0047 | 0.0063 | 0.0090 | 0.0105 | 0.0110
$20$ | 0.0007 | 0.0010 | 0.0006 | 0.0004 | 0.0038 | 0.0045 | 0.0042 | 0.0036 | 0.0064 | 0.0082 | 0.0107 | 0.0088
$100$ | 0.0012 | 0.0007 | 0.0005 | 0.0004 | 0.0035 | 0.0032 | 0.0044 | 0.0043 | 0.0065 | 0.0087 | 0.0095 | 0.0107

Table 2: Size of PCR test applied on a dataset consisting of $n=100$ samples
generated from model (22), where $X\perp\\!\\!\\!\perp Y|Z$. Three
significance levels $\alpha=0.05,0.1,$ and $0.15$ are considered. Statistic
$U_{n,L}$ is obtained from Algorithm 1 by using the score function
$T(x,z,y)=(y-x-z^{\sf T}\mathbf{1})^{2}$, and the decision rule (7) is
employed with the threshold $\theta^{\mathsf{finite}}_{\ell,\alpha}$. Reported
numbers are averaged out over $10,000$ independent realizations.

| $\alpha=0.05$ | $\alpha=0.1$ | $\alpha=0.15$
---|---|---|---
$K$ $L$ | $2$ | $3$ | $5$ | $10$ | $2$ | $3$ | $5$ | $10$ | $2$ | $3$ | $5$ | $10$
$1$ | 0.0560 | 0.0510 | 0.0504 | 0.0493 | 0.0874 | 0.0930 | 0.1018 | 0.0968 | 0.1321 | 0.1515 | 0.1508 | 0.1457
$4$ | 0.0583 | 0.0545 | 0.0509 | 0.0527 | 0.0899 | 0.1000 | 0.0960 | 0.0992 | 0.1320 | 0.1583 | 0.1468 | 0.1492
$20$ | 0.0561 | 0.0488 | 0.0536 | 0.0457 | 0.0874 | 0.0923 | 0.0981 | 0.0933 | 0.1346 | 0.1516 | 0.1470 | 0.1455
$100$ | 0.0564 | 0.0504 | 0.0470 | 0.0521 | 0.0885 | 0.0936 | 0.0925 | 0.1004 | 0.1332 | 0.1543 | 0.1421 | 0.1491

Table 3: Size of PCR test applied on a dataset consisting of $n=100$ samples
generated from model (22), where $X\perp\\!\\!\\!\perp Y|Z$. Three
significance levels $\alpha=0.05,0.1,$ and $0.15$ are considered. Statistic
$U_{n,L}$ is obtained from Algorithm 1 by using the score function
$T(x,z,y)=(y-x-z^{\sf T}\mathbf{1})^{2}$, and the decision rule (7) is
employed with the threshold $\theta^{\mathsf{asym}}_{\ell,\alpha}$. Reported
numbers are averaged out over $10,000$ independent realizations.

Statistical Power of PCR test. Consider a setup similar to (22), but with
$n=1000$ data points and the conditional law

$Y|X,Z\sim\mathsf{N}\left((u^{\sf T}Z)^{2}+2X,1\right)\,,$ (23)

Our power analysis in section 4 suggests that larger values of $M=KL-1$ would
results in higher power. We fix $K=100$ and let $L$ vary in the set
$L=\\{2,3,\dotsc,30\\}$. The significance level is fixed at $\alpha=0.1$.
Figure 3 showcases the power of PCR test with both choices of rejection
thresholds $\theta^{\mathsf{finite}}_{\ell,\alpha}$ and
$\theta^{\mathsf{asym}}_{\ell,\alpha}$. As we see, when $n$ doubles not only
the power increases but also it becomes more stable with respect to the choice
of $L$.

(a) $n=1000$ data points

(b) $n=2000$ data points

Figure 3:  Power of PCR test for (left) $n=1000$ and (right) $n=2000$ data
points. Data points are generated under the setup (22) and the conditional law
(23). We consider the score function $(y-x-z^{\sf T}\mathbf{1})^{2}$ and
choose the significance level $\alpha=0.1$. We consider the decision rule (7)
with both of the rejection thresholds $\theta^{\mathsf{asym}}_{\ell,\alpha}$
and $\theta^{\mathsf{finite}}_{\ell,\alpha}$. Each reported power is obtained
by averaging over $1000$ trials.

Parameter-free PCR test. We consider a setup similar to the previous
experiment (23) and run the PCR test with different choices of
$L\in\\{2,4,8,16,32\\}$. We combine the obtained $p$-values using the
Bonferroni’s correction, as described in Algorithm 2. With $n=1000$ data
points, we get a statistical power of $0.192$ (with the finite-sample
threshold), and $0.815$ (with the asymptotic threshold). Note that in this
case, the power of the PCR test with different individual choices of $L$
(without combining the $p$-values) ranges in $(0.13-0.53)$, for the finite-
sample threshold, and in $(0.576-0.887)$, for the asymptotic-threshold.

For $n=2000$ data points, and with the Bonferroni’s correction, we get a power
of $0.613$, with the finite-sample threshold, and a power of $0.972$, with the
asymptotic threshold. Here, the power of the PCR test with individual choices
of $L$ ranges in $(0.477-0.83)$, for the finite-sample threshold, and in
$(0.8560-0.981)$, for the asymptotic threshold.

Robustness of the PCR test. In this part, we consider cases where the exact
dependency law $P_{X|Z}$ is not available, and we use an estimate of it
denoted by $\widehat{P}_{X|Z}$ (see Section 6 for the details and the
description of the robust PCR test). Consider a setup similar to (22), but
with $n=5000$ data points and the conditional law

$Y|X,Z\sim\mathsf{N}\left((u^{\sf T}Z)^{2}+aX,1\right)\,.$ (24)

When $a=0$, then the null hypothesis is true ($X\perp\\!\\!\\!\perp Y|Z$) and
the rejection rate amounts to the type I error. For $a\neq 0$, the null
hypothesis is false and the rejection rate amounts to the power of the test.

In the current experiment, we assume that the counterfeits are sampled from
$\widehat{P}_{X|Z}$ with

$\widehat{X}|Z\sim\mathsf{N}(v^{\sf T}Z,(1+\eta)^{2})\,.$ (25)

Note that when $\eta=0$, we get the true distribution $P_{X|Z}$ defined in
(22). We use the Pinsker’s
inequality222$d_{\mathsf{TV}}(P,Q)\leq\sqrt{\dfrac{1}{2}d_{\mathsf{KL}}(P,Q)}$to
bound the expected total variation distance
${\mathbb{E}}_{Z}\left[d_{\mathsf{TV}}\left(P_{X|Z}(\cdot|Z),\widehat{P}_{X|Z}(\cdot|Z)\right)\right]$.
Note that for two 1-dimensional Gaussian distributions we have

$d_{\mathsf{KL}}\left(\mathsf{N}(\mu,\sigma^{2}_{1}),\mathsf{N}(\mu,\sigma^{2}_{2})\right)=\log\frac{\sigma_{2}}{\sigma_{1}}+\frac{\sigma_{1}^{2}}{2\sigma_{2}^{2}}-\frac{1}{2}\,,$

which combined with Pinsker’s inequality implies that

${\mathbb{E}}_{Z}\left[d_{\mathsf{TV}}\left(P_{X|Z}(\cdot|Z),\widehat{P}_{X|Z}(\cdot|Z)\right)\right]\leq\delta:=\frac{1}{\sqrt{2}}\left(\log(1+\eta)+\frac{1}{2(1+\eta)^{2}}-\frac{1}{2}\right)^{1/2}.$
(26)

The results for $a=0$ and $a=4$ are summarized in Table 4. As we see the
robust PCR test controls the type I error under the level $\alpha=0.1$ for
different choices of $\eta$. In addition, it achieves a high power for $a=4$.

It is also worth noting that if we use the test statistics $U_{n,L}$ (instead
of $U_{n,L}(\delta)$) we observe an inflation in type I errors. Concretely,
when $\eta=0.04$ we obtain an inflated type I error of $0.595$ (with the
finite-sample threshold $\theta^{\mathsf{finite}}_{\ell,\alpha}$) and an
inflated type I error of $0.1860$ (with the asymptotic threshold
$\theta^{\mathsf{asym}}_{\ell,\alpha}$), while the target level is
$\alpha=0.1$. This highlights the importance of adjusting for the errors in
estimating the model-X conditional distribution, as proposed in Section 6.

| $a=0$ | $a=4$
---|---|---
setting $\eta$ | $0$ | $0.01$ | $0.02$ | $0.04$ | $0$ | $0.01$ | $0.02$ | $0.04$
$U_{n,L}(\delta)$ with $\theta^{\mathsf{finite}}_{L,\alpha}$ | 0.008 | 0 | 0 | 0 | 1 | 0.998 | 0.973 | 0.63
$U_{n,L}(\delta)$ with $\theta^{\mathsf{asym}}_{L,\alpha}$ | 0.1050 | 0.003 | 0 | 0 | 1 | 1 | 0.995 | 0.8790

Table 4: Size ($a=0$) and power ($a=4$) of the robust PCR test for the setting
of (24) and the approximate distribution (25) available for sampling the
counterfeits. We consider $a=0,4$ and $n=5000$ data points. The PCR test is
run with $L=4$ number of labels. For each value of the discrepancy level
$\eta$, we use (26) to get an upper bound $\delta$ on the expected total
variation distance
${\mathbb{E}}_{Z}\left[d_{\mathsf{TV}}\left(P_{X|Z}(\cdot|Z),\widehat{P}_{X|Z}(\cdot|Z)\right)\right]$,
and use it in constructing the robust statistic $U_{n,L}(\delta)$. Note that
$\eta=0$ implies $\delta=0$, and therefore the robust statistic
$U_{n,L}(\delta)$ matches the statistic $U_{n,L}$ in Algorithm (1). For $a=0$
(true null hypothesis), the size is controlled at the significance level
$\alpha=0.1$. Reported numbers are obtained by averaging over $1000$ trials.

###  8.1 Real data experiment: Capital Bikeshare dataset

In this section, we evaluate the performance of the PCR test on real data from
the Capital Bikeshare333The dataset is publicly available at
https://www.capitalbikeshare.com/system-data.. Capital Bikeshare is bike-
sharing system in Washington, D.C, and releases its trips data on a quarterly
basis. The data includes each trip taken, start date and time, end date and
time, start and end stations, Bike ID, and the user type indicating whether
the rider was a registered member or if it was a casual ride (one-time rental
or a short pass).

In this experiment, we use our proposed PCR test to study the independence of
the trip duration ($X$), and other variables, such as the user type ($Y$), and
provide $p-$values for their associations. A similar data and question has
been studied by [BWBS20] using the Conditional Permutation Test (CPT). As can
be imagined, the trip duration ($X$) heavily depends on the route (length of
the rout, elevation ,etc) and the time of the day at the start of the ride
(due to varying traffic and the rush hours). To control for the effect of such
variables, we condition on the start and end locations and the day hour
$Z=(Z_{\text{start loc}},Z_{\text{end loc}},Z_{\text{hour}})$.

In order to implement the PCR test, we use the conditional normal distribution
$X|Z\sim\mathsf{N}(\mu(Z),\sigma^{2}(Z))$ as an approximation of $P_{X|Z}$. We
follow the procedure of [BWBS20] to estimate the mean $\mu(z)$ and variance
$\sigma^{2}(z)$. We outline the procedure here for the reader’s convenience.
We consider a test data, consisting of the rides taken on weekdays in Oct
2011, and a training data consisting of the rides taken on weekdays in Sep
2011 and Nov 2011. The test data is used to for testing conditional
independence between factors of interest, and the training data is used to
estimate the conditional mean and variance ($\mu(z)$,$\sigma^{2}(z)$). To have
reliable estimation, we eliminate the records in the test data for which the
corresponding route in the training data has less than 20 rides. After this
preprocessing step, the test data includes $7,346$ samples. Finally, the
conditional functions $\mu(z)$ and $\sigma^{2}(z)$ are estimated using a
Gaussian kernel with a bandwidth of $20$ minute, on the training data. (See
[BWBS20, Appendix B]for further details on this part.)

We test the null hypothesis (1) with $X$ being the duration of the ride, and
three different response variables $Y$: (1) User type– registered members have
acquaintance with the routes and are likely to have lower trip durations, (2)
Date of the month (continuous variable from $1-30$)– this can be used to
capture effect of factors such as weather and sunlight hours. (3) Weekday
(categorical variable from Monday to Friday)– rides on the early days of the
week are likely to be more work-related. For score function to be used in the
PCR test, we consider the squared residual from regressing $Y$ on $X$. As an
example, when $Y$ is the user type, we encode it as a binary variable
$Y={\mathbb{I}}{\\{\text{the user is a registered member}\\}}$, and fit the
linear model $Y=b_{0}+b_{1}X$ to the training data to obtain the estimates
$\widehat{b}_{0},\widehat{b}_{1}$. Finally, for any test data point $(x,y)$,
we consider the score function
$T(x,y)=(y-\widehat{b}_{0}-\widehat{b}_{1}x)^{2}$.

In this experiment, we use the PCR test with $L=10$ number of labels and the
counterfeit ratio $K=200$, and therefore $M=1999$. Further, in order to reduce
the variation between the true distribution $P_{X|Z}$ distribution and its
estimate $\mathsf{N}(\widehat{\mu}(Z),\widehat{\sigma}^{2}(Z))$, we use the
generalization of the PCR framework as discussed at the end of Section 7.
Concretely, we partition the $n=7346$ test data samples into $N=\lfloor
n/4\rfloor$ smaller groups, each of size $4$, and label each group based on
the rank of its score, among the scores of its counterfeits, as proposed in
the PCR test. Formally, for test data vectors $X_{1:n}$, $Z_{1:n}$, we
construct counterfeits
${\widetilde{X}}_{1:n}^{(1)},{\widetilde{X}}_{1:n}^{(2)},...,{\widetilde{X}}_{1:n}^{(M)}$,
and score each sample and its counterfeits by:

$T=[(\widehat{b}_{0}+\widehat{b}_{1}X_{j}-Y_{j})^{2}]_{j=1:n}\,,\quad\widetilde{T}_{i}=[(\widehat{b}_{0}+\widehat{b}_{1}{\widetilde{X}}_{j}^{(i)}-Y_{j})^{2}]_{j=1:n}\,.$

We then partition the samples into $N=\lfloor n/4\rfloor$ groups of equal size
and score each group (and its counterfeits) by the average score of their four
members. Finally, we follow Algorithm (1) to label the groups and construct
the statistic $U_{N,\ell}$. We calculate the $p$-values for each of the
conditional independence tests, using (11). The results are summarized in
Table 5. As we see among the three response variables considered in this
experiment, user type has the most significant (conditional) dependence to
duration of the ride.

Response $Y$ |  $p$-value (finite) |  $p$-value (asym)
---|---|---
User type | $0.0014$ | 0
Date | $0.3855$ | 0.0456
Week day | 0.2094 | 0.0194
Table 5: $P$-values that are computed from the PCR test on the Capital
Bikeshare dataset. The null hypothesis (1) is considered with $X$ being the
duration of the ride, and the confounder variable $Z$ encoding the start and
end locations, as well as the time of day at the start of the ride. We
consider three different response values $Y$: (1) User type, (2) Date of the
month, (3) Weekday. The $p$-values are obtained as per (11) with the number of
labels $L=10$, and the counterfeit ratio $K=200$.

##  9 Proof of theorems and technical lemmas

###  9.1 Technical preliminaries

######  Lemma 9.1 ( Pearson’s $\chi^{2}-$test size and power).

Consider a multinomial model with $L$ labels $\\{1,2,...,L\\}$, and $n$ number
of samples. For $s\in[L]$, let $W_{s}$ denote the number of samples with label
$s$ and $p_{s}$ be the occurrence probability of label $s$ in one realization
of the multinomial model . Consider the following uniformity hypothesis, at
the significance level $\alpha\in(0,1)$:

$H_{0}:p_{s}=\frac{1}{L},\quad\text{for }1\leq s\leq L\,,$ (27)

with the following decision rule $\Psi_{n,L}$, which is based on the Pearson’s
Chi-squared statistic $U_{n,L}$:

$\Psi_{n,L}={\mathbb{I}}\left(U_{n,L}:=\frac{L}{n}\sum\limits_{s=1}^{L}\left(W_{s}-\frac{n}{L}\right)^{2}\geq
L+\sqrt{\frac{2L}{\alpha}}\right)\,.$

The following statements hold:

  1. 1.

Under the null hypothesis (27),
$U_{n,L}\overset{d}{\Rightarrow}\chi^{2}_{L-1}$, as $n\rightarrow\infty$.

  2. 2.

Under the null hypothesis (27), the size of this test is controlled at level
$\alpha$:

${\mathbb{P}}(\Psi_{n,L}=1)\leq\alpha\,.$

  3. 3.

If for some $\beta>0$, we have the following:

$\sum\limits_{s=1}^{L}\left|p_{s}-\frac{1}{L}\right|\geq\frac{32{L^{1/4}}}{\sqrt{n}}\left[\frac{1}{\sqrt{\alpha}}\vee\frac{1}{\beta}\right]^{1/2}\,,$

then the type II error does not exceed $\beta$:

${\mathbb{P}}(\Psi_{n,L}=0)\leq\beta\,.$

Regarding the proof of Lemma 9.1, note that the first part is a classic result
on the asymptotic null distribution of the Pearson’s Chi-squared test (See
e.g. [LR06], Theorem 14.3.1.) For the proof of parts 2 and 3, we refer to
[BW+19]. More specifically, [BW+19] proves similar claims for the ‘truncated’
$\chi^{2}$-test statistic and for more general hypotheses regarding the
nominal probabilities of the labels under multinomial models. For the special
case of the uniformity testing problem (27), the truncated Chi-squared
statistic reduces to the classic Pearson’s Chi-squared test statistic.

The next lemma is the Berry-Esseen theorem for non-identical independent
random variables and its statement is borrowed from [BC05, Section 5].

######  Lemma 9.2.

([BC05, Section 5]) For zero-mean independent random variables
$\xi_{1},...,\xi_{n}$ with $\sum\limits_{i=1}^{n}{\mathbb{E}}[\xi_{i}^{2}]=1$,
let $W=\sum\limits_{i=1}^{n}\xi_{i}$. If
$\sum\limits_{i=1}^{n}{\mathbb{E}}[|\xi_{i}^{3}|]\leq\gamma$, then we have

$\sup\limits_{-\infty\leq z\leq\infty}\left|{\mathbb{P}}\left(W\leq
z\right)-\Phi(z)\right|\leq\gamma\,.$

###  9.2 The intuition behind the example of Section 1.1

Consider the following regression setting for a measurable function $g$:

$Y=g(X)+{\varepsilon}\,,\quad{\varepsilon}\sim\mathsf{N}(0,1)\text{ and
}X\sim\mathsf{N}(0,1)\,.$

Assume that the data consists of $n$ samples
$(\mathbf{X},\mathbf{Y})=(X_{i},Y_{i})_{i=1}^{n}$. For $j\in[M]$, generate
counterfeits $\widetilde{\mathbf{X}}_{j}\sim\mathsf{N}({0},I_{n\times n})$,
and define
$U=\|\mathbf{Y}-\mathbf{X}\|_{2}^{2}/n,\widetilde{U}_{j}=\|\mathbf{Y}-\widetilde{\mathbf{X}}_{j}\|_{2}^{2}/n$.

From the Central limit theorem, we know that
$U\sim\mathsf{N}(\mu_{1},\sigma_{1}^{2}/n)$ and
$\widetilde{U}_{j}\sim\mathsf{N}(\mu_{2},\sigma_{2}^{2}/n)$, where

$\displaystyle\mu_{1}={\mathbb{E}}[(g(X)-X+{\varepsilon})^{2}],\quad\;\;\quad\;\mu_{2}={\mathbb{E}}[(g(X)-{\widetilde{X}}+{\varepsilon})^{2}]\,,$
$\displaystyle\sigma_{1}^{2}=\mathsf{Var}((g(X)-X+{\varepsilon})^{2}),\quad\;\;\;\sigma_{2}^{2}=\mathsf{Var}((g(X)-{\widetilde{X}}+{\varepsilon})^{2})\,.$

Roughly speaking, if

$\displaystyle\mu_{1}=\mu_{2}\quad\text{and }\quad\sigma_{1}<\sigma_{2}\,,$
(28)

then the counterfeits scores $\widetilde{U}_{j}$ will be distributed around
the original data score $U$, and therefore the distribution of the normalized
rank of the original data score gets an inflation in the central range. With
this intuition in mind, we seek properties of the function $g$ to fulfill the
conditions 28.

Note that, because $X,{\widetilde{X}}$ are exchangeable and independent, we
have

$\mu_{1}-\mu_{2}={\mathbb{E}}[Xg(X)]-{\mathbb{E}}[{\widetilde{X}}g(X)]={\mathbb{E}}[Xg(X)],$

since ${\mathbb{E}}[{\widetilde{X}}]=0$. For even functions $g$, $xg(x)$ is
odd and ${\mathbb{E}}[Xg(X)]=0$ by symmetry of the normal distribution. Hence,
$\mu_{1}=\mu_{2}$.

Next, we rewrite the variance terms:

$\displaystyle\sigma_{1}^{2}-\sigma_{2}^{2}$
$\displaystyle={\mathbb{E}}[(g(X)-X+{\varepsilon})^{4}]-{\mathbb{E}}[(g(X)-{\widetilde{X}}+{\varepsilon})^{4}]-\mu_{1}^{2}+\mu_{2}^{2}$
$\displaystyle={\mathbb{E}}[(g(X)-X+{\varepsilon})^{4}]-{\mathbb{E}}[(g(X)-{\widetilde{X}}+{\varepsilon})^{4}]$
$\displaystyle={\mathbb{E}}[(g(X)+{\varepsilon})^{4}]+{\mathbb{E}}[X^{4}]-4{\mathbb{E}}[X^{3}(g(X)+{\varepsilon})]-4{\mathbb{E}}[X(g(X)+{\varepsilon})^{3}]+6{\mathbb{E}}[X^{2}(g(X)+{\varepsilon})^{2}]$
$\displaystyle-{\mathbb{E}}[(g(X)+{\varepsilon})^{4}]-{\mathbb{E}}[{\widetilde{X}}^{4}]+4{\mathbb{E}}[{\widetilde{X}}^{3}(g(X)+{\varepsilon})]+4{\mathbb{E}}[{\widetilde{X}}(g(X)+{\varepsilon})^{3}]-6{\mathbb{E}}[{\widetilde{X}}^{2}(g(X)+{\varepsilon})^{2}]$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}6{\mathbb{E}}[X^{2}(g(X)+{\varepsilon})^{2}]-6{\mathbb{E}}[{\widetilde{X}}^{2}(g(X)+{\varepsilon})^{2}]$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}6{\mathbb{E}}[X^{2}g(X)^{2}]-6{\mathbb{E}}[g(X)^{2}]\,,$

where $(a)$ follows from the exchangeability of $X$, ${\widetilde{X}}$ in
conjunction with the fact that $x^{3}g(x)$ and $x(g(x)+{\varepsilon})^{3}$ are
odd functions. Step (b) follows from
${\mathbb{E}}[X^{2}]={\mathbb{E}}[\tilde{X}^{2}]=1$,
${\mathbb{E}}[{\varepsilon}]=0$ and the fact ${\varepsilon},X,{\widetilde{X}}$
are independent.

In summary, conditions (28) are satisfied if $g$ is an even function and
${\mathbb{E}}[X^{2}g(X)^{2}]<{\mathbb{E}}[g(X)^{2}]$, for
$X\sim\mathsf{N}(0,1)$. By choosing $g$ to be

$g(x)=\frac{1}{\sqrt{10^{-6}+x^{2}}}\,,$

we get ${\mathbb{E}}[g(X)^{2}]=6.110$, ${\mathbb{E}}[X^{2}g(X)^{2}]=0.798$,
and so it satisfies these conditions.

###  9.3 Proof of Proposition 2.1

Consider $M$ counterfeits
$\widetilde{\mathbf{X}}_{1},\widetilde{\mathbf{X}}_{2},...,\widetilde{\mathbf{X}}_{M}$
sampled independently from $\mathsf{N}(0,I_{n})$. For $j\in[M]$, let
$I_{j}={\mathbb{I}}_{\\{T(\mathbf{X},\mathbf{Y})\geq
T(\widetilde{\mathbf{X}}_{j},\mathbf{Y})\\}}$. Let
$T(\mathbf{X},\mathbf{Y})=\|\mathbf{X}-\mathbf{Y}\|_{2}^{2}/n$ and

$\mu_{n}={\mathbb{E}}\left[{\mathbb{I}}_{\\{T(\mathbf{X},\mathbf{Y})\geq
T(\widetilde{\mathbf{X}}_{1},\mathbf{Y})\\}}\right]\,,\quad\sigma_{n}^{2}={\rm
Var}\left[{\mathbb{I}}_{\\{T(\mathbf{X},\mathbf{Y})\geq
T(\widetilde{\mathbf{X}}_{1},\mathbf{Y})\\}}\right]\,.$

It is easy to see that $\sigma_{n}^{2}=\mu_{n}(1-\mu_{n})$. Before proceeding
further we establish a lemma which will be used in proving the result.

######  Lemma 9.3.

The followings hold:

$\displaystyle\lim_{n\to\infty}\mu_{n}=\lim\limits_{n\rightarrow\infty}{\mathbb{P}}(T(\widetilde{\mathbf{X}},\mathbf{Y})\leq
T(\mathbf{X},\mathbf{Y}))=1/2\,,$
$\displaystyle\lim\limits_{n\rightarrow\infty}{\mathbb{E}}\left[{\mathbb{P}}\left(\\{T(\mathbf{X},\mathbf{Y})\geq
T(\widetilde{\mathbf{X}},\mathbf{Y})\\}|\mathbf{X},\mathbf{Y}\right)^{2}\right]={\mathbb{E}}_{Z\sim\mathsf{N}(0,1)}[\Phi^{2}(\eta
Z)]\,,$

where $\eta=\frac{3+2{\mathbb{E}}[X^{2}g(X)^{2}]}{3+2{\mathbb{E}}[g(X)^{2}]}$.

By applying Chebyshev’s inequality we get

$\displaystyle{\mathbb{P}}\Big{(}\Big{|}\sum\limits_{j=1}^{M}\frac{I_{j}}{M}-1/2\Big{|}\geq\delta\Big{)}$
$\displaystyle\leq{\mathbb{P}}\Big{(}\Big{|}\sum\limits_{j=1}^{M}\frac{I_{j}}{M}-\mu_{n}\Big{|}\geq\delta-|\mu_{n}-1/2|\Big{)}$
$\displaystyle\leq\frac{1}{(\delta-|\mu_{n}-1/2|)^{2}}\cdot{\mathbb{E}}\Big{[}\Big{|}\sum\limits_{j=1}^{M}\frac{I_{j}}{M}-\mu_{n}\Big{|}^{2}\Big{]}\,,$
$\displaystyle=\frac{1}{(\delta-|\mu_{n}-1/2|)^{2}}\cdot{\mathbb{E}}\Big{[}\frac{1}{M^{2}}\sum\limits_{j=1}^{M}(I_{j}-\mu_{n})^{2}+\frac{1}{M^{2}}\sum_{i\neq
j}(I_{i}-\mu_{n})(I_{j}-\mu_{n}))\Big{]}$
$\displaystyle=\frac{1}{(\delta-|\mu_{n}-1/2|)^{2}}\cdot\left(\frac{\sigma_{n}^{2}}{M}+\frac{M-1}{M}{\mathbb{E}}[(I_{1}-\mu_{n})(I_{2}-\mu_{n})]\right)$
$\displaystyle=\frac{1}{(\delta-|\mu_{n}-1/2|)^{2}}\cdot\left(\frac{1}{M}\mu_{n}(1-\mu_{n})+\frac{M-1}{M}{\mathbb{E}}[I_{1}I_{2}-\mu_{n}^{2}]\right)\,.$
(29)

We next compute ${\mathbb{E}}[I_{1}I_{2}-\mu_{n}^{2}]$.

$\displaystyle{\mathbb{E}}[I_{1}I_{2}]$
$\displaystyle={\mathbb{P}}\left(\\{T(\mathbf{X},\mathbf{Y})\geq
T(\widetilde{\mathbf{X}}_{1},\mathbf{Y})\\}\cap\\{T(\mathbf{X},\mathbf{Y})\geq
T(\widetilde{\mathbf{X}}_{2},\mathbf{Y})\\}\right)$
$\displaystyle={\mathbb{E}}\left[{\mathbb{P}}\left(\\{T(\mathbf{X},\mathbf{Y})\geq
T(\widetilde{\mathbf{X}}_{1},\mathbf{Y})\\}\cap\\{T(\mathbf{X},\mathbf{Y})\geq
T(\widetilde{\mathbf{X}}_{2},\mathbf{Y})\\}|\mathbf{X},\mathbf{Y}\right)\right]$
$\displaystyle={\mathbb{E}}\left[{\mathbb{P}}\left(\\{T(\mathbf{X},\mathbf{Y})\geq
T(\widetilde{\mathbf{X}}_{1},\mathbf{Y})\\}|\mathbf{X},\mathbf{Y}\right){\mathbb{P}}\left(\\{T(\mathbf{X},\mathbf{Y})\geq
T(\widetilde{\mathbf{X}}_{2},\mathbf{Y})\\}|\mathbf{X},\mathbf{Y}\right)\right]$
$\displaystyle={\mathbb{E}}\left[{\mathbb{P}}\left(\\{T(\mathbf{X},\mathbf{Y})\geq
T(\widetilde{\mathbf{X}},\mathbf{Y})\\}|\mathbf{X},\mathbf{Y}\right)^{2}\right]\,,$

where we used the fact that conditioned on $\mathbf{X}$ and $\mathbf{Y}$,
score values
$T(\widetilde{\mathbf{X}}_{1},\mathbf{Y}),T(\widetilde{\mathbf{X}}_{2},\mathbf{Y})$
are independent. Therefore, by using Lemma 9.3, we write

$\displaystyle\lim\limits_{n\rightarrow\infty}{\mathbb{E}}[(I_{1}I_{2}-\mu_{n}^{2})]$
$\displaystyle=\lim\limits_{n\rightarrow\infty}{\mathbb{E}}\left[{\mathbb{P}}\left(\\{T(\mathbf{X},\mathbf{Y})\geq
T(\widetilde{\mathbf{X}},\mathbf{Y})\\}|\mathbf{X},\mathbf{Y}\right)^{2}\right]-\mu_{n}^{2}$
$\displaystyle=\lim\limits_{n\rightarrow\infty}{\mathbb{E}}\left[{\mathbb{P}}\left(\\{T(\mathbf{X},\mathbf{Y})\geq
T(\widetilde{\mathbf{X}},\mathbf{Y})\\}|\mathbf{X},\mathbf{Y}\right)^{2}\right]-1/4$
$\displaystyle={\mathbb{E}}_{Z\sim\mathsf{N}(0,1)}[\Phi^{2}(\eta Z)]-1/4\,.$
(30)

To summarize, we let
$S_{M}=\sum\limits_{j=1}^{M}{\mathbb{I}}_{\\{T(\mathbf{X},\mathbf{Y})\geq
T(\widetilde{\mathbf{X}}_{j},\mathbf{Y})\\}}$ and use (30) in (29) along with
$\lim_{n\to\infty}\mu_{n}=1/2$ per Lemma 9.3 to obtain

$\lim\limits_{n\rightarrow\infty}{\mathbb{P}}\left(\left|\frac{S_{M}}{M}-\frac{1}{2}\right|\geq\delta\right)\leq\frac{1}{4M\delta^{2}}+\frac{M-1}{M\delta^{2}}\cdot({\mathbb{E}}_{Z\sim\mathsf{N}(0,1)}[\Phi^{2}(\eta
Z)]-1/4)\,,\quad\forall\delta>0\,.$ (31)

Recalling the $p$ statistic (5), we have $p^{(M)}_{n}=\frac{1+S_{M}}{M+1}$. As
$S_{M}\leq M$, we have

$\frac{S_{M}}{M}\leq\frac{S_{M}+1}{M+1}\leq\frac{S_{M}}{M}+\frac{1}{M}\,,$

which implies that
$\left|p^{(M)}_{n}-\frac{1}{2}\right|\leq\left|\frac{S_{M}}{M}-\frac{1}{2}\right|+\frac{1}{M}$.
Using this relation along with triangle inequality in (31) to arrive at the
following:

$\displaystyle{\mathbb{P}}\Big{(}\Big{|}p^{(M)}_{n}-\frac{1}{2}\Big{|}\geq\delta\Big{)}$
$\displaystyle\leq{\mathbb{P}}\Big{(}\Big{|}\frac{S_{M}}{M}-\frac{1}{2}\Big{|}\geq\delta-\frac{1}{M}\Big{)}$
$\displaystyle\leq\frac{1}{\left({\varepsilon}-1/M\right)^{2}}\left(\frac{1}{4M}+\frac{M-1}{M}\cdot({\mathbb{E}}_{Z\sim\mathsf{N}(0,1)}[\Phi^{2}(\eta
Z)]-1/4)\right)\,.$

This completes the proof of Proposition 2.1.

####  9.3.1 Proof of Lemma 9.3

We start by establishing a lemma which characterizes the conditional
probability that the original data score exceeds a counterfeit score.

Define the shorthands

$\displaystyle
m_{n}(\mathbf{X},\mathbf{Y}):=\frac{\|\mathbf{Y}\|_{2}^{2}}{n}+1\,,\quad
v_{n}(\mathbf{X},\mathbf{Y}):=\frac{4\|\mathbf{Y}\|_{2}^{2}}{n^{2}}+\frac{2}{n}\,.$
(32)

######  Lemma 9.4.

For $m_{n}(\mathbf{X},\mathbf{Y})$ and $v_{n}(\mathbf{X},\mathbf{Y})$ given by
(32) we have

$\Big{|}{\mathbb{P}}(T(\widetilde{\mathbf{X}},\mathbf{Y})\leq
T(\mathbf{X},\mathbf{Y})|\mathbf{X},\mathbf{Y})-\Phi\Big{(}\frac{T(\mathbf{X},\mathbf{Y})-m_{n}(\mathbf{X},\mathbf{Y})}{v_{n}(\mathbf{X},\mathbf{Y})^{1/2}}\Big{)}\Big{|}\leq\gamma_{n}(\mathbf{X},\mathbf{Y})$
(33)

with

$\gamma_{n}(\mathbf{X},\mathbf{Y}):=\frac{1}{n^{2}v_{n}(\mathbf{X},\mathbf{Y})^{1.5}}\left(C_{0}+\sum\limits_{i=1}^{n}\frac{C_{1}|Y_{i}|+C_{2}|Y_{i}|^{2}+C_{3}|Y_{i}|^{3}}{n}\right)\,,$

where $C_{i}$s are absolute constants.

We next show that ${\mathbb{E}}[\gamma_{n}(\mathbf{X},\mathbf{Y})]\to 0$ as
$n\to\infty$.

$\displaystyle{\mathbb{E}}\left[\gamma_{n}(\mathbf{X},\mathbf{Y})\right]$
$\displaystyle={\mathbb{E}}\left[\frac{1}{\sqrt{n}\left(2+4||\mathbf{Y}||_{2}^{2}/n\right)^{1.5}}\left(C_{0}+\sum\limits_{i=1}^{n}\frac{C_{1}|Y_{i}|+C_{2}|Y_{i}|^{2}+C_{3}|Y_{i}|^{3}}{n}\right)\right]\,,$
$\displaystyle\leq\frac{1}{2^{3/2}\sqrt{n}}{\mathbb{E}}\left[\left(C_{0}+\sum\limits_{i=1}^{n}\frac{C_{1}|Y_{i}|+C_{2}|Y_{i}|^{2}+C_{3}|Y_{i}|^{3}}{n}\right)\right]$
$\displaystyle=\frac{1}{2^{3/2}\sqrt{n}}\left(C_{0}+C_{1}{\mathbb{E}}[|Xg(X)+{\varepsilon}|]+C_{2}{\mathbb{E}}[|Xg(X)+{\varepsilon}|^{2}]+C_{3}{\mathbb{E}}[|Xg(X)+{\varepsilon}|^{3}]\right)\,,$

which brings us to

$\displaystyle\lim\limits_{n\rightarrow\infty}{\mathbb{E}}\left[\gamma_{n}(\mathbf{X},\mathbf{Y})\right]=0.$
(34)

In the next lemma, we characterize the distribution of the other quantity in
(33).

######  Lemma 9.5.

For $m_{n}(\mathbf{X},\mathbf{Y})$ and $v_{n}(\mathbf{X},\mathbf{Y})$ given by
(32) we have

$\frac{T(\mathbf{X},\mathbf{Y})-m_{n}(\mathbf{X},\mathbf{Y})}{v_{n}(\mathbf{X},\mathbf{Y})^{1/2}}\overset{d}{\Rightarrow}\mathsf{N}(0,\eta^{2}),\quad\text{as
}n\rightarrow\infty\,.$

with
$\eta=\left(\frac{3+2{\mathbb{E}}[X^{2}g(X)^{2}]}{3+2{\mathbb{E}}[g(X)^{2}]}\right)^{1/2}$.

Using the result of Lemma 9.5 and by an application of the Portmanteau theorem
for the bounded continuous function $\Phi$ we get

$\lim\limits_{n\rightarrow\infty}{\mathbb{E}}\left[\Phi\left(\frac{T(\mathbf{X},\mathbf{Y})-m_{n}(\mathbf{X},\mathbf{Y})}{v_{n}(\mathbf{X},\mathbf{Y})^{1/2}}\right)\right]={\mathbb{E}}_{Z\sim\mathsf{N}(0,1)}[\Phi(\eta
Z)]\,.$ (35)

Combining (34) and (35) with (33) we arrive at

$\lim_{n\to\infty}{\mathbb{P}}(T(\widetilde{\mathbf{X}},\mathbf{Y})\leq
T(\mathbf{X},\mathbf{Y}))={\mathbb{E}}_{Z\sim\mathsf{N}(0,1)}\left[\Phi\left(\eta
Z\right)\right]\,.$

In the next lemma we show that
${\mathbb{E}}_{Z\sim\mathsf{N}(0,1)}\left[\Phi\left(\eta Z\right)\right]=1/2$,
which completes the proof of the first part.

######  Lemma 9.6.

Let $\Phi(\cdot)$ denote the distribution of standard normal variable. Then,
for any constant $\eta$ we have

${\mathbb{E}}_{Z\sim\mathsf{N}(0,1)}\left[\Phi\left(\eta Z\right)\right]=1/2.$

The second part of the lemma follows by a similar argument. We have

$\displaystyle{\mathbb{E}}\left[\gamma_{n}^{2}(\mathbf{X},\mathbf{Y})\right]$
$\displaystyle\leq\frac{1}{8n}{\mathbb{E}}\left[\left(C_{0}+\sum\limits_{i=1}^{n}\frac{C_{1}|Y_{i}|+C_{2}|Y_{i}|^{2}+C_{3}|Y_{i}|^{3}}{n}\right)^{2}\right]$
$\displaystyle\leq\frac{1}{4n}{\mathbb{E}}\left[C_{0}^{2}+\left(\sum\limits_{i=1}^{n}\frac{C_{1}|Y_{i}|+C_{2}|Y_{i}|^{2}+C_{3}|Y_{i}|^{3}}{n}\right)^{2}\right]$
$\displaystyle\leq\frac{1}{4n}\left(C_{0}^{2}+\frac{3}{n}{\mathbb{E}}\Big{[}\sum_{i=1}^{n}C_{1}^{2}|Y_{i}|^{2}+C_{2}^{2}|Y_{i}|^{4}+C_{3}^{2}|Y_{i}|^{6}\Big{]}\right)$
$\displaystyle=\frac{1}{4n}\left(C_{0}^{2}+3C_{1}^{2}{\mathbb{E}}[|Xg(X)+{\varepsilon}|^{2}]+3C_{2}^{2}{\mathbb{E}}[|Xg(X)+{\varepsilon}|^{4}]+3C_{3}^{2}{\mathbb{E}}[|Xg(X)+{\varepsilon}|^{6}]\right)\,,$

which implies that
$\lim\limits_{n\rightarrow\infty}{\mathbb{E}}\left[\gamma_{n}^{2}(\mathbf{X},\mathbf{Y})\right]=0$.

Also, by using Lemma 9.5 and an application of the Portmanteau theorem for the
bounded continuous function $\Phi^{2}$ we obtain

$\lim\limits_{n\rightarrow\infty}{\mathbb{E}}\left[\Phi^{2}\left(\frac{T(\mathbf{X},\mathbf{Y})-m_{n}(\mathbf{X},\mathbf{Y})}{v_{n}(\mathbf{X},\mathbf{Y})^{1/2}}\right)\right]={\mathbb{E}}_{Z\sim\mathsf{N}(0,1)}[\Phi^{2}(\eta
Z)]\,,$

which by invoking Lemma 9.4 completes the proof of Lemma 9.3 second part.

####  9.3.2 Proof of Lemma 9.4

We focus on the distribution of
$T(\widetilde{\mathbf{X}},\mathbf{Y})|\mathbf{X},\mathbf{Y}$ and treat
$\mathbf{X},\mathbf{Y}$ as deterministic values, so the only source of
randomness is $\widetilde{\mathbf{X}}$. To lighten the notation, we write

$v_{n}:=v_{n}(\mathbf{X},\mathbf{Y})=\frac{2}{n}+\frac{4\|\mathbf{Y}\|_{2}^{2}}{n^{2}}\,,$

and introduce

$\xi_{i}=\frac{(Y_{i}-{\widetilde{X}}_{i})^{2}-(Y_{i}^{2}+1)}{nv_{n}^{1/2}}\,,\quad\text{for
}i\in[n]\,.$

By simple algebraic computations, we get that
${\mathbb{E}}[\xi_{i}|\mathbf{X},\mathbf{Y}]=0$ and
$\sum\limits_{i=1}^{n}{\mathbb{E}}[\xi^{2}|\mathbf{X},\mathbf{Y}]=1$. Also,
conditioned on $\mathbf{X},\mathbf{Y}$, random variables $\xi_{i}$ are
independent. We next use the Berry-Essen theorem to characterize the
distribution of $\sum_{i=1}^{n}\xi_{i}$. For the reader’s convenience, the
version of the Berry-Esseen theorem for non-identical random variables is
provided in Lemma 9.2. First, we need to bound the sum of third moments:

$\displaystyle\sum\limits_{i=1}^{n}{\mathbb{E}}[|\xi_{i}^{3}|]$
$\displaystyle=\frac{1}{n^{3}v_{n}^{3/2}}\sum\limits_{i=1}^{n}{\mathbb{E}}\left[\left|(Y_{i}-{\widetilde{X}}_{i})^{2}-(Y_{i}^{2}+1)\right|^{3}\right]$
$\displaystyle=\frac{1}{n^{3}v_{n}^{3/2}}\sum\limits_{i=1}^{n}{\mathbb{E}}\left[\left|{\widetilde{X}}_{i}^{2}-2{\widetilde{X}}_{i}Y_{i}-1\right|^{3}\right]$
$\displaystyle\overset{(a)}{\leq}\frac{1}{n^{3}v_{n}^{3/2}}\sum\limits_{i=1}^{n}(C_{0}+C_{1}|Y_{i}|+C_{2}|Y_{i}|^{2}+C_{3}|Y_{i}|^{3})$
$\displaystyle=\frac{1}{n^{2}v_{n}^{3/2}}\left(C_{0}+\sum\limits_{i=1}^{n}\frac{C_{1}|Y_{i}|+C_{2}|Y_{i}|^{2}+C_{3}|Y_{i}|^{3}}{n}\right)\,,$

where in (a), for $i=0,1,2,3$, coefficients $C_{i}$ are universal constants
that can be precisely computed by using moments of the half-normal
distribution. Note that here the expectation is with respect to
${\widetilde{X}}_{i}$.

Now, we employ the Berry–Esseen theorem 9.2 to get:

$\displaystyle\sup\limits_{z}\left|{\mathbb{P}}(\sum\limits_{i=1}^{n}\xi_{i}\leq
z|\mathbf{X},\mathbf{Y})-\Phi\left(z\right)\right|\leq\gamma_{n}(\mathbf{X},\mathbf{Y})\,.$
(36)

From the definition of $\xi_{i}$ and recalling the definition of score
$T(\widetilde{\mathbf{X}},\mathbf{Y})$ we have

$\displaystyle T(\widetilde{\mathbf{X}},\mathbf{Y})$
$\displaystyle=\frac{1}{n}\|\widetilde{\mathbf{X}}-\mathbf{Y}\|_{2}^{2}=\frac{\|\widetilde{\mathbf{X}}\|_{2}^{2}}{n}+\frac{\|\mathbf{Y}\|_{2}^{2}}{n}-\frac{2\mathbf{X}^{\sf
T}\mathbf{Y}}{n}$
$\displaystyle=1+\frac{\|\mathbf{Y}\|_{2}^{2}}{n}+\frac{\|\widetilde{\mathbf{X}}\|_{2}^{2}}{n}-\frac{2\mathbf{X}^{\sf
T}\mathbf{Y}}{n}-1$
$\displaystyle=m_{n}(\mathbf{X},\mathbf{Y})+v_{n}(\mathbf{X},\mathbf{Y})^{1/2}\sum_{i=1}^{n}\xi_{i}\,.$

Using the above relation and choosing
$z=\tfrac{T(\mathbf{X},\mathbf{Y})-m_{n}(\mathbf{X},\mathbf{Y})}{v_{n}(\mathbf{X},\mathbf{Y})^{1/2}}$
in equation(36) (note that $z$ is a measurable function of
$\mathbf{X},\mathbf{Y}$), we get

$\displaystyle\Big{|}{\mathbb{P}}({T(\widetilde{\mathbf{X}},\mathbf{Y})\leq
T(\mathbf{X},\mathbf{Y})}|\mathbf{X},\mathbf{Y})-\Phi\left(\frac{T(\mathbf{X},\mathbf{Y})-m_{n}(\mathbf{X},\mathbf{Y})}{v_{n}(\mathbf{X},\mathbf{Y})^{1/2}}\right)\Big{|}\leq\gamma_{n}(\mathbf{X},\mathbf{Y})\,.$

####  9.3.3 Proof of Lemma 9.5

Substituting for $T(\mathbf{X},\mathbf{Y})$, $m_{n}(\mathbf{X},\mathbf{Y})$
and $v_{n}(\mathbf{X},\mathbf{Y})$ we get

$\displaystyle\frac{T(\mathbf{X},\mathbf{Y})-m_{n}(\mathbf{X},\mathbf{Y})}{v_{n}(\mathbf{X},\mathbf{Y})^{1/2}}$
$\displaystyle=\frac{\|\mathbf{X}-\mathbf{Y}\|_{2}^{2}/n-{\|\mathbf{Y}\|_{2}^{2}}/{n}-1}{\left({4\|\mathbf{Y}\|_{2}^{2}}/{n^{2}}+{2}/{n}\right)^{1/2}}$
$\displaystyle=\frac{\sqrt{n}\left(\|\mathbf{X}\|_{2}^{2}/n-2\mathbf{Y}^{T}\mathbf{X}/n-1\right)}{\left(2+4\|\mathbf{Y}\|_{2}^{2}/n\right)^{1/2}}\,,$
(37)

By an application of the central limit theorem, the numerator converges in
distribution to a normal random variable. More precisely,

$\displaystyle{\mathbb{E}}[X^{2}-2YX-1]$ $\displaystyle=-2{\mathbb{E}}[XY]$
$\displaystyle=-2{\mathbb{E}}[Xg(X)]-2{\mathbb{E}}[X{\varepsilon}]=0\,,$

where in the last relation we used the property that $g$ is an even function
and $X\sim\mathsf{N}(0,1)$. In addition, ${\rm
Var}[(X^{2}-2YX-1)]=6+4{\mathbb{E}}[X^{2}g(X)^{2}]$ by simple calculation.
Therefore, by CLT we have

$\sqrt{n}\left(||\mathbf{X}-\mathbf{Y}||_{2}^{2}/n-{||\mathbf{Y}||_{2}^{2}}/{n}+1\right)\overset{d}{\Rightarrow}\mathsf{N}(0,6+4{\mathbb{E}}[X^{2}g(X)^{2}])$
(38)

On the other hand, from the weak law of large numbers we have that the
denominator in (37) converges in probability to $6+4{\mathbb{E}}[g(X)^{2}]$.
The proof is completed by using the Slutsky’s theorem.

####  9.3.4 Proof of Lemma 9.6

Let $\Phi(\cdot)$ and $\phi(\cdot)$ respectively denote the distribution and
the density function of the standard normal random variable. We write

$\displaystyle\frac{\partial}{\partial\eta}{\mathbb{E}}[\Phi(\eta
Z)]={\mathbb{E}}[Z\phi(\eta
Z)]\stackrel{{\scriptstyle(a)}}{{=}}{\mathbb{E}}[\eta\phi^{\prime}(\eta
Z)]\stackrel{{\scriptstyle(b)}}{{=}}{\mathbb{E}}[-\eta^{2}Z\phi(\eta
Z)]=-\eta^{2}\frac{\partial}{\partial\eta}{\mathbb{E}}[\Phi(\eta Z)]\,,$ (39)

where we used Stein’s lemma in step $(a)$, and the identity
$\phi^{\prime}(t)=-t\phi(t)$ in step (b). Therefore,
$\frac{\partial}{\partial\eta}{\mathbb{E}}[\Phi(\eta Z)]=0$ and so
${\mathbb{E}}[\Phi(\eta Z)]={\mathbb{E}}[\Phi(0)]=1/2$.

###  9.4 Proof of Theorem 2.2

From Proposition 2.1 we know that

$\lim\limits_{M\rightarrow\infty}\lim\limits_{n\rightarrow\infty}{\mathbb{P}}\left(\left|p^{(M)}_{n}-1/2\right|\geq\delta\right)\leq\frac{1}{\delta^{2}}\left({\mathbb{E}}_{Z\sim\mathsf{N}(0,1)}[\Phi^{2}(\eta
Z)]-1/4)\right)\,.$ (40)

In order to find the probability of divergence from $1/2$, we need to upper
bound the right-hand-side of the above expression. Obviously, it is zero at
$\eta=0$ and we will show that for small enough $\eta$ we get good
concentration around $1/2$. To this end, note that for the function
$g(x)=1/\sqrt{\theta^{2}+x^{2}}$ the following holds

${\mathbb{E}}[X^{2}g(X)^{2}]={\mathbb{E}}\left[\frac{X^{2}}{\theta^{2}+X^{2}}\right]\leq
1\,.$ (41)

On the other hand, we have:

$\displaystyle{\mathbb{E}}[g(X)^{2}]$
$\displaystyle=\frac{1}{\sqrt{2\pi}}\int\limits_{-\infty}^{\infty}\frac{e^{-x^{2}/2}}{\theta^{2}+x^{2}}dx$
$\displaystyle\overset{(a)}{\geq}\frac{1}{\sqrt{2\pi}}\int\limits_{-\sqrt{2}}^{\sqrt{2}}\frac{1-x^{2}/2}{\theta^{2}+x^{2}}dx$
$\displaystyle\geq\frac{1}{\sqrt{2\pi}}\int\limits_{-\sqrt{2}}^{\sqrt{2}}\frac{dx}{\theta^{2}+x^{2}}-{\frac{1}{\sqrt{\pi}}}$
$\displaystyle=\frac{2}{\theta\sqrt{2\pi}}\arctan\frac{\sqrt{2}}{\theta}-{\frac{1}{\sqrt{\pi}}}$
$\displaystyle\overset{(b)}{\geq}\frac{2}{\theta\sqrt{2\pi}}\left(\frac{\pi}{2}-\frac{\theta}{\sqrt{2}}\right)-{\frac{1}{\sqrt{\pi}}}$
$\displaystyle\geq\frac{1}{\theta}\sqrt{\frac{\pi}{2}}-\frac{2}{\sqrt{\pi}}\,,$
(42)

where in (a) we used the $e^{x}\geq 1+x$ inequality, and in (b) we used the
$\arctan(x)\geq\pi/2-1/x$ inequality. Next, use (41) and (42) to get

$\eta^{2}=\frac{3+2{\mathbb{E}}[X^{2}g(X)^{2}]}{3+2{\mathbb{E}}[g(X)^{2}]}\leq\frac{5\sqrt{\pi}}{3\sqrt{\pi}-{4}+{\sqrt{2}\pi}/{\theta}}<\frac{5\theta}{\sqrt{2\pi}}\,,$
(43)

which implies that by choosing $\theta$ small enough, we can make $\eta$
arbitrarily small.

We next show that the deviation of the $p$-statistic from $1/2$ can be
controlled by the choice of $\eta$.

Note that for the normal distribution function $\Phi$ and the normal density
$\phi$ we have

$0\leq\Phi(\eta z)=\Phi(0)+\int_{0}^{\eta z}\phi(t){\rm
d}t\leq\frac{1}{2}+\frac{\eta|z|}{\sqrt{2\pi}}\,.$

Consequently for $Z\sim\mathsf{N}(0,1)$,

${\mathbb{E}}\left[\Phi^{2}(\eta
Z)\right]\leq{\mathbb{E}}\Big{[}\Big{(}\frac{1}{2}+\frac{\eta|Z|}{\sqrt{2\pi}}\Big{)}^{2}\Big{]}=\frac{1}{4}+\frac{\eta^{2}}{2\pi}+\frac{\eta}{\pi}\,.$

Therefore,

${\mathbb{E}}\left[\Phi^{2}(\eta
Z)\right]-\frac{1}{4}\leq\frac{\eta^{2}+2\eta}{2\pi}\,,$

which along with (40) imply

$\lim\limits_{M\rightarrow\infty}\lim\limits_{n\rightarrow\infty}{\mathbb{P}}\Big{(}\Big{|}p_{n}^{(M)}-\frac{1}{2}\Big{|}\geq\delta\Big{)}\leq\frac{\eta^{2}+2\eta}{2\pi\delta^{2}}\,.$

Next be choosing $\delta=(1-\alpha)/2$ and using (43), we obtain that for
$\theta<\alpha^{2}/500$ and $\alpha\leq 1/2$,

$\lim\limits_{M\rightarrow\infty}\lim\limits_{n\rightarrow\infty}{\mathbb{P}}\Big{(}\Big{|}p_{n}^{(M)}-\frac{1}{2}\Big{|}\geq\frac{1-\alpha}{2}\Big{)}\leq\frac{\alpha}{2}\,,$

This completes the proof of part (a) for two-sided CRT.

Proof of part (b) follows along the same lines. The only modification is that
time we set $\delta=1/2-\alpha$. Invoking (43) with assumptions $\alpha\leq
1/2-\gamma$ and $\theta\leq\gamma^{4}\alpha^{2}/2$, we get

$\displaystyle\lim\limits_{M\rightarrow\infty}\lim\limits_{n\rightarrow\infty}{\mathbb{P}}\left(p_{n}^{(M)}\geq
1-\alpha\right)\leq\frac{\alpha}{2}\,,\quad\lim\limits_{M\rightarrow\infty}\lim\limits_{n\rightarrow\infty}{\mathbb{P}}\left(p_{n}^{(M)}\leq\alpha\right)\leq\frac{\alpha}{2}\,.$

This completes the proof of part (b) for one-sided CRT.

###  9.5 Proof of Theorem 3.2

Because of Assumption 3.1 (continuity of probability laws), with probability
one all the score values are distinct and so there is no ambiguity (tie) in
labeling the data points. Recall $W_{\ell}$ as the number of data points with
label $\ell$. By construction, the joint distribution of
$(nW_{1},nW_{2},...,nW_{L})$ is a multinomial distribution with $L$ distinct
values (number of labels). Denote by $p_{\ell}$ the probability of getting
label $\ell$. Then, the statistic $U_{n,L}$, given by (6), is the standard
Pearson’s $\chi^{2}$ test statistic for testing the null hypothesis

$H^{\prime}_{0}:p_{\ell}=\frac{1}{L},\text{ for }\ell\in[L]\,.$ (44)

Now by using Lemma 9.1 (Part 1), we get
$U_{n,L}\overset{d}{\Rightarrow}\chi^{2}_{L-1}$, as $n\to\infty$. The claim
about $\theta_{L,\alpha}^{\mathsf{finite}}$ follows from Part 2 of Lemma 9.1.

###  9.6 Proof of Remark 4.5

Define

$g(u,z,y):=\frac{\partial}{\partial
u}F_{T|ZY}\Big{(}F_{T|Z}^{-1}\big{(}u;Z,Y\big{)};Z,Y\Big{)}\,.$

Then by Assumption 4.3 we have
$\int_{0}^{1}{\mathbb{E}}_{(Z,Y)\sim\mathcal{L}(Z,Y)}[|g(u,Z,Y)|]<\infty$ and
as an application of the Fubini’s theorem, we can change the order of
integration and the expectation and get:

$\displaystyle\int_{0}^{u}{\mathbb{E}}_{(Z,Y)\sim\mathcal{L}(Z,Y)}[g(v,Z,Y)]{\rm
d}v$
$\displaystyle={\mathbb{E}}_{(Z,Y)\sim\mathcal{L}(Z,Y)}\Big{[}\int_{0}^{u}g(v,Z,Y){\rm
d}v\Big{]}$
$\displaystyle={\mathbb{E}}_{(Z,Y)\sim\mathcal{L}(Z,Y)}\Big{[}F_{T|ZY}\Big{(}F_{T|Z}^{-1}\big{(}u;Z,Y\big{)};Z,Y\Big{)}-F_{T|ZY}\Big{(}F_{T|Z}^{-1}\big{(}0;Z,Y\big{)};Z,Y\Big{)}\Big{]}$
$\displaystyle={\mathbb{E}}_{(Z,Y)\sim\mathcal{L}(Z,Y)}\Big{[}F_{T|ZY}\Big{(}F_{T|Z}^{-1}\big{(}u;Z,Y\big{)};Z,Y\Big{)}$

Now taking derivative of both sides with respect to $u$, we arrive at

$\displaystyle{\mathbb{E}}_{(Z,Y)\sim\mathcal{L}(Z,Y)}[g(v,Z,Y)]=\mathsf{r}_{T}(u)\,.$
(45)

We next prove part (b) of the remark. Part(a) follows readily from part (a)
since under the null hypothesis $T(X,Z,Y)$ and $T({\widetilde{X}},Z,Y)$ have
the same distribution.

By definition of the conditional dependency power
$\Delta_{T}(\mathcal{L}(X,Z,Y))$, cf. Definition 4.4 we have

$\displaystyle\Delta_{T}(P_{X,Z,Y})$
$\displaystyle=\int_{0}^{1}|\mathsf{r}_{T}(u)-1|{\rm d}u$
$\displaystyle\overset{(a)}{=}\int\limits_{0}^{1}\left|{\mathbb{E}}_{(Z,Y)\sim\mathcal{L}(Z,Y)}\left[\frac{\partial}{\partial
u}F_{T|ZY}\left(F_{T|Z}^{-1}\big{(}u;Z,Y\big{)};Z,Y\right)\right]-1\right|{\rm
d}u$
$\displaystyle\overset{(b)}{\leq}\int\limits_{0}^{1}{\mathbb{E}}_{(Z,Y)\sim\mathcal{L}(Z,Y)}\left[\left|\frac{\partial}{\partial
u}F_{T|ZY}\left(F_{T|Z}^{-1}\big{(}u;Z,Y\big{)};Z,Y\right)-1\right|\right]{\rm
d}u$
$\displaystyle\overset{(c)}{=}{\mathbb{E}}_{(Z,Y)\sim\mathcal{L}(Z,Y)}\left[\int\limits_{0}^{1}\left|\frac{\partial}{\partial
u}F_{T|ZY}\left(F_{T|Z}^{-1}\big{(}u;Z,Y\big{)};Z,Y\right)-1\right|\right]{\rm
d}u$
$\displaystyle={\mathbb{E}}_{(Z,Y)\sim\mathcal{L}(Z,Y)}\left[\int\limits_{0}^{1}\left|\frac{f_{T|ZY}\left(F_{T|Z}^{-1}\big{(}u;Z,Y\big{)};Z,Y\right)}{f_{T|Z}\left(F_{T|Z}^{-1}\big{(}u;Z,Y\big{)};Z,Y\right)}-1\right|\right]{\rm
d}u$
$\displaystyle={\mathbb{E}}_{(Z,Y)\sim\mathcal{L}(Z,Y)}\left[\int\limits_{-\infty}^{\infty}\left|\frac{f_{T|Z,Y}\left(t;Z,Y\right)}{f_{T|Z}(t;Z,Y)}-1\right|f_{T|Z}(t;Z,Y){\rm
d}t\right]$
$\displaystyle={\mathbb{E}}_{(Z,Y)\sim\mathcal{L}(Z,Y)}\left[2d_{\mathsf{TV}}\left((T({\widetilde{X}},Z,Y)|Z,Y),(T(X,Z,Y)|Z,Y)\right)\right],$

with $X\sim\mathcal{L}(X|Z,Y)$, ${\widetilde{X}}\sim\mathcal{L}(X|Z)$, and
$f_{T|Z,Y}$ and $f_{T|Z}$ representing the density functions corresponding to
cdfs $F_{T|Z,Y}$ and $F_{T|Z}$ . Note that in (a) we used (45); (b) is a
direct result of Jenson’s inequality, and (c) follows from Assumption 4.3 in
conjunction with the Fubini’s theorem.

###  9.7 Proof of Proposition 4.6

Based on the Pearson $\chi^{2}$-CI statistic $U_{n,L}$ construction that is
described in Algorithm 1, for a sample point $(X,Z,Y)$ and its $M$ constructed
counterfeits $\\{({\widetilde{X}}^{(i)},Y,Z)\\}_{i=1}^{M}$ we have the
following rank value

$R=1+\sum\limits_{i=1}^{M}{\mathbb{I}}_{\\{T(X,Z,Y)\geq
T({\widetilde{X}}^{(i)},Z,Y)\\}}\,.$

This allows us to compute the probability of $(X,Z,Y)$ getting label
$s\in[L]$:

$\displaystyle{\mathbb{P}}\left((X,Z,Y)\text{ has label }s\right)$
$\displaystyle={\mathbb{P}}\left((s-1)K+1\leq R\leq sK\right)$
$\displaystyle=\sum\limits_{j=K(s-1)+1}^{Ks}{\mathbb{P}}(R=j)$
$\displaystyle=\sum\limits_{j=K(s-1)+1}^{Ks}{\mathbb{E}}_{ZY}[{\mathbb{P}}(R=j|Y=y,Z=z)]\,.$
(46)

Note that by conditioning on $(Z,Y)=(z,y)$, random variables $T(X,Z,Y)$ and
$T({\widetilde{X}}_{j},Z,Y)$ are independent. To lighten the notation, we use
the shorthands $T:=T(X,Z,Y)$ and
$\widetilde{T}_{i}=T({\widetilde{X}}^{(i)},Z,Y)$, and proceed as follows:

$\displaystyle{\mathbb{P}}\left(R=j|Y=y,Z=z\right)$
$\displaystyle={\mathbb{P}}\left(T\text{ is exactly larger than }j-1\text{ of
}\widetilde{T}_{i}|Z=z,Y=y\right)$
$\displaystyle\overset{(a)}{=}\int{\mathbb{P}}\big{(}t\text{ is exactly larger
than }j-1\text{ of }\widetilde{T}_{i}|Z=z,Y=y\big{)}\;{\rm d}F_{T|ZY}(t;z,y)$
$\displaystyle\overset{(b)}{=}\binom{M}{j-1}\int
F_{T|Z}(t;z,y)^{j-1}(1-F_{T|Z}(t;z,y))^{M-j+1}{\rm d}F_{T|ZY}(t;z,y)$
$\displaystyle{=}\binom{M}{j-1}\int\limits_{0}^{1}u^{j-1}(1-u)^{M-j+1}{\rm
d}F_{T|ZY}\big{(}F_{T|Z}^{-1}(u;z,y);z,y\big{)}\,,$ (47)

where (a) comes from the fact that $T|ZY$ has density $F_{T|ZY}(.)$, and (b)
holds since $\widetilde{T}_{i}|ZY$ is distributed according to $F_{T|Z}(.)$,
independent of $T$. Note that for a function $f(t)$, the notation ${\rm
d}f(t)=f^{\prime}(t){\rm d}t$ denotes the differential of $f(t)$.

We next plug in equation (47) into (46) to get

$\displaystyle{\mathbb{P}}\left((X,Z,Y)\text{ has label }s\right)$
$\displaystyle=\sum\limits_{j=K(s-1)+1}^{Ks}\binom{M}{j-1}{\mathbb{E}}_{ZY}\left[\int\limits_{0}^{1}u^{j-1}(1-u)^{M-j+1}{\rm
d}F_{T|ZY}\big{(}F_{T|Z}^{-1}(u;Z,Y);Z,Y\big{)}\right]$
$\displaystyle\overset{(a)}{=}\sum\limits_{j=K(s-1)+1}^{Ks}\binom{M}{j-1}\int\limits_{0}^{1}u^{j-1}(1-u)^{M-j+1}{\mathbb{E}}_{ZY}\left[{\rm
d}F_{T|ZY}\big{(}F_{T|Z}^{-1}(u;Z,Y);Z,Y\big{)}\right]$
$\displaystyle\overset{{(b)}}{=}\sum\limits_{j=K(s-1)+1}^{Ks}\binom{M}{j-1}\int\limits_{0}^{1}u^{j-1}(1-u)^{M-j+1}{\rm
d}{\mathbb{E}}_{ZY}\left[F_{T|ZY}\big{(}F_{T|Z}^{-1}(u;Z,Y);Z,Y\big{)}\right]$
$\displaystyle=\sum\limits_{j=K(s-1)+1}^{Ks}\binom{M}{j-1}\int\limits_{0}^{1}u^{j-1}(1-u)^{M-j+1}{\rm
d}\mathsf{R}_{T}(u)$
$\displaystyle=\sum\limits_{j=K(s-1)}^{Ks-1}\binom{M}{j}\int\limits_{0}^{1}u^{j}(1-u)^{M-j}\mathsf{r}_{T}(u){\rm
d}u\,,$ (48)

in (a) we used the Fubini’s theorem along with Assumption 4.3 and the fact
that for every $0\leq u\leq 1$ we have $|u^{j}(1-u)^{M-j}|\leq 1$. Also, (b)
is a direct result of Assumption 4.3 and dominated convergence theorem. This
completes the proof of claim (13).

It is worth noting that, when $X\perp\\!\\!\\!\perp Y|Z$, we have
$P_{X|ZY}=P_{X|Z}$ which implies $\mathsf{R}_{T}(u)=u$, so the conditional
relative density function $\mathsf{r}_{T}(u)$ always attains the constant
value $1$. In this case, we have

$\displaystyle p_{s}$
$\displaystyle=\sum\limits_{j=K(s-1)}^{Ks-1}\binom{M}{j}\int\limits_{0}^{1}u^{j}(1-u)^{M-j}{\rm
d}u$ $\displaystyle=\sum\limits_{j=K(s-1)}^{Ks-1}\binom{M}{j}B(j+1,M-j+1)$
$\displaystyle=\sum\limits_{j=K(s-1)}^{Ks-1}\binom{M}{j}\frac{\Gamma(j+1)\Gamma(M-j+1)}{\Gamma(M+2)}$
$\displaystyle=\sum\limits_{j=K(s-1)}^{Ks-1}\binom{M}{j}\frac{j!(M-j)!}{(M+1)!}$
$\displaystyle=\sum\limits_{j=K(s-1)}^{Ks-1}\frac{1}{M+1}$
$\displaystyle=\frac{k}{M+1}=\frac{1}{L}\,,$ (49)

where $B(a,b)$ is the Beta function and $\Gamma(a)$ is the Gamma function.

Now, we are ready to prove Part $(i)$. First note that deriving a more
explicit characterization of $p_{s}$ from (48) is in general intractable, due
to the relative density term $\mathsf{r}_{T}(u)$ in the inner integral
expression . However, it is useful to note that if $\mathsf{r}_{T}(u)$ is a
polynomial of $u$, then this probability can be easily computed by absorbing
that into the integral formulation of the Beta function and then leveraging
the connection between the Gamma function and Beta function for integer
values. Inspired by this observation, our strategy is to approximate
$\mathsf{r}_{T}(u)$ with polynomials. To this end, note that by Assumption
4.2, $\mathsf{r}_{T}(u)$ is a continuous function over $[0,1]$ interval, which
allows us to use the Weierstrass theorem to uniformly approximate
$\mathsf{r}_{T}(u)$ as closely as desired by polynomials. Formally, for any
${\varepsilon}>0$ there exists a polynomial $\widetilde{r}(u)$ with real
coefficients such that

$\sup\limits_{u\in[0,1]}|\widetilde{r}(u)-\mathsf{r}_{T}(u)|<{\varepsilon}\,.$
(50)

Further, from (48) for every $\ell\in[L]$ we have

$\displaystyle\sum\limits_{s=1}^{\ell}p_{s}$
$\displaystyle=\sum\limits_{j=0}^{\ell
K-1}\binom{M}{j}\int\limits_{0}^{1}u^{j}\big{(}1-u\big{)}^{M-j}\mathsf{r}_{T}(u){\rm
d}u$ $\displaystyle\geq\sum\limits_{j=0}^{\ell
K-1}\binom{M}{j}\int\limits_{0}^{1}u^{j}\big{(}1-u\big{)}^{M-j}\widetilde{r}(u){\rm
d}u-{\varepsilon}\sum\limits_{j=0}^{\ell
K-1}\binom{M}{j}\int\limits_{0}^{1}u^{j}\big{(}1-u\big{)}^{M-j}{\rm d}u$
$\displaystyle=\sum\limits_{j=0}^{\ell
K-1}\binom{M}{j}\int\limits_{0}^{1}u^{j}\big{(}1-u\big{)}^{M-j}\widetilde{r}(u){\rm
d}u-\frac{\ell{\varepsilon}}{L}\,,$ (51)

where in the last equality we used the result in (49) that when
$\mathsf{R}_{T}(u)=u$, we have $p_{s}=1/L$. We are left with lower bounding
the right-hand side summation in (51). Let $\widetilde{r}(u)$ be a polynomial
of degree $N$ and coefficients $a_{t}$, i.e.
$\widetilde{r}(u)=\sum\limits_{t=0}^{N}a_{t}u^{t}$. We have

$\displaystyle\sum\limits_{j=0}^{\ell
K-1}\binom{M}{j}\int\limits_{0}^{1}u^{j}\big{(}1-u\big{)}^{M-j}\widetilde{r}(u){\rm
d}u$ $\displaystyle=\sum\limits_{j=0}^{\ell
K-1}\binom{M}{j}\int\limits_{0}^{1}u^{j}\big{(}1-u\big{)}^{M-j}\sum\limits_{t=0}^{N}a_{t}u^{t}{\rm
d}u$ $\displaystyle=\sum\limits_{j=0}^{\ell
K-1}\sum\limits_{t=0}^{N}a_{t}\binom{M}{j}\int\limits_{0}^{1}u^{j+t}\big{(}1-u\big{)}^{M-j}{\rm
d}u$ $\displaystyle=\sum\limits_{j=0}^{\ell
K-1}\sum\limits_{t=0}^{N}a_{t}\binom{M}{j}B(j+t+1,M-j+1)$
$\displaystyle=\sum\limits_{j=0}^{\ell
K-1}\sum\limits_{t=0}^{N}a_{t}\binom{M}{j}\frac{(j+t)!(M-j)!}{(M+t+1)!}$
$\displaystyle=\sum\limits_{t=0}^{N}a_{t}\frac{M!t!}{(M+t+1)!}\sum\limits_{j=0}^{\ell
K-1}\binom{j+t}{t}$
$\displaystyle=\sum\limits_{t=0}^{N}a_{t}\frac{M!t!}{(M+t+1)!}\binom{\ell
K+t}{t+1}$
$\displaystyle=\sum\limits_{t=0}^{N}\frac{a_{t}}{t+1}\prod\limits_{h=0}^{t}\frac{\ell
K+h}{M+1+h}\,,$ (52)

where in the penultimate equation, we used the Hockey-stick identity. Next,
use the following simple inequality in (52)

$\frac{\ell K+h}{M+1+h}\geq\frac{\ell K}{M+1}=\frac{\ell}{L}\,,$

to arrive at

$\displaystyle\sum\limits_{j=0}^{\ell
K-1}\binom{M}{j}\int\limits_{0}^{1}u^{j}\big{(}1-u\big{)}^{M-j}\widetilde{r}(u){\rm
d}u\geq\sum\limits_{t=0}^{N}\frac{a_{t}}{t+1}\left(\frac{\ell}{L}\right)^{t+1}=\int\limits_{0}^{\frac{\ell}{L}}\widetilde{r}(u){\rm
d}u\,.$

Next we plug the above lower bound into (51) to get

$\sum\limits_{s=1}^{\ell}p_{s}\geq\int\limits_{0}^{\frac{\ell}{L}}\widetilde{r}(u){\rm
d}u-\frac{\ell{\varepsilon}}{L}\,,$

which along with (50) implies that

$\sum\limits_{s=1}^{\ell}p_{s}\geq\int\limits_{0}^{\frac{\ell}{L}}\mathsf{r}_{T}(u)du-\frac{2\ell{\varepsilon}}{L}=\mathsf{R}_{T}\left(\frac{\ell}{L}\right)-\frac{2\ell{\varepsilon}}{L}\,.$

Finally, since ${\varepsilon}>0$ can be chosen arbitrarily small, by letting
${\varepsilon}\to 0$ we get the desired claim of (14).

We next proceed to Part $(ii)$. In Part $(i)$, we use a general form of the
Weierstrass approximation theorem, to uniformly approximate $\mathsf{r}_{T}$
as closely as desired, while the rate of convergence (in terms of the
polynomial degree) was not needed. For establishing an upper bound on the sum
of labels probabilities, $\sum\limits_{s=1}^{\ell}p_{s}$, we need to upper
bound the polynomial-approximation error, and knowing the convergence rate
becomes important. For this reason, we use a more refined version of the
Weierstrass approximation theorem. For the reader’s convenience, we state this
version in the following lemma, borrowed from [GP97]:

######  Lemma 9.7 ( [GP97], Theorem 1).

Let $f$ be a $B$-bounded and $C-$Lipschitz continuous function on $[0,1]$.
Then, for every positive integer $N$, there exists a polynomial
$\widetilde{f}_{N}$ of degree $N$ such that

$\sup\limits_{u\in[0,1]}|f(u)-\widetilde{f}_{N}(u)|\leq(C/2+2B)\sqrt{\frac{\log{N}}{N}}\,.$

Recall that by Assumption 4.2, $\mathsf{r}_{T}(u)$ is $B$-bounded and
$C$-Lipschitz, and therefore, by an application of Lemma 9.7 there exists a
polynomial $\widetilde{r}_{N}$ of degree $N$, such that for $D=C/2+2B$ we have

$\|\mathsf{r}_{T}-\widetilde{r}_{N}\|_{\infty}\leq
D\sqrt{\frac{\log{N}}{N}}\,.$ (53)

Let $\widetilde{r}_{N}(u)=\sum\limits_{t=0}^{N}a_{t}u^{t}$. By a similar
argument used in deriving (51) and (52), we get

$\displaystyle\sum\limits_{s=1}^{\ell}p_{s}$
$\displaystyle\leq\sum\limits_{t=0}^{N}\frac{a_{t}}{t+1}\prod\limits_{h=0}^{t}\frac{\ell
K+h}{M+1+h}+\frac{\ell D}{L}\sqrt{\frac{\log{N}}{N}}\,.$ (54)

To further simplify the right-hand side, we use the following simple algebraic
manipulations. Since $h\leq t\leq N$ and $M+1=LK\geq\ell K$ we have $(M+1-\ell
K)(N-h)\geq 0$, from which we get

$\displaystyle\frac{\ell K+h}{M+1+h}$ $\displaystyle\leq\frac{\ell
K+N}{M+1+N}$ $\displaystyle=\frac{\ell
K+N}{LK+N}=\frac{\ell}{L}\left(\frac{K+\tfrac{N}{\ell}}{K+\tfrac{N}{L}}\right)\leq\frac{\ell}{L}\left(1+\frac{N}{K}\right)\,.$

Using this bound in (54), for $h\geq 1$, we arrive at

$\displaystyle\sum\limits_{s=1}^{\ell}p_{s}$
$\displaystyle\leq\left(1+\frac{N}{k}\right)^{N}\sum\limits_{t=0}^{N}\frac{a_{t}}{t+1}\left(\frac{\ell}{L}\right)^{t+1}+\frac{\ell
D}{L}\sqrt{\frac{\log{N}}{N}}$
$\displaystyle=\left(1+\frac{N}{K}\right)^{N}\int\limits_{0}^{\frac{\ell}{L}}\widetilde{r}_{N}(u){\rm
d}u+\frac{\ell D}{L}\sqrt{\frac{\log{N}}{N}}$ $\displaystyle\leq
e^{N^{2}/K}\int\limits_{0}^{\frac{\ell}{L}}\widetilde{r}_{N}(u){\rm
d}u+\frac{\ell D}{L}\sqrt{\frac{\log{N}}{N}}\,.$

By using (53) again, we obtain

$\displaystyle\sum\limits_{s=1}^{\ell}p_{s}$ $\displaystyle\leq
e^{N^{2}/K}\int\limits_{0}^{\frac{\ell}{L}}\widetilde{r}_{N}(u){\rm
d}u+\frac{2\ell D}{L}\sqrt{\frac{\log{N}}{N}}$
$\displaystyle=e^{N^{2}/k}\;\mathsf{R}_{T}\left(\frac{\ell}{L}\right)+\frac{2\ell
D}{L}\sqrt{\frac{\log{N}}{N}}\ \,.$

Set $N=\sqrt{k\log(1+\delta)}$ for a fixed $0<\delta<1$ and rewrite the above
bound as

$\sum\limits_{s=1}^{\ell}p_{s}\leq(1+\delta)\mathsf{R}_{T}\left(\frac{\ell}{L}\right)+\frac{2\ell
D}{L}\left(\frac{\log\left(K\log(1+\delta)\right)}{2\sqrt{K\log(1+\delta)}}\right)^{1/2}\,.$

By using the relations $L\leq\ell$, $\delta<1$, $\mathsf{R}_{T}(u)\leq 1$, and
$\log(1+\delta)\geq\delta/2$, for $\delta\in[0,1]$, we obtain

$\sum\limits_{s=1}^{\ell}p_{s}\leq\mathsf{R}_{T}\left(\frac{\ell}{L}\right)+\delta+2D\left(\frac{\log{K}}{\sqrt{K\delta}}\right)^{1/2}\,.$

Minimizing the right-hand side over $\delta$, we get
$\delta=\left(\frac{4D^{2}\log{k}}{\sqrt{k}}\right)^{2/5}$ , which is smaller
than one for $k$ sufficiently large. Plugging in for this value of $\delta$ we
obtain

$\sum\limits_{s=1}^{\ell}p_{s}\leq\mathsf{R}_{T}\left(\frac{\ell}{L}\right)+\nu_{K}\,,$

with $\nu_{K}=2\left(\frac{4D^{2}\log{K}}{\sqrt{K}}\right)^{2/5}$.

We next proceed to prove Part $(iii)$. For $1\leq s\leq\ell$, let

$q_{s}:=\mathsf{R}_{T}\left(\frac{s}{L}\right)-\mathsf{R}_{T}\left(\frac{s-1}{L}\right)\,,$
(55)

By employing the results of parts $(i)$ and $(ii)$ we have

$\displaystyle\left|p_{s}-q_{s}\right|\leq\Big{|}\sum_{j=1}^{s}p_{j}-\mathsf{R}_{T}\left(\frac{s}{L}\right)-\sum_{j=1}^{s-1}p_{j}+\mathsf{R}_{T}\left(\frac{s-1}{L}\right)\Big{|}\leq\nu_{K}\,.$

Therefore,

$\displaystyle\sum\limits_{s=1}^{L}\left|p_{s}-\frac{1}{L}\right|\geq\sum\limits_{s=1}^{L}\left|q_{s}-\frac{1}{L}\right|-\sum\limits_{s=1}^{L}\left|p_{s}-q_{s}\right|\geq-L\nu_{K}+\sum\limits_{s=1}^{L}\left|q_{s}-\frac{1}{L}\right|\,.$
(56)

Next, by applying the mean value theorem in the definition of $q_{s}$ in (55),
for every $s\in[L]$, there exists
$\xi_{s}\in\left(\frac{s-1}{\ell},\frac{s}{\ell}\right)$, such that
$q_{s}=\mathsf{r}_{T}(\xi_{s})/L$. Therefore,

$\displaystyle\sum\limits_{s=1}^{L}\left|q_{s}-\frac{1}{L}\right|$
$\displaystyle=\frac{1}{L}\sum\limits_{s=1}^{L}|\mathsf{r}_{T}(\xi_{s})-1|$
$\displaystyle=\sum\limits_{s=1}^{L}\int\limits_{\frac{s-1}{L}}^{\frac{s}{L}}|\mathsf{r}_{T}(\xi_{s})-1|{\rm
d}u$
$\displaystyle\geq\sum\limits_{s=1}^{L}\int\limits_{\frac{s-1}{L}}^{\frac{s}{L}}|\mathsf{r}_{T}(u)-1|{\rm
d}u-\sum\limits_{s=1}^{L}\int\limits_{\frac{s-1}{L}}^{\frac{s}{L}}\left|\mathsf{r}_{T}(u)-\mathsf{r}_{T}(\xi_{s})\right|{\rm
d}u$ $\displaystyle\geq\int\limits_{0}^{1}|\mathsf{r}_{T}(u)-1|{\rm
d}u-\sum\limits_{s=1}^{L}\int\limits_{\frac{s-1}{L}}^{\frac{s}{L}}{C|u-\xi_{s}|}{}{\rm
d}u$ $\displaystyle\geq\int\limits_{0}^{1}|\mathsf{r}_{T}(u)-1|{\rm
d}u-\sum\limits_{s=1}^{L}\frac{C}{L^{2}}=\int\limits_{0}^{1}|\mathsf{r}_{T}(u)-1|{\rm
d}u-\frac{C}{L}\,.$

Using the above lower bound into (56) gives

$\sum\limits_{s=1}^{L}\left|p_{s}-\frac{1}{L}\right|\geq\int\limits_{0}^{1}|\mathsf{r}_{T}(u)-1|{\rm
d}u-\ell\nu_{K}-\frac{C}{L}\,.$

###  9.8 Proof of Theorem 4.7

The primary arguments here are similar to the initial reasonings in the proof
of Theorem 3.2, where we arrived at the point that the joint distribution of
$(nW_{1},nW_{2},...,nW_{L})$ is a multinomial distribution with $L$
categories, such that category $s\in[L]$ happens with probability $p_{s}$.
Next, recall Lemma 9.1, part 3, where it implies that if for some $\beta>0$,
the following holds:

$\sum\limits_{s=1}^{L}\left|p_{s}-\frac{1}{L}\right|\geq\frac{32{L^{1/4}}}{\sqrt{n}}\left[\frac{1}{\sqrt{\alpha}}\vee\frac{1}{\beta}\right]^{1/2}\,,$
(57)

then the type II error is bounded by $\beta$. On the other hand, from
Proposition 4.6 we have

$\displaystyle\sum\limits_{s=1}^{L}\left|p_{s}-\frac{1}{L}\right|\geq\int\limits_{0}^{1}|\mathsf{r}_{T}(u){\rm
d}u-1|-L\nu_{L}-\frac{C}{L}\,.$ (58)

Combining equations (57) and (58), in conjunction with the definition of the
conditional dependency in Definition 4.4 completes the proof.

###  9.9 Proof of Theorem 4.8

The first step is similar to initial arguments of the proof of Theorem 3.2,
where we showed that the joint distribution of $(nW_{1},nW_{2},...,nW_{L})$ is
a multinomial distribution with $L$ categories, such that the category
$\ell\in[L]$ occurs with probability $p_{\ell}$. We then use the following
asymptotic result on the Pearson’s $\chi^{2}$ test statistic for multinomial
models (see e.g., [LR06, Theorem 14.3.1]):

$U_{n,L}\overset{(d)}{\Rightarrow}\chi^{2}_{\lambda,L-1}\,,$ (59)

where $\chi^{2}_{\lambda_{n},L-1}$ stands for the $\chi^{2}$ distribution with
$L-1$ degrees of freedom and the non-central parameter
$\lambda=\sum\limits_{\ell=1}^{L}nL\left(p_{\ell}-\frac{1}{L}\right)^{2}$.
This gives us

$\displaystyle\lim\limits_{n\rightarrow\infty}{\mathbb{P}}\left(U_{n,\ell}\geq\theta^{\mathsf{asym}}_{L,\alpha}\right)$
$\displaystyle=\lim\limits_{n\rightarrow\infty}{\mathbb{P}}_{Q\sim\chi^{2}_{\lambda,L-1}}\left(Q\geq\theta^{\mathsf{asym}}_{L,\alpha}\right)\,.$
(60)

Using the Cauchy inequality for
$\lambda=\sum\limits_{\ell=1}^{L}nL\left(p_{\ell}-\frac{1}{L}\right)^{2}$
yields

$\sqrt{\lambda}\geq\sqrt{n}\sum\limits_{\ell=1}^{L}\left|p_{\ell}-\frac{1}{L}\right|\,.$

We then recall the result from Proposition 4.6 to get

$\displaystyle\sum\limits_{s=1}^{L}\left|p_{s}-\frac{1}{L}\right|\geq\int\limits_{0}^{1}|\mathsf{r}_{T}(u){\rm
d}u-1|-L\nu_{L}-\frac{C}{L}\,.$ (61)

In the next step, combine (61) and the lower bound on the conditional
dependency power in Theorem (4.7) to get $\lambda\geq\widetilde{\lambda}$ with
$\widetilde{\lambda}=A^{2}L^{1/2}$, where $A$ is given by:

$A=\max\left(\sqrt{3\log\frac{1}{\beta}}+\left(3\log\frac{1}{\beta}+2\sqrt{\log\frac{1}{\alpha}}+2\log\frac{1}{\alpha}\right)^{1/2},~{}1\right)\,.$
(62)

Using $\lambda\geq\widetilde{\lambda}$ in (60) yields

$\lim\limits_{n\rightarrow\infty}{\mathbb{P}}\left(U_{n,\ell}\geq\theta^{\mathsf{asym}}_{L,\alpha}\right)\geq{\mathbb{P}}_{Q\sim\chi^{2}_{\widetilde{\lambda},L-1}}\left(Q\geq\theta^{\mathsf{asym}}_{L,\alpha}\right)\,.$
(63)

We then provide the following inequality borrowed from [Bir01] on tails of
non-central $\chi^{2}$ random variables.

######  Lemma 9.8 ([Bir01], Lemma 8.1).

Suppose that random variable $X$ has a $\chi^{2}$ distribution with $m$
degrees of freedom and non-central parameter $\lambda$. Then for every $t\geq
0$ we have

$\displaystyle{\mathbb{P}}\left(X\leq
m+\lambda-2\sqrt{(m+2\lambda)t}\right)\leq\exp(-t)\,,$
$\displaystyle{\mathbb{P}}\left(X\geq
m+\lambda+2\sqrt{(m+2\lambda)t}+2t\right)\leq\exp(-t)\,.$

As an immediate consequence of Lemma 9.8, we can obtain the following upper
bound on the $(1-\alpha)$-th quantile of the central $\chi^{2}$ distribution
with $m$ degrees of freedom:

$\chi^{2}_{m}(1-\alpha)\leq
m+2\sqrt{m\log\frac{1}{\alpha}}+2\log\frac{1}{\alpha}\,.$ (64)

By exploiting (64) in
$\theta^{\mathsf{asym}}_{L,\alpha}=\chi^{2}_{L-1}(1-\alpha)$ we arrive at

$\theta^{\mathsf{asym}}_{L,\alpha}\leq
L-1+2\sqrt{(L-1)\log\frac{1}{\alpha}}+2\log\frac{1}{\alpha}\,.$ (65)

Using (65) in (63) brings us

$\lim\limits_{n\rightarrow\infty}{\mathbb{P}}\left(U_{n,\ell}\geq\theta^{\mathsf{asym}}_{L,\alpha}\right)\geq{\mathbb{P}}_{Q\sim\chi^{2}_{\widetilde{\lambda},L-1}}\left(Q\geq
L-1+2\sqrt{(L-1)\log\frac{1}{\alpha}}+2\log\frac{1}{\alpha}\right)\,.$ (66)

We next claim that

$2\sqrt{(L-1)\log\frac{1}{\alpha}}+2\log\frac{1}{\alpha}\leq
A^{2}L^{1/2}-2\sqrt{(L-1+2A^{2}L^{1/2})\log\frac{1}{\beta}}\,.$ (67)

Deploying (67) (we provide the proof of claim (67) later) in (66) yields

$\lim\limits_{n\rightarrow\infty}{\mathbb{P}}\left(U_{n,\ell}\geq\theta^{\mathsf{asym}}_{L,\alpha}\right)\geq{\mathbb{P}}_{Q\sim\chi^{2}_{\widetilde{\lambda},L-1}}\left(Q\geq
L-1+A^{2}L^{1/2}-2\sqrt{(L-1+2A^{2}L^{1/2})\log\frac{1}{\beta}}\right)\,.$
(68)

Next by using the first tail bound of Lemma 9.8 (for values
$m=L-1,\widetilde{\lambda}=A^{2}L^{1/2}$, and $t=\log\frac{1}{\beta}$) in (68)
we obtain

$\lim\limits_{n\rightarrow\infty}{\mathbb{P}}\left(U_{n,\ell}\geq\theta^{\mathsf{asym}}_{L,\alpha}\right)\geq
1-\beta\,.$

This completes the proof. Finally, we are left to prove the claim (67). As
$L\geq 1$, we have

$\displaystyle\widetilde{\theta}:=A^{2}L^{1/2}-2\sqrt{(L-1+2A^{2}L^{1/2})\log\frac{1}{\beta}}\geq\sqrt{L}\left(A^{2}-2\sqrt{(1+2A^{2})\log\frac{1}{\beta}}\right)\,.$

In the next step, by using $A\geq 1$, we get

$\displaystyle\widetilde{\theta}$
$\displaystyle\geq\sqrt{L}\left(A^{2}-2A\sqrt{3\log\frac{1}{\beta}}\right)$
$\displaystyle\geq\sqrt{L}\left(A-\sqrt{3\log\frac{1}{\beta}}\right)^{2}-3\sqrt{L}\log\frac{1}{\beta}$
$\displaystyle\geq\sqrt{L}\left(2\sqrt{\log\frac{1}{\alpha}}+2\log\frac{1}{\alpha}\right)\,,$
(69)

where the last inequality is followed by the definition of $A$ in (62). We
then use $L\geq 1$ in (69) to arrive at the following:

$\widetilde{\theta}\geq
2\sqrt{(L-1)\log\frac{1}{\alpha}}+2\log\frac{1}{\alpha}\,.$

This proves the claim (67).

###  9.10 Proof of Theorem 6.1

Consider a data point $(X,Z,Y)$ and its $M=KL-1$ counterfeits
$({\widetilde{X}}^{(1:M)},Z,Y)$ where ${\widetilde{X}}^{(j)}$ is sampled from
$\widehat{P}_{X|Z}(\cdot|Z)$, for $j\in[M]$. Assume $\widehat{X}$ is also
drawn from $\widehat{P}_{X|Z}(\cdot|Z)$, independently of
${\widetilde{X}}^{(1:M)},X,$ and $Y$. We fix the values of $Z,Y$, and for
$s\in[L]$ define

$A_{s}=\left\\{(x,\tilde{x}^{(1)},...,\tilde{x}^{(M)}):(s-1)K\leq\sum\limits_{j=1}^{M}{\mathbb{I}}_{\\{T(x,Z,Y)\geq
T(\tilde{x}^{(j)},Z,Y)\\}}\leq sK-1\right\\}\,.$

We have

$\displaystyle\left|{\mathbb{P}}\left((X,Z,Y)\text{ has label
}s|Z,Y\right)-\frac{1}{L}\right|$
$\displaystyle\overset{(a)}{=}\left|{\mathbb{P}}\left((X,{\widetilde{X}}^{(1)},...,{\widetilde{X}}^{(M)})\in
A_{s}|Z,Y\right)-\frac{1}{L}\right|$
$\displaystyle\overset{(b)}{=}\left|{\mathbb{P}}\left((X,{\widetilde{X}}^{(1)},...,{\widetilde{X}}^{(M)})\in
A_{s}|Z,Y\right)-{\mathbb{P}}\left((\widehat{X},{\widetilde{X}}^{(1)},...,{\widetilde{X}}^{(M)})\in
A_{s}|Z,Y\right)\right|$
$\displaystyle\overset{(c)}{\leq}d_{\mathsf{TV}}\left(((X,{\widetilde{X}}^{(1)},...,{\widetilde{X}}^{(M)})|Z,Y),((\widehat{X},{\widetilde{X}}^{(1)},...,{\widetilde{X}}^{(M)})|Z,Y)\right)$
$\displaystyle\overset{(d)}{=}d_{\mathsf{TV}}\left((X|Z,Y),(\widehat{X}|Z,Y)\right)$
$\displaystyle\overset{(e)}{=}d_{\mathsf{TV}}\left((X|Z),(\widehat{X}|Z)\right)=d_{\mathsf{TV}}\left(P_{X|Z}(\cdot|Z),\widehat{P}_{X|Z}(\cdot|Z)\right)\,,$
(70)

where $(a)$ comes from the process of labeling the data points; in (b) we used
the fact that conditioned on $Z,Y$ random variables
${\widetilde{X}},{\widetilde{X}}^{(1)},...,{\widetilde{X}}^{(M)}$ are i.i.d.,
hence $\sum\limits_{j=1}^{M}{\mathbb{I}}_{\\{T(x,Z,Y)\geq
T(\tilde{x}^{(j)},Z,Y)\\}}$ takes values $\\{0,1,...,M\\}$, uniformly at
random; (c) is a direct result from the total variation definition; in $(d)$
we used the property that conditioned on $(Z,Y)$, random variables
$(X,{\widetilde{X}},{\widetilde{X}}^{(1)},...,{\widetilde{X}}^{(M)})$ are
independent; $(e)$ comes from the fact that the under null hypothesis,
$X\perp\\!\\!\\!\perp Y|Z$ and also $\widehat{X}\perp\\!\\!\\!\perp Y|Z$ by
construction of $\widehat{X}$.

In the current scenario that counterfeits are drawn from the approximate law
$\widehat{P}_{X|Z}(.|Z)$, define $q_{s}$ to be the probability that under the
null hypothesis, a typical data point $(X,Z,Y)$ gets label $s$. Then, by
marginalizing over $Z$, we can upper bound the deviation of $q_{s}$ from
$1/L$, as follows:

$\displaystyle\left|q_{s}-\frac{1}{L}\right|$
$\displaystyle=\left|{\mathbb{P}}\left((X,Z,Y)\text{ has label
}s\right)-\frac{1}{L}\right|$
$\displaystyle=\left|\int{\mathbb{P}}\left((X,Z,Y)\text{ has label
}s|Z,Y\right){\rm d}P_{ZY}-\frac{1}{L}\right|$
$\displaystyle=\left|\int\left({\mathbb{P}}\left((X,Z,Y)\text{ has label
}s|Z,Y\right)-\frac{1}{L}\right){\rm d}P_{ZY}\right|$
$\displaystyle\leq\int\left|{\mathbb{P}}\left((X,Z,Y)\text{ has label
}s|Z,Y\right)-\frac{1}{L}\right|{\rm d}P_{ZY}$
$\displaystyle\overset{(a)}{\leq}\int
d_{\mathsf{TV}}\left(P_{X|Z}(\cdot|Z),\widehat{P}_{X|Z}(\cdot|Z)\right){\rm
d}P_{ZY}$
$\displaystyle={\mathbb{E}}_{Z}\left[d_{\mathsf{TV}}\left(P_{X|Z}(\cdot|Z),\widehat{P}_{X|Z}(\cdot|Z)\right)\right]\leq\delta\,,$

where (a) comes from (70). In summary we get

$\left|q_{s}-\frac{1}{\ell}\right|\leq\delta,\quad\text{ for
}s=1,2,...,\ell\,.$ (71)

Recall $W_{s}$ as the number of data points getting label $s$. Clearly,

$(W_{1},...,W_{L})=\mathsf{multi}\left(n;q_{1},...,q_{\ell}\right)\,.$

We next use a result on the size of truncated $\chi^{2}$ test from [BW+19,
Theorem 3.2], which implies the first inequality in the chain of inequalities
below:

$\displaystyle\alpha$
$\displaystyle\geq{\mathbb{P}}\left(\sum\limits_{s=1}^{L}\frac{(W_{s}-nq_{s})^{2}-W_{s}}{\max\\{q_{s},\frac{1}{L}\\}}\geq
n\sqrt{\frac{2}{\alpha}\sum\limits_{s=1}^{L}\left(\frac{q_{s}}{\max\\{q_{s},1/L\\}}\right)^{2}}\right)$
$\displaystyle\geq{\mathbb{P}}\left(\sum\limits_{s=1}^{L}\frac{(W_{s}-nq_{s})^{2}-W_{s}}{\max\\{q_{s},\frac{1}{L}\\}}\geq
n\sqrt{\frac{2}{\alpha}L}\right)$
$\displaystyle={\mathbb{P}}\left(\sum\limits_{s=1}^{L}\frac{(W_{s}-nq_{s})^{2}}{\max\\{q_{s},\frac{1}{L}\\}}\geq\sum\limits_{s=1}^{L}\frac{W_{s}}{\max\\{q_{s},\frac{1}{L}\\}}+n\sqrt{\frac{2}{\alpha}L}\right)$
$\displaystyle\geq{\mathbb{P}}\left(\sum\limits_{s=1}^{L}\frac{(W_{s}-nq_{s})^{2}}{\max\\{q_{s},\frac{1}{L}\\}}\geq
L\sum\limits_{s=1}^{L}{W_{s}}+n\sqrt{\frac{2}{\alpha}L}\right)$
$\displaystyle={\mathbb{P}}\left(\sum\limits_{s=1}^{L}\frac{(W_{s}-nq_{s})^{2}}{\max\\{q_{s},\frac{1}{L}\\}}\geq
nL+n\sqrt{\frac{2}{\alpha}L}\right)$
$\displaystyle\overset{(a)}{\geq}{\mathbb{P}}\left(\sum\limits_{s=1}^{L}\frac{(W_{s}-nq_{s})^{2}}{\frac{1}{L}+\delta}\geq
nL+n\sqrt{\frac{2}{\alpha}L}\right)$
$\displaystyle\geq{\mathbb{P}}\left(\frac{L}{n(1+L\delta)}\sum\limits_{s=1}^{L}{\left(W_{s}-nq_{s}\right)^{2}}\geq
L+\sqrt{\frac{2}{\alpha}L}\right)$
$\displaystyle\geq{\mathbb{P}}\left(U_{n,L}(\delta)\geq
L+\sqrt{\frac{2}{\alpha}L}\right)\,,$

where $(a)$ comes from (71) and the last inequality follows from the
definition of $U_{n,L}$. This concludes the proof of claim (20).

For the claim (21), we use the following asymptotic result on the Pearson’s
$\chi^{2}$ test statistic for multinomial models (see e.g, [LR06, Theorem
14.3.1]):

$\lim\limits_{n\rightarrow\infty}{\mathbb{P}}\left(\sum\limits_{s=1}^{L}\frac{(W_{s}-nq_{s})^{2}}{nq_{s}}\geq\theta^{\mathsf{asym}}_{L,\alpha}\right)\leq\alpha\,,$
(72)

where $\theta^{\mathsf{asym}}_{L,\alpha}$ is the $\alpha$-th upper quantile of
a Chi-squared distribution with $L-1$ degrees of freedom. By definition of
$U_{n,L}(\delta)$, we have

$\displaystyle{\mathbb{P}}\left(U_{n,\ell}(\delta)\geq\theta^{\mathsf{asym}}_{L,\alpha}\right)$
$\displaystyle\leq{\mathbb{P}}\left(\frac{L}{n(1+L\delta)}\sum\limits_{s=1}^{L}(W_{s}-nq_{s})^{2}\geq\theta^{\mathsf{asym}}_{L,\alpha}\right)$
$\displaystyle\leq{\mathbb{P}}\left(\sum\limits_{s=1}^{L}\frac{(W_{s}-nq_{s})^{2}}{nq_{s}}\geq\theta^{\mathsf{asym}}_{L,\alpha}\right)\,,$

where in the last inequality we used (71). Finally, plug the above relation
into (72) to get the following relation:

$\lim\limits_{n\rightarrow\infty}{\mathbb{P}}\left(U_{n,L}(\delta)\geq\theta^{\mathsf{asym}}_{L,\alpha}\right)\leq\alpha\,.$

This concludes the proof.

## References

  * [AC19] Mona Azadkia and Sourav Chatterjee.  A simple measure of conditional dependence.  arXiv preprint arXiv:1910.12327, 2019.
  * [Bam75] Donald Bamber.  The area above the ordinal dominance graph and the area below the receiver operating characteristic graph.  Journal of mathematical psychology, 12(4):387–415, 1975.
  * [BC05] Andrew D Barbour and Louis Hsiao Yun Chen.  An introduction to Stein’s method, volume 4.  World Scientific, 2005.
  * [BCH14] Alexandre Belloni, Victor Chernozhukov, and Christian Hansen.  Inference on treatment effects after selection among high-dimensional controls.  The Review of Economic Studies, 81(2):608–650, 2014.
  * [BCJW20] Stephen Bates, Emmanuel Candès, Lucas Janson, and Wenshuo Wang.  Metropolized knockoff sampling.  Journal of the American Statistical Association, pages 1–15, 2020\.
  * [BH95] Yoav Benjamini and Yosef Hochberg.  Controlling the false discovery rate: a practical and powerful approach to multiple testing.  Journal of the Royal statistical society: series B (Methodological), 57(1):289–300, 1995.
  * [Bir01] Lucien Birgé.  An alternative point of view on lepski’s method.  Lecture Notes-Monograph Series, pages 113–133, 2001.
  * [BJCT17] Anand Bhaskar, Adel Javanmard, Thomas A Courtade, and David Tse.  Novel probabilistic models of spatial genetic ancestry with applications to stratification correction in genome-wide association studies.  Bioinformatics, 33(6):879–885, 2017.
  * [BW+19] Sivaraman Balakrishnan, Larry Wasserman, et al.  Hypothesis testing for densities and high-dimensional multinomials: Sharp local minimax rates.  Annals of Statistics, 47(4):1893–1927, 2019.
  * [BWBS20] 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.