A Theoretical Study on Solving Continual Learning
Authors: Gyuhak Kim
Changnan Xiao
Tatsuya Konishi
Zixuan Ke
Bing Liu
Venue: NeurIPS 2022 Accept (2022)
Keywords: Continual learning
lifelong learning

Abstract: Continual learning (CL) learns a sequence of tasks incrementally. There are two popular CL settings, class incremental learning (CIL) and task incremental learning (TIL). A major challenge of CL is catastrophic forgetting (CF). While a number of techniques are already available to effectively overcome CF for TIL, CIL remains to be highly challenging. So far, little theoretical study has been done to provide a principled guidance on how to solve the CIL problem. This paper performs such a study. It first shows that probabilistically, the CIL problem can be decomposed into two sub-problems: Within-task Prediction (WP) and Task-id Prediction (TP). It further proves that TP is correlated with out-of-distribution (OOD) detection, which connects CIL and OOD detection. The key conclusion of this study is that regardless of whether WP and TP or OOD detection are defined explicitly or implicitly by a CIL algorithm, good WP and good TP or OOD detection are necessary and sufficient for good CIL performances. Additionally, TIL is simply WP. Based on the theoretical result, new CIL methods are also designed, which outperform strong baselines in both CIL and TIL settings by a large margin.

A Theoretical Study on Solving Continual Learning
Gyuhak Kim* Changnan X Tatsuya Konishit Zixuan Ke', Bing Liu University Illinois at Chicago
ByteDance KDDI Research
Abstract
Continual learning (CL) learns a sequence of tasks incrementally. There are two popular CL settings, class incremental learning (CIL) and task incremental learn- ing (TIL). A major challenge of CL is catastrophic forgetting (CF). While several techniques are available to effectively overcome CF for TIL, CIL remains be challenging due to the additional difficulty of inter-task class separation. So far little theoretical work has been done provide a principled guidance and neces- sary and sufficient conditions for solving the CIL problem. This paper performs such study. It first probabilistically decomposes the CIL problem into two sub- problems: within-task prediction (WP) and task-id prediction (TP). It further proves that TP correlated with out-of-distribuution (OOD) detection. The key result is that regardless of whether WP and TP or OOD detection are defined explicitly or implicitly by CIL algorithm, good WP and good TP or OOD detection are necessary and sufficient for good CIL performances. Additionally, TIL is simply WP. Based on the theoretical result, new CIL methods are also designed, which outperform strong baselines in both CIL. and TIL. settings by large margin
1 Introduction
Continual learning aims to incrementally learn sequence of tasks [I] Each task consists of a set of classes be learned together. A major challenge of CL is catastrophic fotastrophiccorgettton large number of CL techniques have been proposed, they are mainly empirical. Limited theoretical research has done how to solve CL. This paper performs such theoretical study about the necessary and sufficient conditions for effective CL. There are two main CL. settings that have been extensively studied: class incremental learning (CIL) and task incremental learning (TIL) [2]. In CIL, the learning process builds single classifier for all tasks/classes learned so far. In testing, test instance from any class may be presented for the model classify. No prior task information (c.g.. task-id) of the test instance is provided. Formally, CIL is defined as follows.
(CF). Although
Class incremental learning (CIL). CIL learns a sequence of tasks, 1, 1. T. Each task & has training dataset Dx = {(rk v 1 where n& is the number of data samples task i and zj. E X is an input sample and y E Ys (the set of all classes task k)) is its class label. All Y 's are disjoint (Y n Y 0, vk + k') and U YA Y. The goal of CIL is to construct single predictive function or classifier ʃ X
that can identify the class label y of each given test instance x.
In the TII. setup, each task a separate classification problem. For example, one task could be to classify different breeds of dogs and another task could be to classify different types of animals (the
"qqual contribution
The work was done when this author was visiting Bing Liu's group University of Illinois at Chicago *Correponnaacee author. Bing Liu <liub@uic. edu> eduu>
"The code is available at al/ttps://giithb com/k k- WWPP
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

tasks may not be disjoint). One model is built for each task in shared network. In testing, the task-id of each test instance is provided and the system uses only the specific model for the task (dog or animal classification) to classify the test instance. Formally, TIL. is defined as follows.
Task incremental learning (TTL). TIL learns a sequence of tasks, 1, .,2,,.., T. Each task k has training dataset D {((2), k), yk))=ih where ny is the number of data samples in task k E T = (1.2....,7) T). and 2 E X is an input sample and v E Y C Y is its class label. The goal of TIL is to construct a predictor f X x T Y to identify the class label y E Y2 for (z, k) (the given test instance v from task k))
Several techniques are available to effectively overcome CF for TIL (with almost no CF) 3 However, CIL remains to be highly challenging due to the additional problem of Inter-task Class Separation (ICS) (establishing decision boundaries between the classes of the new task and the classes of the previous tasks) because the previous task data are not accessible. To our knowledge, the ICS problem has not been discussed before but it is critical for the success of CIL. Before discussing the proposed work, we recall the closed-world assumption made by traditional machine learning, i.e., the classes seen in testing must have been seen in training 5 However, in many applications, there are unknowns in testing, which is called the open world setting 31. In open world learning, the training (or known) classes called in-distributiio (IND) classes. A classifier built for the open world can (1) classify test instances of training/IND. classes to their respective classes, which is called IND prediction, and (2) detect test instances that do not belong to any of the IND/known classes but some unknown or out-of-distribution Many OOD detection algorithms can perform both IND prediction and OOD detection 66 7 g The commonality of OOD detection and CIL is that they both need to consider future unknowns.
(OOD) classes, which is called OOD detection.
This paper conducts theoretical study of CIL, which is applicable to any CIL classification model. Instead of focusing on the traditional PAC generalization bound [10 [1. we focus on how to solve the CIL problem. We first decompose the CIL problem into two sub-problems in probabilistic framework: Within-task Prediction (WP) and Task-id Prediction (TP). WP means that the prediction for a test instance is only done within the classes of the task to which the test instance belongs, which is basically the TIL. problem. TP predicts the task-id. TP is needed because in CIL,, task-id is not provided in testing. This paper then proves based on the popular cross-entropy loss that (1) the CIL performance is bounded by WP and TP performances, and (2) TP and task OOD detection performance bound each other (which connects CL and OOD detection). The key result is that regardless of whether WP and TP or OOD detection are defined explicitly or implicitly by CIL algorithm, good WP and good TP or OOD detection are necessary and sufficient conditions for good CIL performances. This result is applicable to both batch/ofiline and online CIL and to CIL problems with blurry task boundaries. The intuition is also quite simple because if CIL model is perfect at detecting OOD samples for each task (which solves the ICS problem), then CII. is reduced to WP.
This theoretical result provides a principled guidance for solving the CII. problem, i.e., to help design better CIL algorithms that can achieve strong WP and TP performances. Since WP is basically IND prediction for each task and most OOD techniques perform both IND prediction and OOD detection, to achieve good CIL accuracy, a strong OOD performance for each task is necessary.
Based on the theoretical guidance, several new CIL methods designed, including techniques based on the integration of a TIL method and an OOD detection method for CIL, which outperform strong baselines in both the CIL and TIL settings by large margin. This combination is particularly attractive because TIL has achieved no forgetting, and we only need a strong OOD technique that can perform both IND prediction and OOD detection learn each task to achieve strong CII. results.
2 Related Work
Although numerous CL techniques have been proposed, little theoretical work has been done on how to solve CL. Existing methods are mainly empirical and belong to several categories. Using regularization [12 B to minimize changes to model parameters learned from previous tasks is a
popular approach [1] [5]
16,
17 [8
19
20 21 22 23 24
25 26 Memorizing some old examples
and using them to jointly train the new task is another popular approach (called replay) [2 28 29
30 31
Some systems learn to generate pseudo training data of old tasks to be used in replay, called pseudo-replay
35 36
37
38
39
40
41
46
48). Orthogonal
projection learns each task in an orthogonal space to other tasks 49
50
51

---

Parameter isolation is yet another popular approach, which makes different subsets (which may overlap) of the network parameters dedicated different tasks using masks [3] 52
53 4 [5]] This
approach is particularly suited for TIL. Several methods have almost completely overcome forgetting.
HAT 3 and CAT
[22 protect previous tasks by masking the important parameters to those tasks.
PackNet 53 CPG (54] and SupSup 4 find an isolated sub-network for each task. HyperNet (55]
initializes task-specific parameters conditioned on task-id. ADP [56] decomposes parameters into shared and adaptive parts to construct order robust TIL system. CCLL [57] uses task-adaptive calibration in convolution layers. Our methods designed based on the proposed theory make use of two parameter isolation- based TIL methods and two OOD detection methods. A strong OOD detection method CSI in [6] helps produce very strong CIL results. CSI is based on data augmentation [58] and contrastive learning [59]. Excellent surveys of OOD detection include [60 61].
Some methods have used a TII. method for CIL, with an additional task-id prediction technique. ITAMIL [62 requires each test batch to be from single task. This is not practical as test samples usually come one by one. CCG (63] builds a separate network to predict the task-id. Expert Gate [64 constructs separate autoencoder for each task. HyperNet [55] and PR-Ent 665] use entropy to predict the task id. Since none of these papers a theoretical study, they did not know that strong OOD detection is the key. Our methods based on OOD detection perform dramatically better.
Several theoretical studies have been made on lifelong/continual learning. However, they focus on traditional generalization bound. [10] proposes a PAC-Bayesian framework to provide a learning bound on expected error in future tasks by the average loss on the observed tasks. The work in [66] studies the generalization error by task similarity and [11] studies the dependence of generalization error on sample size or number of tasks including forward and backward transfer. [67] shows that
orthogonal gradient descent gives a tighter generalization bound than SGD. Our work is very different
as we focus on how to solve the CIL problem, which is orthogonal to the existing theoretical analysis.
3 CIL by Within-Tan Task Prediction and Task-ID Prediction
This section presents our theory. It first shows that the CIL performance improves if the within-task prediction (WP) performance and/or the task-id id prediction (TP) performance improve, and then shows that TP and OOD detection bound each other, which indicates that CIL performance is controlled by WP and OOD detection. This connects CL and OOD detection. Finally, we study the necessary conditions for a good CIL model, which includes good WP, and good TP (or OOD detection).
3.1 CIL Problem Decomposition
This sub-section first presents the assumptions made by CIL based on its definition and then proposes a decomposition of the CIL problem into two sub-problems. A CL system learns a sequence of tasks {(X,, }=)),=,,....r where X, is the domain of task k and Y2 & are classes of task & as Y, (Yv.j where j iidicates the jth class in task k. Let XR. to be the domain of jth class of task k, where X = U, Xk.j. For accuracy, we will use x E Xk.j instead of Yk.j in probabilistic analysis. Based on the definition of class incremental learning (CIL) (Sec. the following assumptions are implied, Assumption 1. The domains of classes of the same task are disjoint, i.e., Xx.5 XX..s' = 0. $J Assumption 2. The domains tasks are disjoint, i.e., Xx n X = 0, Vk + k'.
For any ground event D, the goal of a CIL problem is to learn P(T E D). This can be decomposed into two probabilities, within-task IND prediction (WP) probability and fask-id prediction (TP) probability. WP probability is P(z E Xk.5læ E Xt, D) and TP probability is P(r E D). We can rewrite the CIL problem using WP and TP based on the two assumptions,
P(r E X = Σ P(x E Xk. (o E XR, D)P(2 E Xx(D)
(1)
k=1.....
=P( E Xio Ix E X D)P X
(2)
where ko means particular task and ju particular class in the task.
Some remarks are in order about Eq. 2 and our subsequent analysis to set the stage.
Remark 1. Eq. 2 shows that if we can improve either the WP or TP performance, or both, we can improve the CIL performance.
3

---

Remark 2. is important to note that our theory is not concerned with the learning algorithm or the training process, but we will propose some concrete learning algorithms based on the theoretical result in the experiment section.
Remark 3. Note that the CIL definition and the subsequent analysis are applicable to tasks with any number of classes (including only one class per task) and to online CIL where the training data for each task or class comes gradually in a data stream and may also cross task boundaries (blurry tasks [68]) because our analysis is based on an already-built CIL model after training. Regarding blurry task boundaries, suppose dataset 1 has classes (dog, cat, tiger) and dataset 2 has classes (dog, computer, car). We can define task as [dog, cat, tiger) and task as (computer, car). The shared class dog in dataset 2 is just additional training data of dog appeared after task 1.
Remark 4. Furthermore, CIL= WP TP in Eq. 2 means that when we have WP and TP (defined either explicitly or implicitly by implementation), we can find corresponding CIL model defined by WP * TP. Similarly, when we have CIL model, we can find the corresponding underlying WP and TP defined by their probabilistic definitions.
In the following sub-sections, develop this further concretely derive the sufficient and necessary conditions for solving the CIL. problem in the context of cross-entropy loss as it is used in almost all supervised CL systems.
3.2 CIL. Improves WP and/or TP Improve
As stated in Remark 2 above, the study here is based on a trained CIL model and not concerned with the algorithm used in training the model. We use cross- tross-entropy as the performance measure of a trained model as it the most popular loss function used in supervised CL. For experimental evaluation, we use accuracy following CL. papers. Denote the cross-entropy of two probability distributions p and q as
H (p. def EEploo 9) = Ep:
-101---pp log
(3)
For any E X. let y to be the CIL ground truth label of where yho = 1 E X do otherwise
yk.j = 0. ((k, * (ko. jo). Let ÿ be the WP ground truth label of x. where Too.jo = x E X
Xto.jo
otherwise Dko.j 0, vj + ju- Let ÿ be the TP ground truth label of x, where Uko 1 if X ko
otherwise Dk = 0, vk + kg. Denote
Hwp(x (1, (P(x E Xtos lor E X D)},,
Hc)((x) = H (P(x E D))s)) HTP(#) Hi, E (D))))
(5)
where HwP. HoI and HTP are the cross-entropy values of WP, CIL and TP, respectively. We now present our first theorem. The theorem connects CIL WP and TP, and suggests that by having good WP or TP, the CIL performance improves as the upper bound for the CIL loss decreases. Theorem 1. If Hrr(z) I 5 and Hw)) $ c, we have HCIL(I) c 8.
The detailed proof is given in Appendix A.1. This theorem holds regardless of whether WP and TP are trained together or separately. When they are trained separately, if WP is fixed and we let <= Hw (()). HCIL(z) (x) S Hw)(x) + 6, which means if TP is better, CIL is better. Similarly, TP is fixed, we have HELL (z) S Hrr((r) When they are trained concurrently, there exists a functional relationship between c and depending on implementation. But no matter what it is, when
c 8 decreases, CIL gets better.
Theorem holds for any I E x Xx that satisfies HTP(x) S 8 or Hwr(x) S e. To measure the overall performance under expectation, we present the following corollary.
Corollary 1. Let (X) represents the uniform distribution X. If Ex)x S 8, then E Ex) (H))(()) (z) < ((w + S. Similarly, ii) Ex-U(X) (wP & then (Ho.
(x)-U())HHIIZ(1) < e - EL-U(x) (=--U(x((ETp(])) [H))
The proof is given in Appendix A.2. The corollary is direct extension of Theorem in expectation. The implication is that given TP performance, CIL is positively related to WP. The better the WP is, the better the CIL is as the upper bound of the CIL loss decreases. Similarly, given WP performance, a better TP performance results in a better CII, performance. Due to the positive relation, we can improve CIL by improving either WP or TP using their respective methods developed in each area.

---

3.3 Task Prediction (TP) to OOD Detection
Building on Eq. 2 we have studied the relationship CIL, WP and TP Theorem We now connect TP and OOD detection. They are shown to be dominated by each other to constant factor.
We again use cross-entropy H measure the performance of TP and OOD detection of a trained network as in Sec. 3.2 To build the connection between Hrp(z) (x) and OOD detection of each task, we first define the notations of OOD detection. We use P (a X3. D) represent the probability distribution predicted by the kth task's OOD detector. Notice that the task prediction (TP) probability distribution P(x E X D)) is a categorical distribution over T tasks, while the OOD detection probability distribution P (z E Xx) is a Beroulli distribution. For any E X, define
(O)D,<(z) (1, P (a D)) (O, (a E Xx D))
log Pk (2 E DD log (x & Xx D), X
X
(7)
In CIL, the OOD detection probability for task can be defined using the output values corresponding to the classes of the task. Some examples of the function is sigmoid of maximum logit value or also possible define the OOD detector
maximum softmax probability after re-scaling to to directly as function of tasks instead of a function of the output values of all classes of tasks, i.e. Mahalanobis distance. The following theorem shows that TP and OOD detection bound each other.
Theorem 2. i) 1f Hr)(x) S 6, let P/(22 X D) = P(x E X (D), then HOOD, (2) S 6, Pl PL(EE..1D 1....,T. T. ü) If HOOD,(()) ōk, 1...., T, let P(x E Xx|D) Σ. P((Ex,, then Hrp(z) s
1- e E-)), where 1 is an indicator funciiion B )
See Appendix A.3 for the proof. As we use cross-entropy, the lower the bound, the better the performance is. The first statement (i) says that the OOD detection performance improves the TP performance gets better (i.e., lower 8). Similarly, the second statement (ii) says that the TP performance improves if the OOD detection performance on each task improves (i.e., lower 6g). Besides, since (Σ E (E k 1 e -62) converges to 0 as 5g 's converge to 0 in order of O. (x(), we further know that HTP and Σn HOOD, are equivalent in quantity up to a constant factor.
In Theorem studied how CIL is related to WP and TP. In Theorem 2 showed that TP and OOD bound each other. Now we explicitly give the upper bound of CIL in relation to WP and OOD detection of each task. The detailed proof can be found Appendix A.4.
Theorem 3. If HOOD,(()) S OR k L...., and Hw (x)) S 6, we have
Hen Sct E L1ex )0) Σ 1-
k
where Izex, is an indicator function.
3.4 Necessary Conditions for Improving CIL.
In Theorem] we showed that good performances of WP and TP are sufficient to guarantee a good performance of CIL. In Theorem showed that good performances of WP and OOD are sufficient to guarantee a good performance of CIL. For completeness, we study the necessary conditions of a well-performed CIL in this sub-section.
Theorem 4. If HCIL(x) < n, then there exist i) WP, s.t. Hаr(()) < n, ti) TP, s.t. HTP(z) S and úii an OOD detector for each task, s.t. HOOD S 17, k = I..
The detailed proof is given in Appendix A.5. This theorem tells that if good CIL model is trained, then a good WP, good TP and good OOD detector for each task are always implied. More importantly, by transforming Theorem iinto its contraposition, we have the following statements: If for any WP, Hw (x) > n, then (x)L(x) > If for any TP, (x)(x) > 17, then (zι > n. If for any OOD detector, (Oona(() > 1,, k = 1, ..... T, then Herr.( (2:) > 1). Regardless of whether WP and TP (or OOD detection) are defined explicitly of good WP and the existence of a good TP or OOD detection are necessary conditions for good CIL performance.
implicitly by CIL algorithm, the existence
5

---

Remark 5. It is important to note again that our study in this section is based on a CIL model that has already been built. In other words, our study tells the CIL designers what should be achieved in the final model. Clearly, one would also like to know how to design a strong CII. model based on the theoretical results, which also considers catastrophic forgetting (CF). One effective method is to make use of strong existing TIL. algorithm, which can already achieve no or little forgetting (CF), and combine it with a strong OOD detection algorithm (as mentioned earlier, most OOD detection methods can also perform WP). Thus, any improved method from the OOD detection community can be applied to CIL to produce improved CIL systems (see Sections 4.3 and 4.4p.
we reviewed prior works that have tried to use TIL method for CIL with a task-id prediction method [55] 64 62 63 65]. However, since they did not know that the key to the success of this approach is a strong OOD detection algorithm, they are quite weak (see Section[4).
Recall in Section 2
4 New CIL Techniques and Experiments
Based on Theorem we have designed several new CIL methods, each of which integrates an existing CL algorithm and an OOD detection algorithm. The OOD detection algorithm that we use can perform both within-task IND prediction (WP) and OOD detection. Our experiments have two goals: (1) to show that a good OOD detection method can help improve the accuracy of an existing CIL algorithm, and (2) to fully compare two of these methods (see some others in Sec. [455 with strong baselines to show that they outperform the existing strong baselines considerably.
4.1 Datasets, CL Baselines and OOD Detection Methods
Datasets and CIL. Tasks. Four popular benchmark image classification datasets are used, from which
six CIL. problems are created following recent papers [25, 34 26]. (1) MNIST consists of handwritten
images of 10 digits with 60,000/10,000 training/testing samples. We create CIL problem (M-5T) of 5 tasks with 2 consecutive classes/digits as a task. (2) CIFAR-10 consists of 32x32 color images of 10 classes with 50,000/10,000 0,,00 training/testing samples. We create a CIL problem (C10-5T) of tasks with 2 consecutive classes as task. (3) CIFAR-100 consists of 60,000 32x32 color images with 50,00 50,000/10,00x training/testinn samples. We create two CIL problems by splitting 100 classes into 10 tasks (C100-10T) and 20 tasks (C100-20T), where each task has 10 and 5 classes, respectively. (4) Tiny-ImageNee has 120,000 64x64 color images of 200 classes with 500/50 images per class for training/testing. We create two CIL problems by splitting 200 classes into 5 tasks (T-5T) and 10 tasks (T-10T), where each task has 40 and 20 classes, respectively.
Baseline CL Methods. We include different families of CL methods: regularization, replay, orthogonal projection, and parameter isolation. MUC (25) and PASS (26) are regularization-basde
methods. For replay methods, we use LwF [13], iCaRL 229] Mnemonics (6) BiC [32], DER++ [34],
Finally, for parameter isolation, we use CCG 63 HyperNet (55), HAT (3), SupSup 4 (Sup), and PR 65 We use the official codes for the baselines except for Co CCG, and PR. For these three systems, we copy the results from their papers as the code for CCG is not released and we are unable to run L and PR on our machines.
and C 37,. For orthogonal projection, we use OWM 49
OOD Detection Methods. Two OOD detection methods are used. We combine them with the above existing CL algorithms. Both these methods can also perform within-task IND prediction (WP).
(1). ODIN: Researchers have proposed several methods to improve the OOD detection performance of a trained network by post-processing 7 70 71). ODIN 7 is a representative method. It adds perturbation to input and applies a temperature scaling to the softmax output of a trained network.
(2). CSI: It is recently proposed OOD detection technique (6] that is highly effective. It is based on data and class label augmentation and supervised contrastive learning 72.. Its rotation data
'ITAML 622 is not included as requires batch of test data from the same task to predict the task-id. When each batch has only one test sample, which is our setting, it is very weak. For example, its CIL accuracy is only 33.5% on C100-10T. Expert Gate (EG) [44] is also very weak. Its CIL accuracy is only 43.2 on M-ST. They are much weaker than many baselines. DER 38 is not included as it expands the network after each task, which is somewhat unfair to other systems as all others do not expand the network. DER can generate large number of parameters after the last task, e.g., 117.6 6 millions (M) for C100-20T while our proposed methods require 44.6M (HAT+CSI) and 11.6M (Sup+CSI) (refer to Appendix H). The average accuracy of DER over the 6 CL experiments is 61.4 while our methods achieve 67.9 (HAT+CSI+c) and 64.9 (Sup+CSI+cc) (refer to Tab. B).

---

augmentations create distributional shifted samples to act as negative data for the original samples for contrastive learning. The details of CSI is given in Appendix D.
4.2 Training Details and Evaluation Metrics
Training Details, For the backbone structure, we follow 4
26 34
AlexNet-like architecture
73
is used for MNIST and ResNet-18 774 is used for CIFAR-10. For CIFAR- 100 and Tiny-Imagell
ResNet-18 is also used as CIFAR-I0, but the number of channels are doubled to fit more classes. All the methods use the same backbone architecture except for OWM and HyperNet, for which use their original architectures. OWM uses AlexNet. It is not obvious how to apply the technique to the ResNet structure. HyperNet uses fully-connected network and ResNet-32 for MNIST and other datasets, respectively. We are unable to change the structure due to model initialization arguments unexplained in the original paper. For the replay methods, we use memory buffer 200 for MNIST and CIFAR-10 and 2000 for CIFAR-100 and Tiny-ImageNV as in 29 34 We use the hyper-paramen parameters suggested by the authors. If we could not reproduce any result, we use 10% of the training data as a validation set to grid-search for good syper-parameters. For our proposed methods, we report the prper-parameters in Appendix G. All the results are averages over 5 runs with random seeds.
Evaluation Metrics.
(1), Average classification accuracy over all classes after learning the last task. The final class prediction depends prediction methods (see below). We also report forgetting rate in Appendix J.
(2). Average AUC (Area Under the ROC Curve) over all task models for the evaluation of OOD detection. AUC is the main measure used in OOD detection papers. Using this measure, we show that a better OOD detection method will result in better CIL performance. Let AUC, be the AUC score of task k. It is computed by using only the model (or classes) of task ie to score the test data of task i as the in-distribution (IND) data and the test data from other tasks as the out-of-distributie (OOD) data. The average AUC score is: AUC = E. AUCx/Mr /n, where n is the number tasks.
It is not straightforward to change existing CL algorithms to include a new OOD detection method that needs training, e.g., CSI, except for TIL (task incremental learning) methods, e.g., HAT and Sup. For HAT and Sup, we can simply switch their methods for learming each task with CSI (see See 4.4).
Prediction Methods. The theoretical result in Sec. 3 states that we use Eq. 2 to perform the final prediction. The first probability (WP) in Eq. is easy to get as we can simply use the softmax values of the classes in each task. However, the second probability (TP) in Eq. 2 is tricky as each task is learned without the data of other tasks. There can be many options. We take the following approaches for prediction (which a special case of Eq. 2 see below):
(1). For those approaches that use a single classification head to include all classes learned so far, we predict as follows (which is also the approach taken by the existing papers.)
arg max (x:
where (ax is the logit output of the network.
(2). For multi-head methods (e.g.. HAT, HyperNet, and Sup), which use one head for each task, we use the concatenated output as
g = arg max + f(z)x
where + indicate concatenation and f()) is the output of task k
These methods (in fact, they are the same method used in two different settings) a special case of Eq. if we define OODa Da. as a (max (x))),, where o is the sigmoid. Hence, the theoretical results in Sec. 3 are still applicable. We present a detailed explanation about this prediction method and some other options in Appendix C. These two approaches work quite well.
'The Sup paper proposed an one-shot task-id prediction assuming that the test instances come in batch and all belong to the same task like ITAML. We assume single test instance per batch. Its task-id prediction results in accuracy of 50.2 on C10-5T, which is much lower than 62.6 by using Eq. The task-id prediction of HyperNet also works poorly. The accuracy by its id prediction is 49.34 on C10-ST while it is 53.4 using Eq, 9 PR uses entropy to find id. Among many variations of PR, we use the variations that perform the best for each dataset with exemplar free and single sample per batch at testing (i.e., PR-BW).
7

---

4.3 Better OOD Defection Produces Better CIL Performance
The key theoretical result Sec. 3 is that better OOD detection will produce better CIL performance. Recall our considered methods ODIN and CSI can perform both WP and OOD detection.
Applying ODIN. We first train the bascline models using their original algorithms, and then apply temperature scaling and input noise of ODIN at testing for each task (no training data needed). More precisely, the output of class in task l changes by temperature scaling factor 7he of task k: as
s(;; Tk)
Ma)ass/ Σ (a0asa
(10)
and the input changes by the noise factor ej as
I = r exsign( V. log s(z;
(11)
where 9 is the class with the maximum output value in task k. This is positive adversarial example inspired by [75]. The values тыe and ég are hyper-parann parameters and we use the same values for all tasks except for PASS, for which we had to use validation set to tune т (see Appendix B).
Tab. [ gives the results for C100-10T. The CIL results clearly show that the CIL performance increases if the AUC increases with ODIN. For instance, the CIL of DER++ and Sup improves from 53.71 to 55.29 and 44.58 to 46.74, respectively, as the AUC increases from 85.99 to 88.21 and 79.16 to 80.58. shows that when this method is incorporated into each task model in exist- ing trained CIL network, the CIL performance of the original method improves. We note that ODIN does not always improve the average AUC. For those experienced decrease in AUC, the CIL performance also decreases except LwF. The inconsistency of LwF is due to its se- vere classification bias towards later tasks as discussed in BiC 32. The temperature scaling in ODIN has a
Table I: Performance comparison based on C100-10T between the original out- put and the output post-processed with OOD detection technique ODIN. Note that ODIN is not applicable to iCaRL and Mnemonics as they are not based on soft- max but some distance functions. The results for other datasets are reported in Appendix B.
Method OOD
AUC
CIL
Original
71.31
28.91
OWM
ODIN
70.06
28.88
Original
72.69
30.42
similar effect the bias correction in BiC, and the CIL. of LwF becomes close to that of BiC after the correction. Regardless of whether ODIN improves AUC or not, the positive correlation between AUC and CIL (except LwF) verifies the efficacy of Theorem 3 indicating better OOD detection results in better CIL performances.
MUC
ODIN
72.53
29.79
Original
69.89
33.00
PASS
ODIN
69.60
31.00
Original
88.30
45.26
LWF
ODIN
87.11
51.82
Original
87.89
52.92
BIC
Applying CSL We method CSI. Due to its sophisticated data augmentation, supervised constrative learning and results ensemble, it hard to apply CSI to other baselines without fundamen- tally change them except for HAT and Sup (SupSup) as these methods are parameter isolation-basee TIL meth- ods. We can simply replace their model for training each task with CSI wholesale (the full detail is given in Ap- pendix D). As mentioned earlier, both HAT and SupSup as TIL methods have almost no forgetting.
apply the OOD detection
ODIN
86.73
48.65
Original
85.99
53.71
DER+
ODIN
88.21
55.29
Original
77.72
41.06
HAT
ODIN
77.80
41.21
Original
71.82
30.23
HyperNet
ODIN
72.32
30.83
Original
79.16
44.58
Sup
ODIN
80.58
46.74
Tab. reports the results of using CSI and ODIN. ODIN is weaker OOD method than CSI. Both
HAT and Sup improve greatly as the systems are equipped with a better OOD detection method CSI. These experiment results empirically demonstrate the efficacy of Theorem i.e., the CII. performance can be improved if a better OOD detection method is used.
4.4 Full Comparison of HAT+CSI and Sup+CSI with Baselines
We now make a full comparison of the two strong systems (HAT+CSI and Sup+CSI) designed based on the theoretical results. These combinations are particularly attractive because both HAT and Sup are TIL. systems and have little no CF. Then a strong OOD method (that can also perform WP Wwithin-task/IND prediction) will result in strong CII. method. Since HAT and Sup are exemplar- free CL methods, HAT+CSI and Sup+CSI also do not need any previous task data. Tab.
8

---

Table 2: Average CIL and AUC HAT and Sup with OOD detection methods ODIN and CSL ODIN is traditional OOD detection method while CSI is a recent OOD detection method known to be better than ODIN. As CL methods produce better OOD detection performance by CSI, their CIL. performances are better than the ODIN counterparts.
CL
OOD
C10-5T
C100-10T
C100-20T
T-ST
T-1OT
AUC
CII
AUC
CII
AUC
CII.
AUC
CIL.
AUC
CIL.
ODIN
82.5
62.6
77.8
41.2
75.4
25.8
72.3
38.6
71.8
30.0
HAT
CSI
91.2
87.8
84.5
63.3
86.5
54.6
76.5
45.7
78.5
47.1
ODIN
82.4
62.6
80.6
46.7
81.6
36.4
74.0
41.1
74.6
36.5
Sup
CSI
91.6
86.0
86.8
65.1
88.3
60.2
77.1
48.9
79.4
45.7
Table 3: Average accuracy after all tasks are learned. Exemplar-fre methods are italicized. indicates that in their original papers, PASS and Mnemonics are pre-trained with the first half of the classes. Their results with pre-train are 50.1 and 53.5 on C100-10T, respectively, which are still much lower than the proposed HAT+CSI and Sup+CSI without pre-training. We do not use pre-training in our experiment for fairness. indicates that iCaRL and Mnemonics report average incremental accuracy in their original papers. We report average accuracy over all classes after all tasks are Iearned.
Method
M-5T
C10-5T
C100-10T
C100-20T
T-ST
T-10T
OWM
95.8+
51.810005
28.94:..0
24.1
10.0
8.6=0.42
MUC
74.910.46
52.911.03
30.411.18
14.2:0.30
33.6.10.19
17.410.17
PASSI
76.611.67
47.310.98
33.011.58
25.0110.99
28.410.51
19.110.46
LWF
85.5+3.11
54.7+1.18
45.3+0075
44.3+00.6
32.2+0.50
24.3++0.6
iCaRL.*
96.0+0.43
63.4+1.11
51.4+0.99
47.8+0.48
37.0+0041
28.3+0.18
Mnemonics
96.3+0036
64.1
51.0+:0.4
47.6100.4
37.1+0.46
28.5
BIC
94.1
61.4
52.9+0.64
48.9+0.54
41.7+10.4
33.8=0.40
DER+
95.3+0.69
66.0+1.20
53.7+1..0
46.6+1.44
35.8+0.77
30.5=0.47
Co
65.6
CCG
97.3
70.1
HAT
81.943.74
62.7+1144
41.1+00.3
25.6+00.1
38.5+1.85
29.8+0.65
HyperNet
56.611..85
53.4:2.11
3..2
18.7#1.10
7.910.69
5.310.50
Sup
70.1
62.4::145
44.6::0.44
34.710.30
41.8+11.50
36.5+1036
PR-Ent
74.1
61.9
45.2
HAT+CSI
94.4+:022
87.8+0.71
63.3+1.00
54.610092
45.7+0.26
47.1
Sup+CSI
80.7+2.71
86.0+0.41
65.1
60.2+0.51
48.9+0.25
45.7=0.76
+AT+CSI+c
96.9+00.0
88.0+0048
65.2+0.71
58.0+0045
51.7++0.7
47.6+0.32
Sup+CSI+e 81.0112.0
87.310.37
65.2.10.7
60.510.64
49.210.28
46.2+1..3
shows that HAT and Sup equipped with CSI outperform the baselines by large margins. DER++, the best replay method, achieves 66.0 and 53.7 on C10-5T and C100-10T, respectively, while HAT+CSI achieves 87.8 and 63.3 and Sup+CSI achieves 86.0 and 65.1. The large performance gap remains consistent in more challenging problems, T-5T and T-1OT. We note that Sup works very poorly on M-5T, but Sup+CSI improved it drastically, although still very weak compared to HAT+CSI.
Due to the definition OOD the prediction method and the fact that each task trained separately in HAT and Sup, the outputs (()), from different tasks can be in different scales, which will result in incorrect predictions. To deal with the problem, we can calibrate the output as dr ar f(x)x + 88 and use OOD; (ax (au f()) + B&). The optimal at and 37 for each task can be found by optimization with memory buffer to save a very small number of training examples from previous tasks like that in the replay-based methods. We refer the calibrated methods as HAT+CSI+c and Sup+CSI+c. They are trained by using the memory buffer of the same size as the replay methods (see Sec. 4.2). Tab. shows that the calibration improves from their memory free versions, i.e., without calibration. We provide the details about how to train the calibration parameters ag and 83 in Appendix E.
As shown in Theorem T the CIL performance also depends on the TIL (WP) performance. We compare the TH. accuracies the baselines and our methods in Tab, 4 Our systems again outperform the basclines by large margins more challenging datasets (e.g.. CIFAR100 and

---

Table 4: TIL (WP) results of best performing baselines and our methods. The full results are given in Appendix F. The calibrated versions (+c) of our methods are omitted as calibration does not affect TIL. performances.
Method
M-5T
C10-5T
C100-10T
C100-20T
T-5T
T-10T
DER++ 99.7+0008
92.0=0.54
84.0#9943
86.6+9.44
1..4
60.0+0.74
HAT
99.9+0002
96.7=0.18
84.0=0023
85.0++0.8
61.2++0.2
63.8+0.41
Sup 99.6110.01
96.6=0.21
87.910.27
91.6110.15
64.3110.4
68.4410.2
HAT+CSI
99.9+00.00
98.7-0.06
92.0++0.37
94.3++0.06
68.4+-016
72.440.21
Sup+CSI
99.0+0008
98.7=0.07
93.0+-0.13
95.3++0.20
65.9++025
74.1++028
4.5 Implications for Existing CL Methods, Open-World Learning and Future Research
Implication for regularization and replay methods. Regularization-basee (exemplar-fiee ffree) methods try to protect important parameters of old tasks to mitigate CF. However, since the training of each task does not consider OOD detection, TP will be weak, which causes difficulty for inter-task class separation (ICS) and thus low CL accuracy. Replay-based methods are better as the replay data from old tasks can be naturally regarded OOD data for the current task, then better OOD model is built, which improves TP. However, since the replay data is small. the OOD model is sub-optimal, especially for earlier tasks as their training cannot see any future task data. For both approaches, will be beneficial to consider CF and OOD together in learning each task (e.g., (76)..
Implication for open-world learning. Since theory says that CL needs OOD detection, and OOD detection is also the first step in open-world learning (OWL), CL and OWL are unified to form the self- motivaaoivdd open-world continual learning [5] for learning or Al autonomy. That is, the AI agent can continually discover new tasks (OOD detection) and incrementally learn the tasks (CL) (see (76) all on its own with no involvement of human engineers 5) Further afield, this work is also related to curiosity-driven self-supervised learning in reinforcement learning and 3D navigation.
Limitation and future work. The proposed theory provides principled guidance what needs to be done in order to achieve good CIL results, but it gives no guidance on how to do it. Although two example techniques are presented and evaluated, they are empirical. There are many options to define WP and TP (or OOD). An idea in [40] may be helpful in this regard. [40] argues that a continual learner should learn holistic feature representations of the input data, meaning learn as
many features as possible from the input data. The rationale is that if the system can learn all possible features from each task, then future task does not have to learn those shared/intersecting features by modifying the parameters, which will result in less CF and also better ICS. A full representation of the IND data also improves OOD detection because the OOD score of data point is basically the distance between the data point and the IND distribution. Only capturing a subset of features (e.g.. by cross entropy) will result in poor OOD detection 78 because those missing features may be necessary to separate IND and some OOD data. In our future work, we will study how to optimize WP and TP/OOD and find the necessary conditions for them do well.
5 Conclusion
This paper proposed a theoretical study on how to solve the highly challenging continual learning (CL) problem. class incremental learning (CIL) (the other popular CL setting is task incremental learning (TIL)). The theoretical result provides a principled guidance for designing better CIL algorithms. The paper first decomposed the CIL prediction into within-task prediction (WP) and kask-id prediction (TP). WP is basically TIL. The paper further theoretically demonstrated that TP is correlated with out-of-distribution (OOD) detection. It then proved that a good performance of the two is both necessary and sufficient for good CIL performances. Based on the theoretical result, several new CIL methods were designed. They outperform strong baselines in CIL and also in TIL by large margin. Finally, we also discussed the implications for existing CL techniques and open- open-world learning.
Acknowledgments
The work of Gyuhak Kim, Zixuan Ke and Bing Liu was supported in part by research contract from and 113-1838770) and DARPA contract HR001 1 120C0023.
KDDI, two NSF grants
10

---

References
[1] Zhiyuan Chen and Bing Liu. Lifelong machine learning. Synthesis Lectures on Artificial Intelligence and Machine Learning, 12(3):1-207, 2018.
[2] Gido M van de Ven and Andreas S Tolias. Three scenarios for continual learning. arXiv preprint 1rXiv:1904.07734 2019.
[3] Joan Serrà, Dídac Surís, Marius Miron, and Alexandros Karatzoglou. Overcoming catastrophic forgetting with hard attention to the task. In ICML, 2018
[4] Mitchell Wortsman, Vivek Ramanujan, Rosanne Liu, Aniruddha Kembhavi, Mohammad Raste- gari, Jason Yosinski, and Ali Farhadi. Supermasks in superposition. In H. Larochelle, M. Ran- zato, R. Hadsell, M. F. Balcan, and H. Lin, editors, NeurIPS, 2020.
[5] Bing Liu, Eric Robertson, Scott Grigsby, and Sahisnu Mazumder. Self-initiated open world learning for autonomous ai agents. Proceedings of AAAI Symposium on Designing Artificial Intelligence for Open Worlds, 2021.
[6] Jihoon Tack, Sangwoo Mo, Jongheon Jeong, and Jinwoo Shin. Csi: Novelty detection via contrastive learning on distributionally shifted instances. In NeurlPS, 2020.
[7] Shiyu Liang, Yixuan Li, and R. Srikant. Enhancing the reliability of out-of-distribution image detection in neural networks. In ICLR, 2018.
[8] Sepideh Esmaeilpour, Bing Liu, Eric Robertson, and Lei Shu. Zero-shot -iitr---iittitttioon detection based on the pretrained model clip. In Proceedings of the AAAI conference artificial intelligence, 2022.
[9] Mengyu Wang, Yijia Shao, Haowei Lin, Wenpeng Hu, and Bing Liu. Cmg: A class-mixed generation approach out-of-distribution detection. Proceedings of ECML/PKDD-2002 2022.
[10] Anastasia Pentina and Christoph Lampert. A pac-bayesian bound for lifelong learning. In International Conference on Machine Learning, pages 991-999. PMLR, 2014.
[11] Ryo Karakida and Shotaro Akaho. Learning curves for continual learning in neural networks: Seff-knowledge transfer and forgetting. In International Conference on Learning Representa- tions, 2022.
[12] James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei A Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Overcoming catastrophic forgetting in neural networks. Proceedings of the national academy of sciences, (1((13:3521-3526, 2017.
et al.
[13] Zhizhong Li and Derek Hoiem. Learning Without Forgetting. In ECCV, pages 614-629.
Springer, 2016.
[14] Heechul Jung. Jeongwoo Ju, Minju Jung, and Junmo Kim. Less-forgetting learning in deep neural networks. arXiv preprint 16Xiv:1607.00/22, 2016.
[15] Raffaello Camoriano, Giulia Pasquale, Carlo Ciliberto, Lorenzo Natale, Lorenzo Rosasco, and Giorgio Metta. Incremental robot learning of new objects with fixed update time. In ICRA, 2017.
[16] Friedemann Zenke, Ben Poole, and Surya Ganguli. Continual learning through synaptic intelligence. In ICML, pages 3987-3995, 2017.
[17] Hippolyt Ritter, Aleksandar Botev, and David Barber. Online structured laplace approximations for overcoming catastrophic forgetting. In NeurIPS, 2018.
[18] Jonathan Schwarz, Jelena Luketina, Wojciech M Czamecki, Agnieszka Yee whye Teh, Razvan Pascanu, and Raia Hadsell. Progress & compress: A scalable framework for continual learning. arXiv preprint arXiv: 1oXXvv1805.06 1805.06370 2018.
[19] Ju Xu and Zhanxing Zhu. Reinforced continual learning. In NeurIPS, 2018.

---

[20] Francisco M Castro, Manuel J Marín-Jiméned Nicolás Guil, Cordelia Schmid, and Karteek Alahari. End-to-end incremental learning. In ECCV, pages 233 223-248, 2018.
[21] Wenpeng Hu, Zhou Lin, Bing Liu, Chongyang Tao, Zhengwei Tao, Jinwen Ma, Dongyan Zhao, and Rui Yan. Overcoming catastrophic forgetting for continual learning via model adaptation. In ICLRCR, 2019.
[22] Prithviraj Dhar, Rajat Vikram Singh, Kuan-Chual Peng, Ziyan Wu, and Rama Chellappa. Learning without memorizing. In CVPR, 2019.
[23] Kibok Lee, Kimin Lee, Jinwoo Shin, and Honglak Lee. Overcoming catastrophic forgetting with unlabeled data in the wild. In CVPR, 2019.
[24] Hongjoon Ahn, Sungmin Cha, Donggyu Lee, and Taesup Moon. Uncertainty- continual learning with adaptive regularization. In NeurlPS, 2019.
[25] Yu Liu, Sarah Parisot, Gregory Slabaugh, Xu Jia, Ales Leonardis, and Tinne Tuytelaars. More classifiers, less forgetting: A generic multi-classifier paradigm for incremental learning. In ECCV, pages 699-716. Springer International Publishing, 2020.
[26] Fei Zhu, Xu- Yao Zhang, Chuang Wang. Fei Yin, and Cheng- Liu. Prototype augmentation and self-supervision for incremental learning. In CVPR, 2021.
[27] Andrei A Rusu. Neil C Rabinowitz, Guillaume Desjardins, Hubert Soyer, James Kirkpatrick, Koray Kavukcuoglu, Razvan Pascanu, and Raia Hadsell. Progressive neural networks. arXiv preprint arXiv: 1606. 04670, 2016.
[28] David Lopez-Paz and Mare' Aurelio Ranzato. Gradient Episodic Memory for Continual Learn- ing. In NeurlPS, pages 6470-6479 2017.
[29] Sylvestre-Alvise Rebuffi, Alexander Kolesnikov, and Christoph H Lampert. iCaRL: Incremental classifier and representation learning. In CVPR, pages 5533-5542, 2017.
[30] Arslan Chaudhry, Marc' Aurelio Ranzato, Marcus Rohrbach, and Mohamed Elhoseiny, Efficient lifelong learning with a-gem. In ICLR, 2019.
[31] Saihui Hou, Xinyu Pan, Chen Change Loy, Zilei Wang. and Dahua Lin. Learning a unified classifier incrementally via rebalancing. In CVPR, pages 831-839, 2019.
[32] Yue Wu, Yinpeng Chen, Lijuan Wang. Yuancheng Ye, Zicheng Liu, Yandong Guo, and Yun Fu. Large scale incremental learning. In CVPR, 2019.
[33] David Rolnick, Arun Ahuja, Jonathan Schwarz, Timothy P. Lillicrap, and Greg Wayne. Experi- ence replay for continual learning. In NeurlPS, 2019.
[34] Pietro Buzzega, Matteo Boschini, Angelo Porrello, Davide Abati, and Simone Calderara. Dark experience for general continual learning: a strong, simple baseline. In NeurIPS, 2020.
[35] Jathushan Rajasegaran, Munawar Hayat, Salman Khan, Fahad Shahbaz Khan, Ling Shao, and Ming-Hsuan Yang, An adaptive random path selection approach for incremental learning, 2020.
[36] Yaoyao Liu, Bernt Schiele, and Qianru Sun. Adaptive aggregation networks for class- incremental learning. In CVPR, 2021.
[37] Hyuntak Cha, Jaeho Lee, and Jinwoo Shin. Co21: Contrastive continual learning. In ICCV, 2021.
[38] Shipeng Yan, Jiangwei Xie, and Xuming He. Der: Dynamically expandable representation for class incremental learning. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition, pages 3014-3023, 2021.
[39] Liyun Wang, Xingxing Zhang, Kuo Yang, Longhui Yu, Chongxuan Li, Lanqing Hong, Shifeng Zhang, Zhenguo Li, Yi Zhong, and Jun Zhu. Memory replay with data compression for continual learning. Proceedings of International Conference on Learning Representations (ICLR), 2022.
12

---

[40] Yiduo Guo, Bing Liu, and Dongyan Zhao. Online continual learning through mutual information maximization. In International Conference on Machine Learning, pages 1129-816. PMLR, 2022.
[41] Alexander Gepperth and Cem Karaoguz. A bio-inspired incremental learning architecture for applied perceptual problems. Cognitive Computation, 8(5):924-934, 2016.
[42] Nitin Kamra, Umang Gupta, and Yan Liu. Deep Generative Dual Memory Network for Continual Learning. arXiv preprint arXiv:1710.10330000 2017.
[43] Hanul Shin, Jung Kwon Lee, Jaehong Kim, and Jiwon Kim. Continual learning with deep generative replay. In NIPS, pages 2994-3003, 2017.
[44] Chenshen Wu, Luis Herranz, Xialei Liu, Joost van de Weijer, Bogdan Raducanu, et al. Memory replay gans: Learning to generate new categories without forgetting. In NeurIPS, 2018.
[45] Ari Seff, Alex Beatson, Daniel Suo, and Han Liu. Continual learning in generative adversarial nets. arXiv preprini arXiv: arXiv: 1705.08903, 2017.
[46] Ronald Kemker and Christopher Kanan. FearNet: Brain-Inspired Model for Incremental
Learning. In ICLR, 2018.
[47] Mohammad Rostami, Soheil Kolouri, and Praveen K. Pilly. Complementary learning for overcoming catastrophic forgetting using experience replay. In IJCAI, 2019.
[48] Oleksiy Ostapenko, Mihai Puscas, Tassilo Klein, Patrick Jahnichen, and Moin Nabi. Learning to remember: A synaptic plasticity driven framework for continual learning. In CVPR, pages 11321-11329, 2019.
[49] Guanxiong Zeng, Yang Chen, Bo Cui, and Shan Yu. Continuous learning of context-dependen processing in neural networks. Nature Machine Intelligence, 2019.
[50] Yiduo Guo, Wenpeng Hu, Dongyan Zhao, and Bing Liu. Adaptive orthogonal projection for batch and online continual learning. In Proceedings of AAAI-2022, 2022.
[51] Arslan Chaudhry, Nacemullah Khan, Puneet K. Dokania, and Philip H. S. Torr. Continual learning in low-rank orthogonal subspaces, 2020.
[52] Zixuan Ke, Bing Liu, and Xingchang Huang. Continual learning of mixed sequence of similar and dissimilar tasks. In NewrlPS, 2020.
[53] Arun Mallya and Svetlana Lazebnik. PackNet: Adding Multiple Tasks to a Single Network by Iterative Pruning. arXiv preprint arXiv: 2017.
[54] Ching-Y Yi Hung, Cheng-Hao Tu, Cheng-En Wu, Chien Chien-Hung Chen, Yi-Ming Chan, and Chu- Song Chen. Compacting, picking and growing for unforgetting continual learning. In NeurIPS, volume 32, 2019.
[55] Johannes von Oswald, Christian Henning, João Sacramento, and Benjamin F Grewe. Continual learning with hypernetworks. ICLR, 2020.
[56] Jachong Yoon, Sachoon Kim, Eunho Yang, and Sung Ju Hwang. Scalable and order-robust continual learning with additive parameter decomposition. In ICLR, 2020.
[57] Pravendra Singh, Vinay Kumar Verma, Pratik Mazumder, Lawrence Carin, and Piyush Rai. Calibrating cnns for lifelong learning. NeurIPS, 2020.
[58] Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In CVPR, 2020.
[59] Ting Chen, Simon Korbblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In ICML, 2020.
[60] Saikiran Bulusu, Bhavya Kailkhura, Bo Li, Pramod K Varshney, and Dawn Song. Anomalous instance detection in deep learning: A survey, arXiv preprint arXiv:2003.06979 2020.
13

---

[61] Chuanxing Geng, Sheng-jun Huang, and Songcan Chen. Recent advances in open set recogni- tion: survey, IEEE transactions on pattern analysis and machine intelligence, 2020.
[62]
Jathushan Rajasegaran, Salman Khan, Munawar Hayat, Fahad Shahbaz Khan, and Mubarak Shah. itaml: An incremental task-agnostic meta-learning approach. In CVPR, 2020.
[63] Davide Abati, Jakub Tomezak, Tijmen Blankevoort, Simone Calderara, Rita Cucchiara, and Ehteshami Bejnordi. Conditional channel gated networks for task-aware continual learning. In CVPR, pages 3931-3940, 2020.
[64]
Rahaf Aljundi, Punarjay Chakravarty, and Tinne Tuytelaars. Expert gate: Lifelong learning with network of experts. In CVPR, 2017.
[65] Christian Henning, Maria Cervera, Francesco D' Angelo, Johannes Von Oswald, Regina Traber, Benjamin Ehret, Seijin Kobayashi, Benjamin Grewe, and João Sacramento. Posterior meta- replay for continual learning. NeurlPS, 34, 2021.
[66] Sebastian Lee, Sebastian Goldt, and Andrew Saxe. Continual learning in the teacher-student setup: Impact of task similarity. In International Conference on Machine Learning, pages 6109-6118 19... PMLR, 2021.
[67] Mehdi Abbana Bennani, Thang Doan, and Masashi Sugiyama. Generalisation guarantees for continual learning with orthogonal gradient descent. Lifelong Learning Workshop at the ICML, 2020.
[68] Jihwan Bang, Heesu Kim, YoungJoon Yoo, Jung-War Woo Ha, and Jonghyun Choi. Rainbow memory: Continual learning with memory of diverse samples. In Proceedings the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 8218-881888 6--2277, 2021.
[69] Yaoyao Liu, Yuting Su, An-An Liu, Bernt Schiele, and Qianru Sun. Mnemonics training: Multi-class incremental learning without forgetting. In CVPR, 2020.
[70] Weitang Liu, Xiaoyun Wang, John Owens, and Yixuan Li. Energy-basee outto--diitributiin detection. Advances in Neural Information Processing Systems, 2020.
[71] Kimin Lee, Kibok Lee, Honglak Lee, and Jinwoo Shin. A simple unified framework for detecting dut-of-disti samples and adversarial attacks. Advances in neural information processing systems, 31, 2018.
[72] Prannay Khosla, Piotr Teterwak, Chen Wang, Aaron Sarna, Yonglong Tian, Phillip Isola, Aaron Maschinot, Ce Liu, and Dilip Krishnan. Supervised contrastive learning. arXiv preprint arXiv:2004. 1362, 2020.
[73] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. In NIPS, 2012.
[74] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In CVPR, 2016.
[75] Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversar- ial examples. ICLR, 2015.
[76] Gyuhak Kim, Zixuan Ke, and Bing Liu. A multi-head model for continual learning via out-of- distribution replay. arXiv preprint arXiv:2208. 09X1022208.09734 2022.
[77] Deepak Pathak, Pulkit Agrawal, Alexei A Efros, and Trevor Darrell. Curiosity-driven exploration by self-supervised prediction. In International conference machine learning, pages 2778- 2787. PMLR, 2017.
[78] Wenpeng Hu, Mengyu Wang, Qi Qin, Jinwen Ma, and Bing Liu. Hr:: A holistic approach one class learning. Advances in Neural Information Processing Systems, 13:19111-19124, 2020.
14

---

Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] to [Yes], [No], , or [N/A] You are strongly encouraged to include justification your answer, either by referencing the appropriate section of your paper or providing a brief inline description. For example:
Did you include the license to the code and datasets? [Yes] See Section
Did you include the license the code and datasets? [No] The code and the data are proprietary.
Did you include the license to the code and datasets? [N/A]
Please do modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below,
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Sec. 4.5
(c) Did you discuss any potential negative societal impacts of your work? [Yes] In Appendix
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Sec. 3.1
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Sec. 4.22 and Appendix.
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [Yes] See Appendix
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [No]
(c) Did you include any assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "mYbZa4dApY7", "reviewer": "Reviewer_Gwwq", "summary": "This paper studies class incremental learning(CIL) from a theoretical point of view.\nIt proposes to decompose CIL into within-task prediction(WIP) and task-id prediction(TP) correlating to out-of-distribution(OOD) detection. It further provides sufficient and necessary conditions for improving CIL performance, and proves that a good performance in WIP, TP, and OOD is necessary for a good performance of CIL. Experiments on a combination of existing CL and OOD methods validate the theoretical results.", "questions": "All listed CIL methods are a combination of existing CL and OOD detection methods. It's not clear what are the new designed CIL methods.\n", "limitations": "The authors did not adequately addresses the limitations and potential negative societal impact of the work.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n+ The discussion of CIL performance from a theoretical point of view is interesting.\n\n+ The theoretical results provide guidance on selecting a combination of CL and OOD methods for achieving better CIL performance.\n\n+ The authors have conducted extensive experiments on four datasets and nine CL algorithms.\n\nWeaknesses:\n- Although the authors claim that they have proposed a new CIL method based on their theoretical analysis. It's not clear what the novelty of the proposed method. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "fuTfEp65h6B", "reviewer": "Reviewer_2nNb", "summary": "The paper studies Class Incremental Learning (CIL) and shows that the CIL problem can be decomposed into two subproblems: within-task in-distribution prediction (WIP) and task-id prediction (TP). As a result, the CIL performance is bounded by WIP and TP performances. Moreover, the authors show that the TP subproblem itself can be bounded by the OOD detection problem, and thus by extension, CIL can be bounded by WIP and OOD.   \n\nTo test their theory, the authors add better OOD detection to several CL algorithms and report performance improvements.", "questions": "See above.", "limitations": "Adequate discussion.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**:  \n\n\n1. The paper is very well-organized and well-written. It is easy to follow the arguments.  \n\n\n2. The analysis is mostly intuitive, and I appreciate the effort to understand CIL more theoretically.  \n\n\n\n\n**Weaknesses**:  \n\n\n1. I'm not entirely convinced about the bounds in the paper, and I think the theory is partially incomplete. Let's assume we have an oracle that, given a data point, can tell us the task id with zero loss. Also, let's assume if we train on each task individually, we have zero loss. Then by Theorem 1, it means that we can have zero CIL loss. However, this implies that we should have zero loss for the equivalent TIL problem (since we have task ids), which is not necessarily true. I think (but not sure) the theory holds if we assume we don't have shared parameters for tasks (e.g., parameter isolation methods) or tasks are all orthogonal. Otherwise, even if we know about task ids (e.g., TIL), we still can show the error cannot be bounded. As an example, let's say we have two tasks and we always have access to task ids, but we use the same parameters for both tasks. Then if we train on task 2 for a very long time (without using any CL algorithm), since our loss function only depends on the data of task 2, and since we have shared parameters, the parameters will change, and if we measure the loss on task 1, it can grow (similar to all other TIL works), unless we have additional assumptions. I am willing to discuss this further with the authors during the discussion period.\n\n\n2. Discrete Task Assumption: Assumptions 1 and 2 assume that each data point belongs to one task exactly and tasks are discrete. However, in many real-world setups, the shift may be continuous.  \n\n\n\n3. I have read the argument on Sec.4.2 (L274), but I still think the forgetting rate is an important metric that measures the backward transfer in many algorithms. I encourage the authors to compare the average forgetting for a few benchmarks.  \n\n\n\nOverall, while I think this work is a nice first step, I think the theory is limited in its correct form, and more importantly, I think we need additional assumptions. I am willing to raise my score if my concerns are addressed.\n\n\n\n--------\nUpdate: \nAfter discussion with the authors, I believe they have addressed my concerns, and I raise the score.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "I7zB83xnmq", "reviewer": "Reviewer_SV1o", "summary": "The paper investigates the Class incremental learning (CIL) problem by expressing the problem as a Within-task in-distribution (IND) class learning problem (WIP) and task-id prediction (TP) problem. The author theoretically induces that solving the two problems: WIP and TP, is a necessarily sufficient condition for solving CIL, and also shows that TP is closely related to the out-of-distribution detection (OOD) problem. Based on the investigation, the author proposes a new CIL technique using recent OOD algorithms (solving WIP and OOD simultaneously) and achieved superior CIL performance, supporting the author's claim that OOD is a critical factor for CIL. ", "questions": "See the Strongpoints/weakness page.", "limitations": "See the Strongpoints/weakness page.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "StrongPoints\n\n(1) The theoretical investigation of CIL, starting from WIP and TP to OOD, seems reasonable and worth sharing with the community.\n\n(2) The proposed simple CIL solution using OOD supports the claim of the author, that OOD which can also solve WIP, can sufficiently solve CIL problem. Moreover, comparision to many existing CIL problems increases the credibility of the author's suggestion.\n\nWeakPoints\n\nFirst, note that the reviewer is positive about this work, and this section is much like questions rather than criticism.\n\n(1) The paper focuses on the traditional CIL problem set-up that the incoming data label is completely disjoint. However, a recent line of studies also introduces a more realistic, close-to real-world setting, where the incoming data label is overlapped, which called Blurry task setting [1][2]. When following the author's theoretical induction, the reviewer could not find specific problems restricting the induction to be applied in the Blurry task setting. Hence, applying the idea to the Blurry set-up will strengthen the author's claim.\n\n[1] Rainbow memory: Continual learning with a memory of diverse samples. J Bang, H Kim, YJ Yoo, JW Ha, J Choi - Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2021\n[2] Online Continual Learning on a Contaminated Data Stream with Blurry Task Boundaries. J Bang, H Koh, S Park, H Song, JW Ha, J Choi - Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2022\n\n(2) For the testing datasets, recent CIL problems also use ImageNet to show their algorithm's performance larger than CIFAR 10/100 or tiny-ImageNet. The reviewer does not think that the tendency shown in the experiments will not change drastically, but checking it in ImageNet would much strengthen the credibility of the Experiments.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "0LJPiZ6-mO8", "reviewer": "Reviewer_gU43", "summary": "In this paper, the authors propose that the class-incremental learning problem can be decomposed into two sub-problems: within-task prediction and task-id prediction. They further prove that task-id prediction is correlated to out-of-distribution (OOD) detection. They design some class-incremental learning methods based on their theoretical results and provide experiment results on multiple datasets. ", "questions": "as the comments are given in weaknesses.", "limitations": "not clear in this paper.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- This paper provides in-depth theoretical analyses for class-incremental learning. This is interesting.\n\n- Extensive experiment results on different baselines are provided. \n\nWeaknesses:\n\n- All theoretical analyses are based on the assumption that all classes are independent and identically distributed. However, this might not be true in many real-world applications. For example, there are many classes that correspond to different species of dogs in ImageNet. If these classes occur in different incremental stages, they will significantly influence the task-id prediction. Thus, it is questionable how much these theoretical results can be generalized for real-world applications. \n\n- Some top-performing methods are not cited and compared. For example, [A] archives better performance on CIFAR-100 compared to the proposed method (see Figure 3 in [A]). \n\n- Many details haven’t been provided in the main paper. For example, the authors propose some new CIL techniques in Section 4. However, some important details, such as the number of additional parameters required by the proposed method, are not available. A NeurIPS submission needs to be self-contained, and the authors need to let the audience understander the proposed method without reading the supplementary. It doesn’t seem possible in the current version. \n\n- It would be better to provide a figure to show the overall framework of the proposed method. \n\n- This paper is poorly-organized and difficult to understand. For example, the authors mixed the proposed method with the experiment results in Section 4. \n\n-----\n\nOverall, I think this is an interesting paper with extensive theoretical and experimental results. However, there are some unsolved issues as I mentioned in the “weaknesses” part. Thus, my overall rating is “borderline reject”. \n\n-----\n\n[A] Yan, Shipeng, Jiangwei Xie, and Xuming He. \"Der: Dynamically expandable representation for class incremental learning.\" Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2021.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept