Bilevel Coreset Selection in Continual Learning: A New Formulation and Algorithm
Authors: Jie Hao
Kaiyi Ji
Mingrui Liu
Venue: NeurIPS 2023 poster (2023)
Keywords: Coreset Selection
Continual Learning
Bilevel Optimization
TL;DR: This paper provides a new bilevel coreset selection formulation and optimization algorithm for continual learning.

Abstract: Coreset is a small set that provides a data summary for a large dataset, such that training solely on the small set achieves competitive performance compared with a large dataset. In rehearsal-based continual learning, the coreset is typically used in the memory replay buffer to stand for representative samples in previous tasks, and the coreset selection procedure is typically formulated as a bilevel problem. However, the typical bilevel formulation for coreset selection explicitly performs optimization over discrete decision variables with greedy search, which is computationally expensive. Several works consider other formulations to address this issue, but they ignore the nested nature of bilevel optimization problems and may not solve the bilevel coreset selection problem accurately. To address these issues, we propose a new bilevel formulation, where the inner problem tries to find a model which minimizes the expected training error sampled from a given probability distribution, and the outer problem aims to learn the probability distribution with approximately $K$ (coreset size) nonzero entries such that learned model in the inner problem minimizes the training error over the whole data. To ensure the learned probability has approximately $K$ nonzero entries, we introduce a novel regularizer based on the smoothed top-$K$ loss in the upper problem. We design a new optimization algorithm that provably converges to the $\epsilon$-stationary point with $O(1/\epsilon^4)$ computational complexity. We conduct extensive experiments in various settings in continual learning, including balanced data, imbalanced data, and label noise, to show that our proposed formulation and new algorithm significantly outperform competitive baselines. From bilevel optimization point of view, our algorithm significantly improves the vanilla greedy coreset selection method in terms of running time on continual learning benchmark datasets. The code is available at https://github.com/MingruiLiu-ML-Lab/Bilevel-Coreset-Selection-via-Regularization.

Bilevel Coreset Selection in Continual Learning: A New Formulation and Algorithm
Jie Hao Department of Computer Science George Mason University jhao60gmu.edu
Kaiyi Department of CSE University at Buffalo kaiyi falyiji@buffee falo edu
Mingrui Liu"
Department of Computer Science George Mason University mingrui1@gmu. edu
Abstract
Coreset is small set that provides a data summary for large dataset, such that training solely on the small set achieves competitive performance compared with a large dataset. In rehearsal-based continual learning, the coreset is typically used the memory replay buffer stand for representative samples in previ- ous tasks, and the coreset selection procedure is typically formulated as bilevel problem. However, the typical bilevel formulation for coreset selection explic- itly performs optimization over discrete decision variables with greedy search, which is computationally expensive. Several works consider other formulations to address this issue, but they ignore the nested nature of bilevel optimization problems and may not solve the bilevel coreset selection problem accurately. To address these issues, propose new bilevel formulation, where the inner prob- lem tries to find a model which minimizes the expected training error sampled from given probability distribution, and the outer problem aims to learn the probability distribution with approximately K (coreset size) nonzero entries such that learned model in the inner problem minimizes the training error over the whole data. To ensure the learned probability has approximately K nonzero en- tries, introduce novel regularizer based on the smoothed top-K' loss in the upper problem. We design a new optimization algorithm that provably converges the e-stationary point with ((1/e4) computational complexity. We conduct extensive experiments in various settings in continual learning, including balanced data, imbalanced data, and label noise, show that our proposed formulation and new algorithm significantly outperform competitive baselines. From bilevel optimization point of view, our algorithm significantly improves the vanilla greedy coreset selection method in terms of running time on continual learning benchmark datasets. The code is available httpss//ggtabb....///gguuuuu
Lab/
via www.lReeeutuitoo.o.o
Introduction
Deep Neural Networks (DNNs) have achieved tremendous successes in various domains, includ-
ing computer vision 41 30, natural language processing 772 [5], generative modeling [26 and
"Corresponding Author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

LO
TTask
Mer
(0 w)
B2
Task
①
Butfer
(0cr)
Task T
6
Figure 1: Illustration of our algorithm. There two neural network models, one is Mr for model training, and the other is Mes for coreset selection. A coreset is selected from the current data stream B, by conducting six steps. I Feed stream mini-batch B, and sampled buffer data to M ② Copy model parameters from Mer to Mcs: 6.r + P2r 3 Feed a mini-batch B, into model Mes. 4 Conduct bilevel optimization to update the model parameter 8ex in Mes and output a probability distribution w. ) Sample a coreset from B, based on the distribution of w and add the sampled data into buffer. ④ Calculate stochastic gradient based on B, and sampled data the buffer Step 1, and update Our based on gradient information. Repeat the above steps for each stream mini-batch.
However, in continual learning, where DNNs are trained on a sequence of tasks with possibly non-i.i.d. data, the performance will be degraded on the previously trained tasks. This is referred to as catastrophic forgetting [53 60 To alleviate catastrophic forgetting, one of the effective ways is rehearsal-bure -based continual learning, where a small replay buffer is maintained and revisited during the continuous learning process. There is line of works studying how efficiently maintain the replay buffer using the coreset selection approach 66 78 83). in which small set of data is selected as representative samples to be used in continual learning.
games 688.
The coreset selection in continual learning is formulated as a perdinality-constriine bilevel opti- mization problem which is solved by incremental subset selection [6]. This greedy approach is computationally expensive and hence is not scalable when the coreset size is large. To address this issue, Zhou al. [83] propose a relaxation of the bilevel formulation in [6), which drops the nested nature of bilevel formulation and actually becomes two sequential optimization problems. Tiwari et al. al.proposed a gradient approximation method in [71], which selects a coreset that approximates the gradient of model parameters over the entirety of the data seen so far. Yoon et al. (78) proposes an online coreset selection method by maximizing several similarity metrics based on data pairs within each minibatch, and sample pairs between each minibatch and coreset. These approaches do not directly address the algorithmic challenges caused by the nested nature of the bilevel optimization problem, and may not solve the original bilevel coreset selection problem efficiently.
The key challenges in the bilevel coreset selection problems are two folds. First, the bilevel formula- tion in [6] needs to directly perform optimization over cardinality constraint, which is a nonconvex set and greedy approaches are expensive when the coreset size is large. Second, the bilevel formulation in [6] has a nested structure: one problem is embedded within another, and the outer and inner functions both have dependencies over the same set of decision variables. remains unclear how to design efficient algorithms to solve constrained bilevel optimization algorithms for the coreset selection problem with provable theoretical guarantees.
Our proposed solution addresses these challenges with a novel bilevel formulation and provably efficient optimization algorithms. The proposed new bilevel formulation is referred as Bilevel Coreset Selection via Regularization (BCSR). The main differences between our approach and the standard bilevel approach in 66) are: (i) unlike the standard bilevel formulation which requires performing optimization based on a cardinality constraint, we propose to solve bilevel optimization on probability simplex over training examples: (ii) to make sure the probability distribution lies in a low dimensional manifold, we propose to add a smoothed top- loss as a regularizer to the upper-level problem; (iii) due to our new formulation, we are able to design simple and effective first-order method to solve this new bilevel problem with provable non-asymptotic convergence guarantees. The first-order method is easy to implement and much faster than the greedy approach as in [6]. Our main contribution is listed as follows.

---

Algorithm PyTorch-style pseudocode for BCSR
tasks: the task sequences; т: the number of tasks
L(): loss function;
image batch, y: label batch model, model_proxy: for training and coreset selection
4 update_w: a function updating outer variable
5 M [Q] T] # memory buffer
for ind, task in tasks:
for (x, y) in dataloader:
model_proxy. -oroxx.lodd_statee dict (model parameters ())
9
(x_m, y_m) next bext_batch(( (M)
out1 model
out2 model model(x_m)
loss (outl, y)+ L (out2, y_m)
loss backward
14
M[ind] append find_coreset (x, y, K, model_proxy) update (model. smodee params)
(x_core, y_core)
y_core))
def find_ccreset y, K, model_proxy)
coreset_w 1.0/y.size()
for in range (outer_loops)
for i in range (inner_ (inner_loops):
lover_loss lover_ backward update coreset_w update_ return torch multinomial (coreset_ K)
(coreset_w model (x, y)
22
23
24
We propose new bilevel formulation, namely BCSR, for the coreset selection in rehearsal- based continual learning. Instead of directly learning the binary masks for each sample, the new formulation tries learn a probability distribution a smoothed top-K loss regularizer in the upper problem. This formulation is designed to satisfy two important features continual learning with DNNs: (i) keeping the nested structure in the coreset selection; (ii) being amenable to first-order algorithms, which makes it easy to implement in modern deep learning frameworks such as PyTorch and TensorFlow. Based on the new formulation, we propose an efficient first-order algorithm for solving it. The main workflow of our algorithm is illustrated in Figure [ and the corresponding Pytorch-style pseudocode is presented in Algorithm[]
low-dimensional manifold by adding
We have conducted extensive experiments among various scenarios to verify the effectiveness of proposed algorithm, including balanced, imbalanced, and label-noise data. Our algorithm outperforms all baselines for all settings in terms of average accuracy, and it is much better than all other coreset selection algorithms. For example, on imbalanced data of Multiple Datasets, BCSR is better than the best coreset selection algorithm by 4.65% in average accuracy. From bilevel optimization point of view, our algorithm significantly improves the vanilla greedy coreset selection method [6] in terms of running time on continual learning benchmark datasets.
Under the standard smoothness assumptions of the loss function, we show that our algorithm requires most ((1/A)) complexity for finding c-stationary point in the constrained case") Notably, the ((1/ct) complexity consists of (1//²) backpropagations and (11cc*) samplings from Gaussian distribution, where the latter cost is computationally cheap.
2 Related Work
Continual Learning There are different classes of continual learning methods, including
regularization-bsse approaches [39
81
10
59 64 17]. dynamic architecture methods [61
"In the constrained setting, the definition of e-stationary point is defined with gradient mapping, i.c., is c-stationary point of the function if -/ll Pa (V)(w)) c. where 3 the stepsize, P is the projection operator, A is the probability simplex. This matches the best iteration complexity as in the single level optimization problem [24).

---

79 62 51 76 44 77.. and rehearsal- -asee methods 48 57 II, 58 31
18
28 80
83
78
84
In the rehearsal- -base continual learning, the memory is either reproduced experience replay 48 or generative replay [67]. Our work focuses on the aspect of the coreset selection on the replay memory and can be flexibly integrated into rehearsal-basee methods in continual learning.
Coreset Selection The coreset selection methods were used frequently in supervised and unsu- pervised learning, such as k-means [1]], Gaussian mixture model [49], logistic regression [33 and bayesian inference [2] They were also used frequently in the active learning literature [74 63 The
coreset selection continual learning related to the sample selection R4 2 3. Nguyen et al. 555
introduce variational continual learning which is combined with coresct summarization
[5]. Borsos
et al. [6] proposed the first bilevel formulation for the coresct selection in continual learning, which is later improved by [83 78). Compared with these works, our work focuses improved bilevel coreset selection: we provide a better bilevel formulation than (6] and design a provably efficient
optimization algorithm.
Bilevel optimization Bilevel optimization is used to model nested structure in the decision decision-making
process 773.. Recently, gradient-based bilevel optimization methods have broad applications in
machine learning, including meta-learning (20] hyperparameter optimization [56] 22 neural archi-
tecture search (46), and reinforcement learning 40 32
These methods can be generally categorized
into implicit differentiation [16] [66 45 and iterative differentiation [50] [1 20
[5]
27] based
approaches. Recently, various stochastic bilevel algorithms have been also proposed and analyzed
by [12 25 32 29 [1). A comprehensive introduction can be found in the survey [47]. In this
work, we propose novel stochastic bilevel optimizer with very flexible parameter selection, which shows great promise in the coreset selection for continual learning.
3 New Bilevel Formulation for Coreset Selection in Continual Learning
In this section, we first introduce our new bilevel formulation, namely Bilevel Coreset Selection via Regularization (BCSR). The key idea of this approach is to learn a probability distribution over the whole dataset such that the best model parameter obtained by minimizing the loss on the sampled dataset (i.e., the minimizer for the lower-level problem) is also the best for the whole dataset (i.e., the minimizer for the upper-level problem), and then a coreset can be sampled based on the learned probability distribution. In addition, the learned probability distribution is expected to lie in a low dimensional manifold (i.e., with K nonzero entries where K is the coreset size). To achieve this, we added smooth K loss regularizer to promote the probability distribution to have K nonzero entries. Specifically, the objective function of BCSR is:
K
min ((w) = 4(00 (w)) 0SW ||
E (w + 62)
s.l., (w) arg argmin [(0,w)
Σ w ww 6()
(I)
where n is the sample size, 0 is the model parameter, is the sample weights, (0) denote the loss function calculated based on i-th sample with model parameter 0, 10(s) is the i-th coordinate of w. way is the i-th largest component of w, X > O is the regularization parameter, on each coordinate of where z ~ (O, 1). Note that R(w, 6) == - -x Σ E, (w + +2)] denote the smoothed top-K K regularization. We add this regularization to make sure the summation of the top-K entries of the learned probability vector is large, such that we can confidently choose a coreset with size K. The goal of employing Gaussian noise to the regularizer is for the ease of algorithm design: this Gaussian smoothing technique can make the regularizer to smooth such that it easier to design efficient first-order bilevel optimization solvers. Otherwise, the upper-level problem would become nonconvex and nonsmooth, and it would be difficult for algorithm design under this case.
82 denote to adding ò2
Discussion and Comparison with Prior Works In this part, we illustrate how this new formulation addresses the drawbacks of the previous approaches. The work of (6) does not use any regularizer and regards the weight of each sample as binary mask. This formulation needs to solve combinatorial
4

---

Algorithm 2 Bilevel Coreset Selection via Regularization (BCSR)
Input: Dataset D Initialize: model parameter 0g. memory M = =
1: for batch B; ~ D do
2: Compute coreset S; Find-coreset(l--1.. B,)
3:
4:
end for
Algorithm 3 Find-coreset(f,...
Input: the current model parameter 8, the current batch B, the iteration parameters J.N, Q Initialize: coreset size K, = [8), and
I: wh ..... a1 (uniform probability initialization)
2: 89 =
3: for j = =0,2 0.
do
4: Set initialization 09 0-- if 0 and 09 otherwise
5: for k= 1...., N do
....,,N. 6: update 03 according eq.
7: end for
8: Set initialization of リリ if > 0 and un otherwise
9:
Compute estimate U by solving QP in
(4) by GD with stepsize y and inital oy 0f j-1
10: Compute hypergradient estimate in
11: Update wj+1 and project it onto simplex by
12: end for
13: S
set of K data points sampled from B according to the probability distribution wy Return S
14:
optimization problem and their approach of incremental subset selection is computationally expensive. The work of [83] relaxes the bilevel formulation in [6] minimize the expected loss function over the Bernoulli distribution s, i.e. min.ec (ss, and develops a policy gradient solver to optimize the Bernoulli variable. Their gradient V (s) Fyp(ml)) e) T.
((0)))))) (m)) In p(m(s) (s) does not include the implicit gradient of L(0" (m)) in terms of However, 0* (m) actually depends on the mask m, and m depends on the Bernoulli variable s. In contrast, our bilevel optimization computes the hypergradients for the coreset weights (0
). which considers the dependence between [83] assume that the inner loop can obtain the exact minimizer 8" (m), which may not hold in practice. In contrast, carefully analyze the gap between the estimated 6* (w) and itself by our algorithm and analysis.
and |L]]|
((w) and w 3
addition, Zhou et al.
Algorithm Design
which calls Algorithm aas a subroutine. Each time the algorithm encounters a minibatch B, a coreset is selected within this minibatch by invoking Algorithm 3 Algorithm 3 is first-order algorithm for solving the bilevel formulation (I). In Algorithm 3, the model parameter and the weight distribution are updated alternatively. We first perform N steps of gradient descent steps find a sufficiently good for the lower-level problem (lines 5-7) by the update rule:
Equipped with the new formulation, the entire algorithm is presented in Algorithm 2
0 - -a----veLL(e aV wy).
(2)
where 0f: denotes the model parameters the j-th outer loop and the k-th inner loop. To update the outer variable w. BCSR approximates the true gradient Vo(w) of the outer function w.nt w, which is called hypergradient [56]. BCSR constructs hypergradient estimator:
V. R (V w))) Vol, (ON)))
Σ EEB
R.,
(3)
B
Thh coreset weight in formulation is equivalent sample mask in
5

