Using the fact that $\|\bm{v}_{s}^{(T)}\|_{2}\leq 1$ in (126) finally yields:

$\displaystyle\mathscr{L}(f_{\bm{W}^{T}})$ $\displaystyle\leq
2(1-\mu)\exp\left(-\tilde{\Omega}\left(\frac{\alpha^{6}}{\beta^{6}\sigma^{6}}\right)\right)+2\mu\exp\left(-\tilde{\Omega}\left(\frac{1}{\sigma^{6}}\right)\right).$
(127)

Since $\exp(-\alpha^{6}/(\beta^{6}\sigma^{6}))\leq\mu/\mathrm{poly}(d)$ and
$\exp(-\tilde{\Omega}(1/\sigma^{6}))\leq 1/\mathrm{poly(d)}$ , we obtain the
desired result.

∎

###  G.4 Proof of the GD+M induction hypotheses

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

We prove the induction hypotheses for the signal $c_{r}^{(t)}.$

##### Proof of $c_{r}^{(t+1)}\geq-\tilde{O}(\sigma_{0})$.

We know that with high probability, $c_{r}^{(0)}\geq-\tilde{O}(\sigma_{0})$.
By Lemma F.1, $c_{r}^{(t)}$ is a non-decreasing sequence and therefore, we
always have $c_{r}^{(t)}\geq-\tilde{O}(\sigma_{0}).$

##### Proof of $c_{r}^{(t+1)}\leq\tilde{O}(1/\beta)$.

Assume that D.4 is true for $t\in[\mathcal{T}_{1},T).$ Now, let’s prove this
induction hypothesis for time $t+1.$ For $\tau\in[t]$, we remind that (3)
update rule is

$\displaystyle c_{r}^{(\tau+1)}$
$\displaystyle=c_{r}^{(\tau)}-\eta\mathcal{G}_{r}^{(\tau+1)}.$ (128)

We sum up (128) for $\tau=\mathcal{T}_{1},\dots,t$ and obtain:

$\displaystyle c_{r}^{(t+1)}$
$\displaystyle=c_{r}^{(\mathcal{T}_{1})}-\eta\sum_{\tau=\mathcal{T}_{1}}^{t}\mathcal{G}_{r}^{(\tau+1)}.$
(129)

We apply the triangle inequality in (129) and obtain:

$\displaystyle|c_{r}^{(t+1)}|$
$\displaystyle\leq|c_{r}^{(\mathcal{T}_{1})}|+\eta\sum_{\tau=\mathcal{T}_{1}}^{t}|\mathcal{G}_{r}^{(\tau+1)}|.$
(130)

We now use D.5 to bound $|c_{r}^{(\mathcal{T}_{1})}|$ in (130):

$\displaystyle|c_{r}^{(t+1)}|$
$\displaystyle\leq\tilde{O}(1/\beta)+\eta\sum_{\tau=\mathcal{T}_{1}}^{t}|\mathcal{G}_{r}^{(\tau+1)}|.$
(131)

We now plug the bound on
$\sum_{\tau=\mathcal{T}_{1}}^{t}|\mathcal{G}_{r}^{(\tau+1)}|$ given by Lemma
J.3. We have:

$\displaystyle|c_{r}^{(t+1)}|$
$\displaystyle\leq\tilde{O}(1/\beta)+\tilde{O}(\eta\alpha\mathcal{T}_{0})+\tilde{O}(\eta\hat{\mu}\beta\mathcal{T}_{1})+\tilde{O}(1)\leq\tilde{O}(1/\beta),$
(132)

where we used
$\tilde{O}(\eta\alpha\mathcal{T}_{0})+\tilde{O}(\eta\hat{\mu}\beta\mathcal{T}_{1})+\tilde{O}(1)\leq
1/\beta.$ This proves the induction hypothesis for $t+1.$ ∎

##  Appendix H Extension to $\lambda>0$

Now we discuss how to extend the result to $\lambda>0$. In our result, since
$\lambda=\frac{1}{N\mathrm{poly}(d)}$, we know that before
$T=\tilde{\Theta}\left(\frac{1}{\eta\lambda}\right)$ iterations, the weight
decay would not affect the learning process and we can show everything
similarly.

After iteration $T$, by Lemma I.8 and Lemma J.9, we know that for GD:

$\nu^{(t)}\leq\tilde{O}\left(\lambda\right)$

and for GD + M:

$\nu^{(t)}\leq\tilde{O}\left(\lambda/(\beta^{2})\right)$

For GD, we just need to maintain that $c^{(t)}=\tilde{O}(1/\alpha)$ and
$\Xi_{i}^{(t)}=\tilde{\Omega}(1)$. To see this, we know that if
$c^{(t)}=\tilde{\Omega}(1/\alpha)$, then

$c^{(t+1)}\leq(1-\eta\lambda)c^{(t)}+\eta\tilde{O}\left(\nu^{(t)}\frac{\beta^{3}}{\alpha^{2}}\right)\leq
c^{(t)}$

To show that $\Xi_{i}^{(t)}=\tilde{\Omega}(1)$, assuming that
$\Xi_{i}^{(t)}=1/\mathrm{polylog}(d)$, we know that

$\Xi_{i}^{(t+1)}\geq(1-\eta\lambda)\Xi_{i}^{(t)}+\tilde{\Omega}\left(\eta\frac{1}{N}\right)\geq\Xi_{i}^{(t)}+\tilde{\Omega}\left(\eta\frac{1}{N}\right)$

Similarly, for GD + M, since
$\nu^{(t)}\leq\tilde{O}\left(\lambda/(\beta^{2})\right)$, we know that

$\nabla\hat{L}(W^{(t)})\leq\tilde{O}\left(\lambda\alpha^{3}/(\beta^{2})\right)$

This implies that

$\|W^{(t+1)}-W^{(t)}\|_{2}\leq\tilde{O}\left(\eta\lambda\alpha^{3}/(\beta^{2})\right)$

We need to show that $c^{(t)}=\tilde{\Omega}(1/\beta)$ and all
$|\Xi_{i,j,r}^{(t)}|\leq\tilde{O}(\sigma_{0}\sigma\sqrt{d})$. To see this, we
know that when $c^{(t)}=\Theta\left(\frac{1}{\beta}\right)$, we know that
$c^{(t-t_{0})}=\Theta\left(\frac{1}{\beta}\right)$ for every
$t_{0}\leq\frac{1}{\gamma}$. This implies that

$c^{(t+1)}\geq
c^{(t)}-O\left(\eta\lambda\frac{1}{\beta}\right)+\Omega\left(\frac{\eta}{N}\beta\right)\geq
c^{(t)}+\Omega\left(\frac{\eta}{N}\beta\right)$

On the other hand, for $\Xi_{i,j,r}^{(t)}$ we know that:

$|\Xi_{i,j,r}^{(t+1)}|\leq(1-\eta\lambda)|\Xi_{i,j,r}^{(t)}|+\tilde{O}\left(\eta\nu^{(t)}\sigma_{0}^{2}(\sigma\sqrt{d})^{2}\right)\leq\tilde{O}(\sigma_{0}\sigma\sqrt{d})$

##  Appendix I Technical lemmas for GD

This section presents the technical lemmas needed in Appendix F. These lemmas
mainly consists in different rewritings of GD.

###  I.1 Rewriting derivatives

Using D.1 and D.2, we rewrite the sigmoid terms $\ell_{i}^{(t)}$ when using
GD.

######  Lemma I.1 ($\mathcal{Z}_{1}$ derivative).

Let $i\in\mathcal{Z}_{1}.$ We have
$\ell_{i}^{(t)}=\Theta(1)\widehat{\ell}^{(t)}(\alpha).$

###### Proof of Lemma I.1.

Let $i\in\mathcal{Z}_{1}$. Using D.1, we bound $\ell_{i}^{(t)}$ as

$\displaystyle\frac{1}{1+\exp\left(\alpha^{3}\sum_{s=1}^{m}(c_{s}^{(t)})^{3}+\tilde{O}((\sigma\sigma_{0}\sqrt{d})^{3})\right)}$
$\displaystyle\leq\ell_{i}^{(t)}\leq\frac{1}{1+\exp\left(\alpha^{3}\sum_{s=1}^{m}(c_{s}^{(t)})^{3}-\tilde{O}((\sigma\sigma_{0}\sqrt{d})^{3})\right)}$
$\displaystyle\iff
e^{-\tilde{O}((\sigma\sigma_{0}\sqrt{d})^{3})}\widehat{\ell}^{(t)}(\alpha)$
$\displaystyle\leq\ell_{i}^{(t)}\leq
e^{\tilde{O}((\sigma\sigma_{0}\sqrt{d})^{3})}\widehat{\ell}^{(t)}(\alpha).$
(133)

(133) yields the aimed result. ∎

######  Lemma I.2 ($\mathcal{Z}_{2}$ derivative).

Let $i\in\mathcal{Z}_{2}.$ We have
$\ell_{i}^{(t)}=\Theta(1)\widehat{\ell}^{(t)}(\Xi_{i}^{(t)}).$

###### Proof.

Let $i\in\mathcal{Z}_{2}$. Using D.2, we bound $\ell_{i}^{(t)}$ as

$\displaystyle\frac{1}{1+\exp\left(\tilde{O}(\beta^{3}/\alpha^{3})+\Xi_{i}^{(t)}\right)}$
$\displaystyle\leq\ell_{i}^{(t)}\leq\frac{1}{1+\exp\left(-\tilde{O}(\beta^{3}\sigma_{0}^{3})+\Xi_{i}^{(t)}\right)}$
$\displaystyle\iff
e^{-\tilde{O}(\beta^{3}/\alpha^{3})}\widehat{\ell}^{(t)}(\Xi_{i}^{(t)})$
$\displaystyle\leq\ell_{i}^{(t)}\leq
e^{\tilde{O}(\beta^{3}\sigma_{0}^{3})}\widehat{\ell}^{(t)}(\Xi_{i}^{(t)}).$
(134)

(134) yields the aimed result. ∎

###  I.2 Signal lemmas

In this section, we present a lemma that bounds the sum over time of the GD
increment.

######  Lemma I.3.

Let $t,\mathscr{T}\in[T]$ such that $\mathscr{T}<t.$ Then, the
$\mathcal{Z}_{1}$ derivative is bounded as:

$\displaystyle\sum_{\tau=\mathscr{T}}^{t}\nu_{1}^{(\tau)}\min\\{\kappa,\alpha^{2}(c^{(\tau)})^{2}\\}$
$\displaystyle\leq\tilde{O}\left(\frac{1}{\eta\alpha^{2}}\right)+\tilde{O}\left(\frac{\beta^{3}}{\alpha^{2}}\right)\sum_{\tau=\mathscr{T}}^{t}\nu_{2}^{(\tau)}.$

###### Proof of Lemma I.3.

From Lemma F.4, we know that:

$\displaystyle c^{(t+1)}$ $\displaystyle\geq
c^{(t)}+\tilde{\Theta}(\eta\alpha)\nu_{1}^{(t)}\min\\{\kappa,\alpha^{2}(c^{(t)})^{2}\\}$
(135)

Let $\mathscr{T},t\in[T]$ such that $\mathscr{T}<t.$ We now sum up (135) for
$\tau=\mathscr{T},\dots,t$ and get:

$\displaystyle\sum_{\tau=\mathscr{T}}^{t}\nu_{1}^{(\tau)}\min\\{\kappa,\alpha^{2}(c^{(\tau)})^{2}\\}$
$\displaystyle\leq\tilde{O}\left(\frac{1}{\eta\alpha}\right)(c^{(t+1)}-c^{(\mathscr{T})}).$
(136)

We now consider two cases.

##### Case 1: $t<T_{0}.$

By definition, we know that $c^{(t)}\leq\tilde{O}(1/\alpha).$ Therefore, (136)
yields:

$\displaystyle\sum_{\tau=\mathscr{T}}^{t}\nu_{1}^{(\tau)}\min\\{\kappa,\alpha^{2}(c^{(\tau)})^{2}\\}$
$\displaystyle\leq\tilde{O}\left(\frac{1}{\eta\alpha^{2}}\right).$ (137)

##### Case 2: $t\in[T_{0},T].$

We distinguish two subcases.

  * –

Subcase 1: $\mathscr{T}<T_{0}.$ From Lemma 5.3, we know that:

$\displaystyle c^{(t+1)}$
$\displaystyle\leq\tilde{O}(1/\alpha)+\tilde{O}(\eta\beta^{3}/\alpha^{2})\sum_{\tau=T_{0}}^{t}\nu_{2}^{(\tau)}.$
(138)

We can further bound (138) as:

$\displaystyle c^{(t+1)}$
$\displaystyle\leq\tilde{O}(1/\alpha)+\tilde{O}(\eta\beta^{3}/\alpha^{2})\sum_{\tau=\mathscr{T}}^{t}\nu_{2}^{(\tau)},$
(139)

which combined with (136) implies:

$\displaystyle\sum_{\tau=\mathscr{T}}^{t}\nu_{1}^{(\tau)}\min\\{\kappa,\alpha^{2}(c^{(\tau)})^{2}\\}$
$\displaystyle\leq\tilde{O}\left(\frac{1}{\eta\alpha^{2}}\right)+\tilde{O}\left(\frac{\beta^{3}}{\alpha^{2}}\right)\sum_{\tau=\mathscr{T}}^{t}\nu_{2}^{(\tau)}$
(140)

  * –

Subcase 2: $\mathscr{T}>T_{0}.$ From Lemma 5.3, we know that:

$\displaystyle c^{(t+1)}$
$\displaystyle\leq\tilde{O}(1/\alpha)+\tilde{O}(\eta\beta^{3}/\alpha^{2})\sum_{\tau=\mathcal{T}}^{t}\nu_{2}^{(\tau)},$
(141)

which combined with (136) yields (140).

We therefore managed to prove that in all the cases, (140) holds.

∎

###  I.3 Noise lemmas

In this section, we present the technical lemmas needed in subsection F.2. The
following lemma bounds the projection of the GD increment on the noise.

######  Lemma I.4.

Let $i\in[N]$, $j\in[P]\backslash\\{P(\bm{X}_{i})\\}$ and $r\in[m]$. Let
$\mathscr{T},t\in[T]$ such that $\mathscr{T}<t.$ Then, the noise update (2)
satisfies

$\begin{split}\left|y_{i}(\Xi_{i,j,r}^{(t)}-\Xi_{i,j,r}^{(\mathscr{T})})-\frac{\tilde{\Theta}(\eta\sigma^{2}d)}{N}\sum_{\tau=\mathscr{T}}^{t-1}\ell_{i}^{(\tau)}(\Xi_{i,j,r}^{(\tau)})^{2}\right|&\leq\tilde{O}\left(\frac{P\sigma^{2}\sqrt{d}}{\alpha}\right)+\tilde{O}\left(\frac{\eta\beta^{3}}{\alpha}\right)\sum_{j=\mathscr{T}}^{t-1}\nu_{2}^{(j)}.\end{split}$

###### Proof of Lemma I.4.

Let $i\in[N]$, $j\in[P]\backslash\\{P(\bm{X}_{i})\\}$ and $r\in[m]$. We set up
the following induction hypothesis:

$\begin{split}&\left|y_{i}\Xi_{i,j,r}^{(t)}-y_{i}\Xi_{i,j,r}^{(\mathscr{T})}-\frac{\tilde{\Theta}(\eta\sigma^{2}d)}{N}\sum_{\tau=\mathscr{T}}^{t-1}\ell_{i}^{(\tau)}(\Xi_{i,j,r}^{(\tau)})^{2}\right|\\\
&\leq\tilde{O}\left(\frac{P\sigma^{2}\sqrt{d}}{\alpha}\left(1+\frac{\alpha}{\sigma^{2}d}+\frac{\alpha\eta}{N}\right)\sum_{\tau=0}^{t-1-\mathscr{T}}\frac{P^{\tau}}{d^{\tau/2}}\right)\\\
&+\tilde{O}\left(\frac{\eta\beta^{3}}{\alpha^{2}}\right)\sum_{\tau=0}^{t-1-\mathscr{T}}\frac{P^{\tau}}{d^{\tau/2}}\sum_{j=\mathscr{T}}^{t-\tau}\nu_{2}^{(j)},\end{split}$
(142)

Let’s first show this hypothesis for $t=\mathscr{T}.$ From Lemma F.5, we have:

$\begin{split}&\left|y_{i}(\Xi_{i,j,r}^{(\mathscr{T}+1)}-\Xi_{i,j,r}^{(\mathscr{T})})-\frac{\tilde{\Theta}(\eta\sigma^{2}d)}{N}\ell_{i}^{(\mathscr{T})}(\Xi_{i,j,r}^{(\mathscr{T})})^{2}\right|\\\
&\leq\frac{\tilde{\Theta}(\eta\sigma^{2}\sqrt{d})}{N}\sum_{a\in\mathcal{Z}_{2}}\sum_{k\neq
P(\bm{X}_{a})}\ell_{a}^{(\mathscr{T})}(\Xi_{a,k,r}^{(\mathscr{T})})^{2}\\\
&+\frac{\tilde{\Theta}(\eta\sigma^{2}\sqrt{d})}{N}\sum_{a\in\mathcal{Z}_{1}}\sum_{k\neq
P(\bm{X}_{a})}\ell_{a}^{(\mathscr{T})}(\Xi_{a,k,r}^{(\mathscr{T})})^{2}.\end{split}$
(143)

Now, we apply D.3 to bound $(\Xi_{a,k,r}^{(\mathscr{T})})^{2}$ in (143) and
obtain:

$\begin{split}&\left|y_{i}\Xi_{i,j,r}^{(\mathscr{T}+1)}-y_{i}\Xi_{i,j,r}^{(\mathscr{T})}-\frac{\tilde{\Theta}(\eta\sigma^{2}d)}{N}\ell_{i}^{(\mathscr{T})}(\Xi_{i,j,r}^{(\mathscr{T})})^{2}\right|\\\
&\leq\tilde{\Theta}(\eta
P\sigma^{2}\sqrt{d})\nu_{2}^{(\mathscr{T})}\min\\{\kappa,(c^{(\mathscr{T})})^{2}\alpha^{2}\\}\alpha\\\
&+\tilde{\Theta}(\eta
P\sigma^{2}\sqrt{d})\nu_{1}^{(\mathscr{T})}\min\\{\kappa,(c^{(\mathscr{T})})^{2}\alpha^{2}\\}\alpha.\end{split}$
(144)

We successively apply Lemma I.3, use
$\nu_{2}^{(\mathscr{T})}\min\\{\kappa,(c^{(\mathscr{T})})^{2}\alpha^{2}\\}\alpha\leq\hat{\mu}\tilde{O}(1)\leq\tilde{O}(\hat{\mu})$
and $\hat{\mu}=\Theta(1/N)$ in (144) to finally obtain:

$\displaystyle\left|y_{i}\Xi_{i,j,r}^{(\mathscr{T}+1)}-y_{i}\Xi_{i,j,r}^{(\mathscr{T})}-\frac{\tilde{\Theta}(\eta\sigma^{2}d)}{N}\ell_{i}^{(\mathscr{T})}(\Xi_{i,j,r}^{(\mathscr{T})})^{2}\right|$
$\displaystyle\leq\tilde{O}\left(\frac{P\sigma^{2}\sqrt{d}}{\alpha}\left(1+\frac{\eta\alpha}{N}\right)\right).$

Therefore, the induction hypothesis is verified for $t=\mathscr{T}.$ Now,
assume (LABEL:eq:noiseindhypoth) for $t.$ Let’s prove the result for $t+1.$ We
start by summing up the noise update from Lemma F.5 for
$\tau=\mathscr{T},\dots,t$ which yields:

$\begin{split}&\left|y_{i}(\Xi_{i,j,r}^{(t+1)}-\Xi_{i,j,r}^{(\mathscr{T})})-\frac{\tilde{\Theta}(\eta\sigma^{2}d)}{N}\sum_{\tau=\mathscr{T}}^{t}\ell_{i}^{(\tau)}(\Xi_{i,j,r}^{(\tau)})^{2}\right|\\\
&\leq\frac{\tilde{\Theta}(\eta\sigma^{2}\sqrt{d})}{N}\sum_{\tau=\mathscr{T}}^{t-1}\sum_{a\in\mathcal{Z}_{2}}\ell_{a}^{(\tau)}\sum_{k\neq
P(\bm{X}_{a})}(\Xi_{a,k,r}^{(\tau)})^{2}\\\
&+\frac{\tilde{\Theta}(\eta\sigma^{2}\sqrt{d})}{N}\sum_{a\in\mathcal{Z}_{2}}\ell_{a}^{(t)}\sum_{k\neq
P(\bm{X}_{a})}(\Xi_{a,k,r}^{(t)})^{2}\\\
&+\frac{\tilde{\Theta}(\eta\sigma^{2}\sqrt{d})}{N}\sum_{\tau=\mathscr{T}}^{t}\sum_{a\in\mathcal{Z}_{1}}\ell_{a}^{(\tau)}\sum_{k\neq
P(\bm{X}_{a})}(\Xi_{a,k,r}^{(\tau)})^{2}\end{split}$ (145)

We apply D.3 to bound $(\Xi_{a,k,r}^{(t)})^{2}$ in (LABEL:eq:noiseupd20) and
obtain:

$\begin{split}&\left|y_{i}(\Xi_{i,j,r}^{(t+1)}-\Xi_{i,j,r}^{(\mathscr{T})})-\frac{\tilde{\Theta}(\eta\sigma^{2}d)}{N}\sum_{\tau=\mathscr{T}}^{t}\ell_{i}^{(\tau)}(\Xi_{i,j,r}^{(\tau)})^{2}\right|\\\
&\leq\frac{\tilde{\Theta}(\eta\sigma^{2}\sqrt{d})}{N}\sum_{\tau=\mathscr{T}}^{t-1}\sum_{a\in\mathcal{Z}_{2}}\ell_{a}^{(\tau)}\sum_{k\neq
P(\bm{X}_{a})}(\Xi_{a,k,r}^{(\tau)})^{2}\\\ &+\tilde{\Theta}(\eta
P\sigma^{2}\sqrt{d})\nu_{2}^{(t)}\alpha\min\\{\kappa,(c^{(t)})^{2}\alpha^{2}\\}\\\
&+\tilde{\Theta}(\eta
P\sigma^{2}\sqrt{d})\sum_{\tau=\mathscr{T}}^{t}\nu_{1}^{(\tau)}\alpha\min\\{\kappa,(c^{(\tau)})^{2}\alpha^{2}\\}\end{split}$
(146)

Similarly to above, we apply Lemma I.3 to bound
$\sum_{\tau=0}^{t}\nu_{1}^{(\tau)}\alpha\min\\{\kappa,(c^{(\tau)})^{2}\alpha^{2}\\}$.
We also use
$\nu_{2}^{(t)}\alpha\min\\{\kappa,(c^{(t)})^{2}\alpha^{2}\\}\leq\tilde{O}(\hat{\mu})$
and $\hat{\mu}=\Theta(1/N)$ in (LABEL:eq:noiseupd201) and obtain:

$\begin{split}&\left|y_{i}(\Xi_{i,j,r}^{(t+1)}-\Xi_{i,j,r}^{(\mathscr{T})})-\frac{\tilde{\Theta}(\eta\sigma^{2}d)}{N}\sum_{\tau=\mathscr{T}}^{t}\ell_{i}^{(\tau)}(\Xi_{i,j,r}^{(\tau)})^{2}\right|\\\
&\leq\frac{\tilde{\Theta}(\eta\sigma^{2}\sqrt{d})}{N}\sum_{\tau=\mathscr{T}}^{t-1}\sum_{a\in\mathcal{Z}_{2}}\ell_{a}^{(\tau)}\sum_{k\neq
P(\bm{X}_{a})}(\Xi_{a,k,r}^{(\tau)})^{2}\\\
&+\tilde{O}\left(\frac{P\sigma^{2}\sqrt{d}}{\alpha}\left(1+\frac{\eta\alpha}{N}\right)\right)\\\
&+\tilde{O}\left(\frac{\eta\beta^{3}}{\alpha^{2}}\right)\sum_{j=\mathscr{T}}^{t}\nu_{2}^{(j)}.\end{split}$
(147)

To bound the first term in the right-hand side of (LABEL:eq:noiseupd202), we
use the induction hypothesis (LABEL:eq:noiseindhypoth). Plugging this
inequality in (LABEL:eq:noiseupd202) yields:

$\begin{split}&\left|y_{i}(\Xi_{i,j,r}^{(t+1)}-\Xi_{i,j,r}^{(\mathscr{T})})-\frac{\tilde{\Theta}(\eta\sigma^{2}d)}{N}\sum_{\tau=\mathscr{T}}^{t}\ell_{i}^{(\tau)}(\Xi_{i,j,r}^{(\tau)})^{2}\right|\\\
&\leq\frac{1}{\sqrt{d}}\sum_{a\in\mathcal{Z}_{2}}\sum_{k\neq
P(X_{k})}y_{a}(\Xi_{a,k,r}^{(t)}-\Xi_{a,k,r}^{(\mathscr{T})})\\\
&+\tilde{O}\left(\frac{P^{2}\sigma^{2}}{\alpha\sqrt{d}}\left(1+\frac{\alpha}{\sigma^{2}d}+\frac{\alpha\eta}{N}\right)\sum_{\tau=0}^{t-1-\mathscr{T}}\frac{P^{\tau}}{d^{\tau/2}}\right)\\\
&+\frac{P}{\sqrt{d}}\tilde{O}\left(\frac{\eta\beta^{3}}{\alpha^{2}}\right)\sum_{\tau=0}^{t-1-\mathscr{T}}\frac{P^{\tau}}{d^{\tau/2}}\sum_{j=\mathscr{T}}^{t-1-\tau}\nu_{2}^{(j)}\\\
&+\tilde{O}\left(\frac{P\sigma^{2}\sqrt{d}}{\alpha}\left(1+\frac{\eta\alpha}{N}\right)\right)\\\
&+\tilde{O}\left(\frac{\eta\beta^{3}}{\alpha^{2}}\right)\sum_{j=\mathscr{T}}^{t}\nu_{2}^{(j)}.\end{split}$
(148)

Now, we apply D.1 to have
$y_{a}(\Xi_{a,k,r}^{(t)}-\Xi_{a,k,r}^{(0)})\leq\tilde{O}(1)$ in
(LABEL:eq:noiseupd203) and therefore,

$\begin{split}&\left|y_{i}\Xi_{i,j,r}^{(t+1)}-y_{i}\Xi_{i,j,r}^{(\mathscr{T})}-\frac{\tilde{\Theta}(\eta\sigma^{2}d)}{N}\sum_{\tau=\mathscr{T}}^{t}\ell_{i}^{(\tau)}(\Xi_{i,j,r}^{(\tau)})^{2}\right|\\\
&\leq\frac{\tilde{O}(P)}{\sqrt{d}}+\tilde{O}\left(\frac{P\sigma^{2}\sqrt{d}}{\alpha}\left(1+\frac{\alpha}{\sigma^{2}d}+\frac{\alpha\eta}{N}\right)\sum_{\tau=1}^{t-\mathscr{T}}\frac{P^{\tau}}{d^{\tau/2}}\right)\\\
&+\tilde{O}\left(\frac{\eta\beta^{3}}{\alpha^{2}}\right)\sum_{\tau=1}^{t-\mathscr{T}}\frac{P^{\tau}}{d^{\tau/2}}\sum_{j=\mathscr{T}}^{t-\tau}\nu_{2}^{(j)}\\\
&+\tilde{O}\left(\frac{P\sigma^{2}\sqrt{d}}{\alpha}\left(1+\frac{\eta\alpha}{N}\right)\right)\\\
&+\tilde{O}\left(\frac{\eta\beta^{3}}{\alpha^{2}}\right)\sum_{j=\mathscr{T}}^{t}\nu_{2}^{(j)}.\end{split}$
(149)

By rearranging the terms, we finally have:

$\begin{split}&\left|y_{i}\Xi_{i,j,r}^{(t+1)}-y_{i}\Xi_{i,j,r}^{(\mathscr{T})}-\frac{\tilde{\Theta}(\eta\sigma^{2}d)}{N}\sum_{\tau=\mathscr{T}}^{t}\ell_{i}^{(\tau)}(\Xi_{i,j,r}^{(\tau)})^{2}\right|\\\
&\leq\tilde{O}\left(\frac{P\sigma^{2}\sqrt{d}}{\alpha}\left(1+\frac{\alpha}{\sigma^{2}d}+\frac{\alpha\eta}{N}\right)\sum_{\tau=0}^{t-\mathscr{T}}\frac{P^{\tau}}{d^{\tau/2}}\right)\\\
&+\tilde{O}\left(\frac{\eta\beta^{3}}{\alpha^{2}}\right)\sum_{\tau=0}^{t-\mathscr{T}}\frac{P^{\tau}}{d^{\tau/2}}\sum_{j=\mathscr{T}}^{t-\tau}\nu_{2}^{(j)},\end{split}$
(150)

which proves the induction hypothesis for $t+1.$

Now, let’s simplify the sum terms in (LABEL:eq:noiseindhypoth). Since
$P\ll\sqrt{d}$, by definition of a geometric sequence, we have:

$\displaystyle\sum_{\tau=0}^{t-\mathscr{T}}\frac{P^{\tau}}{d^{\tau/2}}$
$\displaystyle\leq\frac{1}{1-\frac{P}{\sqrt{d}}}=\Theta(1).$ (151)

Plugging (151) in (LABEL:eq:noiseindhypoth) yields

$\begin{split}\left|y_{i}(\Xi_{i,j,r}^{(t)}-\Xi_{i,j,r}^{(\mathscr{T})})-\frac{\tilde{\Theta}(\eta\sigma^{2}d)}{N}\sum_{\tau=\mathscr{T}}^{t}\ell_{i}^{(\tau)}(\Xi_{i,j,r}^{(\tau)})^{2}\right|&\leq\tilde{O}\left(\frac{P\sigma^{2}\sqrt{d}}{\alpha}\right)\\\
&+\tilde{O}\left(\frac{\eta\beta^{3}}{\alpha^{2}}\right)\sum_{\tau=0}^{t-1-\mathscr{T}}\frac{P^{\tau}}{d^{\tau/2}}\sum_{j=\mathscr{T}}^{t-1-\tau}\nu_{2}^{(j)}.\end{split}$
(152)

Now, let’s simplify the second sum term in (152). Indeed, we have:

$\displaystyle\sum_{\tau=0}^{t-1-\mathscr{T}}\frac{P^{\tau}}{d^{\tau/2}}\sum_{j=\mathscr{T}}^{t-1-\tau}\nu_{2}^{(j)}$
$\displaystyle\leq\sum_{\tau=0}^{t-1-\mathscr{T}}\frac{P^{\tau}}{d^{\tau/2}}\sum_{j=\mathscr{T}}^{t-1}\nu_{2}^{(j)}\leq\Theta(1)\sum_{j=\mathscr{T}}^{t-1}\nu_{2}^{(j)},$
(153)

where we used (151) in the last inequality. Plugging (153) in (152) gives the
final result. ∎

After $T_{1}$ iterations, we prove with Lemma 5.4 that for
$i\in\mathcal{Z}_{2}$ and $j\in[P]\backslash\\{P(\bm{X}_{i})\\}$, there exists
$r\in[m]$ such that $\Xi_{i,j,r}^{(\tau)}$ is large. This implies that
$(\Xi_{i,j,r}^{(\tau)})^{2}\ell_{i}^{(\tau)}(\Xi_{i}^{(\tau)})$ stays well
controlled. We therefore rewrite Lemma I.4 to take this into account.

######  Lemma I.5.

Let $i\in[N]$, $j\in[P]\backslash\\{P(\bm{X}_{i})\\}$ and $r\in[m]$. Let
$\mathscr{T},t\in[T]$ such that $\mathscr{T}<t.$ Then, the noise update (2)
satisfies

$\begin{split}\left|y_{i}(\Xi_{i,j,r}^{(t)}-\Xi_{i,j,r}^{(\mathscr{T})})-\frac{\tilde{\Theta}(\eta\sigma^{2}d)}{N}\sum_{\tau=\mathscr{T}}^{t-1}\ell_{i}^{(\tau)}\min\\{\kappa,(\Xi_{i,j,r}^{(\tau)})^{2}\\}\right|&\leq\tilde{O}\left(\frac{P\sigma^{2}\sqrt{d}}{\alpha}\right)+\tilde{O}\left(\frac{\eta\beta^{3}}{\alpha^{2}}\right)\sum_{j=\mathscr{T}}^{t-1}\nu_{2}^{(j)}.\end{split}$

###### Proof of Lemma I.5.

From Lemma I.4, we know that

$\displaystyle\left|y_{i}(\Xi_{i,j,r}^{(t)}-\Xi_{i,j,r}^{(\mathscr{T})})-\frac{\tilde{\Theta}(\eta\sigma^{2}d)}{N}\sum_{\tau=\mathscr{T}}^{t-1}\ell_{i}^{(\tau)}(\Xi_{i,j,r}^{(\tau)})^{2}\right|$
$\displaystyle\leq\tilde{O}\left(\frac{P\sigma^{2}\sqrt{d}}{\alpha}\right)+\tilde{O}\left(\frac{\eta\beta^{3}}{\alpha^{2}}\right)\sum_{j=\mathscr{T}}^{t-1}\nu_{2}^{(j)}.$
(154)

Using Remark 1, we know that a sufficient condition to have
$\widehat{\ell}^{(\tau)}(\Xi_{i}^{(t)}$ is
$(\Xi_{i,j,r}^{(\tau)})^{2}\geq\kappa\geq\tilde{\Omega}(1).$ Therefore, we can
replace
$\widehat{\ell}^{(t)}(\Xi_{i}^{(t)})(\Xi_{i,j,r}^{(\tau)})^{2}=\min\\{\kappa,(\Xi_{i,j,r}^{(\tau)})^{2}\\}.$
Plugging this equality in (154) yields the aimed result. ∎

######  Lemma I.6.

Let
$T_{1}=\tilde{O}\left(\frac{N}{\sigma_{0}\sigma\sqrt{d}\sigma^{2}d}\right)$.
For $t\in[T_{1},T]$, we have
$\frac{1}{N}\sum_{\tau=0}^{t}\sum_{i\in\mathcal{Z}_{2}}\ell_{i}^{(\tau)}\min\\{\kappa,(\Xi_{i,j,r}^{(\tau)})^{2}\\}\leq\tilde{O}\left(\frac{1}{\eta}\right).$

###### Proof of Lemma I.6.

From Lemma F.9, we know that:

$\displaystyle\sum_{\tau=T_{1}}^{t}\nu_{2}^{(\tau)}\leq\tilde{O}\left(\frac{1}{\eta\sigma_{0}}\right).$
(155)

On the other hand we know from Lemma I.5 that:

$\displaystyle\frac{\tilde{\Theta}(\eta\sigma^{2}d)}{N}\sum_{\tau=0}^{T_{1}-1}\sum_{i\in\mathcal{Z}_{2}}\ell_{i}^{(\tau)}\min\\{\kappa,(\Xi_{i,j,r}^{(\tau)})^{2}\\}$
$\displaystyle\leq
y_{i}(\Xi_{i,j,r}^{(T_{1})}-\Xi_{i,j,r}^{(0)})+\tilde{O}\left(\frac{P\sigma^{2}\sqrt{d}}{\alpha}\right)$
(156)
$\displaystyle+\tilde{O}\left(\frac{\eta\hat{\mu}\beta^{3}}{\alpha}\right)T_{1}.$

Besides, we have:
$\tilde{O}\left(\frac{\eta\hat{\mu}\beta^{3}}{\alpha}\right)T_{1}\leq\tilde{O}\left(\frac{P\sigma^{2}\sqrt{d}}{\alpha}\right).$
Plugging this inequality yields

$\displaystyle\frac{\tilde{\Theta}(\eta\sigma^{2}d)}{N}\sum_{\tau=0}^{T_{1}-1}\sum_{i\in\mathcal{Z}_{2}}\ell_{i}^{(\tau)}\min\\{\kappa,(\Xi_{i,j,r}^{(\tau)})^{2}\\}$
$\displaystyle\leq
y_{i}(\Xi_{i,j,r}^{(T_{1})}-\Xi_{i,j,r}^{(0)})+\tilde{O}\left(\frac{P\sigma^{2}\sqrt{d}}{\alpha}\right).$
(157)

By applying D.1, (157) is eventually bounded as:

$\displaystyle\frac{1}{N}\sum_{\tau=0}^{t}\sum_{i\in\mathcal{Z}_{2}}\ell_{i}^{(\tau)}\min\\{\kappa,(\Xi_{i,j,r}^{(\tau)})^{2}\\}$
$\displaystyle\leq\tilde{O}\left(\frac{1}{\eta\sigma^{2}d}\right)+\tilde{O}\left(\frac{P}{\eta\alpha\sqrt{d}}\right)\leq\tilde{O}\left(\frac{1}{\eta}\right).$
(158)

By combining (51) and (158) we deduce that for all
$j\in[P]\backslash\\{P(\bm{X}_{i})\\}$ and $r\in[m]$:

$\displaystyle\frac{1}{N}\sum_{\tau=0}^{t}\sum_{i\in\mathcal{Z}_{2}}\ell_{i}^{(\tau)}\min\\{\kappa,(\Xi_{i,j,r}^{(\tau)})^{2}\\}$
$\displaystyle=\frac{1}{N}\sum_{\tau=0}^{T_{1}}\sum_{i\in\mathcal{Z}_{2}}\ell_{i}^{(\tau)}\min\\{\kappa,(\Xi_{i,j,r}^{(\tau)})^{2}\\}$
(159)
$\displaystyle+\frac{1}{N}\sum_{\tau=T_{1}}^{t}\sum_{i\in\mathcal{Z}_{2}}\ell_{i}^{(\tau)}\min\\{\kappa,(\Xi_{i,j,r}^{(\tau)})^{2}\\}$
$\displaystyle\leq\tilde{O}\left(\frac{1}{\eta}\right).$

∎

###  I.4 Convergence rate of the training loss using GD

In this section, we prove that when using GD, the training loss converges
sublinearly in our setting.

####  I.4.1 Convergence after learning $\mathcal{Z}_{1}$ ($t\in[T_{0},T]$)

######  Lemma I.7 (Convergence rate of the $\mathcal{Z}_{1}$ loss).

Let $t\in[T_{0},T]$. Run GD with learning rate $\eta$ for $t$ iterations.
Then, the $\mathcal{Z}_{1}$ loss sublinearly converges to zero as:

$\displaystyle(1-\hat{\mu})\widehat{\mathcal{L}}^{(t)}(\alpha)\leq\frac{\tilde{O}(1)}{\eta\alpha^{2}(t-T_{0}+1)}.$

###### Proof of Lemma I.7.

Let $t\in[T_{0},T].$ From Lemma F.1, we know that the signal update is lower
bounded as:

$\displaystyle c^{(t+1)}\geq
c^{(t)}+\Theta(\eta\alpha)(1-\hat{\mu})\widehat{\ell}^{(t)}(\alpha)(\alpha
c^{(t)})^{2}.$ (160)

From Lemma 5.1, we know that $c^{(t)}\geq\tilde{\Omega}(1/\alpha)$. Thus, we
simplify (160) as:

$\displaystyle c^{(t+1)}\geq
c^{(t)}+\tilde{\Omega}(\eta\alpha)(1-\hat{\mu})\widehat{\ell}^{(t)}(\alpha).$
(161)

Since
$\alpha^{3}\sum_{r=1}^{m}(c_{r}^{(t)})^{3}\geq\tilde{\Omega}(1/\alpha)-m\tilde{O}(\sigma_{0})\geq\tilde{\Omega}(1/\alpha)>0$,
we can apply Lemma K.22 and obtain:

$\displaystyle c^{(t+1)}\geq
c^{(t)}+\tilde{\Omega}(\eta\alpha)(1-\hat{\mu})\widehat{\mathcal{L}}^{(t)}(\alpha).$
(162)

Let’s now assume by contradiction that for $t\in[T_{0},T]$, we have:

$\displaystyle(1-\hat{\mu})\widehat{\mathcal{L}}^{(t)}(\alpha)>\frac{\tilde{\Omega}(1)}{\eta\alpha^{2}(t-T_{0}+1)}.$
(163)

From the (3) update, we know that $c_{r}^{(\tau)}$ is a non-decreasing
sequence which implies that $\sum_{r=1}^{m}(\alpha c_{r}^{(\tau)})^{3}$ is
also non-decreasing. Since $x\mapsto\log(1+\exp(-x))$ is non-increasing, this
implies that for $s\leq t$, we have:

$\displaystyle\frac{\tilde{\Omega}(1)}{\eta\alpha^{2}(t-T_{0}+1)}<(1-\hat{\mu})\widehat{\mathcal{L}}^{(t)}(\alpha)\leq(1-\hat{\mu})\widehat{\mathcal{L}}^{(s)}(\alpha).$
(164)

Plugging (164) in the update (162) yields for $s\in[T_{0},t]$:

$\displaystyle c^{(s+1)}>c^{(s)}+\frac{\tilde{\Omega}(1)}{\alpha(t-T_{0}+1)}.$
(165)

Let $t\in[T_{0},T]$. We now sum (165) for $s=T_{0},\dots,t$ and obtain:

$\displaystyle
c^{(t+1)}>c^{(T_{0})}+\frac{\tilde{\Omega}(1)(t-T_{0}+1)}{\alpha(t-T_{0}+1)}>\frac{\tilde{\Omega}(1)}{\alpha},$
(166)

where we used the fact that $c^{(T_{0})}\geq\tilde{\Omega}(1/\alpha)>0$ (Lemma
5.1) in the last inequality. Therefore, we have for $t\in[T_{0},T],$
$c^{(t)}\geq\tilde{\Omega}(1/\alpha)>0$. Let’s now show that (166) implies a
contradiction. Indeed, we have:

$\displaystyle\eta\alpha^{2}(t-T_{0}+1)(1-\hat{\mu})\widehat{\mathcal{L}}^{(t)}(\alpha)$
$\displaystyle\leq$
$\displaystyle\eta\alpha^{2}T(1-\hat{\mu})\log\left(1+\exp(-(\alpha
c^{(t)})^{3}-\sum_{r\neq r_{\max}}(\alpha c_{r}^{(t)})^{3}\right)$
$\displaystyle\leq$
$\displaystyle\eta\alpha^{2}T(1-\hat{\mu})\log\left(1+\exp(-\tilde{\Omega}(1)\right),$
(167)

where we used $\sum_{r\neq
r_{\max}}(c_{r}^{(t)})^{3}\geq-m\tilde{O}(\sigma_{0}^{3})$ along with (166) in
(167). We now apply Lemma K.22 in (167) and obtain:

$\displaystyle\eta\alpha^{2}(t-T_{0}+1)(1-\hat{\mu})\widehat{\mathcal{L}}^{(t)}(\alpha)\leq\frac{(1-\hat{\mu})\eta\alpha^{2}T}{1+\exp(\tilde{\Omega}(1))}.$
(168)

Given the values of $T,\eta,\alpha,\hat{\mu}$, we finally have:

$\displaystyle\eta\alpha^{2}(t-(T_{0}-1))(1-\hat{\mu})\widehat{\mathcal{L}}^{(t)}(\alpha)<\tilde{O}(1),$
(169)

which contradicts (163). ∎

####  I.4.2 Convergence at late stages ($t\in[T_{1},T]$)

######  Lemma I.8 (Convergence rate of the loss).

Let $t\in[T_{1},T]$. Run GD with learning rate $\eta\in(0,1/L)$ for $t$
iterations. Then, the loss sublinearly converges to zero as:

$\displaystyle\widehat{L}(\bm{W}^{(t)})\leq\frac{\tilde{O}(1)}{\eta(t-T_{1}+1)}.$

###### Proof of Lemma I.8.

We first apply the classical descent lemma for smooth functions (Lemma K.18).
Since $\widehat{L}(W)$ is smooth, we have:

$\displaystyle\widehat{L}(\bm{W}^{(t+1)})\leq\widehat{L}(\bm{W}^{(t)})-\frac{\eta}{2}\|\nabla\widehat{L}(\bm{W}^{(t)})\|_{2}^{2}=\widehat{L}(\bm{W}^{(t)})-\frac{\eta}{2}\sum_{r=1}^{m}\|\nabla_{\bm{w}_{r}}\widehat{L}(\bm{W}^{(t)})\|_{2}^{2}.$
(170)

Lemma I.9 provides a lower bound on the gradient. We plug it in (170) and get:

$\displaystyle\widehat{L}(\bm{W}^{(t+1)})\leq\widehat{L}(\bm{W}^{(t)})-\tilde{\Omega}(\eta)\widehat{L}(\bm{W}^{(t)})^{2}.$
(171)

Applying Lemma K.19 to (171) yields the aimed result. ∎

####  I.4.3 Auxiliary lemmas for the proof of Lemma I.8

To obtain the convergence rate in Lemma I.8, we used the following auxiliary
lemma.

######  Lemma I.9 (Bound on the gradient for GD).

Let $t\in[T_{1},T]$. Run GD for $t$ iterations. Then, the norm of gradient is
lower bounded as follows:

$\displaystyle\sum_{r=1}^{m}\|\nabla_{\bm{w}_{r}}\widehat{L}(\bm{W}^{(t)})\|_{2}^{2}$
$\displaystyle\geq\tilde{\Omega}(1)\widehat{L}(\bm{W}^{(t)})^{2}.$

###### Proof of Lemma I.9.

Let $t\in[T_{1},T]$. To obtain the lower bound, we project the gradient on the
the signal and on the noise.

##### Projection on the signal.

Since $\|w^{*}\|_{2}=1$, we lower bound
$\|\nabla_{\bm{w}_{r}}\widehat{L}(\bm{W}^{(t)})\|_{2}^{2}$ as

$\displaystyle\|\nabla_{\bm{w}_{r}}\widehat{L}(\bm{W}^{(t)})\|_{2}^{2}\geq\langle\nabla_{\bm{w}_{r}}\widehat{L}(\bm{W}^{(t)}),w^{*}\rangle^{2}=(\mathscr{G}_{r}^{(t)})^{2}.$
(172)

By successively applying Lemma E.2 and Lemma I.1,
$(\mathscr{G}_{r}^{(t)})^{2}$ is lower bounded as

$\displaystyle(\mathscr{G}_{r}^{(t)})^{2}\geq\left(\frac{\alpha^{3}}{N}\sum_{i\in\mathcal{Z}_{1}}\ell_{i}^{(t)}(c_{r}^{(t)})^{2}\right)^{2}\geq\Omega(1)\left(\alpha^{3}(1-\hat{\mu})\widehat{\ell}^{(t)}(\alpha)(c_{r}^{(t)})^{2}\right)^{2}.$
(173)

Combining (172) and (173) yields:

$\displaystyle\|\nabla_{\bm{w}_{r}}\widehat{L}(\bm{W}^{(t)})\|_{2}^{2}\geq\Omega(1)\left(\alpha^{3}(1-\hat{\mu})\widehat{\ell}^{(t)}(\alpha)(c_{r}^{(t)})^{2}\right)^{2}.$
(174)

##### Projection on the noise.

For a fixed $i\in\mathcal{Z}_{2}$ and $j\in[P]\backslash\\{P(\bm{X}_{i})\\}$,
we know that $\|\nabla_{\bm{w}_{r}}\widehat{L}(\bm{W}^{(t)})\|_{2}^{2}$ is
lower bounded as

$\displaystyle\|\nabla_{\bm{w}_{r}}\widehat{L}(\bm{W}^{(t)})\|_{2}^{2}\geq\left\langle\nabla_{\bm{w}_{r}}\widehat{L}(\bm{W}^{(t)}),\frac{\frac{1}{N}\sum_{i\in\mathcal{Z}_{2}}\sum_{j\neq
P(\bm{X}_{i})}\bm{X}_{i}[j]}{\|\frac{1}{N}\sum_{i\in\mathcal{Z}_{2}}\sum_{j\neq
P(\bm{X}_{i})}\bm{X}_{i}[j]\|_{2}}\right\rangle^{2}=(\mathrm{G}_{r}^{(t)})^{2}.$
(175)

On the other hand, by Lemma I.14, we lower bound $\mathrm{G}_{r}^{(t)}$ term
with probability $1-o(1)$ as:

$\displaystyle(\mathrm{G}_{r}^{(t)})^{2}$
$\displaystyle\geq\left(\frac{\tilde{\Omega}(\sigma\sqrt{d})}{N}\sum_{i\in\mathcal{Z}_{2}}\sum_{j\neq
P(\bm{X}_{i})}\ell_{i}^{(t)}(\Xi_{i,j,r}^{(t)})^{2}-\frac{\tilde{O}(\sigma)}{N}\sum_{i\in\mathcal{Z}_{1}}\sum_{j\neq
P(\bm{X}_{i})}\ell_{i}^{(t)}(\Xi_{i,j,r}^{(t)})^{2}\right)^{2}$ (176)

##### Gathering the bounds.

Combining (172), (175), (173) and (176) and using
$2a^{2}+2b^{2}\geq(a+b)^{2},$ we thus bound
$\|\nabla_{\bm{w}_{r}}\widehat{L}(\bm{W}^{(t)})\|_{2}^{2}$ as:

$\begin{split}\|\nabla_{\bm{w}_{r}}\widehat{L}(\bm{W}^{(t)})\|_{2}^{2}\geq&\left(\frac{\alpha+\tilde{O}(\sigma)}{N}\sum_{i\in\mathcal{Z}_{1}}\ell_{i}^{(t)}\alpha^{2}(c_{r}^{(t)})^{2}\right.\\\
&\left.+\frac{\tilde{\Omega}(\sigma\sqrt{d})}{N}\sum_{i\in\mathcal{Z}_{2}}\sum_{j\neq
P(\bm{X}_{i})}\ell_{i}^{(t)}(\Xi_{i,j,r}^{(t)})^{2}\right.\\\
&\left.-\frac{\tilde{O}(\sigma)}{N}\sum_{i\in\mathcal{Z}_{1}}\sum_{j\neq
P(\bm{X}_{i})}\ell_{i}^{(t)}\left((\alpha^{2}(c_{r}^{(t)})^{2}+(\Xi_{i,j,r}^{(t)})^{2}\right)\right)^{2}.\end{split}$
(177)

We now sum up (177) for $r=1,\dots,m$ and apply Cauchy-Schwarz inequality to
get:

$\begin{split}\sum_{r=1}^{m}\|\nabla_{\bm{w}_{r}}\widehat{L}(\bm{W}^{(t)})\|_{2}^{2}&\geq\frac{1}{m}\left(\frac{\alpha+\tilde{O}(\sigma)}{N}\sum_{r=1}^{m}\ell_{i}^{(t)}(\alpha)\alpha^{2}(c_{r}^{(t)})^{2}\right.\\\
&\left.+\frac{\tilde{\Omega}(\sigma\sqrt{d})}{N}\sum_{i\in\mathcal{Z}_{2}}\sum_{r=1}^{m}\sum_{j\neq
P(\bm{X}_{i})}\ell_{i}^{(t)}(\Xi_{i,j,r}^{(t)})^{2}\right.\\\
&\left.-\frac{\tilde{O}(\sigma)}{N}\sum_{i\in\mathcal{Z}_{1}}\sum_{r=1}^{m}\sum_{j\neq
P(\bm{X}_{i})}\ell_{i}^{(t)}\left((\alpha^{2}(c_{r}^{(t)})^{2}+(\Xi_{i,j,r}^{(t)})^{2}\right)\right)^{2}.\end{split}$
(178)

We apply Lemma I.1 to further lower bound (178) and get:

$\begin{split}\sum_{r=1}^{m}\|\nabla_{\bm{w}_{r}}\widehat{L}(\bm{W}^{(t)})\|_{2}^{2}&\geq\Omega\left(\frac{1}{m}\right)\left((\alpha+\tilde{O}(\sigma))(1-\hat{\mu})\sum_{r=1}^{m}\widehat{\ell}^{(t)}(\alpha)\alpha^{2}(c_{r}^{(t)})^{2}\right.\\\
&\left.+\frac{\tilde{\Omega}(\sigma\sqrt{d})}{N}\sum_{i\in\mathcal{Z}_{2}}\sum_{r=1}^{m}\sum_{j\neq
P(\bm{X}_{i})}\ell_{i}^{(t)}(\Xi_{i,j,r}^{(t)})^{2}\right.\\\
&\left.-\frac{\tilde{O}(\sigma)}{N}\sum_{i\in\mathcal{Z}_{1}}\sum_{r=1}^{m}\sum_{j\neq
P(\bm{X}_{i})}\ell_{i}^{(t)}\left((\alpha^{2}(c_{r}^{(t)})^{2}+(\Xi_{i,j,r}^{(t)})^{2}\right)\right)^{2}.\end{split}$
(179)

##### Bound the gradient terms by the loss.

Using Lemma I.10, Lemma I.11 and Lemma I.12 we have:

$\displaystyle(\alpha+\tilde{O}(\sigma))(1-\hat{\mu})\sum_{r=1}^{m}\widehat{\ell}^{(t)}(\alpha)\alpha^{2}(c_{r}^{(t)})^{2}$
$\displaystyle\geq\tilde{\Omega}(\alpha+\tilde{O}(\sigma))\widehat{\mathcal{L}}^{(t)}(\alpha),$
(180)
$\displaystyle\frac{\tilde{O}(\sigma)}{N}\sum_{i\in\mathcal{Z}_{1}}\sum_{r=1}^{m}\sum_{j\neq
P(\bm{X}_{i})}\ell_{i}^{(t)}\left((\alpha^{2}(c_{r}^{(t)})^{2}+(\Xi_{i,j,r}^{(t)})^{2}\right)$
$\displaystyle\leq\tilde{O}(\sigma)(1-\hat{\mu})\widehat{\mathcal{L}}^{(t)}(\alpha),$
(181)
$\displaystyle\frac{\tilde{\Omega}(\sigma\sqrt{d})}{N}\sum_{i\in\mathcal{Z}_{2}}\sum_{r=1}^{m}\sum_{j\neq
P(\bm{X}_{i})}\ell_{i}^{(t)}(\Xi_{i,j,r}^{(t)})^{2}$
$\displaystyle\geq\frac{\tilde{\Omega}(\sigma\sqrt{d})}{N}\sum_{i\in\mathcal{Z}_{2}}\widehat{\mathcal{L}}^{(t)}(\Xi_{i}^{(t)}).$
(182)

Plugging (180), (181) and (182) in (179) yields:

$\displaystyle\sum_{r=1}^{m}\|\nabla_{\bm{w}_{r}}\widehat{L}(\bm{W}^{(t)})\|_{2}^{2}$
$\displaystyle\geq\Omega\left(\frac{1}{m}\right)\left((\alpha+\tilde{O}(\sigma))(1-\hat{\mu})\widehat{\mathcal{L}}^{(t)}(\alpha)\right.$
$\displaystyle\left.+\frac{\tilde{\Omega}(\sigma\sqrt{d})}{N}\sum_{i\in\mathcal{Z}_{2}}\widehat{\mathcal{L}}^{(t)}(\Xi_{i}^{(t)})-(1-\hat{\mu})\tilde{O}(\sigma)\widehat{\mathcal{L}}^{(t)}(\alpha)\right)^{2}$
$\displaystyle\geq\tilde{\Omega}(1)\left((1-\hat{\mu})\widehat{\mathcal{L}}^{(t)}(\alpha)+\frac{1}{N}\sum_{i\in\mathcal{Z}_{2}}\widehat{\mathcal{L}}^{(t)}(\Xi_{i}^{(t)})\right)^{2},$
(183)

Finally, we use Lemma I.13 and lower bound (183) by
$\widehat{L}(\bm{W}^{(t)})^{2}$. This gives the aimed result.

∎

We now present auxiliary lemmas that link the gradient terms with their
corresponding loss.

######  Lemma I.10.

Let $t\in[T_{1},T].$ Run GD for $t$ iterations. Then, we have:

$\displaystyle\sum_{r=1}^{m}\widehat{\ell}^{(t)}(\alpha)\alpha^{2}(c_{r}^{(t)})^{2}\geq\tilde{\Omega}(1)\widehat{\mathcal{L}}^{(t)}(\alpha).$

###### Proof of Lemma I.10.

In order to bound
$\sum_{r=1}^{m}\widehat{\ell}^{(t)}(\alpha)\alpha^{2}(c_{r}^{(t)})^{2}$, we
apply Lemma K.20. We first verify that the conditions of the lemma are met.
From Lemma 5.1 we know that for $t\in[T_{0},T]$, we have
$c^{(t)}\geq\tilde{\Omega}(1/\alpha)$. Along with D.1, this implies that

$\displaystyle\tilde{\Omega}(1)\leq\tilde{\Omega}(1)-m\tilde{O}(\alpha\sigma_{0})\leq\sum_{r=1}^{m}\alpha
c_{r}^{(t)}\leq\tilde{O}(\alpha)m\leq\tilde{O}(1).$ (184)

Therefore, we can apply Lemma K.20 and get the lower bound:

$\displaystyle\sum_{r=1}^{m}\widehat{\ell}^{(t)}(\alpha)(\alpha
c_{r}^{(t)})^{2}\geq\frac{0.05e^{-m\tilde{O}(\sigma_{0})}}{\tilde{O}(1)\left(1+\frac{m^{2}\tilde{O}(\sigma^{2}\sigma_{0}^{2}d)}{\tilde{\Omega}(1)^{2}}\right)}\log\left(1+e^{-\sum_{r=1}^{m}(\alpha
c_{r}^{(t)})^{3}}\right)\geq\tilde{\Omega}(1)\widehat{\mathcal{L}}^{(t)}(\alpha).$
(185)

∎

######  Lemma I.11.

Let $t\in[T_{1},T].$ Run GD for $t$ iterations. Then, we have:

$\displaystyle\frac{1}{N}\sum_{i\in\mathcal{Z}_{1}}\sum_{r=1}^{m}\sum_{j\neq
P(\bm{X}_{i})}\ell_{i}^{(t)}\left((\alpha^{2}(c_{r}^{(t)})^{2}+(\Xi_{i,j,r}^{(t)})^{2}\right)$
$\displaystyle\leq\tilde{O}(1)(1-\hat{\mu})\widehat{\mathcal{L}}^{(t)}(\alpha).$

###### Proof of Lemma I.11.

We again verify that the conditions of Lemma K.20 are met. By using D.1, D.2
and Lemma 5.1, we have:

$\displaystyle\sum_{r=1}^{m}\alpha c_{r}^{(t)}+\sum_{r=1}^{m}\sum_{j\neq
P(\bm{X}_{i})}y_{i}\Xi_{i,j,r}^{(t)}$ $\displaystyle\leq
m\tilde{O}(\alpha)+mP\tilde{O}(\sigma\sigma_{0}\sqrt{d})\leq\tilde{O}(1),$
(186) $\displaystyle\sum_{r=1}^{m}\alpha c_{r}^{(t)}+\sum_{r=1}^{m}\sum_{j\neq
P(\bm{X}_{i})}y_{i}\Xi_{i,j,r}^{(t)}$
$\displaystyle\geq\tilde{\Omega}(1)-m\tilde{O}(\alpha\sigma_{0})\geq\tilde{\Omega}(1).$

By applying Lemma K.20, we have:

$\displaystyle\frac{1}{N}\sum_{i\in\mathcal{Z}_{1}}\sum_{r=1}^{m}\sum_{j\neq
P(\bm{X}_{i})}\ell_{i}^{(t)}\left((\alpha^{2}(c_{r}^{(t)})^{2}+(\Xi_{i,j,r}^{(t)})^{2}\right)$
$\displaystyle\leq\frac{me^{m\tilde{O}(\sigma_{0})}}{\tilde{\Omega}(1)N}\sum_{i\in\mathcal{Z}_{1}}\log\left(1+\exp\left(-\sum_{r=1}^{m}\alpha^{3}(c_{r}^{(t)})^{3}-\Xi_{i}^{(t)}\right)\right)$
$\displaystyle\leq\frac{\tilde{O}(1)}{N}\sum_{i\in\mathcal{Z}_{1}}\log\left(1+\exp\left(-\sum_{r=1}^{m}\alpha^{3}(c_{r}^{(t)})^{3}-\Xi_{i}^{(t)}\right)\right).$
(187)

Lastly, we want to link the loss term in (187) with
$\widehat{\mathcal{L}}^{(t)}(\alpha)$. By applying D.1 and Lemma K.24 in
(187), we finally get:

$\displaystyle\frac{1}{N}\sum_{i\in\mathcal{Z}_{1}}\sum_{r=1}^{m}\sum_{j\neq
P(\bm{X}_{i})}\ell_{i}^{(t)}\left((\alpha^{2}(c_{r}^{(t)})^{2}+(\Xi_{i,j,r}^{(t)})^{2}\right)$
$\displaystyle\leq(1-\hat{\mu})(1+e^{\tilde{O}((\sigma\sigma_{0}\sqrt{d})^{3})})\widehat{\mathcal{L}}^{(t)}(\alpha)$
(188) $\displaystyle\leq(1-\hat{\mu})\widehat{\mathcal{L}}^{(t)}(\alpha).$

Combining (187) and (188) yields the aimed result. ∎

######  Lemma I.12.

Let $t\in[T_{1},T].$ Run GD for $t$ iterations. Then, we have:

$\displaystyle\frac{1}{N}\sum_{i\in\mathcal{Z}_{2}}\sum_{r=1}^{m}\sum_{j\neq
P(\bm{X}_{i})}\ell_{i}^{(t)}(\Xi_{i,j,r}^{(t)})^{2}$
$\displaystyle\geq\frac{\tilde{\Omega}(1)}{N}\sum_{i\in\mathcal{Z}_{2}}\widehat{\mathcal{L}}^{(t)}(\Xi_{i}^{(t)}).$

###### Proof of Lemma I.12.

We again verify that the conditions of Lemma K.20 are met. Using D.1, D.2 and
Lemma 5.4, we have:

$\displaystyle\sum_{r=1}^{m}\beta c_{r}^{(t)}+\sum_{r=1}^{m}\sum_{j\neq
P(\bm{X}_{i})}y_{i}\Xi_{i,j,r}^{(t)}\leq
m\tilde{O}(\beta)+mP\tilde{O}(1)\leq\tilde{O}(1)$ (189)
$\displaystyle\sum_{r=1}^{m}\beta c_{r}^{(t)}+\sum_{r=1}^{m}\sum_{j\neq
P(\bm{X}_{i})}y_{i}\Xi_{i,j,r}^{(t)}\geq\tilde{\Omega}(1)-m\tilde{O}(\sigma_{0})-mP\tilde{O}(\sigma_{0}\sigma\sqrt{d})\geq\tilde{\Omega}(1).$

By applying Lemma K.20, we have:

$\displaystyle\frac{1}{N}\sum_{i\in\mathcal{Z}_{2}}\sum_{r=1}^{m}\sum_{j\neq
P(\bm{X}_{i})}\ell_{i}^{(t)}(\Xi_{i,j,r}^{(t)})^{2}$ (190) $\displaystyle\geq$
$\displaystyle\frac{0.05e^{-m\tilde{O}(\sigma\sigma_{0}\sqrt{d})}}{N\tilde{O}(1)\left(1+\frac{m^{2}(\sigma\sigma_{0}\sqrt{d})^{2}}{\tilde{\Omega}(1)}\right)}\sum_{i\in\mathcal{Z}_{2}}\log\left(1+\exp\left(-\sum_{r=1}^{m}\beta^{3}(c_{r}^{(t)})^{3}-\Xi_{i}^{(t)}\right)\right)$
$\displaystyle\geq$
$\displaystyle\frac{\tilde{\Omega}(1)}{N}\sum_{i\in\mathcal{Z}_{2}}\log\left(1+\exp\left(-\sum_{r=1}^{m}\beta^{3}(c_{r}^{(t)})^{3}-\Xi_{i}^{(t)}\right)\right).$

Lastly, we want to link the loss term in (LABEL:eq:neknfce) with
$\widehat{\mathcal{L}}^{(t)}(\Xi_{i}^{(t)})$. By applying D.1 and Lemma K.24
in (LABEL:eq:neknfce), we finally get:

$\displaystyle\frac{\tilde{\Omega}(1)}{N}\sum_{i\in\mathcal{Z}_{2}}\sum_{r=1}^{m}\sum_{j\neq
P(\bm{X}_{i})}\ell_{i}^{(t)}(\Xi_{i,j,r}^{(t)})^{2}$
$\displaystyle\geq\frac{\tilde{\Omega}(1)e^{-m\tilde{O}(\beta^{3})}}{N}\sum_{i\in\mathcal{Z}_{2}}\widehat{\mathcal{L}}^{(t)}(\Xi_{i}^{(t)})$
(191)
$\displaystyle\geq\frac{\tilde{\Omega}(1)}{N}\sum_{i\in\mathcal{Z}_{2}}\widehat{\mathcal{L}}^{(t)}(\Xi_{i}^{(t)}).$

Combining (LABEL:eq:neknfce) and (191) yields the aimed result. ∎

######  Lemma I.13.

Let $t\in[0,T]$ Run GD for for $t$ iterations. Then, we have:

$\displaystyle(1-\hat{\mu})\widehat{\mathcal{L}}^{(t)}(\alpha)+\frac{1}{N}\sum_{i\in\mathcal{Z}_{2}}\widehat{\mathcal{L}}^{(t)}(\Xi_{i}^{(t)})\geq\Theta(1)\widehat{L}(\bm{W}^{(t)}).$
(192)

###### Proof of Lemma I.13.

we need to lower bound $\widehat{\mathcal{L}}^{(t)}(\alpha)$. By successively
applying Lemma K.24 and D.1, we obtain:

$\displaystyle(1-\hat{\mu})\widehat{\mathcal{L}}^{(t)}(\alpha)$
$\displaystyle=\frac{1}{N}\sum_{i\in\mathcal{Z}_{1}}\frac{1+e^{-\Xi_{i}^{(t)}}}{1+e^{-\Xi_{i}^{(t)}}}\log\left(1+\exp\left(-\sum_{r=1}^{m}(\alpha
c_{r}^{(t)})^{3}\right)\right)$
$\displaystyle\geq\frac{1}{N}\sum_{i\in\mathcal{Z}_{1}}\frac{1}{1+e^{-\Xi_{i}^{(t)}}}\log\left(1+\exp\left(-\sum_{r=1}^{m}(\alpha
c_{r}^{(t)})^{3}\right)-\Xi_{i}^{(t)}\right)$
$\displaystyle\geq\frac{\widehat{L}_{\mathcal{Z}_{1}}(\bm{W}^{(t)})}{1+e^{\tilde{O}((\sigma\sigma_{0}\sqrt{d})^{3})}}$
$\displaystyle\geq\Theta(1)\widehat{L}_{\mathcal{Z}_{1}}(\bm{W}^{(t)}).$ (193)

By successively applying Lemma K.24 and D.1, we obtain:

$\displaystyle\frac{1}{N}\sum_{i\in\mathcal{Z}_{2}}\widehat{\mathcal{L}}^{(t)}(\Xi_{i}^{(t)})$
$\displaystyle=\frac{1}{N}\sum_{i\in\mathcal{Z}_{2}}\frac{1+e^{-\sum_{r=1}^{m}(\beta
c_{r}^{(t)})^{3}}}{1+e^{-\sum_{r=1}^{m}(\beta
c_{r}^{(t)})^{3}}}\log\left(1+\exp\left(-\Xi_{i}^{(t)}\right)\right)$
$\displaystyle\geq\frac{1}{N}\sum_{i\in\mathcal{Z}_{2}}\frac{1}{1+e^{-\sum_{r=1}^{m}(\beta
c_{r}^{(t)})^{3}}}\log\left(1+\exp\left(-\sum_{r=1}^{m}(\beta
c_{r}^{(t)})^{3}\right)-\Xi_{i}^{(t)}\right)$
$\displaystyle\geq\frac{\widehat{L}_{\mathcal{Z}_{2}}(\bm{W}^{(t)})}{1+e^{\tilde{O}((\beta\sigma_{0})^{3})}}$
$\displaystyle\geq\Theta(1)\widehat{L}_{\mathcal{Z}_{2}}(\bm{W}^{(t)}).$ (194)

Combining (193) and (194) yields the aimed result.

∎

Lastly, to obtain Lemma I.8, we need to bound $G_{r}^{(t)}$ which is given by
the next lemma.

######  Lemma I.14 (Gradient on the normalized noise).

For $r\in[m]$, the gradient of the loss $\widehat{L}(\bm{W}^{(t)})$ projected
on the normalized noise $\textstyle\chi$ satisfies with probability $1-o(1)$
for $r\in[m]$:

$\displaystyle-\mathrm{G}_{r}^{(t)}\geq\frac{\tilde{\Theta}(\sigma\sqrt{d})}{N}\sum_{i\in\mathcal{Z}_{2}}\ell_{i}^{(t)}\sum_{j\neq
P(\bm{X}_{i})}(\Xi_{i,j,r}^{(t)})^{2}-\frac{\tilde{O}(\sigma)}{N}\sum_{i\in\mathcal{Z}_{1}}\sum_{j\neq
P(\bm{X}_{i})}\ell_{i}^{(t)}(\Xi_{i,j,r}^{(t)})^{2}.$

###### Proof of Lemma I.14.

Projecting the gradient (given by Lemma E.1) on $\textstyle\chi$ yields:

$\begin{split}-\mathrm{G}_{r}^{(t)}&=\frac{3}{N^{2}}\sum_{i\in\mathcal{Z}_{2}}\sum_{j\neq
P(\bm{X}_{i})}\ell_{i}^{(t)}(\Xi_{i,j,r}^{(t)})^{2}\frac{\|\bm{X}_{i}[j]\|_{2}^{2}}{\|\frac{1}{N}\sum_{b\in\mathcal{Z}_{2}}\sum_{l\neq
P(\bm{X}_{i})}\bm{X}_{b}[l]\|_{2}}\\\
&+\frac{3}{N^{2}}\sum_{i\in\mathcal{Z}_{2}}\ell_{i}^{(t)}\sum_{j\neq
P(\bm{X}_{i})}\sum_{\begin{subarray}{c}k\neq P(\bm{X}_{i})\\\ k\neq
j\end{subarray}}(\Xi_{i,k,r}^{(t)})^{2}\left\langle\bm{X}_{i}[k],\frac{\bm{X}_{i}[j]}{\|\frac{1}{N}\sum_{b\in\mathcal{Z}_{2}}\sum_{l\neq
P(\bm{X}_{i})}\bm{X}_{b}[l]\|_{2}}\right\rangle\\\
&+\frac{3}{N^{2}}\sum_{i\in\mathcal{Z}_{2}}\sum_{\begin{subarray}{c}a\in\mathcal{Z}_{2}\\\
a\neq i\end{subarray}}\ell_{a}^{(t)}\sum_{k\neq
P(\bm{X}_{a})}(\Xi_{a,k,r}^{(t)})^{2}\sum_{j\neq
P(\bm{X}_{i})}\left\langle\bm{X}_{a}[k],\frac{\bm{X}_{i}[j]}{\|\frac{1}{N}\sum_{b\in\mathcal{Z}_{2}}\sum_{l\neq
P(\bm{X}_{i})}\bm{X}_{b}[l]\|_{2}}\right\rangle\\\
&+\frac{3}{N}\sum_{a\in\mathcal{Z}_{1}}\sum_{k\neq
P(\bm{X}_{a})}\ell_{a}^{(t)}(\Xi_{a,k,r}^{(t)})^{2}\left\langle\bm{X}_{a}[k],\frac{\frac{1}{N}\sum_{i\in\mathcal{Z}_{2}}\sum_{j\neq
P(\bm{X}_{i})}\bm{X}_{i}[j]}{\|\frac{1}{N}\sum_{b\in\mathcal{Z}_{2}}\sum_{l\neq
P(\bm{X}_{i})}\bm{X}_{b}[l]\|_{2}}\right\rangle.\end{split}$ (195)

We further bound (195) as:

$\begin{split}&\left|\mathrm{G}_{r}^{(t)}+\frac{3}{N^{2}}\sum_{i\in\mathcal{Z}_{2}}\sum_{j\neq
P(\bm{X}_{i})}\ell_{i}^{(t)}(\Xi_{i,j,r}^{(t)})^{2}\frac{\|\bm{X}_{i}[j]\|_{2}^{2}}{\|\frac{1}{N}\sum_{b\in\mathcal{Z}_{2}}\sum_{l\neq
P(\bm{X}_{i})}\bm{X}_{b}[l]\|_{2}}\right.\\\
&\left.-\frac{3}{N^{2}}\sum_{i\in\mathcal{Z}_{2}}\sum_{a\in\mathcal{Z}_{2}}\ell_{a}^{(t)}\sum_{j\neq
P(\bm{X}_{i})}\sum_{k\neq
P(\bm{X}_{a})}(\Xi_{a,k,r}^{(t)})^{2}\left|\left\langle\bm{X}_{a}[k],\frac{\bm{X}_{i}[j]}{\|\frac{1}{N}\sum_{b\in\mathcal{Z}_{2}}\sum_{l\neq
P(\bm{X}_{i})}\bm{X}_{b}[l]\|_{2}}\right\rangle\right|\right|\\\
&\leq\frac{3}{N}\sum_{a\in\mathcal{Z}_{1}}\sum_{k\neq
P(\bm{X}_{a})}\ell_{a}^{(t)}(\Xi_{a,k,r}^{(t)})^{2}\left|\left\langle\bm{X}_{a}[k],\frac{\frac{1}{N}\sum_{i\in\mathcal{Z}_{2}}\sum_{j\neq
P(\bm{X}_{i})}\bm{X}_{i}[j]}{\|\frac{1}{N}\sum_{b\in\mathcal{Z}_{2}}\sum_{l\neq
P(\bm{X}_{i})}\bm{X}_{b}[l]\|_{2}}\right\rangle\right|.\end{split}$ (196)

Since $\frac{\frac{1}{N}\sum_{i\in\mathcal{Z}_{2}}\sum_{j\neq
P(\bm{X}_{i})}\bm{X}_{i}[j]}{\|\frac{1}{N}\sum_{b\in\mathcal{Z}_{2}}\sum_{l\neq
P(\bm{X}_{i})}\bm{X}_{b}[l]\|_{2}}$ is a unit Gaussian vector, using Lemma
K.8, we bound the right-hand side of (LABEL:eq:Grbd2) with probability
$1-o(1)$, as:

$\begin{split}&\left|\mathrm{G}_{r}^{(t)}+\frac{3}{N^{2}}\sum_{i\in\mathcal{Z}_{2}}\sum_{j\neq
P(\bm{X}_{i})}\ell_{i}^{(t)}(\Xi_{i,j,r}^{(t)})^{2}\frac{\|\bm{X}_{i}[j]\|_{2}^{2}}{\|\frac{1}{N}\sum_{b\in\mathcal{Z}_{2}}\sum_{l\neq
P(\bm{X}_{i})}\bm{X}_{b}[l]\|_{2}}\right.\\\
&\left.-\frac{3}{N^{2}}\sum_{i\in\mathcal{Z}_{2}}\sum_{a\in\mathcal{Z}_{2}}\ell_{a}^{(t)}\sum_{j\neq
P(\bm{X}_{i})}\sum_{k\neq
P(\bm{X}_{a})}(\Xi_{a,k,r}^{(t)})^{2}\left|\left\langle\bm{X}_{a}[k],\frac{\bm{X}_{i}[j]}{\|\frac{1}{N}\sum_{b\in\mathcal{Z}_{2}}\sum_{l\neq
P(\bm{X}_{i})}\bm{X}_{b}[l]\|_{2}}\right\rangle\right|\right|\\\
&\leq\frac{\sigma}{N}\sum_{a\in\mathcal{Z}_{1}}\sum_{k\neq
P(\bm{X}_{a})}\ell_{a}^{(t)}(\Xi_{a,k,r}^{(t)})^{2}.\end{split}$ (197)

Now, using Lemma Lemma K.10 , we can further lower bound the left-hand side of
(LABEL:eq:Grbd3) as:

$\begin{split}&\left|\mathrm{G}_{r}^{(t)}+\frac{3}{N^{2}}\sum_{i\in\mathcal{Z}_{2}}\sum_{j\neq
P(\bm{X}_{i})}\ell_{i}^{(t)}(\Xi_{i,j,r}^{(t)})^{2}\frac{\|\bm{X}_{i}[j]\|_{2}^{2}}{\|\frac{1}{N}\sum_{b\in\mathcal{Z}_{2}}\sum_{l\neq
P(\bm{X}_{i})}\bm{X}_{b}[l]\|_{2}}\right.\\\
&\left.-\frac{\tilde{\Theta}(P)}{\sqrt{d}N^{2}}\sum_{a\in\mathcal{Z}_{2}}\ell_{a}^{(t)}\sum_{k\neq
P(\bm{X}_{a})}(\Xi_{a,k,r}^{(t)})^{2}\frac{\|\bm{X}_{a}[k]\|_{2}^{2}}{\|\frac{1}{N}\sum_{b\in\mathcal{Z}_{2}}\sum_{l\neq
P(\bm{X}_{i})}\bm{X}_{b}[l]\|_{2}}\right|\\\
&\leq\frac{\sigma}{N}\sum_{a\in\mathcal{Z}_{1}}\sum_{k\neq
P(\bm{X}_{a})}\ell_{a}^{(t)}(\Xi_{a,k,r}^{(t)})^{2}.\end{split}$ (198)

Rewriting (LABEL:eq:Grbd4) yields:

$\begin{split}&\left|\mathrm{G}_{r}^{(t)}+\frac{\Theta(1)}{N^{2}}\sum_{i\in\mathcal{Z}_{2}}\sum_{j\neq
P(\bm{X}_{i})}\ell_{i}^{(t)}(\Xi_{i,j,r}^{(t)})^{2}\frac{\|\bm{X}_{i}[j]\|_{2}^{2}}{\|\frac{1}{N}\sum_{b\in\mathcal{Z}_{2}}\sum_{l\neq
P(\bm{X}_{i})}\bm{X}_{b}[l]\|_{2}}\right|\\\
&\leq\frac{\sigma}{N}\sum_{a\in\mathcal{Z}_{1}}\sum_{k\neq
P(\bm{X}_{a})}\ell_{a}^{(t)}(\Xi_{a,k,r}^{(t)})^{2}.\end{split}$ (199)

Remark that $\frac{1}{N}\sum_{b\in\mathcal{Z}_{2}}\sum_{l\neq
P(\bm{X}_{i})}\bm{X}_{b}[l]\sim\mathcal{N}(0,\frac{\hat{\mu}P}{N}\sigma^{2})$.
By applying Lemma K.9, we have:

$\displaystyle\frac{1}{N}\frac{\|\bm{X}_{i}[j]\|_{2}^{2}}{\|\frac{1}{N}\sum_{b\in\mathcal{Z}_{2}}\sum_{l\neq
P(\bm{X}_{i})}\bm{X}_{b}[l]\|_{2}}$
$\displaystyle=\frac{1}{N}\tilde{\Theta}\left(\sigma\sqrt{\frac{dN}{\hat{\mu}P}}\right)=\tilde{\Theta}\left(\sigma\sqrt{\frac{d}{\hat{\mu}NP}}\right)=\tilde{\Theta}(\sigma\sqrt{d}),$
(200)

where we used $P=\tilde{\Theta}(1)$ and $\hat{\mu}N=\tilde{\Theta}(1)$ in the
last equality of (200). Plugging this in (LABEL:eq:Grbd4vfefvr) yields the
desired result. ∎

##  Appendix J Auxiliary lemmas for GD+M

This section presents the auxiliary lemmas needed in Appendix G.

###  J.1 Rewriting derivatives

######  Lemma J.1 (Derivatives for GD+M).

Let $i\in\mathcal{Z}_{k}$, for $k\in\\{1,2\\}.$ Then,
$\ell_{i}^{(t)}=\Theta(1)\widehat{\ell}^{(t)}(\theta)$.

###### Proof.

Let $i\in[N].$ Using D.4, we have:

$\displaystyle\ell_{i}^{(t)}$
$\displaystyle=\mathrm{sigmoid}\left(-\theta^{3}\sum_{s=1}^{m}(c_{s}^{(t)})^{3}-\sum_{s=1}^{m}\sum_{j\neq
P(\bm{X}_{i})}(\Xi_{i,j,s}^{(t)})^{3}\right).$

Therefore, we deduce that:

$\displaystyle
e^{-\tilde{O}((\sigma\sigma_{0}\sqrt{d})^{3})}\widehat{\ell}^{(t)}(\theta)\leq\ell_{i}^{(t)}\leq
e^{\tilde{O}((\sigma\sigma_{0}\sqrt{d})^{3})}\widehat{\ell}^{(t)}(\theta)$

which yields the aimed result. ∎

###  J.2 Signal lemmas

In this section, we present the auxiliary lemmas needed to prove D.5. We first
rewrite the (3) update to take into account the case where the signal
$c^{(\tau)}$ becomes large.

######  Lemma J.2 (Rewriting signal momentum).

For $t\in[T]$, the maximal signal momentum $\mathcal{G}^{(t)}$ is bounded as:

$\displaystyle\mathcal{G}^{(t+1)}$
$\displaystyle\leq\Theta(1-\gamma)\sum_{\tau=0}^{t}\gamma^{t-\tau}\left(\alpha\nu_{1}^{(\tau)}\min\\{\kappa,(\alpha
c^{(\tau)})^{2}\\}+\beta\nu_{2}^{(\tau)}\min\\{\kappa,(\beta
c^{(\tau)})^{2}\\}\right).$

###### Proof of Lemma J.2.

Let $t\in[T]$. Using the signal momentum given by Lemma G.1, we know that:

$\displaystyle\mathcal{G}^{(t+1)}$
$\displaystyle=\Theta(1-\gamma)\sum_{\tau=0}^{t}\gamma^{t-\tau}\left(\frac{\alpha}{N}\sum_{i\in\mathcal{Z}_{1}}(\alpha
c^{(\tau)})^{2}\ell_{i}^{(\tau)}+\frac{\beta}{N}\sum_{i=1}^{N}(\beta
c^{(\tau)})^{2}\ell_{i}^{(\tau)}\right).$ (201)

To obtain the desired result, we need to prove for $i\in\mathcal{Z}_{1}$:

$\displaystyle(\alpha c^{(t)})^{2}\ell_{i}^{(\tau)}$
$\displaystyle\leq\Theta(1)\min\\{\kappa,(\alpha
c^{(\tau)})^{2}\\}\ell_{i}^{(\tau)}.$ (202)

Indeed, we remark that:

$\displaystyle(\alpha c^{(\tau)})^{2}\ell_{i}^{(\tau)}$
$\displaystyle=\frac{\alpha^{2}(c^{(\tau)})^{2}}{1+\exp\left(\alpha^{3}\sum_{s=1}^{m}(c_{s}^{(\tau)})^{3}+\Xi_{i}^{(\tau)}\right)}.$
(203)

By using D.4 and D.5, (203) is bounded as:

$\displaystyle(\alpha c^{(\tau)})^{2}\ell_{i}^{(\tau)}$
$\displaystyle=\frac{\alpha^{3}(c^{(\tau)})^{2}}{1+\exp\left(\alpha^{2}(c^{(\tau)})^{3}+\alpha^{3}\sum_{s\neq
r_{\max}}(c_{s}^{(\tau)})^{3}+\Xi_{i}^{(\tau)}\right)}$
$\displaystyle\leq\frac{\alpha^{2}(c^{(\tau)})^{2}}{1+\exp\left(\alpha^{3}(c^{(\tau)})^{3}-\tilde{O}(m\alpha^{3}\sigma_{0}^{3})-\tilde{O}(mP(\sigma\sigma_{0}\sqrt{d})^{3})\right)}$
$\displaystyle=\frac{\Theta(1)(\alpha c^{(\tau)})^{2}}{1+\exp((\alpha
c^{(\tau)})^{3})}.$ (204)

Using Remark 1, the sigmoid term in (J.2) becomes small when $\alpha
c^{(\tau)}\geq\kappa^{1/3}$. To summarize, we have:

$\displaystyle(\alpha c^{(\tau)})^{2}\ell_{i}^{(\tau)}$
$\displaystyle=\begin{cases}0&\text{if }\alpha c^{(\tau)}\geq\kappa^{1/3}\\\
(\alpha c^{(\tau)})^{2}\ell_{i}^{(\tau)}&\text{otherwise}\end{cases}.$ (205)

(205) therefore implies $(\alpha
c^{(t)})^{2}\ell_{i}^{(t)}\leq\Theta(1)\min\\{\kappa^{2/3},(\alpha
c^{(t)})^{2}\\}\ell_{i}^{(t)}$ which implies (202).

A similar reasoning implies for $i\in\mathcal{Z}_{2}$:

$\displaystyle(\beta c^{(t)})^{2}\ell_{i}^{(\tau)}$
$\displaystyle\leq\Theta(1)\min\\{\kappa,\beta^{2}(c^{(t)})^{2}\\}\ell_{i}^{(\tau)}.$
(206)

Plugging (202) and (206) in (201) yields the aimed result. ∎

We proved in Lemma 6.1 that after $\mathcal{T}_{0}$ iterations, the signal
$c^{(t)}\geq\tilde{\Omega}(1/\alpha)$ which makes $\nu_{1}^{(t)}$ small.
Besides, in Lemma 6.3, we show that after $\mathcal{T}_{1}$ iterations, the
signal $c^{(t)}\geq\tilde{\Omega}(1/\beta)$ which makes $\nu_{2}^{(t)}$ small.
We use these two facts to bound the sum over time of signal momentum.

######  Lemma J.3 (Sum of signal momentum at late stages).

For $t\in[\mathcal{T}_{1},T)$, the sum of maximal signal momentum is bounded
as:

$\displaystyle\sum_{s=\mathcal{T}_{1}}^{t}|\mathcal{G}^{(s+1)}|\leq\tilde{O}(\alpha\mathcal{T}_{0})+\tilde{O}(\hat{\mu}\beta\mathcal{T}_{1})+\frac{\tilde{O}(1)}{\eta}.$
(207)

###### Proof of Lemma J.3.

Let $s\in[\mathcal{T}_{1},T]$. From Lemma J.2, the signal momentum is bounded
as:

$\displaystyle|\mathcal{G}^{(s+1)}|$
$\displaystyle\leq\Theta(1-\gamma)\sum_{\tau=0}^{\mathcal{T}_{0}-1}\gamma^{s-\tau}\alpha\nu_{1}^{(\tau)}\min\\{\kappa,(\alpha
c^{(\tau)})^{2}\\}$ (208)
$\displaystyle+\Theta(1-\gamma)\sum_{\tau=\mathcal{T}_{0}}^{s}\gamma^{s-\tau}\alpha\nu_{1}^{(\tau)}\min\\{\kappa,(\alpha
c^{(\tau)})^{2}\\}$
$\displaystyle+\Theta(1-\gamma)\sum_{\tau=0}^{\mathcal{T}_{1}-1}\gamma^{s-\tau}\beta\nu_{2}^{(\tau)}\min\\{\kappa,(\beta
c^{(\tau)})^{2}\\}$
$\displaystyle+\Theta(1-\gamma)\sum_{\tau=\mathcal{T}_{1}}^{s}\gamma^{s-\tau}\beta\nu_{2}^{(\tau)}\min\\{\kappa,(\beta
c^{(\tau)})^{2}\\}.$

We know that for $\tau\geq\mathcal{T}_{0},$
$c^{(\tau)}\geq\tilde{\Omega}(1/\alpha)$ and for $\tau\geq\mathcal{T}_{1},$
$c^{(\tau)}\geq\tilde{\Omega}(1/\beta)$. Plugging these two facts and using
$\nu_{1}^{(\tau)}\leq 1-\hat{\mu}$ and $\nu_{2}^{(\tau)}\leq\hat{\mu}$ in
(208) leads to:

$\displaystyle\mathcal{G}^{(s+1)}$
$\displaystyle\leq(1-\hat{\mu})\alpha\tilde{O}(1-\gamma)\sum_{\tau=0}^{\mathcal{T}_{0}-1}\gamma^{s-\tau}+\alpha\tilde{O}(1-\gamma)\sum_{\tau=\mathcal{T}_{0}}^{s}\gamma^{s-\tau}\nu_{1}^{(\tau)}$
(209)
$\displaystyle+\hat{\mu}\beta\tilde{O}(1-\gamma)\sum_{\tau=0}^{\mathcal{T}_{1}-1}\gamma^{s-\tau}+\beta\tilde{O}(1-\gamma)\sum_{\tau=\mathcal{T}_{1}}^{s}\gamma^{s-\tau}\nu_{2}^{(\tau)}$

For $\tau\in[\mathcal{T}_{0}-1]$, we have
$\gamma^{s-\tau}\leq\gamma^{s-\mathcal{T}_{0}+1}$ and for
$\tau\in[\mathcal{T}_{1}-1]$,
$\gamma^{s-\tau}\leq\gamma^{s-\mathcal{T}_{1}+1}$. From Lemma J.8 and Lemma
6.4, we can bound $\nu_{1}^{(\tau)}$ and $\nu_{2}^{(\tau)}$. Therefore, (209)
is further bounded as:

$\displaystyle\mathcal{G}^{(s+1)}$
$\displaystyle\leq(1-\hat{\mu})\mathcal{T}_{0}\alpha\tilde{O}(1-\gamma)\gamma^{s-\mathcal{T}_{0}+1}+\frac{\tilde{O}(1-\gamma)}{\eta}\sum_{\tau=1}^{s-\mathcal{T}_{0}+1}\frac{\gamma^{s-\mathcal{T}_{0}+1-\tau}}{\tau}$
(210)
$\displaystyle+\hat{\mu}\mathcal{T}_{1}\beta\tilde{O}(1-\gamma)\gamma^{s-\mathcal{T}_{1}+1}+\frac{\tilde{O}(1-\gamma)}{\eta}\sum_{\tau=1}^{s-\mathcal{T}_{1}+1}\frac{\gamma^{s-\mathcal{T}_{1}+1-\tau}}{\tau}$

We now use Lemma K.25 to bound the sum terms in (210). We have:

$\displaystyle\mathcal{G}^{(s+1)}$
$\displaystyle\leq(1-\hat{\mu})\mathcal{T}_{0}\alpha\tilde{O}(1-\gamma)\gamma^{s-\mathcal{T}_{0}+1}+\hat{\mu}\mathcal{T}_{1}\beta\tilde{O}(1-\gamma)\gamma^{s-\mathcal{T}_{1}+1}$
(211)
$\displaystyle+\frac{\tilde{O}(1-\gamma)}{\eta}\left(\gamma^{s-\mathcal{T}_{0}}+\gamma^{(s-\mathcal{T}_{0}+1)/2}\log\left(\frac{s-\mathcal{T}_{0}+1}{2}\right)+\frac{1}{1-\gamma}\frac{2}{s-\mathcal{T}_{0}+1}\right)$
$\displaystyle+\frac{\tilde{O}(1-\gamma)}{\eta}\left(\gamma^{s-\mathcal{T}_{1}}+\gamma^{(s-\mathcal{T}_{1}+1)/2}\log\left(\frac{s-\mathcal{T}_{1}+1}{2}\right)+\frac{1}{1-\gamma}\frac{2}{s-\mathcal{T}_{1}+1}\right).$

We now sum (211) for $s=\mathcal{T}_{1},\dots,t$. Using the geometric sum
inequality $\sum_{s}\gamma^{s}\leq 1/(1-\gamma)$ and obtain:

$\displaystyle\sum_{s=\mathcal{T}_{1}}^{t}\mathcal{G}^{(s+1)}$
$\displaystyle\leq\tilde{O}(\mathcal{T}_{0}\alpha)+\tilde{O}(\hat{\mu}\beta\mathcal{T}_{1})$
(212)
$\displaystyle+\frac{\tilde{O}(1)}{\eta}\left(1+(1-\gamma)\log(t)\sum_{s=\mathcal{T}_{1}}^{t}(\sqrt{\gamma})^{s-\mathcal{T}_{0}+1}+\sum_{s=\mathcal{T}_{1}}^{t}\frac{2}{s-\mathcal{T}_{0}+1}\right)$
$\displaystyle+\frac{\tilde{O}(1)}{\eta}\left(1+(1-\gamma)\log(t)\sum_{s=\mathcal{T}_{1}}^{t}(\sqrt{\gamma})^{s-\mathcal{T}_{1}+1}+\sum_{s=\mathcal{T}_{1}}^{t}\frac{2}{s-\mathcal{T}_{1}+1}\right)$

We plug $\sum_{s}\sqrt{\gamma}^{s}\leq 1/(1-\sqrt{\gamma})$ and
$\sum_{s=1}^{t-\mathcal{T}_{1}+1}1/s\leq\log(t)+1$ in (212). This yields the
desired result. ∎

###  J.3 Noise lemmas

In this section, we present the technical lemmas to prove Lemma 6.5.

######  Lemma J.4 (Bound on noise momentum).

Run GD+M on the loss function $\widehat{L}(\bm{W}).$ Let $i\in[N]$,
$j\in[P]\backslash\\{P(\bm{X}_{i})\\}$. At a time $t$, the noise momentum is
bounded with probability $1-o(1)$ as:

$\displaystyle\left|-G_{i,j,r}^{(t+1)}+\gamma
G_{i,j,r}^{(t)}\right|\leq(1-\gamma)\tilde{O}(\sigma^{4}\sigma_{0}^{2}d^{2})\nu^{(t)}.$

###### Proof of Lemma J.4.

Let $i\in[N]$ and $j\in[P]\backslash\\{P(\bm{X}_{i})\\}$. Combining the (4)
update rule and Lemma E.3 to get the noise gradient
$\texttt{G}_{i,j,r}^{(t)}$, we obtain

$\displaystyle\left|-G_{i,j,r}^{(t+1)}+\gamma G_{i,j,r}^{(t)}\right|$ (213)
$\displaystyle\leq\frac{3(1-\gamma)}{N}\ell_{i}^{(t)}(\Xi_{i,j,r}^{(t)})^{2}\|\bm{X}_{i}[j]\|_{2}^{2}+\left|\frac{3(1-\gamma)}{N}\sum_{a=1}^{N}\ell_{a}^{(t)}\sum_{k\neq
P(\bm{X}_{a})}(\Xi_{a,k,r}^{(t)})^{2}\langle\bm{X}_{a}[k],\bm{X}_{i}[j]\rangle\right|.$

Using Lemma K.5 and Lemma K.7, (LABEL:eq:diffmoms1) becomes with probability
$1-o(1),$

$\displaystyle\left|-G_{i,j,r}^{(t+1)}+\gamma G_{i,j,r}^{(t)}\right|$ (214)
$\displaystyle\leq\frac{(1-\gamma)\tilde{\Theta}(\sigma^{2}d)}{N}\ell_{i}^{(t)}(\Xi_{i,j,r}^{(t)})^{2}+\frac{(1-\gamma)\tilde{\Theta}(\sigma^{2}\sqrt{d})}{N}\sum_{a=1}^{N}\ell_{a}^{(t)}\sum_{k\neq
P(\bm{X}_{a})}(\Xi_{a,k,r}^{(t)})^{2}.$

Using $\ell_{i}^{(t)}/N\leq\nu^{(t)},$ D.4, we upper bound the first term in
(LABEL:eq:diffmomvfeercs1) to get:

$\displaystyle\left|-G_{i,j,r}^{(t+1)}+\gamma G_{i,j,r}^{(t)}\right|$ (215)
$\displaystyle\leq(1-\gamma)\tilde{O}(\sigma^{4}\sigma_{0}^{2}d^{2})\nu^{(t)}+\frac{(1-\gamma)\tilde{\Theta}(\sigma^{2}\sqrt{d})}{N}\sum_{a=1}^{N}\ell_{a}^{(t)}\sum_{k\neq
P(\bm{X}_{a})}(\Xi_{a,k,r}^{(t)})^{2}.$

We upper bound the second term in (LABEL:eq:diffmoms2) by again using D.4:

$\displaystyle\left|-G_{i,j,r}^{(t+1)}+\gamma
G_{i,j,r}^{(t)}\right|\leq(1-\gamma)\left(\tilde{O}(\sigma^{4}\sigma_{0}^{2}d^{2})+\tilde{O}(P\sigma_{0}^{2}\sigma^{4}d^{3/2})\right)\nu^{(t)}.$
(216)

By using $P\leq\tilde{O}(1)$ and thus,
$\tilde{O}(P\sigma_{0}^{2}\sigma^{4}d^{3/2})\leq\tilde{O}(\sigma^{4}\sigma_{0}^{2}d^{2})$
in (LABEL:eq:Gdiffnoise), we obtain the desired result. ∎

######  Lemma J.5.

Let $t\in[T]$. The noise momentum is bounded as

$\displaystyle|G_{i,j,r}^{(t+1)}|\leq(1-\gamma)\tilde{O}(\sigma^{4}\sigma_{0}^{2}d^{2})\sum_{\tau=0}^{t}\gamma^{t-1-\tau}\nu^{(\tau)}.$

###### Proof of Lemma J.5.

Let $\tau\in[T].$ From Lemma J.4, we know that:

$\displaystyle|G_{i,j,r}^{(\tau+1)}|\leq|\gamma
G_{i,j,r}^{(\tau)}|+(1-\gamma)\tilde{O}(\sigma^{4}\sigma_{0}^{2}d^{2})\nu^{(\tau)}.$
(217)

We unravel the recursion (217) rule for $\tau=0,\dots,t$ and obtain:

$\displaystyle|G_{i,j,r}^{(t+1)}|$
$\displaystyle\leq(1-\gamma)\tilde{O}(\sigma^{4}\sigma_{0}^{2}d^{2})\sum_{\tau=0}^{t}\gamma^{t-\tau}\nu^{(\tau)}.$

∎

######  Lemma J.6 (Noise momentum at late stages).

For $t\in[\mathcal{T}_{1},T)$, the sum of noise momentum is bounded as:

$\displaystyle\sum_{s=\mathcal{T}_{1}}^{t}|G_{i,j,r}^{(s+1)}|\leq\tilde{O}(\sigma^{4}\sigma_{0}^{2}d^{2})\left(\mathcal{T}_{1}+\frac{1}{\eta\beta}\right).$

###### Proof of Lemma J.6.

Let $s\in[\mathcal{T}_{1},T)$. We first apply Lemma J.5 and obtain:

$\displaystyle|G_{i,j,r}^{(s+1)}|\leq(1-\gamma)\tilde{O}(\sigma^{4}\sigma_{0}^{2}d^{2})\left(\sum_{\tau=0}^{\mathcal{T}_{1}-1}\gamma^{s-\tau}\nu^{(\tau)}+\sum_{\tau=\mathcal{T}_{1}}^{t}\gamma^{s-\tau}\nu^{(\tau)}\right).$
(218)

Using the bound from Lemma 6.4, (218) becomes

$\displaystyle|G_{i,j,r}^{(s+1)}|\leq(1-\gamma)\tilde{O}(\sigma^{4}\sigma_{0}^{2}d^{2})\left(\sum_{\tau=0}^{\mathcal{T}_{1}-1}\gamma^{s-\tau}+\sum_{\tau=\mathcal{T}_{1}}^{s}\frac{\gamma^{s-\tau}}{\eta\beta(\tau-\mathcal{T}_{1}+1)}\right)$
(219)

For $\tau\in[0,\mathcal{T}_{1}-1]$, we have
$\gamma^{s-1-\tau}\leq\gamma^{s-\mathcal{T}_{1}+1}$. Plugging these two bounds
in (219) implies:

$\displaystyle|G_{i,j,r}^{(s+1)}|\leq(1-\gamma)\tilde{O}(\sigma^{4}\sigma_{0}^{2}d^{2})\left(\mathcal{T}_{1}\gamma^{s-\mathcal{T}_{1}+1}+\frac{1}{\eta\beta}\sum_{\tau=1}^{s-\mathcal{T}_{1}+1}\frac{\gamma^{s-\mathcal{T}_{1}+1-\tau}}{\tau}\right).$
(220)

We now use Lemma K.25 to bound the sum terms in (220). We have:

$\displaystyle|G_{i,j,r}^{(s+1)}|$ (221)
$\displaystyle\leq(1-\gamma)\tilde{O}(\sigma^{4}\sigma_{0}^{2}d^{2})\mathcal{T}_{1}\gamma^{s-\mathcal{T}_{1}+1}$
$\displaystyle+\frac{1-\gamma}{\eta\beta}\tilde{O}(\sigma^{4}\sigma_{0}^{2}d^{2})\left(\gamma^{s-\mathcal{T}_{1}}+\gamma^{(s-\mathcal{T}_{1}+1)/2}\log\left(\frac{s-\mathcal{T}_{1}+1}{2}\right)+\frac{1}{1-\gamma}\frac{2}{s-\mathcal{T}_{1}+1}\right).$

We now sum (221) for $s=\mathcal{T}_{1},\dots,t$. Using the geometric sum
inequality $\sum_{s}\gamma^{s}\leq 1/(1-\gamma),$ we obtain:

$\displaystyle\sum_{s=\mathcal{T}_{1}}^{t}|G_{i,j,r}^{(s+1)}|\leq\tilde{O}(\sigma^{4}\sigma_{0}^{2}d^{2})\mathcal{T}_{1}+\frac{\tilde{O}(\sigma^{4}\sigma_{0}^{2}d^{2})}{\eta\beta}\left(\log\left(t\right)+\sum_{s=\mathcal{T}_{1}}^{t}\frac{2}{s-\mathcal{T}_{1}+1}\right).$
(222)

We finally use the harmonic series inequality
$\sum_{s=1}^{t-\mathcal{T}_{1}}1/s\leq 1+\log(t)$ in (222) to obtain the
desired result. ∎

###  J.4 Convergence rate of the training loss using GD+M

In this section, we prove that when using GD+M, the training loss converges
sublinearly in our setting.

####  J.4.1 Convergence after learning $\mathcal{Z}_{1}$
$(t\in[\mathcal{T}_{0},T])$

######  Lemma J.7.

For $t\in[\mathcal{T}_{0},T]$ Using GD+M with learning rate $\eta$, the loss
sublinearly converges to zero as

$\displaystyle(1-\hat{\mu})\widehat{\mathcal{L}}^{(t)}(\alpha)\leq\tilde{O}\left(\frac{1}{\eta\alpha^{2}(t-\mathcal{T}_{0}+1)}\right).$
(223)

###### Proof of Lemma J.9.

Let $t\in[\mathcal{T}_{0},T].$ Using Lemma J.11, we bound the signal momentum
as:

$\displaystyle-\mathcal{G}^{(t)}$
$\displaystyle\geq\Theta(1-\gamma)\alpha\sum_{s=\mathcal{T}_{0}}^{t}\gamma^{t-s}\widehat{\ell}^{(s)}(\alpha)(\alpha
c^{(s)})^{2}$ $\displaystyle\geq(1-\hat{\mu})\Theta(1-\gamma)\alpha(\alpha
c^{(t)})^{2}\widehat{\ell}^{(t)}(\alpha)\sum_{s=\mathcal{T}_{0}}^{t}\gamma^{t-s}$
$\displaystyle\geq(1-\hat{\mu})\Theta(1)\alpha(\alpha
c^{(t)})^{2}\widehat{\ell}^{(t)}(\alpha).$ (224)

From Lemma 6.1, we know that $c^{(t)}\geq\tilde{\Omega}(1/\alpha).$ Thus, we
simplify (224) as:

$\displaystyle-\mathcal{G}^{(t)}\geq(1-\hat{\mu})\tilde{\Omega}(\alpha)\widehat{\ell}^{(t)}(\alpha).$
(225)

We now plug (225) in the signal update (3).

$\displaystyle c^{(t+1)}\geq
c^{(t)}+\tilde{\Omega}(\eta\alpha)(1-\hat{\mu})\widehat{\ell}^{(t)}(\alpha).$
(226)

We now apply Lemma K.22 to lower bound (226) by loss terms. We have:

$\displaystyle c^{(t+1)}\geq
c^{(t)}+\tilde{\Omega}(\eta\alpha)(1-\hat{\mu})\widehat{\mathcal{L}}^{(t)}(\alpha).$
(227)

Let’s now assume by contradiction that for $t\in[\mathcal{T}_{0},T]$, we have:

$\displaystyle(1-\hat{\mu})\widehat{\mathcal{L}}^{(t)}(\alpha)>\frac{\tilde{\Omega}(1)}{\eta\alpha^{2}(t-\mathcal{T}_{0}+1)}.$
(228)

From the (3) update, we know that $c_{r}^{(\tau)}$ is a non-decreasing
sequence which implies that $\sum_{r=1}^{m}(\alpha c_{r}^{(\tau)})^{3}$ is
also non-decreasing for $\tau\in[T]$. Since $x\mapsto\log(1+\exp(-x))$ is non-
increasing, this implies that for $s\leq t$, we have:

$\displaystyle\frac{\tilde{\Omega}(1)}{\eta\alpha^{2}(t-\mathcal{T}_{0}+1)}<(1-\hat{\mu})\widehat{\mathcal{L}}^{(t)}(\alpha)\leq(1-\hat{\mu})\widehat{\mathcal{L}}^{(s)}(\alpha).$
(229)

Plugging (229) in the update (228) yields for $s\in[\mathcal{T}_{0},t]$:

$\displaystyle
c^{(s+1)}>c^{(s)}+\frac{\tilde{\Omega}(1)}{\alpha(t-\mathcal{T}_{0}+1)}$ (230)

We now sum (230) for $s=\mathcal{T}_{0},\dots,t$ and obtain:

$\displaystyle
c^{(t+1)}>c^{(\mathcal{T}_{0})}+\frac{\tilde{\Omega}(1)(t-\mathcal{T}_{0}+1)}{\alpha(t-\mathcal{T}_{0}+1)}>\frac{\tilde{\Omega}(1)}{\alpha},$
(231)

where we used the fact that
$c^{(\mathcal{T}_{0})}\geq\tilde{\Omega}(1/\alpha)>0$ (Lemma 6.2) in the last
inequality. Thus, from Lemma 6.1 and (231), we have for
$t\in[\mathcal{T}_{0},T]$, $c^{(t)}\geq\tilde{\Omega}(1/\alpha).$ Let’s now
show that this leads to a contradiction. Indeed, for
$t\in[\mathcal{T}_{0},T]$, we have:

$\displaystyle\eta\alpha^{2}(t-\mathcal{T}_{0}+1)(1-\hat{\mu})\widehat{\mathcal{L}}^{(t)}(\alpha)$
$\displaystyle\leq\eta\alpha^{2}T(1-\hat{\mu})\log\left(1+\exp(-\tilde{\Omega}(1)\right),$
(232)

where we used $c^{(t)}\geq\tilde{\Omega}(1/\alpha)$ in (232). We now apply
Lemma K.22 in (232) and obtain:

$\displaystyle\eta\alpha^{2}(t-\mathcal{T}_{0}+1)(1-\hat{\mu})\widehat{\mathcal{L}}^{(t)}(\alpha)\leq\frac{(1-\hat{\mu})\eta\alpha^{2}T}{1+\exp(\tilde{\Omega}(1))}.$
(233)

Given the values of $\alpha,\eta,T$, we finally have:

$\displaystyle\eta\alpha^{2}(t-\mathcal{T}_{0}+1)(1-\hat{\mu})\widehat{\mathcal{L}}^{(t)}(\alpha)\leq\tilde{O}(1),$
(234)

which contradicts (228). ∎

We now link the bound on the loss to the derivative $\nu_{1}^{(t)}.$

######  Lemma J.8.

For $t\in[\mathcal{T}_{0},T]$, we have
$\nu_{1}^{(t)}\leq\tilde{O}\left(\frac{1}{\eta(t-\mathcal{T}_{0}+1)\alpha}\right)$.

###### Proof of Lemma J.8.

The proof is similar to the one of Lemma 6.4.

∎

####  J.4.2 Convergence at late stages $(t\in[\mathcal{T}_{1},T])$

######  Lemma J.9 (Convergence rate of the loss).

For $t\in[\mathcal{T}_{1},T]$ Using GD+M with learning rate $\eta>0$, the loss
sublinearly converges to zero as

$\displaystyle(1-\hat{\mu})\widehat{\mathcal{L}}^{(t)}(\alpha)+\hat{\mu}\widehat{\mathcal{L}}^{(t)}(\beta)\leq\tilde{O}\left(\frac{1}{\eta\beta^{2}(t-\mathcal{T}_{1}+1)}\right).$
(235)

###### Proof of Lemma J.9.

Let $t\in[\mathcal{T}_{1},T].$ From Lemma J.10, we know that the signal
gradient is bounded as $-\mathscr{G}^{(t)}\geq-\mathscr{G}^{(s)}$ for
$s\in[\mathcal{T}_{1},t].$

$\displaystyle-\mathcal{G}^{(t)}$
$\displaystyle=-\gamma^{t-\mathcal{T}_{1}}\mathcal{G}^{(\mathcal{T}_{1})}-(1-\gamma)\sum_{s=\mathcal{T}_{1}}^{t}\gamma^{t-s}\mathscr{G}^{(s)}$
$\displaystyle\geq-(1-\gamma)\sum_{s=\mathcal{T}_{1}}^{t}\gamma^{t-s}\mathscr{G}^{(s)}$
$\displaystyle\geq-(1-\gamma)\mathscr{G}^{(t)}\sum_{s=\mathcal{T}_{1}}^{t}\gamma^{t-s}$
$\displaystyle=-\Theta(1)\mathscr{G}^{(t)}.$ (236)

From Lemma E.2, the signal gradient is:

$\displaystyle-\mathscr{G}^{(t)}=\Theta(1)\left(\alpha^{3}\widehat{\ell}^{(t)}(\alpha)+\beta^{3}\widehat{\ell}^{(t)}(\beta)\right)(c^{(t)})^{2}.$
(237)

From Lemma 6.3, we know that $c^{(t)}\geq\tilde{\Omega}(1/\beta)$. Thus, we
simplify (237) as:

$\displaystyle-\mathscr{G}^{(t)}\geq\tilde{\Omega}(\beta)\left((1-\hat{\mu})\widehat{\ell}^{(t)}(\alpha)+\hat{\mu}\beta\widehat{\ell}^{(t)}(\beta)\right).$
(238)

By combining (236) and (238), we finally obtain:

$\displaystyle-\mathcal{G}^{(t)}\geq\tilde{\Omega}(\beta)\left((1-\hat{\mu})\widehat{\ell}^{(t)}(\alpha)+\hat{\mu}\widehat{\ell}^{(t)}(\beta)\right).$
(239)

We now plug (239) in the signal update (3).

$\displaystyle c^{(t+1)}\geq
c^{(t)}+\tilde{\Omega}(\eta\beta)\left((1-\hat{\mu})\widehat{\ell}^{(t)}(\alpha)+\hat{\mu}\widehat{\ell}^{(t)}(\beta)\right).$
(240)

We now apply Lemma K.22 to lower bound (240) by loss terms. We have:

$\displaystyle c^{(t+1)}\geq
c^{(t)}+\tilde{\Omega}(\eta\beta)\left((1-\hat{\mu})\widehat{\mathcal{L}}^{(t)}(\alpha)+\hat{\mu}\widehat{\mathcal{L}}^{(t)}(\beta)\right).$
(241)

Let’s now assume by contradiction that for $t\in[\mathcal{T}_{1},T]$, we have:

$\displaystyle(1-\hat{\mu})\widehat{\mathcal{L}}^{(t)}(\alpha)+\hat{\mu}\widehat{\mathcal{L}}^{(t)}(\beta)>\frac{\tilde{\Omega}(1)}{\eta\beta^{2}(t-\mathcal{T}_{1}+1)}.$
(242)

From the (3) update, we know that $c_{r}^{(\tau)}$ is a non-decreasing
sequence which implies that $\sum_{r=1}^{m}(\theta c_{r}^{(\tau)})^{3}$ is
also non-decreasing for $\tau\in[T]$. Since $x\mapsto\log(1+\exp(-x))$ is non-
increasing, this implies that for $s\leq t$, we have:

$\displaystyle\frac{\tilde{\Omega}(1)}{\eta\beta^{2}(t-\mathcal{T}_{1}+1)}<(1-\hat{\mu})\widehat{\mathcal{L}}^{(t)}(\alpha)+\hat{\mu}\widehat{\mathcal{L}}^{(t)}(\beta)\leq(1-\hat{\mu})\widehat{\mathcal{L}}^{(s)}(\alpha)+\hat{\mu}\widehat{\mathcal{L}}^{(s)}(\beta).$
(243)

Plugging (243) in the update (241) yields for $s\in[\mathcal{T}_{1},t]$:

$\displaystyle
c^{(s+1)}>c^{(s)}+\frac{\tilde{\Omega}(1)}{\beta(t-\mathcal{T}_{1}+1)}$ (244)

We now sum (244) for $s=\mathcal{T}_{1},\dots,t$ and obtain:

$\displaystyle
c^{(t+1)}>c^{(\mathcal{T}_{1})}+\frac{\tilde{\Omega}(1)(t-\mathcal{T}_{1}+1)}{\beta(t-\mathcal{T}_{1}+1)}>\frac{\tilde{\Omega}(1)}{\beta},$
(245)

where we used the fact that
$c^{(\mathcal{T}_{1})}\geq\tilde{\Omega}(1/\beta)>0$ (Lemma 6.2) in the last
inequality. Thus, from Lemma 6.2 and (245), we have for
$t\in[\mathcal{T}_{1},T]$, $c^{(t)}\geq\tilde{\Omega}(1/\beta).$ Let’s now
show that this leads to a contradiction. Indeed, for
$t\in[\mathcal{T}_{1},T]$, we have:

$\displaystyle\eta\beta^{2}(t-\mathcal{T}_{1}+1)\left((1-\hat{\mu})\widehat{\mathcal{L}}^{(t)}(\alpha)+\hat{\mu}\widehat{\mathcal{L}}^{(t)}(\beta)\right)$
$\displaystyle\leq$
$\displaystyle\eta\beta^{2}T\left((1-\hat{\mu})\log\left(1+\exp(-(\alpha
c^{(t)})^{3}-\sum_{r\neq r_{\max}}(\alpha c_{r}^{(t)})^{3}\right)\right.$
$\displaystyle\left.\qquad+\hat{\mu}\log\left(1+\exp(-(\beta
c^{(t)})^{3}-\sum_{r\neq r_{\max}}(\beta c_{r}^{(t)})^{3}\right)\right)$
$\displaystyle\leq$
$\displaystyle\eta\beta^{2}T\left((1-\hat{\mu})\log\left(1+\exp(-\tilde{\Omega}(\alpha^{3}/\beta^{3})\right)+\hat{\mu}\log\left(1+\exp(-\tilde{\Omega}(1)\right)\right),$
(246)

where we used $\sum_{r\neq
r_{\max}}(c_{r}^{(t)})^{3}\geq-m\tilde{O}(\sigma_{0}^{3})$ and
$c^{(t)}\geq\tilde{\Omega}(1/\beta)$ in (246). We now apply Lemma K.22 in
(246) and obtain:

$\displaystyle\eta\beta^{2}(t-\mathcal{T}_{1}+1)\left((1-\hat{\mu})\widehat{\mathcal{L}}^{(t)}(\alpha)+\hat{\mu}\widehat{\mathcal{L}}^{(t)}(\beta)\right)\leq\frac{(1-\hat{\mu})\eta\beta^{2}T}{1+\exp(\tilde{\Omega}(\alpha^{3}/\beta^{3}))}+\frac{\hat{\mu}\eta\beta^{2}T}{1+\exp(\tilde{\Omega}(1))}.$
(247)

Given the values of $\alpha,\beta,\eta,T,\hat{\mu}$, we finally have:

$\displaystyle\eta\beta^{2}(t-\mathcal{T}_{1}+1)\left((1-\hat{\mu})\widehat{\mathcal{L}}^{(t)}(\alpha)+\hat{\mu}\widehat{\mathcal{L}}^{(t)}(\beta)\right)\leq\tilde{O}(1),$
(248)

which contradicts (242). ∎

####  J.4.3 Auxiliary lemmas

We now provide an auxiliary lemma needed to obtain (J.9).

######  Lemma J.10.

Let $t\in[\mathcal{T}_{1},T].$ Then, the signal gradient decreases i.e.
$-\mathscr{G}^{(s)}\geq-\mathscr{G}^{(t)}$ for $s\in[\mathcal{T}_{1},t].$

###### Proof of Lemma J.10.

From Lemma E.2, we know that

$\displaystyle-\mathscr{G}^{(t)}=\Theta(1)\left(\alpha^{3}\widehat{\ell}^{(t)}(\alpha)+\beta^{3}\widehat{\ell}^{(t)}(\beta)\right)(c^{(t)})^{2}.$
(249)

Since $c_{r}^{(t)}\geq-\tilde{O}(\sigma_{0})$, we bound (249) as:

$\displaystyle-\mathscr{G}^{(t)}\leq\Theta(1)\left(\alpha^{3}\mathfrak{S}((\alpha
c^{(t)})^{3})+\beta^{3}\mathfrak{S}((\beta c^{(t)})^{3})\right)(c^{(t)})^{2}.$
(250)

The function $x\mapsto x^{2}\mathfrak{S}(x^{3})$ is non-increasing for $x\geq
1.$ Since $c^{(t)}\geq\tilde{\Omega}(1/\beta)$, we have:

$\displaystyle-\mathscr{G}^{(t)}\leq\Theta(1)\left(\alpha^{3}\mathfrak{S}((\alpha
c^{(\mathcal{T}_{1})})^{3})+\beta^{3}\mathfrak{S}((\beta
c^{(\mathcal{T}_{1})})^{3})\right)(c^{(\mathcal{T}_{1})})^{2}=-\mathscr{G}^{(\mathcal{T}_{1})}.$
(251)

∎

######  Lemma J.11.

Let $t\in[\mathcal{T}_{0},T].$ Then, the signal $\mathcal{Z}_{1}$ gradient
decreases i.e. $\widehat{\ell}^{(s)}(\alpha)(\alpha
c^{(s)})^{2}\geq\widehat{\ell}^{(t)}(\alpha)(\alpha c^{(t)})^{2}$ for
$s\in[\mathcal{T}_{0},t].$

###### Proof of Lemma J.11.

The proof is similar to the one of Lemma J.10.

∎

##  Appendix K Useful lemmas

In this section, we provide the probabilistic and optimization lemmas and the
main inequalities used above.

###  K.1 Probabilistic lemmas

In this section, we introduce the probabilistic lemmas used in the proof.

####  K.1.1 High-probability bounds

######  Lemma K.1.

The sum of of symmetric random variables is symmetric.

######  Lemma K.2 (Sum of sub-Gaussians (Vershynin, 2018)).

Let $\sigma_{1},\sigma_{2}>0.$ Let $X$ and $Y$ respetively be $\sigma_{1}$\-
and $\sigma_{2}$-subGaussian random variables. Then, $X+Y$ is
$\sqrt{\sigma_{1}+\sigma_{2}}$-subGaussian random variable.

######  Lemma K.3 (High probability bound subGaussian (Vershynin, 2018)).

Let $t>0.$ Let $X$ be a $\sigma$-subGaussian random variable. Then, we have:

$\displaystyle\mathbb{P}\left[|X|>t\right]\leq
2e^{-\frac{t^{2}}{2\sigma^{2}}}.$

######  Theorem K.1 (Concentration of Lipschitz functions of Gaussian
variables (Wainwright, 2019)).

Let $X_{1},\dots,X_{N}$ be $N$ i.i.d. random variables such that
$X_{i}\sim\mathcal{N}(0,\sigma^{2})$ and $X:=(X_{1},\dots,X_{n}).$ Let
$f\colon\mathbb{R}^{d}\rightarrow\mathbb{R}$ be $L$-Lipschitz with respect to
the Euclidean norm. Then,

$\displaystyle\mathbb{P}[|f(X)-\mathbb{E}[f(X)]|\geq t]\leq
2e^{-\frac{t^{2}}{2L}}.$ (252)

######  Lemma K.4 (Expectation of Gaussian vector (Wainwright, 2019)).

Let $X\in\mathbb{R}^{d}$ be a Gaussian vector such that
$X\sim\mathcal{N}(0,\sigma^{2}\mathbf{I}).$ Then, its expectation is equal to
$\mathbb{E}[\|X\|_{2}]=\Theta(\sigma\sqrt{d}).$

######  Lemma K.5 (High-probability bound on squared norm of Gaussian).

Let $\bm{X}\in\mathbb{R}^{d}$ be a Gaussian vector such that
$X\sim\mathcal{N}(0,\sigma^{2}\mathbf{I}_{d}).$ Then, with probability at
least $1-o(1)$, we have $\|\bm{X}\|_{2}^{2}=\Theta(\sigma^{2}d).$

###### Proof of Lemma K.5. .

We know that the $\|\cdot\|_{2}$ is $1$-Lipschitz and by applying Theorem K.1,
we therefore have::

$\displaystyle\mathbb{P}\left[\left|\|\bm{X}\|_{2}-\mathbb{E}[\|\bm{X}\|_{2}]\right|>\epsilon\right]$
$\displaystyle\leq\exp\left(-\frac{\epsilon^{2}}{2\sigma^{2}}\right).$ (253)

By rewriting (253) and using Lemma K.4, we have with probability $1-\delta,$

$\displaystyle\Theta(\sigma\sqrt{d})-\sigma\sqrt{2\log\left(\frac{1}{\delta}\right)}\leq\|\bm{X}\|_{2}\leq\Theta(\sigma\sqrt{d})+\sigma\sqrt{2\log\left(\frac{1}{\delta}\right)}.$
(254)

By squaring (254) and using $(a+b)^{2}\leq a^{2}+b^{2}$, we obtain the aimed
result. ∎

######  Lemma K.6 (Precise bound on squared norm of Gaussian).

Let $\bm{X}\in\mathbb{R}^{d}$ be a Gaussian vector such that
$X\sim\mathcal{N}(0,\sigma^{2}\mathbf{I}_{d}).$ Then, we have:

$\displaystyle\mathbb{P}\left[\|X\|_{2}\in\left[\frac{1}{2}\sigma\sqrt{d},\frac{3}{2}\sigma\sqrt{d}\right]\right]\geq
1-e^{-d/8}.$

###### Proof of Lemma K.6.

We know that the $\|\cdot\|_{2}$ is $1$-Lipschitz and by applying Theorem K.1,
we therefore have:

$\displaystyle\mathbb{P}\left[\left|\|\bm{X}\|_{2}-\mathbb{E}[\|\bm{X}\|_{2}]\right|>\epsilon\right]$
$\displaystyle\leq\exp\left(-\frac{\epsilon^{2}}{2\sigma^{2}}\right).$ (255)

We use Lemma K.4 and set $\epsilon=\frac{\sigma\sqrt{d}}{2}$ in (255) to
finally get:

$\displaystyle\mathbb{P}\left[\left|\|\bm{X}\|_{2}-\mathbb{E}[\|\bm{X}\|_{2}]\right|>\frac{\sigma\sqrt{d}}{2}\right]$
$\displaystyle\leq\exp\left(-\frac{d}{8}\right).$

∎

######  Lemma K.7 (High-probability bound on dot-product of Gaussians).

Let $X$ and $Y$ be two independent Gaussian vectors in $\mathbb{R}^{d}$ such
that $\bm{X},\bm{Y}$ independent and
$\bm{X}\sim\mathcal{N}(0,\sigma^{2}\mathbf{I})$ and
$\bm{Y}\sim\mathcal{N}(0,\sigma_{0}^{2}\mathbf{I}_{d})$. Assume that
$\sigma\sigma_{0}\leq 1/d.$ Then, with probability $1-o(1)$, we have:

$\displaystyle|\langle\bm{X},\bm{Y}\rangle|$
$\displaystyle\leq\tilde{O}(\sigma\sigma_{0}\sqrt{d}).$

###### Proof of Lemma K.7 .

Let’s define $Z:=\langle\bm{X},\bm{Y}\rangle.$ We first remark that $Z$ is a
sub-exponential random variable. Indeed, the generating moment function is:

$\displaystyle M_{Z}(t)=\mathbb{E}[e^{t\langle
X,Y\rangle}]=\frac{1}{(1-\sigma^{2}\sigma_{0}^{2}t^{2})^{d/2}}=e^{-\frac{d}{2}\log(1-\sigma^{2}\sigma_{0}^{2}t^{2})}\leq
e^{\frac{d\sigma^{2}\sigma_{0}^{2}t^{2}}{2}},\qquad\text{for
}t\leq\frac{1}{\sigma\sigma_{0}}.$

where we used $\log(1-x)\geq-x$ for $x<1$ in the last inequality. Therefore,
by definition of a sub-exponential variable, we have:

$\displaystyle\mathbb{P}\left[|Z-\mathbb{E}[Z]|>\epsilon\right]$
$\displaystyle\leq\begin{cases}2e^{-\frac{\epsilon^{2}}{2d\sigma^{2}\sigma_{0}^{2}}}&\text{for
}0\leq\epsilon\leq d\sigma\sigma_{0}\\\
2e^{-\frac{\epsilon}{2\sigma\sigma_{0}}}&\text{for }\epsilon\geq
d\sigma\sigma_{0}\end{cases}.$ (256)

Since $\sigma^{2}d\leq 1$ and $\epsilon\in[0,1],$ (256) is bounded as:

$\displaystyle\mathbb{P}\left[|Z-\mathbb{E}[Z]|>\epsilon\right]\leq
2e^{-\frac{\epsilon^{2}}{2d\sigma^{2}\sigma_{0}^{2}}}.$ (257)

We know that
$\mathbb{E}[Z]=M^{\prime}(0)=\left(d(1-\sigma^{2}\sigma_{0}^{2}t^{2})^{-\frac{d}{2}-1}\sigma^{2}\sigma_{0}^{2}t\right)(0)=0.$
By plugging this expectation in (257), we have with probability $1-\delta,$

$\displaystyle|\langle\bm{X},\bm{Y}\rangle|$
$\displaystyle\leq\sigma\sigma_{0}\sqrt{2d\log\left(\frac{2}{\delta}\right)}.$

∎

######  Lemma K.8 (High-probability bound on dot-product of Gaussians).

Let $\bm{X}$ and $\bm{Y}$ be two independent Gaussian vectors in
$\mathbb{R}^{d}$ such that
$\bm{X},\bm{Y}\sim\mathcal{N}(0,\sigma^{2}\mathbf{I}_{d}).$ Then, with
probability $1-\delta,$ we have:

$\displaystyle\left|\left\langle\frac{\bm{X}}{\|\bm{X}\|_{2}},\bm{Y}\right\rangle\right|$
$\displaystyle\leq\tilde{O}(\sigma).$

###### Proof of Lemma K.7 .

Let $\bm{U}:=\bm{X}/\|\bm{X}\|_{2}$ and $Z:=\langle\bm{U},\bm{Y}\rangle.$ We
know that the pdf of $\bm{U}$ in polar coordinates is
$f_{\bm{U}}(\theta)=\frac{\Gamma(d/2)}{2\pi^{d/2}}.$ Therefore, the generating
moment function of $Z$ is:

$\displaystyle
M_{Z}(t)=\int_{\mathbb{S}^{d-1}}\int_{\mathbb{R}^{d}}e^{t\langle\bm{u},\bm{y}\rangle}f_{\bm{U}}(\bm{u})f_{\bm{Y}}(\bm{y})d\bm{u}d\bm{y}$
$\displaystyle=\frac{\Gamma(d/2)}{2\pi^{d/2}(2\pi\sigma^{2})^{d/2}}\int_{\mathbb{S}^{d-1}}\int_{\mathbb{R}^{d}}e^{t\langle\bm{u},\bm{y}\rangle}e^{-\frac{\|\bm{y}\|_{2}^{2}}{2\sigma^{2}}}d\bm{y}d\bm{u}$
$\displaystyle=\frac{\Gamma(d/2)}{2\pi^{d/2}(2\pi\sigma^{2})^{d/2}}\int_{\mathbb{S}^{d-1}}\int_{\mathbb{R}^{d}}e^{-\frac{\|\bm{y}-t\sigma^{2}\bm{u}\|_{2}^{2}}{2\sigma^{2}}}e^{\frac{t^{2}\sigma^{2}\|\bm{u}\|_{2}^{2}}{2}}d\bm{y}d\bm{u}$
$\displaystyle=\frac{\Gamma(d/2)}{2\pi^{d/2}(2\pi\sigma^{2})^{d/2}}\int_{\mathbb{S}^{d-1}}e^{\frac{\sigma^{2}t^{2}\|\bm{u}\|_{2}^{2}}{2}}d\bm{u}$
$\displaystyle=\frac{\Gamma(d/2)}{2\pi^{d/2}(2\pi\sigma^{2})^{d/2}}\int_{\mathbb{S}^{d-1}}e^{\frac{\sigma^{2}t^{2}}{2}}d\bm{u}$
$\displaystyle=e^{\frac{\sigma^{2}t^{2}}{2}}.$ (258)

(258) indicates that $Z$ is a sub-Gaussian random variable of parameter
$\sigma$. By definition, it satisfies

$\displaystyle\mathbb{P}[|Z|>\epsilon]\leq
2e^{-\frac{\epsilon^{2}}{2\sigma^{2}}}.$ (259)

Setting $\delta=2e^{-\frac{\epsilon^{2}}{2\sigma^{2}}}$ in (259) yields that
we have with probability $1-\delta,$

$\displaystyle\left|\left\langle\frac{\bm{X}}{\|\bm{X}\|_{2}},\bm{Y}\right\rangle\right|$
$\displaystyle\leq\sqrt{2\log\left(\frac{2}{\delta}\right)}.$

∎

######  Lemma K.9 (High probability bound for ratio of norms).

Let $\bm{X}_{1},\dots,\bm{X}_{n}$ i.i.d. vectors from
$\mathcal{N}(0,\sigma^{2}\mathbf{I}).$ Then, with probability $1-o(1)$, we
have:

$\displaystyle\frac{\|\bm{X}_{1}\|_{2}^{2}}{\|\sum_{i=1}^{n}\bm{X}_{i}\|_{2}}=\tilde{\Theta}\left(\sigma\sqrt{\frac{d}{n}}\right).$
(260)

###### Proof of Lemma K.9.

We know that for $\bm{X}_{1}\sim\mathcal{N}(0,\sigma^{2}d)$, we have:

$\displaystyle\mathbb{P}\left[\|\bm{X}_{1}\|_{2}^{2}\in\left[\frac{\sigma^{2}d}{4},\frac{9\sigma^{2}d}{4}\right]\right]\leq
e^{-d/8}.$ (261)

Therefore, using the law of total probability and (261), we have:

$\displaystyle\mathbb{P}\left[\frac{\|\bm{X}_{1}\|_{2}^{2}}{\|\sum_{i=1}^{n}\bm{X}_{i}\|_{2}}>t\right]$
$\displaystyle=\mathbb{P}\left[\frac{\|\bm{X}_{1}\|_{2}^{2}}{\|\sum_{i=1}^{n}\bm{X}_{i}\|_{2}}>t\;\middle|\;\|\bm{X}_{1}\|_{2}^{2}>\frac{9\sigma^{2}d}{4}\right]\mathbb{P}\left[\|\bm{X}_{1}\|_{2}^{2}>\frac{9\sigma^{2}d}{4}\right]$
$\displaystyle+\mathbb{P}\left[\frac{\|\bm{X}_{1}\|_{2}^{2}}{\|\sum_{i=1}^{n}\bm{X}_{i}\|_{2}}>t\;\middle|\;\|\bm{X}_{1}\|_{2}^{2}<\frac{9\sigma^{2}d}{4}\right]\mathbb{P}\left[\|\bm{X}_{1}\|_{2}^{2}<\frac{9\sigma^{2}d}{4}\right]$
$\displaystyle\leq
e^{-d/8}+\mathbb{P}\left[\frac{\|\bm{X}_{1}\|_{2}^{2}}{\|\sum_{i=1}^{n}\bm{X}_{i}\|_{2}}>t\;\middle|\;\|\bm{X}_{1}\|_{2}^{2}<\frac{9\sigma^{2}d}{4}\right].$
(262)

Now, we can further bound (262) as:

$\displaystyle\mathbb{P}\left[\frac{\|\bm{X}_{1}\|_{2}^{2}}{\|\sum_{i=1}^{n}X_{i}\|_{2}}>t\right]$
$\displaystyle\leq
e^{-d/8}+\mathbb{P}\left[\frac{9\sigma^{2}d}{4t}>\|\sum_{i=1}^{n}\bm{X}_{i}\|_{2}\right].$
(263)

Since $\sum_{i=1}^{n}\bm{X}_{i}\sim\mathcal{N}(0,n\sigma^{2}\mathbf{I}_{d})$,
we also have

$\displaystyle\mathbb{P}\left[\|\sum_{i=1}^{n}\bm{X}_{i}\|_{2}\in\left[\frac{\sigma\sqrt{nd}}{2},\frac{3\sigma\sqrt{nd}}{2}\right]\right]\leq
e^{-d/8}.$ (264)

Therefore by setting $t=\frac{3\sigma}{2}\sqrt{\frac{d}{n}}$, we obtain:

$\displaystyle\mathbb{P}\left[\frac{\|\bm{X}_{1}\|_{2}^{2}}{\|\sum_{i=1}^{n}\bm{X}_{i}\|_{2}}>\frac{3\sigma}{2}\sqrt{\frac{d}{n}}\right]\leq
2e^{-d/8}.$ (265)

Doing the similar reasoning for the lower bound yields:

$\displaystyle\mathbb{P}\left[\frac{\|\bm{X}_{1}\|_{2}^{2}}{\|\sum_{i=1}^{n}\bm{X}_{i}\|_{2}}<\frac{\sigma}{2}\sqrt{\frac{d}{n}}\right]\leq
2e^{-d/8}.$ (266)

∎

######  Lemma K.10 (High probability bound norms vs dot product).

Let $\bm{X}_{1},\dots,\bm{X}_{n}$ i.i.d. vectors from
$\mathcal{N}(0,\sigma^{2}\mathbf{I}_{d}).$ Then, with probability $1-o(1),$ we
have:

$\displaystyle\frac{\sqrt{d}|\langle\bm{X}_{1},\bm{X}_{2}\rangle|}{\|\sum_{i=1}^{N}\bm{X}_{i}\|_{2}}\leq\frac{\|\bm{X}_{1}\|_{2}^{2}}{\|\sum_{i=1}^{N}\bm{X}_{i}\|_{2}}.$
(267)

###### Proof of Lemma K.10.

To show the result, it’s enough to upper bound the following probability:

$\displaystyle\mathbb{P}\left[\|\bm{X}_{1}\|_{2}^{2}>\sqrt{d}|\langle\bm{X}_{1},\bm{X}_{2}\rangle|\right].$
(268)

By using the law of total probability we have:

$\displaystyle\mathbb{P}\left[\|\bm{X}_{1}\|_{2}^{2}>\sqrt{d}|\langle\bm{X}_{1},\bm{X}_{2}\rangle|\right]$
$\displaystyle=$
$\displaystyle\mathbb{P}\left[\|\bm{X}_{1}\|_{2}^{2}>\sqrt{d}|\langle\bm{X}_{1},\bm{X}_{2}\rangle|\;\middle|\;\|\bm{X}_{1}\|_{2}^{2}\in\left[\frac{\sigma^{2}d}{2},\frac{9\sigma^{2}d}{4}\right]\right]\mathbb{P}\left[\|\bm{X}_{1}\|_{2}^{2}\in\left[\frac{\sigma^{2}d}{2},\frac{9\sigma^{2}}{4}\right]\right]$
$\displaystyle+$
$\displaystyle\mathbb{P}\left[\|\bm{X}_{1}\|_{2}^{2}>\sqrt{d}|\langle\bm{X}_{1},\bm{X}_{2}\rangle|\;\middle|\;\|\bm{X}_{1}\|_{2}^{2}\not\in\left[\frac{\sigma^{2}d}{2},\frac{9\sigma^{2}d}{4}\right]\right]\mathbb{P}\left[\|\bm{X}_{1}\|_{2}^{2}\not\in\left[\frac{\sigma^{2}d}{2},\frac{9\sigma^{2}}{4}\right]\right]$
$\displaystyle\leq$
$\displaystyle\mathbb{P}\left[\|\bm{X}_{1}\|_{2}^{2}>\sqrt{d}|\langle\bm{X}_{1},\bm{X}_{2}\rangle|\;\middle|\;\|\bm{X}_{1}\|_{2}^{2}\in\left[\frac{\sigma^{2}d}{2},\frac{9\sigma^{2}d}{4}\right]\right]+e^{-d/8},$
(269)

where we used Lemma K.6 in (269). Using Lemma K.6 again, we can simplify (269)
as:

$\displaystyle\mathbb{P}\left[\|\bm{X}_{1}\|_{2}^{2}>\sqrt{d}|\langle\bm{X}_{1},\bm{X}_{2}\rangle|\right]$
$\displaystyle\leq\mathbb{P}\left[\frac{9\sigma^{2}\sqrt{d}}{4}>|\langle\bm{X}_{1},\bm{X}_{2}\rangle|\right]+e^{-d/8}$
$\displaystyle\leq 2e^{-d/8}.$

∎

####  K.1.2 Anti-concentration of Gaussian polynomials

######  Theorem K.2 (Anti-concentration of Gaussian polynomials (Carbery &
Wright, 2001; Lovett, 2010)).

Let $P(x)=P(x_{1},\dots,x_{n})$ be a degree $d$ polynomial and
$x_{1},\dots,x_{n}$ be i.i.d. Gaussian univariate random variables. Then, the
following holds for all $d,n$.

$\displaystyle\mathbb{P}\left[|P(x)|\leq\epsilon\mathrm{Var}[P(x)]^{1/2}\right]\leq
O(d)\epsilon^{1/d}.$

######  Lemma K.11 (Gaussians and Hermite).

Let
$\mathcal{P}(x_{1},\dots,x_{P})=\sum_{k=1}^{d}\sum_{\mathcal{I}\subset[P]:|\mathcal{I}|=k}c_{\mathcal{I}}\prod_{i\in\mathcal{I}}x_{i}$
be a degree $d$ polynomial where
$x_{1},\dots,x_{P}\overset{i.i.d.}{\sim}\mathcal{N}(0,\sigma^{2})$ and
$c_{\mathcal{I}}\in\mathbb{R}$.
Let $\mathcal{H}(x)=\sum_{e\in\mathbb{N}^{P}:|e|\leq
d}c_{e}^{H}\prod_{i=1}^{P}H_{e_{i}}(x_{i})$ be the corresponding Hermite
polynomial to $\mathcal{P}$ where $\\{H_{e_{k}}\\}_{k=1}^{d}$ is the Hermite
polynomial basis. Then, the variance of $P$ is given by
$\mathrm{Var}[P(x)^{2}]=\sum_{e}|c_{e}^{H}|^{2}.$

######  Lemma K.12.

Let $\\{\bm{v}_{r}\\}_{r=1}^{m}$ be vectors in $\mathbb{R}^{d}$ such that
there exist a unit norm vector $\bm{x}$ that satisfies
$|\sum_{r=1}^{m}\langle\bm{v}_{r},\bm{x}\rangle^{3}|\geq 1.$ Then, for
$\bm{\xi}_{1},\dots,\bm{\xi}_{k}\sim\mathcal{N}(0,\sigma^{2}\mathbf{I}_{d})$
i.i.d., we have:

$\displaystyle\mathbb{P}\left[\left|\sum_{j=1}^{P}\sum_{r=1}^{m}\langle\bm{v}_{r},\bm{\xi}_{j}\rangle^{3}\right|\geq\tilde{\Omega}(\sigma^{3})\right]\geq
1-\frac{O(d)}{2^{1/d}}.$

###### Proof of Lemma K.12.

Let $\xi_{1},\dots,\xi_{j}\sim\mathcal{N}(0,\sigma^{2}\mathbf{I}_{d})$ i.i.d.
We decompose $\bm{\xi}_{j}$ as $\bm{\xi}_{j}=\tilde{a}_{j}\bm{x}+\bm{b}_{j}$
where $\bm{b}_{j}$ is an independent Gaussian on the orthogonal complement of
$\bm{x}$ and $\tilde{a}_{j}\sim\mathcal{N}(0,\sigma^{2}).$ Finally, we rewrite
$\tilde{a}_{j}$ as $\tilde{a}_{j}=\sigma a_{j}$ where
$a_{j}\sim\mathcal{N}(0,1).$ Therefore, we can rewrite
$\sum_{j=1}^{P}\sum_{r=1}^{m}\langle\bm{v}_{r},\bm{\xi}_{j}\rangle^{3}$ as a
polynomial $\mathcal{P}(a_{1},\dots,a_{P})$ defined as:

$\displaystyle\mathcal{P}(a_{1},\dots,a_{P})$
$\displaystyle=\sigma^{3}\sum_{j=1}^{P}a_{j}^{3}\left(\sum_{r=1}^{m}\langle\bm{v}_{r},\bm{x}\rangle^{3}\right)+3\sigma^{2}\sum_{j=1}^{P}a_{j}^{2}\left(\sum_{r=1}^{m}\langle\bm{v}_{r},\bm{x}\rangle^{2}\langle\bm{v}_{r},\bm{b}_{j}\rangle\right)$
(270)
$\displaystyle+3\sigma\sum_{j=1}^{P}a_{j}\left(\sum_{r=1}^{m}\langle\bm{v}_{r},\bm{x}\rangle\langle\bm{v}_{r},\bm{b}_{j}\rangle^{2}\right)+\sum_{j=1}^{P}\sum_{r=1}^{m}\langle\bm{v}_{r},\bm{b}_{j}\rangle^{3}.$

We now compute the mean and variance of $\mathcal{P}(a_{1},\dots,a_{P}).$
Those quantities are obtained through the corresponding Hermite polynomial of
$P$ as stated in Lemma K.11. Let $\mathcal{H}(x)$ be an Hermite polynomial of
degree 3. Since the Hermite basis is given by $H_{0}(x)=1,$ $H_{e_{1}}(x)=x,$
$H_{e_{2}}(x)=x^{2}-1$ and $H_{e_{3}}(x)=x^{3}-3x$, for
$\alpha_{j},\beta_{j},\gamma_{j},\delta_{j}\in\mathbb{R}$, we have:

$\displaystyle\mathcal{H}(a_{1},\dots,a_{P})$
$\displaystyle=\sum_{j=1}^{P}\alpha_{j}H_{e_{3}}(a_{j})+\sum_{j=1}^{P}\beta_{j}H_{e_{2}}(a_{j})+\gamma\sum_{j=1}^{P}H_{e_{1}}(a_{j})+\delta\sum_{j=1}^{P}H_{e_{0}}(a_{j})$
$\displaystyle=\sum_{j=1}^{P}\alpha_{j}(a_{j}^{3}-3a_{j})+\sum_{j=1}^{P}\beta_{j}(a_{j}^{2}-1)+\sum_{j=1}^{P}\gamma_{j}a_{j}+\sum_{j=1}^{P}\delta_{j}$
$\displaystyle=\sum_{j=1}^{P}\alpha_{j}a_{j}^{3}+\sum_{j=1}^{P}\beta_{j}a_{j}^{2}+\sum_{j=1}^{P}(\gamma_{j}-3\alpha_{j})a_{j}+\sum_{j=1}^{P}(\delta_{j}-\beta_{j}).$
(271)

Since the decomposition of a polynomial in the monomial basis is unique, we
can equate the coefficients of $H$ and $P$ and obtain:

$\displaystyle\begin{cases}\alpha_{j}=\sigma^{3}\sum_{r=1}^{m}\langle\bm{v}_{r},\bm{x}\rangle^{3}\\\
\beta_{j}=3\sigma^{2}\sum_{r=1}^{m}\langle\bm{v}_{r},\bm{x}\rangle^{2}\langle\bm{v}_{r},\bm{b}_{j}\rangle\\\
\gamma_{j}=3\sigma\sum_{r=1}^{m}\langle\bm{v}_{r},\bm{x}\rangle\langle
v_{r},b_{j}\rangle^{2}+3\sigma^{3}\sum_{r=1}^{m}\langle\bm{v}_{r},\bm{x}\rangle^{3}\\\
\delta_{j}=\sum_{r=1}^{m}\langle\bm{v}_{r},\bm{b}_{j}\rangle^{3}+3\sigma^{2}\sum_{r=1}^{m}\langle\bm{v}_{r},\bm{x}\rangle^{2}\langle\bm{v}_{r},\bm{b}_{j}\rangle\end{cases}.$
(272)

By applying Lemma K.11, we get that
$\mathrm{Var}[P(a)]=\sum_{j=1}^{P}\alpha_{j}^{2}+\sum_{j=1}^{P}\beta_{j}^{2}+\sum_{j=1}^{P}\gamma_{j}^{2}\geq\sum_{j=1}^{P}\alpha_{j}^{2}.$
By using this lower bound on the variance, the fact that
$|\sum_{r=1}^{m}\langle\bm{v}_{r},\bm{x}\rangle^{3}|\geq 1$ and Theorem K.2,
we obtain

$\displaystyle\mathbb{P}\left[\left|\sum_{j=1}^{P}\sum_{r=1}^{m}\langle\bm{v}_{r},\bm{\xi}_{j}\rangle^{3}\right|\geq\epsilon\sigma^{3}\right]\geq
1-O(d)\epsilon^{1/d}$ (273)

Setting $\epsilon=1/2$ in (273) yields the desired result.

∎

####  K.1.3 Properties of the cube of a Gaussian

######  Lemma K.13.

Let $X\sim\mathcal{N}(0,\sigma^{2})$. Then, $X^{3}$ is
$\sigma^{3}$-subGaussian.

###### Proof of Lemma K.13.

By definition of the moment generating function, we have:

$\displaystyle M_{X^{3}}(t)$
$\displaystyle=\sum_{i=0}^{\infty}\frac{t^{i}E[X^{3i}]}{i!}=\sum_{k=0}^{\infty}\frac{t^{2k}\sigma^{6k}(2k-1)!!}{(2k)!}=\sum_{k=0}^{\infty}\frac{t^{2k}\sigma^{6k}}{2^{k}k!}=e^{\frac{t^{2}\sigma^{6}}{2}}.$

∎

######  Lemma K.14.

Let $(\bm{X}[1],\dots,\bm{X}[P-1])$ be i.i.d. random variables such that
$\bm{X}[j]\sim\mathcal{N}(0,\sigma^{2}\mathbf{I}_{d}).$ Let
$(\bm{w}_{1},\dots,\bm{w}_{m})$ be fixed vectors such that
$w_{r}\in\mathbb{R}^{d}.$ Therefore,

$\displaystyle\sum_{s=1}^{m}\sum_{j=1}^{P-1}\langle\bm{w}_{s},\bm{X}[j]\rangle^{3}\text{
is
}\textstyle(\sigma^{3}\sqrt{P-1}\sqrt{\sum_{s=1}^{m}\|\bm{w}_{s}\|_{2}^{6}})-\text{subGaussian.}$

###### Proof.

We know that
$\langle\bm{w}_{s},\bm{X}[j]\rangle\sim\mathcal{N}(0,\|\bm{w}_{s}\|_{2}^{2}\sigma^{2})$.
Therefore, $\langle\bm{w}_{s},\bm{X}[j]\rangle^{3}$ is the cube of a centered
Gaussian. From Lemma K.13, $\langle\bm{w}_{s},\bm{X}[j]\rangle^{3}$ is
$\sigma^{3}\|\bm{w}_{s}\|_{2}^{3}$-subGaussian. Using Lemma K.2, we deduce
that $\sum_{j=1}^{P-1}\langle\bm{w}_{s},\bm{X}[j]\rangle^{3}$ is
$\sqrt{P}\sigma^{3}\|\bm{w}_{s}\|_{2}^{3}$-subGaussian. Applying again Lemma
K.2, we finally obtain that
$\sum_{s=1}^{m}\sum_{j=1}^{P-1}\langle\bm{w}_{s},\bm{X}[j]\rangle^{3}$ is
$\sigma^{3}\sqrt{P-1}\sqrt{\sum_{s=1}^{m}\|\bm{w}_{s}\|_{2}^{6}}$-subGaussian.
∎

###  K.2 Tensor Power Method Bound

In this subsection we establish a lemma for comparing the growth speed of two
sequences of updates of the form $z^{(t+1)}=z^{(t)}+\eta
C^{(t)}(z^{(t)})^{2}$. This technique is reminiscent of the classical analysis
of the growth of eigenvalues on the (incremental) tensor power method of
degree $2$ and is stated in full generality in (Allen-Zhu & Li, 2020).

####  K.2.1 Bounds for GD

######  Lemma K.15.

Let $\\{z^{(t)}\\}_{t=0}^{T}$ be a positive sequence defined by the following
recursions

$\displaystyle\begin{cases}z^{(t+1)}\geq z^{(t)}+m(z^{(t)})^{2}\\\
z^{(t+1)}\leq z^{(t)}+M(z^{(t)})^{2}\end{cases},$

where $z^{(0)}>0$ is the initialization and $m,M>0$.Let $\upsilon>0$ such that
$z^{(0)}\leq\upsilon.$ Then, the time $t_{0}$ such that $z_{t}\geq\upsilon$
for all $t\geq t_{0}$ is:

$\displaystyle
t_{0}=\frac{3}{mz^{(0)}}+\frac{8M}{m}\left\lceil\frac{\log(\upsilon/z_{0})}{\log(2)}\right\rceil.$

###### Proof of Lemma K.15.

Let $n\in\mathbb{N}^{*}$. Let $T_{n}$ be the time where $z^{(t)}\geq
2^{n}z^{(0)}$. This time exists because $z^{(t)}$ is a non-decreasing
sequence. We want to find an upper bound on this time. We start with the case
$n=1.$ By summing the recursion, we have:

$\displaystyle z^{(T_{1})}\geq z^{(0)}+m\sum_{s=0}^{T_{1}-1}(z^{(s)})^{2}.$
(274)

We use the fact that $z^{(s)}\geq z^{(0))}$ in (274) and obtain:

$\displaystyle T_{1}\leq\frac{z^{(T_{1})}-z^{(0)}}{m(z^{(0)})^{2}}.$ (275)

Now, we want to bound $z^{(T_{1})}-z^{(0)}$. Using again the recursion and
$z^{(T_{1}-1)}\leq 2z^{(0)}$, we have:

$\displaystyle z^{(T_{1})}\leq z^{(T_{1}-1)}+M(z^{(T_{1}-1)})^{2}\leq
2z^{(0)}+4M(z^{(0)})^{2}.$ (276)

Combining (275) and (276), we get a bound on $T_{1}.$

$\displaystyle T_{1}\leq\frac{1}{m(z^{(0)})}+\frac{4M}{m}.$ (277)

Now, let’s find a bound for $T_{n}$. Starting from the recursion and using the
fact that $z^{(s)}\geq 2^{n-1}z^{(0)}$ for $s\geq T_{n-1}$ we have:

$\displaystyle z^{(T_{n})}\geq
z^{(T_{n-1})}+m\sum_{s=T_{n-1}}^{T_{n}-1}(z^{(s)})^{2}\geq
z^{(T_{n-1})}+(2^{n-1})^{2}m(z^{(0)})^{2}(T_{n}-T_{n-1}).$ (278)

On the other hand, by using $z^{(T_{n}-1)}\leq 2^{n}z^{(0)}$ we upper bound
$z^{(T_{n})}$ as follows.

$\displaystyle z^{(T_{n})}$ $\displaystyle\leq
z^{(T_{n}-1)}+M(z^{(T_{n}-1)})^{2}\leq 2^{n}z^{(0)}+M2^{2n}(z^{(0)})^{2}.$
(279)

Besides, we know that $z^{(T_{n-1})}\geq 2^{n-1}z^{(0)}$. Therefore, we upper
bound $z^{(T_{n})}-z^{(T_{n-1})}$ as

$\displaystyle z^{(T_{n})}-z^{(T_{n-1})}\leq
2^{n-1}z^{(0)}+M2^{2n}(z^{(0)})^{2}.$ (280)

Combining (278) and (280) yields:

$\displaystyle T_{n}\leq T_{n-1}+\frac{1}{2^{n-1}m(z^{(0)})}+\frac{4M}{m}.$
(281)

We now sum (281) for $n=2,\dots,n$, use (277) and obtain:

$\displaystyle T_{n}\leq
T_{1}+\frac{2}{mz^{(0)}}+\frac{4Mn}{m}\leq\frac{3}{mz^{(0)}}+\frac{4M(n+1)}{m}\leq\frac{3}{mz^{(0)}}+\frac{8Mn}{m}.$
(282)

Lastly, we know that $n$ satisfies $2^{n}z^{(0)}\geq\upsilon$ this implies
that we can set
$n=\left\lceil\frac{\log(\upsilon/z_{0})}{\log(2)}\right\rceil$ in (282). ∎

######  Lemma K.16.

Let $\\{z^{(t)}\\}_{t=0}^{T}$ be a positive sequence defined by the following
recursion

$\displaystyle\begin{cases}z^{(t)}\geq
z^{(0)}+A\sum_{s=0}^{t-1}(z^{(s)})^{2}-C\\\ z^{(t)}\leq
z^{(0)}+A\sum_{s=0}^{t-1}(z^{(s)})^{2}+C\end{cases},$ (283)

where $A,C>0$ and $z^{(0)}>0$ is the initialization. Assume that $C\leq
z^{(0)}/2.$ Let $\upsilon>0$ such that $z^{(0)}\leq\upsilon.$ Then, the time
$t_{0}$ such that $z^{(t)}\geq\upsilon$ is upper bounded as:

$\displaystyle
t_{0}=8\left\lceil\frac{\log(\upsilon/z_{0})}{\log(2)}\right\rceil+\frac{21}{(z^{(0)})A}.$

###### Proof of Lemma K.16.

Let $n\in\mathbb{N}^{*}.$ Let $T_{n}$ be the time where $z^{(t)}\geq
2^{n-1}z^{(0)}$. We want to upper bound this time. We start with the case
$n=1.$ We have:

$\displaystyle z^{(T_{1})}\geq z^{(0)}+A\sum_{s=0}^{T_{1}-1}(z^{(s)})^{2}-C$
(284)

By assumption, we know that $C\leq z^{(0)}/2.$ This implies that for all
$z^{(t)}\geq z^{(0)}/2$ for all $t\geq 0.$ Plugging this in (284) yields:

$\displaystyle z^{(T_{1})}\geq z^{(0)}+\frac{A}{4}T_{1}(z^{(0)})^{2}-C$ (285)

From (285), we deduce that:

$\displaystyle T_{1}\leq 4\frac{z^{(T_{1})}-z^{(0)}+C}{A(z^{(0)})^{2}}.$ (286)

Now, we want to upper bound $z^{(T_{1})}-z^{(0)}$. Using (283), we deduce
that:

$\displaystyle\begin{cases}z^{(T_{1})}\geq
z^{(0)}+A\sum_{s=0}^{T_{1}-1}(z^{(s)})^{2}-C\\\ z^{(T_{1}-1)}\leq
z^{(0)}+A\sum_{s=0}^{T_{1}-2}(z^{(s)})^{2}+C\end{cases}.$ (287)

Combining the two equations in (287) yields

$\displaystyle z^{(T_{1})}-z^{(T_{1}-1)}\leq A(z^{(T_{1}-1)})^{2}+2C.$ (288)

Since $T_{1}$ is the first time where $z^{(T_{1})}\geq z^{(0)}$, we have
$z^{(T_{1}-1)}\leq z^{(0)}$. Plugging this in (288) leads to:

$\displaystyle z^{(T_{1})}\leq z^{(0)}+A(z^{(0)})^{2}+2C.$ (289)

Finally, using (289) in (286) and $C=o(z^{(0)})$ gives an upper bound on
$T_{1}.$

$\displaystyle T_{1}\leq 4+\frac{3C}{A(z^{(0)})^{2}}\leq
4+\frac{3}{A(z^{(0)})}.$ (290)

Now, let’s find a bound for $T_{n}$. Starting from the recursion, we have:

$\displaystyle\begin{cases}z^{(T_{n})}\geq
z^{(0)}+A\sum_{s=0}^{T_{n}-1}(z^{(s)})^{2}-C\\\ z^{(T_{n-1})}\leq
z^{(0)}+A\sum_{s=0}^{T_{n-1}-1}(z^{(s)})^{2}+C\end{cases}.$ (291)

We substract the two equations in (291), use $z^{(s)}\geq 2^{n-2}$ for $s\geq
T_{n-1}$ and obtain:

$\displaystyle z^{(T_{n})}-z^{(T_{n-1})}\geq
A\sum_{s=T_{n-1}}^{T_{n}-1}(z^{(s)})^{2}-2C\geq
2^{2(n-2)}(z^{(0)})^{2}A(T_{n}-T_{n-1})-2C.$ (292)

On the other hand, from the recursion, we have the following inequalities:

$\displaystyle\begin{cases}z^{(T_{n})}\leq
z^{(0)}+A\sum_{s=0}^{T_{n}-1}(z^{(s)})^{2}-C\\\ z^{(T_{n}-1)}\geq
z^{(0)}+A\sum_{s=0}^{T_{n}-2}(z^{(s)})^{2}-C\end{cases}.$ (293)

We substract the two equations in (293), use $z^{(T_{n}-1)}\leq
2^{n-1}z^{(0)}$ and upper bound $z^{(T_{n})}$ as follows.

$\displaystyle z^{(T_{n})}$ $\displaystyle\leq
z^{(T_{n}-1)}+A(z^{(T_{n}-1)})^{2}+2C\leq
2^{n-1}z^{(0)}+2^{2(n-1)}A(z^{(0)})^{2}+2C.$ (294)

Besides, we know that $z^{(T_{n-1})}\geq 2^{n-2}z^{(0)}$. Therefore, we upper
bound $z^{(T_{n})}-z^{(T_{n-1})}$ as

$\displaystyle z^{(T_{n})}-z^{(T_{n-1})}$ $\displaystyle\leq
2^{n-2}z^{(0)}+2^{2(n-1)}A(z^{(0)})^{2}+2C.$ (295)

Combining (292) and (295) yields:

$\displaystyle T_{n}$ $\displaystyle\leq
T_{n-1}+4+\frac{1}{2^{(n-2)}(z^{(0)})A}+\frac{4C}{2^{2(n-2)}(z^{(0)})^{2}A}$
(296)

We now sum (296) for $n=2,\dots,n$, use $C=o(z^{(0)})$ and then (290) to
obtain:

$\displaystyle T_{n}$ $\displaystyle\leq
T_{1}+4n+\frac{2}{(z^{(0)})A}+\frac{16C}{(z^{(0)})^{2}A}\leq
T_{1}+4n+\frac{18}{(z^{(0)})A}\leq 4(n+1)+\frac{21}{(z^{(0)})A}.$ (297)

Lastly, we know that $n$ satisfies $2^{n}z^{(0)}\geq\upsilon$ this implies
that we can set
$n=\left\lceil\frac{\log(\upsilon/z_{0})}{\log(2)}\right\rceil$ in (297). ∎

####  K.2.2 Bounds for GD+M

######  Lemma K.17 (Tensor Power Method for momentum).

Let $\gamma\in(0,1).$ Let $\\{c^{(t)}\\}_{t\geq 0}$ and
$\\{\mathcal{G}^{(t)}\\}$ be positive sequences defined by the following
recursions

$\displaystyle\begin{cases}\mathcal{G}^{(t+1)}=\gamma\mathcal{G}^{(t)}-\alpha^{3}(c^{(t)})^{2},\\\
c^{(t+1)}=c^{(t)}-\eta\mathcal{G}^{(t+1)}\end{cases},$

and respectively initialized by $z^{(0)}\geq 0$ and $\mathcal{G}^{(0)}=0$. Let
$\upsilon\in\mathbb{R}$ such that $z^{(0)}\leq\upsilon.$ Then, the time
$t_{0}$ such that $z^{(t)}\geq\upsilon$ is:

$\displaystyle
t_{0}=\frac{1}{1-\gamma}\left\lceil\frac{\log(\upsilon)}{\log(1+\delta)}\right\rceil+\frac{1+\delta}{\eta(1-e^{-1})\alpha^{3}c^{(0)}},$

where $\delta\in(0,1).$

###### Proof of Lemma K.17.

Let $\delta\in(0,1).$ We want to prove the following induction hypotheses:

  1. 1.

After
$T_{n}=\frac{n}{1-\gamma}+\sum_{j=0}^{n-2}\frac{\delta(\delta+1)^{j}}{\eta(1-e^{-1})\alpha^{3}c^{(0)}\sum_{\tau=0}^{j}e^{-(j-\tau)}(1+\delta)^{2\tau}}$
iterations, we have:

$\displaystyle-\mathcal{G}^{(T_{n})}\geq(1-e^{-1})\alpha^{3}(c^{(0)})^{2}\sum_{\tau=0}^{n-1}e^{-(n-1-\tau)}(1+\delta)^{2\tau}.$
(TPM-1)

  2. 2.

After
$T_{n}^{\prime}=\frac{n}{1-\gamma}+\sum_{j=0}^{n-1}\frac{\delta(\delta+1)^{j}}{\eta(1-e^{-1})\alpha^{3}c^{(0)}\sum_{\tau=0}^{j}e^{-(j-\tau)}(1+\delta)^{2\tau}}$,
we have:

$\displaystyle c^{(T_{n}^{\prime})}$ $\displaystyle\geq(1+\delta)^{n}c^{(0)}.$
(TPM-2)

Let’s first prove (TPM-1) and (TPM-2) for $n=1.$ First, by using the momentum
update, we have:

$\displaystyle-\mathcal{G}^{(T_{1})}$
$\displaystyle=(1-\gamma)\alpha^{3}\sum_{\tau=0}^{T_{1}-1}\gamma^{T_{1}-1-\tau}(c^{(\tau)})^{2}\geq\alpha^{3}(1-\gamma^{T_{0}})(c^{(0)})^{2}.$
(298)

Setting $T_{1}=1/(1-\gamma)$ and using $\gamma=1-\varepsilon$, we have
$1-\gamma^{\frac{1}{1-\gamma}}=1-\exp(\log(1-\varepsilon)/\varepsilon)=1-e^{-1}.$
Plugging this in (298) yields (TPM-1) for $n=1.$

Regarding (TPM-2), we use the iterate update to have:

$\displaystyle c^{(T_{1}^{\prime})}$
$\displaystyle=c^{(T_{1})}-\eta\sum_{\tau=T_{1}}^{T_{1}^{\prime}-1}\mathcal{G}^{(\tau)}$
$\displaystyle\geq
c^{(0)}+\eta\alpha^{3}(1-e^{-1})(c^{(0)})^{2}(T_{1}^{\prime}-T_{1}),$ (299)

where we used $c^{(T_{1})}\geq c^{(0)}$ and (298) to obtain (299). Since
$T_{1}^{\prime}+1$ is the first time where $c^{(t)}\geq(1+\delta)c^{(0)},$ we
further simplify (299) to obtain:

$\displaystyle T_{1}^{\prime}$
$\displaystyle=T_{1}+\frac{\delta}{\eta\alpha^{3}(1-e^{-1})c^{(0)}}=\frac{1}{1-\gamma}+\frac{\delta}{\eta\alpha^{3}(1-e^{-1})c^{(0)}}.$
(300)

We therefore obtained (TPM-2) for $n=1.$ Let’s now assume (TPM-1) and (TPM-2)
for $n$. We now want to prove these induction hypotheses for $n+1.$ First, by
using the momentum update, we have:

$\displaystyle-\mathcal{G}^{(T_{n+1})}$
$\displaystyle=-\gamma^{T_{n+1}-T_{n}^{\prime}}\mathcal{G}^{(T_{n}^{\prime})}+(1-\gamma)\alpha^{3}\sum_{\tau=T_{n}^{\prime}}^{T_{n+1}-1}\gamma^{T_{n+1}-1-\tau}(c^{(\tau)})^{2}.$
(301)

From (TPM-2) for $n$, we know that $c^{(t)}\geq(1+\delta)^{n}c^{(0)}$ for
$t>T_{n}^{\prime}$. Therefore, (301) becomes:

$\displaystyle-\mathcal{G}^{(T_{n+1})}$
$\displaystyle=-\gamma^{T_{n+1}-T_{n}^{\prime}}\mathcal{G}^{(T_{n}^{\prime})}+\alpha^{3}(1-\gamma^{T_{n+1}-T_{n}^{\prime}})(1+\delta)^{2n}(c^{(0)})^{2}.$
(302)

From (TPM-1), we know that
$-\mathcal{G}^{(T_{n}^{\prime})}\geq(1-e^{-1})\alpha^{3}(c^{(0)})^{2}\sum_{\tau=0}^{n-1}e^{-(n-1-\tau)}(1+\delta)^{2\tau}$
for $t\geq T_{n}.$ Therefore, we simplify (302) as:

$\displaystyle-\mathcal{G}^{(T_{n+1})}$
$\displaystyle\geq\gamma^{T_{n+1}-T_{n}^{\prime}}(1-e^{-1})\alpha^{3}(c^{(0)})^{2}\sum_{\tau=0}^{n-1}e^{-(n-1-\tau)}(1+\delta)^{2\tau}$
(303)
$\displaystyle+\alpha^{3}(1-\gamma^{T_{n+1}-T_{n}^{\prime}})(1+\delta)^{2n}(c^{(0)})^{2}.$

When we set $T_{n+1}$ as in (TPM-1), we have
$T_{n+1}-T_{n}^{\prime}=\frac{1}{1-\gamma}.$ Moreover, since
$\gamma=1-\varepsilon$, we have $\gamma^{\frac{1}{1-\gamma}}=e^{-1}$. Using
these two observations, (303) is thus equal to:

$\displaystyle-\mathcal{G}^{(T_{n+1})}$
$\displaystyle\geq(1-e^{-1})\alpha^{3}(c^{(0)})^{2}\sum_{\tau=0}^{n-1}e^{-(n-\tau)}(1+\delta)^{2\tau}$
$\displaystyle+\alpha^{3}(1-e^{-1})(1+\delta)^{2n}(c^{(0)})^{2}$
$\displaystyle=(1-e^{-1})\alpha^{3}(c^{(0)})^{2}\sum_{\tau=0}^{n}e^{-(n-\tau)}(1+\delta)^{2\tau}.$
(304)

We therefore proved (TPM-1) for $n+1.$ Now, let’s prove (TPM-2). We use the
iterates update and obtain:

$\displaystyle c^{(T_{n+1}^{\prime})}$
$\displaystyle=c^{(T_{n+1})}-\eta\sum_{\tau=T_{n+1}}^{T_{n+1}^{\prime}-1}\mathcal{G}^{(\tau)}$
$\displaystyle\geq(\delta+1)^{n}c^{(0)}+\eta(1-e^{-1})\alpha^{3}(c^{(0)})^{2}\sum_{\tau=0}^{n}e^{-(n-\tau)}(1+\delta)^{2\tau}(T_{n+1}-T_{n+1}^{\prime}),$
(305)

where we used $c^{(T_{n+1})}\geq(\delta+1)^{n}c^{(0)}$ and (304) in the last
inequality. Since $T_{n+1}^{\prime}+1$ is the first time where
$c^{(t)}\geq(1+\delta)^{n+1}c^{(0)},$ we further simplify (305) to obtain:

$\displaystyle T_{n+1}^{\prime}$
$\displaystyle=T_{n+1}+\frac{\delta(\delta+1)^{n-1}}{\eta(1-e^{-1})\alpha^{3}(c^{(0)})^{2}\sum_{\tau=0}^{n}e^{-(n-\tau)}(1+\delta)^{2\tau}}$
$\displaystyle=\frac{n+1}{1-\gamma}+\sum_{j=0}^{n-1}\frac{\delta(\delta+1)^{j}}{\eta(1-e^{-1})\alpha^{3}c^{(0)}\sum_{\tau=0}^{j}e^{-(j-\tau)}(1+\delta)^{2\tau}}$
$\displaystyle+\frac{\delta(\delta+1)^{n}}{\eta(1-e^{-1})\alpha^{3}(c^{(0)})^{2}\sum_{\tau=0}^{n}e^{-(n-\tau)}(1+\delta)^{2\tau}}$
$\displaystyle=\frac{n+1}{1-\gamma}+\sum_{j=0}^{n}\frac{\delta(\delta+1)^{j}}{\eta(1-e^{-1})\alpha^{3}c^{(0)}\sum_{\tau=0}^{j}e^{-(j-\tau)}(1+\delta)^{2\tau}}.$
(306)

We therefore proved (TPM-2) for $n+1.$

Let’s now obtain an upper bound on $T_{n}^{\prime}.$ We have:

$\displaystyle T_{n}^{\prime}$
$\displaystyle\leq\frac{n}{1-\gamma}+\frac{\delta}{\eta(1-e^{-1})\alpha^{3}c^{(0)}}\sum_{j=0}^{n-1}\frac{1}{(1+\delta)^{j}}$
$\displaystyle\leq\frac{n}{1-\gamma}+\frac{1+\delta}{\eta(1-e^{-1})\alpha^{3}c^{(0)}}:=\mathscr{T}_{n}.$
(307)

Finally, we choose $n$ such that $(1+\delta)^{n}\geq\upsilon$ or equivalently,
$n=\left\lceil\frac{\log(\upsilon)}{\log(1+\delta)}\right\rceil$. Plugging
this choice in $\mathscr{T}_{n}$ yields the desired bound. ∎

###  K.3 Optimization lemmas

######  Definition K.1 (Smooth function).

Let $f\colon\mathbb{R}^{n\times d}\rightarrow\mathbb{R}$. $f$ is
$\beta$-smooth if $\|\nabla f(\bm{X})-\nabla
f(\bm{Y})\|_{2}\leq\beta\|\bm{X}-\bm{Y}\|_{2},$ for all
$X,Y\in\mathbb{R}^{n\times d}.$ A consequence of the smoothness is the
inequality:

$\displaystyle f(\bm{X})\leq f(\bm{Y})+\langle\nabla
f(\bm{Y}),\bm{X}-\bm{Y}\rangle+\frac{L}{2}\|\bm{X}-\bm{Y}\|_{2}^{2},\quad\text{for
all }\bm{X},\bm{Y}\in\mathbb{R}^{n\times d}.$

######  Lemma K.18 (Descent lemma for GD).

Let $f\colon\mathbb{R}^{n\times d}\rightarrow\mathbb{R}$ be a $\beta$-smooth
function. Let $\bm{W}^{(t+1)}\in\mathbb{R}^{n\times d}$ be an iterate of $GD$
with learning rate $\eta\in(0,1/L).$ Then, we have

$\displaystyle f(\bm{W}^{(t+1)})\leq f(\bm{W}^{(t)})-\frac{\eta}{2}\|\nabla
f(\bm{W}^{(t)})\|_{2}^{2}.$

###### Proof of Lemma K.18.

By applying the definition of smooth functions and the GD update, we have:

$\displaystyle f(\bm{W}^{(t+1)})$ $\displaystyle\leq
f(\bm{W}^{(t)})+\langle\nabla
f(\bm{W}^{(t)}),\bm{W}^{(t+1)}-\bm{W}^{(t)}\rangle+\frac{L}{2}\|\bm{W}^{(t+1)}-\bm{W}^{(t)}\|_{2}^{2}$
$\displaystyle=f(\bm{W}^{(t)})-\eta\|\nabla
f(\bm{W}^{(t)})\|_{2}^{2}+\frac{L\eta^{2}}{2}\|\nabla
f(\bm{W}^{(t)})\|_{2}^{2}.$ (308)

Setting $\eta<1/L$ in (308) leads to the expected result.

∎

######  Lemma K.19 (Sublinear convergence).

Let $\mathscr{T}\geq 0$. Let $(x_{t})_{t>\mathscr{T}}$ be a non-negative
sequence that satisfies the recursion: $x^{(t+1)}\leq x^{(t)}-A(x^{(t)})^{2},$
for $A>0.$ Then, it is bounded at a time $t>\mathscr{T}$ as

$\displaystyle x^{(t)}\leq\frac{1}{A(t-\mathscr{T})}.$ (309)

###### Proof of Lemma K.19.

Let $\tau\in(\mathscr{T},t]$. By multiplying each side of the recursion by
$(x^{(\tau)}x^{(\tau+1)})^{-1}$, we get:

$\displaystyle\frac{Ax^{(\tau)}}{x^{(\tau+1)}}\leq\frac{1}{x^{(\tau+1)}}-\frac{1}{x^{(\tau)}}.$
(310)

Besides, the update rule indicates that $x^{(\tau)}$ is non-increasing i.e.
$x^{(\tau+1)}\leq x^{(\tau)}.$ Using this fact in (310) yields:

$\displaystyle A\leq\frac{1}{x^{(\tau+1)}}-\frac{1}{x^{(\tau)}}.$ (311)

Now, we sum up (311) for $\tau=\mathscr{T},\dots,t-1$ and obtain:

$\displaystyle
A(t-\mathscr{T})\leq\frac{1}{x^{(t)}}-\frac{1}{x^{(\mathscr{T})}}\leq\frac{1}{x^{(t)}}.$
(312)

Inverting (312) yields the expected result. ∎

###  K.4 Other useful lemmas

####  K.4.1 Logarithmic inequalities

######  Lemma K.20 (Connection between derivative and loss).

Let $a_{1},\dots,a_{m}\in\mathbb{R}$ such that $-\delta\leq a_{i}\leq A$ where
$A,\delta>0$. Assume that $\sum_{i=1}^{m}a_{i}\in(C_{-},C_{+})$, where
$C_{+},C_{-}>0$.Then, the following inequality holds:

$\displaystyle\frac{0.05e^{-6mA^{2}\delta}}{C_{+}\left(1+\frac{m^{2}\delta^{2}}{C_{-}^{2}}\right)}\log\left(1+e^{-\sum_{i=1}^{m}a_{i}^{3}}\right)\leq\frac{\sum_{i=1}^{m}a_{i}^{2}}{1+\exp(\sum_{i=1}^{m}a_{i}^{3})}\leq\frac{20me^{6mA^{2}\delta}}{C_{-}}\log\left(1+e^{-\sum_{i=1}^{m}a_{i}^{3}}\right).$

###### Proof of Lemma K.20.

We apply Lemma K.21 to the sequence $a_{i}+\delta$ and obtain:

$\displaystyle\frac{0.1}{C+}\log\left(1+\exp\left(-\sum_{i=1}^{m}(a_{i}+\delta)^{3}\right)\right)$
$\displaystyle\leq\frac{\sum_{i=1}^{m}(a_{i}+\delta)^{2}}{1+\exp(\sum_{i=1}^{m}(a_{i}+\delta)^{3})}$
(313)
$\displaystyle\leq\frac{10m}{C_{-}}\log\left(1+\exp\left(-\sum_{i=1}^{m}(a_{i}+\delta)^{3}\right)\right).$

We apply Lemma K.24 to further simplify (313).

$\displaystyle\frac{0.1e^{-\sum_{i=1}^{m}(3a_{i}^{2}\delta+3a_{i}\delta^{2}+\delta^{3})}}{C+}\log\left(1+\exp\left(-\sum_{i=1}^{m}a_{i}^{3}\right)\right)$
(314)
$\displaystyle\leq\frac{\sum_{i=1}^{m}(a_{i}+\delta)^{2}}{1+\exp(\sum_{i=1}^{m}(a_{i}+\delta)^{3})}$
$\displaystyle\leq\frac{10m(1+e^{-\sum_{i=1}^{m}(3a_{i}^{2}\delta+3a_{i}\delta^{2}+\delta^{3})})}{C_{-}}\log\left(1+\exp\left(-\sum_{i=1}^{m}a_{i}^{3}\right)\right).$

We remark that the term inside the exponential in (314) can be bounded as:

$\displaystyle 0\leq
2\sum_{i=1}^{m}a_{i}^{2}\delta\leq\sum_{i=1}^{m}(3a_{i}^{2}\delta-2\delta^{3})\leq\sum_{i=1}^{m}(3a_{i}^{2}\delta+3a_{i}\delta^{2}+\delta^{3})\leq
6\sum_{i=1}^{m}a_{i}^{2}\delta\leq 6A^{2}m\delta.$ (315)

Plugging (315) in (314) yields:

$\displaystyle\frac{0.1e^{-6mA^{2}\delta}}{C+}\log\left(1+\exp\left(-\sum_{i=1}^{m}a_{i}^{3}\right)\right)$
(316)
$\displaystyle\leq\frac{\sum_{i=1}^{m}(a_{i}+\delta)^{2}}{1+\exp(\sum_{i=1}^{m}(a_{i}+\delta)^{3})}$
$\displaystyle\leq\frac{20m}{C_{-}}\log\left(1+\exp\left(-\sum_{i=1}^{m}a_{i}^{3}\right)\right).$

Lastly, we need to bound the term in the middle in (316). On one hand, we
have:

$\displaystyle\sum_{i=1}^{m}(a_{i}+\delta)^{2}$
$\displaystyle=2\sum_{i=1}^{m}a_{i}^{2}+2m\delta^{2}\leq
2\left(1+\frac{m^{2}\delta^{2}}{\left(\sum_{i=1}^{m}a_{i}\right)^{2}}\right)\sum_{i=1}^{m}a_{i}^{2}\leq
2\left(1+\frac{m^{2}\delta^{2}}{C_{-}^{2}}\right)\sum_{i=1}^{m}a_{i}^{2}.$
(317)

Besides, since $x\mapsto x^{3}$ is non-decreasing, we have the following lower
bound:

$\displaystyle\sum_{i=1}^{m}(a_{i}+\delta)^{3}\geq\sum_{i=1}^{m}a_{i}^{3}.$
(318)

Combining (317) and (318) yields:

$\displaystyle\frac{\sum_{i=1}^{m}(a_{i}+\delta)^{2}}{1+\exp(\sum_{i=1}^{m}(a_{i}+\delta)^{3})}\leq
2\left(1+\frac{m^{2}\delta^{2}}{C_{-}^{2}}\right)\frac{\sum_{i=1}^{m}a_{i}^{2}}{1+\exp(\sum_{i=1}^{m}a_{i}^{3})}.$
(319)

On the other hand, we have:

$\displaystyle\sum_{i=1}^{m}(a_{i}+\delta)^{2}$
$\displaystyle\geq\sum_{i=1}^{m}a_{i}^{2}+2\delta\sum_{i=1}^{m}a_{i}\geq\sum_{i=1}^{m}a_{i}^{2}+2\delta
C_{-}\geq\sum_{i=1}^{m}a_{i}^{2}.$ (320)

Besides, using (315), we have:

$\displaystyle\sum_{i=1}^{m}(a_{i}+\delta)^{3}\leq\sum_{i=1}^{m}a_{i}^{3}+6A^{2}m\delta.$
(321)

Thus, using (320) and (321) yields:

$\displaystyle\frac{\sum_{i=1}^{m}(a_{i}+\delta)^{2}}{1+\exp(\sum_{i=1}^{m}(a_{i}+\delta)^{3})}\geq\frac{e^{-6mA^{2}\delta}\sum_{i=1}^{m}a_{i}^{2}}{1+\exp(\sum_{i=1}^{m}a_{i}^{3})}.$
(322)

Finally, we obtain the desired result by combining (316), (319) and (322).

∎

######  Lemma K.21 (Connection between derivative and loss for positive
sequences).

Let $a_{1},\dots,a_{m}\in\mathbb{R}$ such that $a_{i}\geq 0$. Assume that
$\sum_{i=1}^{m}a_{i}\in(C_{-},C_{+})$, where $C_{+},C_{-}>0.$ Then, the
following inequality holds:

$\displaystyle\frac{0.1}{C+}\log\left(1+\exp\left(-\sum_{i=1}^{m}a_{i}^{3}\right)\right)\leq\frac{\sum_{i=1}^{m}a_{i}^{2}}{1+\exp(\sum_{i=1}^{m}a_{i}^{3})}\leq\frac{10m}{C_{-}}\log\left(1+\exp\left(-\sum_{i=1}^{m}a_{i}^{3}\right)\right).$

###### Proof of Lemma K.21.

We first remark that:

$\displaystyle\frac{\sum_{i=1}^{m}a_{i}^{2}}{1+\exp(\sum_{i=1}^{m}a_{i}^{3})}$
$\displaystyle=\frac{\left(\sum_{i=1}^{m}a_{i}^{2}\right)\left(\sum_{j=1}^{m}a_{j}\right)}{\left(1+\exp(\sum_{i=1}^{m}a_{i}^{3})\right)\left(\sum_{j=1}^{m}a_{j}\right)}$
$\displaystyle=\frac{\sum_{i=1}^{m}a_{i}^{3}+\sum_{i=1}^{m}\sum_{j\neq
i}a_{i}^{2}a_{j}}{\left(1+\exp(\sum_{i=1}^{m}a_{i}^{3})\right)\left(\sum_{j=1}^{m}a_{j}\right)}.$
(323)

##### Upper bound.

We upper bound (323) by successively applying $\sum_{i=1}^{n}a_{i}>C_{-}$ and
$a_{i}>0$ for all $i$:

$\displaystyle\frac{\sum_{i=1}^{m}a_{i}^{2}}{1+\exp(\sum_{i=1}^{m}a_{i}^{3})}$
$\displaystyle\leq\frac{\sum_{i=1}^{m}a_{i}^{3}+\sum_{i=1}^{m}\sum_{j\neq
i}a_{i}^{2}a_{j}}{C_{-}\left(1+\exp(\sum_{i=1}^{m}a_{i}^{3})\right)}$
$\displaystyle\leq\frac{\sum_{i=1}^{m}a_{i}^{3}+\sum_{i=1}^{m}\sum_{j=1}^{m}a_{i}^{2}a_{j}}{C_{-}\left(1+\exp(\sum_{i=1}^{m}a_{i}^{3})\right)}$
(324)

where we used $a_{i}>0$ for all $i$ in (323). By applying the rearrangement
inequality to (324), we obtain:

$\displaystyle\frac{\sum_{i=1}^{m}a_{i}^{2}}{1+\exp(\sum_{i=1}^{m}a_{i}^{3})}$
$\displaystyle\leq\frac{m}{C_{-}}\frac{\sum_{i=1}^{m}a_{i}^{3}}{1+\exp(\sum_{i=1}^{m}a_{i}^{3})}.$
(325)

We obtain the final bound by applying Lemma K.22 to (325).

##### Lower bound.

We lower bound (323) by using $\sum_{i=1}^{n}a_{i}\leq C_{+}$ and
$\sum_{i=1}^{m}\sum_{j\neq i}a_{i}^{2}a_{j}$:

$\displaystyle\frac{\sum_{i=1}^{m}a_{i}^{2}}{1+\exp(\sum_{i=1}^{m}a_{i}^{3})}$
$\displaystyle\geq\frac{\sum_{i=1}^{m}a_{i}^{3}+\sum_{i=1}^{m}\sum_{j\neq
i}a_{i}^{2}a_{j}}{C_{+}\left(1+\exp(\sum_{i=1}^{m}a_{i}^{3})\right)}$
$\displaystyle\geq\frac{\sum_{i=1}^{m}a_{i}^{3}}{C_{+}\left(1+\exp(\sum_{i=1}^{m}a_{i}^{3})\right)}.$
(326)

We obtain the final bound by applying Lemma K.22 to (326). ∎

######  Lemma K.22 (Connection between derivative and loss).

Let $x>0.$ Then, we have:

$\displaystyle 0.1\log(1+\exp(-x))\leq\mathfrak{S}(x)\leq 10\log(1+\exp(-x))$
(327)

######  Lemma K.23.

Let $(x^{(t)})_{t\geq 0}$ be a non-negative sequence. Let $A>0.$ Assume that
$\sum_{\tau=0}^{T}x^{(\tau)}\leq A.$ Then, there exists a time
$\mathscr{T}\in[T]$ such that $x^{(\mathscr{T})}\leq A/T.$

###### Proof of Lemma K.23.

Assume by contradiction that for all $\tau\in[T]$, $x^{(\tau)}>A/T$. By
summing up $x^{\tau}$, we obtain $\sum_{\tau=0}^{T}x^{(\tau)}>A.$ This
contradicts the assumption that $\sum_{\tau=0}^{T}x^{(\tau)}\leq A.$

∎

######  Lemma K.24 (Log inequalities).

Let $x,y>0.$ Then, the following inequalities holds:

  1. 1.

Assume that $y\leq x.$ We have:

$\displaystyle\log(1+xy)\leq(1+y)\log(1+x).$

  2. 2.

Assume $y<1$. We have:

$\displaystyle y\log(1+x)\leq\log(1+xy).$

###### Proof of Lemma K.24.

We first remark that:

$\displaystyle\log(1+xy)-\log(1+x)$
$\displaystyle=\log\left(\frac{1+xy}{1+x}\right)$
$\displaystyle=\log\left(1+\frac{x(y-1)}{1+x}\right).$ (328)

From (328), we deduce an upper bound as:

$\displaystyle\log(1+xy)-\log(1+x)\leq\log\left(1+\frac{x(y+1)}{1+x}\right).$
(329)

Successively using the inequalities $\log(1+x)\leq x$ and
$\frac{x}{1+x}\leq\log(1+x)$ for $x>-1$ in (329) yields:

$\displaystyle\log(1+xy)-\log(1+x)$
$\displaystyle\leq(1+y)\frac{x}{1+x}\leq(1+y)\log(1+x).$

This proves item 1 of the Lemma. Let’s now prove item 2. Using $a^{z}\leq
1+(a-1)z$ for $z\in(0,1)$ and $a\geq 1$, we know that:

$\displaystyle(1+x)^{y}\leq 1+xy.$ (330)

Since $\log$ is non-decreasing, applying $\log$ to (330) proves item 2.

∎

In Appendix J, we need to bound the sum $\sum_{s=1}^{t}\frac{\gamma^{t-s}}{s}$
for $\gamma<1.$ We derive such bound here.

######  Lemma K.25.

Let $t\geq 1$. Then, we have:

$\displaystyle\sum_{s=1}^{t}\frac{\gamma^{t-s}}{s}\leq\gamma^{t-1}+\gamma^{t/2}\log\left(\frac{t}{2}\right)+\frac{2}{t}\frac{1}{1-\gamma}.$

###### Proof of Lemma K.25.

Let $t=1$. Then, we have:

$\displaystyle\sum_{s=1}^{t}\frac{\gamma^{t-s}}{s}=1\leq\gamma^{0}+\gamma^{1/2}\log\left(\frac{1}{2}\right)+\frac{2}{1-\gamma},$
(331)

given our choice of $\gamma$. Let $t\geq 2.$ We split the sum in two parts as
as follows.

$\displaystyle\sum_{s=1}^{t}\frac{\gamma^{t-s}}{s}-\gamma^{t-1}$
$\displaystyle=\sum_{s=2}^{t}\frac{\gamma^{t-s}}{s}$
$\displaystyle=\sum_{s=2}^{\lfloor
t/2\rfloor}\frac{\gamma^{t-s}}{s}+\sum_{s=\lfloor
t/2\rfloor+1}^{t}\frac{\gamma^{t-s}}{s}$ $\displaystyle\leq\gamma^{t-\lfloor
t/2\rfloor}\sum_{s=2}^{\lfloor t/2\rfloor}\frac{1}{s}+\frac{1}{\lfloor
t/2\rfloor+1}\sum_{s=\lfloor t/2\rfloor+1}^{t}\gamma^{t-s}$
$\displaystyle\leq\gamma^{t/2}\sum_{s=2}^{\lfloor
t/2\rfloor}\frac{1}{s}+\frac{2}{t}\sum_{u=0}^{t-\lfloor
t/2\rfloor-1}\gamma^{u}$ (332)
$\displaystyle\leq\gamma^{t/2}\log\left(\frac{t}{2}\right)+\frac{2}{t}\frac{1}{1-\gamma},$
(333)

where we used the harmonic series inequality
$\sum_{s=2}^{\mathscr{T}}1/s\leq\log(\mathscr{T})$,
$\sum_{u=0}^{\mathscr{T}}\gamma^{u}\leq 1/(1-\gamma)$ and $\lfloor
t/2\rfloor\leq t/2$ in (333).

∎