Retaining Knowledge for Learning with Dynamic Definition
Authors: Zichang Liu
Benjamin Coleman
Tianyi Zhang
Anshumali Shrivastava
Venue: NeurIPS 2022 Accept (2022)

Abstract: Machine learning models are often deployed in settings where they must be constantly updated in response to the changes in class definitions while retaining high accuracy on previously learned definitions. A classical use case is fraud detection, where new fraud schemes come one after another. While such an update can be accomplished by re-training on the complete data, the process is inefficient and prevents real-time and on-device learning. On the other hand, efficient methods that incrementally learn from new data often result in the forgetting of previously-learned knowledge. We define this problem as Learning with Dynamic Definition (LDD) and demonstrate that popular models, such as the Vision Transformer and Roberta, exhibit substantial forgetting of past definitions.  We present the first practical 
and provable solution to LDD. Our proposal is a hash-based sparsity model \textit{RIDDLE} that solves evolving definitions by associating samples only to relevant parameters. We prove that our model is a universal function approximator and theoretically bounds the knowledge lost during the update process. On practical tasks with evolving class definition in vision and natural language processing, \textit{RIDDLE} outperforms baselines by up to 30\% on the original dataset while providing competitive accuracy on the update dataset.

Retaining Knowledge for Learning with Dynamic Definition
Zichang Liu Rice University Houston, TX 77025 zi waahhhhnnurrrre edu
Benjamin Coleman
Rice University Houston, TX 77025 brc7@rice.ed edu
Tianyi Zhang Rice University Houston, TX 77025 tz210rice. edu
Anshumali Shrivastava Rice UniversityThirdAAl Corp. Houston, TX 77025 anshumali@rice. edu
Abstract
Machine learning models are often deployed in settings where they must be con- stantly updated response to the changes in class definitions while retaining high accuracy on previously learned definitions. A classical use case is fraud detection, where new fraud schemes come one after another. While such an update can be accomplished by re-training on the complete data, the process is inefficient and prevents real-time and on-device learning. On the other hand, efficient methods that incrementally learn from new data often result in the forgetting of previously- learned knowledge. We define this problem as Learning with Dynamic Definition (LDD) and demonstrate that popular models, such as the Vision Transformer and Roberta, exhibit substantial forgetting past definitions. We present a first prac- tical and provable solution to LDD. Our proposal is hash-base based sparsity model RIDDLE that solves evolving definitions by associating samples only to relevant parameters. We prove that model is universal function approximator and theoretically bounds the knowledge lost during the update process. On practical tasks with evolving class definition in vision and natural language processing, RID) DLE outperforms baselines by up to 30% on the original dataset while providing competitive accuracy the update dataset.
Introduction
Motivation: A common machine learning pipeline is to first define a task objective based on historical experience, then deploy model trained to optimize the objective over collected data. However, machine learning models rarely operate such a static environment. Instead, models must be dynamically updated to accommodate changes in class definitions without forgetting previous knowledge. Consider the case of fraud detection, where models must adapt to emerging scam patterns while also providing protection against previously-known patterns. Machine learning models are also used to identify harmful microbes given gene sequences, where is important to perform well on new variants newly discovered microorganisms. A similar situation arises when models are used to filter inappropriate content such as hate speech and violence. New phrases or previously-innocee language may become inappropriate due to world events or attempts by users circumvent the filter. While the classification task remains the same (fraud or safe, harmful or not, inappropriate or appropriate, etc.). class definitions evolve over time and likely differ significantly from the point of the initial training. We refer to this setting as Learning under Dynamic Definition (L.D). It should be
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

noted that this notion is very different for several other notions of distribution shift in the literature, which we review in the next section.
standard solution is to retrain the model on all available data (original dataset and data for the new definitions). This methodology is inefficient due to data storage and extra computation, and even prohibitive when dealing with large models and streaming data. Furthermore, it prevents real-time and on-device learning. An ideal and efficient solution is to update the trained model incrementally only with data for the new definitions (e.g. using online gradi- ent descent). However, this is a challenging process due to the tendency of machine learning models, in particu- lar neural networks, to forget previous knowledge. This situation, known as collapse/catastrophie forgetting (25] causes performance decay on the old definitions.
0
1
2
3
-0.2
0.3
h(x)
2
0.4
0.9
-01
1.6
3
2
1.2
4.3
-34
-5.2
0.54
Mcan
3
3.2
0.1
0.3
2.1
4
3.4
2.1
0.7
-.9
Catastrophic forgetting occurs because gradient updates from training examples in the update process are able to change parameters that are tuned for optimal performance on the original dataset [EO Inspired by recent connections between random partitions and dis- tribution models [19], we propose RIDDLE (Retaining Information in a Dynamically Defined Learning Environ- ment), a novel architecture with meaningful parameter groupings. RIDDLE works by partitioning the input space and assigning a set of parameters to each partition. Gradient updates are restricted only to locally relevant parameters, identified by cheap hashing computations. RIDDLE can be viewed as a Mixure-of- ofwoooff----aaaaeeeee where the gating function is Locality Sensitive Function (LSH) and each expert is just one number. At the same time, RIDDLE can be viewed as a kernel method where the prediction is an efficient weighted kernel density estimation. RIDDLE can be plugged into diffirent neural network architectures, just like fully connect layers, to ease the memory loss while utilizing the learned features, as shown in Figure 2 We summarize technical contributions below.
Our Proposal:
Figure 1: The figure demonstrates a toy RIDDLE model with L = 5 and R 4. Given an input x, we calculate its hash code h(x)) and access the weights at those locations. We return the average as the output.
We introduce the RIDDLE (in Section 3 consisting of a set of parameters indexed by locality-sensitiv hash functions. RIDDLE computationally efficient and requires less memory than popular machine learning models with similar accuracy.
We prove that RIDDLE is universal function approximator and can therefore represent any function( Section 4 We prove a formal connection between parameter usage and distribution similarity in Theorem 3.2
In Section 5 we apply RIDDLE in the dynamic definition setting for four real-world tasks.
Our method outperforms baselines by up to 30% on the original dataset while achieving competitive accuracy on the new dataset.
2 Related Work
Continual learning refers to learning and remembering multiple tasks from stream of information. Current approaches can be split into three main categories (1) memory replay to complement neural networks 45 2 (2) constraints on network updates BB 28 52).
Continual Learning:
and (3) dynamic architectural adjustments to accommodate new information, such as additional layers 49 61. Recently, few-shot learning methods are also applied into continue learning to solve
sequential learning with limited data 8 5% [ Continual learning methods encounter similar challenges to the ones presented by learning under dynamic distribution, most notably catastrophic forgetting. However, continual learning attempts to solve sequence of related tasks, often expressed as task embeddings, over data that does not necessarily reflect changes in class definitions.
Train-Tess Distribution Shift: Transfer learning and test-time adaptation attempt to remedy mis- alignments between the training and test distribution. Although such methods may seem relevant in learning with dynamic definition, they have dramatically different goals. Transfer learning attempts to

---

adapt a model from a data-rich source domain to data-scarce target domain, without regard for the performance on the source domain 65 56 59 While several works on train-tes test distribution shift focus on robustness, it is from the perspective of -iitof--iitributionn detection [24, 39 or uncertainty estimation 44 R3 57 Our objective is to provide models that perform well on both the original
dataset and new dataset, where class definitions are different, rather than simply detect or adapt to the distribution change.
Online learning regards optimization as process where model is trained by interacting with a stream of data. Online learning algorithms attempt to minimize the regret, or difference between the loss of the predictions by the incrementally -ariile-t model and the loss of the globally optimal model [S 46 Online learning methods attain minimal regret against adaptive adversaries and could be expected to perform well in the dynamic distribution setting, However, the best performing methods for non-convex online learning require retraining over all previous data at every time step 55 making them practically unsuitable for the tasks we consider.
Online Learning:
Locality-Sensitee Hashing in Machine Learning: Locality-sensitive hash (LSH) functions are central component of our proposal. An LSH family is a set of functions that maps similar inputs to the same hash value (with high probability). LSH is an incredibly powerful and well-studied framework, with the following formal definition 27
f
20 4
Definition 2.1 ((So. cSp, Pr. -se-siiiee hash family). family H called (Sy, cSo, Pr, P2)- sensitive with respect to similarity function sim(;,-) if for any two points 2, y E IRd and h chosen uniformly from H satisfies:
* If (1, v) 2 So then Pr(h(x) = h(v)) 2 P1
. If sim(x, y) - cSo then Pr[h(x)= h(v)] P2
The probability Pr(h(x) htv) is known as the collision probability of x: and y, where we use the term "collision" to mean that two points map to the same hash value. For the purpose of our arguments, we stronger notion of LSH, in which the collision probability is monotonic increasing function of the similarity between x and y. That is Pr[h(r) h(y)] x f(sim(æ, y)).
Under the above conditions, the collision probability Pr[h(x)= huy)) forms positive semi-definite radial kernel [9]. A number of useful kernels can be obtained via LSH, including MinHash for the Jaccard kernel 12 signed random projections for the angular kernel [15]. and p-stable LSH for
kernel in Euclidean space (20)-
Recent works have shown that LSH can be used for efficient statistical estimation 5z 14
19 35
36 37
62 compressive machine learning 34 .naaesst neighbor search [5] 7 and to accelerate
neural network training and inference [17
16
32
40
63). A particularly relevant result is the RACE
sketch 1v which solves kernel density estimation using the number of examples that fall into the random partitions induced by LSH function.
3 RIDDLE for Learning with Dynamic Definition
Learning with Dynamic Definition: We formally define the problem as follows.
Definition 3.1. Given model fa: 0) and loss (x 0), v), consider original dataset D
{(af, 3f) drawn i.i.d. from distribution pa and an update dataset D {(x)) y. )== drawn
i..d from distribution Pu, Let do be the parameters that optimize (.) Ep no {[s(;; 0). The dynamic definition learning problem is to find a solution minimizing Lo+u when we are only given access d and D
(o)
Σ {(((x;0)))) + Σ ((((x;)))))
(a.y)ED"
(x.0)ED*
In this paper, we consider the model performance in response the changes from po to Pa specifically by allowing to be drawn from different input spaces. Note that Definition 3.11 generalizes a straightforward way to sequences of dataset updates by considering D to the union all prior data. The difficulty of the problem may be expressed in terms of the Kullback-Leebbler divergence D (Po PP)) Intuitively, small changes in distribution are easier to handle because need not change substantially to perform well on 4
3

---

3.1 Architecture
RIDDLE is 2D parameter array that contains L rows and columns E R The model is indexed by a set of L randomly generated LSH functions h - fl.....A R) E Z for I = -l.... U....L. L. The prediction evaluated a query x defined as following:
f(z; S, Σ S(L,)(())
Algorithmically, the process consists of three steps: (1) hash code computation, (2) partition look-ups, and (3) output averaging. Specifically, the model output for query z is an average over the L illlstrattes toy example.
parameters retrieved from S using the hash codes h(r). Figure D
For classification problem with C' classes, the 2D arra is repeated C' times, resulting in 3D tensor parameters E RCXLRR The same LSH functions are used for all C' repetitions, and the classification prediction for query is defined as follows:
f(x; 5, argmax
L E ((c,1,((()))
RIDDLE can be used as stand alone machine learning model simple datasets but can also be combined with existing neural networks. Specifically, RIDDLE can use the learned representation from neural network (Figure 2). RIDDLE can also be implemented in standard deep learning frameworks and trained using SGD (Algorithm [T. It should be noted that the parameters of LSH functions ((x)) are not trainable. Only the values in S LXL will be updated by SGD. The inference process consists only of inexpensive hash evaluations and memory look-ups. We use LSH functions based on sparse projections (2) which compute h(x) via inner product with parameter vectors randomly drawn from f-1, 0, 1} with probability {1/6, 2/3, 1/6). With such hash function, computation can be reduced to addition, subtraction and memory lookup.
3.2 Intuition
RIDDLE may seem conceptually different from neural networks first gasp, however, RIDDLE can be viewed combination of Eexture-of-Expert-Laayee understand RIDDLE as mixture of experts, observe that the gating function for every row in
[23] with Kernel Methods [26]. To
RIDDLE is randomly initialized hashing function h; and the expert is one number stored at
Sli, (x)). RIDDLE can be viewed as an ensemble of L such Mixture-of--Eppet--aay other side, RIDDLE is also kernel density estimation process where the LSH collision probability the kernel function. The number stored at S(i, hxxx)) an efficient estimation of the weighted kernel values between the test sample and training samples.
3.3 RIDDLE for Learning with Dynamic Definition
Before determine the class of functions that representable using our model, we first demonstrate that this architecture addresses the problem from Definition 3. We consider RIDDLE model f(; S, h) following the notation from Section 3.1 That is. we are given a model with parameters 0 (S, h) trained on D We wish to adapt the model on D using gradient descent.
Parameter Separation: The RIDDLE partitions parameters in such way that inputs from different distributions are likely to use different parameters. The parameter update may be written as:
S = Se((1, noll for 1.. L, where VE
I Σ (1,,(())))))
From this expression, we can see that L parameters are involved in the computation of (a;; S. h) specifically, the parameters selected by the hash functions (h1 (x,) Based on the LSH property (Definition 2. we expect unrelated inputs to have different hash values and therefore use different parameters. When pa is significantly different from po, x. n and D are likely to activate different partition and thus use different parameter sets.

---

Algorithm RIDDLE Training
Input:
Training Dataset D. [D] m, number of rows L, number of cells R, learning rate v, etror function E(-), number of epochs e, batch size b, random seed s.
Output: Trained Model S, Counters C
Initialize: Zero initialize IR 1xx Zero initialize counters C' E R...R, -Randomly generated L independent LSH functions .h.....h. fr. using random seed s;
for i -> do
Shuffle dataset D
for j == 0 m/b 1 do
Take b samples {I,b.- J,b+1..... I 1]1-1 with labels {1rb, M5b+1.... 91j+1)b-11
Compute gradient y = 1 Vs E; (T:s
Apply update S S 119
end for end for
for every E D do
Increase counters C(I, hy(2;)]+ 1 I 1...L end for
We formalize this intuition below by showing that the difference between f(z;; S) and its initializa- tion is bounded by an estimate of the distribution po.
Theorem 3.2. Given a dataset train a RIDDLE model f(x; S,h) by running Algorithm for epochs with learning rate y and initialization So. Suppose the gradient norms are bounded by G. Then
[E; h, f(x; So, h)]l S enG D)
where KDE(2, D) is the kernel density of D using the kernel of the LSH function h.
Theorem 3.2 allows us to prove the following guarantee:
Theorem 3.3. Using the notation from Definition 3.7 let S. be the sketch that optimizes the loss Lo over D and Sotu be the sketch obtained by training D for epochs with learning rate n and initialization So. If the loss L-Lipschitz with G-bounded gradients, then:
En(Co(So+a) - -o. S Σ GLenKDE(z, D")
The loss difference in Theorem 3.3
quantifies the amount of information about D that is forgotten by the model when trained on m The excess loss on example E D is bounded by the kernel density estimate KDE(x, D When D and D" are drawn from different distributions, which is the characteristic of learning under dynamic distribution, the density becomes small (i.e. as the divergence (P' + oo, KDE(2, D*) - 0).
Parameter Importance: The RIDDLE allows us to determine the importance level of each parameter for encoding information from the original distribution with simple counting. We may do this by counting the number of imputs from D that fall into each partition, using set of counters C' E Rxxft Parameters with a large counter e can be regarded as important for the original distribution, as they participate in prediction for a large fraction of examples from D Our intuition is that parameters corresponding to partitions with large count values are critical for performance on D and should not be adjusted. We use this idea to improve performance via partition-depender dependent learning rates. Specifically, we allow the learning rate 7yc) depend on the partition count c. We find that the following update rule provides good empirical results:
é n(c) clog +
where is a constant
RIDDLE is a Universal Function Approximator
In this section, we analyze the class of functions that can represented using the RIDDLE. Using techniques from the sketching literature, we prove probabilistic guarantec.
5

---

Intuition: To see why it is reasonable for our model to be a universal function approximator, observe that the function learned by RIDDLE a piecewise-come consstnt spline function. Splines are incredibly powerful representation that can approximate any function, given sufficient flexibility in choosing the partitions (or knots) of the spline [51] 50] For example, many neural networks can written as compositions of piecewise-linear splines over a constrained set of partitions TC g 30]. In our case, the partition boundaries are determined by the intersection of LSH functions. With sufficient independent overlapping partitions (large L), our model attains a high-quality representation.
We prove that the expected output of our model is universal function approximator, where the expectation is taken over the choice of LSH functions. We begin with proof that any continuous and bounded function can be approximated arbitrarily well by weighted kernel sum over an N point dataset. We then develop a process that constructs RIDDLE S E R R. whose expected output this kernel sum, Using Chernoff bounds, we show that the error between the model and the kernel sum becomes arbitrarily small as I. - oc (with high probability). Taken together, we have probabilistic guarantee for the error between the RIDDLE and any continuous and bounded function.
Proof Sketch:
Simplitied optimization in practice: Constructing a RIDDLE over a carefully chosen N point dataset can approximate any continuous and bounded function. However, learning both the data and data weights with N being arbitrarily large poses difficulty in optimization. We simplify the optimization by observing that the output of the learning process is not dataset but a model. Therefore, we consider the easier task of learning the model parameters values directly in practice as shown in Algorithm This is a slight relaxation of the problem, however, we argue that with row-sum constraint and reasonable uniqueness assumption about the hash partitions, the two processes are equivalent in practice. Thus, the RIDDLE is a universal function approximator.
4.1 Weighted LSH Kernel Sums are Universal Function Approximators
We are interested the representation capabilities of weighted kernel sums over an N N-point dataset D = {=I,...NN J. We consider the specific case where the kernel is the collision probability of an LSH function. Such kernels are referred to in the literature as LSH kernels [9
f(x) Σ ((,,,)))))))))
The crucial property is that LSH kernels are universal. Informally. kernel is universal if a weighted kernel sum over carefully-chosen point set can approximate any function with arbitrary accuracy [2] Some restrictions apply; the size of the point set is allowed to be arbitrarily large and the accuracy is computed over any compact subset of IRd rather than the entire space.
Definition 4.1. Universal Kernel [42]: : Let ((X) denote the space of bounded and continuous functions compact domain X. Then kernel K( y) is universal if it continuous and induces a reproducing kernel Hilbert space that is dense in ((2)).
Applied to our problem, a universal kernel one which can approximate any well-behaved function over compact subsets of Rd using a linear combination of kernels. The theory of universal kernels allows for a convergence-style proof for weighted LSH kernel sums. We begin by showing that the p-stable LSH functions are universal kernels. We defer proofs to the appendix.
Lemma 4.2. The L2 LSH kernel [T] induced by the p-stable LSH function (20) is shift-invariant and universal.
Theorem 4.3. Given a continuous and bounded function g(g) and any 6 0, there exists set of
coefficients (O,n ). set of points {In} and an integer N such that
(w(1) = Σ (exIK(
(Lx(g) - -(g))lx Se
n=1
where K(Inn q) the L.2 LSH kernel and X is any compact subset of Rd.
Rd.
4.2 RIDDLE for Weighted LSH Kernel Sums
The next step of our proof is to construct a RIDDLE capable of approximating SN(g) from Theo- We consider RIDDLE model with S E L constructed from set of points {Ia} with
rem 4.3

---

coefficient {a., in the following way. For every data point E {In we calculate the indices of using a collection of L2 LSH functions hz(2) for / l..... L. Then, we increment the value of S at location (1, (x)) with the weight a. To query the model, we calculate the index of the query g using the same L.SH functions and retrieve the values S(1, (r(g)) for 1 = 1, ..... I, which we aggregate and return. It should be noted that recent algorithms from the sketching literature propose similar constructions I9 [8 but with the weights constrained to an E {+1,- -1}.
One can prove yields sharp unbiased estimator for the weighted kernel sum (Proofs in appendix).
Theorem 4.4 (RIDDLE Estimator). Given a dataset 'D of weighted samples {(a22s) Nz]], let (x) be an LSH function drawn from an LSH family with collision probability K((,,). Let S be 2d parameter array constructed using h(x). For any query 4
D
PD] Σ
B(S(((g)) = Σ az (();;)) var (S(h(a))
&
Oz K(
The key insight is that each row of S is an unbiased estimator for weighted sums of LSH kernels. By finding the central tendency of the L rows, we can obtain a sharp concentration around fv (g). Although we often use the average to do the aggregation in practice, we analyze the median-of-meant estimator 3 [4], as allows us to prove an exponential concentration of the estimate around the weighted KDE. Note that while this simplifies the proof, it does not affect the convergence to fN (q) as oo. We combine the variance bound from Theorem 4.4 with the median-ov -ffiian----mans- guarantee to obtain relationship between the RIDDLE parameters S, weighted kernel values, and estimation error.
Theorem 4.5 (Weighted KDE Estimation Error). Let Z()) be the median-of-means estimate con- structed using the L unbiased estimators. Then with probability 1 6,
fx(9) 6 VL
(Z( fx(() Se e
log 1/8
where fx( and fx (g) are the weighted KDD with kernels K(r, q) and /K(x, q). respectively.
The universal approximation property of our model follows by observing that the error e in Theo- rem 4.5 goes to zero as N and -> in Theorem 4.3 as L
Experiments
In this section, we first evaluate RIDDLE practical dynamic distribution learning task in Sec- tion [. Further, since we prove RIDDLE as a universal function approximator, we provide an extensive study the expressiveness and efficiency of RIDDLE in Section 5.22 Code is available at httss//ffhhbcccom///ccmm///////
5.1 RIDDLE for Learning under Dynamic Definition
Here, we investigate whether RIDDLE can adapt to new distributions while retaining good perfor- mance on the original distributions.
5.1.1 Datasets
We consider four datasets that reflect dynamic distributions. Every dataset is organized into two parts: the original dataset T and the update dataset D D and D have significant semantic differences and do not share any overlapping training data.
We randomly partitioned digits into two groups (e.g. 4, 4,1,7,5,3 and 9, 0, 6, and train the model to predict the group assignment of an image. For the original distribution, we randomly choose digits from the first group and 3 digits from the second group such D only consists images of 4, 1, 7, 9, 0, 8. The update dataset consists of images of the remaining digits.
MNIST Binary:
7

---

Pretrained Model
x
y
(b)
Figure 2: RIDDLE can be used as a stand-alone model, as shown in (a). We use this setting for experiments on MNIST-binary and all experiments studying expressiveness and efficiency. RIDDLE can also be combined with existing neural networks, as shown in (b). We replace the classification layer with RIDDLE for experiments on CIFARIO, ImageNet, and News
The task predict whether the object in the image is capable of carrying things (e.g. car and horse can carry things, while a frog cannot). The original dataset D contains images of out of objects that can and cannot carry things, and the update dataset h contains the remaining 4 objects.
CIFARIO:
The task is to predict whether person is allergic to the object in the image. We select the image classes overlapping with national allergen directetory [1] and assign images to the allergen and non-allergen classes based the common allergen group in national allergen directory [ The original dataset D contains a subset of allergens and non-allergens, while the update dataset D contains the remaining objects. This task built mimic the the seasonal addition and sensitization of new allergens.
ImageNet:
The original task for the News dataset 4 short description. We re-task the dataset to predict whether a person would interested new article by assigning some topics interesting and the rest not-interesing. The original dataset D contains news from subset of interesting and non con-interesting topics, while the update dataset D contains the rest. We organize this dataset reflect changes in user's interests.
News:
predict the news topics given caption and
5.1.2 Baselines
We compare RIDDLE with two updating strategies on different architectures.
We train neural network to full convergence the original dataset D Then, for updating, we train models only on the update dataset D where the initialization the parameters obtained on Do This approach does not require data storage nor training computation over the original dataset.
Update:
Elastic Weight Consolidation(EWCC 3| was proposed to mitigate catastrophic forgetting by se- lectively slowing down learning on the weights important for previous tasks using Fisher information.
5.1.3 Experiment Details
For tasks where it is reasonable (CIFAR1O. ImageNet and News), we exploit recent advances in large scale pretrained models and replace the final layer with RIDDLE. Pretrained models are usually trained on diverse corpus of unlabeled data and are likely to provide good featurization across distributions.
47 also observe that pretrained models are more resistant to forgetting.
5.1.4
Main Results
Table A. summarizes the test accuracy of all models after training on the original dataset and after the update. After training the original dataset, we observe that all models achieve roughly the

---

Trained on original dataset
Updated on update dataset
Dataset
Method
Original
Update
Original
Update
Modate-MLP
99.2
59.1
69.1
98.9
MNIST Binary
EWC-MLP
99.2
59.8
90.9
96.7
RIDDLE
99.2
60.2
98.3
98.0
Boddate-Resntlis
93.3
69.4
63.22
88.9
Update-ViT
93.3
72.6
74.4
92.7
EWC-Resnet
92.0
71.8
75.9
83.9
CIFARIO
EWC-VIT
91.3
75.5
84.5
90.5
RIDDLE
93.0
75.7
89.0
90.9
Update- Update-Resnet18 Resnet18
76.0
45.2
46.53
62.5
Update- VIT
74.3
45.3
55.6
71.5
ImageNet
EWC-Resnet
74.0
46.6
52.8
68.2
EWC-Vi Vit
71.8
41.2
54.5
71.8
RIDDLE
74.3
45.8
67.1
70.5
Update-RoBERTa
96.1
54.8
74.0
85.7
EWC-ROBERTa
96.5
45.5
86.1
87.5
News
RIDDLE
96.6
54.6
89.7
86.4
Table 1: This table summarizes the accuracy after training original dataset, and after training on update dataset. The RIDDLE obtains comparable accuracy on original test set and update test set after trained on corresponding train set. The RIDDLE's accuracy is significantly higher than all baselines on original test set after updating.
same accuracy on original test set. Accuracy on update test dataset is much worse, which is expected since the update distribution significantly different from the original distribution.
We are interested the accuracy on original dataset after updating the model on update dataset. We observe 20% to 30 % accuracy drop the original accuracy with naive updating. Models such as Resnet18 8 and ViT display catastrophic forgetting behavior, eventually performing no better than random. EWC is effective in prevent forgetting some extend, reducing the degradation around 10% to 20%. The RIDDLE significantly outperforms both baselines combined with all architectures datasets up in terms of original test set accuracy. Indeed, the RIDDLE keeps the accuracy degradation below 7 %. For example, the accuracy drop is only 0.9% on Mnist-Binary. On the updated test set, the RIDDLE achieves competitive accuracy (Table A. indicating that is learning the properties of both distributions.
Note that ViT outperforms Resnet18 on both CIFAR10 and ImageNet, which confirms intuition that pretrained models are inherently more robust to distribution changes. By switching the final classification layer to the RIDDLE, we increase the accuracy by a large margin. The experiment results strongly support our hypothesis that the RIDDLE retains the ability to adapt to new distributions while being less vulnerable than established methods to knowledge loss.
5.1.5 Ablation on Update Rule
There are two main drivers of performance when training RIDDLE over dynamically evolving definitions: the hash function and the parameter-deeendennly learning rate.
Without a learning rate that depends on parameter importance, the test accuracy on the original MNIST test set after updating 94.9%. which is 26 % higher than Apdate-MLP, 4 % higher than EWC-MLP. Using the dynamic learning rate, RIDDLE achieves 98%. There could be smarter or simpler update functions based the parameter count, which we leave for future work.
MLP
Global Learning Rate n(c) O clog c+1
Test accuracy on original
69.1
94.9
98.3
Table 2: This table displays the effect of the partition-dependen learning rate. "Global Learning Rate" means that the learning rate is not related to parameter counts.

---

Dataset
LightGBM
Random Forest
XGBoost
NNI
NN2
RIDDLE
Susy
0.7903
0.7880
0.7926
0.8019
0.8024
0.7924
HAR
0.8532
0.8387
0.8532
0.9027
0.9123
0.9001
Covtype
0.9565
0.9932
0.9874
0.9836
0.9936
0.9853
Connect4
0.8171
0.8335
0.8171
0.8558
0,8657
0.8586
Fashion MNIST 0.8848
0.8777
0.8848
0.8852
0.8889
0.8852
Boston Housing
1.77
2.05
1.62
2.57
2.16
1.74
Table 3: This table summarizes the accuracy comparison. NNI and NN2 denote two different deep
learning models. RIDDLE achieves higher accuracy than at least half of the baselines on all datasets.
Dataset
Method
Accuracy
Memory(MBi
Flops (M)
Inference Time (us)
NN
0.9815
3.59
01.90
164.177
MNIST
RS
0.9784
1.36(1.6X)
0.15(6.1X)
42.003 (3.9X)
NN
0.8852
2.59
0.65
13 131.385
Fashion MNIST
RS
0.8852
1.92(I.6X)
0.13(5X)
39 39.228 (3.3X)
NN
0.9027
2.11
0.53
166.584
HAR
RS
0.9001
L.1((18X)
0.18 (2.9X)
46.567 (3.6X)
NN
2.16
1.96
0.51
61.338
Boston Housing
RS
1.74
0.53(3.7X)
0.03 (17X)
21 31.862 (2.8X)
Table 4: This table summarizes the efficiency comparison between the RIDDLE and a neural network (NN) with similar accuracy. The RIDDLE reduces memory by up 3.7x, FLOPs by up to 17x and inference time by up to 3.9x.
5.2 Study on Expressiveness and Efficiency
In this section, we investigate whether RIDDLE is competitive among popular machine learning models terms of expressiveness and efficiency. Our goal is show that RIDDLE provides good model representation for a variety of tasks. We curated a diverse set of datasets from UCI and Kaggle. These datasets cover wide range of tasks and domains and are widely used as benchmarks in other works 664 [22] All experiments are conducted on machine with 96 www.e/eetteree//eee----- processors (Intel Xeon(R) Gold 5220R 2.20GHz) and 8 Nvidia V100 32GB.
In Table 5.2 we observe that RIDDLE outperforms popular linear methods and is competitive compared deep learning methods. NNI and NN2 denote different neural network architec- (Detailss in Appendix). Both the architecture and evaluation metric is included in Table A.2 We also investigate the efficiency and memory requirement. This important, shows that RIDDLE does not outperform other methods due to an increased parameter size. Table shows that RIDDLE attains the same accuracy as baseline methods with smaller memory footprint, fewer FLOPs and faster inference speed. Specifically, we use up to 3.7X less memory, use 17X less FLOPs, and achieve 3.9x faster inference speed. The memory improvements likely arise from the meaningful parameter groupings, while the computational improvements are because it only uses addition, subtraction and array lookup operations. This experiment confirms that even though RIDDLE allocates different parameters to different distributions, we do not require more parameters than existing methods to achieve robustness or accuracy. One limitation now is that memory grows linear with number of class, which can be address with smart hashing mechanism.
6 Conclusion
In this work, we propose an expressive and efficient model RIDDLE for learning under dynamic distribution. Our setup concerns common scenarios where model has be updated given distribution changes. The model is structured to invulnerable to forgetting because gradients updates are naturally restricted only input relevant parameters. Further, RIDDLE can be used for efficient weighted kernel density estimation.
Acknowledgments
This work supported by National Science Foundation SHF-2211815, HGGDATA-1838177 ONR DURIP Grant, and grants from Adobe, Intel, Total, and VMware.
10

---

References
[1] Asthma and allergies foundation of america, http://www.aaf..oogyysssssssssss
[2] Dimitris Achlioptas. Database-friendly random projections: Johnssn--indenstrauss with binary coins. Journal of Computer and System Sciences, 66(4):671-66 2003. Special Issue on PODS 2001.
[3] Noga Alon, Yossi Matias, and Mario Szegedy, The space complexity of approximating the frequency moments. Journal of Computer and system sciences, 58(1):137-147, 1999.
[4] Alexandr Andoni, Piotr Indyk, TMM Laarhoven, Ilya Razenshteyn, and Ludwig Schmidt. Practical and optimal Ish for angular distance. In Advances in Neural Information Processing Systems (NIPS), pages 1225-1233 Curran Associates, 2015.
[5] Alexandr Andoni, Piotr Indyk, Huy L Nguyen, and Ilya Razenshteyn. Beyond locality-sensitive hashing. In Proceedings of the twenty-fifth annual ACM-SIAM symposium Discrete algo- rithms, pages 1018-1028. SIAM, 2014.
[6] Alexandr Andoni, Thijs Laarhoven, Ilya Razenshteyn, and Erik Waingarten. Optimal hashing- based time-space trade-offss for approximate near neighbors. In Proceedings of the Twenty-Eigha Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 47-66 SIAM, 2017.
[7] Alexandr Andoni and Ilya Razenshteyn. Optimal data-dependent hashing for approximate near neighhors. In Proceedings of the forly-seventh annual ACM symposium on Theory of computing, pages 793-801, 2015.
[8] Antreas Antoniou, Massimiliano Patacchiola, Mateusz Ochal, and Amos Storkey. Defining benchmarks for continual few-shot learning, 2020.
[9] Randall Balestriero and Richard G. Baraniuk. Mad max: Affine spline insights into deep learning. Proceedings of the IEEE, (19(5)7044727,2022
[10] Randall Balestriero, Romain Cosentino, Herve Glotin, and Richard Baraniuk. Spline filters for end-to-end deep learning. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 364-373. PMLR, 10-15 Jul 2018.
[11] Randall Balestriero and richard baraniuk. A spline theory of deep learning. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 374-383. PMLR, 10-15 Jul 2018
[12] A. Broder. On the resemblance and containment of documents. In Proceedings of the Com- pression and Complexity of Sequences 1997, SEQUENCES '97, page 21, USA, 1997. IEEE Computer Society.
[13] Claudio Carmeli, Ernesto De Vito, Alessandro Toigo, and Veronica Umanitá. Vector valued reproducing kernel hilbert spaces and universality. Analysis and Applications, 1901):19-61, 2010.
[14] Moses Charikar and Paris Siminelakis. besshin-bbase-esttnane for kernel density in high dimensions. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 1032-1043. IEEE, 2017.
[15] Moses S. Charikar. Similarity estimation techniques from rounding algorithms. In Proceedings of the Thiry- Foury-Fuuthhaoo Annual ACM Symposium on Theory of Computing, STOC '02, page 380-388, New York. NY, USA, 2002. Association for Computing Machinery.
[16] Beidi Chen, Zichang Liu, Binghui Peng, Zhaozhuo Xu, Jonathan Lingjie Li, Tri Dao, Zhao Song, Anshumali Shrivastava, and Christopher Re. (MONGOOSE]): A learnable (Ish) framework for efficient neural network training. International Conference on Learning Representations, 2021.

---

[17] Beidi Chen, Tharun Medini, and Anshumali Shrivastava. SLIDE: In defense of smart algorithms over hardware acceleration for large- sarge deep learning systems. CoRR, abs//903.cm 000.0312,, 2019.
[18] Benjamin Coleman, Richard Baraniuk, and Anshumali Shrivastava. Sub-linear memory sketches for near neighbor search on streaming data. In International Conference on Machine Learning, pages
PMLR, 2020.
[19] Benjamin Coleman and Anshumali Shrivastava. Sub-Linear RACE Sketches for Approximate Kernel Density Estimation on Streaming Data, page 1739-1749. Association for Computing Machinery, New York, NY, USA, 2020.
[20] Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S. Mirrokni. Locality hashing scheme based on p-stable distributions. In Proceedings of the Twentieth Annual Symposium on Computational Geometry, SCG '04, page 253-262, New York, NY, USA, 2004. Association for Computing Machinery.
[21] Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S Mirrokni. Locality-sensitive hashing scheme based on p-stable distributions. In Proceedings of the twentieth annual symposium Computational geometry, pages 253-262, 2004.
[22] Nick Frickson, Jonas Mueller, Alexander Shirkov, Hang Zhang, Pedro Larroy, Mu Li, and Alexander Smola. Autogluon-tabular: Robust and accurate automl for structured data, 2020.
[23] William Fedus, Jeff Dean, and Barret Zoph. review of sparse expert models in deep learning. 2022.
[24] Stanislav Fort, Jie Ren, and Balaji Lakshminarayanan. Exploring the limits of out-of-distribution detection. CoRR,
2021.
[25] Ian J. Goodfellow, Mehdi Mirza, Da Xiao, Aaron Courville, and Yoshua Bengio. An empirical investigation of catastrophic forgetting in muudient-based neural networks, 2013.
[26] Thomas Hofmann, Bernhard Schölkopf, and Alexander J. Smola. Kernel methods in machine learning. The Annals of Statistics, 36(3), jun 2008.
[27] Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: Towards removing the curse of dimensionality. Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing. STOC '98, page 604-613, New York, NY, USA, 1998. Association for Computing Machinery.
[28] Heechul Jung. Jeongwoo Ju, Minju Jung, and Junmo Kim. Less-forgetting learning in deep neural networks. arXiv preprint arXiv:1607.00122. 2016.
[29] Nitin Kamra, Umang Gupta, and Yan Liu. Deep generative dual memory network for continual learning. arXiv preprint arXiv: 1016. 2017.
[30] James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei A Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Overcoming catastrophic forgetting in neural networks. Proceedings of the national academy of sciences, 1 (14(13):3521-355 33266 2017
et al.
[31] James Kirkpatrick, Razvan Pascanu, Neil C. Rabinowitz, Joel Veness, Guillaume Desjardins, An- Demis
drei A. Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Hassabis, Claudia Clopath, Dharshan Kumaran, and Raia Hadsell. Overcoming catastrophic forgetting in neural networks. CoRR, abs/1612.00796. 2016.
[32] Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer, 2020.
[33] Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. Advances in neural information processing systems, 30, 2017.
[34] Xiaoyun Li and Ping Li. Generalization error analysis of quantized compressive learning. Advances in Neural Information Processing Systems, 32, 2019.
12

---

[35] Xiaoyun Li and Ping Li. Random projections with asymmetric quantization. Advances in Neural Information Processing Systems, 32, 2019.
[36] Xiaoyun Li and Ping Li. Quantization algorithms for random fourier features. In International Conference Machine Learning, pages 6369-6380. PMLR, 2021.
[37] Xiaoyun Li and Ping Li. Quantization algorithms for random fourier features. In International Conference on Machine Learning, pages 6369-6380. PMLR, 2021.
[38] Zhizhong Li and Derek Hoiem. Learning without forgetting. IEEE transactions on pattern analysis and machine intelligence, 40(11):2235 2944779777977 2017.
[39] Shiyu Liang, Yixuan Li, and R. Srikant. Principled detection of out-of- distriibtin examples in neural networks. CoRR, htss1706.02690, 2017.
[40] Zichang Liu, Zhaozhuo Xu, Alan Baonan Ji, Jonathan Li, Beidi Chen, and Anshumali Shrivas- tava. Climbing the WOL: training for cheaper inference. CoRR, abs/2007.01230, 2020.
[41] Chen Luo and Anshumali Shrivastava. Arrays of (locality-sensitive) count estimators (ace): Anomaly detection on the edge. Proceedings of the 2018 World Wide Web Conference, WWW 18, page 1439-144800 1448. Republic and Canton of Geneva, CHE, 2018. International World Wide Web Conferences Steering Committee.
Journal of Machine [42] Charles A Micchelli, Yuesheng Xu, and Haizhang Zhang. Universal Journal Learning Research, 7(12). 2006.
[43] Rishabh Misra. News category dataset, 2022.
[44] Yaniv Ovadia, Emily Fertig, Jie Ren, Zachary Nado, David Sculley, Sebastian Nowozin, Joshua Dillon, Balaji Lakshminarayanan, and Jasper Snoek. Can you trust your model's uncertainty? evaluating predictive uncertainty under dataset shift. Advances in neural information processing systems, 32, 2019.
[45] German I Parisi, Jun Tani, Cornelius Weber, and Stefan Wermter. Lifelong learning of spatiotem- poral representations with qual-memory recurrent self-organization. Frontiers in neurorobotics, page 78, 2018
[46] Sebastian Pokutta and Huan Xu. Adversaries in online learning revisited: with applications in robust optimization and adversarial training. CoRR, abs/2101. 11443, 2021.
[47] Vinay Venkatesh Ramasesh, Aitor Lewkowyez, and Ethan Dyer. Effect of scale on catastrophic forgetting in neural networks. In International Conference on Learning Representations, 2022.
[48] Alon Resler and Yishay Mansour. Adversarial online learning with noise. abs/1810.09346,, 2018
CoRR,
[49] Andrei A Rusu, Neil C Rabinowitz, Guillaume Desjardins, Hubert Soyer, James Kirkpatrick, Koray Kavukcuoglu, Razvan Pascanu, and Raia Hadsell. Progressive neural networks. arXiv preprint arXiv: (66600661.11. 2016.
[50] Jürgen Schmidhuber. Discovering problem solutions with low kolmogorov complexity and high generalization capability. Technical report, MACHINE LEARNING: PROCHEDINGS OF THE TWELFTH INTERNATIONAL CONFERENCE, 1994.
[51] Isaac J Schoenberg. Contributions to the problem of approximation of equidistant data by analytic functions. In IJ Schoenberg Selected Papers, pages 3-57. Springer, 1988.
[52] Joan Serra, Didac Suris, Marius Miron, and Alexandros Karatzoglou. Overcoming catastrophic forgetting with hard attention to the task. In International Conference on Machine Learning. pages 4548-4557 PMLR, 2018
[53] Jake Snell, Kevin Swersky, and Richard Zemel. Prototypical networks for few-shot learning. In Proceedings of the 3/ International Conference on Neural Information Processing Systems, NIPS' 17, page 4080-4090, Red Hook, NY, USA, 2017. Curran Associates Inc
13

---

[54] Ryan Spring and Anshumali Shrivastava. A new unbiased and efficient class of Ish ish-based samplers and estimators for partition function computation in log-linear models, 2017.
[55] Arun Sai Suggala and Praneeth Netrapalli. Online non-convex learning: Following the perturbed leader is optimal. CoRR, abs/ 1903.090000000 10, 2019.
[56] Yu Sun, Xiaolong Wang, Zhuang Liu, John Miller, Alexei A. Efros, and Moritz Hardt. Test-time training with self-supervision for generalization under distribution shifts, 2020.
[57] Joost Van Amersfoort, Lewis Smith, Yee Whye Teh, and Yarin Gal. Uncertainty estimation using single deep deterministic neural network. In International conference on machine learning, pages 9690-9700. PMLR, 2020.
[58] Oriol Vinyals, Charles Blundell, Tim Lillicrap. Koray Kavukcuoglu, and Daan Wierstra. Match- ing networks for one shot learning. In NIPS, pages 3630-3638, 2016.
[59] Dequan Wang, Evan Shelhamer, Shaoteng Liu, Bruno Olshausen, and Trevor Darrell. Tent: Fully test-time adaptation by entropy minimization, 2021.
[60] Zichao Wang, Randall Balestriero, and Richard Baraniuk. A MAX-AFFINE SPLINE PERSPEC- TIVE OF RECURRENT NEURAL NETWORKS. In International Conference on Learning Representations, 2019.
[61] Jachong Yoon, Eunho Yang, Jeongtae Lee, and Sung Ju Hwang. Lifelong learning with dynamically expandable networks. arXiv preprint arXiv:1708.01547 2017.
[62] Amir Zandieh, Navid Nouri, Ameya Velingker, Michael Kapralov, and llya Razenshteyn. Scaling up kernel ridge regression via locality sensitive hashing. International Conference on Artificial Intelligence and Statistics, pages 4088 PMLR, 2020.
[63] Minjia Zhang, Xiaodong Liu, Wenhan Wang, Jianfeng Gao, and Yuxiong He. Navigating with graph representations for fast and scalable decoding of neural language models. arXiv preprint 1xXi::1006.0489, 2018.
[64] Zhi-Hua Zhou and Ji Feng. Deep forest: Towards an alternative deep neural networks. CoRR, abs/1702.08835, 2017.
[65] Fuzhen Zhuang, Zhiyuan Qi, Keyu Duan, Dongbo Xi, Yongchun Zhu, Hengshu Zhu, Hui Xiong. and Qing He. A comprehensive survey on transfer learning. Proceedings of the IEEE, 109(1):43-76, 2020.
14

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [No]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "zAPaTuQLbcU", "reviewer": "Reviewer_gwhJ", "summary": "- This paper proposes RIDDLE, a model with novel parameters grouping strategy, to tackle the catastrophic forgetting problem. In this paper, the catastrophic forgetting problem is formulated as the data distribution deviations between the original and the new tasks. RIDDLE helps solve this problem by preserving the parameters that are mostly responsible for the original tasks. To be specific, RIDDLE leverages the local sensitive hash (LSH) function to map inputs to various indexes of a trainable matrix; its corresponding values are then averaged as the output of the model. Therefore, for different data distributions, LSH maps them to various indexes and utilizes the parameters from the different parts of the trainable array. Catastrophic forgetting is then prevented when the parameters responsible for original tasks are preserved. This paper theoretically shows RIDDLE can represent a large set of functions, and experimentally demonstrate how it mitigates catastrophic forgetting.\n\n- Contributions: (a) This paper proposes a novel parameters grouping strategy. (b) This paper demonstrates the proposed framework can be used for various functions. (c) This paper shows RIDDLE is effective in multiple experiments.", "questions": "Based on the previous potential weakness, the questions are summarized as follows:\n\n- The parameters updating rule: \n(1) When \\alpha is changing, would the model performance vary largely on original and new tasks? And would we need to search \\alpha for different tasks, or it is robust to most tasks? \n(2) Is this the only effective learning rate updating rule? The current updating rule seems complicated and less intuitive, and there can be some easier updating rules. For example, a simple updating rule can be using a pre-defined counting threshold $c_0$, where the parameters with frequency $c$ greater than $c_0$ will not be updated. How about the performance of those easier updating rules?\n\n- Comparisons with other methods (e.g. EWC from Overcoming catastrophic forgetting in neural networks, and CPG from Compacting, Picking and Growing for Unforgetting Continual Learning) to prevent catastrophic forgetting: Does RIDDLE demonstrate advantages over other meta-learning methods (in terms of original /new task accuracy, efficiency, etc.)?\n\n- Why only the last layer is replaced by RIDDLE? Specifically, what would be the performance and efficiency when the intermediate layers are also replaced by RIDDLE?", "limitations": "Yes. The authors have pointed out the potential limitation, and I agree with the authors that this work poses minimal negative social impact.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The idea of using different groups of parameters to tackle catastrophic forgetting is novel and reasonable. \n- The authors demonstrate RIDDLE can be used for multiple functions and multiple tasks. This means RIDDLE can potentially be a general way to solve catastrophic forgetting for many tasks in various scenarios, which could have a significant impact.\n\n\nWeakness:\n- Lack of discussion on how to determine the responsible parameters. Between lines 157 and 158, the authors discuss that frequently used parameters in original tasks should be responsible for the tasks and should not be updated, and the authors propose a soft learning rate to prevent these parameters from overly updating. The proposed updating rule seems complex and is influenced by hyperparameter \\alpha. How does the updating rule influence the performance in the experiment sections?\n\n- Lack of comparisons with other methods to prevent catastrophic forgetting. There are also other methods that effectively prevent catastrophic forgetting, while the authors do not compare with them. Instead, the authors just compare with the pre-trained models. Does RIDDLE demonstrate advantages over other methods that prevent forgetting (in terms of original /new task accuracy, efficiency, etc.)?\nA comparison with other methods (e.g. EWC from Overcoming catastrophic forgetting in neural networks, and CPG from Compacting, Picking and Growing for Unforgetting Continual Learning) could make this work more solid.\n\n- Lack of reasoning on replacing the last layer with RIDDLE. In the experiments, the last layer of models is replaced by RIDDLE framework. Why only the last layer is chosen? For example, RIDDLE can also be applied in the intermediate part of the model to connect two concatenate layers.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ybJuvdI1Ms", "reviewer": "Reviewer_qrRt", "summary": "The authors propose a new model type, that they name RIDDLE, that they claim is a universal function approximator, and can outperform the performance of popular existing neural networks such as ViT and RoBERTa when it comes to catastrophic forgetting when learning on a new task. \n\nRIDDLE consists of a number of hash functions applied to the input sample, which then are aggregated as a means to choose a parameter partition to be used for the data point at hand. They claim that the hash functions are selected such that more similar data distributions are clustered together. \n\nThey benchmark their models against a number of neural networks and more traditional linear models and show that their model exceeds most models both on the source dataset and the update dataset accuracy.", "questions": "1. How does your model compare with neural network based methods that selectively choose what parameters to update, such as elastic weight consolidation, or literally using Fischer information or the gradients wrt loss as a means of generating a mask for what weights to update? There are douzens of continual learning methods that work in similar principles and at least some should be compared with your method.\n2. What is the optimizer and hyperparameters used? What about other training details like number of iterations and data augmentation strategies, as well as any regularization methods applied on the source and update dataset. The effect of these can be astounding. \n3. Figure: What accuracy is shown on the y axis? Test set of original dataset? Or training set?\n", "limitations": "I have already stated technical limitations, but have not noticed any negative societal impact potential from this work.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality:\nThe idea itself seems quite novel, and puts a spin on the modern trends towards neural networks. It would be nice to see combinations of RIDDLE and existing NNs. \n\nQuality:\nThe quality of the writing itself is fair, but the clarity of the descriptions/figures that try to distil the model ideas are hard to parse and interpret. I'd recommend taking the time to rewrite those sections more clearly and to make better figures. Figures directly comparing RIDDLE to known models structurally would be a nice way to help readers transfer their existing knowledge on to RIDDLE.\n\nThe experimental quality is problematic, as it is lacking both in terms of reporting means and standard deviations over a variety of runs, and clearly stating the metrics reported. From line 269 I can guess that the accuracies reported are on the test set, but it should be stated more explicitly, as given the target problem and the novelty of the model, one could easily assume that the authors also compared training speeds etc somewhere and thus training accuracies would also make sense. More importantly, since RIDDLE is essentially a continual learning method that uses its own selective update mechanism, it would only be fair to compare RIDDLE with other existing selective update methods for NNs, elastic weight consolitation, usage of Fischer information as a way to select what parameters to update etc, to name a few, as well as the more classic ProtoNets, Matching Networks. There are also methods that combine static backbones and inner loop updateable components such as Self Critique and Adapt. Without any of these comparisons it's hard to know whether the work is significant in any way. \n\n\nClarity: \n\nWriting is overall OK but is also often clumsy in usage of acronyms such as CIFAR as Cifar, MNIST as Mnist -- more importantly: **The paper underplays the fact that RIDDLE is in fact using a large scale pretrained neural network as its backbone, using RIDDLE only in its last layers. ** I had to dig to find this, and found it at lines 243-246. Please make that more explicit, and rephrase writing that tries to make RIDDLE appear as something other than a neural network. I would be very keen to see how a fully RIDDLE'd model would perform when pretrained on the same dataset as the neural networks were that you used. \n\nAlso, there are no information on what optimizers and other such experimental hyperparameters mentioned. In my own work I have seen stark performance differences when fine tuning ViTs when the learning rate is not small enough. I suspect, based on the patterns in the figures of this paper that the learning rate was arbitrarily chosen or not received enough attention. \n\n\n\n\nSignificance: \n\nThe work can be significant for a continual learning context, but this is hard to tell as no comparisons were made with a lot of existing continual learning methods. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "pYo3sgJnm6z", "reviewer": "Reviewer_u21g", "summary": "The paper tackles the problem of learning from new data without forgetting previously known knowledge. The authors term it Learning with Dynamic Definition (LDD). The proposed method is to hash the input and use the bucketing to associate it with the set of parameters used on it. The idea is that similar inputs will have similar associated parameters due to the hashing, so updates generated due to new inputs will likely not affect the irrelevant parameters much, thus preserving the knowledge. The authors prove that the model is a universal function approximator and theoretically bounds the knowledge lost. On many CV and NLP tasks, the authors find the method does better at retaining knowledge after the update process as evidenced by performance on the original dataset whilst also performing competitively on the new dataset. \n", "questions": "- have you explored any big datasets, how does the tradeoff for memory vs performance look like for bigger datasets?", "limitations": "- Limitations have already been properly/adequately addressed. ", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": " Strength:\n- Relatively simple approach with good results.\n- Comprehensive description of each section, well written.\n- Results section and graphs are significantly impressive.\n\nWeakness:\n- I might be biased, but felt too reliant on LSH doing a good job?\n- Are the scores or gains statistically significant across multiple runs?\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "TQ6obTeT64", "reviewer": "Reviewer_X2yQ", "summary": "This paper formally defines the Learning with Dynamic Definition (LDD) problem and proposes an efficient solution, RIDDLE, to LDD. RIDDLE exploits locality-sensitive hash functions and works by assigning different sets of parameters to distinct inputs. The authors prove that RIDDLE is a universal function approximater. Theoretical analysis together with experiments on vision and NLP tasks demonstrate that RIDDLE can effectively alleviate catastrophic forgetting while achieving comparable performance with standard baseline models.", "questions": "\n1. In RIDDLE \"similar\" input data to use similar parameters in $S$.  This information is captured by the Counters $C$. It would be interesting to illustrate the $C$ matrix to see the pattern for different tasks. The pattern can help to show, for example, how much the update data differ from the original ones.\n2. How would different hash functions affect RIDDLE?\n3. What is the similarity function corresponding to the LSH function in use in RIDDLE?\n4. It would be desirable to see how RIDDLE performs on normal classification tasks?\n5. It would be desirable to include an ablation study to see, for example, how do $R$ and $L$ affect RIDDLE? Does the performance critically depend on the use of the dynamic learning rate $\\eta(c)$?\n6.  According to my understanding, RIDDLE can be dynamically extended, is this correct? For example, given a trained RIDDLE, one can increase $L$ and $R$ by smartly choosing a new hash function.\n\n", "limitations": "The paper briefly mentions a limitation of memory usage of RIDDLE (line 300). As far as I am concerned, the limitations also include\n* a lack of ablation study.\n* no experiment on standard classification tasks.\n* no discussion about the similarity function corresponding to the LSH function used in RIDDLE.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The central topic, i.e., alleviating catastrophic forgetting, is a crucial problem that must be resolved for the realization of Artificial General Intelligence (AGI).\n2. The proposed RIDDLE model is novel, efficient, and elegant. In addition, RIDDLE may be viewed as a self-contained module that can be used together with other SOTA models.\n3. Both theoretical and empirical studies are included to demonstrate the effectiveness of the proposed model.\n4. The paper is generally well-written and easy to follow.\n\nWeaknesses:\n1. Missing discussion about the similarity function associated with the LSH functions in use, i.e., sparse projection-based LSH functions. Is K-L divergence the similarity function?\n2. Experiments only include deliberately designed tasks, e.g., predicting whether a person is allergic to the object in the image on the ImageNet dataset, rather than the standard classification task.\n3. Missing ablation study, for example, how do $L$ and $R$ affect the RIDDLE model?\n4. Some symbols are confusing, for example: between lines 157 and 158, what does $\\bar{c}$ mean in the formula for dynamic learning rate? and symbol $f_{S,h}(x_i)$ in Algorithm 1 is not explicitly defined.\n5. The description of experiment settings needs to be more clear. For example, according to the code, the pretrained models, e.g., ViT, are frozen during training. However, this is not mentioned in the main text; and It is not clear whether all the experiments are conducted using the dynamic learning rate.\n6. Several references to tables should be corrected, for example, Table 5.1 should be Table 1 (lines 264 and 275); and in line 291 it refers to Table 4 without mentioning that this table is in the supplementary material. \n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept