Unlocking the Power of Rehearsal in Continual Learning: A Theoretical Perspective
Authors: Junze Deng
Qinhang Wu
Peizhong Ju
Sen Lin
Yingbin Liang
Ness Shroff
Venue: ICML 2025 poster (2025)
Keywords: Continual Learning
rehearsal-based methods
catastrophic forgetting
Primary area: theory->online_learning_and_bandits

Abstract: Rehearsal-based methods have shown superior performance in addressing catastrophic forgetting in continual learning (CL) by storing and training on a subset of past data alongside new data in current task. While such a concurrent rehearsal strategy is widely used, it remains unclear if this approach is always optimal. Inspired by human learning, where sequentially revisiting tasks helps mitigate forgetting, we explore whether sequential rehearsal can offer greater benefits for CL compared to standard concurrent rehearsal. To address this question, we conduct a theoretical analysis of rehearsal-based CL in overparameterized linear models, comparing two strategies: 1) Concurrent Rehearsal, where past and new data are trained together, and 2) Sequential Rehearsal, where new data is trained first, followed by revisiting past data sequentially. By explicitly characterizing forgetting and generalization error, we show that sequential rehearsal performs better when tasks are less similar. These insights further motivate a novel Hybrid Rehearsal method, which trains similar tasks concurrently and revisits dissimilar tasks sequentially. We characterize its forgetting and generalization performance, and our experiments with deep neural networks further confirm that the hybrid approach outperforms standard concurrent rehearsal. This work provides the first comprehensive theoretical analysis of rehearsal-based CL.

Unlocking the Power of Rehearsal in Continual Learning: A Theoretical Perspective
Junze Deng' Qinhang Wu? Peizhong Ju
Sen Lin
Yinghin Liang'
Ness Shroff 1.2
Abstract
1. Introduction
Continual learning (CL) (Parisi al.. 2019) seeks build an agent that can learn sequence of tasks continuously without access to old task data, resembling human's capability of lifelong learning. One of the major challenges therein is the so-called catastrophic forgetting (Kirkpatrick et al., 2017), i.e., the agent can easily forget the knowledge of old tasks when learning new tasks. large amount of studies have been proposed to address this issue, among which rehearsal- based approaches (Rolnick al., 2019) have demonstrated the
Rehearsal- methods have shown superior performance in addressing catastrophic forgetting in continual learning (CL) by storing and training a subset of past data alongside new data in current task. While such concurrent rehearsal strategy is widely used, it remains unclear if this approach is always optimal. Inspired by human learning, where sequentially revisiting tasks helps mitigate forgetting, we explore whether sequential rehearsal can offer greater benefits for CL com- pared to standard concurrent rehearsal. To address this question, conduct theoretical analysis of rehearsal-based CL in overparameterized linear models, comparing two strategies: 1) Concurrent Rehearsal, where past and new data are trained together, and 2) Sequential Rehearsal, where new data trained first, followed by revisiting past data sequentially. By explicitly characterizing forgetting and generalization error, show that sequential rehearsal performs better when tasks are less similar. These insights further motivate a novel Hybrid Rehearsal method, which trains similar tasks concurrently and revisits dissimilar tasks sequentially. We characterize forgetting and generalization performance, and our experi- ments with deep neural networks further confirm that the hybrid approach outperforms standard concurrent rehearsal. This work provides the first comprehensive theoretical analysis of rehearsal- based CL.
te-thhe-rtt -art performance. The main idea behind is to store a subset of old task data in the memory and revisit them for new task learning, where a widely adopted strategy for training is concurrent rehearsal (Goldfarb et al., 2024), i.e., train the model concurrently on new data and past data.
While the concurrent rehearsal strategy seems very natural and has shown successful performance to address catas- trophic forgetting. it is indeed questionable whether this strategy is always the right way for rehearsal in CL as we consider the following aspects. 1) From the perspective of human learning. In daily life, a common strategy to prevent forgetting is to review old knowledge. For example, suppose student needs to learn a series of topics over a semester be- fore taking an exam, and each topic corresponds to task in CL. Intuitively, if these topics are highly related each other, incorporating the knowledge of old topics into learn- ing new topic can be an effective strategy to strengthen the new learning and simultaneously reduce the forgetting of old knowledge, which is analogous to concurrent rehearsal. However, if the topics are very different from each other. a common practice is to learn new topics first and then go over old topics to mitigate forgetting. Here, such sequential rehearsal may lead to better outcome in the exam. 2) From the perspective of multi-task learning. Learning multiple tasks all at once may lead to poor learning performance due to the potential interference among gradients of different tasks (Yu et al., 2020), whereas standard CL. without regu- larization and rehearsal may even achieve less forgetting for more dissimilar tasks (Lin et al., 2023). Thus motivated, an interesting and open question to ask is:
Department of ECE, Ohio State University, Columbus, USA
2 DDpaatmeett of CSE, Ohio State University, Columbus, USA
2 DDepartment of CS, University of Kentucky, Lexington, USA
"Department of CS, University of Houston, Houston, USA. Corre- spondence to: Junze Deng <deng. 942 @ osu.edu>>.
Proceedings of the ndnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
Question: Whether sequential rehearsal will serve as an appealing rehearsal strategy to complement the standard

---

Unlocking the Power of Rehearsal in Continual Learning: A Theoretical Perspective
concurrent rehearsal, and when will it be advantageous over concurrent rehearsal for CL.
rehearsal, leading to a novel hybrid rehearsal approach where 1) old tasks dissimilar to the current task will be revis- ited by using sequential rehearsal (guided by our theory that suggests more benefit if dissimilar tasks are revisited sequen- tially) and 2) the past data for the remaining old tasks (that are sufficiently similar to the current task) will still be used concurrently with current task data. Our experiments on real datasets with DNNs verify that our hybrid approach can perform better than concurrent rehearsal and the advantage is more apparent when tasks are more dissimilar.
To answer this question from a theoretical perspective, we study rehearsal-basee CL through the lens of overparame- terized linear models to gain useful insights, by following a recent series of theoretical studies in CL (Lin et al., 2023; Evron et al., 2022; Ding et al., 2024; Li et al., 2024). How- ever, none of those previous studies analyzed the rehearsal- based methods. The only theoretical work that studied the rehearsal-based methods is the recent concurrent work (Ba- nayecanzade et al., 2024). But this work considered only the standard concurrent rehearsal method, not from the new perspective of sequential rehearsal.
2. Related Work
Empirical studies in CL. CL has drawn significant atten- tion in recent years, with numerous empirical approaches developed mitigate the issue of catastrophic forgetting, Architecture-be based approaches combat catastrophic forget- ting by dynamically adjusting network parameters (Rusu et al., 2016) or introducing architectural adaptations such as an ensemble of experts (Rypešé et al., 2024). Regularization- based methods constrain model parameter updates to pre- serve the knowledge of previous tasks (Kirkpatrick et al., 2017; Magistri al., 2024). Memory-based methods ad- dress forgetting by storing information of old tasks in the memory and leveraging the information during current task learning, which can be further divided into orthogonal pro- jection based methods and rehearsal -based methods. The former stores gradient information of old tasks to modify the optimization space for the current task (Saha et al., 2021; Lin et al., 2022b), while the latter stores and reuses a tiny sub- set of representative data, known as exemplars. Exemplar sampling methods involve reservoir sampling (Chrysakis & Moens, 2020) and an intomaation-thhoreee evaluation of exemplar candidates (Sun et al., 2022). Other work such as Shin et al. (2017) retains past knowledge by replaying "pseudo-rehearsal" constructed from input data instead of storing raw input. Rehearsal methods mostly use a concur- rent scheme that trains the model using a mix of input data and sampled exemplars (Chaudhry et al., 2018; Dokania et al., 2019; Rebuffi et al., 2017: Garg et al., 2024). Other exemplar utilization methods include Lopez-Paz & Ranzato (2017) and Chaudhry et al. (2018), which use exemplar to impose constraints in the gradient space.
To capture the idea of sequential rehearsal, we propose novel rehearsal strategy, in which the agent sequentially revisits each old task and trains the model with the corre- sponding past data after the current task is well learned.
We summarize our main contributions as follows.
(I) First of all, we provide the first explicit closed-form expressions for the expected value of forgetting and gen- eralization error for both concurrent rehearsal strategy and sequential rehearsal strategy under an overparameterized linear regression setting. Note that the blending of samples from old tasks in concurrent rehearsal introduces significant intricacies related to task correlation in theoretical analysis. To address this challenge, we partition training data into blocks based on different tasks, which enables us to further calculate the task interference using the properties of block matrix. In particular, our theoretical results demonstrate how the performance of rehearsal-based CL is affected by various factors, including task similarity and memory size.
(2) Secondly, we propose a novel rehearsal strategy, i.e., se- quential rehearsal, to sequentially revisit old tasks after the current task fully learned. By characterizing the explicit closed-form expressions for the expected forgetting and gen- eralization error for sequential rehearsal and comparing with the concurrent rehearsal, we give an affirmative answer to the open question above. More importantly, we rigorously characterize the conditions when sequential rehearsal can benefit CL more than concurrent rehearsal, in terms of both forgetting and generalization error, which also consistent with our motivations above: Sequential rehearsal outper- forms concurrent rehearsal if tasks in CL are dissimilar, and the performance improvement is larger when the tasks are more dissimilar. Numerical simulations on linear models further corroborate our theoretical results.
Theoretical studies in CL. Compared to the vast amount of empirical studies in CL, the theoretical understanding of CL is very limited but has started to attract much attention very recently. Bennani & Sugiyama (2020); Doan et al. (2021) investigated CL performance for the orthogonal gra- dient descent approach in NTK models theoretically. Yin et al. (2020) focused on regularization based methods and proposed framework, which requires second-order infor- mation to approximate loss function. Cao et al. (2022); Li et al. (2022) characterized the benefits of continual represen-
(3) Last but not least, our thcoretical insights can indeed go beyond the linear models and guide the practical algorithm design for rehearsal-based CL with deep neural networks (DNNs). More specifically, we merge the idea of sequential rehearsal into standard sitearrsll-bsce CL with concurrent
2

---

Unlocking the Power of Rehearsal in Continual Learning: A Theoretical Perspective
tation learning from theoretical perspective. Evron al. (2023) connected regularization-hasse methods with Pro- jection Onto Convex Sets. Recently, a series of theoretical studies proposed to leverage the tools of overparameter- ized linear models to facilitate better understanding of CL Evron et al. (2022) studied the performance of forgetting under such a setup. After that, Lin et al. (2023) character- ized the performance of CL. where they discuss the impact of task similarities and the task order. Ding et al. (2024) further characterized the impact of finite gradient descent steps on forgetting of CL. Goldfarb & Hand (2023) illus- trated the joint effect of task similarity and overparameter- ization. Zhao et al. (2024) provided a statistical analysis of regularization-basel methods. More recently, et al. (2024) theoretically investigated the impact of mixture-of- experts on the performance of CL in linear models.
consider i..d. Gaussian features and noise, i.e., each ele- ment of X, follows i...d standard Gaussian distribution, and 2, NN0 of In,) where or 2 0 denotes the noise level. To make our result easier to interpret, we let of = a and
n4 = n for all i E [T]-
Memory. For any task t 2 2, besides Dr, the agent has an overall memory dataset M, that contains separate memory datasets Mr. for each of the previous tasks h E [t 1]. i.e., M₁ = U Mr... where Me, = (X..,, Y.,)) E REXM, x RM denotes the samples from previous task h and we define M,, as the number of samples in Mr,. In most CL applications, the memory space is fully utilized and the memory size does not change over time. We denote this memory size by M that does not change with t. In this case, we have 2h=1 Ma,1 = M for any t 2 2. To simplify our theoretical analysis, we focus on the situation in which the memory data are all fresh and have not been used in previous training. We equally allocate the memory to all previous tasks at each time t, i.e., Ma, r-1 h E [t - 1]. For simplicity, we assume 1-1 for any / E (2,3...,,)) ,T)-
Different from all these studies, we seek to fill up the theo- retical understanding for rehearsal- CL. Note that one concurrent study (Banayeeanzade et al., 2024) also investi- gates rehearsal- based CL in linear models with concurrent rehearsal. However, one key difference here is that we pro- pose a novel rehearsal strategy, i.e., the sequential rehearsal, and theoretically show its benefit over concurrent rehearsal for dissimilar tasks. Our theoretical results further motivate a new algorithm design for CL in practice, which demon- strates promising performance on DNNs.
.M. for
M is an integer'
Performance metrics. We first introduce the model error of parameter w over task i's ground truth.
(iw)) = ||20- - w
3. Problem setting
We note that this formulation is widely adopted in recent theoretical studies(EEvron et al., 2022; Lin et al., 2023). The performance of CL. measured by two key metrics, which are forgetting and generalization error. Let w. be the param- eters of the training result at task
We consider a common CL setup consisting of T tasks where each task arrives sequentially in time t E [T]. Here [T' := {1, 2.., T for any positive integer T. Let Ip de- note the p x p identity matrix and let |]-|]| denote the fn-norm.
...,
1. Forgetting: It measures the average forgetting of old tasks after learning the new task. In our setup, forgetting at task T w.r.. previous tasks [T 1] is defined as follows.
Data Model. We adopt the setting of linear ground truth which is commonly used in recent theoretical analysis of CL, e.g., (Lin al., 2023; Li al., 2024: Banayeeanzade al., 2024). Specifically, for each task & [T'. a sample (xt, v1) is generated by linear ground truth model:
T Σ
Fr
E(C,(wT) - (ww)))
(4)
yt x. u + Zt:
(1)
2. Generalization error: It measures the overall model generalization after the final task is learne.. In our setup, generalization error is defined as follows.
where se E R denotes features, y R denotes the output, wi E R2 denotes the ground truth parameters, and 2, E RR denotes the noise.
Dataset. For each task / E [T], there are n, training sam- ples (Ziti, (ta))s We stack those samples into ma- trices/vectors to obtain the dataset D.- = {(x,, Yi) E
T GT = 7 M B[Cx(wT)]
(5)
Rex", x R" ). By Equation (1), we have
The definitions are consistent with the standard CL perfor- mance measures in experimental studies (Saha et al., 2021).
Y = x, w + Zt:
(2)
.M Wee note that without the assumption of r-] E Z, memory can still he allocated as equally possible, resulting in only minor error. Our theoretical results remain referential significance.
where X, = [x1,1 x1,2 Iimb Y, =
[ye,1 vt.2 ... ]e, T and 2, := [zt,1 21,2 )),
We
3

---

Unlocking the Power of Rehearsal in Continual Learning: A Theoretical Perspective
4. A Novel Sequential Rehearsal vs. Popular Concurrent Rehearsal
Dr Mes, Mazi Maz-1
ML1
[23
In this section, we first introduce the popular concurrent rehearsal strategy that is widely used in current CL appli- cations to mitigate catastrophic forgetting. We will then propose a novel sequential rehearsal strategy, which has appealing advantage compared to concurrent rehearsal.
M2z-1
3GD
SGD
Wr-1
Concurrent Rahearsal
Sequential Rehearsal
W--1
We
Figure 1. An illustration of concurrent and sequential rehearsal.
To describe these rehearsal strategies, note that the training result w, at task t will be used as the initial point for the next task & ++1 1. The initial model parameter of task 1 is set to be 0, i.e., Wo O. The training loss for task t is defined by mean-squared-error (MSE). We focus on the over- wve-pparameterized case, i.e., p > n + M. As shown in (Zhang et al., 2022; Gunasekar et al., 2018), the convergence point of stochastic gradient descent (SGD) for MSE is the feasible point closest to the initial point with respect to the f--norm, i... the minimum- norm solution.
5. Main Results
The main theoretical results consist of two parts. First, we derive closed forms of forgetting and generalization error for both concurrent and sequential rehearsal methods. Second, we compare the performance of these two rehearsal- schemes, concluding that sequential rehearsal outperforms concurrent rehearsal when tasks are dissimilar.
5.1. Characterization of Forgetting and Generalization Error
Concurrent rehearsal. We first introduce the popular con- current rehearsal strategy as follows. At each task 2 2, we apply SGD on the current dataset and the memory dataset jointly to update the model parameter. Specifically, as il- lustrated in Figure via SGD on the combined dataset D; M, with the initial point w and obtain the convergent point wt as
In rehearsal-based CL methods, the interference among tasks throughout the entire training process is intricate, due to the presence of the memory dataset. This introduces an unavoidable challenge in understanding the impact of memory on the performance of rehearsal -baed methods.
time L, we minimize the MSE loss
wi- = arg min |w w1-1l
Following from the definitions of forgetting and generaliza- tion in Equations (4) and (5), the key evaluating their per- formance lies in calculating the expected value of model er- rors over any previous task 7th ground truth after learning the final task (i.c., ([C, (wT) )D) Indeed, for a generic t < T, the explicit expressions of E[C, w.)] and (E,,(w,) - (w;) share the same structure for both rehearsal methods. Thus, further following from the definitions of forgetting and gen- eralization error, we present a common performance struc- ture shared by both concurrent rehearsal and sequential rehearsal methods in the following theorem.
s.t. X, wY N = A..WYYA Vh E 11.
Novel sequential rehearsal. In scenarios where previous tasks are very different from the current task, concurrent rehearsal may result in contradicting gradient update di- rections, and can hurt the knowledge transfer among tasks. Consequently, concurrent rehearsal may not always perform well. This motivates novel rehearsal strategy that sequen- tially revisits history tasks one by one after training the current task, analogously to the way how a student reviews previously learned topics to avoid forgetting before exams.
Theorem 5.1. Under the problem setups in this work, the forgetting and the generalization error at time T 2 2 in both rehearsal- methods take the following
To formally describe the training (see Figure 1 for an illus- tration), at each task 2 2, we first train on the current dataset D. to learn the new task until the convergence to the initial stopping point ()) Then, for h = 1,2, t 1, we start from the previous stopping point w w((h1 (h-1) and train the memory dataset MG, to converge to the next stopping point. Eventually, w, is obtained after revisiting all memory sets, i.e., w;- w((- (t-1) To simplify, we define X == X Yo. == Y2 and w; (-1) == w1-1. Then, the training process is equivalent to solve the following optimization problems recursively for h = 0, 1,..,, 1:
T-1
T-1 T-1 ΣΣ j,k=1
Fr
1 T
Σ
c |w
Cisk || |wj - w
(noiser - noise;
+
Gr = dor
GT
|
+
disHT 1|m3 will?
JAk=1
noiser (a), (6)
(h)
arg min w w!! (h-11) 1112 s.t. X a. w Ye,
w
where coefficients and the noise term depend on P. n, M, as provided in Appendix for both rehearsal -ased methods.

---

Unlocking the Power of Rehearsal in Continual Learning: A Theoretical Perspective
Theorem 5.1 indicates that both rehearsal-based methods share the same high-level performance dependence the system parameters. It can be seen that both of their for- getting and generalization eгror consist of the following three components. The first component exhibits the form of C'Ile,; |I for some constant C, which arises from the overpa- rameterized linear regression error. The second component captures the impact of task dissimilarities, representing the interference among different tasks during the training pro- cess. Extracting central information from this component is particularly useful for understanding how task dissimilar- ity affects the comparison between the two rehearsal- based methods, which is the focus of Section 5.2. The third part captures the impact of the noise level.
2023) since different tasks in the memory dataset as well as the current task are learned one by one. The third term cap- tures the noise, which can be analyzed by applying "trace trick" and the properties of Inverse-
distribution.
5.2. Comparison Between Concurrent rehearsal and Sequential rehearsal
The main challenge to compare the performance between the two rehearsal- -based methods lies in the complexity of the second term in forgetting and generalization in Theorem 5.1, which captures how the task similarity as well as memory data affect the performance. Here the task similarity is characterized by the distance between the true parameters for two tasks. In this section, we will first study a simple case with two tasks, i.e., when T = 2, to build our intuition, and then extend to the case with general T based on the central insight obtained in the simple case.
Here, we first provide some basic conclusions for the coeffi- cients in Theorem 5.1. (i) By letting M = 0, both training methods yield the same result, which is consistent with the memoryless case shown by Lin et al. (2023). (ii) We can also observe that low task similarity negatively impacts model generalization, as dısaT (defined in Proposition C.2) are non-negative. When p >> oc, we observe that the value of coefficients dijter approaches to 0 for both rehearsal meth- ods, which implies the negative influence of task dissimi- larities will be alleviated if the model has enough capacity (i.e., when p is sufficiently large). (iii) We observe that the forgetting approaches to 0 when + co. This implies that a model with substantial capacity will facilitate effective learning for each task without forgetting, which can also alleviate the negative impact of task dissimilarity.
Two-task Case (T = 2): Given the noise level a, we de- note noise; = noise, (σ) for simplification. Following from Theorem 5.1, the performance of both rehearsal methods shares the common form:
F2 è w/ll + è2 [! -wIll + noisez noise1,
G2 = di (|] + || (1] + d2 || - will + noise2,
where the specific expressions of constants é, 62 dj. de for both rehearsal methods are provided in Appendix D. To compare between the two rehearsal-based methods, the following lemma captures how their coefficients compare with each other.
Outline of Proof of Theorem 5.1. We provide a brief outline of the proof of Theorem 5.1 here, and the detailed proof is given in Appendix C. By the definition of forgetting and generalization error, it is sufficient to analyze ((C,(w))) and (w,) - (- We next explain how to obtain the explicit expression for (wC)(.:)) ]]. and E[[, (w: can be calculated in a similar way by substituting t with i.
Lemma 5.2. Under the problem setups of the two-task case, we have
flconcrrent)
(sequemiaa)
connurrennt
sequential)
(econurrent) Jsequential)
concurrent)
d2
ssequentaal
The derivation of [w[,(w:)) is carried out through an iter- ative procedure as follows. We first split (w,)) into three terms as follows:
Intuitively, when the task dissimilarities are sufficiently large (i.e.. || - wwill large), then ê2 and de will domi- nant forgetting and generalization error respectively. Then Lemma 5.2 suggests that sequential rehearsal will have less forgetting and generalization error than concurrent rehearsal. Alternatively. if the tasks are very similar and the noise is small, then é₁ and dj will dominate the performance, and concurrent rehearsal will yield better performance. The fol- lowing theorem formally establishes the above observations. Theorem 5.3. Under the problem setups considered in the work, we have
(w,)l = ge (E[[C(w,,))) + term + termnoise>
where gt, terma and termaoise are given in Equation (26) in Appendix C. We then analyze each of those three terms.
The first term ge (I)) can be evaluated by iter- atively rolling out to the initial term, which can then be derived explicitly. Note that the function 9-) takes a linear form, which simplifies the iteration. The second term cap- tures the interference among different tasks during training process. For concurrent rehearsal method, we further derive it by partitioning the data from different tasks and leveraging the properties of block matrices. For sequential rehearsal, we follow the same idea as the memoryless case (Lin et al.,
picomeurrent)
> F2 pisequential
iff
E
w
+5202
>
1,
G (eooeerrent) >
G
(sequentiaa)
iff
>
1,
w
5

---

Unlocking the Power of Rehearsal in Continual Learning: A Theoretical Perspective
where E1, S2; 11, P2 are positive constants with detailed ex- pressions given in Appendix D.
such an advantage should be more apparent tasks become more dissimilar. To explain this, we consider the generaliza- tion error as example. Assuming that the norm of ground truth is fixed, a higher level of task dissimilarities exacer- bates the generalization error since each coefficient disAT (defined in Proposition C.2) is positive for both training methods. However, a weaker dependence on task similar- ities indicates that the generalization error of sequential rehearsal grows slower than concurrent rehearsal tasks become more dissimilar, resulting advantage for sequential rehearsal to enjoy smaller generalization error. A similar reason is applicable to the f'orgetting performance, although it is important to note that Gijk is not always positive.
Theorem 5.3 provably establishes an intriguing fact that the widely used concurrent rehearsal may not always perform better, and sequential rehearsal can perform better when tasks are more different from each other. We further elabo- rate our comparison between the two methods for the case with T = 2 in Appendix D (where the impact of noise is also considered) and with T 3 in Appendix E. The in- sights obtained from Theorem 5.3 can also be extended to the general case as follows.
General Case (T'S > 2): Comparing the performance in two rehearsal methods provided in Theorem 5.1 under general T is significantly more challenging, because the mathematical expression of the coefficients become highly complex. How- ever, our insights obtained from the two-task case can still be useful, i.e., sequential rehearsal tends to performance better when tasks are very different. To formalize such an observation, the following lemma compares the coeffi- cients in forgetting and generalization error between the two rehearsal methods.
Simulation Experiments:
To validate our theoretical in- vestigation, we conduct simulation experiments on CL with overparameterizeed linear models. Set T 5, p 500, = 24, a = O and M 24. The construction of ground truth features follows two principles: 1) each fea- ture is drawn from the unit sphere, and 2) the task gap (i.e.. |w - wi w|| between any two features is identical. Under different setups of the task gap, the comparisons between theoretical results and simulation results are shown in Fig- ure 2 in terms of both forgetting and generalization error. Here, the theoretical results are calculated according to The- orem 5.1, and the simulation results are obtained by taking the empirical expectation over 10s iterations.
Lemma 5.4. Under the problem setups considered in the work, the value of coefficients Ct, Cijko dor, digker in Theo- rem 5, as derived from different rehearsal methods, satisfy the following relationship.
L (concurent)
< 4 (vequential)
(concurrent) Ajk concurrentt
[vequentia))
Gjjk
OT
concurrent)
< dor
fsequential)
jKT
2
(requential
Sequeniid (rrears)
Conceraat Conmurent (Smiatte
1.3 Concurur:: Thepyl
Sequertial (iThsoy)
Concumeet (Sim stedi
Sequendsl
3.10
The above lemma suggests that if the tasks are all very dif- ferent from each other, then sequential rehearsal will have smaller forgetting and generalization error than concurrent rehearsal because (concurrent) Cijk
1.1
Forgutingg
0.00
1.0
Ganuraak
3.55
> Cijk (sequential) and (concurrent digTT
-3.00
(ssquential) will dominate the comparison. While it is chal- 'jkk
-2.5
lenging to provide an exact closed-form characterization of the conditions under which sequential rehearsal outperforms concurrent rehearsal, the following theorem presents an ex- ample where sequential rehearsal outperforms concurrent rehearsal, based on the understanding outlined above.
0.0
0.5
3.0
1.5
2.0
3.0
6.5
1.5
1.5
2.0
Tosk Gap
Task Gap
(a) Forgetting vs Task Gap
(b) Generalization Froo Task Gap
Figure 2. Forgetting and Generalization Error vs Task Gap
Theorem 5.5. Under the problem setups in this work, sup- pose the ground truth w is orthonormal to each other for i E [T], M 2 2, and p = OT** 2 Then we have:
Several important insights can be immediately obtained from Figure 2: 1) Our theoretical results exactly match with our simulation results, which can clearly corroborate the correctness of our theory. 2) When tasks are similar, i.c.. the task gap |ww - wwl is small than some threshold, concurrent replay is better than sequential replay. However, when tasks become dissimilar, sequential replay starts to outperform concurrent replay in terms of both forgetting and generalization error. And the advantage of sequential replay becomes more significant as the task gap increases, which also aligns with our theoretical results.
Fl (concurreet)
>
Fl F(sequontinl
and Grconcurent) > GT
Cesequoniaa)
In Theorem 5.5, orthonormal w/ is extreme case to have very different tasks. Typically, since forgetting and gener- alization error are continuous functions of the task dissimi- larity, we expect that in the regime that the tasks are highly different, sequential rehearsal will still be advantageous to enjoy less forgetting and smaller generalization error, and
6

---

Unlocking the Power of Rehearsal in Continual Learning: A Theoretical Perspective
Remark. It is clear that the order in which old tasks are revisited after current task learning is very important der the framework of sequential rehearsal, which affects both forgetting and generalization errors. Needless to say, the sequential order considered in this work, where tasks are reviewed from the oldest to the newest, is not neces- sarily the optimal strategy for sequential rehearsal, where however has already demonstrated exciting advantages over concurrent rehearsal. How to design an effective rehearsal order to achieve better performance is a very interesting yet challenging future direction.
of the task similarity. Instead, a heuristic-based estimation should be sufficient, by following the gradient-based sim- ilarity characterization as in previous studies (Lopez-Paz & Ranzato, 2017: Lin et al., 2022a:b). To learn task t, we first train the model concurrently on the combined dataset consisting of the current task data Dj and the memory sam- ples from similar tasks M Subsequently, we perform sequential rehearsal by finetuning the learned model on the memory data from each dissimilar task in M The function UPDATEMEMORY represents general exemplar sampling strategy, such as Reservoir Sampling (Rolnick et al., 2019).
6. Implications on Practical CL
Under the problem setups considered in the work, the theo- retical forgetting and generalization error of hybrid re- hearsal strategy under linear models follow the same general expression described in Theorem 5.1. The explicit expres- sions for coefficients are provided in Appendix H. In what follows, we validate the advantage of hybrid rehearsal strat- egy through experiments conducted on real-world datasets and DNNs.
6.1. Hybrid Algorithm Framework
As our theory suggests, sequential rehearsal can benefit CL more than concurrent rehearsal when tasks are dissimilar. Hence, interesting idea and potential way improve the performance is to merge sequential rehearsal into rehearsal- based CL with concurrent rehearsal. Thus inspired, we propose a novel hybrid rehearsal framework, which adapts between concurrent rehearsal and sequential rehearsal for each task based on its similarity with old tasks in the mem- ory. The details are presented in Algorithm 1.
6.2. Hybrid Rehearsal for CL in Practice
95
Accuracy (%)
90
Algorithm 1 Hybrid Rehearsal Training Framework Initialization. Model parameters for task t= 1,2,..... ... T do Retrieve current data D, and memory data Mr if Me # 9 then
85
80
Cencuren:
Consummntt (Comupted)
+yhr di (comuststt
75
2
M .Mdis <- DIVIDEBUIFER(MM)
Tasks (Split (Split-CIFAR-10)
end if
< CONCURRENTTRAINCD, U MM
80
Convurmer
for h: Mr, E M.T do
Accuracy 1%6
75
Consurenn (Camstted)
0 t SEQUENTIALTRAN((MM.)
70
end for
65
Me+1 +- UPDATEMERMRY U.)
60
end for
55
2
3
Tasks (SPlit-CIFAR-100)
In Algorithm 1, prior training on task f,, the overall mem- ory dataset M, is first divided into Masi! and M de- pending on whether previous tasks are similar to the current
75
65
task or not. Specifically, there are two steps in function DIVIDEBUFFER(MM) we characterize task similarities between the current task D, and each previous task in the memory Mi, MMe based on their cosine similar- ity of gradients with respect the model parameters, i.c., S.(VoL(,, (,-)), VoL(M..)) 0,-1), where L denotes training loss and S. is the cosine similarity function; 2) any previous task for which the similarity score is below a threshold 7 will be regarded as a dissimilar task and its data will be put into Mil.s It is important to note that this framework does not rely on very accurate characterizations
Accuracy
55
45
Hyand
Concurent
(empgas) Iyand (oomstted
35
1
2
3
4
5
Tasks
Figure 3. Evolution of Accuracy Acc for Concurrent rehcarsal and Hybrid rehearsal across three datasets and their corrupted variants, corresponding to the results reported in Table I.
As an extension of our theoretical results, we verify the
7

---

Unlocking the Power of Rehearsal in Continual Learning: A Theoretical Perspective
Table 1. Averaged Final Accuracy Ace and Averaged Final Forgetring Fgt of different rehearsal methods (concurrent rehearsal hybrid rehearsal) on three datasets and their corrupted variations. "Improvement" shows the Acc or F'gt overhead that hybrid rehearsal achieves over concurrent rehearsal under the same setup. For all datasets, we construct a sequence of tasks for training. The reported results are presented with + standard deviation. All results are averaged over 10 independent runs.
Metric
Acc (t)
Fgt (4)
Acc (t)
Fgt (4)
Acc (1)
Fgt (L)
Dataset
Split- Sait-CIFAR-OO
Split Split-CIFAR-II CIFAR-100
Oplit-Tinlmmagemeee
Concurrent rehearsal
8.62
9.73 0.76
68.43 a 0.93
14.56
61.10
13.28 a 0.30
Hybrid rehearsal
87.27 0.55
8.25 0.50
69.92 + 0.52
11.29 0.79
63.29+047
9.62 0.45
Improvement
+1.07
-1.48
+1.49
-3.27
+2.19
-3.66
Dataset
Corrupted Split-CIFAR-10
Corrupted Split-CIFAR-100
Corrupted Spiit-Tinllmagene22200
Concurvent rehearsal
82.01 0.90
11.14
6.57
17.35 0.75
$2.69+044
15.23 + 0.49
Hybrid rehearsal
83.45 2022
6.90 = U.56
64.34
9.49 =: 1.67
55.07 0.33
1.91 = 0.69
Improvement
+1.44
-4.24
+-2.01
-7.86
+2.38
-13.32
performance of the proposed hybrid framework in Algo- rithm 1 and compare it with the widely-used concurrent re- hearsal. We consider three real-world datasets under a task- incremental CL setup: CIFAR-IO, CIFAR- 100 (Krizhevsky et al., 2009), and Tinylmagenet2000 (Le & Yang, 2015). Following recent work (Van de Ven et al., 2022), we ran- domly partition the classes from each dataset into multi- ple tasks, yielding Split-CIFAR-10, 10, Split-CIFAR-100, and
mance evolution during CL for all settings from Table in Figure 3, where each point shows the average performance of the model after learning task on all seen tasks so far. While the performance of hybrid rehearsal may degrade during intermediate tasks, it consistently surpasses concur- rent rehearsal in terms of final performance, highlighting the effectiveness of sequentially dissimilar task data for better knowledge consolidation.
the model on
Dolit-Tinllmagene2000 For example, in Split-CIFAR- 10, the sequence of tasks each task contains two distinct classes. The objective for each task Ta is to classify between (1.2) with the task label explicitly provided during training and testing. We employ non-pretrained ResNet18 as the backbone model for all three datasets. To evaluate the performance, we de- note ag,t as the testing accuracy on task t after training task l: and consider the following two metrics: 1) Final Average Accuracy (Acc) across all seen tasks after training defined as Ace- = + Σ @T,r, which can be regarded as generalization error, and 2) Final Average Forgetting (F gt), defined as Fgt = 1 Σ Et= (ar, aT,+), which evaluates the average accuracy drop of old tasks after learning the final task.
To demonstrate the potential of hybrid rehearsal, we con- sider a challenging setup on Split-CIFAR-100 and Split- Tinylmagener200 with a long task sequence, i.e., under a 20-task setting. As shown in Table 2, hybrid rehearsal out- performs concurrent rehearsal by a more pronounced gap, demonstrating the scalability and effectiveness of the hybrid rehearsal strategy in scenarios with a large number of tasks.
T is constructed such that
Furthermore, following our theoretical insight, the hybrid rehearsal strategy exhibits greater advantages when the task dissimilarity is higher. To validate this, we increase task dis- similarity by applying image corruption to one specific task in each of the three datasets, generating Corrupted Split- CIFAR-10, Corrupted Split-CIFAR-1000 and Corrupted Split- ImnyImagenet200. Details of the employed image cor- ruption schemes are provided in Appendix A.3. As shown in the second part of Table 1, hybrid rehearsal outperforms con- current rehearsal in both accuracy and forgetting by a larger margin on all three corrupted dataset variations, aligning with our theoretical insight.
Here, to simplify our comparison between hybrid rehearsal and concurrent rehearsal while avoiding extraneous com- plexities such as rehearsal task ordering (which beyond the scope of this paper), we adopt straightforward relax- ation: most one task with the lowest similarity charac- terization in memory is designated as the "dissimilar task". As shown in Table 1, hybrid rehearsal consistently outper- forms concurrent rehearsal across all three datasets in terms of both average accuracy and forgetting. For the original datasets, the most significant improvement observed on where hybrid rehearsal achieves a 2.19% higher accuracy than concurrent rehearsal while also reducing forgetting by 3.66. We further report the perfor-
To characterize the impact of task similarity on hybrid re- hearsal, we next control the similarity by applying various proportions of label corruption in the task sequence on Split- Tinylmagenet200. For each class within a corrupted task, Peor % of training samples are randomly selected and their labels are uniformly reassigned other class labels within the same task. Intuitively, the tasks are more dissimilar when larger proportion of labels are corrupted. In particular, we
8

---

Unlocking the Power of Rehearsal in Continual Learning: A Theoretical Perspective
In particular, we proposed a novel rehearsal strategy, namely sequential rehearsal, which revisits old tasks in the memory sequentially after current task learning, By leveraging over- parameterized linear models with equal memory allocation, we provided the first explicit expressions of both forgetting and generalization errors under two rehearsal methods: con- current rehearsal and sequential rehearsal. Comparisons between their theoretical performance led the insight that sequential rehearsal outperforms concurrent rehearsal in terms of forgetting and generalization error when the tasks are less similar, which is consistent with our motivations from human learning and multitask learning. Our simulation results on linear models further corroborated the correctness of our theoretical results. More importantly, based on our theory, we proposed a novel hybrid rehearsal framework for practical CL and experiments on real-world data with DNNs verified the superior performance of this framework over tra- ditional concurrent rehearsal. To the best of our knowledge, our work provides the first comprehensive theoretical study on rehearsal for rehearsal- based CL, which could motivate more principled designs for better rehearsal -baadd CL.
Table Ace and Fgt of different rehearsal methods Split- CIFAR-I00 100 and Split- Tiny For all datasets, we con- struct sequence of tasks for training, All results are averaged over 5 independent runs.
Dataset
Split-CIFAR- 100
Split- Tinllmageee22200
Concurrent
67.99 = 0.21
62.94 0.60
Hybrid
72.31 0.38
66.46 0.113
Improvement
+4.32
+3352
Table 2.1 Acc (t)
Dataset
Split-CIFAR-100
SpiitTinylmagenee200
Concurrent
13.91 2011
15.05+0.0
Hybrid
2.18
13.03 0.79
Improvement
-6.48
-2.0
Table 2.2 Fgt (4)
Table Acc and F'gt of different rehearsal methods on Split-Tiny- Imagenet200, where a subset of training data labels are corrupted in the first two tasks. All results are averaged runs.
independent
Setting
Poor = 5%
Peor = 10%
Poor 20%
Acknowledgment
Concurrent
57.36 0.06
53.92 + 0.78
19.07 #: 0.59
This work has been supported in part by the U.S. National Science Foundation under the grants: NSF AI Institute (AI- EDGE) 2112471, CNS-2312836 RINGS-2148253, CNS- 2112471, 2324052, and ECCS-2413528, Office Naval Research Grant N000142412729, and was sponsored by the Army Research Laboratory under Cooperative Agreement Number W91 NFF23-2200 The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official poli- cies, either expressed or implied, of the Army Research Laboratory or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Gov- ermment purposes notwithstanding any copyright notation herein.
Hybrid 60.02 0.36
56.88 : 0.12
63.73- = 0.60
Improvement
+2.66
+2.96
+4.66
Table 3.1 Acc (t)
Setting
Poor = 5%
Poor = 10%
Poor 20%
Concurrent
0.28
17.40
17.35 + 1.15
Hybrid 11.26
12.73 1.00
12.48 0.78
Improvement
-3.59
-4.67
-4.87
Table 3,2 Fgt (1)
consider three different settings: Peor = 5%, 10,, 20%. It can be seen from Table 3 that hybrid rehearsal consistently outperforms concurrent rehearsal, and more importantly, the performance improvement becomes more significant as tasks are more dissimilar. These results further justify the correctness and usefulness of our theoretical results. Note that the performance of hybrid rehearsal has not been opti- mized in terms of the rehearsal order and selection of similar tasks, which may further improve the effectiveness se- quential rehearsal. This encouraging result highlights the great potential of exploiting sequential rehearsal in improv- ing the performance of rehearsal-basee CL..
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential socictal consequences of our work, none which we feel must be specifically highlighted here.
References
Banayecanzade, M., Soltanolkotabi. M., and Rostami, M. Theoretical insights into overparameterized models in multi-task and based continual learning. arXiv preprint arXiv:2408. 16939, 2024.
7. Conclusion
In this work, we took a closer look at the rehearsal strategy in rehearsal- CL and questioned the effectiveness of the widely used training technique, i.e., concurrent rehearsal.
Bennani, M. A. and Sugiyama, M. Generalisation guar-

---

