arXiv CSopen access

Leveraging Complementary Embeddings for Replay Selection in Continual Learning with Small Buffers

Leveraging Complementary Embeddings for Replay Selection in Continual Learning with Small Buffers

Danit Yanowsky1 1

Daphna Weinshall1

School of Computer Science and Engineering The Hebrew University of Jerusalem

arXiv:2604.08336v1 [cs.LG] 9 Apr 2026

{danit.yanowsky,daphna.weinshall}@mail.huji.ac.il

Abstract

learning (CIL) scenario, where each episode introduces new classes, and at test time the model must jointly classify all classes seen so far. Among the many approaches proposed to mitigate forgetting, replay-based methods have emerged as a simple and effective family of techniques. Experience replay (ER) (Rolnick et al., 2019), and its variants such as ER-ACE (Caccia et al., 2021) and MIR (Aljundi et al., 2019a), maintain a small memory buffer of past examples and interleave them with current data during training. Under tight memory constraints, however, performance hinges on which examples are stored for replay. A large body of work has therefore focused on exemplar selection strategies that aim to maximize diversity or representativeness of the buffer, for example through herding (Rebuffi et al., 2017), clustering-based selection (Bang et al., 2021b; Chaudhry et al., 2021), or coverage-based methods (Shaul-Ariel & Weinshall, 2024).

Catastrophic forgetting remains a key challenge in Continual Learning (CL). In replay-based CL with severe memory constraints, performance critically depends on the sample selection strategy for the replay buffer. Most existing approaches construct memory buffers using embeddings learned under supervised objectives. However, class-agnostic, self-supervised representations often encode rich, class-relevant semantics that are overlooked. We propose a new method, Multiple Embedding Replay Selection (MERS), which replaces the buffer selection module with a graph-based approach that integrates both supervised and self-supervised embeddings. Empirical results show consistent improvements over SOTA selection strategies across a range of continual learning algorithms, with particularly strong gains in low-memory regimes. On CIFAR-100 and TinyImageNet, MERS outperforms single-embedding baselines without adding model parameters or increasing replay volume, making it a practical, drop-in enhancement for replay-based continual learning.

Most existing selection strategies operate in a single representation space: they rely on embeddings produced by the current supervised model, typically the penultimate layer of the classifier. However, a supervised embedding tends to specialize to the current episode: it concentrates geometry along class-discriminative directions and compresses directions that are presently irrelevant. In class-incremental learning, this can make rehearsal and buffer construction

1. Introduction Continual Learning (CL) deals with the challenge of training models while acquiring knowledge from a stream of data whose distribution changes over time. Unlike conventional training on a fixed dataset, many real-world settings, such as autonomous driving, personalized assistants, or robotic agents, must cope with non-stationary environments, where new concepts appear and old ones may become rare or disappear. A central obstacle in this setting is catastrophic forgetting (McCloskey & Cohen, 1989; Ratcliff, 1990): when trained naively on new data, neural networks tend to overwrite previously acquired knowledge, leading to severe performance degradation on past tasks. Figure 1. Illustration of our MERS in the class-incremental learning (CIL) setup, after training episode T.

This challenge is particularly acute in the class-incremental 1

Leveraging Complementary Embeddings for Replay Selection in Continual Learning with Small Buffers

fragile - exemplars that look “representative” under the old supervised geometry (e.g., via uniform sampling or mean/coverage criteria) are not necessarily the ones that preserve separability as new classes arrive. This is closely related to distribution shift in domain transfer, which we leverage in the theoretical analysis in Section 4.

Split CIFAR-100 and Split TinyImageNet, using three replay-based continual learning algorithms and both supervised and self-supervised embeddings. Across all methods and datasets, MERS consistently outperforms singleembedding baselines under the same memory budget, with particularly pronounced gains in low-buffer regimes. We further analyze the role of each embedding and the effect of our data-driven alignment and weighting scheme, showing that the Multiple Embedding formulation is key to the observed improvements.

To mitigate this risk, we pair the supervised embedding with a self-supervised embedding. The latter typically induces a broader, more nearly uniform feature distribution, and is therefore less likely to neglect directions that are uninformative for current classes but crucial for future ones. Related ideas appear in continual representation learning that incorporates self-supervised objectives (e.g., CaSSLe (Fini et al., 2022), SSCIL (Ni et al., 2021)). In contrast, we do not seek to replace the supervised representation; instead, we integrate supervised and self-supervised geometries through the lens of point coverage. The goal is to reach a sweet spot, retaining strong discrimination on current classes while maintaining a more uniform geometry that better anticipates unseen classes.

Summary of main contributions: • We propose MERS, a coverage-based replay selection framework that jointly leverages supervised and self-supervised embeddings to capture complementary data geometry under tight memory constraints. • We introduce a non-parametric alignment strategy based on k-NN density estimation that adapts selection scales and weights across embeddings without adding persistent model parameters. • We show that MERS achieves state-of-the-art performance on Split CIFAR-100 and Split TinyImageNet, with especially strong gains in low-memory regimes.

Building on these insights, we propose MultipleEmbedding Replay Selection (MERS), a simple, modular enhancement to replay-based continual learning (see illustration in Fig. 1). Conceptually, MERS replaces the usual single-embedding selection step by a coverage objective defined jointly over several embedding spaces, e.g., a supervised classifier embedding and a self-supervised SimCLR embedding. We show that this objective can be cast as a weighted maximum k-coverage problem over groups, in which each candidate example covers a neighborhood of points in each embedding space. MERS automatically adapts the scale of each embedding using non-parametric density estimation, and assigns a weight to each embedding that reflects its effective contribution. Intuitively, this encourages the buffer to cover dense and diverse regions across all embeddings, rather than overfitting to the geometry of a single view.

2. Related Work Continual learning paradigms. CL approaches are often grouped into: (i) regularization-based methods that constrain parameter updates to preserve prior knowledge (e.g., EWC (Kirkpatrick et al., 2017), LwF (Li & Hoiem, 2017)); (ii) architecture-based methods that expand capacity across tasks (e.g. HAT (Serrà et al., 2018), DAN (Yoon et al., 2018)); and (iii) Replay-based methods that maintain a small memory of exemplars for replay (e.g., ER (Rolnick et al., 2019), ER-ACE (Caccia et al., 2021)). In CIL, rehearsal is particularly competitive under tight memory budgets because it is able to preserve decision boundaries as the label set grows (Hou et al., 2019). STAR (Eskandar et al., 2025) introduces a method-agnostic replay mechanism with adaptive sample reweighting, achieving state-ofthe-art results under tight memory constraints.

From a methodological standpoint, MERS can be understood as a principled extension of coverage-based selection from active learning to the replay setting, preserving the underlying replay backbone while generalizing it to operate jointly over multiple embedding spaces. For a fixed memory budget, our greedy selection algorithm retains the classical (1 − 1/e) approximation guarantee for submodular coverage, while remaining practical to implement and efficient in both time and space. Crucially, MERS is a dropin module: it requires no architectural modifications to the continual learner, introduces no additional trainable parameters, and can be seamlessly combined with existing replaybased methods, such as ER, ER-ACE, or MIR, by simply replacing the buffer update rule.

Selection strategies. A central challenge in replay-based continual learning is exemplar selection. Early methods such as iCaRL employed herding to approximate class centroids in a fixed feature space (Hou et al., 2019). More recent approaches fall into two families: (i) gradientbased methods (e.g., GSS Aljundi et al., 2019b) that prioritize samples likely to induce interference, and (ii) representativeness-oriented methods (e.g., TEAL ShaulAriel & Weinshall, 2024) that retain typical samples based on neighborhood structure. Coverage-based selection and its guarantees. Coverage-

We evaluate MERS in the class-incremental setting on 2

Leveraging Complementary Embeddings for Replay Selection in Continual Learning with Small Buffers

based methods cast exemplar selection as a geometric covering problem. Most prior CL heuristics compute coverage in a single embedding at a fixed scale (e.g. Isele & Cosgun, 2018). Solving a related problem for active learning, ProbCover casts buffer selection as graph coverage (Yehuda et al., 2022), while MaxHerding introduces kernel smoothing (Bae et al., 2024). In contrast, our method generalizes coverage to multiple embeddings and adapts locality per embedding using nonparametric statistics, which is critical in tiny-buffer regimes.

using a fixed per-class budget. All definitions below apply to the samples of a single class unless stated otherwise. 3.1. Notations and definitions n

Let X = {xi }i=1 represent a set of n data points, where xi ∈ X . For this dataset define the graph G = (V, E), with n vertices V = {vi }i=1 where vi ↔ xi , and edges ei,j = D(xi , xj ) for some distance metric D : X × X → R≥0 . With multiple embeddings, each dataset can now be repre sented by a collection of graphs V, E (m) , where m ∈ (m) [M ] indexes the embeddings, vi ↔ xi and ei,j =

Self-supervised representations for CL. Self-supervised learning (SSL) captures class-agnostic invariances that naturally complement supervised features (Uelwer et al., 2025). Methods such as SimCLR (Chen et al., 2020), VICReg (Bardes et al., 2021), and DINO (Caron et al., 2021b) learn rich embeddings without label supervision.

(m)

(m)

D(zi , zj ) for an embedding f (m) : X → Z (m) . Definition 1 (δ-ball). Fix δ > 0, and consider an embed(m) ding f (m) : X → Z (m) where zx = f (m) (x). Define 
(m) (m) Bδ (x) = x′ ∈ X D zx′ , zx(m) ≤ δ

These SSL representations have already demonstrated effective transfer to object detection, semantic segmentation, depth estimation, robotics manipulation, and few-shot recognition, often rivaling or surpassing supervised pretraining (Uelwer et al., 2025). Yet most rehearsal-based CIL methods still choose exemplars solely in the supervised feature space of the current classifier, with only a handful operating purely in an SSL space (e.g. Ni et al., 2021), with known selection strategies such as herding applied unchanged (Lee et al., 2024).

(m)

Bδ (x) denotes the set of points whose embedding lies inside the ball of radius δ centered at x in embedding m. Maximum k-Coverage with multiple groups. The optimization problem, which lies at the heart of our method, can be shown to be a known variant of the k-coverage problem, whose 2-groups version is defined as follows: Definition 2 (Maximum k-Coverage with two groups). Let U be a universe of elements, partitioned into two disjoint subsets U 1 and U 2 such that U = U 1 ∪ U 2 and U 1 ∩ U 2 = ∅. Each element e ∈ U i is associated with a nonnegative weight αi (e) ∈ R≥0 , where the weight functions α1 , α2 may differ between the two groups.

In this work we exploit supervised and SSL embeddings in a complementary manner, preserving both classdiscriminative and class-agnostic structure and yielding consistent gains in tiny-buffer continual-learning regimes. Multi-view learning. This is an ML paradigm where data is represented through multiple distinct feature sets or ”views” (e.g., text and image) (Yu et al., 2025). Common approaches include co-training and multi-view representation learning (Zheng et al., 2023). The central idea is to leverage the complementary information in these views to improve performance, often by enforcing consistency or agreement across them. In contrast, our approach aims to exploit variability among representation in order to achieve a more representative set of examples, rather than achieving a single coherent view of the data.

