LoRanPAC: Low-rank Random Features and Pre-trained Models for Bridging Theory and Practice in Continual Learning
Authors: Liangzu Peng
Juan Elenter
Joshua Agterberg
Alejandro Ribeiro
Rene Vidal
Venue: ICLR 2025 Poster (2025)
Keywords: Continual Learning; Pretrained Models; Overparameterization; Generalization; Random Feature Models
Primary area: transfer learning, meta learning, and lifelong learning
TL;DR: The paper proposes a simple method that delivers stable and strong performance with theoretical guarantees for continual learning with pre-trained models.

Abstract: The goal of continual learning (CL) is to train a model that can solve multiple tasks presented sequentially. Recent CL approaches have achieved strong performance by leveraging large pre-trained models that generalize well to downstream tasks. However, such methods lack theoretical guarantees, making them prone to unexpected failures. Conversely, principled CL approaches often fail to achieve competitive performance. In this work, we aim to bridge this gap between theory and practice by designing a simple CL method that is theoretically sound and highly performant. Specifically, we lift pre-trained features into a higher dimensional space and formulate an over-parametrized minimum-norm least-squares problem. We find that the lifted features are highly ill-conditioned, potentially leading to large training errors (numerical instability) and increased generalization errors. We address these challenges by continually truncating the singular value decomposition of the lifted features. Our approach, termed LoRanPAC, is stable with respect to the choice of hyperparameters, can handle hundreds of tasks, and outperforms state-of-the-art CL methods on multiple datasets. Importantly, our method satisfies a recurrence relation throughout its continual learning process, which allows us to prove it maintains small training and test errors by appropriately truncating a fraction of SVD factors. This results in a stable continual learning method with strong empirical performance and theoretical guarantees. Code available: \url{https://github.com/liangzu/loranpac}.

Published as a conference paper at ICLR 2025
LORANPAC: LOW-RANK RANDOM FEATURES AND PRE-TRAINED MODELS FOR BRIDGING THEORY AND PRACTICE IN CONTINUAL LEARNING
Liangzu Peng University of Pennsylvania 1penn@seas upenn. edu
Juan Elenter Litwin
Spotify juane@spotify.com
Joshua Agterberg
Alejandro Ribeiro
University of Illinois Urbana-Champaign
University of Pennsylvania
jagtBillinois.ee
aribeirodseas. upenn edd
René Vidal
University of Pennsylvania
vidalrêseas upenn .ddu
ABSTRACT
The goal of continual learning (CL) is to train a model that can solve multiple tasks presented sequentially. Recent CL approaches have achieved strong perfor- mance by leveraging large pre-trained models that generalize well to downstream tasks. However, such methods lack theoretical guarantees, making them prone unexpected failures. Conversely, principled CL. approaches often fail to achieve competitive performance. this work, we aim to bridge this gap between theory and practice by designing simple CL method that is theoretically sound and highly performant. Specifically, we lift pre-trained features into higher dimensional space and formulate an over parametrized minimum- norm least-squares problem. We find that the lifted features are highly ill-conditioned, potentially leading to large training errors (numerical instability) and increased generalization errors. We address these challenges by continually truncating the singular value decomposition of the lifted features. Our approach, termed LoRanPAC, is stable with respect the choice of hyperparameters, can handle hundreds of tasks, and outperforms state-of-the-art CL methods multiple datasets. Importantly, a recurrence relation throughout its continual learning process, which allows us prove it maintains small training and test errors by appropriately truncating a fraction of SVD factors. This results in a stable continual learning method with strong empirical performance and theoretical guarantees. Code available: https: gigh.b....... com/ wiaannnnnaaaaaa loraapaac..
method satisfies
INTRODUCTION
Continual learning (CL) requires training a model that performs well on multiple tasks presented sequentially. A primary challenge in CL is acquiring new knowledge without causing catastrophic forgetting (i.e., substantial performance degradation on previously learned tasks). However, the gap that prevails in the CL literature, as review in Section 5 and Appendix H, is that theoretically grounded CL methods tend to be impractical (Evron et al., 2022; Peng & Risteski, 2022; Peng al., 2023; Cai & Diakonikolas, 2024), while highly performant methods involve solving intricate, non-convex training problems, for which deriving informative theoretical guarantees is challenging (Wang et al., 2022b;c;a; Smith al., 2023; Wang et al., 2023; Jung al., 2023; Tang al., 2023; Gao et al., 2024b; Roy et al., 2024; Kim et al., 2024). In this paper, we aim to bridge the gap by designing simple CL method that both theoretically grounded and highly performant.
Work done while at the University of Pennsylvania.

---

Published as a conference paper at ICLR 2025
Towards this goal, we consider learning downstream image classification tasks continually with large pre-trained models, which are widely available nowadays. As their weights are typically frozen, they provide highly generalizable features that significantly boost performance with little computational overhead (Wang et al., 2022d;a; McDonnell et al., 2023; Zhou et al., 2024a). Crucially, pre-trained models simplify network design, as concatenating pre-trained model with shallow trainable network often attains competitive performance (Zhou et al., 2023; McDonnell et al., 2023).
Motivated by the RanPAC method of McDonnell al. (2023), we use a shallow trainable network that is now commonly known as the rundom,featue model. With this network, we lift pre-trained features into a higher dimensional space and then train a linear classifier on the lifted features simply by least-squares fitting. Yet, the lifted features are double-edged: while they tend to boost performance by increasing feature separability (Telgarsky, 2022; Min et al., 2024), they are also highly ill-conditioned, making it computationally difficult to train the linear classifier. For example, the ill-conditioned features would decelerate the convergence of gradient-based methods such as Orthogonal Gradient Descent (OGD) and PCA-OGD (Farajtabar et al., 2020; Doan et al., 2021). Also due to ill-conditioning, the implementation of the Ideal Continual Learner (ICL) (Peng et al., 2023) based incremental Singular Value Decomposition (SVD) will be numerically unstable. While RanPAC alleviates the numerical instability by using ridge regression, its performance is sensitive to the choice of the regularization parameter, which make it ill-suited for long task sequences.
We identify that the ill-conditioning and instability arise as more tasks are observed and then the smallest singular values of the lifted features plummet, while the largest singular values remain almost constant. This finding motivates our method, termed LoRanPAC, which truncates these smallest singular values prior least-squares fitting. LoRanPAC bridges the gap between theory and practice by delivering stable and strong performance with theoretical guarantees. Concretely:
We provide a continual implementation of LoRanPAC to train an over-parameteriied linear classifier with highly ill-conditioned features in a numerically stable fashion (Section 3). We show it is more stable, more scalable, and more efficient than RanPAC.
We derive theoretical guarantees for LoRanPAC, proving that has small training and test errors when a suitable fraction of SVD factors are truncated (Theorems I and 2, Section 4). These results stem from a non-trivial recurrence relation that allows us to capture the continual learning dynamics of LoRanPAC (Lemma 1, Appendix D).
We conduct extensive experiments on multiple datasets, showing that LoRanPAC uniformly out- performs prior works and specifically RanPAC (Section 6). Thanks to our stable implementation. LoRanPAC outmatches RanPAC by a significant margin in the CIL setting with one class given at a time (Inc-1), 1), where hundreds of tasks (classes) are sequentially presented (Table 2).
TECHNICAL BACKGROUND
Problem Setting. We consider classification tasks in the class-incrementtl learning (CIL) setting, where each incoming task contains only unseen classes. Following conventions (Yan et al., 202 1; Zhou al., 2023), we write B-q1, Inc-q2 to mean that the model is given qı classes in the first task and then d2 classes in each of the subsequent tasks (q) = 0 means all tasks have 92 distinct classes). We use vision transformers (ViTs) of Dosovitskiy et al. (2021) as pre-trained models.
Pretrained Features and Labels. Given my images of task f, we feed them to pre-trained ViTs, obtaining the output features X, E Rdxm, Here, d is the feature dimension (d = 768 in the ViTs used). Corresponding to X, is the label matrix Y. E gee Every column of Y, is one-hot vector, that is some standard basis vector in IR, where 0 is the total number of classes observed so far. We thus have C1 S ..... S C S different number of rows as C; varies, one can pad c - G zero rows to Y, when new class information is revealed; so, with a slight abuse of notation, Y, is viewed as having e rows. We denote by Yi: the label matrix of the first tasks: YE. = 1Y,...,.e Yi] E XM,
G. Let M,- == mi +... + my While Y, Rax might have
Random ReLU Features. Let relu { + m0x be ReLU layer and P Exd denote random Gaussian matrix with i.i.d. (0, 1) entries; here we assume E > d. These allow us to embed X, into a higher dimensional space and get random ReLU features H, RR Exm, via
H relu PX.):
H = H,, .... H,] E BxM.
(1)
2

---

Published as a conference paper at ICLR 2025
Note that relu is a pointwise non-linearity, applied to PX, entry-wise. The goal is to learn linear classifier W E R continually, using features H, and labels Y, of task t.
An alternative way to view these setups is through two-layer neural network
X W relu(PX,
where P are randomly generated, then fixed, and W are trainable weights. Networks of this form predate the early work of Schmidt et al. (1992); Pao & Takefuji (1992) and are later known extreme learning machines and random feature models. In Appendix H.2 we review these lines of research. In principle, the randomness of P would have some effects on learning W, but algorithmicllly, this randomness is irrelevant as P is fixed after random generation. In the paper we adopt this algorithmic viewpoint, treating H relu PP11 1:e) as fixed, and largely ignore the randomness of P.
Table 16 of our appendix shows random ReLU features H1 boosts the performance (compared to the original pre-trained features i ReLU features relu(X;), or randomly embedded features PX i:t- Fig. 6 in the appendix furthermore shows that the performance improves as the embedding dimension E increases. These experiments justify the use of random ReLU features in high embedding dimensions (we use E = 10 unless otherwise specified).
Minimum Norm Solution and Its Instability. If >> M,. there are infinitely many W satisfying WH, = Y (Vi). Among them, a common choice is the minimum-norm solution:
min WER
s.t. WH, Y, i= 1......
(Min-Norm)
where ||- denotes the Frobenius norm. While Min-Norm an offline formulation that assumes the availability of all seen data {HH, Y) 1. it can be implemented in a CL fashion, e.g., via incremental SVD (Remark 2). But such an intuitive implementation fails. Fig. Ia plots the eigenvalues of H H1s, showing that HI, Hi. is highly ill-conditioned: it has just few largest and smallest eigenvalues, respectively of order 10"l and 10 outnumbered by the eigenvalues in between that decay more slowly. Fig. 1b plots extreme eigenvalues of H H. l.t. revealing that the minimum eigenvalue drastically drops after a certain number of tasks. Comparing Fig. lb, c, d, we see that the training MSE loss MT, ||W H1:- Y1.ell explodes up, and the test accuracy plummets, exactly when the smallest eigenvalues (of order 10-5) emerge and begin to invade the spectrum. In summary, the incremental SVD solution to Min-Norm is unable to handle the highly ill-conditioned features H Hi.- resulting in numerical errors.
3 LORANPAC: STABLE CONTINUAL LEARNING VIA LOW-RANK RANDOM FEATURES
Offline Formulation. The numerical evidence collected in Fig. suggests that the instability of Min- Norm relates to the emergence of very small eigenvalues that make H1: Ex,, ill-conditioned. This motivates simple remedy, called LoRanPAC (offline formulation), which consists of truncating the smallest singular values (vectors) of 1:r and then solving Min-Norm with its truncated version. More concretely, write the SVD of HI:
as d U +... + o M, U, VMr with ordered singular values 01 2 ... 2 M, The truncation can then be described with some integer k E [0, M,] by a function The that maps H1: d u +... ok. ux, " where k; is the number of top SVD factors preserved. Since Tu, (-) preserves the shape of its input, The (H1:) is of the same size E M, as H Applying this idea of truncation to Min-Norm means solving the following program:
Wr E argmin |[]] W
s.t.
WT,, (H Yı.-
(LoRanPAC)
LoRanPAC is thus named, as it draws inspiration from RanPAC (McDonnell et al., 2023) and leverages low-rank random features. It is safe to assume k; S rank Hi)), , for otherwise the truncation has no effects. For simplicity one might assume H has full rank, that is rank( H.:)) min E, M,).
Continual Implementation. To solve LoRanPAC continually, we first write down the closed-form expression of W.. Let U 1: Dia 1ie be a compact SVD of Th 11); here, U is of size E ke and En is invertible of size k, k2 Similarly, let U1 E1. V be compact SVD of H where
3

---

