Information-theoretic Online Memory Selection for Continual Learning
Authors: Shengyang Sun
Daniele Calandriello
Huiyi Hu
Ang Li
Michalis Titsias
Venue: ICLR 2022 Poster (2022)
Keywords: Task-free continual learning
replay memory
information theoretic
reservoir sampling

Abstract: A challenging problem in task-free continual learning is the online selection of a representative replay memory from data streams. In this work, we investigate the online memory selection problem from an information-theoretic perspective. To gather the most information, we propose the \textit{surprise} and the \textit{learnability} criteria to pick informative points and to avoid outliers. We present a Bayesian model to compute the criteria efficiently by exploiting rank-one matrix structures. We demonstrate that these criteria encourage selecting informative points in a greedy algorithm for online memory selection. Furthermore, by identifying the importance of \textit{the timing to update the memory}, we introduce a stochastic information-theoretic reservoir sampler (InfoRS), which conducts sampling among selective points with high information. Compared to reservoir sampling, InfoRS demonstrates improved robustness against data imbalance. Finally, empirical performances over continual learning benchmarks manifest its efficiency and efficacy.

Published as a conference paper at ICLR 2022
ONLINE MEMORY SELEC- TION FOR CONTINUAL LEARNING
INFORMATION-
Shengyang Sun"), Daniele Calandriello', Huiyi Hu Ang Li Michalis K. Titsias
University of Toronto, Vector Institute, Google Brain, Baiduu Apollo, 'DeepMind ssy0cs toronto. edu, angli01@0a du. com,
[dcalandriello, clarahu, mtitsias (eciiasss@oogg..oooomoo com
ABSTRACT
A challenging problem in task-free continual learning is the online selection of a representative replay memory from data streams. In this work, we investigate the online memory selection problem from an ceemmationthhoreede gather the most information, we propose the surprise and the learnability criteria to pick informative points and avoid outliers. We present a Bayesian model to compute the criteria efficiently by exploiting rank-one matrix structures. We demonstrate that these criteria encourage selecting informative points in greedy algorithm for online memory selection. Furthermore, by identifying the impor- tance of the timing to update the memory, we introduce stochastic information- theoretic reservoir sampler (InfoRS), which conducts sampling among selective points with high information. Compared to reservoir sampling, InfoRS demon- strates improved robustness against data imbalance. Finally, empirical perfor- mances over continual learning benchmarks manifest its efficiency and efficacy.
perspective. To
INTRODUCTION
Continual learning (Robins 1995; Goodfellow et al. 2013 Kirkpatrick et al. 2017) aims at training models through non-stationary data stream without catastrophic forgetting of past experiences. Specifically, replay-based methods (Lopez-Paz
Ranzato 2017 Rebuffi et al. 2017 Rolnick al.) 2019) tackle the continual learning problem by keeping a replay memory for rehearsals over the past data. Given the limited memory budget, selecting a representative memory becomes critical. The majority of existing approaches focus on task-based continual learning and update the memory based on the given task boundaries. Since the requirement for task boundaries is usually not real- istic, general continual learning (GCL) (Aljundi al. [2019a] Delange et al., 2021 Buzzega al.) 2020) has received increasing attention, which assumes that the agent observes the streaming data in an online fashion without knowing task boundaries. GCL makes the online memory selection more challenging since one needs to update the memory in each iteration based only on instant observations. So, successful memory management for GCL needs be both efficient and effective.
Due to the online constraint, only a few memory selection methods are applicable to GCL. A selec- tion method compatible with GCL is reservoir sampling (RS) (Vitter 1985). In particular, RS can be used to randomly extract uniform subset from a data stream in single pass, and it showed com- petitive performances for GCL for balanced streams (Chaudhry et al., 2019b Buzzega et al.) 2020). However, when the data stream is imbalanced, RS tends to miss underrepresented (but essential) modes of the data distribution. To improve the robustness against data imbalance, gradient- trasient-based sample selection (GSS) (Aljundi al. 2019b) proposes to minimize the gradient similarities in the memory, but evaluating many memory gradients in each iteration incurs high computational costs.
We investigate online memory selection from an information-theorrete perspective, where the mem- ory attempts to maintain the most information for the underlying problem. Precisely, we evaluate each data point based on the proposed surprise and learnability criteria. Surprise captures how un- expected a new point is given the memory, and allows us to include new information in the memory. In contrast, learnability captures how much of this new information can be absorbed without inter-
Work done in DeepMind.

---

Published as a conference paper at ICLR 2022
ference, allowing us to avoid outliers. Then we present scalable Bayesian model that can compute surprise and learnaillity with a small computational footprint by exploiting rank-one matrix struc- tures. Finally, we demonstrate the effectiienesss of the proposed criteria using greedy algorithm.
While keeping a representative memory is essential, we show that the timing of the memory up- dates can also be erucial for continual learning performance. Concretely, we highlight that the agent should not update the memory as soon as it sees new data, otherwise it might prematurely remove historical data from the memory and weaken the replay regularization in the GCL process. This phe- nomenon affects the greedy algorithm much more than RS, since the memory updates in RS appear randomly over the whole data stream. To combine the merits of information-theont RS, we modify reservoir sampling to select informative points only. This filters out uninformative points, and thus encourages diverse memory and improves the robustness against data imbalance.
criteria and
Empirically, we demonstrate that the proposed information-theorrtii criteria encourage to select representative memories for learning the underlying function. We also conduct standard continual learning benchmarks and demonstrate the advantage of our proposed reservoir sampler over strong GCL baselines at various levels of data imbalance. Finally, we illustrate the efficiency of the pro- posed algorithms by showing their small computational overheads over the standard RS.
2
MEMORABLE INFORMATION CRITERION
Firstly we formalize the online memory selection problem and propose our information-theored criteria detect informative points. Then we introduce Bayesian model to compute the proposed criteria efficiently. Finally, we demonstrate the usefulness of the criteria in greedy algorithm.
2.1 ONLINE MEMORY SELECTION
We consider a supervised learning problem, where the agent evolves a predictor f to learn the underlying mapping from inputs to targets. We assume that the predictor is in the following form,
fo = 90, (.),,
(1)
where 0 = (0 g. 0n). The base network he, (x) extracts the feature representation of the input x, and 9o, maps the representation to predictions. The function go, is usually a simple module, such as linear layer (Krizhessky et al.) 2012) or rean-of-neiighour (Snell et al.) (017) mapping to the softmax logits. We assume the memory buffer contains the inputs, features, predictions, and targets,
M = (xmm hm gm, Vm) M
(2)
In the online memory selection problem, the agent iteratively receives observations from an online stream, and updates the predictor and the memory buffer. Let B {(x,, yb) be the observed batch in one iteration, a general update formula can be expressed as,
(0. + (0.M,B).
(3)
We emphasize that updating the predictor parameters O and updating the memory M are essential but orthogonal components. For example, the agent can update the memory using RS (Buzzega et al.] 2020) or GSS (Aljundi et al., 2019b), and update O using GEM (Lopez-Paz & Ranzato (017)) or experience replay (Chaudhry et al.] 2019b). This section focuses on how maintain a representative memory M online. while how to update the predictor fe is not our focus. Furthermore, unlike task- continual learning (Kirkpatrick et al., 2017). we assume the agent receives only the data stream without observing task boundaries. This scenario is more diffficult for memory selection. For instance, it must deal with data imbalances, e.g., if discrete tasks of varying lengths exist, we may want the selection to identify more balanced memory and avoid catastrophic forgetting.
2.2 MEMORABLE INFORMATION CRITERION
Intuitively, the online memory should maintain points that carry useful information. We consider a Bayesian model for this problem since the Bayesian framework provides a principled way to quantify the informativeness of data points. Specifically, we let p(y|w; be the likelihood of the observation y given the deterministic input x dependent on the random model parameter w and we
The density p and the parameter w here left completely generie.
2

---

Published as a conference paper at ICLR 2022
denote by p(w) the prior distribution. Then the posterior of w and the predictive distribution of new data points can be inferred according to Bayes's 's rule. Also worth mentioning, the Bayesian model is introduced merely for memory selection, which is different from the predictor fo.
In each iteration of online memory selection, the agent decides whether to include the new data point (x,, V+) into the memory .M. To this end, we present information-theorett criteria based on the Bayesian model to evaluate the usefulness of the new data point. For notational simplicity, we denote by M and YM the inputs and the targets in the memory, respectively.
Surprise. As Claude Shannon says: "Information is the resolution of uncertainty". If the memory M is certain of the target y/- of x. beforehand, incorporating the data point (x,, u+) brings little information into M. Thus we propose to measure the "surprise" of the new point given the memory. We define the surprise criterion of (x., V.) given M as the negative log conditional probability. Ssurp ((x,, B:);; M) = log p(y, IM: X.,X.),
(4)
ply.yyy: YMi XM, x.) = f p(y. x, xxx)).)(ww (o(p))/www/l) M )dw. Intuitively, if (x., comes from a new task, will likely be less predictable according to the memory and the surprise will be large. In this way, the surprise criterion detects informative points and ensures diversity within the buffer.
where ply.
Learnability. The surprise detects unpredictable points in the data stream, but it is not capable of distinguishing "helpful" unfamiliar points and "harmful" outliers. To avoid the outliers, we propose the learnability criterion, which measures how much our Bayesian model can explain the new point once it has absorbed its information in the memory. Formally, we define the learnability as follows,
Steam (xx,, yv) yx); = log p(v (y., y Mi X., x. x.)lu
(5)
where we use v/. and y. represent two realizations of the same random variable. Intuitively, the learnability measures the consensus between the new point and the memory. We illus- trate the utility of learnability through a toy example in Figure T We use a Gaussian process with the RBF ker- nel to fit memory points (shown as black dots )). We visualize its pre- dictive mean and 95% confidence interval as the green line and the shadow region. For two new points (shown as red stars x) separately in the left and right figure, we also visualize the predictive distribution given the memory and the new point, shown as the blue line and the shadow region. We observe that both points surprising the memory since they lie outside (or just outside) of the green confidence regions. However, after conditioning on the new point itself, the left point still lies outside of the confidence region while the prediction on the right adjusts to include the new point. Thus the left point has low learnability, and the right point has high learnability, though both have high surprises. Thus the learnability can be used to detect outliers when combined with the surprise
2
0
-2
-1
0
X
Figure 1: Visualization of the toy problem.
Memorable Information Criterion (MIC). Given 2 O. we propose the Memorable Information Criterion (MIC) as a combination of the surprise and learnability of the new point,
MIC,, ((x,, M) = 17Steam ((,, v.): AM) + S ((x, V- M))
(6)
Notably, the MIC is related to the information gain (IG) (Cover 1999): TG((,,, U+); M) KL (p(wly... y X M, x.) p(w)ppwww))))m XM)). By Appendix E IG can be rewritten as,
(G((x.,));;A))
= Betwles.
[log p(y. /w; - log ly XM),
(7)
where the second term is the surprise, and the first term is upper bounded by the learnability based on Jensen's inequality. Thus we have that MIC1 ((.,)((),)))) y. M) 2 IG((x.. v.):M) 2 O. Given the connection, generalize IG to be a weighted combination of learnability and surprise as well in the Appendix. We also compare with an entropy reduction criterion. More discussions are in See
2.3 AN EFFICIENT BAYESIAN MODEL
Computing the MIC requires inferring Bayesian posteriors, which can be computationally unfeasi- ble for complicated Bayesian models. Now we combine deep networks and Bayesian linear mod- els to make computing the MIC efficient. Deep networks well-known for learning meaningful
3

---

Published as a conference paper at ICLR 2022
representations based on which the predictions are made by simple modules such as linear layers (Krizhevsky et al. 2012; Dubois et al.) 2021). Thus we treat our base network he, as a feature extractor and establish the Bayesian model from the feature space to the target space. Precisely, let dn be the feature dimension and ho = ho, (x) E Redo be the feature of the input x, we compute the normalized feature h := [b 1 / for d == do + 1. Then we consider a Bayesian linear model,
= w "w''+teee(N00"""
(8)
We consider an isotropic Gaussian prior w NO(0, I. Denoting the features and the targets in the buffer as HM E IRMx xd and YM E R respectively, the weight posterior can be computed as,
p MMi HM) = (V(AAM o² AA))
where we define AM = (H + cIa) for o² and bm = H HMM. Given a new point of.
(x+: V.), let h, be the corresponding feature, then the MIC can be computed explicitly as,
((x. log (yslhh A M+ bm- ohh A X++ h, + o²) -logNV A A b., o oh A A + o²),
(10)
where AM- = Am + h.h, and b = b.- + h,y.. A derivation is provided in Appendix E
Efficient computation. Computing the MIC still involves the matrix inversions A AM and A M Fortunately, since AMI differ with AM by rank-one matrix, its inverse can be computed effi- ciently given AM according to the Sherman-Mont Morrison Formula (Sherman & Morrison 1950).
A h AM
A AM+ AM
(11)
Morcover, A M needs not to be computed explicitly either since the MIC expression involves only the matrix vector product A M+ h,. As result, given AM and by, the computational cost of the MIC merely (dP)) One can store A and b. along with the memory, so that the MIC can be computed efficiently. Finally, since the buffer adds or removes at most one point in each iteration, AM and b can be updated efficiently in (dd) well using the Therman-Morrisee formula.
Feature update. Since the predictor evolves along with memory selection, the feature of each input also changes. The feature ha(x,) )) is usually available since the agent needs to forward x, for learning the predictor. However, the stored features HM in the buffer are usually outdated due to representation shifting in the online process. Forwarding the whole memory through the network in each iteration is also computationally infeasible. Alternatively, used to aid learning in the online process, such as memory replay in continual learning (Rebuffi) et al. 2017) experience replay in deep Q learning (Mnih al. (015). Therefore, update the memory features whenever the agent forwards the memories through the network which is free of computational overheads. Finally, we note that the matrix AM needs to be recomputed when the memory features are updated, which takes (dd)) computations using Cholesky decomposition.
notice that the memory is usually
Classification. For classification problems, the exact Bayesian posterior is no longer tractable, preventing explicit expressions of the MIC. To alleviate this problem, we propose to approximate the classification problem as a multi-output regression problem. Specifically, let S S K be the label among K classes, we use the Bayesian model regress the one-hot vector ý RK where Ú: diys i = I,,,, K. Further, we let our Gaussian prior to be independent across output dimensions. Then, the MIC can be computed as the summation of MICs across each output dimension.
2.4 DEMONSTRATING THE CRITERIA BY A GREEDY ALGORITHM
Using a greedy algorithm for online memory selection, we show that the proposed information- theoretic criteria encourage informative points. Intuitively, in each iteration, the algorithm adds the most informative new point and removes the least informative existing point in the buffer.
Information criterion for memories. Consider the new data (x., U+), the buffer M, and a data point (Xm: Vm)) M. Let M. := M U (x., y.) (Xm; Vm). We measure the informativeness
Thhe features are updated every iteration our continual learning experiments, due the memory replay.
4

