Given this connection, our proof strategy is to leverage known results of the
U-statistic along with a careful analysis of the difference between
$V_{\mathrm{MMD}}$ and $U_{\mathrm{MMD}}$. Writing the sensitivity of
$\sqrt{V_{\mathrm{MMD}}}$ as $\Delta_{V^{1/2}}$, Lemma 17 ensures that the
$\mathrm{dpMMD}$ test rejects the null if and only if

$\displaystyle\sqrt{V_{\mathrm{MMD}}}+\frac{2\Delta_{V^{1/2}}}{\xi_{\varepsilon,\delta}}\zeta_{0}>q_{1-\alpha,B},$

where $q_{1-\alpha,B}$ is the $1-\alpha$ quantile of
$\\{\sqrt{V_{\bm{\pi}_{i},\mathrm{MMD}}}+2\Delta_{V^{1/2}}\xi_{\varepsilon,\delta}^{-1}\zeta_{i}\\}_{i=0}^{B}$.
We then closely follow the proof steps given in Section E.4 to prove the
claim.

Bounding the type II error. As in the proof of Theorem 4 in Section E.4, we
let $q_{1-\alpha,B}^{a}$ and $q_{1-\alpha,B}^{b}$ denote the $1-\alpha$
quantiles of
$\\{V_{\bm{\pi}_{0},\mathrm{MMD}}^{1/2},V_{\bm{\pi}_{1},\mathrm{MMD}}^{1/2},\ldots,V_{\bm{\pi}_{B},\mathrm{MMD}}^{1/2}\\}$
and of
$\\{2\Delta_{V^{1/2}}\xi_{\varepsilon,\delta}^{-1}\zeta_{0},\ldots,2\Delta_{V^{1/2}}\xi_{\varepsilon,\delta}^{-1}\zeta_{B}\\}$,
respectively. Similarly, denote by $q_{1-\alpha,\infty}^{a}$ and
$q_{1-\alpha,\infty}^{b}$, the corresponding $1-\alpha$ quantiles with
$B=\infty$. Then for $B\geq 16\alpha^{-2}\log(8/\beta)$, the analysis given in
the proof of Theorem 4 shows that the type II error of the $\mathrm{dpMMD}$
test can be bounded as

$\displaystyle\mathbb{P}\bigl{(}\sqrt{V_{\mathrm{MMD}}}+2\Delta_{V^{1/2}}\xi_{\varepsilon,\delta}^{-1}\zeta_{0}\leq
q_{1-\alpha,B}\bigr{)}~{}\leq~{}$
$\displaystyle\mathbb{P}\bigl{(}\sqrt{V_{\mathrm{MMD}}}+2\Delta_{V^{1/2}}\xi_{\varepsilon,\delta}^{-1}\zeta_{0}\leq
q_{1-\alpha/4,\infty}^{a}+q_{1-\alpha/4,\infty}^{b}\bigr{)}+\beta/2$
$\displaystyle\leq~{}$
$\displaystyle\mathbb{P}\bigl{(}\sqrt{V_{\mathrm{MMD}}}\leq
q_{1-\alpha/4,\infty}^{a}+q_{1-\alpha/4,\infty}^{b}+R_{2}\bigr{)}+5\beta/8,$

where we recall
$R_{2}=2\Delta_{V^{1/2}}\xi_{\varepsilon,\delta}^{-1}F_{\zeta}^{-1}(1-\beta/8)$.
We also note that the quantile $q_{1-\alpha/4,\infty}^{b}$ can be explicitly
written as

$\displaystyle
q_{1-\alpha/4,\infty}^{b}=2\Delta_{V^{1/2}}\xi_{\varepsilon,\delta}^{-1}F_{\zeta}^{-1}(1-\alpha/4),$

and using the inequality (27), the type II error is upper bounded as

$\displaystyle\mathbb{P}\bigl{(}\sqrt{V_{\mathrm{MMD}}}+2\Delta_{V^{1/2}}\xi_{\varepsilon,\delta}^{-1}\zeta_{0}\leq
q_{1-\alpha,B}\bigr{)}$ $\displaystyle\leq~{}$
$\displaystyle\mathbb{P}\bigl{(}\sqrt{V_{\mathrm{MMD}}}\leq
q_{1-\alpha/4,\infty}^{a}+10\Delta_{V^{1/2}}\xi_{\varepsilon,\delta}^{-1}\max\\{\log(1/\alpha),\log(1/\beta)\\}\bigr{)}+5\beta/8.$
(37)

Given this bound for the type II error, our next effort lies in bounding
$q_{1-\alpha/4,\infty}^{a}$.

Bounding $q_{1-\alpha/4,\infty}^{a}$. To obtain an upper bound for
$q_{1-\alpha/4,\infty}^{a}$, we leverage the exponential inequality for
permuted U-statistics studied in Kim et al., 2022a  and Schrab et al., (2023).
To this end, denote the probability function, which is taken over $\bm{\pi}$
conditional on $\mathcal{X}_{m+n}$, as $\mathbb{P}_{\bm{\pi}}$ and note that
for any $t>0$,

$\displaystyle\mathbb{P}_{\bm{\pi}}\Biggl{(}\sqrt{V_{\bm{\pi},\mathrm{MMD}}}\geq\sqrt{\left(\frac{1}{n}+\frac{1}{m}\right)\prod_{i=1}^{d}\frac{1}{\sqrt{2\pi}\lambda_{i}}+t}\Biggr{)}$
$\displaystyle=~{}$
$\displaystyle\mathbb{P}_{\bm{\pi}}\Biggl{(}V_{\bm{\pi},\mathrm{MMD}}\geq\left(\frac{1}{n}+\frac{1}{m}\right)\prod_{i=1}^{d}\frac{1}{\sqrt{2\pi}\lambda_{i}}+t\Biggr{)}$
$\displaystyle=~{}$
$\displaystyle\mathbb{P}_{\bm{\pi}}\Biggl{(}V_{\bm{\pi},\mathrm{MMD}}-U_{\bm{\pi},\mathrm{MMD}}+U_{\bm{\pi},\mathrm{MMD}}\geq\left(\frac{1}{n}+\frac{1}{m}\right)\prod_{i=1}^{d}\frac{1}{\sqrt{2\pi}\lambda_{i}}+t\Biggr{)}$
$\displaystyle=~{}$
$\displaystyle\mathbb{P}_{\bm{\pi}}\Biggl{(}\biggl{\\{}V_{\bm{\pi},\mathrm{MMD}}-U_{\bm{\pi},\mathrm{MMD}}-\left(\frac{1}{n}+\frac{1}{m}\right)\prod_{i=1}^{d}\frac{1}{\sqrt{2\pi}\lambda_{i}}\biggr{\\}}+U_{\bm{\pi},\mathrm{MMD}}\geq
t\Biggr{)}$ $\displaystyle\leq~{}$
$\displaystyle\mathbb{P}_{\bm{\pi}}\bigl{(}U_{\bm{\pi},\mathrm{MMD}}\geq
t\bigr{)},$

where the last equality holds since for any permutation $\bm{\pi}$

$\displaystyle
V_{\bm{\pi},\mathrm{MMD}}-U_{\bm{\pi},\mathrm{MMD}}-\left(\frac{1}{n}+\frac{1}{m}\right)\prod_{i=1}^{d}\frac{1}{\sqrt{2\pi}\lambda_{i}}\leq
0,$

which can be seen from the previous expression of
$V_{\mathrm{MMD}}-U_{\mathrm{MMD}}$ in (36) and non-negativity of
$k_{\bm{\lambda}}$. Hence $q_{1-\alpha/4,\infty}^{a}$ is bounded by

$\displaystyle
q_{1-\alpha/4,\infty}^{a}\leq\sqrt{\left(\frac{1}{n}+\frac{1}{m}\right)\prod_{i=1}^{d}\frac{1}{\sqrt{2\pi}\lambda_{i}}+q_{1-\alpha/4,\infty}^{U}},$

where $q_{1-\alpha/4,\infty}^{U}$ denotes the $1-\alpha/4$ quantile of the
permutation distribution of $U_{\bm{\pi},\mathrm{MMD}}$. Now using the
exponential bound for $U_{\bm{\pi},\mathrm{MMD}}$ in Kim et al., 2022a (,
Equation 59), and following the proof of Schrab et al., (2023, Proposition 4),
we see that there exists a constant $C_{\tau,\beta,M,d}$ such that

$\displaystyle\mathbb{P}\biggl{(}q_{1-\alpha/4,\infty}^{U}\leq
C_{\tau,\beta,M,d}\frac{\log(1/\alpha)}{n\sqrt{\lambda_{1}\cdots\lambda_{d}}}\biggr{)}\geq
1-\beta/8,$

under the conditions of Theorem 9. For simplicity, let us write

$\displaystyle
b_{n,m,\bm{\lambda}}=\left(\frac{1}{n}+\frac{1}{m}\right)\prod_{i=1}^{d}\frac{1}{\sqrt{2\pi}\lambda_{i}}\leq\frac{C_{\tau,d}}{n\lambda_{1}\dots\lambda_{d}}.$
(38)

Observe that we have $\max\\{\log(1/\alpha),\log(1/\beta)\\}\leq
C_{\beta}\log(1/\alpha)$ for $\alpha\in(0,e^{-1})$. Putting these pieces
together and continuing from (37), the type II error is further bounded by

$\displaystyle\mathbb{P}\bigl{(}\sqrt{V_{\mathrm{MMD}}}+2\Delta_{V^{1/2}}\xi_{\varepsilon,\delta}^{-1}\zeta_{0}\leq
q_{1-\alpha,B}\bigr{)}$ $\displaystyle\leq~{}$
$\displaystyle\mathbb{P}\Biggl{(}\sqrt{V_{\mathrm{MMD}}}\leq\sqrt{b_{n,m,\bm{\lambda}}+C_{\tau,\beta,M,d}\frac{\log(1/\alpha)}{n\sqrt{\lambda_{1}\cdots\lambda_{d}}}}+C_{\beta}\Delta_{V^{1/2}}\xi_{\varepsilon,\delta}^{-1}\log(1/\alpha)\Biggr{)}+6\beta/8$
$\displaystyle=~{}$ $\displaystyle\mathbb{P}\Biggl{(}V_{\mathrm{MMD}}\leq
b_{n,m,\bm{\lambda}}+C_{\tau,\beta,M,d}\frac{\log(1/\alpha)}{n\sqrt{\lambda_{1}\cdots\lambda_{d}}}+C_{\beta}^{2}\Delta_{V^{1/2}}^{2}\xi_{\varepsilon,\delta}^{-2}\log^{2}(1/\alpha)$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}+2\sqrt{b_{n,m,\bm{\lambda}}+C_{\tau,\beta,M,d}\frac{\log(1/\alpha)}{n\sqrt{\lambda_{1}\cdots\lambda_{d}}}}C_{\beta}\Delta_{V^{1/2}}\xi_{\varepsilon,\delta}^{-1}\log(1/\alpha)\Biggr{)}+6\beta/8.$
(39)

Connecting $V_{\mathrm{MMD}}$ with $U_{\mathrm{MMD}}$. In order to express the
condition for type II error control in terms of the $L_{2}$ distance, we make
use of the existing results for the U-statistic in Schrab et al., (2023). For
simplicity, we use the notation $C_{1},C_{2},\ldots$ to represent constants
that may depend on $\tau,\beta,s,R,M,d$. The specific values of these
constants may vary in different places. To proceed, let us make an observation
that

$\displaystyle\mathbb{E}\biggl{[}\frac{1}{n^{2}(n-1)}\sum_{(i,j)\in\mathbf{i}_{2}^{n}}k_{\bm{\lambda}}(Y_{i},Y_{j})\biggr{]}~{}=~{}$
$\displaystyle\frac{1}{n}\mathbb{E}\bigl{[}k_{\bm{\lambda}}(Y_{1},Y_{2})\bigr{]}=\frac{1}{n}\int\int
p(y_{1})p(y_{2})k_{\bm{\lambda}}(y_{1},y_{2})dy_{1}dy_{2}$
$\displaystyle\leq~{}$ $\displaystyle\frac{\|p\|_{L_{\infty}}}{n}$

and

$\displaystyle\mathrm{Var}\biggl{[}\frac{1}{n^{2}(n-1)}\sum_{(i,j)\in\mathbf{i}_{2}^{n}}k_{\bm{\lambda}}(Y_{i},Y_{j})\biggr{]}\leq\frac{C_{1}}{n^{3}}\mathbb{E}[k_{\bm{\lambda}}^{2}(Y_{1},Y_{2})]\leq\frac{C_{2}}{n^{3}\lambda_{1}\dots\lambda_{d}}.$
(40)

To explain the last display, note that the U-statistic

$\displaystyle\frac{1}{n(n-1)}\sum_{(i,j)\in\mathbf{i}_{2}^{n}}k_{\bm{\lambda}}(Y_{i},Y_{j})$

achieves the minimum variance among all unbiased estimators of
$k_{\bm{\lambda}}(Y_{1},Y_{2})$, including a linear estimator given as

$\displaystyle\frac{1}{\lfloor n/2\rfloor}\sum_{i=1}^{\lfloor
n/2\rfloor}k_{\bm{\lambda}}(Y_{2i-1},Y_{2i}).$

The variance of the above linear estimator is bounded by
$n^{-1}\mathbb{E}[k_{\bm{\lambda}}^{2}(Y_{1},Y_{2})]$, up to a constant
factor, thereby the inequality (40) holds. A similar calculation shows that

$\displaystyle\mathbb{E}\biggl{[}\frac{1}{m^{2}(m-1)}\sum_{(i,j)\in\mathbf{i}_{2}^{m}}k_{\bm{\lambda}}(Z_{i},Z_{j})\biggr{]}\leq\frac{\|p\|_{L_{\infty}}}{n}\quad\text{and}$
$\displaystyle\mathrm{Var}\biggl{[}\frac{1}{m^{2}(m-1)}\sum_{(i,j)\in\mathbf{i}_{2}^{m}}k_{\bm{\lambda}}(Z_{i},Z_{j})\biggr{]}\leq\frac{C_{3}}{n^{3}\lambda_{1}\dots\lambda_{d}}.$

Based on these results combined with Chebyshev’s inequality, we have the
following statement, which holds with probability at least $1-\beta/8$,

$\displaystyle V_{\mathrm{MMD}}-U_{\mathrm{MMD}}+U_{\mathrm{MMD}}$
$\displaystyle=~{}$ $\displaystyle
b_{n,m,\bm{\lambda}}-\frac{1}{n^{2}(n-1)}\sum_{(i,j)\in\mathbf{i}_{2}^{n}}k_{\bm{\lambda}}(Y_{i},Y_{j})-\frac{1}{m^{2}(m-1)}\sum_{(i,j)\in\mathbf{i}_{2}^{m}}k_{\bm{\lambda}}(Z_{i},Z_{j})+U_{\mathrm{MMD}}$
$\displaystyle\geq~{}$ $\displaystyle
b_{n,m,\bm{\lambda}}-\frac{C_{4}}{n}-\frac{C_{5}}{n^{3/2}\sqrt{\lambda_{1}\dots\lambda_{d}}}+U_{\mathrm{MMD}}.$

Hence, continuing from (39), the type II error is upper bounded by

$\displaystyle\mathbb{P}\Biggl{(}U_{\mathrm{MMD}}\leq\frac{C_{1}}{n}+\frac{C_{2}}{n^{3/2}\sqrt{\lambda_{1}\cdots\lambda_{d}}}+\frac{C_{3}\log(1/\alpha)}{n\sqrt{\lambda_{1}\cdots\lambda_{d}}}+\frac{C_{4}\Delta_{V^{1/2}}^{2}\log^{2}(1/\alpha)}{\xi_{\varepsilon,\delta}^{-2}}$
(41)
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}+2C_{5}\sqrt{b_{n,m,\bm{\lambda}}+\frac{C_{6}\log(1/\alpha)}{n\sqrt{\lambda_{1}\cdots\lambda_{d}}}}\frac{\Delta_{V^{1/2}}\log(1/\alpha)}{\xi_{\varepsilon,\delta}}\Biggr{)}+7\beta/8.$

Recall that we assume $\alpha\in(0,e^{-1})$ and
$\lambda_{1}\cdots\lambda_{d}\leq 1$. Moreover, for the Gaussian kernel, Lemma
5 shows that the sensitivity of $\sqrt{V_{\mathrm{MMD}}}$ satisfies

$\displaystyle\Delta_{V^{1/2}}\leq\frac{C_{6}}{n\sqrt{\lambda_{1}\dots\lambda_{d}}}.$

Using these conditions along with the inequality (38) for
$b_{n,m\bm{\lambda}}$, the previous bound
(LABEL:Eq:_upper_bound_for_type_II_error_2) can be upper bounded as

$\displaystyle\mathbb{P}\Biggl{(}U_{\mathrm{MMD}}\leq\frac{C_{1}\log(1/\alpha)}{n\sqrt{\lambda_{1}\cdots\lambda_{d}}}+\frac{C_{2}\log^{2}(1/\alpha)}{n^{2}\lambda_{1}\cdots\lambda_{d}\xi_{\varepsilon,\delta}^{2}}$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}+\frac{C_{3}\log(1/\alpha)}{n^{3/2}\lambda_{1}\cdots\lambda_{d}\xi_{\varepsilon,\delta}}+\frac{C_{4}\log^{3/2}(1/\alpha)}{n^{3/2}(\lambda_{1}\cdots\lambda_{d})^{3/4}\xi_{\varepsilon,\delta}}\Biggr{)}+7\beta/8.$

Condition in terms of $L_{2}$ distance. As shown in Schrab et al., (2023,
Lemma 2), a sufficient condition for the first probability term in the above
display to be less than $\beta/8$ is

$\displaystyle\mathrm{MMD}_{k_{\bm{\lambda}}}^{2}~{}\geq~{}$ $\displaystyle
C_{5}\sqrt{\mathrm{Var}[U_{\mathrm{MMD}}]}+\frac{C_{1}\log(1/\alpha)}{n\sqrt{\lambda_{1}\cdots\lambda_{d}}}+\frac{C_{2}\log^{2}(1/\alpha)}{n^{2}\lambda_{1}\cdots\lambda_{d}\xi_{\varepsilon,\delta}^{2}}$
$\displaystyle+\frac{C_{3}\log(1/\alpha)}{n^{3/2}\lambda_{1}\cdots\lambda_{d}\xi_{\varepsilon,\delta}}+\frac{C_{4}\log^{3/2}(1/\alpha)}{n^{3/2}(\lambda_{1}\cdots\lambda_{d})^{3/4}\xi_{\varepsilon,\delta}}.$

Moreover, writing the difference of two densities as $\psi=p-q$ and the
convolution of $\psi$ and $k_{\bm{\lambda}}$ as $\psi\ast k_{\bm{\lambda}}$,
the proof of Schrab et al., (2023, Theorem 5) yields that the previous
condition is implied by

$\displaystyle\|\psi\|_{L_{2}}^{2}~{}\geq~{}\|\psi-\psi\ast\varphi_{\lambda}\|_{L_{2}}^{2}+C_{6}$
$\displaystyle\Biggl{\\{}\frac{\log(1/\alpha)}{n\sqrt{\lambda_{1}\cdots\lambda_{d}}}+\frac{\log^{2}(1/\alpha)}{n^{2}\lambda_{1}\cdots\lambda_{d}\xi_{\varepsilon,\delta}^{2}}$
$\displaystyle+\frac{\log(1/\alpha)}{n^{3/2}\lambda_{1}\cdots\lambda_{d}\xi_{\varepsilon,\delta}}+\frac{\log^{3/2}(1/\alpha)}{n^{3/2}(\lambda_{1}\cdots\lambda_{d})^{3/4}\xi_{\varepsilon,\delta}}\Biggr{\\}}.$

Lastly, the proof of Schrab et al., (2023, Theorem 6) yields that over the
Sobolev ball, a sufficient condition for the previous inequality is

$\displaystyle\|\psi\|_{L_{2}}^{2}~{}\geq~{}C_{7}\Biggl{\\{}\sum_{i=1}^{d}\lambda_{i}^{2s}$
$\displaystyle+\frac{\log(1/\alpha)}{n\sqrt{\lambda_{1}\cdots\lambda_{d}}}+\frac{\log^{2}(1/\alpha)}{n^{2}\lambda_{1}\cdots\lambda_{d}\xi_{\varepsilon,\delta}^{2}}$
$\displaystyle+\frac{\log(1/\alpha)}{n^{3/2}\lambda_{1}\cdots\lambda_{d}\xi_{\varepsilon,\delta}}+\frac{\log^{3/2}(1/\alpha)}{n^{3/2}(\lambda_{1}\cdots\lambda_{d})^{3/4}\xi_{\varepsilon,\delta}}\Biggr{\\}}$

as claimed.

###  E.12 Proof of Lemma 7

Let $U_{\mathrm{MMD}}^{\prime}$ be the U-statistic similarly defined as
$U_{\mathrm{MMD}}$ by replacing $Y_{1}$ with $Y_{1}^{\prime}$. Then it can be
seen that

$\displaystyle|U_{\mathrm{MMD}}-U_{\mathrm{MMD}}^{\prime}|~{}=~{}$
$\displaystyle\bigg{|}\frac{2}{n(n-1)}\sum_{i=2}^{n}\big{\\{}k(Y_{1},Y_{j})-k(Y_{1}^{\prime},Y_{j})\big{\\}}-\frac{2}{nm}\sum_{j=1}^{m}\big{\\{}k(Y_{1},Z_{j})-k(Y_{1}^{\prime},Z_{j})\big{\\}}\bigg{|}$
$\displaystyle\leq~{}$ $\displaystyle\frac{8K}{n}.$

Similarly, the difference is bounded by $8K/n$ for other neighboring datasets,
and thus the global sensitivity of $U_{\mathrm{MMD}}$ is bounded by $8K/n$.
Let $\epsilon$ be a number between $(0,K)$. For a translation invariant kernel
with non-empty level sets, we can ensure the existence of an instance where
$Y_{1}=\ldots=Y_{n}$ and $Z_{1}=\ldots=Z_{m}$ such that
$k(Y_{1},Z_{1})=\epsilon_{\star}$ for some $\epsilon_{\star}\in[0,\epsilon]$.
Moreover, by taking $Y_{1}^{\prime}=Z_{1}$, we have
$k(Y_{1},Y_{1}^{\prime})=\epsilon_{\star}$ and $k(Y_{1}^{\prime},Z_{1})=K$.
Under this setting, the difference between $U_{\mathrm{MMD}}$ and
$U_{\mathrm{MMD}}^{\prime}$ becomes

