$\displaystyle\lesssim_{M}\lVert\Sigma_{X}\rVert_{F}^{2}\lVert\Sigma_{Y}\rVert_{F}^{2}\lVert\Sigma_{XY}\rVert_{F}^{2}.$

  * •

By taking expectation with respect to $Z_{2},Z_{3}$, we have

$\displaystyle\mathbb{E}(Z_{1}^{\top}G_{[12]}Z_{1}-\operatorname{tr}(G_{[12]}))^{2}(Z_{2}^{\top}H_{[11]}Z_{1})(Z_{3}^{\top}H_{[11]}Z_{1})(Z_{2}^{\top}G_{[22]}Z_{3})\Big{]}$
$\displaystyle\leq\mathbb{E}^{1/2}(Z_{1}^{\top}G_{[12]}Z_{1}-\operatorname{tr}(G_{[12]}))^{4}\cdot\mathbb{E}^{1/2}(Z_{1}^{\top}H_{[11]}G_{[22]}H_{[11]}Z_{1})^{2}$
$\displaystyle\lesssim_{M}\lVert\Sigma_{XY}\rVert_{F}^{2}\cdot\lVert\Sigma_{XY}\rVert_{F}^{2}=\lVert\Sigma_{XY}\rVert_{F}^{4}.$

In summary we have

$\displaystyle(n-1)\cdot\mathbb{E}\lVert
T_{65}\rVert_{F}^{2}\lesssim_{M}n^{3}\cdot\lVert\Sigma_{X}\rVert_{F}^{2}\lVert\Sigma_{Y}\rVert_{F}^{2}\lVert\Sigma_{XY}\rVert_{F}^{2}+n^{4}\cdot\lVert\Sigma_{XY}\rVert_{F}^{4}.$
(D.13)

A similar bound holds for $T_{64}$. Combining (D.11) - (D.13) and Lemma F.5
concludes the proof. ∎

######  Lemma D.2.

Let $U\equiv H_{[11]}ZZ^{\top}H_{[22]}-G_{[12]}$ with
$Z\sim\mathcal{N}(0,I_{p+q})$, and $U_{1},U_{2},\ldots$ be independent copies
of $U$. Then the following hold.

  1. (1)

$\mathbb{E}U^{2}=G_{[11]}G_{[22]}+\operatorname{tr}(G_{[12]})G_{[12]}$.

  2. (2)

$\mathbb{E}U^{\top}U=G_{[21]}G_{[12]}+G_{[22]}\operatorname{tr}(G_{[11]})$,
$\mathbb{E}UU^{\top}=G_{[12]}G_{[21]}+G_{[11]}\operatorname{tr}(G_{[22]})$.

  3. (3)

$\mathbb{E}\operatorname{tr}(U)U=G_{[11]}G_{[22]}+G_{[12]}^{2}$.

  4. (4)

$\mathbb{E}\operatorname{tr}^{4}(U)\lesssim_{M}\lVert\Sigma_{XY}\rVert_{F}^{4}$
and $\mathbb{E}\lVert
U\rVert_{F}^{4}\lesssim_{M}\lVert\Sigma_{X}\rVert_{F}^{4}\lVert\Sigma_{Y}\rVert_{F}^{4}$.

  5. (5)

$\mathbb{E}\operatorname{tr}^{2}(U_{1}^{\top}U_{2})\asymp\lVert\Sigma_{X}^{2}\rVert_{F}^{2}\lVert\Sigma_{Y}^{2}\rVert_{F}^{2}$,
$\mathbb{E}\operatorname{tr}^{2}(U_{1}U_{2})\asymp\lVert\Sigma_{XY}\Sigma_{YX}\rVert_{F}^{4}$.

  6. (6)

$\mathbb{E}\operatorname{tr}(U_{1})\operatorname{tr}(U_{2})\operatorname{tr}(U_{1}^{\top}U_{2})\asymp_{M}\lVert\Sigma_{XY}\Sigma_{YX}\rVert_{F}^{2}$.

###### Proof.

(1). By Lemma F.3,

$\displaystyle\mathbb{E}U^{2}$
$\displaystyle=\mathbb{E}\big{(}H_{[11]}ZZ^{\top}H_{[22]}H_{[11]}ZZ^{\top}H_{[22]}\big{)}-G_{[12]}^{2}$
$\displaystyle=H_{[11]}\cdot\mathbb{E}(ZZ^{\top})(Z^{\top}H_{[22]}H_{[11]}Z)\cdot
H_{[22]}-G^{2}_{[12]}$
$\displaystyle=H_{[11]}\big{(}H_{[11]}H_{[22]}+H_{[22]}H_{[11]}+\operatorname{tr}(G_{[12]})\cdot
I\big{)}H_{[22]}-G^{2}_{[12]}$
$\displaystyle=G_{[11]}G_{[22]}+\operatorname{tr}(G_{[12]})G_{[12]}.$

(2). By Lemma F.3,

$\displaystyle\mathbb{E}U^{\top}U$
$\displaystyle=\mathbb{E}\big{(}H_{[22]}ZZ^{\top}H_{[11]}^{2}ZZ^{\top}H_{[22]}\big{)}-G_{[21]}G_{[12]}$
$\displaystyle=H_{[22]}\cdot\mathbb{E}(ZZ^{\top})(Z^{\top}H_{[11]}^{2}Z)\cdot
H_{[22]}-G_{[21]}G_{[12]}$
$\displaystyle=H_{[22]}\big{(}2H_{[11]}^{2}+\operatorname{tr}(G_{[11]})\cdot
I\big{)}H_{[22]}-G_{[21]}G_{[12]}$
$\displaystyle=G_{[21]}G_{[12]}+G_{[22]}\operatorname{tr}(G_{[11]}),$

and similarly

$\displaystyle\mathbb{E}UU^{\top}$
$\displaystyle=G_{[12]}G_{[21]}+G_{[11]}\operatorname{tr}(G_{[22]}).$

(3). We have

$\displaystyle\mathbb{E}\operatorname{tr}(U)U$
$\displaystyle=\mathbb{E}\Big{(}Z^{\top}G_{[12]}Z-\operatorname{tr}(G_{[12]})\Big{)}\Big{(}H_{[11]}ZZ^{\top}H_{[22]}-G_{[12]}\Big{)}$
$\displaystyle=H_{[11]}\cdot\mathbb{E}(ZZ^{\top})(Z^{\top}G_{[12]}Z)\cdot
H_{[22]}-\operatorname{tr}(G_{[12]})G_{[12]}$
$\displaystyle=H_{[11]}\big{(}H_{[11]}H_{[22]}+H_{[22]}H_{[11]}+\operatorname{tr}(G_{[12]})\cdot
I\big{)}H_{[22]}-\operatorname{tr}(G_{[12]})G_{[12]}$
$\displaystyle=G_{[11]}G_{[22]}+G_{[12]}^{2}.$

(4). We have

$\displaystyle\mathbb{E}\operatorname{tr}(U)^{4}$
$\displaystyle=\mathbb{E}\big{[}Z^{\top}G_{[12]}Z-\mathbb{E}(Z^{\top}G_{[12]}Z)\big{]}^{4}\lesssim\lVert
G_{[12]}\rVert_{F}^{4}\lesssim_{M}\lVert\Sigma_{XY}\rVert_{F}^{4},$
$\displaystyle\mathbb{E}\lVert U\rVert_{F}^{4}$
$\displaystyle\leq\mathbb{E}\lVert
H_{[11]}ZZ^{\top}H_{[22]}\rVert_{F}^{4}+\lVert G_{[12]}\rVert_{F}^{4}$
$\displaystyle\lesssim_{M}\mathbb{E}\lVert H_{[11]}Z\rVert^{4}\lVert
H_{[22]}Z\rVert^{4}+\lVert\Sigma_{XY}\rVert_{F}^{4}\lesssim\lVert\Sigma_{X}\rVert_{F}^{4}\lVert\Sigma_{Y}\rVert_{F}^{4}+\lVert\Sigma_{XY}\rVert_{F}^{4}.$

The claim follows by Lemma F.5.

(5). By definition, we have

$\displaystyle\operatorname{tr}(U_{1}^{\top}U_{2})$
$\displaystyle=\operatorname{tr}\bigg{(}\big{[}H_{[22]}Z_{1}Z_{1}^{\top}H_{[11]}-G_{[21]}\big{]}\big{[}H_{[11]}Z_{2}Z_{2}^{\top}H_{[22]}-G_{[12]}\big{]}\bigg{)}$
$\displaystyle=(Z_{1}^{\top}G_{[11]}Z_{2})(Z_{1}^{\top}G_{[22]}Z_{2})-Z_{1}^{\top}G_{[11]}G_{[22]}Z_{1}-Z_{2}^{\top}G_{[11]}G_{[22]}Z_{2}+\operatorname{tr}(G_{[11]}G_{[22]})$
$\displaystyle=Z_{1}^{\top}\Big{(}G_{[11]}Z_{2}Z_{2}^{\top}G_{[22]}-G_{[11]}G_{[22]}\Big{)}Z_{1}-\operatorname{tr}(G_{[11]}Z_{2}Z_{2}^{\top}G_{[22]}-G_{[11]}G_{[22]})$
$\displaystyle\equiv
Z_{1}^{\top}A(Z_{2})Z_{1}-\mathbb{E}_{1}(Z_{1}^{\top}A(Z_{2})Z_{1}),$

where $\mathbb{E}_{i}$ denotes expectation only with respect to $Z_{i}$.
Hence,

$\displaystyle\mathbb{E}\operatorname{tr}^{2}(U_{1}^{\top}U_{2})$
$\displaystyle=\mathbb{E}_{2}\operatorname{Var}_{1}(Z_{1}^{\top}A(Z_{2})Z_{1})\asymp\mathbb{E}\lVert
A(Z)\rVert_{F}^{2}$ $\displaystyle=\mathbb{E}\lVert
G_{[11]}ZZ^{\top}G_{[22]}-G_{[11]}G_{[22]}\rVert_{F}^{2}$
$\displaystyle=\mathbb{E}\Big{[}(Z^{\top}G_{[11]}^{2}Z)(Z^{\top}G_{[22]}^{2}Z)-2Z^{\top}G_{[11]}^{2}G_{[22]}^{2}Z+\operatorname{tr}(G_{[11]}^{2}G_{[22]}^{2})\Big{]}$
$\displaystyle=\operatorname{tr}(G_{[11]}^{2}G_{[22]}^{2})+\lVert
G_{[11]}\rVert_{F}^{2}\lVert G_{[22]}\rVert_{F}^{2}\asymp\lVert
G_{[11]}\rVert_{F}^{2}\lVert G_{[22]}\rVert_{F}^{2}$
$\displaystyle=\lVert\Sigma_{X}^{2}\rVert_{F}^{2}\lVert\Sigma_{Y}^{2}\rVert_{F}^{2}\lesssim_{M}\lVert\Sigma_{X}\rVert_{F}^{2}\lVert\Sigma_{Y}\rVert_{F}^{2}.$

On the other hand, as

$\displaystyle\operatorname{tr}(U_{1}U_{2})$
$\displaystyle=\operatorname{tr}\bigg{(}\big{[}H_{[11]}Z_{1}Z_{1}^{\top}H_{[22]}-G_{[12]}\big{]}\big{[}H_{[11]}Z_{2}Z_{2}^{\top}H_{[22]}-G_{[12]}\big{]}\bigg{)}$
$\displaystyle=(Z_{1}^{\top}G_{[12]}Z_{2})(Z_{1}^{\top}G_{[21]}Z_{2})-Z_{1}^{\top}G_{[12]}^{2}Z_{1}-Z_{2}^{\top}G_{[12]}^{2}Z_{2}+\operatorname{tr}(G_{[12]}^{2})$
$\displaystyle=Z_{1}^{\top}\Big{(}G_{[12]}Z_{2}Z_{2}^{\top}G_{[12]}-G_{[12]}^{2}\Big{)}Z_{1}-\operatorname{tr}(G_{[12]}Z_{2}Z_{2}^{\top}G_{[12]}-G_{[12]}^{2})$
$\displaystyle\equiv
Z_{1}^{\top}B(Z_{2})Z_{1}-\mathbb{E}_{1}(Z_{1}^{\top}B(Z_{2})Z_{1}),$

