\begin{equation}\label{eq:Gamma_check}
\begin{aligned}
\check{\Gamma} (n,p,M,\delta)
& =  \Gamma (n,p,M,\delta) +  d^2_{j,\text{max}} \sigma_{\text{max},0} \mathcal{Q}^2_{n,p,\delta} \frac{ (1/c_1) \log \left( c_2 / \delta \right)}{n} \\
&\quad +  2 \sqrt{\Xi_2 (M) } d_{j,\text{max}} \sqrt{\sigma_{\text{max},0}} \sqrt{\mathcal{Q}^2_{n,p,\delta}} \sqrt{\frac{ (1/c_1) \log \left( c_2 / \delta \right)}{n}} \cdot \sqrt{\mathcal{Q}^3_{n,p,M,\delta}}.
\end{aligned}
\end{equation}

As in the proof of Theorem <ref>, we omit the basis dimension, $M$, and let $\bm{\hat{a}^Y_i}=\bm{\hat{a}^Y_{i,M}}$, $\bm{\hat{a}^{X_k}_i} = \bm{\hat{a}^{X_k}_{i,M}}$, and $\bm{B^*_k}=\bm{B^{\ast}_{k, M}}$ for all $k \in [p-1]$.
Then by (<ref>), for all $i \in [n]$, we have

\begin{equation}\label{eq:score-equation-approx}
\bm{\hat{a}^{Y}_i} = \sum^{p-1}_{k=1} \bm{B^{\ast}_{k}} \bm{\hat{a}^{X_k}_i} + \bm{\tilde{u}}_i,
\end{equation}

where $\bm{\tilde{u}_i}=\bm{w_i}+\bm{r_i}+\bm{v_i}$, and $\bm{w_i}$, $\bm{r_i}$, $\bm{v_i}$ are defined in Appendix <ref>.
We now give the proof of Theorem <ref>.

\begin{equation*}
\bm{\hat{A}^X} =
\begin{bmatrix}
(\bm{\hat{a}^{X_1}_1})^{\top} &  (\bm{\hat{a}^{X_2}_1})^{\top} & \cdots & (\bm{\hat{a}^{X_{p-1}}_1})^{\top} \\
(\bm{\hat{a}^{X_1}_2})^{\top} &  (\bm{\hat{a}^{X_2}_2})^{\top} & \cdots & (\bm{\hat{a}^{X_{p-1}}_2})^{\top} \\
\vdots & & \vdots \\
(\bm{\hat{a}^{X_1}_n})^{\top} &  (\bm{\hat{a}^{X_2}_n})^{\top} & \cdots & (\bm{\hat{a}^{X_{p-1}}_n})^{\top} \\
\end{bmatrix}
\in \mathbb{R}^{n \times (p-1) M}.
\end{equation*}

We divide columns of $\bm{\hat{A}^X}$ into $p-1$ groups with equal group size $M$, that is,

where $\bm{\hat{A}^{X_k}} \in \mathbb{R}^{n \times M}$ for all $k \in [p-1]$.
Let $\bm{\hat{Z}}=\bm{\hat{A}^X} \otimes \bm{I_M}$.
Similarly, we divide the columns of $\bm{\hat{Z}}$ into $p-1$ groups with equal group size $M^2$, that is, $\bm{\hat{Z}^X}=[\bm{\hat{Z}^{X_1}},\bm{\hat{Z}^{X_2}},\dots,\bm{\hat{Z}^{X_{p-1}}}]$, where $\bm{\hat{Z}^{X_k}}\in\mathbb{R}^{nM\times M^2}$ for all $k\in [p-1]$. Then, we have $(\bm{\hat{Z}}^{\top}\bm{u})_{k}=\bm{\hat{Z}_k}^{\top}\bm{u}$.
By definition of $\bm{\hat{Z}}$, it is easy to see that $\bm{\hat{Z}_k}=\bm{\hat{A}^{X_k}}\otimes \bm{I_M}$.
In addition, let
$\bm{\hat{a}^{Y}}=((\bm{\hat{a}^Y_1})^{\top}, \cdots, (\bm{\hat{a}^Y_n})^{\top})^{\top} \in \mathbb{R}^{nM}$.
Furthermore, let
$\bm{\tilde{\Sigma}^X_n}=\frac{1}{n}(\bm{\hat{A}^X})^{\top} \bm{\hat{A}^X}$.
Thus, we can rewrite (<ref>) as

\begin{equation*}
\bm{\hat{\beta}} = \argmin_{\bm{\beta}} \left\{ \hat{\mathcal{L}}(\bm{\beta}) + \lambda_n \mathcal{R}(\bm{\beta}) \right\},
\end{equation*}

\begin{align*}
\hat{\mathcal{L}}(\bm{\beta}) & =  \frac{1}{2n} \Vert \bm{\hat{a}^Y} - \bm{\hat{Z}} \bm{\beta} \Vert^2_2, \\
\mathcal{R}(\bm{\beta}) & =  \sum^{p-1}_{k=1} \Vert \bm{\beta_k} \Vert_2,
\end{align*}

and $\bm{\beta}=((\bm{\beta_1})^{\top},\dots,(\bm{\beta_{p-1}})^{\top})^{\top} \in \mathbb{R}^{(p-1)M^2}$, with $\bm{\beta_k} \in \mathbb{R}^{M^2}$ for $k \in [p-1]$.

We can then follow the similar proof of Theorem <ref> to prove Theorem <ref>. The only two modifications needed are new upper bounds for $\frac{2}{n} \max_{k \in [p-1]} \Vert (\bm{\hat{Z}}^{\top} \bm{\tilde{u}})_{k} \Vert_2$ and $\vertiii{\bm{\tilde{\Sigma}^X_n}-\bm{\Sigma^{X}}}_{\infty}$. In fact, when we have

\begin{equation}
\label{eq:thm2-proof-helper}
\lambda_n = \check{\lambda} (n,p,M,\delta) \geq \frac{2}{n} \max_{k \in [p-1]}  \Vert (\bm{\hat{Z}}^{\top} \bm{\tilde{u}} )_{k} \Vert_2 \, \text{ and } \, \vertiii{\bm{\tilde{\Sigma}^X_n}-\bm{\Sigma^{X}}}_{\infty} \leq  \check{\Gamma} (n,p,M,\delta)
\end{equation}

hold, where $\check{\chi} (n,p,M,\delta)$ is defined in (<ref>), then by the similar argument in the proof of Theorem <ref>, we can show that

\begin{equation*}
\sqrt{\sum^{p-1}_{k=1} \left\Vert \hat{\bm{B_k}} - \bm{B^*_k} \right\Vert^2_{\text{F}}} \leq \check{\chi} (n,p,M,\delta) + 12 \sqrt{s} \frac{\omega (M)}{ \sqrt{\kappa(M)}},
\end{equation*}

which further implies that $\hat{\mathscr{N}}_j=\mathscr{N}_j$. Thus, to show that $\hat{\mathscr{N}}_j=\mathscr{N}_j$ holds with high probability, we only need to prove that (<ref>) holds with high probability.

We define the following events.

\begin{align*}
\mathcal{A}_1 & =  \left\{ \frac{1}{n} \sum^n_{i=1} \Vert g^{(i)}_j \Vert^2 \leq  \sigma_{\text{max},0} \mathcal{Q}^2_{n,p,\delta} \, \text{ for all } j \in [p]  \right\}, \\
\mathcal{A}_2 & =  \left\{ \frac{1}{n} \sum^n_{i=1} \Vert e^{(i)} \Vert^2 \leq  \sigma_{jr} \mathcal{Q}^1_{n,p,\delta} \right\}, \\
\mathcal{A}_3 & =  \left\{ \frac{1}{n} \sum^n_{i=1} \Vert \bm{r_i} + \bm{w_i} \Vert^2_2 \leq  \Xi_4 (M) \mathcal{Q}^1_{n,p,\delta} \right\}, \\
\mathcal{A}_4 & =  \left\{ \frac{1}{n} \sum^n_{i=1} \Vert \bm{a^{X_k}}_i \Vert^2_2 \leq \tr \left(\bm{\Sigma^X_{kk}}\right) \mathcal{Q}^2_{n,p-1,\delta} \, \text{ for all } k \in [p-1] \right\}, \\
\mathcal{A}_5 & =  \left\{ \frac{2}{n} \max_{k \in [p-1]} \Vert (\bm{Z}^{\top} (\bm{w}+\bm{r}) )_{k} \Vert_2 \leq \tilde{\lambda} (n,p,M,\delta) \right\}, \\
\mathcal{A}_6 & =  \left\{ \vertiii{\bm{\hat{\Sigma}^X_n}-\bm{\Sigma^{X}}}_{\infty} \leq \Gamma (n,p,M,\delta)  \right\}, \\
\mathcal{A}_7 & =  \left\{ \frac{1}{n} \sum^n_{i=1} \Vert a^{X_k}_{i m} \Vert^2_2 \leq \Xi_2 (M) \mathcal{Q}^3_{n,p,\delta} \, \text{ for all } m \in [M] \text{ and } k \in [p-1] \right\},
\end{align*}

where $\tilde{\lambda} (n,p,M,\delta)$ is defined in (<ref>). Then we claim that under Assumption <ref>, we have

\begin{equation}\label{eq:claim2proof}
\cap^{7}_{i=1} \mathcal{A}_i \Longrightarrow \frac{2}{n} \max_{k \in [p-1]} \Vert (\bm{\hat{Z}}^{\top} \bm{\tilde{u}} )_{k} \Vert_2 \leq \check{\lambda} (n,p,M,\delta) \, \text{and} \, \vertiii{\bm{\tilde{\Sigma}^X_n}-\bm{\Sigma^{X}}}_{\infty} \leq  \check{\Gamma} (n,p,M,\delta).
\end{equation}

We now prove the above claim. We first prove that $\cap^{7}_{i=1} \mathcal{A}_i$ implies that $\frac{2}{n} \max_{k \in [p-1]} \Vert (\bm{\hat{Z}}^{\top} \bm{\tilde{u}} )_{k} \Vert_2 \leq \check{\lambda} (n,p,M,\delta)$. Note that for all $k \in [p-1]$, we have

\begin{align*}
\Vert (\bm{\hat{Z}}^{\top} \bm{\tilde{u}} )_{k} \Vert_2 & = \Vert \bm{\hat{Z}_k}^{\top} \bm{\tilde{u}} \Vert_2 \leq \Vert (\bm{\hat{Z}_k} - \bm{Z}_k)^{\top}\bm{\tilde{u}} \Vert_2 + \Vert \bm{Z}_k^{\top}\bm{\tilde{u}} \Vert_2 \\
& = \Vert (\bm{\hat{Z}_k} - \bm{Z}_k)^{\top}\bm{\tilde{u}} \Vert_2 + \Vert \bm{Z_k}^{\top} (\bm{w}+\bm{r}+\bm{v}) \Vert_2 \\
& \leq \Vert (\bm{\hat{Z}_k} - \bm{Z}_k)^{\top}\bm{\tilde{u}} \Vert_2 + \Vert \bm{Z_k}^{\top} (\bm{w}+\bm{r}) \Vert_2 + \Vert \bm{Z_k}^{\top} \bm{v} \Vert_2,
\end{align*}

where $\bm{v} = (v_{im})_{\{m \in [M]\}}$ with $v_{im}$ defined in (<ref>).
The above inequality implies that

\begin{multline}\label{eq:Zu-decompose}
\frac{2}{n} \max_{k \in [p-1]} \Vert (\bm{Z}^{\top} \bm{u} )_{k} \Vert_2 \leq \frac{2}{n} \max_{k \in [p-1]} \Vert (\bm{\hat{Z}_k} - \bm{Z}_k)^{\top}\bm{\tilde{u}} \Vert_2 +  \frac{2}{n} \max_{k \in [p-1]} \Vert \bm{Z_k}^{\top} (\bm{w}+\bm{r}) \Vert_2 + \frac{2}{n} \max_{k \in [p-1]} \Vert \bm{Z_k}^{\top} \bm{v} \Vert_2
\end{multline}

By $\mathcal{A}_5$, we have the second term to be bounded by $\tilde{\lambda}(n,p,M,\delta)$. To bound the third term, note that

\begin{equation}
\label{eq:proof-thm2-helper1}
\left\Vert \frac{1}{n} \bm{Z_k}^{\top} \bm{v} \right\Vert_2 = \left\Vert \frac{1}{n} (\bm{A^{X_k}} \otimes \bm{I_M})^{\top} \bm{v} \right\Vert_2 = \left\Vert \frac{1}{n} \sum^n_{i=1} (\bm{a^{X_k}_i} \otimes \bm{I_M}) \bm{v_i} \right\Vert_{2} = \left\Vert \frac{1}{n} \sum^n_{i=1} \bm{a^{X_k}_i} \bm{v_i}^{\top} \right\Vert_{\text{F}},
\end{equation}

and by Lemma <ref>, we further have

\begin{equation}
\label{eq:proof-thm2-helper2}
\left\Vert \frac{1}{n} \bm{Z_k}^{\top} \bm{v} \right\Vert_2 \leq \sqrt{\frac{1}{n} \sum^n_{i=1} \left\Vert \bm{a^{X_k}_i} \right\Vert^2_2 } \sqrt{\frac{1}{n} \sum^n_{i=1} \left\Vert \bm{v_i} \right\Vert^2_2 }.
\end{equation}

By Lemma <ref> with

\begin{align*}
\Gamma_g(j) & = \sigma_{\text{max},0} \mathcal{Q}^2_{n,p,\delta} \, \text{ for all } j \in [p] \\
\Gamma_e & = \sigma_{jr} \mathcal{Q}^1_{n,\delta} \\
\Gamma_{\phi}(m) & = d_{jm} \sqrt{\frac{ (1/c_1) \log \left( c_2 / \delta \right)}{n}}
\end{align*}

because of $\mathcal{A}_1$, $\mathcal{A}_2$ and Assumption <ref>, we have

\begin{equation}
\label{eq:def-Gamma_v}
\frac{1}{n} \sum^n_{i=1} \Vert \bm{v_i} \Vert^2 \leq \Gamma_v,
\end{equation}

where $\Gamma_v$ is defined by (<ref>).
And combine with $\mathcal{A}_4$, we have

\begin{align*}
& \left\Vert \frac{2}{n} \bm{Z_k}^{\top} \bm{v} \right\Vert_2 \leq 2 \sqrt{\frac{1}{n} \sum^n_{i=1} \left\Vert \bm{a^{X_k}_i} \right\Vert^2_2 } \sqrt{\frac{1}{n} \sum^n_{i=1} \left\Vert \bm{v_i} \right\Vert^2_2 } \leq  2 \sqrt{ \tr \left(\bm{\Sigma^X_{kk}}\right)} \sqrt{\mathcal{Q}^2_{n,p-1,\delta}}\cdot \Gamma^{1/2}_v.
\end{align*}

Finally, to bound the first term in (<ref>), by similar arguments as (<ref>) and (<ref>), we have