$\displaystyle|U_{\mathrm{MMD}}-U_{\mathrm{MMD}}^{\prime}|=\frac{4(K-\epsilon_{\star})}{n}.$

Since $\epsilon$ (and so $\epsilon_{\star}$) can be arbitrarily small, we see
that the global sensitivity defined with the supremum is lower bounded by
$4K/n$. This concludes the claim of Lemma 7. This concludes the claim of Lemma
7.

###  E.13 Proof of Theorem 10

For notational convenience, let us write
$U_{\mathrm{MMD}}(\mathcal{X}_{n+m}^{\bm{\pi}_{0}})=U_{\mathrm{MMD}}$ and
$U_{\mathrm{MMD}}(\mathcal{X}_{n+m}^{\bm{\pi}_{i}})=U_{\bm{\pi}_{i},\mathrm{MMD}}$
for $i\in[B]$. For $\alpha>1/(B+1)$, Lemma 18 yields that

$\displaystyle\phi_{\mathrm{dpMMD}}^{u}=\mathds{1}\biggl{(}U_{\mathrm{MMD}}+\frac{2c_{m,n}K}{n\xi_{\varepsilon,\delta}}\zeta_{0}>r_{1-\alpha_{\star}}\biggr{)},$

where $\alpha_{\star}=\frac{B+1}{B}\alpha-\frac{1}{B}$ and
$r_{1-\alpha_{\star}}$ is the $1-\alpha_{\star}$ quantile of
$\\{U_{\bm{\pi}_{i},\mathrm{MMD}}+\frac{2c_{m,n}K}{n\xi_{\varepsilon,\delta}}\zeta_{i}\\}_{i=1}^{B}$.
Let us denote the V-statistic of MMD as

$\displaystyle
V_{\mathrm{MMD}}=\frac{1}{n^{2}}\sum_{i,j=1}^{n}k(Y_{i},Y_{j})+\frac{1}{m^{2}}\sum_{i,j=1}^{m}k(Z_{i},Z_{j})-\frac{2}{nm}\sum_{i=1}^{n}\sum_{j=1}^{m}k(Y_{i},Z_{j}),$

which is greater than or equal to $U_{\mathrm{MMD}}$ since

$\displaystyle\frac{1}{n^{2}}\sum_{i,j=1}^{n}k(Y_{i},Y_{j})\geq\frac{1}{n(n-1)}\sum_{(i,j)\in\mathbf{i}_{2}^{n}}k(Y_{i},Y_{j})$
$\displaystyle\Longleftrightarrow~{}$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}k(Y_{i},Y_{i})=K\geq\frac{1}{n(n-1)}\sum_{(i,j)\in\mathbf{i}_{2}^{n}}k(Y_{i},Y_{j})$

and similarly

$\displaystyle\frac{1}{m^{2}}\sum_{i,j=1}^{m}k(Z_{i},Z_{j})\geq\frac{1}{m(m-1)}\sum_{(i,j)\in\mathbf{i}_{2}^{m}}k(Z_{i},Z_{j})$
$\displaystyle\Longleftrightarrow~{}$
$\displaystyle\frac{1}{m}\sum_{i=1}^{m}k(Z_{i},Z_{i})=K\geq\frac{1}{m(m-1)}\sum_{(i,j)\in\mathbf{i}_{2}^{m}}k(Z_{i},Z_{j}).$

Moreover, since $V_{\mathrm{MMD}}\geq 0$, the U-statistic is lower bounded by
$U_{\mathrm{MMD}}\geq U_{\mathrm{MMD}}-V_{\mathrm{MMD}}$. Consider a lower
bound for $U_{\mathrm{MMD}}-V_{\mathrm{MMD}}$ as

$\displaystyle U_{\mathrm{MMD}}-V_{\mathrm{MMD}}~{}=~{}$
$\displaystyle\frac{1}{n(n-1)}\sum_{(i,j)\in\mathbf{i}_{2}^{n}}k(Y_{i},Y_{j})-\frac{1}{n^{2}}\sum_{i,j=1}^{n}k(Y_{i},Y_{j})$
$\displaystyle+~{}$
$\displaystyle\frac{1}{m(m-1)}\sum_{(i,j)\in\mathbf{i}_{2}^{m}}k(Z_{i},Z_{j})-\frac{1}{m^{2}}\sum_{i,j=1}^{m}k(Z_{i},Z_{j})$
$\displaystyle=~{}$
$\displaystyle\frac{1}{n}\biggl{[}\frac{1}{n(n-1)}\sum_{(i,j)\in\mathbf{i}_{2}^{n}}k(Y_{i},Y_{j})-\frac{1}{n}\sum_{i=1}^{n}k(Y_{i},Y_{i})\biggr{]}$
$\displaystyle+~{}$
$\displaystyle\frac{1}{m}\biggl{[}\frac{1}{m(m-1)}\sum_{(i,j)\in\mathbf{i}_{2}^{m}}k(Z_{i},Z_{j})-\frac{1}{m}\sum_{i=1}^{m}k(Z_{i},Z_{i})\biggr{]}$
$\displaystyle\geq~{}$ $\displaystyle-\frac{K}{n}-\frac{K}{m}.$

Thereby, $U_{\mathrm{MMD}}\geq-\frac{K}{n}-\frac{K}{m}$. We use this
observation to lower bound the critical value $r_{1-\alpha_{\star}}$ as

$\displaystyle
r_{1-\alpha_{\star}}\geq\frac{2c_{m,n}K}{n\xi_{\varepsilon,\delta}}\mathrm{Quantile}_{1-\alpha_{\star}}\big{\\{}\zeta_{1},\ldots,\zeta_{B}\big{\\}}-\frac{K}{n}-\frac{K}{m},$

where $\mathrm{Quantile}_{1-\alpha_{\star}}\\{\zeta_{1},\ldots,\zeta_{B}\\}$
denotes the $1-\alpha_{\star}$ quantile of $\zeta_{1},\ldots,\zeta_{B}$.
Putting pieces together yields

$\displaystyle\phi_{\mathrm{dpMMD}}^{u}$ $\displaystyle\leq~{}$
$\displaystyle\mathds{1}\biggl{(}V_{\mathrm{MMD}}+\frac{2c_{m,n}K}{n\xi_{\varepsilon,\delta}}\zeta_{0}>\frac{2c_{m,n}K}{n\xi_{\varepsilon,\delta}}\mathrm{Quantile}_{1-\alpha_{\star}}\big{\\{}\zeta_{1},\ldots,\zeta_{B}\big{\\}}-\frac{K}{n}-\frac{K}{m}\biggr{)}$
$\displaystyle\leq~{}$
$\displaystyle\mathds{1}\biggl{(}\frac{n\xi_{\varepsilon,\delta}}{2c_{m,n}K}V_{\mathrm{MMD}}+\zeta_{0}>\mathrm{Quantile}_{1-\alpha_{\star}}\big{\\{}\zeta_{1},\ldots,\zeta_{B}\big{\\}}-\frac{\xi_{\varepsilon,\delta}}{c_{m,n}}\biggr{)}.$

Further note that the statistic $V_{\mathrm{MMD}}$ is the square of the
empirical MMD, which satisfies

$\displaystyle
V_{\mathrm{MMD}}=\big{\\{}\mathrm{MMD}_{k}(P,Q)+R_{m,n}\\}^{2},$

where $R_{m,n}=O_{P}(n^{-1/2})$ due to Gretton et al., (2012, Theorem 7),
recalled in Lemma 13.

Let us consider $P_{0},Q_{0}\in\mathcal{P}_{\mathbb{S}}$ such that
$\mathrm{MMD}_{k}(P_{0},Q_{0})=\varrho_{0}$ in the theorem statement. Let
$P=P_{0}$, and let $Q$ be a mixture distribution $Q=wP_{0}+(1-w)Q_{0}$. Since
$\mathcal{P}_{\mathbb{S}}$ is a convex set, $Q$ belongs to
$\mathcal{P}_{\mathbb{S}}$, and it can be seen that

$\displaystyle\mathrm{MMD}_{k}(P,Q)=(1-w)\varrho_{0}.$

Now for $\gamma\in(1/2,1)$, we set
$w=1-(n\xi_{\varepsilon,\delta})^{-\gamma}$. Since
$\xi_{\varepsilon,\delta}\asymp n^{-1/2-r}$ with $r\in(0,1/2)$, we can ensure
that $w\in(0,1)$ and
$\mathrm{MMD}_{k}(P,Q)=(n\xi_{\varepsilon,\delta})^{-\gamma}\varrho_{0}$ for
sufficiently large $n$. Moreover, this pair of distributions $(P,Q)$ belongs
to $\mathcal{P}_{\mathrm{MMD}_{k}}\\!(\rho)$ for $\rho$ as in (17) since

$\displaystyle\mathrm{MMD}_{k}(P,Q)=\frac{\varrho_{0}}{\big{(}n\xi_{\varepsilon,\delta}\big{)}^{\gamma}}~{}\geq~{}\rho~{}\asymp~{}\frac{\log(n)}{n\xi_{\varepsilon,\delta}}\quad$
$\displaystyle\Longleftrightarrow\quad\big{(}n\xi_{\varepsilon,\delta}\big{)}^{1-\gamma}~{}\gtrsim~{}\log(n)$
$\displaystyle\Longleftrightarrow\quad
n^{\frac{(1-2r)(1-\gamma)}{2}}~{}\gtrsim~{}\log(n).$

Moreover, as $n\xi_{\varepsilon,\delta}\rightarrow\infty$ and
$\xi_{\varepsilon,\delta}\rightarrow 0$,

$\displaystyle\frac{n\xi_{\varepsilon,\delta}}{2c_{m,n}K}V_{\mathrm{MMD}}=\frac{1}{2c_{m,n}K}\big{\\{}\sqrt{n\xi_{\varepsilon,\delta}}\mathrm{MMD}_{k}(P,Q)+\sqrt{n\xi_{\varepsilon,\delta}}R_{m,n}\\}^{2}=o_{P}(1),$

where we use the fact that $c_{m,n}\in[4,8]$. Having this observation in
place, for any fixed $t>0$, we can take $N_{t}>0$ such that for all $n\geq
N_{t}$, it holds that

$\displaystyle\mathbb{E}[\phi_{\mathrm{dpMMD}}^{u}]~{}\leq~{}$
$\displaystyle\mathbb{P}\Bigl{(}\zeta_{0}>\mathrm{Quantile}_{1-\alpha_{\star}}\big{\\{}\zeta_{1},\ldots,\zeta_{B}\big{\\}}-\frac{\xi_{\varepsilon,\delta}}{c_{m,n}}-\frac{n\xi_{\varepsilon,\delta}}{2c_{m,n}K}V_{\mathrm{MMD}},$
$\displaystyle\hskip
50.00008pt\Big{|}\frac{\xi_{\varepsilon,\delta}}{c_{m,n}}+\frac{n\xi_{\varepsilon,\delta}}{2c_{m,n}K}V_{\mathrm{MMD}}\Big{|}<t\Bigr{)}+\mathbb{P}\Bigl{(}\Big{|}\frac{\xi_{\varepsilon,\delta}}{c_{m,n}}+\frac{n\xi_{\varepsilon,\delta}}{2c_{m,n}K}V_{\mathrm{MMD}}\Big{|}\geq
t\Bigr{)}$ $\displaystyle\leq~{}$
$\displaystyle\mathbb{P}\Bigl{(}\zeta_{0}>\mathrm{Quantile}_{1-\alpha_{\star}}\big{\\{}\zeta_{1},\ldots,\zeta_{B}\big{\\}}-t\Bigr{)}+t$
$\displaystyle=~{}$
$\displaystyle\mathbb{E}\Bigl{[}\mathbb{P}\Bigl{(}\zeta_{0}>\mathrm{Quantile}_{1-\alpha_{\star}}\big{\\{}\zeta_{1},\ldots,\zeta_{B}\big{\\}}-t\,\Big{|}\,\zeta_{1},\ldots,\zeta_{B}\Bigr{)}\Bigr{]}+t$
$\displaystyle\leq~{}$
$\displaystyle\mathbb{P}\Bigl{(}\zeta_{0}>\mathrm{Quantile}_{1-\alpha_{\star}}\big{\\{}\zeta_{1},\ldots,\zeta_{B}\big{\\}}\Bigr{)}+t\|f_{\zeta}\|_{L_{\infty}}+t,$

where $f_{\zeta}$ denotes the density function of $\mathsf{Laplace}(0,1)$ and
the last inequality uses the fact that

$\displaystyle\big{|}\mathbb{P}(\zeta>a+b)-\mathbb{P}(\zeta>b)\big{|}\leq\|f_{\zeta}\|_{L_{\infty}}|a|\quad\text{for
all $a,b\in\mathbb{R}$.}$

Since $\|f_{\zeta}\|_{L_{\infty}}\leq\frac{1}{2}$ and

$\displaystyle\mathbb{P}\Bigl{(}\zeta_{0}>\mathrm{Quantile}_{1-\alpha_{\star}}\big{\\{}\zeta_{1},\ldots,\zeta_{B}\big{\\}}\Bigr{)}=\mathbb{P}\Bigl{(}\zeta_{0}>\mathrm{Quantile}_{1-\alpha}\big{\\{}\zeta_{0},\zeta_{1},\ldots,\zeta_{B}\big{\\}}\Bigr{)}\leq\alpha,$

we have

$\displaystyle\limsup_{n\rightarrow\infty}\inf_{(P,Q)\in\mathcal{P}_{\mathrm{MMD}_{k}}\\!(\rho)}\mathbb{E}_{P,Q}[\phi_{\mathrm{dpMMD}}^{u}]\leq\alpha+\frac{3t}{2}.$

The result follows as $t$ can be made arbitrarily small.

###  E.14 Proof of Theorem 11

Let us denote by $C_{1},C_{2},\ldots$ constants that may depend on
$\tau,\beta,s,R,M,d$. Following the proofs of Theorem 4 and Theorem 9 along
with the sensitivity result for $U_{\mathrm{MMD}}$ in Lemma 7, we may arrive
at the point where the type II error of $\phi_{\mathrm{dpMMD}}^{u}$ is upper
bounded as

$\displaystyle\mathbb{E}[1-\phi_{\mathrm{dpMMD}}^{u}]\leq\mathbb{P}\biggl{(}U_{\mathrm{MMD}}\leq\frac{C_{1}\log(1/\alpha)}{n\sqrt{\lambda_{1}\cdots\lambda_{d}}}+\frac{C_{2}\log(1/\alpha)}{n\lambda_{1}\cdots\lambda_{d}\xi_{\varepsilon,\delta}}\biggr{)}+7\beta/8.$

We then use the proofs of Schrab et al., (2023, Theorem 5) and Schrab et al.,
(2023, Theorem 6), and show that the probability term in the above display is
less than or equal to $\beta/8$ once

$\displaystyle\|p-q\|_{L_{2}}^{2}~{}\geq~{}C_{3}\Biggl{\\{}\sum_{i=1}^{d}\lambda_{i}^{2s}$
$\displaystyle+\frac{\log(1/\alpha)}{n\sqrt{\lambda_{1}\cdots\lambda_{d}}}+\frac{\log(1/\alpha)}{n\lambda_{1}\cdots\lambda_{d}\xi_{\varepsilon,\delta}}\Biggr{\\}}.$

This proves Theorem 11.

##  Appendix F Proofs for Appendix B

This section collects the proofs of the results in Appendix B.

###  F.1 Proof of Proposition 1

Focusing on MMD, the square of the empirical MMD satisfies

$\displaystyle(n+m)\widehat{\mathrm{MMD}}^{2}(\mathcal{X}_{n+m})\overset{d}{\longrightarrow}\sum_{i=1}^{\infty}\lambda_{i}Z_{i}^{2},$

which can be seen by the standard asymptotic theory of V-statistics. See
Fernández and Rivera, (2022, Proposition 9). Moreover, note that the empirical
MMD and the Laplace noise are independent. Therefore, the continuous mapping
theorem along with Slutsky’s theorem proves the result when
$\sqrt{n+m}\sigma\rightarrow\eta\in[0,\infty)$. On the other hand, when
$\sqrt{n+m}\sigma\rightarrow\infty$, it holds that

$\displaystyle\sigma^{-1}M_{\mathrm{MMD}}=\underbrace{\frac{1}{\sqrt{n+m}\,\sigma}}_{=\,o_{P}(1)}\times\underbrace{\sqrt{n+m}\,\widehat{\mathrm{MMD}}(\mathcal{X}_{n+m})}_{=\,O_{P}(1)}+\,\zeta=o_{P}(1)+\zeta.$

This proves the results for MMD. The proof for HSIC is completely analogous
and thereby omitted, which can be derived by using Zhang et al., (2018,
Theorem 1) in place of Fernández and Rivera, (2022, Proposition 9).

###  F.2 Proof of Lemma 8

We first prove the claim by considering two scenarios: (i) $B_{n}$ is fixed in
$n$ and (ii) $B_{n}$ increases with $n$, and prove the consistency result. We
then turn to a general case of $B_{n}$ and complete the proof building on the
prior result. Throughout this proof, we often omit the dependence of $n$ on
$B_{n}$ and write it as $B$ for simplicity.

####  F.2.1 Simple cases

##### Fixed $B$.

Assume that $B$ is fixed and $B+1>\alpha^{-1}$ or equivalently
$\alpha(B+1)\geq 1$. As mentioned in the main text, we simply exploit the
union bound to prove the claim for fixed $B$. Concretely,

$\displaystyle\mathbb{P}\biggl{[}\frac{1}{B+1}\biggl{(}\sum_{i=1}^{B}\mathds{1}(W_{0,n}\leq
W_{i,n})+1\biggr{)}\leq\alpha\biggr{]}~{}=~{}$
$\displaystyle\mathbb{P}\biggl{[}\sum_{i=1}^{B}\mathds{1}(W_{0,n}\leq
W_{i,n})\leq\alpha(B+1)-1\biggr{]}$
$\displaystyle\overset{\mathrm{(i)}}{\geq}~{}$
$\displaystyle\mathbb{P}\biggl{[}\sum_{i=1}^{B}\mathds{1}(W_{0,n}\leq
W_{i,n})\leq 0\biggr{]}$ $\displaystyle=~{}$
$\displaystyle\mathbb{P}\Bigl{[}W_{0,n}-\max_{i\in[B]}W_{i,n}>0\Bigr{]}$
$\displaystyle\overset{\mathrm{(ii)}}{\geq}~{}$ $\displaystyle
1-\sum_{i=1}^{B}\mathbb{P}(W_{0,n}\leq W_{i,n}),$

where step (i) uses condition $\alpha(B+1)>1$ and step (ii) uses de Morgan’s
law and the union bound. By the condition that
$\lim_{n\rightarrow\infty}\mathbb{P}(W_{0,n}\leq W_{1,n})=0$ and since
$\\{W_{0,n}-W_{i,n}\\}_{i=2}^{B}$ are identically distributed as
$W_{0,n}-W_{1,n}$, the lower bound converges to one for fixed $B$ and thus the
consistency result follows.

##### Increasing $B$.

Next we consider the case where $B$ increases to infinity with $n$. For some
$\eta>0$ (specified later), define an event $\mathcal{A}$ as

$\displaystyle\mathcal{A}=\bigg{\\{}\bigg{|}\frac{1}{B}\sum_{i=1}^{B}\mathds{1}(W_{0,n}\leq
W_{i,n})-\mathbb{P}(W_{0,n}\leq
W_{1,n}\,|\,\mathcal{G})\bigg{|}\leq\sqrt{\frac{1}{2B}\log\left(\frac{2}{\eta}\right)}\bigg{\\}}.$

Since $\mathds{1}(W_{0,n}\leq W_{1,n}),\ldots,\mathds{1}(W_{0}\leq W_{B,n})$
are i.i.d. random variables conditional on the sigma field $\mathcal{G}$ under
the condition of Lemma 8, Hoeffding’s inequality yields that

$\displaystyle\mathbb{P}(\mathcal{A}^{c}\,|\,\mathcal{G})\leq\eta.$

By taking the expectation over $\mathcal{G}$ on both sides, it also holds
marginally that $\mathbb{P}(\mathcal{A}^{c})\leq\eta$. Now

$\displaystyle\mathbb{P}\biggl{[}\frac{1}{B+1}\biggl{(}\sum_{i=1}^{B}\mathds{1}(W_{0,n}\leq
W_{i,n})+1\biggr{)}>\alpha\biggr{]}$ (42) $\displaystyle={}$
$\displaystyle\mathbb{P}\biggl{[}\frac{1}{B}\sum_{i=1}^{B}\mathds{1}(W_{0,n}\leq
W_{i,n})>\frac{B+1}{B}\biggl{(}\alpha-\frac{1}{B+1}\biggr{)}\biggr{]}$
$\displaystyle\leq{}$
$\displaystyle\mathbb{P}\biggl{[}\frac{1}{B}\sum_{i=1}^{B}\mathds{1}(W_{0,n}\leq
W_{i,n})>\frac{B+1}{B}\biggl{(}\alpha-\frac{1}{B+1}\biggr{)},\,\mathcal{A}\biggr{]}+\mathbb{P}(\mathcal{A}^{c})$
$\displaystyle\leq{}$ $\displaystyle\mathbb{P}\biggl{[}\mathbb{P}(W_{0,n}\leq
W_{1,n}\,|\,\mathcal{G})+\sqrt{\frac{1}{2B}\log\left(\frac{2}{\eta}\right)}>\frac{B+1}{B}\biggl{(}\alpha-\frac{1}{B+1}\biggr{)}\biggr{]}+\eta.$

By taking $\eta=B^{-1}$, we know $\eta\rightarrow 0$ (since
$B\rightarrow\infty$) and

$\displaystyle\frac{B+1}{B}\biggl{(}\alpha-\frac{1}{B+1}\biggr{)}-\sqrt{\frac{1}{2B}\log\left(\frac{2}{\eta}\right)}\rightarrow\alpha\quad\text{as
$n\rightarrow\infty$.}$

Moreover our condition guarantees that
$\lim_{n\rightarrow\infty}\mathbb{P}(W_{0,n}\leq W_{1,n})=0$. Hence for any
$\epsilon>0$, we can take $N$ such that statement (i) $\eta<\epsilon/2$ and
statement (ii)

$\displaystyle\mathbb{P}\biggl{[}\mathbb{P}(W_{0,n}\leq
W_{1,n}\,|\,\mathcal{G})+\sqrt{\frac{1}{2B}\log\left(\frac{2}{\eta}\right)}>\frac{B+1}{B}\biggl{(}\alpha-\frac{1}{B+1}\biggr{)}\bigg{]}$
(43) $\displaystyle\leq{}$
$\displaystyle\mathbb{P}\biggl{[}\mathbb{P}(W_{0,n}\leq
W_{1,n}\,|\,\mathcal{G})>\frac{\alpha}{2}\biggr{]}$
$\displaystyle\overset{(\dagger)}{\leq}{}$
$\displaystyle\frac{2}{\alpha}\mathbb{P}(W_{0,n}\leq
W_{1,n})\leq\frac{\epsilon}{2},$

hold for all $n\geq N$. Here step ($\dagger$) holds by Markov’s inequality.
Thus for all $n\geq N$ we have

$\displaystyle\mathbb{P}\biggl{[}\frac{1}{B_{n}+1}\biggl{(}\sum_{i=1}^{B_{n}}\mathds{1}(W_{0,n}\leq
W_{i,n})+1\biggr{)}>\alpha\biggr{]}<\epsilon.$

Since $\epsilon$ is arbitrary, the above argument proves the claim that

$\displaystyle\lim_{n\rightarrow\infty}\mathbb{P}\biggl{[}\frac{1}{B_{n}+1}\biggl{(}\sum_{i=1}^{B_{n}}\mathds{1}(W_{0,n}\leq
W_{i,n})+1\biggr{)}\leq\alpha\biggr{]}=1.$

####  F.2.2 Main proof

We now deal with an arbitrary sequence of $B_{n}$ such that $\inf_{n\geq
1}B_{n}+1>\alpha^{-1}$ and prove the claim. First note that

$\displaystyle\mathbb{P}\biggl{[}\frac{1}{B+1}\biggl{(}\sum_{i=1}^{B}\mathds{1}(W_{0,n}\leq
W_{i,n})+1\biggr{)}>\alpha\biggr{]}=\mathbb{P}\biggl{[}\frac{1}{B+1}\sum_{i=1}^{B}\mathds{1}(W_{0,n}\leq
W_{i,n})>\biggl{(}\alpha-\frac{1}{B+1}\biggr{)}\biggr{]}$
$\displaystyle\overset{(\mathrm{i})}{\leq}~{}$
$\displaystyle\mathbb{P}\biggl{[}\sum_{i=1}^{B}\mathds{1}(W_{0,n}\leq
W_{i,n})>0\biggr{]}=1-\mathbb{P}\biggl{[}\sum_{i=1}^{B}\mathds{1}(W_{0,n}\leq
W_{i,n})=0\biggr{]}$ $\displaystyle=~{}$ $\displaystyle
1-\mathbb{E}\biggl{\\{}\mathbb{P}\biggl{[}\sum_{i=1}^{B}\mathds{1}(W_{0,n}\leq
W_{i,n})=0\,\bigg{|}\,\mathcal{G}\biggr{]}\biggr{\\}}=1-\mathbb{E}\Bigl{[}\\{\mathbb{P}(W_{0,n}>W_{1,n}\,|\,\mathcal{G})\\}^{B}\Bigr{]}$
$\displaystyle\overset{(\mathrm{ii})}{\leq}~{}$ $\displaystyle
1-\\{\mathbb{P}(W_{0,n}>W_{1,n})\\}^{B},$

where step (i) uses the condition $\alpha>\frac{1}{B+1}$ and step (ii) uses
Jensen’s inequality. On the other hand, from the previous results
(LABEL:Eq:_step_1_for_increasing_B) and Markov’s inequality with
$\eta=B^{-1}$, we have

$\displaystyle\mathbb{P}\biggl{[}\frac{1}{B+1}\biggl{(}\sum_{i=1}^{B}\mathds{1}(W_{0,n}\leq
W_{i,n})+1\biggr{)}>\alpha\biggr{]}\leq\frac{1}{B}+\frac{\mathbb{P}(W_{0,n}\leq
W_{1,n})+\sqrt{\frac{1}{2B}\log(2B)}}{\frac{B+1}{B}(\alpha-\frac{1}{B+1})}.$

Thus combining the two bounds yields

$\displaystyle\mathbb{P}\biggl{[}\frac{1}{B+1}\biggl{(}\sum_{i=1}^{B}\mathds{1}(W_{0,n}\leq
W_{i,n})+1\biggr{)}>\alpha\biggr{]}$ $\displaystyle\leq~{}$
$\displaystyle\min\Bigg{\\{}1-\\{\mathbb{P}(W_{0,n}>W_{1,n})\\}^{B},\,\frac{1}{B}+\frac{\mathbb{P}(W_{0,n}\leq
W_{1,n})+\sqrt{\frac{1}{2B}\log(2B)}}{\frac{B+1}{B}(\alpha-\frac{1}{B+1})}\Bigg{\\}}.$

Interestingly, a careful argument shows that the above upper bound can be made
independent of $B$. Concretely, write
$p_{n}\coloneqq\mathbb{P}(W_{0,n}>W_{1,n})$ for simplicity, which by
assumption tends to $1$ as $n$ tends to infinity, and let $b_{n}$ be a
positive sequence that goes to infinity and satisfies
$p_{n}^{b_{n}}\rightarrow 1$. For instance, one can take
$b_{n}=\sqrt{-\log(1-p_{n})}$. Using this notation in place, observe

$\displaystyle\min\Bigg{\\{}1-\\{\mathbb{P}(W_{0,n}>W_{1,n})\\}^{B},\,\frac{1}{B}+\frac{\mathbb{P}(W_{0,n}\leq
W_{1,n})+\sqrt{\frac{1}{2B}\log(2B)}}{\frac{B+1}{B}(\alpha-\frac{1}{B+1})}\Bigg{\\}}$
$\displaystyle\leq~{}$
$\displaystyle\mathds{1}(B<b_{n})\big{\\{}1-p_{n}^{B}\big{\\}}+\mathds{1}(B\geq
b_{n})\Bigg{\\{}\frac{1}{B}+\frac{1-p_{n}+\sqrt{\frac{1}{2B}\log(2B)}}{\frac{B+1}{B}(\alpha-\frac{1}{B+1})}\Bigg{\\}}$
$\displaystyle\leq~{}$ $\displaystyle
1-p_{n}^{b_{n}}+\Bigg{\\{}\frac{1}{b_{n}}+\frac{1-p_{n}+\sqrt{\frac{1}{2b_{n}}\log(2b_{n})}}{\frac{b_{n}+1}{b_{n}}(\alpha-\frac{1}{b_{n}+1})}\Bigg{\\}}.$

Now the upper bound does not depend on $B$ and converges to zero, which is
ensured by the condition $\lim_{n\rightarrow\infty}p_{n}=1$. As a result, we
have

$\displaystyle\lim_{n\rightarrow\infty}\mathbb{P}\biggl{[}\frac{1}{B_{n}+1}\biggl{(}\sum_{i=1}^{B_{n}}\mathds{1}(W_{0,n}\leq
W_{i,n})+1\biggr{)}\leq\alpha\biggr{]}=1,$

and complete the proof of Lemma 8.

###  F.3 Proof of Theorem 12

The proof of Theorem 12 can follow a similar approach to that of Theorem 7 by
replacing concentration inequalities for MMD statistics (Lemma 10 and Lemma
13) with the corresponding ones for HSIC statistics (Lemma 12 and Lemma 14).
Throughout this proof, we denote positive constants that only depend on $K$
and $L$ by $C_{1},C_{2},C_{3},\ldots$

Step 1 (Bounding the quantile). Let us remind that $M_{i}$ is defined as
$\widehat{\mathrm{HSIC}}(\mathcal{X}_{n}^{\bm{\pi}_{i}})+2\Delta_{T}\xi_{\varepsilon,\delta}^{-1}\zeta_{i}$
for $i\in\\{0\\}\cup[B]$. We first examine the $1-\alpha$ quantile of
$M_{0},M_{1},\ldots,M_{B}$ denoted as $q_{1-\alpha,B}$ and establish an upper
bound for $q_{1-\alpha,B}$ with high probability. Again, the proof strategy is
similar to that of Theorem 7. With an abuse of notation, let
$q_{1-\alpha/2,B}^{a}$ and $q_{1-\alpha/2,B}^{b}$ be the $1-\alpha/2$
quantiles of
$\\{\widehat{\mathrm{HSIC}}(\mathcal{X}_{n}^{\bm{\pi}_{0}}),\ldots,\widehat{\mathrm{HSIC}}(\mathcal{X}_{n}^{\bm{\pi}_{B}})\\}$
and of
$\\{2\Delta_{T}\xi_{\varepsilon,\delta}^{-1}\zeta_{0},\ldots,2\Delta_{T}\xi_{\varepsilon,\delta}^{-1}\zeta_{B}\\}$,
respectively. Denote by $q_{1-\alpha/2,\infty}^{a}$ and
$q_{1-\alpha/2,\infty}^{b}$ the corresponding $1-\alpha/2$ quantiles with
$B=\infty$. Following the same lines of the proof of Theorem 7, we see that
$q_{1-\alpha,B}\leq q_{1-\alpha/4,\infty}^{a}+q_{1-\alpha/4,\infty}^{b}$ with
probability at least $1-\beta/2$ under our condition for $B$ given as $B\geq
16\alpha^{-2}\log\bigl{(}8/\beta\bigr{)}$. Moreover applying Lemma 12 yields

$\displaystyle q_{1-\alpha/4,\infty}^{a}\leq
C_{1}\sqrt{\frac{1}{n}\max\bigg{\\{}\log\biggl{(}\frac{4}{\alpha}\biggr{)},\,\log^{1/2}\biggl{(}\frac{4}{\alpha}\biggr{)},\,1\bigg{\\}}},$

whereas
$q_{1-\alpha/4,\infty}^{b}=2\Delta_{T}\xi_{\varepsilon,\delta}^{-1}F_{\zeta}^{-1}(1-\alpha/4)$.
Therefore, with probability at least $1-\beta/2$, it holds that

$\displaystyle q_{1-\alpha,B}\leq
C_{1}\sqrt{\frac{1}{n}\max\bigg{\\{}\log\biggl{(}\frac{4}{\alpha}\biggr{)},\,\log^{1/2}\biggl{(}\frac{4}{\alpha}\biggr{)},\,1\bigg{\\}}}+2\Delta_{T}\xi_{\varepsilon,\delta}^{-1}F_{\zeta}^{-1}(1-\alpha/4).$
(44)

Step 2 (Bounding the type II error). For the empirical HSIC, Lemma 14 shows
that the following event

$\displaystyle
E_{1}^{\prime}\coloneqq\biggl{\\{}\bigg{|}\mathrm{HSIC}_{k\otimes\ell}(P_{YZ})-\widehat{\mathrm{HSIC}}(\mathcal{X}_{n})\bigg{|}\leq
C_{2}\sqrt{\frac{\log(8/\beta)}{n}}\biggr{\\}}$

holds with probability at least $1-\beta/4$. On the other hand, the condition
$\zeta_{0}\sim\mathsf{Laplace}(0,1)$ ensures that the probability of the event

$\displaystyle
E_{2}^{\prime}\coloneqq\big{\\{}2\Delta_{T}\xi_{\varepsilon,\delta}^{-1}\zeta_{0}>2\Delta_{T}\xi_{\varepsilon,\delta}^{-1}F^{-1}_{\zeta}(\beta/4)\big{\\}}$

is equal to $1-\beta/4$ where $F_{\zeta}^{-1}$ is the inverse cumulative
distribution function of $\zeta$. Using these results as well as inequality
(44) from Step 1, it can be seen similarly to the proof of Theorem 7 that

$\displaystyle\mathbb{E}[1-\phi_{\mathrm{dpHSIC}}]~{}\leq~{}$
$\displaystyle\mathbb{P}\biggl{(}\mathrm{HSIC}_{k\otimes\ell}(P_{YZ})\leq
q_{1-\alpha,B}+C_{2}\sqrt{\frac{\log(8/\beta)}{n}}-2\Delta_{T}\xi_{\varepsilon,\delta}^{-1}F^{-1}_{\zeta}(\beta/4)\biggr{)}+\frac{\beta}{2}$
$\displaystyle\leq~{}$
$\displaystyle\mathbb{P}\biggl{(}\mathrm{HSIC}_{k\otimes\ell}(P_{YZ})\leq
C_{1}\sqrt{\frac{1}{n}\max\bigg{\\{}\log\biggl{(}\frac{4}{\alpha}\biggr{)},\,\log^{1/2}\biggl{(}\frac{4}{\alpha}\biggr{)},\,1\bigg{\\}}}$
$\displaystyle~{}~{}~{}~{}~{}+2\Delta_{T}\xi_{\varepsilon,\delta}^{-1}F_{\zeta}^{-1}(1-\alpha/4)+C_{2}\sqrt{\frac{\log(8/\beta)}{n}}-2\Delta_{T}\xi_{\varepsilon,\delta}^{-1}F^{-1}_{\zeta}(\beta/4)\biggr{)}+\beta.$

Next, recall that we assume $\alpha\in(0,1)$ and $\beta\in(0,1-\alpha)$ under
which it holds

$\displaystyle\max\bigg{\\{}\log\biggl{(}\frac{4}{\alpha}\biggr{)},\,\log^{1/2}\biggl{(}\frac{4}{\alpha}\biggr{)},\,1,\,\log\biggl{(}\frac{8}{\beta}\biggr{)}\bigg{\\}}~{}\leq~{}C_{3}\max\bigg{\\{}\log\biggl{(}\frac{1}{\alpha}\biggr{)},\,\log\biggl{(}\frac{1}{\beta}\biggr{)}\bigg{\\}}.$
(45)

To see this inequality, first assume that $\alpha\in(0,1/2)$. Then

$\displaystyle\max\bigg{\\{}\log\biggl{(}\frac{4}{\alpha}\biggr{)},\,\log^{1/2}\biggl{(}\frac{4}{\alpha}\biggr{)},\,1\bigg{\\}}~{}\leq~{}$
$\displaystyle C_{4}\log\biggl{(}\frac{1}{\alpha}\biggr{)}\leq
C_{4}\max\biggl{\\{}\log\biggl{(}\frac{1}{\alpha}\biggr{)},\,\log\biggl{(}\frac{8}{\beta}\biggr{)}\biggr{\\}}$
$\displaystyle\leq~{}$ $\displaystyle
C_{5}\max\biggl{\\{}\log\biggl{(}\frac{1}{\alpha}\biggr{)},\,\log\biggl{(}\frac{1}{\beta}\biggr{)}\biggr{\\}}$

as $\beta\in(0,1-\alpha)$. On the other hand, if $\alpha\in[1/2,1)$, $\beta$
should be less than $1/2$, which implies that

$\displaystyle\max\bigg{\\{}\log\biggl{(}\frac{4}{\alpha}\biggr{)},\,\log^{1/2}\biggl{(}\frac{4}{\alpha}\biggr{)},\,1\bigg{\\}}~{}\leq~{}$
$\displaystyle C_{6}\log\biggl{(}\frac{8}{\beta}\biggr{)}\leq
C_{7}\log\biggl{(}\frac{1}{\beta}\biggr{)}$ $\displaystyle\leq~{}$
$\displaystyle
C_{7}\max\biggl{\\{}\log\biggl{(}\frac{1}{\alpha}\biggr{)},\,\log\biggl{(}\frac{1}{\beta}\biggr{)}\biggr{\\}}.$

Therefore inequality (45) follows.

Having these ingredients in place, we follow the same lines of the proof of
Theorem 7 and see that

$\displaystyle\mathbb{E}[1-\phi_{\mathrm{dpHSIC}}]$ $\displaystyle\leq~{}$
$\displaystyle\mathbb{P}\biggl{(}\mathrm{HSIC}_{k\otimes\ell}(P_{YZ})\leq
C_{8}\sqrt{\frac{\max\bigl{\\{}\log(1/\alpha),\log(1/\beta)\\}}{n}}+C_{9}\frac{\max\bigl{\\{}\log(1/\alpha),\log(1/\beta)\\}}{n\xi_{\varepsilon,\delta}}\biggr{)}+\beta$
$\displaystyle\leq~{}$ $\displaystyle\beta,$

where the last inequality holds by taking $C_{K,L}$ to be larger than, for
instance, $2\max\\{C_{8},C_{9}\\}+1$ in the theorem statement. We conclude the
proof by noting that the upper bound is independent of $P_{YZ}$ and taking the
supremum on both sides over
$\mathcal{P}_{\mathrm{HSIC}_{k\otimes\ell}}\\!(\rho)$.

###  F.4 Proof of Theorem 13

The proof of Theorem 13 relies on the same idea as that of Theorem 8, which
uses Le Cam’s two point method and coupling method. Hence we omit the details
explained in the proof of Theorem 8, and instead focus on the key differences.
As in the proof of Theorem 8, we simply let
$\rho^{\star}_{\mathrm{HSIC}}=\rho^{\star}_{\mathrm{HSIC}}(\alpha,\beta,\varepsilon,\delta,n)$
and establish the minimax separation by examining the non-privacy regime and
privacy regime in order.

####  F.4.1 Non-privacy regime

We begin by proving that $\rho^{\star}_{\mathrm{HSIC}}\geq
C_{\eta_{Y},\eta_{Z}}\min\\{\sqrt{\log(1/(\alpha+\beta))/n},1\\}$ in the non-
privacy regime. We pick one distribution $P_{YZ,0}$ from
$\mathcal{P}_{\mathrm{HSIC}_{k\otimes\ell}}(\widetilde{\rho})$ with

$\displaystyle\widetilde{\rho}=C_{\eta_{Y},\eta_{Z}}\min\bigg{\\{}\sqrt{\frac{\log(1/(\alpha+\beta))}{n}},\,1\bigg{\\}}$

and denote the product of its marginals as $P_{Y,0}P_{Z,0}$. Then, as in
Section E.10.1, an application of Le Cam’s two point method (Le Cam,, 1973,
2012) and Bretagnolle–Huber inequality (Canonne,, 2022, Lemma B.4) yields

$\displaystyle\inf_{\phi\in\Phi_{\alpha,\varepsilon,\delta}}\sup_{P_{YZ}\in\mathcal{P}_{\mathrm{HSIC}_{k\otimes\ell}}(\widetilde{\rho})}\mathbb{E}_{P_{YZ}^{n}}[1-\phi]~{}\geq~{}$
$\displaystyle\inf_{\phi\in\Phi_{\alpha,\infty}}\sup_{P_{YZ}\in\mathcal{P}_{\mathrm{HSIC}_{k\otimes\ell}}(\widetilde{\rho})}\mathbb{E}_{P_{YZ}}[1-\phi]$
$\displaystyle\geq~{}$
$\displaystyle\inf_{\phi\in\Phi_{\alpha,\infty}}\mathbb{E}_{P_{YZ,0}}[1-\phi]=1-\sup_{\phi\in\Phi_{\alpha,\infty}}\mathbb{E}_{P_{YZ,0}}[\phi]$
$\displaystyle\geq~{}$ $\displaystyle 1-\alpha-
d_{\mathrm{TV}}(P_{YZ,0}^{\otimes n},P_{Y,0}^{\otimes n}P_{Z,0}^{\otimes n})$
$\displaystyle\geq~{}$ $\displaystyle\frac{1}{2}e^{-n\times
d_{\mathrm{KL}}(P_{YZ,0}\|P_{Y,0}P_{Z,0})}-\alpha.$

Therefore the minimax type II error is at least $\beta$ if $\alpha+\beta<0.4$
as well as

$\displaystyle
d_{\mathrm{KL}}(P_{YZ,0}\|P_{Y,0}P_{Z,0})\leq\frac{1}{n}\log\biggl{(}\frac{1}{2(\alpha+\beta)}\biggr{)}.$

Hence $\rho^{\star}_{\mathrm{HSIC}}\geq
C_{\eta_{Y},\eta_{Z}}\min\\{\sqrt{\log(1/(\alpha+\beta))/n},1\\}$ follows if
we find $P_{YZ,0}$ such that

$\displaystyle\mathrm{HSIC}_{k\otimes\ell}(P_{YZ,0},P_{Y,0}P_{Z,0})\geq
C_{\eta_{Y},\eta_{Z}}\min\Bigg{\\{}\sqrt{\frac{\log(1/(\alpha+\beta))}{n}},\,1\Bigg{\\}}\quad\text{and}$
(46a) $\displaystyle
d_{\mathrm{KL}}(P_{YZ,0}\|P_{Y,0}P_{Z,0})\leq\frac{1}{n}\log\biggl{(}\frac{1}{2(\alpha+\beta)}\biggr{)}.$
(46b)

To this end, consider (discrete) random vectors $Y\in\\{y_{1},y_{2}\\}$ and
$Z\in\\{z_{1},z_{2}\\}$ where $y_{1},y_{2}\in\mathbb{R}^{d_{Y}}$ and
$z_{1},z_{2}\in\mathbb{R}^{d_{Z}}$. Further assume that
$\mathbb{P}(Y=y_{1})=\mathbb{P}(Y=y_{2})=1/2$ and
$\mathbb{P}(Z=z_{1})=\mathbb{P}(Z=z_{2})=1/2$. Suppose that the joint
probabilities of $(Y,Z)$ are given as

$\displaystyle\mathbb{P}(Y=y_{1},Z=z_{1})=\mathbb{P}(Y=y_{2},Z=z_{2})=1/4+\nu\quad\text{and}$
$\displaystyle\mathbb{P}(Y=y_{1},Z=z_{2})=\mathbb{P}(Y=y_{2},Z=z_{1})=1/4-\nu,$

where $\nu\in(0,1/4]$. In this setting, it can be seen that $P_{YZ,0}\neq
P_{Y,0}P_{Z,0}$ and thus $Y$ and $Z$ are trivially dependent. For such
$P_{YZ,0}$ and translation invariant kernels, we have

$\displaystyle\mathrm{HSIC}_{k\otimes\ell}(P_{YZ,0})~{}\overset{\mathrm{(i)}}{=}~{}$
$\displaystyle\sqrt{\mathbb{E}[k(Y_{1},Y_{2})\ell(Z_{1},Z_{2})]+\mathbb{E}[k(Y_{1},Y_{2})\ell(Z_{3},Z_{4})]-2\mathbb{E}[k(Y_{1},Y_{2})\ell(Z_{1},Z_{3})]}$
$\displaystyle\overset{\mathrm{(ii)}}{=}~{}$
$\displaystyle\sqrt{4\nu^{2}\\{\kappa_{Y}(0)-\kappa_{Y}(y_{1}-y_{2})\\}\\{\kappa_{Z}(0)-\kappa_{Z}(z_{1}-z_{2})\\}}$
$\displaystyle\overset{\mathrm{(iii)}}{\geq}~{}$
$\displaystyle\sqrt{4\nu^{2}\eta_{Y}\eta_{Z}}=2\nu\sqrt{\eta_{Y}\eta_{Z}},$

