\mathrm{Var}[T_n]
&\lesssim_{d} \frac{1}{n}\E\left[\max_{1\leq u\leq n}\left\|\sfK(\cdot, X_{u})\right\|_{\cH}^4 + \max_{1\leq u\leq n}\left\|\sfK(\cdot, Y_{u})\right\|_{\cH}^4\right]\nonumber\\
&\lesssim_{d}\frac{1}{n}\E\left[\max_{1\leq u\leq n}\sfK(X_{u},X_{u})^2 + \max_{1\leq u\leq n}\sfK(Y_{u},Y_{u})^2\right]
\end{align}

Now, for $\varepsilon > 0$, define $\varepsilon_n := \varepsilon n^{\frac{4}{4+\delta}}$, and note that

\begin{align}
& \E\left[\max_{1\leq u\leq n}\sfK(X_{u},X_{u})^2 \right] \nonumber \\
& \leq \varepsilon_n + \E\left[\max_{1\leq u\leq n}\sfK(X_{u},X_{u})^2 \bm 1 \left\{ \max_{1\leq u\leq n} \sfK(X_{u},X_{u})^2 > \varepsilon_n \right\} \right] \nonumber \\
& \leq \varepsilon_n + \int_{\varepsilon_n}^{\infty} \P\left(\max_{1\leq u\leq n}\sfK(X_{u},X_{u})^2 \geq t \right) \mathrm dt \nonumber \\
& \leq \varepsilon_n + n \int_{\varepsilon_n}^{\infty} \P( \sfK(X_{1},X_{1})^2 \geq t ) \mathrm dt \tag*{ (by union bound) } \nonumber \\
& \leq \varepsilon_n + n \int_{\varepsilon_n}^{\infty} \frac{\E[\sfK(X_1,X_1)^{2+\delta}]}{t^{1+ \frac{\delta}{2}}} \tag*{ (by Markov's inequality) }
\nonumber \\
&  \lesssim \varepsilon_n + n \int_{\varepsilon_n}^{\infty} \frac{1}{t^{1+ \frac{\delta}{2}}} \tag*{ (since $\E[\sfK(X_1,X_1)^{2+\delta}] < \infty$ by assumption) } \nonumber \\
& \lesssim_{\delta} \varepsilon n^{\frac{4}{4+\delta}} + n^{\frac{ 4 - \delta }{4+\delta}} . \nonumber
\end{align}

Since $\varepsilon$ is arbitrary, this shows

\begin{align}\label{eq:maximumKX}
\E\left[\max_{1\leq u\leq n}\sfK(X_{u},X_{u})^2 \right]  = o\left(n^{\frac{4}{4+\delta}}\right),
\end{align}

and similarly, $\E[\max_{1\leq u\leq n}\sfK(Y_{u}, Y_{u})^2 ]  = o(n^{\frac{4}{4+\delta}})$. Hence, from (<ref>) we conclude,

\begin{align}\label{eq:smalloconsistency1}
\mathrm{Var}[T_n] \lesssim_{d} \frac{1}{n}o\left(n^{\frac{4}{4+\delta}}\right) = o\left(n^{-\frac{\delta}{4 + \delta}}\right) ,
\end{align}

completing the proof of Lemma <ref>.$\Box$

§ PROOFS FOR SECTION <REF>

This section is organized as follows: In Section <ref> we prove
Proposition <ref>. Proposition <ref> is proved in Section <ref>. In Section <ref> we prove Theorem <ref> and in Section <ref> we prove Corollary <ref>.

§.§ Proof of Proposition <ref>

In this section, all equalities involving conditional expectations hold almost surely and we omit writing the same.  With that convention, note that

\begin{align}\label{eq:variancesecondmomentH0}
\mathrm{Var}_{\bH_{0}}[\eta_{n}|\cF(\sZ_n)] = \E_{\bH_{0}}\left[\eta_{n}^2|\cF(\sZ_n)\right],
\end{align}

since $ \E_{\bH_{0}}\left[\eta_{n}|\cF(\sZ_n)\right] = 0$ by (<ref>). Hence,

\begin{align}
\mathrm{Var}_{\bH_{0}}[\eta_{n}|\cF(\sZ_n)]
&= \frac{1}{nK}\E_{\bH_{0}}\left[\left(\sum_{ u , v  \in [n] } \sfH(\bW_{u},\bW_{v})\one\left\{(u,v)\in E(G(\sZ_n))\right\}\right)^2 \bigg| \cF(\sZ_n)\right]\nonumber\\
& = S_1 + S_2 + S_3 ,
\label{eq:condsecondmoment}
\end{align}

where, recalling the definition of the
function $f$ from Proposition <ref>,

\begin{align}\label{eq:S}
S_1 & :=
\frac{1}{nK}\sum_{ u, v \in [n] } \E_{\bH_{0}}[ \sfH^2(\bW_{u},\bW_{v}) |\cF(\sZ_n)] \left(\one\left\{(u,v)\in E(G(\sZ_n))\right\}+ \one\left\{(u,v),(v,u)\in E(G(\sZ_n))\right\}\right)  \nonumber \\
& = \frac{1}{nK}\sum_{ u, v \in [n] } f(Z_u,Z_v)\left(\one\left\{(u,v)\in E(G(\sZ_n))\right\} + \one\left\{(u,v),(v,u)\in E(G(\sZ_n))\right\}\right) \\
S_2 &:=
\frac{1}{nK} \sum_{ \substack{ u, v, u', v' \in [n] \\ |\{u, v\} \cap\{u',v' \}| = 1 }} \E_{\bH_{0}}\left[\sfH(\bW_{u},\bW_{v})\sfH(\bW_{u'},\bW_{v'})|\cF_{n}(\sZ_n)\right]\one\left\{(u, v),(u', v')\in E(G(\sZ_n))\right\}, \nonumber \\
S_3 & := \frac{1}{nK} \sum_{ \substack{ u, v, u', v' \in [n] \\ |\{u, v\} \cap\{u',v' \}| = 0 }} \E_{\bH_{0}} \left[\sfH(\bW_{u},\bW_{v})\sfH(\bW_{u'},\bW_{v'})|\cF_{n}(\sZ_n)\right]\one\left\{(u, v),(u', v')\in E(G(\sZ_n))\right\} .  \nonumber
\end{align}

We begin with $S_2$. For this, let $u, v, u', v' \in [n]$ be such that $|\{u, v\} \cap\{u',v' \}| = 1$. Without loss of generality, assume that $u=u'$ and $v\neq v'$. Then recallng the symmetric property of $\sfH$,

\begin{align*}
\E_{\bH_0}\left[\sfH(\bW_{u},\bW_{v})\sfH(\bW_{u'},\bW_{v'}) |\cF_{n}(\sZ_n)\right]
& = \E_{\bH_0}\left[\sfH(\bW_{v},\bW_{u})\sfH(\bW_{u},\bW_{v'})|Z_{u},Z_{v},Z_{v'}\right].
\end{align*}

Note that, under $\bH_{0}$,

\begin{align}\label{eq:condexp14equal}
\E_{\bH_0}\left[\sfK(X_{v},X_{u})|X_{u}, Z_{u}, Z_{v}\right] = \E_{\bH_0}\left[\sfK(Y_{v},X_{u})|X_{u}, Z_{u}, Z_{v}\right]
\end{align}

\begin{align}\label{eq:condexp23equal}
\E_{\bH_0}\left[\sfK(Y_{v},Y_{u})|Y_{u}, Z_{u}, Z_{v}\right] = \E_{\bH_0}\left[\sfK(X_{v},Y_{u})|Y_{u}, Z_{u}, Z_{v}\right].
\end{align}

\begin{align}\label{eq:condexpfull0}
& \E_{\bH_0} \left[\sfH(\bW_{v},\bW_{u})|\bW_{u},Z_{u},Z_{v},Z_{v'}\right] \nonumber \\
& =\E_{\bH_0}\left[\sfK(X_{v},X_{u})|X_{u}, Z_{u}, Z_{v}\right] + \E_{\bH_0}\left[\sfK(Y_{v},Y_{u})|Y_{u}, Z_{u}, Z_{v}\right] \nonumber \\
& \hspace{0.85in} - \E_{\bH_0}\left[\sfK(X_{v},Y_{u})|Y_{u}, Z_{u}, Z_{v}\right] - \E_{\bH_0}\left[\sfK(Y_{v},X_{u})|X_{u}, Z_{u}, Z_{v}\right] .
\end{align}

By (<ref>) and using the tower property of expectation we have,

\begin{align*}
\E_{\bH_0}\left[\sfH(\bW_{u},\bW_{v})\sfH(\bW_{u'},\bW_{v'})|\cF(\sZ_n)\right] = 0.
\end{align*}

This implies, $S_2 = 0$.

Next, we consider $S_3$. For this, let $u, v, u', v' \in [n]$ be such that $|\{u, v\} \cap\{u',v' \}| = 0$. Then,

\begin{align*}
\E_{\bH_0}\left[\sfH(\bW_{u},\bW_{v})\sfH(\bW_{u'},\bW_{v'})|\cF(\sZ_n)\right]
& = \E_{\bH_0}\left[\sfH(\bW_{u},\bW_{v})\sfH(\bW_{u'},\bW_{v'})| Z_{u},Z_{v},Z_{u'},Z_{v'}\right]\\
& = \E_{\bH_0}\left[\sfH(\bW_{u},\bW_{v})| Z_{u},Z_{v}\right]\E_{\bH_0}\left[\sfH(\bW_{u'},\bW_{v'})| Z_{u'},Z_{v'}\right]
\end{align*}

Now under $\bH_{0}$, recalling (<ref>) we have,

\begin{align*}
\E_{\bH_0}\left[\sfH(\bW_{u},\bW_{v})\sfH(\bW_{u'},\bW_{v'})|\cF_{n}(\sZ_n)\right] = 0 .
\end{align*}

This implies, $S_3 = 0$.

The proof of Proposition <ref> is completed by replacing the terms in the RHS of (<ref>) with $S_1$ from (<ref>), $S_2=0$, and $S_3 = 0$. $\Box$

§.§ Proof of Proposition <ref>

The proof of Proposition <ref> in based on the following 2 lemmas. First, we show that $\hat{\sigma}_n^2$ is close to $\Var_{\bH_0}[\eta_n|\cF(\sZ_n)]$ in $L^2$ (see Appendix <ref> for the proof).

Under the assumptions of Proposition <ref>,

\begin{align*}
\E_{\bH_0}\left[\left(\hat{\sigma}_n^2 - \Var_{\bH_0}[\eta_n|\cF(\sZ_n)]\right)^2\right] = o\left(n^{-\frac{\delta}{8 + \delta}}\right) .
\end{align*}

Note that the above result shows that the difference of $\hat{\sigma}_n^2$ and $\Var_{\bH_0}[\eta_n|\cF(\sZ_n)]$ are close in $L^2$. To translate this into an approximation in the ratio form as in (<ref>) we show in the following lemma $\Var_{\bH_0}[\eta_n|\cF(\sZ_n)]$ is asymptotically bounded away from $0$ (see Appendix <ref> for the proof).

Under the assumptions of Proposition <ref>, for all $\vep>0$,

\begin{align*}
\P_{\bH_0}\left[n^\vep\Var_{\bH_0}[\eta_n|\cF(\sZ_n)]> t\right]\ra 1.
\end{align*}

for all $t>0$.

To complete the proof of Proposition <ref> using the above lemmas, first define $\gamma = \frac{\delta}{8 + \delta}$. Note that by Lemma <ref> the probability $\P_{\bH_0}\left[n^{\frac{\gamma}{4}}\Var_{\bH_0}\left[\eta_{n}|\cF_n(\cZ_{n})\right]\leq 1\right] = o(1)$. Hence for all $\vep>0$,

\begin{align}
\small
\P_{\bH_0}\bigg[\left|\frac{\hat{\sigma}_n^2}{\Var_{\bH_0}\left[\eta_{n}|\cF_n(\cZ_{n})\right]} - 1\right|
&\geq \vep n^{-\frac{\delta}{32 + 4\delta}}\bigg]\nonumber\\
& \leq \P_{\bH_0}\left[n^{\frac{\gamma}{4}}\left|\hat{\sigma}_n^2 - \Var_{\bH_0}\left[\eta_{n}|\cF_n(\cZ_{n})\right]\right|\geq\vep n^{-\frac{\delta}{32 + 4\delta}}\right] + o(1)\nonumber\\
& \leq \frac{n^{\frac{\gamma}{2}}}{\vep^2 n^{-\frac{\delta}{16 + 2\delta}}}\E_{\bH_0}\left[\left(\hat{\sigma}_n^2 - \Var_{\bH_0}\left[\eta_{n}|\cF_n(\cZ_{n})\right]\right)^2\right] + o(1)\nonumber\\
& = \frac{n^{\gamma}}{\vep^2}\E_{\bH_0}\left[\left(\hat{\sigma}_n^2 - \Var_{\bH_0}\left[\eta_{n}|\cF_n(\cZ_{n})\right]\right)^2\right] + o(1)\ra 0 , \label{eq:completesigmavar}
\end{align}

where the last step uses Lemma <ref>. This completes the proof of Proposition <ref>.

§.§.§ Proof of Lemma <ref>

Recalling the definition of $\hat{\sigma}_n^2$ from (<ref>)

$$\hat{\sigma}_n^2 = S_{n} + \tilde{S}_{n},$$

\begin{align}\label{eq:defSn1}
S_{n} := \frac{1}{nK}\sum_{u=1}^{n}\sum_{v=1}^{n}\sfH^{2}\left(\bW_{u},\bW_{v}\right)\one\left\{(u,v)\in E(G(\sZ_n))\right\} ,
\end{align}

\begin{align}\label{eq:defSn2}
\tilde{S}_{n} := \tilde{S}_{n}(\bcW_{n},\cZ_{n}) = \frac{1}{nK}\sum_{u=1}^{n}\sum_{v=1}^{n}\sfH^{2}\left(\bW_{u},\bW_{v}\right)\one\left\{(u,v),(v,u)\in E(G(\sZ_n))\right\}.
\end{align}

Similarly, recalling the definition of $\Var_{\bH_0}[\eta_n|\cF(\sZ_n)]$ from (<ref>) define

$$\Var_{\bH_0}[\eta_n|\cF(\sZ_n)] = V_{n} + \tilde{V}_{n},$$

\begin{align}\label{eq:Vn}
V_{n} := \frac{1}{nK}\sum_{u=1}^{n}\sum_{v = 1}^{n}f(Z_u,Z_v)\one\left\{(u,v)\in E(G(\sZ_n))\right\},
\end{align}

\begin{align}\label{eq:Vnuv}
\tilde{V}_{n} := \frac{1}{nK}\sum_{u=1}^{n}\sum_{v = 1}^{n}f(Z_u,Z_v)\one\left\{(u,v),(v,u)\in E(G(\sZ_n))\right\}.
\end{align}

Here, recall that

\begin{align}\label{eq:deff2}
f(Z,Z')= \E_{\bH_0}\left[\sfH^2(\bW,\bW') |Z,Z'\right] ,
\end{align}

where $\bW = (X,Y),\bW' = (X',Y')$ and $(X,Y,Z)$, $(X',Y',Z')$ are sampled independently from $ P_{XYZ}$.

To complete the proof of Lemma <ref> it is enough to show that,

\begin{align}\label{eq:SnVndiffconvg}
\E_{\bH_0}\left[(S_{n} - V_{n})^2\right] = o\left(n^{-\frac{\delta}{8 + \delta}}\right) \text{ and } \E_{\bH_0}\left[(\tilde{S}_{n} - \tilde{V}_{n})^2\right]  = o\left(n^{-\frac{\delta}{8 + \delta}}\right).
\end{align}

We will show this in Lemma <ref> and Lemma <ref>, respectively.
For notational convenience, as before, we define $\gamma = \frac{\delta}{8 + \delta}$.

Suppose the assumptions of Proposition <ref> hold. Let $S_n$ and $V_n$ be as defined in (<ref>) and (<ref>), respectively. Then

\begin{align}\label{eq:SnVn}
\E_{\bH_0}\left[(S_{n} - V_{n})^2\right] = o\left(n^{-\gamma}\right) .
\end{align}

The proof proceeds by showing that both $S_{n}$ and $V_{n}$ concentrate around $\E_{\bH_0}[S_{n}]$ in $L^2$, that is,

\begin{align}\label{eq:S_nV_npf}
\E_{\bH_0}\left[\left(S_{n} - \E[S_{n}]\right)^2\right] = o\left(n^{-\gamma}\right)  \text{ and } \E_{\bH_0}\left[\left(V_{n} - \E[S_{n}]\right)^2\right] = o\left(n^{-\gamma}\right) .
\end{align}

From (<ref>) the result in (<ref>) is immediate.

First, we show that $S_{n}$ concentrates around $\E_{\bH_0}[S_{n}]$ in $L^2$. To begin with, notice that $S_{n}$ (recall (<ref>)) has the exactly the same form as $T_n$ (that is, $\emmdstat$) in (<ref>) with $\sfH$ replaced by $\sfH^2$.
Hence, following the proof of (<ref>) in Section <ref> with $\sfH$ replaced by $\sfH^2$ gives,

\begin{align}\label{eq:centerSnbdd}
\E_{\bH_0}\left[\left(S_{n} - \E_{\bH_0}\left[S_{n}\right]\right)^2\right]\lesssim_{d}\frac{1}{n}\E_{\bH_0}\left[\left(\max_{1\leq u\neq v\leq n}\sfH^2(\bW_{u},\bW_{v})\right)^2\right] .
\end{align}

Now, recalling (<ref>), $\sfH$ can be rewritten as:

\begin{align}\label{eq:Hasinprod}
\sfH(\bw,\bw') = \left\langle\sfK(x,\cdot) - \sfK(y,\cdot),\sfK(x',\cdot) - \sfK(y,\cdot)\right\rangle.
\end{align}

Hence, by Cauchy Schwarz inequality and the bound $\|a + b\|_{\cH}^m\leq 2^{m-1}\left(\|a\|_{\cH}^m + \|b\|_{\cH}^{m}\right)$,

\begin{align}
\E_{\bH_0}\left[\left(\max_{1\leq u\neq v\leq n}\sfH^2(\bW_{u},\bW_{v})\right)^2\right] & \leq \E_{\bH_0}\left[\left(\max_{1\leq u\leq n}\left\|\sfK(\cdot, X_{u}) - \sfK(\cdot, Y_{u})\right\|_{\cH}^4\right)^2\right] \nonumber \\
& \lesssim \E_{\bH_0}\left[\max_{1\leq u\leq n}\|\sfK(\cdot,X_{u})\|_{\cH}^8 + \max_{1\leq u\leq n}\|\sfK(\cdot,Y_{u})\|_{\cH}^8\right]\nonumber\\
& = \E_{\bH_0}\left[\max_{1\leq u\leq n}\sfK(X_{u},X_{u})^4 + \max_{1\leq u\leq n}\sfK(Y_{u},Y_{u})^4\right] , \label{eq:4thexpbd}
\end{align}

where the last equality follows from the reproducing property of $\sfK$. Now, since by assumption $\E_{\bH_0}\left[\sfK(X_{1},X_{1})^{4 + \delta}\right]<\infty$ and $\E_{\bH_0}\left[\sfK(Y_{1},Y_{1})^{4 + \delta}\right]<\infty$, for some $\delta>0$, by arguments similar to (<ref>) it follows that

\begin{align*}
\E_{\bH_0}\left[\max_{1\leq u\leq n}\sfK(X_{u},X_{u})^4 \right]  = o\left(n^{\frac{8}{8+\delta}}\right) \text{ and } \E_{\bH_0}\left[\max_{1\leq u\leq n}\sfK(Y_{u}, Y_{u})^4 \right]  = o\left(n^{\frac{8}{8+\delta}}\right) .
\end{align*}

Hence, combining the above with (<ref>)  and (<ref>) we conclude,

\begin{align}\label{eq:onconvg}
\E_{\bH_0}\left[\left(S_{n} - \E[S_{n}]\right)^2\right]\lesssim_{d}\frac{1}{n}\E_{\bH_0}\left[\left(\max_{1\leq u\neq v\leq n}\sfH^2(\bW_{u},\bW_{v})\right)^2\right] = o\left(n^{-\gamma}\right) ,
\end{align}

establishing the concentration of $S_n$ as in (<ref>).

Next, we proceed to show that $V_{n}$ (recall (<ref>)) also concentrates around $\E[S_{n}]$. By a conditional expectation argument and recalling (<ref>) it is easy to see that,

\begin{align}\label{eq:VnSnZ}
\E_{\bH_0}[V_{n}] = \E_{\bH_0}[S_{n}] .
\end{align}

Once again, following the proof of (<ref>) in  Section <ref> gives,

\begin{align*}
\E_{\bH_0}\left[\left(V_{n} - \E_{\bH_0}[S_{n}]\right)^2\right] = \E_{\bH_0}\left[\left(V_{n} - \E_{\bH_0}\left[V_{n}\right]\right)^2\right]
& \lesssim_{d} \frac{1}{n}\E_{\bH_0}\left[\left(\max_{1\leq u\neq v\leq n}f(Z_{u},Z_{v})\right)^2\right].
\end{align*}

Recalling the definition of $f$ from (<ref>) and applying Jensen's inequality shows,

\begin{align}\label{eq:f22bound}
\E_{\bH_0}\left[\left(\max_{1\leq u\neq v\leq n}f(Z_{u},Z_{v})\right)^2\right] & \leq \E_{\bH_0}\left[\E_{\bH_0}\left[\max_{1\leq u\neq v\leq n}\sfH(\bW_{u},\bW_{v})^4|\cF(\sZ_n)\right]\right] \nonumber \\
& = \E_{\bH_0}\left[\max_{1\leq u\neq v\leq n}\sfH^{4}(\bW_{u},\bW_{v})\right] .
\end{align}

Finally, following arguments as in (<ref>) and (<ref>) we conclude,

\begin{align}\label{eq:Vn1ESn1close}
\E_{\bH_0}\left[\left(V_{n} - \E_{\bH_0}[S_{n}]\right)^2\right] = o(n^{-\gamma}) .
\end{align}

This proves the concentration of $V_n$ as in (<ref>) and completes the proof of Lemma <ref>.

Now, we proceed to show the $\tilde{S}_{n}$ and $\tilde{V}_{n}$ are close in $L^2$ as in stated in (<ref>). The proof is similar is Lemma <ref>, so we omit some details.

Under the assumptions of Proposition <ref>, $S_n$ and $V_n$ as defined in (<ref>) and (<ref>), respectively,

\begin{align*}
\E_{\bH_0}\left[(\tilde{S}_{n} - \tilde{V}_{n})^2\right] = o\left(n^{-\gamma}\right)
\end{align*}

As in the previous lemma, the proof involves showing that both $\tilde{S}_{n}$ and $\tilde{V}_{n}$ are close to $\E_{\bH_0}[\tilde{S}_{n}]$ in $L^2$.
We begin with by analyzing $\tilde{S}_{n}$. As in Lemma <ref>, we will apply the Efron-Stein inequality. For this, suppose $(\bW_1', Z_1'), (\bW_2', Z_2'), \ldots, (\bW_n', Z_n')$, where $\bm W_i' = (X_i', Y_i')$, for $1 \leq i \leq n$, are generated i.i.d. from the joint distribution $P_{XYZ}$, independent of the data $(\bW_{1},Z_{1}),\ldots, (\bW_{n},Z_{n})$. As in (<ref>),  define a new collection

\begin{align*}
\bcW_{n, s} := \left(\bcW_n \setminus\{\bW_{s}\}\right)\bigcup\{ \bW_{s}'\}\text{ and }\cZ_{n,s} := \left(\sZ_n\setminus\{Z_{s}\}\right)\bigcup\{Z_{s}'\} ,
\end{align*}

where we replace the $s$-th data point with an independent copy. (Recall that $\bcW_n:= \{\bW_i = (X_i,Y_i):1\leq i\leq n \}$ and $\sZ_n := \{Z_1,Z_2,\ldots,Z_n\}$.) Now, recalling (<ref>), consider,

\begin{align*}
\tilde{S}_{n, s} = \tilde{S}_{n}(\bcW_{n,s},\cZ_{n,s}) ,
\end{align*}

that is, $\tilde{S}_{n, s}$ is defined as in (<ref>) evaluated using the samples $\bcW_{n,s}$ and $\cZ_{n,s}$ (instead of $\bcW_{n}$ and $\cZ_{n}$). Now, by arguments similar to the proof of (<ref>) it can be shown that

\begin{align*}
|\tilde{S}_{n} - \tilde{S}_{n, s}|\lesssim_{d}\frac{1}{n}\left[\max_{1\leq u\neq v\leq n}\left|\sfH^2(\bW_{u},\bW_v)\right| + \max_{1\leq u\neq v\leq n}\left|\sfH^2\left(\bW_{u,s},\bW_{v,s}\right)\right|\right] ,
\end{align*}

where $\bW_{u,s}$ is defined in (<ref>). The Efron-Stein inequality and (<ref>) implies,

\begin{align}\label{eq:onvareq}
\E_{\bH_0}\left[\left(\tilde{S}_{n} - \E_{\bH_0}[\tilde{S}_{n}]\right)\right]\lesssim_{d}\frac{1}{n}\E_{\bH_0}\left[\left(\max_{1\leq u\neq v\leq n}\sfH^2(\bW_{u},\bW_{v})\right)^2\right] = o(n^{-\gamma}) .
\end{align}

This shows that $\tilde{S}_{n}$ concentrates around $\E_{\bH_0}[\tilde{S}_{n}]$.

Next, we will show that $\tilde{V}_{n}$ concentrates around $\E_{\bH_0}[\tilde{S}_{n}]$. For this, repeating the arguments in the proof of (<ref>) with $\tilde{S}_{n}$ replaced by $\tilde{V}_{n}$ gives,

\begin{align*}
\E_{\bH_0}\left[\left(\tilde{V}_{n} - \E_{\bH_0}\left[\tilde{V}_{n}\right]\right)^2\right]\lesssim_{d}\frac{1}{n}\E_{\bH_0}\left[\left(\max_{1\leq u\neq v\leq n}f^2(Z_u,Z_v)\right)^2\right] .
\end{align*}

Further, the tower property of expectation shows that $\E_{\bH_0}[\tilde{V}_{n}] = \E_{\bH_0}[\tilde{S}_{n}]$, which implies,

\begin{align*}
\E_{\bH_0}\left[\left(\tilde{V}_{n} - \E_{\bH_0}\left[\tilde{S}_{n}\right]\right)^2\right]
& \lesssim_{d}\frac{1}{n}\E_{\bH_0}\left[\left(\max_{1\leq u\neq v\leq n}f^2(Z_u,Z_v)\right)^2\right]\\
&\leq \frac{1}{n}\E_{\bH_0}\left[\max_{1\leq u\neq v\leq n}\sfH^{4}(\bW_{u},\bW_{v})\right] = o(n^{-\gamma}) ,
\end{align*}

by (<ref>) and (<ref>). This shows that $\tilde{V}_{n}$ concentrates around $\E_{\bH_0}[\tilde{S}_{n}]$, which completes the proof of Lemma <ref>.

The proof of Lemma <ref> is now completed by recalling (<ref>) and the results in Lemma <ref> and Lemma <ref>.

§.§.§ Proof of Lemma <ref>

Using (<ref>) and recalling the expression of $\E_{\bH_{0}}\left[\eta_{n}^2\middle|\cF(\sZ_n)\right]$ from (<ref>) notice,

\begin{align*}
\Var_{\bH_{0}}\left[\eta_n\middle|\cF(\sZ_n)\right] & = \E_{\bH_{0}}\left[\eta_{n}^2\middle|\cF(\sZ_n)\right] \nonumber \\
& \geq \frac{1}{nK}\sum_{u=1}^{n}\sum_{v = 1}^{n}\E_{\bH_0}\left[\sfH^2(\bW_u,\bW_v)\middle|\cF(\sZ_n)\right]\one\left\{(u,v)\in E(G(\sZ_n))\right\} .
\end{align*}

Therefore, to complete the proof of Lemma <ref> it is now enough to show that there exists $c>0$ such that,

\begin{align}\label{eq:EH2condpositive}
\frac{1}{nK}\sum_{u=1}^{n}\sum_{v = 1}^{n}\E_{\bH_0}\left[\sfH^2(\bW_u,\bW_v)\middle|\cF(\sZ_n)\right]\one\left\{(u,v)\in E(G(\sZ_n))\right\}\pto c .
\end{align}

Recalling (<ref>) and (<ref>), to prove (<ref>) it suffices to show that

\begin{align*}
\E_{\bH_0}\left[\frac{1}{nK}\sum_{u=1}^{n}\sum_{v=1}^{n}\sfH^{2}\left(\bW_{u},\bW_{v}\right)\one\left\{(u,v)\in E(G(\sZ_n))\right\}\right]\ra c.
\end{align*}

The proof is now completed by invoking Lemma <ref> and Lemma <ref>.

§.§ Proof of Theorem <ref>

To begin with define,

\begin{align}\label{eq:defVu}
V_{u} := \frac{1}{\sqrt{nK}}\sum_{v\in N_{G(\sZ_n)}(u)}\sfH\left(\bW_{u},\bW_{v}\right), \text{ for all }1\leq u\leq n.
\end{align}

Then $\eta_n$ (recall (<ref>)) can be written as:

\begin{align*}
\eta_{n} = \sum_{u=1}^{n}V_{u} .
\end{align*}

We will prove the CLT of  $\eta_{n}$ using Stein's method based on dependency graphs [Chen and Shao, 2004]. For this, we need to construct a dependency graph for the random variables $\{V_{u}:1\leq u\leq n\}$. To this end, denote by $G^*(\sZ_n)$ the undirected simple graph obtained from the the $K$-NN graph $G(\sZ_n)$, that is,
we remove the directions from the edges and if for a pair of vertices there are directed edges in both directions, we keep only an undirected edge between them. Then we can construct a dependency graph $\cG_n = (V(\cG_n), E(\cG_n))$ as follow: $V(\cG_n) = \{V_{u}:1\leq u\leq n\} $ and there is an edge between $V_u$ and $V_v$, for $1 \leq u \ne v \leq n$, if and only if there exists a path of length $\leq 2$ between $u$ and $v$ in the graph $G^*(\sZ_n)$. Note that if $A, B \in [n]$ is such that there are no edges from the set $\{V_u\}_{u \in A}$ to the set $\{V_u\}_{u \in B}$ in the graph  $\mathcal{G}_n$ , then 2 collections $\{V_u\}_{u \in A}$ and  $\{V_u\}_{u \in B}$ are independent of each other given $\cF(\cZ_{n})$.

Denote by $\Delta$ the maximum degree of a vertex in the dependency graph $\cG_n$. Since the maximum degree of the graph $G^*(\sZ_n)$ is bounded by $c(d) K$, for some constant $c(d) > 0$ depending on the dimension (see <cit.>), it follows that $\Delta \leq C(d) K^2$, for some constant $C(d) > 0$. Now, applying the Stein's method error bound in <cit.>, recalling (<ref>), and denoting $\sigma_n^2:=\Var_{\bH_0}\left[\eta_{n}|\cF(\cZ_{n})\right]$ we have,

\begin{align*}
\sup_{z\in \R}\left|\P_{\bH_0}\left[\frac{\eta_{n}}{\sigma_n}\leq z \middle|\cF(\cZ_{n})\right] - \Phi(z)\right|\lesssim_{d} \frac{K^{20}}{\sigma_n^3} \E_{\bH_0}\left[\sum_{i=1}^{n}|V_{i}|^3 \middle|\cF(\cZ_{n})\right] ,
\end{align*}

almost surely. Using the tower property of conditional expectation gives,
\begin{align}
\sup_{z\in \R}\left|\P_{\bH_0}\left[\frac{\eta_{n}}{\sigma_n}\leq z\right] - \Phi(z)\right|
& \lesssim_{d} \E_{\bH_0}\left[ \frac{K^{20}}{\sigma_n^3} \E_{\bH_0}\left[\sum_{i=1}^{n}|V_{i}|^3 \middle|\cF(\cZ_{n})\right]  \right] . \label{eq:bddonsteindiff}
\end{align}

Note that by Lemma <ref>,

\begin{align}
\E_{\bH_0}\Bigg[ \frac{K^{20}}{\sigma_n^3} \E_{\bH_0}\bigg[\sum_{u=1}^{n}|V_{u}|^3\bigg|
&\cF(\cZ_{n})\bigg] \Bigg]\nonumber\\
& \leq \E_{\bH_0}\left[ \frac{K^{20}}{\sigma_n^3} \E_{\bH_0}\left[\sum_{u=1}^{n}|V_{u}|^3|\cF(\cZ_{n})\right] \one\left\{n^{\vep} \sigma_n^2 \geq 1\right\} \right] + o(1) \nonumber \\
& \leq  K^{20}n^{\frac{3\vep-1}{2}}\E_{\bH_0}\left[\sqrt{n}\E_{\bH_0}\left[\sum_{u=1}^{n}|V_{u}|^3|\cF(\cZ_{n})\right]\right] + o(1) .
\label{eq:bddExpmin2}
\end{align}

The following provides an upper bound on the RHS of from (<ref>).

Under the conditions of Theorem <ref>,

\begin{align*}
\E_{\bH_0}\left[\sqrt{n}\E_{\bH_0}\left[\sum_{u=1}^{n}|V_{u}|^3 \middle|\cF(\cZ_{n})\right]\right]\lesssim_{\sfK} K^{\frac{3}{2}}.
\end{align*}

The proof of Lemma <ref> is given in Appendix <ref>. First we complete the proof of Theorem <ref> using this lemma. To this end, combining (<ref>), (<ref>), and Lemma <ref> gives,

\begin{align}\label{eq:etacltH0}
\sup_{z\in \R}\left|\P_{\bH_0}\left[\frac{\eta_{n}}{\sigma_n}\leq z\right] - \Phi(z)\right| \lesssim_{d,\sfK} K^{\frac{43}{2}}n^{\frac{3\vep-1}{2}} + o(1) = o(1) ,
\end{align}

where the final equality follows by choosing $\vep<\frac{1}{132}$.
To complete the proof of Theorem <ref> we have to replace $\sigma_n^2$ by $\hat{\sigma}_n^2$ in (<ref>). This follows by (<ref>).

§.§.§ Proof of Lemma <ref>

Recall the definition of $V_u$, for $1 \leq u \leq n$, from (<ref>). Then by Hölder's inequality,

\begin{align}\label{eq:bddonsumV}
\sqrt{n}\sum_{u=1}^{n}|V_{u}|^3 & \leq \frac{1}{nK^{\frac{3}{2}}}\sum_{u=1}^{n}\left(\sum_{v\in N_{G(\sZ_n)}(u)}|\sfH(\bW_{u},\bW_{v})|\right)^3 \nonumber \\
& \leq \frac{\sqrt{K}}{n}\sum_{u=1}^{n}\sum_{v\in N_{G(\sZ_n)}(u)}|\sfH(\bW_{u},\bW_{v})|^3 .
\end{align}

Using the representation of $\sfH$ in (<ref>) and the Cauchy-Schwartz inequality,

\begin{align*}
& \sum_{u=1}^{n}\sum_{v\in N_{G(\sZ_n)}(u)}
|\sfH(\bW_{i},\bW_{j})|^3 \nonumber \\
& \leq \sum_{u=1}^{n}\sum_{v\in N_{G(\sZ_n)}(u)}\left\|\sfK(X_{u},\cdot) - \sfK(Y_{u},\cdot)\right\|_{\cH}^{3}\left\|\sfK(X_{v},\cdot) - \sfK(Y_{v},\cdot)\right\|_{\cH}^{3} \nonumber \\
& \lesssim \sum_{u=1}^{n}\sum_{v\in N_{G(\sZ_n)}(u)}\left(\left\|\sfK(X_{u},\cdot)\right\|_{\cH}^{3} + \left\|\sfK(Y_{u},\cdot)\right\|_{\cH}^{3}\right)\left(\left\|\sfK(X_{v},\cdot)\right\|_{\cH}^{3} + \left\|\sfK(Y_{v},\cdot)\right\|_{\cH}^{3}\right) ,
\end{align*}

where the last step uses the inequality $\|a+b\|_{\cH}^m\leq 2^{m-1}(\|a\|_{\cH}^m + \|b\|_{\cH}^m)$, for $m \geq 1$. Finally, recalling the reproducing property of $\sfK$ gives,

\begin{align}\label{eq:bddonsumh3}
& \sum_{u=1}^{n} \sum_{v\in N_{G(\sZ_n)}(u)}
&\lesssim \sum_{u=1}^{n}\sum_{v\in N_{G(\sZ_n)}(u)}\left(\sfK(X_{u},X_{u})^{\frac{3}{2}} + \sfK(Y_{u},Y_{u})^{\frac{3}{2}}\right)\left(\sfK(X_{v},X_{v})^{\frac{3}{2}} + \sfK(Y_{v},Y_{v})^{\frac{3}{2}}\right) .
\end{align}

Now, for $(X,Y,Z)\sim P_{XYZ}$ define,

\begin{align}\label{eq:defbetafn}
\beta(Z) := \E_{\bH_0}\left[\sfK(X,X)^{\frac{3}{2}} + \sfK(Y,Y)^{\frac{3}{2}} |Z\right].
\end{align}

By the moment assumption on $\sfK$ and from <cit.> it follows that $\beta:\cZ\ra\R$ is a well defined  measurable function. Hence, from (<ref>) and (<ref>),

\begin{align}
\E_{\bH_0}\left[\sqrt{n}\E_{\bH_0}\left[\sum_{u=1}^{n}|V_{u}|^3|\cF(\cZ_{n})\right]\right] & \lesssim\frac{\sqrt{K}}{n}\E_{\bH_0}\left[\sum_{u=1}^{n}\sum_{v\in N_{G(\sZ_n)}(u)}\beta(Z_{u})\beta(Z_{v})\right] \nonumber \\
&\lesssim K^{\frac{3}{2}}\E_{\bH_0}\left[\frac{1}{nK}\sum_{u=1}^{n}\sum_{v\in N_{G(\sZ_n)}(u)}\beta(Z_{u})\beta(Z_{v})\right] \nonumber \\
& = K^{\frac{3}{2}}\E_{\bH_0}\left[\frac{1}{K}\sum_{v\in N_{G(\sZ_n)}(1)}\beta(Z_{1})\beta(Z_{v})\right] \nonumber \\
& = K^{\frac{3}{2}}\E_{\bH_0}\left[\beta(Z_{1})\beta(Z_{N(1)})\right] ,
\label{eq:CLTproofuniformN1}
\end{align}

where $N(1)$ is a neighbor of the vertex 1 in the graph $G(\sZ_n)$ chosen uniformly at random. By Cauchy-Schwarz inequality and <cit.>,

\begin{align}\label{eq:CLTproofCauchySch}
K^{\frac{3}{2}}\E_{\bH_0}\left[\beta(Z_{1})\beta(Z_{N(1)})\right] & \leq K^{\frac{3}{2}}\left(\E_{\bH_0}\left[\beta(Z_{1})^2\right]\right)^{\frac{1}{2}}\left(\E_{\bH_0}\left[\beta\left(Z_{N(1)}\right)^2\right]\right)^{\frac{1}{2}} \nonumber \\
& \lesssim K^{\frac{3}{2}}\E_{\bH_0}\left[\beta(Z_{1})^2\right] .
\end{align}

Combining (<ref>) and (<ref>) gives,

\begin{align}\label{eq:1stbddbeta}
\E_{\bH_0}\left[\sqrt{n}\E_{\bH_0}\left[\sum_{u=1}^{n}|V_{u}|^3|\cF(\cZ_{n})\right]\right]\lesssim K^{\frac{3}{2}}\E_{\bH_0}\left[\beta(Z_{1})^2\right].
\end{align}

To complete the proof, recalling the definition of the function $\beta$ from (<ref>) note that,

\begin{align}\label{eq:2ndbddbeta}
\E_{\bH_0}\left[\beta(Z_{1})^2\right]
& = \E_{\bH_0}\left[\left(\E_{\bH_0}\left[\sfK(X_{1},X_{1})^{\frac{3}{2}} + \sfK(Y_{1},Y_{1})^{\frac{3}{2}}|Z_{1}\right]\right)^2\right] \nonumber \\
& \lesssim \E_{\bH_0}\left[\sfK(X_{1},X_{1})^3 + \sfK(Y_{1},Y_{1})^3\right]<\infty ,
\end{align}

by the moment assumption on $\sfK$. The proof of Lemma <ref> is now completed by substituting the bound from (<ref>) in (<ref>).  $\Box$

§.§ Proof of Corollary <ref>

From (<ref>) recall,

\begin{align*}
\eta_{n}=\sqrt{nK}\emmdstatsq ,
\end{align*}

where $\bcW_n = \{\bW_i = (X_i,Y_i):1\leq i\leq n\}$ and $\sZ_n = \{Z_1,\ldots,Z_n\}$. By Theorem <ref> we know that under $\bH_1$,

\begin{align*}
\emmdstatsq \pto \EMMD\left[\cF, P_{X|Z}, P_{Y|Z}\right]>0 ,
\end{align*}

where the positivity of the limit follows from Proposition <ref>. Now, recalling $\phi_n$ from (<ref>), note that to prove Corollary <ref> it is now enough to show that under $\bH_1$, $\hat{\sigma}_n = O_P(1)$. Towards this, from (<ref>),

\begin{align*}
\hat{\sigma}_n^2 & = \frac{1}{nK}\sum_{u=1}^{n}\sum_{v=1}^{n}\sfH^{2}\left(\bW_{u},\bW_{v}\right)\left(\one\left\{(u,v)\in E(G(\sZ_n))\right\}+\one\left\{(u,v),(v,u)\in E(G(\sZ_n))\right\}\right) \nonumber \\
& \leq \frac{2}{nK}\sum_{u=1}^{n}\sum_{v=1}^{n}\sfH^{2}\left(\bW_{u},\bW_{v}\right)\one\left\{(u,v)\in E(G(\sZ_n))\right\}.
\end{align*}

We know from (<ref>) and (<ref>) that

\begin{align*}
\E_{\bH_1}\left[ \frac{1}{nK}\sum_{u=1}^{n}\sum_{v=1}^{n}\sfH^{2}\left(\bW_{u},\bW_{v}\right)\one\left\{(u,v)\in E(G(\sZ_n))\right\}\right] = O(1).
\end{align*}

This implies, $\hat{\sigma}_n = O_{P}(1)$ under $\bH_1$ and completes the proof of Corollary <ref>.

§ PROOFS FROM SECTION <REF>

This section is organized as follows: In Section <ref> we prove Proposition <ref>. Theorem <ref> is proved in Section <ref> and Theorem <ref> is  proved in Section <ref>.

§.§ Proof of Proposition <ref>

Recall that under $\bH_0$, $X$ and $Y$ have the same distribution conditioned on $Z$. Now, recall the finite sample test  described in Section <ref>. Observe that conditional on $\sZ_n$, the samples $(Y_1,\ldots,Y_n)$ are independent and identically distributed as the
samples $\{X_1^{(m)},\ldots, X_n^{(m)}\}$, for all $1 \leq m\leq M+1$.
As a result, the collection $\{ \eta_{n}^{(m)}, 1 \leq m\leq M+1 \}$ (as defined in (<ref>)) are exchangeable conditioned on $\sZ_n$. Thus, recalling (<ref>),

\begin{align*}
\P_{\bH_0}[ \tilde{\phi}_{n, M} = 1|\cF(\sZ_n)] = \P_{\bH_0}\left[p_M\leq \alpha|\cF(\sZ_n)\right]=\frac{\lfloor (M+1)\alpha\rfloor }{M+1}\leq\alpha.
\end{align*}

Taking expectations on both sides show the result in Proposition <ref> (1).

To prove the consistency of the test $\tilde{\phi}_{n,M}$ in Proposition <ref> (2) we start by observing that under $\bH_1$,

\begin{align*}
\frac{\eta_{n}^{(m)}}{\sqrt{nK}}\pto 0 \text{ for all }1\leq m\leq M\text{ and }\frac{\eta_{n}^{(M+1)}}{\sqrt{nK}}\pto \EMMD\left[\cF, P_{X|Z}, P_{Y|Z}\right]>0,
\end{align*}

where the last inequality follows from Proposition <ref>. Consequently, $\one\{\eta_{n}^{(m)}\geq \eta_{n}^{(M+1)}\} = o_{P}(1)$, for all $1\leq m\leq M$. Hence,

\begin{align*}
p_M = \frac{1}{M+1}\left[1 + \sum_{m=1}^{M}\one\left\{\eta_{n}^{(m)}\geq \eta_{n}^{(M+1)}\right\}\right] \pto \frac{1}{M+1}.
\end{align*}

The proof is now completed by choosing $M > \frac{1}{\alpha}-1$.

§.§ Proof of Theorem <ref>

The proof is similar to the proof of Theorem <ref> in Appendix <ref>. To begin with, define

$$\tilde{\bW}_{u} = \left(X_{u}^{(1)},\ldots, X_{u}^{(M_n)}, Y_u \right),$$
for $1\leq u\leq n$. Then $D_n$ in (<ref>) can be expressed as:

\begin{align}\label{eq:defDnHbar}
D_n = \frac{1}{nK}\sum_{u=1}^{n}\sum_{v\in N_{G(\sZ_n)}(u)}\bar{\sfH}\left(\tilde{\bW}_{u},\tilde{\bW}_{v}\right),
\end{align}

\begin{align}\label{eq:defbarH}
\bar{\sfH}\left(\tilde{\bW}_{u},\tilde{\bW}_{v}\right) = \frac{1}{M_n}\sum_{m=1}^{M_n}\sfH\left(\bW_{u}^{(m)},\bW_{v}^{(m)}\right), \quad \text{ for all }1\leq u,v\leq n ,
\end{align}

and $\bW_{u}^{(m)} = (X_u^{(m)}, Y_{u})$, for $1\leq m\leq M_n$. The expression (<ref>) shows that $D_n$  has the exact same form as the estimate $\emmdstatsq$ in (<ref>) with $\sfH$ replaced by $\bar{\sfH}$. Hence, following the combinatorial arguments from Section <ref>, in particular the proof of (<ref>) with $T_n$ replaced by $D_n$ shows,

\begin{align*}
\E\left[\left(D_n - \E D_n\right)^2\right]
&\lesssim_d\frac{1}{n}\E\left[\left(\max_{1\leq u\neq v\leq n}\left|\bar{\sfH}\left(\tilde{\bW}_{u},\tilde{\bW}_{v}\right)\right|\right)^2\right]\\
&\leq\frac{1}{nM_n}\sum_{m=1}^{M_n}\E\left[\left(\max_{1\leq u\neq v\leq n}\left|\sfH\left(\bW_{u}^{(m)},\bW_{v}^{(m)}\right)\right|\right)^2\right] ,
\end{align*}

where the last inequality follows by the definition of $\bar{\sfH}$ from (<ref>) and the Cauchy-Schwarz inequality. By the sampling scheme from Section <ref>, for any $1\leq m\leq M_n$, the collection $\{(X_{u}^{(m)},Y_{u}, Z_{u} \}_{1 \leq u \leq n}$ are generated i.i.d. from $P_{XYZ}$. Then,

\begin{align*}
\E\left[\left(D_n - \E D_n\right)^2\right]
&\lesssim_d\frac{1}{n}\E\left[\left(\max_{1\leq u\neq v\leq n}\left|\sfH\left(\bW_{u}^{(1)}, \bW_{v}^{(1)} \right)\right|\right)^2\right].
\end{align*}

Note that the above upper bound is same as that (<ref>). Hence proceeding as in (<ref>) and (<ref>) we conclude,

\begin{align*}
\E\left[\left(D_n - \E D_n\right)^2\right]  = o\left(n^{-\frac{\delta}{4+\delta}}\right).
\end{align*}

Now, recalling (<ref>), to complete the proof of Theorem <ref> it is enough to show that,

\begin{align*}
\E[D_n]\ra\E\left[\left\|g_{Z_1} \right\|_{\cH}^2\right] ,
\end{align*}

where $g_{Z_1}  = \E\left[\sfK(\cdot,X_1) - \sfK(\cdot,Y_1)\middle|Z_1\right]$ is defined in Lemma <ref>.
For this, exchangeability and the definition of $D_n$ in (<ref>) gives,

\begin{align*}
\left|\E[D_n] - \E\left[\left\|g_{Z_1} \right\|_{\cH}^2\right]\right| = \left|\E\left[\frac{1}{K}\sum_{v=1}^{n}\bar{\sfH}\left( \tilde{\bW}_1, \tilde{\bW}_{v}\right)\one\left\{(1,v)\in E\left(\sZ_n\right)\right\}\right] - \E\left[\left\|g_{Z_1}(\cdot)\right\|_{\cH}^2\right]\right| .
\end{align*}

Now, observe that for $1\leq v\leq n$,

\begin{align*}
\E\left[\bar{\sfH}\left( \tilde{\bW}_{1}, \tilde{\bW}_{v}\right)\middle|Z_1,Z_v\right] = \frac{1}{M_n}\sum_{m=1}^{n}\E\left[\sfH\left(\bW_{1}^{(m)}, \bW_{v}^{(m)}\right)\middle|Z_1,Z_v\right] = \left\langle g_{Z_1}, g_{Z_v} \right\rangle_{\cH} .
\end{align*}

where the last equality follows by observing that the collection $\{(X_u^{(m)}, Y_{u}, Z_{u})\}_{1 \leq u \leq n}$ are generated i.i.d. from $P_{XYZ}$, for any $1\leq m\leq M_n$, and the definition of $\sfH$.

\begin{align*}
\left|\E[D_n] - \E\left[\left\|g_{Z_1}(\cdot)\right\|_{\cH}^2\right]\right| \leq \E\left[\frac{1}{K}\sum_{u=1}^{n}\left|\langle g_{Z_{1}}, g_{Z_{u}}\rangle_{\cH} - \|g_{Z_{1}}\|_{\cH}^2\right|\I\left\{(1,u)\in E(G(\sZ_n))\right\}\right] .
\end{align*}

Notice that the upper bound in the RHS above is same as that in  (<ref>). Hence, the proof of Theorem <ref> is now completed by following the subsequent arguments from the proof of Lemma <ref> in Section <ref>.

§.§ Proof of Theorem <ref>

To begin with, observe from (<ref>) that $\E_{\bH_0}\left[D_n\middle|\cF(\sZ_n)\right] = 0$. In the following lemma we compute the conditional variance of $D_n$ under $\bH_0$.

Denote by $\tau_n^2:= \Var_{\bH_0}\left[\sqrt{nK}D_n\middle|\cF(\sZ_n)\right]$, the conditional variance of $\sqrt{nK}D_n$ given $\cF(\sZ_n)$  under $\bH_0$. Then,

\begin{align*}
\tau_n^2 = \frac{1}{nK}\sum_{ 1 \leq u\neq v \leq n} \ell_n(Z_u,Z_v) \left( \one\left\{(u,v)\in E(G(\sZ_n))\right\} + \one\left\{(u,v),(v,u)\in E(G(\sZ_n))\right\} \right),
\end{align*}

where $\ell_n(Z_u,Z_v) := \E_{\bH_0}[\bar{\sfH}^2(\tilde{\bW}_{u},\tilde{\bW}_{v}) |Z_u,Z_v]$, with $\bar{\sfH}(\tilde{\bW}_{u},\tilde{\bW}_{v})$ defined in (<ref>), for all $1\leq u\neq v\leq n$.

Recalling definition of $\bar{H}$ from (<ref>) gives,

\begin{align*}
\E_{\bH_0}\left[\bar{\sfH}\left(\tilde{\bW}_{u},\tilde{\bW}_{v}\right)\middle|\tilde{\bW}_{v},Z_u,Z_v\right] = \frac{1}{M_n}\sum_{m=1}^{M_n}\E_{\bH_0}\left[\sfH\left(\bW_{u}^{(m)},\bW_{v}^{(m)}\right)\middle|\bW_{v}^{(m)},Z_u,Z_v\right] = 0,
\end{align*}

where the last equality follows from (<ref>), (<ref>), and (<ref>). The proof of Lemma <ref> can now be completed by repeating the proof of  Proposition <ref> from Appendix <ref> with $\eta_n$ replaced by $\sqrt{nK}D_n$.

Next, we show that $\hat{\tau}_n^2$ as defined in (<ref>) is a  consistent estimate $\tau_n^2$. The proof is given in Appendix <ref>.

Suppose Assumption <ref> and Assumption <ref> hold. Moreover, assume $(X,Y,Z)\sim P_{XYZ}$ is such that $\P\left[X\neq Y\right]>0$ and $\int \sfK(x,x)^{4+\delta}\mathrm{d} P_X(x)<\infty$, $\int \sfK(x,x)^{4+\delta}\mathrm{d} P_Y(x)<\infty$, for some $\delta>0$. Then under $\bH_0$, with $K = o(n/\log n)$ and $M_n\ra\infty$ as $n\ra\infty$,

\begin{align*}
\left|\frac{\hat{\tau}_n^2}{\tau_n^2}-1\right| = o_P\left(n^{-\frac{\delta}{32 + 4\delta}}\right) ,
\end{align*}

where $\hat{\tau}_n^2$ and $\tau_n^2$ are defined in (<ref>) and Lemma <ref>, respectively.

With the above lemmas, we now ready to complete with the proof of Theorem <ref>. Once again, drawing parallels with $\eta_n$ (recall (<ref>)) and $\sqrt{nK}D_n$ define,

\begin{align*}
\tilde{V}_{u} = \frac{1}{\sqrt{nK}}\sum_{v\in N_{G(\sZ_n)}(u)}\bar{\sfH}\left(\tilde{\bW}_{u},\tilde{\bW}_{v}\right),\ 1\leq u\leq n.
\end{align*}

Following the arguments from Section <ref> with $V_u$ replaced by $\tilde{V}_{u}$, for $1\leq u\leq n$, and using (<ref>) we get,

\begin{align*}
\sup_{z\in \R}\left|\P_{\bH_0}\left[\frac{\sqrt{nK}D_n}{\tau_n}\leq z\right] - \Phi(z)\right|
& \lesssim_{d} K^{20}n^{\frac{3\vep-1}{2}}\E_{\bH_0} \left[\sqrt{n}\E_{\bH_0} \left[\sum_{u=1}^{n}| \tilde{V}_{u}|^3 \bigg|\cF(\cZ_{n})\right]\right] + o(1) ,
\end{align*}

for any $\vep<\frac{1}{132}$.
Hence, to complete the proof of Theorem <ref> it is enough to show that,

\begin{align}\label{eq:VZ}
\E_{\bH_0}\left[\sqrt{n}\E_{\bH_0}\left[\sum_{u=1}^{n}| \tilde{V}_u |^3 \bigg |\cF(\cZ_{n})\right]\right]\lesssim_{\sfK}K^{\frac{3}{2}}.
\end{align}

Towards this, by (<ref>) and Hölder's inequality observe that,

\begin{align*}
\sqrt{n}\sum_{u=1}^{n} | \tilde{V}_u |^3
&\leq \frac{\sqrt{K}}{n}\sum_{u=1}^{n}\sum_{v\in N_{G(\sZ_n)}(u)}\left|\bar{\sfH}\left(\tilde{\bW}_{u},\tilde{\bW}_{v}\right)\right|^3\\
&\leq \frac{\sqrt{K}}{n}\sum_{u=1}^{n}\sum_{v\in N_{G(\sZ_n)}(u)}\frac{1}{M_n}\sum_{m=1}^{M_n}\left|\sfH\left(\bW_{u}^{(m)},\bW_{v}^{(m)}\right)\right|^3.
\end{align*}

\begin{align*}
& \E_{\bH_0}\left[\sqrt{n}\E_{\bH_0}\left[\sum_{u=1}^{n}| \tilde{V}_{u}|^3 \bigg| \cF(\cZ_{n})\right]\right] \nonumber \\
& \leq \frac{\sqrt{K}}{nM_n}\sum_{m=1}^{M_n}\E_{\bH_0}\left[\E_{\bH_0}\left[\sum_{u=1}^{n}\sum_{v\in N_G(\sZ_n)(u)}\left|\sfH\left(\bW_{u}^{(m)},\bW_{v}^{(m)}\right)\right|^3\middle|\cF(\cZ_{n})\right]\right] .
\end{align*}

Now, recalling (<ref>) and the definition of $\beta(\cdot)$ from (<ref>) we get,

\begin{align*}
\E_{\bH_0}\left[\sqrt{n}\E_{\bH_0}\left[\sum_{u=1}^{n}| \tilde{V}_{u}|^3|\cF(\cZ_{n})\right]\right]
&\leq \frac{\sqrt{K}}{nM_n}\sum_{m=1}^{M_n}\E_{\bH_0}\left[\sum_{u=1}^{n}\sum_{v\in N_G(\sZ_n)(u)}\beta(Z_u)\beta(Z_v)\right]\\
& = \frac{\sqrt{K}}{n}\E_{\bH_0}\left[\sum_{u=1}^{n}\sum_{v\in N_G(\sZ_n)(u)}\beta(Z_u)\beta(Z_v)\right]\lesssim K^{\frac{3}{2}},
\end{align*}

where the last inequality follows from (<ref>), (<ref>), (<ref>), and (<ref>). This completes the proof of (<ref>). Collecting the trail of inequalities we now have,

\begin{align}\label{eq:supdiff}
\sup_{z\in \R}\left|\P_{\bH_0}\left[\frac{\sqrt{nK}D_n}{\tau_n}\leq z\right] - \Phi(z)\right|\lesssim_{d,\sfK} K^{\frac{43}{2}}n^{\frac{3\vep-1}{2}} = o(1)
\end{align}

where the final equality follows by recalling $K = o(n^{1/44})$ and $\vep<\frac{1}{132}$. Replacing $\tau_n$ with $\hat{\tau}_n$ in (<ref>) by Lemma <ref>, gives the result in Theorem <ref>. $\Box$

§.§.§ Proof of Lemma <ref>

Drawing parallels between $\hat{\sigma}_n^2$ (recall (<ref>)) and $\tau_n^2$; and between $\eta_n$ (recall (<ref>)) and $\sqrt{nK}D_n$, we will proceed along similar lines as the proof of Proposition <ref> from Section <ref>. In particular, as in Lemma <ref> we first show that,

\begin{align}\label{eq:SndiffvarDn}
\E_{\bH_0}\left[\left(\hat{\tau}_n^2 - \tau_n^2 \right)^2\right] = o\left(n^{-\frac{\delta}{8 + \delta}}\right).
\end{align}

From the proof of Lemma <ref> from Section <ref>, note that (<ref>) holds as long as,

\begin{align*}
\frac{1}{n}\E_{\bH_0}\left[\max_{1\leq u\neq v\leq n}\bar{\sfH}\left(\tilde{\bW}_{u},\tilde{\bW}_{v}\right)^4\right] = o\left(n^{-\frac{\delta}{8 + \delta}}\right).
\end{align*}

Towards this, using Hölder's inequality gives,

\begin{align*}
\left|\bar{\sfH}\left(\tilde{\bW}_{u},\tilde{\bW}_{v}\right)\right| \leq \frac{1}{M_n}\left(\sum_{m=1}^{M_n}\left|\sfH\left(\bW_{u}^{(m)},\bW_{v}^{(m)}\right)\right|^4\right)^\frac{1}{4}M_n^{\frac{3}{4}}.
\end{align*}

Hence, recalling that for any $1\leq m\leq M_n$, the collection
$\{ ( X_1^{(m)},Y_{1}, Z_{1} ), \ldots, (X_n^{(m)}, Y_{n}, Z_n ) \}$ are generated i.i.d. from $P_{XYZ}$, we get,

\begin{align*}
\frac{1}{n}\E_{\bH_0}\left[\max_{1\leq u\neq v\leq n}\bar{\sfH}\left(\tilde{\bW}_{u},\tilde{\bW}_{v}\right)^4\right]
&\leq \frac{1}{nM_n}\sum_{m=1}^{M_n}\E_{\bH_0}\left[\max_{1\leq u\neq v\leq n}\left|\sfH\left(\bW_{u}^{(m)},\bW_{v}^{(m)}\right)\right|^4\right]\\
& = \frac{1}{n}\E_{\bH_0}\left[\max_{1\leq u\neq v\leq n}\left|\sfH\left(\bW_{u}^{(1)},\bW_{v}^{(1)}\right)\right|^4\right] = o\left(n^{-\frac{\delta}{8 + \delta}}\right),
\end{align*}

where the last equality follows by (<ref>). Having shown (<ref>), notice that to complete the proof of Lemma <ref> we have to translate (<ref>) in to an approximation in terms of the ratio of $\hat{\tau}_n^2$ and $\tau_n^2$. This will be done as in Lemma <ref> by proving the following: For all $\vep>0$,

\begin{align}\label{eq:epsVarDn}
\P_{\bH_0}\left[n^\vep\Var_{\bH_0}\left[\sqrt{nK}D_n\middle|\cF(\sZ_n)\right]>t\right] \ra 1 ,
\end{align}

whenever $t>0$. Again, following the proof of Lemma <ref>, to prove (<ref>) it suffices to show that there exists $c>0$ such that

\begin{align}\label{eq:Hbar2toc}
\E_{\bH_0}\left[\frac{1}{nK}\sum_{u=1}^{n}\sum_{v\in N_{G(\sZ_n)}(u)}\bar{\sfH}^2(\tilde{\bW}_{u},\tilde{\bW}_{v})\right]\ra c.
\end{align}

To evaluate the expectation on the LHS, recall the sampling scheme from Section <ref> to get,

\begin{align}\label{eq:expandHbar}
\E_{\bH_0}\bigg[\frac{1}{nK}\sum_{u=1}^{n}\sum_{v\in N_{G(\sZ_n)}(u)}
&\bar{\sfH}^2(\tilde{\bW}_{u},\tilde{\bW}_{v})\bigg] = \frac{1}{M_n} B_1 + \frac{M_n-1}{M_n} B_2 ,
\end{align}

\begin{align}
B_1 & : = \E_{\bH_0}\left[\frac{1}{nK}\sum_{u=1}^{n}\sum_{v\in N_{G(\sZ_n)}(u)}\sfH^2(\bW_{u}^{(1)},\bW_{v}^{(1)})\right] , \nonumber \\
B_2 & : = \E_{\bH_0}\left[\frac{1}{nK}\sum_{u=1}^{n}\sum_{v\in N_{G(\sZ_n)}(u)}\sfH(\bW_{u}^{(1)},\bW_{v}^{(1)})\sfH(\bW_{u}^{(2)},\bW_{v}^{(2)})\right] . \nonumber
\end{align}

Note, from Lemma <ref>, in particular (<ref>) and (<ref>),  $B_1/M_n = o(1)$. Also, by arguments similar to the proof of Lemma <ref>, $B_2 \rightarrow \E_{\bH_0}[\|\bar{h}(Z)\|_{\cH\otimes\cH}^2]$,
where $\bar{h}$ is defined as:

\begin{align*}
& \bar{h}(Z) \nonumber \\
& := \E_{\bH_0}\left[\sfK(X,\cdot)\otimes\sfK(X,\cdot) - \sfK(X,\cdot)\otimes\sfK(Y^\prime,\cdot) - \sfK(Y,\cdot)\otimes\sfK(X,\cdot) + \sfK(Y,\cdot)\otimes\sfK(Y^\prime,\cdot)|Z\right]  ,
\end{align*}

with $X\sim P_{X|Z = Z}$ and $ Y,Y^\prime$ are i.i.d. $P_{Y|Z = Z}$ independent of $X|Z$.
Thus, taking $M_n\ra\infty$ in the RHS of (<ref>) gives,

$$\E_{\bH_0}\bigg[\frac{1}{nK}\sum_{u=1}^{n}\sum_{v\in N_{G(\sZ_n)}(u)}
\bar{\sfH}^2(\tilde{\bW}_{u},\tilde{\bW}_{v})\bigg] \rightarrow \E_{\bH_0}\left[\|\bar{h}(Z)\|_{\cH\otimes\cH}^2\right].$$

Hence, to complete the proof of (<ref>) (and, as a result,  (<ref>)), it is now enough to show that $\E_{\bH_0}\left[\|\bar{h}(Z)\|_{\cH\otimes\cH}^2\right]\neq 0$. For the sake of contradiction assume that  $\E_{\bH_0}\left[\|\bar{h}(Z)\|_{\cH\otimes\cH}^2\right] = 0$. Then, by arguments similar to the proof of Lemma <ref> we conclude that for $(X,Y,Z)\sim P_{XYZ}$, $X = Y$ almost surely. Recall that by construction that $P_{XYZ} = P_{X|Z}\times P_{Y|Z}\times P_{Z}$, hence from the arguments in the proof of <cit.> we arrive at a contradiction.

The proof of Lemma <ref> now follows by the arguments in (<ref>) together with (<ref>) and (<ref>). $\Box$

§ TECHNICAL RESULTS

In this section we collect some technical about tensor product spaces. The following results hold under both $\bH_0$ and $\bH_1$,  hence we refrain from explicitly mentioning the same.

The tensor product space $\cH\otimes\cH$  is the collection of functions $f\otimes g:\cX\times\cX\ra\R$, where $f, g\in \cH$ and $(f\otimes g)(x,x') := f(x)g(x')$. The inner product in the space $\cH\otimes\cH$ is defined as follows: For $f_1, f_2, g_1, g_2 \in \cH$,

\begin{align*}
\left\langle f_{1}\otimes g_{1},f_{2}\otimes g_{2}\right\rangle_{\cH\otimes\cH} = \left\langle f_{1}, f_{2}\right\rangle_{\cH}\left\langle g_{1}, g_{2}\right\rangle_{\cH}.
\end{align*}

For $(X,Y,Z)\sim P_{XYZ}$, define $h_{Z} \in \cH\otimes\cH$ as follows:

\begin{align*}
h_{Z} := \E\left[\sfK(X,\cdot)\otimes\sfK(X,\cdot) - \sfK(X,\cdot)\otimes\sfK(Y,\cdot) - \sfK(Y,\cdot)\otimes\sfK(X,\cdot) + \sfK(Y,\cdot)\otimes\sfK(Y,\cdot)|Z\right] .
\end{align*}

Suppose Assumption <ref> and Assumption <ref> holds. Moreover, suppose the kernel $\sfK$ satisfies
\begin{align}\label{eq:momentassumpXY}
\int\sfK(x,x)^{4+\delta}\rmd P_{X}(x)<\infty \text{ and }\int\sfK(y,y)^{4+\delta}\rmd P_{Y}(y)<\infty,
\end{align}

for some $\delta>0$. Then with $K = o(n/\log n)$, as $n \rightarrow \infty$

\begin{align}\label{eq:EH2condconvg}
\E\left[\frac{1}{nK}\sum_{u=1}^{n}\sum_{v=1}^{n}\sfH^{2}\left(\bW_{u},\bW_{v}\right)\one\left\{(u,v)\in E(G(\sZ_n))\right\}\right]\ra \E\left[\left\|h_{Z_{1}}\right\|_{\cH\otimes\cH}^2\right]
\end{align}

where $\bW_i = (X_i, Y_i)$ for all $1\leq i\leq n$, $\sZ_n = \{Z_1,\ldots, Z_n\}$ and $\{(X_i, Y_i, Z_i), 1\leq i\leq n\}$ are generated independently from $P_{XYZ}$.

For $\bw = (x,y)\in \cX\times\cX$ define,

\begin{align*}
\sfL_{\bw} := \sfK(x,\cdot)\otimes\sfK(x,\cdot) - \sfK(x,\cdot)\otimes\sfK(y,\cdot) - \sfK(y,\cdot)\otimes\sfK(x,\cdot) + \sfK(y,\cdot)\otimes\sfK(y,\cdot).
\end{align*}

By definition, $\sfL_{\bw} \in \cH\otimes\cH$ and from (<ref>) it follows that,

\begin{align*}
\sfH^{2}(\bw,\bw') = \left\langle\sfL_{\bw},\sfL_{\bw'} \right\rangle
\end{align*}

for all $\bw, \bw' \in \cX\times\cX$. Now, following the arguments in the proof of (<ref>) it can shown that,

\begin{align}\label{eq:hbarvarlimitidff}
& \left| \E\left[\frac{1}{nK}\sum_{u=1}^{n}\sum_{v=1}^{n}\sfH^{2}\left(\bW_{u},\bW_{v}\right)\one\left\{(u,v)\in E(G(\sZ_n))\right\}\right]  - \E\left[\left\|h_{Z_1}\right\|_{\cH\otimes\cH}^2\right]\right| \nonumber \\
& \leq \sqrt{\E\left[\left\|h_{Z_1}\right\|_{\cH\otimes\cH}^2\right]}\sqrt{\E\left[\left\|h_{Z_{N(1)}} - h_{Z_{1}}\right\|_{\cH\otimes\cH}^2\right]} ,
\end{align}

where $N(1)$ is a uniformly selected index from the neighbors of vertex $1$ in the graph $G(\sZ_n)$. From <cit.>,

\begin{align}\label{eq:hZN1}
\E\left[\left\|h\left(Z_{N(1)}\right) - h_{Z_{1}}\right\|_{\cH\otimes\cH}^4\right]\lesssim \E\left[\left\|h_{Z_{1}}\right\|_{\cH\otimes\cH}^4\right].
\end{align}

Also, as in the proof of (<ref>),

\begin{align}
\E\left[\left\|h_{Z_{1}}\right\|_{\cH\otimes\cH}^4\right]\lesssim
&\ \E\left[\sfK(X_{1},X_{1})^4 + 2\sfK(X_{1},X_{1})^2\sfK(Y_{1},Y_{1})^2 + \sfK(Y_{1},Y_{1})^4\right]<\infty , \label{eq:exphZfinite}
\end{align}

where the finiteness follows from the moment assumption in (<ref>). Combining (<ref>) and (<ref>) shows that $\|h_{Z_{N(1)}} - h_{Z_{1}}\|_{\cH\otimes\cH}^2$ is uniformly integrable, Hence, by <cit.>
$$\left\|h_{Z_{N(1)}} - h_{Z_{1}} \right\|_{\cH\otimes\cH}^2 \pto 0.$$
Using this and (<ref>) in (<ref>) completes the proof of Lemma <ref>.

In the following lemma we prove that the limit from (<ref>) is strictly positive.

Suppose the assumptions in Lemma <ref> hold. Also, assume that $(X,Y,Z)\sim P_{XYZ}$ is such that $P_{XY}\left[X\neq Y\right]>0$. Then for $h_Z \in \cH\otimes\cH$ as defined in Lemma <ref>,

\begin{align*}
\E\left[\left\|h_{Z}\right\|_{\cH\otimes\cH}^2\right] > 0.
\end{align*}

The proof will proceed by contradiction. For this, suppose, if possible, $\E[\|h_{Z}\|_{\cH\otimes\cH}^2] = 0$. Then for any $r\in \cH$ by <cit.> we have,

\begin{align}\label{eq:expinnerprod}
\E\left[\left|\left\langle r\otimes r, h_{Z}\right\rangle_{\cH\otimes\cH} \right|\right] = \E\left[\left|r(X)^2 - 2r(X)r(Y) + r(Y)^2\right|\right] = \E\left[(r(X) - r(Y))^2\right]
\end{align}

By the Cauchy-Schwarz inequality,

\begin{align*}
\E\left[\left|\left\langle r\otimes r, h_{Z}\right\rangle_{\cH\otimes\cH} \right|\right]\leq \left\|r\otimes r\right\|_{\cH\otimes\cH}\sqrt{\E\left[\left\|h_{Z}\right\|_{\cH\otimes\cH}^2\right]} = 0 .
\end{align*}

Then (<ref>) implies, $r(X) = r(Y)$ almost surely for all $r\in \cH$. Recalling the seperability of $\cH$ we can extend the above conclusion to $r(X) = r(Y)$ for all $r\in \cH$ almost surely.
Then, for all $x\in \cX$ choosing $r(\cdot) = \sfK(x,\cdot)$ gives,

\begin{align*}
\sfK(x,X) = \sfK(x,Y)\ \text{ for all } x\in \cX\text{ almost surely.}
\end{align*}

Hence, $\sfK(X,\cdot) = \sfK(Y,\cdot)$ almost surely, and by  <cit.> we conclude that $X = Y$ almost surely. This contradicts the assumption $P_{XY}(X\neq Y)>0$ and completes the proof of Lemma <ref>.

§ RELIABILITY DIAGRAMS AND RECALIBRATION

This section is organized as follows. In Section <ref> we provide a brief of review reliability diagrams and describe how the expected calibration error (ECE) is computed in the experiments in Section <ref>. In Section <ref> we discuss the recalibration method based on isotonic regression.

§.§ Reliability Diagrams and Computation of ECE

Suppose $Y\in \{0,1\}$ is a binary response associated with feature vector $Z\in \cZ$. Let $f:\cZ\ra [0,1]$ be a predicitve model, such that $f(Z)$ estimates $\P\left[Y=1\middle| Z\right]$ (notice that for each $z\in \cZ$, $f(z)$ defines a distribution over $\{0,1\}$). Furthemore, we assume access to test samples $\{(Y_i, Z_i): 1\leq i\leq n\}$ to construct reliability diagrams and estimate the ECE.

§.§.§ Reliability Diagrams

Reliability diagrams are visual tools to represent calibration of predictive model from finite samples (see [DeGroot and Fienberg, 1983, Niculescu-Mizil and Caruana, 2005, Gweon and Yu, 2019, Bröcker and Smith, 2007]). In this section we follow the construction from Gweon and Yu, 2019 and Bröcker and Smith, 2007 to briefly describe reliability diagrams in the context of calibration for binary predictive models. Towards this, recall from (<ref>) that a predictive model $f$ is said to be calibrated if and only if,

\begin{align}\label{eq:binarycal}
\P\left[Y=1|f(Z)\right] = f(Z)\text{ almost surely }P_Z.
\end{align}

The continuous nature of the conditioning random variable makes it hard to have a visual depiction of the above identity from finite samples. Thus, one adopts a binning approach to approximate conditional probabilities in (<ref>). To this end, fix $M \geq 2$ and for $m\in [M] := \{1, 2, \ldots, M\}$ let $I_m = \left(\frac{m-1}{M}, \frac{m}{M}\right]$. Then by (<ref>) for a perfectly calibrated model,

\begin{align}\label{eq:condexpreliability}
\P\left[Y = 1|f(Z)\in I_m\right] = \E\left[f(Z)|f(Z)\in I_m\right]\text{ for all }, 1\leq m\leq M.
\end{align}

We can now estimate the quantities in  (<ref>) from the test samples as follows: For all $m\in [M]$, let $B_m$ be the set of indices of test samples whose prediction falls into the interval $I_m$. Observe that,

\begin{align}\label{eq:LandRBm}
L(B_m) = \frac{1}{|B_m|}\sum_{i\in B_m}\one\left\{Y_i=1\right\}\text{ and }R(B_m) = \frac{1}{|B_m|}\sum_{i\in B_m}f(Z_i)
\end{align}

are natural estimates of $\P\left[Y = 1|f(Z)\in I_m\right]$ and $\E\left[f(Z)|f(Z)\in I_m\right]$, respectively. Then the reliability diagram is the curve joining the points $\{(L(B_m),R(B_m)):1\leq m\leq M\}$. For calibrated predictive models $f$ we expect the curve to be close to the diagonal line.

§.§.§ Computation of ECE

The Expected Calibration Error (ECE) of a predictor $f$ [Guo et al., 2017, Naeini et al., 2015], also known as the mean calibration error [Frank, 2015], is defined as,

\begin{align}\label{eq:defECE}
\text{ECE}(f) = \E_{Z\sim P_{Z}}\left[\left|\P\left[Y=1\middle|f(Z)\right] - f(Z)\right|\right],
\end{align}

which is the expectation of the absolute difference of both sides in the identity from (<ref>). By definition, a predictive model $f$ is calibrated if and only if $\text{ECE}(f) = 0$. (In (<ref>) define the ECE with the $\ell_1$ norm, but other variants using the $\ell_p$ norm, for $p\geq 1$, are also studied (see [Lee et al., 2023, Arrieta-Ibarra et al., 2022]).) To estimate ECE from test samples we once again follow the binning strategy from Section <ref>. Following [Lee et al., 2023], first note that $\text{ECE}(f)$ can be approximated by piecewise averaging as follows:

\begin{align*}
\text{ECE}(f)
& \geq \sum_{m=1}^{M}\P(f(Z)\in I_m)\left|\E\left[\P\left[Y=1\middle|f(Z)\right] - f(Z)\middle|f(Z)\in I_m\right]\right|\\
& = \sum_{m=1}^{M}\P\left(f(Z)\in I_m\right)\left|\P\left[Y=1\middle|f(Z)\in I_m\right] - \E\left[f(Z)\middle|f(Z)\in I_m\right]\right|.
\end{align*}

Recalling (<ref>) the RHS above can be estimated as,

\begin{align*}
\widehat{\text{ECE}}(f) = \sum_{m=1}^{M}\frac{|B_m|}{n}\left|L(B_m) - R(B_m)\right|,
\end{align*}

which is used as an approximate measure of $\text{ECE}(f)$ from test samples.

§.§ Recalibration Based on Isotonic Regression

Isotonic regression is a well-known approach for recalibrating the prediction probabilities of a binary classifier (see [Guo et al., 2017, Berta et al., 2024, Zadrozny and Elkan, 2002, Zhong and Kwok, 2013] and references therein). Here, we briefly recall this method. For this, suppose in a binary classification problem a predictive model outputs potentially miscalibrated probabilities $\hat p_1,\ldots,\hat p_n$ for the positive class in a test set of size $n$. To recalibrate the probabilities one learns a non-decreasing, piecewise constant transformation $\hat q_i = \mathsf{q}(\hat p_i)$ that minimizes the squared error loss $\sum_{i=1}^n\left(\mathsf{q}(\hat p_i) -Y_i\right)^2$, where $Y_i\in \{0,1\}$ is the observed response of the $i$-th test sample. Leveraging the piecewise constant condition on $\mathsf{q}$, isotonic regression considers the following optimization problem:

\begin{align*}
\min_{\overset{M,\theta_1,\ldots,\theta_M}{a_1,\ldots,a_{M+1}}}\sum_{m=1}^M \sum_{i=1}^n \mathbf{1}\{a_m\leq \hat p_i<a_{m+1}\}(\theta_m-y_i)^2 ,
\end{align*}

such that $0=a_1\leq a_1\leq \ldots\leq a_{M+1}=1$ and $\theta_1\leq \theta_1\leq \ldots\leq \theta_M$. Here, $M$ is the number of intervals, $\{a_i:1\leq i\leq M\}$ are the endpoints of the intervals and
$\theta_1,\ldots,\theta_M$ are the function values.