so using a similar argument as in the case for
$\mathbb{E}\operatorname{tr}^{2}(U_{1}^{\top}U_{2})$, we have

$\displaystyle\mathbb{E}\operatorname{tr}^{2}(U_{1}U_{2})$
$\displaystyle=\mathbb{E}\lVert
G_{[12]}ZZ^{\top}G_{[12]}-G_{[12]}^{2}\rVert_{F}^{2}$
$\displaystyle=\mathbb{E}\Big{[}(Z^{\top}G_{[12]}G_{[21]}Z)(Z^{\top}G_{[21]}G_{[12]}Z)-2Z^{\top}G_{[12]}G_{[21]}^{2}G_{[12]}Z+\operatorname{tr}(G_{[12]}^{2}G_{[21]}^{2})\Big{]}$
$\displaystyle=\operatorname{tr}(G_{[12]}^{2}G_{[21]}^{2})+\lVert
G_{[12]}\rVert_{F}^{4}\asymp\lVert
G_{[12]}\rVert_{F}^{4}=\lVert\Sigma_{XY}\Sigma_{YX}\rVert_{F}^{4}.$

(6). Using the formula for $\operatorname{tr}(U_{1}^{\top}U_{2})$ in the proof
of (5) above,

$\displaystyle\mathbb{E}\operatorname{tr}(U_{1})\operatorname{tr}(U_{2})\operatorname{tr}(U_{1}^{\top}U_{2})$
$\displaystyle=\mathbb{E}(Z_{1}^{\top}G_{[12]}Z_{1}-\operatorname{tr}(G_{[12]}))(Z_{2}^{\top}G_{[12]}Z_{2}-\operatorname{tr}(G_{[12]}))(Z_{1}^{\top}A(Z_{2})Z_{1}-\operatorname{tr}(A(Z_{2})))$
$\displaystyle=\mathbb{E}(Z_{2}^{\top}G_{[12]}Z_{2}-\operatorname{tr}(G_{[12]}))\cdot\operatorname{tr}(G_{[12]}A(Z_{2})+G_{[12]}A(Z_{2})^{\top})\quad\hbox{(by
Lemma \ref{lem:gaussian_4moment}-(1))}$
$\displaystyle=\mathbb{E}(Z_{2}^{\top}G_{[12]}Z_{2}-\operatorname{tr}(G_{[12]}))$
$\displaystyle\quad\quad\quad\cdot\big{[}Z_{2}^{\top}\big{(}G_{[11]}(G_{[12]}+G_{[21]})G_{[22]}\big{)}Z_{2}-\operatorname{tr}\big{(}G_{[11]}(G_{[12]}+G_{[21]})G_{[22]}\big{)}\big{]}$
$\displaystyle\asymp\operatorname{tr}\big{[}G_{[12]}\cdot\big{(}G_{[11]}(G_{[12]}+G_{[21]})G_{[22]}\big{)}\big{]}\asymp_{M}\lVert\Sigma_{XY}\Sigma_{YX}\rVert_{F}^{2}+\operatorname{tr}\big{[}(\Sigma_{XY}\Sigma_{YX})^{3}\big{]}$
$\displaystyle\asymp_{M}\lVert\Sigma_{XY}\Sigma_{YX}\rVert_{F}^{2}.$

The proof is complete. ∎

####  D.2.2. Third moment bound

###### Proof of Proposition 10.4-(2).

For any $i\in[n]$, let $M_{-i}\equiv\sum_{k\neq i}X_{k}Y_{k}^{\top}$. By
definition of $\Delta_{i}\psi_{1}(\bm{X},\bm{Y})$, we have

$\displaystyle\mathbb{E}|\Delta_{i}\psi_{1}(\bm{X},\bm{Y})|^{3}\lesssim\mathbb{E}^{3/4}(X_{i}^{\top}M_{-i}Y_{i}-X_{i}^{\prime\top}M_{-i}Y_{i}^{\prime})^{4}$
$\displaystyle\lesssim\mathbb{E}^{3/4}\big{[}X_{i}^{\top}M_{-i}Y_{i}-\mathbb{E}_{(X_{i},Y_{i})}(X_{i}^{\top}M_{-i}Y_{i})\big{]}^{4}+\mathbb{E}^{3/4}\big{[}X_{i}^{\prime\top}M_{-i}Y_{i}^{\prime}-\mathbb{E}_{(X_{i}^{\prime},Y_{i}^{\prime})}(X_{i}^{\prime\top}M_{-i}Y_{i}^{\prime})\big{]}^{4}$
$\displaystyle=\mathbb{E}^{3/4}\big{[}Z_{i}^{\top}\widetilde{M}_{-i}Z_{i}-\mathbb{E}_{Z_{i}}(Z_{i}^{\top}\widetilde{M}_{-i}Z_{i})\big{]}^{4}+\mathbb{E}^{3/4}\big{[}Z_{i}^{\prime\top}\widetilde{M}_{-i}Z_{i}^{\prime}-\mathbb{E}_{Z_{i}^{\prime}}(Z_{i}^{\prime\top}M_{-i}Z_{i}^{\prime})\big{]}^{4}.$

Here $\widetilde{M}_{-i}$ is the random matrix defined by

$\displaystyle\widetilde{M}_{-i}\equiv\Sigma^{1/2}\begin{pmatrix}0&M_{-i}\\\
0&0\end{pmatrix}\Sigma^{1/2}.$

Hence we have

$\displaystyle\mathbb{E}|\Delta_{i}\psi_{1}(\bm{X},\bm{Y})|^{3}$
$\displaystyle\lesssim\mathbb{E}^{3/4}\lVert\widetilde{M}_{-i}\rVert_{F}^{4}\lesssim_{M}\mathbb{E}^{3/4}\lVert
M_{-i}\rVert_{F}^{4}$
$\displaystyle\lesssim_{M}n^{3/2}\operatorname{tr}^{3/2}(\Sigma_{X})\operatorname{tr}^{3/2}(\Sigma_{Y})+n^{3}\lVert\Sigma_{XY}\rVert_{F}^{3},$

using Lemma D.3 in the last step. ∎

######  Lemma D.3.

For any $i\in[n]$, let $M_{-i}\equiv\sum_{k\neq i}X_{k}Y_{k}^{\top}$. Then the
mean and variance of $\lVert M_{-i}\rVert_{F}^{2}$ satisfy:

$\displaystyle\mathbb{E}\lVert M_{-i}\rVert_{F}^{2}$
$\displaystyle=n(n-1)\lVert\Sigma_{XY}\rVert_{F}^{2}+(n-1)\operatorname{tr}(\Sigma_{X})\operatorname{tr}(\Sigma_{Y}),$
$\displaystyle\operatorname{Var}\big{(}\lVert M_{-i}\rVert_{F}^{2}\big{)}$
$\displaystyle\lesssim_{M}n\cdot\big{[}\tau_{X}^{2}\tau_{Y}^{2}(n\vee\tau_{X}^{2}\vee\tau_{Y}^{2})+n^{2}\lVert\Sigma_{XY}\rVert_{F}^{2}\big{]}.$

Consequently, $\mathbb{E}\lVert M_{-i}\rVert_{F}^{4}\lesssim
n^{2}\operatorname{tr}^{2}(\Sigma_{X})\operatorname{tr}^{2}(\Sigma_{Y})+n^{4}\lVert\Sigma_{XY}\rVert_{F}^{4}$.

###### Proof.

Without loss of generality we let $i=1$. Note that

$\displaystyle\lVert M_{-1}\rVert_{F}^{2}$
$\displaystyle=\sum_{k_{1},k_{2}\neq
1}(X_{k_{1}}^{\top}X_{k_{2}})(Y_{k_{1}}^{\top}Y_{k_{2}})=\sum_{k_{1},k_{2}\neq
1}(Z_{k_{1}}^{\top}H_{[11]}Z_{k_{2}})(Z_{k_{1}}^{\top}H_{[22]}Z_{k_{2}}).$

Hence the mean formula is

$\displaystyle\mathbb{E}\lVert M_{-1}\rVert_{F}^{2}$
$\displaystyle=(n-1)\mathbb{E}(Z_{1}^{\top}H_{[11]}Z_{1})(Z_{1}^{\top}H_{[22]}Z_{1})+(n-1)(n-2)\mathbb{E}(Z_{1}^{\top}H_{[11]}Z_{2})(Z_{1}^{\top}H_{[22]}Z_{2})$
$\displaystyle=(n-1)\cdot\big{[}2\operatorname{tr}(G_{[12]})+\operatorname{tr}(H_{[11]})\operatorname{tr}(H_{[22]})\big{]}+(n-1)(n-2)\operatorname{tr}(G_{[12]})$
$\displaystyle=n(n-1)\lVert\Sigma_{XY}\rVert_{F}^{2}+(n-1)\operatorname{tr}(\Sigma_{X})\operatorname{tr}(\Sigma_{Y}).$

To bound the variance of $\lVert M_{-1}\rVert_{F}^{2}$, write

$\displaystyle T(Z)\equiv\lVert M_{-1}\rVert_{F}^{2}=\sum_{k_{1},k_{2}\neq
1}(Z_{k_{1}}^{\top}H_{[11]}Z_{k_{2}})(Z_{k_{1}}^{\top}H_{[22]}Z_{k_{2}}).$

So for any $i\neq 1$,

$\displaystyle\nabla_{Z_{i}}T(Z)$ $\displaystyle=\sum_{k_{1},k_{2}\neq
1}\Big{[}(\delta_{k_{1},i}\cdot H_{[11]}Z_{k_{2}}+\delta_{k_{2},i}\cdot
H_{[11]}Z_{k_{1}})(Z_{k_{1}}^{\top}H_{[22]}Z_{k_{2}})$
$\displaystyle\quad\quad+(\delta_{k_{1},i}\cdot
H_{[22]}Z_{k_{2}}+\delta_{k_{2},i}H_{[22]}Z_{k_{1}})(Z_{k_{1}}^{\top}H_{[11]}Z_{k_{2}})\Big{]}$
$\displaystyle=2\cdot\sum_{k\neq
1}(Z_{k}^{\top}H_{[22]}Z_{i})H_{[11]}Z_{k}+2\cdot\sum_{k\neq
1}(Z_{k}^{\top}H_{[11]}Z_{i})H_{[22]}Z_{k}\equiv[T_{11}+T_{12}]_{i}.$

Hence

$\displaystyle\mathbb{E}\lVert T_{11}\rVert_{F}^{2}$ $\displaystyle\asymp
n\cdot\mathbb{E}\bigg{\lVert}\sum_{k\neq
1}(Z_{k}^{\top}H_{[22]}Z_{2})H_{[11]}Z_{k}\bigg{\rVert}^{2}$
$\displaystyle=n\cdot\sum_{k_{1},k_{2}\neq
1}\mathbb{E}(Z_{k_{1}}^{\top}H_{[22]}Z_{2})(Z_{k_{2}}^{\top}H_{[22]}Z_{2})(Z_{k_{1}}^{\top}G_{[11]}Z_{k_{2}})$
$\displaystyle\asymp
n\cdot\Big{[}\mathbb{E}(Z_{2}^{\top}H_{[22]}Z_{2})^{2}(Z_{2}^{\top}G_{[11]}Z_{2})+n\cdot\mathbb{E}(Z_{2}^{\top}H_{[22]}Z_{2})(Z_{3}^{\top}H_{[22]}Z_{2})(Z_{2}^{\top}G_{[11]}Z_{3})$
$\displaystyle\quad+n\cdot\mathbb{E}(Z_{3}^{\top}H_{[22]}Z_{2})^{2}(Z_{3}^{\top}G_{[11]}Z_{3})+n^{2}\mathbb{E}(Z_{3}^{\top}H_{[22]}Z_{2})(Z_{4}^{\top}H_{[22]}Z_{2})(Z_{3}^{\top}G_{[11]}Z_{4})\Big{]}$
$\displaystyle\lesssim_{M}n(\tau_{X}^{2}\tau_{Y}^{4}+n\tau_{X}^{2}\tau_{Y}^{2}+n^{2}\lVert\Sigma_{XY}\rVert_{F}^{2}).$

Flipping $X$, $Y$ for $T_{12}$ to conclude that

$\displaystyle\lVert\nabla_{Z}T(Z)\rVert_{F}^{2}\lesssim_{M}n\cdot\big{[}\tau_{X}^{2}\tau_{Y}^{2}(n\vee\tau_{X}^{2}\vee\tau_{Y}^{2})+n^{2}\lVert\Sigma_{XY}\rVert_{F}^{2}\big{]},$

completing the proof. ∎

###  D.3. Proof of Proposition 10.5

###### Proof of Proposition 10.5.

We only prove the claim for the term $X_{i}^{\top}\Sigma_{XY}Y_{j}$, the bound
for the other term is completely analogous. With some abuse of notation, we
write in the proof $\psi_{2}(\bm{X},\bm{Y})\equiv\sum_{i\neq
j}X_{i}^{\top}\Sigma_{XY}Y_{j}$.

(1). For any $i\in[n]$, as

$\displaystyle\psi_{2}(\bm{X},\bm{Y})=\sum_{\begin{subarray}{c}i_{1}\neq
i_{2}\\\ i_{1},i_{2}\neq
i\end{subarray}}X_{i_{1}}^{\top}\Sigma_{XY}Y_{i_{2}}+\sum_{i_{1}\neq
i}X_{i_{1}}^{\top}\Sigma_{XY}Y_{i}+\sum_{i_{2}\neq
i}X_{i}^{\top}\Sigma_{XY}Y_{i_{2}},$

we have

$\displaystyle\Delta_{i}\psi_{2}(\bm{X},\bm{Y})$
$\displaystyle\equiv\psi_{2}(\bm{X},\bm{Y})-\psi_{2}(\bm{X}^{\\{i\\}},\bm{Y}^{\\{i\\}})$
$\displaystyle=\Big{(}\sum_{j\neq
i}X_{j}\Big{)}^{\top}\Sigma_{XY}(Y_{i}-Y_{i}^{\prime})+(X_{i}-X_{i}^{\prime})^{\top}\Sigma_{XY}\Big{(}\sum_{j\neq
i}Y_{j}\Big{)}.$

Hence for any $A\subset[n]$ such that $i\notin A$,

$\displaystyle\Delta_{i}\psi_{2}(\bm{X}^{A},\bm{Y}^{A})$
$\displaystyle=\Big{(}\sum_{j\in A}X_{j}^{\prime}+\sum_{j\notin
A\cup\\{i\\}}X_{j}\Big{)}^{\top}\Sigma_{XY}(Y_{i}-Y_{i}^{\prime})$
$\displaystyle\quad\quad\quad+(X_{i}-X_{i}^{\prime})^{\top}\Sigma_{XY}\Big{(}\sum_{j\in
A}Y_{j}^{\prime}+\sum_{j\notin A\cup\\{i\\}}Y_{j}\Big{)}.$

This implies that

$\displaystyle\mathbb{E}^{\prime}\big{[}\Delta_{i}\psi_{2}(\bm{X},\bm{Y})\Delta_{i}\psi_{2}(\bm{X}^{A},\bm{Y}^{A})\big{]}$
$\displaystyle=\mathbb{E}^{\prime}\Big{[}\Big{(}\sum_{j\neq
i}X_{j}\Big{)}^{\top}\Sigma_{XY}(Y_{i}-Y_{i}^{\prime})\cdot\Big{(}\sum_{j\in
A}X_{j}^{\prime}+\sum_{j\notin
A\cup\\{i\\}}X_{j}\Big{)}^{\top}\Sigma_{XY}(Y_{i}-Y_{i}^{\prime})\Big{]}$
$\displaystyle\quad+\mathbb{E}^{\prime}\Big{[}\Big{(}\sum_{j\neq
i}X_{j}\Big{)}^{\top}\Sigma_{XY}(Y_{i}-Y_{i}^{\prime})\cdot(X_{i}-X_{i}^{\prime})^{\top}\Sigma_{XY}\Big{(}\sum_{j\in
A}Y_{j}^{\prime}+\sum_{j\notin A\cup\\{i\\}}Y_{j}\Big{)}\Big{]}$
$\displaystyle\quad+\mathbb{E}^{\prime}\Big{[}(X_{i}-X_{i}^{\prime})^{\top}\Sigma_{XY}\Big{(}\sum_{j\neq
i}Y_{j}\Big{)}\cdot\Big{(}\sum_{j\in A}X_{j}^{\prime}+\sum_{j\notin
A\cup\\{i\\}}X_{j}\Big{)}^{\top}\Sigma_{XY}(Y_{i}-Y_{i}^{\prime})\Big{]}$
$\displaystyle\quad+\mathbb{E}^{\prime}\Big{[}(X_{i}-X_{i}^{\prime})^{\top}\Sigma_{XY}\Big{(}\sum_{j\neq
i}Y_{j}\Big{)}\cdot(X_{i}-X_{i}^{\prime})^{\top}\Sigma_{XY}\Big{(}\sum_{j\in
A}Y_{j}^{\prime}+\sum_{j\notin A\cup\\{i\\}}Y_{j}\Big{)}\Big{]}$
$\displaystyle=\Big{(}\sum_{j\neq
i}X_{j}\Big{)}^{\top}\Sigma_{XY}(Y_{i}Y_{i}^{\top}+\Sigma_{Y})\Sigma_{YX}\Big{(}\sum_{j\notin
A\cup\\{i\\}}X_{j}\Big{)}$ $\displaystyle\quad\quad+\Big{(}\sum_{j\neq
i}X_{j}\Big{)}^{\top}\Sigma_{XY}(Y_{i}X_{i}^{\top}+\Sigma_{YX})\Sigma_{XY}\Big{(}\sum_{j\notin
A\cup\\{i\\}}Y_{j}\Big{)}$ $\displaystyle\quad\quad+\Big{(}\sum_{j\neq
i}Y_{j}\Big{)}^{\top}\Sigma_{YX}(X_{i}Y_{i}^{\top}+\Sigma_{XY})\Sigma_{YX}\Big{(}\sum_{j\notin
A\cup\\{i\\}}X_{j}\Big{)}$ $\displaystyle\quad\quad+\Big{(}\sum_{j\neq
i}Y_{j}\Big{)}^{\top}\Sigma_{YX}(X_{i}X_{i}^{\top}+\Sigma_{X})\Sigma_{XY}\Big{(}\sum_{j\notin
A\cup\\{i\\}}Y_{j}\Big{)}$ $\displaystyle\equiv
S_{1}(i,A)+S_{2}(i,A)+S_{3}(i,A)+S_{4}(i,A).$

Hence by using (D.2.1) we have

$\displaystyle S_{1}$
$\displaystyle\equiv\frac{1}{2}\sum_{A\subsetneq[n]}\sum_{i\notin
A}\frac{S_{1}(i,A)}{{n\choose|A|}(n-|A|)}$
$\displaystyle=\frac{1}{2}\sum_{\begin{subarray}{c}1\leq i\leq n\\\ j\neq
i,k\neq
i\end{subarray}}\big{[}X_{j}^{\top}\Sigma_{XY}(Y_{i}Y_{i}^{\top}+\Sigma_{Y})\Sigma_{YX}X_{k}\big{]}\cdot\Big{[}\sum_{A\cap\\{i,k\\}=\emptyset}\frac{1}{{n\choose|A|}(n-|A|)}\Big{]}$
$\displaystyle=\frac{1}{4}\sum_{\begin{subarray}{c}1\leq i\leq n\\\ j\neq
i,k\neq
i\end{subarray}}\big{[}X_{j}^{\top}\Sigma_{XY}(Y_{i}Y_{i}^{\top}+\Sigma_{Y})\Sigma_{YX}X_{k}\big{]}.$

Using similar calculations, we have

$\displaystyle S_{2}$
$\displaystyle\equiv\frac{1}{2}\sum_{A\subsetneq[n]}\sum_{i\notin
A}\frac{S_{2}(i,A)}{{n\choose|A|}(n-|A|)}=\frac{1}{4}\sum_{\begin{subarray}{c}1\leq
i\leq n\\\ j\neq i,k\neq
i\end{subarray}}\big{[}X_{j}^{\top}\Sigma_{XY}(Y_{i}X_{i}^{\top}+\Sigma_{YX})\Sigma_{XY}Y_{k}\big{]},$
$\displaystyle S_{3}$
$\displaystyle\equiv\frac{1}{2}\sum_{A\subsetneq[n]}\sum_{i\notin
A}\frac{S_{3}(i,A)}{{n\choose|A|}(n-|A|)}=\frac{1}{4}\sum_{\begin{subarray}{c}1\leq
i\leq n\\\ j\neq i,k\neq
i\end{subarray}}\big{[}Y_{j}^{\top}\Sigma_{YX}(X_{i}Y_{i}^{\top}+\Sigma_{XY})\Sigma_{YX}X_{k}\big{]},$
$\displaystyle S_{4}$
$\displaystyle\equiv\frac{1}{2}\sum_{A\subsetneq[n]}\sum_{i\notin
A}\frac{S_{4}(i,A)}{{n\choose|A|}(n-|A|)}=\frac{1}{4}\sum_{\begin{subarray}{c}1\leq
i\leq n\\\ j\neq i,k\neq
i\end{subarray}}\big{[}Y_{j}^{\top}\Sigma_{YX}(X_{i}X_{i}^{\top}+\Sigma_{X})\Sigma_{XY}Y_{k}\big{]}.$

As $\mathbb{E}(\psi_{2}|\bm{X},\bm{Y})=\sum_{i=1}^{4}S_{i}$, the proof is
complete by invoking Lemma D.4 below.

(2). By definition, we have for each $i\in[n]$,

$\displaystyle\mathbb{E}|\Delta_{i}\psi_{2}(\bm{X},\bm{Y})|^{3}\lesssim\mathbb{E}\Big{|}\Big{(}\sum_{j\neq
i}X_{j})^{\top}\Sigma_{XY}(Y_{i}-Y_{i}^{\prime})\Big{|}^{3}+\mathbb{E}\Big{|}\Big{(}\sum_{j\neq
i}Y_{j})^{\top}\Sigma_{YX}(X_{i}-X_{i}^{\prime})\Big{|}^{3}$
$\displaystyle\lesssim\Big{(}n^{2}\mathbb{E}(X_{1}^{\top}\Sigma_{XY}Y_{2})^{4}\Big{)}^{3/4}\leq
n^{3/2}\mathbb{E}^{1/2}(Z_{1}^{\top}G_{[12]}Z_{2})^{6}\asymp n^{3/2}\lVert
G_{[12]}\rVert_{F}^{3}\asymp n^{3/2}\lVert\Sigma_{XY}\rVert_{F}^{3}.$

The proof is complete. ∎

######  Lemma D.4.

Recall the terms $S_{1}$-$S_{4}$ defined in the proof of Proposition 10.5. The
following variance bound holds.

$\displaystyle\max_{1\leq i\leq
4}\operatorname{Var}(S_{i})\lesssim_{M}n^{4}\lVert\Sigma_{XY}\rVert_{F}^{4}.$

###### Proof.

We only give a bound for $S_{1}$; bounds for $S_{2}$-$S_{4}$ follow from
completely analogous arguments. By definition we have
$S_{1}=4^{-1}(S_{11}+S_{12})$, where

$\displaystyle S_{11}$ $\displaystyle\equiv\sum_{\begin{subarray}{c}1\leq
i\leq n\\\ j\neq i,k\neq
i\end{subarray}}(X_{j}^{\top}\Sigma_{XY}Y_{i})(Y_{i}^{\top}\Sigma_{YX}X_{k})=\sum_{k=1}^{n}Z_{k}^{\top}\Big{(}\sum_{\ell\neq
k}G_{[21]}Z_{\ell}\Big{)}\Big{(}\sum_{\ell\neq
k}Z_{\ell}^{\top}G_{[12]}\Big{)}Z_{k},$ $\displaystyle S_{12}$
$\displaystyle\equiv\sum_{\begin{subarray}{c}1\leq i\leq n\\\ j\neq i,k\neq
i\end{subarray}}X_{j}^{\top}\Sigma_{XY}\Sigma_{Y}\Sigma_{YX}X_{k}=(n-2)\cdot\sum_{j,k=1}^{n}X_{j}^{\top}\Sigma_{XY}\Sigma_{Y}\Sigma_{YX}X_{k}.$

