lpNTK: Better Generalisation with Less Data via Sample Interaction During Learning
Authors: Shangmin Guo
Yi Ren
Stefano V Albrecht
Kenny Smith
Venue: ICLR 2024 poster (2024)
Keywords: generalisation
data selection
neural tangent kernel
sample interaction
learning dynamics
Primary area: learning theory
TL;DR: We study the sample relationships emerged during the learning of deep neural networks.

Abstract: Although much research has been done on proposing new models or loss functions to improve the generalisation of artificial neural networks (ANNs), less attention has been directed to the impact of the training data on generalisation. In this work, we start from approximating the interaction between samples, i.e. how learning one sample would modify the model's prediction on other samples. Through analysing the terms involved in weight updates in supervised learning, we find that labels influence the interaction between samples. Therefore, we propose the labelled pseudo Neural Tangent Kernel (lpNTK) which takes label information into consideration when measuring the interactions between samples. We first prove that lpNTK asymptotically converges to the empirical neural tangent kernel in terms of the Frobenius norm under certain assumptions. Secondly, we illustrate how lpNTK helps to understand learning phenomena identified in previous work, specifically the learning difficulty of samples and forgetting events during learning. Moreover, we also show that using lpNTK to identify and remove poisoning training samples does not hurt the generalisation performance of ANNs.

