# On the Diminishing Returns of Width for Continual Learning

Etash Guha
SambaNova Systems, RIKEN AIP
<EMAIL_ADDRESS>
&Vihan Lakshman
ThirdAI
<EMAIL_ADDRESS>

###### Abstract

While deep neural networks have demonstrated groundbreaking performance in
various settings, these models often suffer from _catastrophic forgetting_
when trained on new tasks in sequence. Several works have empirically
demonstrated that increasing the width of a neural network leads to a decrease
in catastrophic forgetting but have yet to characterize the exact relationship
between width and continual learning. We design one of the first frameworks to
analyze Continual Learning Theory and prove that width is directly related to
forgetting in Feed-Forward Networks (FFN). Specifically, we demonstrate that
increasing network widths to reduce forgetting yields diminishing returns. We
empirically verify our claims at widths hitherto unexplored in prior studies
where the diminishing returns are clearly observed as predicted by our theory.

##  1 Introduction

Deep Neural Networks (DNNs) have achieved breakthrough performance in numerous
challenging computational tasks that serve as a proxy for intelligence [21].
An essential and practical question is whether the same neural network can
continuously learn over a series of tasks while maintaining performance.
Practically, using a well-trained neural network to achieve similar quality
over a series of tasks is essential for reducing expensive retraining and
computational costs [8] and for mimicking the human-like ability to
continually update its knowledge [14, 20, 36]. In practice, DNNs exhibit
_catastrophic forgetting_ when trained over a series of tasks, experiencing a
sharp drop in performance on the previously learned tasks.

However, preventing catastrophic forgetting is theoretically and empirically
tricky in many situations [19, 17]. Many empirical studies of Continual
Learning (CL) have observed that a model’s hidden dimension or width is
positively correlated with the ability to continually learn [30, 29, 38].
Moreover, catastrophic forgetting is more easily mitigated in the infinite-
width or Neural Tangent Kernel regime [4, 9, 6, 12]. However, the exact
relationship between width and continual learning still needs to be clarified
in the more practical finite-width setting. Theoretically, explaining this
relationship requires understanding the effects of training and retraining a
model on different datasets, which is a complex and difficult-to-analyze
process. Through pure experimentation, most works observe a roughly linear
relationship between width and continual learning, such as in small FFNs [29]
or in large CNNs and ResNets [38, 30], suggesting that increasing the scale of
models is a simple method for improving continual learning.

In this paper, we explicitly investigate the relationship between width and
continual learning. We have observed empirically and theoretically that
_simply increasing a model’s width suffers diminishing returns in improving
continual learning._ To rigorously analyze these phenomena, we establish one
of the first theoretical frameworks for analyzing the continual learning error
of Feed-Forward Networks, connecting fundamental properties like depth, number
of tasks, sparsity, activation smoothness, and width to continual learning
error. We use this framework to prove the connection between width and
continual learning in Feed-Forward Networks of arbitrary depth and nonlinear
activations more tightly. To circumvent the typical analytical difficulties of
continual learning, we use the well-observed empirical observation that wider
models move less from initialization during training. For completeness, we
empirically verify this relationship on Feed-Forward Networks trained with
either Stochastic Gradient Descent (SGD) or Adam [18]
optimizers111https://github.com/vihan-lakshman/diminishing-returns-wide-
continual-learning. This lazy training phenomenon has often been observed
empirically in the literature [43, 31, 23, 33, 6, 13]. Using this observation,
we demonstrate that width acts as a functional regularizer, preventing models
trained on subsequent tasks from being too functionally distant from previous
models. Specifically, our new guarantees formalize this relationship between
width and continual learning for finite-width models with nonlinear
activations and variable depth, which do not exist in the literature for wide
models. To our knowledge, this theoretical framework is one of the first to
provide provable guarantees on the continual learning error of models.

Moreover, we empirically observe these diminishing returns. Some existing
works have tested hidden dimensions up to $2048$ [28] where the diminishing
returns are not apparent. In particular, we measure the continual learning
capabilities of FFNs as the hidden dimension is increased to $2^{16}$, much
larger than previously explored in the literature to our knowledge. With these
new expansive experiments on standard CL benchmarks, we see this relationship
between width and continual learning predicted by our theory. We also test the
other correlations predicted by our framework, such as the connections between
model depth, model sparsity, and the number of tasks on continual learning
error. Our framework predicts that increasing model depth or the number of
tasks will also increase continual learning error, matching the empirical
observations in [30]. Moreover, our model predicts increasing the row-wise
sparsity in a model decreases the continual learning error, such as used in
[40]. Our experiments roughly corroborate all of these relationships over
several real datasets and model shapes. To our knowledge, this is the first
work to provably demonstrate the effects of the number of tasks and row-wise
sparsity on continual learning error.

Our results contribute to the literature examining the relationship between
neural network architectures and continual learning performance. We provide
one of the first theoretical frameworks for analyzing catastrophic forgetting
in Feed-Forward Networks. While our theoretical framework does not perfectly
capture all information about continual forgetting empirically, it is a
valuable step in analyzing continual learning from a theoretical framework. As
predicted by our theoretical framework, we demonstrate empirically that
scaling width alone is insufficient for mitigating the effects of catastrophic
forgetting, providing a more nuanced understanding of finite-width forgetting
dynamics than results achieved in prior studies [29, 38]. We also prove that
our theoretical framework predicts several other connections between model
architecture and catastrophic forgetting.

##### Contributions

In summary, we make the following contributions in our work.

  1. 1.

We develop one of the first theoretical frameworks to analyze catastrophic
forgetting in Feed-Forward Networks. Our theoretical framework corroborates
several empirical findings, such as the connection between depth, sparsity,
and forgetting. Our theoretical framework also predicts that models incur
diminishing returns in terms of continual learning capability at large widths.

  2. 2.

Under this framework, we provably demonstrate that the training of nonlinear,
variable depth feed-forward networks incurs continual learning error on the
order of $\mathcal{O}\left(tW^{-\beta}\alpha^{\frac{1-2\beta}{2}}\right)$
where $t$ is the number of tasks the model has been trained on, $W$ is the
width, $\alpha$ is the sparsity percentage, and $\beta$ is a data-dependent
real value. To our knowledge, this is the first work formalizing the
connection between width, sparsity, number of tasks, and continual learning
for nonlinear models of variable depth.

  3. 3.

By testing at hidden dimensions not seen previously, we empirically see the
diminishing returns of continual learning when increasing width. These
experiments hold across many different width Feed Forward Networks on datasets
such as Rotated MNIST and Fashion MNIST, Rotated SVHN, and the Rotated German
Traffic Signs Benchmark (GTSRB).

  4. 4.

We empirically confirm the predictions of our theoretical frameworks on the
impact of depth, number of tasks, and row-wise sparsity on the continual
learning error over the same host of datasets, demonstrating the power of our
theoretical framework.

##  2 Related Works

###  2.1 Continual Learning

We review several relevant works in the Continual Learning literature. The
original works discussing Continual Learning and Catastrophic Forgetting
phenomenon are Ring [39], McCloskey and Cohen [26] and Thrun and Mitchell
[41]. Perhaps most relevant to this work are Mirzadeh et al. [30] and Mirzadeh
et al. [29], which note the positive correlation between the width of models
and continual learning. However, their experiments are limited to small
widths, at a maximum of $2048$ hidden dimension, which is small relative to
the current deep learning state of the art. Moreover, their analysis is
limited, only proving the continual learning in the setting of two-layer
linear networks without nonlinear activation. Ramasesh et al. [38] and Yoon et
al. [42] discuss how scale broadly empirically affects continual learning but
does not provide any theoretical analysis nor focus specifically on width.

Bennani and Sugiyama [4] and Doan et al. [9] discuss theoretical frameworks
for continually learning models in the infinitely wide or NTK regime. Several
works have used explicit functional regularization as a way to mitigate
catastrophic forgetting [24, 5, 11, 16, 7]. Peng et al. [37] provides a robust
theoretical framework, their Ideal Continual Learner framework, which attempts
to develop a solid theoretical framework for understanding different continual
learning methods. Mirzadeh et al. [28] discuss the geometric similarities
between the different minima found in a continual learning regime

###  2.2 Wide Networks

Here, we review essential works relevant to understanding wide networks in the
literature and different architectures. Nguyen et al. [34] discusses the
effects of width and depth on the learned representation of the model. Arora
et al. [3] discusses the empirical benefits of using the infinite-width Neural
Tangent Kernel on different classification tasks. Novak et al. [35] provides a
method to compute the infinite-width model with less memory and better
efficiency. Lee et al. [22] discuss the training dynamics of wide neural
networks under gradient descent. Lu et al. [25] discuss the expressiveness of
wide neural networks and how wide neural networks can express certain
functions better than deep ones. Jacot et al. [15], Allen-Zhu et al. [1], and
Du et al. [10] capture the training dynamics of infinitely-wide neural
networks under the Neural Tangent Kernel Regime

##  3 Preliminary

###  3.1 Notation

Let our model $\mathbf{M}_{t}$ yielded after training on the $t$th task be
denoted as

$\mathbf{M}_{t}(x)=\mathbf{A}_{t,L}\phi_{L-1}(\mathbf{A}_{t,L-1}\phi_{L-2}(\dots\mathbf{A}_{t,2}\phi_{1}(\mathbf{A}_{t,1}x)))\text{.}$

Here, $x$ is an input of dimensionality $d_{t}$. $\phi_{i}$ is the activation
function for the $i$th layer of $L_{i}$ Lipschitz-Smoothness. Moreover let $W$
be the width of $\mathbf{M}$ such that the input layer
$\mathbf{A}_{t,1}\in\mathbb{R}^{W\times d_{t}}$, last layer
$\mathbf{A}_{t,L}\in\mathbb{R}^{K_{t}\times W}$, and all the middle layers
$\mathbf{A}_{t,l}\in\mathbb{R}^{W\times W}$. Here, $K_{t}$ is the
dimensionality of the output of the $t$th task. We will often index a matrix
by a set of rows. For example, if $\mathcal{S}$ is a set of row indeces,
$\mathbf{A}_{t,l}[\mathcal{S}]$ denotes a matrix in
$\mathbb{R}^{|\mathcal{S}|\times W}$ that contains the $i$th row from
$\mathbf{A}_{t,l}$ if $i\in\mathcal{S}$. Moreover, let $L$ be the model depth.

###  3.2 Problem Setup

Here, we will formalize the problem setup of Continual Learning. Formally, say
we have $T$ training datasets $\mathcal{D}_{1},\dots,\mathcal{D}_{T}$. The
goal of continual learning is to design a model $\mathbf{M}$ such that it
performs well on all datasets $\mathcal{D}_{t}$ for $t\in[T]$. We will
describe the $t$th task as a supervised learning classification task where the
dataset for the $t$th task is
$\mathcal{D}_{t}=(\mathcal{X}_{t},\mathcal{Y}_{t})$. Here, $\mathcal{X}_{t}$
contains $n_{t}$ datapoints of dimension $d_{t}$ and $\mathcal{Y}_{t}$
contains $n_{t}$ labels of dimension $K_{t}$. We wish to form $\mathbf{M}$ by
sequentially training it on each dataset in increasing order from
$\mathcal{D}_{1}$ to $\mathcal{D}_{t}$. We will call $\mathbf{M}_{t}$ the
model outputted after training on the $t$th dataset. After retraining a model
on the new dataset, we want the new model to remember its behavior on the
previous dataset. Namely, we wish to reduce the continual learning error
$\epsilon_{t,t^{\prime}}$ where $t\leq t^{\prime}$ and
$\underset{x\in\mathcal{D}_{t}}{\max}\left\|\mathbf{M}_{t}(x)-\mathbf{M}_{t^{\prime}}(x)\right\|_{2}\leq\epsilon_{t,t^{\prime}}\text{.}$
Here, after training a model for $t^{\prime}-t$ new datasets, we hope to
ensure that the outputs between the original model on the $t$th dataset and
the new model on the $t^{\prime}$th dataset are similar. Given
$\mathbf{M}_{t}$ is trained to completion on dataset $\mathcal{D}_{t}$ and
achieves low error, if our new model $\mathbf{M}_{t^{\prime}}$ is close to
$\mathbf{M}_{t}$ on all inputs from $\mathcal{D}_{t}$, it will also perform
well on $\mathcal{D}_{t}$. Therefore, the main question is the correlation
between $W$, the width of the model $\mathbf{M}$, and the continual learning
error $\epsilon_{t,t^{\prime}}$.

###  3.3 Training Setup

