# Towards guarantees for parameter isolation in continual learning

Giulia Lanzillotta, Sidak Pal Singh & Thomas Hofmann
Department of Computer Science
ETH Zurich &Benjamin F. Grewe
Institute of Neuroinformatics
ETH Zurich ETH AI CenterCorrespondence to<EMAIL_ADDRESS>
###### Abstract

Deep learning has proved to be a successful paradigm for solving many
challenges in machine learning. However, deep neural networks fail when
trained sequentially on multiple tasks, a shortcoming known as _catastrophic
forgetting_ in the _continual learning_ literature. Despite a recent flourish
of learning algorithms successfully addressing this problem, we find that
provable guarantees against catastrophic forgetting are lacking. In this work,
we study the relationship between learning and forgetting by looking at the
geometry of neural networks’ loss landscape. We offer a unifying perspective
on a family of continual learning algorithms, namely methods based on
_parameter isolation_ , and we establish guarantees on catastrophic forgetting
for some of them.

##  1 Introduction and motivation

Statistical models based on deep neural networks are trusted with ever more
complex tasks in real-world applications. In real-world environments the
ability to continually and rapidly learn new behaviors is crucial. It is
therefore worthwhile to understand how deep neural networks store and
integrate new information. In this paper, we want to study neural networks in
the _continual learning_ setting, where the input to the learning algorithm is
a _data stream_. In this setting, it has been observed that training neural
networks on new data often severely degrades the performance on old data, a
phenomenon termed _catastrophic forgetting_ (McCloskey & Cohen, 1989), which
we will often simply refer to as _forgetting_ herefter.

Generally speaking, continual learning algorithms address catastrophic
forgetting by leveraging storage external to the network and imposing
constraints (implicit, or explicit) that ensure the network does not stray too
far off from the prior tasks when a new task is given. The storage gets
updated with each new learning task and its specific contents depend on the
algorithm: typical examples include vectors in the parameter space (network
parameters or gradients), input samples, or neural activities. We review the
main trends in the literature in the related work section (Section 2).

The last couple of years have witnessed significant progress in continual
learning (De Lange et al., 2021; Khetarpal et al., 2022). However, most of
this progress has largely been empirical in nature, without any rigorous
theoretical understanding of the successful strategies. As a consequence,
although the algorithms proposed are shown to reduce catastrophic forgetting
on several benchmarks, there is no guarantee that they will achieve the same
low forgetting rate in other contexts, and, in general, it is hard to obtain a
grip over the inherent limitations of the algorithms. Arguably, these
characteristics are necessary to make such algorithms reliable in the wild.

In this study, we focus on theoretically understanding a family of continual
learning methods based on _parameter isolation_ strategies. We propose a
unified framework for these algorithms from a loss landscape perspective. More
specifically, we approximate each task’s loss around the optimum and derive a
constraint on the parameter update to prevent forgetting. We show that many
existing algorithms are special cases of our framework.

Moreover, our work complements previous studies of catastrophic forgetting for
another family of continual learning algorithms, namely _regularisation-based_
methods. Our results suggest that these two different strategies are more
similar than what initially thought.

We begin by introducing formally the continual learning problem. In Section 2
we review the literature most relevant for this study. In Section 3 we
introduce our framework through an analysis of the tasks’ loss geometry , and
in Section 4 we show that several existing parameter isolation algorithms can
be described within this framework and we establish guarantees for two such
algorithms. Finally, Section 5 is dedicated to the empirical validation of our
theoretical findings.

Figure 1: Illustration of catastrophic forgetting on a toy challenge. An MLP
is trained _sequentially_ on $3$ geometric tasks with $2$ classes (in red and
blue). The first task occupies the center of the space, the second one the
bottom left and the last one the top right corner. Each column shows the
network’s decision boundary after learning the corresponding task: after the
first task (left), the network can perfectly discriminate between the two
classes, however, the decision boundary shifts with the second (middle) and
third (right) tasks and the network forgets the first task entirely. The
multi-task solution is shown in the Appendix 4.

###  1.1 Preliminaries

The term continual learning generally refers to a learning problem in which
the data is accessed sequentially. It is typically assumed that the data
stream is _locally i.i.d._ , thereby it can be written as a sequence of tasks
$\mathcal{T}_{1},\dots,\mathcal{T}_{T}$. In this case, the learning algorithm
cannot access examples of previous or future tasks. We restrict our study to
the supervised learning case as it is the most explored in the literature.
Each task $\mathcal{T}_{t}$ comes with a dataset ${D}_{t}$, which in the
supervised learning scenario consists of a set of pairs
$(x,y)\in\mathcal{X}_{t}\times\mathcal{Y}_{t}$. Another typical assumption is
that the input space is shared across tasks, i.e.
$\mathcal{X}_{t}=\mathcal{X}\,\,\forall\,t\in[1,\dots,T]$.

We define the neural network with a set of parameters $\Theta_{t}$. Hereafter,
we assume w.l.o.g. $\Theta_{t}\subseteq\Theta\,\forall\,\,t$ and use
$\Theta\subseteq\mathbb{R}^{P}$ as parameter space (we elaborate on this
choice in Appendix A). We use $\bm{\theta}$ to refer to a generic vector in
the parameter space and $\bm{\theta}_{t}$ to the value of the parameters found
by training on the $t$-th task. Normally, we index the current task with $t$
and any old task with $o$. The neural network implements a function
$f(\,\cdot\,;\bm{\theta}):\mathcal{X}\to\mathcal{Y}_{t}$. We write
$l_{t}(x,y,\bm{\theta})$ for the $t$-th task loss function, and we refer to
the average loss over the dataset with $\mathcal{L}_{t}(\bm{\theta})$. We
shorten the loss measured at the end of training
$\mathcal{L}_{t}(\bm{\theta}_{t})$ to $\mathcal{L}_{t}^{\star}$. Formally,
given an old task $\mathcal{T}_{o}$, and a current parameter vector
$\bm{\theta}$ we define _forgetting_ as:

$\mathcal{E}_{o}(\bm{\theta})=\mathcal{L}_{o}(\bm{\theta})-\mathcal{L}_{o}^{\star}$
(1)

The forgetting on $\mathcal{T}_{o}$ after learning task $\mathcal{T}_{t}$ is
$\mathcal{E}_{o}(t):=\mathcal{E}_{o}(\bm{\theta}_{t})$ and, trivially,
$\mathcal{E}_{t}(t)=0$. Thus, simply, $\mathcal{E}_{o}(t)$ measures the
reduction in performance on task $\mathcal{T}_{o}$ due to learning tasks
$\\{\mathcal{T}_{o+1},\dots,\mathcal{T}_{t}\\}$. Importantly, forgetting may
also be negative, in which case learning the new task has benefited the
performance on the old task. Averaging over all the previous tasks we get the
_average forgetting_ after task $\mathcal{T}_{t}$:
$\mathcal{E}(t)=\frac{1}{t}\sum_{o=1}^{t}\mathcal{E}_{o}(t)$, also known as
_backward transfer_. The goal of continual learning algorithms is to minimise
$\mathcal{E}(t)$ while learning a new task $\mathcal{T}_{t}$, or,
equivalently, to minimise the _multi-task loss_
$\mathcal{L}_{MT}(\bm{\theta})=\sum_{o=1}^{t}\mathcal{L}_{o}(\bm{\theta})$
while only having access to the current task data $D_{t}$. We call
$\bm{\theta}^{\star}$ a minimiser of the multi-task loss.

##  2 Related work

##### Continual learning

We follow De Lange et al. (2021), dividing the literature on continual
learning into three families of methods: replay methods, regularization-based
methods and parameter isolation methods.

_Replay methods_ (Rebuffi et al., 2017; Lopez-Paz & Ranzato, 2017; Shin et
al., 2017; Van de Ven et al., 2020) rely on storing a set of samples $S$ for
each task, often as input or neural activity vectors. The old samples are
revisited during the learning of new tasks effectively restricting the set of
possible solutions to those that agree with the samples stored in memory.

_Regularisation-based methods_ (Kirkpatrick et al., 2017; Zenke et al., 2017;
Nguyen et al., 2017; Ebrahimi et al., 2019; Ritter et al., 2018; Guo et al.,
2022) stem from a Bayesian interpretation of the continual learning problem.
Given a prior over model parameters $\mathcal{P}(\bm{\theta})$ and a
likelihood for the given task data $\mathcal{P}(D_{t}|\bm{\theta})$, learning
a new task is equivalent to estimating the posterior
$\mathcal{P}(\bm{\theta}|D_{t})$, which is then used as prior for the next
task. In practice, this different formulation results in a soft constraint on
the parameters which gets incorporated in the loss function as a regulariser.

Finally, _parameter isolation methods_ (Rusu et al., 2016; Yoon et al., 2017;
Van Etten et al., 2018; Mallya & Lazebnik, 2018; Farajtabar et al., 2020;
Wortsman et al., 2020; Saha et al., 2021; Kang et al., 2022) revolve around
the idea of dynamically allocating ”parts” of the network to each task
$\Theta_{1},\dots,\Theta_{T}:\bigcup_{t}\Theta_{t}=\Theta$. Unlike the rest of
the continual learning literature, we distinguish between _strict_ and
_general_ parameter isolation. When the term _part_ is understood strictly, as
an index set over the parameters or the neurons, this definition comprises
algorithms like PackNet (Mallya & Lazebnik, 2018), SpaceNet (Van Etten et al.,
2018) or Progressive networks (Rusu et al., 2016), which employ respectively
pruning, sparse training, and network expansion to isolate a small set of
parameters per task. If, instead, we allow a network _part_ to be any generic,
non-axis aligned, subspace of the parameter space, this definition also
contains algorithms like OGD (Farajtabar et al., 2020) and GPM (Saha et al.,
2021) and the variants thereof (Deng et al., 2021; Lin et al., 2022), which
use a more sophisticated projection mechanism to prevent forgetting.

##### Geometric properties of the loss landscape

Our results draw on existing literature studying neural networks’ loss
landscape. In particular, we approximate the loss function around the (local)
minimum $\bm{\theta}_{t}$ by looking at the second order derivatives (i.e.
_Hessian_) matrix. Importantly for the following discussion, Sagun et al.
(2016) (also (Sagun et al., 2017)) observed that the loss landscape is mostly
degenerate, especially around the optimum implying that most of the
eigenvalues of the loss Hessian lie near zero. Singh et al. (2021; 2023)
further established rigorously that the Hessian rank can be at most of the
order square root of the number of parameters. Besides, Gur-Ari et al. (2018)
analysed the evolution of the loss gradient and Hessian during training with
SGD and observed that, after a short period of training, the gradient lies in
the subspace spanned by the top eigenvectors of the Hessian. This subspace is
shown to be approximately preserved over long periods of training, suggesting
that the geometry of the loss landscape stabilises early during training.

##### Catastrophic forgetting from the loss geometry viewpoint

A few works have previously harnessed the knowledge of the loss geometry in
theoretical analyses of catastrophic forgetting. Our work is similar in spirit
to Yin et al. (2020), where they study regularisation-based algorithms also
from a loss landscape perspective. They argue that many regularisation
strategies can be interpreted as minimising a local second-order approximation
to the previous tasks’ loss function. Analogously, we argue that many
parameter isolation strategies also inherently rely on a second-order
approximation of the previous tasks’ loss function, thus suggesting a
substantial connection between the regularisation-based and parameter
isolation approaches. Kong et al. (2023) extend the analysis in Yin et al.
(2020) providing an upper-bound on forgetting for regularisation-based
methods, which depends on the number of optimization iterations, the gradient
variance, and the smoothness of the loss function. While Yin et al. (2020) and
Kong et al. (2023) focus on the optimisation of a regularised objective, for
parameter isolation, we can guarantee low levels of forgetting while being
agnostic to the specific optimisation process. In this respect, parameter
isolation strategies can provide stronger guarantees than regularisation-based
methods.

Some empirical works have also investigated the role of geometrical properties
of the found minima in the overall degree of forgetting. Mirzadeh et al.
(2020b) hypothesize that forgetting correlates with the curvature of the loss
function around the minimum, and thus propose to nudge the optimization
algorithm towards wider minima with careful tuning of its hyper-parameters.
Relying on a similar intuition, Deng et al. (2021) introduce a continual
learning algorithm explicitly biased towards flatter valleys of the multitask
loss. Finally, Mirzadeh et al. (2020a) study the relation between the optima
of the continual and multitask settings in the light of recent work on _linear
mode connectivity_ in neural networks (Draxler et al., 2018; Garipov et al.,
2018; Frankle et al., 2020).
Lastly, also related to this work is Bennani et al. (2020), where the authors
analyse the generalisation of OGD in the NTK regime.

##  3 The loss geometry perspective

In this section, we derive a unified framework for parameter isolation
strategies based on a quadratic approximation of the loss function, and in the
next section, we demonstrate that many existing algorithms are special cases
of this framework. We start by the second-order Taylor expansion of forgetting
$\mathcal{E}_{o}(\bm{\theta})$ around task $\mathcal{T}_{o}$ minimum
$\bm{\theta}_{o}$:

$\displaystyle\mathcal{E}_{o}(\bm{\theta})$
$\displaystyle={(\bm{\theta}-\bm{\theta}_{o})}^{\intercal}\bm{\nabla}\mathcal{L}_{o}(\bm{\theta}_{o})+\frac{1}{2}\,{(\bm{\theta}-\bm{\theta}_{o})}^{\intercal}\mathbf{H}_{o}^{\star}(\bm{\theta}-\bm{\theta}_{o})+\bm{O}(\|\bm{\theta}-\bm{\theta}_{o}\|^{3})\,,$
(2)

where,
$\bm{\nabla}\mathcal{L}_{t}(\bm{\theta})=\dfrac{\partial\mathcal{L}_{t}(\bm{\theta})}{\partial\bm{\theta}}$
denotes the $t$-task loss gradient vector and
$\mathbf{H}_{t}(\bm{\theta})=\dfrac{\partial^{2}\mathcal{L}_{t}(\bm{\theta})}{\partial\bm{\theta}{\partial\bm{\theta}}^{\intercal}}$
the $t$-task loss Hessian matrix. For simplicity we shorten
$\mathbf{H}_{t}(\bm{\theta}_{t})$ to $\mathbf{H}_{t}^{\star}$ henceforth.

We make two assumptions: that $\bm{\theta}_{o}$ is a (perhaps local) minimum
and that the algorithm is confined to a region of the parameter space.

######  Assumption 1.

The learning algorithm terminates _in the vicinity_ of a minimum for each
task, i.e. $\|\bm{\nabla}\mathcal{L}_{o}(\bm{\theta}_{o})\|=\epsilon$ and
$\mathbf{H}_{o}^{\star}\succeq 0$, $\forall o\in[T]$, where $\epsilon$ is
arbitrarily close to $0$.

######  Assumption 2.

The task solutions are close in the parameter space, i.e. there exists some
(small) $\delta$ such that
$\max_{i,j\in[T]}\|\bm{\theta}_{i}-\bm{\theta}_{j}\|<\delta$.

Importantly, these two assumptions are widespread in both the theoretical and
empirical literature in continual learning. If they would not be satisfied,
the approximation of the task loss would lose its validity. Yin et al. (2020)
justify the assumptions in light of studies for overparametrised models, whose
loss function appears convex around the minima. However, the validity of these
two assumptions is often not checked empirically. The first assumption is
mostly accurate for gradient descent and the like. Simply, the algorithm will
reach a minimum if run long enough (Lee et al., 2016). The second assumption
is more stringent, however, and thus it can be more easily violated. In this
work, we devote a substantial part of our empirical analysis to the assessment
of Assumption 2, which we consider to be of general interest for the continual
learning literature.
A way to think about Assumption 2 is to consider the multi-task solution
$\bm{\theta}^{\star}$, which trivially satisfies it, being a solution for all
tasks. In general, in light of the work on the connectivity of individual task
solutions (Mirzadeh et al., 2020a), there may exist sets of solutions
$\\{\bm{\theta}_{1},\dots,\bm{\theta}_{T}\\}$ in the same region of the
parameter space. Interestingly, as shown in the next section, Assumption 2 can
be relaxed for some parameter isolation algorithms.

Using these assumptions we can write the average forgetting in a recursive
fashion (full derivations are provided in the Appendix A.1, together with all
the other proofs).

$\displaystyle\mathcal{E}(t)$
$\displaystyle=\frac{1}{t}\,\bigg{(}\,({t-1})\cdot\mathcal{E}(t-1)+\,\frac{1}{2}\bm{\Delta}_{t}^{\intercal}(\sum_{o=1}^{t-1}\mathbf{H}_{o}^{\star})\bm{\Delta}_{t}+\bm{v}^{\intercal}\bm{\Delta}_{t}\,\bigg{)}+\mathcal{O}(\delta\cdot\epsilon)$
(3)

We use $\bm{v}^{\intercal}$ to denote the vector
$\sum_{o=1}^{t-2}(\bm{\theta}_{t-1}-\bm{\theta}_{o})^{\intercal}\mathbf{H}_{o}^{\star}$.
Importantly, $\bm{v}$ does not depend on the last parameter update
$\bm{\Delta}_{t}=\bm{\theta}_{t}-\bm{\theta}_{t-1}$, thus this expression
isolates the contribution to the average forgetting of the update due to a new
task $\mathcal{T}_{t}$. The terms $\epsilon$ and $\delta$ are defined with the
Assumptions 1-2. With this formulation, we are ready to state a first result.

######  Theorem 1 (Null forgetting).

For any continual learning algorithm satisfying Assumptions 1-2 the following
relationship between previous and current forgetting exists:

$\mathcal{E}(1),\dots,\mathcal{E}(t-1)=0\implies\mathcal{E}(t)=\frac{1}{2}\bm{\Delta}_{t}^{\intercal}\bigg{(}\frac{1}{t}\cdot\sum_{o=1}^{t-1}\mathbf{H}_{o}^{\star}\bigg{)}\bm{\Delta}_{t}$

Intuitively, Theorem 1 quantifies forgetting in terms of the parameter
update’s alignment to the _column space_ of the average Hessian
$\overline{\mathbf{H}}^{\star}_{<t}:=\frac{1}{t-1}\cdot\sum_{o=1}^{t-1}\mathbf{H}_{o}^{\star}$.
An immediate consequence of this statement is that the rank of the average
Hessian (ranging from $0$ to $P$) gives us as a rough measure of the number of
dimensions in the parameter space already “in use” by the first $t-1$ tasks.
We include in Appendix A.2 an empirical assessment of the growth of
$\operatorname{rank}(\overline{\mathbf{H}}^{\star}_{<t})$ as a function of
$t$.
Furthermore, unrolling Theorem 1 from $t=1$ to $t=T$ it is straightforward to
devise a constraint on the parameter update enforcing $\mathcal{E}(t)=0$ for
all $t\in[T]$. The following Theorem introduces this constraint.

######  Theorem 2 (Null-forgetting constraint).

Let $\mathcal{A}:[T]\to\Theta$ be a continual learning algorithm satisfying
Assumptions 1-2, and $\mathcal{A}(t):=\bm{\Delta}_{t}$. Then
$\mathcal{E}_{\tau}(t)=0$ $\forall\,\,\tau<t$ if and only if:

$\bm{\Delta}_{t}^{\intercal}(\sum_{o=1}^{t-1}\mathbf{H}_{o}^{\star})\bm{\Delta}_{t}=0$
(4)

Simply put, enforcing the constraint in Equation 4 guarantees zero or null
forgetting as long as the assumptions are met. In the next section we argue
that parameter isolation algorithms embody variations of this constraint.
Before moving on to the next section we make two remarks.
First, that there’s an intuitive explanation of Theorem 2: when a quadratic
approximation to the loss is accurate enough, simply constraining the
parameter updates to directions along which the multi-task loss landscape is
flat will prevent forgetting. Importantly, the sharper the old tasks minima,
the more stringent the constraint, which explains the recent interest in flat
minima for continual learning (Deng et al., 2021; Mirzadeh et al., 2020a).
Second, it is easy to show that, if Assumptions 1-2 are satisfied,
$\min\mathcal{E}(t)=0$ for all $t\in[T]$. Thus, enforcing Equation 4
effectively minimises forgetting in the quadratic regime. In Appendix A.2 we
consider the case where $\mathcal{E}_{\tau}(t)>0$ for some $\tau<t$, and we
derive a new constraint to achieve $\mathcal{E}(t)=0$.

##  4 A unified view of parameter isolation methods

We now discuss how several existing algorithms such as OGD (Farajtabar et al.,
2020), GPM (Saha et al., 2021), PackNet (Mallya & Lazebnik, 2018) and
Progressive Networks (Rusu et al., 2016) can be understood as variants of our
framework. For _general_ parameter isolation methods the connection is less
obvious, and thus we carry out a meticulous analysis of these cases.
Conversely, we deem it sufficient to discuss the link to _strict_ parameter
isolation intuitively, using an informal proof sketch.

###  4.1 Orthogonal Gradient Descent

Let
$D_{o}=\\{(\bm{x}_{1,o},{y_{1,o}}),\cdots,(\bm{x}_{n_{o},o},{y_{n_{o},o}}))\\}$
be the dataset associated with task $\mathcal{T}_{o}$, where $y\in[C]$. For
any input $\bm{x}$, we denote the network output as
$\bm{f}_{\bm{\theta}}(\bm{x})\in\mathbb{R}^{C}$. The gradient of the network
output with respect to the network parameters is the $P\times C$ matrix
$\nabla_{\bm{\theta}}\bm{f}_{\bm{\theta}}(\bm{x})=\left[\nabla_{\bm{\theta}}\bm{f}^{1}_{\bm{\theta}}(\bm{x}),\,\cdots\,,\nabla_{\bm{\theta}}\bm{f}^{C}_{\bm{\theta}}(\bm{x})\right]$,
where $P$ is the network size. The standard version of OGD imposes the
following constraint on any parameter update $\bm{u}$:

$\langle\bm{u},\nabla_{\bm{\theta}}\bm{f}^{c}_{\bm{\theta}_{o}}(\bm{x}_{i,o})\rangle=0\,\,\,\,\,\forall\,c\in[C],\bm{x}_{i,o}\in
D_{o},o<t,$ (5)

$t$ being the number of tasks solved so far. Our first result is that this
constraint is equivalent to the _null-forgetting_ constraint of Equation 4
whenever Assumption 1 is satisfied.

######  Theorem 3.

Let $\mathcal{A}:[T]\to\Theta$ be a continual learning algorithm satisfying
Assumption 1. If $\mathcal{A}(t)=\bm{\Delta}_{t}$ satisfies Equation 5, then
it satisfies Equation 4.

Importantly, Assumption 2 is not necessary for this result. However, it is
necessary to guarantee $\mathcal{E}(t)=0$ given that the constraint is
satisfied. As a consequence of this result, we obtain _null-forgetting_
guarantees for OGD in the regime described by Assumptions 1-2.

######  Corollary 1 (Null-forgetting guarantees for OGD).

Let $\mathcal{A}:[T]\to\Theta$ be a continual learning algorithm satisfying
Assumptions 1-2. If $\mathcal{A}(t)=\bm{\Delta}_{t}$ satisfies Equation 5 for
all $t\in[T]$, then $\mathcal{E}(t)=0\,\forall t\in[T]$.

###  4.2 Gradient Projection Memory

GPM stores in its memory layer-wise activation vectors for each task. Let
$\bm{x}^{l}_{t}=\sigma(\bm{W}^{l-1^{\intercal}}\bm{x}^{l-1}_{t})$ be the
representation of $\bm{x}_{t}$ at the $l$-th layer of the network
($\bm{x}^{0}_{t}=\bm{x}_{t}$). The GPM algorithm enforces the following
constraint on the weight matrix update $\bm{\Delta}\bm{W}^{l}$:

$\langle\bm{\Delta}\bm{W}^{l},\bm{x}^{l}_{o}\rangle=0\,\,\,\,\forall\,\bm{x}_{o}\in
D_{o},o<t$ (6)

We first show that the GPM constraint is equivalent to the _null-forgetting_
constraint of Equation 4 when Assumption 1 is valid and if the Hessian matrix
is _block-diagonal_.

######  Theorem 4.

Let $\mathcal{A}:[T]\to\Theta$ be a continual learning algorithm satisfying
Assumption 1. If $\bm{H}^{\star}_{o}$ is _block-diagonal_ for all $o\in[T]$,
then if $\mathcal{A}(t)=\bm{\Delta}_{t}$ satisfies Equation 6 it also
satisfies Equation 4.

Next, we move on to show a more general result for GPM, namely that it
satisfies the _null-forgetting_ constraint with respect to a quadratic
approximation of the multi-task loss at every point in the optimization path.
As a consequence, we obtain null-forgetting guarantees for GPM _everywhere in
the parameter space_ , i.e. notwithstanding Assumptions 1-2.

######  Theorem 5.

Let $\mathcal{A}:[T]\to\Theta$ be a continual learning algorithm for a _ReLU_
network and
$\mathcal{A}(t)=\bm{\Delta}_{t}=\sum_{i=1}^{S_{t}}\bm{\delta}_{t}^{(i)}$.
Moreover, let $\\{\bm{\theta}_{t-1\to t}^{(1)},\dots,\bm{\theta}_{t-1\to
t}^{(S_{t})}\\}$ be the points on the optimization path from task $t-1$ to
task $t$ ($\bm{\theta}_{t-1\to t}^{(S_{t})}=\bm{\theta}_{t}$). If Equation 6
is satisfied for all $\\{\bm{\delta}_{t}^{(s)}:s<i\\}$ then $\forall\,o<t$ it
holds that:

$\displaystyle\nabla\mathcal{L}_{o}(\bm{\theta}_{t-1\to
t}^{(i-1)})^{\intercal}\bm{\delta}_{t}^{(i)}=0$ (7)
$\displaystyle{\bm{\delta}_{t}^{(i)}}^{\intercal}\operatorname{block-
diag}(\mathbf{H}_{o}(\bm{\theta}_{t-1\to
t}^{(i-1)}))\,\bm{\delta}_{t}^{(i)}=0$

where $\operatorname{block-diag}(\cdot)$ denotes the layer-wise block-diagonal
Hessian, i.e., $\operatorname{block-
diag}(\mathbf{H})_{i,j}:=\mathbf{H}_{i,j}\,\cdot\,\mathbbm{1}\\{{\text{layer}(\theta_{i})=\text{layer}(\theta_{j})\\}}$.

The constraints in Equation 7 represent the natural generalisation of the
null-forgetting constraint to the case where Assumptions 1-2 are not valid.
Importantly, this result only holds for _ReLU_ networks, and it relies on the
Hessian being block diagonal. In the Appendix C we verify empirically the
extent to which this condition is met in practice.

######  Corollary 2 (Null-forgetting guarantees for GPM).

Let $\mathcal{A}:[T]\to\Theta$ be a continual learning algorithm for a _ReLU_
-network satisfying Equation 6. If $\operatorname{block-
diag}(\mathbf{H}_{o}(\bm{\theta}))=\mathbf{H}_{o}(\bm{\theta})$ for all
$\bm{\theta}\in\Theta$, then $\mathcal{E}(t)=0\,\,\forall\,t\in[T]$.

###  4.3 Strict parameter isolation

As stated above, the algorithms belonging to this category partition the
network by assigning different parameter sets to different tasks. The high-
level intuition is that partitioning the network parameters inevitably entails
orthogonality between the current task parameter update and previous tasks’
updates, thus enforcing Equation 4.

More specifically, PackNet (Mallya & Lazebnik, 2018) selects a small set of
task-specific parameters by pruning after training on the task in question.
Alternatively, SpaceNet (Van Etten et al., 2018) directly trains a dynamically
allocated subset of the network parameters for each task by enforcing
sparsity. Finally Progressive Networks (Rusu et al., 2016) or other similar
approaches known in the literature as _network expansion_ methods, add new
parameters to the network for each new task.
All these methods then freeze the parameter sets pertaining to previous tasks
when learning a new task. Formally, freezing corresponds to applying the
following transformation to the gradient vector:
$\tilde{\nabla}\mathcal{L}_{t}(\bm{\theta})\leftarrow\bm{m}_{t}\circ\nabla\mathcal{L}_{t}(\bm{\theta})$,
where $\bm{m}_{t}$ is a binary mask $(\bm{m}_{t})_{i}=0$ for any $i$ in the
index set of a previous task $\mathcal{I}_{<t}$ and $\circ$ denotes Hadamard-
product. Similarly, the transformation applied to the Hessian matrix is:
$\tilde{\bm{H}}_{t}(\bm{\theta})\leftarrow\bm{M}_{t}\circ\bm{H}_{t}(\bm{\theta})$,
where $\bm{M}_{t}=\bm{m}_{t}\cdot\bm{m}_{t}^{\intercal}$. Consequently,
$\tilde{\nabla}\mathcal{L}_{t}(\bm{\theta})\perp\tilde{\nabla}\mathcal{L}_{o}(\bm{\theta}_{o})$
and
$\tilde{\nabla}\mathcal{L}_{t}(\bm{\theta})^{\intercal}\tilde{\bm{H}}_{o}^{\star}\tilde{\nabla}\mathcal{L}_{t}(\bm{\theta})={0}$.
It readily follows that $\mathcal{E}_{o}(t)=0$ under Assumption 2. The result
carries over to the general setting described by Theorem 5 in a similar
fashion, upon incorporating additional details from the algorithms.

##### Enforcing sparsity

Sparsity-enforcing algorithms (Schwarz et al., 2021; Abbasi et al., 2022)
constitute a special case in the parameter isolation family, as sparsity can
be seen as a softer network partitioning method. As an example, Abbasi et al.
(2022) enforce sparsity on the neural activations using a _$k$ -winner_
activation function and _heterogenous dropout_ : in practice, with high
probability, the layer-wise activation vectors between different tasks are
orthogonal, i.e. $\langle\bm{x}_{o}^{l},\bm{x}_{t}^{l}\rangle=0$ for any pair
$(o,t)$, where $\bm{x}_{o}\in D_{o}$ and $\bm{x}_{t}\in D_{t}$. Is is easy to
see (cf. Equation 14 in the Appendix) that this condition implies that the
gradient with respect to the input weight matrix $\bm{W}^{l-1}$ is orthogonal
to the previous neural activations subspace, i.e.
$\nabla_{\bm{W}^{l-1}}\mathcal{L}_{t}\,\bm{x}_{o}^{l}=\bm{0}$, which
corresponds to the GPM constraint (Equation 6). However, since the constraint
is only met in probability, this algorithm can only offer probabilistic
guarantees.

##  5 Experiments and results

In this section, we present experimental results validation our theoretical
findings. First, we assess the validity of Assumption 2, and evaluate the
accuracy of a quadratic approximation of the loss. Then we validate two claims
hidden in our findings: (1) that that OGD and GPM are essentially equivalent
to enforcing the _null-forgetting_ constraint when Assumptions 1-2 are met and
(2) that our results are agnostic of the architecture or the number of tasks.

Experimental setup. For all experiments, we report the mean and standard
deviation over $5$ runs with different seeds. For brevity, the detailed
instructions for reproducing the results are in Appendix B. To facilitate the
results’ interpretation, we report forgetting in terms of accuracy. Moreover,
we always measure forgetting on the test data.

Datasets. We perform our experiments on standard continual learning
benchmarks. Namely, Rotated MNIST, Split CIFAR-10 and Split CIFAR-100. Rotated
MNIST consists of a sequence of $5$ tasks, each obtained by applying a fixed
image rotation to the MNIST dataset. To avoid an additional source of
randomness in the experiments, we fix the set of rotations. The split
challenges are obtained by partitioning the dataset’s classes into separate
tasks. We split CIFAR-10 and CIFAR-100 into $5$ and $20$ tasks respectively.

Networks. For the experiments on Rotated MNIST we are able to compute the full
Hessian matrix and its eigen-decomposition. We use a small feed-forward neural
network with $3$ hidden layers of width $50$ and we downscale the input image
to $14\times 14$. In addition, we perform experiments on a convolutional
neural network, a ResNet 18 (He et al., 2016) and a Vision Transformer, ViT,
(Dosovitskiy et al., 2020) (see Section 5.3). For these larger networks we use
deflated power iteration (Yao et al., 2018b) for computing the top-$k$
eigenvectors of the Hessian.

###  5.1 Empirical assessment of the validity of a local quadratic
approximation of the loss

Many theoretical and empirical works in continual learning rely on a quadratic
approximation of the loss function around the old tasks optima. Yin et al.
(2020) show that this is the case for the regularisation family, and in this
work we have argued that it also holds for some methods in the parameter
isolation family. In this section we question this assumption, empirically
testing its limits.

Table 1: Approximation error, Equation 2 | lr |  $1^{\text{st}}$ order |  $2^{\text{nd}}$ order | Taylor | $\mathcal{E}_{o}(t)$ | $\|\bm{\theta}_{t}-\bm{\theta}_{o}\|$
---|---|---|---|---|---|---
$o\,{\in[1,t-1]}$ | $1e^{-5}$ | ${0.43}\pm 0.30$ | ${0.26}\pm 0.16$ | $\bm{0.15}\pm 0.15$ | $0.30\pm 0.30$ | $1.23\pm 0.51$
$1e^{-2}$ | $2.33\pm 1.87$ | $\bm{1.49}\pm 1.31$ | $1.55\pm 1.32$ | $2.26\pm 1.85$ | $8.19\pm 2.56$

First, we measure the accuracy of the second order Taylor approximation
(Equation 2) to predict $\mathcal{E}_{o}(t)$ for $t=1,\dots,T$. In Table 1 we
report the prediction error $|\hat{\mathcal{E}}_{o}(t)-\mathcal{E}_{o}(t)|$
for SGD using a low and high learning rate on the Rotated-MNIST challenge.
In general, the approximation is more accurate for low learning rates, which
limit the update norm (cf. $\|\bm{\theta}_{t}-\bm{\theta}_{o}\|$ in Table 1).
Moreover, in Table 1 we inspect the contribution of the first- and second-
order terms to the prediction. Remarkably, the second-order term achieves the
lowest error on average in the high learning rate case. We conjecture that
this effect is due to the faster rate of convergence of the second-order
derivatives of the loss while training (Gur-Ari et al., 2018), which leads to
more stable estimates across an extended region of the landscape, as compared
to the high variance of the gradient vectors.
Unfortunately, we cannot evaluate the approximation accuracy in this way for
larger networks since computing the Hessian matrix is expensive. We thus
devise another experiment which can be carried out on larger networks as well.

##### Perturbation analysis

Figure 2: Perturbation score $\mathfrak{s}(r)$ varying the radius $r$ on a
logarithmic scale in the range $[10^{-3},10^{4}]$ on different tasks from
different challenges. The challenges are solved from left to right
respectively with an MLP, a ViT and a ResNet. The confidence intervals display
the uncertainty over $5$ seeds. The dashed green line highlights the value of
$r$ for which the score converges to $1$ (marked by the dashed brown line).

With this experiment we measure the extent to which Assumption 2 can
effectively be violated. We perturb a task solution $\bm{\theta}_{t}$ along
the Hessian principle eigenvectors $\bm{v}_{i}$ and along random directions
$\bm{\mu}\sim\mathcal{N}(0,\bm{I}_{P})$, controlling the radius of the
perturbation through a parameter $r$. We then compare the effect on the loss
function through the following score:

$\mathfrak{s}(r)=\frac{|\mathcal{L}_{t}(\bm{\theta}_{t}+r\cdot\bm{v}_{i})-\mathcal{L}_{t}(\bm{\theta}_{t})|}{\mathbb{E}_{\bm{\mu}}\left[|\mathcal{L}_{t}(\bm{\theta}_{t}+r\cdot\bm{\mu}^{\prime})-\mathcal{L}_{t}(\bm{\theta}_{t})|\right]}$