where step (i) follows by Gretton et al., (2005, Lemma 1) with
$\\{(Y_{i},Z_{i})\\}_{i=1}^{4}\overset{\mathrm{i.i.d.}}{\sim}P_{YZ,0}$, step
(ii) can be verified through algebra and the last inequality (iii) holds by
choosing $(y_{1},y_{2})$ and $(z_{1},z_{2})$ such that $y_{1}-y_{2}=y_{0}$ and
$z_{1}-z_{2}=z_{0}$.

On the other hand, we verify condition (46b) based on the well-known fact
(_e.g._ , Tsybakov,, 2009, Lemma 2.7) that the Kullback–Leibler divergence is
upper bounded by $\chi^{2}$ divergence denoted by
$d_{\chi^{2}}(P_{YZ,0}\|P_{Y,0}P_{Z,0})$. This gives

$\displaystyle d_{\mathrm{KL}}(P_{YZ,0}\|P_{Y,0}P_{Z,0})~{}\leq~{}$
$\displaystyle
d_{\chi^{2}}(P_{YZ,0}\|P_{Y,0}P_{Z,0})=8\biggl{(}\frac{1}{4}+\nu\biggr{)}^{2}+8\biggl{(}\frac{1}{4}-\nu\biggr{)}^{2}-1$
$\displaystyle=~{}$ $\displaystyle 16\nu^{2}.$

Using the above inequality, condition (46b) is fulfilled by taking

$\displaystyle\nu=\min\Bigg{\\{}\sqrt{\frac{1}{16n}\log\biggl{(}\frac{1}{2(\alpha+\beta)}\biggr{)}},\,\frac{1}{4}\Bigg{\\}}$

for which condition (46a) is also satisfied as

$\displaystyle\mathrm{HSIC}_{k\otimes\ell}(P_{YZ,0})~{}\geq~{}$ $\displaystyle
2\nu\sqrt{\eta_{Y}\eta_{Z}}=\frac{\sqrt{\eta_{Y}\eta_{Z}}}{2}\min\Bigg{\\{}\sqrt{\frac{1}{n}\log\biggl{(}\frac{1}{2(\alpha+\beta)}\biggr{)}},\,1\Bigg{\\}}$
$\displaystyle\geq~{}$ $\displaystyle
C_{\eta_{Y},\eta_{Z}}\min\Bigg{\\{}\sqrt{\frac{\log(1/(\alpha+\beta))}{n}},\,1\Bigg{\\}}$

as $\alpha+\beta<0.4$. Therefore it holds that
$\rho^{\star}_{\mathrm{HSIC}}\geq
C_{\eta_{Y},\eta_{Z}}\min\\{\sqrt{\log(1/(\alpha+\beta))/n},1\\}$ as desired.

####  F.4.2 Privacy regime

The proof of the separation rate under the privacy regime is essentially the
same as that for the $\mathrm{dpMMD}$ test in Appendix E.10.2. All we need is
to find an instance of $P_{YZ,0}$ such that

$\displaystyle\mathrm{HSIC}_{k\otimes\ell}(P_{YZ,0})\geq
C_{\eta_{Y},\eta_{Z}}\min\Bigg{\\{}\frac{\log(1/\beta)}{n\big{(}\varepsilon+\delta\big{)}},\,1\Bigg{\\}}\quad\text{and}$
(47a)
$\displaystyle\|P_{YZ,0}-P_{Y,0}P_{Z,0}\|_{1}\leq\frac{1}{20n\big{(}\varepsilon+\delta\big{)}}\log\biggl{(}\frac{1}{4\beta}\biggr{)}.$
(47b)

To this end, choose the distribution of $(Y,Z)$ as in the case of the non-
privacy regime. For such $P_{YZ,0}$, a direct calculation gives
$\|P_{YZ,0}-P_{Y,0}P_{Z,0}\|_{1}=4\nu$ and thus condition (47b) is satisfied
if we take

$\displaystyle\nu=\min\Bigg{\\{}\frac{1}{80n\big{(}\varepsilon+\delta\big{)}}\log\biggl{(}\frac{1}{4\beta}\biggr{)},\,\frac{1}{4}\Bigg{\\}}.$

On the other hand, the previous calculation of the lower bound for
$\mathrm{HSIC}_{k\otimes\ell}(P_{YZ,0})$ yields

$\displaystyle\mathrm{HSIC}_{k\otimes\ell}(P_{YZ,0})~{}\geq~{}$ $\displaystyle
2\nu\sqrt{\eta_{Y}\eta_{Z}}=2\min\Bigg{\\{}\frac{1}{80n\big{(}\varepsilon+\delta\big{)}}\log\biggl{(}\frac{1}{4\beta}\biggr{)},\,\frac{1}{4}\Bigg{\\}}\sqrt{\eta_{Y}\eta_{Z}}$
$\displaystyle\geq~{}$ $\displaystyle
C_{\eta_{Y},\eta_{Z}}\min\Bigg{\\{}\frac{\log(1/\beta)}{n\big{(}\varepsilon+\delta\big{)}},\,1\Bigg{\\}}$

which in turn verifies condition (47a) under $\beta\in(0,1/5)$. Therefore it
holds that the minimax separation under privacy regime
$\rho^{\star}_{\mathrm{HSIC}}\geq
C_{\eta_{Y},\eta_{Z}}\min\\!\big{\\{}\log(1/\beta)/(n(\varepsilon+\delta)),1\big{\\}}$.

####  F.4.3 Combining bounds

Combining the lower bounds for the non-privacy and privacy regimes, for all
$\varepsilon>0$ and $\delta\in[0,1)$, we obtain

$\displaystyle\rho^{\star}_{\mathrm{HSIC}}~{}\geq~{}$ $\displaystyle
C_{\eta_{Y},\eta_{Z}}\max\Biggl{\\{}\min\bigg{\\{}\sqrt{\frac{\log(1/(\alpha+\beta))}{n}},\,1\bigg{\\}},\,\min\biggl{\\{}\frac{\log(1/\beta)}{n(\varepsilon+\delta)},\,1\biggr{\\}}\Biggr{\\}}$
$\displaystyle\geq~{}$ $\displaystyle
C_{\eta_{Y},\eta_{Z}}\max\Biggl{\\{}\min\bigg{\\{}\sqrt{\frac{\log(1/(\alpha+\beta))}{n}},\,1\bigg{\\}},\,\min\biggl{\\{}\frac{\log(1/\beta)}{n\big{(}\varepsilon+\log(1/(1-\delta))\big{)}},\,1\biggr{\\}}\Biggr{\\}}.$

The last inequality holds since $\log(1/(1-\delta))\geq\delta$ for all
$\delta\in[0,1)$, and is actually tight when $\alpha\asymp\beta$ as explained
in Section E.10.3. This concludes the proof of Theorem 12.

###  F.5 Proof of Theorem 14

The proof of Theorem 14 follows the same structure as the proof of Theorem 9
in Section E.11. For simplicity, write $\widehat{\mathrm{HSIC}}^{2}$ given in
(12) with the Gaussian kernels as $V_{\mathrm{HSIC}}$ and similarly the
U-statistic given in (21) with the Gaussian kernel as $U_{\mathrm{HSIC}}$. We
also denote the corresponding statistics based on permuted data
$\mathcal{X}_{n}^{\bm{\pi}}$ as $V_{\bm{\pi},\mathrm{HSIC}}$ and
$U_{\bm{\pi},\mathrm{HSIC}}$, respectively. Letting

$\displaystyle
K=\prod_{i=1}^{d_{Y}}\frac{1}{\sqrt{2\pi}\lambda_{i}}\quad\text{and}\quad
L=\prod_{i=1}^{d_{Z}}\frac{1}{\sqrt{2\pi}\mu_{i}},$

Lemma 21 ensures that the difference between $V_{\mathrm{HSIC}}$ and
$U_{\mathrm{HSIC}}$ can be written as

$\displaystyle V_{\mathrm{HSIC}}-U_{\mathrm{HSIC}}=D_{1}+D_{2},$

where

$\displaystyle D_{1}=$
$\displaystyle\frac{n-1}{n^{2}}KL-\frac{L}{n^{3}}\sum_{(i,j)\in\mathbf{i}_{2}^{n}}k_{\bm{\lambda}}(Y_{i},Y_{j})-\frac{K}{n^{3}}\sum_{(i,j)\in\mathbf{i}_{2}^{n}}\ell_{\bm{\mu}}(Z_{i},Z_{j}),$
$\displaystyle D_{2}=$
$\displaystyle-\frac{3n^{2}-4n+2}{(n-1)n^{4}}\sum_{(i,j)\in\mathbf{i}_{2}^{n}}k_{\bm{\lambda}}(Y_{i},Y_{j})\ell_{\bm{\mu}}(Z_{i},Z_{j})+\frac{2(5n^{2}-8n+4)}{n^{4}(n-1)(n-2)}\sum_{(i,j_{1},j_{2})\in\mathbf{i}_{3}^{n}}k_{\bm{\lambda}}(Y_{i},Y_{j_{1}})\ell_{\bm{\mu}}(Z_{i},Z_{j_{2}})$
$\displaystyle-\frac{6n^{2}-11n+6}{n^{4}(n-1)(n-2)(n-3)}\sum_{(i_{1},i_{2},j_{1},j_{2})\in\mathbf{i}_{4}^{n}}k_{\bm{\lambda}}(Y_{i_{1}},Y_{i_{2}})\ell_{\bm{\mu}}(Z_{j_{1}},Z_{j_{2}}).$

The term $D_{1}$ is invariant to any permutation of $Z$ values, and thus the
permutation distribution of $V_{\bm{\pi},\mathrm{HSIC}}$ is equivalent to the
permutation distribution of $U_{\bm{\pi},\mathrm{HSIC}}+D_{1}+D_{2,\bm{\pi}}$
where $D_{2,\bm{\pi}}$ has the same form of $D_{2}$ but computed based on
permuted data $\mathcal{X}_{n}^{\bm{\pi}}$. Writing the sensitivity of
$\sqrt{V_{\mathrm{HSIC}}}$ as $\Delta_{V^{1/2}}$, Lemma 17 yields that the
$\mathrm{dpHSIC}$ test rejects the null if and only if

$\displaystyle\sqrt{V_{\mathrm{HSIC}}}+\frac{2\Delta_{V^{1/2}}}{\xi_{\varepsilon,\delta}}\zeta_{0}>q_{1-\alpha,B},$

where $q_{1-\alpha,B}$ is the $1-\alpha$ quantile of
$\\{\sqrt{V_{\bm{\pi}_{i},\mathrm{HSIC}}}+2\Delta_{V^{1/2}}\xi_{\varepsilon,\delta}^{-1}\zeta_{i}\\}_{i=0}^{B}$.
As in the proof of Theorem 9 in Section E.11, we let $q_{1-\alpha,B}^{a}$
denote the $1-\alpha$ quantile of
$\\{V_{\bm{\pi}_{0},\mathrm{HSIC}}^{1/2},V_{\bm{\pi}_{1},\mathrm{HSIC}}^{1/2},\ldots,V_{\bm{\pi}_{B},\mathrm{HSIC}}^{1/2}\\}$.
Similarly, denote by $q_{1-\alpha,\infty}^{a}$ the corresponding $1-\alpha$
quantile with $B=\infty$. Then for $B\geq 16\alpha^{-2}\log(8/\beta)$, the
analysis given in the proof of Theorem 9 shows that the type II error of the
$\mathrm{dpHSIC}$ test can be bounded as

$\displaystyle\mathbb{P}\bigl{(}\sqrt{V_{\mathrm{HSIC}}}+2\Delta_{V^{1/2}}\xi_{\varepsilon,\delta}^{-1}\zeta_{0}\leq
q_{1-\alpha,B}\bigr{)}$ $\displaystyle\leq~{}$
$\displaystyle\mathbb{P}\bigl{(}\sqrt{V_{\mathrm{HSIC}}}\leq
q_{1-\alpha/4,\infty}^{a}+10\Delta_{V^{1/2}}\xi_{\varepsilon,\delta}^{-1}\max\\{\log(1/\alpha),\log(1/\beta)\\}\bigr{)}+5\beta/8.$
(48)

We next delve into $q_{1-\alpha/4,\infty}^{a}$, and then continue to upper
bound the type II error. In what follows, we use the notation
$C_{1},C_{2},C_{3},\ldots$ to represent constants, which could be dependent on
$\alpha,\beta,s,R,M,d_{Y},d_{Z}$. The values of these constants may vary in
different places.

Bounding $q_{1-\alpha/4,\infty}^{a}$. Using the relationship between
$V_{\mathrm{HSIC}}$ and $U_{\mathrm{HSIC}}$ in Lemma 21 and the quantile
inequality in Lemma 20, we have

$\displaystyle q_{1-\alpha/4,\infty}^{a}~{}=~{}$
$\displaystyle\sqrt{\mathrm{Quantile}_{1-\alpha/4}\bigl{(}\big{\\{}U_{\bm{\pi}_{i},\mathrm{HSIC}}+D_{2,\bm{\pi}_{i}}\big{\\}}_{i=0}^{\infty}+D_{1}\bigr{)}}$
$\displaystyle\leq~{}$
$\displaystyle\sqrt{\mathrm{Quantile}_{1-\alpha/8}\bigl{(}\big{\\{}U_{\bm{\pi}_{i},\mathrm{HSIC}}\big{\\}}_{i=0}^{\infty}\bigr{)}+\mathrm{Quantile}_{1-\alpha/8}\bigl{(}\big{\\{}D_{2,\bm{\pi}_{i}}\big{\\}}_{i=0}^{\infty}\bigr{)}+D_{1}}.$

The quantile of the permuted U-statistic $U_{\bm{\pi},\mathrm{HSIC}}$ has been
studied by Kim et al., 2022a . In particular, the proof of Kim et al., 2022a
(, Theorem 5.1) along with the proof of Albert et al., (2022, Proposition 2)
shows that

$\displaystyle\mathbb{E}_{\bm{\pi}}[U_{\bm{\pi},\mathrm{HSIC}}\,|\,\mathcal{X}_{n}]=0\quad\text{and}\quad\mathbb{E}\bigl{[}\mathrm{Var}_{\bm{\pi}}\bigl{(}U_{\bm{\pi},\mathrm{HSIC}}\,|\,\mathcal{X}_{n}\bigr{)}\bigr{]}\leq\frac{C_{1}}{n^{2}\lambda_{1}\cdots\lambda_{d_{Y}}\mu_{1}\cdots\mu_{d_{Z}}}.$

Thus by Chebyshev’s inequality, it can be seen that the following inequality
holds with probability at least $1-\beta/8$:

$\displaystyle\mathrm{Quantile}_{1-\alpha/8}\bigl{(}\big{\\{}U_{\bm{\pi}_{i},\mathrm{HSIC}}\big{\\}}_{i=0}^{\infty}\bigr{)}\leq\frac{C_{2}}{n\sqrt{\lambda_{1}\cdots\lambda_{d_{Y}}\mu_{1}\cdots\mu_{d_{Z}}}},$
(49)

For the $1-\alpha/8$ quantile of
$\big{\\{}D_{2,\bm{\pi}_{i}}\big{\\}}_{i=0}^{\infty}$, note that

$\displaystyle
D_{2,\bm{\pi}}\leq\frac{C_{3}}{n^{4}}\sum_{(i,j_{1},j_{2})\in\mathbf{i}_{3}^{n}}k_{\bm{\lambda}}(Y_{i},Y_{j_{1}})\ell_{\bm{\mu}}(Z_{\pi_{i}},Z_{\pi_{j_{2}}})$

due to the non-negativity of $k_{\bm{\lambda}}$ and $\ell_{\bm{\mu}}$, and
also note that

$\displaystyle\mathbb{E}_{\bm{\pi}}\Biggl{[}\sum_{(i,j_{1},j_{2})\in\mathbf{i}_{3}^{n}}k_{\bm{\lambda}}(Y_{i},Y_{j_{1}})\ell_{\bm{\mu}}(Z_{\pi_{i}},Z_{\pi_{j_{2}}})\,\Big{|}\,\mathcal{X}_{n}\Biggr{]}\leq\frac{C_{4}}{n}\Biggl{[}\sum_{(i_{1},i_{2})\in\mathbf{i}_{2}^{n}}k_{\bm{\lambda}}(Y_{i_{1}},Y_{i_{2}})\Biggr{]}\Biggl{[}\sum_{(j_{1},j_{2})\in\mathbf{i}_{2}^{n}}\ell_{\bm{\mu}}(Z_{j_{1}},Z_{j_{2}})\Biggr{]}.$

Then Markov’s inequality yields that the $1-\alpha/8$ quantile of
$\big{\\{}D_{2,\bm{\pi}_{i}}\big{\\}}_{i=0}^{\infty}$ is bounded as

$\displaystyle\mathrm{Quantile}_{1-\alpha/8}\bigl{(}\big{\\{}D_{2,\bm{\pi}_{i}}\big{\\}}_{i=0}^{\infty}\bigr{)}\leq\frac{C_{5}}{n^{5}}\Biggl{[}\sum_{(i_{1},i_{2})\in\mathbf{i}_{2}^{n}}k_{\bm{\lambda}}(Y_{i_{1}},Y_{i_{2}})\Biggr{]}\Biggl{[}\sum_{(j_{1},j_{2})\in\mathbf{i}_{2}^{n}}\ell_{\bm{\mu}}(Z_{j_{1}},Z_{j_{2}})\Biggr{]}.$

Moreover, since we assume $\|p_{YZ}\|_{L_{\infty}}\leq M$ and
$\|p_{Y}p_{Z}\|_{L_{\infty}}\leq M$,

$\displaystyle\max\Big{\\{}\mathbb{E}[k_{\bm{\lambda}}(Y_{1},Y_{2})\ell_{\bm{\mu}}(Z_{1},Z_{2})],\
\mathbb{E}[k_{\bm{\lambda}}(Y_{1},Y_{2})\ell_{\bm{\mu}}(Z_{1},Z_{3})],\
\mathbb{E}[k_{\bm{\lambda}}(Y_{1},Y_{2})\ell_{\bm{\mu}}(Z_{3},Z_{4})]\Big{\\}}\leq
C_{6}.$

For instance, we see that

$\displaystyle\mathbb{E}[k_{\bm{\lambda}}(Y_{1},Y_{2})\ell_{\bm{\mu}}(Z_{1},Z_{2})]~{}=~{}$
$\displaystyle\int\cdots\int
k_{\bm{\lambda}}(y_{1},y_{2})\ell_{\bm{\mu}}(z_{1},z_{2})p_{YZ}(y_{1},z_{1})p_{YZ}(y_{2},z_{2})\mathrm{d}y_{1}\mathrm{d}y_{2}\mathrm{d}z_{1}\mathrm{d}z_{2}$
$\displaystyle\leq~{}$
$\displaystyle\|p_{YZ}\|_{L_{\infty}}\int\int\underbrace{\int
k_{\bm{\lambda}}(y_{1},y_{2})\mathrm{d}y_{1}}_{=1}\underbrace{\int\ell_{\bm{\mu}}(z_{1},z_{2})\mathrm{d}z_{1}}_{=1}p_{YZ}(y_{2},z_{2})\mathrm{d}y_{2}\mathrm{d}z_{2}$
$\displaystyle\leq~{}$ $\displaystyle M,$

and the other terms can be similarly analyzed. Given this ingredient, we have

$\displaystyle\mathbb{E}\Biggl{\\{}\Biggl{[}\sum_{(i_{1},i_{2})\in\mathbf{i}_{2}^{n}}k_{\bm{\lambda}}(Y_{i_{1}},Y_{i_{2}})\Biggr{]}\Biggl{[}\sum_{(j_{1},j_{2})\in\mathbf{i}_{2}^{n}}\ell_{\bm{\mu}}(Z_{j_{1}},Z_{j_{2}})\Biggr{]}\Biggr{\\}}\leq
C_{7}n^{4}.$

Therefore, another application of Markov’s inequality yields

$\displaystyle\mathrm{Quantile}_{1-\alpha/8}\bigl{(}\big{\\{}D_{2,\bm{\pi}_{i}}\big{\\}}_{i=0}^{\infty}\bigr{)}\leq\frac{C_{8}}{n},$
(50)

with probability at least $1-\beta/8$, and observe that
$D_{1}\leq\frac{n-1}{n^{2}}KL\leq
C_{9}/\\{n\lambda_{1}\cdots\lambda_{d_{Y}}\mu_{1}\cdots\mu_{d_{Z}}\\}$.

In summary, with probability at least $1-\beta/4$,

$\displaystyle
q_{1-\alpha/4,\infty}^{a}\leq\frac{C_{10}}{\sqrt{n\lambda_{1}\cdots\lambda_{d_{Y}}\mu_{1}\cdots\mu_{d_{Z}}}}.$
(51)

given that $D_{1}\leq KL/n$ and
$\lambda_{1}\cdots\lambda_{d_{Y}}\mu_{1}\cdots\mu_{d_{Z}}\leq 1$.

Bounding the type II error. We continue from (48), and note that

$\displaystyle\mathbb{P}\Bigl{(}\sqrt{V_{\mathrm{HSIC}}}\leq
q_{1-\alpha/4,\infty}^{a}+10\Delta_{V^{1/2}}\xi_{\varepsilon,\delta}^{-1}\max\\{\log(1/\alpha),\log(1/\beta)\\}\Bigr{)}$
$\displaystyle=~{}$
$\displaystyle\mathbb{P}\Bigl{(}V_{\mathrm{HSIC}}\leq(q_{1-\alpha/4,\infty}^{a})^{2}+10^{2}\Delta_{V^{1/2}}^{2}\xi_{\varepsilon,\delta}^{-2}\max\\{\log^{2}(1/\alpha),\log^{2}(1/\beta)\\}$
$\displaystyle~{}~{}~{}+20q_{1-\alpha/4,\infty}^{a}\Delta_{V^{1/2}}\xi_{\varepsilon,\delta}^{-1}\max\\{\log(1/\alpha),\log(1/\beta)\\}\Bigr{)}$
$\displaystyle=~{}$
$\displaystyle\mathbb{P}\Bigl{(}U_{\mathrm{HSIC}}\leq\mathrm{Quantile}_{1-\alpha/8}\bigl{(}\big{\\{}U_{\bm{\pi}_{i},\mathrm{HSIC}}\big{\\}}_{i=0}^{\infty}\bigr{)}+\mathrm{Quantile}_{1-\alpha/8}\bigl{(}\big{\\{}D_{2,\bm{\pi}_{i}}\big{\\}}_{i=0}^{\infty}\bigr{)}-D_{2}$
$\displaystyle~{}~{}~{}+10^{2}\Delta_{V^{1/2}}^{2}\xi_{\varepsilon,\delta}^{-2}\max\\{\log^{2}(1/\alpha),\log^{2}(1/\beta)\\}+20q_{1-\alpha/4,\infty}^{a}\Delta_{V^{1/2}}\xi_{\varepsilon,\delta}^{-1}\max\\{\log(1/\alpha),\log(1/\beta)\\}\Bigr{)},$

