Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
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. 
However, 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.
I 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).
In 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.

[1] “Optimal Continual Learning has Perfect Memory and is NP-HARD” , Jeremias Knoblauch, Hisham Husain, Tom Diethe

questions: q1) What reasons would you give that this paper provides an important step forward?
q2) How would you compare your results in section 5 to the conclusions drawn in [1]?
q3) On line 338, do you mean “r=3” instead of “n=3”?

limitations: I did not find a discussion on the limitations of the current findings.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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. 
They 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. 
The 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.
strengths_and_weaknesses: Strengths: 
* 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.
* The paper is well written, with a clear structure and easy to follow. 
* Looking at the problem from a feature extractor point of view is quite intuitive for the supervised setting that is the focus here. 
* The analysis of the linear case is very detailed and clear, and the results in this case are sound and interesting. 

Weaknesses: 
* 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. 
* 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. 
* 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. 
questions: I think the paper can be stronger by clarifying certain points. 

- 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? 

- 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? 

- 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? 

limitations: The paper is mostly theoretical, and a study of societal impact seems out of scope here. 
The 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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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. 

strengths_and_weaknesses: Strengths:

- 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).


Weakness:

While 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:

- 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.
- 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? 
- 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. 
- 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? 
- 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?  



questions: As mentioned in the main review.
limitations: As mentioned in the main review.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
DPGrad is compared with SGD and OGD on a simulated environment.
strengths_and_weaknesses: Strengths:
* The paper rigorously defines the setting and assumptions before introducing the new solution
* 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.

Weaknesses:
* 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.
* 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.
* 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.
* 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.
questions: * It would be great if the authors could provide more empirical evidence of the performance of their algorithm (maybe on standard benchmarks)
* See the other points in the paragraph above.
limitations: --
review_title: null

Meta-review: metareview: This paper provides a theoretical analysis of continual learning when the learner is modeled as a featurizer followed by a linear head. The analysis provides theoretical guarantees on learnability when the featurizer is linear, and is learned using doubly projected gradient descent. The guarantee ensures good accuracy on all environments and resilience to catastrophic forgetting. For a nonlinear featureizer, it is shown that continual learning is not possible in general: there exist scenarios that even when good features exist, either catastrophic forgetting or poor performance has to occur.

Reviewers raised questions about the implication of the theory for practical settings (s7RD, KsmC about how useful the results are in practice, cwgv on whether current analysis based on quadratic activation functions can carry over to ReLU, and VAS6 about whether the analysis works for classification as well [instead of regression]). The authors responded to these. They highlighted  how the algorithm in the linear setting provides an insight into Orthogonal Gradient Descent (OGD), which is known algorithm for continual learning. Authors also explained the significance of the lower bounds for understanding what is fundamentally possible and impossible in continual learning. Moreover, the authors clarified that quadratic activation is not essential for the lower bound, and extended their proof to ReLU in the revised version of the submission. The authors also clarified that classification could be treated as a special case of regression, with target values being discrete, and hence the result is not limited to regression only (although I, the AC, add that for classification, L2 loss is less common, and by classification, we typically refer to loss functions like cross-entropy, but the results of the paper are interesting regardless).

Final scores are all on the accept side, indicating reviewers have found the contributions strong enough for the submission to be published. In concordance, I think this paper provides very interesting insights about some fundamental aspects of learnability in continual settings.

confidence: Certain
Decision: Accept