their connection in terms of minimax risks. To fix the terminology, we simply
call the sampling scheme with random missing indicators as _random- $N$
sampling_, whereas the sampling scheme with a fixed number of $N=n$ as _fixed-
$N$ sampling_.

As mentioned in the main text, the i.i.d. nature of random-$N$ sampling
simplifies the analysis and allows us to employ well-established tools for
lower bounds from semi-parametric statistics, such as the local asymptotic
minimax (LAM) theorem (e.g., van der Vaart,, 2000, Theorem 25.21). The key
idea is that if a lower bound holds under random-$N$ sampling, it might
similarly apply to fixed-$N$ sampling, especially when the number of labeled
dataset $N=\sum_{i=1}^{n+m}\delta_{i}$ tightly concentrates around $n$. We
build on this intuition and make their connection concrete in Proposition 6
and Corollary 4.

##### Illustration.

To demonstrate the idea further, suppose that our aim is to return an estimate
of the mean parameter, which can be expressed as
$\psi=\mathbb{E}(Y)=\mathbb{E}\\{\mathbb{E}(Y\,|\,X,\delta=1)\\}$. It is well-
known that (e.g., Kennedy,, 2022, Example 2), the efficient influence function
of $\psi$ is given as

$\displaystyle\varphi(X,\delta
Y,\delta):=\frac{\mathds{1}(\delta=1)}{\mathbb{P}(\delta=1\,|\,X)}\\{Y-\mathbb{E}(Y\,|\,X,\delta=1)\\}+\mathbb{E}(Y\,|\,X,\delta=1)-\mathbb{E}(Y).$

Under positivity (i.e., $\varrho>0$) and missing completely at random
assumptions, the variance of $\varphi$ can be computed as

$\displaystyle\mathrm{Var}\\{\varphi(X,\delta
Y,\delta)\\}=\mathrm{Var}\\{\mathbb{E}(Y\,|\,X,\delta=1)\\}+\varrho^{-1}\mathbb{E}\\{\mathrm{Var}(Y\,|\,X,\delta=1)\\}.$

The LAM theorem asserts that the asymptotic lower bound for the minimax
squared $L_{2}$ risk, scaled by $n+m$, is given as
$\mathrm{Var}_{P}\\{\varphi(X,\delta Y,\delta)\\}$. This lower bound is
established by considering the worst-case scenario within a neighborhood
around the distribution $P$. We refer to van der Vaart, (2000, Theorem 25.21)
for a precise statement. This local asymptotic lower bound partly recovers the
global minimax lower bound for semi-supervised mean estimation in Zhang et
al., (2019, Proposition 3), which is also recalled in Proposition 7. However,
in general cases, we cannot directly translate this lower bound result to
fixed-$N$ sampling without further assumptions. The following example
demonstrates this point.

######  Example 3.

Suppose that we observe i.i.d. triplets
$\\{(X_{i},\delta_{i},\delta_{i}Y_{i})\\}_{i=1}^{n+m}$ and let
$A=\\{\delta_{1}=\cdots=\delta_{n+m}=0\\}$ with $\mathbb{P}(A)>0$. Then a
bias-variance trade-off yields

$\displaystyle\mathbb{E}\\{(\widehat{\psi}-\psi)^{2}\\}~{}\geq~{}$
$\displaystyle\mathbb{E}\\{(\widehat{\psi}-\psi)^{2}\mathds{1}(A)\\}=\\{\mathrm{Var}(\widehat{\psi}\,|\,A)+\\{\mathbb{E}(\widehat{\psi}\,|\,A)-\psi\\}^{2}\\}\mathbb{P}(A)$
$\displaystyle\geq~{}$
$\displaystyle\\{\mathbb{E}(\widehat{\psi}\,|\,A)-\psi\\}^{2}\mathbb{P}(A).$

Under the event $A$, we only observe $X$ values and so
$\mathbb{E}(\widehat{\psi}\,|\,A)$ contains no information of $\psi$ whenever
$X$ and $Y$ are independent. By treating $\mathbb{E}(\widehat{\psi}\,|\,A)$ as
a constant, the lower bound becomes infinite if the parameter space for $\psi$
is unbounded. On the other hand, the risk under fixed-$N$ sampling, i.e.,
$\mathbb{E}\\{(\widehat{\psi}-\psi)^{2}\,|\,\sum_{i=1}^{n+m}\delta_{i}=n\\}$,
does not suffer from the same issue. This demonstrates that the worst-case
risk under random-$N$ sampling can be infinite, while that under fixed-$N$
sampling is finite.

The gap between the minimax risks under different sampling schemes arises
because the risk function is unbounded in the above example. We show in
Corollary 4 that the minimax risks can be made asymptotically equivalent for
bounded risk functions under regularity conditions. In fact, Corollary 4
follows as a direct consequence of Proposition 6 below, which establishes a
non-asymptotic relationship between the unconditional and conditional minimax
risks for some generic estimation problem.

######  Proposition 6.

Given a measurable space $(\mathcal{X},\mathcal{F})$ equipped with a class of
probability measures $\\{P_{\theta}\\}_{\theta\in\Theta}$ of $(X,\delta
Y,\delta)$ and an action space $\widehat{\Theta}$, let
$\mathcal{L}:\widehat{\Theta}\times\Theta\mapsto\mathbb{R}$ be a loss
function. Suppose that

  1. (i)

The experiment is dominated, i.e., there exists some measure $\mu$ such that
$P_{\theta}\ll\mu$ for all $\theta\in\Theta$.

  2. (ii)

The action space $\widehat{\Theta}$ is a locally compact topological space
with a countable base (e.g., Euclidean space).

  3. (iii)

For each $\theta\in\Theta$, the loss function $\mathcal{L}(\cdot,\theta)$ is
bounded below and the sublevel set
$\\{\widehat{\theta}:\mathcal{L}(\widehat{\theta},\theta)\leq a\\}$ is compact
for each $a$.

  4. (iv)

The missing indicator $\delta$ follows $\delta\sim\mathrm{Bernoull}(\varrho)$
with $\varrho=n/(n+m)$ and it is independent of $X$ and $Y$.

Consider the unconditional minimax risk
$\inf_{\widehat{\theta}}\sup_{\theta}\mathbb{E}\\{\mathcal{L}(\widehat{\theta},\theta)\\}$
where the expectation is taken over
$\\{(X_{i},\delta_{i}Y_{i},\delta_{i})\\}_{i=1}^{n+m}$ i.i.d. copies of
$(X,\delta Y,\delta)\sim P_{\theta}$, and denote
$N=\sum_{i=1}^{n+m}\delta_{i}$. Then for any $q\in(1/2,1)$, the unconditional
risk is bounded as

$\displaystyle\mathsf{Risk}_{L,q}\leq\inf_{\widehat{\theta}}\sup_{\theta}\mathbb{E}\\{\mathcal{L}(\widehat{\theta},\theta)\\}\leq\mathsf{Risk}_{U,q}$

where

$\displaystyle\mathsf{Risk}_{L,q}:=\inf_{\widehat{\theta}}\sup_{\theta}\mathbb{E}\\{\mathcal{L}(\widehat{\theta},\theta)\,|\,N=\lfloor
n+n^{q}\rfloor\\}\times\bigl{(}1-e^{-n^{2q-1}/4}\bigr{)}\quad\text{and}$
$\displaystyle\mathsf{Risk}_{U,q}:=\inf_{\widehat{\theta}}\sup_{\theta}\mathbb{E}\\{\mathcal{L}(\widehat{\theta},\theta)\,|\,N=\lfloor
n-n^{q}+1\rfloor\\}+\biggl{(}\sup_{\widehat{\theta},\theta}[\mathbb{E}\\{\mathcal{L}^{2}(\widehat{\theta},\theta)\\}]^{1/2}+1\biggr{)}\times
e^{-n^{2q-1}/4}.$

