Generalisation Guarantees For Continual Learning With Orthogonal Gradient Descent
Authors: Mehdi Abbana Bennani
Thang Doan
Masashi Sugiyama
Venue:  (2021)
Keywords: Continual Learning
Neural Tangent Kernel
Optimisation

Abstract: In Continual Learning settings, deep neural networks are prone to Catastrophic Forgetting. Orthogonal Gradient Descent (Farajtabar et al., 2019) 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 NTK 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 NTK variation for Continual Learning.

Under review as a conference paper at ICLR 2021
GENERALISATION GUARANTEES FOR CONTINUAL LEARNING WITH ORTHOGONAL GRADIENT DESCENT
Anonymous authors
Paper under double-blind review
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.
INTRODUCTION
Continual Learning is setting in which agent is exposed multiples tasks sequentially (Kirk- patrick 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 al. (018)) 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 large literature on Continual Learning (Parisi et al. 2019 few works have addressed the problem from a theoretical perspective. Recently, Jacot et al. (018) 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, network evolves as 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 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 al. 2019).
Our contributions are summarized as follows:
1. We present a theoretical framework study Continual Learning algorithms in the Neural Tangent Kernel (NTK) regime. This framework frames Continual Learning as recur- sive kernel regression and comprises proxies for Transfer Learning, generalisation, tasks similarity and Curriculum Learning. (Thm. [ Lem. 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.
3. We prove the first generalisation bound for Continual Learning with SGD and OGD. We find that generalisation through tasks depends on 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

---

Under review as a conference paper at ICLR 2021
the robustness to Catastrophic Forgetting of OGD in non overparameterizeed benchmarks.
(Sec. 6
2 RELATED WORKS
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 & Roussel 1997
Ans & Roussel 2000 Goodfellow et al. 2014 French 1999, McCloskey & Cohen 1989 Robins 1995 | Nguyen et al. 2019). Approaches Continual Learning can be categorised into: regularization methods, memory based methods and dynamic architectural methods. We refer the reader to the survey by Parisi al. (019) for extensive overview 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 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 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 al. 2018 Farajtabar al. 2019 Zenke al. 2017).
While there is large literature on the field, there limited number of theoretical works on Continual Learning. Allquer et al. (2017) define 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 generalisation, when training with Stochastic Gradient Descent, in a two tasks setting and for over-paree wher-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.
PRELIMINARIES
Notation We use bold-faced characters for vectors and matrices. We use ||-|| denote the Euclidean norm of a vector or the spectral norm of a matrix, and || || to denote the Frobenius norm of matrix. We use (--) for the Euclidean dot product, and (.-) the dot product in the Hilbert space H. We index the task ID by 7. 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 N (0). We use ( to refer to the direct sum over Fuclidean spaces.
3.1 CONTINUAL LEARNING
Continual Learning considers a series of tasks T .2. where each task can be viewed separate supervised learning problem. Similarly to online learning, data from each task revealed only once. The goal of Continual Learning is to model each task accurately with 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 T E N is drawn from a distribution D,. Individual samples denoted (Xr,) Vr.i), where E [n.]. For given task T,, the model is denoted fr, the
2

---

Under review as a conference paper at ICLR 2021
superscript (t) to indicate the training iteration t N, while use the superseript indicate the asymptotic convergence. For the regression case, given ridge regularisation coefficient À E R*,, for all & N, we write the train loss for a task 7, as
L (T()((())
Σ
+ +AI++1l11 A|[w-(1) -v,;))
-w;-ll?
3.2 OGD FOR CONTINUAL LEARNING
Let Tr the current task, where E N For all [mr]]. let VT, V (xy-1,s). which the Jacobian of task Tr. We define E, vec( (v- i.,, [n+]]), the subspace induced by the Jacobian. The idea behind OGD (Farajtabar et al., (219)) is to update the weights along the projection of the gradient on the orthogonal space induced by the Jacobians over the previous tasks E₁ ... + E,
The update rule at an iteration E Nº for the task Tr is as follows:
(t + 1) (t) nu Vw (tr
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" (Farajtabari al. 2019). Throughout the paper, we only consider the OGD-GTL variant which stores the gradient with respect to the ground truth logit.
3.3 NEURAL TANGENT KERNEL
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. [ee al. (2019) also showed that 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:
(x) R (x) / (x) (w(1) w()).
4 CONVERGENCE: CONTINUAL LEARNING AS A RECURSIVE KERNEL. REGRESSION
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 that the NTK of OGD is recursive with respect to the projection of its feature map on the tasks' spaces. The result is presented Theorem stepping stone towards proving the generalisation bound for OGD in Sec.
4.1 CONVERGENCE THEOREM
Theorem (Continual Learning recursive Kernel Regression)
Given T T1,...,TT TT sequence tasks. Fix learning rate sequence (N+)ee(T) and ridge regulari- sation coefficient R If, for all r, the learning rate satisfies 1) Ix, then for all T, (t( converges linearly to limit solution w such that
fx) (x) ny (x, x-)² (mr (X, X. x1)
3

---

Under review as a conference paper at ICLR 2021
where
(x,xx x') (x)),(xx'²,
y, =y, - -
1-- 1x-1(X,),
(x) ( /w (x) Rd for SGD,
(T (x) Rd-M- for OGD.
and (T, E -R E [T]} are projection matrices from TR to + E&)² and M, = dim( + lRx)
k=1
k=1
The theorem describes how the model f; evolves across tasks. It is recursive because the learning incremental. For given task TT, Tr. - (x) is the knowledge acquired by the agent up to the task Tr-1- At this stage, the model only fits the residual y, Y, 7--1-r which complements the knowledge acquired through h previous tasks. This residual is also proxy for task similarity. If the tasks are identical, the residual equal zero. The knowledge increment is captured by the term: Kr (x, x (Nr+1 (X,, X,) + XI) y, Finally, the task similarity is computed with respect to the most recent feature map or, and K, is the NTK with respect to the feature map Φr.
Remark The recursive relation from Theorem 7 can also be written as a linear combination of kernel regressors as follows:
(x) Σ [x(x),
R=1
where
fx(x) = (x, Xx)' (ASK (Xi, Xx) + XI) AI)
4.2 DISTANCE FROM INITIALISATION THROUGH TASKS
As described in Sec. 4.1 y, is residual. It equal zero if the model f7-1 makes perfect predictions on the next fask 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 Corollary Trracks the distance from initialisation as function of task similarity.
[T]} are Corollary For SGD, and for OGD under the additional assumption that {Tr, orthonormal,
| w = (
+I) "( X1) X X,+1) AT) A 411
Remark 2 Corollary can be applied to get 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 2-layer neural networks with a RELU activation function, with probability no less than d over random initialisation,
(PPP-W(QN)) S H gr-Q
where, in their work:
vr-q= 11 HP Yp,
ÿ PP-Q =y YP-QQ
Note that H is 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 knowledge, since there are 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 X 0, and with the additional assumption of invertibility H. which is valid in the two-layer overparameterized RELU neural network considered in the setting Liu al. (2019)
recover similar approximation.
4

---

Under review as a conference paper at ICLR 2021
5 OGD: LEARNING WITHOUT FORGETTING, PROVABLY
In this section, we study the generalisation properties OGD building-up on Thm. 1 First, we prove that OGD is robust to catastrophic forgetting with respect to all previous tasks (Theorem 2p. Then, present the main generalisation theorem for OGD (Thm. B). The theorem provides several insights present how the Rademacher
on the relation between task similarity and generalisation. Finally, complexity relates to task similarity across a large number of tasks (Lemma[) [ 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.
5.1 MEMORISATION PROPERTY OF OGD
The key to obtaining tight generalisation bounds for OGD is Theorem 2
(No-forgeging Continual Learning with OGD) Given task T,, for all Xk,i E DK a sample from the training data of previous task T ko given that the Jacobian of Xk. belongs to OGD's memory. it holds that:
Theorem 2
1 = = (xE,).
As motivated by Farajtabar al. (2019), the orthogonality of the gradient updates aims 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.
5.2 GENERALISATION PROPERTIES OF SGD AND OGD
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 (T1,... 1.... T be a sequence of tasks. Let be (Di...., ;Dr the respective distributions Rd (1,,1. Let ((T,,, Vr. [m+], [T]] be i.id. samples from D.. [T). Denote X, = (Xr,l,..., X7,n, Y, (Jr.1..... Vr.,., ). Consider the kernel ridge regression solution Ji.
then, for any loss function f: R x R + [0, c) that is c-Lisschitz in the first argument, with probability at least 8.
AII -5, + Rr 3eV
log(2/6)
for OGD, E [1,7].
2nt
(
ne
X AI -yy, + RT 30V
log(2/8)
for SGD,
X X, A1)-13, + 1
k H
Rr + 30/ log(2/5) 2nr
for SGD, T < T.
n
RT
where
8, =r (xr((
T.
5- (6 (X,, X,) -1 [r((k (X,, Xx))
Rr Σ
n
Hk.r = 5I (Kw XK, Xx) + -1)-1 Xx, X, ki (X,, Xx) (X,, Xx) + AI) '5x-
Theorem shows that the generalisation bound for OGD 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
x y, (x, (X), + -y, this term is due the regularisation and describes that the ne empirical loss is not equal to zero due to the regularisation term. This term tends zero in case there no regularisation. For interpretation purposes, in App. [.2.7] we show that the empirical loss tends zero in the no-regularisation case.
5

---

Under review as a conference paper at ICLR 2021
Ry captures the impact of task similarity generalisation which we discuss in Sec. 5.3
Ek=r+1 Hg.r is residual term that appears for SGD only. It is due 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 al. (2019), Liu al. (2019)
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.
5.3 THE IMPACT OF TASK SIMILARITY ON GENERALISATION
Now, we state Lemmall I which tracks the Rademacher complexity through tasks.
Lemma Keeping the same notations and setting as Theorem be bounded follows:
the Rademacher Complexity can
R(FT) S $0 [ ( (X,, (xx
8f (X,, +1) A1)
n2
where Fr is the function class covered by the model to the task T
The right hand side term Ry in the upper bound of the generalisation theorem follows directly from Lemma []] and it draws complexity measure for Continual Learning. 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 and T as S = y (x, X-)+ XI) - This dissimilarity is a generalisation of the term that appears in the upper bound of Thm. 2 by Liu al. 2019 The knowledge from the previous tasks is encoded in the kernel Kiy, through the feature map d,. As an edge case, two successive tasks are identical, S,-1 = 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 the importance of learning with curriculum (Bengio et al. (200))). In the following, we present an edge case which provided an intuition how the bound captures the importance of the order. Consider two dissimilar tasks Tı and To- A sequence of tasks alternating between T, and 2 will lead to a large upper bound, as explained in the first paragraph, while a sequence of tasks concatenating two sequences of T, then T2 will lead to a lower upper bound.
THE IMPACT OF THE NTK VARIATION ON OGD
In the previous section, demonstrated that under the NTK regime and 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 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 the end of each task, as opposed to OGD.
Algorithm presents the OGD+ algorithm, we highlight the differences with OGD in red. The main difference that OGD+ stores the feature maps with respect to the samples from previous tasks, in addition to the feature maps with respect the samples from the current task, as opposed to OGD. This small change 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 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 the beginning of each task.
natbib

---

Under review as a conference paper at ICLR 2021
Algorithm 1: OGD+ for Continual Learning
Input :A task sequence T1. T2 2,.... learning rate 7)
1. Initialize SJ + 0 SD (: w + wo
2. for Task ID .......dd do
repeat
g f Stochastic Batch Gradient for 7 at w;
g g g Eves, (g)
w 7g
until convergence:
Sample S C S
for (x, y) E D and E [1,c] s.I. yk = do
(xx(x; w) Eves, projv(VS/(x;))) S, s
end
Sample D D Update Sp S UD end
EXPERIMENTS
We study the validity Theorem 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 weer-arammterizationn 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 oooooverparameteriieeddd benchmarks. Finally, we present broader picture of the performance of OGD+ against standard Continual Learning baselines (Sec. 7.3)
Benchmarks We use the standard henchmarks similarly to Goodfellow al, 2014) and Chaudhry al. (2019). Permuted MNIST (Goodfellow et al. (2014) consists of 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 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 of 100. In order assess the robustness 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. (020) which contains 200 classes, split into 10 tasks. This benchmark more overparameterized than the other benchmarks.
Evaluation Denoting ar,r the accuracy of the model on the task T, after being trained the task TT, we track two metrics introduced by Chaudhry et al. 2019) and Lopez-Paz & Ranzato (201))
AVERAGE ACCURACY (Ar) is the average accuracy after the model has been trained on the task TT:
T
AT
Σ OT
AVERAGE FORGETTING
(Fr) the average forgetting after the model has been trained on the task
TT:
FT T
max ve(.....T11)
(at,r - aT
se
7

---

Under review as a conference paper at ICLR 2021
OVER- PARAMETERIZATION of trainable parameters over the average number of samples per task (Arora et al. 2019)
We track over- wer-parrameterization of a given benchmark the number
Er R4
Architectures For the MNIST benchmarks, we use the same neural network architectures as Farajtabar et al. (2019). However, since the OGD algorithm doesn't 't scale to large neural networks due to memory limits, we considered smaller scale neural networks for the CIFAR100 and CUB200 benchmarks. For CIFAR 100, we the LeNet architecture (Lecun et al. 1998). For CUB200, keep the pretrained AlexNet similarly to Jung et al. (2020). then freeze the features layers and replace the default classifier with smaller neural network (App. F.I.I.
7.1 ABLATION STUDY FOR OGD, CATASTROPHIC FORGETTING DECREASES WITH OVERPARAMETERIIATOON (THM.P 2
Theorem 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 the model.
Experiment We train a model on the full task sequence on the MNIST and CIFARI00 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. P to these samples only.
Fixing the datasets sizes, our proxy for overparameterization 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 CIFARIOS benchmarks. This result concurs with Thm. 2
pl
-30
-20
253
CINANUO
Benchmakk
Figure 1: The variation of the train accuracy on the memorised samples from the first task as a function of overparameterization (higher is bet- ter). The forgetting decreases with overparame- terization, stated in Theorem
The variation of the train accuracy on the memorised samples from each task, after the model was trained on all tasks in sequence (higher is better). We vary the hidden size as proxy for overparameterization.
Figure 2:
7.2 ABLATION STUDY FOR NON OVER- PARAMETERIZED BENCHMARKS, UPDATING THE JACOBIAN IS CRITICAL TO OGD's ROBUSTNESS (THM. 2
Our analysis relies on the over-parametterizaton 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 measure this impact, perform ablation study OGD, taking into account the Jacobian's 's variation (OGD+) or not (OGD). OGD+ takes into account the Jacobian's 's variation by updating all the stored Jacobians 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, the MNIST, CIFAR 100 and CUB200 benchmarks.
8

---

Under review as a conference paper at ICLR 2021
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 CIFAR 110 and CUB200, the most wver-parameterize benchmark, the robustness of OGD and OGD+ is equivalent. For these henchmarks, 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 's variation in non-overparamettrized settings such as MNIST is an important reason the OGD algorithm is prone to Catastrophic For- getting. This result also highlights the importance of developing a theoretical framework for the non-overparameterizee setting, in order to capture the properties of OGD outside the NTK regime.
Dataset
Permuted MNIST
Rotated MNIST
Split CIFARI00
CUB200
Overparameterization
2
28
1166
OGD
99.71 (+0.95)
-1.777 (+0.35)
-20886 (#1.41)
12.99 (#0.92)
OGD+
-5.98 (+0.36)
-8.57 (+0.53)
-21.59 (+1.27)
-12.89 (=0.51)
Table 1: The average forgetting of with and without accounting for the Jacobian's variation, on the MNIST, CIFAR and CUB200 datasets (lower is better). A higher over-parameeterization coefficient implies that the constant Jacobian assumption is more likely to hold.
7.3 BENCHMARKING OGD+ AGAINST OTHER CONTINUAL LEARNING BASELINES
In order to provide broader picture on the robustness of OGD+ to Catastrophic Forgetting, we benchmark 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 competitive with other Continual Learning methods. On the most overparameterized benchmarks, CIFAR 100 and CUB200, OGD+ is not competitive.
Permuted MNIST
Rotated MNIST
Split CIFAR100
CUB200
Naive SGD
76.31 (+1.89)
71.06 (+0.41)
50.77 (#3.99)
53.93 (10.86)
EWC
80.85 (+1.14)
80.96 (+0.42)
56.82 (#1.75)
62.15 (10.37)
SI
86.69 (#0.4)
75.33 (+0.55)
66.66 (#2.07)
63.17 (+0.42)
MAS
85.96 (+0.72)
80.55 (#0.46)
66.33 (#1.13)
61.43 (+0.68)
Stable SGD
78.17 (#0.76)
88.92 (#0.19)
72.86 (#0.9)
58.79 (+0.36)
OGD
85.0 (#0.86)
79.17 (+0.33)
61.82 (+1.24)
57.89 (+0.89)
OGD+
88.65 (+0.38)
87.73 (+0.5)
61.11 (+1.31)
57.99 (+0.52)
Table 2: The average accuracy of several methods on the MNIST, CIFAR and CUB200 datasets.
8 CONCLUSION
We presented theoretical framework for Continual Learning algorithms in the NTK regime, then leveraged the framework 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 non- overparameterized settings. In order to gain 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 investigate these directions.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Alessandro Achille, Michael Lam, Rahul Tewari, Avinash Ravichandran, Subhransu Maji, Charless Fowlkes, Stefano Soatto, and Pietro Perona. Task2vec: Task embedding for meta-learning, 02 2019.
Rahaf Aljundi, Francesca Babiloni, Mohamed Elhoseiny, Marcus Rohrbach, and Tinne Tuytelaars. Memory aware synapses: Learning what (not) to forget. In ECCV, 2018.
Pierre Alquier, The Tien Mai, and Massimiliano Pontil. Regret Bounds for Lifelong Learning. In Aarti Singh and Jerry Zhu (eds.), Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pp. 261-269. Fort Lauderdale, FL, USA, 20-22 Apr 2017. PMLR.
Bernard Ans and Stéphane Rousset. Avoiding catastrophic forgetting by coupling two reverberating neural networks. Comptes Rendus de l'Académie des Sciences Series III Sciences la Vie, 320 (12):989 997, 1997.
Bernard Ans and Stéphane Rousset. Neural networks with a self-refreshing memory: Knowledge transfer in sequential learning tasks without catastrophic forgetting. Connection Science, 12:1-19, 04 2000. doi: 10. 08800954000001111177
Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. CoRR, abs/1901 088584, 2019.
Natalia D í az Rodr i guez, Vincenzo Lomonaco, David Filliat, and Davide Maltoni. Don't forget, there is more than forgetting: new metrics for continual learning. CoRR, abs/1810.13166 2018.
Peter L.. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. J. Mach. Learn. Res., 3:463-482. March 2003.
Shai Ben-David and Reba Schuller. Exploiting task relatedness for multiple task learning. In Bernhard Schölkopf and Manfred K. Warmuth (eds.), Learning Theory and Kernel Machines, pp. 567-580, Berlin, Heidelberg, 2003. Springer Berlin Heidelberg, ISBN 978-3-540-45167-9,
Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. Curriculum learning. In Proceedings of the 26th Annual International Conference on Machine Learning, ICML '09, pp. 41-48, New York, NY, USA, 2009. Association for Computing Machinery. ISBN 978160558116. doi: 10.1145/1553374.15553333
Frederik Benzing. Understanding regularisation methods for continual learning. ArXiv, abs/2006.06357, 2020.
Alberto Bietti and Julien Mairal. On the inductive bias of neural tangent kernels. In NeurlPS, 2019.
Arslan Chaudhry, Mare' Aurelio Ranzato, Marcus Rohrbach, and Mohamed Elhoseiny. Efficient lifelong learning with GEM. In International Conference Learning Representations, 2019.
Giulia Denevi, Carlo Ciliberto, Dimitris Stamos, and Massimiliano Pontil, Incremental learning-to- learn with statistical guarantees, 2018a.
Giulia Denevi, Carlo Ciliberto, Dimitris Stamos, and Massimiliano Pontil. Learning learn around common mean. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Biance and R. Garnett (eds.), Advances in Neural Information Processing Systems 31, pp. 10169-10179. Curran Associates, Inc., 2018b.
Lee H. Dicker, Dean P. Foster, and Daniel Hsu. Kernel ridge vs. principal component regression: Minimax bounds and the qualification of regularization operators. Electron. J. Statist,, 11(1): 1022-1047, 2017. doi: 10.1214/17-ESS1255
Simon S. Du, Xiyu Zhai, Barnab s P ó czos, and Aarti Singh. Gradient descent provably 2018.
optimizes over-parameterized neural networks. CoRR,
10

---

Under review as a conference paper at ICLR 2021
Simon Shaolei Du, Wei Hu, Sham M. Kakade, Jason D. Lee, and Qi Lei. Few-shot learning via learning the representation, provably. ArXiv, abs/2002.09434, 2020.
Sayna Ebrahimi, Mohamed Elhoseiny, Trevor Darrell, and Marcus Rohrbach. Sincertintt-guuide continual learning with bayesian neural networks. In International Conference Learning Representations, 2020.
Cong Fang, Hanze Dong. and Tong Zhang. Over parameterized two-level neural networks can learn near optimal feature representations, 2019.
Mchrdad Farajtabar, Navid Azizan, Alex Mott, and Ang Li. Orthogonal gradient descent for continual learning. ArXiv, 10.07104, 2019.
Robert French. Catastrophic forgetting in connectionist networks. Trends in cognitive sciences, 3: 128 128-13,,00 05 1999. doi: 10.1011/S 00666/13660 161446611319999192444
S. Goldt, M. M zard, F. Krzakala, and L.. Zdeborov Modelling the influence of data structure on learning in neural networks, 2020.
Sebastian Goldt, Madhu Advani, Andrew M Saxe, Florent Krzakala, and Lenka 7deborov' Dynamics of stochastic gradient descent for two-layer neural networks in the teacher-student setup. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché Buc. E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp. 6979-6999999 6989. Curran Associates, Inc., 2019.
Ian Goodfellow, Mehdi Mirza, Xia Da, Aaron C. Courville, and Yoshua Bengio. An empirical investigation catastrophic forgeting in gradient- neural networks. CoRR, abs/1312 111.6221,, 2014.
Soufiane Hayou, Arnaud Doucet, and Judith Rousseau. Mcan-field behaviour of neural tangent kernel for deep neural networks, 2019,
Wei Hu, Zhiyuan Li, and Dingli Yu. Simple and effective regularization methods for training on noisily labeled data with generalization guarantee, 2019.
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. CoRR, abs/1502.03167, 2015. URL http:://///xii// org/
abs/ /15//1502.. 03167
Arthur Jacot, Franck Gabriel, and Clé ment Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS' 18, pp. Associates Inc.
Red Hook, NY, USA, 2018. Curran
Kaiyi Ji, Junjie Yang, and Yingbin Liang. Multi-step model-agnostic meta-learning: Convergence and improved algorithms, 2020.
Sangwon Jung, Hongjoon Ahn, Sungmin Cha, and Taesup Moon. Continual learning with node-
importance based adaptive group sparse regularization, 2020.
James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Grabska- Barwinska, Demis Hassabis, Claudia Clopath, Dharshan Kumaran, and Raia Hadsell. Overcoming catastrophic forgetting in neural networks. Proceedings of the National Academy of Sciences, 1 114, 12 2016. doi: 10.10733pnas. 1611831114
James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei A. Demis Hassabis, Claudia Clopath, Dharshan Kumaran, and Raia Hadsell. Overcoming catastrophic forgetting in neural networks. Proceedings of the National Academy of Sciences, 114(13):3521-322 2017. doi: 10.1073/pnas.16 1eeei111111.6 18.51144.
Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka
Jeremias Knoblauch, H. Husain, and Tom Diethe. Optimal continual learning has perfect memory and is np-hard. ArXiv, abs/2006.05 188, 2020.
11

---

Under review as a conference paper at ICLR 2021
Alex Krizhevsky. Learning multiple layers of features from tiny images. 2009.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convo- lutional neural networks. In F. Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger (eds.), Advances in Neural Information Processing Systems, volume 25, pp. 1097-1105. Curran As- sociates, Inc., 2012. URL httpppppppppooceeeiigeeeoeeeee/e http://ooccccc............r.eeea nwwrips wwtp:/eweeer....cepeeeeeeeeeeeee httppppp....aappe////////LL
Yann Lecun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. In Proceedings of the IEEE, pp. 2278-2324, 1998.
Jachoon Lee, Lechao Xiao, Samuel S. Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve linear models under gradient descent, 2019.
Jeongtae Lee, Jachong Yoon, Eunho Yang, and Sung Ju Hwang. Lifelong learning with dynamically expandable networks. ArXiv, abs/1 708.01547, 2018.
Mingchen Li, Mahdi Soltanolkotabi, and Samet Oymak. Gradient descent with early stopping is provably robust to label noise for overparameterized neural networks. CoRR, abs/1903. 1680, 2019.
Hong Liu, Mingsheng Long, Jianmin Wang, and Michael I. Jordan. Towards understanding the transferability of deep representations, 2019.
David Lopez-Paz and Mare' Aurelio Ranzato. Gradient episodic memory for continuum learning. CoRR, 700.04006,,8800, 2017. URL http::://awww..r/////aaaaea 08844
Nicolas Masse, Gregory Grant, and David Freedman. Alleviating catastrophic forgetting using context-dependent gating and synaptic stabilization. Proceedings of the National Academy of Sciieces, 115, 02 2018. doi: 10.1073/pnas. 1803391115.
Michael McCloskey and Neal J. Cohen. Catastrophic interference in connectionist networks: The sequential learning problem. Psychology of Learning and Motivation, 24:109-165, 1989.
Seyed Iman Mirzadeh, Mchrdad Farajtabar, Razvan Pascanu, and Hassan Ghasemzadeh. Understand- ing the role of training regimes in continual learning, 2020.
Cuong V. Nguyen, Yingzhen Li, Thang D. Bui, and Richard E. Turner. Variational continual learning. In International Conference on Learning Representations, 2018.
Cuong V Nguyen, Alessandro Achille, Michael Lam, Tal Hassner, Vijay Mahadevan, and Stefano Soatto. Toward understanding catastrophic forgetting in continual learning. ArXiv, htts//908.00091,, 2019.
Pingbo Pan, Alexander Immer, Siddharth Swaroop, Runa Eschenhagen, Richard E Turner, and Mohammad Emtiyaz Khan. Continual deep learning by functional regularisation of memorable past, 2020.
German Parisi, Ronald Kemker, Jose L. Part, Christopher Kanan, and Stefan Wermter, Continual lifelong learning with neural networks: A review. Neural Networks, 11:554 -3:5--1,, 71, 2019.
Roger Ratcliff. Connectionist models of recognition memory: constraints imposed by learning and forgetting functions. Psychological review, 97 2:285-308 1990.
Hippolyt Ritter, Aleksandar Botev, and David Barber. Online structured laplace approximations for overcoming catastrophic forgetting. In Proceedings the 32nd International Conference Neural Information Processing Systems, NIPS'18 18, pp. 42222,2, Red Hook, NY, USA, 2018. Curran Associates Inc.
A. Robins. Catastrophic forgetting, rehearsal and pseudorehearsal. Connection Science, 7:123-, 01 1995.
Nikunj Saunshi, Yi Zhang, Mikhail Khodak, and Sanjeev Arora. A sample complexity separation between non-convex and convex meta-learning 2020.
12

---

Under review as a conference paper at ICLR 2021
Jonathan Schwarz, Jelena Luketina, Wojeiech Czarnecki, Agnieszka Grabska-Ban Barwinska, Yee Teh, Razvan Pascanu, and Raia Hadsell. Progress and compress: scalable framework for continual learning, 05 2018.
Joan Serra, Didac Suris, Marius Miron, and Alexandros Karatzoglou. Overcoming catastrophic forgetting with hard attention to the task. CoRR, abs//8001011 001423, 2018.
Alex J. Smola, Bernhard Schö Ikopf, and Klaus-Robert Mü ller. The connection between regu- larization operators and support vector kernels. Neural Netw, 11(4):637-66) June 1998. doi: (0.1016/00992--00099990003333330
Gido M Van de Ven and Andreas S Tolias. Generative replay with feedback connections general strategy for continual learning. arXiv preprint 1809. 2018.
Gido M Van de Ven and Andreas S Tolias. Three scenarios for continual learning. arXiv preprint arXiv:1904. 07734, 2019.
Ruosong Wang, Simon S. Du, Lin Yang, and Sham M. Kakade. long horizon reinforcement learning more difficult than short horizon reinforcement learning?, 2020.
Colin Wei, Jason D Lee, Qiang Liu, and Tengyu Ma. Regularization matters: Generalization and optimization of neural nets v.s. their induced kernel. H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alche Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp. 9709-9721. Curran Associates, Inc., 2019.
Tianhe Yu, Saurabh Kumar, Abhishek Gupta, Sergey Levine, Karol Hausman, and Chelsea Finn. Gradient surgery for multi-task learning, 2020.
Friedemann Zenke, Ben Poole, and Surya Ganguli. Continual learning through synaptic intelligence. In Proceedings of the 34th International Conference Machine Learning Volume 70, (CML'17, pp. 3987-3995, JMLR.org, 2017.
13

---

Under review as a conference paper at ICLR 2021
A COMPLEMENTARY DISCUSSION
A.1 NTK VARIATION THE IMPORTANCE OF ORTHOGONALITY FOR THE OGD, OGD+ AND A-GEM ALGORITHMM
In the main article, we focused only on the SGD, OGD and OGD+ algorithms. In this section, we highlight a connection of these algorithms 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 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 generali- sation 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 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 not protect all the subspaces, the subspace is updated as it is computed at each training step, the updates are therefore expected be more relevant. Finally OGD+ lies the intersection of both, while it doesn't I update the feature maps at each gradient step, the projection constraint is with respect larger space.
smaller subspace which may
Projection Space
Algorithm
Span
Update rate
Backward Transfer
SGD
None
None
No
OGD
Full
Task
Unclear
OGD+
Full
Task
Unclear
A-GEM
Sample
Gradient step
Yes
Table 3: Overview of the properties of the SGD, OGD, OGD+, A-GEM and A-GEM-NT algorithms.
On the theoretical connection between OGD and A-GEM The A-GEM algorithm (Chaudhry al. 2019) a state of the art Continual Learning algorithm on the standard benchmarks. The idea behind the algorithm to perform gradient descent if estimate of the loss over the previous tasks increases or is unchanged. Otherwise the gradient 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 terms generalisation error, stated in Proposition] T
Proposition 1 In the NTK regime, OGD implies A-GEM with Positive Backward Transfer.
The proof is presented in App. E.1
The extended experiments the importance of the NTK variation for Continual Learning (Sec. F33). 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+.
Experiments
14

---

Under review as a conference paper at ICLR 2021
A.2 EXPRESSIONS OVERVIEW
For convenience, we present in Table an overview of the notions that were mentioned in the main article, with their respective mathematical expressions.
Name
Expression
Residual
y, 1--1
Knowledge increment
(x)x) = Ke (x, X,) (X,, + +1I)
Projection matrix
T
Feature map
o(x)
Effective feature map
(x)
Effective kernel
xx(xxx))
Σ/= tx(ner X, X 8 (Nir (X,, X,) AI)-
Complexity measure
NTK task dissimilarity
1 y (Nrr (X X,) AI)
Table 4: Overview of the notions presented in the main manuscript with their respective notations.
15

---

Under review as a conference paper at ICLR 2021
B PROOFS OVERVIEW
B.1 CONVERGENCE:
Theorem : Convergence of SGD and OGD for Continual Learning We prove Theorem by induction. We rewrite the loss function as regression on the residual y, instead of y, Then, we rewrite the optimisation objective as unconstrained strongly convex optimisation problem. Finally, we compute the unique solution in closed form. The full proof is presented in App. C.I
Continual Learning as recursive Kernel Regression from the recursive form of Theorem
Remark :
The remark follows directly
Corollary Distance from initialisation through tasks The proof follows immediately from the proof of Theorem in which we compute closed form of the weights variation. is presented in App.
B.2 GENERALISATION:
Theorem 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.T
Theorem 3 Generalisation of SGD and OGD for Continual Learning
The proof 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 Lemmal 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 [
Bounding the empirical loss for SGD (App. D.2.5) the emror is the same OGD on the last task. While on the previous tasks, Catastrophic Forgetting can be incurred which implics the appearance of 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
Lemma Implications for Curriculum Learning This results follows from the technical Lemma which upper bounds the Rademacher complexity of the function class that corresponds to the set of linear combinations of kernel regressors.
B.3 THE IMPORTANCE OF THE NTK VARIATION FOR CONTINUAL. LEARNING
The proof relies mainly on Theorem 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
Proposition I OGD implies A-GEM-NT
16

---

Under review as a conference paper at ICLR 2021
C MISSING PROOFS OF SECTION 4
CONVERGENCE
C.I PROOF OF THEOREM I
Stochastic Gradient Descent
We start by proving the Stochastic Gradient Descent (SGD) case of
Theorem [|
Proof
We prove the Theorem by induction.
Our induction hypothesis H,, is the following: H, For all k S T, Theorem holds.
First, we prove that H. holds.
The proof is straightforward. For the first task, since there were no previous tasks, OGD on this task the same as SGD.
Therefore, it is equivalent to minimising the following objective
arg migmin// (X()) ((X,)= wo) -vall2 + weR
> 1lw will
where d(x) Vwg (x).
We replace into the objective with 5, applying V1 =y fo(X1)
arg minl (x wi) y1 + 2 ||w w
(2)
weR
The objective is quadratic and the Hessian is positive definite, therefore the minimum exists and is unique:
w = o (x, (x(,) ((x)) + AI) -y
(3)
Under the NTK regime assumption
fi(x) (x) + V fo (x)" (wi wō)
(4)
Then, by replacing into w w
(i(x) = (x) + Vw xx
AI) -3
(5)
fi(x) = (x) + X1 (X1, X1) + AI)-
(6)
Finally:
(x) - fx() = kn (x, X, (m: X,) AI) -1
(7)
Which completes the proof of H4.
Let E N we assume that Hr is true, then we show that Hx+1 is true.
On the task TT+1, we can write the loss CT+1 as
(r+ = (X++1)) (w w;) 8 8r+1 1|
||w
w/ll
(8)
2
We recall that the optimisation problem on the task T 7+1 is:
(X.+1) w:) -5++1 2 X W
arg argmin||
| w
(9)
2
The optimisation objective is quadratic, unconstrained, with a positive definite hessian. Therefore, an optimum exists and unique
w F+ w: o(X (" AI) -5 ++1
(10)
17

---

Under review as a conference paper at ICLR 2021
We define the kernel Ky+1 R R -> IR as
(x_ x (>())" (x') for all x, E R
(II)
Finally, we recover a closed form expression for f
First, we use the induction hypothesis H.
(x) = (*) + (V (x),, W - wW))
(12)
= (x) + (x) (1 (X,+1, X++1) + AI) "5)
(13)
f7 (x) + Ky+1 (X- X+)) AI) yy,41
(14)
At this stage, we have proven H,+11
(15)
Orthogonal Gradient Descent Now, we prove the Orthogonal Gradient Descent (OGD) case of Theorem ! The key difference in the proof is that the OGD optimisation objective is constrained. The constraints correspond 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.
Proof
We prove the Theorem by induction. Our induction hypothesis H, is the following H, : For all k S Theorem holds.
First, we prove that H., holds.
The proof is straightforward. For the first task, since there were no previous tasks, OGD on this task the same as SGD.
Therefore, it is equivalent minimising the following objective:
arg min] wi) - -v1li²+ ||w -
(16)
weR''
We replace into the objective by the residual term y1 1/1 fo()
X
arg minll/@Xnnnn (X, (X,))(W (ww w - 31112 2 w woll?
(17)
weR.
where oxx) V Wwg (x).
The objective is quadratic and its Hessian is positive definite, therefore the minimum exists and is unique:
W o ( (Xx)) XT) -3
(18)
Under the NTK regime assumption
fi(x fö (x) Vw (wi wh)
(19)
Then, by replacing into w w
fx()) fā (x) + Ox (( +A)
(20)
fi() (x) (x (X,, X1, AI) '/1
(21)
Finally:
(x) (x) m X,, (x, x AI 13
(22)
18

---

Under review as a conference paper at ICLR 2021
Which completes the proof of M4. Let E IN' we assume that H- true, then we show that Hz41 true. On the task T r+,,
write the loss LT+1 as:
X llw will
LT+1 (w) (X 1) wf) -r+1 1 2
(23)
We recall that the optimisation problem on the task 'T TT+1 is:
arg min
mngmin//,,22 (l, (Xx++1)) (w w;) Vr+1l12 + l| will
(24)
weR
u.c.
V++I(w w;)
(25)
where V++1 is projection matrix on ① of the tasks (T k E [T]]. Let T++ E gd xd k,+1) and w E g K,+1 such as:
Ex) the Euclidean space induced by the feature maps
k=1
w -T w
(26)
K, dim A E+) A=
(27)
We rewrite the objective by plugging in the variables we just defined. The two objectives are equivalent:
112 + A T w1
arg min
(
T 81+1
(28)
2
wel"" K++1
This objective is equivalent to:
112 + x [w1
arg min
|X
(29)
WeR Kr+1
For clarity, we define Z, I R +1 (d Kr+1) as:
2,+1 のz (X++11 (T TT+1
(30)
By plugging in Z,+1, we rewrite the objective as:
arg min WeR d-
IZ.+ 3 [1
(31)
The optimisation objective is quadratic, unconstrained, with positive definite hessian. Therefore, an optimum exists and unique
z"= (Z,+1 2 + Xy)
(32)
We recover the expression of the optimum in the original space:
W : Tr+1 ZT, (Z,-1 - AI)
15
(33)
We define the kernel Ky+1 Rd x Rd + IR as
+x+1(x,x0 x²) 4, (x) T 1+ T (x)))(x)) for x, x' Rdd
(34)
Now we rewrite W w
W w T T zTT ((5++1(,++))) X,+1) AI) -
(35)
Finally, we recover a closed form expression for f++1: First, we use the induction hypothesis Hy:
f++ f (x) (Wwf w w")
(36)
= ff + or (x) DT (X++1, Xr+1) + +AI)-15,..
(37)
= (x) + K6 (x, X (X, X,+1) + +XI) -II-15,41
(38)
At this stage, we have proven He+1- We conclude the proof of Thm.
(39)
19

---

Under review as a conference paper at ICLR 2021
C.2 PROOF OF THE COROLLARY
Stochastic Gradient Descent
The proof follows immediately from Thm.
Proof
In the proof of Theorem [
(App. C.1
for the SGD case, we showed that
w+ W
o(x++)) (( + AI) A
(40)
This result implies that:
[w++ will
+ 1-11)''
1 31+11 ++1
(41)
( XTI -
+ 15
r+1
(42)
(43)
Orthogonal Gradient Descent The proof is exactly the same the proof above, the difference lies in the kernel definition, which is implicit.
Proof
In the proof of Theorem (App. for the OGD case, we showed that
w - w T zz (Kir (Xr+1, X++1) + AI)-157.
(44)
This result implies that
[[ +1 w ( X++1) + AI) 'z,+ T 7+1 T (8++1 X,+1) + AII--'y 4t1 (45)
"8,41
=5 X741) AI) -000kkx4110 (X Xr+))))++111))(((((1111
+ XI) - y
(46)
(47)
20

---

Under review as a conference paper at ICLR 2021
D MISSING PROOFS OF SECTION 5 GENERALISATION
D.1 PROOF OF THEOREM 2
The intuition behind the proof is since the gradient updates performed orthogonally 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.
Proof
In the proof of Theorem 1 App. C.1
we showed that, for T fixed task:
f = (*( + wV w 7+1 -
(48)
We rewrite the recursive relation into sum:
(x( = Σ VV (x), - w
(49)
We observe that, for all & E [
k+1 w E Ex-
(50)
On the other hand, for OGD+, given a sample x from D,, for all k E [7 + +,7]]:
fw)f(x): Ex-
(51)
Therefore, for all K E [ 1,
(x) w wk:) =
(52)
Therefore:
(x = fx()
(53)
We conclude.
(54)
D.2 PROOF OF THEBRREM 3
D.2.1 REMINDERS
Reminder RKHS norm
Let kemne,, and H. the reproducing kernel Hilbert space (RKHS) corresponding to the kernel k.
Recall that the RKHS norm of a function f(x) aT n(x, X) is
Ill V (xTn(X
(55)
(56)
Reminder on Generalization and Rademacher Complexity Consider loss function / : R x
R + R. The population loss over the distribution D, and the empirical loss over samples D ((x,),) [n]} from the same distribution D are defined as
Ls( Ln(f)
(57)
1 n
(J(x))))))
(58)
Theorem Suppose the loss function is bounded in [0, c] and is p Lippschit in the first argument.
Then, with probability at least 1 8 over sample S of size n
log(2/8)
(L -s(f) 2pR(F) + 3c/ feF
(59)
2n
21

---

Under review as a conference paper at ICLR 2021
D.2.2 BOUNDING |
Lemma Let Hl the Hilbert space associated the kernel K
We recall that
(x = Ri, (x, X,) at
(60)
OG (Nr (x, 11)
(61)
Then
| H. (X, +
(62)
(63)
Proof
We start from the definition of the RKHS norm of f
F+ 7.
= 1 (X, X,)a, = 8 (Nr (X X,) + R (X,,,,,,,,, +1)
(64)
(65)
Since (Kr (Xr, X,) + AI) < (Kir (X,,
S 3 (Kir (x, X, + AI) Ker ,x,,
(66)
5エ (K+ X X 11
(67)
D.2.3 BOUNDING THE RADEMACHER COMPLEXITY
The goal of this section is upper bound the Rademacher Complexity. First, we derive general upper bound for the Rademacher Complexity of linear combination of kernels in Lemma B]. Then, we apply this bound the linear combination of kernels obtained through Thm. which describes the model through the Continual Learning.
A general bound for the Rademacher Complexity
Lemma (Rademacher Complexity of a linear combination of kernels) Let Kt. X x X R, E (T) kernels such that
sup [xx x)]| oo xEX
To every kernel Ka, associate feature map d: X - He. where Hi is Hilbert space with inner product (:y "HH and for all x, x' E X. K4 (x, = (x)(x), ox(x)))) )H.
For all T E N", given a sequence {Br, E [T]} we define Fr as follows:
-x- E{(x), f((x) (x VE 1ftll, S B.}
(68)
Let X1.',,, Xn be random elements of X. Then for the class F, we have
T 2B,
R(F) <
(X,, 2/
n4
Proof
22

---

Under review as a conference paper at ICLR 2021
Let F, and let E X:
T n2
f(x) = Σ
a Kr (x, x!)
(69)
==1
For all [T], we associate feature map 6, X + Hl
Vx,x N (x,xxx) 0x,
(70)
Therefore:
T
f(x)= = Σ
a (0, (x.) or (x)),
(71)
t= =
Σ
0 Φ (x7 ) θ- (x)),.
(72)
==1
On the other hand, the following holds E [T]
Σ o
= [o) B²
(73)
7H.
is
Therefore:
FT C (x
Σ
(wr. dr H. H. S B, Ve [T] == Fr
(74)
Now, we derive an upper bound the Rademacher complexity of Fr
R(Fi) R(Fr)
(75)
T
E
sup |w. Il [E(T]
(W:: nl
cE (xx))H, [(X,)]
(76)
[=1
E
sup W. la S.
(WT:
Σ
GØ, )) H. [X+)]
(77)
n
1=1
Now apply each function the upper bound from Lemma 22 by Bartlett & Mendelson 2003
T
2B
R(FT)
(X,,,
(78)
(79)
Bounding the Rademacher Complexity for Continual Learning
Lemma Keeping the same notations and setting as Theorem the Rademacher Complexity can be bounded as follows:
R(FT) & Eo (1 8..
(x,, + AI)-1y,
(80)
nh.
where Fr the function class spanned by the model up to the task T
(81)
Proof
For all T E N*, given a sequence (Br, r E [T]} we define Fr as follows
Fr = fx + Σ fxx), fx(x) X+) Vr 17,11fl $ B,}
(82)
23

---

Under review as a conference paper at ICLR 2021
where we set B, as
B, v (y, Y
-r-1 -
(K,, (X,, X,, Ar)-ily -V--1-7)
(83)
Following Lemma 2 for all [T]
E
(84)
which means that the function class F, contains the Continual Learning model up to task T
We apply Lemmaßinn in order to upper bound the Rademacher complexity
2B1 (Tr(K x,)))
R(FT)
(85)
n4
We made the assumption that for all E [T] tr(xtr x,)) O(n+):
T
2B,
R(FT)
(vT
(86)
71
T
B
0
(87)
r=1
(y, - - "+ (X, + "y- - -Y--1-77
(88)
n4
(89)
D.2.4 BOUNDING THE EMPIRICAL LOSS FOR OGD
Lemma 5 Given a current task Tr, the empirical losses on the data from all previous tasks (T 7, T S T) can be bounded follows:
Let T fixed. Then. for all T E [T]
2²_
(ft( I n2r
+ AI) -yy-
(90)
(91)
Case -Task TT
Proof
We start from the definition of the empirical loss:
Lsy (17)
(xT,)) - -TT,)²
(92)
(X,) Yrll2
(93)
nr
We replace into fj by its expression from Theorem
Fr (XT) + fi-1(XT) - yr
(94)
|| (XT) - -8r112
(95)
11
[KT (XT,
XT) AI) - 3r
(96)
11
|
AI) (XT, X7) + AI) -5r -7
(97)
15 A(K7 Xy, X,) + AT) 35 - 3r112
(98)
2
1/m | XT) + (IR 35
(99)
24

---

Under review as a conference paper at ICLR 2021
Now, apply Lemma 2 in order to upper bound the right hand side norm
X² Ls, (ft) I y (Xr, + "5r
(100)
nT
(101)
Case 2 Tasks (Tr, E [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.
Proof
We start from the definition of the empirical loss :
1
Ls, (S7)
(x+.)) 12r,i)
(102)
11
i=1 (x,) 8-112
(103)
n4r
Now, applying Theorem 2 which implies that 17(X,) ) = (x+)
Ls. (17)
1 1h
[1,;(x,) - -r-112
(104)
Then with a similar analysis as Case 1, we get:
X² n2
(sf S y,
AI) 15)-
(105)
(106)
D.2.5 BOUNDING THE EMPIRICAL LOSS FOR SGD
As opposed the analysis for OGD, forgetting can occur for OGD and Theorem 2 is 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:
Let fixed. Then, for all T E [T]
X2_ (Kr Xx) AI) AI)
Ls, (ff) S
(107)
nt
For all E [T' 1]
1
Ls, (f7) < -
(k
kr (x, (X,,
(108)
n
T
Σ
ol (K (x,, Xx)
IRA (X, (X (z X + -
k=7+1
(109)
Case -Task TT. For this case, the analysis is the same as for OGD, as no forgetting occurs with respect the data the model is being trained
25

---

Under review as a conference paper at ICLR 2021
Case 2 Tasks (T,, E - Since SGD is not guaranteed to be robust to Catastrophic Forgetting, this case comprises additional residual terms that correspond to forgetting.
-]};
Proof
Let (T-
From Corr.
we recall that
fi(x) f
Σ (x)
(110)
k=
Then :
T (x,, vr112 = [x(X,) + Σ f((x)) -Y-
(111)
k=Tt1
(x+ v-11 +
Σ (x(,) k==+1
(112)
|x - - v-11++
Σ
(xx))
11
(113)
k=
We upper bound A similarly to the previous paragraphs (x,,
y,112 25 (k, X,) + AI) AI) ",,
(114)
Now, we upper bound
B Let E [,7]]
I Xx) + AI)
K (X Xx)
(Na (X,, Xx) + AI)-1yy
Similarity
T, and
(115)
We conclude by plugging back the upper bounds of and B
(X,; - y.
(hr (X,, -5
(116)
T VI (X,, Xx) + AI) KR (X,,
Xx)
(B) Xx) + XI)
k=++1
(117)
Therefore:
Ls. (s)( - 1 (Mx
(118)
T
+ Σ (Kx + ''xx (..X,,X))allll X (X,, Xx) + AI) AI) (5.)
k=t+1
(119)
D.2.6 PROOF OF THE GENERALISATION THEOREM (THM. 3
Now, we prove the Theorem by applying the lemmas we developed above.
Proof
26

---

Under review as a conference paper at ICLR 2021
With probability 1 8 we have:
log(2/8)
sup feFr
(LD(f)- Ls(f)} s 2pR(FF) 30/
(120)
2nT
log(2/6)
(f) S (ft) + (pR(FF) + 3
(121)
2nr
T
(Xs, Xx))
log(2/0)
CD. S Cs.
3c
2nT
h=1
(122)
Then, by replacing into Ls, (ff.)) with Lemmas 5 and 6 the various cases SGD and OGD.
we get the upper bounds of the theorem for
(123)
D.2.7 ALTERNATIVE PROOF FOR THE EMPIRICAL LOSS BOUNDS No REGULARISATION CASE
This section 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 еπrоr converges to zero. This result illustrates better the intuition behind the term that appears 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 Lemmal Then, we apply this Lemma to prove the convergence to zero in Lemma 8 Finally, in Lemma 9 past tasks, the training error equals to zero all the time.
we show that for the
The training dynamics of OGD
Lemma' (Differential equation of the model's output dynamics) Ler T N", the index of the lask currently being trained on, with OGD.
For all T, defining ú, as
(t) (t -xxx ox, (t, - w;-1)
(124)
KCT
The model's output dynamics while training on the task T, as follows:
ū, + (t) - X,,, 8-).
(125)
(126)
Proof
Let T E N we derive the dynamics while training on the task T,, while training on this task.
First, define
y, -. + or (X,)) w We also define the projection matrix P. E RPXP as:
(127)
P = T T
(128)
The matrix P, performs the projection from the original weight space IR. to the trainable weight space during training on task T,, which corresponds to + Eg)
k=
27

---

Under review as a conference paper at ICLR 2021
Our starting point is the SGD update rule:
w- + 1) = (I( - Vw
(129)
where:
L7 (t), = | (X,, (w
(wr (t) w 1 8-112
(130)
= | (X,) )dr w- (5r + or (X=()>)))))) / w 11
(131)
| (X,)² ) w 8111
(132)
Therefore, get the following expression for the gradient of the loss (wL"(w,(t)) = o, (x,)) (t) )-)
(133)
Then, the following holds:
(134)
(1+++1) (1) (x,)) (W, w-))
(135)
+x (-P-
(136)
= -
-)))
(137)
= (6 -t)()))(+))
-
(138)
(X,,, (1)-),) -ÿ,)
(139)
= =-7jK, (t)
(140)
- (X, X, (ū, (t) -5,)
(141)
It follows that:
ú, + 1) y, (I- 7H, (X, X, (ū, 8-))
(142)
(1) - -ÿ, = -- (X,, X))) (ū)(())) -())
(143)
(144)
The training error converges to zero
Lemma 8 For all tasks T,, [T], the training error C (w)(t) converges to 0 when tends to infinity.
Proof
We start with the definition of the training error on task T
Cs(f(") = 1.0 (X+) - -y-
(145)
ا (1) 3111
(146)
(1 7,,, (X, (ū) 8.)
(147)
Under the assumption that (X, X-) is positive definite, for || (X. X.Di||
the eigenvalues
become less than therefore:
lim (s()(())
(148)
t-000
The training error the past tasks is zero
Lemma For all tasks T,. E [T], the training error Cs.(f) = 0.
Proof This lemma follow immediately from Lemma & 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.
28

---

Under review as a conference paper at ICLR 2021
E MISSING PROOFS OF APP A FOR CONTINUAL LEARNING
THE IMPORTANCE OF THE NTK VARIATION
E.1 PROOF PROPOSITION 1 OGD IMPLIES A-GEM-NT
We present the proof of Proposition!! |
which relies mainly on Theorem 2 stating the robustness of
OGD Catastrophic Forgetting.
Proof
Let T, task fixed, we recall that in the NTK regime, the model can be expressed as
[w(x) = (x) + VJō (x) ww-1)
(149)
Given a task TR and its associated memory Mg. we recall that the loss can expressed as:
M() Σ (x) (x)()(( wi-1) y)²
(150)
(X.))EMi
Similarly to the A-GEM paper, we define gradients vectors g and (gx, [T - 1]} as:
g Vwl(fw, Dy)
(151)
gA = Vwl(fw,Mk)
(152)
Now we extend the expressions:
gi = -Vwl(Jw,Dr Dr)
(153)
Vw Σ
(x;-1(x) V w;-1) -y)
(154)
(X.))EMe
Σ (x=1(x)
(x)(x)( w V
(155)
(X.))MM
For OGD, following Thm. variant for finite memory
Σ
(x) 1)
(156)
(X.))eM.
Finally, since the gradient updates are orthogonal to M
g
(157)
Therefore, for all k E [T 1]
g: g We conclude, OGD implies learning with GEM and A-GEM with no Positive Backward Transfer.
(158)
(159)
29

---

Under review as a conference paper at ICLR 2021
F EXPERIMENTS
REPRODUCIBILITY
F.1.1 ARCHITECTURES
Due to the memory limitations encountered while running OGD and OGD+ the CIFARIO 100 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 layers, each layer uses RELU activation function. The model has 10 logits, which do not use any activation function.
The neural network is multi-head LeNet Lecun et al. (1998) network with Batch Normalisation Toffe & Szegedy (2055) and 200 hidden units for the penultimate layer.
CIFARI00:
Similarly to Jung al. 2020 base architecture is AlexNet (Krizhevsky al. 2012). In order to scale for the OGD type algorithms, we changed the classifier module to a smaller layer RELU neural network, with dropout (Table(5).
CUB200
Layer
Linear (4096, 256)
RELU Dropout (0.5)
Linear (256, 128)
RELU
Linear (128,
Table 5: Classifier module of the architecture used for the CUB200 benchmark.
F.1.2 EXPERIMENT SETUP
We each experiment 5 times, the seeds is the same across all experiments sets. We report the mean and standard deviation of the measurements.
F.1.3 OGD+ IMPLEMENTATION DETAILS
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 balance of the feature maps from all tasks in the memory.
For the dataset streams Split MNIST and Split CIFAR-100, we consider muldi- neural networks. We only store the feature maps with respect the shared weights, the projection step is not performed for the heads" weights.
Multi-head models :
F.1.4 HYPERPARAMETERS
We use the the same hyperparameters as Farajtabar al, (2019) for the algorithms SGD, OGD and OGD+, on the MNIST benchmarks. We also keep small learning rate, in order to preserve the locality assumption OGD, and in order to verify the conditions of the theorems. We report the shared hyperparameters across the benchmarks and algorithms in Table
For the other benchmarks and algorithms, we report the grid search space in Sec. F.I.5
F.1.5 HYPERPARAMETER SEARCH
We present 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 the corresponding github repository.
30

---

Under review as a conference paper at ICLR 2021
Hyperparameter
MNIST
CIFAR-100
CUB-200
Epochs
5
50
75
Architecture
MLP
LeNet
AlexNet (variant)
Hidden dimension
100
200
256
Torch seeds
to 5
Memory size per task
100
Activation
RELU
Table 6: Hyperparameters used across experiments
MNIST Benchmarks
EWC, SI and MAS : we fixed the seed to O, then performed a grid search over the regulari-
sation parameter in [0.1, 10, 100, 1.000, 10.000]
SGD, OGD and OGD+:
used the same hyperparameterss as Farajtabar et al. (2019).
Stable SGD we fixed the seed to 0 then performed grid search over all combinations of:
gamma [0.5, 0.6, 0.7, 0.8, 0.9]
learning rate [0.01, 0.1, 0.25] batch size [10, 32, 64]
dropout [0, 0.1, 0.2, 0.3, 0.4, 0.5]
CIFAR100 and CUB200 Benchmarks
EWC, SI and MAS we fixed the seed to 1, then performed a grid search over:
regularisation coefficient: [0.1, 1, 10, 100, 1.000, 10.000]
learning rate [0.00001, 0.001, 0.01, 0.1]
batch size [32, 64, 256]
SGD, OGD and OGD+ For the MNIST benchmarks, we used the same hyperparameters
Farajtabar al. (219)) While for the CIFAR100 and CUB200 benchmarks, the following grid search
learning rate [0.00001, 0.001, 0.01, 0.1]
batch size [32, 64, 256]
epochs: [1, 20, 50]
Stable SGD we performed the following grid search :
gamma: [0.5, 0.6, 0.7, 0.8, 0.9]
learning rate [0.001, 0.01, 0.1]
batch size [10, 64]
dropout [0. 0.1, 0.2, 0.3, 0.4, 0.5]
epochs: [1, 10, 50]
31

---

Under review as a conference paper at ICLR 2021
F.2 EXPERIMENTS MEMORISATION PROPERTY OF OGD (THM.
F.2.1 THE IMPORTANCE OF THE OVERPARAMETERIIZATOO ASSUMPTION
Thm. 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 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 400.
Results Figure 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 overparameteriiztton.
Then cine vanston
Hidden ri2
320
14 16
The variation of the train accuracy on the memorised samples from the each task, after the model was trained on all tasks in sequence (higher is better). We vary the hidden size as a proxy for overparameterization.
Figure 3:
F.2.2 THE IMPORTANCE OF THE MEMORY SIZE ASSUMPTION
Thm. 2 states that in the NTK regime, given 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, function of the memory size per task.
Results
Figure shows that the mean train accuracy variation decreases uniformly with the memory
size.
Tran doc 20 sanstinn
30
10
-30
100
200
300
Tosk
Figure 4: The variation of the train accuracy the memorised samples from the first task, after the model was trained on all tasks in sequence (higher is better). We vary the memory size per task from 100 to 300.
32

---

Under review as a conference paper at ICLR 2021
F.3 THE IMPORTANCE OF THE NTK VARIATION FOR CONTINUAL LEARNING (SEC.
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.
F.3.1 PERMUTED MNIST
Accuracy + Std. (%)
Task 1
Task
Task 3
Task 4
Task
Task 6
Task 7
A-GEM
76.0+1.6
78.4+1.7
80.3+1.4
82.0=1.6
82.
84.6+0.9
86.2+0,9 85.4+1.9
OGD+
72.8+1.6
75.2+2.9
78.0+1.8
79.8+1.4
81.4#1.4
84.3+1.8
OGD
33.1
62.8+1.6
75.5+2.8
77.1+4.4
82.2+1.4
83.5+1.9
86.5+1.3
Accuracy + Std. (%)
Task 8
Task
Task 10
Task 11
Task 12
Task 13
Task 14
Task 15
A-GEM
87.1+1.1
89.120.9
89.0+1.1
90.3+0.7
91.
92.540.8
93.620.4
94.720.2
OGD+
87.3+1.1
88.4+1.2
90.2+0.7
91.5+0.8
92.4=0.5
93.340.4
94.020.3
94.5=0.1
OGD
86.8+0.5
88.4+1.3
90.240.9
91.6+0..4
92.7+0.2
93.240.3
94.0=0.1
94,420.1
Table Permuted MNIST: The test accuracy models from the indicated task after being trained on all tasks in sequence. The best Continual Learning results highlighted in bold.
F.3.2
ROTATED MNIST
Accuracy = Std. (%)
Task
Task
Task 3
Task 4
Task
Task
Task
A-GEM
76.1+2.3
78.3+2.1
83.6+1.1
86.1+0.8
88.1
89.540.1
91.0+0.3
OGD+
65.4+1.2 41.7+1.6
67.8+1.1
75.6#1.1
80.1
83.9#1.1
86.3+1.2
88.7+0.8
OGD
44.7+1.4
53.2+1.7
61.4+1.4
68.7+1.2
74.8+1.2
81.3+0.8
Accuracy + Std. (%)
Task 8
Task
Task 10
Task 11
Task 12
Task
Task 14
Task 15
A-GEM
91.6+0.2
93.020.2
94.0+0.2
95.1+0.2
95.920.0
96.440.1
96.3+0.1
96.0=0.1
OGD+
90.3+0.7
92.3+0.4
93.9+0.2
94.9+0.1
95.9+0.1
96.120.1
96.140.1 96.2+0.2
95.6#0.
OGD
86.0+0.7
89.7+0.5
92.5+0.2
94.4+0.1
95.7+0.1
96.1
95,8+0.2
Table 8:
Rotated MNIST: The test accuracy of models from the indicated task after being trained all tasks in sequence. The best Continual Learning results are highlighted in bold.
33

---

Under review as a conference paper at ICLR 2021
150
110
56
(a) Task
(b) Task 5
40
(c) Task
(d) Task
105
100
(e) Task
(f) Task 7
(g) Task 4
(h) Task 8
(i) Task 5
ii Task 10
Figure 5: Test accuracy on the first tasks of Rotated MNIST, for SGD, OGD, OGD+ and A-GEM. The y-axis is truncated for clarity. We report the mean and standard deviation over independent runs. The test error is measured for every 250 mini-batch interval.
34

---

Under review as a conference paper at ICLR 2021
F.4 COMPARISON WITH OTHER CONTINUAL LEARNING BASELINES
In order to get broader picture on the robustness of OGD+ to Catastrophic Forgetting, we benchmark it against standard Continual Learning baselines.
F.4.1 EVALUATION
Denoting ar,r the accuracy of the model the task T, after being trained on the task Tr, 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):
1 Σ
Average Accuracy ACC
0T57
(160)
T
Backward Transfer: BWT
01,T
O,,7
(161)
T
Forward Transfer: FWT
ay-1,7 - b
(162)
T
T=1
T-1
Average Forgetting:
AFM
max
(at,r - -T,r)
(163)
T
LE (e(1....T-111
F.5 BASELINES
In addition to the standard baselines, SGD, EWC, SI and MAS, we compare OGD+ against OGD and Stable SGD, which 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, also include this method in our benchmarks.
F.5.1 COMPLEMENTARY RESULTS CONTINUAL LEARNING METRICS
Permuted MNIST
Table 9 shows that OGD+ outperforms the baselines AAC, while it remains competitive on AFM and BWT.
Method
AAC
BWT
FWT
AFM
Naive SGD
76.31 (+1.89)
-19.27 (+2.0)
1.12 (#1.14)
-19.27 (#2.0)
EWC
80.85 (#1.14)
-13.69 (#1.22)
0.97 (#0.8)
-13.69 (+1.22)
SI
86.69 (#0.4)
-..02 (+0.3)
(+1.1
-4.02 (#0.3)
MAS
85.96 (#0.72)
-4.84 (#0.73)
2.51 (#1.36)
-4.84 (#0.73)
Stable SGD
78.17 (#0.76)
-11.63 (+1.03)
1.02 (#0.15)
-11.63 (+1.03)
OGD
85.0 (+0.86)
-9.71 (#0.95)
0.19 (#0.71)
-9.71 (#0.95)
OGD+
88.65 (#0.38)
-5.98 (#0.36)
0.92 (#1.84)
-5.98 (#0.36)
Table 9: Comparison of the average accuracy, average forgetting, forward transfer and backward transfer of several methods the Permuted MNIST benchmark.
35

---

Under review as a conference paper at ICLR 2021
Rotated MNIST Table 10 shows that OGD+ is competitive with the baselines AAC and AFM, while it underperforns on the other metrics. Also draws an improvement over OGD on AAC, BWT and AFM. One probable reason is the relatively low overparameteriizaion of the setting shown in Table T
Method
AAC
BWT
FWT
AFM
Naive SGD
71.06 (+0.41)
-25.99 (40.46)
85.92 (#0.61)
-26.37 (+0.45)
EWC
80.96 (+0.42)
-9.03 (40.44)
79.01 (+0.58)
-9.58 (#0.46)
SI
75.33 (+0.55)
-18.62 (#0.6)
82.66 (#0.61)
-19.24 (+0.58)
MAS
80.55 (+0.46)
-2778 (+0.43)
70.85 (#0.64)
-6.0 (+0.48)
Stable SGD
88.92 (+0.19)
-2.22 (+0.54)
78.73 (+1.05)
-2.8 (+0.53)
OGD
79.17 (+0.33)
-17.17 (#0.35)
85.66 (+0.61)
-17.77 (#0.35)
OGD+
87.73 (+0.5)
-7.88 (+0.55)
85.45 (+0.64)
-8.57 (#0.53)
Table 10: Comparison of the average accuracy, average forgetting, forward transfer and backward transfer several methods on the Rotated MNIST benchmark.
Split CIFARIO0 Table 11 shows that OGD+ is not competitive on Split CIFARI00 all metrics.
Also it draws the same performance as OGD on all metrics, one probable reason is the overparameter- ization of the setting as shown in Table
Method
AAC
BWT
FWT
AFM
Naive SGD
50.77 (#3.99)
-31.63 (+4.26)
0.31 (#1.17)
-31.82 (+4.1)
EWC
56.82 (#1.75)
-20.32 (+2.5)
0.56 (+1.26)
-20.43 (+2.44)
SI
66.66 (#2.07)
-9.41 (+2.51)
(41.26)
-10.03 (+2.38)
MAS
66.33 (+1.13)
-3.31 (#1.12)
0.56 (+0.93)
-4.44 (+0.98)
Stable SGD
72.86 (+0.9)
-11.14 (40.99)
-0.19 (#1.69)
-11.14 (+0.99)
OGD
61.82 (+1.24)
-2.844 (#1.44)
0.33 (+1.02)
-20.86 (=1.4))
OGD+
61.11 (=1.11)
-21.56 (+1.29)
0.32 (+0.97)
-21.59 (#1 1.7)
Table 11: Comparison of the average accuracy, average forgetting, forward transfer and backward transfer of several methods on the Split CIFAR100 benchmark.
CUB200 Table shows that OGD+ is not competitive the CUB200 benchmark all metrics. Also it draws the same performance as OGD on all metrics, one probable reason is the overparameter- ization of the setting as shown in Table [
Method
AAC
BWT
FWT
AFM
Naive SGD
53,93 (+0.86)
-17.07 (#0.88)
0.15 (#0.45)
-17.07 (+0.88)
EWC
62.15 (#0.37)
-3888 (#0.49)
-0.12 (#0.57)
-3.88 (#0.49)
SI
63.17 (#0.42)
-3,24 (#0.63)
-0.23 (+0.51)
-3.43 (40.46)
MAS
61.43 (40.68)
-7.76 (+0.87)
-0.17 (+0.8)
-7.85 (#0.9)
Stable SGD
58.79 (#0.36)
-6.16 (+0.23)
-0.01 (#0.8)
-6.23 (#0.17)
OGD
57.89 (+0.89)
-12.97 (40.94)
0.02 (+0.55)
-12.99 (+0.92)
OGD+
57.99 (+0.52)
-12.88 (40.51)
0.08 (+0.53)
-12.89 (+0.51)
Table 12: Comparison of the average accuracy, average forgetting, forward transfer and backward transfer several methods on the CUB200 benchmark.
36

---

Under review as a conference paper at ICLR 2021
F.5.2 COMPLEMENTARY RESULTS
VALIDATION ACCURACY THROUGH TRAINING
0G0
CCD
(a) Permuted MNIST Task
(b) Permuted MNIST Task
(c) Rotated MNIST Task
(d) Rotated MNIST Task
Nave SE0
State 550
(e) Split CIFAR100 Task
(f) Split CIFAR100 Task
REVA
MACE MEDO
MAG
Statie 500
Sta04 500
(g) Split CUB200 Task
(h) Split CUB200 Task
Figure 6: Test accuracy through tasks for different Continual Learning methods on the MNIST and CIFAR 100 and CUB200 benchmarks. The y-axis is truncated for clarity. We report the mean and standard deviation over 5 independent runs. The test error is measured at the end each task.
37


Reviews:
[{"review_id": "x0qkc0FQgL0", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nWhile the paper makes an interesting attempt on theoretical analyses of OGD based continual learning method, I feel the result is quite limited only to the OGD scheme. Also, the result is for regression, as shown in the loss function in Sec 3.2, but the experiments are on classification, so it's not clear with the connection with the theory and the experiments. The results also seem to be somewhat simple derivations from the known papers, like Jacot et al., (2018) and Liu et al, (2019). \n\nThe experimental results are also very limited  and weak since it only compares with SGD, an obvious weak scheme that suffers from catastrophic forgetting, and does not compare with any other continual learning baselines. For example, the state-of-the-art on CIFAR-100 is around 65%, and the performance of OGD is very weak. Even though the paper aims for a theoretical contribution, it is very limited only for OGD based scheme, which is not strong in practice. So, I am not sure about the significance of the contribution of the paper. But, I haven't fully read the entire proof of the paper, and I may have missed some details regarding the proof. I would like to see other reviewers' opinion as well. \n\nWhat about comparing with more enlarged and various benchmark datasets beyond MNIST and CIFAR-100, like CUB200 or Omniglot as shown in https://arxiv.org/pdf/2003.13726.pdf ? How does OGD or OGD+ compares with other baselines like EWC or MAS?", "extra_scores": {}, "extra_text": {}}, {"review_id": "gUZ45jsK7A", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##########################################################################\n\nSummary:\n\n \nThis paper studies the theoretical aspect of a continual learning method called orthogonal gradient descent (OGD).\nIn this study, authors leverage Neural Tangent Kernel and over parameterized neural networks to prove the generalization of OGD. \n\n##########################################################################\n\nReasons for score: \n\n \nOverall, I vote for rejection. I like the idea of the paper to analyze an exist method from different aspect and even improving it. However, my major concern is about the clarity of the paper (see cons below).\n\n \n##########################################################################Pros: \n\n \n1. The paper investigate an important problem in continual learning framework which is the generalization.\n\n \n2. This paper provides some experiments to show the effectiveness of the proposed framework. \n\n \n##########################################################################\n\nCons: \n\n1. Unfortunately, the paper is not clear and very difficult to follow.\na) For instance, NTK is referred without explaining it well first. \nIn page 2, authors use \"CL\" for referring to continual learning but it has not been defined.\nb) There are many typos and capital letters have been used inappropriately.\nc) f_t has not been defined.\n2- Although the proposed method provides several experiments, there are still many other methods and datasets that have been ignored. There has been recent studies and frameworks that have outperformed OGD, it woud be great if you include them in your baselines. For instance, SGD+Droput in https://arxiv.org/pdf/2004.11545.pdf beats OGD.\n\n3-  There are many metrics to evaluate continual learning frameworks like backward transfer(BWT) or average accuracy over tasks.\nI would suggest the authors to look at the defined metrics in GEM (gradient episodic memory), https://arxiv.org/abs/1706.08840, and compute those values. \n\n \n##########################################################################\n\nQuestions during rebuttal period: \n\n \n- Please address and clarify the cons above .\n- Would you please elaborate more what could be the superior performance of OGD+ on Rotated Mnist dataset w.r.t OGD?\n- What is the time complexity of OGD+?\n\n \n\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "KP68nw6ma4d", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.  \n\nThe primary contribution of this paper is the theoretical analysis of continual learning.  Given that the CL problem does not have an extensive theoretical foundation, the generalization bound in this paper is a notable advance. The theory presented also provides a justification for the empirical observations observed by the authors that as overparameterization increases, the effect of catastrophic forgetting decreases in a variety of CL task setups.  The primary drawback of the paper is that the authors do not compare the OGD+ algorithm to other continual learning algorithms (synaptic intelligence, elastic weight consolidation, etc.).  As a result it is difficult to know how OGD+ compares to alternatives.  It is not clear to the reviewer why improving OGD to OGD+ is itself a contribution.  Given the expense occurred by OGD-type methods in storing ever increasing numbers of directions, it would be important to know the comparison of this method with others.  \n\nMinor comments:\n\n(1) Section 3.2: f^* is not defined as of this point in the paper.\n(2) Theorem 1: The theorem needs a quantifier of lambda\n(3) Line above Remark 1 k_\\tau -> \\kappa_\\tau\n(4) Theorem 2: The paper should define what \"is in the memory\" means when introducing OGD\ns\n(5) Theorem 3: Definition of R_T has incorrect dummy index in the summation\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers were excited by the paper's theoretical contribution to continual learning, since that aspect of continual learning is underdeveloped.  However, all reviewers (including the most positive reviewer during discussions) expressed that the paper would benefit from revisions to improve the clarity and the thoroughness of comparisons in the paper.  The paper's focus on OGD is not necessarily an issue for it to be of use to the community, as mentioned as a negative point in one review that other reviewers disagreed with. The authors are encouraged to revise this paper incorporating the reviewers' suggestions.
Decision: Reject