Robust Data Pruning under Label Noise via Maximizing Re-labeling Accuracy
Authors: Dongmin Park
Seola Choi
Doyoung Kim
Hwanjun Song
Jae-Gil Lee
Venue: NeurIPS 2023 poster (2023)
Keywords: Data Pruning
Data Subset Selection
Noisy Labels
Relabeling
Self-training
TL;DR: In this paper, we propose a new data pruning algorithm under label noise that maximizes the Re-labeling accuracy of the total training set.

Abstract: Data pruning, which aims to downsize a large training set into a small informative subset, is crucial for reducing the enormous computational costs of modern deep learning. Though large-scale data collections invariably contain annotation noise and numerous robust learning methods have been developed, data pruning for the noise-robust learning scenario has received little attention. With state-of-the-art Re-labeling methods that self-correct erroneous labels while training, it is challenging to identify which subset induces the most accurate re-labeling of erroneous labels in the entire training set. In this paper, we formalize the problem of data pruning with re-labeling. We first show that the likelihood of a training example being correctly re-labeled is proportional to the prediction confidence of its neighborhood in the subset. Therefore, we propose a novel data pruning algorithm, Prune4Rel, that finds a subset maximizing the total neighborhood confidence of all training examples, thereby maximizing the re-labeling accuracy and generalization performance. Extensive experiments on four real and one synthetic noisy datasets show that Prune4Rel outperforms the baselines with Re-labeling models by up to 9.1% as well as those with a standard model by up to 21.6%.

Robust Data Pruning under Label Noise via Maximizing Re-labeling Accuracy
Dongmin Park', Seola Choi', Doyoung Kim', Hwanjun Song?, Jae-Gil Lee
KAIST," AWS AI Labs
(dongminpark, seola. choi, dodokim, jaegil)kkaist. ac ac.kr, kr, hwanjun. hwanjun. sta.jj/sssnnnmmaaoo..cmm com
Abstract
Data praning, which aims downsize a large training set into small informative subset, is crucial for reducing the enormoos computational costs of modern deep learning. Though large-scale data collections invariably contain annotation noise and numerous robust learning methods have been developed, data pruning for the noise-robust learning scenario has received little attention. With state-of- the-art Re-labeling methods that self-correct erroneous labels while training, it is challenging identify which subset induces the most accurate re-labeling of erroneous labels in the entire training set. In this paper, we formalize the problem of data pruning with re-labeling. We first show that the likelihood of a training example being correctly re-labeled is proportional to the prediction confidence of its neighborhood the subset. Therefore, we propose a novel data pruning algorithm, Prune4Rel., that finds a subset maximizing the total neighborhood confidence of all training examples, thereby maximizing the re-labeling accuracy and generalization performance. Extensive experiments on four real and one synthetic noisy datasets show that Prune4ReL. outperforms the baselines with Re-labeling models by up 9.1% 1% as well as those with standard model by up to 21.6%.
Introduction
where the model accuracy often increases as a power the training set size, modern deep learning has achieved unprecedented success in many domains, e.g., GPT [3. CLIP 4 and VIT (5). With such massive datasets, however, practitioners often suffer from enormous computational costs for training models, tuning their hyper-paramettrs, and searching for the best architectures, which become the main bottleneck of development cycles. One popular framework to reduce these costs data pruning, which reduces a huge training set into small subset while preserving model accuracy. Notably, Sorscher et al. (6) have shown that popular data pruning approaches can break down the neural scaling law from plwer-law to exponential scaling, meaning that Despite their great success, the impact of label noise on data pruning has received little attention, which is unavoidable in real-world data collection 7 g
By virtue of ever- growing datasets and the neural scaling law 212.
reach desired model accuracy with much fewer data.
Noisy labels are widely known to severely degrade the generalization capability of deep learning, and thus numerous robust learning strategies have been developed to overcome their negative effect in deep learning [10]. Among them, Re-labeling 11, a family of methods that identify wrongly labeled examples and correct their labels during training by self-correction module such as self-consistency regularization [2], has shown state-of-ther oftthe-rtt performance. For example, the performance of Di- videMix
[ trained on the CIFAR-ION (7] dataset containing real human annotation noise is nearly identical to that of a standard model trained on the clean CIFAR-10 10 dataset. Consequently, it is evident that this excellent performance of re-labeling must be carefully considered when designing framework for data pruning under label noise.
"Coresponding author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

92
Iest Accuracy (%)
Incorbet
ee-labeling
Bandon
86
Suallloo
Contect
84
Fergetting
Grahia
te-libeling
Prinediel
82
0.2
0.4
0.6
0.8
Seloction Ratio
Data Example
Neighborhood
[*e]Selected Set ( Re-labeling Coverage
(a) Pruning Performance.
(b) Re-labeling by Neighborhood.
(c) Goal of Prume4ReL.
Figure 1: Key idea of Prune4ReL: (a) shows data pruning performance of Prune4ReL and exist- ing sample selection methods on DIFAR-ION with DivideMix; (b) shows how the neighborhood confidence affects the re-labeling correctness; (c) shows the goal of Prunc4ReL that maximize the neighbor confidence coverage the entire training set, thereby maximizing the re-labeling accuracy.
In this paper, we formulate new problem of data praning with re-labeling for training set with noisy labels, which aims to maximize the generalization power of the selected subset with expecting that a large proportion of erroneous labels are self-corrected (i.e., re-labeled). Unfortunately, prior data pruning and sample selection algorithms are not suitable for our problem because the re- re-labeling capability is not taken into account, and have much room for improvement as shown Figure a Popular data pruning approaches (denoted as Forgetting [14] and GraNd [15] in blue and yellow, respectively) favor hard (i.e., uncertain) examples because they are considered more beneficial for generalization [6]; however, because it is very difficult to distinguish between hard examples and incorrectly -eooreecly-labeleed
labeled examples [17] many of the incorrectly-laheles examples can be included the subset causing unreliable re-labeling. In addition, the small-loss trick [18] (denoted as SmallLoss in green) for sample selection favors casy examples because they are likely to be correctly labeled; however, they are not beneficial for generalization problem necessitates the development of a new data pruning approach.
later stage of training. Therefore, this new
Accordingly, we suggest a completely novel approach of finding subset of the training set such that the re-labeling accuracy of all training examples preserved as much as possible with the model truined on the subset. The first challenge in this direction is how to estimate whether each example can be re-labeled correctly even before fully training models on the candidate subset. The second challenge is how to find the subset that maximizes the overall re-labeling accuracy of the entire training set in an efficient manner.
Addressing these two challenges, we develop a novel framework, called Prune4ReL. For the first challenge, we define the concept of the neighborhood confidence which is the sum of the prediction confidence of each neighbor example in the selected subset. We show that, as in Figure lb). an example with high neighborhood confidence is likely to be corrected by Re-labeling methods. We further provide theoretical and empirical evidence of this argument. For the second challenge, we show that the overall re-labeling accuracy maximized by selecting a subset that maximizes the sum of its reachable neighborhood confidence for all training examples, as shown in Figure [c). Furthermore, because enumerating all possible subsets a combinatorial optimization problem which is ha-hard [19], we provide an efficient greedy selection algorithm that expands the subset one by one by choosing the example that most increases the overall neighborhood confidence.
Extensive experiments on four real noisy datasets, CIFAR-ION, CIFAR-1OON, WebVision, and Clothing- 1M, and one synthetic noisy dataset on ImageNet- 1K show that Prune4ReL consistently outperforms the eight data pruning baselines by up to 9.1%. Moreover, Prune4ReL with Re-labeling models significantly outperforms the data pruning baselines with a standard model by up 21.6%. which reaffirms the necessity of data pruning with re-label
2 Preliminary and Related Work
2.1 Robust Learning under Noisy Labels
long line of literature has been proposed to improve the robustness of DNNs against label noise, and refer to [10] for detailed survey for deep learning with noisy labels. While some studies have

---

focused on modifying the architectures 20] 21 [2 and the loss functions [23 24 25 others have opted for sample selection approaches [26] 18 27 28 that select as many clean examples as possible while discarding noisy examples based on a certain cleanness criterion, e.g. small-loss [18] Note that, these works do not consider the compactness or efficiency of the selected subset. Meanwhile, to further exploit even noisy examples for training, Re-labeling [1] [9] approaches try to correct noisy labels and reuse them for training with re-labeling module, e.g., a heuristic rule [[]. Notably, according to recent benchmark studies on real-world noisy datasets (7), a family of Re-labeling methods with self-consistency regularization 12 has shown state-of-the-ari performance.
In general, Re-labeling methods with self-consistency regularization are based on
Ree-lablingg (D:0,A)
Σ (a..))
1(c_())20 G: 0) + A Σ mED
Grey 0,A),
where D - {
7:) is a given noisy training set obtained from noisy joint distribution X' x } 0 is a classifier, A is strong data augmentation, C.(-) is a prediction confidence score, and is threshold to identify confident (clean) examples for the supervised loss Lee (z. ÿ: f), i.e., cross- entropy. The noisy labels are implicitly corrected by the conficcnni loss Lreg (z; 9) leveraging the power of strong augmentations [30]. DivideMix [33] ELR+ B1, CORES [32 and SOP+ [33
are popular approaches belonging to this family. DivideMix uses a co-training framework to further improve the re-laheling accuracy, and SOP+ introduces additional learnable variables combined with a self-consistency loss. For simplicity, we call this Re-labeling family with self-consistency regularization as "Re-labeling" throughout the paper. Despite their effectiveness, Re-labeling models tend to require more computation time due to additional data augmentations, multiple backbones, and longer training epochs, which raises a need enhance its efficiency.
2.2 Data Pruning
In order to achieve high generalization performance with a selected subset, most data pruning approaches often prioritize the selection of hard or uncertain examples. Specifically, uncertainty- based methods [34] 35 36) favor selecting less confident examples over more confident ones, as the former is assumed to be more informative than the latter. Similarly, geometry-
methods (37 38 focus on removing redundant examples that are close to each other in the feature space, and bass- methods [44 39 40) favor selecting the examples with high loss or gradient measured during training. However, these existing methods may not be effective in realistic scenarios under label noise because noisy examples also exhibit high uncertainty and could be wrongly considered informative for training [14]. Meanwhile, some recent works reported that existing data pruning methods do not work well at high pruning ratios 41 2
To alleviate this drawback, ALADP 41 shows that mixing various levels of uncertain examples is better for data scarcity, Moderate [43] aims to select examples with the distances close to the median, and CCS (42) proposes a coverage- based method that jointly considers data coverage with sample importance. While a few works attempted to improve the robustness of sample selection against label noise by filtering the noise [9] no work yet considers the effect of data pruning on noise-robust learners such as Re-labeling.
3 Methodology
We formalize a problem of data pruning with re-labeling such that it finds the most informative subset S. where model 0s trained on S maximizes the re-labeling accuracy of the entire noisy training set
D = [11 0.)) Formally, we aim to find an optimal subset S* such that
S argmax
Σ 1)s(m:s)) = =-] : 0s argmin CRe-tabeting (S: (S:),A), (x.0)D
(2)
S: 18IS
0
where y" is the ground-truth label of a noisy example x, f(x; 0s) E R is a c-way class prediction of the example from the Re-labeling model 0g. and is the target subset size.
Finding the optimal subset S* through direct optimization of Eq. 22 infeasible because the ground- truth label y" is unknown in practice. In addition, the subset should be found at the early stage of
Maximizing the re- re-labeling accuracy is equivalent to correctly re-labeling all training examples. This formulation enables the model to exploit all clean labels for training, leading to satisfactory generalization.
3

