$\displaystyle=\frac{1}{m}\sum_{r\in[m]}\sigma\big{(}\langle{\mathbf{w}_{y,r}^{(T_{(\mathbf{v}),\delta,L}-1)}},{y\mathbf{v}}\rangle\big{)}\cdot\left(1+\frac{2\eta\|\mathbf{v}\|_{2}^{2}}{m}\cdot\big{(}1-yf(\mathbf{x};\mathbf{W}^{(T_{(\mathbf{v}),\delta,L}-1)})\big{)}\right)$
(B.148)
$\displaystyle\geq\delta\cdot\left(1+\frac{2\eta\|\mathbf{v}\|_{2}^{2}}{m}\cdot(1-3)\right)$
(B.149)
$\displaystyle\geq\delta\cdot\left(1-2\cdot\frac{\|\mathbf{v}\|_{2}^{2}}{\|\mathbf{u}\|_{2}^{2}}\right)$
(B.150) $\displaystyle\geq\frac{3}{4}\delta.$ (B.151)

Last inequality uses the fact that
$\|\mathbf{v}\|_{2}^{2}/\|\mathbf{u}\|_{2}^{2}\leq 1/4$. This shows that the
sequence does not fall below $3\delta/4$ at the step
$T_{(\mathbf{v}),\delta,L}$. In the sequel, we study the behavior of the
sequence after step $T_{(\mathbf{v}),\delta,L}$.

Firstly, by Inequalities (B.134) and (B.135) with
$t=T_{(\mathbf{v}),\delta,L}$, we obtain that the negative parts satisfy

$\displaystyle\min_{r\in[m]}\langle{\mathbf{w}_{-y,r}^{(T_{(\mathbf{v}),\delta,L})}},{-y\mathbf{u}}\rangle\geq-{\sqrt{2\log(16m/p)}\cdot\sigma_{0}\|\mathbf{u}\|_{2}},$
(B.152)
$\displaystyle\min_{r\in[m]}\langle{\mathbf{w}_{-y,r}^{(T_{(\mathbf{v}),\delta,L})}},{-y\mathbf{v}}\rangle\geq-{\sqrt{2\log(16m/p)}\cdot\sigma_{0}\|\mathbf{v}\|_{2}}.$
(B.153)

which by definition of $E_{t}$ in (B.139) implies that

$\displaystyle E_{T_{(\mathbf{v}),\delta,L}}\leq
2\left({\sqrt{2\log(16m/p)}\cdot\sigma_{0}\|\mathbf{u}\|_{2}}\right)^{2}\ll
1.$ (B.154)

For the positive part, we have that

$\displaystyle\max_{r\in[m]}\langle{\mathbf{w}_{y,r}^{(T_{(\mathbf{v}),\delta,L})}},{y\mathbf{u}}\rangle<\max_{r\in[m]}\langle{\mathbf{w}_{y,r}^{(\bar{T}_{k^{*}})}},{y\mathbf{u}}\rangle<1.5\cdot(1.05\beta^{*}_{\mathbf{u}}m)^{1/2},$
(B.155)

and by the same argument as Inequality (B.72) we can obtain the lower bound of
$\max_{r\in[m]}\langle{\mathbf{w}_{y,r}^{(T_{(\mathbf{v}),\delta,L})}},{y\mathbf{u}}\rangle$,

$\displaystyle\max_{r\in[m]}\langle{\mathbf{w}_{y,r}^{(T_{(\mathbf{v}),\delta,L})}},{y\mathbf{u}}\rangle$
$\displaystyle\geq\max_{r\in[m]}\langle{\mathbf{w}_{y,r}^{(T_{(\mathbf{v}),\delta,L}-1)}},{y\mathbf{u}}\rangle\left(1+\frac{2\eta\|\mathbf{u}\|_{2}^{2}}{m}\big{(}1-yf(\mathbf{x};\mathbf{W}^{(T_{(\mathbf{v}),\delta,L}-1)})\big{)}\right)$
(B.156) $\displaystyle\geq
0.2\cdot\big{(}\beta^{*}_{\mathbf{u}}m\big{)}^{1/2},$ (B.157)

and finally for $t\in[T_{(\mathbf{v}),\delta,L},T_{(\mathbf{v})}^{+,2}]$, we
have that

$\displaystyle\frac{1}{m}\sum_{r}\sigma(\langle{\mathbf{w}_{y,r}^{(t)}},{y\mathbf{v}}\rangle)<\delta.$
(B.158)

With all these initial conditions (B.154), (B.155), (B.157), and (B.158), one
can then consider all the steps $\underaccent{\bar}{T}_{k^{\prime}}$,
$\bar{T}_{k^{\prime}}>T_{(\mathbf{v}),\delta,L}$ and apply an inductive
argument exactly the same as in the proof of Lemma B.6 to conclude that for
all $t\in[T_{(\mathbf{v}),\delta,L},T_{(\mathbf{v})}^{+,2}]$ it holds that

$\displaystyle 0.2\cdot(\beta^{*}_{\mathbf{u}}m)^{1/2}$
$\displaystyle\leq\max_{r}\langle{\mathbf{w}_{y,r}^{(t)}},{y\mathbf{u}}\rangle\leq
1.5\cdot(1.05\beta^{*}_{\mathbf{u}}m)^{1/2},$ (B.159)
$\displaystyle\min_{r}\langle{-\mathbf{w}_{-y,r}^{(t)}},{-y\mathbf{u}}\rangle$
$\displaystyle>-{\sqrt{2\log(16m/p)}\cdot\sigma_{0}\|\mathbf{u}\|_{2}},$
(B.160)
$\displaystyle\min_{r}\langle{-\mathbf{w}_{-y,r}^{(t)}},{-y\mathbf{v}}\rangle$
$\displaystyle>-{\sqrt{2\log(16m/p)}\cdot\sigma_{0}\|\mathbf{v}\|_{2}},$
(B.161) $\displaystyle 0$ $\displaystyle\leq
yf(\mathbf{x};\mathbf{W}^{(t)})\leq 3,$ (B.162)

and the sign stability is also true throughout
$t\in[T_{(\mathbf{v}),\delta,L},T_{(\mathbf{v})}^{+,2}]$. Therefore, Lemma B.7
and (B.151) implies that for any
$t\in[T_{(\mathbf{v}),\delta,L},T_{(\mathbf{v})}^{+,2}]$, it holds that

$\displaystyle\frac{1}{m}\sum_{r}\sigma\big{(}\langle{\mathbf{w}_{y,v}^{(t)}},{y\mathbf{v}}\rangle\big{)}\geq$
$\displaystyle\frac{1}{m}\sum_{r}\sigma\big{(}\langle{\mathbf{w}_{y,v}^{(T_{(\mathbf{v}),\delta,L})}},{y\mathbf{v}}\rangle\big{)}\cdot\exp\left\\{-2\cdot\frac{\|\mathbf{v}\|_{2}^{2}}{\|\mathbf{u}\|_{2}^{2}}\cdot\frac{1.5\sqrt{1.05}}{\sqrt{1.05-\delta}}\right\\}\geq\frac{1}{2}\delta.$
(B.163)

In conclusion, we have obtained that

$\displaystyle\frac{1}{m}\sum_{r\in[m]}\sigma\big{(}\langle{\mathbf{w}_{y,r}},{y\mathbf{v}}\rangle\big{)}\geq\delta/2,\quad\forall
t\in[T_{(\mathbf{v}),\delta,L},T_{(\mathbf{v})}^{+,2}].$ (B.164)

If $T_{(\mathbf{v})}^{+,2}\neq+\infty$, repeat the above argument and we can
finish the proof of Proposition B.8. ∎

####  B.6.2 Proof of Proposition B.9

###### Proof of Proposition B.9.

We continue with the notation $\tilde{\eta}=2\eta\|\mathbf{u}\|_{2}^{2}/m$.
Define the function

$\displaystyle
h_{\tilde{\eta}}(z)\coloneqq\big{(}1+\tilde{\eta}(1-z)\big{)}^{2}\cdot z.$
(B.165)

Note that $\|\mathbf{v}\|_{2}^{2}\leq\|\mathbf{u}\|_{2}^{2}$ and that

$\displaystyle\frac{2\eta\|\mathbf{u}\|_{2}^{2}}{m}\cdot\big{(}1-yf(\mathbf{x};\mathbf{W}^{(\bar{T}_{k}-1)})\big{)}<\frac{2\eta\|\mathbf{u}\|_{2}^{2}}{m}<1,$
(B.166)

from the definition of $\bar{T}_{k}-1$. Thus we have the following,

$\displaystyle yf(\mathbf{x},y;\mathbf{W}^{(\bar{T}_{k})})$ (B.167)
$\displaystyle\qquad=\frac{1}{m}\sum_{r\in[m]}\sigma\big{(}\langle{\mathbf{w}_{y,r}^{(\bar{T}_{k}-1)}},{y\mathbf{u}}\rangle\big{)}\cdot\left(1+\frac{2\eta\|\mathbf{u}\|_{2}^{2}}{m}\cdot\big{(}1-yf(\mathbf{x};\mathbf{W}^{(\bar{T}_{k}-1)})\big{)}\right)^{2}$
(B.168)
$\displaystyle\qquad\qquad+\frac{1}{m}\sum_{r\in[m]}\sigma\big{(}\langle{\mathbf{w}_{y,r}^{(\bar{T}_{k}-1)}},{y\mathbf{v}}\rangle\big{)}\cdot\left(1+\frac{2\eta\|\mathbf{v}\|_{2}^{2}}{m}\cdot\big{(}1-yf(\mathbf{x};\mathbf{W}^{(\bar{T}_{k}-1)})\big{)}\right)^{2}$
(B.169)
$\displaystyle\qquad\qquad-\frac{1}{m}\sum_{r\in[m]}\sigma\big{(}-\langle{\mathbf{w}_{-y,r}^{(\bar{T}_{k}-1)}},{-y\mathbf{u}}\rangle\big{)}\cdot\left(1-\frac{2\eta\|\mathbf{u}\|_{2}^{2}}{m}\cdot\big{(}1-yf(\mathbf{x};\mathbf{W}^{(\bar{T}_{k}-1)})\big{)}\right)^{2}$
(B.170)
$\displaystyle\qquad\qquad-\frac{1}{m}\sum_{r\in[m]}\sigma\big{(}-\langle{\mathbf{w}_{-y,r}^{(\bar{T}_{k}-1)}},{-y\mathbf{v}}\rangle\big{)}\cdot\left(1-\frac{2\eta\|\mathbf{v}\|_{2}^{2}}{m}\cdot\big{(}1-yf(\mathbf{x};\mathbf{W}^{(\bar{T}_{k}-1)})\big{)}\right)^{2}$
(B.171)
$\displaystyle\qquad\leq\frac{1}{m}\sum_{r\in[m]}\Big{(}\sigma\big{(}\langle{\mathbf{w}_{y,r}^{(\bar{T}_{k}-1)}},{y\mathbf{u}}\rangle\big{)}+\sigma\big{(}\langle{\mathbf{w}_{y,r}^{(\bar{T}_{k}-1)}},{y\mathbf{v}}\rangle\big{)}\Big{)}\cdot\left(1+\frac{2\eta\|\mathbf{u}\|_{2}^{2}}{m}\cdot\big{(}1-yf(\mathbf{x};\mathbf{W}^{(\bar{T}_{k}-1)})\big{)}\right)^{2}$
(B.172)
$\displaystyle\qquad\qquad-\frac{1}{m}\sum_{r\in[m]}\Big{(}\sigma\big{(}-\langle{\mathbf{w}_{-y,r}^{(\bar{T}_{k}-1)}},{-y\mathbf{u}}\rangle\big{)}+\sigma\big{(}-\langle{\mathbf{w}_{-y,r}^{(\bar{T}_{k}-1)}},{-y\mathbf{v}}\rangle\big{)}\Big{)}$
(B.173)
$\displaystyle\qquad\qquad\qquad\cdot\left(1-\frac{2\eta\|\mathbf{u}\|_{2}^{2}}{m}\cdot\big{(}1-yf(\mathbf{x};\mathbf{W}^{(\bar{T}_{k}-1)})\big{)}\right)^{2}$
(B.174)
$\displaystyle\qquad=yf(\mathbf{x};\mathbf{W}^{(\bar{T}_{k}-1)})\cdot\left(1+\tilde{\eta}\big{(}1-yf(\mathbf{x};\mathbf{W}^{(\bar{T}_{k}-1)})\big{)}\right)^{2}$
(B.175)
$\displaystyle\qquad\qquad+\frac{1}{m}\sum_{r\in[m]}\Big{(}\sigma\big{(}-\langle{\mathbf{w}_{-y,r}^{(\bar{T}_{k}-1)}},{-y\mathbf{u}}\rangle\big{)}+\sigma\big{(}-\langle{\mathbf{w}_{-y,r}^{(\bar{T}_{k}-1)}},{-y\mathbf{v}}\rangle\big{)}\Big{)}\cdot\underbrace{\left(2\tilde{\eta}\big{(}1-yf(\mathbf{x};\mathbf{W}^{(\bar{T}_{k}-1)})\big{)}\right)^{2}}_{<2\tilde{\eta}<2}$
(B.176) $\displaystyle\qquad\leq
yf(\mathbf{x};\mathbf{W}^{(\bar{T}_{k}-1)})\cdot\left(1+\tilde{\eta}\big{(}1-yf(\mathbf{x};\mathbf{W}^{(\bar{T}_{k}-1)})\big{)}\right)^{2}+2E_{\bar{T}_{k}-1}.$
(B.177)

Thus by (B.177) we have proved the second conclusion of Proposition B.9. In
the following, we prove the first conclusion of Proposition B.9.

By Assumption B.2, we know that
$yf(\mathbf{x};\mathbf{W}^{(\bar{T}_{k})})>1+\delta$. The definition of
$T_{(\mathbf{v})}$ along with with Inequality (B.177) imply that

$\displaystyle
h_{\tilde{\eta}}\big{(}f(\mathbf{x};\mathbf{W}^{(\bar{T}_{k}-1)})\big{)}=yf(\mathbf{x};\mathbf{W}^{(\bar{T}_{k}-1)})\cdot\left(1+\tilde{\eta}\big{(}1-yf(\mathbf{x};\mathbf{W}^{(\bar{T}_{k}-1)})\big{)}\right)^{2}\geq
1+\delta-\delta=1.$ (B.178)

Now it suffices to consider the equation $h_{\tilde{\eta}}-1=0$, and one can
easily verify that it has three roots

$\displaystyle z_{1}$ $\displaystyle=1,$ (B.179) $\displaystyle z_{2}$
$\displaystyle=\frac{\tilde{\eta}+2-\sqrt{\tilde{\eta}^{2}+4\tilde{\eta}}}{2\tilde{\eta}},$
(B.180) $\displaystyle z_{3}$
$\displaystyle=\frac{\tilde{\eta}+2+\sqrt{\tilde{\eta}^{2}+4\tilde{\eta}}}{2\tilde{\eta}}>\frac{2\tilde{\eta}+2}{2\tilde{\eta}}>1.$
(B.181)

And the second root $z_{2}<1$ if and only if $\tilde{\eta}>1/2$.

Now if $0<\tilde{\eta}\leq 1/2$, then $z_{1}\leq z_{2}<z_{3}$, and then
$h(z)<1$ for $z<z_{1}=1$. Therefore Inequality (B.178) implies that
$yf(\mathbf{x};\mathbf{W}^{(\bar{T}_{k}-1)})\geq z_{1}=1$, and recursively
implies that $yf(\mathbf{x};\mathbf{W}^{(0)})\geq 1$, which contradicts with
the fact that $yf(\mathbf{x};\mathbf{W}^{(0)})\leq
2{\sqrt{2\log(16m/p)}\cdot\sigma_{0}\|\mathbf{u}\|_{2}}$. So in order for
$\bar{T}_{1}<+\infty$, we must have $\tilde{\eta}>1/2$. In conclusion, one
necessary condition for the stable oscillation Assumption B.2 is that
$\tilde{\eta}>1/2$, and therefore

$\displaystyle yf(\mathbf{x};\mathbf{W}^{(\bar{T}-1)})\geq
z_{2}=\frac{\tilde{\eta}+2-\sqrt{\tilde{\eta}^{2}+4\tilde{\eta}}}{2\tilde{\eta}}.$
(B.182)

This finishes the proof of Proposition B.9. ∎

###  B.7 Discussion: Necessary Condition for $\delta$-Oscillation

Inequality (B.68) provides an upper bound involving $\tilde{\eta}$, which
should be compatible with Assumption B.2, hence

$\displaystyle\big{(}\tilde{\eta}/2+\sqrt{\tilde{\eta}^{2}/4+\tilde{\eta}}\big{)}^{2}>1+\delta\quad\Leftrightarrow\quad\tilde{\eta}>(1+\delta^{-1})\big{(}\sqrt{1+\delta}-1\big{)}.$
(B.183)

One can verify with software that RHS is monotonically increasing in
$\delta\in[0,1]$ with minimal value $0.5$, when $\tilde{\eta}=0$, which is in
line with the weakest oscillation condition discovered in the last part. And
the maximal value taken at $\delta=1$ is less than $0.83$.

On the other hand, Inequality (B.60) should also be compatible with the
Assumption 4.2, which indicates

$\displaystyle
1-\delta>yf(\mathbf{x};\mathbf{W}^{(\bar{T}_{k-1}}))>\frac{2+\tilde{\eta}-\sqrt{\tilde{\eta}^{2}+4\tilde{\eta}}}{2\tilde{\eta}}.$
(B.184)

The readers can see that it is equivalent to
$\tilde{\eta}>\delta^{-1}((1-\delta)^{-1/2}-1)$. Furthermore, we have that
$\delta^{-1}((1-\delta)^{-1/2}-1)>(1+\delta^{-1})(\sqrt{1+\delta}-1)$ thus it
is a stronger requirement on $\eta$.

##  Appendix C Single Training Data Case: Small Learning Rate Regime

This section focuses on training our model with single noiseless data point
$(\mathbf{x},y)$, where $\mathbf{x}=(y\mathbf{u},y\mathbf{v})$ contains two
signal patches with $\mathbf{u}$ much stronger than $\mathbf{v}$. Therefore,
the whole objective can be rearranged by

$\displaystyle
L(\mathbf{W})=\frac{1}{2}\big{(}f(\mathbf{x};\mathbf{W})-y\big{)}^{2}=\frac{1}{2}\left(\sum_{j\in\\{\pm
1\\}}\frac{j}{m}\sum_{r\in[m]}\sigma(\langle\mathbf{w}_{j,r},y\mathbf{u}\rangle)+\sigma(\langle\mathbf{w}_{j,r},y\mathbf{v}\rangle)-y\right)^{2}.$
(C.1)

In this simplified setting, each weight vector is updated by

$\displaystyle\mathbf{w}_{j,r}^{(t+1)}=\mathbf{w}_{j,r}^{(t)}-\frac{jy\eta}{m}\cdot\big{(}f(\mathbf{x};\mathbf{W}^{(t)})-y\big{)}\cdot\left(\sigma^{\prime}(\langle\mathbf{w}_{j,r}^{(t)},y\mathbf{u}\rangle)\mathbf{u}+\sigma^{\prime}(\langle\mathbf{w}_{j,r}^{(t)},y\mathbf{v}\rangle)\mathbf{v}\right).$
(C.2)

Then we can directly obtain the following updating rules of the inner
products,

$\displaystyle\langle\mathbf{w}_{j,r}^{(t+1)},\mathbf{u}\rangle=\langle\mathbf{w}_{j,r}^{(t)},\mathbf{u}\rangle-\frac{jy\eta}{m}\cdot\big{(}f(\mathbf{x};\mathbf{W}^{(t)})-y\big{)}\cdot\sigma^{\prime}(\langle\mathbf{w}_{j,r}^{(t)},y\mathbf{u}\rangle)\cdot\|\mathbf{u}\|_{2}^{2},$
(C.3)
$\displaystyle\langle\mathbf{w}_{j,r}^{(t+1)},\mathbf{v}\rangle=\langle\mathbf{w}_{j,r}^{(t)},\mathbf{u}\rangle-\frac{jy\eta}{m}\cdot\big{(}f(\mathbf{x};\mathbf{W}^{(t)})-y\big{)}\cdot\sigma^{\prime}(\langle\mathbf{w}_{j,r}^{(t)},y\mathbf{v}\rangle)\cdot\|\mathbf{v}\|_{2}^{2},$
(C.4)

since $\mathbf{u}$ and $\mathbf{v}$ are assumed to be orthogonal in our data
generation model. In this section, we also denote the fitting residual at
iteration $t$ as $\ell^{(t)}=f(\mathbf{x};\mathbf{W}^{(t)})-y$ for
convenience.

To better prepare for the analysis of this section, we single out the
following concentration results from Appendix A which provides a high-
probability bound on the initialization $\mathbf{W}^{(0)}$.

######  Lemma C.1 (Initialization).

Suppose that $d=\Omega(\log(m/p))$ and $m=\Omega(\log(1/p))$. Then with
probability at least $1-p$, there holds

$\displaystyle\sigma_{0}\|\mathbf{u}\|/2\leq$
$\displaystyle\max_{r\in[m]}\langle\mathbf{w}^{(t)}_{j,r},j\mathbf{u}\rangle\leq\sqrt{2\log(16m/p)}\sigma_{0}\|\mathbf{u}\|,$
(C.5) $\displaystyle\sigma_{0}\|\mathbf{v}\|/2\leq$
$\displaystyle\max_{r\in[m]}\langle\mathbf{w}^{(t)}_{j,r},j\mathbf{v}\rangle\leq\sqrt{2\log(16m/p)}\sigma_{0}\|\mathbf{v}\|,$
(C.6)

for all $j\in\\{\pm 1\\}$.

The result of this section relies on the following conditions on the data
model and the initialization.

######  Assumption C.2 (Conditions on hyperparameters).

Suppose that the following holds:

  1. 1.

The weight initialization scale
$\sigma_{0}=\widetilde{\Theta}(\|\mathbf{u}\|^{-1}_{2})$;

  2. 2.

The signal strength
$\|\mathbf{u}\|_{2}>\widetilde{\Omega}(m^{2})\cdot\|\mathbf{v}\|_{2}$;

  3. 3.

The dimension $d$ satisfies $d=\Omega(\mathrm{polylog}(m))$.

######  Theorem C.3 (Restatement of Proposition 3.1).

Under Assumption C.2, choosing the learning rate $\eta\leq
m/6\|\mathbf{u}\|_{2}^{2}$ small enough and $\epsilon=0.01$, then with
probability at least $1-p=1-1/\mathrm{poly}(d)$, there exist

$T^{\dagger}=\frac{m}{\eta(1-\tau)\|\mathbf{u}\|^{2}_{2}}\log\left(\frac{2\iota}{\sigma_{0}\|\mathbf{u}\|_{2}}\right),\quad
T=T^{\dagger}+\left\lfloor\frac{Cm^{3}}{2\eta\epsilon\|\mathbf{u}\|^{2}}\right\rfloor,$

with $\tau$, $\iota$ defined in (C.15), (C.16), such that: (i) the average
loss over iterations $[T^{\dagger},T]$ decreased to $2\epsilon$, i.e.

$\displaystyle\frac{1}{T-T^{\dagger}+1}\sum_{s=T^{\dagger}}^{T}L(\mathbf{W}^{(s)})\leq
2\epsilon,$ (C.7)

(ii) the model does not learn weak signal $\mathbf{v}$ well enough, compared
to initialization, i.e.

$\displaystyle\max_{j\in\\{\pm
1\\},r\in[m]}\left|\langle\mathbf{w}_{j,r}^{(t)},\mathbf{v}\rangle\right|\leq
2\sqrt{2\log(16m/p)}\cdot\sigma_{0}\|\mathbf{v}\|_{2}.$ (C.8)

In the small learning rate regime, the dynamics go through two stages, in
which the strong signal $\mathbf{u}$ will be firstly learned exponentially
fast, and subsequently fully fit the given data point $(\mathbf{x},y)$
therefore stabilizing the training process. The following lemma plays an
important role in the exponentially increasing stage, for which we single it
out here.

######  Lemma C.4 (Derivative lower bound).

For any $0<\tau<1$ to be tuned later, suppose at some time $t$ there holds

$\displaystyle\max_{r\in[m],j\in\\{\pm
1\\}}\left\\{\left|\langle\mathbf{w}_{j,r}^{(t)},\mathbf{u}\rangle\right|,\left|\langle\mathbf{w}_{j,r}^{(t)},\mathbf{v}\rangle\right|\right\\}\leq\sqrt{\frac{\tau}{2}},$
(C.9)

then we can lower bound the fitting residual by $-y\ell^{(t)}\geq 1-\tau$.

###### Proof of Lemma C.4.

Plug into the CNN model definition (3.1), we have that

$\displaystyle-y\ell^{(t)}=1-F_{y}(\mathbf{x};\mathbf{W}^{(t)})+F_{-y}(\mathbf{x};\mathbf{W}^{(t)})\geq
1-F_{y}(\mathbf{x};\mathbf{W}^{(t)}).$ (C.10)

We can upper bound $F_{y}(\mathbf{x};\mathbf{W}^{(t)})$ further by

$\displaystyle F_{y}(\mathbf{x};\mathbf{W}^{(t)})$
$\displaystyle=\frac{1}{m}\sum_{r\in[m]}\sigma(\langle\mathbf{w}_{y,r}^{(t)},y\mathbf{u}\rangle)+\sigma(\langle\mathbf{w}_{y,r}^{(t)},y\mathbf{v}\rangle)$
(C.11)
$\displaystyle\leq\max_{r\in[m]}\left\\{\langle\mathbf{w}_{y,r}^{(t)},y\mathbf{u}\rangle^{2}+\langle\mathbf{w}_{y,r}^{(t)},y\mathbf{v}\rangle^{2}\right\\}$
(C.12) $\displaystyle\leq\tau.$ (C.13)

Then it follows that $-y\ell^{(t)}\geq 1-\tau$. ∎

###  C.1 Stage 1. Exponential Growth

We will mainly track the maximal inner product between $\mathbf{w}$ and the
signal vectors $\mathbf{v}$ and $\mathbf{u}$, i.e.,

$\displaystyle\Psi^{(t)}=\max_{j,r}\left|\langle\mathbf{w}_{j,r}^{(t)},\mathbf{v}\rangle\right|,\quad\Phi^{(t)}=\max_{j,r}\left|\langle\mathbf{w}_{j,r}^{(t)},\mathbf{u}\rangle\right|.$
(C.14)

In the following, we would take

$\displaystyle\tau$
$\displaystyle=\max\left\\{2\sigma_{0}\|\mathbf{u}\|_{2}\left(2\log(16m/p)\right)^{1/2-\|\mathbf{v}\|_{2}^{2}/4\|\mathbf{u}\|_{2}^{2}},1-\frac{6\sqrt{2}\|\mathbf{v}\|_{2}^{2}}{\|\mathbf{u}\|^{2}_{2}\log(2/\sqrt{2\log(16m/p)})}\right\\},$
(C.15) $\displaystyle\iota$
$\displaystyle=\sigma_{0}\|\mathbf{u}\|_{2}\cdot\exp\left\\{\frac{1-\tau}{6}\log\left(\frac{\sqrt{\tau/2}}{\sigma_{0}\|\mathbf{u}\|_{2}\sqrt{2\log(16m/p)}}\right)\right\\}.$
(C.16)

By the conditions in Assumption C.2 on
$\|\mathbf{v}\|_{2}^{2}/\|\mathbf{u}\|_{2}^{2}$, we find $\tau,\iota$ both
constants in $(0,1)$.

######  Lemma C.5 (First stage: one training data case).

Under the same conditions as Theorem C.3, there exists time

$\displaystyle
T^{\dagger}=\frac{m}{\eta(1-\tau)\|\mathbf{u}\|^{2}_{2}}\log\left(\frac{2\iota}{\sigma_{0}\|\mathbf{u}\|_{2}}\right),$
(C.17)

such that: (i) the model learns the strong signal to a constant level, i.e.,

$\displaystyle\max_{r\in[m]}\langle\mathbf{w}_{y,r}^{(T^{\dagger})},y\mathbf{u}\rangle\geq\iota,$
(C.18)

(ii) compared to the random initialization, the model does not learn weak
signal that much, i.e.,

$\displaystyle\max_{j\in\\{\pm
1\\},r\in[m]}\left|\langle\mathbf{w}_{j,r}^{(T^{\dagger})},\mathbf{v}\rangle\right|\leq
2\sqrt{2\log(16m/p)}\cdot\sigma_{0}\|\mathbf{v}\|_{2}.$ (C.19)

###### Proof of Lemma C.5.

Firstly, we would find $\\{\Psi^{(t)},\Phi^{(t)}\\}_{t\geq 0}$ having an
exponentially growing upper bound. Recursively, we would have that

$\displaystyle\Psi^{(t+1)}$ $\displaystyle\leq\Psi^{(t)}+\max_{j\in\\{\pm
1\\},r\in[m]}\left|\frac{jy\eta}{m}\cdot\big{(}f(\mathbf{x};\mathbf{W}^{(t)})-y\big{)}\cdot\sigma^{\prime}(\langle\mathbf{w}_{j,r}^{(t)},y\mathbf{v}\rangle)\cdot\|\mathbf{v}\|_{2}^{2}\right|$
(C.20)
$\displaystyle=\Psi^{(t)}+\frac{\eta}{m}\cdot\left|\ell^{(t)}\right|\cdot\|\mathbf{v}\|_{2}^{2}\cdot\max_{j\in\\{\pm
1\\},r\in[m]}\sigma^{\prime}(\langle\mathbf{w}_{j,r}^{(t)},y\mathbf{v}\rangle)$
(C.21)
$\displaystyle\leq\Psi^{(t)}+\frac{2\eta}{m}\cdot\left|\ell^{(t)}\right|\cdot\|\mathbf{v}\|^{2}_{2}\cdot\Psi^{(t)}$
(C.22)
$\displaystyle\leq\exp\left(\frac{6\eta\|\mathbf{v}\|_{2}^{2}}{m}\right)\cdot\Psi^{(t)}.$
(C.23)

Therefore, we have that

$\displaystyle\Psi^{(t)}\leq\exp\left(\frac{6\eta\|\mathbf{v}\|_{2}^{2}t}{m}\right)\cdot\Psi^{(0)}\leq\exp\left(\frac{6\eta\|\mathbf{v}\|_{2}^{2}t}{m}\right)\cdot\sqrt{2\log(16m/p)}\cdot\sigma_{0}\|\mathbf{v}\|_{2}.$
(C.24)

It follows by the same argument that that

$\displaystyle\Phi^{(t)}\leq\exp\left(\frac{6\eta\|\mathbf{u}\|^{2}_{2}t}{m}\right)\Phi^{(0)}\leq\exp\left(\frac{6\eta\|\mathbf{u}\|_{2}^{2}t}{m}\right)\cdot\sqrt{2\log(16m/p)}\cdot\sigma_{0}\|\mathbf{u}\|_{2}.$
(C.25)

Note that the growing rates of these two bounds differ a lot due to the
different magnitudes of $\|\mathbf{u}\|_{2}$ and $\|\mathbf{v}\|_{2}$. Our
subsequent analysis illustrates that $\Phi^{(t)}$ can grow into a constant-
level magnitude since the strong signal $\mathbf{u}$ is significant enough.
Now we can track how well our model learns $\mathbf{u}$ by

$\displaystyle
A^{(t)}=\max_{r\in[m]}\langle\mathbf{w}_{y,r}^{(t)},y\mathbf{u}\rangle.$
(C.26)

By the definition, $A^{(t)}\leq\Phi^{(t)}$ also admits an exponentially
growing upper bound. For a certain $\tau\in(0,1)$, due to the previous upper
bounds (C.24) and (C.25), $\max\\{\Phi^{(t)},\Psi^{(t)}\\}\leq\sqrt{\tau/2}$
remains true at least until

$\displaystyle
T_{1}=\frac{m}{6\eta\|\mathbf{u}\|^{2}}\log\left(\frac{\sqrt{\tau/2}}{\sigma_{0}\|\mathbf{u}\|_{2}\sqrt{2\log(16m/p)}}\right).$
(C.27)

Consequently, until at least $T_{1}$, we can use Lemma C.4 to conclude that
$-y\ell^{(t)}\geq 1-\tau$, which enables lower bounding $A^{(t)}$.
Specifically, start with the updating rule

$\displaystyle\langle\mathbf{w}_{y,r}^{(t+1)},y\mathbf{u}\rangle$
$\displaystyle=\langle\mathbf{w}_{y,r}^{(t)},y\mathbf{u}\rangle+\frac{\eta}{m}\cdot\big{(}-y\ell^{(t)}\big{)}\cdot\sigma^{\prime}(\langle\mathbf{w}_{y,r}^{(t)},y\mathbf{u}\rangle)\cdot\|\mathbf{u}\|^{2}_{2}$
(C.28)
$\displaystyle\geq\langle\mathbf{w}_{y,r}^{(t)},y\mathbf{u}\rangle+\frac{2\eta(1-\tau)\|\mathbf{u}\|^{2}_{2}}{m}\cdot\max_{r\in[m]}\left\\{\langle\mathbf{w}_{y,r}^{(t)},y\mathbf{u}\rangle,0\right\\},$
(C.29)

and take maximum over $r\in[m]$ to see that

$\displaystyle A^{(t+1)}\geq
A^{(t)}+\frac{2\eta(1-\tau)\|\mathbf{u}\|^{2}_{2}}{m}\cdot
A^{(t)}\geq\exp\left(\frac{\eta(1-\tau)\|\mathbf{u}\|^{2}_{2}}{m}\right)\cdot
A^{(t)},$ (C.30)

where the last equality is by $1+z\geq\exp(z/2)$ for any $0\leq z\leq 2$.
Consequently, we would have

$\displaystyle
A^{(t)}\geq\exp\left(\frac{\eta(1-\tau)\|\mathbf{u}\|_{2}^{2}t}{m}\right)\cdot
A^{(0)}\geq\exp\left(\frac{\eta(1-\tau)\|\mathbf{u}\|_{2}^{2}t}{m}\right)\cdot\sigma_{0}\|\mathbf{u}\|_{2}/2,$
(C.31)

at least until $t\leq T_{1}$ defined in (C.27). Then we define another time

$\displaystyle
T_{2}=\frac{m}{\eta(1-\tau)\|\mathbf{u}\|^{2}_{2}}\log\left(\frac{2\iota}{\sigma_{0}\|\mathbf{u}\|_{2}}\right)\leq
T_{1},$ (C.32)

where the inequality is due to the scaling of $\iota$ upon $\tau$. Plugging
$T_{2}$ into the exponential lower bound (C.31), we can conclude that

$\displaystyle\Phi^{(T_{2})}\geq A^{(T_{2})}\geq\iota,$ (C.33)

which already grows up to a constant level magnitude by the time $T_{2}$.
Lastly, we plug the definition of $T_{2}$ to upper bound $\Psi^{(T_{2})}$ as

$\Psi^{(T_{2})}\leq\exp\left(\frac{6\|\mathbf{v}\|_{2}^{2}}{(1-\tau)\|\mathbf{u}\|_{2}^{2}}\log\left(\frac{2\iota}{\sigma_{0}\|\mathbf{u}\|_{2}}\right)\right)\cdot\sqrt{2\log(16m/p)}\cdot\sigma_{0}\|\mathbf{v}\|_{2}\leq
2\sqrt{2\log(16m/p)}\cdot\sigma_{0}\|\mathbf{v}\|_{2}.$

In conclusion, by taking $T^{\dagger}=T_{2}$, this lemma is completely proved.
∎

###  C.2 Stage 2. Stabilized Convergence

In the second stage, our lemmas would suggest that before the model really
learns the weak signal $\mathbf{v}$ (i.e. before
$\max_{j,r}|\langle\mathbf{w}_{j,r}^{(t)},\mathbf{v}\rangle|$ breaks the
$\widetilde{\mathcal{O}}(\sigma_{0}\|\mathbf{v}\|_{2})$ upper bound), the
model already fits the given data point by exploiting the strong signal
$\mathbf{u}$ and decreasing the loss to $\epsilon$.

######  Lemma C.6 (Second stage: one training data case).

Under the same conditions as Theorem C.3, for any $\epsilon=0.01$, there
exists time

$T=T^{\dagger}+\left\lfloor\frac{Cm^{3}}{2\eta\epsilon\|\mathbf{u}\|_{2}^{2}}\right\rfloor$

such that: (i) the average loss over iterations within this stage has
decreased to $2\epsilon$, i.e.,

$\displaystyle\frac{1}{T-T^{\dagger}+1}\sum_{s=T^{\dagger}}^{T}L(\mathbf{W}^{(s)})\leq
2\epsilon,$ (C.34)

(ii) throughout the training dynamics $0\leq t\leq T$, there holds

$\displaystyle\max_{j\in\\{\pm
1\\},r\in[m]}|\langle\mathbf{w}_{j,r}^{(t)},\mathbf{v}\rangle|\leq
2\sqrt{2\log(16m/p)}\sigma_{0}\|\mathbf{v}\|_{2}.$ (C.35)

The proof of Lemma C.6 relies on the following three lemmas (Lemmas C.7, C.8,
and C.9). We present these lemmas with proofs and then combine them to give
the proof of Lemma C.6.

Firstly, we identify when the upper bound on
$\langle\mathbf{w}_{j,r}^{(t)},\mathbf{v}\rangle$ breaks and find that the
conclusions of Lemma C.5 still holds before that time.

######  Lemma C.7.

Under the same conditions in Theorem C.3, take $\eta\leq
m/6\|\mathbf{u}\|_{2}^{2}$. There exists a time

$\displaystyle T^{\ddagger}=\frac{m}{6\eta\|\mathbf{v}\|_{2}^{2}}\log(2)\geq
T^{\dagger}$ (C.36)

such that

$\displaystyle\max_{r\in[m]}\langle\mathbf{w}_{y,r}^{(t)},y\mathbf{u}\rangle\geq\iota/2,\quad\max_{j\in\\{\pm
1\\},r\in[m]}\left|\langle\mathbf{w}_{j,r}^{(t)},\mathbf{v}\rangle\right|\leq
2\sqrt{2\log(16m/p)}\cdot\sigma_{0}\|\mathbf{v}\|_{2}.$ (C.37)

hold for any $T^{\dagger}\leq t\leq T^{\ddagger}$.

###### Proof of Lemma C.7.

Firstly, we need to adopt the exponential upper bound derived in proving Lemma
C.5,

$\displaystyle\Psi^{(t)}\leq\exp\left(\frac{6\eta\|\mathbf{v}\|_{2}^{2}t}{m}\right)\cdot\Psi^{(0)}\leq\exp\left(\frac{6\eta\|\mathbf{v}\|_{2}^{2}t}{m}\right)\cdot\sqrt{2\log(16m/p)}\cdot\sigma_{0}\|\mathbf{v}\|_{2}.$
(C.38)

Then we naturally find that before $T^{\ddagger}$, it would always hold that

$\displaystyle\max_{j\in\\{\pm
1\\},r\in[m]}\left|\langle\mathbf{w}_{j,r}^{(t)},\mathbf{v}\rangle\right|\leq
2\sqrt{2\log(16m/p)}\cdot\sigma_{0}\|\mathbf{v}\|_{2}.$ (C.39)

Due to the conditions on $\|\mathbf{u}\|_{2}^{2}/\|\mathbf{v}\|_{2}^{2}$,
$T^{\ddagger}$ is found to be much larger than $T^{\dagger}$. Then we proceed
by induction to prove the other assertion. At time $t=T^{\dagger}$, the lower
bound $\max_{r}\langle\mathbf{w}_{y,r}^{(t)},y\mathbf{u}\rangle\geq\iota/2$
holds as a consequence of the previous lemma. Suppose it holds until time $t$.
We restate the updating rule by

$\displaystyle\langle\mathbf{w}_{y,r}^{(t+1)},y\mathbf{u}\rangle=\langle\mathbf{w}_{y,r}^{(t)},y\mathbf{u}\rangle+\frac{\eta}{m}\cdot\big{(}1-yf(\mathbf{x};\mathbf{W}^{(t)})\big{)}\cdot\sigma^{\prime}(\langle\mathbf{w}_{y,r}^{(t)},y\mathbf{u}\rangle)\cdot\|\mathbf{u}\|_{2}^{2},$
(C.40)

from which we find
$\max_{r\in[m]}\langle\mathbf{w}_{y,r}^{(t+1)},y\mathbf{u}\rangle\geq\max_{r\in[m]}\langle\mathbf{w}_{y,r}^{(t)},y\mathbf{u}\rangle$
must hold when $yf(\mathbf{x};\mathbf{W}^{(t)})\leq 1$. Otherwise, once
$yf(\mathbf{x};\mathbf{W}^{(t)})>1$, it immediately follows that

$\displaystyle 1$
$\displaystyle<yf(\mathbf{x};\mathbf{W}^{(t)})=F_{y}(\mathbf{x};\mathbf{W}^{(t)})-F_{-y}(\mathbf{x};\mathbf{W}^{(t)})$
(C.41) $\displaystyle\leq
F_{y}(\mathbf{x};\mathbf{W}^{(t)})=\frac{1}{m}\sum_{r\in[m]}\sigma(\langle\mathbf{w}^{(t)}_{y,r},y\mathbf{u}\rangle)+\sigma(\langle\mathbf{w}^{(t)}_{y,r},y\mathbf{v}\rangle)$
(C.42)
$\displaystyle\leq\max_{r\in[m]}\langle\mathbf{w}_{y,r}^{(t)},y\mathbf{u}\rangle^{2}+2\log(16m/p)\cdot\sigma_{0}^{2}\|\mathbf{v}\|_{2}^{2}.$
(C.43)

Consequently, for the specific neuron
$r^{\ast}=\mathop{\mathrm{argmax}}_{r\in[m]}\langle\mathbf{w}_{y,r}^{(t)},y\mathbf{u}\rangle$,
there holds

$\displaystyle\langle\mathbf{w}_{y,r^{\ast}}^{(t+1)},y\mathbf{u}\rangle$
$\displaystyle\geq\langle\mathbf{w}_{y,r^{\ast}}^{(t)},y\mathbf{u}\rangle-\frac{3\eta}{m}\cdot\langle\mathbf{w}_{y,r^{\ast}}^{(t)},y\mathbf{u}\rangle\cdot\|\mathbf{u}\|_{2}^{2}$
(C.44)
$\displaystyle\geq\left(1-2\log(16m/p)\cdot\sigma_{0}^{2}\|\mathbf{v}\|^{2}_{2}\right)\cdot\left(1-\frac{3\eta}{m}\cdot\|\mathbf{u}\|^{2}_{2}\right)$
(C.45) $\displaystyle\geq\frac{\iota}{2},$ (C.46)

where the last inequality is enabled by taking $\eta\leq
m/6\|\mathbf{u}\|^{2}_{2}$ and
$\sigma_{0}\leq\sqrt{1-\iota}/(2\log(16m/p)\|\mathbf{v}\|_{2})$. Thus by
induction, we have finished the proof of Lemma C.7. ∎

Our subsequently analysis confirms that even before $T^{\ddagger}$, the model
can already fit the given data point by exploiting $\mathbf{u}$. For the given
$0<\epsilon<1$, define a reference point $\mathbf{W}^{\ast}$ as

$\displaystyle\mathbf{w}_{j,r}^{\ast}=\frac{4m(1+\epsilon)}{\iota}\cdot\frac{j\mathbf{u}}{\|\mathbf{u}\|^{2}_{2}},\quad
j\in\\{\pm 1\\},r\in[m].$ (C.47)

######  Lemma C.8.

Under the same condition as the previous lemma, for all $T^{\dagger}\leq t\leq
T^{\ddagger}$, there holds that

$\displaystyle y\langle\nabla
f(\mathbf{x};\mathbf{W}^{(t)}),\mathbf{W}^{\ast}\rangle\geq
2\cdot(1+\epsilon).$ (C.48)

###### Proof of Lemma C.8.

Recall the definition of the CNN in (3.1) and that
$\mathbf{u}\perp\mathbf{v}$, so we have

$\displaystyle y\langle\nabla
f(\mathbf{x};\mathbf{W}^{(t)}),\mathbf{W}^{\ast}\rangle$
$\displaystyle=\frac{1}{m}\sum_{j\in\\{\pm
1\\},r\in[m]}\sigma^{\prime}(\langle\mathbf{w}_{j}^{(t)},y\mathbf{u}\rangle)\cdot\langle\mathbf{w}_{j,r}^{\ast},y\mathbf{u}\rangle$
$\displaystyle=\sum_{j\in\\{\pm
1\\},r\in[m]}\sigma^{\prime}(\langle\mathbf{w}_{j,r}^{(t)},y\mathbf{u}\rangle)\cdot\frac{4(1+\epsilon)}{\iota}$
$\displaystyle\geq\max_{r\in[m]}\langle\mathbf{w}_{y,r}^{(t)},y\mathbf{u}\rangle\cdot\frac{4(1+\epsilon)}{\iota}$
$\displaystyle\geq 2\cdot(1+\epsilon),$

where the last inequality is by
$\max_{r\in[m]}\langle\mathbf{w}_{y,r}^{(t)},y\mathbf{u}\rangle\geq\iota/2$ as
shown by the previous lemma. ∎

######  Lemma C.9.

Continued from the previous setting, we know that for $T^{\dagger}\leq t\leq
T^{\ddagger}$, it holds that

$\|\mathbf{W}^{(t)}-\mathbf{W}^{\ast}\|_{F}^{2}-\|\mathbf{W}^{(t+1)}-\mathbf{W}^{\ast}\|_{F}^{2}\geq
2\eta L(\mathbf{W}^{(t)})-2\eta\epsilon^{2}.$

###### Proof of Lemma C.9.

Firstly we expand the difference by

$\displaystyle\|\mathbf{W}^{(t)}-\mathbf{W}^{\ast}\|_{F}^{2}-\|\mathbf{W}^{(t+1)}-\mathbf{W}^{\ast}\|_{F}^{2}=2\eta\cdot\langle\nabla
L(\mathbf{W}^{(t}),\mathbf{W}^{(t)}-\mathbf{W}^{\ast}\rangle-\eta^{2}\cdot\|\nabla
L(\mathbf{W}^{(t})\|_{F}^{2}.$ (C.49)

With one data point, $\nabla L(\mathbf{W}^{(t)})=\ell^{(t)}\nabla
f(\mathbf{x};\mathbf{W}^{(t)})$ admits a simplified expression, where
$\ell^{(t)}=f(\mathbf{W}^{(t)},\mathbf{x})-y$ denotes the fitting residual.
Since the neural network $f(\mathbf{W},\mathbf{x})$ is $2$-homogeneous in
$\mathbf{W}$ due to the activation function $\sigma(z)=\max\\{z,0\\}^{2}$, we
can have

$\displaystyle\langle\nabla
f(\mathbf{x};\mathbf{W}^{(t)}),\mathbf{W}^{(t)}\rangle=2f(\mathbf{x};\mathbf{W}^{(t)}).$
(C.50)

Stack these observations into the first term of previous difference expansion
to obtain that

$\displaystyle\langle\nabla
L(\mathbf{W}^{(t}),\mathbf{W}^{(t)}-\mathbf{W}^{\ast}\rangle$
$\displaystyle=\ell^{(t)}\cdot\langle\nabla
f(\mathbf{x};\mathbf{W}^{(t)}),\mathbf{W}^{(t)}-\mathbf{W}^{\ast}\rangle$
$\displaystyle=\ell^{(t)}\cdot\big{(}2f(\mathbf{x};\mathbf{W}^{(t)})-\langle\nabla
f(\mathbf{x};\mathbf{W}^{(t)}),\mathbf{W}^{\ast}\rangle\big{)}$
$\displaystyle=2\ell^{(t)}\cdot\big{(}f(\mathbf{x};\mathbf{W}^{(t)})-y\big{)}+\ell^{(t)}\cdot
y\cdot\big{(}2-y\langle\nabla
f(\mathbf{x};\mathbf{W}^{(t)}),\mathbf{W}^{\ast}\rangle\big{)}.$

Note that the first term is exactly $4L(\mathbf{W}^{(t)})$. As for the second
term, we need to plug in Lemma C.8 to see $2-y\langle\nabla
f(\mathbf{x};\mathbf{W}^{(t)}),\mathbf{W}^{\ast}\rangle\leq-2\epsilon<0$, so
that

$\displaystyle\left|\ell^{(t)}\cdot y\cdot\big{(}2-y\langle\nabla
f(\mathbf{x};\mathbf{W}^{(t)}),\mathbf{W}^{\ast}\rangle\big{)}\right|\leq\frac{1}{2}\big{(}\ell^{(t)}\big{)}^{2}+2\epsilon^{2}=L(\mathbf{W}^{(t)})+2\epsilon^{2}.$

As a result, we would know $\langle\nabla
L(\mathbf{W}^{(t}),\mathbf{W}^{(t)}-\mathbf{W}^{\ast}\rangle\geq
3L(\mathbf{W}^{(t)})-2\epsilon^{2}$. Next, an upper bound on the second order
term $\eta^{2}\cdot\|\nabla L(\mathbf{W}^{(t})\|_{F}^{2}$ is given by

$\displaystyle\eta^{2}\cdot\|\nabla L(\mathbf{W}^{(t)})\|_{F}^{2}$
$\displaystyle=\eta^{2}\cdot\big{(}\ell^{(t)}\big{)}^{2}\cdot\left(\|\mathbf{u}\|^{2}_{2}\sum_{j\in\\{\pm
1\\},r\in[m]}\sigma^{\prime}(\langle\mathbf{w}^{(t)}_{j,r},y\mathbf{u}\rangle)+\|\mathbf{v}\|_{2}^{2}\sum_{j\in\\{\pm
1\\},r\in[m]}\sigma^{\prime}(\langle\mathbf{w}^{(t)}_{j,r},y\mathbf{v}\rangle)\right)$
$\displaystyle\leq\mathcal{O}\big{(}\max\\{\|\mathbf{u}\|_{2}^{2},\|\mathbf{v}\|_{2}^{2}\\}\big{)}\cdot\eta^{2}\cdot
L(\mathbf{W}^{(t}),$

since the dynamics of the inner products
$\langle\mathbf{w}^{(t)}_{j,r},y\mathbf{u}\rangle,\langle\mathbf{w}^{(t)}_{j,r},y\mathbf{v}\rangle$
are well bounded by $\mathcal{O}(1)$ throughout the time we are considering.
By scaling
$\eta\mathcal{O}(\max\\{\|\mathbf{u}\|^{2},\|\mathbf{v}\|^{2}\\})\leq 1$, we
would know that $\eta^{2}\|\nabla L(\mathbf{W}^{(t})\|_{F}^{2}\leq\eta
L(\mathbf{W}^{(t})$. Eventually, continued from (C.49), we can completely
prove this lemma. ∎

Equipped with Lemmas C.7, C.8, and C.9, we are ready to prove the main lemma
for the second stage.

###### Proof of Lemma C.6.

Continued from Lemma C.9, for any $t\geq T^{\dagger}$, it holds that

$\frac{1}{t-T^{\dagger}+1}\sum_{s=T^{\dagger}}^{t}L(\mathbf{W}^{(s)})\leq\frac{\|\mathbf{W}^{(T^{\dagger})}-\mathbf{W}^{\ast}\|_{F}^{2}}{2\eta(t-T^{\dagger}+1)}+\epsilon^{2}.$

Before proceeding to scale time $t$, it would be helpful to decompose
$\|\mathbf{W}^{(T^{\dagger})}-\mathbf{W}^{\ast}\|_{F}^{2}$ and to have an
upper bound on this term,

$\displaystyle\|\mathbf{W}^{(T^{\dagger})}-\mathbf{W}^{\ast}\|_{F}^{2}$ (C.51)
$\displaystyle\qquad=\sum_{j\in\\{\pm
1\\},r\in[m]}\frac{\langle\mathbf{w}_{j,r}^{(T^{\dagger})}-\mathbf{w}_{j,r}^{\ast},\mathbf{u}\rangle^{2}}{\|\mathbf{u}\|_{2}^{2}}+\frac{\langle\mathbf{w}_{j,r}^{(T^{\dagger})}-\mathbf{w}_{j,r}^{\ast},\mathbf{v}\rangle^{2}}{\|\mathbf{v}\|_{2}^{2}}+\left\|\left(\mathbf{I}_{d}-\frac{\mathbf{v}\mathbf{v}^{\top}}{\|\mathbf{v}\|_{2}^{2}}-\frac{\mathbf{u}\mathbf{u}^{\top}}{\|\mathbf{u}\|_{2}^{2}}\right)(\mathbf{w}_{j,r}^{(T^{\dagger})}-\mathbf{w}_{j,r}^{\ast})\right\|_{2}^{2}$
(C.52) $\displaystyle\qquad\leq\sum_{j\in\\{\pm
1\\},r\in[m]}\frac{2\langle\mathbf{w}_{j,r}^{(T^{\dagger})},\mathbf{u}\rangle^{2}+2\langle\mathbf{w}_{j,r}^{\ast},\mathbf{u}\rangle^{2}}{\|\mathbf{u}\|_{2}^{2}}+\frac{\langle\mathbf{w}_{j,r}^{(T^{\dagger})},\mathbf{v}\rangle^{2}}{\|\mathbf{v}\|_{2}^{2}}+\left\|\left(\mathbf{I}_{d}-\frac{\mathbf{v}\mathbf{v}^{\top}}{\|\mathbf{v}\|_{2}^{2}}-\frac{\mathbf{u}\mathbf{u}^{\top}}{\|\mathbf{u}\|_{2}^{2}}\right)\mathbf{w}_{j,r}^{(0)}\right\|_{2}^{2},$
(C.53)

where we exploit the fact that $\mathbf{w}^{\ast}$ is parallel to $\mathbf{u}$
by Lemma (C.47), and the gradient steps only updates $\mathbf{w}$ along the
directions of $\mathbf{u},\mathbf{v}$. Recall that by Lemma C.7,

$\displaystyle\max_{j\in\pm
1,r\in[m]}\langle\mathbf{w}^{(T^{\dagger})}_{j,r},j\mathbf{u}\rangle=\Omega(1),\quad\max_{j\in\pm
1,r\in[m]}\left|\langle\mathbf{w}^{(T^{\dagger})}_{j,r},\mathbf{v}\rangle\right|=\widetilde{\mathcal{O}}(\sigma_{0}\|\mathbf{v}\|_{2}),$
(C.54)

and also that
$\|\mathbf{w}^{(0)}_{j,r}\|=\widetilde{\mathcal{O}}(\sigma_{0}\sqrt{d})$, the
leading term in (C.53) would be $\sum_{j\in\\{\pm
1\\},r\in[m]}\langle\mathbf{w}_{j,r}^{\ast},\mathbf{u}\rangle^{2}/\|\mathbf{u}\|^{2}_{2}$.
Therefore, we conclude that
$\|\mathbf{W}^{(T^{\dagger})}-\mathbf{W}^{\ast}\|_{F}^{2}\leq
Cm^{3}/\|\mathbf{u}\|_{2}^{2}$ for some constant $C>0$. As a result, the
average loss after iterations $T^{\dagger}$ can be bounded by

$\frac{1}{t-T^{\dagger}+1}\sum_{s=T^{\dagger}}^{t}L(\mathbf{W}^{(s)})\leq\frac{Cm^{3}}{2\eta\|\mathbf{u}\|_{2}^{2}(t-T^{\dagger}+1)}+\epsilon^{2},\quad\forall
t^{\dagger}\leq t\leq T^{\ddagger}.$

Then we choose time $T=T^{\dagger}+\lfloor
Cm^{3}/(2\eta\epsilon\|\mathbf{u}\|_{2}^{2})\rfloor$ as stated in Lemma C.6.
Since
$\|\mathbf{u}\|_{2}^{2}/\|\mathbf{v}\|_{2}^{2}\geq\widetilde{\Omega}(m^{2})$
by Assumption C.2, we can verify that $T\leq T^{\ddagger}$. In conclusion, the
final output would be

$\displaystyle\frac{1}{T-T^{\dagger}+1}\sum_{s=T^{\dagger}}^{T}L(\mathbf{W}^{(s)})\leq\epsilon+\epsilon^{2}\leq
2\epsilon.$ (C.55)

This finishes the proof of Lemma C.6. ∎

Combine Lemmas C.5 and C.6 to obtain the full version of Theorem C.3.

##  Appendix D Proofs for Main Theoretical Results (Section 4)

In this section, we give a detailed proof for our main theoretical results for
the multiple training data case, i.e., Theorem 4.3. The proofs follow the
similar idea as the proofs for single training data case (Appendix B). The
readers interested in the proofs are encouraged to first go through Appendix B
to get the idea of the core steps. In Appendix D.1, we give a preliminary
analysis of the SGD training dynamics. In Appendix D.2, we give an overview of
the proofs with our fundamental reasoning towards weak signal learning. In
Appendix D.3, we give the proof of Theorem 4.3. We prove other lemmas in
subsequent sections.

###  D.1 Preliminary Analysis

Recall that $\mathcal{W}$ is the index set of training data points which lack
the strong feature patch. By Equation (2.5), the CNN weights are updated
according to

$\displaystyle\mathbf{w}_{j,r}^{(t+1)}$
$\displaystyle=\mathbf{w}_{j,r}^{(t)}-\frac{j\eta}{m}\cdot\big{(}f(\mathbf{x}_{i_{t}};\mathbf{W}^{(t)})-y_{i_{t}}\big{)}\cdot\left(\sigma^{\prime}(\langle\mathbf{w}_{j,r}^{(t)},y_{i_{t}}\mathbf{u}\rangle)\cdot
y_{i_{t}}\mathbf{u}\cdot\mathbf{1}\\{i_{t}\notin\mathcal{W}\\}\right.$ (D.1)
$\displaystyle\qquad+\sigma^{\prime}(\langle\mathbf{w}_{j,r}^{(t)},y_{i_{t}}\mathbf{v}\rangle)\cdot
y_{i_{t}}\mathbf{v}+\sigma^{\prime}(\langle\mathbf{w}_{j,r}^{(t)}\cdot\bm{\xi}_{i_{t}}\rangle)\cdot\bm{\xi}_{i_{t}}+\left.\sigma^{\prime}(\langle\mathbf{w}_{j,r}^{(t)}\cdot\widetilde{\bm{\xi}}_{i_{t}}\rangle)\cdot\widetilde{\bm{\xi}}_{i_{t}}\cdot\mathbf{1}\\{i_{t}\in\mathcal{W}\\}\right).$
(D.2)

Also, recall that the correct index sets for the strong and weak signal
patches are defined as

$\displaystyle\mathcal{U}_{j,+}^{(t)}:=\left\\{r\in[m]:\langle\mathbf{w}_{j,r}^{(t)},j\mathbf{u}\rangle\geq
0\right\\},\quad\mathcal{V}_{j,+}^{(t)}:=\left\\{r\in[m]:\langle\mathbf{w}_{j,r}^{(t)},j\mathbf{v}\rangle\geq
0\right\\},$ (D.3)

By the CNN expression (2.3), for each $j\in\\{\pm 1\\}$, the inner products
that matter are

  1. 1.

_positive neurons:_ $\langle\mathbf{w}_{j,r}^{(t)},j\mathbf{u}\rangle$ for
$r\in\mathcal{U}_{j,+}^{(t)}$,
$\langle\mathbf{w}_{j,r}^{(t)},j\mathbf{v}\rangle$ for
$r\in\mathcal{V}_{j,+}^{(t)}$;

  2. 2.

_negative neurons:_ $\langle\mathbf{w}_{-j,r}^{(t)},j\mathbf{u}\rangle$ for
$r\notin\mathcal{U}_{-j,+}^{(t)}$,
$\langle\mathbf{w}_{-j,r}^{(t)},j\mathbf{v}\rangle$ for
$r\notin\mathcal{V}_{-j,+}^{(t)}$.

By (D.2), the update formula of these inner products of interests are given by

$\displaystyle\langle\mathbf{w}_{j,r}^{(t+1)},j\mathbf{u}\rangle$
$\displaystyle=\langle\mathbf{w}_{j,r}^{(t)},j\mathbf{u}\rangle+\frac{\eta\|\mathbf{u}\|_{2}^{2}}{m}\cdot\big{(}1-y_{i_{t}}f(\mathbf{x}_{i_{t}};\mathbf{W}^{(t)})\big{)}\cdot\sigma^{\prime}(\langle\mathbf{w}_{j,r}^{(t)},j\mathbf{u}\rangle
jy_{i_{t}})\cdot\mathbf{1}\\{i_{t}\notin\mathcal{W}\\},$ (D.4)
$\displaystyle\langle\mathbf{w}_{j,r}^{(t+1)},j\mathbf{v}\rangle$
$\displaystyle=\langle\mathbf{w}_{j,r}^{(t)},j\mathbf{v}\rangle+\frac{\eta\|\mathbf{v}\|_{2}^{2}}{m}\cdot\big{(}1-y_{i_{t}}f(\mathbf{x}_{i_{t}};\mathbf{W}^{(t)})\big{)}\cdot\sigma^{\prime}(\langle\mathbf{w}_{j,r}^{(t)},j\mathbf{v}\rangle
jy_{i_{t}}),$ (D.5)

Also by (D.2), the update formula of the inner products with noise vectors are
given by

$\displaystyle\langle\mathbf{w}_{j,r}^{(t+1)},\bm{\xi}_{i}\rangle$
$\displaystyle=\langle\mathbf{w}_{j,r}^{(t)},\bm{\xi}_{i}\rangle+\frac{\eta\cdot
jy_{i_{t}}}{m}\cdot\big{(}1-y_{i_{t}}f(\mathbf{x}_{i_{t}};\mathbf{W}^{(t)})\big{)}\cdot\left(\sigma^{\prime}(\langle\mathbf{w}_{j,r}^{(t)},\bm{\xi}_{i_{t}}\rangle)\cdot\langle\bm{\xi}_{i_{t}},\bm{\xi}_{i}\rangle\right.$
(D.6)
$\displaystyle\qquad+\left.\sigma^{\prime}(\langle\mathbf{w}_{j,r}^{(t)},\widetilde{\bm{\xi}}_{i_{t}}\rangle)\cdot\langle\widetilde{\bm{\xi}}_{i_{t}},\bm{\xi}_{i}\rangle\cdot\mathbf{1}\\{i_{t}\in\mathcal{W}\\}\right),\quad
i\in[n],$ (D.7)
$\displaystyle\langle\mathbf{w}_{j,r}^{(t+1)},\widetilde{\bm{\xi}}_{i}\rangle$
$\displaystyle=\langle\mathbf{w}_{j,r}^{(t)},\widetilde{\bm{\xi}}_{i}\rangle+\frac{\eta\cdot
jy_{i_{t}}}{m}\cdot\big{(}1-y_{i_{t}}f(\mathbf{x}_{i_{t}};\mathbf{W}^{(t)})\big{)}\cdot\left(\sigma^{\prime}(\langle\mathbf{w}_{j,r}^{(t)},\bm{\xi}_{i_{t}}\rangle)\cdot\langle\bm{\xi}_{i_{t}},\widetilde{\bm{\xi}}_{i}\rangle\right.$
(D.8)
$\displaystyle\qquad+\left.\sigma^{\prime}(\langle\mathbf{w}_{j,r}^{(t)},\widetilde{\bm{\xi}}_{i_{t}}\rangle)\cdot\langle\widetilde{\bm{\xi}}_{i_{t}},\widetilde{\bm{\xi}}_{i}\rangle\cdot\mathbf{1}\\{i_{t}\in\mathcal{W}\\}\right),\quad
i\in\mathcal{W}.$ (D.9)

At first glance, the update formulas given above seem intangible. The
following proposition indicates that we can separate the neurons into two
parts, with each individual part learning one kind of sample independently.
For simplicity, we let $\tilde{\eta}\coloneqq 2\eta\|\mathbf{u}\|^{2}_{2}/m$
and $\alpha=\|\mathbf{v}\|_{2}^{2}/\|\mathbf{u}\|_{2}^{2}$ and
$\tilde{f}_{t}=y_{{i_{t}}}f(\mathbf{x}_{i_{t}};\mathbf{W}^{(t)})$. For any
$j\in\\{\pm 1\\}$ and $s\geq 0$, we define effective running time for learning
label-$j$-samples as

$\displaystyle
t_{j}(s)=\min\big{\\{}t\in\mathbb{N}:t>t_{j}(s-1),\;y_{i_{t}}=j\big{\\}},$
(D.10)

with $t_{j}(0)=\min\\{t\in\mathbb{N}:y_{i_{t}}=j\\}$.

######  Proposition D.1.

Suppose that the sign stability condition holds before some
$T_{\mathrm{sign}}$, i.e., $\mathcal{U}^{(t)}_{\pm
j,\pm}=\mathcal{U}^{(0)}_{\pm j,\pm}:=\mathcal{U}_{\pm j,\pm}$ and
$\mathcal{V}^{(t)}_{\pm j,\pm}=\mathcal{V}^{(0)}_{\pm j,\pm}:=\mathcal{V}_{\pm
j,\pm}$ for $t\leq T_{\mathrm{sign}}$. Then for $s$ such that $t_{j}(s)\leq
T_{\mathrm{sign}}$, it holds that

$\displaystyle\langle{\mathbf{w}_{j,r}^{(t_{j}(s+1))}},{j\mathbf{u}}\rangle$
$\displaystyle=\langle{\mathbf{w}_{j,r}^{(t_{j}(s))}},{j\mathbf{u}}\rangle\cdot\big{(}1+\tilde{\eta}(1-\tilde{f}_{t_{j}(s)})\cdot\mathbf{1}\\{i_{t_{j}(s)}\in\mathcal{W}\\}\big{)},\quad\forall
r\in\mathcal{U}_{j,+};$ (D.11)
$\displaystyle\langle{\mathbf{w}_{-j,r}^{(t_{j}(s+1))}},{-j\mathbf{u}}\rangle$
$\displaystyle=\langle{\mathbf{w}_{-j,r}^{(t_{j}(s))}},{-j\mathbf{u}}\rangle\cdot\big{(}1-\tilde{\eta}(1-\tilde{f}_{t_{j}(s)})\cdot\mathbf{1}\\{i_{t_{j}(s)}\in\mathcal{W}\\}\big{)},\quad\forall
r\in\mathcal{U}_{-j,-};$ (D.12)
$\displaystyle\langle{\mathbf{w}_{j,r}^{(t_{j}(s+1))}},{j\mathbf{v}}\rangle$
$\displaystyle=\langle{\mathbf{w}_{j,r}^{(t_{j}(s))}},{j\mathbf{v}}\rangle\cdot\big{(}1+\alpha\tilde{\eta}(1-\tilde{f}_{t_{j}(s)})\big{)},\quad\forall
r\in\mathcal{V}_{j,+};$ (D.13)
$\displaystyle\langle{\mathbf{w}_{-j,r}^{(t_{j}(s+1))}},{-j\mathbf{v}}\rangle$
$\displaystyle=\langle{\mathbf{w}_{-j,r}^{(t_{j}(s))}},{-j\mathbf{v}}\rangle\cdot\big{(}1-\alpha\tilde{\eta}(1-\tilde{f}_{t_{j}(s)})\big{)},\quad\forall
r\in\mathcal{V}_{-j,-}.$ (D.14)

Moreover, for every $t\in(t_{j}(s),t_{j}(s+1)]$, it holds that

$\displaystyle\langle{\mathbf{w}_{j,r}^{(t)}},{j\mathbf{u}}\rangle$
$\displaystyle=\langle{\mathbf{w}_{j,r}^{(t_{j}(s)+1)}},{j\mathbf{u}}\rangle,\quad\forall
r\in\mathcal{U}_{j,+};$ (D.15)
$\displaystyle\langle{\mathbf{w}_{-j,r}^{(t)}},{-j\mathbf{u}}\rangle$
$\displaystyle=\langle{\mathbf{w}_{-j,r}^{(t_{j}(s)+1)}},{-j\mathbf{u}}\rangle,\quad\forall
r\in\mathcal{U}_{-j,-};$ (D.16)
$\displaystyle\langle{\mathbf{w}_{j,r}^{(t)}},{j\mathbf{v}}\rangle$
$\displaystyle=\langle{\mathbf{w}_{j,r}^{(t_{j}(s)+1)}},{j\mathbf{v}}\rangle,\quad\forall
r\in\mathcal{V}_{j,+};$ (D.17)
$\displaystyle\langle{\mathbf{w}_{-j,r}^{(t)}},{-j\mathbf{v}}\rangle$
$\displaystyle=\langle{\mathbf{w}_{-j,r}^{(t_{j}(s)+1)}},{-j\mathbf{v}}\rangle,\quad\forall
r\in\mathcal{V}_{-j,-}.$ (D.18)

###### Proof of Proposition D.1.

See Appendix D.6.1 for a detailed proof. ∎

This proposition helps to break down the dynamics of multiple data training
into two folds. To see this, it suffices to note that the following components

$\displaystyle\tilde{f}_{t_{j}(s)},\quad\left\\{\langle{\mathbf{w}_{j,r}^{(t)}},{j\mathbf{u}}\rangle\right\\}_{r\in\mathcal{U}_{j,+}},\quad\left\\{\langle{\mathbf{w}_{-j,r}^{(t)}},{-j\mathbf{u}}\rangle\right\\}_{r\in\mathcal{U}_{-j,-}},\quad\left\\{\langle{\mathbf{w}_{j,r}^{(t)}},{j\mathbf{v}}\rangle\right\\}_{r\in\mathcal{V}_{j,+}},\quad\left\\{\langle{\mathbf{w}_{-j,r}^{(t)}},{-j\mathbf{v}}\rangle\right\\}_{r\in\mathcal{V}_{-j,+}}$
(D.19)

are independent with $\\{\tilde{f}_{t}\\}_{i_{t}=-j}$ and the rest inner
products associated with $-j$.

###  D.2 Overview of Analysis

The roadmap towards proving our main theorem shares nearly the same logic with
the proof of single data setup (Appendix B). Basically, as long as the weak
signal component and the noise component are not learned in the sense that
these inner products remain negligible, we can prove that the inner products
associated with the strong signal would dominate and the oscillation would
accumulate at a linear rate. This further gives Lemma D.3 which shows the CNN
would learn effectively learn the weak signal
$\langle\mathbf{w}_{j,r}^{(t)},j\mathbf{v}\rangle$. Meanwhile, we can prove
that the influences from the negative part of weak signal learning
$\langle\mathbf{w}_{-j,r}^{(t)},j\mathbf{v}\rangle$ and the noise memorization
$\langle\mathbf{w}_{\pm 1,r}^{(t)},\bm{\xi}_{i}\rangle$,
$\langle\mathbf{w}_{\pm 1,r}^{(t)},\widetilde{\bm{\xi}}_{i}\rangle$ can be
well controlled (Propositions D.4). Putting all together, we can prove the
main result Theorem 4.3.

To be formal, we define two important stopping times as follows:

$\displaystyle T^{j}_{(\mathbf{v})}$ $\displaystyle=\min_{t\geq
0}\left\\{t:\frac{1}{m}\sum_{r\in[m]}\sigma(\langle\mathbf{w}_{j,r}^{(t)},j\mathbf{v}\rangle)\geq\delta/2\right\\},$
(D.20) $\displaystyle T_{(\bm{\xi})}$ $\displaystyle=\min_{t\geq
0}\left\\{t:\max_{r\in[m],j\in\\{\pm
1\\}}\left\\{\max_{i\in[n]}\left|\langle\mathbf{w}_{j,r}^{(t)},\bm{\xi}_{i}\rangle\right|,\max_{i\in\mathcal{W}}\left|\langle\mathbf{w}_{j,r}^{(t)},\widetilde{\bm{\xi}}_{i}\rangle\right|\right\\}\geq\delta/4\right\\}.$
(D.21)

We recap that $\mathcal{W}$ denotes the index set of weak data, and
$\widetilde{\bm{\xi}}_{i}$ denotes the Gaussian noise appearing on the lacking
strong signal patch for those weak data. Also we note that
$T^{j}_{(\mathbf{v})}$, $T_{(\bm{\xi})}\leq+\infty$, where the equal sign is
attainable. We then define

$\displaystyle
T_{\max}^{j}=\min\left\\{T^{j}_{(\mathbf{v})},T_{(\bm{\xi})}\right\\}.$ (D.22)

In the first place, following the same arguments as in the single data setup
(Appendix B), we can derive the boundedness and sign stability results before
time $T_{\max}^{j}$.

######  Lemma D.2 (Boundedness and sign stability).

Under Assumptions 4.1 and 4.2, for fixed $j\in\\{\pm 1\\}$, the followings
hold with probability at least $1-p=1-1/\mathrm{poly}(d)$:

  1. 1.

it holds that $\mathcal{U}_{j,+}^{(t)}=\mathcal{U}_{j,+}^{(0)}\neq\emptyset$
and $\mathcal{V}_{j,+}^{(t)}=\mathcal{V}_{j,+}^{(0)}\neq\emptyset$ for any
$t\in[0,T_{\max}^{j}]$. Hence the superscript $(t)$ can be dropped;

  2. 2.

for any $t\in[0,T_{\max}^{j}]$, we have that

$\displaystyle\max_{r\in[m]}\langle{\mathbf{w}_{j,r}^{(t)}},{j\mathbf{u}}\rangle$
$\displaystyle\leq 1.5\cdot(1.05\beta_{\mathbf{u},j}^{*}m)^{1/2},$ (D.23)

where $\beta_{\mathbf{u},j}^{*}$ is defined in Lemma B.5;

  3. 3.

for any $t\in[0,T_{\max}^{j}]$ it holds that

$\displaystyle\min_{r\in[m]}\langle{\mathbf{w}_{-j,r}^{(t)}},{-j\mathbf{u}}\rangle$
$\displaystyle\geq-{\sqrt{2\log(16m/p)}\cdot\sigma_{0}\|\mathbf{u}\|_{2}},$
(D.24)
$\displaystyle\min_{r\in[m]}\langle{\mathbf{w}_{-j,r}^{(t)}},{-j\mathbf{v}}\rangle$
$\displaystyle\geq-{\sqrt{2\log(16m/p)}\cdot\sigma_{0}\|\mathbf{v}\|_{2}};$
(D.25)

  4. 4.

for any $t\in[0,T_{\max}^{j}]$ such that $y_{i_{t}}=j$, it holds that

$\displaystyle\big{|}1-y_{i_{t}}f(\mathbf{x}_{i_{t}};\mathbf{W}^{(t)})\big{|}\leq
2.$ (D.26)

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

See Appendix D.4 for a detailed proof. ∎

This boundedness and sign stability result further implies weak signal
learning with an exponential rate, which is formally presented as follows.

######  Lemma D.3 (Weak signal learning).

Under Assumptions 4.1 and 4.2, with probability at least
$1-1/\mathrm{poly}(d)$, it holds that for any $j\in\\{\pm 1\\}$ and $0\leq
t_{1}\leq t_{2}\leq T_{\max}^{j}$ that

$\displaystyle\sum_{\begin{subarray}{c}s=t_{1}\\\
y_{i_{s}}=j\end{subarray}}^{t_{2}}\big{(}1-y_{i_{s}}f(\mathbf{x}_{i_{s}};\mathbf{W}^{(s)})\big{)}\geq\frac{\delta}{16}\cdot\big{(}1-(1.05-\delta/4)^{\frac{1}{2}}\big{)}\cdot(t_{2}-t_{1}+1)-\frac{m{(1.05)^{\frac{1}{2}}}}{2\eta\|\mathbf{u}\|_{2}^{2}(1.05-\delta/4)^{\frac{1}{2}}},$
(D.27)

where $\delta$ is specified in Assumption 4.2. Moreover, for
$r\in\mathcal{V}_{j,+}^{(0)}$, we have that

$\displaystyle\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\langle{\mathbf{w}_{j,r}^{(t_{2}+1)}},{j\mathbf{v}}\rangle$
$\displaystyle\geq\langle{\mathbf{w}_{j,r}^{(t_{1})}},{j\mathbf{v}}\rangle\\!\cdot\\!\exp\left\\{\frac{\eta\|\mathbf{v}\|_{2}^{2}}{32m}\\!\cdot\\!\big{(}\delta-\delta(1.05-\delta/4)^{\frac{1}{2}}\big{)}\\!\cdot\\!(t_{2}-t_{1}+1)-\frac{\|\mathbf{v}\|_{2}^{2}{(1.05)^{\frac{1}{2}}}}{\|\mathbf{u}\|_{2}^{2}(1.05-\delta/4)^{\frac{1}{2}}}\right\\}.$
(D.28)

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

See Appendix D.5 for a detailed proof. ∎

The last component to complete our proof of main theorem is controlling noise
memorization during the training process. For simplicity, we define the
maximum absolute value of the noise inner products over data as

$\displaystyle\Upsilon^{(t)}=\max_{r\in[m],j\in\\{\pm
1\\}}\left\\{\max_{i\in[n]}\left|\langle\mathbf{w}_{j,r}^{(t)},\bm{\xi}_{i}\rangle\right|,\max_{i\in\mathcal{W}}\left|\langle\mathbf{w}_{j,r}^{(t)},\widetilde{\bm{\xi}}_{i}\rangle\right|\right\\}.$
(D.29)

We have the following proposition to control the growth of $\Upsilon^{(t)}$.

######  Proposition D.4 (Noise memorization).

Under Assumptions 4.1 and 4.2, then with probability at least
$1-1/\mathrm{poly}(d)$, it holds for any $0\leq t_{1}\leq\min_{j\in\\{\pm
1\\}}\\{T_{\max}^{j}\\}-\widetilde{T}_{(\bm{\xi})}$ and $j\in\\{\pm 1\\}$ that

$\displaystyle\Upsilon^{(t)}\leq\Upsilon^{(t_{1})}\cdot(1+\epsilon),\quad\forall
r\in[m],\quad\forall t_{1}\leq t\leq t_{1}+\widetilde{T}_{(\bm{\xi})}$ (D.30)

where
$\widetilde{T}_{(\bm{\xi})}=\widetilde{\Theta}(mn\cdot\eta^{-1}\cdot\epsilon\cdot(1+\epsilon)^{-1}\cdot(\sigma_{p}^{2}d)^{-1})$
for any $\epsilon>0$.

###### Proof of Proposition D.4.

See Appendix D.6.3 for a detailed proof. ∎

###  D.3 Proof of Theorem 4.3

With Lemma D.2 and D.3 and Proposition D.4, we are ready to prove Theorem 4.3.

###### Proof of Theorem 4.3.

For the $j=\mathop{\mathrm{argmin}}_{j^{\prime}\in\\{\pm
1\\}}\\{T_{\max}^{j^{\prime}}\\}$, we are going to prove that $T_{\max}^{j}$
is bounded by a polynomial time by using contradiction. Specifically, we prove
that

$\displaystyle T_{\max}^{j}\leq
T_{j,0}\coloneqq\frac{32m}{\eta\|\mathbf{v}\|_{2}^{2}}\cdot\big{(}\delta-\delta(1.05-\delta/4)^{\frac{1}{2}}\big{)}^{-1}\cdot\Bigg{\\{}\log\left(\frac{2\sqrt{m\delta}}{\sigma_{0}\|\mathbf{v}\|_{2}}\right)+1.5\cdot\frac{\|\mathbf{v}\|_{2}^{2}}{\|\mathbf{u}\|_{2}^{2}}\cdot\sqrt{\frac{1.05}{1.05-\delta/4}}\Bigg{\\}}.$
(D.31)

Suppose that the result fails, then by definition we have that

$\displaystyle T_{\max}^{j}=T_{(\mathbf{v})}^{j}\wedge
T_{(\bm{\xi})}>T_{j,0}.$ (D.32)

Then Lemma D.2 and Lemma D.3 hold on $[0,T_{j,0}]$. By applying the lower
bound in Inequality (D.28) as well as Lemma A.4, we have that

$\displaystyle\max_{r\in[m]}\langle{\mathbf{w}_{j,r}^{(T_{j,0})}},{j\mathbf{v}}\rangle$
$\displaystyle\geq\max_{r\in[m]}\langle{\mathbf{w}_{j,r}^{(0)}},{j\mathbf{v}}\rangle\cdot\exp\left\\{\frac{\eta\|\mathbf{v}\|_{2}^{2}}{32m}\cdot\big{(}\delta-\delta(1.05-\delta/4)^{\frac{1}{2}}\big{)}\\!\cdot\\!T_{j,0}-1.5\cdot\frac{\|\mathbf{v}\|_{2}^{2}}{\|\mathbf{u}\|_{2}^{2}}\cdot\sqrt{\frac{1.05}{1.05-\delta/4}}\right\\}$
(D.33)
$\displaystyle\geq\frac{1}{2}\sigma_{0}\|\mathbf{v}\|_{2}\cdot\frac{2\sqrt{m\delta}}{\sigma_{0}\|\mathbf{v}\|_{2}}$
(D.34) $\displaystyle=\sqrt{m\delta}.$ (D.35)

This leads to the following,

$\displaystyle\frac{1}{m}\sum_{r\in[m]}\sigma(\langle{\mathbf{w}^{(T_{j,0})}_{j,r}},{j\mathbf{v}}\rangle)\geq\frac{1}{m}\cdot\max_{r\in[m]}(\langle{\mathbf{w}^{(T_{j,0})}_{j,r}},{j\mathbf{v}}\rangle)^{2}\geq\delta,$
(D.36)

which clearly contradicts the definition of $T^{j}_{(\mathbf{v})}$ in (D.20),
hence it must be that $T_{\max}^{j}\leq T_{j,0}<+\infty$.

In the following, we prove that
$T_{\max}^{j}=T_{(\mathbf{v})}^{j}<T_{(\bm{\xi})}$, for which our conclusion
directly follows due to (D.20). Again we prove by contradiction. Suppose that
$T_{\max}^{j}=T_{(\bm{\xi})}<T_{(\mathbf{v})}^{j}$, then $\Upsilon^{(t)}$
would reach $\delta/4$ for time less than $T_{j,0}$ due to definition of
$T_{(\bm{\xi})}$ in (D.21). But by Proposition D.4 with $\epsilon=1$, we know
$\Upsilon^{(t)}$ takes at least

$\displaystyle
K\widetilde{T}_{(\bm{\xi})}:=\widetilde{\Theta}\left(\frac{mn\sigma_{p}^{2}d}{\eta}\cdot\log\left(\frac{\delta}{\sigma_{0}\sigma_{p}\sqrt{d}}\right)\right)$
(D.37)

steps to reach $\delta/4$, where $\widetilde{T}_{(\bm{\xi})}$ is defined in
Proposition D.4. Then due to the scaling of the signal strength in Assumption
4.1, we can also find that $K\widetilde{T}_{(\bm{\xi})}>T_{j,0}$, which is a
contradiction with the definition of $T_{(\bm{\xi})}$. Therefore, we must have
that $T_{\max}^{j}=T_{(\mathbf{v})}^{j}$, which means that at
$t^{\star}=T_{\max}^{j}$,

$\displaystyle\frac{1}{m}\sum_{r\in[m]}\sigma(\langle\mathbf{w}_{j,r}^{(t^{\star})},j\mathbf{v}\rangle)\geq\frac{\delta}{2}.$
(D.38)

In the meanwhile, Proposition D.2 guarantees that at time
$t^{\star}=T_{\max}^{j}$,

$\displaystyle\frac{1}{m}\sum_{r\in[m]}\sigma(\langle\mathbf{w}_{-j,r}^{(t^{\star})},j\mathbf{v}\rangle)\leq\frac{\delta}{4}.$
(D.39)

Thus, we conclude that at time $t^{\star}$,

$\displaystyle\frac{1}{m}\sum_{r\in[m]}\sigma(\langle\mathbf{w}_{j,r}^{(t^{\star})},j\mathbf{v}\rangle)-\frac{1}{m}\sum_{r\in[m]}\sigma(\langle\mathbf{w}_{-j,r}^{(t^{\star})},j\mathbf{v}\rangle)\geq\frac{\delta}{4}.$
(D.40)

This finishes the proof of Theorem 4.3. ∎

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

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

Recall that $T_{\max}^{j}=T_{(\mathbf{v})}^{j}\wedge T_{(\bm{\xi})}$, where

$\displaystyle T_{(\mathbf{v})}^{j}$ $\displaystyle=\min_{t\geq
0}\left\\{t:\frac{1}{m}\sum_{r\in[m]}\sigma\big{(}\langle{\mathbf{w}_{j,r}^{(t)}},{j\mathbf{v}}\rangle\big{)}\geq\delta/2\right\\},$
(D.41) $\displaystyle T_{(\bm{\xi})}$ $\displaystyle=\min_{t\geq
0}\left\\{t:\max_{j\in\\{\pm
1\\},r\in[m],i\in[n]}\left|\langle{\mathbf{w}_{j,r}^{(t)}},{\bm{\xi}_{i}}\rangle\right|\vee\max_{j\in\\{\pm
1\\},r\in[m],i\in\mathcal{W}}\left|\langle{\mathbf{w}_{j,r}^{(t)}},{\widetilde{\bm{\xi}}_{i}}\rangle\right|\geq\delta/4\right\\}.$
(D.42)

We now define some notations to simplify our presentation. Recall that
$\tilde{f}=y_{i_{t}}f(\mathbf{x}_{i_{t}};\mathbf{W}^{(t)})$,
$\tilde{\eta}=2\eta\|\mathbf{u}\|_{2}^{2}/m$ and
$\alpha=\|\mathbf{v}\|_{2}^{2}/\|\mathbf{u}\|_{2}^{2}$. For fixed $j$, we
define

$\displaystyle\bar{S}_{j,k}\coloneqq\min\left\\{s\in\mathbb{N}:s>\bar{S}_{j,k-1}\text{
such that }\tilde{f}_{t_{j}(s)}\geq 1\text{ and
}\tilde{f}_{t_{j}(\max\\{s^{\prime}<s:i_{t_{j}(s^{\prime})}\notin\mathcal{W}\\})}<1\right\\},$
(D.43)

with $\bar{S}_{j,0}=0$, and

$\displaystyle\underaccent{\bar}{S}_{j,k}\coloneqq\min\left\\{s\in\mathbb{N}:s>\underaccent{\bar}{S}_{j,k-1}\text{
such that }i_{t_{j}(s)}\notin\mathcal{W},\;\tilde{f}_{t_{j}(s)}<1\text{ and
}\tilde{f}_{t_{j}(\max\\{s^{\prime}<s:i_{t_{j}(s^{\prime})}\notin\mathcal{W}\\})}\geq
1\right\\},$ (D.44)

with $\underaccent{\bar}{S}_{j,0}=0$. From the definition of $T_{\max}^{j}$,
we know that $i_{t_{j}(\bar{S}_{j,k})}\notin\mathcal{W}$ for $k$ such that
$t_{j}(\bar{S}_{j,k})\leq T_{\max}^{j}$, since otherwise
$\tilde{f}_{t_{j}(\bar{S}_{j,k})}<\delta<1$. Moreover we define

$\displaystyle\mathcal{U}_{j,+}\coloneqq\left\\{r\in[m]:\langle{\mathbf{w}_{j,r}^{(t_{j}(0))}},{j\mathbf{u}}\rangle>0\right\\},\quad\mathcal{U}_{j,-}\coloneqq\left\\{r\in[m]:\langle{\mathbf{w}_{j,r}^{(t_{j}(0))}},{j\mathbf{u}}\rangle\leq
0\right\\},$ (D.45)

and $\mathcal{V}_{j,\pm}$ are defined analogously.

The following analysis is nearly the same as the proof of one data case in the
sense that each step of the proof is organized exactly the same to the proof
of one data case. Therefore we suggest readers to refer to the roadmap
provided in Appendix B.1 frequently for better understanding.

We note that for $t\leq T_{(\mathbf{v})}^{j}\wedge T_{(\bm{\xi})}$, which is
the time scale we are mainly focusing on, it holds that

$\displaystyle\max_{j\in\\{\pm
1\\},r\in[m],i\in[n],i^{\prime}\in\mathcal{W}}\left|\langle{\mathbf{w}_{j,r}^{(t)}},{\bm{\xi}_{i}}\rangle\right|\vee\left|\langle{\mathbf{w}_{j,r}^{(t)}},{\widetilde{\bm{\xi}}_{i^{\prime}}}\rangle\right|$
$\displaystyle\leq\frac{\delta}{4},\quad\frac{1}{m}\sum_{r\in[m]}\sigma\big{(}\langle{\mathbf{w}_{j,r}^{(t)}},{j\mathbf{v}}\rangle\big{)}<\frac{\delta}{2}.$
(D.46)

Now we start presenting the proof of boundedness and sign stability with step-
by-step analysis. The $j$ is arbitrary but fixed throughout analysis. In view
of the effective running time for learning label-$j$-samples defined in
(D.10), (D.43), and (D.44), the proofs for a certain $j$ directly do induction
over $s$.

##### Step 1: Pre-$\bar{S}_{j,1}$ analysis.

Clearly at $s=0$, the lower bounds in Inequalities (D.24) and (D.25) are both
guaranteed by Lemma A.4. Also we know that $\tilde{f}_{t_{j}(0)}\ll 1$ and so
$\bar{S}_{j,1}\geq 1$. The initialization also guarantees that the upper bound
in Inequality (D.23) holds at $s=0$.

For $s\in[0,\bar{S}_{j,1})$, the definition of $\bar{S}_{j,1}$ indicates that
$\tilde{f}_{t_{j}(s)}\leq 1$. Therefore, from Proposition D.1 we can see that
the
$\langle{\mathbf{w}_{j,r}^{t_{j}(s)}},{j\mathbf{u}}\rangle,\;r\in\mathcal{U}_{j,+}$
and
$\langle{\mathbf{w}_{-j,r}^{t_{j}(s)}},{-j\mathbf{u}}\rangle,\;r\in\mathcal{U}_{-j,-}$
are non-decreasing in $s$ during this stage. One naturally infers that for all
$r\in\mathcal{U}_{-j,-}$, it holds that

$\displaystyle\langle{\mathbf{w}_{-j,r}^{(t_{j}(\bar{S}_{j,1}))}},{-j\mathbf{u}}\rangle\geq\langle{\mathbf{w}_{-j,r}^{(t_{j}(\bar{S}_{j,1}-1))}},{-j\mathbf{u}}\rangle\geq\langle{\mathbf{w}_{-j,r}^{(t_{j}(0))}},{-j\mathbf{u}}\rangle\geq-{\sqrt{2\log(16m/p)}\cdot\sigma_{0}\|\mathbf{u}\|_{2}}.$
(D.47)

Same can be verified for
$\langle{\mathbf{w}_{-j,r}^{(t_{j}(s))}},{-j\mathbf{v}}\rangle$ with
$r\in\mathcal{V}_{-j,-}$. Hence the lower bounds in Inequality (D.24) and
(D.25) are extended to $s\in[0,\bar{S}_{j,k}]$. Also, for these inner
products, the sign stability holds on $[0,\bar{S}_{j,1}]$, since
$\tilde{\eta}<4/5$ and thus we have

$\displaystyle
1\pm\frac{2\eta\|\mathbf{u}\|_{2}^{2}}{m}\cdot(1-\tilde{f}_{t_{j}(s)})$
$\displaystyle\geq 1-\tilde{\eta}\big{(}1+o(1)\big{)}\geq 0,$ (D.48)
$\displaystyle
1\pm\frac{2\eta\|\mathbf{v}\|_{2}^{2}}{m}\cdot(1-\tilde{f}_{t_{j}(s)})$
$\displaystyle\geq 1-\alpha\tilde{\eta}\big{(}1+o(1)\big{)}\geq 0.$ (D.49)

Then we turn to upper bound
$\langle{\mathbf{w}_{j,r}^{(t_{j}(s))}},{j\mathbf{u}}\rangle$ for
$s\in[0,\bar{S}_{j,1})$. Note that, for $s$ such that
$i_{t_{j}(s)}\notin\mathcal{W}$, the definition of $T_{\max}^{j}$ implies that

$\displaystyle 1-\delta\geq\tilde{f}_{t_{j}(s)}$
$\displaystyle\geq\frac{1}{m}\sum_{r\in[m]}\sigma\big{(}\langle{\mathbf{w}_{j,r}^{(t_{j}(s))}},{j\mathbf{u}}\rangle\big{)}+\frac{1}{m}\sum_{r\in[m]}\sigma\bigl{(}\langle{\mathbf{w}_{j,r}^{(t_{j}(s))}},{j\mathbf{v}}\rangle\bigr{)}$
(D.50)
$\displaystyle\qquad-\frac{1}{m}\sum_{r\in[m]}\sigma\big{(}-\langle{\mathbf{w}_{-j,r}^{(t_{j}(s))}},{-j\mathbf{u}}\rangle\big{)}-\frac{1}{m}\sum_{r\in[m]}\sigma\big{(}-\langle{\mathbf{w}_{-j,r}^{(t_{j}(s))}},{-j\mathbf{v}}\rangle\big{)}$
(D.51)
$\displaystyle\qquad-\Big{|}\frac{1}{m}\sum_{r\in[m]}\sigma\big{(}\langle{\mathbf{w}_{j,r}^{(t_{j}(s))}},{\bm{\xi}_{i}}\rangle\big{)}+\frac{1}{m}\sum_{r\in[m]}\sigma\big{(}\langle{\mathbf{w}_{-j,r}^{(t_{j}(s))}},{\bm{\xi}_{i}}\rangle\big{)}\Big{|}$
(D.52)
$\displaystyle\geq\frac{1}{m}\sum_{r\in[m]}\sigma\big{(}\langle{\mathbf{w}_{j,r}^{(t_{j}(s))}},{j\mathbf{u}}\rangle\big{)}-2\times
o(1)-2\times\delta/4.$ (D.53)

As a consequence,

$\frac{1}{m}\sum_{r\in[m]}\sigma\big{(}\langle{\mathbf{w}_{j,r}^{(t_{j}(s))}},{j\mathbf{u}}\rangle\big{)}\leq
1-\delta/2+o(1)\leq 1.05.$

Thanks to the local sign stability, Lemma B.5 implies that

$\displaystyle\max_{r\in[m]}\langle{\mathbf{w}_{j,r}^{(t_{j}(s))}},{j\mathbf{u}}\rangle\leq(1.05\beta^{*}_{\mathbf{u},j}m)^{1/2}.$
(D.54)

If otherwise $s\in[0,\bar{S}_{j,k-1})$ such that $i_{t_{j}(s)}\in\mathcal{W}$,
then we choose
$\tilde{s}=\min\\{s^{\prime}>s:i_{t_{j}(s)}\notin\mathcal{W}\\}$. It holds
that either $\tilde{s}<\bar{S}_{j,1}$, or $\tilde{s}=\bar{S}_{j,1}$. For the
previous case, similar argument implies that

$\displaystyle\langle{\mathbf{w}_{j,r}^{(t_{j}(s))}},{j\mathbf{u}}\rangle\leq\langle{\mathbf{w}_{j,r}^{(t_{j}(\tilde{s}))}},{j\mathbf{u}}\rangle\leq(1.05\beta^{*}_{\mathbf{u},j}m)^{1/2}.$
(D.55)

The latter case reduces to establish the upper bound for
$t_{j}(\bar{S}_{j,1})$, which is derived in the next step.

##### Step 2.1: Bounding
$\langle{\mathbf{w}_{j,r}^{(t_{j}(s))}},{j\mathbf{u}}\rangle$ for
$s\in[\bar{S}_{j,1},\underaccent{\bar}{S}_{j,1})$.

Since the weak data does not contributes to learning strong signal, as
indicated in Proposition D.1, we know that

$\langle{\mathbf{w}_{j,r}^{(t_{j}(\bar{S}_{j,1}))}},{j\mathbf{u}}\rangle=\langle{\mathbf{w}_{j,r}^{(t_{j}(\tilde{S}_{j,1}))}},{j\mathbf{u}}\rangle\cdot\big{(}1+\tilde{\eta}(1-\tilde{f}_{t_{j}(\tilde{S}_{j,1})})\big{)},$

where
$\tilde{S}_{j,1}=\max\\{s\leq\tilde{S}_{j,1}-1:i_{t_{j}(s)}\notin\mathcal{W}\\}$.

We begin with a proposition that is parallel to Proposition B.9.

######  Proposition D.5.

For simplicity, we assume that $i_{t_{j}(\bar{S}_{j,k}-1)}\notin\mathcal{W}$
and $\tilde{S}_{j,k}=\bar{S}_{j,k}-1$. Otherwise we can find the last step
before $\bar{S}_{j,k}$ such that $i_{t_{j}(s)}\notin\mathcal{W}$ and leverage
the previous observation in Equation (D.4). Suppose that

$\displaystyle E_{t_{j}(\bar{S}_{j,k}-1)}\coloneqq$
$\displaystyle\frac{1}{m}\sum_{r\in[m]}\sigma\big{(}-\langle{\mathbf{w}_{-j,r}^{(t_{j}(\bar{S}_{j,k}-1))}},{-j\mathbf{u}}\rangle\big{)}+\sigma\big{(}-\langle{\mathbf{w}_{j,r}^{(t_{j}(\bar{S}_{j,k}-1))}},{-j\mathbf{v}}\rangle\big{)}\leq\delta/4,$
(D.56) $\displaystyle\Upsilon^{(t_{j}(\bar{S}_{j,k}))}\coloneqq$
$\displaystyle\max_{j\in\\{\pm
1\\},r\in[m],i\in[n]}\left|\langle{\mathbf{w}_{j,r}^{(t_{j}(\bar{S}_{j,k}))}},{\bm{\xi}_{i}}\rangle\right|\vee\max_{j\in\\{\pm
1\\},r\in[m],i\in\mathcal{W}}\left|\langle{\mathbf{w}_{j,r}^{(t_{j}(\bar{S}_{j,k}))}},{\widetilde{\bm{\xi}}_{i}}\rangle\right|\leq\delta/4,$
(D.57)

then we have that

$\displaystyle\tilde{f}_{t_{j}(\bar{S}_{j,k}-1)}\geq\frac{\tilde{\eta}+2-\sqrt{\tilde{\eta}^{2}+4\tilde{\eta}}}{2\tilde{\eta}},$
(D.58)

and that

$\displaystyle\tilde{f}_{t_{j}(\bar{S}_{j,k})}$
$\displaystyle\leq\left(1+\tilde{\eta}\big{(}1-\tilde{f}_{t_{j}(\bar{S}_{j,k}-1)}\big{)}\right)^{2}+2E_{t_{j}(\bar{S}_{j,k}-1)}+{\Upsilon^{(t_{j}(\bar{S}_{j,k}))}}^{2}$
(D.59)
$\displaystyle\leq\bigl{(}\tilde{\eta}/2+\sqrt{\tilde{\eta}^{2}/4+\tilde{\eta}}\bigr{)}^{2}+2E_{t_{j}(\bar{S}_{j,k}-1)}+{\Upsilon^{(t_{j}(\bar{S}_{j,k}))}}^{2}.$
(D.60)

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

See Appendix D.6.4 for a detailed proof. ∎

With this proposition, we can derive an upper bound on
$\langle{\mathbf{w}_{j,r}^{(t_{j}(\bar{S}_{j,1}))}},{j\mathbf{u}}\rangle$. One
step gradient (D.11) implies that, for $r\in\mathcal{U}_{j,+}$, it holds that

$\displaystyle\langle{\mathbf{w}_{j,r}^{(t_{j}(\bar{S}_{j,1}))}},{j\mathbf{u}}\rangle$
$\displaystyle=\langle{\mathbf{w}_{j,r}^{(t_{j}(\bar{S}_{j,1}-1))}},{j\mathbf{u}}\rangle\cdot\left(1+\tilde{\eta}\big{(}1-\tilde{f}_{t_{j}(\bar{S}_{j,1}-1)}\big{)}\right)$
(D.61)
$\displaystyle\leq\langle{\mathbf{w}_{j,r}^{(t_{j}(\bar{S}_{j,1}-1))}},{j\mathbf{u}}\rangle\cdot\left(1+\tilde{\eta}\left(1-\frac{\tilde{\eta}+2-\sqrt{\tilde{\eta}^{2}+4\tilde{\eta}}}{2\tilde{\eta}}\right)\right)$
(D.62) $\displaystyle\leq 1.5\cdot(1.05\beta^{*}_{\mathbf{u},j}m)^{1/2}.$
(D.63)

Here the first inequality comes from Inequality (D.58). Note that the upper
bound on
$\langle{\mathbf{w}_{j,r}^{(t_{j}(\bar{S}_{j,1}-1))}},{j\mathbf{u}}\rangle$
has been derived in Inequality (D.55) in Step 1.. Taking $\tilde{\eta}=4/5$
easily implies the second inequality above.

This upper bound continues to hold for
$\langle{\mathbf{w}_{j,r}^{(t_{j}(s))}},{j\mathbf{u}}\rangle$ with
$s\in[\bar{S}_{j,1},\underaccent{\bar}{S}_{j,1})$ because of monotonicity. We
consider the lower bound for
$\langle{\mathbf{w}_{j,r}^{(t_{j}(s))}},{j\mathbf{u}}\rangle$ with
$s\in[\bar{S}_{j,1},\underaccent{\bar}{S}_{j,1})$ and
$i_{t_{j}(s)}\notin\mathcal{W}$. For these $s$, we have that

$\displaystyle 1+\delta<\tilde{f}_{t_{j}(s)}$
$\displaystyle\leq\frac{1}{m}\sum_{r\in[m]}\sigma\big{(}\langle{\mathbf{w}_{j,r}^{(t_{j}(s))}},{j\mathbf{u}}\rangle\big{)}+\frac{1}{m}\sum_{r\in[m]}\sigma\big{(}\langle{\mathbf{w}_{j,r}^{(t_{j}(s))}},{j\mathbf{v}}\rangle\big{)}+(\text{negative
part})+(\text{noise part})$ (D.64)
$\displaystyle\leq\frac{1}{m}\sum_{r\in[m]}\sigma\big{(}\langle{\mathbf{w}_{j,r}^{(t_{j}(s))}},{j\mathbf{u}}\rangle\big{)}+\delta/2+\delta/4.$
(D.65)

Combining with Lemma B.5, we obtain that

$\displaystyle\max_{r\in[m]}\langle{\mathbf{w}_{j,r}^{(t_{j}(s))}},{j\mathbf{u}}\rangle\geq(\beta^{*}_{\mathbf{u},j}m)^{1/2},$
(D.66)

for $s\in[\bar{S}_{j,1},\underaccent{\bar}{S}_{j,1})$ and
$i_{t_{j}(s)}\notin\mathcal{W}$.

##### Step 2.2: Lower bounding
$\max_{r}\langle{\mathbf{w}_{y,r}^{(t_{j}(\underaccent{\bar}{S}_{j,k}))}},{y\mathbf{u}}\rangle$.

Same to the proof of Proposition D.5, we can assume that
$i_{t_{j}(\underaccent{\bar}{S}_{j,1}-1)}\notin\mathcal{W}$, without loss of
generality.

Note that, while $\tilde{f}_{t_{j}(s)}$ is not monotonically changing in
$s\in[\bar{S}_{j,1},\underaccent{\bar}{S}_{j,1}]$ in the presence of noise
components, the inner products are still changing monotonically, as indicated
in Proposition D.1. Therefore, we can leverage the control over noise
components to derive an approximate monotonic property. Specifically, the
inner products

$\displaystyle\sigma\big{(}\langle{\mathbf{w}_{j,r}^{(t_{j}(s))}},{j\mathbf{u}}\rangle\big{)},\quad-\sigma\big{(}\langle{\mathbf{w}_{-j,r}^{(t_{j}(s))}},{j\mathbf{u}}\rangle\big{)},\quad\sigma\big{(}\langle{\mathbf{w}_{j,r}^{(t_{j}(s))}},{j\mathbf{v}}\rangle\big{)},\quad-\sigma\big{(}\langle{\mathbf{w}_{-j,r}^{(t_{j}(s))}},{j\mathbf{v}}\rangle\big{)},$
(D.67)

are decreasing in $s\in[\bar{S}_{j,1},\underaccent{\bar}{S}_{j,1}]$. From
Inequality (D.153) in the proof of Proposition D.5, we know that

$\displaystyle\tilde{f}_{t_{j}(\underaccent{\bar}{S}_{j,1}-1)}$
$\displaystyle\leq\tilde{f}_{t_{j}(\bar{S}_{j,1})}-\frac{1}{m}\sum_{r\in[m]}\sigma\big{(}\langle{\mathbf{w}_{j,r}^{(t_{j}(\bar{S}_{j,1}))}},{\bm{\xi}_{i_{t_{j}(\bar{S}_{j,1})}}}\rangle\big{)}-\sigma\big{(}\langle{\mathbf{w}_{-j,r}^{(t_{j}(\bar{S}_{j,1}))}},{\bm{\xi}_{i_{t_{j}(\bar{S}_{j,1})}}}\rangle\big{)}$
(D.68)
$\displaystyle\qquad+\frac{1}{m}\sum_{r\in[m]}\sigma\big{(}\langle{\mathbf{w}_{j,r}^{(t_{j}(\underaccent{\bar}{S}_{j,1}-1))}},{\bm{\xi}_{i_{t_{j}(\underaccent{\bar}{S}_{j,1}-1)}}}\rangle\big{)}-\sigma\big{(}\langle{\mathbf{w}_{-j,r}^{(t_{j}(\underaccent{\bar}{S}_{j,1}-1))}},{\bm{\xi}_{i_{t_{j}(\underaccent{\bar}{S}_{j,1}-1)}}}\rangle\big{)}$
(D.69)
$\displaystyle\leq\big{(}\tilde{\eta}/2+\sqrt{\tilde{\eta}^{2}/4+\tilde{\eta}}\big{)}^{2}+2E_{T_{j}(\bar{S}_{j,1}-1)}+{\Upsilon^{(t_{j}(\underaccent{\bar}{S}_{j,1}))}}^{2}.$
(D.70)

Recall that in Step 1., we proved that $E_{j(\bar{S}_{j,1}-1)}\leq
2({\sqrt{2\log(16m/p)}\cdot\sigma_{0}\|\mathbf{u}\|_{2}})^{2}=o(1)$. Thus from
doing one-step gradient descent (D.11), we know that for
$r\in\mathcal{U}_{j,+}$, it holds that

$\displaystyle\langle{\mathbf{w}_{j,r}^{(t_{j}(\underaccent{\bar}{S}_{j,1}))}},{j\mathbf{u}}\rangle$
$\displaystyle=\langle{\mathbf{w}_{j,r}^{(t_{j}(\underaccent{\bar}{S}_{j,1}-1))}},{j\mathbf{u}}\rangle\cdot\left(1+\tilde{\eta}\big{(}1-\tilde{f}_{t_{j}(\underaccent{\bar}{S}_{j,1}-1)}\big{)}\right)$
(D.71)
$\displaystyle\geq\langle{\mathbf{w}_{j,r}^{(t_{j}(\underaccent{\bar}{S}_{j,1}-1))}},{j\mathbf{u}}\rangle\cdot\left(1+\tilde{\eta}\big{(}1-(\tilde{\eta}/2+\sqrt{\tilde{\eta}^{2}/4+\tilde{\eta}})^{2}\big{)}-0.1\right)$
(D.72) $\displaystyle\geq 0.1\cdot(\beta^{*}_{\mathbf{u},j}m)^{1/2}.$ (D.73)

Here the first inequality is by (D.70), $E_{j(\bar{S}_{j,1}-1)}=o(1)$ and the
definition of $T_{(\bm{\xi})}$, and the second inequality is a consequence of
Inequality (B.73). This positive constant-level lower bound guarantees that
our $\tilde{\eta}$ choice is sufficient for the sign stability to hold for
$s\in[\bar{S}_{j,1},\underaccent{\bar}{S}_{j,2}]$, as shown in the next step.

##### Step 2.3: Lower bounding
$\langle{\mathbf{w}_{-j,r}^{(t_{j}(\underaccent{\bar}{S}_{-j,1}))}},{-j\mathbf{u}}\rangle$
and
$\langle{\mathbf{w}_{-j,r}^{(t_{j}(\underaccent{\bar}{S}_{j,1}))}},{-j\mathbf{v}}\rangle$.

It suffices to consider $r\in\mathcal{V}_{-j,-}$ and $r\in\mathcal{U}_{-j,-}$.
Inequality (D.73) indicates that

$\displaystyle
1\ll\frac{\langle{\mathbf{w}_{j,r}^{(t_{j}(\underaccent{\bar}{S}_{j,1}))}},{j\mathbf{u}}\rangle}{\langle{\mathbf{w}_{j,r}^{(t_{j}(0))}},{j\mathbf{u}}\rangle}=\prod_{s=0,i_{t_{j}(s)}\notin\mathcal{W}}^{\underaccent{\bar}{S}_{j,1}-1}\left(1+\tilde{\eta}\big{(}1-\tilde{f}_{t_{j}(s)}\big{)}\right)\leq\exp\left\\{\tilde{\eta}\sum_{s=0,i_{t_{j}(s)}\notin\mathcal{W}}^{\underaccent{\bar}{S}_{j,1}-1}\big{(}1-\tilde{f}_{t_{j}(s)}\big{)}\right\\}.$
(D.74)

Therefore,

$\displaystyle\sum_{s=0,i_{t_{j}(s)}\in\mathcal{W}}^{\underaccent{\bar}{S}_{j,1}-1}\big{(}1-\tilde{f}_{t_{j}(s)}\big{)}>0.$
(D.75)

Now we can prove the lower bound. For $r\in\mathcal{U}_{-j,-}$, we have that

$\displaystyle\langle{\mathbf{w}_{-j,r}^{(t_{j}(\underaccent{\bar}{S}_{j,1}))}},{-j\mathbf{u}}\rangle$
$\displaystyle=\langle{\mathbf{w}_{-j,r}^{(t_{j}(0))}},{-j\mathbf{u}}\rangle\cdot\prod_{s=0,i_{t_{j}(s)}\notin\mathcal{W}}^{\underaccent{\bar}{S}_{j,1}-1}\left(1-\tilde{\eta}\big{(}1-\tilde{f}_{t_{j}(s)}\big{)}\right)$
(D.76)
$\displaystyle\geq\langle{\mathbf{w}_{-j,r}^{(t_{j}(0))}},{-j\mathbf{u}}\rangle\cdot\exp\left\\{-\tilde{\eta}\sum_{s=0,i_{t_{j}(s)}\notin\mathcal{W}}^{\underaccent{\bar}{S}_{j,1}-1}\big{(}1-\tilde{f}_{t_{j}(s)}\big{)}\right\\}$
(D.77)
$\displaystyle\geq\langle{\mathbf{w}_{-j,r}^{(t_{j}(0))}},{-j\mathbf{u}}\rangle\geq-{\sqrt{2\log(16m/p)}\cdot\sigma_{0}\|\mathbf{u}\|_{2}}.$
(D.78)

On the other hand, for $s\in[0,\underaccent{\bar}{S}_{j,1}-1]$ such that
$i_{t_{j}(s)}\in\mathcal{W}$, condition $t\leq
T_{\max}^{j}=T_{(\mathbf{v})}^{j}\wedge T_{(\bm{\xi})}$ guarantees that

$\displaystyle\tilde{f}_{t_{j}(s)}$
$\displaystyle=\frac{1}{m}\sum_{r\in[m]}\sigma\big{(}\langle{\mathbf{w}_{j,r}^{(t_{j}(s))}},{j\mathbf{v}}\rangle\big{)}-\sigma\big{(}-\langle{\mathbf{w}_{-j,r}^{(t_{j}(s))}},{-j\mathbf{v}}\rangle\big{)}$
(D.79)
$\displaystyle\qquad+\frac{1}{m}\sum_{r\in[m]}\sigma\big{(}\langle{\mathbf{w}_{j,r}^{(t_{j}(s))}},{\bm{\xi}_{i_{t_{j}(s)}}}\rangle\big{)}-\sigma\big{(}\langle{\mathbf{w}_{-j,r}^{(t_{j}(s))}},{\bm{\xi}_{i_{t_{j}(s)}}}\rangle\big{)}$
(D.80)
$\displaystyle\qquad+\frac{1}{m}\sum_{r\in[m]}\sigma\big{(}\langle{\mathbf{w}_{j,r}^{(t_{j}(s))}},{\widetilde{\bm{\xi}}_{i_{t_{j}(s)}}}\rangle\big{)}-\sigma\big{(}\langle{\mathbf{w}_{-j,r}^{(t_{j}(s))}},{\widetilde{\bm{\xi}}_{i_{t_{j}(s)}}}\rangle\big{)}$
(D.81) $\displaystyle\leq\delta/2+2\times\delta/4$ (D.82) $\displaystyle\leq
1.$ (D.83)

Hence we derive that

$\displaystyle\sum_{s\in[0,\underaccent{\bar}{S}_{j,1}-1]}\bigl{(}1-\tilde{f}_{t_{j}(s)}\bigr{)}=\sum_{\begin{subarray}{c}s\in[0,\underaccent{\bar}{S}_{j,1}-1]\\\
i_{t_{j}(s)}\in\mathcal{W}\end{subarray}}\bigl{(}1-\tilde{f}_{t_{j}(s)}\bigr{)}+\sum_{\begin{subarray}{c}s\in[0,\underaccent{\bar}{S}_{j,1}-1]\\\
i_{t_{j}(s)}\notin\mathcal{W}\end{subarray}}\bigl{(}1-\tilde{f}_{t_{j}(s)}\bigr{)}\geq
0.$ (D.84)

And in consequence, for $r\in\mathcal{V}_{j,-}$ it holds that

$\displaystyle\langle{\mathbf{w}_{-j,r}^{(t_{j}(\underaccent{\bar}{S}_{j,1}))}},{-j\mathbf{v}}\rangle$
$\displaystyle=\langle{\mathbf{w}_{-j,r}^{(t_{j}(0))}},{-j\mathbf{v}}\rangle\cdot\prod_{s=0}^{\underaccent{\bar}{S}_{j,1}-1}\left(1-\alpha\tilde{\eta}\big{(}1-\tilde{f}_{t_{j}(s)}\big{)}\right)$
(D.85)
$\displaystyle\geq\langle{\mathbf{w}_{-j,r}^{(t_{j}(0))}},{-j\mathbf{v}}\rangle\cdot\exp\left\\{-\alpha\tilde{\eta}\sum_{s=0}^{\underaccent{\bar}{S}_{j,1}-1}\big{(}1-\tilde{f}_{t_{j}(s)}\big{)}\right\\}$
(D.86)
$\displaystyle\geq\langle{\mathbf{w}_{-j,r}^{(t_{j}(0))}},{-j\mathbf{v}}\rangle\geq-{\sqrt{2\log(16m/p)}\cdot\sigma_{0}\|\mathbf{v}\|_{2}}.$
(D.87)

The monotonicity again extends lower bounds in Inequalities (D.87) and (D.78)
to $s\in[\bar{S}_{j,1},\bar{S}_{j,2}]$. And the sign stability naturally holds
on this interval.

##### Step 2.4 & Finalizing.

Thanks to the sign stability proved in the last step, we can now apply Lemma
B.5 to derive that the upper bound in Inequality (D.23) continues to hold for
all $s\in[\underaccent{\bar}{S}_{j,1},\bar{S}_{j,2}]$, with exactly the same
argument as the Step 1.. With an inductive argument that exactly repeats the
argument above, we can infer that all the results in Lemma D.2 holds for
$t_{j}(s)$ with $s\in[\bar{S}_{j,1},\bar{S}_{j,2}]$. Proposition D.1 implies
that for any $t\in\mathbb{N}$ we can find $s_{t}\in\mathbb{N}$ such that
$t_{j}(s_{t})\leq t<t_{j}(s_{t}+1)$ and
$\langle{\mathbf{w}_{j,r}^{(t)}},{j\mathbf{u}}\rangle=\langle{\mathbf{w}_{j,r}^{(t_{j}(s_{t}))}},{j\mathbf{u}}\rangle$
(so are all other inner products), therefore all the results in Lemma D.2 hold
for $t\leq T_{\max}^{j}$. ∎

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

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

For any $0\leq t_{1}\leq t_{2}\leq T_{\max}^{j}$, $j\in\\{\pm 1\\}$, and
$r\in\mathcal{U}_{j,+}^{(t)}$, by (D.4),

$\displaystyle\langle\mathbf{w}_{j,r}^{(t_{2}+1)},j\mathbf{u}\rangle$
$\displaystyle=\langle\mathbf{w}_{j,r}^{(t_{1})},j\mathbf{u}\rangle+\frac{2\eta\|\mathbf{u}\|_{2}^{2}}{m}\cdot\sum_{\begin{subarray}{c}t_{1}\leq
s\leq t_{2}\\\ y_{i_{s}}=j,i_{s}\notin\mathcal{W}\\\
y_{i_{s}}f(\mathbf{x}_{i_{s}};\mathbf{W}^{(s)})>1\end{subarray}}\big{(}1-y_{i_{s}}f(\mathbf{x}_{i_{s}};\mathbf{W}^{(s)})\big{)}\cdot\langle\mathbf{w}_{j,r}^{(s)},j\mathbf{u}\rangle$
(D.88)
$\displaystyle\qquad+\frac{2\eta\|\mathbf{u}\|_{2}^{2}}{m}\cdot\sum_{\begin{subarray}{c}t_{1}\leq
s\leq t_{2}\\\ y_{i_{s}}=j,i_{s}\notin\mathcal{W}\\\
y_{i_{s}}f(\mathbf{x}_{i_{s}};\mathbf{W}^{(s)})<1\end{subarray}}\big{(}1-y_{i_{s}}f(\mathbf{x}_{i_{s}};\mathbf{W}^{(s)})\big{)}\cdot\langle\mathbf{w}_{j,r}^{(s)},j\mathbf{u}\rangle,$
(D.89)

Note that for $0\leq t_{1}\leq t_{2}\leq T_{\max}^{j}$, we can apply the
conclusions of Lemma D.2. Specifically, we consider the maximal neuron
$r^{*}=\mathop{\mathrm{argmax}}_{r\in[m]}\langle{\mathbf{w}_{j,r}^{(t)}},{j\mathbf{u}}\rangle$,
and

$\displaystyle{(1.05)^{\frac{1}{2}}}\cdot(\beta^{*}_{\mathbf{u},j}m)^{\frac{1}{2}}$
$\displaystyle\geq\left|\langle\mathbf{w}_{j,r^{*}}^{(t_{2}+1)},j\mathbf{u}\rangle-\langle\mathbf{w}_{j,r^{*}}^{(t_{1})},j\mathbf{u}\rangle\right|$
(D.90)
$\displaystyle=\frac{2\eta\|\mathbf{u}\|_{2}^{2}}{m}\cdot\left|\sum_{\begin{subarray}{c}t_{1}\leq
s\leq t_{2}\\\ y_{i_{s}}=j,i_{s}\notin\mathcal{W}\\\
y_{i_{s}}f(\mathbf{x}_{i_{s}};\mathbf{W}^{(s)})>1\end{subarray}}\big{(}1-y_{i_{s}}f(\mathbf{x}_{i_{s}};\mathbf{W}^{(s)})\big{)}\cdot\underbrace{\langle\mathbf{w}_{j,r^{*}}^{(s)},j\mathbf{u}\rangle}_{{\color[rgb]{1,0,0}>(\beta^{*}_{\mathbf{u},j}m)^{\frac{1}{2}}}}\right.$
(D.91) $\displaystyle\qquad\left.-\sum_{\begin{subarray}{c}t_{1}\leq s\leq
t_{2}\\\ y_{i_{s}}=j,i_{s}\notin\mathcal{W}\\\
y_{i_{s}}f(\mathbf{x}_{i_{s}};\mathbf{W}^{(s)})<1\end{subarray}}\big{(}1-y_{i_{s}}f(\mathbf{x}_{i_{s}};\mathbf{W}^{(s)})\big{)}\cdot\underbrace{\langle\mathbf{w}_{j,r^{*}}^{(s)},j\mathbf{u}\rangle}_{{\color[rgb]{1,0,0}<(1.05-\delta/4)^{\frac{1}{2}}\cdot(\beta^{*}_{\mathbf{u},j}m)^{\frac{1}{2}}}}\right|,$
(D.92)

where the red remarks follow from Lemma B.5. Rearranging terms, we conclude
from (D.90) that

$\displaystyle\sum_{\begin{subarray}{c}t_{1}\leq s\leq t_{2}\\\
y_{i_{s}}=j,i_{s}\notin\mathcal{W}\\\
y_{i_{s}}f(\mathbf{x}_{i_{s}};\mathbf{W}^{(s)})<1\end{subarray}}\big{(}1-y_{i_{s}}f(\mathbf{x}_{i_{s}};\mathbf{W}^{(s)})\big{)}$
(D.93)
$\displaystyle\qquad\geq\left(1.05-\delta/4\right)^{-\frac{1}{2}}\cdot\sum_{\begin{subarray}{c}t_{1}\leq
s\leq t_{2}\\\ y_{i_{s}}=j,i_{s}\notin\mathcal{W}\\\
y_{i_{s}}f(\mathbf{x}_{i_{s}};\mathbf{W}^{(s)})>1\end{subarray}}\big{(}y_{i_{s}}f(\mathbf{x}_{i_{s}};\mathbf{W}^{(s)})-1\big{)}-\frac{m{(1.05)^{\frac{1}{2}}}}{2\eta\|\mathbf{u}\|_{2}^{2}(1.05-\delta/4)^{\frac{1}{2}}},$
(D.94)

Under Assumption 4.1, with probability at least $1-1/\mathrm{poly}(d)$, it
holds that

$\displaystyle\left|\left\\{t_{1}\leq s\leq
t_{2}:y_{i_{s}}=j,i_{s}\notin\mathcal{W}\right\\}\right|\geq\frac{1}{4}\cdot(t_{2}-t_{1}+1),$
(D.95)

Combining (D.93) and (D.95), we can finally prove that

$\displaystyle\sum_{\begin{subarray}{c}s=t_{1}\\\
y_{i_{s}}=j,i_{s}\notin\mathcal{W}\end{subarray}}^{t_{2}}\\!\\!\\!\\!\\!\\!1-y_{i_{s}}f(\mathbf{x}_{i_{s}};\mathbf{W}^{(s)})\geq\frac{\delta}{8}\\!\cdot\\!\big{(}1-(1.05-\delta/4)^{\frac{1}{2}}\big{)}\\!\cdot\\!(t_{2}-t_{1}+1)-\frac{m{(1.05)^{\frac{1}{2}}}}{2\eta\|\mathbf{u}\|_{2}^{2}(1.05-\delta/4)^{\frac{1}{2}}}.$
(D.96)

Finally, for the weak data $i_{s}\in\mathcal{W}$, under Assumption 4.1, with
probability at least $1-1/\mathrm{poly}(d)$,

$\displaystyle\left|\left\\{t_{1}\leq s\leq
t_{2}:y_{i_{s}}=j,i_{s}\in\mathcal{W}\right\\}\right|\leq
2\rho\cdot(t_{2}-t_{1}+1)\leq\frac{\delta}{32}\cdot\big{(}1-(1.05-\delta/4)^{\frac{1}{2}}\big{)}\cdot(t_{2}-t_{1}+1),$
(D.97)

where the second inequality follows from the condition on $\rho$ by Assumption
4.1. By Lemma D.2, we have that
$|1-y_{i_{s}}f(\mathbf{x}_{i_{s}};\mathbf{W}^{(s)})|\leq 2$ for $0\leq s\leq
T_{\max}^{j}$ and $y_{s}=j$. Therefore, we have that

$\displaystyle\sum_{\begin{subarray}{c}s=t_{1}\\\
y_{i_{s}}=j,i_{s}\in\mathcal{W}\end{subarray}}^{t_{2}}1-y_{i_{s}}f(\mathbf{x}_{i_{s}};\mathbf{W}^{(s)})\geq-\frac{\delta}{16}\cdot\big{(}1-(1.05-\delta/4)^{\frac{1}{2}}\big{)}\cdot(t_{2}-t_{1}+1).$
(D.98)

Combining (D.96) and (D.98), we can conclude that

$\displaystyle\sum_{\begin{subarray}{c}s=t_{1}\\\
y_{i_{s}}=j\end{subarray}}^{t_{2}}1-y_{i_{s}}f(\mathbf{x}_{i_{s}};\mathbf{W}^{(s)})\geq\frac{\delta}{16}\\!\cdot\\!\big{(}1-(1.05-\delta/4)^{\frac{1}{2}}\big{)}\\!\cdot\\!(t_{2}-t_{1}+1)-\frac{m{(1.05)^{\frac{1}{2}}}}{2\eta\|\mathbf{u}\|_{2}^{2}(1.05-\delta/4)^{\frac{1}{2}}}.$
(D.99)

This finishes the proof of the first part in Lemma D.3. Now we consider the
second part. For simplicity, we denote by
$\alpha=\|\mathbf{v}\|_{2}^{2}/\|\mathbf{u}\|_{2}^{2}$ and
$\tilde{\eta}=2\|\mathbf{u}\|_{2}^{2}/m$. Consider that for any $0\leq t\leq
T_{\max}^{j}$, $j\in\\{\pm 1\\}$, and $r\in\mathcal{V}_{j,+}^{(t)}$, due to
Lemma D.2, the $\mathbf{v}$-sign stability condition is true on
$[0,T_{\max}^{j}]$. In view of (D.5), this means that

$\displaystyle
1+\alpha\tilde{\eta}\cdot\big{(}1-y_{i_{s}}f(\mathbf{x}_{i_{s}};\mathbf{W}^{(s)})\big{)}>0,\quad\forall
0\leq s\leq T_{\max}^{j}\,\,\,\text{s.t.}\,\,\,y_{i_{s}}=j.$ (D.100)

Then for any $t_{1}\leq t\leq T_{\max}^{j}$, $t_{1}\leq s\leq t$, and
$r\in\mathcal{C}_{j,+}^{(t)}$, since $-2\leq
1-y_{i_{s}}f(\mathbf{x}_{i_{s}};\mathbf{W}^{(t)})\leq 2$ due to Lemma D.2, we
can lower bound the relative increment as

$\displaystyle\sum_{\begin{subarray}{c}s=t_{1}\\\
y_{i_{s}}=j\end{subarray}}^{t}$
$\displaystyle\log\Big{(}1+\alpha\tilde{\eta}\big{(}1-y_{i_{s}}f(\mathbf{x}_{i_{s}};\mathbf{W}^{(s)})\big{)}\Big{)}=\sum_{\begin{subarray}{c}s=t_{1}\\\
y_{i_{s}}=j\end{subarray}}^{t}\int_{0}^{\alpha}\frac{\tilde{\eta}\big{(}1-y_{i_{s}}f(\mathbf{x}_{i_{s}};\mathbf{W}^{(s)})\big{)}}{1+\tilde{\eta}z\big{(}1-y_{i_{s}}f(\mathbf{x}_{i_{s}};\mathbf{W}^{(s)})\big{)}}dz$
(D.101) $\displaystyle=\sum_{\begin{subarray}{c}s=t_{1}\\\
y_{i_{s}}=j\end{subarray}}^{t}\int_{0}^{\alpha}\frac{\tilde{\eta}\Big{(}\big{(}1-y_{i_{s}}f(\mathbf{x}_{i_{s}};\mathbf{W}^{(s)})\big{)}+2\Big{)}}{1+\tilde{\eta}z\big{(}1-y_{i_{s}}f(\mathbf{x}_{i_{s}};\mathbf{W}^{(s)})\big{)}}dz-\sum_{\begin{subarray}{c}s=t_{1}\\\
y_{i_{s}}=j\end{subarray}}^{t}\int_{0}^{\alpha}\frac{2\tilde{\eta}}{1+\tilde{\eta}z\big{(}1-y_{i_{s}}f(\mathbf{x}_{i_{s}};\mathbf{W}^{(s)})\big{)}}dz$
(D.102) $\displaystyle\geq\sum_{\begin{subarray}{c}s=t_{1}\\\
y_{i_{s}}=j\end{subarray}}^{t}\int_{0}^{\alpha}\frac{\tilde{\eta}\Big{(}\big{(}1-y_{i_{s}}f(\mathbf{x}_{i_{s}};\mathbf{W}^{(s)})\big{)}+2\Big{)}}{1+2\tilde{\eta}z}dz-\sum_{\begin{subarray}{c}s=t_{1}\\\
y_{i_{s}}=j\end{subarray}}^{t}\int_{0}^{\alpha}\frac{2\tilde{\eta}}{1-2\tilde{\eta}z}dz$
(D.103)
$\displaystyle\geq\int_{0}^{\alpha}\frac{\tilde{\eta}\Big{(}\sum_{s=t_{1},y_{i_{s}}=j}^{t}\big{(}1-y_{i_{s}}f(\mathbf{x}_{i_{s}};\mathbf{W}^{(t)})\big{)}+2N_{j}(t_{0},t)\Big{)}}{1+2\tilde{\eta}z}dz-\int_{0}^{\alpha}\frac{2\tilde{\eta}N_{j}(t_{1},t)}{1-2\tilde{\eta}z}dz,$
(D.104)

where for simplicity we denote $N_{j}(t_{1},t)=|\\{t_{1}\leq s\leq
t:y_{i_{s}}=j\\}|$. Now we can use Proposition D.3 to lower bound the right
hand side of (D.104), Denoting
$\epsilon=\delta\cdot(1-(1.05-\delta/4)^{\frac{1}{2}})/16$, we have that

$\displaystyle\sum_{\begin{subarray}{c}s=t_{1}\\\
y_{i_{s}}=j\end{subarray}}^{t}$
$\displaystyle\log\Big{\\{}1+\alpha\tilde{\eta}\big{(}1-y_{i_{s}}f(\mathbf{x}_{i_{s}};\mathbf{W}^{(s)})\big{)}\Big{\\}}$
(D.105)
$\displaystyle\geq\int_{0}^{\alpha}\frac{\tilde{\eta}\Big{(}\epsilon(t-t_{1}+1)-\Delta+2N_{j}(t_{1},t)\Big{)}}{1+2\tilde{\eta}z}dz-\int_{0}^{\alpha}\frac{2\tilde{\eta}N_{j}(t_{1},t)}{1-2\tilde{\eta}}dz$
(D.106)
$\displaystyle\geq\bigg{(}\frac{\epsilon}{2}(t-t_{1}+1)-\frac{\Delta}{2}+N_{j}(t_{1},t)\bigg{)}\cdot\log(1+2\alpha\tilde{\eta})+N_{j}(t_{1},t)\cdot\log(1-2\alpha\tilde{\eta})$
(D.107)
$\displaystyle\geq\bigg{(}\frac{\epsilon}{2}(t-t_{1}+1)-\frac{\Delta}{2}\bigg{)}\cdot\log(1+2\alpha\tilde{\eta})+N_{j}(t_{1},t)\cdot\log\big{\\{}(1+2\alpha\tilde{\eta})\cdot(1-2\alpha\tilde{\eta})\\},$
(D.108)

where $\Delta$ is defined in Lemma D.3. Moreover since for our choice of
$\alpha\tilde{\eta}\ll 1$ in Assumption 4.1,

$\displaystyle\log(1+2\alpha\tilde{\eta})\geq\alpha\tilde{\eta},\quad\log\big{\\{}(1+2\alpha\tilde{\eta})\cdot(1-2\alpha\tilde{\eta})\big{\\}}=\log\big{\\{}1-4\alpha^{2}\tilde{\eta}^{2}\big{\\}}\geq-2\alpha^{2}\tilde{\eta}^{2},$
(D.109)

and using the fact that with probability at least $1-1/\mathrm{poly}(d)$ it
holds that $N_{j}(t_{1},t)\leq(t-t_{1}+1)/2$, we finally have that

$\displaystyle\sum_{\begin{subarray}{c}s=t_{1}\\\
y_{i_{s}}=j\end{subarray}}^{t}\log\Big{\\{}1+\alpha\tilde{\eta}\big{(}1-y_{i_{s}}f(\mathbf{x}_{i_{s}};\mathbf{W}^{(s)})\big{)}\Big{\\}}$
$\displaystyle\geq\frac{\alpha\tilde{\eta}}{2}\\!\cdot\\!(\epsilon-2\alpha\tilde{\eta})\\!\cdot\\!(t_{1}-t_{1}+1)-\Delta\cdot\log(1+2\alpha\tilde{\eta})$
(D.110)
$\displaystyle\geq\frac{1}{4}\alpha\tilde{\eta}\cdot\epsilon\cdot(t_{1}-t_{1}+1)-2\alpha\tilde{\eta}\cdot\Delta.$
(D.111)

Finally, using (D.5) again, we can lower bound our target as

$\displaystyle\langle{\mathbf{w}_{j,r}^{(t+1)}},{j\mathbf{v}}\rangle$
$\displaystyle=\langle{\mathbf{w}_{j,r}^{(t_{1})}},{j\mathbf{v}}\rangle\cdot\prod_{\begin{subarray}{c}s=t_{1}\\\
y_{i_{s}}=j\end{subarray}}^{t}\Big{(}1+\alpha\tilde{\eta}\big{(}1-y_{i_{s}}f(\mathbf{x}_{i_{s}};\mathbf{W}^{(s)})\big{)}\Big{)}$
(D.112)
$\displaystyle=\langle{\mathbf{w}_{j,r}^{(t_{1})}},{j\mathbf{v}}\rangle\cdot\exp\left\\{\sum_{\begin{subarray}{c}s=t_{1}\\\
y_{i_{s}}=j\end{subarray}}^{t}\log\Big{\\{}1+\alpha\tilde{\eta}\big{(}1-y_{i_{s}}f(\mathbf{x}_{i_{s}};\mathbf{W}^{(s)})\big{)}\Big{\\}}\right\\}$
(D.113)
$\displaystyle\geq\langle{\mathbf{w}_{j,r}^{(t_{1})}},{j\mathbf{v}}\rangle\cdot\exp\left\\{\frac{1}{4}\alpha\tilde{\eta}\cdot\epsilon\cdot(t_{1}-t_{1}+1)-2\alpha\tilde{\eta}\cdot\Delta\right\\}.$
(D.114)

Plugging in the definition of $\epsilon$, $\Delta$, $\alpha$, and
$\tilde{\eta}$, we can arrive at

$\displaystyle\langle{\mathbf{w}_{j,r}^{(t+1)}},{j\mathbf{v}}\rangle\geq\langle{\mathbf{w}_{j,r}^{(t_{1})}},{j\mathbf{v}}\rangle\cdot\exp\left\\{\frac{\eta\|\mathbf{v}\|_{2}^{2}}{32m}\\!\cdot\\!\big{(}\delta-\delta(1.05-\delta/4)^{\frac{1}{2}}\big{)}\\!\cdot\\!(t-t_{1}+1)-\frac{\|\mathbf{v}\|_{2}^{2}{(1.05)^{\frac{1}{2}}}}{\|\mathbf{u}\|_{2}^{2}(1.05-\delta/4)^{\frac{1}{2}}}\right\\}.$
(D.115)

This finishes the proof of Lemma D.3. ∎

###  D.6 Proof of Technical Results

####  D.6.1 Proof of Proposition D.1

###### Proof of Proposition D.1.

From Equation (D.4), for $r\in\mathcal{U}_{j,+}$ and
$t^{\prime}\in(t_{j}(s),t_{j}(s+1)]$, we can infer that

$\displaystyle\langle{\mathbf{w}_{j,r}^{(t^{\prime})}},{j\mathbf{u}}\rangle$
$\displaystyle=\langle{\mathbf{w}_{j,r}^{(t_{j}(s))}},{j\mathbf{u}}\rangle+\sum_{t=t_{j}(s)}^{t^{\prime}-1}\frac{\eta\|\mathbf{u}\|_{2}^{2}}{m}\cdot\big{(}1-\tilde{f}_{t}\big{)}\cdot\sigma^{\prime}\bigl{(}\langle{\mathbf{w}_{j,r}^{(t)}},{j\mathbf{u}}\rangle\cdot
jy_{i_{t}}\bigr{)}\cdot\mathbf{1}\\{i_{t}\in\mathcal{W}\\}.$ (D.116)

The definition of $t_{j}(s)$ implies that for $t\in(t_{j}(s),t_{j}(s+1))$,
$y_{i_{t}}j=-1$. On the other hand $y_{i_{t_{j}(s)}}j=1$, hence we obtain that

$\displaystyle\langle{\mathbf{w}_{j,r}^{(t^{\prime})}},{j\mathbf{u}}\rangle$
$\displaystyle=\langle{\mathbf{w}_{j,r}^{(t_{j}(s))}},{j\mathbf{u}}\rangle+\frac{2\eta\|\mathbf{u}\|_{2}^{2}}{m}\cdot\big{(}1-\tilde{f}_{t_{j}(s)}\big{)}\cdot\langle{\mathbf{w}_{j,r}^{(t)}},{j\mathbf{u}}\rangle\cdot\mathbf{1}\\{i_{t_{j}(s)}\in\mathcal{W}\\}.$
(D.117)

Since the sign stability holds, this multiplication by a non-negative factor
does not change the sign of the inner products. Therefore we have that

$\displaystyle\langle{\mathbf{w}_{j,r}^{(t_{j}(s+1))}},{j\mathbf{u}}\rangle$
$\displaystyle=\langle{\mathbf{w}_{j,r}^{(t_{j}(s+1)-1)}},{j\mathbf{u}}\rangle=\cdots=\langle{\mathbf{w}_{j,r}^{(t_{j}(s)+1)}},{j\mathbf{u}}\rangle$
(D.118)
$\displaystyle=\langle{\mathbf{w}_{j,r}^{(t_{j}(s))}},{j\mathbf{u}}\rangle\cdot\big{(}1+\tilde{\eta}\cdot(1-\tilde{f}_{t_{j}(s)})\big{)}.$
(D.119)

which concludes our result for
$\langle{\mathbf{w}_{j,r}^{(t)}},{j\mathbf{u}}\rangle,\;r\in\mathcal{U}_{j,+}$.
Other result can be proved analogously and are omitted here. ∎

####  D.6.2 Proof of Lemma B.5 for Multiple Data Setting

###### Proof of Lemma B.5 (multiple data setting).

In the multiple data setting, the (positive) inner products only changes at
the steps where the corresponding data label aligns with the directions of the
neurons (i.e., $j=\pm 1$). Define

$\displaystyle\beta^{*,(t_{1})}_{\mathbf{u},j}$
$\displaystyle=\frac{\max_{r\in[m]}\sigma(\langle{\mathbf{w}_{j,r}^{(t_{1})}},{j\mathbf{u}}\rangle)}{\sum_{r\in[m]}\sigma(\langle{\mathbf{w}_{j,r}^{(t_{1})}},{j\mathbf{u}}\rangle)}.$
(D.120)

Again, the local sign stability assumption ensures that each inner product
grows proportionally and the superscript $(t)$ in the neuron index sets can be
dropped, with

$\displaystyle\frac{1}{m}\sum_{r\in[m]}\sigma\big{(}\langle{\mathbf{w}_{j,r}^{(t)}},{j\mathbf{u}}\rangle\big{)}$
$\displaystyle=\frac{1}{m}\sum_{r\in\mathcal{U}_{j,+}}\sigma\big{(}\langle{\mathbf{w}_{j,r}^{(t_{1})}},{j\mathbf{u}}\rangle\big{)}\cdot\prod_{\begin{subarray}{c}t^{\prime}\in[t_{1},t-1]:\\\
y_{i_{t}}=j,\;i_{t}\notin\mathcal{W}\end{subarray}}\left(1+\frac{2\eta\|\mathbf{u}\|_{2}^{2}}{m}\cdot\big{(}1-y_{i_{t^{\prime}}}f(\mathbf{x}_{i_{t^{\prime}}};\mathbf{W}^{(t^{\prime})})\big{)}\right)^{2}$
(D.121)
$\displaystyle=\frac{\max_{r\in[m]}\sigma\big{(}\langle{\mathbf{w}_{j,r}^{(t_{1})}},{j\mathbf{u}}\rangle\big{)}}{m\beta^{*,(t_{1})}_{\mathbf{u},j}}\cdot\prod_{\begin{subarray}{c}t^{\prime}\in[t_{1},t-1]:\\\
y_{i_{t^{\prime}}}=j,\;i_{t}\notin\mathcal{W}\end{subarray}}\left(1+\frac{2\eta\|\mathbf{u}\|_{2}^{2}}{m}\cdot\big{(}1-y_{i_{t^{\prime}}}f(\mathbf{x}_{i_{t^{\prime}}};\mathbf{W}^{(t^{\prime})})\big{)}\right)^{2}$
(D.122)
$\displaystyle=\frac{\sigma\big{(}\max_{r\in[m]}\langle{\mathbf{w}_{j,r}^{(t)}},{j\mathbf{u}}\rangle\big{)}}{m\beta^{*,(t_{1})}_{\mathbf{u},j}}$
(D.123)

Here the first and the third equality is true because Equation (B.2) implies
that all the positive $\langle{\mathbf{w}_{y,r}^{(t)}},{y\mathbf{u}}\rangle$
iterates by sequentially multiplying the same factor

$\displaystyle
1+\frac{2\eta\|\mathbf{u}\|_{2}^{2}}{m}\cdot\big{(}1-yf(\mathbf{x};\mathbf{W}^{(t^{\prime})})\big{)}.$
(D.124)

The second equality comes from the definition of
$\beta^{*,(t_{1})}_{\mathbf{u}}$ in Lemma B.5.

Therefore,
$m^{-1}\cdot\sum_{r\in[m]}\sigma(\langle{\mathbf{w}_{j,r}^{(t)}},{j\mathbf{u}}\rangle)>c$
implies that
$\sigma(\max_{r\in[m]}\langle{\mathbf{w}_{y,r}^{(t)}},{y\mathbf{u}}\rangle)>\beta^{*,(t_{1})}_{\mathbf{u},j}mc$
and the desired lower bound follows. The upper bound can be proved
analogously. ∎

####  D.6.3 Proof of Proposition D.4

###### Proof of Proposition D.4.

We prove the result by induction. For the step $t=t_{1}$, the result holds
trivially. Suppose that this result holds for each step $t_{1},\cdots,t$, then
by (D.7), we have that

$\displaystyle\langle\mathbf{w}_{j,r}^{(t+1)},\bm{\xi}_{i}\rangle$
$\displaystyle=\langle\mathbf{w}_{j,r}^{(t_{1})},\bm{\xi}_{i}\rangle+\sum_{s=t_{1}}^{t}\frac{\eta\cdot
jy_{i_{s}}}{m}\cdot\big{(}1-y_{i_{s}}f(\mathbf{x}_{i_{s}};\mathbf{W}^{(s)})\big{)}\cdot\left(\sigma^{\prime}(\langle\mathbf{w}_{j,r}^{(s)}\cdot\bm{\xi}_{i_{s}}\rangle)\cdot\langle\bm{\xi}_{i_{s}},\bm{\xi}_{i}\rangle\right.$
(D.125)
$\displaystyle\qquad+\left.\sigma^{\prime}(\langle\mathbf{w}_{j,r}^{(s)}\cdot\widetilde{\bm{\xi}}_{i_{s}}\rangle)\cdot\langle\widetilde{\bm{\xi}}_{i_{s}},\bm{\xi}_{i}\rangle\cdot\mathbf{1}\\{i_{s}\in\mathcal{W}\\}\right)$
(D.126)
$\displaystyle=\langle\mathbf{w}_{j,r}^{(t_{1})},\bm{\xi}_{i}\rangle+\sum_{\begin{subarray}{c}s=t_{1}\\\
i_{s}=i\end{subarray}}^{t}\frac{\eta\|\bm{\xi}_{i}\|_{2}^{2}\cdot
jy_{i_{s}}}{m}\cdot\big{(}1-y_{i}f(\mathbf{x}_{i};\mathbf{W}^{(s)})\big{)}\cdot\sigma^{\prime}(\langle\mathbf{w}_{j,r}^{(s)}\cdot\bm{\xi}_{i}\rangle)$
(D.127) $\displaystyle\qquad+\sum_{\begin{subarray}{c}s=t_{1}\\\ i_{s}\neq
i\end{subarray}}^{t}\frac{\eta\|\bm{\xi}_{i}\|_{2}^{2}\cdot
jy_{i_{s}}}{m}\cdot\big{(}1-y_{i_{s}}f(\mathbf{x}_{i_{s}};\mathbf{W}^{(s)})\big{)}\cdot\left(\sigma^{\prime}(\langle\mathbf{w}_{j,r}^{(s)}\cdot\bm{\xi}_{i_{s}}\rangle)\cdot\frac{\langle\bm{\xi}_{i_{s}},\bm{\xi}_{i}\rangle}{\|\bm{\xi}_{i}\|_{2}^{2}}\right.$
(D.128)
$\displaystyle\qquad\qquad+\left.\sigma^{\prime}(\langle\mathbf{w}_{j,r}^{(s)}\cdot\widetilde{\bm{\xi}}_{i_{s}}\rangle)\cdot\frac{\langle\widetilde{\bm{\xi}}_{i_{s}},\bm{\xi}_{i}\rangle}{\|\bm{\xi}_{i}\|_{2}^{2}}\cdot\mathbf{1}\\{i_{s}\in\mathcal{W}\\}\right)$
(D.129)

Taking absolute value, we have that

$\displaystyle\left|\langle\mathbf{w}_{j,r}^{(t+1)},\bm{\xi}_{i}\rangle\right|$
$\displaystyle\leq\left|\langle\mathbf{w}_{j,r}^{(t_{1})},\bm{\xi}_{i}\rangle\right|+\left|\sum_{\begin{subarray}{c}s=t_{1}\\\
i_{s}=i\end{subarray}}^{t}\frac{\eta\|\bm{\xi}_{i}\|_{2}^{2}\cdot
jy_{i_{s}}}{m}\cdot\big{(}1-y_{i}f(\mathbf{x}_{i};\mathbf{W}^{(s)})\big{)}\cdot\sigma^{\prime}(\langle\mathbf{w}_{j,r}^{(s)}\cdot\bm{\xi}_{i}\rangle)\right|$
(D.130) $\displaystyle\qquad+\left|\sum_{\begin{subarray}{c}s=t_{1}\\\
i_{s}\neq i\end{subarray}}^{t}\frac{\eta\|\bm{\xi}_{i}\|_{2}^{2}\cdot
jy_{i_{s}}}{m}\cdot\big{(}1-y_{i_{s}}f(\mathbf{x}_{i_{s}};\mathbf{W}^{(s)})\big{)}\right.$
(D.131)
$\displaystyle\qquad\qquad\left.\cdot\left(\sigma^{\prime}(\langle\mathbf{w}_{j,r}^{(s)}\cdot\bm{\xi}_{i_{s}}\rangle)\cdot\frac{\langle\bm{\xi}_{i_{s}},\bm{\xi}_{i}\rangle}{\|\bm{\xi}_{i}\|_{2}^{2}}+\sigma^{\prime}(\langle\mathbf{w}_{j,r}^{(s)}\cdot\widetilde{\bm{\xi}}_{i_{s}}\rangle)\cdot\frac{\langle\widetilde{\bm{\xi}}_{i_{s}},\bm{\xi}_{i}\rangle}{\|\bm{\xi}_{i}\|_{2}^{2}}\cdot\mathbf{1}\\{i_{s}\in\mathcal{W}\\}\right)\right|$
(D.132)

Applying the definition of $\Upsilon^{(s)}$, we further obtain that

$\displaystyle\left|\langle\mathbf{w}_{j,r}^{(t+1)},\bm{\xi}_{i}\rangle\right|$
$\displaystyle\leq\Upsilon^{(t_{1})}+\sum_{\begin{subarray}{c}s=t_{1}\\\
i_{s}=i\end{subarray}}^{t}\frac{2\eta\|\bm{\xi}_{i}\|_{2}^{2}}{m}\cdot\big{|}1-y_{i}f(\mathbf{x}_{i};\mathbf{W}^{(s)})\big{|}\cdot\Upsilon^{(s)}$
(D.133) $\displaystyle\qquad+\sum_{\begin{subarray}{c}s=t_{1}\\\ i_{s}\neq
i\end{subarray}}^{t}\frac{2\eta\|\bm{\xi}_{i}\|_{2}^{2}}{m}\cdot\big{|}1-y_{i_{s}}f(\mathbf{x}_{i_{s}};\mathbf{W}^{(s)})\big{|}\cdot\Upsilon^{(s)}\cdot\left(\frac{|\langle\bm{\xi}_{i_{s}},\bm{\xi}_{i}\rangle|}{\|\bm{\xi}_{i}\|_{2}^{2}}+\frac{|\langle\widetilde{\bm{\xi}}_{i_{s}},\bm{\xi}_{i}\rangle|}{\|\bm{\xi}_{i}\|_{2}^{2}}\right).$
(D.134)

Now using Lemma D.2, for $s\leq\min_{j\in\\{\pm 1\\}}\\{T_{\max}^{j}\\}$, we
have that $|1-y_{i_{s}}f(\mathbf{x}_{i_{s}};\mathbf{W}^{(s)})|\leq 2$. Also,
by Lemma A.3, it holds that$\|\bm{\xi}_{i}\|_{2}^{2}\leq 3\sigma_{p}^{2}d/2$
and
$|\langle\bm{\xi},\bm{\xi}^{\prime}\rangle|/\|\bm{\xi}\|_{2}^{2}\leq\widetilde{\mathcal{O}}(d^{-1/2})$.
Thus we can further upper bound (D.134) as

$\displaystyle\max_{i\in[n]}\left|\langle\mathbf{w}_{j,r}^{(t+1)},\bm{\xi}_{i}\rangle\right|$
$\displaystyle\leq\Upsilon^{(t_{1})}+\frac{6\eta\sigma_{p}^{2}d}{m}\cdot\left(\sum_{\begin{subarray}{c}s=t_{1}\\\
i_{s}=i\end{subarray}}^{t}\Upsilon^{(s)}+\widetilde{\mathcal{O}}(d^{-1/2})\cdot\sum_{\begin{subarray}{c}s=t_{1}\\\
i_{s}\neq i\end{subarray}}^{t}\Upsilon^{(s)}\right)$ (D.135)
$\displaystyle=\Upsilon^{(t_{1})}+\frac{6\eta\sigma_{p}^{2}d}{m}\cdot\left(\sum_{\begin{subarray}{c}s=t_{1}\\\
i_{s}=i\end{subarray}}^{t}\Upsilon^{(t_{1})}+\widetilde{\mathcal{O}}(d^{-1/2})\cdot\sum_{\begin{subarray}{c}s=t_{1}\\\
i_{s}\neq i\end{subarray}}^{t}\Upsilon^{(t_{1})}\right)$ (D.136)
$\displaystyle\qquad+\frac{6\eta\sigma_{p}^{2}d}{m}\cdot\left(\sum_{\begin{subarray}{c}s=t_{1}\\\
i_{s}=i\end{subarray}}^{t}\big{(}\Upsilon^{(t_{1})}-\Upsilon^{(s)}\big{)}+\widetilde{\mathcal{O}}(d^{-1/2})\cdot\sum_{\begin{subarray}{c}s=t_{1}\\\
i_{s}\neq
i\end{subarray}}^{t}\big{(}\Upsilon^{(t_{1})}-\Upsilon^{(s)}\big{)}\right).$
(D.137)

By our induction, we have that
$\Upsilon^{(s)}-\Upsilon^{(t_{1})}\leq\Upsilon^{(t_{1})}\cdot\epsilon$, for
which we can further bound (D.135) as

$\displaystyle\max_{i\in[n]}\left|\langle\mathbf{w}_{j,r}^{(t+1)},\bm{\xi}_{i}\rangle\right|$
$\displaystyle\leq\Upsilon^{(t_{1})}\cdot\left[1+\frac{6\eta\sigma_{p}^{2}d}{m}\cdot(1+\epsilon)\cdot\left(\sum_{\begin{subarray}{c}s=t_{1}\\\
i_{s}=i\end{subarray}}^{t}1+\widetilde{\mathcal{O}}(d^{-1/2})\cdot\sum_{\begin{subarray}{c}s=t_{1}\\\
i_{s}\neq i\end{subarray}}^{t}1\right)\right]$ (D.138)
$\displaystyle\leq\Upsilon^{(t_{1})}\cdot\left[1+\frac{6\eta\sigma_{p}^{2}d}{m}\cdot(1+\epsilon)\cdot\left(\frac{2(t-t_{1}+1)}{n}+\widetilde{\mathcal{O}}(d^{-1/2})\cdot(t-t_{1}+1)\right)\right]$
(D.139)
$\displaystyle\leq\Upsilon^{(t_{1})}\cdot\left[1+\frac{18\eta\sigma_{p}^{2}d}{mn}\cdot(1+\epsilon)\cdot(t-t_{1}+1)\right],$
(D.140)

where in the first inequality we have utilized the fact that $|\\{t_{1}\leq
s\leq t:i_{s}=i\\}|\leq 2(t-t_{1}+1)/n$, and in the last inequality we apply
the condition that $d=\widetilde{\Omega}(n^{2})$ by Assumption 4.1. Therefore,
when $t\leq t_{1}+\widetilde{T}_{(\bm{\xi})}-1$ with
$\widetilde{T}_{(\bm{\xi})}=\widetilde{\Theta}(mn\cdot\eta^{-1}\cdot\epsilon\cdot(1+\epsilon)^{-1}\cdot(\sigma_{p}^{2}d)^{-1})$,
it holds that

$\displaystyle\max_{i\in[n]}\left|\langle\mathbf{w}_{j,r}^{(t+1)},\bm{\xi}_{i}\rangle\right|$
$\displaystyle\leq\Upsilon^{(t_{1})}\cdot(1+\epsilon).$ (D.141)

By using the same argument as proving (D.141), we can also show that for
$t\leq t_{1}+\widetilde{T}_{(\bm{\xi})}-1$

$\displaystyle\max_{i\in\mathcal{W}}\left|\langle\mathbf{w}_{j,r}^{(t+1)},\widetilde{\bm{\xi}}_{i}\rangle\right|\leq\Upsilon^{(t_{1})}\cdot(1+\epsilon).$
(D.142)

By combining (D.141) and (D.142), we can arrive at

$\displaystyle\Upsilon^{(t+1)}=\max_{j\in\\{\pm
1\\},r\in[m]}\left\\{\max_{i\in[n]}\left|\langle\mathbf{w}_{j,r}^{(t+1)},\bm{\xi}_{i}\rangle\right|,\max_{i\in\mathcal{W}}\left|\langle\mathbf{w}_{j,r}^{(t+1)},\widetilde{\bm{\xi}}_{i}\rangle\right|\right\\}\leq\Upsilon^{(t_{1})}\cdot(1+\epsilon).$
(D.143)

Thus we have proved our induction statement for step $t+1$. Repeating the
induction completes the proof of Proposition D.4. ∎

####  D.6.4 Proof of Proposition D.5

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

We expand $\tilde{f}_{t_{j}(\bar{S}_{j,k})}$ as follows.

$\displaystyle\tilde{f}_{t_{j}(\bar{S}_{j,k})}$
$\displaystyle\leq\frac{1}{m}\sum_{r\in[m]}\sigma\big{(}\langle{\mathbf{w}_{j,r}^{(t_{j}(\bar{S}_{j,k}-1))}},{j\mathbf{u}}\rangle\big{)}\cdot\left(1+\tilde{\eta}\big{(}1-\tilde{f}_{t_{j}(\bar{S}_{j,k}-1)}\big{)}\right)^{2}$
(D.144)
$\displaystyle\qquad+\frac{1}{m}\sum_{r\in[m]}\sigma\big{(}\langle{\mathbf{w}_{j,r}^{(t_{j}(\bar{S}_{j,k}-1))}},{j\mathbf{v}}\rangle\big{)}\cdot\left(1+\alpha\tilde{\eta}\big{(}1-\tilde{f}_{t_{j}(\bar{S}_{j,k}-1)}\big{)}\right)^{2}$
(D.145)
$\displaystyle\qquad-\frac{1}{m}\sum_{r\in[m]}\sigma\big{(}-\langle{\mathbf{w}_{-j,r}^{(t_{j}(\bar{S}_{j,k}-1))}},{-j\mathbf{u}}\rangle\big{)}\cdot\left(1-\tilde{\eta}\big{(}1-\tilde{f}_{t_{j}(\bar{S}_{j,k}-1)}\big{)}\right)^{2}$
(D.146)
$\displaystyle\qquad-\frac{1}{m}\sum_{r\in[m]}\sigma\big{(}-\langle{\mathbf{w}_{j,r}^{(t_{j}(\bar{S}_{j,k}-1))}},{-j\mathbf{v}}\rangle\big{)}\cdot\left(1-\alpha\tilde{\eta}\big{(}1-\tilde{f}_{t_{j}(\bar{S}_{j,k}-1)}\big{)}\right)^{2}$
(D.147)
$\displaystyle\qquad+\left|\frac{1}{m}\sum_{r\in[m]}\sigma\big{(}\langle{\mathbf{w}_{j,r}^{(t_{j}(\bar{S}_{j,k}))}},{\bm{\xi}_{i_{t_{j}(\bar{S}_{j,k})}}}\rangle\big{)}-\frac{1}{m}\sum_{r\in[m]}\sigma\big{(}\langle{\mathbf{w}_{-j,r}^{(t_{j}(\bar{S}_{j,k}))}},{\bm{\xi}_{i_{t_{j}(\bar{S}_{j,k})}}}\rangle\big{)}\right|$
(D.148)
$\displaystyle\leq\frac{1}{m}\sum_{r\in[m]}\left(\sigma\big{(}\langle{\mathbf{w}_{j,r}^{(t_{j}(\bar{S}_{j,k}-1))}},{j\mathbf{u}}\rangle\big{)}+\sigma\big{(}\langle{\mathbf{w}_{j,r}^{(t_{j}(\bar{S}_{j,k}-1))}},{j\mathbf{v}}\rangle\big{)}\right.$
(D.149)
$\displaystyle\qquad\qquad\left.-\sigma\big{(}-\langle{\mathbf{w}_{-j,r}^{(t_{j}(\bar{S}_{j,k}-1))}},{-j\mathbf{u}}\rangle\big{)}-\sigma\big{(}-\langle{\mathbf{w}_{j,r}^{(t_{j}(\bar{S}_{j,k}-1))}},{-j\mathbf{v}}\rangle\big{)}\right)\cdot\left(1+\tilde{\eta}\big{(}1-\tilde{f}_{t_{j}(\bar{S}_{j,k}-1)}\big{)}\right)^{2}$
(D.150)
$\displaystyle\qquad+\frac{1}{m}\sum_{r\in[m]}\left(\sigma\big{(}-\langle{\mathbf{w}_{-j,r}^{(t_{j}(\bar{S}_{j,k}-1))}},{-j\mathbf{u}}\rangle\big{)}+\sigma\big{(}-\langle{\mathbf{w}_{j,r}^{(t_{j}(\bar{S}_{j,k}-1))}},{-j\mathbf{v}}\rangle\big{)}\right)\cdot\left(2\tilde{\eta}\big{(}1-\tilde{f}_{t_{j}(\bar{S}_{j,k}-1)}\big{)}\right)$
(D.151) $\displaystyle\qquad\qquad+{\Upsilon^{(t_{j}(\bar{S}_{j,k}))}}^{2}$
(D.152)
$\displaystyle\leq\tilde{f}_{t_{j}(\bar{S}_{j,k}-1)}\cdot\left(1+\tilde{\eta}\big{(}1-\tilde{f}_{t_{j}(\bar{S}_{j,k}-1)}\big{)}\right)^{2}+2E_{t_{j}(\bar{S}_{j,k}-1)}+{\Upsilon^{(t_{j}(\bar{S}_{j,k}))}}^{2}.$
(D.153)

By Assumption B.2 we know that $\tilde{f}_{t_{j}(\bar{S}_{j,k})}>1+\delta$.
From the discussion in the proof of Lemma B.9, we know that once

$\displaystyle
2E_{t_{j}(\bar{S}_{j,k}-1)}+{\Upsilon^{(t_{j}(\bar{S}_{j,k}))}}^{2}\leq\delta,$
(D.154)

we have that

$\displaystyle\tilde{f}_{t_{j}(\bar{S}_{j,k}-1)}\geq\frac{\tilde{\eta}+2-\sqrt{\tilde{\eta}^{2}+4\tilde{\eta}}}{2\tilde{\eta}},$
(D.155)

and that

$\displaystyle\tilde{f}_{t_{j}(\bar{S}_{j,k})}$
$\displaystyle\leq\left(1+\tilde{\eta}(1-\tilde{f}_{t_{j}(\bar{S}_{j,k}-1)})\right)^{2}+E_{t_{j}(\bar{S}_{j,k}-1)}+{\Upsilon^{(t_{j}(\bar{S}_{j,k}))}}^{2}$
(D.156)
$\displaystyle\leq\bigl{(}\tilde{\eta}/2+\sqrt{\tilde{\eta}^{2}/4+\tilde{\eta}}\bigr{)}^{2}+E_{t_{j}(\bar{S}_{j,k}-1)}+{\Upsilon^{(t_{j}(\bar{S}_{j,k}))}}^{2}.$
(D.157)

This finishes the proof of Proposition D.5 ∎

##  Appendix E Multiple Training Data Case: Small Learning Rate Regime

This section focuses on the multiple training data setup with a small learning
rate.

Recall that $\mathcal{W}$ is the index set of training data points which lack
the strong feature patch. By (2.5), the CNN weights are updated according to

$\displaystyle\mathbf{w}_{j,r}^{(t+1)}$
$\displaystyle=\mathbf{w}_{j,r}^{(t)}-\frac{j\eta}{m}\cdot\big{(}f(\mathbf{x}_{i_{t}};\mathbf{W}^{(t)})-y_{i_{t}}\big{)}\cdot\left(\sigma^{\prime}(\langle\mathbf{w}_{j,r}^{(t)},y_{i_{t}}\mathbf{u}\rangle)\cdot
y_{i_{t}}\mathbf{u}\cdot\mathbf{1}\\{i_{t}\notin\mathcal{W}\\}\right.$ (E.1)
$\displaystyle\qquad+\sigma^{\prime}(\langle\mathbf{w}_{j,r}^{(t)},y_{i_{t}}\mathbf{v}\rangle)\cdot
y_{i_{t}}\mathbf{v}+\sigma^{\prime}(\langle\mathbf{w}_{j,r}^{(t)}\cdot\bm{\xi}_{i_{t}}\rangle)\cdot\bm{\xi}_{i_{t}}$
(E.2)
$\displaystyle\qquad+\left.\sigma^{\prime}(\langle\mathbf{w}_{j,r}^{(t)}\cdot\widetilde{\bm{\xi}}_{i_{t}}\rangle)\cdot\widetilde{\bm{\xi}}_{i_{t}},\cdot\mathbf{1}\\{i_{t}\in\mathcal{W}\\}\right).$
(E.3)

Subsequently, by (E.3) the update formulas of those inner products of
interests are given by

$\displaystyle\langle\mathbf{w}_{j,r}^{(t+1)},j\mathbf{u}\rangle$
$\displaystyle=\langle\mathbf{w}_{j,r}^{(t)},j\mathbf{u}\rangle+\frac{\eta\|\mathbf{u}\|_{2}^{2}}{m}\cdot\big{(}1-y_{i_{t}}f(\mathbf{x}_{i_{t}};\mathbf{W}^{(t)})\big{)}\cdot\sigma^{\prime}(\langle\mathbf{w}_{j,r}^{(t)},j\mathbf{u}\rangle
jy_{i_{t}})\cdot\mathbf{1}\\{i_{t}\notin\mathcal{W}\\},$ (E.4)
$\displaystyle\langle\mathbf{w}_{j,r}^{(t+1)},j\mathbf{v}\rangle$
$\displaystyle=\langle\mathbf{w}_{j,r}^{(t)},j\mathbf{v}\rangle+\frac{\eta\|\mathbf{v}\|_{2}^{2}}{m}\cdot\big{(}1-y_{i_{t}}f(\mathbf{x}_{i_{t}};\mathbf{W}^{(t)})\big{)}\cdot\sigma^{\prime}(\langle\mathbf{w}_{j,r}^{(t)}\cdot
j\mathbf{v}\rangle jy_{i_{t}}),$ (E.5)

and

$\displaystyle\langle\mathbf{w}_{j,r}^{(t+1)},\bm{\xi}_{i}\rangle$
$\displaystyle=\langle\mathbf{w}_{j,r}^{(t)},\bm{\xi}_{i}\rangle+\frac{\eta\cdot
jy_{i_{t}}}{m}\cdot\big{(}1-y_{i_{t}}f(\mathbf{x}_{i_{t}};\mathbf{W}^{(t)})\big{)}\cdot\left(\sigma^{\prime}(\langle\mathbf{w}_{j,r}^{(t)}\cdot\bm{\xi}_{i_{t}}\rangle)\cdot\langle\bm{\xi}_{i_{t}},\bm{\xi}_{i}\rangle\right.$
(E.6)
$\displaystyle\qquad+\left.\sigma^{\prime}(\langle\mathbf{w}_{j,r}^{(t)}\cdot\widetilde{\bm{\xi}}_{i_{t}}\rangle)\cdot\langle\widetilde{\bm{\xi}}_{i_{t}},\bm{\xi}_{i}\rangle\cdot\mathbf{1}\\{i_{t}\in\mathcal{W}\\}\right).$
(E.7)
$\displaystyle\langle\mathbf{w}_{j,r}^{(t+1)},\widetilde{\bm{\xi}}_{i}\rangle$
$\displaystyle=\langle\mathbf{w}_{j,r}^{(t)},\widetilde{\bm{\xi}}_{i}\rangle+\frac{\eta\cdot
jy_{i_{t}}}{m}\cdot\big{(}1-y_{i_{t}}f(\mathbf{x}_{i_{t}};\mathbf{W}^{(t)})\big{)}\cdot\left(\sigma^{\prime}(\langle\mathbf{w}_{j,r}^{(t)},\bm{\xi}_{i_{t}}\rangle)\cdot\langle\bm{\xi}_{i_{t}},\widetilde{\bm{\xi}}_{i}\rangle\right.$
(E.8)
$\displaystyle\qquad+\left.\sigma^{\prime}(\langle\mathbf{w}_{j,r}^{(t)},\widetilde{\bm{\xi}}_{i_{t}}\rangle)\cdot\langle\widetilde{\bm{\xi}}_{i_{t}},\widetilde{\bm{\xi}}_{i}\rangle\cdot\mathbf{1}\\{i_{t}\in\mathcal{W}\\}\right),\quad
i\in\mathcal{W}.$ (E.9)

For convenience, we also write
$\ell^{(t)}_{i}=f(\mathbf{x}_{i};\mathbf{W}^{(t)})-y_{i}$ as the fitting
residual.

The result of this section relies on the following conditions on the data
model and the initialization.

######  Assumption E.1 (Conditions on hyperparameters).

Suppose that the following holds. For some $\epsilon\in(0,1),$

  1. 1.

The weight initialization scale
$\sigma_{0}=\widetilde{\Theta}(\|\mathbf{u}\|_{2}^{-1})$;

  2. 2.

Strong signal strength
$\|\mathbf{u}\|_{2}>\widetilde{\Omega}(m/\sqrt{n\epsilon})\cdot\sigma_{p}\sqrt{d}$
and weak signal strength
$\sigma_{p}\sqrt{d}\geq\widetilde{\Omega}\left(m/\sqrt{n\epsilon}\right)\cdot\|\mathbf{v}\|_{2}$;

  3. 3.

The dimension $d$ satisfies $d=\Omega(\mathrm{polylog}(m,n))$.

######  Theorem E.2 (Restatement of Proposition 4.5).

Under Assumption E.1, choosing the learning rate $\eta\leq
m/6\|\mathbf{u}\|^{2}_{2}$ small enough and $\epsilon^{\prime}\in(0,1)$, then
with high probability $1-1/\mathrm{poly}(d)$, there exist

$\displaystyle
T^{\dagger}=\frac{4m}{\eta(1-\tau)(1-\rho)\|\mathbf{u}\|_{2}^{2}}\log\left(\frac{2\iota}{\sigma_{0}\|\mathbf{u}\|_{2}}\right),\quad
T=T^{\dagger}+\left\lfloor\frac{Cm^{3}}{2\eta\epsilon\|\mathbf{u}\|_{2}^{2}}\right\rfloor,\quad
T^{\prime}=T+\left\lfloor\frac{\left\|\mathbf{W}^{(T)}-\mathbf{W}^{\star}\right\|_{F}^{2}}{2\eta\epsilon}\right\rfloor,$

with $\tau$, $\iota$ defined in (E.15), (E.16) such that: (i) the average loss
on samples $\mathcal{W}^{c}$ decreases to $3\epsilon$ over iterations
$[T^{\dagger},T]$, i.e.

$\frac{1}{2n}\sum_{i\in\mathcal{W}^{c}}\min_{T^{\dagger}\leq t\leq
T}\left\\{y_{i}-f(\mathbf{x}_{i};\mathbf{W}^{(t)})\right\\}^{2}\leq
3\epsilon,$

(ii) average loss on samples $\mathcal{W}$ decreases to $3\epsilon^{\prime}$
over iterations $[T,T^{\prime}]$, i.e.

$\frac{1}{2n}\sum_{i\in\mathcal{W}}\min_{T\leq t\leq
T^{\prime}}\left(y_{i}-f(\mathbf{x}_{i};\mathbf{W}^{(t)})\right)^{2}\leq
3\epsilon^{\prime},$

(iii) the model does not learn weak signal $\mathbf{v}$ well enough even until
$T^{\prime}$, compared to initialization, i.e.

$\displaystyle\max_{j,r}\left|\langle\mathbf{w}_{j\in\\{\pm
1\\},r\in[m]}^{(t)},\mathbf{v}\rangle\right|\leq
2\sqrt{2\log(16m/p)}\cdot\sigma_{0}\|\mathbf{v}\|_{2},\quad\forall t\leq
T^{\prime}.$ (E.10)

In the multiple training data small learning rate regime, the dynamics go
through three stages, which we characterize in Appendices E.1, E.2, and E.3,
respectively. The following lemma plays an important role in the exponentially
increasing stage (stage 1), for which we single it out here.

######  Lemma E.3 (Derivative lower bound).

For any $0<\tau<1$ to be tuned later, suppose at some time $t$ there holds

$\max_{j\in\\{\pm
1\\},r\in[m]}\left\\{\left|\langle\mathbf{w}_{j,r}^{(t)},\mathbf{u}\rangle\right|,\left|\langle\mathbf{w}_{j,r}^{(t)},\mathbf{v}\rangle\right|,\max_{i\in[n]}\left|\langle\mathbf{w}_{j,r}^{(t)},\bm{\xi}_{i}\rangle\right|,\max_{i\in\mathcal{W}}\left|\langle\mathbf{w}_{j,r}^{(t)},\widetilde{\bm{\xi}}_{i}\rangle\right|\right\\}\leq\sqrt{\frac{\tau}{3}},$

then we can lower bound the fitting residual $-y\ell^{(t)}_{i}\geq 1-\tau$ for
every $i\in[n]$.

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

Plug into the CNN model definition (2.3), we have that

$\displaystyle-y\ell^{(t)}_{i}=1-F_{y}(\mathbf{x}_{i};\mathbf{W}^{(t)})+F_{-y}(\mathbf{x}_{i};\mathbf{W}^{(t)})\geq
1-F_{y}(\mathbf{x}_{i};\mathbf{W}^{(t)}).$

If $i\in\mathcal{W}^{c}$, we can upper bound
$F_{y}(\mathbf{x}_{i};\mathbf{W}^{(t)})$ further by

$\displaystyle F_{y}(\mathbf{x}_{i};\mathbf{W}^{(t)})$
$\displaystyle=\frac{1}{m}\sum_{r\in[m]}\sigma(\langle\mathbf{w}_{y,r}^{(t)},y\mathbf{u}\rangle)+\sigma(\langle\mathbf{w}_{y,r}^{(t)},y\mathbf{v}\rangle)+\sigma(\langle\mathbf{w}_{y,r}^{(t)},\bm{\xi}_{i}\rangle)$
$\displaystyle\leq\max_{r\in[m]}\left\\{\langle\mathbf{w}_{y,r}^{(t)},y\mathbf{u}\rangle^{2}+\langle\mathbf{w}_{y,r}^{(t)},y\mathbf{v}\rangle^{2}+\langle\mathbf{w}_{y,r}^{(t)},\bm{\xi}_{i}\rangle^{2}\right\\}\leq\tau.$

Otherwise, if $i\in\mathcal{W}$, we also have

$\displaystyle F_{y}(\mathbf{x}_{i};\mathbf{W}^{(t)})=$
$\displaystyle\frac{1}{m}\sum_{r\in[m]}\sigma(\langle\mathbf{w}_{y,r}^{(t)},\widetilde{\bm{\xi}}_{i}\rangle)+\sigma(\langle\mathbf{w}_{y,r}^{(t)},y\mathbf{v}\rangle)+\sigma(\langle\mathbf{w}_{y,r}^{(t)},\bm{\xi}_{i}\rangle)$
$\displaystyle\leq$
$\displaystyle\max_{r\in[m]}\left\\{\langle\mathbf{w}_{y,r}^{(t)},\widetilde{\bm{\xi}}_{i}\rangle^{2}+\langle\mathbf{w}_{y,r}^{(t)},y\mathbf{v}\rangle^{2}+\langle\mathbf{w}_{y,r}^{(t)},\bm{\xi}_{i}\rangle^{2}\right\\}\leq\tau.$

Then it follows that $-y\ell^{(t)}\geq 1-\tau$. ∎

###  E.1 Stage 1. Learning Strong Signal Exponentially Fast

In this stage, we mainly track the maximal inner product between $\mathbf{w}$
and the signal vectors $\mathbf{v}$ and $\mathbf{u}$, with extra attention to
the maximal inner product between $\mathbf{w}$ and the noise vectors.

$\displaystyle\Psi^{(t)}$ $\displaystyle=\max_{j\in\\{\pm
1\\},r\in[m]}\left|\langle\mathbf{w}_{j,r}^{(t)},\mathbf{v}\rangle\right|,\quad\Phi^{(t)}=\max_{j\in\\{\pm
1\\},r\in[m]}\left|\langle\mathbf{w}_{j,r}^{(t)},\mathbf{u}\rangle\right|,$
$\displaystyle\Gamma^{(t)}_{i}$ $\displaystyle=\max_{j\in\\{\pm
1\\},r\in[m]}\left|\langle\mathbf{w}_{j,r}^{(t)},\bm{\xi}_{i}\rangle\right|,\quad
i\in[n],$ $\displaystyle\widetilde{\Gamma}^{(t)}_{i}$
$\displaystyle=\max_{j\in\\{\pm
1\\},r\in[m]}\left|\langle\mathbf{w}_{j,r}^{(t)},\widetilde{\bm{\xi}}_{i}\rangle\right|,\quad
i\in\mathcal{W}.$

######  Lemma E.4 (First stage: noise).

Under the same conditions as Theorem E.2, ever since initialization, at least
until time

$\displaystyle T_{+}:=\frac{nm}{3\eta(4+\rho)\sigma_{p}^{2}d},$ (E.11)

there still holds that

$\max_{i\in[n]}\Gamma_{i}^{(t)}\leq\sigma_{0}\sigma_{p}\sqrt{d},\quad\max_{i\in\mathcal{W}}\widetilde{\Gamma}_{i}^{(t)}\leq\sigma_{0}\sigma_{p}\sqrt{d}.$
(E.12)

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

For those inner products with noise vectors, $\forall i\in[n]$, the updating
rules become

$\displaystyle\left|\langle\mathbf{w}_{j,r}^{(t+1)},\bm{\xi}_{i}\rangle\right|$
$\displaystyle\leq\left|\langle\mathbf{w}_{j,r}^{(t)},\bm{\xi}_{i}\rangle\right|+\frac{\eta}{m}\cdot\left|\ell^{(t)}_{i_{t}}\right|\cdot\left(\sigma^{\prime}(\langle\mathbf{w}_{j,r}^{(t)}\cdot\bm{\xi}_{i_{t}}\rangle)\cdot\left|\langle\bm{\xi}_{i_{t}},\bm{\xi}_{i}\rangle\right|+\sigma^{\prime}(\langle\mathbf{w}_{j,r}^{(t)}\cdot\widetilde{\bm{\xi}}_{i_{t}}\rangle)\cdot\left|\langle\widetilde{\bm{\xi}}_{i_{t}},\bm{\xi}_{i}\rangle\right|\cdot\mathbf{1}\\{i_{t}\in\mathcal{W}\\}\right)$
(E.13)
$\displaystyle\leq\left|\langle\mathbf{w}_{j,r}^{(t)},\bm{\xi}_{i}\rangle\right|+\frac{6\eta}{m}\cdot\left(\left|\langle\mathbf{w}_{j,r}^{(t)},\bm{\xi}_{i_{t}}\rangle\right|\cdot\left|\langle\bm{\xi}_{i_{t}},\bm{\xi}_{i}\rangle\right|+\left|\langle\mathbf{w}_{j,r}^{(t)},\widetilde{\bm{\xi}}_{i_{t}}\rangle\right|\cdot\left|\langle\widetilde{\bm{\xi}}_{i_{t}},\bm{\xi}_{i}\rangle\right|\cdot\mathbf{1}\\{i_{t}\in\mathcal{W}\\}\right).$
(E.14)

By taking maximum over $r\in[m]$, we conclude that

$\Gamma^{(t+1)}_{i}\leq\Gamma^{(t)}_{i}+\frac{6\eta}{m}\cdot\left(\Gamma_{i_{t}}^{(t)}\cdot\left|\langle\bm{\xi}_{i_{t}},\bm{\xi}_{i}\rangle\right|+\widetilde{\Gamma}_{i_{t}}^{(t)}\cdot\left|\langle\widetilde{\bm{\xi}}_{i_{t}},\bm{\xi}_{i}\rangle\right|\cdot\mathbf{1}\\{i_{t}\in\mathcal{W}\\}\right),\quad\forall
i\in[n].$

Similarly, we also have that

$\widetilde{\Gamma}^{(t+1)}_{i}\leq\widetilde{\Gamma}^{(t)}_{i}+\frac{6\eta}{m}\cdot\left(\Gamma_{i_{t}}^{(t)}\cdot\left|\langle\bm{\xi}_{i_{t}},\widetilde{\bm{\xi}}_{i}\rangle\right|+\widetilde{\Gamma}_{i_{t}}^{(t)}\cdot\left|\langle\widetilde{\bm{\xi}}_{i_{t}},\widetilde{\bm{\xi}}_{i}\rangle\right|\cdot\mathbf{1}\\{i_{t}\in\mathcal{W}\\}\right),\quad\forall
i\in\mathcal{W}.$

We then use induction to rigorously prove our conclusions. Firstly, (E.12)
holds at time $t=0$. Now suppose that (E.12) holds until some
$\widetilde{T}<T_{+}$. Fixing some $i\in[n]$,

$\displaystyle\Gamma^{(\widetilde{T}+1)}_{i}$
$\displaystyle\leq\frac{6\eta\sigma_{0}\sigma_{p}\sqrt{d}}{m}\cdot\sum_{t=0}^{\widetilde{T}}\left(\left|\langle\bm{\xi}_{i_{t}},\bm{\xi}_{i}\rangle\right|+\left|\langle\widetilde{\bm{\xi}}_{i_{t}},\bm{\xi}_{i}\rangle\right|\cdot\mathbf{1}\\{i_{t}\in\mathcal{W}\\}\right)$
$\displaystyle\leq\frac{6\eta\sigma_{0}\sigma_{p}\sqrt{d}}{m}\cdot\left(\frac{3\widetilde{T}\sigma_{p}^{2}d}{2n}+2\widetilde{T}\cdot(1+\rho)\cdot\sigma_{p}^{2}\sqrt{d\log(4n^{2}/p)}\right)$
$\displaystyle\leq\frac{3\eta\sigma_{0}\sigma_{p}\sqrt{d}(4+\rho)\widetilde{T}\sigma_{p}^{2}d}{nm}$
$\displaystyle\leq\sigma_{0}\sigma_{p}\sqrt{d}.$

The first inequality is by induction hypothesis. The second inequality is
because that there are at most $\widetilde{T}/n$ many $i_{t}$’s would equal
$i$ and at most $\rho\widetilde{T}$ many $i_{t}$’s would be in $\mathcal{W}$,
and we also use Lemma A.3 to control the correlations between noise vectors.
The third inequality is by $d\geq 16n^{2}\log(4n^{2}/p)$ for Assumption E.1 ,
while the last inequality is due to $\widetilde{T}<T_{+}$. Similarly, we can
also control $\widetilde{\Gamma}_{i}^{(t+1)}$ for some fixed $i\in\mathcal{W}$
as

$\displaystyle\widetilde{\Gamma}^{(\widetilde{T}+1)}_{i}$
$\displaystyle\leq\frac{6\eta\sigma_{0}\sigma_{p}\sqrt{d}}{m}\cdot\sum_{t=0}^{\widetilde{T}}\left(\left|\langle\bm{\xi}_{i_{t}},\widetilde{\bm{\xi}}_{i}\rangle\right|+\left|\langle\widetilde{\bm{\xi}}_{i_{t}},\widetilde{\bm{\xi}}_{i}\rangle\right|\cdot\mathbf{1}\\{i_{t}\in\mathcal{W}\\}\right)$
$\displaystyle\leq\frac{6\eta\sigma_{0}\sigma_{p}\sqrt{d}}{m}\left(\frac{3\widetilde{T}\sigma_{p}^{2}d}{2n}+2\widetilde{T}\cdot(1+\rho)\cdot\sigma_{p}^{2}\sqrt{d\log(4n^{2}/p)}\right)$
$\displaystyle\leq\sigma_{0}\sigma_{p}\sqrt{d},$

where the second inequality is because there are at most $\widetilde{T}/n$
many $i_{t}$’s would equal $i\in\mathcal{W}$. In conclusion, (E.12) holds at
least until $T_{+}$. ∎

In the following, we would take

$\displaystyle\tau$
$\displaystyle=\max\left\\{2\sigma_{0}\|\mathbf{u}\|_{2}\left(2\log(16m/p)\right)^{1/2-\|\mathbf{v}\|_{2}^{2}/4(\sigma_{p}^{2}d)},1-\frac{6\sqrt{2}\sigma_{p}^{2}d}{\|\mathbf{u}\|_{2}^{2}\log(2/\sqrt{2\log(16m/p)})}\right\\},$
(E.15) $\displaystyle\iota$
$\displaystyle=2\sigma_{0}\|\mathbf{u}\|_{2}\cdot\exp\left\\{\frac{(1-\tau)(1-\rho)\|\mathbf{u}\|_{2}^{2}}{3(4+\rho)\sigma_{p}^{2}d}\right\\}.$
(E.16)

By the conditions in Assumption E.1 on
$\|\mathbf{v}\|_{2}^{2}/\|\mathbf{u}\|_{2}^{2}$, we find $\tau,\iota$ both
constant in $(0,1)$.

######  Lemma E.5 (First stage: signal).

Under the same conditions as Theorem E.2, there exists time

$T^{\dagger}=\frac{4m}{\eta(1-\tau)(1-\rho)\|\mathbf{u}\|_{2}^{2}}\log\left(\frac{2\iota}{\sigma_{0}\|\mathbf{u}\|_{2}}\right),$

such that: (i) the model learns strong signal to a constant level,

$\max_{r\in[m]}\langle\mathbf{w}_{j,r}^{(T^{\dagger})},j\mathbf{u}\rangle\geq\iota,\quad\forall
j\in\\{\pm 1\\},$

(ii) compared to the random initialization, the model does not learn weak
signal that much, i.e.,

$\displaystyle\max_{j\in\\{\pm
1\\},r\in[m]}\left|\langle\mathbf{w}_{j,r}^{(T^{\dagger})},\mathbf{v}\rangle\right|\leq
2\sqrt{2\log(16m/p)}\cdot\sigma_{0}\|\mathbf{v}\|_{2}$ (E.17)

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

Firstly, we would find $\\{\Psi^{(t)},\Phi^{(t)}\\}_{t\geq 0}$ having an
exponentially growing upper bound. Recursively, we would have that

$\displaystyle\Psi^{(t+1)}$ $\displaystyle\leq\Psi^{(t)}+\max_{j\in\\{\pm
1\\},r\in[m]}\left|\frac{jy\eta}{m}\cdot\big{(}f(\mathbf{x}_{i};\mathbf{W}^{(t)})-y\big{)}\cdot\sigma^{\prime}(\langle\mathbf{w}_{j,r}^{(t)},y\mathbf{v}\rangle)\cdot\|\mathbf{v}\|_{2}^{2}\right|$
(E.18)
$\displaystyle=\Psi^{(t)}+\frac{\eta}{m}\cdot\left|\ell^{(t)}_{i}\right|\cdot\|\mathbf{v}\|_{2}^{2}\cdot\max_{j\in\\{\pm
1\\},r\in[m]}\sigma^{\prime}(\langle\mathbf{w}_{j,r}^{(t)},y\mathbf{v}\rangle)$
(E.19)
$\displaystyle\leq\Psi^{(t)}+\frac{2\eta}{m}\cdot\left|\ell^{(t)}_{i}\right|\cdot\|\mathbf{v}\|_{2}^{2}\cdot\Psi^{(t)}$
(E.20)
$\displaystyle\leq\exp\left(\frac{6\eta\|\mathbf{v}\|_{2}^{2}}{m}\right)\cdot\Psi^{(t)}.$
(E.21)

Therefore, we have that

$\displaystyle\Psi^{(t)}\leq\exp\left(\frac{6\eta\|\mathbf{v}\|_{2}^{2}t}{m}\right)\cdot\Psi^{(0)}\leq\exp\left(\frac{6\eta\|\mathbf{v}\|_{2}^{2}t}{m}\right)\cdot\sqrt{2\log(16m/p)}\cdot\sigma_{0}\|\mathbf{v}\|_{2}$
(E.22)

It follows similarly that

$\displaystyle\Phi^{(t)}\leq\exp\left(\frac{6\eta(1-\rho)\|\mathbf{u}\|_{2}^{2}t}{m}\right)\cdot\Phi^{(0)}\leq\exp\left(\frac{6\eta(1-\rho)\|\mathbf{u}\|_{2}^{2}t}{m}\right)\cdot\sqrt{2\log(16m/p)}\cdot\sigma_{0}\|\mathbf{u}\|_{2}.$
(E.23)

The extra factor $1-\rho$ appears because only a $1-\rho$ proportion of data
points would contain $\mathbf{u}$, and therefore contribute to evolution of
$\Phi^{(t)}$. Note that growing rates of these two bounds differ a lot due to
the different magnitudes of $(1-\rho)\|\mathbf{u}\|_{2}$ and
$\|\mathbf{v}\|_{2}$.

Our subsequent analysis illustrates that $\Phi^{(t)}$ can grow into a
constant-level magnitude since strong signal $\mathbf{u}$ is significant
enough. We can track how well our model learns $\mathbf{u}$ by

$A^{(t)}_{1}=\max_{r\in[m],i_{t}\notin\mathcal{W}}\langle\mathbf{w}_{1,r}^{(t)},\mathbf{u}\rangle,\quad
A^{(t)}_{-1}=\max_{r\in[m],i_{t}\notin\mathcal{W}}\langle\mathbf{w}_{-1,r}^{(t)},-\mathbf{u}\rangle.$

By definition, $A^{(t)}_{1},A^{(t)}_{-1}\leq\Phi^{(t)}$ also admits an
exponentially upper bound in (E.23) . For a certain $\tau\in(0,1)$, due to the
exponential upper bounds (E.22) and (E.23),
$\max\\{\Phi^{(t)},\Psi^{(t)}\\}\leq\sqrt{\tau/3}$ is true at least until

$T_{1}=\frac{m}{6\eta(1-\rho)\|\mathbf{u}\|_{2}^{2}}\log\left(\frac{\sqrt{\tau/2}}{\sigma_{0}\|\mathbf{u}\|_{2}\sqrt{2\log(16m/p)}}\right).$

Moreover, since we have $(1-\rho)\|\mathbf{u}\|_{2}^{2}\gg\sigma_{p}^{2}d/n$
by Assumption E.1, we also know $T_{1}\leq T_{+}$ where $T_{+}$ comes from
Lemma E.4. Therefore

$\displaystyle\Gamma_{i}^{(t)}\leq\sigma_{0}\sigma_{p}\sqrt{d}\leq\sqrt{\tau/3},\quad\widetilde{\Gamma}_{i}^{(t)}\leq\sigma_{0}\sigma_{p}\sqrt{d}\leq\sqrt{\tau/3},\quad\forall
t\leq T_{1}$ (E.24)

Consequently, until at least time $T_{1}$, we can use Lemma E.3 to conclude
that $-y_{i_{t}}\ell^{(t)}_{i_{t}}\geq 1-\tau$, which enables lower bounding
$A^{(t)}$ in the following.

The $i_{t}$-th sample would be used to update parameters, according to our
multi-pass SGD updates (2.5). If $i_{t}\in\mathcal{W}$, then
$\langle\mathbf{w}_{j,r}^{(t+1)},j\mathbf{u}\rangle=\langle\mathbf{w}_{j,r}^{(t)},j\mathbf{u}\rangle$
holds for any $j\in\\{\pm 1\\}$ and $r\in[m]$. If $i_{t}\notin\mathcal{W}$ but
$y_{i_{t}}=-1$, then
$\max_{r}\langle\mathbf{w}_{1,r}^{(t+1)},\mathbf{u}\rangle=\max_{r}\langle\mathbf{w}_{1,r}^{(t)},\mathbf{u}\rangle\geq
0$ since that neuron will not be activated. Otherwise, only if
$i_{t}\notin\mathcal{W}$ and $y_{i_{t}}=1$, the updating rule becomes

$\displaystyle\langle\mathbf{w}_{1,r}^{(t+1)},\mathbf{u}\rangle$
$\displaystyle=\langle\mathbf{w}_{1,r}^{(t)},\mathbf{u}\rangle+\frac{\eta}{m}\cdot\big{(}-y_{i_{t}}\ell^{(t)}_{i_{t}}\big{)}\cdot\sigma^{\prime}(\langle\mathbf{w}_{1,r}^{(t)},\mathbf{u}\rangle)\cdot\|\mathbf{u}\|_{2}^{2}$
$\displaystyle\geq\langle\mathbf{w}_{1,r}^{(t)},\mathbf{u}\rangle+\frac{2\eta(1-\tau)\|\mathbf{u}\|_{2}^{2}}{m}\cdot\max\left\\{\langle\mathbf{w}_{1,r}^{(t)},\mathbf{u}\rangle,0\right\\}.$

Take maximum over $r\in[m]$ to see that

$\displaystyle A^{(t+1)}_{1}\geq
A^{(t)}_{1}+\frac{2\eta(1-\tau)\|\mathbf{u}\|_{2}^{2}}{m}\cdot
A^{(t)}_{1}\geq\exp\left(\frac{\eta(1-\tau)\|\mathbf{u}\|^{2}}{m}\right)\cdot
A^{(t)}_{1},$

where the last equality is by $1+z\geq\exp(z/2)$ for any $0\leq z\leq 2$.
Consequently, when $t$ is large (larger than $n$), we would have

$\displaystyle A^{(t)}_{1}\geq$
$\displaystyle\exp\left(\frac{\eta(1-\tau)\|\mathbf{u}\|_{2}^{2}}{m}\cdot\sum_{t^{\prime}\leq
t}\mathbf{1}\\{i_{t^{\prime}}\notin\mathcal{W},y_{i_{t}}=1\\}\right)\cdot
A^{(0)}_{1}$ (E.25) $\displaystyle\geq$
$\displaystyle\exp\left(\frac{\eta(1-\tau)\|\mathbf{u}\|_{2}^{2}\cdot(1-\rho)\cdot
t}{4m}\right)\cdot\sigma_{0}\|\mathbf{u}\|_{2}/2,$ (E.26)

at least until step $t\leq T_{1}$. We use the fact that $\sum_{t^{\prime}\leq
t}\mathbf{1}\\{i_{t^{\prime}}\notin\mathcal{W},y_{i_{t}}=1\\}\geq(1-\rho)t/4$
because the sample labels are balanced (Lemma A.1) and $1-\rho$ proportion of
samples come with the strong signal. In the same manner, we would have that

$\displaystyle
A^{(t)}_{-1}\geq\exp\left(\frac{\eta(1-\tau)\|\mathbf{u}\|_{2}^{2}(1-\rho)t}{4m}\right)\cdot\sigma_{0}\|\mathbf{u}\|_{2}/2.$
(E.27)

Define the time when $A^{(t)}_{\pm 1}$ both break $\iota$,

$\displaystyle
T_{2}=\frac{4m}{\eta(1-\tau)(1-\rho)\|\mathbf{u}\|_{2}^{2}}\log\left(\frac{2\iota}{\sigma_{0}\|\mathbf{u}\|_{2}}\right)\leq
T_{1},$ (E.28)

where the inequality is due to the scaling of $\iota$ upon $\tau$. Moreover,
we also need that $T_{2}\leq T_{+}$, where $T_{+}$ is the time that
$\langle\mathbf{w}_{j,r}^{(t)},\widetilde{\bm{\xi}}_{i}\rangle,\langle\mathbf{w}_{j,r}^{(t)},\bm{\xi}_{i}\rangle$
remains in $\mathcal{O}(\sigma_{0}\sigma_{p}\sqrt{d})$. And this requirement
is also achieved by the selection of $\tau$ and $\iota$. Plugging $T_{2}$ into
the exponential lower bounds (E.26) and (E.27), we can conclude that

$\displaystyle\Phi^{(T_{2})}\geq A^{(T_{2})}_{\pm 1}\geq\iota,$ (E.29)

which already grows up to a constant level magnitude by the time $T_{2}$.
Lastly, plug the definition of $T_{2}$ to upper bound $\psi^{(T_{2})}$ as

$\displaystyle\Psi^{(T_{2})}\leq\exp\left(\frac{24\|\mathbf{v}\|_{2}^{2}}{(1-\tau)(1-\rho)\|\mathbf{u}\|_{2}^{2}}\log\left(\frac{2\iota}{\sigma_{0}\|\mathbf{u}\|_{2}}\right)\right)\cdot\sqrt{2\log(16m/p)}\cdot\sigma_{0}\|\mathbf{v}\|_{2}\leq
2\sqrt{2\log(16m/p)}\cdot\sigma_{0}\|\mathbf{v}\|_{2}.$ (E.30)

In conclusion, by taking $T^{\dagger}=T_{2}$, this lemma is completely proved.
∎

###  E.2 Stage 2. Exploiting Strong Signal

In the second stage, our lemmas suggest that before the model really learns
the weak signal $\mathbf{v}$ or memorizes any noise vector, the model already
fits a proportion $1-\rho$ of the data points (i.e., strong data) by
exploiting strong signal $\mathbf{u}$.

######  Lemma E.6 (Second stage).

Under the same conditions as Theorem E.2, there exists time

$T=T^{\dagger}+\left\lfloor\frac{Cm^{3}}{2\eta\epsilon\|\mathbf{u}\|_{2}^{2}}\right\rfloor$

such that: (i) the average loss over iterations within this stage has
decreased to $2\epsilon$, i.e.,

$\frac{1}{2n}\sum_{i\in\mathcal{W}^{c}}\min_{T^{\dagger}\leq t\leq
T}\left\\{y_{i}-f(\bm{x}_{i};\mathbf{W}^{(t)})\right\\}^{2}\leq 3\epsilon,$

(ii) all through the training dynamics $0\leq t\leq T$, there holds that

$\displaystyle\max_{j\in\\{\pm
1\\},r\in[m]}\left|\langle\mathbf{w}_{j,r}^{(t)},\mathbf{v}\rangle\right|\leq
2\sqrt{2\log(16m/p)}\sigma_{0}\cdot\|\mathbf{v}\|_{2},$ (E.31)

(iii) all through the training dynamics $0\leq t\leq T$, there holds that

$\displaystyle\max_{j\in\\{\pm
1\\},r\in[m],i\in[n]}\left|\langle\mathbf{w}_{j,r}^{(t)},\bm{\xi}_{i}\rangle\right|\leq\sigma_{0}\sigma_{p}\sqrt{d},\quad\max_{j\in\\{\pm
1\\},r\in[m],i\in\mathcal{W}}\left|\langle\mathbf{w}_{j,r}^{(t)},\widetilde{\bm{\xi}}_{i}\rangle\right|\leq\sigma_{0}\sigma_{p}\sqrt{d}.$
(E.32)

In studying the second stage, we firstly identify when the upper bound on
$\langle\mathbf{w}_{j,r}^{(t)},\mathbf{v}\rangle$ breaks and find that the
conclusions of Lemma E.5 still holds before that time.

######  Lemma E.7.

Under the same conditions as Theorem E.2, take $\eta\leq
m/6\|\mathbf{u}\|_{2}^{2}$. There exists a time

$\displaystyle
T^{\ddagger}=\frac{m}{6\eta\|\mathbf{v}\|_{2}^{2}}\log\left(\frac{\sqrt{\tau/2}}{\sigma_{0}\|\mathbf{v}\|_{2}\sqrt{2\log(16m/p)}}\right)\geq
T^{\dagger}$ (E.33)

such that (E.12) and

$\displaystyle\max_{j\in\\{\pm
1\\},r\in[m]}\left|\langle\mathbf{w}_{j,r}^{(t)},\mathbf{v}\rangle\right|\leq
2\sqrt{2\log(16m/p)}\sigma_{0}\|\mathbf{v}\|,\quad\max_{r\in[m]}\langle\mathbf{w}_{j,r}^{(t)},j\mathbf{u}\rangle\geq\iota/2,\quad\forall
j\in\\{\pm 1\\},$ (E.34)

hold for any $T^{\dagger}\leq t\leq T^{\ddagger}$.

###### Proof of Lemma E.7.

Firstly, we need to adopt the exponential upper bound derived in proving Lemma
E.5,

$\Psi^{(t)}\leq\exp\left(\frac{6\eta\|\mathbf{v}\|_{2}^{2}t}{m}\right)\cdot\Psi^{(0)}\leq\exp\left(\frac{6\eta\|\mathbf{v}\|_{2}^{2}t}{m}\right)\cdot\sqrt{2\log(16m/p)}\cdot\sigma_{0}\|\mathbf{v}\|_{2}.$

Then we naturally find that before $T^{\ddagger}$, it would always hold that

$\displaystyle\max_{j\in\\{\pm
1\\},r\in[m]}\left|\langle\mathbf{w}_{j,r}^{(t)},\mathbf{v}\rangle\right|\leq
2\sqrt{2\log(16m/p)}\cdot\sigma_{0}\|\mathbf{v}\|_{2}.$ (E.35)

Due to the conditions on $\|\mathbf{u}\|_{2}^{2}/\|\mathbf{v}\|_{2}^{2}$,
$T^{\ddagger}$ is found to be much larger than $T^{\dagger}$. Then we proceed
to prove the other assertion by induction. At time $t=T^{\dagger}$, the lower
bound $\max_{j,r}\langle\mathbf{w}_{j,r}^{(t)},j\mathbf{u}\rangle\geq\iota/2$
holds as a consequence of the previous lemma. Suppose it holds until time $t$.
If $i_{t}\in\mathcal{W}$, then
$\langle\mathbf{w}_{j,r}^{(t+1)},j\mathbf{u}\rangle=\langle\mathbf{w}_{j,r}^{(t)},j\mathbf{u}\rangle$
holds for any $j\in\\{\pm 1\\},r\in[m]$. If $i_{t}\notin\mathcal{W}$ but
$y_{i_{t}}=-1$, then
$\max_{r\in[m]}\langle\mathbf{w}_{1,r}^{(t+1)},\mathbf{u}\rangle=\max_{r\in[m]}\langle\mathbf{w}_{1,r}^{(t)},\mathbf{u}\rangle\geq
0$ since that neuron will not be activated. Otherwise, if
$i_{t}\notin\mathcal{W}$ and $y_{i_{t}}=1$, consider the updating rule

$\displaystyle\langle\mathbf{w}_{1,r}^{(t+1)},\mathbf{u}\rangle=\langle\mathbf{w}_{1,r}^{(t)},\mathbf{u}\rangle+\frac{\eta}{m}\cdot\big{(}1-y_{i_{t}}f(\mathbf{x}_{i_{t}};\mathbf{W}^{(t)})\big{)}\cdot\sigma^{\prime}(\langle\mathbf{w}_{1,r}^{(t)},\mathbf{u}\rangle)\cdot\|\mathbf{u}\|_{2}^{2},$
(E.36)

from which we find
$\max_{r\in[m],i_{t}\notin\mathcal{W}}\langle\mathbf{w}_{y_{i},r}^{(t+1)},y_{i}\mathbf{u}\rangle\geq\max_{r\in[m],i_{t}\notin\mathcal{W}}\langle\mathbf{w}_{y_{i},r}^{(t)},y_{i}\mathbf{u}\rangle$
must hold if $y_{i_{t}}f(\mathbf{x}_{i_{t}};\mathbf{W}^{(t)})\leq 1$.
Otherwise, once $y_{i_{t}}f(\mathbf{x}_{i_{t}};\mathbf{W}^{(t)})>1$, it
immediately follows that

$\displaystyle 1$
$\displaystyle<y_{i_{t}}f(\mathbf{x}_{i_{t}};\mathbf{W}^{(t)})=F_{y_{i_{t}}}(\mathbf{x}_{i_{t}};\mathbf{W}^{(t)})-F_{-{y_{i_{t}}}}(\mathbf{x}_{i_{t}};\mathbf{W}^{(t)})$
(E.37) $\displaystyle\leq
F_{y_{i_{t}}}(\mathbf{x}_{i_{t}};\mathbf{W}^{(t)})=\frac{1}{m}\sum_{r\in[m]}\sigma(\langle\mathbf{w}_{1,r}^{(t)},y_{i_{t}}\mathbf{u}\rangle)+\sigma(\langle\mathbf{w}_{1,r}^{(t)},y_{i_{t}}\mathbf{v}\rangle)+\sigma(\langle\mathbf{w}_{1,r}^{(t)},\mathbf{\xi}_{i_{t}}\rangle)$
(E.38)
$\displaystyle\leq\max_{r\in[m]}\langle\mathbf{w}_{1,r}^{(t)},\mathbf{u}\rangle^{2}+\sigma_{0}^{2}\|\mathbf{v}\|^{2}+\sigma_{0}^{2}\sigma_{p}^{2}d.$
(E.39)

Consequently, for the specific neuron
$r^{\ast}=\mathop{\mathrm{argmax}}_{r\in[m]}\langle\mathbf{w}_{1,r}^{(t)},\mathbf{u}\rangle^{2}$,
there holds

$\displaystyle\langle\mathbf{w}_{1,r^{\ast}}^{(t+1)},\mathbf{u}\rangle$
$\displaystyle\geq\langle\mathbf{w}_{1,r^{\ast}}^{(t)},\mathbf{u}\rangle-\frac{3\eta}{m}\cdot\langle\mathbf{w}_{1,r^{\ast}}^{(t)},\mathbf{u}\rangle\cdot\|\mathbf{u}\|_{2}^{2}$
(E.40)
$\displaystyle\geq\left(1-8\log(16m/p)\cdot\sigma_{0}^{2}\|\mathbf{v}\|_{2}^{2}-\sigma_{0}^{2}\sigma_{p}^{2}d\right)\cdot\left(1-\frac{3\eta}{m}\cdot\|\mathbf{u}\|_{2}^{2}\right)$
(E.41) $\displaystyle\geq\frac{\iota}{2},$ (E.42)

where the last inequality is enabled by taking

$\displaystyle\eta\leq\frac{m}{6\|\mathbf{u}\|_{2}^{2}},\quad\sigma_{0}\leq\sqrt{\frac{1-\iota}{8\log(16m/p)\cdot\|\mathbf{v}\|_{2}^{2}+\sigma_{p}^{2}d}}.$
(E.43)

Therefore, we find that
$\max_{r\in[m]}\langle\mathbf{w}_{1,r}^{(t+1)},\mathbf{u}\rangle\geq\iota/2$
must hold no matter what $i_{t}$ is. In the same way, one can also obtain
$\max_{r\in[m]}\langle\mathbf{w}_{-1,r}^{(t+1)},-\mathbf{u}\rangle\geq\iota/2$.
By induction, the induction proof is complete. ∎

Our subsequently analysis confirms that even before $T^{\ddagger}$, the model
can already fit those data points with strong signal by exploiting
$\mathbf{u}$. For the given $0<\epsilon<1$, define a reference point
$\mathbf{W}^{\ast}$ as

$\mathbf{w}_{j,r}^{\ast}=\frac{4m(1+\epsilon)}{\iota}\cdot\frac{j\mathbf{u}}{\|\mathbf{u}\|_{2}^{2}},\quad
j\in\\{\pm 1\\},r\in[m].$ (E.44)

######  Lemma E.8.

Under the same condition as the previous lemma, for all $T^{\dagger}\leq t\leq
T^{\ddagger}$, there holds

$\displaystyle y_{i}\langle\nabla
f(\mathbf{x}_{i};\mathbf{W}^{(t)}),\mathbf{W}^{\ast}\rangle\geq
2\cdot(1+\epsilon)$ (E.45)

for any $i\notin\mathcal{W}$.

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

Recall that the definition of CNN in (2.3) and that
$\mathbf{u}\perp\mathrm{span}(\mathbf{v},\bm{\xi}_{i})$. We have that

$\displaystyle y_{i}\langle\nabla
f(\mathbf{x}_{i};\mathbf{W}^{(t)}),\mathbf{W}^{\ast}\rangle$
$\displaystyle=\frac{1}{m}\sum_{j\in\\{\pm