D^{(2)}+\frac{\lambda_{2}/(\rho\rho^{\prime})}{\|D^{(1)}-D^{(2)}\|_{\text{F}}}\left(D^{(1)}-D^{(2)}\right).$

(iii) $V^{(q)}_{(i)}\leftarrow V^{(q)}_{(i-1)}+W^{(q)}_{(i)}-R^{(q)}_{(i)}$,
$q=1,2$.

####  A.3.3 Solution to (A.8) for FFGL2

For FFGL2, there is also no closed form solution. Similar to Section A.3.2, we
compute a closed form solution for
$\\{\hat{Z}^{(1)}_{jj},\hat{Z}^{(2)}_{jj}\\}$, $j=1,\ldots,p$, and use an ADMM
algorithm to compute $\\{\hat{Z}^{(1)}_{jl},\hat{Z}^{(2)}_{jl}\\}$, $1\leq
j\neq l\leq p$.

For any $1\leq j,l\leq p$, we solve:

$\min_{\\{Z^{(1)}_{jl},Z^{(2)}_{jl}\\}}\;\frac{1}{2}\sum^{2}_{q=1}\|Z^{(q)}_{jl}-A^{(q)}_{jl}\|^{2}_{\text{F}}+\frac{\lambda_{1}}{\rho}\mathbbm{1}_{j\neq
l}\sum^{2}_{q=1}\|Z^{(q)}_{jl}\|_{\text{F}}+\frac{\lambda_{2}}{\rho}\sum_{1\leq
a,b\leq M}|Z^{(1)}_{jl,ab}-Z^{(2)}_{jl,ab}|,$ (A.13)

where $\mathbbm{1}_{j\neq l}=1$ when $j\neq l$ and $0$ otherwise.

By Lemma 6, when $j=l$ we have

$\left(\hat{Z}^{(1)}_{jj,ab},\hat{Z}^{(2)}_{jj,ab}\right)=\left\\{\begin{aligned}
&\left(A^{(1)}_{jl,ab}-\lambda_{2}/\rho,A^{(2)}_{jl,ab}+\lambda_{2}/\rho\right)\quad\text{if}\;A^{(1)}_{jl,ab}>A^{(2)}_{jl,ab}+2\lambda_{2}/\rho\\\
&\left(A^{(1)}_{jl,ab}+\lambda_{2}/\rho,A^{(2)}_{jl,ab}-\lambda_{2}/\rho\right)\quad\text{if}\;A^{(1)}_{jl,ab}<A^{(2)}_{jl,ab}-2\lambda_{2}/\rho\\\
&\left(\left(A^{(1)}_{jl,ab}+A^{(2)}_{jl,ab}\right)/2,\left(A^{(1)}_{jl,ab}+A^{(2)}_{jl,ab}\right)/2\right)\quad\text{if}\;\left|A^{(1)}_{jl,ab}-A^{(2)}_{jl,ab}\right|\leq
2\lambda_{2}/\rho,\end{aligned}\right.$

where subscripts $(a,b)$ denote the $(a,b)$-th entry, $1\leq a,b\leq M$ and
$j=1,\ldots,p$.

For $j\neq l$, we get $\\{\hat{Z}^{(1)}_{jl},\hat{Z}^{(2)}_{jl}\\}$, $1\leq
j\neq l\leq p$ by using an ADMM algorithm. Let $B^{(q)}=A^{(q)}_{jl}$,
$q=1,2$. We first construct the scaled augmented Lagrangian:

${L^{\prime}}_{\rho^{\prime}}\left(\\{W\\},\\{R\\},\\{V\\}\right)=\frac{1}{2}\sum^{2}_{q=1}\|W^{(q)}-B^{(q)}\|_{\text{F}}+\frac{\lambda_{1}}{\rho}\sum^{2}_{q=1}\|W^{(q)}\|_{\text{F}}\\\
+\frac{\lambda_{2}}{\rho}\sum_{a,b}|R^{(1)}_{a,b}-R^{(2)}_{a,b}|+\frac{\rho^{\prime}}{2}\sum^{2}_{q=1}\|W^{(q)}-R^{(q)}+V^{(q)}\|^{2}_{\text{F}},$

where $\rho^{\prime}>0$ is a tuning parameter,
$W^{q},R^{(q)},V^{(q)}\in\mathbb{R}^{M\times M}$, $q=1,2$,
$\\{W\\}=\\{W^{(1)},W^{(2)}\\}$, $\\{R\\}=\\{R^{(1)},R^{(2)}\\}$, and
$\\{V\\}=\\{V^{(1)},V^{(2)}\\}$. The detailed ADMM algorithm is described as
below:

ADMM algorithm for solving (A.13) for $j\neq l$

(a) Initialize the variables: $W^{(q)}_{(0)}=I_{M}$, $R^{(q)}_{(0)}=0_{M}$,
and $V^{(q)}_{(0)}=0_{M}$ for $q=1,2$. Let $B^{(q)}=A^{(q)}_{jl}$, $q=1,2$.

(b) Select a scalar $\rho^{\prime}>0$.

(c) For $i=1,2,3,\dots$ until convergence

(i)
$\\{W_{(i)}\\}\leftarrow\operatorname*{arg\,min}_{\\{W\\}}.{L^{\prime}}_{\rho^{\prime}}\left(\\{W\\},\\{R_{(i-1)}\\},\\{V_{(i-1)}\\}\right)$
This is equivalent to

$\\{W_{(i)}\\}\leftarrow\operatorname*{arg\,min}_{\\{W\\}}\frac{1}{2}\sum^{2}_{q=1}\|W^{(q)}-C^{(q)}\|^{2}_{\text{F}}+\frac{\lambda_{1}}{\rho(1+\rho^{\prime})}\sum^{2}_{q=1}\|W^{(q)}\|_{\text{F}},$

where

$C^{(q)}=\frac{1}{1+\rho^{\prime}}\left[B^{(q)}+\rho^{\prime}\left(R^{(q)}_{(i-1)}-V^{(q)}_{(i-1)}\right)\right].$

Similar to (28), we have

$W^{(q)}_{(i)}\leftarrow\left(\frac{\|C^{(q)}\|_{\text{F}}-\lambda_{1}/(\rho(1+\rho^{\prime}))}{\|C^{(q)}\|_{\text{F}}}\right)_{+}\cdot
C^{(q)},\qquad q=1,2.$

(ii)
$\\{R_{(i)}\\}\leftarrow\operatorname*{arg\,min}_{\\{R\\}}{L^{\prime}}_{\rho^{\prime}}\left(\\{W_{(i)}\\},\\{R\\},\\{V_{(i-1)}\\}\right)$
This is equivalent to

$\\{R_{(i)}\\}\leftarrow\operatorname*{arg\,min}_{\\{R\\}}\frac{1}{2}\sum^{2}_{q=1}\|R^{(q)}-D^{(q)}\|^{2}_{\text{F}}+\frac{\lambda_{2}}{\rho\rho^{\prime}}\sum_{a,b}\left|R^{(1)}_{ab}-R^{(2)}_{ab}\right|,$

where $D^{(q)}=W^{(q)}_{(i)}+V^{(q)}_{(i-1)}$. Then by Lemma 6, we have

$\left(R^{(1)}_{(i),ab},R^{(2)}_{(i),ab}\right)=\left\\{\begin{aligned}
&\left(D^{(1)}_{ab}-\lambda_{2}/(\rho\rho^{\prime}),D^{(2)}_{ab}+\lambda_{2}/(\rho\rho^{\prime})\right)\quad\text{if}\;D^{(1)}_{ab}>D^{(2)}_{ab}+2\lambda_{2}/(\rho\rho^{\prime})\\\
&\left(D^{(1)}_{ab}+\lambda_{2}/(\rho\rho^{\prime}),D^{(2)}_{ab}-\lambda_{2}/(\rho\rho^{\prime})\right)\quad\text{if}\;D^{(1)}_{ab}<D^{(2)}_{ab}-2\lambda_{2}/(\rho\rho^{\prime})\\\
&\left(\left(D^{(1)}_{ab}+D^{(2)}_{ab}\right)/2,\left(D^{(1)}_{ab}+D^{(2)}_{ab}\right)/2\right)\quad\text{if}\;\left|D^{(1)}_{ab}-D^{(1)}_{ab}\right|\leq
2\lambda_{2}/(\rho\rho^{\prime}),\end{aligned}\right.$

where subscripts $(a,b)$ denote the $(a,b)$-th entry, $1\leq a,b\leq M$ and
$1\leq j,l\leq p$.

(iii) $V^{(q)}_{(i)}\leftarrow V^{(q)}_{(i-1)}+W^{(q)}_{(i)}-R^{(q)}_{(i)}$,
$q=1,2$.

###  A.4 Derivation of (A.10) and (A.11)

We provide proof of (A.10) and (A.11).

Note that for any $1\leq j,l\leq p$, we can obtain
$\hat{Z}^{(1)}_{jl},\hat{Z}^{(2)}_{jl},\dots,\hat{Z}^{(Q)}_{jl}$ by solving

$\operatorname*{arg\,min}_{Z^{(1)}_{jl},Z^{(2)}_{jl},\dots,Z^{(Q)}_{jl}}\frac{\rho}{2}\sum^{Q}_{q=1}\|Z^{(q)}_{jl}-A^{(q)}_{jl}\|^{2}_{\text{F}}+\lambda_{1}\mathbbm{1}_{j\neq
l}\sum^{Q}_{q=1}\|Z^{(q)}_{jl}\|_{\text{F}}+\lambda_{2}\mathbbm{1}_{j\neq
l}\left(\sum^{Q}_{q=1}\|Z^{(q)}_{jl}\|^{2}_{\text{F}}\right)^{1/2},$ (A.14)

where $\mathbbm{1}_{j\neq l}=1$ when $j\neq l$ and $0$ otherwise. By (A.14),
we have that $\hat{Z}^{(q)}_{jj}=A^{(q)}_{jj}$ for any $j=1,\ldots,p$ and
$q=1,\ldots,Q$, which is (A.10). We then prove (A.11). Denote the objective
function in (A.14) as $\tilde{L}_{jl}$. Then, for $j\neq l$, the
subdifferential of $\tilde{L}_{jl}$ with respect to $Z^{(q)}_{jl}$ is

$\partial_{Z^{(q)}_{jl}}\tilde{L}_{jl}=\rho(Z^{(q)}_{jl}-A^{(q)}_{jl})+\lambda_{1}G^{(q)}_{jl}+\lambda_{2}D^{(q)}_{jl},$

where

$G^{(q)}_{jl}=\left\\{\begin{aligned}
&\frac{Z^{(q)}_{jl}}{\|Z^{(q)}_{jl}\|_{\text{F}}}\quad\text{when}\;Z^{(q)}_{jl}\neq
0\\\ &\\{G^{(q)}_{jl}\in\mathbb{R}^{M\times M}:\|G^{(q)}_{jl}\|_{\text{F}}\leq
1\\}\quad\text{otherwise}\end{aligned}\right.,$

and

$D^{(q)}_{jl}=\left\\{\begin{aligned}
&\frac{Z^{(q)}_{jl}}{\left(\sum^{Q}_{q=1}\|Z^{(q)}_{jl}\|^{2}_{\text{F}}\right)^{1/2}}\quad\text{when}\;\sum^{Q}_{q=1}\|Z^{(q)}_{jl}\|^{2}_{\text{F}}>0\\\
&\\{D^{(q)}_{jl}\in\mathbb{R}^{M\times
M}:\sum^{Q}_{q=1}\|D^{(q)}_{jl}\|^{2}_{\text{F}}\leq
1\\}\quad\text{otherwise}\end{aligned}\right..$

To obtain the optimum, we need

$0\in\partial_{Z^{(q)}_{jl}}\tilde{L}_{jl}(\hat{Z}^{(q)}_{jl})$

for all $q=1,\ldots,Q$. We now split our discussion into two cases.

(a) When $\sum^{Q}_{q=1}\|\hat{Z}^{(q)}_{jl}\|^{2}_{\text{F}}=0$, or
equivalently, $\hat{Z}^{(q)}_{jl}=0$ for all $q=1,\ldots,Q$.

In this case, there exists $G^{(q)}_{jl}$, where
$\|G^{(q)}_{jl}\|_{\text{F}}\leq 1$, for all $q=1,\ldots,Q$; and also
$D^{(q)}_{jl}$, where $\sum^{Q}_{q=1}\|D^{(q)}_{jl}\|^{2}_{\text{F}}\leq 1$,
such that

$0=-\rho\cdot A^{(q)}_{jl}+\lambda_{1}G^{(q)}_{jl}+\lambda_{2}D^{(q)}_{jl},$

which implies that

$D^{(q)}_{jl}=\frac{\rho}{\lambda_{2}}\left(A^{(q)}_{jl}-\frac{\lambda_{1}}{\rho}G^{(q)}_{jl}\right).$

Thus, we have

$\displaystyle\|D^{(q)}_{jl}\|_{\text{F}}$
$\displaystyle=\frac{\rho}{\lambda_{2}}\left\|A^{(q)}_{jl}-\frac{\lambda_{1}}{\rho}G^{(q)}_{jl}\right\|_{\text{F}}\geq\frac{\rho}{\lambda_{2}}\left(\|A^{(q)}_{jl}\|_{\text{F}}-\frac{\lambda_{1}}{\rho}\|G^{(q)}_{jl}\|_{\text{F}}\right)_{+}$
$\displaystyle\geq\frac{\rho}{\lambda_{2}}\left(\|A^{(q)}_{jl}\|_{\text{F}}-\frac{\lambda_{1}}{\rho}\right)_{+},$

which implies that

$\frac{\rho^{2}}{\lambda^{2}_{2}}\sum^{Q}_{q=1}\left(\|A^{(q)}_{jl}\|_{\text{F}}-\frac{\lambda_{1}}{\rho}\right)^{2}_{+}\leq\sum^{Q}_{q=1}\|D^{(q)}_{jl}\|^{2}_{\text{F}}\leq
1,$

and then we have

$\sqrt{\sum^{Q}_{q=1}\left(\|A^{(q)}_{jl}\|_{\text{F}}-\lambda_{1}/\rho\right)^{2}_{+}}\leq\lambda_{2}/\rho.$
(A.15)

(b) When $\sum^{Q}_{q=1}\|\hat{Z}^{(q)}_{jl}\|^{2}_{\text{F}}>0$.

For those $q$’s such that $\hat{Z}^{(q)}_{jl}=0$, there exists $G^{(q)}_{jl}$,
where $\|G^{(q)}_{jl}\|_{\text{F}}=1$, such that

$0=-\rho A^{(q)}_{jl}+\lambda_{1}G^{(q)}_{jl}.$

Thus, we have

$\|A^{(q)}_{jl}\|_{\text{F}}=\frac{\lambda_{1}}{\rho}\|G^{(q)}_{jl}\|_{\text{F}}\leq\frac{\lambda_{1}}{\rho},$

which implies that

$\left(\|A^{(q)}_{jl}\|_{\text{F}}-\lambda_{1}/\rho\right)_{+}=0.$ (A.16)

On the other hand, for those $q$’s such that $\hat{Z}^{(q)}_{jl}\neq 0$, we
have

$0=\rho\left(\hat{Z}^{(q)}_{jl}-A^{(q)}_{jl}\right)+\lambda_{1}\frac{\hat{Z}^{(q)}_{jl}}{\|\hat{Z}^{(q)}_{jl}\|_{\text{F}}}+\lambda_{2}\frac{\hat{Z}^{(q)}_{jl}}{\left(\sum^{Q}_{q=1}\|\hat{Z}^{(q)}_{jl}\|^{2}_{\text{F}}\right)^{1/2}},$

which implies that

$A^{(q)}_{jl}=\hat{Z}^{(q)}_{jl}\left(1+\frac{\lambda_{1}}{\rho\|\hat{Z}^{(q)}_{jl}\|_{\text{F}}}+\frac{\lambda_{2}}{\rho\left(\sum^{Q}_{q=1}\|\hat{Z}^{(q)}_{jl}\|^{2}_{\text{F}}\right)^{1/2}}\right),$
(A.17)

and

$\|A^{(q)}_{jl}\|_{\text{F}}=\|\hat{Z}^{(q)}_{jl}\|_{\text{F}}+\lambda_{1}/\rho+(\lambda_{2}/\rho)\cdot\frac{\|\hat{Z}^{(q)}_{jl}\|_{\text{F}}}{\left(\sum^{Q}_{q=1}\|\hat{Z}^{(q)}_{jl}\|^{2}_{\text{F}}\right)^{1/2}}.$
(A.18)

By (A.18), we have

$\left(\|A^{(q)}_{jl}\|_{\text{F}}-\lambda_{1}/\rho\right)_{+}>\frac{\lambda_{2}}{\rho}\cdot\frac{\|\hat{Z}^{(q)}_{jl}\|_{\text{F}}}{\sqrt{\sum^{Q}_{q=1}\|\hat{Z}^{(q)}_{jl}\|^{2}_{\text{F}}}}>0.$
(A.19)

By (A.16) and (A.19), we have

$\displaystyle\sum^{Q}_{q=}\left(\|A^{(q)}_{jl}\|_{\text{F}}-\lambda_{1}/\rho\right)^{2}_{+}$
$\displaystyle=\sum_{q:\|\hat{Z}^{(q)}_{jl}\|_{\text{F}}\neq
0}\left(\|A^{(q)}_{jl}\|_{\text{F}}-\lambda_{1}/\rho\right)^{2}_{+}$ (A.20)
$\displaystyle>\frac{\lambda^{2}_{2}}{\rho^{2}}\sum_{q:\|\hat{Z}^{(q)}_{jl}\|_{\text{F}}\neq
0}\frac{\|\hat{Z}^{(q)}_{jl}\|^{2}_{\text{F}}}{\sum^{Q}_{q=1}\|\hat{Z}^{(q)}_{jl}\|^{2}_{\text{F}}}$
$\displaystyle>\lambda^{2}_{2}/\rho^{2}.$

We now make the following claims.

Claim 1.
$\sum^{Q}_{q=1}\|\hat{Z}^{(q)}_{jl}\|^{2}_{\text{F}}=0\Leftrightarrow\sqrt{\sum^{Q}_{q=}\left(\|A^{(q)}_{jl}\|_{\text{F}}-\lambda_{1}/\rho\right)^{2}_{+}}\leq\lambda_{2}/\rho$.

This claim is easily shown by (A.15) and (A.20).

Claim 2. When $\sum^{Q}_{q=1}\|\hat{Z}^{(q)}_{jl}\|^{2}_{\text{F}}>0$, we have
$\|\hat{Z}^{(q)}_{jl}\|_{\text{F}}=0\Leftrightarrow\|A^{(q)}_{jl}\|_{\text{F}}\leq\lambda_{1}/\rho$.

This claim is easily shown by (A.16) and (A.19).

Claim 3. When $\|\hat{Z}^{(q)}_{jl}\|_{\text{F}}\neq 0$, then we have

$\hat{Z}^{(q)}_{jl}=\left(\frac{\|A^{(q)}_{jl}\|_{\text{F}}-\lambda_{1}/\rho}{\|A^{(q)}_{jl}\|_{\text{F}}}\right)\left(1-\frac{\lambda_{2}}{\rho\sqrt{\sum^{Q}_{q=}\left(\|A^{(q)}_{jl}\|_{\text{F}}-\lambda_{1}/\rho\right)^{2}_{+}}}\right)A^{(q)}_{jl}.$

To prove this claim, note that by Claim 2 and (A.18), we have

$\left(\|A^{(q)}_{jl}\|_{\text{F}}-\lambda_{1}/\rho\right)_{+}=\|\hat{Z}^{(q)}_{jl}\|_{\text{F}}\left(1+\frac{\lambda_{2}}{\rho\left(\sum^{Q}_{q=1}\|\hat{Z}^{(q)}_{jl}\|^{2}_{\text{F}}\right)^{1/2}}\right)$

for $q=1,\ldots,Q$. Thus,

$\sqrt{\sum^{Q}_{q=1}\left(\|A^{(q)}_{jl}\|_{\text{F}}-\lambda_{1}/\rho\right)^{2}_{+}}=\sqrt{\sum^{Q}_{q=1}\|\hat{Z}^{(q)}_{jl}\|^{2}_{\text{F}}}+\lambda_{2}/\rho,$

which implies that

$\sqrt{\sum^{Q}_{q=1}\|\hat{Z}^{(q)}_{jl}\|^{2}_{\text{F}}}=\sqrt{\sum^{Q}_{q=1}\left(\|A^{(q)}_{jl}\|_{\text{F}}-\lambda_{1}/\rho\right)^{2}_{+}}-\lambda_{2}/\rho.$

Thus, by (A.18), we have

$\displaystyle\|\hat{Z}^{(q)}_{jl}\|_{\text{F}}$
$\displaystyle=\frac{\|A^{(q)}_{jl}\|_{\text{F}}-\lambda_{1}/\rho}{1+\frac{\lambda_{2}/\rho}{\sqrt{\sum^{Q}_{q^{\prime}=1}\left(\|A^{(q^{\prime})}_{jl}\|_{\text{F}}-\lambda_{1}/\rho\right)^{2}_{+}}-\lambda_{2}/\rho}}$
$\displaystyle=\left(1-\frac{\lambda_{2}}{\rho\sqrt{\sum^{Q}_{q^{\prime}=1}\left(\|A^{(q^{\prime})}_{jl}\|_{\text{F}}-\lambda_{1}/\rho\right)^{2}_{+}}}\right)\left(\|A^{(q)}_{jl}\|_{\text{F}}-\lambda_{1}/\rho\right).$

This way, combined with (A.17), we then have

$\hat{Z}^{(q)}_{jl}=\frac{\|\hat{Z}^{(q)}_{jl}\|_{\text{F}}}{\|A^{(q)}_{jl}\|_{\text{F}}}A^{(q)}_{jl}=\left(\frac{\|A^{(q)}_{jl}\|_{\text{F}}-\lambda_{1}/\rho}{\|A^{(q)}_{jl}\|_{\text{F}}}\right)\left(1-\frac{\lambda_{2}}{\rho\sqrt{\sum^{Q}_{q^{\prime}=1}\left(\|A^{(q^{\prime})}_{jl}\|_{\text{F}}-\lambda_{1}/\rho\right)^{2}_{+}}}\right)A^{(q)}_{jl}.$

Finally, combining Claims 1-3, we obtain (A.11).

##  Appendix B Main Technical Proofs

We give proofs of the results given in the main text.

###  B.1 Proof of Lemma 2

We only need to prove that when we use two sets of orthonormal function basis
$e^{M}(t)=\\{e^{M}_{j}(t)\\}^{p}_{j=1}$ and
$\tilde{e}^{M}(t)=\\{\tilde{e}^{M}_{j}(t)\\}^{p}_{j=1}$ to expand the same
subspace $\mathbb{V}^{M}_{[p]}$, the definition of $E^{\pi}_{\Delta}$ will not
be changed. Since both
$e^{M}_{j}(t)=(e^{M}_{j1}(t),e^{M}_{j2}(t),\dots,e^{M}_{jM}(t))^{\top}$ and
$\tilde{e}^{M}_{j}(t)=(\tilde{e}^{M}_{j1}(t),\tilde{e}^{M}_{j2}(t),\dots,\tilde{e}^{M}_{jM}(t))^{\top}$
are orthonormal function basis of $\mathbb{V}^{M}_{j}$, there must exist an
orthonormal matrix $U_{j}\in\mathbb{R}^{M\times M}$ satisfying
$U^{\top}_{j}U_{j}=U_{j}U^{\top}_{j}=I_{M}$, such that
$\tilde{e}^{M}_{j}(t)=U_{j}e^{M}_{j}(t)$. Let $a^{X,M}_{ij}$ be the projection
score vectors of $X_{ij}(t)$ onto $e^{M}_{j}(t)$ and $\tilde{a}^{X,M}_{ij}$ be
the projection score vectors of $X_{ij}(t)$ onto $\tilde{e}^{M}_{j}(t)$. Then
$\tilde{a}^{X,M}_{ij}=U_{j}a^{X,M}_{ij}$. Denote

$U={\rm diag}\\{U_{1},U_{2},\dots,U_{p}\\}\in\mathbb{R}^{pM\times pM}.$

We then have

$\displaystyle\tilde{a}^{X,M}_{i}$
$\displaystyle=((\tilde{a}^{X,M}_{i1})^{\top},(\tilde{a}^{X,M}_{i2})^{\top},\dots,(\tilde{a}^{X,M}_{ip})^{\top})^{\top}$
$\displaystyle=((a^{X,M}_{i1})^{\top}U^{\top}_{1},(a^{X,M}_{i2})^{\top}U^{\top}_{2},\dots,(a^{X,M}_{ip})^{\top}U^{\top}_{p})^{\top}=Ua^{X,M}_{i}$

and

$\tilde{\Sigma}^{X,M}={\rm Cov}\left(\tilde{a}^{X,M}\right)=U{\rm
Cov}\left(\tilde{a}^{X,M}\right)U^{\top}=U\Sigma^{X,M}U^{\top}.$

Thus

$\tilde{\Theta}^{X,M}=\left(\tilde{\Sigma}^{X,M}\right)^{-1}=U\left(\Sigma^{X,M}\right)^{-1}U^{\top}=U\Theta^{X,M}U^{\top}.$

Therefore, $\tilde{\Theta}^{X,M}_{jl}=U_{j}\Theta^{X,M}_{jl}U^{\top}_{l}$ for
all $j,l\in V^{2}$ and, thus,
$\|\tilde{\Theta}^{X,M}_{jl}\|_{\text{F}}=\|\Theta^{X,M}_{jl}\|_{\text{F}}$
for all $j,l\in V^{2}$. This implies the final result.

###  B.2 Proof of Lemma 3

We first show that $X_{ij},Y_{ij}\in{\rm
Span}\left\\{\phi_{j1},\dots,\phi_{jM^{\star}_{j}}\right\\}$ almost surely.
Let

$M^{X}_{j}=\sup\\{M\in\mathbb{N}^{+}:\lambda^{X}_{jM}>0\\}.$

By Karhunen–Loève theorem, we have $X_{ij}=\sum^{M^{X}_{j}}_{k=1}\langle
X_{ij},\phi^{X}_{jk}\rangle\phi^{X}_{jk}$ almost surely. Thus, we have
$X_{ij}\in{\rm
Span}\left\\{\phi^{X}_{j1},\dots,\phi^{X}_{j,M^{X}_{j}}\right\\}$ almost
surely. For any $1\leq k\leq M^{X}_{j}$, we have that

$\int_{\mathcal{T}}K_{jj}(s,t)\phi^{X}_{k}(s)\phi^{X}_{k}(t)dsdt\geq\int_{\mathcal{T}}K^{X}_{jj}(s,t)\phi^{X}_{k}(s)\phi^{X}_{k}(t)dsdt=\lambda^{X}_{jk}>0,$

which implies that $\phi^{X}_{k}\in{\rm
Span}\left\\{\phi_{j1},\dots,\phi_{jM^{\star}_{j}}\right\\}$. Thus, we have
${\rm
Span}\left\\{\phi^{X}_{j1},\dots,\phi^{X}_{j,M^{X}_{j}}\right\\}\subseteq{\rm
Span}\left\\{\phi_{j1},\dots,\phi_{jM^{\star}_{j}}\right\\}$ and
$X_{ij}\in{\rm Span}\left\\{\phi_{j1},\dots,\phi_{jM^{\star}_{j}}\right\\}$
almost surely. Similarly, we have that $Y_{ij}\in{\rm
Span}\left\\{\phi_{j1},\dots,\phi_{jM^{\star}_{j}}\right\\}$ almost surely.

Next, we show that $M^{\prime}_{j}=M^{\star}_{j}$ by contradiction. By the
definition of $M^{\prime}_{j}$, we have that $M^{\prime}_{j}\leq
M^{\star}_{j}$. If $M^{\prime}_{j}\neq M^{\star}_{j}$, then we have
$\mathbb{V}^{M^{\prime}_{j}}_{j}\subseteq\mathbb{H}$ such that
$M^{\prime}_{j}<M^{\star}_{j}$ and
$X_{ij},Y_{ij}\in\mathbb{V}^{M^{\prime}_{j}}_{j}$ almost surely. This implies
that there exists $\phi\in{\rm
Span}\left\\{\phi_{j1},\dots,\phi_{jM^{\star}_{j}}\right\\}\setminus\mathbb{V}^{M^{\prime}_{j}}_{j}$
such that

$\displaystyle\mathbb{E}\left[\left(\langle\phi_{jk}(t),X_{ij}(t)\rangle\right)^{2}\right]=0\quad\text{and}\quad\mathbb{E}\left[\left(\langle\phi_{jk}(t),Y_{ij}(t)\rangle\right)^{2}\right]=0$
$\displaystyle\Rightarrow$
$\displaystyle\int_{\mathcal{T}}K^{X}_{jj}(s,t)\phi_{jk}(s)\phi_{jk}(t)dsdt=0\quad\text{and}\quad\int_{\mathcal{T}}K^{Y}_{jj}(s,t)\phi_{jk}(s)\phi_{jk}(t)dsdt=0$
$\displaystyle\Rightarrow$
$\displaystyle\int_{\mathcal{T}}K_{jj}(s,t)\phi_{jk}(s)\phi_{jk}(t)dsdt=0,$
$\displaystyle\Rightarrow$ $\displaystyle\lambda_{jk}=0,$

which contradicts the definition of $M^{\star}_{j}$. Thus, we must have
$M^{\prime}_{j}=M^{\star}_{j}$.

###  B.3 Proof of Lemma 4

Let $U=V\backslash\\{j,l\\}$, and $a^{X,M}_{U}=\left((a^{X,M}_{j})^{\top},j\in
U\right)^{\top}$. Without loss of generality, assume that $\Sigma^{X,M}$ and
$\Theta^{X,M}$ take the following block structure:

$\displaystyle\Sigma^{X,M}=\left[\begin{matrix}\Sigma^{X,M}_{jj}&\Sigma^{X,M}_{jl}&\Sigma^{X,M}_{jU}\\\
\Sigma^{X,M}_{lj}&\Sigma^{X,M}_{ll}&\Sigma^{X,M}_{lU}\\\
\Sigma^{X,M}_{Uj}&\Sigma^{X,M}_{Ul}&\Sigma^{X,M}_{UU}\\\
\end{matrix}\right],\quad\Theta^{X,M}=\left[\begin{matrix}\Theta^{X,M}_{jj}&\Theta^{X,M}_{jl}&\Theta^{X,M}_{jU}\\\
\Theta^{X,M}_{lj}&\Theta^{X,M}_{ll}&\Theta^{X,M}_{lU}\\\
\Theta^{X,M}_{Uj}&\Theta^{X,M}_{Ul}&\Theta^{X,M}_{UU}\\\ \end{matrix}\right].$

Let $P$ denote the submatrix:

$P=\left[\begin{matrix}\Theta^{X,M}_{jj}&\Theta^{X,M}_{jl}\\\
\Theta^{X,M}_{lj}&\Theta^{X,M}_{ll}\end{matrix}\right].$

By standard results for the multivariate Gaussian (Heckler, 2005), we have

$\displaystyle\mathrm{Var}\left(a^{X,M}_{j}\mid a^{X,M}_{k},k\neq
j\right)=H^{X,M}_{jj}=(\Theta^{X,M}_{jj})^{-1},$
$\displaystyle\mathrm{Var}\left(\left[\begin{matrix}a^{X,M}_{j}\\\
a^{X,M}_{l}\end{matrix}\right]\mid
a^{X,M}_{U}\right)=P^{-1}=\left[\begin{matrix}(P^{-1})_{11}&(P^{-1})_{12}\\\
(P^{-1})_{21}&(P^{-1})_{22}\end{matrix}\right].$

Thus, the first statement directly follows from the first equation. To prove
the second statement, we only need to note that

$\displaystyle H^{X,M}_{jl}$
$\displaystyle=\mathrm{Cov}\left(a^{X,M}_{j},a^{X,M}_{l}\mid
a^{X,M}_{U}\right)$ $\displaystyle=(P^{-1})_{12}$
$\displaystyle=-(\Theta^{X,M}_{jj})^{-1}\Theta^{X,M}_{jl}(P^{-1})_{22}$
$\displaystyle=-H^{X,M}_{jj}\Theta_{jl}^{X,M}H^{\backslash j,X,M}_{ll},$

where the second to last equation follows from the $2\times 2$ block matrix
inverse and the last equation follows from the property of multivariate
Gaussian. This completes the proof.

###  B.4 Proof of Theorem 1

We provide the proof of Theorem 1, following the framework introduced in
Negahban et al. (2012). We start by introducing some notation.

We use $\otimes$ to denote the Kronecker product. For
$\Delta\in\mathbb{R}^{pM\times pM}$, let
$\theta=\operatorname{vec}(\Delta)\in{\mathbb{R}^{p^{2}M^{2}}}$ and
$\theta^{*}=\operatorname{vec}({\Delta^{M}})$, where $\Delta^{M}$ is defined
in Section 2.2. Let $\mathcal{G}=\\{G_{t}\\}_{t=1,\ldots,N_{\mathcal{G}}}$ be
a set of indices, where $N_{\mathcal{G}}=p^{2}$ and
$G_{t}\subset\\{1,2,\cdots,p^{2}M^{2}\\}$ is the set of indices for $\theta$
that correspond to the $t$-th $M\times M$ submatrix of $\Delta^{M}$. Thus, if
$t=(j-1)p+l$, then
$\theta_{G_{t}}=\operatorname{vec}{(\Delta_{jl})}\in{\mathbb{R}^{M^{2}}}$,
where $\Delta_{jl}$ is the $(j,l)$-th $M\times{M}$ submatrix of $\Delta$.
Denote the group indices of $\theta^{*}$ that belong to blocks corresponding
to $E_{\Delta}$ as
$S_{\mathcal{G}}\subseteq{\\{1,2,\cdots,N_{\mathcal{G}}\\}}$. Note that we
define $S_{\mathcal{G}}$ using $E_{\Delta}$ and not $E_{\Delta^{M}}$.
Therefore, as stated in Assumption 2, $|S_{\mathcal{G}}|=s$. We further define
the subspace $\mathcal{M}$ as

${}\mathcal{M}\coloneqq{\\{\theta\in{\mathbb{R}^{p^{2}M^{2}}}\mid\theta_{G_{t}}=0\text{
for all }t\notin{S_{\mathcal{G}}}\\}}.$ (B.1)

Its orthogonal complement with respect to the Euclidean inner product is

$\mathcal{M}^{\bot}\coloneqq{\\{\theta\in{\mathbb{R}^{p^{2}M^{2}}}\mid\theta_{G_{t}}=0\text{
for all }t\in{S_{\mathcal{G}}}\\}}.$ (B.2)

For a vector $\theta$, let $\theta_{\mathcal{M}}$ and
$\theta_{\mathcal{M}^{\bot}}$ be the projection of $\theta$ on the subspaces
$\mathcal{M}$ and $\mathcal{M}^{\bot}$, respectively. Let
$\langle\cdot,\cdot\rangle$ represent the Euclidean inner product. Let

${}\mathcal{R}(\theta)\coloneqq{\sum_{t=1}^{N_{\mathcal{G}}}|\theta_{G_{t}}|_{2}}\triangleq{|\theta|_{1,2}}.$
(B.3)

For any $v\in{\mathbb{R}^{p^{2}M^{2}}}$, the dual norm of $\mathcal{R}$ is
given by

${}\mathcal{R}^{*}(v)\coloneqq\sup_{u\in{\mathbb{R}^{p^{2}M^{2}}\backslash{\\{0\\}}}}\frac{\langle{u},{v}\rangle}{\mathcal{R}(u)}=\sup_{\mathcal{R}(u)\leq{1}}\langle{u},{v}\rangle.$
(B.4)

The subspace compatibility constant of $\mathcal{M}$ with respect to
$\mathcal{R}$ is defined as

${}\Psi(\mathcal{M})\coloneqq{\sup_{u\in{\mathcal{M}\backslash\\{0\\}}}}\frac{\mathcal{R}(u)}{|u|_{2}}.$
(B.5)

Proof  By Lemma 5 and Assumption 1, we have

$|(S^{Y,M}\otimes{S^{X,M}})-(\Sigma^{Y,M}\otimes{\Sigma^{X,M}})|_{\infty}\leq\delta_{n}^{2}+2\delta_{n}\sigma_{\max}$
(B.6)

and

$|\operatorname{vec}{(S^{Y,M}-S^{X,M})}-\operatorname{vec}{(\Sigma^{Y,M}-\Sigma^{X,M})}|_{\infty}\leq
2\delta_{n}.$ (B.7)

Problem (25) can be written in the following form:

$\hat{\theta}_{\lambda_{n}}\in\operatorname*{arg\,min}_{\theta\in{\mathbb{R}^{p^{2}M^{2}}}}\mathcal{L}(\theta)+\lambda_{n}\mathcal{R}(\theta),$
(B.8)

where

${}\mathcal{L}(\theta)=\frac{1}{2}\theta^{\top}(S^{Y,M}\otimes{S^{X,M}})\theta-\theta^{\top}\operatorname{vec}({S^{Y,M}-S^{X,M}}).$
(B.9)

The loss $\mathcal{L}(\theta)$ is convex and differentiable with respect to
$\theta$, and it can be easily verified that $\mathcal{R}(\cdot)$ defines a
vector norm. For $h\in\mathbb{R}^{p^{2}M^{2}}$, the error of the first-order
Taylor series expansion of $\mathcal{L}$ is:

$\displaystyle\delta{\mathcal{L}}(h,\theta^{*})\coloneqq\mathcal{L}(\theta^{*}+h)-\mathcal{L}(\theta^{*})-\langle\nabla\mathcal{L}(\theta^{*}),h\rangle=\frac{1}{2}h^{\top}(S^{Y,M}\otimes{S^{X,M}})h.$
(B.10)

From (B.9), we see that
$\nabla{\mathcal{L}}(\theta)=(S^{Y,M}\otimes{S^{X,M}})\theta-\operatorname{vec}({S^{Y,M}-S^{X,M}})$.
By Lemma 9, we have

${}\mathcal{R}^{*}(\nabla{\mathcal{L}}(\theta^{*}))=\max_{t=1,2,\cdots,N_{\mathcal{G}}}\left|\left[(S^{Y,M}\otimes{S^{X,M}})\theta^{*}-\operatorname{vec}({S^{Y,M}-S^{X,M}})\right]_{G_{t}}\right|_{2}.$
(B.11)

We now establish an upper bound for
$\mathcal{R}^{*}(\nabla{\mathcal{L}}(\theta^{*}))$. First, note that

$(\Sigma^{Y,M}\otimes{\Sigma^{X,M}})\theta^{*}-\operatorname{vec}({\Sigma^{Y,M}-\Sigma^{X,M}})=\operatorname{vec}({\Sigma^{X,M}\Delta^{M}\Sigma^{Y,M}-(\Sigma^{Y,M}-\Sigma^{X,M})})=0.$

Letting $(\cdot)_{jl}$ denote the $(j,l)$-th submatrix, we have

$\displaystyle\left|\left[(S^{Y,M}\otimes{S^{X,M}})\theta^{*}-\operatorname{vec}({S^{Y,M}-S^{X,M}})\right]_{G_{t}}\right|_{2}$
(B.12)
$\displaystyle=\left|\left[(S^{Y,M}\otimes{S^{X,M}}-\Sigma^{Y,M}\otimes{\Sigma^{X,M}})\theta^{*}-\operatorname{vec}{((S^{Y,M}-\Sigma^{Y,M})-(S^{X,M}-\Sigma^{X,M}))}\right]_{G_{t}}\right|_{2}$
$\displaystyle={\|(S^{X,M}\Delta^{M}S^{Y,M}-\Sigma^{X,M}\Delta^{M}\Sigma^{Y,M})_{jl}-(S^{Y,M}-\Sigma^{Y,M})_{jl}-(S^{X,M}-\Sigma^{X,M})_{jl}\|_{F}}$
$\displaystyle\leq{\|(S^{X,M}\Delta^{M}S^{Y,M}-\Sigma^{X,M}\Delta^{M}\Sigma^{Y,M})_{jl}\|_{F}+\|(S^{Y,M}-\Sigma^{Y,M})_{jl}\|_{F}+\|(S^{X,M}-\Sigma^{X,M})_{jl}\|_{F}}.$

For any $M\times{M}$ matrix $A$, $\|A\|_{F}\leq{M|A|_{\infty}}$, so

$\displaystyle\left|\left[(S^{Y,M}\otimes{S^{X,M}})\theta^{*}-\operatorname{vec}({S^{Y,M}-S^{X,M}})\right]_{G_{t}}\right|_{2}$
$\displaystyle\leq
M\left[\left|(S^{X,M}\Delta^{M}S^{Y,M}-\Sigma^{X,M}\Delta^{M}\Sigma^{Y,M})_{jl}\right|_{\infty}+\left|(S^{Y,M}-\Sigma^{Y,M})_{jl}\right|_{\infty}+\left|(S^{X,M}-\Sigma^{X,M})_{jl}\right|_{\infty}\right]$
$\displaystyle\leq
M\left[\left|S^{X,M}\Delta^{M}S^{Y,M}-\Sigma^{X,M}\Delta^{M}\Sigma^{Y,M}\right|_{\infty}+|S^{Y,M}-\Sigma^{Y,M}|_{\infty}+|S^{X,M}-\Sigma^{X,M}|_{\infty}\right].$

For any $A\in{\mathbb{R}^{k\times{k}}}$ and $v\in{\mathbb{R}^{k}}$, we have
$|Av|_{\infty}\leq{|A|_{\infty}|v|_{1}}$. Thus, we further have

$\displaystyle|S^{X,M}\Delta^{M}S^{Y,M}-\Sigma^{X,M}\Delta^{M}\Sigma^{Y,M}|_{\infty}$
$\displaystyle=|[(S^{Y,M}\otimes{S^{X,M}})-(\Sigma^{X,M}\otimes{\Sigma^{Y,M}})]\operatorname{vec}{(\Delta^{M})}|_{\infty}$
$\displaystyle\leq{|(S^{Y,M}\otimes{S^{X,M}})-(\Sigma^{X,M}\otimes{\Sigma^{Y,M}})|_{\infty}}|\operatorname{vec}{(\Delta^{M})}|_{1}$
$\displaystyle=|(S^{Y,M}\otimes{S^{X,M}})-(\Sigma^{X,M}\otimes{\Sigma^{Y,M}})|_{\infty}|\Delta^{M}|_{1}.$

Combining the inequalities gives an upper bound uniform over $\mathcal{G}$
(i.e., for all $G_{t}$):

$\displaystyle\left|\left[(S^{Y,M}\otimes{S^{X,M}})\theta^{*}-\operatorname{vec}({S^{Y,M}-S^{X,M}})\right]_{G_{t}}\right|_{2}$
$\displaystyle\leq
M\left[|(S^{Y,M}\otimes{S^{X,M}})-(\Sigma^{X,M}\otimes{\Sigma^{Y,M}})|_{\infty}|\Delta^{M}|_{1}+|S^{Y,M}-\Sigma^{Y,M}|_{\infty}+|S^{X,M}-\Sigma^{X,M}|_{\infty}\right],$

which implies

$\displaystyle\mathcal{R}^{*}\left(\nabla{\mathcal{L}}(\theta^{*})\right)\leq$
$\displaystyle
M[|(S^{Y,M}\otimes{S^{X,M}})-(\Sigma^{X,M}\otimes{\Sigma^{Y,M}})|_{\infty}|\Delta^{M}|_{1}+$
(B.13)
$\displaystyle|S^{Y,M}-\Sigma^{Y,M}|_{\infty}+|S^{X,M}-\Sigma^{X,M}|_{\infty}].$

Assuming $|S^{X,M}-\Sigma^{X,M}|_{\infty}\leq{\delta_{n}}$ and
$|S^{Y,M}-\Sigma^{Y,M}|_{\infty}\leq\delta_{n}$ implies

${}\mathcal{R}^{*}\left(\nabla{\mathcal{L}}(\theta^{*})\right)\leq{M[(\delta_{n}^{2}+2\delta_{n}\sigma_{\max})|\Delta^{M}|_{1}+2\delta_{n}]}.$
(B.14)

Setting

${}\lambda_{n}=2M\left[\left(\delta_{n}^{2}+2\delta_{n}\sigma_{\max}\right)\left|\Delta^{M}\right|_{1}+2\delta_{n}\right],$
(B.15)

then implies that
$\lambda_{n}\geq{2\mathcal{R}^{*}\left(\nabla{\mathcal{L}}(\theta^{*})\right)}$.
Thus, invoking Lemma 1 in Negahban et al. (2012),
$h=\hat{\theta}_{\lambda_{n}}-\theta^{*}$ must satisfy

${}\mathcal{R}(h_{\mathcal{M}^{\bot}})\leq{3\mathcal{R}(h_{\mathcal{M}})}+4\mathcal{R}(\theta^{*}_{\mathcal{M}^{\bot}}),$
(B.16)

where $\mathcal{M}$ is defined in (B.1). Equivalently,

${}|h_{\mathcal{M}^{\bot}}|_{1,2}\leq{3|h_{\mathcal{M}}|_{1,2}}+4|\theta^{*}_{\mathcal{M}^{\bot}}|_{1,2}.$
(B.17)

By the definition of $\nu_{2}$, we have

${}|\theta^{*}_{\mathcal{M}^{\bot}}|_{1,2}=\sum_{t\notin{\mathcal{S}_{\mathcal{G}}}}|\theta^{*}_{G_{t}}|_{2}\leq\left(p(p+1)/2-s\right)\nu_{2}\leq
p^{2}\nu_{2}.$ (B.18)

Next, we show that $\delta\mathcal{L}(h,\theta^{*})$, as defined in (B.10),
satisfies the Restricted Strong Convexity property defined in definition 2 in
Negahban et al. (2012). That is, we show an inequality of the form:
$\delta\mathcal{L}(h,\theta^{*})\geq{\kappa_{\mathcal{L}}|h|^{2}_{2}}-\omega^{2}_{\mathcal{L}}\left(\theta^{*}\right)$
whenever $h$ satisfies (B.17).

By using Lemma 7, we have

$\displaystyle\theta^{\top}(S^{Y,M}\otimes{S^{X,M}})\theta$
$\displaystyle=\theta^{\top}(\Sigma^{Y,M}\otimes{\Sigma^{X,M}})\theta+\theta^{\top}(S^{Y,M}\otimes{S^{X,M}}-\Sigma^{Y,M}\otimes{\Sigma^{X,M}})\theta$
$\displaystyle\geq{\theta^{\top}(\Sigma^{Y,M}\otimes{\Sigma^{X,M}})\theta-|\theta^{\top}(S^{Y,M}\otimes{S^{X,M}}-\Sigma^{Y,M}\otimes{\Sigma^{X,M}})\theta|}$
$\displaystyle\geq{\lambda^{*}_{\min}}|\theta|^{2}_{2}-M^{2}|S^{Y,M}\otimes{S^{X,M}}-\Sigma^{Y,M}\otimes{\Sigma^{X,M}}|_{\infty}|\theta|^{2}_{1,2},$

where the last inequality holds because Lemma 7 and
$\lambda^{*}_{\min}=\lambda_{\min}(\Sigma^{X,M})\times{\lambda_{\min}(\Sigma^{Y,M})}=\lambda_{\min}(\Sigma^{Y,M}\otimes{\Sigma^{X,M}})>0$.
Thus,

$\displaystyle\delta\mathcal{L}(h,\theta^{*})$
$\displaystyle=\frac{1}{2}h^{\top}(S^{Y,M}\otimes{S^{X,M}})h$
$\displaystyle\geq{\frac{1}{2}\lambda^{*}_{\min}}|h|^{2}_{2}-\frac{1}{2}M^{2}|S^{Y,M}\otimes{S^{X,M}}-\Sigma^{Y,M}\otimes{\Sigma^{X,M}}|_{\infty}|h|^{2}_{1,2}.$

By Lemma 8 and (B.17), we have

$\displaystyle|h|^{2}_{1,2}$
$\displaystyle=(|h_{\mathcal{M}}|_{1,2}+|h_{\mathcal{M}^{\bot}}|_{1,2})^{2}\leq
16({|h_{\mathcal{M}}|_{1,2}}+|\theta^{*}_{\mathcal{M}^{\bot}}|_{1,2})^{2}$
$\displaystyle\leq 16(\sqrt{s}|h|_{2}+p^{2}\nu_{2})^{2}\leq
32s|h|^{2}_{2}+32p^{4}\nu_{2}^{2}.$

Combining with the equation above, we get

$\displaystyle\delta\mathcal{L}(h,\theta^{*})$
$\displaystyle\geq{\left[\frac{1}{2}\lambda^{*}_{\min}-16M^{2}s|S^{Y,M}\otimes{S^{X,M}}-\Sigma^{Y,M}\otimes{\Sigma^{X,M}}|_{\infty}\right]}|h|^{2}_{2}$
(B.19)
$\displaystyle\qquad\qquad-16M^{2}p^{4}\nu_{2}^{2}|S^{Y,M}\otimes{S^{X,M}}-\Sigma^{Y,M}\otimes{\Sigma^{X,M}}|_{\infty}$
$\displaystyle\geq\left[\frac{1}{2}\lambda^{*}_{\min}-8M^{2}s\left(\delta^{2}_{n}+2\delta^{2}_{n}\sigma_{\max}\right)\right]|h|^{2}_{2}$
$\displaystyle\qquad\qquad-16M^{2}p^{4}\nu_{2}^{2}\left(\delta^{2}_{n}+2\delta_{n}\sigma_{\max}\right).$

Thus, appealing to (B.6), the Restricted Strong Convexity property holds with

$\displaystyle\kappa_{\mathcal{L}}$
$\displaystyle\;=\;\frac{1}{2}\lambda^{*}_{\min}-8M^{2}s\left(\delta^{2}+2\delta_{n}\sigma_{\max}\right),$
(B.20) $\displaystyle\omega_{\mathcal{L}}$
$\displaystyle\;=\;4Mp^{2}\nu_{2}\sqrt{\delta_{n}^{2}+2\delta_{n}\sigma_{\max}}.$

When
$\delta_{n}<\frac{1}{4}\sqrt{\frac{\lambda^{*}_{\min}+16M^{2}s(\sigma_{\max})^{2}}{M^{2}s}}-\sigma_{\max}$
as we assumed in the theorem, then $\kappa_{\mathcal{L}}>0$. By Theorem 1 of
Negahban et al. (2012) and Lemma 8, letting
$\lambda_{n}=2M\left[\left(\delta_{n}^{2}+2\delta_{n}\sigma_{\max}\right)|\Delta^{M}|_{1}+2\delta_{n}\right]$,
as in (B.15), ensures

$\displaystyle\|\hat{\Delta}^{M}-\Delta^{M}\|^{2}_{F}$
$\displaystyle=|\hat{\theta}_{\lambda_{n}}-\theta^{*}|^{2}_{2}$ (B.21)
$\displaystyle\leq{9\frac{\lambda^{2}_{n}}{\kappa^{2}_{\mathcal{L}}}}\Psi^{2}(\mathcal{M})+\frac{\lambda_{n}}{\kappa_{\mathcal{L}}}\left(2\omega^{2}_{\mathcal{L}}+4\mathcal{R}(\theta^{*}_{\mathcal{M}^{\bot}})\right)$
$\displaystyle=\frac{9\lambda^{2}_{n}s}{\kappa^{2}_{\mathcal{L}}}+\frac{2\lambda_{n}}{\kappa_{\mathcal{L}}}(\omega^{2}_{\mathcal{L}}+2p^{2}\nu_{2})$
$\displaystyle=\Gamma^{2}_{n}.$

We then prove that $\hat{E}_{\Delta}=E_{\Delta}$. Recall that we have assumed
that $0<\Gamma_{n}<\tau/2=(\nu_{1}-\nu_{2})/2$ and
$\nu_{2}+\Gamma_{n}\leq\epsilon_{n}<\nu_{1}-\Gamma_{n}$. Note that we have
$\|\hat{\Delta}^{M}_{jl}-\Delta^{M}_{jl}\|_{F}\leq{\|\hat{\Delta}^{M}-\Delta^{M}\|_{F}}\leq\Gamma_{n}$
for any $(j,l)\in{V^{2}}$. Recall that

${}E_{\Delta}\;=\;\\{(j,l)\in{V^{2}}:\;j\neq{l},D_{jl}>0\\}.$ (B.22)

We first prove that $E_{\Delta}\subseteq{\hat{E}_{{\Delta}}}$. For any
$(j,l)\in{E_{\Delta}}$, by the definition of $\nu_{1}$ in Section 4.1, we have

$\displaystyle\|\hat{\Delta}^{M}_{jl}\|_{F}$
$\displaystyle\geq{\|\Delta^{M}_{jl}\|_{F}-\|\hat{\Delta}_{jl}^{M}-\Delta^{M}_{jl}\|_{F}}$
$\displaystyle\geq\nu_{1}-\Gamma_{n}$ $\displaystyle>\epsilon_{n}.$

The last inequality holds because we have assumed that
$\epsilon_{n}<\nu_{1}-\Gamma_{n}$. Thus, by definition of $\hat{E}_{{\Delta}}$
in (27), we have $(j,l)\in{\hat{E}_{{\Delta}}}$, which further implies that
$E_{\Delta}\subseteq{\hat{E}_{{\Delta}}}$.

We then show $\hat{E}_{{\Delta}}\subseteq{E_{\Delta}}$. Let
$\hat{E}^{c}_{{\Delta}}$ and $E^{c}_{\Delta}$ denote the complement set of
$\hat{E}_{{\Delta}}$ and $E_{\Delta}$. For any $(j,l)\in{E^{c}_{\Delta}}$,
which also means that $(l,j)\in{E^{c}_{\Delta}}$, by definition of $\nu_{2}$,
we have that

$\displaystyle\|\hat{\Delta}^{M}_{jl}\|_{F}$
$\displaystyle\leq{\|\Delta^{M}_{jl}\|_{F}+\|\hat{\Delta}_{jl}^{M}-\Delta^{M}_{jl}\|_{F}}$
$\displaystyle\leq\nu_{2}+\Gamma_{n}$ $\displaystyle\leq\epsilon_{n}.$

Again, the last inequality holds because because we have assumed that
$\epsilon_{n}\geq\nu_{2}+\Gamma_{n}$. Thus, by definition of
$\hat{E}_{{\Delta}}$, we have $(j,l)\notin{\hat{E}_{{\Delta}}}$ or
$(j,l)\in{\hat{E}^{c}_{{\Delta}}}$. This implies that
$E^{c}_{\Delta}\subseteq{\hat{E}^{c}_{{\Delta}}}$, or
$\hat{E}_{{\Delta}}\subseteq{E_{\Delta}}$. Combing with previous conclusion
that $E_{\Delta}\subseteq{\hat{E}_{{\Delta}}}$, the proof is complete.  [2mm]

###  B.5 Proof of Theorem 4

We only need to prove that

$\displaystyle P\left(\lvert S^{M}-\Sigma^{M}\rvert_{\infty}>\delta\right)$
$\displaystyle\leq C_{1}np\exp\\{-C_{2}\Phi(T,L)M^{-(1+\beta)}\delta\\}$
(B.23) $\displaystyle+C_{3}(pM)^{2}\exp\\{-C_{4}nM^{-2(1+\beta)}\delta^{2}\\}$
$\displaystyle+C_{5}npL\exp\left\\{-\frac{C_{6}M^{-2(1+\beta)}\delta^{2}}{\tilde{\psi}_{2}(T,L)}\right\\},$

where $S^{M}$ can be understood as either $S^{X,M}$ or $S^{Y,M}$ and
$\Sigma^{M}$ can be understood as either $\Sigma^{X,M}$ or $\Sigma^{Y,M}$,
with $C_{k}=C^{X}_{k}$ or $C_{k}=C^{Y}_{k}$ for $k=1,2,3,4$ accordingly. To
see that (B.23) implies (43), we first note that (B.23) implies that

$\displaystyle P\left(\lvert
S^{X,M}-\Sigma^{X,M}\rvert_{\infty}\leq\delta\,\text{and}\,\lvert
S^{Y,M}-\Sigma^{Y,M}\rvert_{\infty}\leq\delta\right)$ $\displaystyle\geq$
$\displaystyle 1-P\left(\lvert
S^{X,M}-\Sigma^{X,M}\rvert_{\infty}>\delta\right)-P\left(\lvert
S^{Y,M}-\Sigma^{Y,M}\rvert_{\infty}>\delta\right)$ $\displaystyle\geq$
$\displaystyle
1-C^{X}_{1}pM\exp\\{-C^{X}_{2}\Phi(T,L)M^{-(1+\beta)}\delta\\}-C^{X}_{3}(pM)^{2}\exp\\{-C^{X}_{4}nM^{-2(1+\beta)}\delta^{2}\\}-$
$\displaystyle
C^{Y}_{1}pM\exp\\{-C^{Y}_{2}\Phi(T,L)M^{-(1+\beta)}\delta\\}-C^{Y}_{3}(pM)^{2}\exp\\{-C^{Y}_{4}nM^{-2(1+\beta)}\delta^{2}\\}$
$\displaystyle\geq$ $\displaystyle
1-2\bar{C}_{1}pM\exp\\{-\bar{C}_{2}\Phi(T,L)M^{-(1+\beta)}\delta\\}-2\bar{C}_{3}(pM)^{2}\exp\\{-\bar{C}_{4}nM^{-2(1+\beta)}\delta^{2}\\},$

where $\bar{C}_{k}$ for $k=1,2,3,4$ are defined in Theorem 4. Thus, by letting
the last two terms in the last line of the above equation all to be $\iota/2$,
we then have (43). This way, the rest of the proof will focus on proving
(B.23).

Denote $(j,l)$-th submatrix of $S^{M}$ as $S^{M}_{jl}$, and $(k,m)$-th entry
of $S^{M}_{jl}$ as $\hat{\sigma}_{jl,km}$, thus we have
$S^{M}=(\hat{\sigma}_{jl,km})_{1\leq j,l\leq p,\leq k,m\leq M}$; similarly,
let $\Sigma^{M}=(\sigma_{jl,km})_{1\leq j,l\leq p,\leq k,m\leq M}$. Then, by
the definition of $S^{M}$ and $\Sigma^{M}$, we have

$\displaystyle\hat{\sigma}_{jl,km}$
$\displaystyle=\frac{1}{n}\sum^{n}_{i=1}\hat{a}_{ijk}\hat{a}_{ilm}$
$\displaystyle\sigma_{jl,km}$
$\displaystyle=\mathbb{E}\left[a_{ijk}a_{ilm}\right].$

Note that

$\displaystyle\hat{a}_{ijk}$
$\displaystyle=\langle\hat{g}_{ij},\hat{\phi}_{jk}\rangle$
$\displaystyle=\langle
g_{ij}+\hat{g}_{ij}-g_{ij},\phi_{jk}+\hat{\phi}_{jk}-\phi_{jk}\rangle$
$\displaystyle=\langle g_{ij},\phi_{jk}\rangle+\langle
g_{ij},\hat{\phi}_{jk}-\phi_{jk}\rangle+\langle\hat{g}_{ij}-g_{ij},\phi_{jk}\rangle+\langle\hat{g}_{ij}-g_{ij},\hat{\phi}_{jk}-\phi_{jk}\rangle$
$\displaystyle=a_{ijk}+\langle
g_{ij},\hat{\phi}_{jk}-\phi_{jk}\rangle+\langle\hat{g}_{ij}-g_{ij},\phi_{jk}\rangle+\langle\hat{g}_{ij}-g_{ij},\hat{\phi}_{jk}-\phi_{jk}\rangle.$

Thus, we have

$\displaystyle\hat{\sigma}_{jl,km}-\sigma_{jl,km}$
$\displaystyle=\frac{1}{n}\sum^{n}_{i=1}\left(\hat{a}_{ijk}\hat{a}_{ilm}-\sigma_{jl,km}\right)$
$\displaystyle=\frac{1}{n}\sum^{n}_{i=1}\left[a_{ijk}+\langle
g_{ij},\hat{\phi}_{jk}-\phi_{jk}\rangle+\langle\hat{g}_{ij}-g_{ij},\phi_{jk}\rangle+\langle\hat{g}_{ij}-g_{ij},\hat{\phi}_{jk}-\phi_{jk}\rangle\right]\times$
$\displaystyle\left[a_{ijk}+\langle
g_{ij},\hat{\phi}_{jk}-\phi_{jk}\rangle+\langle\hat{g}_{ij}-g_{ij},\phi_{jk}\rangle+\langle\hat{g}_{ij}-g_{ij},\hat{\phi}_{jk}-\phi_{jk}\rangle\right]-\sigma_{jl,km}$
$\displaystyle=\sum^{16}_{u=1}I_{u},$

where

$\displaystyle I_{1}$
$\displaystyle=\frac{1}{n}\sum^{n}_{i=1}\left(a_{ijk}a_{ilm}-\mathbb{E}(a_{ijk}a_{ilm})\right),$
$\displaystyle I_{2}$
$\displaystyle=\frac{1}{n}\sum^{n}_{i=1}a_{ijk}\langle\hat{g}_{il}-g_{il},\phi_{lm}\rangle,$
$\displaystyle I_{3}$ $\displaystyle=\frac{1}{n}\sum^{n}_{i=1}a_{ijk}\langle
g_{il},\hat{\phi}_{lm}-\phi_{lm}\rangle,$ $\displaystyle I_{4}$
$\displaystyle=\frac{1}{n}\sum^{n}_{i=1}a_{ijk}\langle\hat{g}_{il}-g_{il},\hat{\phi}_{lm}-\phi_{lm}\rangle,$
$\displaystyle I_{5}$
$\displaystyle=\frac{1}{n}\sum^{n}_{i=1}a_{ilm}\langle\hat{g}_{ij}-g_{ij},\phi_{jk}\rangle,$
$\displaystyle I_{6}$
$\displaystyle=\frac{1}{n}\sum^{n}_{i=1}\langle\hat{g}_{ij}-g_{ij},\phi_{jk}\rangle\langle\hat{g}_{il}-g_{il},\phi_{lm}\rangle,$
$\displaystyle I_{7}$
$\displaystyle=\frac{1}{n}\sum^{n}_{i=1}\langle\hat{g}_{ij}-g_{ij},\phi_{jk}\rangle\langle
g_{il},\hat{\phi}_{lm}-\phi_{lm}\rangle,$ $\displaystyle I_{8}$
$\displaystyle=\frac{1}{n}\sum^{n}_{i=1}\langle\hat{g}_{ij}-g_{ij},\phi_{jk}\rangle\langle\hat{g}_{il}-g_{il},\hat{\phi}_{lm}-\phi_{lm}\rangle,$
$\displaystyle I_{9}$ $\displaystyle=\frac{1}{n}\sum^{n}_{i=1}\langle
g_{ij},\hat{\phi}_{jk}-\phi_{jk}\rangle a_{ilm},$ $\displaystyle I_{10}$
$\displaystyle=\frac{1}{n}\sum^{n}_{i=1}\langle
g_{ij},\hat{\phi}_{jk}-\phi_{jk}\rangle\langle\hat{g}_{il}-g_{il},\phi_{lm}\rangle,$
$\displaystyle I_{11}$ $\displaystyle=\frac{1}{n}\sum^{n}_{i=1}\langle
g_{ij},\hat{\phi}_{jk}-\phi_{jk}\rangle\langle
g_{il},\hat{\phi}_{lm}-\phi_{lm}\rangle,$ $\displaystyle I_{12}$
$\displaystyle=\frac{1}{n}\sum^{n}_{i=1}\langle
g_{ij},\hat{\phi}_{jk}-\phi_{jk}\rangle\langle\hat{g}_{il}-g_{il},\hat{\phi}_{lm}-\phi_{lm}\rangle,$
$\displaystyle I_{13}$
$\displaystyle=\frac{1}{n}\sum^{n}_{i=1}\langle\hat{g}_{ij}-g_{ij},\hat{\phi}_{jk}-\phi_{jk}\rangle
a_{ilm},$ $\displaystyle I_{14}$
$\displaystyle=\frac{1}{n}\sum^{n}_{i=1}\langle\hat{g}_{ij}-g_{ij},\hat{\phi}_{jk}-\phi_{jk}\rangle\langle\hat{g}_{il}-g_{il},\phi_{lm}\rangle,$
$\displaystyle I_{15}$
$\displaystyle=\frac{1}{n}\sum^{n}_{i=1}\langle\hat{g}_{ij}-g_{ij},\hat{\phi}_{jk}-\phi_{jk}\rangle\langle
g_{il},\hat{\phi}_{lm}-\phi_{lm}\rangle,$ $\displaystyle I_{16}$
$\displaystyle=\frac{1}{n}\sum^{n}_{i=1}\langle\hat{g}_{ij}-g_{ij},\hat{\phi}_{jk}-\phi_{jk}\rangle\langle\hat{g}_{il}-g_{il},\hat{\phi}_{lm}-\phi_{lm}\rangle.$

Note that $I_{u}$, $u=1,\ldots,16$ depend on $j,l,k,m$. To simplify the
notation, we do not denote this fact explicitly. Thus, for any $0<\delta\leq
1$, when for any $1\leq j,l\leq p$ and $1\leq k,m\leq M$, if $\lvert
I_{u}\rvert\leq\delta/16$, $u=1,\ldots,16$, we will have $\lvert
S^{M}-\Sigma^{M}\rvert_{\infty}\leq\delta$. This way, for the rest of the
paper, we only need to calculate the probability of $\lvert
I_{u}\rvert\leq\delta/16$, $u=1,\ldots,16$, $1\leq j,l\leq p$ and $1\leq
k,m\leq M$.

Before we proceed to calculate the probability, we need a bit more notation.
By Assumption 3 (i), we have constants $d_{1},d_{2}>0$, such that
$\lambda_{jk}\leq d_{1}k^{-\beta}$, $d_{jk}\leq d_{2}k^{1+\beta}$ for any
$j=1,\ldots,p$ and $k\geq 1$. Let $d_{0}=\max\\{1,\sqrt{d_{1}},d_{2}\\}$, let
$\xi_{ijk}=\lambda^{-1/2}_{jk}a_{ijk}$ so that $\xi_{ijk}\sim N(0,1)$ i.i.d.
for $i=1,\ldots,n$, and denote

$\displaystyle\delta_{1}$
$\displaystyle=\frac{\delta}{144d^{2}_{0}M^{1+\beta}\sqrt{3\lambda_{0,\max}}},$
(B.24) $\displaystyle\delta_{2}$
$\displaystyle=9\lambda_{0,\max}\delta_{1}=\frac{\delta}{16d^{2}_{0}M^{1+\beta}\sqrt{3\lambda_{0,\max}}},$

where $\lambda_{0,\max}=\max_{j\in V}\sum^{\infty}_{k=1}\lambda_{jk}$. Recall
that $\hat{K}_{jj}$, $j=1,\ldots,p$ are defined as in (24). We define five
events $A_{1}$-$A_{5}$ as below:

$\displaystyle A_{1}$
$\displaystyle:\;\lVert\hat{g}_{ij}-g_{ij}\rVert\leq\delta_{1},\quad\forall
i=1,\ldots,n\ \forall j=1,\ldots,p,$ (B.25) $\displaystyle A_{2}$
$\displaystyle:\;\lVert\hat{K}_{jj}-K_{jj}\rVert_{\text{HS}}\leq\delta_{2}\quad\forall
j=1,\ldots,p,$ $\displaystyle A_{3}$
$\displaystyle:\;\frac{1}{n}\sum^{n}_{i=1}\xi^{2}_{ijk}\leq\frac{3}{2}\quad\forall
j=1,\ldots,p\ \forall k=1,\ldots,M,$ $\displaystyle A_{4}$
$\displaystyle:\;\frac{1}{n}\sum^{n}_{i=1}\lVert g_{ij}\rVert^{2}\leq
2\lambda_{0,\max}\quad\forall j=1,\ldots,p,$ $\displaystyle A_{5}$
$\displaystyle:\;\lvert\frac{1}{n}\sum^{n}_{i=1}a_{ijk}a_{ilm}-\sigma_{jl,km}\rvert\leq\frac{\delta}{16}\quad\forall
1\leq j,l\leq\ 1\leq k,m\leq M.$

Without loss of generality, we assume that
$\langle\hat{\phi}_{jl},\phi_{jl}\rangle\geq 0$ for any $1\leq j\leq p$ and
$1\leq k\leq M$ (If this is not true, we only need to use $-\phi_{jl}$ to
substitute $\phi_{jl}$). Then, by Lemma 10-Lemma 25, when $A_{1}$-$A_{5}$ hold
simultaneously, we have $\lvert I_{u}\rvert\leq\delta/16$ for all
$u=1,\ldots,16$, $1\leq j,l\leq p$ and $\ 1\leq k,m\leq M$. This way, we have

$\displaystyle P\left(\lvert S^{M}-\Sigma^{M}\rvert_{\infty}\leq\delta\right)$
$\displaystyle\geq P\left(\lvert I_{u}\rvert\leq\delta/16,\;\text{for
all}\;1\leq u\leq 16,1\leq j,l\leq\ 1\leq k,m\leq M\right)$ $\displaystyle\geq
P\left(\bigcap^{5}_{w=1}A_{w}\right).$

Or equivalently,

$P\left(\lvert S^{M}-\Sigma^{M}\rvert_{\infty}>\delta\right)\leq
P\left(\bigcup^{5}_{w=1}\bar{A}_{w}\right)\leq\sum^{5}_{w=1}P\left(\bar{A}_{w}\right),$
(B.26)

where the last inequality follows Boole’s inequality, and $\bar{A}$ means the
complement of $A$. This way, we then only need to give an upper bound for
$P(\bar{A}_{w})$, $w=1,\ldots,5$.

The $P(\bar{A}_{1})$ follows directly from Theorem 5. Note that by Theorem 5
and definition of $\tilde{\psi}_{1}$-$\tilde{\psi}_{4}$, we have

$\displaystyle P(\bar{A}_{1})=$ $\displaystyle
P\left(\lVert\hat{g}_{ij}-g_{ij}\rVert>\delta_{1}\;\exists 1\leq i\leq n,1\leq
j\leq p\right)$ $\displaystyle\leq$ $\displaystyle
2(np)\left\\{\exp\left(-\frac{\delta_{1}^{2}}{72\tilde{\psi}^{2}_{1}(T,L)+6\sqrt{2}\tilde{\psi}_{1}(T,L)\delta_{1}}\right)\right.$
$\displaystyle+$ $\displaystyle
L\exp\left(-\frac{\delta_{1}^{2}}{\tilde{\psi}_{2}(T,L)}\right)$
$\displaystyle+$
$\displaystyle\left.\exp\left(-\frac{\delta_{1}^{2}}{72\lambda_{0,\max}\tilde{\psi}_{3}(L)+6\sqrt{2\lambda_{0,\max}\tilde{\psi}_{3}(L)}\delta_{1}}\right)\right\\}.$

Let $\gamma_{1}=\sqrt{2}/(12\times 144d^{2}_{0}3\sqrt{3\lambda_{0,\max}})$,
and
$\gamma_{3}=1/(72\lambda_{0,\max}\times(144d^{2}_{0}\sqrt{3\lambda_{0,\max}})^{2})$,
then when $\tilde{\psi}_{1}<\gamma_{1}\cdot\delta/M^{1+\beta}$, and
$\tilde{\psi}_{3}<\gamma_{3}\cdot\delta^{2}/M^{2+2\beta}$, we have
$72\tilde{\psi}^{2}_{1}<6\sqrt{2}\tilde{\psi}_{1}\delta_{1}$ and
$72\lambda_{0,\max}\tilde{\psi}_{3}<6\sqrt{2\lambda_{0,\max}\tilde{\psi}_{3}}\delta_{1}$,
which implies that

$\displaystyle P(\bar{A}_{1})$ (B.27) $\displaystyle\leq
2np\left\\{\exp\left(-\frac{\delta_{1}}{12\sqrt{2}\tilde{\psi}_{1}(T,L)}\right)+\exp\left(-\frac{\delta_{1}}{12\sqrt{2\lambda_{0,\max}}\sqrt{\tilde{\psi}_{3}(L)}}\right)+L\exp\left(-\frac{\delta_{1}^{2}}{\tilde{\psi}_{2}(T,L)}\right)\right\\}$
$\displaystyle\overset{(i)}{\leq}2np\left\\{\exp\left(-\frac{\delta_{1}}{12\sqrt{2}}\Phi(T,L)\right)+\exp\left(-\frac{\delta_{1}}{12\sqrt{2\lambda_{0,\max}}}\Phi(T,L)\right)+L\exp\left(-\frac{\delta_{1}^{2}}{\tilde{\psi}_{2}(T,L)}\right)\right\\}$
$\displaystyle\overset{(ii)}{\leq}4np\exp\left(-\frac{\delta_{1}}{12\sqrt{2\lambda_{0,\max}}}\Phi(T,L)\right)+2npL\exp\left(-\frac{\delta_{1}^{2}}{\tilde{\psi}_{2}(T,L)}\right)$
$\displaystyle=4np\exp\left(-\frac{1}{1728\sqrt{6}\lambda_{0,\max}d^{2}_{0}}\cdot\frac{\delta}{M^{1+\beta}}\cdot\Phi(T,L)\right)$
$\displaystyle+2npL\exp\left(-\frac{\delta^{2}}{6228d^{4}_{0}\lambda_{0,\max}M^{2+2\beta}\tilde{\psi}_{2}(T,L)}\right),$

where $(i)$ follows the definition of $\Phi(T,L)$ and $(ii)$ follows the fact
that $\lambda_{0,\max}>1$.

Before we calculate $P(\bar{A}_{2})$, we first compute $P(\bar{A}_{4})$. Note
that by Jensen’s inequality, for any two real values $z_{1},z_{2}$ and any
positive integer $k$, we have

$(z_{1}+z_{2})^{k}\leq\left(|z_{1}|+|z_{2}|\right)^{k}=2^{k}\left(\frac{1}{2}|z_{1}|+\frac{1}{2}|z_{2}|\right)^{k}\leq
2^{k-1}\left(|z_{1}|+|z_{2}|\right),$

where the last line is because Jensen’s inequality with convex function
$\varphi(t)=t^{k}$, $k$ is a positive integer. Since for any $i=1,\ldots,n$
and $j=1,2\dots,p$, we have $\mathbb{E}[\|g_{ij}\|^{2}]=\lambda_{j0}$. Then,
by Jensen’s inequality and Lemma 31, for any $k\geq 2$, we have

$\displaystyle\mathbb{E}\left[\left(\|g_{ij}\|^{2}-\lambda_{j0}\right)^{k}\right]$
$\displaystyle\leq
2^{k-1}\left(\mathbb{E}\left[\|g_{ij}\|^{2k}+\lambda^{k}_{j0}\right]\right)$
$\displaystyle\leq 2^{k-1}\left((2\lambda_{j0})^{k}k!+\lambda^{k}_{j0}\right)$
$\displaystyle\leq(4\lambda_{j0})^{k}k!,$

where the second inequality is because Lemma 31. Thus,

$\sum^{n}_{i=1}\mathbb{E}\left[\left(\|g_{ij}\|^{2}-\lambda_{j0}\right)^{k}\right]\leq\frac{k!}{2}n\times(32\lambda^{2}_{j0})\times(4\lambda_{j0})^{k-2}.$

Then by Lemma 29, for any $\epsilon>0$, we have

$P\left(\left|\frac{1}{n}\sum^{n}_{i=1}\left\|g_{ij}\right\|^{2}-\lambda_{j0}\right|>\epsilon\right)\leq
2\exp\left(-\frac{n\epsilon^{2}}{64\lambda^{2}_{j0}+8\lambda_{j0}\epsilon}\right).$

This way, we further get

$\displaystyle
P\left(\frac{1}{n}\sum^{n}_{i=1}\left\|g_{ij}\right\|^{2}>2\lambda_{0,\max}\right)$
$\displaystyle\leq
P\left(\frac{1}{n}\sum^{n}_{i=1}\left\|g_{ij}\right\|^{2}>2\lambda_{j0}\right)$
$\displaystyle\leq
P\left(\left|\frac{1}{n}\sum^{n}_{i=1}\left\|g_{ij}\right\|^{2}-\lambda_{j0}\right|>\lambda_{j0}\right)$
$\displaystyle\leq 2\exp\left(-\frac{n}{72}\right).$

Since the above inequality holds for any $j=1,\ldots,p$, we then have

$P(\bar{A}_{4})=P\left(\frac{1}{n}\sum^{n}_{i=1}\left\|g_{ij}\right\|^{2}>2\lambda_{0,\max},\;\exists
j=1,\ldots,p\right)\leq 2p\exp\left(-\frac{n}{72}\right).$ (B.28)

For $P(\bar{A}_{2})$, we first let

$\hat{K}^{g}_{jj}(s,t)=\frac{1}{n}\sum^{n}_{i=1}g_{ij}(s)g_{ij}(t),$

for all $j\in V$ and $K_{jj}(s,t)=\mathbb{E}[g_{ij}(s)g_{ij}(t)]$, and also
let

$A^{\prime}_{2}:\;\lVert\hat{K}^{g}_{jj}-K^{g}_{jj}\rVert_{\text{HS}}\leq\delta_{2}\quad\forall
j=1,\ldots,p.$

Note that

$\displaystyle\|\hat{K}^{g}_{jj}(s,t)-K^{g}_{jj}(s,t)\|_{\text{HS}}$
$\displaystyle=\left\|\frac{1}{n}\sum^{n}_{i=1}\left[\hat{g}_{ij}(s)-g_{ij}(s)+g_{ij}(s)\right]\left[\hat{g}_{ij}(t)-g_{ij}(t)+g_{ij}(t)\right]-K^{g}_{jj}(s,t)\right\|_{\text{HS}}$
$\displaystyle\leq\frac{1}{n}\sum^{n}_{i=1}\|\hat{g}_{ij}-g_{ij}\|^{2}+\frac{2}{n}\sum^{n}_{i=1}\|\hat{g}_{ij}-g_{ij}\|\cdot\|g_{ij}\|+\left\|\frac{1}{n}\sum^{n}_{i=1}\left[g_{ij}(s)g_{ij}(t)-K^{g}_{jj}(s,t)\right]\right\|_{\text{HS}}.$

Let

$\displaystyle A_{6}$
$\displaystyle:\;\left\|\frac{1}{n}\sum^{n}_{i=1}\left[g_{ij}(s)g_{ij}(t)-K^{g}_{jj}(s,t)\right]\right\|_{\text{HS}}\leq
4\lambda_{0,\max}\delta_{1},\;\forall j=1,\ldots,p.$

We claim that when $A_{1}\cap A_{4}\cap A_{6}\Rightarrow A^{\prime}_{2}$. To
prove it, note that by Jensen’s inequality, we have

$\frac{1}{n}\sum^{n}_{i=1}\left\|g_{ij}\right\|\leq\sqrt{\frac{1}{n}\sum^{n}_{i=1}\left\|g_{ij}\right\|^{2}},$

thus, when $A_{4}$ holds, we have
$(1/n)\sum^{n}_{i=1}\left\|g_{ij}\right\|\leq\sqrt{2\lambda_{0,\max}}$ for any
$j=1,\ldots,p$. This way, when $A_{1}$, $A_{4}$ and $A_{6}$ hold
simultaneously, we have

$\|\hat{K}^{g}_{jj}(s,t)-K^{g}_{jj}(s,t)\|_{\text{HS}}\leq\delta^{2}_{1}+2\sqrt{2\lambda_{0,\max}}\delta_{1}+4\lambda_{0,\max}\delta_{1}\leq
9\lambda_{0,\max}\delta_{1},$

which is $A_{2}$. This way, we have proved $A_{1}\cap A_{4}\cap
A_{6}\Rightarrow A^{\prime}_{2}$, which implies that
$\bar{A^{\prime}}_{2}\Rightarrow\bar{A}_{1}\cup\bar{A}_{4}\cup\bar{A}_{6}$,
and thus $P(\bar{A^{\prime}}_{2})\leq
P(\bar{A}_{1})+P(\bar{A}_{4})+P(\bar{A}_{6})$. $P(\bar{A}_{1})$ has been given
by (B.27) and $P(\bar{A}_{4})$ has been given by (B.28), thus we only need to
compute $P(\bar{A}_{6})$.

By Lemma 32, for any $j=1,\ldots,p$, we have

$P\left(\left\|\frac{1}{n}\sum^{n}_{i=1}\left[g_{ij}(s)g_{ij}(t)-K^{g}(s,t)\right]\right\|_{\text{HS}}>4\lambda_{0,\max}\delta_{1}\right)\leq
2\exp\left(-\frac{n\delta^{2}_{1}}{6}\right),$

thus

$P(\bar{A}_{6})\leq
2p\exp\left(-\frac{n\delta^{2}_{1}}{6}\right)=2p\exp\left(-\frac{1}{373248d^{4}_{0}\lambda^{2}_{0,\max}}\times
n\frac{\delta^{2}}{M^{2+2\beta}}\right).$ (B.29)

This way, by combining (B.27), (B.28) and (B.29), we have

$\displaystyle P(\bar{A^{\prime}}_{2})\leq$ $\displaystyle
4pM\exp\left(-\frac{1}{1728\sqrt{6}\lambda_{0,\max}d^{2}_{0}}\cdot\frac{\delta}{M^{1+\beta}}\cdot\Phi(T,L)\right)+2p\exp\left(-\frac{n}{72}\right)$
$\displaystyle+$ $\displaystyle
2p\exp\left(-\frac{1}{373248d^{4}_{0}\lambda^{2}_{0,\max}}\times
n\frac{\delta^{2}}{M^{2+2\beta}}\right).$

Finally, since
$\|\hat{K}_{j}j(s,t)-K_{jj}(s,t)\|_{\text{HS}}\leq\|\hat{K}^{X}_{j}j(s,t)-K^{X}_{jj}(s,t)\|_{\text{HS}}+\|\hat{K}^{Y}_{j}j(s,t)-K^{Y}_{jj}(s,t)\|_{\text{HS}}$,
we have $P(\bar{A}_{2})\leq
P(\bar{A^{\prime}}_{X,2})+P(\bar{A^{\prime}}_{Y,2})$, where $A^{\prime}_{X,2}$
and $A^{\prime}_{Y,2}$ are defined similarly as $A^{\prime}_{2}$ with $g$ to
be $X$ and $Y$. Thus, we have

$\displaystyle P(\bar{A}_{2})\leq$ $\displaystyle
8pM\exp\left(-\frac{1}{1728\sqrt{6}\lambda_{0,\max}d^{2}_{0}}\cdot\frac{\delta}{M^{1+\beta}}\cdot\Phi(T,L)\right)+4p\exp\left(-\frac{n}{72}\right)$
$\displaystyle+$ $\displaystyle
4p\exp\left(-\frac{1}{373248d^{4}_{0}\lambda^{2}_{0,\max}}\times
n\frac{\delta^{2}}{M^{2+2\beta}}\right).$

For $P(\bar{A}_{3})$, by Page 28-29 of Boucheron et al. (2013), and note that
$\sum^{n}_{i=1}\xi^{2}_{ijk}\sim\chi^{2}_{n}$ for any $j=1,\ldots,p$ and
$k=1,\ldots,M$, we have that for any $\epsilon>0$, we have

$P\left(\frac{1}{n}\sum^{n}_{i=1}\xi^{2}_{ijk}-1>\epsilon\right)\leq\exp\left(-\frac{n\epsilon^{2}}{4+4\epsilon}\right).$

Thus, by letting $\epsilon=1/2$, we have

$P\left(\frac{1}{n}\sum^{n}_{i=1}\xi^{2}_{ijk}>\frac{3}{2}\right)\leq\exp\left(-\frac{n}{24}\right),$

which implies that

$P(\bar{A}_{3})\leq pM\exp\left(-\frac{n}{24}\right).$ (B.30)

Finally, for $P(\bar{A}_{5})$, we first claim that for any $\epsilon>0$ and
$1\leq j,l\leq p$, $1\leq k,m\leq M$, we have

$P\left(\left|\frac{1}{n}\sum^{n}_{i=1}a_{ijk}a_{ilm}-\sigma_{jl,km}\right|>\epsilon\right)\leq
2\exp\left(-\frac{n\epsilon^{2}}{64d^{2}_{0}+8d_{0}\epsilon}\right).$

We now prove this claim. Note that

$\displaystyle\mathbb{E}\left[\left(a_{ijk}a_{ilm}-\mathbb{E}(a_{ijk}a_{ilm})\right)^{k}\right]$
$\displaystyle=\lambda^{k/2}_{jk}\lambda^{k/2}_{lm}\mathbb{E}\left[\left(\xi_{ijk}\xi_{ilm}-\mathbb{E}(\xi_{ijk}\xi_{ilm})\right)^{k}\right]$
$\displaystyle\leq
d^{k}_{0}\mathbb{E}\left[\left(\xi_{ijk}\xi_{ilm}-\mathbb{E}(\xi_{ijk}\xi_{ilm})\right)^{k}\right],$

and

$\displaystyle\mathbb{E}\left[\left(\xi_{ijk}\xi_{ilm}-\mathbb{E}(\xi_{ijk}\xi_{ilm})\right)^{k}\right]$
$\displaystyle\leq
2^{k-1}\left(\mathbb{E}\left[|\xi_{ijk}\xi_{ilm}|^{k}\right]+|\mathbb{E}(\xi_{ijk}\xi_{ilm})|^{k}\right)$
$\displaystyle\leq 2^{k-1}\left(\mathbb{E}[\xi^{2k}_{ij1}]+1\right)$
$\displaystyle\leq 2^{k-1}(2^{k}k!+1)$ $\displaystyle\leq 4^{k}k!,$

thus

$\mathbb{E}\left[\left(a_{ijk}a_{ilm}-\mathbb{E}(a_{ijk}a_{ilm})\right)^{k}\right]\leq(4d_{0})^{k}k!.$

The claim then follows directly from Lemma 29. By letting
$\epsilon=\delta/16$,

$P\left(\left|\frac{1}{n}\sum^{n}_{i=1}a_{ijk}a_{ilm}-\sigma_{jl,km}\right|>\frac{\delta}{16}\right)\leq
2\exp\left(-\frac{n\delta^{2}}{16^{2}\times 64\times
d^{2}_{0}+128d_{0}\delta}\right)\leq
2\exp\left(-\frac{n\delta^{2}}{16512d^{2}_{0}}\right)$

holds for any $1\leq j,l\leq p$ and $1\leq k,m\leq M$, which further implies
that

$P\left(\bar{A}_{5}\right)\leq
2(pM)^{2}\exp\left(-\frac{n\delta^{2}}{16512d^{2}_{0}}\right).$ (B.31)

Let $C_{1}=12$, $C_{2}=1/(1728\sqrt{6}\lambda_{0,\max})$, $C_{3}=9$,
$C_{4}=1/(373248d^{4}_{0}\lambda^{2}_{0,\max})$, $C_{5}=2$, and
$C_{6}=1/(6228d^{4}_{0}\lambda_{0,\max})$, then the final result follows by
combining (B.27)-(B.31).

##  Appendix C More Theorems

In this section, we introduce more theorems along with their proofs.

###  C.1 Theorem 5 and Its Proof

In this section, we give a non-asymptotic error bound for our basis expansion
estimated function. This theorem is used in proving Theorem 4.

For a random function $g(t)$, where $t\in\mathcal{T}$, a closed interval of
real line, and lying in a separable Hilbert space $\mathbb{H}$, we have noisy
discrete observations at time points $t_{1},t_{2},\dots,t_{T}$ generated from
the model below:

$h_{k}=g(t_{k})+\epsilon_{k},$ (C.1)

where $\epsilon_{k}\overset{\text{i.i.d.}}{\sim}N(0,\sigma^{2}_{0})$ for
$k=1,\ldots,T$. Let $b(t)=(b_{1}(t),b_{2}(t),\dots,b_{L}(t))^{\top}$ be basis
function vector. We use basis expansion to get
$\hat{g}(t)=\hat{\beta}^{\top}b(t)$, the estimator of $g(t)$, where
$\hat{\beta}\in\mathbb{R}^{L}$ is obtained by minimizing the least square
loss:

$\hat{\beta}=\operatorname*{arg\,min}_{\beta\in\mathbb{R}^{L}}\sum^{T}_{k=1}\left(\beta^{\top}b(t_{k})-h_{k}\right)^{2}.$
(C.2)

We define the design matrix $B$ as

$B=\left[\begin{matrix}b_{1}(t_{1})&\cdots&b_{L}(t_{1})\\\
\vdots&\ddots&\vdots\\\
b_{1}(t_{T})&\cdots&b_{L}(t_{T})\end{matrix}\right]\in\mathbb{R}^{T\times L},$
(C.3)

so that

$\hat{\beta}=\left(B^{\top}B\right)^{-1}B^{\top}h,$ (C.4)

where $h=(h_{1},h_{2},\dots,h_{T})^{\top}\in\mathbb{R}^{T}$.

We assume that $g(t)=\sum^{\infty}_{m=1}\beta^{*}_{m}b_{m}(t)$, and we can
decompose $g(t)$ as $g=g^{\shortparallel}+g^{\bot}$, where
$g^{\shortparallel}\in{\rm Span}(b)$ and $g^{\bot}\in{\rm Span}(b)^{\bot}$.
Let $\lambda_{0}\coloneqq\mathbb{E}[\|g\|^{2}]$ and
$\lambda^{\bot}_{0}\coloneqq\mathbb{E}[\|g^{\bot}\|^{2}]$. Then it is easy to
check that $\lambda_{0}=\sum^{\infty}_{m=1}\mathbb{E}[(\beta^{*}_{m})^{2}]$
and $\lambda^{\bot}_{0}=\sum^{\infty}_{m>L}\mathbb{E}[(\beta^{*}_{m})^{2}]$.

We assume that the basis functions $\\{b_{l}(t)\\}^{\infty}_{l=1}$ compose a
complete orthonormal system (CONS) of $\mathbb{H}$, that is, $\overline{{\rm
Span}\left(\\{b_{l}\\}^{\infty}_{l=1}\right)}=\mathbb{H}$ (see Definition
2.4.11 of Hsing and Eubank (2015)), and have continuous derivative functions
with

$D_{0,b}\coloneqq\sup_{l\geq 1}\sup_{t\in\mathcal{T}}\lvert
b_{l}(t)\rvert<\infty,\qquad D_{1,b}(l)\coloneqq\sup_{t\in\mathcal{T}}\lvert
b^{\prime}_{l}(t)\rvert<\infty,\qquad D_{1,b,L}\coloneqq\max_{1\leq l\leq
L}D_{1,b}(l).$ (C.5)

We further assume that the observation time points $\\{t_{k}:1\leq k\leq T\\}$
satisfy

$\max_{1\leq k\leq
T+1}\left|\frac{t_{k}-t_{(k-1)}}{\lvert\mathcal{T}\rvert}-\frac{1}{T}\right|\leq\frac{\zeta_{0}}{T^{2}},$
(C.6)

where $t_{0}$ and $t_{(T+1)}$ are endpoints of $\mathcal{T}$ and $\zeta_{0}$
is a positive constant. Besides, we assume that
$\sum^{\infty}_{m=1}\mathbb{E}\left[(\beta^{*}_{m})^{2}\right]D^{2}_{1,b}(m)<\infty$,
we then define

$\psi_{4}(L)=\sum_{m>L}\mathbb{E}\left[(\beta^{*}_{m})^{2}\right]D^{2}_{1,b}(m).$

Let

$\displaystyle\psi_{1}(T,L)$
$\displaystyle=\frac{\sigma_{0}L}{\sqrt{\lambda_{\min}\left(B^{\top}B\right)}},\qquad\psi_{3}(L)=\lambda^{\bot}_{0}/\lambda_{0},$

and

$\displaystyle\psi_{2}(T,L)$
$\displaystyle=\frac{1}{(\lambda^{B}_{\min})^{2}}\left(18\lambda_{0}\left[D^{2}_{0,b}(\zeta_{0}+1)^{4}|\mathcal{T}|^{2}D^{2}_{1,b,L}+2D^{4}_{0,b}(2\zeta_{0}+1)^{2}\right]L^{2}\psi_{3}(L)\right.$
$\displaystyle\left.\qquad\qquad+D^{2}_{0,b}(\zeta_{0}+1)^{4}|\mathcal{T}|^{2}L^{2}\psi_{4}(L)\right),$

We then have the following theorem.

###### Theorem 5

For any $\delta>0$, we have

$P\left(\lVert g-\hat{g}\rVert>\delta\right)\leq
2\exp\left(-\frac{\delta^{2}}{72\psi^{2}_{1}(T,L)+6\sqrt{2}\psi_{1}(T,L)\delta}\right)+L\exp\left(-\frac{\delta^{2}}{\psi_{2}(T,L)}\right)\\\
+2\exp\left(-\frac{\delta^{2}}{72\lambda_{0}\psi_{3}(L)+6\sqrt{2\lambda_{0}}\sqrt{\psi_{3}(L)}\delta}\right).$
(C.7)

Proof  Throughout the proof, we often use the technique to first treat $g$ as
a fixed function, that is, we consider probability conditioned on $g$, so the
only randomness comes from $\epsilon_{k}$, $k=1,\ldots,T$. We will then
include the randomness from $g$. Note that since $\epsilon_{k}$ is independent
of $g$, thus the conditional distribution of $\epsilon_{k}$ is the same with
unconditional distribution.

For a fixed $g$, since $\overline{{\rm
Span}\left(\\{b_{l}\\}^{\infty}_{l=1}\right)}=\mathbb{H}$, we can assume that
$g(t)=\sum^{\infty}_{l=1}\beta^{*}_{l}b_{l}(t)$ where $\beta^{*}_{l}=\langle
g,b_{l}\rangle=\int_{\mathcal{T}}g(t)b_{l}(t)dt$. Let
$\beta^{*}=(\beta^{*}_{1},\cdots,\beta^{*}_{L})^{\top}\in\mathbb{R}^{L}$, we
then have
$g^{\shortparallel}(t)=(\beta^{*})^{\top}b(t)=\sum^{L}_{l=1}\beta^{*}_{l}b_{l}(t)$
and $g^{\bot}(t)=\sum_{l>L}\beta^{*}_{l}b_{l}(t)$. Thus, we have

$h_{k}=g(t_{k})+\epsilon_{k}=(\beta^{*})^{\top}b(t_{k})+g^{\bot}(t_{k})+\epsilon_{k}.$

Let
$h^{\bot}=\left(g^{\bot}(t_{1}),g^{\bot}(t_{2}),\dots,g^{\bot}(t_{T})\right)^{\top}$,
$\epsilon=\left(\epsilon_{1},\epsilon_{2},\dots,\epsilon_{T}\right)^{\top}$,
we then have

$h=B\beta^{*}+h^{\bot}+\epsilon.$

Thus,

$\mathbb{E}(\mathbb{\hat{\beta}})=\beta^{*}+\left(B^{\top}B\right)^{-1}B^{\top}h^{\bot},$

and

$\displaystyle\hat{g}(t)-g(t)$
$\displaystyle=\hat{g}(t)-g^{\shortparallel}(t)-g^{\bot}(t)$
$\displaystyle=\hat{g}(t)-(\beta^{*})^{\top}b(t)-g^{\bot}(t)$
$\displaystyle=\left(\hat{\beta}-\mathbb{E}(\hat{\beta})\right)^{\top}b(t)+\left(\left(B^{\top}B\right)^{-1}B^{\top}h^{\bot}\right)^{\top}b(t)-g^{\bot}(t).$

By Lemma 26, we then have

$\displaystyle\lVert\hat{g}-g\rVert$
$\displaystyle\leq\lVert\left(\hat{\beta}-\mathbb{E}(\hat{\beta})\right)^{\top}b(t)\rVert+\lVert\left(\left(B^{\top}B\right)^{-1}B^{\top}h^{\bot}\right)^{\top}b(t)\rVert+\lVert
g^{\bot}\rVert$
$\displaystyle\leq\lvert\hat{\beta}-\mathbb{E}(\hat{\beta})\rvert_{2}\times\lVert
b\rVert_{\mathcal{L}^{2},2}+\lvert\left(B^{\top}B\right)^{-1}B^{\top}h^{\bot}\rvert_{2}\times\lVert
b\rVert_{\mathcal{L}^{2},2}+\lVert g^{\bot}\rVert$
$\displaystyle\leq\lvert\hat{\beta}-\mathbb{E}(\hat{\beta})\rvert_{2}\times\lVert
b\rVert_{\mathcal{L}^{2},2}+\frac{1}{\lambda_{\min}(B^{\top}B)}\times\left\lvert
B^{\top}h^{\bot}\right\rvert_{2}\times\lVert
b\rVert_{\mathcal{L}^{2},2}+\lVert g^{\bot}\rVert.$

Let

$\displaystyle J_{1}$
$\displaystyle=\lvert\hat{\beta}-\mathbb{E}(\hat{\beta})\rvert_{2}\times\lVert_{2}b\rVert_{\mathcal{L}^{2},2}$
(C.8) $\displaystyle J_{2}$
$\displaystyle=\frac{1}{\lambda_{\min}(B^{\top}B)}\times\lvert
B^{\top}h^{\bot}\rvert_{2}\times\lVert b\rVert_{\mathcal{L}^{2},2}$
$\displaystyle J_{3}$ $\displaystyle=\lVert g^{\bot}\rVert,$

where $\lvert\mathcal{T}\rvert$ denotes the length of the interval, then

$\lVert\hat{g}-g\rVert\leq J_{1}+J_{2}+J_{3}.$ (C.9)

Since this equation holds for any $g\in\mathbb{H}$, thus when we include the
randomness from $g$, the above equation holds with probability one. We then
bound $J_{1}$, $J_{2}$ and $J_{3}$ individually.

First, for $J_{1}$, recall that $\lVert b\rVert_{\mathcal{L}^{2},2}=\sqrt{L}$
and $\psi_{1}(T,L)=\sigma_{0}\lVert
b\rVert_{\mathcal{L}^{2},2}\sqrt{L}/\sqrt{\lambda_{\min}\left(B^{\top}B\right)}$,
then for any $\delta>0$, we claim that

$P\left(J_{1}>\delta\right)\leq
2\exp\left(-\frac{\delta^{2}}{8\psi^{2}_{1}(T,L)+2\sqrt{2}\psi_{1}(T,L)\delta}\right).$
(C.10)

To prove this result, we first treat $g$ as fixed, then note that by standard
linear regression theory, we have

$\hat{\beta}\sim
N_{L}\left(\mathbb{E}(\hat{\beta}),\sigma^{2}_{0}\left(B^{\top}B\right)^{-1}\right).$

Thus,

$\frac{1}{\sigma_{0}}\left(B^{\top}B\right)^{1/2}\left(\hat{\beta}-\mathbb{E}(\hat{\beta})\right)\sim
N_{L}\left(0,I_{L}\right)$

Since

$\displaystyle J_{1}$
$\displaystyle=\lvert\hat{\beta}-\mathbb{E}(\hat{\beta})\rvert_{2}\times\lVert
b\rVert_{\mathcal{L}^{2},2}$
$\displaystyle=\lvert\left(B^{\top}B\right)^{-1/2}\left(B^{\top}B\right)^{1/2}\left(\hat{\beta}-\mathbb{E}(\hat{\beta})\right)\rvert_{2}\times\lVert
b\rVert_{\mathcal{L}^{2},2}$
$\displaystyle\leq\frac{1}{\sqrt{\lambda_{\min}\left(B^{\top}B\right)}}\lvert\left(B^{\top}B\right)^{1/2}\left(\hat{\beta}-\mathbb{E}(\hat{\beta})\right)\rvert_{2}\times\lVert
b\rVert_{\mathcal{L}^{2},2}$ $\displaystyle=\frac{\sigma_{0}\lVert
b\rVert_{\mathcal{L}^{2},2}}{\sqrt{\lambda_{\min}\left(B^{\top}B\right)}}\lvert\frac{1}{\sigma_{0}}\left(B^{\top}B\right)^{1/2}\left(\hat{\beta}-\mathbb{E}(\hat{\beta})\right)\rvert_{2},$

we have

$\displaystyle P(J_{1}>\delta)$ $\displaystyle\leq
P\left(\frac{\sigma_{0}\lVert
b\rVert_{\mathcal{L}^{2},2}}{\sqrt{\lambda_{\min}\left(B^{\top}B\right)}}\lvert\frac{1}{\sigma_{0}}\left(B^{\top}B\right)^{1/2}\left(\hat{\beta}-\mathbb{E}(\hat{\beta})\right)\rvert_{2}>\delta\right)$
$\displaystyle=P\left(\lvert\frac{1}{\sigma_{0}}\left(B^{\top}B\right)^{1/2}\left(\hat{\beta}-\mathbb{E}(\hat{\beta})\right)\rvert_{2}>\frac{\delta}{\sigma_{0}\lVert
b\rVert_{\mathcal{L}^{2},2}/\sqrt{\lambda_{\min}\left(B^{\top}B\right)}}\right)$
$\displaystyle\overset{(i)}{\leq}2\exp\left(-\frac{\left(\delta/\left(\sigma_{0}\lVert
b\rVert_{\mathcal{L}^{2},2}/\sqrt{\lambda_{\min}\left(B^{\top}B\right)}\right)\right)^{2}}{8L+2\sqrt{2}\left(\left(\delta/\left(\sigma_{0}\lVert
b\rVert_{\mathcal{L}^{2},2}/\sqrt{\lambda_{\min}\left(B^{\top}B\right)}\right)\right)\right)}\right)$
$\displaystyle=2\exp\left(-\frac{\delta^{2}}{8\psi^{2}_{1}(T,L)+2\sqrt{2}\psi_{1}(T,L)\delta}\right),$

where $(i)$ follows Lemma 28. Now if we treat $g$ as random, we only need to
note that

$\displaystyle P\left(J_{1}>\delta\right)$
$\displaystyle=\mathbb{E}_{g}\left[P\left(J_{1}>\delta_{2}|g\right)\right]$
$\displaystyle=\mathbb{E}_{g}\left[2\exp\left(-\frac{\delta^{2}}{8\psi^{2}_{1}(T,L)+2\sqrt{2}\psi_{1}(T,L)\delta}\right)\right]$
$\displaystyle=2\exp\left(-\frac{\delta^{2}}{8\psi^{2}_{1}(T,L)+2\sqrt{2}\psi_{1}(T,L)\delta}\right).$

Next, for $J_{2}$, we claim that for any $\delta>0$, we have

$\mathbb{P}\left(J_{2}>\delta\right)\leq
L\exp\left(-\frac{9\delta^{2}}{\psi_{2}(T,L)}\right).$ (C.11)

We use $(B^{\top}h^{\bot})_{l}$ to denote the $l$-th element of vector
$B^{\top}h^{\bot}$, then we have

$(B^{\top}h^{\bot})_{l}=\sum^{T}_{k=1}b_{l}(t_{k})g^{\bot}(t_{k})=\sum_{m>L}\beta^{*}_{m}\sum^{T}_{k=1}b_{l}(t_{k})b_{m}(t_{k}).$

Since $g$ is a Gaussian random function with mean zero, we then have
$(B^{\top}h^{\bot})_{l}$ to be a Gaussian random variable. Besides, we have
$\mathbb{E}\left[(B^{\top}h^{\bot})_{l}\right]=0$ and

$\mathbb{E}\left[(B^{\top}h^{\bot})^{2}_{l}\right]=\sum_{m>L}\mathbb{E}\left[\beta^{*2}_{m}\right]\left(\sum^{T}_{k=1}b_{l}(t_{k})b_{m}(t_{k})\right)^{2}$
(C.12)

By definition of $D_{0,b}$, $D_{1,b}(\cdot)$, for any $l<m$, we have that
$\sup_{t\in\mathcal{T}}(b_{l}(t)b_{m}(t))\leq D^{2}_{0,b}$, and
$\sup_{t\in\mathcal{T}}(b_{l}(t)b_{m}(t))^{\prime}=\sup_{t\in\mathcal{T}}\\{b^{\prime}_{l}(t)b_{m}(t)+b_{l}(t)b^{\prime}_{m}(t)\\}\leq
D_{0,b}(D_{1,b}(l)+D_{1,b}(m))$. Note that
$\int_{\mathcal{T}}b_{l}(t)b_{m}(t)dt=0$ for any $l<m$, then by Lemma 30, we
have

$\displaystyle\left|\frac{1}{T}\sum^{T}_{k=1}b_{l}(t_{k})b_{m}(t_{k})\right|$
$\displaystyle=$
$\displaystyle\left|\frac{1}{T}\sum^{T}_{k=1}b_{l}(t_{k})b_{m}(t_{k})-\frac{1}{|\mathcal{T}|}\int_{\mathcal{T}}b_{l}(t)b_{m}(t)dt\right|$
$\displaystyle\leq$
$\displaystyle\frac{D_{0,b}(D_{1,b}(l)+D_{1,b}(m))(\zeta_{0}+1)^{2}|\mathcal{T}|/2+D^{2}_{0,b}(2\zeta_{0}+1)}{T}$

for all $1\leq l<m<\infty$, which implies that

$\left|\sum^{T}_{k=1}b_{l}(t_{k})b_{m}(t_{k})\right|\leq\frac{1}{2}D_{0,b}(\zeta_{0}+1)^{2}|\mathcal{T}|(D_{1,b}(l)+D_{1,b}(m))+D^{2}_{0,b}(2\zeta_{0}+1).$

Then we have

$\displaystyle\left(\sum^{T}_{k=1}b_{l}(t_{k})b_{m}(t_{k})\right)^{2}$
$\displaystyle\leq\left(\frac{1}{2}D_{0,b}(\zeta_{0}+1)^{2}|\mathcal{T}|(D_{1,b}(l)+D_{1,b}(m))+D^{2}_{0,b}(2\zeta_{0}+1)\right)^{2}$
$\displaystyle\leq\frac{1}{2}D^{2}_{0,b}(\zeta_{0}+1)^{4}|\mathcal{T}|^{2}(D_{1,b}(l)+D_{1,b}(m))^{2}+2D^{4}_{0,b}(2\zeta_{0}+1)^{2}$
$\displaystyle\leq
D^{2}_{0,b}(\zeta_{0}+1)^{4}|\mathcal{T}|^{2}(D^{2}_{1,b}(l)+D^{2}_{1,b}(m))+2D^{4}_{0,b}(2\zeta_{0}+1)^{2}.$

By (C.12), we then have

$\displaystyle\mathbb{E}\left[(B^{\top}h^{\bot})^{2}_{l}\right]$
$\displaystyle\leq\left[D^{2}_{0,b}(\zeta_{0}+1)^{4}|\mathcal{T}|^{2}D^{2}_{1,b}(l)+2D^{4}_{0,b}(2\zeta_{0}+1)^{2}\right]\sum_{m>L}\mathbb{E}\left[\beta^{*2}_{m}\right]$
$\displaystyle+D^{2}_{0,b}(\zeta_{0}+1)^{4}|\mathcal{T}|^{2}\sum_{m>L}\mathbb{E}\left[\beta^{*2}_{m}\right]D^{2}_{1,b}(m)$
$\displaystyle\leq\left[D^{2}_{0,b}(\zeta_{0}+1)^{4}|\mathcal{T}|^{2}D^{2}_{1,b}(l)+2D^{4}_{0,b}(2\zeta_{0}+1)^{2}\right]\lambda^{\bot}_{0}+D^{2}_{0,b}(\zeta_{0}+1)^{4}|\mathcal{T}|^{2}\psi_{4}(L)$
$\displaystyle\leq\left[D^{2}_{0,b}(\zeta_{0}+1)^{4}|\mathcal{T}|^{2}D^{2}_{1,b,L}+2D^{4}_{0,b}(2\zeta_{0}+1)^{2}\right]\lambda^{\bot}_{0}+D^{2}_{0,b}(\zeta_{0}+1)^{4}|\mathcal{T}|^{2}\psi_{4}(L)$
$\displaystyle=\lambda_{0}\left[D^{2}_{0,b}(\zeta_{0}+1)^{4}|\mathcal{T}|^{2}D^{2}_{1,b,L}+2D^{4}_{0,b}(2\zeta_{0}+1)^{2}\right]\psi_{3}(L)+D^{2}_{0,b}(\zeta_{0}+1)^{4}|\mathcal{T}|^{2}\psi_{4}(L)$

Thus, by tail bound of Gaussian random variable (Section 2.1.2 of Wainwright
(2019)), we have

$\displaystyle\mathbb{P}\left((B^{\top}h^{\bot})_{l}>\delta\right)\leq$
$\displaystyle\exp\left(-\frac{\delta^{2}}{2\lambda_{0}\left[D^{2}_{0,b}(\zeta_{0}+1)^{4}|\mathcal{T}|^{2}D^{2}_{1,b,L}+2D^{4}_{0,b}(2\zeta_{0}+1)^{2}\right]\psi_{3}(L)+D^{2}_{0,b}(\zeta_{0}+1)^{4}|\mathcal{T}|^{2}\psi_{4}(L)}\right).$

Recall that

$\displaystyle\psi_{2}(T,L)$
$\displaystyle=\frac{1}{(\lambda^{B}_{\min})^{2}}\left(18\lambda_{0}\left[D^{2}_{0,b}(\zeta_{0}+1)^{4}|\mathcal{T}|^{2}D^{2}_{1,b,L}+2D^{4}_{0,b}(2\zeta_{0}+1)^{2}\right]L^{2}\psi_{3}(L)\right.$
$\displaystyle\left.\qquad\qquad+D^{2}_{0,b}(\zeta_{0}+1)^{4}|\mathcal{T}|^{2}L^{2}\psi_{4}(L)\right),$

and note that $\|b\|_{\mathcal{L}^{2},2}=\sqrt{L}$, then we have

$\displaystyle\mathbb{P}\left(J_{2}>\delta\right)$
$\displaystyle\leq\mathbb{P}\left(\lvert
B^{\top}h^{\bot}\rvert_{2}>\frac{\lambda^{B}_{\min}\delta}{\sqrt{L}}\right)\leq\mathbb{P}\left(\max_{1\leq
l\leq L}(B^{\top}h^{\bot})_{l}>\frac{\lambda^{B}_{\min}\delta}{L}\right)$
(C.13) $\displaystyle\leq
L\exp\left(-\frac{9\delta^{2}}{\psi_{2}(T,L)}\right).$

Finally, for $J_{3}$, by Lemma 31 and definition of $\psi_{3}(L)$, we have

$\mathbb{E}\left[\|g^{\bot}\|^{2k}\right]\leq(2\lambda_{0}\psi_{3}(L))^{k}k!.$

This way, by Jensesn’s inequality, we have

$\mathbb{E}\left[\|g^{\bot}\|^{k}\right]=\mathbb{E}\left[\sqrt{\|g^{\bot}\|^{2k}}\right]\leq\sqrt{\mathbb{E}\left[\|g^{\bot}\|^{2k}\right]}\leq\left(\sqrt{2\lambda_{0}\psi_{3}(L)}\right)^{k}k!.$

Thus, by Lemma 29, we have

$P\left(J_{3}>\delta\right)=P\left(\|g^{\bot}\|>\delta\right)\leq
2\exp\left(-\frac{\delta^{2}}{8\lambda_{0}\psi_{3}(L)+2\sqrt{2\lambda_{0}}\sqrt{\psi_{3}(L)}\delta}\right).$
(C.14)

The final result then follows (C.10), (C.13) and (C.14), and the fact that

$\mathbb{P}\left(J_{1}+J_{2}+J_{3}>\delta\right)\leq\mathbb{P}\left(J_{1}>\delta/3\right)+\mathbb{P}\left(J_{2}>\delta/3\right)+\mathbb{P}\left(J_{3}>\delta/3\right).$

[2mm]

##  Appendix D Lemmas and their proofs

In this section, we introduce some useful lemmas along with their proofs.

###### Lemma 5

Let $\sigma_{\max}=\max\\{|\Sigma^{X,M}|_{\infty},\
|\Sigma^{Y,M}|_{\infty}\\}$. Suppose that

$|S^{X,M}-\Sigma^{X,M}|_{\infty}\leq\delta,\qquad|S^{Y,M}-\Sigma^{Y,M}|_{\infty}\leq\delta,$
(D.1)

for some $\delta\geq 0$. Then

$\displaystyle|(S^{Y,M}\otimes{S^{X,M}})-(\Sigma^{Y,M}\otimes{\Sigma^{X,M}})|_{\infty}\leq\delta^{2}+2\delta\sigma_{\max},$
(D.2) and
$\displaystyle|\operatorname{vec}{(S^{Y,M}-S^{X,M})}-\operatorname{vec}{(\Sigma^{Y,M}-\Sigma^{X,M})}|_{\infty}\leq
2\delta.$ (D.3)

Proof  Note that for any $(j,l),(j^{\prime},l^{\prime})\in V^{2}$ and $1\leq
k,k^{\prime},m,m^{\prime}\leq M$, by (D.1), we have

$\displaystyle\left|S^{X,M}_{jl,km}S^{Y,M}_{j^{\prime}l^{\prime},k^{\prime}m^{\prime}}-\Sigma^{X,M}_{jl,km}\Sigma^{Y,M}_{j^{\prime}l^{\prime},k^{\prime}m^{\prime}}\right|$
$\displaystyle\leq\left|S^{X,M}_{jl,km}-\Sigma^{X,M}_{jl,km}\right|\cdot\left|S^{Y,M}_{j^{\prime}l^{\prime},k^{\prime}m^{\prime}}-\Sigma^{Y,M}_{j^{\prime}l^{\prime},k^{\prime}m^{\prime}}\right|+\left|\Sigma^{X,M}_{jl,km}\right|\cdot\left|S^{Y,M}_{j^{\prime}l^{\prime},k^{\prime}m^{\prime}}-\Sigma^{Y,M}_{j^{\prime}l^{\prime},k^{\prime}m^{\prime}}\right|$
$\displaystyle\quad+\left|\Sigma^{Y,M}_{j^{\prime}l^{\prime},k^{\prime}m^{\prime}}\right|\cdot\left|S^{X,M}_{jl,km}-\Sigma^{X,M}_{jl,km}\right|$
$\displaystyle\leq\left|S^{X,M}-\Sigma^{X,M}\right|_{\infty}\left|S^{Y,M}-\Sigma^{Y,M}\right|_{\infty}+\sigma_{\max}\left|S^{Y,M}-\Sigma^{Y,M}\right|_{\infty}+\sigma_{\max}\left|S^{X,M}-\Sigma^{X,M}\right|_{\infty}$
$\displaystyle\leq\delta^{2}+2\delta\sigma_{\max}.$

For (D.3), note that

$\displaystyle\left|\operatorname{vec}{(S^{Y,M}-S^{X,M})}-\operatorname{vec}{(\Sigma^{Y,M}-\Sigma^{X,M})}\right|_{\infty}$
$\displaystyle=\left|(S^{X,M}-\Sigma^{X,M})-(S^{Y,M}-\Sigma^{Y,M})\right|_{\infty}$
$\displaystyle\leq|S^{X,M}-\Sigma^{X,M}|_{\infty}+|S^{Y,M}-\Sigma^{Y,M}|_{\infty}$
$\displaystyle\leq 2\delta.$

[2mm]

###### Lemma 6

For $Z^{(1)},Z^{(2)},A^{(1)},A^{(2)}\in\mathbb{R}^{M\times M}$. Denote the
solution of

$\operatorname*{arg\,min}_{\\{Z^{(1)},Z^{(2)}\\}}\;\frac{1}{2}\sum^{2}_{q=1}\|Z^{(q)}-A^{(q)}\|^{2}_{\text{F}}+\lambda\|Z^{(1)}-Z^{(2)}\|_{\text{F}}$
(D.4)

as $\\{\hat{Z}^{(1)},\hat{Z}^{(2)}\\}$, where $\lambda>0$ is a constant. Then
when $\|A^{(1)}-A^{(2)}\|_{\text{F}}\leq 2\lambda$, we have

$\hat{Z}^{(1)}=\hat{Z}^{(2)}=\frac{1}{2}\left(A^{(1)}+A^{(2)}\right),$ (D.5)

and when $\|A^{(1)}-A^{(2)}\|_{\text{F}}>2\lambda$, we have

$\displaystyle\hat{Z}^{(1)}=A^{(1)}-\frac{\lambda}{\|A^{(1)}-A^{(2)}\|_{\text{F}}}\left(A^{(1)}-A^{(2)}\right)$
(D.6)
$\displaystyle\hat{Z}^{(2)}=A^{(2)}+\frac{\lambda}{\|A^{(1)}-A^{(2)}\|_{\text{F}}}\left(A^{(1)}-A^{(2)}\right).$

Proof  The subdifferential of the objective function in (D.4) is

$G^{(1)}(Z^{(1)},Z^{(2)})\coloneq\partial_{Z^{(1)}}=Z^{(1)}-A^{(1)}+\lambda
T(Z^{(1)},Z^{(2)}),$ (D.7)
$G^{(2)}(Z^{(1)},Z^{(2)})\coloneq\partial_{Z^{(2)}}=Z^{(2)}-A^{(2)}-\lambda
T(Z^{(1)},Z^{(2)}),$ (D.8)

where

$T(Z^{(1)},Z^{(2)})=\left\\{\begin{aligned}
&\frac{Z^{(1)}-Z^{(2)}}{\|Z^{(1)}-Z^{(2)}\|_{\text{F}}}\quad\text{if}\;Z^{(1)}\neq
Z^{(2)}\\\ &\left\\{T\in\mathbb{R}^{M\times M}:\|T\|_{\text{F}}\leq
1\right\\}\quad\text{if}\;Z^{(1)}=Z^{(2)}\end{aligned}\right..$ (D.9)

The optimal condition is:

$0\in G^{(q)}(Z^{(1)},Z^{(2)})\quad q=1,2.$ (D.10)

Claim $\hat{Z}^{(1)}\neq\hat{Z}^{(2)}$ if and only if
$\|A^{(1)}-A^{(2)}\|_{\text{F}}>2\lambda$.

We first prove the necessaity, that is, when $\hat{Z}^{(1)}\neq\hat{Z}^{(2)}$,
we prove that $\|A^{(1)}-A^{(2)}\|_{\text{F}}>2\lambda$. By (D.7)-(D.10), we
have

$\hat{Z}^{(1)}-\hat{Z}^{(2)}-\left(A^{(1)}-A^{(2)}\right)-2\lambda\frac{\hat{Z}^{(1)}-\hat{Z}^{(2)}}{\|\hat{Z}^{(1)}-\hat{Z}^{(2)}\|_{\text{F}}}=0,$

which implies that

$\|A^{(1)}-A^{(2)}\|_{\text{F}}=2\lambda+\|\hat{Z}^{(1)}-\hat{Z}^{(2)}\|_{\text{F}}>2\lambda.$

We then prove the sufficiency, that is, when
$\|A^{(1)}-A^{(2)}\|_{\text{F}}>2\lambda$, we prove
$\hat{Z}^{(1)}\neq\hat{Z}^{(2)}$. Note that by (D.7)-(D.10), we have

$\hat{Z}^{(1)}+\hat{Z}^{(2)}=A^{(1)}+A^{(2)}.$

If $\hat{Z}^{(1)}=\hat{Z}^{(2)}$, we then have

$\hat{Z}^{(1)}=\hat{Z}^{(2)}=\frac{A^{(1)}+A^{(2)}}{2}.$

By (D.7) and (D.10), we have

$\|\hat{Z}^{(1)}-A^{(1)}\|_{\text{F}}=\frac{1}{2}\|A^{(1)}-A^{(2)}\|_{\text{F}}=\lambda\|T(\hat{Z}^{(1)},\hat{Z}^{(2)})\|_{\text{F}}\leq\lambda,$

which implies that

$\|A^{(1)}-A^{(2)}\|_{\text{F}}\leq 2\lambda,$

and this contradicts the assumption that
$\|A^{(1)}-A^{(2)}\|_{\text{F}}>2\lambda$. Thus, we must have
$\hat{Z}^{(1)}\neq\hat{Z}^{(2)}$.

Note that by this claim and the argument proving this claim, we have already
proved (D.5). We then prove (D.6). When
$\|A^{(1)}-A^{(2)}\|_{\text{F}}>2\lambda$, by the claim above, we must have
$\hat{Z}^{(1)}\neq\hat{Z}^{(2)}$. Then by (D.7)-(D.10), we have

$\hat{Z}^{(1)}-A^{(1)}+\frac{\lambda}{\|\hat{Z}^{(1)}-\hat{Z}^{(2)}\|_{\text{F}}}\left(\hat{Z}^{(1)}-\hat{Z}^{(2)}\right)=0,$
(D.11)
$\hat{Z}^{(2)}-A^{(2)}-\frac{\lambda}{\|\hat{Z}^{(1)}-\hat{Z}^{(2)}\|_{\text{F}}}\left(\hat{Z}^{(1)}-\hat{Z}^{(2)}\right)=0.$
(D.12)

(D.11) and (D.12) implies that

$\hat{Z}^{(1)}-\hat{Z}^{(2)}-\left(A^{(1)}-A^{(2)}\right)+\frac{2\lambda}{\|\hat{Z}^{(1)}-\hat{Z}^{(2)}\|_{\text{F}}}\left(\hat{Z}^{(1)}-\hat{Z}^{(2)}\right)=0,$

which implies that

$\hat{Z}^{(1)}-\hat{Z}^{(2)}=\alpha\cdot\left(A^{(1)}-A^{(2)}\right),$ (D.13)

where $\alpha$ is a constant. We then substitue (D.13) back to (D.11) and
(D.12), we then have (D.6).  [2mm]

###### Lemma 7

For a set of indices $\mathcal{G}=\\{G_{t}\\}_{t=1,\ldots,N_{\mathcal{G}}}$,
suppose $|\cdot|_{1,2}$ is defined in (B.3). Then for any matrix
$A\in{\mathbb{R}^{p^{2}M^{2}\times{p^{2}M^{2}}}}$ and
$\theta\in{\mathbb{R}^{p^{2}M^{2}}}$

$|\theta^{\top}A\theta|\leq{M^{2}|A|_{\infty}|\theta|^{2}_{1,2}}.$ (D.14)

Proof  By direct calculation, we have

$\displaystyle|\theta^{\top}A\theta|$
$\displaystyle=\left|\sum_{i}\sum_{j}A_{ij}\theta_{i}\theta_{j}\right|$
$\displaystyle\leq{\sum_{i}\sum_{j}|A_{ij}\theta_{i}\theta_{j}|}$
$\displaystyle\leq{|A|_{\infty}\left(\sum_{i}|\theta_{i}|\right)^{2}}$
$\displaystyle=|A|_{\infty}\left(\sum_{t=1}^{N_{\mathcal{G}}}\sum_{k\in{G_{t}}}|\theta_{k}|\right)^{2}$
$\displaystyle=|A|_{\infty}\left(\sum_{t=1}^{N_{\mathcal{G}}}|\theta_{G_{t}}|_{1}\right)^{2}$
$\displaystyle\leq{|A|_{\infty}\left(\sum_{t=1}^{N_{\mathcal{G}}}M|\theta_{G_{t}}|_{2}\right)^{2}}$
$\displaystyle=M^{2}|A|_{\infty}|\theta|^{2}_{1,2},$

where in the penultimate line, we use that for any vector
$v\in{\mathbb{R}^{n}}$, $|v|_{1}\leq{\sqrt{n}|v|_{2}}$.  [2mm]

###### Lemma 8

Suppose $\mathcal{M}$ is defined as in (B.1). For any
$\theta\in{\mathcal{M}}$, we have $|\theta|_{1,2}\leq{\sqrt{s}}|\theta|_{2}$.
Furthermore, for $\Psi(\mathcal{M})$ as defined in (B.5), we have
$\Psi(\mathcal{M})=\sqrt{s}$.

Proof  By definition of $\mathcal{M}$ and $|\cdot|_{1,2}$, we have

$\displaystyle|\theta|_{1,2}$
$\displaystyle=\sum_{t\in{S_{\mathcal{G}}}}|\theta_{G_{t}}|_{2}+\sum_{t\notin{S_{\mathcal{G}}}}|\theta_{G_{t}}|_{2}$
$\displaystyle=\sum_{t\in{S_{\mathcal{G}}}}|\theta_{G_{t}}|_{2}$
$\displaystyle\leq{\sqrt{s}}\left(\sum_{t\in{S_{\mathcal{G}}}}|\theta_{G_{t}}|^{2}_{2}\right)^{\frac{1}{2}}$
$\displaystyle=\sqrt{s}|\theta|_{2}.$

In the penultimate line, we appeal to the Cauchy-Schwartz inequality. To show
$\Psi(\mathcal{M})=\sqrt{s}$, it suffices to show that the upper bound above
can be achieved. Select $\theta\in{\mathbb{R}^{p^{2}M^{2}}}$ such that
$|\theta_{G_{t}}|_{2}=c$, $\forall{t\in{S_{\mathcal{G}}}}$, where $c$ is some
positive constant. This implies that $|\theta|_{1,2}=sc$ and
$|\theta|_{2}=\sqrt{s}c$ so that $|\theta|_{1,2}=\sqrt{s}|\theta|_{2}$. Thus,
$\Psi(\mathcal{M})=\sqrt{s}$.  [2mm]

###### Lemma 9

For $\mathcal{R}(\cdot)$ norm defined in (B.3), its dual norm
$\mathcal{R}^{*}(\cdot)$, defined in (B.4), is

$\mathcal{R}^{*}(v)\;=\;\max_{t=1,\ldots,N_{\mathcal{G}}}|v_{G_{t}}|_{2}.$
(D.15)

Proof  For any $u:|u|_{1,2}\leq{1}$ and $v\in{\mathbb{R}^{p^{2}M^{2}}}$, we
have

$\displaystyle\langle{v,u}\rangle$
$\displaystyle=\sum_{t=1}^{N_{\mathcal{G}}}\langle{v_{G_{t}},u_{G_{t}}}\rangle$
$\displaystyle\leq{\sum_{t=1}^{N_{\mathcal{G}}}|v_{G_{t}}|_{2}|u_{G_{t}}|_{2}}$
$\displaystyle\leq\left(\max_{t=1,2,\cdots,N_{\mathcal{G}}}|v_{G_{t}}|_{2}\right)\sum_{t=1}^{N_{\mathcal{G}}}|u_{G_{t}}|_{2}$
$\displaystyle=\left(\max_{t=1,2,\cdots,N_{\mathcal{G}}}|v_{G_{t}}|_{2}\right)|u|_{1,2}$
$\displaystyle\leq{\max_{t=1,2,\cdots,N_{\mathcal{G}}}|v_{G_{t}}|_{2}}.$

To complete the proof, we to show that this upper bound can be obtained. Let
$t^{*}=\operatorname*{arg\,max}_{t=1,2,\cdots,N_{\mathcal{G}}}|v_{G_{t}}|$,
and select $u$ such that

$\displaystyle u_{G_{t}}$ $\displaystyle=0$
$\displaystyle\qquad{\forall{t\neq{t^{*}}}},$ $\displaystyle u_{G_{t}}$
$\displaystyle=\frac{v_{G_{t^{*}}}}{|v_{G_{t^{*}}}|_{2}}$
$\displaystyle\qquad{t={t^{*}}}.$

It follows that $|u|_{1,2}=1$ and
$\langle{v,u}\rangle=|v_{G_{t^{*}}}|_{2}=\max_{t=1,\ldots,N_{\mathcal{G}}}|v_{G_{t}}|_{2}$.
[2mm]

###### Lemma 10

Given that $A1$-$A5$ hold, we have $\lvert I_{1}\rvert\leq\delta/16$ for all
$1\leq j,l\leq p$, $\ 1\leq k,m\leq M$.

Proof  This directly follows the assumption that $A_{5}$ holds.  [2mm]

###### Lemma 11

Given that $A1$-$A5$ hold, we have $\lvert I_{2}\rvert\leq\delta/16$ for all
$1\leq j,l\leq p$, $\ 1\leq k,m\leq M$.

Proof  For any $1\leq j,l\leq p$, $\ 1\leq k,m\leq M$, assume that $A1$-$A5$
hold, we then have

$\displaystyle\lvert I_{2}\rvert$
$\displaystyle=\lvert\langle\frac{1}{n}\sum^{n}_{i=1}a_{ijk}(\hat{g}_{il}-g_{il}),\phi_{lm}\rangle\rvert$
$\displaystyle\leq\lVert\frac{1}{n}\sum^{n}_{i=1}a_{ijk}(\hat{g}_{il}-g_{il})\rVert$
$\displaystyle\overset{(i)}{\leq}\sqrt{\frac{1}{n}\sum^{n}_{i=1}a^{2}_{ijk}}\sqrt{\frac{1}{n}\sum^{n}_{i=1}\lVert\hat{g}_{il}-g_{il}\rVert^{2}}$
$\displaystyle\overset{(ii)}{\leq}\delta_{1}\sqrt{\frac{1}{n}\sum^{n}_{i=1}a^{2}_{ijk}}$
$\displaystyle=\delta_{1}\lambda^{1/2}_{jk}\sqrt{\frac{1}{n}\sum^{n}_{i=1}\xi^{2}_{ijk}}$
$\displaystyle\overset{(iii)}{\leq}\sqrt{\frac{3}{2}}\delta_{1}\lambda^{1/2}_{jk}$
$\displaystyle\leq\sqrt{\frac{3}{2}}\sqrt{d_{1}}\delta_{1}k^{-\beta/2}$
$\displaystyle\leq\sqrt{\frac{3}{2}}\sqrt{d_{1}}\delta_{1},$

where $(i)$ follows Lemma 26, $(ii)$ follows $A_{1}$, $(iii)$ follows $A_{3}$.
Note the definition of $d_{0}$, we thus have

$\lvert I_{2}\rvert\leq\sqrt{\frac{3}{2}}d_{0}\delta_{1}.$ (D.16)

Since

$\delta_{1}=\delta/\left(144d^{2}_{0}M^{1+\beta}\sqrt{3\lambda_{0,\max}}\right)\leq\delta/(8\sqrt{6}d_{0}),$
(D.17)

we have

$\sqrt{\frac{3}{2}}d_{0}\delta_{1}\leq\sqrt{\frac{3}{2}}d_{0}\cdot\frac{\delta}{8\sqrt{6}d_{0}}=\frac{\delta}{16}.$
(D.18)

Thus,

$\lvert I_{2}\rvert\leq\frac{\delta}{16}.$

[2mm]

###### Lemma 12

Given that $A1$-$A5$ hold, we have $\lvert I_{3}\rvert\leq\delta/16$ for all
$1\leq j,l\leq p$, $\ 1\leq k,m\leq M$.

Proof  For any $1\leq j,l\leq p$, $\ 1\leq k,m\leq M$, assume that $A1$-$A5$
hold, we then have

$\displaystyle\lvert I_{3}\rvert$
$\displaystyle=\lvert\langle\frac{1}{n}\sum^{n}_{i=1}a_{ijk}g_{il},\hat{\phi}_{lm}-\phi_{lm}\rangle\rvert$
$\displaystyle\leq\lVert\frac{1}{n}\sum^{n}_{i=1}a_{ijk}g_{il}\rVert\lVert\hat{\phi}_{lm}-\phi_{lm}\rVert$
$\displaystyle=\lambda^{1/2}_{jk}\lVert\frac{1}{n}\sum^{n}_{i=1}\xi_{ijk}g_{il}\rVert\lVert\hat{\phi}_{lm}-\phi_{lm}\rVert$
$\displaystyle\overset{(i)}{\leq}\lambda^{1/2}_{jk}\left(\frac{1}{n}\sum^{n}_{i=1}\xi^{2}_{ijk}\right)^{1/2}\left(\frac{1}{n}\sum^{n}_{i=1}\lVert
g_{il}\rVert^{2}\right)^{1/2}\lVert\hat{\phi}_{lm}-\phi_{lm}\rVert$
$\displaystyle\overset{(ii)}{\leq}\lambda^{1/2}_{jk}\left(\frac{1}{n}\sum^{n}_{i=1}\xi^{2}_{ijk}\right)^{1/2}\left(\frac{1}{n}\sum^{n}_{i=1}\lVert
g_{il}\rVert^{2}\right)^{1/2}d_{lm}\lVert\hat{K}_{ll}-K_{ll}\rVert_{\text{HS}},$

where $(i)$ follows Lemma 26, and $(ii)$ follows Lemma 27. Note that
$\lambda^{1/2}_{jk}\leq\sqrt{d_{1}}k^{-\beta/2}$, $d_{lm}\leq
d_{2}m^{1+\beta}$ and $A_{2}$-$A_{4}$ hold, thus we have

$\displaystyle\lvert I_{3}\rvert$
$\displaystyle\leq\sqrt{d_{1}}d_{2}k^{-\beta/2}m^{1+\beta}\sqrt{\frac{3}{2}}\sqrt{2\lambda_{0,\max}}\delta_{2}$
(D.19) $\displaystyle\leq
d^{2}_{0}M^{1+\beta}\sqrt{3\lambda_{0,\max}}\delta_{2}.$

By definition of $\delta_{2}$, we have

$d^{2}_{0}M^{1+\beta}\sqrt{3\lambda_{0,\max}}\delta_{2}\leq
d^{2}_{0}M^{1+\beta}\sqrt{3\lambda_{0,\max}}\times\frac{\delta}{16d^{2}_{0}M^{1+\beta}\sqrt{3\lambda_{0,\max}}}=\frac{\delta}{16}.$
(D.20)

Thus,

$\lvert I_{3}\rvert\leq\frac{\delta}{16}.$

[2mm]

###### Lemma 13

Given that $A1$-$A5$ hold, we have $\lvert I_{4}\rvert\leq\delta/16$ for all
$1\leq j,l\leq p$, $\ 1\leq k,m\leq M$.

Proof  For any $1\leq j,l\leq p$, $\ 1\leq k,m\leq M$, assume that $A1$-$A5$
hold, we then have

$\displaystyle\lvert I_{4}\rvert$
$\displaystyle=\lvert\frac{1}{n}\sum^{n}_{i=1}a_{ijk}\langle\hat{g}_{il}-g_{il},\hat{\phi}_{lm}-\phi_{lm}\rangle\rvert$
$\displaystyle\leq\frac{1}{n}\lVert\sum^{n}_{i=1}a_{ijk}\left(\hat{g}_{il}-g_{il}\right)\rVert\lVert\hat{\phi}_{lm}-\phi_{lm}\rVert$
$\displaystyle=\leq\lambda^{1/2}_{jk}\frac{1}{n}\lVert\sum^{n}_{i=1}\xi_{ijk}\left(\hat{g}_{il}-g_{il}\right)\rVert\lVert\hat{\phi}_{lm}-\phi_{lm}\rVert$
$\displaystyle\overset{(i)}{\leq}\lambda^{1/2}_{jk}\left(\frac{1}{n}\sum^{n}_{i=1}\xi^{2}_{ijk}\right)^{1/2}\left(\frac{1}{n}\sum^{n}_{i=1}\lVert\hat{g}_{il}-g_{il}\rVert^{2}\right)^{1/2}\lVert\hat{\phi}_{lm}-\phi_{lm}\rVert$
$\displaystyle\overset{(ii)}{\leq}\lambda^{1/2}_{jk}d_{lm}\left(\frac{1}{n}\sum^{n}_{i=1}\xi^{2}_{ijk}\right)^{1/2}\left(\frac{1}{n}\sum^{n}_{i=1}\lVert\hat{g}_{il}-g_{il}\rVert^{2}\right)^{1/2}\lVert\hat{K}_{ll}-K_{ll}\rVert_{\text{HS}},$

where $(i)$ follows Lemma 26, and $(ii)$ follows Lemma 27. Note that
$\lambda^{1/2}_{jk}\leq\sqrt{d_{1}}k^{-\beta/2}$, $d_{lm}\leq
d_{2}m^{1+\beta}$ and $A_{1}$-$A_{3}$ hold, thus we have

$\displaystyle\lvert I_{4}\rvert$
$\displaystyle\leq\sqrt{\frac{3}{2}}\sqrt{d_{1}}d_{2}k^{-\beta/2}m^{1+\beta}\delta_{1}\delta_{2}$
$\displaystyle\leq\sqrt{\frac{3}{2}}d^{2}_{0}M^{1+\beta}\delta_{1}\delta_{2}$
$\displaystyle\overset{(iii)}{\leq}\frac{\delta}{16}\times\frac{\sqrt{\frac{3}{2}}d^{2}_{0}M^{1+\beta}\delta_{1}\delta_{2}}{\sqrt{\frac{3}{2}}d_{0}\delta_{1}}$
$\displaystyle\leq\frac{\delta}{16}\times d_{0}M^{1+\beta}\delta_{2}$
$\displaystyle\leq\frac{\delta}{16}\times
d_{0}M^{1+\beta}\times\frac{\delta}{16d^{2}_{0}M^{1+\beta}\sqrt{3\lambda_{0,\max}}}$
$\displaystyle=\frac{\delta}{16}\times\frac{\delta}{16d_{0}\sqrt{3\lambda_{0,\max}}}$
$\displaystyle\leq\frac{\delta}{16},$

where $(iii)$ follows (D.18).  [2mm]

###### Lemma 14

Given that $A1$-$A5$ hold, we have $\lvert I_{5}\rvert\leq\delta/16$ for all
$1\leq j,l\leq p$, $\ 1\leq k,m\leq M$.

Proof  This proof is similar to the proof of Lemma 11, thus is omitted.  [2mm]

###### Lemma 15

Given that $A1$-$A5$ hold, we have $\lvert I_{6}\rvert\leq\delta/16$ for all
$1\leq j,l\leq p$, $\ 1\leq k,m\leq M$.

Proof  For any $1\leq j,l\leq p$, $\ 1\leq k,m\leq M$, assume that $A1$-$A5$
hold, we then have

$\displaystyle\lvert I_{6}\rvert$
$\displaystyle=\lvert\frac{1}{n}\sum^{n}_{i=1}\langle\hat{g}_{ij}-g_{ij},\phi_{jk}\rangle\langle\hat{g}_{il}-g_{il},\phi_{lm}\rangle\rvert$
$\displaystyle\leq\frac{1}{n}\sum^{n}_{i=1}\lvert\langle\hat{g}_{ij}-g_{ij},\phi_{jk}\rangle\rvert\lvert\langle\hat{g}_{il}-g_{il},\phi_{lm}\rangle\rvert$
$\displaystyle\leq\sqrt{\frac{1}{n}\sum^{n}_{i=1}\lvert\langle\hat{g}_{ij}-g_{ij},\phi_{jk}\rangle\rvert^{2}}\sqrt{\frac{1}{n}\sum^{n}_{i=1}\lvert\langle\hat{g}_{il}-g_{il},\phi_{lm}\rangle\rvert^{2}}$
$\displaystyle\leq\sqrt{\frac{1}{n}\sum^{n}_{i=1}\lVert\hat{g}_{ij}-g_{ij}\rVert^{2}}\sqrt{\frac{1}{n}\sum^{n}_{i=1}\lVert\hat{g}_{il}-g_{il}\rVert^{2}}.$

By the assumption that $A_{1}$ holds, we thus have

$\lvert I_{6}\rvert\leq\delta^{2}_{1}.$ (D.21)

By (D.17),(D.18) and Lemma 11, we have

$\displaystyle\delta^{2}_{1}$
$\displaystyle\leq\frac{\delta}{16}\times\frac{\delta^{2}_{1}}{\sqrt{\frac{3}{2}}d_{0}\delta_{1}}$
(D.22)
$\displaystyle=\frac{\delta}{16}\times\frac{\delta_{1}}{\sqrt{\frac{3}{2}}d_{0}}$
(D.23)
$\displaystyle\leq\frac{\delta}{16}\times\frac{1}{\sqrt{\frac{3}{2}}d_{0}}\times\frac{\delta}{8\sqrt{6}d_{0}}$
(D.24) $\displaystyle=\frac{\delta}{16}\times\frac{\delta}{24d^{2}_{0}}$
(D.25) $\displaystyle\leq\frac{\delta}{16},$ (D.26)

and thus

$\lvert I_{6}\rvert\leq\frac{\delta}{16}.$

[2mm]

###### Lemma 16

Given that $A1$-$A5$ hold, we have $\lvert I_{7}\rvert\leq\delta/16$ for all
$1\leq j,l\leq p$, $\ 1\leq k,m\leq M$.

Proof  For any $1\leq j,l\leq p$, $\ 1\leq k,m\leq M$, assume that $A1$-$A5$
hold, we then have

$\displaystyle\lvert I_{7}\rvert$
$\displaystyle=\lvert\frac{1}{n}\sum^{n}_{i=1}\langle\hat{g}_{ij}-g_{ij},\phi_{jk}\rangle\langle
g_{il},\hat{\phi}_{lm}-\phi_{lm}\rangle\rvert$
$\displaystyle\leq\frac{1}{n}\sum^{n}_{i=1}\lvert\langle\hat{g}_{ij}-g_{ij},\phi_{jk}\rangle\langle
g_{il},\hat{\phi}_{lm}-\phi_{lm}\rangle\rvert$
$\displaystyle\leq\sqrt{\frac{1}{n}\sum^{n}_{i=1}\lvert\langle\hat{g}_{ij}-g_{ij},\phi_{jk}\rangle\rvert^{2}}\sqrt{\frac{1}{n}\sum^{n}_{i=1}\lvert\langle
g_{il},\hat{\phi}_{lm}-\phi_{lm}\rangle\rvert^{2}}$
$\displaystyle\leq\sqrt{\frac{1}{n}\sum^{n}_{i=1}\lVert\hat{g}_{ij}-g_{ij}\rVert^{2}}\sqrt{\frac{1}{n}\sum^{n}_{i=1}\lVert
g_{il}\rVert^{2}\lVert\hat{\phi}_{lm}-\phi_{lm}\rVert^{2}}$
$\displaystyle\overset{(i)}{\leq}\delta_{1}\lVert\hat{\phi}_{lm}-\phi_{lm}\rVert\sqrt{\frac{1}{n}\sum^{n}_{i=1}\lVert
g_{il}\rVert^{2}}$
$\displaystyle\overset{(ii)}{\leq}\delta_{1}\sqrt{2\lambda_{0,\max}}\lVert\hat{\phi}_{lm}-\phi_{lm}\rVert$
$\displaystyle\overset{(iii)}{\leq}\delta_{1}\sqrt{2\lambda_{0,\max}}d_{lm}\|\hat{K}_{ll}-K_{ll}\rVert_{\text{HS}}$
$\displaystyle\overset{(iv)}{\leq}\delta_{1}\delta_{2}\sqrt{2\lambda_{0,\max}}d_{lm}$
$\displaystyle\leq\delta_{1}\delta_{2}\sqrt{2\lambda_{0,\max}}d_{2}m^{1+\beta}$
$\displaystyle\leq
d_{0}\sqrt{2\lambda_{0,\max}}M^{1+\beta}\delta_{1}\delta_{2},$

where $(i)$ follows the assumption that $A_{1}$ holds, $(ii)$ follows the
assumption that $A_{4}$ holds, $(iii)$ follows Lemma 27, and $(iv)$ follows
the assumption that $A_{2}$ holds. By (D.17) and (D.20), we have

$\displaystyle\lvert I_{7}\rvert$
$\displaystyle\leq\frac{\delta}{16}\times\frac{d_{0}\sqrt{2\lambda_{0,\max}}M^{1+\beta}\delta_{1}\delta_{2}}{d^{2}_{0}M^{1+\beta}\sqrt{3\lambda_{0,\max}}\delta_{2}}$
$\displaystyle=\frac{\delta}{16}\times\sqrt{\frac{2}{3}}\times\frac{\delta_{1}}{d_{0}}$
$\displaystyle\leq\frac{\delta}{16}\times\sqrt{\frac{2}{3}}\times\frac{\delta}{8\sqrt{6}d^{2}_{0}}$
$\displaystyle=\frac{\delta}{16}\times\frac{\delta}{24\delta^{2}_{0}}$
$\displaystyle\leq\frac{\delta}{16}.$

[2mm]

###### Lemma 17

Given that $A1$-$A5$ hold, we have $\lvert I_{8}\rvert\leq\delta/16$ for all
$1\leq j,l\leq p$, $\ 1\leq k,m\leq M$.

Proof  For any $1\leq j,l\leq p$, $\ 1\leq k,m\leq M$, assume that $A1$-$A5$
hold, we then have

$\displaystyle\lvert I_{8}\rvert$
$\displaystyle=\lvert\frac{1}{n}\sum^{n}_{i=1}\langle\hat{g}_{ij}-g_{ij},\phi_{jk}\rangle\langle\hat{g}_{il}-g_{il},\hat{\phi}_{lm}-\phi_{lm}\rangle\rvert$
$\displaystyle\leq\frac{1}{n}\sum^{n}_{i=1}\lvert\langle\hat{g}_{ij}-g_{ij},\phi_{jk}\rangle\rvert\lvert\langle\hat{g}_{il}-g_{il},\hat{\phi}_{lm}-\phi_{lm}\rangle\rvert$
$\displaystyle\leq\sqrt{\frac{1}{n}\sum^{n}_{i=1}\lvert\langle\hat{g}_{ij}-g_{ij},\phi_{jk}\rangle\rvert^{2}}\sqrt{\frac{1}{n}\sum^{n}_{i=1}\lvert\langle\hat{g}_{il}-g_{il},\hat{\phi}_{lm}-\phi_{lm}\rangle\rvert^{2}}$
$\displaystyle\leq\sqrt{\frac{1}{n}\sum^{n}_{i=1}\lVert\hat{g}_{ij}-g_{ij}\rVert^{2}}\sqrt{\frac{1}{n}\sum^{n}_{i=1}\lVert\hat{g}_{il}-g_{il}\rVert^{2}\lVert\hat{\phi}_{lm}-\phi_{lm}\rVert^{2}}$
$\displaystyle\overset{(i)}{\leq}\delta^{2}_{1}\lVert\hat{\phi}_{lm}-\phi_{lm}\rVert$
$\displaystyle\overset{(ii)}{\leq}\delta^{2}_{1}d_{lm}\lVert\hat{K}_{ll}-K_{ll}\rVert_{\text{HS}}$
$\displaystyle\leq\delta^{2}_{1}d_{2}m^{1+\beta}\lVert\hat{K}_{ll}-K_{ll}\rVert_{\text{HS}}$
$\displaystyle\leq\delta^{2}_{1}d_{0}M^{1+\beta}\lVert\hat{K}_{ll}-K_{ll}\rVert_{\text{HS}}$
$\displaystyle\overset{(iii)}{\leq}d_{0}M^{1+\beta}\delta^{2}_{1}\delta_{2}$

where $(i)$ follows the assumption that $A_{1}$ holds, $(ii)$ follows the
assumption that Lemma 27 holds, and $(iii)$ follows the assumption that
$A_{2}$ holds. By (D.22), we have

$\displaystyle\lvert I_{8}\rvert$
$\displaystyle\leq\frac{\delta}{16}\times\frac{d_{0}M^{1+\beta}\delta^{2}_{1}\delta_{2}}{\delta^{2}_{1}}$
$\displaystyle=\frac{\delta}{16}\times d_{0}M^{1+\beta}\delta_{2}$
$\displaystyle=\frac{\delta}{16}\times
d_{0}M^{1+\beta}\times\frac{\delta}{16d^{2}_{0}M^{1+\beta}\sqrt{3\lambda_{0,\max}}}$
$\displaystyle=\frac{\delta}{16}\times\frac{\delta}{16d_{0}\sqrt{3\lambda_{0,\max}}}$
$\displaystyle\leq\frac{\delta}{16}.$

[2mm]

###### Lemma 18

Given that $A1$-$A5$ hold, we have $\lvert I_{9}\rvert\leq\delta/16$ for all
$1\leq j,l\leq p$, $\ 1\leq k,m\leq M$.

Proof  This proof is similar to the proof of Lemma 12, thus is omitted.  [2mm]

###### Lemma 19

Given that $A1$-$A5$ hold, we have $\lvert I_{10}\rvert\leq\delta/16$ for all
$1\leq j,l\leq p$, $\ 1\leq k,m\leq M$.

Proof  This proof is similar to the proof of Lemma 16, thus is omitted.  [2mm]

###### Lemma 20

Given that $A1$-$A5$ hold, we have $\lvert I_{11}\rvert\leq\delta/16$ for all
$1\leq j,l\leq p$, $\ 1\leq k,m\leq M$.

Proof  For any $1\leq j,l\leq p$, $\ 1\leq k,m\leq M$, assume that $A1$-$A5$
hold, we then have

$\displaystyle\lvert I_{11}\rvert$
$\displaystyle=\lvert\frac{1}{n}\sum^{n}_{i=1}\langle
g_{ij},\hat{\phi}_{jk}-\phi_{jk}\rangle\langle
g_{il},\hat{\phi}_{lm}-\phi_{lm}\rangle\rvert$
$\displaystyle\leq\frac{1}{n}\sum^{n}_{i=1}\lvert\langle
g_{ij},\hat{\phi}_{jk}-\phi_{jk}\rangle\rvert\lvert\langle
g_{il},\hat{\phi}_{lm}-\phi_{lm}\rangle\rvert$
$\displaystyle\leq\sqrt{\frac{1}{n}\sum^{n}_{i=1}\lvert\langle
g_{ij},\hat{\phi}_{jk}-\phi_{jk}\rangle\rvert^{2}}\sqrt{\frac{1}{n}\sum^{n}_{i=1}\lvert\langle
g_{il},\hat{\phi}_{lm}-\phi_{lm}\rangle\rvert^{2}}$
$\displaystyle\leq\sqrt{\frac{1}{n}\sum^{n}_{i=1}\lVert
g_{ij}\rVert^{2}}\sqrt{\frac{1}{n}\sum^{n}_{i=1}\lVert
g_{il}\rVert^{2}}\lVert\hat{\phi}_{jk}-\phi_{jk}\rVert\lVert\hat{\phi}_{lm}-\phi_{lm}\rVert$
$\displaystyle\overset{(i)}{\leq}2\lambda_{0,\max}\lVert\hat{\phi}_{jk}-\phi_{jk}\rVert\lVert\hat{\phi}_{lm}-\phi_{lm}\rVert$
$\displaystyle\overset{(ii)}{\leq}2\lambda_{0,\max}\delta^{2}_{2}d_{jk}d_{lm}$
$\displaystyle\leq
2\lambda_{0,\max}\delta^{2}_{2}d^{2}_{2}k^{1+\beta}m^{1+\beta},$

where $(i)$ follows because assumption $A_{4}$ holds, $(ii)$ follows Lemma 27.
Then, we have

$\lvert I_{11}\rvert\leq
2d^{2}_{0}\lambda_{0,\max}M^{2+2\beta}\delta^{2}_{2}.$ (D.27)

Thus, by (D.20), we have

$\displaystyle 2d^{2}_{0}\lambda_{0,\max}M^{2+2\beta}\delta^{2}_{2}$
$\displaystyle\leq\frac{\delta}{16}\times\frac{2d^{2}_{0}\lambda_{0,\max}M^{2+2\beta}\delta^{2}_{2}}{d^{2}_{0}M^{1+\beta}\sqrt{3\lambda_{0,\max}}\delta_{2}}$
(D.28)
$\displaystyle=\frac{\delta}{16}\times\frac{2}{\sqrt{3}}M^{1+\beta}\sqrt{\lambda_{0,\max}}\delta_{2}$
(D.29)
$\displaystyle=\frac{\delta}{16}\times\frac{2}{\sqrt{3}}M^{1+\beta}\sqrt{\lambda_{0,\max}}\times\frac{\delta}{16d^{2}_{0}M^{1+\beta}\sqrt{3\lambda_{0,\max}}}$
(D.30) $\displaystyle=\frac{\delta}{16}\times\frac{\delta}{24d^{2}_{0}}$
(D.31) $\displaystyle\leq\frac{\delta}{16},$ (D.32)

which implies that

$\lvert I_{11}\rvert\leq\frac{\delta}{16}.$

[2mm]

###### Lemma 21

Given that $A1$-$A5$ hold, we have $\lvert I_{12}\rvert\leq\delta/16$ for all
$1\leq j,l\leq p$, $\ 1\leq k,m\leq M$.

Proof  For any $1\leq j,l\leq p$, $\ 1\leq k,m\leq M$, assume that $A1$-$A5$
hold, we then have

$\displaystyle\lvert I_{12}\rvert$
$\displaystyle=\lvert\frac{1}{n}\sum^{n}_{i=1}\langle
g_{ij},\hat{\phi}_{jk}-\phi_{jk}\rangle\langle\hat{g}_{il}-g_{il},\hat{\phi}_{lm}-\phi_{lm}\rangle\rvert$
$\displaystyle\leq\frac{1}{n}\sum^{n}_{i=1}\lvert\langle
g_{ij},\hat{\phi}_{jk}-\phi_{jk}\rangle\rvert\lvert\langle\hat{g}_{il}-g_{il},\hat{\phi}_{lm}-\phi_{lm}\rangle\rvert$
$\displaystyle\leq\sqrt{\frac{1}{n}\sum^{n}_{i=1}\lvert\langle
g_{ij},\hat{\phi}_{jk}-\phi_{jk}\rangle\rvert^{2}}\sqrt{\frac{1}{n}\sum^{n}_{i=1}\lvert\langle\hat{g}_{il}-g_{il},\hat{\phi}_{lm}-\phi_{lm}\rangle\rvert^{2}}$
$\displaystyle\leq\sqrt{\frac{1}{n}\sum^{n}_{i=1}\lVert
g_{ij}\rVert^{2}}\sqrt{\frac{1}{n}\sum^{n}_{i=1}\lVert\hat{g}_{il}-g_{il}\rVert^{2}}\lVert\hat{\phi}_{jk}-\phi_{jk}\rVert\lVert\hat{\phi}_{lm}-\phi_{lm}\rVert$
$\displaystyle\overset{(i)}{\leq}\sqrt{2\lambda_{0,\max}}\delta_{1}\delta^{2}_{2}d_{jk}d_{lm}$
$\displaystyle\leq
d^{2}_{2}\sqrt{2\lambda_{0,\max}}k^{1+\beta}m^{1+\beta}\delta_{1}\delta^{2}_{2},$

where $(i)$ follows the assumption that $A_{1}$-$A_{3}$ hold along with Lemma
27. Then, we have

$\lvert I_{12}\rvert\leq
d^{2}_{0}\sqrt{2\lambda_{0,\max}}M^{2+2\beta}\delta_{1}\delta^{2}_{2}.$ (D.33)

By (D.17) and (D.28), we have

$\displaystyle
d^{2}_{0}\sqrt{2\lambda_{0,\max}}M^{2+2\beta}\delta_{1}\delta^{2}_{2}$
$\displaystyle\leq\frac{\delta}{16}\times\frac{d^{2}_{0}\sqrt{2\lambda_{0,\max}}M^{2+2\beta}\delta_{1}\delta^{2}_{2}}{2d^{2}_{0}\lambda_{0,\max}M^{2+2\beta}\delta^{2}_{2}}$
(D.34)
$\displaystyle=\frac{\delta}{16}\times\frac{\delta_{1}}{\sqrt{2\lambda_{0,\max}}}$
(D.35)
$\displaystyle\leq\frac{\delta}{16}\times\frac{1}{\sqrt{2\lambda_{0,\max}}}\times\frac{\delta}{8\sqrt{6}d_{0}}$
(D.36)
$\displaystyle=\frac{\delta}{16}\times\frac{\delta}{16d_{0}\sqrt{3\lambda_{0,\max}}}$
(D.37) $\displaystyle\leq\frac{\delta}{16},$ (D.38)

which implies that

$I_{12}\leq\frac{\delta}{16}.$

[2mm]

###### Lemma 22

Given that $A1$-$A5$ hold, we have $\lvert I_{13}\rvert\leq\delta/16$ for all
$1\leq j,l\leq p$, $\ 1\leq k,m\leq M$.

Proof  This proof is similar to the proof of Lemma 13, thus is omitted.  [2mm]

###### Lemma 23

Given that $A1$-$A5$ hold, we have $\lvert I_{14}\rvert\leq\delta/16$ for all
$1\leq j,l\leq p$, $\ 1\leq k,m\leq M$.

Proof  This proof is similar to the proof of Lemma 17, thus is omitted.  [2mm]

###### Lemma 24

Given that $A1$-$A5$ hold, we have $\lvert I_{15}\rvert\leq\delta/16$ for all
$1\leq j,l\leq p$, $\ 1\leq k,m\leq M$.

Proof  This proof is similar to the proof of Lemma 11, thus is omitted.  [2mm]

###### Lemma 25

Given that $A1$-$A5$ hold, we have $\lvert I_{16}\rvert\leq\delta/16$ for all
$1\leq j,l\leq p$, $\ 1\leq k,m\leq M$.

Proof  For any $1\leq j,l\leq p$, $\ 1\leq k,m\leq M$, assume that $A1$-$A5$
hold, we then have

$\displaystyle\lvert I_{16}\rvert$
$\displaystyle=\lvert\frac{1}{n}\sum^{n}_{i=1}\langle\hat{g}_{ij}-g_{ij},\hat{\phi}_{jk}-\phi_{jk}\rangle\langle\hat{g}_{il}-g_{il},\hat{\phi}_{lm}-\phi_{lm}\rangle\rvert$
$\displaystyle\leq\frac{1}{n}\sum^{n}_{i=1}\lvert\langle\hat{g}_{ij}-g_{ij},\hat{\phi}_{jk}-\phi_{jk}\rangle\rvert\lvert\langle\hat{g}_{il}-g_{il},\hat{\phi}_{lm}-\phi_{lm}\rangle\rvert$
$\displaystyle\leq\sqrt{\frac{1}{n}\sum^{n}_{i=1}\lVert\hat{g}_{ij}-g_{ij}\rVert^{2}}\sqrt{\frac{1}{n}\sum^{n}_{i=1}\lVert\hat{g}_{il}-g_{il}\rVert^{2}}\lVert\hat{\phi}_{jk}-\phi_{jk}\rVert\lVert\hat{\phi}_{lm}-\phi_{lm}\rVert$
$\displaystyle\overset{(i)}{\leq}\delta^{2}_{1}d_{jk}d_{lm}\delta^{2}_{2}$
$\displaystyle\leq
d^{2}_{2}k^{1+\beta}m^{1+\beta}\delta^{2}_{1}\delta^{2}_{2}$
$\displaystyle\leq d^{2}_{0}M^{2+2\beta}\delta^{2}_{1}\delta^{2}_{2},$

where $(i)$ follows the assumption that $A_{1}$, $A_{2}$ hold along with Lemma
27. Thus, by (D.18) and (D.34), we have

$\displaystyle\lvert I_{16}\rvert$
$\displaystyle\leq\frac{\delta}{16}\times\frac{d^{2}_{0}M^{2+2\beta}\delta^{2}_{1}\delta^{2}_{2}}{d^{2}_{0}\sqrt{2\lambda_{0,\max}}M^{2+2\beta}\delta_{1}\delta^{2}_{2}}$
$\displaystyle=\frac{\delta}{16}\times\frac{\delta_{1}}{\sqrt{2\lambda_{0,\max}}}$
$\displaystyle\leq\frac{\delta}{16}\times\frac{1}{\sqrt{2\lambda_{0,\max}}}\times\frac{\delta}{8\sqrt{6}d_{0}}$
$\displaystyle=\frac{\delta}{16}\times\frac{\delta}{16d_{0}\sqrt{3\lambda_{0,\max}}}$
$\displaystyle\leq\frac{\delta}{16}.$

[2mm]

###### Lemma 26

Suppose $f_{1},f_{2},\dots,f_{n}\in\mathbb{H}$ and
$v_{1},v_{2},\dots,v_{n}\in\mathbb{R}$, we have

$\lVert\sum^{n}_{i=1}v_{i}f_{i}\rVert\leq\sqrt{\sum^{n}_{i=1}v^{2}_{i}}\sqrt{\sum^{n}_{i=1}\lVert
f_{i}\rVert^{2}}$

Proof  Note that

$\displaystyle\lVert\sum^{n}_{i=1}v_{i}f_{i}\rVert^{2}$
$\displaystyle=\int\left(\sum^{n}_{i=1}v_{i}f_{i}(t)\right)^{2}dt$
$\displaystyle\overset{(i)}{\leq}\int\left(\sum^{n}_{i=1}v^{2}_{i}\right)\left(\sum^{n}_{i=1}f^{2}_{i}(t)\right)dt$
$\displaystyle=\left(\sum^{n}_{i=1}v^{2}_{i}\right)\left(\sum^{n}_{i=1}\lVert
f_{i}\rVert^{2}\right),$

where $(i)$ follows Cauchy-Schwartz inequality, which directly implies the
result.  [2mm]

###### Lemma 27

Suppose that Assumption 3 holds. Denote
$\tilde{\phi}_{jk}=\text{sgn}\left(\langle\hat{\phi}_{jk},\phi_{jk}\rangle\right)\phi_{jk}$,
where $\text{sgn}(t)=1$ if $t\geq 0$ and $\text{sgn}(t)=-1$ if $t<0$. Then we
have

$\lVert\hat{\phi}_{jk}-\tilde{\phi}_{jk}\rVert\leq
d_{jk}\lVert\hat{K}_{jj}-K_{jj}\rVert_{\text{HS}},$

where
$d_{jk}=2\sqrt{2}\max\\{(\lambda_{j(k-1)}-\lambda_{jk})^{-1},(\lambda_{jk}-\lambda_{j(k+1)})^{-1}\\}$
if $k\geq 2$ and $d_{j1}=2\sqrt{2}(\lambda_{j1}-\lambda_{j2})^{-1}$.

Proof  This lemma can be found in Lemma 4.3 of Bosq (2000) and hence the proof
is omitted.  [2mm]

###### Lemma 28

For $z\sim N_{L}\left(0,I_{L}\right)$, then for any $\delta>0$, we have

$P\left(\lVert z\rVert_{2}>\delta\right)\leq
2\exp\left(-\frac{\delta^{2}}{8L+2\sqrt{2L}\delta}\right).$

Proof  Since

$\mathbb{E}\left[\lVert
z\rVert^{2k}_{2}\right]=\frac{\Gamma(\frac{L}{2}+k)}{\Gamma(\frac{L}{2})}\times
2^{k}\leq k!(2L)^{k},$

we have

$\mathbb{E}\left[\lVert z\rVert^{k}_{2}\right]\leq\sqrt{\mathbb{E}\left[\lVert
z\rVert^{2k}_{2}\right]}\leq\sqrt{k!}\left(\sqrt{2L}\right)^{k}\leq\frac{k!}{2}\cdot
4L\cdot(\sqrt{2L})^{k-2}$

for $k\geq 2$. Thus, by Lemma 29, we have proved the result.  [2mm]

###### Lemma 29

Let $Z_{1},Z_{2},\dots,Z_{n}$ be independent random variables in a separable
Hilbert space with norm $\lVert\cdot\rVert$. If $\mathbb{E}[Z_{i}]=0$
($i=1,\ldots,n$) and

$\sum^{n}_{i=1}\mathbb{E}\left[\lVert
Z_{i}\rVert^{k}\right]\leq\frac{k!}{2}nL_{1}L^{k-2}_{2},k=2,3,\dots,$

for two positive constants $L_{1}$ and $L_{2}$, then for all $\delta>0$,

$P\left(\lVert\sum^{n}_{i=1}Z_{i}\rVert\geq n\delta\right)\leq
2\exp\left(-\frac{n\delta^{2}}{2L_{1}+2L_{2}\delta}\right).$

Proof  This lemma can be derived directly from Theorem 2.5 (2) of Bosq (2000)
and hence its proof is omitted.  [2mm]

###### Lemma 30

For a function $f(t)$ defined on $\mathcal{T}$, assuming that $f$ has
continuous derivative, and let $D_{0,f}\coloneqq\sup_{t\in{\mathcal{T}}}\lvert
f(t)\rvert$, $D_{1,f}\coloneqq\sup_{t\in{\mathcal{T}}}\lvert
f^{\prime}(t)\rvert$, assume that $D_{0,f},D_{1,f}<\infty$. Let
$\lvert\mathcal{T}\rvert$ denote the length of interval $\mathcal{T}$, and let
$u_{1}<u_{2}<\dots<u_{T}\in\mathcal{T}$, we denote endpoints of $\mathcal{T}$
as $u_{0}$ and $u_{T+1}$. Assume that there is positive constant $\zeta_{0}$
such that

$\max_{1\leq k\leq
T+1}\left|\frac{u_{k}-u_{k-1}}{\lvert\mathcal{T}\rvert}-\frac{1}{T}\right|\leq\frac{\zeta_{0}}{T^{2}}$
(D.39)

hold. Let $\zeta_{1}=\zeta_{0}+1$, then we have

$\left|\frac{1}{T}\sum^{T}_{k=1}f(u_{k})-\frac{1}{\lvert\mathcal{T}\rvert}\int_{\mathcal{T}}f(t)dt\right|\leq\frac{D_{1,f}\zeta^{2}_{1}\lvert\mathcal{T}\rvert/2+D_{0,f}(\zeta_{1}+\zeta_{0})}{T}.$

Proof  Since

$\displaystyle\left|\frac{1}{T}\sum^{T}_{k=1}f(u_{k})-\frac{1}{\lvert\mathcal{T}\rvert}\int_{\mathcal{T}}f(t)dt\right|$
$\displaystyle\leq\left|\frac{1}{T}\sum^{T}_{k=1}f(u_{k})-\frac{1}{\lvert\mathcal{T}\rvert}\sum^{T}_{k=1}f(u_{k})(u_{k}-u_{k-1})\right|$
$\displaystyle+\left|\frac{1}{\lvert\mathcal{T}\rvert}\sum^{T}_{k=1}f(u_{k})(u_{k}-u_{k-1})-\frac{1}{\lvert\mathcal{T}\rvert}\int_{\mathcal{T}}f(t)dt\right|,$

we will first prove the first part is smaller than $D_{0,f}\zeta_{0}/T$, and
then prove the second part is smaller than
$(D_{1,f}\zeta^{2}_{1}\lvert\mathcal{T}\rvert/2+D_{0,f}\zeta_{1})/T$. For
first part, we have

$\displaystyle\left|\frac{1}{T}\sum^{T}_{k=1}f(u_{k})-\frac{1}{\lvert\mathcal{T}\rvert}\sum^{T}_{k=1}f(u_{k})(u_{k}-u_{k-1})\right|$
$\displaystyle=\left|\sum^{T}_{k=1}f(u_{k})\left(\frac{1}{T}-\frac{u_{k}-u_{k-1}}{\lvert\mathcal{T}\rvert}\right)\right|$
$\displaystyle\leq\sum^{T}_{k=1}\left|f(u_{k})\right|\left|\frac{1}{T}-\frac{u_{k}-u_{k-1}}{\lvert\mathcal{T}\rvert}\right|$
$\displaystyle\leq\max_{1\leq k\leq
T}\left|\frac{u_{k}-u_{k-1}}{\lvert\mathcal{T}\rvert}-\frac{1}{T}\right|\sum^{T}_{k=1}\left|f(u_{k})\right|$
$\displaystyle\leq\frac{\zeta_{0}}{T^{2}}\times T\times D_{0,f}$
$\displaystyle=\frac{\zeta_{0}D_{0,f}}{T}.$

To prove second part, we first note that based on (D.39), we have

$\max_{1\leq k\leq T+1}\lvert
u_{k}-u_{k-1}\rvert\leq\frac{\zeta_{1}\lvert\mathcal{T}\rvert}{T}.$

Then, for any $t\in(u_{k},u_{k+1})$, by Taylor’s expansion, we have

$f(t)=f(u_{k})+f^{\prime}(\bar{t})(t-u_{k}),$

where $\bar{t}\in(u_{k},t)$. Thus,

$\lvert f(t)-f(u_{k})\rvert=\lvert f^{\prime}(\bar{t})\rvert(t-u_{k})\leq
D_{1,f}(t-u_{k}).$

This way, we have

$\displaystyle\left|\frac{1}{\lvert\mathcal{T}\rvert}\sum^{T}_{k=1}f(u_{k})(u_{k}-u_{k-1})-\frac{1}{\lvert\mathcal{T}\rvert}\int_{\mathcal{T}}f(t)dt\right|$
$\displaystyle\leq\frac{1}{\lvert\mathcal{T}\rvert}\sum^{T}_{k=1}\int^{u_{k}}_{u_{k-1}}\lvert
f(u_{k})-f(t)\rvert
dt+\frac{1}{\lvert\mathcal{T}\rvert}\int^{u_{T+1}}_{u_{T}}\lvert f(t)\rvert
dt$ $\displaystyle\leq\frac{1}{\lvert\mathcal{T}\rvert}\times T\times
D_{1,f}\times\int^{u_{k}}_{u_{k-1}}(t-u_{k})dt+\frac{1}{\lvert\mathcal{T}\rvert}\times
D_{0,f}\times\frac{\zeta_{1}\lvert\mathcal{T}\rvert}{T}$
$\displaystyle=\frac{1}{\lvert\mathcal{T}\rvert}\times T\times
D_{1,f}\times\frac{(u_{k+1}-u_{k})^{2}}{2}+\frac{1}{\lvert\mathcal{T}\rvert}\times
D_{0,f}\times\frac{\zeta_{1}\lvert\mathcal{T}\rvert}{T}$
$\displaystyle\leq\frac{1}{\lvert\mathcal{T}\rvert}\times
T\times\frac{D_{1,f}}{2}\times\left(\max_{1\leq k\leq T+1}\lvert
u_{k+1}-u_{k}\rvert\right)^{2}+\frac{1}{\lvert\mathcal{T}\rvert}\times
D_{0,f}\times\frac{\zeta_{1}\lvert\mathcal{T}\rvert}{T}$
$\displaystyle\leq\frac{1}{\lvert\mathcal{T}\rvert}\times
T\times\frac{D_{1,f}}{2}\times\left(\frac{\zeta_{1}\lvert\mathcal{T}\rvert}{T}\right)^{2}+\frac{1}{\lvert\mathcal{T}\rvert}\times
D_{0,f}\times\frac{\zeta_{1}\lvert\mathcal{T}\rvert}{T}$
$\displaystyle=\frac{D_{1,f}\zeta^{2}_{1}\lvert\mathcal{T}\rvert/2+D_{0,f}\zeta_{1}}{T}.$

Thus, combining part 1 and part 2, we have

$\left|\frac{1}{T}\sum^{T}_{k=1}f(u_{k})-\frac{1}{\lvert\mathcal{T}\rvert}\int_{\mathcal{T}}f(t)dt\right|\leq\frac{D_{1,f}\zeta^{2}_{1}\lvert\mathcal{T}\rvert/2+D_{0,f}(\zeta_{1}+\zeta_{0})}{T}.$

[2mm]

###### Lemma 31

For Gaussian random function $g$ in Hilbert Space $\mathbb{H}$ with mean zero,
that is, $\mathbb{E}[g]=0$, we have

$\mathbb{E}\left[\|g\|^{2k}\right]\leq(2\lambda_{0})^{k}\cdot k!,$

where $\lambda_{0}=\mathbb{E}\left[\|g\|^{2}\right]$.

Proof  Let $\\{\phi_{m}\\}_{m\geq 1}$ be othornormal eigenfunctions of $g$,
and $a_{m}=\langle g,\phi_{m}\rangle$, then $a_{m}\sim N(0,\lambda_{m})$ and
$\lambda_{0}=\sum_{m\geq 1}\lambda_{m}$. Let
$\xi_{m}=\lambda^{-1/2}_{m}a_{m}$, then we have $\xi_{m}\sim N(0,1)$ i.i.d..
By Karhunen–Loève theorem, we have

$g=\sum^{\infty}_{m=1}\lambda_{m}^{1/2}\xi_{m}\phi_{m}.$

Thus, $\|g\|=\left(\sum_{m\geq 1}\lambda_{m}\xi^{2}_{m}\right)^{1/2}$, and
$\|g\|^{2k}=\left(\sum_{m\geq 1}\lambda_{m}\xi^{2}_{m}\right)^{k}$.

Recall Jensen’s inequality, for convex function $\psi(\cdot)$, and real
numbers $x_{1},x_{2},\dots,x_{n}$ in its domain, and positive real numbers
$a_{1},a_{2},\dots,a_{n}$, we have

$\psi\left(\frac{\sum^{n}_{i=1}a_{i}x_{i}}{\sum^{n}_{i=1}a_{i}}\right)\leq\frac{\sum^{n}_{i=1}a_{i}\psi(x_{i})}{\sum^{n}_{i=1}a_{i}}.$

Here, let $\psi(t)=t^{k}$, and we then have

$\displaystyle\|g\|^{2k}$ $\displaystyle=\left(\sum_{m\geq
1}\lambda_{m}\right)^{k}\cdot\left(\frac{\sum_{m\geq
1}\lambda_{m}\xi^{2}_{m}}{\sum_{m\geq 1}\lambda_{m}}\right)^{k}$
$\displaystyle\leq\left(\sum_{m\geq
1}\lambda_{m}\right)^{k}\cdot\frac{\sum_{m\geq
1}\lambda_{m}\xi^{2k}_{m}}{\sum_{m\geq 1}\lambda_{m}}$
$\displaystyle=\left(\sum_{m\geq
1}\lambda_{m}\right)^{k-1}\cdot\left(\sum_{m\geq
1}\lambda_{m}\xi^{2k}_{m}\right).$

Thus,

$\displaystyle\mathbb{E}\left[\|g\|^{2k}\right]$
$\displaystyle\leq\left(\sum_{m\geq
1}\lambda_{m}\right)^{k-1}\cdot\left(\sum_{m\geq
1}\lambda_{m}\mathbb{E}\left[\xi^{2k}_{m}\right]\right)$
$\displaystyle=\left(\sum_{m\geq
1}\lambda_{m}\right)^{k}\mathbb{E}\left[\xi^{2k}_{1}\right]$
$\displaystyle=\left(\sum_{m\geq 1}\lambda_{m}\right)^{k}\cdot\pi^{-1/2}\cdot
2^{k}\cdot\Gamma(k+1/2)$ $\displaystyle\leq\left(\sum_{m\geq
1}\lambda_{m}\right)^{k}\cdot 2^{k}\cdot k!$
$\displaystyle=(2\lambda_{0})^{k}k!$

[2mm]

###### Lemma 32

For any $\delta>0$, we have

$P\left(\left\|\frac{1}{n}\sum^{n}_{i=1}\left[g_{ij}(t)g_{ij}(s)-K_{jj}(s,t)\right]\right\|_{\text{HS}}>\delta\right)\leq
2\exp\left(-\frac{n\delta^{2}}{64\lambda^{2}_{0,\max}+8\lambda_{0,\max}\delta}\right)$

holding for any $j=1,\ldots,p$.

Proof  Since $g_{ij}(t)=\sum_{m\geq
1}\lambda^{1/2}_{jm}\xi_{ijm}\phi_{jm}(t)$, and $\xi_{ijm}\sim N(0,1)$ i.i.d.
for $m\geq 1$, we have $g_{ij}(s)g_{ij}(t)=\sum_{m,m^{\prime}\geq
1}\lambda^{1/2}_{jm}\lambda^{1/2}_{jm^{\prime}}\xi_{ijm}\xi_{ijm^{\prime}}\phi_{jm}(s)\phi_{jm^{\prime}}(t)$,
and $K_{jj}(s,t)=\mathbb{E}[g_{ij}(s)g_{ij}(t)]=\sum_{m,m^{\prime}\geq
1}\lambda^{1/2}_{jm}\lambda^{1/2}_{jm^{\prime}}\phi_{jm}(s)\phi_{jm^{\prime}}(t)\mathbbm{1}_{mm^{\prime}}$,
where $\mathbbm{1}_{mm^{\prime}}=\mathbbm{1}(m=m^{\prime})=1$ if
$m=m^{\prime}$ and $0$ if $m\neq m^{\prime}$. Thus,

$\left\|g_{ij}(s)g_{ij}(t)-K_{jj}(s,t)\right\|^{2}_{\text{HS}}=\sum_{m,m^{\prime}\geq
1}\lambda_{jm}\lambda_{jm^{\prime}}(\xi_{ijm}\xi_{ijm^{\prime}}-\mathbbm{1}_{mm^{\prime}})^{2},$

and for any $k\geq 2$, we have

$\displaystyle\mathbb{E}\left[\left\|g_{ij}(s)g_{ij}(t)-K_{jj}(s,t)\right\|^{k}_{\text{HS}}\right]$
$\displaystyle=\mathbb{E}\left[\left\\{\sum_{m,m^{\prime}\geq
1}\lambda_{jm}\lambda_{jm^{\prime}}(\xi_{ijm}\xi_{ijm^{\prime}}-\mathbbm{1}_{mm^{\prime}})^{2}\right\\}^{k/2}\right]$
$\displaystyle\overset{(i)}{\leq}\left(\sum_{m,m^{\prime}\geq
1}\lambda_{jm}\lambda_{jm^{\prime}}\right)^{k/2-1}\sum_{m,m^{\prime}\geq
1}\lambda_{jm}\lambda_{jm^{\prime}}\mathbb{E}\left[\left(\xi_{ijm}\xi_{ijm^{\prime}}-\mathbbm{1}_{mm^{\prime}}\right)^{k}\right],$

where $(i)$ follows Jensen’s inequality with convex function
$\psi(x)=x^{k/2}$. Since

$\displaystyle\mathbb{E}\left[\left(\xi_{ijm}\xi_{ijm^{\prime}}-\mathbbm{1}_{mm^{\prime}}\right)^{k}\right]$
$\displaystyle\leq
2^{k-1}\left(\mathbb{E}\left[(\xi_{ijm}\xi_{ijm^{\prime}})^{k}\right]+1\right)$
$\displaystyle\leq 2^{k-1}\left(\mathbb{E}[\xi^{2k}_{ij1}]+1\right)$
$\displaystyle\leq 2^{k-1}(2^{k}k!+1)$ $\displaystyle\leq 4^{k}k!,$

we then have

$\mathbb{E}\left[\left\|g_{ij}(s)g_{ij}(t)-K_{jj}(s,t)\right\|^{k}_{\text{HS}}\right]\leq(4\lambda_{j0})^{k}k!\leq(4\lambda_{0,\max})^{k}k!.$

The final results then follows directly from Lemma 29.  [2mm]

## References

  * Ahmed and Xing (2009) A. Ahmed and E. P. Xing.  Recovering time-varying networks of dependencies in social and biological studies.  _Proc. Natl. Acad. Sci. U.S.A._ , 106(29):11878–11883, 2009.
  * Barron and Sheu (1991) A. R. Barron and C.-H. Sheu.  Approximation of density functions by sequences of exponential families.  _Ann. Statist._ , 19(3):1347–1369, 1991.
  * Beck and Teboulle (2009) A. Beck and M. Teboulle.  A fast iterative shrinkage-thresholding algorithm for linear inverse problems.  _SIAM J. Imag. Sci._ , 2:183–202, 2009.
  * Bosq (2000) D. Bosq.  _Linear processes in function spaces_ , volume 149 of _Lecture Notes in Statistics_.  Springer-Verlag, New York, 2000.  Theory and applications.
  * Boucheron et al. (2013) S. Boucheron, G. Lugosi, and P. Massart.  _Concentration inequalities_.  Oxford University Press, Oxford, 2013.  A nonasymptotic theory of independence, With a foreword by Michel Ledoux.
  * Boyd et al. (2011) S. P. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein.  Distributed optimization and statistical learning via the alternating direction method of multipliers.  _Found. Trends Mach. Learn._ , 3(1):1–122, 2011\.
  * Cai (2017) T. T. Cai.  Global testing and large-scale multiple testing for high-dimensional covariance structures.  _Annual Review of Statistics and Its Application_ , 4(1):423–446, 2017.
  * Cai et al. (2011) T. T. Cai, W. Liu, and X. Luo.  A constrained $\ell_{1}$ minimization approach to sparse precision matrix estimation.  _J. Am. Stat. Assoc._ , 106(494):594–607, 2011\.
  * Chow and Liu (1968) C. K. Chow and C. N. Liu.  Approximating discrete probability distributions with dependence trees.  _IEEE Trans. Inf. Theory_ , 14(3):462–467, 1968\.
  * Danaher et al. (2014) P. Danaher, P. Wang, and D. M. Witten.  The joint graphical lasso for inverse covariance estimation across multiple classes.  _J. R. Stat. Soc. B_ , 76(2):373–397, 2014.
  * Fazayeli and Banerjee (2016) F. Fazayeli and A. Banerjee.  Generalized direct change estimation in Ising model structure.  In M. F. Balcan and K. Q. Weinberger, editors, _Proceedings of The 33rd International Conference on Machine Learning_ , volume 48 of _Proceedings of Machine Learning Research_ , pages 2281–2290, New York, New York, USA, 2016. PMLR.
  * Ghoshal and Honorio (2019) A. Ghoshal and J. Honorio.  Direct estimation of difference between structural equation models in high dimensions.  _arXiv preprint arXiv:1906.12024_ , 2019.
  * Heckler (2005) C. E. Heckler.  Applied multivariate statistical analysis, 2005.
  * Hsing and Eubank (2015) T. Hsing and R. Eubank.  _Theoretical foundations of functional data analysis, with an introduction to linear operators_.  Wiley Series in Probability and Statistics. John Wiley & Sons, Ltd., Chichester, 2015.
  * Ingber (1997) L. Ingber.  Statistical mechanics of neocortical interactions: Canonical momenta indicators of electroencephalography.  _Physical Review E_ , 55(4):4578–4593, 1997.
  * Kim et al. (2019) B. Kim, S. Liu, and M. Kolar.  Two-sample inference for high-dimensional markov networks.  _arXiv preprint arXiv:1905.00466_ , 2019.
  * Knyazev (2007) G. G. Knyazev.  Motivation, emotion, and their inhibitory control mirrored in brain oscillations.  _Neuroscience & Biobehavioral Reviews_, 31(3):377–395, 2007.
  * Kokoszka and Reimherr (2017) P. Kokoszka and M. Reimherr.  _Introduction to functional data analysis_.  Chapman and Hall/CRC, 2017.
  * Kolar and Xing (2009) M. Kolar and E. P. Xing.  Sparsistent estimation of time-varying discrete markov random fields.  _ArXiv e-prints, arXiv:0907.2337_ , 2009.
  * Kolar and Xing (2011) M. Kolar and E. P. Xing.  On time varying undirected graphs.  In _Proc. of AISTATS_ , 2011.
  * Kolar and Xing (2012) M. Kolar and E. P. Xing.  Estimating networks with jumps.  _Electron. J. Stat._ , 6:2069–2106, 2012.
  * Kolar et al. (2009) M. Kolar, L. Song, and E. P. Xing.  Sparsistent learning of varying-coefficient models with structural changes.  In Y. Bengio, D. Schuurmans, J. D. Lafferty, C. K. I. Williams, and A. Culotta, editors, _Proc. of NIPS_ , pages 1006–1014, 2009.
  * Kolar et al. (2010a) M. Kolar, A. P. Parikh, and E. P. Xing.  On sparse nonparametric conditional covariance selection.  In J. Fürnkranz and T. Joachims, editors, _Proc. 27th Int. Conf. Mach. Learn._ , Haifa, Israel, 2010a.
  * Kolar et al. (2010b) M. Kolar, L. Song, A. Ahmed, and E. P. Xing.  Estimating Time-varying networks.  _Ann. Appl. Stat._ , 4(1):94–123, 2010b.
  * Kolar et al. (2013) M. Kolar, H. Liu, and E. P. Xing.  Markov network estimation from multi-attribute data.  In _Proc. of ICML_ , 2013.
  * Kolar et al. (2014) M. Kolar, H. Liu, and E. P. Xing.  Graph estimation from multi-attribute data.  _J. Mach. Learn. Res._ , 15(1):1713–1750, 2014\.
  * Lauritzen (1996) S. L. Lauritzen.  _Graphical Models_ , volume 17 of _Oxford Statistical Science Series_.  The Clarendon Press Oxford University Press, New York, 1996.  Oxford Science Publications.
  * Li and Solea (2018) B. Li and E. Solea.  A nonparametric graphical model for functional data with application to brain networks based on fMRI.  _J. Amer. Statist. Assoc._ , 113(524):1637–1655, 2018.
  * Li et al. (2007) K.-C. Li, A. Palotie, S. Yuan, D. Bronnikov, D. Chen, X. Wei, O.-W. Choi, J. Saarela, and L. Peltonen.  Finding disease candidate genes by liquid association.  _Genome Biology_ , 8(10):R205, 2007.
  * Liu et al. (2014) S. Liu, J. A. Quinn, M. U. Gutmann, T. Suzuki, and M. Sugiyama.  Direct learning of sparse changes in Markov networks by density ratio estimation.  _Neural Comput._ , 26(6):1169–1197, 2014.
  * Liu et al. (2019) X. Liu, H. Nassar, and K. Podgórski.  Splinets–efficient orthonormalization of the b-splines.  _arXiv preprint arXiv:1910.07341_ , 2019.
  * Lu et al. (2018) J. Lu, M. Kolar, and H. Liu.  Post-regularization inference for time-varying nonparanormal graphical models.  _Journal of Machine Learning Research_ , 18(203):1–78, 2018.
  * Meinshausen and Bühlmann (2006) N. Meinshausen and P. Bühlmann.  High dimensional graphs and variable selection with the lasso.  _Ann. Stat._ , 34(3):1436–1462, 2006.
  * Na et al. (2019) S. Na, M. Kolar, and O. Koyejo.  Estimating differential latent variable graphical models with applications to brain connectivity.  _arXiv preprint arXiv:1909.05892_ , 2019, arXiv:1909.05892v1.
  * Negahban et al. (2012) S. N. Negahban, P. Ravikumar, M. J. Wainwright, and B. Yu.  A unified framework for high-dimensional analysis of $m$-estimators with decomposable regularizers.  _Stat. Sci._ , 27(4):538--557, 2012.
  * Newman (2003) M. E. J. Newman.  The structure and function of complex networks.  _SIAM Rev._ , 45(2):167--256, 2003.
  * Parikh and Boyd (2014) N. Parikh and S. P. Boyd.  Proximal algorithms.  _Foundations and Trends in Optimization_ , 1(3):127--239, 2014.
  * Qiao et al. (2019) X. Qiao, S. Guo, and G. M. James.  Functional Graphical Models.  _J. Amer. Statist. Assoc._ , 114(525):211--222, 2019.
  * Qiao et al. (2020) X. Qiao, C. Qian, G. M. James, and S. Guo.  Doubly functional graphical models in high dimensions.  _Biometrika_ , 107(2):415--431, 2020.
  * Ramsay and Silverman (2005) J. O. Ramsay and B. W. Silverman.  _Functional data analysis_.  Springer Series in Statistics. Springer, New York, second edition, 2005\.
  * Ramsay et al. (2020) J. O. Ramsay, H. Wickham, S. Graves, and G. Hooker.  _fda: Functional Data Analysis_ , 2020.  R package version 2.4.8.1.
  * Ravikumar et al. (2011) P. Ravikumar, M. J. Wainwright, G. Raskutti, and B. Yu.  High-dimensional covariance estimation by minimizing $\ell_{1}$-penalized log-determinant divergence.  _Electron. J. Stat._ , 5:935--980, 2011.
  * She (2012) Y. She.  An iterative algorithm for fitting nonconvex penalized generalized linear models with grouped predictors.  _Computational Statistics & Data Analysis_, 56(10):2976--2990, 2012.
  * Song et al. (2009a) L. Song, M. Kolar, and E. P. Xing.  Keller: Estimating time-varying interactions between genes.  _Bioinformatics_ , 25(12):i128--i136, 2009a.
  * Song et al. (2009b) L. Song, M. Kolar, and E. P. Xing.  Time-varying dynamic bayesian networks.  In Y. Bengio, D. Schuurmans, J. D. Lafferty, C. K. I. Williams, and A. Culotta, editors, _Proc. of NIPS_ , pages 1732--1740, 2009b.
  * Spirtes et al. (2000) P. Spirtes, C. Glymour, and R. Scheines.  _Causation, Prediction, And Search_.  Adaptive Computation and Machine Learning. MIT Press, Cambridge, MA, second edition, 2000.  With additional material by David Heckerman, Christopher Meek, Gregory F. Cooper and Thomas Richardson, A Bradford Book.
  * Sugiyama et al. (2008) M. Sugiyama, S. Nakajima, H. Kashima, P. V. Buenau, and M. Kawanabe.  Direct importance estimation with model selection and its application to covariate shift adaptation.  In J. C. Platt, D. Koller, Y. Singer, and S. T. Roweis, editors, _Advances in Neural Information Processing Systems 20_ , pages 1433--1440. Curran Associates, Inc., 2008.
  * Talih and Hengartner (2005) M. Talih and N. Hengartner.  Structural learning with time-varying components: Tracking the cross-section of the financial time series.  _J. R. Stat. Soc. B_ , 67(3):321--341, 2005.
  * Tibshirani (2010) R. Tibshirani.  Proximal gradient descent and acceleration.  _Lecture Notes_ , 2010.
  * van de Geer and Bühlmann (2009) S. A. van de Geer and P. Bühlmann.  On the conditions used to prove oracle results for the lasso.  _Electron. J. Stat._ , 3:1360--1392, 2009.
  * Vogel and Fried (2011) D. Vogel and R. Fried.  Elliptical graphical modelling.  _Biometrika_ , 98(4):935--951, 2011.
  * Wainwright (2019) M. J. Wainwright.  _High-dimensional statistics: A non-asymptotic viewpoint_ , volume 48.  Cambridge University Press, 2019.
  * Wang and Kolar (2014) J. Wang and M. Kolar.  Inference for sparse conditional precision matrices.  _ArXiv e-prints, arXiv:1412.7638_ , 2014, arXiv:1412.7638.
  * Wang et al. (2018) Y. Wang, C. Squires, A. Belyaeva, and C. Uhler.  Direct estimation of differences in causal graphs.  In S. Bengio, H. M. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, _Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, 3-8 December 2018, Montréal, Canada._ , pages 3774--3785, 2018.
  * Wasserman (2006) L. Wasserman.  _All of nonparametric statistics_.  Springer Science & Business Media, 2006.
  * Witten and Tibshirani (2009) D. M. Witten and R. J. Tibshirani.  Covariance-regularized regression and classification for high dimensional problems.  _J. R. Stat. Soc. B_ , 71(3):615--636, 2009.
  * Xu and Gu (2016) P. Xu and Q. Gu.  Semiparametric differential graph models.  In D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett, editors, _Advances in Neural Information Processing Systems 29_ , pages 1064--1072. Curran Associates, Inc., 2016.
  * Xuan and Murphy (2007) X. Xuan and K. Murphy.  Modeling changing dependency structure in multivariate time series.  In _Proc. of ICML_ , ICML ’07, pages 1055--1062, New York, NY, USA, 2007. ACM.
  * Yin et al. (2010) J. Yin, Z. Geng, R. Li, and H. Wang.  Nonparametric covariance model.  _Stat. Sinica_ , 20:469--479, 2010.
  * Yu et al. (2016) M. Yu, V. Gupta, and M. Kolar.  Statistical inference for pairwise graphical models using score matching.  In _Advances in Neural Information Processing Systems 29_. Curran Associates, Inc., 2016.
  * Yu et al. (2019) M. Yu, V. Gupta, and M. Kolar.  Simultaneous inference for pairwise graphical models with generalized score matching.  _arXiv preprint arXiv:1905.06261_ , 2019.
  * Yuan et al. (2017) H. Yuan, R. Xi, C. Chen, and M. Deng.  Differential network analysis via lasso penalized D-trace loss.  _Biometrika_ , 104(4):755--770, 2017.
  * Yuan and Lin (2006) M. Yuan and Y. Lin.  Model selection and estimation in regression with grouped variables.  _J. R. Stat. Soc. B_ , 68:49--67, 2006.
  * Yuan and Lin (2007) M. Yuan and Y. Lin.  Model selection and estimation in the gaussian graphical model.  _Biometrika_ , 94(1):19--35, 2007.
  * Zapata et al. (2019) J. Zapata, S.-Y. Oh, and A. Petersen.  Partial separability and functional graphical models for multivariate gaussian processes.  _arXiv preprint arXiv:1910.03134_ , 2019.
  * Zhang et al. (2018) C. Zhang, H. Yan, S. Lee, and J. Shi.  Dynamic multivariate functional data modeling via sparse subspace learning.  _CoRR_ , abs/1804.03797, 2018, arXiv:1804.03797.
  * Zhang et al. (1995) X. L. Zhang, H. Begleiter, B. Porjesz, W. Wang, and A. Litke.  Event related potentials during object recognition tasks.  _Brain Research Bulletin_ , 38(6):531--538, 1995\.
  * Zhang and Wang (2016) X. Zhang and J.-L. Wang.  From sparse to dense functional data and beyond.  _Ann. Statist._ , 44(5):2281--2321, 2016.
  * Zhao et al. (2019) B. Zhao, Y. S. Wang, and M. Kolar.  Direct estimation of differential functional graphical models.  _arXiv preprint arXiv:1910.09701_ , 2019.
  * Zhao et al. (2014) S. D. Zhao, T. T. Cai, and H. Li.  Direct estimation of differential networks.  _Biometrika_ , 101(2):253--268, 2014.
  * Zhou et al. (2010) S. Zhou, J. D. Lafferty, and L. A. Wasserman.  Time varying undirected graphs.  _Mach. Learn._ , 80(2-3):295--319, 2010.
  * Zhu et al. (2016) H. Zhu, N. Strawn, and D. B. Dunson.  Bayesian graphical models for multivariate functional data.  _J. Mach. Learn. Res._ , 17:Paper No. 204, 27, 2016.