Published as a conference paper at ICLR 2025
CIPAR1O0 (B O, Inc 10)
ImageNet R (B O, Inc 20)
ImageNet ( 0, Inc 20)
CUB 200 (D 0, Inc 20)
Elgenvalie alues
10"h
Eigenvalues
10
Eigen alues
1n
10a1
10*
10
Eigenvalie
10f
10
10
20X
24K
1.5%
6K
2.5K
Eigonvaluc
Eggovaauu Index
Higenvalue Index
Eigonvalue Index
(Ia) The eigenvalues H H arranged in descending order fixed).
CIFAR100 (8-0, Inc-10)
ImiggeNet-R (8-0, Ioc-20)
ImageNNetAA (8-0, Inc-20)
CUB-200 (8-0, Inc-20)
10t0
Elg.
10
10th
Eig
10
10a
tig.
tog.
10a
tag.
10
tig.
10
10
10
Seon Tasks
Seen Tasks
oo Seon Tasks
Seen Tasks
(lb) Maximum and minimum cigenvalues of H H1s as the number of seen tasks increases.
CIFARLOD (B-0,MM Inc-10)
ImageNet-RR (B-0, 20)
ImageNet- (B-0, Inc-20)
CUB-200 (B-0,
Training Loss
10
Training Lons
10.6
Training Loos
10
Training Lows
10c
10a
10
10"
10a
10
10
of Seen Tasks
of Seon Tasks
8 of Seen Tasks
Seen Tasks
(Ic) Training MSE loss
WHa el of the incremental SVD solution to Min-Norm.
Mr
CIFARLOD (B-0, Inc-10)
ImigeNNi-R (B-0, Inc-20)
ImagoNet-A Inc-20)
CUB-200 (B-0,
Final Ave. (%)
100
100
Final Avc. (8)
100
100
Final Acc.
50
50
Final
2
10
10
Seen Tacks
of
Scen Tasks
Scen Tasks
#of Seen Tasks
(Id) Final test accuracy of the incremental SVD solution to Min-Norm.
Figure I: Spectrum of H H1st and its impact on training losses test accuracy (E' = 100); see also Appendix K.8. The matrix H His is ill-conditioned (la); training loss increases (Ic) and test accuracy drops (Id), drastically, when small eigenvalues (of order 10 10-5) invade the spectrum (Ib).
Algorithm 1: Continual Solver of LoRanPAC (detailed version in Algorithm Appendix C) IR. Exm: (1), labels Y, E Roxo,, truncation percentage Ç [0, 1];
Input (Task t): Features H,
For t + 1, ...:
hi < [(1 <) min(E, M+]
|| Mr mi + + m. can be updated online online update J, detailed in Algorithm 5, Appendix C
Jr + H
Form B, as per (3);
(UI:t; E1:t) + Top-k, SVD factors of B;; Algorithm if 1, or Algorithm
1 |/ cf. (2) and (4)
Compute linear classifier W, = J,Ü 18
Ul has rank 1x)) columns and contains U la as a submatrix. We can then write W, as
W, Yı V E En U Y V in EnL (UINITA
YI. Via Ei U. 1t (UINELU I..) Y. 1: U 1 (UITDT 14
where (i) holds as the column vectors of U1. not shown in Una are orthogonal to U 1:t- Given (2), now suffices to update J. == H RoXE U. E REx*, and Σ x in an online fashion. This procedure is described in Algorithm 1, where the following points are considered:
Since the columns of Yi: are one-hot vectors, can compute H. incrementally by matrix addition rather than (sparse) matrix multiplication.
An exact update of U 1a and Ei would require computing the SVD factors of the full data Hi However, past data H H is not available when observing task t. Thus, consider approximating
4

---

Published as a conference paper at ICLR 2025
CIFARIO0 (B O, Inc 10)
ImageNet R (B O, Inc 20)
ImageNet A 0, Inc 20)
CUB 200 (D 0, Inc 20)
Final Auc. (35)
100
Final Acc, (3)
100
Fizsl Acc. (95)
100
Final Acc. (3)
100
30
50
25
50
90
25
50
90
25 50
90
25 50
90
Trancation Percentage
Truncation Percentage
Trancation Percentage (1)
Truncation Percentage
Figure 2: Final test accuracy the truncation percentage varies.
U 1:t. Σy:t by two respective matrices U1:, Enr of the same sizes. Specifically, as shown Line 6, we set U1: Σx:t to be the top & SVD factors of B,, where B, is defined as
H -UL--1E1H-11 H.
t 1;
B.
otherwise.
Note that B, is of size E' x m,, while for > 1 we have B, of size E' x (k-1+ m,). The top-k; singular values of B, and H1st are close each other (cf. Fig. la, Fig. 8, Fig. 9, and Theorem 6). which indicates the effectiveness of our continual updating strategy. Then, as shown in Line 7 and recalling (2) and Jj = HH I.r. we construct a linear classifier via
In Algorithm 1, Ç denotes the truncation percentage. Given Ç. we set the number ky of top SVD factors preserved at task l k2 = [(1 () min M,], where [-] converts an input number to the closest integer no smaller than it. Fig. 2 visualizes the effect of Ç on the final test accuracy, highlighting nearly zero accuracy with Ç and stable performance with
5%.
Remark 1. At test time, given sample, we make forward pass and obtain its random ReLU feature h. The predicted class is then set according the maximum entry of W.h.
Remark 2. Algorithm with Ç = is the incremental SVD method that we use solve Min-Norm. Remark (Time and Space Complexity). The major cost of Algorithm is to compute the top-k; SVD factors of the E' x (kz-1 + m²) matrix B,, which takes ((E(k,1 + m²)²) time. Futhermore Algorithm I uses O + Ek; + kt) memory to store J. U1. and En and W.. and OEE;,11 Em.) memory to construct B,, and some extra working memory to compute the top-k, SVD factors of B₁. We refer the reader to Appendix for more details.
4 PROVABLY CONTROLLED TRAINING AND TEST ERRORS
In this section, we present Theorems and 2, which bound the training and test error of the output (4) of our approach (Algorithm 1).
Notations. Denote by (+(-) the k-th largest eigenvalue of a symmetric matrix. Define
Pkk (B.B.)
= 7h
max { (1 +1 (BBB)}} 11 1.
(5)
The quantity relates to the skaiilit-plastiinn tradeoff, as it is the ratio between the minimum preserved eigenvalue Pk, (B,B,) at task and the maximum eigenvalues being truncated in the past, 1 ( ). Clearly Tt > 0, as we truncate only non-zero eigenvalues. Furthermore, instead of determining the number of preserved SVD factors ky based the truncation percentage Ç. can take a threshold hyperparameter 8 and truncate eigenvalues smaller than o; this 5 implicitly determines k and we have μos, (B 2 8 Pkc+1 1 (B.B,) which implies 7/- > 1. Finally, as suggested by Fig. a, 7, be as large 1010, If we set 8 10-2 in the case of Fig. 1a, then the maximum truncated eigenvalue is of order 10-5 and the minimum preserved is of order 103.
Then, the accumulative error d, defined as
Og :, 0,
a :
Σ Mk++1 (BB.),,
Vt 1.
(6)
5

---

Published as a conference paper at ICLR 2025
The term de reflects the information ignored by our algorithm, Mk (B.B," is the maximum eigenvalue truncated at task i. Note that, even when observing thousands of tasks (e.g., & Rz 109), if we truncate the smallest eigenvalues (of order 10-9), az is in the order of 10-2.
Model Assumption. We consider a noisy linear regression model. Specifically, we assume there is some ground-truth weight matrix W E RR X and noise E E RRXM; satisfying
Yı W H1a + Ela.
(7)
The quantities W and E are colored to reflect the fact that they are unknown and not computable. The model in (7) is related to probabilistic principal component analysis (PPCA); cf. Tipping & Bishop (1999) and Chapter 2.2 Vidal et al. (2016). The two main differences with PPCA are that make probabilistic assumptions on H or &1st (except in Appendix F); and we consider the over-parameterized case with large E, while PPCA assumes W is a tall matrix (i.e., E < (.).
Bound The Training MSE. In the over- perr-aarettrzeed regime E > Mr. solution to Min-Norm should, in principle, perfectly fit the data and achieve zero training MSE. However, solving Min-Norm is numerically unstable and empirically entails huge losses (Fig. 4). As remedy, our approach truncates the data spectrum continually, trading off between perfectly fitting training data and increasing numerical stability, The following theorem, whose proof can be found in Appendix E, connects the eigenvalue ratio "/t and the accumulative error a with our method's training loss, showing that the training MSE is provably under control:
Theorem 1. Let B It, Or be defined as in (3). (5), and (6) respectively, Yf = WHH + E (7), then the output W. H. U1 DT.
1. of our method (4) satisfies
at + at-1(t 1) + at-1(t 1)2
W,HH - 11 < 4- 1|WT
(8)
M
Mr
T/
(Mr (
kt)
+ (t - 1) min {M, 1. (t 1)k}
+ 1E1=1l
Mr
n2M,
In (8), ||-|| is an overloaded notation, denoting the spectrum norm of a matrix and also the Fuclidean norm of vector. One of the main quantities governing the bound in Theorem is Mr/M, which reflects the truncation process for the current task. When truncating the smallest eigenvalues (of order 10-5) and observing hundreds of tasks, 0e is in the order of 10 which makes az/ insignificant. Then, the terms (t (t-1)/7 and a, a;-1/M, capture the continual past truncations and are equal to zero for t t= 1. Similarly to at, when truncating only the smallest eigenvalues, we have a ~ 10 5(t 1) and (1. - 1)/7* Rs 10-19(1 - 1). Hence, all terms involving (1 - 1)/7/ and at a-11M, are under control for hundreds- even thousands- of tasks. Finally, although the ground-truth W; and noise & are unknown, we empirically verify that the minimum ninimum-norm norm solution to LoRanPAC achieves high accuracy (Section 6). This suggests the linear model assumption is adequate, and that || and ||W; E are reasonably small. In summary, the upper bound (8) shown in Theorem I behaves well and is quite small if we truncate the eigenvalues suitably (which makes ,/e large and a small).
Bound The Test MSE. Consider test sample (h, y) satisfying y = W for some noise vector e. To derive a bound on the test MSE, we assume that is randomly sampled from some distribution with a finite second-order moment (A == E[hhT]] < oc), and that is random, independent of h. Given the output W, of our method (4), we bound its test error Ex,,, [|] y over the randomness of h, as follows:
Theorem 2. Let B,, Yes a be defined as in (3), (5), and (6) respectively. Assume Yı:t = Wi H
Ei (7) and y = W h + E with A = hhh J. The output W, of Algorithm 1 satisfies
En,el Wih- - 211² < 4- W I1 B, 4. 11E V, + 2- 2-E. [l[]]]]
(9)
where B, and V, are defined as follows:
1
1+ (t 1)2 (t-1)2)
Mr + ac - 1) + a 1 1)2
at
B.- A-
H
H
+
M
1:t
7p
1 min (M-1 k (t 1)ke + kie)
V
A
1
H
11
H 1:
7t
(10)
Me
Mk, ( (B.B.))
-t-1
+
+
min (M,- - 1, (t 1)ker
M,
(,
Mr,

---

Published as a conference paper at ICLR 2025
There are two major terms in B. (10). The term in the right- large parenthesis also appears in the error bound of Theorem 1; and reflects the fact that training losses impact test errors. Then, the term | Mr H H is commonly seen in covariance estimation (Wainwright, 2019), where h and the columns of H1:t are assumed to be independent i.i.d. Gaussian vectors. In this case, if A furthermore satisfies some boundedness condition, we can show || M. H converges to 0 as M, - oc; cf. Theorem 9 of Koltchinskii & Lounici (2017). On the other hand, the Gaussian assumption is sufficient but not necessary, and similar conclusion is reached if we take much weaker assumption called hypercontructivity (Jirak et al., 2024). Note that V, is independent of noise, so the rest of the terms in (9), which are weighted by noise magnitudes || /12, B. [e[[|e]] [||]]]]] are negligible if the noise is sufficiently small.
5 RELATED WORK
We now discuss related works that are the most relevant to our method and theory. A more extensive review of the literature and context is in Appendix H.
RanPAC. The RanPAC method of McDonnell et al. (2023) motivates our use of random ReLU features HI...., Ht. It amounts to solving the ridge regression problem (with some À > 0) (RanPAC)
min W WEREXE
A W |
WH:
The choice of hyperparameter À is crucial: RanPAC with small regularization À fails to achieve competitive performance, while it might work well with a large enough (e.g.. À = 10"); cf. Fig. 12. In constrast, Prabhu et al. (2024) finds that small À (of order 10-9) works better if Hi:e is replaced with random Fourier features. This implies the optimal choice of À depends, among other factors, on the scale of the features and the noise level. Our method also has hyperparameter, the truncation percentage Ç. while the choice of ( is less sensitive to these factors (Fig. 2). In the implementation of McDonnell et al. (2023), RanPAC selects from the predefined set {10 10 100 ...., 10*} via cross vross-valiittion on small faction of training data. Although this stabilizes RanPAC in some cases, cross-validation can fail when the validation (or training) set is small and not representative of test data. Unfortunately, this failure occurs often in CIL. with small increments (cf. Table 2, Section 6).
In more detail, for every task and every each candidate choice of X, RanPAC maintains the HI to solve the normal equations W (Hi,H 1: + ALE) H in variable W using off-the-shelf solvers implemented
covariances H 1:2. H.
PyTorch, which in general takes O O time. In contrast, LoRanPAC has O(E(k,1 + m)) time complexity, and this is why it is slower than LoRanPAC for the same E, particularly when E is large (cf. Fig. 3, Section 6). Certainly, both RanPAC and LoRanPAC can potentially be implemented more efficiently. For example, RanPAC involves inverting the regularized covariance H H + ATg. and this inverse can be updated continually via the recursive least-squares method (Sayed, 2008), and its philosophy is also found in recent continual learning papers (Min al., 2022: Zhuang al., 2022; 2023). However, it is known that such scheme can be numerically unstable, brittle for ill-conditioned data. Indeed, in our setting, We find the implementation based on the and is unable to maintain good accuracy. Moreover, numerical emror accumulate over time, leading to worse performance for longer sequences of tasks. Finally, even if we know the numerical errors might arise in these methods, there is no obvious way to remedy them. This is different from implementation based on robust truncated SVD, which has the advantage that we could (empirically) reduce numerical errors by re-orthogonalizing Ula (see Remark 4 and Algorithm 2).
MorrbroonWWoodburr formula. This formula is at the heart of the classic
-ooodbury formula suffers from numerical errors
One more component in RanPAC is a preprocessing step called first-session adaptation. That is, before using the pre-trained model for continual learning, one fine-tunes it with data from the first task in parameter-efficien different features than H Hist- We study the impact of this step in Table 1, Section 6.
way (Panos al., 2023). This needs extra hyperparameters and yields
The final point that relates LoRanPAC to RanPAC is this: W in (2) is global minimizer of [[ (Hra) Y..
min WE
(11)
Both LoRanPAC and RanPAC aim to minimize the MSE loss; the former uses truncation and the latter uses regularization to make the problem better conditioned. The MSE loss typically yields
7

---

Published as a conference paper at ICLR 2025
similar performance to the cross-entropy loss in many settings (Janocha & Czarnecki, 2017; Hui & Belkin, 2021), and the MSE loss is preferred here as it allows for a closed-form sqast-suuares solution to be rapidly computed and continually updated.
ICL. LoRanPAC is also related to the Ideal Continual Learner (ICL) of Peng et al. (2023), which in the linear, over-parameterized case is the following linearly constrained quadratie problem:
min WERsXX
| H, Y.lli
S.I.
WH; Y, 1
(ICL)
Proposition 5 of Peng et al. (2023) gives a method based on SVD to solve ICL; it is proved in Peng & Vidal (2025) that this method implicitly finds the solution to Min-Norm. But we have seen in Fig. I that solving Min-Norm is numerically challenging due to highly ill-conditioned features Hys. Proposition of Peng et al. (2023) further suggests that solving ICL by a muudient-based method gives the approach of Farajtabar et al. (2020), known Orthogonal Gradient Descent (OGD). Subsequently. OGD is combined with the idea of SVD truncation in the PCA-OGD method (Doan al., 2021). As gradient-basee data and would be less efficient than our LoRanPAC implementation; the differences between PCA- OGD and our method are thoroughly discussed in our rebuttal. The OR-Fit method of Min al. (2022) improves PCA-OGD by devising carefully chosen stepsizes that facilitate sol solving the current task. Their proposed stepsizes are related to ICL and recursive least-squares in an intriguing manner; we refer the reader to Peng & Vidal (2025) for the precise mathematical connections and a unifying perspective on the aforementioned methods.
methods, OGD and PCA-OGD converge slowly for ill-conditioned
Principal Component Regression. LoRanPAC combines principal component analysis and ordinary least-squares, which is analogous to principal component regression (PCR) (Xu Hsu, 2019; Huang et al., 2022; Hucker & Wahl, 2023; Bach, 2024; Green & Rooanov, 2024). These papers consider the offline setting, where truncation performed only once. In contrast, we analyze the effect of continual truncation, which is most pertinent for CL. Indeed, for = 1, B2 of Theorem 2 is equal to the corresponding term in Theorem of Huang et al. (2022) up to a constant. More importantly, these papers have statistical assumptions
H1., which are potentially violated by generating H1: via H; := relu( PX,), with X, consisting of features from pre-trained models. In contrast, Theorems 1 and 2 have few assumptions, and so they apply, at least in principle, the full architecture (i.e., pre-trained model and random ReLU feature model in cascade).
6 NUMERICAL VALIDATION
This section highlights the performance and efficiency of LoRanPAC in the CIL setting across a diverse range of datasets and increments. For additional results, see Appendix K, particularly Appendix K.4 for experimental outcomes in the DIL. (domain-incremenntal learning) setting.
6.1 SETUP
Baselines. The most relevant baseline compare is RanPAC (McDonnell al., 2023). Additional competitive baselines include L2P (Wang et al.. 2022d), DualPrompt (Wang et al., 2022c). Co- daPrompt (Smith et al., 2023), SimpleCIL, ADAM (Zhou et al., 2023) and EASE (Zhou et al., 2024a). We also compare LoRanPAC with a joint linear classifier, that is, linear model trained using either the pre-trained features X1. of all T tasks, or the random ReLU features HIT. We denote these two methods by LC (X)rr) and LC (Hirr). To ensure fair comparison, all experiments are conducted based on the PILOT GitHub repository Sun al. (2023), Additional experimental details, as well as comprehensive review of relevant baselines is given in Appendix J and Appendix H.
Pre-trained Models. We use ViT models pre-trained on ImageNet- 1K; specifically the model www__baeeeppttec 224 from the t timm repository (Wightman, 2019). Experiments using ViTs pre-trained on ImageNet-21K are presented in Appendix K.2.
Datasets. Following prior works (Zhou et al., 2023; McDonnell et al., 2023), we CIL experiments with B-q1, Inc-qu on continual learning versions of the following datasets: CIFAR 100 (Krizhevsky al., 2009), ImageNet-R (Hendrycks et al., 2021a), ImageNet-A (Hendrycks et al., 2021b), CUB-200 (Wah et al., 201 1), ObjectNet (Barbu et al., 2019), OmniBenchmark (Zhang et al., 2022), VTAB (Zhai al., 2019), and StanfordCars (Krause et al., 2013). We set qi = 0 for most cases, but since
8

---

Published as a conference paper at ICLR 2025
Table 1: Final accuracy with pre-trained ViTs. Large accuracy gaps between RanPAC and LoRanPAC (ours) are shown in bold. t: Methods using first-session adaptation with the hyperparameters set as per RanPACt. *: Methods using first-session adaptation with the hyperparameters set as per EASE" (Zhou et al., 2024a). Table 14 reports standard deviation. Appendix reports experimental details.
(Part 1)
CIFAR (B-0)
ImageNet-R (B-0)
ImageNet-A (B-N)
CUB-200 (B-0)
Avg.
LC (X.r)
87,56
72.42
58.85
88,76
76.90
LC (H)r)
87.76
73,00
59.25
88,72
77.18
Ine-5
Ine-10
Inc-20
Inc-5
Inc-10
Ine-20
Ine-5
Inc-10
Inc-20
Inc-5
Inc-10
Inc-20
L2P
80.25
83,53
83.57
67.92
71.78
73.42
44.50
48.52
51.28
53.60
59,20
67.81
65.45
DualPrompt
80.85
84.59
67.12
71.57
72.87
53.72
56.75
54.79
63.99
69.93
67.48
CodaPrompt
82.93
86.31
87.87
67.80
72.73
74.85
34.43
49.57
59.51
36.39
60.18
71.29
65.32
SimpleCIL
80.48
80.48
80.48
63.47
63.47
63:47
58.72
58.72
58.72
80.45
80.45
80.45
70.78
RamPAC
86.71
87.02
87.10
71.90
71.97
72.50
56.48
62.34
61.75
88.08
87.15
88.13
76.76
LoRanPAC
88.18
88.18
88.21
73.67
73.72
73.63
62.74
63.20
63.20
89.36
89.27
89.23
78.55
ADAMI
83,55
85.13
85.86
63.73
65.03
71.40
58.72
58.66
58.99
80.49
80.66
81.00
72.77
RanPACI
88.73
90.04
90.74
70.80
73.37
78.80
62,34
62.08
62.28
88.42
87.57
88.68
78.65
LoRanPACt
89.73
90.82
91.44
73.58
74,55
79.13
62.74
62. 80
62.94
89.14
89.19
89.27
79.61
EASE"
84.43
86.48
88.16
73.53
77.02
77.55
58.26
61.69
62.28
80.66
81.68
81.13
76.07
LoRanPAC
89.46
90.90
91.67
78.73
80.43
81.45
63.40
64.45
65.64
89.14
89.19
89.44
81.16
(Part
ObjectNet (B-00)
OmmiBenchmarkk (B-0)
VTAB (B-10)
StanfordCars (BB-16
Avg.
LC (Xir)
59.70
79.55
91.32
74.12
76.17
LC (H)r)
59,96
80.02
91.17
73.65
76.20
Inc-5
Inc-10 10
Inc-20
Inc-5
Inc-10
Inc-20
Inc-5
Tnc- 10
Inc-20
Inc-5
Inc- 10
Inc-20
L2P
45.53
$2.05
55,49
54.50
57.29
60.50
59.32
73.25
78.91
13.70
27.46
43.68
51.81
DualPrompt
47.56
53.68
55.64
56.14
59.18
62.39
64.10
77.78
83.75
11.38
18.84
27.
51.53
CodaPrumpt
46.61
54.44
59.17
60.00
64.98
68.25
68.77
76.81
86.32
7.96
11:29
30.74
$2.95
SimpleCH.
51.66
51.66
51.66
70.19
70.19
70.19
82.53
82.53
82.53
35.46
35.46
35.46
59.96
RanPAC
58.77
$7.66
57.69
77.65
77.63
77.46
91.15
91.58
91.58
58.03
71.40
71.40
73.50
LoRanPAC
60.83
60.86
60.77
79.50
79.60
79.70
92.46
92.55
92.56
74.21
74.39
74.39
76.82
ADAM!
52.16
53.94
55,97
70.54
70.53
70.38
82.55
82.55
82.55
35.61
35.61
35.61
60.67
RanPACT
59.14
61.54
64,59
78.10
78.46
78.86
91.48
91.8% 86.
91.86
58.65
72.24
72.24
74.56
LoRanPACt
61.78
63.56
66.48
80.07
80,28
80.45
92.55
92.53
92.60
74.87
74.89
75.13
77.93
EASE"
49.28
53.88
57.05
70.33
70.68
70.84
89.85
93.48
93, 23.49
32.43
31.77
29.00
61.84
LoRanPAC
61.57
63.40
66.29
80.02
80.42
80.82
92.68
92.71
92.67
75.91
75.71
75.96
78.18
10 for StanfordCars and VTAB have 196 and 50 classes, respectively, take 91 = 16 and Q1 them. We let d2 vary in (5, 10, 20), and also consider the more challenging case (2 = 1.
Metries. After learning task evaluate the top-1 classification accuracy Ai, for every = 1, , For a total of T tasks, the accuracy matrix AA defined as a T x T upper triangular matrix with its (i, t)-th entry being As,., Final accuracy is defined as the average 1 -E=1-A4 A of the last column of A. Total accuracy is defined as the average Tリ--1 Eisises Ai, of all upper triangular entries. Following common practices, use total accuracy and final accuracy as our evaluation metrics.
6.2 EXPERIMENTAL RESULTS AND ANALYSIS
Table 1 contains the main results for g2 5, 10, 20 on 8 different CIL datasets. First observe that L2P, DualPrompt, and CodaPrompt are unstable as their accuracy varies significantly different datasets for different values of d2. Second, SimpleCII., ADAM, and EASE are unstable as their performance largely compromised on StanfordCars. Then, RanPAC is unstable with respect to 92 as exhibits a large performance gap compared to LoRanPAC for q2 5 on ImageNet-A and StanfordCars. Finally, we see LoRanPAC has more stable performance across datasets and for varying Q2.
Why Does LoRanPAC Uniformly Outperform RanPAC? The first reason is that LoRanPAC's high efficiency and scalability enable the use of a larger embedding dimension. Indeed, LoRanPAC uses E 1 taking advantage of the scaling law (Fig. 6, Appendix K.5), while RanPAC uses its default choice E = 10 Note that this is a fair comparison since LoRanPAC's implementation is more scalable and more efficient than RanPAC's. Specifically, LoRanPAC has O (K + 2)

---

Published as a conference paper at ICLR 2025
Inc-5)
ImageNNot-R (8-0, Inc-5)
ImageNNet-A. Inc-5)
(3-0, (nc-5)
Training Time
10
Training Time
Taainin
RantiK:
10
LottasPAC
RantfC:
Thaining
30
RastWi::
16
RantWC:
10
10
10K
15K
ZIK
25K
50K
10DK
10K
15%
20K
25K
50%
100K
10K
15K
20K
25K
50%
100K
10K
15K
20K
25K
50%
10OK
F
15
Figure 3: Training times (in minutes) for varying embedding dimensions E.
time complexity while RanPAC takes O( time for each task t. An alternative way to make fair comparison is the same embedding dimension E for both methods, which case LoRanPAC can be up to 1000 times faster than RanPAC (e.g., see E = 25000 in Fig. 3).
The second reason, as mentioned earlier, that the cross-vass vrlssvvaiiatioon strategy of McDonnell al. (2023) might fail to choose a suitable regularization À for RanPAC when the validation set is small. This is the case in ImageNet-A (B-0, Inc-5) and StanfordCars (B-16, Inc-5) of Table where the validation sets are small and RanPAC's performance is severely degraded. A more careful analysis of these two failure cases shows that the accuracy matrices RanPAC have multiple columns with nearly zero entries (cf. Fig, 15a and Fig. 17c), exposing RanPAC's instability.
Table 2: Final and total accuracy in CIL datasets with Q2 (Inc-1) 1).
CIFARI00
ImageNet-R
ImageNet-A
CUB
ObjectNet
OmniBenchmark
VTAB
StanfordCars
Final Accaracy
RanPAC
86. 86.9920.0z
70. 20.10
26.6225.35
55. 35.15
57.1420.4
77.920.04
91.47
35.56
LoRanPAC
88.19.0.m
73.66.0.07
62.76
89.19 10.00
60.82
79.3
92.51 92.51
74.32.
Total Accuracy
RanPAC
90.46 73
69.1.0.37
44.23 a. 46
74.67 22:87
62.37 23.1
85.23_0.50 0000
74.67 53307
56.27 =0.77
LoRanPAC
02.18
20.87
2: 26.86
92.89 2: 50
g0.54g1.04
86.51
96.41
81.18
Inc-1:
One Class at A Time, light of the above analysis, we consider the CIL setting, with one class given at each iteration (Inc-1). In this setting, a new task has much fewer training samples and CL methods need to cope with hundreds of tasks (classes) on certain datasets. Note that baaee methods such as EASE are infeasible for CIL with Inc-1 1 (cf. Appendix H.)). In this setting, the fragility of RanPAC with respect to the choice of is amplified (see Table 2), and the method exhibits significant performance drop compared to Table 1. In contrast, LoRanPAC's performance is stable, exhibiting high accuracy comparable to the cases of Inc-(5, 10, 20} in Table 1. Accuracy matrices associated with Table 2 plotted in Figs. 14 to 18 of Appendix K. K.10.3, where present similar results for Inc- (1, 21, 4,
7 CONCLUSION
This work puts forward simple method that bridges the gap between empirical performance and the- oretical guarantees continual learning with pre-trained models. By addressing the ill-conditioning of lifted features through continual SVD truncation, our approach achieves both stability and strong performance. Extensive experiments demonstrated that our method outperforms sfate-of-the --thh-art methods across multiple datasets and can handle sequences with hundreds of tasks. Theoretically, we proved that our method maintains small training and test errors by appropriately truncating SVD factors. This work underscores the potential of combining empirical techniques with principled frameworks to develop robust and scalable continual learning systems, and will encourage follow-up works to achieve so as well.
ACKNOWLEDGMENTS
This work is supported by the project ULEARN "Unsupervised Lifelong Learning", funded by the Research Council of Norway (grant number 316080), and by NSF-Simons Research Collaborations on the Mathematical and Scientific Foundations of Deep Learning (NSF grant 2031985).
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Kyra Ahrens, Hans Hergen Lehmann, Jac Hee Lee, and Stefan Wermter. Read between the lay- ers: Leveraging multi-layer representations for rehearsal-free continual learning with pre-trained models. Transactions on Machine Learning Research, 2024. 32, 33, 34
Matej Artac, Matjaz Jogan, and Ales Leonardis. Incremental PCA for on-line visual learning and recognition. In International Conference on Pattern Recognition, 2002. 19
Anonymous Authors. The official homepage on origins of extreme learning machines (elm). https:
//elmorigin www.eoriiiii.iiistiieeeieeeeieee wixsite com/ orrginofeeenn.. Accessed: September, 2024. 34
Francis Bach. High-dimensional analysis of double descent for linear regression with random projections. SIAM Journal Mathematics of Data Science, 6(1):26-50, 2024. 8, 35
Andrei Barbu, David Mayo, Julian Alverio, William Luo, Christopher Wang, Dan Gutfreund, Josh Tenenbaum, and Boris Katz. ObjectNet: A large-scale bias-controlled dataset for pushing the limits of object recognition models. Advances in Neural Information Processing Systems, 2019, 36
Peter L Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 1174449:30033-30077 2020. 35
Mikhail Belkin, Siyuan Ma, and Soumik Mandal. To understand deep learning we need to understand kernel learning. In International Conference Machine Learning. 2018. 35
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-learning practice and the classical variance trade-off. Proceedings of the National Academy of Sciences, 116(32):15849-11 15854, 2019. 35
Matthew Brand. Incremental singular value decomposition of uncertain data with missing values. In European Conference on Computer Vision, 2002. 19
James R Bunch and Christopher P Nielsen. Updating the singular value decomposition. Numerische Mathematik, 31(2):111-129 1978. 19
Xufeng Cai and Jelena Diakonikolas. Last iterate convergence of incremental methods and applica-
tions in continual learning. Technical report, arXiv:2403.0687 [math.OC), 2024.
Arslan Chaudhry, Marcus Rohrbach, Mohamed Elhoseiny, Thalaiyasingam Ajanthan, Puneet K Dokania, Philip HS Torr, and Mare' Aurelio Ranzato. On tiny episodic memories in continual learning. Technical report, arXiv: 19...1900...... 10486v4 [cs.LG], 2019. 32
Shoufa Chen, Chongjian Ge, Zhan Tong, Jiangliu Wang. Yibing Song, Jue Wang, and Ping Luo. AdaptFormer: Adapting vision transformers for scalable visual recognition. Advances in Neural Information Processing Systems, 2022. 33
Yuxin Chen, Yuejie Chi, Jianqing Fan, Cong Ma, al. Spectral methods for data science: A statistical perspective. Foundations and Trends@ in Machine Learning, 14(5):566-806, 2021. 31
Chandler Davis and William Morton Kahan. The rotation of eigenvectors by perturbation. iii. SIAM Journal on Numerical Analysis, 7(1):1 1970. 31
Meng Ding, Kaiyi Ji, Di Wang, and Jinhui Xu. Understanding forgetting in continual learning with
linear regression. In International Conference Machine Learning, 2024. 34
Thang Doan, Mehdi Abbana Bennani, Bogdan Mazoure, Guillaume Rabusseau, and Pierre Alquier. A theoretical analysis of catastrophic forgetting through the NTK overlap matrix. In International Conference on Artificial Intelligence and Statistics, 2021. 2, 8, 33
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale. In International Conference on Learning Representations, 2021.
11

---

Published as a conference paper at ICLR 2025
Arthur Douillard, Alexandre Ramé, Guillaume Couairon, and Matthieu Cord. DyTox: Transformers for continual learning with dynamic token expansion. IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2022. 32
Juan Elenter, Navid NaderiAlizadeh,, Tara Javidi, and Alejandro Ribeiro. Primal dual continual learning: Balancing stability and plasticity through adaptive memory allocation. Technical report, arXiv:2310.001 [es.LG] 2023. 32
Itay Evron, Edward Moroshko, Rachel Ward, Nathan Srebro, and Daniel Soudry. How catastrophic can catastrophic forgetting be in linear regression? In Conference on Learning Theory, 2022. 1, 33
Mehrdad Farajtabar, Navid Azizan, Alex Mott, and Ang Li. Orthogonal gradient descent for continual learning. In International Conference Artificial Intelligence and Statistics, 2020. 2,
Xinyuan Gao, Songlin Dong, Yuhang He, Qiang Wang, and Yihong Gong. Beyond prompt learning:
Continual adapter for efficient rehearsal-free continual learning. In European Conference Computer Vision, 2024a. 33
Zhanxin Gao, Jun Cen, and Xiaobin Chang, Consistent prompting for rehearsal -free continual learning. IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2024b. 1, 33
Daniel Goldfarb, Itay Evron, Nir Weinberger, Daniel Soudry, and Paul Hand. The joint effect of task similarity and overparameterizztion catastrophic forgetting an analytical model. In International Conference on Learning Representations, 2024. 34
Alden Green and Elad Romanov. The high-dimensional asymptoties of principal component regres-
sion. Technical report, arXiv:2405. 1676 [math.ST], 2024. 8, 35
Etash Kumar Guha and Vihan Lakshman. On the diminishing returns of width for continual learning. In International Conference on Machine Learning, 2024. 39
Nathan Halko, Per-Gunnar Martinsson, and Joel A Tropp. Finding structure with randomness:
Probabilistic algorithms for constructing approximate matrix decompositions. SIAM Review, 53 (2):217-288, 2011. 20
Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. Annals of Statistics, 50(2):949, 2022. 35
Tyler I. Hayes and Christopher Kanan. Lifelong machine learning with deep streaming linear discriminant analysis. In IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops, 2020. 33
Reinhard Heckel. Provable continual learning via sketched Jacobian approximations. In International Conference on Artificial Intelligence and Statistics, 2022. 33
Dan Hendrycks, Steven Basart, Norman Mu, Saurav Kadavath, Frank Wang. Evan Dorundo, Rahul Desai, Tyler Zhu, Samyak Parajuli, Mike Guo, et al. The many faces of robustness: A critical analysis of -iitriiiiitttoonnn generalization. In IEEE/CVF International Conference Computer Vision, 202 8, 36
Dan Hendrycks, Kevin Zhao, Steven Basart, Jacob Steinhardt, and Dawn Song. Natural adversarial examples. In IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2021b. 8, 36
Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators. Neural Networks, 2(5):359-366, 1989. 34
Neil Houlsby, Andrei Giurgiu, Stanislaw Jastrzebski, Bruna Morrone, Quentin De Laroussilhe, Andrea Gesmundo, Mona Attariyan, and Sylvain Gelly. Parameter-efficient transfer learning for nlp. In International Conference on Machine Learning, 2019. 33
Edward Hu, yelong shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. LoRA: Low-rank adaptation of large language models. In International Conference Learning Representations, 2022. 33
12

---

Published as a conference paper at ICLR 2025
Hong Hu, Yue M Lu, and Theodor Misiakiewicz. Asymptoties of random feature regression beyond the linear scaling regime. Technical report, arXiv:2403.088 3.0860 [stat.ML], 2024. 39
Guang-Bin Bonan--Bin Huang, Qin- Yu Zhu, and Chee-Kheong Kheong Siew. Extreme learning machine: new learning scheme of feedforward neural networks. IEEE International Join! Conference on Neural Networks, volume 2, pp. 985-990, 2004. 34
Guang-Bin Huang, Yu Zhu, and Shee-KKhengg Siew, Extreme learning machine: Theory and applications. Neurocomputiing. 70(1-3):489-500 2006. 34
Ningyuan Huang, David W Hogg, and Soledad Villar. Dimensionality reduction, regularization, and generalization overparameterized regressions. SIAM Journal on Mathematics of Data Science, (1):126-152, 2022. 8, 35
Laura Hucker and Martin Wahl. note on the prediction error of principal component regression in high dimensions. Theory of Probubility and Mathematical Statistics, 109:37-53, 2023,
Like Hui and Mikhail Belkin. Evaluation of neural architectures trained with square loss vs cross- entropy in classification tasks. In International Conference on Learning Representations, 2021.
Katarzyna Janocha and Wojciech Marian Czarnecki. On loss functions for deep neural networks in classification. Technical report, arXiv: 172.05770 [cs.LG], 2017, 8
Paul Janson, Wenxuan Zhang, Rahaf Aljundi, and Mohamed Elhoseiny. A simple baseline that questions the of setrained-modee. in continual learning. In NeurIPS 2022 Workshop Distribution Shifts: Connecting Methods and Applications, 2022. 32
Menglin Jia, Luming Tang, Bor-Chun Chen, Claire Cardie. Serge Belongie, Bharath Hariharan, and Ser-Nam Lim. Visual prompt tuning. In European Conference on Computer Vision, 2022. 33
Moritz.Jira, Stanislav Minsker, Yiqiu Shen, and Martin Wahl. Concentration and moment inequalities for heavy-tailed random matrices. Technical report, arXiv:2407. 12948 imath.PRJ, 2024.
Dahuin Jung, Dongyoon Han, Jihwan Bang, and Hwanjun Song. Generating instance-level prompts for rehearsal-free continual learning. In IEEE/CVF International Conference on Computer Vision, 2023. 1, 33
Doyoung Kim, Susik Yoon, Dongmin Park, Youngjun Lee, Hwanjun Song. Jihwan Bang, and Jae-Gil Lee. One size fits all for semantic shifts: Adaptive prompt tuning for continual learning. In International Conference Machine Learning, 2024. 1, 33
James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei Rusu, Kieran Milan, John Quan, Tiago Ramalho. Agnieszka Grabska-Barr Barwinska, et al. Overcoming catastrophic forgetting in neural networks. Proceedings of The National Academy of Sciences, 114 (13):3521-3526 2017. 32
Vladimir Koltchinskii and Karim Lounici. Concentration inequalities and moment bounds for sample covariance operators. Bernoulli, pp. 110-133, 2017.
Jonathan Krause, Michael Stark, Jia Deng, and Li Fei-Fei. 3D object representations for fine-grained categorization. In IEEE International Conference on Computer Vision (ICCV) Workshops, 2013.
8, 36
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Technical report, Toronto, ON, Canada, 2009. 8, 36
Avraham Levey and Michael Lindenbaum. Sequential karhunen-loeve basis extraction and its application to images. IEEE Transactions on Image Processing, 98):137711374, 2000. 19
Chuqiao Li, Zhiwu Huang, Danda Pani Paudel, Yabin Wang, Mohamad Shahbazi. Xiaopeng Hong, and Lue Van Gool. A continual deepfake detection benchmark: Dataset, methods, and essentials. In /EEF/CVF Winter Conference Applications of Computer Vision, 2023. 36, 39
13

---

Published as a conference paper at ICLR 2025
Gang Li, Wendi Yu, Yao Yao, Wei Tong, Yingbin Liang, Qihang Lin, and Tianbao Yang. Model developmental safety: A retention-centric method and applications in vision- language models. Technical report, arXiv:2410.03955 [cs.LG], 2024. 32
Qiuwei Li, Zhihui Zhu, and Gongguo Tang. Alternating minimizations converge to second-order optimal solutions. In International Conference on Machine Learning, 2019. 33
Yan-Shuo Liang and Wu-Jun Li. InfLoRA: Interference-fres low-rank adaptation for continual learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2024. 33
Sen Lin, Peizhong Ju, Yingbin Liang, and Ness Shroff. Theory on forgetting and generalization of continual learning. In International Conference on Machine Learning, 2023. 33
Xialei Liu, Awesome incremental learning / lifelong learning. http::/htttttttteeeeeeeeett /https://////// / / thub. com/
xi alielii i www.///wweee--eoeeeeeeeee.oeeeee incementaa --eaarrm ng, 2024. Accessed: August 2024. 32
Vincenzo Lomonaco and Davide Maltoni. CORe50: new dataset and benchmark for continuous object recognition. In Conference on Robot Learning, 2017. 36,
David Lopez-Paz and Marc' Aurelio Ranzato. Gradient episodic memory for continual learning. Advances in Neural Information Processing Systems, 2017. 32
Ashwani Kumar Malik, Ruobin Gao, MA Ganaie, Muhammad Tanveer, and Ponnuthurai Nagaratnam Suganthan. Random vector functional link network: recent developments, applications, and future directions. Applied Soft Computing, 143:1 10377, 2023. 34
Mark D McDonnell, Dong Gong, Amin Parvaneh, Ehsan Abbasnejad, and Anton van den Hengel. RanPAC: Random projections and pre-trained models for continual learning. Advances in Neural Information Processing Systems, 2023. 2, 7, 8, 10, 34, 36, 39
Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and the double descent curve. Communications on Pure and Applied Mathematics, 75 (4):667-766, 2022. 35
Thomas Mensink, Jakob Verbeek, Florent Perronnin, and Gabriela Csurka. Distance-basee image classification: Generalizing to new classes at near-zero zero cost. IEEE transactions on pattern analysis and machine intelligence, 35(11):2624-2633 2013. 32
Hancheng Min, Enrique Mallada, and Rene Vidal. Early neuron alignment in two-layer ReLU networks with small initialization. In International Conference on Learning Representations, 2024.
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. 7,8
Seyed Iman Mirzadeh, Arslan Chaudhry, Dong Yin, Huiyi Hu, Razvan Pascanu, Dilan Gorur, and Mehrdad Farajtabar. Wide neural networks forget less catastrophically. In International Conference on Machine Learning, 2022. 39
Aristeidis Panos, Yuriko Kobe, Daniel Olmeda Reino, Rahaf Aljundi, and Richard E. Turner. First session adaptation: A strong replay-free baseline for class-incremental learning. In IEEE/CVF International Conference on Computer Vision, 2023. 7,32
Y-H Pao and Yoshiyasu Takefuji. Functional-link net computing: theory, system architecture, and functionalities. Computer, 25(5):76-79) 1992. 32, 34, 35
German Parisi, Ronald Kemker, Jose Part, Christopher Kanan, and Stefan Wermter. Continual lifelong learning with neural networks: A review. Neural Networks, 113:54-71, 2019. 32
Binghui Peng and Andrej Risteski. Continual learning: A feature extraction formalization, an efficient algorithm, and fundamental obstructions. In Advances in Neural Information Processing Systems, 2022. 1, 33
14

---

Published as a conference paper at ICLR 2025
Liangzu Peng and René Vidal. Mathematics of continual learning. Technical report, arXiv:2504.1796 [cs.LG], 2025.
Liangzu Peng, Paris Giampouras, and René Vidal. The ideal continual learner: An agent that never forgets. In International Conference on Machine Learning, 2023. 2, 8, 19, 39
Xingchao Peng, Qinxun Bai, Xide Xia, Zijun Huang, Kate Saenko, and Bo Wang. Moment matching for multi-source domain adaptation. In IEEE/CVF International Conference on Computer Vision, 2019. 36,39
Ameya Prabhu, Shiven Sinha, Ponnurangam Kumaraguru, Philip HS Torr, Ozan Sener, and Puneet Dokania. RanDumb: A simple approach that questions the efficacy of continual representation learning. Technical report, arXiw:2402.0882332 (es.CV], 2024. 7, 32, 33
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. Advances in Neural Information Processing Systems, 2007. 33, 35
Rahul Ramesh and Pratik Chaudhari. Model zoo: A growing brain that learns continually. In International Conference Learning Representations, 2022. 33
Sylvestre-Alvis Rebuffi, Alexander Kolesnikov, Georg Sperl, and Christoph H Lampert. iCaRL: Incremental classifier and representation learning. In IEEE Conference on Computer Vision and Pattern Recognition, 2017. 32
David A Ross, Jongwoo Lim, Ruei-Sung Lin, and Ming-Hsuan Yang. Incremental learning for robust visual tracking. International Journal of Computer Vision, 77:125 2008. 19
Anurag Roy, Riddhiman Moulick, Vinay K Verma, Saptarshi Ghosh, and Abir Das. Convolutional prompting meets language models for continual learning. In /EFE/CVF Conference on Computer Vision and Puttern Recognition, 2024. 1,33
Andrei Rusu, Neil C Rabinowitz, Guillaume Desjardins, Hubert Soyer, James Kirkpatrick, Koray Kavukcuoglu, Razvan Pascanu, and Raia Hadsell. Progressive neural networks. Technical report, trXiv:1606.04671V [cs.LG] 2016. 33
Paul Ruvolo and Eric Eaton. ELLA: An efficient lifelong learning algorithm. In International Conference Machine Learning, 2013. 32
Gobinda Saha, Isha Garg, and Kaushik Roy. Gradient projection memory for continual learning. In
International Conference on Learning Representations, 2021. 32
Ali H Sayed. Adaptive Filters. John Wiley & Sons, 2008. 7
Wouter F Schmidt, Martin A Kraaijveld, Robert PW Duin, et al. Feed forward neural networks with random weights. In International Conference on Pattern Recognition, 1992. 3, 34, 35
Khadija Shaheen, Muhammad Abdullah Hanif, Osman Hasan, and Muhammad Shafique. Continual learning for real-world autonomous systems: Algorithms, challenges and frameworks. Journal of Intelligent & Robotic Systems, 105(1):1-333 2022. 32
Haizhou Shi, Zihao Xu, Hengyi Wang, Weiyi Qin, Wenyuan Wang, Yibin Wang, and Hao Wang. Continual learning of large language models: comprehensive survey. Technical report, MxXi:22404.16788 [cs.LG], 2024. 32
James Seale Smith, Leonid Karlinsky, Vyshnavi Gutta, Paola Cascante-Bonilla, Donghyun Kim, Assaf Arbelle, Rameswar Panda, Rogerio Feris, and Zsolt Kira. CODA-Prompt: Continual decomposed attention-based prompting for rehearsal-free continual learning. In IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2023. 1, 8, 33
Hai-Long Sun, Da-Wei Zhou, Han-Jia Ye, and De-Chuan Zhan. PILOT: A pre-trained model-based continual learning toolbox. Technical report, arXiv:2309.0711 [cs.LG], 2023. 8, 36, 38
William Swartworth, Deanna Needell, Rachel Ward, Mark Kong, and Halynn Jeong. Nearly optimal bounds for cyclic forgetting. Advances in Neural Information Processing Systems, 2023. 34
15

---

Published as a conference paper at ICLR 2025
Yuwen Tan, Qinhao Zhou, Xiang Xiang, Ke Wang, Yuchuan Wu, and Yongbin Li. Semantically- tuning is a continual vitransformer. In IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2024. 33
shifted incremental adapter- adapter-tuning
Yu-Ming Tang, Yi-Xing Peng, and Wei-Shi Zheng. When prompt-based incremental learning does not meet strong pretraining. In /EEE/CVF Interational Conference on Computer Vision, 2023. 1, 33
Matus Telgarsky. Feature selection with gradient descent two-layer networks in low-rotation regimes. Technical report, arXiv:2208.02788 [cs.LG]] 2022. 2
Michael E Tipping and Christopher M Bishop. Probabilistic principal component analysis. Journal of the Royal Statistical Society Series B: Statistical Methodology. 61(3):611-622, 1999. 6
Alexander Tsigler and Peter L Bartlett. Benign overfitting in ridge regression. Journal of Machine Learning Research, 24 241123):1-76, 2023. 35,41 41
Gido M van de Ven, Tinne Tuytelaars, and Andreas Tolias. Three types of incremental learning. Nature Machine Intelligence, 4(12):1185-111) 2022. 32
René Vidal, Yi Ma, and Shankar Sastry. Generalized Principal Component Analysis. Springer, 2016.
Catherine Wah, Steve Branson, Peter Welinder, Pietro Perona, and Serge Belongie. The Caltech- UCSD birds-200-2011 dataset. Technical report, California Institute of Technology, 2011. 8, 36
Martin Wainwright. University Press, 2019.
Statistics: A Non-Asymptotic Viewpoint. Cambridge
Lipo P. Wang and Chunru R. Wan. Comments "the extreme learning machine".. IEEE Transactions on Neural Networks, 1944)14944, 2008. 34
Liyunn Wang, Jingyi Xie, Xingxing Zhang, Mingyi Huang, Hang Su, and Jun Zhu. Hierarchical decomposition of prompt-based continual learning: Rethinking obscured sub-optimality. Advances in Neural Information Processing Systems, 2023. 3,
Liyuan Wang, Xingxing Zhang, Hang Su, and Jun Zhu comprehensive survey of continual learning: Theory, method and application. IEEE Transactions on Pattern Analysis and Machine Intelligence, 46(8):5362-5388 2024. 32
Yabin Wang, Zhiwu Huang, and Xiaopeng Hong. S-prompts learning with pre-trained transformers: An occam's 's razor for domain incremental learning. Advances in Neural Information Processing Systems, 2022a. 1, 33
Zhen Wang. Liu Liu, Yiqun Duan, Yajing Kong, and Dacheng Tao. Continual learning with lifelong vision transformer. In IEEE/CVF Conference Computer Vision and Pattern Recognition, 2022b.
1,33
Zifeng Wang, Zizhao Zhang, Sayna Ebrahimi, Ruoxi Sun, Han Zhang, Chen Yu Lee, Xiaoqi Ren, Guolong Su, Vincent Perot, Jennifer Dy, et al. DualPrompt: Complementary prompting for rehearsal-free continual learning. In European Conference on Computer Vision, 2022c. 1, 8, 33
Zifeng Wang, Zizhao Zhang, Chen- Yu Lee, Han Zhang, Ruoxi Sun, Xiaoqi Ren, Guolong Su, Vincent Perot, Jennifer Dy, and Tomas Pfister. Learning to prompt for continual learning. In IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2022d. 2,
Andrew R Webb and David Lowe. The optimised internal representation of multilayer classifier networks performs nonlinear discriminant analysis. Neural Networks, 344) 1990. 34
Ross Wightman. Pytorch image models. https:// com rw1 www.a//n///////mmmmmmmmmm
wwwpchhh-mmammmmmmmee 2019.
Xu and Daniel J Hsu. On the number of variables to use in principal component regression. Advances in Neural Information Processing Systems, 2019. 8, 35
16

