$\displaystyle=\bigg{(}\frac{\bar{\sigma}_{n}}{\sigma_{0}}-1\bigg{)}^{2}\cdot\frac{\operatorname{Var}\big{(}\operatorname{dCov}_{\ast}^{2}(\bm{X},\bm{Y})\big{)}}{\bar{\sigma}_{n}^{2}}\lesssim_{M}\big{(}\rho(A)+\rho^{2}(A)\big{)}^{2}.$

On the other hand, by Theorem 8.5 we have

$\displaystyle\lvert\Delta_{2}\rvert$
$\displaystyle\lesssim_{M}\frac{A}{(p\wedge q)^{1/2}}\lesssim\rho(A).$

The claim follows by collecting the estimates and using $1\wedge t\lesssim
1\wedge t^{\alpha}$ for $\alpha\in(0,1)$. ∎

##  12\. Proof of Theorem 3.1

######  Lemma 12.1.

Suppose that the spectrum of $\Sigma$ is contained in $[1/M,M]$ for some
$M>1$. Then with $\Delta_{X}$ and $\Delta_{Y}$ defined by

$\displaystyle\frac{\operatorname{dCov}_{\ast}(\bm{X})}{\operatorname{dCov}(X)}\equiv
1+\Delta_{X},\quad\frac{\operatorname{dCov}_{\ast}(\bm{Y})}{\operatorname{dCov}(Y)}\equiv
1+\Delta_{Y},$

we have $\mathbb{E}\Delta_{X}^{2}\vee\mathbb{E}\Delta_{Y}^{2}\leq C(n\wedge
p\wedge q)^{-2}$ for some constant $C=C(M)>0$.

###### Proof.

By mean and variance expansions in Theorems 8.5 and 9.12,

$\displaystyle\operatorname{dCov}^{2}(X)=\frac{\lVert\Sigma_{X}\rVert_{F}^{2}}{\tau_{X}^{2}}\Big{[}1+\mathcal{O}_{M}(\tau_{X}^{-1})\Big{]},\quad\operatorname{Var}\big{(}\operatorname{dCov}_{\ast}^{2}(\bm{X})\big{)}\lesssim_{M}\frac{\lVert\Sigma_{X}\rVert_{F}^{2}}{n\tau_{X}^{4}}+\frac{\lVert\Sigma_{X}\rVert_{F}^{4}}{n^{2}\tau_{X}^{4}}.$

Then

$\displaystyle\mathbb{E}\Delta_{X}^{2}$
$\displaystyle=\mathbb{E}\Big{[}\frac{\operatorname{dCov}_{\ast}^{2}(\bm{X})-\operatorname{dCov}^{2}(X)}{\operatorname{dCov}(X)(\operatorname{dCov}_{*}(\bm{X})+\operatorname{dCov}(X))}\Big{]}^{2}$
$\displaystyle\leq\operatorname{dCov}^{-4}(X)\cdot\mathbb{E}\Big{(}\operatorname{dCov}_{\ast}^{2}(\bm{X})-\operatorname{dCov}^{2}(X)\Big{)}^{2}$
$\displaystyle=\operatorname{dCov}^{-4}(X)\cdot\operatorname{Var}\big{(}\operatorname{dCov}_{\ast}^{2}(\bm{X})\big{)}\asymp_{M}(n\tau_{X}^{2})^{-1}+n^{-2}\lesssim_{M}(n\wedge
p\wedge q)^{-2}.$

Similar bounds can be derived for $\Delta_{Y}$. ∎

###### Proof of Theorem 3.1.

Let
$d_{X,Y}^{2}\equiv\operatorname{dCov}^{2}(X)\cdot\operatorname{dCov}^{2}(Y)$,
and $\Delta_{d}$ be defined by
$d_{X,Y}\big{/}\big{(}\frac{\lVert\Sigma_{X}\rVert_{F}}{\tau_{X}}\cdot\frac{\lVert\Sigma_{Y}\rVert_{F}}{\tau_{Y}}\big{)}=1+\Delta_{d}$.
Then by Theorem 8.5,
$\Delta_{d}=\mathcal{O}_{M}\big{(}(\tau_{X}\wedge\tau_{Y})^{-1}\big{)}$.
Recall the definitions of (random) $\Delta_{X}$ and $\Delta_{Y}$ in Lemma
12.1, and note that by definition $\Delta_{d},\Delta_{X},\Delta_{Y}\geq-1$.
For any $t\geq 0$,

$\displaystyle\mathfrak{p}_{n}(t)$
$\displaystyle\equiv\mathbb{P}\bigg{(}\frac{n\cdot\operatorname{dCov}_{\ast}^{2}(\bm{X},\bm{Y})}{\sqrt{2\operatorname{dCov}_{\ast}^{2}(\bm{X})\cdot\operatorname{dCov}_{\ast}^{2}(\bm{Y})}}\leq
t\bigg{)}=\mathbb{P}\bigg{(}\frac{n\cdot\operatorname{dCov}_{\ast}^{2}(\bm{X},\bm{Y})}{\sqrt{2}d_{X,Y}}\leq
t(1+\Delta_{X})(1+\Delta_{Y})\bigg{)}$
$\displaystyle=\mathbb{P}\bigg{(}\frac{n\cdot\tau_{X}\tau_{Y}\operatorname{dCov}_{\ast}^{2}(\bm{X},\bm{Y})}{\sqrt{2}\lVert\Sigma_{X}\rVert_{F}\lVert\Sigma_{Y}\rVert_{F}}\leq
t(1+\Delta_{X})(1+\Delta_{Y})(1+\Delta_{d})\bigg{)}.$ (12.1)

Let $\Delta_{1}$ be defined by
$(1+\Delta_{X})(1+\Delta_{Y})(1+\Delta_{d})=1+\Delta_{1}+\Delta_{d}$. Then
Lemma 12.1 yields that $\mathbb{E}\Delta_{1}^{2}\lesssim_{M}(n\wedge p\wedge
q)^{-2}$. From (12), it holds for any $\delta_{1},\delta_{d}\in(0,1/2]$,

$\displaystyle\mathfrak{p}_{n}(t)\leq\mathbb{P}\bigg{(}\frac{n\cdot\tau_{X}\tau_{Y}\operatorname{dCov}_{\ast}^{2}(\bm{X},\bm{Y})}{\sqrt{2}\lVert\Sigma_{X}\rVert_{F}\lVert\Sigma_{Y}\rVert_{F}}\leq
t(1+\delta_{1}+\delta_{d})\bigg{)}+\mathbb{P}(|\Delta_{1}|\geq\delta_{1})+\bm{1}_{|\Delta_{d}|\geq\delta_{d}}$
$\displaystyle\leq\mathbb{P}\bigg{(}\frac{n\cdot\tau_{X}\tau_{Y}\operatorname{dCov}_{\ast}^{2}(\bm{X},\bm{Y})}{\sqrt{2}\lVert\Sigma_{X}\rVert_{F}\lVert\Sigma_{Y}\rVert_{F}}\leq
t(1+\delta_{1}+\delta_{d})\bigg{)}+\frac{C_{M}(n\wedge p\wedge
q)^{-2}}{\delta_{1}^{2}}+\bm{1}_{|\Delta_{d}|\geq\delta_{d}},$ (12.2)

using the bound on $\mathbb{E}\Delta_{1}^{2}$ in the second inequality. Next
we give two estimates for the upper bound of $\mathfrak{p}_{n}(t)$ useful for
different magnitudes of $A\equiv A(\Sigma)$.

(Estimate 1). By the local central limit theorem in Theorem 2.6, with $A$
defined therein, $\rho(A)=A/(n\wedge p\wedge q)^{1/2}$, and

$\displaystyle e(A)\equiv 1\bigwedge\bigg{(}\frac{1\vee A^{2}}{n\wedge p\wedge
q}\bigg{)}^{1/6}\leq(n\wedge p\wedge q)^{-1/6}+1\wedge\rho^{1/3}(A),$

we have by using
$\Delta_{d}=\mathcal{O}_{M}\big{(}(\tau_{X}\wedge\tau_{Y})^{-1}\big{)}$

$\displaystyle\mathfrak{p}_{n}(t)\leq\inf_{\delta_{1},\delta_{d}\in(0,1/2)}\bigg{\\{}\Phi\bigg{[}t(1+\delta_{1}+\delta_{d})-\frac{A}{\sqrt{2}}\bigg{]}+C_{M}\cdot
e(A)+\frac{C_{M}^{\prime}(n\wedge p\wedge
q)^{-2}}{\delta_{1}^{2}}+\bm{1}_{|\Delta_{d}|\geq\delta_{d}}\bigg{\\}}$
$\displaystyle\leq\Phi\bigg{(}t-\frac{A}{\sqrt{2}}\bigg{)}+C_{t,M}\bigg{[}\inf_{\delta_{1}\in(0,1/2]}\Big{(}\delta_{1}+\frac{(n\wedge
p\wedge
q)^{-2}}{\delta_{1}^{2}}\Big{)}+\inf_{\delta_{d}\in(0,1/2]}(\delta_{d}+\bm{1}_{|\Delta_{d}|\geq\delta_{d}})+e(A)\bigg{]}$
$\displaystyle\leq\Phi\bigg{(}t-\frac{A}{\sqrt{2}}\bigg{)}+C_{t,M}\cdot\big{[}(n\wedge
p\wedge q)^{-1/6}+1\wedge\rho^{1/3}(A)\big{]}.$

(Estimate 2). Note that by Theorem 8.5 and (11.2), we have

