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 as out-of-distribution generalization [16], domain generalization [3], multi-task learning [41], continual learning [25] 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 a lot of interest in the applied community-as evidenced by a multitude of NeurIPS and ICML workshops [26,12,30]-approaches 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.

The intuitive desiderata the continual learning community has settled on 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 a 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 on the current environment while simultaneously maintaining a good performance in the previously seen environments. In continual learning parlance, this is termed "resistance to catastrophic forgetting".

It is 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, we don't care about catastrophic forgetting (or we only do so in some averaged sense); in lifelong learning, it's not necessary to 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 satisfied: why would there even exist a 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 classifier 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 a storage overhead and potentially privacy concerns. This is a 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 a continual stream of environments), and it be would prohibitive to store it for later fine tuning. The number of features is 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 a good set of features exist, we design an efficient algorithm, named doubly projected gradient descent, or DPGrad, that has a good accuracy on all environments, and resists catastrophic forgetting. Our algorithm, while being novel, bears some resemblance to a class of projection-based algorithms used in practice [11,5] -we hope the theoretical analysis can shed insight onto large scale continual learning.

2 Our results

Problem formulation

In a continual learning problem, the learner has sequential access to k environments. In the i-th (i 2 [k]) environment, the data is drawn i.i.d. from the underlying distribution D i over R d ⇥ R, denoted as (x, y) ⇠ D i , where x 2 R d is the input and y 2 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 : R d ! R r that maps the input data x 2 R d to a low dimensional representation R(x) 2 R r (r ⌧ d), along with a sequence of task-dependent linear classifiers (also known as linear prompts) v 1 , . . . , v k 2 R r on top of the representation. Precisely, the prediction of the i-th environment is made by f

As this is the first-cut study, we focus on the realizable and the proper learning setting. 1 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 v 1 , . . . , v k such that for any i 2 [k] and any data (x, y) ⇠ D i , y = hv i , R(x)i (realizable). The learner is required to output a function R that belongs to the hypothesis class H (i.e. 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 note there is also empirical research focusing on unknown environment identity, which would be an interesting direction for future work (See Section 7).

The guarantee that we wish our learning algorithm to obtain is as follows: Definition 2.2 (Goal of Continual Learning). Let d, k, r 2 N, r ⌧ d, k, ✏ 2 (0, 1/2). Let H be a function class in which the feature mappings from R d to R r lie. The continual learning problem involves k environments D 1 , . . . , D k . We assume there exists a function R ?

2 H and a sequence of linear classifiers v ? 1 , . . . , v ? k 2 R r such that for any (x, y) ⇠ D i (i 2 [k]), the label satisfies y = hv ? i , R ? (x)i. The continual learner has sequential access to environments D 1 , . . . , D k , as well as access to arbitrarily many samples per environmentfoot_3 . The goal is to learn a representation function R 2 H and a sequence of linear prompts v 1 , . . . , v k 2 R r that achieve a good accuracy on the current task and do not suffer from catastrophic forgetting. Formally, in the i-th environment (i 2 [k]), the learner optimizes the feature mapping R and the linear classifier v i (without changing v 1 , . . . , v i 1 ) and aims to satisfy

• Avoid catastrophic forgetting: During the execution of the i-th task, the algorithm guarantees that

 ✏ for all j = 1, . . . , i 1,

• Good accuracy on the current task: At the end of i-th task, the algorithm guarantees that

For linear feature mapping, the representation function can be written in a linear form R(x) = U > x for some U 2 R d⇥r , and it implies the i-th environment is generated by a linear model. That is, defining

3 (The benefit of continual learning with linear feature). Note, for linear features, it's in principle possible to just learn a sequence of linear classifiers w 1 , . . . , w k 2 R d separatelywithout learning a low-dimensional featurizer. Choosing an r-dimensional featurizer confers memory efficiency (O(kr + dr) vs. O(dk)) and sample efficiency (O(r) vs. O(d) samples per task in the asymptotic regime k ! 1). Furthermore, the linear case is a sandbox that can be mathematically analyzed and can generate insights for the nonlinear case as well.

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 1), which is an efficient gradient based method and provably learns the representation while avoids catastrophic forgetting. Towards stating the result, we make a few technical assumptions. Assumption 2.4 (Distribution assumption). For any i 2 [k], we assume D i has zero means and it is in isotropic position, that is,

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 2 [k], w i has bounded norm, i.e., kw i k 2  D. Assumption 2.7 (Signal assumption). For any i 2 [k], let W i = span(w 1 , . . . , w i ), W i,? be the space perpendicular to W i and P Wi , P W i,? be the projection operator. We assume either w i belongs to

Remark 2.9. The Range and Signal assumptions are standard in the statistical learning literature. The former ensures an upper bound on kw i k 2 and the later ensures that a new task provides enough "signal" for new features. They are used to set up learning rate and number of gradient iterations.

Remark 2.10. The Bit complexity assumption states that w i can be described with a finite number of bits, and is mostly for convenience -namely so we can argue we exactly recover w i -which makes calculations involving projections of features learned in the past cleaner. Since the number of gradient iterations only depends logarithmically on ⌫, one can relax the bit complexity restriction to only approximately recovering the ground truth features up to a polynomially small (in d, k, D, ✏) 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 features). Let k, d, r 2 N, r ⌧ k, d, ✏ 2 (0, 1/2). When the features are a linear function over the input data, under Assumption 2.4 and 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

and at the end of i-th environment, DPGrad ensures

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. Theorem 2.12 (Barrier for Continual learning with non-linear feature). Let k, r 2, d 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 1 1000 -error over all environments with probability at least 1/2,under the feature extraction formalization of Definition 2.2.

Related work

Continual learning in practice The study of continual learning (or lifelong learning) dates back to the work of [36] and it receives a surge of research interest over recent years [15,19,11,5,14,31,34,17,29,39,18]. A central challenge in the field is to avoid catastrophic forgetting [24,23], which the work of [15] observed happened for gradient-based training of neural networks. While there is a large amount of empirical work, we'll 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 `2 regularization to the objective function that penalizes the movement of neural weights. The orthogonal gradient descent (OGD) algorithm from [11,5] 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. [31] introduces experience replay to continual learning. [14] 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 [34] 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,7].

Continual learning in theory

In comparison to the vast empirical literature, theoretical works are comparatively few. The work of [6] characterize the memory requirement of continual learning, when the environment identity is unknown. The works [35,27,1,4] 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 duplicate-andfine-tuning and the feature extraction paradigm have been extensively investigated in the literature, detailed discussions can be found at [7] and we provide a brief comparison. From an algorithmic perspective, learning a weighted combination over a family of representation functions (i.e. the duplicate and fine-tuning) is much easier, as one can always initiates a 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 [4]. 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 overparameterized and contains billions of parameters. It is then formidable to maintain a large amount of the basic models and learn a linear combination over them. We mention several more works that are morally related in Appendix A.

Continual learning with linear feature

We restate our main result for linear feature mapping. When the features are a linear function over the input data, under Assumption 2.4 and 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

and at the end of i-th environment, DPGrad ensures

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 i 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 [11,5].

In more detail, at the beginning of the i-th (i 2 [k]) environment, DPGrad adds Gaussian noise to the feature matrix U and the linear classifier v i , to generate a good initialization for U and v i . Subsequently, we perform gradient descent to both the feature mapping matrix U and linear classifier v i -except 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 i by rounding each entry of Uv i to the nearest multiple of ⌫, 3 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, ⌘ to denote the learning rate, and T to denote the number of iterations for each task. These are all polynomially small parameters, whose scaling is roughly D, d, k

