Figure 7: Confusion matrices (excluding base initialization data) for
incremental and streaming learning models after class-incremental CIFAR100
training. Incremental learning techniques (iCarl and E2EIL) are biased towards
recently-observed classes (see the many incorrect predictions for classes
80-100 in the two leftmost plots). In contrast, incorrect predictions for
REMIND are concentrated on the last class observed during streaming (see the
line of incorrect predictions at the bottom of third plot). This bias starts
getting corrected when 100 replay samples—instead of 50—are used during each
online update (see the rightmost plot).

Interestingly, many incremental learning approaches exist that perform end-to-
end training (Castro et al., 2018; Hou et al., 2019; Wu et al., 2019). Thus,
one may wonder whether a high-quality streaming approach—one that comes closer
to matching offline learning performance—could be developed by simple
modifications to such techniques. Unfortunately, these techniques, which
employ replay, bias correction, and knowledge distillation to prevent
catastrophic forgetting, are known to perform poorly in the streaming domain
(Hayes et al., 2020). To understand why this is the case, it should be noted
that knowledge distillation is known to provide minimal added benefit when
combined with replay mechanisms (Belouadah & Popescu, 2020; 2019).
Furthermore, we find that correcting bias in the network’s classification
layer is unnecessary for streaming learning. Though batch-incremental
techniques are biased towards recently-observed classes, REMIND is only biased
towards a single class (i.e., the last streamed class), which is easily
corrected by increasing the number of replay samples observed during each
online update; see Figure 7 and Appendix A.7 for experimental
details.151515Many incremental learning works have been proposed to correct
such bias towards recently-observed classes(Hou et al., 2019; Wu et al.,
2019). We emphasize that our focus here is not to compare streaming learning
to the most recent approaches for incremental learning, but rather to
demonstrate that bias towards recent classes is not a consideration for the
streaming domain that we consider.

Such observations reveal that findings relevant to batch-incremental learning
may not translate to the streaming setting. Additionally, a better streaming
methodology cannot be derived by simply adopting and modifying established
techniques for batch incremental learning. To close the performance gap with
offline learning, streaming techniques likely need to avoid freezing network
parameters and leverage more effective forms of replay, as other techniques
like knowledge distillation and bias correction provide minimal benefit.

Method | PQ Encoding | Forward Pass | Backward Pass | Parameter Update
---|---|---|---|---
Time | Time | Time | Time
CSSL | - | 3.67 $\pm$ 0.45 | 5.41 $\pm$ 0.97 | 1.53 $\pm$ 0.06
REMIND | 23.37 $\pm$ 1.13 | 2.65 $\pm$ 0.02 | 1.62 $\pm$ 0.03 | 0.52 $\pm$ 0.01
REMIND + Extra Params | 23.37 $\pm$ 1.13 | 2.95 $\pm$ 0.12 | 1.84 $\pm$ 0.09 | 0.69 $\pm$ 0.04
Table 15: Timing metrics (in milliseconds) for performing model inference and
updates with different streaming methodologies on ImageNet. Because CSSL is
fully-plastic, backward passes and parameter updates take longer to complete,
but REMIND’s use of product quantization to encode model hidden
representations make inference time an order of magnitude slower in comparison
to CSSL.

###  B.7 Computational Impact of Full Plasticity

Given that CSSL makes all model parameters trainable, one may wonder about the
impact of such an approach on the computational complexity of performing
updates and inferences with the underlying model throughout streaming. To
better understand the complexity impact of full plasticity, we measure the
time taken to $i)$ perform a forward pass, $ii)$ perform a backward pass, and
$iii)$ update model parameters with CSSL over several streaming iterations.
For comparison, we perform the same test with REMIND, which freezes a majority
of the underlying network’s early layers.

These timing tests use a ResNet18 model and are performed on the ImageNet
dataset using the same procedure described in Appendix A.1. At each iteration,
100 replay examples are sampled for both CSSL and REMIND. For REMIND, we also
perform supplemental test in which the underlying model has added layers to
make the number of trainable parameters equal to that of CSSL. In all cases,
we measure timing across five streaming iterations and report the average
time; see Table 15.

CSSL has a more expensive forward pass, backward pass, and parameter update in
comparison to REMIND, due to the fact that all network layers are updated by
CSSL. However, REMIND encodes the output of the network’s frozen feature
extractor with a product quantization (PQ) (Jegou et al., 2010) module, which
is quite slow in comparison to the other operations. As such, when data is
passed through the REMIND model—aside from replay examples for which the
model’s encoded hidden representations can be cached—it must be passed through
the frozen portion of the network, encoded via PQ, then passed through the
remaining, trainable layers, making the total inference time of REMIND an
order of magnitude slower than that of CSSL.

##  Appendix C Adapting Baselines to CSSL.

CSSL is capable of randomly initializing the full network—and all network
modules—immediately prior to the commencement of streaming; see Section 3. The
baseline methodologies used within Section 6.1 (i.e., ExStream, Deep SLDA, and
REMIND), however, all utilize pre-trained networks within their respective
streaming algorithms. In particular, ExStream (Hayes et al., 2018) and Deep
SLDA (Hayes & Kanan, 2020) train only the final, fully-connected layer of the
neural network, while REMIND trains the last few convolutional layers and the
final fully-connected layer during streaming—all other network layers are
fixed either by using pre-trained network parameters or performing offline
training over a subset of data during base initialization.

To be capable of starting streaming from a random initialization, baseline
methodologies would either have to $i)$ allow nearly all (or a majority of)
network layers to remain random throughout streaming or $ii)$ be adapted to
train the network end-to-end. Forcing network layers to remain random
throughout streaming catastrophically degrades performance, and adapting such
methodologies to perform end-to-end training is highly non-trivial, as a
majority of techniques within each methodology would break down (e.g.,
compressing the feature representations with PQ, clustering feature vectors,
computing feature covariance, etc.). As such, we simply compare CSSL to
baseline approaches in their original form, without forcing baselines to
conform a cold-start setting (i.e., baselines do not satisfy rule four from
Section 3).

##  Appendix D Technical Results

Within this section, we outline the technical theoretical results (i.e.,
Lemmas and Corollaries) that are established in the process of proving Theorem
1. Again, full proofs of each result are deferred to Section E.

######  Lemma 1.

Assume Assumption 1 holds and
$\omega\leq\mathcal{O}\left(L^{-6}\log^{-3}(m)\right)$. Consider iterates
$\mathbb{W}^{(0)},\dots,\mathbb{W}^{(n)}\in\mathcal{B}(\mathbb{W}^{(0)},\omega)$
obtained via Algorithm 1 with $B$ replay examples taken from buffer
$\mathcal{R}$ per iteration with $\eta=\mathcal{O}(m^{-\frac{3}{2}})$. Given
sufficient overparamterization characterized by

$\displaystyle m\geq\mathcal{O}\left(nB\sqrt{1+\Xi}L^{6}\log^{3}(m)\right)$

We have

$\displaystyle\sum_{t=1}^{n}L_{(t,\xi_{t})}(\mathbb{W}^{(i)})\leq\sum_{t=1}^{n}L_{(t,\xi_{t})}(\mathbb{W}^{\star})+\mathcal{O}\left(LR^{2}m^{-\frac{1}{2}}\right)+\mathcal{O}\left(nm^{-\frac{1}{2}}BL(1+\Xi)\right)$

for $\mathbb{W}^{\star}\in\mathcal{B}(\mathbb{W}^{(0)},\nicefrac{{R}}{{m}})$
with $R>0$ and probability at least
$1-\mathcal{O}(nBL)e^{-\Omega\left(m\omega^{\frac{2}{3}}L\right)}$.

######  Lemma 2.

Given Assumption 1 and taking
$\omega\leq\mathcal{O}\left(L^{-6}\log^{-3}(m)\right)$, we have that

$\displaystyle\mathbb{W}^{(0)},\dots,\mathbb{W}^{(n)}\in\mathcal{B}(\mathbb{W}^{(0)},\omega)$

over $n$ successive iterations of Algorithm 1 with $B$ replay samples taken
from buffer $\mathcal{R}$ per iteration, arbitrary perturbation vectors
applied to both new and replayed data, $\eta=\mathcal{O}(m^{-\frac{3}{2}})$,
and sufficient overparameterization given by

$\displaystyle m\geq\mathcal{O}\left(nB\sqrt{1+\Xi}L^{6}\log^{3}(m)\right)$

with probability at least
$1-\mathcal{O}(nLB)e^{-\Omega\left(m\omega^{\frac{2}{3}}L\right)}$.

######  Lemma 3.

Assume Assumption 1 holds and
$\omega\leq\mathcal{O}\left(L^{-6}\log^{-3}(m)\right)$. Then, when
$\mathbb{W},\mathbb{W}^{\prime}\in\mathcal{B}(\mathbb{W}^{(0)},\omega)$, we
have

$\displaystyle\left|f_{\mathbb{W}^{\prime}}(x_{t}+\xi)-f_{\mathbb{W}}(x_{t}+\xi)-\left\langle\nabla_{\mathbb{W}}f_{\mathbb{W}}(x_{t}+\xi),\mathbb{W}^{\prime}-\mathbb{W}\right\rangle\right|$
$\displaystyle\quad\quad\leq\mathcal{O}\left(\sqrt{m\left(1+\|\xi\|_{2}^{2}\right)}\omega^{\frac{4}{3}}L^{3}\log(m)\right)$

for arbitrary perturbation vector $\xi$161616Here, we do not assign a
subscript $\xi_{t}$ to the perturbation vector intentionally. This is because
the perturbation vector used for this result is arbitrary. Namely, different
perturbation vectors can be used for any $t\in[n]$ and both when the data is
encountered newly or sampled for replay. The result holds for any perturbation
vector chosen for each of these scenarios, where the final bound then depends
on the factor $\|\xi\|_{2}^{2}$. and all $t\in[n]$ with probability at least
$1-\mathcal{O}(nL)e^{-\Omega\left(m\omega^{\frac{2}{3}}L\right)}$.

######  Corollary 1.

Assume Assumption 1 holds and
$\omega\leq\mathcal{O}\left(L^{-6}\log^{-3}(m)\right)$, then when
$\mathbb{W},\mathbb{W}^{\prime}\in\mathcal{B}(\mathbb{W}^{(0)},\omega)$, we
can extend Lemma 3 to show

$\displaystyle L_{(t,\xi)}(\mathbb{W}^{\prime})-L_{(t,\xi)}(\mathbb{W})$
$\displaystyle\geq\sum\limits_{l=1}^{L}\langle\nabla_{W_{l}}L_{(t,\xi)}(\mathbb{W}),W_{l}^{\prime}-W_{l}\rangle-\mathcal{O}\left(\sqrt{m(1+\|\xi\|_{2}^{2})}\omega^{\frac{4}{3}}L^{3}\log(m)\right)$

for all $t\in[n]$ and arbitrary perturbation vector $\xi$ with probability at
least $1-\mathcal{O}(nL)e^{-\Omega\left(m\omega^{\frac{2}{3}}L\right)}$.

######  Lemma 4.

Assume Assumption 1 holds and
$\omega\leq\mathcal{O}\left(L^{-\frac{9}{2}}\log^{-3}(m)\right)$. Then, for
$\mathbb{W}\in\mathcal{B}(\mathbb{W}^{(0)},\omega)$ we have

$\displaystyle\|g_{(t,l,\xi)}-g_{(t,l,\xi)}^{(0)}\|_{2},~{}\|h_{(t,l,\xi)}-h_{(t,l,\xi)}^{(0)}\|_{2}\leq\mathcal{O}\left(\omega
L^{\frac{5}{2}}\sqrt{(1+\|\xi\|_{2}^{2})\log(m)}\right)$

for all $t\in[n]$, $l\in[L-1]$, and arbitrary perturbation vector $\xi$ with
probability at least
$1-\mathcal{O}(nL)e^{-\Omega\left(m\omega^{\frac{2}{3}}L\right)}$.

######  Lemma 5.

Assume Assumption 1 holds and
$\omega\leq\mathcal{O}\left(L^{-6}\log^{-3}(m)\right)$. Then, with probability
at least $1-\mathcal{O}(nL)e^{-\Omega\left(m\omega^{\frac{2}{3}}L\right)}$ we
have for all $l$ such that $l\in[L-1]$ and $t\in[n]$

$\displaystyle\left\|W_{L}^{\prime}\prod\limits_{r=l}^{L-1}\left(D_{(t,r,\xi)}^{\prime}+D_{(t,r)}^{\prime\prime}\right)W_{r}^{\prime}-W_{L}\prod\limits_{r=l}^{L-1}D_{(t,r,\xi)}W_{r}\right\|_{2}\leq\mathcal{O}\left(\omega^{\frac{1}{3}}L^{2}\sqrt{\log(m)}\right)$

where $\mathbb{W},\mathbb{W}^{\prime}\in\mathcal{B}(\mathbb{W}^{(0)},\omega)$,
$D_{i,r}^{\prime\prime}\in[-1,1]^{m\times m}$ is any random diagonal matrix
with at most $\mathcal{O}\left(m\omega^{\frac{2}{3}}L\right)$ non-zero
entries, and $\xi$ is an arbitrary perturbation vector.

######  Lemma 6.

Given Assumption 1, randomly initialized weights $\mathbb{W}^{(0)}$, and
arbitrary perturbation vector $\xi$ we have

$\displaystyle\left\|h_{(t,j,\xi)}^{(0)}\right\|_{2}^{2}\in\left[1-\|\xi\|_{2}^{2},1+\|\xi\|_{2}^{2}\right]$

with probability at least $1-\mathcal{O}\left(nL\right)e^{-\Omega(m/L)}$ for
all $t\in[n]$ and $j\in[L-1]$.

######  Corollary 2.

Given Assumption 1 and assuming
$\omega\leq\mathcal{O}(L^{-\frac{9}{2}}\log^{-3}(m))$, we have for
$\mathbb{W}\in\mathcal{B}(\mathbb{W}^{(0)},\omega)$ and arbitrary perturbation
vector $\xi$

$\displaystyle\|h_{(t,j,\xi)}\|_{2}\leq\mathcal{O}\left(\sqrt{1+\|\xi\|_{2}^{2}}\left(\omega
L^{\frac{5}{2}}\sqrt{\log(m)}+1\right)\right)$

for all $t\in[n]$ and $j\in[L-1]$ with probability at least
$1-\mathcal{O}(nL)e^{-\Omega\left(m\omega^{\frac{2}{3}}L\right)}$.

######  Lemma 7.

Given Assumption 1 and $\omega\leq\mathcal{O}\left(L^{-6}\log^{-3}(m)\right)$,
the following can be shown when
$\mathbb{W}\in\mathcal{B}(\mathbb{W}^{(0)},\omega)$ for arbitrary perturbation
vector $\xi$

$\displaystyle\left\|\nabla_{W_{l}}f_{\mathbb{W}}(x_{t}+\xi)\right\|_{F},\left\|\nabla_{W_{l}}L_{(t,\xi)}(\mathbb{W})\right\|_{F}\leq\mathcal{O}\left(\sqrt{m(1+\|\xi\|_{2}^{2})}\right)$

for all $t\in[n]$ and $l\in[L-1]$ with probability at least
$1-\mathcal{O}(nL)e^{-\Omega\left(m\omega^{\frac{2}{3}}L\right)}$.

##  Appendix E Proofs

Within this section, we provide full proofs for all theoretical results
derived within this work. We begin with an overview of further notation used
within the analysis.

Notation. For some arbitrary set of weight matrices
$\mathbb{W}=\\{W_{1},\dots,W_{L}\\}$, we define $h_{(t,0,\xi)}=x_{t}+\xi$ and
$h_{(t,l,\xi)}=\sigma(W_{l}h_{(t,l-1,\xi)})$ for $l\in[L-1]$ and arbitrary
perturbation vector $\xi$. Similarly, we define $g_{(t,0,\xi)}=x_{t}+\xi$ and
$g_{(t,l,\xi)}=W_{l}h_{(t,l-1,\xi)}$ for $l\in[L-1]$. For the weight matrices
at initialization $\mathbb{W}^{(0)}=\\{W_{1}^{(0)},\dots W_{L}^{(0)}\\}$, we
would similarly define such vectors with the notation $h_{(t,l,\xi)}^{(0)}$
and $g_{(t,l,\xi)}^{(0)}$ (or $h_{(t,l,\xi)}^{\prime}$,
$g_{(t,l,\xi)}^{\prime}$ for weight matrices $\mathbb{W}^{\prime}$ and so on).
We also define
$D_{(t,l,\xi)}=\texttt{diag}(\mathbbm{1}\\{(W_{l}h_{(t,l,\xi)})_{1}>0\\},\dots,\mathbbm{1}\\{(W_{l}h_{(t,l,\xi)})_{m}>0\\})$
for all $t\in[n]$ and $l\in[L-1]$.

###  E.1 Proof of Theorem 1

###### Proof.

For $t\in[n]$ and associated perturbation vectors $\xi_{t}$ for $t\in[n]$, let
$L_{(t,\xi_{t})}^{0-1}(\mathbb{W}^{(t)})=\mathbbm{1}\left\\{y_{t}\cdot
f_{\mathbb{W}^{(t)}}(x_{t}+\xi_{t})<0\right\\}$, where
$L_{(t,\xi_{t})}^{0-1}(\mathbb{W}^{(t)})\leq
4L_{(t,\xi_{t})}(\mathbb{W}^{(t)})$ due to properties of the cross entropy
loss function (i.e., $\mathbbm{1}\\{z\leq 0\\}\leq 4\ell(z)$). With this in
mind, when $m>\mathcal{O}\left(nB\sqrt{1+\Xi}L^{6}\log^{3}(m)\right)$ and
$\omega\leq\mathcal{O}\left(L^{-6}\log^{-3}(m)\right)$, we can invoke Lemma 1
to yield

$\displaystyle\frac{1}{n}\sum\limits_{t=1}^{n}L_{(t,\xi_{t})}^{0-1}(\mathbb{W}^{(t)})\leq\frac{4}{n}\sum\limits_{t=1}^{n}L_{(t,\xi_{t})}(\mathbb{W}^{\star})+\mathcal{O}\left(\frac{LR^{2}}{nm^{\frac{1}{2}}}\right)+\mathcal{O}\left(m^{-\frac{1}{2}}BL(1+\Xi)\right)$

with probability at least
$1-\mathcal{O}(nBL)e^{-\Omega\left(m\omega^{\frac{2}{3}}L\right)}$. Then,
because the model is trained in a streaming fashion as described in Section
5.1, the $t$-th new data example is seen for the first time only at iteration
$t$ within the data stream. Thus, we have that weights $\mathbb{W}^{(t)}$ only
depend on data examples $(x_{1},y_{1}),\dots,(x_{t-1},y_{t-1})$. In other
words, $\mathbb{W}^{(t)}$ is independent of the $t$-th new data example
$(x_{t},y_{t})$. Thus, we can invoke an online-to-batch conversion argument
(see Proposition 1 in (Cesa-Bianchi et al., 2004)) to yield

$\displaystyle\frac{1}{n}\sum\limits_{t=1}^{n}L_{\mathcal{D}}^{0-1}(\mathbb{W}^{(t)})\leq\frac{1}{n}\sum\limits_{t=1}^{n}L_{(t,\xi_{t})}^{0-1}(\mathbb{W}^{(t)})+\sqrt{\frac{2\log(\nicefrac{{1}}{{\delta}})}{n}}$

with probability at least $1-\delta$ for $\delta\in(0,1]$. From here, we
define $\mathbb{\hat{W}}$ as a random entry chosen uniformly from the set
$\\{\mathbb{W}^{(0)},\dots,\mathbb{W}^{(n)}\\}$. Thus, we have the following
by definition

$\displaystyle\frac{1}{n}\sum\limits_{t=1}^{n}L_{\mathcal{D}}^{0-1}(\mathbb{W}^{(t)})=\mathbb{E}\left[L_{\mathcal{D}}^{0-1}(\mathbb{\hat{W}})\right]$

Then, the following can be derived by combining the above expressions

$\begin{split}\mathbb{E}\left[L_{\mathcal{D}}^{0-1}(\mathbb{\hat{W}})\right]&\leq\frac{4}{n}\sum\limits_{t=1}^{n}L_{(t,\xi_{t})}(\mathbb{W}^{\star})+\mathcal{O}\left(\frac{LR^{2}}{nm^{\frac{1}{2}}}\right)\\\
&\quad\quad+\mathcal{O}\left(m^{-\frac{1}{2}}BL(1+\Xi)\right)+\sqrt{\frac{2\log(\frac{1}{\delta})}{n}}\end{split}$
(4)

with probability at least
$1-\delta-\mathcal{O}(nBL)e^{-\Omega\left(m\omega^{\frac{2}{3}}L\right)}$ for
all $\mathbb{W}^{\star}\in\mathcal{B}(\mathbb{W}^{(0)},\nicefrac{{R}}{{m}})$.
Now, we can compare the neural network function $f_{\mathbb{W}^{\star}}$ with
$F_{\mathbb{W}^{(0)},\mathbb{W}^{\star}}$ as follows

$\displaystyle
L_{(t,\xi_{t})}(\mathbb{W}^{\star})\stackrel{{\scriptstyle(i)}}{{\leq}}\ell(y_{t}\cdot
F_{\mathbb{W}^{(0)},\mathbb{W}^{\star}}(x_{t}+\xi_{t}))+\mathcal{O}\left(\sqrt{m\left(1+\Xi\right)}\omega^{\frac{4}{3}}L^{3}\log(m)\right)$

where $(i)$ holds from the 1-Lipschitz continuity of $\ell(\cdot)$ and Lemma 3
with probability at least
$1-\mathcal{O}(nL)e^{-\Omega\left(m\omega^{\frac{2}{3}}L\right)}$. Then, we
can plug this inequality into equation 4 to yield

$\displaystyle\mathbb{E}\left[L_{\mathcal{D}}^{0-1}(\mathbb{\hat{W}})\right]$
$\displaystyle\leq\frac{4}{n}\sum\limits_{t=1}^{n}\ell[y_{t}\cdot
F_{\mathbb{W}^{(0)},\mathbb{W}^{\star}}(x_{t}+\xi_{t})]+\mathcal{O}\left(\sqrt{m\left(1+\Xi\right)}\omega^{\frac{4}{3}}L^{3}\log(m)\right)$
$\displaystyle\quad\quad+\mathcal{O}\left(\frac{LR^{2}}{nm^{\frac{1}{2}}}\right)+\mathcal{O}\left(m^{-\frac{1}{2}}BL(1+\Xi)\right)+\sqrt{\frac{2\log(\frac{1}{\delta})}{n}}$

Then, by taking an infimum over all
$\mathbb{W}^{\star}\in\mathcal{B}(\mathbb{W}^{(0)},\nicefrac{{R}}{{m}})$, we
get the following

$\displaystyle\mathbb{E}\left[L_{\mathcal{D}}^{0-1}\left(\mathbb{\hat{W}}\right)\right]$
$\displaystyle\leq\inf\limits_{f\in\mathcal{F}(\mathbb{W}^{(0)},\nicefrac{{R}}{{m}})}\left(\frac{4}{n}\sum_{t=1}^{n}\ell(y_{t}\cdot
f(x_{t}+\xi_{t}))\right)$
$\displaystyle\quad\quad+\mathcal{O}\left(\sqrt{m\left(1+\Xi\right)}\omega^{\frac{4}{3}}L^{3}\log(m)\right)+\mathcal{O}\left(\frac{LR^{2}}{nm^{\frac{1}{2}}}\right)$
$\displaystyle\quad\quad+\mathcal{O}\left(m^{-\frac{1}{2}}BL(1+\Xi)\right)+\sqrt{\frac{2\log(\nicefrac{{1}}{{\delta}})}{n}}$

From here, by noting that
$\omega\leq\mathcal{O}\left(L^{-6}\log^{-3}(m)\right)$ and
$m\geq\mathcal{O}\left(nB\sqrt{1+\Xi}L^{6}\log^{3}(m)\right)$, the expression
can be simplified as follows

$\begin{split}\mathbb{E}\left[L_{\mathcal{D}}^{0-1}\left(\mathbb{\hat{W}}\right)\right]&\leq\inf\limits_{f\in\mathcal{F}(\mathbb{W}^{(0)},\nicefrac{{R}}{{m}})}\left(\frac{4}{n}\sum_{t=1}^{n}\ell(y_{t}\cdot
f(x_{t}+\xi_{t}))\right)+\sqrt{\frac{2\log(\nicefrac{{1}}{{\delta}})}{n}}\\\
&\quad\quad+{\color[rgb]{0.7578125,0.14453125,0.01953125}\mathcal{O}\Bigg{(}\frac{(1+\Xi)^{\frac{3}{4}}\sqrt{nB}}{L^{2}\log^{\frac{3}{2}}(m)}+\frac{R^{2}}{n^{\frac{3}{2}}B^{\frac{1}{2}}(1+\Xi)^{\frac{1}{4}}L^{2}\log^{\frac{3}{2}}(m)}}\\\
&\quad\quad\quad\quad{\color[rgb]{0.7578125,0.14453125,0.01953125}+\frac{B^{\frac{1}{2}}(1+\Xi)^{\frac{3}{4}}}{n^{\frac{1}{2}}L^{2}\log^{\frac{3}{2}}(m)}\Bigg{)}}\end{split}$
(5)

We then analyze the asymptotic portion of the expression above—highlighted in
red—as follows.

$\displaystyle\mathcal{O}\Bigg{(}\frac{(1+\Xi)^{\frac{3}{4}}\sqrt{nB}}{L^{2}\log^{\frac{3}{2}}(m)}+\frac{R^{2}}{n^{\frac{3}{2}}B^{\frac{1}{2}}(1+\Xi)^{\frac{1}{4}}L^{2}\log^{\frac{3}{2}}(m)}+\frac{B^{\frac{1}{2}}(1+\Xi)^{\frac{3}{4}}}{n^{\frac{1}{2}}L^{2}\log^{\frac{3}{2}}(m)}\Bigg{)}$
$\displaystyle\quad\quad=\mathcal{O}\left(\frac{(1+\Xi)B(n^{2}+1)+R^{2}}{L^{2}\log^{\frac{3}{2}}(m)nB^{\frac{1}{2}}(1+\Xi)^{\frac{1}{4}}}\right)$
$\displaystyle\quad\quad=\mathcal{O}\left(\frac{(1+\Xi)^{\frac{3}{4}}B^{\frac{1}{2}}n}{L^{2}\log^{\frac{3}{2}}(m)}\right)+\mathcal{O}\left(\frac{R^{2}}{L^{2}\log^{\frac{3}{2}}(m)nB^{\frac{1}{2}}(1+\Xi)^{\frac{1}{4}}}\right)$
$\displaystyle\quad\quad\stackrel{{\scriptstyle(i)}}{{\leq}}\mathcal{O}\left(\frac{(1+\Xi)^{\frac{3}{4}}B^{\frac{1}{2}}n+R^{2}}{L^{2}\log^{\frac{3}{2}}(m)}\right)$

where $(i)$ holds due to the fact that
$nB^{\frac{1}{2}}(1+\Xi)^{\frac{1}{4}}>1$. Then, by substituting this
simplified asymptotic expression, we have

$\displaystyle\mathbb{E}\left[L_{\mathcal{D}}^{0-1}\left(\mathbb{\hat{W}}\right)\right]$
$\displaystyle\leq\inf\limits_{f\in\mathcal{F}(\mathbb{W}^{(0)},\nicefrac{{R}}{{m}})}\left(\frac{4}{n}\sum_{t=1}^{n}\ell(y_{t}\cdot
f(x_{t}+\xi_{t})\right)+\sqrt{\frac{2\log(\nicefrac{{1}}{{\delta}})}{n}}+\mathcal{O}\left(\frac{(1+\Xi)^{\frac{3}{4}}B^{\frac{1}{2}}n+R^{2}}{L^{2}\log^{\frac{3}{2}}(m)}\right)$

where the asymptotic portion of the expression can be made arbitrarily small
by increasing the value of $m$. Realizing that this result holds with
probability
$1-\delta-\mathcal{O}(nBL)e^{-\Omega\left(m\omega^{\frac{2}{3}}L\right)}\approx
1-\delta$ as the value of $m$ increases yields the desired result. ∎

###  E.2 Proof of Lemma 1

###### Proof.

We assume $\mathbb{W}^{(0)}$ is initialized as described in Section 5.1, then
updated according to Algorithm 1 with $B$ replay samples taken from buffer
$\mathcal{R}$ at each iteration and distinct, arbitrary data perturbation
vectors—representing data augmentation—applied to both new and replayed data
throughout streaming. For $R>0$, we have
$\mathbb{W}^{\star}\in\mathcal{B}(\mathbb{W}^{(0)},\nicefrac{{R}}{{m}})$,
where $\mathbb{W}^{\star}\in\mathcal{B}(\mathbb{W}^{(0)},\omega)$ whenever
$m\geq\mathcal{O}(L^{6}\log^{3}(m))$ (i.e., $R$ is a constant that does not
appear in the asymptotic bound), which is looser than the overparameterization
requirement within Lemma 2. Similarly, by Lemma 2, we have
$\mathbb{W}^{(0)},\dots,\mathbb{W}^{(n)}\in\mathcal{B}(\mathbb{W}^{(0)},\omega)$
with probability at least
$1-\mathcal{O}(nLB)e^{-\Omega\left(m\omega^{\frac{2}{3}}L\right)}$ whenever
$m\geq\mathcal{O}\left(nB\sqrt{1+\Xi}L^{6}\log^{3}(m)\right)$ and
$\eta=\mathcal{O}(m^{-\frac{3}{2}})$.

Thus, for
$\mathbb{W}^{(t)},\mathbb{W}^{\star}\in\mathcal{B}(\mathbb{W}^{(0)},\omega)$,
by Corollary 1 we have with probability at least
$1-\mathcal{O}(nL)e^{-\Omega\left(m\omega^{\frac{2}{3}}L\right)}$ that

$\begin{split}L_{(t,\xi_{t})}(\mathbb{W}^{(t)})-L_{(t,\xi_{t})}(\mathbb{W}^{\star})&\leq\left\langle\nabla_{\mathbb{W}^{(t)}}L_{(t,\xi_{t})}(\mathbb{W}^{(t)}),\mathbb{W}^{(t)}-\mathbb{W}^{\star}\right\rangle\\\
&\quad\quad+\mathcal{O}\left(\sqrt{m(1+\Xi)}\omega^{\frac{4}{3}}L^{3}\log(m)\right)\\\
&={\color[rgb]{0.7578125,0.14453125,0.01953125}\sum\limits_{l=1}^{L}\left\langle\nabla_{W_{l}^{(t)}}L_{(t,\xi_{t})}(\mathbb{W}^{(t)}),W_{l}^{(t)}-W_{l}^{\star}\right\rangle}\\\
&\quad\quad+\mathcal{O}\left(\sqrt{m(1+\Xi)}\omega^{\frac{4}{3}}L^{3}\log(m)\right)\end{split}$
(6)

We can focus on bounding the red term within the expression above as follows

$\displaystyle\sum\limits_{l=1}^{L}\left\langle\nabla_{W_{l}^{(t)}}L_{(t,\xi_{t})}(\mathbb{W}^{(t)}),W^{(t)}_{l}-W^{\star}_{l}\right\rangle$
$\displaystyle\stackrel{{\scriptstyle
i}}{{=}}\sum\limits_{l=1}^{L}\frac{1}{\eta}\left\langle
W_{l}^{(t)}-W_{l}^{(t+1)}-\eta\sum\limits_{(x_{\text{rep}},y_{\text{rep}})\sim\mathcal{S}_{t}}\nabla_{W_{l}^{(t)}}L_{(x_{\text{rep}},y_{\text{rep}},\xi_{\text{rep}})}(\mathbb{W}^{(t)}),W_{l}^{(t)}-W_{l}^{\star}\right\rangle$
$\displaystyle\stackrel{{\scriptstyle
ii}}{{\leq}}\sum\limits_{l=1}^{L}\frac{1}{2\eta}\Bigg{(}\left\|W_{l}^{(t)}-W_{l}^{(t+1)}-\eta\sum\limits_{(x_{\text{rep}},y_{\text{rep}})\sim\mathcal{S}_{t}}\nabla_{W_{l}^{(t)}}L_{(x_{\text{rep}},y_{\text{rep}},\xi_{\text{rep}})}(\mathbb{W}^{(t)})\right\|_{F}^{2}+\left\|W_{l}^{(t)}-W_{l}^{\star}\right\|_{F}^{2}$
$\displaystyle\quad\quad-\left\|W_{l}^{(t+1)}-W_{l}^{\star}+\eta\sum\limits_{(x_{\text{rep}},y_{\text{rep}})\sim\mathcal{S}_{t}}\nabla_{W_{l}^{(t)}}L_{(x_{\text{rep}},y_{\text{rep}},\xi_{\text{rep}})}(\mathbb{W}^{(t)})\right\|_{F}^{2}\Bigg{)}$
$\displaystyle=\sum\limits_{l=1}^{L}\frac{1}{2\eta}\Bigg{(}\left\|\eta\nabla_{W_{l}^{(t)}}L_{(t,\xi_{t})}(\mathbb{W}^{(t)})\right\|_{F}^{2}+\left\|W_{l}^{(t)}-W_{l}^{\star}\right\|_{F}^{2}$
$\displaystyle\quad\quad-\left\|W_{l}^{(t+1)}-W_{l}^{\star}+\eta\sum\limits_{(x_{\text{rep}},y_{\text{rep}})\sim\mathcal{S}_{t}}\nabla_{W_{l}^{(t)}}L_{(x_{\text{rep}},y_{\text{rep}},\xi_{\text{rep}})}(\mathbb{W}^{(t)})\right\|_{F}^{2}\Bigg{)}$
$\displaystyle\stackrel{{\scriptstyle
iii}}{{\leq}}\sum_{l=1}^{L}\frac{1}{2\eta}\Bigg{(}\left\|\eta\nabla_{W_{l}^{(t)}}L_{(t,\xi_{t})}(\mathbb{W}^{(t)})\right\|_{F}^{2}+\left\|W_{l}^{(t)}-W_{l}^{\star}\right\|_{F}^{2}$
$\displaystyle\quad\quad-\left\|W_{l}^{(t+1)}-W_{l}^{\star}\right\|_{F}^{2}+\left\|\eta\sum\limits_{(x_{\text{rep}},y_{\text{rep}})\sim\mathcal{S}_{t}}\nabla_{W_{l}^{(t)}}L_{(x_{\text{rep}},y_{\text{rep}},\xi_{\text{rep}})}(\mathbb{W}^{(t)})\right\|_{F}^{2}\Bigg{)}$
$\displaystyle\stackrel{{\scriptstyle
iv}}{{\leq}}\sum\limits_{l=1}^{L}\frac{1}{2\eta}\left(\left\|W_{l}^{(t)}-W_{l}^{\star}\right\|_{F}^{2}-\left\|W_{l}^{(t+1)}-W_{l}^{\star}\right\|_{F}^{2}\right)$
$\displaystyle\quad\quad+\mathcal{O}\left(\eta BLm(1+\Xi)\right)$

where $i$ follows from equation 3, $ii$ holds from the identity that $2\langle
A,B\rangle\leq\|A\|_{F}^{2}+\|B\|_{F}^{2}-\|A-B\|_{F}^{2}$, and $iii$ holds
due to the lower triangle inequality, and $iv$ holds due to the upper triangle
inequality and Lemma 7 with probability at least
$1-\mathcal{O}(nBL)e^{-\Omega\left(m\omega^{\frac{2}{3}}L\right)}$ by taking
union bound across all data, replay examples, and network layers. Plugging
this bound into equation 6, we get

$\displaystyle
L_{(t,\xi_{t})}(\mathbb{W}^{(t)})-L_{(t,\xi_{t})}(\mathbb{W}^{\star})$
$\displaystyle\leq\sum\limits_{l=1}^{L}\frac{1}{2\eta}\left(\left\|W_{l}^{(t)}-W_{l}^{\star}\right\|_{F}^{2}-\left\|W_{l}^{(t+1)}-W_{l}^{\star}\right\|_{F}^{2}\right)$
$\displaystyle\quad\quad+\mathcal{O}\left(\eta
BLm(1+\Xi)+\sqrt{m(1+\Xi)}\omega^{\frac{4}{3}}L^{3}\log(m)\right)$

Then, telescoping this expression over $t\in[n]$ yields

$\displaystyle\sum_{t=1}^{n}L_{(t,\xi_{t})}(\mathbb{W}^{(t)})$
$\displaystyle\leq\sum_{t=1}^{n}L_{(t,\xi_{t})}(\mathbb{W}^{\star})+\sum_{l=1}^{L}\frac{\left\|W_{l}^{(0)}-W_{l}^{\star}\right\|_{F}^{2}}{2\eta}$
$\displaystyle\quad\quad+\mathcal{O}\left(n\eta
BLm(1+\Xi)+n\sqrt{m(1+\Xi)}\omega^{\frac{4}{3}}L^{3}\log(m)\right)$
$\displaystyle\stackrel{{\scriptstyle
i}}{{\leq}}\sum_{t=1}^{n}L_{(t,\xi_{t})}(\mathbb{W}^{\star})+\frac{LR^{2}}{2\eta
m^{2}}$ $\displaystyle\quad\quad+\mathcal{O}\left(n\eta
BLm(1+\Xi)+n\sqrt{m(1+\Xi)}\omega^{\frac{4}{3}}L^{3}\log(m)\right)$
$\displaystyle\stackrel{{\scriptstyle
ii}}{{\leq}}\sum_{t=1}^{n}L_{(t,\xi_{t})}(\mathbb{W}^{\star})+\mathcal{O}\left(LR^{2}m^{-\frac{1}{2}}\right)+\mathcal{O}\left(nm^{-\frac{1}{2}}BL(1+\Xi)\right)$

where $i$ follows from the fact that
$\mathbb{W}^{\star}\in\mathcal{B}(\mathbb{W}^{(0)},\nicefrac{{R}}{{m}})$ and
$ii$ holds for sufficiently small $\omega$ with
$\eta=\frac{\kappa}{m^{\frac{3}{2}}}$, where $\kappa$ is a small, positive
constant. Thus, the desired result holds with probability at least
$1-\mathcal{O}(nBL)e^{-\Omega\left(m\omega^{\frac{2}{3}}L\right)}$ with
overparameterization given by the expression below.

$\displaystyle m\geq\mathcal{O}\left(nB\sqrt{1+\Xi}L^{6}\log^{3}(m)\right)$

∎

###  E.3 Proof of Lemma 2

###### Proof.

We assume $\mathbb{W}^{(0)}$ is initialized as described in Section 5.1 and
updated according to Algorithm 1 with $B$ replay examples sampled uniformly
from the replay buffer $\mathcal{R}$ at each update and arbitrary perturbation
vectors—representing data augmentation—applied separately to both new and
replayed data throughout streaming. We take $\omega=C_{1}L^{-6}\log^{-3}(m)$
such that $C_{1}$ is a small enough constant to satisfy assumptions on
$\omega$ in Lemma 7. From here, we can show that
$\mathbb{W}^{(0)},\dots,\mathbb{W}^{(n)}\in\mathcal{B}(\mathbb{W}^{(0)},\omega)$
through induction.

Base Case. The base case
$\mathbb{W}^{(0)}\in\mathcal{B}(\mathbb{W}^{(0)},\omega)$ holds trivially.

Inductive Case. Assume that
$\mathbb{W}^{(t)}\in\mathcal{B}(\mathbb{W}^{(0)},\omega)$. By Lemma 7, we have

$\displaystyle\left\|\nabla_{W_{l}}L_{(t,\xi_{t})}(\mathbb{W})\right\|_{F}\leq\mathcal{O}\left(\sqrt{m(1+\|\xi_{t}\|_{2}^{2})}\right)$
(7)

with probability at least $1-e^{-\Omega\left(m\omega^{\frac{2}{3}}L\right)}$.
Denoting the indices of data elements within our replay buffer as
$\mathcal{R}$, we can then show the following over iterations of Algorithm 1.

$\displaystyle\left\|W_{l}^{(t+1)}-W_{l}^{(0)}\right\|_{F}$
$\displaystyle\stackrel{{\scriptstyle
i}}{{\leq}}\sum\limits_{j=1}^{t}\left\|W_{l}^{(j+1)}-W_{l}^{(j)}\right\|_{F}$
$\displaystyle\stackrel{{\scriptstyle
ii}}{{=}}\sum\limits_{j=1}^{t}\left\|-\eta\left(\sum\limits_{(x_{\text{rep}},y_{\text{rep}})\sim\mathcal{S}_{t}}\nabla_{W_{l}}L_{(x_{\text{rep}},y_{\text{rep}},\xi_{\text{rep}})}\left(\mathbb{W}^{(j)}\right)+\nabla_{W_{l}}L_{(j,\xi_{j})}\left(\mathbb{W}^{(j)}\right)\right)\right\|_{F}$
$\displaystyle\stackrel{{\scriptstyle
iii}}{{\leq}}\eta\sum\limits_{j=1}^{t}\left(\sum\limits(x_{\text{rep}},y_{\text{rep}})\sim\mathcal{S}_{t}\left\|\nabla_{W_{l}}L_{(x_{\text{rep}},y_{\text{rep}},\xi_{\text{rep}})}\left(\mathbb{W}^{(j)}\right)\right\|+\left\|\nabla_{W_{l}}L_{(j,\xi_{j})}\left(\mathbb{W}^{(j)}\right)\right\|\right)$
$\displaystyle\stackrel{{\scriptstyle iv}}{{\leq}}\mathcal{O}\left(\eta
nB\left(\sqrt{m\left(1+\Xi\right)}\right)\right)$

where $i$ and $iii$ hold due to the upper triangle inequality, $ii$ holds from
equation 3, and $iv$ holds due to equation 7 and the definition of $\Xi$.
Thus, for $\omega=C_{1}L^{-6}\log^{-3}(m)$, if we set
$\eta=\frac{\kappa}{m^{\frac{3}{2}}}$ we have

$\displaystyle\left\|W_{l}^{(t+1)}-W_{l}^{(0)}\right\|_{F}$
$\displaystyle\leq\mathcal{O}\left(\eta nB\sqrt{m\left(1+\Xi\right)}\right)$
$\displaystyle=\frac{\kappa nB\sqrt{1+\Xi}}{\sqrt{m}}\stackrel{{\scriptstyle
i}}{{\leq}}\omega$

for some small enough absolute constant $\kappa$ and
$m\geq\mathcal{O}\left(nB\sqrt{1+\Xi}L^{6}\log^{3}(m)\right)$. Thus, the
inductive step is complete and we have
$\mathbb{W}^{(0)},\dots,\mathbb{W}^{(n)}\in\mathcal{B}(\mathbb{W}^{(0)},\omega)$
with probability at least
$1-\mathcal{O}(nLB)e^{-\Omega\left(m\omega^{\frac{2}{3}}L\right)}$ by taking a
union bound over all data examples, replay examples, and network layers. ∎

###  E.4 Proof of Lemma 3

###### Proof.

We consider some fixed $t\in[n]$ with perturbation vector $\xi$ and two weight
matrices
$\mathbb{W},\mathbb{W}^{\prime}\in\mathcal{B}(\mathbb{W}^{(0)},\omega)$, where
$\mathbb{W}^{(0)}$ is initialized as described in Section 3.1. It should be
noted that $\xi$ is an arbitrary perturbation vector that can be different for
any $t\in[n]$. We omit the subscript $\xi_{t}$ to emphasize that the result
can hold with different perturbations for any $t\in[n]$ and both when data is
encountered newly or used for replay. In particular, the result only depends
on the value of $\|\xi\|_{2}^{2}$, thus allowing arbitrary settings of $\xi$
to be used for new or replayed data. From the formulation of the forward pass
in equation 1, it can be shown that
$f_{\mathbb{W}^{\prime}}(x_{t}+\xi)=\sqrt{m}\cdot
W_{L}^{\prime}h_{(t,L-1,\xi)}^{\prime}$ and
$f_{\mathbb{W}}(x_{t}+\xi)=\sqrt{m}\cdot W_{L}h_{(t,L-1,\xi)}$. These
identities allow us to derive the following via direct calculation

$\begin{split}&f_{\mathbb{W}^{\prime}}(x_{t}+\xi)-F_{\mathbb{W},\mathbb{W}^{\prime}}(x_{t}+\xi)\\\
&=-\sqrt{m}\cdot\sum\limits_{l=1}^{L-1}W_{L}\left(\prod\limits_{r=l+1}^{L-1}D_{(t,r,\xi)}W_{r}\right)D_{(t,l,\xi)}\left(W_{l}^{\prime}-W_{l}\right)h_{(t,l-1,\xi)}\\\
&\quad\quad+\sqrt{m}\cdot
W_{L}^{\prime}{\color[rgb]{0.7578125,0.14453125,0.01953125}\left(h_{(t,L-1,\xi)}^{\prime}-h_{(t,L-1,\xi)}\right)}\end{split}$
(8)

Then, from Claim in 11.2 in (Allen-Zhu et al., 2019), it is known that, for
all $t\in[n]$, $h_{(t,L-1,\xi)}-h_{(t,L-1,\xi)}^{\prime}$ (i.e., the red term
within the above expression) can be re-written as

$\displaystyle h_{(t,L-1,\xi)}-h_{(t,L-1,\xi)}^{\prime}$
$\displaystyle=\sum\limits_{l=1}^{L-1}\left(\prod\limits_{r=l+1}^{L-1}\left(D_{(t,r,\xi)}^{\prime}+D_{(t,r)}^{{}^{\prime\prime}}\right)W_{r}^{\prime}\right)\left(D_{(t,l,\xi)}^{\prime}+D_{(t,l)}^{{}^{\prime\prime}}\right)\left(W_{l}-W_{l}^{\prime}\right)h_{(t,l-1,\xi)}$

where $D_{(t,l)}^{{}^{\prime\prime}}\in\mathbb{R}^{m\times m}$ for $l\in[L-1]$
is any random diagonal matrix with at most
$\mathcal{O}\left(m\omega^{\frac{2}{3}}L\right)$ non-zero entries in the range
$[-1,1]$. With this in mind, we can then rewrite equation 8 as follows.

$\displaystyle
f_{\mathbb{W}^{\prime}}(x_{t}+\xi)-F_{\mathbb{W},\mathbb{W}^{\prime}}(x_{t}+\xi)$
$\displaystyle=\sqrt{m}\cdot\sum\limits_{l=1}^{L-1}W_{L}^{\prime}\left(\prod\limits_{r=l+1}^{L-1}\left(D_{(t,r,\xi)}^{\prime}+D_{(t,r)}^{{}^{\prime\prime}}\right)W_{r}^{\prime}\right)\left(D_{(t,l,\xi)}^{\prime}+D_{(t,l)}^{{}^{\prime\prime}}\right)\left(W_{l}-W_{l}^{\prime}\right)h_{(t,l-1,\xi)}$
$\displaystyle\quad\quad-\sqrt{m}\cdot\sum\limits_{l=1}^{L-1}W_{L}\left(\prod\limits_{r=l+1}^{L-1}D_{(t,r,\xi)}W_{r}\right)D_{(t,l,\xi)}\left(W_{l}^{\prime}-W_{l}\right)h_{(t,l-1,\xi)}$

Now, given that $\omega\leq\mathcal{O}\left(L^{-6}\log^{-3}(m)\right)$, we can
unroll this expression to arrive at the final result as follows

$\displaystyle\left|f_{\mathbb{W}^{\prime}}(x_{t}+\xi)-F_{\mathbb{W},\mathbb{W}^{\prime}}(x_{t}+\xi)\right|$
$\displaystyle=\sqrt{m}\cdot\Bigg{|}\sum\limits_{l=1}^{L-1}\left(W_{L}^{\prime}\left(\prod\limits_{r=l+1}^{L-1}\left(D_{(t,r,\xi)}^{\prime}+D_{(t,r)}^{{}^{\prime\prime}}\right)W_{r}^{\prime}\right)\left(D_{(t,l,\xi)}^{\prime}+D_{(t,l)}^{{}^{\prime\prime}}\right)\left(W_{l}-W_{l}^{\prime}\right)h_{(t,l-1,\xi)}\right)$
$\displaystyle\quad\quad-\left(W_{L}\left(\prod\limits_{r=l+1}^{L-1}D_{(t,r,\xi)}W_{r}\right)D_{(t,l,\xi)}\left(W_{l}^{\prime}-W_{l}\right)h_{(t,l-1,\xi)}\right)\Bigg{|}$
$\displaystyle\stackrel{{\scriptstyle
i}}{{\leq}}\sqrt{m}\cdot\sum\limits_{l=1}^{L-1}\Bigg{\|}\Bigg{(}W_{L}^{\prime}\left(\prod\limits_{r=l+1}^{L-1}\left(D_{(t,r,\xi)}^{\prime}+D_{(t,r)}^{{}^{\prime\prime}}\right)W_{r}^{\prime}\right)\left(D_{(t,l,\xi)}^{\prime}+D_{(t,l)}^{{}^{\prime\prime}}\right)$
$\displaystyle\quad\quad+W_{L}\left(\prod\limits_{r=l+1}^{L-1}D_{(t,r,\xi)}W_{r}\right)D_{(t,l,\xi)}\Bigg{\|}_{2}\cdot\|W_{l}-W_{l}^{\prime}\|_{2}\cdot\|h_{(t,l-1,\xi)}\|_{2}$
$\displaystyle\stackrel{{\scriptstyle
ii}}{{\leq}}\mathcal{O}\left(\sqrt{m}\omega^{\frac{1}{3}}L^{2}\log(m)\right)\sum\limits_{l=1}^{L-1}\|W_{l}-W_{l}^{\prime}\|_{2}\cdot\|h_{(t,l-1,\xi)}\|_{2}$
$\displaystyle\stackrel{{\scriptstyle
iii}}{{\leq}}\mathcal{O}\left(\sqrt{m\left(1+\|\xi\|_{2}^{2}\right)}\omega^{\frac{1}{3}}L^{2}\log(m)\left(\omega
L^{\frac{5}{2}}\sqrt{\log(m)}+1\right)\right)\sum\limits_{l=1}^{L-1}\|W_{l}-W_{l}^{\prime}\|_{2}$
$\displaystyle\stackrel{{\scriptstyle
iv}}{{\leq}}\mathcal{O}\left(\sqrt{m\left(1+\|\xi\|_{2}^{2}\right)}\omega^{\frac{1}{3}}L^{2}\log(m)\left(\omega
L^{\frac{5}{2}}\sqrt{\log(m)}+1\right)(\omega L)\right)$
$\displaystyle\stackrel{{\scriptstyle
v}}{{\leq}}\mathcal{O}\left(\sqrt{m\left(1+\|\xi\|_{2}^{2}\right)}\omega^{\frac{4}{3}}L^{3}\log(m)\right)$

where $i$ holds due to triangle inequality, $ii$ holds due to Lemma 5 with
probability at least
$1-\mathcal{O}(nL)e^{-\Omega\left(m\omega^{\frac{2}{3}}L\right)}$, $iii$ holds
due to Corollary 2 with probability at least
$1-\mathcal{O}(nL)e^{-\Omega\left(m\omega^{\frac{2}{3}}L\right)}$, $iv$ holds
due to the definition of the $\omega$ neighborhood, and $v$ holds for
sufficiently small $\omega$. ∎

###  E.5 Proof of Corollary 1

###### Proof.

Consider some fixed $t\in[n]$ and arbitrary perturbation vector $\xi$, where
we again omit the subscript $\xi_{t}$ to emphasize that the result holds with
different perturbations for any $t\in[n]$ and both when data is encountered
newly or sampled for replay. We consider
$\mathbb{W},\mathbb{W}^{\prime}\in\mathcal{B}(\mathbb{W}^{(0)},\omega)$, where
$\mathbb{W}^{(0)}$ is initialized as described within Section 5.1. Recall that
we utilize a standard cross-entropy loss function $\ell(z)=\log(1+e^{-z})$. We
denote the derivative of this function as $\ell^{\prime}(z)$, where
$\ell^{\prime}(z)=\frac{d}{dz}\log(1+e^{-z})=\frac{-1}{e^{z}+1}$. For
$\mathbb{W},\mathbb{W}^{\prime}\in\mathcal{B}(\mathbb{W}^{(0)},\omega)$, we
can derive the following

$\displaystyle L_{(t,\xi)}(\mathbb{W}^{\prime})-L_{(t,\xi)}(\mathbb{W})$
$\displaystyle=\ell\left(y_{t}f_{\mathbb{W}^{\prime}}(x_{t}+\xi)\right)-\ell\left(y_{t}f_{\mathbb{W}}(x_{t}+\xi)\right)$
$\displaystyle\stackrel{{\scriptstyle
i}}{{\geq}}\ell^{\prime}\left(y_{t}f_{\mathbb{W}}(x_{t}+\xi)\right)\cdot
y_{t}\cdot\left(f_{\mathbb{W}^{\prime}}(x_{t}+\xi)-f_{\mathbb{W}}(x_{t}+\xi)\right)$

where $i$ holds due to the convexity of $\ell(\cdot)$. From here, we have

$\displaystyle\ell^{\prime}\left(y_{t}f_{\mathbb{W}}(x_{t}+\xi)\right)\cdot
y_{t}\cdot\left(f_{\mathbb{W}^{\prime}}(x_{t}+\xi)-f_{\mathbb{W}}(x_{t}+\xi)\right)$
$\displaystyle=\ell^{\prime}(y_{t}f_{\mathbb{W}}(x_{t}+\xi))\cdot
y_{t}\cdot\Big{(}f_{\mathbb{W}^{\prime}}(x_{t}+\xi)-f_{\mathbb{W}}(x_{t}+\xi)$
$\displaystyle\quad\quad\pm\left\langle\nabla_{\mathbb{W}}f_{\mathbb{W}}(x_{t}+\xi),\mathbb{W}^{\prime}-\mathbb{W}\right\rangle\Big{)}$
$\displaystyle=\ell^{\prime}\left(y_{t}f_{\mathbb{W}}(x_{t}+\xi)\right)\cdot
y_{t}\cdot\left\langle\nabla_{\mathbb{W}}f_{\mathbb{W}}(x_{t}+\xi),\mathbb{W}^{\prime}-\mathbb{W}\right\rangle$
$\displaystyle\quad\quad+\ell^{\prime}\left(y_{t}f_{\mathbb{W}}(x_{t}+\xi)\right)\cdot
y_{t}\cdot\Big{(}f_{\mathbb{W}^{\prime}}(x_{t}+\xi)-f_{\mathbb{W}}(x_{t}+\xi)$
$\displaystyle\quad\quad-\left\langle\nabla_{\mathbb{W}}f_{\mathbb{W}}(x_{t}+\xi),\mathbb{W}^{\prime}-\mathbb{W}\right\rangle\Big{)}$
$\displaystyle\geq\ell^{\prime}\left(y_{t}f_{\mathbb{W}}(x_{t}+\xi)\right)\cdot
y_{t}\cdot\left\langle\nabla_{\mathbb{W}}f_{\mathbb{W}}(x_{t}+\xi),\mathbb{W}^{\prime}-\mathbb{W}\right\rangle$
$\displaystyle\quad\quad-\Big{|}\ell^{\prime}\left(y_{t}f_{\mathbb{W}}(x_{t}+\xi)\right)\cdot
y_{t}\cdot\Big{(}f_{\mathbb{W}^{\prime}}(x_{t}+\xi)-f_{\mathbb{W}}(x_{t}+\xi)$
$\displaystyle\quad\quad-\left\langle\nabla_{\mathbb{W}}f_{\mathbb{W}}(x_{t}+\xi),\mathbb{W}^{\prime}-\mathbb{W}\right\rangle\Big{)}\Big{|}$
$\displaystyle=\sum\limits_{l=1}^{L}\langle\nabla_{W_{l}}L_{(t,\xi)}(\mathbb{W}),W_{l}^{\prime}-W_{l}\rangle-\Big{|}\ell^{\prime}\left(y_{t}f_{\mathbb{W}}(x_{t}+\xi)\right)\cdot
y_{t}$
$\displaystyle\quad\quad\cdot\Big{(}f_{\mathbb{W}^{\prime}}(x_{t}+\xi)-f_{\mathbb{W}}(x_{t}+\xi)-\left\langle\nabla_{\mathbb{W}}f_{\mathbb{W}}(x_{t}+\xi),\mathbb{W}^{\prime}-\mathbb{W}\right\rangle\Big{)}\Big{|}$

Then, by noticing that $|\ell^{\prime}(y_{t}f_{\mathbb{W}}(x_{t}+\xi))\cdot
y_{t})|\leq 1$ and invoking Lemma 3, we can derive the following with
probability at least
$1-\mathcal{O}(nL)e^{-\Omega\left(m\omega^{\frac{2}{3}}L\right)}$

$\displaystyle L_{(t,\xi)}(\mathbb{W}^{\prime})-L_{(t,\xi)}(\mathbb{W})$
$\displaystyle\geq\sum\limits_{l=1}^{L}\langle\nabla_{W_{l}}L_{(t,\xi)}(\mathbb{W}),W_{l}^{\prime}-W_{l}\rangle-\mathcal{O}\left(\sqrt{m(1+\|\xi\|_{2}^{2})}\omega^{\frac{4}{3}}L^{3}\log(m)\right)$

whenever $\omega\leq\mathcal{O}\left(L^{-6}\log^{-3}(m)\right)$.

∎

###  E.6 Proof of Lemma 4

###### Proof.

Consider some $t\in[n]$ and arbitrary perturbation vector $\xi$, where we omit
the subscript $\xi_{t}$ to emphasize that the result holds with different
perturbations for any $t\in[n]$ and both when data is newly encountered or
sampled for replay. Consider random weight matrices $\mathbb{W}^{(0)}$
initialized as in Section 5.1, and $\mathbb{W}$ such that
$\mathbb{W}\in\mathcal{B}(\mathbb{W}^{(0)},\omega)$.

From Lemma 6, we have with probability at least
$1-\mathcal{O}\left(nL\right)e^{-\Omega(m/L)}$ that
$\|h_{(t,j,\xi)}^{(0)}\|_{2}^{2},\|g_{(t,j,\xi)}^{(0)}\|_{2}^{2}\in\left[1-\|\xi\|_{2}^{2},1+\|\xi\|_{2}^{2}\right]$.
Furthermore, if $m\geq\Omega(nL\log(nL))$, we have that for all $i\in[n]$ and
all $1\leq a\leq b\leq L$

$\displaystyle\left\|\prod\limits_{l=a}^{b}W_{l}^{(0)}D_{(t,l-1,\xi)}^{(0)}\right\|_{2}\leq\mathcal{O}(\sqrt{L})$
(9)

with probability at least $1-e^{-\Omega(\nicefrac{{m}}{{L}})}$ by Lemma 7.3 in
(Allen-Zhu et al., 2019).171717equation 9 has one extra factor of
$D_{(t,l-1,\xi)}^{(0)}$ within the expression in comparison to Lemma 7.3 in
(Allen-Zhu et al., 2019), but this does not impact the norm of the overall
expression because $\left\|D_{l-1}^{(0)}\right\|_{2}\leq 1$. Now, we can prove
the desired result with an induction argument over layers of the network.

Base Case.
$\|g_{(t,0,\xi)}-g_{(t,0,\xi)}^{(0)}\|_{2}=\|x_{t}+\xi-(x_{t}+\xi)\|_{2}=0$,
so the base case trivially holds. The same is true for
$\|h_{(t,0,\xi)}-h_{(t,0,\xi)}^{(0)}\|_{2}$.

Inductive Case. Assume the inductive hypothesis holds for $l-1$. We can derive
the following

$\displaystyle g_{(t,l,\xi)}-g_{(t,l,\xi)}^{(0)}$
$\displaystyle=\left(W_{l}^{(0)}+W_{l}-W_{l}^{(0)}\right)\left(D_{(t,l-1,\xi)}^{(0)}+D_{(t,l-1,\xi)}-D_{(t,l-1,\xi)}^{(0)}\right)\left(g_{(t,l-1,\xi)}^{(0)}+g_{(t,l-1,\xi)}-g_{(t,l-1,\xi)}^{(0)}\right)$
$\displaystyle\quad\quad-
W_{l}^{(0)}D_{(t,l-1,\xi)}^{(0)}g_{(t,l-1,\xi)}^{(0)}$
$\displaystyle=\left(W_{l}-W_{l}^{(0)}\right)\left(D_{(t,l-1,\xi)}^{(0)}+D_{(t,l-1,\xi)}-D_{(t,l-1,\xi)}^{(0)}\right)\left(g_{(t,l-1,\xi)}^{(0)}+g_{(t,l-1,\xi)}-g_{(t,l-1,\xi)}^{(0)}\right)$
$\displaystyle\quad\quad+W_{l}^{(0)}\left(D_{(t,l-1,\xi)}-D_{(t,l-1,\xi)}^{(0)}\right)\left(g_{(t,l-1,\xi)}^{(0)}+g_{(t,l-1,\xi)}-g_{(t,l-1,\xi)}^{(0)}\right)$
$\displaystyle\quad\quad+W_{l}^{(0)}D_{(t,l-1,\xi)}^{(0)}\left(g_{(t,l-1,\xi)}-g_{(t,l-1,\xi)}^{(0)}\right)$

From here, we can telescope over the $g_{(t,l,\xi)}-g_{(t,l,\xi)}^{(0)}$ terms
to obtain the expression below, where distinct terms of interest are
highlighted with separate colors

$\begin{split}g_{(t,l,\xi)}-g_{(t,l,\xi)}^{(0)}&=\sum\limits_{a=1}^{l}\left(\prod\limits_{b=l}^{a+1}W_{b}^{(0)}D_{(t,b-1,\xi)}^{(0)}\right)\Bigg{(}\\\
&\quad\quad{\color[rgb]{0.23046875,0.73046875,0.03125}\left(W_{a}-W_{a}^{(0)}\right)\left(D_{(t,a-1,\xi)}^{(0)}+D_{(t,a-1,\xi)}-D_{(t,a-1,\xi)}^{(0)}\right)\left(g_{(t,a-1,\xi)}^{(0)}+g_{(t,a-1,\xi)}-g_{(t,a-1,\xi)}^{(0)}\right)}\\\
&\quad\quad+{\color[rgb]{0.7578125,0.14453125,0.01953125}W_{a}^{(0)}\left(D_{(t,a-1,\xi)}-D_{(t,a-1,\xi)}^{(0)}\right)\left(g_{(t,a-1,\xi)}^{(0)}+g_{(t,a-1,\xi)}-g_{(t,a-1,\xi)}^{(0)}\right)}\Bigg{)}\end{split}$
(10)

Now, we focus on a single summation element of the green term in equation 10
and provide an upper bound on the norm of this expression.

$\displaystyle\Bigg{\|}\left(\prod\limits_{b=l}^{a+1}W_{b}^{(0)}D_{(t,b-1,\xi)}^{(0)}\right)\left(W_{a}-W_{a}^{(0)}\right)\left(D_{(t,a-1,\xi)}^{(0)}+D_{(t,a-1,\xi)}-D_{(t,a-1,\xi)}^{(0)}\right)$
$\displaystyle\quad\quad\left(g_{(t,a-1,\xi)}^{(0)}+g_{(t,a-1,\xi)}-g_{(t,a-1,\xi)}^{(0)}\right)\Bigg{\|}_{2}$
$\displaystyle\leq\left\|\prod\limits_{b=l}^{a+1}W_{b}^{(0)}D_{(t,b-1,\xi)}^{(0)}\right\|_{2}\cdot\left\|W_{a}-W_{a}^{(0)}\right\|_{2}\cdot\left\|D_{(t,a-1,\xi)}\right\|_{2}\cdot\left\|g_{(t,a-1,\xi)}^{(0)}+g_{(t,a-1,\xi)}-g_{(t,a-1,\xi)}^{(0)}\right\|_{2}$
$\displaystyle\stackrel{{\scriptstyle
i}}{{\leq}}\mathcal{O}\left(\sqrt{L}\right)\cdot\left\|W_{a}-W_{a}^{(0)}\right\|_{2}\cdot\left\|D_{(t,a-1,\xi)}\right\|_{2}\cdot\left\|g_{(t,a-1,\xi)}^{(0)}+g_{(t,a-1,\xi)}-g_{(t,a-1,\xi)}^{(0)}\right\|_{2}$
$\displaystyle\stackrel{{\scriptstyle
ii}}{{\leq}}\mathcal{O}\left(\sqrt{L}\omega\right)\cdot\left\|D_{(t,a-1,\xi)}\right\|_{2}\cdot\left\|g_{(t,a-1,\xi)}^{(0)}+g_{(t,a-1,\xi)}-g_{(t,a-1,\xi)}^{(0)}\right\|_{2}$
$\displaystyle\stackrel{{\scriptstyle
iii}}{{\leq}}\mathcal{O}\left(\sqrt{L}\omega\right)\cdot\left\|g_{(t,a-1,\xi)}^{(0)}+g_{(t,a-1,\xi)}-g_{(t,a-1,\xi)}^{(0)}\right\|_{2}$
$\displaystyle\stackrel{{\scriptstyle
iv}}{{\leq}}\mathcal{O}\left(\sqrt{L}\omega\right)\left[\|g_{(t,a-1,\xi)}^{(0)}\|_{2}+\|g_{(t,a-1,\xi)}-g_{(t,a-1,\xi)}^{(0)}\|_{2}\right]$
$\displaystyle\stackrel{{\scriptstyle
v}}{{\leq}}\mathcal{O}\left(\sqrt{L}\omega\right)\left[\sqrt{1+\|\xi\|_{2}^{2}}+\mathcal{O}\left(\omega
L^{\frac{5}{2}}\sqrt{(1+\|\xi\|_{2}^{2})\log(m)}\right)\right]$

where $i$ holds due to equation 9, $ii$ holds because
$\mathbb{W}\in\mathcal{B}(\mathbb{W}^{(0)},\omega)$, $iii$ holds because
$\|D_{i,a-1}\|_{2}\leq 1$ by construction, $iv$ holds by upper triangle
inequality, and $v$ holds by Lemma 6 and the inductive hypothesis.

Now that we have bounded the green term, we can focus on a single summation
element of the red term in equation 10. First, we make the following
definition

$\displaystyle\zeta$
$\displaystyle\triangleq\left(D_{(t,a-1,\xi)}-D_{(t,a-1,\xi)}^{(0)}\right)\left(g_{(t,a-1,\xi)}^{(0)}+g_{(t,a-1,\xi)}-g_{(t,a-1,\xi)}^{(0)}\right)$
$\displaystyle=\left(D_{(t,a-1,\xi)}-D_{(t,a-1,\xi)}^{(0)}\right)\left(W_{a-1}^{(0)}h_{(t,a-2,\xi)}^{(0)}+g_{(t,a-1,\xi)}-g_{(t,a-1,\xi)}^{(0)}\right)$

Then, by Claim 8.3 and Corollary 8.4 in (Allen-Zhu et al., 2019), we have that
with probability at least $1-e^{-\Omega(m\omega^{\frac{2}{3}}L)}$

$\displaystyle\left\|\frac{1}{c}\zeta\right\|_{0}\leq\mathcal{O}\left(m\omega^{\frac{2}{3}}L\right)~{}~{}\text{and}~{}~{}\left\|\frac{1}{c}\zeta\right\|_{2}\leq\mathcal{O}\left(\omega
L^{\frac{3}{2}}\right)$ (11)

where
$c=\|h_{(t,a-2,\xi)}^{(0)}\|_{2}\in[\sqrt{1-\|\xi\|_{2}^{2}},\sqrt{1+\|\xi\|_{2}^{2}}]$.
Additionally, we define

$\displaystyle\gamma$
$\displaystyle\triangleq\left(\prod\limits_{b=l}^{a+1}W_{b}^{(0)}D_{(t,b-1,\xi)}\right)\cdot
W_{a}^{(0)}\cdot\left[\left(D_{(t,a-1,\xi)}-D_{(t,a-1,\xi)}^{(0)}\right)\left(g_{(t,a-1,\xi)}^{(0)}+g_{(t,a-1,\xi)}-g_{(t,a-1,\xi)}^{(0)}\right)\right]$
$\displaystyle=c\left(\prod\limits_{b=l}^{a+1}W_{b}^{(0)}D_{(t,b-1,\xi)}\right)\cdot
W_{a}^{(0)}\cdot\left[\frac{1}{c}\zeta\right]$

By invoking Claim 8.5 from (Allen-Zhu et al., 2019), we can reformulate
$\gamma$ as

$\displaystyle\gamma=\left(c\left\|\frac{1}{c}\zeta\right\|_{2}\right)(\gamma_{1}+\gamma_{2})$

where with probability at least $1-e^{-\Omega(m\omega^{\frac{2}{3}}L\log(m))}$
the $\gamma_{1}$ and $\gamma_{2}$ terms can be bounded as

$\displaystyle\|\gamma_{1}\|_{2}\leq\mathcal{O}\left(L^{\frac{1}{2}}\omega^{\frac{1}{3}}\log(m)\right)~{}~{}\text{and}~{}~{}\|\gamma_{2}\|_{\infty}\leq\mathcal{O}\left(\sqrt{\frac{\log(m)}{m}}\right)$
(12)

Combining all of this together, we get

$\displaystyle\|g_{(t,l,\xi)}-g_{(t,l,\xi)}^{(0)}\|_{2}$
$\displaystyle=\Bigg{\|}\sum\limits^{l}\Bigg{(}\mathcal{O}\left(\sqrt{L}\omega\right)\left[\sqrt{1+\|\xi\|_{2}^{2}}+\mathcal{O}\left(\omega
L^{\frac{5}{2}}\sqrt{(1+\|\xi\|_{2}^{2})\log(m)}\right)\right]$
$\displaystyle\quad\quad+\left(c\left\|\frac{1}{c}\zeta\right\|_{2}\right)(\gamma_{1}+\gamma_{2})\Bigg{)}\Bigg{\|}_{2}$
$\displaystyle=\Bigg{\|}L\Bigg{(}\mathcal{O}\left(\sqrt{L}\omega\right)\left[\sqrt{1+\|\xi\|_{2}^{2}}+\mathcal{O}\left(\omega
L^{\frac{5}{2}}\sqrt{(1+\|\xi\|_{2}^{2})\log(m)}\right)\right]$
$\displaystyle\quad\quad+\left(c\left\|\frac{1}{c}\zeta\right\|_{2}\right)(\gamma_{1}+\gamma_{2})\Bigg{)}\Bigg{\|}_{2}$
$\displaystyle\stackrel{{\scriptstyle
i}}{{\leq}}\mathcal{O}\left(L^{\frac{3}{2}}\omega\right)\left[\sqrt{1+\|\xi\|_{2}^{2}}+\mathcal{O}\left(\omega
L^{\frac{5}{2}}\sqrt{(1+\|\xi\|_{2}^{2})\log(m)}\right)\right]$
$\displaystyle\quad\quad+L\left(c\left\|\frac{1}{c}\zeta\right\|_{2}\right)\left\|\gamma_{1}+\gamma_{2}\right\|_{2}$
$\displaystyle\stackrel{{\scriptstyle
ii}}{{\leq}}\mathcal{O}\left(L^{\frac{3}{2}}\omega\right)\left[\sqrt{1+\|\xi\|_{2}^{2}}+\mathcal{O}\left(\omega
L^{\frac{5}{2}}\sqrt{(1+\|\xi\|_{2}^{2})\log(m)}\right)\right]$
$\displaystyle\quad\quad+\left(\sqrt{1+\|\xi\|_{2}^{2}}~{}\mathcal{O}\left(\omega
L^{\frac{5}{2}}\right)\right)\left\|\gamma_{1}+\gamma_{2}\right\|_{2}$
$\displaystyle\stackrel{{\scriptstyle
iii}}{{\leq}}\mathcal{O}\left(L^{\frac{3}{2}}\omega\right)\left[\sqrt{1+\|\xi\|_{2}^{2}}+\mathcal{O}\left(\omega
L^{\frac{5}{2}}\sqrt{(1+\|\xi\|_{2}^{2})\log(m)}\right)\right]$
$\displaystyle\quad\quad+\left(\sqrt{1+\|\xi\|_{2}^{2}}~{}\mathcal{O}\left(\omega
L^{\frac{5}{2}}\right)\right)\left(\|\gamma_{1}\|_{2}+\|\gamma_{2}\|_{2}\right)$
$\displaystyle\stackrel{{\scriptstyle
iv}}{{\leq}}\mathcal{O}\left(L^{\frac{3}{2}}\omega\right)\left[\sqrt{1+\|\xi\|_{2}^{2}}+\mathcal{O}\left(\omega
L^{\frac{5}{2}}\sqrt{(1+\|\xi\|_{2}^{2})\log(m)}\right)\right]$
$\displaystyle\quad\quad+\left(\sqrt{1+\|\xi\|_{2}^{2}}~{}\mathcal{O}\left(\omega
L^{\frac{5}{2}}\right)\right)\left(\mathcal{O}\left(L^{\frac{1}{2}}\omega^{\frac{1}{3}}\log(m)\right)+\mathcal{O}\left(\sqrt{\log(m)}\right)\right)$
$\displaystyle=\mathcal{O}\left(L^{\frac{3}{2}}\omega\sqrt{1+\|\xi\|_{2}^{2}}\right)+\mathcal{O}\left(\omega^{2}L^{4}\sqrt{(1+\|\xi\|_{2}^{2})\log(m)}\right)$
$\displaystyle\quad\quad\mathcal{O}\left(\omega^{\frac{4}{3}}L^{3}\sqrt{1+\|\xi\|_{2}^{2}}\log(m)\right)+\mathcal{O}\left(\omega
L^{\frac{5}{2}}\sqrt{(1+\|\xi\|_{2}^{2})\log(m)}\right)$

where $i$ holds by the upper triangle inequality and properties of norms, $ii$
holds by Lemma 6 and equation 11, $iii$ holds by triangle inequality, and $iv$
holds by equation 12 and invoking the upper bound
$\|\gamma_{2}\|_{2}\leq\sqrt{m}\|\gamma_{2}\|_{\infty}$. Then, when $\omega$
is sufficiently small, we get

$\displaystyle\|g_{(t,l,\xi)}-g_{(t,l,\xi)}^{(0)}\|_{2}$
$\displaystyle\leq\mathcal{O}\left(L^{\frac{3}{2}}\omega\sqrt{1+\|\xi\|_{2}^{2}}+\omega
L^{\frac{5}{2}}\sqrt{1+\|\xi\|_{2}^{2}}\sqrt{\log(m)}\right)$
$\displaystyle\leq\mathcal{O}\left(\omega
L^{\frac{5}{2}}\sqrt{\left(1+\|\xi\|_{2}^{2}\right)\log(m)}\right)$ (13)

thus completing the inductive portion of the proof for
$\|g_{(t,l,\xi)}-g_{(t,l,\xi)}^{(0)}\|_{2}$. Then, to finish the inductive
portion of the proof for $\|h_{(t,l,\xi)}-h_{(t,l,\xi)}^{(0)}\|_{2}$, we note
that

$\displaystyle\left\|h_{(t,l,\xi)}-h_{(t,l,\xi)}^{(0)}\right\|_{2}$
$\displaystyle=\|D_{(t,l,\xi)}\left(g_{(t,l,\xi)}-g_{(t,l,\xi)}^{(0)}\right)+\left(D_{(t,l,\xi)}-D_{(t,l,\xi)}^{(0)}\right)g_{(t,l,\xi)}\|_{2}$
$\displaystyle\stackrel{{\scriptstyle
i}}{{\leq}}\|D_{(t,l,\xi)}\|_{2}\cdot\left\|g_{(t,l,\xi)}-g_{(t,l,\xi)}^{(0)}\right\|_{2}+\left\|D_{(t,l,\xi)}-D_{(t,l,\xi)}^{(0)}\right\|_{2}\cdot\|g_{(t,l,\xi)}\|_{2}$
$\displaystyle\stackrel{{\scriptstyle
ii}}{{\leq}}1\cdot\mathcal{O}\left(\omega
L^{\frac{5}{2}}\sqrt{1+\|\xi\|_{2}^{2}}\sqrt{\log(m)}\right)+1\cdot\left(\omega
L^{\frac{3}{2}}\sqrt{1+\|\xi\|_{2}^{2}}\right)$
$\displaystyle\leq\mathcal{O}\left(\omega
L^{\frac{5}{2}}\sqrt{1+\|\xi\|_{2}^{2}}\sqrt{\log(m)}\right)$

where $i$ holds from the upper triangle inequality and properties of the
spectral norm and $ii$ holds from equation 11 and equation 13. Thus, we have
completed the inductive case for $\|h_{(t,l,\xi)}-h_{(t,l,\xi)}^{(0)}\|_{2}$.
From here, a union bound can be taken over all $t\in[n]$ and $l\in[L-1]$ to
yield the desired result with probability
$1-\mathcal{O}(nL)e^{-\Omega(\nicefrac{{m}}{{L}})}-\mathcal{O}(nL)e^{-\Omega\left(m\omega^{\frac{2}{3}}L\right)}+\mathcal{O}(nL)e^{-\Omega\left(m\omega^{\frac{2}{3}}L\log(m)\right)}=1-\mathcal{O}(nL)e^{-\Omega\left(m\omega^{\frac{2}{3}}L\right)}$,
where the last equality again holds when $\omega$ is sufficiently small. ∎

###  E.7 Proof of Lemma 5

###### Proof.

We consider some fixed $t\in[n]$ and arbitrary perturbation vector $\xi$,
where we omit the subscript $\xi_{t}$ to emphasize that the result holds with
different perturbations for any $t\in[n]$ and both when data is newly
encountered or sampled for replay. We define random diagonal matrices
$D_{(t,1)}^{{}^{\prime\prime}},\dots,D_{(t,L-1)}^{{}^{\prime\prime}}$ as any
diagonal matrix with at most $\mathcal{O}\left(m\omega^{\frac{2}{3}}L\right)$
entries in the range $\in[-1,1]$. Consider two sets of model parameters
$\mathbb{W},\mathbb{W}^{\prime}\in\mathcal{B}(\mathbb{W}^{(0)},\omega)$, where
$\mathbb{W}^{(0)}$ is initialized as described in Section 5.1. From equation
11, we know that

$\displaystyle\left\|\frac{1}{\|h_{(t,l-1,\xi)}^{(0)}\|_{2}}\left(D_{(t,l,\xi)}-D_{(t,l,\xi)}^{(0)}\right)g_{(t,l,\xi)}\right\|_{0}\leq\mathcal{O}\left(m\omega^{\frac{2}{3}}L\right)$

with probability at least $1-e^{-\Omega\left(m\omega^{\frac{2}{3}}L\right)}$.
This bound holds for both $\mathbb{W}$ and $\mathbb{W}^{\prime}$. Then,
noticing that right multiplication by $g_{(t,l,\xi)}$ and division by a
constant factor cannot increase the number of non-zero entries within the
matrix $D_{(t,l,\xi)}-D_{(t,l,\xi)}^{(0)}$ (i.e., recall that this matrix is
diagonal), we have

$\displaystyle\left\|D_{(t,l,\xi)}-D_{(t,l,\xi)}^{(0)}\right\|_{0}\leq\mathcal{O}\left(m\omega^{\frac{2}{3}}L\right)$
(14)

From here, we can apply the upper triangle inequality to yield

$\displaystyle\left\|D_{(t,l,\xi)}-D_{(t,l,\xi)}^{\prime}\right\|_{0}$
$\displaystyle=\left\|\left(D_{(t,l,\xi)}-D_{(t,l,\xi)}^{(0)}\right)-\left(D_{(t,l,\xi)}^{\prime}-D_{(t,l,\xi)}^{(0)}\right)\right\|_{0}$
$\displaystyle\stackrel{{\scriptstyle
i}}{{\leq}}\left\|D_{(t,l,\xi)}-D_{(t,l,\xi)}^{(0)}\right\|_{0}+\left\|D_{(t,l,\xi)}^{\prime}-D_{(t,l,\xi)}^{(0)}\right\|_{0}$
$\displaystyle\stackrel{{\scriptstyle
ii}}{{=}}\mathcal{O}\left(m\omega^{\frac{2}{3}}L\right)$

where $i$ holds by the upper triangle inequality and $ii$ is due to equation
14. From here, we apply a union bound over all $t\in[n]$ and $l\in[L-1]$ to
yield

$\displaystyle\left\|D_{(t,l,\xi)}-D_{(t,l,\xi)}^{\prime}\right\|_{0}\leq\mathcal{O}\left(m\omega^{\frac{2}{3}}L\right)$
(15)

for all $t\in[n]$ and $l\in[L-1]$ with probability at least
$1-\mathcal{O}(nL)e^{-\Omega\left(m\omega^{\frac{2}{3}}L\right)}$. equation 15
can also be extended to show the following properties with identical
probability

$\begin{split}\left\|D_{(t,l,\xi)}+D_{(t,l)}^{{}^{\prime\prime}}-D_{(t,l,\xi)}^{(0)}\right\|_{0}\leq\mathcal{O}\left(m\omega^{\frac{2}{3}}L\right)\\\
\left\|D_{(t,l,\xi)}^{\prime}+D_{(t,l)}^{{}^{\prime\prime}}-D_{(t,l,\xi)}^{(0)}\right\|_{0}\leq\mathcal{O}\left(m\omega^{\frac{2}{3}}L\right)\end{split}$
(16)

which holds due to the number of non-zero entries assumed to be within each
random diagonal matrix $D_{(t,l)}^{{}^{\prime\prime}}$ by construction. From
here, we first note that with probability at least
$1-e^{-\Omega\left(m\omega^{\frac{2}{3}}L\log(m)\right)}$ we have

$\displaystyle\left\|\prod\limits_{r=l}^{L-1}\left(D_{(t,l,\xi)}-D_{(t,l)}^{{}^{\prime\prime}}\right)W_{l}\right\|_{2}\leq\mathcal{O}\left(\sqrt{L}\right)$
(17)

due to Lemma 8.6 in (Allen-Zhu et al., 2019). Then, we consider bounding the
following expression

$\displaystyle\left\|W_{L}^{\prime}\prod\limits_{r=l}^{L-1}\left(D_{(t,r,\xi)}^{\prime}+D_{(t,r)}^{\prime\prime}\right)W_{r}^{\prime}-W_{L}\prod\limits_{r=l}^{L-1}D_{(t,r,\xi)}W_{r}\right\|_{2}$
$\displaystyle=\Bigg{\|}\left(W_{L}^{\prime}+W_{L}^{(0)}-W_{L}^{(0)}\right)\prod\limits_{r=l}^{L-1}\left(D_{(t,r,\xi)}^{\prime}+D_{(t,r)}^{{}^{\prime\prime}}\right)W_{r}^{\prime}$
$\displaystyle\quad\quad-\left(W_{L}-W_{L}^{(0)}+W_{L}^{(0)}\right)\prod\limits_{r=l}^{L-1}D_{(t,r,\xi)}W_{r}\Bigg{\|}_{2}$
$\displaystyle=\Bigg{\|}\left(W_{L}^{\prime}-W_{L}^{(0)}\right)\prod\limits_{r=l}^{L-1}\left(D_{(t,r,\xi)}^{\prime}+D_{(t,r)}^{{}^{\prime\prime}}\right)W_{r}^{\prime}+W_{L}^{(0)}\prod\limits_{r=l}^{L-1}\left(D_{(t,r,\xi)}^{\prime}+D_{(t,r)}^{\prime\prime}\right)W_{r}^{\prime}$
$\displaystyle\quad\quad-\left(W_{L}-W_{L}^{(0)}\right)\prod\limits_{r=l}^{L-1}D_{(t,r,\xi)}W_{r}-W_{L}^{(0)}\prod\limits_{r=l}^{L-1}D_{(t,r,\xi)}W_{r}\Bigg{\|}_{2}$
$\displaystyle\stackrel{{\scriptstyle
i}}{{\leq}}\left\|\left(W_{L}^{\prime}-W_{L}^{(0)}\right)\prod\limits_{r=l}^{L-1}\left(D_{(t,r,\xi)}^{\prime}+D_{(t,r)}^{{}^{\prime\prime}}\right)W_{r}^{\prime}\right\|_{2}+\left\|\left(W_{L}-W_{L}^{(0)}\right)\prod\limits_{r=l}^{L-1}D_{(t,r,\xi)}W_{r}\right\|_{2}$
$\displaystyle\quad\quad+\left\|W_{L}^{(0)}\prod\limits_{r=l}^{L-1}\left(D_{(t,r,\xi)}^{\prime}+D_{(t,r)}^{\prime\prime}\right)W_{r}^{\prime}-W_{L}^{(0)}\prod\limits_{r=l}^{L-1}D_{(t,r,\xi)}W_{r}\right\|_{2}$
$\displaystyle\stackrel{{\scriptstyle
ii}}{{\leq}}\mathcal{O}\left(\sqrt{L}\omega\right)+\left\|W_{L}^{(0)}\prod\limits_{r=l}^{L-1}\left(D_{(t,r,\xi)}^{\prime}+D_{(t,r)}^{\prime\prime}\right)W_{r}^{\prime}-W_{L}^{(0)}\prod\limits_{r=l}^{L-1}D_{(t,r,\xi)}W_{r}\right\|_{2}$
$\displaystyle=\mathcal{O}\left(\sqrt{L}\omega\right)+\Bigg{\|}W_{L}^{(0)}\prod\limits_{r=l}^{L-1}\left(D_{(t,r,\xi)}^{\prime}+D_{(t,r)}^{\prime\prime}\right)W_{r}^{\prime}-W_{L}^{(0)}\prod\limits_{r=l}^{L-1}D_{(t,r,\xi)}W_{r}$
$\displaystyle\quad\quad\pm
W_{L}^{(0)}\prod\limits_{r=l}^{L-1}D_{(t,r,\xi)}^{(0)}W_{r}^{(0)}\Bigg{\|}_{2}$
$\displaystyle\stackrel{{\scriptstyle
iii}}{{\leq}}\mathcal{O}\left(\sqrt{L}\omega\right)+\left\|W_{L}^{(0)}\prod\limits_{r=l}^{L-1}\left(D_{(t,r,\xi)}^{\prime}+D_{(t,r)}^{\prime\prime}\right)W_{r}^{\prime}-W_{L}^{(0)}\prod\limits_{r=l}^{L-1}D_{(t,r,\xi)}^{(0)}W_{r}^{(0)}\right\|_{2}$
$\displaystyle\quad\quad+\left\|W_{L}^{(0)}\prod\limits_{r=l}^{L-1}D_{(t,r,\xi)}W_{r}-W_{L}^{(0)}\prod\limits_{r=l}^{L-1}D_{(t,r,\xi)}^{(0)}W_{r}^{(0)}\right\|_{2}$
$\displaystyle\stackrel{{\scriptstyle
iv}}{{\leq}}\mathcal{O}\left(\sqrt{L}\omega\right)+\mathcal{O}\left(\omega^{\frac{1}{3}}L^{2}\sqrt{\log(m)}\right)$
$\displaystyle\stackrel{{\scriptstyle
v}}{{\leq}}\mathcal{O}\left(\omega^{\frac{1}{3}}L^{2}\sqrt{\log(m)}\right)$

where $i$ and $iii$ hold due to the upper triangle inequality, $ii$ holds due
to equation 17, $iv$ holds by Lemma 8.7 in (Allen-Zhu et al., 2019) with
probability at least
$1-e^{-\Omega\left(m\omega^{\frac{2}{3}}L\log(m)\right)}$, and $v$ holds for
$\omega\leq\mathcal{O}\left(L^{-6}\log^{-3}(m)\right)$. Then, the desired
result follows with probability at least
$1-\mathcal{O}(nL)e^{-\Omega\left(m\omega^{\frac{2}{3}}L\right)}-\mathcal{O}(nL)e^{-\Omega\left(m\omega^{\frac{2}{3}}L\log(m)\right)}=1-\mathcal{O}(nL)e^{-\Omega\left(m\omega^{\frac{2}{3}}L\right)}$
by taking a union bound across all $t\in[n]$ and $l\in[L-1]$.

∎

###  E.8 Proof of Lemma 6

###### Proof.

Consider some fixed $t\in[n]$, $j\in[L-1]$, and arbitrary perturbation vector
$\xi$, where we omit the subscript $\xi_{t}$ to emphasize that the result
holds with different perturbations for any $t\in[n]$ and both when data is
newly encountered or sampled for replay. Assume the neural network weights at
initialization $\mathbb{W}^{(0)}$ follow the initialization scheme describe in
Section 5.1. For $l\in[L]$, we can define
$\Delta_{l}^{(0)}\triangleq\frac{\|h_{(t,l,\xi)}^{(0)}\|_{2}^{2}}{\|h_{(t,l-1,\xi)}^{(0)}\|_{2}^{2}}$.
Applying a logarithm (with arbitrary base $a>1$) to this definition, we have

$\displaystyle\log\left(\left\|h_{(t,j,\xi)}^{(0)}\right\|_{2}^{2}\right)=\log(\|x_{t}+\xi\|_{2}^{2})+\sum_{l=0}^{j}\log\left(\Delta_{l}^{(0)}\right)$

Given some $\epsilon\in(0,1]$, we can invoke Fact 7.2 and the proof of Lemma
7.1 from (Allen-Zhu et al., 2019) to show that

$\displaystyle\left|\sum_{l=0}^{j}\log\left(\Delta_{l}^{(0)}\right)\right|\leq\epsilon$

with probability at least
$1-\mathcal{O}(e^{-\Omega(\nicefrac{{\epsilon^{2}m}}{{L}})})$. Thus, we have

$\displaystyle\log(\|x_{t}+\xi\|_{2}^{2})-\epsilon\leq\log\left(\left\|h_{(t,j,\xi)}^{(0)}\right\|_{2}^{2}\right)\leq\log(\|x_{t}+\xi\|_{2}^{2})+\epsilon$
(18)

We first expand the upper bound to derive a bound on
$\|h_{(t,j,\xi)}^{(0)}\|_{2}^{2}$. We begin by exponentiating both sides of
the inequality in equation 18 to obtain the following

$\displaystyle\left\|h_{(t,j,\xi)}^{(0)}\right\|_{2}^{2}$ $\displaystyle\leq
a^{\log(\|x_{t}+\xi\|_{2}^{2})+\epsilon}$
$\displaystyle=(\|x_{t}+\xi\|_{2}^{2})\cdot a^{\epsilon}$
$\displaystyle\stackrel{{\scriptstyle
i}}{{\leq}}(\|x_{t}\|_{2}^{2}+\|\xi\|_{2}^{2})\cdot a^{\epsilon}$
$\displaystyle\stackrel{{\scriptstyle
ii}}{{\leq}}(\|x_{t}\|_{2}^{2}+\|\xi\|_{2}^{2})\cdot a$
$\displaystyle\stackrel{{\scriptstyle iii}}{{=}}(1+\|\xi\|_{2}^{2})\cdot a$

where $i$ follows from the upper triangle inequality, $ii$ is implied by the
fact that $a>1$ and $\epsilon\in(0,1]$, and $iii$ follows from the unit norm
assumption on input data. From here, we note that the base $a$ chosen for the
logarithm is arbitrary, and that any base greater than one can be chosen. With
this in mind, we note that $\lim_{a\rightarrow 1^{+}}(1+\|\xi\|_{2}^{2})\cdot
a=1+\|\xi\|_{2}^{2}$, which yields the upper bound
$\|h_{(t,j,\xi)}^{(0)}\|_{2}^{2}\leq 1+\|\xi\|_{2}^{2}$.

We can similarly derive a lower bound on $\|h_{(t,j,\xi)}^{(0)}\|_{2}^{2}$ as
follows, where we begin by exponentiating both sides of equation 18

$\displaystyle\|h_{(t,j,\xi)}^{(0)}\|_{2}^{2}$ $\displaystyle\geq
a^{\log(\|x_{t}+\xi\|_{2}^{2})-\epsilon}$
$\displaystyle=(\|x_{t}+\xi\|_{2}^{2})\cdot a^{-\epsilon}$
$\displaystyle\stackrel{{\scriptstyle
i}}{{\geq}}\left(\left|\|x_{t}\|_{2}^{2}-\|\xi\|_{2}^{2}\right|\right)\cdot
a^{-\epsilon}$ $\displaystyle\stackrel{{\scriptstyle
ii}}{{\geq}}(1-\|\xi\|_{2}^{2})\cdot a^{-\epsilon}$
$\displaystyle\stackrel{{\scriptstyle
iii}}{{\geq}}(1-\|\xi\|_{2}^{2})\cdot\frac{1}{a}$

where $i$ follows from the lower triangle inequality, $ii$ follows from the
norm assumption on the data, and $iii$ follows from the fact that
$\epsilon\in(0,1]$ and $a>1$. Noting that the base $a$ chosen for the
logarithm is arbitrary, we have $\lim_{a\rightarrow
1^{+}}(1-\|\xi\|_{2}^{2})\cdot\frac{1}{a}=1-\|\xi\|_{2}^{2}$.

By invoking both the upper and lower bounds derived above, we end up with
$\|h_{(t,j,\xi)}^{(0)}\|_{2}^{2}\in\left[1-\|\xi\|_{2}^{2},1+\|\xi\|_{2}^{2}\right]$
with probability at least
$1-\mathcal{O}\left(e^{-\Omega(\nicefrac{{m}}{{L}})}\right)$ due to the fact
that $\epsilon\in(0,1]$. From here, we can take a union bound over all all
$t\in[n]$ and $j\in[L-1]$ to yield the final result with probability
$1-\mathcal{O}\left(nL\right)e^{-\Omega(\nicefrac{{m}}{{L}})}$. ∎

###  E.9 Proof of Corollary 2

###### Proof.

Consider some fixed $t\in[n]$, $j\in[L-1]$, and arbitrary perturbation vector
$\xi$, where we omit the subscript $\xi_{t}$ to emphasize that the result
holds with different perturbations for any $t\in[n]$ and both when data is
newly encountered or sampled for replay. Assume the neural network weights at
initialization $\mathbb{W}^{(0)}$ follow the initialization scheme described
in Section 5.1. From here, we take
$\mathbb{W}\in\mathcal{B}(\mathbb{W}^{(0)},\omega)$. If we then assume
$\omega\leq\mathcal{O}\left(L^{-\frac{9}{2}}\log^{-3}(m)\right)$, then we have
from Lemma 4 that

$\displaystyle\left\|h_{(t,j,\xi)}-h_{(t,j,\xi)}^{(0)}\right\|_{2}\leq\mathcal{O}\left(\omega
L^{\frac{5}{2}}\sqrt{(1+\|\xi\|_{2}^{2})\log(m)}\right)$ (19)

with probability at least $1-e^{-\Omega\left(m\omega^{\frac{2}{3}}L\right)}$.
Similarly, from Lemma 6, we have the following

$\displaystyle\left\|h_{(t,j,\xi)}^{(0)}\right\|_{2}\leq\sqrt{1+\|\xi\|_{2}^{2}}$

with probability at least $1-e^{-\Omega\left(\nicefrac{{m}}{{L}}\right)}$.
Then, we can use these expressions to derive a bound on
$\|h_{(t,j,\xi)}\|_{2}$ as follows

$\displaystyle\left\|h_{(t,j,\xi)}-h_{(t,j,\xi)}^{(0)}\right\|_{2}$
$\displaystyle\stackrel{{\scriptstyle
i}}{{\geq}}\left|\|h_{(t,j,\xi)}\|_{2}-\left\|h_{(t,j,\xi)}^{(0)}\right\|_{2}\right|$
$\displaystyle\stackrel{{\scriptstyle
ii}}{{\geq}}\left|\|h_{(t,j,\xi)}\|_{2}-\sqrt{1+\|\xi\|_{2}^{2}}\right|$
$\displaystyle\geq\|h_{(t,j,\xi)}\|_{2}-\sqrt{1+\|\xi\|_{2}^{2}}$

where $i$ follows from the lower triangle inequality and $ii$ follows from
Lemma 6. Then, combining the expression above with equation 19, we derive

$\displaystyle\|h_{(t,j,\xi)}\|_{2}$ $\displaystyle\leq\mathcal{O}\left(\omega
L^{\frac{5}{2}}\sqrt{(1+\|\xi\|_{2}^{2})\log(m)}\right)+\sqrt{1+\|\xi\|_{2}^{2}}$
$\displaystyle=\mathcal{O}\left(\sqrt{1+\|\xi\|_{2}^{2}}\left(\omega
L^{\frac{5}{2}}\sqrt{\log(m)}+1\right)\right)$

Then, by taking a union bound over all $t\in[n]$ and $j\in[L-1]$, we have the
desired result with probability at least
$1-\mathcal{O}(nL)e^{-\Omega\left(m\omega^{\frac{2}{3}}L\right)}$. ∎

###  E.10 Proof of Lemma 7

###### Proof.

Consider some fixed $t\in[n]$, $l\in[L-1]$, and arbitrary perturbation vector
$\xi$, where we omit the subscript $\xi_{t}$ to emphasize that the result
holds with different perturbations for any $t\in[n]$ and both when data is
newly encountered or sampled for replay. Given
$\mathbb{W}\in\mathcal{B}(\mathbb{W}^{(0)},\omega)$ with $\mathbb{W}^{(0)}$
initialized as described in Section 5.1, we have

$\displaystyle\left\|\nabla_{W_{L}}f_{\mathbb{W}}(x_{t}+\xi)\right\|_{2}$
$\displaystyle\stackrel{{\scriptstyle i}}{{=}}\left\|\sqrt{m}\cdot
h_{(t,L-1,\xi)}\right\|_{2}$ $\displaystyle\stackrel{{\scriptstyle
ii}}{{\leq}}\mathcal{O}\left(\sqrt{m(1+\|\xi\|_{2}^{2})}\left(\omega
L^{\frac{5}{2}}\sqrt{\log(m)}+1\right)\right)$

where $i$ holds because $\nabla_{W_{L}}f_{\mathbb{W}}(x_{t}+\xi)=\sqrt{m}\cdot
h_{(t,L-1,\xi)}^{\top}$ and $ii$ holds due to Corollary 2 with probability at
least $1-e^{-\Omega\left(m\omega^{\frac{2}{3}}L\right)}$. For layers
$l\in[L-1]$, we have

$\displaystyle\nabla_{W_{l}}f_{\mathbb{W}}(x_{t}+\xi)=\sqrt{m}\cdot\left(h_{(t,l-1,\xi)}W_{L}\left(\prod\limits_{r=l+1}^{L-1}D_{(t,r,\xi)}W_{r}\right)D_{(t,l,\xi)}\right)^{\top}$

which allows us to show

$\begin{split}\left\|\nabla_{W_{l}}f_{\mathbb{W}}(x_{t}+\xi)\right\|_{F}&=\sqrt{m}\cdot\left\|h_{(t,l-1,\xi)}W_{L}\left(\prod\limits_{r=l+1}^{L-1}D_{(t,r,\xi)}W_{r}\right)D_{(t,l,\xi)}\right\|_{F}\\\
&\stackrel{{\scriptstyle
i}}{{=}}\sqrt{m}\cdot\|h_{(t,l-1,\xi)}\|_{2}\cdot\left\|W_{L}\left(\prod\limits_{r=l+1}^{L-1}D_{(t,r,\xi)}W_{r}\right)\right\|_{2}\\\
&\stackrel{{\scriptstyle
ii}}{{\leq}}\mathcal{O}\left(\sqrt{m(1+\|\xi\|_{2}^{2})}\left(\omega
L^{\frac{5}{2}}\sqrt{\log(m)}+1\right)\right)\\\
&\quad\quad\cdot{\color[rgb]{0.7578125,0.14453125,0.01953125}\left\|W_{L}\left(\prod\limits_{r=l+1}^{L-1}D_{(t,r,\xi)}W_{r}\right)\right\|_{2}}\\\
\end{split}$ (20)

where $i$ holds due to properties of norms and $ii$ holds due to Corollary 2
with probability at least $1-e^{-\Omega\left(m\omega^{\frac{2}{3}}L\right)}$.
Now, we must bound the red term within the expression above to complete the
proof

$\begin{split}\left\|W_{L}\left(\prod\limits_{r=l+1}^{L-1}D_{(t,r,\xi)}W_{r}\right)\right\|_{2}&\stackrel{{\scriptstyle
i}}{{\leq}}\left\|W_{L}\left(\prod\limits_{r=l+1}^{L-1}\left(D_{(t,r,\xi)}+D_{(t,r)}^{{}^{\prime\prime}}\right)W_{r}\right)\right\|_{2}\\\
&=\Bigg{\|}W_{L}\left(\prod\limits_{r=l+1}^{L-1}\left(D_{(t,r,\xi)}+D_{(t,r)}^{{}^{\prime\prime}}\right)W_{r}\right)\\\
&\quad\quad\pm
W_{L}^{(0)}\prod\limits_{r=l+1}^{L-1}D_{(t,r,\xi)}^{(0)}W_{r}^{(0)}\Bigg{\|}_{2}\\\
&\stackrel{{\scriptstyle
ii}}{{\leq}}\Bigg{\|}W_{L}\left(\prod\limits_{r=l+1}^{L-1}\left(D_{(t,r,\xi)}+D_{(t,r)}^{{}^{\prime\prime}}\right)W_{r}\right)\\\
&\quad\quad-
W_{L}^{(0)}\prod\limits_{r=l+1}^{L-1}D_{(t,r,\xi)}^{(0)}W_{r}^{(0)}\Bigg{\|}_{2}\\\
&\quad\quad+\left\|W_{L}^{(0)}\prod\limits_{r=l+1}^{L-1}D_{(t,r,\xi)}^{(0)}W_{r}^{(0)}\right\|_{2}\\\
&\stackrel{{\scriptstyle
iii}}{{\leq}}\mathcal{O}\left(\omega^{\frac{1}{3}}L^{2}\sqrt{\log(m)}\right)+\mathcal{O}(1)\\\
&=\mathcal{O}\left(1\right)\end{split}$ (21)

where $i$ holds for some random diagonal matrix
$D_{(t,l)}^{{}^{\prime\prime}}\in[-1,1]^{m\times m}$ with at most
$\mathcal{O}\left(m\omega^{\frac{2}{3}}L\right)$ non-zero entries and $ii$ is
due to the upper triangle inequality. $iii$ holds due to Lemma 5 when
$\omega\leq\mathcal{O}\left(L^{-6}\log^{-3}(m)\right)$ and Lemma 7.4 in
(Allen-Zhu et al., 2019) with probabilities at least
$1-e^{-\Omega\left(m\omega^{\frac{2}{3}}L\right)}$ and
$1-e^{-\Omega(\nicefrac{{m}}{{L}})}$, respectively. Thus, we have from
equation 20 and equation 21

$\displaystyle\left\|\nabla_{W_{l}}f_{\mathbb{W}}(x_{t}+\xi)\right\|_{F}$
$\displaystyle\leq\mathcal{O}\left(\sqrt{m(1+\|\xi\|_{2}^{2})}\left(\omega
L^{\frac{5}{2}}\sqrt{\log(m)}+1\right)\right)$
$\displaystyle\leq\mathcal{O}\left(\sqrt{m(1+\|\xi\|_{2}^{2})}\right)$

where the final inequality holds given suffiently small $\omega$. Then, a
union bound can be taken over all $t\in[n]$ and $l\in[L-1]$ to yield the
desired bound on $\left\|\nabla_{W_{l}}f_{\mathbb{W}}(x_{t}+\xi)\right\|_{F}$
with probability at least
$1-\mathcal{O}(nL)e^{-\Omega(\nicefrac{{m}}{{L}})}-\mathcal{O}(nL)e^{-\Omega\left(m\omega^{\frac{2}{3}}L\right)}=1-\mathcal{O}(nL)e^{-\Omega\left(m\omega^{\frac{2}{3}}L\right)}$.
From here, we translate this result to a bound on
$\|\nabla_{W_{l}}L_{(t,\xi)}(\mathbb{W})\|_{F}$ as follows

$\displaystyle\left\|\nabla_{W_{l}}L_{(t,\xi)}(\mathbb{W})\right\|_{F}$
$\displaystyle=\left\|\ell^{\prime}\left(y_{t}\cdot
f_{\mathbb{W}}(x_{t}+\xi)\right)\cdot
y_{t}\cdot\nabla_{W_{l}}f_{\mathbb{W}}(x_{t}+\xi)\right\|_{F}$
$\displaystyle=\left|\ell^{\prime}\left(y_{t}\cdot
f_{\mathbb{W}}(x_{t}+\xi)\right)\cdot
y_{t}\right|\cdot\left\|\nabla_{W_{l}}f_{\mathbb{W}}(x_{t}+\xi)\right\|_{F}$
$\displaystyle\leq\mathcal{O}\left(\sqrt{m(1+\|\xi\|_{2}^{2})}\right)$

where the final inequality is derived by noticing that
$\left|\ell^{\prime}\left(y_{t}\cdot f_{\mathbb{W}}(x_{t}+\xi)\right)\cdot
y_{t}\right|\leq 1$ and invoking the bound on
$\left\|\nabla_{W_{l}}f_{\mathbb{W}}(x_{t}+\xi)\right\|_{F}$ derived above.
Thus, we have arrived at the desired result. ∎