We will examine the setup where our model $\mathbf{M}$ is a Feed Forward
Network with some nonlinear activation. We randomly initialize every layer in
the entire model to train the model on the first task $\mathbf{M}_{1}$. Before
training, as is often done in Continual Learning, we will choose a subset of
rows to be active. For every row with probability $\alpha$, we will select
that row to be active. Otherwise, it will be inactive. Only the active rows
will be used for computation during training and inference. Inactive rows will
not change during training. We will denote $\mathcal{A}_{t,l}$ as the set of
rows active for task $t$ at layer $l$. We use this setup to capture the
connections between row-wise sparsity and continual learning empirically
observed in continual learning literature [40]. Setting $\alpha$ to $1$ will
recover fully dense training. We then train using Adam or SGD till
convergence. To train on a subsequent task, we replace the input and output
layers to match the dimensionality of the new tasks. Moreover, we choose which
rows will be active for this new task for the intermediate layers. We then
retrain till convergence with Adam or SGD. We repeat this training procedure
iteratively for every task. For inference on the $t$th task, we take the
intermediate layers learned at the final task and replace the input and output
layers with the input and output layers trained for the $t$th task to match
the dimensionality of the data from the $t$th task. We only use the active
rows during training for the $t$th task.

##  4 Theoretical Analysis

(a)

(b)

Figure 1: We plot the distance from initialization for both Rotated MNIST and
Rotated Fashion MNIST experiments. We see that distance from initialization
decreases slowly as the width is increased for both datasets. For the
constants discussed in 4.3, the best fitting constants are
$\gamma=0.013,\beta=0.311$ for Rotated MNIST and $\gamma=2.5,\beta=0.12$ for
Fashion MNIST.

We develop the theoretical connection between the width of the intermediate
layers $W$ and the error of continual learning $\epsilon_{t,t^{\prime}}$ for
different task indices $t$ and $t^{\prime}$. We begin by stating our final
theorem and then provide a brief proof sketch. We mention a complete proof in
Section C.1.

###  4.1 Main Theorem

Here, we present our full theorem, Theorem 4.1

######  Theorem 4.1.

(Informal) Say we generate a series of models
$\mathbf{M}_{1},\dots,\mathbf{M}_{T}$ by training sequentially on datasets
$\mathcal{D}_{1},\dots,\mathcal{D}_{T}$ according to Section 3.3. Let
$\lambda_{i,j}^{l}=\frac{\|\mathbf{A}_{l,j}[\mathcal{A}_{l,i}]\|_{2}}{\|\mathbf{A}_{l,i}[\mathcal{A}_{l,i}]\|_{2}}$
denote the ratio of the spectral norms of the weights of different row indices
for different tasks. Moreover, let
$\bar{\lambda}=\underset{l\in[L],i,j\in[T]}{\max}\lambda_{i,j}^{l}$. For all
input vectors from the $t$th dataset $\forall x\in\mathcal{D}_{t}$, the
$\ell_{2}$ norm of the difference of the outputs from models $\mathbf{M}_{t}$
and $\mathbf{M}_{t^{\prime}}$ such that $t^{\prime}\geq t$ are upper bounded
222We can reduce the dependence on weight norms by using noise stability
properties. For more details, please see Section 4.3. by

$\displaystyle\mathbb{E}\bigg{[}\|$
$\displaystyle\mathbf{M}_{t}(x)-\mathbf{M}_{t^{\prime}}(x)\|_{2}\bigg{]}=$
$\displaystyle\mathcal{O}\left((t^{\prime}-t)L2^{L}\bar{\lambda}\chi\left(\prod_{l=1}^{L}L_{l}\|\mathbf{A}_{t,l}\|_{2}\right)\gamma
W^{-\beta}\alpha^{\frac{1-2\beta}{2}}\right)\text{.}$

Here, $\chi$ denotes the maximum norm of the input in $\mathcal{D}_{t}$, i.e.
$\chi=\underset{x\in\mathcal{D}_{t}}{\max}\|x\|_{2}$. Here, $\gamma,\beta$ are
data-dependent positive real values.

As the width of the layers increases, we see that the error
$\epsilon_{t,t^{\prime}}$ is decreased on the order of $W^{-\beta}$. This
formalization furthermore formalizes the connection between the width and the
continual learning error $\epsilon_{t,t^{\prime}}$. This theorem demonstrates
that the continual learning error will decrease slowly as the width increases.
As side effects of xour analysis, we also make explicit how this error scales
over tasks. As the number of datasets trained between
$\mathcal{D}_{t^{\prime}}$ and $\mathcal{D}_{t}$ increases, the continual
learning error increases linearly. This linear increase in error over tasks
is, to our knowledge, unique to this analysis. Moreover, we have an
exponential dependence on $L$, denoting that increasing depth decreases
continual learning ability. Mirzadeh et al. [30] also found that forgetting
increased as depth increased. We reproduce these experiments on our datasets.
Moreover, as the sparsity coefficient is decreased, meaning the chance of a
row being active is decreased, the continual learning ability is increased as
long as $\frac{1-2\beta}{2}$ is positive, which is often the case, in
practice. Thus, this suggests a tradeoff between continual learning ability
and accuracy, as increasing sparsity will increase continual learning ability
but decrease the capacity of the model to learn on a given task. We note some
dependence on the layers’ matrix norms, which may correlate with the layers’
width, but this is usually initialization dependent [31]. We can change the
dependence on the weight norms using the noise stability property of neural
networks as observed in Arora et al. [2] (for more details, please see Section
4.3). Overall, this theorem makes the relationship between several model
parameters, such as width and continual learning, concrete and makes the
diminishing returns more explicit.

###  4.2 Proof Sketch

Here, we present a brief proof sketch of Theorem 4.1 and the intuition behind
it. We will begin this proof by finding the continual learning error between
subsequentially trained models $\mathbf{M}_{t}$ and $\mathbf{M}_{t+1}$, i.e.
$\epsilon_{t,t+1}$, and then scale the analysis to work over more tasks
$t^{\prime}\geq t+1$. To analyze $\epsilon_{t,t+1}$, we split the proof into
three parts: (1) finding how many active rows are shared between layers in the
first and second model at the same position, (2) finding how far these active
rows can change during training, and (3) combining the two parts using
perturbation analysis.

####  4.2.1 Number of Shared Active Rows

From Section 3.3, each row in a layer $\mathbf{A}_{t,l}$ is active with
probability $\alpha$ and inactive with probability $1-\alpha$. Moreover, the
activity of the rows are independent and identical random variables.
Therefore, over the randomness of row selection, the expected number of shared
active rows between two consecutive models is shown in Lemma 4.2.

######  Lemma 4.2.

For any two sequential task indices $t$ and $t+1$ and layer $l$, the expected
size of the intersection between the sets of active rows $\mathcal{A}_{t,l}$
and $\mathcal{A}_{t+1,l}$ is
$\mathbb{E}(|\mathcal{A}_{t,l}\cap\mathcal{A}_{t+1,l}|)=\alpha^{2}W\text{.}$

####  4.2.2 Distance between active rows after training

For rows that are active for both datasets $\mathcal{D}_{t}$ and
$\mathcal{D}_{t+1}$, we need to bound their distance. Here, we use a critical
empirical observation. As observed in Zou et al. [43], Nagarajan and Kolter
[31], Li and Liang [23], Neyshabur et al. [33], Chizat et al. [6], as the
width of the neural network was increased, the distance from initialization
was observed to decrease. Similar intuition on a "lazy training regime" was
presented in Mirzadeh et al. [29]. Still, they did not offer any formal
analysis based on this observation. Intuitively, as the width of the neural
network increases, the implicit regularization of standard gradient-based
learning methods finds models closer to the initialization. While it is
challenging to provide theoretical analyses of the connection between width,
implicit regularization, and the distance from initialization save for
restricted settings [23], empirically, this is a well-observed phenomenon. For
the sake of our analysis, we take this as an assumption in 4.3 and build our
analysis on top of it.

######  Assumption 4.3.

Let $t$ be any task index $t\in[T]$. After training on dataset
$\mathcal{D}_{t+1}$ with initialization $\mathbf{M}_{t}$ via gradient-based
learning methods to generate $\mathbf{M}_{t+1}$, for all layers $l$, we have
that

$\frac{\|\mathbf{A}_{l,t+1}[\mathcal{A}_{l,t+1}]-\mathbf{A}_{l,t}[\mathcal{A}_{l,t+1}]\|_{F}}{\|\mathbf{A}_{l,t}[\mathcal{A}_{l,t+1}]\|_{2}}\leq\gamma|\mathcal{A}_{l,t+1}|^{-\beta}$

where $W$ is the width of the layers of $\mathbf{M}$ where $\gamma,\beta>0$.
Here, $\mathbf{A}_{l,t}[\mathcal{A}_{l,t+1}]$ and
$\mathbf{A}_{l,t+1}[\mathcal{A}_{l,t+1}]$ denote matrices that only contain
the active rows from the weights at the $l$th layer for the tasks $t$ and
$t+1$ respectively.

This assumption states that after training when indexed by the active rows,
the matrix norm of the difference between the $l$th layer of $\mathbf{M}_{t}$
and the $l$th layer of $\mathbf{M}_{i+1}$ normalized by the initial matrix
norm is bounded by some function which is inversely proportional to the width.
This relative distance from initialization is well analyzed in the literature.
For more details on these values in practice, see Section 6. We reiterate that
this phenomenon has been observed across the literature, and we reproduce this
property empirically. Using this assumption, we can demonstrate an upper bound
in the matrix norm of the difference of the weights at a layer for two
sequentially trained models.

######  Lemma 4.4.

Let
$\lambda_{i,j}^{l}=\frac{\|\mathbf{A}_{l,j}[\mathcal{A}_{l,i}]\|_{2}}{\|\mathbf{A}_{l,i}[\mathcal{A}_{l,i}]\|_{2}}$
denote the ratio of the spectral norms of the weights of different row indices
for different tasks. For any task $t$ and layer $l$, we have

$\mathbb{E}\left[\frac{\left\|\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]-\mathbf{A}_{t+1,l}[\mathcal{A}_{t,l}]\right\|_{2}}{\|\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]\|_{2}}\right]\leq\lambda_{t,t+1}^{l}\gamma
W^{-\beta}\alpha^{\frac{1-2\beta}{2}}\text{.}$

The matrix norm of the difference between two layers measures the functional
distance of the two layers. Given this upper bound on the matrix norm, we can
use simple perturbation analysis to calculate how much the difference between
the two outputs of the two sequentially trained models accumulates throughout
the layers.

####  4.2.3 Width as a Functional Reguralizer

We now use simple perturbation analysis to see how far $\mathbf{M}_{t}$ and
$\mathbf{M}_{t^{\prime}}$ will be on input from $\mathcal{D}_{t}$. Given the
Lipschitz-smoothness of the activations at each layer and a bound on the
matrix norm of the weights of different layers from Lemma 4.4, we can use
simple perturbation analysis, i.e., Lemma 2 from Neyshabur et al. [33], to
bound the continual learning error. This analysis gives us a simple guarantee
on the error $\epsilon_{t,t+1}$. Moreover, using simple triangle inequality,
we expand this claim to general $\epsilon_{t,t^{\prime}}$ where
$t^{\prime}>t$. We state the continual learning error between subsequent tasks
using this analysis technique.

######  Lemma 4.5.

Let $\bar{\lambda}=\underset{l\in[L],i,j\in[T]}{\max}\lambda_{i,j}^{l}$. For
any input vector from the dataset for the $t$th task $x\in\mathcal{D}_{t}$,
the $\ell_{2}$ norm of the difference of the outputs from models
$\mathbf{M}_{t}$ and $\mathbf{M}_{t+1}$ are upper bounded by $\forall
x\in\mathcal{D}_{t}$,

$\displaystyle\mathbb{E}\bigg{[}\|\mathbf{M}_{t}$
$\displaystyle(x)-\mathbf{M}_{t+1}(x)\|_{2}\bigg{]}\leq$ $\displaystyle
L2^{L}\chi\bar{\lambda}\left(\prod_{l=1}^{L}L_{l}\|\mathbf{A}_{t,l}\|_{2}\right)\gamma
W^{-\beta}\alpha^{\frac{1-2\beta}{2}}\text{.}$

Here, $\chi$ denotes the maximum norm of the input in $\mathcal{D}_{t}$, i.e.
$\chi=\underset{x\in\mathcal{D}_{t}}{\max}\|x\|_{2}$.

This bound states that the difference between outputs in two models can be
tracked as the input flows through the models. If the two models have close
weights at each layer, they will also have close outputs. Here, we see how
width and sparsity cause the layers to be similar, resulting in low continual
learning error between two sequential models. Using such a bound, we can prove
that the difference between the original and the new model differs only so
much. Moreover, we can extend the above to compare models more than one task
apart, i.e., comparing $\mathbf{M}_{t}$ and $\mathbf{M}_{t^{\prime}}$. Doing
so yields our final theorem. The implicit regularization of training large-
width networks to find minima close to initialization acts as a functional
regularization in the continual learning setting on the order of $W^{-\beta}$.

###  4.3 Extension to Noise Stability

The dependence on the weight norm is pessimistic in our bounds since neural
networks tend to be stable to noise in the input Arora et al. [2]. To remove
such dependence, we can rely on two terms: layer cushion and activation
contraction.

######  Definition 4.6.

Let $x_{t,l-1}$ be defined as the output of the first $l-1$ layers of
$\mathbf{M}_{t}$ for some input $x\in\mathcal{D}_{t}$. The layer cushion of
layer $l$ of the model $\mathbf{M}_{t}$ on the task $t$ is defined to be the
smallest number $\mu_{t,l}$ such that for all inputs in $x\in\mathcal{D}_{t}$,
we have that
$\|\mathbf{A}_{t,l}\|_{2}\|\phi_{l}(x_{t,l-1})\|_{2}\leq\mu_{t,l}\|\mathbf{A}_{t,l}\phi_{l}(x_{t,l-1})\|_{2}\text{.}$

Intuitively, the layer cushion constant $\mu_{t,l}$ is a data-dependent
constant that tightens the pessimistic analysis of using the weight norms.
Moreover, we will define the activation contraction similarly as the
following.

######  Definition 4.7.

Let $x_{t,l-1}$ be defined as the output of the first $l-1$ layers of
$\mathbf{M}_{t}$ for some input $x\in\mathcal{D}_{t}$. The activation
contraction $c_{t}$ for layer $l$ and model $\mathbf{M}_{t}$ is defined as the
smallest number such that for any layer $l$ and any $x\in\mathcal{D}_{t}$ such
that $\|x_{t,l-1}\|_{2}\leq c_{t}\|\phi_{l}(x_{t,l-1})\|_{2}\text{.}$

This connection tightens the pessimistic analysis surrounding the activation
layers. Combining these two definitions, we can remove the dependence on the
weight norm in our bounds.

######  Theorem 4.8.

Denote
$\Gamma_{t}=\underset{x\in\mathcal{D}_{t}}{\max}\|\mathbf{M}_{t}(x)\|_{2}$.
Then, we can characterize the continual learning error between two
subsequently trained models as

$\displaystyle\mathbb{E}\left[\|\mathbf{M}_{t}(x)-\mathbf{M}_{t^{\prime}}(x)\|_{2}\right]$
$\displaystyle\leq\Gamma_{t}(t^{\prime}-t)\gamma\bar{\lambda}W^{-\beta}\alpha^{\frac{1-2\beta}{2}}\eta\text{,}$

where
$\eta=\left(\prod_{i=1}^{l}\kappa_{i}+\kappa_{i}(t^{\prime}-t)\gamma\bar{\lambda}\mu_{t,i}\right)\left(\sum_{i=1}^{l}\kappa_{i}\right)$
and $\kappa_{i}=L_{i}c_{i}\mu_{i,t}$.

Empirically, such constants can improve upon the pessimistic analysis using
weight norms. For more details on the empirical value of these constants,
please see Arora et al. [2].

##  5 Experiments

Width | AA | AF | LA | JA
---|---|---|---|---
$32$ | 56.3 | 37.7 | 93.0 | 91.8
$64$ | 58.7 | 36.0 | 93.5 | 93.5
$128$ | 59.8 | 35.0 | 93.8 | 94.3
$256$ | 60.9 | 34.2 | 94.0 | 94.8
$512$ | 61.9 | 33.2 | 94.1 | 95.0
$1024$ | 62.7 | 32.6 | 94.2 | 95.3
$2048$ | 64.1 | 31.2 | 94.3 | 95.5
$4096$ | 65.3 | 30.2 | 94.5 | 95.7
$8192$ | 66.7 | 28.9 | 94.7 | 95.7
$16384$ | 68.0 | 27.9 | 94.9 | 95.9
$32768$ | 69.4 | 26.6 | 95.6 | 96.1
$65536$ | 69.6 | 26.7 | 95.6 | 96.2
(a) Rotated MNIST

Width | AA | AF | LA | JA
---|---|---|---|---
$32$ | 37.7 | 46.0 | 82.1 | 77.8
$64$ | 37.9 | 46.0 | 82.4 | 80.0
$128$ | 38.2 | 46.0 | 82.5 | 79.4
$256$ | 38.4 | 45.9 | 82.7 | 79.8
$512$ | 38.8 | 45.6 | 82.9 | 79.9
$1024$ | 39.3 | 45.3 | 83.1 | 79.9
$2048$ | 39.9 | 44.8 | 83.3 | 79.1
$4096$ | 40.1 | 44.9 | 83.7 | 80.9
$8192$ | 40.8 | 44.5 | 83.9 | 80.2
$16384$ | 41.4 | 44.3 | 84.5 | 78.8
$32768$ | 41.9 | 44.3 | 84.9 | 79.9
$65536$ | 42.0 | 44.6 | 85.5 | 80.9
(b) Rotated Fashion MNIST

Table 1: Our Continual Learning experiments on varying width FFNs on Rotated
MNIST and Rotated Fashion MNIST. We see that the Average Forgetting slowly
stops decreasing after a width of $2^{10}$.

To empirically validate the theoretical results in this work, we conducted a
series of experiments across multiple established continual learning
benchmarks following prior work Mirzadeh et al. [29, 30]. We find that while
our theoretical framework does not contain all information about catastrophic
forgetting, it is roughly accurate in its predictions. We conduct all
experiments on a single AWS g5g.8xlarge instance equipped with an NVIDIA A10
GPU.

###  5.1 Datasets and Metrics

Following the literature, we train models on four datasets: Rotated MNIST,
Rotated SVHN, Rotated Fashion MNIST, and Rotated GTSRB. To construct each
rotated dataset, we construct five tasks comprising of the original images
from the dataset rotated by $0$, $22.5$, $45$, $67.5$, and $90$ degrees. We
then train on each of these tasks in sequence. Following the work of [29] we
evaluate the efficacy of a continual learning model via three metrics: Average
Accuracy (AA), Average Forgetting (AF), Learning Accuracy (LA), and Joint
Accuracy (JA). For more discussion on the meaning of these metrics, please see
Appendix A.

(a)

(b)

(c)

Figure 3: We visualize the diminishing returns of increasing width across
networks of varying depth. This corroborates our theoretical analysis.

###  5.2 Modeling Setup

We utilize the same model architecture for all of experiments: a Feed Forward
Network consisting of an input, hidden, and output layer. Between each layer,
we use ReLU activations. We vary the width of the hidden layer in all
experiments while keeping all other hyperparameters fixed. We train these
models using the SGD optimizer as well as Adam [18], the latter of which we
report in the appendix. We train these models as classifiers on each task
using CrossEntropy Loss for $5$ epochs. This training paradigm is a standard
modeling choice in the Continual Learning literature [28]. To note, while
swapping out the input and output layers for each task is standard, we found
that doing so did not impact the results significantly since each task has the
same input and output dimensionality, so we do not swap the input and output
layers for each task to better align with the theoretical analysis.

##  6 Results

##### Distance From Initialization

In Figure 1(a) and Figure 1(b), we note that a model’s distance from
initialization tends to decrease as a function of width, which provides
empirical evidence of 4.3. The numerator of our relative distance metric is
the Frobenius norm of the difference between the hidden layers of the
intermediate models trained on the first task and second tasks. In the
denominator of our metric, we have the $\ell_{2}$ norm of the hidden layer of
the model trained on the first task. We see a slowly decreasing distance as
the width increases exponentially. To better understand the constants in 4.3,
we find what values of $\gamma$ and $\beta$ best explain the curves seen in
Figure 1(a) and Figure 1(a). We see values of $\gamma=2.5,\beta=0.12$ for
Fashion MNIST and $\gamma=0.013,\beta=0.311$ for MNIST. This finding also
validates the existing literature on the relationship between width and
distance from initialization [31, 28].

##### Dense Model Results

Furthermore, in Table 1 and Figure 3, we see that increasing width helps with
improving forgetting early on but receives diminishing returns eventually.
Looking specifically at Figure 3, we see a similar trend for datasets MNIST,
Fashion MNIST, and GTSRB. Namely, we see that the increasing width decreases
forgetting as width increases but the forgetting plateaus at larger widths.
This holds across one-layer, two-layer, and three-layer Feed Forward Networks.
However, for SVHN, we see for the first layer that width does not affect the
forgetting much and even increases the forgetting as width increases in two
and three layer networks. All four of these datasets demonstrate a finding
beyond the existing literature: increasing width does not always decrease
forgetting. In Table 1, we provide specific numbers for one-layer networks on
MNIST and Fashion MNIST. For other datasets and depths, we relegate these
tables to the appendix for space purposes; see Figure 9 and Figure 10. We see
specifically in both cases, as width approaches $2^{16}$, the Average
Forgetting begins to plateau, as predicted by our theory. Despite the initial
forgetting for width $2^{5}$ on both datasets beginning at different levels of
forgetting, they both exhibit a similar shape curve in the forgetting,
changing much less after a width of $2^{11}$.

(a)

(b)

Figure 4: We visualize the relationship between depth and task index on
forgetting over several datasets. Figure 4(b) is only for Rotated MNIST.

##### Forgetting over Time

We briefly explore the error over tasks: how much the final model forgets as
the number of tasks seen increases. We take the model trained on the final
task and compute its forgetting on each of the previous tasks. For example,
the forgetting on task index $5$ is $0$ and the forgetting on task index $1$
is the largest since that is the oldest dataset the model has seen. For space,
we include the majority of the figures in the appendix. We plot the error over
the task indices in Figure 4(b) and Figure 8(b) for FFNs of differing widths
on all datasets. We see a roughly linear increase in forgetting as the task
index decreases as is expected. This relationship is seemingly independent of
width and dataset. This linear relationship independent of width corroborates
the theoretical analysis in Theorem 4.1, which predicts a linear relationship.
We include further details in the appendix.

##### Connection between Forgetting and Depth

Our model roughly predicts a increase in forgetting as the depth of the neural
network is increased. This matches several empirical results such as the
results from Mirzadeh et al. [30] that see an increase in forgetting as depth
increases. We reproduce these experiments and report them in Figure 4(a). We
see empirically that the depth and forgetting are positively correlated,
roughly corroborating our theory. Specifically, on Fashion MNIST and GTSRB,
increasing the number of layers from $1$ to $3$ roughly increases the
forgetting. On datasets MNIST and SVHN, the impacts of depth on forgetting are
too small to make any meaningful connection. Our theory roughly predicts an
increase in forgetting as the depth is increased, which holds in two of the
datasets.

##### Connection between Forgetting and Sparsity

We briefly note that our theory predicts that inducing sparsity will improve
the forgetting. In Table 4, when setting the sparsity coefficient
$\alpha=0.1$, forgetting decreases significatntly. For example on MNIST, at
width $2^{14}$, the Average Forgetting decreases to $0.2$, compared to $27.9$
in the dense setting. This corroborates our analysis’s prediction of the
connection between sparsity and forgetting.

##  7 Discussion

We examine both empirically and theoretically the connection between continual
learning and the width of a Feed Forward Network. While our theoretical
framework doesn’t completely capture all information about catastrophic
forgetting, it is a valuable first step to analyzing continual learning
theoretically. Increasing width receives diminishing returns at some point. We
empirically see these diminishing returns at larger hidden dimensions than
tested in previous literature. A possible extension would be whether similar
increases in scale receive diminishing returns such as depth, number of
channels in CNNs, hidden dimension in LLMs, etc. Additionally, an important
work could be to examine if width, in conjunction with other functional
regularization methods, can reduce the effect of diminishing returns.

## References

  * Allen-Zhu et al. [2019] Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang.  Learning and generalization in overparameterized neural networks, going beyond two layers.  _Advances in neural information processing systems_ , 32, 2019.
  * Arora et al. [2018] Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang.  Stronger generalization bounds for deep nets via a compression approach.  In Jennifer Dy and Andreas Krause, editors, _Proceedings of the 35th International Conference on Machine Learning_ , volume 80 of _Proceedings of Machine Learning Research_ , pages 254–263. PMLR, 10–15 Jul 2018.  URL https://proceedings.mlr.press/v80/arora18b.html.
  * Arora et al. [2019] Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang.  On exact computation with an infinitely wide neural net.  _Advances in neural information processing systems_ , 32, 2019.
  * Bennani and Sugiyama [2020] Mehdi Abbana Bennani and Masashi Sugiyama.  Generalisation guarantees for continual learning with orthogonal gradient descent.  In _4th Lifelong Machine Learning Workshop at ICML 2020_ , 2020.
  * Chaudhry et al. [2018] Arslan Chaudhry, Marc’Aurelio Ranzato, Marcus Rohrbach, and Mohamed Elhoseiny.  Efficient lifelong learning with a-gem.  In _International Conference on Learning Representations_ , 2018.
  * Chizat et al. [2019] Lenaic Chizat, Edouard Oyallon, and Francis Bach.  On lazy training in differentiable programming.  _Advances in neural information processing systems_ , 32, 2019.
  * Dhawan et al. [2023] Nikita Dhawan, Sicong Huang, Juhan Bae, and Roger Baker Grosse.  Efficient parametric approximations of neural network function space distance.  In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, _Proceedings of the 40th International Conference on Machine Learning_ , volume 202 of _Proceedings of Machine Learning Research_ , pages 7795–7812. PMLR, 23–29 Jul 2023.  URL https://proceedings.mlr.press/v202/dhawan23a.html.
  * Diethe et al. [2019] Tom Diethe, Tom Borchert, Eno Thereska, Borja Balle, and Neil Lawrence.  Continual learning in practice.  _arXiv preprint arXiv:1903.05202_ , 2019.
  * Doan et al. [2021] Thang Doan, Mehdi Abbana Bennani, Bogdan Mazoure, Guillaume Rabusseau, and Pierre Alquier.  A theoretical analysis of catastrophic forgetting through the ntk overlap matrix.  In _International Conference on Artificial Intelligence and Statistics_ , pages 1072–1080. PMLR, 2021.
  * Du et al. [2019] Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai.  Gradient descent finds global minima of deep neural networks.  In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, _Proceedings of the 36th International Conference on Machine Learning_ , volume 97 of _Proceedings of Machine Learning Research_ , pages 1675–1685. PMLR, 09–15 Jun 2019.  URL https://proceedings.mlr.press/v97/du19c.html.
  * Farajtabar et al. [2020] Mehrdad Farajtabar, Navid Azizan, Alex Mott, and Ang Li.  Orthogonal gradient descent for continual learning.  In _International Conference on Artificial Intelligence and Statistics_ , pages 3762–3773. PMLR, 2020.
  * Geiger et al. [2020] Mario Geiger, Stefano Spigler, Arthur Jacot, and Matthieu Wyart.  Disentangling feature and lazy training in deep neural networks.  _Journal of Statistical Mechanics: Theory and Experiment_ , 2020(11):113301, 2020.
  * Ghorbani et al. [2019] Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari.  Limitations of lazy training of two-layers neural network.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Hadsell et al. [2020] Raia Hadsell, Dushyant Rao, Andrei A Rusu, and Razvan Pascanu.  Embracing change: Continual learning in deep neural networks.  _Trends in cognitive sciences_ , 24(12):1028–1040, 2020.
  * Jacot et al. [2018] Arthur Jacot, Franck Gabriel, and Clément Hongler.  Neural tangent kernel: Convergence and generalization in neural networks.  _Advances in neural information processing systems_ , 31, 2018.
  * Khan and Swaroop [2021] Mohammad Emtiyaz E Khan and Siddharth Swaroop.  Knowledge-adaptation priors.  _Advances in Neural Information Processing Systems_ , 34:19757–19770, 2021.
  * Kim et al. [2022] Gyuhak Kim, Changnan Xiao, Tatsuya Konishi, Zixuan Ke, and Bing Liu.  A theoretical study on solving continual learning.  _Advances in Neural Information Processing Systems_ , 35:5065–5079, 2022.
  * Kingma and Ba [2015] Diederik P. Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  In Yoshua Bengio and Yann LeCun, editors, _ICLR (Poster)_ , 2015.  URL http://dblp.uni-trier.de/db/conf/iclr/iclr2015.html#KingmaB14.
  * Knoblauch et al. [2020] Jeremias Knoblauch, Hisham Husain, and Tom Diethe.  Optimal continual learning has perfect memory and is np-hard.  In _International Conference on Machine Learning_ , pages 5327–5337. PMLR, 2020.
  * Kudithipudi et al. [2022] Dhireesha Kudithipudi, Mario Aguilar-Simon, Jonathan Babb, Maxim Bazhenov, Douglas Blackiston, Josh Bongard, Andrew P Brna, Suraj Chakravarthi Raja, Nick Cheney, Jeff Clune, et al.  Biological underpinnings for lifelong learning machines.  _Nature Machine Intelligence_ , 4(3):196–210, 2022.
  * LeCun et al. [2015] Yann LeCun, Yoshua Bengio, and Geoffrey Hinton.  Deep learning.  _nature_ , 521(7553):436–444, 2015.
  * Lee et al. [2019] Jaehoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl-Dickstein, and Jeffrey Pennington.  Wide neural networks of any depth evolve as linear models under gradient descent.  _Advances in neural information processing systems_ , 32, 2019.
  * Li and Liang [2018] Yuanzhi Li and Yingyu Liang.  Learning overparameterized neural networks via stochastic gradient descent on structured data.  _Advances in neural information processing systems_ , 31, 2018.
  * Lopez-Paz and Ranzato [2017] David Lopez-Paz and Marc’Aurelio Ranzato.  Gradient episodic memory for continual learning.  _Advances in neural information processing systems_ , 30, 2017.
  * Lu et al. [2017] Zhou Lu, Hongming Pu, Feicheng Wang, Zhiqiang Hu, and Liwei Wang.  The expressive power of neural networks: A view from the width.  _Advances in neural information processing systems_ , 30, 2017.
  * McCloskey and Cohen [1989] Michael McCloskey and Neal J Cohen.  Catastrophic interference in connectionist networks: The sequential learning problem.  In _Psychology of learning and motivation_ , volume 24, pages 109–165. Elsevier, 1989.
  * Meisburger et al. [2023] Nicholas Meisburger, Vihan Lakshman, Benito Geordie, Joshua Engels, David Torres Ramos, Pratik Pranav, Benjamin Coleman, Benjamin Meisburger, Shubh Gupta, Yashwanth Adunukota, et al.  Bolt: An automated deep learning framework for training and deploying large-scale neural networks on commodity cpu hardware.  _arXiv preprint arXiv:2303.17727_ , 2023.
  * Mirzadeh et al. [2020] Seyed Iman Mirzadeh, Mehrdad Farajtabar, Dilan Gorur, Razvan Pascanu, and Hassan Ghasemzadeh.  Linear mode connectivity in multitask and continual learning.  _arXiv preprint arXiv:2010.04495_ , 2020.
  * Mirzadeh et al. [2022a] Seyed Iman Mirzadeh, Arslan Chaudhry, Dong Yin, Huiyi Hu, Razvan Pascanu, Dilan Gorur, and Mehrdad Farajtabar.  Wide neural networks forget less catastrophically.  In _International Conference on Machine Learning_ , pages 15699–15717. PMLR, 2022a.
  * Mirzadeh et al. [2022b] Seyed Iman Mirzadeh, Arslan Chaudhry, Dong Yin, Timothy Nguyen, Razvan Pascanu, Dilan Gorur, and Mehrdad Farajtabar.  Architecture matters in continual learning.  _arXiv preprint arXiv:2202.00275_ , 2022b.
  * Nagarajan and Kolter [2019] Vaishnavh Nagarajan and J Zico Kolter.  Generalization in deep networks: The role of distance from initialization.  _arXiv preprint arXiv:1901.01672_ , 2019.
  * Neyshabur et al. [2018a] Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro.  A pac-bayesian approach to spectrally-normalized margin bounds for neural networks.  In _International Conference on Learning Representations_ , 2018a.
  * Neyshabur et al. [2018b] Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro.  The role of over-parametrization in generalization of neural networks.  In _International Conference on Learning Representations_ , 2018b.
  * Nguyen et al. [2020] Thao Nguyen, Maithra Raghu, and Simon Kornblith.  Do wide and deep networks learn the same things? uncovering how neural network representations vary with width and depth.  In _International Conference on Learning Representations_ , 2020.
  * Novak et al. [2022] Roman Novak, Jascha Sohl-Dickstein, and Samuel S Schoenholz.  Fast finite width neural tangent kernel.  In _International Conference on Machine Learning_ , pages 17018–17044. PMLR, 2022.
  * Parisi et al. [2019] German I Parisi, Ronald Kemker, Jose L Part, Christopher Kanan, and Stefan Wermter.  Continual lifelong learning with neural networks: A review.  _Neural networks_ , 113:54–71, 2019.
  * Peng et al. [2023] Liangzu Peng, Paris Giampouras, and René Vidal.  The ideal continual learner: An agent that never forgets.  In _International Conference on Machine Learning_ , pages 27585–27610. PMLR, 2023.
  * Ramasesh et al. [2021] Vinay Venkatesh Ramasesh, Aitor Lewkowycz, and Ethan Dyer.  Effect of scale on catastrophic forgetting in neural networks.  In _International Conference on Learning Representations_ , 2021.
  * Ring [1997] Mark B Ring.  Child: A first step towards continual learning.  _Machine Learning_ , 28:77–104, 1997.
  * Serra et al. [2018] Joan Serra, Didac Suris, Marius Miron, and Alexandros Karatzoglou.  Overcoming catastrophic forgetting with hard attention to the task.  In _International conference on machine learning_ , pages 4548–4557. PMLR, 2018.
  * Thrun and Mitchell [1995] Sebastian Thrun and Tom M Mitchell.  Lifelong robot learning.  _Robotics and autonomous systems_ , 15(1-2):25–46, 1995.
  * Yoon et al. [2018] Jaehong Yoon, Eunho Yang, Jeongtae Lee, and Sung Ju Hwang.  Lifelong learning with dynamically expandable networks.  In _International Conference on Learning Representations_ , 2018.
  * Zou et al. [2020] Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu.  Gradient descent optimizes over-parameterized deep relu networks.  _Machine learning_ , 109:467–492, 2020.

Notation | Meaning | Location
---|---|---
$\mathbf{M}_{t}$ |  Model for $t$th task | Section 3.1
$L_{i}$ |  Lipschitz-Constants if $i$th activation function | Section 3.1
$W$ |  Width of model $\mathbf{M}$ | Section 3.1
$\mathbf{A}_{t,l}$ |  $l$th layer of the $t$th model | Section 3.1
$\mathcal{D}_{t}$ |  $t$th training dataset | Section 3.2
$\epsilon_{t,t^{\prime}}$ |  Continual learning error of $t^{\prime}$th model on $\mathcal{D}_{t}$ | Section 3.2
$\lambda_{i,j}^{l}$ | $\frac{\|\mathbf{A}_{l,j}[\mathcal{A}_{l,i}]\|_{2}}{\|\mathbf{A}_{l,i}[\mathcal{A}_{l,i}]\|_{2}}$ | Theorem 4.1
$\bar{\lambda}$ | Maximum ratio of spectra norms of all models and layers | Theorem 4.1
$L$ | Depth of model | Section 3.1
$\gamma,\beta$ | Constants governing the distance from initialization | 4.3
$\chi$ | $\underset{x\in\mathcal{D}_{t}}{\max}\|x\|_{2}$ | Lemma C.1
$\mu_{t,l}$ |  Layer Cushion for layer $l$ of model $t$ | Definition 4.6
$c_{t}$ |  Activation Contraction of layer $l$ | Definition 4.7
$\Gamma_{t}$ | $\underset{x\in\mathcal{D}_{t}}{\max}\|\mathbf{M}_{t}(x)\|_{2}$ | Theorem 4.8
Table 2: Table of Notation used in Paper

##  Appendix A Metrics

Average accuracy is defined as the mean test accuracy of the final model over
all the tasks after training on all tasks in sequence. Average forgetting is
calculated as the mean difference over tasks between the accuracies obtained
by the intermediate model trained on that task and the final model. The
learning accuracy of a given task measures the accuracy that the model
achieves immediately after training on that task. We also report learning
accuracy as an average over all tasks. Finally, we report Joint Accuracy,
which is the accuracy of training a model on all of the combined datasets.

##  Appendix B Additional Continual Learning Experiments

(a)

(b)

Figure 5: We plot the distance from initialization for both GTSRB and SVHN
experiments. We see that distance from initialization decreases slowly as the
width is increased for both datasets.

Here, we report several additional experiments to investigate the relationship
between width and the ability to learn continually. We demonstrate the
relationship between SGD and this diminishing returns phenomenon by repeating
the experiments with Adam in Section B.1. Moreover, we test how inducing row-
wise sparsity affects the relationship between Continual Learning ability.
Increasing the sparsity can significantly decrease the average forgetting, as
predicted by our theoretical analysis. We demonstrate this in Section B.2.

Furthermore, we study the relationship between forgetting and the number of
tasks trained. We report on this in Section B.3.

###  B.1 Adam and Diminishing Returns

To further investigate the connection between width and continual learning, we
wish to see whether the phenomenon of diminishing returns is visible in other
optimization algorithms. In our theoretical analysis, we argue that the
implicit regularization of gradient-based optimizers finds minima closer to
previous tasks, improving continual learning ability. In our experiments in
the main section, we conduct all experiments with SGD and empirically observe
these diminishing returns. We wish to examine if this implicit regularization
and diminishing returns are unique to SGD or generalizes to other optimization
algorithms. To do so, we repeat the continual learning experiments in the main
text with Adam as the optimizer. We report our results in Table 3. Indeed, we
see very similar results to SGD as in Table 3. We again observe the
diminishing returns for both datasets with Adam as the optimizer. This
observation suggests that our analysis and this phenomenon are not unique to
SGD and extend to different optimizers.

Width | AA | AF | LA | JA
---|---|---|---|---
32 | 51.3 | 43.9 | 94.6 | 91.1
64 | 51.5 | 43.9 | 94.7 | 92.5
128 | 52.2 | 43.2 | 94.8 | 94.1
256 | 51.4 | 44.0 | 94.6 | 94.0
512 | 56.3 | 39.3 | 94.9 | 93.7
1024 | 52.9 | 42.5 | 94.9 | 93.8
2048 | 52.4 | 43.4 | 95.1 | 93.7
4096 | 54.1 | 41.5 | 94.9 | 94.3
8192 | 53.6 | 42.0 | 95.1 | 94.1
16384 | 51.0 | 44.7 | 95.0 | 93.7
32768 | 55.2 | 40.7 | 95.2 | 94.0
65536 | 54.9 | 41.0 | 95.4 | 93.1
(a) Rotated MNIST

Width | AA | AF | LA | JA
---|---|---|---|---
32 | 33.95 | 52.01 | 84.57 | 77.8
64 | 33.66 | 53.04 | 85.48 | 79.7
128 | 35.64 | 51.73 | 86.18 | 79.4
256 | 33.3 | 54.19 | 86.32 | 79.8
512 | 34.27 | 53.39 | 86.52 | 79.9
1024 | 36.31 | 51.33 | 86.62 | 79.1
2048 | 35.73 | 51.77 | 86.53 | 80.9
4096 | 37.47 | 50.2 | 86.66 | 80.2
8192 | 33.25 | 54.32 | 86.37 | 78.8
16384 | 33.98 | 53.71 | 86.57 | 79.9
32768 | 33.95 | 53.65 | 86.49 | 80.9
65536 | 36.91 | 50.69 | 86.53 | 79.0
(b) Rotated Fashion MNIST

Table 3: Continual Learning Results with Adam optimizer training. We see that
despite changing the optimizer to Adam, we see very similar results, including
the diminishing returns trend. This suggests that the diminishing returns
phenomenon is not optimizer-dependent.

###  B.2 Sparsity and Width

In Table 4, we report the results of our investigation into the power of row-
wise sparsity to mitigate the effects of catastrophic forgetting, as predicted
by our theory. For these experiments, we utilize the BOLT deep learning
library (Meisburger et al. [27]) which allows for explicitly setting row-wise
activatins. To summarize our earlier discussion, we define row-wise sparsity
as activated only a subset of the hidden layer neurons in our feedforward
model architecture. We select a fraction $\alpha$ of the hidden layer neurons
for each task to be active uniformly at random. Note that some neurons may be
shared across multiple tasks, which leads to some amount of forgetting, but at
a significantly reduced rate to what we observed in the dense case. Moreover,
the overall learning accuracy is not decreased despite fewer neurons being
used during training. In these experiments, we also apply sparsity to the
output layer such that each task has a distinct set of output classes. As
predicted by our theory, we observe that sparsity can counterweight the
diminishing returns on reducing forgetting purely through width alone.
However, some effects of diminishing returns can still be seen in both
datasets.

Width | AA | AF | LA | JA
---|---|---|---|---
32 | 68.5 | 5.4 | 73.9 | 93.8
64 | 75.6 | 13.3 | 88.9 | 95.8
128 | 82.0 | 9.8 | 91.8 | 96.7
256 | 86.2 | 6.8 | 83.1 | 97.3
512 | 91.2 | 3.3 | 94.5 | 97.7
1024 | 94.6 | 1.3 | 95.9 | 97.9
2048 | 95.5 | 1.3 | 96.7 | 98.1
4096 | 96.4 | 1.0 | 97.3 | 98.0
8192 | 97.1 | 0.5 | 97.6 | 98.1
16384 | 97.7 | 0.2 | 97.9 | 98.0
32768 | 97.6 | 0.3 | 98.0 | 98.2
(a) Rotated MNIST

Width | AA | AF | LA | JA
---|---|---|---|---
32 | 55.7 | 6.0 | 61.7 | 77.8
64 | 58.7 | 13.9 | 72.6 | 79.7
128 | 74.6 | 6.0 | 80.6 | 79.4
256 | 69.9 | 12.7 | 82.6 | 79.8
512 | 76.5 | 7.5 | 84.1 | 79.9
1024 | 79.1 | 5.7 | 84.8 | 79.1
2048 | 77.7 | 7.6 | 85.4 | 80.9
4096 | 82.3 | 3.7 | 85.9 | 80.2
8192 | 79.6 | 6.9 | 86.5 | 78.8
16384 | 78.4 | 8.5 | 86.8 | 79.9
32678 | 78.4 | 8.5 | 86.8 | 80.9
(b) Rotated Fashion MNIST

Table 4: Continual Learning experiments with Row-Wise Sparsity with
$\alpha=0.1$. We see that increasing row-wise sparsity can significantly
decrease forgetting while not decreasing overall learning accuracy. This
corroborates our theoretical results. We still do see diminishing returns in
terms of increasing width and continual learning.

###  B.3 Accuracy over number of tasks

(a)

(b)

We measure the accuracies of the final learned model over all tasks and plot
how the accuracy decreases. We do this over GTSRB and Fashion MNIST. We
conducted this experiment over several different width networks. Our analysis
predicts that there should be a roughly linear relationship between the
accuracy and the number of tasks. With more intermediate tasks between an
initial task and the final task, the model will decrease roughly linearly in
accuracy.

Moreover, our analysis predicts that this error should be independent of the
width. We report the results of our experiments in Figure 8(b). We see in both
experiments that the accuracy roughly decreases as the number of tasks
increases. Moreover, this relationship holds across all the widths tested.
This observation corroborates our theory.

###  B.4 Continual Learning Experiments on Additional Datasets and Depth

We report the numbers from all remaining experiments. In Figure 9, we report
all additional experiments on Fashion MNIST and MNIST. We also report numbers
for two and three layer networks. We also report the numbers for one, two, and
three layer networks on datasets SVHN and GTRSB in LABEL:fig:svhnGTRSB. We see
that the trend of diminishing returns in terms of width across many of the
datasets. We also see that this trend remains apparent among different layer
networks. Moreover, we see that as depth increasing, the forgetting numbers
tend to increase across many of the dataset.

Width | AA | AF | LA | JA
---|---|---|---|---
32 | 54.8 | 40.1 | 93.7 | 93.1
64 | 57.5 | 37.8 | 94.3 | 94.7
128 | 61.0 | 34.9 | 94.9 | 95.6
256 | 61.3 | 34.9 | 95.1 | 96.1
512 | 62.9 | 33.5 | 95.4 | 96.5
1024 | 64.0 | 32.5 | 95.5 | 96.7
2048 | 64.5 | 32.1 | 95.6 | 96.6
4096 | 65.7 | 31.0 | 95.8 | 96.8
8192 | 66.9 | 30.0 | 95.8 | 97.0
16384 | 68.4 | 28.6 | 96.2 | 97.1
32768 | 67.2 | 30.2 | 96.5 | 97.1
(a) Rotated MNIST (2 Layers)

Width | AA | AF | LA | JA
---|---|---|---|---
32 | 32.1 | 51.9 | 82.4 | 81.1
64 | 32.8 | 51.8 | 82.9 | 82.2
128 | 35.2 | 49.4 | 83.1 | 83.4
256 | 33.9 | 51.1 | 83.5 | 84.5
512 | 35.6 | 49.8 | 83.8 | 84.5
1024 | 36.2 | 49.3 | 83.6 | 84.6
2048 | 36.5 | 49.0 | 84.3 | 85.0
4096 | 36.2 | 49.7 | 84.6 | 85.1
8192 | 38.0 | 48.5 | 85.1 | 86.0
16384 | 38.9 | 47.6 | 85.3 | 86.1
32768 | 39.2 | 47.8 | 85.8 | 85.9
(b) Rotated Fashion MNIST (2 Layers)

Width | AA | AF | LA | JA
---|---|---|---|---
32 | 56.5 | 39.0 | 91.8 | 93.1
64 | 60.6 | 35.3 | 92.6 | 95.2
128 | 61.2 | 35.4 | 93.8 | 95.9
256 | 64.9 | 31.9 | 94.4 | 96.3
512 | 63.7 | 33.2 | 95.5 | 96.5
1024 | 65.8 | 31.4 | 95.9 | 97.1
2048 | 66.0 | 31.3 | 96.2 | 97.2
4096 | 68.2 | 29.2 | 96.5 | 97.4
8192 | 69.2 | 28.4 | 96.7 | 97.3
16384 | 68.8 | 28.9 | 96.9 | 97.4
(c) Rotated MNIST (3 Layers)

Width | AA | AF | LA | JA
---|---|---|---|---
32 | 31.0 | 53.2 | 82.1 | 81.3
64 | 31.7 | 52.8 | 82.5 | 82.9
128 | 32.7 | 52.4 | 83.1 | 83.8
256 | 33.6 | 51.9 | 83.5 | 84.5
512 | 33.8 | 52.0 | 83.8 | 84.3
1024 | 35.2 | 50.9 | 84.5 | 85.3
2048 | 36.6 | 49.7 | 84.6 | 85.5
4096 | 37.6 | 48.9 | 85.1 | 85.9
8192 | 38.3 | 48.6 | 85.6 | 85.8
16384 | 39.4 | 47.9 | 85.9 | 85.9
(d) Rotated Fashion MNIST (3 Layers)

Figure 9: We report the numbers from our experiments on more layers on Fashion
MNIST and MNIST. We see that the trend of diminishing returns holds. We also
see that increasing depth often leads to an increase in forgetting.

Width | AA | AF | LA | JA
---|---|---|---|---
32 | 28.8 | 44.8 | 69.8 | 62.2
64 | 31.5 | 44.4 | 72.6 | 66.5
128 | 32.7 | 45.3 | 73.7 | 71.1
256 | 34.8 | 43.5 | 74.9 | 73.0
512 | 33.6 | 45.2 | 73.9 | 72.0
1024 | 34.7 | 43.9 | 74.2 | 73.0
2048 | 34.4 | 44.6 | 74.7 | 72.7
4096 | 34.7 | 44.8 | 75.0 | 73.5
8192 | 34.7 | 44.3 | 74.2 | 73.2
16384 | 33.5 | 44.8 | 73.5 | 70.1
32768 | 30.3 | 48.4 | 73.8 | 72.9
65536 | 35.6 | 43.7 | 73.4 | 73.6
(a) Rotated SVHN

Width | AA | AF | LA | JA
---|---|---|---|---
32 | 46.3 | 31.2 | 72.4 | 67.1
64 | 49.9 | 28.4 | 72.8 | 72.1
128 | 50.6 | 26.8 | 72.8 | 68.4
256 | 51.1 | 26.8 | 73.3 | 67.1
512 | 51.4 | 26.2 | 73.4 | 71.5
1024 | 49.9 | 27.2 | 73.0 | 69.2
2048 | 51.7 | 25.6 | 72.8 | 68.4
4096 | 50.4 | 26.4 | 72.6 | 71.0
8192 | 51.98 | 26.0 | 73.8 | 71.3
16384 | 52.2 | 25.6 | 74.4 | 70.8
32768 | 54.5 | 24.0 | 74.9 | 72.5
65536 | 54.5 | 23.8 | 74.3 | 74.1
(b) Rotated GTSRB

Width | AA | AF | LA | JA
---|---|---|---|---
32 | 30.6 | 42.4 | 69.9 | 61.0
64 | 32.5 | 44.2 | 72.1 | 70.4
128 | 34.9 | 43.8 | 74.4 | 72.9
256 | 33.4 | 45.7 | 75.7 | 75.7
512 | 36.5 | 43.5 | 76.7 | 77.2
1024 | 37.2 | 44.2 | 76.7 | 78.7
2048 | 36.5 | 44.3 | 77.9 | 77.8
4096 | 38.3 | 43.1 | 77.5 | 79.1
8192 | 36.8 | 44.9 | 78.9 | 78.4
16384 | 36.0 | 46.2 | 80.0 | 79.6
32768 | 37.7 | 45.1 | 80.5 | 80.4
(c) Rotated SVHN (2 Layers)

Width | AA | AF | LA | JA
---|---|---|---|---
32 | 41.1 | 35.8 | 70.6 | 66.9
64 | 43.0 | 33.6 | 70.2 | 65.6
128 | 46.4 | 31.6 | 72.6 | 66.3
256 | 45.5 | 32.4 | 72.1 | 70.5
512 | 42.9 | 34.0 | 71.4 | 68.5
1024 | 47.0 | 32.1 | 73.8 | 65.9
2048 | 46.2 | 32.7 | 72.2 | 73.8
4096 | 48.0 | 29.8 | 72.6 | 73.0
8192 | 48.6 | 30.3 | 73.9 | 72.4
16384 | 48.9 | 30.1 | 74.4 | 70.0
32768 | 49.4 | 30.8 | 75.9 | 74.4
(d) Rotated GTSRB (2 Layers)

Width | AA | AF | LA | JA
---|---|---|---|---
32 | 29.7 | 42.5 | 68.3 | 63.4
64 | 32.1 | 44.5 | 72.0 | 70.5
128 | 34.1 | 44.3 | 75.7 | 74.9
256 | 35.9 | 43.9 | 75.5 | 77.6
512 | 36.9 | 44.2 | 76.3 | 77.5
1024 | 37.0 | 44.5 | 77.1 | 79.8
2048 | 37.1 | 44.7 | 77.9 | 79.8
4096 | 37.8 | 43.1 | 77.8 | 80.0
8192 | 38.5 | 44.4 | 78.3 | 80.3
16384 | 38.7 | 44.0 | 79.7 | 80.5
32768 | 39.7 | 43.0 | 80.0 | 81.7
(e) Rotated SVHN (3 Layers)