---

Published as a conference paper at ICLR 2025
Shipeng Yan, Jiangwei Xie, and Xuming He. DER: Dynamically expandable representation for class incremental learning. In JEEE/CVF Conference on Computer Vision and Pattern Recognition, 2021. 2, 32
Jachong Yoon, Eunho Yang, Jeongtae Lee, and Sung Ju Hwang. Lifelong learning with dynamically expandable networks. In International Conference on Learning Representations, 2018. 33
Guanxiong Zeng, Yang Chen, Bo Cui, and Shan Yu. Continual learning of context-dependee processing neural networks. Nature Machine Intelligence, 1(8):644-33 372, 2019. 32
Hongyuan Zha and Horst D Simon. On updating problems in latent semantic indexing. SIAM Journal Scientific Computing, 21(2):88-7791 1999. 19
Xiaohua Zhai, Joan Puigcerver, Alexander Kolesnikov, Pierre Ruyssen, Carlos Riquelme, Mario Lucic, Josip Djolonga, Andre Susano Pinto. Maxim Neumann, Alexey Dosovitskiy, et al. A large-scale study representation learning with the visual task adaptation benchmark. Technical report, arXiv: 1910.04867v2 [cs.CV], 2019. 8, 36
Gengwei Zhang, Liyunn Wang, Guoliang Kang, Ling Chen, and Yunchao Wei. SLCA: Slow learner with classifier alignment for continual learning on a pre-trained model. In IEEE/CVF International Conference Computer Vision, 2023. 33
Yuanhan Zhang, Zhenfei Yin, Jing Shao, and Ziwei Liu. Benchmarking omni-vision representation through the lens of visual realms. In European Conference on Computer Vision, 2022. 8, 36
Xuyang Zhao, Huiyuan Wang, Weiran Huang, and Wei Lin. A statistical theory of regularization- based continual learning. International Conference on Machine Learning. 2024. 34
Da- Rei Zhou, Han-Jia Ye, De-Chuan Zhan, and Ziwei Liu, Revisiting class-incremental learning with pre-trained models: Generalizability and adaptivity are all you need. Technical report, arXiv:2303.0733 [cs.LG], 2023. 2, 8, 32, 33, 36
Da- Wei Zhou, Hai-Long Sun, Han-Jia Ye, and De-Chuan Zhan. Expandable subspace ensemble for pre-trained model-basee class-incremente learning. In IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2024a. 2, 8, 9, 33, 37, 38
Da- Wei Zhou, Qi- Wang, Zhi-Hong Qi, Han-Jia Ye, De-Chuan Zhan, and Ziwei Liu. Class- incremental learning: A survey. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2024b. 32
Huiping Zhuang, Zhenyu Weng. Hongxin Wei, Renchunzi Xie, Kar-Ann Toh, and Zhiping Lin. ACIL: Analytic Blas--nncrmmnntal learning with absolute memorization and privacy protection. Advances in Neural Information Processing Systems, 2022. 7
Huiping Zhuang. Zhenyu Weng, Run He, Zhiping Lin, and Ziqian Zeng. GKEAL: Gaussian kernel embedded analytic learning for few-shot class incremental task. In IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2023. 7
17

---

Published as a conference paper at ICLR 2025
A
OVERVIEW OF THE APPENDIX
Appendix we complie all the mathematical notations used throughout the paper.
In Appendix C we describe the implementation details of LoRanPAC. There, we also discuss other potential implementations and our design choice.
In Appendix D, we present auxiliary lemmas that are useful for proving our main theorems.
Appendix E, we prove the theorems displayed in the main paper (Theorems and 2).
In Appendix we present results similar Appendix E, with the difference that we now assume the noise is Gaussian, which gives slightly tighter error bounds.
In Appendix G, we prove some extra theoretical results such as perturbation bounds on eigenvalues and eigenvectors (Theorem 6).
In Appendix H review related works continual learning, focusing CL methods with pretrained models and existing theoretical developments.
In Appendix we report the statistics of the datasets we use for experiments.
In Appendix we specify the experimental setup.
In Appendix K we report extra experimental results, figures, and tables.
B
NOTATIONS
Here in Table we compile all the notations used in the paper.
Table 3: Notations
d
dimension of pre-trained features embedding dimension
E
m,
number of training samples for task
Me
mi + ................................ + my
total number of classes in the first tasks
total number of tasks Gaussian distribution with
1)
and variance 1
F
the ceiling operator, which maps number to the closest integer no smaller than it
E x F. identity matrix
X,
x my matrix, whose columns are output features pre-trained models E' x d random embedding matrix with N 1) entries Random ReLU features relu(PX, (X,) as defined in (1)
P
He
A
ridge regularization parameter in RanPAC
B.
the matrix whose SVDs are truncated by Algorithm defined in (3) the number of singular values and vectors preserved for the first / tasks function that computes best rank-k; approximation of matrix the k-th largest eigenvalue of symmetric matrix
ki
(H.())
pa()
Un VIT.
SVD of His
UI V
SVD of Ti, (Hıa) SVD factors of B,
lit
UH., E1:t
41
accumulative error defined in (6)
%
the eigengap between the present and past, defined in (5)
18

---

Published as a conference paper at ICLR 2025
C IMPLEMENTATION DETAILS FOR LORANPAC
In this section, we give full details of our algorithm for LoRanPAC. Note that Algorithm 1 of the main paper is concise version of our approach, used illustrate the methodology at high level.
In Appendix C.I, we introduce Algorithm 2, our implementation of the incremental SVD approach. Note that Algorithm 2 dates back least to Bunch & Nielsen (1978) and has been applied to image processing, computer vision, and latent semantic indexing (Zha & Simon, 1999; Levey & Lindenbaum, 2000; Brand, 2002: Artac et al., 2002; Ross et al., 2008). Recently link between continual learning and incremental SVD was built (Peng et al., 2023). However, it has not been applied to the context we consider here to the best of our knowledge, and suitable modifications are needed to incorporate incremental SVD for solving LoRanPAC satisfactorily. For example, we truncate the SVD factors in each continual update as shown Algorithm 2, and the outputs (U1.. Σ1:1) of Algorithm are not necessarily equal to the top-k, SVD factors of H... It is then our contribution to arm Algorithm 2 with theoretical guarantees (ef. Lemma and Theorem 6).
In Appendix C.2, we introduce Algorithm 4, a continual learning method that stably solves LoRan- PAC.
C.I INCREMENTAL. TRUNCATED SVD
We first explain the design choice as suggested by (2): Should we maintain all SVD factors UL., ELa, and Vis.. or should we just maintain the singular values En, and and left singular vectors U. In the main paper, we suggested taking the latter choice, as we empirically found continually updating all SVD factors U U.. Le and Vi. lead to large test errors.
We now describe how to update the top Ke SVD factors ÜL., Ens from the previous estimates Un.-1 1, E and new data H. Let QuRe be the QR decomposition of (Ig Ua- 1 H,
Then we have
U H.)
Ü Un-1 Q.1
Σ E1a-1
U., H. R
Note that 11-11 Q:) is already orthogonal, we do truncated SVD the smaller (k₃-1 me) x (kr-1 + m²) matrix of the right-hand side. The full procedure is summarized below:
Algorithm 2: Incremental Truncated Singular Value Decomposition
Input: data matrix H, E R Exm, of task t, desired output rank k; S min E, Mr} (M; := + ... m.), truncated SVD factors UI:-1 RR Ex and Σ E R of the previous
1 tasks;
Compute the QR decomposition R₂ of (Lg - 1
Set (Eupp: Ummp) to the top-h; SVD components of
Algorithm
Σ EiS-1 Ú, Hi R.
E (M+ (+m 1mm))
(12)
0
Set Σ1 +- Sump and Ün + -Ü Q:IU ump: U1.t +- The orthogonal factor of QR decomposition of Un:t: Output: (Ur,, Σ1.);
I/ improve numerical stability
Remark 4. Since [Ū12-1 Q.) and Ummp are orthogonal, ÜL. is expected to be orthogonal as well. However, the multiplication U. [Ü,- Ummp might lose orthogonality due numerical errors, especially when gets large. This is fixed by an extra post-processing step that orthogonalizes U..-
Memory Complexity Analysis. The extra working memory of this approach is roughly:
O(Em + mf), for the QR factors Q, RG;
O((ke1 + 2)) for the matrix in (12) and its SVD factors;
19

---

Published as a conference paper at ICLR 2025
Algorithm 3: Truncated Singular Value Decomposition (TSVD)
Input: matrix H E IR and desired output rank r S min E, m]; tmp < min E, m):
Compute the SVD 1 + +... +...... Tump ump of H::
Set Σ (I,... U + [ur...., U.]:
Output:
Hence, for large E, this is less than the O(E(ki-1 + m²)) memory used by the direct SVD method.
Time Complexity Analysis. The major cost is the SVD of (12), which takes O(kk-1 + m,)² time. While in principle the QR orthogonalization for the post-processing of Ü1: takes (EE(k,1 m.) time, it is significantly faster than SVD as the constants behind its O()) is very small. Therefore, one would expect the SVD on the matrix of (12) in O(kk)-1 + m2)²) time should much faster than the SVD on the matrix [Ü E He), which needs (K + m²)²) time, where E' is far larger 10 and - 1 + my 104). This true on a sequential machine, but their running time difference is not significant for highly parallel GPU implementations in our experience (e.g., computing the inner product between two E-dimensional vectors has similar running times to computing the inner product between (hi-1 + m& )di--minnsio vectors, due to parallelism). Hence, for a parallel implementation, the main advantage of doing SVD on the matrix (12) is that it takes H.].
than h 1 + my (e.g.,
less working memory than SVD on [U
Remark 5. Algorithm 3 can, in fact, be implemented by randomized linear algebra techniques (Halko et al., 201 1). Some of these techniques compute by design only the top & SVD factors. Intuitively this could save time and memory if A is very small. One such method is conveniently implemented in PyTorch at using randomized approaches, we found this Py Tyrrhhh routine does not seem to be as efficient or accurate our present implementation (we consistently set truncation percentage Ç to 25%).. This observation aligns with the Py PyTorch document of torch.svd. sevvd_llwwwr lowrank: In general, use the full- linalg. svd(( for dense matrices due its 10-fold higher performance characteristics. The low-rank SVD will be useful for huge sparse matrices that torch. linalgi cannot handle. For the moment, we conclude that it needs deeper investigations to see whether randomized techniques are suitable for the continual learning contexts.
well (torch. svd. 1 lowrank). However, in our rudimentary attempts
rank SVD implementation torch. corch.linalg.ss
C.2 CONTINUAL SOLVER FOR LORANPAC
The proposed algorithm is shown in Algorithm 4. Here are a few details that we have not yet mentioned in the main paper. First, note that Algorithm 4 formally updates Mr ad Jj continually. At Line 8 of Algorithm 4 we compute the label-featur feature covariance matrix J1 := H, e Ra x F. and then at lines 10 and 11 we update J:-1 into J. via J, <- Jt-1 + Jump The attentive reader might find that J 1 is of size G-1 x F while Jump is of size Ct x E. But it could be that Q-1 < ct so it might not make sense to add J;-1 and Jump as in Line 11. Note that we wrote Line 11 just for simplicity. The implementation would pad c Ct-1 zero rows to Jz-1 in a similar fashion to how we extend Y into Y, when more classes are given, and this is what Line 11 should mean.
Second, we add an extra parameter Tmax. Taa to control the maximum allowable rank, that is the maximum number of columns U1: is allowed to have. The purpose is to control the time complexity of Algorithm and allow it to run more efficiently on large datasets such as DomainNet (cf. Tables and 8). We argue both the truncation percentage Ç and maximum allowable rank Tmax are needed: With C alone, the method might run slowly or even exceed the memory for large datasets such as DomainNet (cf. Tables 7 and 8): with Fmax alone, truncation is not activated before receiving Tmax samples, and numerical instability if it arises, can not be prevented before truncation is effect. Table 4 gives the values of & and Taux use for each dataset.
20

---

Published as a conference paper at ICLR 2025
Dataset
Truncation Percentage { Embedding Dimension E
Maximum Allowable Rank 7max
CIFAR100
25%
10a
10000
ImageNet-R
25%
10a
10000
ImageNet-A
25%
10a
10000
CUB-200
25%
10
10000
ObjectNet
25%
10a
20000
OmniBenchmark
25%
10a
20000
VTAB
10a
10000
StanfordCars
25%
10a
10000
Table 4: Hyperparameters we use for each dataset.
Algorithm 4: Continual Solver of LoRanPAC (concise version Algorithm 1)
Input of Task t: Random ReLU features H; E gExm, label matrix Y; E Rexxm, truncation percentage Ç [0, 1], maximum allowable rank Ymaxi
For t + 1, ....
Mr Mr-1 mH:
update the total number of samples M. // perserve k SVD factors for the first tasks
d <- min(rmax: (1 -1- ())))
Form B, per (3);
(ÜI:: E1:) +- Top-k, SVD factors of B;; // use Algorithm 3 ift = 1, or Algorithm 2 if >>
If tft=1; = 1:
I/ Continual update of Jj = H 1:t llbel- covariance of task
J1 + Output Algorithm run with inputs H1, Y1;
Else:
10
J Jump + Output of Algorithm run with inputs He, Yo:
label-feature covariance
J. - J,-1 Jump
Form the linear classifier W, = J. (UIT
I/ cf. (2) and (4)
D AUXILIARY LEMMAS
The following lemma provides an explicit expression for the difference between the continually truncated factors Ú Ei UT, and covariance H H.
Lemma Let B, be the matrix whose SVDs are truncated by Algorithm 4, as defined (3). We have U, = U1 and E₁ = Σ,. Moreover, we have
H HIgH -U Σ (B. - Tky (B.BT)
Proof of Lemma 1. It should be clear that U, Ü, and Σ, = Ej. For every i = 1,... / we have
Ü. Th. (B.B.).
and therefore
-BB, = (B.B.) B.B.T
21

---

Published as a conference paper at ICLR 2025
Algorithm 5: Compute The Label-Feature Covariance Matrix
Input: matrix H = [ hm] E TR Bxm and label matrix Y E R
Convert Y into a vector of indices y yy:,.... ym such that the i-th column of Y is the y/-th standard basis vector (i.e., one-hot vector with 1 at position yi);
Initialize S
;9....,88]] to be the x zero matrix; // parallel implementation via torch. Tensor, index_add__
For i ,,....
Sy. f- S, + h4;
Output: S
I| S is equal to HY
key observation that summing the above equality over = 2, ....,. yields
Σ 1=2
-
Σ (B. - -B,B,)
Σ
- H,H,J) = = (TK, (B.B.) - B,B,)
1m2
im2
+
- - H2 H Σ
(Th, (B.B,) -BB,))
(13)
1=2
* U
- H Σ
Thi (B.B.) - -BB,)
1=2
+ U H H. Σ (Th, -B.B.)-BBB))
The last equality also holds for = 1. This finishes the proof.
The lemma below is direct consequence of Von Neumann's trace inequality, and its proof omitted. Lemma 2. Given two square matrices A, B with A positive semidefinite, we have
tr(AB) I tr(4) B|].
Lemma 3 presented below is elementary.
Lemma 3. Assume C' is positive semidefinite matrix. Then we have
tr tr(DDCBD") + tr(DBT CA D S tr(DACA DJ) + tDDBCB DJ), where A, B,C, D are matrices of compatible sizes. Therefore, it holds that tr (D(A+ + B)C(A+ s 2tr((DAA DT) + 2tr(DBCB DT).
The following two lemmas provide upper bounds on several terms appearing naturally in our main results.
Lemma 4. Let B, be defined (3), 7tt in (5), and at in (6). Define
D. = Σ B.B. - Th. (B.B.)
(14)
We have
D D.U ÜT 1:t
8 8-1
5
7t
U D.|
<
?t
ir
(,Ü
<
1
min f MM
kt-1, 1)ke)
7
(D.Ü..E,.UÜT))
1
min (M-11 ke-2, 1)ki}.
pk. B,B.)
7t
22

---

Published as a conference paper at ICLR 2025
Proof of Lemma 4. It follows from definition that
(B.B.- Th, (B.B.)) Una
hence D = D1-1U1a- This means
D.. = Di_ U - 1T:
I D|lil || | -
= -| Huc (B.B,)'
where the last equality follows by definition. On the other hand, we have
(t-1) pkz (B.B.).
| S Σ (B,
%
Combining the above proves the first required equality. The second inequality follows similarly. For the final trace inequality, we have (Ku 0)
tr (D.ÜU..5,:7..)) = tr (D- ST: U
S (r((Di-1)
Un: S 2 ÜT!
(-1 1 metki
Σ
My (,(BBB.))
Mky BB. B.)
j k
t-1
$
m, + 14-1- - kz)
7tt
1 (M-- k(-1);
7t
where (i) holds as D.-1 positive semidefinite (ef. Lemma 2).
We can also bound ir E 1.t alternatively as follows:
tr 1.
< D D tr ET
1)ke
Combining the two bounds tr (D.Ü proves the third inequality. The fourth inequality follows similarly.
Lemma 5. Using the notations in Lemma 4, we have
tr (D, 1.t D.Ü s 1-1
min {M--1
1)ke t 1-1
h2-1, (t
(t-1)
D,Ü E E 1:
UT 1:1
D. S 1
1:1
7
7
[TE - U H (L.
U.. |t) || S at.
t
1
2
|  | <
+
_
min {M,- kr-1, (t 1)kie} ke
71
1
min (M--1 kK-1, 1)ke ks
[U U
1k.
(BBB.)
7t
23

---

Published as a conference paper at ICLR 2025
Proof of Lemma S.
Since Di-1 is positive semidefinite, let 1 be its Cholesky decomposition.
Then we have
tr "D
tr tr (D.
tr (4-1
tr (LI,
S tr (L_,Ü
tr (
E -ū اا-1
min { MM- h (t (t- }
L 1:t L,
7t
In the above, (i) follows from Lemma 2, and (ii) follows from Lemma 4. Continuing with the above incquality, we have
1
L, ||
Pk. (B.
1 Pk. (B.B!)
D|
7
Recall the fact D,U D.-1U The second inequality in Lemma 5 can be proved follows:
D. U
D,Ur, P
D,U DA S.UT, D. D. -
|D,-Ill
D. D D.
U D.
0a--1" 1)-
7t In the above, (i) follows from Lemma 1. The third inequality is proved follows:
(I Ün.U H..H.
H H (Ig (IE--,,Ü
(I Ü,,UT, - -,,5 Ü....:)
(Ig Ü, -
- Ú,,ū,,1
< D = az.
We now prove the fourth inequality:
H 1.t E H 1st
H
@ tr (D,Ü,,
S- Ü,:
tr (D.Ü
14 U. 2D.U S. UT) + ke
m
(t-1 + 2
min (M,1 - h (t- 1)k + kr-
2
?t
24

---

Published as a conference paper at ICLR 2025
In the above, (i) follows from Lemma and (ii) follows from Lemma 4 and the first inequality just proved for Lemma 5.
The fifth inequality can be proved as follows:
Ü H E tr
U
tD, Σ :t
U + tr Σ (
ht
min {M-1 1 (t 1)ke) +
Mk.
(B,B.)
Pk. [B, B, B,)
Here, (i) holds as a result of Lemma and (ii) follows from Lemma
Lemma 6. Using the notations in Lemma we have for any W that
WHH U.. IM, H 2 | a +
at-1(t 1)
at
at-1(t-13 1)2 78
7
Proof. We have
Ui IM, Hu.
=tr -t((WHH::HH,,, E U.. I,, Hi H (U. En H. [M)(W)
tr (W + Ü. - Is)H (Ü, S ÜN.UT. - Ie)(w))
22 (
2
S
D.
am)
22 WI [[[
U
(1 U ū
+2 W
D.Ü
U
(9)
(t (t-1)- 1)a t-1
S 2-
WIF + 2
W c d
n
WI
a ae
a (t 1)
7
In the above. (i) follows from Lemma 1, (ii) from Lemma 3, (iii) from Lemma 2, and (iv) from Lemma 5. The proof is complete.
E PROOFS OF THEOREM 1 AND THEOREM 2
Proof of Theorem 1. Let IM, be the M, x M, identity matrix. The training loss can be written
W.H - Yielf
YY - H - Yi
U H I | U 2 Ú
=I(W; H Exd) (H Un E - H IMs Il
2 ||; HH Un ST. Ü IM, H + 2 [ U S1 UT,H
H1g IM.)
We can now bound the first term by Lemma 6 follows:
< | + a-1((t -
a- - 1)2 -1)2
W H H U E
20 I.. H
+
7t.
7
25

---

Published as a conference paper at ICLR 2025
The second term is bounded above as follows:
|| Una U H 1 )
2 ||Eue| (H U H12 (Ms 3
S || ( Me - kip n/
min {M-- 1 (1)x))))) (1-))(())))
where the first inequality follows from Lemma 2 and the last inequality from Proposition 1.
Proof of Theorem 2. Define D. = Dim (B.B. - The (B.B.)) Note that D, is a symmetric and positive semi-definite matrix.
Note that we have
y1²]= =1En 18n || -| Wihh wih- ell²]
En
Wih
= En Wih w/hhl?]] + ||e|13
so we next focus on bounding En Wih w:nll7]
With the E E identity matrix Ig and
A = Ehhh ], we have
Ex
WWh wil
Ex
YY. H.HHH D U w/
Ex
[IW; Ea - W; h|l²
[I(W;
u. -
2 En
[[W:
111
+ En [1 0 1. 12 ||]]
2- En
[IW; Una E U
+ 1| 12 En
|H U U. U h1]
The term E, H 1:: - UT, 1122 can be bounded above as follows:
H H A
E,
H. AÜ
"0 H1:
((A
1
1
H
1:t
H
itt
H
H lat
U
H
M
M,
A
Mr
1
HigH
1:t
tr (
S
+
tr
H.
HHiH
- 1:1 1:1
H H 1.1
Un - 11
M.
1 min {Mi-1 kr-1, 1)kee } + kis
1
H H
M, 1:t
Mb, (B.B.)
1
(t-1
2 ) min {M-1 k1-1, (t 1)ke}
he
+ 7.,,
Mr
M
Here, (i) follows from Lemma 2 and (ii) follows from Lemma 5.
26

---

Published as a conference paper at ICLR 2025
The term En
||
E LE)h|?
satisfies:
[ [W: U.. IE)A!|
IE)A (U) H.. (w)))
tr
@ tr
(D, U.. U. TE) E D. Un.Ui (E)(W))
$ 2tr (Wi(On., Is)A(U -
2tr (W: S S ((.)..
01 s 2 [[ - U.. [ UT)AA U Ui.0).))l
2 | ||D - AUL, UT,
where the above three steps, (i), (ii), and (ii), follow from Lemma 1, Lemma 3, and Lemma respectively. To bound B+ == [1{ - U
U1aULD)) we have
BB
[E U. (A
Ün (IE -.,
M
A
1
Ü E U
Mt
1
<
A
H
H
U.
M
M
1
1
A
H
|
Mt
M,
A
1
H
H
at
M
M,
To bound B2,
D.U E UT E ST D:| we have
B22
AÜ 11 20T D.
D.Ur. D. lit
(A-
H H + Mr
HIGH Ü U S.2
M
s
H
H
T
.I 1:1 UTD.D.ll'''
-1. 5-2
Mr
1:t
1
D,U 1at
5-2UT
1:t
H H 1:1
Un E D.
M,
1)2
(
tt [
A
H
(
M.
7t
where the last step follows from Lemma 5. Putting together, have obtained
F
[W; (H H U E 2T 11
2. |
< B₁ + Br2
<
A
H
H T.c
(1+ (t 11-tt11
1)22
a-1
(t-
1)2
+
a:
=: B.
M.
M,
2
7t.
M,
Combining the above finishes the proof.
F THEORETICAL GUARANTEES UNDER GAUSSIAN ASSUMPTIONS
In this section, we prove slightly tighter results than Theorems and 2 presented in the main paper. The key idea is make certain Gaussian assumptions noise. Specifically, assume both the
27

---

Published as a conference paper at ICLR 2025
training noise E1a and test noise have i..d. .N(0, entries. With these, present and prove
Theorems to below.
Theorem 3. On top of the settings of Theorem I, furthermore assume Enit consists of ii.d. NN v²)
entries. Then the output W. H1:H 1n 2 1i of our method (4) satisfies
aj + at-1(-11 + a--1(t- 1)2 a11((-11e
Ees
W.H - Yia | S 2. |W:
(15)
M
Mr
MM
Mr
(Mi-h)
(M, (M--ki ks) (t- (6-1mmin min {M-1 1 1, (t-1)k))
+ cep?
MM
Me
M/
Proof of Theorem 3. Let M, be the Mj x My identity matrix. The training loss be written
Ex W;H Y1:
= -Ee. Y1: 1:t U Σ 1: H lit - Yurlle
LE Y1:e(H 11 1:t
1:1 Hia - 1M
=
BEL. (W; H + E ) H 1:
Ü 12 ET. ÜT His IM, mlll
= -|[W,' (H1: H. Un: 1:t
UT. iit ) H + Re 11 (H
1:1 H IM, 1l
We can now bound the first term by Lemma as follows:
(H, UU. Ia, H 2 11; a 0t-1(1-1)
a a=- (1 - 1)2
+
7
7
The second term can be bounded above as follows:
1 (H U1a UH H IM.))
= Er (H, Un. D U, HIa EM T (H 11,0, U1 " H Ins.)
14 Hig IM. =a,u H 1 --20
1-1
Sap²² (Mr - kt) + qu²²
min {M-- 1 (t 1)kee
The last inequality follows from Proposition 1. Combining the above finishes the proof.
While in Theorem 3 bounds the average training MSE loss LES.. W.H YI an alternative to give a bound on M, Ee, W.H W; Hi:elle- The latter term evaluates the difference between the prediction of W, and the ground-truth W on training data Hy.- The difference between the two terms is that Yi = W." Hist + ELzt is contaminated by noise. We bound M. EE,. W.H W H1a I in the next result.
Theorem 4. On top of the settings of Theorem 1, furthermore assume ELrt consists of ii.d N(O, v²)
L. entries. Then the output W. Y1. H Un. " of our method (4) satisfies
ar or-1(1-1)
04 1 1)2
W.H W; H l S 2 1|
M
Mr
M
78 M,
tav2. ( ke tt-
2
+
min {Me-1 k (t 1)kie)
M₁
nMe
Proof of Theorem 4. We have
Eg... W. H1
EEc. Yı. U E 2 H1s W Hia
= -Eem. W H U E U H1s 1:1 I + En
Ün - H 1: 2
= (HW, U U -M, H lF Een.
1 HT, E ن H1s
28

---

Published as a conference paper at ICLR 2025
The first term is identical to that of Theorem and it remains to bound the second term:
BEa
11 H U
H1: ls
1:1 Un lit H H T H U1 U H1s)
Eg tr
= =cv?
H U1 E 1:: F
t--1 min {M-1 kr-1. (t- 1)ke + avv kr-
S sav.
The last inequality follows from Lemma 5.
Theorem On top of the settings of Theorem 2, furthermore assume both E1st and e consists of i.idd
(O0,v² v²) entries. Then the output W. Y1: H U1 E U of our method (4) satisfies
Wch y s 2- 1 B. + cur 2 V2 + cev.
(16)
where IB and Ve are defined in (10) and also shown below:
[ [+
(+-----))) +
at
+ a1-1(t-1) -
+ ac-1 1)
B, =
A
HI.
His
Mt
7
Mr
78 M2
1 min {M-- - ki-1 (t 1)ke} +he)
V.
A
H H1:H
Mr
ux. (r,(B.Bi
hi
[t-1
2
+
min {Mi-1 Ri- (t)kett
Mr
7M,
Proof of Theorem 5. Recall the definition of D, in (14). Note that D, is a symmetric and positive semi-definite matrix.
Note that for any W E RoxE we have
E [ yı'²] = EE [ - Weh - =
= =E Wh - W; + G.2
Denote by IE the E x E identity matrix. With W. Y. U. ", and Y = W, Hia E1 we obtain
Eca.. ht
W,h hi
Eg
YH:H. 1:t U S 20
E
[I(W;" Hist +
W h2
Eg
[I(W; H l:t + Eyd
S U.h
W h1l
=Ep [[ H
W 1|l2
+ EE
H U Un: -.-
= =Ep [IW (H.
TE)
+qpPEn
HH S 5-2 SU 1|
The rest of the proof is identical to that of Theorem
G ADDITIONAL THEORETICAL RESULTS
Given the weight W. == H.H H. computed by our continual implementation in L Section 3, here we aim derive upper bounds on the training MSE losses W.H Y M, without the linear model assumption Y W. H t El used in the main paper.
29

---

Published as a conference paper at ICLR 2025
First observe that
W.H. H. 1:t Y1 | Un U - -M,
where we recall IAs is the M, M, identity matrix. This motivates us give bound on H U1 20T 1:t H I ) Il::
Proposition 1. It holds for every 2 that (Mu == 0, kg =)
1-1
HI H1: IM Mr Kt
min {M-- 1, 1)ks}
Remark 6. The term M, ke is inevitable as we truncate M, K, eigenvalues. Indeed, Mr
ky is precisely equal to [ 11: 1. H1: M. ll.. and it is the minimum of rank-ka approximation problem:
M, kt min LERM,XK
IL - I..
The term 7 min (M,-1 1, (t 1)kb} arises as we solve LoRanPAC continually rather than offline. With 7/t = 1, this term upper bounded by (t - 1)(M-1 - 14-1). With " = 10 (as
discussed in the main paper), this term is negligible for even hundreds of tasks.
Proof of Proposition 1. From Lemma it follows that HigH T 1:1 Un U Una + D,U D
(17)
where we recall D, defined as D. Ei=1 (B.B. Tk. (B,B,) in (14). Then we have
H U E
IM,
H H.g - S + M,
Hi 2H H1: IMI
tr (Hi.
(UU.ÜÜ, + (UI. + 2.U.. Me
t U.
U1:U111 + Mc
tr (D, E 1.1 D D.
+M+-
@1-1 min [M 1 (t - 1) + M, - kt
where (i) is due to Lemma 5.
A simple corollary of Proposition I now follows:
Corollary 1. The output W, of Algorithm 4 satisfies
W.H YY:eelf |YT Yiall
1-1 ?
[M hi +
min (M-i 12-,, 1)kk,
Mr Remark 7. In classification, the columns of Yi:t are one-hot vectors. Hence, up to permutation, Y Y1a E MM xix is a block diagonal matrix with e, block, where the i-th diagonal block is n, n, matrix of all ones 1n,; here n, is the number of labels in class i. In other words, there cxists a permutation matrix such that
M,
Y Yıa = II diag(1 1 1 Bor
Since the maximum eigenvalue of 1m, is m, know
Y Yuell
max {n:). i=l...
Substitute this into Corollary and we obtain
max:=1..... {n,}
M, W. Y
M k +
min (M,1 ki-1 (t 1)kr
M.
%
30

---

Published as a conference paper at ICLR 2025
It is also of interest to bound the distances between the SVD factors computed online and offline, namely the distances between Ei:t E1:t and between U1a U 1st- We do so in the next result.
Theorem 6. Let at be defined as in (6). Fort 2 1 define
gap; == Pk. (H H4) pk++1 (HIgH1))
(18)
Then it always holds that
E E. S a--1-
(19)
Moreover, af-;1 < <(1 1/V2) gap,. then for any t we have
V24+11
min OEO(K)
Unt
01:0 U Üna
(20)
gap;
where ((k) be the set of k orthogonal matrices, defined
O(k) 10 R -00=00- 1x).
Proof of Theorem 6. It is clear that U, U2 and Σ Σj. We now consider the case 2 Note that U1 E1:U1 the eigen decomposition of Tk. (Un + H,H,)), and
U 1 E1 U lit is the eigen decomposition of Tk. H.)). We can compute
H H (Üno- E + H.H.) -Ia- HI Ün.-11 1
B - The (B.B =: Dr:
where (i) follows from Lemma 1. We can therefore apply Weyl's inequality to obtain
Σ
E
s D a
This proves (19), On the other hand, (20) follows from the Davis-Kahar theorem (Davis & Kahan, 1970), or more precisely, from Corollary 2.8 of Chen al. (2021).
G. RELATION BETWEEN THE OFFLINE AND ONLINE SOLUTIONS
Recall the definitions of the offline solution W, in (2) and the output W, of LoRanPAC in (4):
W. Y.. H.U.U.U U Ex.
U " 1ab
W. Y H. U..
Here we aim to bound the distance IWW Welle. We consider the model Yıa = W; H1: this is the Yi.- W His + E with En... Here make this assumption for simplicity, and the result here can be extended to the case with noise.
Recall the definition of gap, in (18):
gap, Pk. HH. pk,+1 (H
Based on Theorem 6, we prove the following result.
Theorem 7. Let an be defined as (6) and gap, as in (18), Assume a < (1-1//V gap,
Suppose Y W. HIg. Then we have
(Veel-1 +
t-1
W. W SlWill
(21)
gap,
7t
Proof. Note that
H H -U.. 1t
H H.. Ün D.Ü,.
31

---

Published as a conference paper at ICLR 2025
where Dr is defined in (14) and the second equality follows from Lemma 1. So we have
W
W. F
W
1:
H H
U
E U W
H
H 1
(22)
- I|:
HI:H 1it U 1 1:t
H1
(23)
1:0
1:t
UnaU 111 - - - D. E
(24)
S W
- 11 +
D D -
(25)
1. -..-UUn [ + D D.U
S I
(26)
(220-1 + t-1
S I|
(27)
gapt
7
where the last inequality is due to Theorem 6 and Lemma 4. The proof is complete.
H REVIEW OF RELATED WORKS
In Appendix H.l we review related work on CL. Recent surveys on CL include Parisi et al. (2019); van de Ven et al. (2022); Shaheen et al. (2022); Zhou al. (2024b); Wang et al. (2024); Shi et al. (2024). See also the GitHub repo of Liu (2024) for an extensive list of CL papers.
In Appendix H.2 we review related work on random feature models.
H.1 MORE RELATED WORK ON CONTINUAL LEARNING
Many CL methods have been proposed without explicitizing the use of pre-trained models (Ruvolo & Eaton, 2013; Kirkpatrick et al., 2017; Rebuffi et al., 2017; Lopez-Paz & Ranzato, 2017; Zeng et al., 2019; Chaudhry et al., 2019; Yan et al., 2021; Saha et al., 2021; Douillard et al., 2022; Elenter al., 2023). An easy way boost their performance is to adapt them for the context of pre-trained models. There are two natural approaches to do so. One approach is to use the pre-trained model as initialization and run these CL algorithms to fine-tune the pre-trained model; see, e.g., Li al. (2024). The other approach is to train shallow network with the output features of the pre-trained model and either of these CI. algorithms. We do not explore these directions here. In what follows, we review existing CL methods explicitly designed for leveraging pre-trained models, and we review theoretical developments for CL as well.
Prior Work on CL with Pre-trained Models. The availability of pre-trained models has motivated new insights into designing CL methods. CL methods such designed can be roughly divided into two categories. In one category, the pre-trained model is completely frozen, and their output features are used as inputs for a tailored CL method. A straightforward method in this category, known as SimpleCIL (Zhou et al., 2023) or Nearest Mean Classifier (NMC) (Mensink et al., 2013; Rebuffi et al., 2017; Panos et al., 2023; Janson et al., 2022), is to classify a test image based on the (cosine) distances of its feature class means of the training features. While this method is stable, hyperparameter- free, and can handle long task sequences, to the best of our knowledge, it does not have theoretical guarantees. Of course, RanPAC and LoRanPAC also fall into this category.' Other methods in the category include Ahrens et al. (2024); Prabhu et al. (2024). Both methods make certain modifications on top of RanPAC:
The method of Ahrens et al. (2024) replaces the random ReLU features with the concatena- tion of the output features of intermediate layers. We identify that this generalizes the idea of Pao Takefuji (1992)².
Note that RanPAC might use mest-session adaptation, which modifies the output features of the pre-trained model, so one might not consider RanPAC as completely freezing the pre-trained model. However, such strategy of first-session adaptation is applied only before the first task, and is not used during continual learning of tasks. In other words, the model after first-session adaptation is completely frozen, and we might just view it as our pre-trained model.
32

---

Published as a conference paper at ICLR 2025
The method of Prabhu et al. (2024) replaces the random ReLU features with random Fourier features (which were used by Rahimi & Recht (2007) for learning kernel machines), and the ridge regression solver of RanPAC with linear discriminant analysis (LDA) (Hayes & Kanan, 2020). Note that LDA optimizes an objective that is in general different from the MSE training loss, for which Prabhu et al. (2024) have not provided theoretical guarantees.
Similarly to RanPAC, the methods of Ahrens et al. (2024); Prabhu et al. (2024) need O(E") time per task to invert the (regularized) F. E covariance matrix. Prabhu et al. (2024) uses F = 25000 in their experiments, which might constitute the current computational limit of performing the inversion (cf. Figs. 3 and 5). Also, both methods lack theoretical guarantees. In contrast, the running time of our LoRanPAC method depends only linearly on L' and can handle E 2 10 with stable performance and theoretical guarantees.
In the other category of methods, the weights of the pre-trained models remain fixed, but the output features of the pre-trained models are changed. The catch that these methods either change the input or change the network architecture. Such change could be applied layer-wise, therefore, in order to describe the idea, it is the simplest to assume the pre-trained model f is a single-layer network.
* If we keep both the input and architecture fixed, then the network would take an input X and output fX))
A popular way to change the input is to stack some trainable parameters Z with input X, where Z and X have the same number of columns. The network outputs f([X; Z)). Here, it is implicitly assumed that f can take input matrices with different number of rows (i.e., different number of tokens). For instance, f can be a single-layer vision transformer. In this case Z is often called (visual) prompts (Jia et al., 2022), and CL methods using this strategy are often called prompt-based methods; see, e.g., (Wang et al., 2022b;c;a; Smith et al., 2023; Wang al., 2023; Jung et al., 2023; Tang et al., 2023; Gao al., 2024b; Roy al., 2024; Kim et al., 2024).
A popular way to change the architecture is to replace the onput- map X + f(X with X + [(X + g xX)), where y is some simple shallow network parametrized by the extra trainable parameters. For instance, 9 could be simple two-layer linear network of the form ( ABX g(X) A relu B BX), where A, B are trainable. In these case, A, B are called adapters (Houlsby et al., 2019; Hu et al., 2022; Chen et al., 2022), and CL methods using this strategy are often called adapter-basee methods (Zhou et al., 2023; 2024a; Liang& & Li, 2024; Tan et al., 2024; Gao et al., 2024a).
Clearly, prompt-based and adapter- based methods can both be viewed as expansion-based methods that enlarge the capacity of a network in order to learn new tasks (Rusu et al., 2016; Yoon et al., 2018; Li et al., 2019; Ramesh & Chaudhari, 2022).
Despite their popularity, both poompt-based and adapter-based methods need to solve highly non- convex training problems, for which deriving informative theoretical guarantees is a significant challenge. Their lack of theoretical guarantees makes them prone to unexpected failures. For example, prompt-based methods such as L.P (Wang al., 2022b), DualPrompt (Wang al., 2022c), CodaPrompp (Smith et al., 2023), have their performance highly sensitive to the choice of hyperparameters and therefore to the pre-trained model in use (Wang et al., 2023), dataset, and problem setting (cf. Table 1); indeed, a small perturbation in learning rates might change the accuracy drastically (Zhang et al., 2023). While they are often equipped with dataset-specifie hyperparameters released by authors (cf. Appendix J), their instability still emerges when applied to long sequence of tasks. This because new prompts or adapters are often needed to maintain high accuracy on new tasks (Zhou et al., 2024a), but doing so eventually becomes infeasible. Indeed, to train on the 100 tasks of the CIFAR 100 dataset in the CIL setting with one class given at a time (B-0, Inc- 1), running the adapter-based method of Zhou et al. (2024a), called EASE, with default hyperparameters, would create more than 117M parameters for its growing number of adapters, while the pre-trained ViTs in use have less than 87M parameters.
In Table 5 we summarize the conceptual differences of our approach from prior works.
Prior Work CL Theory. Theoretical developments
CL have been chasing the current CL practice, with a majority of the theory CL papers limiting themselves to the linear, two-layer, or kernel setting (Doan et al., 2021; Heckel, 2022; Evron et al., 2022; Peng & Risteski, 2022; Lin et al., 2023;
33

---

Published as a conference paper at ICLR 2025
Table 5: Conceptual comparison prior work.
Theoretical Guarantees?
Stablc?
Can Handle Long Task Soquenees?
L.P, Dual Prompt. CodaPrompt
None
No
No
EASE
None
No
No
SimpleCII.
Nome
Yes
Yes
RanPAC
Nome
Na
No
LoRanPAC (Ours)
Theorems
and
Yos
Yes
Swartworth et al., 2023; Goldfarb et al., 2024; Zhao et al., 2024; Ding et al., 2024). While these works cover various theoretical aspects (e.g., generalization bounds, sample complexity, and convergence rates), there has arguably been a huge gap between their simplified settings and deep networks that state-of-the-art CL methods use. On the other hand, we have seen that deep pre-trained models in cascade with shallow trainable networks can provide competitive performance, thus it now makes sense revise and extend these theoretical contributions within this cascaded architecture, thereby providing meaningful guarantees for learning the shallow networks. We believe this viewpoint would greatly reduce the gap between the theory and practice in the current CL literature.
H.2 RANDOM VECTOR FUNCTIONAL LINK NETWORK AND RANDOM FEATURE MODELS
Here we review related works on random feature models. Recall our model is two-layer network of the form
X + W (X)
(28)
where P is randomly generated and fixed, and W consists of trainable parameters.
Random Vector Functional Link Network. In independent efforts, Schmidt et al. (1992) and Pao & Takefuji (1992) considered models of form (I), Schmidt et al. (1992) used the sigmoid activation function & + T++xxp--E"* while Pao & Takefuji (1992) specified an arbitrary activation function as inspired by Hornik et al. (1989) and stack the features X and H together (see, e.g., Section 2.1 of Malik et al. (2023)). The model Pao & Takefuji (1992) proposed has been known as random vector functional link (RVFL), and the model of Schmidt al. (1992) is referred to, according to a recent review (Malik et al., 2023), as Schmidt neural network (SNN).
Models of form (28) are best combined with MSE losses, as training W with P fixed amounts to solving a least- least-squares problem, which admits a closed-form solution as shown by Schmidt et al. (1992) and even earlier by Webb Lowe (1990).
The model Schmidt et al. (1992) and Pao & Takefuji (1992) advocated was proposed, again, by Huang et al. (2004; 2006) under the name extreme learning machine (EL.M.. While Huang et al. (2004) claimed ELMs to be a new learning scheme in the paper title, it was criticized by (Wang & Wan, 2008; Authors) that ELMs are ideas stolen from the last century (Schmidt et al., 1992; Pao & Takefuji, 1992), which Huang et al. (2004) were aware of yet did not cite. Despite the criticism, and perhaps because of its "fancy" name, ELMs had once been popular and attracted many follow-up variants. We shall not review these variants here.
The model we considered, therefore, follows in spirit the framework put forth by Schmidt et al. (1992); Pao & Takefuji (1992). Crucially, our approach is modern instantiation of their framework (cf. Table 6), where we consider larger-scale problems with ill-conditioned data, online solvers with GPU implementations. But does it make sense use the random ReLU features H, := relu( (X;) rather than the pre-trained features X, for regression? Would the transformation P E Rxdd even harm the pre-trained knowledge? McDonnell al. (2023) empirically verified that having the first layer P is beneficial to performance as long as E 2 d, and the accuracy tends to be higher for larger E (see Table A5 of Appendix F.6 of McDonnell et al. (2023)). While RanPAC limited to E 10 our approach is inherently more scalable, allowing us to take E = 10 The pursuit in higher embedding dimension F. brings us into the over-parameterized territory, where the corresponding MSE objective has infinitely many solutions, and this is different from the classic works RVFLs SNNs that largely focus on the case where there are just a few hundred neurons (e.g., E ~ 100).
"Hence, the method of Ahrens et al. (2024) can be viewed as modern variant of Pao & Takefuji (1992) as Ahrens al. (2024) stacks the output features of multiple intermediate layers for regression.
34

---

Published as a conference paper at ICLR 2025
Table 6: Comparison between our approach and classic methods for extreme learning machines.
Problem Scale
Solver
Data
Compute Platform
Schmiid et al. (1992); Pao & Takefuji (1992)
small
offine
well-conditioned
CPU
LoRanPAC (Ours)
large
online
ill-conditioned
GPU
Random Feature Models. Model (28) is also studied under the name random feature model (RFM) with the origin of RFMs often attributed to Rahimi & Recht (2007). The RFM is considered to be simple proxy model for understanding deep networks, and hence it has recently been popular (Belkin al.., 2018; 2019; Bartlett et al., 2020; Hastie et al., 2022; Mei & Montanari, 2022; Tsigler & Bartlett, 2023). Some of these works make statistical assumptions on X, and address technical challenges in analyzing the nonlinear map W velu(P..).
Alternatively, one could conduct analysis conditioned on H, == relu(PX,), which would be more manageable it reduces linear models. For example, the work of Xu & Hsu (2019); Huang et al. (2022); Bach (2024); Green & Romanov (2024) truncates the SVD factors of the features before applying least-squares. This is similar ours, with important difference that they apply LoRanPAC only once, while we apply it continually. Also, their results make statistical (e.g., Gaussian) assumptions on 1.s. which could violate our context that H1 generated via H; := relu(ee x2). In contrast, our results in the main paper, namely Theorems and 2, make no assumptions on H and are therefore applicable to random feature models and to the pre-trained models bridged with random feature model.
35

---

Published as a conference paper at ICLR 2025
1 DATASET DETAILS
For convenience and completeness, we collect some details about the datasets in Tables and 8.
Table Datasets used for class-incremental learning experiments. t; ObjectNet, OmniBenchmark, and VTAB contain large number of classes, and we use subset of these datasets delivered by Zhou et al. (2023); see their Table 4 and also Table A2 of McDonnell et al. (2023).
Dataset Name
Origin
Training Set Size
Test Set Size
Classes
Link
CIFAR 100
(Krizhevsky et al., 2009)
50,000
10,000
100
Here
ImageNet-R
(Hendrycks et al., 2021a)
24,000
6,000
200
Here
ImageNet-A
(Hendrycks et al., 2021b)
5,981
5,985
200
Here
CUB-200
(Wah al., 2011)
9,430
2,358
200
Here
ObjectNet
(Barbu et al., 2019)
26,509
6,628
200
Here
OmniBenchmark
(Zhang al., 2022)
89,697
5,985
300
Here
VTAB
(Zhai al., 2019)
1,796
8,619
50
Here
StanfordCars
(Krause et al., 2013)
8,144
8,041
196
Here
Table 8: Datasets used for domain-incrementi learning. See Table A3 of McDonnell et al. (2023) for even more details.
Dataset Name
Origin
Training Set
Test Set Size
of Classes
Link
CORe50 CDDB-Hard
(Lomonaco Maltoni, 2017)
119.894
44,972
Here
(Li et al., 2023)
16,068
5,353
2
Here
DomainNet
(Peng et al., 2019)
409.832
176,743
345
Here
J EXPERIMENTAL SETUP DETAILS
The details of how we run each of the methods are specified as follows. For L2P, DualPrompt, CodaPrompt, we use the hyperparameters available in the PILOT repo (Sun al., 2023) for the CIFAR100 and ImageNet-R datasets. Since official hyperparameters are released for other datasets, we simply use their respective hyperparameters CIFAR 100 for other datasets. One might notice that these methods have large accuracy drops on other datasets, suggesting that they are sensitive to nyperparameters and the good and datasct-specific hyperparameters, if they exist, are to be found for these methods to perform well. This is an inherent drawback they involve minimizing highly non-convex training objective. On the other hand, many other methods, including SimpleCII. RanPAC, and ours, almost parameter-free Specifically, the only hyperparameter of our approach is the truncation threshold and its role is clearly explained in the main paper.
For joint linear classifiers, that is LC (XI:)) LC (H train for 20 epochs using the cross- entropy loss, batch size 48, weight decay 0.0005, and SGD with the cosine annealing schedule. We run LC (.T) and LC (HI:T) with different initial learning rates (0.001, 0.005, 0.01, 0.02, 0.03]. and take report the maximum accuracy (Table 9). Note that LC (X and LC (H1r)) are trained using the cross-entropy loss, not the MSE loss. The reason is that the features HI are highly ill-conditioned (Fig. 1), which makes SGD converge very slowly with the MSE loss. Comparing this to (I)), we conclude that the MSE loss in our setting is useful when the objective minimized via robust numerical computation techniques (e.g., our LoRanPAC implementation in Appendix C)
instead of SGD.
We also consider the idea of first-session adaptation. This idea introduces few hyperparameters such as the learning rate and schedule. We run experiments with two sets of hyperparameters, given respectively by RanPAC and EASE, We attach the symbol to the method name when hyperparameters of RanPAC (e.g., ADAM LoRanPACE RanPACt). We attach the symbol * when we use the hyperparamters of EASE (e.g., LoRanPAC* EASE*).
the
For RanPAC, the official hyperparameters given by McDonnell et al. (2023) vary for different datasets. We try to unify the setup by keeping using the hyperparameters most frequently used by McDonnell
36

---

Published as a conference paper at ICLR 2025
Table Accuracy of training joint linear classifiers given all data with different initial learning rates {0.001, 0.005, 0.01, 0.02, 0.03) and the corresponding maximum accuracy. LC (X1rr) trains a linear classifier using all pre-trained features XI7 and LC (HT))) uses all embedded features.
LC (X::r)
LC (Hi))
0.001
0.02
Max
0.001
0.02
Max
ViT's pre troined on ImageNet--l 1K
(riss_ ba..aassppp.... pat.chh
224):
CIFARI00
86.39
87.56
87.47
87.09
86.99
87.56
87.76
86.68
86.36
86.75
86.46
87.76
ImageNet-R
70.25
72.22
72.02
72.42
73.00
71.08
71.18
70.70
73.00
ImageNet-AA
54.64
57.67
59.25
56.48
CUB-200
82.32
87.62
88.59
88.63
88.76
88.76
88.72
88.13
88.00 08
88.17
87.83
88.72
ObjectNet
57.53
59.70
59.22
58.68
58.43
59.70
59.96
56.14
55.63
55.48
55.34
59.96
Ommibenchmark
76.11
79.00
79.55
79.43
79.50
79.55
80.02
79.62
79.57
79.62
79.43
80.02
VTAB
86.40
90.89
91.32
91.23
90.89
91.32
91.17
89.86
89,99
90.16
89.99
91.17
StanfordCars
39.56
62.54
69.29
72.86
74.12
72.43
73.65
73.54
72.81
73.65
VTTs pre-trained on ImageNer-22K
patchhee
22 224._2222 1n21k):
CIFARI00
86.15
86.78
86.33
85,86
85.17
86.78
85,80
85.16
85.05
85.31
85.4
85.80
ImageNet-R
67.22
68.63
67.12
65.90
65.28
68.63
68.65
68.00
68.17
68.23
67.78
68.65
ImageNet-A
46.68
51.42
50.03
49.24
48.58
51.42
51.15
50.16
49.44
48.98
49.64
$1.15
CUB-200
85.58
88.89
89.06
88.72
88.21
89.06
89.31
88.17
88.63
88.46
88.51
89.31
ObjectNet
58.01
58.39
57.50
55.87
54.42
58.39
56.93
53.33
54.44
54.47
54.54
56.93
Ommibenchmark
78.95
79.67
79.73
79.45
79.33
79.73
79.62
79.26
79.11
78.91
79.05
79.62
VTAB
87.71
90.78
90.97
90.71
90.11
90.97
90.78
91.03
90.42
90.44
90.27
91.03
StanfordCars
44.80
64.22
68.06
68.92
68.71
68.92
69.38
67.64
67.65
67.79
67.39
69.38
et al. (2023). Specifically, we set the embedding dimension E to 10000 for RanPAC; note the exception that McDonnell et al. (2023) run the CDDB experiments with E' 5000, even though their Table A5 showed that larger E in general leads to higher accuracy on CIFAR100, The main hyperparameters of RanPAC used for first-session adaptation are as follows:
("tuned_epoch" :
"patch_sizee" tweight_decay"::
We run ADAM LoRanPACI, RanPACI where first-session adaptation uses these hyperparameters consistently for all datasets.
The EASE approach of Zhou et al. (2024a) performs fine-tuning, not just for the first session, but for every session, in an interesting way. The hyperparameters in their released code vary for different sessions and different datasets, and we refer the reader to the official GitHub repo of EASE for details. We also run LoRanPAC* with the hyperparameters of EASE for first-session adaptation. Note that this
since EASE does not show experiments on StanfordCars, or does not release hyperparameters dataset, we run EASE with its CIFAR 100 hyperparameters for StanfordCars; see also Table 10 of Appendix K. where tune the initial learning rates of EASE StanfordCars, showing that the accuracy is still low.
Finally, note that in all tables, some approaches marked in gray; they not directly comparable to our approach as the methodology can be very different and it is in fact possible to combine with another for even better performance. On the other hand, RanPAC is the most related to our method, hence we highlight the comparison with the purple background.
K EXTRA EXPERIMENTS, FIGURES, AND TABLES
K.1 PERFORMANCE ON STANFORDCARS
It is observed in Table that many methods exhibit significant performance drops StanfordCars. Are these methods inherently unable to handle this dataset, or is it our taking inappropriate hyper- parameters that lead to poor performance? Note that the authors of these works did not test their
37

---

Published as a conference paper at ICLR 2025
Table 10: Accuracy of EASE with different initial learning rates {0.001, 0.005, 0.01, 0.02, 0.033 on StanfordCars.
0.001
0.005
0.01
0.02
0.03
Tno-5
Inc-10
Inc-20
Inc-5
Inc- 10
Tno-20
Ino-5
Inc-10
Inc-20
Inc-5
Inc-10
Inc-20
Ino-5
Inc-10
Inc-20
33.42
32.27
19.38
33.48
32.33
19.46
33.39
32.65
20.06
32.58
32.11
32.41
31.77
29.76
Table 11: Final accuracy of different methods using ViTs pre-trained on ImageNet-21K
(vit_base________ Saasseppacchle s_2echh666222e_e2eeee 2____2___n2___0 in21k). Compare this with Table of the main paper.
(Part I)
CIFAR100 (R-0)
ImageNet-R (B-0)
ImageNet-A (B-0)
CUB-200 (B-0)
Avg.
(C())))
86.78
51.42
73.97
LC (HHr)
85,80
89.31
73.73
Ino-5
Inc-10
Inc-20
Inc-5
Inc-10
Inc-20
Inc-5
Inc-10
Ine-20
Ino-5
Inc-10
Inc-20
RanPAC'
87.58
87.65
87.75
68.18
70.03
70.13
37.59
52.01
52.73
89.48
89.65
89.44
73.52
LoRanPAC
88.62
88.63
88.67
70.85
70.93
70.72
54.71
54.71
55.10
90.33
90.33
90.46
76.17
EASE"
85.85
70.27
75.88
47.53
86.77
73.99
RanPAC"
90.26
75.47
77.33
58.00
83.21
89.57
89.69
77.78
LoRanPAC
90.55
76.48
77.25
62.74
90.63
79.66
(Part 2)
ObjectNet (B-0)
OmniBenchmark (B-0)
VTAB (B-10)
StanfordCars (B-16)
Avg.
LC (X).)
58.39
79.73
90.97
68.92
74.50
I.C. (H
56.93
79.62
91.03
69.38
74.24
Inc-5
Inc: 10
Inc-20
Inc
Inc
Inc-20 20
Inc
Inc 10
Inc- 20
Inc:5
Inc- 10
Inc 20
RanPAC
59.14
78.38
78.06
65.78
LoRanPAC
61.35
80.
68.96
75.80
EASE*
54.98
57.50
60.35
72.88
73.50
73.87
88.24
93.46
93.43
35.43
34.62
37.32
64.63
RanPAC"
64.56
66.55
66.05
78.55
79.15
79.23
92.77
92.84
93.72
2.31
69.11
69.11
71.16
LaRanPAC"
66.76
66.67
66.93
80.55
80.82
81.55
93.85
93.79
93.76
71.46
71.58
71.71
78.29
methods on StanfordCars, nor they released the corresponding hyperparameters. To rule out the case of hyperparameter misspecification, we take the EASE" method of Zhou et al. (2024a) for example, and we run it with different initial learning rates {0.001, 0.005, 0.01, 0.02, 0.03) for the first task (this hyperparameter is called init rr in the JSON file of the code repo of Sun et al. (2023); all other hyperparameters are set to the corresponding hyperparamters Zhou et al. (2024a) gave for CIFAR 100. The results are in Table 10. It shows that different initial learning rates for EASE do not improve the performance on StanfordCars too much, suggesting that StanfordCars is perhaps inherently difficult for these types of methods.
K.2 EXPERIMENTS WITH VIT FEATURES PRE-TRAINES ON IMAGENET-21K
Note that by default we use ViTs pre-trained on ImageNet-I IK (vit_base base caceee_aachhhh... cattchl6_22440 Here in Table 11 we show experiments with VITs pre-trained on ImageNet-2IK. Comparing this with Table 1, we obtain a similar conclusion that LoRanPAC is more stable than and outperforms RanPAC.
K.3 EXPERIMENTS THAT SHOW LORANPAC STABILIZES THE TRAINING LOSSES
In Fig. 2 of main paper we showed that LoRanPAC has stable test accuracy by truncating the SVD factors, compared to the nearly zero test accuracy of Min-Norm. In Fig. 4, we show that the truncation also stabilizes the average training MSE losses 1 W HIs - Yı 1|2 which eliminates M.
the numerical issues and furthermore enables generalization test scenarios.
K.4 EXPERIMENTS DOMAIN-INCREMENTAA LEARNING (DIL)
Here consider domain- inntiit-nneeeeettlll learning (DIL), where each task has images of all objects collected from different sources or domains, e.g., objects in the images of task could be hand-written sketches of cars, and images of task 2 could be colored cars.
38

---

Published as a conference paper at ICLR 2025
CIFAR1OD (B O, Inc 10)
ImageNet R (B O, Inc 20)
ImageNet. (B 0, Inc 20)
CUB 200 (0 0, Inc 20)
Thining Los
Trannnn Loss
Thining Lows
10
10a
10
Thaining (25%)
10"
1
(255
10
10"
2
Seen Tasks
Seen Tasis
of Seen Tasks
#f Seen
Figure 4: The average training MSE loss M.
1 WHH 1 of the incremental SVD solution to
Min-Norm explodes when eigenvalues of order 10-5 emerge (Fig. 1b). LoRanPAC (25%) truncates 25% minimum singular values and implements LoRanPAC online, stabilizing Min-Norm.
Table 12: Final accuracies of RanPAC and LoRanPAC with pre-trained ViTs for domain incremental learning.
CORc50
CDDB-Hard
DomainNet
Avg.
RanPAC
94.98
75.14
64.20
78.1
LoRanPAC
96.06
79.21
67.18
80.82
We follow the work of McDonnell et al. (2023) to run domain- incremental learning experiments on 3 datasets, CORe50 (Lomonaco& Maltoni, 2017), CDDB-Hard (Li al., 2023), and NemainNet. (Peng et al., 2019). The corresponding experimental results are shown in Table 12, from which we observe a similar phenomenon: LoRanPAC is more stable and has higher accuracy.
K.S SCALING LAWS OF THE EMBEDDING DIMENSION
ObjectNet (B40, Inc:5)
OnniBennhmauk (8-0, Inc:5)
VTAB (8-10, Inc-5)
StunfordCars (BI Inc-5)
Triinin Time
Training Time
Thaining Time
10
Training Time
10
RantKC:
RantfC
Rastte
30
LoRustAC
LeRasPAC
202
LeRueBAC
10
Figure 5: Training times (in minutes) of LoRanPAC and RanPAC for different embedding dimensions
E. See also Fig. 3 in the main paper for similar results the other four datasets.
Fig. 6 exhibits a scaling law where the accuracy LoRanPAC grows with the embedding dimension
E. A similar phenomenon is also shown for RanPAC in Table A5 of Appendix F.6 of McDonnell et al. (2023). However, the experiments RanPAC is not scalable (cf. Figs. 3 and 5), and also limited to only the CIFAR 100 dataset. Here, since our LoRanPAC implementation is more stable and scalable, we can run it with E as large as 10 therefore visualizing the scaling phenomenon for eight different datasets in Fig. 6.
McDonnell et al. (2023) are limited to E = 15000 as
clearly tempting to scale the embedding dimension even more, but doing so brings up two issues. First, large E. entails large memory use, and will therefore eventually be infeasible. Second, we have not found any significant performance gain with even larger (e.g., E = 150000 or E 200000), which is why we stopped at dimension E 10 Note that enlarging E amounts to increasing the width of the corresponding layer. It was suggested that increasing the width is beneficial, theoretically (Peng et al., 2023) and empirically (Mirzadeh et al., 2022). On the other hand, Fig. 6 suggests the benefit of increasing the width empirically diminishes, e.g., the accuracies for 50K and E 100K are comparable on ImageNet-A. A, CUB-200, VTAB, and StanfordCars. This is empirically corroborated by Guha & Lakshman (2024) and theoretically confirmed by Hu al. (2024).
K.6 RUNNING TIMES
In Fig. 3 we compare the running times of several methods in addition to RanPAC (see Figs. and 5). We see that LoRanPAC faster than prompt-based methods (c.g., L2P, CodaPrompt) and adapter-based methods (e.g., EASE) CIFAR100, ImageNet-R, ImageNet-A, and CUB.
39

---

EASE Published as a conference paper at ICLR 2025
CIPAR100 (B O, Inc 5)
Imugehet R (D 0, Inc 5)
ImageNet (B 0. Inc 5)
CUB 200 (B Inc 5)
Final Aue. (3)
85.2
Acc, (E)
74
Final Acc: (3)
Final Acc. (%6)
83
75
899
87.8
72
61
87.6
60
87.5
87.4
10K
1OOK
10X
100K
50%
50K
100K
E
E
ObjectNet
OmmiBenchmark (D Inc
StanfondCans (B 16, Inc
Final Auc. (95)
Final Acc, (3)
Fizal Acc. (95)
Fizal Acc. (8)
79
V2.4
39
60
78
92.2
20
71
50K
10K
103K
10K
100K
10K
100K
E
Figure 6: Final accuracy of LoRanPAC for varying embedding dimensions E. See also Table 15 in comparison RanPAC.
Table 13:
Running times (in minutes) of various methods on CIL datasets with 92 = 5 (Inc-5). This is the same setting Fig. 3.
CIFARI00
ImageNet-R
ImageNet-A
CUB
1.2P
52.09
72.31
26.96
17.62
CodaPrompt
174.9
246.94
27.28
39.91
139.74
128.35
54.0
66.23
LoRanPAC (E- 100K)
31,24
27.0
1.29
3.73
K.7 MULTIPLE RUNS OF THE EXPERIMENTS
In Table 14 we report results under the the same setting of Table 1. We report the mean and standard deviations over random seeds.
Table 14: Final accuracy with pre-trained ViTs under the same setting of Table 1, Reported results mean and standard deviations over 3 random seeds. See also Table 1.
(Part 3)
CIFARI00 (B
InageNNes R (B
ImspeNet (B-0)
CUB-200 (3:0)
Ise-5
Isc-20 20
Iac-10
Isc
Isc.5
tac-10
Inc 20
Iac-5
Iuc-10
78.22 in
12
68.36
g2.01
73.74 is
44.5
49.31
50.8720
52.6 m
59.46
67.47 o
DualPhumpt
$0.39
10.92
85.58
67.67 1o4
71.58
72.6
40.34.11
53,90
56.46.0
$3.94
61. 12.0
68. 18.39
Codathompt
82553a
67.74.39
72.3
74.67
3544
48.56
58.29.ass
38.48,023
58.61
70.67
SimpleCII.
40:48
50 4844
67.47
63.47
69.4
58.72gus
72
58.72gm
3045
25
50.45.00
KaniFiC
36.9329
27.06
07.02.000
71.95:311
71.85
72.29am
72
60.11.100
61.07a14
61.71:0
85.07.0011
57. 57.53
87 37.33.014
LoRaiPAC
85.24...8
73.67
62.89.o
89.
ADAM!
83.44.0 22
8481
86.03 .a.33
63.8...11
64.9
70.82.1::
S8.72
58.7.a4
38.86.0 11
90.48.002
50.69 su0e
80.99.0.1
RanPAA!
88.76a
90: 14.14
90162
71
78.49
7807
21.26
61.71
62.05
WT.9 21.
67. 50
85. 96.31
99.2.a
73.76.319
24.8
62.56a04
62.06an33
62.98.n
89.17
89. 29.24nna
89. 99.36
24.08.04
26.7
24
75.4-324
59.5611
02.41.044
80.6
21.07
LoRanPAC
89.9 41
90.59
91.58 .0.6
78.42.126
80,07
1035
81.45
63 63.18
64.12.03
63.51.ca
19.1.a1
59.24
89.38
(Part 3)
ObjectNes (B-0)
OuniBeechmark (B-0)
VTAB (B
StanfooCaas (3 (3-16)
1
Ias-10
1sc-20
Iac-10
1os-20
1nc.5
Iac-10
Inc-20
Iac-5
Iuc-10)
10e-20
52.3.a
35.51 la.ss
53.74.3de
37.32.jo2
10.91..1
19.0
12.32
76666. 67
14.49.mm
27.34
41.35 .2
DualPhumpt
47.71
10.53
$6.01
56.56.3.
90.45
62:4na
64.77
75.98.322
79.58_a
11.91
18.90 10:75
20.04.111
Codathooppt
46. 46.7asmn
54,32402
59.35a38
64.87aaa
68.5am
62.39
74.93a
85.24.a11
7889.
11.68
29.
SingleCII
51,60
51.00ams
51,60gam
70.19
70.19
70.19
82.53
92.53
g2.53gm
35
35.46
35
KaniXCC
58.15a917
50.17
77.74:300
77.48.11
77 77.4511
91 91.5311:14
91.77.00s
91.77.0
$5.53
71,55
71.54..11
LaRadPAC
60.61
79.76
92.47
92.53.0
74.23
74.35 10113
ADAM!
42.2
53.78
70
70.43
20
12.58
82.58.
35,56
.0.5
15.56
59.33a9
60.3
64 37
78229.11
78.2
78 Wan
01 7
91.
01.88
91 18
44.04
72.30
73. 20
61.45a911
66 34
19.85.3.
10.19.034
50.08.3
92 92.57ar0
91.42.m
92.99.n
74.66amt
24.67.0m1
50.2.n4
50.92
26.78.031
10.67.022
70812071
93.622m1
32.462071
M.66a111
29.79.1
LoRaPRNC
63.67.04
66.5210.0
66.90 66.96.0277
30.07.307
80.34
40.41
93.161ca7
93.17
93.16
75.63
75.561844
75.67.x21
40

---

Published as a conference paper at ICLR 2025
Table 15: Final accuracies of RanPAC and LoRanPAC with pre-trained ViTs. RanPAC takes its default choice E 10K, while for LoRanPAC we set three different values for E: E 10K, E 50K, and 100K.
(Part 1)
CIFAR 100 (B-0)
ImageNet-R (B-0)
ImageNet-A (B-O)
CUB-200 (B-O)
Avg.
Inc-5
Inc-10
Inc-20
Inc-5
Inc-10
Inc-20
Inc-5
Inc-10
Inc-20
Inc-5
Inc-10
Inc-20
RanPAC
86.71
87.02
87.10
71.90
71.97
72,50
56.48
62.34
61.75
88.08
87.15
88.13
76.76
LoRanPAC (E 10K)
87.48
87.49
87.42
70.77
70.85
70.48
58.85
58.46
59.38
86.73
86.85
87.19
76.00
LoRanPAC (E = 60K)
88.13
88.05
88.04
73.05
73.07
73.05
62.80
62.80
62.48
89.23
89.23
89.19
78.26
LoRanPAC (E 100K)
88.18
88.18
88.21
73.67
73.72
73.63
62.74
63.20
63.20
89.36
89.27
89.23
78.55
(Part 2)
ObjectNet (B-0)
OmniRenchmark (B-0)
VTAB (B-10)
StanfordCars (B-16)
Avg.
Inc-5
Inc- 10
Inc:20
Inc-5
Inc-10
Inc-20
Inc-5
Inc. 10
Inc-20
Inc-5
Inc-10
Inc-20
RanPAC
58.77
57.66
57.69
77.63
77.63
77.46
91.15
91.58
91.58
$8.03
71.40
71.40
73.50
LoRanPAC (E' = 10K)
57.97
57.82
58.06
76.79
76.96
76,91
91.89
91.81
91.91
64.03
64.43
64.72
72.78
LoRanPAC (E = 60K)
59.41
59.4
59.54
79.33
79:35
79.43
92.48
92.47
92.54
73.32
73.66
73.47
76.20
LoRanPAC (E 100K)
60.83
60.86
60.77
79.50
79.60
79.70
92.46
92.58
92.56
74.21
74.39
76.82
CIFARLO0 (B-0, Inc-10)
ImagoNNotR (B-0, Inc-20)
ImagoNot-A (B-0, Inc-20)
CUB-300 (B-0, Inc-20)
Elfective Rank Rank
Eifective Rank
Elfective Rank
Eifective Rank
2.5
2.5
2.5
2.5
of Seen Tasks
Seen Tusks
of Seen Tasks
of Seen Tusks
(7a) The effective rank 71 [ (
as the number f of seen tasks increases.
CIFARIO0 (B-0, Inc-10)
ImageNNttR (8-0, Inc-20)
ImageNNt-A (B-0, Inc-20)
CUB-200 (8-0, Inc-20)
Ellecivve Rank
6K
Elfeciive Rank
2K
2K
Bleecivv
2K
1K
Elfective
IK
(7b) The cigenvalues of H Hi. arranged in descending order fixed).
Figure 7: The effective ranks H Hi:t-
K.8 MORE FIGURES FOR DATA ANALYSIS
Recall (+(()) denotes the k-th largest eigenvalue of a matrix and M, = my + m. Define the notion of effective rank, as by Tsigler& & Bartlett (2023):
Tk H H1)) Σj2r My Ms
H Hv.)
Vk 1, ...., M.
(29)
H H1.e)
Note that r1(-) is the standard definition of effective rank (sometimes called stable rank), while (+):) generalizes it by only considering the eigenvalues starting from the k largest.
Fig. 7a plots the effective rank rı (H,, HI:)) as the number of tasks increases and Fig. 7b plots rk( H.. Hı.) for different values of k. We observe similar curves on different datasets: vi (H H.a)
smaller than 3, and rx H. first increases and then decreases as a function of k.
Fig. 8 plots the top ke eigenvalues of B, (recall that only preserve top ki singular values of B.). It shows that the condition number is now order 10 (10 /10%), which is much smaller than the condition number of H H1.t-
Fig. plots the normalized differences 1 Eiielloo Sorlloo//11 E bo between the eigenvalues given by LoRanPAC and its continual implementation (Algorithm 4). This empirically verifies that the differences between the two are insignificant compared to the largest eigenvalue E bloc (just of order 10-3). This experiment assists understanding Theorem 6.
41

---

Published as a conference paper at ICLR 2025
CIFAR (B O, Inc 10)
ImageNet R (B Inc 20)
ImageNet A 0, Inc 20)
CCB 200 (B
Inc 20)
10
10
10
10a
10
10
10
10
7K bigenvalue Index
<X
1OK
7K Eigemaaue Index
<K
10C
2XC
4KC
6K
4K
7K
10C
Aigenvalue Index
Eigenvatue Incle
Figure 8: The eigenvalues of 112 for t = I....,9 9. These are by definition the top k2 eigenvalues of B, B, It shows that our continual implementation (Algorithm 4) prunes the smallest eigenvalues (of order 10-S) so that the condition number is now of order 10 /10%) compare this figure with Fig. la. In this experiment we truncate 25% of the eigenvalues; that is, given Mc. we select ke such that //MM, 75%.
CIFAR100 (B-0, Inc-10)
InigeNNe-R (B-0, Inc-20)
ImageNet-A (B-0, Inc-20)
CUB-200 (B-0, Inc-20)
Eig. DAIL
Eig. DAI.
Elg. DEIL
DNE.
10
10
10
10
3 A of Seen Tasks
2 3 of Seen Tasks
1010
3
3 6 X 9:10
A of Seen Tasks
A Seen Tasks
Figure 9: Normalized differences EE E1:1l0// E between the eigenvalues given by LoRanPAC and its continual implementation (Algorithm 4). This empirically verifies that the differences between the two are insignificant compared to the largest eigenvalue |E lloe (jutt of order 10 30-3). See Fig. and Fig. la. See also Theorem 6 where we formally bound the distances || - oo for every t.
Fig. 10 plots the eigenvalues of Hi: R,M,M,, (M, S 10*) with the embedding dimension E varying in (10000, 25000, 50000, 75000). It shows that the "shape" of the spectrum is similar for different values of F and on different datasets (see also Fig. 1a for the case F. 10%).
Fig. 11 depicts how the random embedding P E R Exd and ReLU layer affect the spectrum of the features. In Fig. 1la we plot the output features X E R of the ImageNet-A dataset from pre-trained ViTs (d 768, MM 5981, E 10a), We see XX is relatively well-conditioned: Its maximum eigenvalue of order 10y and minimum eigenvalue of order 10. Fig. lb shows that X T PX E I Fx M is ill conditioned. This is because PX has rank at most d, and the smallest M d cigenvalues of X P PX should be zero, while we get these small and non nerorro eigenvalues in Fig. 1lb due to numerical errors in (incremental) SVD; these eigenvalues should be truncated (set to zero), in order to solve Min-Norm accurately. Fig. lc shows that relu relu(PX) also has these small and non-zero eigenvalues. While the rank of relu PX) is unclear, its smallest yet non-zero cigenvalues are likely inherent from PX, and we suggest truncating them as well. See also Table 16.
K.9 ABLATION STUDY ON RANDOM RELU FEATURES
In Table 16 we study the effects of the random ReLU model. Recall that, given the output features X, of the data of task é from pre-trained model, we use the random ReLU features H, == relu( (XX,) and labels Y, to train a linear classifier via continually solving Min-Norm or LoRanPAC. We could
CIFAR C,
ImageNer R (B 20)
ImageNet (B 0,
200 (B
10t
104
10
10
100
10
10a
10f
E-25K
E=IUK
B=25K
E-I0K
10
D-75K
10
D=75K
10
7K
10K
4K
7X
10K
2K
4K
6K
4K
TX
JOK
Eigenvalue Index
Eigenwaluc Index
Eigenvalue Index
Eigennauue Index
Figure 10: Eigenvalues of HI M.X, (Mr < 104) with the embedding dimension E varying in (10000, 25000, 50000, 750003. We find that the "shape" of the spectrum similar for different E and on different datasets (see also Fig. la for the case E = 109).
42

---

Published as a conference paper at ICLR 2025
Outpot Features From Pre-trained Models
Random Features
Random ReLU Features
X
R Md
Random Causssian Emheckding
PX
RelJI Activation
H = relu PX
(a)
PER FEREX
10"
10
(h)
10"
(0)
10
10
> E >> M
10"
10
933 Eipervalur Indees
206 600
500
1.58 3K 4.5K Eigenvalic Indes
1.5K Eigenvaluc Indes
1K
4.5K
68
Figure 11: Feeding M data samples pre-trained model gives its d-dimensional output features X E RdxM M Passing it through a random embedding layer and ReLU layer yields the ran- eigenvalues of XXX" X T PX, and H H in descending order, where X consists of pre-trained ViT features of the ImageNet-A dataset (d 768, M 5981, F. 10%). It is seen that PX and H more ill-conditioned than X. See also Table 16.
dom ReLU features H REXM Plotted in (a), (b), (c), respectively,
instead use X, PX, re) the features train the linear classifier. To the effects of these alternative choices, we make Table 16 from which we have the following observations:
The random ReLU features H, gives the highest accuracy, while using the ReLU layer alone or random embedding alone does not make improvements over the original pre-trained features X,
Solving Min-Norm via Incremental SVD exhibits numerical failures random embedding P. This is because PX E RxM has rank at most d and we would get M small yet non-zero eigenvalues accounting for the numerical errors of (incremental) SVD solvers (see, e.g., Fig. 11). While they damage the accuracy, truncating these singular values and the corresponding singular vectors restores the performance.
Table 16: Final accuracy of Min-Norm and LoRanPAC when using different features, X, Rdxm: relu( X,), PX,, and H, == relu (X,)) Here P E Exd is random Gaussian ma- trix with (0, 1) entries and 10 and H, consists of random ReI.U features we use by default. Note that both Min-Norm and LoRanPAC are solved by the incremental SVD method, with differ- ence that the latter truncates the SVDs. Incremental SVD without truncation is not scalable enough to handle all 50000 data samples of CIFAR100, so mark "N.A." in the table for Min-N Min-Norm.
CIFARIOD (B-0, Ine-10)
ImageNet-R (B-0, Inc-20) ImageNet-A (B-0, Inc-20)
CUB (B-0, Inc-20)
Avg.
Final Accuracy of Min Norm
X, relu(
85.11
69.22
58.92
84,90
74.54
84.07
66.43
55.23
84.14
72.47
PX,
N.A.
1.35
2.37
0.55
N.A.
H.
N.A.
0.42
0.92
0.72
N.A.
Final Accuracy LoRonPAC
X,
reluf X.)
PX,
78.96
42.73
63.15
$8.33
H. (default)
88.18
73.65
63.20
89.23
78.57
K.10 EXTRA EMPIRICAL STUDY OF RANPAC
In Appendix 10.2, we analyze the training losses of RanPAC. In Appendix K.10.3 we show RanPAC unstable with respect small increments, while LoRanPAC is more stable.
101 RANPAC IS UNSTABLE WITH RESPECT To REGULARIZATION PARAMETER
In Fig. 12a, we show that RanPAC is unstable as it fails if the regularization À is small. In Fig. 12b, extend the solution of (4) into J,Ü,.. Agg) ÜT for ridge regression; this amounts to RanPAC with truncation. This extension stabilizes RanPAC and is practically immune to changes in the regularization parameter X.
43

---

Published as a conference paper at ICLR 2025
CIPARIOD (B O, Inc 10)
ImageNet R (B O, Inc 20)
ImageNet ( 0, Inc 20)
CUB 200 (D 0, Inc 20)
Aco. (3)
Acc. (3))
Acc. (98
Tosal
Acc.
Tosal
Tosal
Tonal
(itaal
(Ttaal
(ttaal
[Tnal
10
100
IK
1OK 100K
0
10
100
IK
10K
100K
100
1K
10K 100K
0
10
100
IK
10K 100K
(12a) RanPAC breaks down for the small regularization A.
CIFARLO0 (B-0, Inc-10)
ImageNet-R (B-0, Inc-20)
ImageNet-A (B-0, Inc-20)
CUB-200 (B-0, Inc-20)
100
Ave. (%)
Avc. (%)
Are. (16)
Tool
Apc
Tooo
Total
Total
10
100
IK
LOK
L0OK
0
10
100
IX
10K
LOOK
100
IK
10K
100K
0
10
100
IK
10K 100K
(12b) RanPAC with truncation (25%) has stable performance for varying regularization parameter A.
Figure 12: We extend the solution of (4) into 1. + - for ridge regression; this
amounts RanPAC with truncation. This extension stabilizes RanPAC.
CIFARIO0 (B-0, Inc-10)
ImagoeNotRR (B-0, Inc-20)
ImiggoNatAA (B-0, Inc-20)
CUB-300 (B-0, Inc-20)
Training Loss
10-1
Training Loss
10
Training Loss
Training Less
10-1
10
100
10
10
1000
1100
1000
10
10
10 10
of Seen Tasks
of Seen Tasks
of Seen Tasks
of Seen Tasks
Figure 13: The average training MSE loss Mr,
E of RanPAC for different ridge regularization parameters À E 1, 10, 100, 1000}. Compare this with Fig. 12 and Fig. 4.
W WHH H1s -
10. TRAINING LOSSES OF RANPAC
Fig. 13 plots the training loss of RanPAC for different ridge regularization parameters À E 1,,
1, 10, 100, 1000). We observe that, In the case of À 0, the training loss of RanPAC is smaller than 1. Fig. 4 shows that the incremental SVD implementation of Min-Norm could have its training loss larger than 10t0 This difference is because the incremental SVD implementation (without truncation) can be unstable and accumulates errors over time, while RanPAC is imple- mented by solving the normal equations W WH + >gg) = Yr: in variable W (the covariances H H,
1 and Yu t are updated continually). The advantage is that maintaining HIgHT and Y, H is easy and does not entail numerical errors, so solving the normal equations H + XIg)
Y.H directly is expected be stable, long as the solver invoked numerically stable (the built-in Py Torch solver is used). This appears to be the case, as RanPAC maintains small training errors. On the other hand, the corresponding test accuracy can be nearly zero with small À (e.g., when x = 0, 1 as shown in Fig. 12).
1010.3 RANPAC IS UNSTABLE FOR CIL WITH THE SMALLEST INCREMENTS
In the experiments the main paper, we see that RanPAC is unstable for small increments (c.g.. Inc-5). Moreover, its instability is exacerbated in the extreme case Inc-1 (Table 2).
Here, we show similar experimental results in Figs. 14 to 17, suggesting that RanPAC is significantly more unstable for Inc-1, Inc-2, and Inc-4. In particular, in the extreme case of Inc- 1, RanPAC presents failures on all datasets except CIFAR 100 (as indicated by the verticle blue line in Figs. 14 to 17. On the contrary, these figures, including Fig. 18, show that LoRanPAC method is stable for different small increments (1, 2, 4, 5).
44

---

Published as a conference paper at ICLR 2025
CIARRIOO (B-O, Inc-1)
CIBAR1OO (B-O, Inc-1)
ImageNet.KK 1B-0 Inc-1)
ImageNNet- 18-0, Inc-1)
100
25
25
50
50
15
150
150
100
100
200
200
25
50
75
100
50
200
CIFARROO 100 (B-0, Inc-2)
CIFARIOO (B-0, 1nc-2)
ImoopeNNet-R (B-0, Inc-3)
Ema Nonop-NNee-RRR (1--0, Inc-2)
100
100
100
13
13
25
25
25
50
50
50
37
50
50
100
100
13
25
37
50
13
25
57
50
25
50
75
100
25
50
75
100
CIFARIOO (B-0, Inc-4)
CIFARI00 (B-O, Inc-4)
EmsapeNet-R (B-0, Inc-4)
EmtooNNet-R -Rt (B-0, Inc-4)
100
100
100
100
13
13
14.11
13
50
13
50
25
50
25
50
37
37
50
13
19
25
7
13
19
25
13
25
37
50
13
24
37
50
CIFARIOO 100 (B Inc 5)
CIFARIOO (B. D, Inc 5)
ImageNNtt R: (B D, Inc 5)
ImageNet R (B O, Inc 5)
100
100
100
100
50
10
50
20
50
20
50
15
15
30
30
20
5
10
15
20
10
15
20
10
20
30
46
10
20
30
40
(14a) RanPAC
(14b) LoRanPAC
(14c) RanPAC
(14d) LoRanPAC
Figure 14: Upper triangular accuracy matrices on CIFARI00 and ImageNet-R (Inc-1, 1,, 2, 4, 5).
ImageNet
Inc 1)
ImageNett (B. Inc
CUB 0, Inc 1)
(B Inc
100
100
50
50
50
50
100
100
150
150
150
150
200
200
200
200
100
200
150
100
50
150
200
IntageNet-A (8-D. Inc-2)
ImsageNos-A (B-D, Inc-2)
CUB-200
Inc-3)
CUB-200 (B-00 Inc-2)
100
100
100
100
255
25
25
50
50
50
50
100
100
100
100
25
50
100
75
100
25
50
100
75
100
IntageNNttA (8-D. Inc-4)
IntageNottAA (8-00 Inc-4)
CUB-200 (8-0, Inc-4)
CUB-200 (B-0, Inc-4)
100
100
100
100
13
13
13
13
24
-0
25
50
50
50
37
37
37
37
50
13
255
37
50
13
24
57
50
13
25
37
50
25
37
50
ImageeNet A (B. O, Inc 5)
ImugeNet A (B 0, Inc
CUD 200 (B O, Inc 5)
CUB 200 (B 0, Inc
100
100
100
100
10 20
50
20
50
20
50
20
50
30
30
30
30
0
10
20
30
40
10
20
30
40
10
20
30
40
10
20
30
40
(15a) RanPAC
(15b) LoRanPAC
(15c) RanPAC
(15d) LoRanPAC
Figure 15: Upper triangular accuracy matrices on ImageNet-A and CUB-200 (Inc- 1, 2, 4, 5).
45

---

Published as a conference paper at ICLR 2025
ObjecttNet (B-O, Inc-1)
ObjectNet IB-O, Inc-l)
OmniBenchmark IB 18-0, Inc-1)
OrnniBenchmurk IB-0, Inc-1)
100
100
50
75
75
150
150
150
225
225
200
200
300
300
100
150
150
225
500
Objectteet (B-0, Inc-3)
Obj (B-00 Inc-2)
OmnniBnnc (B-0, IB-0))nc-3)
OrgniBenchmork (B-00, Inc-2)
100
100
100
25
25
38
35
50
75
50
100
100
150
150
25
50
75
100
25
50
75
100
38
76
112
150
38
75
112
150
ObjectNet (B-0, Inc-4)
ObjectNet (B-0, Inc-4)
QmunBennhhack (B-0, Inc-4)
QuniBenchmack (B-0, Inc-4)
100
100
100
100
13
13
19
19
144 25
50
25
50
36
50
38
50
37
56
75
75
13
25
37
50
13
24
57
50
19
34
56
75
19
34
56
75
Object|Ne (B D. Inc 5)
ObjecttNtt (B 0, Inc
OmniBenchmark (B D, Inc 5)
OmniBenchmark (B 0, Inc
100
100
100
100
20
50
20
50
30
50
1o 30
50
30
30
45
10
20
30
40
10
20
30
40
30
45
60
15
30
45
60
t
(16a) RanPAC
(16b) LoRanPAC
(16c) RanPAC
(16d) LoRanPAC
Figure 16: Upper triangular accuracy matrices on ObjectNet and OmniBenchmark (Inc- 2, 4. 5).
VTAD Inc 1)
10, Inc
StunfordCars Inc 1)
StanfordCars 16, Inc 1)
100
100
46
45
136
156
15
153
41
21
91
136
46
136
VTAB (8-10, Inc-2)
VTAB (8-10, Inc-2)
SlanfordCais (8-16, Inc-3)
StaufordCars (8-16, Inc-2)
100
100
100
100
23
25
50
50
21
91
11
16
68
91
23
46
VTAB (8-10, Inc-4)
VTAB (B-10, Ino-4)
StanfordCCus (8-16, Inc-4)
StaufordCars (8-16, Inc-4)
100
100
100
100
12
13
50
-00
24
-50
1ow 25
50
34
34
11
12
23
34
46
12
21
34
46
VTAD (D 10, Inc 5)
VTAD (D 10, Inc
StunfordCars (D 16, Inc 5)
StanfordCurs (D 16, Inc
100
100
100
100
10
10
50
50
19
50
19
50
26
28
0
10
19
28
37
10
19
28
37
1
(17a) RanPAC
(17b) LoRanPAC
(17c) RanPAC
(17d) LoRanPAC
Figure 17: Upper triangular accuracy matrices on VTAB and StanfordCars (Inc- 2, 4. 5).
46

---

Published as a conference paper at ICLR 2025
0)
ImugeNet
ImugeNet-AA
200
Total Acc. (95)
100
Tocal Acc. (8)
100
Total Acc. (%)
100
Tocal Acc. (%)
50
RanIVCC
90
RaniACC
RaniAA
RanPAC
LoRtnPMC
LoRannAC
LoRanRAC
LoRanPMC
Inc
Inc
Inc
Inc
UbjectNer
Cmnni Benchmakk
VTAB (8-10)
StanforCCars (8-16)
Total Arc. (9))
100
Total Axe, (%)
Total Avc. (%)
100
Total Acc. (1)
RanPNC
50
RanRNC
RanRMC
RanRMC
LoRanPMC
LoRanPA
LoRunPMC
LoRaniMC
Inc
Inc
Inc
Inc
CIBARIDO (8-D)
ImnageNet-R R (8-D)
ImageNNet-A (8-D)
CUB-200 (8-0)
Finall Avc. (%)
100
Final Avc,
Final Avc.
Final Acc.
RanPSC
Inc
Inc
ObjectNet (B-0)
OmniBenchrurk (B
VTAD (B-10)
StanfordCurs (B-16)
Final Acc. (%)
100
Final Acc. (%)
100
Final Acc.
Final Bec.
LoRtnPaC
LoRunPAC
LoRanPAC
Figure 18: Our LoRanPAC method is stable with respect class increments of each task (Inc-1,
4, 5), while the accuracy of RanPAC drops for smaller increments. The first two rows plot the total accuracy. The last two rows plot the final accuracy. The figures here essentially plot the averages of the upper triangular accuracy matrices (total accuracy) or its last column (final accuracy) of Figs. 14 17. The numerical values of the total and final accuracy for Inc-1 are shown Table
47


Reviews:
[{"review_id": "Z4qXHmdGNh", "reviewer": "Reviewer_EXjv", "summary": "This paper proposes a method for continual learning. In this method, the singular values are continuously truncated. The authors claim that their method has theoretical guarantees as well as good practical performance.", "questions": "Did the authors compare with experience replay method?", "limitations": "", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The authors provided comprehensive theoretical and empirical results.", "weaknesses": "A simple baseline in continual learning is experience replay. But I did not see the authors providing the results for experience-replay-based method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "egFJvUpI7S", "reviewer": "Reviewer_XHQX", "summary": "This paper proposes a new method to address instability issues of RanPAC. Part of the contribution is a diagnosis of the cause of the instability which is attributed to the condition number of the features exploding as the number of tasks increases. The proposed method truncates the smaller singular values of the features in an online or continual way, so that it doesn't have to store all of the previous tasks samples. Effectiveness of the new method is validated empirically.", "questions": "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. \n\n\nIn 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.\n\n\nNew notation that is used in lines 242-243 has not been introduced yet.\n\nTo judge the significance of the experimental results, it would be helpful if the reported numbers included also a measure of uncertainty.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The problem and setup is well motivated. The results are natural and the writing is clear. The experimental results are extensive and seem significant.", "weaknesses": "It seems to me that the main contribution of this work is an algorithm for continual principal component regression, with an application to training with random features. Specially, the properties of the features that arise from pretraining, random projections and nonlinearity don't seem to matter much to the derivations theoretically. On the other hand, if I view the work mainly as an algorithm for continual principal component regression, then the guarantees given in theorems 1 and 2 are a black box, since the quantities $\\gamma_t$ and $a_t$ which have an unpacked recursive form. It is not clear to me how they behave in general.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "iwwETa8Owe", "reviewer": "Reviewer_iVyo", "summary": "This paper introduces a new algorithm, ICL-TSVD, designed to bridge the gap between theory and practice in continual learning (CL) with pre-trained models. It integrates an empirically strong approach RanPAC within the Ideal Continual Learner (ICL) framework. Specifically, ICL-TSVD lifts pre-trained features into a higher dimensional space, then addresses the ill-conditioning of these lifted features through continually SVD truncation, and solves the truncated form of an over-parameterized minimum-norm least-squares problem. Theoretically, it is shown that the method achieves small training and generalization error under certain conditions. Empirically, ICL-TSVD demonstrates stability across various hyperparameter settings and outperforms other CL baselines across multiple datasets.", "questions": "1. In Table 2, why the final accuracy of RanPAC on StanfordCars dataset is only 1.19%? Could you provide an explanation for it?\n\n2. Figure 5 does not plot the training time for RanPAC when embedding dimension $E = 50\\mathrm{K}, 100\\mathrm{K}$, is this because the training process is too slow?\n\n3. How about the running time of ICL-TSVD compared to other CL baselines, especially those that do not utilize SVD in their implementation?\n\n4. For original definition of $\\overline{\\bf{W}}_t$ in Eq. (2) and practical implementation of $\\widetilde{\\bf{W}}_t$ in Eq. (4), do they close to each other? In other words, is there any theoretically guarantee showing that $\\\\|\\overline{\\bf{W}}_t - \\widetilde{\\bf{W}}_t\\\\|_F$ is small in general?\n\n**Minor issues and typos**\n\n- In Eq. (5) of Section 5, the denominator of $\\gamma_t$ should be $\\max\\_{1\\leq i\\leq t-1}\\mu\\_{k_{i+1}}(\\widetilde{\\bf{B}}_i\\widetilde{\\bf{B}}_i^{\\top})$ instead of $\\max\\_{1\\leq i\\leq t-1}\\mu\\_{k\\_{i}+1}(\\widetilde{\\bf{B}}_i\\widetilde{\\bf{B}}_i^{\\top})$.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper clearly demonstrates the contribution of the proposed approach and is easy to follow.\n\n2. Extensive experiments across multiple datasets show that ICL-TSVD remains stable regarding hyperparameter selection (including regularization parameter $\\lambda$ and truncation percentage $\\zeta$) and consistently outperforms previous CL baselines, particularly RanPAC.\n\n3. It provides theoretical guarantees for the proposed method ICL-TSVD by revealing a recurrence relation throughout the CL process, showing that it has small estimation and generalization errors when a suitable fraction of SVD factors are truncated.", "weaknesses": "1. The continual Implementation of $\\overline{\\bf{W}}_t$ involves the computation of $\\widetilde{\\bf{B}}_t$, which has the form of $\\widetilde{\\bf{B}}_t = [\\widetilde{\\bf{U}}\\_{1:t-1}\\widetilde{\\bf{\\Sigma}}\\_{1:t-1}, \\widetilde{\\bf{H}}_t]$ when $t\\geq 2$ according to Eq. (3). Appendix C.1 briefly mentions that it is empirically found continually updating all SVD factors $\\widetilde{\\bf{U}}\\_{1:t}, \\widetilde{\\bf{\\Sigma}}\\_{1:t}$ and $\\widetilde{\\bf{V}}\\_{1:t}$ lead to large test errors. However, it remains unclear why authors use $\\widetilde{\\bf{B}}_t = [\\widetilde{\\bf{U}}\\_{1:t-1}\\widetilde{\\bf{\\Sigma}}\\_{1:t-1}, \\widetilde{\\bf{H}}_t]$ instead of $\\widetilde{\\bf{B}}_t = [\\widetilde{\\bf{U}}\\_{1:t-1}\\widetilde{\\bf{\\Sigma}}\\_{1:t-1}\\widetilde{\\bf{V}}\\_{1:t-1}, \\widetilde{\\bf{H}}_t]$ from a theoretical perspective. What are the difference and connection between these two implementations? Why just maintaining $\\widetilde{\\bf{U}}\\_{1:t-1}$ and $\\widetilde{\\bf{\\Sigma}}\\_{1:t-1}$ can serve as a substitution for all SVD factors, what is the motivation for that?\n\n2. In Section 6.2,  ICL-TSVD chooses embedding dimension $E = 10^5$ while RanPAC uses the default choice $E=10^4$. It is not so convincing that this is a fair comparison although the authors claim that ICL-TSVD’s implementation is more scalable and more efficient than RanPAC’s. Figure 8 and Table 13 in Appendix K indeed show that ICL-TSVD does not outperform RanPAC on about half of the datasets.\n\n3. \n  - For Theorem 1, take Figures 3 and 4 for example, the truncation percentage is set to 25%. Then based on eigenvalues vs. eigenvalue index shown in Figure 1, $a_t$ should be at least in the order of $10^5 \\sim 10^6$, and $\\gamma_t$ is around or slightly larger than 1. In this case, the bound for the estimation error can be very large even if the unknown ground-truth $\\\\|\\mathbf{W}_t^*\\\\|_F^2$ and noise $\\\\|\\mathcal{E}\\_{1:t}\\\\|^2$ are reasonably small, which means that the theoretical guarantee does not match with empirical results. And similar issue exists in Theorem 2 as well. \n  - Furthermore, without independent i.i.d. Gaussian vectors assumption on $\\bf{h}$ and the columns of $\\bf{H}\\_{1:t}$ (which is unrealistic for practice), we may not guarantee that $\\\\|\\Lambda - \\frac{1}{M_t}\\bf{H}\\_{1:t}\\bf{H}\\_{1:t}^{\\top}\\\\|$ converges to 0 as $M_t\\rightarrow\\infty$. \n\n4. 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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sA2GiTrULs", "reviewer": "Reviewer_P9vj", "summary": "The paper tackles the problem of class-incremental learning (CIL).\nTo this end, the paper improves RanPAC (McDonnell et al., 2023), making it more numerically stable as a least-squares problem, by truncating small singular values from the SVD of the (pretrained) embeddings of the samples from *all* previous tasks. The truncation might also positively impact the generalization itself.\nThe authors link their method to a theoretical framework (ICL by Peng et al., ICML 2023) which derived sufficient conditions to preventing forgetting in linear models, and use this connection to derive some bounds on the training and generalization error of the proposed algorithm.", "questions": "Other than what I wrote above,\n\n1. I could not immediately understand why both RanPAC and the proposed method outperform the $LC(H_{1:T})$ benchmark (trained with the original cross entropy loss like explained in Appendix J). Even if the data matrices are ill-conditioned, early stopping (e.g., when performing a fixed number of steps) should create a remedying effect and help generalization. Is it possible that a better hyperparameter tuning is needed here? Did the authors check the training *and* test curves throughout the training of this competitor?\n\n1. 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)?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The proposed method seems to empirically improve upon the existing RanPAC method (McDonnell et al., NeurIPS 2023).\n1. The proposed method is easy to implement.", "weaknesses": "# Major concerns\n\n1. **Proposed analysis feels contrived.**   \nTo me, the analytical connection between ICL (Peng et al., ICML 2023) and the proposed method feels overly strained.\n    1. To begin with, the ICL formulations presented in Line 111 and 116, are purely theoretical (formalizing a sufficient condition to prevent forgetting), and *cannot* be considered continual learning approaches, since they require storing the data from all previous tasks.\n    1. In Line 105 (Eq. 1), the raw feature matrices $X_t$ are randomly mapped to the \"effective\" matrices $H_t=\\text{relu}(PX_t)$ using a random matrix $P\\in\\mathbb{R}^{E\\times d}$ where $E\\gg d$.\nTo facilitate the comparison to the ICL framework, in Line 113, the authors assume that $E$ is so large that it makes the *entire* task sequence feasible (jointly!). However, for most datasets, this would practically make the time and space requirements of the proposed method infeasible.\n    1. Theorem 1 also implicitly requires such extreme overparameterization or that the data can already be explained linearly almost perfectly. Otherwise, $\\Vert\\mathcal{E}_{1:t}\\Vert$ would be large, making the bound uninformative ($\\frac{M_t-k_t}{M_t}$ is not small).  \nHowever, if the data is linearly explained by some model $W^{*}_t$, then ICL trivially obtains 0 loss (since all previous data is stored and optimized simultaneously) and all that is left to analyze is the error stemming from the truncation (which implicitly assumes that the smaller singular values are very small, which might not be the case for arbitrary data).   \nIn my opinion, this is **not** a significant theoretical contribution.\n\n1. **Unclear if accuracy improvements are significant.**  \n 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.\n\n---\n\n## Summary of weaknesses\n\n Considering all of the above, I believe the paper constitutes a nice incremental improvement over RanPAC (using truncation instead of regularization), but I am not convinced that the analysis makes the paper valuable enough for ICLR.\n\n-----\n\n# Minor concerns\n\nI do not expect any response on the following concerns but I recommend addressing them in any future revised version.\n\n1. Many times (e.g., Line 160), the authors specify constant values like $\\lambda = 10^{4}$ and $\\lambda = 10^{-5}$  and refer to them as being very small or very large. However, I find these references problematic since the regularization strength in least-squares problems is meaningless without taking into account the scale of the data and the fitting error. Similarly, I would even go further and say that the main benefit from the proposed method is not that it gets rid of the smallest singular values, but that it remedies the *condition number* of the matrices. The smallest singular values can only be considered \"small\" when comparing to the largest singular values. An alternative method could have limit the condition number instead of using a fixed percentage $\\zeta$.\n\n1. I think Figure 1c would be better if it showed the training accuracy, since this is the origin of the problem there.\n\n1. The time complexity analysis should appear immediately after the algorithm, rather than as a side note on page 9. Space complexity should also be specified. Moreover, at some point, given enough tasks, $M_t = k_{t-1} + m_t$ can become larger than $E$, which then makes the time complexity $E^3$ (notice that the $M_t - $E$ smallest singular values are zeros), just like in RanPAC.\n\n1. In Line 130, the authors say \"the theoretical justification for the strong empirical performance of RanPAC remains limited\". I kindly disagree and claim that it is trivially justified, since according to the formula in Line 124, it just minimizes *all* the losses simultaneously.\n\n1. To be slightly more precise, step 3 in Algorithm 1 should use the floor operator $\\lfloor(1-\\zeta)M_t\\rfloor$.\n\n1. The paper would be more readable if the dimensions are specified when matrices are first presented, e.g., the authors should specify the dimensions of ${\\widetilde{U,\\Sigma,B}_{1:t}}$ in Eq. (3).\n\n1. The sentence in Line 319 (about the values of $\\delta$) is unclear.\n\n1. The message of Figure 6 is unclear.\n\n1. In Theorem 1, I believe $\\frac{M_t-k_t}{M_t}$ is simply $(1-\\zeta)$.\n\n1. In Theorem 1, specify the subscript for the norm used for $\\mathcal{E}_{1:t}$.\n\n1. The presentation is often overcomplicated and inconsistent. For instance, in line 105 (Eq. 1), a projection matrix $P$ is introduced, while most of the analysis throughout the paper, especially in Section 5, completely ignores that matrix and deals with arbitrary deterministic feature matrices $H_t$. Moreover, I would consider presenting the ICL details only after the algorithm itself, as a retrospect.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)