To control the variance of $S_{11}$, note that for any $\ell\in[n]$,

$\displaystyle\nabla_{X_{\ell}}S_{11}$
$\displaystyle=\sum_{\begin{subarray}{c}1\leq i\leq n\\\ j\neq i,k\neq
i\end{subarray}}\delta_{j\ell}\Sigma_{XY}Y_{i}(Y_{i}^{\top}\Sigma_{YX}X_{k})+\delta_{k\ell}\Sigma_{XY}Y_{i}(Y_{i}^{\top}\Sigma_{YX}X_{j})$
$\displaystyle=2\sum_{i\neq\ell,j\neq
i}\Sigma_{XY}Y_{i}(Y_{i}^{\top}\Sigma_{YX}X_{j})=2\sum_{j}\Sigma_{XY}M_{Y,-\\{j,\ell\\}}\Sigma_{YX}X_{j}.$

Here $M_{Y,-A}\equiv\sum_{k\notin A}Y_{k}Y_{k}^{\top}$ for $A\subset[n]$. Then

$\displaystyle\mathbb{E}\lVert\nabla_{X_{\ell}}S_{11}\rVert^{2}$
$\displaystyle=4\sum_{j}\mathbb{E}\operatorname{tr}\big{(}\Sigma_{XY}M_{Y,-\\{j,\ell\\}}\Sigma_{YX}\Sigma_{XY}M_{Y,-\\{j,\ell\\}}\Sigma_{YX}\big{)}$
$\displaystyle=4\sum_{j}\sum_{k_{1},k_{2}\neq
j,\ell}\mathbb{E}(Y_{k_{1}}^{\top}\Sigma_{YX}\Sigma_{XY}Y_{k_{2}})^{2}\lesssim_{M}n^{3}\lVert\Sigma_{XY}\Sigma_{YX}\rVert_{F}^{2}\leq
n^{3}\lVert\Sigma_{XY}\rVert_{F}^{4}.$

On the other hand, as

$\displaystyle\nabla_{Y_{\ell}}S_{11}$
$\displaystyle=\sum_{\begin{subarray}{c}1\leq i\leq n\\\ j\neq i,k\neq
i\end{subarray}}\delta_{i\ell}\big{[}\Sigma_{YX}X_{j}(X_{k}^{\top}\Sigma_{XY}Y_{i})+\Sigma_{YX}X_{k}(X_{j}^{\top}\Sigma_{XY}Y_{i})\big{]}$
$\displaystyle=2\sum_{j,k\neq\ell}\Sigma_{YX}X_{j}(X_{k}^{\top}\Sigma_{XY}Y_{\ell}),$

we have

$\displaystyle\mathbb{E}\lVert\nabla_{Y_{\ell}}S_{11}\rVert^{2}$
$\displaystyle=4\sum_{\begin{subarray}{c}j_{1},j_{2},k_{1},k_{2}\neq\ell,\\\
\lvert\\{j_{1},j_{2},k_{1},k_{2}\\}\rvert=1,2\end{subarray}}\mathbb{E}\big{(}X_{j_{1}}^{\top}\Sigma_{XY}\Sigma_{Y}\Sigma_{YX}X_{j_{2}}\big{)}\big{(}X_{k_{1}}^{\top}\Sigma_{XY}\Sigma_{YX}X_{k_{2}}\big{)}$
$\displaystyle\lesssim_{M}n\lVert\Sigma_{XY}\rVert_{F}^{4}+n^{2}\big{(}\lVert\Sigma_{XY}\rVert_{F}^{4}+\lVert\Sigma_{XY}\Sigma_{YX}\rVert_{F}^{2}\big{)}\asymp
n^{2}\lVert\Sigma_{XY}\rVert_{F}^{4}.$

Putting together the two estimates and using the Gaussian-Poincaré inequality
and a change of variable yield that

$\displaystyle\operatorname{Var}(S_{11})\lesssim_{M}\sum_{\ell}\big{(}\mathbb{E}\lVert\nabla_{X_{\ell}}S_{11}\rVert^{2}+\mathbb{E}\lVert\nabla_{Y_{\ell}}S_{11}\rVert^{2}\big{)}\lesssim_{M}n^{4}\lVert\Sigma_{XY}\rVert_{F}^{4}.$

On the other hand, as $\sum_{j=1}^{n}X_{j}\stackrel{{\scriptstyle
d}}{{=}}\sqrt{n}\cdot X$, direct calculation yields that

$\displaystyle\operatorname{Var}(S_{12})$ $\displaystyle\asymp
n^{2}\cdot\operatorname{Var}\Big{[}\Big{(}\sum_{j=1}^{n}X_{j}\Big{)}^{\top}\Sigma_{XY}\Sigma_{Y}\Sigma_{YX}\Big{(}\sum_{k=1}^{n}X_{k}\Big{)}\Big{]}$
$\displaystyle\asymp
n^{4}\cdot\operatorname{Var}\Big{(}X^{\top}\Sigma_{XY}\Sigma_{Y}\Sigma_{YX}X\Big{)}\lesssim
n^{4}\lVert\Sigma_{XY}\Sigma_{Y}\Sigma_{YX}\rVert_{F}^{2}\lesssim_{M}n^{4}\lVert\Sigma_{XY}\rVert_{F}^{4}.$

Putting together the estimates for $S_{11}$ and $S_{12}$ concludes the proof
for $S_{1}$. ∎

###  D.4. Proof of Proposition 10.6

###### Proof of Proposition 10.6.

We will bound the $X$ component, and the bound for the $Y$ component is
completely analogous.

(1). By direct calculation, we have for each $i\in[n]$,

$\displaystyle\Delta_{i}\psi_{3}(\bm{X},\bm{Y})=\tau_{X}^{-2}\lVert\Sigma_{XY}\rVert_{F}^{2}(\lVert
X_{i}\rVert^{2}-\lVert X_{i}^{\prime}\rVert^{2}).$

Hence for any $A\subset[n]$ such that $i\notin A$, we have also
$\Delta_{i}\psi_{3}(\bm{X}^{A},\bm{Y}^{A})=\tau_{X}^{-2}\lVert\Sigma_{XY}\rVert_{F}^{2}(\lVert
X_{i}\rVert^{2}-\lVert X_{i}^{\prime}\rVert^{2})$, thus by Lemma D.2.1

$\displaystyle T_{\psi_{3}}$ $\displaystyle=\sum_{A\subsetneq[n]}\sum_{i\notin
A}\frac{\tau_{X}^{-4}\lVert\Sigma_{XY}\rVert_{F}^{4}(\lVert
X_{i}\rVert^{2}-\lVert X_{i}^{\prime}\rVert^{2})^{2}}{{n\choose|A|}(n-|A|)}$
$\displaystyle=\sum_{i=1}^{n}\tau_{X}^{-4}\lVert\Sigma_{XY}\rVert_{F}^{4}(\lVert
X_{i}\rVert^{2}-\lVert
X_{i}^{\prime}\rVert^{2})^{2}\cdot\Big{[}\sum_{A\subsetneq[n]:i\notin
A}\frac{1}{{n\choose|A|}(n-|A|)}\Big{]}$
$\displaystyle\asymp\sum_{i=1}^{n}\tau_{X}^{-4}\lVert\Sigma_{XY}\rVert_{F}^{4}(\lVert
X_{i}\rVert^{2}-\lVert X_{i}^{\prime}\rVert^{2})^{2}.$

This means

$\displaystyle\operatorname{Var}\big{[}\mathbb{E}(T_{\psi_{3}}|\bm{X},\bm{Y})\big{]}$
$\displaystyle\leq\operatorname{Var}(T_{\psi_{3}})=n\tau_{X}^{-8}\lVert\Sigma_{XY}\rVert_{F}^{8}\cdot\operatorname{Var}\Big{[}(\lVert
X\rVert^{2}-\lVert X^{\prime}\rVert^{2})^{2}\Big{]}$ $\displaystyle\lesssim
n\tau_{X}^{-8}\cdot\lVert\Sigma_{XY}\rVert_{F}^{8}\cdot\mathbb{E}\big{(}\lVert
X\rVert^{2}-\operatorname{tr}(\Sigma_{X})\big{)}^{4}\lesssim_{M}n\tau_{X}^{-4}\cdot\lVert\Sigma_{XY}\rVert_{F}^{8}.$

(2). We have

$\displaystyle\mathbb{E}|\Delta_{j}\psi_{3}(\bm{X},\bm{Y})|^{3}$
$\displaystyle=\tau_{X}^{-6}\lVert\Sigma_{XY}\rVert_{F}^{6}\cdot\mathbb{E}\lvert\lVert
X\rVert^{2}-\lVert
X^{\prime}\rVert^{2}\rvert^{3}\lesssim\tau_{X}^{-6}\lVert\Sigma_{XY}\rVert_{F}^{6}\mathbb{E}\lvert\lVert
X\rVert^{2}-\operatorname{tr}(\Sigma_{X})\rvert^{3}$
$\displaystyle\lesssim\tau_{X}^{-6}\lVert\Sigma_{XY}\rVert_{F}^{6}\cdot\lVert\Sigma_{X}\rVert_{F}^{3}\lesssim_{M}\tau_{X}^{-3}\lVert\Sigma_{XY}\rVert_{F}^{6}.$

The proof is complete. ∎

##  Appendix E Proof of Theorem 2.5

For notational simplicity, we only prove the case $f_{X}=f_{Y}=f$; the general
case only requires formal modifications.

###  E.1. Notation and preliminaries

Let

$\displaystyle U_{f,\gamma_{X}}(x_{1},x_{2})$ $\displaystyle\equiv
f\big{(}\lVert x_{1}-x_{2}\rVert/\gamma_{X}\big{)}-\mathbb{E}f\big{(}\lVert
x_{1}-X\rVert/\gamma_{X}\big{)}$
$\displaystyle\qquad\qquad-\mathbb{E}f\big{(}\lVert
X-x_{2}\rVert/\gamma_{X}\big{)}+\mathbb{E}f\big{(}\lVert
X-X^{\prime}\rVert/\gamma_{X}\big{)},$ $\displaystyle
V_{f,\gamma_{Y}}(y_{1},y_{2})$ $\displaystyle\equiv f\big{(}\lVert
y_{1}-y_{2}\rVert/\gamma_{Y}\big{)}-\mathbb{E}f\big{(}\lVert
y_{1}-Y\rVert/\gamma_{Y}\big{)}$
$\displaystyle\qquad\qquad-\mathbb{E}f\big{(}\lVert
Y-y_{2}\rVert/\gamma_{Y}\big{)}+\mathbb{E}f\big{(}\lVert
Y-Y^{\prime}\rVert/\gamma_{Y}\big{)}.$

The sample kernel distance covariance
$\operatorname{dCov}_{\ast}^{2}(\bm{X},\bm{Y};f,\gamma)$ in (2.9) can be
represented as a 4-th order $U$-statistics using
$U_{f,\gamma_{X}},V_{f,\gamma_{Y}}$ similar to Proposition 2.1.

######  Proposition E.1.

The following holds:

$\displaystyle\operatorname{dCov}_{\ast}^{2}(\bm{X},\bm{Y};f,\gamma)$
$\displaystyle=\frac{1}{\binom{n}{4}}\sum_{i_{1}<\cdots<i_{4}}h_{f,\gamma}\big{(}Z_{i_{1}},Z_{i_{2}},Z_{i_{3}},Z_{i_{4}}\big{)},$

where

$\displaystyle
h_{f,\gamma}(Z_{1},Z_{2},Z_{3},Z_{4})=\frac{1}{4!}\sum_{(i_{1},\ldots,i_{4})\in\sigma(1,2,3,4)}\bigg{[}U_{f,\gamma_{X}}(X_{i_{1}},X_{i_{2}})V_{f,\gamma_{Y}}(Y_{i_{1}},Y_{i_{2}})$
$\displaystyle\qquad\qquad+U_{f,\gamma_{X}}(X_{i_{1}},X_{i_{2}})V_{f,\gamma_{Y}}(Y_{i_{3}},Y_{i_{4}})-2U_{f,\gamma_{X}}(X_{i_{1}},X_{i_{2}})V_{f,\gamma_{Y}}(Y_{i_{1}},Y_{i_{3}})\bigg{]}.$

###### Proof.

The proof follows the same lines as that of Proposition 2.1; we omit
repetitive details. ∎

We need the following basic properties of $f_{\sqrt{\cdot}}(\cdot)$ inherited
from Assumption B.

######  Lemma E.2.

Under Assumption B for $f(\cdot)$, conclusions (1)-(4) therein hold for
$f_{\sqrt{\cdot}}(\cdot)$ with different constants
$c^{\prime}_{\varepsilon},C^{\prime}_{\varepsilon},\mathfrak{q}^{\prime}$.
Furthermore, $c^{\prime}_{\varepsilon},C^{\prime}_{\varepsilon}$ only depend
on $c_{\varepsilon},C_{\varepsilon}$ and $\varepsilon$, and
$\mathfrak{q}^{\prime}$ only depends on $\mathfrak{q}$.

###### Proof.

The claims hold by definitions of $f^{(\ell)}_{\sqrt{\cdot}}$,
$\ell=0,1,2,3,4$. ∎

A useful consequence of Assumption B is the following.

######  Lemma E.3.

Suppose that Assumption B holds, and the spectrum of $\Sigma_{X},\Sigma_{Y}$
is contained in $[1/M,M]$ for some $M>1$. Then for any integer
$s\in\mathbb{N}$, there exists $K\equiv K(s,\mathfrak{q})>0$ such that if
$p\wedge q\geq K$,

$\displaystyle\max_{1\leq\ell\leq
4}\sup_{\rho^{2}\in[1/M,M]}\sup_{t\in[0,1]}\mathbb{E}\big{\lvert}f_{\sqrt{\cdot}}^{(\ell)}\big{(}\rho^{2}(1+tW)\big{)}\big{\rvert}^{s}\lesssim_{M}1,$

where $W$ is either $L_{X}(X_{1},X_{2})$ or $L_{Y}(Y_{1},Y_{2})$ defined in
(7.3).

###### Proof.

We only prove the case for $W=L_{X}(X_{1},X_{2})$, $\ell=1$. By Lemma E.2, for
all $x\geq 0$, $\lvert f_{\sqrt{\cdot}}^{(1)}(x)\rvert\leq C_{f}(1\vee
x^{-\mathfrak{q^{\prime}}})$ for some $C_{f}>0$ and
$\mathfrak{q}^{\prime}\in\mathbb{N}$. This means that

$\displaystyle\mathbb{E}\big{\lvert}f_{\sqrt{\cdot}}^{(1)}\big{(}\rho^{2}(1+tL_{X}(X_{1},X_{2}))\big{)}\big{\rvert}^{s}\lesssim
1+\rho^{-2s\mathfrak{q^{\prime}}}\mathbb{E}\big{(}1+tL_{X}(X_{1},X_{2})\big{)}^{-s\mathfrak{q^{\prime}}}$
$\displaystyle\lesssim
1+\rho^{-2s\mathfrak{q^{\prime}}}\min\big{\\{}(1-t)^{-s\mathfrak{q^{\prime}}},t^{-s\mathfrak{q^{\prime}}}\mathbb{E}\big{(}\tau_{X}^{-2}\lVert
X_{1}-X_{2}\rVert^{2}\big{)}^{-s\mathfrak{q^{\prime}}}\\}.$

Now use (7.3) to conclude. ∎

We define the analogue of the $h$ function in (7.1): For $u\geq-1$, let

$\displaystyle h_{f,\rho}(u)$
$\displaystyle\equiv\frac{f_{\sqrt{\cdot}}(\rho^{2}(1+u))-f_{\sqrt{\cdot}}(\rho^{2})-f_{\sqrt{\cdot}}^{\prime}(\rho^{2})\rho^{2}u}{2f_{\sqrt{\cdot}}^{\prime}(\rho^{2})\rho^{2}}$
$\displaystyle=\frac{\rho^{2}}{2f^{\prime}_{\sqrt{\cdot}}(\rho^{2})}\cdot
u^{2}\int_{0}^{1}f^{\prime\prime}_{\sqrt{\cdot}}\big{(}\rho^{2}(1+su)\big{)}(1-s)\,\mathrm{d}s.$

When $f(x)=x$ so that $f_{\sqrt{\cdot}}(x)=\sqrt{x}$ and $\rho=1$, we recover
the $h$ function in (7.1).

######  Lemma E.4.

Suppose that Assumption B holds and $1/M\leq\rho^{2}\leq M$ for some $M>1$.
Then

$\displaystyle\lvert h_{f,\rho}(u)\rvert\lesssim_{M}u^{2},\quad\lvert
h_{f,\rho}^{\prime}(u)\rvert\lesssim_{M}\big{|}u\cdot F_{f,\rho;2}(u)\big{|},$

where

$\displaystyle F_{f,\rho;2}(u)\equiv
u^{-1}\int_{0}^{u}f_{\sqrt{\cdot}}^{\prime\prime}(\rho^{2}(1+t))\,\mathrm{d}t=\int_{0}^{1}f_{\sqrt{\cdot}}^{\prime\prime}(\rho^{2}(1+us))\,\mathrm{d}s.$

Furthermore

$\displaystyle
h_{f,\rho}(u)=\frac{f_{\sqrt{\cdot}}^{\prime\prime}(\rho^{2})\rho^{2}}{4f_{\sqrt{\cdot}}^{\prime}(\rho^{2})}\cdot
u^{2}+\frac{\rho^{4}}{2f_{\sqrt{\cdot}}^{\prime}(\rho^{2})}\cdot
u^{3}\int_{0}^{1}f^{(3)}_{\sqrt{\cdot}}\big{(}\rho^{2}(1+su)\big{)}\frac{(1-s)^{2}}{2}\,\mathrm{d}s$
$\displaystyle=\frac{f_{\sqrt{\cdot}}^{\prime\prime}(\rho^{2})\rho^{2}}{4f_{\sqrt{\cdot}}^{\prime}(\rho^{2})}\cdot
u^{2}+\frac{f_{\sqrt{\cdot}}^{(3)}(\rho^{2})\rho^{4}}{12f_{\sqrt{\cdot}}^{\prime}(\rho^{2})}\cdot
u^{3}+\frac{\rho^{6}}{2f_{\sqrt{\cdot}}^{\prime}(\rho^{2})}\cdot
u^{4}\int_{0}^{1}f^{(4)}_{\sqrt{\cdot}}\big{(}\rho^{2}(1+su)\big{)}\frac{(1-s)^{3}}{6}\,\mathrm{d}s$
$\displaystyle\equiv\frac{f_{\sqrt{\cdot}}^{\prime\prime}(\rho^{2})\rho^{2}}{4f_{\sqrt{\cdot}}^{\prime}(\rho^{2})}\cdot
u^{2}+h_{f,\rho;3}(u).$

###### Proof.

The bound for $h_{f,\rho}$ follows by the following consideration: if
$u\in[-1,-1/2]$, it holds by Lemma E.2-Conclusion (2) and the fact
$\rho\asymp_{M}1$ that $|h_{f,\rho}(u)|\lesssim_{M}1\lesssim_{M}u^{2}$; if
$u>-1/2$, if follows from the lower bound on $|f^{\prime}_{\sqrt{\cdot}}|$ and
upper bound on $|f^{{}^{\prime\prime}}_{\sqrt{\cdot}}|$ that

$\displaystyle|h_{f,\rho}(u)|$
$\displaystyle=\Big{|}\frac{\rho^{2}}{2f^{\prime}_{\sqrt{\cdot}}(\rho^{2})}\cdot
u^{2}\int_{0}^{1}f^{\prime\prime}_{\sqrt{\cdot}}\big{(}\rho^{2}(1+su)\big{)}(1-s)\,\mathrm{d}s\Big{|}$
$\displaystyle\lesssim_{M}u^{2}\cdot\sup_{u>-1/2}\sup_{s\in[0,1]}\big{|}f^{\prime\prime}_{\sqrt{\cdot}}\big{(}\rho^{2}(1+su)\big{)}\big{|}\lesssim_{M}u^{2}.$

On the other hand, by Taylor expansion

$\displaystyle
f_{\sqrt{\cdot}}(\rho^{2}(1+u))-f_{\sqrt{\cdot}}(\rho^{2})-f_{\sqrt{\cdot}}^{\prime}(\rho^{2})\rho^{2}u=\int_{0}^{\rho^{2}u}f_{\sqrt{\cdot}}^{\prime\prime}(\rho^{2}+t)(\rho^{2}u-t)\,\mathrm{d}t$
$\displaystyle=\frac{f_{\sqrt{\cdot}}^{\prime\prime}(\rho^{2})}{2}(\rho^{2}u)^{2}+(\rho^{2}u)^{3}\int_{0}^{1}f^{(3)}_{\sqrt{\cdot}}\big{(}\rho^{2}(1+su)\big{)}\frac{(1-s)^{2}}{2}\,\mathrm{d}s$
$\displaystyle=\frac{f_{\sqrt{\cdot}}^{\prime\prime}(\rho^{2})}{2}(\rho^{2}u)^{2}+\frac{f_{\sqrt{\cdot}}^{(3)}(\rho^{2})}{6}(\rho^{2}u)^{3}+(\rho^{2}u)^{4}\int_{0}^{1}f^{(4)}_{\sqrt{\cdot}}\big{(}\rho^{2}(1+su)\big{)}\frac{(1-s)^{3}}{6}\,\mathrm{d}s.$

The first equality shows that

$\displaystyle\lvert
h_{f,\rho}^{\prime}(u)\rvert=\bigg{\lvert}\frac{1}{2f^{\prime}_{\sqrt{\cdot}}(\rho^{2})}\int_{0}^{\rho^{2}u}f_{\sqrt{\cdot}}^{\prime\prime}(\rho^{2}+t)\,\mathrm{d}t\bigg{\rvert}\lesssim_{M}\bigg{\lvert}\int_{0}^{u}f_{\sqrt{\cdot}}^{\prime\prime}(\rho^{2}(1+t))\,\mathrm{d}t\bigg{\rvert}=\big{|}u\cdot
F_{f,\rho;2}(u)\big{|},$

as desired. ∎

###  E.2. Residual estimates

Let

$\displaystyle R_{X;f}(x_{1},x_{2})\equiv
h_{f,\rho_{X}}(L_{X}(x_{1},x_{2})),\,R_{Y;f}(y_{1},y_{2})\equiv
h_{f,\rho_{Y}}(L_{Y}(y_{1},y_{2})).$

These quantities are analogues of $R_{X},R_{Y}$ defined in (7.3). Now we may
develop an expansion of $U_{f,\gamma_{X}},V_{f,\gamma_{Y}}$ similar to Lemma
7.3.

######  Lemma E.5.

With $\bar{R}_{X;f},\bar{R}_{Y;f}$ denoting the double centered versions of
${R}_{X;f},{R}_{Y;f}$, we have

$\displaystyle U_{f,\gamma_{X}}(x_{1},x_{2})$
$\displaystyle=-\frac{2f_{\sqrt{\cdot}}^{\prime}(\rho_{X}^{2})}{\gamma_{X}^{2}}\Big{[}x_{1}^{\top}x_{2}-\tau_{X}^{2}\bar{R}_{X;f}(L_{X}(x_{1},x_{2}))\Big{]},$
$\displaystyle V_{f,\gamma_{Y}}(y_{1},y_{2})$
$\displaystyle=-\frac{2f_{\sqrt{\cdot}}^{\prime}(\rho_{Y}^{2})}{\gamma_{Y}^{2}}\Big{[}y_{1}^{\top}y_{2}-\tau_{Y}^{2}\bar{R}_{Y;f}(L_{Y}(y_{1},y_{2}))\Big{]}.$

###### Proof.

Using the definition of $R_{X,f}$, we have

$\displaystyle f\bigg{(}\frac{\lVert x_{1}-x_{2}\rVert}{\gamma_{X}}\bigg{)}$
$\displaystyle=f_{\sqrt{\cdot}}\big{(}\rho_{X}^{2}+\rho_{X}^{2}L_{X}(x_{1},x_{2})\big{)}$
$\displaystyle=f_{\sqrt{\cdot}}(\rho_{X}^{2})+f_{\sqrt{\cdot}}^{\prime}(\rho_{X}^{2})\rho_{X}^{2}\Big{[}L_{X}(x_{1},x_{2})+2\cdot
R_{X;f}(L_{X}(x_{1},x_{2}))\Big{]},$

