Continual learning: a feature extraction formalization, an efficient algorithm, and fundamental obstructions
Authors: Binghui Peng
Andrej Risteski
Venue: NeurIPS 2022 Accept (2022)
Keywords: Continual learning
learning theory

Abstract: Continual learning is an emerging paradigm in machine learning, wherein a model is exposed in an online fashion to data from multiple different distributions (i.e. environments), and is expected to adapt to the distribution change. Precisely, the goal is to perform well in the new environment, while simultaneously retaining the performance on the previous environments (i.e. avoid ``catastrophic forgetting'').
While this setup has enjoyed a lot of attention in the applied community, there hasn't be theoretical work that even formalizes the desired guarantees. In this paper, we propose a framework for continual learning through the framework of feature extraction---namely, one in which features, as well as a classifier, are being trained with each environment. When the features are linear, we design an efficient gradient-based algorithm $\mathsf{DPGrad}$, that is guaranteed to perform well on the current environment, as well as avoid catastrophic forgetting. In the general case, when the features are non-linear, we show such an algorithm cannot exist, whether efficient or not.

Continual learning: a feature extraction formalization, an efficient algorithm, and barriers
Binghui Peng Columbia University bp26010columbia, edu
Andrej Risteski Carnegie Mellon University aristesk@andrev. cmu, edu
Abstract
Continual learning is an emerging paradigm in machine learning, wherein a model is exposed in online fashion to data from multiple different distributions (i.e. environments), and is expected to adapt to the distribution change. Precisely, the goal is perform well in the new environment, while simultaneously retaining the performance on the previous environments (i.e. avoid "catastrophic forgetting") While this setup has enjoyed a lot of attention in the applied community, there hasn't be theoretical work that even formalizes the desired guarantees. In this paper, propose framework for continual learning through the framework of feature extraction-named one in which features, as well as a classifier, are being trained with each environment. When the features are linear, we design an efficient gradient-base based algorithm DPGrad, that is guaranteed to perform well on the current environment, well avoid catastrophic forgetting. the general case, when the features are non- non-linear, we show such an algorithm cannot exist, whether efficient or not.
Introduction
In the last few years, there has been an increasingly large focus in the modern machine learning community on settings which go beyond iid data. This has resulted in the proliferation of new concepts and settings such out-of-distribution generalization [G]. domain generalization [3]. multi-task learning [4]) continual learning (55 and etc. Continual learning, which is the focus of this paper, concerns learning through a sequence of environments, with the hope of retaining old knowledge while adapting to new environments.
Unfortunately, despite lot of interest in the applied community-ae evidenced by multitude of NeurlPS and ICML workshops 26
approachhs with formal theoretical guarantees are few and far between. The main reason, similar encountered as its cousin fields like out-of-distribution generalization or multi-tasks learning, usually come with some "intuitive" desiderata - but no formal definitions. What's worse, it's often times clear that without strong data assumptions- the problem is woefully ill-defined.
12 30)
The intuitive desiderata the continual learning community has settled is that the setting involves cases where an algorithm is exposed (in an online fashion) to data sequentially coming from different distributions (typically called "environments", inspired from robot/agent interacting with different environments). Moreover, the goal is to keep the size of the model being trained fixed, and make sure the model performs well the current environment while simaltaneously maintaining good performance in the previously seen environments. In continual learning parlance, this is termed "resistance catastrophic forgetting".
clear that some of the above desiderata are shared with well-studied learning theory settings (e.g. online learning, lifelong learning), while some aspects differ. For example, in online learning,
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

we don't care about catastrophic forgetting (or we only do so in some averaged sense); in lifelong learning, it's not necessary keep the size of the model fixed. It is also clear that absent some assumptions on the data and the model being trained, these desiderata cannot possibly be satisfidd: why would there even exist model of some fixed size that performs well on both past environments, and current ones - let alone one that gets updated in an online fashion.
A feature-extraction formalization of continual learning Our paper formalizes a setting for continual learning through the lens of feature extraction: the model maintains a fixed number of (trainable) features, as well as a linear classifter on top of said features. The features are updated for every new environment, with the objective that the features are such that a good linear classifier exists for the new environment, while the previously trained linear classifiers (on the updated features) are still good for the past environments. The reason the linear classifiers from previous rounds are not allowed to be updated is storage efficiency: in order to tune the prompts, one needs to store the training data from previous tasks, this would bring storage overhead and potentially privacy concerns. This is very common approach in practice- examples of this are systems involving large amounts of data of a streaming nature (e.g. Google searches, Youtube, a robotic agent interacting with continual stream of environments), and it be would prohibitive to store it for later fine tuning. The number of features kept fixed for the same reason: if we are to expand with new features for every new environment, the model size (and hence storage requirements) would grow.
We prove two main results for our setting.
1. When the features are a linear function of the input data, and good set of features exist, we design an efficient algorithm, named doubly projected gradient descent, or DPGrad, that has good accuracy on all environments, and resists catastrophic forgetting. Our algorithm, while being novel, bears some resemblance to class of projection-baser algorithms used in practice [I] S learning.
we hope the theoretical analysis can shed insight onto large scale continual
2. When the features are allowed to be a non-linear function of the input, we show that continual learning is not possible-in general. Namely, construct instance for which even if good set of features exists, the online nature of the setting, as well as the fact that the linear classifiers for past environments not allowed to be updated, makes it possible for the algorithm to "commit" to linear classifiers, such that either catastrophic forgetting, or poor performance on the current environment has to occur.
2 Our results
2.1 Problem formulation
In a continual learning problem, the learner has sequential access to k environments. In the i-th E [k)) environment, the data is drawn i.i.d. from the underlying distribution D; over Rd R. denoted (x. v) DD where x E Rd is the input and y E R is the label. Motivated by the empirical success of representation learning [2] [9 we formulate the continual learning problem through the feature extraction view: The learner is required to learn a common feature mapping (also known as representation function) R Rd + H' that maps the input data æ E IRd to a low dimensional representation R(x) RR (r < d), along with a sequence of deeendennddnnt linear classifiers (also known as linear prompts) UI,..., 2% E IR" on top of the representation. Precisely, the prediction of the i-th environment is made by f(x) = (v,, R(x)).
As this is the first-cut study, we focus on the realizable and the proper learning setting That is, we assume the existence of a feature mapping R in the function class H (which is known in advance) and a sequence of linear predictor u1,-.., Uk such that for any i E [k]] and any data (r. y) ~ D,, y = (o,, R(x)) (realizable). The learner required to output a function R that belongs to the hypothesis class H (i.c. the learner is proper).
Remark 2.1 (Known environment identity). Our model requires the knowledge of environment identity at test time, and thus can be classified into the category of incremental task learning. We
We note it is possible to extend our algorithmic result to the realizalie setting, provided the label has symmetric sub- aub-gaussian noise.