$\displaystyle\mathbb{E}\bigg{[}\frac{n\cdot\tau_{X}\tau_{Y}\operatorname{dCov}_{\ast}^{2}(\bm{X},\bm{Y})}{\sqrt{2}\lVert\Sigma_{X}\rVert_{F}\lVert\Sigma_{Y}\rVert_{F}}\bigg{]}$
$\displaystyle=\frac{A}{\sqrt{2}}\big{(}1+\mathcal{O}_{M}((p\wedge
q)^{-1/2}\big{)},$
$\displaystyle\operatorname{Var}\bigg{[}\frac{n\cdot\tau_{X}\tau_{Y}\operatorname{dCov}_{\ast}^{2}(\bm{X},\bm{Y})}{\sqrt{2}\lVert\Sigma_{X}\rVert_{F}\lVert\Sigma_{Y}\rVert_{F}}\bigg{]}$
$\displaystyle\asymp_{M}1\vee\rho^{2}(A).$

Hence by choosing $u=A/(2\sqrt{2}C_{M}(1+\rho(A)))$, and
$\delta_{1}=\delta_{d}=1/2$ in (12), we have

$\displaystyle\mathfrak{p}_{n}(t)$
$\displaystyle\leq\mathbb{P}\big{(}A/\sqrt{2}-C_{M}\cdot u(1+\rho(A))\leq
2t\big{)}+u^{-2}+C_{M}(n\wedge p\wedge q)^{-2}$
$\displaystyle\leq\bm{1}_{A\leq
4\sqrt{2}t}+C_{M}\cdot\Big{(}\big{[}1+\rho(A)^{2}\big{]}/A^{2}+(n\wedge
p\wedge q)^{-2}\Big{)}.$

which implies

$\displaystyle\mathfrak{p}_{n}(t)-\Phi\bigg{(}t-\frac{A}{\sqrt{2}}\bigg{)}\leq
C_{t,M}\bigg{(}e^{-A^{2}/C}+\frac{1+\rho^{2}(A)}{A^{2}}+\bm{1}_{A\leq
4\sqrt{2}t}+\frac{1}{(n\wedge p\wedge q)^{2}}\bigg{)}.$

Combining the estimates (1) and (2), we have

$\displaystyle\mathfrak{p}_{n}(t)-\Phi\bigg{(}t-\frac{A}{\sqrt{2}}\bigg{)}$
$\displaystyle\leq C_{t,M}\bigg{[}\bigg{(}(n\wedge p\wedge
q)^{-1/6}+1\wedge\rho^{1/3}(A)\bigg{)}$
$\displaystyle\quad\quad\quad\bigwedge\bigg{(}e^{-A^{2}/C}+\frac{1}{A^{2}}+\bm{1}_{A\leq
4\sqrt{2}t}+\frac{1}{n\wedge p\wedge q}\bigg{)}\bigg{]}.$

The term in the bracket can be bounded by, via balancing the leading terms
$\rho^{1/3}(A)$ and $A^{-2}$,

$\displaystyle\mathfrak{p}_{n}(t)-\Phi\bigg{(}t-\frac{A}{\sqrt{2}}\bigg{)}\leq\frac{C_{t,M}}{(n\wedge
p\wedge q)^{1/7}}.$ (12.3)

By applying similar arguments to the other direction (lower bound) and the
case $t\leq 0$, we arrive at

$\displaystyle\Big{|}\mathfrak{p}_{n}(t)-\Phi\bigg{(}t-\frac{A}{\sqrt{2}}\bigg{)}\Big{|}\leq\frac{C_{t,M}}{(n\wedge
p\wedge q)^{1/7}},\quad t\in\mathbb{R}.$

Finally, using Theorem 8.5 and its analogous expansion to
$\operatorname{dCov}^{2}(X),\operatorname{dCov}^{2}(Y)$, we have

$\displaystyle
n\operatorname{dCor}^{2}(X,Y)=\frac{n\operatorname{dCov}^{2}(X,Y)}{\sqrt{\operatorname{dCov}^{2}(X)\operatorname{dCov}^{2}(Y)}}$
$\displaystyle=\frac{n\lVert\Sigma_{XY}\rVert_{F}^{2}}{\lVert\Sigma_{X}\rVert_{F}\lVert\Sigma_{Y}\rVert_{F}}\Big{[}1+\mathcal{O}_{M}\big{(}(\tau_{X}\wedge\tau_{Y})^{-1}\big{)}\Big{]}=A\Big{[}1+\mathcal{O}_{M}\big{(}(\tau_{X}\wedge\tau_{Y})^{-1}\big{)}\Big{]},$

the $A$ term in (12.3) can be replaced by $n\operatorname{dCor}^{2}(X,Y)$ at
the lost of a larger constant $C_{t,M}$ by [HJS21, Lemma 2.4]. ∎

##  13\. Proof of Theorem 3.3

###### Proof of Theorem 3.3.

Let $\phi_{\Sigma}$ denote the Lebesgue density for $\mathcal{N}(0,\Sigma)$.
For any prior $\Pi$ on $\Theta(\zeta,\Sigma_{0})$, let $P_{\Pi}$ the
probability measure corresponding to the density $\phi_{\Pi}(x)\equiv\int
p_{\Sigma}(x)\,\mathrm{d}\Pi(\Sigma)$. Then

$\displaystyle\inf_{\psi}\sup_{\Sigma\in\Theta(\zeta,\Sigma_{0})}\big{(}\mathbb{E}_{\Sigma_{0}}\psi+\mathbb{E}_{\Sigma}(1-\psi)\big{)}\geq\inf_{\psi}\big{(}P_{\Sigma_{0}}(\psi)+P_{\Pi}(1-\psi)\big{)}$
$\displaystyle=1-d_{\textrm{TV}}(P_{\Pi},P_{0})\geq
1-\bigg{(}\int\frac{\phi_{\Pi}^{2}}{\phi_{\Sigma_{0}}}-1\bigg{)}^{1/2}.$

The last inequality follows from, e.g. [Tsy09, Equation (2.27), pp. 90]. So
the goal is to find the smallest possible $\zeta>0$ so that the right hand
side of the above display has a non-trivial lower bound under a constructed
prior $\Pi$ on $\Theta(\zeta,\Sigma_{0})$.

First consider the case $\Sigma_{0}=I$. For any
$\widetilde{u}\in\mathbb{R}^{p}$ and $\widetilde{v}\in\mathbb{R}^{q}$, let
$u\equiv[\widetilde{u},0_{q}]\in\mathbb{R}^{p+q}$ and
$v\equiv[0_{p},\widetilde{v}]\in\mathbb{R}^{p+q}$. For any $a>0$, let

$\displaystyle\Sigma_{u,v}\equiv\Sigma_{u,v}(a)\equiv
I+a\big{(}uv^{\top}+vu^{\top}\big{)}=\begin{pmatrix}I&a\widetilde{u}\widetilde{v}^{\top}\\\
a\widetilde{v}\widetilde{u}^{\top}&I\end{pmatrix}.$

We place independent priors
$\widetilde{u}_{i}\sim_{\textrm{i.i.d.}}\sqrt{q}\cdot\textrm{Unif}\\{\pm 1\\}$
on $\widetilde{u}$ and
$\widetilde{v}_{j}\sim_{\textrm{i.i.d.}}\sqrt{p}\cdot\textrm{Unif}\\{\pm 1\\}$
on $\widetilde{v}$, so that $\lVert\widetilde{u}\rVert^{2}=\lVert
u\rVert^{2}=\lVert\widetilde{v}\rVert^{2}=\lVert v\rVert^{2}=pq$ and
$\left\langle u,v\right\rangle=0$. Then by direct calculation,

$\displaystyle(uv^{\top}+vu^{\top})(u+v)=u\cdot\lVert v\rVert^{2}+v\cdot\lVert
u\rVert^{2}=pq\cdot(u+v),$
$\displaystyle(uv^{\top}+vu^{\top})(u-v)=-u\cdot\lVert
v\rVert^{2}+v\cdot\lVert u\rVert^{2}=-pq\cdot(u-v).$

This entails that the rank two matrix $(uv^{\top}+vu^{\top})$ has eigenvalue
$pq$ with eigenvector $u+v$ and eigenvalue $-pq$ with eigenvector $u-v$. Hence
$\Sigma_{u,v}$ has eigenvalues $1+apq$ with eigenvector $u+v$, $1-apq$ with
eigenvector $u-v$, and all rest eigenvalues as $1$, hence
$\det(\Sigma_{u,v})=1-(apq)^{2}$. So by writing $\\{s_{i}\\}_{i=1}^{p+q-2}$ as
a basis for the orthogonal complement of $u+v$ and $u-v$ in
$\mathbb{R}^{p+q}$, we have the eigenvalue decomposition

$\displaystyle\Sigma_{u,v}=\sum_{i=1}^{p+q-2}s_{i}s_{i}^{\top}+(1+apq)\frac{(u+v)(u+v)^{\top}}{\lVert
u+v\rVert^{2}}+(1-apq)\frac{(u-v)(u-v)^{\top}}{\lVert u-v\rVert^{2}}.$

This implies that

$\displaystyle\Sigma_{u,v}^{-1}$
$\displaystyle=\sum_{i=1}^{p+q-2}s_{i}s_{i}^{\top}+\frac{1}{1+apq}\frac{(u+v)(u+v)^{\top}}{\lVert
u+v\rVert^{2}}+\frac{1}{1-apq}\frac{(u-v)(u-v)^{\top}}{\lVert u-v\rVert^{2}}$
$\displaystyle=\Big{[}I-\frac{(u+v)(u+v)^{\top}}{\lVert
u+v\rVert^{2}}-\frac{(u-v)(u-v)^{\top}}{\lVert u-v\rVert^{2}}\Big{]}$
$\displaystyle\quad\quad+\frac{1}{1+apq}\frac{(u+v)(u+v)^{\top}}{\lVert
u+v\rVert^{2}}+\frac{1}{1-apq}\frac{(u-v)(u-v)^{\top}}{\lVert u-v\rVert^{2}}$
$\displaystyle=I-\frac{apq}{1+apq}\frac{(u+v)(u+v)^{\top}}{\lVert
u+v\rVert^{2}}+\frac{apq}{1-apq}\frac{(u-v)(u-v)^{\top}}{\lVert
u-v\rVert^{2}}$
$\displaystyle=I-\frac{a}{2(1+apq)}(u+v)(u+v)^{\top}+\frac{a}{2(1-apq)}(u-v)(u-v)^{\top}.$

Let $\phi_{\Pi}$ be the joint density of $\\{(X_{i},Y_{i})\\}_{i=1}^{n}$ under
the prescribed prior on $\widetilde{u}$ and $\widetilde{v}$, and $\phi_{I}$ be
the joint density under the null. With

$\displaystyle\widetilde{\Sigma}(u_{1},u_{2},v_{1},v_{2})$
$\displaystyle\equiv-\frac{a}{2(1+apq)}(u_{1}+v_{1})(u_{1}+v_{1})^{\top}+\frac{a}{2(1-apq)}(u_{1}-v_{1})(u_{1}-v_{1})^{\top}$
$\displaystyle\qquad-\frac{a}{2(1+apq)}(u_{2}+v_{2})(u_{2}+v_{2})^{\top}+\frac{a}{2(1-apq)}(u_{2}-v_{2})(u_{2}-v_{2})^{\top},$
(13.1)

we have

$\displaystyle\int\frac{\phi_{\Pi}^{2}}{\phi_{I}}$
$\displaystyle=\int\frac{\Big{[}\sum_{u,v}2^{-(p+q)}(2\pi)^{-n(p+q)/2}\det^{-n/2}(\Sigma_{u,v})e^{-\frac{1}{2}\cdot\sum_{i=1}^{n}x_{i}^{\top}\Sigma_{u,v}^{-1}x_{i}}\Big{]}^{2}}{(2\pi)^{-n(p+q)/2}\det^{-n/2}(I_{p+q})e^{-\frac{1}{2}\cdot\sum_{i=1}^{n}\lVert
x_{i}\rVert^{2}}}\,\mathrm{d}x$
$\displaystyle=\sum_{(u_{1},v_{1}),(u_{2},v_{2})}\frac{2^{-2(p+q)}}{\big{[}(1-(apq)^{2}\big{]}^{n}}\int(2\pi)^{-n(p+q)/2}e^{-\frac{1}{2}\cdot\sum_{i=1}^{n}x_{i}^{\top}[\Sigma_{u_{1},v_{1}}^{-1}+\Sigma_{u_{2},v_{2}}^{-1}-I]x_{i}}\,\mathrm{d}x$
$\displaystyle\equiv\sum_{(u_{1},v_{1}),(u_{2},v_{2})}\frac{2^{-2(p+q)}}{\big{[}1-(apq)^{2}\big{]}^{n}}\int(2\pi)^{-n(p+q)/2}e^{-\frac{1}{2}\cdot\sum_{i=1}^{n}x_{i}^{\top}(I+\widetilde{\Sigma}(u_{1},u_{2},v_{1},v_{2}))x_{i}}\,\mathrm{d}x$
$\displaystyle\stackrel{{\scriptstyle(*)}}{{=}}\mathbb{E}_{(u_{1},v_{1}),(u_{2},v_{2})}\bigg{[}\frac{1}{\big{[}1-(apq)^{2}\big{]}^{n}}\det\big{(}I+\widetilde{\Sigma}(u_{1},u_{2},v_{1},v_{2})\big{)}^{-n/2}\bigg{]}.$

Here in $(*)$, $(u_{1},v_{1})$ and $(u_{2},v_{2})$ denote two independent
copies of the prescribed prior on $(u,v)$.

By Lemma 13.1 and the notation
$\\{\lambda_{i}=\lambda_{i}(u_{1},u_{2},v_{1},v_{2})\\}_{i=1}^{4}$ therein,
$I+\widetilde{\Sigma}$ has $p+q-4$ eigenvalues of $1$, and the other four
eigenvalues being $1+\lambda_{i}$, $1\leq i\leq 4$. Hence by the second claim
of Lemma 13.1, for any $a$ such that $apq\leq 1/4$, we have

$\displaystyle\int\frac{\phi_{\Pi}^{2}}{\phi_{I}}$
$\displaystyle=\mathbb{E}_{(u_{1},v_{1}),(u_{2},v_{2})}\Big{[}\frac{1}{\big{[}1-(apq)^{2}\big{]}^{n}}\cdot\frac{1}{\big{[}(1+\lambda_{1})(1+\lambda_{2})(1+\lambda_{3})(1+\lambda_{4})\big{]}^{n/2}}\Big{]}$
$\displaystyle=\mathbb{E}_{(u_{1},v_{1}),(u_{2},v_{2})}\Big{[}\frac{1}{\big{[}1-(apq)^{2}\big{]}^{n}\cdot\big{[}1+\frac{a^{2}}{1-(apq)^{2}}(p^{2}q^{2}-\left\langle
u_{1},u_{2}\right\rangle\left\langle
v_{1},v_{2}\right\rangle)\big{]}^{n}}\Big{]}$
$\displaystyle=\mathbb{E}_{(u_{1},v_{1}),(u_{2},v_{2})}\Big{[}\frac{1}{\big{(}1-a^{2}\left\langle
u_{1},u_{2}\right\rangle\left\langle
v_{1},v_{2}\right\rangle\big{)}^{n}}\Big{]}$
$\displaystyle=1+n\mathbb{E}\big{(}a^{2}\left\langle
u_{1},u_{2}\right\rangle\left\langle v_{1},v_{2}\right\rangle\big{)}$
$\displaystyle\qquad+n(n+1)\mathbb{E}\bigg{[}\big{(}a^{2}\left\langle
u_{1},u_{2}\right\rangle\left\langle
v_{1},v_{2}\right\rangle\big{)}^{2}\int_{0}^{1}\frac{1-t}{\big{(}1-ta^{2}\left\langle
u_{1},u_{2}\right\rangle\left\langle
v_{1},v_{2}\right\rangle\big{)}^{n+2}}\,\mathrm{d}t\bigg{]}.$

To calculate the right hand side of the above display, first note that the
first order term vanishes: $\mathbb{E}(a^{2}\left\langle
u_{1},u_{2}\right\rangle\left\langle v_{1},v_{2}\right\rangle)=0$. Next we
compute the second order term. With $\varepsilon_{i}$’s denoting i.i.d.
Rademacher random variables,

$\displaystyle\mathbb{E}\big{(}a^{2}\left\langle
u_{1},u_{2}\right\rangle\left\langle
v_{1},v_{2}\right\rangle\big{)}^{4}=a^{8}p^{4}q^{4}\cdot\mathbb{E}\bigg{(}\sum_{i=1}^{p}\varepsilon_{i}\bigg{)}^{4}\cdot\mathbb{E}\bigg{(}\sum_{i=1}^{q}\varepsilon_{i}\bigg{)}^{4}\lesssim
a^{8}p^{6}q^{6}.$

On the other hand, under $a^{2}p^{2}q^{2}\leq 1/2$, there exists some absolute
constant $c_{0}>0$ such that for any $t\in[0,1]$,

$\displaystyle\mathbb{E}\bigg{[}\frac{1}{\big{(}1-ta^{2}\left\langle
u_{1},u_{2}\right\rangle\left\langle
v_{1},v_{2}\right\rangle\big{)}^{2(n+2)}}\bigg{]}\leq\mathbb{E}e^{c_{0}a^{2}n\left\langle
u_{1},u_{2}\right\rangle\left\langle v_{1},v_{2}\right\rangle}$
$\displaystyle=\mathbb{E}e^{c_{0}a^{2}npq\sum_{i=1}^{p}\varepsilon_{i}\sum_{j=1}^{q}\varepsilon_{j}^{\prime}}\leq\mathbb{E}\exp\bigg{[}(c_{0}^{2}/2)a^{4}n^{2}p^{3}q^{3}\bigg{(}\frac{1}{\sqrt{q}}\sum_{j=1}^{q}\varepsilon_{j}^{\prime}\bigg{)}^{2}\bigg{]}.$

Under $c_{0}^{2}a^{4}n^{2}p^{3}q^{3}\leq 1/2$, the above display is bounded by
an absolute constant. Collecting all the estimates, we have established that
if

$\displaystyle\max\big{\\{}a^{2}p^{2}q^{2},c_{0}^{2}a^{4}n^{2}p^{3}q^{3}\big{\\}}\leq
1/2,$ (13.2)

the following bound holds: for some absolute constant $C>0$,

$\displaystyle\int\frac{\phi_{\Pi}^{2}}{\phi_{I}}-1\leq C\cdot
a^{4}n^{2}p^{3}q^{3}.$

Now for any $\delta>0$, by taking $a_{*}=\tau n^{-1/2}p^{-3/4}q^{-3/4}$ for
some sufficiently small $\tau=\tau(\delta)>0$, we have
$\int\phi_{\Pi}^{2}/\phi_{I}-1\leq\delta$ and (13.2) is satisfied. As
$\Sigma_{u,v}(a^{*})\in\Theta(\zeta)$ for such choice of $a_{*}$ and any
realization of $(u,v)$, this completes the proof for the lower bound when
$\Sigma_{0}=I$ of the order $\lVert
a_{*}uv^{\top}\rVert_{F}^{2}=a_{*}^{2}\lVert u\rVert^{2}\lVert
v\rVert^{2}=a_{*}^{2}p^{2}q^{2}\asymp\sqrt{pq}/n$. For the general case
$\Sigma_{0}$, we may proceed with the above calculations using
$\Sigma_{0}^{1/2}\Sigma_{u,v}\Sigma_{0}^{1/2}$ instead of $\Sigma_{u,v}$,
which gives the same separation rate under the assumption on the spectrum of
$\Sigma_{X},\Sigma_{Y}$. ∎

######  Lemma 13.1.

The matrix $\widetilde{\Sigma}(u_{1},u_{2},v_{1},v_{2})$ defined in (13) has
at most 4 nontrivial eigenvalues of the form:

$\displaystyle\lambda_{i}$ $\displaystyle=(c_{2}-c_{1})(pq+\left\langle
u_{1},u_{2}\right\rangle)-\beta_{i}(c_{1}+c_{2})(\left\langle
v_{1},v_{2}\right\rangle+pq),\quad i=1,2,$ $\displaystyle\lambda_{i}$
$\displaystyle=(c_{2}-c_{1})(pq-\left\langle
u_{1},u_{2}\right\rangle)+\beta_{i}(c_{1}+c_{2})(\left\langle
v_{1},v_{2}\right\rangle-pq),\quad i=3,4.$

Here $(\beta_{1},\beta_{2})$ and $(\beta_{3},\beta_{4})$ are solutions to
equations (13) and (13) below, respectively. Furthermore,

$\displaystyle(1+\lambda_{1})(1+\lambda_{2})=(1+\lambda_{3})(1+\lambda_{4})=1+\frac{a^{2}}{1-(apq)^{2}}(p^{2}q^{2}-\left\langle
u_{1},u_{2}\right\rangle\left\langle v_{1},v_{2}\right\rangle).$

###### Proof of Lemma 13.1.

We write $\widetilde{\Sigma}(u_{1},u_{2},v_{1},v_{2})$ as $\widetilde{\Sigma}$
in the proof for simplicity. Define

$\displaystyle b$
$\displaystyle\equiv\alpha_{1}u_{1}+\alpha_{2}u_{2}+\alpha_{3}v_{1}+\alpha_{4}v_{2},\quad
c_{1}\equiv\frac{a}{2(1+apq)},\quad c_{2}=\frac{a}{2(1-apq)}.$

Then

$\displaystyle\widetilde{\Sigma}$ $\displaystyle\equiv-
c_{1}\Big{[}(u_{1}+v_{1})(u_{1}+v_{1})^{\top}+(u_{2}+v_{2})(u_{2}+v_{2})^{\top}\Big{]}$
$\displaystyle\qquad\qquad+c_{2}\Big{[}(u_{1}-v_{1})(u_{1}-v_{1})^{\top}+(u_{2}-v_{2})(u_{2}-v_{2})^{\top}\Big{]},$

and

$\displaystyle\widetilde{\Sigma}b\equiv
T_{1}u_{1}+T_{2}u_{2}+T_{3}u_{3}+T_{4}u_{4},$

where

$\displaystyle T_{1}$
$\displaystyle=\alpha_{1}\cdot(c_{2}-c_{1})pq+\alpha_{2}\cdot(c_{2}-c_{1})\left\langle
u_{1},u_{2}\right\rangle-\alpha_{3}\cdot(c_{1}+c_{2})pq-\alpha_{4}\cdot(c_{1}+c_{2})\left\langle
v_{1},v_{2}\right\rangle,$ $\displaystyle T_{2}$
$\displaystyle=\alpha_{1}\cdot(c_{2}-c_{1})\left\langle
u_{1},u_{2}\right\rangle+\alpha_{2}\cdot(c_{2}-c_{1})pq-\alpha_{3}\cdot(c_{1}+c_{2})\left\langle
v_{1},v_{2}\right\rangle-\alpha_{4}\cdot(c_{1}+c_{2})pq,$ $\displaystyle
T_{3}$
$\displaystyle=-\alpha_{1}\cdot(c_{1}+c_{2})pq-\alpha_{2}\cdot(c_{1}+c_{2})\left\langle
u_{1},u_{2}\right\rangle+\alpha_{3}\cdot(c_{2}-c_{1})pq+\alpha_{4}\cdot(c_{2}-c_{1})\left\langle
v_{1},v_{2}\right\rangle,$ $\displaystyle T_{4}$
$\displaystyle=-\alpha_{1}\cdot(c_{1}+c_{2})\left\langle
u_{1},u_{2}\right\rangle-\alpha_{2}\cdot(c_{1}+c_{2})pq+\alpha_{3}\cdot(c_{2}-c_{1})\left\langle
v_{1},v_{2}\right\rangle+\alpha_{4}\cdot(c_{2}-c_{1})pq.$

Hence the identity
$T_{1}/\alpha_{1}=T_{2}/\alpha_{2}=T_{3}/\alpha_{3}=T_{4}/\alpha_{4}$ is
equivalent to (denoting $\rho_{ij}\equiv\alpha_{i}/\alpha_{j}$)

$\displaystyle\quad\quad\rho_{21}\cdot(c_{2}-c_{1})\left\langle
u_{1},u_{2}\right\rangle-\rho_{31}\cdot(c_{1}+c_{2})pq-\rho_{41}\cdot(c_{1}+c_{2})\left\langle
v_{1},v_{2}\right\rangle$ (i)
$\displaystyle=\rho_{12}\cdot(c_{2}-c_{1})\left\langle
u_{1},u_{2}\right\rangle-\rho_{32}\cdot(c_{1}+c_{2})\left\langle
v_{1},v_{2}\right\rangle-\rho_{42}\cdot(c_{1}+c_{2})pq$ (ii)
$\displaystyle=-\rho_{13}\cdot(c_{1}+c_{2})pq-\rho_{23}\cdot(c_{1}+c_{2})\left\langle
u_{1},u_{2}\right\rangle+\rho_{43}\cdot(c_{2}-c_{1})\left\langle
v_{1},v_{2}\right\rangle$ (iii)
$\displaystyle=-\rho_{14}\cdot(c_{1}+c_{2})\left\langle
u_{1},u_{2}\right\rangle-\rho_{24}\cdot(c_{1}+c_{2})pq+\rho_{34}\cdot(c_{2}-c_{1})\left\langle
v_{1},v_{2}\right\rangle.$ (iv)

For the first set of two solutions, let $\alpha_{1}=\alpha_{2}=1$ and
$\alpha_{3}=\alpha_{4}=\beta$. Then $(i)=(ii)$ and $(iii)=(iv)$ automatically
holds, and $(ii)=(iii)$ is equivalent to

$\displaystyle(c_{1}+c_{2})(\left\langle
v_{1},v_{2}\right\rangle+pq)\cdot\beta^{2}+(c_{2}-c_{1})(\left\langle
v_{1},v_{2}\right\rangle-\left\langle u_{1},u_{2}\right\rangle)\cdot\beta$
$\displaystyle\quad\quad-(c_{1}+c_{2})(\left\langle
u_{1},u_{2}\right\rangle+pq)=0.$ (13.3)

Note that as $|\left\langle v_{1},v_{2}\right\rangle|\leq\lVert
v_{1}\rVert\lVert v_{2}\rVert=pq$ and similarly for $|\left\langle
u_{1},u_{2}\right\rangle|$, we have

$\displaystyle(c_{2}-c_{1})^{2}(\left\langle
v_{1},v_{2}\right\rangle-\left\langle
u_{1},u_{2}\right\rangle)^{2}+4(c_{1}+c_{2})^{2}(\left\langle
v_{1},v_{2}\right\rangle+pq)(\left\langle u_{1},u_{2}\right\rangle+pq)\geq 0.$

Hence (13) has two (possible identical) solutions, and these two solutions
denoted by $\beta_{1}$ and $\beta_{2}$ lead to two eigenvectors of
$\widetilde{\Sigma}$. For the second set of two solutions, let
$\alpha_{1}=-\alpha_{2}=1$ and $\alpha_{3}=-\alpha_{4}=\beta$. Then again
$(i)=(ii)$ and $(iii)=(iv)$ automatically, and $(ii)=(iii)$ is equivalent to

$\displaystyle(c_{1}+c_{2})(\left\langle v_{1},v_{2}\right\rangle-
pq)\cdot\beta^{2}+(c_{2}-c_{1})(\left\langle
v_{1},v_{2}\right\rangle-\left\langle u_{1},u_{2}\right\rangle)\cdot\beta$
$\displaystyle\quad\quad-(c_{1}+c_{2})(\left\langle u_{1},u_{2}\right\rangle-
pq)=0.$ (13.4)

The two (possible identical) solutions of the above quadratic equation
(existence due to similar reason as (13)), denoted by $\beta_{3}$ and
$\beta_{4}$, lead to the other two eigenvectors. Summarizing the above
arguments, $\widetilde{\Sigma}$ has four eigenvalue

$\displaystyle\lambda_{i}$ $\displaystyle=(c_{2}-c_{1})(pq+\left\langle
u_{1},u_{2}\right\rangle)-\beta_{i}(c_{1}+c_{2})(\left\langle
v_{1},v_{2}\right\rangle+pq),\quad i=1,2,$ $\displaystyle\lambda_{i}$
$\displaystyle=(c_{2}-c_{1})(pq-\left\langle
u_{1},u_{2}\right\rangle)+\beta_{i}(c_{1}+c_{2})(\left\langle
v_{1},v_{2}\right\rangle-pq),\quad i=3,4.$

For the second claim of the lemma, note that (13) implies that

$\displaystyle\beta_{1}+\beta_{2}$
$\displaystyle=\frac{(c_{2}-c_{1})(\left\langle
u_{1},u_{2}\right\rangle-\left\langle
v_{1},v_{2}\right\rangle)}{(c_{1}+c_{2})(\left\langle
v_{1},v_{2}\right\rangle+pq)},$ $\displaystyle\beta_{1}\cdot\beta_{2}$
$\displaystyle=-\frac{(c_{1}+c_{2})(\left\langle
u_{1},u_{2}\right\rangle+pq)}{(c_{1}+c_{2})(\left\langle
v_{1},v_{2}\right\rangle+pq)}.$

Hence we have

$\displaystyle(1+\lambda_{1})(1+\lambda_{2})$
$\displaystyle=\Big{(}\big{[}1+(c_{2}-c_{1})(pq+\left\langle
u_{1},u_{2}\right\rangle)\big{]}-\beta_{1}(c_{1}+c_{2})(\left\langle
v_{1},v_{2}\right\rangle+pq)\Big{)}$
$\displaystyle\quad\quad\cdot\Big{(}\big{[}1+(c_{2}-c_{1})(pq+\left\langle
u_{1},u_{2}\right\rangle)\big{]}-\beta_{2}(c_{1}+c_{2})(\left\langle
v_{1},v_{2}\right\rangle+pq)\Big{)}$
$\displaystyle=\big{[}1+(c_{2}-c_{1})(pq+\left\langle
u_{1},u_{2}\right\rangle)\big{]}^{2}$
$\displaystyle\quad\quad\quad-(\beta_{1}+\beta_{2})(c_{1}+c_{2})(\left\langle
v_{1},v_{2}\right\rangle+pq)\big{[}1+(c_{2}-c_{1})(pq+\left\langle
u_{1},u_{2}\right\rangle)\big{]}$
$\displaystyle\quad\quad\quad+\beta_{1}\beta_{2}\cdot(c_{1}+c_{2})(\left\langle
v_{1},v_{2}\right\rangle+pq)^{2}$
$\displaystyle=\big{[}1+(c_{2}-c_{1})(pq+\left\langle
u_{1},u_{2}\right\rangle)\big{]}^{2}$
$\displaystyle\quad\quad\quad-(c_{2}-c_{1})(\left\langle
u_{1},u_{2}\right\rangle-\left\langle
v_{1},v_{2}\right\rangle)\big{[}1+(c_{2}-c_{1})(pq+\left\langle
u_{1},u_{2}\right\rangle)\big{]}$
$\displaystyle\quad\quad\quad-(c_{1}+c_{2})^{2}(\left\langle
u_{1},u_{2}\right\rangle+pq)(\left\langle v_{1},v_{2}\right\rangle+pq)$
$\displaystyle=1+(c_{2}-c_{1})(2pq+\left\langle
u_{1},u_{2}\right\rangle+\left\langle
v_{1},v_{2}\right\rangle)-4c_{1}c_{2}(\left\langle
u_{1},u_{2}\right\rangle+pq)(\left\langle v_{1},v_{2}\right\rangle+pq).$

By plugging in the definition of $c_{1}$ and $c_{2}$, we have

$\displaystyle(1+\lambda_{1})(1+\lambda_{2})$
$\displaystyle=1+\frac{a^{2}pq}{1-(apq)^{2}}(2pq+\left\langle
u_{1},u_{2}\right\rangle+\left\langle v_{1},v_{2}\right\rangle)$
$\displaystyle\quad\quad\quad-\frac{a^{2}}{1-(apq)^{2}}(\left\langle
u_{1},u_{2}\right\rangle+pq)(\left\langle v_{1},v_{2}\right\rangle+pq)$
$\displaystyle=1+\frac{a^{2}}{1-(apq)^{2}}(p^{2}q^{2}-\left\langle
u_{1},u_{2}\right\rangle\left\langle v_{1},v_{2}\right\rangle).$

The argument for the expression $(1+\lambda_{3})(1+\lambda_{4})$ is similar,
so the proof is complete. ∎

##  Appendix A Proof of Proposition 2.1

######  Lemma A.1.

Recall $A=\\{A_{ij}=\lVert X_{i}-X_{j}\rVert\\}$ and $B=\\{B_{ij}=\lVert
Y_{i}-Y_{j}\rVert\\}$ and $A^{\ast},B^{\ast}$ defined in (2.1). Then

$\displaystyle\operatorname{dCov}_{\ast}^{2}(\bm{X},\bm{Y})=\frac{1}{n(n-3)}\sum_{k\neq\ell}A_{k\ell}^{\ast}B_{k\ell}^{\ast}=\frac{1}{n(n-3)}\bigg{(}\operatorname{tr}(AB)+\frac{\bm{1}^{\top}A\bm{1}\bm{1}^{\top}B\bm{1}}{(n-1)(n-2)}-\frac{2\bm{1}^{\top}AB\bm{1}}{n-2}\bigg{)}.$

This result is known in the literature, see e.g. in the proof of [YZS18, Lemma
2.1]. We provide a complete proof for the convenience of the reader.

###### Proof.

Recall $A\equiv\\{A_{ij}\\}\equiv\\{\lVert X_{i}-X_{j}\rVert\\}$ and
$B\equiv\\{B_{ij}\|\equiv\lVert Y_{i}-Y_{j}\rVert$. Note that
$\sum_{k\neq\ell}A_{k\ell}^{*}B_{k\ell}^{*}=\operatorname{tr}(A^{*}B^{*})-\sum_{k=1}^{n}(A^{*})_{kk}(B^{*})_{kk}$.
The second term can be computed as follows: As

$\displaystyle A_{kk}^{*}$
$\displaystyle=-\frac{2}{n-2}e_{k}^{\top}A\bm{1}+\frac{1}{(n-1)(n-2)}\bm{1}^{\top}A\bm{1},$

we have

$\displaystyle\sum_{k=1}^{n}A_{kk}^{*}B_{kk}^{*}=\sum_{k=1}^{n}\Big{(}-\frac{2}{n-2}e_{k}^{\top}A\bm{1}+\frac{1}{(n-1)(n-2)}\bm{1}^{\top}A\bm{1}\Big{)}$
$\displaystyle\qquad\qquad\times\Big{(}-\frac{2}{n-2}e_{k}^{\top}B\bm{1}+\frac{1}{(n-1)(n-2)}\bm{1}^{\top}B\bm{1}\Big{)}$
$\displaystyle=\frac{4}{(n-2)^{2}}\bm{1}^{\top}AB\bm{1}+\Big{(}-\frac{4}{(n-1)(n-2)^{2}}+\frac{n}{(n-1)^{2}(n-2)^{2}}\Big{)}\cdot\bm{1}^{\top}A\bm{1}\bm{1}^{\top}B\bm{1}$
$\displaystyle=\frac{4}{(n-2)^{2}}\bm{1}^{\top}AB\bm{1}-\frac{3n-4}{(n-1)^{2}(n-2)^{2}}\bm{1}^{\top}A\bm{1}\bm{1}^{\top}B\bm{1}.$

For the first term, using the definition of $A^{\ast},B^{\ast}$,

$\displaystyle\operatorname{tr}(A^{*}B^{*})$
$\displaystyle=\operatorname{tr}\Big{[}\Big{(}A-\frac{1}{n-2}\bm{1}\bm{1}^{\top}A-\frac{1}{n-2}A\bm{1}\bm{1}^{\top}+\frac{\bm{1}^{\top}A\bm{1}}{(n-1)(n-2)}\bm{1}\bm{1}^{\top}\Big{)}$
$\displaystyle\quad\quad\times\Big{(}B-\frac{1}{n-2}\bm{1}\bm{1}^{\top}B-\frac{1}{n-2}B\bm{1}\bm{1}^{\top}+\frac{\bm{1}^{\top}B\bm{1}}{(n-1)(n-2)}\bm{1}\bm{1}^{\top}\Big{)}\Big{]}$
$\displaystyle=\operatorname{tr}(AB)+\frac{8-2n}{(n-2)^{2}}\bm{1}^{\top}AB\bm{1}+\frac{n^{2}-6n+6}{(n-1)^{2}(n-2)^{2}}\bm{1}^{\top}A\bm{1}\bm{1}^{\top}B\bm{1}.$

Combining the two identities above to conclude. ∎

###### Proof of Proposition 2.1.

By the proceeding lemma,

$\displaystyle\operatorname{dCov}_{\ast}^{2}(\bm{X},\bm{Y})=\frac{1}{n(n-3)}\bigg{(}\operatorname{tr}(AB)+\frac{\bm{1}^{\top}A\bm{1}\bm{1}^{\top}B\bm{1}}{(n-1)(n-2)}-\frac{2\bm{1}^{\top}AB\bm{1}}{n-2}\bigg{)}$
$\displaystyle=\frac{1}{n(n-3)}\bigg{(}\sum_{i\neq
j}A_{ij}B_{ij}+\frac{1}{(n-1)(n-2)}\sum_{i\neq
j,k\neq\ell}A_{ij}B_{k\ell}-\frac{2}{n-2}\sum_{i\neq j,i\neq
k}A_{ij}B_{ik}\bigg{)}$
$\displaystyle\stackrel{{\scriptstyle(*)}}{{=}}\frac{1}{n(n-3)}\bigg{(}\frac{n-3}{n-1}\sum_{i\neq
j}A_{ij}B_{ij}$ $\displaystyle\qquad\qquad+\frac{1}{(n-1)(n-2)}\sum_{i\neq
j\neq k\neq\ell}A_{ij}B_{k\ell}-\frac{2(n-3)}{(n-1)(n-2)}\sum_{i\neq j\neq
k}A_{ij}B_{ik}\bigg{)}$ $\displaystyle=\frac{1}{4!\binom{n}{4}}\sum_{i\neq
j\neq
k\neq\ell}\big{(}A_{ij}B_{ij}+A_{ij}B_{k\ell}-2A_{ij}B_{ik}\big{)}=\frac{1}{\binom{n}{4}}\sum_{i_{1}<\cdots<i_{4}}k_{0}\big{(}Z_{i_{1}},Z_{i_{2}},Z_{i_{3}},Z_{i_{4}}\big{)},$

Here $(*)$ follows from the identities:

$\displaystyle\sum_{i\neq j,i\neq k}A_{ij}B_{ik}$ $\displaystyle=\sum_{i\neq
j\neq k}A_{ij}B_{ik}+\sum_{i\neq j}A_{ij}B_{ij},$ $\displaystyle\sum_{i\neq
j,k\neq\ell}A_{ij}B_{k\ell}$ $\displaystyle=\sum_{i\neq j\neq
k\neq\ell}A_{ij}B_{k\ell}+4\sum_{i\neq j\neq k}A_{ij}B_{ik}+2\sum_{i\neq
j}A_{ij}B_{ij},$

and $k_{0}$ is the symmetrized kernel

$\displaystyle k_{0}(Z_{1},Z_{2},Z_{3},Z_{4})$
$\displaystyle=\frac{1}{4!}\sum_{(i_{1},\ldots,i_{4})\in\sigma(1,2,3,4)}\lVert
X_{i_{1}}-X_{i_{2}}\rVert\big{(}\lVert Y_{i_{1}}-Y_{i_{2}}\rVert+\lVert
Y_{i_{3}}-Y_{i_{4}}\rVert-2\lVert Y_{i_{1}}-Y_{i_{3}}\rVert\big{)}$
$\displaystyle\equiv\mathbb{E}_{\bm{i}\in\sigma_{4}}(i_{1},i_{2})_{X}\big{[}(i_{1},i_{2})_{Y}+(i_{3},i_{4})_{Y}-2(i_{1},i_{3})_{Y}\big{]}$
$\displaystyle=\mathbb{E}_{\bm{i}\in\sigma_{4}}(i_{1},i_{2})_{X}\big{[}(i_{1},i_{2})_{Y}+(i_{3},i_{4})_{Y}-2(i_{2},i_{4})_{Y}\big{]}\quad(1\leftrightarrow
2,3\leftrightarrow 4),$

where we abbreviate $(i,j)_{X}=(X_{i},X_{j}),(i,j)_{Y}=(Y_{i},Y_{j})$ and the
expectation $\mathbb{E}_{\bm{i}\in\sigma_{4}}$ is taken over uniform
distribution of permutation group over $\\{1,2,3,4\\}$. So by averaging the
above two equations, we have

$\displaystyle k_{0}(\bm{Z})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\mathbb{E}_{\bm{i}\in\sigma_{4}}(i_{1},i_{2})_{X}\big{[}(i_{1},i_{2})_{Y}+(i_{3},i_{4})_{Y}-(i_{1},i_{3})_{Y}-(i_{2},i_{4})_{Y}\big{]}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\mathbb{E}_{\bm{i}\in\sigma_{4}}(i_{3},i_{4})_{X}\big{[}(i_{1},i_{2})_{Y}+(i_{3},i_{4})_{Y}-(i_{1},i_{3})_{Y}-(i_{2},i_{4})_{Y}\big{]}\quad(a:1\leftrightarrow
3,2\leftrightarrow 4)$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{=}}\mathbb{E}_{\bm{i}\in\sigma_{4}}(i_{1},i_{3})_{X}\big{[}(i_{1},i_{3})_{Y}+(i_{2},i_{4})_{Y}-(i_{1},i_{2})_{Y}-(i_{3},i_{4})_{Y}\big{]}\quad(a:2\leftrightarrow
3)$
$\displaystyle=\mathbb{E}_{\bm{i}\in\sigma_{4}}(i_{2},i_{4})_{X}\big{[}(i_{1},i_{3})_{Y}+(i_{2},i_{4})_{Y}-(i_{1},i_{2})_{Y}-(i_{3},i_{4})_{Y}\big{]}\quad(c:1\leftrightarrow
3,2\leftrightarrow 4).$

Using that

$\displaystyle(i_{1},i_{2})_{X}+(i_{3},i_{4})_{X}-(i_{1},i_{3})_{X}-(i_{2},i_{4})_{X}$
$\displaystyle=U(X_{i_{1}},X_{i_{2}})+U(X_{i_{3}},X_{i_{4}})-U(X_{i_{1}},X_{i_{3}})-U(X_{i_{2}},X_{i_{4}}),$

and a similar equation for $(\cdot,\cdot)_{Y}$ replacing $U$ by $V$, we have

$\displaystyle k_{0}(\bm{Z})=\frac{1}{4\cdot
4!}\sum_{(i_{1},\ldots,i_{4})\in\sigma(1,2,3,4)}\Big{(}U(X_{i_{1}},X_{i_{2}})+U(X_{i_{3}},X_{i_{4}})-U(X_{i_{1}},X_{i_{3}})-U(X_{i_{2}},X_{i_{4}})\Big{)}$
$\displaystyle\qquad\qquad\qquad\times\Big{(}V(Y_{i_{1}},Y_{i_{2}})+V(Y_{i_{3}},Y_{i_{4}})-V(Y_{i_{1}},Y_{i_{3}})-V(Y_{i_{2}},Y_{i_{4}})\Big{)}$
$\displaystyle=\frac{1}{4\cdot
4!}\sum_{(i_{1},\ldots,i_{4})\in\sigma(1,2,3,4)}\bigg{[}U(X_{i_{1}},X_{i_{2}})\Big{(}V(Y_{i_{1}},Y_{i_{2}})+V(Y_{i_{3}},Y_{i_{4}})-V(Y_{i_{1}},Y_{i_{3}})-V(Y_{i_{2}},Y_{i_{4}})\Big{)}$
$\displaystyle\qquad+U(X_{i_{3}},X_{i_{4}})\Big{(}V(Y_{i_{1}},Y_{i_{2}})+V(Y_{i_{3}},Y_{i_{4}})-V(Y_{i_{1}},Y_{i_{3}})-V(Y_{i_{2}},Y_{i_{4}})\Big{)}$
$\displaystyle\qquad-U(X_{i_{1}},X_{i_{3}})\Big{(}V(Y_{i_{1}},Y_{i_{2}})+V(Y_{i_{3}},Y_{i_{4}})-V(Y_{i_{1}},Y_{i_{3}})-V(Y_{i_{2}},Y_{i_{4}})\Big{)}$
$\displaystyle\qquad-U(X_{i_{2}},X_{i_{4}})\Big{(}V(Y_{i_{1}},Y_{i_{2}})+V(Y_{i_{3}},Y_{i_{4}})-V(Y_{i_{1}},Y_{i_{3}})-V(Y_{i_{2}},Y_{i_{4}})\Big{)}\bigg{]}$
$\displaystyle=\frac{1}{4!}\sum_{(i_{1},\ldots,i_{4})\in\sigma(1,2,3,4)}\bigg{[}U(X_{i_{1}},X_{i_{2}})V(Y_{i_{1}},Y_{i_{2}})+U(X_{i_{1}},X_{i_{2}})V(Y_{i_{3}},Y_{i_{4}})$
$\displaystyle\qquad\qquad-2U(X_{i_{1}},X_{i_{2}})V(Y_{i_{1}},Y_{i_{3}})\bigg{]}=k(\bm{Z}).$

The proof is complete. ∎

##  Appendix B Proofs for Section 8

###  B.1. Proof of Lemma 8.1

###### Proof of Lemma 8.1.

We only prove the formula for $\psi_{X}$. Note that

$\displaystyle\psi_{X}(X_{1},Y_{1})$
$\displaystyle=\mathbb{E}_{X_{2},Y_{2}}\Big{[}\big{(}R_{X}(X_{1},X_{2})-\mathbb{E}_{X}R_{X}(X_{1},X)-\mathbb{E}_{X}R_{X}(X,X_{2})+(\mathbb{E}R_{X})\big{)}Y_{2}^{\top}Y_{1}\Big{]}$
$\displaystyle\stackrel{{\scriptstyle(\ast)}}{{=}}\mathbb{E}_{X_{2},Y_{2}}\Big{[}R_{X}(X_{1},X_{2})Y_{2}^{\top}Y_{1}\Big{]}=\mathbb{E}_{X_{2},Y_{2}}\Big{[}h(L_{X}(X_{1},X_{2}))Y_{2}^{\top}Y_{1}\Big{]}.$

Here in $(*)$ we use the fact that
$\mathbb{E}_{X_{1},X_{2},Y_{2}}R_{X}(X_{1},X_{2})(Y_{2}^{\top}Y_{1})=0$ for
fixed $Y_{1}$, because $R_{X}(X_{1},X_{2})(Y_{2}^{\top}Y_{1})$ has equal
distribution as $R_{X}(-X_{1},-X_{2})(-Y_{2}^{\top}Y_{1})$ for any fixed
$Y_{1}$. On the other hand, by Lemma 7.2 we have

$\displaystyle\mathbb{E}_{X_{2},Y_{2}}\Big{[}h(L_{X}(X_{1},X_{2}))Y_{2}^{\top}Y_{1}\Big{]}$
$\displaystyle=-\frac{\mathbb{E}_{X_{2},Y_{2}}\big{(}L_{X}^{2}(X_{1},X_{2})Y_{2}^{\top}Y_{1}\big{)}}{8}+\mathbb{E}_{X_{2},Y_{2}}\big{[}h_{3}(L_{X}(X_{1},X_{2}))Y_{2}^{\top}Y_{1}\big{]}.$

To compute the first term, use the representation
$X_{1}=\Sigma_{X}^{1/2}Z_{X},Y_{1}=\Sigma_{Y\setminus
X}^{1/2}Z_{Y}+\Sigma_{YX}\Sigma_{X}^{-1/2}Z_{X}$, where $\Sigma_{Y\setminus
X}\equiv\Sigma_{Y}-\Sigma_{YX}\Sigma_{X}^{-1}\Sigma_{XY}$, we have

$\displaystyle\tau_{X}^{4}\cdot\mathbb{E}_{X_{2},Y_{2}}\big{(}L_{X}^{2}(X_{1},X_{2})Y_{2}^{\top}Y_{1}\big{)}$
$\displaystyle=\mathbb{E}_{X_{2},Y_{2}}\bigg{[}\Big{(}\lVert
X_{1}\rVert^{2}+\lVert\Sigma_{X}^{1/2}Z_{X}\rVert^{2}-2X_{1}^{\top}\Sigma_{X}^{1/2}Z_{X}-\tau_{X}^{2}\Big{)}^{2}Z_{X}^{\top}\Sigma_{X}^{-1/2}\Sigma_{XY}Y_{1}\bigg{]}$
$\displaystyle=\mathbb{E}_{X_{2},Y_{2}}\bigg{[}-4\lVert
X_{1}\rVert^{2}X_{1}^{\top}\Sigma_{X}^{1/2}Z_{X}Z_{X}^{\top}\Sigma_{X}^{-1/2}\Sigma_{XY}Y_{1}$
$\displaystyle\qquad-4\lVert\Sigma_{X}^{1/2}Z_{X}\rVert^{2}X_{1}^{\top}\Sigma_{X}^{1/2}Z_{X}Z_{X}^{\top}\Sigma_{X}^{-1/2}\Sigma_{XY}Y_{1}+4\tau_{X}^{2}X_{1}^{\top}\Sigma_{X}^{1/2}Z_{X}Z_{X}^{\top}\Sigma_{X}^{-1/2}\Sigma_{XY}Y_{1}\bigg{]}$
$\displaystyle=-4\lVert
X_{1}\rVert^{2}X_{1}^{\top}\Sigma_{XY}Y_{1}-4\Big{(}\operatorname{tr}(\Sigma_{X})\operatorname{tr}(X_{1}Y_{1}^{\top}\Sigma_{YX})+2\operatorname{tr}(X_{1}Y_{1}^{\top}\Sigma_{YX}\Sigma_{X})\Big{)}+4\tau_{X}^{2}X_{1}^{\top}\Sigma_{XY}Y_{1}$
$\displaystyle=-4\Big{[}\big{(}\lVert
X_{1}\rVert^{2}-\operatorname{tr}(\Sigma_{X})\big{)}X_{1}^{\top}\Sigma_{XY}Y_{1}+2X_{1}^{\top}\Sigma_{X}\Sigma_{XY}Y_{1}\Big{]}.$

The claim follows. ∎

###  B.2. Proof of Lemma 8.3

###### Proof of Lemma 8.3.

For the first inequality, using the representation

$\displaystyle X_{\ell}=\Sigma_{X}^{1/2}Z_{\ell;X},\quad
Y_{\ell}=\Sigma_{Y\setminus
X}^{1/2}Z_{\ell;Y}+\Sigma_{YX}\Sigma_{X}^{-1/2}Z_{\ell;X},\quad\ell=1,2,$

where $\Sigma_{Y\setminus
X}\equiv\Sigma_{Y}-\Sigma_{YX}\Sigma_{X}^{-1}\Sigma_{XY}$, and with the
notation $D\equiv\Sigma_{X}^{-1/2}\Sigma_{XY}\Sigma_{YX}\Sigma_{X}^{-1/2}$,
the left hand side of the desired inequality equals

$\displaystyle\mathbb{E}\bigg{[}\mathfrak{h}\big{(}L_{X}(\Sigma_{X}^{1/2}Z_{1;X},\Sigma_{X}^{1/2}Z_{2;X})\big{)}Z_{1;X}^{\top}DZ_{2;X}\bigg{]},$

whose absolute value is bounded, up to an absolute constant, by

$\displaystyle\mathbb{E}^{1/2}\mathfrak{h}^{2}(L_{X}(X_{1},X_{2}))\cdot\mathbb{E}^{1/2}\big{(}Z_{1;X}^{\top}DZ_{2;X}\big{)}^{2}$
$\displaystyle=\mathbb{E}^{1/2}\mathfrak{h}^{2}(L_{X}(X_{1},X_{2}))\cdot\lVert
D\rVert_{F}\lesssim_{M}\mathbb{E}^{1/2}\mathfrak{h}^{2}(L_{X}(X_{1},X_{2}))\cdot\lVert\Sigma_{XY}\rVert_{F}^{2},$

as desired. ∎

###  B.3. Proof of Lemma 8.4

Let $\mathcal{M}^{d}$ be the set of $d\times d$ matrices and
$\mathcal{M}_{+}^{d}$ the set of p.s.d. matrices of size $d\times d$. We need
the following matrix derivative formulae.

######  Lemma B.1.

Let $I\subset\mathbb{R}$.

  1. (1)

Suppose that $S:I\to\mathcal{M}_{d}$ is a smooth map. Then for any integer
$m\in\mathbb{N}$, and $t\in\mathrm{int}(I)$,

$\displaystyle\frac{\mathrm{d}missing}{\mathrm{d}t}S(t)^{m}=\sum_{k=0}^{m-1}S(t)^{k}\frac{\mathrm{d}missing}{\mathrm{d}t}S(t)S(t)^{m-1-k}.$
(B.1)

  2. (2)

Suppose that $S:I\to\mathcal{M}_{d}$ is a smooth map. Then for any
$t\in\mathrm{int}(I)$,

$\displaystyle\frac{\mathrm{d}missing}{\mathrm{d}t}e^{S(t)}=\int_{0}^{1}e^{uS(t)}\frac{\mathrm{d}missing}{\mathrm{d}t}S(t)e^{(1-u)S(t)}\,\mathrm{d}u.$
(B.2)

  3. (3)

Suppose that $S:I\to\mathcal{M}^{d}_{+}$ is a smooth map. Then for any
$t\in\mathrm{int}(I)$ such that $S(t)$ is p.d.,

$\displaystyle\frac{\mathrm{d}missing}{\mathrm{d}t}S^{1/2}(t)=\int_{0}^{\infty}e^{-uS^{1/2}(t)}\frac{\mathrm{d}missing}{\mathrm{d}t}S(t)e^{-uS^{1/2}(t)}\,\mathrm{d}u.$
(B.3)

These formulae are well-known. We provide a self-contained proof below for the
convenience of the reader.

###### Proof.

(1). We prove the claim by induction on $m$. The base case $m=1$ is trivial,
so we suppose the claim holds up to $m-1$. Now differentiating on both sides
of the identity $S(t)^{m}=S(t)^{m-1}S(t)$ and using the induction hypothesis,
we have

$\displaystyle\frac{\mathrm{d}missing}{\mathrm{d}t}S(t)^{m}$
$\displaystyle=\frac{\mathrm{d}missing}{\mathrm{d}t}S(t)^{m-1}S(t)+S(t)^{m-1}\frac{\mathrm{d}missing}{\mathrm{d}t}S(t)$
$\displaystyle=\bigg{[}\sum_{k=0}^{m-2}S(t)^{k}\frac{\mathrm{d}missing}{\mathrm{d}t}S(t)S(t)^{m-2-k}\bigg{]}S(t)+S(t)^{m-1}\frac{\mathrm{d}missing}{\mathrm{d}t}S(t)=\hbox{RHS
of (\ref{ineq:mat_poly_int_formula})}.$

(2). Using the expansion $e^{A}=\sum_{k=0}^{\infty}A^{k}/k!$,

RHS of (B.2)
$\displaystyle=\int_{0}^{1}\sum_{k,\ell}\frac{1}{k!\ell!}\big{(}uS(t)\big{)}^{k}\frac{\mathrm{d}missing}{\mathrm{d}t}S(t)\big{(}(1-u)S(t)\big{)}^{\ell}\,\mathrm{d}u$
$\displaystyle\stackrel{{\scriptstyle(\ast)}}{{=}}\sum_{k,\ell}\frac{1}{(k+\ell+1)!}S(t)^{k}\frac{\mathrm{d}missing}{\mathrm{d}t}S(t)S(t)^{\ell}$
$\displaystyle=\sum_{m=0}^{\infty}\frac{1}{m!}\sum_{k=0}^{m-1}S(t)^{k}\frac{\mathrm{d}missing}{\mathrm{d}t}S(t)S(t)^{m-1-k}\quad\hbox{(rearraging
the summation)}$
$\displaystyle=\sum_{m=0}^{\infty}\frac{1}{m!}\frac{\mathrm{d}missing}{\mathrm{d}t}S(t)^{m}=\hbox{LHS
of (\ref{ineq:mat_exp_int_formula})}.$

Here in the last line we used (1), whereas in $(\ast)$ we used the simple fact
that $\int_{0}^{1}u^{k}(1-u)^{\ell}\,\mathrm{d}u=k!\ell!/(k+\ell+1)!$ that can
be proved by induction on $\ell$:

$\displaystyle\int_{0}^{1}u^{k}(1-u)^{\ell}\,\mathrm{d}u$
$\displaystyle=\int_{0}^{1}u^{k}(1-u)^{\ell-1}(1-u)\,\mathrm{d}u$
$\displaystyle=\int_{0}^{1}u^{k}(1-u)^{\ell-1}\,\mathrm{d}u-\int_{0}^{1}u^{k+1}(1-u)^{\ell-1}\,\mathrm{d}u$
$\displaystyle=\frac{k!(\ell-1)!}{(k+\ell)!}-\frac{(k+1)!(\ell-1)!}{(k+\ell+1)!}=\frac{k!\ell!}{(k+\ell+1)!}.$

(3). The derivative
$D(t)\equiv\frac{\mathrm{d}missing}{\mathrm{d}t}S^{1/2}(t)$ solves the
Sylvester equation

$\displaystyle
D(t)S^{1/2}(t)+S^{1/2}(t)D(t)=\frac{\mathrm{d}missing}{\mathrm{d}t}S(t).$
(B.4)

We will verify $D(t)$ given by the right hand side of (B.3) satisfies (B.4).
As $S(t)$ is p.d., the integral in (B.3) converges. Now we compute

$\displaystyle\bigg{(}\int_{0}^{\infty}e^{-uS^{1/2}(t)}\frac{\mathrm{d}missing}{\mathrm{d}t}S(t)e^{-uS^{1/2}(t)}\,\mathrm{d}u\bigg{)}S^{1/2}(t)$
$\displaystyle\qquad\qquad\qquad+S^{1/2}(t)\bigg{(}\int_{0}^{\infty}e^{-uS^{1/2}(t)}\frac{\mathrm{d}missing}{\mathrm{d}t}S(t)e^{-uS^{1/2}(t)}\,\mathrm{d}u\bigg{)}$
$\displaystyle=-\int_{0}^{\infty}\frac{\mathrm{d}missing}{\mathrm{d}u}\bigg{[}e^{-uS^{1/2}(t)}\frac{\mathrm{d}missing}{\mathrm{d}t}S(t)e^{-uS^{1/2}(t)}\bigg{]}\,\mathrm{d}u=\frac{\mathrm{d}missing}{\mathrm{d}t}S(t),$

as desired. ∎

###### Proof of Lemma 8.4: compact spectrum case.

We may represent
$(X_{\ell}^{\top},Y_{\ell}^{\top})^{\top}=\Sigma^{1/2}Z_{\ell}$ for
$\ell\in\mathbb{N}$. Let $\bar{Z}_{k,\ell}\equiv Z_{k}-Z_{\ell}$, where
$k,\ell\in\mathbb{N}$, and

$\displaystyle\Sigma_{0}\equiv\begin{pmatrix}\Sigma_{X}&0\\\
0&\Sigma_{Y}\end{pmatrix},\quad\Sigma_{t}\equiv\Sigma_{0}+t\begin{pmatrix}0&\Sigma_{XY}\\\
\Sigma_{YX}&0\end{pmatrix}=\Sigma_{0}+t(\Sigma_{[12]}+\Sigma_{[21]}),$

and $H_{[ij]}(t)\equiv\Sigma_{t}^{1/2}I_{[ij]}\Sigma_{t}^{1/2}$. Then

$\displaystyle\psi_{\mathfrak{h}_{X},\mathfrak{h}_{Y}}(t\Sigma_{XY})\equiv\mathbb{E}\bigg{[}\mathfrak{h}_{X}\bigg{(}\frac{\bar{Z}_{k,\ell}^{\top}H_{[11]}(t)\bar{Z}_{k,\ell}}{\tau_{X}^{2}}-1\bigg{)}\mathfrak{h}_{Y}\bigg{(}\frac{\bar{Z}_{k^{\prime},\ell^{\prime}}^{\top}H_{[22]}(t)\bar{Z}_{k^{\prime},\ell^{\prime}}}{\tau_{Y}^{2}}-1\bigg{)}\bigg{\lvert}Z_{1}\bigg{]}.$

By direct calculation, we have

$\displaystyle\frac{\mathrm{d}missing}{\mathrm{d}t}\psi_{\mathfrak{h}_{X},\mathfrak{h}_{Y}}(t\Sigma_{XY})$
$\displaystyle=\mathbb{E}\bigg{[}\mathfrak{h}_{X}^{\prime}\bigg{(}\frac{\bar{Z}_{k,\ell}^{\top}H_{[11]}(t)\bar{Z}_{k,\ell}}{\tau_{X}^{2}}-1\bigg{)}\mathfrak{h}_{Y}\bigg{(}\frac{\bar{Z}_{k^{\prime},\ell^{\prime}}^{\top}H_{[22]}(t)\bar{Z}_{k^{\prime},\ell^{\prime}}}{\tau_{Y}^{2}}-1\bigg{)}\tau_{X}^{-2}\bar{Z}_{k,\ell}\frac{\mathrm{d}missing}{\mathrm{d}t}H_{[11]}(t)\bar{Z}_{k,\ell}\bigg{\lvert}Z_{1}\bigg{]}$
$\displaystyle\qquad+\mathbb{E}\bigg{[}\mathfrak{h}_{X}\bigg{(}\frac{\bar{Z}_{k,\ell}^{\top}H_{[11]}(t)\bar{Z}_{k,\ell}}{\tau_{X}^{2}}-1\bigg{)}\mathfrak{h}_{Y}^{\prime}\bigg{(}\frac{\bar{Z}_{k^{\prime},\ell^{\prime}}^{\top}H_{[22]}(t)\bar{Z}_{k^{\prime},\ell^{\prime}}}{\tau_{Y}^{2}}-1\bigg{)}\tau_{Y}^{-2}\bar{Z}_{k^{\prime},\ell^{\prime}}\frac{\mathrm{d}missing}{\mathrm{d}t}H_{[11]}(t)\bar{Z}_{k^{\prime},\ell^{\prime}}\bigg{\lvert}Z_{1}\bigg{]}$
$\displaystyle\equiv B_{1}(t)+B_{2}(t).$

Now we compute the term $\mathrm{d}H_{[11]}(t)/\mathrm{d}t$ in $B_{1}$. Using
Lemma B.1-(3) and the fact that
$(\mathrm{d}\Sigma_{t}/\mathrm{d}t)_{k,\ell}=\Sigma_{[12]}+\Sigma_{[21]}$, we
have

$\displaystyle\frac{\mathrm{d}missing}{\mathrm{d}t}\Sigma_{t}^{1/2}$
$\displaystyle=\int_{0}^{\infty}e^{-u\Sigma_{t}^{1/2}}\cdot(\Sigma_{[12]}+\Sigma_{[21]})\cdot
e^{-u\Sigma_{t}^{1/2}}\mathrm{d}u.$

This entails

$\displaystyle\frac{\mathrm{d}missing}{\mathrm{d}t}H_{[11]}(t)$
$\displaystyle=\frac{\mathrm{d}missing}{\mathrm{d}t}\big{(}\Sigma_{t}^{1/2}I_{[11]}\Sigma_{t}^{1/2}\big{)}=\frac{\mathrm{d}missing}{\mathrm{d}t}\Sigma_{t}^{1/2}\cdot
I_{[11]}\Sigma_{t}^{1/2}+\Sigma_{t}^{1/2}I_{[11]}\cdot\frac{\mathrm{d}missing}{\mathrm{d}t}\Sigma_{t}^{1/2}$
$\displaystyle=\int_{0}^{\infty}\mathcal{T}\bigg{[}e^{-u\Sigma_{t}^{1/2}}(\Sigma_{[12]}+\Sigma_{[21]})e^{-u\Sigma_{t}^{1/2}}I_{[11]}\Sigma_{t}^{1/2}\bigg{]}\,\mathrm{d}u.$
(B.5)

Here for a square matrix $A$, $\mathcal{T}(A)\equiv A+A^{\top}$. This implies

$\displaystyle\int_{0}^{1}B_{1}(t)\,\mathrm{d}t$
$\displaystyle=\tau_{X}^{-2}\int_{0}^{1}\mathbb{E}\bigg{[}\mathfrak{h}_{X}^{\prime}\bigg{(}\frac{\bar{Z}_{k,\ell}^{\top}H_{[11]}(t)\bar{Z}_{k,\ell}}{\tau_{X}^{2}}-1\bigg{)}\mathfrak{h}_{Y}\bigg{(}\frac{\bar{Z}_{k^{\prime},\ell^{\prime}}^{\top}H_{[22]}(t)\bar{Z}_{k^{\prime},\ell^{\prime}}}{\tau_{Y}^{2}}-1\bigg{)}$
$\displaystyle\qquad\times\mathcal{T}\bigg{(}\int_{0}^{\infty}\bar{Z}_{k,\ell}^{\top}e^{-u\Sigma_{t}^{1/2}}\big{(}\Sigma_{[12]}+\Sigma_{[21]}\big{)}e^{-u\Sigma_{t}^{1/2}}I_{[11]}\Sigma_{t}^{1/2}\bar{Z}_{k,\ell}\,\mathrm{d}u\bigg{)}\bigg{\lvert}Z_{1}\bigg{]}\,\mathrm{d}t.$

To continue calculations, we may write $e^{-u\Sigma_{t}^{1/2}}$ as follows: by
Lemma B.1-(2), $A\mapsto e^{A}$ as a map from $\mathbb{R}^{(p+q)\times(p+q)}$
to $\mathbb{R}^{(p+q)\times(p+q)}$ has Frechét derivative
$[\nabla(e^{\cdot})](A)\cdot H=\int_{0}^{1}e^{vA}He^{(1-v)A}\,\mathrm{d}v$, so
a first-order Taylor expansion yields that

$\displaystyle e^{-u\Sigma_{t}^{1/2}}-e^{-u\Sigma_{0}^{1/2}}$
$\displaystyle=\int_{0}^{1}\big{[}\nabla(e^{\cdot})\big{]}\big{(}-u\Sigma_{0}^{1/2}+s(-u)(\Sigma_{t}^{1/2}-\Sigma_{0}^{1/2})\big{)}\cdot\big{[}(-u)(\Sigma_{t}^{1/2}-\Sigma_{0}^{1/2})\big{]}\mathrm{d}s$
$\displaystyle=(-u)\int_{0}^{1}\int_{0}^{1}e^{-uv[\Sigma_{0}^{1/2}+s(\Sigma_{t}^{1/2}-\Sigma_{0}^{1/2})]}(\Sigma_{t}^{1/2}-\Sigma_{0}^{1/2})e^{-u(1-v)[\Sigma_{0}^{1/2}+s(\Sigma_{t}^{1/2}-\Sigma_{0}^{1/2})]}\mathrm{d}v\mathrm{d}s$
$\displaystyle\equiv\mathscr{R}_{1}(u,t).$ (B.6)

On the other hand, by Lemma B.1-(3), $A\mapsto A^{1/2}$ as a map from p.s.d.
matrices in $\mathbb{R}^{(p+q)\times(p+q)}$ to itself has Frechét derivative
$[\nabla(\cdot)^{1/2}](A)\cdot
H=\int_{0}^{\infty}e^{-zA^{1/2}}He^{-zA^{1/2}}\,\mathrm{d}z$, so again a
first-order Taylor expansion yields that

$\displaystyle\Sigma_{t}^{1/2}-\Sigma_{0}^{1/2}$
$\displaystyle=\int_{0}^{1}\big{[}\nabla(\cdot)^{1/2}\big{]}\big{(}\Sigma_{0}+w(\Sigma_{t}-\Sigma_{0})\big{)}\cdot(\Sigma_{t}-\Sigma_{0})\,\mathrm{d}w$
$\displaystyle=\int_{0}^{1}\int_{0}^{\infty}e^{-z(\Sigma_{0}+w(\Sigma_{t}-\Sigma_{0}))}(\Sigma_{t}-\Sigma_{0})e^{-z(\Sigma_{0}+w(\Sigma_{t}-\Sigma_{0}))}\,\mathrm{d}z\mathrm{d}w$
$\displaystyle\equiv\mathscr{R}_{2}(t).$ (B.7)

Now using (B.3)-(B.3) and that

$\displaystyle
e^{-u\Sigma_{0}^{1/2}}\big{(}\Sigma_{[12]}+\Sigma_{[21]}\big{)}e^{-u\Sigma_{0}^{1/2}}I_{[11]}\Sigma_{0}^{1/2}=\begin{pmatrix}0&0\\\
e^{-u\Sigma_{Y}^{1/2}}\Sigma_{YX}e^{-u\Sigma_{X}^{1/2}}\Sigma_{X}^{1/2}&0\end{pmatrix},$

we arrive at

$\displaystyle M(u,t)\equiv
e^{-u\Sigma_{t}^{1/2}}\big{(}\Sigma_{[12]}+\Sigma_{[21]}\big{)}e^{-u\Sigma_{t}^{1/2}}I_{[11]}\Sigma_{t}^{1/2}$
$\displaystyle=\begin{pmatrix}0&0\\\
e^{-u\Sigma_{Y}^{1/2}}\Sigma_{YX}e^{-u\Sigma_{X}^{1/2}}\Sigma_{X}^{1/2}&0\end{pmatrix}+e^{-u\Sigma_{0}^{1/2}}\big{(}\Sigma_{[12]}+\Sigma_{[21]}\big{)}e^{-u\Sigma_{0}^{1/2}}I_{[11]}\mathscr{R}_{2}(t)$
$\displaystyle\qquad+\mathscr{R}_{1}(u,t)\big{(}\Sigma_{[12]}+\Sigma_{[21]}\big{)}e^{-u\Sigma_{0}^{1/2}}I_{[11]}\Sigma_{t}^{1/2}+e^{-u\Sigma_{t}^{1/2}}\big{(}\Sigma_{[12]}+\Sigma_{[21]}\big{)}\mathscr{R}_{1}(u,t)I_{[11]}\Sigma_{t}^{1/2}.$

To control the remainder terms, we have

$\displaystyle\lVert\mathscr{R}_{1}(u,t)\rVert_{F}\vee\lVert\mathscr{R}_{2}(t)\rVert_{F}$
$\displaystyle\lesssim_{M}t(u\vee 1)\lVert\Sigma_{XY}\rVert_{F},$
$\displaystyle\lVert\mathscr{R}_{1}(u,t)\rVert_{\operatorname{op}}\vee\lVert\mathscr{R}_{2}(t)\rVert_{\operatorname{op}}$
$\displaystyle\lesssim_{M}t(u\vee 1),$

where we used the following: as
$\inf_{t\in[0,1]}\lambda_{\min}(\Sigma_{t})\geq\lambda_{\min}(\Sigma)\wedge\lambda_{\min}(\Sigma_{0})\gtrsim_{M}1$,

  * •

$\sup_{w\in[0,1]}\int_{0}^{\infty}\lVert
e^{-z(\Sigma_{0}+w(\Sigma_{t}-\Sigma_{0}))}\rVert_{\operatorname{op}}^{2}\mathrm{d}z\lesssim_{M}1$.

  * •

$\sup_{s,v\in[0,1]}\sup_{u\geq 0}\lVert
e^{-uv[\Sigma_{0}^{1/2}+s(\Sigma_{t}^{1/2}-\Sigma_{0}^{1/2})]}\rVert_{\operatorname{op}}\vee\lVert
e^{-u(1-v)[\Sigma_{0}^{1/2}+s(\Sigma_{t}^{1/2}-\Sigma_{0}^{1/2})]}\rVert_{\operatorname{op}}\lesssim_{M}1$.

Hence by using again $\lVert
e^{-u\Sigma_{0}^{1/2}}\rVert_{\operatorname{op}}\vee\lVert
e^{-u\Sigma_{t}^{1/2}}\rVert_{\operatorname{op}}\leq e^{-c_{0}u}$ for some
$c_{0}=c_{0}(M)>0$, there exist another positive $c_{1}$ only depending on $M$
such that

$\displaystyle\lvert\operatorname{tr}M(u,t)\rvert$
$\displaystyle\lesssim_{M}e^{-c_{1}u}\lVert\Sigma_{[12]}\rVert_{F}\big{(}\lVert\mathscr{R}_{1}(u,t)\rVert_{F}\vee\lVert\mathscr{R}_{2}(t)\rVert_{F}\big{)}\lesssim_{M}t(u\vee
1)e^{-c_{1}u}\lVert\Sigma_{XY}\rVert_{F}^{2},$ $\displaystyle\lVert
M(u,t)\rVert_{F}$
$\displaystyle\lesssim_{M}e^{-c_{1}u}\lVert\Sigma_{[12]}\rVert_{F}\big{(}\lVert\mathscr{R}_{1}(u,t)\rVert_{\operatorname{op}}\vee\lVert\mathscr{R}_{2}(t)\rVert_{\operatorname{op}}\big{)}\lesssim_{M}t(u\vee
1)e^{-c_{1}u}\lVert\Sigma_{XY}\rVert_{F},$

which further leads to, with
$\bar{M}(t)\equiv\int_{0}^{\infty}M(u,t)\mathrm{d}u$,

$\displaystyle\big{|}\operatorname{tr}\big{(}\bar{M}(t)\big{)}\big{|}$
$\displaystyle\leq\int_{0}^{\infty}|\operatorname{tr}(M(u,t))|\lesssim_{M}t\lVert\Sigma_{XY}\rVert_{F}^{2},$
$\displaystyle\big{\lVert}\bar{M}(t)\big{\rVert}_{F}$
$\displaystyle\leq\int_{0}^{\infty}\lVert
M(u,t)\rVert_{F}\mathrm{d}u\lesssim_{M}t\lVert\Sigma_{XY}\rVert_{F}.$

Therefore by Cauchy-Schwarz,

$\displaystyle\mathbb{E}\Big{(}\int_{0}^{1}B_{1}(t)\,\mathrm{d}t\Big{)}^{2}$
$\displaystyle\lesssim\tau_{X}^{-4}\mathbb{E}^{1/4}\mathfrak{h}_{X}^{\prime}(L_{X}(X_{1},X_{2}))^{8}\cdot\mathbb{E}^{1/4}\mathfrak{h}_{Y}^{8}(L_{Y}(Y_{1},Y_{2}))\cdot\sup_{t\in[0,1]}\mathbb{E}^{1/2}\big{(}Z_{1}^{\top}\bar{M}(t)Z_{1}\big{)}^{4}$
$\displaystyle\lesssim\tau_{X}^{-4}\mathbb{E}^{1/4}\mathfrak{h}_{X}^{\prime}(L_{X}(X_{1},X_{2}))^{8}\cdot\mathbb{E}^{1/4}\mathfrak{h}_{Y}^{8}(L_{Y}(Y_{1},Y_{2}))\cdot\sup_{t\in[0,1]}\big{[}|\operatorname{tr}(\bar{M}(t))|\vee\lVert\bar{M}(t)\rVert_{F}\big{]}^{2}$
$\displaystyle\lesssim_{M}\tau_{X}^{-4}\mathbb{E}^{1/4}\mathfrak{h}_{X}^{\prime}(L_{X}(X_{1},X_{2}))^{8}\cdot\mathbb{E}^{1/4}\mathfrak{h}_{Y}^{8}(L_{Y}(Y_{1},Y_{2}))\cdot\lVert\Sigma_{XY}\rVert_{F}^{2}\big{(}1\vee\lVert\Sigma_{XY}\rVert_{F}^{2}\big{)}.$

Flip the roles of $X$ and $Y$ to conclude that

$\displaystyle\mathbb{E}\Big{(}\int_{0}^{1}B_{2}(t)\,\mathrm{d}t\Big{)}^{2}$
$\displaystyle\lesssim_{M}\tau_{Y}^{-4}\mathbb{E}^{1/4}\mathfrak{h}_{Y}^{\prime}(L_{Y}(Y_{1},Y_{2}))^{8}\cdot\mathbb{E}^{1/4}\mathfrak{h}_{X}^{8}(L_{X}(X_{1},X_{2}))\cdot\lVert\Sigma_{XY}\rVert_{F}^{2}\big{(}1\vee\lVert\Sigma_{XY}\rVert_{F}^{2}\big{)}.$

The claim follows by noting that

$\displaystyle\psi_{\mathfrak{h}_{X},\mathfrak{h}_{Y}}(\Sigma_{XY})-\psi_{\mathfrak{h}_{X},\mathfrak{h}_{Y}}(0)=\int_{0}^{1}\frac{\mathrm{d}missing}{\mathrm{d}t}\psi_{\mathfrak{h}_{X},\mathfrak{h}_{Y}}(t\Sigma_{XY})\,\mathrm{d}t=\int_{0}^{1}\big{[}B_{1}(t)+B_{2}(t)\big{]}\,\mathrm{d}t,$

as desired. ∎

###### Proof of Lemma 8.4: $X=Y$ case.

The proof is largely similar so we only sketch the key steps. Let
$X_{\ell}\equiv\Sigma_{X}^{1/2}Z_{\ell}$ for $\ell\in\mathbb{N}$. Then with
$\mathfrak{h}_{X},\mathfrak{h}_{Y}$ denoted as $\mathfrak{h},\mathfrak{g}$ to
avoid confusion, we have

$\displaystyle\psi_{\mathfrak{h},\mathfrak{g}}(t\Sigma_{X})=\mathbb{E}\bigg{[}\mathfrak{h}\bigg{(}\frac{\bar{Z}_{k,\ell}^{\top}(t\Sigma_{X})\bar{Z}_{k,\ell}}{\tau_{X}^{2}}-1\bigg{)}\mathfrak{g}\bigg{(}\frac{\bar{Z}_{k^{\prime},\ell^{\prime}}^{\top}(t\Sigma_{X})\bar{Z}_{k^{\prime},\ell^{\prime}}}{\tau_{X}^{2}}-1\bigg{)}\bigg{\lvert}Z_{1}\bigg{]}.$

So

$\displaystyle\frac{\mathrm{d}missing}{\mathrm{d}t}\psi_{\mathfrak{h},\mathfrak{g}}(t\Sigma_{X})$
$\displaystyle=\mathbb{E}\bigg{[}\mathfrak{h}^{\prime}\bigg{(}\frac{\bar{Z}_{k,\ell}^{\top}(t\Sigma_{X})\bar{Z}_{k,\ell}}{\tau_{X}^{2}}-1\bigg{)}\mathfrak{g}\bigg{(}\frac{\bar{Z}_{k^{\prime},\ell^{\prime}}^{\top}(t\Sigma_{X})\bar{Z}_{k^{\prime},\ell^{\prime}}}{\tau_{X}^{2}}-1\bigg{)}\tau_{X}^{-2}\bar{Z}_{k,\ell}^{\top}\Sigma_{X}\bar{Z}_{k,\ell}\bigg{\lvert}Z_{1}\bigg{]}$
$\displaystyle\qquad+\mathbb{E}\bigg{[}\mathfrak{h}\bigg{(}\frac{\bar{Z}_{k,\ell}^{\top}(t\Sigma_{X})\bar{Z}_{k,\ell}}{\tau_{X}^{2}}-1\bigg{)}\mathfrak{g}^{\prime}\bigg{(}\frac{\bar{Z}_{k^{\prime},\ell^{\prime}}^{\top}(t\Sigma_{X})\bar{Z}_{k^{\prime},\ell^{\prime}}}{\tau_{X}^{2}}-1\bigg{)}\tau_{X}^{-2}\bar{Z}_{k^{\prime},\ell^{\prime}}^{\top}\Sigma_{X}\bar{Z}_{k^{\prime},\ell^{\prime}}\bigg{\lvert}Z_{1}\bigg{]}$
$\displaystyle\equiv B_{1}(t)+B_{2}(t).$

Using Cauchy-Schwarz directly to conclude that

$\displaystyle\mathbb{E}\Big{(}\int_{0}^{1}B_{1}(t)\,\mathrm{d}t\Big{)}^{2}\lesssim\tau_{X}^{-4}\cdot\mathbb{E}^{1/4}(\mathfrak{h}^{\prime}\circ
L_{X})^{8}\cdot\mathbb{E}^{1/4}(\mathfrak{g}\circ
L_{X})^{8}\cdot\mathbb{E}^{1/2}(Z_{1}^{\top}\Sigma_{X}Z_{1})^{4}.$

As
$\mathbb{E}^{1/2}(Z_{1}^{\top}\Sigma_{X}Z_{1})^{4}\lesssim_{M}\tau_{X}^{4}\asymp_{M}\lVert\Sigma_{X}\rVert_{F}^{4}$,
the claim follows by treating $B_{2}$ in a similar way. ∎

###  B.4. Proof of Proposition 8.2

######  Lemma B.2.

The following hold:

  1. (1)

For any integer $k\geq 2$ we have

$\displaystyle\big{\lvert}\mathbb{E}\big{[}L_{X}^{k}(X_{1},X_{2})Y_{1}^{\top}Y_{2}\big{]}\big{\rvert}\lesssim_{k,M}\tau_{X}^{-4}\lVert\Sigma_{XY}\rVert_{F}^{2}.$

  2. (2)

For any $k\in\mathbb{N}$ and real number $\ell>0$, there exists some constant
$C=C(k,\ell,M)>0$ such that for $p\geq 8\ell+1$, uniformly in $s\in[0,1]$ and
$r>0$,

$\displaystyle\bigg{\lvert}\mathbb{E}\bigg{[}L^{k}_{X}(X_{1},X_{2})(Y_{1}^{\top}Y_{2})\cdot\int_{0}^{s}\frac{(s-t)^{r}}{\big{(}1+tL_{X}(X_{1},X_{2})\big{)}^{\ell}}\,\mathrm{d}t\bigg{]}\bigg{\rvert}\leq
C\cdot\tau_{X}^{-k}\lVert\Sigma_{XY}\rVert_{F}^{2}.$

###### Proof.

(1). The case $k\geq 4$ follows from Lemmas 7.4 and 8.3. The case $k=2,3$ can
be checked by a direct calculation. We only verify $k=3$ below. Using the
parametrization $(X,Y)\stackrel{{\scriptstyle
d}}{{=}}(\Sigma_{X}^{1/2}Z_{X},\Sigma_{Y\backslash
X}^{1/2}Z_{Y}+\Sigma_{YX}\Sigma_{X}^{-1}Z_{X})$, we have

$\displaystyle\mathbb{E}\big{[}L_{X}^{3}(X_{1},X_{2})Y_{1}^{\top}Y_{2}\big{]}=\tau_{X}^{-6}\mathbb{E}\big{[}(\lVert
X_{1}-X_{2}\rVert^{2}-2\tau_{X}^{2})^{3}(X_{1}^{\top}DX_{2})\big{]},$

where $D\equiv
D(\Sigma)=\Sigma_{X}^{-1}\Sigma_{XY}\Sigma_{YX}\Sigma_{X}^{-1}$. In what
follows, we only prove the case $\Sigma_{X}=I_{p}$; the case of general
$\Sigma_{X}$ follows from analogous arguments by replacing below the leading
term $p^{2}$ by $\operatorname{tr}^{2}(\Sigma_{X})$.

When $\Sigma_{X}=I_{p}$, $D(I_{p})=\Sigma_{XY}\Sigma_{YX}$, and
$(X_{1},X_{2})$ follows a standard normal distribution in $\mathbb{R}^{2p}$.
Furthermore the above display simplifies to

$\displaystyle\tau_{X}^{6}\mathbb{E}\big{[}L_{X}^{3}(X_{1},X_{2})Y_{1}^{\top}Y_{2}\big{]}$
$\displaystyle=\mathbb{E}\lVert
X_{1}-X_{2}\rVert^{6}(X_{1}^{\top}DX_{2})+(-6p)\cdot\mathbb{E}\lVert
X_{1}-X_{2}\rVert^{4}(X_{1}^{\top}DX_{2})$
$\displaystyle\quad\quad\quad+(12p^{2})\cdot\mathbb{E}\lVert
X_{1}-X_{2}\rVert^{2}(X_{1}^{\top}DX_{2})$ $\displaystyle\equiv
L_{1}-6pL_{2}+12p^{2}L_{3}.$

We first calculate $L_{1}$. Using the identity

$\displaystyle\lVert X_{1}-X_{2}\rVert^{4}$ $\displaystyle=\lVert
X_{1}\rVert^{4}+\lVert X_{2}\rVert^{4}+4(X_{1}^{\top}X_{2})^{2}+2\lVert
X_{1}\rVert^{2}\lVert X_{2}\rVert^{2}$ $\displaystyle\quad\quad\quad-4\lVert
X_{1}\rVert^{2}(X_{1}^{\top}X_{2})-4\lVert
X_{2}\rVert^{2}(X_{1}^{\top}X_{2}),$ (B.8)

we have

$\displaystyle L_{1}$ $\displaystyle=\mathbb{E}\Big{[}(\lVert
X_{1}\rVert^{2}+\lVert
X_{2}\rVert^{2}-2X_{1}^{\top}X_{2})\cdot(X_{1}^{\top}DX_{2})$
$\displaystyle\quad\cdot\Big{(}\lVert X_{1}\rVert^{4}+\lVert
X_{2}\rVert^{4}+4(X_{1}^{\top}X_{2})^{2}+2\lVert X_{1}\rVert^{2}\lVert
X_{2}\rVert^{2}-4\lVert X_{1}\rVert^{2}(X_{1}^{\top}X_{2})-4\lVert
X_{2}\rVert^{2}(X_{1}^{\top}X_{2})\Big{)}\Big{]}$
$\displaystyle\stackrel{{\scriptstyle(*)}}{{=}}\mathbb{E}\Big{[}(\lVert
X_{1}\rVert^{2}+\lVert
X_{2}\rVert^{2}-2X_{1}^{\top}X_{2})\cdot(X_{1}^{\top}DX_{2})\cdot$
$\displaystyle\quad\cdot\Big{(}2\lVert
X_{1}\rVert^{4}+4(X_{1}^{\top}X_{2})^{2}+2\lVert X_{1}\rVert^{2}\lVert
X_{2}\rVert^{2}-8\lVert X_{1}\rVert^{2}(X_{1}^{\top}X_{2})\Big{)}\Big{]}$
$\displaystyle=-8\mathbb{E}\lVert X_{1}\rVert^{2}\lVert
X_{1}\rVert^{2}(X_{1}^{\top}X_{2})(X_{1}^{\top}DX_{2})-8\mathbb{E}\lVert
X_{2}\rVert^{2}\lVert X_{1}\rVert^{2}(X_{1}^{\top}X_{2})(X_{1}^{\top}DX_{2})$
$\displaystyle\quad-4\mathbb{E}(X_{1}^{\top}X_{2})(X_{1}^{\top}DX_{2})\lVert
X_{1}\rVert^{4}-8\mathbb{E}(X_{1}^{\top}X_{2})(X_{1}^{\top}DX_{2})(X_{1}^{\top}X_{2})^{2}$
$\displaystyle\quad-4\mathbb{E}(X_{1}^{\top}X_{2})(X_{1}^{\top}DX_{2})\lVert
X_{1}\rVert^{2}\lVert X_{2}\rVert^{2}$ $\displaystyle=-12\mathbb{E}\lVert
X_{1}\rVert^{4}(X_{1}^{\top}X_{2})(X_{1}^{\top}DX_{2})-12\mathbb{E}\lVert
X_{1}\rVert^{2}\lVert X_{2}\rVert^{2}(X_{1}^{\top}X_{2})(X_{1}^{\top}DX_{2})$
$\displaystyle\quad\quad-8\mathbb{E}(X_{1}^{\top}X_{2})^{3}(X_{1}^{\top}DX_{2}),$

using the symmetry between $X_{1}$ and $X_{2}$ in $(*)$. Now by direct
calculation, we have:

  * •

By first taking expectation of $X_{2}$, we have

$\displaystyle\mathbb{E}\lVert
X_{1}\rVert^{4}(X_{1}^{\top}X_{2})(X_{1}^{\top}DX_{2})=\mathbb{E}\lVert
X_{1}\rVert^{4}(X_{1}^{\top}DX_{1})=\big{(}p^{2}+\mathcal{O}(p)\big{)}\operatorname{tr}(D).$

  * •

By first taking expectation of $X_{1}$, we have by Lemma F.3-(1)

$\displaystyle\mathbb{E}\lVert X_{1}\rVert^{2}\lVert
X_{2}\rVert^{2}(X_{1}^{\top}X_{2})(X_{1}^{\top}DX_{2})=\mathbb{E}(X_{1}^{\top}X_{1})(X_{1}^{\top}\lVert
X_{2}\rVert^{2}DX_{2}X_{2}^{\top}X_{1})$
$\displaystyle=\big{[}p+\mathcal{O}(1)\big{]}\cdot\mathbb{E}(X_{2}^{\top}DX_{2})\lVert
X_{2}\rVert^{2}=\big{(}p^{2}+\mathcal{O}(p)\big{)}\operatorname{tr}(D).$

  * •

By first taking expectation of $X_{1}$, we have by Lemma F.3-(1)

$\displaystyle\mathbb{E}(X_{1}^{\top}X_{2})(X_{1}^{\top}DX_{2})(X_{1}^{\top}X_{2})^{2}=\mathbb{E}(X_{1}^{\top}X_{2}X_{2}^{\top}DX_{2})(X_{1}^{\top}X_{2}X_{2}^{\top}X_{1})$
$\displaystyle\lesssim\mathbb{E}(X_{2}^{\top}DX_{2})(X_{2}^{\top}X_{2})=\mathcal{O}(p)\cdot\operatorname{tr}(D).$

Combining the pieces yields that

$\displaystyle
L_{1}=-24\big{(}p^{2}+\mathcal{O}(p)\big{)}\operatorname{tr}(D).$

On the other hand, direct calculation of $L_{2}$ via (B.4) and $L_{3}$ yields
that

$\displaystyle
L_{2}=-8\big{(}p+\mathcal{O}(1)\big{)}\operatorname{tr}(D),\quad
L_{3}=-2\operatorname{tr}(D).$

Putting together the estimates for $L_{1}$-$L_{3}$ concludes that
$\tau_{X}^{6}\mathbb{E}\big{[}L_{X}^{3}(X_{1},X_{2})Y_{1}^{\top}Y_{2}\big{]}=\mathcal{O}(p)\operatorname{tr}(D)\lesssim
p\cdot\lVert\Sigma_{XY}\rVert_{F}^{2}$, as desired.

(2). The left hand side of the desired inequality equals

$\displaystyle\mathbb{E}\bigg{[}L_{X}^{k}\big{(}\Sigma_{X}^{1/2}Z_{1;X},\Sigma_{X}^{1/2}Z_{2;X}\big{)}Z_{1;X}^{\top}DZ_{2;X}\cdot\int_{0}^{s}\frac{(s-t)^{r}}{\big{(}1+tL_{X}(\Sigma_{X}^{1/2}Z_{1;X},\Sigma_{X}^{1/2}Z_{2;X})\big{)}^{\ell}}\,\mathrm{d}t\bigg{]},$
$\displaystyle\lesssim_{M}\mathbb{E}^{1/4}L_{X}^{4k}(X_{1},X_{2})\cdot\mathbb{E}^{1/2}(Z_{1;X}^{\top}DZ_{2;X})^{2}\cdot\mathbb{E}^{1/4}\bigg{[}\int_{0}^{s}\frac{(s-t)^{r}}{\big{(}1+tL_{X}(X_{1},X_{2})\big{)}^{\ell}}\,\mathrm{d}t\bigg{]}^{4}$
$\displaystyle\stackrel{{\scriptstyle(\ast)}}{{\lesssim}}_{k,\ell,M}\tau_{X}^{-2k}\lVert\Sigma_{X}\rVert_{F}^{k}\cdot\lVert
D\rVert_{F}\cdot 1\lesssim_{M}\tau_{X}^{-k}\lVert\Sigma_{XY}\rVert_{F}^{2}.$

Here in $(\ast)$ we used the calculation: as
$1+tL_{X}(X_{1},X_{2})=(1-t)+t\lVert X_{1}-X_{2}\rVert^{2}/\tau_{X}^{2}$,

$\displaystyle\mathbb{E}\bigg{[}\int_{0}^{s}\frac{(s-t)^{r}}{\big{(}1+tL_{X}(X_{1},X_{2})\big{)}^{\ell}}\,\mathrm{d}t\bigg{]}^{4}\lesssim\int_{0}^{s}\mathbb{E}\big{(}1+tL_{X}(X_{1},X_{2})\big{)}^{-4\ell}\mathrm{d}t$
$\displaystyle\lesssim\int_{0}^{s}(1-t)^{-4\ell}\wedge\big{[}t^{-4\ell}\mathbb{E}(\lVert
X_{1}-X_{2}\rVert^{2}/\tau_{X}^{2})^{-4\ell}\big{]}\mathrm{d}t\stackrel{{\scriptstyle(**)}}{{\lesssim}}_{\ell}\int_{0}^{s}\big{[}(1-t)^{-4\ell}\wedge
t^{-4\ell}\big{]}\mathrm{d}t\lesssim 1,$

using in $(**)$ (7.3) which holds under $p\geq 8\ell+1$ . ∎

###### Proof of Proposition 8.2-Part 1: first moment bounds for
$\psi_{X},\psi_{Y}$.

In view of Lemma 8.1, and the calculation

$\displaystyle\mathbb{E}[\lVert
X_{1}\rVert^{2}X_{1}^{\top}\Sigma_{XY}Y_{1}]=\operatorname{tr}(\Sigma_{X})\operatorname{tr}(\Sigma_{XY}\Sigma_{YX})+2\operatorname{tr}(\Sigma_{XY}\Sigma_{YX}\Sigma_{X}),$

we have

$\displaystyle\mathbb{E}A_{1,X}(X_{1},Y_{1})=2\tau_{X}^{-4}\operatorname{tr}(\Sigma_{XY}\Sigma_{YX}\Sigma_{X}).$
(B.9)

Now we handle the ‘residual’ term $\mathbb{E}A_{2,X}(X_{1},Y_{1})$: By Lemmas
7.2 and B.2,

$\displaystyle\lvert\mathbb{E}A_{2,X}(X_{1},Y_{1})\rvert\lesssim\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}\frac{(1-s)^{3}}{\big{(}1+sL_{X}(X_{1},X_{2})\big{)}^{7/2}}\,\mathrm{d}s\bigg{]}\bigg{\rvert}\lesssim_{M}\tau_{X}^{-4}\lVert\Sigma_{XY}\rVert_{F}^{2}.$

The claim follows. ∎

###### Proof of Proposition 8.2-Part 2: second moment bounds for
$\psi_{X},\psi_{Y}$.

We write $A_{1,X},A_{2,X}$ as $A_{1},A_{2}$ in the proof. We only need to
bound

$\displaystyle\mathbb{E}\psi_{X}^{2}(X_{1},Y_{1})\lesssim\big{[}\mathbb{E}A_{1}^{2}(X_{1},Y_{1})+\mathbb{E}A_{2}^{2}(X_{1},Y_{1})\big{]}.$

Next we bound the above two summands separately.

Let $Z\sim\mathcal{N}(0,I_{p+q})$. To bound
$\operatorname{Var}\big{(}A_{1}(X_{1},Y_{1})\big{)}$, we write

$\displaystyle A_{1}(X_{1},Y_{1})\stackrel{{\scriptstyle
d}}{{=}}A_{1}(Z)=(2\tau_{X}^{4})^{-1}\Big{[}\big{(}Z^{\top}H_{[11]}Z-\operatorname{tr}(H_{[11]})\big{)}Z^{\top}\bar{G}_{[1,2]}Z+2Z^{\top}\bar{G}_{X}Z\Big{]}.$

Here $\bar{G}_{[1,2]}=(G_{[12]}+G_{[21]})/2$ and

$\displaystyle\bar{G}_{X}\equiv\frac{1}{2}\Sigma^{1/2}\begin{pmatrix}0&\Sigma_{X}\Sigma_{XY}\\\
\Sigma_{YX}\Sigma_{X}&0\end{pmatrix}\Sigma^{1/2}.$ (B.10)

By Gaussian-Poincaré inequality and Lemma 7.1, we have

$\displaystyle\operatorname{Var}\big{(}2\tau_{X}^{4}A_{1}(X_{1},Y_{1})\big{)}=4\tau_{X}^{8}\cdot\operatorname{Var}(A_{1}(Z))$
$\displaystyle\lesssim\mathbb{E}(Z^{\top}\bar{G}_{[1,2]}Z)^{2}Z^{\top}H_{[11]}^{2}Z+\mathbb{E}\big{(}Z^{\top}H_{[11]}Z-\operatorname{tr}(H_{[11]})\big{)}^{2}Z^{\top}\bar{G}_{[1,2]}^{2}Z+\mathbb{E}Z^{\top}\bar{G}_{X}^{2}Z$
$\displaystyle\lesssim\big{(}\operatorname{tr}^{2}(\bar{G}_{[1,2]})+\lVert\bar{G}_{[1,2]}\rVert_{F}^{2}\big{)}\lVert
H_{[11]}\rVert_{F}^{2}+\lVert\bar{G}_{X}\rVert_{F}^{2}$
$\displaystyle\lesssim_{M}\lVert\Sigma_{X}\rVert_{F}^{2}\big{(}\lVert\Sigma_{XY}\rVert_{F}^{4}+\lVert\Sigma_{XY}\Sigma_{YX}\rVert_{F}^{2}\big{)}+\lVert\Sigma_{XY}\Sigma_{YX}\rVert_{F}^{2}\lesssim_{M}\tau_{X}^{2}\lVert\Sigma_{XY}\rVert_{F}^{4}.$

This together with (B.9) yields that

$\displaystyle\mathbb{E}A_{1}^{2}(X_{1},Y_{1})$
$\displaystyle=\operatorname{Var}\big{(}A_{1}(X_{1},Y_{1})\big{)}+\big{(}\mathbb{E}A_{1}(X_{1},Y_{1})\big{)}^{2}\lesssim_{M}\tau_{X}^{-6}\lVert\Sigma_{XY}\rVert_{F}^{4}.$
(B.11)

Next we handle $A_{2}$: By definition of $h_{3}$ in Lemma 7.2 and the
parametrization $Y_{2}=\Sigma_{Y\backslash
X}^{1/2}Z_{2;Y}+\Sigma_{YX}\Sigma_{X}^{-1/2}Z_{2;X}$,

$\displaystyle\mathbb{E}A_{2}^{2}(X_{1},Y_{1})\lesssim\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}\frac{(1-s)^{2}}{(1+sL_{X}(X_{1},X_{2}))^{5/2}}\,\mathrm{d}s\bigg{]}\bigg{\\}}^{2}$
$\displaystyle\lesssim\mathbb{E}^{1/4}L_{X}^{24}(X_{1},X_{2})\cdot\mathbb{E}^{1/2}(Z_{2;X}^{\top}\Sigma_{X}^{-1/2}\Sigma_{XY}Y_{1})^{4}\cdot\mathbb{E}^{1/4}\bigg{(}\int_{0}^{1}\frac{(1-s)^{2}}{(1+sL_{X}(X_{1},X_{2}))^{5/2}}\,\mathrm{d}s\bigg{)}^{8}.$

The three terms above can be bounded as follows:

  * •

Lemma 7.4 yields that
$\mathbb{E}^{1/4}L_{X}^{24}(X_{1},X_{2})\lesssim_{M}\tau_{X}^{-6}$.

  * •

With $L\equiv\Sigma_{X}^{-1/2}\Sigma_{XY}\Sigma_{Y}^{1/2}$, we have

$\displaystyle\mathbb{E}^{1/2}\big{(}Z_{2;X}^{\top}\Sigma_{X}^{-1/2}\Sigma_{XY}Y_{1}\big{)}^{4}=\mathbb{E}^{1/2}\big{(}Z_{X}^{\top}LZ_{Y}\big{)}^{4}\lesssim\lVert
L\rVert_{F}^{2}\lesssim_{M}\lVert\Sigma_{XY}\rVert_{F}^{2}.$

  * •

By (7.3), for $p$ larger than an absolute constant, the third term is at most
of constant order.

Combining the estimates yields that

$\displaystyle\mathbb{E}A_{2}^{2}(X_{1},Y_{1})$
$\displaystyle\lesssim_{M}\tau_{X}^{-6}\lVert\Sigma_{XY}\rVert_{F}^{2}.$
(B.12)

Combine (B.11)-(B.12) to conclude the estimate for
$\mathbb{E}\psi_{X}^{2}(X_{1},Y_{1})$. A similar argument applies to
$\mathbb{E}\psi_{Y}^{2}(X_{1},Y_{1})$. ∎

###### Proof of Proposition 8.2-Part 3: second moment bound for $\psi_{X,Y}$.

Using the notation in the proof of Lemma 8.4, and viewing $\psi_{X,Y}$ as a
function of $\Sigma_{XY}$, for any $t\in[0,1]$,

$\displaystyle\psi_{X,Y}(t\Sigma_{XY})=\mathbb{E}_{Z_{2}}\bigg{[}\mathcal{D}h\bigg{(}\frac{\bar{Z}_{1,2}^{\top}H_{[11]}(t)\bar{Z}_{1,2}}{\tau_{X}^{2}}-1\bigg{)}\mathcal{D}h\bigg{(}\frac{\bar{Z}_{1,2}^{\top}H_{[22]}(t)\bar{Z}_{1,2}}{\tau_{Y}^{2}}-1\bigg{)}\bigg{]},$

where

$\displaystyle\mathcal{D}g(Z_{1},Z_{2})\equiv
g(Z_{1},Z_{2})-\mathbb{E}_{Z_{1}}g(Z_{1},Z_{2})-\mathbb{E}_{Z_{2}}g(Z_{1},Z_{2})+\mathbb{E}_{Z_{1},Z_{2}}g(Z_{1},Z_{2}).$

Expanding the product results in 16 terms of form

$\displaystyle
B_{(k,\ell),(k^{\prime},\ell^{\prime})}(t\Sigma_{XY})\equiv\mathbb{E}\bigg{[}h\bigg{(}\frac{\bar{Z}_{k,\ell}^{\top}H_{[11]}(t)\bar{Z}_{k,\ell}}{\tau_{X}^{2}}-1\bigg{)}h\bigg{(}\frac{\bar{Z}_{k^{\prime},\ell^{\prime}}^{\top}H_{[22]}(t)\bar{Z}_{k^{\prime},\ell^{\prime}}}{\tau_{Y}^{2}}-1\bigg{)}\bigg{\lvert}Z_{1}\bigg{]},$

where $k\neq\ell,k^{\prime}\neq\ell^{\prime}$. Using Lemma 8.4 and the moment
estimates in Lemma 7.4, we have

$\displaystyle\mathbb{E}\big{(}\psi_{X,Y}(\Sigma_{X,Y})-\psi_{X,Y}(0)\big{)}^{2}$
$\displaystyle\lesssim\sup_{k,k^{\prime},\ell,\ell^{\prime}}\mathbb{E}\big{(}B_{(k,\ell),(k^{\prime},\ell^{\prime})}(\Sigma_{XY})-B_{(k,\ell),(k^{\prime},\ell^{\prime})}(0)\big{)}$
$\displaystyle\lesssim_{M}\tau_{X}^{-4}\tau_{Y}^{-4}\lVert\Sigma_{XY}\rVert_{F}^{2}(1\vee\lVert\Sigma_{XY}\rVert_{F}^{2})(\tau_{X}\wedge\tau_{Y})^{-2}.$

The claim follows as $\psi_{X,Y}(0)=0$. ∎

##  Appendix C Proofs for Section 9

###  C.1. Proof of Lemma 9.2

###### Proof of Lemma 9.2.

As
$\mathbb{E}_{Z_{2},Z_{3},Z_{4}}U(X_{i_{1}},X_{i_{2}})V(Y_{i_{3}},Y_{i_{4}})=0$,
Proposition 2.1 yields that

$\displaystyle
k_{1}(z_{1})=\frac{1}{4!}\sum_{(i_{1},\ldots,i_{4})\in\sigma(1,2,3,4)}\bigg{[}\mathbb{E}_{Z_{2},Z_{3},Z_{4}}U(X_{i_{1}},X_{i_{2}})V(Y_{i_{1}},Y_{i_{2}})$
$\displaystyle\qquad\qquad-2\mathbb{E}_{Z_{2},Z_{3},Z_{4}}U(X_{i_{1}},X_{i_{2}})V(Y_{i_{1}},Y_{i_{3}})\bigg{]}.$

The claim now follows by calculating

$\displaystyle\sum_{(i_{1},\ldots,i_{4})\in\sigma(1,2,3,4)}\mathbb{E}_{Z_{2},Z_{3},Z_{4}}\big{(}U(X_{i_{1}},X_{i_{2}})V(Y_{i_{1}},Y_{i_{2}})\big{)}$
$\displaystyle\qquad=12\big{(}\mathbb{E}U(x_{1},X)V(y_{1},Y)+\mathbb{E}U(X,X^{\prime})V(Y,Y^{\prime})\big{)},$

and

$\displaystyle\mathbb{E}_{Z_{2},Z_{3},Z_{4}}U(X_{i_{1}},X_{i_{2}})V(Y_{i_{1}},Y_{i_{3}})=0,$

using the double-centered property of $U,V$. ∎

###  C.2. Proof of Lemma 9.3

###### Proof of Lemma 9.3.

Recall the identities involving $U,V$ in (7.3). Then we have

$\displaystyle
g_{1}(x_{1},y_{1})\equiv\frac{1}{2}\bigg{[}\mathbb{E}U(x_{1},X_{2})V(y_{1},Y_{2})-\operatorname{dCov}^{2}(X,Y)\bigg{]}$
$\displaystyle=\frac{1}{2\tau_{X}\tau_{Y}}\bigg{[}\big{(}x_{1}^{\top}\Sigma_{XY}y_{1}-\lVert\Sigma_{XY}\rVert_{F}^{2}\big{)}+\big{(}R_{1}(x_{1},y_{1})-\mathbb{E}R_{1}(X_{1},Y_{1})\big{)}\bigg{]},$

where, with $\psi_{X},\psi_{Y},\psi_{XY}$ defined in (8.1),

$\displaystyle
R_{1}(x_{1},y_{1})\equiv-\tau_{X}^{2}\psi_{X}(x_{1},y_{1})-\tau_{Y}^{2}\psi_{Y}(x_{1},y_{1})+\tau_{X}^{2}\tau_{Y}^{2}\psi_{X,Y}(x_{1},y_{1}).$

By Lemma 8.1, we may write [recall the definitions of $\bar{\psi}_{X}$ and
$\bar{\psi}_{Y}$ in (9.1)]

$\displaystyle\psi_{X}(x_{1},y_{1})$
$\displaystyle=\frac{1}{2\tau_{X}^{4}}\big{(}\lVert
x_{1}\rVert^{2}-\operatorname{tr}(\Sigma_{X})\big{)}\lVert\Sigma_{XY}\rVert_{F}^{2}+\bar{\psi}_{X}(x_{1},y_{1}),$
$\displaystyle\psi_{Y}(x_{1},y_{1})$
$\displaystyle=\frac{1}{2\tau_{Y}^{4}}\big{(}\lVert
y_{1}\rVert^{2}-\operatorname{tr}(\Sigma_{Y})\big{)}\lVert\Sigma_{XY}\rVert_{F}^{2}+\bar{\psi}_{Y}(x_{1},y_{1}).$

The claim follows. ∎

###  C.3. Proof of Lemma 9.4

###### Proof of Lemma 9.4.

Note that

$\displaystyle\mathbb{E}\bar{g}_{1}^{2}(X,Y)$
$\displaystyle=\frac{1}{4\tau_{X}^{2}\tau_{Y}^{2}}\Big{[}\mathbb{E}(X^{\top}\Sigma_{XY}Y-\lVert\Sigma_{XY}\rVert_{F}^{2})^{2}+\mathbb{E}\mathscr{A}_{1,X}(X,Y)^{2}+\mathbb{E}\mathscr{A}_{1,Y}(X,Y)^{2}$
$\displaystyle\qquad\qquad+2\mathbb{E}(X^{\top}\Sigma_{XY}Y)\mathscr{A}_{1,X}(X,Y)+2\mathbb{E}(X^{\top}\Sigma_{XY}Y)\mathscr{A}_{1,Y}(X,Y)$
$\displaystyle\qquad\qquad+2\mathbb{E}\mathscr{A}_{1,X}(X,Y)\mathscr{A}_{1,Y}(X,Y)\Big{]}.$

The terms can be calculated as follows:

  * •

Direct calculation yields that

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

  * •

Direct calculation yields that

$\displaystyle\mathbb{E}\mathscr{A}_{1,X}(X,Y)^{2}$
$\displaystyle=\frac{\lVert\Sigma_{XY}\rVert_{F}^{4}}{4\tau_{X}^{4}}\operatorname{Var}(\lVert
X_{1}\rVert^{2})=\frac{\lVert\Sigma_{XY}\rVert_{F}^{4}}{4\tau_{X}^{4}}\cdot
2\lVert\Sigma_{X}\rVert_{F}^{2}=\frac{\lVert\Sigma_{XY}\rVert_{F}^{4}\lVert\Sigma_{X}\rVert_{F}^{2}}{2\tau_{X}^{4}}$

and similarly
$\mathbb{E}\mathscr{A}_{1,Y}(X,Y)^{2}=\lVert\Sigma_{XY}\rVert_{F}^{4}\lVert\Sigma_{Y}\rVert_{F}^{2}/(2\tau_{Y}^{4})$.

  * •

We have

$\displaystyle\mathbb{E}(X^{\top}\Sigma_{XY}Y)\mathscr{A}_{1,X}(X,Y)$
$\displaystyle=-\frac{\lVert\Sigma_{XY}\rVert_{F}^{2}}{2\tau_{X}^{2}}\mathbb{E}\Big{[}(X^{\top}\Sigma
Y)(\lVert X\rVert^{2}-\operatorname{tr}(\Sigma_{X}))\Big{]}$
$\displaystyle=-\frac{\lVert\Sigma_{XY}\rVert_{F}^{2}}{\tau_{X}^{2}}\operatorname{tr}(\Sigma_{XY}\Sigma_{YX}\Sigma_{X}),$

and similarly
$\mathbb{E}(X^{\top}\Sigma_{XY}Y)\mathscr{A}_{1,Y}(X,Y)=-\lVert\Sigma_{XY}\rVert_{F}^{2}\cdot\operatorname{tr}(\Sigma_{XY}\Sigma_{YX}\Sigma_{X})/\tau_{X}^{2}$.

  * •

We have

$\displaystyle\mathbb{E}\mathscr{A}_{1,X}(X,Y)\mathscr{A}_{1,Y}(X,Y)$
$\displaystyle=\frac{\lVert\Sigma_{XY}\rVert_{F}^{4}}{4\tau_{X}^{2}\tau_{Y}^{2}}\mathbb{E}\Big{[}(\lVert
X\rVert^{2}-\operatorname{tr}(\Sigma_{X}))(\lVert
Y\rVert^{2}-\operatorname{tr}(\Sigma_{Y}))\Big{]}$
$\displaystyle=\frac{\lVert\Sigma_{XY}\rVert_{F}^{4}}{4\tau_{X}^{2}\tau_{Y}^{2}}\cdot
2\lVert\Sigma_{XY}\rVert_{F}^{2}=\frac{\lVert\Sigma_{XY}\rVert_{F}^{6}}{2\tau_{X}^{2}\tau_{Y}^{2}}.$

The proof is complete. ∎

###  C.4. Proof of Lemma 9.5

###### Proof of Lemma 9.5.

(1). Let $Z_{1}\sim\mathcal{N}(0,I_{p+q})$. Then we may write

$\displaystyle\bar{g}_{1}(X,Y)\stackrel{{\scriptstyle
d}}{{=}}\bar{g}_{1}(Z)\equiv\frac{1}{4\tau_{X}\tau_{Y}}\cdot\Big{[}Z^{\top}AZ-\mathbb{E}(Z^{\top}AZ)\Big{]},$

where the symmetric matrix $A$ is defined by

$\displaystyle A\equiv
G_{[12]}+G_{[21]}-\frac{\lVert\Sigma_{XY}\rVert_{F}^{2}}{\tau_{X}^{2}}H_{[11]}-\frac{\lVert\Sigma_{XY}\rVert_{F}^{2}}{\tau_{Y}^{2}}H_{[22]}.$

So by Lemma F.3-(1), we have

$\displaystyle\mathbb{E}\bar{g}_{1}^{2}(X,Y)=\frac{1}{16\tau_{X}^{2}\tau_{Y}^{2}}\cdot
2\lVert A\rVert_{F}^{2}$
$\displaystyle=\frac{1}{8\tau_{X}^{2}\tau_{Y}^{2}}\bigg{\lVert}\Sigma^{1/2}\begin{pmatrix}-\big{(}\lVert\Sigma_{XY}\rVert_{F}^{2}/\tau_{X}^{2}\big{)}I_{p}&\Sigma_{XY}\\\
\Sigma_{YX}&-\big{(}\lVert\Sigma_{XY}\rVert_{F}^{2}/\tau_{Y}^{2}\big{)}I_{q}\end{pmatrix}\Sigma^{1/2}\bigg{\rVert}_{F}^{2}$
$\displaystyle\gtrsim_{M}\tau_{X}^{-2}\tau_{Y}^{-2}\bigg{\lVert}\begin{pmatrix}-\big{(}\lVert\Sigma_{XY}\rVert_{F}^{2}/\tau_{X}^{2}\big{)}I_{p}&\Sigma_{XY}\\\
\Sigma_{YX}&-\big{(}\lVert\Sigma_{XY}\rVert_{F}^{2}/\tau_{Y}^{2}\big{)}I_{q}\end{pmatrix}\bigg{\rVert}_{F}^{2}\gtrsim\tau_{X}^{-2}\tau_{Y}^{-2}\lVert\Sigma_{XY}\rVert_{F}^{2}.$

If the spectrum of $\Sigma$ is bounded above as well, then using Lemma F.5, we
have

  * •

$\lVert\Sigma_{XY}\Sigma_{YX}\rVert_{F}^{2}\lesssim_{M}\lVert\Sigma_{XY}\rVert_{F}^{2}$;

  * •

$\operatorname{tr}(\Sigma_{XY}\Sigma_{Y}\Sigma_{YX}\Sigma_{X})\asymp_{M}\lVert\Sigma_{XY}\rVert_{F}^{2}$;

  * •

$\frac{\lVert\Sigma_{XY}\rVert_{F}^{4}\lVert\Sigma_{X}\rVert_{F}^{2}}{2\tau_{X}^{4}}\vee\frac{\lVert\Sigma_{XY}\rVert_{F}^{4}\lVert\Sigma_{Y}\rVert_{F}^{2}}{2\tau_{Y}^{4}}\lesssim_{M}(\tau_{X}^{-2}\vee\tau_{Y}^{-2})\lVert\Sigma_{XY}\rVert_{F}^{2}(\tau_{X}^{2}\wedge\tau_{Y}^{2})\lesssim\lVert\Sigma_{XY}\rVert_{F}^{2}$;

  * •

$\frac{\lVert\Sigma_{XY}\rVert_{F}^{2}\operatorname{tr}(\Sigma_{XY}\Sigma_{YX}\Sigma_{X})}{\tau_{X}^{2}}\vee\frac{\lVert\Sigma_{XY}\rVert_{F}^{2}\operatorname{tr}(\Sigma_{YX}\Sigma_{XY}\Sigma_{Y})}{\tau_{Y}^{2}}\lesssim_{M}\frac{\lVert\Sigma_{XY}\rVert_{F}^{4}}{(\tau_{X}\wedge\tau_{Y})^{2}}\lesssim_{M}\lVert\Sigma_{XY}\rVert_{F}^{2}$;

  * •

$\frac{\lVert\Sigma_{XY}\rVert_{F}^{6}}{\tau_{X}^{2}\tau_{Y}^{2}}\lesssim_{M}\lVert\Sigma_{XY}\rVert_{F}^{2}\frac{\tau_{X}^{4}\wedge\tau_{Y}^{4}}{\tau_{X}^{2}\tau_{Y}^{2}}\lesssim\lVert\Sigma_{XY}\rVert_{F}^{2}.$

Collecting the bounds we conclude that
$\mathbb{E}\bar{g}_{1}^{2}(X,Y)\lesssim_{M}\tau_{X}^{-2}\tau_{Y}^{-2}\lVert\Sigma_{XY}\rVert_{F}^{2}$.

(2). When $X=Y$, we may write with $Z\sim\mathcal{N}(0,I_{p})$ that

$\displaystyle\bar{g}_{1}(Z)=\bar{g}_{1}(X,Y)\stackrel{{\scriptstyle
d}}{{=}}\frac{1}{2\tau_{X}^{2}}\cdot\Big{[}Z^{\top}\bar{A}Z-\mathbb{E}(Z^{\top}\bar{A}Z)\Big{]},$

with the symmetric matrix $\bar{A}$ defined by
$\bar{A}\equiv\Sigma_{X}^{1/2}\Big{[}\Sigma_{X}-\lVert\Sigma_{X}\rVert_{F}^{2}/\tau_{X}^{2}\Big{]}\Sigma_{X}^{1/2}$.
So

$\displaystyle\mathbb{E}\bar{g}_{1}^{2}(X,Y)$
$\displaystyle\asymp\tau_{X}^{-4}\bigg{\lVert}\Sigma_{X}^{1/2}\Big{[}\Sigma_{X}-\lVert\Sigma_{X}\rVert_{F}^{2}/\tau_{X}^{2}\Big{]}\Sigma_{X}^{1/2}\bigg{\rVert}_{F}^{2}$
$\displaystyle\gtrsim_{M}\tau_{X}^{-4}\big{\lVert}\Sigma_{X}-\lVert\Sigma_{X}\rVert_{F}^{2}/\tau_{X}^{2}\big{\rVert}_{F}^{2}=\tau_{X}^{-4}\cdot\lVert\Sigma_{X}\rVert_{F}^{4}p/\tau_{X}^{4}.$

A matching upper bound can be easily proved under the condition
$\lVert\Sigma_{X}\rVert_{\operatorname{op}}\leq M$. The proof is complete. ∎

###  C.5. Proof of Lemma 9.6

###### Proof of Lemma 9.6.

We only prove the case for $\bar{\psi}_{X}$. In the definition (9.1) of
$\bar{\psi}_{X}(X,Y)$, we write
$\bar{\psi}_{X}(x_{1},y_{1})\equiv\bar{A}_{1,X}(x_{1},y_{1})+A_{2,X}(x_{1},y_{1})$.
Then we have

$\displaystyle\operatorname{Var}\big{(}\bar{\psi}_{X}(X,Y)\big{)}\lesssim\operatorname{Var}\big{(}\bar{A}_{1,X}(X,Y))+\operatorname{Var}\big{(}A_{2,X}(X,Y)\big{)}.$

Let $Z\sim\mathcal{N}(0,I_{p+q})$. We may write

$\displaystyle\bar{A}_{1,X}(X,Y)$
$\displaystyle=\frac{1}{2\tau_{X}^{4}}\bigg{[}\big{(}\lVert
X_{1}\rVert^{2}-\operatorname{tr}(\Sigma_{X})\big{)}(X^{\top}\Sigma_{XY}Y-\lVert\Sigma_{XY}\rVert_{F}^{2})+2X^{\top}\Sigma_{X}\Sigma_{XY}Y\bigg{]}$
$\displaystyle\stackrel{{\scriptstyle
d}}{{=}}\frac{1}{2\tau_{X}^{4}}\bigg{[}\big{(}Z^{\top}H_{[11]}Z-\operatorname{tr}(H_{[11]})\big{)}\big{(}Z^{\top}\bar{G}_{[1,2]}Z-\operatorname{tr}(\bar{G}_{[1,2]})\big{)}+2Z^{\top}\bar{G}_{X}Z\bigg{]},$

with $\bar{G}_{X}$ is defined in (B.10). By Gaussian-Poincaré inequality, we
have

$\displaystyle\operatorname{Var}\big{(}\tau_{X}^{4}\bar{A}_{1,X}(X,Y)\big{)}$
$\displaystyle=\operatorname{Var}\big{(}\tau_{X}^{4}\bar{A}_{1,X}(Z)\big{)}$
$\displaystyle\lesssim\mathbb{E}\big{(}Z^{\top}H_{[11]}Z-\operatorname{tr}(H_{[11]})\big{)}^{2}Z^{\top}\bar{G}_{[1,2]}^{2}Z$
$\displaystyle\qquad+\mathbb{E}\big{(}Z^{\top}\bar{G}_{[1,2]}Z-\operatorname{tr}(\bar{G}_{[1,2]})\big{)}^{2}Z^{\top}G_{[11]}Z+\mathbb{E}Z^{\top}\bar{G}_{X}^{2}Z$
$\displaystyle\lesssim\lVert G_{[12]}\rVert_{F}^{2}\lVert
H_{[11]}\rVert_{F}^{2}+\lVert\bar{G}_{X}\rVert_{F}^{2}\lesssim_{M}\tau_{X}^{2}\lVert\Sigma_{XY}\rVert_{F}^{2},$

On the other hand, by the estimate in (B.12),

$\displaystyle\operatorname{Var}\big{(}A_{2,X}(X,Y)\big{)}\lesssim\mathbb{E}A_{2,X}^{2}(X,Y)\lesssim_{M}\tau_{X}^{-6}\lVert\Sigma_{XY}\rVert_{F}^{2}.$

Collecting the bounds to conclude. ∎

###  C.6. Proof of Lemma 9.8

###### Proof of Lemma 9.8.

As $\mathbb{E}_{Z_{3},Z_{4}}U(X_{i_{1}},X_{i_{2}})V(Y_{i_{3}},Y_{i_{4}})=0$,
Proposition 2.1 yields that

$\displaystyle k_{2}(z_{1},z_{2})$
$\displaystyle=\frac{1}{4!}\sum_{(i_{1},\ldots,i_{4})\in\sigma(1,2,3,4)}\bigg{[}\mathbb{E}_{Z_{3},Z_{4}}U(X_{i_{1}},X_{i_{2}})V(Y_{i_{1}},Y_{i_{2}})$
$\displaystyle\qquad\qquad-2\mathbb{E}_{Z_{3},Z_{4}}U(X_{i_{1}},X_{i_{2}})V(Y_{i_{1}},Y_{i_{3}})\bigg{]}.$

The claim now follows by calculating

$\displaystyle\sum_{(i_{1},\ldots,i_{4})\in\sigma(1,2,3,4)}\mathbb{E}_{Z_{3},Z_{4}}U(X_{i_{1}},X_{i_{2}})V(Y_{i_{1}},Y_{i_{2}})$
$\displaystyle=4U(x_{1},x_{2})V(y_{1},y_{2})+8\mathbb{E}U(x_{1},X)V(y_{1},Y)+8\mathbb{E}U(x_{2},X)V(y_{2},Y)+4\operatorname{dCov}^{2}(X,Y),$

and

$\displaystyle\sum_{(i_{1},\ldots,i_{4})\in\sigma(1,2,3,4)}\mathbb{E}_{Z_{3},Z_{4}}U(X_{i_{1}},X_{i_{2}})V(Y_{i_{1}},Y_{i_{3}})$
$\displaystyle=\bigg{[}\sum_{\begin{subarray}{c}(i_{1},\ldots,i_{4})\in\sigma(1,2,3,4),\\\
i_{2}=1,i_{3}=2\end{subarray}}+\sum_{\begin{subarray}{c}(i_{1},\ldots,i_{4})\in\sigma(1,2,3,4),\\\
i_{2}=2,i_{3}=1\end{subarray}}\bigg{]}\mathbb{E}_{Z_{3},Z_{4}}U(X_{i_{1}},X_{i_{2}})V(Y_{i_{1}},Y_{i_{3}})$
$\displaystyle=2\mathbb{E}U(x_{1},X)V(y_{2},Y)+2\mathbb{E}U(x_{2},X)V(y_{1},Y),$

as desired. ∎

###  C.7. Proof of Lemma 9.9

###### Proof of Lemma 9.9.

By definition of $g_{2}$, we have

$\displaystyle g_{2}\big{(}(x_{1},y_{1}),(x_{2},y_{2})\big{)}$
$\displaystyle\equiv
k_{2}\big{(}(x_{1},y_{1}),(x_{2},y_{2})\big{)}-k_{1}(x_{1},y_{1})-k_{1}(x_{2},y_{2})+\operatorname{dCov}^{2}(X,Y)$
$\displaystyle=\frac{1}{6}\bigg{[}U(x_{1},x_{2})V(y_{1},y_{2})-\mathbb{E}U(x_{1},X)V(y_{1},Y)-\mathbb{E}U(x_{2},X)V(y_{2},Y)+\operatorname{dCov}^{2}(X,Y)$
$\displaystyle\qquad\qquad-\mathbb{E}U(x_{1},X)V(y_{2},Y)-\mathbb{E}U(x_{2},X)V(y_{1},Y)\bigg{]}$
$\displaystyle=\frac{1}{6\tau_{X}\tau_{Y}}\bigg{[}\Big{(}x_{1}^{\top}x_{2}y_{1}^{\top}y_{2}-x_{1}^{\top}\Sigma_{XY}y_{1}-x_{2}^{\top}\Sigma_{XY}y_{2}+\lVert\Sigma_{XY}\rVert_{F}^{2}\Big{)}-\Big{(}x_{1}^{\top}\Sigma_{XY}y_{2}+x_{2}^{\top}\Sigma_{XY}y_{1}\Big{)}$
$\displaystyle\qquad\qquad+\big{[}\bar{R}_{2}\big{(}(x_{1},y_{1}),(x_{2},y_{2})\big{)}-\mathbb{E}\bar{R}_{2}\big{(}(X_{1},Y_{1}),(X_{2},Y_{2})\big{)}\big{]}\bigg{]},$

completing the proof. ∎

###  C.8. Proof of Lemma 9.11

###### Proof of Lemma 9.11.

As $\mathbb{E}_{Z_{4}}U(X_{i_{1}},X_{i_{2}})V(Y_{i_{3}},Y_{i_{4}})=0$,
Proposition 2.1 yields that

$\displaystyle k_{3}(z_{1},z_{2},z_{3})$
$\displaystyle=\frac{1}{4!}\sum_{(i_{1},\ldots,i_{4})\in\sigma(1,2,3,4)}\bigg{[}\mathbb{E}_{Z_{4}}U(X_{i_{1}},X_{i_{2}})V(Y_{i_{1}},Y_{i_{2}})-2\mathbb{E}_{Z_{4}}U(X_{i_{1}},X_{i_{2}})V(Y_{i_{1}},Y_{i_{3}})\bigg{]}.$

The claim follows by calculating

$\displaystyle\sum_{(i_{1},\ldots,i_{4})\in\sigma(1,2,3,4)}\mathbb{E}_{Z_{4}}U(X_{i_{1}},X_{i_{2}})V(Y_{i_{1}},Y_{i_{2}})$
$\displaystyle=\bigg{[}\sum_{\begin{subarray}{c}(i_{1},\ldots,i_{4})\in\sigma(1,2,3,4)\\\
i_{1},i_{2}\neq
4\end{subarray}}+\sum_{\begin{subarray}{c}(i_{1},\ldots,i_{4})\in\sigma(1,2,3,4)\\\
i_{1}=4\end{subarray}}+\sum_{\begin{subarray}{c}(i_{1},\ldots,i_{4})\in\sigma(1,2,3,4)\\\
i_{2}=4\end{subarray}}\bigg{]}\mathbb{E}_{Z_{4}}U(X_{i_{1}},X_{i_{2}})V(Y_{i_{1}},Y_{i_{2}})$
$\displaystyle=2\sum_{1\leq i_{1}\neq i_{2}\leq
3}U(x_{i_{1}},x_{i_{2}})V(y_{i_{1}},y_{i_{2}})+4\sum_{1\leq i\leq
3}\mathbb{E}U(X,x_{i})V(Y,y_{i}),$

and

$\displaystyle\sum_{(i_{1},\ldots,i_{4})\in\sigma(1,2,3,4)}\mathbb{E}_{Z_{4}}U(X_{i_{1}},X_{i_{2}})V(Y_{i_{1}},Y_{i_{3}})$
$\displaystyle=\bigg{[}\sum_{\begin{subarray}{c}(i_{1},\ldots,i_{4})\in\sigma(1,2,3,4),\\\
i_{1}=4\end{subarray}}+\sum_{\begin{subarray}{c}(i_{1},\ldots,i_{4})\in\sigma(1,2,3,4),\\\
i_{4}=4\end{subarray}}\bigg{]}\mathbb{E}_{Z_{4}}U(X_{i_{1}},X_{i_{2}})V(Y_{i_{1}},Y_{i_{3}})$
$\displaystyle=\sum_{1\leq i_{1}\neq i_{2}\leq
3}\mathbb{E}U(X,x_{i_{1}})V(Y,y_{i_{2}})+\sum_{(i_{1},i_{2},i_{3})\in\sigma(1,2,3)}U(x_{i_{1}},x_{i_{2}})V(y_{i_{1}},y_{i_{3}}),$

as desired. ∎

##  Appendix D Proofs for Section 10

###  D.1. Proof of Lemma 10.3

###### Proof of Lemma 10.3.

This follows calculations with the definition (10.1) of $\bar{T}_{n}$:

$\displaystyle\bar{T}_{n}\big{(}\bm{X},\bm{Y}\big{)}=\operatorname{dCov}^{2}(X,Y)$
$\displaystyle+\frac{2}{\tau_{X}\tau_{Y}n}\sum_{i}\Big{(}X_{i}^{\top}\Sigma_{XY}Y_{i}-\lVert\Sigma_{XY}\rVert_{F}^{2}-\frac{\lVert\Sigma_{XY}\rVert_{F}^{2}}{2\tau_{X}^{2}}(\lVert
X_{i}\rVert^{2}-\operatorname{tr}(\Sigma_{X}))-\frac{\lVert\Sigma_{XY}\rVert_{F}^{2}}{2\tau_{Y}^{2}}(\lVert
Y_{i}\rVert^{2}-\operatorname{tr}(\Sigma_{Y}))\Big{)}$
$\displaystyle\qquad+\frac{1}{\tau_{X}\tau_{Y}\cdot
2\binom{n}{2}}\sum_{I_{n}^{2}}\bigg{[}\Big{(}X_{i_{1}}^{\top}X_{i_{2}}Y_{i_{1}}^{\top}Y_{i_{2}}-X_{i_{1}}^{\top}\Sigma_{XY}Y_{i_{1}}-X_{i_{2}}^{\top}\Sigma_{XY}Y_{i_{2}}+\lVert\Sigma_{XY}\rVert_{F}^{2}\Big{)}$
$\displaystyle\qquad\qquad\qquad\qquad-\Big{(}X_{i_{1}}^{\top}\Sigma_{XY}Y_{i_{2}}+X_{i_{2}}^{\top}\Sigma_{XY}Y_{i_{1}}\Big{)}\bigg{]}$
$\displaystyle=\operatorname{dCov}^{2}(X,Y)-\frac{2}{\tau_{X}\tau_{Y}n}\sum_{i=1}^{n}\bigg{[}\frac{\lVert\Sigma_{XY}\rVert_{F}^{2}}{2\tau_{X}^{2}}\big{(}\lVert
X_{i}\rVert^{2}-\operatorname{tr}(\Sigma_{X})\big{)}+\frac{\lVert\Sigma_{XY}\rVert_{F}^{2}}{2\tau_{Y}^{2}}\big{(}\lVert
Y_{i}\rVert^{2}-\operatorname{tr}(\Sigma_{Y})\big{)}\bigg{]}$
$\displaystyle\qquad\qquad+\frac{1}{\tau_{X}\tau_{Y}\cdot
2\binom{n}{2}}\sum_{I_{n}^{2}}\bigg{[}\Big{(}X_{i_{1}}^{\top}X_{i_{2}}Y_{i_{1}}^{\top}Y_{i_{2}}-\lVert\Sigma_{XY}\rVert_{F}^{2}\Big{)}-\Big{(}X_{i_{1}}^{\top}\Sigma_{XY}Y_{i_{2}}+X_{i_{2}}^{\top}\Sigma_{XY}Y_{i_{1}}\Big{)}\bigg{]}.$

The claim now follows by the definitions of $\psi_{1}$-$\psi_{3}$. ∎

###  D.2. Proof of Proposition 10.4

####  D.2.1. Variance bound

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

With $W_{i}\equiv X_{i}Y_{i}^{\top}$, we have

$\displaystyle\Delta_{i}\psi_{1}\big{(}\bm{X},\bm{Y}\big{)}=\psi_{1}\big{(}\bm{X},\bm{Y}\big{)}-\psi_{1}\big{(}\bm{X}^{\\{i\\}},\bm{Y}^{\\{i\\}}\big{)}$
$\displaystyle=\sum_{\begin{subarray}{c}i_{1}\neq i_{2},\\\ i_{1},i_{2}\neq
i\end{subarray}}\operatorname{tr}\big{(}W_{i_{1}}W_{i_{2}}^{\top}\big{)}+2\sum_{j\neq
i}\operatorname{tr}(W_{i}W_{j}^{\top})-\bigg{[}\sum_{\begin{subarray}{c}i_{1}\neq
i_{2},\\\ i_{1},i_{2}\neq
i\end{subarray}}\operatorname{tr}\big{(}W_{i_{1}}W_{i_{2}}^{\top}\big{)}+2\sum_{j\neq
i}\operatorname{tr}(W_{i}^{\prime}W_{j}^{\top})\bigg{]}$
$\displaystyle=2\operatorname{tr}\bigg{[}\big{(}W_{i}-W_{i}^{\prime}\big{)}\sum_{j\neq
i}W_{j}^{\top}\bigg{]}=2\bigg{[}Y_{i}^{\top}\Big{(}\sum_{j\neq
i}Y_{j}X_{j}^{\top}\Big{)}X_{i}-Y_{i}^{\prime\top}\Big{(}\sum_{j\neq
i}Y_{j}X_{j}^{\top}\Big{)}X_{i}^{\prime}\bigg{]}.$ (D.1)

So for any $A\subset\\{1,\ldots,n\\}$ and $i\notin A$,

$\displaystyle\Delta_{i}\psi_{1}\big{(}\bm{X}^{A},\bm{Y}^{A}\big{)}=2\operatorname{tr}\bigg{[}\big{(}W_{i}-W_{i}^{\prime}\big{)}\bigg{(}\sum_{j\notin
A\cup\\{i\\}}W_{j}+\sum_{j\in A}W_{j}^{\prime}\bigg{)}^{\top}\bigg{]}$
$\displaystyle=2\bigg{[}Y_{i}^{\top}\bigg{(}\sum_{j\notin
A\cup\\{i\\}}Y_{j}X_{j}^{\top}+\sum_{j\in
A}Y_{j}^{\prime}X_{j}^{\prime\top}\bigg{)}X_{i}-Y_{i}^{\prime\top}\bigg{(}\sum_{j\notin
A\cup\\{i\\}}Y_{j}X_{j}^{\top}+\sum_{j\in
A}Y_{j}^{\prime}X_{j}^{\prime\top}\bigg{)}X_{i}^{\prime}\bigg{]}.$

Then with
$\mathbb{E}^{\prime}\equiv\mathbb{E}_{\bm{X}^{\prime},\bm{Y}^{\prime}}$, we
have

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

The four terms can be calculated as follows:

  * •

By direct calculation,

$\displaystyle B_{1}(i,A)$ $\displaystyle=Y_{i}^{\top}\Big{(}\sum_{j\neq
i}Y_{j}X_{j}^{\top}\Big{)}X_{i}\cdot Y_{i}^{\top}\Big{(}\sum_{j\notin
A\cup\\{i\\}}Y_{j}X_{j}^{\top}+|A|\cdot\Sigma_{YX}\Big{)}X_{i}$
$\displaystyle=\sum_{j\neq i,k\notin
A\cup\\{i\\}}(X_{i}^{\top}X_{j})(Y_{i}^{\top}Y_{j})(X_{i}^{\top}X_{k})(Y_{i}^{\top}Y_{k})$
$\displaystyle\quad\quad\quad+|A|(X_{i}^{\top}\Sigma_{XY}Y_{i})\cdot\sum_{j\neq
i}(X_{i}^{\top}X_{j})(Y_{i}^{\top}Y_{j}).$

  * •

Using independence between $(X_{i}^{\prime},Y_{i}^{\prime})$ and
$\\{(X_{j}^{\prime},Y_{j}^{\prime})\\}_{j\in A}$ as $i\notin A$,

$\displaystyle B_{2}(i,A)$ $\displaystyle=Y_{i}^{\top}\Big{(}\sum_{j\neq
i}Y_{j}X_{j}^{\top}\Big{)}X_{i}\cdot\operatorname{tr}\Big{[}\Big{(}\sum_{j\notin
A\cup\\{i\\}}Y_{j}X_{j}^{\top}+|A|\cdot\Sigma_{YX}\Big{)}\Sigma_{XY}\Big{]}$
$\displaystyle=\sum_{j\neq i,k\notin
A\cup\\{i\\}}(X_{i}^{\top}X_{j})(Y_{i}^{\top}Y_{j})(X_{k}^{\top}\Sigma_{XY}Y_{k})+|A|\lVert\Sigma_{XY}\rVert_{F}^{2}\cdot\sum_{j\neq
i}(X_{i}^{\top}X_{j})(Y_{i}^{\top}Y_{j}).$

  * •

Again by independence between $(X_{i}^{\prime},Y_{i}^{\prime})$ and
$\\{(X_{j}^{\prime},Y_{j}^{\prime})\\}_{j\in A}$ as $i\notin A$,

$\displaystyle B_{3}(i,A)$
$\displaystyle=\operatorname{tr}\Big{(}\Big{[}\sum_{j\neq
i}Y_{j}X_{j}^{\top}\Big{]}\Sigma_{XY}\Big{)}\cdot
Y_{i}^{\top}\Big{(}\sum_{j\notin
A\cup\\{i\\}}Y_{j}X_{j}^{\top}+|A|\cdot\Sigma_{YX}\Big{)}X_{i}$
$\displaystyle=\sum_{j\neq i,k\notin
A\cup\\{i\\}}(X_{j}^{\top}\Sigma_{XY}Y_{j})(X_{i}^{\top}X_{k})(Y_{i}^{\top}Y_{k})+|A|(X_{i}^{\top}\Sigma_{XY}Y_{i})\cdot\sum_{j\neq
i}X_{j}^{\top}\Sigma_{XY}Y_{j}.$

  * •

By Lemma F.4-(4), we have

$\displaystyle B_{4}(i,A)$
$\displaystyle=\mathbb{E}^{\prime}\Big{[}X_{i}^{\prime\top}\Big{(}\sum_{j\neq
i}X_{j}Y_{j}^{\top}\Big{)}Y_{i}^{\prime}\cdot
X_{i}^{\prime\top}\Big{(}\sum_{j\notin
A\cup\\{i\\}}X_{j}Y_{j}^{\top}+|A|\cdot\Sigma_{XY}\Big{)}Y_{i}^{\prime}\Big{]}$
$\displaystyle=\operatorname{tr}\Big{[}\Sigma_{X}\Big{(}\sum_{j\neq
i}X_{j}Y_{j}^{\top}\Big{)}\Sigma_{Y}\Big{(}\sum_{j\notin
A\cup\\{i\\}}Y_{j}X_{j}^{\top}+|A|\cdot\Sigma_{YX}\Big{)}\Big{]}$
$\displaystyle\quad\quad\quad+\operatorname{tr}\Big{[}\Big{(}\sum_{j\neq
i}X_{j}Y_{j}^{\top}\Big{)}\Sigma_{YX}\Big{(}\sum_{j\notin
A\cup\\{i\\}}X_{j}Y_{j}^{\top}+|A|\cdot\Sigma_{XY}\Big{)}\Sigma_{YX}\Big{]}$
$\displaystyle\quad\quad\quad+\operatorname{tr}\Big{[}\Big{(}\sum_{j\neq
i}X_{j}Y_{j}^{\top}\Big{)}\Sigma_{YX}\Big{]}\cdot\operatorname{tr}\Big{[}\Big{(}\sum_{j\notin
A\cup\\{i\\}}X_{j}Y_{j}^{\top}+|A|\cdot\Sigma_{XY}\Big{)}\Sigma_{YX}\Big{]}$
$\displaystyle=\Big{[}\sum_{j\neq i,k\notin
A\cup\\{i\\}}(X_{j}^{\top}\Sigma_{X}X_{k})(Y_{j}^{\top}\Sigma_{Y}Y_{k})+|A|\cdot\sum_{j\neq
i}X_{j}^{\top}\Sigma_{X}\Sigma_{XY}\Sigma_{Y}Y_{j}\Big{]}$
$\displaystyle\quad\quad\quad+\Big{[}\sum_{j\neq i,k\notin
A\cup\\{i\\}}(X_{j}^{\top}\Sigma_{XY}Y_{k})(X_{k}^{\top}\Sigma_{XY}Y_{j})+|A|\cdot\sum_{j\neq
i}X_{j}^{\top}\Sigma_{XY}\Sigma_{YX}\Sigma_{XY}Y_{j}\Big{]}$
$\displaystyle\quad\quad\quad+\Big{[}\sum_{j\neq i,k\notin
A\cup\\{i\\}}(X_{j}^{\top}\Sigma_{XY}Y_{j})(X_{k}^{\top}\Sigma_{XY}Y_{k})+|A|\lVert\Sigma_{XY}\rVert_{F}^{2}\cdot\sum_{j\neq
i}X_{j}^{\top}\Sigma_{XY}Y_{j}\Big{]}.$

Hence we have

$\displaystyle B_{1}(i,A)-B_{2}(i,A)$ $\displaystyle=\sum_{j\neq i,k\notin
A\cup\\{i\\}}(X_{i}^{\top}X_{j})(Y_{i}^{\top}Y_{j})\big{[}X_{k}^{\top}(X_{i}Y_{i}^{\top}-\Sigma_{XY})Y_{k}\big{]}$
$\displaystyle\quad\quad\quad+|A|\cdot\big{(}X_{i}^{\top}\Sigma_{XY}Y_{i}-\lVert\Sigma_{XY}\rVert_{F}^{2}\big{)}\cdot\sum_{j\neq
i}(X_{i}^{\top}X_{j})(Y_{i}^{\top}Y_{j}),$

and, by combining $-B_{3}(i,A)$ with the last term of $B_{4}(i,A)$,

$\displaystyle B_{4}(i,A)-B_{3}(i,A)$ $\displaystyle=\sum_{j\neq i,k\notin
A\cup\\{i\\}}(X_{j}^{\top}\Sigma_{X}X_{k})(Y_{j}^{\top}\Sigma_{Y}Y_{k})+|A|\cdot\sum_{j\neq
i}X_{j}^{\top}\Sigma_{X}\Sigma_{XY}\Sigma_{Y}Y_{j}$
$\displaystyle\quad\quad\quad+\sum_{j\neq i,k\notin
A\cup\\{i\\}}(X_{j}^{\top}\Sigma_{XY}Y_{k})(X_{k}^{\top}\Sigma_{XY}Y_{j})+|A|\cdot\sum_{j\neq
i}X_{j}^{\top}\Sigma_{XY}\Sigma_{YX}\Sigma_{XY}Y_{j}$
$\displaystyle\quad\quad\quad-\sum_{j\neq i,k\notin
A\cup\\{i\\}}(X_{j}^{\top}\Sigma_{XY}Y_{j})\big{[}X_{k}^{\top}(X_{i}Y_{i}^{\top}-\Sigma_{XY})Y_{k}\big{]}$
$\displaystyle\quad\quad\quad-|A|\cdot(X_{i}^{\top}\Sigma_{XY}Y_{i}-\lVert\Sigma_{XY}\rVert_{F}^{2})\cdot\sum_{j\neq
i}X_{j}^{\top}\Sigma_{XY}Y_{j}.$

This implies that

$\displaystyle
4^{-1}\mathbb{E}^{\prime}\big{[}\Delta_{i}\psi_{1}\big{(}\bm{X},\bm{Y}\big{)}\Delta_{i}\psi_{1}\big{(}\bm{X}^{A},\bm{Y}^{A}\big{)}\big{]}$
$\displaystyle=\sum_{j\neq i,k\notin
A\cup\\{i\\}}(X_{j}^{\top}\Sigma_{X}X_{k})(Y_{j}^{\top}\Sigma_{Y}Y_{k})+\sum_{j\neq
i,k\notin
A\cup\\{i\\}}(X_{j}^{\top}\Sigma_{XY}Y_{k})(X_{k}^{\top}\Sigma_{XY}Y_{j})$
$\displaystyle\quad\quad\quad+\sum_{j\neq i,k\notin
A\cup\\{i\\}}\big{[}X_{j}^{\top}(X_{i}Y_{i}^{\top}-\Sigma_{XY})Y_{j}\big{]}\big{[}X_{k}^{\top}(X_{i}Y_{i}^{\top}-\Sigma_{XY})Y_{k}\big{]}$
$\displaystyle\quad\quad\quad+|A|\cdot\sum_{j\neq
i}X_{j}^{\top}\Sigma_{X}\Sigma_{XY}\Sigma_{Y}Y_{j}+|A|\cdot\sum_{j\neq
i}X_{j}^{\top}\Sigma_{XY}\Sigma_{YX}\Sigma_{XY}Y_{j}$
$\displaystyle\quad\quad\quad+|A|\cdot(X_{i}^{\top}\Sigma_{XY}Y_{i}-\lVert\Sigma_{XY}\rVert_{F}^{2})\cdot\sum_{j\neq
i}X_{j}^{\top}(X_{i}Y_{i}^{\top}-\Sigma_{XY})Y_{j}$ $\displaystyle\equiv
4^{-1}\cdot\sum_{\ell=1}^{6}T_{\ell}(i,A).$

By definition, we have

$\displaystyle T_{1}$
$\displaystyle\equiv\frac{1}{2}\sum_{A\subsetneq\\{1,\ldots,n\\}}\sum_{i\notin
A}\frac{T_{1}(i,A)}{\binom{n}{\lvert A\rvert}(n-\lvert A\rvert)}$
$\displaystyle=2\sum_{A\subsetneq\\{1,\ldots,n\\}}\sum_{i\notin A}\sum_{j\neq
i,k\notin
A\cup\\{i\\}}\frac{(X_{j}^{\top}\Sigma_{X}X_{k})(Y_{j}^{\top}\Sigma_{Y}Y_{k})}{\binom{n}{\lvert
A\rvert}(n-\lvert A\rvert)}$ $\displaystyle=2\sum_{\begin{subarray}{c}1\leq
i\leq n,\\\ j\neq i,k\neq
i\end{subarray}}(X_{j}^{\top}\Sigma_{X}X_{k})(Y_{j}^{\top}\Sigma_{Y}Y_{k})\cdot\bigg{[}\sum_{A\cap\\{i,k\\}=\emptyset}\frac{1}{\binom{n}{\lvert
A\rvert}(n-\lvert A\rvert)}\bigg{]}$
$\displaystyle\stackrel{{\scriptstyle(\ast)}}{{=}}\sum_{\begin{subarray}{c}1\leq
i\leq n,\\\ j\neq i,k\neq
i\end{subarray}}(X_{j}^{\top}\Sigma_{X}X_{k})(Y_{j}^{\top}\Sigma_{Y}Y_{k})=(n-2)\sum_{j,k}(X_{j}^{\top}\Sigma_{X}X_{k})(Y_{j}^{\top}\Sigma_{Y}Y_{k}).$

Here in ($\ast$) we used

$\displaystyle\sum_{A\cap\\{i,k\\}=\emptyset}\frac{1}{\binom{n}{\lvert
A\rvert}(n-\lvert A\rvert)}$
$\displaystyle=\sum_{a=0}^{n-2}\sum_{A\cap\\{i,k\\}=\emptyset,\lvert
A\rvert=a}\frac{1}{\binom{n}{a}(n-a)}$
$\displaystyle=\sum_{a=0}^{n-2}\frac{\binom{n-2}{a}}{\binom{n}{a}(n-a)}=\sum_{a=0}^{n-2}\frac{n-a-1}{n(n-1)}=\frac{1}{2}.$
(D.2)

With completely analogous definitions and calculations, we have

$\displaystyle T_{2}$
$\displaystyle=(n-2)\sum_{j,k}(X_{j}^{\top}\Sigma_{XY}Y_{k})(X_{k}^{\top}\Sigma_{XY}Y_{j}),$
$\displaystyle T_{3}$ $\displaystyle=\sum_{1\leq i\leq n}\bigg{[}\sum_{j\neq
i}X_{j}^{\top}(X_{i}Y_{i}^{\top}-\Sigma_{XY})Y_{j}\bigg{]}^{2}.$

Next, we have

$\displaystyle T_{4}$
$\displaystyle\equiv\frac{1}{2}\sum_{A\subsetneq\\{1,\ldots,n\\}}\sum_{i\notin
A}\frac{T_{4}(i,A)}{\binom{n}{\lvert A\rvert}(n-\lvert A\rvert)}$
$\displaystyle=2\sum_{A\subsetneq\\{1,\ldots,n\\}}\sum_{i\notin A}\sum_{j\neq
i}\frac{|A|\cdot(X_{j}^{\top}\Sigma_{X}\Sigma_{XY}\Sigma_{Y}Y_{j})}{\binom{n}{\lvert
A\rvert}(n-\lvert A\rvert)}$ $\displaystyle=2\sum_{1\leq i\leq n,j\neq
i}(X_{j}^{\top}\Sigma_{X}\Sigma_{XY}\Sigma_{Y}Y_{j})\cdot\bigg{[}\sum_{A:i\notin
A}\frac{|A|}{\binom{n}{\lvert A\rvert}(n-\lvert A\rvert)}\bigg{]}$
$\displaystyle\stackrel{{\scriptstyle(\ast\ast)}}{{=}}(n-1)\cdot\sum_{1\leq
i\leq n,j\neq
i}X_{j}^{\top}\Sigma_{X}\Sigma_{XY}\Sigma_{Y}Y_{j}=(n-1)^{2}\cdot\sum_{j=1}^{n}X_{j}^{\top}\Sigma_{X}\Sigma_{XY}\Sigma_{Y}Y_{j}.$

Here in $(**)$ we used

$\displaystyle\sum_{A:i\notin A}\frac{|A|}{\binom{n}{\lvert A\rvert}(n-\lvert
A\rvert)}$ $\displaystyle=\sum_{a=0}^{n-1}\sum_{A:i\notin A,\lvert
A\rvert=a}\frac{a}{\binom{n}{a}(n-a)}=\sum_{a=0}^{n-1}\frac{a\binom{n-1}{a}}{\binom{n}{a}(n-a)}=\sum_{a=0}^{n-1}\frac{a}{n}=\frac{n-1}{2}.$

With completely analogous definitions and calculations, we have

$\displaystyle T_{5}$
$\displaystyle=(n-1)^{2}\cdot\sum_{j=1}^{n}X_{j}^{\top}\Sigma_{XY}\Sigma_{YX}\Sigma_{XY}Y_{j},$
$\displaystyle T_{6}$ $\displaystyle=(n-1)\cdot\sum_{1\leq i\leq n,j\neq
i}(X_{i}^{\top}\Sigma_{XY}Y_{i}-\lVert\Sigma_{XY}\rVert_{F}^{2})\cdot\big{[}X_{j}^{\top}(X_{i}Y_{i}^{\top}-\Sigma_{XY})Y_{j}\big{]}.$

Putting together the pieces, we have
$\mathbb{E}(T_{\psi_{1}}|\bm{X},\bm{Y})=\sum_{i=1}^{6}T_{i}$. The proof is now
complete by invoking Lemma D.1 that gives bounds for the variances of
$T_{i}$’s. ∎

######  Lemma D.1.

Recall the terms $T_{1}$-$T_{6}$ defined in the proof of Proposition 10.4-(1)
above. The following hold.

  1. (1)

$\operatorname{Var}(T_{1})\lesssim_{M}n^{3}\cdot(n\vee\tau_{X}^{2}\vee\tau_{Y}^{2})\cdot(\lVert\Sigma_{X}\rVert_{F}^{2}\lVert\Sigma_{Y}\rVert_{F}^{2}+n\lVert\Sigma_{XY}\rVert_{F}^{2})$.

  2. (2)

$\operatorname{Var}(T_{2})\lesssim_{M}n^{3}\cdot\lVert\Sigma_{XY}\rVert_{F}^{6}+n^{5}\cdot\lVert\Sigma_{XY}\rVert_{F}^{2}$.

  3. (3)

$\operatorname{Var}(T_{3})\lesssim_{M}n^{3}\cdot\lVert\Sigma_{X}\rVert_{F}^{4}\lVert\Sigma_{Y}\rVert_{F}^{4}+n^{4}\cdot(1\vee\lVert\Sigma_{XY}\rVert_{F}^{2})\lVert\Sigma_{X}\rVert_{F}^{2}\lVert\Sigma_{Y}\rVert_{F}^{2}+n^{5}\cdot\lVert\Sigma_{XY}\rVert_{F}^{4}$.

  4. (4)

$\operatorname{Var}(T_{4})\vee\operatorname{Var}(T_{5})\lesssim_{M}n^{5}\cdot\lVert\Sigma_{XY}\rVert_{F}^{2}$.

  5. (5)

$\operatorname{Var}(T_{6})\lesssim_{M}n^{4}\cdot\lVert\Sigma_{X}\rVert_{F}^{2}\lVert\Sigma_{Y}\rVert_{F}^{2}\lVert\Sigma_{XY}\rVert_{F}^{2}$.

Consequently,

$\displaystyle\sum_{i=1}^{6}\operatorname{Var}(T_{i})$
$\displaystyle\lesssim_{M}n^{3}\cdot\lVert\Sigma_{X}\rVert_{F}^{4}\lVert\Sigma_{Y}\rVert_{F}^{4}+n^{4}\cdot(1\vee\lVert\Sigma_{XY}\rVert_{F}^{2})\lVert\Sigma_{X}\rVert_{F}^{2}\lVert\Sigma_{Y}\rVert_{F}^{2}$
$\displaystyle\quad\quad\quad+n^{5}\cdot(1\vee\lVert\Sigma_{XY}\rVert_{F}^{2})\lVert\Sigma_{XY}\rVert_{F}^{2}.$

###### Proof of Lemma D.1.

(Variance of $T_{1}$) Note that

$\displaystyle T_{1}$
$\displaystyle=(n-2)\cdot\sum_{k,\ell}(X_{k}^{\top}\Sigma_{X}X_{\ell})(Y_{k}^{\top}\Sigma_{Y}Y_{\ell})=(n-2)\cdot\sum_{k,\ell}(Z_{k}^{\top}G_{[11]}Z_{\ell})(Z_{k}^{\top}G_{[22]}Z_{\ell}).$

Hence for any $i\in[n]$ and $j\in[p+q]$, we have

$\displaystyle\frac{\partial T_{1}}{\partial Z_{ij}}$
$\displaystyle=2(n-2)\cdot\sum_{k=1}^{n}\Big{[}(e_{j}^{\top}G_{[11]}Z_{k})(Z_{i}^{\top}G_{[22]}Z_{k})+(Z_{i}^{\top}G_{[11]}Z_{k})(Z_{k}^{\top}G_{[22]}e_{j})\Big{]}$
$\displaystyle\equiv
2(n-2)\cdot\big{[}(T_{11})_{(ij)}+(T_{12})_{(ij)}\big{]}.$

By direct calculation, we have

$\displaystyle\mathbb{E}\lVert T_{11}\rVert_{F}^{2}$
$\displaystyle=\sum_{i,j}\mathbb{E}\bigg{[}e_{j}^{\top}G_{[11]}\Big{(}\sum_{k=1}^{n}Z_{k}Z_{k}^{\top}\Big{)}G_{[22]}Z_{i}Z_{i}^{\top}G_{[22]}\Big{(}\sum_{k=1}^{n}Z_{k}Z_{k}^{\top}\Big{)}G_{[11]}e_{j}\bigg{]}$
$\displaystyle=n\cdot\sum_{k_{1},k_{2}=1}^{n}\mathbb{E}\Big{[}(Z_{1}^{\top}G_{[22]}Z_{k_{1}})(Z_{1}^{\top}G_{[22]}Z_{k_{2}})(Z_{k_{1}}^{\top}G_{[11]}^{2}Z_{k_{2}})\Big{]}$
$\displaystyle=n\cdot\mathbb{E}\bigg{[}1\cdot(Z_{1}^{\top}G_{[22]}Z_{1})(Z_{1}^{\top}G_{[22]}Z_{1})(Z_{1}^{\top}G_{[11]}^{2}Z_{1})$
$\displaystyle\qquad\qquad+2(n-1)\cdot(Z_{1}^{\top}G_{[22]}Z_{1})(Z_{1}^{\top}G_{[22]}Z_{2})(Z_{1}^{\top}G_{[11]}^{2}Z_{2})$
$\displaystyle\qquad\qquad+(n-1)\cdot(Z_{1}^{\top}G_{[22]}Z_{2})(Z_{1}^{\top}G_{[22]}Z_{2})(Z_{2}^{\top}G_{[11]}^{2}Z_{2})$
$\displaystyle\qquad\qquad+(n-1)(n-2)\cdot(Z_{1}^{\top}G_{[22]}Z_{2})(Z_{1}^{\top}G_{[22]}Z_{3})(Z_{2}^{\top}G_{[11]}^{2}Z_{3})\bigg{]}$
$\displaystyle\lesssim
n\cdot\bigg{[}1\cdot\lVert\Sigma_{Y}\rVert_{F}^{4}\lVert\Sigma_{X}^{2}\rVert_{F}^{2}$
$\displaystyle\qquad\qquad+n\cdot\big{[}\operatorname{tr}(\Sigma_{XY}\Sigma_{Y}^{3}\Sigma_{YX}\Sigma_{X}^{3})+\lVert\Sigma_{Y}\rVert_{F}^{2}\cdot\operatorname{tr}(\Sigma_{XY}\Sigma_{Y}\Sigma_{YX}\Sigma_{X}^{3})\big{]}$
$\displaystyle\qquad\qquad+n\cdot\lVert\Sigma_{X}^{2}\rVert_{F}^{2}\lVert\Sigma_{Y}\rVert_{F}^{2}+n^{2}\cdot\operatorname{tr}(\Sigma_{XY}\Sigma_{Y}^{3}\Sigma_{YX}\Sigma_{X}^{3})\bigg{]}$
$\displaystyle\asymp_{M}n\cdot\Big{[}\tau_{Y}^{4}\tau_{X}^{2}+n\cdot\tau_{Y}^{2}\lVert\Sigma_{XY}\rVert_{F}^{2}+n\tau_{X}^{2}\tau_{Y}^{2}+n^{2}\lVert\Sigma_{XY}\rVert_{F}^{2}\Big{]}$
$\displaystyle\asymp
n\cdot(n\vee\tau_{Y}^{2})\cdot(\tau_{X}^{2}\tau_{Y}^{2}+n\lVert\Sigma_{XY}\rVert_{F}^{2}).$

A similar calculation for $T_{12}$ yields that

$\displaystyle\mathbb{E}\lVert
T_{11}\rVert_{F}^{2}\lesssim_{M}n\cdot(n\vee\tau_{X}^{2})\cdot(\tau_{X}^{2}\tau_{Y}^{2}+n\lVert\Sigma_{XY}\rVert_{F}^{2}),$