The claim follows by using the fact that double centered version of
$L_{X}(x_{1},x_{2})$ equals $-2x_{1}^{\top}x_{2}/\tau_{X}^{2}$. ∎

The following moment estimates give an analogy of Lemma 7.4.

######  Lemma E.6.

Suppose Assumption B holds, and that (i) the spectrum of
$\Sigma_{X},\Sigma_{Y}$ and (ii) $\rho_{X},\rho_{Y}$ are contained in
$[1/M,M]$ for some $M>1$. Then:

  1. (1)

For any positive integer $s\in\mathbb{N}$,

$\displaystyle\tau_{X}^{2s}\mathbb{E}R_{X;f}^{s}(X_{1},X_{2})\bigvee\tau_{Y}^{2s}\mathbb{E}R_{Y;f}^{s}(Y_{1},Y_{2})\lesssim_{M,s}1.$

  2. (2)

For any positive integer $s\in\mathbb{N}$,

$\displaystyle\tau_{X}^{s}\mathbb{E}h_{f,\rho_{X}}^{\prime}(L_{X}(X_{1},X_{2}))^{s}\bigvee\tau_{Y}^{s}\mathbb{E}h_{f,\rho_{Y}}^{\prime}(L_{Y}(Y_{1},Y_{2}))^{s}\lesssim_{M}1$

holds for $p,q$ large (possibly depending on $s,\mathfrak{q}$).

###### Proof.

Combining with estimates in Lemma 7.4, (1) follows by $\lvert
h_{f,\rho}(u)\rvert\lesssim_{M}u^{2}$, and (2) follows by $\lvert
h^{\prime}_{f,\rho}(u)\rvert\lesssim_{M}|u\cdot F_{f,\rho;2}(u)|$ and noting
that for any $s\in\mathbb{N}$,

$\displaystyle\mathbb{E}\lvert
F_{f,\rho;2}(L_{X}(X_{1},X_{2}))\rvert^{s}\lesssim\sup_{t\in[0,1]}\mathbb{E}\big{\lvert}f_{\sqrt{\cdot}}^{(2)}\big{(}\rho^{2}(1+tL_{X}(X_{1},X_{2}))\big{)}\big{\rvert}^{s}\lesssim_{M}1$

by Lemma E.3. ∎

Let

$\displaystyle\psi_{X;f}(x_{1},y_{1})$
$\displaystyle\equiv\mathbb{E}_{X_{2},Y_{2}}[\bar{R}_{X;f}(x_{1},X_{2})Y_{2}^{\top}y_{1}],$
$\displaystyle\psi_{Y;f}(x_{1},y_{1})$
$\displaystyle\equiv\mathbb{E}_{X_{2},Y_{2}}[\bar{R}_{Y;f}(y_{1},Y_{2})X_{2}^{\top}x_{1}],$
$\displaystyle\psi_{X,Y;f}(x_{1},y_{1})$
$\displaystyle\equiv\mathbb{E}_{X_{2},Y_{2}}[\bar{R}_{X;f}(x_{1},X_{2})\bar{R}_{Y;f}(y_{1},Y_{2})].$

######  Proposition E.7.

Suppose that Assumption B holds, and that $\rho_{X},\rho_{Y}$ are contained in
$[1/M,M]$ for some $M>1$. Then the bounds in Proposition 8.2 hold when
$\psi_{X},\psi_{Y},\psi_{X,Y}$ are replaced with
$\psi_{X;f},\psi_{Y;f},\psi_{X,Y;f}$ under the same spectrum conditions, for
$p,q$ large (possibly depending on $\mathfrak{q}$).

###### Proof.

The proof essentially proceeds the same way as in the proof of Proposition
8.2. We sketch some differences.

(First moment) First, using a similar argument as in Lemma 8.1, we have the
decomposition

$\displaystyle\psi_{X;f}(x,y)=A_{1,X;f}(x,y)+A_{2,X;f}(x,y),$

where
$A_{2,X;f}(x,y)=\mathbb{E}\big{[}h_{f,\rho_{X};3}(L_{X}(x,X))Y^{\top}y\big{]}$
($h_{f,\rho_{X};3}$ defined in Lemma E.4), and

$\displaystyle
A_{1,X;f}(x,y)=-\frac{f^{\prime\prime}_{\sqrt{\cdot}}(\rho_{X}^{2})\rho_{X}^{2}}{f^{\prime}_{\sqrt{\cdot}}(\rho_{X}^{2})\tau_{X}^{4}}\Big{[}\big{(}\lVert
x\rVert^{2}-\operatorname{tr}(\Sigma_{X})\big{)}x^{\top}\Sigma_{XY}y+2x^{\top}\Sigma_{X}\Sigma_{XY}y\Big{]}.$

The bound
$|\mathbb{E}A_{1,X;f}(X,Y)|\lesssim_{M}\tau_{X}^{-4}\lVert\Sigma_{XY}\rVert_{F}^{2}$
follows from Lemma E.2, and the bound for $|\mathbb{E}A_{2,X;f}(X_{1},Y_{1})|$
follows from the following modification: by Lemma E.2,

$\displaystyle\lvert\mathbb{E}A_{2,X;f}(X_{1},Y_{1})\rvert\lesssim_{M}\big{\lvert}\mathbb{E}\big{[}L_{X}^{3}(X_{1},X_{2})Y_{1}^{\top}Y_{2}\big{]}\big{\rvert}$
$\displaystyle\qquad+\bigg{\lvert}\mathbb{E}\bigg{[}L_{X}^{4}(X_{1},X_{2})Y_{1}^{\top}Y_{2}\cdot\int_{0}^{1}(1-s)^{3}f_{\sqrt{\cdot}}^{(4)}\big{(}\rho^{2}(1+sL_{X}(X_{1},X_{2}))\big{)}\,\mathrm{d}s\bigg{]}\bigg{\rvert}.$

The first term can be handled by Lemma B.2 of order at most
$\tau_{X}^{-4}\lVert\Sigma_{XY}\rVert_{F}^{2}$, while by Lemmas 8.3 and E.3,
the second term can be bounded, up to a constant depending on $M$, by

$\displaystyle\mathbb{E}^{1/2}L_{X}^{8}(X_{1},X_{2})\bigg{[}\int_{0}^{1}(1-s)^{3}f_{\sqrt{\cdot}}^{(4)}\big{(}\rho^{2}(1+sL_{X}(X_{1},X_{2}))\big{)}\,\mathrm{d}s\bigg{]}^{2}\cdot\lVert\Sigma_{XY}\rVert_{F}^{2}$
$\displaystyle\lesssim_{M}\tau_{X}^{-4}\lVert\Sigma_{XY}\rVert_{F}^{2}\cdot\sup_{s\in[0,1]}\mathbb{E}^{1/4}\big{[}f_{\sqrt{\cdot}}^{(4)}\big{(}\rho^{2}(1+sL_{X}(X_{1},X_{2}))\big{)}\big{]}^{4}\lesssim_{M,\mathfrak{q}}\tau_{X}^{-4}\lVert\Sigma_{XY}\rVert_{F}^{2}.$

(Second moment) The proof of the second moment bounds for
$\psi_{X;f},\psi_{Y;f}$ requires a modification for controlling
$\mathbb{E}A_{2,X;f}^{2}(X_{1},Y_{1})$:

$\displaystyle\mathbb{E}A_{2,X;f}^{2}(X_{1},Y_{1})$
$\displaystyle\lesssim_{M}\mathbb{E}_{X_{1},Y_{1}}\bigg{\\{}\mathbb{E}_{X_{2},Y_{2}}\bigg{[}L_{X}^{3}(X_{1},X_{2})Y_{1}^{\top}Y_{2}\int_{0}^{1}(1-s)^{2}f_{\sqrt{\cdot}}^{(3)}\big{(}\rho^{2}(1+sL_{X}(X_{1},X_{2}))\big{)}\,\mathrm{d}s\bigg{]}\bigg{\\}}^{2}$
$\displaystyle\lesssim_{M}\tau_{X}^{-6}\lVert\Sigma_{XY}\rVert_{F}^{2}\cdot\sup_{s\in[0,1]}\mathbb{E}^{1/4}\big{[}f_{\sqrt{\cdot}}^{(3)}\big{(}\rho^{2}(1+sL_{X}(X_{1},X_{2}))\big{)}\big{]}^{8}\lesssim_{M}\tau_{X}^{-6}\lVert\Sigma_{XY}\rVert_{F}^{2}.$

using Lemma E.3 in the last step. The proof of the second moment bound for
$\psi_{X,Y;f}$ proceeds along the same lines upon using Lemma E.6. ∎

###  E.3. Mean and variance expansion

Now we may prove the mean and variance expansion formulae:

######  Proposition E.8.

Suppose that Assumption B holds, and that (i) the spectrum of
$\Sigma_{X},\Sigma_{Y}$ (ii) $\rho_{X},\rho_{Y}$ are contained in $[1/M,M]$
for some $M>1$.

  1. (1)

The following mean expansion holds:

$\displaystyle m_{\Sigma;f,\gamma}$
$\displaystyle\equiv\mathbb{E}\operatorname{dCov}_{\ast}^{2}(\bm{X},\bm{Y};f,\gamma)=\operatorname{dCov}^{2}(X,Y;f,\gamma)$
$\displaystyle=\varrho(\gamma)m_{\Sigma}\Big{[}1+\mathcal{O}_{M}\big{(}(\tau_{X}\wedge\tau_{Y})^{-1}\big{)}\Big{]},$

where $m_{\Sigma}$ is the mean for distance covariance defined in Theorem 8.5.

  2. (2)

The following variance expansion holds:

$\displaystyle\operatorname{Var}\big{(}\operatorname{dCov}_{\ast}^{2}(\bm{X},\bm{Y};f,\gamma)\big{)}$
$\displaystyle=\varrho^{2}(\gamma)\bar{\sigma}_{n}^{2}(X,Y)\Big{[}1+\mathcal{O}_{M}\big{(}n^{-1/2}+(p\wedge
q)^{-1/4}\big{)}\Big{]}.$

Here $\bar{\sigma}_{n}^{2}(X,Y)$ is defined in Theorem 2.2.

###### Proof.

The mean and variance expansions can be proved using exactly the same lines as
in the proof of Theorems 8.5 and 9.12, but using Proposition E.7. The scaling
can be checked, e.g., as the leading term in $m_{\Sigma;f,\gamma}$ equals, by
Lemma E.5,

$\displaystyle\frac{4f_{\sqrt{\cdot}}^{\prime}(\rho_{X}^{2})f_{\sqrt{\cdot}}^{\prime}(\rho_{Y}^{2})}{\gamma_{X}^{2}\tau_{Y}^{2}}\lVert\Sigma_{XY}\rVert_{F}^{2}=4f_{\sqrt{\cdot}}^{\prime}(\rho_{X}^{2})f_{\sqrt{\cdot}}^{\prime}(\rho_{Y}^{2})\frac{\tau_{X}\tau_{Y}}{\gamma_{X}^{2}\gamma_{Y}^{2}}\cdot\frac{\lVert\Sigma_{XY}\rVert_{F}^{2}}{\tau_{X}\tau_{Y}}=\varrho(\gamma)\cdot\frac{\lVert\Sigma_{XY}\rVert_{F}^{2}}{\tau_{X}\tau_{Y}},$

whereas $\lVert\Sigma_{XY}\rVert_{F}^{2}/(\tau_{X}\tau_{Y})$ is the leading
term in $m_{\Sigma}$ as established in Theorem 8.5. ∎

The rest of the proof of Theorem 2.5 follows exactly the same lines as that of
the proof of Theorem 2.2. Details are omitted.

##  Appendix F Auxiliary lemmas

######  Lemma F.1.

For real-valued random variables $W,R$, $N\sim\mathcal{N}(0,1)$ and a
deterministic real number $D$, we have

$\displaystyle d_{\mathrm{Kol}}(W+R+D,N)\leq
d_{\mathrm{Kol}}(W,N)+2(\mathbb{E}R^{2})^{1/3}+\lvert D\rvert.$

###### Proof.

Fix $u>0$, on an event $E_{u}$ with probability at least $1-u^{-2}$, $\lvert
R\rvert\leq u\cdot\mathbb{E}^{1/2}R^{2}$. Then for any $t\in\mathbb{R}$

