$\displaystyle\leq\frac{2(\theta-\xi^{2})}{pm}\left(\sum_{r^{\prime}=1}^{m}\left\langle\mathbf{w}_{0,r},\mathbf{x}_{i}\right\rangle^{2}+mR^{2}\right)+\frac{2(\theta-\xi^{2})}{p}\left(\left\langle\mathbf{w}_{k,r},\mathbf{x}_{i}\right\rangle+R^{2}\right)$
$\displaystyle\leq\frac{8(\theta-\xi^{2})\kappa^{2}}{p}$

Plugging this in gives

$\displaystyle\mathbb{E}_{\mathbf{M}_{k}}\left[\|\mathbf{f}_{k,r}-\mathbf{u}_{k}\|_{2}^{2}\mid
N_{k,r}^{\perp}=1\right]\leq\frac{8(\theta-\xi^{2})n\kappa^{2}}{p}$

∎

######  Lemma 4.

Under the condition of Lemma 3, the expected norm and squared-norm of the
mixing gradient is bounded by

$\displaystyle\mathbb{E}_{\mathbf{M}_{k}}\left[\|\mathbf{g}_{k,r}\|_{2}^{2}\right]$
$\displaystyle\leq\frac{2n\theta}{m}\|\mathbf{y}-\mathbf{u}_{k}\|_{2}^{2}+\frac{16\theta(\theta-\xi^{2})n^{2}\kappa^{2}}{pm}$
$\displaystyle\mathbb{E}_{\mathbf{M}_{k}}\left[\|\mathbf{g}_{k,r}\|_{2}\right]$
$\displaystyle\leq\frac{\sqrt{n}\theta}{\sqrt{m}}\|\mathbf{y}-\mathbf{u}_{k}\|_{2}+4n\kappa\sqrt{\frac{\theta(\theta-\xi^{2})}{pm}}$

###### Proof.

Using Lemma 3, we have

$\displaystyle\mathbb{E}_{\mathbf{M}_{k}}\left[N_{k,r}^{\perp}\|\mathbf{f}_{k,r}-\mathbf{u}_{k}\|_{2}^{2}\right]=P(N_{k,r}^{\perp}=1)\mathbb{E}_{\mathbf{M}_{k}}\left[\|\mathbf{f}_{k,r}-\mathbf{u}_{k}\|_{2}^{2}\right]\leq\frac{8\theta(\theta-\xi^{2})n\kappa^{2}}{p}$

According to Jensen’s inequality, we also have

$\displaystyle\mathbb{E}_{\mathbf{M}_{k}}\left[N_{k,r}^{\perp}\|\mathbf{f}_{k,r}-\mathbf{u}_{k}\|_{2}\right]\leq
2\kappa\cdot\sqrt{\frac{2\theta(\theta-\xi^{2})n}{p}}$

Moreover, we have

$\displaystyle\mathbf{g}_{k,r}$
$\displaystyle=\frac{1}{\sqrt{m}}\sum_{i=1}^{n}\left(f_{k,r}^{(i)}-y_{i}\right)a_{r}N_{k,r}^{\perp}\mathbf{x}_{i}\mathbb{I}\\{\left\langle\mathbf{w}_{k,r},\mathbf{x}_{i}\right\rangle\geq
0\\}$
$\displaystyle=\frac{1}{\sqrt{m}}\sum_{i=1}^{n}\left(f_{k,r}^{(i)}-u_{k}^{(i)}\right)a_{r}N_{k,r}^{\perp}\mathbf{x}_{i}\mathbb{I}\\{\left\langle\mathbf{w}_{k,r},\mathbf{x}_{i}\right\rangle\geq
0\\}+\frac{N_{k,r}^{\perp}}{\xi}\cdot\frac{\partial
L(\mathbf{W}_{k})}{\partial\mathbf{w}_{r}}$

Therefore,

$\displaystyle\mathbb{E}_{\mathbf{M}_{k}}\left[\|\mathbf{g}_{k,r}\|_{2}^{2}\right]$
$\displaystyle\leq\frac{2\mathbb{E}_{\mathbf{M}_{k}}\left[N_{k,r}^{\perp}\right]}{\xi^{2}}\left\|\frac{\partial
L(\mathbf{W}_{k})}{\partial\mathbf{w}_{r}}\right\|_{2}^{2}+\frac{2}{m}\mathbb{E}_{\mathbf{M}_{k}}\left[\left\|\sum_{i=1}^{n}\left(f_{k,r}^{(i)}-u_{k}^{(i)}\right)a_{r}N_{k,r}^{\perp}\mathbf{x}_{i}\mathbb{I}\\{\left\langle\mathbf{w}_{k,r},\mathbf{x}_{i}\right\rangle\geq
0\\}\right\|_{2}^{2}\right]$
$\displaystyle\leq\frac{2n}{m}\mathbb{E}_{\mathbf{M}_{k}}\left[N_{k,r}^{\perp}\sum_{i=1}^{n}\left(f_{k,r}^{(i)}-u_{k}^{(i)}\right)^{2}\right]+\frac{2n\theta}{m}\|\mathbf{y}-\mathbf{u}_{k}\|_{2}^{2}$
$\displaystyle\leq\frac{2n}{m}\left(\mathbb{E}_{\mathbf{M}_{k}}\left[N_{k,r}^{\perp}\|\mathbf{f}_{k,r}-\mathbf{u}_{k}\|_{2}^{2}\right]+\theta\|\mathbf{y}-\mathbf{u}_{k}\|_{2}^{2}\right)$
$\displaystyle\leq\frac{2n\theta}{m}\|\mathbf{y}-\mathbf{u}_{k}\|_{2}^{2}+\frac{16\theta(\theta-\xi^{2})n^{2}\kappa^{2}}{pm}$

This shows the first inequality. To show the second, similarly we have

$\displaystyle\mathbb{E}_{\mathbf{M}_{k}}\left[\|\mathbf{g}_{k,r}\|_{2}\right]$
$\displaystyle\leq\frac{\mathbb{E}_{\mathbf{M}_{k}}\left[N_{k,r}^{\perp}\right]}{\xi}\left\|\frac{\partial
L(\mathbf{W}_{k})}{\partial\mathbf{w}_{r}}\right\|_{2}+\frac{1}{\sqrt{m}}\mathbb{E}_{\mathbf{M}_{k}}\left[\left\|\sum_{i=1}^{n}\left(f_{k,r}^{(i)}-u_{k}^{(i)}\right)a_{r}N_{k,r}^{\perp}\mathbf{x}_{i}\mathbb{I}\\{\left\langle\mathbf{w}_{k,r},\mathbf{x}_{i}\right\rangle\geq
0\\}\right\|_{2}\right]$
$\displaystyle\leq\frac{1}{\sqrt{m}}\mathbb{E}_{\mathbf{M}_{k}}\left[N_{k,r}^{\perp}\sum_{i=1}^{n}\left|f_{k,r}^{(i)}-u_{k}^{(i)}\right|\right]+\frac{\sqrt{n}\theta}{\sqrt{m}}\|\mathbf{y}-\mathbf{u}_{k}\|_{2}$
$\displaystyle\leq\sqrt{\frac{n}{m}}\mathbb{E}_{\mathbf{M}_{k}}\left[N_{k,r}^{\perp}\|\mathbf{f}_{k,r}-\mathbf{u}_{k}\|_{2}\right]+\frac{\sqrt{n}\theta}{\sqrt{m}}\|\mathbf{y}-\mathbf{u}_{k}\|_{2}$
$\displaystyle\leq\frac{\sqrt{n}\theta}{\sqrt{m}}\|\mathbf{y}-\mathbf{u}_{k}\|_{2}+4n\kappa\sqrt{\frac{\theta(\theta-\xi^{2})}{pm}}$

∎

######  Lemma 5.

Under the condition of Theorem 3, we have

$\displaystyle\left|\hat{u}_{k,t}^{l(i)}-\hat{u}_{k}^{l(i)}\right|\leq\eta
t\sqrt{n}\|\mathbf{y}-\hat{\mathbf{u}}_{k}^{l}\|_{2}$

and therefore,

$\displaystyle\left|\hat{u}_{k,t}^{l(i)}-\hat{u}_{k}^{l(i)}\right|$
$\displaystyle\leq\eta
t\sqrt{n}\left(\|\mathbf{y}-\mathbf{u}_{k}\|_{2}+\|\mathbf{u}_{k}-\hat{\mathbf{u}}_{k}^{l}\|_{2}\right)$
$\displaystyle\left(\hat{u}_{k,t}^{l(i)}-\hat{u}_{k}^{l(i)}\right)^{2}$
$\displaystyle\leq
2\eta^{2}t^{2}n\left(\|\mathbf{y}-\mathbf{u}_{k}\|_{2}^{2}+\|\mathbf{u}_{k}-\hat{\mathbf{u}}_{k}^{l}\|_{2}^{2}\right)$

###### Proof.

We have

$\displaystyle\left|\hat{u}_{k,t}^{l(i)}-\hat{u}_{k}^{l(i)}\right|$
$\displaystyle=\frac{1}{\sqrt{m}}\left|\sum_{r=1}^{m}a_{r}m_{k,r}^{l}\left(\sigma\left(\left\langle\mathbf{w}_{k,t,r}^{l},\mathbf{x}_{i}\right\rangle\right)-\sigma\left(\left\langle\mathbf{w}_{k,r},\mathbf{x}_{i}\right\rangle\right)\right)\right|$
$\displaystyle\leq\frac{1}{\sqrt{m}}\sum_{r=1}^{m}\left|\sigma\left(\left\langle\mathbf{w}_{k,t,r}^{l},\mathbf{x}_{i}\right\rangle\right)-\sigma\left(\left\langle\mathbf{w}_{k,r},\mathbf{x}_{i}\right\rangle\right)\right|$
$\displaystyle\leq\frac{1}{\sqrt{m}}\sum_{r=1}^{m}\left\|\mathbf{w}_{k,t,r}^{l}-\mathbf{w}_{k,r}\right\|_{2}$
$\displaystyle\leq\frac{\eta}{\sqrt{m}}\sum_{r=1}^{m}\sum_{t^{\prime}=0}^{t-1}\left\|\frac{\partial
L_{\mathbf{m}_{k}^{l}}\left(\mathbf{W}_{k,t}^{l}\right)}{\partial\mathbf{w}_{r}}\right\|_{2}$
$\displaystyle\leq\eta\sqrt{n}\sum_{t^{\prime}=0}^{t-1}\|\mathbf{y}-\hat{\mathbf{u}}_{k,t}^{l}\|_{2}$
$\displaystyle\leq\eta t\sqrt{n}\|\mathbf{y}-\hat{\mathbf{u}}_{k}^{l}\|_{2}$

Therefore,

$\displaystyle\left|\hat{u}_{k,t}^{l(i)}-\hat{u}_{k}^{l(i)}\right|$
$\displaystyle\leq\eta
t\sqrt{n}\left(\|\mathbf{y}-\mathbf{u}_{k}\|_{2}+\|\mathbf{u}_{k}-\hat{\mathbf{u}}_{k}^{l}\|_{2}\right)$

Moreover,

$\displaystyle\left(\hat{u}_{k,t}^{l(i)}-\hat{u}_{k}^{l(i)}\right)^{2}$
$\displaystyle=\left|\hat{u}_{k,t}^{l(i)}-\hat{u}_{k}^{l(i)}\right|^{2}\leq
2\eta^{2}t^{2}n\left(\|\mathbf{y}-\mathbf{u}_{k}\|_{2}^{2}+\|\mathbf{u}_{k}-\hat{\mathbf{u}}_{k}^{l}\|_{2}^{2}\right)$

∎

######  Lemma 6.

Under the condition of Lemma 3, with
$\eta\leq\frac{\lambda_{0}}{16(\tau-1)n^{2}}$, we have

$\displaystyle\left|\left\langle\mathbf{y}-\mathbf{u}_{k},\mathbb{E}_{\mathbf{M}_{k}}\left[\mathbf{I}_{1,k}^{\prime}\right]\right\rangle\right|\leq\frac{1}{8}\eta\theta\tau\lambda_{0}\|\mathbf{y}-\mathbf{u}_{k}\|_{2}^{2}+\frac{16\eta\theta\tau\xi^{2}(1-\xi)^{2}\kappa^{2}n^{3}d}{m\lambda_{0}}+\frac{2\eta^{3}\xi^{2}\tau(\tau-1)^{2}n^{4}pC_{1}}{\theta\lambda_{0}}$

###### Proof.

We start by analyzing $\mathbf{w}_{k+1,r}-\mathbf{w}_{k,r}$. Taking
expectation, we have

$\displaystyle\mathbb{E}_{\mathbf{M}_{k}}\left[\mathbf{w}_{k+1,r}-\mathbf{w}_{k,r}\right]$
$\displaystyle=-\eta\mathbb{E}_{\mathbf{M}_{k}}\left[\eta_{k,r}\sum_{l=1}^{p}\sum_{t=0}^{\tau-1}\frac{\partial
L_{\mathbf{m}_{k}^{l}}\left(\mathbf{W}_{k,t}^{l}\right)}{\partial\mathbf{w}_{r}}\right]$
$\displaystyle=-\eta\mathbb{E}_{\mathbf{M}_{k}}\left[\eta_{k,r}\tau\sum_{l=1}^{p}\frac{\partial
L_{\mathbf{m}_{k}^{l}}\left(\mathbf{W}_{k}\right)}{\partial\mathbf{w}_{r}}+\eta_{k,r}\sum_{l=1}^{p}\sum_{t=1}^{\tau-1}\left(\frac{\partial
L_{\mathbf{m}_{k}^{l}}\left(\mathbf{W}_{k,t}^{l}\right)}{\partial\mathbf{w}_{r}}-\frac{\partial
L_{\mathbf{m}_{k}^{l}}\left(\mathbf{W}_{k}\right)}{\partial\mathbf{w}_{r}}\right)\right]$
$\displaystyle=-\eta\tau\mathbb{E}_{\mathbf{M}_{k}}\left[\mathbf{g}_{k,r}\right]-\eta\mathbb{E}_{\mathbf{M}_{k}}\left[\eta_{k,r}\sum_{l=1}^{p}\sum_{t=1}^{\tau-1}\left(\frac{\partial
L_{\mathbf{m}_{k}^{l}}\left(\mathbf{W}_{k,t}^{l}\right)}{\partial\mathbf{w}_{r}}-\frac{\partial
L_{\mathbf{m}_{k}^{l}}\left(\mathbf{W}_{k}\right)}{\partial\mathbf{w}_{r}}\right)\right]$
$\displaystyle=-\frac{\eta\theta\tau}{\xi}\frac{\partial
L(\mathbf{W}_{k})}{\partial\mathbf{w}_{r}}-\frac{\eta\theta(1-\xi)\tau}{m}\sum_{i=1}^{n}\mathbf{x}_{i}\sigma(\left\langle\mathbf{w}_{k,r},\mathbf{x}_{i}\right\rangle)-$
$\displaystyle\quad\quad\quad\quad\eta\mathbb{E}_{\mathbf{M}_{k}}\left[\eta_{k,r}\sum_{l=1}^{p}\sum_{t=1}^{\tau-1}\left(\frac{\partial
L_{\mathbf{m}_{k}^{l}}\left(\mathbf{W}_{k,t}^{l}\right)}{\partial\mathbf{w}_{r}}-\frac{\partial
L_{\mathbf{m}_{k}^{l}}\left(\mathbf{W}_{k}\right)}{\partial\mathbf{w}_{r}}\right)\right]$

