$\displaystyle\sqrt{2/\pi}n\frac{\|{\mathbf{M}}_{1}-{\mathbf{M}}\|_{\mathrm{F}}^{2}+2\langle{\mathbf{M}}-{\mathbf{M}}^{*},{\mathbf{M}}_{1}-{\mathbf{M}}\rangle}{\sqrt{\sigma^{2}+\|{\mathbf{M}}_{1}-{\mathbf{M}}^{*}\|_{\mathrm{F}}^{2}}+\sqrt{\sigma^{2}+\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\mathrm{F}}^{2}}}$
$\displaystyle\leq$
$\displaystyle\sqrt{2/\pi}\frac{n}{\sigma}\left(\|{\mathbf{M}}_{1}-{\mathbf{M}}\|_{\mathrm{F}}^{2}+2\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\mathrm{F}}\|{\mathbf{M}}_{1}-{\mathbf{M}}\|_{\mathrm{F}}\right),$

where the first equality comes from Lemma 17. And from Theorem 10, we have

$\displaystyle f({\mathbf{M}}_{1})-f({\mathbf{M}})\leq$
$\displaystyle{\mathbb{E}}f({\mathbf{M}}_{1})-{\mathbb{E}}f({\mathbf{M}})+C_{1}\sqrt{nd_{1}r}(\|{\mathbf{M}}_{1}-{\mathbf{M}}^{*}\|_{\mathrm{F}}+\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\mathrm{F}})$
$\displaystyle\leq$
$\displaystyle{\mathbb{E}}f({\mathbf{M}}_{1})-{\mathbb{E}}f({\mathbf{M}})+C_{1}\frac{n}{\sigma}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\mathrm{F}}(2\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\mathrm{F}}+\|{\mathbf{M}}_{1}-{\mathbf{M}}\|_{\mathrm{F}})$
$\displaystyle\leq$
$\displaystyle\frac{n}{\sigma}\|{\mathbf{M}}_{1}-{\mathbf{M}}\|_{\mathrm{F}}^{2}+(2+C_{1})\frac{n}{\sigma}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\mathrm{F}}\|{\mathbf{M}}_{1}-{\mathbf{M}}\|_{\mathrm{F}}+2C_{1}\frac{n}{\sigma}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\mathrm{F}}^{2},$

where the second inequality is from the condition
$\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}\geq\sqrt{\frac{d_{1}r}{n}}\sigma$.
Since
${\mathbf{M}}_{1}={\mathbf{M}}+\frac{\sigma}{2n}\text{SVD}_{r}({\mathbf{G}})$,
we have

$\begin{split}f({\mathbf{M}}+\frac{\sigma}{2n}\text{SVD}_{r}({\mathbf{G}}))&-f({\mathbf{M}})\\\
&\leq\frac{\sigma}{4n}\|{\mathbf{G}}\|_{\mathrm{F,r}}^{2}+(1+C_{1}/2)\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\mathrm{F}}\|{\mathbf{G}}\|_{\mathrm{F,r}}+2C_{1}\frac{n}{\sigma}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\mathrm{F}}^{2}.\end{split}$
(17)

On the other hand, by the definition of sub-gradient, we have

$\displaystyle
f({\mathbf{M}}+\frac{\sigma}{2n}\text{SVD}_{r}({\mathbf{G}}))-f({\mathbf{M}})\geq\frac{\sigma}{2n}\|{\mathbf{G}}\|_{\rm{F},r}^{2}.$
(18)

Combine Equation 17 with Equation 18 and by solving the quadratic inequality
we get

$\|{\mathbf{G}}\|_{\rm{F},r}\leq
Cn\sigma^{-1}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}.$

∎

###  B.2 Proof of absolute value loss with heavy-tailed noise Lemma 2

The $L_{\textsf{\tiny comp}}=2n$ proof is the same as the one given in Section
B.1. Now we focus on lower bound of $f({\mathbf{M}})-f({\mathbf{M}}^{*})$.

First consider phase one when $\|{\mathbf{X}}-{\mathbf{X}}^{*}\|_{\rm{F}}\geq
30{\mathbb{E}}|\xi|=30\gamma$. Use triangle inequality and then get

$\displaystyle f(\mathbf{M})-f(\mathbf{M}^{*})$
$\displaystyle=\sum_{i=1}^{n}|\xi_{i}-\langle{\mathbf{M}}-{\mathbf{M}}^{*},{\mathbf{X}}_{i}\rangle|-\sum_{i=1}^{n}|\xi_{i}|\geq\sum_{i=1}^{n}|\langle{\mathbf{M}}-{\mathbf{M}}^{*},{\mathbf{X}}_{i}\rangle|-2\|\boldsymbol{\xi}\|_{1}.$
(19)

Corollary 2 proves
$\sum_{i=1}^{n}|\langle{\mathbf{M}}-{\mathbf{M}}^{*},{\mathbf{X}}_{i}\rangle|\geq\sqrt{1/2\pi}n\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}$
and Lemma 18 proves with probability over
$1-{}^{*}\\!c_{1}n^{-\min\\{1,\varepsilon\\}}$,
$\frac{1}{n}\|\boldsymbol{\xi}\|_{1}\leq 3{\mathbb{E}}|\xi|=3\gamma$. Then
combined with $\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}\geq 30\gamma$,
Equation 19 could be further bounded with

$\displaystyle
f(\mathbf{M})-f(\mathbf{M}^{*})\geq\sqrt{1/2\pi}n\|\mathbf{M}-\mathbf{M}^{*}\|_{\mathrm{F}}-6n\gamma\geq\frac{n}{6}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}},$

which verifies $\mu_{\textsf{\tiny comp}}=\frac{n}{6}$.

Then consider the second phase when
$C_{2}\sqrt{d_{1}r/n}b_{0}\leq\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}<30\gamma$.
To bound expectation of $f({\mathbf{M}})-f({\mathbf{M}}^{*})$, we first
consider the conditional expectation
${\mathbb{E}}_{\xi}f({\mathbf{M}})-{\mathbb{E}}_{\xi}f({\mathbf{M}}^{*})$.
Notice for all $t_{0}\in{\mathbb{R}}$,

$\displaystyle{\mathbb{E}}|\xi-t_{0}|$ $\displaystyle=\int_{s\geq
t_{0}}(s-t_{0})dH_{\xi}(s)+\int_{s<t_{0}}(t_{0}-s)dH_{\xi}(s)$
$\displaystyle=2\int_{s\geq
t_{0}}(s-t_{0})dH_{\xi}(s)+\int_{-\infty}^{+\infty}(t_{0}-s)dH_{\xi}(s)$
$\displaystyle=2\int_{s\geq
t_{0}}(1-H_{\xi}(s))ds+t_{0}-\int_{-\infty}^{\infty}sdH_{\xi}(s).$

Set $t_{0}=\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle$ and
define
$g_{{\mathbf{X}}_{i}}({\mathbf{M}}):={\mathbb{E}}_{\xi_{i}}|\xi_{i}-\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle|$.
It implies

$\displaystyle
g_{{\mathbf{X}}_{i}}({\mathbf{M}})=2\int_{s\geq\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle}(1-H_{\xi}(s))ds+\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle-\int_{-\infty}^{+\infty}sdH_{\xi}(s).$

This leads to

$\displaystyle
g_{{\mathbf{X}}_{i}}({\mathbf{M}})-g_{{\mathbf{X}}_{i}}({\mathbf{M}}^{*})=2\int_{0}^{\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle}H_{\xi}(s)ds-\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle.$
(20)

Note that
$\langle\mathbf{X}_{i},\mathbf{M}-\mathbf{M}^{*}\rangle\sim\mathcal{N}(0,\|\mathbf{M}-\mathbf{M}^{*}\|_{\mathrm{F}}^{2})$
and denote $z:=\langle\mathbf{X}_{i},\mathbf{M}-\mathbf{M}^{*}\rangle$. Let
$f_{z}(\cdot)$ be the density of $z$. Take expectation of $z$ on both sides of
Equation 20

$\displaystyle\mathbb{E}\left[g_{\mathbf{X}_{i}}(\mathbf{M})-g_{\mathbf{X}_{i}}(\mathbf{M}^{*})\right]$
$\displaystyle=2\int_{-\infty}^{+\infty}\int_{0}^{t}\left(H_{\xi}(s)-0.5\right)f_{z}(t)\,ds\,dz$
$\displaystyle=2\int_{-\infty}^{+\infty}\int_{0}^{t}\int_{0}^{s}h_{\xi}(w)f_{z}(t)\,dw\,ds\,dt$
$\displaystyle\geq
2\int_{-\|\mathbf{M}-\mathbf{M}^{*}\|_{\mathrm{F}}}^{\|\mathbf{M}-\mathbf{M}^{*}\|_{\mathrm{F}}}\int_{0}^{t}f_{z}(t)b_{0}^{-1}s\,ds\,dt$
$\displaystyle=b_{0}^{-1}\int_{-\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}}^{\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}}t^{2}f_{z}(t)\,dt=b_{0}^{-1}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}^{2}\int_{-1}^{1}t^{2}\cdot\frac{1}{\sqrt{2\pi}}e^{-t^{2}/2}\,dt$
$\displaystyle\geq\frac{1}{6b_{0}}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}^{2},$

where the first inequality follows from Assumption 2 and the last is from
$\int_{-1}^{1}t^{2}\cdot\frac{1}{\sqrt{2\pi}}e^{-t^{2}/2}\,dt\geq 1/6$.
Therefore,

$\displaystyle{\mathbb{E}}f({\mathbf{M}})-{\mathbb{E}}f({\mathbf{M}}^{*})=\sum_{i=1}^{n}{\mathbb{E}}g_{{\mathbf{X}}_{i}}({\mathbf{M}})-g_{{\mathbf{X}}_{i}}({\mathbf{M}}^{*})\geq\frac{n}{6b_{0}}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}^{2}.$

Invoke Theorem 10,

$\displaystyle f({\mathbf{M}})-f({\mathbf{M}}^{*})$
$\displaystyle\geq{\mathbb{E}}[f({\mathbf{M}})-f({\mathbf{M}}^{*})]-C\sqrt{nd_{1}r}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}$
$\displaystyle\geq\frac{n}{6b_{0}}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}^{2}-C\sqrt{nd_{1}r}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}$
$\displaystyle\geq\frac{n}{12b_{0}}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}^{2},$

where the last inequality uses $\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}\geq
C_{2}\sqrt{d_{1}r/n}b_{0}$. This proves $\mu_{\textsf{\tiny
stat}}=\frac{n}{12b_{0}}$.

Finally, from the following lemma, we see that $L_{\textsf{\tiny stat}}\leq
C_{3}nb_{1}^{-1}$. And this finishes the proof.

######  Lemma 8 (Upper bound for sub-gradient).

Let ${\mathbf{M}}\in{\mathbb{R}}^{d_{1}\times d_{2}}$ be rank at most $r$
matrix such that $\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}\geq
C_{2}\sqrt{\frac{d_{1}r}{n}}b_{1}$. Let ${\mathbf{G}}\in\partial
f({\mathbf{M}})$ be the sub-gradient. Under the event
${\boldsymbol{\mathcal{E}}}=\\{\sup_{{\mathbf{M}},{\mathbf{M}}_{1}\in{\mathbb{M}}_{r}}|f({\mathbf{M}}+{\mathbf{M}}_{1})-f({\mathbf{M}})-{\mathbb{E}}(f({\mathbf{M}}+{\mathbf{M}}_{1})-f({\mathbf{M}}))|\cdot\|{\mathbf{M}}_{1}\|_{\rm{F}}^{-1}\leq
C_{1}\sqrt{nd_{1}r}\\}$, we have $\|{\mathbf{G}}\|_{\rm{F},r}\leq
C_{3}nb_{1}^{-1}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}$ for some absolute
constant $C_{3}>0$.

###### Proof.

Take
${\mathbf{M}}_{1}={\mathbf{M}}+\frac{b_{1}}{2n}\text{SVD}_{r}({\mathbf{G}})$,
where $\text{SVD}_{r}({\mathbf{G}})$ is the best rank $r$ approximation of
${\mathbf{G}}$ and then $\text{rank}({\mathbf{M}}_{1})\leq 2r$. We finish the
proof via combining lower bound and upper bound of
$f({\mathbf{M}}_{1})-f({\mathbf{M}})$. First consider
${\mathbb{E}}f({\mathbf{M}}_{1})-{\mathbb{E}}f({\mathbf{M}})$. Use the same
notation as the above proof and similarly,

$\displaystyle
g_{{\mathbf{X}}_{i}}({\mathbf{M}}_{1})-g_{{\mathbf{X}}_{i}}({\mathbf{M}})=$
$\displaystyle
2\int_{\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle}^{\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle+\langle{\mathbf{X}}_{i},{\mathbf{M}}_{1}-{\mathbf{M}}\rangle}\int_{0}^{\xi}h_{\xi}(x)\,dx\,d\xi$
$\displaystyle\leq$ $\displaystyle
2b_{1}^{-1}\int_{\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle}^{\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle+\langle{\mathbf{X}}_{i},{\mathbf{M}}_{1}-{\mathbf{M}}\rangle}\xi\,d\xi$
$\displaystyle=$ $\displaystyle
b_{1}^{-1}\left[(\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle+\langle{\mathbf{X}}_{i},{\mathbf{M}}_{1}-{\mathbf{M}}\rangle)^{2}-(\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle)^{2}\right],$

where the inequality follows from the upper bound for $h_{\xi}(x)$. Then take
expectation on each side and sum up over $i$ :

$\displaystyle{\mathbb{E}}f({\mathbf{M}}_{1})-{\mathbb{E}}f({\mathbf{M}})=$
$\displaystyle\sum_{i=1}^{n}{\mathbb{E}}[g_{{\mathbf{X}}_{i}}({\mathbf{M}}_{1})-g_{{\mathbf{X}}_{i}}({\mathbf{M}})]$
$\displaystyle\leq$ $\displaystyle
nb_{1}^{-1}{\mathbb{E}}\left[(\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle+\langle{\mathbf{X}}_{i},{\mathbf{M}}_{1}-{\mathbf{M}}\rangle)^{2}-(\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle)^{2}\right]$
$\displaystyle\leq$ $\displaystyle
nb_{1}^{-1}\left[\|{\mathbf{M}}_{1}-{\mathbf{M}}\|_{\mathrm{F}}^{2}+2\|{\mathbf{M}}_{1}-{\mathbf{M}}\|_{\mathrm{F}}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\mathrm{F}}\right]$

Bound $f({\mathbf{M}}_{1})-f({\mathbf{M}})$ using Corollary 1:

$\displaystyle f({\mathbf{M}}_{1})-f({\mathbf{M}})\leq$
$\displaystyle{\mathbb{E}}f({\mathbf{M}}_{1})-{\mathbb{E}}f({\mathbf{M}})+C_{1}\sqrt{nd_{1}r}(\|{\mathbf{M}}_{1}-{\mathbf{M}}^{*}\|_{\mathrm{F}}+\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\mathrm{F}})$
$\displaystyle\leq$
$\displaystyle{\mathbb{E}}f({\mathbf{M}}_{1})-{\mathbb{E}}f({\mathbf{M}})+C_{3}nb_{1}^{-1}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\mathrm{F}}(2\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\mathrm{F}}+\|{\mathbf{M}}_{1}-{\mathbf{M}}\|_{\mathrm{F}})$
$\displaystyle\leq$ $\displaystyle
nb_{1}^{-1}\|{\mathbf{M}}_{1}-{\mathbf{M}}\|_{\mathrm{F}}^{2}+(2+C_{3})nb_{1}^{-1}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\mathrm{F}}\|{\mathbf{M}}_{1}-{\mathbf{M}}\|_{\mathrm{F}}+2C_{3}nb_{1}^{-1}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\mathrm{F}}^{2},$

where the second inequality is from the condition
$\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}\geq
C_{2}\sqrt{\frac{d_{1}r}{n}}b_{1}$. Since
${\mathbf{M}}_{1}={\mathbf{M}}+\frac{b_{1}}{2n}\text{SVD}_{r}({\mathbf{G}})$,
it becomes

$\begin{split}f({\mathbf{M}}+\frac{b_{1}}{2n}\text{SVD}_{r}({\mathbf{G}}))&-f({\mathbf{M}})\\\
&\leq\frac{b_{1}}{4n}\|{\mathbf{G}}\|_{\mathrm{F,r}}^{2}+(1+C_{1}/2)\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\mathrm{F}}\|{\mathbf{G}}\|_{\mathrm{F,r}}+2C_{1}\frac{n}{b_{1}}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\mathrm{F}}^{2}.\end{split}$
(21)

On the other hand, by the definition of sub-gradient,
$f({\mathbf{M}}_{1})-f({\mathbf{M}})$ has lower bound

$\displaystyle
f({\mathbf{M}}+\frac{b_{1}}{2n}\text{SVD}_{r}({\mathbf{G}}))-f({\mathbf{M}})\geq\frac{b_{1}}{2n}\|{\mathbf{G}}\|_{\rm{F},r}^{2}.$
(22)

Combine Equation 21 with Equation 22 and then solve the quadratic inequality
which leads to

$\|{\mathbf{G}}\|_{\rm{F},r}\leq
C_{3}nb_{1}^{-1}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}.$

∎

###  B.3 Proof of Huber loss with heavy-tailed noise Lemma 3

First consider upper bound of sug-gradient ${\mathbf{G}}\in f({\mathbf{M}})$,
where matrix ${\mathbf{M}}$ has rank at most $r$. We have

$\displaystyle|f({\mathbf{M}}+\text{SVD}_{r}({\mathbf{G}}))-f({\mathbf{M}})|$
$\displaystyle=|\sum_{i=1}^{n}\rho_{H,\delta}(\xi_{i}-\langle{\mathbf{X}}_{i},{\mathbf{M}}+\text{SVD}_{r}({\mathbf{G}})\rangle)-\rho_{H,\delta}(\xi_{i}-\langle{\mathbf{X}}_{i},{\mathbf{M}}\rangle)|$
$\displaystyle\leq\sum_{i=1}^{n}2\delta|\langle{\mathbf{X}}_{i},\text{SVD}_{r}({\mathbf{G}})\rangle\leq
4\delta n\|{\mathbf{G}}\|_{\rm{F},r},$

where the last line comes from Corollary 2. Note that it implies
$L_{\textsf{\tiny comp}}=4\delta n$ and the reason has been stated in Section
B.1.

Then consider the lower bound. Use the inequality
$2\delta|x|-\delta^{2}\leq\rho_{H,\delta}(x)\leq 2\delta|x|$ and then we have

$\displaystyle f({\mathbf{M}})-f({\mathbf{M}}^{*})$
$\displaystyle=\sum_{i=1}^{n}\rho_{H,\delta}(\xi_{i}-\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle)-\rho_{H,\delta}(\xi_{i})$
$\displaystyle\geq
2\delta\sum_{i=1}^{n}(|\xi_{i}-\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle|-|\xi_{i}|)-n\delta^{2}$
$\displaystyle\geq\delta\sqrt{2/\pi}n\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}-4\delta\|\boldsymbol{\xi}\|_{1}-n\delta^{2},$

where the last inequality comes from Corollary 2. Also, Lemma 18 proves with
high probability $\frac{1}{n}\|\boldsymbol{\xi}\|_{1}\leq
3{\mathbb{E}}|\xi|=3\gamma$, which implies

$\displaystyle
f({\mathbf{M}})-f({\mathbf{M}}^{*})\geq\delta\sqrt{2/\pi}n\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}-12\delta
n\gamma-n\delta^{2}.$

Therefore when $\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}\geq
24\gamma+2\delta$, we have
$f({\mathbf{M}})-f({\mathbf{M}}^{*})\geq\frac{\delta
n}{4}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}$. It shows with
$\tau_{\textsf{\tiny comp}}=24\gamma+2\delta$ we have $\mu_{\textsf{\tiny
comp}}=\delta n/4$.

Now consider the second phase. First take expectation against $\xi$ and define
$g_{{\mathbf{X}}_{i}}({\mathbf{M}}):={\mathbb{E}}_{\xi}[\rho_{H,\delta}(\xi_{i}-\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle)]$.
Denote $z=\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle$. Then
with a little abuse of notation, define

$\displaystyle g(z)$
$\displaystyle:=2\delta\int_{\delta+z}^{+\infty}(x-z)\,dH_{\xi}(x)+2\delta\int_{-\infty}^{z-\delta}(z-x)dH_{\xi}(x)+\int_{z-\delta}^{z+\delta}\left(z-x\right)^{2}dH_{\xi}(x)$
(23) $\displaystyle=g_{{\mathbf{X}}_{i}}({\mathbf{M}}).$ (24)

Then simple computation shows

$\displaystyle g^{\prime}(z)$
$\displaystyle=2\int_{z-\delta}^{z+\delta}H_{\xi}(x)dx-2\delta,$
$\displaystyle g^{\prime\prime}(z)$
$\displaystyle=2(H_{\xi}(z+\delta)-H_{\xi}(z-\delta)).$

Assumption 3 guarantees $g^{\prime}(0)=0$. Therefore the Taylor expansion at
$0$ is

$\displaystyle
g(z)=g(0)+2\int_{0}^{z}(H_{\xi}(y+\delta)-H_{\xi}(y-\delta))y\,dy.$

Notice $z=\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle\sim
N(0,\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}^{2})$ and denote its density by
$f_{z}(\cdot)$. Take expectation w.r.t. $z$ and we have

$\displaystyle{\mathbb{E}}g(z)-{\mathbb{E}}g(0)$
$\displaystyle=2\int_{-\infty}^{\infty}\int_{0}^{t}(H_{\xi}(y+\delta)-H_{\xi}(y-\delta))yf_{z}(t)\,dy\,dt$
$\displaystyle\geq
2\int_{-\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}}^{\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}}\int_{0}^{t}f_{z}(t)(H_{\xi}(y+\delta)-H_{\xi}(y-\delta))y\,dy\,dt$
$\displaystyle\geq 4\delta
b_{0}^{-1}\int_{-\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}}^{\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}}t^{2}f_{z}(t)\,dt=4\delta
b_{0}^{-1}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}^{2}\int_{-1}^{1}t^{2}\frac{1}{\sqrt{2\pi}}\exp(-t^{2}/2)\,dt$
$\displaystyle\geq\frac{2}{3}\delta
b_{0}^{-1}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}^{2},$

where the second inequality uses $H_{\xi}(y+\delta)-H_{\xi}(y-\delta)\geq
2\delta b_{0}^{-1}$ when $y\leq\tau_{\textsf{\tiny comp}}$. And this implies

${\mathbb{E}}f({\mathbf{M}})-{\mathbb{E}}f({\mathbf{M}}^{*})=n\left({\mathbb{E}}g(z)-{\mathbb{E}}g(0)\right)\geq
2\delta nb_{0}^{-1}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}^{2}.$

And together with Theorem 10, we have

$\displaystyle f({\mathbf{M}})-f({\mathbf{M}}^{*})$
$\displaystyle\geq{\mathbb{E}}[f({\mathbf{M}})-f({\mathbf{M}}^{*})]-(C_{2}+C_{3}\delta)\sqrt{nd_{1}r}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}.$

And thus when $\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}\geq
b_{0}\frac{C_{2}+C_{3}\delta}{\delta}\sqrt{d_{1}r/n}$, we have

$f({\mathbf{M}})-f({\mathbf{M}}^{*})\geq\frac{1}{3}\delta
nb_{0}^{-1}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}^{2}.$

It proves with $\tau_{\textsf{\tiny
stat}}=b_{0}\frac{C_{2}+C_{3}\delta}{\delta}\sqrt{d_{1}r/n}$ it has
$\mu_{\textsf{\tiny stat}}=\frac{1}{3}\delta nb_{0}^{-1}$.

And the bound for $L_{\textsf{\tiny stat}}$ is given as follows.

######  Lemma 9 (Upper bound for sub-gradient).

Let ${\mathbf{M}}\in{\mathbb{R}}^{d_{1}\times d_{2}}$ be rank at most $r$
matrix and satisfy $\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}\geq
c\sqrt{d_{1}r/n}b_{0}$. Let ${\mathbf{G}}\in\partial f({\mathbf{M}})$ be the
sub-gradient. Under the event
${\boldsymbol{\mathcal{E}}}=\\{\sup_{{\mathbf{M}},{\mathbf{M}}_{1}\in{\mathbb{M}}_{r}}|f({\mathbf{M}}+{\mathbf{M}}_{1})-f({\mathbf{M}})-{\mathbb{E}}(f({\mathbf{M}}+{\mathbf{M}}_{1})-f({\mathbf{M}}))|\cdot\|{\mathbf{M}}_{1}\|_{\rm{F}}^{-1}\leq
C_{1}\sqrt{nd_{1}r}\\}$, we have $\|{\mathbf{G}}\|_{\rm{F},r}\leq
C_{\delta}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}$ for
$C_{\delta}=C_{1}+C_{2}\delta$ and some absolute constant $C_{1},C_{2}>0$.

###### Proof.

Take
${\mathbf{M}}_{1}={\mathbf{M}}+\frac{b_{1}}{4n\delta}\text{SVD}_{r}({\mathbf{G}})$.
First consider ${\mathbb{E}}f({\mathbf{M}}_{1})-{\mathbb{E}}f({\mathbf{M}})$.
Continue from Equation 23,

$\displaystyle~{}~{}~{}~{}{\mathbb{E}}_{\xi}\left[\rho_{H,\delta}(\xi_{i}-\langle{\mathbf{X}}_{i},{\mathbf{M}}_{1}-{\mathbf{M}}^{*}\rangle)\right]-{\mathbb{E}}_{\xi}\left[\rho_{H,\delta}(\xi_{i}-\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle)\right]$
$\displaystyle=2\int_{\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle}^{\langle{\mathbf{X}}_{i},{\mathbf{M}}_{1}-{\mathbf{M}}^{*}\rangle}[H_{\xi}(y+\delta)-H_{\xi}(y-\delta)]y\,dy$
$\displaystyle\leq 4\delta
b_{1}^{-1}\int_{\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle}^{\langle{\mathbf{X}}_{i},{\mathbf{M}}_{1}-{\mathbf{M}}^{*}\rangle}y\,dy$
$\displaystyle=2\delta
b_{1}^{-1}[\langle{\mathbf{X}}_{i},{\mathbf{M}}_{1}-{\mathbf{M}}\rangle^{2}+2\langle{\mathbf{X}}_{i},{\mathbf{M}}_{1}-{\mathbf{M}}\rangle\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle].$

Take expectation on each side and sum up ove $i$:

$\displaystyle{\mathbb{E}}f({\mathbf{M}}_{1})-{\mathbb{E}}f({\mathbf{M}})$
$\displaystyle=n\left({\mathbb{E}}_{\xi}\left[\rho_{H,\delta}(\xi_{i}-\langle{\mathbf{X}}_{i},{\mathbf{M}}_{1}-{\mathbf{M}}^{*}\rangle)\right]-{\mathbb{E}}_{\xi}\left[\rho_{H,\delta}(\xi_{i}-\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle)\right]\right)$
$\displaystyle\leq 2\delta
nb_{1}^{-1}[\|{\mathbf{M}}_{1}-{\mathbf{M}}\|_{\rm{F}}^{2}+2\|{\mathbf{M}}_{1}-{\mathbf{M}}\|_{\rm{F}}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}].$

Then invoke Crorllary 1 and bound $f({\mathbf{M}}_{1})-f({\mathbf{M}})$:

$\displaystyle{~{}~{}~{}~{}}f({\mathbf{M}}_{1})-f({\mathbf{M}})$
$\displaystyle\leq{\mathbb{E}}f({\mathbf{M}}_{1})-{\mathbb{E}}f({\mathbf{M}})+C_{\delta}\sqrt{nd_{1}r}(\|{\mathbf{M}}_{1}-{\mathbf{M}}^{*}\|_{\rm{F}}+\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}})$
$\displaystyle\leq 2\delta
nb_{1}^{-1}\|{\mathbf{M}}_{1}-{\mathbf{M}}\|_{\rm{F}}^{2}+\delta
nb_{1}^{-1}\|{\mathbf{M}}_{1}-{\mathbf{M}}\|_{\rm{F}}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}+C_{\delta}\sqrt{nd_{1}r}(\|{\mathbf{M}}_{1}-{\mathbf{M}}\|_{\rm{F}}+2\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}})$
$\displaystyle\leq 2\delta
nb_{1}^{-1}\|{\mathbf{M}}_{1}-{\mathbf{M}}\|_{\rm{F}}^{2}+c_{\delta}nb_{1}^{-1}\|{\mathbf{M}}_{1}-{\mathbf{M}}\|_{\rm{F}}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}+C_{\delta}nb_{1}^{-1}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}^{2},$

where the last inequality uses
$\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}\geq\sqrt{d_{1}r/n}b_{1}$. Insert
${\mathbf{M}}_{1}={\mathbf{M}}+\frac{b_{1}}{4n\delta}\text{SVD}_{r}({\mathbf{G}})$
and then it is

$\displaystyle
f({\mathbf{M}}_{1})-f({\mathbf{M}})\leq\frac{b_{1}}{8n\delta}\|{\mathbf{G}}\|_{\rm{F},r}^{2}+\frac{c_{\delta}}{4\delta}\|{\mathbf{G}}\|_{\rm{F},r}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}+\frac{C_{\delta}n}{b_{1}}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}^{2}.$
(25)

On the other hand, from the definition of the sub-gradient, we have

$\displaystyle
f({\mathbf{M}}_{1})-f({\mathbf{M}})=f({\mathbf{M}}+\frac{b_{1}}{4n\delta}\text{SVD}_{r}({\mathbf{G}}))-f({\mathbf{M}})\geq\frac{b_{1}}{4n\delta}\|{\mathbf{G}}\|_{\rm{F},r}^{2}.$
(26)

Combine Equation 25 with Equation 26 and then the quadratic inequality of
$\|{\mathbf{G}}\|_{\rm{F},r}$ gives

$\|{\mathbf{G}}\|_{\rm{F},r}\leq
C_{\delta}nb_{1}^{-1}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}.$

∎

###  B.4 Proof of quantile loss with heavy-tailed noise Lemma 4

Notice that quantile loss function $\rho_{Q,\delta}(\cdot)$ is Lipschitz
continuous with $\max\\{\delta,1-\delta\\}$. First consider upper bound of
sug-gradient ${\mathbf{G}}\in f({\mathbf{M}})$, where matrix ${\mathbf{M}}$
has rank at most $r$. We have

$\displaystyle|f({\mathbf{M}}+\text{SVD}_{r}({\mathbf{G}}))-f({\mathbf{M}})|$
$\displaystyle=|\sum_{i=1}^{n}\rho_{Q,\delta}(\xi_{i}-\langle{\mathbf{X}}_{i},{\mathbf{M}}+\text{SVD}_{r}({\mathbf{G}})\rangle)-\rho_{Q,\delta}(\xi_{i}-\langle{\mathbf{X}}_{i},{\mathbf{M}}\rangle)|$
$\displaystyle\leq\sum_{i=1}^{n}\max\\{\delta,1-\delta\\}|\langle{\mathbf{X}}_{i},\text{SVD}_{r}({\mathbf{G}})\rangle|$
$\displaystyle\leq 2\max\\{\delta,1-\delta\\}n\|{\mathbf{G}}\|_{\rm{F},r},$

where the last line comes from Corollary 2. Note that it verifies
$L_{\textsf{\tiny comp}}=2\max\\{\delta,1-\delta\\}n$ and its proof is same as
Section B.1.

Then consider the lower bound. Notice that quantile loss function satisfies
triangle inequality,
$\rho_{Q,\delta}(x_{1}+x_{2})\leq\rho_{Q,\delta}(x_{1})+\rho_{Q,\delta}(x_{2})$
and then it has

$\displaystyle f({\mathbf{M}})-f({\mathbf{M}}^{*})$
$\displaystyle=\sum_{i=1}^{n}\rho_{Q,\delta}(\xi_{i}-\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle)-\rho_{Q,\delta}(\xi_{i})$
$\displaystyle\geq\sum_{i=1}^{n}\rho_{Q,\delta}(-\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle)-\rho_{Q,\delta}(\xi_{i})-\rho_{Q,\delta}(-\xi_{i})$
$\displaystyle\geq\min\\{\delta,1-\delta\\}\sqrt{1/2\pi}n\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}-\|\boldsymbol{\xi}\|_{1},$

where the last inequality comes from empirical process results Corollary 2.
Lemma 18 proves with probability over
$1-{}^{*}\\!c_{1}n^{-\min\\{1,\varepsilon\\}}$,
$\frac{1}{n}\|\boldsymbol{\xi}\|_{1}\leq 3\gamma$. Then it leads to

$\displaystyle
f({\mathbf{M}})-f({\mathbf{M}}^{*})\geq\min\\{\delta,1-\delta\\}\sqrt{1/2\pi}n\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}-3n\gamma.$

Therefore when $\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}\geq
15\gamma\max\\{\frac{1}{\delta},\frac{1}{1-\delta}\\}$, it has

$\displaystyle
f({\mathbf{M}})-f({\mathbf{M}}^{*})\geq\frac{1}{6}\min\\{\delta,1-\delta\\}n\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}},$

which proves with $\mu_{\textsf{\tiny
comp}}=\frac{1}{6}\min\\{\delta,1-\delta\\}n$.

Then consider the second phase where
$c\sqrt{d_{1}r/n}b_{0}\leq\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}\leq
15\gamma\max\\{\frac{1}{\delta},\frac{1}{1-\delta}\\}$. Notice for all
$t_{0}\in{\mathbb{R}}$,

$\displaystyle{\mathbb{E}}\rho_{Q,\delta}(\xi-t_{0})$
$\displaystyle=\delta\int_{s\geq
t_{0}}(s-t_{0})\,dH_{\xi}(s)+(1-\delta)\int_{s<t_{0}}(t_{0}-s)\,dH_{\xi}(s)$
$\displaystyle=\int_{s\geq
t_{0}}(s-t_{0})\,dH_{\xi}(s)+(1-\delta)\int_{-\infty}^{+\infty}(t_{0}-s)\,dH_{\xi}(s)$
$\displaystyle=\int_{s\geq
t_{0}}(1-H_{\xi}(s))\,ds+(1-\delta)t_{0}-(1-\delta)\int_{-\infty}^{\infty}s\,dH_{\xi}(s).$

Set $t_{0}=\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle$ and
define
$g_{{\mathbf{X}}_{i}}({\mathbf{M}}):={\mathbb{E}}_{\xi_{i}}\rho_{Q,\delta}(\xi_{i}-\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle)$.
It implies

$\displaystyle
g_{{\mathbf{X}}_{i}}({\mathbf{M}})=\int_{s\geq\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle}(1-H_{\xi}(s))\,ds+(1-\delta)\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle-(1-\delta)\int_{-\infty}^{+\infty}s\,dH_{\xi}(s).$

This leads to

$\displaystyle
g_{{\mathbf{X}}_{i}}({\mathbf{M}})-g_{{\mathbf{X}}_{i}}({\mathbf{M}}^{*})=\int_{0}^{\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle}H_{\xi}(s)\,ds-\delta\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle.$
(27)

Note that
$\langle\mathbf{X}_{i},\mathbf{M}-\mathbf{M}^{*}\rangle\sim\mathcal{N}(0,\|\mathbf{M}-\mathbf{M}^{*}\|_{\mathrm{F}}^{2})$
and denote $z:=\langle\mathbf{X}_{i},\mathbf{M}-\mathbf{M}^{*}\rangle$. Let
$f_{z}(\cdot)$ be the density of $z$. Take expectation of $z$ on both sides of
Equation 27

$\displaystyle\mathbb{E}\left[g_{\mathbf{X}_{i}}(\mathbf{M})-g_{\mathbf{X}_{i}}(\mathbf{M}^{*})\right]$
$\displaystyle=\int_{-\infty}^{+\infty}\int_{0}^{t}\left(H_{\xi}(s)-\delta\right)f_{z}(t)\,ds\,dt$
$\displaystyle=\int_{-\infty}^{+\infty}\int_{0}^{t}\int_{0}^{s}h_{\xi}(w)f_{z}(t)\,dw\,ds\,dt$
$\displaystyle\geq
b_{0}^{-1}\int_{-\|\mathbf{M}-\mathbf{M}^{*}\|_{\mathrm{F}}}^{\|\mathbf{M}-\mathbf{M}^{*}\|_{\mathrm{F}}}\int_{0}^{t}f_{z}(t)s\,ds\,dt$
$\displaystyle=b_{0}^{-1}\int_{-\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}}^{\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}}t^{2}f_{z}(t)\,dt=b_{0}^{-1}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}^{2}\int_{-1}^{1}t^{2}\cdot\frac{1}{\sqrt{2\pi}}e^{-t^{2}/2}\,dt$
$\displaystyle\geq\frac{1}{6b_{0}}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}^{2},$

where the first inequality follows from Assumption 4 and the last line is from
$\int_{-1}^{1}t^{2}\cdot\frac{1}{\sqrt{2}}e^{-t^{2}/2}dt\geq 1/6$. Therefore,

$\displaystyle{\mathbb{E}}f({\mathbf{M}})-{\mathbb{E}}f({\mathbf{M}}^{*})=\sum_{i=1}^{n}{\mathbb{E}}g_{{\mathbf{X}}_{i}}({\mathbf{M}})-g_{{\mathbf{X}}_{i}}({\mathbf{M}}^{*})\geq\frac{n}{6b_{0}}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}^{2}.$

Invoke Theorem 10,

$\displaystyle f({\mathbf{M}})-f({\mathbf{M}}^{*})$
$\displaystyle\geq{\mathbb{E}}f({\mathbf{M}})-{\mathbb{E}}f({\mathbf{M}}^{*})-C\sqrt{nd_{1}r}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}$
$\displaystyle\geq\frac{n}{6b_{0}}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}^{2}-C\sqrt{nd_{1}r}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}$
$\displaystyle\geq\frac{n}{12b_{0}}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}^{2},$

where the last inequality uses $\|{\mathbf{X}}-{\mathbf{X}}^{*}\|_{\rm{F}}\geq
c\sqrt{d_{1}r/n}b_{0}$. This proves the lower bound in the second phase and
shows $\mu_{\textsf{\tiny stat}}=\frac{n}{12b_{0}}$.

Finally, from the following lemma, we see that $L_{\textsf{\tiny stat}}\leq
C_{2}nb_{1}^{-1}$. And this finished the proof of the lemma.

######  Lemma 10 (Upper bound for sub-gradient).

Let ${\mathbf{M}}\in{\mathbb{R}}^{d_{1}\times d_{2}}$ be at most rank $r$
matrix such that
$\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}\geq\sqrt{d_{1}r/n}b_{1}$. Let
${\mathbf{G}}\in\partial f({\mathbf{M}})$ be the sub-gradient. Under the event
${\boldsymbol{\mathcal{E}}}=\\{\sup_{{\mathbf{M}},{\mathbf{M}}_{1}\in{\mathbb{M}}_{r}}|f({\mathbf{M}}+{\mathbf{M}}_{1})-f({\mathbf{M}})-{\mathbb{E}}(f({\mathbf{M}}+{\mathbf{M}}_{1})-f({\mathbf{M}}))|\cdot\|{\mathbf{M}}_{1}\|_{\rm{F}}^{-1}\leq
C_{1}\sqrt{nd_{1}r}\\}$,, we have $\|{\mathbf{G}}\|_{\rm{F},r}\leq
Cnb_{1}^{-1}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}$ for some absolute
constant $C>0$.

###### Proof.

Take
${\mathbf{M}}_{1}={\mathbf{M}}+\frac{b_{1}}{2n}\text{SVD}_{r}({\mathbf{G}})$,
where $\text{SVD}_{r}({\mathbf{G}})$ is the best rank $r$ approximation of
${\mathbf{G}}$ and then $\text{rank}({\mathbf{M}}_{1})\leq 2r$. First consider
${\mathbb{E}}f({\mathbf{M}}_{1})-{\mathbb{E}}f({\mathbf{M}})$. Use the same
notation as in the above proof and similarly,

$\displaystyle
g_{{\mathbf{X}}_{i}}({\mathbf{M}}_{1})-g_{{\mathbf{X}}_{i}}({\mathbf{M}})=$
$\displaystyle\int_{\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle}^{\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle+\langle{\mathbf{X}}_{i},{\mathbf{M}}_{1}-{\mathbf{M}}\rangle}\int_{0}^{\xi}h_{\xi}(x)\,dx\,d\xi$
$\displaystyle\leq$ $\displaystyle
b_{1}^{-1}\int_{\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle}^{\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle+\langle{\mathbf{X}}_{i},{\mathbf{M}}_{1}-{\mathbf{M}}\rangle}\xi\,d\xi$
$\displaystyle=$
$\displaystyle\frac{1}{2b_{1}}\left[(\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle+\langle{\mathbf{X}}_{i},{\mathbf{M}}_{1}-{\mathbf{M}}\rangle)^{2}-(\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle)^{2}\right],$

where the inequality follows from the upper bound for $h_{\xi}(x)\leq
b_{1}^{-1}$. Then take expectation on each side and sum up:

$\displaystyle{\mathbb{E}}f({\mathbf{M}}_{1})-{\mathbb{E}}f({\mathbf{M}})=$
$\displaystyle\sum_{i=1}^{n}{\mathbb{E}}[g_{{\mathbf{X}}_{i}}({\mathbf{M}}_{1})-g_{{\mathbf{X}}_{i}}({\mathbf{M}})]$
$\displaystyle\leq$
$\displaystyle\frac{n}{2b_{1}}{\mathbb{E}}\left[(\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle+\langle{\mathbf{X}}_{i},{\mathbf{M}}_{1}-{\mathbf{M}}\rangle)^{2}-(\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle)^{2}\right]$
$\displaystyle\leq$
$\displaystyle\frac{n}{2b_{1}}\left[\|{\mathbf{M}}_{1}-{\mathbf{M}}\|_{\mathrm{F}}^{2}+2\|{\mathbf{M}}_{1}-{\mathbf{M}}\|_{\mathrm{F}}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\mathrm{F}}\right]$

Bound $f({\mathbf{M}}_{1})-f({\mathbf{M}})$ using Corollary 1:

$\displaystyle f({\mathbf{M}}_{1})-f({\mathbf{M}})\leq$
$\displaystyle{\mathbb{E}}f({\mathbf{M}}_{1})-{\mathbb{E}}f({\mathbf{M}})+C_{1}\sqrt{nd_{1}r}(\|{\mathbf{M}}_{1}-{\mathbf{M}}^{*}\|_{\mathrm{F}}+\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\mathrm{F}})$
$\displaystyle\leq$
$\displaystyle{\mathbb{E}}f({\mathbf{M}}_{1})-{\mathbb{E}}f({\mathbf{M}})+C_{1}nb_{1}^{-1}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\mathrm{F}}(2\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\mathrm{F}}+\|{\mathbf{M}}_{1}-{\mathbf{M}}\|_{\mathrm{F}})$
$\displaystyle\leq$
$\displaystyle\frac{n}{2b_{1}}\|{\mathbf{M}}_{1}-{\mathbf{M}}\|_{\mathrm{F}}^{2}+(1+C_{1})nb_{1}^{-1}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\mathrm{F}}\|{\mathbf{M}}_{1}-{\mathbf{M}}\|_{\mathrm{F}}+2C_{1}nb_{1}^{-1}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\mathrm{F}}^{2},$

where the second inequality is from the condition
$\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}\geq
c\sqrt{\frac{d_{1}r}{n}}b_{1}$. Since
${\mathbf{M}}_{1}={\mathbf{M}}+\frac{b_{1}}{2n}\text{SVD}_{r}({\mathbf{G}})$,
it becomes

$\begin{split}f({\mathbf{M}}+\frac{b_{1}}{2n}\text{SVD}_{r}({\mathbf{G}}))&-f({\mathbf{M}})\\\
&\leq\frac{b_{1}}{8n}\|{\mathbf{G}}\|_{\mathrm{F,r}}^{2}+(1/2+C_{1}/2)\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\mathrm{F}}\|{\mathbf{G}}\|_{\mathrm{F,r}}+2C_{1}\frac{n}{b_{1}}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\mathrm{F}}^{2}.\end{split}$
(28)

On the other hand, by the definition of sub-gradient,
$f({\mathbf{M}}_{1})-f({\mathbf{M}})$ has lower bound

$\displaystyle
f({\mathbf{M}}+\frac{b_{1}}{2n}\text{SVD}_{r}({\mathbf{G}}))-f({\mathbf{M}})\geq\frac{b_{1}^{2}}{2n}\|{\mathbf{G}}\|_{\rm{F},r}^{2}.$
(29)

Combine Equation 28, Equation 29 and then solve the quadratic inequality which
leads to

$\|{\mathbf{G}}\|_{\rm{F},r}\leq
Cnb_{1}^{-1}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}.$

∎

###  B.5 Proof of tensor case, absolute loss with Gaussian noise Lemma 5

###### Proof.

We shall use ${\mathbb{O}}_{d,r}:=\\{{\mathbf{U}}\in{\mathbb{R}}^{d\times
r}:\,{\mathbf{U}}^{\top}{\mathbf{U}}={\mathbf{I}}_{r}\\}$ to refer to set of
all $d$-by-$r$ matrices with orthonormal columns and ${\mathbb{O}}_{r}$ to be
set of dimension $r$ orthonormal matrices.

Note that when $n\geq C(2^{m}\cdot r_{1}r_{2}\cdots
r_{m}+2\sum_{j=1}^{m}r_{j}d_{j})$, with probability exceeding
$1-4\exp(-c(2^{m}\cdot r_{1}r_{2}\cdots r_{m}+2\sum_{j=1}^{m}r_{j}d_{j}))$,
$L_{\textsf{\tiny comp}}=2n$. The reason is similar to the one presented in
Section B.1 and here we use Gaussian process Corollary 4 to cope with tensor.

Next consider the lower bound for $f({\mathbf{M}})-f({\mathbf{M}}^{*})$. Its
expectation ${\mathbb{E}}[f({\mathbf{M}})-f({\mathbf{M}}^{*})]$ is calculated
in Lemma 17. We shall proceed assuming the event
${\boldsymbol{\mathcal{E}}}=\\{\sup_{{\mathbf{M}}\in{\mathbb{M}}_{\mathbf{r}}}|f({\mathbf{M}})-f({\mathbf{M}}^{*})-{\mathbb{E}}(f({\mathbf{M}})-f({\mathbf{M}}^{*}))|\cdot\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}^{-1}\leq
C_{2}\sqrt{n(2^{m}\cdot r_{1}r_{2}\cdots r_{m}+2\sum_{j=1}^{m}d_{j}r_{j})}\\}$
holds and specifically Theorem 11 proves ${\boldsymbol{\mathcal{E}}}$ holds
with probability exceeding $1-\exp(-c(2^{m}\cdot r_{1}r_{2}\cdots
r_{m}+2\sum_{j=1}^{m}d_{j}r_{j}))$.

We discuss the two phases respectively, namely, phase one when
$\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}\geq\sigma$ and phase two when
$C\sqrt{(2^{m}\cdot r_{1}r_{2}\cdots
r_{m}+2\sum_{j=1}^{m}d_{j}r_{j})/n}\sigma\leq\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}\leq\sigma$.

Case 1: When $\|\mathbf{M}-\mathbf{M}^{*}\|_{\mathrm{F}}\geq\sigma$, we have

$\displaystyle f(\mathbf{M})-f(\mathbf{M}^{*})$
$\displaystyle\geq\mathbb{E}\left[f(\mathbf{M})-f(\mathbf{M}^{*})\right]-C_{2}\sqrt{n(2^{m}\cdot
r_{1}r_{2}\cdots
r_{m}+2\sum_{j=1}^{m}d_{j}r_{j})}\|\mathbf{M}-\mathbf{M}^{*}\|_{\mathrm{F}}$
$\displaystyle=n\sqrt{2/\pi}\frac{1}{\sqrt{\|\mathbf{M}-\mathbf{M}^{*}\|_{\mathrm{F}}^{2}+\sigma^{2}}+\sigma}\|\mathbf{M}-\mathbf{M}^{*}\|_{\mathrm{F}}^{2}-C_{2}\sqrt{n(2^{m}\cdot
r_{1}r_{2}\cdots
r_{m}+2\sum_{j=1}^{m}d_{j}r_{j})}\|\mathbf{M}-\mathbf{M}^{*}\|_{\mathrm{F}}$
$\displaystyle\geq
n\sqrt{2/\pi}\frac{1}{\sqrt{2}+1}\|\mathbf{M}-\mathbf{M}^{*}\|_{\mathrm{F}}-C_{2}\sqrt{n(2^{m}\cdot
r_{1}r_{2}\cdots
r_{m}+2\sum_{j=1}^{m}d_{j}r_{j})}\|\mathbf{M}-\mathbf{M}^{*}\|_{\mathrm{F}}$
$\displaystyle\geq\frac{1}{12}n\|\mathbf{M}-\mathbf{M}^{*}\|_{\mathrm{F}},$

where the penultimate line is from
$\|\mathbf{M}-\mathbf{M}^{*}\|_{\mathrm{F}}\geq\sigma$ and the last line uses
$n\geq C(2^{m}\cdot r_{1}r_{2}\cdots r_{m}+2\sum_{j=1}^{m}d_{j}r_{j})$ for
some large absolute constant $C>0$. It verifies $\mu_{\textsf{\tiny
comp}}=\frac{1}{12}n$.

Case 2: When $C\sqrt{(2^{m}\cdot r_{1}r_{2}\cdots
r_{m}+2\sum_{j=1}^{m}d_{j}r_{j})/n}\sigma\leq\|\mathbf{M}-\mathbf{M}^{*}\|_{\mathrm{F}}<\sigma$,
we have

$\begin{split}f(\mathbf{M})-f(\mathbf{M}^{*})&\geq\mathbb{E}\left[f(\mathbf{M})-f(\mathbf{M}^{*})\right]-C_{2}\sqrt{n(2^{m}\cdot
r_{1}r_{2}\cdots
r_{m}+2\sum_{j=1}^{m}d_{j}r_{j})}\|\mathbf{M}-\mathbf{M}^{*}\|_{\mathrm{F}}\\\
&=n\sqrt{2/\pi}\frac{1}{\sqrt{\|\mathbf{M}-\mathbf{M}^{*}\|_{\mathrm{F}}^{2}+\sigma^{2}}+\sigma}\|\mathbf{M}-\mathbf{M}^{*}\|_{\mathrm{F}}^{2}-C_{2}\sqrt{n(2^{m}\cdot
r_{1}r_{2}\cdots
r_{m}+2\sum_{j=1}^{m}d_{j}r_{j})}\|\mathbf{M}-\mathbf{M}^{*}\|_{\mathrm{F}}\\\
&\geq\frac{1}{6}\frac{n}{\sigma}\|\mathbf{M}-\mathbf{M}^{*}\|_{\mathrm{F}}^{2}-C_{2}\sqrt{n(2^{m}\cdot
r_{1}r_{2}\cdots
r_{m}+2\sum_{j=1}^{m}d_{j}r_{j})}\|\mathbf{M}-\mathbf{M}^{*}\|_{\mathrm{F}}\\\
&\geq\frac{1}{12}\frac{n}{\sigma}\|\mathbf{M}-\mathbf{M}^{*}\|_{\mathrm{F}}^{2},\end{split}$

where the penultimate line uses
$\|\mathbf{M}-\mathbf{M}^{*}\|_{\mathrm{F}}<\sigma$ and the last line is from
$\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}\geq C\sqrt{(2^{m}\cdot
r_{1}r_{2}\cdots r_{m}+2\sum_{j=1}^{m}d_{j}r_{j})/n}\sigma$. It shows
$\mu_{\textsf{\tiny stat}}=\frac{1}{12}\frac{n}{\sigma}$.

Finally, from the following Lemma 11, we see that $L_{\textsf{\tiny stat}}\leq
C_{4}n\sigma^{-1}$. And this finishes the proof of the lemma. ∎

######  Lemma 11 (Upper bound for sub-gradient).

Let tensor ${\mathbf{M}}\in{\mathbb{R}}^{d_{1}\times\cdots\times d_{m}}$ have
rank at most ${\mathbf{r}}$ and satisfy
$\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}\geq\sqrt{n^{-1}(2^{m}\cdot
r_{1}r_{2}\cdots r_{m}+2\sum_{j=1}^{m}d_{j}r_{j})}\sigma$. Let
${\mathbf{G}}\in\partial f({\mathbf{M}})$ be the sub-gradient. Under the event
${\boldsymbol{\mathcal{E}}}=\\{\sup_{{\mathbf{M}}\in{\mathbb{M}}_{\mathbf{r}},{\mathbf{M}}_{1}\in{\mathbb{M}}_{2{\mathbf{r}}}}|f({\mathbf{M}}+{\mathbf{M}}_{1})-f({\mathbf{M}})-{\mathbb{E}}(f({\mathbf{M}}+{\mathbf{M}}_{1})-f({\mathbf{M}}))|\cdot\|{\mathbf{M}}_{1}\|_{\rm{F}}^{-1}\leq
C_{1}\sqrt{n(2^{m}\cdot r_{1}r_{2}\cdots
r_{m}+2\sum_{j=1}^{m}d_{j}r_{j})}\\}$, we have
$\|{\mathbf{G}}\|_{\mathrm{F,2{\mathbf{r}}}}\leq
Cn\sigma^{-1}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}$ for some absolute
constant $C>0$.

###### Proof.

There exists orthonormal matrices
${\mathbf{U}}_{1}\in{\mathbb{O}}_{d_{1},2r_{1}},\cdots,{\mathbf{U}}_{m}\in{\mathbb{O}}_{d_{m},2r_{m}}$
such that
$\|{\mathbf{G}}\|_{\mathrm{F,2{\mathbf{r}}}}=\|{\mathbf{G}}\times_{1}{\mathbf{U}}_{1}^{\top}\times_{2}\cdots\times_{m}{\mathbf{U}}_{m}^{\top}\|_{\rm{F}}$
and denote
$\tilde{{\mathbf{G}}}:={\mathbf{G}}\times_{1}{\mathbf{U}}_{1}{\mathbf{U}}_{1}^{\top}\times_{2}\cdots\times_{m}{\mathbf{U}}_{m}{\mathbf{U}}_{m}^{\top}$.
Take ${\mathbf{M}}_{1}={\mathbf{M}}+\frac{\sigma}{2n}\tilde{{\mathbf{G}}}$. So
$\text{rank}({\mathbf{M}}_{1}-{\mathbf{M}})\leq 2{\mathbf{r}}$. Then we have

$\displaystyle{\mathbb{E}}f({\mathbf{M}}_{1})-{\mathbb{E}}f({\mathbf{M}})=$
$\displaystyle\sqrt{2/\pi}n\frac{\|{\mathbf{M}}_{1}-{\mathbf{M}}^{*}\|_{\mathrm{F}}^{2}-\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\mathrm{F}}^{2}}{\sqrt{\sigma^{2}+\|{\mathbf{M}}_{1}-{\mathbf{M}}^{*}\|_{\mathrm{F}}^{2}}+\sqrt{\sigma^{2}+\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\mathrm{F}}^{2}}}$
$\displaystyle=$
$\displaystyle\sqrt{2/\pi}n\frac{\|{\mathbf{M}}_{1}-{\mathbf{M}}\|_{\mathrm{F}}^{2}+2\langle{\mathbf{M}}-{\mathbf{M}}^{*},{\mathbf{M}}_{1}-{\mathbf{M}}\rangle}{\sqrt{\sigma^{2}+\|{\mathbf{M}}_{1}-{\mathbf{M}}^{*}\|_{\mathrm{F}}^{2}}+\sqrt{\sigma^{2}+\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\mathrm{F}}^{2}}}$
$\displaystyle\leq$
$\displaystyle\sqrt{2/\pi}\frac{n}{\sigma}\left(\|{\mathbf{M}}_{1}-{\mathbf{M}}\|_{\mathrm{F}}^{2}+2\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\mathrm{F}}\|{\mathbf{M}}_{1}-{\mathbf{M}}\|_{\mathrm{F}}\right),$

where the first equality comes from Lemma 17. And from Corollary 3, we have

$\displaystyle f({\mathbf{M}}_{1})-f({\mathbf{M}})\leq$
$\displaystyle{\mathbb{E}}f({\mathbf{M}}_{1})-{\mathbb{E}}f({\mathbf{M}})+C_{1}\sqrt{n(2^{m}\cdot
r_{1}r_{2}\cdots
r_{m}+2\sum_{j=1}^{m}d_{j}r_{j})}(\|{\mathbf{M}}_{1}-{\mathbf{M}}^{*}\|_{\mathrm{F}}+\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\mathrm{F}})$
$\displaystyle\leq$
$\displaystyle{\mathbb{E}}f({\mathbf{M}}_{1})-{\mathbb{E}}f({\mathbf{M}})+C_{1}\frac{n}{\sigma}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\mathrm{F}}(2\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\mathrm{F}}+\|{\mathbf{M}}_{1}-{\mathbf{M}}\|_{\mathrm{F}})$
$\displaystyle\leq$
$\displaystyle\frac{n}{\sigma}\|{\mathbf{M}}_{1}-{\mathbf{M}}\|_{\mathrm{F}}^{2}+(2+C_{1})\frac{n}{\sigma}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\mathrm{F}}\|{\mathbf{M}}_{1}-{\mathbf{M}}\|_{\mathrm{F}}+2C_{1}\frac{n}{\sigma}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\mathrm{F}}^{2},$

where the second inequality is from the condition
$\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}\geq\sqrt{\frac{2^{m}\cdot
r_{1}r_{2}\cdots r_{m}+2\sum_{j=1}^{m}d_{j}r_{j}}{n}}\sigma$. Since
${\mathbf{M}}_{1}={\mathbf{M}}+\frac{\sigma}{2n}\tilde{{\mathbf{G}}}$, we have

$\begin{split}f({\mathbf{M}}+\frac{\sigma}{2n}\tilde{{\mathbf{G}}})&-f({\mathbf{M}})\\\
&\leq\frac{\sigma}{4n}\|{\mathbf{G}}\|_{\mathrm{F,2{\mathbf{r}}}}^{2}+(1+C_{1}/2)\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\mathrm{F}}\|{\mathbf{G}}\|_{\mathrm{F,2{\mathbf{r}}}}+2C_{1}\frac{n}{\sigma}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\mathrm{F}}^{2}.\end{split}$
(30)

On the other hand, by the definition of sub-gradient, we have

$\displaystyle
f({\mathbf{M}}+\frac{\sigma}{2n}\tilde{{\mathbf{G}}})-f({\mathbf{M}})\geq\frac{\sigma}{2n}\|{\mathbf{G}}\|_{\mathrm{F,2{\mathbf{r}}}}^{2}.$
(31)

Combine Equation 30 with Equation 31 and by solving the quadratic inequality
we get

$\|{\mathbf{G}}\|_{\mathrm{F,2{\mathbf{r}}}}\leq
Cn\sigma^{-1}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}.$

∎

###  B.6 Proof of tensor case, absolute value loss with heavy-tailed noise
Lemma 6

The $L_{\textsf{\tiny comp}}=2n$ proof is the same as the one given in Section
B.5. Now we focus on lower bound of $f({\mathbf{M}})-f({\mathbf{M}}^{*})$.

First consider phase one when $\|{\mathbf{X}}-{\mathbf{X}}^{*}\|_{\rm{F}}\geq
30{\mathbb{E}}|\xi|=30\gamma$. Use triangle inequality and then get

$\displaystyle f(\mathbf{M})-f(\mathbf{M}^{*})$
$\displaystyle=\sum_{i=1}^{n}|\xi_{i}-\langle{\mathbf{M}}-{\mathbf{M}}^{*},{\mathbf{X}}_{i}\rangle|-\sum_{i=1}^{n}|\xi_{i}|\geq\sum_{i=1}^{n}|\langle{\mathbf{M}}-{\mathbf{M}}^{*},{\mathbf{X}}_{i}\rangle|-2\|\boldsymbol{\xi}\|_{1}.$
(32)

Corollary 4 proves
$\sum_{i=1}^{n}|\langle{\mathbf{M}}-{\mathbf{M}}^{*},{\mathbf{X}}_{i}\rangle|\geq\sqrt{1/2\pi}n\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}$
and Lemma 18 proves with probability over
$1-{}^{*}\\!c_{1}n^{-\min\\{1,\varepsilon\\}}$,
$\frac{1}{n}\|\boldsymbol{\xi}\|_{1}\leq 3{\mathbb{E}}|\xi|=3\gamma$. Then
combined with $\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}\geq 30\gamma$,
Equation 32 becomes

$\displaystyle
f(\mathbf{M})-f(\mathbf{M}^{*})\geq\sqrt{1/2\pi}n\|\mathbf{M}-\mathbf{M}^{*}\|_{\mathrm{F}}-6n\gamma\geq\frac{n}{6}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}},$

which verifies $\mu_{\textsf{\tiny comp}}=\frac{n}{6}$.

Then consider the second phase when $C_{2}\sqrt{(2^{m}\cdot r_{1}r_{2}\cdots
r_{m}+2\sum_{j=1}^{m}d_{j}r_{j})/n}b_{0}\leq\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}<30\gamma$.
To bound expectation of $f({\mathbf{M}})-f({\mathbf{M}}^{*})$, we first
consider the conditional expectation
${\mathbb{E}}_{\xi}f({\mathbf{M}})-{\mathbb{E}}_{\xi}f({\mathbf{M}}^{*})$.
Notice for all $t_{0}\in{\mathbb{R}}$,

$\displaystyle{\mathbb{E}}|\xi-t_{0}|$ $\displaystyle=\int_{s\geq
t_{0}}(s-t_{0})dH_{\xi}(s)+\int_{s<t_{0}}(t_{0}-s)dH_{\xi}(s)$
$\displaystyle=2\int_{s\geq
t_{0}}(s-t_{0})dH_{\xi}(s)+\int_{-\infty}^{+\infty}(t_{0}-s)dH_{\xi}(s)$
$\displaystyle=2\int_{s\geq
t_{0}}(1-H_{\xi}(s))ds+t_{0}-\int_{-\infty}^{\infty}sdH_{\xi}(s).$

Set $t_{0}=\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle$ and
define
$g_{{\mathbf{X}}_{i}}({\mathbf{M}}):={\mathbb{E}}_{\xi_{i}}|\xi_{i}-\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle|$.
It implies

$\displaystyle
g_{{\mathbf{X}}_{i}}({\mathbf{M}})=2\int_{s\geq\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle}(1-H_{\xi}(s))ds+\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle-\int_{-\infty}^{+\infty}sdH_{\xi}(s).$

This leads to

$\displaystyle
g_{{\mathbf{X}}_{i}}({\mathbf{M}})-g_{{\mathbf{X}}_{i}}({\mathbf{M}}^{*})=2\int_{0}^{\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle}H_{\xi}(s)ds-\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle.$
(33)

Note that $\langle\mathbf{X}_{i},\mathbf{M}-\mathbf{M}^{*}\rangle$ follows
Gaussian distribution with mean zero variance
$\|\mathbf{M}-\mathbf{M}^{*}\|_{\mathrm{F}}^{2}$ and denote it as
$z:=\langle\mathbf{X}_{i},\mathbf{M}-\mathbf{M}^{*}\rangle$. Let
$f_{z}(\cdot)$ be the density of $z$. Take expectation of $z$ on both sides of
Equation 33

$\displaystyle\mathbb{E}\left[g_{\mathbf{X}_{i}}(\mathbf{M})-g_{\mathbf{X}_{i}}(\mathbf{M}^{*})\right]$
$\displaystyle=2\int_{-\infty}^{+\infty}\int_{0}^{t}\left(H_{\xi}(s)-0.5\right)f_{z}(t)\,ds\,dz$
$\displaystyle=2\int_{-\infty}^{+\infty}\int_{0}^{t}\int_{0}^{s}h_{\xi}(w)f_{z}(t)\,dw\,ds\,dt$
$\displaystyle\geq
2\int_{-\|\mathbf{M}-\mathbf{M}^{*}\|_{\mathrm{F}}}^{\|\mathbf{M}-\mathbf{M}^{*}\|_{\mathrm{F}}}\int_{0}^{t}f_{z}(t)b_{0}^{-1}s\,ds\,dt$
$\displaystyle=b_{0}^{-1}\int_{-\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}}^{\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}}t^{2}f_{z}(t)\,dt=b_{0}^{-1}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}^{2}\int_{-1}^{1}t^{2}\cdot\frac{1}{\sqrt{2\pi}}e^{-t^{2}/2}\,dt$
$\displaystyle\geq\frac{1}{6b_{0}}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}^{2},$

where the first inequality follows from Assumption 2 and the last is from
$\int_{-1}^{1}t^{2}\cdot\frac{1}{\sqrt{2\pi}}e^{-t^{2}/2}\,dt\geq 1/6$.
Therefore,

$\displaystyle{\mathbb{E}}f({\mathbf{M}})-{\mathbb{E}}f({\mathbf{M}}^{*})=\sum_{i=1}^{n}{\mathbb{E}}[g_{{\mathbf{X}}_{i}}({\mathbf{M}})-g_{{\mathbf{X}}_{i}}({\mathbf{M}}^{*})]\geq\frac{n}{6b_{0}}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}^{2}.$

Invoke Theorem 11,

$\displaystyle f({\mathbf{M}})-f({\mathbf{M}}^{*})$
$\displaystyle\geq{\mathbb{E}}[f({\mathbf{M}})-f({\mathbf{M}}^{*})]-C\sqrt{n(2^{m}\cdot
r_{1}r_{2}\cdots
r_{m}+2\sum_{j=1}^{m}d_{j}r_{j})}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}$
$\displaystyle\geq\frac{n}{6b_{0}}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}^{2}-C\sqrt{n(2^{m}\cdot
r_{1}r_{2}\cdots
r_{m}+2\sum_{j=1}^{m}d_{j}r_{j})}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}$
$\displaystyle\geq\frac{n}{12b_{0}}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}^{2},$

where the last inequality uses $\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}\geq
C_{2}\sqrt{(2^{m}\cdot r_{1}r_{2}\cdots
r_{m}+2\sum_{j=1}^{m}d_{j}r_{j})/n}b_{0}$. This proves $\mu_{\textsf{\tiny
stat}}=\frac{n}{12b_{0}}$.

Finally, from the following lemma, we see that $L_{\textsf{\tiny stat}}\leq
C_{3}nb_{1}^{-1}$. And this finishes the proof.

######  Lemma 12 (Upper bound for sub-gradient).

Let ${\mathbf{M}}\in{\mathbb{R}}^{d_{1}\times\cdots\times d_{m}}$ be rank at
most ${\mathbf{r}}$ tensor such that
$\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}\geq C_{2}\sqrt{n^{-1}(2^{m}\cdot
r_{1}r_{2}\cdots r_{m}+2\sum_{j=1}^{m}d_{j}r_{j})}b_{1}$. Let
${\mathbf{G}}\in\partial f({\mathbf{M}})$ be the sub-gradient. Under the event
${\boldsymbol{\mathcal{E}}}=\\{\sup_{{\mathbf{M}}\in{\mathbb{M}}_{\mathbf{r}},{\mathbf{M}}_{1}\in{\mathbb{M}}_{2{\mathbf{r}}}}|f({\mathbf{M}}+{\mathbf{M}}_{1})-f({\mathbf{M}})-{\mathbb{E}}(f({\mathbf{M}}+{\mathbf{M}}_{1})-f({\mathbf{M}}))|\cdot\|{\mathbf{M}}_{1}\|_{\rm{F}}^{-1}\leq
C_{1}\sqrt{n(2^{m}\cdot r_{1}r_{2}\cdots
r_{m}+2\sum_{j=1}^{m}d_{j}r_{j})}\\}$, we have
$\|{\mathbf{G}}\|_{\mathrm{F,2{\mathbf{r}}}}\leq
C_{3}nb_{1}^{-1}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}$ for some absolute
constant $C_{3}>0$.

###### Proof.

There exists orthonormal matrices
${\mathbf{U}}_{1}\in{\mathbb{O}}_{d_{1},2r_{1}},\cdots,{\mathbf{U}}_{m}\in{\mathbb{O}}_{d_{m},2r_{m}}$
such that
$\|{\mathbf{G}}\|_{\mathrm{F,2{\mathbf{r}}}}=\|{\mathbf{G}}\times_{1}{\mathbf{U}}_{1}^{\top}\times_{2}\cdots\times_{m}{\mathbf{U}}_{m}^{\top}\|_{\rm{F}}$
and denote
$\tilde{{\mathbf{G}}}:={\mathbf{G}}\times_{1}{\mathbf{U}}_{1}{\mathbf{U}}_{1}^{\top}\times_{2}\cdots\times_{m}{\mathbf{U}}_{m}{\mathbf{U}}_{m}^{\top}$.
Take ${\mathbf{M}}_{1}={\mathbf{M}}+\frac{b_{1}}{2n}\tilde{{\mathbf{G}}}$ and
then $\text{rank}({\mathbf{M}}_{1}-{\mathbf{M}})\leq 2{\mathbf{r}}$. We finish
the proof via combining lower bound and upper bound of
$f({\mathbf{M}}_{1})-f({\mathbf{M}})$. First consider
${\mathbb{E}}f({\mathbf{M}}_{1})-{\mathbb{E}}f({\mathbf{M}})$. Use the same
notation as the above proof and similarly,

$\displaystyle
g_{{\mathbf{X}}_{i}}({\mathbf{M}}_{1})-g_{{\mathbf{X}}_{i}}({\mathbf{M}})=$
$\displaystyle
2\int_{\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle}^{\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle+\langle{\mathbf{X}}_{i},{\mathbf{M}}_{1}-{\mathbf{M}}\rangle}\int_{0}^{\xi}h_{\xi}(x)\,dx\,d\xi$
$\displaystyle\leq$ $\displaystyle
2b_{1}^{-1}\int_{\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle}^{\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle+\langle{\mathbf{X}}_{i},{\mathbf{M}}_{1}-{\mathbf{M}}\rangle}\xi\,d\xi$
$\displaystyle=$ $\displaystyle
b_{1}^{-1}\left[(\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle+\langle{\mathbf{X}}_{i},{\mathbf{M}}_{1}-{\mathbf{M}}\rangle)^{2}-(\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle)^{2}\right],$

where the inequality follows from the upper bound for $h_{\xi}(x)$. Then take
expectation of ${\mathbf{X}}_{i}$ on each side and sum up over $i$ :

$\displaystyle{\mathbb{E}}f({\mathbf{M}}_{1})-{\mathbb{E}}f({\mathbf{M}})=$
$\displaystyle\sum_{i=1}^{n}{\mathbb{E}}[g_{{\mathbf{X}}_{i}}({\mathbf{M}}_{1})-g_{{\mathbf{X}}_{i}}({\mathbf{M}})]$
$\displaystyle\leq$ $\displaystyle
nb_{1}^{-1}{\mathbb{E}}\left[(\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle+\langle{\mathbf{X}}_{i},{\mathbf{M}}_{1}-{\mathbf{M}}\rangle)^{2}-(\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle)^{2}\right]$
$\displaystyle\leq$ $\displaystyle
nb_{1}^{-1}\left[\|{\mathbf{M}}_{1}-{\mathbf{M}}\|_{\mathrm{F}}^{2}+2\|{\mathbf{M}}_{1}-{\mathbf{M}}\|_{\mathrm{F}}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\mathrm{F}}\right]$

Then bound $f({\mathbf{M}}_{1})-f({\mathbf{M}})$ with empirical process
Corollary 3:

$\displaystyle f({\mathbf{M}}_{1})-f({\mathbf{M}})\leq$
$\displaystyle{\mathbb{E}}f({\mathbf{M}}_{1})-{\mathbb{E}}f({\mathbf{M}})+C_{1}\sqrt{n(2^{m}\cdot
r_{1}r_{2}\cdots
r_{m}+2\sum_{j=1}^{m}d_{j}r_{j})}(\|{\mathbf{M}}_{1}-{\mathbf{M}}^{*}\|_{\mathrm{F}}+\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\mathrm{F}})$
$\displaystyle\leq$
$\displaystyle{\mathbb{E}}f({\mathbf{M}}_{1})-{\mathbb{E}}f({\mathbf{M}})+C_{3}nb_{1}^{-1}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\mathrm{F}}(2\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\mathrm{F}}+\|{\mathbf{M}}_{1}-{\mathbf{M}}\|_{\mathrm{F}})$
$\displaystyle\leq$ $\displaystyle
nb_{1}^{-1}\|{\mathbf{M}}_{1}-{\mathbf{M}}\|_{\mathrm{F}}^{2}+(2+C_{3})nb_{1}^{-1}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\mathrm{F}}\|{\mathbf{M}}_{1}-{\mathbf{M}}\|_{\mathrm{F}}+2C_{3}nb_{1}^{-1}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\mathrm{F}}^{2},$

where the second inequality is from the condition
$\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}\geq C_{2}\sqrt{n^{-1}(2^{m}\cdot
r_{1}r_{2}\cdots r_{m}+2\sum_{j=1}^{m}d_{j}r_{j})}b_{1}$. Since
${\mathbf{M}}_{1}={\mathbf{M}}+\frac{b_{1}}{2n}\tilde{{\mathbf{G}}}$, it
becomes

$\begin{split}f({\mathbf{M}}+\frac{b_{1}}{2n}\tilde{{\mathbf{G}}})&-f({\mathbf{M}})\\\
&\leq\frac{b_{1}}{4n}\|{\mathbf{G}}\|_{\mathrm{F,2{\mathbf{r}}}}^{2}+(1+C_{1}/2)\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\mathrm{F}}\|{\mathbf{G}}\|_{\mathrm{F,2{\mathbf{r}}}}+2C_{1}\frac{n}{b_{1}}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\mathrm{F}}^{2}.\end{split}$
(34)

On the other hand, by the definition of sub-gradient,
$f({\mathbf{M}}_{1})-f({\mathbf{M}})$ has lower bound

$\displaystyle
f({\mathbf{M}}+\frac{b_{1}}{2n}\tilde{{\mathbf{G}}})-f({\mathbf{M}})\geq\frac{b_{1}}{2n}\|{\mathbf{G}}\|_{\mathrm{F,2{\mathbf{r}}}}^{2}.$
(35)

Combine Equation 34 with Equation 35 and then solve the quadratic inequality
which leads to

$\|{\mathbf{G}}\|_{\mathrm{F,2{\mathbf{r}}}}\leq
C_{3}nb_{1}^{-1}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}.$

∎

##  Appendix C Proof of Initialization Theorem 5

Notice that

$\displaystyle\|\frac{1}{n}\sum_{i=1}^{n}Y_{i}{\mathbf{X}}_{i}-{\mathbf{M}}^{*}\|=$
$\displaystyle\|\frac{1}{n}\sum_{i=1}^{n}(\xi_{i}+\langle{\mathbf{X}}_{i},{\mathbf{M}}^{*}\rangle){\mathbf{X}}_{i}-{\mathbf{M}}^{*}\|$
$\displaystyle\leq$
$\displaystyle\|\frac{1}{n}\sum_{i=1}^{n}\langle{\mathbf{X}}_{i},{\mathbf{M}}^{*}\rangle{\mathbf{X}}_{i}-{\mathbf{M}}^{*}\|+\frac{1}{n}\|\sum_{i=1}^{n}\xi_{i}{\mathbf{X}}_{i}\|.$

Use Theorem 9 to bound the first term. Note that

${\mathbb{E}}\left[\langle{\mathbf{X}}_{i},{\mathbf{M}}^{*}\rangle{\mathbf{X}}_{i}-{\mathbf{M}}^{*}\right]=0,$
$\|\Lambda_{\max}\left(\langle{\mathbf{X}}_{i},{\mathbf{M}}^{*}\rangle{\mathbf{X}}_{i}-{\mathbf{M}}^{*}\right)\|_{\Psi_{1}}\leq\|\langle{\mathbf{X}}_{i},{\mathbf{M}}^{*}\rangle\|_{\Psi_{2}}\|\Lambda_{\max}\left({\mathbf{X}}_{i}\right)\|_{\Psi_{2}}=c\sqrt{d_{1}}\|{\mathbf{M}}^{*}\|_{\rm{F}},$
${\mathbb{E}}\left[\left(\langle{\mathbf{X}}_{i},{\mathbf{M}}^{*}\rangle{\mathbf{X}}_{i}-{\mathbf{M}}^{*}\right)\left(\langle{\mathbf{X}}_{i},{\mathbf{M}}^{*}\rangle{\mathbf{X}}_{i}-{\mathbf{M}}^{*}\right)^{\top}\right]={\mathbf{M}}^{*}{\mathbf{M}}^{*\top}+d_{2}\|{\mathbf{M}}^{*}\|_{\rm{F}}^{2}\cdot{\mathbf{I}}_{d_{1}},$
${\mathbb{E}}\left[\left(\langle{\mathbf{X}}_{i},{\mathbf{M}}^{*}\rangle{\mathbf{X}}_{i}-{\mathbf{M}}^{*}\right)^{\top}\left(\langle{\mathbf{X}}_{i},{\mathbf{M}}^{*}\rangle{\mathbf{X}}_{i}-{\mathbf{M}}^{*}\right)\right]={\mathbf{M}}^{*\top}{\mathbf{M}}^{*}+d_{1}\|{\mathbf{M}}^{*}\|_{\rm{F}}^{2}\cdot{\mathbf{I}}_{d_{2}}.$

Thus,

$\displaystyle S^{2}:=$
$\displaystyle\max\left\\{\Lambda_{\max}\left(\sum_{i=1}^{n}{\mathbb{E}}\left[\left(\langle{\mathbf{X}}_{i},{\mathbf{M}}^{*}\rangle{\mathbf{X}}_{i}-{\mathbf{M}}^{*}\right)\left(\langle{\mathbf{X}}_{i},{\mathbf{M}}^{*}\rangle{\mathbf{X}}_{i}-{\mathbf{M}}^{*}\right)^{\top}\right]\right)\big{/}n,\right.$
$\displaystyle{~{}~{}~{}~{}~{}~{}~{}~{}}\left.\Lambda_{\max}\left(\sum_{i=1}^{n}{\mathbb{E}}\left[\left(\langle{\mathbf{X}}_{i},{\mathbf{M}}^{*}\rangle{\mathbf{X}}_{i}-{\mathbf{M}}^{*}\right)^{\top}\left(\langle{\mathbf{X}}_{i},{\mathbf{M}}^{*}\rangle{\mathbf{X}}_{i}-{\mathbf{M}}^{*}\right)\right]\right)\big{/}n\right\\}$
$\displaystyle=\sigma_{1}^{2}+d_{1}\|{\mathbf{M}}^{*}\|_{\rm{F}}^{2}.$