The abstract conditions (i), (ii) and (iii) are imposed to apply the minimax
theorem (Strasser,, 1985, Theorem 46.6) under which the minimax risk equals
the Bayes risk with a least favorable prior. As discussed in Polyanskiy and
Wu, (2023, Chapter 28.3.4), these conditions are mild and satisfied for
general problems such as the one with the $L_{2}$ risk defined on the
Euclidean space that we consider in this paper. The proof of Proposition 6
builds on the ideas that $N\sim\mathrm{Binomial}\bigl{(}(n+m,n/(n+m)\bigr{)}$
concentrates around $n$ with high probability and the conditional risk of a
(near)-optimal estimator exhibits monotonic behavior as a function of $N$.
These ideas, combined with the fact that the unconditional risk can be
expressed as a weighted average of conditional risks, establishes the desired
bounds. The details can be found in Section D.3. We remark that, as
demonstrated in Example 3, the conditional and unconditional minimax risks can
be significantly different when the loss function is unbounded over the
parameter space. Therefore the term
$\sup_{\widehat{\theta},\theta}[\mathbb{E}\\{\mathcal{L}^{2}(\widehat{\theta},\theta)\\}]^{1/2}$
in the upper bound cannot be entirely negligible.

As a direct corollary of Proposition 6, the following result identifies
sufficient conditions under which the conditional and unconditional risks are
asymptotically equivalent.

######  Corollary 4.

Consider the regularity conditions in Proposition 6 on data-generating
distributions and loss function. If we further assume that

  1. (i)

The worst-case risk function
$\sup_{\widehat{\theta},\theta}\mathbb{E}\\{\mathcal{L}^{2}(\widehat{\theta},\theta)\\}$
is bounded above by some positive constant.

  2. (ii)

The ratio of the minimax (conditional) risks satisfies

$\displaystyle\frac{\inf_{\widehat{\theta}}\sup_{\theta}\mathbb{E}\\{\mathcal{L}(\widehat{\theta},\theta)\,|\,N=\lfloor
n\\{1+o(1)\\}\rfloor\\}}{\inf_{\widehat{\theta}}\sup_{\theta}\mathbb{E}\\{\mathcal{L}(\widehat{\theta},\theta)\,|\,N=n\\}}=1+o(1).$

  3. (iii)

Neither conditional nor unconditional minimax risks converge at a rate faster
than exponential.

Then the conditional minimax risk and unconditional minimax risk are
asymptotically equivalent as

$\displaystyle\frac{\inf_{\widehat{\theta}}\sup_{\theta}\mathbb{E}\\{\mathcal{L}(\widehat{\theta},\theta)\\}}{\inf_{\widehat{\theta}}\sup_{\theta}\mathbb{E}\\{\mathcal{L}(\widehat{\theta},\theta)\,|\,N=n\\}}=1+o(1).$

As we mentioned earlier, the bounded condition (i) is not entirely avoidable
in view of Example 3. Condition (ii) requires that the conditional minimax
risk is asymptotically continuous as a function of $N$. Alternatively, this
condition (ii) can be replaced by a condition on the unconditional minimax
risk. Specifically, if we consider
$\inf_{\widehat{\theta}}\sup_{\theta}\mathbb{E}\\{\mathcal{L}(\widehat{\theta},\theta)\\}=h(\varrho)$
as a function of the parameter $\varrho$ for the missing indicator, condition
(ii) can be replaced with $h(\varrho_{1,n})/h(\varrho_{2,n})=1+o(1)$ whenever
$\varrho_{1,n}/\varrho_{2,n}=1+o(1)$. The last condition (iii) concerning the
convergence rate is mild and it is expected to be satisfied for almost all
practical problems.

The asymptotic equivalence established in Corollary 4 allows us to apply the
LAM theorem to investigate the minimax risk under fixed-$N$ sampling. However,
in the argument of the LAM theorem, the positivity of $\varrho$ is critical
and it would take non-trivial effort to extend the result to incorporate a
triangular array of distributions with varying $\varrho$. Therefore a direct
translation from random-$N$ sampling to fixed-$N$ sampling yields a lower
bound result limited to certain asymptotic regimes. In contrast, we take a
direct approach to derive the lower bound results in the main text,
specifically utilizing the van Trees inequality, and we avoid imposing an
unnecessary restriction on $\varrho$.

###  A.4 Minimax Lower Bound for Mean Estimation

In this subsection, we briefly revisit the lower bound result for mean
estimation in Zhang et al., (2019, Proposition 3), and provide an alternative
proof in Section D.4 through the van Trees inequality. We reprove this result
merely to illustrate the versatility of the van Trees inequality in
establishing minimax lower bounds under semi-supervised settings.

######  Proposition 7 (Zhang et al., 2019, Proposition 3).

Consider the mean estimation problem with $\psi=\mathbb{E}(Y)$. Let
$\sigma_{X}^{2}$ and $\sigma_{\varepsilon}^{2}$ be some fixed positive
numbers. Then for the class of distributions

$\displaystyle\mathcal{P}_{\mathsf{mean}}=\big{\\{}P_{XY}:Y=X+\varepsilon,\,X\sim
N(\delta,\sigma_{X}^{2}),\,\varepsilon\sim N(c,\sigma_{\varepsilon}^{2})\
\text{where $X$ and $\varepsilon$ are independent}\big{\\}},$

the minimax risk is lower bounded by

$\displaystyle\inf_{\widehat{\psi}}\sup_{P\in\mathcal{P}_{\mathsf{mean}}}n\mathbb{E}_{P}\bigl{\\{}(\widehat{\psi}-\psi_{P})^{2}\bigr{\\}}\geq\sigma_{\varepsilon}^{2}+\frac{n}{n+m}\sigma_{X}^{2}.$

Moreover, it holds that
$\sigma_{\varepsilon}^{2}=\mathbb{E}_{P}\\{\mathrm{Var}_{P}(Y\,|\,X)\\}$ and
$\sigma_{X}^{2}=\mathrm{Var}_{P}\\{\mathbb{E}_{P}(Y\,|\,X)\\}$ for any
$P\in\mathcal{P}_{\mathsf{mean}}$.

We note that Zhang et al., (2019, Proposition 3) considers a larger class of
distributions than $\mathcal{P}_{\mathsf{mean}}$ but their main argument
revolves around the distributions in $\mathcal{P}_{\mathsf{mean}}$. Zhang et
al., (2019) prove Proposition 7 using the well-known fact that a Bayes
estimator with constant risk is minimax. In their construction, the key is to
express the target parameter $\psi$ as a function of other two parameters,
namely $\delta$ and $c$, and consider a scenario where the unlabeled data
provide additional information of $\delta$ but not $c$. This construction
allows us to obtain the second term in the lower bound, which tends to zero as
the size of unlabeled data $m$ increases. We build on their construction and
show the same result based on the van Trees inequality in Section D.4.

##  Appendix B Technical Lemmas

This section collects several technical lemmas. The first result displayed
below is known as Stone’s theorem, which states conditions which guarantee the
consistency of a linear smoother in terms of the MSPE. Given i.i.d. random
vectors $\\{(X_{i},Y_{i})\\}_{i=1}^{n}$, a linear smoother estimator of
$\mathbb{E}(Y\,|\,X)$ has the form of

$\displaystyle\widehat{\mathbb{E}}(Y\,|\,X=x)=\sum_{i=1}^{n}w_{i}(x)Y_{i},$
(12)

where $w_{i}(x)\in\mathbb{R}$ are weights depending only on
$X_{1},\ldots,X_{n}$.

######  Lemma 3 (Györfi et al., 2002, Theorem 4.1).

Assume the following conditions are satisfied for any distribution of $X$:

  1. (i)

There is a constant $c$ such that for every non-negative measurable function
$f$ satisfying $\mathbb{E}[f(X)]<\infty$ and any $n$,

$\displaystyle\mathbb{E}\Bigg{[}\sum_{i=1}^{n}|w_{i}(X)|f(X_{i})\Bigg{]}\leq
c\mathbb{E}[f(X)].$

  2. (ii)

There is a $D\geq 1$ such that for all $n$

$\displaystyle\mathbb{P}\Bigg{[}\sum_{i=1}^{n}|w_{i}(X)|\leq D\Bigg{]}=1.$

  3. (iii)

For all $a>0$,

$\displaystyle\lim_{n\rightarrow\infty}\mathbb{E}\Bigg{[}\sum_{i=1}^{n}|w_{i}(X)|\mathds{1}(\|X_{i}-X\|>a)\Bigg{]}=0.$

  4. (iv)

As $n\rightarrow\infty$,

$\displaystyle\sum_{i=1}^{n}w_{i}(X)\overset{p}{\longrightarrow}1\quad\text{and}\quad\lim_{n\rightarrow\infty}\mathbb{E}\Bigg{[}\sum_{i=1}^{n}w_{i}^{2}(X)\Bigg{]}=0.$

Then for all distributions of $(X,Y)$ with $\mathbb{E}(Y^{2})<\infty$, the
corresponding linear smoother $\widehat{\mathbb{E}}(Y\,|\,X)$ in (12)
satisfies

$\displaystyle\lim_{n\rightarrow\infty}\mathbb{E}\bigl{[}\big{\\{}\widehat{\mathbb{E}}(Y\,|\,X)-\mathbb{E}(Y\,|\,X)\big{\\}}^{2}\bigr{]}=0.$

The following (non-asymptotic Slutsky’s theorem) is well-known (e.g., Bentkus
et al.,, 2009). We provide a proof for completeness.

######  Lemma 4.

For $T=L+\Delta$, $Z\sim N(0,1)$ and $p>0$, we have

$\displaystyle\sup_{x\in\mathbb{R}}\big{|}\mathbb{P}(T\leq x)-\mathbb{P}(Z\leq
x)\big{|}\leq\sup_{x\in\mathbb{R}}\big{|}\mathbb{P}(L\leq x)-\mathbb{P}(Z\leq
x)\big{|}+2p^{\frac{1}{p+1}}\left(\\!\frac{1}{\sqrt{2\pi}}\\!\right)^{\frac{p}{p+1}}\bigl{(}\mathbb{E}[|\Delta|^{p}]\bigr{)}^{\frac{1}{p+1}}.$

###### Proof.

For any $\epsilon>0$, note that

$\displaystyle\mathbb{P}(L+\Delta\leq t)=\mathbb{P}(L+\Delta\leq t,\
|\Delta|\leq\epsilon)+\mathbb{P}(L+\Delta\leq t,\ |\Delta|>\epsilon).$

Thus the triangle inequality gives

$\displaystyle\sup_{x\in\mathbb{R}}\big{|}\mathbb{P}(T\leq x)-\mathbb{P}(Z\leq
x)\big{|}$ $\displaystyle\leq~{}$
$\displaystyle\max\biggl{\\{}\sup_{x\in\mathbb{R}}\big{|}\mathbb{P}(L\leq
x-\epsilon)-\mathbb{P}(Z\leq x)\big{|},\
\sup_{x\in\mathbb{R}}\big{|}\mathbb{P}(L\leq x+\epsilon)-\mathbb{P}(Z\leq
x)\big{|}\bigg{\\}}+\mathbb{P}(|\Delta|^{p}>\epsilon^{p}).$

By applying the triangle inequality again and using the Lipschitz property of
$\mathbb{P}(Z\leq x)$,

$\displaystyle\max\biggl{\\{}\sup_{x\in\mathbb{R}}\big{|}\mathbb{P}(L\leq
x-\epsilon)-\mathbb{P}(Z\leq x)\big{|},\
\sup_{x\in\mathbb{R}}\big{|}\mathbb{P}(L\leq x+\epsilon)-\mathbb{P}(Z\leq
x)\big{|}\bigg{\\}}$ $\displaystyle\leq~{}$
$\displaystyle\sup_{x\in\mathbb{R}}\big{|}\mathbb{P}(L\leq x)-\mathbb{P}(Z\leq
x)\big{|}+\epsilon\sup_{x\in\mathbb{R}}\phi(x),$

where $\phi$ is the probability density function of $N(0,1)$. On the other
hand, Markov’s inequality gives
$\mathbb{P}(|\Delta|^{p}>\epsilon^{p})\leq\epsilon^{-p}\mathbb{E}[|\Delta|^{p}]$.
Therefore

$\displaystyle\sup_{x\in\mathbb{R}}\big{|}\mathbb{P}(T\leq x)-\mathbb{P}(Z\leq
x)\big{|}\leq\sup_{x\in\mathbb{R}}\big{|}\mathbb{P}(L\leq x)-\mathbb{P}(Z\leq
x)\big{|}+\epsilon\sup_{x\in\mathbb{R}}\phi(x)+\epsilon^{-p}\mathbb{E}[|\Delta|^{p}].$

Optimizing the right-hand side over $\epsilon>0$ yields the desired result. ∎

The following lemma due to Esseen, (1942) presents a Berry–Esseen bound for
non-identically distributed summands.

######  Lemma 5.

Let $X_{1},\ldots,X_{n}$ be independent random variables with
$\mathbb{E}(X_{i})=0$, $\mathbb{E}(X_{i}^{2})=\sigma_{i}^{2}>0$ and
$\mathbb{E}(|X_{i}|^{3})=\rho_{i}<\infty$. Denote the standardized sum of
$X_{i}$s as

$\displaystyle
S_{n}=\frac{\sum_{i=1}^{n}X_{i}}{\sqrt{\sum_{i=1}^{n}\sigma_{i}^{2}}}.$

Then there exists an absolute constant $C>0$ such that

$\displaystyle\sup_{t\in\mathbb{R}}|\mathbb{P}(S_{n}\leq t)-\Phi(t)|\leq
C\biggl{(}\sum_{i=1}^{n}\sigma_{i}^{2}\biggr{)}^{-3/2}\sum_{i=1}^{n}\rho_{i}\quad\text{for
all $n$.}$

######  Lemma 6 (Yaskov, 2014, Corollary 3.4).

Let $X_{1},\ldots,X_{n}\in\mathbb{R}^{d}$ be i.i.d. random vectors with
$\mathbb{E}(X)=0$ and $\mathrm{Var}(X)=\bm{I}_{d}$. Define
$K_{d}=\inf_{v\in\mathbb{R}^{d}:\|v\|_{2}=1}\mathbb{E}|X^{\top}v|$. Let
$\widehat{\Sigma}=\frac{1}{n}\sum_{i=1}^{n}X_{i}X_{i}^{\top}$. Then there are
universal constants $C_{0},C_{1},C_{2}>0$ such that with probability at least
$1-\exp\\{-C_{1}K_{d}^{4}n\\}$,

$\displaystyle\lambda_{\mathrm{min}}(\widehat{\Sigma})\geq C_{0}K_{d}^{2},$

when $d/n\leq C_{2}K_{d}^{2}$.

######  Lemma 7.

Consider $n$ i.i.d. pairs $(X_{i},Y_{i})$ drawn from $P_{XY}$ and partition
the support of $X$ into $K$ disjoint bins $B_{1},\ldots,B_{K}$. Let $X$ be
drawn from the marginal distribution $P_{X}$, independent of
$\\{(X_{i},Y_{i})\\}_{i=1}^{n}$. Then the absolute third moment of the
histogram estimator $\mathbb{E}[|\widehat{f}(X)|^{3}]$ where

$\displaystyle\widehat{f}(x)=\frac{\sum_{i=1}^{n}\mathds{1}(X_{i}\in
B_{k})Y_{i}}{\sum_{j=1}^{n}\mathds{1}(X_{j}\in B_{k})}\mathds{1}(x\in B_{k})$

is less than or equal to $\mathbb{E}[|Y|^{3}]$.

###### Proof.

Notice that

$\displaystyle\mathbb{E}\bigl{[}|\widehat{f}(X)|^{3}\,|\,X\in
B_{k}\bigr{]}~{}\overset{\mathrm{(i)}}{\leq}~{}$
$\displaystyle\mathbb{E}\biggl{[}\frac{\sum_{i=1}^{n}\mathds{1}(X_{i}\in
B_{k})|Y_{i}|^{3}}{\sum_{i=1}^{n}\mathds{1}(X_{i}\in B_{k})}\biggm{|}X\in
B_{k}\biggr{]}$ $\displaystyle\overset{\mathrm{(ii)}}{=}~{}$
$\displaystyle\mathbb{E}\biggl{[}\frac{\sum_{i=1}^{n}\mathds{1}(X_{i}\in
B_{k})\mathbb{E}\bigl{[}|Y_{i}|^{3}\,|\,X_{i}\in
B_{k}\bigr{]}}{\sum_{i=1}^{n}\mathds{1}(X_{i}\in B_{k})}\biggm{|}X\in
B_{k}\biggr{]}$ $\displaystyle\overset{\mathrm{(iii)}}{=}~{}$
$\displaystyle\mathbb{E}\biggl{[}\mathbb{E}\bigl{[}|Y_{1}|^{3}\,|\,X_{1}\in
B_{k}\bigr{]}\frac{\sum_{i=1}^{n}\mathds{1}(X_{i}\in
B_{k})}{\sum_{i=1}^{n}\mathds{1}(X_{i}\in B_{k})}\biggm{|}X\in B_{k}\biggr{]}$
$\displaystyle=~{}$
$\displaystyle\mathbb{E}\biggl{[}\mathbb{E}\bigl{[}|Y_{1}|^{3}\,|\,X_{1}\in
B_{k}\bigr{]}\frac{\sum_{i=1}^{n}\mathds{1}(X_{i}\in
B_{k})}{\sum_{i=1}^{n}\mathds{1}(X_{i}\in B_{k})}\biggr{]}$
$\displaystyle=~{}$ $\displaystyle\mathbb{E}\bigl{[}|Y_{1}|^{3}\,|\,X_{1}\in
B_{k}\bigr{]},$

where step (i) uses Jensen’s inequality, step (ii) uses the law of total
expectation, step (iii) holds since $\mathbb{E}[|Y_{1}|^{3}\,|\,X_{1}\in
B_{k}]=\cdots=\mathbb{E}[|Y_{n}|^{3}\,|\,X_{n}\in B_{k}]$. Using this
preliminary result together with the law of total expectation yields

$\displaystyle\mathbb{E}\bigl{[}|\widehat{f}(X)|^{3}\bigr{]}=$
$\displaystyle\sum_{k=1}^{K}\mathbb{E}\bigl{[}|\widehat{f}(X)|^{3}\,|\,X\in
B_{k}\bigr{]}\mathbb{P}(X\in B_{k})$ $\displaystyle\leq$
$\displaystyle\sum_{k=1}^{K}\mathbb{E}\bigl{[}|Y_{1}|^{3}\,|\,X_{1}\in
B_{k}\bigr{]}\mathbb{P}(X_{1}\in B_{k})=\mathbb{E}[|Y|^{3}].$

∎

The following lemma is useful in establishing the asymptotic equivalence in
Proposition 6.

######  Lemma 8 (Chernoff Tail Bounds for Binomial).

Let $Z$ follow a Binomial distribution with parameters $(n,p)$ and denote
$\mu=np$. Then for any $\rho\in(0,1)$,

  * •

Lower tail bound: $\mathbb{P}\\{Z\leq(1-\rho)\mu\\}\leq
e^{-\frac{\mu\rho^{2}}{2}}$ for any $\rho\in(0,1)$.

  * •

Upper tail bound: $\mathbb{P}\\{Z\geq(1+\rho)\mu\\}\leq
e^{-\frac{\min\\{\rho,\rho^{2}\\}\mu}{4}}$ for any $\rho\geq 0$.

###### Proof.

See, e.g., Mulzer, (2018). ∎

##  Appendix C Proofs of Main Results

This section collects the proofs of the results in the main text.

###  C.1 Proof of Theorem 1

We start by proving the asymptotic Normality result, and then proceed to
establish the convergence result in terms of the MSPE.

##### Claim 1: Asymptotic Normality.

Given a fixed function $f$, we denote the semi-supervised U-statistic using
$f$ as

$\displaystyle
U_{f}=U-\frac{r}{n}\sum_{i=1}^{n}f(X_{i})+\frac{r}{n+m}\sum_{i=1}^{n+m}f(X_{i}).$

In _Part 1_ of this proof, we show under the conditions of Theorem 1 that

$\displaystyle\frac{\sqrt{n}(U_{f}-\psi)}{\sqrt{\smash[b]{\Lambda_{n,m,f}}}}\overset{d}{\longrightarrow}N(0,1),$
(13)

and then in _Part 2_ we leverage this result to prove the claim for
$U_{\mathrm{cross}}$.

_Part 1. Asymptotic Normality of $U_{f}$._ Since $U_{f}$ remains invariant to
a location-shift of $f$, we will assume that $\mathbb{E}[f(X)]=\psi$ without
loss of generality. By the Hoeffding decomposition, the semi-supervised
U-statistic $U_{f}$ can be written as

$\displaystyle
U_{f}=\underbrace{\psi+\frac{r}{n}\sum_{i=1}^{n}\\{\ell_{1}(Y_{i})-f(X_{i})\\}+\frac{r}{n+m}\sum_{i=1}^{n+m}\\{f(X_{i})-\psi\\}}_{:=L_{f}}+R,$

where the remainder term $R$ satisfies $\mathbb{E}[R]=0$ and
$\mathrm{Var}[R]=O(n^{-2})$ by Lee, (1990, Theorem 2 and Theorem 4 of Section
1.6). Therefore, by Chebyshev’s inequality, we have the relationship
$U_{f}=L_{f}+o_{P}(n^{-1/2})$. Given this asymptotic equivalence, once we
prove

$\displaystyle\frac{\sqrt{n}(L_{f}-\psi)}{\sqrt{\smash[b]{\Lambda_{n,m,f}}}}\overset{d}{\longrightarrow}N(0,1)\quad\text{as
$n\rightarrow\infty$,}$ (14)

the first claim on asymptotic Normality follows by Slutsky’s theorem. We note
that $L_{f}-\psi$ can be written as the sum of independent random variables
$L_{f}-\psi=\sum_{i=1}^{n+m}Z_{i}$ where

$\displaystyle
Z_{i}=\begin{cases}\frac{r}{n}\\{\ell_{1}(Y_{i})-f(X_{i})\\}+\frac{r}{n+m}\\{f(X_{i})-\psi\\}&\text{for
$1\leq i\leq n$},\\\\[5.0pt] \frac{r}{n+m}\\{f(X_{i})-\psi\\}&\text{for
$n+1\leq i\leq n+m$.}\end{cases}$

We remark that $Z_{i}$ are not identically distributed, which makes the
conventional central limit theorem for i.i.d. summands not applicable.
Instead, we leverage Lindeberg’s central limit theorem for triangular arrays.
Since we assume $\mathbb{E}[f(X)]=\psi$, it can be seen by the law of total
expectation that each $Z_{i}$ is centered at zero, and by letting
$A:=\ell_{1}(Y)-f(X)$ and $B:=f(X)-\psi$

$\displaystyle\mathrm{Var}(Z_{i})=\begin{cases}\frac{r^{2}}{n^{2}}\mathbb{E}[A^{2}]+\frac{r^{2}}{(n+m)^{2}}\mathbb{E}[B^{2}]+\frac{2r^{2}}{n(n+m)}\mathbb{E}[AB]&\text{for
$1\leq i\leq n$},\\\\[5.0pt]
\frac{r^{2}}{(n+m)^{2}}\mathbb{E}[B^{2}]&\text{for $n+1\leq i\leq
n+m$.}\end{cases}$

Defining

$\displaystyle s^{2}:=$
$\displaystyle\sum_{i=1}^{n+m}\mathrm{Var}(Z_{i})=\frac{r^{2}}{n}\mathbb{E}[A^{2}]+\frac{r^{2}}{n+m}\mathbb{E}[B^{2}]+\frac{2r^{2}}{n+m}\mathbb{E}[AB],$

the asymptotic Normality (14) holds if Lindeberg’s condition is fulfilled,
i.e., for any fixed $\epsilon>0$,

$\displaystyle\lim_{n\rightarrow\infty}\frac{1}{s^{2}}\sum_{i=1}^{n+m}\mathbb{E}\bigl{[}Z_{i}^{2}\mathds{1}(|Z_{i}|>\epsilon
s)\bigr{]}$ $\displaystyle=~{}$
$\displaystyle\lim_{n\rightarrow\infty}\biggl{\\{}\frac{n}{s^{2}}\mathbb{E}\bigl{[}Z_{1}^{2}\mathds{1}(|Z_{1}|>\epsilon
s)\bigr{]}+\frac{m}{s^{2}}\mathbb{E}\bigl{[}Z_{n+1}^{2}\mathds{1}(|Z_{n+1}|>\epsilon
s)\bigr{]}\biggr{\\}}=0.$

First of all, the finite second moment condition for $\ell$ and $f$ yields

$\displaystyle\mathbb{E}[n^{2}Z_{1}^{2}\mathds{1}(|Z_{1}|>\epsilon
s)]\leq\mathbb{E}[n^{2}Z_{1}^{2}]\leq
r^{2}(\mathbb{E}[A^{2}]+\mathbb{E}[B^{2}]+2|\mathbb{E}[AB]|)<\infty,$

and $n^{2}Z_{1}^{2}\mathds{1}(|Z_{1}|>\epsilon s)$ converges to zero almost
surely as $n\rightarrow\infty$ for any fixed $\epsilon$. Moreover, it can be
seen that

$\displaystyle ns^{2}=\Lambda_{n,m,f}\geq
r^{2}\mathbb{E}[\mathrm{Var}\\{\ell_{1}(Y)\,|\,X\\}]+\frac{r^{2}n}{n+m}\mathrm{Var}[\mathbb{E}\\{\ell_{1}(Y)\,|\,X\\}],$

where the inequality holds by Lemma 2. Since we assume
$\mathbb{E}[\mathrm{Var}\\{\ell_{1}(Y)\,|\,X\\}]>0$, it follows that

$\displaystyle\lim_{n\rightarrow\infty}ns^{2}>0.$ (15)

Therefore, the dominated convergence theorem ensures that

$\displaystyle\lim_{n\rightarrow\infty}\frac{n}{s^{2}}\mathbb{E}\bigl{[}Z_{1}^{2}\mathds{1}(|Z_{1}|>\epsilon
s)\bigr{]}=0.$

A similar argument shows that

$\displaystyle\mathbb{E}\bigl{[}mnZ_{n+1}^{2}\mathds{1}(|Z_{n+1}|>\epsilon
s)\bigr{]}\leq r^{2}\mathbb{E}[B^{2}]<\infty$

and $mnZ_{n+1}^{2}\mathds{1}(Z_{n+1}|>\epsilon s)$ converges to zero almost
surely as $n\rightarrow\infty$ for any fixed $\epsilon>0$. Hence, again, the
dominated convergence theorem along with (15) shows that

$\displaystyle\lim_{n\rightarrow\infty}\frac{m}{s^{2}}\mathbb{E}\bigl{[}Z_{n+1}^{2}\mathds{1}(|Z_{n+1}|>\epsilon
s)\bigr{]}=0.$

Consequently, Lindeberg’s condition holds and this proves the claim (13).

_Part 2. Asymptotic Normality of $U_{\mathrm{cross}}$._ Given the result (13),
the asymptotic Normality of $U_{\mathrm{cross}}$ follows by Slutsky’s theorem
once we prove

$\displaystyle\mathbb{E}[(U_{\mathrm{cross}}-U_{f})^{2}]=o(n^{-1}).$ (16)

Let $n_{0}=\lfloor n/2\rfloor$ and $m_{0}=\lfloor m/2\rfloor$. Then by the
definition of $\widehat{f}_{\mathrm{cross}}$, the difference between
$U_{\mathrm{cross}}$ and $U_{f}$ can be expressed as

$\displaystyle U_{\mathrm{cross}}-U_{f}$ $\displaystyle=~{}$
$\displaystyle\frac{r}{n}\sum_{i=1}^{n}\\{f(X_{i})-\widehat{f}_{\mathrm{cross}}(X_{i})\\}-\frac{r}{n+m}\sum_{i=1}^{n+m}\\{f(X_{i})-\widehat{f}_{\mathrm{cross}}(X_{i})\\}$
$\displaystyle=~{}$
$\displaystyle\underbrace{\frac{r}{n}\sum_{i=1}^{n_{0}}\\{f(X_{i})-\widehat{f}_{1}(X_{i})\\}-\frac{r}{n+m}\sum_{i=1}^{n_{0}}\\{f(X_{i})-\widehat{f}_{1}(X_{i})\\}-\frac{r}{n+m}\sum_{i=n+1}^{n+m_{0}}\\{f(X_{i})-\widehat{f}_{1}(X_{i})\\}}_{\mathrm{(I)}}$
$\displaystyle+~{}$
$\displaystyle\underbrace{\frac{r}{n}\sum_{i=n_{0}+1}^{n}\\{f(X_{i})-\widehat{f}_{2}(X_{i})\\}-\frac{r}{n+m}\sum_{i=n_{0}+1}^{n}\\{f(X_{i})-\widehat{f}_{2}(X_{i})\\}-\frac{r}{n+m}\sum_{i=n+m_{0}+1}^{n+m}\\{f(X_{i})-\widehat{f}_{2}(X_{i})\\}}_{\mathrm{(II)}}.$

As $\mathbb{E}[(U_{\mathrm{cross}}-U_{f})^{2}]\leq
2\mathbb{E}[(\mathrm{I})^{2}]+2\mathbb{E}[(\mathrm{II})^{2}]$, and due to the
symmetry between (I) and (II), it suffices to prove that
$\mathbb{E}[\mathrm{(I)}^{2}]=o(n^{-1})$. Writing
$\mathbb{E}[f(X)-\widehat{f}_{1}(X)\,|\,\widehat{f}_{1}]=\Delta_{\widehat{f}_{1}}$,
we can express the term (I) as

$\displaystyle\mathrm{(I)}~{}=~{}$
$\displaystyle\underbrace{\frac{r}{n}\sum_{i=1}^{n_{0}}\\{f(X_{i})-\widehat{f}_{1}(X_{i})-\Delta_{\widehat{f}_{1}}\\}}_{:=\mathrm{(I)}_{1}}-\underbrace{\frac{r}{n+m}\sum_{i=1}^{n_{0}}\\{f(X_{i})-\widehat{f}_{1}(X_{i})-\Delta_{\widehat{f}_{1}}\\}}_{:=\mathrm{(I)}_{2}}$
$\displaystyle-\underbrace{\frac{r}{n+m}\sum_{i=n+1}^{n+m_{0}}\\{f(X_{i})-\widehat{f}_{1}(X_{i})-\Delta_{\widehat{f}_{1}}\\}}_{:=\mathrm{(I)}_{3}}+a_{n,m}\Delta_{\widehat{f}_{1}},$

where

$\displaystyle a_{n,m}=\frac{r(\lfloor n/2\rfloor m-n\lfloor
m/2\rfloor)}{n(n+m)}.$

Then by the elementary inequality: $(x_{1}+x_{2}+x_{3}+x_{4})^{2}\leq
4(x_{1}^{2}+x_{2}^{2}+x_{3}^{2}+x_{4}^{2})$,

$\displaystyle\mathbb{E}[\mathrm{(I)}^{2}]\leq
4\mathbb{E}[(\mathrm{I})_{1}^{2}]+4\mathbb{E}[(\mathrm{I})_{2}^{2}]+4\mathbb{E}[(\mathrm{I})_{3}^{2}]+4\mathbb{E}[\Delta_{\widehat{f}_{1}}^{2}]a_{n,m}^{2},$

and by the law of expectation, and the (conditional) independence between
summands,

$\displaystyle\mathbb{E}[(\mathrm{I})_{1}^{2}]=\frac{r^{2}n_{0}}{n^{2}}\mathbb{E}\bigl{[}\mathrm{Var}\\{f(X)-\widehat{f}_{1}(X)\,|\,\widehat{f}_{1}\\}\bigr{]}\leq\frac{r^{2}n_{0}}{n^{2}}\mathbb{E}\bigl{[}\\{f(X)-\widehat{f}_{1}(X)\\}^{2}\bigr{]}=o(n^{-1}).$

Similarly, the other terms satisfy that
$\mathbb{E}[(\mathrm{I})_{2}^{2}]=o(n^{-1})$ and
$\mathbb{E}[(\mathrm{I})_{3}^{2}]=o(n^{-1})$. Lastly, it holds that
$a_{n,m}^{2}=O(n^{-2})$ for any integers $n,m$, and so
$\mathbb{E}[\mathrm{(I)}^{2}]=o(n^{-1})$, which again proves the claim (16).

##### Claim 2: Convergence of MSE.

For the second claim, we write $U_{f}-\psi:=H_{f}+R$ where

$\displaystyle
H_{f}=\frac{r}{n}\sum_{i=1}^{n}\\{\ell_{1}(Y_{i})-f(X_{i})\\}+\frac{r}{n+m}\sum_{i=1}^{n+m}\\{f(X_{i})-\psi\\}.$

Noting that $\mathbb{E}[H_{f}]=0$ and
$\mathrm{Var}[H_{f}]=n^{-1}\Lambda_{n,m,f}$, we have the identity that

$\displaystyle\frac{\mathbb{E}\bigl{[}\bigl{(}U_{f}-\psi\bigr{)}^{2}\bigr{]}}{n^{-1}\Lambda_{n,m,f}}=1+\frac{2\mathbb{E}[H_{f}R]}{n^{-1}\Lambda_{n,m,f}}+\frac{\mathbb{E}[R^{2}]}{n^{-1}\Lambda_{n,m,f}}.$
(17)

As mentioned earlier, $R$ satisfies $\mathbb{E}[R]=0$ and
$\mathrm{Var}[R]=O(n^{-2})$ by Lee, (1990, Theorem 2 and Theorem 4 of Section
1.6). Hence the last term in the above display converges to zero. Similarly
the Cauchy–Schwarz inequality yields that the second term fulfills

$\displaystyle\frac{2|\mathbb{E}[H_{f}R]|}{n^{-1}\Lambda_{n,m,f}}\leq
2\sqrt{\frac{\mathbb{E}[H_{f}^{2}]}{n^{-1}\Lambda_{n,m,f}}}\sqrt{\frac{\mathbb{E}[R^{2}]}{n^{-1}\Lambda_{n,m,f}}}=2\sqrt{\frac{\mathbb{E}[R^{2}]}{n^{-1}\Lambda_{n,m,f}}}=o(1).$

As a result, the ratio (17) converges to one as $n\rightarrow\infty$.
Furthermore, given the following decomposition:

$\displaystyle\frac{\mathbb{E}\bigl{[}\bigl{(}U_{\mathrm{cross}}-\psi\bigr{)}^{2}\bigr{]}}{n^{-1}\Lambda_{n,m,f}}~{}=~{}$
$\displaystyle\frac{\mathbb{E}\bigl{[}\bigl{(}U_{\mathrm{cross}}-U_{f}+U_{f}-\psi\bigr{)}^{2}\bigr{]}}{n^{-1}\Lambda_{n,m,f}}$
$\displaystyle=~{}$
$\displaystyle\frac{\mathbb{E}\bigl{[}\bigl{(}U_{f}-U_{\mathrm{cross}}\bigr{)}^{2}\bigr{]}}{n^{-1}\Lambda_{n,m,f}}+\frac{\mathbb{E}\bigl{[}\bigl{(}U_{f}-\psi\bigr{)}^{2}\bigr{]}}{n^{-1}\Lambda_{n,m,f}}+\frac{2\mathbb{E}\bigl{[}\bigl{(}U_{\mathrm{cross}}-U_{f}\bigr{)}\bigl{(}U_{f}-\psi\bigr{)}\bigr{]}}{n^{-1}\Lambda_{n,m,f}},$

the second claim in Theorem 1 follows once we show

$\displaystyle\frac{\mathbb{E}\bigl{[}\bigl{(}U_{f}-U_{\mathrm{cross}}\bigr{)}^{2}\bigr{]}}{n^{-1}\Lambda_{n,m,f}}=o(1).$

Remark that we already proved in (16) that
$\mathbb{E}[(U_{\mathrm{cross}}-U_{f})^{2}]=o(n^{-1})$, and
$\Lambda_{n,m,f}\geq r^{2}\mathbb{E}[\mathrm{Var}\\{\ell_{1}(Y)\,|\,X\\}]>0$.
Therefore the above claim follows, and the third term in the decomposition is
also $o(1)$, which can be verified by the Cauchy–Schwarz inequality. This
completes the proof of Theorem 1.

###  C.2 Proof of Lemma 2

Note that minimizing $\Lambda_{n,m,f}$ is equivalent to minimizing

$\displaystyle\mathrm{Var}[f(X)]-2\mathrm{Cov}[f(X),\psi_{1}(X)]=\mathrm{Var}[\psi_{1}(X)-f(X)]-\mathrm{Var}[\psi_{1}(X)].$

As the variance is non-negative, this expression is lower bounded by
$-\mathrm{Var}[\psi_{1}(X)]$, which can be achieved when $\psi_{1}=f$. Hence
the result follows.

###  C.3 Proof of Proposition 1

To prove the claim, we upper bound the MSPE using condition (i) and applying
the inequality $(x+y)^{2}\leq 2x^{2}+2y^{2}$ twice as

$\displaystyle\mathbb{E}[\\{\widehat{\mathbb{E}}[\widehat{\ell}_{1}(Y)\,|\,X]-\mathbb{E}[\ell_{1}(Y)\,|\,X]\\}^{2}]$
$\displaystyle=~{}$
$\displaystyle\mathbb{E}[\\{\widehat{\mathbb{E}}[\widehat{\ell}_{1}(Y)-\ell_{1}(Y)\,|\,X]+\widehat{\mathbb{E}}[\ell_{1}(Y)\,|\,X]+R-\mathbb{E}[\ell_{1}(Y)\,|\,X]\\}^{2}]$
$\displaystyle\leq~{}$ $\displaystyle
2\mathbb{E}[\\{\widehat{\mathbb{E}}[\widehat{\ell}_{1}(Y)-\ell_{1}(Y)\,|\,X]\\}^{2}]+4\mathbb{E}[\\{\widehat{\mathbb{E}}[\ell_{1}(Y)\,|\,X]-\mathbb{E}[\ell_{1}(Y)\,|\,X]\\}^{2}]+4\mathbb{E}[R^{2}].$

The upper bound is $o(1)$ under conditions (i), (ii) and (iii), which
completes the proof of Proposition 1.

###  C.4 Proof of Proposition 2

For simplicity, assume that $n$ is even. For the linear smoother, condition
(ii) holds with $R=0$ as

$\displaystyle\widehat{\mathbb{E}}[\widehat{\ell}_{1}(Y)\,|\,X=x]~{}=~{}$
$\displaystyle\sum_{i=n/4+1}^{n/2}w_{i}(x)\widehat{\ell}_{1}(Y_{i})$
$\displaystyle=~{}$
$\displaystyle\sum_{i=n/4+1}^{n/2}w_{i}(x)\big{\\{}\widehat{\ell}_{1}(Y_{i})-\ell_{1}(Y_{i})\big{\\}}+\sum_{i=n/4+1}^{n/2}w_{i}(x)\widehat{\ell}_{1}(Y_{i})$
$\displaystyle=~{}$
$\displaystyle\widehat{\mathbb{E}}[\widehat{\ell}_{1}(Y)-\ell_{1}(Y)\,|\,X=x]+\widehat{\mathbb{E}}[\ell_{1}(Y)\,|\,X=x].$

For condition (iii), writing the rescaled weight function as

$\displaystyle\widetilde{w}_{i}(X)=\frac{w_{i}(x)}{\sum_{j=1}^{n}w_{j}(x)},$

we can observe a series of inequalities:

$\displaystyle\mathbb{E}[\\{\widehat{\mathbb{E}}[\widehat{\ell}_{1}(Y)-\ell_{1}(Y)\,|\,X]\\}^{2}]~{}=~{}$
$\displaystyle\mathbb{E}\biggl{[}\bigg{(}\sum_{i=n/4+1}^{n/2}w_{i}(X)\bigl{\\{}\widehat{\ell}_{1}(Y_{i})-\ell_{1}(Y_{i})\bigr{\\}}\bigg{)}^{2}\biggr{]}$
$\displaystyle\overset{(\mathrm{i})}{\lesssim}~{}$
$\displaystyle\mathbb{E}\biggl{[}\bigg{(}\sum_{i=n/4+1}^{n/2}\widetilde{w}_{i}(X)\bigl{\\{}\widehat{\ell}_{1}(Y_{i})-\ell_{1}(Y_{i})\bigr{\\}}\bigg{)}^{2}\biggr{]}$
$\displaystyle\overset{(\mathrm{ii})}{\lesssim}~{}$
$\displaystyle\mathbb{E}\biggl{[}\sum_{i=n/4+1}^{n/2}\widetilde{w}_{i}(X)\bigl{\\{}\widehat{\ell}_{1}(Y_{i})-\ell_{1}(Y_{i})\bigr{\\}}^{2}\biggr{]},$

where step (i) uses the condition $\sum_{i=n/4+1}^{n/2}w_{i}(x)\leq C$ and
step (ii) holds by Jensen’s inequality. By the law of total expectation and
independence from sample splitting, the last expectation can be expressed as

$\displaystyle\mathbb{E}\biggl{[}\sum_{i=n/4+1}^{n/2}\widetilde{w}_{i}(X)\bigl{\\{}\widehat{\ell}_{1}(Y_{i})-\ell_{1}(Y_{i})\bigr{\\}}^{2}\biggr{]}~{}=~{}$
$\displaystyle\mathbb{E}\biggl{[}\sum_{i=n/4+1}^{n/2}\widetilde{w}_{i}(X)\mathbb{E}\Bigl{(}\bigl{\\{}\widehat{\ell}_{1}(Y_{i})-\ell_{1}(Y_{i})\bigr{\\}}^{2}\,|\,X_{i}\Bigr{)}\biggr{]}$
$\displaystyle\leq~{}$ $\displaystyle\mathbb{E}\biggl{[}\max_{n/4+1\leq i\leq
n/2}\mathbb{E}\Bigl{(}\bigl{\\{}\widehat{\ell}_{1}(Y_{i})-\ell_{1}(Y_{i})\bigr{\\}}^{2}\,|\,X_{i}\Bigr{)}\biggr{]}.$

Observe that $\widehat{\ell}_{1}(y)$ is a U-statistic of $\ell_{1}(y)$ with
the variance bounded above as

$\displaystyle\mathbb{E}\bigl{[}\bigl{\\{}\widehat{\ell}_{1}(y)-\ell_{1}(y)\bigr{\\}}^{2}\bigr{]}\lesssim\frac{1}{n}\mathbb{E}[\ell^{2}(y,Y_{1},\ldots,Y_{r-1})]:=\frac{g(y)}{n},$
(18)

which follows by Lee, (1990, Theorem 3 and Theorem 4 of Chapter 1). Moreover
noting that

$\displaystyle\mathbb{E}\bigl{[}|\mathbb{E}[g(Y)\,|\,X]|\bigr{]}\leq\mathbb{E}[g(Y)]=\mathbb{E}[\ell^{2}(Y_{1},\ldots,Y_{r})]<\infty,$

we have

$\displaystyle\mathbb{E}\biggl{[}\max_{n/4+1\leq i\leq
n/2}\mathbb{E}\Bigl{(}\bigl{\\{}\widehat{\ell}_{1}(Y_{i})-\ell_{1}(Y_{i})\bigr{\\}}^{2}\,|\,X_{i}\Bigr{)}\biggr{]}\lesssim
n^{-1}\mathbb{E}\Bigl{[}\max_{n/4+1\leq i\leq
n/2}\mathbb{E}[g(Y_{i})\,|\,X_{i}]\Bigr{]}=o(1),$

where the last equality makes use of the following result that if
$Z_{1},\ldots,Z_{n}$ are i.i.d. random variable with
$\mathbb{E}[|Z_{1}|]<\infty$, then $\mathbb{E}[\max_{1\leq i\leq
n}Z_{i}]=o(n)$ (Downey,, 1990). This implies
$\mathbb{E}[\\{\widehat{\mathbb{E}}[\widehat{\ell}_{1}(Y)-\ell_{1}(Y)\,|\,X]\\}^{2}]=o(1)$
as desired.

###  C.5 Proof of Theorem 2

Let us denote as $U_{f}$ the semi-supervised U-statistic using the target
assistant-function $f$. In view of the proof of Theorem 1, it suffices to
prove

$\displaystyle U_{\mathrm{plug}}-U_{f}=o_{P}(n^{-1/2}).$

This condition is met under (i) Donsker condition in Theorem 2, followed by
van der Vaart, (2000, Lemma 19.24). Therefore, we focus on (ii) stability
condition in Theorem 2 and prove the above asymptotic equivalence between
$U_{\mathrm{plug}}$ and $U_{f}$.

Letting $\mathbb{E}_{X_{i}}$ be the expectation with respect to $X_{i}$
conditional on everything else, we write $U_{\mathrm{plug}}-U_{f}$ as

$\displaystyle U_{\mathrm{plug}}-U_{f}~{}=~{}$
$\displaystyle\frac{r}{n}\sum_{i=1}^{n}\\{f(X_{i})-\widehat{f}(X_{i})\\}-\frac{r}{n+m}\sum_{i=1}^{n+m}\\{f(X_{i})-\widehat{f}(X_{i})\\}$
$\displaystyle=~{}$ $\displaystyle(\mathrm{I})+(\mathrm{II})+(\mathrm{III}),$

where

$\displaystyle(\mathrm{I}):=\frac{r}{n}\sum_{i=1}^{n}\\{f(X_{i})-\widehat{f}^{(-i)}(X_{i})+\mathbb{E}_{X_{i}}[\widehat{f}^{(-i)}(X_{i})]-\mathbb{E}[f(X)]\\}$
$\displaystyle\hskip
25.00003pt+\frac{r}{n}\sum_{i=1}^{n}\\{\widehat{f}^{(-i)}(X_{i})-\widehat{f}(X_{i})\\}+\frac{r}{n}\sum_{i=1}^{n}\\{\mathbb{E}_{X_{i}}[\widehat{f}(X_{i})]-\mathbb{E}_{X_{i}}[\widehat{f}^{(-i)}(X_{i})]\\},$
$\displaystyle(\mathrm{II}):=-\frac{r}{n+m}\sum_{i=1}^{n+m}\\{f(X_{i})-\widehat{f}^{(-i)}(X_{i})+\mathbb{E}_{X_{i}}[\widehat{f}^{(-i)}(X_{i})]-\mathbb{E}[f(X)]\\}$
$\displaystyle\hskip
25.00003pt-\frac{r}{n+m}\sum_{i=1}^{n+m}\\{\widehat{f}^{(-i)}(X_{i})-\widehat{f}(X_{i})\\}-\frac{r}{n+m}\sum_{i=1}^{n+m}\\{\mathbb{E}_{X_{i}}[\widehat{f}(X_{i})]-\mathbb{E}_{X_{i}}[\widehat{f}^{(-i)}(X_{i})]\\},$
$\displaystyle(\mathrm{III}):=-\frac{r}{n}\sum_{i=1}^{n}\mathbb{E}_{X_{i}}[\widehat{f}(X_{i})-\widehat{f}^{(-i)}(X_{i})]+\frac{r}{n+m}\sum_{i=1}^{n+m}\mathbb{E}_{X_{i}}[\widehat{f}(X_{i})-\widehat{f}^{(-i)}(X_{i})]$
$\displaystyle\hskip
25.00003pt+\frac{r}{n}\sum_{i=1}^{n}\mathbb{E}_{X_{i}}[\widehat{f}^{(-i)}(X_{i})]-\frac{r}{n+m}\sum_{i=1}^{n+m}\mathbb{E}_{X_{i}}[\widehat{f}^{(-i)}(X_{i})].$

Le us start by analyzing the first term
$(\mathrm{I}):=(\mathrm{I})_{a}+(\mathrm{I})_{b}+(\mathrm{I})_{c}$ where

$\displaystyle(\mathrm{I})_{a}:=\frac{r}{n}\sum_{i=1}^{n}\\{f(X_{i})-\widehat{f}^{(-i)}(X_{i})+\mathbb{E}_{X_{i}}[\widehat{f}^{(-i)}(X_{i})]-\mathbb{E}[f(X)]\\},$
$\displaystyle(\mathrm{I})_{b}:=\frac{r}{n}\sum_{i=1}^{n}\\{\widehat{f}^{(-i)}(X_{i})-\widehat{f}(X_{i})\\},$
$\displaystyle(\mathrm{I})_{c}:=\frac{r}{n}\sum_{i=1}^{n}\\{\mathbb{E}_{X_{i}}[\widehat{f}(X_{i})]-\mathbb{E}_{X_{i}}[\widehat{f}^{(-i)}(X_{i})]\\},$

and we see that both $(\mathrm{I})_{b}$ and $(\mathrm{I})_{c}$ satisfy

$\displaystyle\mathbb{E}[|(\mathrm{I})_{b}|]\leq r\max_{1\leq i\leq
n}\mathbb{E}\bigl{[}\big{|}\widehat{f}(X_{i})-\widehat{f}^{(-i)}(X_{i})\big{|}\bigr{]}\quad\text{and}$
$\displaystyle\mathbb{E}[|(\mathrm{I})_{c}|]\leq r\max_{1\leq i\leq
n}\mathbb{E}\bigl{[}\big{|}\widehat{f}(X_{i})-\widehat{f}^{(-i)}(X_{i})\big{|}\bigr{]}.$

For the term $(\mathrm{I})_{a}$, letting
$W_{i}:=f(X_{i})-\widehat{f}^{(-i)}(X_{i})+\mathbb{E}_{X_{i}}[\widehat{f}^{(-i)}(X_{i})]-\mathbb{E}[f(X)]$,
we have

$\displaystyle
n\mathbb{E}[\\{(\mathrm{I})_{a}\\}^{2}]=\frac{r^{2}}{n}\sum_{i=1}^{n}\mathbb{E}[W_{i}^{2}]+\frac{r^{2}}{n}\sum_{1\leq
i\neq j\leq n}\mathbb{E}[W_{i}W_{j}].$

Since $X_{i}$ is independent of $\widehat{f}^{(-i)}$, we observe that
$\mathbb{E}_{X_{i}}[\widehat{f}^{(-i)}(X_{i})]=\mathbb{E}_{X}[\widehat{f}^{(-i)}(X)]$,
which leads to

$\displaystyle\frac{r^{2}}{n}\sum_{i=1}^{n}\mathbb{E}[W_{i}^{2}]\lesssim\mathbb{E}[\\{\widehat{f}(X)-f(X)\\}^{2}]=o(1).$

Next, for $i\neq j$, we build on the proof idea of double centering in Chen et
al., (2022). In particular, define $W_{i}^{(-j)}$ and $W_{j}^{(-i)}$ similarly
as $W_{i}$ and $W_{j}$, respectively, by replacing $(X_{j},Y_{j})$ in $W_{i}$
and $(X_{i},Y_{i})$ in $W_{j}$ with their i.i.d. copies. Then we have
$\mathbb{E}_{X_{j}}[W_{j}W_{i}^{(-j)}]=0$ and thus the law of total
expectation yields $\mathbb{E}[W_{j}W_{i}^{(-j)}]=0$. Similarly, we have
$\mathbb{E}[W_{i}W_{j}^{(-i)}]=0$. This along with the Cauchy–Schwarz
inequality leads to

$\displaystyle|\mathbb{E}[W_{i}W_{j}]|~{}=~{}$
$\displaystyle\big{|}\mathbb{E}\bigl{[}(W_{i}-W_{i}^{(-j)})(W_{j}-W_{j}^{(-i)})\bigr{]}\big{|}$
$\displaystyle\leq~{}$
$\displaystyle\big{\\{}\mathbb{E}\bigl{[}\big{(}W_{i}-W_{i}^{(-j)}\big{)}^{2}\bigr{]}\big{\\}}^{1/2}\big{\\{}\mathbb{E}\bigl{[}\big{(}W_{j}-W_{j}^{(-i)}\big{)}^{2}\bigr{]}\big{\\}}^{1/2}.$

We let $\widehat{f}^{(-i,-j)}$ denote an estimate of $f$ trained on
$\mathcal{D}_{XY}^{(-i,-j)}$, that is the same as $\mathcal{D}_{XY}$ except
$(X_{i},Y_{i})$ and $(X_{j},Y_{j})$ replaced by their i.i.d. copies. Then
using the inequality $(x+y)^{2}\leq 2x^{2}+2y^{2}$, we have

$\displaystyle\mathbb{E}\bigl{[}\big{(}W_{i}-W_{i}^{(-j)}\big{)}^{2}\bigr{]}\leq
2\mathbb{E}[\\{\widehat{f}^{(-i)}(X_{i})-\widehat{f}^{(-i,-j)}(X_{i})\\}^{2}]+2\mathbb{E}[\\{\widehat{f}^{(-i)}(X)-\widehat{f}^{(-i,-j)}(X)\\}^{2}]\quad\text{and}$
$\displaystyle\mathbb{E}\bigl{[}\big{(}W_{j}-W_{j}^{(-i)}\big{)}\bigr{]}\leq
2\mathbb{E}[\\{\widehat{f}^{(-j)}(X_{j})-\widehat{f}^{(-i,-j)}(X_{j})\\}^{2}]+2\mathbb{E}[\\{\widehat{f}^{(-j)}(X)-\widehat{f}^{(-i,-j)}(X)\\}^{2}].$

Moreover, since $X_{i}$ is not used in the construction of both
$\widehat{f}^{(-i)}$ and $\widehat{f}^{(-i,-j)}$, the following identity holds

$\displaystyle\mathbb{E}[|\widehat{f}^{(-i)}(X_{i})-\widehat{f}^{(-i,-j)}(X_{i})|^{2}]~{}=~{}$
$\displaystyle\mathbb{E}[|\widehat{f}^{(-i)}(X)-\widehat{f}^{(-i,-j)}(X)|^{2}]$
$\displaystyle=~{}$
$\displaystyle\mathbb{E}[|\widehat{f}(X)-\widehat{f}^{(-j)}(X)|^{2}],$

where the second equality follows since $\widehat{f}(X)-\widehat{f}^{(-j)}(X)$
and $\widehat{f}^{(-i)}(X)-\widehat{f}^{(-i,-j)}(X)$ have the same
distribution. This leads to

$\displaystyle\mathbb{E}\bigl{[}\big{(}W_{i}-W_{i}^{(-j)}\big{)}^{2}\bigr{]}\leq
4\max_{1\leq i\leq
n}\mathbb{E}[\\{\widehat{f}(X)-\widehat{f}^{(-i)}(X)\\}^{2}].$

Putting things together, we have

$\displaystyle\bigg{|}\frac{r^{2}}{n}\sum_{1\leq i\neq j\leq
n}\mathbb{E}[W_{i}W_{j}]\bigg{|}~{}\lesssim~{}n\max_{1\leq i\leq
n}\mathbb{E}[\\{\widehat{f}(X)-\widehat{f}^{(-i)}(X)\\}^{2}]=o(1)$

and thus conclude that

$\displaystyle\sqrt{n}\mathbb{E}[|(\mathrm{I})|]=o(1).$

The second term (II) can be analyzed analogously as (I) and shown to be
$\sqrt{n}\mathbb{E}[|(\mathrm{II})|]=o(1)$.

For the last term (III), as we assume $\widehat{f}$ is trained on the entire
labeled dataset $\mathcal{D}_{XY}$, $\widehat{f}^{(-i)}$ remains the same as
$\widehat{f}$ for $n+1\leq i\leq n+m$. Thus the last two sums in the term
(III) satisfy

$\displaystyle\frac{r}{n}\sum_{i=1}^{n}\mathbb{E}_{X_{i}}[\widehat{f}^{(-i)}(X_{i})]-\frac{r}{n+m}\sum_{i=1}^{n+m}\mathbb{E}_{X_{i}}[\widehat{f}^{(-i)}(X_{i})]$
$\displaystyle=\ $
$\displaystyle\frac{rm}{n(n+m)}\sum_{i=1}^{n}\mathbb{E}_{X_{i}}[\widehat{f}^{(-i)}(X_{i})]-\frac{rm}{n+m}\mathbb{E}_{X}[\widehat{f}(X)]$
$\displaystyle=\ $
$\displaystyle\frac{rm}{n+m}\times\frac{1}{n}\sum_{i=1}^{n}\big{\\{}\mathbb{E}_{X_{i}}[\widehat{f}^{(-i)}(X_{i})]-\mathbb{E}_{X}[\widehat{f}(X)]\big{\\}}$
$\displaystyle=\ $
$\displaystyle\frac{rm}{n+m}\times\frac{1}{n}\sum_{i=1}^{n}\big{\\{}\mathbb{E}_{X}[\widehat{f}^{(-i)}(X)-\widehat{f}(X)]\big{\\}},$

where the last equality utilizes the observation that
$\mathbb{E}_{X_{i}}[\widehat{f}^{(-i)}(X_{i})]=\mathbb{E}_{X}[\widehat{f}^{(-i)}(X)]$
as $\widehat{f}^{(-i)}$ is independent of $X_{i}$. Therefore, we have

$\displaystyle\sqrt{n}\mathbb{E}[|(\mathrm{III})|]\lesssim\sqrt{n}\max_{1\leq
i\leq
n}\mathbb{E}\bigl{[}\big{|}\widehat{f}(X_{i})-\widehat{f}^{(-i)}(X_{i})\big{|}\bigr{]}+\sqrt{n}\max_{1\leq
i\leq
n}\mathbb{E}\bigl{[}\big{|}\widehat{f}(X)-\widehat{f}^{(-i)}(X)\big{|}\bigr{]}=o(1).$

We have shown that

$\displaystyle\mathbb{E}[|U_{\mathrm{plug}}-U_{f}|]=o(n^{-1/2}),$

which together with Markov’s inequality proves the desired claim
$U_{\mathrm{plug}}-U_{f}=o_{P}(n^{-1/2})$.

###  C.6 Proof of Theorem 3

The proof of Theorem 3 builds on the Berry–Esseen bound for non-linear
statistics (Chen et al.,, 2011, Chapter 10) and Lemma 4. For notational
simplicity, let us write

$\displaystyle\sigma^{2}:=n^{-1}\Lambda_{n,m,f}=\frac{r^{2}}{n}\biggl{(}\sigma_{1}^{2}+\frac{m}{n+m}\\{\mathrm{Var}[f(X)]-2\mathrm{Cov}[f(X),\psi_{1}(X)]\\}\biggr{)}\geq\frac{r^{2}\sigma_{1}^{2}}{n},$
(19)

where the inequality follows by Lemma 2, which shows that $\psi_{1}$ minimizes
$\Lambda_{n,m,f}$ as a function of $f$, and $\Lambda_{n,m,f}$ defined with
$\psi_{1}$ is greater than or equal to $r^{2}\sigma_{1}^{2}/n$. Using Chen et
al., (2011, Equation 10.19), we observe that $U_{\mathrm{cross}}$ can be
decomposed as

$\displaystyle\frac{U_{\mathrm{cross}}-\psi}{\sigma}~{}={}$
$\displaystyle\underbrace{\frac{r}{\sigma
n}\sum_{i=1}^{n}\\{\ell_{1}(Y_{i})-f(X_{i})\\}+\frac{r}{\sigma(n+m)}\sum_{i=1}^{n+m}\\{f(X_{i})-\psi\\}}_{=W}$
(20) $\displaystyle+{}$
$\displaystyle\underbrace{\frac{1}{\sigma}\binom{n}{r}^{-1}\sum_{1\leq
i_{1}<\cdots<i_{r}\leq
n}\biggl{(}\ell(Y_{i_{1}},\ldots,Y_{i_{r}})-\psi-\sum_{j=1}^{r}\\{\ell_{1}(Y_{i_{j}})-\psi\\}\biggr{)}}_{=\Delta_{1}}$
$\displaystyle+{}$ $\displaystyle\underbrace{\frac{r}{\sigma
n}\sum_{i=1}^{n}\\{f(X_{i})-\widehat{f}_{\mathrm{cross}}(X_{i})\\}+\frac{r}{\sigma(n+m)}\sum_{i=1}^{n+m}\\{\widehat{f}_{\mathrm{cross}}(X_{i})-f(X_{i})\\}}_{=\Delta_{2}}$
$\displaystyle={}$ $\displaystyle W+\Delta_{1}+\Delta_{2}.$

As in the proof of Theorem 1, we note that $W$ can be written as the sum of
independent random variables $Z_{i}$, i.e., $W=\sum_{i=1}^{n+m}Z_{i}$, where

$\displaystyle Z_{i}=\begin{cases}\frac{r}{\sigma
n}\\{\ell_{1}(Y_{i})-f(X_{i})\\}+\frac{r}{\sigma(n+m)}\\{f(X_{i})-\psi\\}&\text{for
$1\leq i\leq n$},\\\\[5.0pt]
\frac{r}{\sigma(n+m)}\\{f(X_{i})-\psi\\}&\text{for $n+1\leq i\leq
n+m$.}\end{cases}$

For $k\in[n]$, let $\Delta_{1,k}$ denote a leave-one-out version of
$\Delta_{1}$, excluding $Y_{k}$ in its calculation, defined as

$\displaystyle\Delta_{1,k}=\frac{1}{\sigma}\binom{n}{r}^{-1}\sum_{\begin{subarray}{c}1\leq
i_{1}<\cdots<i_{r}\leq n\\\ \text{$i_{q}\neq k$ for all
$q$}\end{subarray}}\biggl{(}\ell(Y_{i_{1}},\ldots,Y_{i_{r}})-\psi-\sum_{j=1}^{r}\\{\ell_{1}(Y_{i_{j}})-\psi\\}\biggr{)},$

and set $\Delta_{1,k}=\Delta_{1}$ for $k\in[n+m]\setminus[n]$. For $k\in[n]$,
we let $\Delta_{2,k}$ be similarly computed as $\Delta_{2}$ but by replacing
$(X_{k},Y_{k})$ with its i.i.d. copy $(\widetilde{X}_{k},\widetilde{Y}_{k})$.
For $k\in[n+m]\\!\setminus\\![n]$, we let $\Delta_{2,k}$ be similarly computed
as $\Delta_{2}$ but by replacing $X_{k}$ with its i.i.d. copy
$\widetilde{X}_{k}$. This construction ensures that $Z_{i}$, which is a
function of $(X_{i},Y_{i})$ or $X_{i}$ only, is independent of
$(W-Z_{i},\Delta_{1,i}+\Delta_{2,i})$ for each $i\in[n+m]$.

Letting $\Delta=\Delta_{1}+\Delta_{2}$, Chen et al., (2011, Theorem 10.1)
yields

$\displaystyle\sup_{t\in\mathbb{R}}\bigg{|}\mathbb{P}\biggl{(}\frac{\sqrt{n}(U_{\mathrm{cross}}-\psi)}{\sqrt{\smash[b]{\Lambda_{n,m,f}}}}\leq
t\biggr{)}-\Phi(t)\bigg{|}~{}\leq~{}$ $\displaystyle
6.1(\beta_{2}+\beta_{3})+\mathbb{E}[|W\Delta|]+\sum_{i=1}^{n+m}\mathbb{E}|Z_{i}(\Delta-\Delta_{i})|$
$\displaystyle=~{}$ $\displaystyle
6.1(\mathrm{I})+\mathrm{(II)}+\mathrm{(III)},$

where

$\displaystyle\beta_{2}=\sum_{i=1}^{n+m}\mathbb{E}[Z_{i}^{2}\mathds{1}(|Z_{i}|>1)]\quad\text{and}\quad\beta_{3}=\sum_{i=1}^{n+m}\mathbb{E}[|Z_{i}|^{3}\mathds{1}(|Z_{i}|\leq
1)].$

We next provide upper bounds for (I), (II) and (III) in order.

##### Analysis of (I).

Starting with $\mathrm{(I)}=\beta_{2}+\beta_{3}$, recall

$\displaystyle
M_{p,\ell_{1}}=\mathbb{E}[|\ell_{1}(Y)-\mathbb{E}[\ell_{1}(Y)]|^{p}]\quad\text{and}\quad
M_{p,f}=\mathbb{E}[|f(X)-\mathbb{E}[f(X)]|^{p}].$

Then using the inequality $\sigma^{3}\gtrsim\sigma_{1}^{3}n^{-3/2}$ from (19),
we have

$\displaystyle\beta_{2}+\beta_{3}\leq
2\sum_{i=1}^{n+m}\mathbb{E}[|Z_{i}|^{3}]=2n\mathbb{E}[|Z_{1}|^{3}]+2m\mathbb{E}[|Z_{n+1}|^{3}]~{}\lesssim~{}\frac{M_{3,\ell_{1}}+M_{3,f}}{\sqrt{n}\sigma_{1}^{3}},$

which yields the first term in $\Omega_{1}$ in the theorem statement.

##### Analysis of (II).

For the second term $(\mathrm{II})=\mathbb{E}[|W\Delta|]$, the triangle
inequality along with Jensen’s inequality yields

$\displaystyle\mathbb{E}[|W\Delta|]\leq\mathbb{E}[|W\Delta_{1}|]+\mathbb{E}[|W\Delta_{2}|]\leq\\{\mathbb{E}[\Delta_{1}^{2}]\\}^{1/2}+\\{\mathbb{E}[\Delta_{2}^{2}]\\}^{1/2},$

where we use the condition $\mathbb{E}[W^{2}]=1$ or equivalently
$\mathrm{Var}[\sum_{i=1}^{n+m}Z_{i}]=\sigma^{2}$. Moreover, Chen et al.,
(2011, Equation 10.20) yields

$\displaystyle\\{\mathbb{E}[\Delta_{1}^{2}]\\}^{1/2}\leq\bigg{\\{}\frac{(r-1)^{2}\mathrm{Var}[\ell(Y_{1},\ldots,Y_{r})]}{r(n-r+1)\mathrm{Var}[\ell_{1}(Y)]}\biggr{\\}}^{1/2}\lesssim\frac{\sigma_{\ell}}{(n-r)\sigma_{1}},$

where we use the inequality $\mathrm{Var}[\ell_{1}(Y)]\geq\sigma_{1}^{2}$ and
recall that $\sigma_{\ell}^{2}=\mathrm{Var}[\ell(Y_{1},\ldots,Y_{r})]$. The
next term $\mathbb{E}[\Delta_{2}^{2}]$ is analyzed in the proof of Theorem 1,
and it can be shown that

$\displaystyle\\{\mathbb{E}[\Delta_{2}^{2}]\\}^{1/2}\lesssim\frac{\Delta_{\mathrm{MSPE}}^{1/2}}{\sigma_{1}}.$

Therefore, we have

$\displaystyle\mathbb{E}[|W\Delta|]\lesssim\frac{\sigma_{\ell}}{\sqrt{n-r}\sigma_{1}}+\frac{\Delta_{\mathrm{MSPE}}^{1/2}}{\sigma_{1}}.$

##### Analysis of (III).

For the last term
$\mathrm{(III)}=\sum_{i=1}^{n+m}\mathbb{E}|Z_{i}(\Delta-\Delta_{i})|$, we
first apply the triangle inequality

$\displaystyle\sum_{i=1}^{n+m}\mathbb{E}|Z_{i}(\Delta-\Delta_{i})|\leq\sum_{i=1}^{n+m}\mathbb{E}|Z_{i}(\Delta_{1}-\Delta_{1,i})|+\sum_{i=1}^{n+m}\mathbb{E}|Z_{i}(\Delta_{2}-\Delta_{2,i})|.$

Note that $\Delta-\Delta_{1,i}=0$ for $i\in[n+m]\setminus[n]$. So using Chen
et al., (2011, Equation 10.21) along with the Cauchy–Schwarz inequality yields

$\displaystyle\sum_{i=1}^{n+m}\mathbb{E}|Z_{i}(\Delta_{1}-\Delta_{1,i})|\ =\ $
$\displaystyle\sum_{i=1}^{n}\mathbb{E}|Z_{i}(\Delta_{1}-\Delta_{1,i})|$
$\displaystyle\leq\ $ $\displaystyle
n\\{\mathbb{E}[Z_{1}^{2}]\\}^{1/2}\\{\mathbb{E}[(\Delta_{1}-\Delta_{1,1})^{2}]\\}^{1/2}$
$\displaystyle\lesssim\ $
$\displaystyle\frac{(M_{2,\ell_{1}}^{1/2}+M_{2,f}^{1/2})}{\sigma_{1}}\times\biggr{[}\frac{2(r-1)\mathrm{Var}[\ell(Y_{1},\ldots,Y_{r})]}{nr(n-r+1)\sigma_{1}^{2}}\biggr{]}^{1/2}$
$\displaystyle\lesssim\ $
$\displaystyle\frac{(M_{2,\ell_{1}}^{1/2}+M_{2,f}^{1/2})\sigma_{\ell}}{\sqrt{n-r}\sigma_{1}^{2}}.$

Turning to the next term, we use the Cauchy–Schwarz inequality to yield

$\displaystyle\sum_{i=1}^{n+m}\mathbb{E}|Z_{i}(\Delta_{2}-\Delta_{2,i})|\
\leq\ $
$\displaystyle\sum_{i=1}^{n+m}\\{\mathbb{E}[Z_{i}^{2}]\\}^{1/2}\\{\mathbb{E}[(\Delta_{2}-\Delta_{2,i})^{2}]\\}^{1/2},$

where the second moment of $Z_{i}$ satisfies

$\displaystyle\mathbb{E}[Z_{i}^{2}]\lesssim\begin{cases}\frac{1}{n\sigma_{1}^{2}}\big{\\{}\mathrm{Var}[\ell_{1}(Y)]+\mathrm{Var}[f(X)]\big{\\}},\quad&\text{if
$i\in[n]$,}\\\\[5.0pt]
\frac{1}{n\sigma_{1}^{2}}\frac{n^{2}}{(n+m)^{2}}\mathrm{Var}[f(X)],\quad&\text{if
$i\in[n+m]\setminus[n]$.}\end{cases}$

To deal with $\mathbb{E}[(\Delta_{2}-\Delta_{2,i})^{2}]$, we let
$n_{0}=\lfloor n/2\rfloor$ and $m_{0}=\lfloor m/2\rfloor$, and denote by
$\widehat{f}_{2}^{-(1)}$ the estimator similarly defined as $\widehat{f}_{2}$
but replacing $(X_{1},Y_{1})$ with i.i.d. copy
$(\widetilde{X}_{1},\widetilde{Y}_{1})$. Then by first fixing $i=1$, consider
the following decomposition as in the proof of Theorem 1:

$\displaystyle\sigma\times(\Delta_{2}-\Delta_{2,1})$ $\displaystyle=~{}$
$\displaystyle\frac{r}{n}\\{f(X_{1})-\widehat{f}_{1}(X_{1})-f(\widetilde{X}_{1})+\widehat{f}_{1}(\widetilde{X}_{1})\\}-\frac{r}{n+m}\\{f(X_{1})-\widehat{f}_{1}(X_{1})-f(\widetilde{X}_{1})+\widehat{f}_{1}(\widetilde{X}_{1})\\}$
$\displaystyle+~{}$
$\displaystyle\frac{r}{n}\sum_{i=n_{0}+1}^{n}\\{\widehat{f}_{2}^{-(1)}(X_{i})-\widehat{f}_{2}(X_{i})\\}-\frac{r}{n+m}\sum_{i=n_{0}+1}^{n}\\{\widehat{f}_{2}^{-(1)}(X_{i})-\widehat{f}_{2}(X_{i})\\}$
$\displaystyle-~{}$
$\displaystyle\frac{r}{n+m}\sum_{i=n+m_{0}+1}^{n+m}\\{\widehat{f}_{2}^{-(1)}(X_{i})-\widehat{f}_{2}(X_{i})\\}$
$\displaystyle=~{}$
$\displaystyle\frac{rm}{n(n+m)}\\{f(X_{1})-\widehat{f}_{1}(X_{1})-f(\widetilde{X}_{1})+\widehat{f}_{1}(\widetilde{X}_{1})\\}+\frac{rm}{n(n+m)}\sum_{i=n_{0}+1}^{n}\\{\widehat{f}_{2}^{-(1)}(X_{i})-\widehat{f}_{2}(X_{i})\\}$
$\displaystyle-~{}$
$\displaystyle\frac{r}{n+m}\sum_{i=n+m_{0}+1}^{n+m}\\{\widehat{f}_{2}^{-(1)}(X_{i})-\widehat{f}_{2}(X_{i})\\}.$

Moreover observe that

$\displaystyle\frac{rm}{n(n+m)}\sum_{i=n_{0}+1}^{n}\\{\widehat{f}_{2}^{-(1)}(X_{i})-\widehat{f}_{2}(X_{i})\\}-\frac{r}{n+m}\sum_{i=n+m_{0}+1}^{n+m}\\{\widehat{f}_{2}^{-(1)}(X_{i})-\widehat{f}_{2}(X_{i})\\}$
$\displaystyle=~{}$
$\displaystyle\frac{rm}{n(n+m)}\sum_{i=n_{0}+1}^{n}\\{\widehat{f}_{2}^{-(1)}(X_{i})-\mathbb{E}[\widehat{f}_{2}^{-(1)}(X)\,|\,\widehat{f}_{2}^{-(1)}]-\widehat{f}_{2}(X_{i})+\mathbb{E}[\widehat{f}_{2}(X)\,|\,\widehat{f}_{2}]\\}$
$\displaystyle-~{}$
$\displaystyle\frac{r}{n+m}\sum_{i=n+m_{0}+1}^{n+m}\\{\widehat{f}_{2}^{-(1)}(X_{i})-\mathbb{E}[\widehat{f}_{2}^{-(1)}(X)\,|\,\widehat{f}_{2}^{-(1)}]-\widehat{f}_{2}(X_{i})+\mathbb{E}[\widehat{f}_{2}(X)\,|\,\widehat{f}_{2}]\\}$
$\displaystyle+~{}$
$\displaystyle\underbrace{\frac{r}{n+m}\times\frac{m\lfloor
n/2\rfloor-n\lfloor
m/2\rfloor}{n}}_{\asymp~{}n^{-1}}\times\bigl{(}\mathbb{E}[\widehat{f}_{2}^{-(1)}(X)\,|\,\widehat{f}_{2}^{-(1)}]-\mathbb{E}[\widehat{f}_{2}(X)\,|\,\widehat{f}_{2}]\bigr{)},$

where the summands in the alternative expression are centered. Using this
observation, it can be seen that

$\displaystyle\sigma^{2}\mathbb{E}[(\Delta_{2}-\Delta_{2,1})^{2}]$
$\displaystyle~{}\lesssim~{}$
$\displaystyle\frac{m^{2}}{n^{2}(n+m)^{2}}\mathbb{E}[\\{\widehat{f}_{1}(X)-f(X)\\}^{2}]+\frac{1}{n^{2}}\mathbb{E}[\\{\widehat{f}_{2}^{-(1)}(X)-\widehat{f}_{2}(X)\\}^{2}]$
$\displaystyle~{}~{}+\frac{m^{2}}{n^{2}(n+m)^{2}}\sum_{i=n_{0}+1}^{n}\mathbb{E}[\\{\widehat{f}_{2}^{-(1)}(X_{i})-\mathbb{E}[\widehat{f}_{2}^{-(1)}(X)\,|\,\widehat{f}_{2}^{-(1)}]-\widehat{f}_{2}(X_{i})+\mathbb{E}[\widehat{f}_{2}(X)\,|\,\widehat{f}_{2}]\\}^{2}]$
$\displaystyle~{}~{}+\frac{1}{(n+m)^{2}}\sum_{i=n+m_{0}+1}^{n+m}\mathbb{E}[\\{\widehat{f}_{2}^{-(1)}(X_{i})-\mathbb{E}[\widehat{f}_{2}^{-(1)}(X)\,|\,\widehat{f}_{2}^{-(1)}]-\widehat{f}_{2}(X_{i})+\mathbb{E}[\widehat{f}_{2}(X)\,|\,\widehat{f}_{2}]\\}^{2}]$
$\displaystyle\lesssim~{}$
$\displaystyle\frac{m^{2}}{n^{2}(n+m)^{2}}\mathbb{E}[\\{\widehat{f}_{1}(X)-f(X)\\}^{2}]+\frac{1}{n^{2}}\mathbb{E}[\\{\widehat{f}_{2}^{-(1)}(X)-\widehat{f}_{2}(X)\\}^{2}]$
$\displaystyle~{}~{}+\frac{m^{2}n}{n^{2}(n+m)^{2}}\mathbb{E}[\\{\widehat{f}_{2}^{-(1)}(X)-\widehat{f}_{2}(X)\\}^{2}]+\frac{m}{(n+m)^{2}}\mathbb{E}[\\{\widehat{f}_{2}^{-(1)}(X)-\widehat{f}_{2}(X)\\}^{2}]$

and

$\displaystyle\mathbb{E}[(\Delta_{2}-\Delta_{2,1})^{2}]~{}\lesssim~{}$
$\displaystyle\frac{m^{2}}{n(n+m)^{2}\sigma_{1}^{2}}\mathbb{E}[\\{\widehat{f}_{1}(X)-f(X)\\}^{2}]+\frac{1}{\sigma_{1}^{2}n}\mathbb{E}[\\{\widehat{f}_{2}^{-(1)}(X)-\widehat{f}_{2}(X)\\}^{2}]$
$\displaystyle~{}+\frac{m^{2}}{\sigma_{1}^{2}(n+m)^{2}}\mathbb{E}[\\{\widehat{f}_{2}^{-(1)}(X)-\widehat{f}_{2}(X)\\}^{2}]+\frac{nm}{\sigma_{1}^{2}(n+m)^{2}}\mathbb{E}[\\{\widehat{f}_{2}^{-(1)}(X)-\widehat{f}_{2}(X)\\}^{2}]$
$\displaystyle\lesssim~{}$
$\displaystyle\frac{1}{n\sigma_{1}^{2}}\mathbb{E}[\\{\widehat{f}_{1}(X)-f(X)\\}^{2}]+\frac{m}{\sigma_{1}^{2}(n+m)}\mathbb{E}[\\{\widehat{f}_{2}^{-(1)}(X)-\widehat{f}_{2}(X)\\}^{2}].$

The other terms $\mathbb{E}[(\Delta_{2}-\Delta_{2,i})^{2}]$ for
$i\in\\{2,\ldots,n\\}$ can be similarly handled, which yields that

$\displaystyle\sum_{i=1}^{n}\\{\mathbb{E}[Z_{i}^{2}]\\}^{1/2}\\{\mathbb{E}[(\Delta_{2}-\Delta_{2,i})^{2}]\\}^{1/2}$
$\displaystyle\lesssim~{}$
$\displaystyle\frac{1}{\sigma_{1}^{2}}\bigl{(}M_{2,\ell_{1}}^{1/2}+M_{2,f}^{1/2}\bigr{)}\Delta_{\mathrm{MSPE}}^{1/2}+\sqrt{\frac{m}{n(n+m)}}\frac{\bigl{(}M_{2,\ell_{1}}^{1/2}+M_{2,f}^{1/2}\bigr{)}}{\sigma_{1}^{2}}\sum_{i=1}^{n_{0}}\sqrt{\mathbb{E}[\\{\widehat{f}_{2}^{(-i)}(X)-\widehat{f}_{2}(X)\\}^{2}]}$
$\displaystyle~{}+\sqrt{\frac{m}{n(n+m)}}\frac{\bigl{(}M_{2,\ell_{1}}^{1/2}+M_{2,f}^{1/2}\bigr{)}}{\sigma_{1}^{2}}\sum_{i=n_{0}+1}^{n}\sqrt{\mathbb{E}[\\{\widehat{f}_{1}^{(-i)}(X)-\widehat{f}_{1}(X)\\}^{2}]}$
$\displaystyle\lesssim~{}$
$\displaystyle\frac{1}{\sigma_{1}^{2}}\bigl{(}M_{2,\ell_{1}}^{1/2}+M_{2,f}^{1/2}\bigr{)}\Delta_{\mathrm{MSPE}}^{1/2}$
$\displaystyle~{}+\frac{\bigl{(}M_{2,\ell_{1}}^{1/2}+M_{2,f}^{1/2}\bigr{)}}{\sigma_{1}^{2}}\bigg{\\{}\frac{nm}{n+m}\bigg{\\}}^{1/2}\bigg{\\{}\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}[\\{\widehat{f}_{\mathrm{cross}}^{(-i)}(X)-\widehat{f}_{\mathrm{cross}}(X)\\}^{2}]\bigg{\\}}^{1/2}$
$\displaystyle\lesssim~{}$
$\displaystyle\frac{\bigl{(}M_{2,\ell_{1}}^{1/2}+M_{2,f}^{1/2}\bigr{)}}{\sigma_{1}^{2}}\bigl{(}\Delta_{\mathrm{MSPE}}^{1/2}+\Delta_{\mathrm{Stability}}^{1/2}\bigr{)}.$

Next we deal with $\mathbb{E}[(\Delta_{2}-\Delta_{2,n+1})^{2}]$. Similarly as
before, we have

$\displaystyle\sigma\times(\Delta_{2}-\Delta_{2,n+1})$ $\displaystyle=~{}$
$\displaystyle\frac{r}{n+m}\\{\widehat{f}_{1}(X_{n+1})-f(X_{n+1})-\widehat{f}_{1}(\widetilde{X}_{n+1})+f(\widetilde{X}_{n+1})\\}$
$\displaystyle~{}+\frac{rm}{n(n+m)}\sum_{i=n_{0}+1}^{n}\\{\widehat{f}_{2}^{-(n+1)}(X_{i})-\widehat{f}_{2}(X_{i})\\}-\frac{r}{n+m}\sum_{i=n+m_{0}+1}^{n+m}\\{\widehat{f}_{2}^{-(n+1)}(X_{i})-\widehat{f}_{2}(X_{i})\\}$
$\displaystyle=~{}$
$\displaystyle\frac{r}{n+m}\\{\widehat{f}_{1}(X_{n+1})-f(X_{n+1})-\widehat{f}_{1}(\widetilde{X}_{n+1})+f(\widetilde{X}_{n+1})\\},$

where the last line uses our condition on $\widehat{f}_{2}$ that it does not
use the unlabeled dataset, thereby $\widehat{f}_{2}$ and
$\widehat{f}_{2}^{-(n+1)}$ remain the same. This leads to

$\displaystyle\sigma^{2}\mathbb{E}[(\Delta_{2}-\Delta_{2,n+1})^{2}]\leq\frac{2r^{2}}{(n+m)^{2}}\mathbb{E}[\\{\widehat{f}_{1}(X)-f(X)\\}^{2}].$

The other term $\mathbb{E}[(\Delta_{2}-\Delta_{2,i})^{2}]$ for
$i\in[n+m]\\!\setminus\\![n+1]$ can be similarly handled, which yields that

$\displaystyle\sum_{i=n+1}^{n+m}\\{\mathbb{E}[Z_{i}^{2}]\\}^{1/2}\\{\mathbb{E}[(\Delta_{2}-\Delta_{2,i})^{2}]\\}^{1/2}\lesssim\frac{1}{\sigma_{1}^{2}}M_{2,f}^{1/2}\Delta_{\mathrm{MSPE}}^{1/2}.$

Summing all the results from Analysis (I), (II) and (III), we have

$\displaystyle\sup_{t\in\mathbb{R}}\bigg{|}\mathbb{P}\biggl{(}\frac{\sqrt{n}(U_{\mathrm{cross}}-\psi)}{\sqrt{\smash[b]{\Lambda_{n,m,f}}}}\leq
t\biggr{)}-\Phi(t)\bigg{|}~{}\lesssim{}$
$\displaystyle\frac{M_{3,\ell_{1}}+M_{3,f}}{\sqrt{n}\sigma_{1}^{3}}+\frac{(M_{2,\ell_{1}}^{1/2}+M_{2,f}^{1/2}+\sigma_{1})\sigma_{\ell}}{\sqrt{n-r}\sigma_{1}^{2}}$
(21) $\displaystyle+{}$
$\displaystyle\frac{M_{2,\ell_{1}}^{1/2}+M_{2,f}^{1/2}+\sigma_{1}}{\sigma_{1}^{2}}\bigl{(}\Delta_{\mathrm{MSPE}}^{1/2}+\Delta_{\mathrm{Stability}}^{1/2}\bigr{)}.$

##### Obtaining the bound $\Delta_{\mathrm{MSPE}}^{1/3}$.

To obtain the bound depending on $\Delta_{\mathrm{MSPE}}^{1/3}$, the
decomposition (20) together with Lemma 4 yields

$\displaystyle\sup_{t\in\mathbb{R}}\bigg{|}\mathbb{P}\biggl{(}\frac{\sqrt{n}(U_{\mathrm{cross}}-\psi)}{\sqrt{\smash[b]{\Lambda_{n,m,f}}}}\leq
t\biggr{)}-\Phi(t)\bigg{|}\ \lesssim\
\sup_{t\in\mathbb{R}}\big{|}\mathbb{P}\bigl{(}W+\Delta_{1}\leq
t\bigr{)}-\Phi(t)\big{|}+\\{\mathbb{E}[|\Delta_{2}|^{2}]\\}^{1/3}.$

Moreover, following the previous analysis, we have

$\displaystyle\sup_{t\in\mathbb{R}}\big{|}\mathbb{P}\bigl{(}W+\Delta_{1}\leq
t\bigr{)}-\Phi(t)\big{|}\ \lesssim\
\frac{M_{3,\ell_{1}}+M_{3,f}}{\sqrt{n}\sigma_{1}^{3}}+\frac{(M_{2,\ell_{1}}^{1/2}+M_{2,f}^{1/2}+\sigma_{1})\sigma_{\ell}}{\sqrt{n-r}\sigma_{1}^{2}}\quad\text{and}$
$\displaystyle\\{\mathbb{E}[|\Delta_{2}|^{2}]\\}^{1/3}\ \lesssim\
\frac{\Delta_{\mathrm{MSPE}}^{1/3}}{\sigma_{1}^{2/3}}.$

Therefore

$\displaystyle\sup_{t\in\mathbb{R}}\bigg{|}\mathbb{P}\biggl{(}\frac{\sqrt{n}(U_{\mathrm{cross}}-\psi)}{\sqrt{\smash[b]{\Lambda_{n,m,f}}}}\leq
t\biggr{)}-\Phi(t)\bigg{|}\ \lesssim\
\frac{M_{3,\ell_{1}}+M_{3,f}}{\sqrt{n}\sigma_{1}^{3}}+\frac{(M_{2,\ell_{1}}^{1/2}+M_{2,f}^{1/2}+\sigma_{1})\sigma_{\ell}}{\sqrt{n-r}\sigma_{1}^{2}}+\frac{\Delta_{\mathrm{MSPE}}^{1/3}}{\sigma_{1}^{2/3}}.$
(22)

##### Conclusion.

Now combining the two inequalities (21) and (22) proves the desired claim in
Theorem 3.

###  C.7 Proof of Proposition 3

We prove the result focusing on the linear kernel $\ell(y)=y$. For notational
simplicity, assume that we have the labeled dataset of size $2n$ and the
unlabeled dataset of size $2m$. Our target assistant-function $f$ is set as
$f(x)=0$ for all $x$, and our estimators $\widehat{f}_{1}$ and
$\widehat{f}_{2}$ are set as

$\displaystyle\widehat{f}_{1}(x)=\frac{\sqrt{\epsilon_{n}}}{2}\times\biggl{(}x+\frac{1}{\sqrt{n}}\sum_{i=1}^{n}X_{i}\biggr{)}\quad\text{and}\quad\widehat{f}_{2}(x)=\frac{\sqrt{\epsilon_{n}}}{2}\times\biggl{(}x+\frac{1}{\sqrt{n}}\sum_{i=n+1}^{2n}X_{i}\biggr{)}.$
(23)

Assume that $Y$ and $X$ are perfectly correlated and follow the standard
Normal distribution as $Y=X\sim N(0,1)$. Then it can be seen that

$\displaystyle\Delta_{\mathrm{MSPE}}=\mathbb{E}[\\{\widehat{f}_{1}(X)-f(X)\\}^{2}]+\mathbb{E}[\\{\widehat{f}_{2}(X)-f(X)\\}^{2}]=\epsilon_{n}.$

Moreover, we can prove that
$\Delta_{\mathrm{Stability}}=\Delta_{\mathrm{MSPE}}=\epsilon_{n}$, from which
we can verify the condition
$\Delta_{\mathrm{MSPE}}\geq\max\\{\epsilon_{n},\Delta_{\mathrm{Stability}}\\}$.
Using these estimators and letting $\varepsilon_{n}:=\sqrt{\epsilon_{n}}/2$,

$\displaystyle\overline{Y}:=\frac{1}{2n}\sum_{i=1}^{2n}Y_{i}\quad\text{and}\quad\widetilde{Y}:=\frac{1}{2m}\sum_{i=2n+1}^{2n+2m}Y_{i},$

the semi-supervised U-statistic $U_{\mathrm{cross}}$ can be written as

$\displaystyle U_{\mathrm{cross}}\,=\,$
$\displaystyle\frac{1}{2n}\sum_{i=1}^{n}(Y_{i}-\widehat{f}_{2}(X_{i}))+\frac{1}{2n}\sum_{i=n+1}^{2n}(Y_{i}-\widehat{f}_{1}(X_{i}))+\frac{1}{2n+2m}\sum_{i=1}^{n}\widehat{f}_{2}(X_{i})$
$\displaystyle+\frac{1}{2n+2m}\sum_{i=2n+1}^{2n+m}\widehat{f}_{2}(X_{i})+\frac{1}{2n+2m}\sum_{i=n+1}^{2n}\widehat{f}_{1}(X_{i})+\frac{1}{2n+2m}\sum_{i=2n+m+1}^{2n+2m}\widehat{f}_{1}(X_{i})$
$\displaystyle=\,$
$\displaystyle\biggl{(}1-\varepsilon_{n}\frac{m}{n+m}\biggr{)}\overline{Y}+\varepsilon_{n}\frac{m}{n+m}\widetilde{Y},$

where we leverage the invariance of $U_{\mathrm{cross}}$ to location-shifts
for both $\widehat{f}_{1}$ and $\widehat{f}_{2}$. That is,
$U_{\mathrm{cross}}$ remains the same for any values of $c_{1},c_{2}$ in
$\widehat{f}_{1}+c_{1}$ and $\widehat{f}_{2}+c_{2}$. Hence, letting
$Z_{1},Z_{2}\overset{\mathrm{i.i.d.}}{\sim}N(0,1)$ and noting that
$\Lambda_{n,m,f}=\mathrm{Var}[Y]$ in this example,

$\displaystyle\frac{\sqrt{2n}U_{\mathrm{cross}}}{\sqrt{\mathrm{Var}[Y]}}\overset{d}{=}\biggl{(}1-\varepsilon_{n}\frac{m}{n+m}\biggr{)}Z_{1}+\varepsilon_{n}\frac{m}{n+m}\sqrt{\frac{n}{m}}Z_{2}.$

Letting $n/m:=\lambda\leq 1$, we characterize the distribution of the
standardized $U_{\mathrm{cross}}$ as

$\displaystyle\biggl{(}1-\frac{m}{n+m}\varepsilon_{n}\biggr{)}Z_{1}+\varepsilon_{n}\frac{m}{n+m}\sqrt{\frac{n}{m}}Z_{2}\sim
N\biggl{(}0,\biggl{(}1-\frac{\varepsilon_{n}}{1+\lambda}\biggr{)}^{2}+\frac{\varepsilon_{n}^{2}\lambda}{(1+\lambda)^{2}}\biggr{)}.$

Thus, for any $t\in\mathbb{R}$, we have the identity:

$\displaystyle\bigg{|}\mathbb{P}\biggl{(}\frac{\sqrt{2n}U_{\mathrm{cross}}}{\sqrt{\mathrm{Var}[Y]}}\leq
t\biggr{)}-\Phi(t)\bigg{|}=\bigg{|}\Phi\biggl{(}t\bigg{\\{}\biggl{(}1-\frac{\varepsilon_{n}}{1+\lambda}\biggr{)}^{2}+\frac{\varepsilon_{n}^{2}\lambda}{(1+\lambda)^{2}}\bigg{\\}}^{-1/2}\biggr{)}-\Phi(t)\bigg{|}.$

Take $t=1$. Then for sufficiently large $n$, we can guarantee that
$\varepsilon_{n}\in(0,1/2)$ is sufficiently small, ensuring that

$\displaystyle\bigg{|}\mathbb{P}\biggl{(}\frac{\sqrt{2n}U_{\mathrm{cross}}}{\sqrt{\mathrm{Var}[Y]}}\leq
t\biggr{)}-\Phi(t)\bigg{|}\,\geq\,$ $\displaystyle
C_{1}\Bigg{|}1-\bigg{\\{}\biggl{(}1-\frac{\varepsilon_{n}}{1+\lambda}\biggr{)}^{2}+\frac{\varepsilon_{n}^{2}\lambda}{(1+\lambda)^{2}}\bigg{\\}}^{-1/2}\Bigg{|}$
$\displaystyle\geq\,$ $\displaystyle
C_{2}\bigg{|}\bigg{\\{}\biggl{(}1-\frac{\varepsilon_{n}}{1+\lambda}\biggr{)}^{2}+\frac{\varepsilon_{n}^{2}\lambda}{(1+\lambda)^{2}}\bigg{\\}}^{1/2}-1\bigg{|}$
$\displaystyle=\,$ $\displaystyle
C_{2}\bigg{|}\sqrt{\frac{(1-\varepsilon_{n})^{2}+\lambda}{1+\lambda}}-1\bigg{|}=\frac{C_{2}}{\sqrt{1+\lambda}}(\sqrt{1+\lambda}-\sqrt{(1-\varepsilon_{n})^{2}+\lambda})$
$\displaystyle\geq\,$
$\displaystyle\frac{C_{3}\varepsilon_{n}}{1+\lambda}\geq\frac{C_{3}}{2}\varepsilon_{n}.$

The claim now follows by noting that
$\varepsilon_{n}=\sqrt{\epsilon_{n}}/2\geq\Delta_{\mathrm{MSPE}}^{1/2}/2$.

######  Remark 2.

We specifically analyzed the estimators $\widehat{f}_{1}$ and
$\widehat{f}_{2}$ presented in (23) to demonstrate a non-trivial role of
$\Delta_{\mathrm{Stability}}$. In fact, the same proof goes through with the
following simpler estimators

$\displaystyle\widehat{f}_{1}(x)=\widehat{f}_{2}(x)=\sqrt{\frac{\epsilon_{n}}{2}}x\quad\text{for
all $x\in\mathbb{R}$,}$

which satisfy $\Delta_{\mathrm{MSPE}}=\epsilon_{n}$. Moreover, we have
$\Delta_{\mathrm{Stability}}=0$ as $\widehat{f}_{1}$ and $\widehat{f}_{2}$ are
independent of the data. This implies that the same conclusion in Theorem 3
also holds for the plug-in estimator $U_{\mathrm{plug}}$ if we set
$\widehat{f}(x)=\sqrt{\epsilon_{n}/2}x$ in the definition of
$U_{\mathrm{plug}}$.

###  C.8 Proof of Theorem 4

We first remark that when $\widehat{f}$ is conditioned, $U_{\mathrm{single}}$
is essentially the oracle version of the semi-supervised U-statistic where $f$
is unknown. Therefore the proof of Theorem 3 remains valid for
$U_{\mathrm{single}}$ with the terms involving $\Delta_{\mathrm{MSPE}}$ and
$\Delta_{\mathrm{Stability}}$ being zero. In particular, we have the following
conditional guarantee:

$\displaystyle\sup_{t\in\mathbb{R}}\bigg{|}\mathbb{P}\biggl{(}\frac{\sqrt{n}(U_{\mathrm{single}}-\psi)}{\sqrt{\smash[b]{\Lambda_{n,m,\widehat{f}}}}}\leq
t\,\bigg{|}\,\widehat{f}\biggr{)}-\Phi(t)\bigg{|}\ \leq\ $ $\displaystyle
C\Bigg{\\{}\frac{M_{3,\ell_{1}}+\mathbb{E}[|\widehat{f}(X)-\mathbb{E}[\widehat{f}(X)\,|\,\widehat{f}]|^{3}\,|\,\widehat{f}]}{\sqrt{n}\sigma_{1}^{3}}$
$\displaystyle+\frac{(M_{2,\ell_{1}}^{1/2}+\\{\mathbb{E}[|\widehat{f}(X)-\mathbb{E}[\widehat{f}(X)\,|\,\widehat{f}]|^{2}\,|\,\widehat{f}]\\}^{1/2}+\sigma_{1})\sigma_{\ell}}{\sqrt{n-r}\sigma_{1}^{2}}\Bigg{\\}}.$

Now by taking the expectation over $\widehat{f}$ on both sides and using
Jensen’s inequality, we have

$\displaystyle\sup_{t\in\mathbb{R}}\bigg{|}\mathbb{P}\biggl{(}\frac{\sqrt{n}(U_{\mathrm{single}}-\psi)}{\sqrt{\smash[b]{\Lambda_{n,m,\widehat{f}}}}}\leq
t\biggr{)}-\Phi(t)\bigg{|}\ \leq\ $
$\displaystyle\mathbb{E}\Biggl{[}\sup_{t\in\mathbb{R}}\bigg{|}\mathbb{P}\biggl{(}\frac{\sqrt{n}(U_{\mathrm{single}}-\psi)}{\sqrt{\smash[b]{\Lambda_{n,m,\widehat{f}}}}}\leq
t\,\bigg{|}\,\widehat{f}\biggr{)}-\Phi(t)\bigg{|}\Biggr{]}$
$\displaystyle\leq\ $ $\displaystyle
C\Bigg{\\{}\frac{M_{3,\ell_{1}}+M_{3,\widehat{f}}}{\sqrt{n}\sigma_{1}^{3}}+\frac{(M_{2,\ell_{1}}^{1/2}+M_{2,\widehat{f}}^{1/2}+\sigma_{1})\sigma_{\ell}}{\sqrt{n-r}\sigma_{1}^{2}}\Bigg{\\}}.$

This completes the proof of Theorem 4.

###  C.9 Proof of Theorem 5

In this proof, we begin by addressing a simple case and gradually increase the
generality of the problem setting. In particular, Section C.9.1 focuses on the
setting where the kernel $\ell$ has order one and is uniformly bounded by some
constant. We then extend this result to unbounded kernels of order one in
Section C.9.2. Lastly, Section C.9.3 extends the result to unbounded kernels
of arbitrary order. By doing so, we can effectively convey the main idea
behind the proof without complicating the notation from the beginning.

####  C.9.1 Simplest Case: Bounded Kernel of Order One

In this subsection, we assume that the kernel $\ell$ has order one, i.e.,
$\ell(y)=\ell_{1}(y)$. Given the distribution $P$ of $(X,Y)$ in the local
asymptotic minimax lower bound, we also assume that the related quantities
$|\ell_{1}(y)-\psi_{1}(x)|$ and $|\psi_{1}(x)-\mathbb{E}_{P}[\psi_{1}(X)]|$
where $\psi_{1}(\cdot)=\mathbb{E}_{P}[\ell_{1}(Y)\,|\,X=\cdot]$ are uniformly
bounded by some constant $K$ for all values of $(x,y)$ on the domain
$\mathcal{X}\times\mathcal{Y}$ of $(X,Y)$.

Given the density function $p$ of $P$ with respect to the Lebesgue
measure222We assume this for notational convenience and the same proof holds
for cases where the density is defined with respect to some other base
measure., consider a tilted density $p_{\epsilon_{1},\epsilon_{2}}$ defined as

$\displaystyle
p_{\epsilon_{1},\epsilon_{2}}(x,y):=p(x,y)\\{1+\epsilon_{1}k_{1}(x,y)\\}\\{1+\epsilon_{2}k_{2}(x)\\}.$

Here $\epsilon_{1},\epsilon_{2}$ are some real numbers and
$k_{1}:\mathcal{X}\times\mathcal{Y}\mapsto\mathbb{R},\,k_{2}:\mathcal{X}\mapsto\mathbb{R}$
are some functions. Writing the conditional density of $Y\,|\,X$ and the
marginal density of $X$ as $p_{Y\mkern 1.0mu|\mkern 1.0muX}$ and $p_{X}$,
respectively, we assume that

$\displaystyle\int_{\mathcal{Y}}k_{1}(x,y)p_{Y\mkern 1.0mu|\mkern
1.0muX}(y\,|\,x)dy=0\;\text{for all $x\in\mathcal{X}$ and
}\int_{\mathcal{X}}k_{2}(x)p_{X}(x)dx=0.$ (24)

Moreover, for some given $K>0$, assume that
$\|k_{1}\|_{\infty}:=\sup_{(x,y)\in\mathcal{X}\times\mathcal{Y}}|k_{1}(x,y)|\leq
K$, $\|k_{2}\|_{\infty}:=\sup_{x\in\mathcal{X}}|k_{2}(x)|\leq K$,
$|\epsilon_{1}|<1/K,|\epsilon_{2}|<1/K$ so that
$p_{\epsilon_{1},\epsilon_{2}}$ is a valid density function. The constructed
tilted density $p_{\epsilon_{1},\epsilon_{2}}$ satisfies

$\displaystyle\frac{\partial}{\partial\epsilon_{1}}p_{\epsilon_{1},\epsilon_{2}}(x,y)=p(x,y)k_{1}(x,y)\\{1+\epsilon_{2}k_{2}(x)\\},$
$\displaystyle\frac{\partial}{\partial\epsilon_{2}}p_{\epsilon_{1},\epsilon_{2}}(x,y)=p(x,y)\\{1+\epsilon_{1}k_{1}(x,y)\\}k_{2}(x),$
$\displaystyle\frac{\partial}{\partial\epsilon_{1}}\log
p_{\epsilon_{1},\epsilon_{2}}(x,y)=\frac{k_{1}(x,y)}{\\{1+\epsilon_{1}k_{1}(x,y)\\}}\quad\text{and}$
$\displaystyle\frac{\partial}{\partial\epsilon_{2}}\log
p_{\epsilon_{1},\epsilon_{2}}(x,y)=\frac{k_{2}(x)}{1+\epsilon_{2}k_{2}(x)},$

and these alternative expressions will be used through the proof.

Note that

$\displaystyle\int_{\mathcal{Y}}\int_{\mathcal{X}}\frac{\partial}{\partial\epsilon_{1}}p_{\epsilon_{1},\epsilon_{2}}(x,y)dxdy=\int_{\mathcal{X}}\underbrace{\int_{\mathcal{Y}}k_{1}(x,y)p_{Y\mkern
1.0mu|\mkern
1.0muX}(y\,|\,x)dy}_{=0}\\{1+\epsilon_{2}k_{2}(x)\\}p_{X}(x)dx=0,$
$\displaystyle\int_{\mathcal{Y}}\int_{\mathcal{X}}\frac{\partial}{\partial\epsilon_{2}}p_{\epsilon_{1},\epsilon_{2}}(x,y)dxdy=\int_{\mathcal{X}}\underbrace{\int_{\mathcal{Y}}\\{1+\epsilon_{1}k_{1}(x,y)\\}p_{Y\mkern
1.0mu|\mkern 1.0muX}(y\,|\,x)dy}_{=1}p_{X}(x)k_{2}(x)dx=0,$

which implies that for any given $\epsilon_{1},\epsilon_{2}$,

$\displaystyle\mathbb{E}_{P_{\epsilon_{1},\epsilon_{2}}}\biggl{[}\frac{\partial}{\partial\epsilon_{1}}\log
p_{\epsilon_{1},\epsilon_{2}}(X,Y)\biggr{]}=\mathbb{E}_{P_{\epsilon_{1},\epsilon_{2}}}\biggl{[}\frac{\partial}{\partial\epsilon_{2}}\log
p_{\epsilon_{1},\epsilon_{2}}(X,Y)\biggr{]}=0,$

where $\mathbb{E}_{P_{\epsilon_{1},\epsilon_{2}}}$ denotes the expectation
with respect to $(X,Y)$ from the distribution $P_{\epsilon_{1},\epsilon_{2}}$
with density $p_{\epsilon_{1},\epsilon_{2}}$. We also have that

$\displaystyle\mathbb{E}_{P_{\epsilon_{1},\epsilon_{2}}}\biggl{[}\frac{\partial}{\partial\epsilon_{1}}\log
p_{\epsilon_{1},\epsilon_{2}}(X,Y)\frac{\partial}{\partial\epsilon_{2}}\log
p_{\epsilon_{1},\epsilon_{2}}(X,Y)\biggr{]}$ (25) $\displaystyle={}$
$\displaystyle\int_{\mathcal{X}}\underbrace{\int_{\mathcal{Y}}k_{1}(x,y)p_{Y\mkern
1.0mu|\mkern 1.0muX}(y\,|\,x)dy}_{=0}k_{2}(x)p_{X}(x)dx=0.$

Having presented some preliminary results, we now describe the specific
setting that we consider:

  * •

Denote $Z_{n,m}:=\\{(X_{i},Y_{i})\\}_{i=1}^{n}\cup\\{X_{i}\\}_{i=n+1}^{n+m}$,
which are mutually independent observations drawn from $(X,Y)\sim
P_{\epsilon_{1},\epsilon_{2}}$ and $X\sim P_{X,\epsilon_{2}}$ with density
$p_{X,\epsilon_{2}}$, which is the marginal density of $X$ given as
$p_{X,\epsilon_{2}}(x)=p_{X}(x)\\{1+\epsilon_{2}k_{2}(x)\\}$.

  * •

Consider some generic estimator $\widehat{\psi}(Z_{n,m})=\widehat{\psi}$ of
the parameter

$\displaystyle\psi(P_{\epsilon_{1},\epsilon_{2}}):=\psi_{\epsilon_{1},\epsilon_{2}}=\int_{\mathcal{X}}\int_{\mathcal{Y}}\ell(y)p_{\epsilon_{1},\epsilon_{2}}(x,y)dydx.$

The parameter is differentiable with respect to $\epsilon_{1}$ and
$\epsilon_{2}$, satisfying

$\displaystyle\frac{\partial}{\partial\epsilon_{1}}\psi_{\epsilon_{1},\epsilon_{2}}=\int_{\mathcal{X}}\int_{\mathcal{Y}}\ell(y)\frac{\partial}{\partial\epsilon_{1}}p_{\epsilon_{1},\epsilon_{2}}(x,y)dydx,$
$\displaystyle\frac{\partial}{\partial\epsilon_{2}}\psi_{\epsilon_{1},\epsilon_{2}}=\int_{\mathcal{X}}\int_{\mathcal{Y}}\ell(y)\frac{\partial}{\partial\epsilon_{2}}p_{\epsilon_{1},\epsilon_{2}}(x,y)dydx$

under the additional assumption that

$\displaystyle\int_{\mathcal{X}}\int_{\mathcal{Y}}|\ell(y)|p(x,y)dxdy<\infty.$

This additional condition allows us to interchange differentiation and
integration. Note that this moment condition is fulfilled as we assume the
$2+\upsilon$ finite moment of $\ell$ for $\upsilon>0$.

  * •

To apply the van Trees inequality, we specify the prior on $\epsilon_{1}$ and
$\epsilon_{2}$. More specifically, assume that $\epsilon_{1}$ and
$\epsilon_{2}$ are independent and follow the same distribution with the
cosine density

$\displaystyle g(u)=\frac{1}{\delta}\cos^{2}\biggl{(}\frac{\pi
u}{2\delta}\biggr{)}\quad\text{supported on $[-\delta,\delta]$,}$

where $\delta\in(0,K^{-1})$ will be specified later. Note that
$g(\delta)=g(-\delta)=0$ and

$\displaystyle\int_{-\delta}^{\delta}\frac{\partial}{\partial u}g(u)du=0.$
(26)

The specific choice of cosine density is not crucial. In fact, the proof
follows for any centered prior distribution that satisfies conditions in the
van Trees inequality (e.g., Polyanskiy and Wu,, 2023, Theorem 29.3).

##### A lower bound for Bayes risk via van Trees inequality.

Now, the integration by parts under the condition that
$g(\delta)=g(-\delta)=0$ yields

$\displaystyle\int_{-\delta}^{\delta}(\widehat{\psi}-\psi_{\epsilon_{1},\epsilon_{2}})\frac{\partial}{\partial\epsilon_{1}}\Biggl{[}\prod_{i=1}^{n}p_{\epsilon_{1},\epsilon_{2}}(x_{i},y_{i})\prod_{j=n+1}^{n+m}p_{X,\epsilon_{2}}(x_{j})g(\epsilon_{1})g(\epsilon_{2})\Biggr{]}d\epsilon_{1}$
$\displaystyle=\ $
$\displaystyle\int_{-\delta}^{\delta}\biggl{(}\frac{\partial}{\partial\epsilon_{1}}\psi_{\epsilon_{1},\epsilon_{2}}\biggr{)}\Biggl{[}\prod_{i=1}^{n}p_{\epsilon_{1},\epsilon_{2}}(x_{i},y_{i})\prod_{j=n+1}^{n+m}p_{X,\epsilon_{2}}(x_{j})g(\epsilon_{1})g(\epsilon_{2})\Biggr{]}d\epsilon_{1}.$

Similarly,

$\displaystyle\int_{-\delta}^{\delta}(\widehat{\psi}-\psi_{\epsilon_{1},\epsilon_{2}})\frac{\partial}{\partial\epsilon_{2}}\Biggl{[}\prod_{i=1}^{n}p_{\epsilon_{1},\epsilon_{2}}(x_{i},y_{i})\prod_{j=n+1}^{n+m}p_{X,\epsilon_{2}}(x_{j})g(\epsilon_{1})g(\epsilon_{2})\Biggr{]}d\epsilon_{2}$
$\displaystyle=\ $
$\displaystyle\int_{-\delta}^{\delta}\biggl{(}\frac{\partial}{\partial\epsilon_{2}}\psi_{\epsilon_{1},\epsilon_{2}}\biggr{)}\Biggl{[}\prod_{i=1}^{n}p_{\epsilon_{1},\epsilon_{2}}(x_{i},y_{i})\prod_{j=n+1}^{n+m}p_{X,\epsilon_{2}}(x_{j})g(\epsilon_{1})g(\epsilon_{2})\Biggr{]}d\epsilon_{2}.$

Denoting the expectation taken over both $(\epsilon_{1},\epsilon_{2})$ and
$Z_{n,m}$ as $\mathbb{E}_{\epsilon_{1},\epsilon_{2},Z_{n,m}}$, these two
identities show that

$\displaystyle\mathbb{E}_{\epsilon_{1},\epsilon_{2},Z_{n,m}}\biggl{[}(\widehat{\psi}-\psi_{\epsilon_{1},\epsilon_{2}})\underbrace{\frac{\partial}{\partial\epsilon_{1}}\biggl{\\{}\log\biggl{(}\prod_{i=1}^{n}p_{\epsilon_{1},\epsilon_{2}}(X_{i},Y_{i})\prod_{j=n+1}^{n+m}p_{X,\epsilon_{2}}(X_{j})g(\epsilon_{1})g(\epsilon_{2})\biggr{)}\biggr{\\}}}_{:=\eta_{1}}\biggr{]}$
$\displaystyle=\ $
$\displaystyle\mathbb{E}_{\epsilon_{1},\epsilon_{2}}\biggl{[}\frac{\partial}{\partial\epsilon_{1}}\psi_{\epsilon_{1},\epsilon_{2}}\biggr{]}:=\tau_{1}$

and

$\displaystyle\mathbb{E}_{\epsilon_{1},\epsilon_{2},Z_{n,m}}\biggl{[}(\widehat{\psi}-\psi_{\epsilon_{1},\epsilon_{2}})\underbrace{\frac{\partial}{\partial\epsilon_{2}}\biggl{\\{}\log\biggl{(}\prod_{i=1}^{n}p_{\epsilon_{1},\epsilon_{2}}(X_{i},Y_{i})\prod_{j=n+1}^{n+m}p_{X,\epsilon_{2}}(X_{j})g(\epsilon_{1})g(\epsilon_{2})\biggr{)}\biggr{\\}}}_{:=\eta_{2}}\biggr{]}$
$\displaystyle=\ $
$\displaystyle\mathbb{E}_{\epsilon_{1},\epsilon_{2}}\biggl{[}\frac{\partial}{\partial\epsilon_{2}}\psi_{\epsilon_{1},\epsilon_{2}}\biggr{]}:=\tau_{2}.$

By letting
$\bm{\eta}:=(\eta_{1},\eta_{2})^{\top},\bm{\tau}:=(\tau_{1},\tau_{2})^{\top}$
and $\bm{u}:=(u_{1},u_{2})^{\top}$, the Cauchy–Schwarz inequality yields

$\displaystyle\mathbb{E}_{\epsilon_{1},\epsilon_{2},Z_{n,m}}\bigl{[}(\widehat{\psi}-\psi_{\epsilon_{1},\epsilon_{2}})^{2}\bigr{]}~{}\geq~{}$
$\displaystyle\sup_{\bm{u}\neq
0}\frac{(\bm{u}^{\top}\bm{\tau})^{2}}{\bm{u}^{\top}\mathbb{E}[\bm{\eta}\bm{\eta}^{\top}]\bm{u}}=\sup_{\bm{u}:\|\bm{u}\|_{2}=1}\bigl{\\{}\bm{u}^{\top}(\mathbb{E}[\bm{\eta}\bm{\eta}^{\top}])^{-1/2}\bm{\tau}\bigr{\\}}^{2}$
$\displaystyle=\ $
$\displaystyle\bm{\tau}^{\top}(\mathbb{E}[\bm{\eta}\bm{\eta}^{\top}])^{-1}\bm{\tau}.$

To explicitly compute the inverse of $\mathbb{E}[\bm{\eta}\bm{\eta}^{\top}]$,
observe that

$\displaystyle\eta_{1}=\sum_{i=1}^{n}\frac{\partial}{\partial\epsilon_{1}}\log
p_{\epsilon_{1},\epsilon_{2}}(X_{i},Y_{i})+\frac{\partial}{\partial\epsilon_{1}}\log
g(\epsilon_{1}).$

Hence, using the condition (26),

$\displaystyle\mathbb{E}_{\epsilon_{1},\epsilon_{2},Z_{n,m}}[\eta_{1}^{2}]~{}=~{}$
$\displaystyle
n\mathbb{E}_{\epsilon_{1},\epsilon_{2},X,Y}\biggl{[}\biggl{(}\frac{\partial}{\partial\epsilon_{1}}\log
p_{\epsilon_{1},\epsilon_{2}}(X,Y)\biggr{)}^{2}\biggr{]}+\mathbb{E}_{\epsilon_{1}}\biggl{[}\biggl{(}\frac{\partial}{\partial\epsilon_{1}}\log
g(\epsilon_{1})\biggr{)}^{2}\biggr{]}$ $\displaystyle=~{}$ $\displaystyle
n\mathbb{E}_{\epsilon_{1},\epsilon_{2},X,Y}\biggl{[}\biggl{(}\frac{k_{1}(X,Y)}{1+\epsilon_{1}k_{1}(X,Y)}\biggr{)}^{2}\biggr{]}+\frac{\pi^{2}}{\delta^{2}}$
$\displaystyle:=\ $ $\displaystyle
nT_{\epsilon_{1}}+\frac{\pi^{2}}{\delta^{2}}.$

Next for $\eta_{2}$, we have

$\displaystyle\eta_{2}\ =\ $
$\displaystyle\sum_{i=1}^{n}\frac{\partial}{\partial\epsilon_{2}}\log
p_{\epsilon_{1},\epsilon_{2}}(X_{i},Y_{i})+\sum_{j=n+1}^{n+m}\frac{\partial}{\partial\epsilon_{2}}\log
p_{X,\epsilon_{2}}(X_{j})+\frac{\partial}{\partial\epsilon_{2}}\log
g(\epsilon_{2})$ $\displaystyle=\ $
$\displaystyle\sum_{i=1}^{n+m}\frac{\partial}{\partial\epsilon_{2}}\log
p_{X,\epsilon_{2}}(X_{i})+\frac{\partial}{\partial\epsilon_{2}}\log
g(\epsilon_{2}),$

and therefore

$\displaystyle\mathbb{E}_{\epsilon_{1},\epsilon_{2},Z_{n,m}}[\eta_{2}^{2}]\ =\
$
$\displaystyle(n+m)\mathbb{E}_{\epsilon_{2},X}\biggl{[}\biggl{(}\frac{k_{2}(X)}{1+\epsilon_{2}k_{2}(X)}\biggr{)}^{2}\biggr{]}+\frac{\pi^{2}}{\delta^{2}}$
$\displaystyle:=\ $
$\displaystyle(n+m)T_{\epsilon_{2}}+\frac{\pi^{2}}{\delta^{2}}.$

For the off-diagonal term, we need to consider the expectation of
$\eta_{1}\eta_{2}$, which turns out to be zero. Specifically, observe that

$\displaystyle\mathbb{E}_{\epsilon_{1},\epsilon_{2},Z_{n,m}}[\eta_{1}\eta_{2}]\
=\ $
$\displaystyle\mathbb{E}_{\epsilon_{1},\epsilon_{2},Z_{n,m}}\biggl{[}\bigg{\\{}\sum_{i=1}^{n}\frac{\partial}{\partial\epsilon_{1}}\log
p_{\epsilon_{1},\epsilon_{2}}(X_{i},Y_{i})+\frac{\partial}{\partial\epsilon_{1}}\log
g(\epsilon_{1})\bigg{\\}}$ $\displaystyle\hskip
50.00008pt\times\bigg{\\{}\sum_{i=1}^{n+m}\frac{\partial}{\partial\epsilon_{2}}\log
p_{X,\epsilon_{2}}(X_{j})+\frac{\partial}{\partial\epsilon_{2}}\log
g(\epsilon_{2})\bigg{\\}}\biggr{]}$ $\displaystyle=\ $
$\displaystyle\sum_{i=1}^{n}\sum_{j=1}^{n+m}\mathbb{E}_{\epsilon_{1},\epsilon_{2},Z_{n,m}}\biggl{[}\frac{\partial}{\partial\epsilon_{1}}\log
p_{\epsilon_{1},\epsilon_{2}}(X_{i},Y_{i})\frac{\partial}{\partial\epsilon_{2}}\log
p_{X,\epsilon_{2}}(X_{j})\biggr{]}$ $\displaystyle+\ $
$\displaystyle\sum_{i=1}^{n}\mathbb{E}_{\epsilon_{1},\epsilon_{2},X_{i},Y_{i}}\biggl{[}\frac{\partial}{\partial\epsilon_{1}}\log
p_{\epsilon_{1},\epsilon_{2}}(X_{i},Y_{i})\biggr{]}\mathbb{E}_{\epsilon_{2}}\biggl{[}\frac{\partial}{\partial\epsilon_{2}}\log
g(\epsilon_{2})\biggr{]}$ $\displaystyle+\ $
$\displaystyle\sum_{j=1}^{n+m}\mathbb{E}_{\epsilon_{1}}\biggl{[}\frac{\partial}{\partial\epsilon_{1}}\log
g(\epsilon_{1})\biggr{]}\mathbb{E}_{X_{j},\epsilon_{2}}\biggl{[}\frac{\partial}{\partial\epsilon_{2}}\log
p_{X,\epsilon_{2}}(X_{j})\biggr{]}$ $\displaystyle+\ $
$\displaystyle\mathbb{E}_{\epsilon_{1}}\biggl{[}\frac{\partial}{\partial\epsilon_{1}}\log
g(\epsilon_{1})\biggr{]}\mathbb{E}_{\epsilon_{2}}\biggl{[}\frac{\partial}{\partial\epsilon_{2}}\log
g(\epsilon_{2})\biggr{]}$ $\displaystyle=\ $ $\displaystyle 0,$

where we use the conditions that

$\displaystyle\mathbb{E}_{\epsilon_{1}}\biggl{[}\frac{\partial}{\partial\epsilon_{1}}\log
g(\epsilon_{1})\biggr{]}=\mathbb{E}_{\epsilon_{2}}\biggl{[}\frac{\partial}{\partial\epsilon_{2}}\log
g(\epsilon_{2})\biggr{]}=0$

and the below due to the identity (LABEL:Eq:_equality_condition):

$\displaystyle\mathbb{E}_{\epsilon_{1},\epsilon_{2},X,Y}\biggl{[}\frac{\partial}{\partial\epsilon_{1}}\log
p_{\epsilon_{1},\epsilon_{2}}(X,Y)\frac{\partial}{\partial\epsilon_{2}}\log
p_{X,\epsilon_{2}}(X)\biggr{]}$ $\displaystyle=~{}$
$\displaystyle\mathbb{E}_{\epsilon_{1},\epsilon_{2},X,Y}\biggl{[}\frac{\partial}{\partial\epsilon_{1}}\log
p_{\epsilon_{1},\epsilon_{2}}(X,Y)\frac{\partial}{\partial\epsilon_{2}}\log
p_{\epsilon_{1},\epsilon_{2}}(X,Y)\biggr{]}=0.$

Putting things together yields

$\displaystyle\mathbb{E}_{\epsilon_{1},\epsilon_{2},Z_{n,m}}\bigl{[}(\widehat{\psi}-\psi_{\epsilon_{1},\epsilon_{2}})^{2}\bigr{]}~{}\geq{}$
$\displaystyle\begin{pmatrix}\tau_{1}&\tau_{2}\end{pmatrix}\begin{pmatrix}nT_{\epsilon_{1}}+\frac{\pi^{2}}{\delta^{2}}&0\\\
0&(n+m)T_{\epsilon_{2}}+\frac{\pi^{2}}{\delta^{2}}\end{pmatrix}^{-1}\begin{pmatrix}\tau_{1}\\\
\tau_{2}\end{pmatrix}$ (27) $\displaystyle={}$
$\displaystyle\frac{\tau_{1}^{2}}{nT_{\epsilon_{1}}+\frac{\pi^{2}}{\delta^{2}}}+\frac{\tau_{2}^{2}}{(n+m)T_{\epsilon_{2}}+\frac{\pi^{2}}{\delta^{2}}},$

where we recall that

$\displaystyle\tau_{1}=\mathbb{E}_{\epsilon_{1},\epsilon_{2}}\biggl{[}\frac{\partial}{\partial\epsilon_{1}}\psi_{\epsilon_{1},\epsilon_{2}}\biggr{]},\quad\tau_{2}=\mathbb{E}_{\epsilon_{1},\epsilon_{2}}\biggl{[}\frac{\partial}{\partial\epsilon_{2}}\psi_{\epsilon_{1},\epsilon_{2}}\biggr{]},$
$\displaystyle
T_{\epsilon_{1}}=\mathbb{E}_{\epsilon_{1},\epsilon_{2},X,Y}\biggl{[}\biggl{(}\frac{k_{1}(X,Y)}{1+\epsilon_{1}k_{1}(X,Y)}\biggr{)}^{2}\biggr{]}\quad\text{and}$
$\displaystyle
T_{\epsilon_{2}}=\mathbb{E}_{\epsilon_{2},X}\biggl{[}\biggl{(}\frac{k_{2}(X)}{1+\epsilon_{2}k_{2}(X)}\biggr{)}^{2}\biggr{]}.$

##### A refined expression for the lower bound.

Now take $\delta=Kn^{-1/2}$ and assume that $n>K^{4}$. Under this assumption,
the choice of $\delta=Kn^{-1/2}$ satisfies $\delta<K^{-1}$, which ensures that
$p_{\epsilon_{1},\epsilon_{2}}$ is a valid density. Under this choice, we have
$|1+\epsilon_{1}k_{1}(X,Y)|\geq 1-1/\sqrt{n}$ and
$|1+\epsilon_{2}k_{2}(X)|\geq 1-1/\sqrt{n}$ with probability one, provided
that $\|k_{1}\|_{\infty}\leq K$ and $\|k_{2}\|_{\infty}\leq K$. Using this, we
can verify that

$\displaystyle T_{\epsilon_{1}}~{}=~{}$
$\displaystyle\int_{\mathcal{X}}\int_{\mathcal{Y}}\int_{-\delta}^{\delta}\int_{-\delta}^{\delta}\frac{k_{1}^{2}(x,y)}{1+\epsilon_{1}k_{1}(x,y)}p_{Y\mkern
1.0mu|\mkern
1.0muX}(y\,|\,x)p_{X}(x)\\{1+\epsilon_{2}k_{2}(x)\\}g(\epsilon_{1})g(\epsilon_{2})dxdyd\epsilon_{1}d\epsilon_{2}$
$\displaystyle\leq~{}$
$\displaystyle\frac{1}{1-1/\sqrt{n}}\int_{\mathcal{X}}\int_{\mathcal{Y}}k_{1}^{2}(x,y)p(x,y)dxdy$

and

