Data Valuation Without Training of a Model
Authors: Ki Nohyun
Hoyong Choi
Hye Won Chung
Venue: ICLR 2023 poster (2023)
Keywords: Data valuation
generalization error bounds
complexity-gap score
data pruning
training dynamics

Abstract: Many recent works on understanding deep learning try to quantify how much individual data instances influence the optimization and generalization of a model. Such attempts reveal characteristics and importance of individual instances, which may provide useful information in diagnosing and improving deep learning. However, most of the existing works on data valuation require actual training of a model, which often demands high-computational cost. In this paper, we provide a training-free data valuation score, called complexity-gap score, which is a data-centric score to quantify the influence of individual instances in generalization of two-layer overparameterized neural networks. The proposed score can quantify irregularity of the instances and measure how much each data instance contributes in the total movement of the network parameters during training. We theoretically analyze and empirically demonstrate the effectiveness of the complexity-gap score in finding `irregular or mislabeled' data instances, and also provide applications of the score in analyzing datasets and diagnosing training dynamics. Our code is publicly available at https://github.com/JJchy/CG_score.

Published as a conference paper at ICLR 2023
DATA VALUATION WITHOUT TRAINING OF A MODEL
Nohyun Ki; Hoyong Choi;; Hye Won Chung
School of Electrical Engineering
Korea Advanced Institute of Science and Technology (KAIST)
Daejeon, South Korea {kinohyun, chy0707, bwchungJkkaist.co
ABSTRACT
Many recent works on understanding deep learning try to quantify how much in- dividual data instances influence the optimization and generalization of a model. Such attempts reveal characteristics and importance of individual instances. which may provide useful information in diagnosing and improving deep learning. How- ever, most of the existing works on data valuation require actual training of a model, which often demands high-computational cost. In this paper, we provide a training-free free data valuation score, called complexity- score, which is a data- centric score quantify the influence of individual instances in generalization of two-layer overparameterized neural networks. The proposed score can quantify irregularity of the instances and measure how much each data instance contributes in the total movement of the network parameters during training. We theoretically analyze and empirically demonstrate the effectiveness of the complexity gap score in finding 'irreularr or mislabeled' data instances, and also provide applications of the score in analyzing datasets and diagnosing training dynamies. Our code is _ccore
publicly available at Ittps:: :tap::://gitee //ttthbbtttt/tt//// com/
INTRODUCTION
Creation of large datasets has driven development of deep learning in diverse applications including computer vision (Krizhevsky et al. 2012
Dosovitskiy et al.) 2021), natural language processing (Vaswani al. 2017; Brown al., 2020 and reinforcement learning (Mnih et al. 2015 Silver
iet al. 2016). To utilize the dataset in a more efficient and effective manner, some recent works have attempted to understand the role of individual data instances in training and generalization of neural networks. In (Ghorbani & Zou| 2019), a metric to quantify the contribution of each training instance in achieving a high test accuracy was analyzed under the assumption that not only the training data but also the test data is available. [Tiang et al. (2021) defined score to identify irregular examples that need to memorized during training, in order for the model to accurately classify the example.
All these previous methods for data valuation require actual training of model to quantify the role of individual instances at the model. Thus, the valuation itself often requires nigh-computational cost, which may contradict some motivations of data valuation. For example, in (Ghorbani & Zou, 2019 Jiang et al. 202T), to examine the effect of individual data instances in training, one needs to train a model repeatedly while eliminating each instance subsets of instances. In (Swayamdiptal et al. 2020 Toneva et al. 2019). on the other hand, training dynamics- the behavior of a model on each instance throughout the training-is analyzed to categorize data instances. When the motivation for data valuation lies at finding a subset of data that can approximate the full-dataset training to save the computational cost for training, the previous valuation methods might not be suitable, since they already require the training with the full dataset before one can figure out 'important" instances.
In this paper, our main contribution is on defining a training-free data valuation score, which can be directly computed from data and can effectively quantify the impact of individual instances in opti- mization and generalization of neural networks. The proposed score, called complexity-ee gap score, measures the gap in data complexity where a certain data instance is removed from the full dataset. The data complexity measure was originally introduced in Arora et al. (2019) to quantify the com- plexity of the full dataset, which was used in bounding the generalization error of overparameterized
"Equal contribution.

---

Published as a conference paper at ICLR 2023
two-layer neural networks trained by gradient descent. Different from that work, where the com- plexity of the full dataset was of main concern, our focus is on decomposing the effect of individual data instances in the training. and thus we newly introduce complexity gap score (CG-score). We theoretically analyze and empirically demonstrate that the CG-score can quantify 'irregularity' of instances within each class, and thus can be used in identifying atypical examples, either due to the inherent irregularity of the instance or mislabeled classification. We also demonstrate that the proposed score has close relation to 'learning difficulty' of the instances by analyzing the training dynamics of data instances. Our key contributions are as below:
Training-free data valuation: which leverage the information from training itself, we provide a training- -ree data valu- ation score, CG-score, which is the data-centric score quantify the effect of individual data instances in optimization and generalization of neural networks.
Different from previous methods for data valuation, most of
Geometric interpretation: We provide analysis that the CG-score can measure irregularity of each instance, i.e., it measures the average 'similarity' of an instance to the instances of the same class and the average 'dissimilarity" the instances of different classes.
Effectiveness of the score: We empirically demonstrate the effectiveness of the CG-score in data valuation. We show that pruning data instances with small CG-score does not significantly degrade the generalization capability of a model, e.g., for CIFAR-10 we can prune 40% of the data with less than 1% of drop in test accuracy. Our scoring method is especially useful in data pruning, since different from other scores, which require the training with the full dataset, our method does not require any training of model.
Application of the score; We provide potential applications of the CG-score in analyzing datasets and training dynamics. We analyze the histograms of the CG-score for various datasets demonstrate that the CG-score can measure irregularity of the instances. We also demonstrate that the instances with higher CG-score are 'difficult' examples, which are learned slowly by the models, by comparing the loss and test accuracy curves and the evolution of Neural Tangent Kernel (NTK) submatrices of lowes/highest- groups
RELATED WORKS
Different from many existing works where the effect of datasets model training is analyzed as whole, some recent works have focused on understanding the impact of individual data instances. Ghorbani & Zou 2019); [won al. (202T) defined 'Data Shapley', to evaluate the value of each data instance, by measuring the average gap in performances when an instance is held-out from any subsets of given training data. Jiang et al. (022)) defined consistency score (C-score) of each instance by estimating the prediction accuracy of the instance attained by the model trained with the full dataset except the instance. Both Data Shapley and C-score require multiple trainings of model to compute the scores. Another main branch uses the training dynamics to identify 'dif- ficult' instances for classification, either due to irregularity or mislabeling, by measuring different forms of confidence, stability or influence in the decision of the networks throughout the training Toneva et al. 2019 Swayamdipta et al.) 2020, Pruthi et al. 2020). In (Baldock et al., 202I). the computational difficulty of an instance defined the number of hidden layers after which the networks' prediction coincides with the prediction at the output. With application of robust learn- ing, some works quantify the difficulty of each instance by a 'margin' from the decision boundary (Zhang et al.] 2021). CRAIG (Mirzasoleiman et al. 2020)p finds valuable subsets of data as core- sets that preserve the gradient of the total loss. All these previous methods are demonstrated to be effective in at least one or more applications of data valuation, including data pruning (Paul al. [021 Swayamdipta et al. [2020) |020] Agarwal et al. 2022 Feldman & Zhang, 2020). importance- based weighted sampling (Chang et al. [017 Koh & Liang 2017). noise filtering (Li et al.) 2020) Lee et al. 2019b Kim et 2021). robust learning (Ren et al.) 2018 Pleiss et al. (020), out-of- distribution generalizations (Swayamdipta et al., 2020) or diverse sample generalization (Lee et al.) 2021). However, all these methods require the training of model with the full dataset (at least for a few optimization steps). Recently, some works try to evaluate different subsets of training data by utilizing generalization error bound, induced by the NTK theory of neural networks (Wu et al. 2022] Zhang & Zhang 2022). However, these methods do not provide a computationalll-effttooo quantity the effect of individual data instances. Our data valuation method, on the other hand, is a data-centric method that can be efficiently calculated from data only without training of model.
way to
2

---

Published as a conference paper at ICLR 2023
3 COMPLEXITY-GAN SCORE: DATA VALUATION WITHOUT TRAINING
In this section, we introduce a new data valuation score, called complexity-gen gap score, based on the analysis of overparameterized two-layer neural networks from Arora et al. (2019).
3.1 PRELIMINARIES: DATA COMPLEXITY MEASURE IN TWO-LAYER NEURAL NETWORKS
We first review the result from Arora et al. 2019),, where a two-layer neural network trained by ran- domly initialized gradient descent is analyzed. Consider a two-layer ReI.U activated neural network having m neurons in the hidden layer, of which the output is fw.a(x) = /m Er=1 a, (w, x) where x E Rd is the input, W,...., Wm F² are weight vectors in the first layer, a1..... am E R are weights in the second layer, and o (xx) m0x .:) is the ReL.U activation function. Let W E TR. Assume that the network parameters are
(wi...., w.. E Rdxm and = (a1,-..,
randomly initialized as (0) ~ NNO,, 1. axxd and a, ~ -1, Vr E [m]. where K E (0. 1] is the size of random initialization. The second layer a is then fixed and only the first layer W is op- timized through gradient descent (GD) to minimize the quadratic loss, (WW)
(v: Σ u,) ),
where u, fw (x;) and {xx, ) is the dataset drawn i.idd. from an underlying distribution
(4))(()) where 7) > 0 is the learning rate. The output of the network for the input x, at the k-th iteration is denoted by u, = (x.))),(xx)) For simplicity, it is assumed that ||x|| = 1 and |// s 1.
D. The GD update rule can be written w, (k + 1) (k)k) = -1j Bw,
The data complexity measure governing the training of the two-layer ReLU activated neural network is defined in terms of the following Gram matrix H E R associated with ReLU activation:
H Wo [x] 1,1(w") x, 2 O, X, 2 07] x x arccos (x. x²))
(I)
2T
In Arora et al. 2019). a complexity measure of data was defined as y (H where y (g1..... .un))...))............... and it was shown that this measure bounds the total movement of all neurons in W from their random initialization. Moreover, the data complexity measure bounds the generalization error by restricting the Rademacher complexity of the resulting function class. In the following, write the eigen-decomposition of H as H = >x A where A are ordered such that A1 2 A2 ... Further, assuming An. 2 An > O, we can write = (x)
Theorem 1 (Informal version of (Arora et al., 2019)). Assume that Amin (H²) An 2 Ao 0. For sufficiently large width m, sufficiently small learning rate n > and sufficiently small random initialization O. with probability at least å over the random initialization, have
a) Bound in loss: lly - u-(k)ll2 =
Σ (1 - ) 24 (v]x)² + small constant,
b) Bound in total movement of neurons: (W))) W(0)|rr S Vy ( + small constant,
log Aod
c) Bound in population loss: E(x.,) ((ln))/D((((//wwaaaa S y (T(3))--3 +0
n
where a) and b) hold for all iteration k 2 0 GD, and c) holds for k 2 (1/((n))) log(n/5)).
This theorem shows that the label vector y is aligned with top eigenvectors of H i.e., (v y) is large for large X then the loss decreases quickly and the total movement of neurons well as the generalization error is small. Thus, the data complexity measure y (H*) 'y captures the complexity of data governing both the optimization and generalization of the overparameterizee two-layer neural networks. However, this quantity captures the complexity of the whole data. To decompose the effect of individual instances, we newly define a complexity gap score.
3.2 COMPLEXITY-GE SCORE AND TRAINING DYNAMICS
We define the complexity gap score (CG-score) of (x;, yi) as the difference between the data com- plexity measure when (x,, 31) is removed from given dataset {(x,, 9:)
CG(i) y (H (H,
(2)
3

---

Published as a conference paper at ICLR 2023
where y-, is the label vector except the i-th sample point and H is the (n 1) (n 1) matrix obtained by removing the i-th row and column of H
We first emphasize that the proposed score can be easily calculated from given data without the need of training neural networks, as opposed to other data valuation scores requiring either a trained neural network statistics calculated from training dynamics. Yet, the proposed score captures two important properties on the training and generalization of data instance, implied by Theorem [
1. An instance (X,, y/ with a large CG-score is a 'difficult' example, in the sense that remov- ing it from the dataset reduces the generalization error bound by large amount, which implies that the dataset without (x,, Us) is much easier to be learned and generalized.
2. An instance (x,, V/) with larger CG-score contributes more the optimization and drives the total movement of neurons by a larger amount, measured by [[(kk) (O)]..
We next discuss the computational complexity of calculating the CG-score. To calculate {CG(i)) need to take the inverse of matrices H and H for all i [ni], which requires Onn²) complexity when we use general O algorithm for the matrix inversion. By
using Schur complement, however, we can reduce this complexity to O(n²). Without loss of gener- ality, we can assume n. Denote H Th and (H~))-1 by
H F- g:
(H h
H
H (-
di)
(3)
where H have g.
(H
E R (n- ()
gi h; E R- and c₁ d, E R. From H H (H
In.
n-
H mー
c. 0, i.e., h
g
By Schur complement,
H
which is equal to (H for i n, be calculated
H = (H (H d7 hT
Since we have
y (H ( = y ルーー y;h, y-i + v.y I,, + 22d..
(5)
y I (HC) y y dy [y_ h:)?
the CG-score, CG) equation can be calculated by
CG(i) = - dy h.) 2y: + v2 = (yT,, Vd. vi vvVVd
(6)
Thus, CG(i) can be calculated by the n-th column (h,, d,) of (H without the need of caleu- lating (Ho) when i = n. The case for general i a n can also be readily solved by permuting the i-th row and column of o into the last positions.
Correlation to other scores We show relation between our score and other data valuation scores that require the training of neural networks. Toneva et al. (2019) define 'the forgetting score' for each training example as the number of times during training the decision of that sample switches from correct one incorrect one. Paul et al. (202T), on the other hand, suggest the GraNd score, which is the expected loss gradient norm Elll (u(k), y) [I] to bound the contribution of each training example to the decrease of loss on any other example over a single gradient step. The GraNd score is further approximated (under some assumptions) by the E1.2N score, defined to be Elyy - u(k)]] where u(k) is the output of the neural network for the sample (xr y) at the k-th step. Since ly u(k)), if rescaled, is upper bound on 0-1 loss, Es ly u(k) -ykk(k]] upper bounds forgetting score after rescaling. Thus, an example with a high forgetting score will also have high GraND score and high EL2N score averaged over multiple time steps. We next relate our complexity gaa score to (v - u(k)), and thus to all the three previous scores defined using training dynamics.
It was shown in (Arora et al. 2019) that for the overparameterizee two-layer networks trained by GD, the gap between the label vector and the network output at the step & can be approximated as y u(k) ~ // Thus, we get Ee y u(k) R Dx H y'y (HH -
4

---

Published as a conference paper at ICLR 2023
Table Spearman's rank correlation between CG-score (CG' -score) and other data valuation scores.
Correlation btwn. CG-score and Forgetting
Correlation btwn. CG' CG'-score and C-score
Datasets
C-score
E1.2N
Forgetting
EL.2N
CIFAR-10
0.557
0.432
0.365
0.115
0.110
0.136
CIFAR-100
0.529
0.289
0.356
0.243
0.090
0.177
Without loss of generality, consider i n. Then, the accumulated difference between y; and uy (k(k) over lt can be approximated as
Σ (u - (k)) so (b.y-1 v.d:) /n= = (yI,bi/Vdd vVVV vd./n.
Note that both the right-hand side of equation 7 and CG(i) in equation 6 depend on the term (yI, h..hh//v /dd + vivd)) Thus, we can expect that CG will be correlated with the scores related to training dynamics, including the forgetting score, GraND score and EL,2N score. Different from those scores, our score can be directly calculated from the data without training of model.
Inversion H is an effective step the definition of CG(i) equation 2 we use the inverse of Ho to measure the alignment of the eigenvectors of H with the label vector One could suggest another score that directly uses H instead of (H~) )_ which can save the computation for inversion. However, we argue that the score calculated by using (Ho)-1 includes more information than the score calculated by H due to the reason described below. Let us define CG' (f) :=
HHHy-yy - yjj Without loss of generality, assume i Then, CG) (g. y- +
efez where g: (H*) 1.(n-1).. and G H defined in equation 3 Since c = 1/2 for all for y/ +1 we have CG'
i E [n] from the definition of H in equation and y?
2(y, (H y) 1/2) 1/2. By using the approximation y u(k) ~ (I 1yHH00* )oy from Arora et al. 2019). we have u(1) = y "H when k = 1, which implies u(1) = m Thus, (G y (1) + 1/2. Note that an instance (x, y4) has large CG'( ya (1) is large. i.e.,
the network output (1) after 1-time step has the same sign as the targeted label ys E f- and has large magnitude. Thus, CG'(i) measures how fast the training instance can be learned by the neural network. Different from Ci'(i), our original score CG(i) is correlated with the accumulated error between Yi and u, (k) averaged over the training shown in equation 7 Thus, our original score (i), using the inverse of H reflects the statistics averaged over the whole training steps.
In Table I we compare the Spearman's a rank correlation between CG-score/CG'ssoo -score and other data valuation scores including C-score (Jiang et al.) 202T), forgetting score (Toneva et al. 2019) and EL2N score (Paul et al. 2021) for CIFAR-I0/ 1000 datasets We can observe that CG-score has higher correlations with the previous scores compared to those of -score. In the rest of this paper, we focus on the CG-score for our data valuation score.
3.3 GEOMETRIC INTERPRETATION OF THE COMPLEXITY GAP SCORE
We next provide geometric interpretation for the CG-score. For the sake of simplicity, we consider
binary dataset with 7 samples having = 1 and 2/2 samples having =11 We further assume
that H = - if yı = y, and E[ = q yı # Yj for some |pl g//. Note that the diagonal
entires H = 1/2 for all i E [n). Thus, HH can be decomposed as H = ( - p) I, + S
(p
where S is a block matrix with S =
2 In/2. and the resulting eigenvalues of TE| x
1 P
are (p+g)m + (1 p). (p-g)m 2
p) and ( p) with multiplicity (n -2). When p O(g)
and p = (1/n), the matrix E 00 (1 (1/2) I,. From the representations of H and (H in
c g, (H^))= assuming H s (1/2) and using c; = 1/2, we can write h. = - -g. By using this approximation, our CG-score in equation 6 can
equation 3 and the implied relation h
'The way we calculate CG-scores for multi-lahel datasets is explained in Appendix To reduce the computation complexity, calculated the scores by sub-sampling data and averaging them over multiple runs.
5

---

Published as a conference paper at ICLR 2023
200
175
150
125
100
75
1.0
Class (nose) DecBound
50
0.5
0 25 150125150115.00
Rist cimension Input Input
Rest dimension of
(a) Heat map of (H*))=1
(b) CG-score (elean)
(c) CG-score (10% label noise)
nn-i for 200 indices. We plot 200 indices only for clear visualization. (b) Scatter graph of CG-Score for two groups of samples from 3000-D Gaussian distributions having the same mean except the first dimension, where class 1 has mean +1 (red) and class 2 has mean -1 (blue). Samples near the boundary (x1 = 0) tend to have higher CG-score. (c) Same plot as (b) with 10% label noise. Samples with label noise (marked by plus symbol) tend to have higher CG-score.
Figure I: (a) Heat map of (H²))-
be approximated as
CG(i) di dy 2y h.) + v.d, x
(y
since d, R. 2 and of = 1. Since y I,g:) EjE( (j H E jj((ni H and thus (y g:)] (p-g)m = o11) assuming p = @(2) and o(1/1)
(m), , the second term - 8y, (y
becomes much larger than the first term, which is proportional to (y, g.))²² Thus, -8, (y .gs) the main term that determines the order of (CG(1)) Note that y: (g:) measures the gap be-
tween E H and [jE(In)u H Since H = x x, urccos(xx xx)) 3/4 (y
2r
measures the gap between the average similarities of x; with other samples {x,) of the same class y₁ y/ and that with samples of the different class yj * yí, where the similarity measured by the cosine between the two samples (x,, X3) multiplied by the chance that ReLU is activated for both the samples. Thus, we can expect two important trends regarding the CG-score:
1. Regular vs. irregular samples: If a sample (x,, y:) is 'regular' sample representing the class in the sense that it has a larger similarity with other samples of the same class than samples from the different class, then it will have a large [y_i) resulting in lower CG-score due to the minus sign. On the other hand, if sample (x,, yi) is 'inregular' in the sense that does not represent the class and has a small similarity with the samples of the same class, then (y(y.g will be small, resulting in a higher CG-score.
2. Clean label vs. noisy label: A sample with label noise tends to have large CG- score since the order of two terms in subtraction at (y Lje((n)u=y) H
[je(www Hi is effectively switched for label-noise samples. Thus, (y_ tend be negative for a sample with label noise, while is positive for clean-label samples.
We empirically demonstrate the above two trends by controlled experiment. Consider two 3000- dimensional Gaussian distributions with a fixed covariance matrix 0.25/ a000 and different means (1,0,...0 0) and (-1, 0,.,,,,.... 0). representing class +1 and-1, respectively. We generate 1000 samples from each class. We first check whether the structural assumptions on H hold with this synthetic dataset. In Fig. Ial we observe that (H*) can be well approximated by 21n-1. and thus the approximation for CG(i) in equation 8 may hold well. We then examine the correlation between the CG-score and the sample value the first dimension. In Fig. [b] we can observe that instances = 0 have higher CG-scores. This shows that irregular samples, e.g.,
near the decision boundary samples near the boundary of the two classes, indeed have higher CG-scores. We further modify the generated samples by randomly flipping the labels of 10% samples and re-calculate the CG-scores of all the samples. As shown in Fig. Ic the samples with label noise tend to have higher CG- scores,,, agreeing with our intuition. In Appendix SB we further discuss discriminating mislabeled data and atypical (but useful) data by using CG-score, and also show high/low-scoring examples for public datasets including MNIST, FMNIST, CIFAR-10 and ImageNet in Appendix $C

---

Published as a conference paper at ICLR 2023
FMNIST
CIFAR-10
CIFAR-10D
Pruning low vslun cata
92-4
00.3
ELSN
96.0
Pergeting
Pegeting
censeet
Tel dinaee
Tull sooret
Portan aroanae.
102
60
60
Partic oftinn
21 Poiton of
(a) Pruning low-scoring examples first. Better score maintains the test accuracy longer.
Pruning high value data
OCacen
0,26
0.34
Kander
Mareo
Randonn
(h) Pruning high-scoring examples first. Better score makes the rapid performance drop.
Figure 2: Pruning experiments with FMNIST (left), CIFAR-10 (middle) and CIFAR-100 (right). Only CG-Score does not require any training of the model to calculate the scores, but it achieves competitive performances and outperforms the random baseline.
(a), CG-score maintains the test accuracy up significant removing portions; in (b), the test accuracy drops most rapidly for CG- score since the examples with high CG-score are essential in generalization of the model.
DATA VALUATION THROUGH COMPLEXITY GAP SCORE
4.1 DATA PRUNING EXPERIMENTS
To evaluate the ability of the CG-score in identifying important examples, we design data pruning experiments, similar to those in Ghorbani & Zou (2019); Paul et al. (2021). ) We evaluate our score on three public datasets, FMNIST, CIFAR-1O/TON and train ResNet networks (He al. 2016), ResNet18 for FMNIST and CIFAR-IO 10 and ResNet50 for CIFAR- --0AR-100&A dataset, respectively. As base- line methods for data valuation, we use three state-of-the-as scores, C-score (Jiang et al. 202 EL2N (Paul et al. )021), and Forgetting score (Toneva et al. 2019), all of which require training of models for computation. On the contrary, our score a data-centric measure and independent on the model. More details the baselines and experiments are summarized in Appendix $D
In Figure 2 the first row shows the test accuracy of the model trained with different subset sizes when low-scoring (regular) examples are removed first, while the second row shows the similar result but when high-scoring (irregular) examples are removed first. We report the mean the result after five independent runs, and the shaded regions indicate the standard deviation. The gray line (full dataset) represents the results when all data is used, while the red curve (random) represents the results when examples randomly removed. We networks maintain the test accuracy up to significant removing portions, i.e., 40% for CIFAR-10 and 20% for CIFAR-I00 with less than 1 test accuracy drop. Our CG-score, which does not require any training of a model, can achieve competitive performances as the other baseline methods and also significantly outperforms the random baseline. When removing the high-scoring examples first, the test accuracy drops most rapidly for the CG-score curve, implying that examples with the high CG- are essential part of the data governing the generalization of the model.
observe that when removing low-scoring examples first,
We show the effectiveness of CG-score in more complicated models and also in fine-tuning by reporting the data pruning experiments at DenseNetBC-10n 100 (Huang et al., 2017) and Vision Trans- former (ViT) (Dosovitskiy al., (021) in Appendix $ We also compare CG-score with two more baselines, TracIn (Pruthi et al. 2020) and CRAIG (Mirzasoleiman al. 2020), Appendix $F
4.2 DETECTING LABEL NOISE
In Section 3.3 we analyzed the CG-score and showed that the examples with label noise tend to have higher CG-score. We next empirically investigate the ability of the CG-score in detecting label noise
7

---

Published as a conference paper at ICLR 2023
muaieee modoc sata Nound/No
CIPAR100
Clea
Noow latel
0.05
Ncha
Cieon
0.00
0.05
80
3.000
0.04
0.02
0.03
R.24
40
0.00
Bunden
20
0.09
05 500rs
150
200
40
sore
120
30
30
of datt chocks))))
(a) Density of CG-score for clean vs. label-noise
(b) Fraction of detected label noise
Figure 3: (a) Density of CG-score for clean (80%) vs. label-noise (20%) examples. Examples with label noise tend to have higher CG-score. For FMNIST (left) dataset, the CG-score histograms betwen clean and label-noise groups are better separated than those for CIFAR-100 100 (right). (b) Fraction of label noise (y-axis) included the examined portion (r-axis) for 20% label noise. CG- score (blue) achieves better noise detectability for FMNIST than for CIFAR-100.
by artificially corrupting 20% of instances in FMNIST and CIFAR- 100 with random label noise. We first examine the distribution of the CG-scores for each dataset after the corruption in Figure 3a] We can observe that for both datasets, the examples with corrupted labels (orange) tend to have higher CG-scores than those with clean labels (blue). For relatively simpler dataset, FMNIST (left), the CG-score histograms can be more clearly separable between the clean and noisy groups compared to more complex dataset, CIFAR- 100 (right). With this observation, CG-score can have a better detectability of label noise for relatively simpler datasets.
anticipate that the
We evaluate the noise detectability of the CG-score by checking varying portion of the examples sorted by the CG-score (highest first) in Fig. 3b] The curves indicate the fraction of noisy examples included in the examined subset. We compare our score with two other scores, Forgetting score and EL2N. as well as a random baseline and the oracle. We can observe that the CG-score achieves the best performance, near that of the oracle, for FMINST, and competitive performances for CIFAR- 100. In the plot, we also compare the performance of the CG-score with that of 'Partial CCore, which is a new score defined by a sub-term of the CG-score. In the CG-score in equation 3 we have three terms, but only the second term 2y;(y I h;) uses the label information of the data (x+, J:)- Thus, we examined the ability of this term only, defined as the 'Partial CG-score', detecting the label noise, and found that the CG-score and partial CG-score have similar performances in detecting label noise, which implies that the label-noise detectability of the CG-score mainly comes from the term 2y, (y h.). More experiments with higher noise rate are reported in Appendix SG
COMPLEXITY- GAP SCORE AND DEEP LEARNING PHENOMENA
We next demonstrate that the CG-score can capture 'learning difficulty" of data instances.
5.1 COMPLEXITY GAP SCORE CAPTURES LEARNING DIFFICULTY
It has been widely observed that there exists an order of instances in which a model learns to classify
the data correctly and this order is robust within model types (Wu et al. 2021). Many previous scoring functions use this type of observation and define the 'difficulty" of a given instance based on the speed at which the model's prediction converges (Toneva al. 2019 S Swayamdipta et al., 2020) Our data-centric CG-score is originally defined based on the gap in the generalization error bounds as in equation but it also reflects the convergence speed of the instance, as analyzed in equation] 7 We empirically demonstrate this relation by analyzing the training dynamics of CIFAR-10 10 dataset trained R network. We first sort the data instances in ascending order using the CG-score and divide the data into 10 equal-sized subgroups. We then measure the mean of loss and training accuracy for the 10 subgroups as training progresses. Fig. 4a and Fig. 4b show the mean of loss and the training accuracy throughout the training for the 10 subgroups, respectively, where the blue color represents the low-scoring groups and the red color represents the high-scoring groups. We can observe that the mean loss and accuracy converge faster for low-scoring groups, while it takes longer to converge for high-scoring groups This indicates that the CG-score is highly correlated with the 'difficulty' of example measured by the learning speed at model.
8

---

Published as a conference paper at ICLR 2023
2.5
100
Loss
2.0
Accuracy1%)
Korel velecity
1.5
1.0
0.5
0.0
25
50
75
100 125 Epoch
150
175 200
0
25
50
75
100 Epach
125
150
175
200
0
25
50
75 100
150 175 200 Epoch
125
(a) Loss mean
(b) Accuracy
(c) Kernel velocity
Training dynamics measured for each subset of CIFAR-10 examples, grouped by the CG- score. The line color varies over groups, where the blue lines include low-scoring examples and the red lines include high-scoring groups. (a) and (b) Mean loss and accuracy for subgroups of CIFAR- 10 data, sorted by the CG-score, trained on ResNet18. The mean loss and accuracy converge slowly for high-scoring groups (red lines). (c) Kernel velocity of CIFAR- 10 examples grouped by the CG- score. The Kernel evolves with a higher velocity for high-scoring groups throughout the training.
Figure 4:
5.2 DATA SAMPLES DRIVING MOVEMENT OF NEURONS
We next investigate the relation between the CG-score and the evolution velocity of the data- dependent Neural Tangent Kernel (NTK) (Fort et al. 2020). NTK has been widely used to approxi- mate the evolution of an infinite-width deep learning model via linearization around initial weights, when the network is trained by gradient descent with a sufficiently small learning rate (Jacot et al.] 2018). The main idea is that in the limit of an infinite width, the network parameters do not move very far from its initialization throughout the training, so that the learning process can be approxi- mated by a linear process along the tangent space to the manifold of the model's function class at the initialization (Lee et al. (2199).. However, as observed in Fort et al. (2020), for finite-width network, the tangent kernel is not constant but it rather rapidly changes over time, especially at the beginning of the training. To quantify this change, Fort et al. (2020) addressed the data-dependent Kernel Gram matrix, which the Gram matrix of the logit Jacobian, and defined the Kernel velocity as the cosine distance between two NTK Gram matrices before and after one epoch of training. In Paul et al. (02TT), the Kernel velocity was used to evaluate the subgroups of data instances to figure out the subgroup driving the learning and the change in the NTK feature space. We conduct similar experiments for subgroups of data, divided according to our CG-score. Fig. Aclshows the Kernel ve- locities for 10 different subgroups of CIFAR-10 data trained in ResNet18. Each group composed of 125 consecutive instances from each level, where the level is defined by dividing the full dataset, sorted in ascending order by the CG-score, into 10 groups The higher level (red) is composed of instances having higher CG-scores, while the lower level (blue) is composed of instances having lower CG-scores. We can observe that the samples with high CG-score (red) maintains higher Ker- nel velocity throughout the training. which means that NTK Gram matrix evolves by a larger amount for the samples of high CG-score. Thus, we can hypothesize that the instances with high CG-score are 'difficult" examples the network may struggle to optimize and try to fit throughout the training.
6 DISCUSSION
We proposed the CG-score, a data-centric valuation score, quantify the effect of individual data instances in optimization and generalization of overparameterized two-layer neural networks trained by gradient descent. We theoretically and empirically demonstrated that the CG-score can identify 'irregular' instances within each class, and can be used as a score to select instances essential for generalization of model or in filtering instances with label noise. We also showed the close relation between the CG-score and learning difficulty of instances by analyzing training dynamics. Interest- ing open problems related to the CG-score include 1) providing theoretical justification of the score for more general deep neural networks and 2) improving the score by modifying the definition in terms of 'features' of data instances. In Appendix ş we provide further discussion for 'feature- space CG-score" and report experimental results, demonstrating the effectiveness of the score.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENT
This research was supported by the National Research Foundation of Korea under grant 202IRICICI I 1088539, and by the Ministry of Science and ICT, Korea, under the ITTP (Institute for Information and Communications Technology Panning and Evaluation) grant No.2020-0-0062.
REFERENCES
Chirag Agarwal, Daniel D' D'suuza, and Sara Hooker. Estimating example difficulty using variance of gradients. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recog- nition, 2022.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of op- timization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, 2019.
Robert Baldock, Hartmut Maennel, and Behnam Neyshabur. Deep learning through the lens of example difficulty. Advances in Neural Information Processing Systems, 2021.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In Advances in Neural Information Processing Systems, 2020.
Haw-Shiuan Chang, Erik Leared-Miller, and Andrew McCallum. Active bias: rate neural networks by emphasizing high variance samples. In Advances in Neural Information Processing Systems, 2017.
Training more accu-
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In JEEE Conference on Computer Vision and Pattern Recognition, 2009.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszko- reit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale. In International Conference on Learning Representations, 2021.
Vitaly Feldman and Chiyuan Zhang. What neural networks memorize and why: Discovering the long tail via influence estimation. In Proceedings of the 34th International Conference on Neural Information Processing Systems, 2020.
Stanislav Fort, Gintare Karolina Dziugaite, Mansheej Paul, Sepideh Kharaghani, Daniel M. Roy, and Surya Ganguli. Deep learning versus kernel learning: An empirical study of loss landscape geom- etry and the time evolution the neural tangent kernel. In Proceedings of the 34th International Conference on Neural Information Processing Systems, 2020.
Amirata Ghorbani and James Zou. Data shapley: Equitable valuation of data for machine learning. In International Conference on Machine Learning, 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In IEEE Conference on Computer Vision and Pattern Recognition, 2016.
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q. Weinberger. Densely connected convolutional networks. In 2017 IEEE Conference on Computer Vision and Puttern Recognition (CVPR), 2017.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kemnel: Convergence and gen- eralization in neural networks, Advances in neural information processing systems, 2018.
10

---

Published as a conference paper at ICLR 2023
Ziheng Jiang, Chiyuan Zhang, Kunal Talwar, and Michael C Mozer. Characterizing structural reg- ularities of labeled data in overparameterized models. In International Conference on Machine Learning. 2021.
Taehyeon Kim, Jongwoo Ko, Sangwook Cho, JinHwan Choi, and Se- Young Yun. FINE samples for learning with noisy labels. In Advances in Neural Information Processing Systems, 2021.
Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In Proceedings of the 34th International Conference on Machine Learning, 2017.
Alex Krizhevsky, llya Sutskever. and Geoffrey Hinton. Imagenet classification with deep convo- lutional neural networks. In Advances in Neural Information Processing Systems, 2012.
Yongchan Kwon, Manuel A. Rivas, and James Zou. Efficient computation and analysis of dis- tributional shapley values. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, 2021.
Jachoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks any depth evolve as linear models under gradient descent. Advances in neural information processing systems, 2019a.
Jinhee Lee, Haeri Kim, Youngkyu Hong, and Hye Won Chung. Self-diagnosing gan: Diagnosing underrepresented samples in generative adversarial networks. Advances in Neural Information Processing Systems, 34:1925- 1938, 2021.
Kimin Lee, Sukmin Yun, Kibok Lee, Honglak Lee, Bo Li, and Jinwoo Shin. Robust inference via generative classifiers for handling noisy labels. In Proceedings of the 36th International Conference on Machine Learning, 2019b.
Junnan Li, Richard Socher, and Steven C.H. Hoi. Dividemix: Learning with noisy labels as semi- supervised learning. In International Conference on Learning Representations, 2020.
Ilya Loshchilov and Frank Hutter. SGDR: Stochastic gradient descent with warm restarts. In Inter- national Conference on Learning Representations, 2017.
Baharan Mirzasoleiman, Jeff Bilmes, and Jure Leskovee. Coresets for data-efficient training of ma- chine learning models. In Proceedings of the 37th International Conference on Machine Learning, 2020.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Belle- mare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wier- stra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, 2015.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high- performance deep learning library. Advances in neural information processing systems, 2019.
Mansheej Paul, Surya Ganguli, and Gintare Karolina Dziugaite. Deep learning on a data diet: Find- ing important examples early in training. Advances in Neural Information Processing Systems, 2021.
Geoff Pleiss, Tianyi Zhang, Ethan Flenberg, and Kilian Q Weinherger. Identifying mislabeled data using the area under the margin ranking. In Advances Neural Information Processing Systems, 2020.
Garima Pruthi, Frederick Liu, Satyen Kale, and Mukund Sundararajan. Estimating training data influence by tracing gradient descent. In Advances in Neural Information Processing Systems, 2020.
Mengye Ren, Wenyuan Zeng, Bin Yang, and Raquel Urtasun. Learning to reweight examples for robust deep learning. In Proceedings of the 35th International Conference on Machine Learning, 2018.
11

---

Published as a conference paper at ICLR 2023
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Mare Lanctot, et al. Mastering the game of go with deep neural networks and tree search. Nature, 2016.
Ben Sorscher, Robert Geirhos, Shashank Shekhar, Surya Ganguli, and Ari S. Morcos. Beyond neural scaling laws: beating power law scaling via data pruning. In Advances in Neural Information Processing Systems, 2022.
Swabha Swayamdipta, Roy Schwartz, Nicholas Lourie, Yizhong Wang, Hannaneh Hajishirzi, Noah A. Smith, and Yejin Choi. Dataset cartography: Mapping and diagnosing datasets with training dynamics. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, 2020.
Mariya Toneva, Alessandro Sordoni, Remi Tachet des Combes, Adam Trischler, Yoshua Bengio, and Geoffrey J. Gordon. An empirical study of example forgetting during deep neural network learning. In 7th International Conference Learning Representations, 2019.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Eukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Infor- mation Processing Systems, 2017.
Xiaoxia Wu, Ethan Dyer, and Behnam Neyshabur. When do curricula work? In 9th International Conference Learning Representations, 2021.
Zhaoxuan Wu, Yao Shu, and Bryan Kian Hsiang Low. DAVINZ: Data valuation using deep ral networks at initialization. In Proceedings of the 39th International Conference on Machine Learning. 2022.
Jingfeng Zhang, Jianing Zhu, Gang Niu, Bo Han, Masashi Sugiyama, and Mohan Kankanhalli. Geometry-aware instance-reweighted adversarial training. In 9th International Conference on Learning Representations, 2021.
Rui Zhang and Shihua Zhang. Rethinking influence functions neural networks in the over- parameterized regime. Proceedings of the AAAI Conference Artificial Intelligence, 2022.
12

---

Published as a conference paper at ICLR 2023
A EXTENSIONS TO MULTI-CLASS COMPLEXITY GAP SCORE
In this section, we explain the details of how we calculate the CG-scores for multi-label public
datasets.
A.1 CALCULATION OF CG-SCORE FOR MULTI-LABEL DATASETS
In defining the CG-score equation we assumed the binary datasets y }+1} with inputs hav- ing a fixed norm |x||| = 1. To calculate the CG-score for multi-label (k-class) public datasets, we first normalize all the imputs to have ||x|| 1. We then calculate the CG-score for examples of each class j E [b], assuming that all the examples from class j have label +1 and the rest of the examples from any other classes have label I. In detail, let y (y1, 1/: v2:-..>. Un) E (,, k- be the label vector for n data instances and, without loss of generality, assume that X1, X2, belong class i.e. V/1 "/.,...; y/ 1. Then, to calculate the CG-score for x1, X2, ... Xt, we gen- erate the gram matrix H with (x1, 1), (x2, 1)..... (x1, 1), (x++1. -1), (X1+2, -1), -1),.., (Xn, and calculate the CG-scores of X1, Xg, ........ ... xi as the two-label case.
XI
A.2 STOCHASTIC METHOD TO CALCULATE CG-SCORES
Since the calculation of the CG-score requires taking the inverse of n re-dimensional matrix H where n is the number of total samples, would demand expensive memory and computational cost for large n. To lower the complexity, we sub-sample the examples with class 1 so that the ratio between class +1 and class -1 is reduced from 1 (k- 1) to 1 3 for MNIST and FMINST, 1 for CIFAR-I0 and CIFAR-100. We repeat this process 10 times by randomly sampling examples of label -1 and then average out the calculated CG-score of each example from class +1.
A.3 JUSTIFICATION OF STOCHASTIC METHOD CALCULATE CG-SCORES
To justify the stochastic method in calculating the CG-scores, we conduct experiment to check whether the CG-scores calculated by the stochastic method converges well to the true CG-scores utilizing the full dataset. We created subset of the CIFAR- 10 dataset, the Small-CIFAR-II 10 dataset, which consists of 1,000 instances for each label (a total of 10,000 instances). Then, we compared the CG-score calculated by 10,000x 10,000 Gram matrix H of the full dataset (true CG-score) with the CG-score calculated by the stochastic method, where the stochastic CG-score for the instances from class (class 1) are calculated by subsampling the samples from any other classes (class -1) with the ratio between class and 1 equal to 1 (size 2,000x2,000), 1 2 (size 3,000x3,000) 1 3 (size 4,000x4.000) and 1 (size 5,000x5,000 5,000) instead of 1 9. We repeat this process multiple times by randomly sampling examples of label -1 and then average out the calculated CG-score of each example from class +..
In Figure 5 we plot the Spearman's 's rank correlation and Pearson correlation between the true CG- score and the stochastic CG-score for each ratio (different colors) as the number of random sampling increases. We can observe that the correlations converge to certain number as the number of random sampling increases, and the amount correlation increases as the size of the matrix (the number of instances included in defining H increases. The values of correlations obtained after 20 independent runs are 0.829, 0.914, 0.953, and 0.973 for Spearman rank correlations and 0.796, 0.898, 0.943, and 0.967 for Pearson rank correlations.
Recommended number of runs for stochastic calculation. The proper number of runs in stochastic calculation of the CG-score may need to be determined by the size and the number of classes of the datasets. We recommend the number of runs large enough to include at least half of the whole dataset in calculating the CG-score for samples of each class. As an example, for the CIFAR- 100 dataset, where each class includes 500 images, when the sampling ratio between the class of interest and the rest of classes is 1:4, we calculate the score for 500 images from the class of interest by using 2,000 images from the rest of 99 classes. Then, about 20 images are selected from each of the 99 classes. To cover at least half of the images per class (250), need repeat the runs about 10 times (ignoring overlap of samples in each run). For the FMNIST/CIFAR- 10 datasets, the similar calculation shows that only 2-3 runs will be enough.
13

---

Published as a conference paper at ICLR 2023
Spearman rank correlation
6.95
Pearson correlation
0.90
2000x2000
6.85
0.89
3000x3000
4000x4000
5000x5000
2000x2000
0.00
3000x3000
4000x4000
0.75
5000x5000
2
10
12
14
16
18
20
10 12 of calculations
14
16
18
20
calculations
Figure 5: We create Small CIFAR-10 dataset by sampling 1,000 data from each class of CIFAR- 10 dataset. Figures show Spearman's 's rank correlation(left) and Pearson correlation(right) between the CG-score of Small CIFAR-10 10 and CG-score calculated by subsampling the dataset (stochastic CG-score) the number of calculations (random sampling) increases. Stochastic CG-scores calculated with 2,000 (cyan), 3,000 (orange), 4,000 (green), and 5,000 (red) instances, while the full data includes 10,000 instances (1 5,000 for each class). X-axis indicates the number of independent runs to calculate averaged score, and Y-axis indicates the correlations.
B DISCRIMINATING MISLABELED DATA FROM ATYPICAL (BUT USEFUL) DATA BY CG-SCORES
showed that irregular samples, either from input itself or mislahelling, tend to have high CG-scores. Diseriminating mislabeled data and atypical (but useful) data is a major challenge in data valuation, since both the mislabeled data and atypical data irregular in the data distribution and tend to have high CG-scores. The same challenge has been observed with previous valuation scores such as forgetting score (Toneva al. 2019) and EL.2N score (Paul et 2021).
In Section 3.3
However, we find that mislabeled data usually has higher CG-score than atypical data, and this tendency gives the possibility separate mislabeled data from the rest of the clean data. To check the tendency, we perform data window experiment. The data instances are sorted in ascending order by the CG-score, and we compare the test accuracy training instances selected from an offset% to (offset+500)k scoring group, for different offset points of (0, 5, .o...... 45, 50}. For example, when the offset is 20%, we select the data instances from 20% to 70% scoring examples. When the training instances do not include mislabeled data, we can expect that the window experiment will show higher accuracy as the offset increases up to 50%. We add 20% of random label noise to FMNIST and CIFAR- datasets when the dataset includes mislabeled instances.
neural network trained with 50% of
how the trend changes
As shown in Fig. (a) and (b), the test accuracy increases until the offset reaches 30% and then drops after the point. When the offset 30%, the 50%-width window includes 30% to 80% scoring examples. Since 20% mislabeled data are mainly located within the 80% to 100% scoring group, as the offset increases above 30%, the 50%-width window starts to include mislabeled instances and this causes the rapid drop of the accuracy. Thus, from the window experiments we can that the mislabeled data has the highest CG-score and can be separable from the rest of the clean examples by the CG-score.
Then, the next reasonable question is how to set the threshold on CG-score to detect the mislabeled data when the portion of mislabeled data is unknown. We show that the sign of the partial CG- score 2y, ( I,h.), which is sub-term of the CG-score in equation incluuding the label information ys can be used in this purpose. As explained in Sec. 3.3 the partial CG-score measures the gap between the average similarity of the data instance with other samples of the same class compared to that with the samples of the different classes. Thus, by checking the sign of the partial CG- Ccore, discriminate mislabeled samples from clean samples. In Fig. (c), show the scatter plot of clean (blue) and mislabeled data (orange), where one can find that mislabeled examples tend to have positive partial CG-score (x-axis). As shown in Table 2 we check that for FMNIST with
14

---

Published as a conference paper at ICLR 2023
90
Cleen
Noise label
accuracy
80
Test accurac
80
80
75
DG-Score
60
70
40
60
65
50
Random
60
Random
10
20
30
40
50
10
20
30
40
30
-20
-10
10
20
Offset window
window
Partial CG score
(a) Window experiment (FMNIST) (b) Window experiment (CIFAR-10)
(c) Scatter graph (CIFAR-10)
Figure 6: (a) and (b) Window experiments with 20% label noisy for FMNIST (a) and CIFAR-I (b) datasets. Test accuracy (y-axis) of model trained with 50% of training instances selected from offset% (X-axis) (0ff scoring group. (c) Scatter graph of Partial CG-score (x-axis) and CG-score (y-axis) for CIFAR-10 10 with 20% label noise.
Table 2: Number mislabeled data and clean data in each subset selected based on the partial CG- score (2y,(y' h,)))) for FMNIST and CIFAR-10 10 datasets, where 20% of samples in each dataset are corrupted with label noise.
Dataset
FMNIST
CIFAR-10
(y, positive
negative
high 20%
positive
negative
high 20%
mislabeled clean
11796
204
10776
7146
2854
5619
3462
44538
1224
8331
31669
4381
20% label noise (12,000 mislabeled instances and 48,000 clean instances), (8761179//22000)) of mislabeled data ends up having positive partial CG-score, while only 7%6==462/48800) of clean data has positive partial CG-score Thus, even when the portion of label noise is unknown, our partial CG-score can effectively detect the mislabeled data by the sign information. This tendency was less clear for CIFAR-10 dataset due to the increased dataset complexity, but still the tendency existed.
C VISUALIZATION OF EXAMPLES SORTED BY CG-SCORE
Analysis of MNIST and FMINST by CG-score In Fig. 7 we show examples of MNIST (Fig- 7ab and FMNIST (Fig. 7b) images sorted by CG-score. The top/bottom three rows show the top- /bottom-rant ranked examples, respectively. We can observe that the examples with the lowest CG-score are regular examples representing each class and they look similar to each other, while the examples with the highest scores are irregular and they look different among themselves, among which we can identify (possibly) mislabeled instances, marked with red rectangles. Similarly, in CIFAR- 10 images (Fig. 7c). we observe that low- www-scoring examples (bottom two rows) are regular ones sharing similar features representing the class while high-scoring examples (top two rows) are irregular ones.
Analysis of CIFAR-100 by CG-score Fig. X shows the examples of CIFAR-I00 dataset. Fig. 8a shows the means and standard variations of 100 classes in CIFAR-100 dataset. Among 100 classes, 'orange' and 'plain' classes have small CG-score means and variances, while 'bottle" and 'flatfish' classes have large CG-score means and variances. We display ten top-/bottom ranked examples of these four classes, with the histograms of the scores in Fig. 8b
Analysis of ImageNet by CG-score To check the effectiveness of CG-score in analyzing more complicated dataset, compute CG-score the ImageNet dataset well. The CG-score is com- puted with the sampling ratio of 1:4 by averaging the results from 10 independents runs. Fig. g shows the distribution of CG-score and shows examples of ImageNet dataset with CG-score his-
15

---

Published as a conference paper at ICLR 2023
1
7
J
6
1
High score
High scure
1
7
6
4
+
S
4
1
2
9
5
f
/
2
4
5
6
7
8
9
Low Soore
Low Spore
2
3
4
S
6
7 8
9
2
4
S
7
8
9
(a) Examples of MNIST dataset
(b) Examples of FMNIST dataset
High score
Low: score
(c) Examples of CIFAR-IU dataset (Cat, dog, frog, and truck)
Figure 7: Examples sorted by CG-score. In (a) and (b), top-3 rows / bottom-3 rows display top- ranked bottom-ranked examples, respectively. Among top-ranked examples, (possibly) mislabeled examples are marked by red rectangles. In (c), top-2 rows / bottom-2 rows display top-ranked / bottom-ranked examples, respectively.
togram. 'Jack-o-lantern' and 'Rapeseed' classes have relatively smaller mean and std of CG-score and the examples from these classes share some typical attributes (color and shape). On the other hand, 'Ladybug' has high standard deviation and we can observe clear differences between the low- scoring examples and high-scoring examples. Examples of 'Spatula', which has the biggest mean and relatively high standard deviation, do not look similar to each other but rather diverse. From the analysis, can see that our CG-score is effective in examining high high-resolution complicated dataset such as ImageNet, and the score reflects the instance- wise structural regularities, which can be used in analyzing improving learning algorithms.
D IMPLEMENTATION DETAILS AND COMPUTATIONAL COST
D. TRAINING DETAILS
In Section 4 and 5 we evaluate our score on three public datasets, FMNIST, CIFAR-10/1000 by training ResNet networks (He et al. 2016) of different depths. ResNet18 used for FMNIST and CIFAR-10 10 dataset and ResNet50 is used for CIFAR-100 dataset. Implementation of the ResNet based on the ResNet network in torchvision Paszke et al.) 2019). Since FMNIST and CIFAR images smaller than ImageNet (Deng et al. 2009) images, we replace the front parts of the ResNet (convolution layer with 7x7 kernel and 2x2 stride, max pooling layer with 3x3 kernel and 2x2 stride) with single convolution layer with 3x3 kernel and 1x1 stride for small size image. The details on hyperparameters and optimization methods used in training are summarized the Table
3
D.2 COMPUTATIONAL TIME
Table 4 provides computational time (in seconds) to obtain CG-scores with different sampling ratio 1:1, 1:2, 1:3, and 1:4 for FMNIST and 1IFAR-10/10 dataset. We also report the time to compute the baseline scores, Forgetting TTneva et al. 2019), EL2N (Paul et al. 2021). TracIn (Pruthi al. 2020), and CRAIG (Pruthi et al.. 2020). We do not calculate the CG-score of FMNIST dataset with sampling ratio 1:4 since it requires inversion for 30,000x30,000 matrix, which exceeds the limit of
16

---

Published as a conference paper at ICLR 2023
pottc
Stdd of CG-score
dothen
11.
iaann
#gance
20.0
22.5
Distribution CG-scores CIFAR-100
High
8.1
6:0
033
plain
3.6
bottle
000
038
nadiish
Density
0.0
009
0.6
023
DG-score
CG-score
CG-score
CG-score
(b) Examples and histograms of four classes in CIFAR-100
Figure 8: Sample analysis for CIFAR-100 dataset in terms of the CG-score. (a) shows the CG- score means and standard deviations of 100 classes in CIFAR-100 dataset. (b) shows ten top-ranked examples (top two rows) and bottom ranked examples (bottom two rows) for orange, plain, bottle, and flatfish classes of CIFAR-100 100 dataset. Histograms show distributions of the CG-scores for each class.
Table 3: Details for the experiments used in the training of the dataset.
FMNIST
CIFARIO
CIFAR100
Architecture
ResNet18
ResNet18
ResNet50
Batch size
128
128
128
Epochs
100
200
200
Initial Learning Rate
0.02
0.05
0.1
Weight decay
5e-4
5e-4
5e-4
Optimizer Learning Rate Scheduler
SGD with momentum 0.9
Cosine annealing schedule (Loshchilov & Hutter 2017)
Normalize by dataset's mean, variance
Data Augmentation
Random Zero Padded Cropping (4 pixels on all sides)
Random left-right flipping (probability 0.5)
the device memory. Every score including ours and baselines needs to be calculated by averaging the results of independent multiple rums. For fair comparison, compare the time to get each score for a single run. Cost to compute CG-score depends on the size of the Gram matrix H since need calculate the inverse of He to get the CG-score and the computational complexity
17

---

Published as a conference paper at ICLR 2023
dagyoug
90-
Std of CG-score
80-
spotula
jаpesee
Jock
50-
40
300
140
Mean CG-score
(a) Distribution of CG-scores ImageNet
Jack-o-lantem
Rageseed
Ladybug
Spatula
0.08
0.09
033
0.333
0035
0.10
0.30
0008
0008
0.35
0.30
0069
0.000
369
90
0.000
209
300
0.08
300
CG scone
CG CG-score
CG-score
CG-score
(b) Examples and histograms four classes Imagenet
Figure 9: Sample analysis for ImageNet in terms of the CG-score. (a) shows the CG-score means and standard deviations of 1,000 classes in ImageNet dataset. (b) shows four top-ranked examples (top row) and four bottom ranked examples (bottom row) for Jack-o-lantem,, Rapeseed, Ladybug, and Spatula classes of ImageNet dataset. Histograms show density distributions the CG-scores for each class.
Table 4: Time cost(seconds) to compute scores of the dataset.
FMNIST
CIFAR-10
CIFAR-100
CG-score 1:1
1063
608
37.9
CG-score 1:2
2610
1497
40.3
CG-score 1:3
4834
2773
49.0
CG-score 1:4
4388
61.1
Forgetting
1879
3322
6675
EL2N
370
323
662
TracIn
1856
3425
8400
CRAIG 3023
5263
10472
GPU
Nvidia A100 40GB
conduct an inversion of n x matrix is O Therefore, for a dataset of which each class includes a large number of instances (e.g., FMNIST and CIF,R-10), taking the inverse a Gram matrix with large sampling ratio may cause expensive computational cost, while computing the score for dataset which each class includes relatively small number of instances (CIFAR-100) can be done in short time. For example, calculating CG-score of CIFAR- 10 dataset (5,000 data in class) takes 1.2 hours with sampling ratio 1:4, while that for CIFAR- 100(500 data a class) takes just minute. EI EI.2N score is time-efficient overall because it is calculate at the relatively early stage of training.
18

---

Published as a conference paper at ICLR 2023
Forgetting and TracIn, on the other hand, take relatively longer time since they require at least one full train of the model. In addition, we argue that our method has another computational advantage that we do not need to search networks and hyperparameters which would work well for the target dataset.
D.3 EXPERIMENTAL DETAILS
Baseline scores for data valuation We use three state-of-the scores, C-score (Jiang et al. 2021 EL.NN (Paul et al. 202T), and Forgetting score (Toneva et al. 2019) as baselines with which our CG-score compared. We use pre-calculated C-score for CIFAR and CIFAR- 100 fromDiang al. (202I) and calculate EL2N and Forgetting score by averaging the score across five independent training using the full dataset. We obtain EL2N scores at 20th epochs the training. We use the same network architectures to calculate EL2N and Forgetting score: ResNet18 for FMNIST and CIFAR-10 dataset and ResNet50 for CIFAR-100 dataset. Detailed definitions the scores are as follows:
Consistency score (C-score): C-score of each instance is calculated by estimating the pre- diction accuracy of the instance attained by the model trained with the full dataset except the instance.
C-score (x,, y/) E,, ((x,,)))))) (F; 5 (Xx y:) v.l]
where f(x; S) is trained network using subset S, and i denotes empirical averaging with r i.i.d. samples of such subsets.
Error L2-Norm (EL2N); The EL2N score of a training sample (x; vi) is defined to be [[]]
yill2] where f(W((), x) is the output of the neural network for the sample (x, y/ at the 1-th step.
Forgetting score: Forgetting score is defined as the number of times during training (until time step 7) the decision of that sample switches from correct one to an incorrect one: Forgetting(Xx) (x,, Vs) is defined as
T
Σ 1 (arg max f( - x,) = 31 - 1 (arg max ((W() =v.). (10)
Data pruning experiment We report the mean of the results after five independent runs. The shaded regions indicate the standard deviation. We acquire each result by training network using a dataset pruned by specified portions, where the training instances are ordered by each score. We compute the number of iterations at which all data can be used in one epoch, and use the same num- ber of iterations in all pruning experiments for a fair comparison. When we prune the dataset, we remove the instances from each class by the same amount, between classes. As will be shown Section the distribution of scores is different among classes, so an imbalance problem between classes may occur if the data pruning is performed without con- sidering the portion of classes within the dataset.
preserve the original proportion
E ROBUSTNESS OF CG-SCORE OVER MODEL VARIANTS
Our CG-score is derived based on the theoretical analysis of the generalization error bounds on overparameterized two-layer ReLU activated neural network. To demonstrate that our CG-score is effective in more complicated networks, in the main text (Section 4.1. we used ResNets to eval- uate our score for data pruning experiments. To further demonstrate the robustness of our score against model changes. in this section, we report the results of data pruning experiments on CIFAR- 10 dataset using DenseNetBC-1000 Huang et al. (0017), a more complicated convolutional network, and Vision Transformer (ViT) (Dosovitskiy et al. (021) pretrained by ImageNet dataset. The imple- mentation details of DenseNet follows that of Huang et al. (2017). We use the same hyperparameter and optimization method summarized in Table 3able for training DenseNet. To fine-tume VíT, follow the implementation details outlined in Dosovitskiy et al. (202T). Specifically, we download a ViT model pretrained the ImageNet dataset using the timm module in PyTorch, and then fine-tune
19

---

Published as a conference paper at ICLR 2023
DenseNet-100 (Pruning low value)
DenseNet-100 (Pruning high value)
95.0
94
94.5
Test accurccy
Test accuracy(
92
93.5
CG-score
90
CG-scare
93.0
Forgetting
C-score
88
Forgetting
C-score
92.5
Random
Random
92.0
0.5
0.6
0.7
0.8
0.9
0.5
0.6
0.7
D.8
0.9
Portion of train set
Portion of train
(a) Pruning low-scoring examples first.
(b) Pruning high-scoring examples first.
Figure 10: Pruning experiments with CIFAR-I0 dataset trained on DenseNet-100 Even if the model changes from ResNet to DenseNet, observe similar trends as in Figure 2
VIT (Pruning low value)
VIT (Pruning high value)
Test accuracy
98.0
Test accuracyy
96
97.5
97.0
CG-score Feature CG-score
94
CG score
Featune CG-score
96.5
92
96.0
Forgetting
Fargetting
C-score
C-score
95.5
Full dataset
Full dataset
95.0
88
0.05
0.10
0.15
0.20
0.25
0.05
0.10
0.1.
0.20
0.25
Portion of train set
Portion of train
(a) Pruning low-scoring examples first.
(h) Pruning high-scoring examples first.
Figure 11: Pruning experiments with CIFAR-10 dataset trained on VIT pretrained by ImageNet dataset. Despite changing the model from ResNet to ViT and fine-tuning it, we still observe similar trends as shown in Figure 2
the model the CIFAR-10 dataset for 10 epochs using the ADAM optimizer. We set the initial learning rate to le-5 and do not use learning rate scheduler or weight decay.
In Figure 10 the left figure shows the test accuracy of the model trained with different subset sizes, when low-scoring (regular) examples are removed first, and the right figure shows the similar result but when high-scoring (irregular) examples two independent runs, and the shaded regions indicate the standard deviation. The red-curve (ran- dom) is the result when randomly ordered examples are used. We can observe similar trend in Fig. 2 the experimental results using ResNets, in spite of the model change. Our CG-score achieves competitive performances as the other baselines. The reason that we observe a rapid performance degradation at smaller training data portion in the left figure (removing low value data first) is due to the characteristics of leave-one-out method we used in the calculation of the CG-score. Remov- ing typical sample from dataset does not change the generalization error bounds much, since similar samples already exist the dataset. Thus, typical samples tend to have low CG-scores when the score is measured by the leave-one-out method. However, when we remove 50% of instances, samples sharing the typicality can be excluded simultaneously from the dataset, which might cause severe degradation of the generalization capability of the neural network. Thus, for smaller train- ing data portion, it can be better to make sure at least a small portion of typical samples is indeed included in the training. Similar observations have been made in Swayamdipta al. (2020).
removed fist. We report the mean of the result after
20

---

Published as a conference paper at ICLR 2023
As shown in Sorscher et al. (2022) data scoring can also be effective in reducing the amount of data for fine-tuning pre-trained models. Therefore, we examine whether our CG-score can be ef- fective for fine-tuning the transformer-bast basseder--beddd--e models, in particular, VIT. In Figure II the left figure shows the test accuracy of ViT fine-tuned with different subset sizes of CIFAR-10 10 when low-scoring (regular) examples are removed first, while the right figure shows the results when high-scoring (irregular) examples are removed first. We report the mean of the results after five independent runs and indicate the standard deviation with shaded regions. The red curve (random) represents the results when examples are randomly removed. We observe that when low-scoring examples are removed first, similar to Figure 2 the networks maintain test accuracy even when up to 90% of the dataset is removed. Our CG-score achieves competitive performance compared to other baselines and significantly outperforms the random baseline.
F ADDITIONAL EXPERIMENTS WITH TWo MORE BASELINES
F.1 OTHER DIRECTIONS OF DATA VALUATION
There two additional branches of related works for data valuation, in addition to the methodolo- gies described in the Section 2 The first branch uses the influence function. The influence function approximates the degree of change of parameters when specific data enters or leaves the training dataset, so determines which data is valuable by calculating the effect of the data on learning. The second branch uses coreset selection. Coresets are weighted subsets of the data selected to resemble the model training using the full dataset. Coresets may need to be updated as training progresses.
Baseline algorithms for data valuation We use representative scores in each branch, TracIn (Pruthi et al.) 2020) for influence function and CRAIG (Mirzasolciman et al.] (020)) for coreset selection, as additional baselines. Detailed definitions of the scores are described below:
TracIn: TracIn CheckPoint (TracInCP) value between two data points defined as weighted sum of dot products of the loss gradients calculated at the two data points. The gradients are obtained from the & checkpoints {t1...., tx} of the model in the middle of training and the weight 1), is the learning rate at each checkpoint f;
TracInCP(2,2
nre Vi(w,, 2 TVl(wn))))
(11)
where l(w,, 2) loss function at 1,-th step with model parameter Wt,,
CRAIG: CoResets for Accelerating Incremental Gradient descent (CRAIG) is an algorithm that solves the optimization problem, which finds subset that preserves the gradient of the total loss:
S E argmax
Σ min max [f((w) (f s.t. |S| S
(12)
JES NEW
iEV
where (ww) I(w, (a,; yk)) is loss for the data (x;, 9: with model parameter w, the full dataset and S is the coresets with size and pt be the softmax output for data (xi, y:). In CRAIG, the gradient f((w) is approximated by ps yt when cross entropy loss used with soft-max at the last layer.
F.2 DATA PRUNING EXPERIMENTS
In this section, we conduct data pruning experiments, similar to Section 4.1 We conduct the experi- ments using the above two additional baselines, TracIn and CRAIG, separately from the experiments of the main text, since the two algorithms require additional assumptionssresourres that have not been used for the baselines considered in the main text: TracIn requires validation set to calculate the data values; CRAIG does not select a fixed subset of data to be used throughout the training, but keeps updating the subset of the data (coresets) to be used for training every 10 epochs.
21

---

Published as a conference paper at ICLR 2023
FMNIST
CIFAR-10
CIFAR-100
Pruning low value data
25.0
94.0
94.0
Clossor
Clocor
hooin
Iradn
Fack
CR4I
CHAG
CRAIS
Random
93.5
Random
Random
Full detaned
Full detenet
0.
0.6
0.7
0.6
0.9
65
0.6
0.7
09
066
677
0.8
(a) Pruning low-scoring examples first. Better score maintains the test accuracy longer.
Pruning high value data
95.0
94.5
76
24.0
92
92.5
93.0
92.5
CG-score
CGacore
Trech
88
Trechn
Tacl
Rancom
Random
corasct
85
Portion of tram sot
Fortion of tra set
Portion of train set
(b) Pruning high-scoring examples first. Better score makes the rapid performance drop.
Figure 12: Pruning experiments with three datasets FMNIST (left), CIFAR-10 (middle) and CIFAR- 100 (right). Our CG-score can achieve better performances than the Tracin score and competitive performances compared to the CRAIG algorithm. Different from our scoring method, TracIn re- quires a validation set to calculate the data values and CRAIG does not select a fixed subset of data to used throughout the training, but keeps updating the subset the data (coresets) to be used for training every 10 epochs. CRAIG has been evaluated only for pruning low-valued samples due to the nature coreset selection where coresets are selected with per element weights.
Experimental details As described in the Pruthi et al. (2020), we calculate the TracIn score by using the gradients of the parameters of the network's 's last layer. The check points are set at every 20 epochs, starting from the end of the first 20th epoch. We use checkpoints for FMNIST and 10 checkpoints for CIFAR- 10 and CIFAR-100. We create a validation set composed of 1,000 samples by taking part of the test dataset, and calculate TracIn score with this validation set. As TracIn score is defined between two data points (2, z') as in equation [1 we set the score of each training sample z by averaging TracIn scores TracInCP(2,, z²) over all samples z' the validation set.
In CRAIG, the subset selection is performed every 10 epochs. We only test CRAIG in pruning low- valued data but not in the reverse order (pruning high-valued data), since CRAIG extracts coresets to be used with per element weights for preserving the gradient of total loss but does not give what are the valued (equal weight) samples.
TracIn score and CRAIG calculated at the networks same those used in the experiment in Section 4.T ResNet18 for FMNIST and CIFAR- 10, and ResNet50 for CIFAR-100 dataset. The other experimental details are the same Table in Appendix D.3
Experimental results Similar to data pruning experiment in Section 4.1 in Figure 12 the first row shows the test accuracy of the model trained with different subset sizes, when low-scoring (regular) examples are removed first, and the second row shows the similar result but when high-scoring (irregular) examples are removed first. We report the mean of the results after five independent runs, and the shaded regions indicate the standard deviation. The red-curve (random) is the result when randomly ordered examples are used. When pruning low-scoring data first, it is preferable to maintain the accuracy up to large removing portion (a small training set); when pruning high- scoring data first, the rapid drop of performance is preferable since it means that the score can detect high-value samples, necessary for generalization of the model. Our CG-score better performances than the Tracin score and competitive performances compared to the CRAIG algorithm. Since CRAIG updates the coresets over the training, choose different semantics
achieve
22

---

Published as a conference paper at ICLR 2023
20% FMNNST
20% CIFAR-100
Fraction Tound(
1000
80
80
score
60
Partall CG-score
60
Trachn
fancom
Oraele
10
20
30
40
50
10
20
30
40
50
Fraction of data checked!%)
Fraction of data checked)%))
Figure 13: Fraction of label noise (y-axis) included in the examined portion (x-axis) for 20% label noise for oracle. Partial CG-score (ours), CG-score (ours), TracIn and random baseline.
FMNIST
CIFAR-10
CIFAR-100
ckan label
0.07
daan abol
dean labal
0.06
0.05
0.06
0.04
0.03
0.04
0.00
40
80
100
120
0.00
20
80
100
CG score
0.12
0.06
nose
0.030
0.05
0.025
0.04
0.06
0.020
0.02
0.010
0.02
0.085
0.01
0.00
CD score
Figure 14: Density of CG-scores at clean dataset and label noisy dataset.
of the data suitable for each phase of the training, which results in better performance. This result may imply the effectiveness of the scheduled batch selection, e.g., curriculum learning, in training neural networks. We inspect that the performance of TracIn may heavily depend on the size of the validation set and also the possible domain discrepancy between training and test datasets. In our test, there is no domain discrepancy, but if there exists a domain shift between the test dataset and the training dataset, TracIn may perform better than other methods with the help of validation set.
F.3 DETECTING LABEL NOISE
We also compared the performance of our CG-score in detecting mislabeled data with that of TracIn. As suggested in Pruthi et al. (2020). we use 'self-influence' of each training example, i.e., the in- loss during the training process, TracInCP(2, 2), to identify
fluence of training point mislabeled data. In Pruthi et al. (202)), it was shown that mislabeled examples tend to have higher TracIn values, and thus TracIn values can be effectively used in identifying mislabeled examples. In Fig. 13 we show the comparison of our method with TracIn in identifying mislabeled examples in FMNIST and CIFAR- 100 datasets, respectively, each of which includes 20% label noise. TracIn achieves better performance in CIFAR- but ours outperformed TracIn in FMNIST. Since TracIn measures the 'self-influence' of each training example over the training, starting from 20th epoch, for relatively simpler dataset such FMNIST, some mislabeled instances could have already been memorized at the network. which makes them not detectable by the TracIn values. On the other hand, our method better detects mislabeled data for casier datasets as discussed in Sec. 4.2 Thus, we can conclude that depending on data complexity, the outperforming method can be changing.
G SCORE DISTRIBUTION FOR PUBLIC DATASETS
23

---

Published as a conference paper at ICLR 2023
50% FMNIST
50% SIFAR-100
Fraction Tound(
1000
80
80
60
60
Partaal CG-szore
Random
20
forgetting score
20
212h
Dracce
20
40
60
80
100
20
40
60
80
100
Fraction of data checked!%)
Fraction of data checked)%)
80% FMNISS
80% CIFAR-100
Fraction fourd(())
1000
CG-ccoe
Purbal CD score
80
Random
80
Forgetting scone
60
60
20
20
40
60
80
100
20
40
60
80
100
Fraction of data checked/%)
Fraction of data checked)%)
Figure 15: Fraction of label noise (y-axis) included in the examined portion (x-axis) for (t%p(t and (bottto))) label noise for FMINST (left) and CIFAR-100 (right) datasets.
Score distributions In Fig. 14 we compare the CG-score distributions of three public datasets, FMNIST, CIFAR-10 and CIFAR- 100 before and after we artificially corrupt 20% of instances with random label noise. The top row shows the distributions before the corruption, and the bottom row shows the distributions after the corruption, where the orange color displays the distribution of the CG-score for 20% instances with label noise and the blue displays that for 80% instances with clean label. The gap between scores of clean data and noisy data, which enables us to detect the noise by the CG-score, is larger for relatively simpler dataset, FMINST, than those for CIFAR-10/100.
Detecting mislabeled instances at high noise rate We conduct additional experiments check the detectability of mislabeled instances by our CG-score, when the noise ratio increases to 50% and even 80% for FMNIST and CIFAR- 10 dataset. In the main text, we considered mild noise ratio of 20% and reported the result in Fig. 3 The results for higher noise cases are shown in Fig. 15 In the CIFAR-10 10 dataset, when the noise ratio is 80%, each class includes 1,000 correctly labeled images and 4,000 mislabeled images, composed of 445 samples coming from each of the other nine classes. Even for such an extremely noisy case, our CG-score can effectively detect the mislabeled data, since our score can discover samples that have relatively lower correlation to the majority of the samples of the same class as analyzed in Sec. 3.3
H FEATURE-SPACE CG-SCORE
Our original CG-score can be calculated by data without any trained network. In this section we check the validity of a new CG-score, which is defined in terms of feature of data, and compare its characteristic with that of the original data-centric CG-score. We train ResNet18 using FMNIST and CIFAR-10 dataset and ResNet50 using CIFAR- 100 dataset to obtain each data's 's feature at 10th epoch, where the feature is defined at the output of the penultimate layer (512 and 2048 dimensions for ResNet18 8 and ResNet50, respectively). Then we calculate the feature-space CG scores, which are calculated by the feature instead of the data itself. Unlike CG-score, calculating feature-space CG-score requires training of model for few epochs, which implies that the score becomes dependent to the model and we need additional computational efforts. However, feature CG-score achieves superior performances at data valuation the results of data pruning experiment (Fig. 16) and noise detection experiment (Fig. 17 show even though the features were extracted at early stage of the training (10th epoch).
Furthermore, we compare how the Spearman rank correlation between the feature-space CG-scores and other scores, including the original CG-score and the previous maining-based scores such as
24

---

Published as a conference paper at ICLR 2023
FMNIST
CIFAR-10
CIFAR-100
Pruning low value data
73
Cleezare
CG-score
94.8
Twetur Cl
Feeture DGvecore
CESLor
94.0
EL2h
74
E.28
94.6
EUN
hargdting
roggtting
Forgetting
Csscore
C-score
94.4
Raviiom
93.5
Random
Random
Full detinet
Full detanet
Full decaset
0.
0.6
0.7
0.6
0.9
655
0.6
0.7
09
0.6
0.7
0.8
Portion
(a) Pruning low-scoring examples first. Better score maintains the test accuracy longer.
Pruning high value data
76
92
score
CG soore
score
Feature re CG score
Feeture CG score
Feature CG-score
EL2N
0.2N
22
E12N
Fargatting
Forgetting
Pergetting
88
Cascoe
Calora
91
Random
Random
danacct
85
Portion tram sot
Fortion of fra set
Portion of train set
(b) Pruning high-scoring examples first. Better score makes the rapid performance drop.
Figure 16: Pruning experiments with three datasets FMNIST (left), CIFAR-10 (middle) and CIFAR- 100 (right). With additional computation (training of model for 10 epochs), our feature-space CG- score can achieve better performances than the original CG-score. The performances are competitive to other baseline scores
Fraction of rota data foundy9)
#MNST
CBAR100
100
100
60
60
Pertal CGesare
Fearii CG score
ELLM
20
forgetting scoe
20
10
30
40
20
30
50
Praction data of cheedoedt5)
Tracikan of Call (1ec
Figure 17: Fraction of label noise (y-axis) included in the examined portion (a-axis) for 20% label noise. Feature-space CG-score achieves superior noise detectability for FMNIST than for CIFAR- 100.
C-score, Forgetting score, and EL2N, change over the epochs at which the feature space CG-scores are calculated. Figure 18 reports the result. In Figure [8] we can first observe that the feature space CG-score and the original CG-score has the highest correlation the very beginning of the training (epoch 1), but as the training progresses, the correlation decreases. This trend can be explained by the fact that the feature space CG-score computes the value of data in the learned embedding space, while our score computes the value of the original data without embedding it into latent space. As training of model progresses, the embedded data may incur bias the data valuation, depending on particular model or training algorithm, and thus the correlation between the feature space CG-score and the original data-centric CG-score may decrease. On the other hand, correlation between feature space CG-score and other wrining-based scores (EL2N, Forgetting, and C-score) increases during the initial stage, and then decreases gradually. More specifically, for both EL2N and Forgetting score, which are computed at the same network as that of the feature space CG-score, the correlation increases as the epoch increases and then slightly drops and becomes saturated at a certain value. The C-score, which was calculated in different CNN network, shows slightly different tendency compared to EL2N or forgetting score, and attains its peak at an earlier epoch, epoch 5. This result implies that the feature-space CG score includes meaningful information for
25

---

Published as a conference paper at ICLR 2023
Spearman Correlation
lorgetting ginzl score
0.7
044
02-
50
100 200
Epech
Figure 18: Spearman rank correlation (y-axis) between feature space CG-score calculated at each epoch (x-axis) and baseline scores including C-score, EL2N, Forgetting score and the original data- centric CG-sc The feature space CG-scores are calculated right after epoch 1(after one epoch of training), 3, 9, 11, 20, 50, and 200 (end of the training).
data valuation, correlated with other training-based scores for overall epochs. However, the feature space CG-score may incur some bias in data valuation as the training progresses. Understanding the effectiveness of the feature-space CG score in diverse applications can be interesting future research direction.
I DETAILS OF KERNEL VELOCITY
We calculate the kernel velocity of 10 groups of instances, where each group is composed of 125 samples. The following is how we construct each group: Sort CIFAR-I0 examples in ascending order by the CG-score, divide the examples into 10 groups, and select 125 consecutive samples from the beginning of each group.
We calculate the NTK kernel velocity described in Paul et al. (2021): Let C be the number of classes. Let (x;) be the e-th logit value for input x; at the l-epoch. When W(I) is the parameters of the model, the c-th logit gradient at input is v/(")) (x:) = Vw (a:)) NR.. Then, the data-
dependent NTK submatrix of group of m samples == (x Xam) is defined as K,(S)
Mr (,, where (.)) m2mCXN is constructed by placing (x.," (xe)))ee in rows of 1r (S). The kernel velocity is defined
(8) 1 (K,(S), K++1(S)) (S)] (S)]I
(13)
Lastly, we provide some explanations of what the kernel velocity measures if define for finite-width ReLU activated 2-layer neural network. Remind that our analysis uses the Gram matrix H defined in equation [ which derived for overparameterized ReLU activated 2-layer neural network. We can generalize the definition of the Gram matrix as- suming finite-width network, similar to Kr(S), as follows. The output of the network is fw.a(x) = 1 Em a (w, x), and the gradient with respect to W (wi...., w.)
Vm Rdxm is Vw)(xi) = f(x,,, V (w) Vw., (xx)]
XI 7m
[al
>
0} az agl(w]]x x4 2 O},...,o (y....,mmI(ve I/ 2 OJ}. Denoting the network parameters at the 1-th step as W(t), we can define the Gram matrix H, as (H₂); = x, x; E 1[w,Tx; > 0, , > 0}. which is proportion to the number of neurons in the hid- den layer activated both for x; and x, at the epoch. We can define the kernel velocity similar to equation| 13 by calculating H, for subset of data, and replacing (S(S) by (S). For this case, the high kernel velocity implies that H, differs much from H i... the portion of neurons acti- vated for pairs of instances changes rapidly during training.
26

---

Published as a conference paper at ICLR 2023
Table 5: Spearman rank correlations between the CG-score and the partial CG-scores
Dataset
CIFAR-10
CIFAR-10 R-00
Subsampling Ratio
1:2
1:3
1:4
1:1
1:2
1:3
1:4
ty h:)²
-0.759
-0,461
-0.136
0.132
-0.671
-0.296
0.035
0.264
2/s (y hs)
0.912
0.948
0.962
0.970
0.902
0.939
0.955
0.964
yr
-0.015
0.066
0.121
0.163
-0.069
0.018
0.087
0.136
J CORRELATIONS BETWEEN CG-SCORE AND PARTIAL CG-SCORES
From the CG-score, which is expressed as (y ) + 2y: h.) + yfd, at the equation 6 we can define three partial CG-scores, di (y_,h,)² 2y and vfd, respectively. In this section, we analyze which term dominates the order of CG-scores for two public datasets, CIFAR- 10/100, by analyzing the correlation between the CG-score and the three partial CG-scores. We also examine whether the correlations vary when we change the size of the Gram matrix H whose dimension changes according to the level of sub-sampling, explained in Sec. A.2 We get H with different subsampling ratios, 1:1, 1:2, 1:3, and 1:4, and then calculate the CG-score and partial CG- scores, defined by the three partial terms. Table B shows the Spearman rank correlations between the CG-scores and the partial CG-scores. We can see that (y h:), which was utilized at noise detection experiments, is the partial score having the largest correlation with the CG-score across all subsampling ratios. On the other hand, correlations to other partial-scores are relatively low, and the correlations change much the subsampling ratio changes.
K
SCHUR COMPLEMENT
Calculating CG-score (equation 2 of n data instances requires the inversion of x n matrix, which may cause expensive computational cost for a large n. Therefore, we provided computationally efficient way to obtain the CG-score by using Schur complement equation 4 Here we provide some details to derive the inverse of sub-bloch matrix using Schur complement. By Schur complement, we have
A C
B -1 D
(A-BD- DDD'C(AA BD BD-
-(A -BD BD -D- (14)
-
Remind that H and (H are denoted by
( h h
R
(
(15)
g
where H R-
( 2-1
CR
(n-11)x((e 1).
gi h, E R=-1 and C₁ d, E R, i.e.
(H*)=
H
h
H 00
gi
(16)
d;
g
62
By substituting A, B, C, and D in equation obtain that
with (H ( )-1 h, h, and d, respectively, we
H no
n-1 ((H
)=1 h,h, hd/
(17)
Thus, (H (H²) 2 h.h /di
27


Reviews:
[{"review_id": "llfr17xoMr", "reviewer": "Reviewer_3m6j", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper proposes the complexity gap (CG) score, which quantifies the change in data complexity when each training instance is removed from the training set.  The primary differentiator between CG score and other data valuation measures (e.g., Shapley value, C-score, etc.) is that CG score can be calculated without any (partial) model training.  ", "summary_of_the_review": "The concept of estimating data's value without any training is obviously attractive. However, there are no free lunches. \"Low-cost\" strategies usually require tradeoffs and encounter limitations where the method breaks down.  The authors never really address this point by, for example, affirmatively showing that such a \"breakdown\" does not occur on hard tasks. They also do not include a substantive, stand-alone discussion or acknowledgment of the method's observed \"breaking points.\"  That is a grievous omission.\n\nIf the authors have evaluated their method on harder tasks and did not report the results, those results are needed.  Without them, the paper is definitely incomplete.  \n\nThe paper has promise. Perhaps with a strong author response, I could be persuaded to acceptance. However, the paper changes, in particular the additional necessary evaluation, needs significant revision.", "strength_and_weaknesses": "Reading the paper's abstract, I was quite excited by the stated claims.  The ideas and the paper have promise.  However, the paper has problems; it is not yet ready for publication and needs to empirically evaluate and candidly discuss where this \"training-free\" data valuation runs into limitations.\n\n#### **Strengths**\n\n- A competent method to evaluate the quality of data without model training is clearly highly valuable.  This makes CG score's motivation clear and compelling.\n\n- The generalization of complexity score from a dataset valuation method to an instance valuation method is a natural strategy.  It makes the paper's theoretical foundation easier to understand.\n\n- I appreciated the discussion of CG', and I am glad the authors included it.\n\n#### **Weaknesses**\n- Evaluating only Fashion MNIST and CIFAR10(0) is very disappointing.  These are not particularly challenging datasets.  Related work (e.g., Jiang et al. 2020) evaluate on ImageNet.  I could not recommend acceptance without more challenging datasets.\n\n- I am surprised about Table 4's poor rank correlation between \"feature space CG\" and vanilla CG.  It is concerning how well your method will work on more challenging tasks.  Moreover, I imagine that pretrained features will generally be more semantically meaningful than the raw pixel values.  My intuition could be wrong here, but I imagine I would not be the only one to hold such a prior.  The authors really need to address this point at least in Section G but ideally in the main paper.\n\n- In Section 3.1, the authors describe CG score as a \"*data-centric measure*.\"  However, all evaluation in this paper is on vision datasets.  Data-centric/data-agnostic measures should be evaluated on multiple data modalities.  At best, this evaluation could only show that CG score is an effective vision data metric.\n\n- Figure 2 was confusing at first review.  I believe a primary reason for that is that in one case \"larger is better\" and in the other \"smaller is better.\"  Perhaps dividing it into two subfigures where that difference is made more obvious (e.g., in the caption) would improve clarity.\n\n- The paper as a whole needs more baselines.  There are many alternate data valuation approaches (e.g., Influence Functions, TracIn, Shapley Value methods) not evaluated here that should be for at least some experiments \n  - Figure 3b should at least include C-score.  I understand Jiang et al. do not provide precalculated C-score values for FashionMNIST but they do for standard MNIST.  Hence, Figure 3b's evaluation could use regular MNIST. Jiang et al. also provide C-score for CIFAR100.\n\n- This paper needs a self-contained section explicitly specifying the computational and space complexity. It is fine to include it in the supplement, but it needs to be there.  If I missed it, please let me know, but I also checked the supplement.  Section A.2 came the closest but largely glossed over the point.\n  - I assume you have data on the execution time of your method.  It should be in the supplement for reference.\n\n- The \"*Related Works*\" does not adequately discuss the relation between data valuation and training-set influence. This relationship is primarily contextualized through Data Shapley which is only one method in this broader field. I also think the evaluation would be stronger with one or more training-set influence methods (e.g., TracIn [Pruthi et al. 2020]) included.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "VxfvqtC3dt", "reviewer": "Reviewer_QwGQ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The authors propose a new data instance valuation metric (CG score) - for scoring the how impactful a particular training instance would be on training a neural net.  This can be viewed in terms of how difficult of an example it is to learn and how much it effects generalization, etc.  This metric does not require actually training any neural net (for any number of steps), unlike much previous work on the topic.  The approach is based on a generalization error bound for 1-hidden-layer neural networks (under a number of simplifying assumptions) - in particular, measuring the change in this bound if a particular data instance is excluded from the training set.  They develop a succinct and computational efficient method to compute this change for each data instance.\n\nThey propose using such a metric for data pruning before training - to reduce the size of the data set used / needed for training a network, and for identifying mislabeled data points - and validate this with analyses and experiments.  They also demonstrate it could identify those data instances that are harder to learn - which suggests it could also be useful for something like curriculum learning.\n", "summary_of_the_review": "Overall I found it to be an interesting and potentially useful paper on the one hand that could inspire further research, but on the other hand also raising several questions and missing fields of prior work on the target applications (i.e., dataset subset selection / pruning, and handling label error).  In particular I feel it is not really accurate to claim past methods have not been developed to quantify data instance complexity without also training the predictive model, and that the missing related work and describing where this work fits in comparison could have a negative effect, as related work may end up being rehashed if readers are unaware of it.  Further it is not enough to determine if the proposed approach should be used in practice (i.e., the practical benefit) vs. the other methods not mentioned or compared to.  I hope these concerns can be addressed in revisions and in appendices as needed as well.\n", "strength_and_weaknesses": "\nStrengths:\n1) The approach is interesting (and thought-provoking) and soundly developed.  It is not purely a trivial application of the prior developed error bound as a lot of thought went into how to apply it and efficiently compute it, and a lot of analyses to understand what is doing and measuring, and how it relates to other metrics.\n\n2) Compared to recent past work analyzing data importance from neural net training it has clear advantage in not requiring training any neural network.  \n\n3) Thorough and varied experiments are provided to illustrate the properties of the metric.\n\n4) The paper is well written and organized.\n\n\nWeaknesses:\n\n1) I feel perhaps the biggest weakness is lack of mention and comparison to prior work targeting the particular problems this metric is proposed to be applied to - selecting a subset of data for more efficient training, and finding mislabeled training data.\n\nIn particular - a major motivation of the approach was to \"dataset pruning\" - which is essentially using the score per data instance to select a subset of data points for training, e.g., in order to enable fast / less expensive training on just a subset of the data.  The paper is a bit misleading in stating it is the only approach to doing this that doesn't require training a neural network first - as in general this is an area of research with a long history, and there are many methods that have been developed to select a subset of the data for training that don't all require fitting a particular predictive model to it first.  It would be best to mention these methods, why this proposed approach may have some advantage, if any, and also include some of these in the experiment results.  In particular - would I use this proposed metric, or one existing approach to identifying a subset of the data to use for training?  What are the advantages and disadvantages of each?  Additionally there are many other alternatives to accelerating machine learning training such as data sketches - not just selecting a subset of data, but summarizing the data in some way first (perhaps even with random features) to speedup training using a smaller transformed set of data.\n\nSome examples of papers in this area:\n- \"Coresets for Data-efficient Training of Machine Learning Models\" Mirzasoleiman et al.\n- \"Subset Selection in Machine Learning: Theory, Applications, and Hands On\" (tutorial) Iyer et al.\n- \"Training Data Subset Selection for Regression With Controlled Generalization Error\" Sivasubramanian et al.\n- \"Introduction to Core-sets: an Updated Survey\" Feldman\n- \"GLISTER: Generalization based Data Subset Selection for Efficient and Robust Learning\" Killamsetty et al.\n- \"Finding High-Value Training Data Subset through Differentiable Convex Programming\" Das et al.\n- \"Oblivious Sketching for Logistic Regression\" Munteanu et al.\n\nThe same also goes for handling label error or detecting which data instances are mislabeled - again there is a large body of related work in this area not mentioned or compared to.  E.g.:\n- \"An instance level analysis of data complexity\" Smith et al.\n- \"Identifying mislabeled training data.\" Brodley et al.\n\nI found myself wondering throughout, how this work sits compared to these other approaches.  Overall it may be this is more of an analyses of a particular metric derived from a bound - so may not be claiming to be better than other approaches for each problem, but in order to have a complete and thoroughly useful analysis, it would be helpful to know how it compares.\n\n2) The original bound and the corresponding proposed metric is based on a single hidden layer MLP relu neural net - with a lot of further restricting assumptions such as on the data and weights, and also with only the hidden layer parameters being trained in the process.  The analyses of the proposed metric also make various other assumptions, of varying strength.  It would be helpful to see more experiments and analyses to understand how the proposed approach performance changes as these assumptions are violated - especially since the datasets and variations used with them were limited (just 3 datasets with no exploration of varying model types, for example).  \n\nIt would also be helpful for some discussion around what it would mean for the metric with changing neural net architecture or assumptions - how would it diverge, what would a good metric change in these cases, etc.\n\nI.e., what about different kinds of nets, e.g., more complicated (like transformer / self-attention), or with different form (e.g., different types of convolution or RNN) or activation, or with more layers?  The intrinsic biases the different network configurations and architectures correspond encode would seem to suggest different metrics might be better suited to different architectures - so what kind of universality does the proposed metric have?\n\n3) The two objectives / proposed uses for the proposed metric seem at odds and hard to reconcile. The proposed metric simultaneously is higher if a training example is necessary for good generalization (e.g., close to the decision boundary), but also higher if the training example is mislabeled.  It's being used for both things but both would require the user to take opposite actions - if the data instance has a high score and if we assume it is an important training instance we want to keep it in the training data over other instances.  On the other hand if the data instance has a high score, and we assume it is a mislabeled data instance, we would want to remove it from the training data.  How then could one decide based on this metric whether or not exclude a data instance?  I.e., how can you differentiate such cases?\n\n\n4) The idea is pretty straightforward - in the sense of taking an error bound and just measuring the difference on it by removing a data instance - this kind of leave-out-out analyses approach has been widely used and is common in machine learning (e.g., for feature importance as well), in many different context.  This may be seen as somewhat limiting the novelty, but I feel the additional development of a computational efficient algorithm and analyses of the approach overcomes this limitation.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "DWNk48c017", "reviewer": "Reviewer_6ZH6", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "- The authors tried to tackle a fundamental problem, data valuation.\n- Most previous works need model training for quantifying the values of the samples (which is computationally inefficient); however, the proposed method does not need model training.\n- The authors provided various experimental results that show the superiority and usefulness of the proposed data valuation in multiple datasets (including CIFAR-10)", "summary_of_the_review": "1. Generalization\n- In this paper, the proposed method is highly dependent on two-layer overparameterized MLP. (H in Equation (2))\n- In that case, can we say that this score is generalized to more general neural networks? Or, can we say this score is generalized to simpler models such as linear models?\n- Can we also generalize this method for a regression problem?\n\n2. Connection between data value and model\n- The value of the data can be different across different models.\n- For instance, the value of the sample with a linear model can be different with a non-linear model.\n- In that case, how can the proposed method quantify the value of the data depending on the models?\n- The author said that this model is independent of the model but I am not sure in general whether data value can be independent of the model.\n\n3. Experiments\n- The experimental results are interesting. \n- Especially, the authors show consistent improvements for noisy label finding.\n- It would be interesting if the authors can provide the results with a higher noisy ratio (like even higher than 50%) to check the robustness of the model.\n\n4. Figure 2\n- For pruning lower value samples, the proposed method shows somewhat consistently worse performance than alternatives.\n- Is there any intuition that the proposed method does not do well for discovering lower value samples? Especially with a smaller training data portion?", "strength_and_weaknesses": "Strength:\n- The proposed method is computationally much more efficient than alternatives.\n- Still, the proposed method shows competitive empirical results in comparison to alternatives.\n- The proposed method is well supported with the theoretical analyses.\n\nWeakness:\n- It is unclear whether the data value can be \"independent\" of the model.\n- In some experimental results, the proposed method shows somewhat consistently worse performance.\n- It would be good if the authors can provide empirical advantages of computational complexity.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "-0XeovpOHn9", "reviewer": "Reviewer_egMu", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This work proposes a method for scoring the utility of individual samples in a dataset, a problem that's relevant for dataset pruning and identifying incorrect/noisy labels. Whereas previous work has developed solutions that involve training the model with the full dataset one or more times, this work proposes a model-free approach. The approach focuses on the data complexity score defined by Arora et al (2019) and calculates the difference when the sample is included vs excluded. The computational complexity for this approach is potentially high, requiring the inversion of a $n \\times n$ matrix (where $n$ is the training set size), but this will in some cases compare favorably to the cost of model training.\n\nThe authors provide experiments with three image datasets showing that the method (complexity gap score) is useful for dataset pruning, and that it can highlight cases where the dataset has noisy labels.", "summary_of_the_review": "I think this work is a valuable addition to the data valuation literature. The method has some shortcomings and the paper could be improved in a couple places, but I view it favorably overall. If the authors could make some of the changes mentioned in my review, I would be inclined to raise my score.", "strength_and_weaknesses": "--- Strengths ---\n\n- A reasonable and relatively simple approach to quantify the value of individual training samples: the difference in a data complexity measure (the complexity gap score).\n- An interesting application of the generalization gap analysis for two-layer networks from Arora et al (2019).\n- The authors consider how to minimize computation time by reducing the number of matrix inversions.\n- One of very few methods that enables dataset pruning without performing a full training run.\n- The authors elaborate on the mathematical relationship between the complexity gap score several existing scores (\"Correlation to other scores\").\n- Provides similar or better performance to existing methods in the experiments with FashionMNIST, CIFAR-10/100\n\n--- Weaknesses ---\n\n- Heavily based on ideas from Arora et al (2019). I personally don't view this as a major shortcoming, I think it's a valuable insight that work from a very different part of the field is applicable here.\n- The authors could consider adding an appendix section to walk through their derivations for eq. 3-4 in more detail. It took me a while to see where these results come from, particularly the part about the Schur complement (it seems related to the formula for inversion of block matrices, which was not mentioned).\n- Could the authors provide more information about the running-time they observe in practice? It seems important to know how the large matrix inversion $(\\mathbf{H}^\\infty)^{-1}$ compares to a single training run, or how much the computation is reduced when performing the stochastic calculation.\n- In the experiments, the C-score doesn't appear to have been used for Fashion-MNIST (Figure 2). Is there a reason for this, would the authors be able to add it?\n- One shortcoming in this approach seems to be that we expect large complexity gap scores both for useful/difficult samples and for samples with incorrect/noisy labels. This means that if we prune the dataset by keeping only samples with large scores, we're likely to retain samples with incorrect labels. I suspect this issue does not exist for any previous method that explicitly evaluates performance on a validation/test set when training with partial training sets. Could this be discussed/acknowledged somewhere in the paper?\n\nAbout the method:\n- It would be nice to allude to several implementation details in the main text, such as how you ensure scalar labels, $|y| < 1$, vector-shaped inputs and $||x||_2 = 1$. I see that these were described in Appendix A, but this would have been nice to point to more clearly, perhaps in the experiments section.\n- The stochastic calculation approach was not mentioned at all in the main text, but it seems to play a crucial role in reducing the practical computation time. Is that what was used throughout the experiments? The sanity check with Spearman's rank correlation is helpful, but could the authors also include a plot with Pearson's correlation? I would hope that we see the results converging to something closer to 1, because Pearson's will be less sensitive to small disagreements between the lowest scores.\n- Do the authors have any practical recommendations for determining the required number of runs required for convergence of their stochastic approach? Could it be significantly different for different datasets?\n\nA couple missing works that should probably be mentioned:\n- TracIn [1] belongs to the family of methods that analyze training dynamics to understand the value of each sample in the dataset. This should probably be cited and could even be considered as an additional baseline for the complexity gap score.\n- There's a paper that attempts to derive a closed-form solution for the Data Shapley values [2], and I believe it doesn't require training a model either. The results end up being bounds rather than the exact values, but I think this work ends up falling in the same category. This work should definitely be mentioned, and perhaps compared against in the experiments.\n\n[1] Pruthi et al, \"Estimating training data influence by tracing gradient descent\" (2020)\n[2] Kwon et al, \"Efficient computation and analysis of distributional Shapley values\" (2021)", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster