INFORMATION-THEORETIC ONLINE MEMORY SELEC-
Year: 2021

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 surprise and the 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 the timing to update the memory, we introduce a stochastic informationtheoretic 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 the efficiency and efficacy of proposed approaches.

heading: 1 INTRODUCTION
text: Continual learning (Robins, 1995; Goodfellow et al., 2013; Kirkpatrick et al., 2017) aims at training models through a non-stationary data stream without catastrophic forgetting of past experiences. Specifically, replay-based methods (Lopez-Paz & Ranzato, 2017; Rebuffi et al., 2017; Rolnick et 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 realistic, general continual learning (GCL) (Aljundi et al., 2019a; Delange et al., 2021; Buzzega et 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 to be both efficient and effective.
Due to the online constraint, only a few memory selection methods are applicable to GCL. A selection method compatible with GCL is reservoir sampling (RS) (Vitter, 1985). In particular, RS can be used to randomly extract a uniform subset from a data stream in a single pass, and it showed competitive 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-based sample selection (GSS) (Aljundi et 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-theoretic perspective, where the memory 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 unexpected 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 interference, allowing us to avoid outliers. Then we present a scalable Bayesian model that can compute surprise and learnability with a small computational footprint by exploiting rank-one matrix structures. Finally, we demonstrate the effectiveness of the proposed criteria using a greedy algorithm.
While keeping a representative memory is essential, we show that the timing of the memory updates can also be crucial 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 phenomenon 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-theoretic criteria and RS, we modify reservoir sampling to select informative points only. This filters out uninformative points, and thus encourages a diverse memory and improves the robustness against data imbalance.
Empirically, we demonstrate that the proposed information-theoretic 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 proposed algorithms by showing their small computational overheads over the standard RS.

heading: 2 MEMORABLE INFORMATION CRITERION FOR ONLINE MEMORY SELECTION
text: Firstly we formalize the online memory selection problem and propose our information-theoretic criteria to detect informative points. Then we introduce a Bayesian model to compute the proposed criteria efficiently. Finally, we demonstrate the usefulness of the criteria in a greedy algorithm.

heading: 2.1 ONLINE MEMORY SELECTION
text: 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,
fθ(·) = gθg (hθh(·)), (1)
where θ := (θg,θh). The base network hθh(x) extracts the feature representation of the input x, and gθg maps the representation to predictions. The function gθg is usually a simple module, such as a linear layer (Krizhevsky et al., 2012) or mean-of-neighbours (Snell et al., 2017) mapping to the softmax logits. We assume the memory buffer contains the inputs, features, predictions, and targets,
M = {(xm,hm,gm, ym)}Mm=1 . (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 = {(xb, yb)}Bb=1 be the observed batch in one iteration, a general update formula can be expressed as,
(θ,M)←− (θ,M,B) . (3)
We emphasize that updating the predictor parameters θ and updating the memoryM 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 θ using GEM (Lopez-Paz & Ranzato, 2017) or experience replay (Chaudhry et al., 2019b). This section focuses on how to maintain a representative memory M online, while how to update the predictor fθ is not our focus. Furthermore, unlike task-based continual learning (Kirkpatrick et al., 2017), we assume the agent receives only the data stream without observing task boundaries. This scenario is more difficult 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 a more balanced memory and avoid catastrophic forgetting.

heading: 2.2 MEMORABLE INFORMATION CRITERION
text: 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;x) be the likelihood of the observation y given the deterministic input x dependent on the random model parameter w,1 and we denote by p(w) the prior distribution. Then the posterior of w and the predictive distribution of new
1The density p and the parameter w here are left completely generic.
data points can be inferred according to Bayes’s rule. Also worth mentioning, the Bayesian model is introduced merely for memory selection, which is different from the predictor fθ.
In each iteration of online memory selection, the agent decides whether to include the new data point (x?, y?) into the memoryM. To this end, we present information-theoretic criteria based on the Bayesian model to evaluate the usefulness of the new data point. For notational simplicity, we denote by XM 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?, y?) brings little information intoM. Thus we propose to measure the “surprise” of the new point given the memory. We define the surprise criterion of (x?, y?) givenM as the negative log conditional probability,
ssurp((x?, y?);M) = − log p(y?|yM;XM,x?), (4) where p(y?|yM;XM,x?) = ∫ p(y?|w;x?)p(w|yM;XM)dw. Intuitively, if (x?, y?) comes from a new task, it 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.
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,
slearn((x?, y?);M) = log p(y′?|y?,yM;XM,x?)|y′?=y? , (5)
where we use y′? and y? to represent two realizations of the same random variable. Intuitively, the learnability measures the consensus between the new point and the memory. We illustrate the utility of learnability through a toy example in Figure 1. We use a Gaussian process with the RBF kernel 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 ?) 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 are surprising to 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.
Memorable Information Criterion (MIC). Given η ≥ 0, we propose the Memorable Information Criterion (MIC) as a combination of the surprise and learnability of the new point,
MICη((x?, y?);M) = ηslearn((x?, y?);M) + ssurp((x?, y?);M). (6) Notably, the MIC is related to the information gain (IG) (Cover, 1999): IG((x?, y?);M) = KL (p(w|y?,yM;XM,x?)||p(w|yM;XM)). By Appendix E, IG can be rewritten as,
IG((x?, y?);M) = Ep(w|y?,yM;XM,x?) [log p(y?|w;x?)]− log p(y?|yM;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((x?, y?);M) ≥ IG((x?, y?);M) ≥ 0. Given the connection, we 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 Sec C.

heading: 2.3 AN EFFICIENT BAYESIAN MODEL
text: Computing the MIC requires inferring Bayesian posteriors, which can be computationally unfeasible for complicated Bayesian models. Now we combine deep networks and Bayesian linear models to make computing the MIC efficient. Deep networks are well-known for learning meaningful
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 hθh as a feature extractor and establish the Bayesian model from the feature space to the target space. Precisely, let d0 be the feature dimension and h0 = hθh(x) ∈ Rd0 be the feature of the input x, we compute the normalized feature h := [h>0 , 1] >/ √ d for d := d0 + 1. Then we consider a Bayesian linear model,
y = w>h + , ∼ N (0, σ2) . (8)
We consider an isotropic Gaussian prior w ∼ N (0, σ2wI). Denoting the features and the targets in the buffer as HM ∈ RM×d and yM ∈ RM respectively, the weight posterior can be computed as,
p(w|yM;HM) = N (A−1MbM, σ 2A−1M ), (9)
where we define A−1M = ( H>MHM + cId )−1 for c = σ 2 σ2w and bM = H>MyM. Given a new point (x?, y?), let h? be the corresponding feature, then the MIC can be computed explicitly as,
MICη((x?, y?);M) =η logN (y?|h>? A−1M+bM+ , σ 2h>? A −1 M+h? + σ 2)
− logN (y?|h>? A−1MbM, σ 2h>? A −1 Mh? + σ
2), (10)
where AM+ = AM + h?h>? and bM+ = bM + h?y?. A derivation is provided in Appendix E.
Efficient computation. Computing the MIC still involves the matrix inversions A−1M+ and A −1 M . Fortunately, since AM+ differ with AM by a rank-one matrix, its inverse can be computed efficiently given A−1M according to the Sherman-Morrison Formula (Sherman & Morrison, 1950),
A−1M+ = A −1 M −
A−1Mh?h > ? A −1 M 1 + h>? A −1 Mh? . (11)
Moreover, A−1M+ needs not to be computed explicitly either since the MIC expression involves only the matrix vector product A−1M+h?. As a result, given A −1 M and bM, the computational cost of the MIC is merely O(d2). One can store A−1M and bM 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, A−1M and bM can be updated efficiently in O(d2) as well using the Sherman-Morrison formula. Feature update. Since the predictor evolves along with memory selection, the feature of each input also changes. The feature hθ(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, we notice that the memory is usually used to aid learning in the online process, such as memory replay in continual learning (Rebuffi et al., 2017) or experience replay in deep Q learning (Mnih et al., 2015). Therefore, we update the memory features whenever the agent forwards the memories through the network,2 which is free of computational overheads. Finally, we note that the matrix A−1M needs to be recomputed when the memory features are updated, which takes O(d3) computations using a Cholesky decomposition. 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 1 ≤ y ≤ K be the label among K classes, we use the Bayesian model to regress the one-hot vector ŷ ∈ RK , where ŷi = δiy, i = 1, ..,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.

heading: 2.4 DEMONSTRATING THE CRITERIA BY A GREEDY ALGORITHM
text: Using a greedy algorithm for online memory selection, we show that the proposed informationtheoretic 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?, y?), the buffer M, and a data point (xm, ym) ∈ M. LetM∗,−m := M∪ (x?, y?)\(xm, ym). We measure the informativeness
2The features are updated in every iteration in our continual learning experiments, due to the memory replay.
of (xm, ym) according to its MIC for the pseudo buffer M?,−m, i.e., MICη((xm, ym);M?,−m). Notably, the criterion for memories is comparable to the criterion for the new point, since MICη((x?, y?);M) = MICη((x?, y?);M?,−?) can be expressed similarly. Let (xb? , yb?) ∈ M be the memory point with the smallest MIC. We decide whether to replace it with the new point (x?, y?). Specifically, we present information improvement thresholding to determine whether the new point improves the information by at least a certain amount. We present learnability thresholding to only add points with high learnability. The overall algorithm, Informationtheoretic Greedy Selection (InfoGS), replaces (xb? , yb?) with (x?, y?), if the new point passes both thresholding. A detailed description and the pseudocode are shown in Alg 2 in the Appendix.
A toy experiment. Using InfoGS, we illustrate the proposed criteria by a toy experiment. We generate the toy dataset by training a ResNet-18 (He et al., 2016) for CIFAR-10 classification and storing the network features and the targets of 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 observes 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 “relearn” performance, where we fit 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 of 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 2.

heading: 3 INFORMATION-THEORETIC RESERVOIR SAMPLING
text: In this section we incorporate the MIC into continual learning. For training the prediction network, we 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 θ by minimizing the following objective,
L(θ;M) = 1 |B| l(B;θ) + α M M∑ m=1 ‖fθ(xm)− gm‖22 + β M M∑ m=1 l((xm, ym);θ),
where the objective is composed of (1) the fitting loss of the current batch, such as the cross entropy; (2) the mean squared loss between the predictive logits fθ(xm) of the memory input xm and its memory logits gm; (3) the fitting loss of the memory. α and β are hyper-parameters.
While straightforward, naively employing InfoGS to curate the buffer suffers the timing issue we identify for continual learning. We present a new algorithm, the information-theoretic reservoir sampling, which integrates the MIC into RS and achieves improved robustness against data imbalance.
Algorithm 1 Information-theoretic Reservoir Sampling (InfoRS)
1: Input: MemoryM and matrices A−1M ,bM, the batch B, the predictor parameter θ. 2: Input: The reservoir count n and the budget M . 3: Input: Running mean and stddev for the MIC: µ̂i, σ̂i. The thresholding ratio γi. 4: Update the predictor parameter θ based onM and B.3 // Predictor Update 5: Update the features for the memory points used in replay, and update A−1M ,bM accordingly. 6: for (x?, y?) in B do 7: if |M| < M or MICη((x?, y?);M) ≥ µ̂i + σ̂i ∗ γi // Information Thresholding 8: UpdateM, n←− ReservoirSampling(M,M, n, (x?, y?)). // Memory Update 9: Update A−1M ,bM based on the Sherman-Morrison formula ifM is updated.
10: Update µ̂i, σ̂i using the criterion MICη((x?, y?);M). // Running Moments Update 11: return BufferM and A−1M ,bM. The reservoir count n and statistics µ̂i, σ̂i. The updated θ.

heading: 3.1 THE IMPORTANCE OF THE TIMING TO UPDATE THE MEMORY
text: While maintaining a representative memory is critical to properly regularize an online CL process, we will now discuss and empirically show that when the memory is updated (i.e., the update timing) is also influential. We begin by giving an intuition of this issue with a mind experiment, where the agent sequentially observes the data from two tasks T1 and T2. At the time t of task switching, the agent has a memory with M examples from T1. Assume that the agent will update the memory by removing M2 examples from T1 and adding M 2 examples from T2 at the time t + ∆t. Since the T2 examples are repeatedly visited after time t, it is favorable to use a large ∆t. In contrast, updating the memory at the beginning of T2 with ∆t = 0, leads to degrading T1 regularizations too early.
We further demonstrate this by a Split CIFAR10 experiment with 5 tasks. After ∆t iterations of each task Ti for i = 1, ..., 5, we randomly replace 200i memories with the examples from Ti. In Figure 3, we report the final accuracies with varying ∆t to change the timing of memory updates, for both α = 0, β = 1 and α = 0.3, β = 1 in dark experience replay. We observe that updating the memory early in each task leads to worse performances. The phenomenon is more distinct for α = 0.3, where storing premature logits gm early in each task actually hurts the network learning.
Reservoir sampling acts randomly to maintain a uniform sample from the past stream, thus it tends not to update the buffer immediately at a new task. However, InfoGS accumulates surprising examples 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. Moreover, 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.

heading: 3.2 INFORMATION-THEORETIC RESERVOIR SAMPLING
text: To alleviate the timing problem of InfoGS, we present the information-theoretic reservoir sampling (InfoRS) algorithm, which attempts to bring together the merits of both the information-theoretic 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 µ̂i, σ̂i be the running mean and standard deviation of the MICs for all historical observations, and let γi be a hyper-parameter. InfoRS selects the point (x?, y?) for reservoir sampling if its MIC passes the information threshold: MICη((x?, y?);M) ≥ µ̂i + σ̂i ∗ γi. The overall algorithm of InfoRS is shown in Alg 1 and we also provide the algorithm of ReservoirSampling in Alg 3 in the Appendix.
3We use DER++ in Eq 12 for updating the predictor, but other algorithms can be adopted as well.
Worth mentioning, a point (x?, y?) passing the information threshold results in itself being considered 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 InfoGS. 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 observations, 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 a 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.

heading: 4 RELATED WORKS
text: Experience replay for continual learning. Experience replay is widely adopted in continual learning to prevent catastrophic forgetting (Robins, 1995; Lopez-Paz & Ranzato, 2017; Rebuffi et al., 2017; Rolnick et al., 2019). However, the majority of approaches focus on task-based 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., 2021; Yoon et al., 2021). In contrast, reservoir sampling (Vitter, 1985) is used (Rolnick et al., 2019; Chaudhry et al., 2019b; Buzzega et al., 2020; Isele & Cosgun, 2018; Balaji et al., 2020) to update the memory online and maintain uniform samples from the stream. RS is generalized to class-balanced RS (CBRS) that selects uniform samples over each class (Chrysakis & Moens, 2020; Wiewel & Yang, 2021; Kim et al., 2020), 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 learning, 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 highdimensional inputs is crucial. Borsos et al. (2020) present the weighted coreset selection and extend it to GCL. However, the method incurs large computational costs and is limited to a small memory.
More applications with online data selection. Apart from preventing catastrophic forgetting, online selecting data is also useful for improving the computational and memory efficiencies of learning systems. Deep Q-learning (Mnih et al., 2015) adopts past experiences to 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((x?, y?);θ)−L((x?, y?);θ′), where θ′ is the parameter after the network updates θ for one step using (x?, 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 θ′ is obtained by one-step gradient updates unlike our exact inference. Bayesian optimization (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., 2021) aims at a small set training on which achieves similar performances to training on the original dataset. Sparse Gaussian processes also consider the selection of inducing points (Seeger et al., 2003; Csato & Opper, 2002; Bui et al., 2017). For instance, Seeger et al. (2003) adopt the information gain to select inducing points for a scalable Gaussian process method.

heading: 5 EXPERIMENTS
text: 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 et 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 as bs, and the memory batch size as mbs. Specifically, we randomly sample mbs 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 as lr.
Benchmarks. The benchmarks involve Permuted MNIST, Split MNIST, Split CIFAR10, and Split MiniImageNet. 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 CIFAR10, 10 classes are split into 5 tasks evenly; for Split MiniImageNet, 100 classes are split into 10 tasks evenly. We use a 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) generalizes 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 a WRS baseline with the total output-space Hessian (Pan et al., 2020) as importance weights. Specifically, if p1:K are the predictive probabilities for K classes of a point, its total output-space Hessian is computed as 1 − ∑K k=1 p 2 i . Intuitively, the total Hessian of a point is small if it has a confident 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., 2019b) minimizes the gradient similarities in the memory. We present the comparisons with CBRS and GSS in Figure 8 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, bs=128, mbs=128. For Split CIFAR10 and Split MiniImageNet, we adopt a standard ResNet-18 (He et al., 2016) and set bs=32, mbs=32.4 We set M = 200 and M = 1000 for Split CIFAR10 and Split MiniImageNet, respectively. To tune the hyper-parameters, we pick 10% of training data as the validation set, then we pick the best 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 hyperparameter, averaged over 10 seeds. The tuning hyper-parameters include the learning rate lr, the logit regularization coefficient α, the target regularization coefficient β, the learnability ratio η, and the information thresholding ratio γi, if needed. We present the detailed hyper-parameters in Table 1.
4Our ResNet contains a MaxPooling with window shape 3 and stride 2 after the first ReLU, which is absent in Buzzega et al. (2020). Our initial conv uses kernel 7 and stride 2, compared to their kernel 3 and stride 1.
Robustness against data imbalance. To simulate data imbalance, we vary training epochs across different tasks. Specifically, given the base epoch ne > 0 and data imbalance r ≥ 1, we randomly pick one task T? and train it for ne ∗ r epochs, while we train the other tasks for ne epochs. Thus T? 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 r = 1, 3, 10, 30. We set ne = 1 for Permuted MNIST and Split MNIST, ne = 50 for Split CIFAR10, and ne = 100 for Split MiniImageNet. The results are shown in Figure 4. Moreover, Figure 4 also compares InfoRS and RS across varying budgets over Split CIFAR10.
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 is 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 count of InfoRS for Split MiniImageNet with data imbalance r = 10. The results are visualized in Figure 5. Furthermore, a good memory should contain similar example amounts for all classes. Let M1:K be the example numbers in the memory for all K classes. For each method, we compute the variance 1K ∑ kM 2 k − ( 1K ∑ kMk) 2. Figure 5 also visualizes the variances for Split MiniImageNet.
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 running time over Split MiniImageNet with the data imbalance r = 30. As shown in Figure 6, InfoGS and InfoRS incur small computational overheads compared to RS. This result demonstrates the efficiency of the proprosed algorithms.