Unlocking the Power of Rehearsal in Continual Learning: A Theoretical Perspective
antees for continual learning with orthogonal gradient descent. In 4th Lifelong Machine Learning Workshop at ICML, 2020.
Gunasekar, S., Lee, J., Soudry, D., and Srebro, N. Character- izing implicit bias in terms of optimization geometry. In International Conference Machine Learning[ICML), 2018.
Cao, X., Liu, W., and Vempala, S. S. Provable lifelong learning of representations. In International Conference on Artificial Intelligence and Atatistics(AISAATS)) 2022.
Guo, Y., Liu, B., and Zhao, D. Online continual learning through mutual information maximization. In Interna- tional conference on machine learning(ICML), 2022.
Chaudhry, A., Ranzato, M., Rohrbach, M., and Elhoseiny, M. Efficient lifelong learning with a-gem. In Interna- tional Conference on Learning Representations((LLRR) 2018.
Ju, P., Liang, Y., and Shroff, N. B. Theoretical character- ization of the generalization performance of overfitted meta-learning. In International Conference on Learning Representations//ILR)) 2023.
Chrysakis, A. and Moens, M.-F. Online continual learning from imbalanced data. In International Conference on Machine Leurning(ICML., pp. 1952-1961. PMLR, 2020.
Kirkpatrick, J., Pascanu, R., Rabinowitz, N., Veness, J., Des- jardins, G., Rusu, A. A., Milan, K., Quan, J., Ramalho, T., A., et al. Overcoming catastrophic forgetting in neural networks. Proceedings of the national academy of sciences, 1 114(13):3521-
Crabska-Barwintee
Ding, M., Ji, K., Wang, D., and Xu, J. Understanding forgetting in continual learning with linear regression. In International Conference on Machine Lear))ng(ICML), pp. 10978-11001, PMLR, 2024.
2017.
Krizhevsky, A., Hinton, G., al. Learning multiple layers of features from tiny images. Technical report, University of Toronto, Toronto, ON, Canada, 2009.
Doan, T., Bennani, M. A., Mazoure, B., Rabusseau, G., and Alquier, P. A theoretical analysis of catastrophic forget- ting through the ntk overlap matrix. In International Con- ference on Artificial Intelligence and ASUSiSSi 2021.
Le, Y. and Yang, X. Tiny imagenet visual recognition chal- lenge. CS 231N, 7(7):3, 2015.
LeCun, Y., Boser, B., Denker, J., Henderson, D., Howard, R., Hubbard, W., and Jackel, L. Handwritten digit recog- nition with back-propagation network. Advances in Neural Information Processing Systems(Neurips)), 1989.
Dokania, P., Torr, P., and Ranzato, M. Continual learning with tiny episodic memories. In Workshop on Multi-Task and Lifelong Reinforcement Learning, 2019.
Evron, I., Moroshko, F., Ward, R., Srebro, N., and Soudry, D. How catastrophic can catastrophic forgetting be in linear regression? In Conference on Learning The- ory(CoLT), 2022.
Li, H., Lin, S., Duan, L.,, Liang, Y., and Shroff, N. B. The- ory on mixture-of-experts in continual learning, arXiv preprint arXiv:2406. 16437, 2024.
Li, Y., Li, M., Asif, M. S., and Oymak, S. Provable and efficient continual representation learning. arXiv preprint arXiv:2203. 02026, 2022.
Evron, I., Moroshko, E.. Buzaglo, G., Khriesh, M., Marjich, B., Srebro, N., and Soudry, D. Continual learning in linear classification on separable data. International Conference on Machine Learning(CCML), 2023.
Lin, S., Yang, L., Fan, D., and Zhang, J. Beyond not- forgetting: Continual learning with backward knowledge transfer. Advances in Neural Information Processing Systems(Neurips), 35:16165-1611 2022a.
Garg, S., Farajtabar, M., Pouransari, H., Vemulapalli, R., Mehta, S., Tuzel, O., Shankar, V., and Faghri, F. Tic- clip: Continual training of clip models. In International Conference on Learning Representations((CLBB)) 2024.
Lin, S., Yang, L., Fan, D., and Zhang. J. Trgp: Trust region gradient projection for continual learning. International Conference on Learning Representations//CLRR) 2022b.
Goldfarb, D. and Hand, P. Analysis of catastrophic forget- ting for random orthogonal transformation tasks in the overparameterizee regime. In International Conference on Artificial Intelligence and Statistics(AISTATSSS 2023.
Lin, S., Ju, P., Liang, Y., and Shroff, N. Theory on forget- ting and generalization of continual learning. In Inter- national Conference on Machine Learning(ICMLL) pp. 2 21078-21100. PMLR, 2023.
Goldfarb, D., Evron, I., Weinberger, N., Soudry, D., and HAnd, P. The joint effect of task similarity and overpa- rameterization on catastrophic forgetting- an analytical model. In The Twelfth International Conference on Learn- ing Representations((CLAn 2024.
Lopez-Paz, D. and Ranzato, M. Gradient episodic memory for continual learning. Advances in Neural Information Processing Systems(Neurips), 30, 2017.
10

---

Unlocking the Power of Rehearsal in Continual Learning: A Theoretical Perspective
Magistri, S., Trinci, T., Soutif, A., de Weijer, J., and Bagdanov, A. D. Elastic feature consolidation for cold start exemplar-free incremental learning. In International Conference on Learning Representations//CLR)) 2024.
Zhang, C., Bengio, S., Hardt, M., Recht, B., and Vinyals, O. Understanding deep learning requires rethinking gen- eralization. In International Conference Learning Representations(/CLB)) 2022.
Parisi, G. I., Kemker, R., Part, J. L., Kanan, C., and Wermter, S. Continual lifelong learning with neural networks: A review. Neural networks, 11::54-71, 2019.
Zhao, X., Wang, H., Huang, W., and Lin, W. A statisti- cal theory of regularization-basse continual learning. In International Conference Machine Learning(ICML), 2024.
Rebuffi, S.-A., Kolesnikov, A., Sperl, G., and Lampert, C. H. icarl: Incremental classifier and representation learning. In Proceedings of the IEEE conference on Computer Vision and Putlern Recognition, pp. 2001-2010, 2017.
Rolnick, D., Ahuja, A., Schwarz, J., Lillicrap, T., and Wayne, G. Experience replay for continual learn- ing. Advances in Neural Information Processing Sys- Jems(Neurris), 32, 2019.
Rusu, A., Rabinowitz, N. C., Desjardins, G., Soyer, H., Kirkpatrick, J., Kavukcuoglu, K., Pascanu, R., and Had- sell, R. Progressive neural networks. arXiv preprint arXiv: New::6666.40 04671, 2016.
Rypesć, G., Cygert, S., Khan, V., Trzcinski, T., Zieliński, B. M., and Twardowski, B. Divide and not forget: Ensem- ble of selectively trained experts in continual learning. In The Twelfth International Conference on Learning Representations//CLLB)) 2024.
Saha, G., Garg, I., and Roy, K. Gradient projection memory for continual learning. In International Conference on Learning Representationn(((LLR)) 2021.
Shin, H., Lee, K., Kim, J., and Kim, J. Continual learn- ing with deep generative replay. Advances Neural Information Processing Systems(Neuripae 30, 2017.
Sun, S., Calandriello, D.,
Hu, H., Li, A., and Titsias, M. coarmatiionthhoreeee online memory selection for con- tinual learning. In International Conference on Learning Representations//CLRR) 2022.
Van de Ven, G. M., Tuytelaars, T., and Tolias, A. S. Three types of incremental learning. Nature Machine Intelli- gence, 1152):1185-1197, 2022.
Yin, D., Farajtabar, M., Li, A., Levine, N., and Mott, A. Optimization and generalization of eggularization-basee continual learning: a loss approximation viewpoint. arXiv preprint arXiv:2006. 10974, 2020.
Yu, T. Kumar, S., Gupta, A., Levine, S., Hausman, K., and Finn, C. Gradient surgery for multi-task learn- ing. Advances in Neural Information Processing Sys- temst Neurips,,,,,) 2020.

---

Unlocking the Power of Rehearsal in Continual Learning: A Theoretical Perspective
Supplementary Materials
A. DNN Experiments Details
A.1. Hardware Details
We outline the hardware configuration used conduct the experiments on DNN:
Operating system: Red Hat Enterprise Linux Server 7.9 (Maipo)
Type of CPU: 2.4 GHz 14-Core Intel Xeon E5-2680 v4 (Broadwell)
Type of GPU: NVIDIA P100 "Pascal" GPU with 16GB memory
A.2. Implementation Details
Dataset. We evaluate hybrid rehearsal variations of standard image classification datasets: MNLiS- Split- CIFAR-10, Split-CIFAR- 100, and Seeii-Tinnlmagnneeeee (Van de Ven et al., 2022; Guo et al., 2022; Sun et al., 2022).
MNIST (LeCun et al., 1989) contains 60, 000 28 28 grayscale train images and 10, 000 test images of 10 unique classes. For the experiments reported Table 5, we randomly split 10 classes into 5 tasks, each containing overlaaaag classes.
CIFAR-10 (Krizhevsky et al., 2009) contains 50, 000 32 x 32 color train images and 10, 000 test images of 10 unique classes. For the experiments reported in Table 1, we randomly split 10 classes into 5 tasks, each containing 2 non-overlapping classes.
CIFAR-100 (Krizhevsky et al., 2009) contains 50, 000 32 x 32 color train images and 10, 000 test images of 100 unique classes. For the experiments reported in Table 1, we randomly split 25 classes into 5 tasks, each containing 5 non-overlapping classes. For the experiments reported in Table 2, we randomly split 100 classes into 20 tasks, each containing non-overlapping classes. For the experiments reported Table 6, we randomly split 100 classes into 10 tasks, each containing 10 non-overlapping classes.
Tinylmagene2200 (Le Yang. 2015) contains 100, 000 64 x 64 color train images and 20, 000 test images of 200 unique classes. For the experiments reported in Table 1 and Table randomly split 50 classes into 5 tasks, each containing 10 non-overlapping classes. For the experiments reported in Table 2, we randomly split 200 classes into 20 tasks, each containing 10 non-overlapping classes.
DNN Architecture and Training Details. For training on Split-MNIST, we employ a three-layer MLP with two fully connected hidden layers of 400 ReLU units following (Van de Ven al., 2022). For training on Split-CIFAR-I0 10. Split- CIFAR-100, and 1plit-Tnnymmagene2200,,, we employ non-pretrained ResNet- Ven et al., 2022), we adopt a multi-headed output layer such that each task is assigned its own output layer, consistent with the typical Task Incremental CL setup. During supervised training, we explicitly provide the task identifier (ranging from 1 to 5 for Split-CIFAR- 10) alongside the image-label pairs as additional input to the model. For simplicity, we use reservoir sampling strategy to construct the memory buffer. Our buffer size is 200, 300, 30, 30 per class for Split-MNIST, Split-CIFAR-00, Split- Dolit-CIFAR-IA -000 and Split-Tiny Imnggeneee0200, correspondingly. For experiments not involving image corruption, we didn't 't apply any data augmentation before training.
DNN backbone. Following (Van de
For all experiments on concurrent rehearsal and sequential rehearsal, use the SGD optimizer with StepLR learning rate scheduler, which decays the learning rate by a fixed factor predefined intervals. The detailed parameters for each dataset are listed in Table 4.
Similarity Threshold. We report the employed similarity threshold parameter 7 corresponding to different setting in Table 1. For Popli-CIFARR-00 100, and Corrupted Split- Split-CIFAR- CIFAR- 1000, r = -0.1. For Split-CIFAR-ID 10, Corrupted Split- Split-CIFAR- 100 Split-Tinylnn 20liiiTinnlmmgeee2200,,,, and Corrupted Titt-Tiinmmmm220000. 0.
12

---

Unlocking the Power of Rehearsal in Continual Learning: A Theoretical Perspective
Table Training parameters for all four datasets.
Method
Parameter
Split-MNIST Split-CIFRR110
Split-CIFAR-100
Split-Tntllmagene2200
Epoch
30
40
Minibatch Size
256
128
128
128
Momentum
0.9
0.9
0.9
0.9
Concurrent rehearsal
Weight Decay
le
le le-4
1e-4
Initial LR
0.05
0.05
0.05
0.05
LR Decay Factor
0.1
0.1
0.1
0.1
IRR Step
10
20
20
25
Epoch
15
30
30
40
Minibatch Size
128
64
64
64
Momentum
0.9
0.9
0.9
0.9
Sequential rehearsal
Weight Decay
1e
1e
1e
2e -3
Initial LR
0.0007
0.001
0.001
0,002
LR Decay Factor
0.8
0.5
0.5
0.5
LR Step
12
16
A.3. Task Corruption
For experiments described Section 6.2, we control the similarity level of the dataset by applying data corruption to a selected task. We provide a list of sample images under different image corruption schemes in Figure
In Table 1, for Corrupted Split-CIFAR-10, apply Glass Corruption all Ti training data. For Corrupted Split- CIFAR-100, apply Color-swapping, Gaussian Blur, and Rotating Corruption all To training data. For Corrupted Split-Tinylmagenne2000, apply Color-swapping, Gaussian Blur, and Rotating Corruption all Ti training data.
In Table 5, for Corrupted Split-MNISI, we apply Rotation on all To training data.
In Table 6, for the scenario "Original Dataset", we don't apply any image corruption. For the scenario "I Corruption", we apply Glass corruption on Ti. For the scenario "2 Corruption", we apply Glass corruption on Ti, and rotational color swapping on T2. For the scenario "3 Corruption", we apply Glass corruption on Tı, rotational color swapping on T3, and elastic pixelation Ts-
A.4. Additional Results
We report the performance of hybrid rehearsal and concurrent rehearsal on Split-MNIST and its corrupted variation in Table 5.
To further demonstrate the effect of task similarity on hybrid rehearsal, we seek control the similarity by using the number of corrupted tasks (i.e., task with corrupted images) in the task sequence on Split- Aplit-IIFAR-100 In particular, we consider three different scenarios, '1 Corruption' with 1 corrupted task, Corruption with 2 corrupted tasks, and '3 Corruption' with corrupted tasks. Intuitively, the tasks are more dissimilar when more tasks are corrupted. It can be seen from Table that hybrid rehearsal consistently outperforms concurrent rehearsal, and more importantly, the performance improvement becomes more significant tasks are more dissimilar.
Table 5. Ace and Fgt of different rehearsal methods (concurrent rehearsal vs. hybrid rehearsal) on Split-MNIST and its corrupted variations. All results are averaged over 5 independent runs.
Metric
Acc (t)
Fgt (4)
Acc (t)
Fgt (4)
Dataset
Split MNIST
Corrupted Split
Concurrent rehearsal
95.24 0.25
5.33
94.29 0.15
6.48 4.200
Hybrid rehearsal
95.39 0.16
1.65 + 1.12
94.81 0.008
2.57 + 0.73
Improvement
+0.15
3.68
+ +0.52
-3.91
13

---

Unlocking the Power of Rehearsal in Continual Learning: A Theoretical Perspective
Table Ace and Fgt of different rehearsal methods Split-CIFAR-101 with varying numbers of corrupted tasks. We construct sequence of 10 tasks for training. "Corruption Number = s" indicates that data corruption was applied to out of 10 tasks, making it more dissimilar than others. All results are averaged over independent runs.
Corruption Number
Concurrent rehearsal
68.27 0.33
6.22
60.67
0.23
58.93 0.11
Hybrid rehearsal
68.79 a 0.43
64.81 0.16
61.30
59.72
0.15
Improvement
+0.52
+0.57
+0.63
+0.79
Table 4.1 Acc (t)
Corruption Number
0
2
3
Concureent rehearsal
6.11
7.76 = 0.09
9.28 + 0.16
8.57 + 0.08
Hybrid rehearsal
6.10 + 0.22
7.23 0.10
8.75 = 0.09
8.35 = 0.10
Improvement
0..14
-0.53
-0.53
-0.22
Table 4.2 Fgt (1)
B. Supporting Lemmas
Define Px -X and X X(XTX)-I. We first provide some useful lemmas for the derivation of forgetting and generalization error. In the following lemma, we provide the expression of the SGD convergence point when training single task.
Lemma B.1. Suppose X TR and Y E IR"", where Y X " + z. Consider the optimization problem:
W. arg min w w,l12
s.t. X w Y.
The solution of the above problem can be written as:
w. -w 1Xi,+X1(X Xi(YY X "m),,
or equivalently.
w, - Px)x, + +xw" + X12.
Proof. The detailed proof refers to Lemma B.1 in Lin et al. (2023).
Lemma B.2. Suppose each element of the random matrix X E [Rpx follows i..d. standard distribution and RP, then we have:
E
Px P
m ||0|2
Proof. The detailed proof refers to Proposition in Ju al. (2023).
Lemma B.3. Suppose each element of the random matrix X E Æexm follows i...d. standard distribution. Also, the random
vector E I follows (0, o² Im)) independently. Then, we have;
m
E
x
p m
Proof. The proof is completed by applying the "trace trick" as follows.
10
x
2
X x) z
tr
(xT x) -1
zz
E
[x x) -1] E xz ==
14

---

Unlocking the Power of Rehearsal in Continual Learning: A Theoretical Perspective
E [ x)
*]]
ma²
p m
where (z) follows from the independence between and 2, (i) follows from the fact that E [xx = I' and (iti) follows from the fact that (XTx) x)-
x) follows the inverse-Wishart distribution with identity scale matrix In and p
degrees-of-freedde
Lemma B.4. Suppose X E IRpX and v1 E IRP, then we have:
(I Px v1 X x2v2) = 0,
((I - P (xx)2,, = 0.
Proof. The proof follows from the definitions of Px and Xt straightforward.
Now, we provide useful lemmas in proving Lemma C.I for the concurrent rehearsal method.
Lemma B.5. Suppose P RPxP is a projection matrix and each element of the random vector v E R. follows i.i.d. standard Gaussian distribution, then Pe and (I - P)u are independent. Moreover, Suppose each element of the random matrix V Roxm follows ii.d standard Gaussian distribution, then PV and (I - PVV are independent
Proof. The proof for vector case is completed in two steps. First, we prove that Pv and (I - P)u are jointly Gaussian. wi
Pv
Denote z - P)e as the concatenation of the two vectors and wo = as an arbitrary vector, where wh; U2 E RR.
W2
Since the linear combination w z (w, P + w (I P))v remains Gaussian distribution for any w, we conclude that Po and (I - P) are jointly Gaussian. Next, we prove that they are uncorrelated as follows:
Cov(Pv, (I P)e) = E [Po((I p)b)
PE(ev T) P)
P(I -P) P)
0,
where (i) follows from the fact that v has i.i.d. standard Gaussian elements. By combining these two facts, we conclude that Po and (I P)v are independent. For the matrix case, we can equivalently consider the vector ó E Ram which is formed by concatenating all the columns of V and the projection matrix = diag([,, P...,Pp. Pl) E TRPXXm
Lemma B.6. Suppose each element of the random matrix X Rxx follows i.idd standard Gaussian distribution and R?, then we have:
E
X
x
|||||2 I.
Proof. To clarify, we denote X [11 D.. where a; is the jth column of X. We also denote [l)s as the element of 4th row and tth column matrix. Due to the independence of elements in X, follows that:
fo if J.
E uv x x(1,, cov(v" x, v T xz,z)=
||/l|
if if
Lemma B.7. Suppose each element of the random matrix X E Rpxm follows i...d. standard Gaussian distribution and the projection matrix P. E IRpXP satisfying rank P) = d, then have:
tr (X ((--)) p m
15

---

Unlocking the Power of Rehearsal in Continual Learning: A Theoretical Perspective
Proof. We first note that (I T-P) P) is projection matrix with (p many eigenvalues and many eigenvalues 0. With loss of generalization,
write (I P) U EU where Σ diag((1, ... 1,0, -... 0J) is diagonal matrix, whose first
(p- d) diagonal elements are while others are O, and U is an orthogonal matrix. We denote X R( as the first
(p- d) rows of X. Then, have:
Cr E X (I (I- p)X)
E
X U EUX) "]
1 tr
E
(x x '
(x X
tr
E
p d m
where (i) follows from the rotational symmetry of standard Gaussian distribution, (ii) follows from the fact that follows the inverse- inverse-Wishart distribution with identity scale matrix Im and (p - d) degrees-of-freedon
Lemma B.8. Suppose each element of the random matrices X1 E R X² I2px follows i.i.d. standard Gaussian distribution and u E IRP. Denote V X1, X2), then we have:
vt
X 0
mi p
(1+
112
||
p
m2 m2
Proof. First of all, we partition the matrix V V into four blocks as follows:
X
X X1 x
X X
X2
X1
X2
Then, we partition the matrix (VT V)-1 following the same partitioning scheme as T V:
(V
A1,1
A1,2
A2,1
A2,2
where 11,1 E R Xm11 More specifically, we have
A1. = (X X -1 (x, x X2 X X2 XX
X1) XX XxX
= + Px, X2 (Xg (I - Px,) X. Px.
Therefore, we have
E
vi
X 0
1
1
E
Px
+ Px, X2 (X. -I-
x Px,] 0)
m
1 2 +
E
v
Px, X2 (X Xx. Px
where (i) follows from Lemma B.2. Now, consider
E
Px, X2 (X, (I- Px,) X2 Px 0
x Px vw T Px, X² (X, (I Px )x²) xx²) -1
E
tr Ex, [X_ Px, vo Px, Xz] Exx, ( (x,] (I Px, Xx,) Xx,) "[)
Ex,
(8)
tr [| w112 I.E,, (x, (I- - Px, )x,) "1)]
Exi
16

---

Unlocking the Power of Rehearsal in Continual Learning: A Theoretical Perspective
Ex,
Px, 211²
tr
[xx
(X2 (I 2x)) "[)]
(188)
Ex,
||x v112
m2
p
mi
12
(xx)
172
m1
|
p m
m2
P
where (1) follows from Lemma B.5, (ii) follows from Lemma B.6, (ii) follows from the fact that Lemma B.7 actually holds for any X₂ and (iv) follows from Lemma B.2. By combining Equations (7) and (8), we complete the proof.
Lemma B.9. Suppose each element of random matrices X1 E RRXMI, X2 E RRxxma X3 E Rpxms follows iid. standard
Gaussian distribution and v E RR. Denote V = 11,, X2, Xs), then we have:
1
X1 O 0 (V
x
1
m1 m2
||0||
p(p
m2
mg
Proof. First of all, we observe that:
0
X
X
0 T
2v
X1 0
V)
2
vt
X
Vi
0
V1
Vi
X₂ 0
v
0
0
0
By taking expectation over both sides of the equation, we have:
2E
X
X
v
0
X
X
0
E
V
X 2
v
E
Vt
2
E
Vi
X₂
v
m1 + 7722
+
m3
|0|
m1
[
M2 + m3
||0112
772
m3
p
p
112
m3
122
1+
171 + m3
||D||
p
p 1711
172
m3
2m 1712
|/00
p(p - m1
m2
mg
where (i) follows from Lemma B.8. By dividing both sides by 2, we complete the proof.
Corollary B.10. Suppose each element of random matrices X1 E Roxmi, X2 Rpxma X3 E Tpxxms follows i.d.d.
standard Gaussian distribution and U1 U2 E R. Denote V [X,, X2, X3). then we have:
(10: 1/2l
110 1
|221
m2
E
X1
O
0 (V V)
VV-
X,J V2
2p(p m1
m3
1)
Proof. To simplify the notation, we denote V12 we first have:
X1 0 0 and
V2 = 0 X₂ 0
Then according to Lemma B.9,
E (0) (v) - 22)l
m m2
||00 -02
p(p
m2 mg 1)
On the other hand, we have:
(w) -
-2) 22 VV (o) - 0z)
17

---

Unlocking the Power of Rehearsal in Continual Learning: A Theoretical Perspective
E
81
V 2 fi
+E 22 (1 VV- 'V'' d/
2E vi V1 V22 v2)
m2 |0 1|
M1 ||22|
1) 2 [o] Vi(V
V 02]
plp mi m12 mg -13-11 -1) 1) p(p m. m2 mg
where (i) follows from Lemma B.9. By combining the above two equations, we complete the proof.
Next, we provide our supporting lemmas that help to prove the advantage of sequential rehearsal as follows.
Lemma B.11. Suppose n, P, i, M are positive integers where 2 2 and p > n n M. For any non-negative integer < t. 1-1 1, we have:
(1 (1-1-1111)) 1)p
M
1-111
M
p
p
Proof. We first note the fact that
(1- (1 1 1)p)
M
h-1-1
| (1-
(t - 1 1)M1
1 M
(1 - 1 - 1)p
P
Therefore, we have
M
1-1-1
M
(1
M
1 (1-(E (t 1)p
>
1
p
Lemma B.12. Suppose nt L, M are positive integers where 2 and p > max(n + M, M.M. For any non-negative
integerl < <t-1, 1, we have:
M
1-1-1
n M
(n +
M)M
1 (1- (t- 1 1)p
1 1 p
p
p2
Proof. If - 1 = 1 ort - - 1 2, the proof is trivial. If - 1 - 2 3, according the binomial theorem, have:
(1-1-1-11p) 1)p
11- (--
M
1-1-1
M
t-i-1
t 1-1
k 1 (
M
(1 (1-1)-
1 pl
Σ
(t - 1)p
p
where
1-1-1
----11 (
M
)
t (1-1-1)
M
1---1
t-1-- 1) (-
M
+ Σ
(10)
(t - - 1)p
2
(t (t-l- - 1)p
k
(t (t-1- 1)p
k=3
To simplify the notation, we denote m
M I-1
We first discuss if 1 1 is even. Then, we have:
1-1-11
M
k
(t
1)p
1+1//
3 )
(t--1-)
1)
(-m
2k-3
t- 1 1)
(- (-m
2k-27
+
p
2k 2
1)/22
Σ
(t-1-) 1)!
m
2k-3
(t-1 1)!
m
2k-2
(2k - 3)((( - - 2k: 2)
p
(2k 2)!(1 - 1- 2k +1)!
p
(1-++1//2
Σ
(t-1-10 1)!
m
2
1
m
(2k- 3)1(t - - 2k 1)!
p
t
1 2k +
2k 2
p
3
18

---

Unlocking the Power of Rehearsal in Continual Learning: A Theoretical Perspective
(I1)
where (i) follows from the fact that p > TM. We then discuss if ( - - -
is odd, we have:
t 1
(
M
&
k
(1 16-1 1)p
(1-1//2
(t-1-1) 1-1 1)
(-m)
m
2k-3
(1-1-1 1)
m P
2h- 2
H-1-1
+
2k 3 p
2h 2
P
(1 0/2
(t (t-18 1 - 1)!
m
2k-3
(t - 1 - 1)!
m
2
+
(2k- 3)((1 - 1 2k + 2)!
p
(2k 2)!(1 - 1 - 2k + 13
p
(e- 1/2
(t-l-10 1)1
m
2k-3
1
1 m
(2k 3)((t - 2k + 1)!
p
t- 1 2k +
2k - 2
p.
(4)
0
(12)
where (i) follows from the fact that / - 1 - 1 is odd and (ti) follows from the fact that > TM. By combing Equations (9) to (12), we conclude:
M
t-|-1
7
1
t 1
1)p
p
M
t - - 1
M
1 72
+
p
2
1t-1 1- 1)2p²
p
n + M
nM +
(t-I- (1(1-1))
2
11-1-1)
M²
(t
( 1-111 1
nM²
p
p2
2
(1 - 1 - 1)2p3
n + M
(n M)M
+
p
p2
which completes the proof.
Lemma B.13. Suppose n, p. t, M,,T T are positive integers where t S T and p > n + M, then we have:
(1-") M
n
M
(n + MMM
n +
M
T + M)M
P +
1
+
p2
p
p²
Proof. According to the binomial theorem, we have:
1 n M.,
(n + 2 MMMM 1
11 n
M
1
Σ
1-1
1
n
+ M
&. ((n +
MYM (M++MM
1-
(13)
P
p²
P
k
p
p²
a
We further notice that for k= = 0, 0,I,,., 2:
t
n
+
M
k
(n + M)M
1-h
( )
n n ++M
k+1
(n + M)M
1-k-1
1
k
p
D2
k k+1
P
D2
t!
n + M
k
(n + M)M
h-k1
(n + MMM
(1- n M
1
k - 1)! kl(t-
p
D2
(t - -k)pp²
k + 1
p
t!
n + M
(n + M)M
(-k-1
(n + M)M
1
n + M
1
kl(t- - k - 1)!
p
p2
pa
T
p
(
0,
(14)
19

---

Unlocking the Power of Rehearsal in Continual Learning: A Theoretical Perspective
where (i) follows from the fact that p > (n + (T + 1). We note that Equation (14) shows that the term og achieves the maximum at k- t 1. Therefore, we can upper bound Equation (13) by
1 n + M
(n + MMM
n n M
(111)
t
(1
(1-
-+
n
t-1
(n + M)M
D2
1 1-
P
12
n M
T M)M
p²
which completes the proof.
Here, we present tighter version of Lemma B.13, which helps to prove Theorem 5.5 in Section 5.2. Lemma B.14. Suppose n. t, M, T are fixed positive integers where t S T and p > n + M, then we have:
(1-1) n MM M
P + (n + M)M
(1- n n+ A (1-"PA²² + t(n + M)M ((++M)M I + M)
p²
p
p2
2p
Proof. According to the binomial theorem, we have:
n M (n+ + M)M
p2
n + M
(111)
(1- n + M 1-1
+n+ + M)M
1
n + M)
* ((m+ M)M
t-k
P
D2
P
y2
k=0
n + MY
T(n + +MM
+ M
(n
M
M)M
t-k
(15)
p
pd
p
p²
By the same argument as Equation (14), we know that the term 0g achieves the maximum at = - 2. Therefore, we can upper bound Equation (15) by
n2 + M (n + M)M
P
D
n
+ M
+ t(n + M)M
+ (1-
1 1-2) (1
1
(1-
n + M ++
1-2 (
((n ((n+ M)M 2
p2
p
p2
M
t(n M)M
T M)
p
which completes the proof.
Lemma B.15. Suppose n, p, t, M,, T are positive integers where M 2 2, t S T
and p > max(n+ + M, Tin+M)M
n2 M
M-1
For any non-negative integer I t 1, we have:
n n M 1
(n + MOMM
(1- (t-1 (1-1t-1-1)) (1-((-111)) 1)p
M
1-1-1
1
(
n M
1
1
P
Tp)
p
(1- n+M) P
Proof. By dividing
on both sides, it is equivalent to prove
(1+
(t (1- -+
(n MYM M/) Dd p(n +
M
6-111
<1 1
1)p
Tp
According to AM-GM inequality, we have:
(n (n+ M)M [ 1+ Dd
p(n p"-p(n + )
(1-7--- (1-111111)) 1)p
M
61-1
1
+
n p-ppa+MM
(n- M)M
+ (t (t-1-1) 1)
1
1ー1
t-1
<
t
20

---

Unlocking the Power of Rehearsal in Continual Learning: A Theoretical Perspective
M)+ p Md)+
M t-1
+
(16)
t
When p
MMM M n + M, we have:
I(n + M)M M.
T(n + M)M
M
<
<
(17)
p²- p(n + M)
p
p² p(n + M)
p
p
Therefore, by combining Equations (16) and (17), we have:
+ p² p(n +
(n ( M
(1-0-11-
M
t-1
< 1
1
t-1
<1
1
<1 Tp
(1 -1-1-- 1 1)p
(t - 1)p
(t- 1)p
which completes the proof.
Lemma B.16. Suppose n. p,t, M, are positive integers where S T and p > max(n + M, 27,27 (n + 2) then we
have:
II 1=
2-2
M
t-1-1
n
M
1-1-1
n
1 1-
1
(1 - 1 - 1)p
P/
1111111p
p
T=0
[
n + M
- (1
n2 + M i-1
>
p
p
Proof. To prove this lemma, we first have:
2-2
M
1-1-1
1 n
2-2
M
i-1-1
(1 (1 p
11
(t-l- 11)1)
p
(i 1---- 111pp)
1=
1=0
M
1-1-1
M
1-1-1
(1-1) mm
1 p
1 (t (1-13 1- 1)p
(t- -1-1 1
1)p
1=
i-2
M
8-1-1
1 11-" n
(i - 1- 1)p
1=0
1-1-1
H-1-1
M
(1- (1- n
(1 (i-1 1 11)pp
M
1 n
(t- 1 - l)p
p
1=0
i-2
II
M
(1-7)
1 p
(i - 1 - 13p)
1=0
1-2
M
i-1-1
(1-m) n
t-i-1
M
1-1-1
1 11
1
(i - 1- 1)p)
(t - 1 - 1)p/
1=0
n2 + MM
+ (n
(n+ + M)M
)
M )
i
n
p
p
p
n + M
(n (n+ MMM
+ M
nM t-i
+
p
p²
P
p²
n + M
i-1
1)
(n
+
M)M
k
(1 n + M i-k-17
k
p2
k=1
(1-
[
n + M
t-i
1+
Σ
1-1
i
(MM) )
(1-
n + M
t-i-k
p
k
p²
P
k=
21

---

Unlocking the Power of Rehearsal in Continual Learning: A Theoretical Perspective
n +
M P
i-1
n
+
t-i M
-1 1
p
n n+ M
6-1 1-1
n.
n M
t-i-k
[
k
p²
k=1
(1 n >
4
i-1
i
(n
+ M)M (M+MMM p²
(1-
n + M
i-h-1
-
(18)
P
k
p
k=
73.k
where (i) follows from Lemma 1.12 together with the fact that term yi 0 and from the fact that (1-
M
1-1-1
(1-1-110)
1 M for I- 0, 1, .., t- i 1. Now. we need to prove 7/2 + Ya > O. We first focus on 722 We have:
n M+M
1-1
t i
(MM)
(1-
n2 + M tii-1
72
1
p²
P
p
n +
M
T
nM
1
P
p²
T(n + M)
nM
(19)
P
p2
We then focus on term 73- Consider:
('
8-1
(n + M)M)
&
n + M
h-
i 1
(n + MYM k+1
1 (1- n + M
i-k-2
12
k+ 1
12
P
(i- 1)!
(n MYM
M
k- 2
n M
p M
1
(n M)M
1
kl(i- - k - 22)
p2
p
k 1
k k+1
1²
(
(i 1 1)!
(n MMM
n + M
i-
[
n +
M)
M
(n + M)M
1
1
blli 2)!
p²
p
T
p
2p²
(1)
0,
(20)
where (1) follows from & E [i 1] and (ii) follows from the fact that > 2(n + M). This indicates that 73,8 achieves
(1 (1-2i) x+M
1-1
maximum at k = 1. We recall that
< 0. Therefore, we have:
n + M r-1
1) 11
( (n+ (M++MM)
(1- n + M i-2
73
p
p
1 n + M
M
1-
T2 + M)M
1
P
D²
[-i
n + M 17
T + MMM
(21)
k
D2
When k is even and less than or equal to l. - i (i.e., k = 22,4 G..,, .... and k S l - i),, we have:
t {-2)
k ) (- n n+ M
&
t (-=)) (x+1)
)
(- n + M
k+1
(t i)!
n2 + M
k
n + M
P
p
kl(t k: 1)
P
t
(I + 1)p
(t- i)!
n + M
k
'
n + M
Ml(
- i - 1: - 1)1
P
T
3p
22

---

Unlocking the Power of Rehearsal in Continual Learning: A Theoretical Perspective
(
0,
(22)
where (i) follows from p> > even, we can conclude
(n+ MYT
By combining Equations (21) and (22) and simply discussing when - is odd or
3
-2) 2)
k )
(-
n + M k >
(t- (t-1) (- n n M
T(n + +M)
>
P
P
p
which further implies:
7 + M)
Y
(23)
pd
Now, by combining Equations (18), (19) and (23), we have:
2-2
M
2-2
M
i-1-1
1
1
(t 1
1)p/
p
(1 - 1 - 1)p
p
1=0
+
M
f-1
+
M
t-i
+ 1
T(n + +M)
nM
T + M)
1
p
p
p
p²
pd
n
M
i-1
n + M
t-i
(24)
P
P
where (1) follows from the fact that p 27 (n + My²
Lemma B.17. Suppose n. P. 1, M, T are positive integers where 1 S T and p > (n MYT. For any non-negative integer
i. < t, we have:
2-2
M
1-1-1
72
M
4-1-1
m
(t 1 1 1))p)
(i - 1 1)p
P
1=0 n
M
i-1
n + M
t-
T
(n +
M)M
1
+
p
y22
Proof. To prove this lemma, We consider:
M
M
i-1-1
|
1
1 p
(1-1-
1)p)
(1 1- 1)p
1-1-1
M
8-1-1
(1-3) n
1-2
(1- (1 - 1 - 1)p
M
1-|-1
(1 (1- mm
[1 1---- 1 - 1)p
I=
i=t-i
II
i-2
(1
M
6-1-1
1 n
(i -1-1- 1- 11-1pp
p)
1=0
M
1-111
(1
M
1-1-1
n1
}
1- -
(t
- 1)p
(1 - 1)p
p
1=0
i-2
M
i-1-1
1- m
(1 - 1- 1)p
p)
1=0
1-2
M
i-1-1
(1
M
1-1-1
(1 1- n
II
1
1
(i 1- 1)p)
p
(t [ 1)p
p
0=0
1=0
71
23

---

Unlocking the Power of Rehearsal in Continual Learning: A Theoretical Perspective
n + M
(-1
n M
1- (n + M)M
1
p²
(8))
n + M i-1
n + M
b-)
( + M)M
- -1+
p²
n + M
n + M
t-i
T ( MMM
-1
+
(25)
p
P²
where (i) follows from Lemmas B.11 and B.12 and the fact that 7/1 < 0: (it) follows from Lemma B. 13.
Here, we present tighter version of Lemma B.17, which helps to prove Theorem 5.5 in Section 5.2.
Lemma B.18. Suppose n. p. t, M,T are positive integers where t T and p > (n MYT. For any non-negative integer i < I, we have:
M
1-1-1
11
M
1
(t [
1)p
p
(i 1--1 1)p
1=0
+ M
+ M
(t- (n M)M
( + M)
+
p
p
pd
Proof. The proof follows from the same argument as Lemma B.17 but we use Lemma B.14 14 instead of Lemma B.13.
C. Proof of Theorem 5.1
First of all, we present the detailed iteration formula for the proof outline of Theorem 5.1 in Section 5.1. For both rehearsal methods, we have:
[[C](w:)] gi (E[C,(w;-1)]
termng + termooise
(26)
where gt
(concurren)) (x) (1
M+M )x, 9i
(sequential)) (z) (1 M
1 Jr term term noise
(concurrent)
(n+tMo* p-n- M -1 term
(sequential)
(t-1)p
noise
(1- (1-1)p) p-n and the form of termy is given in Equations (29) and (33)
t-1
nn?
(t-1)p
for concurrent rehearsal and sequential rehearsal, respectively.
Based the above iteration formula, further derive the explicit expressions of [[[r(wx)) and (w,) - (w,)),, and they share the same structure for both rehearsal methods for any S T which is formally presented in the following lemma. Lemma C.1. Denote w, as the parameters of training result task t. Under the problem setups considered in this work. the expected value of the model error (,(w:) in both rehearsal cheers methods take the following forms.
EL,(un)) doc || 12 1
deyke [|m0 wiill + noise;(a),
=k==1
T-1
B(Ci(ur)) L.(wx:)) =c: ||00111
Σ 5,k=1
Cjjk 1100
wi 11 (noise; (a)) nooss;;(o))
For both concurrent and sequential rehearsal method, Theorem 5.1 follows directly by combining Lemma C.1 and the definitions of Fr and Gr. Therefore, suffices to prove Lemma C. to obtain the coefficients in Theorem 5.1. Before we start our proof, we first present the explicit expressions of coefficients as well as the noise term in Theorem 5.1 for both concurrent and sequential rehearsal methods in the following proposition.
Proposition C.2. Under the problem setups considered this work, the coefficients that express forgetting F, and generalization error Gt take the following forms.
di
ccmmuureen) -rrr111
c
(comcurrent)
dgg
(comcureon)
d
cconcurentt
24

---

Unlocking the Power of Rehearsal in Continual Learning: A Theoretical Perspective
(1 T Σ
Bi, + r'M nnnnn k,
Σ
pris Bralli
if j E [t - 11,k= =
M
1=0
1=0
(enneureent)
rn) T' nH
if j 1,k i
jkkt
pr Bi,.HHi.. H1,
If j < k and k # i,t
I'M I k,t
if j k and j
tconeurrent)
(coneurrent) iikh ro 1),
(coneurrent) 1jkT
ijkk
Dz
ssqueential)
c
(sequential)
60T
(sequential)
cconeureett)
0z
1-1-1
(sequential)
(1 ro)(1) B B--
A.(l - -1) -) +
Σ
A, -
Bi,
if 1t 1] and k: = i
jjkt
t=
(1 -r)or)(11 Bo,))
if j = 1, k: i
Isequential)
(sequentill) likT
(seeuentiol)
ijk
Liiki
n
(conuurenn)
(a) ror 1-1
An.o
An+Mo
M
1=0
t-2 noise, (eegeeninl)) (o) - Ar00 Bo,,)
Ano
Bo,,) "
1
where =
nta Bi.t
M (1-1-1pp
il
HI,
Bit p-n-M-1'
A.(a)
II (1 B 1-11 - roj. A
p
0
o.w.
p-a-1
To simplify notation, omit the tilde notation of the memory data to simplify notations: X1,i == X Vr, Yy, and Zt,i Tt, for E [t- - 1J. Similar to Equation (2), for the memory data, we have
Y,, J,,, w + 21,5-
(27)
where Z (O, obHx) is i..dd noise. Since there no memory data involved for task 1, by combining Lemma B.I and the fact that wn O, can easily derive the first parameter
w1 Px, i6 + x
Then, the expected value of the model error ECC(ww) can be derived as follows.
E [1 (I|l
(0)
Px, (w) w + EII[I Px.)w
+
| +
+E
(6) n2 i w1l +
1
n p
||
11
+
no
(28)
p-n-1
where (1) follows from Lemma B.4 and the fact that 2 are independent Gaussian with zero mean and (fi) follows from Lemma B.2 and Lemma B.3. For 2 2, the two training methods use memory in different ways. We present them in the following two subsections.
C.1. Proof of Concurrent Rehearsal in Lemma C.1
In this subsection, we prove Lemma C. for concurrent rehearsal method. To simplify, we apply the following notations to denote the current data in this subsection: X, Xt,, Y, == Y,,, and z, == z,,.. Then, for each task t, the SGD convergent point w, of training loss Ct D, M,) is equivalent to the optimization problem:
wc min | w.- 112 s.l. XT, w Yes j [0].
25

---

Unlocking the Power of Rehearsal in Continual Learning: A Theoretical Perspective
Define Ve (Xt,1 1,2 my xt, and Eo [2,11 P2,2, Ze,el T.
According Lemma B.I, have
Y11
Y2
we = 11-1 V
V. w
Yi.e
X T
1.1 [
X X w
= (I - w,, V,
+ V 2/.
Consider an arbitrary s.t. i S T and fix it. The expected value of model error (w:) can be split into the following three parts.
X T
11 [w) wnj)
X 2 wn;)
W wil 1| = E (I (w)) V,
+ V 44
X (w) (w) w))
X T (wi w0/)
2
x x (wn mn,)
[I Pv, (wt 21 + E
V
+ E
V, E4
x Jo (w) - w))
XJ (wr w )
(84) (1
T4 +
M2
X [w w()
(n + M))
E 11
20
E
V
(29)
p- n2
X t.t (w) w
term (ennammnn)
where (1) follows from Lemma B.4 and the fact that 7 are independent Gaussian with zero mean and (ii) follows from
Lemma B.2 and Lemma B.3. Denote Vr, as V, with all zero elements except X i.e., Vn,; [0.... Xtj,, ..., 0] To further calculate term2
(concurren) in Equation (29), we have:
X
[w)
w.)
X (w)
w
E
V
X T
(w= w
V V.J((u (wn - w0;)
V (VV.J((0))) (w; - w.)i|²²
+ Σ
Σ
(wi- w.;) T (v. Vv) -i.V.VVV (w) ww;)
j=1 k=1,
Med
1 - - M, -1
+ + M, -Mys
1|w3 21; + nt 1+
p n4e - Mr -1 11:0 - -20
Mr
Σ
p(p nu Mr 1) (12033 w 1 200 w.,1 112 1/20 wo 112))
Me,k
nt Mrj
(1|003 -
-w:l- wil12- ||00 w., 11?
|m -20²'1 20,(1?)
(30)
p(p
1=1
26

---

Unlocking the Power of Rehearsal in Continual Learning: A Theoretical Perspective
where (i) follows from Lemma B.8 and Corollary B.10. Recall that n4 n1 Mes [ and the fact that M, M. By combining Equations (29) and (30); we have:
n + M
l,, wol1 -
E [1-1 wi| ||
p
1-1 1
M
1+ p
n + M
1-1
M
||03 - wii ||
(t
- 1)p
M- -1 1
/=1
n
1
M
1|e0 wll1
p- M -1 1
p
p
t-2
1-1
(
p(p n M 11 (11103 -wogl 1001=~1100 wo?ll - 1|a0f wo 11²)
nM 1-1
P(p M- - 1) (1100 will? - -11003 - -w:'l 1/00; uo? mn?11²)
(n + M)
+
n M -1
By iterating the above equation and combining it with Equation (28), we have:
E Ww=
w1
n + M
t-1
E W1-
wo'l
P
1 n + M
11-111
M
n + M
M
1
6-1-1
|/0/ -will"
P
(t-1- 1)p
p- p- n M 1
n n+ M
M
|| w 1|
1 +
p-n - M
n M
11-1-2 1-1-1
Σ
(1--)) )2
M 1)) (Ie03 will 2 1|,03 ww,1² - -1120 w. (12)
P
p(p
n+ M
1t-1-1
p(p n - M 1) (1100) - w1 - ||003 - un; - |, -00; 11²)
T-1-I
RM
P
n + M
(n + M)
p- n M- 1
(1 )
M 1-1
n + M
1-1
p)
|mm1 +
"E "Elw w.ll
p
p
n + M
11-1-1 M
n M i-1-1
M
1
||wj w
p
(t tt-l= 1-1110 1)p
p n - M- - 1
n + M
M
1 - -w;ll will
P
p-n MMMMMM1
M
n n M
11-1-2 1-1-1
Σ
p(p - M 11) (1w0 will - ||:03 - -w,'l - -1100% ux;" 123
(T--)) )2
k=
n M
1t-1-1
p(p - n - M - 1) (1100 w. .11 - ||:03 un; / - -0n 11²)
RM 1---
p
27

---

Unlocking the Power of Rehearsal in Continual Learning: A Theoretical Perspective
m
n +
M no²
1-2
n +
(n M) MY )
1
1
+
1
p
P
p
1
p
p 12 M -1
1=0
1 n
n
n
MM
t-1
p
n
+ M
t-1
n
2-2
n + M
M
1+ n M-
p M 1-1-1
M
p
P
p
(t - 1)p
1=0
(t-1-1j 1j + (t - - 2)
n.M
(-1-1 M )
1/w9 wo,l
p(p n M 1)
2-2
1
n + M
1t-1-1
M
1+
n M- - M
1-1-1
p
(1-1- - 1)p
p n - M -1
2=2
nM + (t- (6-11 - - M )2
1-1-1
| - 20, 1|
p(p- - n - M- - 1)
n + M
M
(I (t- 1) nM
1-1-1
|| ||0|_ will
1
P
P
p
M
p(p n - M 1)
11-1-21-1-1
112 )2
n+ M
[wj w 2
P(D n M 1)
P
n+ M
MM 1-1-1
|00 w
1| +
(concurrent)
P
p(p n M -
+ MY
1-1
|
p
n + M 1
M
+ (1- n + M
(1-"+~
t-j n ||00 - wil
(1 (1- 1)p
|
un?l 2
n M
(H-))² )
|00 wi |
p
p(p M - 1)
n + M
RM T-I-I
1|00 wi
11
+ noise
(concurrent) (o),
(31)
p
plp- n2 - M - 1)
where
noise (concurrent) (o) = -11-3) p (1-" n + M
11
t-1
na²
L-2 +
n n M 1 (n + M) p
1
p n-n n
p n M -1
1=0
By rearranging the terms in the above equation, we complete the poof for dconcurrent and concumment) dog Furthermore, the expressions of of (cooccureet) and (concurrent) can be derived directly based on de Aikk
in Lemma C.I.
ljke fconcurremt d (concurrent and the likt
definitions of forgetting. The explicit expressions of c
(eomeurrent) and
(concurren)) are derived as follows.
isk
2 (concurrent)
E l|1= -w,'1 - EE llw, will ||?
= =(1-2)
_)) p [ [1- n + M
i-17 n + M (1-
||
1|
p
P
28

---

Unlocking the Power of Rehearsal in Continual Learning: A Theoretical Perspective
)
n + M
t-1
(1
n +
M
n
t-2
n
+ M
M
+
p
P
P
(t (t-l- 1)p
1=0
n + M
M
1|207 -ww 12
p
(1
1- 1)p
1=0
n + M 1
M
+
(1
n M
n2
|unj
w
P
(t
(t-1-1 1)p
n+M) 1
M
1
n + M
n
+
p
(t-l- 1)p
P
n + M 1
M
+
M
i-j
|00
wj
p
(i-l- 1)p
p
p
will"
M
11-1-2t-111
1-1-
M )2
|/0 will
P
p(P - n1 - M - 1)
B1
n n M
(1-1-1) )2
11003 - - 11
P
p(P n M 1)
k=j+1
++M
nM
1-1-1
|00 w0-lll =
P
p(p nl M 1)
B2
M
T---I
n
1100
-w w
p(p
M - 1)
+ noise,
(concurrent)
(a)
noise
(concurrent) (a)
(32)
We will show that 31 consists of terms 63.8 |wj- will" with و5.m > 0 and j.k # L and 82 consists of terms
Wiue |wj- - will with 1j, > 0 for a sufficient large p in Appendix F.2.
C.2. Proof of Sequential Rehearsal in Lemma C.1
In this subsection, we prove Lemma C.I for sequential rehearsal method. To simplify, we apply the following notations to denote the current data in this subsection: X, == X Y, == Y,, and 20,0- When / 2 2, the sequence of SGD convergent points w)(") is equivalent the sequential optimization problems:
(-11)) 2 [ s.t. x,,w= = Yrss, j= 1,,1,..,, 1,
w
= min 1
w w
where uo!-1) wi-1 and w,- w. (t-1) Consider arbitrary i s.t. i < T and fix it. During the training process over each task in the memory dataset, the expected of model error can be split into three parts as follows.
E (6
un?
[I Px.,,
(1 (ui)
w + Pxi,s (uo - -ws) + X b
|
(
1
M
E 10
1) wi 1|
(t (t-1) 1)p ||00 ww
M
+
1-1)
M
2
(t 1)p
p
for j = 1,2, t 1, where (i) follows from Lemmas B. to B.4. Similarly, for the current dataset, we have:
E 1
(0)
w | E (|( - (w: - w + Px, (wi - -w:)l'
29

---

Unlocking the Power of Rehearsal in Continual Learning: A Theoretical Perspective
(
71 p
will + n2 E 11101111
l|w=" - -w;ll + no²
p
p 1
By combining the above two equations, we have:
M
(-1
E 1,,- - -203
1
E f1 - -w,l
(t (t-1) (t-1)p)
p
+ Σ
1-1
(1
M
t-j-1 1
M
E w w 11 (1 (1-
M
t-1 n lwm
w 1|
(t - 1)p
(t - 1)p
(t - 1)p
==1
Germauusndaal) Gecuential)
term
M
t-j-1
02 p
M.
no² p- n 1-n
1-1
(1
1
(33)
(t
1)p
(t 1)p
By applying this process recursively, we obtain the expression of the expected value of the model error (E,,( as follows.
E 11,0-
2
M
1-1-1
1
-
12
E f1ee - u0m1 11
(t-
1)p
p
(1
M
11=) (1
M
1-5-111
M
|100
wo 11
(t. k --11 -1)p/
(1 18-1-111 1)p
(1 11-1 l - 1)p0
M
(1 (1-
n
1
M
1-1-1
n
| 10,1
(t- k - 1)p
p
(t - 1- -1)p
p
M
t-1
w1ll + noise, n (sequemtial (o)
1)p/
1-2
M
1-1-1
(1
11
||wا 1|2
p
1t-18
1 1 1)p
p
1=0
M
M
1-1-2 M
1 p
(1 k
1)p
(1 --- 1 -1)p)
(1-1- 1- 1)p
1-2
M
1-1-1
( (t-1-1)) 1)p
1 p p
| w0 11
M
k-
(1 (1- p) ( (1- (1- (1 16-1-11 1)p
M
t-j-1-1
M
(t - ks 1)p)
(t - 1 - 1)p
0=
M
c-K-1
1 n 1 (j 1)p
M
J-1 n
| - w 11
(t (6-16 1- 1)p)
p
k=0
M
1-1
+
| w 112
noise
(soquential) (0)s
(34)
(t- - 1)p
where
noise(eqquaatall (sequential) (a) =
M
h-k-1
12
k - 1)p
P
1=0 0=
Σ
M
f-j-1
[-1 0²
M
no²
1
(1 (0-1) l)p)
p
(1 - 1)p
p 71 1
30

---

Unlocking the Power of Rehearsal in Continual Learning: A Theoretical Perspective
By rearranging the terms, we complete the poof for dog ('squeetial) and d/sequential) in Lemma C.I. Furthermore, the expressions of liktt d(squential)) (sequential) and the definition of forgetting. The explicit Light
c/ ( and (sequentaa) can be derived directly based dog
iikk expressions of connurrent) and (sequential)
Cigk
are derived as follows.
(sequential)
E
wi
n ut
12
E
M
6-1-1
M
1-1-1
}}
1 (t 1
|
11
p
1)p
p
(i 1 1)p
p
1=0
M
1-1-1
1
i-2
M
i-1-1
1 12
(t 1 - 1)p
(i - [ - 1)p
p
1=0
M
(-k-1
1 p (1-))
M
1-1-2
M
(t- k - 1)p
(t - 1 - 1)p
--1 1 1)p
M
i-k-1
1 p (i-1 1 11pp
mm
(1 M
i-1-2
M
||w0 wo?1 1|
(i- k- - 1pp)
(1- 1 1)p
M
(1- -) (1 (1 (1-1 1 1)p
M
(-j-1-1
M
(1 - k - -1)p
(1 1-11 1 - 1)p
M
1-k-1
1- (1p) ]) 1
M 1-1
j-1 n2
wwj - wil
(t - k - 1)p
- 111ppp
M
1- ( (1-2) p
m²
(1
M
i-j-1-
M
(1 k 11)
(1 - 1- 1)p)
(1-1-1) 1)p
M
k-k-1
(1 ( p)
12 | (1
M
4-5-1-1
M
(i-k k- 1)p
(i 11-1-111 1)p
(i 1- 1)p
M
1-
1 n
(1-
M 5-1 n
(t - 1)p
p }
(j 1)p
p
1
M
i-k-1
1 n
(1
1
M
n
||06 20 1|
(i k- -1)p
p
(j 1)p
p
k=
+
M
1-1 n 1|w7 w1,1 + noise,
(sequentiall
(a) noise
(sequentaal)
(a)
(35)
(t - 1)p
C.3. Proof of Theorem 5.1
Theorem 5.1 follows directly from Lemma C.1 and the definitions of Fr and GT.
D. Proof of Lemma 5.2 and Theorem 5.3
In this section, we will prove Lemma 5.2 and Theorem 5.3, and provide details about constants E2, M22 According to Equations (31), (32), (34) and (35), the forgetting and generalization error for T 2 is as follows. For concurrent rehearsal method, the forgetting is provided follows.
Fl ploonuument
= E || W22
wi|l²
- E |www- - -will"
=
n + M
(1- n2
|! + 12
1 1
M
|ml| will 2
p
p
p
p- M
(n + M)
12 + M
no²
+
(36)
p
(n M) -1
P
p n2
1
31

---

Unlocking the Power of Rehearsal in Continual Learning: A Theoretical Perspective
And also, provide the generalization emror follows.
2
(cconcurrent)
E U22 will²= + EE W22 w w22l²)
M
) (1-") p) /) (1wiil2 + 1|205
p
2n M
2nd
n(n + +M)
+
+
w
2
p
p(p - nt - -M -1)
p²
(n M) M)
n + M
no
+ p- (n + M) - + [
(37)
For sequential rehearsal method, the forgetting is provided as follows.
F2 Esequential
E 22222
will
E W1 will"
M
nM
p² ) (1
M
+
| 11
|
wx !l
p
p
2M
nM
no2
M
+
+
(38)
p
p²
p
n2
p- M -1
And also, we provide the generalization error as follows.
G2
reequential
E
||02
will
112 +
1222 -w,l'= will")
2
M
2
2n M
n(n + 2M)
2
(1wi + +1|w511²)
+
||20
2 p
2
p2
pd
M
n1
n
MØ²
+ 1
2
(39)
p
P
M 1
D.1. Proof of Coefficients é é in Lemma 5.2 and Forgetting in Theorem 5.3
By observing Equation (36) and Equation (38), the expressions of forgetting for both rehearsal methods share the same structure:
-w F2 = é | 1| + è2 | - will + noiscy(o).
We first compare the coefficients è1 and the noise term no)s In the below inequalities, the expressions for concurrent rehearsal are provided on the left while the expressions for sequential rehearsal are on the right.
+ M
1
n
M
nM
(1
p
P
P
pd
M
M
02:
1
A
n
M
p
(n 2)
n + M
n102
2M
nM
1102
Mの²
noiser(a)
p (n + M)
p - n
P
p2
p n
- M -
The comparison implies that ot ((concument) further caleulation, obtain the following conclusion:
(equuettaal) (concurent))
(sequential) and noise
(concurrent)
(a) noise F
(sequential)
(a). By
F (onnurrentt)
Fl (isequential)
and only if
& || will + Ezo²
||
M
aM
where E =
and E
To illustrate this conclusion better, we
provide the following two special cases.
If the noise is 0, and the task similarity is low enough (i.e., | will 2 is large enough), sequential rehearsal achieves lower forgetting. More specifically, F peconcurrcatt (scquental) if and only if [ will (p-n)(p-n-Ml M-1)
p M- ||w]|
32

---

Unlocking the Power of Rehearsal in Continual Learning: A Theoretical Perspective
If task difference I More specifically, (.soncurreut) 1
w 11 0 and the noise is large enough, sequential rehearsal achieves lower forgetting. (equential)
2 12
if and only
ndd p
1
2
0 2
w
1
M
a.M
M
P-R-1
D.2. Proof of Coefficients d1 d2 in Lemma 5.2 and Generalization error in Theorem 5.3
By observing Equation (37) and Equation (39), the expressions of generalization error for both rehearsal methods share the same structure:
G2 = di (1|w0]ll + || + d2 ||uoj unğ 2 + noiseg(a).
We first compare the coefficients d1, d and the noise term noiseg(a)) In the below inequalities, the expressions for concurrent rehearsal are provided on the left while the expressions for sequential rehearsal are on the right.
d1
(1 n M D
(1
1
n
M)
M
2
<
P
2n + M
2n.
n(n + M)
2n + M
n(n + 2M)
n
d2
+
p(p M - 1)
p²
p
p2
pd
noise:
(n + M)
+
+
M
na2
M
2
11.
no²
M
(n + M)
P
p
p
M
-
which implies that d. (soncurrent) [sequential) and de calculation, we obtain the following conclusion:
feoncurrent)
d2
Atsequentia)
noise G
(concurrent)
noiseG
(sequential)
(o). By further
22
(concurrent)
2 G (iequential)
if and only if ||0 - wzll -
+ 222 > ||0
(1
M nM
where 111 we provide the following two special cases.
and P2
P y² p-n-1
To illustrate this conclusion better,
nad (1-3)
22
52
If the noise a is O, and the task similarity is small enough (i.e., || - wi 1 is big enough), sequential rehearsal has smaller generalization error. More specifically, G2 (fconcurreat) (p-n)(p- (||= + [|==)]]))
G (equential) if and only if |wi - will -w;ll
2
If the task difference | wEl 1| = 0 and the noise a is big, sequential rehearsal has a smaller generalization error. (scuuentaa) if and only if
More specifically, G Cfconcurent) 2 G²
nM n
n
[|w || 1()
1
M
nM D
M M
P
p-n-1
E. Comparison between Concurrent and Sequential Rehearsal Methods When T 3
Recall that M2,1 = M and M3,1 Ma.2 = 2 under our equal memory allocation assumption. In this section, we assume
O. According Equations (31) and (32). we write out the performance of the concurrent rehearsal method when T as follows.
F (concurrent)
E
1/ - w|ll
E w1
will 2 +1 11ag - u0312 2- -E |122 wiil())
2
1
2(n + MM)
(n 22²
(1-10 71
||,7|11
+
2 (- n
1
n M
n2 + M
)
(1- n p
|
2
p
p2
p
p
p
33

---

Unlocking the Power of Rehearsal in Continual Learning: A Theoretical Perspective
+
1
2(n + M)
nM p(p
+
M
+
n + M
1 n1
(1
n + M
| w
|?
2
p
M- -1)
2p(p M- - 1)
P
p
p
+
1
nh
n.M
1|00 - -w3ll
+
1 1
+
n.M
|1222 uz/ 11?
(40)
2
p
p(p- n M 1)
2
P
p(p
n - M 1)
and
(soncurent)
3
1
[ W3
wii
112 + 111ss ww2l +
1103 wrll²)
3
1
+ M 2 (1-")
1
(120 1| + ||00 11 + -||00311 11²)
3
p
p
(3
3(n + M)
nM
3M2
+
3
P
p(p n M - 1)
4p(p - 11 M 1)
+ M
3n M +
n(n M)
2
|
will
P
p
p
p²
+
n
2
2(n + M)
(n + M)²
M
n
n
M
+
M
+
3nM
|
u03 |
3 P
p
pd
p
p
2p
2p(p
n M
1)
+
n
n
+ M
M
3nM
|100
wgl 11
(41)
3
P
2p
2p(p - n - M
According to Equations (34) and (35), we write out the performance of sequential rehearsal when T = 3 as follows.
Frg
pisequeentia)
E
will - E ||
[w
- wil 11 + E ||003
w 21 - IE || - =0)))²
1
1
n
1
M
(1
M)
2
(1 1
||0 2
2
P
p1
2p
2
n
p
3
11
M
p
(1
M
2p
2
-
1
n
p
1
M
p
||00š| 1|²
2
n
p
( 1
M)
p
p
-
n
2p/
M
2
2 - n
p
- 1 + 1
M
2p
2
(1
n
M
p
4p²
M
| - ww 1
M
2 n
M
2
||
w
+
1
1w5
w3l 1
(42)
2p/
p
2p/
p
And also, we have
G
conncurrent)
[E 1103 will + E
[w3 - will
+ E 200 will
1
1
n
(1
M)
M
)
(1 M
2
([|wi]) 1|
+ ||
+ ||w/ا| 122)
3
p
p
2p
1
M
2
[[ [
M)
M
M
M²
1
1
2
+
+
|m
w 1|
3
p
2p
p
p
P
p
p
4p2
1
(1
My
+
1
M
1
M
+
1
n
1
M
(1-
M
2
2p/
p
2p/
p
p
p
p
2p
p
(1-
M
M
+
|
w3 |
2p
2p
(1((1111))
1
MM
n
1 1
M m )
(1 (1- n
+1
+
M
|w
w 1|
(43)
3
2p
p
p
p
2p
34

---

Unlocking the Power of Rehearsal in Continual Learning: A Theoretical Perspective
E.1. Comparison of Forgetting When =3
By observing Equation (40) and Equation (42), the expressions of forgetting for both rehearsal methods share the same structure:
1 200 llw1 w²ll² + Le 1/w0 wIll + dcs 1 02 ||,5|1 F3 ee "12 +
1
will
By comparing Equation (40) and Equation (42). we have the following conclusions:
L.e (econeurren))
c
sequeetial))
2.0²
consuurre)
C2 (sequential) 3.C3 d(suncurren) > C3 (sequential) when >
5n+ dfcuncureen)) d (aaquentia))
2
4.04
5.0g
(cuncurment
c5
(sequential)
The proof of
these conclusions is provided as follows.
Proof. 1. 1
geconeurent)
(sequential)
We have:
q (ooquential)
n
3
1
M
M
2
1
p )) ))
"
p
p
2p
1
n
2
1
#)
M
1
M
2
-1
(1-7) mm
p
p
2p
p
2
M
2
1- n
1
1 ---)
-1
1
P
p
n P
+
M
(1-
1
p
(coneurrent)
2
(econcureen)
sequentiall
Consider:
(sequential)
n
3
M
M
71
2
1
M
2p
n
3
M
n2
2
M
1
1
n
n
M
n
M
P
P
P
P
n
TM
n
M
n M
RM
12
P
P
p2
n
NM
n M
R +
M
nM
D
P
P
n
TL + M
n1 + M
n
n&
2(n + M)
nM
+
1
1
+
P
p
12
p
122
n
n. + M
n + M
(concurrent)
3. C3
(concurrent)
(equential)
when p>
5n44M We first lower bound (concurent) follows.
C3
1 2(n + M)
nM
M
n + M
n) )
(1
(1-
n + M
conncurennt)
p(p M- - 1) +
1 (1-
P
2p(p
M -1-1)
P
p
2(n + +M)
nM
2
n + M
n
n M
+
1
1
p
2²
2p²
p
pl
p
35

---

Unlocking the Power of Rehearsal in Continual Learning: A Theoretical Perspective
n +
M
n
M
n p
n
n
M 2nM2
+
p
p
pd
On the other hand, we upper bound ((sequential)
Cg
as follows.
(sequential)
71
M
n
M
M
12
M
M
2
1
+
1
p
P
2p
P
2p
p
4p2
11
M
T
M
72
D )
M
(1- "
M
2
1
+
P
P
P
p
M
M
M
-1]
2
4p2
P
P
P
P
P
P
11
M
M
M
M
M
2n
M
2
+
P
P
P
P
P
P
P
4p
p
P
A3
M
T
M
M
M
2
1
P
P
P
P
P
P
P
M
2M
nM
M
M
P
P
P
D
P
P
M
M
M
2M
nM
1
P
P
P
P
P
P
P
D²
M
TI
+
M
+
M
TO
+
2M
nM
1
P
P
P
P
p
M
M
n
+
2n.
n
An
M
2nM²
p2
ps
where (i) follows from the face that p > S-+-4M and (ti) follows from the fact that
a+2M
+
Since p > 5n-44M
p
p²
have:
2
n
M-
2nM2
n² + 2nM
n² + 4n²M M
2nM2
2
pd
p3
which implies 2
elconeurrent)
3
eequential)
and completes the proof.
4. 4,C4
((concurent)
(sequentia)
Consider:
(comeurrent)
n +
nM
n2
M
2
(sqquential)
P
p(p
M
p
2p
p
The proof of cg
(concurrent)
5
(sequential) is the same as c
s(concurrent)
(equential
E.2. Comparison of Generalization Error When 3
By observing Equation (41) and Equation (43), the expressions of generalization error for both rehearsal methods share the same structure:
G3
-. (1w + ||,3|| + | 12 + 3
1 _dg || - will -w;l + d3 : - will +
1 du 1|w - will
3
3
By comparing Equation (41) and Equation (43). we have the following conclusions: 1. Zeoneurrent)
d Esequential).
2. jcuonuument)
relationships is provided as follows. 2 3.d
Aeequenial) when > 4n+3M, (lcomcureent > d Alequential), 4. fecomcurentt -
The proof of these > d (lequential)
1. (econcurent)
[sequential),
d (sequential)
n2 -11-)) (1 (1
M (
M
p)
2p
36

---

Unlocking the Power of Rehearsal in Continual Learning: A Theoretical Perspective
11
3
M
2 1
P
n
M
M
p
conneurent)
2. jececureent)
2
)sequental) 2
when p >
1n+3M 2
We first lower bound d2
(eoneurennt as follows.
(concureett
3(n + M)
nM
3M2
n M
3n
M
n(n + M)
3
+
+
2
+
p
p(p- M
1)
4p(p
M
1)
p
P
P
p2
3(n + +M)
nMM
3M2
n M
3n
M
n(n + M)
3
+
+
2
p
p²
4p2
P
p
p
p²
n + M
nM
2(n
+
M)
n M
3n
n
n + M)
1
P
p²
p
P
p
p
p2
2(n + M)
3n
+ nM
+ M
n
n² M
2nM2
p
p²
pd
On the other hand, we upper bound Asequential) as follows.
2
d2
jisequential)
M
2
M
M
M
M
2
+
p
2p
P
P
P
P
P
4D²
M
M
M
TE
M
M
M
+
+
4p2
P
P
P
4p2
n
M
M
11
YI
M
M
M
M
n
M
M
2
2
+
4p²
p
P
4p
M
TI
YL
M
M
2
2n
M
2
1
P
4p2
p
p
n
M
n
n
M
M
2
P
p
P
P
n
M
2n
n1
M
2
2M
n
M
nM
M p
1
p
P
P
p/
P
p2
p
p2
2(n + M)
3n 2
+ 3nM + M
n
+ 3n M
+ n2
M
P
D2
nd
2(n + M)
3n 2 + 3nM + M
n
+ 33 M + nM2
p
p
pd
Since p
4n+3M
we have:
3n + nM + M
n² M 2nM2 n
3n + 3nM + M
3
3n M + n22
+
22
3
n2
p
which implies d Tconcrrentt)
d2
sesuuetiaa)
and completes the proof.
3.
(iconcureet)
3
Asequential)
We first lower bound d
(tsoncurent) as follows.
g cancurrent)
n
2
2(n + M).
+
(n 2)²
M
+ M
+
M
+
3nM
p
p
p²
p
p
2p
2p(p M 1)
37

---

Unlocking the Power of Rehearsal in Continual Learning: A Theoretical Perspective
n p
2 2(n + M)
(n + M)²
M
n +
M
M
3nM
+
+
p
p²
p
p
2p
2p²
On the other hand, upper bound dg
(sequential follows.
dz
Asequential)
M
M
M
π
M
M
2
M
M
1
1
1
1
1
2p
p
2p/
P
P
P
P
2p
P
2p)
2p
M
2
M
n
M
M
M
M
1
+
1
2p
P
p
p
P
4p
2P
2n
M
n
+ 2nM
M
M
M
7I + M
n.12
M
M
2
P
p
P
P
4p2
P
P
4pp
2p
11
2n 2M
n² 2nM
M
M
YI + M
nM2 M
M
2
+
+
1
P
p²
P
P
4p
2p
n1
2(n + M)
(n + M)²
M
n + M
M
3nM
2
+
+
1
+
+
p²
p
p
2p
2p²
By combining the above equations, we complete the proof.
4. 44
jecncurrent)
>
d jieqqential)
Consider:
(sequential)
M
2
M
M
4
1
2p
P
P
P
2p
M
M
+
p
P
P
2/
2 YI + M
M
2p pd
+ M
M
3nM
2
2p
2p(p - n - M 1)
(concurrent)
04
F. Proof of Lemma 5.4
In this section, we prove Lemma 5.4, which helps to further compare the performance between concurrent and sequential rehearsal methods for general T. We assume that M 2. We first prove coefficients dor, dijker in Appendix F.1, and then prove the coefficients Cijk in Appendix F.2.
F.1. Proof of Coefficients dor, diser in Lemma 5.4
In this subsection, will compare the coefficients dor, disET under different rehearsal methods. We first fix the index i, which implies that we consider the generalization error the previous task i.
1. We first prove feoncurrent)
d
d
(sequential)
According to Lemma B.11, we have:
ni + M
T-1
oT
(concurrent)
1
P
T-2
M
T-1-1
1 11
(T- -1 1)p
1=
(sequentaa)
oo
38

---

Unlocking the Power of Rehearsal in Continual Learning: A Theoretical Perspective
2. Now, we prove fieT
(sequential) 11ST
p > 27 (n + M) M.nM. We first consider:
T
2-2
M
T-1-1
(1
"
n
1 n M.
(n + MMM T-1
-
(T - 1 1- 1)p)
p
D
1=0
(60)
71
+ M
T-1
T + M)nM
+
(44)
pd
where (i) follows from Lemma 1.12 and (ti) follows from Lemma B.13. We also notice that:
2-21-1
M
T T-k-1
( (1- 11
M
T-1-2
M
(T' - k - 1)p/
p
(T-
1)p/
(T - 1 - 1)p
1=
(1 (1- -T -k- -1)p
M
T-k-1
(1 (1-p)
M
T-1-2
M
p
(T (1-1-1) 1)p
TT T-1 1- 1)p
T-3
II
(1
M
T-k-1
1 (1-%) p
(1
M M p p
(T - k - 1)p
Amm
3
n + M
1
M
ni + M
(n + M)M
T-2
M M
1
1- p ) p
P
(T- 11-11 - 1)p
P
p2
1
M
M
n+ M
T-2
(2 MYM
(1- (1- p p
M
M
1
+
1
+
Tp
P
(1-1 1}p
P
12
1=0
n + M l
M
M
Te + M)M²
+
(45)
p
TT
--1-11
T2p²
pd
where (i) follows from Lemmas B. and B.15 and (ii) follows from Lemma B.13. By combining Equations (44) and (45), we can conclude:
(sequential)
12
12 +
M
T-1
T-2
Σ
1 n + M
M
T + M)nM
M
(n + M)M2
$16T
p
1
P
+
P
-1- 1)p
+
pd
T2p
pd
1=0
n M
(1
+
M
T-1
T-2
n + M
)
M
1
1
p
p
p
(T-1- (T-1-1)) -1)p
1=0
AIFT
(concurrent)
(46)
where (i) follows from the fact that >> 2T + MyMM
3. Next, we prove fconcureent)
(scquential)
if > (n + M),, for = 2,3,..., T -1. 1. We first have:
15F7
T
M
T-k-1
12
M
T-j-1-1
M
TT- - k- - -1)p
p
TT 1 1)p
(T 1 11-11 1)p
M
T-k-1
(
(1
M
T-j-1-1
M
(T- - k - 11)p
p
(T - 1 1 1)p
T-1-1 1)p
T-j-2
M
T-k-1 (1 (1-
n M
(T- k - -1)p
p jp
k=0
T-j-2
1 n + M
M
n M
(n +
+MM
T-j-1 M
+
Tp
p
(T-1- 1)p
p
p²
jp
(1)
(1- Tp
T 2
Σ
n + M
M
n M
T-j-1
M.
Tn + M)
1
+
1
+
P
(T- 1- -1)p
p
jp
jpm
1=0
39

---

Unlocking the Power of Rehearsal in Continual Learning: A Theoretical Perspective
T T-j-1
n+ + M
M M (T-1-17 1)p T
(m + MMM
1
+
(47)
p
pd
1=
where (1) follows from Lemmas B.12 and B.15, (ii) follows Lemma B.13. Therefore, if > (" + M)M, we have:
T-j-11-1
M
T-k-1 1
1 (17) m (1
M
T-j-I-1
M
(T - - 1)p
(1-1-1)p
(T- 1 1)p
k=
T-j-1
1 n + M
M
(48)
p
(T' -1 1)p
1=0
Furthermore, we have:
T T-j-1
(1-
M
T-k-1
(1-1) 11
(1-
M j-1
n
(1-
n + M
T-j
n
(49)
(T
1--1111) 1)p
1)p
P
p
k=
where (i) follows from Lemmas B.12 and B.15. Therefore, by combining Equations (48) and (49), we have:
GjsT
(sequettaal
T-f-1
Σ
M (1- n2
(1
P
(T- 1)p
M
+
(1-
n2
+
p
M
T-J
p
<
(oonuureent
(50)
I=0
4. Last, we prove dvrer
conncureent
(sequentia)) arer
The proof is straightforward:
(eqquential)
-(--TT
M
T-1
n
n2
conneurent) d TTYT
ATIT
(T
1)p
P
P
5. Morcover, for the other choices of j, k we have (concuurent) and
dijkT
df (equuetiial
O.
F.2. Proof of Coefficients Cigk in Lemma 5.4
In this subsection, we will compare the coefficients c2 Ciyk under different rehearsal methods. Before we start, we first provide some important observation about the terms 31 and B2 in Equation (32). We split the term 31 into two parts.
T-1-1 Σ
n M
1-11-11
M )2 (-1-1)
B1 =
|100
-woll
w
3
P(p
M -1) 1)
1=
n M+M
IT 22--1
M (---1)
+
M M-1 11003 w
p
p(P
BT.
(51)
n M
(i-1-1)
M )2
Σ
|03 - -will
p
p(p - n1 - M - 1]
k=j+1
Since T - i - 1 2 0, we notice that B consists of terms 8/ 1|13 - -will where 8tt 2 (1-
n+M
M²
for any
T4pa
j,k E [T' -1] 1] and < As For the term ST. we have:
3T = Σ
2
1
n + M
T #1 1-2 2-1-11
Σ
Σ
p(P n M 1) ||00 w
(-111)²
)²
1=0
#=1
n M
li-1-2
(--1-1) )2
1|03 - wil2
P
k=j+1 p(p - n1 - M 1)
n + M
T-í
(1- n |1-"+,
M
1 1i-1-2 i-1-1
(MM )2
Σ
Σ
100 -w
p
p(p - n M - 1)
+=
40

---

Unlocking the Power of Rehearsal in Continual Learning: A Theoretical Perspective
T(n + M)
221-1-2
1-1-1
)²
||00 -wūll
(52)
p
p(u M 1)
The above argument shows that ST consists of terms je |m= - wi I2 where 65.x 2
-T for j. E [i 1] and
j < k. Therefore, if p > (T+ + 1) + M). we can conclude that 31 consists of terms 55.2 ||203 - -wal for J. k E T - 1]
and j < k, where
n
M
M T2p
T' + M)M²
89 2
>0, 0,
(53)
P
1
By the same argument, we have:
T--11
IT--1
n M
B2
Σ
T-1-
wwj
w7 -ill 11 122
P
p(p 12 M- 1)
1=0
T-2
n M
IT-1-1
nM
T-I-1
|1003 207-111
p(p - n - M 1)
82
(54)
n + M
nM
1
i-1-1
||00 -w w/
p
p(p M - 1)
j=1
where 35 consists of terms nHA 1|/3 - will 1|
with T 2 [ n+M
aM for j, E [T- - 1] and j < h and 3y consists
Tp
of terms M7 m0 uIill with 75.K 2-
for j. h E [1 - 1] and j < k. Therefore, p > (T + 1)(n + M)M,
we conclude that B2 consists of terms Mjjk
1100 - will 1 for j E [I: - -1], = 2, i where
n + M
nM
T + M)nM > 0.
nj.k3 2
1 (1-
(55)
p
Tp
pd
Now, we start to coefficients 6, Cijk in Lemma 5.4. We first fix the index i, which means that we consider the forgetting on the previous task i. The proof of C
(coneurrent) <
(scquential) if > 2n + M)² follows from Lemma 1. directly.
The proof of (eoncurent)
Cjkk are follows.
(sequential)
ijk
1. We prove
(concurren))
Cil
(equuatiia))
if p > (T + M)nM. We first upper bound part of the coefficient (sequeatial).
Gii
M
T-1-1
1 n
M
1 11
}}
p
(T- 11)p
p
(i 1--1-1 1)p
p
1=0
1=0
(4)
+
M
T-1
(1- 1
n + M
i-17
T (n + MmmM
(56)
p
p
p
pd
where (i) follows from Lemma 171 We then upper bound the other part of (sequentia))
cis as follows.
2-21-1
Σ1
M
T-k-1
1 (1-)
n1
M
T-1-2
M
T k 1)p)
p
T 1 1)p
T - 1)p
(1 (1 - - 1)p
M
i-k-1
(1 (1 p
n
(1
M
1-1-2
M
(i 1i-1 1 1- 1)p
(1-1- - 1)p
T-k-1
T-1-2 M
M
1 n)
(1
1
M
(T- k 11-1) 1)p
p
(T- - -1 - -1)p
(T I 11-11 -1)p
M
T-k-1
I n
M
T-1-2
M
T - k- -11pp)
p
111pp
(T --1-1)pp 1)p
41

---

Unlocking the Power of Rehearsal in Continual Learning: A Theoretical Perspective
M
s-k-1
n p
M
1-1-2
M
1 11-1111)
(i k 1)p)
1)p
(i-l- - 1)p
k=u
M
T-k-1
1 n
(
1
M
T-1-2
M
(T (T-K k 111pp
p
(1-1-11)
(T - (P-1-11 1)p
(T 11-TT h --11 11pp
M
T-k-1
1 (1pp)
n
(1
M
i-l-2
M
p
(1-1 1---11 1)p
(i (i- 1 - 1)p
M
i-k-1
(1 (1-p) p
M
1-1-2
M
1
ii-k k 1)p
(i (i-1-10 1)p
(i-l- 1)p
n + M
M
M
T + M)M2
+
P
(T-1-10 - 1)p
T2p²
pd
n M.
(n+ + M)M
1-++T
n + M -1--
M
1-1-2
M
+
P
D2
P
(i - 1- 1)p
(i- 1 1)p
n + M
M
M
T2 + M)M
p
(T-1- 1)p
T2p²
pd
n + M
1-++7
(n + M)M
(1 (1- P
n + M
M
p
p²
(i ( 1 - 1)p
n M
M
i-1
1 n M+M 1
M
M
M
2T + M)M2
+
(57)
P
(T ---1-
1- 1)p
p
(i-l- 1)p
Tzp²
pd
1=0
where (1) follows from Equation (45) and Lemmas B.11 and B. 12, (ii) follows from Lemma B.13. By combining Equations (56) and (57),
(sequential) i1
n
(1
n + M
T-1
n+M
8-1
T-1
M+
n
M
p
p
P
P
(T- 1)p
1
n + M 1
M
T2 + M)nM
M
2T (n + MMM²
+
T2p2 +
(58)
P
(i-l-) 1)p
pd
pd
(
+ M
T-1
1
n + M
f-17
+
Σ
T-1
1
n = ² 1
)
M
p
p
P
p
(T (T- 1)p
1=0
+
M
1
M
p
(1-1-1)p
(84)
G1:
(concurrent)
(59)
where (i) follows from the fact that p >>>> 37 (n + My,M, (1i) follows from our observation in Equations (51) to (55). (sequential)
2. Next, we prove (concurrennt)
Gijs of two parts, where the first part can be upper bounded by
cigy >
p > 3T (n + M ),,, for j = 2, ..... 2 - 1. We observe that Giya
(sequential)
consists
T-1-1 Σ
M
T-K-1
1-1)
1
(1 1 (T- 1-11-1 1)p
M
T-1-1-1 M
1
(T- k - 1)p
p
(T - 1 - 1)p
ΣΙ (1-
M
1-
(1- n |
(1-
M
i-j-t-1
M
( k - -1)p
p
(i 1- 1)pp
(i - 1- 1)p
0=0
k=0
42

---

Unlocking the Power of Rehearsal in Continual Learning: A Theoretical Perspective
(1- n
M.n+MM M
i-j-1 Σ
n + M
P )
M
M
(m
1
+
(60)
p
(T- 1)p
(i-1-1)) 1)p
p2p²
pd
I=0
1=0
The other part of (sequential)
Cija
can be upper bounded by:
M
T-K-1
1 (1-7)
12
M
8-1
1
TT k - 1)p
p
(j 1)p
k=
i-j-1
M
i-k-1
(1 (1--)
M
R1P
(i - 1 - 11pp
p
[j - 11))
k=
n M
i-j-1
( (1- n + M
T-i
T2 + M)M
(1 (1-
M
j-1
n
1
P
p²
[
1)p
+
M i-j-1
n + M T-i
T2 + M)nM
(61)
P
Dd
where (i) follows from Lemma B.17. By combining Equations (60) and (61), we have
(sequential)
+
M
M
n + M
M
P
(1- 1)p
p
(i-1-1)0 1)p
n + M
f-1
[
n ++M M
T
+ M
MM
M
2T + M)M²
1
1
p
p
pd
T2p²
p3
n + M 1
M
i-j-1
n M
M
1
p
(T 1--1-1 1)p
(1-1-10 1)p
1=0
1=0
n + M
i-j-1
(1- n + M
T-i
-1
-1
p
(concurrent)
(62)
where (i) follows from the fact that p> 37 + M M, (1i) follows from our observation in Equations (51) to (55).
3. We prove (concurent) > Equations (47) and (49), we have
d ijjs
(sequential) Ejs
for j = i, + 1, ...., T p > (n + M)M According to the same derivation as
(sequential) ijs
T-j-1
1
n + M M
M
1
n + M
T-j
n
M
T + +M)
p
(T 1- 1)p
p
p
T T2p²
pd
1=0
T-j-1
n + M
M
n + M
T-j
1
p
( 18-1-17 1)p
p
P
(comcurrent)
where (i) follows from our observation in Equations (51) to (55).
4. Last, we prove
(concurren)
Cyi
(sequential)
i >>>0>:>>:: (2 + M)M. Consider:
(sequential)
(1
M
T-1 n
(1
M
1M
Crr
TT 1)p
p
(T
1)p
p p
<<
2
(1)
p
43

---

Unlocking the Power of Rehearsal in Continual Learning: A Theoretical Perspective
(88
(concurren))
(63)
where (i) follows from the fact that p (n + M)M, (ii) follows from our observation Equations (51) (55).
5. As discussed in Equations (51) to (55), we have
G. Proof of Theorem 5.5
In this section, we prove Theorem 5.5 where we provide a particular example in which sequential rehearsal has lower forgetting and generalization than concurrent rehearsal. We first prove the forgetting part in Theorem 5.5, Recall Fr T == ((rr( Li(w,)). Therefore, it suffices to prove
[Ci(wT) [:ww;) [,: (coneurrent)
[(((WT) - ((:))) (Sqquunnttt)tiaaaa
and | -w;ll 2 for (sqquentaa))
if > (n + M M for each i e [- 1]. Since w are orthonormal, we have ||0 i F j. Recall the discussion about B2 in Equation (54). Then, we consider
28 = Σ
T-i-1
1
n M
2nM
p(p n2 - M - 1)
1=U
[] (1 M
2nA
p(p - - M --1) 1)
1
na M
P
2nM
-I (T-))
2+ ya
(64)
p²
2+-. P
We note that for any & E [3, T -i -i-1
and & is odd, we have
T - 1
n2 + M
T - 1 k: + 1
n M
k+1
+
P
p
(T - i)!
n + M
k
n + M
[T - i - k - 1)!
T i - k
k: 1+
(T'
n + M k
[1
+
M
I! - i k: - 1)!
P
0,
where (i) follows from the fact that
> T(n+ + M). By simply discussing when T - i is odd or even, we can have
T ) (- n + k
T 1) ( n+M
T (T-²) 1) (
+ M
2
P
P
P
TT (n M)
(TT i 1)(n + M)²
2p
By substituting the above equation into Equation (64), we can have
2nM
(T i)(n + M)
(T-1)( -i 1)(n + M)
285
p(n + M)
2p²
2(T -inM
(T- iT - -i- -i-1)(n M MynM
p2
Dd
(T i)(n + M)M
M
T2 + T MynM
(65)
1
44

---

Unlocking the Power of Rehearsal in Continual Learning: A Theoretical Perspective
where (i) follows from the fact that n 2 M 1. Now, can conclude:
(C((T)) L,(w,)
(connurment) (
T
(ooneureen)
+ 2
concurrent)
j=1
(
1
11
M
T-1
1
+ M
i-17
2
(sequentaa)
+2, +23
p
p
P
j=1
n + M
T-1
+
M
L-17
+ 2
(sequemial)
+
(66)
p
p
P
where (i) follows from Equations (58), (62) and (63). On the other hand, we have:
(2TT) - Li(w)) ) (soquential)
(
1 n1
(
n
"
T-1
-
-11-n+
n
T
(squential)
+
P
==1
(T
in + M)M
(n M2
(67)
p2
pd
where (i) follows from Lemma B.18. By combining Equations (65) to (67) and the fact that p > 2T + MynM, we have
(L,(w)) - (ww,) (scecurmnt)) > (WTT (.,,) (sequemtial) [
which completes the proof.
Next, we prove the generalization error part in Theorem 5.5. Recall Gr = # (L:(WT), suffices to prove
(ooncumennt
(WT) L.
((sequential) (WT)
if p > (n + M + M)²M for each i E [T]. Since w are orthonormal, we have || = 1 and || woil² = 2 for
i * j. Therefore, we have
n + M
16-1-1
nM
Σ
p(p n2 - M 1) [wj : w.'ll !|
E-I-I
j=l
T-2
n + M
IT-1-1
MnM
1
T-I-I
P
2
j=l
n M
T
2n
(T 1)
P
p²
T(n + M)
2(T 1)mM
p2
T(n + M)
(T'- () + M + 1)M
(68)
P
2
where (1) follows from the fact that n 2 M + 1. Therefore, by combining Equations (31) and (68), we have:
C plconcurent) (wr))
1 11-1 p
1 )
n M
T-1
p
(1- n M
T-1
n
T-2
n + M M
+ 2
p
P
p
(T-1-
1)p
1=0
45

---

Unlocking the Power of Rehearsal in Continual Learning: A Theoretical Perspective
+
p )
M
+ (11-
n + M
T-j
2n
+
(T- 1)p
p
p
p
j=2
i=0
T(n + M)
(T- + M 1)M
(69)
p²
On the other hand, we have:
4.
(sequeeniall)
(WT)
-
11
n
M.
(n + M)M
T-1
P
p
2
+
M
T-1
TE
T-2
Σ
1
n + M
M
P
P
-T- 1)p
1=0
--1
+
M
1
M
(1
n + M
T T-j
2n
+
P
(T-1-10 1)p
p
p
1 _
(1
n n
T-1
P
n+ M
T-1
TE
T-2
n M 1
M
1
P
p
(T-1-1 1)p
1=0
(T-5-1
n
M
!
M
(1- n M
T-j
n2
2n
+
p
TT
1-1--1h
P
P
1=0
(T - 1)(n+ + M)M
I' + M)
(70)
2pd
where (i) follows from Lemma B. and Equations (46) and (50), (ii) follows from Lemma B.14 and the fact that 1 1 2 < 1. To build the relationship between Equations (69) and (70), we have:
T(n + M) (In+M))a
(T- 1) + M + 1)M
(T- 1)(n+ M)M
T + M2M
1
12
D²
2pt
(T -1MM
T(T 1) + M) + M + 11M
I + M)2M²
pd
2pd
> 0
(71)
where (1) follows from the fact that p > 2n p(soquentia)/ (wr).
(n + M + 11)MM. By combining Equations (69) to (71), we can conclude:
C c/coneurrent (wr) > C. (w.r))
H. Proof of Hybrid Rehearsal in Proposition H.1
First of all, recall that the memory set M, = .MMii UMiss where MMri Unez(mm) Me, and M = Uher Men We present the explicit expressions of coefficients and the noise term in Theorem 5.1 for hybrid rehearsal method in the following proposition.
Under the problem setups considered in this work, the coefficients that express the expected value of the forgetting F; and generalization error Ge obtained by Algorithm take the following forms.
Proposition H.1.
d (lybrid) roT (t - 1);
(lybrid)
Afhybrid)
fhybrid))
64
dg.
46

---

Unlocking the Power of Rehearsal in Continual Learning: A Theoretical Perspective
(-j-1
Σ (1 Bi,1) -:-1 Br) (8lm)
+
" (1 Bi,,) Tr (.())BB,.:KI, (slm)
(-1,) 2
1=0
1=0
+(1 - Bb- " nl'ilt - k)
(sim)
+ (1 B 1z
1 -roo
1--
(lohrid)
T((1(11 -Bi,) -
- Bi, B
if
j E -t- 11,
jjkt
ru) + +nIi(t= K) (1EZ!
if
j t,k =i
E [1 B1,1) - L1()) (iikzz
if
j < k and j. k + i,
I I 1:) Ke) (
if
3 < k and j.k
(eyrrid)
((hobrid)
hyyridd) ijki
ijkk
2-2
(ybridd
(0) = Σ r(())
Σ (1
-e(5)) - + (1 - B1,t) 14 Anto 1 Ba
noise,
1=0
j=1
M
i
where Ta == 1- nooe
Bi =
(1-1-1)9
Ki,
c-1-1 [((N) 1-1 Se(i) such that (the 9th element
Bi
p
O.W.
p-n-
a-1
of I(
j. 1 (/ = 1, p
(dit) [.]
= 1 1 L'((a)
II
(1 B1,t)
Ao,a
p-a-1
1=0
In Algorithm 1, the training process of CONCURRENTTRAIIDII is equivalent to solve the following optimization problem:
min w wi-1l 1 s.t. X, w = Y,, w
x, Ye,,, h h I
(72)
Then, the training process of SIQUEENTAALTRAIN(MM.. for h: Med E Mits is equivalent to solve:
i. (fe(
u 11) 2 s.t. X, Yeh: h = 1,2, 2,,,,.. [di) (dix)
min
(73)
where the (h) element of I(diaa is h. The final convergent point of task is denoted w, wi (Iz (09) argument concurrent rehearsal (or sequential rehearsal), it suffices to prove Lemma C. 1 to derive the explicit expressions for both forgetting and generalization error. Consider an arbitrary i s.t. < T and fix it. The expected value of model error ([:)(w:)) are derived as follows including concurrent part and sequential part.
By the same
The first part is concurrent part. Define Visim as the concatenation of X, and X,,, for all E I Similarly, define s as the concatenation of 2; and Z,, for all h E Z!sim) By following the same argument as concurrent rehearsal method, we have:
E
2
+
I
(ii))
M
1 - w. 11 + Vrimt t
x (w, - w
(n + ( M (smm)
)
E
+
p n
[
M 1-1
x, (w - -0,)
|Z(
(sim)
M Z-i
(
E [ - 11
n MM (| (sim) 1)
M
+ Σ
1+
1-1
||w0 -o,l²
(t 1)p
p- 12 |Z|
(im)) M
47

---

Unlocking the Power of Rehearsal in Continual Learning: A Theoretical Perspective
I
M (im)
+
n2
1 +
||w0 - 1,,
(
p
p
n
t-1
.MM
)2
(--T)
M 1) (11003 - wi/1 woil²-1|u0 ww 1-22 -1|00g - uo7 11²)
p(p
(
J.KEI,
kSj
a.
1) (11003 - 2n,1 112 1 [uo - we. 11 -1120 -wo" 11²)
p(p n2
I
s 1-1
jEZZiu
(n +
|
)0²
r-1
(74)
p - I
bim)
M
where (i) follows from the same argument of Equation (29) and (ii) follows from the same argument of Equation (30). The second part is sequential part. According to Lemmas B.1 to B.4, we have:
(f(()) E 3
-w: 1111=1111
= (1-1-11-0 M
E
2 (1(00-1)
w
+
M
|20
w 1|
M (t-1)
1)
0²
(t 1)p)
1)p
By iterating the above equation, we have:
W. wi 1 =
(1
1
M
E
(0)
w ||²
(t 1)p
[24 (((())
M
M
+ Σ
E [ - w
(t - 1)p
(t - 1)p
jEzúa
M
1-(()
M 0² 1-1
(75)
(t
1)p
M
By combining Equations (74) and (75) and repeating the process, we derive the expected value of model error (,w,, with hybrid rehearsal method as follows.
E ww
1
M
1
n1
+ |
(sim)
I-I
M
|w:-1 - w 11
(1- 1)p
p
M
12
t-1
M
(sim) tsj
/ - wo 11
+
(t - 1)p
(t 1)p
|
+
M
n
: - w
(I - 1)p/
p
1 (sim)
(sim)
M )2
1
M
Σ
t.j 1
i-1
M. - 1) |wj - -will 1
(t 1)p/
1= 1 p(p - n
(sim)
M
t-1
1 (sim) nM
t.j 1-1
|wj - wi 1|
+
(t 1)p
p(p - n - | (isi)))
M
1)
T-1
|
(1 (1- (t. -1)p
M
M
(dis) t-
100 will
(t - 1)p
+
(
M
|
(n + | (sim)
1-1 )02
M
+
M
(-40)
i-1
M 02
(t - 1)p/
I (im)
M0
(t - 1)p
M
p- n
1-1
j=1
P
T-1
48

---

Unlocking the Power of Rehearsal in Continual Learning: A Theoretical Perspective
M
n +
1
h-
1
||,x,12
(t
1)p
p
p
0=0
1 (t-l-1) 1)p
M
|
1-1
1
M
1
+ (
(im) M
1-
1 (sim) M t-
(t h
1)p
(t - 1 1)p
h=0
M
(
2-j-1
M
+
[ h- h
(im)
M
h-h-1
(j+ |/=1} (+=1) - 11p
[1 - h - 1)p
p
h=U
1
M
n |1 2-1
(im))
{- hhh I
M
(1
1
M
1 (diss) M
(-i,)
(t h - 1)p
(t - 1 - 1)p
(t - 1 - 1)p
h=0
1|w3 20, 112
(1- (f - 1)p
M
1
n2 +
1olbl-11 1-h-1
1-1-1
(sim) (sim)) 1.J
1 1-1,k ( M )
1-1-111
100 w
p
p(p
[ 2-1-1
M
+(1 (1--t-
M
[
1-1-1
Σ
1 (sim) nM
2- 1,j (-1-)
100
wi-111
(t 1)p
p(p
12
[ (sim)
1-1
M
1)
+ noise, (hybrid) (r)
where (i) follows from the iteration and Equation (28) and
(-21-1
M
( T-n-1
noise,
(yybid)) (0) = ΣI
1
(t - h 1)p
p
1=0 0=0
M
|
(n + |((im)
x-1-1 )o²
M
1-1-1 o2
1 -
(t - 1)p/
n sim)
M
1 1)p
p 1-1-1
M8
1-1-1
1-2
M
(1
n +
(sim)
M
no²
2-
I
(1 1)p
p
P n
By rearranging the terms and substituting t T, complete the poof for (bybrid) doz
and d (ybridd)
Furthermore, the expressions and the definition of forgetting.
15k2
of C
(hyhrid) and (hyhrid) in Proposition H.1 can be derived directly based on doT Gijk
(hyrrid)
and d iikT
fhybrid)
49

---

Unlocking the Power of Rehearsal in Continual Learning: A Theoretical Perspective
(a) Sample images without corruption.
(b) Glass Corruption: the images are transformed to simulate the effect viewing through frosted glass, inducing localized blurring and pixel displacement.
(c) Color-swapping and Rotation Corruption: the images are randomly rotated by arbitrary angles, and a subset of pixels undergoes random permutation of RGB channels.
(d) Elastic and Pixelate Image Corruption: the images are subjected to smooth, linear spatial deformations followed by pixclation, resulting in low-resolution appearance.
Figure 4. Sample images for demonstrating the employed corruption schemes.
50


Reviews:
[{"review_id": "NaPtKFVcv4", "reviewer": "Reviewer_ngv9", "summary": "The paper studies rehearsal in continual learning for overparameterized linear models. Next to concurrent rehearsal, which is the commonly used setting, they also look into sequential rehearsal, where different task data is revisited sequentially. From the theoretical analysis, they conclude that for highly dissimilar tasks, sequential rehearsal may be better. Interestingly, they next turn this into a practical algorithm, where the most dissimilar task is learnt sequentially while the other tasks are learnt concurrently. Although the effect is minor, a positive effect is observed on standard small continual learning benchmarks such as MNIST, Cifar 10 and Cifar-100.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for providing the valuable review. Please note that all our new experiment results (i.e., the tables we quote below) and our codes can be accessed via the link \nhttps://anonymous.4open.science/r/repo-c14014\n\n\n**Q1:** Results with more / larger datasets (e.g. (mini)ImageNet), and under different settings could have strengthened the paper further.\n\n**A1:** Thank you for your constructive suggestion. Despite the limited time, we made every effort to expand our experiments to Tiny-Imagenet200, as presented in Table R1 via the anonymous link. Our experiments on Tiny-ImageNet demonstrate that hybrid rehearsal achieves a substantial improvement over conventional concurrent rehearsal. On the original dataset, hybrid rehearsal improves the Averaged Final Accuracy by 2.19% and reduces forgetting by 3.66%. On the corrupted dataset, it improves the Averaged Final Accuracy by 2.38% and reduces forgetting by 13.32%, which also aligns with our theoretical observation that benefits of our hybrid rehearsal increase as task dissimilarity rises. Furthermore, we observe that the advantage of our method is even more obvious in Tiny-Imagenet200 compared to MNIST, CIFAR-10 and CIFAR-100. This is because Tiny-Imagenet200 is a more complex dataset and exhibits a higher level of task dissimilarity, and hence benefits of our hybrid rehearsal are more salient.\n\n**Q2.**  I doubt whether the observed differences, which have only been shown in a task-incremental setting, are worth the extra complexity in a practical setting, and concurrent rehearsal may remain the go-to solution. \n\n**A2:**  We sincerely appreciate the reviewer’s insightful observation. We agree that hybrid rehearsal can introduce additional complexity in practical deployments, and that conventional concurrent rehearsal may offer greater simplicity and convenience. We also appreciate the reviewer’s recognition that one goal of our paper is to highlight, from a scientific perspective, that concurrent rehearsal, while practical, can be suboptimal in terms of performance, as we have demonstrated in task-incremental settings. Our findings suggest that alternative strategies, such as hybrid rehearsal, warrant further exploration for their potential benefits.\n\n\nWe thank the reviewer again for your inspiring comments. We hope that our responses resolved your concerns. If so, we wonder if the reviewer could kindly consider to increase your score. Certainly, we are more than happy to answer your further questions.", "claims_and_evidence": "I did not find any problematic claims.", "methods_and_evaluation_criteria": "The proposed method is simple, but this is mostly a theoretical paper. The strategy for the proofs in the paper make sense. \nEvaluation criteria are the ones commonly used in this context.", "theoretical_claims": "I did not check all proofs completely, but could not find any issues in the proof outlines and other parts I checked.", "experimental_designs_or_analyses": "Results with more / larger datasets (e.g. (mini)ImageNet), and under different settings could have strenghtened the paper further, for instance going beyond the task-incremental setting, to class or domain incremental ones.", "relation_to_broader_scientific_literature": "The authors did a good job in contextualizing their work in a broader context, including both the standard continual learning literature as well as papers focusing on a more theoretical analysis.", "essential_references_not_discussed": "I can't think of any references that should have been discussed but are missing.", "other_strengths_and_weaknesses": "The key finding of the paper, that sequential rehearsal can in some cases outperform concurrent rehearsal, is interesting and somewhat surprising. The paper's strength is that this is not only observed empirically, but also analyzed theoretically, albeit on an overparameterized linear model only. \nNeither of the two parts of the paper (theoretical analysis, empirical study) would have been sufficient on their own, but combined I think there's sufficient evidence. \nI found the paper well structured and clear. \n\nI doubt whether the observed differences, which have only been shown in a task-incremental setting, are worth the extra complexity in a practical setting, and concurrent rehearsal may remain the go-to solution. Nevertheless, the paper shows that concurrent rehearsal may not be the optimal setting, and I think this is worth sharing.", "other_comments_or_suggestions": "/", "questions_for_authors": "1. Did you try experiments beyond the task-incremental setting ? Is there a reason why you did not ?", "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": {"ethical_review_concerns": "/"}}, {"review_id": "WtvUecKIE5", "reviewer": "Reviewer_ptpD", "summary": "This paper theoretically and numerically investigates the effects of concurrent and sequential rehearsal in the context of continual learning. The authors analytically derive that, in a linear regression model, sequential rehearsal leads to better performance than concurrent rehearsal when tasks are more dissimilar. To validate these findings, they propose a hybrid approach in which memories with low dissimilarity are rehearsed concurrently, while those with high dissimilarity are rehearsed sequentially. This hybrid strategy is then applied and tested within a deep neural network model across multiple tasks, showing minimal to modest improvements over a purely concurrent approach.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for providing the valuable review. Please note that all our new experiment results (i.e., the tables we quote below) and our codes (including code for Fig. 2) can be accessed via the link \nhttps://anonymous.4open.science/r/repo-c14014\n\n\n**Q:** Clarify the choice of $\\mathcal{L}_i(w)$, and justify the performance metric in the overparameterized setting\n\n**A:**  We first clarify that $\\mathcal{L}_i(w) = (w -w^*_i)^2$ is equivalent to the test error $\\mathbb{E}[y - Xw]^2$. To see this, we derive $\\mathbb{E}[y - Xw]^2 = \\mathbb{E}[X(w -w^*_i)]^2 + \\sigma^2= \\mathbb{E}[(w -w^*_i)^\\top X^\\top X (w -w^*_i)  ] + \\sigma^2 =   (w -w^*_i)^2+ \\sigma^2 $, where the last equality follows because $X$ has i.i.d. standard Gaussian entries, and $\\sigma$ is noise level. Such a loss has been commonly adopted in recent theoretical studies of CL [1,2]. \n\nThe example given by the reviewer is not valid, because the loss function (i.e., the test error) needs to take the expected value over the distribution of $X$, not for a specific value of $X$.\n\nFurther note that the model parameter $w$ depends on input data $X$, because the model is trained based on data. Thus, the performance of forgetting and generalization defined in (4) and (5) is evaluated using the **expected value** of model errors, which reflects the overall performance across a set of inputs. \n\n**Q:** Provide reference for the statement \"the convergence point of SGD for MSE is the feasible point closest to the initial point in $l_2$-norm, i.e., minimum-norm solution.\"\n\n**A:** In [3,4], it has been mathematically shown that in overparameterized linear models, SGD/GD converges to the minimum-norm solution, i.e., the feasible point closest to the initial point with respect to $l_2$-norm. Further, such a property has been widely used to simplify the theoretical model in CL [1,2]. \n\n**Q** Numerical results are within error margin?\n\n**A:** In Table 1 of the paper, the improvement of both generalization and forgetting on **corrupted** datasets (with higher level of task dissimilarity) is substantial and far more outside the error, which validates our theoretical observation. The improvement is marginal on original datasets(Split-MNIST, Split-CIFAR-10, Split-CIFAR-100) because their task dissimilarity level is not significant. \n\nWe further conducted **new experiments on Tiny-Imagenet200** (see Table R1 via the anonymous link). For this more complex dataset, where task similarity is much higher, on the original dataset, hybrid rehearsal improves the Averaged Final Accuracy by 2.19% and reduces forgetting by 3.66%. On the corrupted dataset, it improves the Averaged Final Accuracy by 2.38% and reduces forgetting by 13.32%. These results clearly demonstrate the benefits of our hybrid rehearsal. \n\n\n**Q:** Will resampled input-output pairs in memory alter $w_i^*$ that perfectly solves the corresponding task?\n\n**A:** We clarify that in this paper, ​$w_i^*$ represents the ground-truth model parameters, which are **fixed** for each task. Then based on such a ground-truth $w_i^*$, data are generated by $Y_i=X^\\top_iw^∗_i+z_i$. Clearly, resampling of input-output pairs will not change ground-truth parameters. \n\n**Q:** Explain influence of $\\tau$. Why was it not tested in your experiments? If only one task is treated as dissimilar, doesn’t that bypass the role of $\\tau$? \n\n**A:** Thank you for highlighting this point. Our experiment is a simplified implementation of Algorithm 1, where  **at most** one task is designated as the ‘dissimilar task’ for sequential rehearsal. $\\tau$ still serves the role of threshold as follows. If multiple tasks have scores below $\\tau$, then the most dissimilar task is set for sequential rehearsal. Otherwise, if all tasks have positive scores, then no task is chosen for sequential rehearsal. Note that this is a reasonable experiment setup in CL [5]. \n\n**Further note on choice of $\\tau$:** Since the task similarity score is defined to be cosine similarity between gradient of each previous task and concurrent task, positive score indicates their alignment, and negative score indicates their confliction. Hence, in our experiment, we set threshold $\\tau$ to be $0$ naturally. In practice, $\\tau$ can be set negative to ensure the task dissimilarity is high enough. \n\nThank you again for your insightful comments. We hope our responses addressed your concerns and would greatly appreciate your kind consideration in increasing your score.\n\nReferences:\n\n[1] Evron, et al. \"How catastrophic can catastrophic forgetting be in linear regression?.\" COLT 2022.\n\n[2] Lin, et al. \"Theory on forgetting and generalization of continual learning.\" ICML 2023.\n\n[3] Gunasekar, et al. \"Characterizing Implicit Bias in Terms of Optimization Geometry.\" ICML 2018.\n\n[4] Zhang, et al. \"Understanding deep learning requires rethinking generalization.\" arXiv 2016.\n\n[5] Lin, et al. \"Trgp: Trust region gradient projection for continual learning.\" ICLR 2022.", "claims_and_evidence": "The authors claim that in a linear regression model, where labels are generated from a noisy teacher network, and under the mean-squared error (MSE) criterion, in the over-parameterized case (i.e., when the input dimension exceeds the number of training examples), the following holds:\n\n1. Sequential rehearsal outperforms concurrent rehearsal when tasks are more dissimilar.\n2. This principle extends to deep neural networks.\n\nHowever, as I will argue below, I have concerns that the authors' performance metric may not be fully justified, and as a result, the theoretical claims may not be valid.\n\nAdditionally, throughout their proofs, the authors rely heavily on the statement: \"It is known that the convergence point of stochastic gradient descent (SGD) for MSE is the feasible point closest to the initial point with respect to the \\mathcal{l}_2-norm, i.e., the minimum-norm solution.\" Unfortunately, they do not provide a reference for this claim. To my knowledge, there is no theoretical work that confirms this result in the over-parameterized case.\n\nAs a consequence, the minimization procedures presented in lines 187 and 212 may not accurately reflect the outcome of running SGD.", "methods_and_evaluation_criteria": "The loss over task $i$ for current parameters $w$ is evaluated as $$\\mathcal{L}_i(\\mathbf{w}) = ||\\mathbf{w} - \\mathbf{w}_i^*||.$$\nHowever, I believe this measure is not appropriate in the underdetermined case, where the input dimension $p$ exceeds the number of current training examples $n$. In such situations, the current weight vector $\\mathbf{w}$ can differ from the target weights $\\mathbf{w}_i^*$ while still yielding an MSE of zero. This occurs because, in an underdetermined system, there are multiple weight configurations that can perfectly fit the data, making the comparison between $\\mathbf{w}$ and $\\mathbf{w}_i^*$ potentially missleading.\n\nFor example, let's assume the first task has one input $\\mathbf{x} = [1, 0]$ with $\\mathbf{w}_1^* = [1, 1]$ then $\\mathbf{w} = [1, 0]$ yields a MSE of $0$ but $\\mathcal{L}_i(\\mathbf{w}) \\neq 0$! In fact, $\\mathcal{L}_i(\\mathbf{w})$ can be arbitraily large or small.\n\nFurther, the authors state: \"To simplify our theoretical analysis, we focus on the situation in which the memory data are all fresh and have not been used in previous training.\" However, if the input-output pairs in the memory are resampled after each task, then in the underdetermined case, this would alter the set of $\\mathbf{w}_i^*$​ that perfectly solve the corresponding task.\n\nIn summary, the theoretical setup does not appear to be fully consistent with the derivations and conclusions drawn.\n\nNumerically, the hybrid rehersal training framework leads to minimal to modest improvements over a purely concurrent approach. However, improvements are often within the margin of error and thus may be simply a result of noise.", "theoretical_claims": "All theoretical claims are based on the loss function $\\mathcal{L}_i(\\mathbf{w})$. However, as discussed in the Methods and Evaluation Criteria section, I have concerns about the validity of this measure. Specifically, I believe it may not be appropriate, which raises doubts about the validity of the theoretical claims that rely on it.", "experimental_designs_or_analyses": "The authors validate their analytical results numerically (albeit without label noise) in Figure 2. Interestingly, the theory and simulation appear to align perfectly. One possibility is that my concern about $\\mathcal{L}_i(\\mathbf{w})$ being unjustified is mistaken. Another possibility is that resampling items in the memory artificially increases the effective dimensionality of the training data, thereby shifting the model into the underparameterized regime. Or perhaps there is another explanation?\n\nUnfortunately, the authors do not provide their simulation code, making it difficult to verify these possibilities.\n\nIn principle, the numerical setup (datasets, evaluation criteria, etc.) in Section 6. appears well-designed to test the hybrid rehearsal training framework. However, the authors state that they \"adopt a straightforward relaxation: only one task with the lowest similarity characterization in memory is designated as the ‘dissimilar task.’\" This raises a significant concern — if only one task is treated as dissimilar, doesn’t that essentially bypass the role of the threshold $\\tau$? If $\\tau$ is not properly explored or validated, Algorithm 1 is not actually been implemented and validated and it becomes unclear how the simulation results refer to the theoretical claims. This should also affect how we interpret the trend described in Table 2, which is intended to reflect the theoretical result.", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "Robins (1995) was one of the first to study catastrophic forgetting, rehearsal and pseudorehearsal and thus should be included. Similarly, Mc-Closkey & Cohen (1989) and Ratcliff (1990) where among the first to explore and describe the phenonemon of catastrophic forgetting and thus should be referenced.\n\nIn my view, it would be important to include Prabhu (2020) to provide a more balanced perspective on the statement: \"A large amount of studies have been proposed to address this issue, among which rehearsal-based approaches (Rolnick et al., 2019) have demonstrated state-of-the-art performance.\" Including this reference would offer a more nuanced view of rehearsal-based methods and their relative performance.\n\nFurther, Lee et al. (2021) (\"Continual learning in the teacher-student setup: Impact of task similarity.\"), is closely related to the presented work but not cited. They also study continual learning using a teacher-student paradigm as a function of similarity between teachers.", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A", "questions_for_authors": "1. Could you clarify why the choice of $\\mathcal{L}_i(\\mathbf{w})$, and consequently the chosen performance metrics, is justified in the overparameterized setting?\n2. Do you plan to make the code (particularly for Figure 2) available (to reviewers)?\n3. Could you explain why the influence of $\\tau$? was not tested in your experiments?\n4. Why do you think the improvements of the numerical results are minimal (often within the margin of error)?", "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": "5HyvJ7QQHR", "reviewer": "Reviewer_GGhR", "summary": "In the context of Continual Learning, the authors propose a new rehearsal method, which is sequential. Then the authors present a theoretical analysis of both sequential and concurrent rehearsal methods. The authors derive a closed form expression of generalisation and forgetting for both methods. The main takeaway is that sequential rehearsal outperforms concurrent rehearsal when tasks are dissimilar. Based on these findings, they propose a hybrid rehearsal CL algorithm. For every new task, the memory dataset is split into similar and dissimilar samples. The similar samples are merged with the current task and the dissimilar points are finetuned afterwards.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Please note that all our new experiment results (i.e., the tables we quote below) and our codes can be accessed via the link \nhttps://anonymous.4open.science/r/repo-c14014\n\n**==Questions about Experiments==**\n\n**Effectiveness of the method under label corruption:** We conduct experiments under label corruption (see Table R2 in the anonymous link). Under varying levels of label corruption, our hybrid rehearsal also outperforms concurrent rehearsal, demonstrating the effectiveness of our method under label corruption.\n\n**Experiments on Tiny-Imagenet200:** Results are in Table R1 via the anonymous link. For this more complex dataset, hybrid rehearsal substantially outperforms concurrent replay. On the original dataset, hybrid rehearsal improves accuracy by 2.19% and reduces forgetting by 3.66%. On the corrupted dataset, it improves accuracy by 2.38% and reduces forgetting by 13.32%. \n\n**Add std in Table 2:** We marked standard deviation in Table R4 via the anonymous link. As can be observed, the improvement of most results are well beyond the error bars. \n\n**Impact of number of memory splits and ordering of dissimilar samples:** Thanks for the suggestion. We are currently exploring these issues with full efforts. \n\n**Improvement of CIFAR-100 is marginal compared to MNIST and CIFAR-10:** This may not be due to the more complex dataset, as our new experiment on Tiny-Imagenet200 shows significant improvement. It could be because the random selection of classes in our experiments did not have high dissimilarity among tasks. \n\n**Other questions:** In our experiments, each sample is used the **same** number of times in both hybrid and concurrent rehearsal for a fair comparison. The unit of y-axis is a scalar of 1.\n\n**==Questions about Other Issues==**\n\n**Whether objective in L186 is equivalent to $\\text{argmin} (Xw - y )^2$ plus some regularization:** The optimization objective in Line 186 comes from the convergence point of SGD on the linear model with the starting point of $w_{t-1}$ **without any regularization** [2,3,5]. This optimization is not equivalent to $\\text{argmin}_w (X^\\top w-y)^2+\\lambda \\|w\\|$ because we force $X^\\top w-y=0$ (Line 188) while $\\text{argmin}_w (X^\\top w-y)^2+\\lambda \\|w\\|$ usually leads to a non-zero $(X^\\top w-y)^2$ due to the need of balance between $(X^\\top w-y)^2$ and $\\|w\\|$. \n\n**Extension of linear model to more complex data:** A natural next step is to extend our analysis to neural networks in the NTK regime, which is effectively a linearized model. Further, our analysis of rehearsal-based CL can also integrate with recent advances in analyzing over-parameterized neural networks and attention models, to study CL under these more complex models. \n\n**Comparison to multitask learning:** Previous studies [1,4] have shown that conventional concurrent rehearsal outperforms multitask learning. We expect our method to outperform the multitask learning baseline, as it subsumes concurrent replay as a special case.\n\n**Intuition about coefficients in Theorem 5.1:** The coefficients in Theorem 5.1, which are given in (32) and (35) in appendix, suggest the following intuitions about how task ordering impacts forgetting. When memory size $M$ is small, introducing dissimilar tasks early reduces forgetting by encouraging broader feature exploration, aligning with [3] (which has $M=0$). As $M$ increases, delaying dissimilar tasks helps, since early introduction leads to frequent rehearsal, and their conflicting nature can disrupt learning of later tasks.\n\n**L 223 to 237:** $M$ and $p$ affect the theorem via the coefficients $c_i$, $c_{ijk}$, $d_{0T}$ and $d_{ijkT}$ (see Proposition B.2 in appendix).\n\n**Similarity of sequential rehearsal with Curriculum Learning:** Although they appear similar, their underlying training objectives differ significantly. In **curriculum learning**, the model is presented with data in a structured progression, typically organized by increasing difficulty, with the goal of optimizing an overall learning performance. In contrast, **sequential rehearsal** involves data drawn from different (possibly conflicting) tasks, where the model is trained by rehearsing over these tasks with a goal of mitigating forgetting. The forgetting issue is not addressed in curriculum learning.\n\nThank you for your insightful comments. We hope our responses addressed your concerns and would greatly appreciate your kind consideration in increasing your score.\n\nReference:\n\n[1] Goodfellow, et al. \"An empirical investigation of catastrophic forgetting in gradient-based neural networks.\" arXiv.\n\n[2] Gunasekar, et al. \"Characterizing Implicit Bias in Terms of Optimization Geometry.\" ICML 2018.\n\n[3] Lin, et al. \"Theory on forgetting and generalization of continual learning.\" ICML 2023.\n\n[4] Wu, Zihao, et al. \"Is multi-task learning an upper bound for continual learning?\" ICASSP 2023\n\n[5] Zhang, et al. \"Understanding deep learning requires rethinking generalization.\" arXiv 2016.", "claims_and_evidence": "- \"our hybrid approach can perform better than concurrent rehearsal and the advantage is more apparent when tasks are more dissimilar\"\nOne question I have is whether the samples are seen the same number of times in the final benchmarks, when comparing the hybrid vs the concurrent rehearsal. (i.e. Are the experiments set with training steps or epochs as a hyperparameter ?)\n\nThe following two claims are supported theoretically : \n- The first explicit closed-form expressions for the expected value of forgetting and generalization error for both concurrent rehearsal strategy and sequential rehearsal strategy under an overparameterized linear regression setting.\n- Sequential rehearsal outperforms concurrent rehearsal if tasks in CL are dissimilar, and the performance improvement is larger when the tasks are more dissimilar.", "methods_and_evaluation_criteria": "The benchmarks and metrics are the standard ones used across most CL literature.", "theoretical_claims": "I didn't check the proofs for the theoretical claims.\n\n- Could you clarify the optimisation objective in L 186, is it equivalent to argmin (X \\omega - y ) ** 2 plus some regularisation on the weights ?", "experimental_designs_or_analyses": "I reviewed all the experimental designs and analyses in the main paper.\n\nSome questions below :\n- Are the samples are seen the same number of times in the final benchmarks, when comparing the hybrid vs the concurrent rehearsal. (i.e. Are the experiments set with training steps or epochs as a hyperparameter ?)\n- In Table 2, could you add the std to conclude on the significance of the improvement ?\n- Is the method effective if the corruption is applied to the labels ?\n- L 370 : Actually I think that the task ordering for the buffer division is within scope and it would be valuable to see the improvement wrt the number of splits and the ordering of the dissimilar samples. Especially since that the improvements are not very significant in the current minimal setup. It would be valuable to see if it's because of this simplification, or if it's still the case for a more optimised buffer division and ordering.\n- Figure 2 : Could you clarify the unit of the y axis ?", "relation_to_broader_scientific_literature": "This work relates to the theoretical Continual Learning literature. Several works quantify the impact of task similarity on CF under different task, model and data assumptions : [2], [3], [4], [5], [6].\n\nAnother set of related works enforce adapt training using rehearsal samples, in order to avoid interference : [8], [9].\n\nAdditionally, the closest work to this paper is [1] which investigates rehearsal-based CL in linear models with concurrent rehearsal.\n\n- [1] Banayeeanzade, Mohammadamin et al. “Theoretical Insights into Overparameterized Models in Multi-Task and Replay-Based Continual Learning.” ArXiv abs/2408.16939 (2024): n. pag.\n- [2] Bennani, Mehdi et al. “Generalisation Guarantees for Continual Learning with Orthogonal Gradient Descent.” ArXiv abs/2006.11942 (2020): n. Pag.\n- [3] Doan, Thang Van et al. “A Theoretical Analysis of Catastrophic Forgetting through the NTK Overlap Matrix.” International Conference on Artificial Intelligence and Statistics (2020).\n- [4] Lee, Sebastian et al. “Continual Learning in the Teacher-Student Setup: Impact of Task Similarity.” International Conference on Machine Learning (2021).\n- [5] Evron, Itay et al. “How catastrophic can catastrophic forgetting be in linear regression?” ArXiv abs/2205.09588 (2022): n. Pag.\n- [6] Evron, Itay et al. “The Joint Effect of Task Similarity and Overparameterization on Catastrophic Forgetting - An Analytical Model.” ArXiv abs/2401.12617 (2024): n. pag.\n- [7] Hiratani, N. (2024). Disentangling and Mitigating the Impact of Task Similarity for Continual Learning. ArXiv, abs/2405.20236.\n- [8] Chaudhry, A., Ranzato, M., Rohrbach, M., & Elhoseiny, M. (2018). Efficient Lifelong Learning with A-GEM. ArXiv, abs/1812.00420.\n- [9] Lopez-Paz, D., & Ranzato, M. (2017). Gradient Episodic Memory for Continual Learning. Neural Information Processing Systems.", "essential_references_not_discussed": "The proposed sequential rehearsal method may share some similarities with other curriculum learning methods. I am not familiar with the literature, but It would be worth mentioning the related works in Curriculum Learning.", "other_strengths_and_weaknesses": "Strengths : \n- Clarity of the presentation and ease to follow the paper\n- Clear motivation and positioning wrt the literature\n- Informative analysis which investigates rehearsal methods which are widely used\n- Clear experiments and results\n\nWeaknesses : \n- The linear model is very simplistic and it's unclear to which extends it transfers to more complex data. \n- The results look promising on the small scale MNIST and CIFAR-10 datasets, but the improvement is marginal on the larger CIFAR-100 benchmark.\n- The proposed method is evaluated with a single split of the memory buffer. It is unclear to which extend the improvement evolves as a function of the number of splits.\n- Other comments in the other sections.", "other_comments_or_suggestions": "Suggestions : \n- Theorem 5.1 : I think it would add clarity to share an intuition about the coefficients in the interpretation below the theorem.\n- L 223 to 237 : \"By letting M = 0\", \"When p→∞\" both quantities don't appear in the form of the theorem presented in the main paper.", "questions_for_authors": "- Could the proposed method outperform the multitask learning baseline, provided the permutations of data are optimised and all the dataset is accessible at once ?\n- In Theorem 5.1, it look like the only way the task ordering may influence forgetting is through the coefficients. Could you share an intuition about how the task ordering impacts forgetting from the Theorem ?\n- Table 1 : On CIFAR-100, the improvement in CF is marginal compared to MNIST and CIFAR-10. Could it be because the data and model are more complex and further from the theoretical assumptions than the other two benchmarks ?", "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": "2ZrRyomZiF", "reviewer": "Reviewer_p4ve", "summary": "This paper explores a different scheme for rehearsal training in continual learning. It also provides theoretical framework for forgetting and generalization error of concurrent and sequential rehearsal. And the authors show under conditions where the difference between the sequential tasks is large, sequential rehearsal is provably better than concurrent rehearsal. This paper includes experimental results that verify its theory.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for providing the valuable review. Please note that all our new experiment results (i.e., the tables we quote below) and our codes can be accessed via the link https://anonymous.4open.science/r/repo-c14014\n\n\n**Q:** Are there any risks of overfitting in sequential rehearsal?\n\n**A:** We appreciate the reviewer’s question. During training, the risk of overfitting indeed exists due to the limited size of memory data. To reduce the overfitting risk, our experiment has adopted a more conservative learning rate if a ‘dissimilar task’ is learned separately, as presented in Table 3 of the paper.\n\n**Q:** About the sequential rehearsal, did you try training with the rehearsal samples for several rounds? For example, in figure 1, after training $M_{t,t-1}$, go back to train on $M_{t,1}$.  What would it be?\n\n**A:** We appreciate the reviewer’s insightful question. Despite the limited time, we made every effort to expand our experiments to train dissimilar tasks for multiple rounds, as presented in Table R3 in the anonymous link. The Averaged Final Accuracy(Acc) of multiple-round training is not changed significantly, while the Forgetting(Fgt) is slightly improved compared to single-round training. It could be because the same memory data is repeatedly learned when sequential training is conducted over multiple rounds, which may help recover more previous knowledge while introducing an unavoidable risk of overfitting.", "claims_and_evidence": "The claims are easy to understand and with rich illustration.", "methods_and_evaluation_criteria": "About the sequential rehearsal, did you try training with the rehearsal samples for several rounds? For example, in figure 1, after training $M_{t, t-1}$, go back to train on $M_{t,1}$. What would it be?", "theoretical_claims": "The theoretical claims are supported with abundant proof.", "experimental_designs_or_analyses": "The experiments and analyses are adequate.", "relation_to_broader_scientific_literature": "No", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "No", "other_comments_or_suggestions": "No", "questions_for_authors": "Are there any risk of overfitting in sequential rehearsal?", "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:

Meta-review: The paper studies the impact of rehearsal buffers in continual learning for overparametrized models. It observes an interesting phenomenon, namely that, depending on the extent of overlaps between tasks, serial rather than concurrent rehearsal is preferable: this was supported by both a theoretical analysis and experimental validation, and led to the suggestion of a new and performant continual learning algorithm.

Reviewers found these observations and the consequent algorithm interesting and worth reporting to the ICML community, while also pointing out that experimental evidence could be strengthened. In response to this, the authors included several additional experiments, including on Tiny-ImageNet200, that they are strongly encouraged to include in the final version of the paper. 

The authors should also incorporate several additional comments by the reviewers, as they have stated that they will do during the author-reviewer discussions.  The issues raised by Reviewer ptpD and satisfactorily addressed during the rebuttal period suggest corresponding edits that will help clarify the test error notion used, the proper context ([3,4]) for SGD equivalence to the constrained optimization, as well as sampling. One additional edit specifically requested by Reviewer GGhR is to add breakdown similar to Fig. 4 here in Mirzadeh et al., that reports accuracy performance on a per task basis.
Decision: Accept (poster)