where the first equality simply follows by taking the square on both sides,
and the second equality uses the identity
$V_{\mathrm{HSIC}}=U_{\mathrm{HSIC}}+D_{1}+D_{2}$ from Lemma 21. Next, by
Lemma 6, the global sensitivity of $\sqrt{V_{\mathrm{HSIC}}}$ is bounded as

$\displaystyle\Delta_{V^{1/2}}\leq\frac{C_{1}}{n\sqrt{\lambda_{1}\cdots\lambda_{d_{Y}}\mu_{1}\cdots\mu_{d_{Z}}}}.$

In addition, observe that $|D_{2}|\leq C_{2}n^{-1}$ with probability at least
$1-\beta/16$, which can be proven by Markov’s inequality. Therefore, equipped
with the previous ingredients (48), (49), (50) and (51), the type II error
bound can be bounded as

$\displaystyle\mathbb{P}\bigl{(}\sqrt{V_{\mathrm{HSIC}}}+2\Delta_{V^{1/2}}\xi_{\varepsilon,\delta}^{-1}\zeta_{0}\leq
q_{1-\alpha,B}\bigr{)}$ $\displaystyle\leq~{}$
$\displaystyle\mathbb{P}\biggl{(}U_{\mathrm{HSIC}}\leq\frac{C_{3}}{n\sqrt{\lambda_{1}\cdots\lambda_{d_{Y}}\mu_{1}\cdots\mu_{d_{Z}}}}+\frac{C_{4}}{n^{2}\lambda_{1}\cdots\lambda_{d_{Y}}\mu_{1}\cdots\mu_{d_{Z}}\xi_{\varepsilon,\delta}^{2}}$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}+\frac{C_{5}}{n^{3/2}\lambda_{1}\cdots\lambda_{d_{Y}}\mu_{1}\cdots\mu_{d_{Z}}\xi_{\varepsilon,\delta}}\biggr{)}+\frac{15}{16}\beta.$

Condition in terms of $L_{2}$ distance. A slight modification of Albert et
al., (2022, Lemma 1) yields that a sufficient condition for the first
probability in the above display to be less than $\beta/16$ is

$\displaystyle\mathrm{HSIC}^{2}_{k_{\bm{\lambda}}\otimes\ell_{\bm{\mu}}}~{}\geq~{}$
$\displaystyle\sqrt{\mathrm{Var}[U_{\mathrm{HSIC}}]}+\frac{C_{3}}{n\sqrt{\lambda_{1}\cdots\lambda_{d_{Y}}\mu_{1}\cdots\mu_{d_{Z}}}}+\frac{C_{4}}{n^{2}\lambda_{1}\cdots\lambda_{d_{Y}}\mu_{1}\cdots\mu_{d_{Z}}\xi_{\varepsilon,\delta}^{2}}$
$\displaystyle+\frac{C_{5}}{n^{3/2}\lambda_{1}\cdots\lambda_{d_{Y}}\mu_{1}\cdots\mu_{d_{Z}}\xi_{\varepsilon,\delta}}.$

In addition, by writing $\psi=p_{YZ}-p_{Y}p_{Z}$ and the convolution of $\psi$
and $k_{\bm{\lambda}}\otimes\ell_{\bm{\mu}}$ as
$\psi\ast(k_{\bm{\lambda}}\otimes\ell_{\bm{\mu}})$, Albert et al., (2022,
Theorem 1 and Proposition 4) show that the previous condition is implied by

$\displaystyle\|\psi\|_{L_{2}}^{2}~{}\geq~{}\|\psi-\psi\ast(k_{\bm{\lambda}}\otimes\ell_{\bm{\mu}})\|_{L_{2}}^{2}+C_{6}$
$\displaystyle\Bigg{\\{}\frac{1}{n\sqrt{\lambda_{1}\cdots\lambda_{d_{Y}}\mu_{1}\cdots\mu_{d_{Z}}}}+\frac{1}{n^{2}\lambda_{1}\cdots\lambda_{d_{Y}}\mu_{1}\cdots\mu_{d_{Z}}\xi_{\varepsilon,\delta}^{2}}$
$\displaystyle+\frac{1}{n^{3/2}\lambda_{1}\cdots\lambda_{d_{Y}}\mu_{1}\cdots\mu_{d_{Z}}\xi_{\varepsilon,\delta}}\Bigg{\\}}.$

Finally the proof of (Albert et al.,, 2022, Theorem 2) yields that over the
Sobolev ball, a sufficient condition for the previous inequality is

$\displaystyle\|\psi\|_{L_{2}}^{2}~{}\geq~{}C_{7}\Bigg{\\{}$
$\displaystyle\sum_{i=1}^{d_{Y}}\lambda_{i}^{2s}+\sum_{i=1}^{d_{Z}}\mu_{i}^{2s}+\frac{1}{n\sqrt{\lambda_{1}\cdots\lambda_{d_{Y}}\mu_{1}\cdots\mu_{d_{Z}}}}$
$\displaystyle+\frac{1}{n^{2}\lambda_{1}\cdots\lambda_{d_{Y}}\mu_{1}\cdots\mu_{d_{Z}}\xi_{\varepsilon,\delta}^{2}}+\frac{1}{n^{3/2}\lambda_{1}\cdots\lambda_{d_{Y}}\mu_{1}\cdots\mu_{d_{Z}}\xi_{\varepsilon,\delta}}\Bigg{\\}}$

as claimed.

###  F.6 Proof of Lemma 9

##### Sensitivity upper bound.

For simplicity, write
$U_{\mathrm{HSIC}}=U_{\mathrm{HSIC},a}+U_{\mathrm{HSIC},b}-2U_{\mathrm{HSIC},c}$
where

$\displaystyle U_{\mathrm{HSIC},a}~{}:=~{}$
$\displaystyle\frac{1}{n(n-1)}\sum_{(i,j)\in\mathbf{i}_{2}^{n}}k(Y_{i},Y_{j})\ell(Z_{i},Z_{j}),$
$\displaystyle U_{\mathrm{HSIC},b}~{}:=~{}$
$\displaystyle\frac{(n-4)!}{n!}\sum_{(i_{1},i_{2},j_{1},j_{2})\in\mathbf{i}_{4}^{n}}k(Y_{i_{1}},Y_{j_{1}})\ell(Z_{i_{2}},Z_{j_{2}}),$
$\displaystyle U_{\mathrm{HSIC},c}~{}:=~{}$
$\displaystyle\frac{1}{n(n-1)(n-2)}\sum_{(i,j_{1},j_{2})\in\mathbf{i}_{3}^{n}}k(Y_{i},Y_{j_{1}})\ell(Z_{i},Z_{j_{2}}).$

To establish an upper bound for the global sensitivity, we first consider a
neighboring dataset
$\tilde{\mathcal{X}}_{n}=\\{(Y_{1}^{\prime},Z_{1}^{\prime}),(Y_{2},Z_{2}),\ldots,(Y_{n},Z_{n})\\}$
and denote the U-statistic of HSIC based on $\tilde{\mathcal{X}}_{n}$ as
$U_{\mathrm{HSIC}}^{\prime}:=U_{\mathrm{HSIC},a}^{\prime}+U_{\mathrm{HSIC},b}^{\prime}-2U_{\mathrm{HSIC},c}^{\prime}$.
By the triangle inequality, the absolute deviation between $U_{\mathrm{HSIC}}$
and $U_{\mathrm{HSIC}}^{\prime}$ is then bounded as

$\displaystyle|U_{\mathrm{HSIC}}-U_{\mathrm{HSIC}}^{\prime}|~{}\leq~{}$
$\displaystyle|U_{\mathrm{HSIC},a}-U_{\mathrm{HSIC},a}^{\prime}|+|U_{\mathrm{HSIC},b}-U_{\mathrm{HSIC},b}^{\prime}|+2|U_{\mathrm{HSIC},c}-U_{\mathrm{HSIC},c}^{\prime}|$
$\displaystyle\leq~{}$ $\displaystyle\frac{C_{1}KL}{n},$

where $C_{1},C_{2},\ldots$ denote some universal positive constants
throughout.

For another neighboring dataset
$\tilde{\mathcal{X}}_{n}=\\{(Y_{1}^{\prime},Z_{1}),(Y_{2},Z_{2}^{\prime}),\ldots,(Y_{n},Z_{n})\\}$,
a similar analysis shows that
$|U_{\mathrm{HSIC}}-U_{\mathrm{HSIC}}^{\prime}|\leq\frac{C_{2}KL}{n}$. Since
$U_{\mathrm{HSIC}}$ is invariant to the permutation of the paired indices, we
may conclude that

$\displaystyle\sup_{\bm{\pi}\in\bm{\Pi}_{n}}\sup_{\begin{subarray}{c}\mathcal{X}_{n},\tilde{\mathcal{X}}_{n}:\\\
d_{\mathrm{ham}}(\mathcal{X}_{n},\tilde{\mathcal{X}}_{n})\leq
1\end{subarray}}\bigl{|}U_{\mathrm{HSIC}}(\mathcal{X}_{n}^{\bm{\pi}})-U_{\mathrm{HSIC}}(\tilde{\mathcal{X}}_{n}^{\bm{\pi}})\bigr{|}\leq\frac{C_{3}KL}{n}.$
(52)

While it is loose, the inequality holds with $C_{3}=24$ for $n\geq 4$.

##### Sensitivity lower bound.

We now show that this upper bound is tight up to a constant factor. We treat
the cases of $n$ being even or odd separately, and follow a similar reasoning
to the one in Section E.7. Recall that kernels $k$ and $\ell$ are assumed to
have non-empty level sets on $\mathbb{Y}$ and $\mathbb{Z}$. Hence, for a given
$\epsilon\in(0,\min\\{K,L\\})$, we may assume that there exist
$y_{a},y_{b}\in\mathbb{Y}$ and $z_{a},z_{b}\in\mathbb{Z}$ such that
$k(y_{a},y_{b})=\epsilon_{1}$ and $\ell(z_{a},z_{b})=\epsilon_{2}$ where
$0\leq\epsilon_{1},\epsilon_{2}\leq\epsilon$.

##### Sensitivity lower bound for $n=2k$ even.

We begin by considering the case where $n$ is even, and compute the difference
between U-statistics of the HSIC based on two specific neighboring datasets
given below:

$\displaystyle\mathcal{X}_{n}=\begin{bmatrix}y_{a}&z_{a}\\\ \vdots&\vdots\\\
y_{a}&z_{a}\\\ y_{a}&z_{a}\\\ y_{a}&z_{a}\\\ y_{b}&z_{b}\\\ \vdots&\vdots\\\
y_{b}&z_{b}\end{bmatrix}\quad\text{and}\quad\tilde{\mathcal{X}}_{n}=\begin{bmatrix}y_{a}&z_{a}\\\
\vdots&\vdots\\\ y_{a}&z_{a}\\\ y_{a}&z_{a}\\\ y_{b}&z_{b}\\\ y_{b}&z_{b}\\\
\vdots&\vdots\\\ y_{b}&z_{b}\end{bmatrix}.$

The indices displayed above are $1,\dots,k-2,k-1,k,k+1,\dots 2k$, and it is
clear that $d_{\mathrm{ham}}(\mathcal{X}_{n},\tilde{\mathcal{X}}_{n})=1$. We
further consider the permutation $\bm{\pi}$ which permutes only the $k-1$ and
$k$ entries, _i.e._ , $\bm{\pi}=(1,2,\ldots,k-2,k,k-1,k+1,\ldots,n)$, so that

$\displaystyle\mathcal{X}_{n}^{\bm{\pi}}=\begin{bmatrix}y_{a}&z_{a}\\\
\vdots&\vdots\\\ y_{a}&z_{a}\\\ y_{a}&z_{a}\\\ y_{a}&z_{a}\\\ y_{b}&z_{b}\\\
\vdots&\vdots\\\
y_{b}&z_{b}\end{bmatrix}\quad\text{and}\quad\tilde{\mathcal{X}}_{n}^{\bm{\pi}}=\begin{bmatrix}y_{a}&z_{a}\\\
\vdots&\vdots\\\ y_{a}&z_{a}\\\ y_{a}&z_{b}\\\ y_{b}&z_{a}\\\ y_{b}&z_{b}\\\
\vdots&\vdots\\\ y_{b}&z_{b}\end{bmatrix}.$

We now compute the U-statistic of the HSIC based on these two permuted
datasets. Unfortunately, a direct computation of $U_{\mathrm{HSIC}}$ requires
a complicated case-by-case analysis. Instead, we consider the following trick
to simplify calculations. First of all, we pretend that $(y_{a},z_{a})$ and
$(y_{b},z_{b})$ take some specific values, say $(y_{a},z_{a})=(1,1)$ and
$(y_{b},z_{b})=(0,0)$, and consider indicator kernels
$k(y,y^{\prime})=K\times\mathds{1}(y=y^{\prime})$ and
$\ell(z,z^{\prime})=L\times\mathds{1}(z=z^{\prime})$. Under this simplified
setting, $U_{\mathrm{HSIC}}$ is essentially the statistic considered in Kim et
al., (2023, Proposition 1) for multinomial data, which can be computed in a
straightforward manner. In addition, we observe that $U_{\mathrm{HSIC}}$ based
on the indicator kernels remains the same as $U_{\mathrm{HSIC}}$ based on
generic kernels $k$ and $\ell$ up to some quantities tending to zero as
$\epsilon_{1},\epsilon_{2}\rightarrow 0$. Using this trick along with the
observation that $k(y,y)=K$ and $\ell(z,z)=L$ for all $y\in\mathbb{Y}$ and
$z\in\mathbb{Z}$, it can be seen that for all $k\geq 2$

$\displaystyle
U_{\mathrm{HSIC}}(\mathcal{X}_{n}^{\bm{\pi}})=\frac{k(k-1)}{(2k-1)(2k-3)}KL+C_{1}\epsilon_{1}+C_{2}\epsilon_{2}+C_{3}\epsilon_{1}\epsilon_{2},$

where $C_{1},C_{2},C_{3}$ are constants that only depend on $K,L,n$. A similar
calculation yields

$\displaystyle
U_{\mathrm{HSIC}}(\tilde{\mathcal{X}}_{n}^{\bm{\pi}})~{}=~{}\frac{(k-2)(k^{2}-4k+1)}{(k-1)(2k-1)(2k-3)}KL+C_{1}^{\prime}\epsilon_{1}+C_{2}^{\prime}\epsilon_{2}+C_{3}^{\prime}\epsilon_{1}\epsilon_{2},$

where $C_{1}^{\prime},C_{2}^{\prime},C_{3}^{\prime}$ are constants that only
depend on $K,L,n$. From these results, we deduce that

$\displaystyle
U_{\mathrm{HSIC}}(\mathcal{X}_{n}^{\bm{\pi}})-U_{\mathrm{HSIC}}(\tilde{\mathcal{X}}_{n}^{\bm{\pi}})$
$\displaystyle=~{}$
$\displaystyle\left(\frac{2}{k-1}-\frac{1}{2k-1}-\frac{1}{2k-3}\right)KL+(C_{1}-C_{1}^{\prime})\epsilon_{1}+(C_{2}-C_{2}^{\prime})\epsilon_{2}+(C_{3}-C_{3}^{\prime})\epsilon_{1}\epsilon_{2}$
$\displaystyle\overset{(\star)}{\to}~{}$
$\displaystyle\left(\frac{2}{k-1}-\frac{1}{2k-1}-\frac{1}{2k-3}\right)KL\geq\frac{KL}{k}$

where convergence ($\star$) holds as $\epsilon_{1},\epsilon_{2}\rightarrow 0$
for each fixed $K,L,n$, and the last inequality holds for all $k\geq 2$.
Therefore, by letting $k=n/2\geq 2$, it holds that

$\displaystyle\sup_{\bm{\pi}\in\bm{\Pi}_{n}}\sup_{\begin{subarray}{c}\mathcal{X}_{n},\tilde{\mathcal{X}}_{n}:\\\
d_{\mathrm{ham}}(\mathcal{X}_{n},\tilde{\mathcal{X}}_{n})\leq
1\end{subarray}}\bigl{|}U_{\mathrm{HSIC}}(\mathcal{X}_{n}^{\bm{\pi}})-U_{\mathrm{HSIC}}(\tilde{\mathcal{X}}_{n}^{\bm{\pi}})\bigr{|}\geq\frac{2KL}{n}.$

##### Sensitivity lower bound for $n=2k+1$ odd.

We now consider the same two datasets as in the even case but with an
additional row consisting of $(y_{b},z_{b})$:

$\displaystyle\mathcal{X}_{n}=\begin{bmatrix}y_{a}&z_{a}\\\ \vdots&\vdots\\\
y_{a}&z_{a}\\\ y_{a}&z_{a}\\\ y_{a}&z_{a}\\\ y_{b}&z_{b}\\\ \vdots&\vdots\\\
y_{b}&z_{b}\\\
y_{b}&z_{b}\end{bmatrix}\quad\text{and}\quad\tilde{\mathcal{X}}_{n}=\begin{bmatrix}y_{a}&z_{a}\\\
\vdots&\vdots\\\ y_{a}&z_{a}\\\ y_{a}&z_{a}\\\ y_{b}&z_{b}\\\ y_{b}&z_{b}\\\
\vdots&\vdots\\\ y_{b}&z_{b}\\\ y_{b}&z_{b}\end{bmatrix},$

where the indices displayed are $1,\dots,k-2,k-1,k,k+1,\dots 2k,2k+1$. As
before, we indeed have
$d_{\mathrm{ham}}(\mathcal{X}_{n},\tilde{\mathcal{X}}_{n})=1$. Once again, we
consider the permutation $\bm{\pi}$ which permutes only the $k-1$ and $k$
entries, which leads to

$\displaystyle\mathcal{X}_{n}^{\bm{\pi}}=\begin{bmatrix}y_{a}&z_{a}\\\
\vdots&\vdots\\\ y_{a}&z_{a}\\\ y_{a}&z_{a}\\\ y_{a}&z_{a}\\\ y_{b}&z_{b}\\\
\vdots&\vdots\\\ y_{b}&z_{b}\\\
y_{b}&z_{b}\end{bmatrix}\quad\text{and}\quad\tilde{\mathcal{X}}_{n}^{\bm{\pi}}=\begin{bmatrix}y_{a}&z_{a}\\\
\vdots&\vdots\\\ y_{a}&z_{a}\\\ y_{a}&z_{b}\\\ y_{b}&z_{a}\\\ y_{b}&z_{b}\\\
\vdots&\vdots\\\ y_{b}&z_{b}\\\ y_{b}&z_{b}\end{bmatrix}.$

To compute $U_{\mathrm{HSIC}}(\mathcal{X}_{n}^{\bm{\pi}})$ and
$U_{\mathrm{HSIC}}(\tilde{\mathcal{X}}_{n}^{\bm{\pi}})$, we use the trick
considered in the even case, and find that

$\displaystyle
U_{\mathrm{HSIC}}(\mathcal{X}_{n}^{\bm{\pi}})~{}=~{}\frac{k(k+1)}{4k^{2}-1}KL+C_{1}\epsilon_{1}+C_{2}\epsilon_{2}+C_{3}\epsilon_{1}\epsilon_{2}$

and

$\displaystyle
U_{\mathrm{HSIC}}(\tilde{\mathcal{X}}_{n}^{\bm{\pi}})~{}=~{}\frac{(k+1)(k-2)(k^{2}-3k-2)}{k(k-1)(2k-1)(2k+1)}KL+C_{1}^{\prime}\epsilon_{1}+C_{2}^{\prime}\epsilon_{2}+C_{3}^{\prime}\epsilon_{1}\epsilon_{2},$

where $C_{1},\ldots,C_{3}^{\prime}$ are constants that only depend on $K,L,n$.
As a result, we have

$\displaystyle
U_{\mathrm{HSIC}}(\mathcal{X}_{n}^{\bm{\pi}})-U_{\mathrm{HSIC}}(\tilde{\mathcal{X}}_{n}^{\bm{\pi}})$
$\displaystyle~{}=~{}\frac{4(k^{3}-2k+1)}{k(k-1)(4k^{2}-1)}KL+(C_{1}-C_{1}^{\prime})\epsilon_{1}+(C_{2}-C_{2}^{\prime})\epsilon_{2}+(C_{3}-C_{3}^{\prime})\epsilon_{1}\epsilon_{2}$
$\displaystyle~{}\overset{(\star)}{\to}~{}\frac{4(k^{3}-2k+1)}{k(k-1)(4k^{2}-1)}KL\geq\frac{2}{2k+1}KL,$

where convergence ($\star$) holds as $\epsilon_{1},\epsilon_{2}\rightarrow 0$
for each fixed $K,L,n$, and the last inequality holds for all $k\geq 2$.
Therefore we conclude that

$\displaystyle\sup_{\bm{\pi}\in\bm{\Pi}_{n}}\sup_{\begin{subarray}{c}\mathcal{X}_{n},\tilde{\mathcal{X}}_{n}:\\\
d_{\mathrm{ham}}(\mathcal{X}_{n},\tilde{\mathcal{X}}_{n})\leq
1\end{subarray}}\bigl{|}U_{\mathrm{HSIC}}(\mathcal{X}_{n}^{\bm{\pi}})-U_{\mathrm{HSIC}}(\tilde{\mathcal{X}}_{n}^{\bm{\pi}})\bigr{|}\geq\frac{2KL}{n},$

for any $n\geq 4$ (either even or odd). This completes the derivation of the
lower bound on the sensitivity of the HSIC U-statistic. Together with the
upper bound (52), this verifies the claim of Lemma 9.

###  F.7 Proof of Theorem 15

Let us write the V-statistic of HSIC as