heading: 6 CONCLUSION
text: We presented information-theoretic approaches for online memory selection. Specifically, we proposed to maintain the most information in the memory by evaluating new points along two dimensions: the surprise and the learnability, which are shown to 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 threshold in InfoRS avoids duplicate points in the memory, improving robustness against imbalanced data streams. Moreover, our proposed algorithms run efficiently, thanks to the proposed Bayesian model.
ETHICS STATEMENT
This paper introduces a novel and efficient mechanism for selecting examples into an online memory. The proposed memory selection approach is applied to 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 to store all the data into a 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 a 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 we discuss our efforts to facilitate the reproducibility of the paper. Firstly, we present detailed pseudocodes for the proposed InfoRS (Alg 1) and InfoGS (Alg 2). We also present pseudocodes for the baselines used in the experiments, including reservoir sampling (Alg 3), weighted reservoir sampling (Alg 4), and class-balanced reservoir sampling (Alg 5). Moreover, we introduce the process to tune the hyper-parameters in the experimental section, and we present in Table 1 the detailed hyper-parameters we tuned for the involved approaches. In addition, we show detailed derivations and proofs in Sec E. Finally, besides the visualization figures, we present the precise means and standard errors of the experiments in Table 2.

heading: A ALGORITHMS AND PSEUDOCODES
text: 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 (xb? , yb?) ∈M be the memory point with the smallest MIC. We decide whether to replace it with the new point (x?, y?) by the information improvement thresholding. Specifically, let µ̂i, σ̂i be the running mean and standard deviation of the MIC for all historical observations, and let γi be a hyper-parameter. The information improvement thresholding determines whether the new point improves the information by at least a certain amount,
if: MICη((x?, y?);M) ≥ MICη((xb? , yb?);M∗,−b?) + µ̂i + γi ∗ σ̂i. (12)
Learnability thresholding. Outliers usually come with a large surprise. To further exclude outliers, we propose the learnability thresholding. Specifically, let µ̂l, σ̂l be the running mean and standard deviation of the learnability for all historical observations, and let γl be a hyper-parameter. Then the learnability thresholding determines whether slearn((x?, y?);M) ≥ µ̂l + γl ∗ σ̂l. In this way, we deliberately take a certain percentage of data with low learnability out of consideration.
The overall algorithm, the Information-theoretic Greedy Selection (InfoGS), replaces the memory point (xb? , yb?) with (x?, y?), if the new point passes both the information improvement thresholding and learnability thresholding. A pseudocode is shown in Alg 2.
Algorithm 2 Information-theoretic Greedy Selection (InfoGS)
1: Input: MemoryM, the batch Bt, the budget M , the predictor fθ. 2: Input: Running mean and stddev for the information criterion: µ̂i, σ̂i. The thresholding ratio γi. 3: Input: Running mean and stddev for the learnability: µ̂l, σ̂l. The thresholding ratio γl. 4: Update fθ based onM and (x?, y?), with a network learning algorithm. 5: Compute A−1M and bM using the features and targets in the memory. 6: for = 1, ..., |Bt| do 7: if |M| < M 8: Update the buffer:M←−M∪ (xb? , yb?). 9: Update A−1M and bM based on the Sherman-Morrison formula. 10: continue 11: Get the batch index with the largest information criterion among those with large learnability:
b? = arg max b:slearn((xb,yb);M)≥µ̂l+σ̂l∗γl MICη((xb, yb);M). (13)
12: Get the memory index with the smallest information criterion:
m? = arg min m MICη((xm, ym);M∪ (xb? , yb?)\(xm, ym)).
13: if MICη((xb, yb);M) ≥ MICη((xm? , ym?);M∪ (xb? , yb?)\(xm, ym)) + (µ̂i + σ̂i ∗ γi) 14: Update the buffer:M←−M∪ (xb? , yb?)\(xm, ym). 15: Update A−1M and bM using xb? and xm? based on the Shermann-Morrison formula. 16: else 17: Update µ̂i, σ̂i, µ̂l, σ̂l using Bt. 18: return BufferM and predictor fθ, the statistics µ̂i, σ̂i, µ̂l, σ̂l. 19: Update µ̂i, σ̂i, µ̂l, σ̂l using Bt. 20: return BufferM and predictor fθ, the statistics µ̂i, σ̂i, µ̂l, σ̂l.
A.2 RESERVOIR SAMPLING
We present the pseudocodes for reservoir sampling (Vitter, 1985), the weighted reservoir sampling (Chao, 1982; Efraimidis & Spirakis, 2006), and the class-balanced reservoir sampling (Chrysakis & Moens, 2020). Worth mentioning, the weighted reservoir sampling becomes equivalent to reservoir sampling if the score function is a constant function. The class-balanced reservoir sampling becomes equivalent to reservoir sampling if only one class is observed.
Algorithm 3 Reservoir Sampling (Vitter, 1985) 1: Input: BufferM, the budget M , the count n, the new data point (x?, y?). 2: if |M| < M 3: M←−M∪ (x?, y?). 4: else 5: Generate a random integer i within 1, ..., n+ 1. 6: if i ≤M 7: M←−M∪ (x?, y?)\Mi. 8: return M, n+ 1.
Algorithm 4 Weighted Reservoir Sampling (Chao, 1982; Efraimidis & Spirakis, 2006) 1: Input: BufferM, budget M , the new data point (x?, y?). 2: Input: The score function w and the accumulative score w̄. 3: Compute the score w? = w(x?, y?). 4: Update the accumulative score w̄ = w̄ + w?. 5: if |M| < M 6: M←−M∪ (x?, y?). 7: else 8: Compute normalized score ŵ? = min(w?w̄ , 1 M ).
9: Generate a random integer i within 1, ...,M + 1, based on the probability,
[ M︷ ︸︸ ︷ ŵ?, ..., ŵ?, 1−M ∗ ŵ?].