Published as a conference paper at ICLR 2024
LPNTK: BETTER GENERALISATION WITH LESS DATA VIA SAMPLE INTERACTION DURING LEARNING
Shangmin Guo', Yi Ren', Stefano V. Albrecht', Kenny Smith' ' University of Edinburgh, University of British Columbia,
ABSTRACT
Although much research has been done on proposing new models or loss functions to improve the generalisation of artificial neural networks (ANNs), less attention has been directed to the impact of the training data generalisation. In this work, we start from approximating the interaction between samples, i.e. how learn- ing one sample would modify the model's prediction other samples. Through analysing the terms involved in weight updates in supervised learning, we find that labels influence the interaction between samples. Therefore, we propose the labelled pseudo Neural Tangent Kernel (IpNTK) which takes label information into consideration when measuring the interactions between samples. We first prove that IpNTK asymptotically converges to the empirical neural tangent kernel in terms of the Frobenius norm under certain assumptions. Secondly, we illustrate how IpNTK helps to understand learning phenomena identified in previous work, specifically the learning difficulty of samples and forgetting events during learn- ing. Moreover, we also show that using IpNTK to identify and remove poisoning training samples does not hurt the generalisation performance of ANNs.
INTRODUCTION
In the past decade, artificial neural networks (ANNs) have achieved great successes with the help of large models and very large datasets (Silver et al. 2016 Krizhevsky et al. 2017:; Vaswani et al, 2017). There usually three components involved in training ANN: the model, i.c. the ANN itself: a loss function; and a dataset, usually labelled for supervised learning. Previous work has shown that generalisation performance can be boosted by changing the model architecture, e.g- ResNet (He et al. 2016) and ViT (Dosovitskiy et al. (2000;; or introducing new loss functions, e.g. focal loss (Lin al.) 2017) and regularisation (Goodfellow
al. 2016). Researchers have also explored methods that allow models to choose data, e.g. active learning (Settles) 2012), to improve generalisation performance and reduce laborious data annotation. In this work, we focus on selecting data in order to achieve better generalisation performance.
Although the training samples are usually assumed to be independent and identically dis- tributed (i.i.d, Goodfellow et al., 2016), ANNs do not learn the samples independently. as the pa- rameter update on one labelled sample will influence the predictions for many other samples. This dependency is double-edged sword. On the plus side, the dependency between seen and unseen samples makes it possible for ANNs to output reliable predictions on held-out data (Koh & Liang. 2017). However, dependencies between samples ct al. 2017). D, i.c. updates on a sample appearing later might crase the correct predictions for previous samples. Hence, argue that it is necessary to investigate the relationships between samples in or- der to understand how data selection affects the learning, and further how to improve generalisation performance through manipulating data.
also cause catastrophic forgetting (Kirkpatrick
We first decompose the learning dynamics of ANN models in classification tasks, and show that the interactions between training samples be well-captured by combining the empirical neural tangent kernel (eNTK Jacot et al., (2018) with label information. We thus propose a scalar sample similarity metric that measures the influence of an update on one sample to the prediction on another, called labelled pseudo NTK (IpNTK), which extends pseudo NTK (Mohamadi & Sutherland, 2022
Correspondence author: gungedd.cco acceedddc...

---

Published as a conference paper at ICLR 2024
PNTK) by incorporating the label information. As shown in Section 2.3 our IpNTK can be viewed as a linear kernel on a feature space representing each sample as a vector derived from the lpNTK. point out that
Since the inner product of high nigh-dimensional vectors can be positive/negative/zene there are three types of relationships between a pair of samples: interchangeable, unrelated, and contradictory. Following the analysis of inner products between lpNTK representations, that a sample can be considered as redundant if its largest inner product is not with itself, i.c. it can be removed without reducing the trained ANNs' generalisation performance. Moreover, through experiments, we verify that two concepts from previous work can be connected to and explained by the above three types of relationships: the learning difficulty of data discussed by |Paul et al. (2021), and the forgetting events during ANN learning found by Toneva et al. (2018). Furthermore, inspired by the discussion about the connections between learning difficulty and generalisation from [Sorscher et al. (2022), we show that the generalisation performance of trained ANNs is not influenced, and can be potentially improved, by removing part of the samples in the largest cluster obtained through farthest point clustering (FPC) with IpNTK as the similarity metric.
find
In summary, we make three contributions in this work: 1) we introduce a new kernel, IpNTK, which can take label information into account for ANNs to measure the interaction between samples during learning; 2) we provide a unified view to explain the learning difficulty of samples and forgetting events using the three types of relationships defined under IpNTK; 3) we show that generalisation performance in classification problems is not impacted by carefully removing data items that have similar lpNTK feature representations.
LPNTK: SAMPLE INTERACTION VIA FIRST-ORDER TAYLOR APPROXIMATION
2.1 DERIVATION ON SUPERVISED LEARNING FOR CLASSIFICATION PROBLEMS
We start from the first-order Taylor approximation to the interactions between two samples in classi- fication. Suppose in a K K-way classification problem, the dataset D consists of N labelled samples, i.e. D = {(x;; }:)) Our neural network model is fæ; w) _ q (xx) = poftmax(2(1t) w)) where w E Rd is the vectorised parameters, = X + R and q E A K K-1 To update parameters, we assume the cross-entropy loss function, i.e. q(=))
log qg (a)) where qs represents the k-th element of the prediction vector q, and the propppropggttion algorithm (Rumelhart et al.) 1986). At time t, suppose we take a step of stochastic gradient descent (SGD) with learning rate 17 on a sample Tu. we show that this will modify the prediction on D. # C. as:
A (wx) q + (xx) (x.o))
R 1 A A (2.)) K (2o, (Ptar(0n) g' (xx))
(1)
KxK
KXK
Kx1
where (Ir.)) ( K' F.)) V. 20 (2.))) )uw (V.z Vewe(an (Ir) Huw) ) and (rr (Ir.) is one-hot vector where only the yu-th element The full derivation is given in Appendix A
K' a.)) in Equation [ is a dot product between the gradient matrix on T. (V (V=='(xn))) ) and Co (V (2x)(( w.t) Thus, an entry K' > means that the two gradient vectors, Vuii, (z.) and Vwry. x' (xx). are pointing in similar directions, thus learning one leads to better prediction on the other; when KY, < O the two gradients are pointing in opposite directions, thus learning one leads to worse prediction on the other. Regarding the case where K & O, the two gradient vectors are approximately orthogonal, and learning one of them has almost no influence on the other. Since (' the only term that involves both F, and 2. at the same time, we argue that the matrix itself or a transformation of it can be seen as a similarity measure between v. and Co. which naturally follows from the first-order Taylor approximation. K't K2,,,, a.a) is also known as the eNTK Jacot et al. 2018) in vector output form.
Although K' R.)) is a natural similarity measure between Co and Ba, there are two problems. First, it depends on both the samples and parameters w', thus becomes variable over training since w' varies over t. Therefore, to make this similarity metric more accurate, it is reasonable to select the trained model which performs the best on the validation set, iee. parameters having the best generalisation performance. Without loss of generality, we denote such parameters as w in the following, and the matrix as K. The second problem is that we compute K (xx, xx) for every pair
2

---

Published as a conference paper at ICLR 2024
of samples (z, x'), but need to convert them to scalars n(æ,, x²) in order to use them conventional scalar- valued kernel. This also makes it possible to directly compare two similarity matrices, e.g. K and K". It is intuitive to use Lp.g or Frobenius norm of matrices to convert K ( x') to scalars. However, through experiments, we found that the off-diagonal entries in K" (2 F.) are usually non-zero and there many negative entries, thus neither -prrm Instead, the findings from Mohamadi & Sutherland (2022) suggests that the sum of all elements in K (x,x') divided by K serves as a good candidate for this proxy scalar value, and they refer this quantity as pNTK. We follow their idea, but show that the signs of elements in Pur (x) q(x) should be considered in order have higher test accuracy in practice. We provide empirical evidence that this is the case in Section 4
F-norm is appropriate.
2.2 INFORMATION FROM LABELS
Beyond the similarity matrix K, there are two other terms in Equation [ the softmax derivative term A and the prediction error term Per (m.) -a)))-'((( ga(..... As shown in Equation from Appendix A the signs in A are constant across all samples. Thus, is not necessary to take A into consideration when we measure the similarity between two specific samples.
We now consider the prediction error term. In common practice, Par is usually a one-hot vector in which only the y-th element is 1 and all others are O. Since softmax(z) A K we can perform the following analysis of the signs of elements in the prediction error term:
0 Q1 < 0
(wu - q(xx))
=
1 Qy > 0
+
s(Vu) - sign (Pur( - q(xx)) =
+1
(2)
0 9K
< 0
The above analysis shows how learning V. would modify the predictions on To i.. ((.)). Conversely, we can also approximate Am. q(x,,, in the same way. In this case, it is easy to see that ((Fu, T.) K (Ia,, æ.) and all elements of Pur( since K (I 2o) (Po) (zx)) ) = K (Io: x.)T (Pun (I.) - q (xx,)). Therefore, for pair of samples H, and Tu., their labels would change the signs of the rows and columns of the similarity matrix K (æ., R..), respectively.
q(x.) are negative except the yo-th digit,
Note that do not use the whole error term Par( ((x)) but only the signs of its entries. As illustrated in Section 3.1 below, if a large fraction of samples in the dataset share similar gradients, all their prediction errors would become tiny after relatively short period of training. In this case, taking the magnitude of (==(2)) (=x)(= 0) into consideration leads to a conclusion that those samples are dissimilar to each other because the model can accurately fit them. Therefore, we argue that the magnitudes of prediction errors are misleading for measuring the similarity between samples from the learning dynamic perspective.
2.3 LABELLED PSEUDO NEURAL TANGENT KERNEL (LPNTK)
Following the analysis in Section 2.2
we introduce the following IpNTK:
IpNTK((#.. No), (æ., va))
(((w)) (yo) @ K (Ro,
K
1
To( (Vw) 1 K
(3)
s (yo) V Vwz(wx))
K
1xd
dxl
where denotes that element-wise product between two matrices, and s(-) defined in Equation 2
The first line of Equation 3 is to emphasise the difference between our !pNTK and PNTK, i.e. we sum up the element-wise products between 1 (yy. s(y)) and K. Equivalently, the second line shows that our kernel can also be thought of as a linear kernel on the feature space where a sample along with its label y is represented as V s(y) TV (xx). The second expression also shows the novelty of our IpNTK, ie. the label information is taken into the feature representations of samples. We verify that the gap between IpNTK and eNTK is bounded in Appendix B
3

---

Published as a conference paper at ICLR 2024
Practical pipeline: make our IpNTK more accurately approximate the interactions between samples in practice, we follow the pipeline: 1) fit the model on a given benchmark, and select the parameters validation set; 2) calculate the IpNTK matrix based on the wn by enumerating (<, y), (ac', y²); u)) for all pairs (ar, y) and (ær, y/) from the training set.
""' which has the best performance
RETHINKING EASY/HARD SAMPLES FOLLOWING LPNTK
E Rd under IpNTK, and the angles between any two such vectors could be acute, right, or obtuse, it is straightforward to the following three types of relationships between two labelled samples:
Since each labelled sample (ar, y) corresponds to a vector /R
interchangeable samples (where the angle is acute) update the parameters of the model in similar directions, thus learning one sample makes the prediction on the other sample also more accurate;
unrelated samples (where the angle is right) update parameters in (almost) orthogonal directions, thus learning one sample (almost) doesn't modify the prediction on the other sample;
contradictory samples (where the angle obtuse) update parameters in opposite directions, thus learning one sample makes the prediction on the other sample worse.
More details about the above three types of relationships can be found in Appendix C In the re- mainder of this section, we illustrate and verify how the above three types of relationships provide new unified view of some existing learning phenomena, specifically easy/hard samples discussed by Paul et al. (202T) and forgetting events found by Toneva et al. (2018).
3.1 A UNIFIED VIEW FOR EASY/HARD SAMPLES AND FORGETTING EVENTS
Suppose at time-step 1 of training, we use a batch of data B = ((*,, ((rt,,/)) =D to update the param- eters. We now consider how this update would influence the predictions of samples in B and BC+1, As shown by Equation I for sample x' in either Bt or Bt+,, the change of its prediction is approximately 7) A' (x') Exrer= K'(x', x') (Pta q' (x")). Note that the sum on B is still linear, as all elements in Equation I are linear.
Following the above analysis, it is straightforward to see that a sample in B is contradictory to most of the samples in B', it would most likely be forgotten. the updates from B' modify its prediction in the "wrong" direction. Furthermore, if the probability of sampling data contradictory to (ær, y) is high across the training, then (æ, y) would become hard learn the updates from this sample are likely to be cancelled out by the updates from the contradictory samples until the prediction error on the contradictory samples are low.
On the other hand, if a sample in IB++1 is interchangeable with most of the samples in B², it would be an easy sample, the updates from BBd already modified its prediction in the "correct" direction. Moreover, if there is large group of samples that are interchangeable with each other, they will be easier to learn since the updates from all of them modify their predictions in similar directions.
Therefore, we argue that the easy/hard samples as well as the forgetting events are closely related to the interactions between the IpNTK feature representations, i.e. / st)) (V ==> of the samples in a dataset. The number of interhhangebbeloootraiccoyyy samples can be thought as the "learning weights" of their corresponding INNTK feature representations.
An example of and further details about the above analysis are given in Appendix D.I
3.2 EXPERIMENT 1: CONTROL LEARNING DIFFICULTY
The first experiment
is verify that the learning difficulty of samples is mainly due to the interactions between them, rather than inherent properties of individual samples. To do so, we empirically verify the following two predictions derived from our explanation given in Section 3.1l
Prediction for given universal of training samples for a subset of it T T contains fewer samples, the interactions in T are weaker compared the interactions in T. thus the learning difficulty of samples in T is less correlated with their learning difficulty in T;
4

---

Published as a conference paper at ICLR 2024
4096 1024 [p=0.86)
4096 (p=0.61)
4096 64 (g=02284)
4095 (p=0.222)
4096 (G=0
4096 (p=00007)
90-
125
Figure I: Correlation between the learning difficulty of samples trained on subsets of varying sizes. For each subfigure, the x-value is the difficulty of samples trained on the universal set (4096), while y-axis is the difficulty trained on the contrast setting (1024, 256, etc.). Smaller Pearson correlation coefficient p means less correlation between x and y values. The title of each panel is the settings we compare, egg. "4096 vs I" means that we plot the learning difficulty of the same sample on the universal set (of size 4096) against its learnability in dataset containing just itself.
Prediction 2 for a given training sample (æz, y), if the other samples in the training set (a', ,/) E T \ {(2r,)) v)) are more interchangeable to it, then (a. y) is easier to learn.
To verify Prediction 1
we show that the learning difficulty of a sample on the universal dataset T becomes less correlated with its learning difficulty on subsets of ' of smaller sizes. Following the definition from Jiang et al. (202T) and Ren et al. (022), we define the learning difficulty of a sample (x. y) as the integration of training loss over epochs, or formally Σ, [(x y) where & indicates the index of training epochs. In this way, larger values indicate greater learning difficulty.
We run our experiment using the ResNet-18 model (He et al., 2016) and a subset of the CIFAR-10 10 dataset (Krizhevsky et al. 2009): we select 4096 samples randomly from all the ten classes, giving a set of 40960 samples in total. On this dataset, we first track the learning dificullty of samples through single training run of the model. Then, we randomly split it into 4096 subsets where X E {1, 4, 16, 256, 1024], and train a model on each of these subsets. For example, when X = 1, we train 4096 models of the same architecture and initial parameters the 4096 subsets containing just 1 sample per class. In all runs, we use the same hyperparameters and train the network with the same batch size. The results are shown in Figure [ To eliminate the effects from hyperparameters, we also run the same experiment with varying settings of hyperparameters on both CIFAR1O 10 (with ResNet- 18, and MNIST where train LeNet-5 model (LeCun et al.) 1989.. Note that we train ResNet-11 18 on CIFARIO and LeNet-5 on MNIST in all the following experiments. Further details can be found in Appendix D.2
X
Given our analysis in Section 3.1 we expect that the interactions between samples will be more different to the universal set when the dataset size is smaller, as a result the learning difficulty of samples would change more. As shown in Figure [ the correlation between the learning difficulty on the whole dataset and the subsets indeed becomes less when the subset is of smaller size, which matches with our prediction.
To verify Prediction 2] we follow an analysis in Section 3.1 i.e. if there is a large group of samples that are citerchangeable/conraaiccooo
to a sample, it should become easier/harder to learn respec- tively. To do so, we first need to group the labelled samples. Considering that the number of sample are usually tens of thousands and the time for computing a k(æ, x') is quadratic to the number of samples, we choose the farthest point clustering (FPC) algorithm proposed by Gonzalez (1985), since: 1) in theory, it can be sped up to O(N log M) where M is the number of centroids (Feder & Greene 1988): 2) we cannot arbitrarily interpolate between two gradients More details are given in Appendix D.5
As shown in the Appendix D.5 the clusters from FPC are distributed in a heavy long-tail fash- ion, i.e. most of the samples are in the largest cluster. A straightforward prediction following our method is that the centroid of the head (largest) cluster becomes easier due to the large number of interchangeable samples in the cluster. To verify this, we single out the centroids of all classes on MNIST and CIFAR10, 10, and manually add an equal number of the following three types of sam- ples: 1) most interchangeable samples from the head cluster which should make them easier; 2) most non-interchangeable samples" from tail clusters which make them harder; 3) medium inter- changeable samples from the "edge" of the head cluster which should have an intermediate effect
CClustering algorithms like k-means may interpolate between two samples to create centroids of clusters. We found in our experiment that contradictory samples are rare in practice.
5

---

Published as a conference paper at ICLR 2024
HESTT mance
Thining
(a) MNIST
(b) CIFAR-10
Figure 2: Learning difficulty of target samples, i.e. centroids of FPC head clusters, when the sam- ples in the training set are interchangeable (red line), non-interchangeable (purple line), or medium interchangeable (yellow line). The plots show that the learning difficulty of target samples can be controlled through adding samples with different relationships to them into the training sets.
on learnability. We then track the learning difficulty of the centroids on these three types of datasets over 100 random seeds, and the results are shown Figure 2 can be seen that the learning diffi- culty of the target samples become significantly lower when there are more interchangeable samples in the training set, as the red lines are always the lowest. Conversely, as the purple lines are always the highest, the learning difficulty of targets become significantly lower when there exist more non- interchangeable samples in the training set. Similarly, if the samples are medium interchangeable to the centroids, their learning difficulty is just between the other two cases. This shows that we can control the learning difficulty of a sample through controlling the relationships of other samples in the same dataset it, which supports our Prediction 2 and further our analysis in Section 3.1 More details can be found in Appendix D.3.
3.3 EXPERIMENT 2: PREDICT FORGETTING EVENTS WITH LPNTK
The second experiment we run is to check whether the forgetting events can be predicted with !pNTK (k). However, since the sum operation in Equation 3 is irreversible, in order to predict the forgetting events with higher accuracy, we propose a variant of IpNTK & by replacing s(y) in the where
1 is the y-th element. More details of this IpNTK variant are given in Appendix D.4 Following Toneva al. (2018), we say a sample is forgotten at epoch (++ 1 if the model can correctly predict it at / but then makes an incorrect prediction + To guarantee the accuracy of the first-order Taylor approximation, we set the learning rate to 10 in this experiment. In order to sample enough many forgetting events, track the predictions on batches of 128 samples over 10 random seeds in the first 50 and 700 iterations of the training process MNIST and CIFARIO respectively. and observed 7873 forgetting events MNIST and 2799 forgetting events on CIFAR1O. 10. The results of predicting these forgetting events by the variant of IpNTK are given in Table
lpNTK representation with [- K x.......
As can be seen from Table I our variant of INNTK can predict forgetting events significantly better than random guess during the training of models both MNIST and CIFARIO. 10. The prediction metrics on CIFAR-10 are higher, possibly because the number of parameters of ResNet- 18 is greater than LeNet-5, thus the change of each parameter is smaller during a single iteration, which further leads to a more accurate Taylor approximation.
Precision
Recall
Fl -scoe
Benchmarks
Mean
Std
Mean
Std
Mean
Std
MNIST
42.72%
+6.55%
59.02%
+7.49%
49.54%
-6.9%%
CIFAR-10 10
49.47%
+7.06%
69.50%
+7.49%
57.76%
77.6%
Table Performance of predicting forgetting events with our IpNTK on MNIST and CIFAR-10.
USE CASE: SUPERVISED LEARNING FOR IMAGE CLASSIFICATION
Inspired by the finding from Sorscher et al. (2022) that selective data pruning can lead to substan- tially better performance than random selection, we also explore whether pruning samples following the clustering results under IpNTK could help to improve generalisation performance in typical su- pervised learning task, image classification. In the experiments below, we use the same models and benchmarks as in Section 3.3

---

Published as a conference paper at ICLR 2024
Following the clustering analysis from Appendix D.5 resentations of samples from a cluster into a single vector. The size of the cluster can then be thought as the weight for that vector during learning. Given the cluster size distribution is heavily long-tailed, the learning would be biased towards the samples in the head cluster. However, we also know that the samples in the head cluster are more interchangeable with each other, i.e. they update parameters in similar directions. Therefore, we ask the following two questions in Section 44. and 4.2
suppose we compose the IpNTK feature rep-
4.1 Do WE NEED ALL THOSE INTERCHANGEABLE SAMPLES FOR GOOD GENERALISATION?
To answer this question, we define sample as redundaatt under IpNTK the most interchangeable sample to it is not itself. Formally, for a sample æ. if there exists another sample x' * æ such that lpNTK (x, y). verify that redundant samples identified in this way are indeed not required for accurate generali- sation, we removed them from both MNIST and CIFAR-IO to get de-redundant versions of them also de-
y')) > IpNTK(( y), (x, y)). then æ is considered as a redundant sample 3 To
under lpNTK. To show the necessity of taking the label information into consideration, fine redundant samples under pNTK in a similar way, i.e. for a sample æ. if there exists another sample æ² j x such that (1, a²) pNTKK(r .),, then æ: is considered as a redundant sample under pNTK. Following this definition, we can also get de-redundant MNIST and CIFAR 10 with PNTK. The test accuracy over training epochs on the whole training sets of MNIST and CIFAR-10 10 along with the de-redundant versions of them are shown in Table 2 To eliminate the effects from hyperparameters, we ran this experiment over 10 different random seeds. Moreover, we did not fine- tune any hyperparameters, to make sure that the comparison between different instances of datasets are fair. As a result, the average test accuracy we obtained is not as high as reported in some other works, e.g. Guo et al. 20222.
Full
De-redundant by pNTK
De-redundant by IpNTK
Benchmarks
Mean
Std
Mean
Std
Mean
Std
MNIST
99.31%
0.03%
99.27%
0.05%
99.30%
0.03%
CIFARIO
93.28%
0.06%
90.93%
0.29%
93.17%
0.23%
Table 2: Test accuracy over training epochs of models trained with MNIST and CIFAR-10 as well as the de-redundant versions. The results are averaged across 10 different runs, and the corresponding standard deviation is also given. This table shows that removing the redundant samples defined with our 1pNTK leads to generalisation performance w.o. statistically significant difference to the whole set, while pNTK leads to worse performance.
can be seen in Sablee]thar removing the redundant samples under IpNTK leads to almost the same generalisation performance on both MNIST and CIFAR- 10 (converged test accuracy obtained with the whole training sets is not significantly higher than accuracy obtained using the de-redundant ver- sion using IpNTK: on MNIST, ((19)- 0.293, p 0.4: on CIFAR1O. 10, t {(19) 1 1.562, p = 0.153), whereas the de-redundant versions obtained by PNTK leads to significantly worse generalisation performance (on MNIST, t(19) 13.718, 718, < 0.01; on CIFAR1O, t(19)= 26.252, p < 0.01).
Overall, our results suggest that it is not necessary to train on multiple redundant samples (as iden- tified using lpNTK) in order to have good generalisation performance: the fact that identifying redundant samples using PNTK doey lead to reduction in performance shows that taking the la- bel information into account evaluating the relationships between samples (as we do in IpNTK) indeed leads to a better similarity measure than PNTK in practice.
4.2 WILL THE GENERALISATION PERFORMANCE DECREASE IF THE BIAS IN THE DATA TOWARDS THE NUMEROUS INTERCHANGEABL SAMPLES IS REMOVED?
To answer this question, found several relevant clues from existing work. Feldman 2020
demonstrated that memorising the noisy or anomalous labels of the tailed samples is necessary
in order to achieve close-to-optimal generalisation performance. Paul et al. (2021) and Sorscher
et al. (2022) pointed out that keeping the hardest samples can lead to better generalisation perfor- mance than keeping only the easy samples. Particularly, the results in Figure I Paul et al. (2021)
AA visualisation of redundant sample definition is given in Appendix E.1

---

Published as a conference paper at ICLR 2024
Benchmarks MNIST
Full
1pNTK
EL2N
GraNd
Forgot Score 99.266
Influence-score 39.27(+0.05) %
(4..00+
99.37( +0.04)s
99.33( 99.33((-.00) 4-0.6) %
99.28; 0.055%
+
CIFARIO
23.26610006)%
93.35 20.12)
93.32 E0.07 1%
92.87 11.33
1222%
92.53
Table 3: Test accuracy of models trained with full training set and various subsets from MNIST and CIFARIO. The results are averaged across 10 different runs, and the standard deviation are also given. The table shows that randomly removing 10% of the samples in the head cluster leads to slightly better generalisation performance than the original datasets.
show that removing 10% or 20% of the easy samples can lead to better test accuracy than training on the full training set.
As discussed in Section B both the long-tail clusters and hard samples can be connected to the three types of relationships under our lpNTK. Specifically, samples in the head cluster are more interchangeable with each other, and thus easier to learn, while the samples in the tail clusters are more unrelated or even contradictory to samples in the head cluster and thus harder to learn. Furthermore, labels of the samples in the tail clusters are more likely to be noisy or anomalous, e.g. the "6" shown in the seventh row in Figure [3 looks more like "4" than a typical "6".
Inspired by the connections between clustering results under 1pNTK and the previous works, we: 1) remove the redundant samples from the dataset under IpNTK; 2) cluster the remaining samples with FPC and IpNTK; 3) randomly prune 10% of the samples in the largest cluster; 4) compare the test accuracy of models trained with the original datasets and the pruned versions. This sequence of steps involves removing roughly 20% of the total dataset. The results are given in Table 3
As we can see in Table 3 the sub-dataset pruned by IpNTK actually lead to slightly higher test accuracy than the full training sets of MNIST and CIFAR-10: f-test comparing converged test accuracy after training on the full vs IpNTK-prunde datasets shows significantly higher performance in the pruned sets (MNIST: ((19) -3.205, p 0.005; CIFAR: ((19) -3.996,7 p 0.003). This suggests that it is potentially possible to improve the generalisation performance on test sets by removing some interchangeable samples in the head cluster from FPC on IpNTK.
4.3 LIMITATION OF THIS INITIAL EXPLORATION OF LPNTK
Although the results illustrated above answer the two questions in Section 4.1 and 4.2 this work still suffers from several limitations when applying lpNTK practice.
Additional hyper-parameter selection: our experiments in this section involve decision on several additional hyper-parameters The fraction of samples be removed in Section 4.2 20%, is purely heuristic. Similarly, the number of clusters in FPC clustering M is also heuristic. Here, the optimal choice of M related to both the training and test datasets and needs to be further studied.
Computational complexity of lNNTK O(N2d²) is also a significant limitation for its application in practice. To overcome this, a proxy quantity for IpNTK is necessary, especially proxy that can be computed in (1) along with the training of the models.
Dependency on accurate models parameters w": as stated Section 2.3 an accurate IpNTK de- pends on parameters that perform accurate prediction on validation data. This limits the calculation of IpNTK to be post-training. In future work, we aim to provide method that can compute IpNTK along with the training of models, and improve the final generalisation of models by doing so.
Relationships between only training samples: technically, IpNTK can measure any pair of annotated samples. Thus, it is also possible to use IpNTK to measure the similarity between the training and test data, which is very relevant to methods like influence function (Koh & Liang 2017).
5 RELATED WORKS
Transmission Bottleneck in Iterated Learning: This work originated as an exploration of the possible forms of transmission bottleneck in the iterated learning framework (Kirby & Hurford 2002 Smith et al. 2003 Kirby al. 2014) deep learning models. In existing works (e.g.
In the paper Paul al. 2021), the authors pruned the samples with lowest EIL2N scores to obtain better generalisation performance, which corresponds to the samples in the head cluster discussed in Appendix D.5
8

---

Published as a conference paper at ICLR 2024
Guo al. 2020: Lu et al. 2020: Ren al., 2020 Vani al. 2021 Rajeswar al. 2022 the
transmission bottleneck is usually implemented as a limit on the number of pre- pre- training epochs for the new generation of agents. However, as shown in human experiments by Kirby al. (2008), the transmission bottleneck can also he a subset of the whole training set, which works well for human agents. So, inspired by the original work on humans, subset-sampling as form of transmission bottleneck. As shown in Section 4.2 it is indeed possible to have higher generalisation performance through limiting the size of subsets. Thus, we argue that this work sheds light on new form of transmission bottleneck of iterated learning for DL agents.
explore the possibilityy of using
The NTK was first proposed by Jacot et al. (2018), and was derived on fully connected neural networks, or equivalently multi-layer perceptrons. Lee et al.] (2019); Yang 2019 2020); Yang & Littwin (202T) then extend NTK to most of the popular neural network architectures. Beyond the theoretical insights, NTK has also been applied to various kinds of DI. tasks, e.g. 1) Park et al. (2020) and Chen et al. (202T) in neural architecture search; 2) /houu et al.) (202I) in meta learning; and 3) Holzmüller et al. (0022) and Wang al. (2021) in active learning. dataset distillation (Nguyen et al. 2020 202T). which is closely related to our work, thus we discuss it separately in the next paragraph. Mohamadi & Suther (2022) explore how to convert the matrix- valued eNTK for classification problems to scalar values. They show that the sum of the eNTK matrix would asymptotically converge the eNTK, which inspires INNTK. However, we emphasise the information from labels, and focus more on practical use cases of lpNTK. We also connect IpNTK with the practical learning phenomena like learning difficulty of samples and forgetting events.
Neural Tangent Kernel:
NTK has also been applied
Coreset Selection and Dataset Distillation: As discussed in Section 4 we improve the generalisa- tion performance through removing part of the samples in the training sets. This technique is also a common practice in coreset selections (CS, Guo et al., 2022), although the aim of CS is usually to select subset of training samples that can obtain generalisation performance similar to the whole set. On the other hand, we aim to show that it is possible to improve the generalisation performance via removing samples. In the meantime, as shown in Equation 3 our IpNTK is defined on the gradi- ents of the outputs w.r.t the parameters. Work on both coreset selection (Killamsetyy et al. (021 and dataset distillation (Zhao et al., 2021) have also explored the information from gradients for either selecting or synthesising samples. However, these works aimed to match the gradients of the loss function w.r.t the parameter on the selected/synthesisedd samples with the whole dataset, whereas focus on the gradients between samples in the training set.
6 CONCLUSION
In this work, studied the impact of data relationships generalisation by approximating the interactions between labelled samples, i.c. how learning one sample modifies the prediction on the other, via first-order Taylor approximation. With SGD as the optimiser and cross entropy as the loss function, we analysed Equation [ showed that eNTK matrix is a natural similarity measure and how labels change the signs of its elements. Taking the label information into consideration, we proposed IpNTK in Section 2 and proved that it asymptotically converges to the eNTK under certain assumptions. As illustrated in Section 3 is then straightforward to see that samples in dataset might be interchangeable, unrelated, or contradictory. Through experiments on MNIST and CIFAR-10. we showed that the learning difficulty of samples as well as forgetting events can be well explained under unified view following these three types of relationships. Moreover, we clustered the samples based on IpNTK, and found that the distributions over clusters are extremely long-tailed, which can further support our explanation about the learning difficulty of samples in practice.
Inspired by Paul et al. (22II) and Sorscher et al. (2022), ), we showed that the generalisation per- formance does not decrease on both MNIST and CIFAR-10 through pruning out part of the inter- changeable samples in the largest cluster obtained via FPC and lpNTK. Our findings also agree with Sorscher et al.) (202)) in that the minority of the training samples alisation performance, when a large fraction of datasets can be used to train models. Or equivalently, the bias towards the majority samples (those in the largest cluster) may degrade generalisation in such cases. Overall, we believe that our work provides a novel perspective to understand and anal- yse the learning of DL models through the lens of learning dynamics, label information, and sample relationships.
important for good gener-

---

Published as a conference paper at ICLR 2024
REFERENCES
Xiangning Chen, Cho-Jui Hsich, and Boqing Gong. When vision transformers outperform resnets without pre-traininn pre-training or strong data augmentations. arXiv preprint arXiv:2106.0 2021.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, al. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010.1 11929, 2020.
Tomás Feder and Daniel Greene. Optimal algorithms for approximate clustering. In Proceedings of the twentieth annual ACM symposium on Theory of computing, pp. 434 444, 1988.
Vitaly Feldman. Does learning require memorization? a short tale about a long tail. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pp. 954-959, 2020.
Teofilo Gonzalez. Clustering minimize the maximum intercluster distance. Theoretical com- puter science, 38:293-306, 1985.
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep learning. MIT press, 2016.
Chengcheng Guo, Bo Zhao, and Yanbing Bai. Deepcore: comprehensive library for coreset selection in deep learning. arXiv preprint arXiv:2204.0888 08499, 2022.
Shangmin Guo, Yi Ren, Serhii Havrylov, Stella Frank, Ivan Titov, and Kenny Smith. The emergence of compositional languages for numeric concepts through iterated learning in neural agents. In The 13th International Conference on the Evolation of Language, 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
David Holzmüller, Viktor Zaverkin, Johannes Kästner, and Ingo Steinwart. A framework and bench- mark for deep batch active learning for regression. arXiv preprint arXiv:2203.0944 009400 2022.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kemel: Convergence and gen- eralization in neural networks. In Advances in Neural Information Processing Systems, 2018.
Ziheng Jiang, Chiyuan Zhang, Kunal Talwar, and Michael C Mozer. Characterizing structural reg- ularities labeled data overparameterized models. In International Conference on Machine PMLR, 2021.
Learning. pp.
Krishnateja Killamsetty, Durga, Ganesh Ramakrishnan, Abir De, and Rishabh Iyer. Grad-match: Gradient matching based data subset selection for efficient deep model training. In International Conference on Machine Learning, pp. 5464-5474. PMLR, 2021.
Simon Kirby and James R Hurford. The emergence of linguistic structure: An overview of the iterated learning model. Simulating the evolution of language, pp. 121-147, 2002.
Simon Kirby, Hannah Cornish, and Kenny Smith. Cumulative cultural evolution in the laboratory: An experimental approach to the origins of structure in human language. Proceedings of the National Academy of Sciences,
2008. doi: 10. http://paa..0773555111
URL https: wwwp://wwwww/.. www..ppaaa...m wwtp/org//ooo/oooo abs////b///ii 10w.11..111131a880 070 7835105
Simon Kirby, Tom Griffiths, and Kenny Smith. Iterated learning and the evolution language.
Current opinion in neurobiology, 28:108-114 2014.
James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei A. Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Grabska-Barwinske Demis Has- sabis, Claudia Clopath, Dharshan Kumaran, and Raia Hadsell. Overcoming catastrophic for- getting in neural networks. Proceedings of the National Academy of Sciences. 114(13):3521- 3526, 2017. doi: 10.1073/pnas..61113 1611s351111 URL https: www. pnas ort/ooo//oooooooooo abs/ 10. 70.1073/pnas. 1611 8351141
10

---

Published as a conference paper at ICLR 2024
Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In International conference on machine learning, pp. 1894. PMLR, 2017.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convo- lutional neural networks. Communications of the ACM, 60(6):84-9))) 90, 2017.
Yann LeCun, Bernhard Boser, John Denker, Donnie Henderson, Richard Howard, Wayne Hubbard, and Lawrence Jackel. Handwritten digit recognition with a back prookkpppppgtion network. Advances in neural information processing systems, 2, 1989.
Yann LeCun, Leon Bottou, Genevieve Orr, and Klaus-Robert Müller. Efficient backprop. In Neural Networks: Tricks of the Trade, pp. 9-50. Springer, 1998.
Jaehoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jaseha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve linear models under gradient descent. Advances in neural information processing systems, 32, 2019.
Tsung-Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollár. Focal loss for dense object detection. Proceedings of the IEEE international conference on computer vision, pp- 2980-2988, 2017.
Yuchen Lu, Soumye Singhal, Florian Strub, Aaron Courville, and Olivier Pietquin. Countering language drift with seeded iterated learning. In International Conference on Machine Learning, pp. 6437-6447. PMLR, 2020.
Mohamad Amin Mohamadi and Danica Sutherland. A fast, well-founded approximation to the empirical neural tangent kernel. arXiv preprint wrXiv:2206.1254. 2022.
Timothy Nguyen, Zhourong Chen, and Jachoon Lee. Dataset meta-learning from kernel ridge- regression. arXiv preprint arXiv:2011.00050 2020.
Timothy Nguyen, Roman Novak, Lechao Xiao, and Jachoon Lec. Dataset distillation with in- finitely wide convolutional networks. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wort- man Vaughan (eds.), Advances Neural Information Processing Systems, 2021. URL https: //openzeview. net. forum? wtt.://dddwwh.ppoooooe d=hXMMPPedddPP
Daniel S Park, Jaehoon Lee, Daiyi Peng. Yuan Cao, and Jascha Sohl-Dickstein. Towards nngp- guided neural architecture search. arXiv preprint arXiv:201 1.06006, 2020.
Mansheej Paul, Surya Ganguli, and Gintare Karolina Dziugaite. Deep learning on a data diet: Find- ing important examples early in training. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 20596-20607. Curran Associates, Inc., 2021. URL http::tttt//s//ocdiiinooo new.ediii..nnnnnnn.............. Pwp.r.
cc/ cc./pp//7288///aeecffffee3333311
Sai Rajeswar, Pau Rodriguez, Soumye Singhal, David Vazquez, and Aaron Courville. Multi-label iterated learning for image classification with label ambiguity. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 4783 4793, 2022.
Yi Ren, Shangmin Guo, Matthieu Labeau, Shay B. Cohen, and Simon Kirby. Compositional lan- guages emerge in neural iterated learning model. In International Conference Learning Representations, 2020. URL httpttt::/ppeeeeeeteeeee
net/ wtt.:e/eeooommm.m-eeeee......
Yi Ren, Shangmin Guo, and Danica J. Sutherland. Better supervisory signals by observing leam- ing paths. In International Conference on Learning Representations, 2022. URL https:
/ //openreviee ew. net. htw..eee//foormmemooooooooaadaa
David E Rumelhart, Geoffrey Hinton, and Ronald J Williams. Learning representations by back- propagating errors. nature, 523(6888):533-536 1986.

---

Published as a conference paper at ICLR 2024
Burr Settles. Active learning. Synthesis lectures artificial intelligence and machine learning, 6 (1):1-114, 2012.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittweeser, Ioannis Antonoglou, Veda Panneershelvam,, Marc Lanctot, al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):444488) 2016.
Kenny Smith, Simon Kirby, and Henry Brighton. Iterated learning: A framework for the emergence of language. Artificial life, 9(4)371 2003.
Ben Sorscher, Robert Geirhos, Shashank Shekhar, Surya Ganguli, and Ari Morcos. Beyond neural scaling laws: beating power law scaling via data pruning. arXiv preprint 220.1i:2200.1448880 2022.
Mariya Toneva, Alessandro Sordoni, Remi Tachet des Combes, Adam Trischler, Yoshua Bengio, and Geoffrey Gordon. An empirical study of example forgetting during deep neural network learning. arXiv preprint arXiv:1812.05155. 2018.
Ankit Vani, Max Schwarzer, Yuchen Lu, Eeshan Dhekane, and Aaron Courville. Iterated learning for emergent systematicity in [vqa}. In International Conference on Learning Representations, 2021. [ttp:ttss:///oeeeee
net. http://eoooommmmododo.o......
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural informa- fion processing systems, 30, 2017.
Haonan Wang, Wei Huang, Andrew Margenot, Hanghang Tong, and Jingrui He. Deep active learn- ing by leveraging training dynamics. arXiv preprint arXiv:2110.08611, 2021.
Wenxiao Wang, Alexander Levine, and Soheil Feizi. Lethal dose conjecture on data poisoning.
arXiv preprint arXiv:2208.0333 2022.
Wei Xiong. A note exponential inequality. 2022. URL stttp://homm..stc.eee /n/
xw2011 6/ htt///tteeeepppp pdf
Greg Yang. Wide feedforward or recurrent neural networks of any architecture are gaussian pro- cesses. In H. Wallach, H. Larochelle, A. Beygelzimer, d'Alché-Buc, Fox, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Asso- ciates, Inc., 2019. URL httt::::/pprcceedingg neraseneriip.. cctppapprr/2111//iieeee 97665666d93325- http://pccccaaaa..eeee....rrreer
pdf
Greg Yang. Tensor programs ii: Neural tangent kernel for any architecture. arXiv preprint arXiv:2006. 14548, 2020.
Greg Yang and Etai Littwin. Tensor programs iib: Architectural universality of neural tangent kernel training dynamics. In International Conference on Machine Learning, pp. 11762-111777 11772, PMLR, 2021.
Bo Zhao, Konda Reddy Mopuri, and Hakan Bilen. Dataset condensation with gradient matching. In International Conference on Learning Representations, 2021. URL. /tR.hhttpp:://peeeeviiee
met/forume forum? L.
Yufan Zhou, Zhenyi Wang, Jiayi Xian, Changyou Chen, and Jinhui Xu. Meta-learning with neural tangent kernels. arXiv preprint arxi::2102.03909 2021.
12

---

Published as a conference paper at ICLR 2024
A FULL DERIVATION OF LPNTK ON CLASSIFICATION PROBLEM IN SUPERVISED LEARNING
Following the problem formulated in Section 2 let's begin with Taylor expansion of (l..)(Z.))
(x V q
(wo)lwt (w
w + O w'' w'1l?).
Kx1
Xx1
Kxd
To evaluate the leading term, we can plug in the definition of SGD and apply the chain rule repeat- edly:
V (wo)last (wo+1 - ur") = (xo)l=
V ( 17 V (axn)llo
Kxd
dx1
Kxk
kxd
1xd
V= (a=)lao)ln (- L V V (zn)) )
V ( I Vw (20) loo (V w (x
(V
KxK
Kxd
dxK
Rx1
= Tj A (x.) K' (2:; aw) (Peal - o (In))
(4)
For the higher-ordee terms, using as above that
w w V/ wx ( to (Pur( (x(w))
and note that || Puur (Ix.) - q" .. is bounded as Pur. q E AK we have that
(11 w0 112) = (n² (V x(x w: 1 (x.,) q' (x..) = v( ( )lāp))
L
The first term in the above decomposition is symmetric positive semi-definite (PSD) matrix shown below,
41 q1)
QQQ2 (2)
4291
42
G24K
A' A'(x.) = V 1z:
(5)
9K 91
9K 92
OK (1 qK
The second term in the above decomposition, K' (2,, v.), is the outer product of the Jacobian on ar and a.. It is intuitive see that the elements in this matrix would be large if the Jacobians are both large and similar direction. Since (x,,,, a.)) is matrix rather than a scalar, so it is not a conventional scalar-valued kernel. This matrix also usually known as matrix-valued NTK.
The third term in the above decomposition is the prediction error on Cus (.r (2.). During the training, for most of the samples, this term would gradually approach 0, suppose the model can fit well on the dataset. However, it is varying over the epochs, so it is not a constant like the sign vector (yy). Thus, we introduce only the signs from this vector into our IpNTK, as illustrated in Section
B FURTHER RESULTS ON THE ASYMPTOTIC CONVERGENCE OF LPNTK
Theorem 1. (Informal). Suppose the last layer of our neural network z(x;; w) is a linear layer of width w. Let n((x, y), (x', s')) be the corresponding IpNTK, and K (x, x') be the corresponding eNTK. Over the initialisation of 2(æ; w), with high probability, the following holds:
||K ((n,y), (a', , 8 IK (xx x x')lr E 0(1)
(6)
where Ix is a K-by-K identity matrix. A formal statement and proof are given in Appendix B.I We also provide our interpretation of this result in Appendix B.2
13

---

Published as a conference paper at ICLR 2024
B.1 PROOF OF THEOREM I SECTION 2.3
Out proof blow relies on sub-expe sub-exponential random variables, and we recommend the Appendix B. of Mohamadi & Sutherland 2022) and notes written by Xiong 2022) for the necessary background knowledge.
Following the notation from Section 2.1 assume ANN model z(-) has L layers, and the vectorised parameters a layer / E { ......L} is denoted as w' whose width is wy. In the meantime, assume the last layer of is dense layer parameterised by matrix W4, and the input the last layer is (2;; w ())
IR thus =(x) WL g(x). Lastly, let's assume the parameters of the last layer are initialised by the LeCun initialisation proposed by LeCun et al. 1998), i.c. W (O, ..Z.) Equivalently, W can be seen W VWE u where w. NV, 1).
I
has been shown by Lee et al. al. (2019) and Yang (2020) that the eNTK can be formulated as the sum of gradients of the outputs w.r. the vectorised parameters w', That said, the eNTK of an ANN can be denoted as
K (x,
w 2(x) V (
(7)
1=1
Since the last layer of x(.) is dense layer, ic. x(x) W a()), we know that V vw'
V gz V Vw'g(z) = wt V g(z). Thus, the above Equation 7
can re-written as
K (x, Vw 2 2((x)))
Σ w v V Vw: w
-g(x) w Σ
V n (wx) Vn Vm wT
(8)
g(=))=((a))) (((4'),,, w K (xx x')
where In is K-by-K identity matrix.
Then, by expanding Equation g we can have that the elements in K K=(x,, x²) are
(²))xx²) = = })g(z) Tg(a))
g((a)
W (x. W WF
1(i [[ j)g(x) g((')
W W ta
K2
ab (x, a²)
a=1
b=1
WL
w1
1(i = j)g(z) g(('))
U Ugb U K29 (x, x')
WL
where 1(.) is the indicator function.
From Equation [ like the PNTK proposed by Mohamadi & Sutherland (2022). it can be seen that IpNTK simply calculates a weighted summation the element eNTK. Thus, IpNTK can also be seen appending another dense layer parameterised by - ( to the ANN z(-) where s(y) defined in Equation 2 Similar how we get Equation between æ and w' is
we can get that the value of IpNTK
K
N² x= x') g(x) g(x')
se
(u))sa(
K
(10)
K
K
WL
= =g(x)T "(x")) -g(x') +
Σ
se(y) ) Udl K2 (x,
Kwi
14

---

Published as a conference paper at ICLR 2024
Now, let's define the difference matrix between IpNTK and eNTK D(x,x') - veL x² (x, x')
X I
yer K2 (x, x'), then the entries in ( x') are
Lami > twe tin K (2t, x') Jymil
(2)(
2c== 2d=1 Σ Der - 8c(v)sa(y Mea I ) Ka at (2r, x²); ifi=
K K
WL / wL
K
2a=1
2b=1
Uso uzb K
ab (x,
if j.
(11)
Since all parameters are i..d, further simplify the above equation as:
Whallgh - # Ee Σx se(y)sa()))nn Uea Uelbs
if if j.
(iy(r,
Ka as (ax, x²)
WL WL
Uialib.
(12)
then straightforward to see that we can use inequalities for sub-exponential random variables to bound the above result, since: 1) NOO, 1); 2) uf (1) and is sub-exponential with parameters D² 4 and
(SE(4,4)) 3) uny SE v2); 4) linear combination of sub- exponential random variables is still sub-exponential; 5) for random variable X SE(v?, () the following inequality holds with probability at least - 6:
X - pl < max v2
2 log
2 8' 23 log
2
However, note that all elements in Equation I are independent of each other in the case i j. Suppose that = K (ax, x. ll we can then rewrite the case as:
al
1
Da(ax
Wia
sc (y)) Uee
WT, /
K
Σ
se (e())s(()) (eD)saaa)uu
Juo Udo
1=1
D2 (x,,0")
(13)
WL
Uio Ueb
L,baa
W
sely)sa(1/ (t)))sa(/)uoooll Uua Udb
In the following, will bound the above four Da( x') terms separately. Let's start with (a, x'). Considering that a linear combination of a sequence of sub-exponential random vari- ables (U.) where U. E SF B.) is sub-exponential, i.e. Σ, au SE(,, afv? max; |o Bi),
15

---

Published as a conference paper at ICLR 2024
can have the following derivation:
(x x')
se(y)ss()) (ea
WL
WL
to
K
WL
Σ
8c(y)sc(1( (oel Uuea
WL WL
K
K
c=
WL
K {1())
K s((1)s((1))
SE
4
WL
UL
K
K
K - 1
k)
SE
4
,4 K)
K²
WL
(K - ((V)s;(())) + K
K - -Ks(( ())))s(((')
11
SE
4
4 max
WL
WL
K²
K
K
2a
K² (25)())s;()
1)
s (1)))s((()))
SE
WL
K2
Vwr K
20
+3 K+1 K
E
SE
WL
VWoK
(14)
With wr >> K > 2 and the property (5) from the paragraph below Equation
we can claim:
(xx 2x (K + 3)
8
20x
/ 220g
<
2 2 log
(15)
K
g WL
with probability at least 4.
Regarding the remaining terms, the entries are products two independent Gaussian r.v. u u', thus the weighted sum of them are also sub-exponential. Further, we can bound all of them with the property we used Equation 15 So, similar to the above analysis [,,( x'), we can claim that:
2a
K 1
1
(x,
max
2
log
(16)
WL
K
K 8'
WL
[D3 (2,
2a
max
W/, -
2 log
V2
log
(17)
WWr
WT
2x
WL 1
V2 log
(2r, 2')l
/uL
max
WL
2 log
8'
(18)
with probability at least
Regarding the case * of Equation 11 the result identical D (ax x')| shown in the above
Equation 17 Therefore, considering Equation 15 to [8Ill all together, we can loosen the above bounds, and have the following inequalities:
8a
8 8' V2logg
Diy(x, x')l
max 2 2
(19)
WL
with probability at least
Therefore, to sum up from the above, since the Frobenius norm of D(x, x') is /E., Dis xx))), get the following bound for the F-norm of the difference matrix:
8Ka max 2
8K2 2 2 8 V2log
8K2
)) - (20) 8
Pr | (1 x')
16

---

Published as a conference paper at ICLR 2024
B.2 INTERPRETATION OF THEOREM
The above proof and Equation 6 basically say that, even under the infinity width assumption. the gap between IpNTK and eNTK is relatively bounded and non-negligible. They relatively bounded means that IpNTK won't 't diverge from eNTK to an arbitrarily large value. The gap between IpNTK and eNTK is also -on-negligi because the difference doesn't 't converge either.
C FURTHER DETAILS ABOUT THE SAMPLE RELATIONSHIPS UNDER LPNTK
Co
Co
Co
Tu
Ey
Fy
(a) Interchangeable
(b) Unrelated
(c) Contradictory
Figure 3: Visualisation of three possible relationships between data samples. Each vector represents an update to parameters of models based on a hack-propagation from a sample e.g. Do or It and their corresponding labels. Formal definitions given below.
C.I INTERCHANGEABLE
In this case, the two gradient vectors construct small acute angle, and projections each other is longer than fraction of the other vector, formally the conditions can be written as
v, (x.. Z (xo) 2 LA
(z V (2 2
V (2
Vw (2.
where t E (3) 1]. This situation is visualised in Figure 3a
C.2 UNRELATED
In this case, the two gradient vectors almost inter-orthogonal, formally the conditions can be written as
Zy (I.) V Tw
A Vu (Zx) V Vw
Rs 0.
V Zy (I,))"
V w Vw (2.))
This situation is visualised in Figure 3b
C.3 CONTRADICTORY
In this case, the two gradient vectors are almost opposite. Like the interchangeable case, the condi- tions can be formally written as:
By (x... V V (x.)
V Vzzz(Zn) V Vn
S t
<
V no (x
V Zy (x.))
where 1-1,-b) This situation is visualised in Figure 3c
However, the possible causes of this case is more complicated than the above two.
Bo, i.e. the two samples are from the same class. Suppose æu is interchangeable with many other samples in the same class and x, not, this may indicate that æ, is an outlier of the class.
Vu * Vo. ie. the samples are from different classes. Since the annotated data in these two classes not be learnt by the model at the same time, guess is that the data is not completely compatible with the learning model, or the learning model may have a wrong bias for the task.
17

---

Published as a conference paper at ICLR 2024
C.4 CONTRADICTORY SAMPLES IN PRACTICE
In the experiments showed in Section 3.2, we found the contradictory samples are relatively rare in MNIST and CIFAR. This might due to that the labels in benchmarks like MNIST and CIFAR are relatively clean. We believe that if the input signal sampled uniformly, then the more complex the input samples are (e.g., colour images are more complex than black-and-writ ones, high-resolution images are more complex than low-resolution ones) the less likely that the contradictory samples occur. This is due to that larger feature space as well as parameter space makes it less likely for two samples with different labels to have identical features or representations. As long as these two samples have different values on just one dimension, we cannot say they are strictly contradictory.
But, in practice, we believe that there are indeed specific cases that can introduce many contradictory signals. For example, we can do so by manually flipping the label, systematically changing the data collector. Moreover, contradiction can also happen when models fit a good high-level representations for the samples. For example, two samples both contain a grass land as the background, and one is labelled as "cow" while the other is labelled as "grass". In this case, the high-level feature combination is identical, i.e (cow, grass), but the mappings might cancel each other during the learning of the model.
in the foreground and
D FURTHER DETAILS ABOUT EXPERIMENTS IN SECTION 3
D.1 AN EXTREME EXAMPLE OF EASY/HARD SAMPLES DUE INTERACTIONS
In this section, we illustrate an extreme case of interchangeable sample and another extreme case of contradictory samples. To simplify the task, we assume K = 2, i.e. a binary classification problem, and there are only two annotated samples in the training set, (Ia. Bu) and (Iu, vo). Note that the inputs are identical, and we discuss yo yo and yo # Yu separately in the following.
1. Vo = Vu In this case, the two annotated sample are actually identical, thus learning any one of them is equivalent to learning both. It is then straightforward to that these two (identical) samples are interchangeable. Though they are identical, the one that appears later would be counted as an easy sample, since the updates the other one automatically lead good predictions for both.
2. Mo F yo In this case, since there are only two categories, learning of them would cancel the update due to the other one. Suppose the model is being trained in an online learning fashion, and the two samples appear in turn. Then, learning (æ., Yu)) drags the model's prediction q(x... towards On the other hand, learning (æ., Vo) drags the model's prediction ((x.)) towards the opposite direction you In this way, the two samples are completely contradictory to each other, and they both are difficult samples, since the learning is unlikely to converge.
D.2 FURTHER DETAILS ABOUT THE LEARNING DIFFICULTY CORRELATION EXPERIMENT
In this section, we illustrate more details about how we measure the learning difficulty of samples in datasets with varying sizes, as a supplement Section 3.2 Let's suppose that the original training set T contains N samples of K classes. For a given subset size X, we construct X proper subsets of T, T A (Ti,..., , T& J. of which each contains X samples drawn uniformly random from all classes without replacement. To get the Pearson correlation coefficient p between learning difficulty of samples on T and 'T, we run the following Algorithm ||
N
In Section 3.2, we set N 2000 on MNIST. To further eliminate the effects from hyperparameters, we run A I on both MNIST and CIFAR-10 10 with varying learning rates as well as batch size. In these experiments, we train LeNet-5 on MNIST and ResNet-18 on CIFAR-10. The results and the corresponding hyperparameters are listed below:
1. this setting runs MNIST with N 4096, X {1, 16, 64, 256, 1024). learning rate is set to 0.1, and batch size is 128, the correlation results are given in Table 4 and are visualised in Figure
18

---

Published as a conference paper at ICLR 2024
Algorithm 1: Correlation between Learning Difficulty on Size and Size X
Input:
T
(Xin
the training set initial parameters, and the ANN to train number of training epochs learning rate
w. f
7
LL (.....,0;
// List of sample Learning difficulty
N total
f + (0....,0
1/ Lists of sample learning difficulty on subsets
N rocal
< w
// Initialise the parameters to learn
for e <- F. do
for n f- 1 to N do
q - f(xn; wo):
[ + k= 1(k yn) log(gk);
// Cross-entropy loss
Ln - Ln +
wo wh 1 V 1
10
for j +-
x
do
W <
1/ Initialise the parameters for subset
12
for e < to F do
for
1] X - to X do
// enumerate subset of
14
- fxx w)))
I {-- -
Σk=1 1(k = yn. log( ())(
In - Ln +
16
Wj + wj + V m 4;
Output: The Pearson correlation coefficient between L and IL
19

---

Published as a conference paper at ICLR 2024
2. this setting runs MNIST with N = 4096, X (1, 16, 64, 256, 1024). learning rate is set to 0.001, and batch size is 256, the correlation results are given in Table 5 and are visualised in Figure 5
3. this setting runs on CIFARIO with N 4096, X E {1, 4, 16, 64, 256, 1024). learning rate is set to 0.1, and batch size is 128, the correlation results are given in Table and are visualised in F
Note that the hyperparameter combinations in all the above settings are different from the experiment we ran for Figure M Therefore, we argue that the conclusion on learning difficulty correlations experiments consistently holds across different combinations of hyperparameters, N and X.
Size
4096
1024
256
64
16
4096
1.0
0.8512
0.7282
0.5753
0.3865
0.2330
0.062
1024
1.0
0.8206
0.6775
0.4731
0.2888
0.0658
256
1.0
0.7856
0.5853
0.3687
0.0858
64
1.0
0.7169
0.4871
0.1566
16
1.0
0.6379
0.2303
4
1.0
0.3720
1.0
Table 4: The Pearson correlation coefficients between learning difficulty on MNIST where N 4096, X {1.4, 4, 16, 64, 256, 1024), learning rate 0.1, and batch size is 128, i.e. setting As shown in the table, larger gap between the sizes always lead to smaller p. which matches with our Prediction Prediction iilustrated in Section 3.2
Size
4096
1024
256
64
16
4096
1.0
0.9096
0.7376
0.4065
0.2141
0.0695
0.0307
1024
1.0
0.8830
0.5128
0.2707
0.0858
0.0498
256
1.0
0.6782
0.3486
0.0971
0.0605
64
1.0
0.5898
0.1774
0.1598
16
1.0
0.6601
0.6023
4
1.0
0.8414
1.0
Table 5: The Pearson correlation coefficients between learning difficulty on MNIST where
4096, X {1, 4, 16, 64, 256, 1024]. learning rate is to 0.001, and batch size is 256, i.e. setting As shown in the table, larger gap between the sizes always lead to smaller p. which matches with our Prediction Prediction illustrated in Section 3.2
Size
4096
1024
256
64
16
4
4096
1.0
0,8433
0.5772
0.2805
0.1840
0.0628
0.0131
1024
1.0
0.7377
0.4142
0.2595
0.0950
0.0254
256
1.0
0.5409
0.3979
0.1352
0.0345
64
1.0
0,4082
0.1493
0.0427
16
1.0
0.1844
0.0673
4
1.0
0.0912
1.0
Table The Pearson correlation coefficients between learning difficulty on CIFARIO where 4096, X E {1,4, 16, 64, 256, 1024). learning rate is set to 0.1, and batch size is 128, i.c. setting As shown the table, larger gap between the sizes always lead to smaller p. which matches with Prediction Prediction 1 illustrraedd in Section 3.2
20

---

Published as a conference paper at ICLR 2024
4096 vs 1024 (p=0.836) 4096 256 (p=0.735)
4096 vs (p=0.536)
15
10
4096 vs 16
10
15
(o=0.37)
4096 vs 4 (p=0.26)
15
20
4096 vs 1 (p=0.052)
15
15
10-
10
1024 256 (p=0.828)
1024 vs 64 (p=
0.639)
1024
(p=0.435)
30
5
1024 vs 4 (p=m0 2..0..27. 75)
10
1024 vs 1 (p.0.00m 0.031
10
20
256 vs 64 (p 0p.7.)
20
30
15
20
10
10
256 16 (p=0.59) 7
256 (p=8. 0.088)
10
256 1 p=0=0 0.14
25
20
15
10
64 vs 16
10
(p= 6.729
64 Vs 4 1p=00p-.1
5
0.513
64 Vs 1 1p-00.188
10
15
20
10-
10
16 10=0.675 0..67)
16 (p= 0.219)
4 1 (p=0.355 0.359)
25
20
15
10
5
100
20
30
10
20
30
10
20
Figure 4: Visualisation of the correlation between learning difficulty on MNIST where N 4096, X (1,4, 16, 64, 256, 1024), learning rate is 0.1, and batch size is 128, i.e. setting 1 Note that we plot only the correlation between 1000 samples in order to keep the plots readable.
21

---

Published as a conference paper at ICLR 2024
4096 1024 (p=0.919)
4096 vs 256 (p=0.75)
4096 vs 64 (p= (p=8.418)
30
20
20
10
10
4096
16 (p=0.2 0.231
4096 Vs 4 (p=0.072)
4096
1= 0.008)
29.0
28.5
28.5
28.5
28.0
27.5
27.0
1024 256 000866
1824 64 005222
1824 Vs
16 (p=0.286)
28.5
20
26
10
24
1024 3 0.10.1
1024 V5 1 pp= 0.09)
256 64 0p=8
28.5
28.5
28.0
26-
27.5
27.0
256
16
20
00=
0.361)
30
256
4
4pp=
0.13)
30
256 vs 1 (p=0.047)
30
28.5
28.5
28.5
28.0
27.0
64 16 (p= 0.631)
64
(p=0.239)
70
64 1 0=..11
28.5
28.0
27.0
16 (p=0. 0.65)
16 vs (p= 0.59
(p= 0p=5.85)
28.5
28.5
28.5
28.0
27.0
27.0
27.5
28.0
28.5
27.5
28.0
28.5
27.5
26.0
28.5
29,0
Visualisation of the correlation between learning difficulty on MNIST where 4096, X E {1,4, 16, 64, 256, 1024), learning rate is set to 0.001, and batch size is 256, i.e. set- Note that we plot only the correlation between 1000 samples order keep the plots readable.
Figure
ting 2]
22

---

Published as a conference paper at ICLR 2024
4096 Vs 1024 (p= 0.84) 4096 vs 256 (p=0.559)
4096 vs 64 (p= 0.27)
150
200
100
100
150
100
25
0
4096 vs
50
16
pp=
0.1 74)
4096 vs
30
4 (p=
100
8 0
4096 vs
50
pp 0.035)
100
200
200
200
200
150
100
100
100
1024 vs
50
256
100
(p=0.742
(-24)
150
1024 V5 64 (p=0.425
30
100
1024 vs 16 0p=0.251)
100
200
100
150
100
100
50-
1024 vs 4 (p=
100
0.1 1...777 137)
1024 vs 1 1p-00.004]
50
100
256 vs 64 (p=0.567)
50
200
200
150
150
100
100
100
50
256 16 (p=0. 0.381)
150
256
(p=0.138)
19
256 vs 1 -p=- 000
200
200
200
150
100
100
64
16 0030.311
64
(5=0.15)
75
100
64 vs f 289
200
200
200
150
150
100
100
16 (0= 0.198)
150
16 1 00=0.029]
40 vs 1 (o=
0.059)
200
200
200
150
150
150
100
Figure 6: Visualisation of the correlation between learning difficulty on CIFARIO where 4096, X E {1, 4, 16, 64, 256, 1024). learning rate is set to 0.1, and batch size is 128, i.c. setting Note that we plot only the correlation between 1000 samples in order keep the plots readable.
23

---

Published as a conference paper at ICLR 2024
D.3 FURTHER DETAILS ABOUT THE LEARNING DIFFICULTY CONTROL EXPERIMENT
In this section, we provide more details about the learning difficulty control experiment illustrated in Section We first show the centroids of largest cluster obtained through farthest point clustering, of which more details can be found in Appendix D.3 of each class in MNIST and CIFARIO in Figure 7 and F respectivel.
Clics
Cleen
22 3
4
Claz
Cbss
Clcc
Caas
dis 9
6
5
8
7
9
Figure 7: Target samples of each class in MNIST found by FPC with lpNTK as the similarity metric.
Figure 8: Target samples of each class in CIFAR10 found by FPC with IpNTK the similarity metric.
Then, we show the samples that are the most interchangeable to the targets, thus make the targets easier to learn, on MNIST and CIFARIO Figure y and Figure TO respectively. is worth noting that the most interchangeable samples to the targets found by IpNTK are not necessarily the most similar samples to the targets the input space. Take the "car" class in CIFARIO (the second row of Figure 10p for example, the target is photo of a red car from the left back view, and the third most interchangeable sample it is a photo of yellow from the front right view. At the same time, the fourth and fifth most interchangeable samples are both photos of red cars, thus they have shorter distance to the targets the input space due to the large red regions in them. However, under the lpNTK measure, the fourth and fifth red cars less interchangeable/siillaa to the target red car than the third yellow car. This example shows that our IpNTK is significantly different from the similarity measures in the input space.
We also show the samples that are medium interchangeable to the targets, thus make the targets medium easy lear,, MNIST and 1IFAR10 in Figure 1T and Figure
F respectivel...
24

---

Published as a conference paper at ICLR 2024
2
2
2
2
2
2
3
3
3
3
3
3
4
4
4
4
4
4
5
5
5
5
5
5
6
6
6
6
6
6
7
7
7
7
7
7
8
8
8
8
8
8
9
9999
9
9
9
Figure 9: Samples that are the most interchangeable to the targets in MNIST. The leftmost column is the target samples that also shown in Figure 7 The remaining 5 columns the most inter-
changeable samples to the targets in each class.
25

---

Published as a conference paper at ICLR 2024
Figure 10: Sample that are the most interchangeable to the targets in CIFARIO. The leftmost col- umn is the target samples that also shown in Figure The remaining 5 columns the most interchangeable samples to the targets in each class.
26

---

Published as a conference paper at ICLR 2024
I
7
2
2
2
2
2
3
3
3
3
3
3
4
4
4
4
4
4
5
5
5
5
5
5
6
6
6
6
6
6
7
7
7
7
7
7
8
8
g
8
8
8
9
9
9
9
9
9
Figure 11: Samples that are the medium interchangeable to the targets in MNIST. The leftmost
column is the target samples that also shown in Figure 7 The remaining 5 columns are the
medium interchangeable samples to the targets in each class.
27

---

Published as a conference paper at ICLR 2024
Figure 12: Sample that are the medium interchangeable to the targets in CIFARIO. The leftmost column is the target samples that also shown in Figure The remaining 5 columns the medium interchangeable samples to the targets in each class.
28

---

Published as a conference paper at ICLR 2024
Finally, show the samples that are the most non-interchangeablle to the targets, thus make the targets hard to learn, on MNIST and CIFAR 10 Figure [3 and [ that these samples from the tail clusters are more likely to share features appearing in other classes. An example is the class "6" shown in the seventh row of Figure 13 As can be seen there, the second fourth most non-interchangeable to the target look more like "4" than the others. Inspired by this observation, we argue that samples in the tail classes should be annotated with multiple labels rather than single label, since they may contain similar "feature" from other classes. However, limited to the scope by this work, we leave this question to the future works.
We observed
D.4 FURTHER DETAILS ABOUT THE FORGETTING EVENT PREDICTION EXPERIMENT
In this section, illustrate
details about how predict the forgetting events with IpNTK, as a supplement to Section 3.3 Let's 's suppose at training iteration t, the parameter our model w updated with a batch of samples B' = { vf) of size B, thus becomes w Then, at the next iteration & + 1, we update the model parameters w*+1 with another batch of samples 4+2 We found that the predictions
= (a +1 + [= the beginning of training are almost uniform distributions over classes, thus the prediction error term in Equation 2 is likely be |- ..... 1 # ..... -T To give more accurate approximation to the change of predictions at the beginning of training, we therefore replace the syy) in Equation
large number of samples
with (y) 1-1..... K- K-1 ..... -I] and denote this variant of our IpNTK R. We then
y-th th entry propose the following Algorithm to get the confusion matrix of the performance of predicting forgetting events with R.
Algorithm 2: Predict forgetting events with variant of IpNTK R the batch of samples at the batch of samples at t the saves parameters at time-step t, + 1, and t+ learning rate
Input:
B {(x) y. LB
B++1 {(x)
w
w w +2
7
0,
List to record whether forgetting events happen
B total
F. +- {0, 0
// List to record the predicted forgetting events
B total
for i +-- to B do
if arg max qt
(a/: wt+11
v A arg max xf (x/; 2² + yf then
L F, 1
// Forgesting event happens
Aq: + 0;
for j - to B do
L Ag + Aq. + M(xx x ,+,, :
Aq: + Ag:
K
where K - 1 the -t element;
if arg max q (ar3; t1+ 5f A arg max [q*+1(a w'+1) Aq:] # y then // Predicted forgetting events
10
1;
Output: The precision, recall, and Fl-score of with IF as ground truth
D.5 FARTHEST POINT CLUSTERING WITH LPNTK
In this section, we illustrate more details about how we cluster the training samples based on far- thest point clustering (FPC) and lpNTK. Suppose that there N samples in the training set,
29

---

Published as a conference paper at ICLR 2024
1
2
2
3
8
4
4
4
5
6
7
8
8
c
8
8
9
q
a
a
9
Figure 13: Samples that are the most non-interchangeable to the targets in MNIST. The leftmost column is the target samples that are also shown in Figure 7 The remaining columns the most
non-interchangeable samples to the targets in each class.
30

---

Published as a conference paper at ICLR 2024
Figure 14: Sample that are the most non-interchangeable to the targets in CIFARIO. The leftmost column is the target samples that are also shown in Figure & non-intercaangeable samples to the targets in each class.
The remaining columns the most
31

---

Published as a conference paper at ICLR 2024
{(x, ( and the 1pNTK between a pair of samples is denoted k((æ,, y), (a',8)), The FPC algorithm proposed by Gonzalez (1885) running with our !pNTK is demonstrated Algorithm 3
Algorithm 3: Farthest Point Clustering with lpNTK
Input: Dataset ((0 yt) 1=1 The number of centroids M
(
Output: Cluter centroids (c.....,CMd List of samples indices in all clusters: (I.,,..., M
Ne 1;
// Nunber of established clusters // Centroid of the first cluster // List of sample indices in the first clsuter
f arg max; (a( Bi), (e);
L1 t + 01 c1/=1
while N₂
do
d 4 00, Cnew 6 -1;
11 1. Find the controid for the new cluster
for j - 1 No do
if minyeL, nl( , Mey)) (ay, yy)) < d then
+ minsel, k( (((ee)) yer ) ( Uy)); Gnew + arg mi, k(( ((( Ye, (zy:
10
No f No 1,eN, t Cnew, IN. t 0 // 2. Move samples that are closer to centroid to the new cluster for j f No 1
the
I1
12
for i Lj do
if (<(( vs), (Ie, Be,)) < n((2,, Vi), (Fewe VeN.)) then
L s Th \ (i):
IN. & LNN U (i):
To show that the distribution of clusters sizes are heavily long-tailed on both MNIST and CIFAR- 10, i.c. there
few large clusters and many small clusters, sort the clusters from FPC first by size, then show the sizes of the top-30 on MNIST and CIFARIO in Figure [5| It is straightforward to that most of the samples actually in the head cluster, ie. the largest cluster. There are a further 20 clusters containing more than one sample, then the remaining clusters all contain just single sample. This indicates that the cluster distribution is indeed long-tailed.
M 10% X N here. We
CIOUUT 100
(a) MNIST
(b) CIFAR-10
Figure 15: Number of samples in the top-30 clusters ranked by sizes on MNIST and CIFAR-10. The number of clusters equals to 10% of the original training set's size, and both used categories indexed 0 as an example.
E REDUNDANT SAMPLES AND POISONING SAMPLES
E. REDUNDANT SAMPLES
Suppose there are two samples æ; and D2 from the same class, and their corresponding gradient vectors in the INNTK feature space are drawn solid arrows in Figure 16 The 2² can be
32

---

Published as a conference paper at ICLR 2024
further decomposed into two vectors, æ1 which has the same direction as 22 and xi whose direction is perpendicular to 22, and both are drawn as dashed arrows in Figure [6 Since æ'j is larger than 22, this means that component of 2 is larger than 222 the direction of 2g. Further, this shows that learning #1 is equivalent to learning 22 (times some constant) and a hypothetical samples that is orthogonal 22. In this case, the sample 22 is said to be redundant.
#1
2
22
x'1
Figure 16: A hypothetical redundant sample (22) example.
E.2 POISONING SAMPLES
Data poisoning refers to a class of training-timie adversarial attacks Wang et al. (2022): the adversary is given the ability to insert and remove bounded number of training samples to manipulate the behaviour (e.g. predictions for some target samples) of models trained using the resulted, poisoned the name of "poisoning samples" here rather than "outliers" "anomalies" to emphasise that those samples lead to worse generalisation.
data. Therefore,
More formally, for a given set of samples T, if the averaged test accuracy of the models trained C X are defined as poisoning samples.
is statistically significantly greater than the models trained on T. the samples in T
To better illustrate findings about poisoning samples, we first illustrate hypothetical FPC re- sults, as shown in Figure 17 There are 5 resulted clusters, and the number of samples in each cluster is 2,2, 1, 1, Back to the three types of relationships defined in Section [3] samples in the same cluster (e.g. the blue dots) would be more likely to be interchangeable with each other, and samples from different clusters (e.g. the yellow, green, and red dots) would be more likely to be unrelated or contradictory.
Although those samples in the tail did not seem to contribute much to the major group, the interesting thing is that they are not always poisoning. That is, the poisoning data are inconsistent over the varying sizes of the pruned dataset.
Let's denote the original training set as T, and the pruned dataset as X. When a large fraction of data can be kept in the pruned dataset, e.g. [X|/|T| > 85%, removing some samples that are more interchangeable with the others, or equivalently from the head cluster, would benefit the test accuracy, as demonstrated Section 4.2 That is, in such case, the poisoning samples are the samples in the largest cluster, e.g. the blue dots in Figure 17
However, where only small fraction of data can be kept, e.g. 5% or 1%, we find that the poisoning samples are the samples from the tail clusters, e.g. the yellow/green/rred dot in Figure 17 This finding matches with the conclusions from Sorscher et al. (2022). To verify it, we first randomly sample 5% from the MNIST training set, and put them all together in training set T,. In the meantime, we sample the same amount of data only from the largest cluster obtained on MNIST, and put them all together in another training set T2. We then compare the generalisation performance of LeNet models trained with T, and T2, and we try two fractions, 1% and 5%. The results are shown in the following Figure T8
Many attempts have been made to define outliers or anomaly in statisties and computer science, but there common consensus of formal and general definition.
33

---

Published as a conference paper at ICLR 2024
cluster
öfuster
cluster 2
cluster
cluster 3
Figure 17: An example of farthest point clustering result.
MNIST Randem Samplngg Largest Quster
5% MMIST Rendrum famp
93
06
94
13
10
Taining Epech
Faining Esoch
(a) 1%
(b) 5%
Figure 18: Test accuracy over training epochs of models trained with X% data sampled with dif- ferent strategies. The lines are averaged across 10 different runs, and the shadow areas show the corresponding standard deviation. The plots show that sampling from the largest FPC cluster can lead higher generalisation performance when only small fraction of data can be kept in the pruned training sets.
As shown in Figure 18 in both 1% and 5% cases, keeping only the samples from the largest cluster obtained via FPC with INNTK lead higher test accuracy than sampling from the whole MNIST training set. This verifies our argument that the most interchangeable samples are more important for generalisation when only a few training samples can be used for learning.
Lastly, we want to give a language learning example to further illustrate the above argument. Let's consider the plural nouns. We just need to add have a few other rules for the regular nouns ending with e.g. -s, -sh, -ch. Whereas, there is no specific rule for irregular nouns like child or mouse. So, the irregular nouns are more likely to be considered as samples in the tail clusters, as they are more dissimilar to each other. For an English learning beginner, the most important samples might the regular nouns, as they can cover most cases of changing nouns to plurals. However, one continues to learn, it becomes necessary to remember those irregular patterns in order to advance further. Therefore, suppose the irregular patterns are defined as in the tail clusters, they may not always be poisoning for generalisation performance.
the end make regular nouns plural, and
34


Reviews:
[{"review_id": "1hxH6llMAK", "reviewer": "Reviewer_3vgc", "summary": "This paper proposed to incorporate label information into the Neural Tangent Kernel (NTK) and designed a kernel called lpNTK to study the interaction between training examples. The author suggested classifying the relationships between a pair of examples into three types --- interchangeable, unrelated, and contradictory --- based on the angles between the vectors represented in lpNTK. The author then used these concepts to analyze some phenomena and techniques of learning dynamics, such as learning difficulty, forgetting, pruning, and redundancy. The observations and analyses were supported by experiments on the MNIST and CIFAR10 datasets.", "questions": "- It is not completely clear to me why it is reasonable to fix the similarity matrix $\\mathbf{K}$. Isn't it that a pair of training examples can be similar or dissimilar during different stages of training? How can we obtain the model that performs the best on the validation set in applications like data pruning?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Disclaimer: I'm not very familiar with the literature and some technical details of NTK. I might be biased because other reviews are visible to me before I write mine.\n\n- The learning dynamics and learning difficulty is an important problem in many subfields of machine learning. The author provided nice theoretical tools for it based on NTK.\n- Incorporating label information is useful for analyzing many supervised learning tasks in a more fine-grained way. The use case of data pruning is reasonable and convincing. I believe that the proposed tools can be used to deepen our understanding of some methods for learning from noisy/imbalanced data.\n- This paper is well structured. The author raised intuitive hypotheses, asked clear questions, and then conducted reasonable experiments to verify them.\n- The author contextualized this paper well and discussed related work sufficiently.", "weaknesses": "- Maybe it's because I'm unfamiliar with the literature, but I feel that this paper can benefit from mathematically clearer definitions of some terms such as interaction and learning difficulty.\n- The author stated that \"contradictory samples are rare in practice\" but didn't explain why. I suspect that it's because the MNIST and CIFAR10 datasets used in experiments are relatively clean, and there are few ambiguous training examples. The conjectures in C.3 were nice, but I would expect more solid explanations or explorations.\n- The author did not discuss much about the limitations of this work.\n\nMinor issues:\n- Section 2.1: the abbreviation $\\mathbf{z} \\in \\mathbb{R}^K$ is misleading because I think $\\mathbf{z}$ is a $\\mathbb{R}^K$-valued function, not just a vector.\n- Rigorously, a simplex with $K$ values is $(K-1)$-dimensional, i.e., it should be $\\Delta^{K-1}$.\n- Since many methods for noisy label learning and selective prediction (classification with rejection) heuristically make use of the learning dynamics, it would be convincing to apply lpNTK to those applications. However, those can be future work directions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BXvkZKyEh1", "reviewer": "Reviewer_4TQg", "summary": "This paper enhances the Neural Tangent Kernel by integrating label information, which offers a more nuanced understanding of the interaction between samples compared to the existing eNTK method. The authors explore the relationship between lpNTK and eNTK, and use vector angles to classify samples into interchangeable, unrelated, and contradictory categories. This novel categorization facilitates a 'data-centric' improvement in model training. The idea is interesting, but there lack baselines to validate their proposed method.", "questions": "Please refer to Weaknesses.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The integration of label information into the Neural Tangent Kernel (NTK) represents a novel approach that enhances the characterization of sample interactions during optimization. And the sign approximation also makes sense.  \n2. The application of the proposed lpNTK is both reasonable and beneficial. It effectively validates the utility of lpNTK's mapping functions (vectors), demonstrating their practical effectiveness.", "weaknesses": "I have the following concerns:\n1. Concerning Theorem 1, the authors assert that 'the gap between lpNTK and eNTK will not be significantly different.' However, this seems contradictory to subsequent analysis and empirical studies presented. The paper's central theme appears to be the integration of label information for a more nuanced understanding of sample relationships. If the lpNTK kernel closely resembles the original eNTK, could the authors clarify how this supports the stated claim? This warrants further explanation.\n2. The categorization of samples into three groups mirrors the 'data-IQ' framework in Seedat et al. (2022), which also segments samples into easy, ambiguous, and hard categories. Data-IQ assesses prediction error and confidence throughout the training process, a concept seemingly echoed in this paper. I recommend that the authors draw comparisons with this methodology to highlight distinct aspects and contributions of their work.\n3. There lack baselines to validate the effectiveness of the proposed method for measuring sample similarity. For instance, the influence function is a known technique for understanding relationships between samples during training. A comparison with such established methods would provide a more robust validation of the proposed approach.\n4. It would be beneficial if the authors could include a computational complexity analysis of the lpNTK. This information would be crucial for understanding the practicality and scalability of the proposed method in different settings.\n\n[1] Seedat, N., Crabbé, J., Bica, I., & van der Schaar, M. (2022). Data-IQ: Characterizing subgroups with heterogeneous outcomes in tabular data. Advances in Neural Information Processing Systems, 35, 23660-23674.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bGBDTUZsy4", "reviewer": "Reviewer_9biR", "summary": "This paper aims to study the interaction between samples in supervised learning from a learning dynamics viewpoint. To that end, the authors propose a the labeled pseudo Neural Tangent Kernel (lpNTK), a new adaptation of the NTK which explicitly incorporates label information into the kernel. First, lpNTK is shown to asymptotically converge to the empirical Neural Tangent Kernel (eNTK). Then, the authors demonstrate how lpNTK helps to understand phenomena such as identifying and interpreting easy/hard examples and forgetting events. Finally, the paper shows a case study in which lpNTK is used to improve the generalization performance of neural nets in image classification via pruning and de-biasing.", "questions": "- Have the authors considered drawing connections between interchangeable and contradictory samples and forging / machine unlearning [1], i.e. by training on a specific point we could plausibly say that we have also optimized for another datapoint? \n\nOther questions embedded in Weaknesses above.\n\nI am willing to increase my score as part of the discussion phase if the authors can address my concerns.\n\nReferences:\n\n[1] Thudi, Anvith, et al. \"On the necessity of auditable algorithmic definitions for machine unlearning.\" 31st USENIX Security Symposium (USENIX Security 22). 2022.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper's main conceptual contribution of incorporating label information into the NTK is novel and interesting!\n- The connection to sample difficulty and forgetting events is an interesting use-case for the lpNTK and allows us to connect sample difficulty with training dynamics.\n- I found it pretty interesting that lpNTK allows for pruning and simultaneous utility improvements. This could open up another connection to selective prediction (learning a high-confidence subset of the distribution).\n- Related work appears sufficiently discussed.", "weaknesses": "- Should Eq (1) contain the sign operator wrapped around the last factor? In Section 2.2, it is stated that the paper does not use the whole error term but only the sign as shown in Eq (2). I am also not sure I was able to follow the explanation as to why the magnitudes should not matter. Could the magnitude be useful for ranking?\n- Although Figure 2 and the displayed evolution of distinct FPC clusters is insightful, I was wondering whether additional visualizations of the lpNTK would have been possible? \n- The results in Table 1 showing the forgetting events don't seem particularly impressive (especially on MNIST). Am I missing something here?\n- It would have been great if the authors had provided a visualization of some of the pruned samples. Are there any patterns present in pruned examples in particular?\n- It is evident that the authors tried really hard to fit the paper into the page limit. There are formatting artifacts in terms of very little vspace throughout the paper, especially towards the end of the paper (pages 7-9). I would strongly encourage the authors to reduce dangling words instead of resorting to these very evident formatting tricks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)