The other major concern is that it was unclear to the reviewer if accuracy improvements are significant, the reason being:

It seems like the results in the main Table 1 are of a single run per model-dataset combination. No standard deviation is reported. Given that most of the improvements upon RanPAC are somewhat small, it is unclear if these are indeed statistically significant.

Our Reply: Thank you for raising this point. We argue that the results in Table 1 are statistically significant, as it covers various datasets under different settings. Also, note that in Table 1 we use the same random seed and task order and split as prior works, and we use hyperparameters directly from prior works, without taking advantage of tuning them for our method.

Such uniform improvements in the CIL setting (Table 1) are not seen in the follow-up works of RanPAC, many of which have been accepted to top ML/CV conferences. Some prior works have complicated continual learning strategies that still couldn't outperform RanPAC in the CIL setting, indicating that RanPAC is a very strong baseline (see, e.g., Table 1 of Zhou et al. 2024a). It is only in our paper that all comparisons to RanPAC are highlighted with a detailed analysis of why our method works better (Line 159, Line 482).

Furthermore, Fig 5 and Table 2 show that our method is significantly more scalable and more accurate.

On the other hand, we agree that reporting standard deviation is useful as it can better illustrate the strength of our method (e.g., more stable than RanPAC). In Table 16, Appendix L.3, of our revision, we run the same experiments as in Table 2 multiple times, with different random seeds, exposing that RanPAC has huge standard deviations on several datasets.

We hope this gives a refresher view of our algorithmic contributions. Please also take a look at our top post, Thank you for your patience thus far.

Dear Reviewer P9vj,

Thank you for your thoughtful comments. We understand your concerns. We believe they are due to some misunderstandings of our algorithm and motivations. Some misunderstandings arose as we lacked space in the main paper, and the other was caused by slight inaccuracy on our part. However, all these are easy to fix, and we take the opportunity to respond to your comments and justify our method. In our revision, we will make some space (e.g., put Fig 6 in the Appendix) and revise accordingly.

Comment 1: ...the ICL formulations in Line 111 and 116 ... require storing the data from all previous tasks.

Reply 1: While these formulations require access to past data, and similarly in the RanPAC formulation (in Line 124), they admit continual implementations. We chose to state their offline versions for conciseness.

Comment 2: ...the authors assume that $E$ is so large that it makes the entire task sequence feasible (jointly!)

Reply 2: We address it by considering the following two points:

• First, as indicated in the top post, a larger $E$ gives higher accuracy (Fig 8, Appendix K.4). This is a practical motivation rather than a theoretical convenience for ICL to be feasible.
• Second, assuming $E$ is large allows us to review ICL and RanPAC very quickly in a unified manner and with minimum texts and minimum complication.
• Third, our method works for any $E$. Indeed, although the formulations presented in Lines 111, 116, 243 require a large $E$ to be feasible, the computational solutions stated in Eqs. 2 and 4 do not. In particular, when we have $M\_t > E$, the solution $\overline{W}\_t\gets Y_{1:t}\overline{V}\_{1:t}\overline{\Sigma}\_{1:t}^{-1}\overline{U}\_{1:t}^\top$ in Eq. 2 is the solution to the normal equations $W\tau\_{k\_t}(H\_{1:t})\tau\_{k\_t}(H\_{1:t})^\top = Y_{1:t}\tau\_{k\_t}(H\_{1:t})^\top$, which means the offline version of ICL-TSVD would minimize the MSE loss $\\| W \tau\_{k\_t}(H\_{1:t}) - Y\_{1:t} \\|_F$. Therefore, while we agree that ICL is purely theoretical, it is precisely our contribution to propose ICL-TSVD that makes it practical.

Comment 3: Assuming E is too large would practically make the time and space requirements of the proposed method infeasible for most datasets.

Reply 3: If we agree that the case of large $E$ is practically motivated, and that prior methods can't handle it, then it is precisely our contribution to address the computational challenges with large $E$ via a method of complexity $O(E(k\_{t-1}+m\_t)^2)$ per task. We showed on multiple datasets that our method is feasible for $E$ large.

Comment 4: Theorem 1 implicitly requires such extreme overparameterization or that the data can already be explained linearly almost perfectly. Otherwise, ... making the bound uninformative ($\frac{M\_t-k\_t}{M\_t}$ is not small)

Reply 4: We are motivated to consider $E$ large, but the theorems do not assume it. We should have made clear that theorems hold for any $E,M_t$, and any $k\_t\in [0, \min\\{ E, M\_t\\})$, not just for $k\_t=(1-\zeta)M\_t$. The term $\frac{M\_t-k\_t}{M\_t}$ vanishes if $M\_t \to \infty$ and if we only truncate the smallest eigenvalues (and in our experiments, there are just a few of them, which means $M\_t-k\_t=o(M\_t)$); this is when the theorems can be informative.

Comment 5: all that is left to analyze is the error stemming from the truncation. In my opinion, this is not a significant theoretical contribution.

Reply 5: While we appreciate your very high standard for significant theoretical contributions, we'd like to argue the following:

• such analysis is not entirely trivial, in our humble opinion; e.g., the upper bounds have complicated dependencies on quantities such as $a\_t$ and $\gamma\_t$.
• our theory is the first such result, to the best of our knowledge, for truncated incremental SVD (since Bunch & Nielsen,1978), for continual learning with pre-trained models, and for continual principal component regression.
• our contribution is not purely theoretical, and our theory is practically motivated: It analyzes the effects of continual truncation to provide extra insights into our method, as we believe our algorithmic contribution is very strong and improves prior works in many important ways.

Comment 6: ... which implicitly assumes that the smaller singular values are very small, which might not be the case for arbitrary data ...

Reply 6: We agree that our theorems might not be informative for all data. This is inevitable, as the truncation throws away information, and we often need the assumption of large eigengaps in this type of analysis. For us, deriving a theorem that is tight for all data is an ambition; we simply want to truncate the smallest singular values (cf. Fig 1), and our theory just shows that it works.

Please feel free to let us know which part of your major concern 1 remains alive. We'd be glad to have further exchanges.

Question 1: Why do both RanPAC and the proposed method outperform the LC ($H_{1:T}$)?

Answer 1: We checked the test accuracies of LC ($H_{1:T}$) at every epoch. It was no better than the presented results. We trained it for 20 epochs in the presented experiments, and we found the accuracy got slightly worse when we trained it for 30 epochs; this might be some form of early stopping you suggested. A similar phenomenon is shown in Table 1 of the RanPAC paper (https://arxiv.org/abs/2307.02251) for LC ($X_{1:T}$), called joint linear probe in that table.

The plausible explanation is that SGD (with decreasing stepsizes) only finds the exact global minimizer as the number of iterations tends to infinity, while RanPAC and ICL-TSVD find it in closed-form. Another factor to consider is that we used the cross-entropy loss for SGD, while RanPAC and ICL-TSVD have MSE losses. It is not clear how the two losses would compare beyond Remark 2. (We tried MSE losses for SGD, and the accuracy was very low after running more than 20 epochs.)

Question 2: In Figure 4a, what is going on with the scaling of the x-axis? What was the maximal truncation percentage that you examined? I would expect seeing a sharp decrease at the for high values, but it is not apparent. Moreover, why can we truncate so much without losing performance even though the eigenvalues do not decrease so quickly (as seen from Figure 1a)?

Answer 2: There is no issue with the x-axis; we tested a range of truncation percentages from [0%,90%], and for clarity, we only reported the results for [0%, 5%, 25%, 50%, 90%] in Fig 4a.

This figure shows that, as we truncate more, the method runs faster without sacrificing the accuracy too much. We hope this convinces you that the complexity of time and space can be very low by controlling the truncation percentage. In RanPAC, there is no such control, and its implementation has $O(E^3)$ complexity.

Actually, the eigenvalues do decrease very quickly as per Figure 1a (and this is perhaps why the test accuracy is not affected too much):

• There are a few very small eigenvalues of order $10^{-5}$; they're likely due to numerical errors, and they might have just been $0$ if we could compute the exact SVD.
• There are just a few top eigenvalues (of order $10^{11}$), and they quickly decrease to much smaller values $10^{6}$; we believe the eigenvalues of order $10^{6}$ are the actual tail of the spectrum. Also note that the effective rank (or stable rank) is just 2 or 3 (cf. Fig 9a, Appendix K.5).

Minor Concerns: Thank you very much for all the details. We understand them, and we agree with the comments to a great extent. We will address all of them after the decisions are made or in the next public version of our manuscript. Please understand that, like all ICLR authors, we are running busy and crazy with the rebuttal.

Finally, we address the last comment:

I do not feel like it says a lot more than classical results for stationary settings (where removing insignificant directions incur a loss defined by the truncated singular values).

We note that we are addressing the continual learning case, where we do not maintain the past data and we have minimum assumptions. In this case, there is no hope of getting a result stronger than what the "classical results for stationary settings" can suggest. However, our theorems precisely capture the effects of continual truncation (which is unknown previously), in such a way that:

• the bound of the training MSE loss is zero if we do not truncate;
• the bound of the generalization MSE loss coincides with Huang et al. (2022) in the offline case (a single task) under their exact assumptions. This result of Huang et al. (2022) is more recent than classic.

In retrospect, the information you already got from the theorem is that the continual truncation would perform comparably with the offline static case if we truncate insignificant directions. This is previously unknown. We proved it.

Why is such a result, then, a major concern rather than a nice, novel contribution where we can recover the classical results for stationary settings with a more general result for continual truncation?

Respectfully, we invite you to consider the following two analogies:

• In continual learning practice, researchers will be very proud if their method has similar accuracy to the static baseline (i.e., joint training).
• gradient descent for convex smooth optimization has (unaccelerated) convergence rate $O(1/k)$ where $k$ is the number of iterations. This result has been known for decades. Many papers, including several seminar works, have been published to show that gradient descent variants (e.g., coordinate descent methods [1,2]) have a convergence rate of $O(1/k)$. If we were to apply your standard and your argument, all these subsequent works would be rejected as they are not valuable enough for ICLR: the proved bound on the convergence rate didn't say too much beyond the $O(1/k)$ rate we already know about gradient descent. But we hold a different view. We appreciate that these methods are different from gradient descent, and in fact generalize it. In our case, we analyze a continual learning method, different from an offline method, and obtain a result that generalizes the bounds in the offline case or the case of truncating only once.

We are truly truly confused. We look forward to your reply so we can find a common ground.

[1] Yu. Nesterov, Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems (https://epubs.siam.org/doi/10.1137/100802001)

[2] Amir Beck and Luba Tetruashvili, On the convergence of block coordinate descent type methods (https://epubs.siam.org/doi/abs/10.1137/120887679)

Thank you for the follow-up comments on the experimental part.

1. Table 16 is a good improvement upon Table 2. Why not simply updating Table 2?

• We wanted to keep the original manuscript untouched so that the reviewers and ACs have better access to the original version. We will, of course, replace Table 2 with Table 16, after the decisions are out or in our next revision.

2. I am not sure why the authors insist on not adding STDs to Table 1. I was not convinced by their response that such an addition is methodologically unnecessary.

• We are not resisting it. We do agree that having standard deviations shown is important; this is why we have run Table 16.
• We had concerns that Table 1 is too large to include more details. Also, the experiments would take a lot of time as many methods are slow (everybody was running experiments for the rebuttal, and we had limited GPU resources). Our plan was to revise Table 1 in the next major revision.
• That being said, we still have two days to respond; please stay tuned, and by Nov 27, we will at least include a comparison between RanPAC and our method with standard deviations under the same setting as in Table 1.

I have read the authors' long response.
However, I do not believe it answers my Major Concern in the original review.

Specifically,

1. The authors make an effort to convince me that the proposed method is feasible for diverse regimes of $d, E, M_t$, but this is not my concern; I do not doubt the feasibility of the proposed method nor its reported empirical success.

2. I do doubt that the connection to ICL adds anything meaningful to the paper and to the empirical success of the method.
   As I explained in my review, I find Theorem 1 informative only when $\Vert \mathcal{E}_{1:t}\Vert$ is small (which holds information only about the data, not the algorithm).
   In such cases, where the labels are approximately explained linearly by the data, line 7 in the algorithm essentially says "we construct the solution using a (sequentially-built) low-rank approximation of the (left-)singular values of the 'accumulated' feature matrix of all tasks seen so far". For linear data this is reasonable and very straightforward since it approximates a perfect solution so far, but I do not see what we learn from "linking" it to ICL.
   Moreover, the first term in the theorem simply says "if we throw away only insignificant directions it will incur a low loss". I do not feel like it says a lot more than classical results for stationary settings (where removing insignificant directions incur a loss defined by the truncated singular values).
   I do not believe that my standard here is "very high".

3. The authors also mentioned that their "upper bounds have complicated dependencies on quantities such as $a_t$".
   Do the authors find $a_t$ to be an informative quantity?

4. Coming to think of it again, all of this sounds closely related to PCA-OGD (Doan et al., 2020) and their proven bounds, which are not discussed at all.

I decided to raise my score to 6.

• The authors agreed to publish the STDs in the next version of the manuscript. This seems important to me since the whole point is that RanPAC is unstable and the improvements of ICL-TSVD upon it are often small.

• I was convinced during the discussion with the authors that I was too harsh in my initial review.

  • Personally I still believe that the connections to ICL are rather contrived and mostly make the presentation cumbersome (I had other remarks in my initial review that the authors promised to address in future revisions). I would have more easily accepted this paper as a short paper focusing mostly on the algorithm itself. However, the authors convinced me that the theory they developed may be interesting for the community and is not trivial. At this point, it seems like a matter of personal taste.
  • I would still recommend refining the messages of the paper, and its (more interesting) perspectives as a sequential truncation methods and PCA-OGD (see next).

• In another reply the authors discussed the relations to PCA-OGD:

  • I find the algorithmic "difference" between the methods to be rather small. The difference between GD and SVD in a linear setting (or layer) is insignificant and often boils down to mere implementation details. However, I do agree now that there are differences in the truncation policies, e.g., since PCA-OGD doesn't store the singular values and applies PCA only to the current task's gradients. This could easily be adjusted to be very similar to ICL-TSVD, but accumulates to a sufficient "delta" that can be considered a different algorithm.
  • I agree that the theorem in the paper reviewed here is easier to understand than in the other paper and is somewhat more elegant.
  • I suggest elaborating on these connections in the updated manuscript (at least in an appendix).

Dear Reviewer P9vj,

Thank you for your time in reading all of our responses and for agreeing with the empirical success of the ICL-TSVD method.

We also thank you for the follow-up interrogations and the opportunity for us to clarify.

For the new concern in relation to PCA-OGD, we kindly refer you to our reply to Reviewer XHQX. There, we discussed PCA-OGD in detail and how our paper improves it in both theory and practice, which we hope you will appreciate. In fact, given PCA-OGD, we believe we can now better address your concerns.

Let us begin with the comments on $a\_t$:

• By saying that the upper bounds have complicated dependencies on quantities such as $a\_t$, we mean the upper bounds are not trivial to prove. Complicated dependencies on $a\_t$ do not contradict the fact that $a\_t$ is an intuitive and suggestive quantity, as it is just the sum of the maximum eigenvalues continually truncated.
• Comparing our theorems to the corresponding result of PCA-OGD, we hope you would appreciate that we are addressing a more challenging problem (continual truncation, as we explained to Reviewer XHQX), and that our results are much simpler with only two intuitive quantities $a\_t$ and $\gamma\_t$; the corresponding result in PCA-OGD has more than 8 quantities. Similarly, more complicated are the quantities defined in Theorem 3.1 of a recent paper accepted to ICML 2024 (https://arxiv.org/abs/2405.17583).

Next, thank you for agreeing that we can do nothing about the noise term without extra assumptions on data. We now explain the links to ICL from our perspective:

• Reviewer XHQX justified the connection between ICL and the minimum norm solution.
• ICL (with its minimum-norm version) is how we begin to think about the problem, and RanPAC inspires us to consider the network architecture. Sections 2 and 3 introduce them and their instability. There, the links to ICL (and RanPAC) are important as they help develop the story and motivate our approach.
• We name our method ICL-TSVD as its connection to ICL is closer than RanPAC (cf. Lines 116, 242, Eqs 2, 4). It is just a name. We are open to other names.
• Our theorems are proved independently and do not rely on ICL in any way (similarly, PCA-OGD is inspired by OGD, while its theorems do not rely on the OGD method). We mention this to clarify the following point (we somehow overlooked this comment, and maybe this is why we are confused by other comments):

The authors link their method to a theoretical framework (ICL by Peng et al., ICML 2023) ... and use this connection to derive some bounds on the training and generalization error of the proposed algorithm.

Please note that we didn't use the connection to ICL to derive theoretical bounds. (The paragraph at Line 336 is only to give a feeling about the effects of truncation, if that is the source of confusion.)

Given these considerations, we couldn't see how the link to ICL becomes a major concern, as the link does not have any impact on our theory or experimental results, and it only serves together with RanPAC as a motivation to develop our approach. We expect it to be addressed easily by revising the manuscript and rephrasing (if you also think so, please give us more details).

Please let us know whether this addresses your concern and whether you have new ones.

Dear Reviewer iVyo,

Thank you for your time on the paper and the appendices. We appreciate your comments on weaknesses and questions, as well as the deep insights shown there. Our rebuttal takes your comments into full consideration, and we hope it will earn your support for acceptance.

We will revise our paper accordingly based on your comments and our responses. Please feel free to raise any further concerns, and we will be happy to address them during the discussion phase.

Comment 1: ... it remains unclear why authors use $\widetilde{B}\_t:=[\widetilde{U}\_{1:t-1}\widetilde{\Sigma}\_{1:t-1}, H\_t]$ [as defined in Eq. 3], instead of $\widetilde{C}_t:=[\widetilde{U}\_{1:t-1}\widetilde{\Sigma}\_{1:t-1}\widetilde{V}\_{1:t-1}^\top, H\_t]$.

Reply 1: This is a good point that we could have clarified in Appendix C.1. We apologize for the confusion. We address it below:

• First, one might consider maintaining all TSVD factors $\widetilde{U}\_{1:t},\widetilde{\Sigma}\_{1:t},\widetilde{V}\_{1:t}$ and labels $Y_{1:t}$, and forming the classifier $\widetilde{W}\_t\gets Y_{1:t}\widetilde{V}\_{1:t}\widetilde{\Sigma}\_{1:t}^{-1}\widetilde{U}\_{1:t}^\top$ (cf. Eq. 2). Empirically, this gives large test errors, and it is the method we implied in Appendix C.1.
• This led us to the strategy indicated in Eqs 2 and 4, that is to maintain $\widetilde{U}\_{1:t},\widetilde{\Sigma}\_{1:t}$ and form a solution as per Eq. 4. To do so, the first idea is to update TSVD factors using $\widetilde{C}_t$; interestingly, this is mathematically equivalent to using $\widetilde{B}_t$. Indeed, with the QR decomposition $Q\_t R\_t = (I_E - \widetilde{U}\_{1:t-1}\widetilde{U}\_{1:t-1}^\top) H_t$, we have $\widetilde{C}_t= [\widetilde{U}\_{1:t-1}\widetilde{\Sigma}\_{1:t-1} \widetilde{V}\_{1:t-1}^\top,\ H\_t ] = [\widetilde{U}\_{1:t-1},\ Q\_t ] \begin{bmatrix} \widetilde{\Sigma}\_{1:t-1} & \widetilde{U}\_{1:t-1}^\top H\_t \\\ 0 & R_t \end{bmatrix} \begin{bmatrix} \widetilde{V}\_{1:t-1}^\top &0 \\\ 0 & I\_{m\_t} \end{bmatrix}$ Similarly, $\widetilde{B}_t$ equals the product of the first two matrices on the right-hand side. Since the first and third matrices are orthogonal, it suffices to calculate the SVD of the middle matrix on the right-hand side. Since the final classifier in Eq. 4 can be calculated without $\widetilde{V}\_{1:t}$, we could just maintain $\widetilde{U}\_{1:t},\widetilde{\Sigma}\_{1:t}$ and ignore $\widetilde{V}\_{1:t}$. We hope it is clear now.

Comment 2: ICL-TSVD uses $E=100K$ while RanPAC uses its default $E=10K$. It is not so convincing that this is a fair comparison although ... Fig. 8 & Table 13 show that ICL-TSVD does not outperform RanPAC on about half of the datasets.

Reply 2: As indicated in the top post and our answer to your question 2 below, RanPAC is too slow for larger $E$. Here is what we could argue if both methods use the same $E\geq 10000$:

• ICL-TSVD and RanPAC would have comparable accuracy (cf. Fig. 8, Table 13). RanPAC might even have a slight advantage (when it works stably), for two reasons. First, it performs cross-validation, while we simply use $\zeta$=25% without any specific attention paid to tuning it. Second, RanPAC's implementation has less continual learning flavor: It updates covariances $H\_{1:t} H\_{1:t}^\top$ and $Y\_{1:t} H\_{1:t}^\top$ and solves the normal equations $W (H\_{1:t} H\_{1:t}^\top + \lambda\_t I)= Y\_{1:t} H\_{1:t}^\top$ with a selected regularization strength $\lambda\_t$; this is what an offline ridge regression method would solve. By doing so, numerical errors would not accumulate over time, while the issue is that it takes $O(E^2)$ space and $O(E^3)$ time, which makes RanPAC infeasible for large $E$. Given these, we found it remarkable that our online ICL-TSVD implementation has accuracy comparable to an almost offline RanPAC implementation.
• ICL-TSVD is more stable and will outperform RanPAC a lot in CIL with smaller increments (e.g., the setting of Table 2), even with the same $E=10K$.
• ICL-TSVD is up to 1000 times faster for $E=50K$.
• RanPAC runs out of memory for $E=100K$.

Question 1: In Table 2, why the final accuracy of RanPAC on StanfordCars dataset is only 1.19%?

Reply 1: Good question. We explained why RanPAC is unstable and fails in the general case in the post above (Our Algorithmic Contributions and Improvements in Comparison to RanPAC).

Below, we aim to explain why it fails specifically in the case you mentioned.

• First, in Table 2, we are given one class at a time. This means the training set is small for every task $t$, so the validation set of RanPAC is also small. In this case, its cross-validation strategy struggles at choosing a good regularization parameter.
• Then, note that RanPAC chooses $\lambda\_t$ for every task $t$ encountered. A wrongly chosen $\lambda\_t$ would result in nearly zero accuracy on all seen tasks, while the accuracy would recover in the next task, if $\lambda_{t+1}$ is chosen suitably.
• For StanfordCars, RanPAC fails at the last task in the present setting, which makes the 1.19% final accuracy in Table 2. Figure 18 (B-16, Inc-1) plots the full accuracy matrices of RanPAC on StanfordCars, and the blue columns imply failures and nearly zero accuracies on all seen tasks. In particular, note that the last column of that figure is in blue.
• Finally, note that Table 2 only contains a single run of the experiments with a seed given by prior work (default in the code repo). In Table 16, Appendix L.3 of our revision, we show the same experiments with 3 random seeds, and report the mean and standard deviations of the accuracies. In that table, the final accuracy of RanPAC improves, as for some other seeds, it does not necessarily fail at the lat task. However, the table also shows RanPAC exhibits large standard deviations on StanfordCars. We will present the new table instead, in our revision.

Question 2: Figure 5 does not plot the training time for RanPAC when embedding dimension $E=50K,E=100K$, is this because the training process is too slow?

Reply 2: Yes, RanPAC is too slow for large $E$. E.g., it takes more than 20 hours with $E=50K$ on ImageNet-A, while our method takes about 1 minute (RanPAC is similarly slow on other datasets). This was also mentioned in the post at the top.

We hope this clarifies why our comparison with RanPAC is fair, even with different $E$. If both methods use the same $E$, we end up with the conclusion that our method is up to $1000$ times faster, while being more stable with comparable performance.

Question 3: How about the running time of ICL-TSVD compared to other CL baselines, especially those that do not utilize SVD in their implementation?

Reply 3: This was addressed above, together with Weakness 4.

Question 4: For $\overline{W}_t$ and $\widetilde{W}_t$ defined in Eq. 2 and Eq. 4, respectively, is there any theoretical guarantee on $\\| \overline{W}_t - \widetilde{W}_t \\|\_F$?

Reply 4: Beautiful question. The answer is yes, and we provide such a bound in Theorem 7, Appendix L.1 of our revision. Note that the upper bound of Theorem 7 is meaningful and not loose if we truncate at a position $k\_t$ that exhibits large eigengaps. In fact, to get meaningful bounds, it is in some sense necessary to truncate at such a position $k\_t$ that exhibits large eigengaps; for a (remote) counterexample, see, e.g., Section 2.3.2 in the following reference:

[1] Yuxin Chen, Yuejie Chi, Jianqing Fan, Cong Ma, et al. Spectral methods for data science: A statistical perspective. Foundations and Trends® in Machine Learning, 14(5):566–806, 2021. (https://arxiv.org/abs/2012.08496)

Comment 3: (Part 1) The quantities $a\_t$ and $\gamma\_t$ can be large & (Part 2) Gaussian assumptions can be unrealistic, and $\| \Lambda - \frac{1}{M_t} H_{1:t} H_{1:t}^\top \|$ might not converge to $0$ as $M_t \to \infty$.

Reply 3 (Part 1): Indeed $a\_t$ and $\gamma\_t$ can be large, and in this case we need a large $M_t$ to have small upper bounds. This is also why the theory section is titled Provably Controlled Estimation and Generalization, i.e., the upper bounds are controlled by where we truncate. More specifically, we take the following perspectives:

• Our theory is informative in the following sense: the errors are small if we truncate at the position that exhibits a large eigengap and we truncate only small eigenvalues. This suggests we could set $k_t$ by detecting the eigengap and truncating only small eigenvalues. Our theory can provide informative bounds for this strategy. This is nice, as our original motivation is to eliminate the extremely small eigenvalues (cf. Fig 1).
• However, since there are typically just a few such small eigenvalues, this strategy would truncate only a few eigenvalues, while, empirically, truncating more would gain efficiency without affecting generalization too much (Fig 4a).
• Despite these thoughts, we make a simple choice: truncate 25% of them. We believe this is not a big limitation, as we have illustrated the effect of choosing $k\_t$, and in our code (to be released), the user can choose different truncation strategies that fit their needs.

Reply 3 (Part 2): We agree that Gaussian assumptions can be unrealistic, so we didn't use them in the theorem. Next we explain why we mentioned Gaussianity and why this assumption is not necessarily needed in our case:

• We mentioned in the text that $\| \Lambda - \frac{1}{M\_t} H\_{1:t} H\_{1:t}^\top \|$ goes to $0$ as $M\_t\to \infty$ when $H\_{1:t}$ consists of i.i.d. Gaussian vectors and $\Lambda$ satisfies certain boundedness conditions (Koltchinskii & Lounici 2017). This is the simplest possible explanation we know that allows the reader to quickly understand the term $\| \Lambda - \frac{1}{M\_t} H\_{1:t} H\_{1:t}^\top \|$, without getting into any technical details. We believe this would facilitate digesting our theorem.
• On the other hand, we can still guarantee $\| \Lambda - \frac{1}{M\_t} H\_{1:t} H\_{1:t}^\top \| \to 0$ even if the Gaussian assumption on $H\_{1:t}$ is replaced with a much weaker condition called hypercontractivity; see, e.g., [1]. Specifically, assuming every column of $H\_{1:t}$ is an i.i.d. copy of some random vector $h$, the hypercontractivity condition only requires $h$ to satisfy $\sup\_{v:\\|v\\|=1} \\frac{\\mathbb{E}^{1/p}| h^\top v|^p }{ \\mathbb{E}^{1/2}| h^\top v|^2 } <\infty$ for some $p > 4$. We hope it is now clear that Gaussian assumptions are indeed not required in our results.

[1] Jirak et al., "Concentration and moment inequalities for heavy-tailed random matrices" (https://arxiv.org/abs/2407.12948)

Comment 4: Figure 5 shows the comparison of training times for varying embedding dimensions $E$ between ICL-TSVD and RanPAC. How about comparison with other CL baselines in terms of training time? Typically, the computational cost of SVD-type algorithms is large, is ICL-TSVD still faster than other CL methods under the current experimental settings?

Reply 4: This comment relates to the following question and here we address them together.

Question 3: How about the running time of ICL-TSVD compared to other CL baselines, especially those that do not utilize SVD in their implementation?

Thank you for raising this point. We mention the following points:

• First, we justified in the above post that we essentially perform (incremental) low-rank SVD, which makes our method faster than conventional SVD-based methods.
• Then, we note that we didn't compare the running times of other methods in the paper, primarily because our method outperforms them by a large margin and other methods are of different types.
• On the other hand, we are happy to compare the running times with more baselines. This is shown in Table 15, Appendix L.2, of our revision. In that table, our method is shown to be multiple times faster than prompt-based methods (e.g., L2P, CodaPrompt) and adapter-based methods (e.g., EASE). These methods do not utilize SVDs. They are slower as they need to backpropagate the gradients throughout the large pre-trained ViTs for multiple epochs, to train learnable prompts or adapters (with the ViT parameters frozen).

Reply to minor typos: Thank you for reading the manuscript carefully and pointing out the typo. We are now fully aware of it and will make a revision accordingly.

Dear Reviewer XHQX,

We appreciate your comments on the paper's strengths, and thank you for recommending acceptance with a score of 6. We reply to your comments below. Do let us know if you have further concerns and if we can improve in any other aspects.

Comment 1: It seems to me that the main contribution of this work is an algorithm for continual principal component regression (continual PCR), with an application to training with random features.

Reply 1: Good point. We did mention the connection to continual PCR in Remarks 4 and 6, and, to our knowledge, the notion of continual PCR is not mentioned elsewhere; please let us know if that is not the case. We believe the connection we established is important, as many continual learning methods lack theory, while PCR is an important topic in the theory community (or, at least, the references cited in Remarks 4 and 6 are focused on theory); this connection will facilitate our understanding of continual learning by extending existing theoretical results in overparameterized linear models and random feature models to the online/continual case.

Comment 2: ... the properties of the features that arise from pretraining, random projections and nonlinearity don't seem to matter much to the derivations theoretically.

Reply 2: We agree with you. On the other hand, note that random projections and nonlinearity affect the spectrum of $H\_{1:t}$, so they play implicit roles in the values of $a\_t$ and $\gamma\_t$ in the upper bounds. We believe a full analysis that takes random projections and nonlinearity into account is possible in a continual learning setting, e.g., by extending existing theorems for random feature models. Such analysis is well-suited for future work, and we will discuss more related works in more detail and mention this future direction in Appendix H.2.

Comment 3: ... the quantities $\gamma\_t$ and $a\_t$ have an unpacked recursive form. It is not clear to me how they behave in general.

Reply 3: We agree that the appearance of $\gamma\_t$ and $a\_t$ in the upper bound is unconventional, while we argue that we can understand how they behave through the spectrum of $H\_{1:t}$ (or $\widetilde{B}\_t$). E.g., as justified in the paper, $\gamma\_t$ would be very large and $a\_t$ would be small, if we truncate at a position that exhibits large eigengap and the eigenvalues truncated are very small, then the overall upper bound is small. Furthermore, $a\_t$ and $\gamma\_t$ are computable, so we could in principle just plot their values and analyze their behaviors for different truncation strategies. We'd be happy to include such plots if you deem them necessary.

Comment 4: In the ICL framework of Peng et al. (2023), they are maintaining a minimum norm solution based on proof of Proposition 5 in that work where they are using the pseudoinverse. So I think the statements on top of page 3 might not be quite accurate.

Reply 4: We apologize for the confusion. The constraint $x\in \mathcal{K}\_{t-1}$ in Proposition 5 of Peng et al. (2023) can be viewed as the constraint $WH\_{1:t-1}=Y\_{1:t-1}$ in the over-parametrized regime.

Comment 5: In lines 202-208 the cause of instability of RanPAC is attributed to the double descent phenomenon. I think it would be helpful to explain this more to the reader.

Reply 5: This would indeed be helpful. In Appendix K.7.1, we had partial empirical justifications regarding this point. To be more accurate, when we say double descent, we mean the empirical observation that RanPAC has small training losses yet large test losses.

Comment 6: New notation that is used in lines 242-243 has not been introduced yet.

Reply 6: Sorry for the confusion. If we understand it correctly, the new notation used in lines 242-243 refers to $\tau_{k_t}(\cdot)$. This is defined in Line 240 by words. It maps a matrix to its best rank-$k_t$ approximation.

Comment 7: To judge the significance of the experimental results, it would be helpful if the reported numbers included also a measure of uncertainty.

Reply 7: This is a good point. Below we justify our original setup and then mention new experiments with a measure of uncertainty:

• In our original manuscript, we follow the experimental setting of prior work (with the same random seed), and we believe that our experiments are significant as they cover many datasets under various settings.
• On the other hand, we agree with your advice to include a measure of standard deviation, as this can better highlight the strength of our method. We performed such an experiment in Table 16, Appendix L.2, of our revision. That table shows RanPAC has large standard deviations on multiple datasets, while our method is much more stable.

We hope this alleviates your concern. Given more time, we will include or revise more experiments that we deem necessary to measure standard deviations.

Dear Reviewer XHQX,

Thank you for the follow-up comments. We are grateful for your reminder of [1] (PCA-OGD), as there is indeed an interesting connection. We are aware of [1] and cited it, but we overlooked its PCA part. PCA-OGD collects and orthogonalizes eigenvectors to project the gradients. In Algorithm 1 of [1], the set $S\_J$ of eigenvectors grows in size, previous elements are not modified, and the PCA step only truncates the SVDs of the gradients for the current task; in our notation, it considers $\tau\_{d}(H\_t)$ for every $t$ to preserve top $d$ eigenvectors. To our knowledge, PCA-OGD has the following differences compared to our method (please let us know if that is inaccurate):

• (different algorithms) PCA-OGD is a variant of gradient descent, while our method is based on SVDs. PCA-OGD does use the SVDs, but its purpose is to construct the eigenspaces where gradients are projected.
• The set $S\_J$ keeps growing and then PCA-OGD would eventually be infeasible. Also, it does not maintain any information about singular values, so it is unclear which eigenvectors should be discarded when memory is insufficient. In contrast, our method keeps track of singular values, and can truncate SVD factors easily.
• (different truncation strategies) The truncation of each task in PCA-OGD is independent, therefore it amounts to truncating only once. This is simpler than the case we consider, as we need to analyze the effects of $\tau\_{k\_t}(\widetilde{B}\_t)$ defined in Eq 3. Such analysis was mentioned in a follow-up work as an open problem [2] (we are happy to discuss further the differences from [2] if needed).
• (different theorems) The type of theorems is different. In [1], the term analyzed is the forgetting, while we provide bounds on training/generalization errors on the joint loss. The analysis of [1] couldn't be transferred to our case in the under-parameterized regime, as OGD inherently requires overparameterization (otherwise, the orthogonal space might be empty). On the contrary, our theorems can be extended to bound the forgetting.

[2] Youngjae Min, Kwangjun Ahn, and Navid Azizan. One-pass learning via bridging orthogonal gradient descent and recursive least-squares. In IEEE Conference on Decision and Control, 2022.

Comment 3: To be more precise, they depend on the spectrum of $\widetilde{B}\_t$, and hence, implicitly, the spectrum of $H\_{1:t}$. We need extra assumptions to relate the spectrums of $\widetilde{B}\_t$ and $\widetilde{H}\_{1:t}$ (similarly to the eigengap assumptions in Theorem 6), and if we do so, we could potentially express our results in terms of the spectrum of $\widetilde{H}\_{1:t}$. We didn't go into these complications and only argued in Line 287 that, empirically, the spectrums of $\widetilde{B}\_t$ and $\widetilde{H}\_{1:t}$ are close to each other. In general, there is no closed-form relation (equality) between the spectrums of $\widetilde{B}\_t$ and $\widetilde{H}\_{1:t}$ due to continual truncation, and this is also a main difference from PCA-OGD.

Comment 4: You are correct. We appreciate your insights there. The program in Proposition 5 of Peng et al. (2023) would indeed result in a minimum solution if solved via SVDs. We didn't mention this in the main paper as that would take a little bit more to explain. We promise to mention the connection in the revision in the form of a simple lemma in the appendix.

Comment 5: We apologize for the confusion regarding double descent. The simplest way to address it is to revise our wording. We will remove the phrases about double descent and say RanPAC (in some cases) produces small training errors yet large test errors.

My comment about the experiments seems addressed.: Thank you for letting us know:)

Thank you again for your time and follow-up comments, which have improved our work. Many of the above discussions will be included in our paper. Please feel free to let us know if there is still confusion remaining.

Dear Reviewer EXjv,

Thank you for your comments. We are happy to read the strength that The authors provided comprehensive theoretical and empirical results.

The question is whether experience-replay-based methods are compared. The answer is yes (this is implicit in the paper).

Details. We compared our approach with the joint training method (that replays all training data, rather than just a small fraction). In some sense, joint training serves as a performance upper bound for experience-replay-based methods.

Specifically, LC ($X_{1:T}$) refers to joint training of a linear classifier using vanilla ViT features $X_{1:T}$, while LC ($H_{1:T}$) is the same approach, but using the random ReLU features $H_{1:T}$. In Table 1, we show our method outperforms both approaches, without storing any of the samples or features $X_{1:T}$.

There could be other variants of joint training. For example, one could consider joint training of a two-layer ReLU network using ViT features $X_{1:T}$. We didn't show its performance in the paper, but we confirm that it is comparable to LC ($X_{1:T}$) and LC ($H_{1:T}$). We'd be happy to add such a result in the revision.

Please: Feel free to raise any further concerns, as we will be available to respond in the next few days. For example, if you are interested in seeing a specific kind of experience replay methods, let us know and we will compare them.

Please: Dear reviewer, as you've seen, we received divergent reviews. We would be extremely grateful if you could look further at the paper and update your thoughts.

Thank you very much,

Authors

It is right before Thanksgiving, and we take the opportunity to say thank you to all reviewers for their intellectual input. We also want to express our special gratitude to Reviewer XHQX and Reviewer P9vj for participating in the discussion and supporting acceptance.

It is also in the middle of the discussion phase, so we want to have a quick summary of where we are now:

• Reviewer XHQX replied to our rebuttal and suggested that the concern on experiments was addressed. We believe the remaining concerns are somehow minor (but if it is not, please let us know!). For example, regarding the confusion on double descent, we have addressed it by revising our manuscript and removing related contents; in retrospect, we just wanted to say that RanPAC could have large test losses yet small training losses. Finally, we refer the reviewer to Appendix L.4, in which we aim to address the comments on continual PCA to its full extent.
• Reviewer P9vj revised the score from 3 to 6. We highly appreciate it. After discussion, we are glad that Reviewer P9vj finds our theory more elegant and our experiments an empirical success. We believe the main concerns have been addressed, and we promise to make the necessary revisions that would improve the paper (See Appendix L.4).
• While Reviewer EXjv and Reviewer iVyo haven't engaged with us during the discussion phase, this is understandable. For comments of Reviewer iVyo, we have derived a new theorem in Appendix L.1, and we have run new experiments in Appendix L.2. For comments of Reviewer EXjv, we have made a justification about experience replay methods. We believe we have also addressed their comments to the fullest extent; if that is inaccurate, please feel free to let us know.

We appreciate your comments.

Please find the paper you mentioned cited and discussed at page 21 of the manuscript; see the paragraph at line 1122.

Before submission, we implemented an RLS type method using the Woodbury matrix identity to invert the regularized covariance (which is a generalized version of acil). It didn't work well due to numerical instability, a known issue of the matrix inverse formula.

We will further talk about it in the main paper of our camera ready, in a unifying manner. Please stay tuned.

I truly appreciate your insightful work on this topic. It might be helpful to reference [1] in the camera-ready version to further enrich the literature review. Thank you for considering this suggestion.

[1] ACIL: Analytic class-incremental learning with absolute memorization and privacy protection. NeurIPS 2022.