Width | AA | AF | LA | JA
---|---|---|---|---
32 | 39.9 | 33.8 | 66.6 | 67.4
64 | 40.6 | 34.5 | 68.2 | 67.5
128 | 43.0 | 32.8 | 69.5 | 68.9
256 | 44.1 | 31.8 | 69.6 | 69.3
512 | 43.0 | 33.9 | 69.4 | 73.3
1024 | 41.3 | 36.9 | 71.4 | 72.0
2048 | 45.2 | 32.0 | 70.7 | 73.0
4096 | 44.3 | 33.7 | 72.5 | 71.4
8192 | 44.7 | 34.6 | 72.9 | 72.3
16384 | 43.1 | 35.6 | 73.5 | 74.8
32768 | 46.6 | 33.9 | 75.8 | 72.8
(f) Rotated GTSRB (3 Layers)

Figure 10: We report the numbers from our experiments on more layers on SVHN
and GTRSB. We see that the trend of diminishing returns holds. We also see
that increasing depth often leads to an increase in forgetting.

##  Appendix C Theoretical Analysis

We will first prove the main claim connecting width and continual learning
Theorem 4.1 in Section C.1. We then extend this analysis to noise stability in
Section C.2.

###  C.1 Proof of Theorem 4.1

We formalize the proof of Theorem 4.1 given the intuition from proof sketch of
from the main body. To do the analysis for $\epsilon_{t,t+1}$, we split the
proof into three parts: (1) finding how many active rows are shared between
anything two layers, (2) finding how far these active rows can change during
training, and (3) combining the two parts together using perturbation
analysis.

See 4.2

###### Proof.

Let $\mathbb{I}_{i}$ be the indicator random variable of whether a row $i$ is
active in both models $\mathbf{M}_{t}$ and $\mathbf{M}_{t+1}$, i.e.
$\mathbb{I}_{i}$ if $i\in\mathcal{A}_{t,l}\land
i\in\mathcal{A}_{t^{\prime},l}$ and $0$ otherwise. Therefore, the expected
value of the size of the intersection of the two sets $\mathcal{A}_{t,l}$ and
$\mathcal{A}_{t^{\prime}}$ is

$\displaystyle\mathbb{E}(|\mathcal{A}_{t,l}\cap\mathcal{A}_{t^{\prime},l}|)$
$\displaystyle=\mathbb{E}\left[\sum_{i\in[W]}\mathbb{I}_{i}\right]$
$\displaystyle=\sum_{i\in[W]}\mathbb{E}\left[\mathbb{I}_{i}\right]$

Now, given that the probability that each row $i$ is in a given active set
with probability $\alpha$, the probability a row is randomly in both active
sets is $\alpha^{2}$, i.e. $\mathbb{E}(\mathbb{I}_{i})=\alpha^{2}$. Given
there are $W$ total rows this yields
$\mathbb{E}(|\mathcal{A}_{t,l}\cap\mathcal{A}_{t^{\prime},l}|)=\alpha^{2}W$. ∎

See 4.4

###### Proof.

Now, in expectation, the size of $\mathcal{A}_{t,l}$ is $\alpha W$, i.e.

$\mathbb{E}(|\mathcal{A}_{t,l}|)=\alpha W\text{.}$

Only $\alpha^{2}W$ of the $\alpha W$ active rows $\mathcal{A}_{t,l}$ will
intersect $\mathcal{A}_{t+1,l}$ in expectation, from Lemma 4.2. Therefore,
when training $\mathbf{M}_{t+1}$ only $\alpha^{2}W$ of the $\alpha W$ rows in
expectation will change from its initialization. The rest of the rows will
stay unchanged during training for task $t+1$. Now,
$\mathbf{A}_{t,l}[\mathcal{A}_{t,l}](x)-\mathbf{A}_{t+1,l}[\mathcal{A}_{t,l}]$
is a matrix in $\mathbb{R}^{\mathcal{A}_{t,l}\times W}$. Moreover, this matrix
will have $\alpha(1-\alpha)W$ rows of all $0$’s in expectation. For the other
rows, we know from 4.3, the difference of the two layers indexed by
$\mathcal{A}_{t+1,l}$ is bounded by

$\displaystyle\frac{\|\mathbf{A}_{l,t+1}[\mathcal{A}_{l,t+1}]-\mathbf{A}_{l,t}[\mathcal{A}_{l,t+1}]\|_{F}}{\|\mathbf{A}_{l,t}[\mathcal{A}_{l,t+1}]\|_{2}}$
$\displaystyle\leq\gamma[\alpha W]^{-\beta}$

By the definition of Frobenius Norm

$\displaystyle\sum_{i\in\mathcal{A}_{l,t+1}}\|\mathbf{A}_{l,t+1}[i]-\mathbf{A}_{l,t}[i]\|_{2}^{2}$
$\displaystyle=\|\mathbf{A}_{l,t+1}[\mathcal{A}_{l,t+1}]-\mathbf{A}_{l,t}[\mathcal{A}_{l,t+1}]\|_{F}^{2}$
$\displaystyle\leq\gamma^{2}[\alpha
W]^{-2\beta}\|\mathbf{A}_{l,t}[\mathcal{A}_{l,t+1}]\|_{2}^{2}$

Since the expectation of sum is the sum of expectation, we have that

$\mathbb{E}\left(\sum_{i\in\mathcal{A}_{l,t+1}}\|\mathbf{A}_{l,t+1}[i]-\mathbf{A}_{l,t}[i]\|_{2}^{2}\right)=\sum_{i\in\mathcal{A}_{l,t+1}}\mathbb{E}\left(\|\mathbf{A}_{l,t+1}[i]-\mathbf{A}_{l,t}[i]\|_{2}^{2}\right)\text{.}$

Since all rows are exchangeable under training, we have that the expected
$\ell_{2}$ norm of a row is upper bounded by

$\mathbb{E}\left[\|\mathbf{A}_{l,t+1}[i]-\mathbf{A}_{l,t}[i]\|_{2}^{2}\right]\leq\gamma^{2}[\alpha
W]^{-2\beta-1}\|\mathbf{A}_{l,t}[\mathcal{A}_{l,t+1}]\|_{2}^{2}\text{.}$

Therefore, for rows in both active sets
$\mathcal{A}_{l,t+1}\cup\mathcal{A}_{l,t}$, the expected $\ell_{2}$ norm of
the difference of the rows in $\mathbf{M}_{t}$ and $\mathbf{M}_{t+1}$ is
$\gamma^{2}[\alpha W]^{-2\beta-1}$. For notational ease, let
$\mathcal{I}=\mathcal{A}_{t,l}\cap\mathcal{A}_{t+1,l}$ denote the intersection
of the active rows while
$\mathcal{O}=\mathcal{A}_{t,l}\cap\mathcal{A}_{t+1,l}^{C}$ denote the active
rows not in the active task. Therefore,

$\displaystyle\mathbb{E}$
$\displaystyle\left[\|\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]-\mathbf{A}_{t+1,l}[\mathcal{A}_{t,l}]\|_{2}\right]$
$\displaystyle\leq\mathbb{E}\left[\left\|\mathbf{A}_{t,l}[\mathcal{I}]-\mathbf{A}_{t+1,l}[\mathcal{I}]\right\|_{2}+\left\|\mathbf{A}_{t,l}[\mathcal{O}]-\mathbf{A}_{t+1,l}[\mathcal{O}]\right\|_{2}\right]$
(1)
$\displaystyle=\mathbb{E}\left[\left\|\mathbf{A}_{t,l}[\mathcal{I}]-\mathbf{A}_{t+1,l}[\mathcal{I}]\right\|_{2}\right]$
(2)
$\displaystyle\leq\mathbb{E}\left[\left\|\mathbf{A}_{t,l}[\mathcal{I}]-\mathbf{A}_{t+1,l}[\mathcal{I}]\right\|_{F}\right]$
$\displaystyle\leq\sqrt{\sum_{i\in\mathcal{I}}\mathbb{E}\left[\left\|\mathbf{A}_{t,l}[i]-\mathbf{A}_{t+1,l}[i]\right\|_{2}^{2}\right]}$
(3) $\displaystyle\leq\sqrt{\alpha^{2}W\cdot\gamma^{2}[\alpha
W]^{-2\beta-1}\|\mathbf{A}_{l,t}[\mathcal{A}_{l,t+1}]\|_{2}^{2}}$
$\displaystyle\leq\gamma
W^{-\beta}\alpha^{\frac{1-2\beta}{2}}\|\mathbf{A}_{l,t}[\mathcal{A}_{l,t+1}]\|_{2}$
$\displaystyle=\gamma
W^{-\beta}\alpha^{\frac{1-2\beta}{2}}\|\mathbf{A}_{l,t}[\mathcal{A}_{l,t}]\|_{2}\lambda_{t,t+1}^{l}$

Here, Equation 1 comes from splitting the matrix-multiply by different rows,
Equation 2 comes from seeing that all rows in $\mathcal{O}$ will remain
unchanged after training, and Equation 3 comes from
$\mathbb{E}(\sqrt{X})\leq\sqrt{\mathbb{E}(X)}$ by Jensen’s Inequality for a
random variable $X$.

From here, we have that

$\mathbb{E}\left[\frac{\|\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]-\mathbf{A}_{t+1,l}[\mathcal{A}_{t,l}]\|_{2}}{\|\mathbf{A}_{l,t}[\mathcal{A}_{l,t}]\|_{2}}\right]\leq\gamma
W^{-\beta}\alpha^{\frac{1-2\beta}{2}}\lambda_{t,t+1}^{l}$

∎

######  Lemma C.1.

Say we generate a series of models $\mathbf{M}_{1},\dots,\mathbf{M}_{T}$ by
training sequentially on datasets $\mathcal{D}_{1},\dots,\mathcal{D}_{T}$. Let
$\lambda_{i,j}^{l}=\frac{\|\mathbf{A}_{l,j}[\mathcal{A}_{l,i}]\|_{2}}{\|\mathbf{A}_{l,i}[\mathcal{A}_{l,i}]\|_{2}}$
denote the ratio of the spectral norms of the weights of different row indeces
for different tasks. Moreover, let
$\bar{\lambda}=\underset{l\in[L],i,j\in[T]}{\max}\lambda_{i,j}^{l}$. For any
input vector from the $i$th dataset $x\in\mathcal{D}_{i}$, the $\ell_{2}$ norm
of the difference of the outputs from models $\mathbf{M}_{t}$ and
$\mathbf{M}_{t+1}$ are upper bounded by

$\forall
x\in\mathcal{D}_{t},\quad\mathbb{E}\left[\|\mathbf{M}_{t}(x)-\mathbf{M}_{t+1}(x)\|_{2}\right]\leq
L2^{L}\bar{\lambda}\chi\left(\prod_{l=1}^{L}L_{l}\|\mathbf{A}_{t,l}\|_{2}\right)\gamma
W^{-\beta}\alpha^{\frac{1-2\beta}{2}}\text{.}$

###### Proof.

We will begin by proving the perturbation analysis The first part of this
proof mainly follows from Neyshabur et al. [32]. We restate it here with the
differing notation for clarity and completeness. We will prove the induction
hypothesis that for any $x\in\mathcal{D}_{t}$,

$\|\mathbf{M}_{t,l}(x)-\mathbf{M}_{t+1,l}(x)\|_{2}\leq
2^{l}\|x\|_{2}\left(\prod_{i=1}^{l}L_{i}\|\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]\|_{2}\right)\sum_{i=1}^{l}\frac{\|\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]-\mathbf{A}_{t+1,l}[\mathcal{A}_{t,l}]\|_{2}}{\|\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]\|_{2}}\text{.}$

Here, $\mathbf{M}_{t,l}$ and $\mathbf{M}_{t+1,l}$ denote the models
$\mathbf{M}_{t}$ and $\mathbf{M}_{t^{\prime}}$ respectively with only the
first $l$ layers. The base case of induction trivially holds, given that
$\|\mathbf{M}_{t,0}(x)-\mathbf{M}_{t+1,0}(x)\|_{2}=0$ by definition. Now, we
prove the induction step. Assume that the induction hypothesis holds for
$l-1$. We will prove that it holds for $l$. For notational ease, denote
$\mathbf{U}_{t,l}=\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]-\mathbf{A}_{t+1,l}[\mathcal{A}_{t,l}]$,
$x_{t,l}=\mathbf{M}_{t,l}(x)$, and $x_{t+1,l}=\mathbf{M}_{t+1,l}(x)$. We have
that

$\displaystyle\|x_{t,l}$ $\displaystyle-x_{t+1,l}\|_{2}$
$\displaystyle\leq\|\left(\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]+\mathbf{U}_{t,l}\right)\phi_{l}(x_{t+1,l-1})-\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]\phi_{l}(x_{t,l-1})\|_{2}$
$\displaystyle\leq\|\left(\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]+\mathbf{U}_{t,l}\right)(\phi_{l}(x_{t+1,l-1})-\phi_{l}(x_{t,l-1}))+\mathbf{U}_{t,l}\phi_{l}(x_{t,l-1})\|_{2}$
$\displaystyle\leq\left(\|\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]\|_{2}+\|\mathbf{U}_{t,l}\|_{2}\right)\|\phi_{l}(x_{t+1,l-1})-\phi_{l}(x_{t,l-1})\|_{2}+\|\mathbf{U}_{t,l}\|_{2}\|\phi_{l}(x_{t,l-1})\|_{2}$
$\displaystyle\leq
L_{l}\left(\|\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]\|_{2}+\|\mathbf{U}_{t,l}\|_{2}\right)\|x_{t+1,l-1}-x_{t,l-1}\|_{2}+L_{l}\|\mathbf{U}_{t,l}\|_{2}\|x_{t,l-1}\|_{2}$
(4) $\displaystyle\leq
2L_{l}\left(\|\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]\|_{2}\right)\|x_{t+1,l-1}-x_{t,l-1}\|_{2}+L_{l}\|\mathbf{U}_{t,l}\|_{2}\|x_{t,l-1}\|_{2}$
$\displaystyle\leq
2L_{l}\left(\|\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]\|_{2}\right)\left(1+\frac{1}{L}\right)^{l-1}\|x_{t,0}\|_{2}\left(\prod_{i=1}^{l-1}L_{i}\|\mathbf{A}_{t,i}[\mathcal{A}_{t,i}]\|_{2}\right)\sum_{i=1}^{l-1}\frac{\|\mathbf{U}_{t,l}\|_{2}}{\|\mathbf{A}_{t,i}[\mathcal{A}_{t,i}]\|_{2}}$
$\displaystyle\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad+L_{l}\|\mathbf{U}_{t,l}\|_{2}\|x_{t,l-1}\|_{2}$
(5) $\displaystyle\leq
2^{l}L_{l}\left(\prod_{i=1}^{l-1}L_{i}\|\mathbf{A}_{t,i}[\mathcal{A}_{t,i}]\|_{2}\right)\sum_{i=1}^{l-1}\frac{\|\mathbf{U}_{t,i}\|_{2}}{\|\mathbf{A}_{t,i}[\mathcal{A}_{t,i}]\|_{2}}\|x_{t,0}\|_{2}$
$\displaystyle\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad+L_{l}\|x_{t,0}\|_{2}\|\mathbf{U}_{t,l}\|_{2}\prod_{i=1}^{l-1}L_{i}\|\mathbf{A}_{t,i}[\mathcal{A}_{t,i}]\|_{2}$
$\displaystyle\leq
2^{l}L_{l}\left(\prod_{i=1}^{l-1}L_{i}\|\mathbf{A}_{t,i}[\mathcal{A}_{t,i}]\|_{2}\right)\sum_{i=1}^{l-1}\frac{\|\mathbf{U}_{t,l}\|_{2}}{\|\mathbf{A}_{t,i}[\mathcal{A}_{t,i}]\|_{2}}\|x_{t,0}\|_{2}$
$\displaystyle\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad+\|x_{t,0}\|_{2}\frac{\|\mathbf{U}_{t,l}\|_{2}}{\|\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]\|_{2}}\prod_{i=1}^{l}L_{i}\|\mathbf{A}_{t,i}[\mathcal{A}_{t,i}]\|_{2}$
$\displaystyle\leq
2^{L}\left(\prod_{i=1}^{l}L_{i}\|\mathbf{A}_{t,i}[\mathcal{A}_{t,i}]\|_{2}\right)\sum_{i=1}^{l}\frac{\|\mathbf{U}_{t,l}\|_{2}}{\|\mathbf{A}_{t,i}[\mathcal{A}_{t,i}]\|_{2}}\|x_{t,0}\|_{2}$

Here, Equation 4 comes from the fact that $\phi_{l}$ is $L_{l}$-Lipschitz
smooth and that $\phi_{l}(0)=0$. Moreover, Equation 5 comes from applying the
induction hypothesis. Therefore, we have proven the induction hypothesis for
all layers. We have

$\forall
x\in\mathcal{D}_{t},\quad\|\mathbf{M}_{t}(x)-\mathbf{M}_{t+1}(x)\|_{2}\leq
2^{L}\|x\|_{2}\left(\prod_{l=1}^{L}L_{l}\|\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]\|_{2}\right)\sum_{l=1}^{L}\frac{\|\mathbf{U}_{t,l}\|_{2}}{\|\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]\|_{2}}\text{.}$

Denoting $\chi=\max_{x\in\mathcal{D}_{t}}\|x\|_{2}$ and using Lemma 4.4

$\forall
x\in\mathcal{D}_{t},\quad\mathbb{E}\left[\|\mathbf{M}_{t}(x)-\mathbf{M}_{t+1}(x)\|_{2}\right]\leq
2^{L}\chi\left(\prod_{l=1}^{L}L_{l}\|\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]\|_{2}\right)\sum_{l=1}^{L}\lambda_{t,t+1}^{l}\gamma
W^{-\beta}\alpha^{\frac{1-2\beta}{2}}\text{.}$

Here, we reminded the reader that
$\lambda_{i,j}^{l}=\frac{\|\mathbf{A}_{l,i}[\mathcal{A}_{l,i}]\|_{2}}{\|\mathbf{A}_{l,i}[\mathcal{A}_{l,j}]\|_{2}}$
denotes the ratio of the spectral norms of the weights of different row
indeces for different tasks. Moreover, for any matrix, removing rows cannot
increase the matrix norm, we have that
$\|\mathbf{A}_{t,l}\|_{2}\geq\|\mathbf{A}_{t,l}[\mathcal{A}_{t,l}\|_{2}$.
Therefore, we have

$\prod_{l=1}^{L}\|\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]\|_{2}\leq\prod_{l=1}^{L}\|\mathbf{A}_{t,l}\|_{2}\text{.}$

Given $\bar{\lambda}=\underset{l\in[L],i,j\in[T]}{\max}\lambda_{i,j}^{l}$,

$\forall
x\in\mathcal{D}_{t},\quad\mathbb{E}\left[\|\mathbf{M}_{t}(x)-\mathbf{M}_{t+1}(x)\|_{2}\right]\leq
L2^{L}\bar{\lambda}\chi\left(\prod_{l=1}^{L}L_{l}\|\mathbf{A}_{t,l}\|_{2}\right)\gamma
W^{-\beta}\alpha^{\frac{1-2\beta}{2}}\text{.}$

∎

See 4.1

###### Proof.

We need only repeat the proof above but with a different perturbation to
account for the number of tasks. We repeat it for clarity. We will prove the
induction hypothesis that for any $x\in\mathcal{D}_{t}$,

$\|\mathbf{M}_{t,l}(x)-\mathbf{M}_{t^{\prime},l}(x)\|_{2}\leq
2^{l}\|x\|_{2}\left(\prod_{i=1}^{l}L_{i}\|\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]\|_{2}\right)\sum_{i=1}^{l}\frac{\|\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]-\mathbf{A}_{t^{\prime},l}[\mathcal{A}_{t,l}]\|_{2}}{\|\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]\|_{2}}\text{.}$

Here, $\mathbf{M}_{t,l}$ and $\mathbf{M}_{t^{\prime},l}$ denote the models
$\mathbf{M}_{t}$ and $\mathbf{M}_{t^{\prime}}$ respectively with only the
first $l$ layers. The base case of induction trivially holds, given that
$\|\mathbf{M}_{t,0}(x)-\mathbf{M}_{t^{\prime},0}(x)\|_{2}=0$ by definition.
Now, we prove the induction step. Assume that the induction hypothesis holds
for $l-1$. We will prove that it holds for $l$. For notational ease, denote
$\mathbf{U}_{t,l}=\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]-\mathbf{A}_{t^{\prime},l}[\mathcal{A}_{t,l}]$,
$x_{t,l}=\mathbf{M}_{t,l}(x)$, and
$x_{t^{\prime},l}=\mathbf{M}_{t^{\prime},l}(x)$. We have that

$\displaystyle\|x_{t,l}$ $\displaystyle-x_{t^{\prime},l}\|_{2}$
$\displaystyle\leq\|\left(\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]+\mathbf{U}_{t,l}\right)\phi_{l}(x_{t^{\prime},l-1})-\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]\phi_{l}(x_{t,l-1})\|_{2}$
$\displaystyle\leq\|\left(\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]+\mathbf{U}_{t,l}\right)(\phi_{l}(x_{t^{\prime},l-1})-\phi_{l}(x_{t,l-1}))+\mathbf{U}_{t,l}\phi_{l}(x_{t,l-1})\|_{2}$
$\displaystyle\leq\left(\|\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]\|_{2}+\|\mathbf{U}_{t,l}\|_{2}\right)\|\phi_{l}(x_{t^{\prime},l-1})-\phi_{l}(x_{t,l-1})\|_{2}+\|\mathbf{U}_{t,l}\|_{2}\|\phi_{l}(x_{t,l-1})\|_{2}$
$\displaystyle\leq
L_{l}\left(\|\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]\|_{2}+\|\mathbf{U}_{t,l}\|_{2}\right)\|x_{t^{\prime},l-1}-x_{t,l-1}\|_{2}+L_{l}\|\mathbf{U}_{t,l}\|_{2}\|x_{t,l-1}\|_{2}$
(6) $\displaystyle\leq
2L_{l}\left(\|\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]\|_{2}\right)\|x_{t^{\prime},l-1}-x_{t,l-1}\|_{2}+L_{l}\|\mathbf{U}_{t,l}\|_{2}\|x_{t,l-1}\|_{2}$
$\displaystyle\leq
2L_{l}\left(\|\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]\|_{2}\right)\left(1+\frac{1}{L}\right)^{l-1}\|x_{t,0}\|_{2}\left(\prod_{i=1}^{l-1}L_{i}\|\mathbf{A}_{t,i}[\mathcal{A}_{t,i}]\|_{2}\right)\sum_{i=1}^{l-1}\frac{\|\mathbf{U}_{t,l}\|_{2}}{\|\mathbf{A}_{t,i}[\mathcal{A}_{t,i}]\|_{2}}$
$\displaystyle\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad+L_{l}\|\mathbf{U}_{t,l}\|_{2}\|x_{t,l-1}\|_{2}$
(7) $\displaystyle\leq
2^{l}L_{l}\left(\prod_{i=1}^{l-1}L_{i}\|\mathbf{A}_{t,i}[\mathcal{A}_{t,i}]\|_{2}\right)\sum_{i=1}^{l-1}\frac{\|\mathbf{U}_{t,i}\|_{2}}{\|\mathbf{A}_{t,i}[\mathcal{A}_{t,i}]\|_{2}}\|x_{t,0}\|_{2}$
$\displaystyle\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad+L_{l}\|x_{t,0}\|_{2}\|\mathbf{U}_{t,l}\|_{2}\prod_{i=1}^{l-1}L_{i}\|\mathbf{A}_{t,i}[\mathcal{A}_{t,i}]\|_{2}$
$\displaystyle\leq
2^{l}L_{l}\left(\prod_{i=1}^{l-1}L_{i}\|\mathbf{A}_{t,i}[\mathcal{A}_{t,i}]\|_{2}\right)\sum_{i=1}^{l-1}\frac{\|\mathbf{U}_{t,l}\|_{2}}{\|\mathbf{A}_{t,i}[\mathcal{A}_{t,i}]\|_{2}}\|x_{t,0}\|_{2}$
$\displaystyle\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad+\|x_{t,0}\|_{2}\frac{\|\mathbf{U}_{t,l}\|_{2}}{\|\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]\|_{2}}\prod_{i=1}^{l}L_{i}\|\mathbf{A}_{t,i}[\mathcal{A}_{t,i}]\|_{2}$
$\displaystyle\leq
2^{L}\left(\prod_{i=1}^{l}L_{i}\|\mathbf{A}_{t,i}[\mathcal{A}_{t,i}]\|_{2}\right)\sum_{i=1}^{l}\frac{\|\mathbf{U}_{t,l}\|_{2}}{\|\mathbf{A}_{t,i}[\mathcal{A}_{t,i}]\|_{2}}\|x_{t,0}\|_{2}$

Here, Equation 6 comes from the fact that $\phi_{l}$ is $L_{l}$-Lipschitz
smooth and that $\phi_{l}(0)=0$. Moreover, Equation 7 comes from applying the
induction hypothesis. Therefore, we have proven the induction hypothesis for
all layers. We have

$\forall
x\in\mathcal{D}_{t},\quad\|\mathbf{M}_{t}(x)-\mathbf{M}_{t^{\prime}}(x)\|_{2}\leq
2^{L}\|x\|_{2}\left(\prod_{l=1}^{L}L_{l}\|\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]\|_{2}\right)\sum_{l=1}^{L}\frac{\|\mathbf{U}_{t,l}\|_{2}}{\|\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]\|_{2}}\text{.}$

Now,

$\displaystyle\frac{\|\mathbf{U}_{t,l}\|_{2}}{\|\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]\|_{2}}$
$\displaystyle=\frac{\|\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]-\mathbf{A}_{t^{\prime},l}[\mathcal{A}_{t,l}]\|_{2}}{\|\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]\|_{2}}$
$\displaystyle=\frac{\left\|\sum_{i=t}^{t^{\prime}-1}\mathbf{A}_{i,l}[\mathcal{A}_{i,l}]-\mathbf{A}_{i+1,l}[\mathcal{A}_{i+1,l}]\right\|_{2}}{\|\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]\|_{2}}$
$\displaystyle\leq\frac{\sum_{i=t}^{t^{\prime}-1}\left\|\mathbf{A}_{i,l}[\mathcal{A}_{i,l}]-\mathbf{A}_{i+1,l}[\mathcal{A}_{i+1,l}]\right\|_{2}}{\|\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]\|_{2}}$

Therefore, in expectation,

$\displaystyle\mathbb{E}\left[\frac{\|\mathbf{U}_{t,l}\|_{2}}{\|\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]\|_{2}}\right]$
$\displaystyle\leq(t^{\prime}-t)\bar{\lambda}\gamma
W^{-\beta}\alpha^{\frac{1-2\beta}{2}}$

Denoting $\chi=\max_{x\in\mathcal{D}_{t}}\|x\|_{2}$ and using Lemma 4.4

$\forall
x\in\mathcal{D}_{t},\quad\mathbb{E}\left[\|\mathbf{M}_{t}(x)-\mathbf{M}_{t^{\prime}}(x)\|_{2}\right]\leq
L2^{L}\chi\left(\prod_{l=1}^{L}L_{l}\|\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]\|_{2}\right)(t^{\prime}-t)\bar{\lambda}\gamma
W^{-\beta}\alpha^{\frac{1-2\beta}{2}}\text{.}$

Here, we reminded the reader that
$\lambda_{i,j}^{l}=\frac{\|\mathbf{A}_{l,i}[\mathcal{A}_{l,i}]\|_{2}}{\|\mathbf{A}_{l,i}[\mathcal{A}_{l,j}]\|_{2}}$
denotes the ratio of the spectral norms of the weights of different row
indeces for different tasks. Moreover, for any matrix, removing rows cannot
increase the matrix norm, we have that
$\|\mathbf{A}_{t,l}\|_{2}\geq\|\mathbf{A}_{t,l}[\mathcal{A}_{t,l}\|_{2}$.
Therefore, we have

$\prod_{l=1}^{L}\|\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]\|_{2}\leq\prod_{l=1}^{L}\|\mathbf{A}_{t,l}\|_{2}\text{.}$

Given $\bar{\lambda}=\underset{l\in[L],i,j\in[T]}{\max}\lambda_{i,j}^{l}$,

$\forall
x\in\mathcal{D}_{t},\quad\mathbb{E}\left[\|\mathbf{M}_{t}(x)-\mathbf{M}_{t^{\prime}}(x)\|_{2}\right]\leq(t^{\prime}-t)L2^{L}\bar{\lambda}\chi\left(\prod_{l=1}^{L}L_{l}\|\mathbf{A}_{t,l}\|_{2}\right)\gamma
W^{-\beta}\alpha^{\frac{1-2\beta}{2}}\text{.}$

∎

###  C.2 Noise Stability

See 4.8

###### Proof.

We will prove the induction hypothesis that

$\|\mathbf{M}_{t,l}(x)-\mathbf{M}_{t^{\prime},l}(x)\|_{2}\leq\epsilon_{l}\|\mathbf{M}_{t,l}(x)\|_{2}\text{,}$

where $\epsilon_{l}=\prod_{i}^{l}a_{i}\left(\sum_{i=1}^{l}b_{i}\right)$ where
$a_{i}=c_{i}\mu_{i,t}L_{i}+\frac{L_{i}\mu_{i,l}\|\mathbf{U}_{i,l}\|_{2}c_{l}}{\|\mathbf{A}_{i,l}[\mathcal{A}_{i,l}]\|_{2}}$
and
$b_{i}=\frac{L_{i}\mu_{i,l}\|\mathbf{U}_{i,l}\|_{2}c_{l}}{\|\mathbf{A}_{i,l}[\mathcal{A}_{i,l}]\|_{2}}$.
The base case trivially holds given
$\|\mathbf{M}_{t,0}(x)-\mathbf{M}_{t^{\prime},0}(x)\|_{2}=0$. Here,
$\mathbf{M}_{t,l}$ and $\mathbf{M}_{t^{\prime},l}$ denote the models
$\mathbf{M}_{t}$ and $\mathbf{M}_{t^{\prime}}$ respectively with only the
first $l$ layers. We now perform our induction.

$\displaystyle\|\mathbf{M}_{t,l}(x)-\mathbf{M}_{t^{\prime},l}(x)\|_{2}$
$\displaystyle=\|(\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]-\mathbf{U}_{t,l})\phi_{l}(x_{t^{\prime},{l-1}})-\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]\phi_{l}(x_{t,{l-1}})\|_{2}$
$\displaystyle\leq\|(\mathbf{A}_{t,l}[\mathcal{A}_{t,l}](\phi_{l}(x_{t^{\prime},{l-1}})-\phi_{l}(x_{t,{l-1}}))-\mathbf{U}_{t,l}\phi_{l}(x_{t^{\prime},{l-1}})\|_{2}$
$\displaystyle\leq\|\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]\|_{2}\|\phi_{l}(x_{t^{\prime},{l-1}})-\phi_{l}(x_{t,{l-1}})\|_{2}+\|\mathbf{U}_{t,l}\|_{2}\|\phi_{l}(x_{t^{\prime},{l-1}})\|_{2}$
$\displaystyle\leq
L_{l}\|\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]\|_{2}\|x_{t^{\prime},{l-1}}-x_{t,{l-1}}\|_{2}+L_{l}\|\mathbf{U}_{t,l}\|_{2}\|x_{t^{\prime},{l-1}}\|_{2}$
(8) $\displaystyle\leq
L_{l}\epsilon_{l-1}\|\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]\|_{2}\|x_{t,{l-1}}\|_{2}+(1+\epsilon_{l-1})L_{l}\|\mathbf{U}_{t,l}\|_{2}\|x_{t,{l-1}}\|_{2}$
(9) $\displaystyle\leq
c_{l}L_{l}\epsilon_{l-1}\|\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]\|_{2}\|\phi_{l}(x_{t,l-1})\|_{2}+(1+\epsilon_{l-1})L_{l}\|\mathbf{U}_{t,l}\|_{2}\|x_{t,l-1}\|_{2}$
(10) $\displaystyle\leq
c_{l}\mu_{t,l}L_{l}\epsilon_{l-1}\|\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]\phi_{l}(x_{t,l-1})\|_{2}+(1+\epsilon_{l-1})L_{l}\|\mathbf{U}_{t,l}\|_{2}\|x_{t,l-1}\|_{2}$
(11) $\displaystyle\leq
c_{l}\mu_{t,l}L_{l}\epsilon_{l-1}\|x_{t,l}\|_{2}+(1+\epsilon_{l-1})L_{l}\|\mathbf{U}_{t,l}\|_{2}\|x_{t,l-1}\|_{2}$

Here, Equation 8 comes from the Lipschitz-Smoothness of the activation layers,
Equation 9 comes from applying our induction hypothesis from the previous
layer, Equation 10 comes from applying the activation contraction from
Definition 4.7, Equation 11 comes from applying the layer cushion from
Definition 4.6. We also note that the ratio outputs of two subsequential
layers is bounded as in the following.

$\displaystyle\frac{\|x_{t,l-1}\|_{2}}{\|x_{t,l}\|_{2}}$
$\displaystyle\leq\frac{c_{l}\|\phi_{l}(x_{t,l-1})\|_{2}}{\|x_{t,l}\|_{2}}$
(12)
$\displaystyle\leq\frac{c_{l}\mu_{t,l}}{\|\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]\|_{2}}$
(13)

Here, Equation 12 come from applying the activation contraction from
Definition 4.7 and Equation 13 comes from applying the layer cushion from
Definition 4.6. Therefore, we have that

$\displaystyle\epsilon_{l}$
$\displaystyle\leq\frac{c_{l}\mu_{t,l}L_{l}\epsilon_{l-1}\|x_{t,l}\|_{2}+(1+\epsilon_{l-1})L_{l}\|\mathbf{U}_{t,l}\|_{2}\|x_{t,l-1}\|_{2}}{\|x_{t,l}\|_{2}}$
$\displaystyle\leq
c_{l}\mu_{t,l}L_{l}\epsilon_{l-1}+\frac{(1+\epsilon_{l-1})L_{l}\|\mathbf{U}_{t,l}\|_{2}\|x_{t,l-1}\|_{2}}{\|x_{t,l}\|_{2}}$
$\displaystyle\leq
c_{l}\mu_{t,l}L_{l}\epsilon_{l-1}+\frac{(1+\epsilon_{l-1})\mu_{t,l}L_{l}\|\mathbf{U}_{t,l}\|_{2}c_{l}}{\|\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]\|_{2}}$

For mathematical ease, denote
$a_{l}=c_{l}\mu_{t,l}L_{l}+\frac{L_{l}\mu_{t,l}\|\mathbf{U}_{t,l}\|_{2}c_{l}}{\|\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]\|_{2}}$
and
$b_{l}=\frac{L_{l}\mu_{t,l}\|\mathbf{U}_{t,l}\|_{2}c_{l}}{\|\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]\|_{2}}$.
Thus, we have

$\displaystyle\epsilon_{l}$ $\displaystyle\leq a_{l}\epsilon_{l-1}+b_{l}$
$\displaystyle\leq\prod_{i}^{l}a_{i}\sum_{i=1}^{l-1}b_{i}+b_{l}$
$\displaystyle\leq\prod_{i}^{l}a_{i}\left(\sum_{i=1}^{l-1}b_{i}+b_{l}\right)$
$\displaystyle\leq\prod_{i}^{l}a_{i}\left(\sum_{i=1}^{l}b_{i}\right)$

We have thus proved our hypothesis. We will now simplify the bound. We have
that

$\displaystyle\mathbb{E}\left[a_{l}\right]$
$\displaystyle=\mathbb{E}\left[c_{l}\mu_{t,l}L_{l}+\frac{L_{l}\mu_{t,l}\|\mathbf{U}_{t,l}\|_{2}c_{l}}{\|\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]\|_{2}}\right]$
$\displaystyle\leq
c_{l}\mu_{t,l}L_{l}+L_{l}\mu_{t,l}(t^{\prime}-t)\gamma\bar{\lambda}W^{-\beta}\alpha^{\frac{1-2\beta}{2}}$
(14) $\displaystyle\leq
c_{l}\mu_{t,l}L_{l}+L_{l}c_{l}\mu_{t,l}(t^{\prime}-t)\gamma\bar{\lambda}$

Here, Equation 14 comes from Theorem 4.1. Similarly, we can bound $b_{l}$ such
that

$\displaystyle\mathbb{E}\left[b_{l}\right]$
$\displaystyle=\mathbb{E}\left[\frac{L_{l}\mu_{t,l}\|\mathbf{U}_{t,l}\|_{2}c_{l}}{\|\mathbf{A}_{t,l}[\mathcal{A}_{t,l}]\|_{2}}\right]$
$\displaystyle\leq
L_{l}c_{l}\mu_{t,l}(t^{\prime}-t)\gamma\bar{\lambda}W^{-\beta}\alpha^{\frac{1-2\beta}{2}}$

Therefore, putting it all together yields

$\displaystyle\mathbb{E}\left[\epsilon_{l}\right]\leq\left(\prod_{i=1}^{l}c_{i}\mu_{t,i}L_{i}+L_{i}c_{i}\mu_{t,i}(t^{\prime}-t)\gamma\bar{\lambda}\right)\left(\sum_{i=1}^{l}L_{i}c_{i}(t^{\prime}-t)\gamma\bar{\lambda}W^{-\beta}\alpha^{\frac{1-2\beta}{2}}\mu_{t,i}\right)$
$\displaystyle\leq(t^{\prime}-t)\gamma\bar{\lambda}W^{-\beta}\alpha^{\frac{1-2\beta}{2}}\left(\prod_{i=1}^{l}c_{i}\mu_{t,i}L_{i}+L_{i}(t^{\prime}-t)\gamma\bar{\lambda}\mu_{t,i}\right)\left(\sum_{i=1}^{l}L_{i}\mu_{t,i}\right)$

We now have that $\forall x\in\mathcal{D}_{t}$,

$\mathbb{E}\left[\|\mathbf{M}_{t}(x)-\mathbf{M}_{t^{\prime}}(x)\|_{2}\right]\leq\underset{x\in\mathcal{D}_{t}}{\max}\|\mathbf{M}_{t}(x)\|_{2}\cdot(t^{\prime}-t)\gamma\bar{\lambda}W^{-\beta}\alpha^{\frac{1-2\beta}{2}}\left(\prod_{i=1}^{l}c_{i}\mu_{t,i}L_{i}+L_{i}c_{i}(t^{\prime}-t)\gamma\bar{\lambda}\mu_{t,i}\right)\left(\sum_{i=1}^{l}L_{i}c_{i}\mu_{t,i}\right)\text{.}$

∎