\begin{equation}
\label{eq:proof-thm2-helper3}
\left\Vert \frac{1}{n} (\bm{\hat{Z}_k} -\bm{Z_k})^{\top} \bm{\tilde{u}} \right\Vert_2 \leq \sqrt{\frac{1}{n} \sum^n_{i=1} \left\Vert \bm{\hat{a}^{X_k}_i} - \bm{a^{X_k}_i} \right\Vert^2_2 } \sqrt{\frac{1}{n} \sum^n_{i=1} \left\Vert \bm{\tilde{u}_i} \right\Vert^2_2 }.
\end{equation}

Since we have

\begin{align*}
\frac{1}{n} \sum^n_{i=1} \left\Vert \bm{\hat{a}^{X_k}_i} - \bm{a^{X_k}_i} \right\Vert^2_2 & \leq \left( \frac{1}{n} \sum^n_{i=1} \Vert g_{ik} \Vert^2 \right) \sum^M_{m=1} \Vert \hat{\phi}_m - \phi_m \Vert^2 \\
& \leq \sigma_{\text{max},0} \mathcal{Q}^2_{n,p,\delta} \frac{(1/c_1)\log(c_2/\delta)}{n} d^2_{js}(M)
\end{align*}

by $\mathcal{A}_1$ and Assumption <ref>,

\begin{align*}
\sqrt{\frac{1}{n} \sum^n_{i=1} \left\Vert \bm{\tilde{u}_i} \right\Vert^2_2} & \leq \sqrt{\frac{1}{n} \sum^n_{i=1} \left\Vert \bm{r_i} + \bm{w_i} \right\Vert^2_2} + \sqrt{\frac{1}{n} \sum^n_{i=1} \left\Vert \bm{v_i} \right\Vert^2_2} \\
& \leq \sqrt{\Xi_4 (M)} \sqrt{ \mathcal{Q}^1_{n,\delta} } + \Gamma^{1/2}_v
\end{align*}

by $\mathcal{A}_3$ and (<ref>), then by (<ref>), we have

\begin{multline*}
\left\Vert \frac{1}{n} (\bm{\hat{Z}_k} -\bm{Z_k})^{\top} \bm{\tilde{u}} \right\Vert_2 \leq \sqrt{\sigma_{\text{max},0}} \sqrt{ \mathcal{Q}^2_{n,p,\delta} } \sqrt{\frac{(1/c_1)\log(c_2/\delta)}{n}} d_{js}(M) \cdot \left( \sqrt{\Xi_4 (M)} \sqrt{ \mathcal{Q}^1_{n,\delta} } + \Gamma^{1/2}_v \right).
\end{multline*}

Thus, combine the bounds of three terms in (<ref>) and by the definition of $\check{\lambda}(n,p,M,\delta)$ in (<ref>), we have

\begin{equation*}
\frac{2}{n} \max_{k \in [p-1]} \left\Vert \bm{Z_k}^{\top} \bm{v} \right\Vert_2 \leq \check{\lambda}(n,p,M,\delta).
\end{equation*}

We then prove that $\cap^{7}_{i=1} \mathcal{A}_i$ implies that $\vertiii{\bm{\tilde{\Sigma}^X_n}-\bm{\Sigma^{X}}}_{\infty} \leq \check{\Gamma} (n,p,M,\delta)$. Note that

$$\vertiii{\bm{\tilde{\Sigma}^X_n}-\bm{\Sigma^{X}}}_{\infty} \leq \vertiii{\bm{ \tilde{\Sigma}^{X}} - \bm{\hat{\Sigma}^X_n} }_{\infty} + \vertiii{ \bm{\hat{\Sigma}^X_n} -\bm{\Sigma^{X}} }_{\infty},

and by $\mathcal{A}_6$, we thus only need to prove that $\vertiii{\bm{ \tilde{\Sigma}^{X}} - \bm{\hat{\Sigma}^X_n} }_{\infty} \leq \check{\Gamma}(n,p,M,\delta)-\Gamma(n,p,M,\delta)$. Note that

\begin{align*}
\vertiii{\bm{ \tilde{\Sigma}^{X}} - \bm{\hat{\Sigma}^X_n} }_{\infty} & =  \max_{1 \leq k, k^{\prime} \leq p-1} \vertiii{ \frac{1}{n} (\bm{ \hat{A}^{X_k} })^{\top} \bm{ \hat{A}^{X_{k^{\prime}}} } - \frac{1}{n} \bm{ (A^{X_k} })^{\top} \bm{ A^{X_{k^{\prime}}} } }_{\infty} \\
& =  \max_{1 \leq k, k^{\prime} \leq p-1}  \max_{1 \leq m, m^{\prime} \leq M} \left\vert \frac{1}{n} \sum^n_{i=1} \hat{a}^{X_k}_{im} \hat{a}^{X_{k^{\prime}}}_{im^{\prime}} - a^{X_{k}}_{im} a^{X_{k^{\prime}}}_{im^{\prime}} \right\vert, \numberthis \label{eq:intermi-step-1}
\end{align*}

\begin{align*}
& \left\vert \frac{1}{n} \sum^n_{i=1} \hat{a}^{X_k}_{im} \hat{a}^{X_{k^{\prime}}}_{im^{\prime}} - a^{X_{k}}_{im} a^{X_{k^{\prime}}}_{im^{\prime}} \right\vert \\
& =  \left\vert \frac{1}{n} \sum^n_{i=1} \left( \hat{a}^{X_k}_{im} -  a^{X_{k}}_{im} \right) \left( \hat{a}^{X_{k^{\prime}}}_{im^{\prime}} - a^{X_{k^{\prime}}}_{im^{\prime}}\right) + \frac{1}{n} \sum^n_{i=1} a^{X_{k}}_{im} \left( \hat{a}^{X_{k^{\prime}}}_{im^{\prime}} - a^{X_{k^{\prime}}}_{im^{\prime}}\right) + \frac{1}{n} \sum^n_{i=1} a^{X_{k^{\prime}}}_{im^{\prime}} \left( \hat{a}^{X_k}_{im} -  a^{X_{k}}_{im} \right) \right\vert \\
& \leq  \left\vert \frac{1}{n} \sum^n_{i=1} \left( \hat{a}^{X_k}_{im} -  a^{X_{k}}_{im} \right) \left( \hat{a}^{X_{k^{\prime}}}_{im^{\prime}} - a^{X_{k^{\prime}}}_{im^{\prime}} \right) \right\vert + \left\vert \frac{1}{n} \sum^n_{i=1} a^{X_{k}}_{im} \left( \hat{a}^{X_{k^{\prime}}}_{im^{\prime}} - a^{X_{k^{\prime}}}_{im^{\prime}}\right) \right\vert + \left\vert \frac{1}{n} \sum^n_{i=1} a^{X_{k^{\prime}}}_{im^{\prime}} \left( \hat{a}^{X_k}_{im} -  a^{X_{k}}_{im} \right) \right\vert \\
& \leq   \sqrt{\frac{1}{n} \sum^n_{i=1} \left( \hat{a}^{X_k}_{im} -  a^{X_{k}}_{im} \right)^2} \sqrt{\frac{1}{n} \sum^n_{i=1} \left( \hat{a}^{X_{k^{\prime}}}_{im^{\prime}} - a^{X_{k^{\prime}}}_{im^{\prime}} \right)^2} + \sqrt{\frac{1}{n} \sum^n_{i=1} \left( \hat{a}^{X_k}_{im} \right)^2} \sqrt{\frac{1}{n} \sum^n_{i=1} \left( \hat{a}^{X_{k^{\prime}}}_{im^{\prime}} - a^{X_{k^{\prime}}}_{im^{\prime}} \right)^2} \\
+ &  \sqrt{\frac{1}{n} \sum^n_{i=1} \left( a^{X_{k^{\prime}}}_{im^{\prime}} \right)^2} \sqrt{\frac{1}{n} \sum^n_{i=1} \left( \hat{a}^{X_k}_{im} -  a^{X_{k}}_{im} \right)^2}. \numberthis \label{eq:intermi-step-2}
\end{align*}

By Lemma <ref> with

\begin{align*}
\Gamma_g(j) & = \sigma_{\text{max},0} \mathcal{Q}^2_{n,p,\delta} \, \text{ for all } j \in [p], \\
\Gamma_{\phi}(m) & = d_{jm} \sqrt{\frac{ (1/c_1) \log \left( c_2 / \delta \right)}{n}},
\end{align*}

we have

\begin{equation*}
\frac{1}{n} \sum^n_{i=1} \left( \hat{a}^{X_k}_{im} - a^{X_k}_{im} \right)^2 \leq  d^2_{j,\text{max}} \sigma_{\text{max},0} \mathcal{Q}^2_{n,p,\delta} \frac{ (1/c_1) \log \left( c_2 / \delta \right)}{n}
\end{equation*}

for all $m \in [M]$ and $k \in [p-1]$. And by $\mathcal{A}_7$, we have

\begin{equation*}
\frac{1}{n} \sum^n_{i=1} \Vert a^{X_k}_{i m} \Vert^2_2 \leq \Xi_2 (M) \mathcal{Q}^3_{n,p,\delta}
\end{equation*}

for all $m \in [M]$ and $k \in [p-1]$. Combine with (<ref>) and (<ref>), we have

\begin{align*}
& \vertiii{\bm{ \tilde{\Sigma}^{X}} - \bm{\hat{\Sigma}^X_n} }_{\infty} \\
\leq \, &  d^2_{j,\text{max}} \sigma_{\text{max},0} \mathcal{Q}^2_{n,p,\delta} \frac{ (1/c_1) \log \left( c_2 / \delta \right)}{n} \\
+ & 2 \sqrt{\Xi_2 (M) } d_{j,\text{max}} \sqrt{\sigma_{\text{max},0}} \sqrt{\mathcal{Q}^2_{n,p,\delta}} \sqrt{\frac{ (1/c_1) \log \left( c_2 / \delta \right)}{n}} \cdot \sqrt{\mathcal{Q}^3_{n,p,M\delta}} \\
& =  \check{\Gamma}(n,p,M,\delta)-\Gamma(n,p,M,\delta) \leq \check{\Gamma}(n,p,M,\delta).
\end{align*}

Therefore, by (<ref>) and Lemma <ref>, Lemma <ref>, Lemma <ref> and Lemma <ref>, we have

\begin{align*}
& \mathbb{P} \left\{ \frac{2}{n} \max_{k \in [p-1]}  \Vert (\bm{Z}^{\top} \bm{u} )_{k} \Vert_2 \leq \check{\lambda} (n,p,M,\delta) \, \text{and} \, \vertiii{\bm{\tilde{\Sigma}^X_n}-\bm{\Sigma^{X}}}_{\infty} \leq  \check{\Gamma} (n,p,M,\delta) \right\} \\
& \geq  1 - \mathbb{P} \left\{ \cup^7_{i=1} \bar{\mathcal{A}}_i \right\} \\
& \geq  1 - 8 \delta.
\end{align*}

Finally, we only need $n$ large enough such that $\check{\Gamma} (n,p,M,\delta) \leq \kappa(M) / (32 M^2 s)$ and $\check{\chi} (n,p,M,\delta) \leq \nu (M)/3$ where $\check{\chi} (n,p,M,\delta)$ is defined in (<ref>). After dropping $\log(n)$ term, to satisfy the first condition, we need

\begin{equation*}
n \geq O \left(  \frac{ M^4 s^2 \log (p^2 M^2 /\delta) }{\kappa^2 (M)} \right),
\end{equation*}

and to satisfy the second condition, we need

\begin{equation*}
n \geq O \left( \frac{ \max \left\{ sM^2, s\log (p/\delta), sM^2 \omega^2 (M) \log (M^2 p /\delta), s^3 M^2 (\log(1/\delta)^2), s (d^2_{j0}-d^2_{js}(M) \Phi^2(M)) \right\} }{\kappa (M) \nu^2 (M)} \right).
\end{equation*}

Then combine the above results and note that decreasing $8\delta$ to $\delta$ doesn't affect the asymptotic order of $n$, we the have the final result.

§.§ Proposition <ref> and its Proof

Let $\mathbb{H}$ be a separable Hilbert space of functions defined on a compact domain $\mathcal{T} \subseteq \mathbb{R}$. For $f,g \in \mathbb{H}$, let $\langle f,g \rangle=\int_{\mathcal{T}} f(t) g(t) dt$. Assume that $\beta(s,t)$ is the kernel function of an integral operator $\mathcal{K}:\mathbb{H} \mapsto \mathbb{H}$, where $(s,t) \in \mathcal{T}^2$, that is, we have $\int_{\mathcal{T}}\beta(\cdot,s) f(s) ds \in \mathbb{H}$. Recall that we define the Hilbert Schmidt norm of $\beta(s,t)$ as $\Vert \beta(s,t) \Vert^2_{\text{HS}}=\int_{\mathcal{T}}\int_{\mathcal{T}} \beta^2(s,t)ds dt$. We assume that $\Vert \beta(s,t) \Vert_{\text{HS}}< \infty$. Let $\{\phi_{m}(\cdot)\}^{\infty}_{m=1}$ be an orthonormal basis of $\mathbb{H}$.

Let $\{\phi_{m}(\cdot)\}^{\infty}_{m=1}$ be any orthonormal basis of $\mathbb{H}$ and $\beta(s,t)$ be a bivariate function on $\mathcal{T}\times \mathcal{T}$ such that $\Vert \beta(s,t) \Vert_{\text{HS}}<\infty$, we then have

\begin{equation*}
\beta (s,t) = \sum^{\infty}_{m=1} \sum^{\infty}_{m^{\prime}=1} b_{m m^{\prime}} \phi_m (s) \phi_{m^{\prime}} (t)\quad \text{almost everywhere},
\end{equation*}

\begin{equation*}
b_{m m^{\prime}} = \int_{\mathcal{T}} \int_{\mathcal{T}} \beta (s,t) \phi_m (s) \phi_{m^{\prime}} (t) ds dt.
\end{equation*}

Let $\check{\beta}(s,t)=\sum^{\infty}_{m=1} \sum^{\infty}_{m^{\prime}=1} b_{m m^{\prime}} \phi_m (s) \phi_{m^{\prime}} (t)$. We only need to prove that $\beta(s,t)=\check{\beta}(s,t)$ a.e.. Or equivalently, we only need to show that $\Vert \beta(s,t) -  \check{\beta}(s,t) \Vert_{\text{HS}}=0$.

First, we show that $ \sum^{\infty}_{m=1}\sum^{\infty}_{m^{\prime}=1} b^2_{m m^{\prime}}=\Vert \beta(s,t) \Vert^2_{\text{HS}}<\infty$. For any $m\geq 1$, we have $\int_{\mathcal{T}} \beta (s, \cdot) \phi_m (s) ds \in \mathbb{H}$. Since $\{\phi_{m}(\cdot)\}^{\infty}_{m=1}$ is an orthonormal basis of $\mathbb{H}$, by Parseval's relation (Theorem 2.4.13 of [10]), we have

\begin{align*}
\sum^{\infty}_{m^{\prime}=1} b^2_{m m^{\prime}} = \sum^{\infty}_{m^{\prime}=1} \left( \int_{\mathcal{T}} \left( \int_{\mathcal{T}} \beta (s,t) \phi_m (s) ds \right) \phi_{m^{\prime}} (t)  dt \right)^2
= \int_{\mathcal{T}} \left( \int_{\mathcal{T}} \beta (s,t) \phi_m (s) ds \right)^2 dt,
\end{align*}

which further implies that

\begin{align*}
\sum^{\infty}_{m=1}\sum^{\infty}_{m^{\prime}=1} b^2_{m m^{\prime}} & = \sum^{\infty}_{m=1}  \int_{\mathcal{T}} \left( \int_{\mathcal{T}} \beta (s,t) \phi_m (s) ds \right)^2 dt \\
& = \int_{\mathcal{T}} \left\{ \sum^{\infty}_{m=1}  \left( \int_{\mathcal{T}} \beta (s,t) \phi_m (s) ds \right)^2 \right\} dt
= \int_{\mathcal{T}} \int_{\mathcal{T}} \beta^2(s,t) ds dt
= \Vert \beta (s,t) \Vert^2_{\text{HS}} < \infty, \numberthis \label{eq:integ-kernel-representation-1}
\end{align*}

where in the second equality we can change the order of integration and summation using Fubini's Theorem (Theorem 1.7.2 of [7]) and the assumption that $\Vert \beta (s,t) \Vert_{\text{HS}}<\infty$, while the last equality is by Parseval's relation.

Let $\check{\beta}^M(s,t)=\sum_{m \leq M \,\text{or}\, m^{\prime} \leq M} b_{m m^{\prime}} \phi_m (s) \phi_{m^{\prime}} (t)$. Then

\begin{equation*}
\Vert \check{\beta}^M(s,t) \Vert^2_{\text{HS}}=\sum_{m \leq M \,\text{or}\, m^{\prime} \leq M} b^2_{m m^{\prime}}
\end{equation*}

\begin{equation*}
\Vert \check{\beta}(s,t) - \check{\beta}^M(s,t) \Vert^2_{\text{HS}} = \left\Vert \sum^{\infty}_{m>M} \sum^{\infty}_{m^{\prime}>M} b_{m m^{\prime}} \phi_m (s) \phi_{m^{\prime}} (t) \right\Vert^2_{\text{HS}} = \sum^{\infty}_{m>M} \sum^{\infty}_{m^{\prime}>M} b^2_{m m^{\prime}}.
\end{equation*}

Thus, by (<ref>), $\lim_{M \to \infty} \Vert \check{\beta}(s,t) - \check{\beta}^M(s,t) \Vert_{\text{HS}}=0$. Therefore, to show that $\check{\beta}(s,t)=\beta(s,t)$ a.e., we only need to show that $\lim_{M \to \infty} \Vert \beta(s,t) - \check{\beta}^M(s,t) \Vert_{\text{HS}}=0$.
To see why, note that
$\Vert \beta(s,t) -  \check{\beta}(s,t) \Vert_{\text{HS}} \leq \Vert \beta(s,t) -  \check{\beta}^M(s,t) \Vert_{\text{HS}} + \Vert \check{\beta}(s,t) -\check{\beta}^M(s,t) \Vert_{\text{HS}}$ for any $M$. Letting $M \to \infty$, we then have $\Vert \beta(s,t) -  \check{\beta}(s,t) \Vert_{\text{HS}}=0$, which implies that $\check{\beta}(s,t)=\beta(s,t)$ a.e..

To prove that $\lim_{M \to \infty} \Vert \beta(s,t) - \check{\beta}^M(s,t) \Vert_{\text{HS}}=0$, note that

\begin{align*}
\int_{\mathcal{T}} \int_{\mathcal{T}} \beta(s,t) \check{\beta}^M(s,t) ds dt & = \int_{\mathcal{T}} \int_{\mathcal{T}} \sum_{m \leq M \,\text{or}\, m^{\prime} \leq M} b_{m m^{\prime}} \beta(s,t) \phi_m (s) \phi_{m^{\prime}} (t)  ds dt \\
& = \sum_{m \leq M \,\text{or}\, m^{\prime} \leq M} b_{m m^{\prime}}  \int_{\mathcal{T}} \int_{\mathcal{T}} \beta(s,t) \phi_m (s) \phi_{m^{\prime}} (t)  ds dt \\
& = \sum_{m \leq M \,\text{or}\, m^{\prime} \leq M} b^2_{m m^{\prime}}
= \Vert \check{\beta}^M(s,t) \Vert^2_{\text{HS}},
\end{align*}

we have

\begin{align*}
\Vert \beta(s,t) - \check{\beta}^M(s,t) \Vert^2_{\text{HS}}
& = \Vert \beta(s,t) \Vert^2_{\text{HS}} + \Vert \check{\beta}^M(s,t) \Vert^2_{\text{HS}} - 2 \int_{\mathcal{T}} \int_{\mathcal{T}} \beta(s,t) \check{\beta}^M(s,t) ds dt \\
& =  \Vert \beta(s,t) \Vert^2_{\text{HS}} - \Vert \check{\beta}^M(s,t) \Vert^2_{\text{HS}}.
\end{align*}

Then, by (<ref>), $\lim_{M \to \infty} \Vert \beta(s,t) - \check{\beta}^M(s,t) \Vert_{\text{HS}}=0$, which completes the proof.

§ USEFUL LEMMAS

Recall that $\mathcal{C}_{n,\delta}$ is defined in (<ref>) and $\mathcal{Q}^1_{n,\delta}$, $\mathcal{Q}^2_{n,p,\delta}$, and $\mathcal{Q}^1_{n,p, M,\delta}$ are defined in (<ref>).

Let $\delta \in (0, 1]$. Then $\max_{k \in[p-1]}\Vert \bm{A^{X_k}} \Vert_2/\sqrt{n}\leq \mathcal{C}_{n,\delta}$ with probability at least $1-\delta$.

The result follows directly from Theorem 6.1 of 35 and a union bound.

Suppose $\max_{k \in [p-1]}\Vert \bm{A^{X_k}} \Vert_2/\sqrt{n}\leq \mathcal{C}_{n,\delta_1}$ for some $0<\delta_1 \leq 1$. Then there exists a constant $c>0$ such that

\begin{multline*}
\max_{k \in [p-1]} \left\Vert \frac{1}{n} \bm{Z_k}^\top \bm{u} \right\Vert_2
\leq  \frac{M \mathcal{C}_{n,\delta_1} \sqrt{ \Xi_1(M) }}{\sqrt{n}}+ 2 \mathcal{C}_{n,\delta_1} \sqrt{\Xi_1 (M)} \sqrt{ \frac{ \log (4(p-1)/\delta_2) }{n} } \\
+   \omega(M) \left\{ 1 + 7\sqrt{3} \frac{M \sqrt{ \log (6(p-1)/\delta_2) + 2 \log M}}{\sqrt{n}} + \right. \\
\left. \frac{8 c}{3} \frac{ M (\log (2n)) (\log (6(p-1)/\delta_2) + 2\log M) }{n} \right\}
\end{multline*}

holds with probability at least $1-\delta_2$, $\delta_2 \in (0, 1]$.

Note that $\Vert \bm{Z_k} \Vert_2=\Vert \bm{A^{X_k}} \otimes \bm{I_M} \Vert_2 = \Vert \bm{A^{X_k}} \Vert_2$. Thus $\Vert \bm{Z_k} / \sqrt{n} \Vert_2 \leq \mathcal{C}_{n,\delta_1}$, $k \in [p-1]$, since $\max_{k \in [p-1]}\Vert \bm{A^{X_k}} \Vert_2/\sqrt{n}\leq \mathcal{C}_{n,\delta_1}$. Recall that $\bm{u}=\bm{w} + \bm{r}$, where $\bm{u}$ is defined in (<ref>), $\bm{w}=(\bm{w_1}^{\top},\bm{w_2}^{\top},\dots,\bm{w_n}^{\top})^{\top} \in \mathbb{R}^{nM}$ and $\bm{r}=(\bm{r_1}^{\top},\bm{r_2}^{\top},\dots,\bm{r_n}^{\top})^{\top} \in \mathbb{R}^{nM}$. Both $\bm{w_i}$ and $\bm{r_i}$ are Gaussian vectors with mean zero, and covariance matrices $\bm{\Sigma^{w}}$ and $\bm{\Sigma^{r}}$ respectively for all $i \in [n]$ , where we dropped the superscript $M$ to simplify the notation, and $\bm{w_i} \independent \bm{r_i}$.

Fix $k \in [p-1]$. Let $\bm{r_i} = \bm{r^1_i} + \bm{r^2_i}$, where

\[
\bm{r^1_i} = \bm{r_i} - \bm{\Sigma^{r,X_k}} \left( \bm{\Sigma^{X}_{kk}} \right)^{-1} \bm{a^{X_k}_i}
\qquad \text{and} \qquad \bm{r^2_i}= \bm{\Sigma^{r,X_k}} \left( \bm{\Sigma^{X}_{kk}} \right)^{-1} \bm{a^{X_k}_i}.
\]

Since both $\bm{r_i}$ and $\bm{a^{X_k}_i}$ are Gaussian vectors and $\Cov (\bm{a^{X_k}_i}, \bm{r^1_i})=\bm{0}$, we have $\bm{a^{X_k}_i} \independent \bm{r^1_i}$. Then

\begin{equation}\label{eq:lemma2-1}
\left\Vert \frac{1}{n} \bm{Z_k}^\top \bm{u} \right\Vert_2 \leq
\left\Vert \frac{1}{n} \bm{Z_k}^\top (\bm{w}+\bm{r^1}) \right\Vert_2 + \left\Vert \frac{1}{n} \bm{Z_k}^\top \bm{r^2} \right\Vert_2.
\end{equation}

We upper bound the first term on the right hand side of (<ref>). Let $\bm{\xi_i}=\bm{w_i} + \bm{r^1_i}$. Then $\bm{\xi_i}$ is a Gaussian vector with mean zero and covariance matrix $\bm{\Sigma^{\xi}_k }$, with $\bm{\Sigma^{\xi}_k } = \bm{\Sigma^w}+\bm{\Sigma^r}-\bm{\Sigma^{r,X_k}} \left( \bm{\Sigma^{X}_{kk}} \right)^{-1} \bm{\Sigma^{{X_k},r}}$. Note that $\bm{\xi} \independent \bm{Z_k}$ and we establish a bound conditional on $\bm{Z_k}$ first.

For any pair $\bm{\theta},\bm{\theta^{\prime}} \in \mathbb{R}^{nM}$, we have

\begin{equation*}
\left\vert \left\Vert \frac{\bm{Z_k^{\top}} \bm{\theta}}{n} \right\Vert_2 - \left\Vert \frac{\bm{Z_k^{\top}} \bm{\theta}^{\prime}}{n} \right\Vert_2 \right\vert \leq \frac{1}{n} \left\Vert \bm{Z_k}^{\top} (\bm{\theta}-\bm{\theta^{\prime}}) \right\Vert_2\leq \frac{1}{n} \Vert \bm{Z_k} \Vert_2 \Vert \bm{\theta}-\bm{\theta^{\prime}} \Vert_2 \leq
\frac{\mathcal{C}_{n,\delta_1}}{\sqrt{n}} \Vert \bm{\theta}-\bm{\theta^{\prime}} \Vert_2.
\end{equation*}

Therefore, $\bm{\theta} \mapsto\Vert \frac{\bm{Z_k}^{\top} \bm{\theta}}{n}\Vert_2$ is a Lipschitz function with a Lipschitz constant $\mathcal{C}_{n,\delta_1}/\sqrt{n}$. Note that $\bm{\xi}$ has a strongly log-concave distribution with the parameter $(\rho_{max}(\bm{I_M} \otimes \bm{\Sigma^{\xi}_k} ))^{-1}=(\rho_{max}( \bm{\Sigma^{\xi}_k} ))^{-1}$.
Then, by Theorem 3.16 of 35, we have

\begin{equation}\label{eq:LipSchitzBound}
\mathbb{P}\left\{ \left\Vert \frac{ \bm{Z_k}^{\top} \bm{\xi} }{n} \right\Vert_2 \geq \mathbb{E}\left[\left\Vert \frac{\bm{Z_k}^{\top} \bm{\xi}}{n} \right\Vert_2 \right]+\Delta \right\}\leq 2\exp{\left(-\frac{n\Delta^2}{4C^{2}_{n,\delta_1}\rho_{\max}(\bm{\Sigma^{\xi}_k})}\right)}\quad \text{for all }\Delta>0.
\end{equation}

Next, we bound $\mathbb{E}\left[ n^{-1}\left\Vert {\bm{Z_k}^{\top} \bm{\xi}}\right\Vert_2 \right]$ using the Sudakov-Fernique inequality <cit.>. For any vector $\bm{\theta} \in \mathbb{R}^{M^2}$, let $\zeta_{\bm{\theta}} = {n}^{-1} \langle \bm{\theta}, \bm{Z_k}^{\top} \bm{\xi} \rangle$. Then $n^{-1}\Vert \bm{Z_k}^{\top} \bm{\xi}  \Vert_2 = \max_{\Vert \bm{\theta} \Vert_2=1} \zeta_{\bm{\theta}}$. For any two vectors $\bm{\theta}, \bm{\theta^{\prime}} \in \mathbb{R}^{M^2}$,
we have

\begin{multline*}
\mathbb{E}\left[(\zeta_{\bm{\theta}}-\zeta_{\bm{\theta^{\prime}}})^2\right] =\mathbb{E}\left[\left(\frac{1}{n}\left\langle \bm{\theta}-\bm{\theta^{\prime}}, \bm{Z_k}^{\top} \bm{\xi} \right\rangle\right)^2 \right]
=\frac{1}{n^2}\mathbb{E}\left[(\bm{\theta}-\bm{\theta^{\prime}})^{\top} \bm{Z_k}^{\top} \bm{\xi} \bm{\xi}^{\top} \bm{Z_k} (\bm{\theta}-\bm{\theta^{\prime}}) \right] \\
\leq \frac{\rho_{\max}(\bm{\Sigma^{\xi}_k})}{n} \frac{\Vert \bm{Z_k} \Vert^2_2}{n} \Vert \bm{\theta}-\bm{\theta^{\prime}} \Vert^2_2
\leq \frac{C^2_{n,\delta_1} \rho_{\max}(\bm{\Sigma^{\xi}_k})}{n}\Vert \bm{\theta}-\bm{\theta^{\prime}} \Vert^2_2.
\end{multline*}

We define another Gaussian process, $\tilde{\zeta}_{\bm{\theta}}=\left(\mathcal{C}_{n,\delta_1} \sqrt{\rho_{\max}(\bm{\Sigma^{\xi}_k})/n}\right) \cdot \langle \bm{\theta}, \bm{\epsilon} \rangle$, where $\bm{\epsilon} \sim N(\bm{0},\bm{I_{M^2}})$. For any pair $\bm{\theta}, \bm{\theta^{\prime}} \in \mathbb{R}^{M^2}$, we have

\begin{equation*}
\mathbb{E}\left[(\tilde{\zeta}_{\bm{\theta}}-\tilde{\zeta}_{\bm{\theta^{\prime}}})^2\right]=\frac{C^2_{n,\delta_1} \rho_{\max}(\bm{\Sigma^{\xi}_k})}{n}\Vert \bm{\theta}-\bm{\theta^{\prime}} \Vert^2_2 \geq \mathbb{E}\left[(\zeta_{\bm{\theta}}-\zeta_{\bm{\theta^{\prime}}})^2\right].
\end{equation*}