$\displaystyle V_{\mathrm{HSIC}}~{}=~{}$
$\displaystyle\frac{1}{n^{2}}\sum_{i,j=1}^{n}k(Y_{i},Y_{j})\ell(Z_{i},Z_{j})+\frac{1}{n^{4}}\sum_{i_{1},i_{2},j_{1},j_{2}=1}^{n}k(Y_{i_{1}},Y_{j_{1}})\ell(Z_{i_{2}},Z_{j_{2}})$
$\displaystyle-$
$\displaystyle\frac{2}{n^{3}}\sum_{i,j_{1},j_{2}=1}^{n}k(Y_{i},Y_{j_{1}})\ell(Z_{i},Z_{j_{2}})$
$\displaystyle=~{}$ $\displaystyle
V_{\mathrm{HSIC},a}+V_{\mathrm{HSIC},b}-2V_{\mathrm{HSIC},c},$

which is equivalent to the square of $\widehat{\mathrm{HSIC}}$. Using the
bounded kernel property, it can be seen that

$\displaystyle\max\Big{\\{}|U_{\mathrm{HSIC},a}-V_{\mathrm{HSIC},a}|,\
|U_{\mathrm{HSIC},b}-V_{\mathrm{HSIC},b}|,\
|U_{\mathrm{HSIC},c}-V_{\mathrm{HSIC},c}|\Big{\\}}\leq C_{1}\frac{KL}{n}$

for some constant $C_{1}>0$, which leads to

$\displaystyle|U_{\mathrm{HSIC}}-V_{\mathrm{HSIC}}|\leq C_{2}\frac{KL}{n}.$

Again, $C_{2}$ is some positive number. By treating $K$ and $L$ as some fixed
numbers, we also note that Lemma 14 yields

$\displaystyle
V_{\mathrm{HSIC}}=\big{\\{}\mathrm{HSIC}_{k\otimes\ell}(P_{YZ})+R_{n}\big{\\}}^{2}\quad\text{where
$R_{n}=O_{P}(n^{-1/2})$.}$

Having these ingredients in place, we can essentially follow the same proof
strategy as for Theorem 10 and conclude that

$\displaystyle\limsup_{n\rightarrow\infty}\inf_{P\in\mathcal{P}_{\mathrm{HSIC}_{k\otimes\ell}}\\!(\rho)}\mathbb{E}_{P_{YZ}}[\phi_{\mathrm{dpHSIC}}^{u}]\leq\alpha.$

This completes the proof of Theorem 15.

###  F.8 Proof of Theorem 16

Let us denote by $C_{1},C_{2},\ldots$ constants that may depend on
$\alpha,\beta,R,M,d_{Y},d_{Z}$. Following the proofs of Theorem 4 and Theorem
14 along with the sensitivity result for $U_{\mathrm{HSIC}}$ in Lemma 9, we
may arrive at the point where the type II error of
$\phi_{\mathrm{dpHSIC}}^{u}$ is upper bounded as

$\displaystyle\mathbb{E}[1-\phi_{\mathrm{dpHSIC}}^{u}]\leq\mathbb{P}\biggl{(}U_{\mathrm{HSIC}}\leq\frac{C_{1}}{n\sqrt{\lambda_{1}\cdots\lambda_{d_{Y}}\mu_{1}\cdots\mu_{d_{Z}}}}+\frac{C_{2}}{n\lambda_{1}\cdots\lambda_{d_{Y}}\mu_{1}\cdots\mu_{d_{Z}}\xi_{\varepsilon,\delta}}\biggr{)}+\frac{15}{16}\beta$

We then use the proofs of Albert et al., (2022, Theorem 1) and Albert et al.,
(2022, Theorem 2), and show that the probability term in the above display is
less than or equal to $\beta/16$ once

$\displaystyle\|\psi\|_{L_{2}}^{2}~{}\geq~{}C_{3}\Biggl{\\{}\sum_{i=1}^{d_{Y}}\lambda_{i}^{2s}+\sum_{i=1}^{d_{Z}}\mu_{i}^{2s}$
$\displaystyle+\frac{1}{n\sqrt{\lambda_{1}\cdots\lambda_{d_{Y}}\mu_{1}\cdots\mu_{d_{Z}}}}+\frac{1}{n\lambda_{1}\cdots\lambda_{d_{Y}}\mu_{1}\cdots\mu_{d_{Z}}\xi_{\varepsilon,\delta}}\Bigg{\\}}.$

This proves Theorem 11.

##  Appendix G Technical Lemmas

This section collects some technical lemmas used in the main proofs. The first
lemma from Kim, (2021) provides an exponential concentration inequality for
the permuted MMD statistic with kernel $k$.

######  Lemma 10 (Theorem 5.1 of Kim, 2021).

Consider two samples $Y_{1},\ldots,Y_{n}$ and $Z_{1},\ldots,Z_{m}$ and write
$\\{X_{1},\ldots,X_{N}\\}=\\{Y_{1},\ldots,Y_{n},Z_{1},\ldots,Z_{m}\\}$. Let us
further write $\widetilde{k}(x,y)=k(x,x)+k(y,y)-2k(x,y)$ and
$\gamma=nm/(n+m)^{2}$. Define

$\displaystyle\widehat{\sigma}^{2}=\frac{1}{N(N-1)}\sum_{(i,j)\in\bm{i}_{2}^{N}}\widetilde{k}(X_{i},X_{j}).$

Then for all $t>0$,

$\displaystyle\mathbb{P}_{\bm{\pi}}\Biggl{[}\sup_{f\in\mathcal{F}_{k}}\biggl{(}\frac{1}{n}\sum_{i=1}^{n}f(X_{\pi_{i}})-\frac{1}{m}\sum_{i=1}^{m}f(X_{\pi_{i+n}})\biggr{)}\geq
t+\sqrt{\frac{\widehat{\sigma}^{2}}{2N\gamma}}\ \Bigg{|}\
X_{1},\ldots,X_{N}\Biggr{]}\leq\exp\biggl{(}-\frac{N\gamma^{2}t^{2}}{2\widehat{\sigma}^{2}}\biggr{)}.$

An exponential tail decay in the above comes at a price — it requires that $n$
and $m$ are well-balanced in the sense that $N\gamma^{2}$ is large. Thus it
can be used to show that
$\widehat{\mathrm{MMD}}(\mathcal{X}_{n+m}^{\bm{\pi}})=o_{P}(1)$ under the
limited regime where $N\gamma^{2}\rightarrow\infty$. The lemma below removes
this unnecessary constraint at the expense of having a polynomial tail decay.

######  Lemma 11 (Markov for the Permuted MMD).

Under the setting of Lemma 10 with $N=n+m$, we have

$\displaystyle\mathbb{P}\Biggl{[}\sup_{f\in\mathcal{F}_{k}}\biggl{(}\frac{1}{n}\sum_{i=1}^{n}f(X_{\pi_{i}})-\frac{1}{m}\sum_{i=1}^{m}f(X_{\pi_{i+n}})\biggr{)}\geq
t\Biggr{]}\leq\frac{2K}{nt^{2}}\quad\text{for all $t>0$.}$

Hence $\widehat{\mathrm{MMD}}(\mathcal{X}_{n+m}^{\bm{\pi}})=o_{P}(1)$,
provided that $Kn^{-1}\rightarrow 0$.

###### Proof.

Markov’s inequality together with the V-statistic representation of the
empirical MMD yields that for any $t>0$

$\displaystyle\mathbb{P}\Biggl{[}\sup_{f\in\mathcal{F}_{k}}\biggl{(}\frac{1}{n}\sum_{i=1}^{n}f(X_{\pi_{i}})-\frac{1}{m}\sum_{i=1}^{m}f(X_{\pi_{i+n}})\biggr{)}\geq
t\Biggr{]}$ $\displaystyle\leq~{}$
$\displaystyle\frac{1}{t^{2}}\biggl{\\{}\underbrace{\frac{1}{n^{2}}\sum_{i,j=1}^{n}\mathbb{E}[k(X_{\pi_{i}},X_{\pi_{j}})]}_{\mathrm{(I)}}+\underbrace{\frac{1}{m^{2}}\sum_{i,j=1}^{m}\mathbb{E}[k(X_{\pi_{i+n}},X_{\pi_{j+n}})]}_{\mathrm{(II)}}-\underbrace{\frac{2}{nm}\sum_{i=1}^{n}\sum_{j=1}^{m}\mathbb{E}[k(X_{\pi_{i}},X_{\pi_{j+n}})]}_{\mathrm{(III)}}\biggr{\\}}.$

Exploiting the uniformity of permutation $\bm{\pi}$, we analyze the terms (I),
(II) and (III), separately. The analyses of the first two terms (I) and (II)
are similar, and we note that

$\displaystyle\mathbb{E}[k(X_{\pi_{i}},X_{\pi_{i}})]=\mathbb{E}[k(X_{\pi_{i+n}},X_{\pi_{i+n}})]~{}=~{}$
$\displaystyle\frac{1}{N}\sum_{i=1}^{n}\mathbb{E}[k(Y_{i},Y_{i})]+\frac{1}{N}\sum_{j=1}^{m}\mathbb{E}[k(Z_{j},Z_{j})]$
$\displaystyle=~{}$
$\displaystyle\frac{n}{N}\mathbb{E}[k(Y_{1},Y_{1})]+\frac{m}{N}\mathbb{E}[k(Z_{1},Z_{1})]$

and for $i\neq j$,

$\displaystyle\mathbb{E}[k(X_{\pi_{i}},X_{\pi_{j}})]=\mathbb{E}[k(X_{\pi_{i+n}},X_{\pi_{j+n}})]$
$\displaystyle=~{}$
$\displaystyle\frac{1}{N(N-1)}\biggl{\\{}\sum_{(i,j)\in\bm{i}_{2}^{n}}\mathbb{E}[k(Y_{i},Y_{j})]+\sum_{(i,j)\in\bm{i}_{2}^{m}}\mathbb{E}[k(Z_{i},Z_{j})]+2\sum_{i=1}^{n}\sum_{j=1}^{m}\mathbb{E}[k(Y_{i},Z_{j})]\bigg{\\}}$
$\displaystyle=~{}$
$\displaystyle\frac{n(n-1)}{N(N-1)}\mathbb{E}[k(Y_{1},Y_{2})]+\frac{m(m-1)}{N(N-1)}\mathbb{E}[k(Z_{1},Z_{2})]+\frac{2nm}{N(N-1)}\mathbb{E}[k(Y_{1},Z_{1})].$

Therefore

$\displaystyle\mathrm{(I)}~{}=~{}$
$\displaystyle\frac{n}{nN}\mathbb{E}[k(Y_{1},Y_{1})]+\frac{m}{nN}\mathbb{E}[k(Z_{1},Z_{1})]$
$\displaystyle+~{}$
$\displaystyle\frac{n-1}{n}\biggl{\\{}\frac{n(n-1)}{N(N-1)}\mathbb{E}[k(Y_{1},Y_{2})]+\frac{m(m-1)}{N(N-1)}\mathbb{E}[k(Z_{1},Z_{2})]+\frac{2nm}{N(N-1)}\mathbb{E}[k(Y_{1},Z_{1})]\biggr{\\}}$

and

$\displaystyle\mathrm{(II)}~{}=~{}$
$\displaystyle\frac{n}{mN}\mathbb{E}[k(Y_{1},Y_{1})]+\frac{m}{mN}\mathbb{E}[k(Z_{1},Z_{1})]$
$\displaystyle+~{}$
$\displaystyle\frac{m-1}{m}\biggl{\\{}\frac{n(n-1)}{N(N-1)}\mathbb{E}[k(Y_{1},Y_{2})]+\frac{m(m-1)}{N(N-1)}\mathbb{E}[k(Z_{1},Z_{2})]+\frac{2nm}{N(N-1)}\mathbb{E}[k(Y_{1},Z_{1})]\biggr{\\}}.$

On the other hand, the last term (III) is

$\displaystyle\mathrm{(III)}~{}=~{}$
$\displaystyle\frac{2n(n-1)}{N(N-1)}\mathbb{E}[k(Y_{1},Y_{2})]+\frac{2m(m-1)}{N(N-1)}\mathbb{E}[k(Z_{1},Z_{2})]+\frac{4nm}{N(N-1)}\mathbb{E}[k(Y_{1},Z_{1})].$

Given that kernel $k$ is non-negative and bounded by $K$, we can upper bound
$\mathrm{(I)}+\mathrm{(II)}-\mathrm{(III)}$ as

$\displaystyle\mathrm{(I)}+\mathrm{(II)}-\mathrm{(III)}~{}\leq~{}$
$\displaystyle\biggl{(}\frac{n}{nN}+\frac{m}{nN}+\frac{n}{mN}+\frac{m}{mN}\biggr{)}K=\frac{n+m}{nm}K$
$\displaystyle\leq~{}$ $\displaystyle\frac{2K}{n}.$

Hence the result follows. ∎

The lemma below presents a concentration bound for the permuted HSIC
statistic. It is worth noting that obtaining the logarithmic dependence on
$\alpha$ is non-trivial, and thus we highlight it as our contribution.

######  Lemma 12 (Concentration Inequality for Permuted HSIC).

Assume that the kernels $k$ and $\ell$ are bounded as $0\leq
k(y,y^{\prime})\leq K$ and $0\leq\ell(z,z^{\prime})\leq L$ for all
$y,y^{\prime}\in\mathbb{Y}$ and $z,z^{\prime}\in\mathbb{Z}$. Then for any
$\alpha\in(0,1)$,

$\displaystyle\mathbb{P}_{\bm{\pi}}\biggl{(}\widehat{\mathrm{HSIC}}(\mathcal{X}_{n}^{\bm{\pi}})\geq
C\sqrt{\frac{KL}{n}}\max\bigg{\\{}\log^{1/4}\biggl{(}\frac{1}{\alpha}\biggr{)},\log^{1/2}\biggl{(}\frac{1}{\alpha}\biggr{)},1\bigg{\\}}\,\bigg{|}\,\mathcal{X}_{n}\biggr{)}\leq\alpha,$

where $C$ is some positive constant.

###### Proof.

The proof is based on Kim et al., 2022a (, Theorem 6.2) that establishes an
exponential tail bound for a permuted U-statistic of HSIC. Given
$\mathcal{X}_{n}^{\bm{\pi}}$, let us denote the permuted U-statistic by

$\displaystyle U_{\bm{\pi},\mathrm{HSIC}}~{}=~{}$
$\displaystyle\frac{(n-2)!}{n!}\sum_{(i,j)\in\bm{i}_{2}^{n}}k(Y_{i},Y_{j})\ell(Z_{\pi_{i}},Z_{\pi_{j}})+\frac{(n-4)!}{n!}\sum_{(i_{1},i_{2},j_{1},j_{2})\in\bm{i}_{4}^{n}}k(Y_{i_{1}},Y_{j_{1}})\ell(Z_{\pi_{i_{2}}},Z_{\pi_{j_{2}}})$
$\displaystyle-$
$\displaystyle\frac{2(n-3)!}{n!}\sum_{(i,j_{1},j_{2})\in\bm{i}_{3}^{n}}k(Y_{i},Y_{j_{1}})\ell(Z_{\pi_{i}},Z_{\pi_{j_{2}}}),$

where $\bm{i}_{m}^{n}$ stands for the set of all $m$-tuples drawn from $[n]$
without replacement. Kim et al., 2022a (, Theorem 6.2) shows that
$U_{\bm{\pi},\mathrm{HSIC}}$ satisfies

$\displaystyle\mathbb{P}_{\bm{\pi}}\bigl{(}U_{\bm{\pi},\mathrm{HSIC}}\geq
t\,|\,\mathcal{X}_{n}\bigr{)}\leq\exp\bigg{\\{}\\!-C_{1}\min\biggl{(}\frac{t^{2}}{\Sigma_{n}^{2}},\
\frac{t}{\Sigma_{n}}\biggr{)}\bigg{\\}}\quad\text{for all $t>0$,}$

where

$\displaystyle\Sigma_{n}^{2}=\frac{1}{n^{2}(n-1)^{2}}\sup_{\bm{\pi}\in\bm{\Pi}_{n}}\Biggl{\\{}\sum_{(i,j)\in\bm{i}_{2}^{n}}k^{2}(Y_{i},Y_{j})\ell^{2}(Z_{\pi_{i}},Z_{\pi_{j}})\Bigg{\\}}\leq\frac{1}{n(n-1)}K^{2}L^{2}.$

The inequality above holds under the assumption that $k$ and $\ell$ are
uniformly bounded by $K$ and $L$. Therefore, under the assumption of Lemma 12,

$\displaystyle\mathbb{P}_{\bm{\pi}}\bigl{(}U_{\bm{\pi},\mathrm{HSIC}}\geq
t\,|\,\mathcal{X}_{n}\bigr{)}\leq\exp\bigg{\\{}\\!-C_{2}\min\biggl{(}\frac{n^{2}t^{2}}{K^{2}L^{2}},\
\frac{nt}{KL}\biggr{)}\bigg{\\}}\quad\text{for all $t>0$.}$ (53)

On the other hand, the squared empirical HSIC can be written in the form of a
V-statistic given as

$\displaystyle\widehat{\mathrm{HSIC}}^{2}(\mathcal{X}_{n}^{\bm{\pi}})~{}=~{}$
$\displaystyle\frac{1}{n^{2}}\sum_{i,j=1}^{n}k(Y_{i},Y_{j})\ell(Z_{\pi_{i}},Z_{\pi_{j}})+\frac{1}{n^{4}}\sum_{i_{1},i_{2},j_{1},j_{2}=1}^{n}k(Y_{i_{1}},Y_{j_{1}})\ell(Z_{\pi_{i_{2}}},Z_{\pi_{j_{2}}})$
$\displaystyle-$
$\displaystyle\frac{2}{n^{3}}\sum_{i,j_{1},j_{2}=1}^{n}k(Y_{i},Y_{j_{1}})\ell(Z_{\pi_{i}},Z_{\pi_{j_{2}}}),$

and we note that the difference between the U-statistic and the V-statistic is
bounded as

$\displaystyle\big{|}U_{\bm{\pi},\mathrm{HSIC}}-\widehat{\mathrm{HSIC}}^{2}(\mathcal{X}_{n}^{\bm{\pi}})\big{|}$
$\displaystyle\leq~{}$
$\displaystyle\bigg{|}\frac{(n-2)!}{n!}\sum_{(i,j)\in\bm{i}_{2}^{n}}k(Y_{i},Y_{j})\ell(Z_{\pi_{i}},Z_{\pi_{j}})-\frac{1}{n^{2}}\sum_{i,j=1}^{n}k(Y_{i},Y_{j})\ell(Z_{\pi_{i}},Z_{\pi_{j}})\bigg{|}$
$\displaystyle+~{}$
$\displaystyle\bigg{|}\frac{(n-4)!}{n!}\sum_{(i_{1},i_{2},j_{1},j_{2})\in\bm{i}_{4}^{n}}k(Y_{i_{1}},Y_{j_{1}})\ell(Z_{\pi_{i_{2}}},Z_{\pi_{j_{2}}})-\frac{1}{n^{4}}\sum_{i_{1},i_{2},j_{1},j_{2}=1}^{n}k(Y_{i_{1}},Y_{j_{1}})\ell(Z_{\pi_{i_{2}}},Z_{\pi_{j_{2}}})\bigg{|}$
$\displaystyle+~{}$
$\displaystyle\bigg{|}\frac{2(n-3)!}{n!}\sum_{(i,j_{1},j_{2})\in\bm{i}_{3}^{n}}k(Y_{i},Y_{j_{1}})\ell(Z_{\pi_{i}},Z_{\pi_{j_{2}}})-\frac{2}{n^{3}}\sum_{i,j_{1},j_{2}=1}^{n}k(Y_{i},Y_{j_{1}})\ell(Z_{\pi_{i}},Z_{\pi_{j_{2}}})\bigg{|}$
$\displaystyle\leq~{}$ $\displaystyle C_{3}\frac{KL}{n},$ (54)

for any $\bm{\pi}$ and $\mathcal{X}_{n}$. Using the above bound (54) and
letting $t>0$, we convert the concentration inequality for the permuted
empirical HSIC into that for the permuted U-statistic as

$\displaystyle\mathbb{P}_{\bm{\pi}}\bigl{(}\widehat{\mathrm{HSIC}}(\mathcal{X}_{n}^{\bm{\pi}})\geq
t\,|\,\mathcal{X}_{n}\bigr{)}~{}=~{}$
$\displaystyle\mathbb{P}_{\bm{\pi}}\bigl{(}\widehat{\mathrm{HSIC}}^{2}(\mathcal{X}_{n}^{\bm{\pi}})\geq
t^{2}\,|\,\mathcal{X}_{n}\bigr{)}$ $\displaystyle=~{}$
$\displaystyle\mathbb{P}_{\bm{\pi}}\biggl{(}\widehat{\mathrm{HSIC}}^{2}(\mathcal{X}_{n}^{\bm{\pi}})-U_{\bm{\pi},\mathrm{HSIC}}+U_{\bm{\pi},\mathrm{HSIC}}\geq
t^{2}\,|\,\mathcal{X}_{n}\biggr{)}$ $\displaystyle\leq~{}$
$\displaystyle\mathbb{P}_{\bm{\pi}}\bigl{(}\big{|}\widehat{\mathrm{HSIC}}^{2}(\mathcal{X}_{n}^{\bm{\pi}})-U_{\bm{\pi},\mathrm{HSIC}}\big{|}+U_{\bm{\pi},\mathrm{HSIC}}\geq
t^{2}\,|\,\mathcal{X}_{n}\bigr{)}$
$\displaystyle\overset{\mathrm{(i)}}{\leq}~{}$
$\displaystyle\mathbb{P}_{\bm{\pi}}\biggl{(}U_{\bm{\pi},\mathrm{HSIC}}\geq
t^{2}-C_{3}\frac{KL}{n}\,|\,\mathcal{X}_{n}\biggr{)}$
$\displaystyle\overset{\mathrm{(ii)}}{\leq}~{}$
$\displaystyle\mathbb{P}_{\bm{\pi}}\biggl{(}U_{\bm{\pi},\mathrm{HSIC}}\geq\frac{t^{2}}{2}\,|\,\mathcal{X}_{n}\biggr{)}$
$\displaystyle\overset{\mathrm{(iii)}}{\leq}~{}$
$\displaystyle\exp\bigg{\\{}\\!-C_{4}\min\biggl{(}\frac{n^{2}t^{4}}{K^{2}L^{2}},\
\frac{nt^{2}}{KL}\biggr{)}\bigg{\\}}$

where step (i) uses the bound (54), step (ii) assumes that $t^{2}\geq
2C_{3}\frac{KL}{n}$ and step (iii) follows by concentration inequality (53).
Setting the last exponential bound to $\alpha$ and solving for $t$ yield the
desired result. ∎

We recall the concentration inequality of the empirical MMD presented by
Gretton et al., (2012), which has been used in various places throughout the
paper.