$\displaystyle\mathbb{P}(W+R+D\leq t)$ $\displaystyle\leq\mathbb{P}(W+D\leq
t+u\mathbb{E}^{1/2}R^{2})+u^{-2}$ $\displaystyle\leq\mathbb{P}(N\leq t+\lvert
D\rvert+u\mathbb{E}^{1/2}R^{2})+u^{-2}+d_{\mathrm{Kol}}(W,N)$
$\displaystyle\leq\mathbb{P}(N\leq t)+\lvert
D\rvert+u\mathbb{E}^{1/2}R^{2}+u^{-2}+d_{\mathrm{Kol}}(W,N).$

Optimizing the above display over $u>0$ to conclude one side of the
inequality. The reverse direction is similar. ∎

######  Lemma F.2.

For two random variables $X,Y$, with $\varphi_{Y}$ denoting the Lebesgue
density of $Y$, we have $d_{\mathrm{Kol}}^{2}(X,Y)\leq
4\lVert\varphi_{Y}\rVert_{\infty}d_{\mathrm{W}}(X,Y)$, where $d_{\mathrm{W}}$
is the Wasserstein distance.

###### Proof.

Fix $t\in\mathbb{R}$ and $\varepsilon>0$. Let $g_{t,\varepsilon}(\cdot)\equiv
1$ on $(-\infty,t]$, $g_{t,\varepsilon}(\cdot)\equiv 0$ on
$[t+\varepsilon,\infty)$ and be linearly interpolated on $(t,t+\varepsilon)$.
As $g_{t,\varepsilon}$ is $\varepsilon^{-1}$-Lipschitz,

$\displaystyle\mathbb{P}(X\leq t)-\mathbb{P}(Y\leq
t)\leq\mathbb{E}g_{t,\varepsilon}(X)-\mathbb{E}g_{t,\varepsilon}(Y)+\mathbb{E}g_{t,\varepsilon}(Y)-\mathbb{E}\bm{1}_{(-\infty,t]}(Y)$
$\displaystyle\leq\varepsilon^{-1}d_{\mathrm{W}}(X,Y)+\mathbb{P}\big{(}t\leq
Y\leq
t+\varepsilon\big{)}\leq\varepsilon^{-1}d_{\mathrm{W}}(X,Y)+\varepsilon\lVert\varphi_{Y}\rVert_{\infty}.$

Optimizing over $\varepsilon>0$ obtains the one-sided inequality. The other
direction is similar. ∎

######  Lemma F.3.

Suppose $Z,Z_{1},Z_{2},\ldots$ are independent copies of
$\mathcal{N}(0,I_{d})$. The following hold.

  1. (1)

For any matrices $A,B\in\mathbb{R}^{d\times d}$,

$\displaystyle\mathbb{E}(Z^{\top}AZ)(Z^{\top}BZ)=\operatorname{tr}(A)\operatorname{tr}(B)+\operatorname{tr}(AB)+\operatorname{tr}(AB^{\top}),$
$\displaystyle\mathbb{E}\big{(}Z^{\top}AZ-\operatorname{tr}(A)\big{)}\big{(}Z^{\top}BZ-\operatorname{tr}(B)\big{)}=\operatorname{tr}(AB)+\operatorname{tr}(AB^{\top}).$

  2. (2)

For any matrices $A,B\in\mathbb{R}^{d\times d}$,

$\displaystyle\mathbb{E}(Z_{1}^{\top}AZ_{2}Z_{2}^{\top}BZ_{1})^{2}$
$\displaystyle=2\big{(}\operatorname{tr}^{2}(AB)+\operatorname{tr}(ABAB)+2\operatorname{tr}(ABB^{\top}A^{\top})\big{)}$
$\displaystyle\qquad+\operatorname{tr}(AA^{\top})\operatorname{tr}(BB^{\top}).$

  3. (3)

For any matrix $A\in\mathbb{R}^{d\times d}$,

$\displaystyle\mathbb{E}(ZZ^{\top})(Z^{\top}AZ)=A+A^{\top}+\operatorname{tr}(A)I_{d}.$

###### Proof.

(1). Note that

$\displaystyle\mathbb{E}(Z^{\top}AZ)(Z^{\top}BZ)=\mathbb{E}\operatorname{tr}\big{(}AZZ^{\top}BZZ^{\top}\big{)}$
$\displaystyle=\mathbb{E}\sum_{i,j,k,\ell}A_{ij}(ZZ^{\top})_{jk}B_{k\ell}(ZZ^{\top})_{\ell
i}=\sum_{i,j,k,\ell}A_{ij}B_{k\ell}\cdot\mathbb{E}Z_{i}Z_{j}Z_{k}Z_{\ell}.$

To make the expectation on the right hand side non-vanishing:

  * •

$(i=j)\neq(k=\ell)$. This contributes to $\sum_{i\neq k}A_{ii}B_{kk}$.

  * •

$(i=k)\neq(j=\ell)$. This contributes to $\sum_{i,j}A_{ij}B_{ij}$.

  * •

$(i=\ell)\neq(j=k)$. This contributes to $\sum_{i,j}A_{ij}B_{ji}$.

  * •

$i=j=k=\ell$. This contributes to $3\sum_{i}A_{ii}B_{ii}$.

Collecting the terms to conclude the first equality. The second equality
follows a direct expansion.

(2). Note that

$\displaystyle\mathbb{E}(Z_{1}^{\top}AZ_{2}Z_{2}^{\top}BZ_{1})^{2}=\mathbb{E}\Big{[}\mathbb{E}\big{[}Z_{1}^{\top}\big{(}AZ_{2}Z_{2}^{\top}B\big{)}Z_{1}\cdot
Z_{1}^{\top}\big{(}AZ_{2}Z_{2}^{\top}B\big{)}Z_{1}\lvert Z_{2}\big{]}\Big{]}$
$\displaystyle=\mathbb{E}\operatorname{tr}^{2}(AZ_{2}Z_{2}^{\top}B)+\mathbb{E}\operatorname{tr}(AZ_{2}Z_{2}^{\top}BAZ_{2}Z_{2}^{\top}B)+\mathbb{E}\operatorname{tr}(AZ_{2}Z_{2}^{\top}BB^{\top}Z_{2}Z_{2}^{\top}A^{\top})$
$\displaystyle=\mathbb{E}\big{(}Z_{2}^{\top}BAZ_{2}\big{)}^{2}+\mathbb{E}\big{(}Z_{2}^{\top}BAZ_{2}\big{)}^{2}+\mathbb{E}Z_{2}^{\top}BB^{\top}Z_{2}\cdot
Z_{2}^{\top}A^{\top}AZ_{2}$
$\displaystyle=2\big{(}\operatorname{tr}^{2}(AB)+\operatorname{tr}(ABAB)+2\operatorname{tr}(ABB^{\top}A^{\top})\big{)}+\operatorname{tr}(BB^{\top})\operatorname{tr}(AA^{\top}).$

(3). For $i\neq j$,

$\displaystyle\big{(}\mathbb{E}(ZZ^{\top})(Z^{\top}AZ)\big{)}_{ij}$
$\displaystyle=\mathbb{E}\bigg{[}Z_{i}Z_{j}\sum_{k,\ell}Z_{k}A_{k\ell}Z_{\ell}\bigg{]}=A_{ij}+A_{ji}.$

For $i=j$,

$\displaystyle\big{(}\mathbb{E}(ZZ^{\top})(Z^{\top}AZ)\big{)}_{ii}$
$\displaystyle=\mathbb{E}\bigg{[}Z_{i}^{2}\sum_{k,\ell}Z_{k}A_{k\ell}Z_{\ell}\bigg{]}=\mathbb{E}Z_{i}^{4}\cdot
A_{ii}+\sum_{k\neq i}(\mathbb{E}Z_{i}^{2})(\mathbb{E}Z_{k}^{2})A_{kk}$
$\displaystyle=3A_{ii}+\sum_{k\neq i}A_{kk}=2A_{ii}+\operatorname{tr}(A).$

The proof is complete. ∎

######  Lemma F.4.

The following hold:

  1. (1)

$\mathbb{E}\lVert X_{1}\rVert^{2}\lVert
Y_{1}\rVert^{2}=\operatorname{tr}(\Sigma_{X})\operatorname{tr}(\Sigma_{Y})+2\lVert\Sigma_{XY}\rVert_{F}^{2}$.

  2. (2)

$\mathbb{E}(X_{1}^{\top}\Sigma_{XY}Y_{2})^{2}=\operatorname{tr}(\Sigma_{X}\Sigma_{XY}\Sigma_{Y}\Sigma_{YX})$.

  3. (3)

$\mathbb{E}(X_{1}^{\top}X_{2})^{2}(Y_{1}^{\top}Y_{2})^{2}=2\lVert\Sigma_{XY}\rVert_{F}^{4}+2\lVert\Sigma_{XY}\Sigma_{YX}\rVert_{F}^{2}+4\operatorname{tr}(\Sigma_{XY}\Sigma_{Y}\Sigma_{YX}\Sigma_{X})+\lVert\Sigma_{X}\rVert_{F}^{2}\lVert\Sigma_{Y}\rVert_{F}^{2}$.

  4. (4)

For any matrix $A,B$,

$\displaystyle\mathbb{E}(X_{1}^{\top}AY_{1})(X_{1}^{\top}BY_{1})=\operatorname{tr}(A\Sigma_{YX})\operatorname{tr}(B\Sigma_{YX})+\operatorname{tr}(A\Sigma_{YX}B\Sigma_{YX})+\operatorname{tr}(\Sigma_{X}A\Sigma_{Y}B^{\top}).$

In particular, for $A=B=\Sigma_{XY}$, we have
$\mathbb{E}(X_{1}^{\top}\Sigma_{XY}Y_{1})^{2}=\lVert\Sigma_{XY}\rVert_{F}^{4}+\lVert\Sigma_{XY}\Sigma_{YX}\rVert_{F}^{2}+\operatorname{tr}(\Sigma_{XY}\Sigma_{Y}\Sigma_{YX}\Sigma_{X})$.

  5. (5)

For any matrix $A,B$,

$\displaystyle\mathbb{E}(X_{1}^{\top}AX_{1})(Y_{1}^{\top}BY_{1})=\operatorname{tr}(A\Sigma_{X})\operatorname{tr}(B\Sigma_{Y})+\operatorname{tr}(A\Sigma_{XY}B\Sigma_{YX})+\operatorname{tr}(A\Sigma_{XY}B^{\top}\Sigma_{YX}).$

###### Proof.

(1) follows from

$\displaystyle\mathbb{E}\lVert X_{1}\rVert^{2}\lVert Y_{1}\rVert^{2}$
$\displaystyle=\mathbb{E}Z_{1}^{\top}H_{[11]}Z_{1}\cdot
Z_{1}^{\top}H_{[22]}Z_{1}$
$\displaystyle=\operatorname{tr}(H_{11})\operatorname{tr}(H_{22})+2\operatorname{tr}(H_{11}H_{22})=\operatorname{tr}(\Sigma_{X})\operatorname{tr}(\Sigma_{Y})+2\lVert\Sigma_{XY}\rVert_{F}^{2}.$

(2) follows from

$\displaystyle\mathbb{E}(X_{1}^{\top}\Sigma_{XY}Y_{2})^{2}$
$\displaystyle=\mathbb{E}\operatorname{tr}\big{(}\Sigma_{XY}Y_{2}Y_{2}^{\top}\Sigma_{XY}X_{1}X_{1}^{\top}\big{)}=\operatorname{tr}(\Sigma_{XY}\Sigma_{Y}\Sigma_{YX}\Sigma_{X}).$

(3). Note that

