Introduction
Theoretical analysis in linear models
Avoiding catastrophic forgetting

A Theoretical Analysis ofCatastrophic Forgetting
Pierre Alquier

New Trends in Statistical Learning II
Porquerolles, June 2022

Pierre Alquier, RIKEN AIP

Catastrophic ForgettingIntroduction
Theoretical analysis in linear models
Avoiding catastrophic forgettingThang Doan

Mehdi Abbana Bennani

Bosch research

AqemiaBogdan Mazoure

Guillaume Rabusseau

MILA / McGill University

MILA / Unifersité de Montréal

Doan, T., Bennani, M. A., Mazoure, B., Rabusseau, G. & Alquier, P. (2021). A theoreticalanalysis of catastrophic forgetting through the NTK overlap matrix. AISTATS’2021.
Pierre Alquier, RIKEN AIP

Catastrophic ForgettingIntroduction
Theoretical analysis in linear models
Avoiding catastrophic forgetting

Contents

1

Introduction
Continual learning problem
Catastrophic forgetting

2

Theoretical analysis in linear models

3

Avoiding catastrophic forgetting

Pierre Alquier, RIKEN AIP

Catastrophic ForgettingIntroduction
Theoretical analysis in linear models
Avoiding catastrophic forgetting

Continual learning problem
Catastrophic forgetting

Contents

1

Introduction
Continual learning problem
Catastrophic forgetting

2

Theoretical analysis in linear models

3

Avoiding catastrophic forgetting

Pierre Alquier, RIKEN AIP

Catastrophic ForgettingIntroduction
Theoretical analysis in linear models
Avoiding catastrophic forgetting

Continual learning problem
Catastrophic forgetting

NotationsRegression/classification problem :objects x ∈ X ,labels y ∈ Y ⊂ R,
predictors fw : X → Y, w ∈ Rd , objective : neural networks.
Difficulties of “continual learning”
d is huge, → we need a lot of data.
the dataset is huge, → impossible to store all the data.
we will learn w sequentially based on a data stream(xt , yt ), → the xt come from a real life data collection process that makes them
non-indentically distributed..
Pierre Alquier, RIKEN AIP

Catastrophic ForgettingIntroduction
Theoretical analysis in linear models
Avoiding catastrophic forgetting

Continual learning problem
Catastrophic forgetting

Online learning theory
Online learning theory provides algorithms to learn from datastreams, with theoretical guarantees.
Online Gradient Algorithm
w1 := 0,wt+1 = wt − ηt ∇w =wt `(yt , fw (xt )).
Regret bound for OGA
If ` is L-Lipschitz + convex, one can calibrate ηt such thatr
TT
1 X
1 X
2
`(yt , fwt (xt )) − inf`(yt , fw (xt )) ≤ BL.
kw k≤B T
T t=1
T
t=1
Pierre Alquier, RIKEN AIP

Catastrophic ForgettingIntroduction
Theoretical analysis in linear models
Avoiding catastrophic forgetting

Continual learning problem
Catastrophic forgetting

Example : training a self-driving car
Decide an itinerary
from RIKEN AIP (Tokyo)
to Tabayama.

Pierre Alquier, RIKEN AIP

Catastrophic ForgettingIntroduction
Theoretical analysis in linear models
Avoiding catastrophic forgetting

Continual learning problem
Catastrophic forgetting

Observationyt = fw ∗ (xt )y = 1, . . . , τ1 :xt i.i.d from P1 → we learn w1 .

y = τ1 + 1, . . . , τ2 :xt i.i.d from P2 → we update w1 to w2 .

...
y = τK + 1, . . . , τK +1 :xt i.i.d from PK → we update wK to wK +1 .

x ∼ P1 :fwK +1 (x) is a much worse prediction than fw1 (x).
we forgot how to deal with objects x ∼ P1 .
Pierre Alquier, RIKEN AIP

Catastrophic ForgettingIntroduction
Theoretical analysis in linear models
Avoiding catastrophic forgetting

Continual learning problem
Catastrophic forgetting

What is the problem with online learning theory ?

rTT
1 X
1 X
2
`(yt , fwt (xt )) − inf`(yt , fw (xt )) ≤ BL.
kw k≤B T
T t=1
T
t=1
tells you fwt (xt ) predicts well yt (on average over t), notthat fwT (xt ) predicts well yt .
P
online-to-batch bounds : averaging w̄t = 1t ts=1 ws isproven to work well for out-of-sample prediction... in thei.i.d case !

Pierre Alquier, RIKEN AIP

Catastrophic ForgettingIntroduction
Theoretical analysis in linear models
Avoiding catastrophic forgetting

Continual learning problem
Catastrophic forgetting

An example

Hong, D. Y., Li, Y. &Shin, B. S. (2019).
Predictive EWC :mitigating catastrophic
forgetting of neuralnetwork throughpre-prediction of learning
data. Journal of AmbientIntelligence andHumanized Computing.

Pierre Alquier, RIKEN AIP

Catastrophic ForgettingIntroduction
Theoretical analysis in linear models
Avoiding catastrophic forgetting

Continual learning problem
Catastrophic forgetting

Some references

Sutton, R. (1986). Two problems with back propagation and other steepest descent learning
procedures for networks. Proceedings of the Eighth Annual Conference of the Cognitive ScienceSociety.

French, R. M. (1999). Catastrophic forgetting in connectionist networks. Trends in cognitive
sciences.

Kirkpatrick, J., Pascanu, R., Rabinowitz, N., Veness, J., Desjardins, G., Rusu, A. A., Milan, K.,
Quan, J., Ramalho, T., Grabska-Barwinska, A. & Hassabis, D. (2017). Overcoming catastrophic
forgetting in neural networks. Proceedings of the National Academy of Sciences.

Kemker, R., McClure, M., Abitino, A., Hayes, T. & Kanan, C. (2018). Measuring catastrophic
forgetting in neural networks. AAAI’2018.

Pierre Alquier, RIKEN AIP

Catastrophic ForgettingIntroduction
Theoretical analysis in linear models
Avoiding catastrophic forgetting

Contents

1

Introduction
Continual learning problem
Catastrophic forgetting

2

Theoretical analysis in linear models

3

Avoiding catastrophic forgetting

Pierre Alquier, RIKEN AIP

Catastrophic ForgettingIntroduction
Theoretical analysis in linear models
Avoiding catastrophic forgetting

Linear model – notations
initialization : wτ0 = 0.
task τk given as a block :yτk +1Yτk :=  ...  and Xτk := yτk+1xτTk +1..
.
xτTk+1

update :22wτk = arg min kYτk − Xτk w k + λ.kw − wτk−1 kw ∈Rd
= wτk−1 + (XTτk Xτk + λ.I)− XTτk Yτk − Xτk wτk−1 .
|{z}=ỸτkPierre Alquier, RIKEN AIP

Catastrophic ForgettingIntroduction
Theoretical analysis in linear models
Avoiding catastrophic forgetting

Definition of forgetting
Definition - forgetting of task i at the end of task j
For s ≤ t we put∆τs →τt := kXτs wτt − Xτs wτs k2 .
Xτt = Uτt Στt VτTt be the SVD of Xτt ,Oτs →τt = VτTs Vτt the overlap matrix,Mτt := Στt (Στt + λ.I)− UTτt .
Theorem
For any t > s,∆τs →τt =tX

2Uτk Στk Oτs →τk Mτk Ỹτkk=s+1
Pierre Alquier, RIKEN AIP

Catastrophic Forgetting.

Introduction
Theoretical analysis in linear models
Avoiding catastrophic forgetting

Upper bound on forgetting
Corollary√∆τs →τt ≤ kΣτs koptXkOτs →τt kop Mτk Ỹτkk=s+1

With Vτt = (Vτt [1]|Vτt [2]| . . . ) we haveOτi,js →τt = cos(Vτs [i], Vτt [j])and kOτs →τt kop = cos(α) where α is the Dixmier angle
between the span of Vτt and the span of Vτs .
Dixmier, J. (1949). Étude sur les variétés et les opérateurs de Julia, avec quelques applications.
Bulletin de la SMF.

Pierre Alquier, RIKEN AIP

Catastrophic ForgettingIntroduction
Theoretical analysis in linear models
Avoiding catastrophic forgetting

A recent improvement

Evron, I., Moroshko, E., Ward, R., Srebro, N. & Soudry, D. (2022). How catastrophic cancatastrophic forgetting be in linear regression ? COLT’22.

simplified setting, allows an refinement of the analysis,note : I find their results very elegant, so I presented theprevious result using some of their notations.
In their paper :λ = 0, there is w ∗ such that Yτs = Xτs w ∗ (no noise).
the Xτs are normalized ⇒ kΣτs kop ≤ 1.

Pierre Alquier, RIKEN AIP

Catastrophic ForgettingIntroduction
Theoretical analysis in linear models
Avoiding catastrophic forgetting

Consequences of the simplifications
Define the orthogonal projection Pτk = I − Xτk (XTτk Xτk )− XTτk ,then wτk − w ∗ = Pτk (wτk−1 − w ∗ )= Pτk . . . Pτ1 ( wτ0 −w ∗ ),|{z}
=0and ∆τs →τt = kXτs wτt − Xτs wτs k2= kXτs wτt − Yτs k2= kXτs wτt − Xτs w ∗ k2
= kXτs Pτt . . . Pτ1 w ∗ k2
≤ k(I − Pτs )Pτt . . . Pτ1 w ∗ k2 .
Pierre Alquier, RIKEN AIP

Catastrophic ForgettingIntroduction
Theoretical analysis in linear models
Avoiding catastrophic forgetting

Average forgetting : worst caseDefinition - average forgetting at task ttt
1X
1 X τs →τt
2kXτs wτt − Xτs wτs k =∆F (t) :=
t s=1
t s=1

t

1XkXτs Pτt . . . Pτ1 w ∗ k2
F (t) =t s=1
They design a situation where : 
1F (t) ≥ 1 − O √ .
tPierre Alquier, RIKEN AIP

Figure from Evron et al. (2022).
Catastrophic ForgettingIntroduction
Theoretical analysis in linear models
Avoiding catastrophic forgetting

Situations where forgetting do not occur
Evron et al. (2022) then argue that in general, forgetting is
not that bad :cyclic tasks : τ1 , . . . , τT , τ1 , . . . , τT , . . . After seeing ttasks,
 2

T T 2 (d − max{rank(Xτs )}F (t) ≤ min √ ,,tt
randomized tasks : τI1 , τI2 , . . . where the Ii are i.i.d
uniform in {1, . . . , T }, then after seeing t tasks,P
9 d − T1 Ts=1 rank(Xτs ).
E[F (t)] ≤t→ however, this requires to store the tasks, or, at least, to be able to learn them many times...
Pierre Alquier, RIKEN AIP

Catastrophic ForgettingIntroduction
Theoretical analysis in linear models
Avoiding catastrophic forgetting

Conclusion of the theoretical analysis
What we learnt so far
catastrophic forgetting can happen even in linear models,depends on the geometry and order of the tasks.
Open questions :noisy case,nonlinear case,tasks not by block // not aware that a new task begins,other algorithms... (we propose a few in the next section),
theoretical limitations :Knoblauch, J., Hisham, H. & Diethe, T. (2020). Optimal continual learning has perfect memory
and is NP-hard. ICML’2020.

Pierre Alquier, RIKEN AIP

Catastrophic ForgettingIntroduction
Theoretical analysis in linear models
Avoiding catastrophic forgetting

Contents

1

Introduction
Continual learning problem
Catastrophic forgetting

2

Theoretical analysis in linear models

3

Avoiding catastrophic forgetting

Pierre Alquier, RIKEN AIP

Catastrophic ForgettingIntroduction
Theoretical analysis in linear models
Avoiding catastrophic forgetting

Orthogonal updates
Doan, T., Bennani, M. A. & Sugiyama, M. (2020). Generalisation guarantees for continual
learning with orthogonal gradient descent. ICML’2020 Workshop on Lifelong Learning.

wτk =arg minw ∈ RdTVτ
(w − wτk−1 ) = 0
22kYτk − Xτk w k + λ.kw − wτk−1 k1TVτ

k−1.
.
.
(w − wτk−1 ) = 0= wτk−1 + Πk (XTτk Xτk + λ.I)− XTτk Yτk − Xτk wτk−1

where Πk is the orthogonal projection on ker(VτT1 | . . . |VτTk−1 ).
∆τs →τt = 0.
But the procedure requires to store Vτ1 , Vτ2 , ...
Pierre Alquier, RIKEN AIP

Catastrophic ForgettingIntroduction
Theoretical analysis in linear models
Avoiding catastrophic forgetting

Data compression (1/2)
In general, Xτt = Uτt Στt VτTt .
|{z} |{z} |{z} |{z}Nt ×d

Nt ×Nt Nt ×Nt Nt ×d

Data compression : replace Vτt by V̂τt (d × n, n  Nt ) :“OGD” : X̂τt : n rows sampled from Xτt , X̂τt = Ûτt Σ̂τt V̂τTt .
Farajtabar, M., Azizan, N., Mott, A. & Li, A. (2020). Orthogonal gradient descent for continuallearning. AISTATS’2020.

instead of random rows, “memorable observations” :Pan, P. , Swaroop, S. , Immer, A., Eschenhagen, R., Turner, R. & Khan, M. E. (2020). Continual
Deep Learning by Functional Regularisation of Memorable Past. NeurIPS’2020.

Different framework, but the philosophy would here leadto select high-leverage observations.
Pierre Alquier, RIKEN AIP

Catastrophic ForgettingIntroduction
Theoretical analysis in linear models
Avoiding catastrophic forgetting

Data compression (2/2)
Data compression : replace Vτt by V̂τt (n × d, n  Nt ) :our proposal, “PCA-OGD” : PCA on Xτt , that is T V̂τtT.
V τt =∗
Π̂t := orthogonal projection on ker(V̂τT1 | . . . |V̂τTt−1 ).
Ôτs →τt = VτTs Π̂t Vτt√∆τs →τt ≤ kΣτs koptXÔτs →τt

k=s+1

Pierre Alquier, RIKEN AIP

opMτk ỸτkCatastrophic ForgettingIntroduction
Theoretical analysis in linear models
Avoiding catastrophic forgetting

SimulationkÔτs →τt kop for “OGD” and “PCA-OGD” in two settings.

Pierre Alquier, RIKEN AIP

Catastrophic ForgettingIntroduction
Theoretical analysis in linear models
Avoiding catastrophic forgetting

Experiments on the MNIST dataset

Neural network with the NTK approximation :fw (x) ' fw0 (x) + h∇w =w0 fw (x), w − w0 i
Pierre Alquier, RIKEN AIP

Catastrophic ForgettingIntroduction
Theoretical analysis in linear models
Avoiding catastrophic forgetting

Experiments : impact of kOτs →τt kop

Pierre Alquier, RIKEN AIP

Catastrophic ForgettingIntroduction
Theoretical analysis in linear models
Avoiding catastrophic forgetting

Experiments : evaluation of kÔτs →τt kop

Pierre Alquier, RIKEN AIP

Catastrophic ForgettingIntroduction
Theoretical analysis in linear models
Avoiding catastrophic forgetting

Experiments : performances

Pierre Alquier, RIKEN AIP

Catastrophic ForgettingIntroduction
Theoretical analysis in linear models
Avoiding catastrophic forgetting

La fin終わり
ありがとう ございます。

Pierre Alquier, RIKEN AIP

Catastrophic Forgetting