heading: 10: if i ≤M
text: 11: M←−M∪ (x?, y?)\Mi. 12: return M, w̄.
Algorithm 5 Class-Balanced Reservoir Sampling (Chrysakis & Moens, 2020) 1: Input: BufferM, the budget M , the new data point (x?, y?). 2: Input: The counts n ∈ RK for all K classes. 3: if |M| < M 4: M←−M∪ (x?, y?). 5: else 6: Get the class index k with the largest count. 7: if nk > ny? 8: Generate a random integer i within 1, ...,nk. 9: Replace the i-th class-k point in the memory with (x?, y?). 10: Update the counter: ny? = ny? + 1. 11: else 12: LetMy? be the sub-buffer for class-y?. 13: UpdateMy? using reservoir sampling,
My? ,ny? ←− ReservoirSampling(My? , |My? |,ny? , (x?, y?)).
14: return M,n.

heading: B EXPERIMENTAL DETAILS
text: Methods. Our experiments involve Reserovir sampling (RS) (Vitter, 1985), weighted reservoir sampling 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 clustering (FSS-Clust) (Aljundi et al., 2019b), InfoGS, and InfoRS.
The toy Gaussian process regression. We present here the experimental details of the toy GP regression in Figure 1. We consider a GP with the one-dimensional RBF kernel: k(x, x′) = exp(−2(x− x′)2). We fix the variance of the observation noise as 0.04. For the memory points, we generate the inputs using np.linspace(-1, 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-CIFAR10, we make sure each of the five tasks is chosen twice within 10 random runs. We present the hyper-parameters and the configurations for the continual learning experiments in Table 1. We denote the batch size as bs, and the memory batch size as mbs. Specifically, we 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 as lr. Furthermore, α and β are the regularization coefficients in the dark experience replay objective; η is the coefficient of the learnability in the MIC; γi is the coefficient of the standard deviation for the information improvement thresholding (InfoGS) or the information thresholding (InfoRS); γl is the coefficient of the standard deviation for the learnability thresholding (InfoGS).
C INFORMATION-THEORETIC CRITERIA
In this section we present other information-theoretic criteria for online memory selection. Firstly, we have introduced the memorable information criterion composed of the learnability and the surprise,
MICη((x?, y?);M) = η log p(y′?|y?,yM;XM,x?)|y′?=y? − log p(y?|yM;XM). (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 Eq 7. Based on the rewritten form in Eq 7, we generalize the information gain as a weighted combination,
IGη((x?, y?);M) = ηEp(w|y?,yM;XM,x?) [log p(y?|w;x?)]− log p(y?|yM;XM), (15)
where we include a coefficient η to the first term similarly to MIC. We note that IG1 = IG. Comparing 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|y?,yM;XM,x?), thus it quantifies the “learnability” as well but in a different form as in MICη . Therefore, both MICη and IGη are weighted combinations of “learnability” and “surprise”.
Additionally, under the proposed Bayesian model in Subsec 2.3, the weighted IG can be computed in explicit forms as well,
IGη((x?, y?);M) =η logN (y?|h>? A−1M+bM+ , σ 2)− η 2 h>? A −1 M+h?
− logN (y?|h>? A−1MbM, σ 2h>? A −1 Mh? + σ
2), (16)
where h? is the feature of x?.
Entropy Reduction. The entropy reflects the amount of information carried in a distribution. Thus another information-theoretic 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,
ER((x?, y?);M) := H[p(w|M)]−H[p(w|M, (x, y))], (17)
where H represents the entropy of the distribution. The weight posterior is a Gaussian distribution under the Bayesian model in Subsec 2.3, thus the entropy can be computed explicitly as well,
ER((x?, y?);M) = 1
2 log|A−1M | −
1 2 log|A−1M+ | = 1 2 log|(AM + x?x>? )A−1M |
= 1
2 log|I + x?x>? A−1M | =
1 2 log(1 + x>? A −1 Mx?). (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 we propose the “learnability” 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 prediction gain (Graves et 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 “learnability”. In this paper we pick the MICη since its learnability and surprise expressions are in a 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 it can behave more like an unsuperised information criterion where output/label information is not captured. For example, if 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.
We further conduct Split CIFAR10 and Split MiniImageNet experiments to compare ER, IG1, IG3,MIC1,MIC3. The results are shown in Figure 7. We observe IGη and MICη perform similarly in this experiment. Furthermore, we observe that using η = 3 improves over η = 1 for the Split CIFAR10 experiment, while using η = 1 improves over η = 3 for the Split MiniImageNet experiment. This indicates the importance to balance the surprise and learnability in the informationtheoretic criteria. We also observe that the entropy reduction achieves competitive results as well, although it does not rely on the targets of new points.

heading: D MORE EXPERIMENTS
text: In this section we present more experimental results. Firstly, in Table 2 we present the test performances of the continual learning benchmarks, accompanying Figure 4.
More baselines. We compare the proposed approaches with the gradient sample selection (GSS) (Aljundi et al., 2019b) and class-balanced reservoir sampling (CBRS) (Chaudhry et al., 2019a) as well. We choose the GSS-Greedy algorithm in Aljundi et al. (2019b), which proposes a greedy algorithm 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. Class-balanced reservoir sampling (Chaudhry et al., 2019a) proposes to force a balanced buffer across classes by conducting reservoir sampling separately for each class. Consequently, when K classes are observed, each class will occupy M/K points in the memory. A pseudocode for CBRS is shown in Alg 5. However, CBRS is only applicable to fix the classimbalance problem for classifications. In comparison, InfoRS is generally applicable to all forms of data imbalance in the problems.
We include GSS and CBRS in Figure 8. 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 class-imbalance problem, but the classes in Permuted MNIST are always balanced. For the other three benchmarks where class-imbalance appears, CBRS demonstrates the best robustness compared to all approaches. However, as observed in Split CIFAR10 and Split MiniImageNet, CBRS underperforms RS and InfoRS when the data is balanced. We argue that the timing of the memory updates influences CBRS here. Because CBRS attempts to maintain a 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 as well, which also affects the performance of CBRS.
We also include the feature-space clustering method (FSS-Clust) (Aljundi et al., 2019b) for Permuted 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 to update the memory” is still different since InfoRS removes a 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 to 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.
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 InfoRS 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 underlying mapping. Due to the evolving features, new points might have a larger chance to be surprising and existing memories could be deleted as a result.
Forward transfer and backward transfer. We also present the forward transfer and backward transfer for the continual learning benchmarks in Table 3 and Table 4, respectively. The forward and backward transfer is introduced in Lopez-Paz & Ranzato (2017). Specifically, let Ri,j be the
performance of task j after training task i, and let bi be the performance of task i at initialization, then they are defined in the following expression,
backward transfer = 1
T − 1 T−1∑ i=1 (RT,i −Ri,i)
forward transfer = 1
T − 1 T−1∑ i=1 (Ri,i+1 − bi+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 is almost impossible. In contrast, it is possible for the network to explore the 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.
Ablation studies for η and γi. The learnability ratio η controls the weighting between surprise and learnability. We present an ablation study to investigate the impact of η in InfoRS. In addition, the information thresholding parameter γi 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 10.
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, we 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.
The TSNE plot with a smaller memory. In Figure 2, we demonstrated that incorporating learnability is important to filter out outliers, using the TSNE plot of 200 selected memories. Here we present another comparison to investigate the scenario with a small memory. Specifically, we set the memory buffer as 25. The results are shown in Figure 12.
Impact of α and β. 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 13.

heading: E PROOFS
text: In this section we provide necessary proofs.
Information Gain. We rewrite the information gain as the following,
IG((x?, y?);M) = KL (p(w|y?,yM;XM,x?)||p(w|yM;XM)) = Ep(w|y?,yM;XM,x?) [ log
p(w|y?,yM;XM,x?) p(w|yM;XM) ] = Ep(w|y?,yM;XM,x?) [ log p(w, y?,yM;XM,x?)
p(w,yM;XM)p(y?|yM;XM,x?) ] = Ep(w|y?,yM;XM,x?)[log p(y?|w,yM)− log p(y?|yM;XM)] = Ep(w|y?,yM;XM,x?)[log p(y?|w;x?)]− log p(y?|yM;XM). (19)
Proof. By applying Jensen’s inequality we have
log p(y′?|y?,yM;XM,x?)|y′?=y? = logEp(w|y?,yM;XM,x?)[p(y?|w;x?)] ≥ Ep(w|y?,yM;XM,x?)[log p(y?|w;x?)] (20)
Information Criterion for Bayesian Linear Regression. Given a new point (x?, y?), let h? be the corresponding feature, then the criterion is represented as,
s((h?, y?);M) = η log p(y′?|y?,yM;XM,x?)|y′?=y? − log p(y?|yM;XM). (21)
Given the memoryM, the posterior distribution of weights can be computed as, p(w|yM;HM) = N (A−1MbM, σ 2A−1M ). (22)
where the matrix A−1M = ( H>MHM + cId )−1 for c = σ 2 σ2w and bM = H>MyM. Similarly let M+ =M∪ (x?, y?), AM+ = AM+h?h>? and bM+ = bM+h?y?, then weight posterior given the memoryM+ can be computed as,
p(w|yM+ ;HM+) = N (A−1M+bM+ , σ 2A−1M+). (23)
Thus the predictive distributions can be represented as,
y′?|yM+ ∼ N (h>? A−1M+bM+ , σ 2h>? A −1 M+h? + σ 2), (24)
y?|yM ∼ N (y?|h>? A−1MbM, σ 2h>? A −1 Mh? + σ 2). (25)
which directly leads to the expression of the information criterion
MICη((x?, y?);M) =η logN (y?|h>? A−1M+bM+ , σ 2h>? A −1 M+h? + σ 2)
− logN (y?|h>? A−1MbM, σ 2h>? A −1 Mh? + σ 2).
We can now combine this with the definition of the log density logN (y|a, b) = log ( 1
b √ 2π e− 1 2 ( y−a b )
2 )
= −1 2 (( y − a b )2 + log(2πb2) ) of a Gaussian N (a, b). Let us denote with µ+ and σ+ the updated mean and variance, and with µ− and σ− the old mean and variance (not to be confused with the noise variance σ. Then
MICη((x?, y?);M) =− η
2 (( y? − µ+ σ+ )2 + log(2πσ2+) ) + 1 2 (( y? − µ− σ− )2 + log(2πσ2−) )

Review summaries:
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.  

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.  The 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.  

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.