---

note there is also empirical research focusing on unknown environment identity, which would be an interesting direction for future work (See Section
The guarantee that we wish our learning algorithm to obtain is as follows:
Definition 2.2 (Goal of Continual Learning). Let d. k. r N. r & d, CE (0.1/2). Let be function class in which the feature mappings from IR to IK' lie. The continual learning problem involves & environments Di,..., DD=- We assume there exists function R. E H and sequence of linear classifiers vi...., ukk E IR" such that for any (I.y) Di (i [k]], the label satisfies = = (,,,R()))
The continual learner has sequential access environments Di...., DE. well access to arbitrarily many samples per environmen The goal is to learn a representation function E H and sequence of linear prompts U...... Uk R' that achieve a good accuracy on the current task and do not suffer from catastrophic forgetting. Formally, in the i-th environment (i E [k]), the learner optimizes the feature mapping R and the linear classifier v2 (without changing U1,..., (-11) and aims to satisfy
Avoid catastrophic forgetting: During the execution of the i-th task, the algorithm guar- antees that
L(R, 22) = 2 (z.v)>D)
E ((0g, R(x)) - v)² S for all j = 1,..., 1-
Good accuracy on the current task: At the end of i-th task, the algorithm guarantees that
1 E. ((us, R(x)) - y)² c.
T 0;) 2 (z.9)>,
For linear feature mapping, the representation function can be written in a linear form R(x) = UT x for some U E RRdxr, and it implies the i-th environment is generated by a linear model. That is, defining w; = Uv, E Rd, one can write y = (ve, U x) {ws, 2))
Remark 2.3 (The benefit of continual learning with linear feature). Note, for linear features, it's in principle possible to just learn sequence of linear classifiers Wi..... ... Wk E Rd separately- without learning a low-dimensional featurizer. Choosing an r-dimensional featurizer confers memory efficiency (O + dr) (ddk) and sample efficiency (O(r) vs. (d)) samples per task in the asymptotic regime l - oo). Furthermore, the linear case is a sandbox that can be mathematically analyzed and can generate insights for the nonlinear case as well.
2.2 DPGrad: Efficient gradient based method for linear features
For the case of linear features, we propose an efficient algorithm which we term DPGrad (pseudocode in Algorithm|D D which is an efficient gradient based method and provably learns the representation while avoids catastrophic forgetting. Towards stating the result, we make few technical assumptions.
Assumption 2.4 (Distribution assumption). For any i [k]. assume D; has zero means and it is
in isotropic position, that is, EzwD, [x] = Ô and Ez-D,, [x:'' 1
Remark 2.5. This assumption is largely for convenience. In fact, one can replace the isotropic condition with a general bounded covariance assumption, our algorithm still can work with extra preprocessing step, and the sample complexity scales with the condition number of covariance matrix.
Assumption 2.6 (Range assumption). For any i [R)], wi has bounded norm, i.e., || 2 S D.
Assumption 2.7 (Signal assumption). For any i E [k]. let W; = span(wi,.... w.), Wi,1 be the space perpendicular to W, and Pw,, Pw,,, be the projection operator: We assume either un belongs to W,-1 or it has non-negligible component orthogonal to Wę-1, i.e., | [| will2 E {0) ( D). Assumption 2.8 (Bit complexity assumption). Each coordinate of is a multiple of v >>>>> 0.
Remark 2.9. The Range and Signal assumptions are standard in the statistical leurning literature.
The former ensures upper bound ||w l2 and the later ensures that new task provides enough "iignal" for new features. They are used to set up learning rate and number of gradient iterations.
'The results easily extend to the finite sample case using standard techniques. We focus on the population results to keep the focus the online nature of the environments.
3

---

Remark 2.10. The Bit complexity assumption states that W; can be described with finite number of bits, and is mostly for convenience namely so we can argue we exactly recover w,-which makes calculations involving projections of features learned in the past cleaner. Since the number of gradient iterations only depends logarithmically on v, one can relax the bit complexity restriction to only approximately recovering the ground truth features up to polynomially small (in d, k, D, c) precision. Our argument can still go through at the cost of some additional error analysis.
The main result is then as follows:
Theorem 2.11 (Continual learning with linear fcatures). Let N,r
(0,1/2).
When the features are a linear function over the input data, under Assumption 2.4 Assumption 2.6 2.8 with high probability, DPGrad provably achieves good loss and avoids catastrophic forgeting. In particular, during the execution of i-th environment, DPGrad always ensures
1
L(U,v;) =
IE (a.j)~;;
(x Ut, - -y)² s, for all j 1, 2,2, ...,,
and at the end of i-th environment, DPGrad ensures
E L(U, vx) 2 (x.D),D,
(ar Uu; y)² Sc.
2.3 Fundamental obstructions for non-linear features
The continual learning setup with non-linear features turns out to be much more difficult even without computational constraints. Our result rules out the existence of a proper continual learner, even when all environment distributions are uniform and the representation function is realizable by a two-layer convolutional neural network.
There exists class of non-linear feature mappings and sequence of environments, such that there is (proper) continual learning algorithm that can guarantee to achieve less than 1000 -error over all environments with probability at least 1/2,under the feature extraction formalization of Definition 2.2
Theorem 2.12 (Barrier for Continual learning with non- non-linear feature). Let k. 2 2, 2,
3 Related work
Continual learning in practice The study of continual learning (or lifelong learning) dates back to the work of 336 and it receives surge of research interest recent years [I5]] 19
5
14
31
17
29
39 18. A central challenge in the field is to avoid fatussrophiccforgettnng [24]
23 which the
work of [5] observed happened for gradient-based training of neural networks. While there is large
amount of empirical work, we' 'lll briefly summarize the dominant approaches. The regularization based approach alleviates catastrophic forgetting by posing constraints on the update of the neural weights. The elastic weight consolidation (EWC) approach [19 adds weighted lg regularization to the objective function that penalizes the movement of neural weights. The orthogonal gradient descent (OGD) algorithm from [ [ enforces the gradient update being orthogonal to update direction (by viewing the gradients as a high dimensional vector). The memory replay approach restores data from previous tasks and alleviates catastrophic forgetting by rehearsing in the later tasks. B1 introduces experience replay to continual learning. [4] trains a deep generative model (a.k.a. GAN) to simulate past dataset for future use. The dynamic architecture approach dynamically adjusts the neural network architecture to incorporate new knowledge and avoid forgetting. The progressive neural network [4] blocks changes to the existing network and expands the architecture by allocating a new subnet to be trained with the new information. We refer the interested reader to more complete surveys 25 77
Continual learning in theory In comparison to the vast empirical literature, theoretical works are comparatively few. The work of [ characterize the memory requirement of continual learning, when the environment identity is unknown. The works [35 27 1 provide sample complexity guarantees on lifelong learning. Their approaches can be categorized roughly into the duplicate and fine-tuning paradigm: The algorithm maintains a weighted combination over a family of representation functions and the focus is on the sample complexity guarantee. By contrast, we focus on the feature extraction paradigm and learn linear prompts on top of a single representation function. Both the auplicate-and- fine-tuning and the feature extraction paradigm have been extensively investigated in the literature,

---

detailed discussions can be found at 7 and we provide brief comparison. From an algorithmic perspective, learning a weighted combination over family of representation functions (i.e. the duplicate and fine-tuning) is much easier, as one can always initiates new representation function for a new task. The algorithmic convenience allows previous literature focus more on the generalization and sample complexity guarantee, culminating with the recent work of [ We note again that learning a single representation function and task specific linear prompts is much more challenging, but has practical benefits, e.g. memory efficiency. For example, in the applications of NLP, the basic representation function (e.g. BERT (9]) is already overparameterizes and contains billions of parameters. It is then formidable to maintain large amount of the basic models and learn linear combination over them. We mention several more works that are morally related in Appendix A
4 Continual learning with linear feature
We restate our main result for linear feature mapping.
Theorem 2.11 (Continual learning with linear features). Let k. d, E &,,, (0.1/2)
When the features are a linear function over the input data, under Assumption 1.numption..aannd Assumption 2.6
2.8 with high probability, DPGrad provably achieves good loss and avoids catastrophic forgetting In particular, during the execution of i-th environment, DPGrad always ensures
L(U,0,) =
E (a.y)~>;;
(x UxJUr, - -3)² S e, for all j L, 2, ................................ 1-1, 1,
(1)
and at the end of i-th environment, DPGrad ensures
E L(U, vx) = 2 (2.g)DD,
(x Ux - u)² Se
(2)
4.1 Algorithm
A complete and formal description of DPGrad is presented in Algorithm 1 DPGrad simultaneously updates the matrix of features U, as well as the linear classifier v, using gradient descent- with the restriction that the update of U only occurs along directions that are orthogonal to the column and row span of the previous feature matrix. Intuitively, one wishes the projection guarantees that existing features that have been learned are not erased or interfered by new environments. Due to the quadratic nature of the loss, and the appearance of "cross-terms", this turns out to require both column and row orthogonality, and interestingly deviates from the practically common OGD method I 5
In more detail, the beginning of the i-th (i E [k)) environment, DPGrad adds Gaussian noise to the feature matrix U and the linear classifier vi, to generate a good initialization for and u;- Subsequently, we perform gradient descent to both the feature mapping matrix U and linear classifier W e--excep U is only updated along orthogonal directions w.r.t. the column span and the row span. At the end of each environment, DPGrad has a post-processing step to recover the ground truth w; by rounding each entry of U'; to the nearest multiple of v P and then update the column and row span if the orthogonal component is non-negligible. The reason for the later step is that we only need to preserve row space when encountering new features.
Parameters We use to denote the initialization scale, denote the learning rate, and T to denote the number of iterations for each task. These are all polynomially small parameters, whose scaling roughly D. d, l < 0 < 17 <T
Notation We write [n] = (,,,....., n),, |n :2)] = [MI...., }. We use rand (M1, n2) E R X
to denote size n2 R22 matrix whose entries are draw from random Gaussian N(0, 1). For each i [A]. t E [0 T). denote U,, to be the feature matrix in the t-th iteration the i-th environment (after performing the gradient update), denote Ui, similarly. DPGrad includes projection step at the end of i-th environment, we use Uidand to denote the feature matrix after this projection. We use W, (resp. V,) to denote the column (resp. row) space maintained at the end of i-th environment. Let W1 C IR" be the subspace orthogonal to W and define V1 similarly. Let Pw, Pv, Pw., Pv, be the projection onto W. V. W1, V1 separately.
'Tii is the only place where use the Bit complexity assumption.
5

---

Algorithm Doubly projected gradient descent (DPGrad)
1:
0.V 0. +
> U E Rdxr
2: σ + TED ) 17 0 p T. + 01 log Dkd + 0 log )
3: for l.r.=,.... do
4:
Unii f- a Pw_ rand (d, r) Pv 0i + rand(r)
Unit Rdxr 14 Rd
5:
U 5 U + Unit
6:
for t = "....,T' do
7:
VU f- (x. [x(x Uv y)0 Ve, + -B(y))),, (UTx(
x(x Uv, UU; -y)l
8:
nPw, Vulv
9:
U1 8/3 V m
10: end for
11: end for
12: Wi &- Round,
b Round to the nearest multiple of v, 02 E Rd
if Pw We 2| 2 1/D then W span(W w.), span(V U U.)
14: U <- PwUPv
4.2 Analysis
We sketch the analysis of DPGrad and prove Theorem 2.11 Due space limitation, the detailed proof is deferred to Appendix The proof proceeds in the following four steps:
1. The first step. presented in Section matrix factorization and it allows us to focus on more algebraically friendly objective function.
reduces continual learning to a problem of continual
2. We then present some basic lincar-algebraic facts to decompose the feature mapping matrix U. its gradient, and the loss into orthogonal components. The orthogonality of gradient update allows us to decouple the process of leveraging the existing features and the process of learning new feature, reflected in the loss terms and gradient update rules. See Section 4.27 for details.
3. In Section 4.2.3 we zoom into one single environment, and prove DPGrad provably con- verges global optimum, assuming the feature matrix U from previous environment is well conditioned. This step contains the major bulk of our analysis: The objective function of continual matrix factorization is non-convex, and no regularization or spectral initialization used. (We cannot re-initialize, lest we destroy progress from prior environments.)
4. Finally, in Section 4.2.4 we inductively prove that DPGrad converges and the feature matrix is always well-conditioned. This wraps up the entire proof.
4.2.1 Reduction
We first recall the formal statement of the problem continual matrix factorization.
Definition 4.1 (Continual matrix factorization). Let d, k, N, d, k, > O. Let W [wi...., wx] = (V*))) Rdxk where U Rdxr V E Rkxr, In an continual matrix factorization problem, the algorithu receives ue E Rdd in the i-th step, and it is required to maintain matrix U RRdx and outpul vector v. E RR such that
1 IU wil3 Se, L(U,
(3)
2
and
i(U 01) [10n wyl12 sc j j= ;
The key observation that running DPGrad on the original continual learning objective 2 implicitly
optimizes the continual matrix factorization objective K (Lemma 4.2 Moreover, e-approximate
solution continual matrix factorization is also an e-approximate solution of continual learning (Lemma 3

---

Lemma 4.2 (Gradient equivalence), Under Assumption 2.4 for any i E [k], the gradient update of objective equals the gradient update of objective
Lemma 4.3 (Objective cquivalence). For any w Wk E R. E Rd and Vi..... 2k E R"
suppose L(U, u)) =1ll'; will < e holds for all E [k], then L(U, v.) = ((ay) (x Uv: y)² 6.
Combining the above observations, it suffices to analyse DPGrad for continual matrix factorization and prove Eq. 3 and Eq. 4
4.2.2 Decomposition
We first provide some basic linear algebraic facts about orthogonal decompositions. For any i [k.. we decompose Us, Usy along W.-1, W,-1.1. V and V1-1,
Let w, W + B where A E W,-1 and Wi W Note this decomposition is unique. We focus on the case that ||w,,llle E [1/D, , DJ in the following statements, and the case of |lw,Bll2 0 carries over easily. (These are the only U, = U + U. where each column of U, lies W;-1 and each column of wi,B lies in W1-1.1- (Note, again, U and Us, B are unique.) We further write Us,B = Ba, + U122, where the columns of U,2 lie in W,-1,1 \ (w;,B). Finally, denote e; 02 U/22 with 0, Vi-1 and 14,2 E V We summarize decompositions mentioned above, with a few additional observations, in the lemma below:
cases, per Assumption 2.7 Similarly, let
Lemma 4.4 (Orthogonal decomposition). For any i [k] and any E [0: T) there exists an unique decomposition of Ui and Vi,t of form
U2 = U1A,D + B,,
column(Ur.An) E WW,-1, Column(UUUU E W
row(Ui,A..) E Vi-1, row(Uu,,,))) E V;-1,1
Wi = W/,A + Wi,B:
wA,A W,-1, W,, E W1-1,1 Di,t E VoWL.,, E Vi-1,1, w 1 column
B, = w/ B + U12
Uge = 111, + U3222
U1,1, E V,-1, 2422, V
Here we use column A), row(A) to denote the column and row space of matrix A, and column A) W if the column space of A is subspace of W.
Since A. remains unchanged for t [0 7}, we abbreviate it as U.A hereafter. We next provide the exact gradient update of each component under loss function L(U,, 04) 1 [[ w,ll2 and orthogonal projection.
Lemma 4.5 (Gradient formula). For any E [k], the gradient update (after projection) obeys the relations (1) Vz, ( ( U12 1): (2) Vu.. 2222,,200.2 (3) Ve,, (1)
UT, - U.TAAU U,A Wi,A and (4) V. (L) = ||,, (z] 612 1)x, U,
We perform similar decomposition to the loss function.
Lemma 4.6 (Loss formula). For any E [k], E [T'] we have
D(UGe, v..) = " wr + 2 10r.B1/(4TT,.... - 1)² + 1 11222 (5)
Decoupling existing features from "new" features We now offer some intuitive explanation for the decomposition. The first loss term in Eq. 5 quantifies the error with already learned features. That is, the matrix U.A stores existing features that have been learned, and it remains unchanged during the execution of the i-th environment; it remains to optimize U1,1, such that U,, matches W,,A- The second and last loss term quantify the loss on a new feature, wherew,,p is the new feature component, and the matrix Ui,2, can be thought of as random noise. Intuitively, one should hope Vi,,, and this matches the new component of wi,. At the same time, one hopes U2 would disappear, at least, 2 + 0 when oc.
7

---

4.2.3 Convergence
For fixed environment, prove w.h.p. DPGrad converges and the loss approaches to zero, given the initial feature mapping matrix U is well conditioned.
Lemma 4.7. For any E [ki, suppose U satisfies 2VD
1 S Amin mmin(Ur,)) S maax mmax(Ui,.) S DV minn(Ur, (UL,A) and max (Ui,a) denote the minimum and maximum non-zero singular value of matrix U, After T O( L log Did +0( & log * iterations, with probability at least 1 - ((1/k)
where min
the loss L(U,, 04) S EV/ Dnk.
Outline of the proof DPGrad ensures existing features are preserved and it only optimizes the linear classifier, hence a linear convergence rate can be easily derived for the first loss term, given the feature matrix is well-conditioned. The key part is controlling the terms that capture learning with new features, i.e., the second and last loss term, where both the feature mapping Uz, R and linear prompt i get updated. In this case, the objective is non-convex and non-smooth. Our analysis draws inspiration from the recent work of [40], and divides the optimization process into two stages. We prove DPGrad first approaches to nice initialization position with high probability, and then show linear convergence f
To be concrete, in the first stage, we prove (1) T %4,2, moves closer to 1, and (2) | || 22 2 O. That is, the second loss term of Eq. ( decreases to small constant while the pairs Fi,t. 022,4 remain balanced and roughly equal up scaling. Meanwhile, we note U22, is non- non-increasing, though the last loss term could still increase because ||0,,2 ll2 increases. In the and "4,2t
second stage, we prove by induction that ||U, 22,2,112 2.,.,,.. (hence converging to global optimal), and | || 100.B1222,2,11l = O.
1| decay with linear rate
4.2.4 Induction
Lemma 4.7 proves rapid convergence of DPGrad for one single environment. To extend the argument to the whole sequence of environments, we need to ensure (1) the feature matrix is always well- conditioned and (2) catastrophic forgetting does not happen. For (I), we need analyse the limiting point of DPGrad (there are infinitely many optimal solutions to Eq. (.), make sure it is well-balance and orthogonal previous row/column space. For (2), we make use of the orthogonality of DPGrad.
Proof Sketch of Theorem 2.17 Thanks to the reduction established in Section 4.2.1 it suffices to prove Eq. B and Eq. For each environment i (i [K)), we inductively prove (1) DPGrad achieves good accuracy on the current environment, i.e., |U - will2 S ev; (2) The feature
matrix U, remains well conditioned, i.c. 2VD (umi(Uu,end) S maxx (U).nd) ) S 2vDD and (3) The algorithm does not suffer from catastrophic forgetting, i.e., ||U;, - w.|l2 for any j < i, E [7]]
The first claim is already implied by Lemma 4.7 For the second claim, one first shows DPGrad exactly recovers w; by taking w; C. = Roundy feature matrix does not change, i.c. Uz,end = -,-1,endi when W;,B E [1/D, D). then one can show || W...B./..T as W,.B column(UG-1.en)) U22,, 1 row(Ui-1,end) and
When W,,B O, one can prove the
Uieedd ~ Uid + 1
(لाل.रा W < O(vD)) the feature matrix U remains well-conditioned. The last claim can be derived from the orthogonality. This wraps up the proof of Theorem
5 Lower bound for non-linear features
We next consider continual learning under a non-linear feature mapping. Learning with non-linear features turns out to be much more difficult, and our main result is to rule out the possibility of (proper) continual learner. We restate the formal statement. The detailed proof are deferred to Appendix
'We note most existing works on matrix factorization or matrix sensing either require some fine-grained initialization (e.g. spectral initialization 8 adding regularization term that enforces smoothness [3], none of which are applicable in setting.
8

---

Theorem 2.12 (Barrier for Continual learning with non-liness feature). Let ker 2 2, d 2 3. There exists a class of non-linear feature mappings and a sequence of environments, such that there is no (proper) continual learning algorithm that can guarantee to achieve less than 1000 -error over all environments with probability at least u/2,under the feature extraction formalization of Definition 2.2
Our lower bound is constructed quadratic activation functions. The input distribution is assumed to be uniform and the target function a polynomial over the input. The first environment is constructed such that multiple global optimum exist (hence the optimization task is under-constrained). However, if wrong optimum solution is picked, when the second environment is revealed, the non-linearity makes impossible switch
simple family of two-layer convolutional neural network with
Proof Sketch. Sketch. It suffices take = 2, 3,r and we sketch the construction here. For both environments, we assume the input data are drawn uniformly at random from (3 1), where (3 1) denotes the unit ball R centered at origin. The hypothesis class H consists of all two-layer convolutional neural network with single kernel of size 2 and the quadratic activation function. That is, the representation function is parameterized by w E g² and takes the form of (x) ((w, x1,2)² (w, x223)²) E IR?, where E RR, Tzgj E IR 1R/-+11 is vector consists of the i-th entry to the j-th entry of x.
The hard sequence of environments are drawn from the following distribution: (1) The objective function fi of the first environment is fz) z²: (2) The objective function fz of the second environment equals f2(x) z with probability 1/2, and equals f2(x) = 2 with probability 1/2. Note the continual learning task is realizable and one can prove no (proper) continual learning algorithm can guarantee to achieve less than 1 1/1000-error on both environments with probability at least 1/2.
Though our lower bound instance uses polynomial activation function, this assumption is not essential in Appendix we prove similar lower bounds with a ReLU activation function.
6 Experiments
For linear feature functions, we perform simulations on synthetic dataset to verify the practicality of DPGrad and compare its performance with vanilla SGD and Orthogonal gradient descent (OGD), a close practical cousin of our algorithm. In our simulations, we set d = 100, r = 20, & = 500 and the ground truth U* V* is drawn from Gaussian. The input data are sampled from N (0. Ia) and we draw 1000 samples for each task. Additional details about the setup can be found in Appendix D
10a
DPGD
SCD
10a
20-1
30'2
10
10
100
200
300
400
500
Task ID
Figure 1: Continual learning with linear feature: comparative performance of DPGrad/OGI//SGD. Data is synthetically generated with d = 100, r = 20, k = 500 and the ground truth U*, V is drawn from Gaussian. Additional details about the setup can be found in Appendix D
The results are presented at Figure I It indicates the (1) practicality of DPGrad and (2) DPGrad significantly outperforms the vanilla SGD and OGD (of course, DPGrad is designed for this kind of data). The population loss is measured at the end and the it equals ||U l|2 for each task The

---

average enror of DPGrad is 0.001, the average error of OGD is 83.59, the average error of SGD is 5.16.
Moreover, in Appendix we provide additional experimental results on two popular benchmarks, Rotated MNIST and Permuted MNIST. Since DPGrad is designed specifically for linear regression, we provide two variants of DPGrad (without provable guarantees on their performance, of course)- one is modification suitable for multi-class classification, the other is modification suitable for non-linear featurizers, Detailed numbers and figures can be found in Appendix algorithms alleviate catastrophic forgetting and perform much better than vanilla SGD. Furthermore, the performance of both is much more stable than OGD and the accuracy remains at high level across tasks.
I In brief, both
Conclusion
In this paper, we initiate a study of continual learning through the feature extraction lens, proposing an efficient gradient based algorithm, DPGrad, for the linear case, and a fundamental impossibility result in the general case. Our work leaves several interesting future directions. First, it would be interesting to generalize DPGrad to non-linear feature mappings (perhaps even without provable guarantees) and conduct empirical study of its performance. Second, our impossibility result does not rule out an improper continual learner, and in general, one can always maintain a task specific representation function and achieve good performance over all environments. would be thus interesting to investigate what are the fundamental memory-accurase trade-offs.
Acknowledgement
BP acknowledges support of the NSF via CCF-1909756, CCF2007443, CCF-2134105, CCF-1703925, IIS- 1 1881554, CCF-2106429 and CCF-2107187. AR acknowledges support of the NSF via IIS- 2211907, the CMU/PwC DT&I Center, and an Amazon Research Award.
10

---

References
[1] Maria-Florina Balcan, Avrim Blum, and Santosh Vempala. Efficient representations for lifelong learning and autoencoding. In Conference on Learning Theory, pages 191-210, PMLR, 2015.
[2] Yoshua Bengio, Aaron Courville, and Pascal Vincent. Representation learning: A review and new perspectives. IEEE transactions pattern analysis and machine intelligence, 35(8):1798- 1828, 2013.
[3] Gilles Blanchard, Gyemin Lee, and Clayton Scott. Generalizing from several related classifica- tion tasks to new unlabeled sample. In Advances Neural Information Processing Systems, volume 24. Curran Associates, Inc., 2011.
[4] Xinyuan Cao, Weiyang Liu, and Santosh S Vempala. Provable lifelong learning of representa- tions. arXiv preprint arXiv:2 10. 11100/44000 /4098, 2021.
[5] Arslan Chaudhry, Naeemullah Khan, Puneet Dokania, and Philip Torr. Continual learning in low-rank orthogonal subspaces. Advances in Neural Information Processing Systems, 33, 2020.
[6] Xi Chen, Christos Papadimitriou, and Binghui Peng. Memory bounds for continual learning. In 2022 IEEE 63th Annual Symposium on Foundations of Computer Science (FOCS), 2022.
[7] Zhiyuan Chen and Bing Liu. Lifelong machine learning. Synthesis Lectures on Artificial Intelligence and Machine Learning, 12(3):1-207, 2018
[8] Yuejie Chi, Yue M Lu, and Yuxin Chen. Nonconvex optimization meets low-rank matrix factorization: An overview. IEEE Transactions on Signal Processing, 67(20):5239-526) 2019.
(9] Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume (Long and Short Papers), pages 4171-4186, 2019.
[10] Simon Shaolei Du, Wei Hu, Sham M Kakade, Jason Lee, and Qi Lei. Few-shot learning via learning the representation, provably. In International Conference on Learning Representations, 2020.
[11] Mchrdad Farajtabar, Navid Azizan, Alex Mott, and Ang Li. Orthogonal gradient descent for continual learning. In International Conference on Artificial Intelligence and Statistics, pages 3762-3773. PMLR, 2020.
[12] Haytham Fayek, Arslan Chaudhry, David Lopez-Paz, Eugene Belilovsky, Jonathan Schwarz, Mare Pickett, Rahaf Aljundi, Sayna Ebrahimi, Razvan Pascanu, and Puneet Dokania. Ieml workshop on continual learning, 2020.
[13] Rong Ge, Chi Jin, and Yi Zheng. No spurious local minima in nonconvex low rank problems: A unified geometric analysis. In International Conference on Machine Learning, pages 1233-1242. PMLR, 2017.
[14] Alexander Gepperth and Cem Karaoguz. A bio-inspired incremental learning architecture for applied perceptual problems. Cognitive Computation, 8(5):924-934 2016.
[15] Ian J Goodfellow, Mehdi Mirza, Da Xiao, Aaron Courville, and Yoshua Bengio. An empirical investigation of catastrophic forgetting in gradient-based neural networks. arXiv preprint 11 2013.
[16] Dan Hendrycks, Steven Basart, Norman Mu, Saurav Kadavath, Frank Wang, Evan Dorundo, Rahul Desai, Tyler Zhu, Samyak Parajuli. Mike Guo, et al. The many faces of robustness: critical analysis of out-of-distribution generalization. In Proceedings of the IEEE/CVF International Conference Computer Vision, pages 8340-8349, 2021.
[17] Khurram Javed and Martha White. Meta-learning representations for continual learning. Ad- vances in Neural Information Processing Systems, 32, 2019.

---

[18] Ghassen Jerfel, Erin Grant, Tom Griffiths, and Katherine A Heller. Reconciling meta-learning and continual learning with online mixtures of tasks. Advances Neural Information Processing Systems, 32, 2019.
[19] James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei A Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Barobskk,aa,nkkk,, et al. Overcoming catastrophic forgetting in neural networks. Proceedings of the national academy of sciences, 1 114(13)3351--352, 2017.
[20] Andreas Maurer. Transfer bounds for linear feature learning. Machine learning, 75(3):327-350, 2009.
[21] Andreas Maurer, Massi Pontil, and Bemardiio Romera- Sparse coding for multitask and transfer learning. In International conference on machine learning, pages 343-351. PMLR, 2013.
[22] Andreas Maurer, Massimiliano Pontil, and Bernardino Romera-Paredes. The benefit of multitask representation learning. Journal of Machine Learning Research, 17(81):1-32 2016.
[23] James I. McClelland, Bruce L McNaughton, and Randall C O'Reellly, Why there comple- mentary learning systems in the hippocampus and neocortex: insights from the successes and failures of connectionist models of learning and memory. Psychological review, 102(3):419, 1995.
[24] Michael McCloskey and Neal J Cohen. Catastrophic interference in connectionist networks: The sequential learning problem. In Psychology of learning and motivation, volume 24, pages 109-165. Elsevier, 1989.
[25] German I Parisi, Ronald Kemker, Jose L Part, Christopher Kanan, and Stefan Wermter. Continual lifelong learning with neural networks: A review. Neural Networks, 113:54-71, 2019.
[26] Razvan Pascanu, Yee Teh, Mare Pickett, and Mark Ring. Neurips workshop on continual learning, 2018
[27] Anastasia Pentina and Ruth Urner. Lifelong learning with weighted majority votes. Advances in Neural Information Processing Systems, 29, 2016.
[28]
Massimiliano Pontil and Andreas Maurer. Excess risk bounds for multitask learning with trace norm regularization. In Conference on Learning Theory, pages 55-76. PMLR, 2013.
[29] Vinay Venkatesh Ramasesh, Ethan Dyer, and Maithra Raghu. Anatomy of catastrophic for- getting: Hidden representations and task semantics. In International Conference on Learning Representations, 2020.
[30] Amal Rannen-Triki, Arslan Chaudhry, Bogdan Mazoure, Xu He, Thang Doan, Rahaf Aljundi, and Vincenzo Lomonaco. Ieml workshop theory and foundation of continual learning, 2021.
[31] David Rolnick, Arun Ahuja, Jonathan Schwarz, Timothy Lillicrap. and Gregory Wayne. Experi- ence replay for continual learning. Advances in Neural Information Processing Systems, 32, 2019.
[32] Elan Rosenfeld, Pradeep Ravikumar, and Andrej Risteski. An online learning approach to interpolation and extrapolation in domain generalization. arXiv preprint 13Xiv:2102.13128,
2021.
[33] Elan Rosenfeld, Pradeep Kumar Ravikumar, and Andrej Risteski. The risks of invariant risk minimization. In International Conference on Learning Representations, 2020.
[34] Andrei Rusu, Neil C Rabinowitz, Guillaume Desjardins. Hubert Soyer, James Kirkpatrick, Koray Kavukcuoglu, Razvan Pascanu, and Raia Hadsell. Progressive neural networks. arXiv preprint arXiv: !606 04671, 2016.
[35] Paul Ruvolo and Eric Faton. Ella: An efficient lifelong learning algorithm. In International conference machine learning, pages 507-515. PMLR, 2013.
12

---

[36] Sebastian Thrun and Tom M Mitchell. Lifelong robot learning. Robotics and autonomous systems, 15(1-2):25-46 1995.
[37] Nilesh Tripuraneni. Chi Jin, and Michael Jordan. Provable meta-leamiing of linear repre- sentations. In International Conference Machine Learning, pages 10434-10443. PMLR, 2021.
[38] Nilesh Tripuraneni, Michael Jordan, and Chi Jin. On the theory of transfer learning: The importance of task diversity. Advances in Neural Information Processing Systems, 33:7852- 7862, 2020.
[39] Gido van de Ven, Hava T Siegelmann, and Andreas S Tolias. Brain-inspired replay for continual learning with artificial neural networks. Nature communications, 11(1):1-14, 2020.
[40] Tian Ye and Simon Du. Global convergence of gradient descent for asymmetric low-rank matrix factorization. Advances in Neural Information Processing Systems, 34, 2021.
[41] Yu Zhang and Qiang Yang. An overview of multi-task learning. National Science Review, 5(1):30 43:300433220 2018.
Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] to [Yes], [No]. or [N/A]. You are strongly encouraged to include a justification to your answer, either by referencing the appropriate section of your paper or providing brief inline description. For example:
Did you include the license to the code and datasets? [N/A]
Please do not modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [No]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
13

---

(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you' ro using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable
information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you deseribe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "akGyodr4ndn", "reviewer": "Reviewer_KsmC", "summary": "The authors introduce DPGrad, an algorithm for task-incremental continual learning focused on the case where the features extractors are assumed to be linear. They also provide a lower bound on the error for a specific setting with non-linear features extractors.\nDPGrad is compared with SGD and OGD on a simulated environment.", "questions": "* It would be great if the authors could provide more empirical evidence of the performance of their algorithm (maybe on standard benchmarks)\n* See the other points in the paragraph above.", "limitations": "--", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* The paper rigorously defines the setting and assumptions before introducing the new solution\n* The work in this paper tries to provide additional understanding of the theoretical aspects involved in the continual learning process. A direction which is heavily unexplored in the CL community due to the difficulty of the topic.\n\nWeaknesses:\n* The authors generically refer to continual learning in several parts of the paper but, as they correctly point out, there are several different settings in continual learning and their findings do not apply to all of them. It is particular important to be clear about it when providing negative results such the lower bound in Sec. 5.\n* The definition of forgetting on L102 works because of the assumption that the learner will get a good accuracy on the current task (L103) but it would be wrong otherwise. Generally speaking, it would be more intuitive to see it expressed as a difference with the performance measured in the past on an observed task.\n* It is quite hard to understand the potential practical impact of the findings in the paper and the results in Sec. 6 do not help. It is clear that the main contribution of this work is theoretical and the aim is not to outperform some continual learning baselines, but it would be beneficial for the community to understand how big is the gap between theory and practice.\n* Sec 5 provides a lower bound on the error but it is not clear how much of a practical impact that is going to have. It would be interesting if the authors could discuss which realistic assumptions on the environments could provide a more favorable situation.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "LZhUTfWnGQ_", "reviewer": "Reviewer_VAS6", "summary": "In the recent past, there have been several advancements in the field of Continual Learning (CL), where a big chunk of it is devoted to empirical research, such as the usage of replay/regularization-based methods. However, there has been much lesser attention to the theoretical aspects. This work considers continual learning in the regime of regression tasks, where the task descriptors are available. With the standard definition of catastrophic forgetting, the paper demonstrates an algorithm that provably avoids catastrophic forgetting, when the underlying data generating process is such that when the features that lead to optimum solutions to regression can be written as a linear mapping of inputs. Under this setting, they propose an algorithm called DPGrad, which is based on a projected gradient descent algorithm. They further show using a special case that in a non-linear regime, it is not possible to prevent catastrophic forgetting. Finally, in a synthetic toy example, they show the efficacy of DPGrad against OGD and plain SGD. \n", "questions": "As mentioned in the main review.", "limitations": "As mentioned in the main review.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- Theoretical contributions are strong, even for the simplest case, that is linear model regime and squared loss, and proofs seem rigorous (although I’ve not completely verified them).\n\n\nWeakness:\n\nWhile it is primarily a theoretical work, much of the weaknesses of this work are related to limited applicability to the empirical setting. In the following, I will list down my questions:\n\n- In Algorithm 1 Line 13, V is defined as the span of v_i. However in other places as well V is used, but maybe it is referring to row space (see line 205). This is getting a bit confusing to me.\n- While a downside of having a memory-based replay method is mentioned in line 48, they are currently SOTA. How does DPGrad change when CL is accompanied by experience replay? \n- The setting uses task descriptors and have different linear classifier for different tasks ($v_i$). However, again from a practical point of view it is a big assumption that much previous CL work (albeit empirical) tends to avoid. Can it be easily proven/disproven that even in a linear feature case if one uses a single head (just one v_i for all the tasks) catastrophic forgetting will happen? Intuitively it seems it cannot prevent forgetting. \n- While the focus of this work is regression, what about the classification problems? Some of the previous work such as Gradient Episodic Memory (GEM) has the same formulation of no forgetting (assuming memory is a decent representation of task distribution) but uses local linear assumptions to provide a working algorithm. Can authors add some discussion on extending this to classification problems? \n- Can the authors mention the following paper in the related work- “Reconciling meta-learning and continual learning with online mixtures of tasks” especially their section 6.1 have additional simulation-based datasets that can be used in this setting to improve the experiments section?  \n\n\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "LEq_Cpvo1AL", "reviewer": "Reviewer_cwgv", "summary": "The authors consider defining a theoretical framework allowing to study the continual learning problem. They look at this problem from the point of view of feature extraction, where features are continually learned on a sequence of environments, followed by task specific linear classifiers. \nThey then provide an analysis of two cases: the case where the features are linear, and the case where they are not. In the first case, they provide an algorithm that is (under certain well defined assumptions) guaranteed to converge and that gives a learner that does equally well on the past and on the present tasks. In the second case, they construct a counterexample on which no continual learning can guarantee a low error with high enough probability. \nThe algorithm provided for the first case is validated by a simulation on synthetic data, and compared to vanilla stochastic gradient descent and to orthogonal gradient descent from which the proposed algorithm is heavily inspired.", "questions": "I think the paper can be stronger by clarifying certain points. \n\n- The authors recognize the similarity between their proposed algorithm and the gradient projection family of methods that have been previously proposed. Can they state more clearly the differences and why their proposed method is a novel one? \n\n- While the feature extraction take on continual learning is interesting, it would be more interesting in practice to study the case where the feature extractor and the linear classifier are trained simultaneously, taking it closer to e.g. neural networks training. Can the current analysis be extended to cover this case? \n\n- The study of the non-linear case is based on a quadratic activation function and a polynomial target. Most of the neural networks used nowadays use ReLU activations or its variants, and encode piecewise linear functions. Can this fact change the analysis of the non-linear case, and do the results change in that case, especially when coupled with a joint training of the features and the linear classifiers? \n", "limitations": "The paper is mostly theoretical, and a study of societal impact seems out of scope here. \nThe work can however be improved by bringing the non-linear case study closer to settings used in practice. This can lead to a much higher impact and improved understanding of continual learning. ", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n* The paper is looking at filling a gap in the literature between theory and practice. It is looking at a problem that can be very useful for the community to improve our understanding of Continual Learning in general.\n* The paper is well written, with a clear structure and easy to follow. \n* Looking at the problem from a feature extractor point of view is quite intuitive for the supervised setting that is the focus here. \n* The analysis of the linear case is very detailed and clear, and the results in this case are sound and interesting. \n\nWeaknesses: \n* While the paper is well structured, it seems quite unbalanced between the linear case and the non linear one. It is focused mostly around the former, while the latter is more interesting in practice. The motivation of the authors is that the linear case provides intuition for the non-linear case. This is not generally true. From a neural network perspective for example, this can hold for the overparameterized setting, in which the input has a significantly lower dimension than the features. The analysis conducted in this paper consider the opposite setting with low dimensional features, and the insights derived from the linear case are likely to break for the non-linear case. \n* The conclusion for the non-linear case seems to stretch the argument more than it allows. The considered setting is so particular and little used in practice (especially for the supervised learning setting). In particular, the choice of the activation function and the changing objective between the environments are not used in practice. Moreover, the choice of learning the features and the linear classifier separately can highly impact the results. Showing that there is no proper continual learner with sufficiently low error in this setting seems insufficient to conclude that it is the case in general for the non-linear case. \n* The experimental results are interesting as they mimic exactly the theorem assumptions. They are however very limited. It would be interesting to conduct some experiments with real data, even at a small scale (where a linear model can already give reasonable performance), to see if the observations still holds when the assumptions are partly relaxed. ", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "JhCWB08j5Cm", "reviewer": "Reviewer_s7RD", "summary": "The papers considers the incremental problem setting of Continual Learning (CL) and investigates the performance of methods with a multi-head architecture. This setup is seen through the lens of feature extraction, in which there is a shared network which extracts features from the input, and a task-specific linear classifier. The paper reviews two cases. In the first, the feature extractor is a linear mapping of the input. For this case, the authors present a gradient-based algorithm which is guaranteed to be able to learn to perform new tasks, while avoiding catastrophic forgetting. In the second case, the feature extractor is a nonlinear mapping of the input. The authors show that there is a CL sequence in which a CL algorithm cannot reliably achieve a high performance.", "questions": "q1) What reasons would you give that this paper provides an important step forward?\nq2) How would you compare your results in section 5 to the conclusions drawn in [1]?\nq3) On line 338, do you mean “r=3” instead of “n=3”?\n", "limitations": "I did not find a discussion on the limitations of the current findings.\n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I think that this paper constitutes a step in a very interesting direction, namely, exploring the limitations of different CL approaches. I also think that the contributions made in the paper are novel. \nHowever, I am unsure about the paper’s significance. Most of the presentation is dedicated to developing an algorithm which works well when the target feature map is linear. However, there is no discussion on how the insights gained from this are actually relevant to the non-linear setting. Therefore, I am left with the impression that this cannot be used to further the theoretical research in Continual Learning.\nI found the result for non-linear features to be interesting, however, there is a missing discussion on why this is an impactful result. What is more, I think that [1] already contains a similar result, while reached in a different way. Concretely, that if a CL algorithm does not store any data points of past tasks, it’s not going to achieve optimal performance (please correct me if I’m wrong).\nIn terms of clarity, I do not think that the current state of CL research is correctly depicted in the paper. For instance in paragraph 28-34, the authors discuss only a subset of the CL ideas  (a domain-incremental CL setting with regularisation-based approaches) while claiming to summarise all of CL. Moreover, I think that the proof sketch in Section 5 needs another iteration in order to improve readability.\n\n[1] “Optimal Continual Learning has Perfect Memory and is NP-HARD” , Jeremias Knoblauch, Hisham Husain, Tom Diethe\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept