$C_{\zeta}=C_{4}(1+\vartheta_{2})\max_{m=1,\ldots,M}\rho_{x}^{1/2}\rho_{a}^{1/2}\\{\rho_{b}^{1/2}\|\bm{\Sigma}^{m,\mathbf{u}}\|_{2}^{1/2}+(\rho_{b}\rho_{a})^{1/2}\|\bm{\Sigma}^{m,\mathbf{q}}\|_{2}^{1/2}+\|\bm{\Sigma}_{i}^{\mathbf{r}}\|_{2}^{1/2}+\|\bm{\Sigma}_{i}^{\mathbf{w}}\|_{2}^{1/2}\\}.$

Assume conditions of Lemma D.2 hold and sample size
$N=O(C_{\zeta}^{2}\\{(\alpha^{\star}k)^{2}+\log p\\})$. For any support set
$\bar{{\mathcal{S}}}_{i}$ defined in (D.5) satisfying
$|\bar{{\mathcal{S}}}_{i}|\leq C_{5}k^{2}s^{\star}$, we have

$\frac{1}{M}\|[\nabla_{\mathbf{B}_{i}}f(\mathbf{A}^{\star},\mathbf{B}^{\star})]_{\bar{\mathcal{S}}_{i}}\|_{r(k,\infty)}>C_{\zeta}\sqrt{\frac{(\alpha^{\star}k)^{2}+\log
p}{N}},$

with probability smaller than $p^{-1}\exp\\{-(\alpha^{\star}k)^{2}\\}$.

###  D.3 One-step Update

With results from Lemma D.1–D.4 introduced in Section D.2 as the building
blocks, we are able to construct the analysis of the one-step update of
Algorithm 1. Noting that the sample complexity required in Lemma D.1–D.4
depend on some condition numbers $\kappa_{m}$, $C_{\epsilon}$ and $C_{\zeta}$.
We assume that $\kappa_{m}^{2}$, $C_{\epsilon}^{2}$ and $C_{\zeta}^{2}$ are
not large and see them as constants. Therefore, we could drop the terms and
simplify the notations by focusing the rates of convergence with respect to
$\alpha^{\star}$, $k$, $s^{\star}$,$p$, $M$ and $k_{m}$ for $m=1,\ldots,M$.
Lemma D.5 states that with proper initial condition and step size $\eta_{A}$
and $\eta_{B}$, the distance $\max_{i\in
V}\|\mathbf{B}_{i}^{+}-\mathbf{B}_{i}^{\star}\|_{F}^{2}+\max_{m=1,\ldots,M}\|\mathbf{A}^{m+}-\mathbf{A}^{m\star}\|_{F}^{2}$
is contracted at each iteration.

######  Lemma D.5.

[One-Step Update] Suppose that the conditions of Lemma D.2 hold. Let
$N=O(s^{\star}\max_{m=1,\ldots,M}k_{m}+(\alpha^{\star}k)^{2}+\log p+\log M)$ .
Define

$\rho_{1}=4\left\\{1-\frac{3p(s^{\star}+1)\Upsilon_{1}}{4\Upsilon_{2}}\eta_{A}\right\\},\quad\rho_{2}=C_{\vartheta}\left(1-\frac{M\Upsilon_{6}}{4}\eta_{B}\right),$

and
$\delta_{0}:=\exp\\{-(s^{\star}+1)\min_{m=1,\ldots,M}k_{m}\\}\vee\exp\\{-(\alpha^{\star}k)^{2}\\}$.
Suppose that

$\displaystyle\alpha^{\star}$
$\displaystyle\leq\frac{\Upsilon_{1}\Upsilon_{6}}{32(1+\vartheta_{1})(1+\vartheta_{2})\tau_{2}\Upsilon_{2}\Upsilon_{3}^{2}},$
$\displaystyle\eta_{A}$
$\displaystyle\leq\frac{1}{3p(s^{\star}+1)}\left(\frac{\Upsilon_{6}}{8\Upsilon_{5}}\wedge\frac{2}{\Upsilon_{2}}\right),\quad\eta_{B}\leq\frac{1}{12M}\left(\frac{\Upsilon_{1}}{\Upsilon_{5}\Upsilon_{2}}\wedge\frac{\Upsilon_{6}}{2\Upsilon_{7}}\right),$

and $\eta_{A}$ and $\eta_{B}$ are selected such that $\rho_{1},\rho_{2}<1$ and
satisfy $4p\eta_{A}=C_{\vartheta}M\eta_{B}$. Then,

$\max_{i\in
V}\|\mathbf{B}_{i}^{+}-\mathbf{B}_{i}^{\star}\|_{F}^{2}+\max_{m=1,\ldots,M}\|\mathbf{A}^{m+}-\mathbf{A}^{m\star}\|_{F}^{2}\\\
\leq\rho_{1}\max_{m=1,\ldots,M}\|{\mathbf{A}^{m}}-\mathbf{A}^{m\star}\|_{F}^{2},+\rho_{2}\max_{i\in
V}\|\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}\|_{F}^{2}+\frac{\Upsilon_{8}}{\Upsilon_{1}}\max_{m=1,\ldots,M}\frac{k(k_{m}+k+\log
M)}{N}\\\
+\frac{\Upsilon_{9}}{\Upsilon_{7}}\frac{s^{\star}\\{(\alpha^{\star}k)^{2}+\log
p\\}}{N},$

with probability at least $1-10\delta_{0}$.

###### Proof of Lemma D.5.

First, we combine the results from Lemma D.1 and Lemma D.2, we can obtain

$\displaystyle\max_{i\in
V}\|\mathbf{B}_{i}^{+}-\mathbf{B}_{i}^{\star}\|_{F}^{2}$
$\displaystyle+\max_{m=1,\ldots,M}\|\mathbf{A}^{m+}-\mathbf{A}^{m\star}\|_{F}^{2}$
$\displaystyle\leq
T_{1}\max_{m=1,\ldots,M}\|{\mathbf{A}^{m}}-\mathbf{A}^{m\star}\|_{F}^{2}+T_{2}\max_{i\in
V}\|\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}\|_{F}^{2}$
$\displaystyle\quad+T_{3}\max_{m=1,\ldots,M}\|\nabla_{{\mathbf{A}^{m}}}f(\mathbf{A}^{\star},\mathbf{B}^{\star})\|_{2}^{2}$
$\displaystyle\quad+T_{4}\max_{i\in
V}\|[\nabla_{\mathbf{B}_{i}}f(\mathbf{A}^{\star},\mathbf{B}^{\star})]_{\bar{\mathcal{S}}_{i}}\|^{2}_{r(k,\infty)}$
(D.10)

where

$\displaystyle T_{1}$
$\displaystyle=4\left\\{1-\eta_{A}\frac{3p(s^{\star}+1)\Upsilon_{1}}{2\Upsilon_{2}}+\eta_{A}\frac{2ps^{\star}\Upsilon_{4}^{2}\Upsilon_{3}^{2}}{\Upsilon_{6}}\right\\}+C_{\vartheta}Ms^{\star}\eta_{B}\left(\frac{2\Upsilon_{4}^{2}\Upsilon_{3}^{2}}{\Upsilon_{6}}+3\Upsilon_{5}M\eta_{B}\right);$
$\displaystyle T_{2}$
$\displaystyle=C_{\vartheta}{\left(1-\eta_{B}M\Upsilon_{6}+3\eta_{B}^{2}M^{2}\Upsilon_{7}\right)}+4p\eta_{A}\left(\frac{\Upsilon_{6}}{2}+3p(s^{\star}+1)\Upsilon_{5}\eta_{A}\right);$
$\displaystyle T_{3}$
$\displaystyle=4k\eta_{A}\left(\frac{4\Upsilon_{2}}{p(s^{\star}+1)\Upsilon_{1}}+3\eta_{A}\right);$
$\displaystyle T_{4}$
$\displaystyle=C_{\vartheta}(1+\vartheta_{1})s^{\star}\eta_{B}\left(\frac{2}{M\Upsilon_{6}}+3\eta_{B}\right).$

First, we want to simplify the term of $T_{1}$. With the choices of
$\alpha^{\star}$, $\eta_{B}$ in the statement, we can obtain

$\displaystyle\frac{2ps^{\star}\Upsilon_{4}^{2}\Upsilon_{3}^{2}}{\Upsilon_{6}}\leq\frac{p(s^{\star}+1)\Upsilon_{1}}{4\Upsilon_{2}},\quad\left(\frac{2\Upsilon_{4}^{2}\Upsilon_{3}^{2}}{\Upsilon_{6}}+3\Upsilon_{5}M\eta_{B}\right)\leq\frac{\Upsilon_{1}}{2\Upsilon_{2}}.$

Since $4p\eta_{A}=C_{\vartheta}M\eta_{B}$, we can conclude

$\displaystyle T_{1}\leq
4\left\\{1-\frac{3p(s^{\star}+1)\Upsilon_{1}}{4\Upsilon_{2}}\eta_{A}\right\\}.$

Next, we want to simplify the term $T_{2}$. Similarly, with the choices of
$\alpha^{\star}$, $\eta_{B}$, and $\eta_{A}$, we have

$\displaystyle 3\eta_{B}M^{2}\Upsilon_{7}\leq\frac{M\Upsilon_{6}}{8},\quad
3p(s^{\star}+1)\Upsilon_{5}\eta_{A}\leq\frac{\Upsilon_{6}}{8};$

Then, using the fact that $p\eta_{A}=C_{\vartheta}\eta_{B}$, we can conclude
that

$\displaystyle T_{2}\leq
C_{\vartheta}\left\\{1-\frac{M\Upsilon_{6}}{4}\eta_{B}\right\\}.$

With the choice of $\eta_{A}$, we have

$\displaystyle T_{3}$
$\displaystyle\leq\frac{32}{3}\frac{k}{\Upsilon_{1}\\{p(s^{\star}+1)\\}^{2}}+\frac{16}{3}\frac{k}{\Upsilon_{2}^{2}\\{p(s^{\star}+1)\\}^{2}}.$

Using the fact that $\Upsilon_{2}^{2}\geq 2\Upsilon_{1}$, we can further bound
the above display as

$\displaystyle
T_{3}\leq\frac{14k}{\Upsilon_{1}\\{p(s^{\star}+1)\\}^{2}}\leq\frac{14k}{\Upsilon_{1}(ps^{\star})^{2}}.$

Recall the definition of $\Upsilon_{8}$ in Section C. In fact, by Lemma D.3
and take the union bound over $m=1,\ldots,M$, we can verify that

$\displaystyle
T_{3}\max_{m=1,\ldots,M}\|\nabla_{{\mathbf{A}^{m}}}f(\mathbf{A}^{\star},\mathbf{B}^{\star})\|_{2}^{2}\leq\frac{\Upsilon_{8}}{\Upsilon_{1}}\max_{m=1,\ldots,M}k\frac{k+k_{m}+\log
M}{N},$ (D.11)

with probability at least $1-\max_{m=1,\ldots,M}\exp\\{-(k_{m}+k)\\}\geq
1-\delta_{0}$, where we define this event as $\mathcal{E}_{A}$.

We find the upper bound of $T_{4}$ in a similar way as we do for $T_{3}$. Note
that by Lemma I.1, We have $\Upsilon_{7}\geq\Upsilon_{6}^{2}$. Then, with the
choice of $\eta_{B}$, we have

$\displaystyle T_{4}\leq
C_{\vartheta}(1+\vartheta_{1})s^{\star}\left(\frac{1}{12M^{2}\Upsilon_{7}}+\frac{3}{576}\frac{1}{M^{2}\Upsilon_{7}}\right)\leq\frac{C_{\vartheta}(1+\vartheta_{1})s^{\star}}{M^{2}\Upsilon_{7}}.$

Recall the definition of $\Upsilon_{9}$ in Section C. Then, apply Lemma D.4
and take the union bound over $i\in V$, we can obtain that

$T_{4}\max_{i\in
V}\|[\nabla_{\mathbf{B}_{i}}f(\mathbf{A}^{\star},\mathbf{B}^{\star})]_{\bar{\mathcal{S}}_{i}}\|_{r(k,\infty)}^{2}\leq\frac{\Upsilon_{9}}{\Upsilon_{7}}\frac{s^{\star}\\{(\alpha^{\star}k)^{2}+\log
p\\}}{N},$ (D.12)

with probability at least $1-\exp\\{-(\alpha^{\star}k)^{2}\\}\geq
1-\delta_{0}$ and we define such event as $\mathcal{E}_{B}$.

Let $\mathcal{E}$ be the event when Lemma D.1–D.2 hold. Therefore, by De
Morgan’s law, $\mathcal{E}\cap\mathcal{E}_{A}\cap\mathcal{E}_{B}$ happens with
probability at least $1-10\delta_{0}$. ∎

###  D.4 Proof of Theorem 5.3

First, we apply Lemma D.5 for one iteration and obtain that with probability
at least $1-10\delta_{0}$:

$\max_{i\in
V}\|\mathbf{B}_{i}^{(1)}-\mathbf{B}_{i}^{\star}\|_{F}^{2}+\max_{m=1,\ldots,M}\|\mathbf{A}^{m(1)}-\mathbf{A}^{m\star}\|_{F}^{2}\\\
\leq\rho_{1}\max_{m=1,\ldots,M}\|\mathbf{A}^{m(0)}-\mathbf{A}^{m\star}\|_{F}^{2},+\rho_{2}\max_{i\in
V}\|\mathbf{B}_{i}^{(0)}-\mathbf{B}_{i}^{\star}\|_{F}^{2}+\Xi^{2},$

where the right hand side is bounded by
$(C_{1}+1)(C_{A}^{2}\rho_{a}+C_{B}^{2}\rho_{b})$ because (i)
$\rho_{1},\rho_{2}<1$ and (ii) $\Xi^{2}\leq
C_{1}(C_{A}^{2}\rho_{a}+C_{B}^{2}\rho_{b})$ under the condition of Theorem
5.3. Therefore, we apply Lemma D.5 again to obtain the upper bound for
$\max_{i\in
V}\|\mathbf{B}_{i}^{(2)}-\mathbf{B}_{i}^{\star}\|_{F}^{2}+\max_{m=1,\ldots,M}\|\mathbf{A}^{m(2)}-\mathbf{A}^{m\star}\|_{F}^{2}$:

$\max_{i\in
V}\|\mathbf{B}_{i}^{(2)}-\mathbf{B}_{i}^{\star}\|_{F}^{2}+\max_{m=1,\ldots,M}\|\mathbf{A}^{m(2)}-\mathbf{A}^{m\star}\|_{F}^{2}\\\
\leq\rho_{1}\max_{m=1,\ldots,M}\|\mathbf{A}^{m(1)}-\mathbf{A}^{m\star}\|_{F}^{2},+\rho_{2}\max_{i\in
V}\|\mathbf{B}_{i}^{(1)}-\mathbf{B}_{i}^{\star}\|_{F}^{2}+(1+\pi)\Xi^{2},$

where $\pi=\rho_{1}\vee\rho_{2}$ and with probability at least
$1-10\delta_{0}$.

Then, iterate for $L$ times and by the telescoping technique, we complete the
proof:

$\displaystyle\max_{m=1,\ldots,M}\|\mathbf{A}^{m(L)}-\mathbf{A}^{m\star}\|_{F}^{2}+\max_{i\in
V}\|\mathbf{B}_{i}^{(L)}-\mathbf{B}_{i}^{\star}\|_{F}^{2}\leq\pi^{L}R_{0}^{2}+\frac{1}{1-\pi}\Xi^{2},$

with probability at least $1-10\delta_{0}$.

###  D.5 Proof of Lemma D.1–D.4

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

We study one iteration for updating ${\mathbf{A}^{m}}$ for $m=1,\ldots,M$ via
Algorithm 1 and we have

$\displaystyle\|\mathbf{A}^{m+}-\mathbf{A}^{m\star}\|_{F}^{2}$
$\displaystyle={\|\mathcal{P}_{\tau}\left({\mathbf{A}^{m}}-\eta_{A}\nabla_{{\mathbf{A}^{m}}}f(\mathbf{A},\mathbf{B})\right)-\mathbf{A}^{m\star}\|_{F}^{2}}.$
First, we claim that any row of $\mathbf{A}^{m\star}$ is in
$\mathcal{K}_{m}(\tau_{1},\tau_{2})$ defined by (3.8) with probability at
least $1-5\exp(-\sum_{m=1}^{2}k_{m})$. Then, apply Lemma H.1 and the above
display could be further bounded as $\displaystyle\leq
4{\|{\mathbf{A}^{m}}-\eta_{A}\nabla_{{\mathbf{A}^{m}}}f(\mathbf{A},\mathbf{B})-\mathbf{A}^{m\star}\|_{F}^{2}}$
$\displaystyle=4\\{\|{\mathbf{A}^{m}}-\mathbf{A}^{m\star}\|_{F}^{2}-2\eta_{A}\mathcal{I}_{1,m}+\eta_{A}^{2}\mathcal{I}_{2,m}\\},$

where

$\mathcal{I}_{1,m}=\langle{\nabla_{{\mathbf{A}^{m}}}f(\mathbf{A},\mathbf{B})},{{\mathbf{A}^{m}}-\mathbf{A}^{m\star}}\rangle,\quad\mathcal{I}_{2,m}=\|\nabla_{{\mathbf{A}^{m}}}f(\mathbf{A},\mathbf{B})\|_{F}^{2}.$

Now we justify the claim that any row of $\mathbf{A}^{m\star}$ is in
$\mathcal{K}_{m}(\tau_{1},\tau_{2})$. For each row $j=1,\ldots,k$, we could
apply triangle inequality and obtain that

$\displaystyle\|\mathbf{A}_{j\cdot}^{m\star}\|_{2}$
$\displaystyle\leq\|\mathbf{A}_{j\cdot}^{m\star}-\mathbf{A}_{j\cdot}^{m(0)}\|_{2}+\|\mathbf{A}_{j\cdot}^{m(0)}\|_{2}$
$\displaystyle\leq\|\mathbf{A}_{j\cdot}^{m\star}-\mathbf{A}_{j\cdot}^{m(0)}\|_{2}+\|\mathbf{A}^{m(0)}\|_{2}.$

Under Assumption 4 and $N=O(\max_{m=1,\ldots,M}\kappa_{m}^{2}k_{m})$, by
Theorem 5.1, we know that
$\|\mathbf{A}_{j\cdot}^{m\star}-\mathbf{A}_{j\cdot}^{m(0)}\|_{2}$ is bounded
by some small constant with probability at least
$1-5\exp(-\sum_{m=1}^{M}k_{m})$, and we define such event as
$\mathcal{E}_{I}$. Therefore, there exists some finite $\tau_{2}>0$ such that
$\|\mathbf{A}_{j\cdot}^{m\star}\|_{2}\leq\tau_{2}k_{m}^{-1/2}\|\mathbf{A}^{m(0)}\|_{2}$
for $j=1,\ldots,k$. The existence of a valid $\tau_{1}$ can be justified in a
similar way and hence we omit the step.

In order to find the upper bound of
$\|\mathbf{A}^{m+}-\mathbf{A}^{m\star}\|_{F}^{2}$, it suffices to find the
lower bound of $\mathcal{I}_{1,m}$ and the upper bound of $\mathcal{I}_{2,m}$,
which are presented in the Lemma D.6 and Lemma D.7, respectively.

On the event of $\mathcal{E}_{I}$, combining the results of Lemma D.6–D.7 and
taking the maximum over $m=1,\ldots,M$ on both sides, we obtain that

$\displaystyle\frac{1}{4}\max_{m=1,\ldots,M}\|\mathbf{A}^{m+}-\mathbf{A}^{m\star}\|_{F}^{2}$
$\displaystyle\leq\left(1-\eta_{A}\frac{3p(s^{\star}+1)\Upsilon_{1}}{2\Upsilon_{2}}+\eta_{A}\frac{2ps^{\star}\Upsilon_{4}^{2}\Upsilon_{3}^{2}}{\Upsilon_{6}}\right)\max_{m=1,\ldots,M}\|{\mathbf{A}^{m}}-\mathbf{A}^{m\star}\|_{F}^{2}$
$\displaystyle\quad+k\eta_{A}\left(\frac{4\Upsilon_{2}}{p(s^{\star}+1)\Upsilon_{1}}+3\eta_{A}\right)\max_{m=1,\ldots,M}\|\nabla_{{\mathbf{A}^{m}}}f(\mathbf{A}^{\star},\mathbf{B}^{\star})\|_{2}^{2}$
$\displaystyle\quad+p\eta_{A}\left(\frac{\Upsilon_{6}}{2}+3p(s^{\star}+1)\Upsilon_{5}\eta_{A}\right)\max_{i\in
V}\|\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}\|_{F}^{2}$
$\displaystyle\quad+\eta_{A}\left(-\frac{2}{p(s^{\star}+1)\Upsilon_{2}}+3\eta_{A}\right)$
$\displaystyle\quad\times\left\\{\max_{m=1,\ldots,M}\|\nabla_{{\mathbf{A}^{m}}}f(\mathbf{A},\mathbf{B}^{\star})-\nabla_{{\mathbf{A}^{m}}}f(\mathbf{A}^{\star},\mathbf{B}^{\star})\|_{F}^{2}\right\\}.$
(D.13)

with probability at least
$1-\max_{m=1,\ldots,M}\exp\\{-k_{m}(s^{\star}+1)\\}$. By conditions of
$\eta_{A}$, $-{2}/\\{p(s^{\star}+1)\Upsilon_{2}\\}+3\eta_{A}<0$ and hence we
can drop the last term of (D.5).

Then, marginalizing over the event $\mathcal{E}_{I}$, (D.8) holds with
probability at least

$\left\\{1-5\exp\left(-\sum_{m=1}^{M}k_{m}\right)\right\\}\left[1-\max_{m=1,\ldots,M}\exp\\{-k_{m}(s^{\star}+1)\\}\right]\\\
\geq 1-\max_{m=1,\ldots,M}6\exp\\{-k_{m}(s^{\star}+1)\\}.$

∎

###### Proof of Lemma D.2.

We study one iteration for updating $\mathbf{B}_{i}$ for $i\in[p]$ via
Algorithm 1. Recall that $s=\vartheta_{1}s^{\star}/2$ and
$\alpha=\vartheta_{2}\alpha^{\star}/2$. Then, apply Lemma H.3–H.4 and (D.7),
we have

$\|\mathbf{B}_{i}^{+}-\mathbf{B}_{i}^{\star}\|_{F}^{2}=\|\mathcal{H}_{\alpha}\circ{\mathcal{T}}_{s}\left\\{\mathbf{B}_{i}-\eta_{B}[\nabla_{\mathbf{B}_{i}}f(\mathbf{A},\mathbf{B})]_{\bar{\mathcal{S}}_{i}}\right\\}-\mathbf{B}_{i}^{\star}\|_{F}^{2}\\\
\leq
C_{\vartheta}\big{\\{}\|\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}\|_{F}^{2}-2\eta_{B}\mathcal{I}_{3,i}+\eta_{B}^{2}\mathcal{I}_{4,i}\big{\\}},$
(D.14)

where

$\mathcal{I}_{3,i}=\langle{[\nabla_{\mathbf{B}_{i}}f(\mathbf{A},\mathbf{B})]_{\bar{\mathcal{S}}_{i}}},{\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}}\rangle,\quad\mathcal{I}_{4,i}=\|[\nabla_{\mathbf{B}_{i}}f(\mathbf{A},\mathbf{B})]_{\bar{\mathcal{S}}_{i}}\|_{F}^{2}.$

Next, we will apply Lemma D.8 for the lower bound of $\mathcal{I}_{3,i}$ and
apply Lemma D.9 for the upper bound of $\mathcal{I}_{4,i}$ for $i\in V$.

Combining Lemma D.8–D.9 and taking the maximum over $i\in V$ yields,

$\displaystyle\max_{i\in
V}\|\mathbf{B}_{i}^{+}-\mathbf{B}_{i}^{\star}\|_{F}^{2}$ $\displaystyle\leq
C_{\vartheta}\bigg{\\{}\left(1-\eta_{B}M\Upsilon_{6}+3\eta_{B}^{2}M^{2}\Upsilon_{7}\right)\max_{i\in
V}\|\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}\|_{F}^{2}$
$\displaystyle\quad+Ms^{\star}\eta_{B}\left(\frac{2\Upsilon_{4}^{2}\Upsilon_{3}^{2}}{\Upsilon_{6}}+3\Upsilon_{5}M\eta_{B}\right)\max_{m=1,\ldots,M}\|{\mathbf{A}^{m}}-\mathbf{A}^{m\star}\|_{F}^{2}$
$\displaystyle\quad+(1+\vartheta_{1})s^{\star}\eta_{B}\left(\frac{2}{M\Upsilon_{6}}+3\eta_{B}\right)\max_{i\in
V}\|[\nabla_{\mathbf{B}_{i}}f(\mathbf{A}^{\star},\mathbf{B}^{\star})]_{\bar{\mathcal{S}}_{i}}\|^{2}_{r(k,\infty)}\bigg{\\}},$

with probability at least $1-\max_{m=1,\ldots,M}\exp(-k_{m}s^{\star})$.

∎

Before showing the proofs of Lemma D.3–D.4, we introduce the notion of Orlicz
norm, where we only consider the sub-exponential and sub-Gaussian cases here.
Assume that $X$ is a sub-exponential random variable, and sub-exponential norm
is defined as

$\displaystyle\|X\|_{\psi_{1}}=\inf\\{t>0:\mathbb{E}\exp(|X|/t)\leq 2\\}.$

Assume that $X$ is a sub-Gaussian random variable, and sub-Gaussian norm is
defined as

$\displaystyle\|X\|_{\psi_{2}}=\inf\\{t>0:\mathbb{E}\exp(|X|^{2}/t^{2})\leq
2\\}.$

###### Proof of Lemma D.3.

Let $\mathcal{N}_{1}$ be the $1/8$-net of
$\mathbb{S}^{k-1}=\\{\mathbf{v}\in\mathbb{R}^{k}:\|\mathbf{v}\|_{2}=1\\}$ and
$\mathcal{N}_{2}$ be the $1/8$-net of
$\mathbb{S}^{k_{m}-1}=\\{\mathbf{v}\in\mathbb{R}^{k_{m}}:\|\mathbf{v}\|_{2}=1\\}$.
Then, by Lemma I.4, we have

$\displaystyle\|\nabla_{{\mathbf{A}^{m}}}f(\mathbf{A}^{\star},\mathbf{B}^{\star})\|_{2}$
$\displaystyle=\sup_{\mathbf{u}\in\mathbb{S}^{k-1}}\sup_{\mathbf{d}\in\mathbb{S}^{k_{m}-1}}\left|\mathbf{u}^{\top}\nabla_{{\mathbf{A}^{m}}}f(\mathbf{A}^{\star},\mathbf{B}^{\star})\mathbf{d}\right|$
$\displaystyle\leq
2\max_{\mathbf{u}\in\mathcal{N}_{1}}\max_{\mathbf{d}\in\mathcal{N}_{2}}\left|\mathbf{u}^{\top}\nabla_{{\mathbf{A}^{m}}}f(\mathbf{A}^{\star},\mathbf{B}^{\star})\mathbf{d}\right|$

Define

$\displaystyle\mathbf{v}_{i}^{m,(n)}$
$\displaystyle=\widetilde{\mathbf{B}}_{i}^{\star}(\mathbf{I}_{p}\otimes\mathbf{A}^{m\star})\mathbf{y}^{m,(n)}$
$\displaystyle=\mathbf{A}^{m\star}\mathbf{y}_{i}^{m,(n)}-\mathbf{B}_{i}^{\star}(\mathbf{I}_{p-1}\otimes\mathbf{A}^{m\star})\mathbf{y}_{\backslash\\{i\\}}^{m,(n)}$
$\displaystyle=\widetilde{\mathbf{B}}_{i}^{\star}\left\\{{\mathbf{u}^{m}}^{(n)}+(\mathbf{I}_{p}\otimes{\mathbf{A}^{m\star}}){\mathbf{q}^{m}}^{(n)}\right\\}+\mathbf{r}_{i}^{(n)}+\mathbf{w}_{i}^{(n)},$
(D.15)

for $i\in V$, $m=1,\ldots,M$ and $n=1,\ldots,N$. Using (D.3), we can write

$\displaystyle\nabla_{{\mathbf{A}^{m}}}f(\mathbf{A}^{\star},\mathbf{B}^{\star})$
$\displaystyle=\sum_{j=1}^{p}(\mathbf{e}_{j}^{\top}\otimes\mathbf{I}_{k})\left\\{\sum_{i=1}^{p}\widetilde{\mathbf{B}}_{i}^{\star\top}\widetilde{\mathbf{B}}_{i}^{\star}(\mathbf{I}_{p}\otimes\mathbf{A}^{m\star})\widehat{\bm{\Sigma}}^{m}\right\\}(\mathbf{e}_{j}\otimes\mathbf{I}_{k_{m}})$
$\displaystyle=\sum_{j=1}^{p}(\mathbf{e}_{j}^{\top}\otimes\mathbf{I}_{k})\left[\sum_{i=1}^{p}\widetilde{\mathbf{B}}_{i}^{\star\top}\left\\{\frac{1}{N}\sum_{n=1}^{N}\mathbf{v}_{i}^{m,(n)}(\mathbf{y}^{m,(n)})^{\top}\right\\}\right](\mathbf{e}_{j}\otimes\mathbf{I}_{k_{m}}).$

Then, combining the above two results, we observe that for any
$\mathbf{u}\in\mathcal{N}_{1}$ and $\mathbf{d}\in\mathcal{N}_{2}$

$\mathbf{u}^{\top}\left[\sum_{j=1}^{p}(\mathbf{e}_{j}^{\top}\otimes\mathbf{I}_{k})\left\\{\sum_{i=1}^{p}\widetilde{\mathbf{B}}_{i}^{\star\top}\mathbf{v}_{i}^{m}(\mathbf{y}_{i}^{m})^{\top}\right\\}(\mathbf{e}_{j}\otimes\mathbf{I}_{k_{m}})\right]\mathbf{d},$

is a sub-exponential random variable. Therefore, we can obtain the upper bound
of Orlicz norm as

$\displaystyle\bigg{\|}\sum_{j=1}^{p}(\mathbf{e}_{j}^{\top}\otimes\mathbf{I}_{k})$
$\displaystyle\left\\{\sum_{i=1}^{p}\widetilde{\mathbf{B}}_{i}^{\star\top}\mathbf{v}_{i}^{m}(\mathbf{y}_{i}^{m})^{\top}\right\\}(\mathbf{e}_{j}\otimes\mathbf{I}_{k_{m}})\bigg{\|}_{\psi_{1}}$
$\displaystyle\leq\sum_{i=1}^{p}\bigg{\|}\sum_{j=1}^{p}(\mathbf{e}_{j}^{\top}\otimes\mathbf{I}_{k})\left\\{\widetilde{\mathbf{B}}_{i}^{\star\top}\mathbf{v}_{i}^{m}(\mathbf{y}_{i}^{m})^{\top}\right\\}(\mathbf{e}_{j}\otimes\mathbf{I}_{k_{m}})\bigg{\|}_{\psi_{1}}.$
Note that if $j\not\in\mathscr{N}_{i}^{\star}\cup\\{i\\}$, then
$(\mathbf{e}_{j}^{\top}\otimes\mathbf{I}_{k})\widetilde{\mathbf{B}}_{i}^{\star\top}={\bf
0}$. Therefore, the above display is equivalent as
$\displaystyle=\sum_{i=1}^{p}\bigg{\|}\sum_{j\in\mathscr{N}_{i}^{\star}\cup\\{i\\}}(\mathbf{e}_{j}^{\top}\otimes\mathbf{I}_{k})\left\\{\widetilde{\mathbf{B}}_{i}^{\star\top}\mathbf{v}_{i}^{m}(\mathbf{y}_{i}^{m})^{\top}\right\\}(\mathbf{e}_{j}\otimes\mathbf{I}_{k_{m}})\bigg{\|}_{\psi_{1}}.$
By Lemma 2.7.7 in (vershynin2018high), we can further bound the above display
as
$\displaystyle\leq\sum_{i=1}^{p}\sum_{j\in\mathscr{N}_{i}^{\star}\cup\\{i\\}}\bigg{\|}(\mathbf{e}_{j}^{\top}\otimes\mathbf{I}_{k})\widetilde{\mathbf{B}}_{i}^{\star\top}\mathbf{v}_{i}^{m}\bigg{\|}_{\psi_{2}}\bigg{\|}(\mathbf{y}_{i}^{m})^{\top}(\mathbf{e}_{j}\otimes\mathbf{I}_{k_{m}})\bigg{\|}_{\psi_{2}}.$
(D.16)

Using the fact that $|\mathscr{N}_{i}^{\star}\cup\\{i\\}|\leq s^{\star}+1$ and
the fact that

$\displaystyle\|\widetilde{\mathbf{B}}_{i}^{\star\top}\mathbf{v}_{i}^{m}\|_{\psi_{2}}$
$\displaystyle=\bigg{\|}\widetilde{\mathbf{B}}_{i}^{\star\top}\left\\{\widetilde{\mathbf{B}}_{i}^{\star}\left({\mathbf{u}^{m}}+(\mathbf{I}_{p}\otimes{\mathbf{A}^{m\star}}){\mathbf{q}^{m}}\right)+\mathbf{r}_{i}+\mathbf{w}_{i}\right\\}\bigg{\|}_{\psi_{2}}$
$\displaystyle\leq\|\widetilde{\mathbf{B}}_{i}^{\star\top}\widetilde{\mathbf{B}}_{i}^{\star}{\mathbf{u}^{m}}\|_{\psi_{2}}+\|\widetilde{\mathbf{B}}_{i}^{\star\top}(\mathbf{I}_{p}\otimes{\mathbf{A}^{m\star}}){\mathbf{q}^{m}}\|_{\psi_{2}}+\|\widetilde{\mathbf{B}}_{i}^{\star\top}\mathbf{r}_{i}\|_{\psi_{2}}+\|\widetilde{\mathbf{B}}_{i}^{\star\top}\mathbf{w}_{i}\|_{\psi_{2}}$
$\displaystyle\leq\|\widetilde{\mathbf{B}}_{i}^{\star}\|_{2}(\|\widetilde{\mathbf{B}}_{i}^{\star}\|_{2}\|\bm{\Sigma}^{m,\mathbf{u}}\|_{2}^{1/2}+\|\widetilde{\mathbf{B}}_{i}^{\star}\|_{2}\|\mathbf{A}^{m\star}\|_{2}\|\bm{\Sigma}^{m,\mathbf{q}}\|_{2}^{1/2}+\|\bm{\Sigma}_{i}^{\mathbf{r}}\|_{2}^{1/2}+\|\bm{\Sigma}_{i}^{\mathbf{w}}\|_{2}^{1/2}),$

for $i\in V$, we can further bound the right hand side of (D.16) as

$\displaystyle\bigg{\|}\sum_{j=1}^{p}(\mathbf{e}_{j}^{\top}\otimes\mathbf{I}_{k})$
$\displaystyle\left\\{\sum_{i=1}^{p}\widetilde{\mathbf{B}}_{i}^{\star\top}\mathbf{v}_{i}^{m}(\mathbf{y}_{i}^{m})^{\top}\right\\}(\mathbf{e}_{j}\otimes\mathbf{I}_{k_{m}})\bigg{\|}_{\psi_{1}}$
$\displaystyle\leq p(s^{\star}+1)\|\bm{\Sigma}^{m}\|_{2}^{1/2}\max_{i\in
V}\|\widetilde{\mathbf{B}}_{i}^{\star}\|_{2}(\|\widetilde{\mathbf{B}}_{i}^{\star}\|_{2}\|\bm{\Sigma}^{m,\mathbf{u}}\|_{2}^{1/2}+\|\widetilde{\mathbf{B}}_{i}^{\star}\|_{2}\|\mathbf{A}^{m\star}\|\|\bm{\Sigma}^{m,\mathbf{q}}\|_{2}^{1/2}$
$\displaystyle\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad+\|\bm{\Sigma}_{i}^{\mathbf{r}}\|_{2}^{1/2}+\|\bm{\Sigma}_{i}^{\mathbf{w}}\|_{2}^{1/2})$
$\displaystyle\leq
p(s^{\star}+1)\rho_{x}^{1/2}\rho_{b}^{1/2}\big{\\{}\rho_{b}^{1/2}\|\bm{\Sigma}^{m,\mathbf{u}}\|_{2}^{1/2}+(\rho_{b}\rho_{a})^{1/2}\|\bm{\Sigma}^{m,\mathbf{q}}\|_{2}^{1/2}$
$\displaystyle\quad\quad\quad\quad\quad\quad\quad\quad\quad+\max_{i\in
V}(\|\bm{\Sigma}_{i}^{\mathbf{r}}\|_{2}^{1/2}+\|\bm{\Sigma}_{i}^{\mathbf{w}}\|_{2}^{1/2})\big{\\}},$

where the last line follows by Assumption 6–7.

Next, let $C_{\epsilon}=C_{3}\max_{i\in
V}\rho_{x}^{1/2}\rho_{b}^{1/2}\big{\\{}\rho_{b}^{1/2}\|\bm{\Sigma}^{m,\mathbf{u}}\|_{2}^{1/2}+(\rho_{b}\rho_{a})^{1/2}\|\bm{\Sigma}^{m,\mathbf{q}}\|_{2}^{1/2}+\|\bm{\Sigma}_{i}^{\mathbf{r}}\|_{2}^{1/2}+\|\bm{\Sigma}_{i}^{\mathbf{w}}\|_{2}^{1/2}\big{\\}}$
for some constant $C_{3}>0$. Under the condition of the sample size
$N=O(C_{\epsilon}^{2}(k+k_{m}+\log M))$, apply Bernstein’s inequality (see
Theorem 2.8.1 invershynin2018high) and take the union bound over
$\mathcal{N}_{1}$ and $\mathcal{N}_{2}$, where
$\left|\mathcal{N}_{1}\right|\leq 17^{k}$ and
$\left|\mathcal{N}_{2}\right|\leq 17^{k_{m}}$, we can obtain

$\frac{1}{p(s^{\star}+1)}\|\nabla_{{\mathbf{A}^{m}}}f(\mathbf{A}^{\star},\mathbf{B}^{\star})\|_{2}\geq
C_{\epsilon}\sqrt{\frac{k_{m}+k+\log M}{N}},$

with probability smaller than $M^{-1}\exp\\{-(k_{m}+k)\\}$. ∎

###### Proof of Lemma D.4.

We first expand
$\nabla_{\mathbf{B}_{i}}f(\mathbf{A}^{\star},\mathbf{B}^{\star})$ and obtains

$\nabla_{\mathbf{B}_{i}}f(\mathbf{A}^{\star},\mathbf{B}^{\star})=-\frac{1}{N}\sum_{m=1}^{M}\sum_{n=1}^{N}\\{\mathbf{A}^{m\star}\mathbf{y}_{i}^{m,(n)}-\mathbf{B}_{i}^{\star}(\mathbf{I}_{p-1}\otimes{\mathbf{A}^{m\star}})\mathbf{y}_{\backslash\\{i\\}}^{m,(n)}\\}(\mathbf{y}_{\backslash\\{i\\}}^{m,(n)})^{\top}(\mathbf{I}_{p-1}\otimes{\mathbf{A}^{m\star\top}}).$

Replacing

$\mathbf{A}^{m\star}\mathbf{y}_{i}^{m,(n)}-\mathbf{B}_{i}^{\star}(\mathbf{I}_{p-1}\otimes{\mathbf{A}^{m\star}})\mathbf{y}_{\backslash\\{i\\}}^{m,(n)}=\mathbf{v}_{i}^{m,(n)},$

for $n=1,\ldots,N$ and $m=1,\ldots,M$ yields

$\nabla_{\mathbf{B}_{i}}f(\mathbf{A}^{\star},\mathbf{B}^{\star})=-\frac{1}{N}\sum_{m=1}^{M}\sum_{n=1}^{N}\mathbf{v}_{i}^{m,(n)}(\mathbf{y}_{\backslash\\{i\\}}^{m,(n)})^{\top}(\mathbf{I}_{p-1}\otimes{\mathbf{A}^{m\star\top}}).$

Define $\mathbf{t}^{m,(n)}_{i}\in\mathbb{R}^{k\times(p-1)}$ which transforms
the original matrix
$(\mathbf{y}_{\backslash\\{i\\}}^{m,(n)})^{\top}(\mathbf{I}_{p-1}\otimes{\mathbf{A}^{m\star\top}})\in\mathbb{R}^{1\times
k(p-1)}$ to

$\mathbf{t}^{m,(n)}_{i}=(\mathbf{A}^{m\star}\mathbf{y}_{1}^{m,(n)},\ldots,\mathbf{A}^{m\star}\mathbf{y}_{p}^{m,(n)})\in\mathbb{R}^{k\times(p-1)},$
(D.17)

for $m=1,\ldots,M$ and $n=1,\ldots,N$. Then, we can write

$\bigg{\|}\frac{1}{N}\sum_{m=1}^{M}\sum_{n=1}^{N}[\mathbf{v}_{i}^{m,(n)}(\mathbf{y}_{\backslash\\{i\\}}^{m,(n)})^{\top}(\mathbf{I}_{p-1}\otimes{\mathbf{A}^{m\star\top}})]_{\bar{\mathcal{S}}_{i}}\bigg{\|}_{r(k,\infty)}=\bigg{\|}\frac{1}{N}\sum_{m=1}^{M}\sum_{n=1}^{N}[\mathbf{v}_{i}^{m,(n)}\otimes\mathbf{t}^{m,(n)}_{i}]_{\bar{\mathcal{S}}_{i}^{\prime}}\bigg{\|}_{2,\infty},$

where we denote $\bar{\mathcal{S}}_{i}^{\prime}$ as the support set whose
elements are translated from $\bar{\mathcal{S}}_{i}$ due to the transformation
from a matrix of dimension $k\times k(p-1)$ to ${k^{2}\times(p-1)}$.

_Step 1_. Consider a fixed $\bar{{\mathcal{S}}}_{i}$and recall the definition
of the neighborhood set $\bar{\mathscr{N}}_{i}$ and the relation of
$\bar{\mathcal{S}}_{i}$ and $\bar{\mathscr{N}}_{i}$ defined in (D.2). Since
$|\bar{\mathscr{N}}_{i}|\leq(1+\vartheta_{1})s^{\star}$, we know that there
are at most $(1+\vartheta_{1})s^{\star}$ nonzero columns in
$\sum_{m=1}^{M}\sum_{n=1}^{N}[\mathbf{v}_{i}^{m,(n)}\otimes\mathbf{t}^{m,(n)}_{i}]_{\bar{\mathcal{S}}_{i}^{\prime}}$.
Similarly, for each column of
$\sum_{m=1}^{M}\sum_{n=1}^{N}[\mathbf{v}_{i}^{m,(n)}\otimes\mathbf{t}^{m,(n)}_{i}]_{\bar{\mathcal{S}}_{i}^{\prime}}$,
there are at most $\\{(1+\vartheta_{2})\alpha^{\star}k\\}^{2}$ nonzero
entries. Define the subset of the support set

$\displaystyle{\mathcal{S}}_{\cdot,i}^{\prime}$
$\displaystyle=\\{u:(u,i)\in{\mathcal{S}}^{\prime}\\};$
$\displaystyle{\mathcal{S}}_{\cdot,(i-1)k+1:ik}$
$\displaystyle=\\{(u,v):(u,v)\in{\mathcal{S}},v=(i-1)k+1,\ldots,ik\\}.$

Let

$\displaystyle\mathcal{U}({\mathcal{S}}^{\prime})$
$\displaystyle=\\{\mathbf{u}\in
R^{k^{2}}:\text{supp}{(\mathbf{u})}\subset\\{{\mathcal{S}}_{\cdot,i}^{\prime},i=1,\ldots,(p-1)\\},\|\mathbf{u}\|_{2}\leq
1\\};$ $\displaystyle\mathcal{D}({\mathcal{S}})$
$\displaystyle=\\{\mathbf{D}\in\mathbb{R}^{k\times
k}:\text{supp}(\mathbf{D})\subset\\{{\mathcal{S}}_{\cdot,(i-1)k+1:ik},i=1,\ldots,(p-1)\\},\|\mathbf{D}\|_{F}\leq
1\\}.$

Therefore, we can express the above equation as

$\displaystyle\bigg{\|}\frac{1}{N}\sum_{m=1}^{M}\sum_{n=1}^{N}[\mathbf{v}_{i}^{m,(n)}\otimes\mathbf{t}^{m,(n)}_{i}]_{\bar{\mathcal{S}}_{i}^{\prime}}\bigg{\|}_{2,\infty}$
$\displaystyle=\max_{j\in\bar{\mathscr{N}}_{i}}\sup_{\mathbf{u}\in\mathcal{U}(\bar{\mathcal{S}}^{\prime}_{i})}\left|\frac{1}{N}\sum_{m=1}^{M}\sum_{n=1}^{N}\mathbf{u}^{\top}[\mathbf{v}_{i}^{m,(n)}\otimes\mathbf{t}^{m,(n)}_{i}]_{\bar{\mathcal{S}}_{i}^{\prime}}\mathbf{e}_{j}\right|$
$\displaystyle\leq\max_{j\in\bar{\mathscr{N}}_{i}}\sup_{\mathbf{u}\in\mathcal{U}(\bar{\mathcal{S}}^{\prime}_{i})}\left|\frac{1}{N}\sum_{m=1}^{M}\sum_{n=1}^{N}\mathbf{u}^{\top}\mathbf{v}_{i}^{m,(n)}\otimes\mathbf{t}^{m,(n)}_{i}\mathbf{e}_{j}\right|$
(D.18)

where $\mathbf{e}_{j}\in\mathbb{R}^{p-1}$ denotes the $j$-th standard
canonical basis.

For matrices $\mathbf{E}$, $\mathbf{F}$, $\mathbf{G}$, $\mathbf{H}$, applying
the fact
$\mathop{\mathrm{tr}}(\mathbf{E}^{\top}\mathbf{F}\mathbf{G}\mathbf{H}^{\top})=\operatorname{vec}\left(\mathbf{E}\right)^{\top}(\mathbf{H}\otimes\mathbf{F})\operatorname{vec}\left(\mathbf{G}\right)$
to the right hand side of (D.5) we can obtain

$\displaystyle\max_{j\in\bar{\mathscr{N}}_{i}}\sup_{\mathbf{u}\in\mathcal{U}(\bar{\mathcal{S}}_{i}^{\prime})}\frac{1}{N}$
$\displaystyle\sum_{m=1}^{M}\sum_{n=1}^{N}\mathbf{u}^{\top}\mathbf{v}_{i}^{m,(n)}\otimes\mathbf{t}^{m,(n)}_{i}\mathbf{e}_{j}$
$\displaystyle=\max_{j\in\bar{\mathscr{N}}_{i}}\sup_{\mathbf{D}\in\mathcal{D}(\bar{\mathcal{S}}_{i})}\frac{1}{N}\sum_{m=1}^{M}\sum_{n=1}^{N}\mathop{\mathrm{tr}}\left\\{\mathbf{D}^{\top}\mathbf{t}^{m,(n)}_{i}\mathbf{e}_{j}\mathbf{v}_{i}^{m,(n)\top}\right\\}$
$\displaystyle=\max_{j\in\bar{\mathscr{N}}_{i}}\sup_{\mathbf{D}\in\mathcal{D}(\bar{\mathcal{S}}_{i})}\frac{1}{N}\sum_{m=1}^{M}\sum_{n=1}^{N}(\mathbf{D}\mathbf{v}_{i}^{m,(n)})^{\top}\mathbf{t}^{m,(n)}_{i}\mathbf{e}_{j}.$

Define $\mathcal{N}$ to be the $\frac{1}{2}$-net of the set
$\mathcal{D}(\bar{\mathcal{S}}_{i})$, we have

$\max_{j\in\bar{\mathscr{N}}_{i}}\sup_{\mathbf{D}\in\mathcal{D}}\frac{1}{N}\sum_{m=1}^{M}\sum_{n=1}^{N}(\mathbf{D}\mathbf{v}_{i}^{m,(n)})^{\top}\mathbf{t}^{m,(n)}_{i}\mathbf{e}_{j}\leq
2\max_{j\in\bar{\mathscr{N}}_{i}}\max_{\mathbf{D}\in\mathcal{N}}\frac{1}{N}\sum_{m=1}^{M}\sum_{n=1}^{N}(\mathbf{D}\mathbf{v}_{i}^{m,(n)})^{\top}\mathbf{t}^{m,(n)}_{i}\mathbf{e}_{j}.$

We consider the case that elements of
$\\{\\{\mathbf{y}^{m,(n)}\\}_{m=1}^{M}\\}_{n=1}^{N}$ are pairwise independent.
This implies that
$(\mathbf{D}\mathbf{v}_{i}^{m,(n)})^{\top}\mathbf{t}^{m,(n)}_{i}\mathbf{e}_{j}$
and
$(\mathbf{D}\mathbf{v}_{i}^{m^{\prime},(n^{\prime})})^{\top}\mathbf{y}^{m^{\prime},(n^{\prime})}_{i}\mathbf{e}_{j}$
are pairwise independent for every $n\neq n^{\prime}$. Given $n$ being fixed,
$(\mathbf{D}\mathbf{v}_{i}^{m,(n)})^{\top}\mathbf{t}^{m,(n)}_{i}\mathbf{e}_{j}$
and
$(\mathbf{D}\mathbf{v}_{i}^{m^{\prime},(n)})^{\top}\mathbf{y}^{m^{\prime},(n)}_{i}\mathbf{e}_{j}$
might not be independent for $m\neq m^{\prime}$. Observe that
$(\mathbf{D}\mathbf{v}_{i}^{m,(n)})^{\top}\mathbf{t}^{m,(n)}_{i}\mathbf{e}_{j}$
are sub-exponentially distributed. Under this setting, we can bound the Orlicz
norm $\|\cdot\|_{\psi_{1}}$ of the random variable
$M^{-1}\sum_{m=1}^{M}(\mathbf{D}\mathbf{v}_{i}^{m})^{\top}\mathbf{t}_{i}^{m}\mathbf{e}_{j}$
as the following. By writing $\mathbf{v}_{i}^{m}$ in terms of (D.15) and
$\mathbf{t}_{i}$ in terms of (D.17), we have

$\displaystyle\bigg{\|}\frac{1}{M}\sum_{m=1}^{M}$
$\displaystyle(\mathbf{D}\mathbf{v}_{i}^{m})^{\top}\mathbf{t}_{i}^{m}\mathbf{e}_{j}\bigg{\|}_{\psi_{1}}$
$\displaystyle\leq\max_{m=1,\ldots,M}\|\mathbf{A}^{m\star}\|_{2}\|\bm{\Sigma}^{m}\|_{2}^{1/2}\big{(}\|\widetilde{\mathbf{B}}_{i}^{\star}\|_{2}\|\bm{\Sigma}^{m,\mathbf{u}}\|_{2}^{1/2}+\|\widetilde{\mathbf{B}}_{i}^{\star}\|_{2}\|\mathbf{A}^{m\star}\|\|\bm{\Sigma}^{m,\mathbf{q}}\|_{2}^{1/2}$
$\displaystyle\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad+\|\bm{\Sigma}_{i}^{\mathbf{r}}\|_{2}^{1/2}+\|\bm{\Sigma}_{i}^{\mathbf{w}}\|_{2}^{1/2}\big{)}$
$\displaystyle\leq\max_{m=1,\ldots,M}\rho_{x}^{1/2}\rho_{a}^{1/2}\\{\rho_{b}^{1/2}\|\bm{\Sigma}^{m,\mathbf{u}}\|_{2}^{1/2}+(\rho_{b}\rho_{a})^{1/2}\|\bm{\Sigma}^{m,\mathbf{q}}\|_{2}^{1/2}+\|\bm{\Sigma}_{i}^{\mathbf{r}}\|_{2}^{1/2}+\|\bm{\Sigma}_{i}^{\mathbf{w}}\|_{2}^{1/2}\\},$

where we recall that $\|\mathbf{B}_{i}^{\star}\|\leq\rho_{b}^{1/2}$ for $i\in
V$, $\|\mathbf{A}^{m\star}\|\leq\rho_{a}^{1/2}$ and
$\|\bm{\Sigma}^{m}\|\leq\rho_{x}$ for $m=1,\ldots,M$.

_Step 2_. We define

$C_{\zeta}=(1+\vartheta_{2})C_{4}\max_{m=1,\ldots,M}\rho_{x}^{1/2}\rho_{a}^{1/2}\\{\rho_{b}^{1/2}\|\bm{\Sigma}^{m,\mathbf{u}}\|_{2}^{1/2}+(\rho_{b}\rho_{a})^{1/2}\|\bm{\Sigma}^{m,\mathbf{q}}\|_{2}^{1/2}+\|\bm{\Sigma}_{i}^{\mathbf{r}}\|_{2}^{1/2}+\|\bm{\Sigma}_{i}^{\mathbf{w}}\|_{2}^{1/2}\\},$

for some small constant $C_{4}>0$. Then, under the condition of the sample
size $N=O(C_{\zeta}^{2}\\{(\alpha^{\star}k)^{2}+\log p\\})$, apply the
Bernstein’s inequality with

$t=C_{\zeta}\sqrt{\frac{(\alpha^{\star}k)^{2}+\log p}{N}},$

and take the union bound over $j\in\bar{\mathscr{N}}_{i}$ with
$|\bar{\mathscr{N}}_{i}|\leq(1+\vartheta_{1})s^{\star}\leq p$ and
$\mathbf{D}\in\mathcal{N}$ with $|\mathcal{N}|\leq
5^{(1+\vartheta_{2})^{2}(\alpha^{\star})^{2}k^{2}}$, we obtain