Therefore

$\displaystyle\mathbb{E}_{\mathbf{M}_{k}}\left[I_{1,k}^{(i)}\right]$
$\displaystyle=\frac{\xi}{\sqrt{m}}\sum_{r\in
S_{i}}a_{r}\mathbb{E}_{\mathbf{M}_{k}}\left[\sigma(\left\langle\mathbf{w}_{k+1,r},\mathbf{x}_{i}\right\rangle)-\sigma(\left\langle\mathbf{w}_{k,r},\mathbf{x}_{i}\right\rangle)\right]$
$\displaystyle=\frac{\xi}{\sqrt{m}}\sum_{r\in
S_{i}}a_{r}\left\langle\mathbb{E}_{\mathbf{M}_{k}}\left[\mathbf{w}_{k+1,r}-\mathbf{w}_{k,r}\right],\mathbf{x}_{i}\right\rangle\mathbb{I}\\{\left\langle\mathbf{w}_{k,r},\mathbf{x}_{i}\right\rangle\geq
0\\}$ $\displaystyle=-\frac{\eta\theta\tau}{\sqrt{m}}\sum_{r\in
S_{i}}a_{r}\left\langle\frac{\partial
L(\mathbf{W}_{k})}{\partial\mathbf{w}_{r}},\mathbf{x}_{i}\right\rangle\mathbb{I}\\{\left\langle\mathbf{w}_{k,r},\mathbf{x}_{i}\right\rangle\geq
0\\}-\eta\left(\mathcal{E}_{1,k}^{(i)}+\mathcal{E}_{2,k}^{(i)}\right)$
$\displaystyle=\frac{\eta\xi\theta\tau}{m}\sum_{r\in
S_{i}}\sum_{j=1}^{n}(y_{i}-u_{k}^{(i)})\left\langle\mathbf{x}_{i},\mathbf{x}_{j}\right\rangle\mathbb{I}\\{\left\langle\mathbf{w}_{k,r},\mathbf{x}_{i}\right\rangle\geq
0,\left\langle\mathbf{w}_{k,r},\mathbf{x}_{j}\right\rangle\geq
0\\}-\eta\left(\mathcal{E}_{1,k}^{(i)}+\mathcal{E}_{2,k}^{(i)}\right)$
$\displaystyle=\eta\theta\tau\sum_{j=1}^{n}\left(\mathbf{H}(k)_{ij}-\mathbf{H}(k)^{\perp}_{ij}\right)(y_{j}-u_{k}^{(j)})-\eta\left(\mathcal{E}_{1,k}^{(i)}+\mathcal{E}_{2,k}^{(i)}\right)$

where

$\displaystyle\mathcal{E}_{1,k}^{(i)}$
$\displaystyle=\frac{\theta\xi(1-\xi)\tau}{m^{\frac{3}{2}}}\sum_{r\in
S_{i}}\sum_{j=1}^{n}a_{r}\left\langle\mathbf{x}_{i},\mathbf{x}_{j}\right\rangle\sigma(\left\langle\mathbf{w}_{k,r},\mathbf{x}_{j}\right\rangle)$
$\displaystyle\mathcal{E}_{2,k}^{(i)}$
$\displaystyle=\frac{\xi}{\sqrt{m}}\sum_{r\in
S_{i}}a_{r}\left\langle\mathbb{E}_{\mathbf{M}_{k}}\left[\eta_{k,r}\sum_{l=1}^{p}\sum_{t=1}^{\tau-1}\left(\frac{\partial
L_{\mathbf{m}_{k}^{l}}\left(\mathbf{W}_{k,t}^{l}\right)}{\partial\mathbf{w}_{r}}-\frac{\partial
L_{\mathbf{m}_{k}^{l}}\left(\mathbf{W}_{k}\right)}{\partial\mathbf{w}_{r}}\right)\right],\mathbf{x}_{i}\right\rangle\mathbb{I}\\{\left\langle\mathbf{w}_{k,r},\mathbf{x}_{i}\right\rangle\geq
0\\}$

Let
$\mathcal{E}_{1,k}=\begin{bmatrix}\mathcal{E}_{1,k}^{(1)},\dots,\mathcal{E}_{1,k}^{(n)}\end{bmatrix}$,
and
$\mathcal{E}_{2,k}=\begin{bmatrix}\mathcal{E}_{2,k}^{(1)},\dots,\mathcal{E}_{2,k}^{(n)}\end{bmatrix}$.
Then we have

$\displaystyle\mathbb{E}_{\mathbf{M}_{k}}\left[\mathbf{I}_{1,k}\right]=\eta\theta\tau\left(\mathbf{H}(k)-\mathbf{H}(k)^{\perp}\right)(\mathbf{y}-\mathbf{u}_{k})-\eta\left(\mathbf{\mathcal{E}}_{1,k}+\mathbf{\mathcal{E}}_{2,k}\right)$

Thus,

$\displaystyle\mathbb{E}_{\mathbf{M}_{k}}\left[\mathbf{I}_{1,k}^{\prime}\right]$
$\displaystyle=\mathbb{E}_{\mathbf{M}_{k}}\left[\mathbf{I}_{1,k}\right]-\eta\theta\tau\mathbf{H}(k)(\mathbf{y}-\mathbf{u}_{k})$
$\displaystyle=\eta\theta\tau\mathbf{H}(k)^{\perp}(\mathbf{y}-\mathbf{u}_{k})+\eta\left(\mathcal{E}_{1,k}+\mathcal{E}_{2,k}\right)$

According to Lemma 7 and Lemma 8, we have the bound of
$\mathcal{E}_{1,k}^{(i)}$ and $\mathcal{E}_{2,k}^{(i)}$ as

$\displaystyle\left|\mathcal{E}_{1,k}^{(i)}\right|$
$\displaystyle\leq\theta\xi(1-\xi)\tau n\kappa\sqrt{\frac{2d}{m}}$
$\displaystyle\left|\mathcal{E}_{2,k}^{(i)}\right|$
$\displaystyle\leq\frac{\eta\xi\tau(\tau-1)n^{\frac{3}{2}}}{2}\left(\theta\|\mathbf{y}-\mathbf{u}_{k}\|_{2}+\sqrt{pC_{1}}\right)$

Moreover, according to Lemma 17, we have

$\displaystyle\|\mathbf{H}(k)^{\perp}\|_{2}\leq 4\xi n\kappa^{-1}R$

Let $R\leq\frac{\kappa\lambda_{0}}{128n}$, we have

$\displaystyle\|\mathbf{H}(k)^{\perp}\|_{2}\leq\frac{\lambda_{0}}{32}$

Therefore, we have

$\displaystyle\left|\left\langle\mathbf{y}-\mathbf{u}_{k},\mathbb{E}_{\mathbf{M}_{k}}\left[\mathbf{I}_{1,k}^{\prime}\right]\right\rangle\right|$
$\displaystyle\leq\eta\theta\tau\left|\left\langle\mathbf{y}-\mathbf{u}_{k},\mathbf{H}(k)^{\perp}(\mathbf{y}-\mathbf{u}_{k})\right\rangle\right|+\eta\sum_{i=1}^{n}\left(\left|\left(y_{i}-u_{k}^{(i)}\right)\mathcal{E}_{1,k}^{(i)}\right|+\left|\left(y_{i}-u_{k}^{(i)}\right)\mathcal{E}_{2,k}^{(i)}\right|\right)$
$\displaystyle=\eta\theta\tau\|\mathbf{H}(k)^{\perp}\|_{2}\|\mathbf{y}-\mathbf{u}_{k}\|_{2}^{2}+\max_{i\in[n]}\left(\left|\mathcal{E}_{1,k}^{(i)}\right|+\left|\mathcal{E}_{2,k}^{(i)}\right|\right)\eta\sum_{i=1}^{n}\left|y_{i}-u_{k}^{(i)}\right|$
$\displaystyle\leq\frac{1}{32}\eta\theta\tau\lambda_{0}\|\mathbf{y}-\mathbf{u}_{k}\|_{2}^{2}+\max_{i\in[n]}\left(\left|\mathcal{E}_{1,k}^{(i)}\right|+\left|\mathcal{E}_{2,k}^{(i)}\right|\right)\eta\sqrt{n}\|\mathbf{y}-\mathbf{u}_{k}\|_{2}$
$\displaystyle\leq\frac{1}{32}\eta\theta\tau\lambda_{0}\|\mathbf{y}-\mathbf{u}_{k}\|_{2}^{2}+\frac{\eta^{2}\theta\xi\tau(\tau-1)n^{2}}{2}\|\mathbf{y}-\mathbf{u}_{k}\|_{2}^{2}+$
$\displaystyle\quad\quad\quad\quad\left(\eta\theta\xi(1-\xi)\tau\kappa\sqrt{\frac{2n^{3}d}{m}}+\frac{\eta^{2}\xi\tau(\tau-1)n^{2}}{2}\sqrt{pC_{1}}\right)\|\mathbf{y}-\mathbf{u}_{k}\|_{2}$

Using the general inequality that $ab\leq\frac{1}{2}(a^{2}+b^{2})$, and
$\eta\leq\frac{\lambda_{0}}{16(\tau-1)n^{2}}$, we get

$\displaystyle\left|\left\langle\mathbf{y}-\mathbf{u}_{k},\mathbb{E}_{\mathbf{M}_{k}}\left[\mathbf{I}_{1,k}^{\prime}\right]\right\rangle\right|\leq\frac{1}{8}\eta\theta\tau\lambda_{0}\|\mathbf{y}-\mathbf{u}_{k}\|_{2}^{2}+\frac{16\eta\theta\tau\xi^{2}(1-\xi)^{2}\kappa^{2}n^{3}d}{m\lambda_{0}}+\frac{2\eta^{3}\xi^{2}\tau(\tau-1)^{2}n^{4}pC_{1}}{\theta\lambda_{0}}$

∎

######  Lemma 7.

Under the assumption of Theorem 3 we have that for all $k\in[K],i\in[n]$, it
holds that

$\displaystyle\left|\mathcal{E}_{1,k}^{(i)}\right|$
$\displaystyle\leq\theta\xi(1-\xi)\tau n\kappa\sqrt{\frac{2d}{m}}$

###### Proof.

We have

$\displaystyle\left|\mathcal{E}_{1,k}^{(i)}\right|$
$\displaystyle\leq\frac{\theta\xi(1-\xi)\tau}{m^{\frac{3}{2}}}\left|\sum_{r\in
S_{i}}\sum_{j=1}^{n}a_{r}\left\langle\mathbf{x}_{i},\mathbf{x}_{j}\right\rangle\sigma(\left\langle\mathbf{w}_{k,r},\mathbf{x}_{j}\right\rangle)\right|$
$\displaystyle\leq\frac{\theta\xi(1-\xi)\tau}{m^{\frac{3}{2}}}\sum_{r\in
S_{i}}\sum_{j=1}^{n}\left|\left\langle\mathbf{w}_{k,r},\mathbf{x}_{i}\right\rangle\right|$
$\displaystyle\leq\frac{\theta\xi(1-\xi)\tau n}{m^{\frac{3}{2}}}\sum_{r\in
S_{i}}\|\mathbf{w}_{k,r}\|_{2}$ $\displaystyle\leq\frac{\theta\xi(1-\xi)\tau
n}{m^{\frac{3}{2}}}\sum_{r\in S_{i}}\left(\|\mathbf{w}_{0,r}\|_{2}+R\right)$
$\displaystyle\leq\frac{\theta\xi(1-\xi)\tau
n}{m}\|\mathbf{W}_{0}\|_{F}+\frac{\theta\xi(1-\xi)\tau nR}{\sqrt{m}}$
$\displaystyle\leq\theta\xi(1-\xi)\tau n\kappa\sqrt{\frac{2d}{m}}$

where for the bound of $\|\mathbf{W}_{0}\|_{F}$ we use Lemma 22. ∎

######  Lemma 8.

Suppose $\|\mathbf{w}_{k,t,r}-\mathbf{w}_{0,r}\|_{2}\leq R$ for all $r\in[m]$.
Then we have

$\displaystyle\left|\mathcal{E}_{2,t}^{(i)}\right|\leq\frac{\eta\xi\tau(\tau-1)n^{\frac{3}{2}}}{2}\left(\theta\|\mathbf{y}-\mathbf{u}_{k}\|_{2}+\sqrt{pC_{1}}\right)$

###### Proof.

Since $r\in S_{i}$, the difference between the surrogate gradients of a sub-
network has the form

$\displaystyle\left\|\frac{\partial
L_{\mathbf{m}_{k}^{l}}\left(\mathbf{W}_{k,t}^{l}\right)}{\partial\mathbf{w}_{r}}-\frac{\partial
L_{\mathbf{m}_{k}^{l}}\left(\mathbf{W}_{k}\right)}{\partial\mathbf{w}_{r}}\right\|_{2}$
$\displaystyle=\frac{1}{\sqrt{m}}\left\|\sum_{j=1}^{n}a_{r}m_{k,r}^{l}\mathbf{x}_{j}\left(\hat{u}_{k,t}^{l(j)}-\hat{u}_{k}^{l(j)}\right)\mathbb{I}\\{\left\langle\mathbf{w}_{k,r},\mathbf{x}_{j}\right\rangle\geq
0\\}\right\|_{2}$
$\displaystyle\leq\frac{m_{k,r}^{l}}{\sqrt{m}}\sum_{j=1}^{n}\left|\hat{u}_{k,t}^{l(j)}-\hat{u}_{k}^{l(j)}\right|$

Therefore, using the convexity of $\ell_{2}$-norm,

$\displaystyle\left\|\mathbb{E}_{\mathbf{M}_{k}}\left[\eta_{k,r}\sum_{l=1}^{p}\left(\frac{\partial
L_{\mathbf{m}_{k}^{l}}\left(\mathbf{W}_{k,t}^{l}\right)}{\partial\mathbf{w}_{r}}-\frac{\partial
L_{\mathbf{m}_{k}^{l}}\left(\mathbf{W}_{k}\right)}{\partial\mathbf{w}_{r}}\right)\right]\right\|_{2}$
$\displaystyle\leq\mathbb{E}_{\mathbf{M}_{k}}\left[\eta_{k,r}\left\|\sum_{l=1}^{p}\left(\frac{\partial
L_{\mathbf{m}_{k}^{l}}\left(\mathbf{W}_{k,t}^{l}\right)}{\partial\mathbf{w}_{r}}-\frac{\partial
L_{\mathbf{m}_{k}^{l}}\left(\mathbf{W}_{k}\right)}{\partial\mathbf{w}_{r}}\right)\right\|_{2}\right]$
$\displaystyle\leq\mathbb{E}_{\mathbf{M}_{k}}\left[\eta_{k,r}\sum_{l=1}^{p}\left\|\frac{\partial
L_{\mathbf{m}_{k}^{l}}\left(\mathbf{W}_{k,t}^{l}\right)}{\partial\mathbf{w}_{r}}-\frac{\partial
L_{\mathbf{m}_{k}^{l}}\left(\mathbf{W}_{k}\right)}{\partial\mathbf{w}_{r}}\right\|_{2}\right]$
$\displaystyle\leq\mathbb{E}_{\mathbf{M}_{k}}\left[\frac{\eta_{k,r}}{\sqrt{m}}\sum_{l=1}^{p}m_{k,r}\sum_{j=1}^{n}\left|\hat{u}_{k,t}^{l(j)}-\hat{u}_{k}^{l(j)}\right|\right]$

