Year: 2020

Abstract:
In Continual Learning settings, deep neural networks are prone to Catastrophic Forgetting. Orthogonal Gradient Descent was proposed to tackle the challenge. However, no theoretical guarantees have been proven yet. We present a theoretical framework to study Continual Learning algorithms in the Neural Tangent Kernel regime. This framework comprises closed form expression of the model through tasks and proxies for Transfer Learning, generalisation and tasks similarity. In this framework, we prove that OGD is robust to Catastrophic Forgetting then derive the first generalisation bound for SGD and OGD for Continual Learning. Finally, we study the limits of this framework in practice for OGD and highlight the importance of the Neural Tangent Kernel variation for Continual Learning with OGD.

heading: 1 INTRODUCTION
text: Continual Learning is a setting in which an agent is exposed to multiples tasks sequentially (Kirkpatrick et al., 2016). The core challenge lies in the ability of the agent to learn the new tasks while retaining the knowledge acquired from previous tasks. Too much plasticity (Nguyen et al., 2018) will lead to catastrophic forgetting, which means the degradation of the ability of the agent to perform the past tasks (McCloskey & Cohen 1989, Ratcliff 1990, Goodfellow et al. 2014). On the other hand, too much stability will hinder the agent from adapting to new tasks.
While there is a large literature on Continual Learning (Parisi et al., 2019), few works have addressed the problem from a theoretical perspective. Recently, Jacot et al. (2018) established the connection between overparameterized neural networks and kernel methods by introducing the Neural Tangent Kernel (NTK). They showed that at the infinite width limit, the kernel remains constant throughout training. Lee et al. (2019) also showed that, in the infinite width limit or Neural Tangent Kernel (NTK) regime, a network evolves as a linear model when trained on certain losses under gradient descent. In addition to these findings, recent works on the convergence of Stochastic Gradient Descent for overparameterized neural networks (Arora et al., 2019) have unlocked multiple mathematical tools to study the training dynamics of over-parameterized neural networks.
We leverage these theoretical findings in order to to propose a theoretical framework for Continual Learning in the NTK regime then prove convergence and generalisation properties for the algorithm Orthogonal Gradient Descent for Continual Learning (Farajtabar et al., 2019).
Our contributions are summarized as follows:
1. We present a theoretical framework to study Continual Learning algorithms in the Neural Tangent Kernel (NTK) regime. This framework frames Continual Learning as a recursive kernel regression and comprises proxies for Transfer Learning, generalisation, tasks similarity and Curriculum Learning. (Thm. 1, Lem. 1 and Thm. 3).
2. In this framework, we prove that OGD is robust to forgetting with respect to an arbitrary number of tasks under an infinite memory (Sec . 5, Thm. 2).
3. We prove the first generalisation bound for Continual Learning with SGD and OGD. We find that generalisation through tasks depends on a task similarity with respect to the NTK. (Sec. 5, Theorem 3)
4. We study the limits of this framework in practical settings, in which the Neural Tangent Kernel may vary. We find that the variation of the Neural Tangent Kernel impacts negatively
the robustness to Catastrophic Forgetting of OGD in non overparameterized benchmarks. (Sec. 6)

heading: 2 RELATED WORKS
text: Continual Learning addresses the Catastrophic Forgetting problem, which refers to the tendency of agents to ”forget” the previous tasks they were trained on over the course of training. It’s an active area of research, several heuristics were developed in order to characterise it (Ans & Rousset 1997, Ans & Rousset 2000, Goodfellow et al. 2014, French 1999, McCloskey & Cohen 1989, Robins 1995, Nguyen et al. 2019). Approaches to Continual Learning can be categorised into: regularization methods, memory based methods and dynamic architectural methods. We refer the reader to the survey by Parisi et al. (2019) for an extensive overview on the existing methods. The idea behind memory-based methods is to store data from previous tasks in a buffer of fixed size, which can then be reused during training on the current task (Chaudhry et al. 2019, Van de Ven & Tolias 2018). While dynamic architectural methods rely on growing architectures which keep the past knowledge fixed and store new knowledge in new components, such as new nodes or layers. (Lee et al. 2018, Schwarz et al. 2018) Finally, regularization methods regularize the objective in order to preserve the knowledge acquired from the previous tasks (Kirkpatrick et al. 2016, Aljundi et al. 2018, Farajtabar et al. 2019, Zenke et al. 2017).
While there is a large literature on the field, there is a limited number of theoretical works on Continual Learning. Alquier et al. (2017) define a compound regret for lifelong learning, as the regret with respect to the oracle who would have known the best common representation for all tasks in advance. Knoblauch et al. (2020) show that optimal Continual Learning algorithms generally solve an NP-HARD problem and will require perfect memory not to suffer from catastrophic forgetting. Benzing (2020) presents mathematical and empirical evidence that the two methods – Synaptic Intelligence and Memory Aware Synapses – approximate a rescaled version of the Fisher Information.
Continual Learning is not limited to Catastrophic Forgetting, but also closely related to Transfer Learning. A desirable property of a Continual Learning algorithm is to enable the agent to carry the acquired knowledge through his lifetime, and transfer it to solve new tasks. A new theoretical study of the phenomena was presented by Liu et al. (2019). They prove how the task similarity contributes to generalisation, when training with Stochastic Gradient Descent, in a two tasks setting and for over-parameterised two layer RELU neural networks.
The recent findings on the Neural Tangent Kernel (Jacot et al., 2018) and on the properties of overparameterized neural networks (Du et al. 2018, Arora et al. 2019) provide powerful tools to analyze their training dynamics. We build up on these advances to construct a theoretical framework for Continual Learning and study the generalisation properties of Orthogonal Gradient Descent.

heading: 3 PRELIMINARIES
text: Notation We use bold-faced characters for vectors and matrices. We use ‖·‖ to denote the Euclidean norm of a vector or the spectral norm of a matrix, and ‖ · ‖F to denote the Frobenius norm of a matrix. We use 〈·, ·〉 for the Euclidean dot product, and 〈·, ·〉H the dot product in the Hilbert space H. We index the task ID by τ . The ≤ operator if used with matrices, corresponds to the partial ordering over symmetric matrices. We denote N the set of natural numbers, R the space of real numbers and N? for the set Nr {0}. We use ⊕ to refer to the direct sum over Euclidean spaces.

heading: 3.1 CONTINUAL LEARNING
text: Continual Learning considers a series of tasks {T 1, T 2, . . .}, where each task can be viewed as a separate supervised learning problem. Similarly to online learning, data from each task is revealed only once. The goal of Continual Learning is to model each task accurately with a single model. The challenge is to achieve a good performance on the new tasks, while retaining knowledge from the previous tasks (Nguyen et al., 2018).
We assume the data from each task T τ , τ ∈ N?, is drawn from a distribution Dτ . Individual samples are denoted (xτ,i, yτ,i), where i ∈ [nτ ]. For a given task T τ , the model is denoted fτ , we use the
superscript (t) to indicate the training iteration t ∈ N, while we use the superscript ? to indicate the asymptotic convergence. For the regression case, given a ridge regularisation coefficient λ ∈ R+, for all t ∈ N, we write the train loss for a task T τ as :
Lτ (wτ (t)) = nτ∑ i=1 (f (t)τ (xτ,i)− yτ,i)2 + λ ∥∥wτ (t)−w?τ−1∥∥2.

heading: 3.2 OGD FOR CONTINUAL LEARNING
text: Let T T the current task, where T ∈ N?. For all i ∈ [nT ], let vT,i = ∇wf?T−1(xT−1,i), which is the Jacobian of task T T . We define Eτ = vec({vτ,i, i ∈ [nτ ]}), the subspace induced by the Jacobian. The idea behind OGD (Farajtabar et al., 2019) is to update the weights along the projection of the gradient on the orthogonal space induced by the Jacobians over the previous tasks E1 ⊕ . . .⊕ Eτ−1. The update rule at an iteration t ∈ N? for the task T T is as follows :
wT (t+ 1) = wT (t)− ηΠE⊥T−1∇wL T (wT (t)).
The intuition behind OGD is to “preserve the previously acquired knowledge by maintaining a space consisting of the gradient directions of the neural networks predictions on previous tasks” (Farajtabar et al., 2019). Throughout the paper, we only consider the OGD-GTL variant which stores the gradient with respect to the ground truth logit.

heading: 3.3 NEURAL TANGENT KERNEL
text: In their seminal paper, Jacot et al. (2018) established the connection between deep networks and kernel methods by introducing the Neural Tangent Kernel (NTK). They showed that at the infinite width limit, the kernel remains constant throughout training. Lee et al. (2019) also showed that a network evolves as a linear model in the infinite width limit when trained on certain losses under gradient descent.
Throughout our analysis, we make the assumption that the neural network is overparameterized, and consider the linear approximation of the neural network around its initialisation:
f (t)(x) ≈ f (0)(x) +∇wf (0)(x)T (w(t)−w(0)).

heading: 4 CONVERGENCE - CONTINUAL LEARNING AS A RECURSIVE KERNEL REGRESSION
text: In this section, we derive a closed form expression for the Continual Learning models through tasks. We find that Continual Learning models can be expressed with recursive kernel ridge regression across tasks. We also find a that the NTK of OGD is recursive with respect to the projection of its feature map on the tasks’ spaces. The result is presented in Theorem 1, a stepping stone towards proving the generalisation bound for OGD in Sec. 5.

heading: 4.1 CONVERGENCE THEOREM
text: Theorem 1 (Continual Learning as a recursive Kernel Regression)
Given T 1, . . . , T T a sequence of tasks. Fix a learning rate sequence (ητ )τ∈[T ] and a ridge regularisation coefficient λ ∈ R+. If, for all τ , the learning rate satisfies ητ < 1‖κτ (Xτ ,Xτ )+λI‖ , then for all τ , wτ (t) converges linearly to a limit solution w?τ such that
f?τ (x) = f ? τ−1(x) + κτ (x,Xτ ) T (κτ (Xτ ,Xτ ) + λI) −1ỹτ ,
where
κτ (x,x ′) = φ̃τ (x)φ̃τ (x ′)T ,
ỹτ = yτ − yτ−1→τ , yτ−1→τ = f ? τ−1(Xτ ),
φ̃τ (x) = { ∇wf?0 (x) ∈ Rd for SGD , Tτ∇wf?0 (x) ∈ Rd−Mτ for OGD.
and {Tτ ∈ Rd−Mτ ,d, τ ∈ [T ]} are projection matrices from Rd to ( τ⊕ k=1 Ek)⊥ andMτ = dim( τ⊕ k=1 Ek) .
The theorem describes how the model f?τ evolves across tasks. It is recursive because the learning is incremental. For a given task T τ , f?τ−1(x) is the knowledge acquired by the agent up to the task T τ−1. At this stage, the model only fits the residual ỹτ = yτ − yτ−1→τ , which complements the knowledge acquired through previous tasks. This residual is also a proxy for task similarity. If the tasks are identical, the residual is equal to zero. The knowledge increment is captured by the term: κτ (x,Xτ ) T (κτ+1(Xτ ,Xτ ) + λI) −1ỹτ . Finally, the task similarity is computed with respect to the most recent feature map φ̃τ , and κτ is the NTK with respect to the feature map φ̃τ .
Remark 1 The recursive relation from Theorem 1 can also be written as a linear combination of kernel regressors as follows:
f?τ (x) = τ∑ k=1 f̃ ? k(x),
where
f̃ ?
k(x) = κk(x,Xk) T (κk(Xk,Xk) + λI) −1ỹk.

heading: 4.2 DISTANCE FROM INITIALISATION THROUGH TASKS
text: As described in Sec. 4.1, ỹτ is a residual. It is equal to zero if the model f ? τ−1 makes perfect predictions on the next task T τ . The more the next task T τ is different, the further the neural network needs to move from its previous state in order to fit it. Corollary 1 tracks the distance from initialisation as a function of task similarity.
Corollary 1 For SGD, and for OGD under the additional assumption that {Tτ , τ ∈ [T ]} are orthonormal,∥∥w?τ+1 −w?τ∥∥2 = ỹTτ+1(κ(Xτ+1,Xτ+1) + λI)−1κ(Xτ+1,Xτ+1)(κ(Xτ+1,Xτ+1) + λI)−1ỹτ+1, Remark 2 Corollary 1 can be applied to get a similar result to Theorem 3 by Liu et al. (2019). In this remark, we consider mostly their notations. Their theorem states that under some conditions, for 2-layer neural networks with a RELU activation function, with probability no less than 1− δ over random initialisation,
‖W(P )−W(Q)‖F ≤ √ ỹTP→QH ∞−1 P ỹP→Q + ,
where, in their work:
yP→Q = H ∞,T PQ H ∞−1 P yP ,
ỹP→Q = yQ − yP→Q.
Note that H∞P is a Gram matrix, which also corresponds to the NTK of the neural network they consider. We see an analogy with our result, where we work directly with the NTK, with no assumptions on the neural network. One important observation is that, to our knowledge, since there are no guarantees for the invertibility of our Gram matrix, we add a ridge regularisation to work with a regularised matrix, which is then invertible. In our setting, by considering λ → 0, and with the additional assumption of invertibility of Hτ,0,which is valid in the two-layer overparameterized RELU neural network considered in the setting of Liu et al. (2019), we can recover a similar approximation.

heading: 5 OGD : LEARNING WITHOUT FORGETTING, PROVABLY
text: In this section, we study the generalisation properties of OGD building-up on Thm. 1. First, we prove that OGD is robust to catastrophic forgetting with respect to all previous tasks (Theorem 2). Then, we present the main generalisation theorem for OGD (Thm. 3). The theorem provides several insights on the relation between task similarity and generalisation. Finally, we present how the Rademacher complexity relates to task similarity across a large number of tasks (Lemma 1). The lemma states that the more dissimilar tasks are, the larger the class of functions explored by the neural network, with high probability. This result highlights the importance of the curriculum for Continual Learning.

heading: 5.1 MEMORISATION PROPERTY OF OGD
text: The key to obtaining tight generalisation bounds for OGD is Theorem 2.
Theorem 2 (No-forgetting Continual Learning with OGD) Given a task T τ , for all xk,i ∈ Dk, a sample from the training data of a previous task T k, given that the Jacobian of xk,i belongs to OGD’s memory, it holds that:
f?τ (xk,i) = f ? k (xk,i).
As motivated by Farajtabar et al. (2019), the orthogonality of the gradient updates aims to preserve the acquired knowledge, by not altering the weights along relevant dimensions when learning new tasks. Theorem 2 implies that, given an infinite memory, the training error on all samples from the previous tasks is unchanged, when training with OGD.

heading: 5.2 GENERALISATION PROPERTIES OF SGD AND OGD
text: Now, we state the main generalisation theorem for OGD, which provides generalisation bounds on the data from all the tasks, for SGD and OGD.
Theorem 3 (Generalisation of SGD and OGD for Continual Learning)
Let {T 1, . . . T T } be a sequence of tasks. Let be {D1, . . . ,DT } the respective distributions over Rd × {−1, 1}. Let {(xτ,i, yτ,i), i ∈ [nt], τ ∈ [T ]} be i.i.d. samples from Dτ , τ ∈ [T ]. Denote Xτ = (xτ,1, . . . ,xτ,nτ ), yτ = (yτ,1, . . . , yτ,nτ ). Consider the kernel ridge regression solution f ? T , then, for any loss function ` : R×R→ [0, c] that is c-Lipschitz in the first argument, with probability at least 1− δ,
LDτ (f?T ) ≤  λ2 nτ ỹτ (κτ (Xτ ,Xτ ) + λI) −1ỹτ +RT + 3c √ log(2/δ) 2nT , for OGD, τ ∈ [1, T ], λ2 nτ ỹτ (κτ (Xτ ,Xτ ) + λI) −1ỹτ +RT + 3c √ log(2/δ) 2nT , for SGD, τ = T , λ2
nτ ỹTτ (kτ (Xτ ,Xτ ) + λI) −1ỹτ + 1 nT ∑T k=τ+1Hk,τ +RT + 3c √ log(2/δ) 2nT , for SGD, τ < T .
where
ỹτ = yτ − f?τ−1(Xτ ),
RT = T∑ τ=1
√ tr(κτ (Xτ ,Xτ ))
n2τ ỹTτ (κτ (Xτ ,Xτ ) + λI) −1ỹτ ,
Hk,τ = ỹ T k (kk(Xk,Xk) + λI) −1kk(Xk,Xτ )kk(Xτ ,Xk)(kk(Xk,Xk) + λI) −1ỹk.
Theorem 3 shows that the generalisation bound for OGD is tighter than SGD. This results from Thm. 2, which states that OGD is robust to Catastrophic Forgetting. The bound is looser for SGD over the past tasks through the forgetting term that appears.
The bound of Theorem 3 comprises the following main terms :
• λ 2
nτ ỹτ (κτ (Xτ ,Xτ ) + λI) −1ỹτ : this term is due to the regularisation and describes that the empirical loss is not equal to zero due to the regularisation term. This term tends to zero in case there is no regularisation. For interpretation purposes, in App. D.2.7, we show that the empirical loss tends to zero in the no-regularisation case.
• RT captures the impact of task similarity on generalisation which we discuss in Sec. 5.3. • ∑T k=τ+1Hk,τ is a residual term that appears for SGD only. It is due to the catastrophic
forgetting that occurs with SGD. It also depends on the tasks similarity.
These bounds share some similarities with the bounds derived by Arora et al. (2019), Liu et al. (2019) and Hu et al. (2019), where in these works, the bounds were derived for supervised learning settings, and in some cases for two-layer RELU neural networks. Similarly, the bounds depend on the Gram matrix of the data, with the feature map corresponding to the NTK.

heading: 5.3 THE IMPACT OF TASK SIMILARITY ON GENERALISATION
text: Now, we state Lemma 1, which tracks the Rademacher complexity through tasks.
Lemma 1 Keeping the same notations and setting as Theorem 3, the Rademacher Complexity can be bounded as follows:
R̂(FT ) ≤ T∑ τ=1 O
(√ tr(κτ (Xτ ,Xτ ))
n2τ ỹTτ (κτ (Xτ ,Xτ ) + λI) −1ỹτ
) ;
where FT is the function class covered by the model up to the task T τ
The right hand side term RT in the upper bound of the generalisation theorem follows directly from Lemma 1, and it draws a complexity measure for Continual Learning. It states that the upper bound on the Rademacher complexity increases when the tasks are dissimilar. We define the NTK task dissimilarity between two subsequent tasks T τ−1 and T τ as S̄τ−1→τ = ỹTτ (κτ (Xτ ,Xτ )+λI)−1ỹτ . This dissimilarity is a generalisation of the term that appears in the upper bound of Thm. 2 by Liu et al. 2019. The knowledge from the previous tasks is encoded in the kernel κτ , through the feature map φτ . As an edge case, if two successive tasks are identical, S̄τ−1→τ = 0 and the upper bound does not increase.
Implications for Curriculum Learning We also observe that the upper bound depends on the task ordering, which may provide a theoretical explanation on the importance of learning with a curriculum (Bengio et al. (2009)). In the following, we present an edge case which provided an intuition on how the bound captures the importance of the order. Consider two dissimilar tasks T 1 and T 2. A sequence of tasks alternating between T 1 and T 2 will lead to a large upper bound, as explained in the first paragraph, while a sequence of tasks concatenating two sequences of T 1 then T 2 will lead to a lower upper bound.

heading: 6 THE IMPACT OF THE NTK VARIATION ON OGD
text: In the previous section, we demonstrated that under the NTK regime and an infinite memory, OGD is provably robust to catastrophic forgetting. In practical settings, these two assumptions do not hold, therefore, in this section, we study the limits of the NTK regime. We present OGD+, a variant of OGD we use to study the importance of the NTK variation for Continual Learning in practice.
In order to decouple the NTK variation phenomena in our experiments, we propose then study the OGD+ algorithm, which is designed to be more robust to the NTK variation, through updating its orthonormal basis with respect to all the tasks at the end of each task, as opposed to OGD.
Algorithm 1 presents the OGD+ algorithm, we highlight the differences with OGD in red. The main difference is that OGD+ stores the feature maps with respect to the samples from previous tasks, in addition to the feature maps with respect to the samples from the current task, as opposed to OGD. This small change is motivated by the variation of the NTK in practice. In order to compute the feature maps with respect to the previous samples, OGD+ saves these samples in a dedicated memory, we call this storage the samples memory. This memory comes in addition to the orthonormal feature maps memory. The only role of the samples memory is to compute the updated feature maps at the beginning of each task.
natbib
Algorithm 1: OGD+ for Continual Learning Input :A task sequence T 1, T 2, . . ., learning rate η
1. Initialize SJ ← {} ; SD ← {}; w← w0 2. for Task ID τ = 1, 2, 3, . . . do
repeat g← Stochastic Batch Gradient for T τ at w; g̃ = g − ∑ v∈SJ projv(g);
w← w − ηg̃ until convergence; Sample S ⊂ SD; for (x, y) ∈ Dτ ⋃ S and k ∈ [1, c] s.t. yk = 1 do
u← ∇fτ (x;w)− ∑ v∈SJ projv(∇fτ (x;w)) SJ ← SJ ⋃ {u}
end Sample D ⊂ Dτ ; Update SD ← SD ⋃ D
end

heading: 7 EXPERIMENTS
text: We study the validity Theorem 2 which states that under the given conditions, OGD is perfectly robust to Catastrophic Forgetting (Sec. 7.1). We find that the Catastrophic Forgetting of OGD decreases with over-parameterization. Then, we perform an ablation study using OGD+ in order to study the applicability and limits of the constant Jacobian assumption in practice (Sec. 7.2). We find that the assumption holds for some benchmarks, and that updating the Jacobian (OGD+) is critical for the robustness of OGD in the non-overparameterized benchmarks. Finally, we present a broader picture of the performance of OGD+ against standard Continual Learning baselines (Sec. 7.3)
Benchmarks We use the standard benchmarks similarly to Goodfellow et al. (2014) and Chaudhry et al. (2019). Permuted MNIST (Goodfellow et al., 2014) consists of a series of MNIST supervised learning tasks, where the pixels of each task are permuted with respect to a fixed permutation. Rotated MNIST (Farajtabar et al., 2019) consists of a series of MNIST classification tasks, where the images are rotated with respect to a fixed angle, monotonically. We increment the rotation angle by 5 degrees at each new task. Split CIFAR-100 (Chaudhry et al., 2019) is constructed by splitting the original CIFAR-100 dataset (Krizhevsky, 2009) into 20 disjoint subsets, where each subset is formed by sampling without replacement 5 classes out of 100. In order to assess the robustness to catastrophic forgetting over long tasks sequences, we increase the length of the tasks streams from 5 to 15 for the MNIST benchmarks, and consider all the 20 tasks for the Split CIFAR-100 benchmark. We also use the CUB200 benchmark (Jung et al., 2020) which contains 200 classes, split into 10 tasks. This benchmark is more overparameterized than the other benchmarks.
Evaluation Denoting aT,τ the accuracy of the model on the task T τ after being trained on the task T T , we track two metrics introduced by Chaudhry et al. (2019) and Lopez-Paz & Ranzato (2017) :
AVERAGE ACCURACY (AT ) is the average accuracy after the model has been trained on the task T T :
AT = 1
T T∑ τ=1 aT,τ .
AVERAGE FORGETTING (FT ) is the average forgetting after the model has been trained on the task T T :
FT = 1
T − 1 T−1∑ τ=1 max t∈{1,...,T−1} (at,τ − aT,τ ).
OVER-PARAMETERIZATION We track over-parameterization of a given benchmark as the number of trainable parameters over the average number of samples per task (Arora et al., 2019) :
O = p∑T
τ=1 nτ/T .
Architectures For the MNIST benchmarks, we use the same neural network architectures as Farajtabar et al. (2019). However, since the OGD algorithm doesn’t scale to large neural networks due to memory limits, we considered smaller scale neural networks for the CIFAR100 and CUB200 benchmarks. For CIFAR100, we use the LeNet architecture (Lecun et al., 1998). For CUB200, we keep the pretrained AlexNet similarly to Jung et al. (2020), then freeze the features layers and replace the default classifier with a smaller neural network (App. F.1.1).

heading: 7.1 ABLATION STUDY : FOR OGD, CATASTROPHIC FORGETTING DECREASES WITH OVERPARAMETERIZATION (THM. 2)
text: Theorem 2 states that in the NTK regime, given an infinite memory, the train error of OGD is unchanged. We study the impact of overparameterization on Catastrophic Forgetting of OGD through an ablation study on the number of parameters of the model.
Experiment We train a model on the full task sequence on the MNIST and CIFAR100 benchmarks, then measure the variation of the train accuracy of the memorised samples from the first task. The reason we consider the samples in the memory is the applicability of Thm. 2 to these samples only. Fixing the datasets sizes, our proxy for overparameterization is the hidden size, which we vary.
Results Figures 1 and 2 show that the train error variation decreases with overparameterization for OGD, on the MNIST and CIFAR100 benchmarks. This result concurs with Thm. 2.

heading: 7.2 ABLATION STUDY : FOR NON OVER-PARAMETERIZED BENCHMARKS, UPDATING THE
text: JACOBIAN IS CRITICAL TO OGD’S ROBUSTNESS (THM. 2)
Our analysis relies on the over-parameterization assumption, which implies that the Jacobian is constant through tasks. Theorem 2 follows from this property. However, in practice, this assumption may not hold and forgetting is observed for OGD. We study the impact of the variation of the Jacobian in practice on OGD.
In order to measure this impact, we perform an ablation study on OGD, taking into account the Jacobian’s variation (OGD+) or not (OGD). OGD+ takes into account the Jacobian’s variation by updating all the stored Jacobians at the end of each task.
Experiment We measure the average forgetting (Chaudhry et al., 2019) without (OGD) or with (OGD+) accounting for the Jacobian’s variation, on the MNIST, CIFAR100 and CUB200 benchmarks.
Results Table 1 shows that for the Rotated MNIST and Permuted MNIST benchmarks, which are the least overparameterized, OGD+ is more robust to Catastrophic Forgetting than OGD. This improvement follows from the variation of the Jacobian in these benchmarks and that OGD+ accounts for it. While on CIFAR100 and CUB200, the most over-parameterized benchmark, the robustness of OGD and OGD+ is equivalent. For these benchmarks, since the variation of the Jacobian is smaller, due to overparameterization, OGD+ is equivalent to OGD.
This result confirms our initial hypothesis that the Jacobian’s variation in non-overparameterized settings such as MNIST is an important reason the OGD algorithm is prone to Catastrophic Forgetting. This result also highlights the importance of developing a theoretical framework for the non-overparameterized setting, in order to capture the properties of OGD outside the NTK regime.

heading: 7.3 BENCHMARKING OGD+ AGAINST OTHER CONTINUAL LEARNING BASELINES
text: In order to provide a broader picture on the robustness of OGD+ to Catastrophic Forgetting, we benchmark it against standard Continual Learning baselines.
Results Table 2 shows that, on the Permuted MNIST and Rotated MNIST benchmarks, which are the least overparameterized, OGD+ draws an improvement over OGD and is competitive with other Continual Learning methods. On the most overparameterized benchmarks, CIFAR100 and CUB200, OGD+ is not competitive.

heading: 8 CONCLUSION
text: We presented a theoretical framework for Continual Learning algorithms in the NTK regime, then leveraged the framework to study the convergence and generalisation properties of the SGD and OGD algorithms. We also assessed our theoretical results through experiments and highlighted the applicability of the framework in practice. Our analysis highlights multiple connections to neighbouring fields such as Transfer Learning and Curriculum Learning. Extending the analysis to other Continual Learning algorithms is a promising future direction, which would provide a better understanding of the various properties of these algorithms and how they could be improved. Additionally, our experiments highlight the limits of the applicability of the framework to nonoverparameterized settings. In order to gain a better understanding of the properties of the OGD algorithm in this setting, extending the framework beyond the over-parameterization assumption is an important direction. We hope this work provides new keys to investigate these directions.

heading: A COMPLEMENTARY DISCUSSION

heading: A.1 NTK VARIATION - THE IMPORTANCE OF ORTHOGONALITY FOR THE OGD, OGD+ AND A-GEM ALGORITHMS
text: In the main article, we focused only on the SGD, OGD and OGD+ algorithms. In this section, we highlight a connection of these algorithms to the A-GEM algorithm. All these algorithms perform orthogonal projections during the weight update step, however these projections differ in the following ways :
• the span of the space the updates are orthogonal to. • the rate at which the projection space is updated.
Additionally, the A-GEM algorithm present the additional property of allowing Positive Backward Transfer by design. Positive Backward Transfer is a desirable property in the sense that the generalisation on a past task increases while training on the current task.
Similarities among the algorithms Table 3 presents an overview of the connections between the algorithm. In practice, the models are not trained in the NTK regime. Since the feature map changes through training, the orthogonality constraint of OGD becomes less relevant and may harm the learning. On the other hand, while A-GEM performs a projection on a smaller subspace which may not protect all the subspaces, the subspace is updated as it is computed at each training step, the updates are therefore expected to be more relevant. Finally OGD+ lies at the intersection of both, while it doesn’t update the feature maps at each gradient step, the projection constraint is with respect to a larger space.
On the theoretical connection between OGD and A-GEM The A-GEM algorithm (Chaudhry et al., 2019) is a state of the art Continual Learning algorithm on the standard benchmarks. The idea behind the algorithm is to perform a gradient descent if an estimate of the loss over the previous tasks increases or is unchanged. Otherwise the gradient is projected orthogonally to the gradient over the loss estimate over the previous tasks.
We find that OGD draws a upper bound in comparison to A-GEM-NT in terms of generalisation error, as stated in Proposition 1.
Proposition 1 In the NTK regime, OGD implies A-GEM with no Positive Backward Transfer.
The proof is presented in App. E.1.
Experiments The extended experiments on the importance of the NTK variation for Continual Learning (Sec. F.3), show that A-GEM outperforms OGD and OGD+ on most benchmarks. A probable reason behind this difference is the rate of update of the feature map for the A-GEM algorithm, even though it spans a smaller space than OGD and OGD+.

heading: A.2 EXPRESSIONS OVERVIEW
text: For convenience, we present in Table 4 an overview of the notions that were mentioned in the main article, with their respective mathematical expressions.

heading: B PROOFS OVERVIEW

heading: B.1 CONVERGENCE :
text: Theorem 1 : Convergence of SGD and OGD for Continual Learning We prove Theorem 1 by induction. We rewrite the loss function as a regression on the residual ỹτ instead of yτ . Then, we rewrite the optimisation objective as an unconstrained strongly convex optimisation problem. Finally, we compute the unique solution in a closed form. The full proof is presented in App. C.1.
Remark 1 : Continual Learning as a recursive Kernel Regression The remark follows directly from the recursive form of Theorem 1.
Corollary 1 : Distance from initialisation through tasks The proof follows immediately from the proof of Theorem 1, in which we compute a closed form of the weights variation. It is presented in App. C.2.

heading: B.2 GENERALISATION :
text: Theorem 2 : No-forgetting Continual Learning with OGD The proof relies on the orthogonality property of the OGD update, which implies that the subspaces spanned by the samples in the memory would not have any changes incurred. The proof is presented in App . D.1
Theorem 3 : Generalisation of SGD and OGD for Continual Learning The proof or Theorem 3 is presented in App. D.2. The proof follows the following structure :
• Bounding the Rademacher complexity (App. D.2.3) : First, we state the technical Lemma 3 that upper bounds the Rademacher complexity of the function class that corresponds to the set of linear combinations of kernel regressors. Then we apply the lemma to the function class obtained through Theorem 1.
• Bounding the empirical loss for SGD (App. D.2.5) : the error is the same as OGD on the last task. While on the previous tasks, Catastrophic Forgetting can be incurred which implies the appearance of a residual term that corresponds to the forgetting.
• Bounding the empirical loss for OGD (App. D.2.4) : The proof techniques are very similar to the SGD case, however we leverage Theorem 2 in order to derive tighter bounds due to the absence of Catastrophic Forgetting.
• Wrap-up (App. D.2.6) : Finally, we wrap-up all the lemmas to derive the bound of Theorem 3.
Lemma 1 - Implications for Curriculum Learning This results follows from the technical Lemma 3, which upper bounds the Rademacher complexity of the function class that corresponds to the set of linear combinations of kernel regressors.

heading: B.3 THE IMPORTANCE OF THE NTK VARIATION FOR CONTINUAL LEARNING :
text: Proposition 1 - OGD implies A-GEM-NT The proof relies mainly on Theorem 2 stating the robustness of OGD to Catastrophic Forgetting. We derive the A-GEM update then apply Theorem 2, which leads to the implication. The full proof is presented in App. D.2.3.

heading: C MISSING PROOFS OF SECTION 4 - CONVERGENCE

heading: C.1 PROOF OF THEOREM 1
text: Stochastic Gradient Descent We start by proving the Stochastic Gradient Descent (SGD) case of Theorem 1.

heading: Proof
text: We prove the Theorem 1 by induction.
Our induction hypothesis Hτ is the following : Hτ : For all k ≤ τ , Theorem 1 holds.
First, we prove thatH1 holds.
The proof is straightforward. For the first task, since there were no previous tasks, OGD on this task is the same as SGD.
Therefore, it is equivalent to minimising the following objective :
arg min w∈Rd ∥∥f0(X1) + φ(X1)T (w −w?0)− y1∥∥22 + λ2 ‖w −w?0‖2 (1) where φ(x) = ∇w?0f ? 0 (x).
We replace into the objective with ỹ1 applying ỹ1 = y1 − f0(X1) :
arg min w∈Rd ∥∥φ(X1)T (w −w?0)− ỹ1∥∥22 + λ2 ‖w −w?0‖2 (2) The objective is quadratic and the Hessian is positive definite, therefore the minimum exists and is unique :
w?1 −w?0 = φ(X1)(φ(X1)Tφ(X1) + λI)−1ỹ1 (3)
Under the NTK regime assumption :
f?1 (x) = f ? 0 (x) +∇wf?0 (x)T (w?1 −w?0) (4)
Then, by replacing into w?1 −w?0 :
f?1 (x) = f ? 0 (x) +∇wf?0 (x)Tφ(X1)(φ(X1)Tφ(X1) + λI)−1ỹ1 (5)
f?1 (x) = f ? 0 (x) + κ1(x,X1)(κ1(X1,X1) + λI) −1ỹ1 (6)
Finally :
f?1 (x)− f?0 (x) = κ1(x,X1)(κ1(X1,X1) + λI)−1ỹ1 (7)
Which completes the proof ofH1.
Let τ ∈ N?, we assume thatHτ is true, then we show thatHτ+1 is true.
On the task T τ+1, we can write the loss Lτ+1 as :
Lτ+1(w) = ∥∥φτ (Xτ+1)T (w −w?τ )− ỹτ+1∥∥22 + λ2 ‖w −w?τ‖2 (8)
We recall that the optimisation problem on the task T τ+1 is :
arg min w∈Rd ∥∥φτ (Xτ+1)T (w −w?τ )− ỹτ+1∥∥22 + λ2 ‖w −w?τ‖2 (9) The optimisation objective is quadratic, unconstrained, with a positive definite hessian. Therefore, an optimum exists and is unique :
w?τ+1 −w?τ = φ(Xτ+1)(φ(Xτ+1)Tφ(Xτ+1) + λI)−1ỹτ+1 (10)
We define the kernel κτ+1 : Rd × Rd → R as :
κτ+1(x,x ′) = φτ (x) Tφτ (x ′) for all x,x′ ∈ Rd (11)
Finally, we recover a closed form expression for f?τ+1 :
First, we use the induction hypothesisHτ :
f?τ+1(x) = f ? τ (x) + 〈∇wf?τ (x),w?τ+1 −w?τ 〉 (12)
= f?τ (x) + φτ (x)φ(Xτ+1)(κτ+1(Xτ+1,Xτ+1) + λI) −1ỹτ+1 (13) = f?τ (x) + κτ+1(x,Xτ+1)(κτ+1(Xτ+1,Xτ+1) + λI) −1ỹτ+1 (14)
At this stage, we have provenHt+1.
(15)
Orthogonal Gradient Descent Now, we prove the Orthogonal Gradient Descent (OGD) case of Theorem 1. The key difference in the proof is that the OGD optimisation objective is constrained. The constraints correspond to the orthogonality to the subspace spanned by the memorised feature maps from the previous tasks. Another key difference occurs during the regularisation, as opposed to the SGD case where the regularisation of the weights spans on the whole space, the regularisation of OGD only applies to the “learnable” space. This property follows from the orthogonality constraint, which enforces that the space spanned by the previous tasks is unchanged.

heading: Proof
text: We prove the Theorem 1 by induction. Our induction hypothesisHτ is the following : Hτ : For all k ≤ τ , Theorem 1 holds.
First, we prove thatH1 holds.
The proof is straightforward. For the first task, since there were no previous tasks, OGD on this task is the same as SGD.
Therefore, it is equivalent to minimising the following objective :
arg min w∈Rd ∥∥f0(X1)φ(X1)T (w −w?0)− y1∥∥22 + λ2 ‖w −w?0‖2 (16) We replace into the objective by the residual term ỹ1 = y1 − f0(X1)
arg min w∈Rd ∥∥φ(X1)T (w −w?0)− ỹ1∥∥22 + λ2 ‖w −w0‖2 (17) where φ(x) = ∇w?0f ? 0 (x).
The objective is quadratic and its Hessian is positive definite, therefore the minimum exists and is unique :
w?1 −w?0 = φ(X1)(φ(X1)Tφ(X1) + λI)−1ỹ1 (18)
Under the NTK regime assumption :
f?1 (x) = f ? 0 (x) +∇wf?0 (x)T (w?1 −w?0) (19)
Then, by replacing into w?1 −w?0 :
f?1 (x) = f ? 0 (x) +∇wf?0 (x)Tφ(X1)(φ(X1)Tφ(X1) + λI)−1ỹ1 (20)
f?1 (x) = f ? 0 (x) + κ1(x,X1)(κ1(X1,X1) + λI) −1ỹ1 (21)
Finally :
f?1 (x)− f?0 (x) = κ1(x,X1)(κ1(X1,X1) + λI)−1ỹ1 (22)
Which completes the proof ofH1. Let τ ∈ N?, we assume thatHτ is true, then we show thatHτ+1 is true. On the task T τ+1, we can write the loss Lτ+1 as :
Lτ+1(w) = ∥∥φτ (Xτ+1)T (w −w?τ )− ỹτ+1∥∥22 + λ2 ‖w −w?τ‖2 (23)
We recall that the optimisation problem on the task T τ+1 is :
arg min w∈Rd ∥∥φτ (Xτ+1)T (w −w?τ )− ỹτ+1∥∥22 + λ2 ‖w −w?τ‖2 (24) u.c. Vτ+1(w −w?τ ) = 0 (25)
where Vτ+1 is a projection matrix on ( τ⊕ k=1 Ek)⊥, the Euclidean space induced by the feature maps of the tasks {T k, k ∈ [τ ]}. Let Tτ+1 ∈ Rd×(d−Kτ+1) and w̃ ∈ Rd−Kτ+1 such as :
w −w?τ = Tτ+1w̃ (26)
Kτ = dim( τ⊕ k=1 Ek) (27)
We rewrite the objective by plugging in the variables we just defined. The two objectives are equivalent :
arg min w̃∈Rd−Kτ+1 ∥∥φτ (Xτ+1)TTτ+1w̃ − ỹτ+1∥∥22 + λ2 ‖Tτ+1w̃‖2 (28) This objective is equivalent to :
arg min w̃∈Rd−Kτ+1 ∥∥φτ (Xτ+1)TTτ+1w̃ − ỹτ+1∥∥22 + λ2 ‖w̃‖2 (29) For clarity, we define Zτ+1Rnτ+1×(d−Kτ+1) as :
Zτ+1 = φτ (Xτ+1) TTτ+1 (30)
By plugging in Zτ+1, we rewrite the objective as :
arg min w̃∈Rd−Kτ+1 ∥∥Zτ+1w̃ − ỹτ+1∥∥22 + λ2 ‖Tτ+1w̃‖2 (31) The optimisation objective is quadratic, unconstrained, with a positive definite hessian. Therefore, an optimum exists and is unique :
w̃?τ+1 = Z T τ+1(Zτ+1Z T τ+1 + λI) −1ỹτ+1 (32) We recover the expression of the optimum in the original space :
w?τ+1 −w?τ = Tτ+1Z T τ+1(Zτ+1Z T τ+1 + λI) −1ỹτ+1 (33)
We define the kernel κτ+1 : Rd × Rd → R as : κτ+1(x,x ′) = φτ (x) TTτ+1T T τ+1φτ (x
′) for all x,x′ ∈ Rd (34) Now we rewrite w?τ+1 −w?τ :
w?τ+1 −w?τ = Tτ+1Z T τ+1(κτ+1(Xτ+1,Xτ+1) + λI) −1ỹτ+1 (35) Finally, we recover a closed form expression for f?τ+1 : First, we use the induction hypothesisHτ :
f?τ+1(x) = f ? τ (x) + 〈∇wf?τ (x),w?τ+1 −w?τ 〉 (36)
= f?τ (x) + φτ (x)Tτ+1Z T τ+1(κτ+1(Xτ+1,Xτ+1) + λI) −1ỹτ+1 (37) = f?τ (x) + κτ+1(x,Xτ+1)(κτ+1(Xτ+1,Xτ+1) + λI) −1ỹτ+1 (38)
At this stage, we have provenHt+1. We conclude the proof of Thm. 1.
(39)

heading: C.2 PROOF OF THE COROLLARY 1
text: Stochastic Gradient Descent The proof follows immediately from Thm. 1.

heading: Proof
text: In the proof of Theorem 1 (App. C.1), for the SGD case, we showed that :
w?τ+1 −w?τ = φ(Xτ+1)(φ(Xτ+1)Tφ(Xτ+1) + λI)−1ỹτ+1 (40)
This result implies that :∥∥w?τ+1 −w?τ∥∥2 = ỹTτ+1(φ(Xτ+1)Tφ(Xτ+1) + λI)φ(Xτ+1)Tφ(Xτ+1)(φ(Xτ+1)Tφ(Xτ+1) + λI)−1ỹτ+1 (41)
= ỹTτ+1(κ(Xτ+1,Xτ+1) + λI) −1κ(Xτ+1,Xτ+1)(κ(Xτ+1,Xτ+1) + λI) −1ỹτ+1 (42) (43)
Orthogonal Gradient Descent The proof is exactly the same as the proof above, the difference lies in the kernel definition, which is implicit.

heading: Proof
text: In the proof of Theorem 1 (App. C.1), for the OGD case, we showed that :
w?τ+1 −w?τ = Tτ+1Z T τ+1(κτ+1(Xτ+1,Xτ+1) + λI) −1ỹτ+1 (44)
This result implies that :∥∥w?τ+1 −w?τ∥∥2 = ỹTτ+1(κτ+1(Xτ+1,Xτ+1) + λI)−1Zτ+1TTτ+1Tτ+1ZTτ+1(κτ+1(Xτ+1,Xτ+1) + λI)−1ỹτ+1 (45)
= ỹTτ+1(κτ+1(Xτ+1,Xτ+1) + λI) −1κτ+1(Xτ+1,Xτ+1)(κτ+1(Xτ+1,Xτ+1) + λI) −1ỹτ+1 (46) (47)

heading: D MISSING PROOFS OF SECTION 5 - GENERALISATION

heading: D.1 PROOF OF THEOREM 2
text: The intuition behind the proof is : since the gradient updates were performed orthogonally to the feature maps of the training data of the source task, the parameters in this space are unchanged, while the remaining space, which was changed, is orthogonal to these features maps, therefore, the inference is the same and the training error remains the same as at the end of training on the source task.

heading: Proof
text: In the proof of Theorem 1, App. C.1, we showed that, for T τ a fixed task:
f?τ+1(x) = f ? τ (x) + 〈∇wf?τ (x),w?τ+1 −w?τ 〉. (48)
We rewrite the recursive relation into a sum: f?τ+1(x)− f?0 (x) = τ∑ k=1 〈∇wf?k (x),w?k+1 −w?k〉. (49)
We observe that, for all k ∈ [T ]: w?k+1 −w?k ∈ Ek′ . (50) On the other hand, for OGD+, given a sample x from Dτ , for all k′ ∈ [τ + 1, T ] : ∇wf?k (x) ∈ Ek′ (51) Therefore, for all k′ ∈ [k + 1, τ ] : 〈∇wf?k′(x),w?k′+1 −w?k′〉 = 0 (52)
Therefore : f?τ (x) = f ? k (x) (53)
We conclude. (54)

heading: D.2 PROOF OF THEOREM 3

heading: D.2.1 REMINDERS

heading: Reminder on RKHS norm
text: Let κ a kernel, andH the reproducing kernel Hilbert space (RKHS) corresponding to the kernel κ. Recall that the RKHS norm of a function f(x) = αTκ(x,X) is :
‖f‖H = √ αTκ(X,X)α (55)
(56)
Reminder on Generalization and Rademacher Complexity Consider a loss function l : R × R → R. The population loss over the distribution D, and the empirical loss over n samples D = {(xi, yi), i ∈ [n]} from the same distribution D are defined as :
LD(f) = E(x,y)∼D[l(f(x), y)] (57)
LS(f) = 1
n n∑ i=1 l(f(xi), yi) (58)
Theorem 4 Suppose the loss function is bounded in [0, c] and is ρ−Lipschitz in the first argument. Then, with probability at least 1− δ over sample S of size n :
sup f∈F {LD(f)− LS(f)} ≤ 2ρR̂(F) + 3c
√ log(2/δ)
2n (59)
D.2.2 BOUNDING ∥∥∥f̃?τ∥∥∥Hτ :
Lemma 2 LetHτ the Hilbert space associated to the kernel κτ .
We recall that :
f̃ ?
τ (x) = κτ (x,Xτ ) Tατ (60)
ατ = (κτ (Xτ ,Xτ ) + λI) −1ỹτ (61)
Then :∥∥∥f̃?τ∥∥∥2Hτ ≤ ỹTτ (κτ (Xτ ,Xτ ) + λI)−1ỹτ (62) (63)

heading: Proof
text: We start from the definition of the RKHS norm of f̃ ?
τ :∥∥∥f̃?τ∥∥∥2Hτ = αTτ κτ (Xτ ,Xτ )ατ (64) = ỹTτ (κτ (Xτ ,Xτ ) + λI) −1κτ (Xτ ,Xτ )(κτ (Xτ ,Xτ ) + λI) −1ỹτ (65)
Since (κτ (Xτ ,Xτ ) + λI)−1 ≤ (κτ (Xτ ,Xτ ))−1
≤ ỹTτ (κτ (Xτ ,Xτ ) + λI)−1κτ (Xτ ,Xτ )κτ (Xτ ,Xτ )−1ỹτ (66) ≤ ỹTτ (κτ (Xτ ,Xτ ) + λI)−1ỹτ (67)

heading: D.2.3 BOUNDING THE RADEMACHER COMPLEXITY
text: The goal of this section is to upper bound the Rademacher Complexity. First, we derive a general upper bound for the Rademacher Complexity of a linear combination of kernels in Lemma 3 . Then, we apply this bound to the linear combination of kernels obtained through Thm. 1, which describes the model through the Continual Learning.

heading: A general bound for the Rademacher Complexity
text: Lemma 3 (Rademacher Complexity of a linear combination of kernels) Let κt : X × X → R, t ∈ [T ] kernels such that :
sup x∈X
‖κt(x,x)‖ <∞
To every kernel κt, we associate a feature map φt : X → Ht, whereHt is a Hilbert space with inner product 〈·, ·〉Ht , and for all x,x
′ ∈ X , κt(x,x′) = 〈φt(x), φt(x′)〉Ht For all T ∈ N?, given a sequence {Bτ , τ ∈ [T ]} we define FT as follows :
FT = {x→ T∑ t=1 ft(x), ft(x) = α T t κt(x,Xt) ∀t ∈ [T ], ‖ft‖Ht ≤ Bt} (68)
Let X1, ·, Xn be random elements of X . Then for the class F , we have :
R̂(F) ≤ T∑ t=1 2Bt nt (Tr(κt(Xt,Xt))) 1/2
Proof
Let f ∈ F , and let x ∈ X :
f(x) = T∑ τ=1 nτ∑ i=1 ατi κτ (x,x τ i ) (69)
For all τ ∈ [T ], we associate a feature map φτ : X→ Hτ ∀x,x′ ∈ X κτ (x,x′) = 〈φτ (x), φτ (x′)〉Hτ (70)
Therefore :
f(x) = T∑ t=1 nτ∑ i=1 ατi 〈φτ (xτi ), φτ (x)〉Hτ (71)
= T∑ τ=1 〈 nτ∑ i=1 ατi φτ (x τ i ), φτ (x)〉Hτ (72)
On the other hand, the following holds ∀t ∈ [T ] :∥∥∥∥∥ nτ∑ i=1 ατi φτ (x τ i ) ∥∥∥∥∥ 2 Hτ = ∑ i,j ατi α τ jκτ (x τ i ,x τ j ) ≤ B2τ (73)
Therefore :
FT ⊂ {x→ T∑ t=1 〈wτ , φτ (x)〉Hτ , ‖wτ‖2 ≤ Bτ ∀t ∈ [T ]} := F̃T (74)
Now, we derive an upper bound of the Rademacher complexity of FT :
R̂(FT ) ≤ R̂(F̃T ) (75)
= E[ sup ‖wτ‖2≤Bτ ,t∈[T ] T∑ t=1 〈wτ , 2 nτ nτ∑ i=1 iφτ (x τ i )〉Hτ |(Xτ )] (76)
= T∑ t=1 E[ sup ‖wτ‖2≤Bτ 〈wτ , 2 nτ nτ∑ i=1 iφτ (x τ i )〉Hτ |(Xτ )] (77)
Now we apply on each function fτ the upper bound from Lemma 22 by Bartlett & Mendelson 2003
R̂(FT ) ≤ T∑ t=1 2Bτ nτ (Tr(κτ (Xτ ,Xτ ))) 1/2 (78)
(79)

heading: Bounding the Rademacher Complexity for Continual Learning
text: Lemma 4 Keeping the same notations and setting as Theorem 3, the Rademacher Complexity can be bounded as follows:
R̂(FT ) ≤ T∑ τ=1 O √ ỹTτ (κτ (Xτ ,Xτ ) + λI)−1ỹτ nτ  , (80) where FT is the function class spanned by the model up to the task T τ .
(81)

heading: Proof
text: For all T ∈ N?, given a sequence {Bτ , τ ∈ [T ]} we define FT as follows :
FT = {x→ T∑ τ=1 fτ (x), fτ (x) = α T τ κτ (x,Xτ ) ∀τ ∈ [T ], ‖fτ‖Hτ ≤ Bτ} (82)
where we set Bτ as : Bτ = √ (yτ − yτ−1→τ )T (κτ (Xτ ,Xτ ) + λI)−1(yτ − yτ−1→τ ) (83)
Following Lemma 2 for all τ ∈ [T ] : f?τ ∈ FT (84)
which means that the function class F t contains the Continual Learning model up to task T τ . We apply Lemma 3 in order to upper bound the Rademacher complexity :
R̂(FT ) ≤ T∑ τ=1 2Bτ nτ (Tr(κτ (Xτ ,Xτ ))) 1/2 (85)
We made the assumption that for all τ ∈ [T ] tr(κτ (Xτ ,Xτ )) = O(nτ ) :
R̂(FT ) ≤ T∑ τ=1 2Bτ nτ O( √ nτ ) (86)
≤ T∑ τ=1 O( Bτ√ nτ ) (87) ≤ T∑ τ=1 O √ (yτ − yτ−1→τ )T (κτ (Xτ ,Xτ ) + λI)−1(yτ − yτ−1→τ ) nτ
 (88) (89)

heading: D.2.4 BOUNDING THE EMPIRICAL LOSS FOR OGD
text: Lemma 5 Given a current task T T , the empirical losses on the data from all previous tasks (T τ , τ ≤ T ) can be bounded as follows :

heading: Let T ∈ N fixed. Then, for all τ ∈ [T ]
text: LSτ (f?T ) ≤ λ2
nτ ỹτ (κτ (Xτ ,Xτ ) + λI)
−1ỹτ (90)
(91)
Case 1 -Task T T Proof We start from the definition of the empirical loss :
LST (f?T ) = 1
nT nT∑ i=1 (f?T (xT,i)− yT,i)2 (92)
= 1
nT ‖f?T (XT )− yT ‖ 2 2 (93)
We replace into f?T by its expression from Theorem 1 :
= 1
nT
∥∥∥f̃?T (XT ) + f?T−1(XT )− yT∥∥∥2 2
(94)
= 1
nT ∥∥f?T−1(XT )− ỹT∥∥22 (95) = 1
nT ∥∥(kT (XT ,XT )T (κT (XT ,XT ) + λI)−1ỹT − ỹT∥∥22 (96) = 1
nT ∥∥(kT (XT ,XT ) + λI− λI)(κT (XT ,XT ) + λI)−1ỹT − ỹT∥∥22 (97) = 1
nT ∥∥ỹT − λ(κT (XT ,XT ) + λI)−1ỹT − ỹT∥∥22 (98) = λ2
nT
∥∥(κT (XT ,XT ) + λI)−1ỹT∥∥22 (99)
Now, we apply Lemma 2 in order to upper bound the right hand side norm :
LST (f?T ) ≤ λ2
nT ỹT (κT (XT ,XT ) + λI)
−1ỹT (100)
(101)
Case 2 - Tasks {T τ , τ ∈ [1, T − 1]} : The proof is very similar to Case 1, we apply Theorem 2, which is the key property of OGD in terms of no forgetting.

heading: Proof
text: We start from the definition of the empirical loss :
LSτ (f?T ) = 1
nτ nτ∑ i=1 (f?T (xτ,i)− yτ,i)2 (102)
= 1
nτ ‖f?T (Xτ )− yτ‖ 2 2 (103)
Now, applying Theorem 2 which implies that f?τ (Xτ ) = f ? T (Xτ ) :
LSτ (f?T ) = 1
nτ ‖f?τ (Xτ )− yτ‖ 2 2 (104)
Then with a similar analysis as Case 1, we get :
LSτ (f?T ) ≤ λ2
nτ ỹτ (kT (Xτ ,Xτ ) + λI)
−1ỹτ (105)
(106)

heading: D.2.5 BOUNDING THE EMPIRICAL LOSS FOR SGD
text: As opposed to the analysis for OGD, forgetting can occur for OGD and Theorem 2 is no longer valid. Similarly to the OGD empirical loss analysis, we study the case on the data from the last task and the case on the data from all the other tasks.
Lemma 6 The empirical losses on the source and target tasks can be bounded as follows :

heading: Let T ∈ N fixed. Then, for all τ ∈ [T ]
text: LST (f?T ) ≤ λ2
nT ỹT (kT (XT ,XT ) + λI)
−1ỹT (107)
For all τ ∈ [T − 1]
LSτ (f?T ) ≤ 1
nτ (λ2ỹTτ (kτ (Xτ ,Xτ )) −1ỹτ (108)
+ T∑ k=τ+1 ỹTk (κk(Xk,Xk) + λI) −1κk(Xτ ,Xk)κk(Xτ ,Xk) T (κk(Xk,Xk) + λI) −1ỹk)
(109)
Case 1 -Task T T For this case, the analysis is the same as for OGD, as no forgetting occurs with respect to the data the model is being trained on.
Case 2 - Tasks {T τ , τ ∈ [1, T − 1]} : Since SGD is not guaranteed to be robust to Catastrophic Forgetting, this case comprises additional residual terms that correspond to forgetting.

heading: Proof
text: Let τ ∈ [T − 1].
From Corr. 1, we recall that :
f?T (x) = f ? τ (x) + T∑ k=τ+1 f̃ ? k(x) (110)
Then :
‖f?T (Xτ )− yτ‖ 2 2 = ∥∥∥∥∥f?τ (Xτ ) + T∑
k=τ+1
f̃ ?
k(Xτ )− yτ ∥∥∥∥∥ 2
2
(111)
≤ ‖f?τ (Xτ )− yτ‖ 2 2 + ∥∥∥∥∥ T∑
k=τ+1
f̃ ?
k(Xτ ) ∥∥∥∥∥ 2
2
(112)
≤ ‖f?τ (Xτ )− yτ‖ 2 2︸ ︷︷ ︸
A
+ T∑ k=τ+1 ∥∥∥f̃?k(Xτ )∥∥∥2 2︸ ︷︷ ︸
B
(113)
We can upper bound A similarly to the previous paragraphs :
‖f?τ (Xτ )− yτ‖ 2 2 ≤ λ 2ỹTτ (kτ (Xτ ,Xτ ) + λI) −1ỹτ (114)
Now, we upper bound B . Let k ∈ [τ + 1, T ] :∥∥∥f̃?k(Xτ )∥∥∥2 2 = ỹTk (κk(Xk,Xk) + λI) −1 κk(Xτ ,Xk)κk(Xτ ,Xk)
T︸ ︷︷ ︸ Similarity between the tasks T τ and T k (κk(Xk,Xk) + λI) −1ỹk
(115)
We conclude by plugging back the upper bounds of A and B
‖f?T (Xτ )− yτ‖ 2 2 ≤ λỹ T τ (kτ (Xτ ,Xτ )) −1ỹτ (116)
+ T∑ k=τ+1 ỹTk (κk(Xk,Xk) + λI) −1κk(Xτ ,Xk)κk(Xτ ,Xk) T (κk(Xk,Xk) + λI) −1ỹk
(117)
Therefore :
LSτ (f?T ) ≤ 1
nτ (λ2ỹTτ (kτ (Xτ ,Xτ )) −1ỹτ (118)
+ T∑ k=τ+1 ỹTk (κk(Xk,Xk) + λI) −1κk(Xτ ,Xk)κk(Xτ ,Xk) T (κk(Xk,Xk) + λI) −1ỹk)
(119)

heading: D.2.6 PROOF OF THE GENERALISATION THEOREM (THM. 3)
text: Now, we prove the Theorem 3 by applying the lemmas we developed above.
Proof
With probability 1− δ we have :
sup f∈FT
{LD(f)− LS(f)} ≤ 2ρR̂(FT ) + 3c
√ log(2/δ)
2nT (120)
LDτ (f?T ) ≤ LSτ (f?T ) + 2ρR̂(FT ) + 3c
√ log(2/δ)
2nT (121)
LDτ (f?T ) ≤ LSτ (f?T ) + T∑ k=1 O √ ỹTk (κk(Xk,Xk))−1ỹk nk + 3c√ log(2/δ) 2nT
(122)
Then, by replacing into LSτ (f?T ) with Lemmas 5 and 6, we get the upper bounds of the theorem for the various cases of SGD and OGD.
(123)

heading: D.2.7 ALTERNATIVE PROOF FOR THE EMPIRICAL LOSS BOUNDS - NO REGULARISATION CASE
text: This section is complementary and aims to provide a better interpretation of the bounds in Theorem 3.
We prove that in the case where there is no regularisation, the training error converges to zero. This result illustrates better the intuition behind the λ term that appears in the upper bound of the Theorem 3, which is under the regularisation assumption.
First, we derive the differential equation of the model’s output dynamics in Lemma 7. Then, we apply this Lemma to prove the convergence to zero in Lemma 8. Finally, in Lemma 9, we show that for the past tasks, the training error equals to zero all the time.

heading: The training dynamics of OGD
text: Lemma 7 (Differential equation of the model’s output dynamics) Let T ∈ N?, the index of the task currently being trained on, with OGD.

heading: For all τ < T , defining ũτ as :
text: ũτ (t) = f (t) τ (Xτ )− ∑ k<τ f̃ ? k(Xτ ) = φτ (Xτ ) T (wτ (t)−w?τ−1) (124)
The model’s output dynamics while training on the task T τ is as follows :
ũτ (t+ 1)− ũτ (t) = −ηκτ (Xτ ,Xτ )(ũτ (t)− ỹτ ). (125) (126)

heading: Proof
text: Let τ ∈ N?, we derive the dynamics while training on the task T τ , while training on this task.
First, we define : ≈ yτ = ỹτ + φτ (Xτ ) Tw?τ−1 (127)
We also define the projection matrix Pτ ∈ Rp×p as :
Pτ = T T τ Tτ (128)
The matrix Pτ performs the projection from the original weight space Rp to the trainable weight space during training on task T τ , which corresponds to ( τ⊕ k=1 Ek)⊥ .
Our starting point is the SGD update rule :
wτ (t+ 1) = wτ (t)− ηPτ+1∇wLτ (wτ (t)) (129) where :
Lτ (wτ (t)) = ∥∥φτ (Xτ )T (wτ (t)−w?τ−1)− ỹτ∥∥22 (130)
= ∥∥φτ (Xτ )Twτ (t)− (ỹτ + φτ (Xτ )Tw?τ−1)∥∥22 (131)
= ∥∥φτ (Xτ )Twτ (t)− ≈yτ∥∥22 (132)
Therefore, we get the following expression for the gradient of the loss :
∇wLτ (wτ (t)) = φτ (Xτ )(φτ (Xτ )Twτ (t)− ≈ yτ ) (133)
Then, the following holds :
(134)
ũτ (t+ 1)− ũτ (t) = φτ (Xτ )T (wτ (t+ 1)−wτ (t)) (135) = φτ (Xτ )
T (−ηPτ∇wL(wτ (t))) (136) = φτ (Xτ ) T (−ηPτφτ (Xτ )(φτ (Xτ )Twτ (t)− ≈ yτ )) (137)
= (φτ (Xτ )Tτ ) T (−ηTτφτ (Xτ )(φτ (Xτ )Twτ (t)− ≈ yτ )) (138) = −ηκτ (Xτ ,Xτ )(φτ (Xτ )Twτ (t)− ≈ yτ ) (139) = −ηκτ (Xτ ,Xτ )(ũτ (t)− ỹτ ) (140) = −ηκτ (Xτ ,Xτ )(ũτ (t)− ỹτ ) (141)
It follows that :
ũτ (t+ 1)− ỹτ = (I− ηκτ (Xτ ,Xτ ))(ũτ (t)− ỹτ ) (142) ũτ (t)− ỹτ = −(I− ηκτ (Xτ ,Xτ ))t(ũτ (0)− ỹτ ) (143)
(144)
The training error converges to zero
Lemma 8 For all tasks T τ , τ ∈ [T ], the training error Lτ (wτ (t)) converges to 0 when t tends to infinity .

heading: Proof
text: We start with the definition of the training error on task T : LS(f (t)τ ) = ∥∥∥f (t)τ (Xτ )− yτ∥∥∥2 (145)
= ‖ũτ (t)− ỹτ‖ 2 (146) = ∥∥(I − ηκτ (Xτ ,Xτ ))t(ũτ (0)− ỹτ )∥∥ (147)
Under the assumption that κτ (Xτ ,Xτ ) is positive definite, for η ≤ 1‖(κτ (Xτ ,Xτ ))‖ the eigenvalues become less than 1, therefore :
lim t→∞
LS(f (t)τ ) = 0 (148)
The training error on the past tasks is zero
Lemma 9 For all tasks T τ , τ ∈ [T ], the training error LSτ (f?T ) = 0.
Proof This lemma follow immediately from Lemma 8 which states that the training error converges to zero for OGD on all tasks and Theorem 2 which states that the training error on the past tasks is unchanged.

heading: E MISSING PROOFS OF APP A - THE IMPORTANCE OF THE NTK VARIATION FOR CONTINUAL LEARNING

heading: E.1 PROOF OF PROPOSITION 1 - OGD IMPLIES A-GEM-NT
text: We present the proof of Proposition 1, which relies mainly on Theorem 2 stating the robustness of OGD to Catastrophic Forgetting.

heading: Proof
text: Let T τ a task fixed, we recall that in the NTK regime, the model can be expressed as :
fw(x) = f ? τ−1(x) +∇f?0 (x)(w −w?τ−1) (149)
Given a task T k and its associated memoryMk, we recall that the loss can be expressed as : l(fw,Mk) = ∑
(x,y)∈Mk (f?τ−1(x) +∇f?0 (x)(w −w?τ−1)− y)2 (150)
Similarly to the A-GEM paper, we define the gradients vectors g and {gk, k ∈ [τ − 1]} as :
g = ∇wl(fw, Dτ ) (151) gk = ∇wl(fw,Mk) (152)
Now we extend the expressions :
gk = ∇wl(fw, Dτ ) (153) = ∇w ∑
(x,y)∈Mk (f?τ−1(x) +∇f?0 (x)(w −w?τ−1)− y)2 (154)
= ∑
(x,y)∈Mk (f?τ−1(x) +∇f?0 (x)(w −w?τ−1)− y)∇f?0 (x) (155)
For OGD, following Thm. 2 variant for finite memory : = ∑
(x,y)∈Mk (∇f?0 (x)(w −w?τ−1))∇f?0 (x) (156)
Finally, since the gradient updates are orthogonal toMk :
gk = 0 (157)
Therefore, for all k ∈ [τ − 1] :
gk · g = 0 (158)
We conclude, OGD implies learning with GEM and A-GEM with no Positive Backward Transfer.
(159)

heading: F EXPERIMENTS

heading: F.1 REPRODUCIBILITY

heading: F.1.1 ARCHITECTURES
text: Due to the memory limitations encountered while running OGD and OGD+ on the CIFAR100 and CUB200 dataset, we use smaller architectures which are different from Jung et al. (2020). For the MNIST benchmark, we keep the same architecture as Farajtabar et al. (2019).
MNIST : Similarly to Farajtabar et al. (2019), the neural network is a three-layer MLP with 100 hidden units in two layers, each layer uses RELU activation function. The model has 10 logits, which do not use any activation function.
CIFAR100 : The neural network is a multi-head LeNet Lecun et al. (1998) network with Batch Normalisation Ioffe & Szegedy (2015) and 200 hidden units for the penultimate layer.
CUB200 : Similarly to Jung et al. (2020), our base architecture is AlexNet (Krizhevsky et al., 2012). In order to scale for the OGD type algorithms, we changed the classifier module to a smaller 3 layer RELU neural network, with dropout (Table 5).

heading: Layer

heading: F.1.2 EXPERIMENT SETUP
text: We run each experiment 5 times, the seeds set is the same across all experiments sets. We report the mean and standard deviation of the measurements.

heading: F.1.3 OGD+ IMPLEMENTATION DETAILS
text: Memory : During the OGD+ memory update step, for each task, the new associated feature maps replace the memory slots of the previous feature maps for the same task. The goal is to ensure a balance of the feature maps from all tasks in the memory.
Multi-head models : For the dataset streams Split MNIST and Split CIFAR-100, we consider multi-headed neural networks. We only store the feature maps with respect to the shared weights, the projection step is not performed for the heads’ weights.

heading: F.1.4 HYPERPARAMETERS
text: We use the the same hyperparameters as Farajtabar et al. (2019) for the algorithms SGD, OGD and OGD+, on the MNIST benchmarks. We also keep a small learning rate, in order to preserve the locality assumption of OGD, and in order to verify the conditions of the theorems. We report the shared hyperparameters across the benchmarks and algorithms in Table 6.
For the other benchmarks and algorithms, we report the grid search space in Sec. F.1.5.

heading: F.1.5 HYPERPARAMETER SEARCH
text: We present our hyperparameter search ranges for each Continual Learning method. We selected the hyperparameter sets that maximise the average accuracy. The results and scripts of the hyperparameter search and the best hyperparameters are provided on the corresponding github repository.
Hyperparameter MNIST CIFAR-100 CUB-200 Epochs 5 50 75
Architecture MLP LeNet AlexNet (variant) Hidden dimension 100 200 256
Torch seeds 1 to 5 Memory size per task 100
Activation RELU

heading: CIFAR100 and CUB200 Benchmarks

heading: MNIST Benchmarks

heading: F.2 EXPERIMENTS : MEMORISATION PROPERTY OF OGD (THM. 2)

heading: F.2.1 THE IMPORTANCE OF THE OVERPARAMETERIZATION ASSUMPTION
text: Thm. 2 states that in the NTK regime, given an infinite memory, the train error of OGD is unchanged.
Experiments We track the variation of the train accuracy of the samples in the memory through tasks after being trained on all subsequent tasks. We consider the MLP hidden layer size as a proxy for overparameterization. We run the experiments on the Permuted MNIST and Rotated MNIST benchmarks, with the OGD algorithm. We vary the hidden size from 100 to 400.
Results Figure 3 shows that the variation of the train accuracy of OGD+ decreases uniformly with the hidden size. This result indicates the forgetting of OGD decreases with overparameterization.

heading: F.2.2 THE IMPORTANCE OF THE MEMORY SIZE ASSUMPTION
text: Thm. 2 states that in the NTK regime, given an infinite memory, the train error of OGD is unchanged.
Experiments We track the variation of the train accuracy of the samples in the memory through tasks after being trained on all subsequent tasks, as a function of the memory size per task.
Results Figure 4 shows that the mean train accuracy variation decreases uniformly with the memory size.

heading: F.3 THE IMPORTANCE OF THE NTK VARIATION FOR CONTINUAL LEARNING (SEC. 6)
text: In this section, we present extended results on the importance of the NTK variation for Continual Learning. For completion, we present the variation of the test accuracy of the model at the end of training for all tasks. Also, we run the benchmarks on the A-GEM algorithm as a supporting materials for the discussion in App. A.
F.3.1 PERMUTED MNIST
F.3.2 ROTATED MNIST

heading: F.4 COMPARISON WITH OTHER CONTINUAL LEARNING BASELINES
text: In order to get a broader picture on the robustness of OGD+ to Catastrophic Forgetting, we benchmark it against standard Continual Learning baselines.

heading: F.4.1 EVALUATION
text: Denoting aT,τ the accuracy of the model on the task T τ after being trained on the task T T , and b̄ the vector of test accuracies at initialisation, we track the following metrics presented by Chaudhry et al. (2019) and Lopez-Paz & Ranzato (2017) :
Average Accuracy : ACC = 1
T T∑ τ=1 aT,τ (160)
Backward Transfer : BWT = 1
T − 1 T∑ τ=1 aT,τ − aτ,τ (161)
Forward Transfer : FWT = 1
T − 1 T∑ τ=1 aτ−1,τ − b̄τ (162)
Average Forgetting : AFM = 1
T − 1 T−1∑ τ=1 max t∈{1,...,T−1} (at,τ − aT,τ ) (163)

heading: F.5 BASELINES
text: In addition to the standard baselines, SGD, EWC, SI and MAS, we compare OGD+ against OGD and Stable SGD, which was recently introduced by Mirzadeh et al. (2020). They show that Stable SGD outperforms OGD on all benchmarks, in order for the evaluation to be as fair and comprehensive as possible, we also include this method in our benchmarks.

heading: F.5.1 COMPLEMENTARY RESULTS - CONTINUAL LEARNING METRICS
text: Permuted MNIST Table 9 shows that OGD+ outperforms the baselines on AAC, while it remains competitive on AFM and BWT.
Rotated MNIST Table 10 shows that OGD+ is competitive with the baselines on AAC and AFM, while it underperforms on the other metrics. Also it draws an improvement over OGD on AAC, BWT and AFM. One probable reason is the relatively low overparameterization of the setting as shown in Table 1.
Split CIFAR100 Table 11 shows that OGD+ is not competitive on Split CIFAR100 on all metrics. Also it draws the same performance as OGD on all metrics, one probable reason is the overparameterization of the setting as shown in Table 1.
CUB200 Table 12 shows that OGD+ is not competitive on the CUB200 benchmark on all metrics. Also it draws the same performance as OGD on all metrics, one probable reason is the overparameterization of the setting as shown in Table 1.

heading: F.5.2 COMPLEMENTARY RESULTS - VALIDATION ACCURACY THROUGH TRAINING

Review summaries:
The authors use a Neural Tangent Kernel (NTK) approximation of wide neural nets to establish generalization bounds for continual learning (CL) using stochastic gradient descent (SGD) and orthogonal gradient descent (OGD).  In this regime, the authors prove that OGD does not suffer from catastrophic forgetting of training data.  The authors additionally introduce a modification to OGD which causes significant performance improvements in the Rotated MNIST and Permuted MNIST problems.  OGD involves storing feature maps from data points from previous tasks.  The modified OGD method (OGD+) additionally stores feature maps from the current task.  

The paper provides a theoretical analysis on the OGD based continual learning method. The method is in fact proposed by a previous paper (Farajtabar et al. 2019) and the current paper shows a generalization bound for the regression case. The result (Thm 3) compares the generalization bounds between SGD and OGD and shows OGD leads to a tighter bound. The theorem is also based on the bound on the Rademacher Complexity (Lemma 1).  The paper also suggests OGD+, which stores some data points from past tasks. They also present some experimental results on small benchmark datasets, and show OGD+ outperforms SGD and OGD.