$\displaystyle\mathbb{P}\bigg{\\{}\frac{1}{M}\bigg{\|}\frac{1}{N}\sum_{m=1}^{M}\sum_{n=1}^{N}$
$\displaystyle[\mathbf{v}_{i}^{m,(n)}\otimes\mathbf{t}^{m,(n)}_{i}]_{\bar{\mathcal{S}}_{i}^{\prime}}\bigg{\|}_{2,\infty}>t\bigg{\\}}$
$\displaystyle\leq\mathbb{P}\left\\{2\max_{j\in\bar{\mathscr{N}}_{i}}\max_{\mathbf{D}\in\mathcal{N}}\frac{1}{MN}\sum_{m=1}^{M}\sum_{n=1}^{N}(\mathbf{D}\mathbf{v}_{i}^{m,(n)})^{\top}\mathbf{t}^{m,(n)}_{i}\mathbf{e}_{j}>t\right\\}$
$\displaystyle\leq\sum_{j\in\bar{\mathscr{N}}_{i}}\sum_{\mathbf{D}\in\mathcal{N}}\mathbb{P}\left\\{2\frac{1}{MN}\sum_{m=1}^{M}\sum_{n=1}^{N}(\mathbf{D}\mathbf{v}_{i}^{m,(n)})^{\top}\mathbf{t}^{m,(n)}_{i}\mathbf{e}_{j}>t\right\\}$
$\displaystyle\leq p^{-1}\exp\\{-(\alpha^{\star}k)^{2}\\}.$ (D.19)

∎

###  D.6 Lemma D.6– D.9 and Their Proofs

In this section we introduce Lemma D.6 – D.9 in order. The proof is stated
following to the introduction of each lemma. We start with stating Lemma D.6.

######  Lemma D.6.

Let $\Upsilon_{1},\Upsilon_{2},\Upsilon_{3},\Upsilon_{4},\Upsilon_{6}$ be
constants defined in Section C. Under the conditions of Lemma D.1, we have

$\displaystyle\mathcal{I}_{1,m}$
$\displaystyle\geq\left(\frac{3p(s^{\star}+1)\Upsilon_{1}}{4\Upsilon_{2}}-\frac{ps^{\star}\Upsilon_{4}^{2}\Upsilon_{3}^{2}}{\Upsilon_{6}}\right)\|{\mathbf{A}^{m}}-\mathbf{A}^{m\star}\|_{F}^{2}-\frac{\Upsilon_{6}}{4}\sum_{i=1}^{p}\|\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}\|_{F}^{2}$
$\displaystyle\quad-\frac{2k\Upsilon_{2}}{p(s^{\star}+1)\Upsilon_{1}}\|\nabla_{{\mathbf{A}^{m}}}f(\mathbf{A}^{\star},\mathbf{B}^{\star})\|_{2}^{2}$
$\displaystyle\quad+\frac{1}{p(s^{\star}+1)\Upsilon_{2}}\|\nabla_{{\mathbf{A}^{m}}}f(\mathbf{A},\mathbf{B}^{\star})-\nabla_{{\mathbf{A}^{m}}}f(\mathbf{A}^{\star},\mathbf{B}^{\star})\|_{2}^{2},$

with probability at least $1-M^{-1}\exp\\{-k_{m}(s^{\star}+1)\\}$.

###### Proof of Lemma D.6.

Let $\mathscr{M}_{i}^{\star}=\mathscr{N}_{i}^{\star}\cup\\{i\\}$, where
$\mathscr{N}_{i}^{\star}$ is defined in (2.7), with
$\left|\mathscr{M}_{i}\right|\leq s^{\star}+1$ and let

$\displaystyle\mathcal{E}_{i}^{m}(\mathscr{M}_{i}^{\star})=\left\\{\frac{\nu_{x}}{2}\leq\sigma_{\min}(\widehat{\bm{\Sigma}}^{m}_{\mathscr{M}_{i}^{\star}\mathscr{M}_{i}^{\star}})\leq\sigma_{\max}(\widehat{\bm{\Sigma}}^{m}_{\mathscr{M}_{i}^{\star}\mathscr{M}_{i}^{\star}})\leq\frac{3\rho_{x}}{2}\right\\}.$
(D.20)

Under the conditions of the lemma, we have

$\mathbb{P}\left(\bigcap_{i=1}^{p}\mathcal{E}_{i}^{m}\right)\geq
1-M^{-1}\exp\\{-k_{m}(s^{\star}+1)\\},$

using Lemma I.2. We will work on the event

$\mathcal{E}^{m}=\bigcap_{i=1}^{p}\mathcal{E}_{i}^{m}.$ (D.21)

By definition of $\mathcal{I}_{1,m}$ we can write

$\displaystyle\mathcal{I}_{1,m}$
$\displaystyle=\langle{\nabla_{{\mathbf{A}^{m}}}f(\mathbf{A},\mathbf{B})},{{\mathbf{A}^{m}}-\mathbf{A}^{m\star}}\rangle$
$\displaystyle=\langle{\nabla_{{\mathbf{A}^{m}}}f(\mathbf{A},\mathbf{B})-\nabla_{{\mathbf{A}^{m}}}f(\mathbf{A},\mathbf{B}^{\star})},{{\mathbf{A}^{m}}-\mathbf{A}^{m\star}}\rangle$
$\displaystyle\quad+\langle{\nabla_{{\mathbf{A}^{m}}}f(\mathbf{A},\mathbf{B}^{\star})-\nabla_{{\mathbf{A}^{m}}}f(\mathbf{A}^{\star},\mathbf{B}^{\star})},{{\mathbf{A}^{m}}-\mathbf{A}^{m\star}}\rangle$
$\displaystyle\quad+\langle{\nabla_{{\mathbf{A}^{m}}}f(\mathbf{A}^{\star},\mathbf{B}^{\star})},{{\mathbf{A}^{m}}-\mathbf{A}^{m\star}}\rangle$
$\displaystyle=\mathcal{I}_{11,m}+\mathcal{I}_{12,m}+\mathcal{I}_{13,m}.$

We proceed to lower-bound the terms separately.

Using (D.2), for $\mathcal{I}_{11,m}$ we have

$\displaystyle\mathcal{I}_{11,m}$
$\displaystyle=\langle{\nabla_{{\mathbf{A}^{m}}}f(\mathbf{A},\mathbf{B})-\nabla_{{\mathbf{A}^{m}}}f(\mathbf{A},\mathbf{B}^{\star})},{{\mathbf{A}^{m}}-\mathbf{A}^{m\star}}\rangle$
$\displaystyle=\sum_{i=1}^{p}\langle{(\widetilde{\mathbf{B}}_{i}^{\top}\widetilde{\mathbf{B}}_{i}-\widetilde{\mathbf{B}}_{i}^{\star\top}\widetilde{\mathbf{B}}_{i}^{\star})(\mathbf{I}_{p}\otimes{\mathbf{A}^{m}})\widehat{\bm{\Sigma}}^{m}},{\mathbf{I}_{p}\otimes({\mathbf{A}^{m}}-\mathbf{A}^{m\star})}\rangle$
$\displaystyle=\sum_{i=1}^{p}\langle{\widetilde{\mathbf{B}}_{i}-\widetilde{\mathbf{B}}_{i}^{\star}},{\widetilde{\mathbf{B}}_{i}^{\star}\\{\mathbf{I}_{p}\otimes{({\mathbf{A}^{m}}-\mathbf{A}^{m\star})}\\}\widehat{\bm{\Sigma}}^{m}(\mathbf{I}_{p}\otimes{\mathbf{A}^{m\top}})}\rangle$
$\displaystyle\quad+\sum_{i=1}^{p}\langle{\widetilde{\mathbf{B}}_{i}-\widetilde{\mathbf{B}}_{i}^{\star}},{\widetilde{\mathbf{B}}_{i}(\mathbf{I}_{p}\otimes{{\mathbf{A}^{m}}})\widehat{\bm{\Sigma}}^{m}\\{\mathbf{I}_{p}\otimes{(\mathbf{A}^{m\top}-\mathbf{A}^{m\star\top})}\\}}\rangle.$
(D.22)

Let $\bar{{\mathcal{S}}}_{i,u\cdot}=\\{v:(u,v)\in\bar{{\mathcal{S}}}_{i}\\}$,
where $\bar{{\mathcal{S}}}_{i}$ is defined in (D.7). By definition, for each
$u=1,\ldots,k$,
$\left|\bar{{\mathcal{S}}}_{i,u\cdot}\right|\leq(1+\vartheta_{1})s^{\star}(1+\vartheta_{2})\alpha^{\star}k$.
For the first term in (D.22), we apply the fact that the $i$-th block matrix
$\mathbf{B}_{ii}=\mathbf{I}_{k}\in\mathbb{R}^{k\times k}$ in
$\widetilde{\mathbf{B}}_{i}$ and
$\mathbf{B}_{ii}^{\star}=\mathbf{I}_{k}\in\mathbb{R}^{k\times k}$ in
$\widetilde{\mathbf{B}}_{i}^{\star}$ are equivalent. Hence the $i$-th block
matrix $\widetilde{\mathbf{B}}_{i}-\widetilde{\mathbf{B}}_{i}^{\star}$ is a
zero matrix. Therefore, we can write

$\displaystyle\langle$
$\displaystyle{\widetilde{\mathbf{B}}_{i}-\widetilde{\mathbf{B}}_{i}^{\star}},{\widetilde{\mathbf{B}}_{i}^{\star}\\{\mathbf{I}_{p}\otimes{({\mathbf{A}^{m}}-\mathbf{A}^{m\star})}\\}\widehat{\bm{\Sigma}}^{m}(\mathbf{I}_{p}\otimes{\mathbf{A}^{m\top}})}\rangle$
$\displaystyle=\left\langle{-[\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}]_{\bar{\mathcal{S}}_{i}}},{[\widetilde{\mathbf{B}}_{i}^{\star}\\{\mathbf{I}_{p}\otimes{({\mathbf{A}^{m}}-\mathbf{A}^{m\star})}\\}\widehat{\bm{\Sigma}}^{m}_{\cdot\backslash\\{i\\}}(\mathbf{I}_{p-1}\otimes{\mathbf{A}^{m\top}})]_{\bar{\mathcal{S}}_{i}}}\right\rangle$
$\displaystyle\leq\left\|\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}\right\|_{F}\left\|[\widetilde{\mathbf{B}}_{i}^{\star}\\{\mathbf{I}_{p}\otimes{({\mathbf{A}^{m}}-\mathbf{A}^{m\star})}\\}\widehat{\bm{\Sigma}}^{m}_{\cdot\backslash\\{i\\}}(\mathbf{I}_{p-1}\otimes{\mathbf{A}^{m\top}})]_{\bar{\mathcal{S}}_{i}}\right\|_{F}$
$\displaystyle(\text{by Cauchy-Schwarz}).$

Furthermore, we have

$\displaystyle\left\|[\widetilde{\mathbf{B}}_{i}^{\star}\\{\mathbf{I}_{p}\otimes{({\mathbf{A}^{m}}-\mathbf{A}^{m\star})}\\}\widehat{\bm{\Sigma}}^{m}_{\cdot\backslash\\{i\\}}(\mathbf{I}_{p-1}\otimes{\mathbf{A}^{m\top}})]_{\bar{\mathcal{S}}_{i}}\right\|_{F}^{2}$
$\displaystyle=\sum_{(u,v)\in\bar{\mathcal{S}}_{i}}\left|(\widetilde{\mathbf{B}}_{i}^{\star}\\{\mathbf{I}_{p}\otimes{({\mathbf{A}^{m}}-\mathbf{A}^{m\star})}\\}\widehat{\bm{\Sigma}}^{m}_{\cdot\backslash\\{i\\}}(\mathbf{I}_{p-1}\otimes{\mathbf{A}^{m\top}}))_{u,v}\right|^{2}.$
$\displaystyle\leq\sum_{(u,v)\in\bar{\mathcal{S}}_{i}}\left\|\left(\widetilde{\mathbf{B}}_{i}^{\star}\\{\mathbf{I}_{p}\otimes{({\mathbf{A}^{m}}-\mathbf{A}^{m\star})}\\}\widehat{\bm{\Sigma}}^{m}_{\cdot\backslash\\{i\\}}\right)_{u,\cdot}\right\|_{2}^{2}\left\|(\mathbf{I}_{p-1}\otimes{\mathbf{A}^{m\top}})_{\cdot,v}\right\|_{2}^{2}$
$\displaystyle\leq\max_{v\in[k]}\left\|({\mathbf{A}^{m}})_{v,\cdot}\right\|_{2}^{2}\sum_{u\in[k]}\sum_{v\in\bar{\mathcal{S}}_{i,u\cdot}}\left\|(\widetilde{\mathbf{B}}_{i}^{\star}\\{\mathbf{I}_{p}\otimes{({\mathbf{A}^{m}}-\mathbf{A}^{m\star})}\\}\widehat{\bm{\Sigma}}^{m}_{\cdot\backslash\\{i\\}})_{u,\cdot}\right\|^{2}_{2}.$
Since ${\mathbf{A}^{m}}\in\mathcal{K}_{m}(\tau_{1},\tau_{2})$, defined in
(3.8), by the projection operator $\mathcal{P}_{m,\tau}$ in Algorithm 1, we
have
$\max_{v\in[k]}\|({\mathbf{A}^{m}})_{v,\cdot}\|_{2}^{2}\leq\frac{\tau_{2}}{k_{m}}\|\mathbf{A}^{m(0)}\|^{2}_{2}$.
Furthermore, using the fact that
$|\bar{\mathcal{S}}_{i,u\cdot}|\leq(1+\vartheta_{1})(1+\vartheta_{2})s^{\star}\alpha^{\star}k$,
the above display can be bounded as
$\displaystyle\leq\frac{\tau_{2}}{k_{m}}\left\|\mathbf{A}^{m(0)}\right\|^{2}_{2}(1+\vartheta_{1})(1+\vartheta_{2})s^{\star}\alpha^{\star}k\left\|\widetilde{\mathbf{B}}_{i}^{\star}\\{\mathbf{I}_{p}\otimes{({\mathbf{A}^{m}}-\mathbf{A}^{m\star})}\\}\widehat{\bm{\Sigma}}^{m}_{\cdot\backslash\\{i\\}}\right\|_{F}^{2}$
$\displaystyle\leq(1+\vartheta_{1})(1+\vartheta_{2})s^{\star}\alpha^{\star}{\tau_{2}}\left\|\mathbf{A}^{m(0)}\right\|_{2}^{2}\left\|\widetilde{\mathbf{B}}_{i}^{\star}\right\|_{F}^{2}\left\|{\mathbf{A}^{m}}-\mathbf{A}^{m\star}\right\|_{F}^{2}\left\|\widehat{\bm{\Sigma}}^{m}_{\cdot\backslash\\{i\\}}\right\|_{2}^{2}$
$\displaystyle(k_{m}\geq k)$
$\displaystyle\leq(1+\vartheta_{1})(1+\vartheta_{2})s^{\star}\alpha^{\star}{\tau_{2}}\left\|\mathbf{A}^{m(0)}\right\|_{2}^{2}\left\|\widetilde{\mathbf{B}}_{i}^{\star}\right\|_{F}^{2}\left\|{\mathbf{A}^{m}}-\mathbf{A}^{m\star}\right\|_{F}^{2}\left\|\widehat{\bm{\Sigma}}^{m}\right\|_{2}^{2}$
$\displaystyle(\|\widehat{\bm{\Sigma}}^{m}_{\cdot\backslash\\{i\\}}\|_{2}\leq\|\widehat{\bm{\Sigma}}^{m}\|_{2}).$

Combining the last two results, we can bound the first term in (D.22) as

$\displaystyle\|[\widetilde{\mathbf{B}}_{i}^{\star}$
$\displaystyle\\{\mathbf{I}_{p}\otimes{({\mathbf{A}^{m}}-\mathbf{A}^{m\star})}\\}\widehat{\bm{\Sigma}}^{m}_{\cdot\backslash\\{i\\}}(\mathbf{I}_{p-1}\otimes{\mathbf{A}^{m\top}})]_{\bar{\mathcal{S}}_{i}}\|_{F}\left\|\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}\right\|_{F}$
$\displaystyle\leq\sqrt{(1+\vartheta_{1})(1+\vartheta_{2})s^{\star}\alpha^{\star}\tau_{2}}\left\|\widehat{\bm{\Sigma}}^{m}\right\|_{2}\left\|\mathbf{A}^{m(0)}\right\|_{2}\left\|\widetilde{\mathbf{B}}_{i}^{\star}\right\|_{F}\|{\mathbf{A}^{m}}-\mathbf{A}^{m\star}\|_{F}\|\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}\|_{F}.$
(D.23)

For the second term in (D.22), we have

$\displaystyle\left\langle{\widetilde{\mathbf{B}}_{i}-\widetilde{\mathbf{B}}_{i}^{\star}},{\widetilde{\mathbf{B}}_{i}(\mathbf{I}_{p}\otimes{{\mathbf{A}^{m}}})\widehat{\bm{\Sigma}}^{m}\\{\mathbf{I}_{p}\otimes{(\mathbf{A}^{m\top}-\mathbf{A}^{m\star\top})}\\}}\right\rangle$
$\displaystyle=-\left\langle{[\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}]_{\bar{{\mathcal{S}}}_{i}}},{\widetilde{\mathbf{B}}_{i}(\mathbf{I}_{p}\otimes{{\mathbf{A}^{m}}})\widehat{\bm{\Sigma}}^{m}_{\cdot\backslash\\{i\\}}\\{\mathbf{I}_{p-1}\otimes{(\mathbf{A}^{m\top}-\mathbf{A}^{m\star\top})}\\}}\right\rangle$
$\displaystyle(\widetilde{\mathbf{B}}_{ii}=\widetilde{\mathbf{B}}_{ii}^{\star}=\mathbf{I}_{k})$
$\displaystyle\leq\left\|\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}\right\|_{F}\left\|[\widetilde{\mathbf{B}}_{i}(\mathbf{I}_{p}\otimes{{\mathbf{A}^{m}}})\widehat{\bm{\Sigma}}^{m}_{\cdot\backslash\\{i\\}}\\{\mathbf{I}_{p-1}\otimes{(\mathbf{A}^{m\top}-\mathbf{A}^{m\star\top})}\\}]_{\bar{{\mathcal{S}}}_{i}}\right\|_{F}$
$\displaystyle(\text{by Cauchy-Schwarz}).$

Let $\bar{{\mathcal{S}}}_{i,\cdot v}=\\{u:(u,v)\in\bar{{\mathcal{S}}}_{i}\\}$.
Note that if $(u,v)\in\bar{\mathcal{S}}_{i}$, then
$\lceil{v/k}\rceil\in\bar{\mathscr{N}}_{i}$. Let the index set
$\backslash\\{i\\}=\\{1,\ldots,p\\}\backslash\\{i\\}$, we have

$\displaystyle\left\|[\widetilde{\mathbf{B}}_{i}(\mathbf{I}_{p}\otimes{{\mathbf{A}^{m}}})\widehat{\bm{\Sigma}}^{m}_{\cdot\backslash\\{i\\}}\\{\mathbf{I}_{p-1}\otimes{(\mathbf{A}^{m\top}-\mathbf{A}^{m\star\top})}\\}]_{\bar{{\mathcal{S}}}_{i}}\right\|_{F}^{2}$
$\displaystyle=\sum_{(u,v)\in\bar{{\mathcal{S}}}_{i}}\left|(\widetilde{\mathbf{B}}_{i}(\mathbf{I}_{p}\otimes{{\mathbf{A}^{m}}})\widehat{\bm{\Sigma}}^{m}_{\cdot\bar{\mathscr{N}}_{i}}\\{\mathbf{I}_{|\bar{\mathscr{N}}_{i}|}\otimes{(\mathbf{A}^{m\top}-\mathbf{A}^{m\star\top})}\\})_{u,v}\right|^{2}$
$\displaystyle\leq\sum_{(u,v)\in\bar{{\mathcal{S}}}_{i}}\|(\widetilde{\mathbf{B}}_{i}(\mathbf{I}_{p}\otimes{{\mathbf{A}^{m}}}))_{u\cdot}\|_{2}^{2}\|(\widehat{\bm{\Sigma}}^{m}_{\cdot\bar{\mathscr{N}}_{i}}\\{\mathbf{I}_{|\bar{\mathscr{N}}_{i}|}\otimes{(\mathbf{A}^{m\top}-\mathbf{A}^{m\star\top})}\\})_{\cdot,v}\|_{2}^{2}$
$\displaystyle\leq\|(\mathbf{I}_{p}\otimes{{\mathbf{A}^{m}}^{\top}})\widetilde{\mathbf{B}}_{i}^{\top}\|_{2,\infty}^{2}\sum_{v\in[k(p-1)]}\sum_{u\in\bar{{\mathcal{S}}}_{i,\cdot
v}}\|(\widehat{\bm{\Sigma}}^{m}_{\cdot\bar{\mathscr{N}}_{i}}\\{\mathbf{I}_{|\bar{\mathscr{N}}_{i}|}\otimes{(\mathbf{A}^{m\top}-\mathbf{A}^{m\star\top})}\\})_{\cdot,v}\|_{2}^{2}$
$\displaystyle\leq(1+\vartheta_{2})\alpha^{\star}k\|((\mathbf{I}_{p}\otimes{\mathbf{A}^{m\top}})\widetilde{\mathbf{B}}_{i}^{\top}\|_{2,\infty}^{2}\|\widehat{\bm{\Sigma}}^{m}_{\cdot\bar{\mathscr{N}}_{i}}\\{\mathbf{I}_{|\bar{\mathscr{N}}_{i}|}\otimes{(\mathbf{A}^{m\top}-\mathbf{A}^{m\star\top})}\\}\|_{F}^{2}.$
By Lemma F.9 in na2021estimating, for any two matrices $\mathbf{X}$,
$\mathbf{Y}$, we have
$\|\mathbf{X}\mathbf{Y}\|_{2,\infty}\leq\|\mathbf{X}\|_{2,\infty}\|\mathbf{Y}\|_{1}$,
where $\|\mathbf{Y}\|_{1}$ denotes the maximum $\ell_{1}$-norm of the column
of $\mathbf{Y}$. Then, the above display is abounded as
$\displaystyle\leq(1+\vartheta_{2})\alpha^{\star}k\|(\mathbf{I}_{p}\otimes{\mathbf{A}^{m\top}})\|_{2,\infty}^{2}\|\widetilde{\mathbf{B}}_{i}^{\top}\|_{1}^{2}\|\widehat{\bm{\Sigma}}^{m}_{\cdot\bar{\mathscr{N}}_{i}}\\{\mathbf{I}_{|\bar{\mathscr{N}}_{i}|}\otimes{(\mathbf{A}^{m\top}-\mathbf{A}^{m\star\top})}\\}\|_{F}^{2}$
$\displaystyle=(1+\vartheta_{2})\alpha^{\star}k\|\mathbf{A}^{m\top}\|_{2,\infty}^{2}\|\widetilde{\mathbf{B}}_{i}^{\top}\|_{1}^{2}\|\widehat{\bm{\Sigma}}^{m}_{\cdot\bar{\mathscr{N}}_{i}}\\{\mathbf{I}_{|\bar{\mathscr{N}}_{i}|}\otimes{(\mathbf{A}^{m\top}-\mathbf{A}^{m\star\top})}\\}\|_{F}^{2}.$
Apply the condition of $\mathcal{K}_{m}(\tau_{1},\tau_{2})$, we can bound the
above display as
$\displaystyle\leq(1+\vartheta_{2})\alpha^{\star}\tau_{2}\|\mathbf{A}^{m(0)}\|_{2}^{2}\|\widetilde{\mathbf{B}}_{i}^{\top}\|_{1}^{2}\|\widehat{\bm{\Sigma}}^{m}_{\cdot\bar{\mathscr{N}}_{i}}\\{\mathbf{I}_{|\bar{\mathscr{N}}_{i}|}\otimes{(\mathbf{A}^{m\top}-\mathbf{A}^{m\star\top})}\\}\|_{F}^{2}.$
Since $|\bar{\mathscr{N}}_{i}|\leq(1+\vartheta_{1})s^{\star}$, and hence
$\|\\{\mathbf{I}_{\left|\bar{\mathscr{N}}_{i}\right|}\otimes{(\mathbf{A}^{m\top}-\mathbf{A}^{m\star\top})}\\}\|_{F}\leq\sqrt{(1+\vartheta_{1})s^{\star}}\|\mathbf{A}^{m\top}-\mathbf{A}^{m\star\top}\|_{F}$.
Along with Cauchy interlacing theorem, we can bound the above display as
$\displaystyle\leq(1+\vartheta_{1})(1+\vartheta_{2})s^{\star}\alpha^{\star}\tau_{2}\|\mathbf{A}^{m(0)}\|_{2}^{2}\|\widetilde{\mathbf{B}}_{i}^{\top}\|_{1}^{2}\|{\mathbf{A}^{m}}-\mathbf{A}^{m\star}\|_{F}^{2}\|\widehat{\bm{\Sigma}}^{m}\|_{2}^{2}.$
Finally, under assumption of Lemma D.1, we have
$\|\widetilde{\mathbf{B}}_{i}^{\top}-\widetilde{\mathbf{B}}_{i}^{\star\top}\|_{1}=\|\mathbf{B}_{i}^{\top}-\mathbf{B}_{i}^{\star\top}\|_{1}\leq
C_{B}\|\mathbf{B}_{i}^{\star\top}\|_{1}\leq
C_{B}\|\widetilde{\mathbf{B}}_{i}^{\star\top}\|_{1}$. Therefore, apply
triangle inequality, we can further obtain the bound
$\displaystyle\leq(1+\vartheta_{1})(1+\vartheta_{2})(1+C_{B})^{2}s^{\star}\alpha^{\star}\tau_{2}\|\mathbf{A}^{m(0)}\|_{2}^{2}\|\widetilde{\mathbf{B}}_{i}^{\star\top}\|_{1}^{2}\|{\mathbf{A}^{m}}-\mathbf{A}^{m\star}\|_{F}^{2}\|\widehat{\bm{\Sigma}}^{m}\|_{2}^{2},$
(D.24)

Taking the results of (D.6)–(D.24) and plugging back to (D.22) , we can bound
$\mathcal{I}_{11,m}$ with Young’s inequality and obtains

$\displaystyle\mathcal{I}_{11,m}$
$\displaystyle\geq-\Upsilon_{4}\Upsilon_{3}\sqrt{s^{\star}}\sum_{i=1}^{p}\|{\mathbf{A}^{m}}-\mathbf{A}^{m\star}\|_{F}\|\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}\|_{F}$
$\displaystyle\geq-\Upsilon_{4}\Upsilon_{3}\sqrt{s^{\star}}\sum_{i=1}^{p}\left(\frac{1}{2C_{12}}\|\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}\|_{F}^{2}+\frac{C_{12}}{2}\|{\mathbf{A}^{m}}-\mathbf{A}^{m\star}\|_{F}^{2}\right),$

where we have