$\displaystyle T_{\epsilon_{2}}~{}=~{}$
$\displaystyle\int_{\mathcal{X}}\int_{-\delta}^{\delta}\frac{k_{2}^{2}(x)}{1+\epsilon_{2}k_{2}(x)}p_{X}(x)g(\epsilon_{2})dxd\epsilon_{2}~{}\leq~{}\frac{1}{1-1/\sqrt{n}}\int_{\mathcal{X}}k_{2}^{2}(x)p_{X}(x)dx.$

Observe that

$\displaystyle\frac{\partial}{\partial\epsilon_{1}}\psi_{\epsilon_{1},\epsilon_{2}}~{}=~{}$
$\displaystyle\int_{\mathcal{X}}\int_{\mathcal{Y}}\ell_{1}(y)\frac{\partial}{\partial\epsilon_{1}}p_{\epsilon_{1},\epsilon_{2}}(x,y)dxdy$
$\displaystyle=~{}$
$\displaystyle\int_{\mathcal{X}}\int_{\mathcal{Y}}\ell_{1}(y)p(x,y)k_{1}(x,y)\\{1+\epsilon_{2}k_{2}(x)\\}dxdy.$

This observation together with $\mathbb{E}_{\epsilon_{2}}[\epsilon_{2}]=0$
yields

$\displaystyle\tau_{1}=\mathbb{E}_{\epsilon_{1},\epsilon_{2}}\biggl{[}\frac{\partial}{\partial\epsilon_{1}}\psi_{\epsilon_{1},\epsilon_{2}}\biggr{]}=\int_{\mathcal{X}}\int_{\mathcal{Y}}\ell_{1}(y)k_{1}(x,y)p(x,y)dxdy.$

Similarly,

$\displaystyle\tau_{2}=\mathbb{E}_{\epsilon_{1},\epsilon_{2}}\biggl{[}\frac{\partial}{\partial\epsilon_{2}}\psi_{\epsilon_{1},\epsilon_{2}}\biggr{]}=\int_{\mathcal{X}}\int_{\mathcal{Y}}\ell_{1}(y)k_{2}(x)p(x,y)dxdy=\int_{\mathcal{X}}\psi_{1}(x)k_{2}(x)p_{X}(x)dx,$

where $\psi_{1}(x)=\int_{\mathcal{Y}}\ell_{1}(y)p_{Y\mkern 1.0mu|\mkern
1.0muX}(y\,|\,x)dy$.

##### Relating Bayes risk to minimax risk.

Let $(\widetilde{X},\widetilde{Y})$ be a random vector from the distribution
$P$ with density $p$ without perturbation. Note that
$\mathbb{E}[\ell_{1}(\widetilde{Y})k_{1}(\widetilde{X},\widetilde{Y})]=\mathbb{E}[\\{\ell_{1}(\widetilde{Y})-\psi_{1}(\widetilde{X})\\}k_{1}(\widetilde{X},\widetilde{Y})]$
and
$\mathbb{E}[\psi_{1}(\widetilde{X})k_{2}(\widetilde{X})]=\mathbb{E}[\\{\psi_{1}(\widetilde{X})-\mathbb{E}[\psi_{1}(\widetilde{X})]\\}k_{2}(\widetilde{X})]$
due to our conditions for $k_{1}$ and $k_{2}$ in (24). Then the established
expressions for $\tau_{1},\tau_{2},T_{\epsilon_{1}},T_{\epsilon_{2}}$ and
$\delta=Kn^{-1/2}$ applied to the lower bound (27) yield

$\displaystyle\mathbb{E}_{\epsilon_{1},\epsilon_{2},Z_{n,m}}\bigl{[}(\widehat{\psi}-\psi_{\epsilon_{1},\epsilon_{2}})^{2}\bigr{]}$
$\displaystyle\geq~{}$
$\displaystyle\frac{\bigl{(}\mathbb{E}[\\{\ell_{1}(\widetilde{Y})-\psi_{1}(\widetilde{X})\\}k_{1}(\widetilde{X},\widetilde{Y})]\bigr{)}^{2}}{\frac{n}{1-1/\sqrt{n}}\mathbb{E}[k_{1}^{2}(\widetilde{X},\widetilde{Y})]+nK^{-2}\pi^{2}}+\frac{\bigl{(}\mathbb{E}[\\{\psi_{1}(\widetilde{X})-\mathbb{E}[\psi_{1}(\widetilde{X})]\\}k_{2}(\widetilde{X})]\bigr{)}^{2}}{\frac{n+m}{1-1/\sqrt{n}}\mathbb{E}[k_{2}^{2}(\widetilde{X})]+nK^{-2}\pi^{2}},$

which holds for any $n>K^{4}$, $k_{1}\in\mathcal{K}_{1}$ and
$k_{2}\in\mathcal{K}_{2}$ where

$\displaystyle\mathcal{K}_{1}=\bigg{\\{}k:\int_{\mathcal{Y}}k(x,y)p_{Y\mkern
1.0mu|\mkern 1.0muX}(y\,|\,x)dy=0,\ \|k\|_{\infty}\leq
K\bigg{\\}}\quad\text{and}$
$\displaystyle\mathcal{K}_{2}=\bigg{\\{}k:\int_{\mathcal{X}}k(x)p_{X}(x)dx=0,\
\|k\|_{\infty}\leq K\bigg{\\}}.$

Thus for $n>K^{4}$,

$\displaystyle\sup_{k_{1}\in\mathcal{K}_{1},k_{2}\in\mathcal{K}_{2}}\mathbb{E}_{\epsilon_{1},\epsilon_{2},Z_{n,m}}\bigl{[}(\widehat{\psi}-\psi_{\epsilon_{1},\epsilon_{2}})^{2}\bigr{]}\
\geq\ $
$\displaystyle\sup_{k_{1}\in\mathcal{K}_{1}}\frac{\bigl{(}\mathbb{E}[\\{\ell_{1}(\widetilde{Y})-\psi_{1}(\widetilde{X})\\}k_{1}(\widetilde{X},\widetilde{Y})]\bigr{)}^{2}}{\frac{n}{1-1/\sqrt{n}}\mathbb{E}[k_{1}^{2}(\widetilde{X},\widetilde{Y})]+nK^{-2}\pi^{2}}$
$\displaystyle+\ $
$\displaystyle\sup_{k_{2}\in\mathcal{K}_{2}}\frac{\bigl{(}\mathbb{E}[\\{\psi_{1}(\widetilde{X})-\mathbb{E}[\psi_{1}(\widetilde{X})]\\}k_{2}(\widetilde{X})]\bigr{)}^{2}}{\frac{n+m}{1-1/\sqrt{n}}\mathbb{E}[k_{2}^{2}(\widetilde{X})]+nK^{-2}\pi^{2}}.$

Since we assume that $|\ell_{1}(y)-\psi_{1}(x)|$ and
$|\psi_{1}(x)-\mathbb{E}[\psi_{1}(\widetilde{X})]|$ are bounded by $K$ for all
$(x,y)\in\mathcal{X}\times\mathcal{Y}$ so that
$\ell_{1}(\cdot)-\psi_{1}(\cdot)\in\mathcal{K}_{1}$ and
$\psi_{1}(\cdot)-\mathbb{E}[\psi_{1}(\widetilde{X})]\in\mathcal{K}_{2}$. Hence
by taking $k_{1}(x,y)=\ell_{1}(y)-\psi_{1}(x)$ and
$k_{2}(x)=\psi_{1}(x)-\mathbb{E}[\psi_{1}(\widetilde{X})]$, we have

$\displaystyle\inf_{\widehat{\psi}}\sup_{k_{1}\in\mathcal{K}_{1},k_{2}\in\mathcal{K}_{2}}n\mathbb{E}_{\epsilon_{1},\epsilon_{2},Z_{n,m}}\bigl{[}(\widehat{\psi}-\psi_{\epsilon_{1},\epsilon_{2}})^{2}\bigr{]}~{}\geq~{}\frac{\sigma_{1,P}^{4}}{\frac{1}{1-n^{-1/2}}\sigma_{1,P}^{2}+K^{-2}\pi^{2}}+\frac{\sigma_{2,P}^{4}}{\frac{1+m/n}{1-n^{-1/2}}\sigma_{2,P}^{2}+K^{-2}\pi^{2}},$

where we recall
$\sigma_{1,P}^{2}=\mathbb{E}_{P}[\mathrm{Var}_{P}\\{\ell_{1}(Y)\,|\,X\\}]$ and
$\sigma_{2,P}^{2}=\mathrm{Var}_{P}[\psi_{1}(X)]$.

##### Connecting minimax risk with the class $\mathcal{F}_{P}(K/\sqrt{n})$.

Recall $m/n\rightarrow\lambda\in[0,\infty]$. Also note that for any
$k_{1}\in\mathcal{K}_{1}$, $k_{2}\in\mathcal{K}_{2}$,
$\epsilon_{1},\epsilon_{2}\in[-K/\sqrt{n},K/\sqrt{n}]$, the corresponding
tilted distribution $P_{\epsilon_{1},\epsilon_{2}}$ belongs to
$\mathcal{F}_{P}(K^{2}/\sqrt{n})$. Therefore, denoting that the parameter
$\psi$ based on a distribution $Q$ as $\psi_{Q}$, it follows that

$\displaystyle\sup_{Q\in\mathcal{F}_{P}(K^{2}/\sqrt{n})}n\mathbb{E}_{Q}\bigl{[}(\widehat{\psi}-\psi_{Q})^{2}\bigr{]}\geq\frac{\sigma_{1,P}^{4}}{\frac{1}{1-n^{-1/2}}\sigma_{1,P}^{2}+2K^{-2}\pi^{2}}+\frac{\sigma_{2,P}^{4}}{\frac{1+m/n}{1-n^{-1/2}}\sigma_{2,P}^{2}+2K^{-2}\pi^{2}},$

as the supremum becomes larger when it is taken over a larger set.
Consequently

$\displaystyle\liminf_{n\rightarrow\infty}\sup_{Q\in\mathcal{F}_{P}(K^{2}/\sqrt{n})}n\mathbb{E}_{Q}\bigl{[}(\widehat{\psi}-\psi_{Q})^{2}\bigr{]}\geq\frac{\sigma_{1,P}^{4}}{\sigma_{1,P}^{2}+2K^{-2}\pi^{2}}+\frac{\sigma_{2,P}^{4}}{(1+\lambda)\sigma_{2,P}^{2}+2K^{-2}\pi^{2}},$

which concludes

$\displaystyle\liminf_{K\rightarrow\infty}\liminf_{n\rightarrow\infty}\sup_{Q\in\mathcal{F}_{P}(K/\sqrt{n})}n\mathbb{E}_{Q}\bigl{[}(\widehat{\psi}-\psi_{Q})^{2}\bigr{]}\geq\sigma_{1,P}^{2}+\frac{\sigma_{2,P}^{2}}{1+\lambda}.$

####  C.9.2 Extension: Unbounded Kernel of Order One

In the previous subsection, we assume that $\ell_{1}(\cdot)-\psi_{1}(\cdot)$
and $\psi_{1}(\cdot)-\mathbb{E}_{P}[\psi_{1}(X)]$ are uniformly bounded. We
now relax this constraint. The proof remains the same up to here:

$\displaystyle\sup_{k_{1}\in\mathcal{K}_{1},k_{2}\in\mathcal{K}_{2}}\mathbb{E}_{\epsilon_{1},\epsilon_{2},Z_{n,m}}\bigl{[}(\widehat{\psi}-\psi_{\epsilon_{1},\epsilon_{2}})^{2}\bigr{]}~{}\geq~{}$
$\displaystyle\sup_{k_{1}\in\mathcal{K}_{1}}\frac{\bigl{(}\mathbb{E}[\\{\ell_{1}(\widetilde{Y})-\psi_{1}(\widetilde{X})\\}k_{1}(\widetilde{X},\widetilde{Y})]\bigr{)}^{2}}{\frac{n}{1-1/\sqrt{n}}\mathbb{E}[k_{1}^{2}(\widetilde{X},\widetilde{Y})]+nK^{-2}\pi^{2}}$
$\displaystyle+~{}$
$\displaystyle\sup_{k_{2}\in\mathcal{K}_{2}}\frac{\bigl{(}\mathbb{E}[\\{\psi_{1}(\widetilde{X})-\mathbb{E}[\psi_{1}(\widetilde{X})]\\}k_{2}(\widetilde{X})]\bigr{)}^{2}}{\frac{n+m}{1-1/\sqrt{n}}\mathbb{E}[k_{2}^{2}(\widetilde{X})]+nK^{-2}\pi^{2}}.$

Since $\ell_{1}(\cdot)-\psi_{1}(\cdot)$ and
$\psi_{1}(\cdot)-\mathbb{E}_{P}[\psi_{1}(X)]$ are not necessarily bounded, we
cannot set them to be $k_{1}$ and $k_{2}$, respectively. Instead, define a
truncated kernel
$\widetilde{\ell_{1}}(y)=\ell_{1}(y)\mathds{1}(|\ell_{1}(y)|\leq K/2)$, and
set

$\displaystyle
k_{1}(x,y)=\widetilde{\ell_{1}}(y)-\mathbb{E}[\widetilde{\ell_{1}}(Y)\,|\,X=x]:=\widetilde{\ell_{1}}(y)-\widetilde{\psi}_{1}(x),$

which is uniformly bounded by $-K$ and $K$. Under this choice of $k_{1}$,

$\displaystyle\mathbb{E}[\\{\ell_{1}(\widetilde{Y})-\psi_{1}(\widetilde{X})\\}k_{1}(\widetilde{X},\widetilde{Y})]$
$\displaystyle=~{}$
$\displaystyle\mathbb{E}[\\{\ell_{1}(\widetilde{Y})-\psi_{1}(\widetilde{X})\\}\\{\ell_{1}(\widetilde{Y})-\psi_{1}(\widetilde{X})+\widetilde{\ell_{1}}(\widetilde{Y})-\ell_{1}(\widetilde{Y})+\psi_{1}(\widetilde{X})-\widetilde{\psi}_{1}(\widetilde{X})\\}]$
$\displaystyle=~{}$
$\displaystyle\sigma_{1,P}^{2}+\underbrace{\mathbb{E}[\\{\ell_{1}(\widetilde{Y})-\psi_{1}(\widetilde{X})\\}\\{\widetilde{\ell}_{1}(\widetilde{Y})-\ell_{1}(\widetilde{Y})\\}]}_{=V_{1,K}}+\underbrace{\mathbb{E}[\\{\ell_{1}(\widetilde{Y})-\psi_{1}(\widetilde{X})\\}\\{\psi_{1}(\widetilde{X})-\widetilde{\psi}_{1}(\widetilde{X})\\}]}_{=V_{2,K}}.$

By sequentially applying the Cauchy–Schwarz inequality, Hölder’s inequality,
and Markov’s inequality, we have for any $\upsilon>0$,

$\displaystyle
V_{1,K}^{2}\leq\sigma_{1,P}^{2}\mathbb{E}[\\{\widetilde{\ell_{1}}(\widetilde{Y})-\ell_{1}(\widetilde{Y})\\}^{2}]~{}=~{}$
$\displaystyle\sigma_{1,P}^{2}\mathbb{E}[\\{\ell_{1}(\widetilde{Y})\mathds{1}(|\ell_{1}(\widetilde{Y})|>K/2)\\}^{2}]$
$\displaystyle\leq~{}$
$\displaystyle\sigma_{1,P}^{2}\big{\\{}\mathbb{E}[\ell_{1}^{2+2\upsilon}(\widetilde{Y})]\big{\\}}^{\frac{1}{1+\upsilon}}\big{\\{}\mathbb{P}\bigl{(}|\ell_{1}(\widetilde{Y})|>K/2\bigr{)}\big{\\}}^{\frac{1+\upsilon}{\upsilon}}$
$\displaystyle\leq~{}$
$\displaystyle\sigma_{1,P}^{2}\big{\\{}\mathbb{E}[\ell_{1}^{2+2\upsilon}(\widetilde{Y})]\big{\\}}^{\frac{1}{1+\upsilon}}\biggl{\\{}\frac{2\mathbb{E}[|\ell_{1}(\widetilde{Y})|]}{K}\biggr{\\}}^{\frac{1+\upsilon}{\upsilon}}=O\bigl{(}K^{-\frac{1+\upsilon}{\upsilon}}\bigr{)},$

where we assume that
$\mathbb{E}[\ell_{1}^{2+2\upsilon}(\widetilde{Y})]<\infty$. By (conditional)
Jensen’s inequality, we can similarly show that

$\displaystyle
V_{2,K}^{2}\leq\sigma_{1,P}^{2}\big{\\{}\mathbb{E}[\ell_{1}^{2+2\upsilon}(\widetilde{Y})]\big{\\}}^{\frac{1}{1+\upsilon}}\biggl{\\{}\frac{2\mathbb{E}[|\ell_{1}(\widetilde{Y})|]}{K}\biggr{\\}}^{\frac{1+\upsilon}{\upsilon}}=O\bigl{(}K^{-\frac{1+\upsilon}{\upsilon}}\bigr{)}.$

Now let us look at the term
$\mathbb{E}[k_{1}^{2}(\widetilde{X},\widetilde{Y})]$. Using Hölder’s
inequality as above,

$\displaystyle\mathbb{E}[k_{1}^{2}(\widetilde{X},\widetilde{Y})]~{}=~{}$
$\displaystyle\mathbb{E}[\\{\ell_{1}(\widetilde{Y})-\psi_{1}(\widetilde{X})+\widetilde{\ell_{1}}(\widetilde{Y})-\ell_{1}(\widetilde{Y})+\psi_{1}(\widetilde{X})-\widetilde{\psi}_{1}(\widetilde{X})\\}^{2}]$
$\displaystyle=~{}$
$\displaystyle\sigma_{1,P}^{2}+\mathbb{E}[\\{\widetilde{\ell_{1}}(\widetilde{Y})-\ell_{1}(\widetilde{Y})\\}^{2}]+\mathbb{E}[\\{\psi_{1}(\widetilde{X})-\widetilde{\psi}_{1}(\widetilde{X})\\}^{2}]$
$\displaystyle+~{}$ $\displaystyle
2\mathbb{E}[\\{\widetilde{\ell_{1}}(\widetilde{Y})-\ell_{1}(\widetilde{Y})\\}\\{\psi_{1}(\widetilde{X})-\widetilde{\psi}_{1}(\widetilde{X})\\}]+2\mathbb{E}[\\{\ell_{1}(\widetilde{Y})-\psi_{1}(\widetilde{X})\\}\\{\psi_{1}(\widetilde{X})-\widetilde{\psi}_{1}(\widetilde{X})\\}]$
$\displaystyle+~{}$ $\displaystyle
2\mathbb{E}[\\{\widetilde{\ell_{1}}(\widetilde{Y})-\ell_{1}(\widetilde{Y})\\}\\{\ell_{1}(\widetilde{Y})-\psi_{1}(\widetilde{X})\\}]$
$\displaystyle=~{}$
$\displaystyle\sigma_{1,P}^{2}+O\bigl{(}K^{-\frac{1+\upsilon}{2\upsilon}}\bigr{)}.$

Similarly we let $\check{\psi}_{1}(x):=\psi_{1}(x)\mathds{1}(|\psi_{1}(x)|\leq
K/2)$, and set

$\displaystyle
k_{2}(x)=\check{\psi}_{1}(x)-\mathbb{E}[\check{\psi}_{1}(\widetilde{X})],$

which is uniformly bounded by $-K$ and $K$. Under the assumption that
$\mathbb{E}[\ell_{1}^{2+2\upsilon}(\widetilde{Y})]<\infty$, a similar
calculation along with Jensen’s inequality shows that

$\displaystyle\mathbb{E}[\\{\psi_{1}(\widetilde{X})-\mathbb{E}[\psi_{1}(\widetilde{X})]\\}k_{2}(\widetilde{X})]=\sigma_{2,P}^{2}+O\bigl{(}K^{-\frac{1+\upsilon}{\upsilon}}\bigr{)}\quad\text{and}$
$\displaystyle\mathbb{E}[k_{2}^{2}(\widetilde{X})]=\sigma_{2,P}^{2}+O\bigl{(}K^{-\frac{1+\upsilon}{2\upsilon}}\bigr{)}.$

Hence under the finite $2+\upsilon$ moment condition for $\ell_{1}$ with
$\upsilon>0$, we have the same conclusion as

$\displaystyle\liminf_{K\rightarrow\infty}\liminf_{n\rightarrow\infty}\sup_{Q\in\mathcal{F}_{P}(K/\sqrt{n})}n\mathbb{E}_{Q}\bigl{[}(\widehat{\psi}-\psi_{Q})^{2}\bigr{]}\geq\sigma_{1,P}^{2}+\frac{\sigma_{2,P}^{2}}{1+\lambda}.$

####  C.9.3 Extension: Unbounded Kernel of Arbitrary Order

Next we extend the previous result for unbounded kernels of order one to those
of arbitrary order $r\in\mathbb{N}_{+}$.

##### Building insight focusing on $r=2$.

Starting with the case of $r=2$, suppose that

$\displaystyle\psi_{\epsilon_{1},\epsilon_{2}}=\int_{\mathcal{X}}\dots\int_{\mathcal{Y}}\ell(y,y^{\prime})p_{\epsilon_{1},\epsilon_{2}}(x,y)p_{\epsilon_{1},\epsilon_{2}}(x^{\prime},y^{\prime})dxdx^{\prime}dydy^{\prime},$

where $\ell(y,y^{\prime})$ is symmetric in its argument. In order to build
upon the result in the previous section, especially (27), we only need to re-
compute

$\displaystyle\tau_{1}=\mathbb{E}_{\epsilon_{1},\epsilon_{2}}\biggl{[}\frac{\partial}{\partial\epsilon_{1}}\psi_{\epsilon_{1},\epsilon_{2}}\biggr{]}\quad\text{and}\quad\tau_{2}=\mathbb{E}_{\epsilon_{1},\epsilon_{2}}\biggl{[}\frac{\partial}{\partial\epsilon_{2}}\psi_{\epsilon_{1},\epsilon_{2}}\biggr{]}.$

The other parts remain the same. Since
$\mathbb{E}_{\epsilon_{1}}[\epsilon_{1}]=\mathbb{E}_{\epsilon_{2}}[\epsilon_{2}]=0$
and
$\mathbb{E}_{\epsilon_{1}}[\epsilon_{1}^{2}]=\mathbb{E}_{\epsilon_{2}}[\epsilon_{2}^{2}]=\frac{(\pi^{2}-6)}{3\pi^{2}}\delta^{2}$,
we have

$\displaystyle\mathbb{E}_{\epsilon_{1},\epsilon_{2}}\biggl{[}\frac{\partial}{\partial\epsilon_{1}}\psi_{\epsilon_{1},\epsilon_{2}}\biggr{]}~{}=~{}$
$\displaystyle
2\int\dots\int\ell(y,y^{\prime})p(x,y)k_{1}(x,y)\\{1+\epsilon_{2}k_{2}(x)\\}p(x^{\prime},y^{\prime})$
$\displaystyle\hskip
50.00008pt\times\\{1+\epsilon_{1}k_{1}(x^{\prime},y^{\prime})\\}\\{1+\epsilon_{2}k(x^{\prime})\\}g(\epsilon_{1})g(\epsilon_{2})dydy^{\prime}dxdx^{\prime}d\epsilon_{1}d\epsilon_{2}$
$\displaystyle=~{}$ $\displaystyle
2\int\dots\int\ell(y,y^{\prime})k_{1}(x,y)p(x,y)p(x^{\prime},y^{\prime})$
$\displaystyle\hskip
50.00008pt\times\\{1+\epsilon_{2}k(x^{\prime})+\epsilon_{2}k_{2}(x)+\epsilon_{2}^{2}k_{2}(x)k_{2}(x^{\prime})\\}g(\epsilon_{2})dydy^{\prime}dxdx^{\prime}d\epsilon_{2}$
$\displaystyle=~{}$ $\displaystyle
2\int\dots\int\ell(y,y^{\prime})k_{1}(x,y)p(x,y)p(x^{\prime},y^{\prime})dydy^{\prime}dxdx^{\prime}$
$\displaystyle+~{}$ $\displaystyle
2\int\dots\int\ell(y,y^{\prime})k_{1}(x,y)p(x,y)p(x^{\prime},y^{\prime})\epsilon_{2}^{2}k_{2}(x)k_{2}(x^{\prime})g(\epsilon_{2})dydy^{\prime}dxdx^{\prime}d\epsilon_{2}$
$\displaystyle=~{}$ $\displaystyle 2\int\int\ell_{1}(y)k_{1}(x,y)p(x,y)dxdy$
$\displaystyle+~{}$
$\displaystyle\frac{2(\pi^{2}-6)}{3\pi^{2}}\delta^{2}\int\dots\int\ell(y,y^{\prime})k_{1}(x,y)k_{2}(x)k_{2}(x^{\prime})p(x,y)p(x^{\prime},y^{\prime})dydy^{\prime}dxdx^{\prime},$

where we recall $\ell_{1}(y)=\mathbb{E}[\ell(Y,Y^{\prime})\,|\,Y=y]$. Hence
under the condition for $k_{1}$ in (24) and
$\mathbb{E}[|\ell(Y,Y^{\prime})|]<\infty$, we observe

$\displaystyle\mathbb{E}_{\epsilon_{1},\epsilon_{2}}\biggl{[}\frac{\partial}{\partial\epsilon_{1}}\psi_{\epsilon_{1},\epsilon_{2}}\biggr{]}=2\mathbb{E}[\\{\ell_{1}(Y)-\psi_{1}(X)\\}k_{1}(X,Y)]+O(\delta^{2}K^{3}).$

Next we similarly observe that

$\displaystyle\mathbb{E}_{\epsilon_{1},\epsilon_{2}}\biggl{[}\frac{\partial}{\partial\epsilon_{2}}\psi_{\epsilon_{1},\epsilon_{2}}\biggr{]}~{}=~{}$
$\displaystyle
2\int\dots\int\ell(y,y^{\prime})p(x,y)\\{1+\epsilon_{1}k_{1}(x,y)\\}k_{2}(x)p(x^{\prime},y^{\prime})$
$\displaystyle\hskip
50.00008pt\times\\{1+\epsilon_{1}k_{1}(x^{\prime},y^{\prime})\\}\\{1+\epsilon_{2}k(x^{\prime})\\}g(\epsilon_{1})g(\epsilon_{2})dydy^{\prime}dxdx^{\prime}d\epsilon_{1}d\epsilon_{2}$
$\displaystyle=~{}$ $\displaystyle
2\int\dots\int\ell(y,y^{\prime})p(x,y)\\{1+\epsilon_{1}k_{1}(x,y)\\}k_{2}(x)p(x^{\prime},y^{\prime})$
$\displaystyle\hskip
50.00008pt\times\\{1+\epsilon_{1}k_{1}(x^{\prime},y^{\prime})\\}g(\epsilon_{1})dydy^{\prime}dxdx^{\prime}d\epsilon_{1}$
$\displaystyle=~{}$ $\displaystyle 2\int\int\ell_{1}(y)k_{2}(x)p(x,y)dxdy$
$\displaystyle+~{}$ $\displaystyle
2\int\dots\int\ell(y,y^{\prime})p(x,y)k_{2}(x)p(x^{\prime},y^{\prime})\epsilon_{1}^{2}k_{1}(x,y)k_{1}(x^{\prime},y^{\prime})g(\epsilon_{1})dydy^{\prime}dxdx^{\prime}d\epsilon_{1}$
$\displaystyle=~{}$ $\displaystyle 2\int\int\ell_{1}(y)k_{2}(x)p(x,y)dxdy$
$\displaystyle+~{}$
$\displaystyle\frac{2(\pi^{2}-6)}{3\pi^{2}}\delta^{2}\int\dots\int\ell(y,y^{\prime})p(x,y)k_{2}(x)p(x^{\prime},y^{\prime})k_{1}(x,y)k_{1}(x^{\prime},y^{\prime})dydy^{\prime}dxdx^{\prime}.$

Therefore, using the condition for $k_{2}$ in (24), we have

$\displaystyle\mathbb{E}_{\epsilon_{1},\epsilon_{2}}\biggl{[}\frac{\partial}{\partial\epsilon_{2}}\psi_{\epsilon_{1},\epsilon_{2}}\biggr{]}~{}=~{}2\mathbb{E}[\\{\psi_{1}(Y)-\mathbb{E}[\psi_{1}(Y)]\\}k_{2}(X)]+O(\delta^{2}K^{3}).$

By taking $\delta=K/\sqrt{n}$, we will get the same asymptotic lower bound
with an additional constant factor $4$, i.e.,

$\displaystyle\liminf_{K\rightarrow\infty}\liminf_{n\rightarrow\infty}\sup_{Q\in\mathcal{F}_{P}(K/\sqrt{n})}n\mathbb{E}_{Q}\bigl{[}(\widehat{\psi}-\psi_{Q})^{2}\bigr{]}\geq
4\sigma_{1,P}^{2}+\frac{4\sigma_{2,P}^{2}}{1+\lambda}.$

##### Arbitrary $r\in\mathbb{N}_{+}$.

Now suppose that $\ell(y_{1},\ldots,y_{r})$ is symmetric in its arguments with
a fixed $r\in\mathbb{N}_{+}$ and we are interested in estimating

$\displaystyle\psi=\mathbb{E}[\ell(Y_{1},\ldots,Y_{r})].$

By symmetry of $\ell$ in its arguments, we can write

$\displaystyle\frac{\partial}{\partial\epsilon_{1}}\psi_{\epsilon_{1},\epsilon_{2}}=r\int\dots\int\ell(y_{1},\ldots,y_{r})\bigg{\\{}\frac{\partial}{\partial\epsilon_{1}}p_{\epsilon_{1},\epsilon_{2}}(x_{1},y_{1})\bigg{\\}}p_{\epsilon_{1},\epsilon_{2}}(x_{2},y_{2})\cdots
p_{\epsilon_{1},\epsilon_{2}}(x_{r},y_{r})dx_{1}dy_{1}\cdots dx_{r}dy_{r},$
$\displaystyle\frac{\partial}{\partial\epsilon_{2}}\psi_{\epsilon_{1},\epsilon_{2}}=r\int\dots\int\ell(y_{1},\ldots,y_{r})\bigg{\\{}\frac{\partial}{\partial\epsilon_{2}}p_{\epsilon_{1},\epsilon_{2}}(x_{1},y_{1})\bigg{\\}}p_{\epsilon_{1},\epsilon_{2}}(x_{2},y_{2})\cdots
p_{\epsilon_{1},\epsilon_{2}}(x_{r},y_{r})dx_{1}dy_{1}\cdots dx_{r}dy_{r}.$

Further write $\ell_{1}(y)=\mathbb{E}[\ell(y,Y_{2},\ldots,Y_{r})]$ and
$\psi_{1}(x)=\mathbb{E}[\ell_{1}(Y)\,|\,X=x]$. We may follow the analysis for
the case of $r=2$ and it holds that

$\displaystyle\mathbb{E}_{\epsilon_{1},\epsilon_{2}}\biggl{[}\frac{\partial}{\partial\epsilon_{1}}\psi_{\epsilon_{1},\epsilon_{2}}\biggr{]}~{}=~{}r\mathbb{E}[\\{\ell_{1}(Y)-\psi_{1}(X)\\}k_{1}(X,Y)]+O(\delta^{2}K^{2r-1})\quad\text{and}$
$\displaystyle\mathbb{E}_{\epsilon_{1},\epsilon_{2}}\biggl{[}\frac{\partial}{\partial\epsilon_{2}}\psi_{\epsilon_{1},\epsilon_{2}}\biggr{]}~{}=~{}r\mathbb{E}[\\{\psi_{1}(X)-\mathbb{E}[\psi_{1}(X)]\\}k_{2}(X)]+O(\delta^{2}K^{2r-1}),$

assuming that $\delta$ is sufficiently small and $r$ is fixed. Now, by taking
$\delta=K/\sqrt{n}$, we will get the same asymptotic lower bound with an
additional constant factor $r^{2}$, i.e.,

$\displaystyle\liminf_{K\rightarrow\infty}\liminf_{n\rightarrow\infty}\sup_{Q\in\mathcal{F}_{P}(K/\sqrt{n})}n\mathbb{E}_{Q}\bigl{[}(\widehat{\psi}-\psi_{Q})^{2}\bigr{]}\geq
r^{2}\sigma_{1,P}^{2}+\frac{r^{2}\sigma_{2,P}^{2}}{1+\lambda}.$

###  C.10 Proof of Proposition 4

Throughout the proof, we often omit the dependence on $P$ in $\mathbb{E}_{P}$,
$\mathrm{Var}_{P}$, $\mathrm{Cov}_{P}$, $G_{P,m,n}$ and $H_{P,m,n}$ to
simplify the notation. To start, we observe that the variance of
$U^{\star}_{\mathrm{adapt}}$ without the scaling factor $(n+m)/(n+m-1)$ is
equal to that of

$\displaystyle\sum_{1\leq i\neq j\leq
n+m}\Biggl{[}\,\sum_{k=1}^{\infty}\lambda_{k}\biggl{\\{}\frac{\delta_{i}}{n}\phi_{k}(Y_{i})-\frac{\delta_{i}}{n}\mathbb{E}[\phi_{k}(Y_{i})\,|\,X_{i}]+\frac{1}{n+m}\mathbb{E}[\phi_{k}(Y_{i})\,|\,X_{i}]\biggr{\\}}$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\times\biggl{\\{}\frac{\delta_{j}}{n}\phi_{k}(Y_{j})-\frac{\delta_{j}}{n}\mathbb{E}[\phi_{k}(Y_{j})\,|\,X_{j}]+\frac{1}{n+m}\mathbb{E}[\phi_{k}(Y_{j})\,|\,X_{j}]\biggr{\\}}\Biggr{]}.$

Denoting the summands as

$\displaystyle a_{ij}:=$
$\displaystyle\sum_{k=1}^{\infty}\lambda_{k}\biggl{\\{}\frac{\delta_{i}}{n}\phi_{k}(Y_{i})-\frac{\delta_{i}}{n}\mathbb{E}[\phi_{k}(Y_{i})\,|\,X_{i}]+\frac{1}{n+m}\mathbb{E}[\phi_{k}(Y_{i})\,|\,X_{i}]\biggr{\\}}$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\times\biggl{\\{}\frac{\delta_{j}}{n}\phi_{k}(Y_{j})-\frac{\delta_{j}}{n}\mathbb{E}[\phi_{k}(Y_{j})\,|\,X_{j}]+\frac{1}{n+m}\mathbb{E}[\phi_{k}(Y_{j})\,|\,X_{j}]\biggr{\\}},$

for $1\leq i\neq j\leq n+m$, notice that

$\displaystyle\mathrm{Var}\Biggl{[}\sum_{1\leq i\neq j\leq
n+m}a_{ij}\Biggr{]}~{}=~{}$ $\displaystyle\sum_{1\leq i\neq j\leq
n+m}\sum_{1\leq s\neq t\leq n+m}\mathrm{Cov}(a_{ij},a_{st})$
$\displaystyle=~{}$ $\displaystyle 4\sum_{\begin{subarray}{c}1\leq i,j,s\leq
n+m\\\
\mathrm{distinct}\end{subarray}}\mathrm{Cov}(a_{ij},a_{is})+2\sum_{1\leq i\neq
j\leq n+m}\mathrm{Cov}(a_{ij},a_{ij})$ $\displaystyle:=~{}$ $\displaystyle
4S_{1}+2S_{2},$

where the second identity holds since $\mathrm{Cov}(a_{ij},a_{st})=0$ when
$\\{i,j\\}\cap\\{s,t\\}=\emptyset$. We now analyze the two summations
separately.

Analysis of $S_{1}$. By the law of total covariance,

$\displaystyle\mathrm{Cov}(a_{ij},a_{is})~{}=~{}$
$\displaystyle\mathbb{E}\bigl{[}\underbrace{\mathrm{Cov}(a_{ij},a_{is}\,|\,X_{i},Y_{i})}_{=0}\bigr{]}+\mathrm{Cov}\bigl{(}\mathbb{E}[a_{ij}\,|\,X_{i},Y_{i}],\mathbb{E}[a_{is}\,|\,X_{i},Y_{i}]\bigr{)}$
$\displaystyle=~{}$
$\displaystyle\mathrm{Cov}\bigl{(}\mathbb{E}[a_{ij}\,|\,X_{i},Y_{i}],\mathbb{E}[a_{is}\,|\,X_{i},Y_{i}]\bigr{)}$
$\displaystyle=~{}$
$\displaystyle\begin{cases}\frac{1}{n^{2}(n+m)^{2}}\mathrm{Var}\bigl{[}\mathbb{E}\bigl{\\{}\ell(Y_{1},Y_{2})\,|\,Y_{1}\bigr{\\}}-\frac{m}{n+m}\mathbb{E}\bigl{\\{}\ell(Y_{1},Y_{2})\,|\,X_{1}\bigr{\\}}\bigr{]}&\quad\text{if
$\delta_{i}=1$,}\\\\[5.0pt]
\frac{1}{(n+m)^{4}}\mathrm{Var}\bigl{[}\mathbb{E}\bigl{\\{}\ell_{2}(Y_{1},Y_{2})\,|\,X_{1}\bigr{\\}}\bigr{]}&\quad\text{if
$\delta_{i}=0$.}\end{cases}$

Therefore, $S_{1}$ can be computed as

$\displaystyle S_{1}~{}=~{}$
$\displaystyle\sum_{i=1}^{n}\sum_{\begin{subarray}{c}1\leq j,s\leq n+m\\\
i,j,s\,\mathrm{distinct}\end{subarray}}\mathrm{Cov}(a_{ij},a_{is})+\sum_{i=n+1}^{n+m}\sum_{\begin{subarray}{c}1\leq
j,s\leq n+m\\\
i,j,s\,\mathrm{distinct}\end{subarray}}\mathrm{Cov}(a_{ij},a_{is})$
$\displaystyle=~{}$
$\displaystyle\frac{n(n+m-1)(n+m-2)}{n^{2}(n+m)^{2}}\mathrm{Var}\biggl{[}\mathbb{E}\bigl{\\{}\ell(Y_{1},Y_{2})\,|\,Y_{1}\bigr{\\}}-\frac{m}{n+m}\mathbb{E}\bigl{\\{}\ell(Y_{1},Y_{2})\,|\,X_{1}\bigr{\\}}\biggr{]}$
$\displaystyle+~{}$
$\displaystyle\frac{m(n+m-1)(n+m-2)}{(n+m)^{4}}\mathrm{Var}\bigl{[}\mathbb{E}\bigl{\\{}\ell(Y_{1},Y_{2})\,|\,X_{1}\bigr{\\}}\bigr{]}.$

This can be further simplified as

$\displaystyle S_{1}~{}=~{}$
$\displaystyle\frac{(n+m-1)(n+m-2)}{n(n+m)^{2}}\mathrm{Var}\bigl{[}\mathbb{E}\bigl{\\{}\ell(Y_{1},Y_{2})\,|\,Y_{1}\bigr{\\}}\bigr{]}$
$\displaystyle-~{}$
$\displaystyle\frac{m(n+m-1)(n+m-2)}{n(n+m)^{3}}\mathrm{Var}\bigl{[}\mathbb{E}\bigl{\\{}\ell(Y_{1},Y_{2})\,|\,X_{1}\bigr{\\}}\bigr{]}$
$\displaystyle=~{}$
$\displaystyle\frac{(n+m-1)(n+m-2)}{n(n+m)^{2}}\biggl{\\{}\mathrm{Var}\bigl{[}\mathbb{E}\bigl{\\{}\ell(Y_{1},Y_{2})\,|\,Y_{1}\bigr{\\}}\bigr{]}-\frac{m}{n+m}\mathrm{Var}\bigl{[}\mathbb{E}\bigl{\\{}\ell(Y_{1},Y_{2})\,|\,X_{1}\bigr{\\}}\bigr{]}\biggr{\\}}$
$\displaystyle=~{}$
$\displaystyle\frac{1}{n}\biggl{\\{}\mathrm{Var}\bigl{[}\mathbb{E}\bigl{\\{}\ell(Y_{1},Y_{2})\,|\,Y_{1}\bigr{\\}}\bigr{]}-\frac{m}{n+m}\mathrm{Var}\bigl{[}\mathbb{E}\bigl{\\{}\ell(Y_{1},Y_{2})\,|\,X_{1}\bigr{\\}}\bigr{]}\biggr{\\}}\\{1+o_{\mathcal{P}}(1)\\}.$

Here and hereafter, we use the notation $o_{\mathcal{P}}(1)$ to represent a
sequence of numbers that converges to zero as $n\rightarrow\infty$ uniformly
over $\mathcal{P}$.

Analysis of $S_{2}$. Next for $S_{2}$, note that

$\displaystyle S_{2}~{}=~{}$ $\displaystyle\sum_{i=1}^{n}\sum_{1\leq j\neq
i\leq n+m}\mathrm{Var}(a_{ij})+\sum_{i=n+1}^{n+m}\sum_{1\leq j\neq i\leq
n+m}\mathrm{Var}(a_{ij})$ $\displaystyle=~{}$ $\displaystyle
n(n-1)\mathrm{Var}(a_{ij}\,|\,\delta_{i}=1,\delta_{j}=1)+nm\mathrm{Var}(a_{ij}\,|\,\delta_{i}=1,\delta_{j}=0)$
$\displaystyle+~{}$ $\displaystyle
mn\mathrm{Var}(a_{ij}\,|\,\delta_{i}=0,\delta_{j}=1)+m(m-1)\mathrm{Var}(a_{ij}\,|\,\delta_{i}=0,\delta_{j}=0),$

where $\mathrm{Var}(a_{ij}\,|\,\delta_{i}=1,\delta_{j}=1)$ denotes the
variance of $a_{ij}$ when $\delta_{i}=1,\delta_{j}=1$ and the other terms are
similarly defined. These variances are computed as

$\displaystyle\mathrm{Var}(a_{ij}$
$\displaystyle\,|\,\delta_{i}=1,\delta_{j}=1)$ $\displaystyle=~{}$
$\displaystyle\frac{1}{n^{4}}\mathrm{Var}\bigg{\\{}\sum_{k=1}^{\infty}\lambda_{k}\biggl{(}\phi_{k}(Y_{1})-\frac{m}{n+m}\mathbb{E}[\phi_{k}(Y_{1})\,|\,X_{1}]\biggr{)}\biggl{(}\phi_{k}(Y_{2})-\frac{m}{n+m}\mathbb{E}[\phi_{k}(Y_{2})\,|\,X_{2}]\biggr{)}\bigg{\\}},$
$\displaystyle\mathrm{Var}(a_{ij}$
$\displaystyle\,|\,\delta_{i}=0,\delta_{j}=1)=\mathrm{Var}(a_{ij}\,|\,\delta_{i}=1,\delta_{j}=0)$
$\displaystyle=~{}$
$\displaystyle\frac{1}{n^{2}(n+m)^{2}}\mathrm{Var}\bigg{\\{}\sum_{k=1}^{\infty}\lambda_{k}\biggl{(}\phi_{k}(Y_{1})-\frac{m}{n+m}\mathbb{E}[\phi_{k}(Y_{1})\,|\,X_{1}]\biggr{)}\mathbb{E}[\phi_{k}(Y_{2})\,|\,X_{2}]\bigg{\\}}\quad\text{and}$
$\displaystyle\mathrm{Var}(a_{ij}$
$\displaystyle\,|\,\delta_{i}=0,\delta_{j}=0)=\frac{1}{(n+m)^{4}}\mathrm{Var}\bigg{\\{}\sum_{k=1}^{\infty}\lambda_{k}\mathbb{E}[\phi_{k}(Y_{1})\,|\,X_{1}]\mathbb{E}[\phi_{k}(Y_{2})\,|\,X_{2}]\bigg{\\}}.$

Therefore $S_{2}$ can be written as

$\displaystyle S_{2}~{}=~{}$
$\displaystyle\frac{n(n-1)}{n^{4}}\mathrm{Var}\bigg{\\{}\sum_{k=1}^{\infty}\lambda_{k}\biggl{(}\phi_{k}(Y_{1})-\frac{m}{n+m}\mathbb{E}[\phi_{k}(Y_{1})\,|\,X_{1}]\biggr{)}\biggl{(}\phi_{k}(Y_{2})-\frac{m}{n+m}\mathbb{E}[\phi_{k}(Y_{2})\,|\,X_{2}]\biggr{)}\bigg{\\}}$
$\displaystyle+~{}$
$\displaystyle\frac{2mn}{n^{2}(n+m)^{2}}\mathrm{Var}\biggl{\\{}\sum_{k=1}^{\infty}\lambda_{k}\biggl{(}\phi_{k}(Y_{1})-\frac{m}{n+m}\mathbb{E}[\phi_{k}(Y_{1})\,|\,X_{1}]\biggr{)}\mathbb{E}[\phi_{k}(Y_{2})\,|\,X_{2}]\biggr{\\}}$
$\displaystyle+~{}$
$\displaystyle\frac{m(m-1)}{(n+m)^{4}}\mathrm{Var}\biggl{\\{}\sum_{k=1}^{\infty}\lambda_{k}\mathbb{E}[\phi_{k}(Y_{1})\,|\,X_{1}]\mathbb{E}[\phi_{k}(Y_{2})\,|\,X_{2}]\biggr{\\}}.$

Moreover, we have

$\displaystyle S_{2}~{}=~{}$
$\displaystyle\frac{m(m-1)}{(n+m)^{4}}\mathrm{Var}[\ell_{2}(X_{1},X_{2})]+\frac{2mn}{n^{2}(n+m)^{2}}\mathrm{Var}\bigg{\\{}\ell_{1}(Y_{1},X_{2})-\frac{m}{n+m}\ell_{2}(X_{1},X_{2})\bigg{\\}}$
$\displaystyle+~{}$
$\displaystyle\frac{n(n-1)}{n^{4}}\mathrm{Var}\bigg{\\{}\ell(Y_{1},Y_{2})-\frac{m}{n+m}\ell_{1}(Y_{1},X_{2})-\frac{m}{n+m}\ell_{1}(X_{1},Y_{2})+\frac{m^{2}}{(n+m)^{2}}\ell_{2}(X_{1},X_{2})\bigg{\\}}.$

Furthermore,

$\displaystyle\mathrm{Var}\bigg{\\{}\ell_{1}(Y_{1},X_{2})-\frac{m}{n+m}\ell_{2}(X_{1},X_{2})\bigg{\\}}~{}=~{}$
$\displaystyle\mathrm{Var}[\ell_{1}(Y_{1},X_{2})]+\frac{m^{2}}{(n+m)^{2}}\mathrm{Var}[\ell_{2}(X_{1},X_{2})]$
$\displaystyle-~{}$
$\displaystyle\frac{2m}{n+m}\underbrace{\mathrm{Cov}\big{\\{}\ell_{1}(Y_{1},X_{2}),\ell_{2}(X_{1},X_{2})\big{\\}}}_{=\mathrm{Var}[\ell_{2}(X_{1},X_{2})]}$
$\displaystyle=~{}$
$\displaystyle\mathrm{Var}[\ell_{1}(Y_{1},X_{2})]-\frac{m(m+2n)}{(n+m)^{2}}\mathrm{Var}[\ell_{2}(X_{1},X_{2})]$

and an analogous calculation shows that

$\displaystyle\mathrm{Var}\bigg{\\{}\ell(Y_{1},Y_{2})-\frac{m}{n+m}\ell_{1}(Y_{1},X_{2})-\frac{m}{n+m}\ell_{1}(X_{1},Y_{2})+\frac{m^{2}}{(n+m)^{2}}\ell_{2}(X_{1},X_{2})\bigg{\\}}$
$\displaystyle=~{}$
$\displaystyle\mathrm{Var}[\ell(Y_{1},Y_{2})]+\frac{2m^{2}}{(n+m)^{2}}\mathrm{Var}[\ell_{1}(Y_{1},X_{2})]+\frac{m^{4}}{(n+m)^{4}}\mathrm{Var}[\ell_{2}(X_{1},X_{2})]$
$\displaystyle~{}-\frac{4m}{n+m}\mathrm{Var}[\ell_{1}(Y_{1},X_{2})]+\frac{4m^{2}}{(n+m)^{2}}\mathrm{Var}[\ell_{2}(X_{1},X_{2})]-\frac{4m^{3}}{(n+m)^{3}}\mathrm{Var}[\ell_{2}(X_{1},X_{2})]$
$\displaystyle=~{}$
$\displaystyle\mathrm{Var}[\ell(Y_{1},Y_{2})]+\biggl{[}\frac{2m^{2}}{(n+m)^{2}}-\frac{4m}{n+m}\biggr{]}\mathrm{Var}[\ell_{1}(Y_{1},X_{2})]$
$\displaystyle~{}+\biggl{[}\frac{m^{4}}{(n+m)^{4}}+\frac{4m^{2}}{(n+m)^{2}}-\frac{4m^{3}}{(n+m)^{3}}\biggr{]}\mathrm{Var}[\ell_{2}(X_{1},X_{2})]$
$\displaystyle=~{}$
$\displaystyle\mathrm{Var}[\ell(Y_{1},Y_{2})]-\frac{2m(m+2n)}{(n+m)^{2}}\mathrm{Var}[\ell_{1}(Y_{1},X_{2})]+\frac{m^{2}(m+2n)^{2}}{(m+n)^{4}}\mathrm{Var}[\ell_{2}(X_{1},X_{2})].$

Hence, $S_{2}$ can be written as

$\displaystyle S_{2}~{}=~{}$
$\displaystyle\frac{n-1}{n^{3}}\mathrm{Var}[\ell(Y_{1},Y_{2})]-\frac{2m\\{m(n-1)+n(n-2)\\}}{n^{3}(m+n)^{2}}\mathrm{Var}[\ell_{1}(Y_{1},X_{2})]$
$\displaystyle+~{}$
$\displaystyle\frac{m\\{m^{2}(n-1)+mn(n-3)-n^{2}\\}}{n^{3}(m+n)^{3}}\mathrm{Var}[\ell_{2}(X_{1},X_{2})]$
$\displaystyle=~{}$
$\displaystyle\frac{1}{n^{2}}\mathrm{Var}[\ell(Y_{1},Y_{2})]\\{1+o_{\mathcal{P}}(1)\\}-\frac{2m}{n^{2}(n+m)}\mathrm{Var}[\ell_{1}(Y_{1},X_{2})]\\{1+o_{\mathcal{P}}(1)\\}$
$\displaystyle+~{}$
$\displaystyle\frac{1}{n^{2}}\frac{m^{2}}{(n+m)^{2}}\mathrm{Var}[\ell_{2}(X_{1},X_{2})]\\{1+o_{\mathcal{P}}(1)\\}-\frac{m}{n(n+m)^{3}}\mathrm{Var}[\ell_{2}(X_{1},X_{2})]$
$\displaystyle=~{}$
$\displaystyle\frac{1}{n^{2}}\bigg{[}\mathrm{Var}[\ell(Y_{1},Y_{2})]-\frac{2m}{(n+m)}\mathrm{Var}[\ell_{1}(Y_{1},X_{2})]+\frac{m^{2}}{(n+m)^{2}}\mathrm{Var}[\ell_{2}(X_{1},X_{2})]\bigg{]}\\{1+o_{\mathcal{P}}(1)\\}$
$\displaystyle-~{}$
$\displaystyle\frac{m}{n(n+m)^{3}}\mathrm{Var}[\ell_{2}(X_{1},X_{2})].$

Observe that
$\mathrm{Var}[\ell_{2}(X_{1},X_{2})]\leq\mathrm{Var}[\ell_{1}(Y_{1},X_{2})]\leq\mathrm{Var}[\ell(Y_{1},Y_{2})]$,
which can be verified by Jensen’s inequality. Given this, when
$\mathrm{Var}[\ell(Y_{1},Y_{2})]\leq C_{1}$ and
$\mathrm{Var}[\ell(Y_{1},Y_{2})]-2\mathrm{Var}[\ell_{1}(Y_{1},X_{2})]+\mathrm{Var}[\ell_{2}(X_{1},X_{2})]\geq
C_{2}$, we observe that

$\displaystyle G_{m,n}~{}=~{}$
$\displaystyle\mathrm{Var}[\ell(Y_{1},Y_{2})]-\frac{2m}{(n+m)}\mathrm{Var}[\ell_{1}(Y_{1},X_{2})]+\frac{m^{2}}{(n+m)^{2}}\mathrm{Var}[\ell_{2}(X_{1},X_{2})]$
$\displaystyle=~{}$
$\displaystyle\mathrm{Var}\bigg{\\{}\sum_{k=1}^{\infty}\lambda_{k}\biggl{(}\phi_{k}(Y_{1})-\frac{m}{n+m}\mathbb{E}[\phi_{k}(Y_{1})\,|\,X_{1}]\biggr{)}\biggl{(}\phi_{k}(Y_{2})-\frac{m}{n+m}\mathbb{E}[\phi_{k}(Y_{2})\,|\,X_{2}]\biggr{)}\bigg{\\}}$
$\displaystyle\geq~{}$
$\displaystyle\mathrm{Var}[\ell(Y_{1},Y_{2})]-2\mathrm{Var}[\ell_{1}(Y_{1},X_{2})]+\mathrm{Var}[\ell_{2}(X_{1},X_{2})]\,\geq\,C_{2}.$

Therefore for any $P\in\mathcal{P}$,

$\displaystyle S_{2}~{}=~{}$
$\displaystyle\frac{1}{n^{2}}G_{m,n}\\{1+o_{\mathcal{P}}(1)\\}-\frac{m}{n(n+m)^{3}}\mathrm{Var}[\ell_{2}(X_{1},X_{2})]$
$\displaystyle=~{}$
$\displaystyle\frac{1}{n^{2}}G_{m,n}\\{1+o_{\mathcal{P}}(1)\\}.$

In other words, $S_{2}$ approximates
$n^{-2}G_{m,n}\\{1+o_{\mathcal{P}}(1)\\}$, regardless of the value of
$m\in\mathbb{N}_{\geq 0}$.

Summary. Recalling

$\displaystyle
H_{m,n}=\mathrm{Var}\bigl{[}\mathbb{E}\bigl{\\{}\ell(Y_{1},Y_{2})\,|\,Y_{1}\bigr{\\}}\bigr{]}-\frac{m}{n+m}\mathrm{Var}\bigl{[}\mathbb{E}\bigl{\\{}\ell(Y_{1},Y_{2})\,|\,X_{1}\bigr{\\}}\bigr{]},$

we have shown that

$\displaystyle\mathrm{Var}[U_{\mathrm{adapt}}^{\star}]~{}=~{}$
$\displaystyle\biggl{(}\frac{n+m-1}{n+m}\biggr{)}^{2}\\{4S_{1}+2S_{2}\\}$
$\displaystyle=~{}$
$\displaystyle\biggl{(}\frac{4}{n}H_{m,n}+\frac{2}{n^{2}}G_{m,n}\biggr{)}\\{1+o_{\mathcal{P}}(1)\\}.$

with no restriction on $m$. Therefore, it holds that

$\displaystyle\lim_{n\rightarrow\infty}\sup_{P\in\mathcal{P}}\biggl{|}\frac{\mathrm{Var}_{P}[U^{\star}]}{4n^{-1}H_{P,m,n}+2n^{-2}G_{P,m,n}}-1\biggr{|}=0.$

###  C.11 Proof of Theorem 6

As in Section C.10, we often omit the dependence on $P$ whenever it is clear
from the context. We again use the notation $a_{n}=o_{\mathcal{P}}(b_{n})$ to
denote that $a_{n}/b_{n}$ converges to zero as $n\rightarrow\infty$ uniformly
over $\mathcal{P}$.

For simplicity, write

$\displaystyle\Gamma_{k}:=\frac{1}{n}\sum_{i=1}^{n}\big{\\{}\phi_{k}(Y_{i})-\mathbb{E}[\phi_{k}(Y_{i})\,|\,X_{i}]\big{\\}}+\frac{1}{n+m}\sum_{j=1}^{n+m}\mathbb{E}[\phi_{k}(Y_{j})\,|\,X_{j}],$
$\displaystyle\widehat{\Gamma}_{k}:=\frac{1}{n}\sum_{i=1}^{n}\big{\\{}\phi_{k}(Y_{i})-\widehat{\mathbb{E}}[\phi_{k}(Y_{i})\,|\,X_{i}]\big{\\}}+\frac{1}{n+m}\sum_{j=1}^{n+m}\widehat{\mathbb{E}}[\phi_{k}(Y_{j})\,|\,X_{j}],$
$\displaystyle\Pi_{i,k}:=\frac{\delta_{i}}{n}\phi_{k}(Y_{i})-\frac{\delta_{i}}{n}\mathbb{E}[\phi_{k}(Y_{i})\,|\,X_{i}]+\frac{1}{n+m}\mathbb{E}[\phi_{k}(Y_{i})\,|\,X_{i}]\quad\text{and}$
$\displaystyle\widehat{\Pi}_{i,k}:=\frac{\delta_{i}}{n}\phi_{k}(Y_{i})-\frac{\delta_{i}}{n}\widehat{\mathbb{E}}[\phi_{k}(Y_{i})\,|\,X_{i}]+\frac{1}{n+m}\widehat{\mathbb{E}}[\phi_{k}(Y_{i})\,|\,X_{i}].$

Then the difference between $U_{\mathrm{adapt}}$ and
$U_{\mathrm{adapt}}^{\star}$ can be written as

$\displaystyle U_{\mathrm{adapt}}-U_{\mathrm{adapt}}^{\star}~{}=~{}$
$\displaystyle\frac{n+m}{n+m-1}\Biggl{[}\
\sum_{k=1}^{\infty}\lambda_{k}\bigl{(}\Gamma_{k}-\widehat{\Gamma}_{k}\bigr{)}^{2}+2\sum_{k=1}^{\infty}\lambda_{k}\Gamma_{k}\bigl{(}\widehat{\Gamma}_{k}-\Gamma_{k}\bigr{)}$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}-\sum_{k=1}^{\infty}\lambda_{k}\biggl{\\{}\sum_{i=1}^{n+m}\bigl{(}\widehat{\Pi}_{i,k}-\Pi_{i,k}\bigr{)}^{2}\biggr{\\}}-2\sum_{k=1}^{\infty}\lambda_{k}\biggl{\\{}\sum_{i=1}^{n+m}\bigl{(}\widehat{\Pi}_{i,k}-\Pi_{i,k}\bigr{)}\Pi_{i,k}\biggr{\\}}\Biggr{]}$
$\displaystyle=~{}$
$\displaystyle\frac{n+m}{n+m-1}\bigl{[}(\mathrm{I})+2(\mathrm{II})-(\mathrm{III})-2(\mathrm{IV})\bigr{]}.$

We shall show that each of $\mathbb{E}[|(\mathrm{I})|]$,
$\mathbb{E}[|(\mathrm{II})|]$, $\mathbb{E}[|(\mathrm{III})|]$ and
$\mathbb{E}[|(\mathrm{IV})|]$ is
$o_{\mathcal{P}}(\\{\mathrm{Var}[U_{\mathrm{adapt}}^{\star}]\\}^{1/2})$. Then
the desired claim follows since $(n+m)/(n+m-1)=1+o_{\mathcal{P}}(1)$.

For the first term (I), we follow a similar approach in the proof of Theorem 1
and show

$\displaystyle\mathbb{E}[|(\mathrm{I})|]~{}=~{}$
$\displaystyle\sum_{k=1}^{\infty}\lambda_{k}\mathbb{E}\bigl{[}\bigl{(}\Gamma_{k}-\widehat{\Gamma}_{k}\bigr{)}^{2}\bigr{]}=\sum_{k=1}^{\infty}\lambda_{k}\mathbb{E}\Biggl{[}\Biggl{(}\frac{1}{n}\sum_{i=1}^{n}\bigl{\\{}\widehat{\mathbb{E}}[\phi_{k}(Y_{i})\,|\,X_{i}]-\mathbb{E}[\phi_{k}(Y_{i})\,|\,X_{i}]\bigr{\\}}$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}-\frac{1}{n+m}\sum_{i=1}^{n+m}\bigl{\\{}\widehat{\mathbb{E}}[\phi_{k}(Y_{i})\,|\,X_{i}]-\mathbb{E}[\phi_{k}(Y_{i})\,|\,X_{i}]\big{\\}}\Biggr{)}^{2}\Biggr{]}$
$\displaystyle\leq~{}$ $\displaystyle
C\times\frac{1}{n}\sum_{k=1}^{\infty}\lambda_{k}\mathbb{E}\bigl{[}\big{\\{}\mathbb{E}[\phi_{k}(Y)\,|\,X]-\widehat{\mathbb{E}}[\phi_{k}(Y)\,|\,X]\big{\\}}^{2}\bigr{]},$

where $C$ denotes some positive constant. The last quantity multiplied by $n$
can be written as

$\displaystyle\sum_{k=1}^{\infty}\lambda_{k}\mathbb{E}\bigl{[}\bigl{\\{}\mathbb{E}[\phi_{k}(Y)\,|\,X]-\widehat{\mathbb{E}}[\phi_{k}(Y)\,|\,X]\bigr{\\}}^{2}\bigr{]}=\mathbb{E}\biggl{[}\int_{\mathcal{Y}}\int_{\mathcal{Y}}\int_{\mathcal{X}}\ell(y_{1},y_{2})\bigl{\\{}p_{Y\mkern
1.0mu|\mkern 1.0muX}(y_{1}\,|\,x)-\widehat{p}_{Y\mkern 1.0mu|\mkern
1.0muX}(y_{1}\,|\,x)\bigr{\\}}$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\times\bigl{\\{}p_{Y\mkern
1.0mu|\mkern 1.0muX}(y_{2}\,|\,x)-\widehat{p}_{Y\mkern 1.0mu|\mkern
1.0muX}(y_{2}\,|\,x)\bigr{\\}}p_{X}(x)d\nu(y_{1})d\nu(y_{2})d\nu(x)\biggr{]}$
$\displaystyle\leq~{}$
$\displaystyle\mathbb{E}\Biggl{[}\int_{\mathcal{X}}\int_{\mathcal{Y}}\biggl{\\{}\int\ell^{2}(y_{1},y_{2})p_{Y\mkern
1.0mu|\mkern
1.0muX}(y_{1}\,|\,x)d\nu(y_{1})\biggr{\\}}^{1/2}\biggl{\\{}\int_{\mathcal{Y}}\frac{\bigl{\\{}p_{Y\mkern
1.0mu|\mkern 1.0muX}(y_{1}\,|\,x)-\widehat{p}_{Y\mkern 1.0mu|\mkern
1.0muX}(y_{1}\,|\,x)\bigr{\\}}^{2}}{p_{Y\mkern 1.0mu|\mkern
1.0muX}(y_{1}\,|\,x)}d\nu(y_{1})\biggr{\\}}^{1/2}$
$\displaystyle~{}~{}~{}~{}~{}~{}\times\big{|}p_{Y\mkern 1.0mu|\mkern
1.0muX}(y_{2}\,|\,x)-\widehat{p}_{Y\mkern 1.0mu|\mkern
1.0muX}(y_{2}\,|\,x)\big{|}p_{X}(x)d\nu(y_{1})d\nu(y_{2})d\nu(x)\Biggr{]}$
$\displaystyle\leq~{}$
$\displaystyle\mathbb{E}\Biggl{[}\int_{\mathcal{X}}\biggl{\\{}\int_{\mathcal{Y}}\int_{\mathcal{Y}}\ell^{2}(y_{1},y_{2})p_{Y\mkern
1.0mu|\mkern 1.0muX}(y_{1}\,|\,x)p_{Y\mkern 1.0mu|\mkern
1.0muX}(y_{2}\,|\,x)d\nu(y_{1})d\nu(y_{2})\biggr{\\}}^{1/2}$
$\displaystyle~{}~{}~{}\times\biggl{\\{}\int_{\mathcal{Y}}\frac{\bigl{\\{}p_{Y\mkern
1.0mu|\mkern 1.0muX}(y_{1}\,|\,x)-\widehat{p}_{Y\mkern 1.0mu|\mkern
1.0muX}(y_{1}\,|\,x)\bigr{\\}}^{2}}{p_{Y\mkern 1.0mu|\mkern
1.0muX}(y_{1}\,|\,x)}d\nu(y_{1})\biggr{\\}}^{1/2}\biggl{\\{}\int_{\mathcal{Y}}\frac{\bigl{\\{}p_{Y\mkern
1.0mu|\mkern 1.0muX}(y_{2}\,|\,x)-\widehat{p}_{Y\mkern 1.0mu|\mkern
1.0muX}(y_{2}\,|\,x)\bigr{\\}}^{2}}{p_{Y\mkern 1.0mu|\mkern
1.0muX}(y_{2}\,|\,x)}d\nu(y_{2})\biggr{\\}}^{1/2}$
$\displaystyle~{}~{}~{}\times p_{X}(x)d\nu(x)\Biggr{]}$ $\displaystyle=~{}$
$\displaystyle\int_{\mathcal{X}}\biggl{\\{}\int_{\mathcal{Y}}\int_{\mathcal{Y}}\ell^{2}(y_{1},y_{2})p_{Y\mkern
1.0mu|\mkern 1.0muX}(y_{1}\,|\,x)p_{Y\mkern 1.0mu|\mkern
1.0muX}(y_{2}\,|\,x)d\nu(y_{1})d\nu(y_{2})\biggr{\\}}^{1/2}$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}\times\mathbb{E}\biggl{[}\int_{\mathcal{Y}}\frac{\bigl{\\{}p_{Y\mkern
1.0mu|\mkern 1.0muX}(y_{1}\,|\,x)-\widehat{p}_{Y\mkern 1.0mu|\mkern
1.0muX}(y_{1}\,|\,x)\bigr{\\}}^{2}}{p_{Y\mkern 1.0mu|\mkern
1.0muX}(y_{1}\,|\,x)}d\nu(y_{1})\biggr{]}\times p_{X}(x)d\nu(x)$
$\displaystyle\leq~{}$
$\displaystyle\sup_{x\in\mathcal{X}}\mathbb{E}\biggl{[}\underbrace{\int_{\mathcal{Y}}\frac{\bigl{\\{}p_{Y\mkern
1.0mu|\mkern 1.0muX}(y_{1}\,|\,x)-\widehat{p}_{Y\mkern 1.0mu|\mkern
1.0muX}(y_{1}\,|\,x)\bigr{\\}}^{2}}{p_{Y\mkern 1.0mu|\mkern
1.0muX}(y_{1}\,|\,x)}d\nu(y_{1})}_{=D_{\chi^{2}}(p_{Y\mkern 1.0mu|\mkern
1.0muX=x},\widehat{p}_{Y\mkern 1.0mu|\mkern 1.0muX=x})}\biggr{]}$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}\times\Biggl{\\{}\int_{\mathcal{X}}\int_{\mathcal{Y}}\int_{\mathcal{Y}}\ell^{2}(y_{1},y_{2})p_{Y\mkern
1.0mu|\mkern 1.0muX}(y_{1}\,|\,x)p_{Y\mkern 1.0mu|\mkern
1.0muX}(y_{2}\,|\,x)p_{X}(x)d\nu(y_{1})d\nu(y_{2})d\nu(x)\Biggr{\\}}^{1/2}$

where each step follows by applying the Cauchy–Schwarz inequality as well as
the Fubini–Tonelli theorem. Observing that for any
$y_{1},y_{2}\in\mathcal{Y}$, the following inequality holds

$\displaystyle-\ell(y_{1},y_{1})-\ell(y_{2},y_{2})\leq
2\ell(y_{1},y_{2})\leq\ell(y_{1},y_{1})+\ell(y_{2},y_{2}),$

which yields that

$\displaystyle\int_{\mathcal{X}}\int_{\mathcal{Y}}\int_{\mathcal{Y}}\ell^{2}(y_{1},y_{2})p_{Y\mkern
1.0mu|\mkern 1.0muX}(y_{1}\,|\,x)p_{Y\mkern 1.0mu|\mkern
1.0muX}(y_{2}\,|\,x)p_{X}(x)d\nu(y_{1})d\nu(y_{2})d\nu(x)$
$\displaystyle\leq~{}$
$\displaystyle\int_{\mathcal{X}}\int_{\mathcal{Y}}\ell^{2}(y_{1},y_{1})p_{Y\mkern
1.0mu|\mkern 1.0muX}(y_{1}\,|\,x)\underbrace{\int_{\mathcal{Y}}p_{Y\mkern
1.0mu|\mkern
1.0muX}(y_{2}\,|\,x)d\nu(y_{2})}_{=1}p_{X}(x)d\nu(y_{1})d\nu(x)=\mathbb{E}[\ell(Y,Y)].$

Consequently, we have established that

$\displaystyle\sum_{k=1}^{\infty}\lambda_{k}\mathbb{E}\bigl{[}\bigl{(}\mathbb{E}[\phi_{k}(Y)\,|\,X]-\widehat{\mathbb{E}}[\phi_{k}(Y)\,|\,X]\bigr{)}^{2}\bigr{]}~{}\leq~{}$
$\displaystyle\sup_{x\in\mathcal{X}}\mathbb{E}\bigl{[}D_{\chi^{2}}(p_{Y\mkern
1.0mu|\mkern 1.0muX=x},\widehat{p}_{Y\mkern 1.0mu|\mkern
1.0muX=x})\bigr{]}\sqrt{\mathbb{E}[\ell(Y,Y)]}$ $\displaystyle=~{}$
$\displaystyle o_{\mathcal{P}}\bigl{(}\sqrt{\mathbb{E}[\ell(Y,Y)]}\bigr{)},$

under the condition that
$\sup_{x\in\mathcal{X}}\mathbb{E}\bigl{[}D_{\chi^{2}}(p_{Y\mkern 1.0mu|\mkern
1.0muX=x},\widehat{p}_{Y\mkern 1.0mu|\mkern
1.0muX=x})\bigr{]}=o_{\mathcal{P}}(1)$. This implies that
$\mathbb{E}[(\mathrm{I})]=o_{\mathcal{P}}\bigl{(}n^{-1}\sqrt{\mathbb{E}[\ell(Y,Y)]}\bigr{)}$.

For the second term $(\mathrm{II})$, we express it as the sum of
$(\mathrm{II})_{1}$ and $(\mathrm{II})_{2}$:

$\displaystyle(\mathrm{II})~{}=~{}$
$\displaystyle\sum_{k=1}^{\infty}\lambda_{k}\Gamma_{k}\bigl{(}\widehat{\Gamma}_{k}-\Gamma_{k}\bigr{)}$
$\displaystyle=~{}$
$\displaystyle\sum_{k=1}^{\infty}\lambda_{k}\biggl{(}\frac{1}{n}\sum_{i=1}^{n}\big{\\{}\phi_{k}(Y_{i})-\mathbb{E}[\phi_{k}(Y_{i})\,|\,X_{i}]\big{\\}}+\frac{1}{n+m}\sum_{j=1}^{n+m}\big{\\{}\mathbb{E}[\phi_{k}(Y_{j})\,|\,X_{j}]-\mathbb{E}[\phi_{k}(Y)]\big{\\}}\biggr{)}$
$\displaystyle\underbrace{\times\biggl{(}\frac{1}{n}\sum_{i=1}^{n}\bigl{\\{}\mathbb{E}[\phi_{k}(Y_{i})\,|\,X_{i}]-\widehat{\mathbb{E}}[\phi_{k}(Y_{i})\,|\,X_{i}]-\frac{1}{n+m}\sum_{j=1}^{n+m}\bigl{\\{}\mathbb{E}[\phi_{k}(Y_{j})\,|\,X_{j}]-\widehat{\mathbb{E}}[\phi_{k}(Y_{j})\,|\,X_{j}]\bigr{\\}}\biggr{)}}_{=(\mathrm{II})_{1}}$
$\displaystyle+~{}$
$\displaystyle\sum_{k=1}^{\infty}\lambda_{k}\mathbb{E}[\phi_{k}(Y)]\times\biggl{(}\frac{1}{n}\sum_{i=1}^{n}\bigl{\\{}\mathbb{E}[\phi_{k}(Y_{i})\,|\,X_{i}]-\widehat{\mathbb{E}}[\phi_{k}(Y_{i})\,|\,X_{i}]$
$\displaystyle\underbrace{~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}-\frac{1}{n+m}\sum_{j=1}^{n+m}\bigl{\\{}\mathbb{E}[\phi_{k}(Y_{j})\,|\,X_{j}]-\widehat{\mathbb{E}}[\phi_{k}(Y_{j})\,|\,X_{j}]\bigr{\\}}\biggr{)}}_{=(\mathrm{II})_{2}}.$

Observe that the Cauchy–Schwarz inequality yields

$\displaystyle(\mathrm{II})_{1}^{2}~{}\leq~{}$
$\displaystyle(\mathrm{I})\times\Biggl{[}\sum_{k=1}^{\infty}\lambda_{k}\biggl{(}\frac{1}{n}\sum_{i=1}^{n}\big{\\{}\phi_{k}(Y_{i})-\mathbb{E}[\phi_{k}(Y_{i})\,|\,X_{i}]\big{\\}}$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}+\frac{1}{n+m}\sum_{j=1}^{n+m}\big{\\{}\mathbb{E}[\phi_{k}(Y_{j})\,|\,X_{j}]-\mathbb{E}[\phi_{k}(Y)]\big{\\}}\biggr{)}^{2}\Biggr{]}$

and there exists some constant $C>0$ such that

$\displaystyle\mathbb{E}\Biggl{[}\sum_{k=1}^{\infty}\lambda_{k}\biggl{(}\frac{1}{n}\sum_{i=1}^{n}\big{\\{}\phi_{k}(Y_{i})-\mathbb{E}[\phi_{k}(Y_{i})\,|\,X_{i}]\big{\\}}+\frac{1}{n+m}\sum_{j=1}^{n+m}\big{\\{}\mathbb{E}[\phi_{k}(Y_{j})\,|\,X_{j}]-\mathbb{E}[\phi_{k}(Y)]\big{\\}}\biggr{)}^{2}\Biggr{]}$
$\displaystyle\leq~{}$ $\displaystyle\frac{C}{n}\mathbb{E}[\ell(Y,Y)].$

Therefore, combining with the previous result
$\mathbb{E}[(\mathrm{I})]=o_{\mathcal{P}}\bigl{(}n^{-1}\sqrt{\mathbb{E}[\ell(Y,Y)]}\bigr{)}$,
we have

$\displaystyle\mathbb{E}[|(\mathrm{II})_{1}|]\leq\sqrt{\mathbb{E}\bigl{[}(\mathrm{II})_{1}^{2}\bigr{]}}\leq\frac{C}{n}\sqrt{\mathbb{E}[(\mathrm{I})]}\times\sqrt{\mathbb{E}[\ell(Y,Y)]}=o_{\mathcal{P}}\bigl{(}n^{-1}\\{\mathbb{E}[\ell(Y,Y)]\\}^{3/4}\bigr{)}.$

Next we again follow an analogous approach in the proof of Theorem 1 and show

$\displaystyle\mathbb{E}\bigl{[}(\mathrm{II})_{2}^{2}\bigr{]}\leq\frac{C}{n}\mathbb{E}\biggl{[}\bigg{\\{}\sum_{k=1}^{\infty}\lambda_{k}\mathbb{E}[\phi_{k}(Y)]\bigl{(}\mathbb{E}[\phi_{k}(Y)\,|\,X]-\widehat{\mathbb{E}}[\phi_{k}(Y)\,|\,X]\bigr{)}\bigg{\\}}^{2}\biggr{]}.$

Recall that $\psi_{1}(x)=\mathbb{E}[\ell_{1}(Y)\,|\,X=x]$. The Cauchy–Schwarz
inequality then yields

$\displaystyle\mathbb{E}\biggl{[}\bigg{\\{}\sum_{k=1}^{\infty}\lambda_{k}\mathbb{E}[\phi_{k}(Y)]\bigl{(}\mathbb{E}[\phi_{k}(Y)\,|\,X]-\widehat{\mathbb{E}}[\phi_{k}(Y)\,|\,X]\bigr{)}\bigg{\\}}^{2}\biggr{]}$
$\displaystyle=~{}$
$\displaystyle\mathbb{E}\biggl{[}\int_{\mathcal{X}}\biggl{\\{}\int_{\mathcal{Y}}\bigl{\\{}\ell_{1}(y)-\psi_{1}(x)\bigr{\\}}\bigl{\\{}p_{Y\mkern
1.0mu|\mkern 1.0muX}(y\,|\,x)-\widehat{p}_{Y\mkern 1.0mu|\mkern
1.0muX}(y\,|\,x)\bigr{\\}}d\nu(y)\biggr{\\}}^{2}p_{X}(x)d\nu(x)\biggr{]}$
$\displaystyle\leq~{}$
$\displaystyle\mathbb{E}\biggl{[}\int_{\mathcal{X}}\biggl{\\{}\int_{\mathcal{Y}}\bigl{\\{}\ell_{1}(y)-\psi_{1}(x)\bigr{\\}}^{2}p_{Y\mkern
1.0mu|\mkern 1.0muX}(y\,|\,x)d\nu(y)\biggr{\\}}\times
D_{\chi^{2}}\bigl{(}p_{Y\mkern 1.0mu|\mkern 1.0muX=x},\widehat{p}_{Y\mkern
1.0mu|\mkern 1.0muX=x}\bigr{)}p_{X}(x)d\nu(x)\biggr{]}$ $\displaystyle=~{}$
$\displaystyle\int_{\mathcal{X}}\biggl{\\{}\int_{\mathcal{Y}}\bigl{\\{}\ell_{1}(y)-\psi_{1}(x)\bigr{\\}}^{2}p_{Y\mkern
1.0mu|\mkern
1.0muX}(y\,|\,x)d\nu(y)\biggr{\\}}\times\mathbb{E}\Bigl{[}D_{\chi^{2}}\bigl{(}p_{Y\mkern
1.0mu|\mkern 1.0muX=x},\widehat{p}_{Y\mkern 1.0mu|\mkern
1.0muX=x}\bigr{)}\Bigr{]}p_{X}(x)d\nu(x)$ $\displaystyle\leq~{}$
$\displaystyle\sup_{x\in\mathcal{X}}\mathbb{E}\bigl{[}D_{\chi^{2}}(p_{Y\mkern
1.0mu|\mkern 1.0muX=x},\widehat{p}_{Y\mkern 1.0mu|\mkern
1.0muX=x})\bigr{]}\times\mathbb{E}[\\{\ell_{1}(Y)-\psi_{1}(X)\\}^{2}].$

Hence, under the condition that
$\sup_{x\in\mathcal{X}}\mathbb{E}\bigl{[}D_{\chi^{2}}(p_{Y\mkern 1.0mu|\mkern
1.0muX=x},\widehat{p}_{Y\mkern 1.0mu|\mkern
1.0muX=x})\bigr{]}=o_{\mathcal{P}}(1)$, we have

$\displaystyle\mathbb{E}[|(\mathrm{II})_{2}|]=o_{\mathcal{P}}\bigl{(}\sqrt{n^{-1}\mathbb{E}[\\{\ell_{1}(Y)-\psi_{1}(X)\\}^{2}]}\bigr{)},$

which in turn implies that

$\displaystyle\mathbb{E}[|(\mathrm{II})|]=o_{\mathcal{P}}\bigl{(}n^{-1}\\{\mathbb{E}[\ell(Y,Y)]\\}^{3/4}+\sqrt{n^{-1}\mathbb{E}[\\{\ell_{1}(Y)-\psi_{1}(X)\\}^{2}]}\bigr{)}.$

For the term $(\mathrm{III})$, we observe that

$\displaystyle\mathbb{E}[|(\mathrm{III})|]~{}=~{}$