Then, by Theorem 9, we have

$\displaystyle\|\frac{1}{n}\sum_{i=1}^{n}\langle{\mathbf{X}}_{i},{\mathbf{M}}^{*}\rangle{\mathbf{X}}_{i}-{\mathbf{M}}^{*}\|$
$\displaystyle\leq
c\sqrt{\sigma_{1}^{2}+d_{1}\|{\mathbf{M}}^{*}\|_{\rm{F}}^{2}}\sqrt{\frac{\log
d_{1}}{n}}+c\frac{\log
d_{1}}{n}\log\left(\frac{\sqrt{d_{1}}\|{\mathbf{M}}^{*}\|_{\rm{F}}}{\sqrt{\sigma_{1}^{2}+d_{1}\|{\mathbf{M}}^{*}\|_{\rm{F}}^{2}}}\right)$
$\displaystyle\leq c_{0}\sqrt{\frac{d_{1}r\log d_{1}}{n}}\sigma_{1}$

holds with probability over $1-c_{1}d_{1}^{-1}$. Then consider the second
term. Note that with probability over $1-c_{2}\exp(-d_{1})$, the following
holds

$\displaystyle\frac{1}{n}\|\sum_{i=1}^{n}\xi_{i}{\mathbf{X}}_{i}\|\leq
c_{3}\frac{\sqrt{d_{1}}}{n}\left(\sum_{i=1}^{n}\xi_{i}^{2}\right)^{1/2}.$ (36)

Lemma 19 analyzes tail bound for sum of squared heavy-tailed random variables
and proves with probability exceeding $1-(\log d_{1})^{-1}$, the following
holds

$\displaystyle\sum_{i=1}^{n}\xi_{i}^{2}\leq(2n\gamma_{1}\log
d_{1})^{\frac{2}{1+\epsilon}}$

Instert it into Equation 36:

$\displaystyle\frac{1}{n}\|\sum_{i=1}^{n}\xi_{i}{\mathbf{X}}_{i}\|\leq\tilde{c}_{3}\sqrt{d_{1}}n^{-\frac{\varepsilon}{1+\varepsilon}}\left(\log
d_{1}\right)^{\frac{1}{1+\varepsilon}}\gamma_{1}^{\frac{1}{1+\epsilon}}.$

Thus, we have

$\displaystyle\|\frac{1}{n}\sum_{i=1}^{n}Y_{i}{\mathbf{X}}_{i}-{\mathbf{M}}^{*}\|\leq
c_{0}\sqrt{\frac{d_{1}r\log
d_{1}}{n}}\sigma_{1}+\tilde{c}_{3}\sqrt{d_{1}}n^{-\frac{\varepsilon}{1+\varepsilon}}\left(\log
d_{1}\right)^{\frac{1}{1+\varepsilon}}\gamma_{1}^{\frac{1}{1+\epsilon}},$

which implies
$\|\frac{1}{n}\sum_{i=1}^{n}Y_{i}{\mathbf{X}}_{i}-{\mathbf{M}}^{*}\|\leq\sigma_{r}/4$.
Then by Lemma 16, we have

$\displaystyle\|\frac{1}{n}\operatorname{SVD}_{r}(\sum_{i=1}^{n}Y_{i}{\mathbf{X}}_{i})-{\mathbf{M}}^{*}\|\leq
c_{4}\sqrt{\frac{d_{1}r\log
d_{1}}{n}}\sigma_{1}+c_{5}\sqrt{d_{1}}n^{-\frac{\varepsilon}{1+\varepsilon}}\left(\log
d_{1}\right)^{\frac{1}{1+\varepsilon}}\gamma_{1}^{\frac{1}{1+\epsilon}}.$

Note that $\text{rank}({\mathbf{M}}_{0}-{\mathbf{M}}^{*})\leq 2r$. Then, it
has

$\displaystyle\|{\mathbf{M}}_{0}-{\mathbf{M}}^{*}\|_{\mathrm{F}}\leq$
$\displaystyle\sqrt{2r}\|{\mathbf{M}}_{0}-{\mathbf{M}}^{*}\|$ $\displaystyle=$
$\displaystyle\sqrt{2r}\|\operatorname{SVD}_{r}(\frac{1}{n}\sum_{i=1}^{n}Y_{i}{\mathbf{X}}_{i})-{\mathbf{M}}^{*}\|_{2}$
$\displaystyle\leq$ $\displaystyle\tilde{c}_{4}\sqrt{\frac{d_{1}r^{2}\log
d_{1}}{n}}\sigma_{1}+\tilde{c}_{5}\sqrt{d_{1}r}n^{-\frac{\varepsilon}{1+\varepsilon}}\left(\log
d_{1}\right)^{\frac{1}{1+\varepsilon}}\gamma_{1}^{\frac{1}{1+\epsilon}},$

which completes the proof.

######  Theorem 9.

(Bernstein’s Inequality, Proposition 2 in Koltchinskii et al. [2011]) Let
${\mathbf{A}},{\mathbf{A}}_{1},\cdots,{\mathbf{A}}_{n}$ be i.i.d. $p\times q$
matrices that satisfy for some $\alpha\geq 1$ (and all $i$)

${\mathbb{E}}{\mathbf{A}}_{i}=0,\qquad\|\Lambda_{\max}({\mathbf{A}}_{i})\|_{\Psi_{\alpha}}=:K<+\infty.$

Define

$S^{2}:=\max\left\\{\Lambda_{\max}\left(\sum_{i=1}^{n}{\mathbb{E}}{\mathbf{A}}_{i}{\mathbf{A}}_{i}^{\top}\right)\big{/}n,\Lambda_{\max}\left(\sum_{i=1}^{n}{\mathbb{E}}{\mathbf{A}}_{i}^{\top}{\mathbf{A}}_{i}\right)\big{/}n\right\\}.$

Then for some constant $C>0$ and for all $t>0$,

$\displaystyle{\mathbb{P}}\left(\Lambda_{\max}\left(\sum_{i=1}^{n}{\mathbf{A}}_{i}\right)\big{/}n\geq
CS\sqrt{\frac{t+\log(p+q)}{n}}+CK\log^{1/\alpha}\left(\frac{K}{S}\right)\frac{t+\log(p+q)}{n}\right)\leq\exp(-t).$

##  Appendix D Proof of Tensor Regression Initialization Theorem 8

For any two orthogonal matrices
${\mathbf{U}},{\mathbf{V}}\in{\mathbb{O}}_{d,r}$, their distance with optimal
rotation is defined to be
$d({\mathbf{U}},{\mathbf{V}}):=\min_{{\mathbf{R}}\in{\mathbb{O}}_{r}}\|{\mathbf{U}}-{\mathbf{V}}{\mathbf{R}}\|_{\rm{F}}$.
First estimate distance between ${\mathbf{U}}_{i}^{(0)}$ and
${\mathbf{U}}_{i}^{*}$. Denote

$\displaystyle\hat{{\mathbf{N}}}=\frac{1}{2n(n-1)}\sum_{1\leq i<i^{\prime}\leq
n}^{n}\tilde{Y}_{i}\tilde{Y}_{i^{\prime}}({\mathbf{X}}_{i}{\mathbf{X}}_{i^{\prime}}^{T}+{\mathbf{X}}_{i^{\prime}}{\mathbf{X}}_{i}^{T}).$
(37)

From Lemma 13 and Wedin’s sin$\Theta$ theorem, we obtain that with probability
exceeding $1-c_{0}m\bar{d}^{-10}$, for all $i\in[m]$,

$\displaystyle
d({\mathbf{U}}_{i}^{(0)},{\mathbf{U}}_{i}^{*})\leq\sqrt{2r_{i}}\|\tilde{\mathbf{N}}_{i}-{\mathbf{M}}_{(i)}^{*}{\mathbf{M}}_{(i)}^{*\top}\|/\underline{\lambda}^{2}\leq
C_{1}\sqrt{\log\bar{d}}\frac{(d^{*})^{1/4}r_{i}}{n^{1/2}}\kappa^{2}+C_{2}\sqrt{\log\bar{d}}\frac{(d^{*})^{1/2}r_{i}^{1/2}}{n}\cdot\frac{\|\xi\|_{2+\varepsilon}^{2}}{\underline{\lambda}^{2}}.$
(38)

Decompose ${\mathbf{M}}_{0}-{\mathbf{M}}^{*}$ and we have

$\displaystyle\|{\mathbf{M}}_{0}-{\mathbf{M}}^{*}\|_{\rm{F}}\leq\|{\mathbf{C}}^{(0)}-{\mathbf{C}}^{*}\|_{\rm{F}}+m\bar{\lambda}\max_{j=1,\ldots,m}d({\mathbf{U}}_{j}^{(0)},{\mathbf{U}}_{j}^{*}).$
(39)

We now bound $\|{\mathbf{C}}^{(0)}-{\mathbf{C}}^{*}\|_{\rm{F}}$. Definition of
${\mathbf{C}}^{(0)}$ implies
$\nabla_{{\mathbf{C}}}L_{n}({\mathbf{C}}^{(0)}\times_{i}{\mathbf{U}}_{i}^{(0)})=0$.
Then expand square of $\|{\mathbf{C}}^{(0)}-{\mathbf{C}}^{*}\|_{\rm{F}}$.

$\displaystyle\|{\mathbf{C}}^{(0)}-{\mathbf{C}}^{*}\|_{\rm{F}}^{2}$
$\displaystyle=\langle\nabla_{{\mathbf{C}}}L({\mathbf{C}}^{(0)}\times_{j\in[m]}{\mathbf{U}}_{j}^{(0)})-\nabla_{{\mathbf{C}}}L({\mathbf{C}}^{*}\times_{j\in[m]}{\mathbf{U}}_{j}^{(0)}),{\mathbf{C}}^{(0)}-{\mathbf{C}}^{*}\rangle$
$\displaystyle=\underbrace{\langle(\nabla_{{\mathbf{C}}}L-\nabla_{{\mathbf{C}}}L_{n})({\mathbf{C}}^{(0)}\times_{j\in[m]}{\mathbf{U}}_{j}^{(0)}),{\mathbf{C}}^{(0)}-{\mathbf{C}}^{*}\rangle}_{\beta_{1}}-\underbrace{\langle\nabla_{{\mathbf{C}}}L({\mathbf{C}}^{*}\times_{j\in[m]}{\mathbf{U}}_{j}^{(0)}),{\mathbf{C}}^{(0)}-{\mathbf{C}}^{*}\rangle}_{\beta_{2}}.$
(40)

The first term on the right hand side can be analyzed as follows:

$\displaystyle\langle(\nabla_{{\mathbf{C}}}L-\nabla_{{\mathbf{C}}}L_{n})({\mathbf{C}}^{(0)}\times_{j\in[m]}{\mathbf{U}}_{j}^{(0)}),{\mathbf{C}}^{(0)}-{\mathbf{C}}^{*}\rangle=\langle(\nabla
L-\nabla
L_{n})({\mathbf{C}}^{(0)}\times_{j\in[m]}{\mathbf{U}}_{j}^{(0)}),({\mathbf{C}}^{(0)}-{\mathbf{C}}^{*})\times_{j\in[m]}{\mathbf{U}}_{j}^{(0)}\rangle$
$\displaystyle{~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}}=\langle(\nabla
L-{\mathbb{E}}_{\xi}\nabla
L_{n})({\mathbf{C}}^{(0)}\times_{j\in[m]}{\mathbf{U}}_{j}^{(0)}),({\mathbf{C}}^{(0)}-{\mathbf{C}}^{*})\times_{j\in[m]}{\mathbf{U}}_{j}^{(0)}\rangle$
$\displaystyle{~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}}+\langle({\mathbb{E}}_{\xi}\nabla
L_{n}-\nabla
L_{n})({\mathbf{C}}^{(0)}\times_{j\in[m]}{\mathbf{U}}_{j}^{(0)}),({\mathbf{C}}^{(0)}-{\mathbf{C}}^{*})\times_{j\in[m]}{\mathbf{U}}_{j}^{(0)}\rangle.$

Notice that the first term is

$\displaystyle{~{}~{}~{}~{}}\langle(\nabla L-{\mathbb{E}}_{\xi}\nabla
L_{n})({\mathbf{C}}^{(0)}\times_{j\in[m]}{\mathbf{U}}_{j}^{(0)}),({\mathbf{C}}^{(0)}-{\mathbf{C}}^{*})\times_{j\in[m]}{\mathbf{U}}_{j}^{(0)}\rangle$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\langle{\mathbf{M}}_{0}-{\mathbf{M}}^{*},{\mathbf{X}}_{i}\rangle\langle({\mathbf{C}}^{(0)}-{\mathbf{C}}^{*})\times_{j\in[m]}{\mathbf{U}}_{j}^{(0)},{\mathbf{X}}_{i}\rangle-\langle{\mathbf{M}}_{0}-{\mathbf{M}}^{*},({\mathbf{C}}^{(0)}-{\mathbf{C}}^{*})\times_{j\in[m]}{\mathbf{U}}_{j}^{(0)}\rangle.$

Using a standard empirical process argument, we get as long as
$n\gtrsim\sum_{j}^{m}d_{j}r_{j}+r_{1}r_{2}\cdots r_{m}$, with probability
exceeding $1-\exp(-C(\sum_{j}^{m}d_{j}r_{j}+r_{1}r_{2}\cdots r_{m}))$,

$\sup_{{\mathbf{A}},{\mathbf{B}}\in{\mathbb{M}}_{{\mathbf{r}}},\|{\mathbf{A}}-{\mathbf{M}}^{*}\|_{\rm{F}},\|{\mathbf{B}}\|_{\rm{F}}\leq
1}|\frac{1}{n}\sum_{i=1}^{n}\langle{\mathbf{A}}-{\mathbf{M}}^{*},{\mathbf{X}}_{i}\rangle\langle{\mathbf{B}},{\mathbf{X}}_{i}\rangle-\langle{\mathbf{A}}-{\mathbf{M}}^{*},{\mathbf{B}}\rangle|\lesssim\sqrt{\frac{\sum_{j=1}^{m}d_{j}r_{j}+r_{1}r_{2}\cdots
r_{m}}{n}},$

by which the first term could be bounded with:

$\begin{split}&~{}~{}~{}~{}|\langle(\nabla L-{\mathbb{E}}_{\xi}\nabla
L_{n})({\mathbf{C}}^{(0)}\times_{j\in[m]}{\mathbf{U}}_{j}^{(0)}),({\mathbf{C}}^{(0)}-{\mathbf{C}}^{*})\times_{j\in[m]}{\mathbf{U}}_{j}^{(0)}\rangle|\\\
&\leq c_{0}\sqrt{\frac{\sum_{j=1}^{m}d_{j}r_{j}+r_{1}r_{2}\cdots
r_{m}}{n}}\|{\mathbf{M}}_{0}-{\mathbf{M}}^{*}\|_{\rm{F}}\|{\mathbf{C}}^{(0)}-{\mathbf{C}}^{*}\|_{\rm{F}}.\end{split}$
(41)

On the other hand,

$\displaystyle\langle({\mathbb{E}}_{y}\nabla L_{n}-\nabla
L_{n})({\mathbf{C}}^{(0)}$
$\displaystyle\times_{j\in[d]}{\mathbf{U}}_{j}^{(0)}),({\mathbf{C}}^{(0)}-{\mathbf{C}}^{*})\times_{j\in[d]}{\mathbf{U}}_{j}^{(0)T}\rangle=\langle\frac{1}{n}\sum_{i=1}^{n}\xi_{i}{\mathbf{X}}_{i},({\mathbf{C}}^{(0)}-{\mathbf{C}}^{*})\times_{j\in[d]}{\mathbf{U}}_{j}^{(0)}\rangle.$
(42)

First fix the noise term $\\{\xi_{i}\\}_{i=1}^{n}$. Then with a standard
covering argument, we have with probability exceeding
$1-c_{1}^{\prime}\exp(-(\sum_{j=1}^{m}r_{j}d_{j}+r_{1}r_{2}\cdots r_{m}))$,

$\displaystyle\sup_{{\mathbf{A}}\in{\mathbb{M}}_{{\mathbf{r}}},\|{\mathbf{A}}\|_{\rm{F}}\leq
1}\langle\sum_{i}^{n}\xi_{i}{\mathbf{X}}_{i},{\mathbf{A}}\rangle\leq
c_{1}\sqrt{\sum_{j=1}^{m}d_{j}r_{j}+r_{1}r_{2}\cdots
r_{m}}\left(\sum_{i=1}^{n}\xi_{i}^{2}\right)^{1/2},$ (43)

where $c_{1},c_{1}^{\prime}>0$ are some constants. By Lemma 18, we obtain
upper bound of sum of heavy-tailed variables,

$\displaystyle{\mathbb{P}}\left(\sum_{i=1}^{n}\xi_{i}^{2}\geq
3n\|\xi\|_{2+\varepsilon}^{2}\right)\leq
1-c_{2}^{\prime}n^{-\min\\{\varepsilon/2,1\\}}.$ (44)

Insert Equation 43, 44 into Equation 42 and it leads to

$\displaystyle|\langle({\mathbb{E}}_{y}\nabla L_{n}-\nabla
L_{n})({\mathbf{C}}^{(0)}\times_{j\in[m]}{\mathbf{U}}_{j}^{(0)}),({\mathbf{C}}^{(0)}-{\mathbf{C}}^{*})\times_{j\in[m]}{\mathbf{U}}_{i}^{(0)T}\rangle|$
$\displaystyle\hskip 85.35826pt\leq
2\sqrt{\frac{\sum_{j=1}^{m}d_{j}r_{j}+r_{1}\cdots
r_{m}}{n}}\cdot\|\xi\|_{2+\varepsilon}\|{\mathbf{C}}^{(0)}-{\mathbf{C}}^{*}\|_{\rm{F}}.$
(45)

with probability exceeding
$1-c_{1}^{\prime}\exp(-(\sum_{j=1}^{m}r_{j}d_{j}+r_{1}r_{2}\cdots
r_{m}))-c_{2}^{\prime}n^{-\min\\{\varepsilon/2,1\\}}$. Then use Equation 41, D
to bound the first term on the R.H.S. of Equation D:

$\displaystyle|\beta_{1}|$ $\displaystyle\leq
C_{1}\sqrt{\frac{\sum_{j=1}^{m}d_{j}r_{j}+r_{1}r_{2}\cdots
r_{m}}{n}}(\|{\mathbf{M}}_{0}-{\mathbf{M}}^{*}\|_{\rm{F}}+\|\xi\|_{2+\varepsilon})\|{\mathbf{C}}^{(0)}-{\mathbf{C}}^{*}\|_{\rm{F}}$
$\displaystyle\leq C_{1}\sqrt{\frac{\sum_{j=1}^{m}d_{j}r_{j}+r_{1}r_{2}\cdots
r_{m}}{n}}\bigg{(}\|{\mathbf{C}}^{(0)}-{\mathbf{C}}^{*}\|_{\rm{F}}+m\bar{\lambda}\max_{j=1,\ldots,m}d({\mathbf{U}}_{j}^{(0)},{\mathbf{U}}_{j}^{*})+\|\xi\|_{2+\varepsilon}\bigg{)}\|{\mathbf{C}}^{(0)}-{\mathbf{C}}^{*}\|_{\rm{F}}.$
(46)

Now we consider $\beta_{2}$. Notice that

$\displaystyle\|\nabla_{{\mathbf{C}}}L({\mathbf{C}}^{*}\times_{j\in[m]}{\mathbf{U}}_{j}^{(0)})\|_{\rm{F}}$
$\displaystyle=\|{\mathbf{C}}^{*}(\times_{j\in[m]}{\mathbf{U}}_{j}^{(0)}-\times_{j\in[m]}{\mathbf{U}}_{j}^{*})\times_{k\in[m]}{\mathbf{U}}_{k}^{(0)\top}\|_{\rm{F}}\leq
m\bar{\lambda}\max_{j=1,\ldots,m}d({\mathbf{U}}_{j}^{(0)},{\mathbf{U}}_{j}^{*}).$

Therefore

$\displaystyle|\beta_{2}|\leq\|\nabla_{{\mathbf{C}}}L({\mathbf{C}}^{*}\times_{i}{\mathbf{U}}_{i}^{(0)})\|_{\rm{F}}\|{\mathbf{C}}^{(0)}-{\mathbf{C}}^{*}\|_{\rm{F}}\leq
m\bar{\lambda}\max_{j=1,\ldots,m}d({\mathbf{U}}_{j}^{(0)},{\mathbf{U}}_{j}^{*})\|{\mathbf{C}}^{(0)}-{\mathbf{C}}^{*}\|_{\rm{F}}.$
(47)

Now from (D), (D) and (47), we obtain

$\displaystyle\|{\mathbf{C}}^{(0)}-{\mathbf{C}}^{*}\|_{\rm{F}}\leq
C_{2}\sqrt{\frac{\sum_{j=1}^{m}d_{j}r_{j}+r_{1}r_{2}\cdots
r_{m}}{n}}\|\xi\|_{2+\varepsilon}+C_{3}m\bar{\lambda}\max_{j=1,\ldots,m}d({\mathbf{U}}_{j}^{(0)},{\mathbf{U}}_{j}^{*}).$

Now we go back to (39), and we have

$\displaystyle\|{\mathbf{M}}_{0}-{\mathbf{M}}^{*}\|_{\rm{F}}\leq
C_{2}\sqrt{\frac{\sum_{j=1}^{m}d_{j}r_{j}+r_{1}r_{2}\cdots
r_{m}}{n}}\|\xi\|_{2+\varepsilon}+(C_{3}+1)m\bar{\lambda}\max_{j=1,\ldots,m}d({\mathbf{U}}_{j}^{(0)},{\mathbf{U}}_{j}^{*}).$

Now from (38) and under the sample size condition and SNR condition, we
verified for some contant $C_{4}>0$,

$\|{\mathbf{M}}_{0}-{\mathbf{M}}^{*}\|_{\rm{F}}\leq C_{4}\underline{\lambda},$

holds with probability over
$1-c_{1}^{\prime}\exp(-(\sum_{j=1}^{m}r_{j}d_{j}+r_{1}r_{2}\cdots
r_{m}))-c_{2}^{\prime}n^{-\min\\{\varepsilon/2,1\\}}-c_{3}^{\prime}m\bar{d}^{-10}$.

######  Lemma 13.

Let ${\mathbf{M}}\in{\mathbb{R}}^{d_{1}\times d_{2}}$ be a rank $r$ matrix and
suppose $d_{1}\leq d_{2}$. Suppose $\\{{\mathbf{X}}_{i}\\}_{i=1}^{n}$ is a
sequence of i.i.d. sensing matrices with i.i.d. standard normal entries and
$\\{\xi_{i}\\}_{i=1}^{n}$ is a sequence of i.i.d. noise and then observe

$Y_{i}=\langle{\mathbf{M}},{\mathbf{X}}_{i}\rangle+\xi_{i},\,i=1,\cdots,n.$

Denote $\sigma_{1}=\|{\mathbf{M}}\|$ and $d=d_{1}\vee d_{2}$. Suppose the
following condition is satisfied:

  * (C1)

Sample size satisfies: $n\geq\sqrt{rd_{1}d_{2}}\log d$.

  * (C2)

Exists constant $\varepsilon>0$, such that
${\mathbb{E}}|\xi_{1}|^{2+\varepsilon}<+\infty$. Denote
$\|\xi_{1}\|_{2+\varepsilon}:=({\mathbb{E}}|\xi_{1}|^{2+\varepsilon})^{1/(2+\varepsilon)}$.

Truncate $Y_{i}$ with
$\tau=\frac{n^{1/2}}{(d_{1}d_{2})^{1/4}}(\sqrt{r}\sigma_{1}+\gamma)$,
$\tilde{Y}_{i}=\text{sign}(Y_{i})(|Y_{i}|\vee\tau)$ and define

$\tilde{{\mathbf{N}}}:=\frac{1}{n(n-1)}\sum_{1\leq i\neq i^{\prime}\leq
n}\tilde{Y}_{i}\tilde{Y}_{i^{\prime}}({\mathbf{X}}_{i}{\mathbf{X}}_{i^{\prime}}^{\top}+{\mathbf{X}}_{i^{\prime}}{\mathbf{X}}_{i}^{\top}).$

Then there exist some constants $c_{0},C_{1},C_{2}>0$, such that with
probability exceeding $1-c_{0}d^{-10}$,

$\|\tilde{\mathbf{N}}-{\mathbf{M}}{\mathbf{M}}^{T}\|\leq
C_{1}\frac{(d_{1}d_{2})^{1/4}\sqrt{\log
d}}{\sqrt{n}}\sqrt{r}\sigma_{1}^{2}+C_{2}\frac{(d_{1}d_{2})^{1/2}\sqrt{\log
d}}{n}\|\xi\|_{2+\varepsilon}^{2}.$

###### Proof.

For convenience, let $Y,{\mathbf{X}}$ be i.i.d. with
$\\{Y_{i},{\mathbf{X}}_{i}\\}_{i=1}^{n}$ and
$\tilde{Y}:=\text{sign}(Y)\cdot(|Y|\vee\tau)$. Notice that $(2+\varepsilon)$
moment of $Y$ could be bounded with

$\displaystyle\|Y\|_{2+\varepsilon}:=({\mathbb{E}}|Y|^{2+\varepsilon})^{1/(2+\varepsilon)}\leq\sqrt{2+\varepsilon}\|{\mathbf{M}}\|_{\rm{F}}+\|\xi\|_{2+\varepsilon}\leq
c_{0}\sqrt{r}\sigma_{1}+\|\xi\|_{2+\varepsilon}.$ (48)

Notice that

$\displaystyle\|\tilde{\mathbf{N}}-{\mathbf{M}}{\mathbf{M}}^{\top}\|\leq\|\tilde{{\mathbf{N}}}-{\mathbb{E}}\tilde{Y}{\mathbf{X}}\cdot{\mathbb{E}}\tilde{Y}{\mathbf{X}}^{\top}\|+\|{\mathbb{E}}\tilde{Y}{\mathbf{X}}\cdot{\mathbb{E}}\tilde{Y}{\mathbf{X}}^{\top}-{\mathbf{M}}{\mathbf{M}}^{\top}\|.$
(49)