Then, by the Sudakov-Fernique inequality, we have

\begin{equation*}
\mathbb{E}\left[\left\Vert \frac{ \bm{Z_k}^{\top} \bm{\xi} }{n} \right\Vert_2 \right]=\mathbb{E}\left[\max_{\Vert \bm{\theta} \Vert_2=1} \zeta_{\bm{\theta}}\right] \leq \mathbb{E} \left[\max_{\Vert \bm{\theta} \Vert_2=1}\tilde{\zeta}_{\bm{\theta}} \right].
\end{equation*}

On the other hand,

\begin{equation*}
\begin{aligned}
\mathbb{E}\left[\max_{\Vert \bm{\theta} \Vert_2=1} \tilde{\zeta}_{\bm{\theta}}\right]  =  \frac{\mathcal{C}_{n,\delta_1} \sqrt{\rho_{\max}(\bm{\Sigma^{\xi}_k})}}{\sqrt{n}}\mathbb{E}\left[\Vert \bm{\epsilon} \Vert_2\right]
\leq\frac{\mathcal{C}_{n,\delta_1}\sqrt{\rho_{\max}(\bm{\Sigma^{\xi}_k})}}{\sqrt{n}}\sqrt{\mathbb{E}\left[\Vert \bm{\epsilon} \Vert^2_2\right]}
=\frac{M \mathcal{C}_{n,\delta_1} \sqrt{\rho_{\max} (\bm{\Sigma^{\xi}_k})}}{\sqrt{n}}.
\end{aligned}
\end{equation*}

Combining (<ref>) with the above upper bound, we have

\begin{equation*}
\mathbb{P}\left\{\left\Vert \frac{\bm{Z_k}^{\top} \bm{\xi}}{n} \right\Vert_2 \geq \frac{M \mathcal{C}_{n,\delta_1} \sqrt{\rho_{\max}(\bm{\Sigma^{\xi}_k})}}{\sqrt{n}}+\Delta \right\}\leq 2\exp{\left(-\frac{n\Delta^2}{4C^{2}_{n,\delta_1}\rho_{\max}(\bm{\Sigma^{\xi}_k})}\right)}, \quad \Delta>0.
\end{equation*}

The above inequality holds for any $\bm{Z_k}$ such that $\Vert \bm{Z_k} / \sqrt{n} \Vert_2 \leq \mathcal{C}_{n,\delta_1}$ and, therefore, is valid unconditionally as well. Since $\Xi_1(M) = \max_{k \in [p-1]} \rho_{\max}(\bm{\Sigma^{\xi}_k})$, if follows from the union bound that
\begin{equation}\label{eq:lemma2-5}
\mathbb{P}\left\{\max_{k \in [p-1]}\;\left\Vert \frac{ \bm{Z_k}^{\top} \bm{\xi}}{n} \right\Vert_2 \geq \frac{M \mathcal{C}_{n,\delta_1} \sqrt{\Xi_1(M)}}{\sqrt{n}}+\Delta \right\}\leq 2 (p-1) \exp{\left(-\frac{n\Delta^2}{4C^{2}_{n,\delta_1} \Xi_1(M)}\right)},
\quad \Delta>0.
\end{equation}

Next, we upper bound the second term in (<ref>). For any $k \in [p-1]$, we have

\begin{align*}
\left\Vert \frac{1}{n} \bm{Z_k}^\top \bm{r^2} \right\Vert_2
& =  \left\Vert \frac{1}{n} \sum^n_{i=1}  (\bm{a^{X_k}_i} \otimes \bm{I_M}) \bm{r^2_i} \right\Vert_2
=  \left\Vert \frac{1}{n} \sum^n_{i=1}  \bm{r^2_i} (\bm{a^{X_k}_i})^{\top} \right\Vert_{\text{F}} \\
& =  \left\Vert \frac{1}{n} \sum^n_{i=1}  \bm{\Sigma^{r,X_k}} \left( \bm{\Sigma^{X}_{kk}} \right)^{-1} \bm{a^{X_k}_i} (\bm{a^{X_k}_i})^{\top} \right\Vert_{\text{F}} \\
& \leq  \left\Vert \frac{1}{n} \sum^n_{i=1}  \bm{\Sigma^{r,X_k}} \left( \bm{\Sigma^{X}_{kk}} \right)^{-1} \bm{a^{X_k}_i} (\bm{a^{X_k}_i})^{\top} - \bm{\Sigma^{r,X_k}} \right\Vert_{\text{F}} + \left\Vert \bm{\Sigma^{r,X_k}} \right\Vert_{\text{F}}.
\end{align*}

\begin{align*}
& =  \left\Vert \bm{\Sigma^{r,X_k}} \left\{ \frac{1}{n} \sum^n_{i=1}  \left( \bm{\Sigma^{X}_{kk}} \right)^{-1} \bm{a^{X_k}_i} (\bm{a^{X_k}_i})^{\top}  - \bm{I_M} \right\} \right\Vert_{\text{F}} + \left\Vert \bm{\Sigma^{r,X_k}} \right\Vert_{\text{F}}\\
& \leq  \left\Vert \bm{\Sigma^{r,X_k}} \right\Vert_{\text{F}} \left\Vert  \frac{1}{n} \sum^n_{i=1}  \left( \bm{\Sigma^{X}_{kk}} \right)^{-1} \bm{a^{X_k}_i} (\bm{a^{X_k}_i})^{\top}  - \bm{I_M} \right\Vert_{\text{F}} + \left\Vert \bm{\Sigma^{r,X_k}} \right\Vert_{\text{F}}\\
& =  \left\Vert \bm{\Sigma^{r,X_k}} \right\Vert_{\text{F}} \left\Vert  \frac{1}{n} \sum^n_{i=1} \left( \left( \bm{\Sigma^{X}_{kk}} \right)^{-1/2} \bm{a^{X_k}_i} \right) \left( \left( \left( \bm{\Sigma^{X}_{kk}} \right)^{-1/2} \bm{a^{X_k}_i} \right) \right)^{\top} - \bm{I_M}  \right\Vert_{\text{F}} + \left\Vert \bm{\Sigma^{r,X_k}} \right\Vert_{\text{F}} \\
& \overset{\Delta}{=} \left\Vert \bm{\Sigma^{r,X_k}} \right\Vert_{\text{F}} \left\{ \left\Vert \frac{1}{n} \sum^n_{i=1} \bm{b^{X_k}_i} \left( \bm{b^{X_k}_i} \right)^{\top} - \bm{I_M} \right\Vert_{\text{F}} + 1 \right\}, \numberthis \label{eq:lemma2-2}
\end{align*}

where $\bm{b^{X_k}_i} = ( \bm{\Sigma^{X}_{kk}} )^{-1/2} \bm{a^{X_k}_i} \sim N(0,\bm{I_M})$. Since

\begin{equation}\label{eq:lemma2-3}
\left\Vert \frac{1}{n} \sum^n_{i=1} \bm{b^{X_k}_i} \left( \bm{b^{X_k}_i} \right)^{\top} - \bm{I_M} \right\Vert_{\text{F}} \leq M \vertiii{\frac{1}{n} \sum^n_{i=1} \bm{b^{X_k}_i} \left( \bm{b^{X_k}_i} \right)^{\top} - \bm{I_M} }_{\infty},
\end{equation}

we only need to bound $ \vertiii{\frac{1}{n} \sum^n_{i=1} \bm{b^{X_k}_i} \left( \bm{b^{X_k}_i} \right)^{\top} - \bm{I_M} }_{\infty}$.
We use Theorem 4.1 in 16 to bound this term. We first check the conditions therein. Note that for $b^{X_k}_{im}$ is a standard normal random variable for all $i \in [n]$ and $m \in [M]$, we have $(b^{X_k}_{im})^2$ to be chi-squared distributed with degree of freedom 1. By the moment generating function of chi-square distribution, we have

\begin{equation*}
\mathbb{E}\left[\exp\{\eta (b^{X_k}_{im})^2 \} \right]=\frac{1}{\sqrt{1-2\eta}} \quad \text{for all } 0<\eta<1/2.
\end{equation*}

Thus, we have

\begin{align*}
\Vert b^{X_k}_{im} \Vert_{\psi_2} & =  \inf\{\eta>0:\mathbb{E}\left[{\psi_2 (\vert b^{X_k}_{im} \vert / \eta)}\right]\leq 1\}\\
& =  \inf\{\eta>0:\mathbb{E}\left[{\exp ( (b^{X_k}_{im})^2 / \eta^2)}\right]\leq 2\}\\
& =  \inf\{\eta>0:1/\sqrt{1-2/\eta^2}\leq 2\}\\
& =  \frac{2\sqrt{2}}{\sqrt{3}}.
\end{align*}

Furthermore, we have

\begin{equation*}
\Vert b^{X_k}_i \Vert_{M,\psi_2} = \max_{m \in [M]} \Vert b^{X_k}_{im} \Vert_{\psi_2} = \frac{2\sqrt{2}}{\sqrt{3}}.
\end{equation*}

for all $i \in [n]$. In addition, note that

\begin{equation*}
\Var{\left( b^{X_k}_{im} b^{X_k}_{i m^{\prime}} \right)} \leq \mathbb{E}\left[(b^{X_k}_{i m})^2 (b^{X_k}_{i m^{\prime}})^2\right] \leq \left( \mathbb{E}\left[(b^{X_k}_{i m})^4 \right] \right)^{1/2} \left( \mathbb{E}\left[(b^{X_k}_{i m^{\prime}})^4\right] \right)^{1/2} = 3
\end{equation*}

for all $m, m^{\prime} \in [M]$, thus we have

\begin{equation*}
\max_{m,m^{\prime} \in [M]} \left\{ \frac{1}{n} \sum^n_{i=1} \Var{\left( b^{X_k}_{im} b^{X_k}_{i m^{\prime}} \right)} \right\} \leq 3.
\end{equation*}

Therefore, by Theorem 4.1 in 16, we have

\begin{equation*}
\mathbb{P} \left\{ \vertiii{\frac{1}{n} \sum^n_{i=1} \bm{b^{X_k}_i} \left( \bm{b^{X_k}_i} \right)^{\top} - \bm{I_M} }_{\infty} > 7\sqrt{3} \sqrt{\frac{\Delta + 2 \log M}{n}} + \frac{8 c}{3} \frac{ (\log (2n)) (\Delta + 2\log M) }{n} \right\} \leq 3 e^{-\Delta},
\end{equation*}

for all $\Delta>0$, where $c$ is a constant.
Thus, combining the above equation with (<ref>) and (<ref>), we have

\begin{equation*}
\mathbb{P} \left\{ \left\Vert \frac{1}{n} \bm{Z_k}^\top \bm{r^2} \right\Vert_2 > \left\Vert \bm{\Sigma^{r,X_k}} \right\Vert_{\text{F}} \left\{ 1 + 7\sqrt{3} \frac{M \sqrt{\Delta + 2 \log M}}{\sqrt{n}} + \frac{8 c}{3} \frac{ M (\log (2n)) (\Delta + 2\log M) }{n} \right\} \right\} \leq 3 e^{-\Delta}.
\end{equation*}

Let $\omega(M)=\max_{k \in [p-1]} \left\Vert \bm{\Sigma^{r,X_k}} \right\Vert_{\text{F}}$, then

\begin{equation}\label{eq:lemma2-4}
\begin{aligned}
& \mathbb{P} \left\{ \max_{k \in [p-1]} \left\Vert \frac{1}{n} \bm{Z_k}^\top \bm{r^2} \right\Vert_2 >  \omega(M) \left\{ 1 + 7\sqrt{3} \frac{M \sqrt{\Delta + 2 \log M}}{\sqrt{n}} + \frac{8 c}{3} \frac{ M (\log (2n)) (\Delta + 2\log M) }{n} \right\} \right\} \\
& \leq  3 (p-1) e^{-\Delta}.
\end{aligned}
\end{equation}

The result follows by combining (<ref>), (<ref>), and (<ref>).

Let $\lambda_n = \tilde{\lambda}(n,p,M,\delta)$, where

\begin{multline*}
\tilde{\lambda} (n, p, M, \delta) =  2 \mathcal{C}_{n,\delta} \left(\frac{M  \sqrt{\Xi_1 (M)}}{\sqrt{n}}+ 2 \sqrt{\Xi_1 (M)} \sqrt{ \frac{ \log (4(p-1)/\delta) }{n} } \right) \\
+ 2 \omega (M) \left\{
7\sqrt{3} \frac{M \sqrt{ \log (6(p-1)/\delta) + 2 \log M}}{\sqrt{n}} \right. \\
\left. +
\frac{ 8 M c (\log (2n)) (\log (6(p-1)/\delta) + 2\log M) }{3n} \right\},
\end{multline*}

is defined in (<ref>), then (<ref>) holds with probability at least $1-2\delta$. That is, we have

\begin{equation*}
\lambda_n \geq \frac{2}{n} \max_{k \in [p-1]} \Vert (\bm{Z}^{\top} \bm{u})_{k} \Vert_2
\end{equation*}

hold with probability at least $1-2\delta$.

The result follows directly from Lemma <ref>, Lemma <ref> and Bonferroni inequality.

\begin{equation*}
\mathbb{P} \left\{ \sqrt{\sum^{p-1}_{k=1} \left\Vert \bm{\hat{B}_k} - \bm{B^*_k} \right\Vert^2_{\text{F}}} \leq \chi (n,p,M,\delta) + 12 \sqrt{s} \frac{\omega (M)}{ \sqrt{\kappa(M)}} \right\} \geq 1-3\delta,
\end{equation*}

where $\kappa(M)$ is defined in (<ref>) and $\chi (n,p,M,\delta)$ is defined in (<ref>).

By Lemma <ref> and (<ref>), we can get an error bound for $\Vert \hat{\beta}-\beta^{\ast} \Vert_2$ by applying Theorem 1 in 23.
Note that by Lemma C.4 of 38, we have the subspace compatibility constant defined in Definition 3 of 23 to be $\sqrt{s}$.
Then, for all $0<\delta \leq 1$, when $n$ is large enough such that $\Gamma (n,p,M,\delta) \leq \kappa(M)/(32 M^2 s)$, where $\Gamma (n,p,M,\delta)$ is defined in (<ref>), and let $\lambda_n=\tilde{\lambda} (n,p,M,\delta)$, where $\tilde{\lambda} (n,p,M,\delta)$ is defined in (<ref>), then by Corollary 1 in 23, Lemma <ref>, (<ref>), and a union bound, we have the desired result.

There exists a constant $c$ such that

\begin{equation}\label{eq:EleAbsCovMaxBound}
\vertiii{\bm{\hat{\Sigma}^X_n}-\bm{\Sigma^X}}_{\infty}\leq 7\sqrt{3}K_0\sqrt{\frac{\log{(3/\delta)}+2\log{((p-1)M)}}{n}}+\frac{8c K_0 \log{(2n)}(\log{(3/\delta)}+2\log{((p-1)M)})}{3n}
\end{equation}