where $\bm{\mu}^{\prime}:=\frac{\bm{\mu}}{||\bm{\mu}||}$. In Figure 2 we plot
$\mathfrak{s}(r)$ for several values of $r$ on some tasks of the three
challenges we consider. More plots can be found in Appendix C. Interestingly,
the same trend can be observed across tasks and across architectures. These
observations confirm that in a ball around the optimum the loss Hessian
principal eigenvectors represent the directions where the loss landscape is
steeper, and, conversely, that outside of this ball the second order
approximation to the loss breaks down. These empirical results suggest that
local quadratic approximations are still accurate reasonably far away from
their center, however they also show their tangible limits. Importantly,
across tasks and random seeds the size of the ball $B$ appears to be stable,
while increasing proportionally to the network size. Investigating this effect
further is outside of the scope of this analysis, however the use of tools
such as the _perturbation analysis_ may help us gain insights into still
unknown geometric properties of the loss landscapes.

###  5.2 OGD and GPM satisfy the null-forgetting constraint

We augment SGD with a projection step, enforcing orthogonality to the first
$k$ eigenvectors of the Hessian of each task. We refer to the augmented
version of SGD as $\operatorname{SGD}^{\dagger}$. In formula:

$\displaystyle\operatorname{SGD}:\bm{\theta}^{\prime}\leftarrow\bm{\theta}-\eta\bm{g}\,\quad\text{and}\quad\operatorname{SGD}^{\dagger}:\bm{\theta}^{\prime}\leftarrow\bm{\theta}-\eta(\bm{I}-\bm{M}\bm{M}^{\intercal})\bm{g},$
(8)

where $\bm{g}$ represents the batch gradient vector of the current task
$\mathcal{T}_{t}$, and $\bm{M}$ is a basis for
$\operatorname{span}(\\{\bm{v}_{1}^{o},\dots,\bm{v}_{k}^{o}\
|\,o\in[1,t-1],\bm{v}_{i}^{o}:=i\text{-th eigenvector of
}\mathbf{H}_{o}^{\star}\\})$. We follow the choice by Saha et al. (2021) to
determine $k$ dynamically as a function of the spectral energy of
$\mathbf{H}_{o}^{\star}$, modifying OGD accordingly. Intuitively, we consider
the first $(1-\epsilon)$ fraction of the Hessian spectral energy. We refer the
reader to Appendix B for further details. Importantly, since SGD† operates
with the Hessian matrix at the task optimum, it will not work when Assumption
2 is violated.

We evaluate GPM, OGD and SGD† on the Rotated-MNIST challenge against the SGD
baseline. In order to compare the case in which Assumption 2 holds against the
case in which it doesn’t we train the models twice, changing the learning rate
from $0.01$ to $10^{-5}$, while keeping the number of epochs fixed.
Additionally, in the Appendix C we also evaluate Equation 4 for OGD and GPM.

Figure 3: Comparison of all the methods in the high (left) and low (right)
learning rate (lr) setting. On the $y$ axes, the accuracy average forgetting.
Notice that the levels of forgetting are overall lower in the low learning
rate setting.

We plot the results in Figure 3. When the learning rate is high, OGD and SGD†,
which rely on Assumption 2, perform similarly to SGD. In line with our
theoretical findings, we observe low forgetting for GPM in both regimes. When
the learning rate is low the three methods are equivalent. These results
confirm our theoretical findings that OGD and GPM can be explained by the
constraint in Equation 4.

###  5.3 Results for other architectures

The power of a theory is commensurate with its predictive scope. In this last
section we want to demonstrate that our theoretical findings are not bound to
any specific architecture, or any fixed number of tasks. In order to do so we
would like to use SGD† to train a convolutional or transformer network.
However, enforcing Equation 4 is too computationally expensive on any network
of decent size. Therefore we instead enforce an approximation of Equation 4
using only the first $10$ or $20$ eigenvectors of each task Hessian matrix: we
refer to these approximation respectively as SGD†-10 and SGD†-20.
Moreover, in order to satisfy Assumption 2 we again train with a low learning
rate ($0.001$). Overall, this training setup is suboptimal in many respects
(performance, computation, memory) and it is designed specifically to validate
the theoretical findings. Examples of efficient algorithms implementing the
null-forgetting constraint are OGD, GPM and the other algorithms discussed,
and competing with existing algorithms is not a goal of this study.

Network | Algorithm | CIFAR-10 ($\mathcal{E}(5)$) | CIFAR-100 ($\mathcal{E}(20)$)
---|---|---|---
ResNet | SGD | $0.025\pm 0.034$ | $0.29\pm 0.14$
SGD†-$10$ | $0.017\pm 0.024$ | $0.22\pm 0.14$
SGD†-$20$ | $\bm{0.014}\pm 0.021$ | $\bm{0.16}\pm 0.12$
ViT | SGD | $0.031\pm 0.044$ | $0.25\pm 0.13$
SGD†-$10$ | $0.007\pm 0.014$ | $0.16\pm 0.13$
SGD†-$20$ | $\bm{0.006}\pm 0.014$ | $\bm{0.11}\pm 0.11$
Table 2: Average forgetting $\mathcal{E}(T)$ measured in terms of accuracy of
SGD and SGD† with varying values of $k$ on Split CIFAR-10 ($T=5$) and Split
CIFAR-100 ($T=20$). The relatively high variance is partly due to the
randomness inherent in the iterative eigen-decomposition process.

The results are summarised in Table 2, and an extended version can be found in
Appendix C. We observe a reduction in final forgetting when using SGD† during
training. Importantly, this reduction is visible regardless of the
architecture or the number of tasks ($5$ or $20$) to be solved, suggesting
that the null-forgetting constraint is valid for different settings.
SGD†-10 or -20 implement a significantly low-rank approximation of the Hessian
matrix, given that its dimension is $P\times P$ and $P$ can be in the order of
$10^{6}$. The fact that the effect is stronger when using $20$ instead of $10$
dimensions confirms that the quality of the Hessian approximation plays a role
in the effectiveness of the constraint.

##  6 Conclusion

We propose a unified theoretical framework for parameter isolation strategies
in continual learning, based on a quadratic loss approximation perspective. We
show that many existing parameter isolation algorithms are special cases of
our framework, thereby providing theoretical grounding for them. Furthermore,
we use this framework to establish guarantees on catastrophic forgetting for
two such algorithms. Our results also highlight a non trivial connection of
parameter isolation and regularisation-based algorithms, which we invite
future research to explore.

## References

  * Abbasi et al. (2022) Ali Abbasi, Parsa Nooralinejad, Vladimir Braverman, Hamed Pirsiavash, and Soheil Kolouri.  Sparsity and heterogeneous dropout for continual learning in the null space of neural activations.  In _Conference on Lifelong Learning Agents_ , pp. 617–628. PMLR, 2022.
  * Bennani et al. (2020) Mehdi Abbana Bennani, Thang Doan, and Masashi Sugiyama.  Generalisation guarantees for continual learning with orthogonal gradient descent.  _arXiv preprint arXiv:2006.11942_ , 2020.
  * De Lange et al. (2021) Matthias De Lange, Rahaf Aljundi, Marc Masana, Sarah Parisot, Xu Jia, Aleš Leonardis, Gregory Slabaugh, and Tinne Tuytelaars.  A continual learning survey: Defying forgetting in classification tasks.  _IEEE transactions on pattern analysis and machine intelligence_ , 44(7):3366–3385, 2021.
  * Deng et al. (2021) Danruo Deng, Guangyong Chen, Jianye Hao, Qiong Wang, and Pheng-Ann Heng.  Flattening sharpness for dynamic gradient projection memory benefits continual learning.  _Advances in Neural Information Processing Systems_ , 34:18710–18721, 2021.
  * Dosovitskiy et al. (2020) Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al.  An image is worth 16x16 words: Transformers for image recognition at scale.  _arXiv preprint arXiv:2010.11929_ , 2020.
  * Draxler et al. (2018) Felix Draxler, Kambis Veschgini, Manfred Salmhofer, and Fred Hamprecht.  Essentially no barriers in neural network energy landscape.  In _International conference on machine learning_ , pp. 1309–1318. PMLR, 2018.
  * Ebrahimi et al. (2019) Sayna Ebrahimi, Mohamed Elhoseiny, Trevor Darrell, and Marcus Rohrbach.  Uncertainty-guided continual learning with bayesian neural networks.  _arXiv preprint arXiv:1906.02425_ , 2019.
  * 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_ , pp. 3762–3773. PMLR, 2020.
  * Frankle et al. (2020) Jonathan Frankle, Gintare Karolina Dziugaite, Daniel Roy, and Michael Carbin.  Linear mode connectivity and the lottery ticket hypothesis.  In _International Conference on Machine Learning_ , pp. 3259–3269. PMLR, 2020.
  * Garipov et al. (2018) Timur Garipov, Pavel Izmailov, Dmitrii Podoprikhin, Dmitry P Vetrov, and Andrew G Wilson.  Loss surfaces, mode connectivity, and fast ensembling of dnns.  _Advances in neural information processing systems_ , 31, 2018.
  * Golmant et al. (2018) Noah Golmant, Zhewei Yao, Amir Gholami, Michael Mahoney, and Joseph Gonzalez.  pytorch-hessian-eigenthings: efficient pytorch hessian eigendecomposition, October 2018.  URL https://github.com/noahgolmant/pytorch-hessian-eigenthings.
  * Guo et al. (2022) Yiduo Guo, Bing Liu, and Dongyan Zhao.  Online continual learning through mutual information maximization.  In _International Conference on Machine Learning_ , pp. 8109–8126. PMLR, 2022.
  * Gur-Ari et al. (2018) Guy Gur-Ari, Daniel A Roberts, and Ethan Dyer.  Gradient descent happens in a tiny subspace.  _arXiv preprint arXiv:1812.04754_ , 2018.
  * He et al. (2016) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 770–778, 2016.
  * Hsu et al. (2018) Yen-Chang Hsu, Yen-Cheng Liu, Anita Ramasamy, and Zsolt Kira.  Re-evaluating continual learning scenarios: A categorization and case for strong baselines.  _arXiv preprint arXiv:1810.12488_ , 2018.
  * Kang et al. (2022) Haeyong Kang, Rusty John Lloyd Mina, Sultan Rizky Hikmawan Madjid, Jaehong Yoon, Mark Hasegawa-Johnson, Sung Ju Hwang, and Chang D Yoo.  Forget-free continual learning with winning subnetworks.  In _International Conference on Machine Learning_ , pp. 10734–10750. PMLR, 2022.
  * Khetarpal et al. (2022) Khimya Khetarpal, Matthew Riemer, Irina Rish, and Doina Precup.  Towards continual reinforcement learning: A review and perspectives.  _Journal of Artificial Intelligence Research_ , 75:1401–1476, 2022.
  * Kirkpatrick et al. (2017) James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei A Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Grabska-Barwinska, et al.  Overcoming catastrophic forgetting in neural networks.  _Proceedings of the national academy of sciences_ , 114(13):3521–3526, 2017.
  * Kong et al. (2023) Yajing Kong, Liu Liu, Huanhuan Chen, Janusz Kacprzyk, and Dacheng Tao.  Overcoming catastrophic forgetting in continual learning by exploring eigenvalues of hessian matrix.  _IEEE Transactions on Neural Networks and Learning Systems_ , 2023.
  * Lee et al. (2016) Jason D Lee, Max Simchowitz, Michael I Jordan, and Benjamin Recht.  Gradient descent converges to minimizers.  _arXiv preprint arXiv:1602.04915_ , 2016.
  * Lin et al. (2022) Sen Lin, Li Yang, Deliang Fan, and Junshan Zhang.  Trgp: Trust region gradient projection for continual learning.  _arXiv preprint arXiv:2202.02931_ , 2022.
  * Lopez-Paz & Ranzato (2017) David Lopez-Paz and Marc’Aurelio Ranzato.  Gradient episodic memory for continual learning.  _Advances in neural information processing systems_ , 30, 2017.
  * Mallya & Lazebnik (2018) Arun Mallya and Svetlana Lazebnik.  Packnet: Adding multiple tasks to a single network by iterative pruning.  In _Proceedings of the IEEE conference on Computer Vision and Pattern Recognition_ , pp. 7765–7773, 2018.
  * McCloskey & 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, pp. 109–165. Elsevier, 1989.
  * Mirzadeh et al. (2020a) 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_ , 2020a.
  * Mirzadeh et al. (2020b) Seyed Iman Mirzadeh, Mehrdad Farajtabar, Razvan Pascanu, and Hassan Ghasemzadeh.  Understanding the role of training regimes in continual learning.  _Advances in Neural Information Processing Systems_ , 33:7308–7320, 2020b.
  * Nguyen et al. (2017) Cuong V Nguyen, Yingzhen Li, Thang D Bui, and Richard E Turner.  Variational continual learning.  _arXiv preprint arXiv:1710.10628_ , 2017.
  * Rebuffi et al. (2017) Sylvestre-Alvise Rebuffi, Alexander Kolesnikov, Georg Sperl, and Christoph H Lampert.  icarl: Incremental classifier and representation learning.  In _Proceedings of the IEEE conference on Computer Vision and Pattern Recognition_ , pp. 2001–2010, 2017.
  * Ritter et al. (2018) Hippolyt Ritter, Aleksandar Botev, and David Barber.  Online structured laplace approximations for overcoming catastrophic forgetting.  _Advances in Neural Information Processing Systems_ , 31, 2018.
  * Rusu et al. (2016) Andrei A Rusu, Neil C Rabinowitz, Guillaume Desjardins, Hubert Soyer, James Kirkpatrick, Koray Kavukcuoglu, Razvan Pascanu, and Raia Hadsell.  Progressive neural networks.  _arXiv preprint arXiv:1606.04671_ , 2016.
  * Sagun et al. (2016) Levent Sagun, Leon Bottou, and Yann LeCun.  Eigenvalues of the hessian in deep learning: Singularity and beyond.  _arXiv preprint arXiv:1611.07476_ , 2016.
  * Sagun et al. (2017) Levent Sagun, Utku Evci, V Ugur Guney, Yann Dauphin, and Leon Bottou.  Empirical analysis of the hessian of over-parametrized neural networks.  _arXiv preprint arXiv:1706.04454_ , 2017.
  * Saha et al. (2021) Gobinda Saha, Isha Garg, and Kaushik Roy.  Gradient projection memory for continual learning.  _arXiv preprint arXiv:2103.09762_ , 2021.
  * Schraudolph (2002) Nicol N Schraudolph.  Fast curvature matrix-vector products for second-order gradient descent.  _Neural computation_ , 14(7):1723–1738, 2002.
  * Schwarz et al. (2021) Jonathan Schwarz, Siddhant Jayakumar, Razvan Pascanu, Peter E Latham, and Yee Teh.  Powerpropagation: A sparsity inducing weight reparameterisation.  _Advances in neural information processing systems_ , 34:28889–28903, 2021.
  * Shin et al. (2017) Hanul Shin, Jung Kwon Lee, Jaehong Kim, and Jiwon Kim.  Continual learning with deep generative replay.  _Advances in neural information processing systems_ , 30, 2017.
  * Singh et al. (2021) Sidak Pal Singh, Gregor Bachmann, and Thomas Hofmann.  Analytic insights into structure and rank of neural network hessian maps.  _Advances in Neural Information Processing Systems_ , 34:23914–23927, 2021.
  * Singh et al. (2023) Sidak Pal Singh, Thomas Hofmann, and Bernhard Schölkopf.  The hessian perspective into the nature of convolutional neural networks.  _arXiv preprint arXiv:2305.09088_ , 2023.
  * Van de Ven et al. (2020) Gido M Van de Ven, Hava T Siegelmann, and Andreas S Tolias.  Brain-inspired replay for continual learning with artificial neural networks.  _Nature communications_ , 11(1):4069, 2020.
  * Van Etten et al. (2018) Adam Van Etten, Dave Lindenbaum, and Todd M Bacastow.  Spacenet: A remote sensing dataset and challenge series.  _arXiv preprint arXiv:1807.01232_ , 2018.
  * Wortsman et al. (2020) Mitchell Wortsman, Vivek Ramanujan, Rosanne Liu, Aniruddha Kembhavi, Mohammad Rastegari, Jason Yosinski, and Ali Farhadi.  Supermasks in superposition.  _Advances in Neural Information Processing Systems_ , 33:15173–15184, 2020.
  * Xu et al. (2018) Peng Xu, Bryan He, Christopher De Sa, Ioannis Mitliagkas, and Chris Re.  Accelerated stochastic power iteration.  In _International Conference on Artificial Intelligence and Statistics_ , pp. 58–67. PMLR, 2018.
  * Yao et al. (2018a) Zhewei Yao, Amir Gholami, Daiyaan Arfeen, Richard Liaw, Joseph Gonzalez, Kurt Keutzer, and Michael Mahoney.  Large batch size training of neural networks with adversarial training and second-order information.  _arXiv preprint arXiv:1810.01021_ , 2018a.
  * Yao et al. (2018b) Zhewei Yao, Amir Gholami, Qi Lei, Kurt Keutzer, and Michael W Mahoney.  Hessian-based analysis of large batch training and robustness to adversaries.  _Advances in Neural Information Processing Systems_ , 31, 2018b.
  * Yin et al. (2020) Dong Yin, Mehrdad Farajtabar, Ang Li, Nir Levine, and Alex Mott.  Optimization and generalization of regularization-based continual learning: a loss approximation viewpoint.  _arXiv preprint arXiv:2006.10974_ , 2020.
  * Yoon et al. (2017) Jaehong Yoon, Eunho Yang, Jeongtae Lee, and Sung Ju Hwang.  Lifelong learning with dynamically expandable networks.  _arXiv preprint arXiv:1708.01547_ , 2017.
  * Zenke et al. (2017) Friedemann Zenke, Ben Poole, and Surya Ganguli.  Continual learning through synaptic intelligence.  In _International conference on machine learning_ , pp. 3987–3995. PMLR, 2017.

Appendix

This document contains the materials supporting and extending the discussion
in the main text. It is organised as follows:

  * •

Appendix A collects the proofs to all the Theorems and Corollaries of the main
text. Additionally, we elaborate further observations derived from our
theoretical framework.

  * •

Appendix B provides all the details of our experimental setup.

  * •

Appendix C gathers additional results supporting the experiments described in
the main text.

Figure 4: The multitask solution for the toy challenge in Figure 1. The same
network has been used. This demonstrates that a multitask solution exists,
despite standard optimization algorithms are not able to find it.

##  Appendix A Proofs and Further discussion

####  A.0.1 Notation and formalism

First, we shortly recap the notation and formalism introduced in our
discussion.

We consider a sequence of supervised learning tasks
$\mathcal{T}_{1},\dots,\mathcal{T}_{T}$, each associated with a dataset
${D}_{t}=\\{(x_{1},y_{1}),\dots,(x_{n_{t}},y_{n_{t}})\\}$, where
$(x,y)\in\mathcal{X}\times\mathcal{Y}_{t}$. We describe a neural network by
its set of parameters $\Theta_{t}\subseteq\mathbb{R}^{P}$, $P$ denoting the
total number of parameters in the network. We tipically use the index $t$ to
refer to the task currently being learned and $o$ to a general previous task.

We use bold to indicate a vector or a matrix, e.g. $\bm{0}$ is the null
vector. $\bm{\theta}$ refers to a general value taken by the parameters, and
$\bm{\theta}_{t}$ is the solution found on task $\mathcal{T}_{t}$. Moreover,
we write $\bm{\Delta}_{t}:=\bm{\theta}_{t}-\bm{\theta}_{t-1}$, i.e. the update
to the parameters following task $\mathcal{T}_{t}$. Simply,
$\bm{\Delta}_{0}=\bm{0}$, $\bm{\theta}_{0}$ being the initialisation point.

We use $l_{t}(x,y,\bm{\theta})$ to denote the $t$-th task loss function, and
write the average loss over the dataset as $\mathcal{L}_{t}(\bm{\theta})$,
i.e.
$\mathcal{L}_{t}(\bm{\theta})=\frac{1}{n_{t}}\sum_{i=1}^{n_{t}}l_{t}(x_{i},y_{i},\bm{\theta})$.
We shorten the loss measured at the end of training
$\mathcal{L}_{t}(\bm{\theta}_{t})$ to $\mathcal{L}_{t}^{\star}$.

The vector of first-order derivatives or gradient of the loss with respect to
the parameters $\bm{\theta}$ is
$\bm{\nabla}\mathcal{L}_{t}(\bm{\theta})=\frac{\partial\mathcal{L}_{t}(\bm{\theta})}{\partial\bm{\theta}}$
and the matrix of second-order-derivativatives or Hessian of the loss with
respect to the parameters $\bm{\theta}$ is
$\mathbf{H}_{t}(\bm{\theta})=\frac{\partial^{2}\mathcal{L}_{t}(\bm{\theta})}{\partial\bm{\theta}^{2}}$.
In the interest of space, we shorten the Hessian evaluated at the end of
training $\mathbf{H}_{t}(\bm{\theta}_{t})$ to $\mathbf{H}_{t}^{\star}$.

In our discussion we use w.l.o.g. $\Theta_{t}\subseteq\Theta$. We will now
justify this choice. Consider the case in which the network is somewhat
different for each task (e.g. in the case of Progressive Networks (Rusu et
al., 2016) a new component is added to the network for each task). We then
write $\Theta_{i}\neq\Theta_{j}$ for any $i,j\in[T]$. Define
$\Theta=\bigcup_{t=1}^{T}\Theta_{t}$ to be the _final parameter space_.
Accordingly, each task update $\bm{\Delta}_{t}$ belongs to a subspace of the
final parameter space, i.e. $\bm{\theta}_{t}\in\Theta_{t}\subseteq\Theta$. Our
analysis applies to a general $\Theta$, thus carrying over to any choice of
$\Theta_{t}$. Intuitively, using new parameters for each task introduces
orthogonality between the parameters (and correspondingly their update
vectors) over task-specific dimensions in $\Theta$. In order to be
comprehensive, we use a general $\Theta$ in our analysis.

###  A.1 Omitted proofs

####  A.1.1 Approximations of forgetting

In the following, we show the steps leading to Equation A.1.1.

We start from the Taylor expansion (Equation 2) of the loss around
$\bm{\theta}_{t}$:

$\displaystyle\mathcal{E}_{o}(\bm{\theta}_{t})$
$\displaystyle={(\bm{\theta}_{t}-\bm{\theta}_{o})}^{\intercal}\bm{\nabla}\mathcal{L}_{o}(\bm{\theta}_{o})+\frac{1}{2}\,{(\bm{\theta}_{t}-\bm{\theta}_{o})}^{\intercal}\mathbf{H}_{o}^{\star}(\bm{\theta}_{t}-\bm{\theta}_{o})+\bm{O}(\|\bm{\theta}_{t}-\bm{\theta}_{o}\|^{3})$

Using Assumptions 1-2 we write:

$\displaystyle\mathcal{E}_{o}(t)$
$\displaystyle=\frac{1}{2}\,\left(\bm{\theta}_{t}-\bm{\theta}_{o}\right)^{\intercal}\mathbf{H}_{o}^{\star}\left(\bm{\theta}_{t}-\bm{\theta}_{o}\right)+\mathcal{O}(\delta\cdot\epsilon)$
$\displaystyle=\frac{1}{2}\,\left(\sum_{\tau=o+1}^{t}\bm{\Delta}_{\tau}\right)^{\intercal}\mathbf{H}_{o}^{\star}\left(\sum_{\tau=o+1}^{t}\bm{\Delta}_{\tau}\right)+\mathcal{O}(\delta\cdot\epsilon)$
$\displaystyle=\underbrace{\frac{1}{2}\,\left(\sum_{\tau=o+1}^{t-1}\bm{\Delta}_{\tau}\right)^{\intercal}\mathbf{H}_{o}^{\star}\left(\sum_{\tau=o+1}^{t-1}\bm{\Delta}_{\tau}\right)}_{\mathcal{E}_{o}(t-1)}+\frac{1}{2}\bm{\Delta}_{t}^{\intercal}\mathbf{H}_{o}^{\star}\bm{\Delta}_{t}+$
$\displaystyle\hskip
5.0pt+\frac{1}{2}\left(\sum_{\tau=o+1}^{t-1}\bm{\Delta}_{\tau}\right)^{\intercal}\mathbf{H}_{o}^{\star}\bm{\Delta}_{t}+\frac{1}{2}\bm{\Delta}_{t}^{\intercal}\mathbf{H}_{o}^{\star}\left(\sum_{\tau=o+1}^{t-1}\bm{\Delta}_{\tau}\right)+\mathcal{O}(\delta\cdot\epsilon)$
$\displaystyle=\mathcal{E}_{o}(t-1)+\frac{1}{2}\bm{\Delta}_{t}^{\intercal}\mathbf{H}_{o}^{\star}\bm{\Delta}_{t}+\left(\sum_{\tau=o+1}^{t-1}\bm{\Delta}_{\tau}\right)^{\intercal}\mathbf{H}_{o}^{\star}\bm{\Delta}_{t}+\mathcal{O}(\delta\cdot\epsilon)$

Based on this formulation, we characterize the average forgetting as follows:

$\displaystyle\mathcal{E}(t)$
$\displaystyle=\frac{1}{t}\sum_{o=1}^{t}\mathcal{E}_{o}(t)=\frac{1}{t}\underbrace{\mathcal{E}_{t}(t)}_{=0}+\frac{1}{t}\sum_{o=1}^{t-1}\mathcal{E}_{o}(t)$
$\displaystyle=\frac{1}{t}\sum_{o=1}^{t-1}\left[\mathcal{E}_{o}(t-1)+\frac{1}{2}\bm{\Delta}_{t}^{\intercal}\mathbf{H}_{o}^{\star}\bm{\Delta}_{t}+\left(\sum_{\tau=o+1}^{t-1}\bm{\Delta}_{\tau}\right)^{\intercal}\mathbf{H}_{o}^{\star}\bm{\Delta}_{t}+\mathcal{O}(\delta\cdot\epsilon)\right]$
$\displaystyle=\frac{1}{t}\sum_{o=1}^{t-1}\left[\mathcal{E}_{o}(t-1)\right]+\frac{1}{t}\sum_{o=1}^{t-1}\left[\frac{1}{2}\bm{\Delta}_{t}^{\intercal}\mathbf{H}_{o}^{\star}\bm{\Delta}_{t}\right]+\frac{1}{t}\sum_{o=1}^{t-1}\left[\left(\sum_{\tau=o+1}^{t-1}\bm{\Delta}_{\tau}\right)^{\intercal}\mathbf{H}_{o}^{\star}\bm{\Delta}_{t}\right]+\mathcal{O}(\delta\cdot\epsilon)$
$\displaystyle={\frac{t-1}{t}}\cdot\mathcal{E}(t-1)+\frac{1}{2t}\bm{\Delta}_{t}^{\intercal}\left[\sum_{o=1}^{t-1}\mathbf{H}_{o}^{\star}\right]\bm{\Delta}_{t}+\frac{1}{t}\left[\underbrace{\sum_{o=1}^{t-1}(\bm{\theta}_{t-1}-\bm{\theta}_{o})^{\intercal}\mathbf{H}_{o}^{\star}}_{\bm{v}^{\intercal}}\right]\bm{\Delta}_{t}+\mathcal{O}(\delta\cdot\epsilon)$
$\displaystyle=\frac{1}{t}\,\left(\,({t-1})\cdot\mathcal{E}(t-1)+\,\frac{1}{2}\bm{\Delta}_{t}^{\intercal}(\sum_{o=1}^{t-1}\mathbf{H}_{o}^{\star})\bm{\Delta}_{t}+\bm{v}^{\intercal}\bm{\Delta}_{t}\,\right)+\mathcal{O}(\delta\cdot\epsilon)$

####  A.1.2 Theorem 1

We want to prove the following statement.

######  Theorem 1 (Null forgetting).

For any continual learning algorithm satisfying Assumptions 1-2 the following
relationship between previous and current forgetting exists:

$\mathcal{E}(1),\dots,\mathcal{E}(t-1)=0\implies\mathcal{E}(t)=\frac{1}{2}\bm{\Delta}_{t}^{\intercal}\bigg{(}\frac{1}{t}\cdot\sum_{o=1}^{t-1}\mathbf{H}_{o}^{\star}\bigg{)}\bm{\Delta}_{t}$

Proof. We prove the above statement by induction. We prove the base case for
$t=1$ and $t=2$, since some terms trivially cancel out for $t=1$.

Base case 1:
$\mathcal{E}(1)=0\implies\mathcal{E}(2)=\frac{1}{2}\bm{\Delta}_{2}^{\intercal}\bm{H}_{1}^{\star}\bm{\Delta}_{2}$.
Notice that by definition, $\mathcal{E}(1)=\mathcal{E}_{1}(1)=0$.

Using Equation A.1.1 we can write $\mathcal{E}(2)$:

$\displaystyle\mathcal{E}(2)$
$\displaystyle={\mathcal{E}(1)}+\,\frac{1}{2}\bm{\Delta}_{2}^{\intercal}(\bm{H}_{1}^{\star})\bm{\Delta}_{2}\,+(\bm{\theta}_{1}-\bm{\theta}_{1})^{\intercal}\bm{H}_{1}^{\star}\bm{\Delta}_{2}$
$\displaystyle=0+\,\frac{1}{2}\bm{\Delta}_{2}^{\intercal}\bm{H}_{1}^{\star}\bm{\Delta}_{2}\,+{0}$

Base case 2:
$\mathcal{E}(1)=0,\mathcal{E}(2)=0\implies\mathcal{E}(3)=\frac{1}{2}\bm{\Delta}_{3}^{\intercal}(\frac{1}{3}\bm{H}_{1}^{\star}+\frac{1}{3}\bm{H}_{2}^{\star})\bm{\Delta}_{3}$.
Using the last result from case 1, we have that :

$\displaystyle\mathcal{E}(2)$
$\displaystyle=\,\frac{1}{2}\bm{\Delta}_{2}^{\intercal}\bm{H}_{1}^{\star}\bm{\Delta}_{2}=0$

The latter equation implies that
$\bm{\Delta}_{2}^{\intercal}\bm{H}_{1}^{1}=\bm{0}$. Plugging it into the value
of $\mathcal{E}(3)$ given by Equation A.1.1:

$\displaystyle\mathcal{E}(3)$
$\displaystyle=\frac{1}{3}\bigg{(}2\cdot{\mathcal{E}(2)}+\,\frac{1}{2}\bm{\Delta}_{3}^{\intercal}(\bm{H}_{2}^{\star}+\bm{H}_{1}^{\star})\bm{\Delta}_{3}\,+\sum_{t=1}^{2}(\bm{\theta}_{2}-\bm{\theta}_{t})^{\intercal}\bm{H}_{t}^{\star}\bm{\Delta}_{3}\bigg{)}$
$\displaystyle=0+\,\frac{1}{2}\bm{\Delta}_{3}^{\intercal}(\mfrac{1}{3}\bm{H}_{2}^{\star}+\mfrac{1}{3}\bm{H}_{1}^{\star})\bm{\Delta}_{3}\,+\mfrac{1}{3}\underbrace{\bm{\Delta}_{2}^{\intercal}\bm{H}_{1}^{1}}_{=\bm{0}}\bm{\Delta}_{3}\,+\mfrac{1}{3}\underbrace{(\bm{\theta}_{2}-\bm{\theta}_{2})}_{=\bm{0}}^{\intercal}\bm{H}_{t}^{\star}\bm{\Delta}$

Induction step: if $\mathcal{E}(\tau)=0\,\,\forall\tau<t$ then
$\mathcal{E}(t)\geq 0$. We start by writing out $\mathcal{E}(t)$.

$\displaystyle\mathcal{E}(t)$
$\displaystyle=\frac{1}{t}\bigg{(}(t-1)\cdot\mathcal{E}(t-1)+\,\frac{1}{2}\bm{\Delta}_{t}^{\intercal}\big{(}\sum_{\tau=1}^{t-1}\bm{H}_{\tau}^{\star}\big{)}\bm{\Delta}_{t}+\sum_{\tau=1}^{t-1}(\bm{\theta}_{t-1}-\bm{\theta}_{\tau})^{\intercal}\bm{H}_{\tau}^{\star}\,\bm{\Delta}_{t}\bigg{)}$
$\displaystyle=0+\,\frac{1}{2}\bm{\Delta}_{t}^{\intercal}\big{(}\sum_{\tau=1}^{t-1}\bm{H}_{\tau}^{\star}\big{)}\bm{\Delta}_{t}+\sum_{\tau=1}^{t-1}(\bm{\Delta}_{\tau+1}+\dots+\bm{\Delta}_{t-1})^{\intercal}\bm{H}_{\tau}^{\star}\,\bm{\Delta}_{t}$

The induction step is accomplished if
$\sum_{\tau=1}^{t-1}(\bm{\Delta}_{\tau+1}+\dots+\bm{\Delta}_{t-1})^{\intercal}\bm{H}_{\tau}^{\star}=\sum_{\tau=1}^{t-2}(\bm{\Delta}_{\tau+1}+\dots+\bm{\Delta}_{t-1})^{\intercal}\bm{H}_{\tau}^{\star}=\bm{0}$.
Consider now the case in which
$\sum_{\tau=1}^{t-1}(\bm{\Delta}_{\tau+1}+\dots+\bm{\Delta}_{t-1})^{\intercal}\bm{H}_{\tau}^{\star}\neq\bm{0}$.
It follows that:

$\displaystyle\sum_{\tau=1}^{t-2}(\bm{\Delta}_{\tau+1}+\dots+\bm{\Delta}_{t-1})^{\intercal}\bm{H}_{\tau}^{\star}\neq\bm{0}$
$\displaystyle\sum_{\tau=1}^{t-2}\bm{\Delta}_{t-1}^{\intercal}\bm{H}_{\tau}^{\star}+\sum_{\tau=1}^{t-2}(\bm{\Delta}_{\tau+1}+\dots+\bm{\Delta}_{t-2})^{\intercal}\bm{H}_{\tau}^{\star}\neq\bm{0}$

Multilying by $\bm{\Delta}_{t-1}$ on the right we get:

$\displaystyle\sum_{\tau=1}^{t-2}\bm{\Delta}_{t-1}^{\intercal}\bm{H}_{\tau}^{\tau}\bm{\Delta}_{t-1}+\sum_{\tau=1}^{t-3}(\bm{\Delta}_{\tau+1}+\dots+\bm{\Delta}_{t-2})^{\intercal}\bm{H}_{\tau}^{\tau}\bm{\Delta}_{t-1}\neq\bm{0}^{\intercal}\bm{\Delta}_{t-1}$

We compare this result with the value of $\mathcal{E}(t-1)$ given by Equation
A.1.1:

$\displaystyle\mathcal{E}(t-1)=$
$\displaystyle\frac{1}{t-1}\,\bigg{(}\,({t-2})\cdot\mathcal{E}(t-2)+\,\frac{1}{2}\bm{\Delta}_{t-1}^{\intercal}(\sum_{o=1}^{t-2}\mathbf{H}_{o}^{\star})\bm{\Delta}_{t-1}+\sum_{\tau=1}^{t-2}(\bm{\Delta}_{\tau+1}+\dots+\bm{\Delta}_{t-1})^{\intercal}\bm{H}_{\tau}^{\star}\,\bm{\Delta}_{t-1}\,\bigg{)}$
$\displaystyle=\frac{1}{t-1}\bigg{(}0+\frac{1}{2}\bm{\Delta}_{t-1}^{\intercal}(\sum_{\tau=1}^{t-2}\bm{H}_{\tau}^{\star})\bm{\Delta}_{t-1}+\sum_{\tau=1}^{t-2}(\bm{\Delta}_{\tau+1}+\dots+\bm{\Delta}_{t-1})^{\intercal}\bm{H}_{\tau}^{\star}\,\bm{\Delta}_{t-1}\big{)}\neq
0$

We arrived at a contradiction, which proves the induction step and concludes
the claim’s proof.

####  A.1.3 Theorem 2

In order to arrive at the statement of Theorem 2 simply notice that, by
definition, $\mathcal{E}(1)=0$ for any continual learning algorithm, and apply
repeatedly Theorem 1. We briefly go through all the steps.

By $\mathcal{E}(1)=0$ and Theorem 1,
$\mathcal{E}(2)=\bm{\Delta}_{2}^{\intercal}(\sum_{o=1}^{1}\mathbf{H}_{o}^{\star})\bm{\Delta}_{2}$.
By assumption 1-2, all Hessian matrices are positive semi-definite and,
accordingly, $\mathcal{E}(2)\geq 0$. It follows that $\mathcal{A}$ is
forgetting-optimal if and only if $\mathcal{E}(2)=0$. Recursively applying
this argument, if $\mathcal{A}$ is forgetting-optimal then it holds:

$\displaystyle\mathcal{E}(2)=\bm{\Delta}_{2}^{\intercal}(\sum_{o=1}^{1}\mathbf{H}_{o}^{\star})\bm{\Delta}_{2}=0$
$\displaystyle\dots$
$\displaystyle\mathcal{E}(T)=\bm{\Delta}_{T}^{\intercal}(\sum_{o=1}^{T-1}\mathbf{H}_{o}^{\star})\bm{\Delta}_{T}=0$

as stated in Theorem 2.

####  A.1.4 Theorem 3

We wish to prove the following statement regarding Orthogonal Gradient Descent
(OGD) Farajtabar et al. (2020).

######  Theorem 3.

Let $\mathcal{A}:[T]\to\Theta$ be a continual learning algorithm satisfying
Assumption 1. If $\mathcal{A}(t)=\bm{\Delta}_{t}$ satisfies Equation 5, then
it satisfies Equation 4.

We start by recalling the OGD algorithm. Let
$D_{o}=\\{(\bm{x}_{1},{y_{1}}),\cdots,(\bm{x}_{n_{o}},{y_{n_{o}}}))\\}$ be the
dataset associated with task $\mathcal{T}_{o}$ and
$\bm{f}_{\bm{\theta}}(\bm{x})\in\mathbb{R}^{K}$ be the network output
corresponding to the input $\bm{x}$. The gradient of the network output with
respect to the network parameters is the $P\times K$ matrix:

$\nabla_{\bm{\theta}}\bm{f}_{\bm{\theta}}(\bm{x})=\left[\nabla_{\bm{\theta}}\bm{f}^{1}_{\bm{\theta}}(\bm{x}),\,\cdots\,,\nabla_{\bm{\theta}}\bm{f}^{K}_{\bm{\theta}}(\bm{x})\right]$

The standard version of OGD imposes the following constraint on any parameter
update $\bm{u}$:

$\langle\bm{u},\nabla_{\bm{\theta}}\bm{f}^{k}_{\bm{\theta}_{o}}(\bm{x}_{i})\rangle=0$

for all $k\in[1,K]$, $\bm{x}_{i}\in D_{o}$ and $o\leq t$, $t$ being the number
of tasks solved so far. If SGD is used, for example, the update $\bm{u}$ is
the gradient of the new task loss for a data batch. Notice that the old task
gradients are evaluated at the minima $\bm{\theta}_{o}$.

Proof Recall the definition of the average loss:

$\mathcal{L}_{t}(\bm{\theta})=\frac{1}{n_{t}}\sum_{i=0}^{n_{t}}l_{t}(\bm{x}_{i,t},y_{i,t},\bm{\theta})$

The Hessian matrix of the loss $\bm{H}_{t}(\bm{\theta})$ can be decomposed as
a sum of two other matrices (Schraudolph, 2002): the _outer-product_ Hessian
and the _functional_ Hessian.

$\displaystyle\bm{H}_{t}(\bm{\theta})=\frac{1}{{n_{t}}}\sum_{i=1}^{n_{t}}\nabla_{\bm{\theta}}\bm{f}_{\bm{\theta}}(\bm{x}_{i})\left[\nabla_{\bm{f}}^{2}{\ell}_{i}\right]\nabla_{\bm{\theta}}\bm{f}_{\bm{\theta}}\left(\bm{x}_{i}\right)^{\intercal}+\frac{1}{{n_{t}}}\sum_{i=1}^{n_{t}}\sum_{k=1}^{K}\left[\nabla_{\bm{f}}{\ell}_{i}\right]_{k}\nabla_{\bm{\theta}}^{2}\bm{f}_{\bm{\theta}}^{k}\left(\bm{x}_{i}\right)\,,$
(9)

where $\ell_{i}=l(\bm{x_{i}},y_{i})$ and $\nabla_{\bm{f}}^{2}{\ell}_{i}$ is
the $K\times K$ matrix of second order derivatives of the loss ${\ell}_{i}$
with respect to the network output $\bm{f}_{\bm{\theta}}(\bm{x_{i}})$. At the
optimum $\bm{\theta}_{t}$ (Assumption 1) the contribution of the functional
Hessian is negligible (Singh et al., 2021). We rewrite the goal of the proof
using these two facts:

$\bm{\Delta}_{t}^{\intercal}\mathbf{H}_{o}^{\star}\bm{\Delta}_{t}=0$
$\bm{\Delta}_{t}^{\intercal}\left(\frac{1}{{n_{o}}}\sum_{i=1}^{n_{o}}\nabla_{\bm{\theta}}\bm{f}_{\bm{\theta}}(\bm{x}_{i})\left[\nabla_{\bm{f}}^{2}{\ell}_{i}\right]\nabla_{\bm{\theta}}\bm{f}_{\bm{\theta}}\left(\bm{x}_{i}\right)^{\intercal}\right)\bm{\Delta}_{t}=0$
(10)

Farajtabar et al. (2020) apply the OGD constraint (Equation 5) to the batch
gradient vector $\bm{g}_{B}=\nabla\mathcal{L}_{t}^{B}$. Following this choice
$\bm{\Delta}_{t}=\sum_{s=1}^{S_{t}}-\eta\bm{g}_{s}$, where $\eta$ is the
learning rate. Clearly, if, for all $s$, $\bm{g}_{s}$ satisfies Equation 5,
then $\bm{\Delta}_{t}$ satisfies it. Hereafter, we ignore the specific form of
$\bm{\Delta}_{t}$, proving the result for a broader class of algorithms for
which $\bm{\Delta}_{t}$ satisfies the OGD constraint. Continuing from Equation
10:

$\displaystyle\frac{1}{{n_{o}}}\left(\sum_{i=1}^{n_{o}}\nabla_{\bm{\theta}}\bm{\Delta}_{t}^{\intercal}\bm{f}_{\bm{\theta}}(\bm{x}_{i})\left[\nabla_{\bm{f}}^{2}{\ell}_{i}\right]\nabla_{\bm{\theta}}\bm{f}_{\bm{\theta}}\left(\bm{x}_{i}\right)^{\intercal}\bm{\Delta}_{t}\right)$
$\displaystyle\frac{1}{{n_{o}}}\left(\sum_{i=1}^{n_{o}}\nabla_{\bm{\theta}}\left[\bm{\Delta}_{t}^{\intercal}\left[\nabla_{\bm{\theta}}\bm{f}^{1}_{\bm{\theta}}(\bm{x}_{i}),\,\cdots\,,\nabla_{\bm{\theta}}\bm{f}^{K}_{\bm{\theta}}(\bm{x}_{i})\right]\right]\left[\nabla_{\bm{f}}^{2}{\ell}_{i}\right]\nabla_{\bm{\theta}}\bm{f}_{\bm{\theta}}\left(\bm{x}_{i}\right)^{\intercal}\bm{\Delta}_{t}\right)$
$\displaystyle\frac{1}{{n_{o}}}\left(\sum_{i=1}^{n_{o}}\nabla_{\bm{\theta}}\left[\underbrace{\bm{\Delta}_{t}^{\intercal}\nabla_{\bm{\theta}}\bm{f}^{1}_{\bm{\theta}}(\bm{x}_{i})}_{=0},\,\cdots\,,\underbrace{\bm{\Delta}_{t}^{\intercal}\nabla_{\bm{\theta}}\bm{f}^{K}_{\bm{\theta}}(\bm{x}_{i})}_{=0}\right]\left[\nabla_{\bm{f}}^{2}{\ell}_{i}\right]\nabla_{\bm{\theta}}\bm{f}_{\bm{\theta}}\left(\bm{x}_{i}\right)^{\intercal}\bm{\Delta}_{t}\right)=0,$

where
$\bm{\Delta}_{t}^{\intercal}\nabla_{\bm{\theta}}\bm{f}^{k}_{\bm{\theta}}(\bm{x}_{i})=0$
is the OGD constraint, which holds for any $k,i$ and $o<t$. This concludes the
proof.

####  A.1.5 Corollary 1

Consider an algorithm $\mathcal{A}$ satisfying Assumptions 1-2. By Theorem 3
we know that, if $\mathcal{A}(t)=\bm{\Delta}_{t}$ satisfies the OGD
constraint, then
$\bm{\Delta}_{t}^{\intercal}\mathbf{H}_{o}^{\star}\bm{\Delta}_{t}=0\,\forall
o<t.$ Consequently,
$\bm{\Delta}_{t}^{\intercal}(\sum_{o=1}^{t-1}\mathbf{H}_{o}^{\star})\bm{\Delta}_{t}=0$.
By Theorem 2, it follows that $\mathcal{E}(t)=0\,\,\forall\,t\in[T]$.

####  A.1.6 On the validity of OGD-GTL

Instead of considering all the function gradients with respect to all the
outputs
$\\{\nabla_{\bm{\theta}}\bm{f}^{k}_{\bm{\theta}}(\bm{x})\,|\,k\in[1,K],\bm{x}\in
D_{o}\\}$, Farajtabar et al. (2020) also consider a cheaper approximation
where they impose orthogonality only with respect to the index corresponding
to the true ground truth label (GTL). We show this can be understood via
fairly mild assumptions, if the loss function is cross-entropy.

For a cross-entropy loss, $\bm{f}^{k}_{\bm{\theta}}(\bm{x_{i}})$ is the log-
probability (or logit) associated with class $k$ for input $\bm{x_{i}}$. The
probability $p(y_{i}=k|\bm{x_{i}};\bm{\theta})$ is then defined as
$(\bm{p_{i}})_{j}=\operatorname{softmax}(\bm{f}_{\bm{\theta}}(\bm{x_{i}}))_{k}$.
Recall, from the proof of Theorem 3, that the theorem statement can be
equivalently written as:

$\bm{\Delta}_{t}^{\intercal}\left(\frac{1}{{n_{o}}}\sum_{i=1}^{n_{o}}\nabla_{\bm{\theta}}\bm{f}_{\bm{\theta}}(\bm{x}_{i})\left[\nabla_{\bm{f}}^{2}{\ell}_{i}\right]\nabla_{\bm{\theta}}\bm{f}_{\bm{\theta}}\left(\bm{x}_{i}\right)^{\intercal}\right)\bm{\Delta}_{t}=0$

For a cross-entropy loss the Hessian of the loss with respect to the network
output is given by:

$\nabla_{\bm{f}}^{2}{\ell}_{i}=\operatorname{diag}(\bm{p_{i}})-\bm{p_{i}p_{i}}^{\intercal}$

Without loss of generality, assume index $k=1$ corresponds to the GTL. Towards
the end of the usual training, the softmax output at index $1$, i.e.,
$p_{1}\approx 1$. Let us assume that the probabilities for the remaining
output coordinates is equally split between them. More precisely, let

$p_{2},\cdots,p_{K}=\dfrac{1-p_{1}}{K-1}.$

Hence, in terms of their scales, we can regard $p_{1}=\mathcal{O}(1)$ while
$p_{2},\cdots,p_{K}=\mathcal{O}\left(K^{-1}\right)$. Furthermore,
$(1-p_{i})=\mathcal{O}(1)\quad\forall\,i\in[2\cdots K]$. Then, a simple
computation of the inner matrix in the Hessian outer product, i.e.,
$\nabla_{\bm{f}}^{2}{\ell}=\operatorname{diag}(\bm{p})-\bm{pp}^{\top}$, will
reveal that diagonal entry corresponding to the ground truth label is
$\mathcal{O}(1)$, while rest of the entries in the matrix are of the order
$\mathcal{O}\left(K^{-1}\right)$ or $\mathcal{O}\left(K^{-2}\right)$ — thereby
explaining this approximation. Also, we can see that this approximation would
work well only when $K\gg 1$ and does not carry over to other loss functions,
e.g. Mean Squared Error (MSE). In fact, $K=2$ all the entries of this matrix
are of the same magnitude $|p_{1}(1-p_{1})|$, and for MSE simply
$\nabla_{\bm{f}}^{2}{\ell}_{i}=\bm{I}_{K}$.

####  A.1.7 Theorem 5

We start by proving Theorem 5. Before proceeding, we introduce the special
notation to be used in the proof.

Notation: given some $a\times b$ matrix $\bm{C}$ we identify with
$\operatorname{vec}({\bm{C}})$ its $a\cdot b$ vector form
($\operatorname{vec}(\cdot)$ is the _vectorisation_ operator). We use the
standard _input_ $\times$_output_ in order to determine the matrices
dimensionality. Moreover, for simplicity, we consider all the network layers
to have width $D$ (the same analysis can be done for layers of different
widths). As an example, the gradient
${\nabla}_{\bm{W}^{l}}\mathcal{L}_{t}(\bm{\theta})$ is a tensor of dimensions
$D\times D\times 1$, and
$\operatorname{vec}({\nabla}_{\bm{W}^{l}}\mathcal{L}_{t}(\bm{\theta}))$ is a
vector of size $D^{2}$. Finally, we use $\bm{\theta}$ to refer to the _vector_
of network parameters (the vectorization operation is implicit), thus
${\nabla}_{\bm{\theta}}\mathcal{L}_{t}(\bm{\theta})$, shortened to
${\nabla}\mathcal{L}_{t}(\bm{\theta})$ is a vector of size $P$.

Proof We recall the GPM algorithm. Let
$\bm{x}^{l+1}_{i}=\sigma(\bm{W}^{{l}^{\intercal}}\bm{x}^{l})$ be the
representation of $\bm{x}_{i}$, by layer $l$ of the network
($\bm{x}^{0}_{i}=\bm{x}_{i}$). Notice that the GPM algorithm does not allow
for bias vectors in the layer functions, thus the set of network parameters is
$\\{\bm{W}^{0},\dots,\bm{W}^{L-1}\\}$. The GPM constraint on the weight matrix
update $\bm{\Delta}\bm{W}^{l}$ reads:

$\langle{\bm{\Delta}\bm{W}}^{l},\bm{x}^{l}_{i}\rangle=0$ (11)

for all network layers $l$, $\bm{x}_{i}\in D_{o}$ and all previous tasks
$\mathcal{T}_{o}$, $o<t$.

The optimization path from $\bm{\theta}_{t-1}$ to $\bm{\theta}_{t}$ is the
sequence of parameter values $\\{\bm{\theta}_{t-1\to
t}^{1},\dots,\bm{\theta}_{t-1\to t}^{S_{t}}\\}$, with parameter updates
$\bm{\delta}_{t}^{(i)}=\bm{\theta}_{t-1\to t}^{i}-\bm{\theta}_{t-1\to
t}^{i-1}$. In the following discussion we drop the task index and simply write
$\bm{\delta}^{(i)}=\bm{\theta}^{(i)}-\bm{\theta}^{(i-1)}$. Similarly,
$\bm{W}^{l^{(i)}}=\bm{W}^{l(i-1)}+\bm{\delta}_{t}^{(i)}[l]$ for the layer
parameters. Observe that:

$\operatorname{vec}(\nabla_{\bm{W}^{l}}\mathcal{L}_{o}(\bm{\theta}^{(i-1)}))^{\intercal}\operatorname{vec}(\bm{\delta}^{(i)}[l])=0\,\,\forall\,l\implies\nabla\mathcal{L}_{o}(\bm{\theta}^{(i-1)})^{\intercal}\bm{\delta}^{(i)}=0$

and, similarly:

$\displaystyle\operatorname{vec}(\bm{\delta}_{t}^{(i)}[l])^{\intercal}\mathbf{H}_{o}(\bm{W}^{l(i-1)})\operatorname{vec}(\bm{\delta}_{t}^{(i)}[l])=0\,\,\forall\,l$
$\displaystyle\implies{\bm{\delta}_{t}^{(i)}}^{\intercal}\operatorname{block-
diag}(\mathbf{H}_{o}(\bm{\theta}_{t-1\to
t}^{(i-1)}))\,\bm{\delta}_{t}^{(i)}=0$

Thus it is sufficient to prove the following two statements, for all
$i\in[1,S_{t}]$, all layers $l$, and all $o<t$:

$\operatorname{vec}(\nabla_{\bm{W}^{l}}\mathcal{L}_{o}(\bm{\theta}^{(i-1)}))^{\intercal}\operatorname{vec}(\bm{\delta}^{(i)}[l])=0$
(12)
$\operatorname{vec}(\bm{\delta}_{t}^{(i)}[l])^{\intercal}\mathbf{H}_{o}(\bm{W}^{l(i-1)})\operatorname{vec}(\bm{\delta}_{t}^{(i)}[l])=0$
(13)

By the linearity of the derivative
$\nabla_{\bm{W}^{l}}\mathcal{L}_{o}(\bm{\theta}^{(i-1)})=\frac{1}{n_{o}}\sum_{j=1}^{n_{o}}\nabla_{\bm{W}^{l}}\ell_{j}$,
where $\ell_{j}=l_{o}(\bm{x_{j}},y_{j};\bm{\theta}^{(i-1)})$. We unpack
$\nabla_{\bm{W}^{l}}\ell_{j}$ using the chain rule:

$\nabla_{\bm{W}^{l}}\ell_{j}=\nabla_{\bm{W}^{l}}\bm{f}_{\bm{\theta}^{(i-1)}}(\bm{x_{j}})\circ\nabla_{\bm{f}}\ell_{j}$

Again, by the use of the chain rule we have:

$\displaystyle\nabla_{\operatorname{vec}(\bm{W}^{l})}\bm{f}_{\bm{\theta}^{(i-1)}}(\bm{x_{j}})$
$\displaystyle=\nabla_{\operatorname{vec}(\bm{W}^{l})}\left(\bm{W}^{l^{(i-1)^{\intercal}}}\bm{x}_{j}^{l(i-1)}\right)\,\,\underbrace{\operatorname{diag}\left(\sigma^{\prime}(\bm{W}^{l^{(i-1)^{\intercal}}}\bm{x}_{j}^{l(i-1)})\right)}_{=:\bm{A}}\cdot\underbrace{\nabla_{\bm{x}_{j}^{l+1}}{\bm{f}}_{\bm{\theta}^{(i-1)}}(\bm{x}_{j})}_{=:\bm{\zeta}_{l+1}}$
$\displaystyle=\nabla_{\operatorname{vec}(\bm{W}^{l})}\left(\bm{W}^{l^{(i-1)^{\intercal}}}\bm{x}_{j}^{l(i-1)}\right)\,\,\cdot\bm{A}\cdot\bm{\zeta}_{l+1}$
$\displaystyle=(\bm{x}_{j}^{l(i-1)}\otimes\bm{I}_{D})\cdot\bm{A}\cdot\bm{\zeta}_{l+1}$
$\displaystyle=(\bm{x}_{j}^{l(i-1)}\otimes\bm{A})\cdot\bm{\zeta}_{l+1}$

where $\bm{A}$ contains the element-wise derivatives of the activation
function $\sigma$ and $\bm{I}_{D}$ is the $D\times D$ identity matrix.
Expanding recursively the layer activation:

$\displaystyle\bm{x}_{j}^{l(i-1)}=\sigma(\bm{W}^{{l-1{(i-1)}}^{\intercal}}\bm{x}_{j}^{l-1{(i-1)}})$
$\displaystyle\dots$
$\displaystyle\bm{x}_{j}^{1^{(i-1)}}=\sigma(\bm{W}^{{0^{(i-1)}}^{\intercal}}\bm{x}_{j})$

As a consequence of the GPM constraint:

$\bm{W}^{{0^{(i-1)}}^{\intercal}}\bm{x}_{j}=\left(\bm{W}_{o}^{0}+(\bm{W}^{0^{(i-1)}}-\bm{W}_{o}^{0})\right)^{\intercal}\bm{x}_{j}=\bm{W}_{o}^{{0}^{\intercal}}\bm{x}_{j},$

$\bm{W}_{o}^{0}$ being the value of $\bm{W}^{0}$ at the optimum of task
$\mathcal{T}_{o}$, i.e. $\bm{\theta}_{o}$. By a recursive argument we then
get:

$\displaystyle\bm{x}_{j}^{1^{(i-1)}}=\sigma(\bm{W}_{o}^{{0}^{\intercal}}\bm{x}_{j})=\bm{x}_{j}^{1}$
$\displaystyle\dots$
$\displaystyle\bm{x}_{j}^{l(i-1)}=\sigma(\bm{W}_{o}^{{l-1}^{\intercal}}\bm{x}^{l-1}_{j})=\bm{x}_{j}^{l}$

In a nutshell, the GPM constraint freezes the network activation vectors to
their value at the optimum, for each input stored in memory. Using this
result, the expression of the output gradient simplifies to:

$\nabla_{\operatorname{vec}(\bm{W}^{l})}\bm{f}_{\bm{\theta}^{(i-1)}}(\bm{x_{j}})=(\bm{x}_{j}^{l}\otimes\bm{A})\cdot\bm{\zeta}_{l+1}$
(14)

We are now ready finalize the first point of our proof (Equation 12).

$\displaystyle\operatorname{vec}(\nabla_{\bm{W}^{l}}\mathcal{L}_{o}(\bm{\theta}^{(i-1)}))^{\intercal}\operatorname{vec}(\bm{\delta}^{(i)}[l])=$
$\displaystyle(\nabla_{\operatorname{vec}(\bm{W}^{l})}\mathcal{L}_{o}(\bm{\theta}^{(i-1)}))^{\intercal}\operatorname{vec}(\bm{\delta}^{(i)}[l])=$
$\displaystyle\left(\frac{1}{n_{o}}\sum_{j=1}^{n_{o}}(\bm{x}_{j}^{l}\otimes\bm{A})\cdot\bm{\zeta}_{l+1}\cdot\nabla_{\bm{f}}\ell_{j}\right)^{\intercal}\operatorname{vec}(\bm{\delta}^{(i)}[l])=$
$\displaystyle\frac{1}{n_{o}}\sum_{j=1}^{n_{o}}{\operatorname{vec}(\bm{\delta}^{(i)}[l])}^{\intercal}(\bm{x}_{j}^{l}\otimes\bm{A})\cdot\bm{\zeta}_{l+1}\cdot\nabla_{\bm{f}}\ell_{j}=$
$\displaystyle\frac{1}{n_{o}}\sum_{j=1}^{n_{o}}\operatorname{vec}(\underbrace{\bm{x}_{j}^{l^{\intercal}}\bm{\delta}^{(i)}[l]}_{=\bm{0}}\bm{A})\cdot\bm{\zeta}_{l+1}\cdot\nabla_{\bm{f}}\ell_{j}=0$
(GPM constraint, eq. 11)

We now proceed to the second point. As before, we decompose the Hessian into
the sum of outer-product and functional Hessian:

$\displaystyle\bm{H}_{o}(\bm{\theta})=\frac{1}{{n_{o}}}\sum_{j=1}^{n_{o}}\nabla_{\bm{\theta}}\bm{f}_{\bm{\theta}}(\bm{x}_{j})\left[\nabla_{\bm{f}}^{2}{\ell}_{j}\right]\nabla_{\bm{\theta}}\bm{f}_{\bm{\theta}}\left(\bm{x}_{j}\right)^{\intercal}+\frac{1}{{n_{o}}}\sum_{i=j}^{n_{o}}\sum_{k=1}^{K}\left[\nabla_{\bm{f}}{\ell}_{j}\right]_{k}\nabla_{\bm{\theta}}^{2}\bm{f}_{\bm{\theta}}^{k}\left(\bm{x}_{j}\right)\,$

In particular we are interested in the block-diagonal elements of the Hessian
matrix, i.e. $\mathbf{H}_{o}(\bm{W}^{l(i-1)})$. When _ReLU_ or linear
activation functions are used the functional part does not contribute to the
the block-diagonal elements, as it can be seen from Equation 14:

$\displaystyle\nabla_{\bm{W}^{l}}^{2}\bm{f}_{\bm{\theta}^{(i-1)}}^{k}\left(\bm{x}_{j}\right)\,$
$\displaystyle=\nabla_{\bm{W}^{l}}\left((\bm{x}_{j}^{l}\otimes\bm{A})\cdot\bm{\zeta}_{l+1}\right)$
$\displaystyle=(\bm{x}_{j}^{l}\otimes\left[\nabla_{\bm{W}^{l}}\bm{A}\right])\cdot\bm{\zeta}_{l+1}$

$\bm{A}$ is a diagonal matrix, and if $\sigma=\operatorname{ReLU}$ then:

$\bm{A}_{kk}=\begin{cases}1\hskip 5.0pt\text{ if
}[\bm{W}^{{l(i-1)}^{\intercal}}\bm{x}_{j}^{l(i-1)}]_{k}>0\\\ 0\hskip
5.0pt\text{ otherwise}\end{cases}$

Consequently, the gradient with respect to the layer weights $\bm{W}^{l(i-1)}$
is null. Similarly, if the activation function is linear, $\bm{A}$ is simply
the identity matrix, and the gradient is $0$. For a general activation
function $\sigma$, the diagonal entries of $\bm{A}$ can have a non-linear
dependence on $\bm{W}^{l(i-1)}$, and a case-by-case evaluation is required.
Hereafter, we consider the piecewise-linear and linear case, for which the
functional Hessian is _block-hollow_.

We can thus ignore the outer-product component in the Hessian layer blocks
$\mathbf{H}_{o}(\bm{W}^{l(i-1)})$ and write:

$\displaystyle\mathbf{H}_{o}(\bm{W}^{l(i-1)})$
$\displaystyle=\frac{1}{{n_{o}}}\sum_{j=1}^{n_{o}}\nabla_{\bm{W}^{l}}\bm{f}_{\bm{\theta}^{(i-1)}}(\bm{x}_{j})\left[\nabla_{\bm{f}}^{2}{\ell}_{j}\right]\nabla_{\bm{W}^{l}}\bm{f}_{\bm{\theta}^{(i-1)}}\left(\bm{x}_{j}\right)^{\intercal}$
$\displaystyle=\frac{1}{{n_{o}}}\sum_{j=1}^{n_{o}}\left[(\bm{x}_{j}^{l}\otimes\bm{A})\cdot\bm{\zeta}_{l+1}\right]\left[\nabla_{\bm{f}}^{2}{\ell}_{j}\right]\left[(\bm{x}_{j}^{l}\otimes\bm{A})\cdot\bm{\zeta}_{l+1}\right]^{\intercal}$

We can now finalise the second point in our proof (Equation 13).

$\displaystyle\operatorname{vec}(\bm{\delta}_{t}^{(i)}[l])^{\intercal}\mathbf{H}_{o}(\operatorname{vec}(\bm{W}^{l(i-1)}))\operatorname{vec}(\bm{\delta}_{t}^{(i)}[l])=$
$\displaystyle=\operatorname{vec}(\bm{\delta}_{t}^{(i)}[l])^{\intercal}\left(\frac{1}{{n_{o}}}\sum_{j=1}^{n_{o}}\left[(\bm{x}_{j}^{l}\otimes\bm{A})\cdot\bm{\zeta}_{l+1}\right]\left[\nabla_{\bm{f}}^{2}{\ell}_{j}\right]\left[(\bm{x}_{j}^{l}\otimes\bm{A})\cdot\bm{\zeta}_{l+1}\right]^{\intercal}\right)\operatorname{vec}(\bm{\delta}_{t}^{(i)}[l])=$
$\displaystyle=\frac{1}{{n_{o}}}\sum_{j=1}^{n_{o}}\left(\left[\operatorname{vec}(\bm{\delta}_{t}^{(i)}[l])^{\intercal}(\bm{x}_{j}^{l}\otimes\bm{A})\cdot\bm{\zeta}_{l+1}\right]\right)\left[\nabla_{\bm{f}}^{2}{\ell}_{j}\right]\left(\left[(\bm{x}_{j}^{l}\otimes\bm{A})\cdot\bm{\zeta}_{l+1}\right]^{\intercal}\operatorname{vec}(\bm{\delta}_{t}^{(i)}[l])\right)=$
$\displaystyle=\frac{1}{{n_{o}}}\sum_{j=1}^{n_{o}}\left(\left[\operatorname{vec}(\underbrace{\bm{x}_{j}^{{l}^{\intercal}}\bm{\delta}_{t}^{(i)}[l]}_{=\bm{0}}\bm{A})\cdot\bm{\zeta}_{l+1}\right]\right)\left[\nabla_{\bm{f}}^{2}{\ell}_{j}\right]\left(\left[(\bm{x}_{j}^{l}\otimes\bm{A})\cdot\bm{\zeta}_{l+1}\right]^{\intercal}\operatorname{vec}(\bm{\delta}_{t}^{(i)}[l])\right)=0$

Once more, $\bm{x}_{j}^{{l}^{\intercal}}\bm{\delta}_{t}^{(i)}[l]$ evaluates to
$0$ following the GPM constraint. We have evaluated only the right side of the
expression (as it is enough to prove the equivalence), however notice that the
expression is symmetric.

Notice that our proof applies to any $o<t$ and any $i\in[1,S_{t}]$ and layer
$l$ in the network, since the GPM constraint also holds for all these cases.
We have proved Theorem 5 for all network with piecewise-linear and linear
activation functions. We leave the case of other activation functions to the
reader.

####  A.1.8 Theorem 4

We are now ready to prove that, under Assumptions 1-2, algorithms satisfying
the GPM constraint also satisfy the null-forgetting constraint (Equation 4,
when the Hessian matrices are block diagonal.

Recall the null-forgetting constraint (Equation 4):

$\mathcal{A}(t)=\bm{\Delta}_{t}=\operatorname{argmin}\mathcal{E}(t)\iff\bm{\Delta}_{t}^{\intercal}(\sum_{o=1}^{t-1}\mathbf{H}_{o}^{\star})\bm{\Delta}_{t}=0$

By Assumption 1, we know $\mathbf{H}_{o}^{\star}$ coincides with the outer-
product Hessian:

$\bm{H}_{o}(\bm{\theta})=\frac{1}{{n_{o}}}\sum_{j=1}^{n_{o}}\nabla_{\bm{\theta}}\bm{f}_{\bm{\theta}_{o}}(\bm{x}_{j})\left[\nabla_{\bm{f}}^{2}{\ell}_{j}\right]\nabla_{\bm{\theta}}\bm{f}_{\bm{\theta}_{o}}\left(\bm{x}_{j}\right)^{\intercal}$

Thus the statement to prove is:

$\displaystyle\bm{\Delta}_{t}^{\intercal}(\sum_{o=1}^{t-1}\mathbf{H}_{o}^{\star})\bm{\Delta}_{t}=0$
$\displaystyle\iff\bm{\Delta}_{t}^{\intercal}(\sum_{o=1}^{t-1}\frac{1}{{n_{o}}}\sum_{j=1}^{n_{o}}\nabla_{\bm{\theta}}\bm{f}_{\bm{\theta}_{o}}(\bm{x}_{j})\left[\nabla_{\bm{f}}^{2}{\ell}_{j}\right]\nabla_{\bm{\theta}}\bm{f}_{\bm{\theta}_{o}}\left(\bm{x}_{j}\right)^{\intercal})\bm{\Delta}_{t}=0$
$\displaystyle\iff\sum_{o=1}^{t-1}\frac{1}{{n_{o}}}\sum_{j=1}^{n_{o}}\bm{\Delta}_{t}^{\intercal}\left(\nabla_{\bm{\theta}}\bm{f}_{\bm{\theta}_{o}}(\bm{x}_{j})\left[\nabla_{\bm{f}}^{2}{\ell}_{j}\right]\nabla_{\bm{\theta}}\bm{f}_{\bm{\theta}_{o}}\left(\bm{x}_{j}\right)^{\intercal}\right)\bm{\Delta}_{t}=0$
$\displaystyle\iff\sum_{o=1}^{t-1}\frac{1}{{n_{o}}}\sum_{j=1}^{n_{o}}{(\sum_{i=1}^{S_{t}}\bm{\delta}_{t}^{(i)})}^{\intercal}\left(\nabla_{\bm{\theta}}\bm{f}_{\bm{\theta}_{o}}(\bm{x}_{j})\left[\nabla_{\bm{f}}^{2}{\ell}_{j}\right]\nabla_{\bm{\theta}}\bm{f}_{\bm{\theta}_{o}}\left(\bm{x}_{j}\right)^{\intercal}\right)(\sum_{i=1}^{S_{t}}\bm{\delta}_{t}^{(i)})=0$
$\displaystyle\iff\sum_{o=1}^{t-1}\frac{1}{{n_{o}}}\sum_{j=1}^{n_{o}}\left(\sum_{i=1}^{S_{t}}\bm{\delta}_{t}^{{(i)}^{\intercal}}\nabla_{\bm{\theta}}\bm{f}_{\bm{\theta}_{o}}(\bm{x}_{j})\right)\left[\nabla_{\bm{f}}^{2}{\ell}_{j}\right]\left(\sum_{i=1}^{S_{t}}\nabla_{\bm{\theta}}\bm{f}_{\bm{\theta}_{o}}(\bm{x}_{j})^{\intercal}\bm{\delta}_{t}^{(i)}\right)=0$

Being the Hessian matrix block-diagonal by assumption, it is sufficient to
prove:

$\operatorname{vec}(\bm{\delta}_{t}^{(i)}[l])^{\intercal}\nabla_{\bm{W}^{l}}\bm{f}_{\bm{\theta}_{o}}(\bm{x}_{j})=0$

where we adopt the notation from the proof of Theorem 5. Using the result in
Equation 14:

$\displaystyle\operatorname{vec}(\bm{\delta}_{t}^{(i)}[l])^{\intercal}\nabla_{\bm{W}^{l}}\bm{f}_{\bm{\theta}_{o}}(\bm{x}_{j})$
$\displaystyle=\operatorname{vec}(\bm{\delta}_{t}^{(i)}[l])^{\intercal}(\bm{x}_{j}^{l}\otimes\bm{A})\cdot\bm{\zeta}_{l+1}$
$\displaystyle=\operatorname{vec}(\bm{x}_{j}^{{l}^{\intercal}}\bm{\delta}_{t}^{(i)}[l]\bm{A})\cdot\bm{\zeta}_{l+1}=0,$

where the last equality follows from the GPM constraint.

####  A.1.9 Corollary 2

Finally we go over the proof of Corollary 2. We start by considering the
following Taylor expansion:

$\mathcal{E}_{o}(\bm{\theta}_{t-1\to
t}^{(i)})=\mathcal{E}_{o}(\bm{\theta}_{t-1\to
t}^{(i-1)})+\nabla\mathcal{L}_{o}(\bm{\theta}_{t-1\to
t}^{(i-1)})^{\intercal}\bm{\delta}_{t}^{(i)}+\frac{1}{2}\bm{\delta}_{t}^{(i)\intercal}\mathbf{H}_{o}(\bm{\theta}_{t-1\to
t}^{(i-1)})\bm{\delta}_{t}^{(i)}+\mathcal{O}(\|\delta_{t}^{(i)}\|)$

By the GPM constraint, $\nabla\mathcal{L}_{o}(\bm{\theta}_{t-1\to
t}^{(i-1)})^{\intercal}\bm{\delta}_{t}^{(i)}=0$ and
$\bm{\delta}_{t}^{(i)\intercal}\mathbf{H}_{o}(\bm{\theta}_{t-1\to
t}^{(i-1)})\bm{\delta}_{t}^{(i)}=0$, as by assumption $\operatorname{block-
diag}(\mathbf{H}_{o}(\bm{\theta}_{t-1\to
t}^{(i-1)})=\mathbf{H}_{o}(\bm{\theta}_{t-1\to t}^{(i-1)})$. Consequently, the
expression of forgetting on the optimization path simplifies to:

$\mathcal{E}_{o}(\bm{\theta}_{t-1\to
t}^{(i)})=\mathcal{E}_{o}(\bm{\theta}_{t-1\to
t}^{(i-1)})+\mathcal{O}(\|\delta_{t}^{(i)}\|)$

For sufficiently small step sizes (often
$\|\delta_{t}^{(i)}\|\in\mathcal{O}(\eta)$, where $\eta$ is the learning
rate), the approximation error is negligible, and, by recursively applying the
above identity we obtain:
$\mathcal{E}_{o}(\bm{\theta}_{t})=\mathcal{E}_{o}(\bm{\theta}_{o})=0$, which
proves the statement.

###  A.2 Further discussion

####  A.2.1 Non monotonic null-forgetting

The null-forgetting constraint presupposes that forgetting is zero after
learning each task, i.e. $\mathcal{E}_{\tau}(t)=0$ for any $\tau$ and $t$
(with $\tau<t$). Here we consider what happens when $\mathcal{E}(\tau)>0$ for
some $\tau<t$. Specifically, we want to derive a new constraint on the update
$\bm{\Delta}_{\tau+1}$ such that $\mathcal{E}(\tau+1)=0$.

######  Theorem 6 (Non monotonic null-forgetting constraint.).

Let $\mathcal{A}:[T]\to\Theta$ be a continual learning algorithm satisfying
Assumptions 1-2. Furthermore, for the first $\tau-1$ tasks it holds that
$\mathcal{E}(k)=0$. Let
$\mathcal{A}(\tau)=\bm{\Delta}_{\tau}\,\,s.t.\,\,\mathcal{E}(\tau)>0$.

Then for an update $\mathcal{A}(\tau+1)=\bm{\Delta}_{\tau+1}$,
$\mathcal{E}(\tau+1)=0$ if and only if:

$\bm{\Delta}_{\tau+1}=\bm{z}-(\sum_{o=1}^{\tau}\mathbf{H}_{o}^{\star})^{\dagger}\bm{B}\bm{\Delta}_{\tau},$
(16)

for any vector $\bm{z}$ satisfying the condition
$(\sum_{o=1}^{\tau}\mathbf{H}_{o}^{\star})\bm{z}=\bm{0}$. $\bm{B}$ is the
matrix characterising $\mathcal{E}(\tau)$, i.e.
$\mathcal{E}(\tau)=\frac{1}{2\tau}\bm{\Delta}_{\tau}^{\intercal}\bm{B}\bm{\Delta}_{\tau}$.

Proof. By Assumptions 1-2 we can approximate $\mathcal{E}(\tau+1)$ using
Equation A.1.1:

$\mathcal{E}(\tau+1)=\frac{1}{\tau+1}\,\bigg{(}\,{\tau}\cdot\mathcal{E}(\tau)+\,\frac{1}{2}\bm{\Delta}_{\tau+1}^{\intercal}(\sum_{o=1}^{\tau}\mathbf{H}_{o}^{\star})\bm{\Delta}_{\tau+1}+\sum_{o=1}^{\tau-1}(\bm{\theta}_{\tau}-\bm{\theta}_{o})^{\intercal}\mathbf{H}_{o}^{\star}\bm{\Delta}_{\tau+1}\,\bigg{)}$

Using $\mathcal{E}(k)=0\,\forall\,k<\tau$ and Theorem 1 we have
$\mathcal{E}(\tau)=\bm{\Delta}_{\tau}^{\intercal}\bm{B}\bm{\Delta}_{\tau}=C>0$,
where we define $\bm{B}:=(\sum_{o=1}^{\tau-1}\mathbf{H}_{o}^{\star})$.
Moreover, notice that:

$\bm{v}_{\tau}:=\sum_{o=1}^{\tau-1}(\bm{\theta}_{\tau}-\bm{\theta}_{o})^{\intercal}\mathbf{H}_{o}=\sum_{o=1}^{\tau-1}\bm{\Delta}_{\tau}^{\intercal}\mathbf{H}_{o}^{\star}+\bm{v}_{\tau-1}$

From Theorem 1 it follows that $\bm{v}_{\tau-1}=\bm{0}$ and thus:

$\mathcal{E}(\tau+1)=\frac{1}{\tau+1}\,\bigg{(}\,{\tau}\cdot
C+\,\frac{1}{2}\bm{\Delta}_{\tau+1}^{\intercal}(\sum_{o=1}^{\tau}\mathbf{H}_{o}^{\star})\bm{\Delta}_{\tau+1}+\bm{\Delta}_{\tau}^{\intercal}\mathbf{B}\bm{\Delta}_{\tau+1}\,\bigg{)}$

Notice that this expression is quadratic in $\bm{\Delta}_{\tau+1}$ and thus
$\mathcal{E}(\tau+1)$ admits a closed-form solution. We get:

$\operatorname{argmin}_{\bm{\Delta}_{\tau+1}}\mathcal{E}(\tau+1)=\bm{z}-(\sum_{o=1}^{\tau}\mathbf{H}_{o}^{\star})^{\dagger}\bm{B}\bm{\Delta}_{\tau},$

where $\bm{z}$ is any vector satisfying the condition
$(\sum_{o=1}^{\tau}\mathbf{H}_{o}^{\star})\bm{z}=0$. Notice that if
$\mathcal{E}(\tau)=0$ then $\bm{B}\Delta_{\tau}=\bm{0}$ and 6 reduces to the
null-forgetting constraint from Theorem 2. Intuitively, in order to reverse
forgetting, the algorithm has to retrace its steps along the harmful
directions in the previous update (i.e. $\bm{B}\bm{\Delta}_{\tau}$).

The next Corollary extends the result in Theorem 1 to the case of non-
monotonic forgetting. It follows directly from Theorem 6 and the formulation
of forgetting in Equation A.1.1.

######  Corollary 3 (Non monotonic null-forgetting.).

For any continual learning algorithm satisfying Assumptions 1-2 the following
relationship between previous and current forgetting exists:

$\mathcal{E}(1),\dots,\mathcal{E}(t-2)=0,\mathcal{E}(t-1)>0,\mathcal{E}(t)=0\implies\mathcal{E}(t+2)=\frac{1}{2}\bm{\Delta}_{t+2}^{\intercal}\bigg{(}\mfrac{1}{t+2}\cdot\sum_{o=1}^{t+1}\mathbf{H}_{o}^{\star}\bigg{)}\bm{\Delta}_{t+2}$

####  A.2.2 Implications of null-forgetting

Theorem 1 describes forgetting in terms of the alignment between the current
parameter update and the column space of the Hessians of the previous tasks.

Let
$\overline{\mathbf{H}}^{\star}_{<t}:=\frac{1}{t-1}\cdot\sum_{o=1}^{t-1}\mathbf{H}_{o}^{\star}$
denote the average Hessian matrix of the old tasks. Intuitively, the higher
the rank of $\overline{\mathbf{H}}^{\star}_{<t}$ the less capacity is left to
learn a new task. In order to see this, simply consider the constrained
optimization problem:

$\displaystyle\bm{\Delta}_{t}=$
$\displaystyle\operatorname{argmin}_{\bm{\Delta}\in\Theta}\mathcal{L}_{t}(\bm{\Delta}+\bm{\theta}_{t-1})$
$\displaystyle
s.t.\,\bm{\Delta}_{t}^{\intercal}\overline{\mathbf{H}}^{\star}_{<t}\bm{\Delta}_{t}=0$

The constraint on the parameter update effectively restricts the search space
from $\Theta$ to the $P-R$-dimensional subspace orthogonal to the column space
of $\overline{\mathbf{H}}^{\star}_{<t}$, where
$R=\operatorname{rank}(\overline{\mathbf{H}}^{\star}_{<t})$. Thus, the higher
$R$, the smaller the set of feasible solutions for the current task.
Importantly, this formulation ignores potential _constructive interference_
between tasks, which is a limitation of many parameter isolation models (Lin
et al. (2022) do follow-up work on GPM addressing this problem). This
condition is necessary under Assumption 1-2, where forgetting is always non-
negative and thus there can be no constructive interference. However, in the
more general setting, the condition reflects a worse-case scenario, and
exploiting a constructive intereference of task may save network capacity for
future tasks.

Figure 5: Rank and effective rank for various threshold $\lambda$ values on
the Rotated MNIST challenge, learned by SGD. The values are averaged over
seeds.

Methods enforcing sparsity on the parameter updates (Schwarz et al., 2021)
induce a transformation of the loss gradient vector and Hessian matrix similar
to parameter isolation methods. In practice, the column space of $\bm{H}_{o}$
is a subset of the task parameters $\Theta_{o}$. Thereby, the alignment of the
current update to the column space of the average Hessian becomes simply a
function of the overlap with the previous updates
$\|\bm{\Delta}_{t}-\bm{\theta}_{t-1}\|_{0}$ and the average Hessian rank is
$R\leq(\sum_{o=1}^{t-1}{r_{o}})\cdot P$, where $r_{o}$ is the fraction of
active connections for task $\mathcal{T}_{o}$. If the average Hessian rank is
not maximal, Theorem 1 suggests that $r_{t}>(1-(\sum_{o=1}^{t-1}{r_{o}}))$ can
be achieved without suffering forgetting.

In Figure 5 we plot the evolution of
$\operatorname{rank}(\overline{\mathbf{H}}^{\star}_{<t})$ over $t$ for the
Rotated-MNIST challenge. Additionally, we evaluate the effective rank of the
average Hessian for multiple threshold $\lambda$ values, which better captures
the effective dimensionality of the matrix column space.

##  Appendix B Experimental Details

####  B.0.1 Experimental setup

The experiments are designed to support the theoretical contribution of the
paper. The specific experimental design choices are motivated by the theory
and by the common practices in the field. Especially when providing results on
existing methods (Section 5.2), we employ similar experimental setting as in
the original paper. Following is a detailed description of our experimental
setup, which is aimed at facilitating reproducibility.

##### Datasets.

  1. 1.

_Rotated-MNIST_ : a sequence of $5$ tasks, each corresponding to a fixed
rotation applied to the MNIST dataset. We fix the set of rotations to
$[-45^{\circ},-22.5^{\circ},0,22.5^{\circ},45^{\circ}]$, in line with
(Farajtabar et al., 2020). In order to be able to compute the network Hessian
matrix, the input is downscaled to $14\times 14$. The output space is shared
across task, and has $10$ dimensions, one for each digit. We employ the
standard Pytorch train-test split, loading $60,000$ inputs to train each task.

  2. 2.

_Split CIFAR-10_ : a sequence of $5$ tasks, each corresponding to a different
pair of labels in the CIFAR-10 dataset. The splits are fixed across
experiments: classes $(0,1)$ for the first task, $(2,3)$ for the second one,
and so on. The output space is shared across task, and has dimensionality $2$.
We employ the standard Pytorch train-test split, loading $5,000\times 2$
inputs to train each task.

  3. 3.

_Split CIFAR-100_ : a sequence of $20$ tasks. Similarly to Split CIFARO-10,
each task corresponds to a different set of $5$ classes from the CIFAR-100
dataset. The splits are fixed across experiments. The output space is shared
across task, and has dimensionality $5$. We employ the standard Pytorch train-
test split, loading $500\times 5$ inputs to train each task.

##### Network architectures.

Overall, we employ $3$ different network architectures in the experiments: an
MLP, a CNN, and a Transformer. We here describe the implementation of the
three networks. In Table 4 we provide an overview of the different
hyperparameter settings used: each experiment configuration takes one row of
the table.

  1. 1.

The MLP has $3$ hidden layers with $50$ units each. Experiments with similar
MLP architectures are widespread in the literature (Farajtabar et al., 2020;
Saha et al., 2021; Mirzadeh et al., 2020b; Hsu et al., 2018). However, we
reduce the conventional layer width from $100$ (or $200$) to $50$ neurons,
while increasing the depth by one layer (from $2$ to $3$), thereby lowering
the network size. Our network has a total of $18,010$ parameters. In the GPM
experiments we do not include bias terms in the network, thus reducing the
size further to $17,800$. We train this network using SGD, SGD†, OGD and GPM
with the same hyperparameter configurations.

  2. 2.

The CNN used is a ResNet 18 (He et al., 2016). We adopt the same
implementation as (Mirzadeh et al., 2020b; Saha et al., 2021; Lopez-Paz &
Ranzato, 2017), which is a smaller version of the original ResNet18, with
three times less feature maps per layer. In total, the network has around
$0.5$M parameters. This network is trained using SGD and SGD† on Split
CIFAR-10 and Split CIFAR-100 (the output layer size is changed accordingly).
The same hyperparameter configuration is used for both SGD and SGD† in order
to make a fair comparison.

  3. 3.

The Transformer is a ViT (Dosovitskiy et al., 2020). The use of Transformers
is not as widespread yet in the continual learning literature. We refer to a
publicly available implementation of a ViT in Pytorch111Found on Github:
https://github.com/omihub777/ViT-CIFAR. Last accessed in May 2023., which is
again a smaller version than the original. The network has around $12$M
parameters. We retain the standard configuration provided in the reference
implementation for almost all hyperparameters, except we simplify the
optimization scheme. We use SGD instead of the Adam optimizer, no weight decay
or label smoothing and a simple two-steps learning rate decay schedule. We
train this network for SGD and SGD† again on Split CIFAR-10 and Split
CIFAR-100, changing the output layer accordingly.

Table 3: Experiments configurations Network | Dataset | Algorithm | Learning rate | Epochs
---|---|---|---|---
MLP | Rotated-MNIST | SGD | $0.01$ | $5$
SGD |  $\\{0.01$, $10^{-5}\\}$ | $15$
SGD†, $\epsilon=0.01$ | $0.01$ | $5$
SGD†, $\epsilon=0.01$ |  $\\{0.01$, $10^{-5}\\}$ | $15$
GPM, $\epsilon=0.01$ | $0.01$ | $5$
GPM, $\epsilon=0.01$ |  $\\{0.01$, $10^{-5}\\}$ | $15$
OGD-gtl, $\epsilon=0.01$ | $0.01$ | $5$
OGD-gtl, $\epsilon=0.01$ |  $\\{0.01$, $10^{-5}\\}$ | $15$
ResNet18 | Split CIFAR-10 | SGD | $\\{0.1,0.001\\}$ | $\\{10/20,1\\}$
SGD†, $k=10$ | $\\{0.1,0.001\\}$ | $\\{10/20,1\\}$
SGD†, $k=20$ | $\\{0.1,0.001\\}$ | $\\{10/20,1\\}$
Split CIFAR-100 | SGD | $\\{0.1,0.001\\}$ | $\\{30/60/70,10\\}$
SGD†, $k=10$ | $\\{0.1,0.001\\}$ | $\\{30/60/70,10\\}$
SGD†, $k=20$ | $\\{0.1,0.001\\}$ | $\\{30/60/70,10\\}$
ViT | Split CIFAR-10 | SGD | $\\{0.1,0.001\\}$ | $\\{10/20,1\\}$
SGD†, $k=10$ | $\\{0.1,0.001\\}$ | $\\{10/20,1\\}$
SGD†, $k=20$ | $\\{0.1,0.001\\}$ | $\\{10/20,1\\}$
Split CIFAR-100 | SGD | $\\{0.1,0.001\\}$ | $\\{15/25,5/10\\}$
SGD†, $k=10$ | $\\{0.1,0.001\\}$ | $\\{15/25,5/10\\}$
SGD†, $k=20$ | $\\{0.1,0.001\\}$ | $\\{15/25,5/10\\}$
Table 4: All the experiments in the table are repeated over $5$ seeds, namely
$11,13,21,33,55$. When the same learning rate is used for all the tasks it is
written as a single number. Otherwise, we use a different learning rate for
the tasks following the first and we indicate this as $\\{r_{1},r_{2:T}\\}$ in
the table. The batch size is $10$ unless stated otherwise. The epoch number
follows a similar scheme: if a different number of epochs is used between the
first and remaining tasks we write $\\{e_{1},e_{2:T}\\}$. Moreover, if the
learning rate is decayed while learning a task we write the decay schedule in
the place of the epoch number as
$\\{s^{1}_{1}/s^{2}_{1}/\dots/e_{1},s^{1}_{2:T}/s^{2}_{2:T}/\dots/e_{2:T}\\}$,
which means that the first learning learning rate is decayed after $s^{1}_{1}$
epochs and then again $s^{2}_{1}$, until reaching the final epoch $e_{1}$.
Similarly, for the remaining tasks, the learning rate is decayed after
$s^{1}_{2:T}$ epochs and then again $s^{2}_{2:T}$, and so on until reaching
the final epoch $e_{2:T}$.

##### Metrics.

Finally, we recapitulate the metrics used in the paper. We measure forgetting
on a specific task as
$\mathcal{E}_{o}(t)=\mathcal{L}_{o}(\bm{\theta}_{t})-\mathcal{L}_{o}^{\star}$
and average forgetting as
$\mathcal{E}(t)=\mfrac{1}{t}\sum_{o=1}^{t-1}\mathcal{E}_{o}(t)$. In the
literature, forgetting is often measured as
$\operatorname{BWT}=\mfrac{1}{T-1}\sum_{o=1}^{T-1}(a_{o,o}-a_{T,o})$, where
$a_{j,i}$ denotes the accuracy on task $\mathcal{T}_{i}$ for
$\bm{\theta}=\bm{\theta}_{j}$. In our results we also report forgetting in
terms of accuracy, in order to increase the interpretability of the scores.
Simply, we replace the definition of forgetting with
$\mathcal{E}_{o}(t)=a_{o,o}-a_{t,o}$ and
$\mathcal{E}(t)=\mfrac{1}{t}\sum_{o=1}^{t-1}\mathcal{E}^{a}_{o}(t)$. Finally,
in accordance with the convention in the literature, we also measure the
average accuracy over tasks as $a(t)=\mfrac{1}{t}\sum_{o=1}^{t}a_{t,o}$. For
all these scores we evaluate the loss and accuracy on the test set.

##### Selection of $k$ in experiment 5.2

When comparing OGD, GPM and SGD$\dagger$ we have to be careful in selecting
the number of new vectors to store in the memory for each task, since each
method uses different vectors in practice. We decide to threshold the spectral
energy of the addition to the memory, using $\epsilon$ as a cutoff parameter.
In practice, instead of controlling , the number of eigenvectors, we control ,
the portion of spectral energy left out, where spectral energy is the squared
eigenvalues norm . From the eigendecomposition, we obtain the cumulative
spectral energy and we make a cut keeping $1-\epsilon$ of the total energy. In
this way, the size of the ‘protected subspace’ depends on the task, and in
particular on the geometry of the optimum.

####  B.0.2 Hessian computation and eigendecomposition

The loss Hessian matrix plays a key role in our theoretical framework, and
thus its computation is necessary to our experiments. However, the Hessian
matrix has a high memory cost, i.e. $\mathcal{O}(P^{2})$ ($P$ being the size
of the network). Moreover, SGD† uses the principal eigenvectors of the
Hessian, and the eigendecomposition operation has complexity
$\mathcal{O}(P^{3})$. For the MLP network we can compute the full Hessian
matrix in $\approx 160s$ and its eigendecomposition in $\approx 960s$ For the
CNN and the Transformer networks, we cannot compute the full Hessian matrix.
However, we can still obtain its principal eigenvectors through iterative
methods such as _power iteration_ or the _Lanczos method_ and the Hessian-
vector product (Yao et al., 2018a; Xu et al., 2018). Golmant et al. (2018) has
publicly provided an implementation of these methods for Pytorch neural
networks, which we have adapted to our scope. We use a random subset of the
data to compute the Hessian and/or its eigenvectors. For all the experiments
we fix the subset size to $1000$ samples.

##  Appendix C Additional results

###  C.1 Extended results

In this section we present the results of the experiments in their entirety.
We adopt the same structure of Section 5 of the paper.

####  C.1.1 Experiments Section 5.2

With the first set of experiments, we investigate the empirical validity of
Theorems 3-4. In the paper, we show the equivalence of GPM, OGD and SGD† when
the analysis assumptions are met. Here we further examine GPM and OGD.

##### Measuring the violation of the constraint

Corollary 1 and 2 establish zero forgetting guarantees for OGD and GPM under
Assumption 1-2. We directly measure the degree of violation of the null-
forgetting constraint (Equation 4) on the RMNIST dataset for both methods and
compare them with vanilla SGD. The score used is simply:

$VNC(t)=\bm{\Delta}_{t}^{\intercal}(\mfrac{1}{t}\sum_{o=1}^{t-1}\mathbf{H}_{o}^{\star})\bm{\Delta}_{t}$

The null-forgetting constraint is satisfied if $VNC(t)=0$ for all $t$. The
results, reported in Table 5, agree with our theoretical intuition: GPM and
OGD consisently achieve lower degrees of violation of the null-forgetting
constraint.

Table 5: Violation of null-forgetting constraint (Equation 4). lr | Algorithm | $VNC(t)$
---|---|---
$1e^{-5}$ | GPM | $0.004\pm 0.004$
OGD | $\bm{0.0001}\pm 0.0004$
SGD | $0.27\pm 0.10$
$1e^{-2}$ | GPM | $\bm{0.14}\pm 0.11$
OGD | $0.25\pm 0.05$
SGD | $0.59\pm 0.07$

##### Verifying the underlying assumptions

Next, we check the underlying assumptions of both GPM and OGD. Through our
analysis we show that GPM relies on a block-diagonal approximation of the loss
Hessian matrix. In order to evaluate the validity of the assumption we define
a _block-diagonality_ score:

$\mathfrak{D}(M)=1-\frac{\mathbb{E}_{(i,j)\notin
D}\,|M_{ij}|}{\mathbb{E}_{(i,j)\in D}\,|M_{ij}|},$

where we use $B$ to denote the set of entries in the diagonal blocks, and $M$
is any matrix. Notice that a perfectly block-diagonal matrix will score
$\mathfrak{D}(M)=1$. For non block-diagonal matrices the score has no lower
bound. On random matrices, the score evaluates to $-0.001\,(\pm 0.02)$, over
$1000$ trials. In Table 6 (left), we record the average score for the Hessian
matrix $\bm{H}_{t}^{\star}$ of different tasks when training with GPM, both in
the high and low learning rate cases. The average is taken over seeds and
tasks. Importantly, the results reveal that the assumption is not met in
practice.

OGD effectively adopts the outer-product Hessian $\bm{H}_{t}^{O}$ (Equation
9), which has been shown to be a good approximation of the Hessian matrix
towards the end of training (Singh et al., 2021) \- and thus is automatically
satisfied under Assumption 1. We verify this assumption by computing the
_spectral similarity_ of the Hessian and its outer-product component. We
define the spectral similarity between two matrices as follows:

$\mathfrak{S}(\bm{A},\bm{B})=\frac{\langle\bm{A},\bm{B}\rangle_{F}}{\|\bm{A}\|_{F}\|\bm{B}\|_{F}},$

where $\langle\cdot,\cdot\rangle_{F}$ denotes the Frobenius inner product and
$\|\cdot\|_{F}$ denotes the Frobenius norm. This score is equal to $1$ for two
equivalent matrices, while, for dissimilar matrices it can be arbitrarily low.
We test the score on pairs of random matrices, and obtain an average of
$-0.0002\,(\pm 0.01)$ over $1000$ trials. In Table 6 (right) we report the
score $\mathfrak{S}(\bm{H}_{t}^{O},\bm{H}_{t}^{\star})$, averaged over tasks
and seeds. For both the high and low learning rate case the score is around
$0.7$.

Table 6: Validity of the assumptions underlying GPM (left) and OGD (right).

lr | $\mathfrak{D}(\bm{H}_{t}^{\star})$
---|---
$1e^{-5}$ | $-0.04\pm 0.12$
$1e^{-2}$ | $-0.11\pm 0.13$

lr | $\mathfrak{S}(\bm{H}_{t}^{O},\bm{H}_{t}^{\star})$
---|---
$1e^{-5}$ | $0.70\pm 0.08$
$1e^{-2}$ | $0.69\pm 0.02$

####  C.1.2 Experiments Section 5.3

The second set of experiments is aimed at testing the validity of our analysis
on other architectures. We employ CNNs and Transformers, as described in
Section B. Figure 6 and 7 show the average forgetting on Split CIFAR-100 for
tasks $1$ to $20$ (previous results only considered the first $10$ tasks for
brevity). Moreover, we could compute up to the first $40$ eigenvectors for the
ResNet, and we include the results in Figure 6.

Figure 6: Convolutional networks: Average forgetting $\mathcal{E}(t)$ of SGD
and SGD† with varying values of $k$ on Split CIFAR-100 for ResNet-18. Figure
7: Vision Transformers: Average forgetting $\mathcal{E}(t)$ of SGD and SGD†
with varying values of $k$ on Split CIFAR-100 for Vision Transformer.

Next, we report a comprehensive view of the results on Split CIFAR-10 in Table
7. Similarly to Split CIFAR-100, we observe the average forgetting increasing
overall with $t$. Importantly, both the CNN and the Transformer record
significantly lower levels of forgetting when trained with SGD†, once again
supporting the validity of our theoretical results.

Table 7: $\mathcal{E}(t)$ on Split CIFAR-10. | Algorithm | $\mathcal{E}(2)$ | $\mathcal{E}(3)$ | $\mathcal{E}(4)$ | $\mathcal{E}(5)$
---|---|---|---|---|---
ResNet | SGD | $0.0127\pm 0.0200$ | $0.0186\pm 0.0196$ | $0.0375\pm 0.0515$ | $0.0285\pm 0.0267$
SGD†-$10$ | $0.0100\pm 0.0177$ | $0.0092\pm 0.0145$ | $0.0201\pm 0.0198$ | $0.0261\pm 0.0313$
SGD†-$20$ | $\bm{0.0094}\pm 0.0169$ | $\bm{0.0076}\pm 0.0167$ | $\bm{0.0171}\pm 0.0172$ | $\bm{0.0213}\pm 0.0262$
ViT | SGD | $0.0306\pm 0.0329$ | $0.0249\pm 0.0383$ | $0.0476\pm 0.0669$ | $0.0264\pm 0.0282$
SGD†-$10$ | $\bm{0.0122}\pm 0.0153$ | $0.0073\pm 0.0147$ | $0.0081\pm 0.0161$ | $0.0057\pm 0.0118$
SGD†-$20$ | $0.0126\pm 0.0173$ | $\bm{0.0061}\pm 0.0160$ | $\bm{0.0077}\pm 0.0154$ | $\bm{0.0048}\pm 0.0110$

Additionally, we report average accuracy on both Split CIFAR-10 (Table 8) and
Split CIFAR-100 (Table 9).

Table 8: Average accuracy $a(t)$ on Split CIFAR-10. We limit the learning of each task after the first one to $1$ epoch.  | Algorithm | $a(1)$ | $a(2)$ | $a(3)$ | $a(4)$ | $a(5)$
---|---|---|---|---|---|---
ResNet | SGD | $0.942\pm 0.01$ | $0.777\pm 0.15$ | $0.714\pm 0.14$ | $0.654\pm 0.11$ | $0.685\pm 0.16$
SGD†-$10$ | $0.942\pm 0.01$ | $0.778\pm 0.15$ | $0.713\pm 0.16$ | $0.656\pm 0.16$ | $0.675\pm 0.17$
SGD†-$20$ | $0.942\pm 0.01$ | $\bm{0.779}\pm 0.16$ | $\bm{0.720}\pm 0.15$ | $\bm{0.664}\pm 0.15$ | $\bm{0.684}\pm 0.17$
ViT | SGD | $0.903\pm 0.003$ | ${0.766}\pm 0.08$ | $0.739\pm 0.07$ | $0.693\pm 0.04$ | $0.7233\pm 0.10$
SGD†-$10$ | $0.903\pm 0.003$ | $\bm{0.785}\pm 0.09$ | $\bm{0.751}\pm 0.09$ | $\bm{0.713}\pm 0.10$ | $\bm{0.7264}\pm 0.09$
SGD†-$20$ | $0.903\pm 0.003$ | $0.783\pm 0.10$ | $0.7480\pm 0.09$ | $0.705\pm 0.11$ | $0.719\pm 0.10$
Table 9: Final average accuracy $a(T)$ on Split CIFAR-100, compared to the average current task accuracy $a_{t,t}$ across tasks. We limit the learning of each task after the first one to $10$ epochs.  | Algorithm | $a(T)$ | $a_{t,t}$
---|---|---|---
ResNet | SGD | $0.2215\pm 0.09$ | $\bm{0.5068}\pm 0.10$
SGD†-$10$ | $0.2366\pm 0.09$ | $0.4660\pm 0.11$
SGD†-$20$ | $0.2487\pm 0.09$ | $0.4185\pm 0.11$
SGD†-$40$ | $\bm{0.2542}\pm 0.08$ | $0.3703\pm 0.12$
ViT | SGD | $0.2258\pm 0.09$ | $\bm{0.4789}\pm 0.09$
SGD†-$10$ | $0.2452\pm 0.09$ | $0.4089\pm 0.11$
SGD†-$20$ | $\bm{0.2577}\pm 0.06$ | $0.3726\pm 0.12$

Importantly, the average accuracy reflects the balance of forgetting and
intransigence in the network. Lower forgetting comes at the cost of a lower
capacity for learning new tasks. On the contrary, a very plastic network
performs well on the current task while performing poorly on the old ones. In
Table 9 we compare the accuracy on the current task $a_{t,t}$ to the final
average accuracy of the network. SGD always outperforms SGD† on the current
task, however it achieves the lowest average accuracy. This compromise between
forgetting and intransigence, or equivalently between plasticity and
stability, is better portrayed in Figure 8, where we show the average accuracy
and forgetting of SGD† on Rotated-MNIST as we vary the parameter $\epsilon$,
controlling the fraction of spectral energy left of the memory for each task.
Simply, $\epsilon=0$ corresponds to fixing $k=P$, and $\epsilon=1$ corresponds
to fixing $k=0$. Importantly, the extremes achieve lower average accuracy.

Figure 8: Average final accuracy $a(T)$ and forgetting $\mathcal{E}(T)$ of
SGD† on Rotated-MNIST varying $\epsilon$. For each task, a $(1-\epsilon)$
fraction of the spectral energy of the Hessian matrix is stored in memory,
thus through $\epsilon$ we dynamically control the memory size.

####  C.1.3 Experiments Section 5.1

The last set of experiments is aimed at assessing the validity of the
analysis.

##### Approximations of forgetting

First, we evaluate the quality of two approximations of forgetting, namely a
second order Taylor approximation (Equation 2) and the approximation derived
from Assumptions 1-2 (Equation A.1.1). Table 10 extends the results shown in
Table 1 to the case $o=t-1$, which isolates the contribution of a single
update to forgetting. We observe the same trend in both cases, with the second
order term in the Taylor expansion providing a stable estimate of forgetting
across a wider region of the parameter space.

Table 10: Approximation error, Equation 2, on Rotated-MNIST. | lr |  $1^{\text{st}}$ order |  $2^{\text{nd}}$ order | Taylor | $\mathcal{E}_{o}(t)$ | $\|\bm{\theta}_{t}-\bm{\theta}_{o}\|$
---|---|---|---|---|---|---
$o\,\in[1,t-1]$ | $1e^{-5}$ | ${0.43}\pm 0.30$ | ${0.26}\pm 0.16$ | $\bm{0.15}\pm 0.15$ | $0.30\pm 0.30$ | $1.23\pm 0.51$
$1e^{-2}$ | $2.33\pm 1.87$ | $\bm{1.49}\pm 1.31$ | $1.55\pm 1.32$ | $2.26\pm 1.85$ | $8.19\pm 2.56$
$o=t-1$ | $1e^{-5}$ | ${0.16}\pm 0.07$ | ${0.19}\pm 0.09$ | $\bm{0.05}\pm 0.02$ | $0.018\pm 0.02$ | $0.71\pm 0.13$
$1e^{-2}$ | $0.39\pm 0.06$ | $\bm{0.09}\pm 0.05$ | $0.13\pm 0.05$ | $0.33\pm 0.05$ | $5.48\pm 0.17$

In Table 11 we report the error of the average forgetting estimate given by
Equation A.1.1 on Rotated MNIST for different values of $t$. Interestingly, we
notice that the error is not monotonic, although forgetting constantly
increases.

Table 11: Equation A.1.1 approximation error on Rotated-MNIST. $t$ | lr | $|\hat{\mathcal{E}}(t)-\mathcal{E}(t)|$ | $\mathcal{E}(t)$
---|---|---|---
$2$ | $1e^{-5}$ | $\bm{0.047}\pm 0.01$ | $0.024\pm 0.01$
$1e^{-2}$ | $0.062\pm 0.07$ | $0.36\pm 0.06$
$3$ | $1e^{-5}$ | $\bm{0.049}\pm 0.005$ | $0.122\pm 0.02$
$1e^{-2}$ | $0.74\pm 0.1050$ | $1.27\pm 0.06$
$4$ | $1e^{-5}$ | $\bm{0.073}\pm 0.02$ | $0.255\pm 0.03$
$1e^{-2}$ | $1.17\pm 0.24$ | $2.45\pm 0.23$
$5$ | $1e^{-5}$ | $\bm{0.068}\pm 0.05$ | $0.48\pm 0.07$
$1e^{-2}$ | $0.80\pm 0.13$ | $3.09\pm 0.14$

Finally, we evaluate the quality of the estimates of forgetting for the ResNet
experiments on Split CIFAR-100. In order to do so, we employ low rank
approximations of the Hessian matrix, obtained through iterative methods. In
Table 12 and 13 we report results for multiple rank values, $r=10,20,30,40$.
Overall, the forgetting approximation quality increases with the rank.

Table 12: Approximation error, Equation 2, on Split CIFAR-100. $r$ |  $1^{\text{st}}$ order |  $2^{\text{nd}}$ order | Taylor | $\mathcal{E}_{o}(t)$ | $\|\bm{\theta}_{t}-\bm{\theta}_{o}\|$
---|---|---|---|---|---
10 | $0.63\pm 0.31$ | $0.54\pm 0.38$ | $0.60\pm 0.30$ | $0.57\pm 0.39$ | $2.15\pm 0.89$
20 | $0.63\pm 0.31$ | $0.50\pm 0.37$ | $0.54\pm 0.30$ | $0.57\pm 0.39$ | $2.15\pm 0.89$
30 | $0.63\pm 0.31$ | $0.41\pm 0.30$ | $0.42\pm 0.26$ | $0.57\pm 0.39$ | $2.15\pm 0.89$
40 | $0.63\pm 0.31$ | $\bm{0.27}\pm 0.20$ | $\bm{0.21}\pm 0.16$ | $0.57\pm 0.39$ | $2.15\pm 0.89$
Table 13: Equation A.1.1 approximation error on Split CIFAR-100.  $r$ | $|\hat{\mathcal{E}}(t)-\mathcal{E}(t)|$ | $\mathcal{E}(t)$
---|---|---
10 | $0.37\pm 0.17$ | $0.57\pm 0.13$
20 | $0.36\pm 0.16$ | $0.57\pm 0.13$
30 | $0.34\pm 0.14$ | $0.57\pm 0.13$
40 | $\bm{0.30}\pm 0.11$ | $0.57\pm 0.13$

##### Perturbation analysis

In Section 5.1 we propose a tool to measure the range of validity of the
assumptions of our analysis, named _perturbation analysis_. Here, we present
the detailed results of the perturbation analysis, for all the tasks in the
Rotated MNIST setting. These can be found in Figure 9.

Figure 9: Perturbation score $\mathfrak{s}(r)$ on all the tasks of the
Rotated-MNIST challenge, learned with SGD. The dashed green line highlights
the value of r for which the score converges to 1 (marked by the dashed brown
line).

Next, to further complement these results, we additionally provide results for
ResNet18 in the Split-CIFAR100 setting in Figure 10 and that for ViT in Figure
11.

Figure 10: Perturbation score $\mathfrak{s}(r)$ on all the tasks of the Split
CIFAR-100 challenge, learned with SGD. The dashed green line highlights the
value of r for which the score converges to 1 (marked by the dashed brown
line). Figure 11: Perturbation score $\mathfrak{s}(r)$ on all the tasks of the
Split CIFAR-10 challenge, learned with SGD. The dashed green line highlights
the value of r for which the score converges to 1 (marked by the dashed brown
line).

The observations from our perturbation analysis on Rotated-MNIST largely
extend to these latter settings. Notice that, as the network size increases,
the perturbation score converges to $1$ for higher values of $r$ (marked by
the dashed green line). There is more noise in some of the plots, which can be
attributed to the fact that for these bigger networks, we are relying on the
power method to obtain the top eigenvectors, unlike the exact Hessian
computation in the case of Rotated-MNIST.