$\displaystyle\Upsilon_{3}$
$\displaystyle=\|\widehat{\bm{\Sigma}}^{m}\|_{2}(C_{B}+1)\max_{m=1,\ldots,M}\|\mathbf{A}^{m(0)}\|_{2}\max_{i\in
V}(\|\mathbf{B}_{i}^{\star}\|_{F}\vee\|\widetilde{\mathbf{B}}_{i}^{\star\top}\|_{1});$
$\displaystyle\Upsilon_{4}$
$\displaystyle=2\sqrt{(1+\vartheta_{1})(1+\vartheta_{2})\tau_{2}\alpha^{\star}},$

and $C_{12}$ is a constant defined later.

Under the event of ${\mathcal{E}^{m}}$ defined in (D.21), by Lemma G.3, we
know that $f(\mathbf{A},\mathbf{B}^{\star})$ is $\mu$-strongly convex and
$L$-smooth with respect to ${\mathbf{A}^{m}}$ with probability at least
$1-M^{-1}\exp\\{-k_{m}(s^{\star}+1)\\}$, where

$\mu=\frac{p(s^{\star}+1)\nu_{x}\nu_{b}}{4},\quad
L=\frac{3p(s^{\star}+1)\rho_{x}\rho_{p}}{4}.$

Define

$\displaystyle\Upsilon_{1}$
$\displaystyle=\frac{3\nu_{x}\nu_{b}\rho_{x}\rho_{b}}{16},\quad\Upsilon_{2}=\frac{\nu_{x}\nu_{b}+3\rho_{x}\rho_{b}}{4}.$

Therefore, by Lemma I.3, we have

$\displaystyle\mathcal{I}_{12,m}$
$\displaystyle=\langle{\nabla_{{\mathbf{A}^{m}}}f(\mathbf{A},\mathbf{B}^{\star})-\nabla_{{\mathbf{A}^{m}}}f(\mathbf{A}^{\star},\mathbf{B}^{\star})},{{\mathbf{A}^{m}}-\mathbf{A}^{m\star}}\rangle$
$\displaystyle\geq\frac{p(s^{\star}+1)\Upsilon_{1}}{\Upsilon_{2}}\|{\mathbf{A}^{m}}-\mathbf{A}^{m\star}\|_{F}^{2}$
$\displaystyle\quad+\frac{1}{p(s^{\star}+1)\Upsilon_{2}}\|\nabla_{{\mathbf{A}^{m}}}f(\mathbf{A},\mathbf{B}^{\star})-\nabla_{{\mathbf{A}^{m}}}f(\mathbf{A}^{\star},\mathbf{B}^{\star})\|_{F}^{2},$

with probability at least $1-M^{-1}\exp\\{-k_{m}(s^{\star}+1)\\}$, the
probability that ${\mathcal{E}^{m}}$ happens.

Define $\|\cdot\|_{*}$ to be the nuclear norm. In the last step, we apply
Hölder’s inequality and obtain,

$\displaystyle\mathcal{I}_{13,m}$
$\displaystyle=\langle{\nabla_{{\mathbf{A}^{m}}}f(\mathbf{A}^{\star},\mathbf{B}^{\star})},{{\mathbf{A}^{m}}-\mathbf{A}^{m\star}}\rangle$
$\displaystyle\geq-\|\nabla_{{\mathbf{A}^{m}}}f(\mathbf{A}^{\star},\mathbf{B}^{\star})\|_{2}\|{\mathbf{A}^{m}}-\mathbf{A}^{m\star}\|_{*}$
$\displaystyle\geq-\sqrt{2k}\|\nabla_{{\mathbf{A}^{m}}}f(\mathbf{A}^{\star},\mathbf{B}^{\star})\|_{2}\|{\mathbf{A}^{m}}-\mathbf{A}^{m\star}\|_{F}$
$\displaystyle\geq-\sqrt{2k}\left\\{\frac{1}{2C_{13}}\|\nabla_{{\mathbf{A}^{m}}}f(\mathbf{A}^{\star},\mathbf{B}^{\star})\|_{2}^{2}+\frac{C_{13}}{2}\|{\mathbf{A}^{m}}-\mathbf{A}^{m\star}\|_{F}^{2}\right\\},$

and the second last step follows by the fact
$\|\mathbf{Z}\|_{*}\leq\sqrt{r}\|\mathbf{Z}\|_{F}$, where $r$ is the rank of
$\mathbf{Z}$. Since $k\leq k_{m}$ for all $m=1,\ldots,M$ and hence the rank of
${\mathbf{A}^{m}}-\mathbf{A}^{m\star}$ is at most $2k$. $C_{13}>0$ will be
defined below.

Setting $C_{12}$ and $C_{13}$ as

$C_{12}=\frac{2\Upsilon_{4}\Upsilon_{3}\sqrt{s^{\star}}}{\Upsilon_{6}},\quad
C_{13}=\frac{1}{2\sqrt{2k}}\frac{p(s^{\star}+1)\Upsilon_{1}}{\Upsilon_{2}},$

where $\Upsilon_{6}=\frac{\nu_{x}\nu_{a}}{2}$.

Combining results of $\mathcal{I}_{11,m}$, $\mathcal{I}_{12,m}$, and
$\mathcal{I}_{13,m}$, we can obtain that

$\displaystyle\mathcal{I}_{1,m}$
$\displaystyle\geq\left(\frac{3p(s^{\star}+1)\Upsilon_{1}}{4\Upsilon_{2}}-\frac{ps^{\star}\Upsilon_{4}^{2}\Upsilon_{3}^{2}}{\Upsilon_{6}}\right)\|{\mathbf{A}^{m}}-\mathbf{A}^{m\star}\|_{F}^{2}-\frac{\Upsilon_{6}}{4}\sum_{i=1}^{p}\|\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}\|_{F}^{2}$
$\displaystyle\quad-\frac{2k\Upsilon_{2}}{p(s^{\star}+1)\Upsilon_{1}}\|\nabla_{{\mathbf{A}^{m}}}f(\mathbf{A}^{\star},\mathbf{B}^{\star})\|_{2}^{2}$
$\displaystyle\quad+\frac{1}{p(s^{\star}+1)\Upsilon_{2}}\|\nabla_{{\mathbf{A}^{m}}}f(\mathbf{A},\mathbf{B}^{\star})-\nabla_{{\mathbf{A}^{m}}}f(\mathbf{A}^{\star},\mathbf{B}^{\star})\|_{F}^{2},$

with probability at least $1-M^{-1}\exp\\{-k_{m}(s^{\star}+1)\\}$. ∎

######  Lemma D.7.

Let $\Upsilon_{5}$ be a constant defined in Section C. Under conditions of
Lemma D.1, we have

$\displaystyle\mathcal{I}_{2,m}$ $\displaystyle\leq
3\bigg{\\{}\|\nabla_{{\mathbf{A}^{m}}}f(\mathbf{A},\mathbf{B}^{\star})-\nabla_{{\mathbf{A}^{m}}}f(\mathbf{A}^{\star},\mathbf{B}^{\star})\|_{F}^{2}$
$\displaystyle\quad+p(s^{\star}+1)\Upsilon_{5}\sum_{i=1}^{p}\|\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}\|_{F}^{2}+k\|\nabla_{{\mathbf{A}^{m}}}f(\mathbf{A}^{\star},\mathbf{B}^{\star})\|_{2}^{2}\bigg{\\}}.$

###### Proof of Lemma D.7.

By definition of $\mathcal{I}_{2,m}$, we can write

$\displaystyle\mathcal{I}_{2,m}$
$\displaystyle=\|\nabla_{{\mathbf{A}^{m}}}f(\mathbf{A},\mathbf{B})\|_{F}^{2}$
$\displaystyle\leq
3\bigg{\\{}\|\nabla_{{\mathbf{A}^{m}}}f(\mathbf{A},\mathbf{B})-\nabla_{{\mathbf{A}^{m}}}f(\\{\mathbf{A}^{m\star}\\}_{m=1}^{M}\cup\mathcal{A}^{\backslash
m\star},\mathbf{B}^{\star})\|_{F}^{2}$
$\displaystyle\quad\quad+\|\nabla_{{\mathbf{A}^{m}}}f(\\{\mathbf{A}^{m\star}\\}_{m=1}^{M}\cup\mathcal{A}^{\backslash
m\star},\mathbf{B}^{\star})-\nabla_{{\mathbf{A}^{m}}}f(\mathbf{A}^{\star},\mathbf{B}^{\star})\|_{F}^{2}$
$\displaystyle\quad\quad+\|\nabla_{{\mathbf{A}^{m}}}f(\mathbf{A}^{\star},\mathbf{B}^{\star})\|_{F}^{2}\bigg{\\}}.$

By (D.3) and triangle inequality, we can first decompose $\mathcal{I}_{21,m}$
as

$\displaystyle\mathcal{I}_{21,m}$
$\displaystyle=\|\nabla_{{\mathbf{A}^{m}}}f(\mathbf{A},\mathbf{B})-\nabla_{{\mathbf{A}^{m}}}f(\\{\mathbf{A}^{m\star}\\}_{m=1}^{M}\cup\mathcal{A}^{\backslash
m\star},\mathbf{B}^{\star})\|_{F}$
$\displaystyle=\left\|\sum_{i=1}^{p}\sum_{j=1}^{p}(\mathbf{e}_{j}^{\top}\otimes\mathbf{I}_{k})\\{\widetilde{\mathbf{B}}_{i}^{\top}(\widetilde{\mathbf{B}}_{i}-\widetilde{\mathbf{B}}_{i}^{\star})+(\widetilde{\mathbf{B}}_{i}^{\top}-\widetilde{\mathbf{B}}_{i}^{\star\top})\widetilde{\mathbf{B}}_{i}^{\star}\\}(\mathbf{I}_{p}\otimes{{\mathbf{A}^{m}}})\widehat{\bm{\Sigma}}^{m}(\mathbf{e}_{j}\otimes\mathbf{I}_{k_{m}})\right\|_{F}.$
Since
$(\mathbf{e}_{j}^{\top}\otimes\mathbf{I}_{k})\widetilde{\mathbf{B}}_{i}^{\top}={\bf
0}$ and
$(\mathbf{e}_{j}^{\top}\otimes\mathbf{I}_{k})(\widetilde{\mathbf{B}}_{i}^{\top}-\widetilde{\mathbf{B}}_{i}^{\star\top})={\bf
0}$ for $j\not\in\bar{\mathscr{N}}_{i}\backslash\\{i\\}$, we can write the
above display as
$\displaystyle=\left\|\sum_{i=1}^{p}\sum_{j\in\bar{\mathscr{N}}_{i}\cup\\{i\\}}(\mathbf{e}_{j}^{\top}\otimes\mathbf{I}_{k})\\{\widetilde{\mathbf{B}}_{i}^{\top}(\widetilde{\mathbf{B}}_{i}-\widetilde{\mathbf{B}}_{i}^{\star})+(\widetilde{\mathbf{B}}_{i}^{\top}-\widetilde{\mathbf{B}}_{i}^{\star\top})\widetilde{\mathbf{B}}_{i}^{\star}\\}(\mathbf{I}_{p}\otimes{{\mathbf{A}^{m}}})\widehat{\bm{\Sigma}}^{m}(\mathbf{e}_{j}\otimes\mathbf{I}_{k_{m}})\right\|_{F}$
$\displaystyle\leq\sqrt{(1+\vartheta_{1})(s^{\star}+1)}\sum_{i=1}^{p}\|\\{\widetilde{\mathbf{B}}_{i}^{\top}(\widetilde{\mathbf{B}}_{i}-\widetilde{\mathbf{B}}_{i}^{\star})+(\widetilde{\mathbf{B}}_{i}^{\top}-\widetilde{\mathbf{B}}_{i}^{\star\top})\widetilde{\mathbf{B}}_{i}^{\star}\\}(\mathbf{I}_{p}\otimes{\mathbf{A}^{m}})\widehat{\bm{\Sigma}}^{m}\|_{F},$

where the last inequality follows by
$|\bar{\mathscr{N}}_{i}\cup\\{i\\}|\leq(1+\vartheta_{1})(s^{\star}+1)$. Now,
consider single $i\in\\{1,\ldots,p\\}$ and apply triangle inequality once
more, we have

$\displaystyle\mathcal{I}_{211,m,i}$
$\displaystyle=\|\\{\widetilde{\mathbf{B}}_{i}^{\top}(\widetilde{\mathbf{B}}_{i}-\widetilde{\mathbf{B}}_{i}^{\star})+(\widetilde{\mathbf{B}}_{i}^{\top}-\widetilde{\mathbf{B}}_{i}^{\star\top})\widetilde{\mathbf{B}}_{i}^{\star}\\}(\mathbf{I}_{p}\otimes{\mathbf{A}^{m}})\widehat{\bm{\Sigma}}^{m}\|_{F}$
$\displaystyle\leq(\|\widetilde{\mathbf{B}}_{i}\|_{2}+\|\widetilde{\mathbf{B}}_{i}^{\star}\|_{2})\|(\mathbf{I}_{p}\otimes{{\mathbf{A}^{m}}})\|_{2}\|\widehat{\bm{\Sigma}}^{m}\|_{2}\|\widetilde{\mathbf{B}}_{i}-\widetilde{\mathbf{B}}_{i}^{\star}\|_{F}.$
Using the fact that for a pair of matrices $\mathbf{X}$, $\mathbf{Y}$,
$\|\mathbf{X}\otimes\mathbf{Y}\|_{2}=\|\mathbf{X}\|_{2}\|\mathbf{Y}\|_{2}$,
the above display is equivalent as
$\displaystyle=(\|\widetilde{\mathbf{B}}_{i}\|_{2}+\|\widetilde{\mathbf{B}}_{i}^{\star}\|_{2})\|{\mathbf{A}^{m}}\|_{2}\|\widehat{\bm{\Sigma}}^{m}\|_{2}\|\widetilde{\mathbf{B}}_{i}-\widetilde{\mathbf{B}}_{i}^{\star}\|_{F}$
$\displaystyle\leq(1+C_{A})\|\mathbf{A}^{m\star}\|_{2}(\|\widetilde{\mathbf{B}}_{i}\|_{2}+\|\widetilde{\mathbf{B}}_{i}^{\star}\|_{2})\|\widehat{\bm{\Sigma}}^{m}\|_{2}\|\widetilde{\mathbf{B}}_{i}-\widetilde{\mathbf{B}}_{i}^{\star}\|_{F},$

where the last step follows by the assumption stated in Lemma D.1:
$\|{\mathbf{A}^{m}}-\mathbf{A}^{m\star}\|_{2}\leq
C_{A}\|\mathbf{A}^{m\star}\|_{2}$.

Note that, by triangle inequality and the definition of spectral norm , we can
write

$\displaystyle\|\widetilde{\mathbf{B}}_{i}\|_{2}\leq\|\widetilde{\mathbf{B}}_{i}-\widetilde{\mathbf{B}}_{i}^{\star}\|_{2}+\|\widetilde{\mathbf{B}}_{i}^{\star}\|_{2}$
$\displaystyle=\|\mathbf{B}_{i}-{\mathbf{B}}_{i}^{\star}\|_{2}+\|\widetilde{\mathbf{B}}_{i}\|_{2}$
$\displaystyle\leq
C_{B}\|\mathbf{B}_{i}^{\star}\|_{2}+\|\widetilde{\mathbf{B}}_{i}^{\star}\|_{2}\leq(C_{B}+1)\|\widetilde{\mathbf{B}}_{i}^{\star}\|_{2}.$
(D.25)

Plugging (D.25) back to $\mathcal{I}_{211,m,i}$ yields

$\displaystyle\mathcal{I}_{211,m,i}$
$\displaystyle\leq(1+C_{A})(2+C_{B})\|\widehat{\bm{\Sigma}}^{m}\|_{2}\|\widetilde{\mathbf{B}}_{i}^{\star}\|_{2}\|\mathbf{A}^{m\star}\|_{2}\|{\mathbf{B}}_{i}-{\mathbf{B}}_{i}^{\star}\|_{F},$
(D.26)

where it follows by the fact that
$\|\widetilde{\mathbf{B}}_{i}-\widetilde{\mathbf{B}}_{i}^{\star}\|_{F}=\|{\mathbf{B}}_{i}-{\mathbf{B}}_{i}^{\star}\|_{F}$.

Then, sum up $\mathcal{I}_{211,m,i}$ for $i\in V$, we have

$\displaystyle\mathcal{I}_{21,m}$
$\displaystyle\leq\Upsilon_{5}^{1/2}\sqrt{s^{\star}+1}\sum_{i=1}^{p}\|\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}\|_{F},$

where
$\Upsilon_{5}=(1+C_{A})^{2}(2+C_{B})^{2}\|\widehat{\bm{\Sigma}}^{m}\|_{2}^{2}\rho_{b}\rho_{a}$.

Then, applying Cauchy-Schwarz inequality yields

$\mathcal{I}_{21,m}^{2}\leq
p(s^{\star}+1)\Upsilon_{5}\sum_{i=1}^{p}\|\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}\|_{F}^{2}.$

Therefore, we can conclude that

$\displaystyle\mathcal{I}_{2,m}$ $\displaystyle\leq
3\bigg{\\{}\|\nabla_{{\mathbf{A}^{m}}}f(\mathbf{A},\mathbf{B}^{\star})-\nabla_{{\mathbf{A}^{m}}}f(\mathbf{A}^{\star},\mathbf{B}^{\star})\|_{F}^{2}$
$\displaystyle\quad+\Upsilon_{5}p(s^{\star}+1)\sum_{i=1}^{p}\|\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}\|_{F}^{2}+k\|\nabla_{{\mathbf{A}^{m}}}f(\mathbf{A}^{\star},\mathbf{B}^{\star})\|_{2}^{2}\bigg{\\}}.$

∎

######  Lemma D.8.

The constants $\Upsilon_{3},\Upsilon_{4},\Upsilon_{6}$ are defined in Section
C. Under the conditions of Lemma D.2, we have

$\mathcal{I}_{3,i}\geq\frac{M\Upsilon_{6}}{2}\|\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}\|_{F}^{2}-\frac{s^{\star}\Upsilon_{4}^{2}\Upsilon_{3}^{2}}{\Upsilon_{6}}\sum_{m=1}^{M}\|{\mathbf{A}^{m}}-\mathbf{A}^{m\star}\|_{F}^{2}\\\
-\frac{(1+\vartheta_{1})s^{\star}}{M\Upsilon_{6}}\|\nabla_{\mathbf{B}_{i}}f(\mathbf{A}^{\star},\mathbf{B}^{\star})\|_{r(k,\infty)}^{2}.$

with probability at least $1-p^{-1}\max_{m=1,\ldots,M}\exp(-k_{m}s^{\star})$.

###### Proof of Lemma D.8.

By definition of $\mathcal{I}_{3,i}$, we can write

$\displaystyle\mathcal{I}_{3,i}$
$\displaystyle=\langle{[\nabla_{\mathbf{B}_{i}}f(\mathbf{A},\mathbf{B})]_{\bar{\mathcal{S}}_{i}}},{\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}}\rangle$
$\displaystyle=\langle{[\nabla_{\mathbf{B}_{i}}f(\mathbf{A},\mathbf{B})-\nabla_{\mathbf{B}_{i}}f(\mathbf{A}^{\star},\mathbf{B})]_{\bar{\mathcal{S}}_{i}}},{\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}}\rangle$
$\displaystyle+\langle{[\nabla_{\mathbf{B}_{i}}f(\mathbf{A}^{\star},\mathbf{B})-\nabla_{\mathbf{B}_{i}}f(\mathbf{A}^{\star},\mathbf{B}^{\star})]_{\bar{\mathcal{S}}_{i}}},{\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}}\rangle$
$\displaystyle+\langle{[\nabla_{\mathbf{B}_{i}}f(\mathbf{A}^{\star},\mathbf{B}^{\star})]_{\bar{\mathcal{S}}_{i}}},{\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}}\rangle$
$\displaystyle=\mathcal{I}_{31,i}+\mathcal{I}_{32,i}+\mathcal{I}_{33,i}.$

First, we express $\mathcal{I}_{31,i}$ as (D.4) and obtain

$\displaystyle\mathcal{I}_{31,i}$
$\displaystyle=\langle{[\nabla_{\mathbf{B}_{i}}f(\mathbf{A},\mathbf{B})-\nabla_{\mathbf{B}_{i}}f(\mathbf{A}^{\star},\mathbf{B})]_{\bar{\mathcal{S}}_{i}}},{\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}}\rangle$
$\displaystyle=-\sum_{m=1}^{M}\langle{[\widetilde{\mathbf{B}}_{i}(\mathbf{I}_{p}\otimes{{\mathbf{A}^{m}}})\widehat{\bm{\Sigma}}^{m}_{\cdot\backslash\\{i\\}}(\mathbf{I}_{p-1}\otimes{\mathbf{A}^{m\top}})]_{\bar{\mathcal{S}}_{i}}},{\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}}\rangle$
$\displaystyle\quad+\sum_{m=1}^{M}\langle{[\widetilde{\mathbf{B}}_{i}(\mathbf{I}_{p}\otimes{\mathbf{A}^{m\star}})\widehat{\bm{\Sigma}}^{m}_{\cdot\backslash\\{i\\}}(\mathbf{I}_{p-1}\otimes{\mathbf{A}^{m\star\top}})]_{\bar{\mathcal{S}}_{i}}},{\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}}\rangle$
$\displaystyle=-\sum_{m=1}^{M}\langle{[\widetilde{\mathbf{B}}_{i}\\{\mathbf{I}_{p}\otimes{({\mathbf{A}^{m}}-\mathbf{A}^{m\star})}\\}\widehat{\bm{\Sigma}}^{m}_{\cdot\backslash\\{i\\}}(\mathbf{I}_{p-1}\otimes{\mathbf{A}^{m\star\top}})]_{\bar{\mathcal{S}}_{i}}},{\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}}\rangle$
$\displaystyle\quad-\sum_{m=1}^{M}\langle{[\widetilde{\mathbf{B}}_{i}(\mathbf{I}_{p}\otimes{{\mathbf{A}^{m}}})\widehat{\bm{\Sigma}}^{m}_{\cdot\backslash\\{i\\}}\\{\mathbf{I}_{p-1}\otimes{(\mathbf{A}^{m\top}-\mathbf{A}^{m\star\top})}\\}]_{\bar{\mathcal{S}}_{i}}},{\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}}\rangle.$
Apply Cauchy-Schwarz inequality, we can lower bound the above display as
$\displaystyle\geq-\sum_{m=1}^{M}\|[\widetilde{\mathbf{B}}_{i}\\{\mathbf{I}_{p}\otimes{({\mathbf{A}^{m}}-\mathbf{A}^{m\star})}\\}\widehat{\bm{\Sigma}}^{m}_{\cdot\backslash\\{i\\}}(\mathbf{I}_{p-1}\otimes{\mathbf{A}^{m\star\top}})]_{\bar{\mathcal{S}}_{i}}\|_{F}\|\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}\|_{F}$
$\displaystyle\quad-\sum_{m=1}^{M}\|[\widetilde{\mathbf{B}}_{i}(\mathbf{I}_{p}\otimes{{\mathbf{A}^{m}}})\widehat{\bm{\Sigma}}^{m}_{\cdot\backslash\\{i\\}}\\{\mathbf{I}_{p-1}\otimes{(\mathbf{A}^{m\top}-\mathbf{A}^{m\star\top})}\\}]_{\bar{\mathcal{S}}_{i}}\|_{F}\|\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}\|_{F}.$
(D.27)

We bound the above two terms individually. Following the same proof steps as
in (D.6), for $m=1,\ldots,M$, we can obtain

$\displaystyle\|[\widetilde{\mathbf{B}}_{i}$
$\displaystyle\\{\mathbf{I}_{p}\otimes{({\mathbf{A}^{m}}-\mathbf{A}^{m\star})}\\}\widehat{\bm{\Sigma}}^{m}_{\cdot\backslash\\{i\\}}(\mathbf{I}_{p-1}\otimes{\mathbf{A}^{m\star\top}})]_{\bar{\mathcal{S}}_{i}}\|_{F}\|\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}\|_{F}$
$\displaystyle\leq\sqrt{(1+\vartheta_{1})(1+\vartheta_{2})s^{\star}\alpha^{\star}\tau_{2}}\|\mathbf{A}^{m(0)}\|_{2}\|\widetilde{\mathbf{B}}_{i}\|_{F}\|\widehat{\bm{\Sigma}}^{m}\|_{2}\|{\mathbf{A}^{m}}-\mathbf{A}^{m\star}\|_{F}\|\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}\|_{F}$
$\displaystyle\leq\sqrt{(1+\vartheta_{1})(1+\vartheta_{2})s^{\star}\alpha^{\star}\tau_{2}}(C_{B}+1)\|\mathbf{A}^{m(0)}\|_{2}\|\widetilde{\mathbf{B}}_{i}^{\star}\|_{F}\|\widehat{\bm{\Sigma}}^{m}\|_{2}\|{\mathbf{A}^{m}}-\mathbf{A}^{m\star}\|_{F}\|\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}\|_{F}.$
(D.28)

We can bound the second term in (D.27) similar in the way shown in (D.24) and
obtain

$\displaystyle\|[\widetilde{\mathbf{B}}_{i}$
$\displaystyle(\mathbf{I}_{p}\otimes{{\mathbf{A}^{m}}})\widehat{\bm{\Sigma}}^{m}_{\cdot\backslash\\{i\\}}\\{\mathbf{I}_{p-1}\otimes{(\mathbf{A}^{m\top}-\mathbf{A}^{m\star\top})}\\}]_{\bar{\mathcal{S}}_{i}}\|_{F}\|\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}\|_{F}$
$\displaystyle\leq\sqrt{(1+\vartheta_{1})(1+\vartheta_{2})s^{\star}\alpha^{\star}\tau_{2}}\|\widehat{\bm{\Sigma}}^{m}\|_{2}\|\mathbf{A}^{m(0)}\|_{2}\|\widetilde{\mathbf{B}}_{i}\|_{1}\|{\mathbf{A}^{m}}-\mathbf{A}^{m\star}\|_{F}\|\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}\|_{F}$
$\displaystyle\leq\sqrt{(1+\vartheta_{1})(1+\vartheta_{2})s^{\star}\alpha^{\star}\tau_{2}}(1+C_{B})\|\widehat{\bm{\Sigma}}^{m}\|_{2}\|\mathbf{A}^{m(0)}\|_{2}\|\widetilde{\mathbf{B}}_{i}^{\star}\|_{1}\|{\mathbf{A}^{m}}-\mathbf{A}^{m\star}\|_{F}\|\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}\|_{F}.$
(D.29)

Combining results from (D.28)–(D.6), we can apply Young’s inequality and lower
bound $\mathcal{I}_{31,i}$ as

$\displaystyle\mathcal{I}_{31,i}$
$\displaystyle\geq-\sum_{m=1}^{M}\Upsilon_{4}\Upsilon_{3}\sqrt{s^{\star}}\|{\mathbf{A}^{m}}-\mathbf{A}^{m\star}\|_{F}\|\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}\|_{F}$
$\displaystyle\geq-\Upsilon_{4}\Upsilon_{3}\sqrt{s^{\star}}\sum_{m=1}^{M}\left(\frac{1}{2C_{31}}\|{\mathbf{A}^{m}}-\mathbf{A}^{m\star}\|_{F}^{2}+\frac{C_{31}}{2}\|\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}\|_{F}^{2}\right),$