$\displaystyle\mathbb{E}(X_{1}^{\top}X_{2})^{2}(Y_{1}^{\top}Y_{2})^{2}=\mathbb{E}(Z_{1}^{\top}H_{[11]}Z_{2})^{2}\mathbb{E}(Z_{1}^{\top}H_{[22]}Z_{2})^{2}$
$\displaystyle=2\big{(}\operatorname{tr}^{2}(H_{[11]}H_{[22]})+\operatorname{tr}(H_{[11]}H_{[22]}H_{[11]}H_{[22]})+2\operatorname{tr}(H_{[11]}^{2}H_{[22]}^{2})\big{)}+\operatorname{tr}(H_{[11]}^{2})\operatorname{tr}(H_{[22]}^{2})$
$\displaystyle=2\lVert\Sigma_{XY}\rVert_{F}^{4}+2\lVert\Sigma_{XY}\Sigma_{YX}\rVert_{F}^{2}+4\operatorname{tr}(\Sigma_{XY}\Sigma_{Y}\Sigma_{YX}\Sigma_{X})+\lVert\Sigma_{X}\rVert_{F}^{2}\lVert\Sigma_{Y}\rVert_{F}^{2}.$

(4). Let $A_{\Sigma}\equiv\Sigma^{1/2}\begin{pmatrix}0&A\\\
0&0\end{pmatrix}\Sigma^{1/2},\quad
B_{\Sigma}\equiv\Sigma^{1/2}\begin{pmatrix}0&B\\\
0&0\end{pmatrix}\Sigma^{1/2}.$ Then

$\displaystyle\mathbb{E}(X_{1}^{\top}AY_{1})(X_{1}^{\top}BY_{1})$
$\displaystyle=\mathbb{E}(Z_{1}^{\top}A_{\Sigma}Z_{1})(Z_{1}^{\top}B_{\Sigma}Z_{1})=\operatorname{tr}(A_{\Sigma})\operatorname{tr}(B_{\Sigma})+\operatorname{tr}(A_{\Sigma}B_{\Sigma})+\operatorname{tr}(A_{\Sigma}B_{\Sigma}^{\top})$
$\displaystyle=\operatorname{tr}(A\Sigma_{YX})\operatorname{tr}(B\Sigma_{YX})+\operatorname{tr}(A\Sigma_{YX}B\Sigma_{YX})+\operatorname{tr}(\Sigma_{X}A\Sigma_{Y}B^{\top}).$

(5). Abusing notation, let $A_{\Sigma}\equiv\Sigma^{1/2}\begin{pmatrix}A&0\\\
0&0\end{pmatrix}\Sigma^{1/2},\quad
B_{\Sigma}\equiv\Sigma^{1/2}\begin{pmatrix}0&0\\\
0&B\end{pmatrix}\Sigma^{1/2}.$ Then

$\displaystyle\mathbb{E}(X_{1}^{\top}AX_{1})(Y_{1}^{\top}BY_{1})$
$\displaystyle=\mathbb{E}(Z_{1}^{\top}A_{\Sigma}Z_{1})(Z_{1}^{\top}B_{\Sigma}Z_{1})=\operatorname{tr}(A_{\Sigma})\operatorname{tr}(B_{\Sigma})+\operatorname{tr}(A_{\Sigma}B_{\Sigma})+\operatorname{tr}(A_{\Sigma}B_{\Sigma}^{\top})$
$\displaystyle=\operatorname{tr}(A\Sigma_{X})\operatorname{tr}(B\Sigma_{Y})+\operatorname{tr}(A\Sigma_{XY}B\Sigma_{YX})+\operatorname{tr}(A\Sigma_{XY}B^{\top}\Sigma_{YX}).$

The proof is complete. ∎

######  Lemma F.5.

It holds that
$\lVert\Sigma_{XY}\rVert_{F}^{2}\leq\lVert\Sigma_{X}\rVert_{F}\lVert\Sigma_{Y}\rVert_{F}$.
If in addition
$\lVert\Sigma_{X}^{-1}\rVert_{\operatorname{op}}\vee\lVert\Sigma_{Y}^{-1}\rVert_{\operatorname{op}}\leq
M$ for some $M>1$, then
$\lVert\Sigma_{XY}\rVert_{F}^{2}\lesssim_{M}\tau_{X}^{2}\wedge\tau_{Y}^{2}$.

###### Proof.

For the first claim, note that

$\displaystyle\lVert\Sigma_{XY}\rVert_{F}^{2}$
$\displaystyle=\operatorname{tr}\big{(}\mathbb{E}X_{1}Y_{1}^{\top}\mathbb{E}Y_{2}X_{2}^{\top}\big{)}=\mathbb{E}(X_{1}^{\top}X_{2})(Y_{1}^{\top}Y_{2})$
$\displaystyle\leq\mathbb{E}^{1/2}(X_{1}^{\top}X_{2})^{2}\cdot\mathbb{E}^{1/2}(Y_{1}^{\top}Y_{2})^{2}=\lVert\Sigma_{X}\rVert_{F}\lVert\Sigma_{Y}\rVert_{F},$

as desired. For the second claim, as the conditional covariance
$\Sigma_{X\backslash Y}=\Sigma_{X}-\Sigma_{XY}\Sigma_{Y}^{-1}\Sigma_{YX}$ is
p.s.d., we have

$\displaystyle\lVert\Sigma_{XY}\rVert_{F}^{2}\lesssim_{M}\operatorname{tr}(\Sigma_{XY}\Sigma_{Y}^{-1}\Sigma_{YX})\leq\operatorname{tr}(\Sigma_{X})=\tau_{X}^{2}/2.$

Flipping the role of $X,Y$ to conclude. ∎

## References

  * [And58] T. W. Anderson, _An introduction to multivariate statistical analysis_ , Wiley Publications in Statistics, John Wiley & Sons, Inc., New York; Chapman & Hall, Ltd., London, 1958.
  * [BD14] Wicher Bergsma and Angelos Dassios, _A consistent test of independence based on a sign covariance related to Kendall’s tau_ , Bernoulli 20 (2014), no. 2, 1006–1028.
  * [BKR61] J. R. Blum, J. Kiefer, and M. Rosenblatt, _Distribution free tests of independence based on the sample distribution function_ , Ann. Math. Statist. 32 (1961), 485–498.
  * [Cha08] Sourav Chatterjee, _A new method of normal approximation_ , Ann. Probab. 36 (2008), no. 4, 1584–1610.
  * [CM13] T. Tony Cai and Zongming Ma, _Optimal hypothesis testing for high dimensional covariance matrices_ , Bernoulli 19 (2013), no. 5B, 2359–2388.
  * [dW80] T. de Wet, _Cramér-von Mises tests for independence_ , J. Multivariate Anal. 10 (1980), no. 1, 38–50.
  * [Feu93] Andrey Feuerverger, _A consistent test for bivariate dependence_ , Int. Stat. Rev. 61 (1993), no. 2, 419–433.
  * [GBR+12] Arthur Gretton, Karsten M. Borgwardt, Malte J. Rasch, Bernhard Schölkopf, and Alexander Smola, _A kernel two-sample test_ , J. Mach. Learn. Res. 13 (2012), 723–773.
  * [GFLS21] Lan Gao, Yingying Fan, Jinchi Lv, and Qi-Man Shao, _Asymptotic distributions of high-dimensional distance correlation inference_ , Ann. Statist., to appear. Available at arXiv:1910.12970 (2021+).
  * [GFT+07] Arthur Gretton, Kenji Fukumizu, Choon Hui Teo, Le Song, Bernhard Schölkopf, and Alexander J Smola, _A kernel statistical test of independence._ , Advances in Neural Information Processing Systems, vol. 20, Citeseer, 2007, pp. 585–592.
  * [GHS+05] Arthur Gretton, Ralf Herbrich, Alexander Smola, Olivier Bousquet, and Bernhard Schölkopf, _Kernel methods for measuring independence_ , J. Mach. Learn. Res. 6 (2005), 2075–2129.
  * [HJS21] Qiyang Han, Tiefeng Jiang, and Yandi Shen, _A general method for power analysis in testing high dimensional covariance matrices_ , arXiv preprint arXiv:2101.11086 (2021).
  * [Hoe48] Wassily Hoeffding, _A non-parametric test of independence_ , Ann. Math. Statistics 19 (1948), 546–557.
  * [HS16] Xiaoming Huo and Gábor J. Székely, _Fast computing for distance covariance_ , Technometrics 58 (2016), no. 4, 435–447.
  * [Ken38] M. G. Kendall, _A new measure of rank correlation._ , Biometrika 30 (1938), 81–93.
  * [KKK+12] Jing Kong, Barbara EK Klein, Ronald Klein, Kristine E Lee, and Grace Wahba, _Using distance correlation and ss-anova to assess associations of familial relationships, lifestyle factors, diseases, and mortality_ , Proceedings of the National Academy of Sciences 109 (2012), no. 50, 20352–20357.
  * [Lyo13] Russell Lyons, _Distance covariance in metric spaces_ , Ann. Probab. 41 (2013), no. 5, 3284–3305.
  * [LZZ12] Runze Li, Wei Zhong, and Liping Zhu, _Feature screening via distance correlation learning_ , J. Amer. Statist. Assoc. 107 (2012), no. 499, 1129–1139.
  * [MT17] David S. Matteson and Ruey S. Tsay, _Independent component analysis via distance covariance_ , J. Amer. Statist. Assoc. 112 (2017), no. 518, 623–637.
  * [Mui82] Robb J. Muirhead, _Aspects of multivariate statistical theory_ , John Wiley & Sons, Inc., New York, 1982, Wiley Series in Probability and Mathematical Statistics.
  * [Pea95] K Pearson, _Notes on regression and inheritance in the case of two parents_ , Proceedings of the Royal Society of London 58 (1895), 240–242.
  * [Ros75] M. Rosenblatt, _A quadratic measure of deviation of two-dimensional density estimates and a test of independence_ , Ann. Statist. 3 (1975), 1–14.
  * [Ser80] Robert J. Serfling, _Approximation theorems of mathematical statistics_ , John Wiley & Sons, Inc., New York, 1980, Wiley Series in Probability and Mathematical Statistics.
  * [Spe04] C. Spearman, _The proof and measurement of association between two things._ , The American Journal of Psychology 15 (1904), 72–101.
  * [SR09] Gábor J. Székely and Maria L. Rizzo, _Brownian distance covariance_ , Ann. Appl. Stat. 3 (2009), no. 4, 1236–1265.
  * [SR13] by same author, _The distance correlation $t$-test of independence in high dimension_, J. Multivariate Anal. 117 (2013), 193–213.
  * [SR14] by same author, _Partial distance correlation with methods for dissimilarities_ , Ann. Statist. 42 (2014), no. 6, 2382–2412.
  * [SRB07] Gábor J. Székely, Maria L. Rizzo, and Nail K. Bakirov, _Measuring and testing dependence by correlation of distances_ , Ann. Statist. 35 (2007), no. 6, 2769–2794.
  * [SSGF13] Dino Sejdinovic, Bharath Sriperumbudur, Arthur Gretton, and Kenji Fukumizu, _Equivalence of distance-based and RKHS-based statistics in hypothesis testing_ , Ann. Statist. 41 (2013), no. 5, 2263–2291.
  * [SZ14] Xiaofeng Shao and Jingsi Zhang, _Martingale difference correlation and its use in high-dimensional variable screening_ , J. Amer. Statist. Assoc. 109 (2014), no. 507, 1302–1318.
  * [Tsy09] Alexandre B. Tsybakov, _Introduction to Nonparametric Estimation_ , Springer Series in Statistics, Springer, New York, 2009, Revised and extended from the 2004 French original, Translated by Vladimir Zaiats.
  * [WDM18] L. Weihs, M. Drton, and N. Meinshausen, _Symmetric rank covariances: a generalized framework for nonparametric measures of dependence_ , Biometrika 105 (2018), no. 3, 547–562.
  * [Yan70] T. Yanagimoto, _On measures of association and a related problem_ , Ann. Inst. Statist. Math. 22 (1970), no. 1, 57–63.
  * [YZS18] Shun Yao, Xianyang Zhang, and Xiaofeng Shao, _Testing mutual independence in high dimension via distance covariance_ , J. R. Stat. Soc. Ser. B. Stat. Methodol. 80 (2018), no. 3, 455–480.
  * [ZYS18] Xianyang Zhang, Shun Yao, and Xiaofeng Shao, _Conditional mean and quantile dependence testing in high dimension_ , Ann. Statist. 46 (2018), no. 1, 219–246.
  * [ZZYS20] Changbo Zhu, Xianyang Zhang, Shun Yao, and Xiaofeng Shao, _Distance-based and RKHS-based dependence metrics in high dimension_ , Ann. Statist. 48 (2020), no. 6, 3366–3394.