The Joint Effect of Task Similarity and Overparameterization on Catastrophic Forgetting — An Analytical Model

We thank the reviewer for their comments and we are glad that the reviewer generally found our results interesting.

However, there seems to be a misunderstanding regarding the scope of the paper. The reviewer wrote in their summary that we “uncover a pattern in overparameterized models where intermediate task similarity leads to the most forgetting”. This is true but it is only a part of our paper.

Generally, our paper is the first to reveal a nuanced analytical interplay between overparameterization and task similarity, and show that overparameterization alone is not enough to understand catastrophic forgetting (in contrast to a current line of continual learning empirical papers which only focuses on the benefits of overparameterization). Our Theorem 3 and Figure 3 clearly demonstrate this.

Moreover, in Weakness 4 the reviewer wrote that they believe that Goldfarb and Hand (2023) already addressed a similar research question.
We have to respectfully disagree, since there are important differences between our work and theirs, which we have already thoroughly discussed in multiple places in our paper (e.g., in the Introduction, Learning Dynamics of Section 2.2, and in the Simulations of Section 2.4). Specifically, Goldfarb and Hand (2023) only study the effect of overparameterization without considering any notion of task similarity. They analyze the regime of low task similarity, i.e., applying completely random transformations to the first data matrix ($\alpha=1$), while our main result analyzes the full spectrum of task similarity from $\alpha=0$ to $1$.
Additionally, that paper uses restrictive data assumptions and provides an upper bound on performance, while our work does not assume any particular data model and our main result is an exact expression for expected forgetting.

As to the more minor comments,

• Weakness 3 & Question 1:

The proof is difficult to follow.

Response: Deriving exact expressions for our analysis was indeed difficult and required 60+ pages of complicated proofs. We originally tried to make our proof’s idea accessible using the Proof Sketch that appears right after Theorem 3.
Following the reviewer’s comment, we will further revise the manuscript and add an entire page presenting a Proof Outline in a new appendix for the final version (this requires a lot of time and we want the reviewers-authors discussion to start in the meanwhile).

• Weakness 2:

Format in Assumption 1 seems incorrect since there is a long blank.

Response: The long blank was not a mistake but a styling choice (using \hfill). We now removed this blank to avoid confusion.

If we have adequately addressed the reviewer's concerns, we kindly ask the reviewer to consider raising their score. If there are any remaining concerns, please let us know.

We appreciate the reviewer's comments and are pleased that they recognize the value and contribution of our findings to the continual learning literature.

Below we address their questions:

• Question 1:

Is the conclusion proved to be universal (for non-linear complex neural networks)?

Response: Our rigorous analysis directly applies to linear regression models. Empirically, we verified our analysis’ validity on linear models and showed evidence that our findings can explain some behaviors observed in MLPs trained on continual permutation benchmarks.
Extending our analysis to similar continual settings in more complex networks should be very interesting, but will probably require more intricate analytical tools.
Existing theoretical results in CL mostly deal with simple models, and there are still very few analytical results on more complex models. We believe that in order to derive results for more complex models, the community must first thoroughly understand the simpler ones (e.g., linear models). Now that we’ve established an interplay between task similarity and overparameterization in linear models, the community can concentrate on extending it to more complex models (e.g., MLPs or CNNs).
We now added this as a future direction in the “Future work” section of the revised manuscript.

• Questions 2&5:

Pixel shuffling is the only current knob for dissimilarity in the experiments, which does not match real world scenarios. Can the same experimental conclusions be reached for other complex datasets?

Response: We hypothesize that the true effect of task similarity comes from similarity in the NTK feature regime as presented in Appendix A. Pixel shuffling is just one proxy for which to generate the desired effect in the NTK feature regime but the relationship between experimental setup and the NTK features is a complex one. We leave the full uncovering of this effect for future work (we mention this in the “Future work” section of the revised manuscript).

• Question 3:

Is overparameterization equivalent to learning capacity?

Response: Overparameterization is related to learning capacity but is not equivalent. Any model that surpasses the complexity of the interpolation threshold has an equal capacity to fully fit to the training set. However, more overparameterized models enjoy the beneficial properties of smoother optimization landscapes and sometimes more favorable generalization properties.

• Question 4:

Can we explain Pseudoinverse Properties and Operator Norm Properties in detail?

Response: The pseudoinverse property that we used in Equation (4) is that for any matrix $\mathbf{X}$ and an orthogonal matrix $\mathbf{O}$, it holds that $\mathbf{X}=\mathbf{X}\mathbf{X}^{+}\mathbf{X}$ and $(\mathbf{X}\mathbf{O})^{+}=\mathbf{O}^{+}\mathbf{X}^{+}=\mathbf{O}^{\top}\mathbf{X}^{+}$. The operator norm property refers to $\Vert\mathbf{X}\mathbf{v}\Vert\le\Vert\mathbf{X}\Vert\Vert\mathbf{v}\Vert$.
To improve readability, we now added these explicitly within Equation (4) and underneath it.

We again thank the reviewer for the feedback.
If we have adequately addressed the reviewer's concerns, we kindly ask the reviewer to continue supporting our submission.
If there are any remaining concerns, please let us know.

We thank the reviewer for their valuable feedback, and we are glad that they appreciate our work.
Below we address the reviewer's concerns

• Question/Weakness 1:

It seems weird to have the same y for two different tasks.

Response: This is due to our analysis being analogous to the data permutation task benchmarks of continual learning. These tasks are especially amenable to analysis as they are each equally difficult for an MLP to solve. Thus we can fairly compare their accuracies and forgetting between tasks.
More generally, many practical continual learning scenarios are subject to domain shifts (e.g., sees another “region” in $\mathcal{X}$), without changing the output space $\mathcal{Y}$.

• Question/Weakness 2:

There is some gap between the theory and MNIST experiments (training loss vs. test error; regression vs. classification).

Response: We view the present work as an initial result in understanding the relationship between task similarity and forgetting. Nonetheless there are still clear analogies between the analysis and experiments of our work. The permutation task setting is a variant of the DOTS model where random permutation matrices are used instead of random orthogonal matrices. In continual learning practice, training error and test error are strongly correlated: when forgetting is observed in the test error then it is also observed in the training error. Additionally, studying training error allows us to loosen the data assumptions of prior work (Goldfarb, Lin) to give better insight into the problem’s worst-case performance. Regression and classification problems are also closely related. One can turn the MNIST experiments into a one-hot regression problem and expect to observe the same effects as in the classification problem.

• Question 3: Is there any deeper connection between the bound in the highly overparameterized regime, $\alpha^2 (1-\alpha)^2$, and the corresponding bound in Lemma 9 of Evron et al. (2022) for the case ?

  Response: There is indeed a deeper connection! Given no task-repetitions ($k=2$), the result from Evron et al. (2022) yields a forgetting upper bound of $\frac{1}{2} \max_{i} \{ \cos^2 (\theta_i) (1-\cos^2 (\theta_i)) \}$, where $\theta_i$ are the nonzero principal angles between the solution subspaces of the two tasks (here, they are equivalent to the principal angles between the data itself; you can see Claim 19 in their paper).
  This expression is of course very similar to our overparameterized results, i.e., $\alpha^{2}(1-\alpha)^{2}=\left(\frac{m}{p}\right)^{2}\left(1-\frac{m}{p}\right)^{2}$.

  Trying to explain this very briefly and intuitively: When $m=0$, our random transformation $**O**$ (applied to $**X**_1$ to create $**X**_2$) is a deterministic identity operator. This, of course, yields principal angles of $0$ between tasks, incurring no forgetting.
  When $m=p$, the random transformation becomes completely random, and since we assume high overparameterization, it means that the two subspaces are going to be almost orthogonal w.h.p. (i.e., have angles of $90^{\circ}$, again incurring no forgetting.
  To understand $m=\frac{p}{2}$, it is perhaps easy to imagine two random lines in $2$ dimensions. In this case it is known that the expected angle between them should be $\approx 45^{\circ}$, which corresponds to the highest forgetting in Evron et al. (2022).

  Following this review, we have now incorporated a similar discussion (on a slightly different aspect) in our “Geometric interpretation and Comparison to Evron et al. (2022)” paragraph in the discussion of the revised manuscript. We believe that it helps see deeper connections like the one that the reviewer noticed.

• Question 4:

Is there a geometric proof that achieves the same result as our algebraic calculations (randomness of principle angles)?

Response: This is a good question. Following the discussion here and with reviewer TGNt, and the discussion we’ve added to the manuscript, it is apparent that geometric reasoning is indeed partially possible here. Specifically, analyzing worst-case expected forgetting should be related to the largest principal angle between 2 random subspaces (see, e.g., “On the largest principal angle between random subspaces”, 2006). However, there should be important differences, requiring different proof techniques. Specifically, our analysis allows for the entire range of $m$ (number of directions/pixels that we rotate), while the aforementioned other paper requires the two subspaces to be completely random. Thus, it seems like they can only help analyze the $m=p$ case.

We again thank the reviewer for the feedback.
If we have adequately addressed the reviewer's concerns, we kindly ask the reviewer to continue supporting our submission.
If there are any remaining concerns, please let us know.

We thank the reviewer for their valuable feedback, and we are glad that they found our paper novel and theoretically sound.

Below we address some of the reviewer's concerns,

• Weakness:

It is unclear how DOTS can compare with the notion of similarity in related works.

Response: In our linear regression setting, the existing similarity notion most comparable to our DOTS should be the principal angles between the solution subspaces of the two data matrices ($\mathbf{X}_1,\mathbf{X}_2$)}, which were used to quantify task similarity in Doan et al. (2021) and Evron et al. (2022). We elaborate on this further here below, and in the discussion in our revised manuscript.

• Question 1:

Is the theory able to provide worst-case forgetting analysis with more general dataset assumption, or T>2 datasets?

Response: These are important questions and we added the following discussion to a new section on “Limitations and Future work” in the revised manuscript. Our analysis has primarily examined settings with $T=2$ tasks. Extending these analytical results to $T\ge 3$ tasks poses an immediate challenge. The complexity of our analysis, which already required intricate techniques and proofs, suggests that tackling this extension may be considerably difficult. Moreover, the convergence analysis presented in a previous paper (Evron et al. 2022) for learning $T\ge 3$ tasks cyclically has proven to be notably more challenging than that for $T=2$ tasks, and was further improved in a follow-up paper (Swartworth et al. 2023).

• Questions 2&3:

How does DOTS relate to other notions of similarity in prior work? Is there a contradiction to Figure 3 in Evron et al. (2022)?

Response: We thank the reviewer for this interesting question!
Evron et al. (2022) showed analytically that intermediate task similarity (a principle angle of $45^{\circ}$) is most difficult in two-task linear regression.
Their analysis applies to any two arbitrary tasks, and thus seemingly contradicts the behavior observed, e.g., in our Figure 1(b), where maximal dissimilarity is most difficult.
The key to settling this apparent disagreement is the randomness of our transformations.
Their analysis focuses on any two deterministic tasks, while our second task is given by a random transformation of the first, as done in many popular continual learning benchmarks (e.g., permutation and rotation tasks).

For simplicity, instead of the case that the reviewer mentioned, where $d=p-1$, let us focus on $d=1$ (in two tasks these are almost equivalent; see Claim 19 in Evron et al. (2022)).

To gain a geometric intuition, consider two tasks of rank $d=1$ ($\mathbf{x}_1, \mathbf{x}_2$). Consider also a maximal DOTS proxy for task dissimilarity ($\alpha=\frac{m}{p}=1$), i.e., $\mathbf{x}_2 = \mathbf{O}\mathbf{x}_1$ is simply a random rotation of $\mathbf{x}_1$ in $p$ dimensions. It is known that $\mathbb{E} \big| \big\langle \frac{\mathbf{x}_1}{\Vert{\mathbf{x}_1}\Vert}, \frac{\mathbf{x}_2}{\Vert{\mathbf{x}_2}\Vert} \big\rangle \big| \approx \frac{1}{\sqrt{p}}$. Near the interpolation threshold, \eg when $p= 2$ (recall that $d=1$), we get that ${\mathbb{E} \big| \big\langle \frac{\mathbf{x}_1}{\Vert{\mathbf{x}_1}\Vert}, \frac{\mathbf{x}_2}{\Vert{\mathbf{x}_2}\Vert} \big\rangle \big| \approx \frac{1}{\sqrt{2}}} \Longrightarrow {\mathbb{E}\angle(\mathbf{x}_1,\mathbf{x}_2) \approx 45^{\circ}}$, corresponding to the intermediate task dissimilarity in Evron et al. (2022), where forgetting is maximal. On the other hand, given high overparameterization levels ($p\to\infty$), we get that ${\mathbb{E} \big| \big\langle \frac{\mathbf{x}_1}{\Vert{\mathbf{x}_1}\Vert}, \frac{\mathbf{x}_2}{\Vert{\mathbf{x}_2}\Vert} \big\rangle \big| \approx \frac{1}{\sqrt{p}} \to 0} \Longrightarrow {\mathbb{E} \angle(\mathbf{x}_1,\mathbf{x}_2)\to 90^{\circ}}$, corresponding to the maximal task dissimilarity in Evron et al. (2022), where forgetting is minimal.

We originally compared our results to Evron et al. (2022) in the discussion section. Following the reviewer’s question, we included the discussion above in the revised manuscript to further elaborate on these aspects.

We again thank the reviewer for the feedback.
If we have adequately addressed the reviewer's concerns, we kindly ask the reviewer to continue supporting our submission.
If there are any remaining concerns, please let us know.

We thank the reviewer for their comments on our paper, and we are glad that they found our results interesting.

Unfortunately, there seem to be several misunderstandings that perhaps interfered with the reviewer’s assessment of our paper. For instance, the reviewer wrote that “in an overparametrized regime, forgetting decreases as the task dissimilarity increases, however, in an underparametrized scenario, the trend is reversed”. However,

• We only analyzed overparameterized models (from the interpolation threshold to a highly overparameterized regime), as seen from Theorem 3 (the rank $d$ is upper bounded by the dimensionality $p$). Underparameterized regimes are practically less common today, and cannot be very interesting under our realizability assumption (since there would only be a unique solution and there would be no place to discuss the bias incurred by continual learning).

• Even in the overparameterized regime, we did not conclude that forgetting decreases as task dissimilarity increases, but rather showed a nuanced non-monotonic behavior (kindly see Section 2.3.1 on the Extremal Cases and Figures 2 and 3).

Importantly, we believe that our paper serves as an analytical counterexample to the findings of several previous empirical papers, which concluded that overparameterization always mitigates forgetting. Specifically, we use our model to demonstrate that, and even if we take overparameterization to the extreme, we can still have a considerable amount of forgetting (and it does not necessarily decay to zero), e.g. when $\alpha=1-\frac{m}{p} = 0.5$. We believe that it is more convincing that we were able to find this counterexample even in the simplest model of linear regression and in a simple-yet-standard data model. This suggests that more complex models probably also have a nuanced behavior with regard to overparameterization, though not necessarily exactly the same behavior.

To enhance clarity, we revised the manuscript and incorporated a brief discussion in Section 2.3.2, just before Figure 3. Additionally, we explicitly highlighted this aspect in the contribution list within the introduction.

The reviewer also asked (Q2,Q3) whether we tried to evaluate our upper bound “in more challenging scenarios” (e.g., CNNs) or with different notions of task similarity. The answer is that we did not, but neither did we claim that our analysis simply extends to such cases. For example, permutation benchmarks like the one we aim to characterize, are not very suitable for CNNs, since the permutations significantly interfere with the spatial assumptions convolutional models implicitly make (shift-equivariance of representations and shift-invariance of the classification).
Again, our aim is that our analysis can be used as a counterexample to the practical common belief that overparameterization always mitigates forgetting and as a demonstration of a more nuanced interplay between overparameterization and task similarity. More generally, when doing theoretical research, we believe that one must start from the simplest models as we did, before addressing more complex scenarios as the reviewer rightly suggested.

Following this discussion, we now include these suggestions in the "Future work" section at the end of our revised manuscript.

If we have adequately addressed the reviewer's concerns, we kindly ask the reviewer to consider raising their score. If there are any remaining concerns, please let us know.

We thank the reviewer for the thorough and helpful review. Below we address the weaknesses the reviewer has pointed out and also answer all the questions. We believe that the changes made following the discussion below, helped to improve our paper significantly.

• Weaknesses 1&2 and Questions 1,2,3:

What is the exact optimization scheme to which our results apply (algorithm, batch size, learning rate)? The model and algorithm are not stated in the introduction. Which theorem from Gunasekar et al. is used.

Response: We apologize about the lack of clarity on the aspects mentioned by the reviewer. Below we address these questions and specify how the revised manuscript clarifies them.

We study the simplest continual learning procedure - starting from a zero initialization $**0**_p$ and iteratively minimizing the current task’s loss using (S)GD initialized with the previous task’s solution. In each iteration, we assume that learning “converges” to the limit solution, obtained by (S)GD with any batch size (as long as the learning rate is small enough; see Section 2.1 in Gunasekar et al. (2018)). This is a similar procedure to the one studied in several analytical papers (e.g., Evron et al. (2022); Goldfarb and Hand (2023)).

As can be seen in our revised manuscript, we now (1) specifically mention that we study an (S)GD scheme in the introduction; (2) changed the title of Section 2.2 to “The Analyzed Learning Scheme and its Learning Dynamics”; (3) specifically write before Scheme 1 that this is the scheme that we analyze; (4) added a footnote to the analytical iterates, explaining that any batch size can be use as long as the learning rate is small enough; (5) highlight right after the scheme that we do not actually compute pseudoinverses; (6) and finally, specifically refer to Scheme 1 in our main Theorem 3.

• Weakness 3: The analysis focuses on the dimensionality and overlap with respect to the manifold of the data distribution, which should not be confused with the overparameterization of deep networks.

  Response: We agree with the reviewer and we added this to the “Limitations and Future work” section in our revised manuscript.

• Weakness 6:

Unsure if permuted MNIST is suitable to study changes in task similarity that are comparable to DOTS. Vanilla MNIST is on a very low dimensional manifold. I would prefer a simulation study that uses artificial data.

Response: The permuted MNIST experiments are intended to illustrate the ideas of the analysis in a more realistic image classification scenario. Note that the permuted image setting is an analogous version of the DOTS simulation where random permutation matrices are used instead of random orthogonal matrices. We recognize that MNIST images lie on a low dimensional manifold and this notion is what motivated our decision in the analysis to have data of low rank d; in this case, low effective dimensionality is a similarity between MNIST and the simulated data.

• Weakness 4: The paper should state explicitly that the analysis is limited to the rich learning scheme. It does not provide any insights into the lazy learning regime.

  Response: We see two possible interpretations of this statement, and we are slightly confused by both.
  In case the reviewer was referring to our theoretical analysis, we note that we work in the setting of linear regression, in which there is no rich/lazy regime distinction. As far as we are aware, the lazy vs rich distinction applies only to non-linear parameterizations, where the initialization scale qualitatively affects the final solution (e.g., minimizing the L2 norm in "lazy", vs L1 norm in "rich", in the squared linear regression model of Woodworth et al. (COLT 2020)). In contrast, as can be deduced from our Eq. 3, in linear regression, changing the initialization just shifts the final solution location (along a direction orthogonal to the data manifold) — which is not a qualitative change.
  In case the reviewer meant to the application of our linear regression results to neural networks, then, as far as we are aware, the only formal way to prove that linear regression results directly apply to neural networks is to be in a regime where the neural network is approximately linear, such as the NTK regime. Therefore, we only claim our results can be directly applied to neural networks in this case. Perhaps some of our conclusions also apply to the rich regime, but we do not see how this could be theoretically proven.