so we conclude by the Gaussian-Poincaré inequality that

$\displaystyle\operatorname{Var}(T_{1})\lesssim_{M}n^{3}\cdot(n\vee\tau_{X}^{2}\vee\tau_{Y}^{2})\cdot(\tau_{X}^{2}\tau_{Y}^{2}+n\lVert\Sigma_{XY}\rVert_{F}^{2}).$

(Variance of $T_{2}$) Note that

$\displaystyle
T_{2}=(n-2)\cdot\sum_{k,\ell}(Z_{k}^{\top}G_{[12]}Z_{\ell})(Z_{k}^{\top}G_{[21]}Z_{\ell}).$

Hence for any $i\in[n]$ and $j\in[p+q]$,

$\displaystyle\frac{\partial T_{2}}{\partial Z_{ij}}$
$\displaystyle=2(n-2)\cdot\sum_{k}\Big{[}(e_{j}^{\top}G_{[12]}Z_{k})(Z_{i}^{\top}G_{[21]}Z_{k})+(Z_{k}^{\top}G_{[12]}e_{j})(Z_{k}^{\top}G_{[21]}Z_{i})\Big{]}$
$\displaystyle\equiv
2(n-2)\cdot\big{[}(T_{21})_{(ij)}+(T_{22})_{(ij)}\big{]}.$

By direct calculation, we have

$\displaystyle\mathbb{E}\lVert T_{21}\rVert_{F}^{2}$
$\displaystyle=\sum_{i,j}\mathbb{E}\Big{[}Z_{i}^{\top}G_{[21]}\Big{(}\sum_{k}Z_{k}Z_{k}^{\top}\Big{)}G_{[21]}e_{j}e_{j}^{\top}G_{[12]}\Big{(}\sum_{k}Z_{k}Z_{k}^{\top}\Big{)}G_{[12]}Z_{i}\Big{]}$
$\displaystyle=n\cdot\sum_{k_{1},k_{2}}\mathbb{E}\Big{[}(Z_{1}^{\top}G_{[21]}Z_{k_{1}})(Z_{1}^{\top}G_{[21]}Z_{k_{2}})(Z_{k_{1}}^{\top}G_{[21]}G_{[12]}Z_{k_{2}})\Big{]}$
$\displaystyle=n\cdot\mathbb{E}\bigg{[}1\cdot(Z_{1}^{\top}G_{[21]}Z_{1})(Z_{1}^{\top}G_{[21]}Z_{1})(Z_{1}^{\top}G_{[21]}G_{[12]}Z_{1})$
$\displaystyle\quad\quad+2(n-1)\cdot(Z_{1}^{\top}G_{[21]}Z_{1})(Z_{1}^{\top}G_{[21]}Z_{2})(Z_{1}^{\top}G_{[21]}G_{[12]}Z_{2})$
$\displaystyle\quad\quad+(n-1)\cdot(Z_{1}^{\top}G_{[21]}Z_{2})(Z_{1}^{\top}G_{[21]}Z_{2})(Z_{2}^{\top}G_{[21]}G_{[12]}Z_{2})$
$\displaystyle\quad\quad+(n-1)(n-2)\cdot(Z_{1}^{\top}G_{[21]}Z_{2})(Z_{1}^{\top}G_{[21]}Z_{3})(Z_{2}^{\top}G_{[21]}G_{[12]}Z_{3})\bigg{]}$
$\displaystyle\lesssim_{M}n\cdot\Big{[}\lVert\Sigma_{XY}\rVert_{F}^{6}+n\cdot\lVert\Sigma_{XY}\rVert_{F}^{4}+n^{2}\cdot\lVert\Sigma_{XY}\rVert_{F}^{2}\Big{]}$
$\displaystyle\asymp
n\cdot\big{(}\lVert\Sigma_{XY}\rVert_{F}^{6}+n^{2}\lVert\Sigma_{XY}\rVert_{F}^{2}\big{)}.$

A similar bound holds for $T_{22}$.

(Variance of $T_{3}$) Note that

$\displaystyle T_{3}$ $\displaystyle=\sum_{k=1}^{n}\Big{[}\sum_{\ell\neq
k}X_{\ell}^{\top}(X_{k}Y_{k}^{\top}-\Sigma_{XY})Y_{\ell}\Big{]}^{2}=\sum_{k=1}^{n}\Big{[}\sum_{\ell\neq
k}Z_{\ell}^{\top}\Big{(}H_{[11]}Z_{k}Z_{k}^{\top}H_{[22]}-G_{[12]}\Big{)}Z_{\ell}\Big{]}^{2}.$

Hence for any $i\in[n]$ and $j\in[p+q]$, we have

$\displaystyle 2^{-1}\frac{\partial T_{3}}{\partial Z_{ij}}$
$\displaystyle=\sum_{k=1}^{n}\Big{[}\sum_{\ell\neq
k}Z_{\ell}^{\top}\Big{(}H_{[11]}Z_{k}Z_{k}^{\top}H_{[22]}-G_{[12]}\Big{)}Z_{\ell}\Big{]}$
$\displaystyle\qquad\qquad\times\sum_{\ell\neq
k}\Big{[}\delta_{i\ell}e_{j}^{\top}(H_{[11]}Z_{k}Z_{k}^{\top}H_{[22]}-G_{[12]})Z_{\ell}$
$\displaystyle\qquad\qquad\qquad\qquad+\delta_{i\ell}Z_{\ell}^{\top}(H_{[11]}Z_{k}Z_{k}^{\top}H_{[22]}-G_{[12]})e_{j}$
$\displaystyle\qquad\qquad\qquad\qquad+\delta_{ik}\cdot
Z_{\ell}^{\top}(H_{[11]}e_{j}Z_{k}^{\top}H_{[22]}+H_{[11]}Z_{k}e_{j}^{\top}H_{[22]})Z_{\ell}\Big{]}$
$\displaystyle=\Big{[}\sum_{\ell\neq
i}Z_{\ell}^{\top}\Big{(}H_{[11]}Z_{i}Z_{i}^{\top}H_{[22]}-G_{[12]}\Big{)}Z_{\ell}\Big{]}\cdot\Big{[}\sum_{\ell\neq
i}(Z_{\ell}^{\top}H_{[11]}e_{j})(Z_{i}^{\top}H_{[22]}Z_{\ell})\Big{]}$
$\displaystyle+\Big{[}\sum_{\ell\neq
i}Z_{\ell}^{\top}\Big{(}H_{[11]}Z_{i}Z_{i}^{\top}H_{[22]}-G_{[12]}\Big{)}Z_{\ell}\Big{]}\cdot\Big{[}\sum_{\ell\neq
i}(Z_{\ell}^{\top}H_{[11]}Z_{i})(e_{j}^{\top}H_{[22]}Z_{\ell})\Big{]}$
$\displaystyle+\sum_{k\neq i}\Big{[}\sum_{\ell\neq
k}Z_{\ell}^{\top}\Big{(}H_{[11]}Z_{k}Z_{k}^{\top}H_{[22]}-G_{[12]}\Big{)}Z_{\ell}\Big{]}\cdot\Big{[}e_{j}^{\top}\Big{(}H_{[11]}Z_{k}Z_{k}^{\top}H_{[22]}-G_{[12]}\Big{)}Z_{i}\Big{]}$
$\displaystyle+\sum_{k\neq i}\Big{[}\sum_{\ell\neq
k}Z_{\ell}^{\top}\Big{(}H_{[11]}Z_{k}Z_{k}^{\top}H_{[22]}-G_{[12]}\Big{)}Z_{\ell}\Big{]}\cdot\Big{[}Z_{i}^{\top}\Big{(}H_{[11]}Z_{k}Z_{k}^{\top}H_{[22]}-G_{[12]}\Big{)}e_{j}\Big{]}$
$\displaystyle\equiv(T_{31})_{(ij)}+(T_{32})_{(ij)}+(T_{33})_{(ij)}+(T_{34})_{(ij)}.$

For $T_{31}$, we have

$\displaystyle\mathbb{E}\lVert
T_{31}\rVert_{F}^{2}=n\cdot\mathbb{E}\Big{[}\sum_{\ell\neq
1}Z_{\ell}^{\top}\Big{(}H_{[11]}Z_{1}Z_{1}^{\top}H_{[22]}-G_{[12]}\Big{)}Z_{\ell}\Big{]}^{2}\cdot\bigg{\lVert}\sum_{\ell\neq
1}(Z_{1}^{\top}H_{[22]}Z_{\ell})H_{[11]}Z_{\ell}\bigg{\rVert}^{2}$
$\displaystyle\leq n\cdot\mathbb{E}^{1/2}\Big{[}\sum_{\ell\neq
1}Z_{\ell}^{\top}\Big{(}H_{[11]}Z_{1}Z_{1}^{\top}H_{[22]}-G_{[12]}\Big{)}Z_{\ell}\Big{]}^{4}\cdot\mathbb{E}^{1/2}\bigg{\lVert}\sum_{\ell\neq
1}(Z_{1}^{\top}H_{[22]}Z_{\ell})H_{[11]}Z_{\ell}\bigg{\rVert}^{4}.$

The two terms can be bounded as follows:

  * •

Let $U_{1}\equiv H_{[11]}Z_{1}Z_{1}^{\top}H_{[22]}-G_{[12]}$. By first
conditioning on $Z_{1}$, we have

$\displaystyle\mathbb{E}\Big{[}\sum_{\ell\neq
1}Z_{\ell}^{\top}U_{1}Z_{\ell}\Big{]}^{4}$
$\displaystyle\lesssim\mathbb{E}\big{[}n\cdot\operatorname{tr}(U_{1})+n^{1/2}\cdot\lVert
U_{1}\rVert_{F}\big{]}^{4}$
$\displaystyle\lesssim_{M}n^{4}\cdot\lVert\Sigma_{XY}\rVert_{F}^{4}+n^{2}\cdot\lVert\Sigma_{X}\rVert_{F}^{4}\lVert\Sigma_{Y}\rVert_{F}^{4},$
(D.3)

where the last inequality follows from Lemma D.2-(4).

  * •

Let $M_{-1}\equiv\sum_{k\neq 1}Z_{k}Z_{k}^{\top}$. Then by first taking
expectation with respect to $Z_{1}$, we have

$\displaystyle\mathbb{E}\bigg{\lVert}\sum_{\ell\neq
1}(Z_{1}^{\top}H_{[22]}Z_{\ell})H_{[11]}Z_{\ell}\bigg{\rVert}^{4}\asymp\mathbb{E}\operatorname{tr}^{2}\Big{(}H_{[22]}M_{-1}H_{[11]}^{2}M_{-1}H_{[22]}\Big{)}$
$\displaystyle=\mathbb{E}\bigg{[}\sum_{k_{1},k_{2}\neq
1}(Z_{k_{1}}^{\top}H_{[11]}^{2}Z_{k_{2}})(Z_{k_{1}}^{\top}H_{[22]}^{2}Z_{k_{2}})\bigg{]}^{2}$
$\displaystyle=\mathbb{E}\sum_{k_{1},k_{2},k_{3},k_{4}\neq
1}(Z_{k_{1}}^{\top}H_{[11]}^{2}Z_{k_{2}})(Z_{k_{1}}^{\top}H_{[22]}^{2}Z_{k_{2}})(Z_{k_{3}}^{\top}H_{[11]}^{2}Z_{k_{4}})(Z_{k_{3}}^{\top}H_{[22]}^{2}Z_{k_{4}}).$

    1. (i)

When $k_{1}$-$k_{4}$ take one distinct value, there are up to $n$ such terms,
and each term has contribution

$\displaystyle\mathbb{E}(Z_{1}^{\top}H_{[11]}^{2}Z_{1})^{2}(Z_{1}^{\top}H_{[22]}^{2}Z_{1})^{2}\lesssim\mathbb{E}^{1/2}(Z_{1}^{\top}H_{[11]}^{2}Z_{1})^{4}\cdot\mathbb{E}^{1/2}(Z_{1}^{\top}H_{[22]}^{2}Z_{1})^{4}$
$\displaystyle\lesssim\lVert H_{[11]}\rVert_{F}^{4}\lVert
H_{[22]}\rVert_{F}^{4}=\lVert\Sigma_{X}\rVert_{F}^{4}\lVert\Sigma_{Y}\rVert_{F}^{4}.$

    2. (ii)

When $k_{1}$-$k_{4}$ take two distinct values, there are up to $n^{2}$ such
terms, and each term has contribution

$\displaystyle\mathbb{E}\Big{[}(Z_{1}^{\top}H_{[11]}^{2}Z_{1})(Z_{1}^{\top}H_{[22]}^{2}Z_{1})(Z_{1}^{\top}H_{[11]}^{2}Z_{2})(Z_{1}^{\top}H_{[22]}^{2}Z_{2})\Big{]}$
$\displaystyle\quad=\mathbb{E}\Big{[}(Z_{1}^{\top}H_{[11]}^{2}Z_{1})(Z_{1}^{\top}H_{[22]}^{2}Z_{1})(Z_{1}^{\top}H_{[11]}^{2}H_{[22]}^{2}Z_{1})\Big{]}$
$\displaystyle\leq\mathbb{E}^{1/4}(Z_{1}^{\top}H_{[11]}^{2}Z_{1})^{4}\cdot\mathbb{E}^{1/4}(Z_{1}^{\top}H_{[22]}^{2}Z_{1})^{4}\cdot\mathbb{E}^{1/2}(Z_{1}^{\top}H_{[11]}^{2}H_{[22]}^{2}Z_{1})^{2}$
$\displaystyle\lesssim\lVert H_{[11]}\rVert_{F}^{2}\cdot\lVert
H_{[22]}\rVert_{F}^{2}\cdot\big{[}\operatorname{tr}(H_{[11]}^{2}H_{[22]}^{2})+\lVert
H_{[11]}^{2}H_{[22]}^{2}\rVert_{F}\big{]}$
$\displaystyle\lesssim_{M}\lVert\Sigma_{X}\rVert_{F}^{2}\cdot\lVert\Sigma_{Y}\rVert_{F}^{2}\cdot(\lVert\Sigma_{XY}\rVert_{F}^{2}+\lVert\Sigma_{XY}\rVert_{F}).$

    3. (iii)

When $k_{1}$-$k_{4}$ take three distinct values in the form of
$(k_{1}=k_{2})\neq k_{3}\neq k_{4}$, there are up $n^{3}$ such terms, and each
term has contribution

$\displaystyle\mathbb{E}\Big{[}(Z_{1}^{\top}H_{[11]}^{2}Z_{1})(Z_{1}^{\top}H_{[22]}^{2}Z_{1})(Z_{2}^{\top}H_{[11]}^{2}Z_{3})(Z_{3}^{\top}H_{[22]}^{2}Z_{2})\Big{]}$
$\displaystyle=\mathbb{E}\Big{[}(Z_{1}^{\top}H_{[11]}^{2}Z_{1})(Z_{1}^{\top}H_{[22]}^{2}Z_{1})\Big{]}\cdot\operatorname{tr}\big{(}H_{[11]}^{2}H_{[22]}^{2}\big{)}$
$\displaystyle\asymp\lVert H_{[11]}\rVert_{F}^{2}\lVert
H_{[22]}\rVert_{F}^{2}\operatorname{tr}\big{(}H_{[11]}^{2}H_{[22]}^{2}\big{)}\lesssim_{M}\lVert\Sigma_{X}\rVert_{F}^{2}\lVert\Sigma_{Y}\rVert_{F}^{2}\lVert\Sigma_{XY}\rVert_{F}^{2}.$

    4. (iv)

When $k_{1}$-$k_{4}$ take three distinct values in the form of
$(k_{1}=k_{3})\neq k_{2}\neq k_{4}$, there are up to $n^{3}$ such terms, and
each term has contribution

$\displaystyle\mathbb{E}\Big{[}(Z_{1}^{\top}H_{[11]}^{2}Z_{2})(Z_{1}^{\top}H_{[22]}^{2}Z_{2})(Z_{1}^{\top}H_{[11]}^{2}Z_{3})(Z_{1}^{\top}H_{[22]}^{2}Z_{3})\Big{]}$
$\displaystyle=\mathbb{E}\big{(}Z_{1}^{\top}H_{[11]}^{2}H_{[22]}^{2}Z_{1}\big{)}^{2}\asymp_{M}\lVert\Sigma_{XY}\rVert_{F}^{2}+\lVert\Sigma_{XY}\rVert_{F}^{4}.$

    5. (v)

When $k_{1}$-$k_{4}$ take four distinct values, there are up to $n^{4}$ such
terms, and each term has contribution

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

Putting together estimates (i)-(v) yields that

$\displaystyle\mathbb{E}\bigg{\lVert}\sum_{\ell\neq
1}(Z_{1}^{\top}H_{[22]}Z_{\ell})H_{[11]}Z_{\ell}\bigg{\rVert}^{4}$
$\displaystyle\lesssim_{M}n\cdot\tau_{X}^{4}\tau_{Y}^{4}+n^{2}\cdot\tau_{X}^{2}\tau_{Y}^{2}\lVert\Sigma_{XY}\rVert_{F}+n^{3}\cdot\tau_{X}^{2}\tau_{Y}^{2}\lVert\Sigma_{XY}\rVert_{F}^{2}+n^{4}\cdot\lVert\Sigma_{XY}\rVert_{F}^{4}$
$\displaystyle\lesssim
n^{2}\cdot\tau_{X}^{4}\tau_{Y}^{4}+n^{4}\cdot\lVert\Sigma_{XY}\rVert_{F}^{4}.$
(D.4)

The last inequality follows since (1) when the second term dominates the third
term $n\lVert\Sigma_{XY}\rVert_{F}\lesssim 1$, the overall bound is dominated
by the first term; (2) when the third term dominates the second term, the
overall bound reduces to the sum of the first, third and fourth terms that can
be written as a complete square.

Combining (• ‣ D.2.1) and (• ‣ D.2.1) yields that

$\displaystyle T_{31}$
$\displaystyle\lesssim_{M}n^{3}\cdot(n\lVert\Sigma_{XY}\rVert_{F}^{2}+\lVert\Sigma_{X}\rVert_{F}^{2}\lVert\Sigma_{Y}\rVert_{F}^{2})^{2}.$
(D.5)

A similar bound holds for $T_{32}$.

Next we bound $T_{33}$. For any $k\in[n]$, let $U_{k}\equiv
H_{[11]}Z_{k}Z_{k}^{\top}H_{[22]}-G_{[12]}$ be a centered random matrix. Then
by definition, we have

$\displaystyle\mathbb{E}\lVert T_{33}\rVert_{F}^{2}$
$\displaystyle=n\cdot\sum_{k_{1},k_{2}\neq
1}\mathbb{E}\Big{[}\Big{(}\sum_{\ell\neq
k_{1}}Z_{\ell}^{\top}U_{k_{1}}Z_{\ell}\Big{)}\cdot\Big{(}\sum_{\ell\neq
k_{2}}Z_{\ell}^{\top}U_{k_{2}}Z_{\ell}\Big{)}\cdot(Z_{1}^{\top}U_{k_{1}}^{\top}U_{k_{2}}Z_{1})\Big{]}$
$\displaystyle=n\cdot\sum_{\ell_{1},\ell_{2}=1}\sum_{k_{1}\notin\\{\ell_{1},1\\},k_{2}\notin\\{\ell_{2},1\\}}\mathbb{E}\big{(}Z_{\ell_{1}}^{\top}U_{k_{1}}Z_{\ell_{1}}\big{)}(Z_{\ell_{2}}^{\top}U_{k_{2}}Z_{\ell_{2}})(Z_{1}^{\top}U_{k_{1}}^{\top}U_{k_{2}}Z_{1}).$

We now divide the analysis of $T_{33}$ into the following four cases:
$\ell_{1}=\ell_{2}=1$ (Case 1), $\ell_{1}=1$, $\ell_{2}\neq 1$ (Case 2),
$(\ell_{1}=\ell_{2})\neq 1$ (Case 3), $\ell_{1}\neq\ell_{2}\neq 1$ (Case 4).

  * •

When $\ell_{1}=\ell_{2}=1$,

$\displaystyle S_{1}$ $\displaystyle\equiv\sum_{k_{1}\neq 1,k_{2}\neq
1}\mathbb{E}\big{(}Z_{1}^{\top}U_{k_{1}}Z_{1}\big{)}(Z_{1}^{\top}U_{k_{2}}Z_{1})(Z_{1}^{\top}U_{k_{1}}^{\top}U_{k_{2}}Z_{1})$
$\displaystyle\asymp
n\cdot\mathbb{E}(Z_{1}^{\top}U_{2}Z_{1})^{2}\cdot(Z_{1}^{\top}U_{2}^{\top}U_{2}Z_{1})+n^{2}\cdot\mathbb{E}\big{(}Z_{1}^{\top}U_{2}Z_{1}\big{)}(Z_{1}^{\top}U_{3}Z_{1})(Z_{1}^{\top}U_{2}^{\top}U_{3}Z_{1}).$

    1. (i)

By Lemma D.2,

$\displaystyle\mathbb{E}(Z_{1}^{\top}U_{2}Z_{1})^{2}\cdot(Z_{1}^{\top}U_{2}^{\top}U_{2}Z_{1})\leq\mathbb{E}^{1/2}(Z_{1}^{\top}U_{2}Z_{1})^{4}\cdot\mathbb{E}^{1/2}(Z_{1}^{\top}U_{2}^{\top}U_{2}Z_{1})^{2}$
$\displaystyle\lesssim\mathbb{E}\big{(}\operatorname{tr}(U_{2})+\lVert
U_{2}\rVert_{F}\big{)}^{2}\cdot\lVert
U_{2}\rVert_{F}^{2}\lesssim\mathbb{E}\big{[}\operatorname{tr}(U_{2})^{4}+\lVert
U_{2}\rVert_{F}^{4}\big{]}\lesssim_{M}\lVert\Sigma_{X}\rVert_{F}^{4}\lVert\Sigma_{Y}\rVert_{F}^{4}.$

    2. (ii)

We have

$\displaystyle\mathbb{E}\big{(}Z_{1}^{\top}U_{2}Z_{1}\big{)}(Z_{1}^{\top}U_{3}Z_{1})(Z_{1}^{\top}U_{2}^{\top}U_{3}Z_{1})$
$\displaystyle\leq\mathbb{E}^{1/4}\big{(}Z_{1}^{\top}U_{2}Z_{1}\big{)}^{4}\cdot\mathbb{E}^{1/4}(Z_{1}^{\top}U_{3}Z_{1})\cdot\mathbb{E}^{1/2}(Z_{1}^{\top}U_{2}^{\top}U_{3}Z_{1})^{2}$
$\displaystyle\lesssim\mathbb{E}\big{(}|\operatorname{tr}(U_{2})|+\lVert
U_{2}\rVert_{F}\big{)}\cdot\mathbb{E}\big{(}|\operatorname{tr}(U_{3})|+\lVert
U_{2}\rVert_{F}\big{)}\cdot\mathbb{E}\big{(}|\operatorname{tr}(U_{2}U_{3})|+\lVert
U_{2}U_{3}^{\top}\rVert_{F}\big{)}$
$\displaystyle\lesssim(\lVert\Sigma_{X}\rVert_{F}\lVert\Sigma_{Y}\rVert_{F})^{2}\cdot\mathbb{E}[\lVert
U_{2}\rVert_{F}\lVert
U_{3}\rVert_{F}]\lesssim_{M}\lVert\Sigma_{X}\rVert_{F}^{4}\lVert\Sigma_{Y}\rVert_{F}^{4}.$
(D.6)

Combining (i) and (ii) yields that in this first case,

$\displaystyle
S_{1}\lesssim_{M}n^{2}\lVert\Sigma_{X}\rVert_{F}^{4}\lVert\Sigma_{Y}\rVert_{F}^{4}.$
(D.7)

  * •

When $\ell_{1}=1$ and $\ell_{2}\neq 1$, we have (by letting $\ell_{2}=2$)

$\displaystyle S_{2}$ $\displaystyle\equiv\sum_{k_{1}\neq
1,k_{2}\notin\\{1,2\\}}\mathbb{E}(Z_{1}^{\top}U_{k_{1}}Z_{1})(Z_{2}^{\top}U_{k_{2}}Z_{2})(Z_{1}^{\top}U_{k_{1}}^{\top}U_{k_{2}}Z_{1})$
$\displaystyle=\sum_{k_{2}\notin\\{1,2\\}}\mathbb{E}(Z_{1}^{\top}U_{2}Z_{1})(Z_{2}^{\top}U_{k_{2}}Z_{2})(Z_{1}^{\top}U_{2}^{\top}U_{k_{2}}Z_{1})$
$\displaystyle\quad\quad+\sum_{k_{1},k_{2}\notin\\{1,2\\}}\mathbb{E}\big{(}Z_{1}^{\top}U_{k_{1}}Z_{1}\big{)}(Z_{2}^{\top}U_{k_{2}}Z_{2})(Z_{1}^{\top}U_{k_{1}}^{\top}U_{k_{2}}Z_{1})$
$\displaystyle\asymp
n\cdot\mathbb{E}(Z_{1}^{\top}U_{2}Z_{1})(Z_{2}^{\top}U_{3}Z_{2})(Z_{1}^{\top}U_{2}^{\top}U_{3}Z_{1})$
$\displaystyle\quad\quad\quad+n\cdot\mathbb{E}\big{(}Z_{1}^{\top}U_{3}Z_{1}\big{)}(Z_{2}^{\top}U_{3}Z_{2})(Z_{1}^{\top}U_{3}^{\top}U_{3}Z_{1})$
$\displaystyle\quad\quad\quad+n^{2}\cdot\mathbb{E}\big{(}Z_{1}^{\top}U_{3}Z_{1}\big{)}(Z_{2}^{\top}U_{4}Z_{2})(Z_{1}^{\top}U_{3}^{\top}U_{4}Z_{1}).$

    1. (i)

Using similar argument as in the previous case, we have

$\displaystyle\mathbb{E}(Z_{1}^{\top}U_{2}Z_{1})(Z_{2}^{\top}U_{3}Z_{2})(Z_{1}^{\top}U_{2}^{\top}U_{3}Z_{1})$
$\displaystyle\lesssim_{M}\lVert\Sigma_{X}\rVert_{F}^{4}\lVert\Sigma_{Y}\rVert_{F}^{4},$
$\displaystyle\mathbb{E}\big{(}Z_{1}^{\top}U_{3}Z_{1}\big{)}(Z_{2}^{\top}U_{3}Z_{2})(Z_{1}^{\top}U_{3}^{\top}U_{3}Z_{1})$
$\displaystyle\lesssim_{M}\lVert\Sigma_{X}\rVert_{F}^{4}\lVert\Sigma_{Y}\rVert_{F}^{4}.$

    2. (ii)

For the third summand, by taking expectation with respect to $Z_{2}$ and then
$Z_{1}$, we have

$\displaystyle\mathbb{E}\big{(}Z_{1}^{\top}U_{3}Z_{1}\big{)}(Z_{2}^{\top}U_{4}Z_{2})(Z_{1}^{\top}U_{3}^{\top}U_{4}Z_{1})=\mathbb{E}(Z_{1}^{\top}U_{3}Z_{1})(Z_{1}^{\top}U_{3}^{\top}\operatorname{tr}(U_{4})U_{4}Z_{1})$
$\displaystyle=\mathbb{E}\operatorname{tr}(U_{3}^{2}\cdot\operatorname{tr}(U_{4})U_{4}^{\top})+\mathbb{E}\operatorname{tr}(U_{3}U_{3}^{\top}\operatorname{tr}(U_{4})U_{4})+\mathbb{E}\operatorname{tr}(U_{3})\operatorname{tr}(U_{4})\operatorname{tr}(U_{3}^{\top}U_{4})$
$\displaystyle\asymp_{M}\operatorname{tr}\Big{[}\mathbb{E}(U_{3}^{2})\cdot\mathbb{E}\big{(}\operatorname{tr}(U_{4})U_{4}^{\top}\big{)}\Big{]}+\operatorname{tr}\Big{[}\mathbb{E}(U_{3}U_{3}^{\top})\cdot\mathbb{E}\big{(}\operatorname{tr}(U_{4})U_{4}\big{)}\Big{]}+\lVert\Sigma_{XY}\rVert_{F}^{2}.$

The last line follows from Lemma D.2-(6). By Lemma D.2-(1)(2)(3), we have

$\displaystyle\operatorname{tr}\Big{[}\mathbb{E}(U_{3}^{2})\cdot\mathbb{E}\big{(}\operatorname{tr}(U_{4})U_{4}^{\top}\big{)}\Big{]}=\operatorname{tr}\Big{[}\Big{(}G_{[11]}G_{[22]}+\operatorname{tr}(G_{[12]})G_{[12]}\Big{)}\Big{(}G_{[22]}G_{[11]}+G_{[21]}^{2}\Big{)}\Big{]}$
$\displaystyle=\operatorname{tr}(G_{[11]}G_{[22]}G_{[22]}G_{[11]})+\operatorname{tr}(G_{[11]}G_{[22]}G_{[21]}^{2})$
$\displaystyle\quad\quad\quad+\operatorname{tr}(G_{[12]})\operatorname{tr}(G_{[12]}G_{[22]}G_{[11]})+\operatorname{tr}(G_{[12]})\operatorname{tr}(G_{[12]}G_{[21]}^{2})$
$\displaystyle\asymp_{M}\lVert\Sigma_{XY}\rVert_{F}^{2}+\lVert\Sigma_{XY}\Sigma_{YX}\rVert_{F}^{2}+\lVert\Sigma_{XY}\rVert_{F}^{4}+\lVert\Sigma_{XY}\rVert_{F}^{2}\lVert\Sigma_{XY}\Sigma_{YX}\rVert_{F}^{2}$
$\displaystyle\lesssim\lVert\Sigma_{XY}\rVert_{F}^{2}(1\vee\lVert\Sigma_{XY}\rVert_{F}^{2}),$

and

$\displaystyle\operatorname{tr}\Big{[}\mathbb{E}(U_{3}U_{3}^{\top})\cdot\mathbb{E}\big{(}\operatorname{tr}(U_{4})U_{4}\big{)}\Big{]}=\operatorname{tr}\Big{[}\Big{(}G_{[12]}G_{[21]}+G_{[11]}\operatorname{tr}(G_{[22]})\Big{)}\Big{(}G_{[11]}G_{[22]}+G_{[12]}^{2}\Big{)}\Big{]}$
$\displaystyle=\operatorname{tr}(G_{[12]}G_{[21]}G_{[11]}G_{[22]})+\operatorname{tr}(G_{[21]}G_{[12]}^{3})$
$\displaystyle\quad\quad\quad+\operatorname{tr}(G_{[22]})\operatorname{tr}(G_{[11]}^{2}G_{[22]})+\operatorname{tr}(G_{[22]})\operatorname{tr}(G_{[11]}G_{[12]}^{2})$
$\displaystyle\asymp_{M}\lVert\Sigma_{XY}\Sigma_{YX}\rVert_{F}^{2}+\operatorname{tr}\big{[}(\Sigma_{XY}\Sigma_{YX})^{3}\big{]}+\lVert\Sigma_{Y}\rVert_{F}^{2}\lVert\Sigma_{XY}\rVert_{F}^{2}+\lVert\Sigma_{Y}\rVert_{F}^{2}\lVert\Sigma_{XY}\Sigma_{YX}\rVert_{F}^{2}$
$\displaystyle\asymp_{M}\lVert\Sigma_{Y}\rVert_{F}^{2}\lVert\Sigma_{XY}\rVert_{F}^{2}.$

Using Lemma F.5, we have

$\displaystyle\mathbb{E}\big{(}Z_{1}^{\top}U_{3}Z_{1}\big{)}(Z_{2}^{\top}U_{4}Z_{2})(Z_{1}^{\top}U_{3}U_{4}^{\top}Z_{1})$
$\displaystyle=\mathbb{E}(Z_{1}^{\top}U_{3}Z_{1})(Z_{1}^{\top}U_{3}\operatorname{tr}(U_{4})U_{4}^{\top}Z_{1})\lesssim_{M}\lVert\Sigma_{Y}\rVert_{F}^{2}\lVert\Sigma_{XY}\rVert_{F}^{2}.$

Combining (i) and (ii) yields that in this second case,

$\displaystyle S_{2}$
$\displaystyle\lesssim_{M}n\cdot\lVert\Sigma_{X}\rVert_{F}^{4}\lVert\Sigma_{Y}\rVert_{F}^{4}+n^{2}(\lVert\Sigma_{X}\rVert_{F}^{2}+\lVert\Sigma_{Y}\rVert_{F}^{2})\lVert\Sigma_{XY}\rVert_{F}^{2}.$
(D.8)

A similar estimate holds for the case $\ell_{1}\neq 1,\ell_{2}=1$.

  * •

When $(\ell_{1}=\ell_{2})\neq 1$, we have (letting $\ell_{1}=\ell_{2}=2$)

$\displaystyle S_{3}$
$\displaystyle\equiv\sum_{k_{1},k_{2}\notin\\{1,2\\}}\mathbb{E}\big{(}Z_{2}^{\top}U_{k_{1}}Z_{2}\big{)}(Z_{2}^{\top}U_{k_{2}}Z_{2})(Z_{1}^{\top}U_{k_{1}}^{\top}U_{k_{2}}Z_{1})$
$\displaystyle\asymp
n\cdot\mathbb{E}\big{(}Z_{2}^{\top}U_{3}Z_{2}\big{)}^{2}(Z_{1}^{\top}U_{3}^{\top}U_{3}Z_{1})+n^{2}\cdot\mathbb{E}\big{(}Z_{2}^{\top}U_{3}Z_{2}\big{)}(Z_{2}^{\top}U_{4}Z_{2})(Z_{1}^{\top}U_{3}^{\top}U_{4}Z_{1})$
$\displaystyle=n\cdot\mathbb{E}(Z_{2}^{\top}U_{3}Z_{2})^{2}\lVert
U_{3}\rVert_{F}^{2}+n^{2}\mathbb{E}(Z_{2}^{\top}U_{3}Z_{2})(Z_{2}^{\top}U_{4}Z_{2})\operatorname{tr}(U_{3}^{\top}U_{4})$
$\displaystyle\asymp n\cdot\big{[}\mathbb{E}\lVert
U_{3}\rVert_{F}^{4}+\mathbb{E}\operatorname{tr}^{2}(U_{3})\lVert
U_{3}\rVert_{F}^{2}\big{]}$
$\displaystyle\quad\quad\quad+n^{2}\cdot\Big{[}\mathbb{E}\operatorname{tr}^{2}(U_{3}U_{4}^{\top})+\mathbb{E}\operatorname{tr}(U_{3}U_{4})\operatorname{tr}(U_{3}U_{4}^{\top})+\mathbb{E}\operatorname{tr}(U_{3})\operatorname{tr}(U_{4})\operatorname{tr}(U_{3}^{\top}U_{4})\Big{]}.$

By Lemma D.2 and Lemma F.5,

$\displaystyle\mathbb{E}\lVert
U_{3}\rVert_{F}^{4}+\mathbb{E}\operatorname{tr}^{2}(U_{3})\lVert
U_{3}\rVert_{F}^{2}$
$\displaystyle\lesssim_{M}\lVert\Sigma_{X}\rVert_{F}^{4}\lVert\Sigma_{Y}\rVert_{F}^{4}+\lVert\Sigma_{XY}\rVert_{F}^{2}\lVert\Sigma_{X}\rVert_{F}^{2}\lVert\Sigma_{Y}\rVert_{F}^{2}$
$\displaystyle\asymp_{M}\lVert\Sigma_{X}\rVert_{F}^{4}\lVert\Sigma_{Y}\rVert_{F}^{4},$

and

$\displaystyle\mathbb{E}\operatorname{tr}^{2}(U_{3}U_{4}^{\top})+\mathbb{E}\operatorname{tr}(U_{3}U_{4})\operatorname{tr}(U_{3}U_{4}^{\top})+\mathbb{E}\operatorname{tr}(U_{3})\operatorname{tr}(U_{4})\operatorname{tr}(U_{3}^{\top}U_{4})$
$\displaystyle\lesssim_{M}\lVert\Sigma_{X}\rVert_{F}^{2}\lVert\Sigma_{Y}\rVert_{F}^{2}+\lVert\Sigma_{X}\rVert_{F}\lVert\Sigma_{Y}\rVert_{F}\lVert\Sigma_{XY}\rVert_{F}^{2}+\lVert\Sigma_{XY}\rVert_{F}^{2}\asymp\lVert\Sigma_{X}\rVert_{F}^{2}\lVert\Sigma_{Y}\rVert_{F}^{2}.$

Consequently,

$\displaystyle S_{3}$
$\displaystyle\asymp_{M}n\lVert\Sigma_{X}\rVert_{F}^{4}\lVert\Sigma_{Y}\rVert_{F}^{4}+n^{2}\lVert\Sigma_{X}\rVert_{F}^{2}\lVert\Sigma_{Y}\rVert_{F}^{2}.$
(D.9)

  * •

When $\ell_{1},\ell_{2}\neq 1$ and $\ell_{1}\neq\ell_{2}$, we have (letting
$\ell_{1}=2$, $\ell_{2}=3$)

$\displaystyle S_{4}$
$\displaystyle\equiv\sum_{k_{1}\notin\\{1,2\\},k_{2}\notin\\{1,3\\}}\mathbb{E}\big{(}Z_{2}^{\top}U_{k_{1}}Z_{2}\big{)}(Z_{3}^{\top}U_{k_{2}}Z_{3})(Z_{1}^{\top}U_{k_{1}}^{\top}U_{k_{2}}Z_{1})$
$\displaystyle=\Big{[}\sum_{k_{1}=3,k_{2}=2}+\sum_{k_{1}=3,k_{2}\notin\\{1,2,3\\}}+\sum_{k_{1}\notin\\{1,2,3\\},k_{2}=2}+\sum_{k_{1},k_{2}\notin\\{1,2,3\\}}\Big{]}(\cdots)$
$\displaystyle\asymp\mathbb{E}\big{(}Z_{2}^{\top}U_{3}Z_{2}\big{)}(Z_{3}^{\top}U_{2}Z_{3})(Z_{1}^{\top}U_{3}^{\top}U_{2}Z_{1})+n\cdot\mathbb{E}\big{(}Z_{2}^{\top}U_{3}Z_{2}\big{)}(Z_{3}^{\top}U_{4}Z_{3})(Z_{1}^{\top}U_{3}^{\top}U_{4}Z_{1})$
$\displaystyle\qquad+n\cdot\mathbb{E}\big{(}Z_{2}^{\top}U_{4}Z_{2}\big{)}(Z_{3}^{\top}U_{2}Z_{3})(Z_{1}^{\top}U_{4}^{\top}U_{2}Z_{1})$
$\displaystyle\qquad+n^{2}\cdot\mathbb{E}\big{(}Z_{2}^{\top}U_{4}Z_{2}\big{)}(Z_{3}^{\top}U_{5}Z_{3})(Z_{1}^{\top}U_{4}^{\top}U_{5}Z_{1})\equiv\sum_{\ell}S_{4,\ell}.$

    1. (i)

By ((ii)),
$S_{4,1}\lesssim_{M}\lVert\Sigma_{X}\rVert_{F}^{4}\lVert\Sigma_{Y}\rVert_{F}^{4}$.

    2. (ii)

By first taking expectation with respect to $Z_{1}$ and $Z_{2}$, we have by
Lemma D.2-(4)(5)

$\displaystyle S_{4,2}/n$
$\displaystyle=\mathbb{E}\operatorname{tr}(U_{3})(Z_{3}^{\top}U_{4}Z_{3})\operatorname{tr}(U_{3}^{\top}U_{4})$
$\displaystyle\leq\mathbb{E}^{1/4}\operatorname{tr}^{4}(U_{3})\cdot\mathbb{E}^{1/4}(Z_{3}^{\top}U_{4}Z_{3})^{4}\cdot\mathbb{E}^{1/2}\operatorname{tr}^{2}(U_{3}^{\top}U_{4})$
$\displaystyle\lesssim_{M}\lVert\Sigma_{XY}\rVert_{F}\lVert\Sigma_{X}\rVert_{F}^{2}\lVert\Sigma_{Y}\rVert_{F}^{2}\lesssim(1\vee\lVert\Sigma_{XY}\rVert_{F}^{2})\lVert\Sigma_{X}\rVert_{F}^{2}\lVert\Sigma_{Y}\rVert_{F}^{2}.$

    3. (iii)

By taking expectation with respect to $Z_{1},Z_{3}$, a similar argument as in
(ii) yields that

$\displaystyle S_{4,3}/n$
$\displaystyle=\mathbb{E}(Z_{2}^{\top}U_{4}Z_{2})\operatorname{tr}(U_{2})\operatorname{tr}(U_{4}^{\top}U_{2})\lesssim_{M}(1\vee\lVert\Sigma_{XY}\rVert_{F}^{2})\lVert\Sigma_{X}\rVert_{F}^{2}\lVert\Sigma_{Y}\rVert_{F}^{2}$

    4. (iv)

By taking expectation with respect to $Z_{1},Z_{2},Z_{3}$, we have by Lemma
D.2-(6)

$\displaystyle
S_{4,4}/n^{2}=\mathbb{E}\operatorname{tr}(U_{4})\operatorname{tr}(U_{5})\operatorname{tr}(U_{4}^{\top}U_{5})\lesssim_{M}\lVert\Sigma_{XY}\rVert_{F}^{4}.$

Putting together the estimates in (i)-(iv), we have in this case

$\displaystyle S_{4}$
$\displaystyle\lesssim_{M}\lVert\Sigma_{X}\rVert_{F}^{4}\lVert\Sigma_{Y}\rVert_{F}^{4}+n\cdot(1\vee\lVert\Sigma_{XY}\rVert_{F}^{2})\lVert\Sigma_{X}\rVert_{F}^{2}\lVert\Sigma_{Y}\rVert_{F}^{2}+n^{2}\cdot\lVert\Sigma_{XY}\rVert_{F}^{4}.$
(D.10)

Finally combine (D.7) - (D.10) (and recall the notation $S_{1}$-$S_{4}$
defined at the end of each case) to conclude the bound for $\mathbb{E}\lVert
T_{33}\rVert_{F}^{2}$:

$\displaystyle\mathbb{E}\lVert T_{33}\rVert_{F}^{2}$ $\displaystyle\lesssim
n\cdot S_{1}+n^{2}\cdot S_{2}+n^{2}\cdot S_{3}+n^{3}\cdot S_{4}$
$\displaystyle\lesssim_{M}n\cdot\big{[}n^{2}\lVert\Sigma_{X}\rVert_{F}^{4}\lVert\Sigma_{Y}\rVert_{F}^{4}\big{]}$
$\displaystyle\quad\quad+n^{2}\cdot\big{[}n\cdot\lVert\Sigma_{X}\rVert_{F}^{4}\lVert\Sigma_{Y}\rVert_{F}^{4}+n^{2}(\lVert\Sigma_{X}\rVert_{F}^{2}+\lVert\Sigma_{Y}\rVert_{F}^{2})\lVert\Sigma_{XY}\rVert_{F}^{2}\big{]}$
$\displaystyle\quad\quad+n^{2}\cdot\big{[}n\lVert\Sigma_{X}\rVert_{F}^{4}\lVert\Sigma_{Y}\rVert_{F}^{4}+n^{2}\lVert\Sigma_{X}\rVert_{F}^{2}\lVert\Sigma_{Y}\rVert_{F}^{2}\big{]}$
$\displaystyle\quad\quad+n^{3}\cdot\big{[}\lVert\Sigma_{X}\rVert_{F}^{4}\lVert\Sigma_{Y}\rVert_{F}^{4}+n\cdot(1\vee\lVert\Sigma_{XY}\rVert_{F}^{2})\lVert\Sigma_{X}\rVert_{F}^{2}\lVert\Sigma_{Y}\rVert_{F}^{2}+n^{2}\cdot\lVert\Sigma_{XY}\rVert_{F}^{4}\big{]}$
$\displaystyle\asymp
n^{3}\cdot\lVert\Sigma_{X}\rVert_{F}^{4}\lVert\Sigma_{Y}\rVert_{F}^{4}+n^{4}\cdot(1\vee\lVert\Sigma_{XY}\rVert_{F}^{2})\lVert\Sigma_{X}\rVert_{F}^{2}\lVert\Sigma_{Y}\rVert_{F}^{2}+n^{5}\cdot\lVert\Sigma_{XY}\rVert_{F}^{4}.$

A similar bound holds for $T_{34}$. The above bound dominates the bound (D.5)
for $T_{31}$ and $T_{32}$ and hence is a valid bound for $T_{3}$.

(Variance of $T_{4}$ and $T_{5}$) By direct calculation, we have

$\displaystyle\operatorname{Var}(T_{4})\asymp
n^{5}\operatorname{Var}\big{(}X_{1}^{\top}\Sigma_{X}\Sigma_{XY}\Sigma_{Y}Y_{1}\big{)}\equiv
n^{5}\operatorname{Var}(U).$

Then

$\displaystyle\mathbb{E}\lVert\nabla_{X_{1}}(X_{1}^{\top}\Sigma_{X}\Sigma_{XY}\Sigma_{Y}Y_{1})\rVert^{2}=\mathbb{E}\lVert\nabla_{X_{1}}(\Sigma_{X}\Sigma_{XY}\Sigma_{Y}Y_{1})\rVert^{2}\lesssim_{M}\lVert\Sigma_{XY}\rVert_{F}^{2}.$

A similar bound holds for the gradient with respect to $Y_{1}$. By Gaussian-
Poincaré inequality and a change of variable, we then have

$\displaystyle\operatorname{Var}(T_{4})\lesssim_{M}\lVert\Sigma_{XY}\rVert_{F}^{2}.$

A similar bound holds for $\operatorname{Var}(T_{5})$.

(Variance of $T_{6}$) Recall the notation $U_{k}\equiv
H_{[11]}Z_{k}Z_{k}^{\top}H_{[22]}-G_{[12]}$. Then

$\displaystyle T_{6}$
$\displaystyle=(n-1)\sum_{k\neq\ell}(Z_{k}^{\top}G_{[12]}Z_{k}-\lVert\Sigma_{XY}\rVert_{F}^{2})\cdot(Z_{\ell}^{\top}U_{\ell}Z_{\ell}).$

Then for any $i\in[n]$ and $j\in[p+q]$, we have

$\displaystyle\frac{\partial T_{6}}{\partial Z_{ij}}$
$\displaystyle=(n-1)\cdot\sum_{k\neq\ell}\bigg{[}\delta_{ki}(Z_{k}^{\top}G_{[12]}e_{j}+e_{j}^{\top}G_{[12]}Z_{k})\cdot(Z_{\ell}^{\top}U_{k}Z_{\ell})$
$\displaystyle\quad+\delta_{\ell
i}(Z_{k}^{\top}G_{[12]}Z_{k}-\lVert\Sigma_{XY}\rVert_{F}^{2})(e_{j}^{\top}U_{k}Z_{\ell}+Z_{\ell}^{\top}U_{k}e_{j})$
$\displaystyle\quad+\delta_{ki}(Z_{k}^{\top}G_{[12]}Z_{k}-\lVert\Sigma_{XY}\rVert_{F}^{2})\cdot
Z_{\ell}^{\top}\big{[}H_{[11]}(Z_{k}e_{j}^{\top}+e_{j}Z_{k}^{\top})H_{[22]}\big{]}Z_{\ell}\bigg{]}$
$\displaystyle=(n-1)\cdot\sum_{k\neq
i}\bigg{[}(e_{j}^{\top}G_{[12]}Z_{i})(Z_{k}^{\top}U_{i}Z_{k})+(Z_{i}^{\top}G_{[12]}e_{j})(Z_{k}^{\top}U_{i}Z_{k})$
$\displaystyle\quad\quad+(Z_{k}^{\top}G_{[12]}Z_{k}-\lVert\Sigma_{XY}\rVert_{F}^{2})(e_{j}^{\top}U_{k}Z_{i})+(Z_{k}^{\top}G_{[12]}Z_{k}-\lVert\Sigma_{XY}\rVert_{F}^{2})(Z_{i}^{\top}U_{k}e_{j})$
$\displaystyle\quad\quad+(Z_{i}^{\top}G_{[12]}Z_{i}-\lVert\Sigma_{XY}\rVert_{F}^{2})(Z_{k}^{\top}H_{[11]}Z_{i}e_{j}^{\top}H_{[22]}Z_{k})$
$\displaystyle\quad\quad+(Z_{i}^{\top}G_{[12]}Z_{i}-\lVert\Sigma_{XY}\rVert_{F}^{2})(Z_{k}^{\top}H_{[11]}e_{j}Z_{i}^{\top}H_{[22]}Z_{k})\bigg{]}$
$\displaystyle\equiv(n-1)\cdot(T_{61}+T_{62}+T_{63}+T_{64}+T_{65}+T_{66})_{ij}.$

For $T_{61}$, we have

$\displaystyle\mathbb{E}\lVert T_{61}\rVert_{F}^{2}$
$\displaystyle=n\cdot\sum_{k_{1},k_{2}\neq
1}(Z_{k_{1}}^{\top}U_{1}Z_{k_{1}})(Z_{k_{2}}^{\top}U_{1}Z_{k_{2}})(Z_{1}^{\top}G_{[21]}G_{[12]}Z_{1})$
$\displaystyle\asymp
n\cdot\Big{[}n\cdot\mathbb{E}(Z_{2}^{\top}U_{1}Z_{2})^{2}(Z_{1}^{\top}G_{[12]}G_{[21]}Z_{1})$
$\displaystyle\qquad\qquad+n^{2}\cdot\mathbb{E}(Z_{2}^{\top}U_{1}Z_{2})(Z_{3}^{\top}U_{1}Z_{3})(Z_{1}^{\top}G_{[12]}G_{[21]}Z_{1})\Big{]}.$

The two terms can be bounded as follows:

  * •

By Lemma D.2-(4), we have

$\displaystyle\mathbb{E}(Z_{2}^{\top}U_{1}Z_{2})^{2}(Z_{1}^{\top}G_{[12]}G_{[21]}Z_{1})\leq\mathbb{E}^{1/2}(Z_{2}^{\top}U_{1}Z_{2})^{4}\cdot\mathbb{E}^{1/2}(Z_{1}^{\top}G_{[12]}G_{[21]}Z_{1})^{2}$
$\displaystyle\lesssim\mathbb{E}\big{[}\operatorname{tr}^{2}(U_{1})+\lVert
U_{1}\rVert_{F}^{2}\big{]}\cdot\lVert
G_{[12]}\rVert_{F}^{2}\asymp_{M}\lVert\Sigma_{X}\rVert_{F}^{2}\lVert\Sigma_{Y}\rVert_{F}^{2}\lVert\Sigma_{XY}\rVert_{F}^{2}+\lVert\Sigma_{XY}\rVert_{F}^{4}.$

  * •

Again by Lemma D.2-(4), we have

$\displaystyle\mathbb{E}(Z_{2}^{\top}U_{1}Z_{2})(Z_{3}^{\top}U_{1}Z_{3})(Z_{1}^{\top}G_{[12]}G_{[21]}Z_{1})=\mathbb{E}\operatorname{tr}(U_{1})^{2}(Z_{1}^{\top}G_{[12]}G_{[21]}Z_{1})$
$\displaystyle\leq\mathbb{E}^{1/2}\operatorname{tr}(U_{1})^{4}\cdot\mathbb{E}^{1/2}(Z_{1}^{\top}G_{[12]}G_{[21]}Z_{1})^{2}\lesssim\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_{61}\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.11)

A similar bound holds for $T_{62}$.

For $T_{63}$, we have

$\displaystyle\mathbb{E}\lVert T_{63}\rVert_{F}^{2}$
$\displaystyle=\mathbb{E}\sum_{i}\bigg{\lVert}\sum_{k\neq
i}(Z_{k}^{\top}G_{[12]}Z_{k}-\operatorname{tr}(G_{[12]}))U_{k}Z_{i}\bigg{\rVert}^{2}$
$\displaystyle=n\cdot\sum_{k_{1},k_{2}\neq
1}\mathbb{E}(Z_{k_{1}}^{\top}G_{[12]}Z_{k_{1}}-\operatorname{tr}(G_{[12]}))(Z_{k_{2}}^{\top}G_{[12]}Z_{k_{2}}-\operatorname{tr}(G_{[12]}))(Z_{1}^{\top}U_{k_{1}}^{\top}U_{k_{2}}Z_{1})$
$\displaystyle\asymp
n\cdot\Big{[}n\cdot\mathbb{E}(Z_{2}^{\top}G_{[21]}Z_{2}-\operatorname{tr}(G_{[12]}))^{2}\lVert
U_{2}\rVert_{F}^{2}$
$\displaystyle\quad\quad+n^{2}\cdot\mathbb{E}(Z_{2}^{\top}G_{[12]}Z_{2}-\operatorname{tr}(G_{[12]}))(Z_{3}^{\top}G_{[12]}Z_{3}-\operatorname{tr}(G_{[12]}))\operatorname{tr}(U_{2}^{\top}U_{3})\Big{]}.$

The two terms can be bounded as follows:

  * •

By Lemma D.2-(4),

$\displaystyle\mathbb{E}(Z_{2}^{\top}G_{[21]}Z_{2}-\operatorname{tr}(G_{[12]}))^{2}\lVert
U_{2}\rVert_{F}^{2}\leq\mathbb{E}^{1/2}(Z_{2}^{\top}G_{[21]}Z_{2}-\operatorname{tr}(G_{[12]}))^{4}\cdot\mathbb{E}^{1/2}\lVert
U_{2}\rVert_{F}^{4}$ $\displaystyle\lesssim_{M}\lVert
G_{[12]}\rVert_{F}^{2}\cdot\lVert\Sigma_{X}\rVert_{F}^{2}\lVert\Sigma_{Y}\rVert_{F}^{2}=\lVert\Sigma_{X}\rVert_{F}^{2}\lVert\Sigma_{Y}\rVert_{F}^{2}\lVert\Sigma_{XY}\rVert_{F}^{2}.$

  * •

By Lemma D.2-(4)(5), we have

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

In summary, we have

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

A similar bound holds for $T_{64}$.

For $T_{65}$, we have

$\displaystyle\mathbb{E}\lVert T_{65}\rVert_{F}^{2}$
$\displaystyle=\sum_{i}\mathbb{E}\bigg{\lVert}\sum_{k\neq
i}(Z_{i}^{\top}G_{[12]}Z_{i}-\operatorname{tr}(G_{[12]}))(Z_{k}^{\top}H_{[11]}Z_{i})H_{[22]}Z_{k}\bigg{\rVert}^{2}$
$\displaystyle=n\cdot\sum_{k_{1},k_{2}\neq
1}\mathbb{E}(Z_{1}^{\top}G_{[12]}Z_{1}-\operatorname{tr}(G_{[12]}))^{2}(Z_{k_{1}}^{\top}H_{[11]}Z_{1})(Z_{k_{2}}^{\top}H_{[11]}Z_{1})(Z_{k_{1}}^{\top}G_{[22]}Z_{k_{2}})$
$\displaystyle\asymp
n\cdot\Big{[}n\cdot\mathbb{E}(Z_{1}^{\top}G_{[12]}Z_{1}-\operatorname{tr}(G_{[12]}))^{2}(Z_{2}^{\top}H_{[11]}Z_{1})^{2}(Z_{2}^{\top}G_{[22]}Z_{2})$
$\displaystyle\quad\quad+n^{2}\cdot\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{]}.$

The two terms can be bounded as follows

  * •

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

$\displaystyle\mathbb{E}(Z_{1}^{\top}G_{[12]}Z_{1}-\operatorname{tr}(G_{[12]}))^{2}(Z_{2}^{\top}H_{[11]}Z_{1})^{2}(Z_{2}^{\top}G_{[22]}Z_{2})$
$\displaystyle\asymp\mathbb{E}(Z_{1}^{\top}G_{[12]}Z_{1}-\operatorname{tr}(G_{[12]}))^{2}(Z_{1}^{\top}G_{[11]}Z_{1})\operatorname{tr}(G_{[22]})$
$\displaystyle\leq\lVert\Sigma_{Y}\rVert_{F}^{2}\cdot\mathbb{E}^{1/2}(Z_{1}^{\top}G_{[12]}Z_{1}-\operatorname{tr}(G_{[12]}))^{4}\cdot\mathbb{E}^{1/2}(Z_{1}^{\top}G_{[11]}Z_{1})^{2}$