where $\Upsilon_{3}$, and $\Upsilon_{4}$ are defined in Section C and $C_{31}$
is defined below.

We define the event $\bar{\mathcal{E}}_{i}$:

$\bar{\mathcal{E}}_{i}:=\cap_{m=1}^{M}{\mathcal{E}_{i}^{m}}(\bar{\mathscr{N}}_{i}),$
(D.30)

where ${\mathcal{E}_{i}^{m}}(\cdot)$ for $m=1,\ldots,M$ are defined in (D.20).
Then, taking the union bound, if
$N=O(\max_{m=1,\ldots,M}\kappa_{m}^{2}(k_{m}s^{\star}+\log M+\log p))$, we see
that event $\bar{\mathcal{E}}_{i}$ will happen with probability at least

$1-(pM)^{-1}\sum_{m=1}^{M}\exp\\{-k_{m}s^{\star}\\}\geq
1-p^{-1}\max_{m=1,\ldots,M}\exp(-k_{m}s^{\star}).$

To find the lower bound of $\mathcal{I}_{32,i}$, we use formula of
$\nabla_{\mathbf{B}_{i}}f$ stated in (D.4). Combining with the fact that

$-(\widetilde{\mathbf{B}}_{i}-\widetilde{\mathbf{B}}_{i}^{\star})(\mathbf{I}_{p}\otimes{\mathbf{A}^{m\star}})\mathbf{Y}^{m}=(\mathbf{B}_{i}-\mathbf{B}_{i}^{\star})(\mathbf{I}_{p-1}\otimes{\mathbf{A}^{m\star}}){\mathbf{Y}_{\backslash\\{i\\}}^{m}}$

for $m=1,\ldots,M$, we can write

$\displaystyle\mathcal{I}_{32,i}$
$\displaystyle=\langle{[\nabla_{\mathbf{B}_{i}}f(\mathbf{A}^{\star},\mathbf{B})-\nabla_{\mathbf{B}_{i}}f(\mathbf{A}^{\star},\mathbf{B}^{\star})]_{\bar{\mathcal{S}}_{i}}},{\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}}\rangle$
$\displaystyle=\sum_{m=1}^{M}\langle{-(\widetilde{\mathbf{B}}_{i}-\widetilde{\mathbf{B}}_{i}^{\star})(\mathbf{I}_{p}\otimes{\mathbf{A}^{m\star}})\widehat{\bm{\Sigma}}^{m}_{\cdot\backslash\\{i\\}}(\mathbf{I}_{p-1}\otimes{\mathbf{A}^{m\star\top}})},{[\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}]_{\bar{\mathcal{S}}_{i}}}\rangle$
$\displaystyle=\sum_{m=1}^{M}\langle{[\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}]_{\bar{\mathcal{S}}_{i}}(\mathbf{I}_{p-1}\otimes{\mathbf{A}^{m\star}})\widehat{\bm{\Sigma}}^{m}_{\cdot\backslash\\{i\\}}(\mathbf{I}_{p-1}\otimes{\mathbf{A}^{m\star\top}})},{[\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}]_{\bar{\mathcal{S}}_{i}}}\rangle$
$\displaystyle=\frac{1}{N}\sum_{m=1}^{M}\|[\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}]_{\bar{\mathcal{S}}_{i}}(\mathbf{I}_{p-1}\otimes{\mathbf{A}^{m\star}}){\mathbf{Y}_{\backslash\\{i\\}}^{m}}\|_{F}^{2}.$

Therefore, we can further lower bound $\mathcal{I}_{32,i}$ as

$\displaystyle\mathcal{I}_{32,i}$
$\displaystyle\geq\sum_{m=1}^{M}\sigma_{\min}^{2}(\mathbf{A}^{m\star})\sigma_{\min}(\widehat{\bm{\Sigma}}^{m}_{\bar{\mathscr{N}}_{i}\bar{\mathscr{N}}_{i}})\|\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}\|_{F}^{2}.$
$\displaystyle\geq\frac{\nu_{x}}{2}\sum_{m=1}^{M}\sigma_{\min}^{2}(\mathbf{A}^{m\star})\|\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}\|_{F}^{2}=M\Upsilon_{6}\|\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}\|_{F}^{2},$

with probability at least $1-p^{-1}\max_{m=1,\ldots,M}\exp(-k_{m}s^{\star})$.
The last inequality is followed by conditioning on the event
$\bar{\mathcal{E}}_{i}$ in (D.30).

Finally, applying Lemma I.6 yields,

$\displaystyle\mathcal{I}_{33,i}$
$\displaystyle=\langle{[\nabla_{\mathbf{B}_{i}}f(\mathbf{A}^{\star},\mathbf{B}^{\star})]_{\bar{\mathcal{S}}_{i}}},{\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}}\rangle$
$\displaystyle\geq-\|[\nabla_{\mathbf{B}_{i}}f(\mathbf{A}^{\star},\mathbf{B}^{\star})]_{\bar{\mathcal{S}}_{i}}\|_{r(k,\infty)}\|\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}\|_{r(k,1)}$
$\displaystyle\geq-\sqrt{(1+\vartheta_{1})s^{\star}}\|[\nabla_{\mathbf{B}_{i}}f(\mathbf{A}^{\star},\mathbf{B}^{\star})]_{\bar{\mathcal{S}}_{i}}\|_{r(k,\infty)}\|\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}\|_{r(k,2)}$
$\displaystyle=-\sqrt{(1+\vartheta_{1})s^{\star}}\|[\nabla_{\mathbf{B}_{i}}f(\mathbf{A}^{\star},\mathbf{B}^{\star})]_{\bar{\mathcal{S}}_{i}}\|_{r(k,\infty)}\|\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}\|_{F}$
$\displaystyle\geq-\sqrt{(1+\vartheta_{1})s^{\star}}\left\\{\frac{1}{2C_{33}}\|[\nabla_{\mathbf{B}_{i}}f(\mathbf{A}^{\star},\mathbf{B}^{\star})]_{\bar{\mathcal{S}}_{i}}\|_{r(k,\infty)}^{2}+\frac{C_{33}}{2}\|\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}\|_{F}^{2}\right\\}.$

Setting $C_{31}$, $C_{33}$ as

$C_{31}=\frac{\Upsilon_{6}}{2\Upsilon_{3}\Upsilon_{4}\sqrt{s^{\star}}},\quad
C_{33}=\frac{M\Upsilon_{6}}{2\sqrt{(1+\vartheta_{1})s^{\star}}},$

Combining $\mathcal{I}_{31,i}$, $\mathcal{I}_{32,i}$, $\mathcal{I}_{33,i}$,
$\mathcal{I}_{33,i}$ obtains

$\mathcal{I}_{3,i}\geq\frac{M\Upsilon_{6}}{2}\|\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}\|_{F}^{2}-\frac{s^{\star}\Upsilon_{4}^{2}\Upsilon_{3}^{2}}{\Upsilon_{6}}\sum_{m=1}^{M}\|{\mathbf{A}^{m}}-\mathbf{A}^{m\star}\|_{F}^{2}\\\
-\frac{(1+\vartheta_{1})s^{\star}}{M\Upsilon_{6}}\|[\nabla_{\mathbf{B}_{i}}f(\mathbf{A}^{\star},\mathbf{B}^{\star})]_{\bar{\mathcal{S}}_{i}}\|_{r(k,\infty)}^{2}.$

with probability at least $1-p^{-1}\max_{m=1,\ldots,M}\exp(-k_{m}s^{\star})$.

∎

######  Lemma D.9.

Under the conditions of Lemma D.2, we have

$\mathcal{I}_{4,i}\leq
3\bigg{\\{}\Upsilon_{5}Ms^{\star}\sum_{m=1}^{M}\|{\mathbf{A}^{m}}-\mathbf{A}^{m\star}\|_{F}^{2}+\Upsilon_{7}M^{2}\|\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}\|_{F}^{2}\\\
+(1+\vartheta_{1})s^{\star}\|[\nabla_{\mathbf{B}_{i}}f(\mathbf{A}^{\star},\mathbf{B}^{\star})]_{\bar{\mathcal{S}}_{i}}\|_{r(k,\infty)}^{2}\bigg{\\}}.$

###### Proof of Lemma D.9.

We want to find the upper bound of $\mathcal{I}_{4,i}$. By definition of
$\mathcal{I}_{4,i}$, we have

$\displaystyle\mathcal{I}_{4,i}$
$\displaystyle=\|[\nabla_{\mathbf{B}_{i}}f(\mathbf{A},\mathbf{B})]_{\bar{\mathcal{S}}_{i}}\|_{F}^{2}$
$\displaystyle\leq
3\bigg{\\{}\|[\nabla_{\mathbf{B}_{i}}f(\mathbf{A},\mathbf{B})-\nabla_{\mathbf{B}_{i}}f(\mathbf{A}^{\star},\mathbf{B})]_{\bar{\mathcal{S}}_{i}}\|_{F}^{2}$
$\displaystyle\quad\quad+\|[\nabla_{\mathbf{B}_{i}}f(\mathbf{A}^{\star},\mathbf{B})-\nabla_{\mathbf{B}_{i}}f(\mathbf{A}^{\star},\mathbf{B}^{\star})]_{\bar{\mathcal{S}}_{i}}\|_{F}^{2}$
$\displaystyle\quad\quad+\|[\nabla_{\mathbf{B}_{i}}f(\mathbf{A}^{\star},\mathbf{B}^{\star})]_{\bar{\mathcal{S}}_{i}}\|_{F}^{2}\bigg{\\}}$
$\displaystyle\leq
3(\mathcal{I}_{41,i}+\mathcal{I}_{42,i}+\mathcal{I}_{43,i}).$

We further upper bound $\mathcal{I}_{41,i}$ and $\mathcal{I}_{42,i}$,
respectively below.

First, we can write $\mathcal{I}_{41,i}$ using the result in (D.27):

$\displaystyle\mathcal{I}_{41,i}$
$\displaystyle=\|[\nabla_{\mathbf{B}_{i}}f(\mathbf{A},\mathbf{B})-\nabla_{\mathbf{B}_{i}}f(\mathbf{A}^{\star},\mathbf{B})]_{\bar{\mathcal{S}}_{i}}\|_{F}^{2}$
$\displaystyle=\bigg{\|}\sum_{m=1}^{M}[\widetilde{\mathbf{B}}_{i}(\mathbf{I}_{p}\otimes{{\mathbf{A}^{m}}})\widehat{\bm{\Sigma}}^{m}_{\cdot\backslash\\{i\\}}\\{\mathbf{I}_{p-1}\otimes{({\mathbf{A}^{m}}-\mathbf{A}^{m\star})}\\}^{\top}]_{\bar{\mathcal{S}}_{i}}$
$\displaystyle\quad\quad+[\widetilde{\mathbf{B}}_{i}\\{\mathbf{I}_{p}\otimes{({\mathbf{A}^{m}}-\mathbf{A}^{m\star})}\\}\widehat{\bm{\Sigma}}^{m}_{\cdot\backslash\\{i\\}}(\mathbf{I}_{p-1}\otimes{\mathbf{A}^{m\star\top}})]_{\bar{\mathcal{S}}_{i}}\bigg{\|}_{F}^{2}.$
Apply Cauchy-Schwarz inequality, the above display can be bounded as
$\displaystyle\leq
2M\sum_{m=1}^{M}\|[\widetilde{\mathbf{B}}_{i}(\mathbf{I}_{p}\otimes{{\mathbf{A}^{m}}})\widehat{\bm{\Sigma}}^{m}_{\cdot\backslash\\{i\\}}\\{\mathbf{I}_{p-1}\otimes{(\mathbf{A}^{m\top}-\mathbf{A}^{m\star\top})}\\}]_{\bar{\mathcal{S}}_{i}}\|_{F}^{2}$
$\displaystyle\quad+2M\sum_{m=1}^{M}\|[\widetilde{\mathbf{B}}_{i}\\{\mathbf{I}_{p}\otimes{({\mathbf{A}^{m}}-\mathbf{A}^{m\star})}\\}\widehat{\bm{\Sigma}}^{m}_{\cdot\backslash\\{i\\}}(\mathbf{I}_{p-1}\otimes{\mathbf{A}^{m\star\top}})]_{\bar{\mathcal{S}}_{i}}\|_{F}^{2}.$
(D.31)

Then, we bound the above two terms separately.

Since
$\widetilde{\mathbf{B}}_{i}(\mathbf{I}_{p}\otimes{{\mathbf{A}^{m}}})\widehat{\bm{\Sigma}}^{m}_{\cdot\backslash\\{i\\}}\\{\mathbf{I}_{p-1}\otimes{(\mathbf{A}^{m\top}-\mathbf{A}^{m\star\top})}\\}$
is evaluated on the support $\bar{\mathcal{S}}_{i}$, for any
$(u,v)\in\bar{\mathcal{S}}_{i}$, we have $\lceil
v/k\rceil\in\bar{\mathscr{N}}_{i}$. Therefore, we have

$\displaystyle\sum_{m=1}^{M}\|[\widetilde{\mathbf{B}}_{i}(\mathbf{I}_{p}\otimes{{\mathbf{A}^{m}}})$
$\displaystyle\widehat{\bm{\Sigma}}^{m}_{\cdot\backslash\\{i\\}}\\{\mathbf{I}_{p-1}\otimes{(\mathbf{A}^{m\top}-\mathbf{A}^{m\star\top})}\\}]_{\bar{\mathcal{S}}_{i}}\|_{F}^{2}$
$\displaystyle=\sum_{m=1}^{M}\|[\widetilde{\mathbf{B}}_{i}(\mathbf{I}_{p}\otimes{{\mathbf{A}^{m}}})\widehat{\bm{\Sigma}}^{m}_{\cdot\bar{\mathscr{N}}_{i}}\\{\mathbf{I}_{|\bar{\mathscr{N}}_{i}|}\otimes{(\mathbf{A}^{m\top}-\mathbf{A}^{m\star\top})}\\}]_{\bar{\mathcal{S}}_{i}}\|_{F}^{2}.$
$\displaystyle\leq(1+\vartheta_{1})s^{\star}\|\widetilde{\mathbf{B}}_{i}\|_{2}^{2}\sum_{m=1}^{M}\|{\mathbf{A}^{m}}\|_{2}^{2}\|\widehat{\bm{\Sigma}}^{m}\|_{2}^{2}\|{\mathbf{A}^{m}}-\mathbf{A}^{m\star}\|_{F}^{2}$
$\displaystyle\leq(1+\vartheta_{1})s^{\star}(1+C_{A})^{2}(2+C_{B})^{2}\|\widetilde{\mathbf{B}}_{i}^{\star}\|_{2}^{2}\sum_{m=1}^{M}\|\mathbf{A}^{m\star}\|_{2}^{2}\|\widehat{\bm{\Sigma}}^{m}\|_{2}^{2}\|{\mathbf{A}^{m}}-\mathbf{A}^{m\star}\|_{F}^{2},$
(D.32)

where the last line follows by the condition of Lemma D.2.

Similarly, we can write the second term of (D.31) as

$\displaystyle\sum_{m=1}^{M}\|[\widetilde{\mathbf{B}}_{i}\\{\mathbf{I}_{p}\otimes{({\mathbf{A}^{m}}-\mathbf{A}^{m\star})}\\}$
$\displaystyle\widehat{\bm{\Sigma}}^{m}_{\cdot\backslash\\{i\\}}(\mathbf{I}_{p-1}\otimes{\mathbf{A}^{m\star\top}})]_{\bar{\mathcal{S}}_{i}}\|_{F}^{2}$
$\displaystyle=\sum_{m=1}^{M}\|[\widetilde{\mathbf{B}}_{i\mathscr{N}_{i}}\\{\mathbf{I}_{|\mathscr{N}_{i}|}\otimes{({\mathbf{A}^{m}}-\mathbf{A}^{m\star})}\\}\widehat{\bm{\Sigma}}^{m}_{\mathscr{N}_{i}\backslash\\{i\\}}(\mathbf{I}_{p-1}\otimes{\mathbf{A}^{m\star\top}})]_{\bar{\mathcal{S}}_{i}}\|_{F}^{2}.$
Using the fact that
$|\mathscr{N}_{i}|\leq\vartheta_{1}s^{\star}/2\leq(1+\vartheta_{1})s^{\star}$,
we have
$\|\\{\mathbf{I}_{|\mathscr{N}_{i}|}\otimes{({\mathbf{A}^{m}}-\mathbf{A}^{m\star})}\\}\|_{F}^{2}\leq(1+\vartheta_{1})s^{\star}\|{\mathbf{A}^{m}}-\mathbf{A}^{m\star}\|_{F}^{2}$.
Therefore, the above display can be further bounded as
$\displaystyle\leq(1+\vartheta_{1})s^{\star}\|\widetilde{\mathbf{B}}_{i}\|_{2}^{2}\sum_{m=1}^{M}\|\mathbf{A}^{m\star}\|_{2}^{2}\|\widehat{\bm{\Sigma}}^{m}\|_{2}^{2}\|{\mathbf{A}^{m}}-\mathbf{A}^{m\star}\|_{F}^{2}$
$\displaystyle\leq(1+\vartheta_{1})s^{\star}(2+C_{B})^{2}\|\widetilde{\mathbf{B}}_{i}^{\star}\|_{2}^{2}\sum_{m=1}^{M}\|\mathbf{A}^{m\star}\|_{2}^{2}\|\widehat{\bm{\Sigma}}^{m}\|_{2}^{2}\|{\mathbf{A}^{m}}-\mathbf{A}^{m\star}\|_{F}^{2}.$
(D.33)

Plugging the results of (D.32)–(D.33) back to (D.31), we could conclude that

$\mathcal{I}_{41,i}\leq
M\Upsilon_{5}\sum_{m=1}^{M}s^{\star}\|{\mathbf{A}^{m}}-\mathbf{A}^{m\star}\|_{F}^{2},$

where
$\Upsilon_{5}=4(1+C_{A})^{2}(2+C_{B})^{2}\rho_{b}\rho_{a}\max_{m=1,\ldots,M}\|\widehat{\bm{\Sigma}}^{m}\|_{2}^{2}$.

Similarly, expanding $\mathcal{I}_{42,ij}$ obtains

$\displaystyle\mathcal{I}_{42,i}$
$\displaystyle\leq\|\nabla_{\mathbf{B}_{i}}f(\mathbf{A}^{\star},\mathbf{B})-\nabla_{\mathbf{B}_{i}}f(\mathbf{A}^{\star},\mathbf{B}^{\star})\|_{F}^{2}$
$\displaystyle=\left\|\sum_{m=1}^{M}(\mathbf{B}_{i}-\mathbf{B}_{i}^{\star})(\mathbf{I}_{p-1}\otimes{\mathbf{A}^{m\star}})\widehat{\bm{\Sigma}}^{m}_{\backslash\\{i\\}\backslash\\{i\\}}(\mathbf{I}_{p-1}\otimes{\mathbf{A}^{m\star\top}})\right\|_{F}^{2}$
$\displaystyle\leq
M\sum_{m=1}^{M}\|\mathbf{A}^{m\star}\|_{2}^{4}\|\widehat{\bm{\Sigma}}^{m}_{\backslash\\{i\\}\backslash\\{i\\}}\|_{2}^{2}\|\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}\|_{F}^{2}\leq\Upsilon_{7}M^{2}\|\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}\|_{F}^{2},$

where
$\Upsilon_{7}=\max_{m=1,\ldots,M}\rho_{a}^{2}\|\widehat{\bm{\Sigma}}^{m}\|_{2}^{2}$.

Next, we can write $\mathcal{I}_{43,i}$ as

$\mathcal{I}_{43,i}=\|[\nabla_{\mathbf{B}_{i}}f(\mathbf{A}^{\star},\mathbf{B}^{\star})]_{\bar{\mathcal{S}}_{i}}\|_{F}^{2}\leq(1+\vartheta_{1})s^{\star}\|[\nabla_{\mathbf{B}_{i}}f(\mathbf{A}^{\star},\mathbf{B}^{\star})]_{\bar{\mathcal{S}}_{i}}\|_{r(k,\infty)}^{2}.$

Combining results of $\mathcal{I}_{41,i}$ and $\mathcal{I}_{42,i}$, we can
conclude that

$\mathcal{I}_{4,i}\leq
3\bigg{\\{}\Upsilon_{5}Ms^{\star}\sum_{m=1}^{M}\|{\mathbf{A}^{m}}-\mathbf{A}^{m\star}\|_{F}^{2}+M^{2}\Upsilon_{7}\|\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}\|_{F}^{2}\\\
+(1+\vartheta_{1})s^{\star}\|[\nabla_{\mathbf{B}_{i}}f(\mathbf{A}^{\star},\mathbf{B}^{\star})]_{\bar{\mathcal{S}}_{i}}\|_{r(k,\infty)}^{2}\bigg{\\}}.$

∎

##  Appendix E Analysis of the Initialization

Section E.1 discusses the proof of Theorem 5.1. Section E.2 introduces
auxiliary lemmas for the proofs of Theorem 5.1. Section E.3 shows the proof of
Lemma 5.2.

###  E.1 Proof of Theorem 5.1

We prove the result for one modality. Let
$\check{\mathbf{A}}^{m\star}=(\mathbf{L}^{\star})^{\dagger}$ be the
pseudoinverse of $\mathbf{L}^{m\star}$, where
$\mathbf{L}^{m\star}\in\mathbb{R}^{k_{m}\times k}$ be the matrix realization
of ${\mathscr{L}^{m}}$ such that the $\ell\ell^{\prime}$-th entry of
$\mathbf{L}^{m\star}$ is
$L_{\ell\ell^{\prime}}^{m}=\langle{{\mathscr{L}^{m}}\phi_{\ell^{\prime}}^{m}},{\phi_{\ell}^{m}}\rangle_{\mathbb{H}_{m}}$.
It should be noted that $\check{\mathbf{A}}^{m\star}\in\mathbb{R}^{k\times
k_{m}}$ is different from $\mathbf{A}^{m\star}\in\mathbb{R}^{k\times k_{m}}$:
the former is first truncating ${\mathscr{L}^{m}}$ and then taking
pseudoinverse while the later is first taking the pseudoinverse of
${\mathscr{L}^{m}}$ and then conducting finite truncation. However, the
difference of the two will become small as $k$ and $k_{m}$ are selected large
enough and the remaining terms are small in magnitude. For the estimate in
(4.3), we have the following

$\|{\mathbf{A}^{m}}^{(0)}-\mathbf{Q}\mathbf{A}^{m\star}\|_{F}=\|\mathbf{Q}{\mathbf{A}^{m}}^{(0)}-\mathbf{A}^{m\star}\|_{F}\leq\|\mathbf{Q}{\mathbf{A}^{m}}^{(0)}-\check{\mathbf{A}}^{m\star}\|_{F}+\|{\check{\mathbf{A}}^{m\star}-\mathbf{A}^{m\star}}\|_{F},\qquad
m=1,2,$ (E.1)

where $\mathbf{Q}$ is a diagonal matrix with diagonal entries taking values in
$\\{-1,1\\}$ that aligns columns of the matrix $\mathbf{V}^{m}$ with the
corresponding columns of the population canonical matrix $\mathbf{V}^{m\star}$
so that $\langle{q_{j}\mathbf{v}_{j}^{m}},{\mathbf{v}_{j}^{m\star}}\rangle\geq
0$. For the first term of (E.1), we can apply the result of Lemma E.1 to find
a valid upper bound. For the second term, we recall that

$\displaystyle{\mathscr{L}^{k_{m},k}}=\sum_{\ell=1}^{k_{m}}\sum_{\ell^{\prime}=1}^{k}\langle{{\mathscr{L}^{m}}\phi_{\ell^{\prime}}},{\phi_{\ell}^{m}}\rangle_{\mathbb{H}_{m}}\phi_{\ell}^{m}\otimes\phi_{\ell^{\prime}};$
$\displaystyle\mathscr{A}_{m}^{k,k_{m}}=\sum_{\ell=1}^{k}\sum_{\ell^{\prime}=1}^{k_{m}}\langle{\mathscr{A}_{m}\phi_{\ell^{\prime}}^{m}},{\phi_{\ell}}\rangle_{\mathbb{H}}\phi_{\ell}\otimes\phi_{\ell^{\prime}}^{m}.$

Define ${\mathscr{L}^{m,r}}={\mathscr{L}^{m}}-{\mathscr{L}^{k_{m},k}}$ and
write

$\displaystyle\|\check{\mathbf{A}}^{m\star}-\mathbf{A}^{m\star}\|_{F}$
$\displaystyle\leq(2k)^{1/2}\|\check{\mathbf{A}}^{m\star}-\mathbf{A}^{m\star}\|_{2}$
$\displaystyle=(2k)^{1/2}|\\!|\\!|({\mathscr{L}^{k_{m},k}})^{\dagger}-\mathscr{A}_{m}^{k,k_{m}}|\\!|\\!|.$
Apply Lemma E.5, the above display can be bounded as $\displaystyle\leq
2^{3/2}k^{1/2}|\\!|\\!|{\mathscr{L}^{m}}^{\dagger}|\\!|\\!|^{2}|\\!|\\!|{\mathscr{L}^{m,r}}|\\!|\\!|.$

Hence, we complete the proof.

###  E.2 Proofs of Lemma E.1–E.6

######  Lemma E.1.

Suppose that Assumptions 5–6 hold and
$N=O(\max_{m=1,\ldots,M}\kappa_{m}^{2}k_{m})$ where
$\kappa_{m}=\sigma_{\max}(\bm{\Sigma}^{m})/\sigma_{\min}(\bm{\Sigma}^{m})$.
Then, let $C_{\gamma_{k},\nu_{x},\rho_{x}}>0$ be a constant depending on
$\gamma_{k}$, $\nu_{x}$, and $\rho_{x}$, we have

$\|\mathbf{Q}{\mathbf{A}^{m}}^{(0)}-\check{\mathbf{A}}^{m\star}\|_{F}\leq
C_{\gamma_{k},\nu,\rho}\left(1+\max_{j=1,\ldots,k}\max_{j\neq
i}\frac{1}{|\gamma_{j}-\gamma_{i}|}\right)\sqrt{k\frac{\sum_{k=1}^{2}k_{m}}{N}},$

with probability at least $1-5\exp(-\sum_{m=1}^{2}k_{m})$.

###### Proof of Lemma E.1.

We have

$\displaystyle\left\|\mathbf{Q}{\mathbf{A}^{m}}^{(0)}-\check{\mathbf{A}}^{m\star}\right\|_{F}$
$\displaystyle=\left\|\widehat{\bm{\Gamma}}^{-1/2}\widehat{\mathbf{V}}^{m\top}(\widehat{\bm{\Sigma}}_{11}^{m})^{-1/2}-\mathbf{Q}\bm{\Gamma}^{\star-1/2}\mathbf{V}^{m\star\top}(\bm{\Sigma}_{11}^{m})^{-1/2}\right\|_{F}$
$\displaystyle(\mathbf{Q},\bm{\Gamma}\text{ are diagonal matrices})$
$\displaystyle=\left\|\widehat{\bm{\Gamma}}^{-1/2}\widehat{\mathbf{V}}^{m\top}(\widehat{\bm{\Sigma}}_{11}^{m})^{-1/2}-\bm{\Gamma}^{\star-1/2}\mathbf{Q}\mathbf{V}^{m\star\top}(\bm{\Sigma}_{11}^{m})^{-1/2}\right\|_{F}$
$\displaystyle\leq\left\|\widehat{\bm{\Gamma}}^{-1/2}\widehat{\mathbf{V}}^{m\top}\left\\{(\widehat{\bm{\Sigma}}_{11}^{m})^{-1/2}-(\bm{\Sigma}_{11}^{m})^{-1/2}\right\\}\right\|_{F}$
$\displaystyle\quad+\left\|\widehat{\bm{\Gamma}}^{-1/2}\left(\widehat{\mathbf{V}}^{m}-\mathbf{V}^{m\star}\mathbf{Q}\right)^{\top}(\bm{\Sigma}_{11}^{m})^{-1/2}\right\|_{F}$
$\displaystyle\quad+\left\|\left(\widehat{\bm{\Gamma}}^{-1/2}-\bm{\Gamma}^{\star-1/2}\right)\mathbf{Q}\mathbf{V}^{m\star\top}(\bm{\Sigma}_{11}^{m})^{-1/2}\right\|_{F}.$

We then apply Lemma E.2–E.4 to upper bound the above three terms individually
and arrive at

$\displaystyle\left\|\mathbf{Q}{\mathbf{A}^{m}}^{(0)}-\check{\mathbf{A}}^{m\star}\right\|_{F}$
$\displaystyle\leq
C_{1}\|\widehat{\bm{\Gamma}}^{-1/2}\|_{2}(\rho_{x}^{1/2}\nu_{x}^{-2}+\nu_{x}^{-3/2})\sqrt{\frac{kk_{m}}{N}}$
$\displaystyle\quad+C_{2}k^{1/2}\nu_{x}^{-1/2}\|\widehat{\bm{\Gamma}}^{-1/2}\|_{2}(\gamma_{k}^{-3/2}+1)\max_{j=1,\ldots,k}\max_{j\neq
i}\frac{1}{|\gamma_{j}-\gamma_{i}|}\|\widehat{\mathbf{R}}^{12}-\mathbf{R}^{12\star}\|_{2},$

with probability at least $1-\exp(-k_{m})$.

Under the condition that $N=O(\max_{m=1,\ldots,M}\kappa_{m}^{2}k_{m})$, we
could apply Lemma E.6 and obtain

$\|\widehat{\mathbf{R}}^{12}-\mathbf{R}^{12\star}\|_{2}^{2}\leq
C_{3}\rho_{x}^{4}\nu_{x}^{-4}(\rho_{x}^{1/2}\nu_{x}^{-1/2}+1)^{2}\frac{\sum_{m=1}^{2}k_{m}}{N}$

with probability at least $1-3\exp(-\sum_{m=1}^{2}k_{m})$ for some constant
$C_{3}>0$.

Recall that
$\|\widehat{\bm{\Gamma}}^{-1/2}\|_{2}=\|\widehat{\mathbf{R}}_{12}^{-1/2}\|_{2}$
and by Lemma I.1, we have
$\|\widehat{\bm{\Gamma}}^{-1/2}\|_{2}\leq(3/2)\gamma_{k}^{-1/2}$, with
probability at least $1-\exp(-k)$.

Taking the union bound, we can conclude that

$\|\mathbf{Q}{\mathbf{A}^{m}}^{(0)}-\check{\mathbf{A}}^{m\star}\|_{F}\leq
C_{\gamma_{k},\rho_{x},\nu_{x}}\left(1+\max_{j=1,\ldots,k}\max_{j\neq
i}\frac{1}{|\gamma_{j}-\gamma_{i}|}\right)\sqrt{\frac{k\sum_{k=1}^{2}k_{m}}{N}},$

with probability at least $1-5\exp(-\sum_{m=1}^{2}k_{m})$ and

$\displaystyle C_{\gamma_{k},\rho_{x},\nu_{x}}$
$\displaystyle=C_{4}\bigg{\\{}\gamma_{k}^{-1/2}(\rho_{x}^{1/2}\nu_{x}^{-2}+\nu_{x}^{-3/2})+\rho_{x}^{2}\nu_{x}^{-5/2}(\gamma_{k}^{-1/2}+\gamma_{k}^{-2})(\rho_{x}^{1/2}\nu_{x}^{-1/2}+1)\bigg{\\}},$

for some universal constant $C_{4}>0$. ∎

######  Lemma E.2.

Under the conditions of Lemma E.1 and an universal constant $C_{1}>0$, we have

$\left\|\widehat{\bm{\Gamma}}^{-1/2}\widehat{\mathbf{V}}^{m\top}\left\\{(\widehat{\bm{\Sigma}}_{11}^{m})^{-1/2}-(\bm{\Sigma}_{11}^{m})^{-1/2}\right\\}\right\|_{F}\leq
C_{1}\|\widehat{\bm{\Gamma}}^{-1/2}\|_{2}(\rho_{x}^{1/2}\nu_{x}^{-2}+\nu_{x}^{-3/2})\sqrt{\frac{kk_{m}}{N}},$

with probability at least $1-\exp(-k_{m})$.

###### Proof of Lemma E.2.

We have

$\displaystyle\left\|\widehat{\bm{\Gamma}}^{-1/2}\widehat{\mathbf{V}}^{m\top}\left\\{(\widehat{\bm{\Sigma}}_{11}^{m})^{-1/2}-(\bm{\Sigma}_{11}^{m})^{-1/2}\right\\}\right\|_{F}$
$\displaystyle=\left\|{\widehat{\bm{\Gamma}}^{-1/2}\widehat{\mathbf{V}}^{m\top}\left\\{(\widehat{\bm{\Sigma}}_{11}^{m})^{-1/2}-(\bm{\Sigma}_{11}^{m})^{-1/2}\right\\}}\right\|_{F}$
$\displaystyle\leq
k^{1/2}\left\|\widehat{\bm{\Gamma}}^{-1/2}\right\|_{2}\left\|(\widehat{\bm{\Sigma}}_{11}^{m})^{-1/2}-(\bm{\Sigma}_{11}^{m})^{-1/2}\right\|_{2},$
where the inequality follows by the fact that
$\|\widehat{\mathbf{V}}^{m}\|_{2}\leq 1$. Apply Lemma I.10, we can further
obtain that $\displaystyle\leq
k^{1/2}\left\\{3\left\|(\widehat{\bm{\Sigma}}_{11}^{m})^{-1/2}\right\|_{2}\left(\left\|\widehat{\bm{\Sigma}}_{11}^{m}\right\|_{2}\vee\left\|\bm{\Sigma}_{11}^{m}\right\|_{2}\right)+1\right\\}$
$\displaystyle\quad\times\left\|\widehat{\bm{\Gamma}}^{-1/2}\right\|_{2}\left\|(\bm{\Sigma}_{11}^{m})^{-3/2}\right\|_{2}\left\|\widehat{\bm{\Sigma}}_{11}^{m}-\bm{\Sigma}_{11}^{m}\right\|_{2}.$

Recall that
$\sigma_{\min}(\bm{\Sigma}^{m}_{11})\geq\sigma_{\min}(\bm{\Sigma}^{m})\geq\nu_{x}$
and
$\rho_{x}\geq\sigma_{\max}(\bm{\Sigma}^{m})\geq\sigma_{\max}(\bm{\Sigma}^{m}_{11})$.
Since $N=O(\max_{m=1,\ldots,M}\kappa_{m}^{2}k_{m})$, we have

$3\rho_{x}/2\geq\sigma_{\min}(\widehat{\bm{\Sigma}}^{m}_{11})\geq\nu_{x}/2,$
(E.2)

with probability at least $1-\exp(-k_{m})$, following Lemma I.1.

Therefore, under Assumption 6, we have

$\displaystyle\left\\{3\left\|(\widehat{\bm{\Sigma}}_{11}^{m})^{-1/2}\right\|_{2}\left(\left\|\widehat{\bm{\Sigma}}_{11}^{m}\right\|_{2}\vee\left\|\bm{\Sigma}_{11}^{m}\right\|_{2}\right)+1\right\\}\left\|(\bm{\Sigma}_{11}^{m})^{-3/2}\right\|_{2}\leq
9\rho_{x}^{1/2}\nu_{x}^{-2}+\nu_{x}^{-3/2},$ (E.3)

with probability at least $1-\exp(-k_{m})$. Then, we arrive at the conclusion
that

$\displaystyle\|\widehat{\bm{\Gamma}}^{-1/2}\widehat{\mathbf{V}}^{m\top}\left((\widehat{\bm{\Sigma}}_{11}^{m})^{-1/2}-(\bm{\Sigma}_{11}^{m})^{-1/2}\right)\|_{F}$
$\displaystyle\leq
C_{1}\|\widehat{\bm{\Gamma}}^{-1/2}\|_{2}(\rho_{x}^{1/2}\nu_{x}^{-2}+\nu_{x}^{-3/2})\sqrt{\frac{kk_{m}}{N}},$

with probability at least $1-\exp(-k_{m})$. ∎

######  Lemma E.3.

Under the conditions of Lemma E.1 and an universal constant $C_{1}>0$, we have

$\|\widehat{\bm{\Gamma}}^{-1/2}\left(\widehat{\mathbf{V}}^{m}-\mathbf{V}^{m\star}\mathbf{Q}\right)^{\top}(\bm{\Sigma}_{i,i}^{m})^{-1/2}\|_{F}\\\
\leq
C_{1}k^{1/2}\nu_{x}^{-1/2}\|\widehat{\bm{\Gamma}}^{-1/2}\|_{2}\max_{j=1,\ldots,k}\max_{j\neq
i}\frac{1}{|\gamma_{j}-\gamma_{i}|}\|\widehat{\mathbf{R}}^{12}-\mathbf{R}^{12\star}\|_{2}.$

###### Proof of Lemma E.3.

Write

$\left\|\widehat{\bm{\Gamma}}^{-1/2}\left(\widehat{\mathbf{V}}^{m}-\mathbf{V}^{m\star}\mathbf{Q}\right)^{\top}(\bm{\Sigma}_{11}^{m})^{-1/2}\right\|_{F}\leq\|\widehat{\bm{\Gamma}}^{-1/2}\|_{2}\|(\bm{\Sigma}_{11}^{m})^{-1/2}\|_{2}\|\widehat{\mathbf{V}}^{m}-\mathbf{V}^{m\star}\mathbf{Q}\|_{F}.$

Note that we have

$\displaystyle\|\widehat{\mathbf{V}}^{m}-\mathbf{V}^{m\star}\mathbf{Q}\|_{F}^{2}=\sum_{i=1}^{k}\|\widehat{\mathbf{v}}_{i}^{m}-q_{i}\mathbf{v}_{i}^{m\star}\|_{2}^{2},$

where $q_{i}$ is the $i$th diagonal entry of $\mathbf{Q}$.

Since $q_{i}$ is either $+1$ or $-1$ such that
$\|\widehat{\mathbf{v}}_{i}^{m}-q_{i}\mathbf{v}_{i}^{m\star}\|_{2}^{2}$ is
minimized, we know that
$\langle{\widehat{\mathbf{v}}_{i}^{m}},{q_{i}\mathbf{v}_{i}^{m\star}}\rangle\geq
0$. Let $\Delta=\widehat{\mathbf{R}}^{12}-\mathbf{R}^{12\star}$ and
$C_{2},C_{3}>0$ be universal constants. Recall the singular decomposition of
$\mathbf{R}^{12\star}$ is
$\mathbf{R}^{12\star}=\sum_{j}^{k}\gamma_{j}\mathbf{v}_{j}^{1\star}(\mathbf{v}_{j}^{2\star})^{\top}$,
where $\gamma_{j}$ could be viewed as the canonical correlation of
$\mathbf{y}_{1}^{1}$ and ${\mathbf{y}_{1}^{2}}$ for $j=1,\ldots,k$. Without
the loss of generality, let $m=1$ be the first data modality and
$m^{\prime}=2$ be the second data modality, we can apply Theorem 5.2.2 in
hsing2015theoretical, restated in Lemma I.9, and obtain

$\displaystyle\|\widehat{\mathbf{v}}_{i}^{m}-q_{i}\mathbf{v}_{i}^{m\star}\|_{2}$
$\displaystyle\leq\bigg{\|}\sum_{j\neq
i}\frac{\gamma_{j}\langle{\mathbf{v}_{j}^{m^{\prime}}q_{j}},{\Delta^{\top}\mathbf{v}_{i}^{m\star}q_{i}}\rangle+\gamma_{i}\langle{\mathbf{v}_{i}^{m^{\prime}}q_{i}},{\Delta^{\top}\mathbf{v}_{j}^{m\star}q_{j}}\rangle}{\gamma_{j}^{2}-\gamma_{i}^{2}}(\mathbf{v}_{j}^{m\star}q_{j})\bigg{\|}_{2}$
$\displaystyle\quad+C_{2}\max_{j\neq
i}\frac{2}{|\gamma_{j}^{2}-\gamma_{i}^{2}|}\|\Delta\|_{2}$
$\displaystyle\leq\max_{j\neq
i}\frac{\gamma_{j}}{|\gamma_{j}^{2}-\gamma_{i}^{2}|}\bigg{\|}\sum_{j\neq
i}\langle{\mathbf{v}_{j}^{m^{\prime}}q_{j}},{\Delta^{\top}\mathbf{v}_{i}^{m\star}q_{i}}\rangle(\mathbf{v}_{j}^{m\star}q_{j})\bigg{\|}_{2}$
$\displaystyle\quad+\max_{j\neq
i}\frac{\gamma_{i}}{|\gamma_{j}^{2}-\gamma_{i}^{2}|}\bigg{\|}\sum_{j\neq
i}{\langle{\mathbf{v}_{i}^{m^{\prime}}q_{i}},{\Delta^{\top}\mathbf{v}_{j}^{m\star}q_{j}}\rangle}(\mathbf{v}_{j}^{m\star}q_{j})\bigg{\|}_{2}$
$\displaystyle\quad+C_{2}\max_{j\neq
i}\frac{2}{|\gamma_{j}^{2}-\gamma_{i}^{2}|}\|\Delta\|_{2}.$ Since
$\|\sum_{j\neq
i}{\langle{\mathbf{v}_{i}^{m^{\prime}}q_{i}},{\Delta^{\top}\mathbf{v}_{j}^{m\star}q_{j}}\rangle}(\mathbf{v}_{j}^{m\star}q_{j})\|_{2}\leq\|\Delta\|_{2}$,
$\|\sum_{j\neq
i}\langle{\mathbf{v}_{j}^{m^{\prime}}q_{j}},{\Delta^{\top}\mathbf{v}_{i}^{m\star}q_{i}}\rangle(\mathbf{v}_{j}^{m\star}q_{j})\|_{2}\leq\|\Delta\|_{2}$
and $\gamma_{i},\gamma_{j}\leq 1$, the above display can be further bounded as
$\displaystyle\leq\max_{j\neq
i}\frac{2\|\Delta\|_{2}}{|\gamma_{j}^{2}-\gamma_{i}^{2}|}+C_{2}\max_{j\neq
i}\frac{2}{|\gamma_{j}^{2}-\gamma_{i}^{2}|}\|\Delta\|_{2}$ $\displaystyle\leq
C_{3}\max_{j\neq i}\frac{1}{|\gamma_{j}-\gamma_{i}|}\|\Delta\|_{2},$

where the last inequality follows by the fact that the magnitude of the
canonical correlation is less than one $|\gamma_{i}|\leq 1$ for any $i$ and
hence
$|\gamma_{j}^{2}-\gamma_{i}^{2}|\leq|\gamma_{j}-\gamma_{i}||\gamma_{j}+\gamma_{i}|\leq
2|\gamma_{j}-\gamma_{i}|$. Then, we complete the proof.

∎

######  Lemma E.4.

Under the conditions of Lemma E.1 and an universal constant $C_{1}>0$, we have

$\|\left(\widehat{\bm{\Gamma}}^{-1/2}-\bm{\Gamma}^{\star-1/2}\right)\mathbf{Q}\mathbf{V}^{m\star\top}(\bm{\Sigma}_{11}^{m})^{-1/2}\|_{F}\leq
k^{1/2}\gamma_{k}^{-3/2}\nu_{x}^{-1/2}(3\|\widehat{\bm{\Gamma}}^{-1/2}\|+1)\|\widehat{\mathbf{R}}^{12}-\mathbf{R}^{12\star}\|_{2}.$

###### Proof of Lemma E.4.

Since $\mathbf{Q}$ is a diagonal matrix whose diagonal entries taking values
in $\\{1,-1\\}$ and $\|\mathbf{V}^{m\star\top}\|_{2}\leq 1$, we can write

$\left\|\left(\widehat{\bm{\Gamma}}^{-1/2}-\bm{\Gamma}^{\star-1/2}\right)\mathbf{Q}\mathbf{V}^{m\star\top}(\bm{\Sigma}_{11}^{m})^{-1/2}\right\|_{F}\leq\|(\bm{\Sigma}_{11}^{m})^{-1/2}\|_{2}\left\|{\widehat{\bm{\Gamma}}^{-1/2}-\bm{\Gamma}^{\star-1/2}}\right\|_{F}.$

Applying Lemma I.10 again with
$\lambda=(\|\widehat{\bm{\Gamma}}\|_{2}\vee\|\bm{\Gamma}^{\star}\|_{2})\leq 1$
yields

$\displaystyle\|\widehat{\bm{\Gamma}}^{-1/2}-\bm{\Gamma}^{\star-1/2}\|_{F}$
$\displaystyle\leq
k^{1/2}\|\bm{\Gamma}^{\star-3/2}\|(3\|\widehat{\bm{\Gamma}}^{-1/2}\|+1)\|\widehat{\bm{\Gamma}}-\bm{\Gamma}^{\star}\|_{2}.$
$\displaystyle\leq
k^{1/2}\gamma_{k}^{-3/2}(3\|\widehat{\bm{\Gamma}}^{-1/2}\|+1)\|\widehat{\bm{\Gamma}}-\bm{\Gamma}^{\star}\|_{2}.$
(E.4)

Applying Weyl’s inequality (See Theorem III.2.1 in bhatia2013matrix for
details), we have

$\|\widehat{\bm{\Gamma}}-\bm{\Gamma}^{\star}\|_{2}\leq\|\widehat{\mathbf{R}}^{12}-\mathbf{R}^{12\star}\|_{2}.$

Then, we complete the proof.

∎

######  Lemma E.5.

Let ${\mathscr{L}}\in\mathfrak{B}(\mathbb{H}_{1},\mathbb{H}_{2})$ be a compact
operator and $\\{\phi_{1,\ell}\\}_{\ell\in\mathbb{N}}$ and
$\\{\phi_{2,\ell}\\}_{\ell\in\mathbb{N}}$ be the CONS for $\mathbb{H}_{1}$ and
$\mathbb{H}_{2}$, respectively. Let

${\mathscr{L}^{r}}={\mathscr{L}}-{\mathscr{L}^{p,d}},\quad{\mathscr{L}^{p,d}}=\sum_{\ell=1}^{p}\sum_{\ell^{\prime}=1}^{d}\langle{{\mathscr{L}}\phi_{1,\ell^{\prime}}},{\phi_{2,\ell}}\rangle\phi_{2,\ell}\otimes\phi_{1,\ell^{\prime}}.$

Define $\mathscr{A}=\mathscr{L}^{\dagger}$ and
$\mathscr{A}^{d,p}=\sum_{\ell=1}^{d}\sum_{\ell^{\prime}=1}^{p}\langle{{\mathscr{L}^{\dagger}}\phi_{2,\ell^{\prime}}},{\phi_{1,\ell}}\rangle\phi_{1,\ell}\otimes\phi_{2,\ell^{\prime}}$,
then we have

$\|(\mathscr{L}^{p,d})^{\dagger}-\mathscr{A}^{d,p}\|_{\text{HS}}\leq
2|\\!|\\!|{\mathscr{L}}^{\dagger}|\\!|\\!|^{2}|\\!|\\!|{\mathscr{L}^{r}}|\\!|\\!|.$

###### Proof of Lemma E.5.

Write

$\displaystyle|\\!|\\!|(\mathscr{L}^{p,d})^{\dagger}-\mathscr{A}^{d,p}|\\!|\\!|$
$\displaystyle\leq|\\!|\\!|({\mathscr{L}^{p,d}})^{\dagger}-\mathscr{A}|\\!|\\!|$
$\displaystyle=|\\!|\\!|({\mathscr{L}^{p,d}})^{\dagger}-({\mathscr{L}^{p,d}}+{\mathscr{L}^{r}})^{\dagger}|\\!|\\!|.$
Apply the result from Lemma I.8, we could further bound the above display as
$\displaystyle\leq
2(|\\!|\\!|({\mathscr{L}^{p,d}})^{\dagger}|\\!|\\!|^{2}\vee|\\!|\\!|{\mathscr{L}}^{\dagger}|\\!|\\!|^{2})|\\!|\\!|{\mathscr{L}^{r}}|\\!|\\!|$
$\displaystyle\leq
2|\\!|\\!|{\mathscr{L}}^{\dagger}|\\!|\\!|^{2}|\\!|\\!|{\mathscr{L}^{r}}|\\!|\\!|.$

Hence we complete the proof. ∎

######  Lemma E.6.

Given two centered Gaussian random vectors
$\mathbf{x}\in\mathbb{R}^{d},\mathbf{y}\in\mathbb{R}^{p}$ with covariance
$\bm{\Sigma}_{x}$ and $\bm{\Sigma}_{y}$, respectively. We define
$\bm{\Sigma}_{xy}$ be the cross covariance and
$\mathbf{R}_{xy}=\bm{\Sigma}_{x}^{-1/2}\bm{\Sigma}_{xy}\bm{\Sigma}_{y}^{-1/2}$.
Let $\widehat{\bm{\Sigma}}_{x}$ be the sample covariance of $\mathbf{x}$,
$\widehat{\bm{\Sigma}}_{y}$ sample covariance of $\mathbf{y}$, and
$\widehat{\bm{\Sigma}}_{xy}$ be the sample cross covariance of
$\mathbf{x},\mathbf{y}$ with $N$ independent samples. Define
$\widehat{\mathbf{R}}_{xy}=\widehat{\bm{\Sigma}}_{x}^{-1/2}\widehat{\bm{\Sigma}}_{xy}\widehat{\bm{\Sigma}}_{y}^{-1/2}$.
Let $C_{1}>0$ be an universal constant. Assume that $N=O(p+d)$,
$\alpha=(\|\bm{\Sigma}_{x}\|_{2}\vee\|\bm{\Sigma}_{y}\|_{2})$ and
$\beta=(\|\bm{\Sigma}_{x}^{-1/2}\|_{2}\vee\|\bm{\Sigma}_{y}^{-1/2}\|_{2})$,
then

$\|\widehat{\mathbf{R}}_{xy}-\mathbf{R}_{xy}\|_{2}\leq
C_{1}\alpha^{2}\beta^{4}(3\alpha^{1/2}\beta+1)\sqrt{\frac{(p+d)}{N}},$

with probability at least $1-3\exp\\{-(p+d)\\}$.

###### Proof.

The inequality could be shown by first applying the triangle inequality and
then use the tail bound to find the upper bound of each term individually. We
have

$\displaystyle\|\widehat{\mathbf{R}}_{xy}-\mathbf{R}_{xy}\|_{2}$
$\displaystyle\leq\|(\widehat{\bm{\Sigma}}_{x}^{-1/2}-\bm{\Sigma}_{x}^{-1/2})\widehat{\bm{\Sigma}}_{xy}\widehat{\bm{\Sigma}}_{y}^{-1/2}\|_{2}$
$\displaystyle\quad+\|\bm{\Sigma}_{x}^{-1/2}(\widehat{\bm{\Sigma}}_{xy}-\bm{\Sigma}_{xy})\widehat{\bm{\Sigma}}_{y}^{-1/2}\|_{2}$
$\displaystyle\quad+\|\bm{\Sigma}_{x}^{-1/2}\bm{\Sigma}_{xy}(\widehat{\bm{\Sigma}}_{y}^{-1/2}-\bm{\Sigma}_{y}^{-1/2})\|_{2}$
$\displaystyle\leq\mathcal{I}_{9,1}+\mathcal{I}_{9,2}+\mathcal{I}_{9,3}.$

Since $N=O(d+p)$, we have

$\displaystyle(i)\quad\sigma_{\min}(\widehat{\bm{\Sigma}}_{x})\geq\frac{1}{2}\sigma_{\min}(\bm{\Sigma}_{x});$
$\displaystyle(ii)\quad\sigma_{\min}(\widehat{\bm{\Sigma}}_{y})\geq\frac{1}{2}\sigma_{\min}(\bm{\Sigma}_{y});$
$\displaystyle(iii)\quad\sigma_{\max}(\widehat{\bm{\Sigma}}_{xy})\leq\frac{3}{2}\sigma_{\min}(\bm{\Sigma}_{xy})\leq\frac{3}{2}(\|\bm{\Sigma}_{x}\|_{2}\vee\|\bm{\Sigma}_{y}\|_{2}),$

with probability at least $1-3\exp\\{-(d+p)\\}$, following Lemma I.1 and the
union bound.

Apply Lemma I.10 and Lemma I.1 to $\mathcal{I}_{9,1}$ and we could obtain the
upper bound

$\mathcal{I}_{9,1}\leq
C_{2}(\|\bm{\Sigma}_{x}\|_{2}\vee\|\bm{\Sigma}_{y}\|_{2})^{2}(\|\bm{\Sigma}_{x}^{-1/2}\|_{2}\vee\|\bm{\Sigma}_{y}^{-1/2}\|_{2})^{4}\\\
\left\\{3(\|\bm{\Sigma}_{x}\|_{2}\vee\|\bm{\Sigma}_{y}\|_{2})^{1/2}(\|\bm{\Sigma}_{x}^{-1/2}\|_{2}\vee\|\bm{\Sigma}_{y}^{-1/2}\|_{2})+1\right\\}\sqrt{\frac{(p+d)}{N}},$

with probability $1-3\exp\\{-(d+p)\\}$ for some absolute constant $C_{2}>0$.
We obtain the same upper bound for $\mathcal{I}_{9,3}$. For
$\mathcal{I}_{9,2}$, we have smaller coefficient:

$\mathcal{I}_{9,2}\leq
C_{3}(\|\bm{\Sigma}_{x}\|_{2}\vee\|\bm{\Sigma}_{y}\|_{2})(\|\bm{\Sigma}_{x}^{-1/2}\|_{2}\vee\|\bm{\Sigma}_{y}^{-1/2}\|_{2})^{2}\sqrt{\frac{(p+d)}{N}},$

with probability $1-2\exp\\{-(d+p)\\}$ and $C_{3}>0$. Hence, the terms
$\mathcal{I}_{9,1}$ and $\mathcal{I}_{9,3}$ dominate. Then, by summing up
$\mathcal{I}_{9,1}$, $\mathcal{I}_{9,2}$, and $\mathcal{I}_{9,3}$, we complete
the proof.

∎

###  E.3 Proof of Lemma 5.2

The proof is consisted of three steps. In the first step, we show the
condition where the solution is nontrivial. In the second and third step, we
show the contraction of the iterates of Algorithm 2.

Step 1. Given ${\mathbf{A}^{m}}^{(0)}$ for $m=1,\ldots,M$, we want to verify
that ${\mathbf{A}^{m}}^{(0)}{\mathbf{Y}_{i}^{m}}\neq{\bf 0}$ for
$m=1,\ldots,M$ and $i\in V$ with high probability. Then the solution to the
minimizer of $h_{i}(\mathbf{B}_{i})$ is nontrivial. Since

$\frac{1}{N}\|{\mathbf{A}^{m}}^{(0)}{\mathbf{Y}_{i}^{m}}\|_{F}^{2}=\operatorname{vec}({\mathbf{A}^{m}}^{(0)})^{\top}(\mathbf{I}_{k}\otimes\widehat{\bm{\Sigma}}^{m}_{ii})\operatorname{vec}({\mathbf{A}^{m}}^{(0)})\geq
0$

and
$\sigma_{\min}(\mathbf{I}_{k}\otimes\widehat{\bm{\Sigma}}^{m}_{ii})=\sigma_{\min}(\widehat{\bm{\Sigma}}^{m}_{ii})$,
it suffices to show that $\sigma_{\min}(\widehat{\bm{\Sigma}}^{m}_{ii})>0$. We
define the event as

${\mathcal{E}_{ii}^{m}}=\\{\sigma_{\min}(\widehat{\bm{\Sigma}}^{m}_{ii})>0\\},\quad
m=1,\ldots,M.$

Then, under the condition that $N=O(\kappa_{m}^{2}(k_{m}+\log M+\log p))$,
Lemma I.1 states that event ${\mathcal{E}_{ii}^{m}}$ happens with probability
at least $1-(pM)^{-1}\exp(-k_{m})$ for $m=1,\ldots,M$. Taking the union bound
again and applying De Morgan’s law, we can show that the event

$\cap_{m=1}^{M}\cap_{i=1}^{p}{\mathcal{E}_{ii}^{m}},$

happens with probability at least $1-\max_{m=1,\ldots,M}\exp(-k_{m})$. Then,
we conclude that ${\mathbf{A}^{m}}^{(0)}{\mathbf{Y}_{i}^{m}}\neq{\bf 0}$ for
$i\in V$ and $m=1,\ldots,M$ with probability at least

$1-\max_{m=1,\ldots,M}\exp(-k_{m})\geq
1-\max_{m=1,\ldots,M}\exp(-k_{m}s^{\star}).$

Step 2. Given that the solution is nontrivial, the next step is to prove that
the projected gradient descent would converge to a local optimum with
quantified error. By Lemma G.5, we know that $h$ is a
$\min_{m=1,\ldots,M}2^{-1}\nu_{x}\sigma_{\min}^{2}({\mathbf{A}^{m}}^{(0)})$-strongly
convex with respect to $\mathbf{B}_{i}$ with probability at least
$1-\max_{m=1,\ldots,M}\exp(-k_{m}s^{\star})$. It is easy to verify that $h$ is
$\max_{m=1,\ldots,M}\sigma_{\max}^{2}(\mathbf{A}^{m(0)})\|\widehat{\bm{\Sigma}}^{m}\|$-smooth.
Let $\widehat{\mathbf{Z}}_{i}^{m}=\mathbf{A}^{m(0)}{\mathbf{Y}_{i}^{m}}$ and
$\mathbf{Z}_{i}^{m}=\mathbf{A}^{m\star}{\mathbf{Y}_{i}^{m}}$ for $i\in V$.
Then, we can write

$h(\mathbf{B}_{i})=\frac{1}{M}\sum_{m=1}^{M}\|\widehat{\mathbf{Z}}_{i}^{m}-\sum_{j\in
i\in V}\mathbf{B}_{ij}\widehat{\mathbf{Z}}_{j}^{m}\|_{F}^{2}.$

Let
$\pi_{0}=C_{\vartheta}\left\\{1-{\sigma_{\min}^{2}(\mathbf{A}^{m^{\prime}(0)})\nu_{x}\eta_{B_{0}}}/2\right\\}$.
Apply Lemma E.7–E.8, we can obtain

$\displaystyle\|\mathbf{B}_{i}^{+}-\mathbf{B}_{i}^{\star}\|_{F}$
$\displaystyle\leq\pi_{0}\|\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}\|_{F}$
$\displaystyle\quad+\eta_{B_{0}}C_{\vartheta}\frac{1}{M}\sum_{m=1}^{M}\big{\\{}\|[-\widetilde{\mathbf{B}}_{i}^{\star}\\{\mathbf{I}_{p}\otimes{({\mathbf{A}^{m}}^{(0)}-\mathbf{A}^{m\star})}\\}\widehat{\bm{\Sigma}}^{m}_{\cdot\backslash\\{i\\}}(\mathbf{I}_{p-1}\otimes{{\mathbf{A}^{m}}^{(0)}})^{\top}]_{\bar{\mathcal{S}}_{i}}\|_{F}$
$\displaystyle\quad\quad\quad\quad\quad\quad\quad\quad+\|[\widetilde{\mathbf{B}}_{i}^{\star}(\mathbf{I}_{p}\otimes{\mathbf{A}^{m\star}})\widehat{\bm{\Sigma}}^{m}_{\cdot\backslash\\{i\\}}\\{\mathbf{I}_{p-1}\otimes{({\mathbf{A}^{m}}^{(0)}-\mathbf{A}^{m\star})}\\}^{\top}]_{\bar{\mathcal{S}}_{i}}\|_{F}\big{\\}}$
$\displaystyle\quad+{C_{\delta,i}C_{\vartheta}\eta_{B_{0}}}\sqrt{\frac{\alpha^{\star}s^{\star}k^{2}}{N}},$
(E.5)

with probability at least $1-3\max_{m=1,\ldots,M}\exp(-k_{m}s^{\star})$.

Note that we can write

$\displaystyle\|[-\widetilde{\mathbf{B}}_{i}^{\star}(\mathbf{I}_{p}\otimes{{\mathbf{A}^{m}}^{(0)}})\widehat{\bm{\Sigma}}^{m}_{\cdot\backslash\\{i\\}}(\mathbf{I}_{p-1}\otimes{{\mathbf{A}^{m}}^{(0)}})^{\top}+\widetilde{\mathbf{B}}_{i}^{\star}(\mathbf{I}_{p}\otimes{\mathbf{A}^{m\star}})\widehat{\bm{\Sigma}}^{m}_{\cdot\backslash\\{i\\}}(\mathbf{I}_{p-1}\otimes{\mathbf{A}^{m\star}})^{\top}]_{\bar{\mathcal{S}}_{i}}\|_{F}$
$\displaystyle\leq\big{\\{}\|[-\widetilde{\mathbf{B}}_{i}^{\star}\\{\mathbf{I}_{p}\otimes{({\mathbf{A}^{m}}^{(0)}-\mathbf{A}^{m\star})}\\}\widehat{\bm{\Sigma}}^{m}_{\cdot\backslash\\{i\\}}(\mathbf{I}_{p-1}\otimes{{\mathbf{A}^{m}}^{(0)}})^{\top}]_{\bar{\mathcal{S}}_{i}}\|_{F}$
$\displaystyle\quad\quad\quad\quad\quad\quad+\|[\widetilde{\mathbf{B}}_{i}^{\star}(\mathbf{I}_{p}\otimes{\mathbf{A}^{m\star}})\widehat{\bm{\Sigma}}^{m}_{\cdot\backslash\\{i\\}}\\{\mathbf{I}_{p-1}\otimes{({\mathbf{A}^{m}}^{(0)}-\mathbf{A}^{m\star})}\\}^{\top}]_{\bar{\mathcal{S}}_{i}}\|_{F}\big{\\}}$
$\displaystyle\leq\rho_{b}^{1/2}\|\widehat{\bm{\Sigma}}^{m}\|_{2}\left\\{\sigma_{\max}({\mathbf{A}^{m}}^{(0)})+\rho_{a}^{1/2}\right\\}\sqrt{(1+\vartheta_{1})s^{\star}}\|{\mathbf{A}^{m}}^{(0)}-\mathbf{A}^{m\star}\|_{F}$
$\displaystyle\leq
C_{\gamma}\|{\mathbf{A}^{m}}^{(0)}-\mathbf{A}^{m\star}\|_{F},$ (E.6)

where
$C_{\gamma}=\max_{m=1,\ldots,M}\rho_{b}^{1/2}\|\widehat{\bm{\Sigma}}^{m}\|_{2}\left\\{\sigma_{\max}({\mathbf{A}^{m}}^{(0)})+\rho_{a}^{1/2}\right\\}\sqrt{(1+\vartheta_{1})s^{\star}}$.

Combine (E.5)–(E.6) together, we have

$\|\mathbf{B}_{i}^{+}-\mathbf{B}_{i}^{\star}\|_{F}\leq\pi_{0}\|\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}\|_{F}+\frac{C_{\gamma}C_{\vartheta}\eta_{B_{0}}}{M}\sum_{m=1}^{M}\|\mathbf{A}^{m(0)}-\mathbf{A}^{m\star}\|_{F}+{C_{\delta,i}C_{\vartheta}\eta_{B_{0}}}\sqrt{\frac{\alpha^{\star}s^{\star}k^{2}}{N}},$

with probability at least $1-3\max_{m=1,\ldots,M}\exp(-k_{m}s^{\star})$.

Step 3. Starting with $\mathbf{B}_{i}^{(0)}={\bf 0}$, after $L$ iterations of
Algorithm 2, we have the following result by telescoping technique:

$\displaystyle\|\mathbf{B}_{i}^{(L)}-\mathbf{B}_{i}^{\star}\|_{F}\leq\pi_{0}^{L}\|\mathbf{B}_{i}^{\star}\|_{F}+\frac{C_{\gamma}C_{\vartheta}}{1-\pi_{0}}\frac{\eta_{B_{0}}}{M}\sum_{m=1}^{M}\|\mathbf{A}^{m(0)}-\mathbf{A}^{m\star}\|_{F}+\frac{C_{\delta,i}C_{\vartheta}\eta_{B_{0}}}{1-\pi_{0}}\sqrt{\frac{\alpha^{\star}s^{\star}k^{2}}{N}},$

with probability at least $1-3\max_{m=1,\ldots,M}\exp(-k_{m}s^{\star})$.

######  Lemma E.7.

Consider the following objective function

$\widehat{g}(\mathbf{B}_{i})=(\mathbf{B}_{i})=\frac{1}{2N}\bigg{\|}\widehat{\mathbf{Z}}_{i}-\sum_{j\neq
i}\mathbf{B}_{ij}\widehat{\mathbf{Z}}_{j}\bigg{\|}_{F}^{2},$

where $\widehat{g}$ is $L$-smooth and $\mu$-strongly convex with respect to
$\mathbf{B}_{i}$ and $\widehat{\mathbf{Z}}_{i}\in\mathbb{R}^{k\times N}$ for
$i\in V$. Let one-step iterate of the update to be

$\mathbf{B}_{i}^{+}=\mathcal{H}_{\alpha}\circ{\mathcal{T}}_{s}\left(\mathbf{B}_{i}-\eta\nabla_{\mathbf{B}_{i}}\widehat{g}(\mathbf{B}_{i})\right),$

where $\eta\leq 1/L$. Let $\mathbf{Z}_{i}\in\mathbb{R}^{k\times N}$ for $i\in
V$. Define

$\displaystyle\widehat{\mathbf{K}}_{\cdot\backslash i}$
$\displaystyle=(\widehat{\mathbf{Z}}_{1}^{\top},\ldots,\widehat{\mathbf{Z}}_{i-1}^{\top},\widehat{\mathbf{Z}}_{i}^{\top},\ldots,\widehat{\mathbf{Z}}_{p}^{\top})^{\top}(\widehat{\mathbf{Z}}_{1}^{\top},\ldots,\widehat{\mathbf{Z}}_{i-1}^{\top},\widehat{\mathbf{Z}}_{i+1}^{\top},\ldots,\widehat{\mathbf{Z}}_{p}^{\top})\in\mathbb{R}^{kp\times
k(p-1)}$ $\displaystyle\mathbf{K}_{\cdot\backslash i}$
$\displaystyle=(\mathbf{Z}_{1}^{\top},\ldots,\mathbf{Z}_{i-1}^{\top},\mathbf{Z}_{i}^{\top},\ldots,\mathbf{Z}_{p}^{\top})^{\top}(\mathbf{Z}_{1}^{\top},\ldots,\mathbf{Z}_{i-1}^{\top},\mathbf{Z}_{i+1}^{\top},\ldots,\mathbf{Z}_{p}^{\top})\in\mathbb{R}^{kp\times
k(p-1)}.$

Then

$\frac{1}{C_{\vartheta}}\|\mathbf{B}_{i}^{+}-\mathbf{B}_{i}^{\star}\|_{F}\leq\left(1-\eta\mu\right)\|\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}\|_{F}+\eta\|[\widetilde{\mathbf{B}}_{i}^{\star}(\widehat{\mathbf{K}}_{\cdot\backslash
i}-\mathbf{K}_{\cdot\backslash
i})]_{\bar{\mathcal{S}}_{i}}\|_{F}+\eta\|[\widetilde{\mathbf{B}}_{i}^{\star}\mathbf{K}_{\cdot\backslash
i}]_{\bar{\mathcal{S}}_{i}}\|_{F}$

where $\bar{\mathcal{S}}_{i}$ is defined in (D.5).

###### Proof.

First, we define

$g(\mathbf{B}_{i})=\frac{1}{2N}\bigg{\|}\mathbf{Z}_{i}-\sum_{j\neq
i}\mathbf{B}_{ij}\mathbf{Z}_{j}\bigg{\|}_{F}^{2}.$

Apply Lemma H.3–H.4, we can write

$\|\mathbf{B}_{i}^{+}-\mathbf{B}_{i}^{\star}\|_{F}=\|\mathcal{H}_{\alpha}\circ{\mathcal{T}}_{s}\left(\mathbf{B}_{i}-\eta\nabla_{\mathbf{B}_{i}}\widehat{g}(\mathbf{B}_{i})\right)-\mathbf{B}_{i}^{\star}\|_{F}\leq
C_{\vartheta}\|\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}-\eta[\nabla_{\mathbf{B}_{i}}\widehat{g}(\mathbf{B}_{i})]_{\bar{\mathcal{S}}_{i}}\|_{F},$

where $\bar{\mathcal{S}}_{i}$ is defined in (D.5). Then, by (D.14), we can
write

$\displaystyle\|\mathbf{B}_{i}^{+}-\mathbf{B}_{i}^{\star}\|_{F}$
$\displaystyle\leq
C_{\vartheta}\big{\\{}\|\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}-\eta[\nabla_{\mathbf{B}_{i}}\widehat{g}(\mathbf{B}_{i})-\nabla_{\mathbf{B}_{i}}\widehat{g}(\mathbf{B}_{i}^{\star})]_{\bar{\mathcal{S}}_{i}}\|_{F}$
$\displaystyle\quad+\|\eta[\nabla_{\mathbf{B}_{i}}\widehat{g}(\mathbf{B}_{i}^{\star})-\nabla_{\mathbf{B}_{i}}g(\mathbf{B}_{i}^{\star})]_{\bar{\mathcal{S}}_{i}}\|_{F}+\|[\eta\nabla_{\mathbf{B}_{i}}g(\mathbf{B}_{i}^{\star})]_{\bar{\mathcal{S}}_{i}}\|_{F}\big{\\}},$

where $C_{\vartheta}$ is a constant depending on $\vartheta_{1}$ and
$\vartheta_{2}$ defined in Section C.

Write

$\displaystyle\|\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}-$
$\displaystyle\eta[\nabla_{\mathbf{B}_{i}}\widehat{g}(\mathbf{B}_{i})-\nabla_{\mathbf{B}_{i}}\widehat{g}(\mathbf{B}_{i}^{\star})]_{\bar{\mathcal{S}}_{i}}\|_{F}$
$\displaystyle\leq\|\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}-\eta\left\\{\nabla_{\mathbf{B}_{i}}\widehat{g}(\mathbf{B}_{i})-\nabla_{\mathbf{B}_{i}}\widehat{g}(\mathbf{B}_{i}^{\star})\right\\}\|_{F}$
$\displaystyle=\|\operatorname{vec}\left(\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}\right)-\eta\operatorname{vec}\left(\nabla_{\mathbf{B}_{i}}\widehat{g}(\mathbf{B}_{i})-\nabla_{\mathbf{B}_{i}}\widehat{g}(\mathbf{B}_{i}^{\star})\right)\|_{2}$
$\displaystyle=\bigg{\|}\left\\{\mathbf{I}_{k^{2}(p-1)}-\eta\int_{t=0}^{1}\nabla^{2}\widehat{g}(\operatorname{vec}\left(t\mathbf{B}_{i}+(1-t)\mathbf{B}_{i}^{\star}\right))dt\right\\}\operatorname{vec}\left(\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}\right)\bigg{\|}_{2}$
$\displaystyle\leq\bigg{\|}{\mathbf{I}_{k^{2}(p-1)}-\eta\int_{t=0}^{1}\nabla^{2}\widehat{g}(\operatorname{vec}\left(t\mathbf{B}_{i}+(1-t)\mathbf{B}_{i}^{\star}\right))dt}\bigg{\|}_{2}\|\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}\|_{F}$
$\displaystyle\leq\left(1-\eta\mu\right)\|\mathbf{B}_{i}-\mathbf{B}_{i}^{\star}\|_{F}$
(E.7)

Note that we can write
$\nabla_{\mathbf{B}_{i}}\widehat{g}(\mathbf{B}_{i}^{\star})=-\widetilde{\mathbf{B}}_{i}^{\star}\widehat{\mathbf{K}}_{\cdot\backslash
i}$ and
$\nabla_{\mathbf{B}_{i}}{g}(\mathbf{B}_{i}^{\star})=-\widetilde{\mathbf{B}}_{i}^{\star}\mathbf{K}_{\cdot\backslash
i}$. Then, we can write

$\displaystyle\|\eta[\nabla_{\mathbf{B}_{i}}\widehat{g}(\mathbf{B}_{i}^{\star})-\nabla_{\mathbf{B}_{i}}g(\mathbf{B}_{i}^{\star})]_{\bar{\mathcal{S}}_{i}}\|_{F}=\eta\|[\widetilde{\mathbf{B}}_{i}^{\star}(\widehat{\mathbf{K}}_{\cdot\backslash
i}-\mathbf{K}_{\cdot\backslash i})]_{\bar{\mathcal{S}}_{i}}\|_{F},$

where
$\widetilde{\mathbf{B}}_{i}^{\star}=(-\mathbf{B}_{i1}^{\star}\cdots-\mathbf{B}_{ip}^{\star})\in\mathbb{R}^{k\times
pk}$. ∎

######  Lemma E.8.

Under the conditions of Lemma 5.2 and define

$C_{\delta,i}=C_{2}\sqrt{(1+\vartheta_{2})(1+\vartheta_{1})}\\\
\times\max_{m=1,\ldots,M}\rho_{x}^{1/2}\rho_{a}^{1/2}\\{\rho_{b}^{1/2}\|\bm{\Sigma}^{m,\mathbf{u}}\|_{2}^{1/2}+(\rho_{a}\rho_{b})^{1/2}\|\bm{\Sigma}^{m,\mathbf{q}}\|_{2}^{1/2}+\|\bm{\Sigma}_{i}^{\mathbf{r}}\|_{2}^{1/2}+\|\bm{\Sigma}_{i}^{\mathbf{w}}\|_{2}^{1/2}\\},$

where $C_{2}>0$ is an universal constant, we have

$\eta_{B_{0}}\|[\nabla_{\mathbf{B}_{i}}h_{i}(\mathbf{B}_{i}^{\star})]_{\bar{\mathcal{S}}_{i}}\|_{F}\leq
C_{\delta,i}\eta_{B_{0}}\sqrt{\frac{\alpha^{\star}s^{\star}k^{2}}{N}},$

with probability at least $1-\exp\\{{-\alpha^{\star}ks^{\star}}\\}$.

###### Proof of Lemma E.8.

We use similar argument of Lemma D.4 and write that

$[\nabla_{\mathbf{B}_{i}}h_{i}(\mathbf{B}_{i}^{\star})]_{\bar{\mathcal{S}}_{i}}=-\frac{1}{MN}\left[\sum_{m=1}^{M}\sum_{n=1}^{N}\mathbf{v}_{i}^{m,(n)}(\mathbf{y}_{\backslash\\{i\\}}^{m,(n)})^{\top}(\mathbf{I}_{p-1}\otimes{\mathbf{A}^{m\star\top}})\right]_{\bar{\mathcal{S}}_{i}},$

where $\mathbf{v}_{i}^{m,(n)}$ is defined in (D.15).

Define

$\displaystyle\mathcal{U}_{1}({\mathcal{S}})$
$\displaystyle=\\{\mathbf{u}:\text{supp}({\mathbf{u}})\subset\\{{\mathcal{S}}_{\cdot,i},i=1,\ldots
k(p-1)\\},\|\mathbf{u}\|_{1}=1\\},\;{\mathcal{S}}_{\cdot,i}=\\{u:(u,i)\in{\mathcal{S}}\\};$
$\displaystyle\mathcal{U}_{2}({\mathcal{S}})$
$\displaystyle=\\{\mathbf{w}:\text{supp}(\mathbf{w})\subset\\{{\mathcal{S}}_{i,\cdot},i=1,\ldots,k\\},\|\mathbf{w}\|_{1}=1\\},\;{\mathcal{S}}_{i,\cdot}=\\{v;(i,v)\in{\mathcal{S}}\\}.$

For notation simplicity, we define
$\mathcal{U}_{1}=\mathcal{U}_{1}(\bar{\mathcal{S}}_{i})$ and
$\mathcal{U}_{2}=\mathcal{U}_{2}(\bar{\mathcal{S}}_{i})$. Let
$\mathcal{N}_{1}$ be the $1/8$-net of $\mathcal{U}_{1}$ and $\mathcal{N}_{2}$
be the $1/8$-net of $\mathcal{U}_{2}$. Then, we can write

$\displaystyle\|[\nabla_{\mathbf{B}_{i}}h_{i}(\mathbf{B}_{i}^{\star})]_{\bar{\mathcal{S}}_{i}}\|_{F}$
$\displaystyle\leq\sqrt{k}\|[\nabla_{\mathbf{B}_{i}}h_{i}(\mathbf{B}_{i}^{\star})]_{\bar{\mathcal{S}}_{i}}\|_{2}$
$\displaystyle=\sqrt{k}\sup_{\mathbf{u}\in\mathcal{U}_{1}}\sup_{\mathbf{w}\in\mathcal{U}_{2}}\mathbf{u}^{\top}\left[\frac{1}{N}\sum_{n=1}^{N}\frac{1}{M}\sum_{m=1}^{M}\mathbf{v}_{i}^{m,(n)}(\mathbf{y}_{\backslash\\{i\\}}^{m,(n)})^{\top}(\mathbf{I}_{p-1}\otimes{\mathbf{A}^{m\star\top}})\right]_{\bar{\mathcal{S}}_{i}}\mathbf{w}.$
Apply Lemma I.4, we can upper bound the above display as $\displaystyle\leq
2\sqrt{k}\sup_{\mathbf{u}\in\mathcal{N}_{1}}\sup_{\mathbf{w}\in\mathcal{N}_{2}}\mathbf{u}^{\top}\left[\frac{1}{N}\sum_{n=1}^{N}\frac{1}{M}\sum_{m=1}^{M}\mathbf{v}_{i}^{m,(n)}(\mathbf{y}_{\backslash\\{i\\}}^{m,(n)})^{\top}(\mathbf{I}_{p-1}\otimes{\mathbf{A}^{m\star\top}})\right]_{\bar{\mathcal{S}}_{i}}\mathbf{w},$

where the right hand side can be seen as sum of i.i.d. sub-exponential random
variables with Orlicz norm upper bounded by
$\max_{m=1,\ldots,M}\rho_{x}^{1/2}\rho_{a}^{1/2}\\{\rho_{b}^{1/2}\|\bm{\Sigma}^{m,\mathbf{u}}\|_{2}^{1/2}+(\rho_{a}\rho_{b})^{1/2}\|\bm{\Sigma}^{m,\mathbf{q}}\|_{2}^{1/2}+\|\bm{\Sigma}_{i}^{\mathbf{r}}\|_{2}^{1/2}+\|\bm{\Sigma}_{i}^{\mathbf{w}}\|_{2}^{1/2}\\}$,
where a similar proof can be found in Lemma D.4. Define

$C_{\delta,i}=C_{2}\sqrt{(1+\vartheta_{2})(1+\vartheta_{1})}\\\
\times\max_{m=1,\ldots,M}\rho_{x}^{1/2}\rho_{a}^{1/2}\\{\rho_{b}^{1/2}\|\bm{\Sigma}^{m,\mathbf{u}}\|_{2}^{1/2}+(\rho_{a}\rho_{b})^{1/2}\|\bm{\Sigma}^{m,\mathbf{q}}\|_{2}^{1/2}+\|\bm{\Sigma}_{i}^{\mathbf{r}}\|_{2}^{1/2}+\|\bm{\Sigma}_{i}^{\mathbf{w}}\|_{2}^{1/2}\\},$

and $C_{2}>0$. Therefore, apply Bernstein’s inequality with
$N=O(C_{\delta,i}^{2}\alpha^{\star}s^{\star}k)$ and take the union bound over
all $\mathcal{N}_{1}$ with
$|\mathcal{N}_{1}|\leq(17)^{(1+\vartheta_{1})\alpha^{\star}k}$ and
$\mathcal{N}_{2}$ with
$|\mathcal{N}_{2}|\leq(17)^{(1+\vartheta_{1})(1+\vartheta_{2})\alpha^{\star}ks^{\star}}$,
we have

$\displaystyle\mathcal{I}_{73,i}$
$\displaystyle=\eta_{B_{0}}\|[\nabla_{\mathbf{B}_{i}}h_{i}(\mathbf{B}_{i}^{\star})]_{\bar{\mathcal{S}}_{i}}\|_{F}\leq\eta_{B_{0}}\sqrt{k}\|[\nabla_{\mathbf{B}_{i}}h_{i}(\mathbf{B}_{i}^{\star})]_{\bar{\mathcal{S}}_{i}}\|_{2}\leq
C_{\delta,i}\eta_{B_{0}}\sqrt{\frac{\alpha^{\star}s^{\star}k^{2}}{N}},$

with probability at least $1-\exp\\{{-\alpha^{\star}ks^{\star}}\\}\geq
1-\max_{m=1,\ldots,M}\exp(-k_{m}s^{\star})$,

∎

##  Appendix F Proof of Theorem 5.4

The main theorem combines results from Theorem 5.1 and Lemma 5.2 with result
from Theorem 5.3.

_Step 1_ : The first step is to show that ${\mathbf{A}^{m}}^{(0)}$ computed
from (4.3) for $m=1,\ldots,M$ and $\mathbf{B}_{i}$ outputed by Algorithm 2 for
$i\in V$ satisfy Assumption 8. Since
$\|{\mathbf{A}^{m}}^{(0)}-\mathbf{A}^{m\star}\|_{2}\leq\|{\mathbf{A}^{m}}^{(0)}-\mathbf{A}^{m\star}\|_{F}$
and
$\sqrt{8k}|\\!|\\!|\mathscr{A}^{m}|\\!|\\!|^{2}|\\!|\\!|\mathscr{L}^{m,r}|\\!|\\!|$
is a constant under the condition that
$|\\!|\\!|\mathscr{L}^{m,r}|\\!|\\!|=o(1/\sqrt{k_{m}})$, Theorem 5.1 tells us
that there exists a $N=O(\max_{m=1,\ldots,M}k_{m}+\log M)$, with $M=2$, such
that $\|{\mathbf{A}^{m}}^{(0)}-\mathbf{A}^{m\star}\|_{2}\geq
C_{A}\|\mathbf{A}^{m\star}\|_{2}+\sqrt{8k}|\\!|\\!|\mathscr{A}^{m}|\\!|\\!|^{2}|\\!|\\!|\mathscr{L}^{m,r}|\\!|\\!|$
with probability smaller than $2^{-1}\exp(-k_{1}-k_{2})$ for each $m=1,2$.
Using the condition that Taking the union bound, we have
$\|{\mathbf{A}^{m}}^{(0)}-\mathbf{A}^{m\star}\|_{2}\geq
C_{A}\|\mathbf{A}^{m\star}\|_{2}$ for $m=1,\ldots,M$ with probability smaller
than $\exp(-k_{1}-k_{2})$. We define this event as $\mathcal{E}_{A^{0}}^{c}$.

Similarly, since all norms in finite dimensional are equivalent, it suffices
to show that $\|\mathbf{B}_{i}^{(0)}-\mathbf{B}_{i}^{\star}\|_{F}\leq
C_{B}\|\mathbf{B}_{i}^{\star}\|_{F}$ for $i\in V$. Under the condition
$N=O(\max_{m=1,\ldots,M}s^{\star}k_{m}+\log M+\log p)$, apply Lemma 5.2 with
the number of iteration $L_{0}=-C_{1}\log\\{(k^{2}+\log s^{\star})\\}/{N}\\}$
and Theorem 5.1, we have
$\|{\mathbf{B}_{i}^{(0)}-\mathbf{B}_{i}^{\star}}\|_{F}\geq
C_{B}\|\mathbf{B}_{i}^{\star}\|_{F}$ with probability smaller than
$3p^{-1}\delta_{0}$ for each $i\in V$. Then, taking the union bound over $i\in
V$, we have $\|\mathbf{B}_{i}^{(0)}-\mathbf{B}_{i}^{\star}\|_{F}\geq
C_{B}\|\mathbf{B}_{i}^{\star}\|_{F}$ for $i\in V$ with probability smaller
than $3\delta_{0}$. We define such conditional event as
$\mathcal{E}_{B^{0}\cap A^{0}}^{c}$. Therefore, Assumption 8 holds with
probability at least

$1-\left\\{\mathbb{P}(\mathcal{E}_{B^{0}}^{c})+\mathbb{P}(\mathcal{E}_{A^{0}}^{c})\right\\}\geq
1-\left\\{\mathbb{P}(\mathcal{E}_{B^{0}\cap
A^{0}}^{c})+\mathbb{P}(\mathcal{E}_{A^{0}}^{c})\right\\}\geq 1-4\delta_{0}.$

_Step 2_ : Under Assumption 8, we can apply Theorem 5.3. The second part of
the theorem can be shown by triangle inequality. Let $L$ be any constant such
that $L\geq(-\log(1-\pi)+2\log\Xi-2\log R_{0})/\log\pi$. This implies that for
any $i\in V$

$\displaystyle\|\mathbf{B}_{i,j}^{(L)}-\mathbf{B}_{ij}^{\star}\|_{F}$
$\displaystyle\leq\left(\max_{m=1,\ldots,M}\|\mathbf{A}_{m}^{(L)}-\mathbf{A}^{m\star}\|_{F}^{2}+\max_{i\in
V}\|\mathbf{B}_{i,j}^{(L)}-\mathbf{B}_{ij}^{\star}\|_{F}^{2}\right)^{1/2}$
$\displaystyle\leq\sqrt{\frac{2}{1-\pi}}\Xi\leq\frac{1}{2}\Lambda(k)$

Suppose that $j\in\mathscr{N}_{i}^{\star}$, then

$\|\mathbf{B}_{i,j}^{(L)}\|_{F}\geq\|\mathbf{B}_{ij}^{\star}\|_{F}-\|\mathbf{B}_{i,j}^{(L)}-\mathbf{B}_{ij}^{\star}\|_{F}\geq\Lambda(k)-\frac{1}{2}\Lambda(k)=\frac{1}{2}\Lambda(k),$

with probability at least $1-10\delta_{0}$. Similarly, if
$j\in{\mathscr{N}_{i}^{\star}}^{c}\backslash\\{i\\}$,

$\|\mathbf{B}_{i,j}^{(L)}\|_{F}\leq\|\mathbf{B}_{i,j}^{(L)}-\mathbf{B}_{ij}^{\star}\|_{F}\leq\frac{1}{2}\Lambda(k),$

with probability at least $1-10\delta_{0}$. Therefore, under Assumption 4, if
we select edges with the threshold $(1/2)\Lambda(k)$, we are able to recover
the edge set with probability at least $1-10\delta_{0}$. Finally,
marginalizing over the conditional probability that Assumption 8 holds, we
have

$\mathbb{P}(\widehat{\mathscr{N}}_{i}=\mathscr{N}_{i}^{\star};1\leq i\leq
p)\geq(1-10\delta_{0})(1-4\delta_{0})\geq 1-14\delta_{0}$

##  Appendix G Strong Convexity and Smoothness

In this section, we show the convexity coefficient and smoothness coefficient
of $f(\cdot)$ and $h_{i}(\cdot)$. Lemma G.3 states that
$f(\cdot,\mathbf{B}^{\star})$ is strongly convex and smooth with respect to
any ${\mathbf{A}^{m}}$ for $m=1,\ldots,M$ with high probability under proper
sample size condition. Lemma G.5 shows that under mild condition of
${\mathbf{A}^{m}}$ for $m=1,\ldots,M$ and sample size, $h_{i}(\cdot)$ is
strongly convex and smooth with respect $\mathbf{B}_{i}$ with high
probability. We being with reviewing the definition of $L$-smoothness and
$\mu$-strong convexity.

######  Definition G.1.

A function $f:\operatorname{Dom}(f)\rightarrow\mathbb{R}$ is $L$-smooth if for
any $\mathbf{x},\mathbf{y}\in\operatorname{Dom}(f)$ we have that

$\left|f(\mathbf{y})-f(\mathbf{x})-\langle{\nabla
f(\mathbf{x})},{\mathbf{y}-\mathbf{x}}\rangle\right|\leq\frac{L}{2}\|\mathbf{y}-\mathbf{x}\|_{2}^{2}.$

######  Definition G.2.

A function $f:\operatorname{Dom}(f)\rightarrow\mathbb{R}$ is $\mu$-strongly
convex if for any $\mathbf{x},\mathbf{y}\in\operatorname{Dom}(f)$ we have that

$f(\mathbf{y})\geq f(\mathbf{x})+\langle{\nabla
f(\mathbf{x})},{\mathbf{y}-\mathbf{x}}\rangle+\frac{\mu}{2}\|\mathbf{y}-\mathbf{x}\|_{2}^{2}.$

######  Lemma G.3.

Assume that Assumption 6–7 hold, $\|\mathbf{B}_{i}^{\star}\|_{r(k,0)}\leq
s^{\star}$ for $i\in V$ and
$\kappa_{m}=\sigma_{\max}(\bm{\Sigma}^{m})/\sigma_{\min}(\bm{\Sigma}^{m})$. If
$N=O(\kappa_{m}^{2}(k_{m}s^{\star}+\log M+\log p))$, then
$f(\mathbf{A},\mathbf{B}^{\star})$ is
$\\{(s^{\star}+1)p\nu_{x}\nu_{b}\\}/{2}$-strongly convex and
$\\{3(s^{\star}+1)p\rho_{x}\rho_{b}\\}/{2}$-smooth with respect to
${\mathbf{A}^{m}}$ with probability at least
$1-M^{-1}\exp\\{-k_{m}(s^{\star}+1)\\}$.

###### Proof of Lemma G.3.

Define the following two constants:

$\displaystyle d_{1}$
$\displaystyle=({s^{\star}+1})\sum_{i=1}^{p}\sigma_{\min}(\widehat{\bm{\Sigma}}^{m}_{\mathscr{N}_{i}^{\star}\cup\\{i\\}\mathscr{N}_{i}^{\star}\cup\\{i\\}})\sigma_{\min}^{2}(\widetilde{\mathbf{B}}_{i}^{\star}),$
$\displaystyle d_{2}$
$\displaystyle=({s^{\star}+1})\sum_{i=1}^{p}\|\widetilde{\mathbf{B}}_{i}^{\star}\|_{2}^{2}\|\widehat{\bm{\Sigma}}^{m}_{\mathscr{N}_{i}^{\star}\cup\\{i\\}\mathscr{N}_{i}^{\star}\cup\\{i\\}}\|_{2}.$

By Lemma G.4, we have $f$ be $d_{1}$-strongly convex. Under the condition
$N=O(\kappa_{m}^{2}(k_{m}s^{\star}+\log M+\log p))$ event
$\mathcal{E}_{m}=\cap_{i=1}^{p}\mathcal{E}_{m,i}(\mathscr{N}_{i}^{\star}\cup\\{i\\})$
defined in (D.21) holds with probability at least
$1-M^{-1}\exp\\{-k_{m}(s^{\star}+1)\\}$. Applying Lemma I.1 yields
$\sigma_{\min}(\widehat{\bm{\Sigma}}^{m}_{\mathscr{N}_{i}^{\star}\cup\\{i\\}\mathscr{N}_{i}^{\star}\cup\\{i\\}})\geq
2^{-1}\sigma_{\min}(\bm{\Sigma}^{m}_{\mathscr{N}_{i}^{\star}\cup\\{i\\},\mathscr{N}_{i}^{\star}\cup\\{i\\}})$
for $i\in V$ with probability at least
$1-M^{-1}\exp\\{-k_{m}(s^{\star}+1)\\}$. Therefore we have

$\displaystyle({s^{\star}+1})\sum_{i=1}^{p}\sigma_{\min}(\widehat{\bm{\Sigma}}^{m}_{\mathscr{N}_{i}^{\star}\cup\\{i\\}\mathscr{N}_{i}^{\star}\cup\\{i\\}})\sigma_{\min}^{2}(\widetilde{\mathbf{B}}_{i}^{\star})$
$\displaystyle\geq\frac{s^{\star}+1}{2}\sum_{i=1}^{p}\sigma_{\min}(\bm{\Sigma}^{m}_{\mathscr{N}_{i}^{\star}\cup\\{i\\},\mathscr{N}_{i}^{\star}\cup\\{i\\}})\sigma_{\min}^{2}(\widetilde{\mathbf{B}}_{i}^{\star}),$

with probability at least $1-M^{-1}\exp\\{-k_{m}(s^{\star}+1)\\}$. Apply
Assumption 6–7, we can obtain a further lower bound and obtain $\mu$:

$\frac{s^{\star}+1}{2}\sum_{i=1}^{p}\sigma_{\min}(\bm{\Sigma}^{m}_{\mathscr{N}_{i}^{\star}\cup\\{i\\},\mathscr{N}_{i}^{\star}\cup\\{i\\}})\sigma_{\min}^{2}(\widetilde{\mathbf{B}}_{i}^{\star})\geq\frac{(s^{\star}+1)p\nu_{x}\nu_{b}}{2}.$

Next, we want to verify the smoothness condition: $f$ is $d_{2}$-smooth by
Lemma G.4. Apply Lemma I.1 again, with probability at least
$1-M^{-1}\exp\\{-k_{m}(s^{\star}+1)\\}$, we can bound

$\displaystyle({s^{\star}+1})\sum_{i=1}^{p}\|\widetilde{\mathbf{B}}_{i}^{\star}\|_{2}^{2}\|\widehat{\bm{\Sigma}}^{m}_{\mathscr{N}_{i}^{\star}\cup\\{i\\}\mathscr{N}_{i}^{\star}\cup\\{i\\}}\|_{2}$
$\displaystyle\leq\frac{3(s^{\star}+1)}{2}\sum_{i=1}^{p}\sigma_{\max}(\bm{\Sigma}^{m}_{\mathscr{N}_{i}^{\star}\cup\\{i\\},\mathscr{N}_{i}^{\star}\cup\\{i\\}})\|\widetilde{\mathbf{B}}_{i}^{\star}\|_{2}^{2}.$
Finally, apply Assumption 6–7, the above display is bounded as
$\displaystyle\leq\frac{3(s^{\star}+1)p\rho_{x}\rho_{b}}{2}\|{\mathbf{A}^{m}}^{\prime}-{\mathbf{A}^{m}}\|_{F}^{2},$

with probability at least $1-M^{-1}\exp\\{-k_{m}(s^{\star}+1)\\}$. ∎

######  Lemma G.4.

$f(\mathbf{A},\mathbf{B}^{\star})$ is
$(s^{\star}+1)\sum_{i=1}^{p}\sigma_{\min}^{2}(\mathbf{B}_{i}^{\star})\sigma_{\min}(\widehat{\bm{\Sigma}}^{m}_{\mathscr{N}_{i}^{\star}\cup\\{i\\}\mathscr{N}_{i}^{\star}\cup\\{i\\}})$-strongly
convex and
$(s^{\star}+1)\sum_{i=1}^{p}\sigma_{\max}^{2}(\mathbf{B}_{i}^{\star})\sigma_{\max}(\widehat{\bm{\Sigma}}^{m}_{\mathscr{N}_{i}^{\star}\cup\\{i\\}\mathscr{N}_{i}^{\star}\cup\\{i\\}})$-smooth
with respect to ${\mathbf{A}^{m}}$.

###### Proof of Lemma G.4.

To show strong convexity of $f(\mathbf{A},\mathbf{B}^{\star})$, we verify the
following condition. For any ${\mathbf{A}^{m}}^{\prime}\in\mathbb{R}^{k\times
k_{m}}$, we have

$\displaystyle f(\mathbf{A}^{\prime},\mathbf{B}^{\star})\geq
f(\mathbf{A},\mathbf{B}^{\star})+\langle{\nabla_{{\mathbf{A}^{m}}}f(\mathbf{A},\mathbf{B}^{\star})},{{\mathbf{A}^{m}}^{\prime}-{\mathbf{A}^{m}}}\rangle+\frac{\mu}{2}\|{{\mathbf{A}^{m}}^{\prime}-{\mathbf{A}^{m}}}\|_{F}^{2},$

with specific $\mu>0$. We first recall the definition of
$f(\mathbf{A},\mathbf{B}^{\star})$ in (D.1):

$f(\mathbf{A},\mathbf{B}^{\star})=\frac{1}{2N}\sum_{i=1}^{p}\sum_{m=1}^{M}\|\widetilde{\mathbf{B}}_{i}^{\star}(\mathbf{I}_{p}\otimes{\mathbf{A}^{m}})\mathbf{Y}_{m}\|_{F}^{2}.$

Then, we can write

$f(\mathbf{A}^{\prime},\mathbf{B}^{\star})-f(\mathbf{A},\mathbf{B}^{\star})\\\
=\sum_{i=1}^{p}\langle{\widetilde{\mathbf{B}}_{i}^{\star\top}\widetilde{\mathbf{B}}_{i}^{\star}(\mathbf{I}_{p}\otimes{\mathbf{A}^{m}})\widehat{\bm{\Sigma}}^{m}},{\mathbf{I}_{p}\otimes({\mathbf{A}^{m}}^{\prime}-{\mathbf{A}^{m}})}\rangle+\frac{1}{2N}\sum_{i=1}^{p}\|\widetilde{\mathbf{B}}_{i}^{\star}\\{\mathbf{I}_{p}\otimes{({\mathbf{A}^{m}}^{\prime}-{\mathbf{A}^{m}})}\\}\mathbf{Y}^{m}\|_{F}^{2}.$

Then, apply (D.2), the above equation is equivalent as

$f(\mathbf{A}^{\prime},\mathbf{B}^{\star})-f(\mathbf{A},\mathbf{B}^{\star})\\\
=\langle{\nabla_{{\mathbf{A}^{m}}}f(\mathbf{A},\mathbf{B}^{\star})},{{\mathbf{A}^{m}}^{\prime}-{\mathbf{A}^{m}}}\rangle+\frac{1}{2N}\sum_{i=1}^{p}\|\widetilde{\mathbf{B}}_{i}^{\star}\\{\mathbf{I}_{p}\otimes{({\mathbf{A}^{m}}^{\prime}-{\mathbf{A}^{m}})}\\}\mathbf{Y}^{m}\|_{F}^{2}.$
(G.1)

Hence, it suffices to find the lower bound of the second of (G.1) in terms of
$\|{\mathbf{A}^{m}}^{\prime}-{\mathbf{A}^{m}}\|_{F}^{2}$. Recall the
definition of $\mathscr{N}_{i}^{\star}$ in (2.8), and therefore we have
$\widetilde{\mathbf{B}}_{i{\mathscr{N}_{i}^{\star}}^{c}\backslash\\{i\\}}^{\star}={\bf
0}$. Consequently, we can write

$\displaystyle\frac{1}{2N}\sum_{i=1}^{p}\|\widetilde{\mathbf{B}}_{i}^{\star}\\{\mathbf{I}_{p}\otimes{({\mathbf{A}^{m}}^{\prime}-{\mathbf{A}^{m}})}\\}$
$\displaystyle\mathbf{Y}^{m}\|_{F}^{2}$
$\displaystyle=\frac{1}{2N}\sum_{i=1}^{p}\|\widetilde{\mathbf{B}}_{i\mathscr{N}_{i}^{\star}\cup\\{i\\}}^{\star}\\{\mathbf{I}_{|\mathscr{N}_{i}^{\star}|+1}\otimes{({\mathbf{A}^{m}}^{\prime}-{\mathbf{A}^{m}})}\\}\mathbf{Y}^{m}_{\mathscr{N}_{i}^{\star}\cup\\{i\\}}\|_{F}^{2}$
$\displaystyle\geq\frac{s^{\star}+1}{2}\sum_{i=1}^{p}\sigma_{\min}(\widehat{\bm{\Sigma}}^{m}_{\mathscr{N}_{i}^{\star}\cup\\{i\\}\mathscr{N}_{i}^{\star}\cup\\{i\\}})\sigma_{\min}^{2}(\widetilde{\mathbf{B}}_{i}^{\star})\|{\mathbf{A}^{m}}^{\prime}-{\mathbf{A}^{m}}\|_{F}^{2}.$

Next, we want to verify the smoothness condition. We recall the definition
that $f(\mathbf{A},\mathbf{B}^{\star})$ is $L$-smooth with respect to
${\mathbf{A}^{m}}$ if for any ${\mathbf{A}^{m}}^{\prime}$, we have

$\displaystyle f(\mathbf{A}^{\prime},\mathbf{B}^{\star})\leq
f(\mathbf{A},\mathbf{B}^{\star})+\langle{\nabla_{{\mathbf{A}^{m}}}f(\mathbf{A},\mathbf{B}^{\star})},{{\mathbf{A}^{m}}^{\prime}-{\mathbf{A}^{m}}}\rangle+\frac{L}{2}\|{{\mathbf{A}^{m}}^{\prime}-{\mathbf{A}^{m}}}\|_{F}^{2}.$

To find a valid $L$ of the objective function, it suffices to find the upper
bound of the second term in (G.1). Then, using the same proof technique as we
find $\mu$, we have

$\displaystyle\frac{1}{2N}\sum_{i=1}^{p}\|\widetilde{\mathbf{B}}_{i}^{\star}\\{\mathbf{I}_{p}\otimes{({\mathbf{A}^{m}}^{\prime}-{\mathbf{A}^{m}})}\\}$
$\displaystyle\mathbf{Y}^{m}\|_{F}^{2}$
$\displaystyle=\frac{1}{2N}\sum_{i=1}^{p}\|\widetilde{\mathbf{B}}_{i\mathscr{N}_{i}^{\star}\cup\\{i\\}}^{\star}\\{\mathbf{I}_{|\mathscr{N}_{i}^{\star}|+1}\otimes{({\mathbf{A}^{m}}^{\prime}-{\mathbf{A}^{m}})}\\}\mathbf{Y}^{m}_{\mathscr{N}_{i}^{\star}\cup\\{i\\}}\|_{F}^{2}$
$\displaystyle\leq\frac{s^{\star}+1}{2}\sum_{i=1}^{p}\|\widetilde{\mathbf{B}}_{i}^{\star}\|_{2}^{2}\|\widehat{\bm{\Sigma}}^{m}_{\mathscr{N}_{i}^{\star}\cup\\{i\\}\mathscr{N}_{i}^{\star}\cup\\{i\\}}\|_{2}\|{\mathbf{A}^{m}}^{\prime}-{\mathbf{A}^{m}}\|_{F}^{2}.$

We hence complete the proof ∎

######  Lemma G.5.

Assume that Assumption 6 holds and
$N=O(\max_{m=1,\ldots,M}\kappa_{m}^{2}(k_{m}s^{\star}+\log M))$, where
$\kappa_{m}=\sigma_{\max}(\bm{\Sigma}^{m})/\sigma_{\min}(\bm{\Sigma}^{m})$.
Then, $h_{i}(\mathbf{B})$ is
$\min_{m=1,\ldots,M}2^{-1}\nu_{x}\sigma_{\min}^{2}({\mathbf{A}^{m}})$-strongly
convex with respect to $\mathbf{B}_{i}$ with probability at least
$1-\max_{m=1,\ldots,M}\exp(-k_{m}s^{\star})$.

###### Proof of Lemma G.5.

We can write $h_{i}(\mathbf{B}_{i}+\Delta)$ as

$h_{i}(\mathbf{B}_{i}+\Delta)=h_{i}(\mathbf{B}_{i})+2\langle{\nabla_{\mathbf{B}_{i}}h_{i}(\mathbf{B}_{i})},{\Delta}\rangle+\frac{1}{2N}\sum_{m=1}^{M}\frac{1}{M}\|\Delta(\mathbf{I}_{p-1}\otimes{{\mathbf{A}^{m}}}){\mathbf{Y}_{\backslash\\{i\\}}^{m}}\|_{F}^{2}.$

We can lower bound the last term of the above display as

$\displaystyle\min_{m=1,\ldots,M}\frac{1}{2N}$
$\displaystyle\|\Delta(\mathbf{I}_{p-1}\otimes{{\mathbf{A}^{m}}}){\mathbf{Y}_{\backslash\\{i\\}}^{m}}\|_{F}^{2}.$
$\displaystyle=\min_{m=1,\ldots,M}\frac{1}{2N}\|\Delta(\mathbf{I}_{|\mathscr{N}_{i}^{\star}|}\otimes{{\mathbf{A}^{m}}}){\mathbf{Y}_{\mathscr{N}_{i}^{\star}}^{m}}\|_{F}^{2}+\frac{1}{2N}\|\Delta(\mathbf{I}_{|{\mathscr{N}_{i}^{\star}}^{c}|-1}\otimes{{\mathbf{A}^{m}}}){\mathbf{Y}_{{\mathscr{N}_{i}^{\star}}^{c}\backslash\\{i\\}}^{m}}\|_{F}^{2}$
$\displaystyle\geq\min_{m=1,\ldots,M}\frac{1}{2N}\|\Delta(\mathbf{I}_{|\mathscr{N}_{i}^{\star}|}\otimes{{\mathbf{A}^{m}}}){\mathbf{Y}_{\mathscr{N}_{i}^{\star}}^{m}}\|_{F}^{2}$
$\displaystyle\geq\min_{m=1,\ldots,M}\frac{1}{2}\sigma_{\min}^{2}({\mathbf{A}^{m}})\sigma_{\min}(\widehat{\bm{\Sigma}}^{m}_{\mathscr{N}_{i}^{\star}\mathscr{N}_{i}^{\star}})\|\Delta\|_{F}^{2}$
Under the condition $N=O(\max_{m=1,\ldots,M}\kappa_{m}^{2}(k_{m}s^{\star}+\log
M))$ and Assumption 6, we can apply Lemma I.1 and obtain that
$\min_{m=1,\ldots,M}\sigma_{\min}(\widehat{\bm{\Sigma}}^{m}_{\mathscr{N}_{i}^{\star}\mathscr{N}_{i}^{\star}})\geq\nu_{x}/2$
with probability at least $1-\max_{m=1,\ldots,M}\exp(-k_{m}s^{\star})$. Then,
the above display is upper bounded as
$\displaystyle\geq\min_{m=1,\ldots,M}\frac{\nu_{x}}{2}\sigma_{\min}^{2}({\mathbf{A}^{m}})\|\Delta\|_{F}^{2},$

with probability at least $1-\max_{m=1,\ldots,M}\exp(-k_{m}s^{\star})$. Here
we complete the proof. ∎

##  Appendix H Projection coefficients

In this section, we show the expansion coefficients resulted from projection
to non-convex sets. Lemma H.1 discusses coefficient of the general condition
of projection to $\mathcal{K}_{m}(\tau_{1},\tau_{2})$ and Lemma H.3–H.4
discuss the coefficients of projection to $\mathcal{K}_{B}(s,\alpha)$.

######  Lemma H.1.

Let $\mathcal{K}(\tau_{1},\tau_{2})=\\{\mathbf{X}\in\mathbb{R}^{p\times
d}:\tau_{1}\leq\|\mathbf{X}_{i,\cdot}\|_{2}\leq\tau_{2},i=1,\ldots,p\\}$ and
$\mathcal{P}_{\tau}$ be the projection operator that projects $\mathbf{X}$ to
$\mathcal{K}(\tau_{1},\tau_{2})$. Then, for any
$\mathbf{Y}\in\mathcal{K}(\tau_{1},\tau_{2})$, we have

$\|\mathcal{P}_{\tau}(\mathbf{X})-\mathbf{Y}\|_{F}\leq
2\|\mathbf{X}-\mathbf{Y}\|_{F}.$

###### Proof.

First, we consider that there is only single row in $\mathbf{X}$ and hence we
can directly apply the result of Lemma H.2. The generalization to $p$ rows,
with $p>1$, follows similarly:

$\displaystyle\|\mathcal{P}_{\tau}(\mathbf{X})-\mathbf{Y}\|_{F}^{2}=\sum_{j=1}^{p}\|\widetilde{\mathcal{P}}_{\tau}(\mathbf{x}_{j})-\mathbf{y}_{j}\|_{2}^{2}\leq