to denote a size n 1 ⇥ n 2 matrix whose entries are draw from random Gaussian N(0, 1). For each i 2 [k], t 2 [0 : T ], denote U i,t to be the feature matrix in the t-th iteration of the i-th environment (after performing the gradient update), denote v i,t similarly. DPGrad includes a projection step at the end of i-th environment, we use U i,end to denote the feature matrix after this projection. We use W i (resp. V i ) to denote the column (resp. row) space maintained at the end of i-th environment. Let W ? ✓ R n be the subspace orthogonal to W and define V ? similarly. Let P W , P V , P W ? , P V ? be the projection onto W, V, W ? , V ? separately.

Algorithm 1 Doubly projected gradient descent (DPGrad)

for t = 1, . . . , T do 7:

end for 11: end for

Analysis

We sketch the analysis of DPGrad and prove Theorem 2.11. Due to space limitation, the detailed proof is deferred to Appendix B. The proof proceeds in the following four steps:

1. The first step, presented in Section 4.2.1, reduces continual learning to a problem of continual matrix factorization and it allows us to focus on a more algebraically friendly objective function.

2. We then present some basic linear-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 a new feature, as reflected in the loss terms and gradient update rules. See Section 4.2.2 for details.

3. In Section 4.2.3, we zoom into one single environment, and prove DPGrad provably converges to a 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.

Reduction

We first recall the formal statement of the problem of continual matrix factorization.

In an continual matrix factorization problem, the algorithm receives w i 2 R d in the i-th step, and it is required to maintain a matrix U 2 R d⇥r and output a vector

The key observation is that running DPGrad on the original continual learning objective (2)

Combining the above observations, it suffices to analyse DPGrad for continual matrix factorization and prove Eq. ( 3) and Eq. ( 4).

Decomposition

We first provide some basic linear algebraic facts about orthogonal decompositions. For any i 2

Let w i = w i,A + w i,B where w i,A 2 W i 1 and w i,B 2 W i 1,? . Note this decomposition is unique. We focus on the case that kw i,B k 2 2 [1/D, D] in the following statements, and the case of kw i,B k 2 = 0 carries over easily. (These the only two cases, per Assumption 2.7). Similarly, let

, where each column of U i,A lies W i 1 and each column of w i,B lies in W i 1,? . (Note, again, U i,A and U i,B are unique.) We further write

, where the columns of U i,2 lie in W i 1,? \{w i,B }. Finally, denote

We summarize decompositions mentioned above, with a few additional observations, in the lemma below: Lemma 4.4 (Orthogonal decomposition). For any i 2 [k] and any t 2 [0 : T ], there exists an unique decomposition of U i,t , w i and v i,t of the form

Here we use column(A), row(A) to denote the column and row space of matrix A, and column(A) 2 W if the column space of A is a subspace of W.

Since U i,A,t remains unchanged for t = [0 : T ], we abbreviate it as U i,A hereafter. We next provide the exact gradient update of each component under loss function b

2 and orthogonal projection. Lemma 4.5 (Gradient formula). For any i 2 [k], the gradient update (after projection) obeys the relations (1)

We perform a similar decomposition to the loss function.

Lemma 4.6 (Loss formula).

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 i,A stores existing features that have been learned, and it remains unchanged during the execution of the i-th environment; it remains to optimize v i,1,t such that U i,A v i,1,t matches w i,A . The second and last loss term quantify the loss on a new feature, wherew i,B is the new feature component, and the matrix U i,2,t can be thought of as random noise. Intuitively, one should hope

x > i,t v i,2,t = 1 and this matches the new component of w i,B . At the same time, one hopes U i,2,t would disappear, or at least, kU i,2,t v i,2,t k 2 ! 0 when t ! 1.

Convergence

For a fixed environment, we prove w.h.p. DPGrad converges and the loss approaches to zero, given the initial feature mapping matrix U i,A is well conditioned. Lemma 4.7. For any i 2

where min (U i,A ) and max (U i,A ) denote the minimum and maximum non-zero singular value of matrix U i,A . After

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 U i,B and linear prompt v 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 a nice initialization position with high probability, and then show linear convergence. 4To be concrete, in the first stage, we prove (1) x > i,t v moves closer to 1, and (2) kx i,t kw i,B k 2 v i,2,t k 2 ⇡ 0. That is, the second loss term of Eq. ( 5) decreases to a small constant while the pairs x i,t , v i,2,t remain balanced and roughly equal up to scaling. Meanwhile, we note U i,2,t is non-increasing, though the last loss term could still increase because kv i,2,t k 2 increases. In the second stage, we prove by induction that kU > i,2,t v i,2,t k 2 and |x > i,t v i,2,t 1| decay with a linear rate (hence converging to a global optimal), and kx i,t kw i,B k 2 v i,2,t k 2 ⇡ 0.

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 wellconditioned and (2) catastrophic forgetting does not happen. For (1), we need to analyse the limiting point of DPGrad (there are infinitely many optimal solutions to Eq. ( 3)), make sure it is well-balance and orthogonal to previous row/column space. For (2), we make use of the orthogonality of DPGrad.

Proof Sketch of Theorem 2.11. Thanks to the reduction established in Section 4.2.1, it suffices to prove Eq. (3) and Eq. (4). For each environment i (i 2 [k]), we inductively prove (1) DPGrad achieves good accuracy on the current environment, i.e., kU i,T v i w i k 2  ✏⌫; (2) The feature matrix U i remains well conditioned, i.e.

When w i,B = 0, one can prove the feature matrix does not change, i.e, U i,end = U i 1,end ; when w i,B 2 [1/D, D], then one can show

), the feature matrix U remains well-conditioned. The last claim can be derived from the orthogonality. This wraps up the proof of Theorem 2.11.

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 a (proper) continual learner. We restate the formal statement. The detailed proof are deferred to Appendix C. Theorem 2.12 (Barrier for Continual learning with non-linear feature). Let k, r 2, d 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 1 1000 -error over all environments with probability at least 1/2,under the feature extraction formalization of Definition 2.2.

Our lower bound is constructed on a simple family of two-layer convolutional neural network with quadratic activation functions. The input distribution is assumed to be uniform and the target function is 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 a wrong optimum solution is picked, when the second environment is revealed, the non-linearity makes it impossible to switch back-and-forth.

Proof Sketch. It suffices to take k = 2, d = 3, r = 2 and we sketch the construction here. For both environments, we assume the input data are drawn uniformly at random from B 3 (0, 1), where B 3 (0, 1) denotes the unit ball in R 3 centered at origin. The hypothesis class H consists of all two-layer convolutional neural network with a single kernel of size 2 and the quadratic activation function. That is, the representation function is parameterized by w 2 R 2 and takes the form of R w (x) = (hw, x 1:2 i 2 , hw, x 2:3 i 2 ) 2 R 2 , where x 2 R 3 , x i:j 2 R j i+1 is a 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 f 1 of the first environment is f 1 (x) = x 2 2 ;

(2) The objective function f 2 of the second environment equals f 2 (x) = x 2 3 with probability 1/2, and equals f 2 (x) = x 2 1 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/1000-error on both environments with probability at least 1/2.

Though our lower bound instance uses a polynomial activation function, this assumption is not essential -in Appendix C, we prove similar lower bounds with a ReLU activation function.

Experiments

For linear feature functions, we perform simulations on a 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, k = 500 and the ground truth U ? , V ? is drawn from Gaussian. The input data are sampled from N (0, I d ) and we draw 1000 samples for each task. Additional details about the setup can be found in Appendix D. Moreover, in Appendix E, 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 a modification suitable for multi-class classification, the other is a modification suitable for non-linear featurizers. Detailed numbers and figures can be found in Appendix E. In brief, both 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 a high level across tasks.

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 an 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. It would be thus interesting to investigate what are the fundamental memory-accuracy trade-offs.

(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're using/curating? [N/A] (e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content?