######  Lemma 13 (Theorem 7 of Gretton et al., 2012).

Assume that the kernel $k$ is bounded as $0\leq k(x,y)\leq K$ for all
$x,y\in\mathbb{S}$. Then for any $t>0$

$\displaystyle\mathbb{P}\biggl{\\{}\bigg{|}\widehat{\mathrm{MMD}}(\mathcal{X}_{n+m})-\mathrm{MMD}_{k}(P,Q)\bigg{|}>2\biggl{(}\sqrt{\frac{K}{m}}+\sqrt{\frac{K}{n}}\biggr{)}+t\biggr{\\}}\leq
2\exp\biggl{(}-\frac{t^{2}mn}{2K(m+n)}\biggr{)}.$

The following is a counterpart to Lemma 13 for the empirical HSIC. While
similar results exist in the literature (e.g., Gretton et al.,, 2005, Theorem
3), none precisely align with our specific requirements. Hence we opt to
present a detailed proof of the following result.

######  Lemma 14 (Exponential Inequality for the Empirical HSIC).

Assume that the kernels $k$ and $\ell$ are bounded as $0\leq
k(y,y^{\prime})\leq K$ and $0\leq\ell(z,z^{\prime})\leq L$ for all
$y,y^{\prime}\in\mathbb{Y}$ and $z,z^{\prime}\in\mathbb{Z}$. Then for any
$t\geq 0$,

$\displaystyle\mathbb{P}\biggl{\\{}\big{|}\widehat{\mathrm{HSIC}}(\mathcal{X}_{n})-\mathrm{HSIC}_{k\otimes\ell}(P_{YZ})\big{|}\geq
C_{1}\sqrt{\frac{KL}{n}}+t\bigg{\\}}\leq
2\exp\biggl{(}-\frac{C_{2}t^{2}n}{KL}\biggr{)},$

where $C_{1},C_{2}$ are positive constants.

###### Proof.

Throughout the proof, we denote by $C_{1},C_{2},\ldots$ some generic positive
constants. By Lemma 6, the empirical HSIC has global sensitivity at most
$C_{1}\sqrt{KL}/n$. Thus an application of McDiarmid’s inequality (Gretton et
al.,, 2012, Theorem 29) yields

$\displaystyle\mathbb{P}\bigl{\\{}\big{|}\widehat{\mathrm{HSIC}}(\mathcal{X}_{n})-\mathbb{E}\bigl{[}\widehat{\mathrm{HSIC}}(\mathcal{X}_{n})\bigr{]}\big{|}\geq
t\big{\\}}\leq 2\exp\biggl{(}-\frac{C_{2}t^{2}n}{KL}\biggr{)}\quad\text{for
all $t\geq 0$.}$ (55)

Now we bound the difference between the expectation of
$\widehat{\mathrm{HSIC}}(\mathcal{X}_{n})$ and the population HSIC as

$\displaystyle\big{|}\mathbb{E}\bigl{[}\widehat{\mathrm{HSIC}}(\mathcal{X}_{n})\bigr{]}-\mathrm{HSIC}_{k\otimes\ell}(P_{YZ})\big{|}$
$\displaystyle=~{}$
$\displaystyle\bigg{|}\mathbb{E}\biggl{[}\sup_{f\in\mathcal{F}_{k\otimes\ell}}\bigg{\\{}\frac{1}{n}\sum_{i=1}^{n}f(Y_{i},Z_{i})-\frac{1}{n^{2}}\sum_{i,j=1}^{n}f(Y_{i},Z_{j})\bigg{\\}}\biggr{]}-\sup_{f\in\mathcal{F}_{k\otimes\ell}}\big{\\{}\mathbb{E}_{P_{YZ}}[f(Y,Z)]-\mathbb{E}_{P_{Y}P_{Z}}[f(Y,Z)]\big{\\}}\bigg{|}$
$\displaystyle\overset{\mathrm{(i)}}{\leq}~{}$
$\displaystyle\mathbb{E}\bigg{|}\sup_{f\in\mathcal{F}_{k\otimes\ell}}\bigg{\\{}\frac{1}{n}\sum_{i=1}^{n}f(Y_{i},Z_{i})-\frac{1}{n^{2}}\sum_{i,j=1}^{n}f(Y_{i},Z_{j})\bigg{\\}}-\sup_{f\in\mathcal{F}_{k\otimes\ell}}\big{\\{}\mathbb{E}_{P_{YZ}}[f(Y,Z)]-\mathbb{E}_{P_{Y}P_{Z}}[f(Y,Z)]\big{\\}}\bigg{|}$
$\displaystyle\overset{\mathrm{(ii)}}{\leq}~{}$
$\displaystyle\mathbb{E}\bigg{|}\sup_{f\in\mathcal{F}_{k\otimes\ell}}\bigg{\\{}\frac{1}{n}\sum_{i=1}^{n}f(Y_{i},Z_{i})-\mathbb{E}_{P_{YZ}}[f(Y,Z)]-\frac{1}{n^{2}}\sum_{i,j=1}^{n}f(Y_{i},Z_{j})+\mathbb{E}_{P_{Y}P_{Z}}[f(Y,Z)]\bigg{\\}}\bigg{|}$
$\displaystyle\overset{\mathrm{(iii)}}{\leq}~{}$
$\displaystyle\underbrace{\mathbb{E}\sup_{f\in\mathcal{F}_{k\otimes\ell}}\bigg{|}\frac{1}{n}\sum_{i=1}^{n}f(Y_{i},Z_{i})-\mathbb{E}_{P_{YZ}}[f(Y,Z)]\bigg{|}}_{\coloneqq\mathrm{(I)}}+\underbrace{\mathbb{E}\sup_{f\in\mathcal{F}_{k\otimes\ell}}\bigg{|}\frac{1}{n^{2}}\sum_{i,j=1}^{n}f(Y_{i},Z_{j})-\mathbb{E}_{P_{Y}P_{Z}}[f(Y,Z)]\bigg{|}}_{\coloneqq\mathrm{(II)}},$

where step (i) uses Jensen’s inequality, step (ii) uses the reverse triangle
inequality and step (iii) follows by the triangle inequality. Let
$\\{(\tilde{Y}_{i},\tilde{Z}_{i})\\}_{i=1}^{n}$ be i.i.d. copies of
$(Y_{1},Z_{1})$, and $\\{\epsilon_{i}\\}_{i=1}^{n}$ be i.i.d. Rademacher
random variables. Then Jensen’s inequality in conjunction with symmetrization
yields

$\displaystyle\mathrm{(I)}~{}\leq~{}$
$\displaystyle\mathbb{E}\sup_{f\in\mathcal{F}_{k\otimes\ell}}\bigg{|}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}\big{\\{}f(Y_{i},Z_{i})-f(\tilde{Y}_{i},\tilde{Z}_{i})\big{\\}}\bigg{|}$
$\displaystyle\leq~{}$ $\displaystyle
2\mathbb{E}\sup_{f\in\mathcal{F}_{k\otimes\ell}}\bigg{|}\frac{1}{n}\sum_{i=1}^{n}\epsilon_{i}f(Y_{i},Z_{i})\bigg{|}~{}\leq~{}2\sqrt{\frac{KL}{n}},$
(56)

where the last inequality is due to Bartlett and Mendelson, (2002, Lemma 22).
For the second term,

$\displaystyle\mathrm{(II)}~{}\overset{(\mathrm{i})}{\leq}~{}$
$\displaystyle\frac{1}{n}\sum_{j=1}^{n}\mathbb{E}\sup_{f\in\mathcal{F}_{k\otimes\ell}}\bigg{|}\frac{1}{n}\sum_{i=1}^{n}f(Y_{i},Z_{j})-\mathbb{E}_{P_{Y}P_{Z}}[f(Y,Z)]\bigg{|}$
$\displaystyle=~{}$
$\displaystyle\mathbb{E}\sup_{f\in\mathcal{F}_{k\otimes\ell}}\bigg{|}\frac{1}{n}\sum_{i=2}^{n}f(Y_{i},Z_{1})+\frac{f(Y_{1},Z_{1})}{n}-\mathbb{E}_{P_{Y}P_{Z}}[f(Y,Z)]\bigg{|}$
$\displaystyle\overset{(\mathrm{ii})}{\leq}~{}$
$\displaystyle\mathbb{E}\sup_{f\in\mathcal{F}_{k\otimes\ell}}\bigg{|}\frac{1}{n}\sum_{i=2}^{n}f(Y_{i},Z_{1})-\mathbb{E}_{P_{Y}P_{Z}}[f(Y,Z)]\bigg{|}+\frac{1}{n}\mathbb{E}\sup_{f\in\mathcal{F}_{k\otimes\ell}}|f(Y_{1},Z_{1})|$
$\displaystyle\overset{(\mathrm{iii})}{\leq}~{}$
$\displaystyle\mathbb{E}\sup_{f\in\mathcal{F}_{k\otimes\ell}}\bigg{|}\frac{1}{n-1}\sum_{i=2}^{n}f(Y_{i},Z_{1})-\mathbb{E}_{P_{Y}P_{Z}}[f(Y,Z)]\bigg{|}$
$\displaystyle+\frac{1}{n(n-1)}\sum_{i=2}^{n}\mathbb{E}\sup_{f\in\mathcal{F}_{k\otimes\ell}}|f(Y_{i},Z_{1})|+\frac{1}{n}\mathbb{E}\sup_{f\in\mathcal{F}_{k\otimes\ell}}|f(Y_{1},Z_{1})|,$

where step (i) follows by Jensen’s inequality and step (ii) and step (iii) use
the triangle inequality. Let $\mathcal{H}_{k\otimes\ell}$ be the reproducing
kernel Hilbert space with the product kernel $k\otimes\ell$. Then by the
reproducing property and the Cauchy–Schwarz inequality, we have

$\displaystyle\sup_{f\in\mathcal{F}_{k\otimes\ell}}|f(y,z)|=\sup_{f\in\mathcal{F}_{k\otimes\ell}}|\langle
k(\cdot,y)\ell(\cdot,z),f\rangle_{\mathcal{H}_{k\otimes\ell}}|\leq\sqrt{k(y,y)\ell(z,z)}\sup_{f\in\mathcal{F}_{k\otimes\ell}}\|f\|_{\mathcal{H}_{k\otimes\ell}}\leq\sqrt{KL}$

for all $y\in\mathbb{Y},z\in\mathbb{Z}$. Using this inequality and letting
$\\{(\tilde{Y}_{i},\tilde{Z}_{1})\\}_{i=2}^{n}$ be i.i.d. copies of
$\\{(Y_{i},Z_{1})\\}_{i=2}^{n}$ and recalling that
$\\{\epsilon_{i}\\}_{i=1}^{n}$ are i.i.d. Rademacher random variables, the
second term can be further bounded by

$\displaystyle\mathrm{(II)}~{}\leq~{}$
$\displaystyle\mathbb{E}\sup_{f\in\mathcal{F}_{k\otimes\ell}}\bigg{|}\frac{1}{n-1}\sum_{i=2}^{n}f(Y_{i},Z_{1})-\mathbb{E}_{P_{Y}P_{Z}}[f(Y,Z)]\bigg{|}+\frac{2\sqrt{KL}}{n}$
$\displaystyle=~{}$
$\displaystyle\mathbb{E}\sup_{f\in\mathcal{F}_{k\otimes\ell}}\bigg{|}\frac{1}{n-1}\sum_{i=2}^{n}f(Y_{i},Z_{1})-\frac{1}{n-1}\sum_{i=2}^{n}\mathbb{E}[f(\tilde{Y}_{i},\tilde{Z}_{1})]\bigg{|}+\frac{2\sqrt{KL}}{n}$
(57) $\displaystyle\leq~{}$
$\displaystyle\mathbb{E}\sup_{f\in\mathcal{F}_{k\otimes\ell}}\bigg{|}\frac{1}{n-1}\sum_{i=2}^{n}f(Y_{i},Z_{1})-f(\tilde{Y}_{i},\tilde{Z}_{1})\bigg{|}+\frac{2\sqrt{KL}}{n}$
$\displaystyle=~{}$
$\displaystyle\mathbb{E}\biggl{\\{}\mathbb{E}\biggl{[}\sup_{f\in\mathcal{F}_{k\otimes\ell}}\bigg{|}\frac{1}{n-1}\sum_{i=2}^{n}\epsilon_{i}\\{f(Y_{i},Z_{1})-f(\tilde{Y}_{i},\tilde{Z}_{1})\\}\bigg{|}\,\Big{|}\,Z_{1},\tilde{Z}_{1}\biggr{]}\biggr{\\}}+\frac{2\sqrt{KL}}{n}$
(58) $\displaystyle\leq~{}$ $\displaystyle
2\mathbb{E}\biggl{\\{}\mathbb{E}\biggl{[}\sup_{f\in\mathcal{F}_{k\otimes\ell}}\bigg{|}\frac{1}{n-1}\sum_{i=2}^{n}\epsilon_{i}f(Y_{i},Z_{1})\bigg{|}\,\Big{|}\,Z_{1}\biggr{]}\biggr{\\}}+\frac{2\sqrt{KL}}{n}$
$\displaystyle\leq~{}$ $\displaystyle
2\sqrt{\frac{KL}{n-1}}+\frac{2\sqrt{KL}}{n},$ (59)

where the last inequality is due to Bartlett and Mendelson, (2002, Lemma 22).
Putting the inequalities (56) and (59) together, we have

$\displaystyle\big{|}\mathbb{E}\bigl{[}\widehat{\mathrm{HSIC}}(\mathcal{X}_{n})\bigr{]}-\mathrm{HSIC}_{k\otimes\ell}(P_{YZ})\big{|}\leq
C_{3}\sqrt{\frac{KL}{n}}.$

The above inequality along with McDiarmid’s inequality (55) yields

$\displaystyle\mathbb{P}\biggl{\\{}\big{|}\widehat{\mathrm{HSIC}}(\mathcal{X}_{n})-\mathrm{HSIC}_{k\otimes\ell}(P_{YZ})\big{|}\geq
t+C_{3}\sqrt{\frac{KL}{n}}\bigg{\\}}\leq
2\exp\biggl{(}-\frac{C_{2}t^{2}n}{KL}\biggr{)}\quad\text{for all $t\geq 0$.}$

Hence we complete the proof of Lemma 14. ∎

The below lemma is folklore in the literature (_e.g._ , Romano and Wolf,,
2005, Lemma 1) where we recall $\lfloor x\rfloor$ denotes the largest integer
smaller than or equal to $x$. We provide a proof for completeness.

######  Lemma 15 (Permutation $p$-value).

Suppose that $X_{1},\ldots,X_{n},X_{n+1}$ are exchangeable random variables.
Then for any $\alpha\in[0,1]$, it holds that

$\displaystyle\mathbb{P}\biggl{(}\frac{1}{n+1}\bigg{\\{}\sum_{i=1}^{n}\mathds{1}(X_{n+1}\leq
X_{i})+1\bigg{\\}}\leq\alpha\biggr{)}\leq\frac{\lfloor(n+1)\alpha\rfloor}{n+1}\leq\alpha.$

Suppose further that $X_{1},\ldots,X_{n+1}$ are all distinct with probability
one. Then

$\displaystyle\mathbb{P}\biggl{(}\frac{1}{n+1}\bigg{\\{}\sum_{i=1}^{n}\mathds{1}(X_{n+1}\leq
X_{i})+1\bigg{\\}}\leq\alpha\biggr{)}=\frac{\lfloor(n+1)\alpha\rfloor}{n+1}.$

###### Proof.

Let $X_{(1)}\leq X_{(2)}\leq\ldots\leq X_{(n+1)}$ be the order statistics of
$X_{1},\ldots,X_{n+1}$. Then we have a series of the identities:

$\displaystyle\frac{1}{n+1}\bigg{\\{}\sum_{i=1}^{n}\mathds{1}(X_{n+1}\leq
X_{i})+1\bigg{\\}}=\frac{1}{n+1}\sum_{i=1}^{n+1}\mathds{1}(X_{n+1}\leq
X_{i})\leq\alpha$ $\displaystyle\Longleftrightarrow~{}$
$\displaystyle\sum_{i=1}^{n+1}\mathds{1}(X_{n+1}\leq
X_{i})\leq\lfloor(n+1)\alpha\rfloor$ $\displaystyle\Longleftrightarrow~{}$
$\displaystyle\sum_{i=1}^{n+1}\mathds{1}(X_{i}<X_{n+1})\geq(n+1)-\lfloor(n+1)\alpha\rfloor\coloneqq
k$ $\displaystyle\Longleftrightarrow~{}$ $\displaystyle X_{n+1}>X_{(k)}.$

Now by the exchangeability condition, we have

$\displaystyle\mathbb{P}(X_{n+1}>X_{(k)})~{}=~{}$
$\displaystyle\mathbb{E}\bigg{[}\frac{1}{n+1}\sum_{i=1}^{n+1}\mathds{1}(X_{i}>X_{(k)})\bigg{]}.$

On the other hand, by the definition of $X_{(k)}$,

$\displaystyle\frac{1}{n+1}\sum_{i=1}^{n+1}\mathds{1}(X_{i}>X_{(k)})\leq\frac{n+1-k}{n+1}=\frac{\lfloor(n+1)\alpha\rfloor}{n+1}.$

Hence the first result follows. When $X_{1},\ldots,X_{n+1}$ are all distinct,
observe

$\displaystyle\sum_{i=1}^{n+1}\mathds{1}(X_{i}>X_{(k)})=n+1-k.$

Thus

$\displaystyle\mathbb{E}\bigg{[}\frac{1}{n+1}\sum_{i=1}^{n+1}\mathds{1}(X_{i}>X_{(k)})\bigg{]}=\frac{n+1-k}{n+1}=\frac{\lfloor(n+1)\alpha\rfloor}{n+1}.$

∎

The permutation test is often slightly conservative due to its discrete
nature. The following randomization trick is well-known in the literature
(e.g., Lehmann and Romano,, 2005, Chapter 15), which modifies the permutation
test to have type I error exactly equal to $\alpha$.

######  Lemma 16 (Randomized Tests).

For given $\alpha\in(0,1)$ and $\gamma\in(0,\alpha]$, consider a test function
$\phi$ such that $\mathbb{P}_{H_{0}}(\phi=1)=\gamma\leq\alpha$. Letting $U$ be
a uniform random variable on $[0,1]$ independent of $\phi$, define a
randomized test $\phi_{\mathrm{rand}}$ as

$\displaystyle\phi_{\mathrm{rand}}=\phi+(1-\phi)\times\mathds{1}\biggl{(}U\leq\frac{\alpha-\gamma}{1-\gamma}\biggr{)}.$

The randomized test $\phi_{\mathrm{rand}}$ has type I error exactly equal to
$\alpha$, and power never worse than that of $\phi$, _i.e._ ,
$\mathbb{P}_{H_{0}}(\phi_{\mathrm{rand}}=1)=\alpha$ and
$\mathbb{P}_{H_{1}}(\phi_{\mathrm{rand}}=1)\geq\mathbb{P}_{H_{1}}(\phi=1)$.

###### Proof.

Type I error control is immediate given that

$\displaystyle\mathbb{E}_{H_{0}}[\phi_{\mathrm{rand}}]~{}=~{}$
$\displaystyle\mathbb{E}_{H_{0}}[\phi]+\mathbb{E}_{H_{0}}[1-\phi]\times\mathbb{P}_{H_{0}}\biggl{(}U\leq\frac{\alpha-\gamma}{1-\gamma}\biggr{)}$
$\displaystyle=~{}$
$\displaystyle\gamma+(1-\gamma)\times\frac{\alpha-\gamma}{1-\gamma}=\alpha.$

The second claim about the power is also immediate given that
$\phi_{\mathrm{rand}}\geq\phi$. ∎

The permutation test can be expressed in terms of the permutation $p$-value as
well as the quantile of the permutation distribution, which can be justified
by the following lemma.

######  Lemma 17 (Quantile Representation).

For any $\alpha\in[0,1]$ and dataset $\\{X_{1},\ldots,X_{n+1}\\}$, we have the
identity

$\displaystyle\mathds{1}\biggl{(}\frac{1}{n+1}\bigg{\\{}\sum_{i=1}^{n}\mathds{1}(X_{n+1}\leq
X_{i})+1\bigg{\\}}\leq\alpha\biggr{)}=\mathds{1}\bigl{(}X_{n+1}>q_{1-\alpha}\bigr{)},$

where $q_{1-\alpha}$ is the $1-\alpha$ quantile of
$\\{X_{1},\ldots,X_{n+1}\\}$ given as

$\displaystyle q_{1-\alpha}=$
$\displaystyle\inf\biggl{\\{}t\in\mathbb{R}:\frac{1}{n+1}\sum_{i=1}^{n+1}\mathds{1}(X_{i}\leq
t)\geq 1-\alpha\biggr{\\}}.$

Moreover, by letting $X_{(\lceil(1-\alpha)(n+1)\rceil)}$ denote the
$\lceil(1-\alpha)(n+1)\rceil$th order statistic of $X_{1},\ldots,X_{n+1}$ and
$X_{(0)}=-\infty$, we have $q_{1-\alpha}=X_{(\lceil(1-\alpha)(n+1)\rceil)}$.

###### Proof.

The second claim follows by noting that

$\displaystyle q_{1-\alpha}~{}=~{}$
$\displaystyle\inf\biggl{\\{}t\in\mathbb{R}:\frac{1}{n+1}\sum_{i=1}^{n+1}\mathds{1}(X_{i}\leq
t)\geq 1-\alpha\biggr{\\}}$ $\displaystyle=~{}$
$\displaystyle\inf\biggl{\\{}t\in\mathbb{R}:\frac{1}{n+1}\sum_{i=1}^{n+1}\mathds{1}(X_{i}<t)\geq
1-\alpha\biggr{\\}}$ (60) $\displaystyle=~{}$
$\displaystyle\inf\biggl{\\{}t\in\mathbb{R}:\sum_{i=1}^{n+1}\mathds{1}(X_{i}<t)\geq(1-\alpha)(n+1)\biggr{\\}}$
$\displaystyle=~{}$ $\displaystyle X_{(\lceil(1-\alpha)(n+1)\rceil)}.$

For the first claim, denote $G(x)=\sum_{i=1}^{n+1}\mathds{1}(X_{i}<x)$, which
is a left-continuous step function. We then have

$\displaystyle\mathds{1}\biggl{(}\frac{1}{n+1}\bigg{\\{}\sum_{i=1}^{n}\mathds{1}(X_{n+1}\leq
X_{i})+1\bigg{\\}}\leq\alpha\biggr{)}~{}=~{}$
$\displaystyle\mathds{1}\bigl{(}G(X_{n+1})\geq(1-\alpha)(n+1)\bigr{)}$
$\displaystyle\leq~{}$ $\displaystyle\mathds{1}(X_{n+1}>q_{1-\alpha})$

where the last step follows since $G$ is a left-continuous step function. In
more detail, suppose that $G(X_{n+1})\geq(1-\alpha)(n+1)$. Since $G$ is a
left-continuous step function, there exists a small constant $\epsilon>0$ such
that $G(X_{n+1}-\epsilon)=G(X_{n+1})\geq(1-\alpha)(n+1)$. Therefore, $X_{n+1}$
cannot be the $1-\alpha$ quantile and should be greater than $q_{1-\alpha}$.

Moreover, the event $X_{n+1}>q_{1-\alpha}$ implies that
$G(X_{n+1})\geq(1-\alpha)(n+1)$ by the definition of $q_{1-\alpha}$ as in
expression (60). Hence we conclude that

$\displaystyle\mathds{1}\bigl{(}G(X_{n+1})\geq(1-\alpha)(n+1)\bigr{)}~{}=~{}\mathds{1}(X_{n+1}>q_{1-\alpha}),$

and the first claim follows. ∎

The next lemma plays a crucial role in proving the validity of the
differentially private permutation test in Algorithm 1.

######  Lemma 18 (Alternative Expression).

Given $\alpha\in(0,1)$ and $n\geq 1$, set

$\displaystyle\alpha_{\star}=\max\bigg{\\{}\biggl{(}\frac{n+1}{n}\alpha-\frac{1}{n}\biggr{)},\,0\bigg{\\}}.$

Then for dataset $\\{X_{1},\ldots,X_{n+1}\\}$, we have the identity

$\displaystyle\mathds{1}(X_{n+1}>q_{1-\alpha})=\mathds{1}(X_{n+1}>r_{1-\alpha_{\star}})\mathds{1}\biggl{(}\alpha\geq\frac{1}{n+1}\biggr{)},$

where $q_{1-\alpha}$ and $r_{1-\alpha_{\star}}$ are the $1-\alpha$ quantile of
$\\{X_{i}\\}_{i=1}^{n+1}$ and the $1-\alpha_{\star}$ quantile of
$\\{X_{i}\\}_{i=1}^{n}$, respectively.

###### Proof.

For $\alpha\in(0,\frac{1}{n+1})$, $q_{1-\alpha}$ becomes the maximum of
$X_{1},\ldots,X_{n+1}$ for which $\mathds{1}(X_{n+1}>q_{1-\alpha})=0$.
Similarly, it becomes

$\displaystyle\mathds{1}(X_{n+1}>r_{1-\alpha_{\star}})\mathds{1}\biggl{(}\alpha\geq\frac{1}{n+1}\biggr{)}=0.$

Hence we only need to verify the identity under $\alpha\geq\frac{1}{n+1}$. In
what follows, we assume $\alpha\geq\frac{1}{n+1}$ and show that
$\mathds{1}(X_{n+1}>q_{1-\alpha})=\mathds{1}(X_{n+1}>r_{1-\alpha_{\star}})$.

Remark that the $1-\alpha$ quantile of $\\{X_{1}+c,\ldots,X_{n+1}+c\\}$ is the
same as the $1-\alpha$ quantile of $\\{X_{1},\ldots,X_{n+1}\\}$ plus $c$ for
any $c\in\mathbb{R}$. Using this location-shift property of quantiles, observe
that

$\displaystyle\mathds{1}(X_{n+1}>q_{1-\alpha})~{}=~{}$
$\displaystyle\mathds{1}\biggl{(}0>\inf\biggl{\\{}x\in\mathbb{R}:\frac{1}{n+1}\sum_{i=1}^{n+1}\mathds{1}(X_{i}-X_{n+1}\leq
x)\geq 1-\alpha\biggr{\\}}\biggr{)}$ $\displaystyle=~{}$
$\displaystyle\mathds{1}\biggl{(}0>\inf\biggl{\\{}x\in\mathbb{R}:\frac{1}{n}\sum_{i=1}^{n}\mathds{1}(X_{i}-X_{n+1}\leq
x)\geq\frac{n+1}{n}(1-\alpha)-\frac{\mathds{1}(0\leq
x)}{n}\biggr{\\}}\biggr{)}$ $\displaystyle\geq~{}$
$\displaystyle\mathds{1}\biggl{(}0>\inf\biggl{\\{}x\in\mathbb{R}:\frac{1}{n}\sum_{i=1}^{n}\mathds{1}(X_{i}-X_{n+1}\leq
x)\geq\frac{n+1}{n}(1-\alpha)\biggr{\\}}\biggr{)}$
$\displaystyle\overset{(\dagger)}{=}~{}$
$\displaystyle\mathds{1}\biggl{(}0>\inf\biggl{\\{}x\in\mathbb{R}:\frac{1}{n}\sum_{i=1}^{n}\mathds{1}(X_{i}-X_{n+1}\leq
x)\geq\min\biggl{[}\frac{n+1}{n}(1-\alpha),\,1\biggr{]}\biggr{\\}}\biggr{)}$
$\displaystyle=~{}$ $\displaystyle\mathds{1}(X_{n+1}>r_{1-\alpha_{\star}}).$

where the equality ($\dagger$) holds under $\alpha\geq\frac{1}{n+1}$.
Therefore it holds that
$\mathds{1}(X_{n+1}>q_{1-\alpha})\geq\mathds{1}(X_{n+1}>r_{1-\alpha_{\star}})$.

Next we prove the other direction
$\mathds{1}(X_{n+1}>q_{1-\alpha})\leq\mathds{1}(X_{n+1}>r_{1-\alpha_{\star}})$.
Note that the infimum in the definition of a quantile can be replaced by the
minimum so that

$\displaystyle\frac{1}{n+1}\sum_{i=1}^{n+1}\mathds{1}(X_{i}-X_{n+1}\leq\underbrace{q_{1-\alpha}-X_{n+1}}_{\coloneqq\tilde{q}_{1-\alpha}})\geq
1-\alpha.$

Having this in mind, for $\alpha\geq\frac{1}{n+1}$, assume
$X_{n+1}>q_{1-\alpha}$ (equivalently $0>\tilde{q}_{1-\alpha}$) under which it
holds that

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\mathds{1}(X_{i}-X_{n+1}\leq\tilde{q}_{1-\alpha})\geq\frac{n+1}{n}(1-\alpha)-\frac{\mathds{1}(0\leq\tilde{q}_{1-\alpha})}{n}=\frac{n+1}{n}(1-\alpha)$
$\displaystyle\Longleftrightarrow~{}$
$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\mathds{1}(X_{i}-X_{n+1}\leq\tilde{q}_{1-\alpha})\geq\min\biggl{\\{}\frac{n+1}{n}(1-\alpha),\,1\biggr{\\}}.$

This implies that $\tilde{q}_{1-\alpha}\geq
r_{1-\alpha_{\star}}-X_{n+1}\coloneqq\tilde{r}_{1-\alpha_{\star}}$ by the
definition of $r_{1-\alpha_{\star}}$. Consequently,
$\mathds{1}(X_{n+1}>q_{1-\alpha})\leq\mathds{1}(\tilde{q}_{1-\alpha}\geq\tilde{r}_{1-\alpha_{\star}})$,
which further implies that

$\displaystyle\mathds{1}(X_{n+1}>q_{1-\alpha})\leq\mathds{1}(\tilde{q}_{1-\alpha}\geq\tilde{r}_{1-\alpha_{\star}})\mathds{1}(X_{n+1}>q_{1-\alpha})\leq\mathds{1}(0>\tilde{r}_{1-\alpha_{\star}})=\mathds{1}(X_{n+1}>r_{1-\alpha_{\star}}).$

Thus we conclude that
$\mathds{1}(X_{n+1}>q_{1-\alpha})=\mathds{1}(X_{n+1}>r_{1-\alpha_{\star}})$
for $\alpha\geq\frac{1}{n+1}$ as well. This completes the proof of Lemma 18. ∎

The next result is concerned with the global sensitivity of the quantiles.

######  Lemma 19 (Sensitivity of Quantiles).

Suppose that the test statistic $T$ has the global sensitivity at most
$\Delta_{T}$ as in (4). Let us denote by
$r_{1-\alpha}\bigl{(}\mathcal{X}_{n};\\{\bm{\pi}_{i},\zeta_{i}\\}_{i=1}^{B}\bigr{)}$
the $1-\alpha$ quantile of $\\{M_{i}\\}_{i=1}^{B}$ where
$M_{i}=T(\mathcal{X}_{n}^{\bm{\pi}_{i}})+2\Delta_{T}\xi_{\varepsilon,\delta}^{-1}\zeta_{i}$
with $\xi_{\varepsilon,\delta}=\varepsilon+\log(1/(1-\delta))$ and
$\zeta_{i}\overset{\mathrm{i.i.d.}}{\sim}\mathsf{Laplace}(0,1)$ for $i\in[B]$.
Then for any $\alpha\in[0,1)$, the global sensitivity of the $1-\alpha$
quantile satisfies

$\displaystyle\sup_{\begin{subarray}{c}\mathcal{X}_{n},\tilde{\mathcal{X}}_{n}:\\\
d_{\mathrm{ham}}(\mathcal{X}_{n},\tilde{\mathcal{X}}_{n})\leq
1\end{subarray}}\big{|}r_{1-\alpha}\bigl{(}\mathcal{X}_{n};\\{\bm{\pi}_{i},\zeta_{i}\\}_{i=1}^{B}\bigr{)}-r_{1-\alpha}\bigl{(}\tilde{\mathcal{X}}_{n};\\{\bm{\pi}_{i},\zeta_{i}\\}_{i=1}^{B}\bigr{)}\big{|}~{}\leq~{}\Delta_{T},$

for any permutations $\bm{\pi}_{1},\ldots,\bm{\pi}_{B}$ and any
$\zeta_{1},\ldots,\zeta_{B}\overset{\mathrm{i.i.d.}}{\sim}\mathsf{Laplace}(0,1)$.

###### Proof.

Let $\tilde{\mathcal{X}}_{n}$ be a neighboring dataset of $\mathcal{X}_{n}$
where $\tilde{\mathcal{X}}_{n}$ and $\mathcal{X}_{n}$ differ only in their
$k$th component for some $k\in[n]$. Denote the permuted test statistics
computed on
$\tilde{\mathcal{X}}_{n}^{\bm{\pi}_{1}},\ldots,\tilde{\mathcal{X}}_{n}^{\bm{\pi}_{B}}$
by $\tilde{T}_{1},\ldots,\tilde{T}_{B}$. For simplicity, we write
$r_{1-\alpha}=r_{1-\alpha}\bigl{(}\mathcal{X}_{n};\\{\bm{\pi}_{i},\zeta_{i}\\}_{i=1}^{B}\bigr{)}$
and
$\tilde{r}_{1-\alpha}=r_{1-\alpha}\bigl{(}\tilde{\mathcal{X}}_{n};\\{\bm{\pi}_{i},\zeta_{i}\\}_{i=1}^{B}\bigr{)}$.
Having this notation, first note that $T_{i}\geq\tilde{T}_{i}-\Delta_{T}$ for
all $i\in[B]$ under the assumption of (4) and thus

$\displaystyle{1-\alpha}\leq\frac{1}{B}\sum_{i=1}^{B}\mathds{1}(T_{i}+2\Delta_{T}\xi_{\varepsilon,\delta}^{-1}\zeta_{i}\leq
r_{1-\alpha})\leq\frac{1}{B}\sum_{i=1}^{B}\mathds{1}(\tilde{T}_{i}+2\Delta_{T}\xi_{\varepsilon,\delta}^{-1}\zeta_{i}\leq
r_{1-\alpha}+\Delta_{T}),$

which implies that $\tilde{r}_{1-\alpha}\leq r_{1-\alpha}+\Delta_{T}$.

Next we argue that $\tilde{r}_{1-\alpha}\geq r_{1-\alpha}-\Delta_{T}$. For
this direction, let $\epsilon>0$ be an arbitrary constant. Then by the
definition of $r_{1-\alpha}$ and $T_{i}\leq\tilde{T}_{i}+\Delta_{T}$ for all
$i\in[B]$,

$\displaystyle{1-\alpha}>\frac{1}{B}\sum_{i=1}^{B}\mathds{1}(T_{i}+2\Delta_{T}\xi_{\varepsilon,\delta}^{-1}\zeta_{i}\leq
r_{1-\alpha}-\epsilon)\geq\frac{1}{B}\sum_{i=1}^{B}\mathds{1}(\tilde{T}_{i}+2\Delta_{T}\xi_{\varepsilon,\delta}^{-1}\zeta_{i}\leq
r_{1-\alpha}-\epsilon-\Delta_{T}).$

Hence $\tilde{r}_{1-\alpha}>r_{1-\alpha}-\epsilon-\Delta_{T}$. Since
$\epsilon$ is arbitrary, we conclude $\tilde{r}_{1-\alpha}\geq
r_{1-\alpha}-\Delta_{T}$. In summary, we have established that
$|r_{1-\alpha}-\tilde{r}_{1-\alpha}|\leq\Delta_{T}$, which holds for any
$k\in[n]$, any permutations $\bm{\pi}_{1},\ldots,\bm{\pi}_{B}$ and any
$\zeta_{1},\ldots,\zeta_{B}\overset{\mathrm{i.i.d.}}{\sim}\mathsf{Laplace}(0,1)$.
Therefore, the desired claim follows. ∎

The Laplace mechanism introduces a perturbed statistic by adding Laplace
noise. Instead of directly studying quantiles of this perturbed statistic, it
is often easier to analyze the quantiles of the original statistic and the
quantiles of the added Laplace noise separately. These results can then be
combined using the following quantile inequality.

######  Lemma 20 (Quantile Inequality).

Let $q_{1-\alpha}^{X+Y}$ be the $1-\alpha$ quantile of $X+Y$. Similarly, let
$q_{1-\alpha/2}^{X}$ and $q_{1-\alpha/2}^{Y}$ be the $1-\alpha/2$ quantile of
$X$ and $Y$, respectively. Then $q_{1-\alpha}^{X+Y}\leq
q_{1-\alpha/2}^{X}+q_{1-\alpha/2}^{Y}$.

###### Proof.

Note that if $\\{X+Y>q_{1-\alpha/2}^{X}+q_{1-\alpha/2}^{Y}\\}$, then at least
one of the events $\\{X>q_{1-\alpha/2}^{X}\\}$ and
$\\{Y>q_{1-\alpha/2}^{Y}\\}$ should occur (otherwise contradiction). This
together with the union bound yields

$\displaystyle\mathbb{P}\bigl{(}X+Y>q_{1-\alpha/2}^{X}+q_{1-\alpha/2}^{Y}\bigr{)}~{}\leq~{}$
$\displaystyle\mathbb{P}\bigl{(}X>q_{1-\alpha/2}^{X}\bigr{)}+\mathbb{P}\bigl{(}Y>q_{1-\alpha/2}^{Y}\bigr{)}$
$\displaystyle\leq~{}$ $\displaystyle\alpha,$

where the last inequality follows by the definition of quantile. The above
implies that the $1-\alpha$ quantile of $X+Y$ is less than or equal to
$q_{1-\alpha/2}^{X}+q_{1-\alpha/2}^{Y}$ and therefore the claim follows. ∎

The following lemma computes the difference between the V-statistic and
U-statistic of the squared HSIC, which is useful in the proof of Theorem 14.

######  Lemma 21 (Difference between $V_{\mathrm{HSIC}}$ and
$U_{\mathrm{HSIC}}$).

Recall $\widehat{\mathrm{HSIC}}^{2}$ given in (12) and $U_{\mathrm{HSIC}}$
given in (21). Suppose that kernels satisfy $k(y,y)=K$ and $\ell(z,z)=L$ for
all $y\in\mathbb{Y}$ and $z\in\mathbb{Z}$. Then the difference between
$\widehat{\mathrm{HSIC}}^{2}$ and $U_{\mathrm{HSIC}}$ is computed as follows:

$\displaystyle\widehat{\mathrm{HSIC}}^{2}-U_{\mathrm{HSIC}}=D_{1}+D_{2},$

where

$\displaystyle D_{1}~{}=~{}$
$\displaystyle\frac{n-1}{n^{2}}KL-\frac{L}{n^{3}}\sum_{(i,j)\in\mathbf{i}_{2}^{n}}k(Y_{i},Y_{j})-\frac{K}{n^{3}}\sum_{(i,j)\in\mathbf{i}_{2}^{n}}\ell(Z_{i},Z_{j})$
$\displaystyle D_{2}~{}=~{}$
$\displaystyle-\frac{3n^{2}-4n+2}{(n-1)n^{4}}\sum_{(i,j)\in\mathbf{i}_{2}^{n}}k(Y_{i},Y_{j})\ell(Z_{i},Z_{j})+\frac{2(5n^{2}-8n+4)}{n^{4}(n-1)(n-2)}\sum_{(i,j_{1},j_{2})\in\mathbf{i}_{3}^{n}}k(Y_{i},Y_{j_{1}})\ell(Z_{i},Z_{j_{2}})$
$\displaystyle-\frac{6n^{2}-11n+6}{n^{4}(n-1)(n-2)(n-3)}\sum_{(i_{1},i_{2},j_{1},j_{2})\in\mathbf{i}_{4}^{n}}k(Y_{i_{1}},Y_{i_{2}})\ell(Z_{j_{1}},Z_{j_{2}}).$

_Remark._ _The term $D_{1}$ is invariant to any permutation of either $Y$
values or $Z$ values._

###### Proof.

Write the squared empirical HSIC in (12) as $V_{\mathrm{HSIC}}$ and the
U-statistic of the squared HSIC as $U_{\mathrm{HSIC}}$. Note that
$V_{\mathrm{HSIC}}=V_{a}+V_{b}-2V_{c}$ where

$\displaystyle
V_{a}~{}=~{}\frac{1}{n^{2}}\sum_{i,j=1}^{n}k(Y_{i},Y_{j})\ell(Z_{i},Z_{j}),\quad
V_{b}~{}=~{}\frac{1}{n^{4}}\sum_{i_{1},i_{2},j_{1},j_{2}=1}^{n}k(Y_{i_{1}},Y_{i_{2}})\ell(Z_{j_{1}},Z_{j_{2}}),$
$\displaystyle
V_{c}~{}=~{}\frac{1}{n^{3}}\sum_{i,j_{1},j_{2}=1}^{n}k(Y_{i},Y_{j_{1}})\ell(Z_{i},Z_{j_{2}}),$

and each term can be expressed as

$\displaystyle V_{a}~{}=~{}$
$\displaystyle\frac{KL}{n}+\frac{1}{n^{2}}\sum_{(i,j)\in\mathbf{i}_{2}^{n}}k(Y_{i},Y_{j})\ell(Z_{i},Z_{j}),$
$\displaystyle V_{b}~{}=~{}$
$\displaystyle\frac{KL}{n^{3}}+\frac{2K}{n^{4}}\sum_{(i,j)\in\mathbf{i}_{2}^{n}}\ell(Z_{i},Z_{j})+\frac{2L}{n^{4}}\sum_{(i,j)\in\mathbf{i}_{2}^{n}}k(Y_{i},Y_{j})+\frac{KLn(n-1)}{n^{4}}$
$\displaystyle+~{}$
$\displaystyle\frac{K(n-2)}{n^{4}}\sum_{(i,j)\in\mathbf{i}_{2}^{n}}\ell(Z_{i},Z_{j})+\frac{L(n-2)}{n^{4}}\sum_{(i,j)\in\mathbf{i}_{2}^{n}}k(Y_{i},Y_{j})$
$\displaystyle+~{}$
$\displaystyle\frac{2}{n^{4}}\sum_{(i,j)\in\mathbf{i}_{2}^{n}}k(Y_{i},Y_{j})\ell(Z_{i},Z_{j})+\frac{4}{n^{4}}\sum_{(i,j_{1},j_{2})\in\mathbf{i}_{3}^{n}}k(Y_{i},Y_{j_{1}})\ell(Z_{i},Z_{j_{2}})$
$\displaystyle+~{}$
$\displaystyle\frac{1}{n^{4}}\sum_{(i_{1},i_{2},j_{1},j_{2})\in\mathbf{i}_{3}^{n}}k(Y_{i_{1}},Y_{i_{2}})\ell(Z_{j_{1}},Z_{j_{2}})\quad\text{and}$
$\displaystyle V_{c}~{}=~{}$
$\displaystyle\frac{KL}{n^{2}}+\frac{K}{n^{3}}\sum_{(i,j)\in\mathbf{i}_{2}^{n}}\ell(Z_{i},Z_{j})+\frac{L}{n^{3}}\sum_{(i,j)\in\mathbf{i}_{2}^{n}}k(Y_{i},Y_{j})$
$\displaystyle+~{}$
$\displaystyle\frac{1}{n^{3}}\sum_{(i,j)\in\mathbf{i}_{2}^{n}}k(Y_{i},Y_{j})\ell(Z_{i},Z_{j})+\frac{1}{n^{3}}\sum_{(i,j_{1},j_{2})\in\mathbf{i}_{3}^{n}}k(Y_{i},Y_{j_{1}})\ell(Z_{i},Z_{j_{2}}).$

Note also that $U_{\mathrm{HSIC}}$ can be written as
$U_{\mathrm{HSIC}}=U_{a}+U_{b}-2U_{c}$ where

$\displaystyle U_{a}~{}=~{}$
$\displaystyle\frac{1}{n(n-1)}\sum_{(i,j)\in\mathbf{i}_{2}^{n}}k(Y_{i},Y_{j})\ell(Z_{i},Z_{j}),$
$\displaystyle U_{b}~{}=~{}$
$\displaystyle\frac{(n-4)!}{n!}\sum_{(i_{1},i_{2},j_{1},j_{2})\in\mathbf{i}_{4}^{n}}k(Y_{i_{1}},Y_{j_{1}})\ell(Z_{i_{2}},Z_{j_{2}})\quad\text{and}$
$\displaystyle U_{c}~{}=~{}$
$\displaystyle\frac{1}{n(n-1)(n-2)}\sum_{(i,j_{1},j_{2})\in\mathbf{i}_{3}^{n}}k(Y_{i},Y_{j_{1}})\ell(Z_{i},Z_{j_{2}}).$

The result follows by calculating $V_{a}-U_{a}$, $V_{b}-U_{b}$ and
$-2V_{c}+2U_{c}$, and simplifying their sum via algebra. ∎