By decoupling techniques [De la Pena and Giné, 2012], it has for any $t>0$,

${\mathbb{P}}(\|\tilde{{\mathbf{N}}}-{\mathbb{E}}\tilde{Y}{\mathbf{X}}\cdot{\mathbb{E}}\tilde{Y}{\mathbf{X}}^{\top}\|\geq
t)\leq
15{\mathbb{P}}(\|\hat{{\mathbf{N}}}-{\mathbb{E}}\tilde{Y}{\mathbf{X}}\cdot{\mathbb{E}}\tilde{Y}{\mathbf{X}}^{\top}\|\geq
15t),$

where $\hat{\mathbf{N}}=\frac{1}{2n(n-1)}\sum_{1\leq i\neq j\leq
n}\tilde{Y}_{i}\tilde{Y}_{j}^{\prime}({\mathbf{X}}_{i}{\mathbf{X}}_{j}^{\prime
T}+{\mathbf{X}}_{j}^{\prime}{\mathbf{X}}_{i}^{T})$ and
$\\{({\mathbf{X}}_{i}^{\prime},\tilde{Y}_{i}^{\prime})\\}_{i=1}^{n}$ is an
independent copy of $\\{({\mathbf{X}}_{i},\tilde{Y}_{i})\\}_{i=1}^{n}$ such
that

$Y_{i}^{\prime}=\langle{\mathbf{M}},{\mathbf{X}}_{i}^{\prime}\rangle+\xi_{i}^{\prime},\quad
i=1,\cdots,n.$

Denote

$\displaystyle\boldsymbol{\Delta}_{1}:=\frac{1}{n}\sum_{i=1}^{n}\tilde{Y}_{i}{\mathbf{X}}_{i}-{\mathbb{E}}\tilde{Y}{\mathbf{X}},\quad\boldsymbol{\Delta}_{2}:=\frac{1}{n}\sum_{j=1}^{n}\tilde{Y}_{j}^{\prime}{\mathbf{X}}_{j}^{\prime}-{\mathbb{E}}\tilde{Y}{\mathbf{X}}.$

Then the first term of Equation 49 could be expressed in the way of

$\displaystyle\hat{\mathbf{N}}-{\mathbb{E}}\tilde{Y}{\mathbf{X}}\cdot{\mathbb{E}}\tilde{Y}{\mathbf{X}}^{\top}$
$\displaystyle=\frac{n}{2(n-1)}\bigg{(}\boldsymbol{\Delta}_{1}\boldsymbol{\Delta}_{2}^{T}+\boldsymbol{\Delta}_{2}\boldsymbol{\Delta}_{1}^{T}+(\boldsymbol{\Delta}_{1}+\boldsymbol{\Delta}_{2})\cdot{\mathbb{E}}\tilde{Y}{\mathbf{X}}^{\top}+{\mathbb{E}}\tilde{Y}{\mathbf{X}}\cdot(\boldsymbol{\Delta}_{1}+\boldsymbol{\Delta}_{2})^{\top}\bigg{)}$
$\displaystyle~{}~{}~{}~{}+\frac{1}{n-1}\bigg{(}\frac{1}{2n}\sum_{i=1}^{n}\tilde{Y}_{i}\tilde{Y}_{i}^{\prime}({\mathbf{X}}_{i}{\mathbf{X}}_{i}^{\prime
T}+{\mathbf{X}}_{i}^{\prime}{\mathbf{X}}_{i}^{T}-2{\mathbb{E}}\tilde{Y}{\mathbf{X}}\cdot{\mathbb{E}}\tilde{Y}{\mathbf{X}}^{\top})\bigg{)}.$

Step 1. Bound $\|\boldsymbol{\Delta}_{1}\|,\|\boldsymbol{\Delta}_{2}\|$. The
proof follows Bernstein’s inequality Theorem 9. Note that for any
${\mathbf{u}}\in\SS^{d_{1}-1}$, ${\mathbf{v}}\in\SS^{d_{2}-1}$,
$|{\mathbf{u}}^{\top}{\mathbb{E}}\tilde{Y}_{i}{\mathbf{X}}_{i}{\mathbf{v}}|\leq\tau{\mathbb{E}}|{\mathbf{u}}^{\top}{\mathbf{X}}_{i}{\mathbf{v}}|\leq
2\tau$, which implies

$\|{\mathbb{E}}\tilde{Y}_{i}{\mathbf{X}}_{i}\|\leq 2\tau.$

Furthermore, we have for some constant $c_{2}>0$,

$\big{\|}\|\tilde{Y}_{i}{\mathbf{X}}_{i}-{\mathbb{E}}\tilde{Y}_{i}{\mathbf{X}}_{i}\|\big{\|}_{\psi_{2}}\leq
c_{2}\tau\sqrt{d}.$

Then consider
$\|{\mathbb{E}}\tilde{Y}_{i}^{2}{\mathbf{X}}_{i}{\mathbf{X}}_{i}^{T}\|$:

$\displaystyle\|{\mathbb{E}}\tilde{Y}_{i}^{2}{\mathbf{X}}_{i}{\mathbf{X}}_{i}^{T}\|$
$\displaystyle\leq{\mathbb{E}}\|\tilde{Y}_{i}^{2}{\mathbf{X}}_{i}{\mathbf{X}}_{i}^{T}\|\leq({\mathbb{E}}|Y_{i}|^{2+\varepsilon})^{2/(2+\varepsilon)}({\mathbb{E}}\|{\mathbf{X}}_{i}\|^{2\cdot\frac{2+\varepsilon}{\varepsilon}})^{\frac{\varepsilon}{2+\varepsilon}}$
$\displaystyle\leq c_{2}\|Y\|_{2+\varepsilon}^{2}d.$

Then we have

$\displaystyle\|{\mathbb{E}}(\tilde{Y}_{i}{\mathbf{X}}_{i}-{\mathbb{E}}\tilde{Y}_{i}{\mathbf{X}}_{i})(\tilde{Y}_{i}{\mathbf{X}}_{i}-{\mathbb{E}}\tilde{Y}_{i}{\mathbf{X}}_{i})^{\top}\|$
$\displaystyle\leq\|{\mathbb{E}}\tilde{Y}_{i}^{2}{\mathbf{X}}_{i}{\mathbf{X}}_{i}^{T}\|\leq
c_{2}\|Y\|_{2+\varepsilon}^{2}d.$

Similarly,
$\|{\mathbb{E}}(\tilde{Y}_{i}{\mathbf{X}}_{i}-{\mathbb{E}}\tilde{Y}_{i}{\mathbf{X}}_{i})^{\top}(\tilde{Y}_{i}{\mathbf{X}}_{i}-{\mathbb{E}}\tilde{Y}_{i}{\mathbf{X}}_{i})\|$
could be bounded with $c_{2}\|Y\|_{2+\varepsilon}^{2}d$. Thus by Bernstein’s
inequality Theorem 9, the following equation holds with probability exceeding
$1-c_{4}d^{-10}$,

$\displaystyle\|\frac{1}{n}\sum_{i=1}^{n}\tilde{Y}_{i}{\mathbf{X}}_{i}-{\mathbb{E}}\tilde{Y}{\mathbf{X}}\|\leq
c_{3}\|Y\|_{2+\varepsilon}\sqrt{\frac{d\log
d}{n}}+c_{3}\tau\sqrt{d}\sqrt{\log\frac{c^{\prime}\tau}{\|Y\|_{2+\varepsilon}}}\cdot\frac{\log
d}{n},$

which finishes bounding $\|\boldsymbol{\Delta}_{1}\|$. It’s similar to
$\|\boldsymbol{\Delta}_{2}\|$ and with a union bound, the following equation
holds

$\displaystyle\max\\{\|\boldsymbol{\Delta}_{1}\|,\|\boldsymbol{\Delta}_{2}\|\\}\leq
c_{3}\|Y\|_{2+\varepsilon}\sqrt{\frac{d\log
d}{n}}+c_{3}\tau\sqrt{d}\sqrt{\log\frac{c^{\prime}\tau}{\|Y\|_{2+\varepsilon}}}\cdot\frac{\log
d}{n}$

with probability exceeding $1-2c_{4}d^{-10}$.

Step 2. Bound
$\|\boldsymbol{\Delta}_{1}\cdot{\mathbb{E}}\tilde{Y}{\mathbf{X}}^{T}\|,\|\boldsymbol{\Delta}_{2}\cdot{\mathbb{E}}\tilde{Y}{\mathbf{X}}^{T}\|$.
WLOG, we only consider
$\|\boldsymbol{\Delta}_{1}\cdot{\mathbb{E}}\tilde{Y}{\mathbf{X}}^{T}\|$ and
for convenience denote $\tilde{\mathbf{M}}={\mathbb{E}}\tilde{Y}{\mathbf{X}}$.
Recall that
$\boldsymbol{\Delta}_{1}\cdot{\mathbb{E}}\tilde{Y}{\mathbf{X}}^{T}=\boldsymbol{\Delta}_{1}\tilde{{\mathbf{M}}}^{T}=\frac{1}{n}\sum_{i=1}^{n}(\tilde{Y}_{i}{\mathbf{X}}_{i}-\tilde{{\mathbf{M}}})\tilde{{\mathbf{M}}}^{T}$.
The proof also follows Bernstein’s inequality Theorem 9. First, note that

${\mathbb{E}}[(\tilde{Y}_{i}{\mathbf{X}}_{i}-\tilde{{\mathbf{M}}})\tilde{{\mathbf{M}}}^{\top}]=0,\quad\big{\|}\|(\tilde{Y}_{i}{\mathbf{X}}_{i}-\tilde{{\mathbf{M}}})\tilde{{\mathbf{M}}}^{\top}\|\big{\|}_{\psi_{2}}\leq
c_{1}\tau\|\tilde{{\mathbf{M}}}\|\sqrt{d_{1}},$

which uses $\|\tilde{{\mathbf{M}}}\|\leq 2\tau$. Then consider
$\|{\mathbb{E}}\tilde{Y}_{i}^{2}{\mathbf{X}}_{i}\tilde{{\mathbf{M}}}^{T}\tilde{{\mathbf{M}}}{\mathbf{X}}_{i}^{T}\|$:

$\displaystyle\|{\mathbb{E}}\tilde{Y}_{i}^{2}{\mathbf{X}}_{i}\tilde{{\mathbf{M}}}^{T}\tilde{{\mathbf{M}}}{\mathbf{X}}_{i}^{T}\|$
$\displaystyle\leq{\mathbb{E}}\|Y_{i}^{2}{\mathbf{X}}_{i}\tilde{{\mathbf{M}}}^{T}\tilde{{\mathbf{M}}}{\mathbf{X}}_{i}^{T}\|\leq({\mathbb{E}}|Y_{i}|^{2+\varepsilon})^{2/2+\varepsilon}({\mathbb{E}}\|\tilde{{\mathbf{M}}}{\mathbf{X}}_{i}^{\top}\|^{2\cdot\frac{2+\varepsilon}{\varepsilon}})^{\frac{\varepsilon}{2+\varepsilon}}.$

With standard $\varepsilon$-net techniques (see Vershynin [2018]), we have for
any $t>0$, $\|\tilde{{\mathbf{M}}}{\mathbf{X}}_{i}^{\top}\|\leq
c_{0}(\sqrt{d_{1}}+t)\|\tilde{{\mathbf{M}}}\|$ holds with probability at least
$1-2\exp(-t^{2})$ and
${\mathbb{E}}\|\tilde{{\mathbf{M}}}{\mathbf{X}}_{i}^{\top}\|\leq
c_{0}^{\prime}\sqrt{d_{1}}\|\tilde{{\mathbf{M}}}\|$. Then combined with
$\|\tilde{{\mathbf{M}}}\|=\|{\mathbb{E}}\tilde{Y}{\mathbf{X}}\|\leq
c_{1}^{\prime}\|Y\|_{2+\varepsilon}$, we have

$\displaystyle\|{\mathbb{E}}\tilde{Y}_{i}^{2}{\mathbf{X}}_{i}\tilde{{\mathbf{M}}}^{T}\tilde{{\mathbf{M}}}{\mathbf{X}}_{i}^{T}\|\leq
c_{2}\|Y\|_{2+\varepsilon}^{2}\|{\mathbf{M}}\|^{2}d_{1}.$

Thus we have

$\displaystyle\|{\mathbb{E}}((\tilde{Y}_{i}{\mathbf{X}}_{i}-\tilde{{\mathbf{M}}})\tilde{{\mathbf{M}}}^{T})((\tilde{Y}_{i}{\mathbf{X}}_{i}-\tilde{{\mathbf{M}}})\tilde{{\mathbf{M}}}^{T})^{T}\|$
$\displaystyle\leq\|{\mathbb{E}}\tilde{Y}_{i}^{2}{\mathbf{X}}_{i}\tilde{{\mathbf{M}}}^{T}\tilde{{\mathbf{M}}}{\mathbf{X}}_{i}^{T}\|\leq
c_{2}\|Y\|_{2+\varepsilon}^{2}\|\tilde{{\mathbf{M}}}\|^{2}d_{1}.$

Similarly, it has

$\displaystyle\|{\mathbb{E}}((\tilde{Y}_{i}{\mathbf{X}}_{i}-\tilde{{\mathbf{M}}})\tilde{{\mathbf{M}}}^{T})^{\top}((\tilde{Y}_{i}{\mathbf{X}}_{i}-\tilde{{\mathbf{M}}})\tilde{{\mathbf{M}}}^{T})\|$
$\displaystyle\leq\|{\mathbb{E}}\tilde{Y}_{i}^{2}\tilde{{\mathbf{M}}}{\mathbf{X}}_{i}^{\top}{\mathbf{X}}_{i}\tilde{{\mathbf{M}}}^{\top}\|\leq
c_{2}\|Y\|_{2+\varepsilon}^{2}\|\tilde{{\mathbf{M}}}\|^{2}d_{1}.$

By Bernstein’s inequality Theorem 9, with probability exceeding $1-2d^{-10}$,
the following equation holds

$\displaystyle\|\boldsymbol{\Delta}_{1}\tilde{{\mathbf{M}}}^{T}\|\leq
c_{3}\|Y\|_{2+\varepsilon}\|\tilde{{\mathbf{M}}}\|\sqrt{\frac{d_{1}\log
d}{n}}+c_{3}\tau\|\tilde{{\mathbf{M}}}\|\sqrt{d}_{1}\sqrt{\log\frac{\tau}{\|Y\|_{2+\varepsilon}}}\cdot\frac{\log
d}{n}$

Term $\|\boldsymbol{\Delta}_{2}\tilde{{\mathbf{M}}}^{T}\|$ could be bounded in
a similar fashion. Take a union bound and then we get with probability
exceeding $1-4d^{-10}$,

$\begin{split}\max&\\{\|\boldsymbol{\Delta}_{1}\tilde{{\mathbf{M}}}^{T}\|,\|\boldsymbol{\Delta}_{2}\tilde{{\mathbf{M}}}^{T}\|\\}\\\
&\leq c_{3}\|Y\|_{2+\varepsilon}\|\tilde{{\mathbf{M}}}\|\sqrt{\frac{d_{1}d\log
d}{n}}+c_{3}\tau\|\tilde{{\mathbf{M}}}\|\sqrt{d}_{1}\sqrt{\log\frac{\tau}{\|Y\|_{2+\varepsilon}}}\cdot\frac{\log
d}{n}\end{split}$ (50)

Step 3. Bound $\|\boldsymbol{\Delta}_{1}\boldsymbol{\Delta}_{2}^{T}\|$. We
shall bound $\|\boldsymbol{\Delta}_{1}\boldsymbol{\Delta}_{2}^{T}\|$ under
event

${\boldsymbol{\mathcal{E}}}_{1}=\\{\|\boldsymbol{\Delta}_{2}\|\leq
c_{3}\|Y\|_{2+\varepsilon}\sqrt{\frac{d\log
d}{n}}+c_{3}\tau\sqrt{d}\sqrt{\log\frac{c^{\prime}\tau}{\|Y\|_{2+\varepsilon}}}\cdot\frac{\log
d}{n}\\},$

which is verified to hold with probability over $1-4d^{-10}$ in Step 1.
Replace $\tilde{{\mathbf{M}}}$ with $\boldsymbol{\Delta}_{2}$ of
$\|\boldsymbol{\Delta}_{1}\boldsymbol{\Delta}_{2}\|$ in Step 2 and follow Step
2 procedure. Then we get with probability exceeding $1-2d^{-10}$,

$\begin{split}&\|\boldsymbol{\Delta}_{1}\boldsymbol{\Delta}_{2}^{T}\|\leq
c_{4}\bigg{(}\|Y\|_{2+\varepsilon}\sqrt{\frac{d_{1}\log
d}{n}}+\tau\sqrt{d_{1}}\sqrt{\log\frac{\tau}{\|Y\|_{2+\varepsilon}}}\cdot\frac{\log
d}{n}\bigg{)}\\\
&{~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}}\times\bigg{(}\|Y\|_{2+\varepsilon}\sqrt{\frac{d\log
d}{n}}+\tau\sqrt{d}\sqrt{\log\frac{c^{\prime}\tau}{\|Y\|_{2+\varepsilon}}}\cdot\frac{\log
d}{n}\bigg{)}.\end{split}$ (51)

Step 4. Bound
$\|\frac{1}{n}\sum_{i=1}^{n}\tilde{Y}_{i}\tilde{Y}_{i}^{\prime}{\mathbf{X}}_{i}{\mathbf{X}}_{i}^{\prime
T}-\tilde{{\mathbf{M}}}\tilde{{\mathbf{M}}}^{T}\|$. Notice that

$\frac{1}{n}\sum_{i=1}^{n}\tilde{Y}_{i}\tilde{Y}_{i}^{\prime}{\mathbf{X}}_{i}{\mathbf{X}}_{i}^{\prime
T}-\tilde{{\mathbf{M}}}\tilde{{\mathbf{M}}}^{T}=\frac{1}{n}\sum_{i=1}^{n}\tilde{Y}_{i}{\mathbf{X}}_{i}(\tilde{Y}_{i}^{\prime}{\mathbf{X}}_{i}^{\prime}-\tilde{{\mathbf{M}}})^{T}+\frac{1}{n}\sum_{i=1}^{n}(\tilde{Y}_{i}{\mathbf{X}}_{i}-\tilde{{\mathbf{M}}})\tilde{{\mathbf{M}}}^{T}.$

Note that the second term
$\boldsymbol{\Delta}_{1}\tilde{{\mathbf{M}}}^{T}=\frac{1}{n}\sum_{i=1}^{n}(Y_{i}{\mathbf{X}}_{i}-\tilde{{\mathbf{M}}})\tilde{{\mathbf{M}}}^{T}$
is analyzed in Step 2. Analysis of the first term also follows Bernstein’s
inequality Theorem 9. Notice that

${\mathbb{E}}[\tilde{Y}_{i}{\mathbf{X}}_{i}(\tilde{Y}_{i}^{\prime}{\mathbf{X}}_{i}^{\prime}-\tilde{{\mathbf{M}}})^{T}]=0,\quad\big{\|}\|\tilde{Y}_{i}{\mathbf{X}}_{i}(\tilde{Y}_{i}^{\prime}{\mathbf{X}}_{i}^{\prime}-\tilde{{\mathbf{M}}})^{T}\|\big{\|}_{\psi_{2}}\leq
c_{2}\tau^{2}d,$
$\displaystyle\|{\mathbb{E}}\tilde{Y}_{i}^{2}{\mathbf{X}}_{i}(\tilde{Y}_{i}^{\prime}{\mathbf{X}}_{i}^{\prime}-\tilde{{\mathbf{M}}})^{T}(\tilde{Y}_{i}^{\prime}{\mathbf{X}}_{i}^{\prime}-\tilde{{\mathbf{M}}}){\mathbf{X}}_{i}^{T}\|$
$\displaystyle\leq\|{\mathbb{E}}\tilde{Y}_{i}^{2}\tilde{Y}_{i}^{{}^{\prime}2}{\mathbf{X}}_{i}{\mathbf{X}}_{i}^{{}^{\prime}\top}{\mathbf{X}}_{i}^{{}^{\prime}}{\mathbf{X}}_{i}^{\top}\|$
$\displaystyle\leq({\mathbb{E}}|\tilde{Y}_{i}|^{2+\varepsilon}|\tilde{Y}_{i}^{{}^{\prime}}|^{2+\varepsilon})^{2/(2+\varepsilon)}({\mathbb{E}}\|{\mathbf{X}}_{i}^{{}^{\prime}}{\mathbf{X}}_{i}^{\top}\|^{2\cdot\frac{2+\varepsilon}{\varepsilon}})^{\varepsilon/(2+\varepsilon)}$
$\displaystyle\leq c_{1}\|\tilde{Y}_{i}\|_{2+\varepsilon}^{4}d_{1}d_{2},$
$\displaystyle\|{\mathbb{E}}\tilde{Y}_{i}^{2}(\tilde{Y}_{i}^{\prime}{\mathbf{X}}_{i}^{\prime}-\tilde{{\mathbf{M}}}){\mathbf{X}}_{i}^{T}{\mathbf{X}}_{i}(\tilde{Y}_{i}^{\prime}{\mathbf{X}}_{i}^{\prime}-\tilde{{\mathbf{M}}})^{T}\|$
$\displaystyle\leq\|{\mathbb{E}}\tilde{Y}_{i}^{2}\tilde{Y}_{i}^{{}^{\prime}2}{\mathbf{X}}_{i}^{{}^{\prime}}{\mathbf{X}}_{i}^{\top}{\mathbf{X}}_{i}{\mathbf{X}}_{i}^{{}^{\prime}\top}\|$
$\displaystyle\leq({\mathbb{E}}|\tilde{Y}_{i}|^{2+\varepsilon}|\tilde{Y}_{i}^{{}^{\prime}}|^{2+\varepsilon})^{2/(2+\varepsilon)}({\mathbb{E}}\|{\mathbf{X}}_{i}{\mathbf{X}}_{i}^{{}^{\prime}\top}\|^{2\cdot\frac{2+\varepsilon}{\varepsilon}})^{\varepsilon/(2+\varepsilon)}$
$\displaystyle\leq c_{1}\|Y_{i}\|_{2+\varepsilon}^{4}d_{1}d_{2}.$

Then by Bernstein’s inequality Theorem 9, we have with probability exceeding
$1-2d^{-10}$,

$\displaystyle\|\frac{1}{n}\sum_{i=1}^{n}\tilde{Y}_{i}{\mathbf{X}}_{i}(\tilde{Y}_{i}^{\prime}{\mathbf{X}}_{i}^{\prime}-\tilde{{\mathbf{M}}})^{T}\|\leq
c_{3}\|Y\|_{2+\varepsilon}^{2}\sqrt{d_{1}d_{2}}\sqrt{\frac{\log
d}{n}}+c_{3}\tau^{2}d\sqrt{\log\frac{\tau^{2}d}{\|Y\|_{2+\varepsilon}^{2}\sqrt{d_{1}d_{2}}}}\cdot\frac{\log
d}{n}.$ (52)

Step 5. Bound
$\|{\mathbb{E}}\tilde{Y}{\mathbf{X}}\cdot{\mathbb{E}}\tilde{Y}{\mathbf{X}}^{\top}-{\mathbf{M}}{\mathbf{M}}^{\top}\|$.
Notice that
$\|{\mathbf{M}}{\mathbf{M}}^{T}-\tilde{{\mathbf{M}}}\tilde{{\mathbf{M}}}^{T}\|\leq\|{\mathbf{M}}-\tilde{{\mathbf{M}}}\|(\|{\mathbf{M}}\|+\|\tilde{{\mathbf{M}}}\|)$.
Furthermore, we have for any ${\mathbf{u}}\in\SS^{d_{1}-1}$,
${\mathbf{v}}\in\SS^{d_{2}-1}$,

$\displaystyle|{\mathbf{u}}^{\top}({\mathbf{M}}-\tilde{{\mathbf{M}}}){\mathbf{v}}|$
$\displaystyle\leq{\mathbb{E}}|Y|\cdot
1_{|Y|>\tau}\cdot|{\mathbf{u}}^{\top}{\mathbf{X}}{\mathbf{v}}|$
$\displaystyle\leq\tau^{-1}{\mathbb{E}}|Y|^{2}|{\mathbf{u}}^{\top}{\mathbf{X}}{\mathbf{v}}|$
$\displaystyle\leq\tau^{-1}\|Y\|_{2+\varepsilon}^{2}\cdot({\mathbb{E}}|{\mathbf{u}}^{\top}{\mathbf{X}}{\mathbf{v}}|^{1+2/\varepsilon})^{\varepsilon/(2+\varepsilon)}\leq
c_{1}\tau^{-1}\|Y\|_{2+\varepsilon}^{2},$

where $c_{1}>0$ is some constant and it implies
$\|{\mathbf{M}}-\tilde{{\mathbf{M}}}\|\leq
c_{1}\tau^{-1}\|Y\|_{2+\varepsilon}^{2}$. Then, we have

$\|{\mathbf{M}}\|=\sigma_{1},\quad\|\tilde{{\mathbf{M}}}\|\leq\|{\mathbf{M}}\|+\|{\mathbf{M}}-\tilde{{\mathbf{M}}}\|\leq\sigma_{1}+c_{1}\tau^{-1}\|Y\|_{2+\varepsilon}^{2}.$

Therefore,

$\displaystyle\|{\mathbf{M}}{\mathbf{M}}^{\top}-\tilde{{\mathbf{M}}}\tilde{{\mathbf{M}}}^{\top}\|\leq
c_{1}\tau^{-1}\|Y\|_{2+\varepsilon}^{2}\left(2\sigma_{1}+c_{1}\tau^{-1}\|Y\|_{2+\varepsilon}^{2}\right).$
(53)

Step 6. Put everything together. Combine Equation 49 with Equation 50, 51, 52
and 53 and then we get with probability exceeding $1-c_{0}d^{-10}$,

$\displaystyle\quad\|\tilde{\mathbf{N}}-{\mathbf{M}}{\mathbf{M}}^{T}\|$
$\displaystyle\leq\frac{n}{n-1}\bigg{(}\|\boldsymbol{\Delta}_{1}\boldsymbol{\Delta}_{2}^{\top}\|+2\|\boldsymbol{\Delta}_{1}\cdot{\mathbb{E}}\tilde{Y}{\mathbf{X}}^{\top}\|\bigg{)}+\frac{1}{n-1}\|\sum_{i=1}^{n}\tilde{Y}_{i}\tilde{Y}_{i}^{\prime}{\mathbf{X}}_{i}{\mathbf{X}}_{i}^{{}^{\prime}\top}-{\mathbb{E}}\tilde{Y}{\mathbf{X}}\cdot{\mathbb{E}}\tilde{Y}{\mathbf{X}}^{\top}\|+\|{\mathbb{E}}\tilde{Y}{\mathbf{X}}\cdot{\mathbb{E}}\tilde{Y}{\mathbf{X}}^{\top}-{\mathbf{M}}{\mathbf{M}}^{\top}\|$
$\displaystyle\leq 2\bigg{(}\|Y\|_{2+\varepsilon}\sqrt{\frac{d_{1}\log
d}{n}}+\tau\sqrt{d_{1}}\sqrt{\log\frac{\tau}{\|Y\|_{2+\varepsilon}}}\cdot\frac{\log
d}{n}\bigg{)}\bigg{(}\|Y\|_{2+\varepsilon}\sqrt{\frac{d\log
d}{n}}+\tau\sqrt{d}\sqrt{\log\frac{c^{\prime}\tau}{\|Y\|_{2+\varepsilon}}}\cdot\frac{\log
d}{n}\bigg{)}$
$\displaystyle~{}~{}~{}~{}+3\|Y\|_{2+\varepsilon}\|\tilde{{\mathbf{M}}}\|\sqrt{\frac{d_{1}\log
d}{n}}+3\tau\|\tilde{{\mathbf{M}}}\|\sqrt{d}_{1}\sqrt{\log\frac{\tau}{\|\tilde{{\mathbf{M}}}\|}}\cdot\frac{\log
d}{n}+c_{1}\tau^{-1}\|Y\|_{2+\varepsilon}^{2}\left(2\sigma_{1}+c_{1}\tau^{-1}\|Y\|_{2+\varepsilon}^{2}\right)$
$\displaystyle~{}~{}~{}~{}+\frac{1}{n-1}\bigg{(}\|Y\|_{2+\varepsilon}^{2}\sqrt{d_{1}d_{2}}\sqrt{\frac{\log
d}{n}}+\tau^{2}d\sqrt{\frac{\tau^{2}d}{\|Y\|_{2+\varepsilon}^{2}\sqrt{d_{1}d_{2}}}}\cdot\frac{\log
d}{n}\bigg{)}.$

Insert
$\|\tilde{{\mathbf{M}}}\|\leq\sigma_{1}+c_{1}\tau^{-1}\|Y\|_{2+\varepsilon}^{2}$,
$\|Y\|_{2+\varepsilon}\leq c_{0}\sqrt{r}\sigma_{1}+\|\xi\|_{2+\varepsilon}$
and take
$\tau\asymp\sqrt{n}(c_{0}\sqrt{r}\sigma_{1}+\|\xi\|_{2+\varepsilon})\left(d_{1}d_{2}\right)^{-1/4}$.
Also, with sample size $n\geq\sqrt{d_{1}d_{2}}\log d$, we finally have

$\displaystyle\|\tilde{\mathbf{N}}-{\mathbf{M}}{\mathbf{M}}^{T}\|\leq
C_{1}\frac{(d_{1}d_{2})^{1/4}\sqrt{\log
d}}{\sqrt{n}}\sqrt{r}\sigma_{1}^{2}+C_{2}\frac{(d_{1}d_{2})^{1/2}\sqrt{\log
d}}{n}\|\xi\|_{2+\varepsilon}^{2},$

where $C_{1},C_{2}>0$ are some constants. ∎

##  Appendix E Technical Lemmas

######  Lemma 14 (Partial Frobenius Norm, Lemma 28 of Tong et al. [2021a]).

Define partial Frobenius norm of matrix
${\mathbf{M}}\in\mathbb{R}^{d_{1}\times d_{2}}$ to be

$\|{\mathbf{M}}\|_{\rm{F},r}:=\sqrt{\sum_{i=1}^{r}\sigma_{i}^{2}({\mathbf{M}})}=\|{\rm
SVD}_{r}({\mathbf{M}})\|_{\rm{F}}.$

For any ${\mathbf{M}},\hat{{\mathbf{M}}}\in\mathbb{R}^{d_{1}\times d_{2}}$
with $\operatorname{rank}(\hat{{\mathbf{M}}})\leq r$, one has

$|\langle{\mathbf{M}},\hat{{\mathbf{M}}}\rangle|\leq\|{\mathbf{M}}\|_{\rm{F},r}\|\hat{\mathbf{M}}\|_{\rm{F}}.$
(54)

For any ${\mathbf{M}}\in\mathbb{R}^{d_{1}\times d_{2}}$,
${\mathbf{V}}\in\mathbb{R}^{d_{1}\times r}$, one has

$\|{\mathbf{M}}{\mathbf{V}}\|_{\rm{F}}\leq\|{\mathbf{M}}\|_{\rm{F},r}\|{\mathbf{V}}\|.$
(55)

######  Lemma 15.

(Frobenius norm of projected sub-gradient) Let
${\mathbf{M}}\in{\mathbb{R}}^{d_{1}\times d_{2}}$ be a matrix with rank at
most $r$. Suppose $\mathbf{G}\in\partial f({\mathbf{M}})$ is the sub-gradient
at ${\mathbf{M}}$ and $\mathbb{T}$ is the tangent space for
${\mathbb{M}}_{\mathbf{r}}$ at ${\mathbf{M}}$. Then we have

$\|\mathcal{P}_{\mathbb{T}}(\mathbf{G})\|_{\mathrm{F}}\leq\sqrt{2}\|{\mathbf{G}}\|_{\rm{F},r}.$

###### Proof.

Notice that

$\displaystyle\|{\mathcal{P}}_{{\mathbb{T}}}({\mathbf{G}})\|_{\rm{F}}^{2}=\|{\mathbf{U}}{\mathbf{U}}^{T}{\mathbf{G}}\|_{\rm{F}}^{2}+\|({\mathbf{I}}-{\mathbf{U}}{\mathbf{U}}^{T}){\mathbf{G}}{\mathbf{V}}{\mathbf{V}}^{T}\|_{\rm{F}}^{2}.$

Then by properties of partial Frobenius norm Lemma 55, one has

$\displaystyle\|{\mathbf{U}}{\mathbf{U}}^{T}{\mathbf{G}}\|_{\rm{F}}=\|{\mathbf{U}}^{T}{\mathbf{G}}\|_{\rm{F}}$
$\displaystyle\leq\|{\mathbf{G}}\|_{\rm{F},r}\|{\mathbf{U}}\|=\|{\mathbf{G}}\|_{\rm{F},r},$
$\displaystyle\|({\mathbf{I}}-{\mathbf{U}}{\mathbf{U}}^{T}){\mathbf{G}}{\mathbf{V}}{\mathbf{V}}^{T}\|_{\rm{F}}$
$\displaystyle\leq\|{\mathbf{G}}\|_{\rm{F},r},$

which implies $\|{\mathcal{P}}_{{\mathbb{T}}}({\mathbf{G}})\|_{\rm{F}}^{2}\leq
2\|{\mathbf{G}}\|_{\rm{F},r}^{2}$. ∎

######  Lemma 16.

(Matrix Perturbation) Suppose matrix
${\mathbf{M}}^{*}\in\mathbb{R}^{d_{1}\times d_{2}}$ has rank $r$ and has
singular value decomposition
${\mathbf{M}}^{*}=\mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^{\top}$ where
$\boldsymbol{\Sigma}=\operatorname{diag}\\{\sigma_{1},\sigma_{2},\cdots,\sigma_{r}\\}$
and $\sigma_{1}\geq\sigma_{2}\geq\cdots\geq\sigma_{r}>0$. Then for any
$\hat{{\mathbf{M}}}\in\mathbb{R}^{d\times d}$ satisfying
$\|\hat{{\mathbf{M}}}-{\mathbf{M}}\|_{\mathrm{F}}<\sigma_{r}/4$, with
$\hat{\mathbf{U}}_{r}\in\mathbb{R}^{d_{1}\times r}$ and
$\hat{\mathbf{V}}_{r}\in{\mathbb{R}}^{d_{2}\times r}$ the left and right
singular vectors of $r$ largest singular values, we have

$\displaystyle\|\hat{\mathbf{U}}_{r}\hat{\mathbf{U}}_{r}^{\top}-\mathbf{U}\mathbf{U}^{\top}\|$
$\displaystyle\leq\frac{4}{\sigma_{r}}\|\hat{\mathbf{M}}-\mathbf{M}\|,\quad\|\hat{\mathbf{V}}_{r}\hat{\mathbf{V}}_{r}^{\top}-\mathbf{V}\mathbf{V}^{\top}\|\leq\frac{4}{\sigma_{r}}\|\hat{\mathbf{M}}-\mathbf{M}\|,$
$\displaystyle\|\operatorname{SVD}_{r}(\hat{{\mathbf{M}}})-{\mathbf{M}}^{*}\|$
$\displaystyle\leq\|\mathbf{\hat{{\mathbf{M}}}-{\mathbf{M}}^{*}}\|+20\frac{\|\hat{{\mathbf{M}}}-{\mathbf{M}}^{*}\|^{2}}{\sigma_{r}},$
$\displaystyle\|\operatorname{SVD}_{r}(\hat{{\mathbf{M}}})-{\mathbf{M}}^{*}\|_{\mathrm{F}}$
$\displaystyle\leq\|\mathbf{\hat{{\mathbf{M}}}-{\mathbf{M}}^{*}}\|_{\mathrm{F}}+20\frac{\|\hat{{\mathbf{M}}}-{\mathbf{M}}^{*}\|\|\hat{{\mathbf{M}}}-{\mathbf{M}}^{*}\|_{\mathrm{F}}}{\sigma_{r}}.$

###### Proof.

See Section F. ∎

######  Theorem 10.

(Empirical process in matrix recovery) Suppose $f(\mathbf{M})$ is defined in
Equation 2 and $\rho(\cdot)$ is $\tilde{L}$-Lipschitz continuous. Then there
exists constants $C,C_{1}>0$, such that

$\big{|}(f(\mathbf{M})-f(\mathbf{M}^{*}))-(\mathbb{E}f(\mathbf{M})-\mathbb{E}f(\mathbf{M}^{*}))\big{|}\leq(C_{1}+C\tilde{L})\sqrt{nd_{1}r}\|\mathbf{M}-\mathbf{M}^{*}\|_{\mathrm{F}}$
(56)

holds for all at most $r$ rank matrix ${\mathbf{M}}\in\mathbb{R}^{d_{1}\times
d_{2}}$ with probability over
$1-\exp\left(-\frac{C^{2}d_{1}r}{3}\right)-3\exp\left(-\frac{n}{\log
n}\right)$.

###### Proof.

See Section G. ∎

######  Corollary 1.

Suppose $f(\mathbf{M})$ is defined in Equation 2 and $\rho(\cdot)$ is
$\tilde{L}$-Lipschitz continuous. Then there exists constants $C,C_{1}>0$,
such that

$\big{|}(f(\mathbf{M}+{\mathbf{M}}_{1})-f(\mathbf{M}))-(\mathbb{E}f(\mathbf{M}+{\mathbf{M}}_{1})-\mathbb{E}f(\mathbf{M}))\big{|}\leq(C_{1}+C\tilde{L})\sqrt{nd_{1}r}\|\mathbf{M}_{1}\|_{\mathrm{F}}$
(57)

holds for all at most $r$ rank matrix
${\mathbf{M}},{\mathbf{M}}_{1}\in\mathbb{R}^{d_{1}\times d_{2}}$ with
probability over
$1-\exp\left(-\frac{C^{2}d_{1}r}{3}\right)-3\exp\left(-\frac{n}{\log
n}\right)$.

###### Proof.

It is similar to proof of Theorem 10. ∎

######  Corollary 2.

Suppose conditions in Theorem 10 hold and let
${\mathbf{X}}_{1},\dots,{\mathbf{X}}_{n}$ have i.i.d. $\mathcal{N}(0,1)$
entries. For any at most rank $r$ matrix
${\mathbf{M}}\in{\mathbb{R}}^{d_{1}\times d_{2}}$, There exist constants
$c,c_{1}>0$, such that when $n\geq cd_{1}r$, the following inequality

$\displaystyle\sqrt{\frac{1}{2\pi}}n\|{\mathbf{M}}\|_{\rm{F}}\leq\sum_{i=1}^{n}|\langle{\mathbf{X}}_{i},{\mathbf{M}}\rangle|\leq
2n\|{\mathbf{M}}\|_{\rm{F}}$

holds with high probability over $1-\exp(-c_{1}d_{1}r)$.

###### Proof.

Take the absolute loss function in Theorem 10 , namely, $\rho(\cdot)=|\cdot|$
and set ${\mathbf{M}}^{*}$ to be zero and instert
${\mathbb{E}}|\langle{\mathbf{X}}_{i},{\mathbf{M}}\rangle|=\sqrt{\frac{2}{\pi}}\|{\mathbf{M}}\|_{\rm{F}}$
(see Lemma 17) into it. ∎

######  Lemma 17.

(Expectation of absolute loss under Gaussian noise) Suppose the noise term
follows Gaussian distribution $\xi_{1},\cdots,\xi_{n}\stackrel{{\scriptstyle
i.i.d.}}{{\sim}}\mathcal{N}(0,\sigma^{2})$ and take the absolute value loss
function

$f({\mathbf{M}})=\sum_{i=1}^{n}|Y_{i}-\langle{\mathbf{M}},{\mathbf{X}}_{i}\rangle|,$

and then we have

$\mathbb{E}[f(\mathbf{M})]=n\sqrt{\frac{2}{\pi}}\sqrt{\sigma^{2}+\|\mathbf{M}-\mathbf{M}^{*}\|_{\mathrm{F}}^{2}},\quad\mathbb{E}[f(\mathbf{M}^{*})]=n\sqrt{\frac{2}{\pi}}\sigma.$

###### Proof.

Note that
$f(\mathbf{M})=\sum_{i=1}^{n}|Y_{i}-\langle\mathbf{X}_{i},\mathbf{M}\rangle|=\sum_{i=1}^{n}|\xi_{i}-\langle\mathbf{X}_{i},\mathbf{M}-\mathbf{M}^{*}\rangle|$,
$f({\mathbf{M}}^{*})=\sum_{i=1}^{n}|Y_{i}-\langle\mathbf{X}_{i},\mathbf{M}^{*}\rangle|=\sum_{i=1}^{n}|\xi_{i}|$.

First calculate the conditional expectation
$\mathbb{E}[[|\xi_{i}-\langle\mathbf{A}_{i},\mathbf{M}-\mathbf{M}^{*}\rangle|]\lvert\mathbf{A}_{i}]$.
Notice that conditioned on $\mathbf{A}_{i}$,
$\xi_{i}-\langle\mathbf{A}_{i},\mathbf{X}-\mathbf{X}^{*}\rangle$ is normally
distributed with mean
$-\langle\mathbf{A}_{i},\mathbf{X}-\mathbf{X}^{*}\rangle$ and variance
$\sigma^{2}$ and then
$|\xi_{i}-\langle\mathbf{A}_{i},\mathbf{X}-\mathbf{X}^{*}\rangle|$ has a
folded normal distribution.

$\begin{split}\mathbb{E}&[[|\xi_{i}-\langle\mathbf{X}_{i},\mathbf{M}-\mathbf{M}^{*}\rangle|]\lvert\mathbf{X}_{i}]\\\
&=\sigma\sqrt{\frac{2}{\pi}}\exp(-\frac{\langle\mathbf{X}_{i},\mathbf{M}-\mathbf{M}^{*}\rangle^{2}}{2\sigma^{2}})-\langle\mathbf{X}_{i},\mathbf{M}-\mathbf{M}^{*}\rangle[1-2\phi(\frac{\langle\mathbf{X}_{i},\mathbf{M}-\mathbf{M}^{*}\rangle}{\sigma})],\end{split}$

where $\phi(\cdot)$ is the normal cumulative distribution function. For each
$i=1,2,\cdots,n$, one has

$\begin{split}\mathbb{E}[|\xi_{i}-\langle\mathbf{X}_{i},\mathbf{M}-\mathbf{M}^{*}\rangle|]&=\mathbb{E}[\mathbb{E}[[|\xi_{i}-\langle\mathbf{X}_{i},\mathbf{M}-\mathbf{M}^{*}\rangle|]\lvert\mathbf{X}_{i}]]\\\
&=\sigma\sqrt{\frac{2}{\pi}}\mathbb{E}[\exp(-\frac{\langle\mathbf{X}_{i},\mathbf{M}-\mathbf{M}^{*}\rangle^{2}}{2\sigma^{2}})]-\mathbb{E}[\langle\mathbf{X}_{i},\mathbf{M}-\mathbf{M}^{*}\rangle[1-2\phi(\frac{\langle\mathbf{X}_{i},\mathbf{M}-\mathbf{M}^{*}\rangle}{\sigma})]]\end{split}$

and notice that
$\langle\mathbf{X}_{i},\mathbf{M}-\mathbf{M}^{*}\rangle\sim\mathcal{N}(0,\|\mathbf{M}-\mathbf{M}^{*}\|_{\mathrm{F}}^{2})$
and then after integration calculation it is

$\mathbb{E}[|\xi_{i}-\langle\mathbf{X}_{i},\mathbf{M}-\mathbf{M}^{*}\rangle|=\sqrt{\frac{2}{\pi}}\sqrt{\sigma^{2}+\|\mathbf{M}-\mathbf{M}^{*}\|_{\mathrm{F}}^{2}}.$

Specifically, when ${\mathbf{M}}={\mathbf{M}}^{*}$, it leads to
$\mathbb{E}[|\xi|]=\sqrt{\frac{2}{\pi}}\sigma$. Thus, we have

$\mathbb{E}[f(\mathbf{M})]=n\mathbb{E}[|\xi_{i}-\langle\mathbf{X}_{i},\mathbf{M}-\mathbf{M}^{*}\rangle|]=n\sqrt{\frac{2}{\pi}}\sqrt{\sigma^{2}+\|\mathbf{M}-\mathbf{M}^{*}\|_{\mathrm{F}}^{2}},\quad\mathbb{E}[f(\mathbf{\mathbf{M}}^{*})]=n\mathbb{E}[|\xi|]=n\sqrt{\frac{2}{\pi}}\sigma.$

∎

######  Lemma 18.

(Contraction of Heavy Tailed Random Variables) Suppose
$\xi,\xi_{1},\xi_{2},\cdots,\xi_{n}$ are i.i.d. random variables and there
exists $\varepsilon>0$ such that its $1+\varepsilon$ moment is finite, that is
${\mathbb{E}}|\xi|^{1+\varepsilon}<+\infty$. Then
$\frac{1}{n}\sum_{i=1}^{n}|\xi_{i}|\leq 3{\mathbb{E}}|\xi|$ with probability
exceeding $1-{}^{*}\\!cn^{-\min\\{\varepsilon,1\\}}$. Here ${}^{*}\\!c>0$ is
some constant which depends on
${\mathbb{E}}|\xi|,{\mathbb{E}}|\xi|^{1+\varepsilon}$.

###### Proof.

First consider when $0<\varepsilon<1$. Denote $\varphi_{i}:=|\xi_{i}|$ and
take truncation $\bar{\varphi}_{i}:=|\xi_{i}|\cdot
1_{\\{|\xi_{i}|<n\\}}=\varphi_{i}\cdot 1_{\varphi_{i}>n}$. For conveniece,
denote
$\|\xi\|_{1+\varepsilon}:=\left({\mathbb{E}}|\xi|^{1+\varepsilon}\right)^{1/(1+\varepsilon)}$
and introduce independent random variable $\varphi$ which has same
distribution as $\varphi_{1},\cdots,\varphi_{n}$ and define
$\bar{\varphi}:=\varphi\cdot 1_{\\{\varphi<n\\}}$. The original problem is
equivalent to bound $\frac{1}{n}\sum_{i=1}^{n}\varphi_{i}$ with its
expectation.

Note that
$\frac{1}{n}\sum_{i=1}^{n}\left(\varphi_{i}-{\mathbb{E}}\varphi_{i}\right)$
could be written into sum of three parts,

$\frac{1}{n}\sum_{i=1}^{n}\left(\varphi_{i}-{\mathbb{E}}\varphi_{i}\right)=\frac{1}{n}\sum_{i=1}^{n}\left(\bar{\varphi}_{i}-{\mathbb{E}}\bar{\varphi}_{i}\right)+\frac{1}{n}\sum_{i=1}^{n}\left(\varphi_{i}-\bar{\varphi}_{i}\right)+({\mathbb{E}}\varphi-{\mathbb{E}}\bar{\varphi}).$

Analyze the three parts respectively. Consider the first term, for any
constant $s>0$,

$\displaystyle{\mathbb{P}}\left(|\frac{1}{n}\sum_{i=1}^{n}\left(\bar{\varphi}_{i}-{\mathbb{E}}\bar{\varphi}_{i}\right)|>s\right)$
$\displaystyle\leq\frac{1}{ns^{2}}{\textrm{Var}}\,\left(\bar{\varphi}\right)\leq\frac{1}{ns^{2}}{\mathbb{E}}\bar{\varphi}^{1+\varepsilon}\bar{\varphi}^{1-\varepsilon}\leq\frac{\|\xi\|_{1+\varepsilon}^{1+\varepsilon}}{ns^{2}}\cdot
n^{1-\varepsilon}=\|\xi\|_{1+\varepsilon}^{1+\varepsilon}s^{-2}n^{-\varepsilon},$

where the intermediate equation uses Markov inequality and the last inequality
is because of $\bar{\varphi}<n$. Then consider the second term, the
probability of
$\frac{1}{n}\sum_{i=1}^{n}\bar{\varphi}_{i}\neq\frac{1}{n}\sum_{i=1}^{n}\varphi_{i}$

$\displaystyle{\mathbb{P}}\left(\frac{1}{n}\sum_{i=1}^{n}\bar{\varphi}_{i}\neq\frac{1}{n}\sum_{i=1}^{n}\varphi_{i}\right)$
$\displaystyle\leq n{\mathbb{P}}\left(\varphi>n\right)\leq
n\frac{{\mathbb{E}}\varphi^{1+\varepsilon}}{n^{1+\varepsilon}}=\|\xi\|_{1+\varepsilon}^{1+\varepsilon}n^{-\varepsilon}.$

The last term measures the expectation difference and could be bounded as
followed,

$\displaystyle{\mathbb{E}}\varphi_{i}-{\mathbb{E}}\bar{\varphi}_{i}$
$\displaystyle={\mathbb{E}}\varphi_{i}\cdot
1_{\varphi_{i}>n}\leq{\mathbb{E}}\varphi.$

Hence, we have

$\displaystyle{\mathbb{P}}\left(|\frac{1}{n}\sum_{i=1}^{n}\varphi_{i}-{\mathbb{E}}\varphi_{i}|>s\right)$
$\displaystyle\leq{\mathbb{P}}\left(|\frac{1}{n}\sum_{i=1}^{n}\bar{\varphi}_{i}-{\mathbb{E}}\varphi_{i}|>s\right)+{\mathbb{P}}\left(\frac{1}{n}\sum_{i=1}^{n}\bar{\varphi}_{i}\neq\frac{1}{n}\sum_{i=1}^{n}\varphi_{i}\right)$
$\displaystyle\leq{\mathbb{P}}\left(|\frac{1}{n}\sum_{i=1}^{n}\bar{\varphi}_{i}-{\mathbb{E}}\bar{\varphi}_{i}|>s-({\mathbb{E}}\varphi-{\mathbb{E}}\bar{\varphi})\right)+\|\xi\|_{1+\varepsilon}^{1+\varepsilon}n^{-\varepsilon}$
$\displaystyle\leq{\mathbb{P}}\left(|\frac{1}{n}\sum_{i=1}^{n}\bar{\varphi}_{i}-{\mathbb{E}}\bar{\varphi}_{i}|>s-{\mathbb{E}}\varphi\right)+\|\xi\|_{1+\varepsilon}^{1+\varepsilon}n^{-\varepsilon},$

where the last inequality uses
${\mathbb{E}}\varphi_{i}-{\mathbb{E}}\bar{\varphi}_{i}\leq{\mathbb{E}}\varphi$.
Take $s=2{\mathbb{E}}\varphi$ and then it becomes

$\displaystyle{\mathbb{P}}\left(|\frac{1}{n}\sum_{i=1}^{n}\varphi_{i}-{\mathbb{E}}\varphi_{i}|>2{\mathbb{E}}\varphi\right)$
$\displaystyle\leq{\mathbb{P}}\left(|\frac{1}{n}\sum_{i=1}^{n}\varphi_{i}-{\mathbb{E}}\varphi_{i}|>{\mathbb{E}}\varphi\right)+\|\xi\|_{1+\varepsilon}^{1+\varepsilon}n^{-\varepsilon}$
$\displaystyle\leq\|\xi\|_{1+\varepsilon}^{1+\varepsilon}[{\mathbb{E}}\varphi]^{-2}n^{-\varepsilon}+\|\xi\|_{1+\varepsilon}^{1+\varepsilon}n^{-\varepsilon},$

which proves ${\mathbb{P}}(\frac{1}{n}\sum_{i=1}^{n}|\xi_{i}|\geq
3{\mathbb{E}}|\xi|)\leq{}^{*}\\!cn^{-\varepsilon}$. When $\varepsilon\geq 1$,
we have ${\mathbb{P}}(\frac{1}{n}\sum_{i=1}^{n}|\xi_{i}|\geq
3{\mathbb{E}}|\xi|)\leq{}^{*}\\!cn^{-1}$ whose proof is simpler and hence
skipped. ∎

######  Lemma 19.

(Tail inequality for sum of squared heavy-tailed random variables) Suppose
$\xi,\xi_{1},\cdots,\xi_{n}$ are i.i.d. random variables and there exists
$0<\varepsilon\leq 1$ such that its $1+\varepsilon$ moment is finite, that is
${\mathbb{E}}|\xi|^{1+\varepsilon}<+\infty$. Denote
$\|\xi\|_{1+\varepsilon}=\left({\mathbb{E}}|\xi|^{1+\varepsilon}\right)^{1/(1+\varepsilon)}$.
Then for any $s>0$, tail bound for sum of squares could be upper bounded

${\mathbb{P}}\left(\sum_{i=1}^{n}\xi_{i}^{2}>s\right)\leq
2n\|\xi\|_{1+\varepsilon}^{1+\varepsilon}s^{-\frac{1+\varepsilon}{2}}.$

###### Proof.

For any $s>0$, it has ${\mathbb{P}}\left(\xi^{2}\geq s\right)\leq
s^{-\frac{1+\varepsilon}{2}}{\mathbb{E}}|\xi|^{1+\varepsilon}$ which uses
Markov’s inequality. Introduce truncated random variable
$\varphi_{i}:=\xi_{i}^{2}1_{\\{\xi_{i}^{2}<s\\}}$. Note that
$\sum_{i=1}^{n}\xi_{i}^{2}$ could be written into sum of two parts

$\sum_{i=1}^{n}\xi_{i}^{2}=\sum_{i=1}^{n}\varphi_{i}+\sum_{i=1}^{n}(\xi_{i}^{2}-\varphi_{i}).$

Hence, we analyze these two parts respectively. First consider probability of
$\sum_{i=1}^{n}\xi_{i}^{2}\neq\sum_{i=1}^{n}\varphi_{i}$:

$\displaystyle{\mathbb{P}}\left(\sum_{i=1}^{n}\xi_{i}^{2}\neq\sum_{i=1}^{n}\varphi_{i}\right)$
$\displaystyle\leq n{\mathbb{P}}\left(\xi^{2}>s\right)\leq
n\frac{{\mathbb{E}}|\xi|^{1+\varepsilon}}{s^{\frac{1+\varepsilon}{2}}}=n\|\xi\|_{1+\varepsilon}^{1+\varepsilon}s^{-\frac{1+\varepsilon}{2}}.$

Then bound tail for sum of $\varphi_{i}$:

$\displaystyle{\mathbb{P}}\left(\sum_{i=1}^{n}\varphi_{i}>s\right)$
$\displaystyle\leq
ns^{-1}{\mathbb{E}}\varphi=ns^{-1}{\mathbb{E}}\varphi^{\frac{1+\epsilon}{2}}\varphi^{\frac{1-\epsilon}{2}}\leq
n\|\xi\|_{1+\varepsilon}^{1+\varepsilon}s^{-\frac{1+\varepsilon}{2}}.$

Finally, combine the above two equations, it has

$\displaystyle{\mathbb{P}}\left(\sum_{i=1}^{n}\xi_{i}^{2}>s\right)$
$\displaystyle\leq{\mathbb{P}}\left(\sum_{i=1}^{n}\varphi_{i}>s\right)+{\mathbb{P}}\left(\sum_{i=1}^{n}\xi_{i}^{2}\neq\sum_{i=1}^{n}\varphi_{i}\right)\leq
2n\|\xi\|_{1+\varepsilon}^{1+\varepsilon}s^{-\frac{1+\varepsilon}{2}},$

which completes the proof. ∎

######  Lemma 20 (Partial Frobenius norm for tensor).

Suppose ${\mathbf{M}}\in{\mathbb{R}}^{d_{1}\times\dots\times d_{m}}$ is an
$m$-th order tensor. Denote ${\mathbf{r}}=(r_{1},\cdots,r_{m})^{\top}$. The
partial Frobenius norm of ${\mathbf{M}}$ is defined to be

$\|{\mathbf{M}}\|_{\rm{F},{\mathbf{r}}}:=\sup_{{\mathbf{U}}_{1}\in{\mathbb{O}}_{d_{1},r_{1}},\cdots,{\mathbf{U}}_{m}\in{\mathbb{O}}_{d_{m},r_{m}}}\|{\mathbf{M}}\times_{1}{\mathbf{U}}_{1}^{\top}\times_{2}\dots\times_{m}{\mathbf{U}}_{m}^{\top}\|_{\rm{F}},$

Then for any tensor
$\hat{{\mathbf{M}}}\in{\mathbb{R}}^{d_{1}\times\cdots\times d_{m}}$ with
Tucker rank at most ${\mathbf{r}}$, one has

$|\langle{\mathbf{M}},\hat{{\mathbf{M}}}\rangle|\leq\|{\mathbf{M}}\|_{\rm{F},{\mathbf{r}}}\|\hat{\mathbf{M}}\|_{\rm{F}}.$

Specifically, it implies
$\|{\mathbf{M}}\|_{\rm{F},{\mathbf{r}}}=\sup_{\hat{\mathbf{M}}\in{\mathbb{M}}_{\mathbf{r}},\|\hat{\mathbf{M}}\|_{\rm{F}}\leq
1}|\langle{\mathbf{M}},\hat{\mathbf{M}}\rangle|$. Furthermore, for any
${\mathbf{V}}_{j}\in{\mathbb{R}}^{d_{1}\times
r_{1}},\ldots,{\mathbf{V}}_{m}\in{\mathbb{R}}^{d_{m}\times r_{m}}$, one has

$\|{\mathbf{M}}\times_{1}{\mathbf{V}}_{1}^{\top}\times_{2}\cdots\times_{m}{\mathbf{V}}_{m}^{\top}\|_{\rm{F}}\leq\|{\mathbf{M}}\|_{\rm{F},{\mathbf{r}}}\|{\mathbf{V}}_{1}\|\cdots\|{\mathbf{V}}_{m}\|.$

###### Proof.

For matrix $\hat{{\mathbf{M}}}\in{\mathbb{M}}_{{\mathbf{r}}}$, there exist
core tensor $\hat{\mathbf{C}}\in{\mathbb{R}}^{r_{1}\times\dots\times r_{m}}$
and orthogonal matrices $\hat{\mathbf{V}}_{j}\in{\mathbb{O}}_{d_{j},r_{j}}$
for each $j$ such that
$\hat{\mathbf{M}}=\hat{{\mathbf{C}}}_{1}\times_{1}\hat{\mathbf{V}}_{1}\times_{2}\dots\times_{m}\hat{\mathbf{V}}_{m}$.
Note that $\|\hat{\mathbf{M}}\|_{\rm{F}}=\|\hat{\mathbf{C}}\|_{\rm{F}}$. Then
one has

$\displaystyle|\langle{\mathbf{M}},\hat{\mathbf{M}}\rangle|$
$\displaystyle=|\langle{\mathbf{M}}\times_{1}\hat{\mathbf{V}}_{1}^{\top}\times_{2}\dots\times_{m}\hat{\mathbf{V}}_{m}^{\top},\hat{\mathbf{C}}\rangle|$
$\displaystyle\leq\|{\mathbf{M}}\times_{1}\hat{\mathbf{V}}_{1}^{\top}\times_{2}\dots\times_{m}\hat{\mathbf{V}}_{m}^{\top}\|_{\rm{F}}\|\hat{\mathbf{C}}\|_{\rm{F}}$
$\displaystyle\leq\|{\mathbf{M}}\|_{\rm{F},{\mathbf{r}}}\|\hat{\mathbf{M}}\|_{\rm{F}}.$

Note that the equality holds when
$\|{\mathbf{M}}\|_{\rm{F},{\mathbf{r}}}=\|{\mathbf{M}}\times_{1}\hat{\mathbf{V}}_{1}^{\top}\times_{2}\dots\times_{m}\hat{\mathbf{V}}_{m}^{\top}\|_{\rm{F}}$
and
$\hat{\mathbf{C}}={\mathbf{M}}\times_{1}\hat{\mathbf{V}}_{1}^{\top}\times_{2}\dots\times_{m}\hat{\mathbf{V}}_{m}^{\top}/\|{\mathbf{M}}\|_{\rm{F},{\mathbf{r}}}$,
which shows
$\|{\mathbf{M}}\|_{\rm{F},{\mathbf{r}}}=\sup_{\hat{\mathbf{M}}\in{\mathbb{M}}_{\mathbf{r}},\|\hat{\mathbf{M}}\|_{\rm{F}}\leq
1}|\langle{\mathbf{M}},\hat{\mathbf{M}}\rangle|$. It is obvious that for any
matrices ${\mathbf{V}}_{j}\in{\mathbb{R}}^{d_{j}\times r_{j}}$, one has

$\|{\mathbf{M}}\times_{1}{\mathbf{V}}_{1}^{\top}\times_{2}\cdots\times_{m}{\mathbf{V}}_{m}^{\top}\|_{\rm{F}}\leq\|{\mathbf{M}}\|_{\rm{F},{\mathbf{r}}}\|{\mathbf{V}}_{1}\|\cdots\|{\mathbf{V}}_{m}\|.$

∎

######  Lemma 21.

For any tensor ${\mathbf{M}}\in{\mathbb{M}}_{{\mathbf{r}}}$, suppose
${\mathbf{G}}\in\partial f({\mathbf{M}})$ is the subgradient at ${\mathbf{M}}$
and ${\mathbb{T}}$ is the tangent space for ${\mathbb{M}}_{{\mathbf{r}}}$ at
${\mathbf{M}}$. Then we have

$\|{\mathcal{P}}_{{\mathbb{T}}}({\mathbf{G}})\|_{\rm{F}}\leq\sqrt{m+1}\|{\mathbf{G}}\|_{\rm{F},{\mathbf{r}}}.$

###### Proof.

Let
${\mathbf{M}}={\mathbf{C}}\times_{1}{\mathbf{U}}_{1}\times_{2}\cdots\times_{m}{\mathbf{U}}_{m}$
be its Tucker decomposition. Then we have

${\mathcal{P}}_{{\mathbb{T}}}({\mathbf{G}})={\mathbf{G}}\times_{1}{\mathbf{U}}_{1}{\mathbf{U}}_{1}^{\top}\times_{2}\cdots\times_{m}{\mathbf{U}}_{m}{\mathbf{U}}_{m}^{\top}-\sum_{i=1}^{m}{\mathbf{C}}\times_{j\in[m]\backslash
i}{\mathbf{U}}_{j}\times_{i}\dot{{\mathbf{U}}}_{i},$

with $\dot{{\mathbf{U}}}_{i}=\left({\mathbf{G}}\times_{j\in[m]\backslash
i}{\mathbf{U}}_{j}^{\top}\times_{i}({\mathbf{I}}_{d_{i}}-{\mathbf{U}}_{i}{\mathbf{U}}_{i}^{\top})\right)_{(i)}\left({\mathbf{C}}_{(i)}\right)^{\dagger}$.
It implies

$\displaystyle\|{\mathcal{P}}_{{\mathbb{T}}}({\mathbf{G}})\|_{\rm{F}}^{2}$
$\displaystyle=\|{\mathbf{G}}\times_{1}{\mathbf{U}}_{1}{\mathbf{U}}_{1}^{\top}\times_{2}\cdots\times_{m}{\mathbf{U}}_{m}{\mathbf{U}}_{m}^{\top}\|_{\rm{F}}^{2}+\sum_{i=1}^{m}\|{\mathbf{C}}\times_{j\in[m]\backslash
i}{\mathbf{U}}_{j}\times_{i}\dot{{\mathbf{U}}}_{i}\|_{\rm{F}}^{2}$
$\displaystyle\leq(m+1)\|{\mathbf{G}}\|_{\rm{F},{\mathbf{r}}}^{2}.$

∎

######  Lemma 22 (Lemma 3.2 of Koch and Lubich [2010]).

For any ${\mathbf{M}},{\mathbf{M}}^{*}\in{\mathbb{M}}_{{\mathbf{r}}}$ with
$\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}\leq\frac{1}{16m(m+3)}\underline{\lambda}$,
denote ${\mathbb{T}}$ as the tangent space for ${\mathbb{M}}_{\mathbf{r}}$ at
${\mathbf{M}}$ and then we have

$\|{\mathcal{P}}_{{\mathbb{T}}}^{\perp}({\mathbf{M}}-{\mathbf{M}}^{*})\|_{\rm{F}}\leq\frac{8m(m+3)}{\underline{\lambda}}\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}^{2}.$

######  Theorem 11.

(Empirical process in tensor recovery) Suppose $f(\cdot)$ is defined in
Equation 8 and $\rho(\cdot)$ is $\tilde{L}$-Lipschitz continuous. Then there
exist constants $C,C_{1}>0$, such that

$\big{|}(f(\mathbf{M})-f(\mathbf{M}^{*}))-(\mathbb{E}f(\mathbf{M})-\mathbb{E}f(\mathbf{M}^{*}))\big{|}\leq(C_{1}+C\tilde{L})\sqrt{n(2\sum_{j=1}^{m}r_{j}d_{j}+2^{m}\cdot
r_{1}\cdots r_{d})}\|\mathbf{M}-\mathbf{M}^{*}\|_{\mathrm{F}}$ (58)

holds for all at most Tucker rank ${\mathbf{r}}$ tensor
${\mathbf{M}}\in\mathbb{R}^{d_{1}\times\cdots\times d_{m}}$ with probability
over $1-3\exp\left(-\frac{n}{\log n}\right)-\exp\left(-C(2^{m}\cdot
r_{1}r_{2}\cdots r_{m}+2\sum_{j=1}^{m}r_{j}d_{j})\right)$.

###### Proof.

See Section H. ∎

######  Corollary 3.

Suppose $f(\cdot)$ is defined in Equation 8 and $\rho(\cdot)$ is
$\tilde{L}$-Lipschitz continuous. Then there exist constants $C,C_{1}>0$, such
that

$\big{|}(f(\mathbf{M}+{\mathbf{M}}_{1})-f(\mathbf{M}))-(\mathbb{E}f(\mathbf{M}+{\mathbf{M}}_{1})-\mathbb{E}f(\mathbf{M}))\big{|}\leq(C_{1}+C\tilde{L})\sqrt{n(2\sum_{j=1}^{m}r_{j}d_{j}+2^{m}\cdot
r_{1}\cdots r_{d})}\|\mathbf{M}_{1}\|_{\mathrm{F}}$ (59)

holds for all at most Tucker rank ${\mathbf{r}}$ tensor
${\mathbf{M}}\in\mathbb{R}^{d_{1}\times\cdots\times d_{m}}$ and all at most
Tucker rank $2{\mathbf{r}}$ tensor
${\mathbf{M}}_{1}\in\mathbb{R}^{d_{1}\times\cdots\times d_{m}}$, with
probability over $1-3\exp\left(-\frac{n}{\log
n}\right)-\exp\left(-C(2^{m}\cdot r_{1}r_{2}\cdots
r_{m}+2\sum_{j=1}^{m}r_{j}d_{j})\right)$.

###### Proof.

It is similar to proof of Theorem 11. ∎

######  Corollary 4.

Suppose conditions of Theorem 11 hold and let
${\mathbf{X}}_{1},\dots,{\mathbf{X}}_{n}$ have i.i.d. $N(0,1)$ entries. For
any at most rank ${\mathbf{r}}$ tensors
${\mathbf{M}}\in{\mathbb{M}}_{2{\mathbf{r}}}$, there exist constants
$c,c_{1}>0$, such that when $n\geq c\sqrt{2^{m}\cdot r_{1}r_{2}\cdots
r_{m}+2\sum_{j=1}^{m}r_{j}d_{j}}$, the following inequality

$\displaystyle\sqrt{\frac{1}{2\pi}}n\|{\mathbf{M}}\|_{\rm{F}}\leq\sum_{i=1}^{n}|\langle{\mathbf{X}}_{i},{\mathbf{M}}\rangle|\leq
2n\|{\mathbf{M}}\|_{\rm{F}}$

holds with high probability over $1-\exp(-c_{1}(2^{m}\cdot r_{1}r_{2}\cdots
r_{m}+2\sum_{j=1}^{m}r_{j}d_{j}))$.

###### Proof.

Take the absolute loss function in Theorem 11, namely, $\rho(\cdot)=|\cdot|$
and instert
${\mathbb{E}}|\langle{\mathbf{X}}_{i},{\mathbf{M}}\rangle|=\sqrt{\frac{2}{\pi}}\|{\mathbf{M}}\|_{\rm{F}}$
(see Lemma 17) into it. ∎

######  Lemma 23 (Partial Frobenius norm of random Gaussian Tensor).

Suppose ${\mathbf{X}}\in{\mathbb{R}}^{d_{1}\times\dots\times d_{m}}$ has
independent $N(0,1)$ entries. Then for rank vector
${\mathbf{r}}=(r_{1},\dots,r_{m})^{\top}$, it has

$\displaystyle{\mathbb{P}}\left(\|{\mathbf{X}}\|_{\rm{F},{\mathbf{r}}}\geq
2c\left(t+\sqrt{\sum_{j=1}^{d}r_{j}d_{j}+r_{1}r_{2}\cdots
r_{d}}\right)\right)\leq 2\exp\left(-t^{2}\right)$

###### Proof.

The proof uses $\varepsilon$-net arguments. Recall that
${\mathbb{M}}_{{\mathbf{r}}}=\\{{\mathbf{M}}\in{\mathbb{R}}^{d_{1}\times\dots\times
d_{m}}:\text{rank}({\mathbf{M}}_{(j)})\leq r_{j},\,j=1,\cdots,m\\}$ is the set
of tensors with Tucker rank at most ${\mathbf{r}}$. From definition of partial
Frobenius norm, it has

$\|{\mathbf{X}}\|_{\rm{F},{\mathbf{r}}}=\sup_{{\mathbf{M}}\in{\mathbb{M}}_{\mathbf{r}},\|{\mathbf{M}}\|_{\rm{F}}\leq
1}|\langle{\mathbf{X}},{\mathbf{M}}\rangle|$

and suppose it achieves the supremum at
${\mathbf{M}}_{0}\in{\mathbb{M}}_{{\mathbf{r}}}$, namely,
$\|{\mathbf{M}}_{0}\|_{\rm{F}}=1$ and
$\|{\mathbf{X}}\|_{\rm{F},{\mathbf{r}}}=|\langle{\mathbf{X}},{\mathbf{M}}_{0}\rangle|$.
Then there exist a core tensor
${\mathbf{C}}_{0}\in{\mathbb{R}}^{r_{1}\times\cdots\times r_{m}}$ and
orthogonal matrices
${\mathbf{U}}_{1}^{0}\in{\mathbb{O}}_{d_{1},r_{1}},\cdots,{\mathbf{U}}_{m}^{0}\in{\mathbb{O}}_{d_{m},r_{m}}$
such that

${\mathbf{M}}_{0}={\mathbf{C}}_{0}\times_{1}{\mathbf{U}}_{1}^{0}\times_{2}\cdots\times_{m}{\mathbf{U}}_{m}^{0}.$

Notice that $\|{\mathbf{C}}_{0}\|_{\rm{F}}=1$. Define
${\mathbb{F}}_{\mathbf{r}}=\\{{\mathbf{C}}\in{\mathbb{R}}^{r_{1}\times\dots\times
r_{m}}:\|{\mathbf{C}}\|_{\rm{F}}=1\\}$ to be the set of tensors with unit
Frobenius norm. Then it has one $\varepsilon/(m+1)$-net
${\mathcal{N}}_{\varepsilon/(m+1)}^{{\mathbb{F}}_{\mathbf{r}}}$ with
cardinality
$|{\mathcal{N}}_{\varepsilon/(m+1)}^{{\mathbb{F}}_{\mathbf{r}}}|\leq(3(m+1)/\varepsilon)^{r_{1}r_{2}\cdots
r_{m}}$ respect to the Frobenius norm. Suppose
${\mathcal{N}}_{1},\cdots,{\mathcal{N}}_{m}$ are $\varepsilon/(m+1)$-nets of
orthogonal matrix sets
${\mathbb{O}}_{d_{1},r_{1}},\cdots,{\mathbb{O}}_{d_{m},r_{m}}$ respectively
with cardinalities

$|{\mathcal{N}}_{1}|\leq(3(m+1)/\varepsilon)^{d_{1}r_{1}},\cdots,|{\mathcal{N}}_{m}|\leq(3(m+1)/\varepsilon)^{d_{m}r_{m}}.$

See Rauhut et al. [2017], Vershynin [2018] for more about $\varepsilon$-nets.
Hence, for tensor
${\mathbf{M}}_{0}={\mathbf{C}}_{0}\times_{1}{\mathbf{U}}_{1}^{0}\times_{2}\cdots\times_{m}{\mathbf{U}}_{m}^{0}$,
there is close approximation in the nets. Exist
${\mathbf{C}}\in{\mathcal{N}}_{\varepsilon/(m+1)}^{{\mathbb{F}}_{\mathbf{r}}},\,{\mathbf{U}}_{1}\in{\mathcal{N}}_{1},\cdots,{\mathbf{U}}_{m}\in{\mathcal{N}}_{m}$
such that

$\|{\mathbf{C}}_{0}-{\mathbf{C}}\|_{\rm{F}}\leq\varepsilon/(m+1),\,\|{\mathbf{U}}_{1}^{0}-{\mathbf{U}}_{1}\|_{\rm{F}}\leq\varepsilon/(m+1),\cdots,\|{\mathbf{U}}_{m}^{0}-{\mathbf{U}}_{m}\|_{\rm{F}}\leq\varepsilon/(m+1).$

Denote the product as
${\mathbf{M}}={\mathbf{C}}\times_{1}{\mathbf{U}}_{1}\times_{2}\cdots\times_{m}{\mathbf{U}}_{m}$.
Furthermore, net
${\mathcal{N}}:=\\{{\mathbf{M}}={\mathbf{C}}\times_{1}{\mathbf{U}}_{1}\times_{2}\cdots\times_{m}{\mathbf{U}}_{m}:{\mathbf{C}}\in{\mathcal{N}}_{\varepsilon/(m+1)}^{{\mathbb{F}}_{\mathbf{r}}},\,{\mathbf{U}}_{1}\in{\mathcal{N}}_{1},\dots,{\mathbf{U}}_{m}\in{\mathcal{N}}_{m}\\}$
forms an $\varepsilon$-net of ${\mathbb{M}}_{{\mathbf{r}}}$ with cardinality
$|{\mathcal{N}}|\leq(3(m+1)/\varepsilon)^{r_{1}r_{2}\cdots
r_{m}+\sum_{j=1}^{m}r_{j}d_{j}}$.

Then come back to partial Frobenius norm of ${\mathbf{X}}$ and we have

$\displaystyle\|{\mathbf{X}}\|_{\rm{F},{\mathbf{r}}}$
$\displaystyle=|\langle{\mathbf{X}},{\mathbf{M}}_{0}\rangle|$
$\displaystyle\leq|\langle{\mathbf{X}},{\mathbf{M}}\rangle|+|\langle{\mathbf{X}},{\mathbf{M}}_{0}-{\mathbf{M}}\rangle|$
$\displaystyle\leq\sup_{{\mathbf{M}}\in{\mathcal{N}}}|\langle{\mathbf{X}},{\mathbf{M}}\rangle|+\varepsilon\|{\mathbf{X}}\|_{\rm{F},{\mathbf{r}}},$

which implies

$\|{\mathbf{X}}\|_{\rm{F},{\mathbf{r}}}\leq\frac{1}{1-\varepsilon}\sup_{{\mathbf{M}}\in{\mathcal{N}}}|\langle{\mathbf{X}},{\mathbf{M}}\rangle|.$

On the other hand, for any fixed ${\mathbf{M}}\in{\mathcal{N}}$, we have
$\|\langle{\mathbf{X}},{\mathbf{M}}\rangle\|_{\Psi_{2}}^{2}=1$. Then the inner
product between ${\mathbf{X}}$ and fixed tensor ${\mathbf{M}}$ has the
following tail bound

${\mathbb{P}}\left(|\langle{\mathbf{X}},{\mathbf{M}}\rangle|\geq u\right)\leq
2\exp(-u^{2}).$

Thus the union yields

${\mathbb{P}}\left(\sup_{{\mathbf{M}}\in{\mathcal{N}}}|\langle{\mathbf{X}},{\mathbf{M}}\rangle|\geq
u\right)\leq
2|{\mathcal{N}}|\exp(-u^{2})\leq(3(m+1)/\varepsilon)^{r_{1}r_{2}\cdots
r_{m}+\sum_{j=1}^{m}r_{j}d_{j}}\exp(-u^{2}).$

Take $\varepsilon=1/2$ and $u=c(\sqrt{r_{1}r_{2}\cdots
r_{m}+\sum_{j=1}^{m}r_{j}d_{j}}+t)$ and it leads to

${\mathbb{P}}\left(\sup_{{\mathbf{M}}\in{\mathcal{N}}}|\langle{\mathbf{X}},{\mathbf{M}}\rangle|\geq
u\right)\leq 2\exp(-t^{2}),$

which proves

${\mathbb{P}}\left(\|{\mathbf{X}}\|_{\rm{F},{\mathbf{r}}}\geq 2u\right)\leq
2\exp(-t^{2}).$

∎

##  Appendix F Proof of Matrix Perturbation Lemma 16

To prove Lemma 16, first consider simpler case when the matrix and the
perturbation are symmetric.

######  Lemma 24.

(Symmetric Matrix Perturbation) Suppose symmetric matrix
$\mathbf{M}^{*}\in{\mathbb{R}}^{d\times d}$ has rank $r$. Let
$\mathbf{M}^{*}=\mathbf{U}\boldsymbol{\Lambda}\mathbf{U}^{\top}$ be its
singular value decomposition with
$\boldsymbol{\Lambda}=\operatorname{diag}\\{\lambda_{1},\lambda_{2},\cdots,\lambda_{r}\\}$,
$|\lambda_{1}|\geq|\lambda_{2}|\geq\cdots\geq|\lambda_{r}|>0$. Then for any
matrix $\hat{{\mathbf{M}}}\in{\mathbb{R}}^{d\times d}$ satisfying
$\|\hat{{\mathbf{M}}}-{\mathbf{M}}\|_{\mathrm{F}}<\sigma_{r}/4$ with
$\hat{\mathbf{U}}_{r}\in\mathbb{R}^{d\times r}$ eigenvectors of $r$ largest
absolute eigenvalues of $\hat{\mathbf{M}}$, then we have

$\|\hat{\mathbf{U}}_{r}\hat{\mathbf{U}}_{r}^{\top}-\mathbf{U}\mathbf{U}^{\top}\|\leq\frac{4\|\hat{\mathbf{M}}-\mathbf{M}\|}{|\lambda_{r}|},$
$\|\operatorname{SVD}_{r}(\hat{\mathbf{M}})-\mathbf{M}^{*}\|\leq\|\hat{\mathbf{M}}-\mathbf{M}\|+20\frac{\|\hat{\mathbf{M}}-\mathbf{M}\|^{2}}{\lambda_{r}},$
$\|\operatorname{SVD}_{r}(\hat{\mathbf{M}})-\mathbf{M}^{*}\|_{\mathrm{F}}\leq\|\hat{\mathbf{M}}-\mathbf{M}\|_{\mathrm{F}}+20\frac{\|\hat{\mathbf{M}}-\mathbf{M}\|\|\hat{\mathbf{M}}-\mathbf{M}\|_{\mathrm{F}}}{\lambda_{r}}.$

###### Proof.

Denote $\mathbf{Z}=\hat{\mathbf{M}}-\mathbf{M}$. Define
$\mathbf{U}_{\perp}\in\mathbb{R}^{d\times(d-r)}$ such that
$[\mathbf{U},\mathbf{U}_{\perp}]\in\mathbb{R}^{d\times d}$ is orthonormal and
then define the projector

$\mathfrak{P}^{\perp}:=\mathbf{U}_{\perp}\mathbf{U}_{\perp}^{\top},\quad\mathfrak{P}^{-1}:=\mathbf{U}\boldsymbol{\Lambda}^{-1}\mathbf{U}^{\top}.$

Write
$\mathfrak{P}^{-k}=\mathbf{U}\boldsymbol{\Lambda}^{-k}\mathbf{U}^{\top}$, for
all $k\geq 1$ and for convenience when $k=0$, we write
$\mathfrak{P}^{0}=\mathfrak{P}^{-1}$. Define the $k$-th order perturbation

$\mathcal{S}_{\mathbf{M}^{*},k}(\mathbf{Z}):=\sum_{\mathbf{s}:s_{1}+\cdots+s_{k+1}=k}(-1)^{1+\tau(\mathbf{s})}\mathfrak{P}^{-s_{1}}\mathbf{Z}\mathfrak{P}^{-s_{2}}\cdots\mathfrak{P}^{-s_{k}}\mathbf{Z}\mathfrak{P}^{-s_{k+1}},$

where $s_{1},\cdots,s_{k}$ are non-negative integers and
$\tau(\mathbf{s})=\sum_{i=1}^{k}\mathbb{I}(s_{i}>0)$ is the number of positive
indices in $\mathbf{s}$. Work Xia [2021] proves

$\hat{\mathbf{U}}_{r}\hat{\mathbf{U}}_{r}^{\top}-\mathbf{U}\mathbf{U}^{\top}=\sum_{k\geq
1}\mathcal{S}_{\mathbf{M}^{*},k}(\mathbf{Z}).$

Then norm of $\mathcal{S}_{\mathbf{M}^{*},k}(\mathbf{Z})$ coulded be bounded
in the way of

$\|\mathcal{S}_{\mathbf{M}^{*},k}(\mathbf{Z})\|\leq\binom{2k}{k}\frac{\|\mathbf{Z}\|^{k}}{|\lambda_{r}|^{k}}\leq\left(\frac{4\|\mathbf{Z}\|}{|\lambda_{r}|}\right)^{k},\quad\|\mathcal{S}_{\mathbf{M}^{*},k}(\mathbf{Z})\|_{\mathrm{F}}\leq\binom{2k}{k}\frac{\|\mathbf{Z}\|_{\mathrm{F}}^{k}}{|\lambda_{r}|^{k}}\leq\left(\frac{4\|\mathbf{Z}\|_{\mathrm{F}}}{|\lambda_{r}|}\right)^{k}.$

Hence, the above three equations lead to

$\|\hat{\mathbf{U}}_{r}\hat{\mathbf{U}}_{r}^{\top}-\mathbf{U}\mathbf{U}^{\top}\|\leq\sum_{k\geq
1}\|\mathcal{S}_{\mathbf{M}^{*},k}(\mathbf{Z})\|\leq\frac{4\|\mathbf{Z}\|}{|\lambda_{r}|},\quad\|\hat{\mathbf{U}}_{r}\hat{\mathbf{U}}_{r}^{\top}-\mathbf{U}\mathbf{U}^{\top}\|_{\mathrm{F}}\leq\sum_{k\geq
1}\|\mathcal{S}_{\mathbf{M}^{*},k}(\mathbf{Z})\|_{\mathrm{F}}\leq\frac{4\|\mathbf{Z}\|_{\mathrm{F}}}{|\lambda_{r}|}.$

Then consider $\mathcal{S}_{\mathbf{M}^{*},k}(\mathbf{Z})\mathbf{M}^{*}$:

$\begin{split}\mathcal{S}_{\mathbf{M}^{*},k}(\mathbf{Z})\mathbf{M}^{*}&=\sum_{\mathbf{s}:s_{1}+\cdots+s_{k+1}=k}(-1)^{1+\tau(\mathbf{s})}\mathfrak{P}^{-s_{1}}\mathbf{Z}\mathfrak{P}^{-s_{2}}\cdots\mathfrak{P}^{-s_{k}}\mathbf{Z}\mathfrak{P}^{-s_{k+1}}\mathbf{M}^{*}\\\
&=\sum_{\mathbf{s}:s_{1}+\cdots+s_{k+1}=k}(-1)^{1+\tau(\mathbf{s})}\mathfrak{P}^{-s_{1}}\mathbf{Z}\mathfrak{P}^{-s_{2}}\cdots\mathfrak{P}^{-s_{k}}\mathbf{Z}\mathfrak{P}^{-s_{k+1}}\mathbf{U}\boldsymbol{\Lambda}\mathbf{U}^{\top}.\end{split}$

Note that when $s_{k+1}=0$,
$\mathfrak{P}^{-s_{k+1}}=\mathbf{U}_{\perp}\mathbf{U}_{\perp}^{\top}$ and
hence $\mathfrak{P}^{-s_{k+1}}\mathbf{M}^{*}=0$ and thus we have

$\mathcal{S}_{\mathbf{M}^{*},k}(\mathbf{Z})\mathbf{M}^{*}=\sum_{\mathbf{s}:s_{1}+\cdots+s_{k+1}=k,\,s_{k+1}>0}(-1)^{1+\tau(\mathbf{s})}\mathfrak{P}^{-s_{1}}\mathbf{Z}\mathfrak{P}^{-s_{2}}\cdots\mathfrak{P}^{-s_{k}}\mathbf{Z}\mathfrak{P}^{1-s_{k+1}}.$

Specifically, when $k=1$, it is
$\mathcal{S}_{\mathbf{M}^{*},1}(\mathbf{Z})\mathbf{M}^{*}=\mathbf{U}_{\perp}\mathbf{U}_{\perp}^{\top}\mathbf{Z}\mathbf{U}\mathbf{U}^{\top}$
and its operator norm could be bounded with

$\|\mathcal{S}_{\mathbf{M}^{*},k}(\mathbf{Z})\mathbf{M}^{*}\|\leq\binom{2k-1}{k}\frac{\|\mathbf{Z}\|^{k+1}}{|\lambda_{r}|^{k-1}}\leq\|\mathbf{Z}\|\left(\frac{4\|\mathbf{Z}\|}{|\lambda_{r}|}\right)^{k-1},$

which implies

$\|\sum_{k\geq
2}\mathcal{S}_{\mathbf{M}^{*},k}(\mathbf{Z})\mathbf{M}^{*}\|\leq\frac{4\|\mathbf{Z}\|^{2}}{|\lambda_{r}|}.$

Similarly, Frobenius norm of
$\mathcal{S}_{\mathbf{M}^{*},k}(\mathbf{Z})\mathbf{M}^{*}$ has

$\|\mathcal{S}_{\mathbf{M}^{*},k}(\mathbf{Z})\mathbf{M}^{*}\|_{\mathrm{F}}\leq\binom{2k-1}{k}\frac{\|\mathbf{Z}\|^{k}}{|\lambda_{r}|^{k-1}}\|\mathbf{Z}\|_{\mathrm{F}}\leq\|\mathbf{Z}\|_{\mathrm{F}}\left(\frac{4\|\mathbf{Z}\|}{|\lambda_{r}|}\right)^{k-1},$
$\|\sum_{k\geq
2}\mathcal{S}_{\mathbf{M}^{*},k}(\mathbf{Z})\mathbf{M}^{*}\|_{\mathrm{F}}\leq\frac{4\|\mathbf{Z}\|_{\mathrm{F}}\|\mathbf{Z}\|}{|\lambda_{r}|}.$

Then expand $\operatorname{SVD}_{r}(\hat{\mathbf{M}})-\mathbf{M}^{*}$:

$\begin{split}&{~{}~{}~{}~{}}\operatorname{SVD}_{r}(\hat{\mathbf{M}})-\mathbf{M}^{*}\\\
&=\hat{\mathbf{U}}_{r}\hat{\mathbf{U}}_{r}^{\top}(\mathbf{M}^{*}+\mathbf{Z})\hat{\mathbf{U}}_{r}\hat{\mathbf{U}}_{r}^{\top}-\mathbf{M}^{*}\\\
&=\hat{\mathbf{U}}_{r}\hat{\mathbf{U}}_{r}^{\top}(\mathbf{M}^{*}+\mathbf{Z})\hat{\mathbf{U}}_{r}\hat{\mathbf{U}}_{r}^{\top}-\mathbf{U}\mathbf{U}^{\top}\mathbf{M}^{*}\mathbf{U}\mathbf{U}^{\top}\\\
&=(\hat{\mathbf{U}}_{r}\hat{\mathbf{U}}_{r}^{\top}-\mathbf{U}\mathbf{U}^{\top})\mathbf{M}^{*}\mathbf{U}\mathbf{U}^{\top}+\hat{\mathbf{U}}_{r}\hat{\mathbf{U}}_{r}^{\top}\mathbf{M}^{*}(\hat{\mathbf{U}}_{r}\hat{\mathbf{U}}_{r}^{\top}-\mathbf{U}\mathbf{U}^{\top})+\hat{\mathbf{U}}_{r}\hat{\mathbf{U}}_{r}^{\top}\mathbf{Z}\hat{\mathbf{U}}_{r}\hat{\mathbf{U}}_{r}^{\top}\\\
&=\sum_{k\geq
2}\mathcal{S}_{\mathbf{M}^{*},k}(\mathbf{Z})\mathbf{M}^{*}\mathbf{U}\mathbf{U}^{\top}+\hat{\mathbf{U}}_{r}\hat{\mathbf{U}}_{r}^{\top}\mathbf{M}^{*}\sum_{k\geq
2}\mathcal{S}_{\mathbf{M}^{*},k}(\mathbf{Z})+\mathbf{U}_{\perp}\mathbf{U}_{\perp}^{\top}\mathbf{Z}\mathbf{U}\mathbf{U}^{\top}\\\
&{~{}~{}~{}}+\hat{\mathbf{U}}_{r}\hat{\mathbf{U}}_{r}^{\top}\mathbf{U}\mathbf{U}^{\top}\mathbf{Z}\mathbf{U}_{\perp}\mathbf{U}_{\perp}^{\top}+\hat{\mathbf{U}}_{r}\hat{\mathbf{U}}_{r}^{\top}\mathbf{Z}\hat{\mathbf{U}}_{r}\hat{\mathbf{U}}_{r}^{\top}\\\
&=\sum_{k\geq
2}\mathcal{S}_{\mathbf{M}^{*},k}(\mathbf{Z})\mathbf{M}^{*}\mathbf{U}\mathbf{U}^{\top}+\hat{\mathbf{U}}_{r}\hat{\mathbf{U}}_{r}^{\top}\mathbf{M}^{*}\sum_{k\geq
2}\mathcal{S}_{\mathbf{M}^{*},k}(\mathbf{Z})+\mathbf{Z}-\mathbf{U}_{\perp}\mathbf{U}_{\perp}^{\top}\mathbf{Z}\mathbf{U}_{\perp}\mathbf{U}_{\perp}^{\top}\\\
&{~{}~{}~{}}+(\hat{\mathbf{U}}_{r}\hat{\mathbf{U}}_{r}^{\top}-\mathbf{U}\mathbf{U}^{\top})\mathbf{U}\mathbf{U}^{\top}\mathbf{Z}\mathbf{U}_{\perp}\mathbf{U}_{\perp}^{\top}+(\hat{\mathbf{U}}_{r}\hat{\mathbf{U}}_{r}^{\top}\mathbf{Z}\hat{\mathbf{U}}_{r}\hat{\mathbf{U}}_{r}^{\top}-\mathbf{U}\mathbf{U}^{\top}\mathbf{Z}\mathbf{U}\mathbf{U}^{\top})\\\
\end{split}$

Take Frobenius norm on each side of the above equation and it leads to

$\begin{split}&{~{}~{}~{}~{}}\|\operatorname{SVD}_{r}(\hat{\mathbf{M}})-\mathbf{M}^{*}\|_{\mathrm{F}}\\\
&\leq\|\sum_{k\geq
2}\mathcal{S}_{\mathbf{M}^{*},k}(\mathbf{Z})\mathbf{M}^{*}\mathbf{U}\mathbf{U}^{\top}\|_{\mathrm{F}}+\|\hat{\mathbf{U}}_{r}\hat{\mathbf{U}}_{r}^{\top}\mathbf{M}^{*}\sum_{k\geq
2}\mathcal{S}_{\mathbf{M}^{*},k}(\mathbf{Z})\|_{\mathrm{F}}+\|\mathbf{Z}-\mathbf{U}_{\perp}\mathbf{U}_{\perp}^{\top}\mathbf{Z}\mathbf{U}_{\perp}\mathbf{U}_{\perp}^{\top}\|_{\mathrm{F}}\\\
&{~{}~{}~{}}+\|(\hat{\mathbf{U}}_{r}\hat{\mathbf{U}}_{r}^{\top}-\mathbf{U}\mathbf{U}^{\top})\mathbf{U}\mathbf{U}^{\top}\mathbf{Z}\mathbf{U}_{\perp}\mathbf{U}_{\perp}^{\top}\|_{\mathrm{F}}+\|\hat{\mathbf{U}}_{r}\hat{\mathbf{U}}_{r}^{\top}\mathbf{Z}\hat{\mathbf{U}}_{r}\hat{\mathbf{U}}_{r}^{\top}-\mathbf{U}\mathbf{U}^{\top}\mathbf{Z}\mathbf{U}\mathbf{U}^{\top}\|_{\mathrm{F}}\\\
&\leq\frac{4\|\mathbf{Z}\|_{\mathrm{F}}\|\mathbf{Z}\|}{|\lambda_{r}|}+\frac{4\|\mathbf{Z}\|_{\mathrm{F}}\|\mathbf{Z}\|}{|\lambda_{r}|}+\|\mathbf{Z}\|_{\mathrm{F}}+3\|\hat{\mathbf{U}}_{r}\hat{\mathbf{U}}_{r}^{\top}-\mathbf{U}\mathbf{U}^{\top}\|\|\mathbf{Z}\|_{\mathrm{F}}\\\
&\leq\|\mathbf{Z}\|_{\mathrm{F}}+20\frac{\|\mathbf{Z}\|_{\mathrm{F}}\|\mathbf{Z}\|}{|\lambda_{r}|}.\end{split}$

Similarly, one has the bound of the operator norm

$\|\operatorname{SVD}_{r}(\hat{\mathbf{M}})-\mathbf{M}^{*}\|\leq\|\hat{\mathbf{M}}-\mathbf{M}\|+20\frac{\|\hat{\mathbf{M}}-\mathbf{M}\|^{2}}{\lambda_{r}}.$

∎

###### Proof of Lemma 16.

Here we construct symmetrization of $\mathbf{M}^{*}$ and $\hat{\mathbf{M}}$
and then we could apply Lemma 24. First construct symmetric matrices

$\mathbf{Y}^{*}:=\left(\begin{matrix}0&\mathbf{M}^{*}\\\
\mathbf{M}^{*\top}&0\end{matrix}\right),\,\hat{\mathbf{Y}}:=\left(\begin{matrix}0&\hat{\mathbf{M}}\\\
\hat{\mathbf{M}}^{\top}&0\end{matrix}\right).$

Denote the perturbation matrix as
$\mathbf{Z}:=\hat{\mathbf{M}}-\mathbf{M}^{*}$ and similarly define

$\hat{\mathbf{Z}}:=\left(\begin{matrix}0&\mathbf{Z}\\\
\mathbf{Z}^{\top}&0\end{matrix}\right)=\left(\begin{matrix}0&\hat{\mathbf{M}}-\mathbf{M}^{*}\\\
\hat{\mathbf{M}}^{\top}-\mathbf{M}^{*\top}&0\end{matrix}\right).$

Note that $\operatorname{rank}(\mathbf{Y}^{*})\leq 2r$. By Lemma 24, one has

$\|\operatorname{SVD}_{2r}(\hat{\mathbf{Y}})-\mathbf{Y}^{*}\|_{\mathrm{F}}\leq\|\hat{\mathbf{Z}}\|_{\mathrm{F}}+20\frac{\|\hat{\mathbf{Z}}\|\|\hat{\mathbf{Z}}\|_{\mathrm{F}}}{|\lambda_{2r}(\mathbf{Y}^{*})|}$
(60)

Suppose ${\mathbf{M}}^{*}$ has singular value decomposition
$\mathbf{M}^{*}=\mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^{\top}$, where
$\boldsymbol{\Sigma}=\operatorname{diag}(\sigma_{1},\cdots,\sigma_{r})\in\mathbb{R}^{r\times
r}$ with $\sigma_{1}\geq\cdots\geq\sigma_{r}>0$. Notice that

$\frac{1}{\sqrt{2}}\left(\begin{matrix}\mathbf{U}&\mathbf{U}\\\
\mathbf{V}&-\mathbf{V}\end{matrix}\right)\in\mathbb{R}^{2d\times 2r}$

is an orthogonal matrix and its columns contain $2r$ linearly independent
eigenvectors of $\mathbf{Y}^{*}$

$\frac{1}{\sqrt{2}}\left(\begin{matrix}\mathbf{U}&\mathbf{U}\\\
\mathbf{V}&-\mathbf{V}\end{matrix}\right)^{\top}\mathbf{Y}^{*}\frac{1}{\sqrt{2}}\left(\begin{matrix}\mathbf{U}&\mathbf{U}\\\
\mathbf{V}&-\mathbf{V}\end{matrix}\right)=\left(\begin{matrix}\boldsymbol{\Sigma}&0\\\
0&-\boldsymbol{\Sigma}\end{matrix}\right)$

Thus, we have $|\lambda_{2r}(\mathbf{Y}^{*})|=\sigma_{r}$. Similarly, we could
prove

$\operatorname{SVD}_{2r}(\hat{\mathbf{Y}})=\frac{1}{\sqrt{2}}\left(\begin{matrix}\hat{\mathbf{U}}_{r}&\hat{\mathbf{U}}_{r}\\\
\hat{\mathbf{V}}_{r}&-\hat{\mathbf{V}}_{r}\end{matrix}\right)^{\top}\hat{\mathbf{Y}}\frac{1}{\sqrt{2}}\left(\begin{matrix}\hat{\mathbf{U}}_{r}&\hat{\mathbf{U}}_{r}\\\
\hat{\mathbf{V}}_{r}&-\hat{\mathbf{V}}_{r}\end{matrix}\right)=\left(\begin{matrix}0&\operatorname{SVD}_{r}(\hat{\mathbf{M}})\\\
\operatorname{SVD}_{r}(\hat{\mathbf{M}}^{\top})&0\end{matrix}\right),$

which implies

$\|\operatorname{SVD}_{2r}(\hat{\mathbf{Y}})-\mathbf{Y}^{*}\|_{\mathrm{F}}=\sqrt{2}\|\operatorname{SVD}_{r}(\hat{\mathbf{M}})-\mathbf{M}^{*}\|_{\mathrm{F}}.$

Combine the above equation with
$\|\hat{\mathbf{Z}}\|_{\mathrm{F}}=\sqrt{2}\|\mathbf{Z}\|_{\mathrm{F}}$,
$\|\hat{\mathbf{Z}}\|=\|\mathbf{Z}\|$ and Equation 60 becomes

$\|\operatorname{SVD}_{r}(\hat{\mathbf{M}})-\mathbf{M}^{*}\|_{\mathrm{F}}\leq\|\mathbf{Z}\|_{\mathrm{F}}+20\frac{\|\mathbf{Z}\|\|\mathbf{Z}\|_{\mathrm{F}}}{\sigma_{r}}.$

Notice that proof of
$\|\operatorname{SVD}_{r}(\hat{\mathbf{M}})-\mathbf{M}^{*}\|_{\mathrm{F}}\leq\|\mathbf{Z}\|_{\mathrm{F}}+20\frac{\|\mathbf{Z}\|\|\mathbf{Z}\|_{\mathrm{F}}}{\sigma_{r}}$
is similar to the Frobinius norm case. Apply the perturbated eigenvector
results of Lemma 24 here and it becomes

$\bigg{\|}\frac{1}{2}\left(\begin{matrix}\hat{\mathbf{U}}_{r}&\hat{\mathbf{U}}_{r}\\\
\hat{\mathbf{V}}_{r}&-\hat{\mathbf{V}}_{r}\end{matrix}\right)^{\top}\left(\begin{matrix}\hat{\mathbf{U}}_{r}&\hat{\mathbf{U}}_{r}\\\
\hat{\mathbf{V}}_{r}&-\hat{\mathbf{V}}_{r}\end{matrix}\right)-\frac{1}{2}\left(\begin{matrix}\mathbf{U}&\mathbf{U}\\\
\mathbf{V}&-\mathbf{V}\end{matrix}\right)^{\top}\left(\begin{matrix}\mathbf{U}&\mathbf{U}\\\
\mathbf{V}&-\mathbf{V}\end{matrix}\right)\bigg{\|}\leq\frac{4\|\mathbf{Z}\|}{\sigma_{r}},$
(61)

which implies

$\|\hat{\mathbf{U}}_{r}\hat{\mathbf{U}}_{r}^{\top}-\mathbf{U}\mathbf{U}^{\top}\|\leq\frac{4\|\mathbf{Z}\|}{\sigma_{r}}=\frac{4}{\sigma_{r}}\|\hat{\mathbf{M}}-\mathbf{M}\|.$
(62)
$\|\hat{\mathbf{V}}_{r}\hat{\mathbf{V}}_{r}^{\top}-\mathbf{U}\mathbf{U}^{\top}\|\leq\frac{4\|\mathbf{Z}\|}{\sigma_{r}}=\frac{4}{\sigma_{r}}\|\hat{\mathbf{M}}-\mathbf{M}\|.$
(63)

∎

##  Appendix G Proof of Matrix Recovery Empirical Process Theorem 10

###### Proof.

The proof follows from Theorem 14. Denote
${\mathbb{M}}_{r}:=\\{{\mathbf{M}}\in{\mathbb{R}}^{d_{1}\times
d_{2}}:\text{rank}({\mathbf{M}})\leq r\\}$ the set of matrices with rank
bounded by $r$. And consider

$\displaystyle~{}~{}~{}~{}Z:=\sup_{{\mathbf{M}}\in{\mathbb{M}}_{r}}|f({\mathbf{M}})-f({\mathbf{M}}^{*})-{\mathbb{E}}(f({\mathbf{M}})-f({\mathbf{M}}^{*}))|/\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}.$

Together with
$f({\mathbf{M}})=\sum_{i=1}^{n}\rho(\langle{\mathbf{X}}_{i},{\mathbf{M}}\rangle-
y_{i})$, we have

$\displaystyle{\mathbb{E}}Z$ $\displaystyle\leq
2{\mathbb{E}}\sup_{{\mathbf{M}}\in{\mathbb{M}}_{r}}\left|\sum_{i=1}^{n}\widetilde{\epsilon}_{i}\cdot\big{(}\rho(\langle{\mathbf{X}}_{i},{\mathbf{M}}\rangle-
y_{i})-\rho(\langle{\mathbf{X}}_{i},{\mathbf{M}}^{*}\rangle-
y_{i})\big{)}\right|\cdot\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}^{-1}$
$\displaystyle\leq
4\tilde{L}\cdot{\mathbb{E}}\sup_{{\mathbf{M}}\in{\mathbb{M}}_{r}}\left|\sum_{i=1}^{n}\widetilde{\epsilon}_{i}\cdot\langle{\mathbf{X}}_{i},{\mathbf{M}}-{\mathbf{M}}^{*}\rangle\right|\cdot\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}^{-1}$
$\displaystyle\leq
4\tilde{L}\cdot{\mathbb{E}}\|\sum_{i=1}^{n}\widetilde{\epsilon}_{i}{\mathbf{X}}_{i}\|_{\mathrm{F,2r}}\leq
4\tilde{L}\cdot\sqrt{2r}{\mathbb{E}}\|\sum_{i=1}^{n}\widetilde{\epsilon}_{i}{\mathbf{X}}_{i}\|,$

where $\\{\widetilde{\epsilon}_{i}\\}_{i=1}^{n}$ is Rademacher sequence
independent of ${\mathbf{X}}_{1},\ldots,{\mathbf{X}}_{n}$. The first
inequality is from Theorem 12 and the second inequality is from Theorem 13.
Notice that $\sum_{i=1}^{n}\widetilde{\epsilon}_{i}{\mathbf{X}}_{i}$ has
i.i.d. $N(0,n)$ entries and therefore
${\mathbb{E}}\|\sum_{i=1}^{n}\widetilde{\epsilon}_{i}{\mathbf{X}}_{i}\|_{2}\leq
C_{1}\sqrt{nd}$ for some absolute constant $C_{1}>0$. And thus we have

${\mathbb{E}}Z\leq 4\sqrt{2}C_{1}\tilde{L}\sqrt{nd_{1}r}.$

Moreover,

$\displaystyle~{}~{}~{}~{}\|\sup_{{\mathbf{M}}\in{\mathbb{M}}_{r}}|\rho(Y_{i}-\langle\mathbf{X}_{i},\mathbf{M}\rangle)-\rho(Y_{i}-\langle\mathbf{X}_{i},\mathbf{M}^{*}\rangle)|\cdot\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}^{-1}\|_{\Psi_{2}}$
$\displaystyle\leq\tilde{L}\|\sup_{{\mathbf{M}}\in{\mathbb{M}}_{r}}|\langle\mathbf{X}_{i},\mathbf{M}-\mathbf{M}^{*}\rangle|\cdot\|{\mathbf{M}}-{\mathbf{M}}^{*}\|_{\rm{F}}^{-1}\|_{\Psi_{2}}$