holds with probability at least $1-\delta$ where $K_0$ is defined by (<ref>).

The result follows Theorem 4.1 in 16. In order to apply the theorem, we need to check the conditions therein. First, we bound $\max_{k \in [p-1], m \in [M]}\Vert a^{X_k}_{im} \Vert_{\psi_2}$. Note that for $\zeta \sim N(0,\sigma^2)$, we have $(\zeta/\sigma)^2$ is chi-square distributed with degree of freedom 1. By the moment generating function of chi-square distribution, we have

\begin{equation*}
\mathbb{E}\left[\exp\{\eta(\zeta/\sigma)^2\} \right]=\frac{1}{\sqrt{1-2\eta}} \quad \text{for all } 0<\eta<1/2.
\end{equation*}

Thus, we have

\begin{equation*}
\mathbb{E}\left[\exp\left(\zeta^2/t^2\right) \right]=\mathbb{E}\left[\exp\left\{\left(\sigma^2/t^2\right)\cdot \left(\zeta^2/\sigma^2\right)  \right\} \right]=\frac{1}{\sqrt{1-2\sigma^2/t^2}}
\end{equation*}

for all $t>\sqrt{2}\sigma$. Let $1/\sqrt{1-2\sigma^2/t^2}\leq 2$, we have $t\geq (2\sqrt{2})/(\sqrt{3}\sigma)$. Thus, we have

\begin{equation*}
\begin{aligned}
\Vert \zeta \Vert_{\psi_2}&=\inf\{t>0:\mathbb{E}\left[{\psi_2 (\vert \zeta \vert / t)}\right]\leq 1\}\\
&=\inf\{t>0:\mathbb{E}\left[{\exp (\zeta^2 / t^2)}\right]\leq 2\}\\
&=\inf\{t>0:1/\sqrt{1-2\sigma^2/t^2}\leq 2\}\\
\end{aligned}
\end{equation*}

Based on the above result, we have for any $i\in[n]$,

\begin{equation*}
\begin{aligned}
\Vert \bm{a^{X_k}_i} \Vert_{M,\psi_2}&=\max_{k \in [p-1], m \in [M]} \Vert a^{X_k}_{im} \Vert_{\psi_2}\\
&=\frac{2\sqrt{2}}{\sqrt{3}}\max_{ k \in [p-1], m \in [M] }\sqrt{\Sigma^{X}_{kk,mm}}\\
&= \frac{2\sqrt{2}}{\sqrt{3}}\sqrt{K_0},
\end{aligned}
\end{equation*}

where $K_0$ is defined by (<ref>).
We then bound $\max_{k,k^{\prime} \in [p], m, m^{\prime} \in [M]}\Var{\left(a^{X_k}_{im} a^{X_{k^{\prime}}}_{i m^{\prime}} \right)}$. This followed by

\begin{equation*}
\begin{aligned}
\Var{\left(a^{X_k}_{im} a^{X_{k^{\prime}}}_{i m^{\prime}} \right)} & \leq  \mathbb{E}\left[(a^{X_k}_{im})^2  (a^{X_{k^{\prime}}}_{i m^{\prime}})^2 \right]\leq \left(  \mathbb{E}\left[(a^{X_k}_{im})^4 \right]  \mathbb{E}\left[ (a^{X_{k^{\prime}}}_{i m^{\prime}})^2 \right] \right)^{1/2}\\
&=\left(9 (\Sigma^X_{kk,mm})^2 (\Sigma^X_{k^{\prime} k^{\prime},m^{\prime} m^{\prime}})^2 \right)^{1/2}\\
&\leq 3K_0^2.
\end{aligned}
\end{equation*}

Thus, the final result is derived by applying Theorem 4.1 in 16 with $K_{n,p}=(2\sqrt{2}/\sqrt{3})\sqrt{K_0}$ and $A^2_{n,p}=3K_0^2$.

For $\bm{x_i},\bm{y_i}\in \mathbb{R}^M$, $i \in [n]$, we have

\begin{equation*}
\left\Vert \frac{1}{n} \sum^n_{i=1} \bm{x_i} \bm{y_i}^{\top} \right\Vert_{\text{F}} \leq \sqrt{\frac{1}{n} \sum^n_{i=1} \Vert \bm{x_i} \Vert^2_2} \sqrt{\frac{1}{n} \sum^n_{i=1} \Vert \bm{y_i} \Vert^2_2}\, .
\end{equation*}

For any $m,m'\in[M]$, we have

\begin{equation*}
\left\vert \frac{1}{n} \sum^n_{i=1} x_{im} y_{i m^{\prime}} \right\vert^2 \leq \left( \frac{1}{n} \sum^n_{i=1} x^2_{im} \right) \left( \frac{1}{n} \sum^n_{i=1} y^2_{im^{\prime}} \right).
\end{equation*}

\begin{multline*}
\left\Vert \frac{1}{n} \sum^n_{i=1} \bm{x_i} \bm{y_i}^{\top} \right\Vert^2_{\text{F}}
=  \sum^M_{m,m^{\prime}=1} \left\vert \frac{1}{n} \sum^n_{i=1} x_{im} y_{i m^{\prime}} \right\vert^2 \leq \sum^M_{m,m^{\prime}=1} \left( \frac{1}{n} \sum^n_{i=1} x^2_{im} \right) \left( \frac{1}{n} \sum^n_{i=1} y^2_{im^{\prime}} \right) \\
=  \left( \frac{1}{n} \sum^n_{i=1} \sum^{M}_{m=1} x^2_{im} \right) \left( \frac{1}{n} \sum^n_{i=1} \sum^M_{m^{\prime}=1} y^2_{im^{\prime}} \right)
=  \left( \frac{1}{n} \sum^n_{i=1} \Vert \bm{x_i} \Vert^2_2 \right) \left( \frac{1}{n} \sum^n_{i=1} \Vert \bm{y_i} \Vert^2_2 \right),
\end{multline*}

and the result immediately follows.

\begin{equation}\label{eq:Gamma_n}
\Gamma (n,p,M,\delta) = 7\sqrt{3}K_0\sqrt{\frac{\log{(3/\delta)}+2\log{((p-1)M)}}{n}}+\frac{8c K_0 \log{(2n)}(\log{(3/\delta)}+2\log{((p-1)M)})}{3n},
\end{equation}

then when $\Gamma (n,p,M,\delta) \leq \kappa(M)/(32 M^2 s)$, we have

\begin{equation*}
\mathbb{P} \left\{ \frac{1}{2n}\Vert \bm{Z} \bm{\Delta\beta} \Vert^2_2 \geq \frac{\kappa}{4} \Vert \bm{\Delta\beta} \Vert^2_2 \text{ for all } \bm{\Delta\beta} \in \mathbb{C}(\mathscr{N}_j) \right\} \geq 1-\delta,
\end{equation*}

where $\mathbb{C}(\mathscr{N}_j)$ is defined in (<ref>).

We want to first prove

\begin{equation*}
\frac{1}{2n}\Vert \bm{Z} \bm{\Delta\beta} \Vert^2_2 \geq \kappa_{\mathcal{L}}\Vert \bm{\Delta\beta} \Vert^2_2-\tau_{\mathcal{L}}(\bm{\beta^{\ast}}) \quad \text{for all } \bm{\Delta\beta} \in\mathbb{C}(\mathscr{N}_j),
\end{equation*}

where $\kappa_{\mathcal{L}}>0$ is a positive constant, $\tau_{\mathcal{L}}(\beta^{\ast})>0$, and $\mathbb{C}(\mathscr{N}_j)$ is defined in (<ref>).

Since $\bm{Z} = \bm{A^X} \otimes \bm{I_M}$, thus for any $ \bm{\theta} \in\mathbb{R}^{(p-1)M^2}$, we have

\begin{equation*}
\begin{aligned}
\frac{1}{n}\Vert \bm{Z} \bm{\theta} \Vert^2_2&=\frac{1}{n}\Vert (\bm{A^X} \otimes I_M) \bm{\theta} \Vert^2_2\\
&=\frac{1}{n}\bm{\theta}^{\top} ( \bm{A^X} \otimes \bm{I_M})^{\top}( \bm{A^X} \otimes \bm{I_M})\bm{\theta}\\
&=\frac{1}{n}\bm{\theta}^{\top}((\bm{A^X})^{\top} \otimes \bm{I_M})(\bm{A^X}\otimes \bm{I_M}) \bm{\theta}\\
&=\frac{1}{n}\bm{\theta}^{\top}((\bm{A^X})^{\top} \bm{A^X} \otimes \bm{I_M}) \bm{\theta}\\
&=\bm{\theta}^{\top}(\bm{\hat{\Sigma}^X_n} \otimes \bm{I_M})\bm{\theta},
\end{aligned}
\end{equation*}

where $\bm{\hat{\Sigma}^X_n} = \frac{1}{n} (\bm{A^X})^{\top} \bm{A^X}$. We then further have

\begin{equation*}
\begin{aligned}
\frac{1}{n}\Vert \bm{Z} \bm{\theta} \Vert^2_2&=\bm{\theta}^{\top}(\bm{\Sigma^X} \otimes \bm{I_M}) \bm{\theta}+\bm{\theta}^{\top}\left((\bm{\hat{\Sigma}^X_n}-\bm{\Sigma^X})\otimes \bm{I_M}\right)\bm{\theta}\\
&\geq \left\vert \bm{\theta}^{\top}(\bm{\Sigma^X} \otimes \bm{I_M}) \bm{\theta} \right\vert -\left\vert \bm{\theta}^{\top}\left((\bm{\hat{\Sigma}^X_n}-\bm{\Sigma^X})\otimes \bm{I_M}\right)\bm{\theta} \right\vert.
\end{aligned}
\end{equation*}

Note that

\begin{align*}
\min_{\bm{\theta}\in\mathbb{C}(\mathscr{N}_j)\setminus\{0\}}\frac{\bm{\theta}^{\top}(\bm{\Sigma^{X}}\otimes \bm{I_M})\bm{\theta}}{\Vert \bm{\theta} \Vert^2_2}&\geq \min_{\bm{\theta}\in\mathcal{M}\setminus\{0\}}\frac{\bm{\theta}^{\top}(\bm{\Sigma^{X}}\otimes \bm{I_M})\bm{\theta}}{\Vert \bm{\theta} \Vert^2_2}\\
&\geq\rho_{\min}\left(\bm{\Sigma^X_{\mathscr{N}_j \mathscr{N}_j}} \otimes \bm{I_M}\right)\\
&=\rho_{\min}(\bm{\Sigma^X_{\mathscr{N}_j \mathscr{N}_j}})\\
\end{align*}

and we have $\kappa(M)>0$ for all $M$ by Assumption <ref>.
Thus, for any $\bm{\theta}\in\mathbb{C}(\mathscr{N}_j)$, we have

\begin{equation}\label{eq:RECDecompose}
\frac{1}{n}\Vert \bm{Z} \bm{\theta} \Vert^2_2\geq \kappa \Vert \bm{\theta}\Vert^2_2-\left\vert\bm{\theta}^{\top}\left((\bm{\hat{\Sigma}^X_n}-\bm{\Sigma^X})\otimes \bm{I_M}\right) \bm{\theta} \right\vert.
\end{equation}

To prove the RSC condition, it then suffices to give an upper bound for $\vert \bm{\theta}^{\top}\left((\bm{\hat{\Sigma}^X_n}-\bm{\Sigma^X})\otimes \bm{I_M}\right)\bm{\theta}\vert$, where $\bm{\theta}\in\mathbb{C}(\mathscr{N}_j)$. By Lemma 5 in section D of the appendix of 39 and the definition of $\mathbb{C}(\mathscr{N}_j)$, for any $\bm{\theta}\in\mathbb{C}(\mathscr{N}_j)$, we have

\begin{equation*}
\begin{aligned}
\left\vert \bm{\theta}^{\top}\left((\bm{\hat{\Sigma}^X_n}-\bm{\Sigma^{X}})\otimes \bm{I_M} \right) \bm{\theta} \right\vert &\leq M^2 \vertiii{(\bm{\hat{\Sigma}^X_n}-\bm{\Sigma^{X}})\otimes \bm{I_M}}_{\infty}\Vert \bm{\theta} \Vert^{2}_{1,2}\\
&=M^2 \vertiii{(\bm{\hat{\Sigma}^X_n}-\bm{\Sigma^{X}})\otimes \bm{I_M}}_{\infty}\left(\Vert \bm{\theta}_{\mathcal{M}}\Vert_{1,2}+\Vert \bm{\theta}_{\mathcal{M}^{\bot}}\Vert_{1,2} \right)^2\\
&\leq 16 M^2 \vertiii{(\bm{\hat{\Sigma}^X_n}-\bm{\Sigma^{X}})\otimes I_M}_{\infty} \Vert \bm{\theta}_{\mathcal{M}}\Vert^2_{1,2}\\
&\leq 16 s M^2 \vertiii{(\bm{\hat{\Sigma}^X_n}-\bm{\Sigma^{X}})\otimes I_M}_{\infty}\Vert \bm{\theta}_{\mathcal{M}}\Vert^2_{1,2},
\end{aligned}
\end{equation*}

where the penultimate line is by Lemma 6 in section D of 39. Note that

\[
\vertiii{(\bm{\hat{\Sigma}^X_n}-\bm{\Sigma^{X}})\otimes \bm{I_M}}_{\infty}=\vertiii{\bm{\hat{\Sigma}^X_n}-\bm{\Sigma^{X}}}_{\infty},
\]

then combine (<ref>) and Lemma <ref>, we have constant $c$ such that for any $\delta>0$, with probability at least $1-\delta$, we have

\begin{equation}
\begin{aligned}
\frac{1}{2n}\Vert \bm{Z} \bm{\Delta\beta} \Vert^2_2 & \geq  \left( \frac{\kappa}{2}-8M^2 s\cdot \left\{ 7\sqrt{3}K_0\sqrt{\frac{\log{(3/\delta)}+2\log{((p-1)M)}}{n}} + \right.\right.\\
& \left.\left. \frac{8c K_0 \log{(2n)}(\log{(3/\delta)}+2\log{((p-1)M)})}{3n} \right\} \right)\Vert \bm{\Delta\beta} \Vert^2_2
\end{aligned}
\end{equation}

for all $\bm{\Delta\beta}\in\mathbb{C}(\mathscr{N}_j)$.
Let $\Gamma (n,p,M,\delta)$ be defined by (<ref>),
then when $\Gamma (n,p,M,\delta) \leq \kappa(M)/(32 M^2 s)$, we have

\begin{equation*}
\frac{1}{2n}\Vert \bm{Z} \bm{\Delta\beta} \Vert^2_2 \geq \frac{\kappa}{4} \Vert \bm{\Delta\beta} \Vert^2_2 \text{ for all } \bm{\Delta\beta} \in \mathbb{C}(\mathscr{N}_j)
\end{equation*}

with probability at least $1-\delta$.

In the next few results, recall that

\[
\lfb =  1 + 8 \left(  \frac{\log (2/\delta)}{n} + \sqrt{ \frac{\log (2/\delta)}{n} } \right) .
\]

Let $\xi_1,\cdots,\xi_n$ be i.i.d. mean zero random elements in some Hilbert space, and $\mathbb{E}[\Vert \xi_1 \Vert^2 ]=\sigma_{\xi}$. Besides, we assume that

\begin{equation*}
\mathbb{E}\left[ \Vert \xi_1\Vert^{2k} \right] \leq (2 \sigma_{\xi})^k \cdot k !  \quad \text{ for all } k = 1,2,\cdots .
\end{equation*}

Then for any given $\delta \in (0, 1]$, we have

\begin{equation*}
\mathbb{P} \left\{  \frac{1}{n} \sum^n_{i=1} \Vert \xi_i \Vert^2 \leq \sigma_{\xi} \lfb \right\} \geq 1 - \delta.
\end{equation*}

Note that $x \mapsto \vert x \vert^k$ is a convex function when $k\geq 1$ and $x \in \mathbb{R}$. By Jensen's inequality, we have
$\vert x/2+y/2 \vert^k \leq (\vert x \vert^k + \vert y \vert^k) / 2$, which implies that $\vert x + y \vert^k \leq 2^{k-1} (\vert x \vert^k + \vert y \vert^k)$.
Then by Lemma <ref>, for $k \geq 2$, we have

\begin{equation*}
\mathbb{E} \left[  \left\vert \Vert \xi_1 \Vert^2 - \sigma_{\xi}  \right\vert^k \right] \leq 2^{k-1} \left(  \mathbb{E} \left[ \Vert \xi_1 \Vert^{2k} \right] + \sigma^k_{\xi} \right) \leq 2^{k-1} \left( (2 \sigma_{\xi})^k k! + \sigma^k_{\xi} \right) \leq (4 \sigma_{\xi})^k k!.
\end{equation*}

Thus, we have

\begin{equation*}
\frac{1}{n} \sum^n_{i=1} \mathbb{E} \left[  \left\vert \Vert \xi_i \Vert^2 - \sigma_{\xi}  \right\vert^k \right] \leq \frac{k!}{2} (32 \sigma^2_{\xi}) (4 \sigma_{\xi})^{k-2}
\end{equation*}

for all $k=2,3,\dots$. Then, by Theorem 2.5 4, we have

\begin{equation*}
\mathbb{P} \left\{ \left\vert \frac{1}{n} \sum^n_{i=1} \Vert \xi_i \Vert^2 - \sigma_{\xi} \right\vert > \Delta \right\} \leq 2 \exp \left( - \frac{n \Delta^2 }{ 64 \sigma^2_{\xi} + 8 \sigma_{\xi} \Delta } \right), \quad \Delta > 0.
\end{equation*}

The result follows by rearranging the terms.

Let $\delta \in (0, 1]$. For any $j \in [p]$, we have

\begin{align*}
\mathbb{P} &\left\{ \frac{1}{n} \sum^n_{i=1} \Vert g_{ij} \Vert^2 \leq  \sigma_{\max,0} \lfb \right\} \geq 1 -\delta \\
\intertext{and}
\mathbb{P} &\left\{ \frac{1}{n} \sum^n_{i=1} \Vert e_{ij} \Vert^2 \leq  \sigma_{jr} \lfb \right\} \geq 1 -\delta,
\end{align*}

where $e_{ij}$ is defined in (<ref>) and $\sigma_{jr}=\mathbb{E} [ \Vert e_{ij} \Vert^2]$.

The result follows directly from Lemma <ref>.

For all $0<\delta \leq 1$, we have

\begin{equation*}
\mathbb{P} \left\{ \frac{1}{n} \sum^n_{i=1} \Vert \bm{r_i} + \bm{w_i} \Vert^2_2 \leq  \Xi_4 (M) \lfb \right\} \geq 1 -\delta,
\end{equation*}

\begin{equation*}
\mathbb{P} \left\{ \frac{1}{n} \sum^n_{i=1} \Vert \bm{a^{X_k}}_i \Vert^2_2 \leq \tr \left(\bm{\Sigma^X_{kk}}\right) \lfb \right\} \geq 1 -\delta,
\end{equation*}

\begin{equation*}
\mathbb{P} \left\{ \frac{1}{n} \sum^n_{i=1} \Vert a^{X_k}_{i m} \Vert^2_2 \leq \Xi_2 (M) \lfb \right\} \geq 1 -\delta \, \text{for all } m \in [M], k \in [p-1] .
\end{equation*}

Note that $\mathbb{E} [ \Vert \bm{r_i} + \bm{w_i} \Vert^2_2 ] = \Xi_4 (M)$, $\mathbb{E} [ \Vert \bm{a^{X_k}_i} \Vert^2_2 ] = \tr (\bm{\Sigma^X_{kk}}) $ and $\mathbb{E} [ \Vert a^{X_k}_{im} \Vert^2_2 ] = \Sigma^{X_k X_k}_{mm} \leq \rho_{\max} (\bm{\Sigma^X_{kk}}) \leq \Xi_2 (M)$, where $\Xi_2 (M),\Xi_4 (M)$ is defined in (<ref>), and then the result follows directly from Lemma <ref>.

Let $g$ be a mean zero random Gaussian function in the Hilbert space $\mathbb{H}$. Let $\sigma_0=\mathbb{E}\left[ \Vert g \Vert^{2} \right]$.

\[
\mathbb{E}\left[ \Vert g \Vert^{2k} \right]\leq (2\sigma_0)^{k}\cdot k!  \quad \text{ for all } k = 1,2,\cdots .
\]

Let $\{\phi_{m} \}_{m\geq 1}$ be othornormal eigenfunctions of covariance function of $g$.
Let $a_m=\langle g,\phi_{m} \rangle$. We have $a_m$, $m \geq 1$, are independent mean zero Gaussian random variables with variance $\sigma_m$ and $\sigma_0=\sum_{m\geq 1}\sigma_{m}$. We further have

\begin{equation*}
g=\sum^{\infty}_{m=1}\sigma_{m}^{1/2} \xi_{m} \phi_{m},
\end{equation*}

where $\xi_{m}=\sigma^{-1/2}_{m}a_m$ are independent standard Gaussian, and
$\Vert g \Vert=\left(\sum_{m\geq 1}\sigma_{m}\xi^{2}_{m}\right)^{1/2}$.

Using the Jensen's inequality for $t \mapsto t^{2k}$, we have

\begin{multline*}
\Vert g \Vert^{2k}=\left(\sum_{m\geq 1}\sigma_{m}\right)^{k} \cdot  \left(\frac{\sum_{m\geq 1}\sigma_{m}\xi^{2}_{m}}{\sum_{m\geq 1}\sigma_{m}}\right)^{k}
\\
\leq \left(\sum_{m\geq 1}\sigma_{m}\right)^{k} \cdot \frac{\sum_{m\geq 1}\sigma_{m}\xi^{2k}_{m}}{\sum_{m\geq 1}\sigma_{m}}
=\left(\sum_{m\geq 1}\sigma_{m}\right)^{k-1} \cdot \left( \sum_{m\geq 1}\sigma_{m}\xi^{2k}_{m} \right).
\end{multline*}

\begin{equation*}
\begin{aligned}
\mathbb{E}\left[ \Vert g \Vert^{2k} \right]
\leq \left(\sum_{m\geq 1}\sigma_{m}\right)^{k-1} \cdot \left( \sum_{m\geq 1}\sigma_{m}\mathbb{E}\left[\xi^{2k}_{m}\right] \right)
=\sigma_{0}^{k} \mathbb{E}\left[\xi^{2k}_{1}\right]
\leq \sigma_{0}^{k}\cdot 2^k \cdot k!=(2\sigma_{0})^{k}k!\, ,
\end{aligned}
\end{equation*}

which completes the proof.

Recall that $\bm{g_i}(\cdot)=(g_{i1}(\cdot), g_{i2}(\cdot), \dots, g_{ip}(\cdot) )^{\top}$ is our $i$-th observation defined in Section <ref>. Besides, recall that in Section <ref>, we have $\phi_{m}=\phi_{jm}$ and $\hat{\phi}_{m}=\hat{\phi}_{jm}$ be the $m$-th basis function and and its corresponding estimate respectively used to do projection for $j$-th node, and
$\bm{\hat{a}^{X_k}_{i,M}}=(\hat{a}^{X_k}_{i1},\ldots,\hat{a}^{X_k}_{iM})^{\top}$ be the projection score vector of $\bm{g_i}$ by using $\{\hat{\phi}_{m}\}^M_{m=1}$.
Under the assumption that

\begin{equation*}
\frac{1}{n} \sum^n_{i=1} \Vert g_{ij} \Vert^2 \leq  \Gamma_g (j) \, \text{ for all } j \in [p],
\end{equation*}

\begin{equation*}
\Vert \hat{\phi}_m - \phi_m \Vert \leq \Gamma_{\phi}(m) \, \text{ for all } m \geq 1,
\end{equation*}

for some $0 < \delta \leq 1$, we then have

\begin{equation*}
\frac{1}{n} \sum^n_{i=1} \left( \hat{a}^{X_k}_{im} - a^{X_k}_{im} \right)^2 \leq \Gamma_g (k) \Gamma^2_{\phi}(m),
\end{equation*}

for all $k \in [p-1]$ and $m \geq 1$. Furthermore, we have

\begin{equation*}
\frac{1}{n} \sum^{n}_{i=1} \Vert \bm{\hat{a}^{X_k}_i} - \bm{a^{X_k}_i} \Vert^2 \leq \Gamma_g (k)  \sum^M_{m=1} \Gamma^2_{\phi}(m).
\end{equation*}

Note that

\begin{equation*}
\left( \hat{a}^{X_k}_{im} - a^{X_k}_{im} \right)^2 = \left( \langle g^{X_k}_i, \hat{\phi}_m - \phi_m \rangle \right)^2 \leq \Vert g^{X_k}_i \Vert^2 \Vert \hat{\phi}_m - \phi_m \Vert^2.
\end{equation*}

Thus we have

\begin{equation*}
\frac{1}{n} \sum^n_{i=1} \left( \hat{a}^{X_k}_{im} - a^{X_k}_{im} \right)^2 \leq \left( \frac{1}{n} \sum^n_{i=1} \Vert g^{X_k}_i \Vert^2  \right) \Vert \hat{\phi}_m - \phi_m \Vert^2.
\end{equation*}

The rest of the proof follows directly from the assumptions we made.

For a given node $j \in [p]$, recall that $\phi_{m}=\phi_{jm}$ and $\hat{\phi}_{m}=\hat{\phi}_{jm}$ are the $m$-th basis function and its corresponding estimate respectively used to do projection for $j$-th node, defined in Section <ref>. Besides, let $\beta_k (t^{\prime},t)=\beta_{jk} (t^{\prime},t)$ and recall that $b^{\ast}_{k,m m^{\prime}} = \int_{\mathcal{T}\times \mathcal{T}} \beta_k (t^{\prime},t) \phi_m (t) \phi_{m^{\prime}} (t^{\prime}) dt^{\prime} dt$ is defined in (<ref>) and $\tilde{b}_{k,m m^{\prime}} = \int_{\mathcal{T}} \beta_k (t^{\prime},t) \hat{\phi}_m (t^{\prime}) \hat{\phi}_{m^{\prime}} (t) dt^{\prime} dt$ is defined in (<ref>).
Under the assumption that

\begin{equation*}
\Vert \hat{\phi}_m - \phi_m \Vert \leq \Gamma_{\phi}(m) \, \text{for all } m \geq 1,
\end{equation*}

and $\sum^{\infty}_{m=1}\Gamma^2_{\phi}(m)<\infty$, then we have

\begin{multline*}
\sum^{p-1}_{k=1} \sum^{\infty}_{m^{\prime}=1} \left( \tilde{b}_{k,m m^{\prime}} - b^{\ast}_{k,m m^{\prime}} \right)^2 \leq 2 \left( \sum_{k \in \mathscr{N}_j} \Vert \beta_{k} (t,t^{\prime}) \Vert^2_{\text{HS}} \right) \Gamma^2_{\phi}(m) \\
+ 2 \sum_{k \in \mathscr{N}_j} \sum^{\infty}_{m^{\prime}=1} \left\vert \int_{\mathcal{T}\times\mathcal{T}} \beta_{k} (t,t^{\prime}) \phi_m (t) \left( \hat{\phi}_{m^{\prime}} (t^{\prime}) - \phi_{m^{\prime}} (t^{\prime})  \right)  d t^{\prime} dt \right\vert^2,
\end{multline*}

where $\beta_{k} (t,t^{\prime})$ is defined in (<ref>).

Note that

\begin{align*}
& \quad \left\vert \tilde{b}_{k,m m^{\prime}} - b^{\ast}_{k,m m^{\prime}} \right\vert \\
& =  \left\vert \int_{\mathcal{T}\times\mathcal{T} } \beta_{k} (t,t^{\prime}) \left( \hat{\phi}_m (t) \hat{\phi}_{m^{\prime}} (t^{\prime}) - \phi_m (t) \phi_{m^{\prime}} (t^{\prime}) \right) d t^{\prime} dt \right\vert \\
& = \left\vert \int_{\mathcal{T}\times\mathcal{T}} \beta_{k} (t,t^{\prime}) \left\{ \left(\hat{\phi}_m (t) - \phi_m (t) \right) \hat{\phi}_{m^{\prime}} (t^{\prime}) + \phi_m (t) \left( \hat{\phi}_{m^{\prime}} (t^{\prime}) - \phi_{m^{\prime}} (t^{\prime})  \right)  \right\} d t^{\prime} dt \right\vert \\
& \leq \left\vert \int_{\mathcal{T}\times\mathcal{T}} \beta_{k} (t,t^{\prime})  \left(\hat{\phi}_m (t) - \phi_m (t) \right) \hat{\phi}_{m^{\prime}} (t^{\prime}) d t^{\prime} dt \right\vert + \left\vert \int_{\mathcal{T}\times\mathcal{T}} \beta_{k} (t,t^{\prime}) \phi_m (t) \left( \hat{\phi}_{m^{\prime}} (t^{\prime}) - \phi_{m^{\prime}} (t^{\prime})  \right)  d t^{\prime} dt \right\vert. \numberthis \label{eq:lemma12-helper-1}
\end{align*}

Since $\{ \phi_{m^{\prime}} \}^{\infty}_{m^{\prime}=1}$ is an orthonormal function basis, thus when we treat $\int_{\mathcal{T}} \beta_{k} (t,t^{\prime})  \left(\hat{\phi}_m (t) - \phi_m (t) \right) dt$ as a function of $t^{\prime}$, we have

\begin{align*}
& \quad \sum^{\infty}_{m^{\prime}=1} \left\vert \int_{\mathcal{T}\times\mathcal{T}} \beta_{k} (t,t^{\prime})  \left(\hat{\phi}_m (t) - \phi_m (t) \right) \hat{\phi}_{m^{\prime}} (t^{\prime}) d t^{\prime} dt \right\vert^2 \\
& = \int_{\mathcal{T}} \left( \int_{\mathcal{T}} \beta_{k} (t,t^{\prime}) \left(\hat{\phi}_m (t) - \phi_m (t) \right) d t  \right)^2 dt^{\prime} \\
& \leq \int_{\mathcal{T}} \left( \int_{\mathcal{T}} \beta^2_{k} (t,t^{\prime}) dt \right) \left( \int_{\mathcal{T}} \left(\hat{\phi}_m (t) - \phi_m (t) \right)^2 dt \right) dt^{\prime} \\
& = \Vert \hat{\phi}_m - \phi_m  \Vert^2 \Vert \beta_{k} (t,t^{\prime}) \Vert^2_{\text{HS}} \\
& \leq \Gamma^2_{\phi}(m) \Vert \beta_{k} (t,t^{\prime}) \Vert^2_{\text{HS}}. \numberthis \label{eq:lemma12-helper-2}
\end{align*}

Combine (<ref>)-(<ref>), and note that $b^*_{k,m m^{\prime}}=\tilde{b}_{k,m m^{\prime}}=0$ for all $m,m^{\prime}\geq 1$ when $k \notin \mathscr{N}_j$,
thus we have

\begin{multline*}
\sum^{p-1}_{k=1} \sum^{\infty}_{m^{\prime}=1} \left( \tilde{b}_{k,m m^{\prime}} - b^{\ast}_{k,m m^{\prime}} \right)^2 \leq 2 \left( \sum_{k \in \mathscr{N}_j} \Vert \beta_{k} (t,t^{\prime}) \Vert^2_{\text{HS}} \right) \Gamma^2_{\phi}(m) \\
+ 2 \sum_{k \in \mathscr{N}_j} \sum^{\infty}_{m^{\prime}=1} \left\vert \int_{\mathcal{T}\times\mathcal{T}} \beta_{k} (t,t^{\prime}) \phi_m (t) \left( \hat{\phi}_{m^{\prime}} (t^{\prime}) - \phi_{m^{\prime}} (t^{\prime})  \right)  d t^{\prime} dt \right\vert^2.
\end{multline*}

Recall that $\bm{g_i}(\cdot)=(g_{i1}(\cdot), g_{i2}(\cdot), \dots, g_{ip}(\cdot) )^{\top}$ is our $i$-th observation defined in Section <ref> and $e_{ij}(\cdot)$ is the error term defined in Assumption <ref>. Besides, recall that $\phi_{m}=\phi_{jm}$ and $\hat{\phi}_{m}=\hat{\phi}_{jm}$ are the $m$-th basis function and its corresponding estimate respectively used to do projection for the $j$-th node, defined in Section <ref>. Recall from (<ref>)

\begin{equation*}
\bm{v_{iM}} = \sum^{p-1}_{k=1} (\bm{\tilde{B}_{k,M}}-\bm{B^{\ast}_{k,M}}) \bm{\hat{a}^{X_k}_{i,M}} + (\bm{\tilde{r}_{i,M}}-\bm{r_{i,M}}) + (\bm{\tilde{w}_{i,M}} - \bm{w_{i,M}}),
\end{equation*}

and suppose that

\begin{equation*}
\frac{1}{n} \sum^n_{i=1} \Vert g_{ij} \Vert^2 \leq \Gamma_g (j) \, \text{ for all } j \in [p],
\end{equation*}

\begin{equation*}
\frac{1}{n} \sum^n_{i=1} \Vert e_{ij} \Vert^2 \leq  \Gamma_e \text{ for all } j \in [p],
\end{equation*}

\begin{equation*}
\Vert \hat{\phi}_m - \phi_m \Vert \leq \Gamma_{\phi}(m) \, \text{ for all } m \geq 1,
\end{equation*}

where $\sum^{\infty}_{m=1}\Gamma^2_{\phi}(m)<\infty$. Then,

\begin{equation}
\label{eq:lemma14-res1}
\frac{1}{n} \sum^n_{i=1} v^2_{i m} \leq \text{I}_m + \text{II}_m + \text{III}_m,
\end{equation}

\begin{align*}
\text{I}_m & = 6  \left( \sum_{k \in \mathscr{N}_j} \Gamma_g(k) \right) \left\{ \left( \sum_{k \in \mathscr{N}_j} \Vert \beta_{k} (t,t^{\prime}) \Vert^2_{\text{HS}} \right) \Gamma^2_{\phi}(m) \right. \\
& \quad \quad \left. + \sum_{k \in \mathscr{N}_j} \sum^{\infty}_{m^{\prime}=1} \left\vert \int_{\mathcal{T}\times\mathcal{T}} \beta_{k} (t,t^{\prime}) \phi_m (t) \left( \hat{\phi}_{m^{\prime}} (t^{\prime}) - \phi_{m^{\prime}} (t^{\prime})  \right)  d t^{\prime} dt \right\vert^2 \right\}.\\
\text{II}_m & = 3 \left( \sum_{k \in \mathscr{N}_j} \sum^{\infty}_{m^{\prime}=M+1} \left( b^{\ast}_{k,m m^{\prime}} \right)^2  \right) \left( \sum_{k \in \mathscr{N}_j} \Gamma_g(k) \right) \left( \sum^{\infty}_{m^{\prime}=M+1}  \Gamma^2_{\phi}(m^{\prime}) \right), \\
\text{III}_m & =  3 \Gamma_e \Gamma^2_{\phi}(m).
\end{align*}

Recall that $\beta_{jk} (t,t^{\prime})$ is defined in (<ref>). Drop the subscript $j$ and let $\beta_{k} (t,t^{\prime})=\beta_{jk} (t,t^{\prime})$. Recall that $b^{\ast}_{k,m m^{\prime}} = \int_{\mathcal{T}\times \mathcal{T}} \beta_k (t^{\prime},t) \phi_m (t) \phi_{m^{\prime}} (t^{\prime}) dt^{\prime} dt$ is defined in (<ref>).
Furthermore, we have

\begin{equation}
\label{eq:lemma14-res2}
\begin{aligned}
\frac{1}{n} \sum^n_{i=1} \Vert \bm{v_i} \Vert^2 & \leq 12 \left( \sum^{\infty}_{m=1}\Gamma^2_{\phi}(m) \right)\left( \sum_{k \in \mathscr{N}_j} \Vert \beta_{k} (t,t^{\prime}) \Vert^2_{\text{HS}} \right)   \left( \sum_{k \in \mathscr{N}_j} \Gamma_g(k) \right) \\
& + 3 \Phi^2(M) \left( \sum_{k \in \mathscr{N}_j} \Gamma_g(k) \right) \left( \sum^{\infty}_{m^{\prime}=M+1}  \Gamma^2_{\phi}(m^{\prime}) \right) + 3 \Gamma_e \sum^M_{m=1} \Gamma^2_{\phi}(m),
\end{aligned}
\end{equation}

where, as previously defined in (<ref>),

\begin{equation*}
\Phi (M) = \sqrt{ \sum^{p-1}_{k=1} \sum^M_{m=1} \sum^{\infty}_{m^{\prime}=M+1} \left( b^{\ast}_{k,m m^{\prime}} \right)^2 }.
\end{equation*}

Note that

\begin{align*}
v_{i m} & =  \sum^{p-1}_{k=1} \sum^{M}_{m^{\prime}=1} (\tilde{b}_{k,m m^{\prime}} - b^{\ast}_{k,m m^{\prime}}) \hat{a}^{X_k}_{i m^{\prime}} + \sum^{p-1}_{k=1} \sum^{\infty}_{m^{\prime}=M+1} \left(\tilde{b}_{k,m m^{\prime}} \hat{a}^{X_k}_{i m^{\prime}} - b^{\ast}_{k,m m^{\prime}} a^{X_k}_{i m^{\prime}} \right) + \langle e_{ij}(t), \hat{\phi}_m(t) - \phi_m(t)  \rangle \\
& =  \sum_{k \in \mathscr{N}_j} \sum^{M}_{m^{\prime}=1} (\tilde{b}_{k,m m^{\prime}} - b^{\ast}_{k,m m^{\prime}}) \hat{a}^{X_k}_{i m^{\prime}} + \sum_{k \in \mathscr{N}_j} \sum^{\infty}_{m^{\prime}=M+1} \left(\tilde{b}_{k,m m^{\prime}} \hat{a}^{X_k}_{i m^{\prime}} - b^{\ast}_{k,m m^{\prime}} a^{X_k}_{i m^{\prime}} \right) + \langle e_{ij}(t), \hat{\phi}_m(t) - \phi_m(t)  \rangle \\
& =  \sum_{k \in \mathscr{N}_j} \sum^{\infty}_{m^{\prime}=1} (\tilde{b}_{k,m m^{\prime}} - b^{\ast}_{k,m m^{\prime}}) \hat{a}^{X_k}_{i m^{\prime}} + \sum_{k \in \mathscr{N}_j} \sum^{\infty}_{m^{\prime}=M+1} b^{\ast}_{k,m m^{\prime}} (\hat{a}^{X_k}_{i m^{\prime}} - a^{X_k}_{i m^{\prime}}) + \langle e_{ij}(t), \hat{\phi}_m(t) - \phi_m(t)  \rangle.
\end{align*}

By Jensen's inequality, we have

\begin{align*}
v^2_{i m} & \leq 3 \left( \sum_{k \in \mathscr{N}_j} \sum^{\infty}_{m^{\prime}=1} (\tilde{b}_{k,m m^{\prime}} - b^{\ast}_{k,m m^{\prime}}) \hat{a}^{X_k}_{i m^{\prime}}  \right)^2 + 3 \left( \sum_{k \in \mathscr{N}_j} \sum^{\infty}_{m^{\prime}=M+1} b^{\ast}_{k,m m^{\prime}} (\hat{a}^{X_k}_{i m^{\prime}} - a^{X_k}_{i m^{\prime}})  \right)^2 \\
& \quad + 3 \left( \langle e_{ij}(t), \hat{\phi}_m(t) - \phi_m(t)  \rangle \right)^2.
\end{align*}

By Cauchy-Schwartz inequality, we further have

\begin{align*}
v^2_{i m} & \leq  3 \left( \sum_{k \in \mathscr{N}_j} \sum^{\infty}_{m^{\prime}=1} (\tilde{b}_{k,m m^{\prime}} - b^{\ast}_{k,m m^{\prime}})^2  \right) \left( \sum_{k \in \mathscr{N}_j} \sum^{\infty}_{m^{\prime}=1} \left( \hat{a}^{X_k}_{i m^{\prime}} \right)^2 \right) \\
+ & 3 \left( \sum_{k \in \mathscr{N}_j} \sum^{\infty}_{m^{\prime}=M+1} \left( b^{\ast}_{k,m m^{\prime}} \right)^2  \right) \left( \sum_{k \in \mathscr{N}_j} \sum^{\infty}_{m^{\prime}=M+1} (\hat{a}^{X_k}_{i m^{\prime}} - a^{X_k}_{i m^{\prime}})^2  \right) + 3 \Vert e_{ij}(t) \Vert^2 \Vert \hat{\phi}_m(t) - \phi_m(t) \Vert^2.
\end{align*}

Note that $\sum^{\infty}_{m=1} (\hat{a}^{X_k}_{i m} )^2=\Vert g^{X_k}_i \Vert^2$, thus we have

\begin{align*}
\frac{1}{n} \sum^n_{i=1} v^2_{i m} & \leq  3 \left( \sum_{k \in \mathscr{N}_j} \sum^{\infty}_{m^{\prime}=1} (\tilde{b}_{k,m m^{\prime}} - b^{\ast}_{k,m m^{\prime}})^2  \right) \left( \sum_{k \in \mathscr{N}_j} \frac{1}{n} \sum^n_{i=1} \Vert g^{X_k}_i \Vert^2 \right) \\
+ & 3 \left( \sum_{k \in \mathscr{N}_j} \sum^{\infty}_{m^{\prime}=M+1} \left( b^{\ast}_{k,m m^{\prime}} \right)^2  \right) \left( \sum_{k \in \mathscr{N}_j} \sum^{\infty}_{m^{\prime}=M+1} \frac{1}{n} \sum^n_{i=1} (\hat{a}^{X_k}_{i m^{\prime}} - a^{X_k}_{i m^{\prime}})^2  \right) \\
+ & 3 \left( \frac{1}{n} \sum^n_{i=1} \Vert e_{ij}(t) \Vert^2 \right) \Vert \hat{\phi}_m(t) - \phi_m(t) \Vert^2 \\
\overset{\Delta}{=} & \text{I}^{\prime}_m + \text{II}^{\prime}_m + \text{III}^{\prime}_m.
\end{align*}

By Lemma <ref> and our assumption, we have

\begin{multline*}
\text{I}^{\prime}_m \leq 6  \left( \sum_{k \in \mathscr{N}_j} \Gamma_g(k) \right) \left\{ \left( \sum_{k \in \mathscr{N}_j} \Vert \beta_{k} (t,t^{\prime}) \Vert^2_{\text{HS}} \right) \Gamma^2_{\phi}(m) \right. \\
\left. + \sum_{k \in \mathscr{N}_j} \sum^{\infty}_{m^{\prime}=1} \left\vert \int_{\mathcal{T}\times\mathcal{T}} \beta_{k} (t,t^{\prime}) \phi_m (t) \left( \hat{\phi}_{m^{\prime}} (t^{\prime}) - \phi_{m^{\prime}} (t^{\prime})  \right)  d t^{\prime} dt \right\vert^2 \right\}.
\end{multline*}

By Lemma <ref>, we have

\begin{equation*}
\frac{1}{n} \sum^n_{i=1} \left( \hat{a}^{X_k}_{i m^{\prime}} - a^{X_k}_{i m^{\prime}} \right)^2 \leq \Gamma_g (k) \Gamma^2_{\phi}(m^{\prime}).
\end{equation*}

\begin{align*}
\text{II}^{\prime}_m & \leq  3 \left( \sum_{k \in \mathscr{N}_j} \sum^{\infty}_{m^{\prime}=M+1} \left( b^{\ast}_{k,m m^{\prime}} \right)^2  \right) \left( \sum_{k \in \mathscr{N}_j} \Gamma_g(k) \right) \left( \sum^{\infty}_{m^{\prime}=M+1}  \Gamma^2_{\phi}(m^{\prime}) \right).
\end{align*}

In addition, we have

\begin{align*}
\text{III}^{\prime}_m \leq 3 \Gamma_e \Gamma^2_{\phi}(m).
\end{align*}

Combining the above results, we complete the proof of (<ref>).

To show (<ref>), note that $\{ \phi_{m} \}^{\infty}_{m=1}$ is an orthonormal function basis, and we treat
$$\int_{\mathcal{T}} \beta_{k} (t,t^{\prime}) \left( \hat{\phi}_{m^{\prime}} (t^{\prime}) - \phi_{m^{\prime}} (t^{\prime})  \right)  d t^{\prime}$$
as a function of $t$, then we have