---

training, i.e. in a warm-up up period, to reduce the computational cost [[]. To achieve these goals in an accurate and efficient way, in Section 3.1 we first introduce a new metric, the reduced neighborhood confidence, that enables estimating the re-labeling capacity of a subset even in the warm-up period. Then, in Section 3.2 we propose new data pruning algorithm Prune4Rel. using this reduced neighborhood confidence to find a subset that maximizes the re-labeling accuracy.
3.1 Reduced Neighborhood Confidence
As measurement of estimating the re-labeling accuracy, we use the confidence of neighbor examples for each target noisy example x, because the noisy examples are known to be corrected by their clean neighbor examples with self-consistency regularization [44]. Specifically, once an augmentation of noisy example has similar embedding to those of other clean neighbors in the representation space, the self-consistency loss can force the prediction of the noisy example to be similar to those of other clean neighbors as a way of re-labeling. This property is also evidenced by a theory of re- re-labeling with generalization bound [45]. Thus, the neighboring relationship among examples can be clear clue to estimate the re-labeling accuracy even in the early stage of training.
We define neighborhood and its reduced neighhorhood confidence to utilize the relationship of neighboring examples in Definitions 3.1 and 3.2
Definition 3.1. (NEIGHBORHOOD). Let B(x,) = {x: [|A(x;)) - x|| I <} be a set of all possible augmentations from the original example z; using an augmentation function A. Then, given noisy training set D, neighborhood of r; is defined as (xx;)) {ar D: B(x;) n ((x) + 0}. which is the set of examples that are reachable by the augmentation A.
Definition 3.2. (REDUCED NEIGHBORHOOD CONFIDENCE). The reduced neighborhood confidence Cxy S) of an example x; is the sum of the prediction confidence C1() of its neighbors zj E (z;,)) in given reduced (i.e., selected) subset S, which is formalized as
C) = Σ (pyeN(a))) C(zy), 2,E8
and its empirical reduced neighborhood confidence is computed by using the cosine similarity among the augmentations of all possible pairs of example embeddings,
Cx(:;:))= = Σ H(sim(A(esssAAttt)))2) sim (5m((A(;). C(xy), ZJES
where sim(-) is the cosine similarity between the augmentations A(x) of two different examples in the embedding space, and a threshold determine whether the two examples belong to the same neighborhood. Unlike Fq. (3). Eq. { is calculated as weighted sum of prediction confidences with cosine similarity to approximate the likelihood of belonging to the neighborhood.
Based on these definitions, we investigate the theoretical evidence of employing the reduced neigh- borhood confidence as a means estimate the re-labeling capacity of subset.
Theoretical Evidence. A subset S with a high value of the total reduced neighborhood confidence, the sum of the reduced neighborhood confidence of each example in S, allows a Re-labeling model to maximize its re-labeling accuracy in the entire training set. We formally support this optimization by providing theoretical analysis that extends the generalization bound in the prior re-labeling theory 45 to data pruning.
Assumption 3.3. (EXPANSION AND SEPARATION). Following the assumption in 45 the expansion and A-separation assumptions hold for the training set D. The a-expansion means that an example is reachable to the a number of augmentation neighbors on average, i.e., [ The --separation means that data distributions with different ground-truth classes are highly separable, such that the average proportion of the neighbors from different classes is as small as 3.
a.
Under these assumptions, we can obtain a training accuracy (error) bound of Re-labeling model trained on a subset S' as in Theorem 3.4

---

Theorem 3.4. Assume that subset S E 'D follows as expansion and Bs Bs-separation. where as S a. Then, the training error of a Re-labeling model fs trained on S is bounded by the inverse of the total reduced neighborhood confidence ExED Cx(ar; S) such that,
2. 2-151 (rr((O))
+ 2.as
Err(Os) - ΣIED Cxr(2; S)
as 1 3s.
(5)
where M is model trained with the supervised loss in Eq. I on a given clean set M S.
Proof. We extend the label denoising theorem in [45] by incorporating the influence of the subset to the expansion factor ag. The complete proof is available in Appendix
Since is is usually very small, its effect on the error bound is negligible. Then, the bound highly depends on the total reduced neighborhood confidence. That is, as the total reduced neighborhood confidence increases, the error bound becomes tighter. This theorem supports that we can utilize the reduced neighborhood confidence for the purpose of maximizing the re-labeling accuracy.
Empirical Evidence. To empirically support The- orem 3.4 we validate the correlation between the
Re Accuracy
Utility
Converge
empirical reduced neighborhood confidence and the re-labeling accuracy using CIFAR- 1ON, which is real-world noisy benchmark dataset.
D Decrease
Specifically, we train DivideMix 13 the 20% ran- domly selected subset for a warm-up training epoch of 10 and calculate the empirical reduced neighbor- hood confidence (x; S) for the entire training set. Next, we fully train DivideMix [13] on the random subset S. Last, divide the entire training set into 15 bins according to the obtained Čxr(;; 8) and ver- ify the average re-labeling accuracy for each bin.
0.70
0.60
10
1/2
Empirical Neighborhood Conf. (x;
Figure 2: Correlation between neighborhood confidence and re-labeling accuracy on a 20% randomly selected subset of CIFAR-1ON.
Figure[showe how the re-labeling accuracy changes according the empirical reduced neighborhood confidence in Eq. (4) (The term "empirical" is simply omitted hereafter.) The re-labeling accuracy shows strong positive correlation with the reduced neighborhood confidence. Interestingly, as the neighborhood confidence increases, its utility improving the re-labeling accuracy decreases, eventually reaching convergence point after surpassing certain threshold.
3.2 Data Pruning by Maximizing Neighborhood Confidence Coverage
We present a new data pruning algorithm called Prune4ReL which optimizes the total reduced neighborhood confidence defined in Eq. ④ This objective is equivalent to identifying a subset that maximizes the re-labeling accuracy on the entire training set, as justified in Theorem 3.4 Therefore, the objective of Prune4ReL is to find the subset S*, which is formulated as
S
argmax S:
Σ (C)(=:))), 18|S
RIED
where (2) is utility function of the reduced neighborhood confidence CN S) in improving the re-labeling accuracy. By the observation in Figure 2 we define (2) as a non-decreasing and concave function where (0) 0. In our implementation, as the utility function, i.e., (=)) = tanh(z). However, directly solving Eq. (6) is computationally expensive and impractical due to its NP-hard nature as Set-Cover problem 19. Accordingly, employ an approximation solution to efficiently address this combinatorial optimization.
the positive of the tanh function
Optimization with Greedy Approximation. We present a practical solution for solving the optimiza- tion problem stated in Eq. (6) using a greedy approximation. The objective function satisfies both the monotonicity and submodularity conditions, indicating that the return of the objective function monotonically increases and the marginal benefit of adding an example decreases as the subset grows. Thus, a greedy sample selection can be employed in Algorithm I
RRnndAug [30] is used as the augmentation function for the reduced neighborhood confidence.
5

---

In detail, we begin with an empty set S and ini- tialize the reduced neighborhood confidence ČN to 0 (lowest confidence) for all training ex- amples (Line 1). Next, at every step, we select an example æ that maximizes the marginal benefit (Cx(2) + C(+)) - (Cx(z)) of Eq. O and update the reduced neighborhood confidence EN based the similarity scores (Lines 3-7). To further improve robustness and efficiency, we introduce class-balanced version, Prune4Rel-p, of which the detailed process is elaborated Appendix B
Algorithm 1 Greedy Neighborhood Confidence
INPUT:
D: training set, 8: target subset size, and C(r):
confidence from warm-up classifier
1: Initialize t 0; Va E D, Cx(x)= =0
2: repeat
== aargmaa..ev (oee)
4: S=SU {σ}
5: for all E D do
(v((v) += (0im(x,0)27) sim(z, C(xx)
until S|
OUTPUT: Final selected subset S
In Theorem 3.5 we guarantee the selected subset S obtained by our greedy solution achieves a (1-1/e) 1eee-//epppppe approximaxi of the optimum.
Theorem 3.5. Since Eq. (6). denoted as OBJ, is a monotone, submodular, and non-negative on x, the greedy solution provides a set with a (1 (L--1ee)-pppretl -apeaaappooinntaoonn of the optimun. Formally,
OBJ(S) 2 (1 - 1/c)) OBJ(SS).
Proof. We prove the monotonicity and submodularity of Eq. (6. If the two conditions are satisfied, Eq. naturally holds. See Appendix C for the complete proof.
Time Complexity Analysis. We analyze the time complexity of our greedy approximation in Algorithm [
At each step, Prune4ReL takes the time complexity of Om log m) O(m)), where m is the training set size and is the embedding dimension size of the warm-up classifier. Specifically, in Line 3, sampling an example with the largest marginal benefit of confidence takes 0m log m), and in Lines 5-6, updating the reduced neighborhood confidence of all training examples takes ((m)). In addition, with Prune4ReLg, the time complexity is reduced to O(m log(m/c)) (mm)) because it iteratively selects the example with the largest marginal benefit within each class subset, which is lower than the time complexity of a similar distance- based data pruning work, kCenterGreedy (38) aiming to maximize the distance coverage of a selected subset to the entire training set by a greedy approximation. At each iteration, kCenterGreedy's runtime is ((mke). where ke is the size of the selected set at iteration [46). Note that, its time complexity increases as the subset size grows, which hinders its usability on a large-scale dataset. In Section 4.2, we empirically show that Prune4ReL is scalable to prune Clothing- IM, a large dataset with IM examples, whereas kCenterGreedy is not.
4 Experiments
4.1 Experiment Setting
Datasets. We first perform the data pruning task on four real noisy datasets, CIFAR-ION CIFAR- 100N, Webvision, and Clothing IM. CIFAR-10N and CIFAR- CIFAR-1OON 77] contain human renanottasoons of 50K training images in the original CIFAR- 10 and CIFAR- 100 [47]. Specifically, each training
image in CIFAR-1ON contains three noisy labels, called Random 1,2,3, which are further transformed into the Worst-case label. Each image in CIFAR- 100N contains one noisy label. WebVising [ and Clothing- [9] are two large-scale noisy datasets. WebVision contains 2.4M images crawled from the Web using the 1,000 concepts in ImageNet- 48). Following prior work [49], we use mini-
mini-Web WebVision consisting of the first 50 classes of the Google image subset with approximately 66K training images. Clothing- 1M consists of 1M training images with noisy labels and 10K clean test images collected from online shopping websites. Additionally, a large-scale synthetic noisy dataset, which we call ImageNet-N, is included in our experiments. It consists of 1.2M training images, which are the training images of ImageNet-I1 48 with asymmetric label noise. See Appendix for details of the noise injection.
Algorithms. We compare Prune4ReL with a random selection from a uniform distribution, Uniform, a clean sample selection algorithm, Smalll loss (26.. and six data pruning algorithms including Mar- gin (50), k- k-CenterGreedy (38), Forgetting 14) GraNd [5], SSP (,, and Moderate 4 SmallL Loss favors examples with small loss. For data pruning algorithms, (1) Margin selects examples in the

---

Table I: Performance comparison of sample selection baselines and Prune4ReL on CIFAR-1ON and CIFAR-10ON, The best results are in bold.
CIFAR-ION
CIFAR-100N
Re-label Models
Selection Methods
Random
Wonst
Noisy
0.4
0.4
0.6
0.2
0.8
Uniform
87.5a02
91.9aa2
93.7am.
94.8
83.2 88.5
90.2
91.4
30.5 55.3
57.5 58.6
SmallL
68.1440
82,4a04
89.0 93.1
70.3 80,3
19.1 92.1 10
33.3 47.4=111 59,4 62.0=12
Margin
68.5+29
88.5mma 93,2a02 94.7=0.1
61.3a0s 75.1 85,3en2 90.2
17.1=03 30.8=1. 46.3+22 61.2+1a
kCenter
87.4405
93,0aa1 94,4 95.0eea
82.7=0s 88,40ai 90,6ea)
92.2=a.
38.0=110 50.0=18 59.7=13 63.0e0d
DivMix
Forget
85,2+05
93,0sa2 94.5 +5,1
78.3 88,3e02
90,4 02.00
26,421.3 54.3
63.1 66.6
GraNd
21.8 60.9s45 92.5 94, 8:s..1
18.5 25.5
49.3 88 0
15.5 26.0=1.9
44.7 60,4
SSP
85,8+1s 92.2a115
93,0=11 94.5
81,4=25 86.5e1
89.6 91. 4.
30.1=2.2 52,4=1. 58.7=00 63,4
Moderate
86,440s 91,4a9a
93,8e05 94. 24.8
81.4=112 86.5e06
90.0ees 91 6
34,2+14 54,5 56.1=00 59,9=0s
Pr4ReI.
87.610s
92 94. 15.1
83.7.00
88.81a1
90.2gmm 92.0gmm
37.2110 55.3.00
61.2.00 65.5
Pr
88,1
93,0sa2 94.5 +5.1
83.7=04 88.6504
90.8 92.4
39.4:00 56.3
63.5 67,4000
Uniform
87.5 91.5 93.4 $4.8
81.9201 87.5
90.8 91.8
46.5 55.7:u2 60.8 64.4
SmallL
77.6+25
86.2=n) 90,7=0z 94. 3403
78.8=02 84.1=01
89,3
92. 32.3
48.5+00 59.8=n4 63 9.90 =6.1
Margin
52.1=59
79.6*86 92,6=30 15.1+13
45.7=11
61.8+07
84.6e03 92.5+a0
20.0=1.2 34,4=003 50,4e00 63.9eau
kCenter
86.3+04
92.2=00 94.1 95.3
81.9=0.
88.0s00 91.3em. 92.3
44,8=00 55.9 61.6e033 65.2=00
Forget
82.4gin 93.0gn3 94,2203 95 0.5.1
=1. 87.7aa1 90.6gn3 92, 22.
38.0g00 55.3 63.2 65.8
SOP+
GraNd
24.2a55
$1.6532 85,9 94. 9asa
15.4 25.7a00 $1.0anz 86 8:0.
11.0g00 19.0=no 38 7,05 62, 100
SSP
80.5+26
91.7=15 93.8 95.0ee2
70.8=27
86.6+1. 89. 29.2 92.3
39.2+22 54.9=15 62.7=07 65 65.0e03
Moderate
87,8+1 92,8=05 94,0a03 94,9w02
75,2+15
81,9+12 87,7=07
91,8
46.4+1. 54.6=117 60 60.2 64,6=04
Pr4Rel,
87.8111 92,71m1 94,4 95. I Las.
82.7.ns
88.1
91.3gm1 92.5
50.21,0
59.1 63.9.00 65.7gn9
Pr
88.5 93.1=n2 94.400. 95.3
84.9=as 89.2 91.3en. 92.9
52,9 60.1 64.1 66.2
increasing order of the difference between the highest and the second highest softmax probability; (2)
CenterGreedy selects i examples that maximize the distance coverage to the entire training set; (3)
Forgetting selects examples that are easy to be forgotten by the classifier throughout the warm-up
training epochs; (4) GraNd uses the average norm of the gradient vectors to measure the contribution
of each example to minimizing the training loss; (5) SSP leverages self-supervised pre-trained model to select the most prototypical examples; and (6) Moderate aims to select moderately hard examples using the distances to the median.
Implementation Details. We train two representative Re-labeling models. DivideMix [33 and SOP+ 33 for our experiments. The hyperparameters for DivideMix and SOP+ are favorably configured following the original papers. Following the prior Re-labeling work [13 33 for CIFAR- 1ON and CIFAR-10ON, PreAct Resnet- 18 (5T) is trained for 300 epochs using SGD with momentum of 0.9, a weight decay of O. 0.0005, and batch size of 128. The initial learning rate is 0.02, and is decayed with cosine annealing scheduler. For Web In 522 is trained for 100 epochs with a batch size of 32. For Clothing- 1M, we use ResNet-50 [53 pre-trained on ImageNet and fine-tune it for 10 epochs with batch size of 32. The initial learning rates of Web Vision and Clothing- 1M are 0.02 and 0.002, which are dropped by a factor of 10 at the halfway point of the training epochs. For ImageNet-N, ResNet-50 [53 is trained for 50 epochs with batch size of 64 and an initial learning rate of 0.02 decayed with a cosine annealing scheduler.
For data pruning algorithms, following prior work [16,, we perform sample selection after 10 warm- up training epochs for CIN,R-1ON, Web Vision, and ImageNet-N,, and 30 warm-up epochs for CIFAR-10ON, For Clothing-IM, we perform the sample selection after I warm-up training epoch from the ImageNet pre-trained ResNet-50. The hyperparameters for all data pruning methods are favorably configured following the original papers. For Prune4Rel., we set its hyperparameter to 0.975 for CIFAR- 1ON, to 0.95 for CIFAR- 10ON, WebVision, and ImageNet-N, and to 0.8 for Clothing- -M. More implementation details can be found in Appendix All methods are implemented with PyTorch 1.8.0 and exccuted on NVIDIA RTX 3080 GPUs The code is available at hhttp -mm-dmmllllll a
//github.comm/
Evaluation. For CIFAR- ION, CIFAR-10ON, and WisVis,on, we select the subset with the selection ratios (0.2, 0.4, 0.6, 0.8). For Clothing- 1M and ImageNet-N, we construct the subset with (0.01, 0.05, 0.1, 0.2) and [0.05, 0.1, 0.2, 0.4) selection ratios, respectively. We measure the test accuracy of the Re-labeling models trained from scratch on the selected subset. Every experiment is run three times, and the average of the last accuracy is reported. For CIFAR-ION with the Random noise, we average the test accuracy of the models trained using the three noisy labels.
7

---

Uniform
Margin cCenter
Porget GraNd
Moterate
100
Small:.
PruaetRela
Smatil
Elapsod Time (mrin)
80
Marqta
Test.Accura (%6
Gruldd
65
60
Kieeler
65
55
40
45
20
60
35
0.2
0.4
0.6
0.8
0.01
0.05
0.1
0.2
0
Selection Ratio
Selection Ratio
Selection Method
(a) Vision.
(b) Clothing-IM.
(c) GPU Time for Selection.
Figure 3: Data pruning performance comparison: (a) test accuracy of SOP+ trained on each selected subset Web WebVision; (b) test accuracy of DivideMix trained on each selected subset of Clothing- (c) clapsed GPU time for selecting subset Web Vision with selection ratio of 0.8.
Table Performance comparison of the standard cross-entropy model and Re-labeling models when combined with data pruning methods on CIFAR-ION and CIFAR-IOON.
CIFAR-ION
CIFAR-IOON
Learning Models
Selection Methods
Random
Worst
Noisy
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
Uniform
75.6=0.1
81.0a0.1
83.0ga
84.3205
58.62033 63.9
66.4
67.5
37.44:02 46.1 =02 50. 1000
$2.3
Standard
SmallI. Forget
83.4 87.5103 90.1 2:0
10. 77.5 80.62005
76.4
42.21:0 54.7.05
57.7
57.4
82.2200 86.2go.
85.4200
71.2a 73.3
71.4200 69.629
43.5g10 54.5.01
57.5 56.6199
DivMix SOP+
Pr
88.1=0.3
93.0
94.5 95.1
83,7 88.6
90.8
92.4
39.4:00 56.3
63,5 67.4
PriReL_
88.5 93.1::0.2 94.4 95.3
:4.9 89.2 91.3g0.3
92.9
52,9205
60.1=06
64.1
66.2+00
4.2
Main Results on Real Noisy Datasets
Test Accuracy. Table D summarizes the test accuracy of eight baselines and Prune4ReL on CIFAR- 1ON and CIFAR- 100N trained with two Re-labeling models. Overall, Prune4ReL consistently achieves the best performance for all datasets across varying selection ratios. Numerically, Prune4ReL improves DivideMix and SOP+ by up to 3.7% and 9.1 %, respectively. Compared with six data pruning baselines, they show rapid performance degradation as the size of the subset decreases; most of them, which are designed to favor hard examples, tend to select a large number of noisy examples, resulting in unreliable re-labeling. While Moderate selects moderately hard examples, it is still worse than Prune4ReL. since it is not designed for noise-robust learning scenarios with Re-labeling models. On the other hand, SmallL clean sample selection baseline, shows poor performance in CIFAR- 1ON (Random), because this dataset contains relatively low noise ratio, and selecting clean examples is less critical. Although SmallLoss shows robust performance in CIFAR- 100N, is worse than Prunc4ReL because it loses many informative noisy examples that help generalization if re-labeled correctly. Meanwhile, Uniform is a fairly robust baseline as it selects easy (clean) and hard (noisy) examples in balanced way; many selected noisy examples may be relabeled correctly by other selected clean neighbors, resulting in satisfactory test accuracy.
Similarly, Figures 3(a) and (b) visualize the efficacy of the baselines and Prune4ReL the Wibiin and Clothing- IM datasets. We train SOP+ on WebVision and DivideMix on Clothing- IM. Similar to CIFAR-N datasets, Prune4Rel. achieves better performance than existing baselines on two datasets. Quantitatively, Prunc4ReL outperforms the existing sample selection methods by up to 2.7% on WebVision with a selection ratio of 0.4. This result confirms that the subset selected by Prune4ReL, which maximizes the total neighborhood confidence of the training set, successfully maintains the performance of Re-labeling models and is effective for model generalization.
Efficiency. In Figure c),,, we further show the GPU time taken for selecting subsets within the warm-up training. We train SOP+ on WebVision with a selection ratio of 0.8. Powered by our efficient greedy approximation, Prune4ReL fastly prunes the dataset in a reasonable time, GraNd takes almost 10 times longer than SmallLoss or Margin, since it trains the warm-up classifier multiple times for the ensemble. kCenterGreedy is infeasible to run our GPU configuration due to its huge computation and memory costs.
8

---

Table 3: Effect of the confidence metrics on Prune4ReL.
TestA ocunccy (%)
0.00
60
Re-label Model
Dataset
Conf. Metric
Selection Ratio
55
0.2
0.8
CIFAR-
MaxProb
82.7
92.5
SOP+
(Worst)
DillProb
82.5
92.5
Scloction Ratio
CIFAR-1000 10UN
MaxProh DitlProb
50.2
65.7
Figure 4: Effect of the neighbor-
hood threshold 7 on Prune4Rel.B.
4.3 Necessity of Data Pruning with Re-labeling under Label Noise
Table 2 shows the superiority of the Re-labeling models over the standard learning model, i.e., only with the cross-entropy loss, for data pruning under label noise. When combined with the data pruning methods, the performance of the Re-labeling models such as DivideMix and SOP+ significantly surpasses those of the standard models on CIFAR- and C1ONR-1OON by up to 21.6%. That is, the re-labeling capacity can be well preserved by a proper data pruning strategy. This result demonstrates the necessity of data pruning for the Re-labeling models in the presence of noisy labels.
4.4 Ablation Studies
Effect of Confidence Metrics. Prune4ReL. can be integrated with various metrics for the confidence of predictions Eq. (6). In our investigation, we consider two widely-used metrics: (1) MaxProb, which represents the maximum value of softmax probability and (2) DiffProb, which measures the difference between the highest and second highest softmax probabilities. Table T shows the effect of the two confidence metrics the test accuracy of SOP+ on CIFAR-ION (Worst) and CIFAR- 100N. The result indicates that both metrics perform similarly and yield higher accuracy compared to existing data pruning baselines, which demonstrates Prune4ReL is open to the choice of the confidence metric.
Effect of Neighborhood Size. Prune4Rel. involves a hyperparameter in Eq. 6 to determine the neighborhood of each example, where larger (smaller) value introduces a fewer (more) number of neighbors. Figure showws the effect of E {0.93, 0.95, 0.99} on the test accuracy of SOP+ trained on CIFAR-10ON with varying selection ratios. general, Prune4ReL shows better or comparable performance than other sample selection baselines. Among them, Prune4ReL. with = 0.95 shows a satisfactory accuracy across varying selection ratios. With smaller value of T = 0.93, shows the best performance in a high selection ratio of 0.8, but it becomes less effective in low selection ratios, due to the increasing influence of noisy examples caused by a relatively large neighborhood size. On the contrary, with large value of r 0.99, it primarily selects clean yet easy examples due to small neighborhood size, leading to a relatively less improvement performance.
4.5 In-depth Analysis of Noisy Examples in Selected Subset
Noise Ratio of Selected Subset. Table shows the ratio of noisy examples in the subset selected by each sample selection method. SmallLoss shows very low ratio of noisy examples in the subset because it prefers clean examples. Many data pruning methods, including Margin, GraNd, SSP, and Moderate (for CIFAR- CIFAR-IOON), tend to select a higher ratio of noisy examples compared with that of each original dataset since they prefer to select hard examples. On the other hand, Prune4Rel. selects low ratio of noisy examples when the subset size small and gradually increases the noise ratio the subset size increases. This result indicates that Prune4ReL expands the confident subset through Algorithm -ee.e selecting the most confident (clean) examples first and then trying to select less confident (hard or noisy) neighbors ensure accurate re-labeling, While some baselines, such as kCenterGreedy, Forget, and Moderate (for CIFAR-1ON), also select somewhat low ratio of noisy examples, their data pruning performances worse than Prune4ReL because the quality (or celf-correctability) of noisy examples is not considered when selecting the subset, which is further investigated in Table 5
Self-correctability of Selected Noisy Examples. Table the self-correctability of selected subsets, which indicates the ratio of correctly re-labeled noisy examples out of all selected noisy

---

Table 4: Ratio (%) of noisy examples in the selected subset.
Selection Mathods
CIFAR-ION (Random, 18%)
CIFAR-ION (Worst, 40%)
CIFAR- 100N (Noisy, 40%)
Model
0.8
0.4
SmalIL
0.1
0.2
1.0
4.0
0.8
3.6
11.5
26.2
3.5
8.7
16.3
27.4
Margin
29.7
25.7
22.5
19.7
54.6
52.1
48.5
44.6
61.5
56.8
51.6
46.2
kConter
19.0
18.8
19.1
18.6
40.0
41.1
41.6
42.1
37,5
38.7
39.9
40.4
Forget
17.0
17.7
17.5
17.8
37.7
38.8
39.2
40.2
37.9
34.6
33.0
36.8
SOP+
GraNd
67.5
41.7
28.6
21.5
91.5
79.4
64.2
50.1
93.9
57.3
61.2
49.3
SSP
25.2
23.7
21.6
19.5
48.5
46.4
43.2
42.1
52.7
52.3
46.8
43.0
Moderate
6.6
7.1
8.4
13.5
31.7
33.4
34.7
40.0
33.2
54.6
60.2
64.6
Pr4ReL
17.0
18.7
19.3
22.5
38.7
42.7
43.5
46.5
28.3
29.1
33.3
31.2
Table 5: Ratio of correctly re-labeled noisy examples in the selected subset (denoted as % Correct).
Table 6: Data pruning performance on Ima- geNet with 20% synthetic label noise.
Re-label Model
Selection Methods
ImageNer- IK (Syn, =s 20%)
Re label Model
Selection Methods
CIFAR-ION (Random)
0.05
0.1
0.2
0.4
Ace. % Noisy % Correct
Uniform
27.8
42.5
52.7
59.2
kCenter
86.3
19.0
75.2
SmallL
22.8
31.4
42.7
54.4
SOP+
SOP+
Forget
82.4
17.0
61.7
Forget
4.1
8.3
50.6
57.2
PriReL
88.1
17.0
90.3
PrdRel.
30.2
44.3
53.5
60.0
examples. Here, we compare Prune4Rel. with kCenterGreedy and Forgetting on CIFAR-1ON (Random) with the selection ratio of 0.2, where the ratio of noisy examples (i.e., % Noisy) in the selected subset of each method is similar (i.e., from 17% to 19%). Although these methods select almost equal amounts of noisy examples, there were differences in the self-correttabiliiy (i.e., %Correct) of the selected subsets. Noisy examples selected by Prune4ReL. are mostly self- correctable as it maximizes the total neighborhood confidence of the training set. contrast, those selected by existing data pruning methods such as kCenter and Forget are not guaranteed to be self-correctable. This result confirms that Prune4ReL not only selects low ratio noisy examples but also considers the quality of the selected subset in terms of maximizing re-labeling accuracy. Therefore, Prune4Rel. fully takes advantage the Re-labeling methods.
4.6 Results on ImageNet-N with Synthetic Label Noise
We further validate the efficacy of Prune4ReL on ImageNet-N by injecting synthetic label noise of 20% the commonly-used benchmark dataset ImageNet- IK (see Appendix D for details). Table 6 shows the test accuracy of Prune4ReL and three representative sample selection baselines with varying selection ratios of (0.05, 0. 0.2, 0.4). Similar to the result in Section 4.2 Prune4Rel. consistently outperforms the baselines by up to 8.6%, thereby adding more evidence of the superiority of Prune4ReL. In addition, owing to its great computation efficiency, Prune4ReL. is able scale to ImageNet-N, large-scale dataset with approximately 1.2M training examples.
5 Conclusion
We present a noise-robust data pruning method for Re-labeling, called Prune4ReL, that finds a subset that maximizes the total neighborhood confidence of the training examples, thereby maximizing the re-labeling accuracy and generalization performance. To identify subset that maximizes the re- labeling accuracy, Prune4ReL introduces novel metric, the reduced neighborhood confidence, which the prediction confidence of each neighbor example in the selected subset, and the effectiveness of this metric in estimating the re-labeling capacity of subset is theoretically and empirically validated. Furthermore, we optimize Prune4Rel. with an efficient greedy algorithm that expands the subset by selecting the example that contributes the most to increasing the total reduced neighborhood confidence. Experimental results demonstrate the substantial superiority of Prune4Rel. compared to existing data pruning methods in the presence of label noise.
10

---

Acknowledgement
This work was supported by Institute of Information Communications Technology Planning Evaluation (ITPP) grant funded by the Korea government (MSIT) (No. 2020-0-00862, DB4DL: High- Usability and Performance In-Memory Distributed DBMS for Deep Learning and No. 2022-0-00157, Robust, Fair, Extensible Data-Centric Continual Learning).
References
[1] Joel Hestness, Sharan Narang, Newsha Ardalani, Gregory Diamos, Heewoo Jun, Hassan Kianinejad, Md Patwary, Mostofa Ali, Yang Yang, and Yanqi Zhou. Deep Learning Scaling is Predictable, Empirically. arXiv preprint arXiv: 1tt.f::1122.004400 2.0009, 2017.
[2] Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling Laws for Neural Language Models. arXiv preprint arXiv:2001.000 0.3361, 2020.
[3] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language Models Few-shot Learners. In NeurIPS, pages 1877-1901, 2020.
[4] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning Transferable Visual Models from Natural Language Supervision. In ICML, pages 9748-8763, 2021.
[5] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale. arXiv preprint arXiv:2010.11929, 2020.
[6] Ben Sorscher, Robert Geirhos, Shashank Shekhar, Surya Ganguli, and Ari Morcos. Beyond Neural Scaling Laws: Beating Power Law Scaling via Data Pruning. In NeurIPS, pages 19523-19536, 2022.
[7] Jiaheng Wei, Zhaowei Zhu, Hao Cheng, Tongliang Liu, Gang Niu, and Yang Liu. Learning with Noisy Labels Revisited: Study using Real-world Human Annotations. arXiv preprint arXiv:2110. 10..1110122000 12088, 2021.
[8] Wen Li, Limin Wang, Wei Li, Eirikur Agustsson, and Lue Van Gool. Webvision Database: Visual Learning and Understanding from Web Data. arXiv preprint arXiv: 02800262, 2017.
[9] Tong Xiao, Tian Xia, Yi Yang, Chang Huang, and Xiaogang Wang. Learning from Massive Noisy Labeled Data for Image Classification. In CVPR, pages 2691-2699, 2015.
[10] Hwanjun Song, Minseok Kim, Dongmin Park, Yooju Shin, and Jae-Gil Lee. Learning from Noisy Labels with Deep Neural Networks: Survey. TNNLS, pages 1-19, 2022.
[11] Hwanjun Song, Minseok Kim, and Jae-Gil Lee. Selfie: Refurbishing Unclean Samples for Robust Deep Learning. In ICML, pages 5907-5915, 2019.
[12] Qizhe Xie, Zihang Dai, Eduard Hovy, Thang Luong, and Quoe Le. Unsupervised Data Augmentation for Consistency Training. In NeurIPS, pages
2020.
[13] Junnan Li. Richard Socher, and Steven CH Hoi. Dividemix: Learning with Noisy Labels as Semi-supervised Learning, arXiv preprint wwXiv:2002.07394 2020.
[14] 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. arXiv preprint /
2018.
[15] Mansheej Paul, Surya Ganguli, and Gintare Karolina Dziugaite. Deep Learning on a Data Diet: Finding Important Examples Early in Training. In NewrIPS, pages 90596-20601 2021.

---

[16] Chengcheng Guo, Bo Zhao, and Yanbing Bai. Deepcore: A Comprehensive Library for Coreset Selection in Deep Learning. In DEXA, pages 181-195, 2022.
[17] Dongmin Park, Yooju Shin, Jihwan Bang, Youngjun Lee, Hwanjun Song, and Jae-Gil Lee. Meta-Query-Net: Resolving hurty-nnformaaiveness Dilemma in Open-set Active Learning. In Neur/PS, pages 51416-31429, 2022.
[18] Bo Han, Quanming Yao, Xingrui Yu, Gang Niu, Miao Xu, Weihua Hu, Ivor Tsang, and Masashi Sugiyama. Co-teaching: Robust Training of Deep Neural Networks with Extremely Noisy Labels. In NeurlPS, pages 8536-85444 8546, 2018.
[19] Krishnateja Killamsetty, Durga Sivasubramanian, Ganesh Ramakrishnan, and Rishabh Iyer. Glister: Generalization based Data Subset Selection for Efficient and Robust Learning. In AAAI, pages 8110-8118 18, 2021.
[20] Jacob Goldberger and Ehud Ben-Reuven. Training Deep Neural Networks Using a Noise Adaptation Layer. In ICLR, 2017.
[21] Bo Han, Jiangchao Yao, Gang Niu, Mingyuan Zhou, Ivor Tsang, Ya Zhang, and Masashi Sugiyama. Masking: A New Perspective of Noisy Supervision. In NeurIPS, pages 5841-5851, 2018.
[22] Jiangchao Yao, Jiajie Wang, Ivor W Tsang, Ya Zhang, Jun Sun, Chengqi Zhang, and Rui Zhang. Deep Learning from Noisy Image Labels with Quality Embedding. TIP,
2018.
[23] Aritra Ghosh, Himanshu Kumar, and P Shanti Sastry. Robust Loss Functions under Label Noise for Deep Neural Networks. In AAAI, pages 1919-1925, 2017.
[24] Dan Hendryeks, Mantas Mazeika, Duncan Wilson, and Kevin Gimpel. Using Trusted Data to Train Deep Networks Labels Corrupted by Severe Noise. In NeurlPS, pages 10477-10486, 2018.
[25] Xingjun Ma, Hanxun Huang, Yisen Wang, Simone Romano, Sarah Erfani, and James Bailey, Normalized Loss Functions for Deep Learning with Noisy Labels. In ICML, pages 2020.
[26] Lu Jiang, Zhengyuan Zhou, Thomas Leung, Li-Jia Li, and Li Fei-Fei. Mentornet: Learning Data-driven Curriculum for Very Deep Neural Networks on Corrupted Labels. In ICML, pages 2304-2313, 2018
[27] Hongxin Wei, Lei Feng, Xiangyu Chen, and Bo An. Combating Noisy Labels by Agreement: A Joint Training Method with Co-regularization. CVPR, pages 13726-13735, 2020.
[28] Pengxiang Wu, Songzhu Zheng, Mayank Goswami, Dimitris Metaxas, and Chao Chen. A Topological Filter for Learning with Label Noise. In NeurlPS, pages 1/32221139,, 2020.
[29] Tianyi Zhou, Shengjie Wang, and Jeff Bilmes. Robust Curriculum Learning: From Clean Label Detection to Noisy Label Self-correction. In ICLR, 2021.
[30] Ekin D Cubuk, Barret Zoph, Jonathon Shlens, and Quoc V Le. Randaugment: Practical Automated Data Augmentation with a Reduced Search Space. In NeurlPS, pages 18613-18624, 2020.
[31] Sheng Liu, Jonathan WWeed Narges Razavian, and Carlos Fernandez-Granda. Early- learning Regularization Prevents Memorization of Noisy Labels. In NeurIPS, pages 20331- 20342, 2020.
[32] Hao Cheng, Zhaowei Zhu, Xingyu Li, Yifei Gong, Xing Sun, and Yang Liu. Learning with Instance-dependent Label Noise: A Sample Sieve Approach. arXiv preprint arXiv:2010.02337, 2020.
[33] Sheng Liu, Zhihui Zhu, Qing Qu, and Chong You. Robust Training under Label Noise by Over-parameeerizzaton.. In ICML, pages 14153-14172, 2022.
12

---

[34] Dan Wang and Yi Shang. A New Active Labeling Method for Deep Learning. In IJCN,, pages 112-119, 2014.
[35] Dan Roth and Kevin Small. Margin-based Active Learning for Structured Output Spaces. In ECML, pages 413-424, 424, 2006.
[36] Ajay Joshi, Fatih Porikli, and Nikolaos Papanikolopoulos. Multi-class Active Learning for Image Classification. In CVPR, pages 2372-23177 2009.
[37] Yutian Chen, Max Welling, and Alex Smola. Super-samples from Kernel Herding. arXiv preprint arXiv: 203.3442, 2012.
[38] Ozan Sener and Silvio Savarese. Active Learning for Convolutional Neural Networks: A Core-Set Approach. ICLR, 2018.
[39] Krishnateja Killamsetty, S Durga, Ganesh Ramakrishnan, Abir De, and Rishabh Iyer. Grad- match: Gradient Matching based Data Subset Selection for Efficient Deep Model Training, In ICML, pages 5464-5474, 2021.
[40] Baharan Mirzasoleiman, Jeff Bilmes, and Jure Leskovec. Coresets for Data-efficient Training of Machine Learning Models. In ICML, pages 6950-6960, 2020.
[41] Dongmin Park, Dimitris Papailiopoulos, and Kangwook Lee. Active Learning is Strong Baseline for Data Subset Selection. In NeurlPS Workshop, 2022.
[42] Haizhong Zheng, Rui Liu, Fan Lai, and Atul Prakash. Coverage-centric Coreset Selection for High Pruning Rates. ICLR, 2022.
[43] Xiaobo Xia, Jiale Liu, Jun Yu, Xu Shen, Bo Han, and Tongliang Liu. Moderate Coreset: A Universal Method Data Selection for Real-world Data-efficient Deep Learning. ICLR, 2022.
[44] Erik Englesson and Hossein Azizpour. Consistency Regularization Can Improve Robustness to Label Noise. arXiv preprint arXiv:2110.01242, 2021.
[45] Colin Wei, Kendrick Shen, Yining Chen, and Tengyu Ma. Theoretical Analysis of Self- with Deep Networks on Unlabeled Data. arXiv preprint arXiv:2010.03622, 2020.
[46] Gui Citovsky, Giulia DeSalvo, Claudio Gentile, Lazaros Karydas, Anand Rajagopalan, Afshin Rostamizadch, and Sanjiv Kumar. Batch Active Learning at Scale. In NeurIPS, pages 11933- 11944, 2021.
[47] Alex Krizhevsky, Geoffrey Hinton, et al. Learning Multiple Layers of Features from Tiny Images. Technical report, University of Toronto, 2009.
[48] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A Large-scale Hierarchical Image Database. In CVPR, pages 248-255, 2009.
[49] Pengfei Chen, Ben Ben Liao, Guangyong Chen, and Shengyu Zhang. Understanding and Utilizing Deep Neural Networks Trained with Noisy Labels. In ICML, pages 1062-1070, 2019.
[50] Cody Coleman, Christopher Yeh, Stephen Mussmann, Baharan Mirzasoleiman, Peter Bailis, Percy Liang, Jure Leskovec, and Matei Zaharia. Selection via Proxy: Efficient Data Selection for Deep Learning. arXiv preprint arXiv: 1oXiv:9900... 1906. 1989, 2019.
[51] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity Mappings in Deep Residual Networks. In ECCV. pages 630-645, 2016.
[52] Christian Szegedy, Sergey loffe, Vincent Vanhoucke, and Alexander Alemi. Inception-v4, inception-resnet and the Impact of Residual Connections on Learning. In AAAI, pages 4278- 4284, 2017.
[53] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep Residual Learning for Image Recognition. In CVPR, pages 770-778, 2016.
13

---

[54] Uriel Feige. A Threshold of In n for Approximating Set Cover. Journal of the ACM (JACM), 45(4):634-65 652, 1998.
[55] Qing Yu, Daiki Ikami, Go Irie, and Kiyoharu Aizawa. Multi-task Curriculum Framework for Open-set Semi-supervised Learning. In ECCV, pages 438 -544444,200 2020.
[56] Dongmin Park, Hwanjun Song, MinSeok Kim, and Jae-Gil Lee. Task-Agnostic Undesirable Feature Deactivation Using Out-of-Distribution Data. In NewrIPS, pages 4040 404404052, 2021.
[57] Matthias De Lange, Rahaf Aljundi, Mare Masana, Sarah Parisot, Xu Jia, Aleš Leonardis, Gregory Slabaugh, and Tinne Tuytelaars. A Continual Learning Survey: Defying Forgetting in Classification Tasks. PAMI, 3467),336-3385, 2021.
[58] Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Neural Architecture Search: A Survey. JMLR, 109))11977-2017, 2019.
14


Reviews:
[{"review_id": "m7a6rn49jY", "reviewer": "Reviewer_N3nf", "summary": "The paper proposes Prune4ReL, which prunes a noisy training dataset such that the performance of a Re-labeling trained downstream model is maximized. \nUnlike previous work, the paper targets pruning a *noisy* dataset and explicitly considers the learning algorithm of the downstream model. The proposed method is specifically tailored to Re-labeling, automatically cleaning the noisy training dataset.\nThe utility function in Prune4ReL is inspired by the theory proposed in [1] and gracefully incorporated into the context of data pruning. \nThe experimental results show that most prior work suffers under noisy datasets, while Prune4ReL remains robust to the noise in the training dataset, resulting in substantial improvements over baselines.\n\n[1] Theoretical Analysis of Self-Training with Deep Networks on Unlabeled Data, ICLR2021", "questions": "Experiment\n- Uniform sampling is usually the second-best baseline. It performs especially well in CIFAR-10N Random/Worst and Clothing-1M. Can the authors elaborate more on this? \n  - Do the authors believe the gap between uniform sampling and Prune4ReL is small due to the greedy sampling? Or what are the other hypothesis?\n- The derivation from the reduced neighbourhood confidence (Eq. 3) to the empirical reduced neighbour confidence (Eq.4) is confusing. What motivates using the cosine distance to perform a weighted sum? Is this motivated by importance sampling?\n- WebVision and Clothing-1M are crawled from the web, but Prune4ReL seems to work better in Clothing-1M. Can the authors elaborate on this further? \n  - It seems that kCenter and GraNd are missing in Figure 3b. The authors have to find a better way to visualize this plot (Figure 3b). Try to zoom in a little bit.\n- Section 4.5 is like the motivation of the paper. Consider re-order them.", "limitations": "As mentioned in the #weakness, there are some minor limitations.\n- Empirical results: The proposed method still requires some work on improving over uniform sampling baseline, and the authors did not justify the strong uniform baseline.\n", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The strength of the paper include\n- Clear presentation and easy-to-follow writing\n- The proposed method is theoretically-inspired and, maybe more importantly, easy to implement\n- The evaluation, together with the analysis, is convincing.\n- Include the analysis on why and how the baseline fail\n\nThe paper is well-organized, and the method and evaluation are solid.", "weaknesses": "The paper conducts a complete study on the proposed Prune4ReL, and the following weakness is relatively minor.\n\n- Prune4ReL outperforms the baselines by a large margin, but the gap between PruneReL and uniform sampling is small.\n- Some notations are not clear.\n  - Def. 3.1: the $x$ is not in the pixel space. Instead, it's in the embedding space. The author should state the dimension of $x$ at the beginning\n  - in Thm 3.4, it should be $\\mathcal{S} \\subseteq \\tilde{D}$", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nWe sincerely appreciate the reviewers' constructive comments and positive feedback on our manuscript.\n\n`Q1. Uniform sampling is usually the second-best baseline. It performs especially well in CIFAR-10N Random/Worst and Clothing-1M. Can the authors elaborate more on this?`\n\nTo improve the performance of Re-labeling models, sample selection should achieve a balance between easy (clean) and hard (possibly noisy) examples. This is because the easy (clean) examples support the correct relabeling of neighbor hard examples, while the hard examples greatly boost the test accuracy if they are re-labeled correctly. Existing data pruning algorithms that prefer hard examples may perform poorly due to a lack of easy examples that support accurate relabeling, and clean sample selection algorithms that prefer easy examples may also perform poorly due to a lack of hard (informative) examples that aid in test accuracy after relabeling. On the other hand, uniform sampling shows somewhat robust performance by selecting easy and hard examples in a balanced way.\n\nFor CIFAR-10N, as shown in the selection ratio of 0.2 in Table 1, uniform sampling was more effective at a small selection ratio because a proper amount of easy (clean) examples was collected to support accurate relabeling. However, looking at the selection ratio of 0.8, uniform sampling tended to show lower performance than other data pruning baselines since selecting hard examples became more important as there existed already proper amounts of easy examples. For Clothing-1M, we conjecture that uniform sampling performed well because a low selection ratio was used for testing the fine-tuning. Overall, we will add this discussion in the final version.\n\n\n`Q2. The derivation from the reduced neighborhood confidence (Eq. 3) to the empirical reduced neighborhood confidence (Eq.4) is confusing. What motivates using the cosine distance to perform a weighted sum? Is this motivated by importance sampling?`\n\nThe reduced neighborhood confidence (Eq. 3) of each example is calculated as the sum of the confidences in its neighborhood. However, identifying the neighborhood of an example is very expensive and thus practically infeasible. Thus, instead of explicitly finding the neighborhood of each example, the *empirical* reduced neighborhood confidence (Eq. 4) approximates it using the cosine similarity **as the likelihood of belonging to the neighborhood**. We will elaborate on this rationale in the final version.\n\n\n`Q3. WebVision and Clothing-1M are crawled from the web, but Prune4ReL seems to work better in Clothing-1M. Can the authors elaborate on this further?`\n\nWe interpret your question to mean that Prune4Rel achieves higher accuracy at lower selection ratios in Clothing-1M. Following the existing literature[a] for Clothing-1M, we used a ResNet model pretrained on ImageNet, as specified in Section 4.1. Thus, **fine-tuning was tested for Clothing-1M**, and this setting explains why high accuracy was achieved using a small portion of the Clothing-1M training set. Please inform us if we misunderstood your question.\n\n[a] Sheng Liu, Zhihui Zhu, Qing Qu, Chong You: Robust Training under Label Noise by Over-parameterization. ICML 2022: 14153-14172\n\n\n`Q4. kCenter and GraNd are missing in Figure 3b. The authors have to find a better way to visualize this plot (Figure 3b). Try to zoom in a little bit.`\n\nThanks for pointing out this issue. The enhanced plot is included in the pdf file for the global response. Since *kCenter* requires huge computation and memory costs, it is not feasible to run in our environment (refer to Figure 3c). Also, since *Forgetting* requires prediction history during the warm-up training period to calculate the forgetting score of each training example, we could not run it for Clothing-1M where sample selection is performed from the pre-trained model.\n\n\n`Q5. Section 4.5 is like the motivation of the paper. Consider re-ordering them.`\n\nThank you very much for helping us improve our paper. As you propely recognize, utilizing Re-labeling models for data pruning under label noise is much more effective than utilizing standard models. Thus, we will reorder Section 4.5 to Section 4.3 in order to confirm the motivation early on. In addition, we will add a summary of Section 4.5 at the end of Introduction: \"When combined with the pruning methods, the performance of the Re-labeling models significantly surpasses that of the standard models in CIFAR-10N and CIFAR-100N by up to 21.6%.\"\n\n\n`Q6. Some notations are not clear.`\n> In Definition 3.1, the dimensionality of $x$ is set to be 512 for CIFAR-10N and CIFAR-100N and 2048 for WebVision and Clothing-1M. We will include this detail in the final version.\n\n> In Theorem 3.4, we will correct the notation to $\\mathcal{S} \\subseteq \\tilde{\\mathcal{D}}$. Thank you for pointing out the typo."}, {"review_id": "wuCV9CWXHO", "reviewer": "Reviewer_jBWT", "summary": "The paper proposes a novel data pruning algorithm, Prune4ReL, that maximizes the neighborhood confidence of the entire training examples, which is proportional to the likelihood of correct re-labeling. The paper demonstrates the effectiveness of Prune4ReL on four noisy datasets, where it outperforms baselines by a large margin.", "questions": "In addition, the current dataset-pruning experiment mainly focuses on image classification, but this kind of task is too simple to reflect the real needs. For example, for CIFAR or even ImageNet, we don't need dataset-pruning at all, and the cost of training on these datasets is very affordable for almost all scientific teams. I think the real application scenario of dataset-pruning should be the most popular tasks such as large language model (LLM) training and multi-modal training. So, what do you think is the main difficulty of using dataset-pruning for these tasks? How is these tasks different from image classification?\n\nAt present, the performance of dataset-pruning algorithm in image classification tasks is generally not very good, for example, the performance degrades very seriously under high pruning-ratio Settings. Moreover, all existing pruning algorithms cannot outperform the ramdom selection baseline with a significant margin. However, in the field of LLM, as a contrast, some manually filtered datasets [1,2] can achieve a data set size reduction of tens of times, and performance remains unchanged or even significantly improved. So, can we say that manual filtering is still far better than algorithmic automated filtering? Or, what in the world is causing such a big gap.\n\n[1]. Textbooks Are All You Need. Arxiv. [2306.11644] \n[2]. LIMA: Less Is More for Alignment. Arxiv. [2305.11206]", "limitations": "Please refer to Weaknesses.", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The writing of this article is very clear and easy to follow up. Moreover, the methodology in this paper is also reasonable with necessary theoretical analysis. I enjoy this work very much! My only concern about this work is the experimental part.\n\n", "weaknesses": "1. Recent works like [1,2,3] are missing in those selected baselines. \n\n2. Lack of results on ImageNet-1K, which is the most convincing part for us.\n\n[1] Moderate: Moderate coreset: A universal method of data selection for real-world data-efficient deep learning. ICLR-2023 \n\n[2] SSP: “Beyond neural scaling laws: beating power law scaling via data pruning. NeurIPS-2022 \n\n[3] CCS: Coverage-centric Coreset Selection for High Pruning Rates. ICLR-2023", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "`The writing of this article is very clear and easy to follow up. Moreover, the methodology in this paper is also reasonable with necessary theoretical analysis. I enjoy this work very much!`\n> We are very glad to hear that you enjoy reading our paper.\n\n`My only concern about this work is the experimental part.`\n> We did our best to improve the evaluation during the rebuttal period, and we hope that our efforts will address your sole concern.\n\n\n`Q1. Recent works like [a,b,c] are missing in those selected baselines.`\n\nThank you very much for recommending important references. We have additionally conducted the experiments with Moderate[a] and SSP[b], and the results with SOP+ are reported as below. **Prune4Rel is also shown to outperform these recent baselines**, because they are not designed for the **noise-robust** learning scenario. We will add these results (also for other datasets) in the final version.\n\n| Methods        |         | CIFAR-10N | Random   |          |         | CIFAR-10N | Worst    |          |\n| -------------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- |\n|                | 0.2      | 0.4      | 0.6      | 0.8      | 0.2      | 0.4      | 0.6      | 0.8      |\n| Uniform  | 87.5     | 91.5     | 93.4     | 94.8     | 81.9     | 87.5     | 90.8     | 91.8     |\n| SmallL   | 77.6     | 86.2     | 90.7     | 94.3     | 78.8     | 84.1     | 89.3     | 92.3     |\n| Margin   | 52.1     | 79.6     | 92.6     | 95.1     | 45.7     | 61.8     | 84.6     | **92.5** |\n| kCenter  | 86.3     | 92.2     | 94.1     | **95.3** | 81.9     | 88.0     | 91.3     | 92.3     |\n| Forget   | 82.4     | 93.0     | 94.2     | 95.0     | 71.1     | 87.7     | 90.6     | 92.2     |\n| GraNd    | 24.2     | 51.6     | 85.9     | 94.9     | 15.4     | 25.7     | 51.0     | 86.8     |\n| **Moderate** | 88.3     | 92.8     | 94.1     | 94.6     | 75.0     | 81.9     | 87.7     | 91.8     |\n| **SSP** | 80.5     | 91.7     | 93.8     | 95.0     | 70.8     | 86.6     | 89.2     | 92.3     |\n| **Pr4Rel**     | 88.2     | 93.0     | **94.4** | 95.1     | 83.4     | **89.3** | **91.5** | **92.5** |\n| **Pr4Rel$_B$** | **88.6** | **93.1** | 94.2     | **95.3** | **84.2** | 89.1     | 91.3     | **92.5** |\n\nWe were unable to add CCS[c] within a week, but the results for CCS will be included in the final version.\n\n[a] Xiaobo Xia, Jiale Liu, Jun Yu, Xu Shen, Bo Han, Tongliang Liu: Moderate Coreset: A Universal Method of Data Selection for Real-world Data-efficient Deep Learning. ICLR 2023\n\n[b] Ben Sorscher, Robert Geirhos, Shashank Shekhar, Surya Ganguli, Ari Morcos: Beyond neural scaling laws: beating power law scaling via data pruning. NeurIPS 2022\n\n[c] Haizhong Zheng, Rui Liu, Fan Lai, Atul Prakash: Coverage-centric Coreset Selection for High Pruning Rates. ICLR 2023\n\n\n`Q2. Lack of results on ImageNet-1K, which is the most convincing part for us.`\n\nThank you very much for helping us improve our paper. All datasets used for our experiments, CIFAR-10N, CIFAR-100N, WebVision, and Clothing-1M, have **real** label noises. However, for ImageNet-1K, we could not find its variant that contains real label noises. Thus, we have injected synthetic noises into ImageNet-1K. In detail, we flipped the original label (e.g., $classId = 0$) to an incorrect label (e.g., $classId = 1$) randomly by a given noise rate. The results for ImageNet-1K are provided as below and will be included in the final version. Here, the noise rate is set to be 20%, and SOP+ is trained for 50 epochs from scratch with a batch size of 64. Prune4Rel is shown to perform the best also in this dataset, thereby demonstrating its versatility. (More results for high selection ratios will come during the discussion phase.)\n\n| Methods         | ImageNet-1K | 20% Noise |     |\n| --------------- | ------- | -------- | -------- |\n| Selection Ratio | 0.01    | 0.05     | 0.1      |\n| Uniform         | 2.6     | 27.8     | 42.5     |\n| SmallL          | 5.8     | 22.8     | 31.4     |\n| Forget          | 0.8     | 4.1      | 8.3      |\n| **Pr4Rel$_B$**  | **6.0** | **30.2** | **44.3** |\n\n\n`Q3. I think the real application scenario of dataset-pruning should be the most popular tasks such as large language model (LLM) training and multi-modal training. So, what do you think is the main difficulty of using dataset-pruning for these tasks? How is these tasks different from image classification?`\n\nThis is an excellent question. We agree with you that data pruning for multi-modal training and large language model (LLM) training will be more interesting than for image classification. Regarding LLM training, we believe that there are several challenges, compared to image classification. First, various levels---token, sentence, and document---can be considered as a pruning granularity for a large-scale corpus. Second, efficient selection criteria should be developed for LLMs, because most of the metrics typically used for image classification, e.g., gradients, are very expensive to calculate. Obviously, there will be additional challenges to investigate. After the review period concludes, we, the authors and the reviewer, can even attempt to collaborate on this extremely intriguing topic.\n\n\n`Q4. Can we say that manual filtering is still far better than algorithmic automated filtering? Or, what in the world is causing such a big gap?`\n\nAgain, thank you for posing a very interesting research question. In our opinion, the quality, diversity, and redundancy of a given raw dataset are more important in determining the efficacy of data pruning than whether it is performed automatically or manually. (The capacity of a pre-trained model is also relevant given that [d] involves data pruning for fine-tuning.) Clearly, additional research is required to provide an exact answer to this question.\n\n[d] Chunting Zhou et al.: LIMA: Less Is More for Alignment. CoRR abs/2305.11206 (2023)"}, {"review_id": "ctx4eie3pi", "reviewer": "Reviewer_ALmL", "summary": "This paper studies the task of data pruning, specifically in the setting of label noise. The authors propose a method to perform data pruning by maximizes the total neighborhood confidence of the training examples (which is equivalent to maximizing the relabeling accuracy). \n\nThe authors theoretically analyze this particular setting, bounding the error of a model trained on the subset that satisfies the expansion and separation assumptions from prior work. Their resulting bound is inversely proportional to the neighborhood confidence.\n\nTheir empirical results show mixed results in the comparison against existing methods; namely, in Table 1, the results are slightly better than existing baselines on a small number of tasks but predominantly match the performance of existing methods. In table 2, it also seems that the existing method Forget and kCenter seem to select similar or fewer noisy examples than the proposed method (except in the case of CIFAR-100N with 0.2 or 0.4).\n", "questions": "N/A", "limitations": "The authors have adequately addressed the limitations.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The authors present a theorem that shows that the error of a model trained on a subset of data is inversely related to the neighborhood confidence. They propose a method that maximizes the neighborhood confidence, which in turn minimizes this bound.\n\nThe authors show in Figure 3 that the test accuracy with SOP increases when using a subset produced by the proposed method. However, it is unclear why this is necessarily the case, since there are similar or fewer noisy examples selected by the Forget baseline method.\n\nThe authors provide ablation studies that study the effect of neighborhood threshold $\\tau$ and with different confidence metrics.\n", "weaknesses": "The bolding strategies in Table 1 are a bit misleading; in many scenarios, a baseline achieves the same performance as the proposed method (and sometimes achieves a smaller variance), but the proposed method is still listed in bold. In fact, the reported method achieves the same performance across many of the tasks.\n\nSimilarly, the results in Table 2 show that the Forget baseline seems to select subsets with a smaller ratio of noisy examples when compared to the proposed method. However, in subsection 4.3, the authors claim that this method selects a high ratio of noisy examples.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "`Q1. Their empirical results show mixed results in the comparison against existing methods. In Table 1, the results are slightly better than existing baselines on a small number of tasks but predominantly match the performance of existing methods`\n\nThank you very much for your careful review. We acknowledge your concerns but respectfully argue that **our empirical results are promising** in three ways.\n\n> **(1) Prune4Rel *consistently* outperforms in various datasets and selection ratios.** No baseline consistently shows comparable accuracy in Table 1. To illustrate our claim, the average over different selection ratios for each dataset with SOP+ is calculated as follows. \n \n| Methods        | CIFAR-10N Random | CIFAR-10N Worst | CIFAR-100N Noisy |\n| -------------- | -------- | -------- | -------- |\n| Uniform        | 91.8     | 88.0     | 56.9     |\n| SmallL         | 87.2     | 86.1     | 59.6     |\n| Margin         | 79.9     | 71.2     | 42.0     |\n| kCenter        | 92.0     | 88.4     | 56.9     |\n| Forget         | 91.2     | 85.4     | 55.6     |\n| GraNd          | 64.2     | 44.7     | 32.7     |\n| **Pr4Rel**     | 92.7     | 89.2     | 59.5     |\n| **Pr4Rel$_B$** | **92.8** | **89.3** | **60.8** |\n\n> **(2) The improvement becomes more pronounced when the selection ratio is *relatively low* (e.g., 20% in Table 1).** It is relatively hard to show the difference at high selection ratios, because not many examples are pruned. Table 1 shows that slightly better or comparable accuracy tends to appear at high selection ratios.\n\n> **(3) The results on another dataset reaffirm the superiority of Prune4Rel.** The table in *Q2 of the reviewer jBWT* is obtained for ImageNet-1K with synthetic flip noises.\n\nOverall, we hope that the reviewer's concerns on empirical results are resolved by our three supporting arguments. We will enrich Table 1 by adding the averages and new results in the final version.\n\n\n`Q2. In Table 2, it seems that the existing method Forget and kCenter seem to select similar or fewer noisy examples than the proposed method (except in the case of CIFAR-100N with 0.2 or 0.4).`\n\nThe goodness of a selected subset cannot be determined based solely on the proportion of noisy examples; the **quality** (or **self-correctability**) of these noisy examples must also be considered. Noisy examples selected by Prune4Rel are mostly self-correctable because it maximizes the total neighborhood confidence of the training set. In contrast, those selected by existing data pruning methods such as kCenter and Forget are ***not*** guaranteed to be self-correctable. To contrast the proportion of self-correctable examples in kCenter, Forget, and Prune4Rel, we plan to expand Table 2 as follows. Here is the proportion of self-correctable examples among the noisy ones within a selected subset at a selection ratio of 0.2.\n\n| Model | Methods    | CIFAR-10N Random |  |  |\n| ----- | ---------- | -------- | -------- | -------- |\n|       |            | Test Accuracy | % Noisy | % (Self-Correct / Noisy) |\n| SOP+  | kCenter    | 86.3     | 19.0 | 75.2     |\n|       | Forget     | 82.4     | 17.0 | 61.7     |\n|       | **Pr4Rel** | 88.2     | 17.0 | **90.3** |\n\nTherefore, the noisy examples selected by kCenter and Forget may harm the generalizability of a model, whereas those selected by Prune4Rel are rather useful for training. \n\nIn Section 4.3, we meant to say that Prune4Rel selects more high-quality noisy examples aggressively as the subset size increases, based on the increased confidence. We recognize that the current writing is not very clear, and we will revise it accordingly.\n\n\n`Q3. The authors show in Figure 3 that the test accuracy with SOP+ increases when using a subset produced by the proposed method. However, it is unclear why this is necessarily the case, since there are similar or fewer noisy examples selected by the Forget baseline method.`\n\nThis question is answered by the **response to Q2**. The contribution of noisy examples to a model's relabeling capability is low in kCenter and Forget, whereas it is very high in Prune4Rel, despite the fact that the proportion of noisy examples is comparable.\n\n\n`Q4. The bolding strategies in Table 1 are a bit misleading; in many scenarios, a baseline achieves the same performance as the proposed method (and sometimes achieves a smaller variance), but the proposed method is still listed in bold.`\n\nWe apologize for any confusion that our current presentation may have caused. We intended to highlight only our methods, unless they were inferior to any baseline. We will revise the strategy for bolding such that the highest values (including ties) are highlighted. For example, part of Table 1 for SOP+ will be changed to the following.\n\n| Methods        |         | CIFAR-10N | Random   |          |         | CIFAR-10N | Worst    |          |        | CIFAR-100N | Noisy    |          |\n| -------------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- |\n|                | 0.2      | 0.4      | 0.6      | 0.8      | 0.2      | 0.4      | 0.6      | 0.8      | 0.2      | 0.4      | 0.6      | 0.8      |\n| SmallL         | 77.6     | 86.2     | 90.7     | 94.3     | 78.8     | 84.1     | 89.3     | 92.3     | 48.5     | 59.8     | 63.9     | **66.1** |\n| Margin         | 52.1     | 79.6     | 92.6     | 95.1     | 45.7     | 61.8     | 84.6     | **92.5** | 20.0     | 34.4     | 50.4     | 63.3     |\n| kCenter        | 86.3     | 92.2     | 94.1     | **95.3** | 81.9     | 88.0     | 91.3     | 92.3     | 44.8     | 55.9     | 61.6     | 65.2     |\n| **Pr4Rel**     | 88.2     | 93.0     | **94.4** | 95.1     | 83.4     | **89.3** | **91.5** | **92.5** | 49.0     | 59.1 | **64.1** | 65.7 |\n| **Pr4Rel$_B$** | **88.6** | **93.1** | 94.2     | **95.3** | **84.2** | 89.1     | 91.3     | **92.5** | **52.9** | **60.1** | **64.1** | **66.1** |"}, {"review_id": "VplvBmzO3R", "reviewer": "Reviewer_rFfD", "summary": "This paper studies data pruning in noisy label setting. Built on re-labeling models, it proposes Prune4ReL that finds a subset to maximize the re-labeling accuracy. In particular, it introduces neighborhood confidence as the criteria for selection, as well as a greedy algorithm to select the subset. Evaluation show its superiority over prior data pruning methods.", "questions": "See weakness above", "limitations": "The authors clearly stated the limitations in appendix.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The target setting is interesting and well motivated. The proposed neighborhood confidence and Prune4ReL is sound with theoretical guarantee. In addition, the evaluations are comprehensive and experimental results look promising. ", "weaknesses": "I don't see any major weakness, but I do have some comments:\n\n1. The proposed data pruning method does require model training as many sample selection methods for robust learning do; I think these methods should also be considered as baselines and compared, even though they are not specifically designed for data pruning. Currently, the authors only compare SmallLoss, which is quite outdated.\n\n2. There are some related work in robust learning field that also leverage neighborhood information, but the authors did not include and discuss them, eg, \"Learning with Neighbor Consistency for Noisy Labels\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "`Q1. The proposed data pruning method does require model training as many sample selection methods for robust learning do; I think these methods should also be considered as baselines and compared, even though they are not specifically designed for data pruning.` \n\nThank you very much for helping us improve our paper. Many sample selection methods, including the small-loss trick, have been developed for the purpose of removing noisy examples from the training set. However, these methods do not consider the importance of examples in terms of re-labeling. Thus, a new data pruning method should ***not*** completely remove noisy examples but select them if they are expected to be relabeled correctly. We expect that other sample selection methods would also perform worse than ours because they do not try to select noisy examples which could be potentially helpful. According to your suggestion, we will try to add more decent sample selection baselines such as Co-teaching+[a] in the final version.\n\n[a] Xingrui Yu, Bo Han, Jiangchao Yao, Gang Niu, Ivor W. Tsang, Masashi Sugiyama: How does Disagreement Help Generalization against Label Corruption? ICML 2019: 7164-7173\n\n\n`Q2. There are some related work in robust learning field that also leverage neighborhood information, but the authors did not include and discuss them, e.g., \"Learning with Neighbor Consistency for Noisy Labels\"`\n\nThank you for bringing up an important topic for discussion. The method NCR[b] that you mentioned utilizes consistency regularization among neighbors so that examples with similar feature representations produce similar outputs. Consequently, NCR and Prune4Rel share the phiolosophy that neighbor examples are useful in the presence of label noise. Nevertheless, the objectives of the two methods to utilizing the neighborhood are distinct: NCR aims to reduce the impact of incorrect labels, whereas Prune4Rel seeks to determine the contribution of an example to the re-labeling accuracy. The final version will include this discussion.\n\n[b] Ahmet Iscen, Jack Valmadre, Anurag Arnab, Cordelia Schmid: Learning with Neighbor Consistency for Noisy Labels. CVPR 2022: 4662-4671"}]

Author rebuttal:
We deeply appreciate the reviewers' positive feedback and valuable comments. Most reviewers agreed that (1) **the problem setting and methodology are reasonable and novel**, (2) **the theoretical analysis of the methodology is sound**, and (3) **the evaluation was performed extensively**.  Because the reviewer's comments are mostly about the experiments, **we have significantly improved (and are improving) the evaluation section** during the rebuttal period by adding two baselines, one dataset, and one metric.  (See the attached PDF file for an enhanced plot.)  Therefore, we believe that the superiority of Prune4Rel over other baselines has demonstrated much more clearly and hope that the remaining concerns are addressed by the rebuttal.  We are happy to answer additional questions during the discussion period.

Meta-review: In the reviewers' words: this paper has a "interesting and well motivated" goal which is achieved by a "sound", "reasonable", "theoretically-inspired", and "easy to implement" algorithm, with "theoretical guarantees" and "convincing evaluation". "The writing of this article is very clear" with "clear presentation". Given the unanimous recommendation for acceptance from the four reviewers, I recommend acceptance.
Decision: Accept (poster)