---

Published as a conference paper at ICLR 2022
Without Learability
With Learnability
0.80
10
Releam Accuracy
0.75
0.65
0.60
reservoir
without learnaiility
0.55
with learnabiliyy
0.50
Budget
Figure 2: left: Relearning performance of the memory. We compare InfoGS with RS and InfoGS without using learnability, for various budgets. middle, right: TSNE visualizations of the train- ing data (colored dots, where the color represents the label of the data point) and 200 memory points (black digits. where the digit represents the label of the point) for InfoGS without and with learnability, respectively. We observe that InfoGS without learnability selects many memories that differ from the training majority, i.e., it selects outliers. In comparison, incorporating learnability avoids the outliers and selects memories that spread the training region and help to learn the decision boundary. Further, InfoGS performances also improve over RS when the budget very low.
of (Xm. 3m) according to its MIC for the pseudo buffer M.,-ms ic., MIC,,(xx Um)) Notably, the criterion for memories is comparable to the criterion for the new point, since MIC,, MM) = MIC,,((x, v.): M.,..) can be expressed similarly.
Let (xy+, (xb+,96+) 96-) with the new point (x.,V+) Specifically, we present information improvement thresholding to deter- mine whether the new point improves the information by least certain amount. We present learn- ability thresholding to only add points with high learnability, The overall algorithm, Information- theoretic Greedy Selection (InfoGS), replaces (x.., y0-) with (x., y.), if the new point passes both thresholding. A detailed description and the pseudocode are shown in Alg 2 in the Appendix.
.M be the memory point with the smallest MIC. We decide whether to replace it
toy experiment. Using InfoGS, we illustrate the proposed criteria by a toy experiment. We gener- ate the toy dataset by training a ResNet-16 18 (He et al. 2016) for CIFAR-10 classification and storing the network features and the targets the whole dataset. We use pre-trained features for InfoGS, to focus on the online memory selection without the interference of feature learning. The agent ob- serves the dataset stream for one epoch with the batch size 32, sequentially by the order of classes: {0, 1), {2, 3), {4, 5). {6, 7). {8, 9}. We evaluate the final memory by the "relcarn" performance, where we a linear classifier on merely the memory points and report the test accuracy. In this way, the relearning performance directly represents the quality of the memory. We compare InfoGS with RS. To investigate the impact learnability, we also include a modified InfoGS by removing the learnability. We run all methods across various memory budgets. We also plot the memories using the TSNE visualization (Hinton & Roweis 2002). The results are shown in Figure
3 INFORMATION- THEIOOTT-TTEERITIC RESERVOIR SAMPLING
In this section we incorporate the MIC into continual learning. For training the prediction network, pick the dark experience replay (DER++) (Buzzega et al. 2020), which is fully compatible to GCL and achieves state-of-art performances on continual learning benchmarks. DER++ prevents the network from forgetting by regularizing both the targets and the logits. Specifically, for each new batch B, DER++ optimizes the network parameter f by minimizing the following objective,
1 B
B M
M(O:M)
((:
+ M Σ [
gm 112
Σ (((xm vm))
where the objective is composed of (I) the fitting loss of the current batch, such as the cross entropy; (2) the mean squared loss between the predictive logits fo (x,.... of the memory input xm and its memory logits gm: (3) the fitting loss of the memory. a and |3 are syper-parammters.
While straightforward, naively employing InfoGS to curate the buffer suffers the timing issue identify for continual learning. We present a new algorithm, the information -theoortottthhtticccc reservoir sam- pling, which integrates the MIC into RS and achieves improved robustness against data imbalance.
5

---

Published as a conference paper at ICLR 2022
Algorithm information-theerelle Reservoir Sampling (InfoRS)
1:
Input: Memory M and matrices A J b., the batch B, the predictor parameter 0.
2: Input: The reservoir count and the budget M.
3: Input: Running mean and stddev for the MIC: fú, o; The thresholding ratio "V--
4: Update the predictor parameter 0 based M and 3
// Predictor Update
5: Update the features for the memory points used in replay, and update A AM
M bm accordingly.
6: for (x., W.) in B do
7: if [M] < M or MIC,, ((Xx,,y.) ;.);:M 2 j4 + 77 % M,,, n, (x., y.)).
// Information Thresholding Memory Update
ReservoirSampling 9: Update A AM b.M based on the Aherman-Morrison formula M is updated.
8: Update M,
10: Update Rú, o; using the criterion MIC,((x, (x) M)).
// Running Moments Update return Buffer M and A:: b. The reservoir count n and statistics Pa. og. The updated O.
11:
3.1 THE IMPORTANCE OF THE TIMING TO UPDATE THE MEMORY
While maintaining a representative memory is critical to properly regularize an online CL process, will discuss and empirically show that when the memory updated (i.e., the update timing) is also influential. We begin by giving an intuition of this issue with mind experiment, where the agent sequentially observes the data from two tasks Ti and T2. At the time of task switching, the agent has a memory with M examples from Tí. Assume that the agent will update the memory by removing examples from Ti and adding 2 examples from T2 the time + At. Since the Tz examples are repeatedly visited after time I, is favorable use large At. In contrast, updating leads to degrading Ti regularizations too early.
memory at the beginning of To with Al-
We further demonstrate this by Split CI- FARIO experiment with 5 tasks. After At it- erations of each task T: for I, 1,.,,,, 5, we ran- domly replace 200 memories with the examples from T. In Figure 3 report the final accu- racies with varying At to change the timing of memory updates, for both a 0, 3 = and = 0.3,0,33 B = in dark experience replay. We observe that updating the memory early in each task Icads to worse performances. The phe- nomenon more distinct for a 0.3, where storing premature logits gm early in each task actually hurts the network learning.
0.55
a
Valid Accuracy
0.50
a 0.3
0.45
0.40
0.35
0.30
1
1000
3000
10000
Update Iteration
Figure 3: The effect of update timing AL
Reservoir sampling acts randomly to maintain uniform sample from the past stream, thus it tends not to update the buffer immediately at a new task. However, InfoGS accumulates surprising exam- ples greedily, thus its memory updates tend to happen early in each task. Therefore, the greediness of InfoGS is a disadvantage to RS in terms of the timing to update the memory. Morcover, the importance of timing persists not only in the task-based continual learning, but also in the general continual learning regime where the data distribution shifts continuously.
3.2 INFORMATION- THEOOETT RESERVOIR SAMPLING
To alleviate the timing problem of InfoGS, we present the information-theoreee reservoir sampling (InfoRS) algorithm, which attempts bring together the merits of both the information-theorett criteria and the reservoir sampling. The MIC facilitates a representative memory, but the greedy selection should be circumvented for the sake of timing. To this end, we propose InfoRS, which conducts reservoir sampling over those points with high MICs. Similarly to InfoGS, we let P.g & be the running mean and standard deviation of the MICs for all historical observations, and let 7 be a hyper-parameter. InfoRS selects the point (x+; y-) ) for reservoir sampling if its MIC passes the information threshold: MIC,, ((x., y. M) > 14 + ō %/t The overall algorithm of InfoRS is shown in Alg [ and we also provide the algorithm of ReservoirSampling in Alg in the Appendix.
We use DER+ in Eq 1225 for updating the predictor, but other algorithms he adopted well.

---

Published as a conference paper at ICLR 2022
Worth mentioning, point (x., V4) passing the information threshold results in itself being consid- ered in the reservoir sampling procedure. However, due to the stochasticity in RS, the point might not be added to the memory. Consequently, InfoRS overcomes the timing issue for the greedy In- foGS. In addition, standard RS draws uniform samples over the stream, making it vulnerable to imbalanced data. For example, the memory can be dominated by a specific task if it has lots of ob- servations, while examples from other tasks might be missed and their regularizations be degraded. In comparison, for InfoRS, if a specific task occupies more space in the memory, similar points in the task will have smaller information criterion and thus a lower chance to pass the information threshold. Thus the memory selected by InfoRS will not be dominated by specific tasks and tend to be more balanced. In this way, InfoRS could be more robust to data imbalance compared to RS.
4 RELATED WORKS
Experience replay for continual learning, Experience replay is widely adopted in continual learn-
ing to prevent catastrophic forgetting (Robins, 1995] Lopez & Ranzato| 2017: Rebuffi et al.
2017
Rolnick al., 2019). However, the majority of approaches focus on task- bask-basddde continual
learning and update the memory relying on task boundaries (Rebuffi et al. 2017: Nguyen et al.
2018
Titsias et al.] 2020 Pan et al. 2020 |Bang et al., [02T]] Yoon et al.] 2021). 1). In contrast, reser-
voir sampling (Vitter 1985) is used (Rolnick et al. 2019 Chaudhry et al., 2019b] Buzzega et al.)
2020
Isele & Cosgun 2018 Balaji al. 2020) to update the memory online and maintain uniform
RS (CBRS) that selects uniform sam- ples over each class (Chrysakis & Moens 2020| Wiewel & Yang) | Kim et al.) (020)) but CBRS cannot resolve other forms of data imbalance. To counter the vulnerabilities to data imbalance, GSS (Aljundi et al. 2019b) proposes to minimize gradient similarities to ensure the memory diversity, but incurs large computational costs for gradient computations. For continual reinforcement learn- ing, Isele& & Cosgun 2018) propose selection strategies based on prediction errors or rewards, but these do not promote diversities within the memory. They further attempt to maximize the coverage of the input space for the memory, while selecting an appropriate distance metric between high- dimensional inputs is erucial. [Borsos et al. (220) present the weighted coreset selection and extend it to GCL. However, the method incurs large computational costs and is limited to a small memory,
samples from the stream. RS is generalized to
More applications with online data selection. Apart from preventing catastrophic forgetting, on- line selecting data is also useful for improving the computational and memory efficiencies of learn- ing systems. Deep Q-learning (Mnih al. (015)) adopts past experiences train the Q-networks, and selective experiences can improve the learning efficiency of agents (Schulman et al. 2015). Moreover, online selection forms the key component in curriculum learning (Bengio et al. 2009) to pick the next curriculum for efficient learning. Specifically, prediction gain (PG) (Bellemare et al.) 2016 Graves et al.] 2017) picks the curriculum according to L( yx f) L((xx,(( (xxx,...): 0'. where O' is the parameter after the network updates 0 for one step using (X,, (x,,y*) y.). Thus PG can be seen as the combination of surprises and learnability as well. However, PG does not use a memory buffer and the 6' is obtained by one-step gradient updates unlike exact inference. Bayesian optimiza- tion (Mockus et al.] 1978) and active learning (MacKay) 1992) learn the problem with querying the training data interactively to maximize some unknown objective or data efficiency. However, the labels of the queried data are not available before the query, which is different to our setting where both the input and target are available. Online submodular maximization (Buchbinder et al., 2014 Lavania et al. 2021) selects a memory buffer online to maximize a submodular criterion. They propose greedy algorithms based on an improvement thresholding procedure, which is similar to our InfoGS. However, as discussed in Sec. 3] greedy algorithms can suffer from the issue of timing in continual learning. Also, while we provide MIC as a general criterion to evaluate forthcoming points, submodular maximization relies on meaningful submodular criterions.
Offline data selection. Offline selections assume the whole dataset is available and a representative small set is targeted, which helps to lift the memory burden of dataset storage and improve learning efficiency. Coreset selection (Campbell & Broderick] 2019) aims to find a weighted set whose maximum likelihood estimator approximates that of the whole dataset. Dataset distillation (Zhao) et al. 2020 Nguyen et al. (021) aims at a small set training on which achieves similar performances to trainnn on the original dataset. Sparse Gaussian processes also consider the selection of inducing points (Seeger et al. 2003) Csato & Opper 2002 Bui et al. al. 2017). For instance, (Seeger et al. (2003) adopt the information gain to select inducing points for a scalable Gaussian process method.
7

---

Published as a conference paper at ICLR 2022
Split MNIST
Split CIFAR10
Split MinilmageNet
Split CIFAR1O
0.24
0.8
0.50
Test Accuracy
0.22
Test Accuracy
0.60
0.7
0.45
0.55
0.20
RS
0.40
0.50
InfoGS
WRS
0.35
0.18
0.45
M-1600
M=800
0.5 InfoRS
0.16
0.40
0.30
M-400
30
Data Imbalance
Data Imbalance
Data Imbalance
Data Imbelance
Figure 4: Test performances against data imbalance over continual learning benchmarks. left three: We compare RS, weighted RS (WRS) using the output-space Hessian, InfoGS and InfoRS. For each experiment, plot the mean and the 95% confidence interval across 10 random seeds. right: We compare InfoRS and RS for different memory budgets over Split CIFARIO. For all figures, we observe that InfoRS is more robust data imbalance compared to RS.
5 EXPERIMENTS
We investigate how InfoRS performs empirically. We assume the general continual learning regime, where the agent is agnostic of task boundaries. We use DER++ (Buzzega al. 2020) for learning the predictor along with the online memory selection instead of using pretrained features. To introduce experimental details, we first describe useful notations following [Buzzega et al. (2020). We denote the batch size bs, and the memory batch size as mbs. Specifically, we randomly sample mbss points from the memory buffer in each iteration. We denote the memory budget as M. For all experiments, we adopt the stochastic gradient descent optimizer and we denote the learning rate Ir.
Benchmarks. The benchmarks involve Permuted MNIST, Split MNIST, Split CIFAR1O, and Split MinilmageNet. Permuted MNIST involves 20 tasks, and transforms the images by task-dependent permutations. The agent attempts to classify the digits without task identities. The other benchmarks split the dataset into disjoint tasks based on labels. For Split MNIST and Split CIFARIO, 10, 10 classes are split into 5 tasks evenly; for Split MinilmageNet, 100 classes are split into 10 tasks evenly. We use fixed split across all random seeds. The agent attempts to classify the images without task identities either. For the sake of space, we present the results for Permuted MNIST in the Appendix.
Methods. The online fashion in GCL causes that only a few existing methods are compatible. In addition to RS, weighted reservoir sampling (WRS) (Chao 1982 Efraimidis & Spirakis 2006) gen- eralizes RS to non-uniform sampling in proportional to data-dependent weights. Consequently, one can adopt WRS to favor specific points according to the chosen importance weight. We include WRS baseline with the total output-space Hessian (Pan et al. 2020) as importance weights. Specif- ically, if Pı-K the predictive probabilities for K classes of point, its total output-space Hessian is computed as 1 Ex= r Intuitively, the total Hessian of point is small if it has a confi- dent prediction. We compare InfoRS, InfoGS, RS and WRS over the experiments. Additionally, class-balanced reservoir sampling (CBRS) (Chrysakis & Moens 2020) maintains uniform samples separately for each class, and GSS (Aljundi et al. (019b) minimizes the gradient similarities in the memory. We present the comparisons with CBRS and GSS in Figure X
in the Appendix for clarity.
Experimental details. For Permuted MNIST and Split MNIST, we adopt a fully connected network with two hidden layers of 100 units each, and we set M=100, 1s=128, m1s=118. For Split CIFARIO and Split Minilmage we adopt a standard R8 (He et al. 2016) and set bs=32, mbs=32 We set M = 200 and M = 1000 for Split CIFARIO and Split MinilmageNet, respectively. To tune the hyper-parametert hyper-parameter based on the averaged validation accuracy over 5 random seeds. The final test performance is reported by relearning the model using the whole training set with the best hyper- parameter, averaged over 10 seeds. The tuning hyper-parameters include the learning rate Ir, the logit regularization coefficient a, the target regularization coefficient 88 the learnability ratio 1), and the information thresholding ratio 7;, if needed. We present the detailed hyper-parameten in Table
we pick 10% of training data as the validation set, then we pick the best
'Our ResNet contains a MaxPooling with window shape 3 and stride 2 after the first ReLUU, which is absent in Buzzega al. (022) Our initial conv uses kernel 7 and stride 2, compared to their kernel and stride 1.
8

---

Published as a conference paper at ICLR 2022
1e6
6
Reservoir Count
1
Class Variance
RS
3
400
WRS
4
5
InfoGS
200
InfoRS
2
0
100000
200000
300000
30
Iteration
Data Imbalance
Figure 5: left: The reservoir count along with training. The line = 1, 7, 9, corresponds to the problem where the i-th task has 10 times epochs than the other tasks. We also plot the black dashed line for the count of standard RS. We observe that the reservoir count of InfoRS grows at a similar speed as RS for most tasks. However, it grows slower iterations corresponding to task for each line i. In this way, InfoRS counters the imbalanced data stream, maintains diverse buffer, and behaves more robustly. right: The class variance of the memory. We observe that the memory of RS becomes the most imbalanced with the data imbalance increasing.
Robustness against data imbalance. To simulate data imbalance, we vary training epochs across different tasks. Specifically, given the base epoch n. > and data imbalance > L, we randomly pick one task T. and train it for ne epochs, while we train the other tasks for ne epochs. Thus TT is observed r times more frequently and the data imbalance increases when r grows. Given the imbalanced training data, the agent is still expected to learn all tasks well. Therefore, we evaluate all tasks equally and report the averaged test performance. For all the benchmarks, we conduct experiments with for Split CIFAR 10, and n. = 100 for Split MinilmageNet. The results are shown in Figure Moreover, Figure also compares InfoRS and RS across varying budgets over Split CIFARIO.
1, 3, 10, 30. We set n.e 1 for Permuted MNIST and Split MNIST, n. 50
We observe that RS and InfoRS outperform other approaches when the data is balanced, while InfoRS demonstrates improved robustness compared to RS as data imbalance increases. Compared to InfoRS and RS, InfoGS is less affected by data imbalance since InfoGS acts greedily to gather the memories. Also, WRS with the total Hessian is more robust than RS, since frequently observed points tend to have confident predictions and thus small weights to be sampled. Overall, we observe that InfoRS improves the robustness from RS without sacrificing the performance for balanced data.
We manifest the robustness of InfoRS by visualizing its reservoir count along with training. which the total number of points considered in the reservoir sampling. Thus the count increases linearly for the standard RS, but is affected by the information thresholding in InfoRS. We track the reservoir 10. The results are visualized in
count of InfoRS for Split MinilmageNet with data imbalance T Furthermore, good memory should contain similar example amounts for all classes. Let MIKK the example numbers the memory for all K classes. For each method, we compute the variance Σx M + Σx 2 Figure also visualizes the variances for Split MinilmageNet.
Running time. To demonstrate the computational efficiency of the proposed approaches, we compare the running time of RS, WRS, InfoGS, InfoRS. Specifically, we plot the total run- ning time over Split MinilmageNet with the data imbalance r = 30. As shown in Figure(6] InfoGS and InfoRS incur small computational overheads compared RS. This result demon- strates the efficiency of the proprosed algorithms.
25000
Seconds
20000
15000
10000
5000
WR5
InfoGS
InfoRs
CONCLUSION
Figure 6: The total running time.
We presented information-theorede approaches for online memory selection. Specifically, we pro- posed to maintain the most information in the memory by evaluating new points along two dimen- sions: the surprise and the learnability, which are shown select informative points and avoid outliers. Besides the InfoGS which updates the buffer whenever seeing new examples, we presented the InfoRS that counters the timing issue of the greedy algorithm. Adding the information thresh- old in InfoRS avoids duplicate points in the memory, improving robustness against imbalanced data streams. Moreover, proposed algorithms efficiently, thanks to the proposed Bayesian model.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTI
We thank Yutian Chen, Razvan Pascanu and Yee Whye Teh for their constructive feedback.
ETHICS STATEMENT
This paper introduces a novel and efficient mechanism for selecting examples into an online memory. The proposed memory selection approach is applied continual learning. An important benefit of this approach is that it allows a neural network to be trained from a stream of data, in which case it is not required store all the data into storage. The overall machine learning efficiency could be significantly improved in terms of both space storage and computation. However, potential risk comes with the fact that small amount of information is selected into an online memory. Special care should be taken to ensure the user's privacy is not violated in certain situations.
REPRODUCIBILITY STATEMENT
Here discuss efforts to facilitate the reproducibility of the paper. Firstly, present detailed pseudocodes for the proposed InfoRS (Alg and InfoGS (Alg 2 We also present pseudocodes for the baselines used in the experiments, including reservoir sampling (Algß), weighted reservoir sampling (Alg 4). and class-balanced reservoir sampling (Alg 5). Moreover, we introduce the pro- cess tune the hyper-parameters in the experimental section, and present in Table The detailed hyper-pann parameters we tuned for the involved approaches. In addition, we show detailed derivations and proof' in See EE] Finally, besides the visualization figures, we present the precise means and standard errors of the experiments in Table 2
REFERENCES
Rahaf Aljundi, Klaas Kelchtermans, and Tinne Tuytelaars. Task-free continual learning. In Pro- ceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 11254 11263, 2019a.
Rahaf Aljundi, Min Lin, Baptiste Goujaud, and Yoshua Bengio. Gradient based sample selection for online continual learning, Advances in Neural Information Processing Systems, 32: 1816-11825. 2019b.
Yogesh Balaji, Mehrdad Farajtabar, Dong Yin, Alex Mott, and Ang Li. The effectiveness of memory replay large scale continual learning, 2020.
Jihwan Bang. Heesu Kim, YoungJoon Yoo, Jung- Woo Ha, and Jonghyun Choi. Rainbow mem- ory: Continual learning with a memory of diverse samples. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp.
2021.
Marc Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Remi Munos. Unifying count-based exploration and intrinsic motivation. Advances neural information pro- cessing systems, 29:1471-1479, 2016.
Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. Curriculum learning. In Proceedings of the 26th annual international conference machine learning, pp. 41-48, 2009,
Zalán Borsos, Mojmir Mutny, and Andreas Krause. Coresets via bilevel optimization for continual learning and streaming. Advances Neural Information Processing Systems, 33, 2020.
Niv Buchbinder, Moran Feldman, and Roy Schwartz. Online submodular maximization with pre- emption. Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algo- rithms, pp. 1202-1216 1216. SIAM, 2014.
Thang D Bui, Cuong Nguyen, and Richard E Turner. Streaming Sparse Gaussian Process Approx- imations. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems 30, pp. 3299-3307 Curran Associates, Inc., 2017.
10

---

Published as a conference paper at ICLR 2022
Pietro Buzzega, Matteo Boschini, Angelo Porrello. Davide Abati, and Simone Calderara. Dark experience for general continual learning: a strong, simple baseline. 34th Conference on Neural Information Processing Systems (NeurIPS 2020), 2020.
Trevor Campbell and Tamara Broderick. Automated scalable bayesian inference via hilbert coresets. The Journal of Machine Learning Research, (0(1):551-588 2019.
Min-Te Te Chao. 1982.
general purpose uncqual probability sampling plan. Biometrika, 69(3):653-656,
Arslan Chaudhry, Mare' Aurelio Ranzato, Marcus Rohrbach, and Mohamed Elhoseiny. Efficient lifelong learning with a- a-GEM. International Conference on Learning Representations, 2019a. 2019 URL httphttsss//cppereeieeee net. Forum? dd=kkf2_sc555
Arslan Chaudhry, Marcus Rohrbach, Mohamed Elhoseiny, Thalaiyasingam Ajanthan. Puneet K Dokania, Philip HS Torr and Marc' Aurelio Ranzato. On tiny episodic memories in continual learning. arXiv preprint arXiv: 10486 2019b.
Aristotelis Chrysakis and Marie-Francing Moens. Online continual learning from imbalanced data. In International Conference on Machine Learning, pp. 1952-1966 1961. PMLR, 2020.
Thomas M Cover. Elements of information theory. John Wiley Sons, 1999.
L. Csato and M. Opper. Sparse online Gaussian processes. Neural Computation, 14:641-668, 2002.
Matthias Delange, Rahaf Aljundi, Mare Masana, Sarah Parisot, Xu Jia, Ales Leonardis, Greg Slabaugh, and Tinne Tuytelaars. A continual learning survey: Defying forgetting in classification tasks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021.
Yann Dubois, Benjamin Bloem-Reddy, Karen Ullrich, and Chris Maddison. Lossy compression for lossless prediction. arXiv preprint 1:Xi:2206611800 2021.
Pavlos S Efraimidis and Paul G Spirakis. Weighted random sampling with reservoir. Information Processing Letters, 97(5):181
2006.
lan Goodfellow, Mehdi Mirza, Da Xiao, Aaron Courville, and Yoshua Bengio. An empiri- cal investigation of catastrophic forgetting in gradient-based neural networks. arXiv preprint 1rX1v:1312.6211, 2013.
Alex Graves, Mare Bellemare, Jacob Menick, Remi Munos, and Koray Kavukcuoglu. Automated curriculum learning for neural networks. In international conference on machine learning, pp. 1311-1320. PMLR, 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 770-778, 2016.
Geoffrey Hinton and Sam T Roweis. Stochastic neighbor embedding. In NIPS, volume 15, pp. 833-840. Citeseer, 2002.
David Isele and Akansel Cosgun. Selective experience replay for lifelong learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018
Chris Dongjoo Kim, Jinseo Jeong, and Gunhee Kim. Imbalanced continual learning with partition- ing reservoir sampling. In European Conference Computer Vision, pp. 411-428. Springer, 2020.
James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei A Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Grabska Barwinska. al. Overcom- ing catastrophic forgetting in neural networks. Proceedings of the National Academy of Sciences, pp. 201611835, 2017.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep volutional neural networks. Advances in neural information processing systems, 25:1097-1105, 2012.
11

---

Published as a conference paper at ICLR 2022
Chandrashekhar Lavania, Kai Wei, Rishabh Iyer. and Jeff Bilmes. A practical online framework for extracting running video summaries under a fixed memory budget. In Proceedings of the 2021 SIAM International Conference Data Mining (SDM), pp.
SIAM, 2021.
David Lopez-Paz and Marc' Aurelio Ranzato. Gradient episodic memory for continual learning. In Proceedings of the 31st International Conference Neural Information Processing Systems, pp- 6470-6479, 2017.
David JC MacKay. Information-based objective functions for active data selection. Neural compu- lation, 4(4):590-604, 1992.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 518(7540):529- 533, 2015.
Jonas Mockus, Vytautas Tiesis, and Antanas Zilinskas. The application of bayesian methods for seeking the extremum. Towards global optimization, 2(1 ((117-11 17-1292): 1978.
Cuong V Nguyen, Yingzhen Li, Thang D Bui, and Richard Turner. Variational continual learning. In International Conference on Learning Representations, 2018.
Timothy Nguyen, Roman Novak, Lechao Xiao, and Jaehoon Lee. Dataset distillation with infinitely wide convolutional networks. arXiv preprint arXiv:2 13034 2021.
Pingho Pan, Siddharth Swaroop, Alexander Immer, Runa Eschenhagen, Richard Turner, and Mo- hammad Emtiyaz. H. Khan. Continual deep learning by functional regularisation memorable past. In Advances in Neural Information Processing Systems, volume 33, pp. 4453-4464. Cur- ran Associates, Inc., 2020. URL htl/tttss///pccceetlel hrr.r//h...1000000000000000300-3
neurips wwwerrpps.ccpppper///2220 cctppppr//22c/////////c/
pdf
Sylvestre- -olvestreAAlvise Rebuffi, Alexander Kolesnikov, Georg Sperl, and Christoph H Lampert. icarl: Incremental classifier and representation learning. In Proceedings of the IEEE conference Computer Vision and Pattern Recognition, pp. 2001-2010, 2017.
Anthony Robins. Catastrophic forgetting, rehearsal and pseudorehearsal. Connection Science, 7(2):
123-146, 1995.
David Rolnick, Arun Ahuja, Jonathan Schwarz, Timothy P Lillicrap. and Greg Wayne. Experience replay for continual learning. In Proceedings of the 33rd International Conference Neural Information Processing Systems, pp. 350-360, 2019.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In Proceedings of the 32nd International Conference on Machine Learning, 2015.
M. Seeger, C. K. Williams, and N. D. Lawrence. Fast forward selection speed up sparse Gaussian process regression. In Ninth International Workshop on Artificial Intelligence. MIT Press, 2003.
Jack Sherman and Winifred Morrison. Adjustment of an inverse matrix corresponding to a change in one element of given matrix. The Annals of Mathematical Statistics, 21(1): 1950.
Jake Snell, Kevin Swersky, and Richard Zemel. Prototypical networks for few-shot learning. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp- 4080-4090, 2017.
Michalis K. Titsias, Jonathan Schwarz, Alexander G. de G. Matthews, Razvan Pascanu, and Yee whye Tch. Functional regularisation for continual learning with gaussian processes. In International Conference on Learning Representations, 2020. /ttttps://openeeview
Jeffrey S Vitter. Random sampling with a reservoir. ACM Transactions on Mathematical Software (TOMS), 11(1):37-57, 1985.
12

---

Published as a conference paper at ICLR 2022
Felix Wiewel and Bin Yang. Entropy-based sample selection for online continual learning. In 2020 28th European Signal Processing Conference (EUSIPCO), pp. 1477-1481. IEEE, 2021.
Jaehong Yoon, Divyam Madaan, Eunho Yang, and Sung Ju Hwang. Online coreset selection for rehearsal-based continual learning. arXiv preprint arXiv:2106.0108: 2021.
Bo Zhao, Konda Reddy Mopuri, and Hakan Bilen. Dataset condensation with gradient matching. In International Conference on Learning Representations, 2020.
13

---

Published as a conference paper at ICLR 2022
A ALGORITHMS AND PSEUDOCODES
In this section we present more algorithms details and pseudocodes for the proposed InfoGS and the reservoir sampling.
A.1 INFOGS
Information improvement thresholding. Let ) E M be the memory point with the small- est MIC. We decide whether to replace it with the new point (x.; y/) by the information improve- ment thresholding. Specifically, let üu, o3 be the running mean and standard deviation of the MIC for all historical observations, and let y be a olding determines whether the new point improves the information by least certain amount,
The information improvement thresh-
if: (TCC,(((x,,)) U.): 2 MTC,, ((xor; y6 M:, + ia + ōz.
(12)
Learnability thresholding. Outliers usually come with a large surprise. To further exclude outliers, propose the learnability thresholding. Specifically, let ju, ōy be the running deviation of the learnability for all historical observations, and let m be hyper-parameter, Then the learnability thresholding determines whether Steam ((mm((x..) y. M) 2 f + 7 * oj. In this way, we deliberately take a certain percentage of data with low learnability out of consideration.
and standard
The overall algorithm, the Information--therrei Greedy Selection (InfoGS), replaces the memory point (Xp. Mbb-) with ). if the new point passes both the information improvement threshold- ing and learnability thresholding. pseudocode shown in Alg 2
Algorithm 2 ieftrmmation-thcoreede Greedy Selection (InfoGS)
Input: Memory M, the batch B", the budget M, the predictor fo.
2: Input: Running mean and stddev for the information criterion: Pa. o, The thresholding ratio
Vi
3: Input: Running mean and stddev for the learnability: ju, ōj. The thresholding ratio n--
4: Update So based on M and (x,, with network learning algorithm.
5: Compute A A and b using the features and targets the memory.
6: for 1, | do
7: if' [M|
8: Update the buffer: + MM (xo., (o-).
9: Update AM and b, based on the
formula.
10: continue
11: Get the batch index with the largest information criterion among those with large learnability:
arg max
MIC,(((s,, M))
(13)
8i8icam ( M)
12:
Get the memory index with the smallest information criterion:
m arg min MIC,, (2Cm, Fm)) M (Xa., you ) (Xmm vm))).
13:
if MIC,, :6); M) 2 IIC,,((Mm Dm ); MM (xo+, yb- (XX Fm)) + (β: + ô, w)
Update the buffer: M - MU (xb*, yb (Xm Mm).
Update And and b, using os- and Fm based on the Shermann-Morrison formula.
16:
else
Update fui, &G frg ôj using Br.
18:
return Buffer M and predictor fe. the statistics jas oū Pu, o Update P4, ã. P4, o; using Bt.
19:
20:
return Buffer M and predictor fe. the statistics ia GG fu, Ō
14

---

Published as a conference paper at ICLR 2022
A.2
RESERVOIR SAMPLING
We present the pseudocodes for reservoir sampling (Vitter 1985), the weighted reservoir sampling
(Chao 1982 Efraimidis & Spirakis 2006), and the flas-balanced reservoir sampling (Chrysakis &
Moens 2020). Worth mentioning, the weighted reservoir sampling becomes equivalent to reservoir
sampling if the score function is constant function. The Mass-balaaced reservoir sampling becomes equivalent to reservoir sampling if only one class is observed.
Algorithm Reservoir Sampling (Vitter 1985)
1: Input: Buffer M, the budget M, the count n, the new data point (X+; V=).
2: if [M] M
3:
(L-MU(x,,)
4: else
5: Generate random integer i within 1...., n + 1.
6: if S M
7: M - MU (X.,
8: return M,n+1.
Algorithm Weighted Reservoir Sampling (Chaol 1982 Efraimidis & Spirakis 2006)
1: Input: Buffer M, budget M, the new data point (x,, V+).
2: Input: The score function and the accumulative score w.
3: Compute the score w, = w(x,, V+).
4: Update the accumulative score w + W..
5: if [M] < M
6: M (x..
7: else
8: Compute normalized score v. min( W. 1). 10
9: Generate random integer i within 1, M based on the probability,
[1 ... Wn M w.).
10: if S M
11: M --- MU (x,,
12: return M, w.
Algorithm Class Balanced Reservoir Sampling (Chyysakis & Moens 2020)
1: Input: Buffer M, the budget M, the new data point (x., V.).
2: Input: The counts n R. for all K classes.
3: if [M] M
4:
M -
5: else
6: Get the class index with the largest count.
7:
if ng ny.
8:
Generate random integer within 1, ng. Replace the i-th class-k point in the memory with (x., V.).
9:
10:
Update the counter: ny. ny, + 1.
11:
else
12:
Let My. be the sub-buffer for class-y.. Update My. using reservoir sampling.
My. ny. ReserviirSamplingMMM.. MMy Dy. (X., V4)).
14:
return M.n.
15

---

Published as a conference paper at ICLR 2022
B EXPERIMENTAL DETAILS
Methods. Our experiments involve Reserovir sampling (RS) Vitter
1985), weighted reservoir sam-
pling with the output-space Hessian (WRS), class-balanced reservoir sampling (CBRS) (Chrysakis) & Moens 2020), greedy gradient sample selection (GSS) (Aljundi et al. 2019b), feature-space clus- tering (FSS- Clust) (Aljundi et al. 2019b), coreset (Borsos et al. 2020), InfoGS, and InfoRS.
The toy Gaussian process regression. We present here the experimental details of the toy GP regression in Figure
We consider GP with the mie-iimensional RBF kernel: k(z, exp(-2(x - x') )²) We fix the variance of the observation noise as 0.04. For the memory points, we generate the inputs using np. ap.linspace(-1, 10). We randomly sample noisy function values from the Gaussian process. For two new points, we fix them as (0, 1) in the left and (1.5, 1) in the right.
Continual learning benchmarks. To create data imbalance, we deliberately tie the task-ID that receives more epochs with the random seed, so that the imbalance appears for all tasks across the random runs. For example, in Split-CIFAR1O, IO, we make sure each of the five tasks chosen twice within 10 random runs. We present the syper-parameters and the configurations for the continual learning experiments in Table | We denote the batch size as bs, and the memory batch size as mbs. Specifically, randomly sample mbs points from the memory buffer in each iteration to regularize the network. We denote the memory budget as M. For all the experiments, we adopt the stochastic gradient descent optimizer and we denote the learning rate Ir. Furthermore, and 3 are the regularization coefficients in the dark experience replay objective; v) is the coefficient of the learnability in the MIC; 7/ is the coefficient of the standard deviation for the information improvement thresholding (InfoGS) or the information thresholding (InfoRS); is the coefficient of the standard deviation for the learnability thresholding (InfoGS).
Table 1: Hyperparameters and Configurations of the Continual Learning Experiments.
Permuted MNIST and Split MNIST
Configuration
Network: FC-[100,100), base epoch n. 1, bs: 128, mbs: 128, M=100, sgd Hyper-parameters
Methods
RS, WRS(var), CBRS
Ir: [0.03, 0.3, a: [0.3, 1.), 3 [0.3, 1.]
GSS, FSS-Clust
Ir: [0.03, 0.1, 0.3). o: [0.3, 1.), 8: [0.3, 1. Memory batch size for gss: 10
Coreset
Ir: [0.001, 0.003, 0.01, 0.03) 0.3, 1.), 8 [0.3), slots: 10
Ir: [0.03, 0.1, 0.3) a: 00.3 1.1. 8: [1.].
InfoGS
7) : [0., 1., 3.1, 7: | 0, 0.3) 71 [0., 1.).
noise sigma: σ 0.3, jitter c o/. 0.1
Ir: [0.03, 0.3), a: 0.3, 1.1, 8 [L.]. 17 [0., 1., 3.1.,.3.,00 3.1,
0.3,
InfoRS
noise sigma: o 0.3, jitter c oh- 0.1
Split CIFARIO and Split MinilmageNet
Network: ResNet-18, bs: 32, mbs: 32, optimizer: sgd
base epoch n, 50 (CIFAR 10) and n. 100 (MinilmageNett)
Configuration
M = 200 (CIFAR1O) and M = 1000 (MinilmageNet), data aug: [pad(4),
Methods
Hyper-parameters
RS, WRS(var), CBRS
Ir: 00.01, 0.03), a : [0.3, 1.). 8 [1.33]
Ir: [0.01, 0.03), a: [0.3, 1.), 0 [1., 3.]. 77 [1.], 7/
0-5, 0.5) [O.].
InfoGS
noise sigma: a 0.3, jitter e - 0.1
Ir: [0.01, 0.03), a : [0.3, 1.), 8 [L., 3.J. n 1., 1-0.3,
InfoRS
o²
noise sigma: σ = 0.3, jitter c c= oz
0.1
16

---

Published as a conference paper at ICLR 2022
C INFORMATION-THEORETI CRITERIA
In this section we present other information-theerriic criteria for online memory selection. Firstly, have introduced the memorable information criterion composed of the learnability and the sur- prise,
((X,, M) =
M, x. x.)l - log X.)..
(14)
Weighted Information Gain. The standard information gain (Cover 1999) is the KL divergence between the updated posterior and the memory posterior, which is further rewritten in E Based on the rewritten form in Eq generalize the information gain weighted combination,
1G,((xx y. MM xM:
[log |w; x. log p(y. MyM;
(15)
where we include a coefficient v to the first term similarly to MIC. We note that IG, = IG. Com- paring IG,, and MIC,, we observe they share the same second surprise term, but differ in the first term. Nevertheless, observing that the first term in IG,, is the expected log probability of the new data point under the updated posterior p(w g. X.), thus it quantifies the "learnability" as well but in different form as in MTC,, Therefore, both MTC, and IG, are weighted combinations of "learaailltt"" and "surprise".
Additionally, under the proposed Bayesian model in Subsec 2.3 the weighted IG can be computed explicit forms as well,
(x),( =1 log. h A b b o²) - A - log A o h, A,, +
(16)
where h, the feature of x..
Entropy Reduction. The entropy reflects the amount of information carried in distribution. Thus another information-theoretii criterion would be how much the entropy can be reduced by adding the new point into the buffer. We propose the entropy reduction criterion as the following.
BR:( == Hlp(w|M) - Hlpp(w| IM, (x, v))],
(17)
where represents the entropy of the distribution. The weight posterior Gaussian distribution under the Bayesian model in Subsec 2.3 thus the entropy can be computed explicitly as well,
(R((xx.U=);;M)) logl M logl A
-
logl(AM x, A
1
logl x A M log(1 + +x Af)))
(18)
We note that this entropy reduction is independent of the target y. of the new point.
Comparing the information-theoretic criteria. Intuitively, we propose the "surprise" to detect unexpected points for gathering the most information in the memory, and propose the "learn- ability" to encourage the consensus between the new point and the memory. As demonstrated by MIC,, and IG,, the "learnability" can be quantified by different explicit expressions. Similarly, the "surprise" criterion might have different expressions as well. This is also illustrated by the predic- tion gain (Graves al. 2017), where the losses before and after one step of gradient updates can be understood as the "surprise" and "learnability", respectively. Therefore, we do not think that MIC, strictly outperforms IG,, since both combine the "surprise" and "learnabiiity". In this paper we pick the MIC,, since its learnability and surprise expressions are in more comparable form, given that both are log predictive densities.
The entropy reduction criterion does not depend on the target y. under the Gaussian weight posterior. Unlike the "surprise" criterion, ER encourages the diversity of inputs. Therefore can behave more like an unsuperised information criterion where output/label information is not captured. For example, the underlying distribution is composed of two input modes (where each mode has different target labels), while one mode is larger in the input space but the other mode is smaller. Then ER might focus more on the larger mode but neglects the smaller mode, yet this problem could be fixed by considering the target observations.
17

---

Published as a conference paper at ICLR 2022
0.550
0.26
0.525
0.24
Valid Accuracy
0.500
0.22
0.475
0.20
0.450
0.18
0.425
IG1
0.16
1
0.400
IGg
0.14
MICa
0.12
0.375
3
10
30
1
10
30
Data Imbalance
Data Imbalance
Figure 7: The performances of InfoRS with varying criteria for Split CIFARIO (left) and Split MinilmageNet (righf). We compare ER, MICI, MIC3, MG,,
We further conduct Split CIFARIO and Split MinilmageNett experiments ER, IG1, IG,, 1IC1, MTC3. The results are shown in Figure 7 We observe IG,, and MTC,, perform similarly in this experiment. Furthermore, the Split CIFARIO 10 experiment, while using 1) = 1 improves over 3 for the Split MinilmageNet experiment. This indicates the importance to balance the surprise and learnability the information- theoretic criteria. We also observe that the entropy reduction achieves competitive results as well, although does not rely on the targets of new points.
compare
observe that using 7 3 improves over 7 for
D MORE EXPERIMENTS
In this section present more experimental results. Firstly, in Table mances of the continual learning benchmarks, accompanying Figure
present the test perfor-
More baselines. We compare the proposed approaches with the gradient sample selection (GSS) (Aljundi et al. 2019b) and Mass-balanced reservoir sampling (CBRS) (Chaudhry et al.) (2119)) as well. We choose the GSS-Greedy algorithm Anjulundii et al. (2019)), which proposes a greedy algo- rithm to minimize gradient similarities in the memory. However, since evaluating the per-example gradients in each iteration causes large computational costs, we only managed to run it for Permuted MNIST and Split MNIST. As argued in the paper, RS is vulnerable to imbalanced data streams. Specifically for classifications, RS tends to select the classes with more appearances and leads to an imbalanced buffer. Blass-balanced reservoir sampling (Chaudhry et al. (209a)) proposes to force a balanced buffer across classes by conducting reservoir sampling separately for each class. Con- sequently, when K classes observed, each class will occupy M/K M/K points in the memory. A pseudocode for CBRS shown in Alg 5 However, CBRS only applicable to fix the class- imbalance problem for classifications. In comparison, InfoRS generally applicable all forms of data imbalance in the problems.
We include GSS and CBRS in Figure We observe that GSS performs worse than other approaches. For the CBRS, we first observe that it sees a performance degradation similar to RS over Permuted MNIST, since CBRS can only fix the inss-immalancee problem, but the classes in Permuted MNIST are always balanced. For the other three benchmarks where class-imbalance appears, CBRS demon- strates the best robustness compared to all approaches. However, as observed Split CIFAR10 and Split Mini CBRS underperforms RS and InfoRS when the data is balanced. We argue that the timing the memory updates influences CBRS here. Because CBRS attempts to maintain class-balanced buffer, it will immediately include new points into the buffer when these points are from previously unseen classes. In consequence, CBRS tends to update the buffer at the beginning of each task for the three Split benchmarks. Then the historical points will be removed earlier. In particular, for the dark experience replay, the stored logits at the beginning of each task will be harmful to network learning well, which also affects the performance of CBRS.
18

---

Published as a conference paper at ICLR 2022
Permuted MNIST
Split MNIST
Split CIFAR10
Split MinilmageNet
0.80
0.24
0.50
Test Accuracy
0.75
0.22
RS
0.45
0.70
WRS
0.20
0.65
GSS
0.6
0.40
InfoGS
0.18
0.60
InfoRS
0.35
CBRS
0.16
0.30
1
3
10
30
1
3
10
30
1
3
10
30
3
10
30
Data Imbalance
Data Imbalance
Data Imbalance
Data Imbalance
Figure& 8: Test performances against data imbalances over continual learning benchmarks. We com- pare RS, weighted RS (WRS) using the output-space Hessian, InfoGS, InfoRS, GSS, and CBRS. For each experiment, we plot the mean and the 95% confidence interval across 10 random seeds.
We also include the feature-space clustering method (FSS-Clust) (Aljundi et al.) 2019b) for Per- muted MNIST and Split MNIST. The results are shown in Table 2 We observe that FSS-Clust also underperforms RS and InfoRS.
Ablation studies for InfoGS and InfoRS. InfoRS is motivated by trying to resolve the timing issue of InfoGS. However, besides the difference of "when to update the memory" between InfoRS and InfoGS, "how update the memory" is still different since InfoRS removes random memory point while InfoGS removes the least informative memory point. Therefore, we further present an ablation algorithm to separate the effect of "when to update the memory" and "how to update the memory". In InfoGS. the new point is added to the memory as long as it passes the information improvement thresholding and the learnability thresholding, thus InfoGS tends update the memory urgently. To bridge the gap between InfoGS and InfoRS, we propose to decide "when to update the memory" by reservoir sampling as well. Specifically, if the new point passes both thresholding in InfoGS, we decide whether to include it in the memory by reservoir sampling. If the point also passes the reservoir sampling, we put the new point into the memory and remove the least informative existing point. The resulting algorithm is represented InfoGS-RS.
Permuted MNIST
Split MNIST
Split CIFAR10
Split MinilmageNet
0.80
0.85
0.24
Test Accuracy
0.80
0.50
0.75
0.75
0.22
0.70
0.45
0.20
0.70
InfoGS
0.65
InfoGS-RS
0.40
InfoRS
0.60
0.18
3
1
3
Data Imbalance
Data Imbalance
Data Imbalance
Data Imbalance
Figure 9: Test performances against data imbalances over continual learning benchmarks. We com- pare InfoGS, InfoRS, and the InfoGS with reservoir sampling (InfoGS-RS)
We compare InfoGS, InfoRS and InfoGS-RS in Figure 9 From the figure we observe that although InfoGS-RS incorporates reservoir sampling to remedy the timing issue, it still underperforms In- foRS when the tasks are balanced. We hypothesize that feature learning might be accounted for the difference. For example, due to the effect of regularizations, the features for the memory points tend to be stable in the learning process, while the features for new points will adapt to learn the under- lying mapping. Due to the evolving features, new points might have a larger chance to be surprising and existing memories could be deleted as result.
We also present the forward transfer and backward transfer for the continual learning benchmarks in Table 3 and Table respectively. The forward and backward transfer is introduced in Lopez-Paz & Ranzato (017)) Specifically, let Rig be the
Forward transfer and backward transfer.
19

---

Published as a conference paper at ICLR 2022
Table 2: The means and standard errors of the continual learning benchmarks.
Method
imbalance=1
imbalance=3
imbalance=10
imbalance=30
Permuted MNIST (M=100)
RS Buzzega ct 2020
75.41 0.32
74.90 0.42
72.90 0.47
66.35 0.41
WRS
73.76 + 0.41
73.97 0.43
71.92 = 0.50
69.44
CBRS Chrysskis Moens 2020)
76.86 0.31
75.07=0.42 0.42
71.02 +
65.73 + 0.72
GSS (Aljundi al. 2019D)
64.46 + 0.48
61.74
59.36 = 1.59
FSS-Clust (Aljundi et al. 2019b)
70.53 0.33
70.12 + 0.57
68.35 0.82
65.82 : 0.90
IntoGS
79.10 0.36
79.03 = 0.29
76.51
0.39
72.59 1 0.69
InfoRS
77.50 + 0.19
77.07 = 0.32
73.97 + 0.48
67.67 = 0.62
Split MNIST (M=100)
RS Buzzega et 2020
81.49 0.72
78.74 1.17
71.94 1.87
52.76 + 1.41
WRS
75.75 1.24
73.90 0.97
68.82
2.39
65.87 + 2.92
CBRS (Chrysaks & Moens
2020
80.96 1.43
79.71
2.28 79.43
75.08 + 2.73
GSS (Aljund1 al. 9b)
45.36 0.95
45.10
44.16
49.54 2.57
FSS-Clust (Aljundı et al
2019b
52.85 1.13
54.59
54.36
55.33 + 2.89
Coreset
(Borsos et 2020
69.77 0.75
2.24
2.99
42.05 + 2.19
InfoGS
78.55 + 1.37
78.35 1.56
10.90
67.19 = 3.52
InfoRS
80.02 1.53
81.48 0.98
73.81 2.43
63.70 = 2.63
Split CIFARIO
(M=200)
RS Buzzega al. 2020
50.32 0.30
48.31 + 0.54
40.59 0.67
32.88 + 1.43
WRS
34.14 + 0.59
37.66 + 0.30
36.65 0.76
CBRS Chrysskss & Moens 2020
48.35 + 0.55
48.64 0.39
47.65
48.90 = 0.56
IntoGS
44.99 + 1.37
48.02 + 0.65
44.59 0.77
46.18 = 0.82
InfoRS
52.61 0.36
51.11 0.35
46.66 0.76
42.10 + 0.71
Split MinilmageNet (M=1000)
RS Buzzega et al. 2020
23.48 0.24
23.19 + 0.30
20.93 0.51
16.89 = 0.67
WRS
17.24 + 0.27
17.04
16.93 + 0.39
15.87 = 0.25
Chrssahrssakis & Moens 2020
21.74 0.07
21.41 0.11
21.10
20.52 0.26
InfoGS
20.05 + 0.15
00.99+0.11
19.51 1:51+000 0.26
19.16 + 0.33
InfoRS
23.83 0.14
23.35 0.22
22.03 0.39
19.69 + 0.44
performance of task j after training task i, and let b; be the performance of task at initialization, then they are defined in the following expression,
backward transfer
(Br, - Rai)
T-1
forward transfer
T (Ra,41 - b1+1).
Intuitively, backward transfer measures how training new tasks can improve previous performances. Forward transfer measures how much performance improvement over a random network can be achieved by training previous tasks. New classes appear in news tasks in Split benchmarks, making the forward transfer almost impossible. relationship between data points in the Permuted MNIST to achieve forward transfer. Therefore, we only report forward transfer for Permuted MNIST and Split MNIST for comparison, while we report backward transfer for all benchmarks.
contrast, it is possible for the network to explore the
20

---

Published as a conference paper at ICLR 2022
Table 3: The means and standard errors of forward transfers in continual learning benchmarks.
Method
imbalance=1
imbalance=3
imbalance=10
imbalance=30
Permuted MNIST (M=100)
RS BBuzzze et al. 2020
0.88 + 0.27
0.73 + 0.24
0.74 + 0.24
0.75 + 0.27
WRS
0.86 + 0.28
0.65 0.22
0.84 = 0.25
0.80 + 0.25
ChRSsChrssakis & Moens 2020
0.90 + 0.22
0.84 0.30
0.72 0.33
0.81 + 0.22
GSS (Aljundi et al. 901
0.74 0.26
0.64 0.29
0.77
0.55 + 0.25
FSS-Cluss (Aljundı et 2019b
1.91 + 0.23
1.89 = 0.28
1.74
1.74 0.34
InfoGS
0.75 + 0.26
0.67 0.32
0.78 + 0.29
0.58 + 0.28
InfoRS
0.64 + 0.30
0.92 0.25
0.82 + 0.25
0.58 + 0.23
Split MNIST (M=100)
RS al.
2020
9.68 + 0.89
-9,68 0.89
-9.68 + 0.89
9.68 = 0.89
WRS
9.68 0.89
9.68
-9.68 + 0.89
99.68 0.89
CBRS(Chrysakis & Moens
2020
-9.68 + 0.89
9.68
+
-9.68 0.89
GSS Aljundi et al. 2019b)
99.68 0.89
9.68
9.68
-9.68 0.89
FSS-Clust (Aljundı et al.
2019b
-10.99 1.58
-10.09
-10.09
-10.09 1.58
Coreset (Borsos el al.
2020
-10.09 + 1.58
-10.99
1.58
-10.09
-10.09 1 1.58
IntoGS InfoRS
-9.68 + 0.89
-9.68 0.89
9.68
-9.68 0.89
-9.68 + 0.89
-9.68 = 0.89
-9.68
-9.68 + 0.89
21

---

Published as a conference paper at ICLR 2022
Table 4: The means and standard emrors of backward transfers in the continual learning benchmarks.
Method
imbalance=l
imbalance=3
imbalance=10
imbalance=30
Permuted MNIST (M=100)
(Buzzeeg et 2020
-19.27 + 0.26
211.30 + 0.31
-23.34 + 0.30
-31.48
0.43
WRS
-21.69 + 0.30
-21.98 + 0.58
-24.60 + 0.72
-28.07 = 0.76
& Moens
2020)
-19.98 + 0.43
-21.30 + 0.39
-24.72 + 0.31
-30.43 = 0.65
GSS (Aljundi et al. 201 9b)
-32.58 + 0.57
-33.53 0.74
-34.55 + 0.96
-36.23
FSS-Clust (Aljundi et al. 2019b
-24.72 0.34
-25.42
1.2 0.59
-27.38
+ 0.82
30.14
InfoGS
15.68 + 0.30
17.20
0.26
19.558
0.28
22.77 1 0.62
InfoRS
-18.16 + 0.22
-20.20
+ 0.52
-22.44
+ 0.51
28.95 + 0.57
Split MNIST (M=100)
RS Buzzega et al. WRS
2020
-2190 + 1.53
25.58 + 1.36
-36.75 + 1.88
-33.51 + 1.32
-24.33 + 1.99
-26.03 = 1.36
-37.78 + 3.19
-99.55
CBRS(Chrysakis & Moens
2020
-22.62 4: 1.29
23.75 + 1.02
-25.33 +: 2.67
2
GSS (Aljundi et al. 2019b)
65.27+1.22
65.58 1.43
-65.59 1.33
FSS-Clust (Aljundı et al.
2019b
-56.49 + 1.45
54.52 2.14
+3.10
+
Coreset
Borsos ct al.
2020
-18.72 + 0.79
34.04 2.88
50.00 + 4.29
-9.13
IntoGS
-21.22 + 1.93
28.59
+ 1.99
33.11 + 3.25
33.881 5.12
InfoRS
18.52 + 1.06
23.81
+ 1.83
31.74 + 3.83
43.37 = 2.71
Split CIFARIO (M-200)
Buzzega et al. WRS
2020
-44.09 + 0.75
-50.74 1.53
-53.00 + 2.26
-2266 4.51
-61.35 1.03
-58.45 0.96
-55.91 + 0.95
-56.33
- 1.51
Chryssasss Moens 2020
-53.92 + 0.50
-55.62 + 0.54
-53.56 + 0.49
-55.32 - 0.83
IntoGS InfoRS
51.92
-43.14 1.26
-42.80 = 1.19
-49.30 1.78 1.78
43.46 = 0.66
-46.72 1.06
-47.02 + 1.75
-51.63 = 2.62
Split MinilmageNet (M=1000)
[Sizeze et al. 2020
-22.52 + 0.27
52.68 + 0.59
-33.62 1.58
-2.667
3.09
WRS
-61.11 + 0.37
60.59 + 0.47
-59.63 + 0.44
-61.28 0.31
(BRS(Chrysakie Moens
2020
-58.33 + 0.15
-57.91 0.17
-58.91 + 0.29
59.34
IntoGS
-58.80 # 0.13
-59.14
-59.87 + 0.34
60.991
InfoRS
-53.04 + 0.23
-53.41 + 0.62
-53.89 + 1.27
-57.28 + 1.06
22

---

Published as a conference paper at ICLR 2022
Ablation studies for 17 and 7/- The learnability ratio 7) controls the weighting between surprise and learaaility. We present an ablation study to investigate the impact of in InfoRS. In addition, the information thresholding parameter NN determines the degree of InfoRS from acting purely randomly to greedily. We also present an ablation study to investigate its impact. The results are shown in
Figure T0
0.55
0.50
Valid Accuracy
0.45
0.40
R=1
R=3
0.35
R=10
3=30
0.30
2
4
6
8
-2
0 Vi
2
Figure 10: Validation performances against the learnability ratio (1)) and the information threshold- ing ratio (74), over Split CIFARIO. We compare InfoRS under various data imbalances (R) and plot the means and 95% confidence intervals. Firstly, for all data imbalance, the best is achieved at around 3 and the best "/ at around O. Thus both hyperparameters are not sensitive to data imbalance. Secondly, for the learnability ratio, setting 1 0 and setting 1) to be large both lead to degraded performances, which indicates the importance of properly balancing surprise and learnability in on- line memory selection. Thirdly, for the information thresholding ratio, setting it to be small makes InfoRS act similarly to RS while setting it to be large makes InfoRS more greedy. Therefore, we observe that when the data is balanced (R 1. R 3), setting % leads to similar optimal per- formances. In contrast, when the data is imbalanced (R 10, R 30). choosing an intermediate 7/s can properly balance the stochasticity and the greediness.
Evolution of test accuracies along with training. In Figure 11 we show how the test accuracies evolve along with seeing more tasks. Specifically, for each dataset, visualize the evolutions in RS and InfoRS over a single random run, where the first task is trained for 30 times epochs than the others.
Permuted MNIST
Split MNIST
1.0
0.90
Accuracy
0.85
0.80
0.8
0.75
0.7
0.70
InfoRS
0
15
0
4
Split CIFAR10
Split MinilmageNet
1.0
0.0
Test Accuracy
0.8
0.6
0.6
0.4
0.4
0.2
Tasks
Tasks
Figure 11: The evolution of test accuracies. The first task is trained for 30 times longer than others.
23

---

Published as a conference paper at ICLR 2022
The TSNE plot with smaller memory. In Figure 2 demonstrated that incorporating learn- ability is important to filter out outliers, using the TSNE plot of 200 selected memories. Here we present another comparison to investigate the scenario with small memory. Specifically, set the memory buffer as 25. The results are shown in Figure T2
Without Learnability
With Learnability
8
7
5
4
3
2
Figure 12: TSNE visualizations of the training data (colored dots, where the color represents the label of the data point) and 25 memory points (black digits, where the digit represents the label of the point) for InfoGS without and with learnability, respectively. With a small memory, we observe that InfoGS without learnability performs similarly to InfoGS with learnability, Both select a representative memory buffer that reflects the training distribution. Because the agent needs to select 25 memories out of data points from 10 classes, the surprise will dominate the selection process, and the outlier issue is not protruding. Therefore, incorporating lcarnability is not critical the selection when the memory buffer is very small.
Impact of and 3. The logit regularization coefficient and the label regularization coefficient in DER++ control the regularization degree of the replay buffer. We further present an experiment investigate their impact separately, in Figure B
0.55
0.50
Valid Accuracy
0.45
0.40
R=1
R=3
0.35
R=10
R=30
0.0
0.3
1.0
3.0
0.00.3
1.0
3.0
10.0
a
B
Figure 13: Validation performances against the logit regularization coefficient (a) and the label reg- ularization coefficient (3) in DER++ over Split 10. We compare InfoRS under various data imbalances (R) and plot the means and 95% confidence intervals. We observe that the performance not sensitive and 8.
24

---

Published as a conference paper at ICLR 2022
E PROOFS
In this section we provide necessary proofs.
Information Gain. We rewrite the information gain as the following,
(.) = KL (p(w1/ ( MMi XM.X. x. pllpplpppwWw (ilpp(wwMm XM))
log [(w] M+ X. x.
Mi
Mi X.M)
log p(w, ye N.M X x.)
Bptwlu- x.x
[logp(V- [wlll,ydl log Io::
B
[lo [w;]:,,.) logply. MMi X.).
(19)
Proof. By applying Jensen's inequality we have
logp(v.1v.. MMi XM, x,)l -y- M.
2 Mw..
(20)
Information Criterion for Bayesian Linear Regression. Given a new point U.), let h, be the corresponding feature, then the criterion is represented as,
s( ((,, vx); M) 1) log M... X x+),,; -.. logp(y- ymM XM)-
(21)
Given the memory M, the posterior distribution of weights can be computed as,
p(wlymi H.) = -A(A bw, AM))
b'
(22)
HM M + ccla -1 for o² oz and b = HLYM Similarly let where the matrix AM = HHHH
M = MMMU,, y.), AMt AM h.h! and b b. h,ye. then weight posterior given the memory M can be computed as,
p(wlym== H N(Aji bMt o² d'Am)))
(23)
Thus the predictive distributions can be represented as,
V'lymt ~ A/b, A- D o 2 AM h, + +03), 8.lym (y. AM, o Ajth, h, + o²). which directly leads to the expression of the information criterion
(24)
(25)
MIC,, v+): log (y.lhh A Ard bM- hh A Mi h, 0²)
Nog h A bu, A A + o²).
We combine this with the definition of the log density
- = (("7
1/ vv-a 2 + log (2g(2
log Nog/a(yla, b) = log
=
b/22
of Gaussian A (a, b). Let denote with 44 and a. the updated mean and variance, and with μ and a_ the old mean and variance (not to be confused with the noise variance a. Then
= ( ( a+
2
--) ((=-)) α_
2
H+t
log((2o'))
+
log (2TO²))
25


Reviews:
[{"review_id": "XzJl5b3_44q", "reviewer": "Reviewer_6ZWf", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "", "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": "Objective of the work:\n* The paper extends the existing research direction in general continual learning. The key contribution is proposing the criteria to select and replace the existing points in the memory buffer.\n\nStrong points:\n* A new method for online memory selection. The surprise captures how unexpected a new point is given the memory, and allows us to include new information in the memory. The learnability captures how much of this new information can be absorbed without interference, allowing us to avoid outliers.\n* The proposed Memorable Information Criterion (MIC) is a weighted combination of the proposed learnability and surprise scores. The authors also connect that MIC is related to Information Gain. In the appendix, the paper has compared these criteria (MIC, IG, ER) thoroughly.\n\nWeak points:\n* The surprise score is related to the uncertainty score in literature which has been widely used to select unseen points. While the learnability makes sense to distinguish the unfamiliar and outlier points. Having said that, the reviewer thinks that the learnability score can make the algorithm too preservative to learn new information.\n\n* The performance may critically depend on balancing how much we want to “surprise” versus “learn” through $\\eta$. It is highly recommended to have the ablation study with respect to $\\eta$.\n\n* Bayesian linear regression requires matrix inversion of a matrix $d \\times d$ where $d$ is the feature dimension. The Sherman-Morrison Formula, Eq. (11), can be used to efficiently update the inverse matrix. However, while the reviewer acknowledges the trick works well in practice, the reviewer doesn't see this is a great technical contribution of the paper.\n\n\nPresentation: \n* The paper is in general well written and easy to follow.\n\nReproducibility:\n* The results appear to be reproducible though I would encourage the authors to release their code to enable better validation of their claims.\n\n\nMinor points:\n* The author has demonstrated the effectiveness of the proposed criteria using a greedy algorithm to replace the existing points with the new points if certain condition is met. It could be interesting to consider either replacing (as the proposed framework) versus expanding without replacing. The reviewer thinks that we may need to enlarge the memory buffer overtime to learn more tasks. However, this would be out of the scope of the paper.\n\n* In Figure 2, it is not clear to compare the middle figure and right figure to see the effect of learnability.\n\n* The paper presents a scalable Bayesian model that can compute surprise and learnability with a small computational footprint by exploiting rank-one matrix structures. Instead of using a deep network and Bayesian linear model, I am wondering if it is better to directly train a Bayesian neural network for estimating the uncertainty?\n\n* a footnote must be placed at the end of a clause or sentence, such as adding the number after the comma or full stop.\n\n", "summary_of_the_paper": "This paper considers an online memory selection task for continual learning applications. The paper proposes a new (information-theoretic) criterion to pick informative points and void outliers. This criterion is a combination of the surprise and learnability score. In addition, the paper presents a stochastic information-theoretic reservoir sampler (InfoRS) to sample among selective points with high information.\n\nThe paper empirically demonstrates the proposed criteria encourage to select representative memories for learning the underlying function. They consider continual learning benchmark as well as ablation studies of data imbalance. \n", "summary_of_the_review": "The key contribution is proposing the criteria to select and replace the existing points in the memory buffer. However, the technical novelty is limited. The paper includes several techniques which have been widely used elsewhere. The surprise (uncertainty estimation) has been widely used in literature. The Bayesian linear regression and the rank-one update trick are also well studied.\n\nEmpirically, the performance may critically depend on balancing how much we want to “surprise” vs “learn”. This should be well studied in the experiments. Perhaps, the paper can propose a technique to adaptively learn $\\eta$ over time.\n\nThe reviewer thinks the paper is currently at the borderline.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Munf8jCyDQ", "reviewer": "Reviewer_PFQ2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "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": "", "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": "Strengths:\n\n1. I think that the paper was easy to follow overall, and the MIC criterion is intuitive. The tSNE plots (of the selected example for the memory of size 200) showing the ablation study was also quite interesting. \n2. The proposed algorithm outperformed RS and other mentioned baselines, without too much computational overhead over RS. \n3. Authors do study over other possible metrics than MIC, including Entropy Reduction, therefore empirically justifying the criterion. \n\nWeakness: This subsection is a collection of doubts, suggestions about some more experiments (including other baselines), and how this submission can be improved overall. \n\nBaselines and Performance metrics:\n1.  I suggest including the paper [1] and online k-medoid clustering. [1] “Coresets via Bilevel Optimization for Continual Learning and Streaming” NeurIPS’20. \n2. In my opinion, it is also important to report the backward transfer or forgetting metric, similar to the DER paper.\n3. While the manuscript contains final testing results for different imbalance levels, I think for CL papers a plot of accuracy after each task provides more information ( For example, see Fig 3 in the A-GEM paper -  EFFICIENT LIFELONG LEARNING WITH A-GEM).\n\nTechnical Questions:\n\n1. How sensitive is the performance with the thresholding hyperparameter?\n2. Fig (5) right, similar to infoRS, I think for RS one also needs the confidence bars. \n3. In the section about robustness to imbalance, does a different seed change the task ID in which we add more epochs? Moreover (more of a sanity check), but do authors keep the task-iD same across different “R” values?\n4. Algorithm (2): What is the need to compute A_M^-1 and b_M when the memory is not full? Cannot one just do that once we fill in the memory, and use features based on the new parameters?  \n5. Algorithm (2): Rather a technical question - why are we only choosing one example from each batch? There can be a case that we have two examples with similar (but not the same) and high MIC values and are learnable (two different classes, right when we begin a new task). \n6. Regarding GSS: Are authors using the GSS-IQP, or the GSS-Greedy? Moreover, one easy trick one can do to accelerate GSS is to consider gradient with respect to the last layer only, the way it is done in the paper [1] (See [2] as well). [1] Coresets for Data-efficient Training of Machine Learning Models, ICML’20. [2] Not all samples are created equal: Deep learning with importance sampling, ICML’18. \nRegarding GSS: Rather a sanity check, but do authors use DER++ loss in this case for the fair comparison?\n7. In Section E appendix (Proof), equation (19), where the KL is expanded, in my opinion, the numerator seems notationally odd. That is, why is x_{\\ast} mentioned as a conditioned variable and as a parameter at the same time. Wouldn’t it suffice to just use it as a conditioned variable? \n\nTechnical suggestions:\n1. Fig (2), please show how does the memory look like in the tSNE plot for the cases with small sizes such as 10/25 for RS and infoRS (w/ and w/o learnability)  \n2. What is mentioned here as DER is actually DER++ in the original paper.\n3. In the related works section, which talks about dataset distillation, there is another paper [1] (ICLR’21) that also talks about dataset distillation with applications in continual learning. [1] Dataset Condensation with Gradient Matching.\n\nWriting Suggestions:\n\n1. In equation (1), I think it will be good to not use \\theta for both h and g. \n2. Equation (3), during the overall update step, we update memory as well as the network parameters. Therefore, I suggest using notations accordingly.\n3. In the algorithm block, I would recommend adding line numbers, which improve readability and cross-referencing in a discussion. \n4. Section 2.1, last paragraph: Add spacing after the period right before the “Furthermore”.\n", "summary_of_the_paper": "This work targets the problem of Continual Learning (CL) and In particular, the problem of populating the buffer memory in the Experience Replay (ER)-based paradigm. In ER, we are allowed to store a small subset of the incoming data stream, therefore deciding on a good policy to populate the memory buffer is important. The paper proposes MEMORABLE INFORMATION CRITERION (MIC) which is a combination of the surprisal and learnability of an incoming example and further motivates this with a  bayesian analysis. Using MIC, it introduces two algorithms, namely, InfoRS and infoGS for buffer update. The paper includes experiments on standard CL datasets with a focus on General Continual Learning (GCL) guideline, which focuses on not having dependence on task boundaries. Finally, it reports the proposed method's performance on imbalanced data streams and shows that infoRS outperformed reservoir sampling, GSS, and some other baselines. \n", "summary_of_the_review": "It is an interesting work, however, lacks discussion about some baselines (not mentioned in the paper) and other performance metrics (about forgetting, BWT). There are some questions (mentioned in the detailed review) that need to be answered in order to make it a strong submission. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "I2D7xaQiS-p", "reviewer": "Reviewer_TW8M", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "", "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": "Strengths:\n\n+ The proposed methods seem fairly natural. In particular, the notion of surprise and learnability seem well-suited to the current problem at hand. The computation of the Bayesian posteriors is also natural and the Gaussian assumption, together with conjugacy, results in efficient updates, which is nice. \n\n+ The InfoRS algorithm also seems natural for sampling. \n\nWeaknesses:\n\n- It would be preferable for the authors to consider the effects of each of their proposed modules separately -- surprise, learnability as well as InfoRS. Currently from the experimental section, it is unclear which module contributes to which aspect of the improvement. An ablation study would be useful. \n\n- I am wondering whether the authors have examined the effect of the many hyperparameters in their study such as \\eta, \\alpha and \\beta. \n\n- The datasets used seem rather simplistic, just MNIST and CIFAR10. ", "summary_of_the_paper": "This paper considers task-free continual learning in the context of online memory selection. The author consider the use of information-theoretic principles and propose the surprise and learnability criteria to select informative points and avoid outliers. The authors also propose InfoRS to sample among selective points with high information. The methods are validated on continual learning benchmark datasets, and show efficiency and improvements over existing approaches. ", "summary_of_the_review": "Generally, the paper has some novel contributions but also some minor weaknesses. If the authors can address the weaknesses/queries I raised in the main review, I'm happy to increase my score. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: One way of avoiding catastrophic forgetting in continual learning is through keeping a memory buffer for experience replay.  This paper addresses the problem of online selection of representative samples for populating such memory buffer for experience replay.  The paper proposes novel information-theoretic criteria that selects samples that captures surprise (samples that are most informative) and learnability (to avoid outliers).  They utilize a Bayesian formulation to quantify informativeness. They provide two algorithms: a greedy approach, and an approach that takes timing (when to) update memory into account based on reservoir sampling to mitigate possible issues with class imbalance.

Pros:  The paper is well written and organized.  It was easy to follow. The formulation is novel and technically sound. The idea of taking learnability into account is novel and interesting.  It provides a nice way of avoiding outliers and balancing surprising information. The authors presented the motivation for each part of the framework well.  

Cons: To understand the contribution of each component of the formulation and competing criteria, an ablation study is needed.
Reviewers had several detailed suggestions and questions, including sensitivity to hyperparameters, additional citations, additional data sets beyond MNIST and CIFAR10, etc.  

In the rebuttal, the authors have addressed several of these concerns.  Please make sure to include and incorporate reviewer suggestions in the final revised version.
Decision: Accept (Poster)