---

Table 1: Experiment results Split CIFAR-100
Balanced
Imbalanced
Label Noise
Methods
FGTr
FGIr
Ap
FGTT
K K-means Features
57.82+0.69
0,070=0.003
45.4440.76
0.037+0.002
57.38+ .26
0.098+0.003
K-means Embedding
59.77=0.24
0.001+0.001
43.91+0.15
0.044+0.001
57.92+
0.091+0.016
Uniform
58.99:0.54
0,074=0.004
44.73=0.11
0.033+0.007
58.76+1.07
0.087+0.006
iCaRL
60.74:0.09
0.044:0.026
44.25a2.04
0.042s0.019
59.70=0.70
0.071+0.010
Grad Matching
59.1740.38
0,06720 003
45.4420.64
0.03840.000 001
59,5841.25
0.073+0.008
SPR
59.56+0.73
0.143+0.000 064
44.45=0.55
0.086+0.023
58,74+0.63
0.073+0.010
MetaSP
60.1440.25
0,056.0 230
43.7420.36
0.079 014
57.43=0.54
0.06440.077
Greedy Coresct
19.39+0.16
0.066+000117 017
43,80+0.01
0.039+0.000 007
58.22+0.16
0.066++00001
GCR
58.73+0.43
0.073+0.013
44.48+0.05
0.03540. 005
58.72+0.63
0.081 +0 +0.005
PBCS
55.6442.26 26
0.062=0.001
39.87=1.12
0.076x0.011
56,9340.14
0.10040.003
OCS
52.5720.37
0.08810.001
46.5420.34
0.022+0.005
51.7720.81
0.10344.007
BCSR
61.601:0.14
0.051
47.30+0.57
0.022+0.005
60.70:0.08
0.059
where R(w, 0; == -x (w++3) (w++ and
~~ Solving the Hessian-invers--vccton prod-
uct in eq. 3 is computationally intractable. We denote e" := (V wwy)) - Vol,
in eq. (3) where v" can be approximated by solving the following quadratic programming problem
efficiently by Q steps of gradient descent (line 9):
1 v" ViL(ON wyyv x (ol. min 2
(4)
Next, the hypergradient estimate (line 10) is computed based the output of approximated quadratic programming. Note both model parameters and sample weights need to use warm start initialization (line 4 and line 8). Then the weight is updated and projected onto simplex (line 1 1):
w 1 w2 Bup Wj+1 PA (w)++))
where A : {w ER" 0 (()) 1, ||m|| = 1}. In terms of other experimental hyperparameters, we allow very flexible choices of hyperparameters (e.g., N, Q) as shown in our theory to achieve polynomial time complexity for finding a e-stationary point.
The selected coresets for each task are stored a memory buffer with a fixed size m. There is a separated memory slot for each task with size [m/i] when the task i comes. After each task the memory slots before will randomly remove some samples to adjust all the memory slots to /m/i]. That means the memory size for each task decreases the task ID increase to maintain the total buffer size m unchanged. The same memory strategy is also used in the greedy coreset approach [6]
Experiments
We conduct extensive experiments under various settings, including balanced data, imbalanced data, and label-noise data. The empirical results demonstrate the effectiveness of our method in rehearsal- -basad continual learning.
5.1 Experimental Setup
Datasets We use commonly-used datasets in the field of continual learning, including Split CIFAR- 100, Permuted MNIST, Multiple Datasets, Tiny-ImageNet, and Split Food-101. We follow the experimental settings as that in prior work (78) and [83] Each dataset is processed with three approaches: balanced, imbalanced, and label-noise. Please refer to Appendix L for more details about data processing and settings.
Baselines We compare our algorithm BCSR with other continual learning methods based on coreset strategy, including k-means features [55] k-means embedding 663 Uniform Sampling, iCaRL. [57], GCR 771,, and OCS (78. We also compare with
Grad Matching [9] Greedy Coreset 66) PBCS
83
non-coreset reply method, SPR (38, MetaSP 70 All algorithms are built upon episodic memory,
which stores coreset selected from stream data. Then a model, such as ResNet-18 (30), is trained
over the data from the current stream and the episodic memory.
Metrics Average accuracy and forgetting measure [10] are two primary evaluation metries that
used in continual learning literature. AVG ACC (Ar) is the average accuracy tested on all tasks
after finishing the task T: Ar ET= @T where ar, is the test accuracy of task after training

---

Table 2: Experiment results Multiple Datasets
Balanced
Imbullncedd
Label Noise
Methods
Ar
FGTr
FGIr
Ap
FGTT
K K-means Features
54.61=0.88
0.138+0.007
33.6142.66
0.1 0,136+40.63
45,46+33.5
20+200000
K-means Embedding
56.81+1.65
0.106++0.019
35.93+1
0.106+0.031
46 46.32+3.19
0.084+0.030
Uniform
55.97=0.03
0.101=0.012
35.48+2.96
0.104+0.025
48.68:4..4
0.079+0.002
iCaRL
56.19;0.32
0.130s:0.12
42.18a1.59
0.057a60.022
49.2240.54
0.06710.010
Grad Matching
53.41:0.46
0.1 0.119920.02
38. 16.33.9990
0.082400.00 003
46.9621.05
0.091+0.022
SPR
56.20+1.91
0.12
40.79:1.73
0,14340.051
49.77+1.58
0.062+0.024
MetaSP
51.14=1.10
0,11 042
41.32+1.50
0.103 055
47.1441.66
0.081+0.02
Greedy Coresct
53.56+0.06
0.099+0.000 005
22.57=1.110
0.265+0.022
41.32+1.51
0.137 009
GCR
54.35+0.31
0.125+0.014
35.13+2.79
0. 043
47.58+1.30
0.078+0.016
PBCS
52.93:0.28
0.152#0.016
37.25a2.93
0.115+0.035
47.51=1.56
00.01
OCS
55.65a2.26
0.062:0.001
40.48:1.39
0.051+00000
45.03+4.16
0049:00001
BCSR
59.8920.95
0.09620.005
45.13+0.54
0,04610.008
49.97=1.14
0.064x0.031
Table 3: Experiment results on Tiny-ImageNer
Balanced
Inbalanced
Label Noise
Methods
FGT
AVG ACC
FGT
ACC
K-means Features
41.20=0.75 75
0.131 004
36.27=0.30
0,079=0.01
36 10.68.133
0.095#0.000
K-means Fibeedding
41.48+1.21
0.129+0.007
36.29+0.23
0.085+0.003
1..01+1.51
0.083+0.000
Uniform
11:022
0222
37.07=0.53
0.083400.00
37.14=1.05
0.099x0.000
iCaRL
43.8420.09
0.114200004
37.6520.84
0.058a0.008
38.5240.25
0.06310.006
Grad Matching
43.45::0332
0. 0.105=0.000 007
37.58=0.39
0.066 004
38.84:2044
0.064
SPR
42.79x0.50
0.102:00.099
36.55a0.74 74
0.070a0.000
39.89a0.53
0.065a0.021
MetaSP
43.33=0.32
0, 0,127 002
36.75=0.57
0.086 006
37, 37.1811.76
0.068+0.00 007
Greedy Coresct
41.0240.33
0.1 19=0.017
33.43=0.86
0,10340.000
36.37:0.16
0.079+0.000
GCR
41.45+0.35
0.125+0.008
36.08+0.62
0.072+0.017
37.46+40440
0.115
PBCS
36.99+0.115
0.177+0.002
35,88+0.16 16
0.071+00080
37.02:0.116
0.133+0.029 0.09
OCS
41.29:0.09
0.1 12+0000.0
35.09+0.60
0.036:200111
35. 15.3640.94
0.061 +0.005
BCSR
44.1340.33
0.10640.001
38.5910.11
0.070&0.004
40.72:0.56
0.05510.006
the task T. FGTr evaluates the performance drop on the past tasks after training on the task T:
FGT, = + E [maxxee,...TTI1 (az,e ; ar,,)]-
Implementation Details Following the implementation of the coreset- based algorithm o we use two models for the purposes of model training and coreset selection respectively, where the first model is denoted as M, for model training, and the second model (also known as a proxy model) is denoted as Mes for coreset selection. In the section of the model training. we adopt single-head MLP with two hidden layers for Permuted MNIST, and a ResNet- 18 for Split CIFAR- 100 and other datasets. In the section of the coreset selection, Mcs adopts the same architecture as M This is aeeeeteeeeeeeie
the key difference between our work and the Greedy Coreset [6]: they use Neural Tangent Kernels (NTK) (35) while use a specific deep neural network. Note that NTK performs learning based on fixed features, which is shown to be limited [66]. In contrast, our algorithm allows hicrarchical feature learning during the training process. In addition, our algorithm does not rely discrete decision variables as in 6 we use first-order methods with gradient and product information with convergence guarantee and hence is more efficient in practice. For non- coreset reply methods SPR and MetaSP, we set the size of the method buffer as that in coreset-based methods. Especially for SPR, there are memory buffers: the delayed buffer D temporarily stocks the incoming data stream, and the purified buffer P maintains the cleansed data. To satisfy the
Table 4: Experiment results on Food-101
Balanced
Imbalanced
Label Noise
Methods
AVG ACC
FGT
AVG ACC
FGT
AVG ACC
PGT
K-means Features
46.3521.41
0.05720.003 004
33.3520.93
0.064410.00 008
34.88100.6 64
0.12740.011
K-means Embedding
49.47 4..4
0.040=0.000 004
34.07=0.89
0.057+0.014
35.54+0.57
0.141
Uniform
46.50+0.15
0.048+0.001
34.61+0.16
0.060+0.00 007
36.69+1.15
0.12340.000
iCaRL
12:4280.78
0.035+0.001
36.83+1.06
0.032+0.000
39.22:+.30
0.084+0.010
Grud Matching
49.13=0.44
0.026100.02
36.51+0.04
0.04340.00 003
38, 23.8640..3
0.086++00119
SPR
18.34:0.54
0.042+40.033
37.41=0.68
0.037+00.00 006
38.6340.33 34
0.06910.016
MetaS
48.8420.38
0.05340.000
38.4110.78
0.05340.011
38.7810.41
0.06340.013
Greedy Coresct
49.19 19.991
0.030 008
38.78:0.01
0.038+0.000
38.61=0.18
0.096+0.008
GCR
47.03a1.17
0.04840.0044
36.9910.30
0.04240.00 0US
35.78+ .08
0.12640.013
PBCS
47.98=0.42
0. 0.098:0.006
38.00:00.16
0.04640.000 001
37.77=0.40 40
0.123+0.013
OCS
46.80+
0.103+0.013
24.44+0.29
0.067+0.001
35.50+0.04
0.135+0.00
BCSR
51.30++0.2
0.03950.008
39.05=0.99
0.044+0.001
39.63+0.22
0.060=40077
7

---

AVG Ace
AVG AC0
ANG ACC
70
10 50
40
1011122314155611110 71819
(a) Permuted MNIST
(b) Imbalanced Permuted MNIST (c) Label-Noo Noise Permuted MNIST
Krnnom
Peat
The average accuracy during the continual learning. After each task, the training model is tested on encountered tasks. Due to the nature of forgetting, the average test performance of the methods tends to decrease.
Figure 2:
Table 5: Random initialization with (W) and without (WO) bilevel optimizers (BO)
Split CIFAR 100
Permuted MNIST
Multiple Datasets
BO
Ar
FGI,
Ar
FGTT,
PGTr
WO
58.37+0.37
0073=0.004
53 33.04
0.074=0.009 0.05%=0.002
35.50+0.80
0. 28200.2027 0.096:00.05
6166+0.14
0.051=0.015
56.2340.29
59,89:0.95
requirement of coreset experiments, we keep the size of P and D buffers the same. The detailed hyperparameter settings can be found in Appendix C
5.2 Results
We report the results of average accuracy (AVG ACC) and forgetting (FGT) for all the algorithms on the balanced, imbalanced. and label-noise benchmarks, and the results are presented in Table [ Table 2 T T and Table ( [B) respectively. We have the following observations. (i) In the balanced setting, our method outperforms other baselines significantly in terms of AVG ACC. For example, compared with the best coreset selection methods, our BCSR shows 2.21%, 4.24%. 2.68%, 2.11%, and 1.7% improvements in AVG ACC on five benchmarks, respectively. (ii) In the imbalanced and label-noise setting, our method also demonstrates relatively higher performance. For example, on imbalanced data of Multiple Datasets, BCSR is better than the best coreset selection algorithm by 4. 4.65% in average accuracy. An interesting observation that Greedy Coreset ( does not perform very well, especially in imbalanced and label-noise settings. The reason is that the inner optimization in Greedy Coreset is conducted by an NTK, where only a fixed feature is used but not the learned feature. (iii) From bilevel optimization point of view, our algorithm significantly reduces the running time of the vanilla greedy coreset selection method (6] by at least 58% on continual learning benchmark datasets. For detailed comparison, please check Table 3 in Appendix [ (iv) In addition, the test AVG ACC (Figure 2 and Figure 4 in Appendix FF) of the BCSR during the training process shows that algorithm alleviates catastrophic forgetting and it is comparable to other best baselines. For example, BCSR enjoys the lowest forgetting for almost all datasets under the label-noise setting (except for Multiple Datasets in Table 2. For most experiments other settings, BCSR achieves a forgetting performance that comparable to the best methods with at most 1% gap.
5.3 Ablation Studies
We conduct ablation studies to inspect the effectiveness of individual components in our proposed approach, including the effect of the bilevel optimizer, the smoothed top-K regularizer, and the coreset size K (Appendix D respectively.
Random initialization with and without bilevel optimizers. Our new bilevel optimization algorithm (Algorithm 3 of vital importance for finding a good distribution w for selecting the coreset. To demonstrate this, we design comparative experiments: one experiment initializes w randomly without updating it, and the other one adopts the same initialization strategy but updates w by the proposed bilevel optimizer. Then we sample coresets based on from two methods respectively. As you can see, the random initialization method equivalent Uniform Sampling. We report the experimental results of average accuracy and forgetting on three balanced datasets in Table It can be observed that the sampling strategy based on bilevel optimization significantly outperforms random sampling. In particular, the strategy with bilevel optimization shows 3. 3.23%. 2.89%, and 4.39% AVG ACC improvement on three benchmarks. Meanwhile, also obtains 2. 2.20%, 1.60%, and 20% FGT reduction on three benchmarks.
8

---

Table 6: The impact of different values of X
Split CIFAR-I00
Permuted MNIST Ap
Multiple Datasets
A
Ap
FGTT
PGTT
Ar
PGTT
0.00
60.43+0.15
0.064250.055
54.20=1.53
0.1
55.71=0.35
0,055+0.002
60.56+2.05
0.074+0.016
55.09=2.94
0.097+0.020
55,39+0.95
0.065+0.000
0.10
61.04e0.53
0.063+4.007
57.20=0.58
0.064a0.010
55.69:0.40
0.057+0.002
59.43a1.20
00S
35.43a1.53
0.108a0.019
58.1840.77
0.046210.000
5.00
58, 80te 1.58
0.084+0.017
53.13+2.74
0.120#0.021
56.67=0.78
0.051
59.53a0.42
0.075s0.012
53.54:2.02
0.118a0.029
55.57&1.05
0.06010.010
Upper toaa
Upper toss
3.5
BCSA
ECSA
Ornnet
Centue
1.0
Mpplly
0.5
11
13
17
(a) Split CIFAR-100
(b) Multiplc Datasets
Figure 3: The upper loss of bilevel optimization. Each distinct spike means the arrival of a new task.
To verify the effectiveness of our bilevel optimizer. we compare the loss curve with Greedy Coreset that uses NTK. The result is presented in Figure 3 There are number of stream mini-batches in each task. The bilevel optimizer trains over each bani-b where the upper loss is plotted in the figure. In the experiment, we plot the loss value for every 5 mini-batches. Within each task, the loss from BCSR gradually decreases with slight fluctuations, and increases only when encountering a new task. In contrast, the loss value of the Greedy Coreset approach always stays large. It indicates that our bilevel optimizer is more effective than the Greedy Coreset approach.
Effectiveness of the regularizer. In our algorithm, the bilevel formulation has a smooth top- loss regularizer in the objective function promote the probability distribution to have K nonzero entries. The goal is to make sure that the summation of top-K entries of the learned probability vector large, which increases confidence in the coreset selection. The hyperparameter is used to balance the cross-entropy loss and the regularization term. We explore the effects on the performance with different X, and list the results in T
This ablation experiment is performed on our framework BCSR, and average accuracy and forgetting on three balanced benchmarks reported. When À 0.10, BCSR reach the best performance (The highest AVG ACC and lowest FGT) on Split CIFAR- 100 and Permuted MNIST. While on Multiple Datasets, BCSR performs the best when and hence it is more challenging to select the appropriate representative samples. In this case, larger would emphasize more on maximizing the top- K probability and help select better representative samples. In addition, we observe that À set as a too large or too small value will damage the performance, which is in line with the observations in standard regularized empirical risk minimization problems such as overfitting and underfitting. Please refer to Appendix H for further analysis.
1.0. This dataset contains more categories,
6 Theoretical Analysis
In this section, we provide theoretical analysis for our proposed method. In particular, we establish convergence rate for our algorithm BCSR.
Theorem 1. Suppose standard assumptions hold in bilevel optimization (see Assumptions 7 and in Appendix M Choose parameters X, a, 1 and N such that (1 a)p (1+ 8rL2 where
[2 +LY= and Cq QoMM + +1 Q²2 pM + +nQ.. Furthermore, choose the stepsize 3 such
C2
that 32 2 < 1 and 3 < 1 where the constant w is given by Equation 16 in Appendix A ALo'

---

Then, we have the following convergence result.
1
1 Σ E G & 0 (B3 Da + Do BJ
+
[3] mpJ)
J
where G = (w; Pa (w, V ((w)))) denote the generalized projected gradient, Do:
<(wo) min ((w) 0, Do 10% 0% 2 + 1/ u.l Lo is the smoothness parameter of the
total objective <(w) whose form is proved in Appendix
Theorem provides a general convergence result for the proposed bilevel algorithm, which allows for very flexible selection of subloop lengths N and Q as long as the inequality (1 + A) ap)) (1
8rL2 S T/ holds given proper stepsizes X, 17, a. For example, in most of our experiments, the np
choice of N and = 3 works the best. Then, in this case, we further specify the parameters in Theorem D and provide the following corollary.
2 Corollary 1. Under the same setting as in Theorem ! choose N = 1,Q 3 and set X
iPa 1GU8I7 and a S +. Then, to make sure an e-accurate stationary point, i.e., J o B|G the number of iterations is D(E-)) each using [B] OcE²2) of samples from the standard Gaussian distribution NO, 1).
Corollary T shows that the proposed bilevel algorithm converges an c-accurate stationary point using only ( iterations and (c--)) samples drawn from WO., 1) per iteration. Note the the large batch size [B| (cc22) necessary here to guarantee convergence rate of (1/T),, which matches the results in solving single-level constrained nonconvex problems (24. In addition, it is computationally tractable because sampling from a known Gaussian distribution easy and cheap.
Conclusion
In this paper, we advance the state-of-the th-theeart art bilevel coreset selection in continual learning. We first introduce a new bilevel formulation with smoothed top-K regularization and then design efficient bilevel optimizer as a solver. We conduct extensive experiments in continual learning benchmark datasets to demonstrate the effectiveness of our proposed approach. We also show that the bilevel optimizer can efficiently find e-stationary point with O(1/e*) computational complexity, which matches the best complexity of projected SGD for single-level problem.
Acknowledgments and Disclosure of Funding
We would like to thank the anonymous reviewers for their helpful comments. Jie Hao and Mingrui Liu are both supported by grant from George Mason University. Computations were run on ARGO, research computing cluster provided by the Office of Research Computing at George Mason University (URL: https://oc..mu..edu)
References
[1] Rahaf Aljundi, Francesca Babiloni, Mohamed Elhoseiny, Mareus Rohrbach, and Tinne Tuyte- laars. Memory aware synapses: Learning what (not) to forget. In Proceedings of the European Conference on Computer Vision (ECCV), pages 139-154, 2018.
[2] Rahaf Aljundi, Eugene Belilovsky, Tinne Tuytelaars, Laurent Charlin, Massimo Caccia, Min Lin, and Lucas Page-Caccia. Online continual learning with maximal interfered retrieval. In Advances Neural Information Processing Systems 32, pages 11849-11860. 2019.
[3] Rahaf Aljundi, Min Lin, Baptiste Goujaud, and Yoshua Bengio. Gradient based sample selection for online continual learning. Advances in neural information processing systems, 32, 2019.
[4] Michael Arbel and Julien Mairal. Amortized implicit differentiation for stochastic bilevel optimization. In International Conference on Learning Representations, 2022.
10

---

[5] Olivier Bachem, Mario Lucic, and Andreas Krause. Coresets for nonparametric estimation-the case of dp-means. In International Conference on Machine Learning, pages 209-217. PMLR, 2015.
[6] Zalán Borsos, Mojmir Mutny, and Andreas Krause. Coresets via bilevel optimization for contin- ual learning and streaming. Advances in Neural Information Processing Systems, 33:14879- 14890, 2020.
[7] Lukas Bossard, Matthieu Guillaumin, and Luc Van Gool. Food-101 -miding discriminative components with random forests. In European Conference on Computer Vision, 2014.
[8] Yaroslav Bulatov. Notmnist dataset. Google (Books/OCR), Tech. Rep.[Online]. Available: http://yaroslavvb blogspot. it/201 1/09//otmmist-daaasssee hmml, 2, 2011.
[9] Trevor Camphell and Tamara Broderick. Automated scalable bayesian inference via hilbert coresets. The Journal of Machine Learning Research, 20(1):551-588, 2019.
[10] Arslan Chaudhry, Puneet K Dokania, Thalaiyasingam Ajanthan, and Philip HS Torr. Riemannian walk for incremental learning: Understanding forgetting and intransigence. In Proceedings of the European Conference on Computer Vision (ECCV), pages 532-547, 2018.
[11] Arslan Chaudhry, Marc' Aurelio Ranzato, Marcus Rohrbach, and Mohamed Elhoseiny. Efficient lifelong learning with a-gem. arXiv preprint arXiv: 2018.
[12] Tianyi Chen, Yuejiao Sun, and Wotao Yin. A single- tigee-li stochastic bilevel optimization method. arXiv preprint arXiv:2102.0467/ 2021.
[13] Yin Cui, Menglin Jia, Tsung- Yi Lin, Yang Song, and Serge Belongie. Class-balanced loss based on effective number of samples. In Proceedings of the IEEE/CVF conference computer vision and pattern recognition, pages
2019.
[14] Mathieu Dagréou, Pierre Ablin, Samuel Vaiter, and Thomas Moreau. framework for bilevel optimization that enables stochastic and global variance reduction algorithms. arXiv preprint 2:X1::2200.13409, 2022.
[15] Jacob Devlin, Ming-Woy Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv: 18 04805, 2018.
[16] Justin Domke. Generic methods for optimization-based modeling. In Artificial Intelligence and Statistics (AISTATS), pages 318-326, 2012.
[17] Sayna Ebrahimi, Mohamed Elhoseiny, Trevor Darrell, and Marcus Rohrbach. Uncertainty- guided continual learning with bayesian neural networks. arXiv preprint arXiv: 02425, 2019.
[18] Mehrdad Farajtabar, Navid Azizan, Alex Mott, and Ang Li. Orthogonal gradient descent for continual learning. arXiv preprint arXiv:1910007004, 2019.
[19] Dan Feldman and Michael Langberg. unified framework for approximating and clustering data. In Proceedings of the fhrty--ttttrdd annual ACM symposiun Theory of computing, pages 569-578, 2011.
[20] Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adap- tation of deep networks. In Proceedings of the 34th International Conference Machine Learning- Volume 70, pages 1126-1135. JMLR. org, 2017.
[21] Luca Franceschi, Michele Donini, Paolo Frasconi, and Massimiliano Pontil. Forward and reverse gradient-based hyperparameter optimization. In International Conference on Machine Learning (ICML), pages 1165-1173, 2017.
[22] Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riccardo Grazzi, and Massimiliano Pontil. Bilevel programming for hyperparameter optimization and meta-learning. In International Conference Machine Learning, pages 1568-1577. PMLR, 2018.

---

[23] Camille Garcin, Maximilien Servajean, Alexis Joly, and Joseph Salmon. Stochastic smooth- ing of the top-k calibrated hinge loss for deep imbalanced classification. arXiv preprint arXiv:2202.02 193, 2022.
[24] Saeed Ghadimi, Guanghui Lan, and Hongchao Zhang. Mini-batch stochastic approxima- tion methods for nonconvex stochastic composite optimization. Mathematical Programming. 1 155(1):267-305, 2016.
[25] Saced Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. arXiv preprint arXiv; 0w1.11022222222 2018.
(26] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural information processing systems, pages 2672-2680, 2014.
[27] Riccardo Grazzi, Luca Franceschi, Massimiliano Pontil, and Saverio Salzo. On the iteration complexity of hypergradient computation. In Proc. International Conference on Machine Learning (ICML), 2020.
[28] Yunhui Guo, Mingrui Liu, Tianbao Yang, and Tajana Rosing. Improved schemes for episodic memory-based lifelong learning. Advances in Neural Information Processing Systems, 33, 2020.
[29] Zhishuai Guo and Tianbao Yang. Randomized stochastic variance-reduced methods for stochas- tic bilevel optimization. arXiv preprint arXiv:2105.02266. 2021.
[30] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[31] Xu He and Herbert Jaeger. Overcoming catastrophic interference using conceptor-aided back- propagation. 2018
[32] Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A two-timescale framework for bilevel optimization: Complexity analysis and application to actor-critic. arXiv preprint arXiv:2007.05/70, 2020.
[33] Jonathan Huggins, Trevor Campbell, and Tamara Broderick. Coresets for scalable bayesian logistic regression. Advances in Neural Information Processing Systems, 29, 2016.
[34] David Isele and Akansel Cosgun. Selective experience replay for lifelong learning. In Proceed- ings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
[35] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
[36] Kaiyi Ji, Mingrui Liu, Yinghin Liang, and Lei Ying. Will bilevel optimizers benefit from loops. arXiv preprint arXiv:2205. 14224, 2022.
[37] Kaiyi Ji, Junjie Yang, and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced design. In International Conference on Machine Learning (ICML), pages 4882-4892. PMLR, 2021.
[38] Chris Dongjoo Kim, Jinseo Jeong, Sangwoo Moon, and Gunhee Kim. Continual learning on noisy data streams via self-purified replay. Proceedings of the IEEE/CVE international conference computer vision, pages 537-547 2021.
[39] James Kirkpatrick. Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei A Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Geabska-Barrinnsee et al. Overcoming catastrophic forgetting in neural networks. Proceedings of the national academy of sciences, 1 114(13):5511-352,, 2017.
[40] Vijay Konda and John Tsitsiklis. Actor-critic algorithms. Advances in neural information processing systems, 12, 1999.
12

---

[41] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. In Advances in neural information processing systems, pages 1097-1105, 2012.
[42] Ya Le and Xuan Yang, Tiny imagenet visual recognition challenge. CS 231N, 7(7):3, 2015.
[43] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 ():22)) 1):2278-2324, 1998.
[44] Xilai Li, Yingbo Zhou, Tianfu Wu, Richard Socher, and Caiming Xiong. Learn to grow: A continual structure learning framework for overcoming catastrophic forgetting. In International Conference on Machine Learning, pages 3925-3934. PMLR, 2019.
[45] Renjie Liao, Yuwen Xiong, Ethan Fetaya, Lisa Zhang, KiJung Yoon, Xaq Pitkow, Raquel Urtasun, and Richard Zemel. Reviving and improving recurrent back-propagation. Proc. International Conference on Machine Learning (ICML), 2018.
[46] Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search. ICLR, 2019.
[47] Risheng Liu, Jiaxin Gao, Jin Zhang, Deyu Meng, and Zhouchen Lin. Investigating bi-level optimization for learning and vision from unified perspective: A survey and beyond. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021.
[48] David Lopez-Paz et al. Gradient episodic memory for continual learning. In Advances in Neural Information Processing Systems, pages 6467-6476, 2017.
[49] Mario Lucic, Matthew Faulkner, Andreas Krause, and Dan Feldman. Training gaussian mixture models at scale via corescts. The Journal of Machine Learning Research, 18(1):5885-5909 2017.
[50] Dougal Maclaurin, David Duvenaud, and Ryan Adams. Gradient-based hyperparameter opti- mization through reversible learning. In International Conference on Machine Learning (ICML), pages 2112-2122, 2015.
[51] Arun Mallya and Svetlana Lazebnik. Packnet: Adding multiple tasks to single network by iterative pruning. In Proceedings of the IEEE conference on Computer Vision and Pattern Recognition, pages 7765-7773, 2018.
[52] James L McClelland, Bruce L McNaughton, and Randall C O'Reellly. Why there are comple- mentary learning systems in the hippocampus and neocortex: insights from the successes and failures of connectionist models of learning and memory. Psychological review, 102(3):419, 1995.
[53] Michael McCloskey and Neal J Cohen. Catastrophic interference in connectionist networks: The sequential learning problem. In Psychology of learning and motivation, volume 24, pages 109-165. Elsevier, 1989.
[54] Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. Reading digits in natural images with unsupervised feature learning. 2011.
[55] Cuong V Nguyen, Yingzhen Li, Thang D Bui, and Richard E Turner. Variational continual learning, arXiv preprint arXiv:1710.1000 2017.
[56] Fabian Pedregosa. Hyperparameter optimization with approximate gradient. In International conference on machine learning, pages 737-746. PMLR, 2016.
[57] Sylvestre-Alvise Rebuffi, Alexander Kolesnikov, Georg Sperl. and Christoph H Lampert. icarl: Incremental classifier and representation learning. In Proceedings of the IEEE conference on Computer Vision and Pattern Recognition, pages 2001-2010, 2017.
[58] Matthw Riemer, Ignacio Cases, Robert Ajemian, Miao Liu, Irina Rish, Yuhai Tu, and Ger- ald Tesauro. Learning to learn without forgetting by maximizing transfer and minimizing interference. arXiv preprint arXiv:1810.11910 2018.
13

---

[59] Hippolyt Ritter, Aleksandar Botev, and David Barber. Online structured laplace approximations for overcoming catastrophic forgetting. Advances in Neural Information Processing Systems, pages 3738-3748, 2018. 8.
[60] Anthony Robins. Catastrophic forgetting, rehearsal and pseudorchearsal. Connection Science, 122)1123,, 1995.
[61] Andrei A Rusu, Neil C Rabinowitz, Guillaume Desjardins, Hubert Soyer, James Kirkpatrick, Koray Kavukcuoglu, Razvan Pascanu, and Raia Hadsell. Progressive neural networks. arXiv preprint 1rXiv:1606.0467777 2016
[62] Jonathan Schwarz, Wojeiech Czarnecki. Jelena Luketina, Agnieszka Trabbka-Barwinskee Yee Whye Tch, Razvan Pascanu, and Raia Hadsell. Progress & compress: A scalable framework for continual learning. In International Conference on Machine Learning. pages 4528 4537. PMLR, 2018.
[63] Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set approach. arXiv preprint
2017.
[64] Joan Serra, Didac Suris, Marius Miron, and Alexandros Karatzoglou. Overcoming catastrophic forgetting with hard attention to the task. International Conference on Machine Learning, pages 4548-4557 PMLR, 2018.
[65] Amirreza Shaban, Ching-An Cheng, Nathan Hatch, and Byron Boots. Truncated back- propagation for bilevel optimization. In International Conference on Artificial Intelligence and Staristics (AISTATS), pages 1722-1732, 2019.
[66] Zhenmei Shi, Junyi Wei, and Yingyu Liang. A theoretical analysis on feature learning in neural networks: Emergence from inputs and advantage over fixed features. arXiv preprint drXiv:2206.01717,
2022.
[67] Hanul Shin, Jung Kwon Lee, Jaehong Kim, and Jiwon Kim. Continual learning with deep generative replay. Advances in neural information processing systems, 30, 2017.
[68] David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driess- che, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484, 2016.
[69] Johannes Stallkamp, Mare Schlipsing, Jan Salmen, and Christian Igel. The german traffic sign recognition benchmark: multi-class classification competition. In The 201 international joint conference on neural networks, pages 1453- 1460. IEEE, 2011.
[70] Qing Sun, Fan Lyu, Fanhua Shang, Wei Feng, and Liang Wan. Exploring example influence in continual learning. Advances in Neural Information Processing Systems, 35:27075-27086. 2022.
[71] Rishabh Tiwari, Krishnateja Killamsetty, Rishabh Iyer, and Pradeep Shenoy. Ger: Gradient coreset based replay buffer selection for continual learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 99-108, 2022.
[72] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
[73] Luis N Vicente and Paul H Calamai. Bilevel and multilevel programming: A bibliography review. Journal of Global optimization, 563):291-306, 1994.
[74] Kai Wei, Rishabh Iyer, and Jeff Bilmes. Submodularity in data subset selection and active learning. In International conference on machine learning, pages 1954-1963. PMLR, 2015.
[75] Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms. arXiv preprint 1rXiv:1008.07747, 2017.
14

---

[76] Ju Xu and Zhanxing Zhu. Reinforced continual learning. Advances in Neural Information Processing Systems, 31, 2018.
[77] Jaehong Yoon, Sachoon Kim, Eunho Yang, and Sung Ju Hwang. Scalable and order-robust con- tinual learning with additive parameter decomposition. International Conference on Learning Representations, 2020.
[78] Jaehong Yoon, Divyam Madaan, Eunho Yang, and Sung Ju Hwang. Online coreset selection for rehearsal-based continual learning. arXiv preprint arXiv:2 10w.0.000....... 2021.
[79] Jachong Yoon, Eunho Yang, Jeongtae Lee, and Sung Ju Hwang. Lifelong learning with dynamically expandable networks. arXiv preprint arXiv: 01547, 2017.
[80] Tianhe Yu, Saurabh Kumar, Abhishek Gupta, Sergey Levine, Karol Hausman, and Chelsea Finn. Gradient surgery for multi-task learning. Advances in Neural Information Processing Systems, 33:5824-5835 2020.
[81] Friedemann Zenke, Ben Poole, and Surya Ganguli. Continual learning through synaptic intelligence. In Proceedings of the 34th International Conference on Machine Learning-Von Volume 70, pages 3987-3995, JMLR. org, 2017.
[82] Guodong Zhang, James Martens, and Roger Grosse. Fast convergence of natural gradient descent for over-parameterized neural networks. Advances in Neural Information Processing Systems (NeurIPS), 32, 2019.
[83] Xiao Zhou, Renjie Pi, Weizhong Zhang, Yong Lin, Zonghao Chen, and Tong Zhang. Proba- bilistic bilevel coreset selection. In Kamalika Chaudhuri. Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Confer- ence on Machine Leurning, volume 162 of Proceedings of Machine Learning Research, pages 27287-27302. PMLR, 17-23 Jul 2022.
[84] Xiangyu Zhu, Jie Hao, Yunhui Guo, and Mingrui Liu. Auc maximization in imbalanced lifelong learning. In Uncertainty in Artificial Intelligence, pages 2574-2555555 258-2585. PMLR, 2023.
15

---

A Proof of Theorem 1
Let A(") := {w S w(t S 1, | = 1} denote the constraint set of the upper-level problem
We first provide some important inequalities.
Recall that v be the 9th GD iterate in solving the linear system ViL(ON, w,)0= Ei=1 Ver(o)) at iteration j via the following process:
vgth = (I (I , + n
(6)
which, by telescoping Equation
6 over from 0 to Q 1, yields
Q-1
of = - -1- Rf +
Σ (1 - ( w.y))
V
Let o3 be the solution of the linear system VOL wy)x Ei= V((03), and then we have
2-1
-I- w/ 03 + n Σ VoLL0, 1, Vl(()))
(8)
9=0
Combining Equation 6 and Equation 7 noting that of = -ff and using Assumption that
||,ā|| & [1(V)1(03, wyy |||| Σ i=1 Ve,(6)) S M the difference between ug and uiz can be
bounded as
118 wIl 5|((1 - VVV w2)) (1 -1- VVL w5) w3 11
M /
1109 - -231 (1 - mu) (1- m))
Q-1
Q-1
+ +nM
Σ (I - VVL w,))
Σ (I - (U-V2,(03,,,)11
9=0
9=0
+ + -1- (1 - nn4 2) _ 100 - 11
(9)
/
We next bound Ag = ||(T 17 V3 LON w;)) (I - vn- ( 10;))911 in Equation 9 as:
11-nyin nリ) + (1 n/1 npl ely 0g ||-
(10)
which, by telescoping Equation
10p and in conjunction with Equation (9. yields
np M 11of - -071 SQ(1 - -
I1oN 07 + (1- (1-1)1))1111111 1109 u3
Q-1 + M Σ
q(1 7 mpl10 - 07] || + (1 - (1 1 (1-nw)9) タ)
100-
103 - 0 (11)
/1
9=0
Q(1 mnni Q pM1 110m - -071 + (1 - nnn 01000-11111101 - -ل-11l |l
H
1 1- (1 - (1- n
+ (1 - (7tti 01 1/15
- -351+ +
PM 1 - -031
n2
+ (1 (1 - 0) L 1107 - 8
/
which, combined with ||u3 - - ||| < 4 + ) + 1) 1[u -.jill and using the fact that
(1 - (1=x)² 2 1 - IQ for 0 v x - 1, yields
4 C3110; 110 - -0717 1|2
Elle9 - v3 <(1 - m - -0-111 + n/
4 (1) To Mp 2 T.
(T + +1) ||., w 1|
(12)
np p 42
4
16

---

where the constant Co == QpMn + Q + tQQ P
The next step is to characterize the error induced by the lower-level updates on 0.
Note that 0j arg ming L(,, wj). Using Assumptions and
2 we have
|00 031 S (1 o1u) M 100 07,
(13)
which, in conjunction with 09 = 0 and Lemma 2.2 in 25 yields
Elle - 07 <(1 an) (1 2) 1
+ (1 - ap) (1 + 1/ L"
Bllwy - w 112
(14)
42²
Recall the definition that can obtain
Then, combining Equation (12) and Equation 11 yields we
PM L
P²2 L2
(1 +
BII0N - 031 + E1 u/11
<(1 + 2)(1 ax) M ,²M32
1222 (1
8r1.
B110 3-1
-1
m/
+ +1 - 11 - w 112 + w|B| my
w--1l?
(15)
where the constant w is given by
1 + 1) (1 ap) (1+
M²M I
1.2122
112
8 L
M²2 14_
(120 r(1 anp) N (1+ +)
1 T.2p2
1/2
(16)
114 2
Recall that we choose (1 +1+10 A)(1 ap) No (1 + 8rL2
S mue. Then, we obtain from Equation (15)
np
that
P²
(1
E110N 07,1 + t 2 u3
12
<(1 mmuu (1 + p² M²
E El カ-1 -1-111
L2 112
+ (1 7/) 1-1 03 1/=111 +IwEElu, w
(17)
Let 0j (1 3 1=
E 07 12 1 2 111 Then, incorporating the update that wy
Par - -1p;-1) into Equation 17 yields
3 (20-1 - PAn - ||
6, S(1 - nu)6, 1 + 3
G
+ 2w 1w08119y-1 vo(
(18)
We next bound the last term in the above Equation estimate 3 Rw,, B) V.. VoL wy) have
18
Based on the definition of the hypergradient
E||i;
V
VV 6: VR(W,, 0112 3p2 22
3E
B10 1/112= 1|2
3L'E
-,912
42
i 3
V V 8: (Rww,8)l + +LL
[1
M²M
B110; 07²1 112 + 3L 3L 1
2
SEB
P²M
6K
+ 2
1
B1103 11 32 -
+ 3L36,,
(19)
B
1²
B
17

---

where (2) follows because V ó; 2) is an unbiased estimate of V R(w, 8) and (di) follows from
Proposition !
Substituting Equation (19) into Equation (8) yields
8, S (1 7/ + 6w L3) 16) 12
20 G--1l1..
(20)
B
Let 7 = 1- Th + 6wB L2 Then, telescoping Equation (00g
yields
12wK
j-1
69 - r 50 +
(1 (1-T) r) + 2w
(21)
t=0
Based on Equation (1 we are ready to provide the final convergence result. First, based on the
Lipschitz continuity in Assumption 1 Assumption annd Assumption 3 we have
VV(w1)- Vo(w2)) S Løllur - wwel,
where the constant Lg = vK= + +P+ + 2
1² + pt. is the smoothness parameter. Then,
n³
this inequality further implies
La
b(1j++1) Sp(w)) (Vo(w)), (0t1)) wwp) 2
|1,+1 - wyyl
1
SŌ(w;) - 3 (Bp)) Pan(w; (425) - wz) + (Vó(wz)) P,, Par -3p,) w3))
L3 ||05+1 wyl1?
(22)
To analyze the second term the right hand side of the above Equation 22 we note that
PB (w)- B43;) w))
=(wy _B, Pa- (w, Bt2)) Pa- (w, 34p)) - w,) + 1|P (1: (wx Bq,) - w, ||
which, in conjunction with the property of projection on convex set that (z- 1 (2)(2)))) y PA- (x) S 0
for any y E S and the fact that wy PA (w,-1 840-11 E S, yields
- (Bp,,, Pa (wy - 84p,) w,) 2 |P (wy - BB2,) - w 112 2 20.
-w
(23)
Then, substituting Equation 23 into Equation (22 yields
Le
So(w)) + (V)(w,) - Pjj PAn (wn - B:p;) - -w3) +
|| - wo
2
SØ(w;) 3 |,,,13
8
|جاا vo(w;)]1
I.0.32
11Ž,11
2
2
SΦ(w;) (9-
3 B2
||G 22= (B.
T2
110; vo(w,)11
(24)
4
2
where we use the notation that G₁ (wj - PA (wi - B)),)) and the non-expansive property of
projection. Then, taking the expectation and incorporating Equation (19) into Equation (4 we have
E <Rp(w,) (
L002
L0
B|G
(3
Bl|i,
Vo(w,))11
2
3 Lg,32
+ 3 L032
6K
<kd(w,) - 4
EIG,, 1|
+ 3L',,).
(25)
4
2
[B]
Then, substituting Equation 21 into the above Equation 25 yields
Ed(w5+11 <Ep(w;) (3
T2
12
6K
El1G,112
(B
2
B
12wK 32
j-1
+ +LL2 B
(7'60-
+ (1 [1-r)[B]
+ 2w0
T
2
<Ep(ws) - (3) g2
E||G,112 + (1+
6w. 13)
(3
T.g.32 6K
4
1 1-
2
[B]
L8.3
L8
j-1
+ +3I2 ( B
7
5n + 66w
Σ
-
E G
GE
2
2
0=0
18

---

which, by taking the telescoping over j from 0 to J 1, yields
1-1
L
4
1
=
(ww)) - mino v(w)
+ (1+ 6w,321.2
(1
L
6K
BJ
1-
2
[B]
3T,2 (1 1igft
(1 - T + GuoB2 1. L
2
do
LGB
1
J-1 1-1
7
7'B|
1=0 1=0
②0 (W)) - mino k(w))
+ (1+ 6w.
1 )
B
6K
BJ
2
[B]
3T. (1 Light
T)J + Gis
2
d0
1,3 LoB
1
J-1
EIG,, 12
(1
(1
T)J
Rearranging the above inequality, we have
3
6G132 1,2
(1 2 E||G211
1=0
((wb) - min ((w) (1+
6wFBL L2
1 (2)
(1-
LaB 2
6K
31,2
(1
60
(26)
BJ
B
(1 T)J
Recalling the definition that r = 1- - nh n 6w:32 L22, and noting that we choose the stepsize B such that 6w L22 < tn and 3 < I7.5 we can simplify Equation (26) as
Σ BIG, ((w)) min d(w)
27K
27L260
+
+
16.7
BJ
4|B
8mit
M² From the gradient descent based updates, we have 6, (1+ +
1A
0311
+
Ellog
-tll - -
(1 12p
M2
[10@ - 01112 + |lu| - uill? < +00. Then, the proof is complete.
B Proof of Corollary 1
Based on the definition of Co = QeMa + T220pM + 7Q and noting that 17 S 1 < and
Q 3, we have Cq I 12n(( pM + L), which, combined with the definition that r (2 +L)2 yields
C3
S 144n/2. Then, based on the choice of N = 1 and X = 2, we have
(1 + A)(1 a (1+
8rI2
$ (1 apl
2 (1+
1152nL
S1
op
+
1152n 2
mp
1
2
which, in conjunction with S 1008 at and a S t. yields
n²2
(1 + A)(1 a (1+ 8r1,2
S
4 op $1 mp..
(27)
7/
This implies that the inequality (1+ 2) app N + 8rL2
< 1 du required by Theorem is
T/
satisfied. Then, treating μ. 77 L, M, a. B, K, |088 - 051 2 and
|| - 21 12 as constants independent
of the total number J of iterations, we have
E s o
1
(28)
B
1=
Then, to ensure an e-accurate stationary point, the number of iterations is -2 with batch size [ (2).).
19

---

C Experiment Hyperparameters
The experimemtal hyperparameters list in Table including the memory size: [M] coreset size: [S], stream batch size: [B,], learning rate for M Ir.. learning rate for Mas: Iry, learning rate for sample weights: lr., regularization efficient: epochs for training model: E, outer loops bilevel optimization: J, inner loops in bilevel optimization: N, loops for estimating the Hessian-inverse-
vector product: Q, factor of Gaussian noise:
Table 7: Hyperparameters settings in experiments.
Permuted MNIST
Split
Split Tiny-Imagenet
Multiple Datasets
Split
Hyperparameters
CIFAR-100
Food-101
M
200
100
200
83
100
1
10
20
10
Bd
Ir
0.005
0.15
0.20
0.1
0.15
Iry
5.0
5.0
10
5.0
10
Irw
5.0
5.0
10
5.0
10
0.1
0.1
0.1
0.1
0.1
Q
3
3
3
3
16 3
1e -
le
1e -
1e 1e-3
D Running Time Comparison
We evaluate the rumning time (wall-clock time) of baseline methods on Split Tiny- Tiny-ImaeeNet and Split Food-101 in Table All the training sections keep the same among these algorithms. Since there no advanced coreset selection procedures in K-means Features, K- K-means Embedding, Uniform sampling, iCaRL, and Grad Matching, their running costs are pretty low but with worse performance (i.e., accuracy and forgetting) compared with our approach BCSR. PBCS and GCR, SPR and MetaSP don't involve bilevel formulations, they cannot guarantee accurate coreset sampling though with lower time cost against BCSR. Compared with OCS, BCSR takes 23% and 35% running time reduction Tiny-Imaged and Split Food- 101, respectively. Because similarity computing based on data pairs is computationally expensive for OCS. Greedy Coreset takes much more time than BCSR due the usage of NTK.
Table 8: Running time.
Time (hours)
Methods
Tiny- Imageem
Split F0od-101
K-means Features
0.15
0.02
K-means Embedding
0.41
0.04
Uniform
0.13
0.03
iCaRL
0.41
0.04
Grad Matching
0.57
0.06
SPR
0.77
0.11
MetaSP
0.86
0.13
PBCS
1.13
0.15
GCR
0.91
0.13
Greedy Coresct
6.26
0.83
OCS
3.45
0.40
BCSR
2,65
0.26
E Experiments on Permuted-MNIST
The experiment results on Permuted-MNIST is presented in this section. BCSR outperforms other baselines significantly in AVG ACC all the data settings, while showing relatively low forgetting.
20

---

Table 9: Experiment results Permuted MNIST
Balanced
Imbalanced
Label Noise
Methods
Ay
FGTT
Ay
FGTT
Ar
FG77
K-means Features
54.3010.93
0.064:0.012
39.4610.11
0.02340.003
46.71+0.64
0.09410.011
K- K-means Emhedding
54.7841.88
0.056x0.009
41.9742.02
0.01340.005
47.36&1.58
0.082:0.015
Uniform
53.7440.35
0.07340.00 006
38.4911.8 89
0.02540.008
46.35#1.72
0.091=0.014
iCaRL
52.62+0.01
0.076+0.00)
18.64=0.58
0.022+0.001
48.14=0.83
0.082=0.007
Grad Matching
54.76+1.61
0.065=00011
33.67+1 .224
0.02840.003
48.24=0.42
0.089+0.009
SPR
54.24#0.45
0.068=0.011 019
40.79+0.83
0.031 003
48 48.23=0075
0.067=0.004
MetaSP
41.3240.94
0.061+0.007
Greedy Coreset
54.1010.81
0.051
26.68113.39
0.033+0.014
19.45a1.73
0.078=0.009
GCR
54.5340.64
0.067=0.021
40.6340.50
0.032x0.005
48 48.64a0.755
0.07430.014
PBCS
51.61+1.44
0.144z0.021
41.14+0.23
0.119#0.007
39.74
0.178=0.001
OCS
54.37=0.34
0.026=0.001
50.19=0,47
0.020#0.005
48 48,08=1 ,44
0,046=00.003
BCSR
56.23=0.29
0.058
52.52+0.45
0.010=0.002
50.8243.03
0.056=00007
Evolution of Average Accuracy
We present the learning process of different methods on Multiple Datasets in Figure There are five tasks, where the average accuracy is tested after training each task. BCSR shows better performance than other baselines in different settings, including Balanced, Imbalanced, and label-noise.
AVG ACC
70
20
40
Tanks
Tasks
Taskks
(a) Balanced Multiple Datascts
(b) Imbalanced Multiple Datasets
(c) Label-Noise Multiple Datasets
Droecting
Marcing
Grady
Figure 4: Evolution average accuracy during the continual learning process for Multiple Datasets.
G Possibility Distribution of Candidate Coreset
To explore the effect of top-K K regularizer, we observe the possibility distribution of sample weights after each bilevel optimization, where sample weights of candidate coresets initialized uniformly. The novel top-K regularizer makes sure that the summation of the top-K entries of the learned probability vector is large, such that we can confidently choose coreset with size K We show the weight distribution after optimization in Figure. 5 where you can find that top-K weights are much higher than others (with margin 2%), which easily distinguishes the top-K core samples from candidates.
more of Gradd 6012
0.08
0.30
0.00
Possibiityy
0.08
0.04
0.02
0.00
Candidate
Figure 5: Possibility distribution of can- didate coreset for one mini-batch stream data.
Figure 6: The hypergradients in outer-loop.
21

---

H The Effect of Top-K K Regularizer
To further analyze the effects of top-K regularizer, conduct the ablation study with different values of regularizer coefficient À on balanced Split CIFAR-100. The performance results with different are shown in Table 10 and the corresponding average top-K summations of coreset weights are in Table [T In our experiment, there are 50 candidate samples in each mini-batch data, and the summation of 50 coreset weights is equal 1.00. Top-K summation of weights increases as increases, which imposes higher probabilities on top- K entries and lower probabilities on the rest candidates. The best performance is achieved when À = 0.1, which means À balances the trade-off between the loss function and regularizer strength: if À is too large, the algorithm primarily focuses on choosing the important samples instead of updating the model parameter, and vice versa.
Table 10: Ablation study for the regularize coefficient A.
Measure
>=0.01
x=0.05
0=0.10
A=055
x=1.00
Ar FGTT
59.3740.35
60.23+0.43
61.60+0.11 0.051=0.015
59.42+ 1.45 0.138+0.075
58.89+1.64 6.64
0.095+0.098
0.07420.054
0.128=0.076
Table 11: Top-K summation/Total summation of coreset weights (K 10).
Measure
>=0.11
A=0.05
A=
A=0.50
>=1.00
Top-K KK Sum/Total Sum 0.41/1.00
0.56/1.00
0.63/1.00
0.73/1.00
0.84/1.00
I Hypergradient Evolution
To demonstrate the efficiency of bilevel optimization, we illustrate the evolution of hypergradients for a bilevel optimization on Split CIFAR- 100 Figure. [6] We observe the average norm of hypergradient reduces from 10-1 to less than 10-2 in each round of coreset selection with loops equal to 10. The hypergradient curves show that our designed bilevel optimization provides both theoretical and practical convergence guarantees.
Table 12: The effect of coreset size
K=10 AT
K=20
K=40
Methods
AT
AT
Uniform
58.99+0.54
53,57+2.93
53.03+1.97
Greedy Coreset
59.39=0.16
56.8143.32
56.0940.42
PBCS
55.64=2.26
49.84+1.76
40.95=0.32
OCS
52.5740.37
54.8740.58
56.4622007
BCSR
61.60+0.14
59.06=1.15
56.58+0.21
The Effect of Coreset Size K
Coreset size K also plays important role in the experiment. We compare our BCSR with other coreset-based algorithms on different K. Note that coreset selected from the current stream mini-batch B,, so the coreset size K satisfies K < [B]]- In the main experiment results, K = 10 is fixed in all the algorithms for fair comparison. Here, we set K = 10, 20, 40 to conduct the continual learning experiments, respectively. The result is represented in Table 12 Note that all the results presented here are based on balanced Split CIFAR-100.
We mainly compare with the other four methods, including Uniform Sampling and three coreset- based methods, Greedy Coreset, PBCS, and OCS. We can observe that the performance of almost all methods becomes worse when coreset size is large. The reason is that if coreset size is larger and closer to B,, more redundant or noisy data are selected from the current stream mini-batch, and the coreset would not be representative anymore. In contrast, the smaller coreset could reduce the probability that redundant data are selected. Compared with other methods, BCSR shows the best performance (both accuracy and forgetting) and better robustness different K.
22

---

K The Effect of Inner Loops N and Hessian-invers--eetorr Product Loops Q
We conduct ablation studies explore the sensitivity of hyperparameters (N and Q) Split CIFAR- 100. The results are presented in Tables 13 (NV and Table (Q).. The model performance remains relatively stable when increasing inner loops (N) while fixing Q. But too large N (N 2 15) leads to performance degradation due to overfitting. The Q loops show similar properties that few Q loops (e.g., Q = 3) are enough to approximate the Hessian-inverse -nverse-veeerrooo product. Too small Q and too large Q will hurt the performance due to possible underfitting (e.g., Q = 1) and overfitting (e.g.. Q 20).
Table 13: Ablation study for the inner loops (N) with fixed Q = 3.
Measure
N=1
N=5
N=10
N=15
N=20
Ar FGTT
61.60+0.14 0.051
61.75+0.11 0.047#0.013
61.64+0.15
60.77+0.32
59.20#0.41 0.079#0.035
0.063#0.017
0.074#0.021
Table 14:
Ablation study for the loops Q with fixed N = 1.
Measure
Q=1
Q=3
Q-5
Q=10
Q-20
Ar FGTT
12.14+1.53
61.60=0.14
61.57+0.15
58.42+0.53
57.80+1.31
0.12340.038
0.051#0.015
0.06410.012
0.173+0.045
0.162+0.041
L Datasets
Spit CIFAR-100. Balanced split CIFAR-100 is based on the original CIFAR-100 and is split into 20 tasks, each consisting of 5 disjoint classes. The imbalanced setting and label noise also applied to this dataset to make the task more challenging. We follow [13 to transform the original dataset imbalanced long-tailed CIFAR-100. In the label-noise setting, randomly select 20% data in each task and randomly change their labels to an arbitrary label of 10 classes.
Permuted MNIST. Balanced MNIST is handwritten digits dataset 43 containing 20 tasks, where each task applies a fixed random permutation to the image pixels. For the imbalanced setting, we randomly select classes over 10 and sample 10% of the selected classes for training. We also conduct the experiments on the label noise scenario, where symmetric label noise with 20% noise rate imposed on the data. In particular, to make the problem setting challenging, each task only retains 3000 training data randomly sampled from the original data.
Multiple Datasets. This dataset 78 contains couple of totally different datasets, including MNIST [43), fashion-MNIST [75), NotMNIST [8]. Traffic Sign [69] and SVHN (54). There are 5 tasks, and each task is constructed by randomly selecting 1000 training samples from a different dataset. The procedure of creating the dataset in the imbalanced and label-noise settings is the
same as that in Split CIFAR-100.
Split Tmag- This dataset [42 contains 100000 images of 200 classes (500 for each class) downsized to 64 64 colored images. Each class has 500 training images, 50 validation images, and 50 test images. We construct the task sequences by splitting data into 20 tasks, where each task consists of 10 disjoint classes.
Split Food-101. This dataset 7 is a challenging data set of 101 food categories, with 101 '000 images. All the images are resized to x 64 pixels to be fed into models. To build continual learning tasks easily, We discard the last category and split data into 20 tasks, with 5 categories within each task. Other data settings, including imbalanced and lable-noise, are the same as Split CIFAR-100.
M Assumptions and Properties
We first provide standard definitions and assumptions for the convergence rate analysis of bilevel optimization 225 36). For notational convenience, we define ((0) == Σn (()).
23

---

Definition 1. A mapping f is Lipsschht continuous 2 llf(z) f(x')] - 1 2/1l.
Assumption 1. The lower-level function L(0, w) is p-strongly-conver w.E.t. 0.
Assumption 1 is a necessary geometric assumption in analyzing the convergence rate of bilevel optimization algorithms, as also widely adopted existing theories in [25 37 32
We also note that this condition satisfied for overparamettrrized neural networks 82] The following assumption
imposes some Lipschitz continuity conditions on the upper- and lower-level objective functions.
Assumption 2. The gradients VoL(O, w). V L(A, w) and E(0) are L-Lipschitz continuous w.r.t. and In addition, the gradient norm Ve((0 (w))ll S M.
Note that we do not impose any conditions on the regularization function R(w, 6). The following assumption imposes the Lipschitz continuity on the second-order derivatives of the lower-level functions.
Assumption 3. The second-order derivatives v. VaL(O, w) and [. 0) are p-Lipschitz continu- ous.
Then, we use the following proposition to characterize the properties of the smoothed top- regular- izer R(w, 8), based the results in 23).
Proposition 1. The smoothed regularizer R(w, 6) and its sampled version R(w, 6; satisfy the fol- lowing two important properties: (i) The gradient V R(w, 5) exists and is VK= -Lipschitz continuous: (ii) The gradient norm [[[,, 6; Z)|| is bounded by v K for any sample ž.
Proposition shows that the regularizer R(w, 8) is smooth and its stochastic version R(w, 8; is bounded. These two properties are important guarantee the non-asymptotic convergence of our proposed bilevel method.
24


Reviews:
[{"review_id": "PctCSoZCdv", "reviewer": "Reviewer_FPqc", "summary": "The paper presents a better approach for grasping the coreset-based bi-level optimization procedure used in the field of continual learning. The proposed method relies on the use of the proxy model to obtain a coreset, which in turn will affect the training of the original model.  With that being said, the idea relies on relaxing the hard cardinality constraints usually used in the field of coreset construction for continual learning tasks, to a softer version that allows the use of first-order methods.", "questions": "Is it possible to circumvent the need for a proxy model in the case of working with large models? How worse would the results be if one would use some quantized or pruned version of the original model $M_{tr}$?", "limitations": "The authors listed the limitations associated with their theoretical analysis in the form of assumptions usually used in the field of coresets for continual learning.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "In what follows, a list of the strengths of the presented paper is given:\n\n * The paper draws back from the hard cardinality constraint and follows a relaxed version of it by resolving to the use of probability simplex and the top-K smoothed regularization to mimic the effect of the lost cardinality constraint.\n * The method is easy to follow, as well as it relies on the use of a proxy model.\n * While the proposed model is among the top 5 slowest from the list of competitors (referring to Table 8 in the appendix), it is by far the best method in terms of accuracy and forgetting almost across the board. \n * The new formulation of the problem allows for dropping the use of combinatorial optimization techniques while exposing the field to first-order optimizers. \n * Finally, the paper is well-written and easy to follow.", "weaknesses": "One problem that I have in mind is the use of the proxy model, which might be a limitation in the presence of large models, i.e., models containing $> 100M$ parameters. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer FPqc:\n\nThanks for your reviews. We have addressed your concerns below.\n\n**Q1: The proxy model $M_{cs}$ might be a limitation in the presence of large models, i.e., models containing >100M  parameters. Is it possible to circumvent the need for a proxy model in the case of working with large models? How worse would the results be if one would use some quantized or pruned version of the original model $M_{tr}$?**\n\n**A1**: It is feasible to use only one model for the training and coreset selection phases. After each training phase, the model parameters can be saved in the disk temporarily and then the model continues to conduct coreset selection.  In the next model training phase, the saved model parameters are loaded into the current model again. This method can handle large models but with an extra overload of loading and checkpointing. \n\nIn addition, we apply the quantization technique [1] to the models $M_{cs}$ and $M_{tr}$ with lower bits. Specifically, we keep the full precision of the model $M_{tr}$ during the learning of each task, but the model  $M_{tr}$ is quantized upon finishing one task. In particular, the gradients are calculated on quantized model parameters (INT16, INT8 and INT4) to perform gradient-based updates. After several steps of updates upon finishing the training of one task, the full precision model is quantized and saved. Then the quantized model is loaded to $M_{cs}$ for coreset selection. The above process repeats until finishing all the tasks. Finally, the quantized model $M_{tr}$ is used for performance evaluation. The results (ACC, FGT, quantized model size) are shown in Table 1. Specifically, models are quantized to INT16, INT8 and INT4 respectively, but with a small performance degradation (e.g., reduced by up to $4.1$% for INT4). However, the model size shrinks from $3.76$MB to $1.67$MB (INT16), $0.93$MB (INT8) and $0.61$MB (INT4), respectively, which reduces the memory footprint significantly (e.g., up to $83.8$% decrease for INT4). The results demonstrate that the quantized model achieves comparable performance to the original full precision model for the coreset selection but with a much smaller model size. That provides some useful insights into a quantized version of a large model applied in continual learning. \n\n**Table 1. The performance of the quantized model of ResNet18 on Split CIFAR-100 (FP32 means the original model with full precision).**\n| Param Type | ACC             | FGT                | Model Size (MB)|     \n|------------------|------------------|--------------------|-----------------------|\n| FP32            | 61.60±0.14  | 0.051±0.015    |  3.76                  |\n| INT16           | 60.03±0.16  | 0.064±0.017    |  1.67                  |\n| INT8             | 59.12±0.21  | 0.081±0.024    |  0.93                  |\n| INT4             | 59.06±0.15  | 0.085±0.027    |   0.61                 |\n\n[1] Polino A, Pascanu R, Alistarh D. Model compression via distillation and quantization[J]. arXiv preprint arXiv:1802.05668, 2018.\n"}, {"review_id": "5653gIus5K", "reviewer": "Reviewer_AXy9", "summary": "This work addresses the coreset selection problem in rehearsal-based continual learning, focusing specifically on the application of bilevel optimization. The authors identify limitations in existing bilevel optimization-based coreset selection methods for continual learning, including high computational costs resulting from greedy search and the loss of bilevel optimization nature due to single-level equivalence. To overcome these drawbacks, the authors propose a new formulation that incorporates the probability simplex and a smoothed top-K regularizer. The latter enforces the K most important elements have larger weights. The authors develop a new stochastic bilevel method for this continuous and smooth loss. The effectiveness of the proposed method is demonstrated through comprehensive experiments, which also include various ablation studies. The authors establish the properties of the new loss function and provide guarantees on convergence.", "questions": "1. How to select the parameters such as N, Q and $\\delta$ in Algorithm 3 for continual learning? It would be beneficial to provide suggestions or guidelines for choosing these parameters and to discuss the sensitivity of the algorithm's performance to such parameters.\n\n2. What are the main challenges of the bilevel optimization analysis in the continual learning setting? ", "limitations": "yes", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Both continual learning and bilevel optimization are timely topics.The exploration of the benefits of bilevel optimization in continual learning is an under-explored area, making the studied topic in this work both interesting and important.\n2. The paper is well written and easy to follow. The inclusion of Figure 1, illustrating the process of training bilevel algorithms in continual learning, along with PyTorch-style pseudocode, greatly aids in understanding the entire process.\n3. The introduction of the new loss function and bilevel algorithms is well-motivated. The replacement of the nuclear norm with a smoothed top-K regularizer, as proposed in the paper, is a good idea that leads to faster and improved bilevel optimization algorithms. The empirical evidence provided in Figure 3 serves as a strong justification for the efficacy of the new loss function and algorithms.\n4. The experiments conducted in the paper are comprehensive. The evaluation encompasses various datasets, including multiple datasets, split Cifar100, and large-scale datasets like Tiny-ImageNet and Food-101. Additionally, various ablation studies are also included.\n5. The paper establishes guarantees on convergence rate and explores the properties of the new loss function. ", "weaknesses": "The proposed algorithm needs to compute the Hessian-vector products, which may be computation expensive in large-scale cases. This computational expense may pose challenges and limit the applicability of the algorithm. Is it possible to improve the efficiency of the proposed method by utilizing Hessian-free bilevel algorithms based on recent advancements (e.g., Liu et al. [1], Sow et al. [2])？\n\n[1] Liu, Bo, et al. \"Bome! bilevel optimization made easy: A simple first-order approach.\" Advances in Neural Information Processing Systems 35 (2022): 17248-17262.\n\n[2] Sow, Daouda, Kaiyi Ji, and Yingbin Liang. \"On the convergence theory for hessian-free bilevel algorithms.\" Advances in Neural Information Processing Systems 35 (2022): 4136-4149.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer AXy9,\n\n Thanks for your reviews. We have addressed your concerns below.\n\n**Q1: Is it possible to improve the efficiency of the proposed method by utilizing Hessian-free bilevel algorithms based on recent advancements?**\n\n**A1**: Yes, two types of Hessian-free methods may be considered. The first approach is to approximate the Hessian- and Jacobian-vector products via finite-difference estimation, i.e., using $[\\nabla f(x+\\alpha v)-\\nabla f(x-\\alpha v)]/(2\\alpha)$ to approximate $\\nabla^2 f(x)v$. Then, the entire process will not contain second-order information. The second approach is to apply the recent value-function-based problem reformulation and constrained optimization-based approaches [1]. We will investigate these ideas in future studies. \n\n[1] B. Liu et al. “Bome! bilevel optimization made easy: A simple first-order approach.” NeurIPS 2022.\n\n**Q2: How to select the parameters such as N, Q, and $\\delta$ in Algorithm 3 for continual learning? It would be beneficial to provide suggestions or guidelines for choosing these parameters and to discuss the sensitivity of the algorithm's performance to such parameters.**\n\n**A2**: We conduct ablation studies to explore the sensitivity of hyperparameters ($N$ and $Q$) on  Split CIFAR-100. The results are presented in Tables 2 ($N$) and 3 ($Q$). The model performance remains relatively stable when increasing inner loops ($N$) while fixing $Q$.  But too large $N$ ($N\\geq 15$) leads to performance degradation due to overfitting.  The $Q$ loops show similar properties that a few $Q$ loops (e.g., $Q=3$) are enough to approximate the Hessian inverse product. Too small $Q$ or too large $Q$ will hurt the performance due to possible underfitting (e.g., $Q=1$) or overfitting (e.g., $Q=20$). $\\delta$ is a factor for Gaussian noise. It is usually small enough for Gaussian smoothness, so it is fixed as $1e-3$ in the experimental setting.  \n\n**Table 2.  Ablation study for the inner loops (N) with fixed loops $Q=3$.**\n| Measure | N=1             | N=5              | N=10           | N=15            | N=20            |\n|-------------|------------------|------------------|-----------------|------------------|------------------|\n| ACC       | 61.60±0.14  | 61.75±0.11   | 61.64±0.15  | 60.77±0.32   | 59.20±0.41  |\n| FGT       | 0.051±0.015| 0.047±0.013| 0.063±0.017 | 0.074±0.021 | 0.079±0.035 |\n\n**Table 3. Ablation study for the loops Q with fixed inner loops $N=1$.**\n| Measure |  Q=1                 | Q=3            | Q=5               | Q=10            | Q=20            |\n|-------------|----------------------|-----------------|-------------------|------------------|------------------|\n| ACC       | 52.14±1.53       | 61.60±0.14  | 61.57±0.15   | 58.42±0.53   |  57.80±1.31  |\n| FGT       |  0.123±0.038    |0.051±0.015 | 0.064±0.012  | 0.173±0.045 | 0.162±0.041 |\n\n**Q3: What are the main challenges of bilevel optimization analysis in the continual learning setting?**\n\n**A3**: Existing works on bilevel optimization mainly focus on the unconstrained case, and the analysis often relies on the continuity between two adjacent iterates. As a comparison, our analysis in CL setting needs to deal with the constraint over the simplex, and it is non-trivial to handle the possible discontinuity caused by the projection.  Another challenge lies in showing the smoothness of the problem as well as a hypergradient estimation error under the stochastic Top-K regularizer. \n\n"}, {"review_id": "nq2SRdYaQA", "reviewer": "Reviewer_vGFs", "summary": "The authors present a new approach to coreset selection in rehearsal-based continual learning. The authors claim that traditional methods optimise over discrete decision variables, resulting in computationally expensive processes. To address this, they propose a new bilevel formulation where the inner problem finds a model that minimizes expected training error, and the outer problem learns a probability distribution with approximately K nonzero entries through adding a regularizer and ensuring convergence to the ϵ-stationary point with O(1/ϵ^4) complexity. The authors also perform extensive experiments demonstrate superior performance compared to existing methods in various continual learning settings.", "questions": "Could you please clarify the differences and advantages between your method and [7]? In lines 135-139, the author simply states that \"so this formulation [7] oversimplifies the coreset selection problem.\" However, this statement does not highlight any specific disadvantages of [7].\n\nI will consider improving my score if my question and concern could be well-addressed.", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The availability of provided code facilitates reproducibility, making it a straightforward process.\n2. The authors present experimental results that demonstrate a pretty good performance in comparison to the selected baselines.\n3. The inclusion of the added regularizer seems promising, but it requires a more detailed and elaborate explanation to justify its contribution adequately.", "weaknesses": "**Weaknesses**\nMy main concern is that this work appears to be primarily an incremental extension of prior work [2] by adding a regularizer. While this is not necessarily negative, I do not see any significant new improvements from an algorithmic perspective. Specifically, in lines 46-52, the authors assert that the key challenges of bilevel coreset selection are (1) the expensive nature of optimization over cardinality constraints and (2) the nested nature of bilevel optimization. However, these weaknesses pertain to [1] rather than the coreset selection problem itself.\nIn order to address these challenges, [2] was proposed. The contributions that the authors claim in this paper seem to stem from [2] rather than the proposed method itself.\n\n**Suggestion:**  \nCertainly, enhancing the motivation of the paper and clarifying the advantages of the proposed method compared to [7] is crucial for improving the paper. The author should allocate more space to address these aspects.\n\n[1] Borsos, Z., Mutny, M., & Krause, A. (2020). Coresets via bilevel optimization for continual learning and streaming. Advances in neural information processing systems, 33, 14879-14890.\n\n[2] Zhou, X., Pi, R., Zhang, W., Lin, Y., Chen, Z., & Zhang, T. (2022, June). Probabilistic bilevel coreset selection. In International Conference on Machine Learning (pp. 27287-27302). PMLR.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your reviews. We have addressed your concerns below.\n\n**Q1: Could you please clarify the differences and advantages between your method and [2]? In lines 135-139, the author simply states that \"so this formulation [2] oversimplifies the coreset selection problem.\" However, this statement does not highlight any specific disadvantages of [2].**\n\n**[1] Borsos, Z., Mutny, M., & Krause, A. (2020). Coresets via bilevel optimization for continual learning and streaming. Advances in neural information processing systems, 33, 14879-14890.**\n\n**[2] Zhou, X., Pi, R., Zhang, W., Lin, Y., Chen, Z., & Zhang, T. (2022, June). Probabilistic bilevel coreset selection. In International Conference on Machine Learning (pp. 27287-27302). PMLR.**\n\n\n**A1**: Thank you for this insightful question. We will improve our presentation, especially the comparison with [2]. The challenges of bilevel continual learning in [1] are:  1) performing optimization over discrete decision variables with greedy search; 2) the nested structure of bilevel problems. Both [2] and our method BCSR relax the discrete bilevel optimization problem into a continuous one. Our approach improves over [2] due to the following differences.\n\n1) Zhou et al. [2] relaxes the bilevel formulation to minimize the loss function over the Bernoulli distribution $s$, i.e., $\\min_{s\\in \\mathcal{C}} \\Phi(s)$,  and develop a policy gradient solver to optimize the Bernoulli variable. Their gradient $\\nabla_{s}\\Phi(s) = E_{p(m|s)}\\Big[L(\\theta^*(m))\\nabla_{s}\\ln p(m|s)\\Big]$ discards the implicit gradient of $L(\\theta^*(m))$ in terms of $s$. However, $\\theta^*(m)$ actually depends on the mask $m$, and $m$ depends on the Bernoulli variable $s$. Therefore there is an implicit gradient because changes in $s$ will cause changes in $\\theta^*(m)$: this fact is ignored by Zhou et al. [2] and hence it is a disadvantage. In contrast, our bilevel optimization computes the hypergradients for the coreset weights $w$ ($0\\leq w \\leq 1$ and $\\|w\\|_1 =1$ ), which considers the implicit dependence between $\\theta^*(w)$ and $w$. The experiment results also prove that our method is much better than Zhou et al. [2] for coreset selection.\n\n2) Zhou et al. [2] assumes that the inner loop converges to $\\theta^*(m)$ exactly, which oversimplifies the analysis and may not hold in practice. In contrast, we carefully analyze the gap between estimated $\\hat{\\theta}(m)$ by our algorithm and the minimizer of the inner problem $\\theta^*(m)$. Please note that we use $m$ (i.e., sample mask) in the rebuttal to follow the notation in Zhou et al. [2] but our paper uses notation $w$ to denote coreset weights (which is equivalent to sample mask). \n\n3) Our new bilevel formulation introduces a novel smoothed Top-K regularizer, which is important as shown in our ablation studies (Table 6 and Section G in the original manuscript). In contrast, [2] does not use such a regularizer. Indeed, we show empirically that our algorithm BCSR is  better than Zhou et al. [2] in a wide spectrum of benchmark datasets, as illustrated in Table 1~4 in the main text.\n"}, {"review_id": "8VQg41qwDZ", "reviewer": "Reviewer_b44u", "summary": "Past works have limitations in terms of scalability, formulation approximation, or performance. This paper offers an efficient coreset selection problem with provable theoretical guarantees. That is, the authors solve a bilevel optimization on a probability distribution over the dataset with loss minimization on the selected dataset that is guided into a low-dimensional manifold via a smoothed top-K loss as a regularizer on the probability distribution. ", "questions": "if Weaknessses (1) could be further analyzed and shown, as well as comparison with (2) other state of the art rehearsal baselines comparison would be informative.", "limitations": "Not mentioned in the paper.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The approach is simple, yet well-motivated by the limitations of previous works.\nThe writing addresses the limitations well and is easy to follow. \n", "weaknesses": "(1) Further analysis into the top-K loss and its causal effects would aid in understanding the mechanics of probability distribution being regularized into a low-dimensional manifold. \n\n(2) comparisons with state-of-the-art non-coreset replay methods (e.g., using stability plasticity scores [1], contrastive representation based selection [2]), as it would be meaningful to see the prospect of this direction. \n\n(3) [minor] main illustration figure 1 could include more technical information (embedding some important eqns for example) or include an additional figure to guide the reader better.\n\n\n\n[1] Sun et al, Exploring Example Influence in Continual Learning, NeurIPS 2022\n[2] Kim et al, Continual Learning on Noisy Data Streams via Self-Purified Replay, ICCV 2021", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer b44u,\n\nThanks for your reviews. We have addressed your concerns below.\n\n**Q1: Further analysis into the top-K loss and its causal effects would aid in understanding the mechanics of probability distribution being regularized into a low-dimensional manifold.**\n\n**A1**: We guess you mean the top-K regularizer. To further analyze the effects of Top-K regularizer, we conduct the ablation study with different values of regularizer coefficient $\\lambda$.  The performance results with different $\\lambda$ are shown in Table 4 and the corresponding average  Top-K summations of coreset weights are in Table 5.  In our experiment, there are $50$ candidate samples in each mini-batch data, and the summation of $50$ coreset weights is equal to $1.00$.  Top-K summation of weights increases as $\\lambda$ increases, which imposes higher probabilities on the Top-K entries and lower probabilities on the rest candidates. The best performance is achieved when $\\lambda=0.1$, which means $\\lambda$ balances the trade-off between the loss function and regularizer strength: if $\\lambda$ is too large, the algorithm primarily focuses on choosing the important samples instead of updating the model parameter, and vice versa. \n\n\n**Table 4. Ablation study for the regular coefficient $\\lambda$**\n| Measure | $\\lambda$=0.01 | $\\lambda$=0.05| $\\lambda$=0.1     | $\\lambda$=0.5 | $\\lambda$=1   |\n|-------------|--------------------|-------------------|----------------------|------------------|------------------|\n| ACC       | 59.37±0.35     | 60.23±0.43    | **61.60±0.14**  | 59.42±1.45  | 58.89±1.64   |\n| FGT       | 0.095±0.098   | 0.074±0.054 | **0.051±0.015** |0.138±0.075 | 0.128±0.076 |\n\n**Table 5. TopK summation of coreset weights (K=10)**\n| Measure | $\\lambda$=0.01 | $\\lambda$=0.05 | $\\lambda$=0.1 | $\\lambda$=0.5 | $\\lambda$=1   |\n|-------------|--------------------|--------------------|-------------------|------------------|-----------------|\n| Sum       | 0.41/1.00        | 0.56/1.00        | 0.63/1.00       | 0.73/1.00      | 0.84/1.00    |\n\n\n**Q2: Comparisons with state-of-the-art non-coreset replay methods (e.g., using stability plasticity scores [1], contrastive representation based selection [2]), as it would be meaningful to see the prospect of this direction.**\n\n**[1] Sun et al, Exploring Example Influence in Continual Learning, NeurIPS 2022\n[2] Kim et al, Continual Learning on Noisy Data Streams via Self-Purified Replay, ICCV 2021**\n\n**A2**: We compare two state-of-the-art replay-based methods MetaSP [1] and SPR [2] on Split CIFAR-100, Multiple Datasets, and Tiny-ImageNet. The results are shown in Table 6, 7, and 8 respectively. Our method BCSR outperforms others on balanced, imbalance, and noise settings. In the imbalanced dataset, BCSR demonstrates relatively higher performance.  The reason is that the algorithms in [1] and [2] do not select the most relevant examples in the replay member while our coreset selection method BCSR chooses the most informative samples and saves them into the replay buffer according to the model parameter. \n\n**Table 6. Experiments on Split CIFAR-100**\n| Methods           | Balanced   |             | Imbalanced |             | Label Noise |             |\n|----------------------|---------------|-----------|-----------------|----------|------------------|-----------|\n|                          | AVG ACC |   FGT    | AVG ACC   | FGT     | AVG ACC    | FGT      |\n| MetaSP [1]        | 60.14±0.25 | 0.056±0.23 | 43.74±0.36 | 0.079±0.014 | 57.43±0.54  | 0.086±0.007 |\n| SPR [2]            | 59.56±0.73 | 0.143±0.064 | 44.45±0.55 | 0.086±0.023 | 58.74±0.63  | 0.073±0.010 |\n| BCSR              | **61.60±0.14** | **0.051±0.015** | **47.30±0.57** | **0.022±0.005** | **60.70±0.08**  | **0.059±0.013** |\n\n**Table 7. Experiments on Multiple Datasets**\n| Methods           | Balanced   |             | Imbalanced |             | Label Noise |             |\n|----------------------|---------------|------------|-----------------|----------|------------------|-----------|\n|                          | AVG ACC |   FGT    | AVG ACC   | FGT     | AVG ACC    | FGT      |\n| MetaSP [1]        | 57.14±1.10 | 0.113±0.042 | 41.32±1.50 | 0.103±0.053 | 47.14±1.66  | 0.081±0.027 |\n| SPR [2]            | 56.20±1.91 | 0.124±0.036 | 40.79±1.73 | 0.143±0.051 | 49.77±1.58  | **0.062±0.024** |\n| BCSR              | **59.89±0.95** | **0.096±0.005** | **45.13±0.54** |**0.046±0.008** | **49.97±1.14**  | 0.064±0.031 |\n\n**Table 8. Experiments on Tiny-ImageNet**\n| Methods           | Balanced   |             | Imbalanced |             | Label Noise |             |\n|----------------------|---------------|------------|-----------------|----------|------------------|-----------|\n|                          | AVG ACC |   FGT    | AVG ACC   | FGT     | AVG ACC    | FGT      |\n| MetaSP [1]       | 43.33±0.32 | 0.127±0.002 | 36.75±0.57 | 0.086±0.006 | 37.18±0.76  | 0.068±0.007 |\n| SPR [2]            | 42.79±0.50 | **0.102±0.009** | 36.55±0.74 | 0.070±0.026 | 39.89±0.53  | 0.065±0.021 |\n| BCSR              | **44.13±0.33** | 0.106±0.001 | **38.59±0.11** |**0.047±0.004** | **40.72±0.56**  |**0.055±0.006** |\n\n**Q3: [minor] main illustration Figure 1 could include more technical information (embedding some important eqns for example) or include an additional figure to guide the reader better.**\n\n**A3**: Thank you for your suggestion. We will add a description under the figure in the final version to draw the connection from texts to Equation 1 and pytorch-style pseudocode in Algorithm 1.\n\n\n"}]

Author rebuttal:
**General Response:**

We would like to thank all reviewers for their constructive comments. We have answered the corresponding questions from reviewers and provided new experiment results requested by reviewers. The main summary of our responses includes:

1. Per Reviewer FPqc suggestion:
	- We have added the quantized experiments for models $M_{tr}$ and $M_{cs}$, and compared the performance (ACC and FGT) between quantized models and original models in continual learning. The descriptions of experimental details are included in our response. We show that our quantized models do not lose too much performance but require much smaller memory.

2. Per Reviewer AXy9 suggestion:
      - We have cited and discussed Hessian-free methods, which can be used to improve the efficiency of our method.
	- We have conducted ablation experiments for hyperparameters $N$, $Q$ for sensitivity analysis, and stated the details for $\delta$ setting.  
	- We have explained the main challenges of bilevel optimization analysis in continual learning: 1) bilevel optimization on the constrained case; 2) smoothness of the problem.  

3. Per Reviewer vGFs suggestion:
	- We have clarified the main differences and advantages between our method and Zhou et al. [ref1].

[ref1] Zhou, X., Pi, R., Zhang, W., Lin, Y., Chen, Z., & Zhang, T. (2022, June). Probabilistic bilevel coreset selection. In International Conference on Machine Learning (pp. 27287-27302). PMLR.

4. Per Reviewer b44u suggestion:
	- We have further analyzed the effects of Top-K regularizer and conducted ablation experiments for regular coefficient $\lambda$. 
	- We have added experiments for comparisons with state-of-the-art non-coreset replay methods [ref2] and [ref3]: the results are included in new tables in the rebuttal. 
	- We will add a description under the figure in the final version to draw the connection from texts to equation 1 and pytorch-style pseudocode in Algorithm 1.

[ref2] Sun et al, Exploring Example Influence in Continual Learning, NeurIPS 2022

[ref3] Kim et al, Continual Learning on Noisy Data Streams via Self-Purified Replay, ICCV 2021



Meta-review: The paper proposes a new algorithm for the problem of coreset selection for continual learning. The authors propose a new formulation of the problem, demonstrate a new bi-level optimization procedure for this formulation, and conduct multiple experiments to support their claims.
The reviewers commended the novelty and simplicity of the approach, the use of probability simplex and top-k regularization and the thoroughness of the experiments. During the discussion period, most of the concerns have been addressed. There is consensus among the reviewers that the paper should be accepted. 
After reading the paper, the reviews and the discussions, I feel that this is a solid work and the community will benefit from understanding this result. Thus, I recommend acceptance.
Decision: Accept (poster)