By Lemma 5, we have

$\displaystyle\left|\hat{u}_{k,t}^{l(i)}-\hat{u}_{k}^{l(i)}\right|\leq\eta
t\sqrt{n}\left(\|\mathbf{y}-\mathbf{u}_{k}\|_{2}+\|\mathbf{u}_{k}-\hat{\mathbf{u}}_{k}^{l}\|_{2}\right)$

Therefore,

$\displaystyle\left|\mathcal{E}_{2,t}^{(i)}\right|$
$\displaystyle\leq\frac{\xi}{\sqrt{m}}\sum_{r\in
S_{i}}\left\|\mathbb{E}_{\mathbf{M}_{k}}\left[\eta_{k,r}\sum_{l=1}^{p}\sum_{t=1}^{\tau-1}\left(\frac{\partial
L_{\mathbf{m}_{k}^{l}}\left(\mathbf{W}_{k,t}^{l}\right)}{\partial\mathbf{w}_{r}}-\frac{\partial
L_{\mathbf{m}_{k}^{l}}\left(\mathbf{W}_{k}\right)}{\partial\mathbf{w}_{r}}\right)\right]\right\|_{2}$
$\displaystyle\leq\frac{\xi}{\sqrt{m}}\sum_{t=1}^{\tau-1}\sum_{r\in
S_{i}}\left\|\mathbb{E}_{\mathbf{M}_{k}}\left[\eta_{k,r}\sum_{l=1}^{p}\left(\frac{\partial
L_{\mathbf{m}_{k}^{l}}\left(\mathbf{W}_{k,t}^{l}\right)}{\partial\mathbf{w}_{r}}-\frac{\partial
L_{\mathbf{m}_{k}^{l}}\left(\mathbf{W}_{k}\right)}{\partial\mathbf{w}_{r}}\right)\right]\right\|_{2}$
$\displaystyle\leq\frac{\xi}{\sqrt{m}}\sum_{t=1}^{\tau-1}\sum_{r\in
S_{i}}\mathbb{E}_{\mathbf{M}_{k}}\left[\frac{\eta_{k,r}}{\sqrt{m}}\sum_{l=1}^{p}m_{k,r}\sum_{j=1}^{n}\left|\hat{u}_{k,t}^{l(j)}-\hat{u}_{k}^{l(j)}\right|\right]$
$\displaystyle\leq\frac{\eta\xi
n^{\frac{3}{2}}}{m}\sum_{t=1}^{\tau-1}t\sum_{r\in
S_{i}}\mathbb{E}_{\mathbf{M}_{k}}\left[\eta_{k,r}\sum_{l=1}^{p}m_{k,r}\left(\|\mathbf{y}-\mathbf{u}_{k}\|_{2}+\|\mathbf{y}-\hat{\mathbf{u}}_{k}^{l}\|_{2}\right)\right]$
$\displaystyle\leq\frac{\eta\xi\tau(\tau-1)n^{\frac{3}{2}}}{2}\left(]\theta\|\mathbf{y}-\mathbf{u}_{k}\|_{2}+\mathbb{E}_{\mathbf{M}_{k}}\left[\eta_{k,r}\sum_{l=1}^{p}m_{k,r}^{l}\|\mathbf{u}_{k}-\hat{\mathbf{u}}_{k}^{l}\|_{2}\right]\right)$
$\displaystyle\leq\frac{\eta\xi\tau(\tau-1)n^{\frac{3}{2}}}{2}\left(\theta\|\mathbf{y}-\mathbf{u}_{k}\|_{2}+\sqrt{pC_{1}}\right)$

where the last inequality follows from Lemma 24. ∎

######  Lemma 9.

Under the condition of Theorem 3, we have

$\displaystyle\left|\left\langle\mathbf{y}-\mathbf{u}_{k},\mathbb{E}_{\mathbf{M}_{k}}\left[\mathbf{I}_{2}\right]\right\rangle\right|\leq\frac{1}{8}\eta\theta\tau\lambda_{0}\|\mathbf{y}-\mathbf{u}_{k}\|_{2}^{2}+\frac{\eta\lambda_{0}\xi^{2}(\theta-\xi^{2})n\kappa^{2}}{24p\tau}+\frac{\eta\lambda_{0}\xi^{2}(\tau-1)^{2}pC_{1}}{96\tau\theta}$

###### Proof.

To start, we notice that Using the $1$-Lipschitzness of ReLU, we have

$\displaystyle\mathbb{E}_{\mathbf{M}_{k}}\left[\left|I_{2,k}^{(i)}\right|\right]$
$\displaystyle=\frac{\xi}{\sqrt{m}}\mathbb{E}_{\mathbf{M}_{k}}\left[\left|\sum_{r\in
S_{i}^{\perp}}a_{r}\left(\sigma(\left\langle\mathbf{w}_{k+1,r},\mathbf{x}_{i}\right\rangle-\sigma(\left\langle\mathbf{w}_{k+1,r},\mathbf{x}_{i}\right\rangle\right)\right|\right]$
$\displaystyle\leq\frac{\xi}{\sqrt{m}}\sum_{r\in
S_{i}^{\perp}}\mathbb{E}_{\mathbf{M}_{k}}\left[\left|\sigma(\left\langle\mathbf{w}_{k+1,r},\mathbf{x}_{i}\right\rangle-\sigma(\left\langle\mathbf{w}_{k+1,r},\mathbf{x}_{i}\right\rangle\right|\right]$
$\displaystyle\leq\frac{\xi}{\sqrt{m}}\sum_{r\in
S_{i}^{\perp}}\mathbb{E}_{\mathbf{M}_{k}}\left[\left|\left\langle\mathbf{w}_{k+1,r}-\mathbf{w}_{k,r},\mathbf{x}_{i}\right\rangle\right|\right]$
$\displaystyle\leq\frac{\xi}{\sqrt{m}}\sum_{r\in
S_{i}^{\perp}}\mathbb{E}_{\mathbf{M}_{k}}\left[\|\mathbf{w}_{k+1,r}-\mathbf{w}_{k,r}\|_{2}\right]$
$\displaystyle\leq\frac{\eta\xi}{\sqrt{m}}\sum_{r\in
S_{i}^{\perp}}\mathbb{E}_{\mathbf{M}_{k}}\left[\left\|\eta_{k,r}\sum_{t=0}^{\tau-1}\sum_{l=1}^{p}\frac{\partial
L_{\mathbf{m}_{k}^{l}}\left(\mathbf{W}_{k,t}^{l}\right)}{\partial\mathbf{w}_{r}}\right\|_{2}\right]$
$\displaystyle\leq\frac{\eta\xi}{\sqrt{m}}\sum_{r\in
S_{i}^{\perp}}\left(\mathbb{E}_{\mathbf{M}_{k}}\left[\|\mathbf{g}_{k,r}\|_{2}\right]+\mathbb{E}_{\mathbf{M}_{k}}\left[\eta_{k,r}\sum_{t=1}^{\tau-1}\sum_{l=1}^{p}\left\|\frac{\partial
L_{\mathbf{m}_{k}}\left(\mathbf{W}_{k,t}^{l}\right)}{\partial\mathbf{w}_{r}}\right\|_{2}\right]\right)$
$\displaystyle\leq\frac{\eta\theta\xi\sqrt{n}}{m}|S_{i}^{\perp}|\|\mathbf{y}-\mathbf{u}_{k}\|_{2}+\frac{4\eta\xi\kappa
n|S_{i}^{\perp}|}{m}\sqrt{\frac{\theta(\theta-\xi^{2})}{p}}+$
$\displaystyle\quad\quad\quad\quad\frac{\eta\xi\sqrt{n}}{m}\sum_{r\in
S_{i}^{\perp}}\mathbb{E}_{\mathbf{M}_{k}}\left[\eta_{k,r}\sum_{t=1}^{\tau-1}\sum_{l=1}^{p}m_{k,r}^{l}\|\mathbf{y}-\hat{\mathbf{u}}_{k,t}^{l}\|_{2}\right]$
$\displaystyle\leq\frac{\eta\theta\xi\sqrt{n}}{m}|S_{i}^{\perp}|\|\mathbf{y}-\mathbf{u}_{k}\|_{2}+\frac{4\eta\xi\kappa
n|S_{i}^{\perp}|}{m}\sqrt{\frac{\theta(\theta-\xi^{2})}{p}}+$
$\displaystyle\quad\quad\quad\quad\frac{\eta\xi\sqrt{n}}{m}\sum_{r\in
S_{i}^{\perp}}\mathbb{E}_{\mathbf{M}_{k}}\left[\eta_{k,r}\sum_{t=1}^{\tau-1}\sum_{l=1}^{p}m_{k,r}^{l}\|\mathbf{y}-\hat{\mathbf{u}}_{k}^{l}\|_{2}\right]$
$\displaystyle\leq\frac{\eta\theta\xi\tau\sqrt{n}}{m}|S_{i}^{\perp}|\|\mathbf{y}-\mathbf{u}_{k}\|_{2}+\frac{4\eta\xi\kappa
n|S_{i}^{\perp}|}{m}\sqrt{\frac{\theta(\theta-\xi^{2})}{p}}+$
$\displaystyle\quad\quad\quad\quad\frac{\eta\xi\sqrt{n}}{m}\sum_{r\in
S_{i}^{\perp}}\mathbb{E}_{\mathbf{M}_{k}}\left[\eta_{k,r}\sum_{t=1}^{\tau-1}\sum_{l=1}^{p}m_{k,r}^{l}\|\mathbf{u}_{k}-\hat{\mathbf{u}}_{k}^{l}\|_{2}\right]$

where in the seventh inequality we use the bound on
$\mathbb{E}_{\mathbf{M}_{k}}\left[\|\mathbf{g}_{k,r}\|_{2}\right]$ from Lemma
4. Moreover, using Lemma 24 we have

$\displaystyle\mathbb{E}_{\mathbf{M}_{k}}\left[\eta_{k,r}\sum_{l=1}^{p}m_{k,r}^{l}\|\mathbf{u}_{k}-\hat{\mathbf{u}}_{k}^{l}\|_{2}\right]\leq\sqrt{pC_{1}}$

Then we have

$\displaystyle\mathbb{E}_{\mathbf{M}_{k}}\left[\left|I_{2,k}^{(i)}\right|\right]$
$\displaystyle\leq\frac{\eta\theta\xi\tau\sqrt{n}}{m}|S_{i}^{\perp}|\|\mathbf{y}-\mathbf{u}_{k}\|_{2}+\frac{4\eta\xi\kappa
n|S_{i}^{\perp}|}{m}\sqrt{\frac{\theta(\theta-\xi^{2})}{p}}+\frac{\eta\xi(\tau-1)}{m}\sqrt{npC_{1}}|S_{i}^{\perp}|$
$\displaystyle\leq
8\eta\theta\xi\tau\sqrt{n}\kappa^{-1}R\|\mathbf{y}-\mathbf{u}_{k}\|_{2}+16\eta\xi
nR\sqrt{\frac{\theta(\theta-\xi^{2})}{p}}+4\eta\xi(\tau-1)\kappa^{-1}R\sqrt{npC_{1}}$

where in the last inequality we use $|S_{i}^{\perp}|\leq 4m\kappa^{-1}R$.
Therefore,

$\displaystyle\left|\left\langle\mathbf{y}-\mathbf{u}_{k},\mathbb{E}_{\mathbf{M}_{k}}\left[\mathbf{I}_{2,k}\right]\right\rangle\right|$
$\displaystyle=\left|\sum_{i=1}^{n}(y_{i}-u_{k}^{(i)})\mathbb{E}_{\mathbf{M}_{k}}\left[I_{2,k}^{(i)}\right]\right|$
$\displaystyle\leq\sum_{i=1}^{n}\left|y_{i}-u_{k}^{(i)}\right|\cdot\left|\mathbb{E}_{\mathbf{M}_{k}}\left[I_{2,k}^{(i)}\right]\right|$
$\displaystyle\leq\max_{i\in[n]}\left|\mathbb{E}_{\mathbf{M}_{k}}\left[I_{2,k}^{(i)}\right]\right|\sum_{i=1}^{n}\left|y_{i}-u_{k}^{(i)}\right|$
$\displaystyle\leq\sqrt{n}\max_{i\in[n]}\left|\mathbb{E}_{\mathbf{M}_{k}}\left[I_{2,k}^{(i)}\right]\right|\|\mathbf{y}-\mathbf{u}_{k}\|_{2}$
$\displaystyle\leq
8\eta\theta\xi\tau\kappa^{-1}nR\|\mathbf{y}-\mathbf{u}_{k}\|_{2}^{2}+16\eta\xi
R\sqrt{\frac{\theta(\theta-\xi^{2})n^{3}}{p}}\|\mathbf{y}-\mathbf{u}_{k}\|_{2}+$
$\displaystyle\quad\quad\quad\quad
4\eta\xi(\tau-1)\kappa^{-1}nR\sqrt{pC_{1}}\|\mathbf{y}-\mathbf{u}_{k}\|_{2}$
$\displaystyle\leq\frac{1}{8}\eta\theta\tau\lambda_{0}\|\mathbf{y}-\mathbf{u}_{k}\|_{2}^{2}+\frac{\eta\lambda_{0}\xi^{2}(\theta-\xi^{2})n\kappa^{2}}{24p\tau}+\frac{\eta\lambda_{0}\xi^{2}(\tau-1)^{2}pC_{1}}{96\tau\theta}$

where in the last inequality we use $R\leq\frac{\kappa\lambda_{0}}{192n}$ and
$ab\leq\frac{1}{2}(a^{2}+b^{2})$. ∎

######  Lemma 10.

Under the condition of Theorem 3, with
$\eta\leq\frac{\lambda_{0}}{48n\tau\max\\{n,p\\}}$, we have

$\displaystyle\mathbb{E}_{\mathbf{M}_{k}}\left[\|\mathbf{u}_{k+1}-\mathbf{u}_{k}\|_{2}^{2}\right]\leq\frac{1}{4}\eta\theta\tau\lambda_{0}\|\mathbf{y}-\mathbf{u}_{k}\|_{2}^{2}+\frac{17\eta^{2}\xi^{2}\tau^{2}\theta(\theta-\xi^{2})n^{3}\kappa^{2}}{p}+\eta^{2}\xi^{2}\lambda_{0}(\tau-1)^{2}pnC_{1}$

###### Proof.

As in previous lemma, we use the Lipschitzness of ReLU to get

$\displaystyle\mathbb{E}_{\mathbf{M}_{k}}\left[\left(u_{k+1}^{(i)}-u_{k}^{(i)}\right)^{2}\right]$
$\displaystyle\leq\frac{\xi^{2}}{m}\mathbb{E}_{\mathbf{M}_{k}}\left[\left(\sum_{r=1}^{m}a_{r}\left(\sigma(\left\langle\mathbf{w}_{k+1,r},\mathbf{x}_{i}\right\rangle)-\sigma(\left\langle\mathbf{w}_{k,r},\mathbf{x}_{i}\right\rangle)\right)\right)^{2}\right]$
$\displaystyle\leq\xi^{2}\sum_{r=1}^{m}\mathbb{E}_{\mathbf{M}_{k}}\left[\left(\sigma(\left\langle\mathbf{w}_{k+1,r},\mathbf{x}_{i}\right\rangle)-\sigma(\left\langle\mathbf{w}_{k,r},\mathbf{x}_{i}\right\rangle)\right)^{2}\right]$
$\displaystyle\leq\xi^{2}\sum_{r=1}^{m}\mathbb{E}_{\mathbf{M}_{k}}\left[\left\langle\mathbf{w}_{k+1,r}-\mathbf{w}_{k,r},\mathbf{x}_{i}\right\rangle^{2}\right]$
$\displaystyle\leq\xi^{2}\sum_{r=1}^{m}\mathbb{E}_{\mathbf{M}_{k}}\left[\left\|\mathbf{w}_{k+1,r}-\mathbf{w}_{k,r}\right\|_{2}^{2}\right]$
$\displaystyle=\xi^{2}\left(D_{1,k}+D_{2,k}\right)$

where

$\displaystyle D_{1,k}$ $\displaystyle=\sum_{r\in
S_{i}}\mathbb{E}_{\mathbf{M}_{k}}\left[\left\|\mathbf{w}_{k+1,r}-\mathbf{w}_{k,r}\right\|_{2}^{2}\right]$
$\displaystyle D_{2,k}$ $\displaystyle=\sum_{r\in
S_{i}^{\perp}}\mathbb{E}_{\mathbf{M}_{k}}\left[\left\|\mathbf{w}_{k+1,r}-\mathbf{w}_{k,r}\right\|_{2}^{2}\right]$

Using Lemma 11 and Lemma 12 we have

$\displaystyle D_{1,k}$
$\displaystyle\leq\left(4\eta^{2}\tau^{2}n\theta+4\eta^{4}\theta
n^{3}\tau^{3}(\tau-1)p\right)\|\mathbf{y}-\mathbf{u}_{k}\|_{2}^{2}+\frac{16\eta^{2}\tau^{2}\theta(\theta-\xi^{2})n^{2}\kappa^{2}}{p}+4\eta^{4}n^{3}\tau^{2}(\tau-1)^{2}pC_{1}$
$\displaystyle D_{2,k}$
$\displaystyle\leq\frac{\eta^{2}\theta\tau\lambda_{0}}{18}\left(1+(\tau-1)p\right)\|\mathbf{y}-\mathbf{u}_{k}\|_{2}^{2}+\frac{4\eta^{2}\lambda_{0}\theta(\theta-\xi^{2})\tau
n\kappa^{2}}{9p}+\frac{\eta^{2}\tau(\tau-1)\lambda_{0}pC_{1}}{18}$

Therefore we have

$\displaystyle\mathbb{E}_{\mathbf{M}_{k}}\left[\|\mathbf{u}_{k+1}-\mathbf{u}_{k}\|_{2}^{2}\right]$
$\displaystyle\leq\xi^{2}n\left(D_{1,k}+D_{2,k}\right)$
$\displaystyle\leq\left(4\eta^{2}\xi^{2}\tau^{2}n^{2}\theta+4\eta^{4}\theta\xi^{2}n^{4}\tau^{3}(\tau-1)p+\frac{\eta^{2}\theta\tau
n\lambda_{0}}{18}\left(1+(\tau-1)p\right)\right)\|\mathbf{y}-\mathbf{u}_{k}\|_{2}^{2}+$
$\displaystyle\quad\quad\quad\quad\frac{16\eta^{2}\xi^{2}\tau^{2}\theta(\theta-\xi^{2})n^{3}\kappa^{2}}{p}+4\eta^{4}\xi^{2}n^{4}\tau^{2}(\tau-1)^{2}pC_{1}+\frac{4\eta^{2}\lambda_{0}\xi^{2}\theta(\theta-\xi^{2})\tau
n^{2}\kappa^{2}}{9p}+$
$\displaystyle\quad\quad\quad\quad\frac{\eta^{2}\xi^{2}\tau(\tau-1)n\lambda_{0}pC_{1}}{18}$

With $\eta\leq\frac{\lambda_{0}}{48n\tau\max\\{n,p\\}}$, we have

$\displaystyle\mathbb{E}_{\mathbf{M}_{k}}\left[\|\mathbf{u}_{k+1}-\mathbf{u}_{k}\|_{2}^{2}\right]$
$\displaystyle\leq\frac{1}{4}\eta\theta\tau\lambda_{0}\|\mathbf{y}-\mathbf{u}_{k}\|_{2}^{2}+\frac{17\eta^{2}\xi^{2}\tau^{2}\theta(\theta-\xi^{2})n^{3}\kappa^{2}}{p}+\eta^{2}\xi^{2}\lambda_{0}(\tau-1)^{2}pnC_{1}$

∎

######  Lemma 11.

$\displaystyle D_{1,k}\leq\left(4\eta^{2}\tau^{2}n\theta+4\eta^{4}\theta
n^{3}\tau^{3}(\tau-1)p\right)\|\mathbf{y}-\mathbf{u}_{k}\|_{2}^{2}+\frac{16\eta^{2}\tau^{2}\theta(\theta-\xi^{2})n^{2}\kappa^{2}}{p}+4\eta^{4}n^{3}\tau^{2}(\tau-1)^{2}pC_{1}$

###### Proof.

We have

$\displaystyle D_{1,k}$ $\displaystyle=\eta^{2}\sum_{r\in
S_{i}}\mathbb{E}_{\mathbf{M}_{k}}\left[\left\|\eta_{k,r}\sum_{t=0}^{\tau-1}\sum_{l=1}^{p}\frac{\partial
L_{\mathbf{m}_{k}^{l}}\left(\mathbf{W}_{k,t}^{l}\right)}{\partial\mathbf{w}_{r}}\right\|_{2}^{2}\right]$
$\displaystyle\leq\eta^{2}\sum_{r\in
S_{i}}\mathbb{E}_{\mathbf{M}_{k}}\left[\left\|\tau\mathbf{g}_{k,r}+\eta_{k,r}\sum_{t=1}^{\tau-1}\sum_{l=1}^{p}\left(\frac{\partial
L_{\mathbf{m}_{k}^{l}}\left(\mathbf{W}_{k,t}^{l}\right)}{\partial\mathbf{w}_{r}}-\frac{\partial
L_{\mathbf{m}_{k}^{l}}\left(\mathbf{W}_{k}\right)}{\partial\mathbf{w}_{r}}\right)\right\|_{2}^{2}\right]$
$\displaystyle\leq 2\eta^{2}\tau^{2}\sum_{r\in
S_{i}}\mathbb{E}_{\mathbf{M}_{k}}\left[\|\mathbf{g}_{k,r}\|_{2}^{2}\right]+2\eta^{2}(\tau-1)p\sum_{r\in
S_{i}}\sum_{t=1}^{\tau-1}\mathbb{E}_{\mathbf{M}_{k}}\left[\eta_{k,r}^{2}\sum_{l=1}^{p}\left\|\frac{\partial
L_{\mathbf{m}_{k}^{l}}\left(\mathbf{W}_{k,t}^{l}\right)}{\partial\mathbf{w}_{r}}-\frac{\partial
L_{\mathbf{m}_{k}^{l}}\left(\mathbf{W}_{k}\right)}{\partial\mathbf{w}_{r}}\right\|_{2}^{2}\right]$

Note that for $r\in S_{i}$, we have

$\displaystyle\left\|\frac{\partial
L_{\mathbf{m}_{k}^{l}}\left(\mathbf{W}_{k,t}^{l}\right)}{\partial\mathbf{w}_{r}}-\frac{\partial
L_{\mathbf{m}_{k}^{l}}\left(\mathbf{W}_{k}\right)}{\partial\mathbf{w}_{r}}\right\|_{2}^{2}$
$\displaystyle=\frac{m_{k,r}}{m}\left\|\sum_{i=1}^{n}a_{r}\mathbf{x}_{i}\left(\hat{u}_{k,t}^{l(i)}-\hat{u}_{k}^{l(i)}\right)\mathbb{I}\\{\left\langle\mathbf{w}_{k,r},\mathbf{x}_{i}\right\rangle\\}\geq
0\right\|_{2}^{2}$
$\displaystyle\leq\frac{nm_{k,r}}{m}\sum_{i=1}^{n}\left(\hat{u}_{k,t}^{l(i)}-\hat{u}_{k}^{l(i)}\right)^{2}$
$\displaystyle\leq\frac{n^{2}m_{k,r}^{l}}{m}\left(2\eta^{2}t^{2}n\|\mathbf{y}-\mathbf{u}_{k}\|_{2}^{2}+2\eta^{2}t^{2}n\|\mathbf{u}_{k}-\hat{\mathbf{u}}_{k}^{l}\|_{2}^{2}\right)$

where in the last inequality we use Lemma 5. Plugging in the bound above and
the bound on
$\mathbb{E}_{\mathbf{M}_{k}}\left[\|\mathbf{g}_{k}\|_{2}^{2}\right]$ from
Lemma 4 gives

$\displaystyle D_{1,k}$ $\displaystyle\leq
4\eta^{2}\tau^{2}n\theta\|\mathbf{y}-\mathbf{u}_{k}\|_{2}^{2}+\frac{16\eta^{2}\tau^{2}\theta(\theta-\xi^{2})n^{2}\kappa^{2}}{p}+4\eta^{4}\theta
n^{3}\tau^{3}(\tau-1)p\|\mathbf{y}-\mathbf{u}_{k}\|_{2}^{2}+$
$\displaystyle\quad\quad\quad\quad
4\eta^{4}n^{3}\tau^{3}(\tau-1)p\mathbb{E}_{\mathbf{M}_{k}}\left[\eta_{k,r}^{2}\sum_{l=1}^{p}m_{k,r}^{l}\|\mathbf{u}_{k}-\hat{\mathbf{u}}_{k}^{l}\|_{2}^{2}\right]$
$\displaystyle\leq\left(4\eta^{2}\tau^{2}n\theta+4\eta^{4}\theta
n^{3}\tau^{3}(\tau-1)p\right)\|\mathbf{y}-\mathbf{u}_{k}\|_{2}^{2}+\frac{16\eta^{2}\tau^{2}\theta(\theta-\xi^{2})n^{2}\kappa^{2}}{p}+4\eta^{4}n^{3}\tau^{2}(\tau-1)^{2}pC_{1}$

∎

######  Lemma 12.

$\displaystyle
D_{2,k}\leq\frac{\eta^{2}\theta\tau\lambda_{0}}{18}\left(1+(\tau-1)p\right)\|\mathbf{y}-\mathbf{u}_{k}\|_{2}^{2}+\frac{4\eta^{2}\lambda_{0}\theta(\theta-\xi^{2})\tau
n\kappa^{2}}{9p}+\frac{\eta^{2}\tau(\tau-1)\lambda_{0}pC_{1}}{18}$

###### Proof.

$\displaystyle D_{2,k}$ $\displaystyle=\eta^{2}\sum_{r\in
S_{i}^{\perp}}\mathbb{E}_{\mathbf{M}_{k}}\left[\left\|\eta_{k,r}\sum_{t=0}^{\tau-1}\sum_{l=1}^{p}\frac{\partial
L_{\mathbf{m}_{k}^{l}}\left(\mathbf{W}_{k,t}^{l}\right)}{\partial\mathbf{w}_{r}}\right\|_{2}^{2}\right]$
$\displaystyle\leq\eta^{2}\tau\sum_{r\in
S_{i}^{\perp}}\left(\mathbb{E}_{\mathbf{M}_{k}}\left[\|\mathbf{g}_{k,r}\|_{2}^{2}\right]+\sum_{t=1}^{\tau-1}\mathbb{E}_{\mathbf{M}_{k}}\left[\left\|\eta_{k,r}\sum_{l=1}^{p}\frac{\partial
L_{\mathbf{m}_{k}^{l}}\left(\mathbf{W}_{k,t}^{l}\right)}{\partial\mathbf{w}_{r}}\right\|_{2}^{2}\right]\right)$
$\displaystyle\leq\eta^{2}\tau\sum_{r\in
S_{i}^{\perp}}\left(\mathbb{E}_{\mathbf{M}_{k}}\left[\|\mathbf{g}_{k,r}\|_{2}^{2}\right]+p\sum_{t=1}^{\tau-1}\mathbb{E}_{\mathbf{M}_{k}}\left[\eta_{k,r}^{2}\sum_{l=1}^{p}\left\|\frac{\partial
L_{\mathbf{m}_{k}}\left(\mathbf{W}_{k,t}^{l}\right)}{\partial\mathbf{w}_{r}}\right\|_{2}^{2}\right]\right)$
$\displaystyle\leq\frac{2\eta^{2}\tau
n\theta}{m}|S_{i}^{\perp}|\|\mathbf{y}-\mathbf{u}_{k}\|_{2}^{2}+\frac{8\eta^{2}\theta(\theta-\xi^{2})\tau
n^{2}\kappa^{2}}{pm}|S_{i}^{\perp}|+\frac{\eta^{2}\tau
np}{m}|S_{i}^{\perp}|\sum_{t=1}^{\tau-1}\mathbb{E}_{\mathbf{M}_{k}}\left[\eta_{k,r}^{2}\sum_{l=1}^{p}m_{k,r}^{l}\|\mathbf{y}-\hat{\mathbf{u}}_{k,t}^{l}\|_{2}^{2}\right]$
$\displaystyle\leq\frac{2\eta^{2}\tau
n\theta}{m}|S_{i}^{\perp}|\|\mathbf{y}-\mathbf{u}_{k}\|_{2}^{2}+\frac{8\eta^{2}\theta(\theta-\xi^{2})\tau
n^{2}\kappa^{2}}{pm}|S_{i}^{\perp}|+\frac{2\eta^{2}\theta\tau(\tau-1)np}{m}|S_{i}^{\perp}|\|\mathbf{y}-\mathbf{u}_{k}\|_{2}^{2}+$
$\displaystyle\quad\quad\quad\quad\frac{2\eta^{2}\tau(\tau-1)np}{m}|S_{i}^{\perp}|\mathbb{E}_{\mathbf{M}_{k}}\left[\eta_{k,r}^{2}\sum_{l=1}^{p}m_{k,r}^{l}\|\mathbf{u}_{k}-\hat{\mathbf{u}}_{k}^{l}\|_{2}^{2}\right]$

Using $|S_{i}^{\perp}|\leq 4m\kappa^{-1}R$ with
$R\leq\frac{\xi\kappa\lambda_{0}}{144n}$ gives

$\displaystyle D_{2,k}$
$\displaystyle\leq\frac{\eta^{2}\theta\tau\lambda_{0}}{18}\left(1+(\tau-1)p\right)\|\mathbf{y}-\mathbf{u}_{k}\|_{2}^{2}+\frac{4\eta^{2}\lambda_{0}\theta(\theta-\xi^{2})\tau
n\kappa^{2}}{9p}+$
$\displaystyle\quad\quad\quad\quad\frac{\eta^{2}\tau(\tau-1)\lambda_{0}p}{18}\mathbb{E}_{\mathbf{M}_{k}}\left[\eta_{k,r}^{2}\sum_{l=1}^{p}m_{k,r}^{l}\|\mathbf{u}_{k}-\hat{\mathbf{u}}_{k}^{l}\|_{2}^{2}\right]$
$\displaystyle\leq\frac{\eta^{2}\theta\tau\lambda_{0}}{18}\left(1+(\tau-1)p\right)\|\mathbf{y}-\mathbf{u}_{k}\|_{2}^{2}+\frac{4\eta^{2}\lambda_{0}\theta(\theta-\xi^{2})\tau
n\kappa^{2}}{9p}+\frac{\eta^{2}\tau(\tau-1)\lambda_{0}pC_{1}}{18}$

∎

##  Appendix H Lemmas for Theorem 4

######  Lemma 13.

The $k$th global step produce the squared error satisfying

$\displaystyle\|\mathbf{y}-\mathbf{u}_{k+1}\|_{2}^{2}=\frac{1}{p}\sum_{l=1}^{p}\|\mathbf{y}-\hat{\mathbf{u}}_{k,\tau}^{l}\|_{2}^{2}-\frac{1}{p^{2}}\sum_{l=1}^{p}\sum_{l^{\prime}=1}^{l-1}\|\hat{\mathbf{u}}_{k,\tau}^{l}-\hat{\mathbf{u}}_{k,\tau}^{l^{\prime}}\|_{2}^{2}$

###### Proof.

We have

$\displaystyle\|\mathbf{y}-\mathbf{u}_{k+1}\|_{2}^{2}$
$\displaystyle=\left\|\mathbf{y}-\frac{1}{p}\sum_{l=1}^{p}\hat{\mathbf{u}}_{k,\tau}^{l}\right\|_{2}^{2}$
$\displaystyle=\frac{1}{p^{2}}\sum_{l=1}^{p}\sum_{l^{\prime}=1}^{p}\left\langle\mathbf{y}-\hat{\mathbf{u}}_{k,\tau}^{l},\mathbf{y}-\hat{\mathbf{u}}_{k,\tau}^{l^{\prime}}\right\rangle$
$\displaystyle=\frac{1}{p}\sum_{l=1}^{p}\|\mathbf{y}-\hat{\mathbf{u}}_{k,\tau}^{l}\|_{2}^{2}-\frac{1}{p}\sum_{l=1}^{p}\|\mathbf{y}-\hat{\mathbf{u}}_{k,\tau}^{l}\|_{2}^{2}+\frac{1}{p^{2}}\sum_{l=1}^{p}\sum_{l^{\prime}=1}^{p}\left\langle\mathbf{y}-\hat{\mathbf{u}}_{k,\tau}^{l},\mathbf{y}-\hat{\mathbf{u}}_{k,\tau}^{l^{\prime}}\right\rangle$
$\displaystyle=\frac{1}{p}\sum_{l=1}^{p}\|\mathbf{y}-\hat{\mathbf{u}}_{k,\tau}^{l}\|_{2}^{2}-$
$\displaystyle\quad\quad\quad\quad\frac{1}{2p^{2}}\left(\sum_{l=1}^{p}\sum_{l^{\prime}=1}^{p}\left(\|\mathbf{y}-\hat{\mathbf{u}}_{k,\tau}^{l}\|_{2}^{2}+\|\mathbf{y}-\hat{\mathbf{u}}_{k,\tau}^{l^{\prime}}\|_{2}^{2}\right)-\sum_{l=1}^{p}\sum_{l^{\prime}=1}^{p}\left\langle\mathbf{y}-\hat{\mathbf{u}}_{k,\tau}^{l},\mathbf{y}-\hat{\mathbf{u}}_{k,\tau}^{l^{\prime}}\right\rangle\right)$
$\displaystyle=\frac{1}{p}\sum_{l=1}^{p}\|\mathbf{y}-\hat{\mathbf{u}}_{k,\tau}^{l}\|_{2}^{2}-\frac{1}{p^{2}}\sum_{l=1}^{p}\sum_{l^{\prime}=1}^{l-1}\|\hat{\mathbf{u}}_{k,\tau}^{l}-\hat{\mathbf{u}}_{k,\tau}^{l^{\prime}}\|_{2}^{2}$

∎

######  Lemma 14.

We have

$\displaystyle\frac{1}{p}\sum_{l=1}^{p}\sum_{l^{\prime}=1}^{l-1}\|\hat{\mathbf{u}}_{k,\tau}^{l}-\hat{\mathbf{u}}_{k,\tau}^{l^{\prime}}\|_{2}^{2}=\sum_{l=1}^{p}\|\mathbf{u}_{k,\tau}-\hat{\mathbf{u}}_{k,\tau}^{l}\|_{2}^{2}$

###### Proof.

Using $\mathbf{u}_{k}=\frac{1}{p}\sum_{l=1}^{p}\hat{\mathbf{u}}_{k}^{l}$ we
have

$\displaystyle\sum_{l=1}^{p}\|\mathbf{u}_{k,\tau}-\hat{\mathbf{u}}_{k,\tau}^{l}\|_{2}^{2}$
$\displaystyle=\sum_{l=1}^{p}\left\|\frac{1}{p}\sum_{l^{\prime}=1}^{p}\hat{\mathbf{u}}_{k,\tau}^{l}-\hat{\mathbf{u}}_{k,\tau}^{l}\right\|_{2}^{2}$
$\displaystyle=\frac{1}{p^{2}}\sum_{l=1}^{p}\left\|\sum_{l^{\prime}=1}^{p}\left(\hat{\mathbf{u}}_{k,\tau}^{l^{\prime}}-\hat{\mathbf{u}}_{k,\tau}^{l}\right)\right\|_{2}^{2}$
$\displaystyle=\frac{1}{p^{2}}\sum_{l=1}^{p}\sum_{l_{1}=1}^{p}\sum_{l_{2}=1}^{p}\left\langle\hat{\mathbf{u}}_{k,\tau}^{l_{1}}-\hat{\mathbf{u}}_{k,\tau}^{l},\hat{\mathbf{u}}_{k,\tau}^{l_{2}}-\hat{\mathbf{u}}_{k,\tau}^{l}\right\rangle$
$\displaystyle=\sum_{l=1}^{p}\|\hat{\mathbf{u}}_{k,\tau}^{l}\|_{2}^{2}-\frac{1}{p}\sum_{l=1}^{p}\sum_{l^{\prime}=1}^{p}\left\langle\hat{\mathbf{u}}_{k,\tau}k^{l},\hat{\mathbf{u}}_{k}^{l^{\prime}}\right\rangle$
$\displaystyle=\frac{1}{2p}\left(\sum_{l=1}^{p}\sum_{l^{\prime}=1}^{p}\left(\|\hat{\mathbf{u}}_{k,\tau}^{l}\|_{2}^{2}+\|\hat{\mathbf{u}}_{k,\tau}^{l^{\prime}}\|_{2}^{2}\right)-\sum_{l=1}^{p}\sum_{l^{\prime}=1}^{p}2\left\langle\hat{\mathbf{u}}_{k,\tau}^{l},\hat{\mathbf{u}}_{k,\tau}^{l^{\prime}}\right\rangle\right)$
$\displaystyle=\frac{1}{p}\sum_{l=1}^{p}\sum_{l^{\prime}=1}^{l-1}\|\hat{\mathbf{u}}_{k,\tau}^{l}-\hat{\mathbf{u}}_{k,\tau}^{l^{\prime}}\|_{2}^{2}$

∎

######  Lemma 15.

Suppose the condition of lemma 25 holds and the step size satisfies
$\eta=O\left(\frac{\lambda_{0}p}{n^{2}\left(1-p^{-1}\right)^{\frac{2}{3}}\tau}\right)$,
then with probability at least $1-\delta$ it holds for all $k\in[K]$ that

$\displaystyle\iota_{k}\leq\frac{\left(1-p^{-1}\right)^{\frac{1}{3}}\eta\lambda_{0}}{2p}\sum_{l=1}^{p}\sum_{t=0}^{\tau-1}\mathbb{E}_{\mathbf{M}_{k}}\left[\left\|\mathbf{y}-\hat{\mathbf{u}}_{k,t}^{l}\right\|_{2}^{2}\right]+24\left(1-p^{-1}\right)^{\frac{2}{3}}n\kappa^{2}\eta\tau\frac{\lambda_{\max}}{\lambda_{0}}$

###### Proof.

Recall the definition of $\iota_{k}$, expanding the quadratic form gives

$\displaystyle\iota_{k}$
$\displaystyle=\frac{1}{p}\sum_{l=1}^{p}\mathbb{E}_{\mathbf{M}_{k}}\left[\left\|\mathbf{u}_{k}-\hat{\mathbf{u}}_{k}^{l}\right\|_{2}^{2}-\left\|\mathbf{u}_{k,\tau}-\hat{\mathbf{u}}_{k,\tau}^{l}\right\|_{2}^{2}\right]$
$\displaystyle=\frac{1}{p}\sum_{l=1}^{p}\mathbb{E}_{\mathbf{M}_{k}}\left[\left\|\mathbf{u}_{k}-\hat{\mathbf{u}}_{k}^{l}\right\|_{2}^{2}-\left\|\left(\mathbf{u}_{k}-\hat{\mathbf{u}}_{k}^{l}\right)+\left(\mathbf{u}_{k}-\mathbf{u}_{k+1}-\hat{\mathbf{u}}_{k}^{l}+\hat{\mathbf{u}}_{k,\tau}^{l}\right)\right\|_{2}^{2}\right]$
$\displaystyle=\frac{1}{p}\sum_{l=1}^{p}\mathbb{E}_{\mathbf{M}_{k}}\left[2\left\langle\mathbf{u}_{k}-\hat{\mathbf{u}}_{k}^{l},\mathbf{u}_{k}-\mathbf{u}_{k+1}-\hat{\mathbf{u}}_{k}^{l}+\hat{\mathbf{u}}_{k,\tau}^{l}\right\rangle+\left\|\mathbf{u}_{k}-\mathbf{u}_{k+1}-\hat{\mathbf{u}}_{k}^{l}+\hat{\mathbf{u}}_{k,\tau}^{l}\right\|_{2}^{2}\right]$
$\displaystyle=\frac{1}{p}\sum_{l=1}^{p}\mathbb{E}_{\mathbf{M}_{k}}\left[2\left\langle\mathbf{u}_{k}-\hat{\mathbf{u}}_{k}^{l},\hat{\mathbf{u}}_{k,\tau}^{l}-\hat{\mathbf{u}}_{k}^{l}\right\rangle\right]+\frac{1}{p}\sum_{l=1}^{p}\mathbb{E}_{\mathbf{M}_{k}}\left[\left\|\mathbf{u}_{k}-\mathbf{u}_{k+1}-\hat{\mathbf{u}}_{k}^{l}+\hat{\mathbf{u}}_{k,\tau}^{l}\right\|_{2}^{2}\right]$

where in the third inequality, we use the fact that

$\displaystyle\sum_{l=1}^{p}\left\langle\mathbf{u}_{k}-\hat{\mathbf{u}}_{k}^{l},\mathbf{u}_{k}-\mathbf{u}_{k+1}\right\rangle=\left\langle
p\mathbf{u}_{k}-\sum_{l=1}^{p}\hat{\mathbf{u}}_{k}^{l},\mathbf{u}_{k}-\mathbf{u}_{k+1}\right\rangle=0$

For convenience, we denote

$\displaystyle\sigma_{k,r}^{(i)}=\sigma\left(\left\langle\mathbf{W}_{k,r},\mathbf{x}_{i}\right\rangle\right);\quad\sigma_{k,\tau,r}^{l(i)}=\sigma\left(\left\langle\mathbf{w}_{k,\tau,r}^{l},\mathbf{x}_{i}\right\rangle\right)$

Noticing that
$\frac{1}{p}\sum_{l=1}^{p}\left(\hat{\mathbf{u}}_{k}^{l}-\hat{\mathbf{u}}_{k,\tau}^{l}\right)=\mathbf{u}_{k}-\mathbf{u}_{k+1}$,
we apply a trick similar to lemma 14 to get that

$\displaystyle\frac{1}{p}\sum_{l=1}^{p}\mathbb{E}_{\mathbf{M}_{k}}\left[\left\|\mathbf{u}_{k}-\mathbf{u}_{k+1}-\hat{\mathbf{u}}_{k}^{l}+\hat{\mathbf{u}}_{k,\tau}^{l}\right\|_{2}^{2}\right]$
$\displaystyle=\frac{1}{p^{2}}\sum_{l=1}^{p}\sum_{l^{\prime}=1}^{l-1}\mathbb{E}_{\mathbf{M}_{k}}\left[\left\|\hat{\mathbf{u}}_{k}^{l}-\hat{\mathbf{u}}_{k,\tau}^{l}-\hat{\mathbf{u}}_{k}^{l}-\hat{\mathbf{u}}_{k,\tau}^{l}\right\|_{2}^{2}\right]$
$\displaystyle=\frac{1}{mp^{2}}\sum_{l=1}^{p}\sum_{l^{\prime}=1}^{l-1}\sum_{i=1}^{n}\left(\sum_{r=1}^{m}a_{r}m_{k,r}^{l}\left(\sigma_{k,r}^{(i)}-\sigma_{k,\tau,r}^{l(i)}\right)-m_{k,r}^{l^{\prime}}\left(\sigma_{k,r}^{(i)}-\sigma_{k,\tau,r}{l^{\prime}(i)}\right)\right)_{2}^{2}$
$\displaystyle\leq\frac{1}{mp^{2}}\sum_{l=1}^{p}\sum_{l^{\prime}=1}^{l-1}\sum_{i=1}^{n}\sum_{r,r^{\prime}=1}^{m}m_{k,r}^{l}\left(\sigma_{k,r}^{(i)}-\sigma_{k,\tau,r}^{l(i)}\right)^{2}+m_{k,r}^{l^{\prime}}\left(\sigma_{k,r}^{(i)}-\sigma_{k,\tau,r}{l^{\prime}(i)}\right)^{2}$
$\displaystyle\leq\frac{\eta^{2}\tau
n^{2}}{mp^{2}}\sum_{l=1}^{p}\sum_{l^{\prime}=1}^{l-1}\sum_{r=1}^{m}\sum_{t=0}^{\tau-1}\left(m_{k,r}^{l}\left\|\mathbf{y}-\hat{\mathbf{u}}_{k,t}^{l}\right\|_{2}^{2}+m_{k,r}^{l^{\prime}}\left\|\mathbf{y}-\hat{\mathbf{u}}_{k,t}^{l^{\prime}}\right\|_{2}^{2}\right)$
$\displaystyle\leq\frac{\eta^{2}\tau
n^{2}(p-1)}{2mp}\sum_{l=1}^{p}\sum_{r=1}^{m}\sum_{t=0}^{\tau-1}m_{k,r}^{l}\left\|\mathbf{y}-\hat{\mathbf{u}}_{k,t}^{l}\right\|_{2}^{2}$

Notice that fixing an $l\in[p]$, we have that $m_{k,r}^{l}$’s are independent
for all $r\in[m]$. Apply Hoeffding’s inequality to get that

$\displaystyle\mathbb{P}\left(\sum_{r=1}^{m}m_{k,r}^{l}\geq
2mp^{-1}\right)\leq\exp\left(-2mp^{-2}\right)$

Apply the union bound over all $k\in[K]$ and $l\in[p]$, and apply the over-
parameterization requirement to get that, with probability at least
$1-\delta$, it holds that

$\displaystyle\frac{1}{p}\sum_{l=1}^{p}\mathbb{E}_{\mathbf{M}_{k}}\left[\left\|\mathbf{u}_{k}-\mathbf{u}_{k+1}-\hat{\mathbf{u}}_{k}^{l}+\hat{\mathbf{u}}_{k,\tau}^{l}\right\|_{2}^{2}\right]$
$\displaystyle\leq\frac{\eta^{2}\tau
n^{2}(p-1)}{p^{2}}\sum_{l=1}^{p}\sum_{t=0}^{\tau-1}\left\|\mathbf{y}-\hat{\mathbf{u}}_{k,t}^{l}\right\|_{2}^{2}$
$\displaystyle\leq\frac{\left(1-p^{-1}\right)^{\frac{1}{3}}\eta\lambda_{0}}{4p}\sum_{l=1}^{p}\sum_{t=0}^{\tau-1}\left\|\mathbf{y}-\hat{\mathbf{u}}_{k,t}^{l}\right\|_{2}^{2}$

by choosing
$\eta=O\left(\frac{\lambda_{0}p}{n^{2}\left(1-p^{-1}\right)^{\frac{2}{3}}\tau}\right)$
The first term can be bounded by

$\displaystyle\Delta_{1}$
$\displaystyle=\left\langle\mathbf{u}_{k}-\hat{\mathbf{u}}_{k}^{l},\hat{\mathbf{u}}_{k,\tau}^{l}-\hat{\mathbf{u}}_{k}^{l}\right\rangle\leq\left\|\mathbf{u}_{k}-\hat{\mathbf{u}}_{k}^{l}\right\|\left\|\hat{\mathbf{u}}_{k,\tau}^{l}-\hat{\mathbf{u}}_{k}^{l}\right\|$

We study the term
$\left\|\hat{\mathbf{u}}_{k,t+1}^{l}-\hat{\mathbf{u}}_{k,t}^{l}\right\|_{2}$.
Following analysis in the proof of hypothesis 1, we write
$\hat{\mathbf{u}}_{k,t+1}^{l}-\hat{\mathbf{u}}_{k,t}^{l}=\mathbf{I}_{1,k,t}^{l}+\mathbf{I}_{2,k,t}^{l}$.
We first study the magnitude of $\mathbf{I}_{1,k,t}^{l}$. Its $i$th entry has

$\displaystyle
I^{l(i)}_{1,k,t}=\eta\sum_{j=1}^{n}\left(\mathbf{m}_{k}^{l}\circ\mathbf{H}(k,t)-\mathbf{m}_{k}^{l}\circ\mathbf{H}(k,t)^{\perp}\right)_{ij}\left(y_{i}-\hat{u}_{k,t}^{l(i)}\right)$

As we have shown in the proof of theorem 2

$\displaystyle\left\|\mathbf{m}_{k}^{l}\circ\mathbf{H}(k,t)-\mathbf{H}^{\infty}\right\|\leq\frac{\lambda_{0}}{2}$

Therefore,
$\lambda_{\max}\left(\mathbf{m}_{k}^{l}\circ\mathbf{H}(k,t)\right)\leq\lambda_{\max}+\frac{\lambda_{0}}{2}\leq
2\lambda_{\max}$. Moreover, in the proof of hypothesis 1 we have shown that

$\displaystyle\left\|\mathbf{m}_{k}^{l}\circ\mathbf{H}(k,t)^{\perp}\right\|_{2}\leq
4n\kappa^{-1}R$

Therefore, we have

$\displaystyle\left\|\mathbf{I}_{1,k,t}^{l}\right\|_{2}$
$\displaystyle=\eta\left(\mathbf{m}_{k}^{l}\circ\mathbf{H}(k,t)-\mathbf{m}_{k}^{l}\circ\mathbf{H}(k,t)^{\perp}\right)\left(\mathbf{y}-\hat{\mathbf{u}}_{k,t}^{l}\right)$
$\displaystyle\leq\left(2\eta\lambda_{\max}+4\eta\kappa^{-1}nR\right)\left\|\mathbf{y}-\hat{\mathbf{u}}_{k,t}^{l}\right\|_{2}$

Using the bound of $\left|I^{l(i)}_{2,k,t}\right|$ in the proof of hypothesis
1, we have that

$\displaystyle\left\|\mathbf{I}_{2,k,t}^{l}\right\|_{2}\leq\left(\sum_{i=1}^{n}\left|I^{l(i)}_{2,k,t}\right|^{2}\right)^{\frac{1}{2}}4\eta\kappa^{-1}nR\left\|\mathbf{y}-\hat{\mathbf{u}}_{k,t}^{l}\right\|_{2}$

Therefore,

$\displaystyle\left\|\hat{\mathbf{u}}_{k,t+1}^{l}-\hat{\mathbf{u}}_{k,t}^{l}\right\|_{2}\leq\left\|\mathbf{I}_{1,k,t}^{l}\right\|_{2}+\left\|\mathbf{I}_{2,k,t}^{l}\right\|_{2}\leq\left(2\eta\lambda_{\max}+8\eta\kappa^{-1}nR\right)\left\|\mathbf{y}-\hat{\mathbf{u}}_{k,t}^{l}\right\|_{2}\leq
3\eta\lambda_{\max}\left\|\mathbf{y}-\hat{\mathbf{u}}_{k,t}^{l}\right\|_{2}$

by our choice of $R$. Thus, we have that

$\displaystyle\Delta_{1}\leq
3\eta\lambda_{\max}\sum_{t=0}^{\tau-1}\left\|\mathbf{y}-\hat{\mathbf{u}}_{k,t}^{l}\right\|_{2}\left\|\mathbf{u}_{k}-\hat{\mathbf{u}}_{k}^{l}\right\|_{2}\leq\frac{\left(1-p^{-1}\right)^{\frac{1}{3}}\eta\lambda_{0}}{8}\sum_{t=0}^{\tau-1}\left\|\mathbf{y}-\hat{\mathbf{u}}_{k,t}^{l}\right\|_{2}^{2}+12\frac{\eta\tau\lambda_{\max}}{\left(1-p^{-1}\right)^{\frac{1}{3}}\lambda_{0}}\left\|\mathbf{u}_{k}-\hat{\mathbf{u}}_{k}^{l}\right\|_{2}^{2}$

Therefore, by applying lemma 25 we have that

$\displaystyle\iota_{k}\leq\frac{\left(1-p^{-1}\right)^{\frac{1}{3}}\eta\lambda_{0}}{2p}\sum_{l=1}^{p}\sum_{t=0}^{\tau-1}\mathbb{E}_{\mathbf{M}_{k}}\left[\left\|\mathbf{y}-\hat{\mathbf{u}}_{k,t}^{l}\right\|_{2}^{2}\right]+24\left(1-p^{-1}\right)^{\frac{2}{3}}n\kappa^{2}\eta\tau\frac{\lambda_{\max}}{\lambda_{0}}$

∎

##  Appendix I Auxiliary Results

######  Lemma 16.

With probability at least $1-ne^{-m\kappa^{-1}R}$ we have $|S_{i}|\leq
4m\kappa^{-1}R$ for all $i\in[n]$.

###### Proof.

Note that $\mathbb{I}\\{r\in
S_{i}^{\perp}\\}=\mathbb{I}\\{\mathbb{I}\\{A_{ir}\\}\neq
0\\}=\mathbb{I}\\{A_{ir}\\}$. Therefore, we have

$\displaystyle|S_{i}^{\perp}|=\sum_{r=1}^{m}\mathbb{I}\\{r\in
S_{i}^{\perp}\\}=\mathbb{I}\\{A_{ir}\\}.$

Since
$\mathbb{E}_{\mathbf{w}_{0,r}}\left[\mathbb{I}\\{A_{ir}\\}\right]=P\left(A_{ir}\right)\leq\frac{2R}{\kappa\sqrt{2\pi}}\leq\kappa^{-1}R$,
we also have

$\displaystyle\mathbb{E}_{\mathbf{w}_{0,r}}\left[\left(\mathbb{I}\\{A_{ir}\\}-\mathbb{E}_{\mathbf{w}_{0,r}}\left[\mathbb{I}\\{A_{ir}\\}\right]\right)^{2}\right]\leq\mathbb{E}_{\mathbf{w}_{0,r}}\left[\mathbb{I}\\{A_{ir}\\}^{2}\right]=\frac{2R}{\kappa\sqrt{2\pi}}\leq\kappa^{-1}R$

Again apply Bernstein inequality over the random variable
$\mathbb{I}\\{A_{ir}\\}-\mathbb{E}_{\mathbf{w}_{0,r}}\left[\mathbb{I}\\{A_{ir}\\}\right]$
with $t=3m\kappa^{-1}R$ gives

$\displaystyle P\left(|S_{i}^{\perp}|\leq
4m\kappa^{-1}R\right)=P\left(\sum_{r=1}^{m}\mathbb{I}\\{A_{ir}\\}\geq
4m\kappa^{-1}R\right)\leq\exp\left(-m\kappa^{-1}R\right)$

∎

######  Lemma 17.

Define $\mathbf{H}^{\perp}\in\mathbb{R}^{n\times n}$ such that

$\displaystyle\mathbf{H}^{\perp}_{ij}=\frac{\xi}{m}\left\langle\mathbf{x}_{i},\mathbf{x}_{j}\right\rangle\sum_{r\in
S_{i}^{\perp}}\mathbb{I}\\{\left\langle\mathbf{w}_{r},\mathbf{x}_{i}\right\rangle\geq
0;\left\langle\mathbf{w}_{r},\mathbf{x}_{i}\right\rangle\geq 0\\}$

If $|S_{i}^{\perp}|\leq 4m\kappa^{-1}R$, then we have

$\displaystyle\|\mathbf{H}^{\perp}\|_{2}\leq 4n\xi\kappa^{-1}R$

###### Proof.

We note that

$\displaystyle\|\mathbf{H}^{\perp}\|_{2}^{2}\leq\|\mathbf{H}^{\perp}\|_{F}^{2}=\sum_{i,j=1}^{n}|\mathbf{H}_{ij}^{\perp}|^{2}$

For each $i,j$ pair we have

$\displaystyle|\mathbf{H}_{ij}^{\perp}|\leq\frac{\xi}{m}|S_{i}^{\perp}|=4\xi\kappa^{-1}R$

Thus

$\displaystyle\|\mathbf{H}^{\perp}\|_{2}\leq\left(\|\mathbf{H}^{\perp}\|_{F}^{2}\right)^{-\frac{1}{2}}\leq\left(16n^{2}\kappa^{-2}\Delta^{2}\right)^{-\frac{1}{2}}=4n\xi\kappa^{-1}R$

∎

######  Lemma 18.

For i.i.d Bernoulli masks with parameter $\xi$,
$N_{k,r}^{\perp}\sim\texttt{Bern}(\theta)$ with

$\displaystyle\theta=P(N_{k,r}^{\perp}=1)=1-(1-\xi)^{p}$

###### Proof.

We have

$\displaystyle P(N_{k,r}^{\perp}=1)$
$\displaystyle=1-P(N_{k,r}^{\perp}=0)=1-\prod_{l=1}^{p}P(m_{k,r}^{l}=0)=1-(1-\xi)^{p}$

∎

######  Lemma 19.

We have

$\displaystyle\mathbb{E}_{\mathbf{M}_{k}}\left[(\nu_{k,r,r}-\xi)^{2}\right]\leq\theta-\xi^{2}$

###### Proof.

To start, we notice that
$\nu_{k,r,r}=\eta_{k,r}\sum_{l=1}^{p}m_{k,r}^{l2}=\eta_{k,r}\sum_{l=1}^{p}m_{k,r}^{l}=N_{k,r}^{\perp}$.
Therefore
$\mathbb{E}_{\mathbf{M}_{k}}\left[\nu_{k,r,r}\right]=\mathbb{E}_{\mathbf{M}_{k}}\left[N_{k,r}^{\perp}\right]=\theta$.
Moreover, since $N_{k,r}^{\perp 2}=N_{k,r}^{\perp}$, we have
$\mathbb{E}_{\mathbf{M}_{k}}\left[\nu_{k,r,r}^{2}\right]=\theta$. Thus, using
$\theta\geq\xi$, we have

$\displaystyle\mathbb{E}_{\mathbf{M}_{k}}\left[(\nu_{k,r,r}-\xi)^{2}\right]$
$\displaystyle=\mathbb{E}_{\mathbf{M}_{k}}\left[\nu_{k,r,r}^{2}\right]-2\xi\mathbb{E}_{\mathbf{M}_{k}}\left[\nu_{k,r,r}\right]+\xi^{2}$
$\displaystyle=\theta-2\xi\theta+\xi^{2}\leq\theta-\xi^{2}$

∎

######  Lemma 20.

For i.i.d Bernoulli masks with parameter $\xi$, we have

$\displaystyle\mathbb{E}_{\mathbf{M}_{k}}\left[\nu_{k,r,r^{\prime}}\mid
N_{k,r}^{\perp}=1\right]=\begin{cases}\xi&\text{if }r\neq r^{\prime}\\\
1&\text{if }r=r^{\prime}\end{cases}$

###### Proof.

If $r=r^{\prime}$, we have

$\displaystyle\mathbb{E}_{\mathbf{M}_{k}}\left[\nu_{k,r,r^{\prime}}\mid
N_{k,r}^{\perp}=1\right]$
$\displaystyle=\mathbb{E}_{\mathbf{M}_{k}}\left[\eta_{k,r}\sum_{l=1}^{p}m_{k,r}^{l}\mid
N_{k,r}^{\perp}=1\right]=\mathbb{E}_{\mathbf{M}_{k}}\left[\frac{X_{k,r}}{N_{k,r}}\mid
N_{k,r}^{\perp}=1\right]$
$\displaystyle=\mathbb{E}_{\mathbf{M}_{k}}\left[N_{k,r}^{\perp}\mid
N_{k,r}^{\perp}=1\right]=1$

If $r^{\prime}\neq r$, then we have that $m_{k,r^{\prime}}^{l}$ is independent
from $m_{k,r}^{l}$ and $N_{k,r}$. Therefore,

$\displaystyle\mathbb{E}_{\mathbf{M}_{k}}\left[\nu_{k,r,r^{\prime}}\mid
N_{k,r}^{\perp}=1\right]$
$\displaystyle=\mathbb{E}_{\mathbf{M}_{k}}\left[\eta_{k,r}\sum_{l=1}^{p}m_{k,r}^{l}\mid
N_{k,r}^{\perp}=1\right]\mathbb{E}_{\mathbf{M}_{k}}\left[m_{k,r^{\prime}}^{l}\right]$
$\displaystyle=\xi\mathbb{E}_{\mathbf{M}_{k}}\left[\frac{X_{k,r}}{N_{k,r}}\mid
N_{k,r}^{\perp}=1\right]=\xi$

∎

######  Lemma 21.

The variance follows

$\displaystyle\text{Var}_{\mathbf{M}_{k}}\left(\nu_{k,r,r^{\prime}}\mid
N_{k,r}^{\perp}=1\right)=\begin{cases}\frac{\theta-\xi^{2}}{p}&\text{if }r\neq
r^{\prime}\\\ 0&\text{if }r=r^{\prime}\end{cases}$

###### Proof.

For $r\neq r^{\prime}$, the expectation of $\nu_{k,r,r^{\prime}}^{2}$ given
$N_{k,r}^{\perp}=1$ is

$\displaystyle\mathbb{E}_{\mathbf{M}_{k}}\left[\nu_{k,r,r^{\prime}}^{2}\mid
N_{k,r}^{\perp}=1\right]$
$\displaystyle=\mathbb{E}_{\mathbf{M}_{k}}\left[\frac{\sum_{l=1}^{p}\sum_{l^{\prime}=1}^{p}m_{k,r}^{l}m_{k,r}^{l^{\prime}}m_{k,r^{\prime}}^{l}m_{k,r^{\prime}}^{l^{\prime}}}{X_{k,r}}\mid
N_{k,r}^{\perp}=1\right]$ $\displaystyle=\sum_{l=1}^{p}\sum_{l^{\prime}\neq
l}\mathbb{E}_{\mathbf{M}_{k}}[m_{k,r^{\prime}}^{l}]\mathbb{E}_{\mathbf{M}_{k}}[m_{k,r^{\prime}}^{l^{\prime}}]\mathbb{E}_{\mathbf{M}_{k}}\left[\frac{m_{k,r}^{l}}{X_{k,r}}\mid
N_{k,r}^{\perp}=1\right]\mathbb{E}_{\mathbf{M}_{k}}\left[\frac{m_{k,r}^{l^{\prime}}}{X_{k,r}}\mid
N_{k,r}^{\perp}=1\right]+$
$\displaystyle\quad\quad\quad\quad\sum_{l=1}^{p}\mathbb{E}_{\mathbf{M}_{k}}[m_{k,r^{\prime}}^{l}]\mathbb{E}_{\mathbf{M}_{k}}\left[\frac{m_{k,r}^{l}}{X_{k,r}^{2}}\mid
N_{k,r}^{\perp}=1\right]$
$\displaystyle=\xi^{2}\sum_{l=1}^{p}\sum_{l^{\prime}\neq
l}\mathbb{E}_{\mathbf{M}_{k}}\left[\frac{m_{k,r}^{l}}{X_{k,r}}\mid
N_{k,r}^{\perp}=1\right]\mathbb{E}_{\mathbf{M}_{k}}\left[\frac{m_{k,r}^{l^{\prime}}}{X_{k,r}}\mid
N_{k,r}^{\perp}=1\right]+$
$\displaystyle\quad\quad\quad\quad\xi\sum_{l=1}^{p}\mathbb{E}_{\mathbf{M}_{k}}\left[\frac{m_{k,r}^{l}}{X_{k,r}^{2}}\mid
N_{k,r}^{\perp}=1\right]$
$\displaystyle=\xi^{2}+\xi\mathbb{E}_{\mathbf{M}_{k}}\left[\frac{1}{X_{k,r}}\mid
N_{k,r}^{\perp}=1\right]-\xi^{2}\sum_{l=1}^{p}\mathbb{E}_{\mathbf{M}_{k}}\left[\frac{m_{k,r}^{l}}{X_{k,r}}\mid
N_{k,r}^{\perp}=1\right]^{2}$

Therefore, the variance of $\nu_{k,r,r^{\prime}}$ given $N_{k,r}^{\perp}=1$
has the form

$\displaystyle\text{Var}\left(\nu_{k,r,r^{\prime}}\mid
gN_{k,r}^{\perp}=1\right)$
$\displaystyle=\mathbb{E}_{\mathbf{M}_{k}}\left[\nu_{k,r,r^{\prime}}^{2}\mid
N_{k,r}^{\perp}=1\right]-\mathbb{E}_{\mathbf{M}_{k}}\left[\nu_{k,r,r^{\prime}}\mid
N_{k,r}^{\perp}=1\right]^{2}$
$\displaystyle=\xi\mathbb{E}_{\mathbf{M}_{k}}\left[\frac{1}{X_{k,r}}\mid
N_{k,r}^{\perp}=1\right]-\xi^{2}\sum_{l=1}^{p}\mathbb{E}_{\mathbf{M}_{k}}\left[\frac{m_{k,r}^{l}}{X_{k,r}}\mid
N_{k,r}^{\perp}=1\right]^{2}$

Let $X(p)=\sum_{l=1}^{p}m_{\cdot}^{l}\sim\mathcal{B}(p,\xi)$, then we have

$\displaystyle\mathbb{E}_{\mathbf{M}_{k}}\left[\frac{1}{X_{k,r}}\mid
N_{k,r}^{\perp}=1\right]$
$\displaystyle=\mathbb{E}_{\mathbf{M}_{k}}\left[\frac{1}{1+X(p-1)}\right]$
$\displaystyle\mathbb{E}_{\mathbf{M}_{k}}\left[\frac{m_{k,r}^{l}}{X_{r}}\mid
N_{k,r}^{\perp}=1\right]$ $\displaystyle=P(m_{k,r}^{l}=1\mid
N_{k,r}^{\perp}=1)\mathbb{E}_{\mathbf{M}_{k}}\left[\frac{1}{1+X(p-1)}\right]=\frac{\xi}{\theta}\mathbb{E}_{\mathbf{M}_{k}}\left[\frac{1}{1+X(p-1)}\right]$

Moreover, using reciprocal moments we have

$\displaystyle\mathbb{E}_{\mathbf{M}_{k}}\left[\frac{1}{1+X(p-1)}\right]=\frac{\theta}{p\xi}$

Therefore

$\displaystyle\text{Var}_{\mathbf{M}_{k}}\left(\nu_{k,r,r^{\prime}}\mid
N_{k,r}^{\perp}=1\right)$
$\displaystyle=\xi\mathbb{E}_{\mathbf{M}_{k}}\left[\frac{1}{1+X(p-1)}\right]-\frac{\xi^{4}}{\theta^{2}}p\mathbb{E}_{\mathbf{M}_{k}}\left[\frac{1}{1+X(p-1)}\right]^{2}$
$\displaystyle=\frac{\theta-\xi^{2}}{p}$

If $r=r^{\prime}$, the variance is

$\displaystyle\text{Var}_{\mathbf{M}_{k}}\left(\nu_{r,r}\mid
g_{r}=1\right)=\text{Var}_{\mathbf{M}_{k}}\left(g_{r}\mid g_{r}=1\right)=0$

∎

######  Lemma 22.

Suppose $\kappa\leq 1,R\leq\kappa\sqrt{\frac{d}{32}}$. With probability at
least $1-e^{md/32}$ we have that

$\displaystyle\|W_{0}\|_{F}\leq\kappa\sqrt{2md}-\sqrt{m}R$

###### Proof.

For all $r\in[m],d_{1}\in[d]$, we have
$\mathbb{E}_{\mathbf{M}_{k}}\left[w_{rd_{1}}^{2}\right]=\kappa^{2}$. Moreover,
each $w_{rd_{1}}^{2}$ is a $(2\kappa^{2},2\kappa^{2})$-sub-exponential random
variable

$\displaystyle\mathbb{E}\left[e^{t(w_{rd_{1}}^{2}-\kappa^{2})}\right]$
$\displaystyle=\frac{1}{\kappa\sqrt{2\pi}}\int_{-\infty}^{\infty}e^{t(w_{rd_{1}}^{2}-\kappa^{2}}e^{-\frac{w_{rd_{1}}^{2}}{2\kappa^{2}}}dw_{rd_{1}}$
$\displaystyle=\frac{1}{\kappa\sqrt{2\pi}}\int_{-\infty}^{\infty}e^{-(\frac{1}{2\kappa^{2}}-t)w_{rd_{1}}^{2}-t\kappa^{2}}dw_{rd_{1}}$
$\displaystyle=\frac{1}{\kappa\sqrt{2\pi}}\cdot\sqrt{\frac{\pi}{(2\kappa)^{-1}-t}}\cdot
e^{-t\kappa^{2}}$
$\displaystyle=\frac{e^{-t\kappa^{2}}}{\sqrt{1-2t\kappa^{2}}}\leq
e^{2t^{2}\kappa^{4}}$

with $t\leq\frac{1}{2\kappa^{2}}$. Thus, using independence between entries of
$\mathbf{W}_{0}$ gives

$\displaystyle\mathbb{E}\left[e^{t(\|\mathbf{W}_{0}\|_{F}^{2}-md\kappa^{2})}\right]\leq\prod_{r=1}^{m}\prod_{d_{1}=1}^{d}\mathbb{E}\left[e^{t(w_{rd_{1}}^{2}-\kappa^{2})}\right]\leq
e^{2mdt^{2}\kappa^{4}}$

Invoking the tail bound of sub-exponential random variable gives

$\displaystyle P\left(\|\mathbf{W}_{0}\|_{F}^{2}\geq
md\kappa^{2}+t\right)\leq\begin{cases}e^{-\frac{t^{2}}{8md\kappa^{4}}}&\text{
if }0\leq t\leq 2md\kappa^{2}\\\ e^{-\frac{t^{2}}{4\kappa^{2}}}&\text{ if
}t>2md\kappa^{2}\end{cases}$

Let $t=md\kappa^{2}-2m\kappa R\sqrt{2d}+mR^{2}$. Then

$\displaystyle\|\mathbf{W}_{0}\|_{F}^{2}\leq 2md\kappa^{2}+mR^{2}-2m\kappa
R\sqrt{2d}=(\kappa\sqrt{2md}-\sqrt{m}R)^{2}$

with probability at least $1-e^{-\frac{t^{2}}{8md\kappa^{4}}}$. Using
$R\leq\kappa\sqrt{\frac{d}{32}}$ we have $t\geq\frac{1}{2}md\kappa^{2}$. Thus
with probability at least $1-e^{-\frac{md}{32}}$ we have

$\displaystyle\|\mathbf{W}_{0}\|_{F}\leq\kappa\sqrt{2md}-\sqrt{m}R$

∎

######  Lemma 23.

Assume $\kappa\leq 1$ and $R\leq\frac{\kappa}{\sqrt{2}}$. With probability at
least $1-ne^{-\frac{m}{32}}$ over initialization, it holds for all $i\in[n]$
that

$\displaystyle\sum_{r=1}^{m}\left\langle\mathbf{w}_{0,r},\mathbf{x}_{i}\right\rangle^{2}\leq
2m\kappa^{2}-mR^{2}$
$\displaystyle\sum_{i=1}^{n}\sum_{r=1}^{m}\left\langle\mathbf{w}_{0,r},\mathbf{x}_{i}\right\rangle^{2}\leq
2mn\kappa^{2}-mnR^{2}$

###### Proof.

It suffice to prove the first inequality, and the second follows by summing
over $n$. To begin, we show that each
$\left\langle\mathbf{w}_{0},\mathbf{x}_{i}\right\rangle$ are Gaussian with
zero mean and variance $\kappa^{2}$. Using independence between entries of
$\mathbf{w}_{0,r}$, we have

$\displaystyle\mathbb{E}\left[e^{-t\left\langle\mathbf{w}_{0,r},\mathbf{x}_{i}\right\rangle}\right]$
$\displaystyle=\mathbb{E}\left[\prod_{j=1}^{d}e^{-tw_{0,r,j}x_{i,j}}\right]=\prod_{j=1}^{d}\mathbb{E}\left[e^{-tw_{0,r,j}x_{i,j}}\right]$
$\displaystyle=\prod_{j=1}^{d}e^{-t^{2}x_{i,j}^{2}\kappa^{2}}=e^{-t^{2}\kappa^{2}\sum_{j=1}^{d}x_{i,j}^{2}}=e^{-t^{2}\kappa^{2}}$

where the last equality follows from our assumption that
$\|\mathbf{x}_{i}\|_{2}=1$. Next, we treat each
$\omega_{r,i}=\left\langle\mathbf{w}_{0,r},\mathbf{x}_{i}\right\rangle^{2}$ as
a random variable. First, we compute the mean of $\omega_{r,i}$

$\displaystyle\mathbb{E}[\omega_{r,i}]$
$\displaystyle=\mathbb{E}_{\mathbf{W}_{0}}\left[\left\langle\mathbf{w}_{0,r},\mathbf{x}_{i}\right\rangle^{2}\right]=\mathbb{E}_{\mathbf{W}_{0}}\left[\left(\sum_{d_{1}=1}^{d}w_{0,r,d}x_{i,d}\right)^{2}\right]$
$\displaystyle=\sum_{d_{1}=1}^{d}\mathbb{E}_{\mathbf{W}_{0}}\left[w_{0,r,d}^{2}\right]x_{i,d}^{2}=\kappa^{2}\sum_{d_{1}=1}^{d}x_{i,d}^{2}=\kappa^{2}$

Then, we show that each $\omega_{r,i}$ is sub-exponential with parameter
$(2\kappa^{2},2\kappa^{2})$.

$\displaystyle\mathbb{E}\left[e^{t(\omega_{r,i}-\kappa^{2})}\right]$
$\displaystyle=\frac{1}{\kappa\sqrt{2\pi}}\int_{-\infty}^{\infty}e^{t(\omega_{r,i}-\kappa^{2})}e^{-\frac{\omega_{r,i}}{2\kappa^{2}}}d\sqrt{\omega_{r,i}}$
$\displaystyle=\frac{1}{\kappa\sqrt{2\pi}}\int_{-\infty}^{\infty}e^{-(\frac{1}{2\kappa^{2}}-t)(\sqrt{\omega_{r,i}})^{2}-t\kappa^{2}}d\sqrt{\omega_{r,i}}$
$\displaystyle=\frac{1}{\kappa\sqrt{2\pi}}\cdot\sqrt{\frac{\pi}{(2\kappa^{2})^{-1}-t}}\cdot
e^{-t\kappa^{2}}$ $\displaystyle=\frac{e^{-t\kappa^{2}}}{1-2t\kappa^{2}}\leq
e^{2t\kappa^{4}}$

for $t\leq\frac{1}{2\kappa^{2}}$. Since each $\mathbf{w}_{0,r}$ is
independent, we have that each $\omega_{r,i}$ is independent for a fixed $i$.
Thus

$\displaystyle\mathbb{E}\left[e^{t\sum_{r=1}^{m}(\omega_{r,i}-\kappa^{2})}\right]$
$\displaystyle=\prod_{r=1}^{m}\mathbb{E}\left[e^{t(\omega_{r,i}-\kappa^{2})}\right]\leq
e^{2mt\kappa^{4}}$

Thus we have

$\displaystyle P\left(\sum_{r=1}^{m}\omega_{r,i}\geq
m\kappa^{2}+t\right)\leq\begin{cases}e^{-\frac{t^{2}}{8m\kappa^{4}}}&\text{ if
}0\leq t\leq 2m\kappa^{2}\\\ e^{-\frac{t^{2}}{2\kappa^{2}}}&\text{ if }t\geq
2m\kappa^{2}\end{cases}$

We choose $t=m\kappa^{2}-mR^{2}$. Since $R\leq\frac{\kappa}{\sqrt{2}}$, we
have that $\frac{m\kappa^{2}}{2}\leq t\leq m\kappa^{2}$. Thus

$\displaystyle P\left(\sum_{r=1}^{m}\omega_{r,i}\geq
2m\kappa^{2}-mR^{2}\right)\leq e^{-\frac{m}{8}}$

Apply a union bound over all $i\in[n]$ gives that with probability at least
$1-ne^{-\frac{m}{32}}$, it holds for all $i\in[n]$ that

$\displaystyle\sum_{r=1}^{m}\omega_{r,i}\leq 2m\kappa^{2}-mR^{2}$

∎

######  Lemma 24.

If for some $R>0$ and all $r\in[m]$ the initialization satisfies

$\displaystyle\sum_{r=1}^{m}\left\langle\mathbf{w}_{0,r},\mathbf{x}_{i}\right\rangle^{2}\leq
2mn\kappa^{2}-mnR^{2}$

and for all $r\in[m]$, it holds that
$\|\mathbf{w}_{k,r}-\mathbf{w}_{0,r}\|_{2}\leq R$. Then with
$C_{1}=\frac{4\theta^{2}(1-\xi)n\kappa^{2}}{p}$, we have

$\displaystyle\mathbb{E}_{\mathbf{M}_{k}}\left[\eta_{k,r}^{2}\sum_{l=1}^{p}m_{k,r}^{l}\|\mathbf{u}_{k}-\hat{\mathbf{u}}_{k}^{l}\|_{2}^{2}\right]\leq
C_{1};\quad\mathbb{E}_{\mathbf{M}_{k}}\left[\eta_{k,r}\sum_{l=1}^{p}m_{k,r}^{l}\|\mathbf{u}_{k}-\hat{\mathbf{u}}_{k}^{l}\|_{2}\right]\leq\sqrt{pC_{1}}$

###### Proof.

Using reciprocal moments, we have

$\displaystyle\mathbb{E}_{\mathbf{M}_{k}}\left[\eta_{k,r}\right]$
$\displaystyle=P\left(N_{k,r}^{\perp}=1\right)\mathbb{E}_{\mathbf{M}_{k}}\left[\eta_{k,r}\mid
N_{k,r}^{\perp}=1\right]=\frac{\theta^{2}}{p\xi}$

To start, we compute that for $r\neq r^{\prime}$. Using the independence of
$m_{k,r}^{l}$ and $m_{k,r^{\prime}}^{l}$, we have

$\displaystyle\mathbb{E}_{\mathbf{M}_{k}}\left[\eta_{k,r}^{2}\sum_{l=1}^{p}m_{k,r}^{l}(\xi-
m_{k,r^{\prime}}^{l})^{2}\right]$
$\displaystyle=\sum_{l=1}^{p}\mathbb{E}_{\mathbf{M}_{k}}\left[\eta_{k,r}^{2}m_{k,r}(\xi-
m_{k,r^{\prime}})^{2}\right]$
$\displaystyle=\sum_{l=1}^{p}\mathbb{E}_{\mathbf{M}_{k}}\left[\eta_{k,r}^{2}m_{k,r}^{l}\right]\mathbb{E}_{\mathbf{M}_{k}}\left[(\xi-
m_{k,r^{\prime}}^{l})^{2}\right]$
$\displaystyle=\xi(1-\xi)\mathbb{E}_{\mathbf{M}_{k}}\left[\eta_{k,r}^{2}\sum_{l=1}^{p}m_{k,r}^{l}\right]$
$\displaystyle=\xi(1-\xi)\mathbb{E}_{\mathbf{M}_{k}}\left[\eta_{k,r}\right]$

For $r=r^{\prime}$, we use the idempotent

$\displaystyle\mathbb{E}_{\mathbf{M}_{k}}\left[\eta_{k,r}^{2}\sum_{l=1}^{p}m_{k,r}^{l}(\xi-
m_{k,r}^{l})^{2}\right]$
$\displaystyle=(1-\xi)^{2}\mathbb{E}_{\mathbf{M}_{k}}\left[\eta_{k,r}^{2}\sum_{l=1}^{p}m_{k,r}^{l}\right]$
$\displaystyle=(1-\xi)^{2}\mathbb{E}_{\mathbf{M}_{k}}\left[\eta_{k,r}\right]$

Therefore

$\displaystyle\mathbb{E}_{\mathbf{M}_{k}}\left[\eta_{k,r}^{2}\sum_{l=1}^{p}m_{k,r}^{l}\left(u_{k}^{(i)}-\hat{u}_{k}^{l(i)}\right)^{2}\right]$
$\displaystyle\leq\frac{1}{m}\mathbb{E}_{\mathbf{M}_{k}}\left[\eta_{k,r}^{2}\sum_{l=1}^{p}m_{k,r}^{l}\left(\sum_{r^{\prime}=1}^{m}a_{r}(\xi-
m_{k,r^{\prime}}^{l})\sigma(\left\langle\mathbf{w}_{k,r^{\prime}},\mathbf{x}_{i}\right\rangle)\right)^{2}\right]$
$\displaystyle\leq\frac{1}{m}\mathbb{E}_{\mathbf{M}_{k}}\left[\eta_{k,r}^{2}\sum_{l=1}^{p}m_{k,r}^{l}\sum_{r^{\prime}=1}^{m}(\xi-
m_{k,r^{\prime}}^{l})^{2}\sigma(\left\langle\mathbf{w}_{k,r^{\prime}},\mathbf{x}_{i}\right\rangle)^{2}\right]$
$\displaystyle\leq\frac{1}{m}\sum_{r^{\prime}=1}^{m}\mathbb{E}_{\mathbf{M}_{k}}\left[\eta_{k,r}^{2}\sum_{l=1}^{p}m_{k,r}^{l}(\xi-
m_{k,r^{\prime}}^{l})^{2}\right]\sigma(\left\langle\mathbf{w}_{k,r^{\prime}},\mathbf{x}_{i}\right\rangle)^{2}$
$\displaystyle\leq\frac{\xi(1-\xi)}{m}\mathbb{E}_{\mathbf{M}_{k}}\left[\eta_{k,r}\right]\sum_{r^{\prime}=1}^{m}\sigma(\left\langle\mathbf{w}_{k,r^{\prime}},\mathbf{x}_{i}\right\rangle)^{2}+$
$\displaystyle\quad\quad\quad\quad\frac{(1-\xi)(1-2\xi)}{m}\mathbb{E}_{\mathbf{M}_{k}}\left[\eta_{k,r}\right]\sigma(\left\langle\mathbf{w}_{k,r},\mathbf{x}_{i}\right\rangle)^{2}$
$\displaystyle\leq\frac{\theta^{2}(1-\xi)}{mp}\sum_{r^{\prime}=1}^{m}\left\langle\mathbf{w}_{k,r^{\prime}},\mathbf{x}_{i}\right\rangle^{2}+\frac{(1-\xi)^{2}\theta^{2}}{mp\xi}\left\langle\mathbf{w}_{k,r},\mathbf{x}_{i}\right\rangle^{2}$
$\displaystyle\leq\frac{2\theta^{2}(1-\xi)\kappa^{2}}{p}+\frac{2\theta^{2}(1-\xi)^{2}\kappa^{2}}{mp\xi}$
$\displaystyle\leq\frac{4\theta^{2}(1-\xi)\kappa^{2}}{p}$

where in the last inequality we use $m\geq\xi^{-1}$. Thus, we have

$\displaystyle\mathbb{E}_{\mathbf{M}_{k}}\left[\eta_{k,r}^{2}\sum_{l=1}^{p}m_{k,r}^{l}\|\mathbf{u}_{k}-\hat{\mathbf{u}}_{k}^{l}\|_{2}^{2}\right]$
$\displaystyle=\sum_{i=1}^{n}\mathbb{E}_{\mathbf{M}_{k}}\left[\eta_{k,r}^{2}\sum_{l=1}^{p}m_{k,r}^{l}\left(u_{k}^{(i)}-\hat{u}_{k}^{l(i)}\right)^{2}\right]\leq
C_{1}$

Also, we have

$\displaystyle\mathbb{E}_{\mathbf{M}_{k}}\left[\eta_{k,r}\sum_{l=1}^{p}m_{k,r}^{l}\|\mathbf{u}_{k}-\hat{\mathbf{u}}_{k}^{l}\|_{2}\right]$
$\displaystyle\leq\mathbb{E}_{\mathbf{M}_{k}}\left[\left(\eta_{k,r}\sum_{l=1}^{p}m_{k,r}^{l}\|\mathbf{u}_{k}-\hat{\mathbf{u}}_{k}^{l}\|_{2}\right)^{2}\right]^{\frac{1}{2}}$
$\displaystyle\leq\sqrt{p}\mathbb{E}_{\mathbf{M}_{k}}\left[\eta_{k,r}^{2}\sum_{l=1}^{p}m_{k,r}^{l}\|\mathbf{u}_{k}-\hat{\mathbf{u}}_{k}^{l}\|_{2}^{2}\right]^{\frac{1}{2}}$

Plugging in the previous bound gives the desired result. ∎

######  Lemma 25.

If for some $R>0$ and all $r\in[m]$ the initialization satisfies

$\displaystyle\sum_{r=1}^{m}\left\langle\mathbf{w}_{0,r},\mathbf{x}_{i}\right\rangle^{2}\leq
2mn\kappa^{2}-mnR^{2}$

and for all $r\in[m]$, it holds that
$\|\mathbf{w}_{k,r}-\mathbf{w}_{0,r}\|_{2}\leq R$. Then we have

$\displaystyle\mathbb{E}_{\mathbf{M}_{k}}\left[\|\mathbf{u}_{k}-\hat{\mathbf{u}}_{k}^{l}\|_{2}^{2}\right]\leq
4\xi(1-\xi)n\kappa^{2}$

###### Proof.

To start, we have

$\displaystyle\mathbb{E}_{\mathbf{M}_{k}}\left[\left(u_{k}^{(i)}-\hat{u}_{k}^{l(i)}\right)^{2}\right]$
$\displaystyle=\frac{1}{m}\mathbb{E}_{\mathbf{M}_{k}}\left[\left(\sum_{r=1}^{m}a_{r}(\xi-
m_{k,r}^{l})\sigma(\left\langle\mathbf{w}_{k,r},\mathbf{x}_{i}\right\rangle)\right)^{2}\right]$
$\displaystyle\leq\frac{1}{m}\sum_{r=1}^{m}\mathbb{E}_{\mathbf{M}_{k}}\left[(\xi-
m_{k,r}^{l})^{2}\right]\sigma(\left\langle\mathbf{w}_{k,r},\mathbf{x}_{i}\right\rangle)^{2}$
$\displaystyle\leq\frac{\xi(1-\xi)}{m}\sum_{r=1}^{m}\left\langle\mathbf{w}_{k,r},\mathbf{x}_{i}\right\rangle^{2}$
$\displaystyle\leq\frac{2\xi(1-\xi)}{m}\sum_{r=1}^{m}\left\langle\mathbf{w}_{0,r},\mathbf{x}_{i}\right\rangle^{2}+2\xi(1-\xi)R^{2}$
$\displaystyle\leq 4\xi(1-\xi)\kappa^{2}$

Therefore,

$\displaystyle\mathbb{E}_{\mathbf{M}_{k}}\left[\|\mathbf{u}_{k}-\hat{\mathbf{u}}_{k}^{l}\|_{2}^{2}\right]$
$\displaystyle=\sum_{i=1}^{n}\mathbb{E}_{\mathbf{M}_{k}}\left[\left(u_{k}^{(i)}-\hat{u}_{k}^{l(i)}\right)^{2}\right]\leq
4\xi(1-\xi)n\kappa^{2}$

∎

######  Lemma 26.

Assume that for all $i\in[n]$, $y_{i}$ satisfies $|y_{i}|\leq C-1$ for some
$C\geq 1$. Then, we have

$\displaystyle\mathbb{E}_{\mathbf{W}_{0},\mathbf{a}}\left[\|\mathbf{y}-\mathbf{u}_{0}\|_{2}^{2}\right]\leq
C^{2}n$

###### Proof.

It is easy to see that
$\mathbb{E}_{\mathbf{W}_{0},\mathbf{a}}\left[u_{0}^{(i)}\right]=0$. Now, note
that

$\displaystyle\mathbb{E}_{\mathbf{W}_{0},\mathbf{a}}\left[\left(u_{0}^{(i)}\right)^{2}\right]$
$\displaystyle=\frac{\xi^{2}}{m}\mathbb{E}_{\mathbf{W}_{0},\mathbf{a}}\left[\left(\sum_{r=1}^{m}a_{r}\sigma(\left\langle\mathbf{w}_{0,r},\mathbf{x}_{i}\right\rangle\right)^{2}\right]$
$\displaystyle=\frac{\xi^{2}}{m}\sum_{r=1}^{m}\mathbb{E}_{\mathbf{W}_{0}}\left[\left\langle\mathbf{w}_{0,r},\mathbf{x}_{i}\right\rangle^{2}\right]$
$\displaystyle=\frac{\xi^{2}}{m}\sum_{r=1}^{m}\mathbb{E}_{\mathbf{W}_{0}}\left[\left(\sum_{d^{\prime}=1}^{d}w_{0,r,d^{\prime}}x_{i,d^{\prime}}\right)^{2}\right]$
$\displaystyle=\frac{\xi^{2}}{m}\sum_{r=1}^{m}\sum_{d^{\prime}=1}^{d}\mathbb{E}_{\mathbf{W}_{0}}\left[w_{0,r,d^{\prime}}^{2}x_{i,d^{\prime}}^{2}\right]$
$\displaystyle=\frac{\xi^{2}}{m}\sum_{r=1}^{m}\sum_{d^{\prime}=1}^{d}x_{i,d^{\prime}}^{2}$
$\displaystyle=\xi^{2}$

Therefore,

$\displaystyle\mathbb{E}_{\mathbf{W}_{0},\mathbf{a}}\left[\left(y_{i}-u_{0}^{(i)}\right)^{2}\right]=y_{i}^{2}-2y_{i}\mathbb{E}_{\mathbf{W}_{0},\mathbf{a}}\left[u_{0}^{(i)}\right]+\mathbb{E}_{\mathbf{W}_{0},\mathbf{a}}\left[\left(u_{0}^{(i)}\right)^{2}\right]=y_{i}^{2}+\xi^{2}$

Thus,

$\displaystyle\mathbb{E}_{\mathbf{W}_{0},\mathbf{a}}\left[\|\mathbf{y}-\mathbf{u}_{0}\|_{2}^{2}\right]=\sum_{i=1}^{n}\mathbb{E}_{\mathbf{W}_{0},\mathbf{a}}\left[\left(y_{i}-u_{0}^{(i)}\right)^{2}\right]=\sum_{i=1}^{n}y_{i}^{2}+\xi^{2}n\leq
C^{2}n$

∎