\begin{align*}
& \quad \sum_{k \in \mathscr{N}_j} \sum^{\infty}_{m^{\prime}=1} \sum^{\infty}_{m=1} \left\vert \int_{\mathcal{T}\times\mathcal{T}} \beta_{k} (t,t^{\prime}) \phi_m (t) \left( \hat{\phi}_{m^{\prime}} (t^{\prime}) - \phi_{m^{\prime}} (t^{\prime})  \right)  d t^{\prime} dt \right\vert^2 \\
& = \sum_{k \in \mathscr{N}_j} \sum^{\infty}_{m^{\prime}=1} \int_{\mathcal{T}} \left\{ \int_{\mathcal{T}} \beta_{k} (t,t^{\prime}) \left( \hat{\phi}_{m^{\prime}} (t^{\prime}) - \phi_{m^{\prime}} (t^{\prime})  \right)  d t^{\prime}  \right\}^2 dt \\
& \leq \sum_{k \in \mathscr{N}_j} \sum^{\infty}_{m^{\prime}=1} \int_{\mathcal{T}} \left\{ \int_{\mathcal{T}} \beta^2_{k} (t,t^{\prime}) dt  \right\} \left\{ \int_{\mathcal{T}} \left( \hat{\phi}_{m^{\prime}} (t^{\prime}) - \phi_{m^{\prime}} (t^{\prime})  \right)^2  d t^{\prime} \right\} dt \\
& = \left( \sum_{k \in \mathscr{N}_j} \Vert \beta_{k} (t,t^{\prime}) \Vert^2_{\text{HS}} \right) \left( \sum^{\infty}_{m^{\prime}=1} \Gamma^2_{\phi}(m^{\prime}) \right).
\end{align*}

Thus, we have

\begin{equation*}
\sum^M_{m=1} I_m \leq \sum^{\infty}_{m=1} I_m \leq 12 \left( \sum^{\infty}_{m=1}\Gamma^2_{\phi}(m) \right)\left( \sum_{k \in \mathscr{N}_j} \Vert \beta_{k} (t,t^{\prime}) \Vert^2_{\text{HS}} \right)   \left( \sum_{k \in \mathscr{N}_j} \Gamma_g(k) \right).
\end{equation*}

(<ref>) then follows the combination of the above inequality and (<ref>).

Let $\bm{A} \in \mathbb{R}^{m \times n}$, $\bm{B} \in \mathbb{R}^{n \times m}$. We have

\begin{align*}
& \sqrt{\rho_{\min}\left( \bm{B}^{\top} \bm{B} \right)} \Vert \bm{A} \Vert_{\text{F}} \leq \Vert \bm{BA} \Vert_{\text{F}} \leq \Vert \bm{B} \Vert_2 \Vert \bm{A} \Vert_{\text{F}} \\
\intertext{and}
&\sqrt{\rho_{\min}\left( \bm{B} \bm{B}^{\top}  \right)} \Vert \bm{A} \Vert_{\text{F}} \leq \Vert \bm{AB} \Vert_{\text{F}} \leq \Vert \bm{B} \Vert_2 \Vert \bm{A} \Vert_{\text{F}}.
\end{align*}

Let $\bm{A}=\left[ \bm{a_1}, \bm{a_2}, \dots, \bm{a_n} \right]$.

\begin{equation*}
\Vert \bm{BA} \Vert^2_{\text{F}} = \tr \left( \bm{A}^{\top} \bm{B}^{\top} \bm{B} \bm{A} \right) = \sum^{n}_{i=1} \bm{a_i}^{\top} \bm{B}^{\top} \bm{B} \bm{a_i},
\end{equation*}

we have

\begin{equation*}
\rho_{\min}\left( \bm{B}^{\top} \bm{B} \right) \Vert \bm{A} \Vert^2_{\text{F}}= \rho_{\min} \left( \bm{B}^{\top} \bm{B} \right) \sum^{n}_{i=1} \Vert \bm{a_i} \Vert^2_2 \leq \sum^{n}_{i=1} \bm{a_i}^{\top} \bm{B}^{\top} \bm{B} \bm{a_i} \leq \Vert \bm{B} \Vert^2_2 \sum^{n}_{i=1}   \Vert \bm{a_i} \Vert^2_2 = \Vert \bm{B} \Vert^2_2 \Vert \bm{A} \Vert^2_{\text{F}}.
\end{equation*}

The final result follows from taking the square root on both sides.

Let $\bm{A} \in \mathbb{R}^{n \times n}$ be symmetric and positive semi-definite, $\bm{B} \in \mathbb{R}^{n \times m}$, and $\bm{C} \in \mathbb{R}^{n \times n}$ be a diagonal matrix with positive diagonal elements. Then we have

\begin{equation*}
\Vert (\bm{A} + \bm{C}) \bm{B} \Vert_F \geq \Vert \bm{C} \bm{B} \Vert_F.
\end{equation*}

Let $j$-th column of $\bm{B}$ be $\bm{b_j}$ for $j=1,\ldots,m$. Then we have

\begin{align*}
\Vert (\bm{A} + \bm{C}) \bm{B} \Vert^2_F & = \tr \left( \bm{B}^{\top} (\bm{A} + \bm{C})^{\top} (\bm{A} + \bm{C})  \bm{B} \right) \\
& = \sum^m_{j=1} \bm{b_j}^{\top} (\bm{A} + \bm{C})^{\top} (\bm{A} + \bm{C}) \bm{b_j} \\
& = \sum^m_{j=1} \bm{b_j}^{\top} \bm{A}^{\top} \bm{A} \bm{b_j} + \sum^m_{j=1} \bm{b_j}^{\top} \bm{C}^{\top} \bm{A} \bm{b_j} + \sum^m_{j=1} \bm{b_j}^{\top} \bm{A}^{\top} \bm{C} \bm{b_j} + \sum^m_{j=1} \bm{b_j}^{\top} \bm{C}^{\top} \bm{C} \bm{b_j}.
\end{align*}

Since $\bm{A}$ is symmetric and positive semi-definite and $\bm{C}$ is a diagonal matrix with positive diagonal elements, we have $\bm{C}^{\top} \bm{A}=\bm{A}^{\top} \bm{C}=\bm{C}\bm{A}$ to be symmetric and positive semi-definite. And note that $\bm{A}^{\top} \bm{A}$ is symmetric and positive semi-definite, thus we have

\begin{equation*}
\Vert (\bm{A} + \bm{C}) \bm{B} \Vert^2_F \geq \sum^m_{j=1} \bm{b_j}^{\top} \bm{C}^{\top} \bm{C} \bm{b_j} = \tr \left( \bm{B}^{\top} \bm{C}^{\top} \bm{C} \bm{B} \right) = \Vert \bm{C} \bm{B} \Vert^2_F,
\end{equation*}

which implies the final result.

§ TABLE OF NOTATIONS

Notation     Meaning     Page

$G = (V,E)$     undirected graph, $V$ is set of vertices, $E$ is set of edges     2

$\bm{X}$     $p$-dimensional random variables     2

$M$     number of basis functions we used to do dimension reduction     3

$\bm{g}(\cdot)$     $p$-dimensional multivariate Gaussian process     5

$\mathcal{T}$     domain of multivariate Gaussian process     5

$C_{jl}(t,t')$     conditional cross-covariance function     5

$\{\bm{g_i}(\cdot)\}_{i=1}^n$     $\bm{g_i}(\cdot)=(g_{i1}(\cdot), \cdots, g_{ip}(\cdot))^\top$, random copies of $\bm{g}(\cdot)$     5

$\beta_{jk}(t,t')$     coefficient on ${g}_{ij}$ from ${g}_{ik}$     5

$\mathscr{N}_j, \hat{\mathscr{N}}_j$     (estimated) neighborhood set of node $j$     5

$e_{ij}(\cdot)$     error of $g_{ij}(\cdot)$     5

$\bm{\phi_j}$     $=\{\phi_{jm}(\cdot)\}_{m=1}^\infty$, orthonormal functional basis on $\mathbb{H}$     6

$\bm{a_{i,k,M}}$     $=(a_{ik1},\cdots,a_{ikM})^\top$, vector of projection scores     6

$g_i^Y(\cdot), g_i^{X_k}(\cdot)$     random functions of the target node and the other random functions     6

$\bm{a_{i,M}^Y}, \bm{a_{i,M}^{X_k}}, \bm{a_{i,M}^X}$     vectors of scores projected on known bases $\bm{\phi_j}$     6

$\bm{B^{\ast}_{k,M}}$     regression matrix parameter     7

$\bm{w_{i,M}}, \bm{r_{i,M}}$     noise vector and bias term for $M$-truncation     7

$\bm{\hat{B}_{k,M}}$     Estimator of $\bm{B^{\ast}_{k,M}}$     7

$\lambda_n$     penalty parameter for group Lasso regression     7

$\epsilon_n$     threshold parameter of neighborhood recognition     7

$\hat{E}$     estimated edge set    7

$\bm{\hat{a}_{i,M}^Y}, \bm{\hat{a}_{i,M}^{X_k}}, \bm{\hat{a}_{i,M}^X}$     vectors of scores projected on estimated bases $\bm{\hat{\phi}_j}$     7-8

$K_{jj}(t',t)$     functional covariance of $g_{ij}(\cdot)$     8

$\mathcal{K}_j(f)(t)$     Hilbert-Schmidt covariance operator     8

$\{\sigma_{jm}\}_{m\in\mathbb{N}}$     eigenvalues of $\mathcal{K}_j$     8

$g_{ij}^M(t)$     $\mathcal{L}^2$ projection of $g_{ij}(t)$ onto the basis spanned by the first $M$ FPCA functions     8

$\hat{K}_{jj}(t',t)$     empirical functional covariance of $g_{ij}(\cdot)$     8

$\{\hat{\sigma}_{jm},\hat{\phi}_{jm}(t)\}_{m=1}^M$     eigenpairs of $\hat{K}_{jj}(t',t)$     8

$\hat{a}_{ijm}$     $=\int_\mathcal{T} g_{ij}(t)\hat{\phi}_{jm}(t)dt$, estimated FPCA scores     8

$\bm{\hat{B}}_{\lambda_n}$     $=(\bm{\hat{B}_1},\cdots,\bm{\hat{B}_{p-1}})$, group Lasso estimates under a fixed $\lambda_n$     9

$\bm{\Tilde{B}_k}$     estimates of $\bm{B_k}$ in selective cross-validation process     10

$\bm{\hat{\epsilon}_i}$     $=\bm{a^Y_{i,M}} - \sum^{p-1}_{k=1} \bm{\tilde{B}_{k}} \bm{a^{X_k}_{i,M}}$, residuals of $\bm{\Tilde{B}_k}$     10

$\bm{A^Y}, \bm{A^{X_k}}, \bm{A^X}$     matrices of FPCA scores     10

$\rho, \rho^h$     penalty parameter for ADMM subproblem (on iteration $h$)     10

$b^{\ast}_{k,m m^{\prime}}$     $= \int_{\mathcal{T}\times \mathcal{T}} \beta_k (t^{\prime},t) \phi_m (t) \phi_{m^{\prime}} (t^{\prime}) dt^{\prime} dt$     12

$\beta_{k,M} (t^{\prime},t)$     $ =  \sum^{M}_{m,m^{\prime}=1} b^{\ast}_{k,m m^{\prime}} \phi_m (t) \phi_{m^{\prime}} (t^{\prime})$     13

$\beta_{k, >M} (t^{\prime},t)$     $=  \sum^{\infty}_{m>M \,\text{or}\, m^{\prime}>M} b^{\ast}_{k,m m^{\prime}} \phi_m (t) \phi_{m^{\prime}} (t^{\prime})$     13

$\bm{\Sigma^{X_k,r}}$     $=\Cov(\bm{a_{i,M}^{X_k}}, \bm{r_{i,M}})$, and $\bm{\Sigma^{r, X_k}} = (\bm{\Sigma^{X_k,r}})^\top$     13

$\bm{\Sigma^{X_k,X_l}}$     $=\Cov(\bm{a_{i,M}^{X_k}}, \bm{a_{i,M}^{X_l}})$    13

$\Xi_1(M)$     $=  \max_{k \in [p-1]} \left\{ \rho_{\max}(\bm{\Sigma^w}+\bm{\Sigma^r}-\bm{\Sigma^{r,X_k}} \left( \bm{\Sigma^{X_k, X_k}} \right)^{-1} \bm{\Sigma^{{X_k},r}}) \right\}$     13

$\Xi_2(M)$     $=  \max_{k \in[p-1]}\rho_{\max}(\bm{\Sigma^{X_k, X_k}})$     13

$\Xi_3(M)$     $=  \max_{k \in[p-1]}\tr(\bm{\Sigma^{X_k, X_k}})$     13

$\Xi_4(M)$     $=  \tr \left\{ \bm{\Sigma^r} + \bm{\Sigma^w} + \bm{\Sigma^{r,w}} + \bm{\Sigma^{w,r}} \right\}$    13

$\omega(M)$    $=  \max_{k \in [p-1]} \left\Vert \bm{\Sigma^{r,X_k}}\right\Vert_{\text{F}}$     13

Notation     Meaning     Page

$K_0$     $=\max_{k\in[p-1], m\in M} \mathbb{E}[(a_{i,m}^{X_k})^2]$, used to derive an upper bound for the estimation error of the covariance matrix of $\bm{a_{i,M}^X}$     13

$\kappa(M)$     $=\rho_{\min}\left((\bm{\Sigma}^X)_{\mathscr{N}_j, \mathscr{N}_j}\right)$     14

$\tau(M)$     $=\min_{k \in \mathscr{N}_j} \left\Vert \bm{B^{\ast}_k} \right\Vert_{\text{F}} = \min_{k \in \mathscr{N}_j} \left\Vert \beta_{k, M} (t^{\prime},t) \right\Vert_{\text{HS}}$, relevant signal strength    14

$\chi(n,p,M,\delta)$     $=\frac{6\sqrt{s}}{\sqrt{\kappa(M)}} \tilde{\lambda} (n, p, M, \delta)$     14

$\tilde{\lambda} (n, p, M, \delta)$     exact form can be found in (<ref>)    14

$\Phi(M)$     $=\sqrt{ \sum^{p-1}_{k=1} \sum^M_{m=1} \sum^{\infty}_{m^{\prime}=M+1} \left( b^{\ast}_{k,m m^{\prime}} \right)^2 }$     16

$\check{\chi}(n,p,M,\delta)$     $= \frac{6\sqrt{s}}{\sqrt{\kappa(M)}} \check{\lambda} (n, p, M, \delta)$     16

$\check{\lambda} (n, p, M, \delta)$     exact form given in (<ref>)    16

$\Lambda(M,\bm{\phi})$     $\frac{\omega(M)}{\sqrt{\kappa(M)}\tau(M)}$     17

$(\bm{a_{i1}},\cdots, \bm{a_{ip}})^\top$     generated functional scores from a mean zero Gaussian distribution     18

$\bm{f}(\cdot)$     vector of Fourier basis functions     18

$M^*$     number of basis functions contained in $\bm{f}(\cdot)$     18

$\bm{\Sigma}$     covariance matrix of $(\bm{a_{i1}},\cdots, \bm{a_{ip}})^\top$     18

$\bm{\Theta}$     $=\bm{\Sigma}^{-1}$, precision matrix     18

$T$      number of observation time points     19

$\epsilon_{ijk}$     observation error of $g_{ij}(t_k)$     19

$\sigma$     variance of $\epsilon_{ijk}$     19