Let S = {S1 , S2 , . . . , Sl } be a family of subsets of U , and let k ∈ N be a budget parameter. For a subcollection A ⊆ S, define the coverage weight as X X α2 (e). α1 (e) + Coverage(A) = S e∈ S∈A S∩U 1

e∈

S

S∈A S∩U

2

The goal is to select a sub-collection A ⊆ S of size at most k that maximizes Coverage(A). This formulation can be extended to multiple embeddings. 3.2. Coverage-based selection, a single embedding

3. Our method: MERS

A coverage-based selection strategy seeks a small representative subset of X by maximizing a suitable notion of coverage on a graph built from the data. More specifically, ProbCover (Yehuda et al., 2022) selects a subset L∗ ⊂ X of size at most b that maximizes the number of points covered by the union of corresponding δ-balls:

The proposed method, termed Multiple Embedding Replay Selection (MERS), is designed to enhance replay-based approaches within the CIL framework. The method, illustrated in Fig. 1, replaces the buffer selection rule with a coverage-based method, which integrates in turn supervised and self-supervised embeddings. Its primary benefits are expected to manifest in low-memory buffer regimes. Buffer selection is performed independently for each class,

L∗ = arg 3

max

L⊆X, |L|=b

[ x∈L

Bδ (x) .

Leveraging Complementary Embeddings for Replay Selection in Continual Learning with Small Buffers

(Superscript (m) is omitted given a single embedding).

3.4. Embedding alignment

∗

Equivalently, ProbCover seeks a subset L such that the number of points that lie within distance δ of at least one point in L∗ is maximized. This is equivalent to the b−set max coverage problem. MaxHerding (Bae et al., 2024) generalizes this idea by replacing hard δ-ball coverage with a continuous kernel-based similarity measure (e.g., an RBF kernel centered at each selected point), where the underlying objective remains a (soft) notion of coverage.

Bandwidth selection for the RBF kernel in MaxHerding. Coverage-based selection methods rely on hyperparameters that control similarity range and partition granularity, which become especially problematic in Multiple Embedding settings where embeddings {E (m) }M m=1 originate from heterogeneous backbones with incompatible geometric scales. When integrating MaxHerding into MERS, the relevant parameter is the RBF bandwidth σ where
κRBF (x, x′ ) = exp −∥x − x′ ∥2 /(2σ 2 ) .

3.3. Coverage-based selection, multiple embeddings We now generalize the coverage objective to the multiple embedding setting considered in this work. Intuitively, each embedding captures different aspects of the data geometry; we therefore aim to select a buffer that covers dense regions across all embeddings. To this end, we define a weighted multiple embedding coverage objective. Definition 3 (Buffer selection with weighted Multiple Embedding coverage). Let α1 , . . . , αM ≥ 0 denote nonnegative weights that reflect the relative importance of each embedding. For a candidate subset L ⊆ X, define M X [ (m) αm Bδm (xi ) . (1) F (L) =

Following the widely adopted median heuristic (Garreau et al., 2018), we set σ to the median cosine distance among all exemplars in the current episode. This choice aligns kernel similarities with the intrinsic geometry and sparsity of each embedding E (m) , ensuring consistent behavior across embeddings, as validated in Section 7. Weighting each embedding. We now discuss the estimation of the vector of weights {αm } defined in (3). First, we recall the definition of the k-NN density estimation. Once again, let Mc = {x ∈ X | y(x) = c}. For any (m) x ∈ Mc , let NK (x) denote the set of its k nearest neigh(m) bors in Mc \ x in embedding E (m) . Let ρk (x) denote the mean distance from x to set NK (x). In embedding m, the kNN density estimate at x is defined as follows:

xi ∈L

m=1

Given a budget b, the buffer-selection problem becomes L∗ = arg max F (L). L⊆X, |L|=b

(m) fbk (x) =

The optimization problem in (1) is equivalent to a special case of the weighted maximum k-coverage problem with M groups. To make this connection explicit, define, for each embedding m, a ground set Um that contains one el(m) ement ui for every datapoint xi ∈ X, and define the UM global ground set U = m=1 Um (disjoint union). For each datapoint xi , associate the subset M [  (m) (m) Si = uj ∈ Um xj ∈ Bδm (xi ) . (2)

(m)

αm =

m=1

αm

[

Si ∩ Um .

median(fbk (x)) (m) median(fb (x))

(5)

1

The reasoning behind this definition is as follows: if two point clouds differ only by a scale factor, the distribution of α remains unchanged, resulting in α1 = α2 . In practice, however, the supervised embedding ESupervised tends to exhibit micro-clusters - tightly grouped, nearly identical samples within a class - more so than the self-supervised embedding Eself-supervised . These local geometric effects reduce the nearest-neighbor distance ρ1 without a proportional reduction in ρk , thereby increasing the ratio ρk /ρ1 . This effect is significantly weaker in the self-supervised embedding Eself-supervised , whose geometry is more uniform. As a result, we typically observe:

For any L ⊆ X we can rewrite (1) as follows: M X

(4)

For embedding m, we now define its weight as follows:

m=1

F (L) =

k (m) ρk (x)

(3)

i:xi ∈L

From (3) and Def. 2, maximizing F (L) subject to |L| = b is equivalent to a weighted maximum k-coverage problem with M groups over the family {Si }N i=1 , where all elements e ∈ E (m) share a common weight αm . The resulting objective is a non-negative, normalized, monotone, submodular set function (see Appendix B).Therefore, the greedy algorithm that iteratively selects the element with the largest marginal gain achieves a (1 − 1/e)-approximation to the optimal solution (Vazirani, 2001). A full proof is provided in Appendix D.

β =

αSupervised > 1. αself-supervised

(6)

Our greedy algorithm maximizes the weighted coverage score defined in (3). Because the algorithm also enforces diversity through disjoint k-NN balls, dense supervised 4

Leveraging Complementary Embeddings for Replay Selection in Continual Learning with Small Buffers (1)

(2)

proxies: GSSL = N (0, σΣ) or GSSL = N (0, σIn ), which are justified by the presumed uniformity of SSL embeddings. The distribution over the SL embedding is modeled by an anisotropic proxy GSL = N (0, Σ1/2 DΣ1/2 ) with D = diag(α, . . . , α, β, . . . , β), α > β > 0, where α acts on m discriminative directions and β compresses the remaining n − m directions. To factor out irrelevant globalscale effects, we enforce equal global compression between the SL and SSL embeddings by matching the volumes of their covariance ellipsoids, i.e., their determinants.

balls contain far fewer candidate edges than large selfsupervised balls. Multiplying the supervised edge count by β thus equalizes the edge mass that each selected point can cover, ensuring that the sampler does not over-represent the sparse self-supervised space and achieves a balanced, diverse subset across both embeddings. 3.5. The MERS algorithm Pseudo-code for the MaxHerding-variant of MERS is provided in Alg. 1 (see Appendix for the ProbCover-variant).

Anisotropy increases KL under equal volume. Under equal-volume normalization, the anisotropic SL perturbation yields a larger class-conditional distortion than the SSL proxies as measured by DKL (G0 ∥·). In particular,   (1) DKL (G0 ∥ GSL ) ≥ DKL G0 GSSL ,   (2) DKL (G0 ∥ GSL ) ≥ DKL G0 GSSL , β < β0 .

Algorithm 1 MERS MaxHerding Input: Dataset C = {x1 , . . . , xn }, kernels km , weights αm , buffer ⇕, budget b. Output: Updated memory buffer M. PM (m) (m) 1: k(x, x′ ) ← m=1 αm km (zx , zx′ ) 2: for t = 1 to b do ▷ Greedy MaxHerding selection 3: for each xj ∈ C \ S do n 1X max(k(xi , xj ) − ci , 0) G(xj ) ← 4: n i=1 5: end for 6: xt ← arg maxxj ∈C\S G(xj ); S ← S ∪ {xt } 7: for i = 1 to n do 8: ci ← max(ci , k(xi , xt )) 9: end for 10: end for 11: M ← M ∪ S return M

for some β0 . Moreover, in the highly anisotropic regime β → 0, the resulting KL gap can grow arbitrarily large. A domain-adaptation view of class-incremental training. We now formulate the episode-to-episode shift as a domain adaptation problem. A central quantity in this framework is the train–test risk gap, defined as the difference between the empirical risk on the training set and the risk on a test set; a larger gap indicates poorer generalization. Accordingly, our objective is to minimize this gap. In our setting, only class Y = 1 is carried over from the previous episode and is therefore represented by a limited buffer of stored examples, while all remaining classes are represented by freshly sampled data. As a result, the training and test distributions coincide for all but the buffered class: Ptr (X | Y = y) = Pte (X | Y = y) ∀y ̸= 1, whereas Ptr (X | Y = 1) ̸= Pte (X | Y = 1). The following result characterizes the effect of this class-conditional shift on the risk gap for any classifier h:
RiskGap ≤ DKL Pte (X | Y = 1)∥Ptr (X | Y = 1) .

4. Theoretical analysis Appendix D provides a theoretical justification for sampling from a mixture of Supervised (SL) and SelfSupervised (SSL) embeddings. The key premise is that SL representations can become episode-specialized, concentrating variation in class-discriminative directions and compressing directions that are currently irrelevant, whereas SSL representations tend to preserve a broader set of non-label factors and induce a more isotropic geometry. While SL specialization is clearly beneficial, encoding task-relevant structure and domain knowledge, we show that the broader, less discrimination-oriented geometry of SSL representations can improve robustness to domain shift and to the emergence of new classes.

In other words, the train-test risk gap is bounded by the KL-divergence between the class conditional distribution of the buffered class in the train and test distributions. Implication for SSL vs. SL sampling. Together, (4) and (4) give us our final result: under equal-volume normalization, sampling in an SSL geometry leads to a tighter bound on the train-test risk gap than sampling in the anisotropic SL geometry, especially in the small-β regime, and therefore implies better generalization.

Modeling SL/SSL as class-conditional perturbations. We model each class-conditional distribution in a reference feature space Rn by a Gaussian N (µ, Σ). We investigate a reference class whose conditional distribution is G0 = N (µ0 , Σ), fixing µ0 = 0 w.l.o.g. Each embedding used for buffer sampling induces a modified class-conditional distribution for the reference class. With SSL embedding, we model the modified distribution by one of two isotropic

5. Methodology In our empirical evaluation, MERS is evaluated while enhancing 3 distinct experience replay continual learning al5

Leveraging Complementary Embeddings for Replay Selection in Continual Learning with Small Buffers

gorithms, detailed in Section 5.1. We report results in comparison with several common exemplar selection strategies, which are described in Section 5.2. Section 5.3 describes the 3 alternative SSL methods used for evaluation. Section 5.4 describes the two datasets used in our evaluation, following customary practice in the evaluation of CIL methods. Evaluation metrics are described in Section 5.5. All experiments use a class-balanced replay buffer.

tions via self-distillation from an EMA teacher. VICReg and SimCLR are trained from scratch at each episode using only the current episode’s data. DINOv2 embeddings are extracted from a frozen model (see Appendix E.3). 5.4. Datasets We evaluate on two standard CIL benchmarks: Split CIFAR-100 (Chaudhry et al., 2019; Rebuffi et al., 2017), which divides CIFAR-100 into 10 episodes of 10 classes each (500 training and 100 test images per class), and Split TinyImageNet (Le & Yang, 2015), which splits TinyImageNet into 10 episodes of 20 classes each (500 training and 50 test images per class).

5.1. Continual Learning Algorithms We evaluate MERS with three rehearsal-based continual learning baselines: ER (Rolnick et al., 2019), which replays buffered past examples; ER-ACE (Caccia et al., 2021), which decouples losses for new and replayed data; and ER-ACE-STAR (Eskandar et al., 2025), which augments ER-ACE with an adaptive, method-agnostic replay reweighting strategy.

5.5. Evaluation Metrics in CIL We report five standard CIL metrics: • Average Accuracy: AAt is the mean accuracy over all tasks learned up to task t. • Final Average Accuracy: F AA = AAT P . T • Anytime Average Accuracy: AAA = T1 t=1 AAt . P T −1 1 • Forgetting: F = T −1 i=1 (maxj≤T Ai,j − Ai,T ), where Ai,j - accuracy on task i after learning task j. • Stability: on previously learned tasks. S = PT accuracy Pt−1 1 1 t=2 t−1 i=1 Ai,t , where Ai,t denotes the accuT −1 racy on task i after learning task t.

5.2. Baseline selection strategies We compare against representative exemplar selection strategies: (i) Random selects exemplars uniformly at random from each class; (ii) Herding (Welling, 2009; Rebuffi et al., 2017) selects samples to approximate the class mean in feature space; (iii) Rainbow Memory (Bang et al., 2021a) balances multiple criteria such as diversity and uncertainty; (iv) TEAL (Shaul-Ariel & Weinshall, 2024) clusters samples and selects representative exemplars; (v) ProbCover (Bae et al., 2024) selects points based on classcoverage using the ProbCover approach; (vi) MaxHerding (Bae et al., 2024) selects points based on class-coverage using the MaxHerding approach.

6. Empirical Results 6.1. Main results In our empirical evaluation, we assess two variants of MERS that rely on two related coverage-based methods, denoted MERS ProbCover and MERS MaxHerding, as described above. To assess robustness to memory constraints, we varied the capacity of the replay-buffer, from 100 to 1000 on the Split CIFAR-100 benchmark; the resulting FAA is reported in Fig. 2, while AAA is reported in Tables 1- 2. On Split TinyImageNet benchmark, we consider buffer sizes ranging from 200 to 6000, with FAA results shown in Fig 3. The complete results, including AAA, are provided in Appendix A (see Fig. 12).

5.3. Self-supervised learning baselines We evaluate three SOTA self-supervised representation learning methods: SimCLR (Chen et al., 2020), a contrastive approach maximizing agreement between augmented views; VICReg (Bardes et al., 2021), which enforces invariance with variance and covariance regularization without negatives; and DINOv2 (Caron et al., 2021a; Oquab et al., 2023), which learn transferable representa-

Table 1. Average Accuracy Across All Tasks (AAA) on CIFAR-100 ER ACE STAR. For each |M|, the best AAA is highlighted in bold. Random

ProbCover

MaxHerding

|M| Supervised Supervised Supervised

MERS

Herding

TEAL

Supervised Supervised

100 41.71 ±0.18 47.98 ±0.13 49.32 ±0.13 50.96 ±0.19 41.98 ±0.20 48.41 ±0.33 300 50.25 ±0.35 57.10 ±0.25 57.11 ±0.14 58.96 ±0.21 51.79 ±0.27 56.56 ±0.23 500 54.14 ±0.32 59.88 ±0.17 60.32 ±0.27 61.64 ±0.16 55.22 ±0.30 60.06 ±0.15 1000 60.03 ±0.27 64.17 ±0.30 63.92 ±0.12 65.54 ±0.29 61.50 ±0.08 64.05 ±0.28 2000 65.12 ±0.22 67.82 ±0.20 68.08 ±0.34 69.23 ±0.27 65.38 ±0.19 67.57 ±0.07

6

Leveraging Complementary Embeddings for Replay Selection in Continual Learning with Small Buffers Table 2. Average Accuracy Across All Tasks (AAA) on CIFAR-100 ER ACE. For each |M|, the best AAA is highlighted in bold. Random

ProbCover

MaxHerding

|M| Supervised Supervised Supervised

MERS

Herding

TEAL

Supervised Supervised

100 41.31 ±0.30 45.98 ±0.35 47.04 ±0.21 48.32 ±0.15 40.77 ±0.19 42.91±0.13 300 49.90 ±0.28 54.03 ±0.21 54.19 ±0.29 55.68 ±0.39 48.70 ±0.29 53.13 ±0.19 500 53.72 ±0.20 57.17 ±0.07 58.01 ±0.11 58.99 ±0.19 52.94 ±0.10 56.80 ±0.14 1000 58.88 ±0.09 61.72 ±0.24 62.35 ±0.30 63.52 ±0.23 58.80 ±0.22 61.10 ±0.28 2000 64.21 ±0.35 66.47 ±0.25 66.35 ±0.25 66.96 ±0.10 64.53 ±0.14 65.66 ±0.24

(a) FAA

(b) AAA

Figure 3. FAA (left) and AAA (right) on Split TinyImageNet for ER-ACE with buffer size |M| = 1000, using MERS, compared against alternative selection strategies.

6.2. Pretrained vs. Episodic Embeddings

(a) ER-ACE-STAR

Following the same protocol as outlined above, results when using different SSL embeddings (see Section 5.3) are presented in Fig. 4, with complete FAA and AAA tables reported in Appendix A.

(b) ER-ACE

Figure 4. FAA of MERS with ER-ACE-STAR on Split CIFAR100 using different embeddings: SimCLR, VICReg and DINOv2

6.3. Selection stability and forgetting We analyze selection stability and forgetting for MaxHerding with a supervised embedding, Max-Herding with SimCLR embedding, and the integrated MERS approach. Results are reported in Fig. 5, with complete stability and forgetting statistics provided in Appendix H.2.

(c) ER Figure 2. FAA as a function of memory size |M | on Split CIFAR100 for three continual learning algorithms, described in Section 5.1. Results with MERS are compared against alternative selection strategies, described in Section 5.2. The selection-strategy legend is shown in panel (c).

We observe that Max-Herding based on SimCLR embeddings consistently yields higher stability and lower forget7

Leveraging Complementary Embeddings for Replay Selection in Continual Learning with Small Buffers

distributional drift between stored exemplars and data encountered in later episodes.

7. Ablation study We conducted targeted ablations to identify which design choices of our MERS are most critical: RBF bandwidth σ in MaxHerding We tested three settings for σ: (i) median cosine distances, (ii) σ = 1, and (iii) median k-NN distances. On CIFAR-100, (i) and (iii) coincide, while the constant value reduces FAA by ≈ 1% in the small-buffer regime (see Fig. 6). As (i) is dataset-agnostic and robust across budgets, we adopt it as the default.

(a) Stability

Figure 6. Improvements in FAA on CIFAR-100 as a function of |M| while varying the RBF bandwidth σ in MaxHerding. (b) Forgetting Figure 5. Stability and forgetting of ER-ACE-STAR with MERS as a function of |M | on Split CIFAR-100.

We conducted an ablation study on the embedding weight α using different density estimators. The results show a slight improvement when using the α defined in (5), as reported in Appendix I.

ting compared to its supervised counterpart. Furthermore, MERS, which integrates supervised and self-supervised embedding spaces, achieves the most stable selection behavior overall, outperforming both Max-Herding variants across all evaluated settings.

We also conducted an ablation study using MaxHerding with only SimCLR embeddings, and showed that MERS achieves higher FAA and AAA accuracy, as reported in Fig. 4

6.4. Discussion

8. Summary

Across all buffer sizes, replay methods, and datasets, MERS achieves the strongest performance. The integrated variant consistently matches or outperforms its constrained counterparts, with the largest gains in the low-budget regime (up to 1000 exemplars). While the gap narrows as the buffer grows, the integrated MERS remains top-ranked, often tying for best. Overall, MERS outperforms either embedding alone, with integration yielding the greatest benefit under tight memory constraints. Notably, these gains coincide with increased selection stability and reduced forgetting, suggesting that embedding integration plays a key role in the observed performance improvements.

We present Multiple Embedding Replay Selection (MERS), a plug-and-play sampler for replay-based continual learning that merges supervised and self-supervised feature spaces in a complementary manner. By building k-NN coverage graphs in each space, re-scaling them with densityaware weights, and greedily selecting exemplars that maximize a combined coverage score, MERS fills both classdiscriminative and invariant regions of the data manifold. Across Split CIFAR-100 and Split TinyImageNet, it boosts final-average accuracy over single-embedding baselines when memory is tight, all without increasing the buffer size or changing model parameters. The method is plugand-play, incurs only double selection-time overhead and self-supervised training. The approach opens avenues for dynamic, task-aware embedding integration in future work.

The empirical findings reported in Section 6.3 are consistent with our theoretical analysis in Section 4. The improved stability and reduced forgetting observed with SimCLR and the integrated MERS approach reflect a reduced 8

Leveraging Complementary Embeddings for Replay Selection in Continual Learning with Small Buffers

Impact Statement

Chen, T., Kornblith, S., Norouzi, M., and Hinton, G. A simple framework for contrastive learning of visual representations. In International conference on machine learning, pp. 1597–1607. PmLR, 2020. 3, 6

This paper presents work whose goal is to advance the field of machine learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.

Cover, T. M. and Thomas, J. A. Elements of Information Theory. Wiley, 2 edition, 2006. 17

Alemi, A. A., Fischer, I., Dillon, J. V., and Murphy, K. Deep variational information bottleneck. In International Conference on Learning Representations, 2017. 14

da Costa, V. G. T., Fini, E., Nabi, M., Sebe, N., and Ricci, E. sololearn: A library of self-supervised methods for visual representation learning. Journal of Machine Learning Research, 23 (56):1–6, 2022. URL http://jmlr.org/papers/v23/ 21-1155.html. 17

Aljundi, R., Belilovsky, E., Tuytelaars, T., Charlin, L., Caccia, M., Lin, M., and Page-Caccia, L. Online continual learning with maximal interfered retrieval. Advances in neural information processing systems, 32, 2019a. 1

Eskandar, M., Imtiaz, T., Hill, D., Wang, Z., and Dy, J. Star: Stability-inducing weight perturbation for continual learning, 2025. URL https://arxiv.org/abs/2503.01595. 2, 6

Aljundi, R., Lin, M., Goujaud, B., and Bengio, Y. Gradient based sample selection for online continual learning. Advances in neural information processing systems, 32, 2019b. 2

Fini, E., Turrisi da Costa, V. G., Alameda-Pineda, X., Ricci, E., Alahari, K., and Mairal, J. Self-supervised models are continual learners. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2022. 2

References

Bae, W., Noh, J., and Sutherland, D. J. Generalized coverage for more robust low-budget active learning. In European Conference on Computer Vision, pp. 318–334. Springer, 2024. 3, 4, 6

Garreau, D., Jitkrittum, W., and Kanagawa, M. Large sample analysis of the median heuristic, 2018. URL https: //arxiv.org/abs/1707.07269. 4

Bang, J., Kim, H., Yoo, Y., Ha, J.-W., and Choi, J. Rainbow memory: Continual learning with a memory of diverse samples. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 8218–8227, 2021a. 6

Hou, S., Pan, X., Loy, C. C., Wang, Z., and Lin, D. Learning a unified classifier incrementally via rebalancing. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 831–839, 2019. 2

Bang, J., Kim, H., Yoo, Y., Ha, J.-W., and Choi, J. Rainbow memory: Continual learning with a memory of diverse samples, 2021b. URL https://arxiv.org/abs/2103.17230. 1

Isele, D. and Cosgun, A. Selective experience replay for lifelong learning, 2018. URL https://arxiv.org/abs/1802. 10269. 3 Kirkpatrick, J., Pascanu, R., Rabinowitz, N., Veness, J., Desjardins, G., Rusu, A. A., Milan, K., Quan, J., Ramalho, T., Grabska-Barwinska, A., et al. Overcoming catastrophic forgetting in neural networks. Proceedings of the national academy of sciences, 114(13):3521–3526, 2017. 2

Bardes, A., Ponce, J., and LeCun, Y. Vicreg: Variance-invariancecovariance regularization for self-supervised learning. arXiv preprint arXiv:2105.04906, 2021. 3, 6 Caccia, L., Aljundi, R., Asadi, N., Tuytelaars, T., Pineau, J., and Belilovsky, E. New insights on reducing abrupt representation change in online continual learning. arXiv preprint arXiv:2104.05025, 2021. 1, 2, 6

Le, Y. and Yang, X. Tiny imagenet visual recognition challenge. CS 231N, 7(7):3, 2015. 6 Lee, K.-Y., Zhong, Y., and Wang, Y.-X. Do pre-trained models benefit equally in continual learning?, 2024. URL https: //arxiv.org/abs/2210.15701. 3

Caron, M., Touvron, H., Misra, I., Jegou, H., Mairal, J., Bojanowski, P., and Joulin, A. Emerging properties in selfsupervised vision transformers. In 2021 IEEE/CVF International Conference on Computer Vision (ICCV), pp. 9630–9640, 2021a. doi: 10.1109/ICCV48922.2021.00951. 6

Levin, D. A., Peres, Y., and Wilmer, E. L. Markov Chains and Mixing Times. American Mathematical Society, 2 edition, 2017. See Proposition 4.5 for a supremum characterization of total variation. 16

Caron, M., Touvron, H., Misra, I., Jégou, H., Mairal, J., Bojanowski, P., and Joulin, A. Emerging properties in self-supervised vision transformers. In Proceedings of the IEEE/CVF international conference on computer vision, pp. 9650–9660, 2021b. 3

Li, Z. and Hoiem, D. Learning without forgetting. IEEE transactions on pattern analysis and machine intelligence, 40(12): 2935–2947, 2017. 2

Chaudhry, A., Rohrbach, M., Elhoseiny, M., Ajanthan, T., Dokania, P., Torr, P., and Ranzato, M. Continual learning with tiny episodic memories. In Workshop on Multi-Task and Lifelong Reinforcement Learning, 2019. 6

McCloskey, M. and Cohen, N. J. Catastrophic interference in connectionist networks: The sequential learning problem. In Psychology of learning and motivation, volume 24, pp. 109– 165. Elsevier, 1989. 1

Chaudhry, A., Gordo, A., Dokania, P., Torr, P., and Lopez-Paz, D. Using hindsight to anchor past knowledge in continual learning. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pp. 6993–7001, 2021. 1

Nemhauser, G. L., Wolsey, L. A., and Fisher, M. L. An analysis of approximations for maximizing submodular set functions—i. Mathematical Programming, 14(1):265–294, 1978. 12

9

Leveraging Complementary Embeddings for Replay Selection in Continual Learning with Small Buffers Ni, Z., Tang, S., and Zhuang, Y. Self-supervised class incremental learning. arXiv preprint arXiv:2111.11208, 2021. 2, 3

Yu, Z., Dong, Z., Yu, C., Yang, K., Fan, Z., and Chen, C. P. A review on multi-view learning. Frontiers of Computer Science, 19(7):197334, 2025. 3

Oord, A. v. d., Li, Y., and Vinyals, O. Representation learning with contrastive predictive coding. arXiv preprint arXiv:1807.03748, 2018. 14

Zheng, Q., Zhu, J., Li, Z., Tian, Z., and Li, C. Comprehensive multi-view representation learning. Information Fusion, 89: 198–209, 2023. 3

Oquab, M., Darcet, T., Moutakanni, T., Vo, H., Szafraniec, M., Khalidov, V., Fernandez, P., Haziza, D., Massa, F., El-Nouby, A., Assran, M., Ballas, N., Galuba, W., Howes, R., Huang, P.Y., Li, S.-W., Misra, I., Rabbat, M., Sharma, V., Synnaeve, G., Xu, H., Jégou, H., Mairal, J., Labatut, P., Joulin, A., and Bojanowski, P. Dinov2: Learning robust visual features without supervision. arXiv preprint arXiv:2304.07193, 2023. 6

A. ProbCover-based variant of MERS We study the integration of supervised and self-supervised embeddings within a coverage-based selection strategy, namely ProbCover (Yehuda et al., 2022). ProbCover is an active-learning algorithm that formulates sample selection as a maximum coverage problem on a δ-neighborhood graph: given a small budget, it greedily selects points that maximize the number of previously uncovered neighbors within a fixed radius δ.

Papyan, V., Han, X. Y., and Donoho, D. L. Prevalence of neural collapse during the terminal phase of deep learning training. Proceedings of the National Academy of Sciences, 117 (40):24652–24663, 2020. doi: 10.1073/pnas.2015509117. 16 Ratcliff, R. Connectionist models of recognition memory: constraints imposed by learning and forgetting functions. Psychological review, 97(2):285, 1990. 1

To adapt ProbCover to the continual learning setting, we treat the current memory buffer as the unlabeled pool and the exemplar set as the selected subset. We further extend the method to operate over multiple embedding spaces, following the weighted multi-coverage formulation described in Section 3.2 of the main paper. The resulting procedure is summarized in Algorithm 2.

Rebuffi, S.-A., Kolesnikov, A., Sperl, G., and Lampert, C. H. icarl: Incremental classifier and representation learning. In Proceedings of the IEEE conference on Computer Vision and Pattern Recognition, pp. 2001–2010, 2017. 1, 6 Rolnick, D., Ahuja, A., Schwarz, J., Lillicrap, T., and Wayne, G. Experience replay for continual learning. Advances in neural information processing systems, 32, 2019. 1, 2, 6

Selection of δ in ProbCover

Serrà, J., Surı́s, D., Miron, M., and Karatzoglou, A. Overcoming catastrophic forgetting with hard attention to the task, 2018. URL https://arxiv.org/abs/1801.01423. 2

A critical hyperparameter in ProbCover is the cover-ball radius δ, which determines the granularity of the induced neighborhood graph. Since different embeddings exhibit markedly different geometric and density characteristics, using a fixed δ across embeddings is suboptimal.

Shaul-Ariel, S. and Weinshall, D. Teal: New selection strategy for small buffers in experience replay class incremental learning. arXiv preprint arXiv:2407.00673, 2024. 1, 2, 6 Tishby, N., Pereira, F. C., and Bialek, W. The information bottleneck method. arXiv preprint physics/0004057, 2000. 14

Following the nonparametric alignment strategy proposed in the main paper, we estimate δ from the data using classconditional k-NN statistics. For a class c, let Dc = {xi | yi = c}. For each xi ∈ Dc , denote by Nk (xi ) its k nearest neighbors in Dc \ {xi }, and define

Uelwer, T., Robine, J., Wagner, S. S., Höftmann, M., Upschulte, E., Konietzny, S., Behrendt, M., and Harmeling, S. A survey on self-supervised methods for visual representation learning. Machine Learning, 114(4):1–56, 2025. 3

ri = medianxj ∈Nk (xi ) ∥xi − xj ∥.

Vazirani, V. V. Approximation algorithms, volume 1. Springer, 2001. 4

We then set δ = medianxi ∈Dc ri .

Wang, T. and Isola, P. Understanding contrastive representation learning through alignment and uniformity on the hypersphere. In International conference on machine learning, pp. 9929– 9939. PMLR, 2020. 14, 15

The neighborhood size k is chosen adaptively via the memory-aware ratio

Welling, M. Herding dynamical weights to learn. In Proceedings of the 26th annual international conference on machine learning, pp. 1121–1128, 2009. 6

k=

|Dc | , Mc

where |Dc | is the number of class-c samples observed in the current episode and Mc is the class-specific buffer capacity. This choice links the effective resolution of the coverage graph to both the stream statistics and the available memory budget: larger buffers yield finer partitions, while smaller buffers induce coarser coverage.

Yehuda, O., Dekel, A., Hacohen, G., and Weinshall, D. Active learning through a covering lens. Advances in Neural Information Processing Systems, 35:22354–22367, 2022. 3, 10, 14 Yoon, J., Yang, E., Lee, J., and Hwang, S. J. Lifelong learning with dynamically expandable networks, 2018. URL https: //arxiv.org/abs/1708.01547. 2

10

Leveraging Complementary Embeddings for Replay Selection in Continual Learning with Small Buffers

B. Submodularity and greedy approximation for Multiple Embedding coverage

Algorithm 2 MERS ProbCover Require: Dataset C = {x1 , . . . , xn }, distances Dm , weights αm , buffer M, budget b, ball-size δ. Ensure: Updated memory buffer M. (m) (m) (m) 1: Bδ (xj ) ← {xi ∈ C | Dm (zxi , zxj ) ≤ δ} 2: for t = 1 to b do ▷ Greedy Set Cover selection PM (m) 3: xt ← arg maxxj ∈C\S m=1 αm Bδ (xj ) ∩ U

Proposition 1. The function F : 2X → R≥0 defined in Definition 3 is non-negative, normalized, monotone, and submodular. Proof. By Definition 3, there exists a finite index set U , non-negative weights {wu }u∈U , and subsets {Cu ⊆ X}u∈U such that for every L ⊆ X,

S ← S ∪ {xt } for m = 1 to M do ▷ Update uncovered set for all embeddings (m) 6: U ← U \ Bδ (xt ) 7: end for 8: end for 9: M ← M ∪ S; return M

4: 5:

F (L) =

X

  wu 1 L ∩ Cu ̸= ∅ ,

u∈U

where 1[·] is the indicator function. Non-negativity and normalization. Since all weights wu are non-negative and indicators are in {0, 1}, we have F (L) ≥ 0 for all L ⊆ X. For L = ∅ we have ∅ ∩ Cu = ∅ for every u ∈ U , hence all indicators are zero and F (∅) = 0. Thus F is non-negative and normalized. Monotonicity. Let A ⊆ B ⊆ X. If an index u ∈ U is covered by A, i.e., A ∩ Cu ̸= ∅, then since A ⊆ B we also have B ∩ Cu ̸= ∅. Therefore,

A.1. MERS ProbCover Main results We next evaluate MERS instantiated with ProbCover, following the same experimental protocol described in Section 6.1.

{u ∈ U : A ∩ Cu ̸= ∅} ⊆ {u ∈ U : B ∩ Cu ̸= ∅}, and by non-negativity of the weights, X X F (A) = wu ≤

As shown in Fig. 7, MERS ProbCover improves performance over the corresponding replay methods and selection strategies, particularly under tight memory constraints. While ProbCover can outperform the Max-Herding selection strategy in some configurations, MERS MaxHerding consistently achieves the strongest results overall.

u:A∩Cu ̸=∅

wu = F (B).

u:B∩Cu ̸=∅

Thus F is monotone. Submodularity. To show submodularity, let A ⊆ B ⊆ X and x ∈ X \ B. Consider the marginal gains

A.2. Selection stability Following the selection stability and forgetting analysis presented in Section 6.3, we analyze selection stability and forgetting for MERS ProbCover under varying memory budgets. Results for ER-ACE-STAR, ER-ACE, and ER on Split CIFAR-100 are shown in Figs. 9–11.

∆x (A) := F (A ∪ {x}) − F (A), ∆x (B) := F (B ∪ {x}) − F (B). By the definition of F ,

Consistent with the trends observed for Max-Herding, ProbCover based on self-supervised SimCLR embeddings exhibits higher selection stability and lower forgetting compared to ProbCover using supervised embeddings. This indicates that self-supervised representations lead to more consistent buffer composition over time, independent of the specific coverage objective. While ProbCover remains less stable than the corresponding Max-Herding variant, it improves over supervised embedding-based selection and reinforces the evidence presented in the main text regarding the stabilizing effect of self-supervised embeddings.

∆x (A) =

X

   wu 1 (A ∪ {x}) ∩ Cu ̸= ∅

u∈U

  − 1 A ∩ Cu ̸= ∅ X = wu . u∈U :x∈Cu , A∩Cu =∅

Indeed, u contributes to the marginal gain for A if and only if u was not covered by A (so A ∩ Cu = ∅) but becomes covered after adding x, which happens precisely when x ∈ Cu . 11

Leveraging Complementary Embeddings for Replay Selection in Continual Learning with Small Buffers

(a) ER-ACE-STAR

(b) ER-ACE

(c) ER

Figure 7. MERS ProbCover: FAA as a function of memory size |M | on Split CIFAR-100 for three continual learning algorithms, see Section 5.1. Results with MERS are compared against alternative selection strategies, see Section 5.2.

(a) FAA

(b) AAA

Figure 8. MERS ProbCover: FAA (right) and AAA (left) as a function of memory size |M | on Split CIFAR-100 with ER-ACE. Results with MERS are compared against alternative selection strategies.

C. Time and Space complexity of MERS

Analogously, ∆x (B) =

X

We analyse the computational cost under the standard setting in which the selection strategy is invoked once per training episode. Let n be the number of examples from the current episode that belong to class c, M the number of distinct embedding spaces, d the dimensionality of each embedding, and b the class-wise memory-buffer budget ( the number of items that |M| may store for class c).

wu .

u∈U :x∈Cu , B∩Cu =∅

Since A ⊆ B, we have {u ∈ U : x ∈ Cu , B ∩ Cu = ∅} ⊆ {u ∈ U : x ∈ Cu , A ∩ Cu = ∅}, and all weights are non-negative. Therefore

Self-supervised stage. During every episode, MERS is called exactly once. Running SimCLR for Essl epochs on A = 2 views of the n episode images costs

∆x (B) ≤ ∆x (A), which is exactly the submodularity inequality

TSimCLR = O(Essl A n P )

F (A ∪ {x}) − F (A) ≥ F (B ∪ {x}) − F (B).

with P trainable parameters. Self-supervised training consumes

Greedy approximation guarantee. Since F is nonnegative, normalized, monotone, and submodular, the greedy algorithm yields a (1 − 1/e)-approximation under a cardinality constraint (Nemhauser et al., 1978), i.e.,

SSimCLR = O(P + s f ) space model parameters P plus the current batch’s s activations of size f , and the batch size s. The SimCLR weights are discarded after each episode, persistent memory is dominated by the replay images.

∗

F (Lb ) ≥ (1 − 1/e) F (L ).

12

Leveraging Complementary Embeddings for Replay Selection in Continual Learning with Small Buffers

(a) Stability

(b) Forgetting

Figure 9. MERS ProbCover: Stability and forgetting of ER-ACE-STAR with MERS as a function of |M | on Split CIFAR-100.

(a) Stability

(b) Forgetting

Figure 10. MERS ProbCover: Stability and forgetting of ER-ACE with MERS as a function of |M | on Split CIFAR-100.

(a) Stability

(b) Forgetting

Figure 11. MERS ProbCover: Stability and forgetting of ER with MERS as a function of |M | on Split CIFAR-100.

13

Leveraging Complementary Embeddings for Replay Selection in Continual Learning with Small Buffers

C.0.1. MERS ProbCover

self-supervised representations. While the benefits of supervised embeddings are clear - they capture classdiscriminative structure, the goal here is to formalize the complementary value of self-supervised representations and explain when they can improve robustness to future classes. Specifically, in Section D.3 we show that sampling from SSL embeddings is likely to yield a tighter (smaller) bound on the train-test risk gap than sampling from SL embedding.

The algorithm consists of two stages: (i) Ball-graph construction. For every embedding m ∈ {1, . . . , M } we compute all pairwise cosine distances in (m) Rd to obtain the δ-neighbourhoods
Bδ (x). This step 2 costs Tgraph = O M n max{d, b} and stores Sgraph = O(M n2 ) adjacency edges.

To this end we make the following assumptions:

(ii) Greedy covering. Across b iterations we repeatedly pick the vertex that covers the largest number of stilluncovered neighbours. The work per iteration yields Tcover = O(|E| + b n) ⊆ O(M n2 + b n).

1. Geometry under supervision vs. self-supervision. Supervised learning (SL) tends to concentrate representation variability in a relatively lowdimensional, class-discriminative subspace, whereas self-supervised learning (SSL) tends to preserve a broader set of non-label factors that are stable across views and yields representations that are universally good for images (or domain objects), regardless of class label.

Overall complexity.
TMERS-ProbCover = O M n2 max d, b , SMERS-ProbCover = O(M n2 ), The original ProbCover analysis (Yehuda
et al., 2022) reports a running time of O n2 max{d, b} . Our derivation shows that the Multiple Embedding extension, MERS –ProbCover, retains the same quadratic dependence on n and on max d, b, differing only by the multiplicative factor M (which equals 2 in all of our experiments).

2. Matched global scale (equal compression). When comparing SL and SSL for coverage-based selection, we normalize the embeddings so that both have the same global scale/compression level.

(ii) Greedy MaxHerding selection. (i) Integrated-kernel construction. Gram matrix Kij = k(xi , xj ) =

M X

Assumption 1 is motivated by standard informationtheoretic and geometric perspectives: (i) supervised training encourages label-sufficient compression of representations (Tishby et al., 2000; Alemi et al., 2017); (ii) contrastive self-supervision can be viewed as maximizing agreement (shared information) between augmented views while simultaneously promoting spread/uniformity (or decorrelation) of representations (Oord et al., 2018; Wang & Isola, 2020).

We assemble the

(m)

αm km xi

(m)

, xj

.

m=1

Forming its 12 n(n − 1) entries costs Tkernel = O(mn2 d),

Skernel = O(n2 ).

Assumption 2 follows from the scale handling in our selection objectives. Both ProbCover and MaxHerding include an explicit length-scale hyper-parameter (δ and σ, respectively) that is chosen so as to make the procedure effectively scale-invariant. Therefore, when comparing the selected sets under two different embeddings, we first align their global scale to ensure a fair comparison and to prevent trivial differences caused by an overall rescaling.

(ii) Greedy selection. Each of the b iterations scans all candidates (≤ n) and exploits the pre-computed kernel: TMaxHerding = O(b n2 ),

SMaxHerding = O(n).

Overall complexity.

For the purposes of the following analysis, we assume there exists a feature space Rn in which the classconditional distribution of each class, past and future, can be approximated by a Gaussian N (µ, Σ) in Rn with Σ positive-definite. We interpret this space as emphasizing class-relevant factors of variation, abstracting away labelirrelevant features due to such factors as illumination, pose, or background.

TMERS–MaxHerding = O mn2 (d + b) ,
SMERS–MaxHerding = O n2 + nd .

D. Detailed Theoretical Analysis In this section we present a theoretical analysis that motivates sampling from a mixture of supervised and 14

Leveraging Complementary Embeddings for Replay Selection in Continual Learning with Small Buffers

p Since Vol(EΣ′ ) = Vol(B1 ) det(Σ′ ), where B1 is the unit ball in Rn , equal volume is equivalent to matching determinants:

D.1. Selective feature compression increases class conditional divergence In this section we show that the probabilistic distortion induced by an anisotropic embedding is typically larger, as measured by KL divergence, than the distortion induced by an isotropic embedding, or by an embedding that preserves the isotropy of the original distribution.

Vol(EΣ1 ) = Vol(EΣ2 )

i =1: det(Σ1/2 DΣ1/2 ) = det(σΣ) ⇐⇒ det(D) = σ n ⇐⇒ αm β n−m = σ n . i =2: det(Σ1/2 DΣ1/2 ) = det(σIn ) ⇐⇒ det(D) · det(Σ) = σ n ⇐⇒ σn . αm β n−m = det(Σ)

Using Assumption 1. Our method MERS selects a representative set for this class using an alternative embedding, which induces a (potentially) different class-conditional distribution in Rn . By Assumption 1, we model the classconditional distribution under SSL and SL as follows:

Lemma 1 (KL-divergence). The KL-divergence between the true class conditional distribution Go and the SSLinduced distribution can be expressed as follows:

SSL. As idealized proxies for a representation that preserves broad, view-stable factors and avoids label-induced anisotropy, we consider two SSL-induced class-conditional models:

i =1:

The KL-divergence between Go and the SL-induced distribution is:

(1)

The first model, GSSL , corresponds to the idealized case in which SSL recovers the true class geometry up to a global rescaling; while optimistic, it yields cleaner expressions and serves as a convenient analytic baseline. The second (2) model, GSSL , represents an isotropic (whitened) geometry - a more faithful proxy for the “uniformity” pressure in contrastive objectives, which encourages representations to spread approximately uniformly on (or near) a sphere (Wang & Isola, 2020).

i=1:

i=2:

SL. We model label-driven selective compression by an anisotropic rescaling of the covariance. For some m ∈ {1, . . . , n − 1},
GSL := N 0, Σ1/2 DΣ1/2 , m times

 1n − n + n ln σ , 2 σ  1 1 (2) DKL (Go ∥GSSL ) = tr(Σ) − n 2 σ  +n ln σ − ln det(Σ) ; (1)

DKL (Go ∥GSSL ) =

i=2:

σ ∈ (0, 1),

D = diag(α, . . . , α, β, . . . , β ), | {z } | {z }

det(Σ1 ) = det(Σ2 ).

Thus, this constraint is equivalent to

Consider a single class from the current episode. Without loss of generality, assume its mean is at the origin and its class-conditional distribution in the reference feature space is Go := N (0, Σ).

(1) GSSL := N (0, σΣ), (2) GSSL := N (0, σIn ).

⇐⇒

 1m n−m + − n + n ln σ , 2 α β (7)  1 m n−m DKL (Go ∥GSL ) = + − n + n ln σ− 2 α β  ln det(Σ) . (8) DKL (Go ∥GSL ) =

Proof. These identities follow from the standard KLdivergence formula for zero-mean Gaussians with positive definite covariance matrices:

α > β > 0.

 
det(Σ1 ) DKL N (0, Σ0 ) ∥ N (0, Σ1 ) = 21 tr(Σ−1 1 Σ0 ) − n + ln det(Σ0 ) ,

n−m times

and the equal-volume constraints in (D.1).

Here, the m directions scaled by α represent classdiscriminative variability retained by supervision, while the remaining n − m directions are compressed by β.

Proposition 2. For i = 1, anisotropy increases DKL (Go ∥ · ) under equal volume:

Enforcing Assumption 2. We match the volume of the covariance ellipsoids, i.e., the Mahalanobis level sets

(1)

DKL (Go ∥GSL ) ≥ DKL (Go ∥GSSL ),

EΣ′ := {x ∈ Rn : x⊤ (Σ′ )−1 x ≤ 1}.

DKL (Go ∥GSL ) −−−→ ∞, (1) DKL (Go ∥GSSL ) β→0

with equality in the first expression iff α = β = σ. 15

Leveraging Complementary Embeddings for Replay Selection in Continual Learning with Small Buffers

Single-class conditional shift assumption. Let Rn denote the input space and let Y = {1, . . . , K} be the label space. Label Y = 1 corresponds to a class from the current episode; without loss of generality we assume its mean satisfies µ1 = 0. Labels Y = 2, . . . , K correspond to the K −1 classes that will appear in the next episode. We write Ci for the class associated with label Y = i, for i ∈ [K].

Proof. By Lemma 1, together with (1) and (7), (1)

DKL (Go ∥GSL )−DKL (Go ∥GSSL ) =

1m n − m n + − . 2 α β σ

To show that this expression is nonnegative, we apply the weighted AM–GM inequality to α1 and β1 with weights m n and n−m n :

When constructing the training set for the next episode, classes {Ci }K i=2 are sampled from their original classconditional distributions N (µi , Σi ) in Rn , as assumed above. In contrast, class C1 is represented by the exemplars stored in the replay buffer, which reflect the (possibly distorted) class-conditional distribution induced by the new embedding.

 1 m/n  1 (n−m)/n m1 n−m 1 + ≥ nα n β α β 1 1 = m/n (n−m)/n = , σ α β where the last equality uses the equal-volume constraint αm β n−m = σ n in (D.1).

As customary in domain adaptation, let S := Ptr (X, Y ) denote the source/train distribution and T := Pte (X, Y ) the target/test distribution. In our setting the two distributions coincide except for the class-conditional distribution of C1 .1 In particular,

To see the asymptotic result, note that as β → 0 under αm β n−m = σ n , we have α → ∞ and m α → 0 while n−m → ∞, which implies that D (G KL o ∥GSL ) → ∞ β (1)

whereas DKL (Go ∥GSSL ) remains finite.

Ptr (Y = y) = Pte (Y = y) ∀y ∈ Y,

Proposition 3. For i = 2, there exists β0 > 0 such that (2)

DKL (Go ∥GSL ) ≥ DKL Go ∥GSSL

Ptr (X | Y = y) = Pte (X | Y = y) ∀y ̸= 1, ∀β < β0 ,

but Ptr (X | Y = 1) ̸= Pte (X | Y = 1). Let π1 := Pte (Y = 1) = Ptr (Y = 1).

DKL (Go ∥GSL ) −−−→ ∞. (2)
DKL Go ∥GSSL β→0

Domain adaptation bound For a classifier h : X → Y, the 0–1 loss is ℓ01 (h(x), y) := 1{h(x)̸=y} ∈ [0, 1], and the corresponding risk is

Proof. By Lemma 1, together with (1) and (8), (2)

DKL (Go ∥GSL ) − DKL (Go ∥GSSL ) 1  m n − m tr(Σ)  + − . = 2 α β σ

    RD (h) := P(X,Y )∼D h(X) ̸= Y = E(X,Y )∼D ℓ01 (h(X), Y ) .

Theorem 1 (Train–test risk gap controlled by the shifted class). For any classifier h,

As β → 0 under αm β n−m = σ n / det Σ, necessarily α → n−m ∞, so m → ∞. Therefore the difference α → 0 while β above is positive for all sufficiently small β, proving the existence of β0 and the asymptotic result.

  |RT (h) − RS (h)| ≤ π1 dTV Ptr (X | Y = 1), Pte (X | Y = 1) .

where dTV denotes the total variation distance. Proof. It is known (see, e.g., Levin et al., 2017) that for probability measures S, T on the same measurable space and any measurable f : X × Y → [0, 1],

The asymptotic results show that, in the highly anisotropic regime (e.g., when β is very small, as suggested by a strong form of “neural collapse” (Papyan et al., 2020)), the KL gap between the SL and SSL proxies can become arbitrarily large.

ES f − ET f ≤ dTV (S, T ) := sup |S(A) − T (A)| A

= sup ES g − ET g . 0≤g≤1

D.2. Class conditional shift and domain adaptation

Moreover, since by assumption S(x, y) = πy Ptr (x | y), T (x, y) = πy Pte (x | y) and Ptr (x | y) = Pte (x | y) for all y ̸= 1, we get

In this section we cast class-incremental learning as a domain adaptation problem, where the effective data distribution shifts between episodes. Since MERS selects representatives on a per-class basis within the current episode, we focus on the resulting class-conditional shift and study how it affects a downstream classification task: distinguishing the current class from the K − 1 new classes that will appear in the next episode.

  ES [f (X, Y )] − ET [f (X, Y )] = π1 EPtr (X|1) [f (X, 1)] − EPte (X|1) [f (X, 1)] . 1

The CIL training procedure rebalances the class prior, ensuring that P (Y = 1) matches between train and test regardless of the buffer size.

16

Leveraging Complementary Embeddings for Replay Selection in Continual Learning with Small Buffers

Taking f (X, Y ) = ℓ01 (h(X), Y ), we obtain

E. Hyperparameters

|RT (h) − RS (h)| = π1 EPtr (X|1) [ℓ01 (h(X), 1)]−
EPte (X|1) [ℓ01 (h(X), 1)]big| ≤ π1 dTV Ptr (X | 1), Pte (X | 1) ,

E.1. classification model we employ a ResNet-18 backbone trained for 100 epochs with a batch size of 10. The ER-ACE configuration begins with a learning rate of 0.01. The ER and MIR configuration begins with a learning rate of 0.1, for all configurations, SGD optimization includes Nesterov momentum of 0.9 and weight decay 0.0002. The learning rate is decayed by a factor of 0.3 every 66 epochs. All experiments were run with five random seeds (0-4).

which proves the claim. Corollary 1 (KL-controlled train–test risk gap). For any classifier h, r |RT (h) − RS (h)| ≤ π1



 = 1) Ptr (X | Y = 1) .



 = 1) Ptr (X | Y = 1) .

1 2 DKL Pte (X | Y

Equivalently, r RT (h) ≤ RS (h) + π1

1 2 DKL Pte (X | Y

E.2. class order We follow the canonical class order for each benchmark: Split CIFAR-100 uses classes [1 . . . 100], and Split TinyImageNet uses classes [1 . . . 200].

Proof. The result follows from Pinsker’s inequality (Cover & Thomas, 2006), which states that for distributions P, Q with finite DKL (P ∥Q), r 1 DKL (P ∥Q). dTV (P, Q) ≤ 2

E.3. Self-Supervised Training Our SimCLR and VICREeg implementation is adapted from solo-learn(da Costa et al., 2022), and is available in the source code. The self-supervised model is trained on the images observed in the current episode only, never on the full dataset. For DINOv2, we extract frozen embeddings from a pretrained foundational model, specifically the dinov2 vitb14 backbone, 768-dimensional, without any further fine-tuning.

D.3. The benefits of using the SSL embedding Proposition 4 (SSL yields a tighter DA-style bound than SL). Under the setup of Section D.1 and the equalvolume normalization, the SSL embedding yields a tighter (smaller) bound on the train-test risk gap than the SL embedding.

E.4. Feature Normalization Each feature vector is divided by its ℓ2 norm, yielding unitnorm representations. Similarities are therefore computed with the cosine distance.

Proof. In the notation of Section D.1, the test conditional for class 1 is Pte (X | Y = 1) = Go , while the correspond(i) ing training conditional is Ptr (X | Y = 1) = GSSL (under SSL) or GSL (under SL). Applying Corollary 1 gives, for any classifier h, r 1 (i)
|RT (h) − RS (h)| ≤ π1 DKL Go ∥GSSL 2 (SSL embedding),

F. Compute resources Each experiment trained deep-learning models on GPUs, consuming up to 22 GB of GPU memory and no more than 20 GB of system RAM.

G. Source code

and r |RT (h) − RS (h)| ≤ π1

The complete source code is provided in the supplementary ZIP file and will be publicly released on GitHub upon acceptance. The source code includes a README that lists the commands required to reproduce all of the experiments described in this paper.

1 DKL Go ∥GSL 2 (SL embedding).

Under equal volume, Proposition 2 implies (1) DKL (Go ∥GSL ) ≥ DKL (Go ∥GSSL ), and Proposition 3 shows that for sufficiently small β, (2) DKL (Go ∥GSL ) ≥ DKL (Go ∥GSSL ). In either case, the KL term, and hence the right-hand side of the bound, is smaller under SSL than under SL, which proves the claim.

H. Additional results H.1. Main results tables The tables 3a- 2 presents the complete tables for the results in Section 6.1, evaluated with both the FAA and AAA met17

Leveraging Complementary Embeddings for Replay Selection in Continual Learning with Small Buffers

rics. H.2. Selection stability We provide additional results for ER and We provide additional results for ER and ER-ACE on Split CIFAR-100, reported in Fig. 13- 14

I. Ablation Study We compare MERS against a MaxHerding variant that relies solely on SSL embeddings. As shown in Fig. 4, MERS consistently achieves higher FAA and AAA accuracy, highlighting the benefit of combining Self-Supervised and Supervised representations. Fig. 15 presents an ablation study on the effect of the embedding weight parameter α when using the median K-NN density defined in Eq. 4, applied to MERS ProbCover on Split CIFAR-100 under the ER-ACE setting. The results indicate a slight but consistent improvement when using the formulation of α given in Eq. 5.

Figure 15. MERS MaxHerding. Ablation of the embedding weight α using K-NN density estimators on Split CIFAR-100 with ER-ACE. The baseline corresponds to Eq. (5), and a minor but consistent improvement is observed with this weighting.

J. Robustness to Episode Class Order in Continual Learning As in the experiments presented in Tables 1–2, we repeated them using different episode Class orders. Below are the Final Averaged Accuracy and the Anytime Averaged Accuracy Tables 4- 7.

18

Leveraging Complementary Embeddings for Replay Selection in Continual Learning with Small Buffers

Table 3. Final Averaged Accuracy (FAA) on Split CIFAR-100 with three CL algorithms ,averaged over 5 independent runs (mean ± standard error). For each |M|, the best FAA is in bold. (a) ER ACE STAR Random

ProbCover

Buffer Supervised Supervised Supervised 100 300 500 1000 2000

Herding

MaxHerding MERS

TEAL

Supervised Supervised

21.93 ±0.17 29.32 ±0.20 32.04 ±0.32 33.43 ±0.44 21.57 ±0.30 29.68 ±0.36 31.85 ±0.38 41.47 ±0.24 42.07 ±0.28 44.00 ±0.18 33.47 ±0.21 41.33 ±0.26 36.68 ±0.49 45.39 ±0.17 46.43 ±0.19 47.81 ±0.15 38.28 ±0.19 45.76 ±0.34 44.62 ±0.20 50.96 ±0.25 50.86 ±0.27 53.50 ±0.30 44.81 ±0.15 50.98 ±0.26 51.31 ±0.27 55.49 ±0.20 56.27 ±0.37 58.44 ±0.24 51.30 ±0.24 55.56 ±0.15 (b) ER ACE Random

ProbCover

Buffer Supervised Supervised Supervised 100 300 500 1000 2000

Herding

MaxHerding MERS

TEAL

Supervised Supervised

21.80 ±0.34 28.13 ±0.35 29.35 ±0.30 30.95 ±0.44 22.08 ±0.16 29.67±0.13 32.01 ±0.30 38.30 ±0.15 39.33 ±0.13 40.55 ±0.28 29.94 ±0.22 37.60 ±0.25 36.29 ±0.52 42.22 ±0.25 43.55 ±0.10 45.26 ±0.19 35.58 ±0.22 41.44 ±0.23 43.30 ±0.21 48.44 ±0.22 49.19 ±0.23 50.64 ±0.32 42.71 ±0.12 47.33 ±0.24 50.14 ±0.30 53.85 ±0.27 53.69 ±0.26 55.42 ±0.21 50.09 ±0.21 53.04 ±0.12 (c) ER

Random

ProbCover

MaxHerding

|M| Supervised Supervised Supervised

MERS

Herding

TEAL

Rainbow

Supervised Supervised Supervised

300 13.25 ±0.10 16.29 ±0.21 17.60 ±0.18 17.74 ±0.25 16.02±0.20 17.06 ±0.13 13.46 ±0.10 500 17.69 ±0.30 22.03 ±0.17 23.54 ±0.15 23.78 ±0.14 20.20±0.85 22.49 ±0.20 16.98 ±0.60 1000 26.04 ±0.24 31.65 ±0.29 32.78 ±0.32 33.26 ±0.24 29.80±0.35 31.92 ±0.43 26.72 ±0.17 2000 38.30 ±0.23 42.76 ±0.09 42.88 ±0.22 43.89 ±0.33 41.74±0.29 42.22 ±0.51 38.40 ±0.22

(a) ER-ACE-STAR

(b) ER-ACE

Figure 12. AAA as a function of memory size |M | on Split CIFAR-100 for different continual learning algorithms. Results with MERS are compared against alternative selection strategies.

19

Leveraging Complementary Embeddings for Replay Selection in Continual Learning with Small Buffers

(a) Stability

(b) Forgetting

Figure 13. Stability and forgetting of ER-ACE with MERS as a function of |M | on Split CIFAR-100.

(a) Stability

(b) Forgetting

Figure 14. Stability and forgetting of ER with MERS as a function of |M | on Split CIFAR-100.

20

Leveraging Complementary Embeddings for Replay Selection in Continual Learning with Small Buffers

Table 4. FAA with a different class ordering, averaged over 5 independent runs (mean ± standard error). Several sample-selection strategies and embedding spaces are compared across multiple replay-buffer sizes (|M|). For each |M|, the best AAA is in bold; result within the standard error of the best are also bolded. (a) FAA on Split CIFAR-100 ER ACE. Random

MERS ProbCover

Buffer Supervised Supervised 100 300 500 1000 2000 4000 5000

20.79 ±0.27 31.76 ±0.07 35.80 ±0.32 42.27 ±0.22 49.41 ±0.18 55.32 ±0.24 57.96 ±0.21

SimCLR

MERS MaxHerding MERS

Supervised

SimCLR

MERS

29.81 ±0.20 27.82 ±0.25 29.35 ±0.24 29.42 ±0.11 29.20 ±0.33 29.89 ±0.22 38.84 ±0.19 37.78 ±0.14 39.47 ±0.28 38.16 ±0.35 38.73 ±0.36 39.60 ±0.25 42.46 ±0.23 42.25 ±0.19 43.28 ±0.23 42.72 ±0.23 42.82 ±0.21 43.71 ±0.21 47.69 ±0.23 48.11 ±0.19 48.98 ±0.27 47.77 ±0.21 48.89 ±0.27 50.00 ±0.16 52.99 ±0.07 53.53 ±0.24 54.17 ±0.19 53.18 ±0.20 54.20 ±0.28 54.80 ±0.19 58.03 ±0.11 58.79 ±0.24 59.28 ±0.18 58.52 ±0.20 58.56 ±0.34 59.03 ±0.19 60.10 ±0.11 60.79 ±0.19 60.84 ±0.27 59.85 ±0.18 59.90 ±0.11 60.07 ±0.13 (b) FAA on Split CIFAR-100 ER.

Random

MERS ProbCover

Buffer Supervised Supervised 100 300 500 1000 2000 4000 5000

10.50 ±0.14 14.67 ±0.24 19.86 ±0.31 28.48 ±0.22 40.45 ±0.23 51.23 ±0.22 55.03 ±0.20

SimCLR

MERS MaxHerding MERS

Supervised

SimCLR

MERS

13.02 ±0.11 11.44 ±0.13 12.18 ±0.08 12.53 ±0.18 12.24 ±0.07 12.79 ±0.12 20.32 ±0.26 19.01 ±0.34 20.33 ±0.21 19.62 ±0.17 18.83 ±0.56 19.52 ±0.33 25.37 ±0.18 23.68 ±0.35 25.01 ±0.44 25.73 ±0.22 24.25 ±0.22 25.74 ±0.55 34.37 ±0.33 33.62 ±0.29 35.18 ±0.21 34.54 ±0.34 34.43 ±0.35 35.40 ±0.20 43.84 ±0.32 44.34 ±0.31 45.38 ±0.28 44.62 ±0.19 44.76 ±0.37 45.58 ±0.40 53.91 ±0.20 54.37 ±0.20 54.97 ±0.27 54.69 ±0.32 54.01 ±0.16 54.81 ±0.16 56.75 ±0.13 57.16 ±0.25 57.79 ±0.22 56.67 ±0.23 56.49 ±0.21 57.06 ±0.23 (c) FAA on Split CIFAR-100 ER ACE.

Random

MERS ProbCover

Buffer Supervised Supervised 200 400 600 1000 2000 4000 6000

11.89 ±0.13 13.27 ±0.12 13.47 ±0.08 14.50 ±0.16 16.59 ±0.15 19.11 ±0.13 22.57 ±0.06

SimCLR

MERS MaxHerding MERS

Supervised

SimCLR

MERS

13.95 ±0.17 12.58 ±0.05 13.33 ±0.09 13.54 ±0.07 13.50 ±0.14 13.91 ±0.25 15.69 ±0.12 14.33 ±0.12 15.16 ±0.11 14.72 ±0.21 15.00 ±0.10 15.35 ±0.19 16.44 ±0.06 15.42 ±0.19 16.64 ±0.24 15.71 ±0.18 16.07 ±0.10 16.37 ±0.31 18.16 ±0.19 16.99 ±0.19 18.44 ±0.11 17.51 ±0.16 17.26 ±0.15 17.89 ±0.12 20.50 ±0.21 19.71 ±0.19 21.03 ±0.09 20.08 ±0.23 19.50 ±0.20 20.26 ±0.27 23.09 ±0.15 22.94 ±0.17 24.45 ±0.20 23.18 ±0.21 22.43 ±0.33 22.94 ±0.20 25.41 ±0.20 25.42 ±0.30 26.40 ±0.26 25.66 ±0.19 24.66 ±0.18 25.02 ±0.15

21

Leveraging Complementary Embeddings for Replay Selection in Continual Learning with Small Buffers

Table 5. FAA with a different class ordering, averaged over 5 independent runs (mean ± standard error). Several sample-selection strategies and embedding spaces are compared across multiple replay-buffer sizes (|M|). For each |M|, the best AAA is in bold; result swithin the standard error of the best are also bolded. (a) FAA on Split CIFAR-100 ER ACE. Random

MERS ProbCover

Buffer Supervised Supervised 100 300 500 1000 2000 4000 5000

20.59 ±0.23 28.61 ±0.05 35.30 ±0.19 41.99 ±0.16 49.00 ±0.23 56.89 ±0.11 58.75 ±0.22

SimCLR

MERS MaxHerding MERS

Supervised

SimCLR

MERS

27.64 ±0.44 25.67 ±0.45 27.42 ±0.32 28.10 ±0.30 28.30 ±0.44 29.35 ±0.25 37.84 ±0.14 36.90 ±0.31 38.88 ±0.21 37.70 ±0.34 37.63 ±0.31 39.19 ±0.19 42.23 ±0.19 41.75 ±0.18 43.55 ±0.23 42.02 ±0.25 42.42 ±0.13 44.02 ±0.38 48.18 ±0.22 48.36 ±0.15 48.96 ±0.25 47.89 ±0.23 48.71 ±0.30 49.63 ±0.30 53.20 ±0.22 53.51 ±0.08 54.44 ±0.28 53.67 ±0.22 54.30 ±0.14 55.11 ±0.10 59.01 ±0.27 59.18 ±0.12 59.73 ±0.15 59.30 ±0.05 59.23 ±0.14 59.67 ±0.10 60.45 ±0.18 60.65 ±0.11 61.40 ±0.22 60.17 ±0.11 60.37 ±0.09 60.94 ±0.07 (b) FAA on Split CIFAR-100 ER.

Random

MERS ProbCover

Buffer Supervised Supervised 100 300 500 1000 2000

9.95 ±0.07 13.71 ±0.09 17.41 ±0.38 27.44 ±0.48 39.78 ±0.30

SimCLR

MERS MaxHerding MERS

Supervised

SimCLR

MERS

11.45 ±0.11 10.32 ±0.06 11.17 ±0.17 11.19 ±0.05 11.05 ±0.18 11.51 ±0.01 18.87 ±0.11 17.16 ±0.14 18.71 ±0.25 18.10 ±0.34 18.01 ±0.22 18.71 ±0.25 23.75 ±0.39 22.37 ±0.34 24.66 ±0.14 24.11 ±0.15 23.40 ±0.15 24.66 ±0.29 33.50 ±0.17 32.51 ±0.48 33.99 ±0.27 33.70 ±0.20 33.27 ±0.16 34.64 ±0.31 43.73 ±0.01 43.74 ±0.30 44.02 ±0.20 44.06 ±0.30 44.01 ±0.20 45.22 ±0.16 (c) FAA on Split CIFAR-100 ER ACE.

Random

MERS ProbCover

Buffer Supervised Supervised 200 400 600 1000 2000 4000 6000

11.39 ±0.10 11.98 ±0.24 12.90 ±0.13 14.14 ±0.09 15.94 ±0.16 19.42 ±0.22 22.05 ±0.25

SimCLR

MERS MaxHerding MERS

Supervised

SimCLR

MERS

13.23 ±0.12 12.22 ±0.14 12.75 ±0.13 13.11 ±0.08 12.71 ±0.11 12.95 ±0.09 15.09 ±0.21 13.70 ±0.16 14.71 ±0.24 13.84 ±0.15 14.12 ±0.21 14.51 ±0.16 16.18 ±0.12 14.68 ±0.08 15.78 ±0.18 14.97 ±0.19 15.48 ±0.13 15.14 ±0.06 17.67 ±0.26 16.21 ±0.22 17.47 ±0.15 16.61 ±0.11 16.32 ±0.18 16.77 ±0.10 19.88 ±0.24 18.60 ±0.23 20.42 ±0.29 19.70 ±0.34 19.01 ±0.14 19.21 ±0.22 22.86 ±0.13 23.05 ±0.35 24.08 ±0.07 22.80 ±0.12 21.84 ±0.28 21.84 ±0.23 25.98 ±0.34 25.63 ±0.30 26.53 ±0.13 25.14 ±0.23 24.43 ±0.28 25.23 ±0.25

22

Leveraging Complementary Embeddings for Replay Selection in Continual Learning with Small Buffers

Table 6. AAA with a different class ordering, averaged over 5 independent runs (mean ± standard error). Several sample-selection strategies and embedding spaces are compared across multiple replay-buffer sizes (|M|). For each |M|, the best AAA is in bold; result swithin the standard error of the best are also bolded. (a) AAA on Split CIFAR-100 ER ACE. Random

MERS ProbCover

Buffer Supervised Supervised 100 300 500 1000 2000 4000 5000

39.94 ±0.09 49.19 ±0.10 52.85 ±0.08 57.60 ±0.13 62.35 ±0.14 66.73 ±0.17 68.32 ±0.16

SimCLR

MERS MaxHerding MERS

Supervised

SimCLR

MERS

46.09 ±0.08 45.60 ±0.09 46.90 ±0.18 46.21 ±0.18 46.17 ±0.11 46.78 ±0.27 53.33 ±0.07 53.62 ±0.09 54.30 ±0.13 53.46 ±0.30 53.92 ±0.19 54.68 ±0.14 56.55 ±0.15 56.76 ±0.12 57.07 ±0.26 56.52 ±0.12 57.34 ±0.10 57.77 ±0.07 60.65 ±0.09 60.90 ±0.10 61.46 ±0.06 60.60 ±0.23 61.25 ±0.06 61.97 ±0.17 64.36 ±0.20 64.85 ±0.11 64.91 ±0.12 64.29 ±0.13 65.01 ±0.08 65.26 ±0.15 68.22 ±0.09 68.39 ±0.17 68.67 ±0.14 68.20 ±0.14 67.97 ±0.08 68.16 ±0.07 69.36 ±0.08 69.92 ±0.15 69.80 ±0.17 69.40 ±0.14 69.07 ±0.04 69.20 ±0.10 (b) AAA on Split CIFAR-100 ER.

Random

MERS ProbCover

Buffer Supervised Supervised 100 300 500 1000 2000 4000 5000

28.19 ±0.11 34.42 ±0.42 40.31 ±0.21 48.62 ±0.24 58.66 ±0.23 66.49 ±0.18 68.89 ±0.17

SimCLR

MERS MaxHerding MERS

Supervised

SimCLR

MERS

30.89 ±0.07 29.72 ±0.24 30.51 ±0.16 30.31 ±0.11 30.37 ±0.15 30.49 ±0.15 38.55 ±0.37 38.12 ±0.33 39.30 ±0.13 38.44 ±0.25 37.92 ±0.46 38.37 ±0.42 43.90 ±0.27 42.60 ±0.39 43.55 ±0.34 43.74 ±0.09 43.58 ±0.37 44.68 ±0.31 51.78 ±0.20 51.86 ±0.22 52.58 ±0.35 51.67 ±0.37 52.27 ±0.31 52.71 ±0.25 59.70 ±0.47 60.57 ±0.20 61.48 ±0.18 60.68 ±0.13 60.73 ±0.37 60.49 ±0.28 67.67 ±0.23 67.41 ±0.17 68.30 ±0.32 68.10 ±0.12 67.35 ±0.27 68.12 ±0.11 69.58 ±0.18 69.53 ±0.22 70.13 ±0.21 69.02 ±0.21 69.21 ±0.32 69.43 ±0.05 (c) AAA on Split CIFAR-100 ER ACE.

Random

MERS ProbCover

Buffer Supervised Supervised 200 400 600 1000 2000 4000 6000

25.92 ±0.07 27.78 ±0.16 28.96 ±0.07 30.49 ±0.05 33.23 ±0.13 36.95 ±0.13 39.66 ±0.12

SimCLR

MERS MaxHerding MERS

Supervised

SimCLR

MERS

28.32 ±0.06 27.43 ±0.10 28.17 ±0.11 27.91 ±0.09 27.93 ±0.09 28.20 ±0.08 30.60 ±0.13 29.61 ±0.07 30.50 ±0.09 29.73 ±0.05 29.94 ±0.10 30.10 ±0.10 31.60 ±0.13 30.94 ±0.09 31.82 ±0.08 31.18 ±0.09 31.40 ±0.15 31.56 ±0.13 33.60 ±0.15 33.05 ±0.13 34.08 ±0.10 33.43 ±0.12 33.12 ±0.20 33.22 ±0.11 36.09 ±0.13 35.84 ±0.11 36.86 ±0.05 36.08 ±0.14 35.51 ±0.14 36.04 ±0.20 39.32 ±0.13 39.06 ±0.10 39.87 ±0.12 39.10 ±0.12 38.47 ±0.09 38.57 ±0.12 40.90 ±0.12 41.19 ±0.10 41.67 ±0.08 40.94 ±0.15 40.08 ±0.10 40.26 ±0.16

23

Leveraging Complementary Embeddings for Replay Selection in Continual Learning with Small Buffers

Table 7. AAA with a different class ordering, averaged over 5 independent runs (mean ± standard error). Several sample-selection strategies and embedding spaces are compared across multiple replay-buffer sizes (|M|). For each |M|, the best AAA is in bold; result swithin the standard error of the best are also bolded. (a) AAA on Split CIFAR-100 ER ACE. Random

MERS ProbCover

Buffer Supervised Supervised 100 300 500 1000 2000 4000 5000

41.79 ±0.14 51.26 ±0.11 56.12 ±0.28 61.84 ±0.20 66.46 ±0.05 71.57 ±0.10 72.95 ±0.09

SimCLR

MERS MaxHerding MERS

Supervised

SimCLR

MERS

47.76 ±0.18 47.34 ±0.14 48.44 ±0.08 48.51 ±0.17 48.63 ±0.15 49.18 ±0.11 56.10 ±0.12 56.54 ±0.18 57.50 ±0.13 56.33 ±0.17 57.15 ±0.14 57.78 ±0.13 59.79 ±0.14 60.32 ±0.15 61.35 ±0.08 60.28 ±0.12 60.63 ±0.12 61.45 ±0.11 64.49 ±0.20 65.41 ±0.12 65.54 ±0.14 64.56 ±0.12 65.04 ±0.17 65.79 ±0.22 68.70 ±0.17 68.92 ±0.18 69.02 ±0.15 68.87 ±0.12 69.22 ±0.09 69.29 ±0.17 72.34 ±0.17 72.52 ±0.11 73.00 ±0.03 72.53 ±0.06 72.30 ±0.21 72.44 ±0.13 73.61 ±0.10 73.48 ±0.09 74.22 ±0.12 73.14 ±0.09 73.36 ±0.14 73.66 ±0.03 (b) AAA on Split CIFAR-100 ER.

Random

MERS ProbCover

Buffer Supervised Supervised 100 300 500 1000 2000

29.82 ±0.13 37.89 ±0.08 43.07 ±0.17 52.56 ±0.13 62.59 ±0.15

SimCLR

MERS MaxHerding MERS

Supervised

SimCLR

MERS

32.42 ±0.04 31.62 ±0.12 32.58 ±0.20 32.28 ±0.08 32.09 ±0.16 32.58 ±0.17 42.18 ±0.13 41.20 ±0.14 42.32 ±0.15 41.33 ±0.18 41.74 ±0.14 42.39 ±0.04 47.15 ±0.13 47.20 ±0.09 48.48 ±0.09 47.70 ±0.09 47.64 ±0.12 48.52 ±0.19 55.93 ±0.05 55.92 ±0.29 56.60 ±0.31 56.30 ±0.08 56.35 ±0.20 57.20 ±0.11 64.42 ±0.21 64.67 ±0.11 64.56 ±0.04 64.45 ±0.13 64.52 ±0.07 64.96 ±0.10 (c) AAA on Split CIFAR-100 ER-ACE.

Random

MERS ProbCover

Buffer Supervised Supervised 200 400 600 1000 2000 4000 6000

26.65 ±0.04 28.01 ±0.07 29.02 ±0.12 31.03 ±0.15 34.01 ±0.16 37.83 ±0.13 40.15 ±0.24

SimCLR

MERS MaxHerding MERS

Supervised

SimCLR

MERS

28.49 ±0.11 27.57 ±0.06 28.24 ±0.09 28.16 ±0.19 28.19 ±0.05 28.31 ±0.12 30.93 ±0.23 29.82 ±0.13 30.79 ±0.15 30.06 ±0.02 30.28 ±0.12 30.49 ±0.12 32.01 ±0.09 31.05 ±0.16 32.21 ±0.14 31.76 ±0.18 31.45 ±0.09 31.66 ±0.08 33.92 ±0.13 32.97 ±0.07 34.43 ±0.16 33.52 ±0.14 33.15 ±0.16 33.11 ±0.12 36.25 ±0.22 35.97 ±0.17 36.96 ±0.10 36.65 ±0.11 36.11 ±0.18 36.11 ±0.19 39.51 ±0.11 39.78 ±0.21 40.28 ±0.12 39.37 ±0.13 38.70 ±0.10 39.05 ±0.11 42.05 ±0.26 41.66 ±0.15 42.57 ±0.15 41.37 ±0.14 40.76 ±0.24 41.43 ±0.04 (d) AAA on Split CIFAR-100 ER.

Random

MERS ProbCover

Buffer Supervised Supervised 200 400 600 1000 2000 4000 6000

21.09 ±0.10 20.94 ±0.07 21.16 ±0.10 21.91 ±0.15 25.57 ±0.14 33.03 ±0.11 39.88 ±0.15

SimCLR

MERS MaxHerding MERS

Supervised

SimCLR

MERS

21.06 ±0.04 21.03 ±0.02 21.00 ±0.09 21.12 ±0.13 21.22 ±0.02 21.16 ±0.12 21.48 ±0.11 21.06 ±0.04 21.59 ±0.06 21.56 ±0.05 21.34 ±0.05 21.33 ±0.09 22.15 ±0.09 21.59 ±0.09 21.91 ±0.11 22.17 ±0.10 21.75 ±0.08 21.78 ±0.06 23.30 ±0.05 22.91 ±0.15 23.64 ±0.12 23.30 ±0.10 22.82 ±0.09 22.83 ±0.08 27.72 ±0.14 26.72 ±0.10 27.64 ±0.09 27.25 ±0.15 26.46 ±0.16 27.03 ±0.10 35.37 ±0.30 34.41 ±0.18 36.29 ±0.15 35.24 ±0.17 34.08 ±0.08 34.45 ±0.23 41.56 ±0.17 41.02 ±0.17 41.70 ±0.14 40.87 ±0.24 39.76 ±0.18 40.65 ±0.07

24