Deep k-NN for Noisy Labels
Authors: Dara Bahri
Heinrich Jiang
Maya Gupta
Venue:  (2020)

Abstract: Modern machine learning models are often trained on examples with noisy labels that hurt performance and are hard to identify. In this paper, we provide an empirical study showing that a simple $k$-nearest neighbor-based filtering approach on the logit layer of a preliminary model can  remove mislabeled training data and produce more accurate models than some recently proposed methods. We also provide new statistical guarantees into its efficacy.

Under review as a conference paper at ICLR 2020
DEEP K-NN FOR NOISY LABELS
Anonymous authors Paper under double-blind review
ABSTRACT
Modern machine learning models are often trained on examples with noisy labels that hurt performance and are hard to identify. In this paper, we provide an empir- ical study showing that a simple k-nearest neighbor-based filtering approach on the logit layer of preliminary model can remove mislabeled training data and produce more accurate models than some recently proposed methods. We also provide new statistical guarantees into its efficacy.
INTRODUCTION
Machine learned models can only be good the data they used train With increas- ingly large modern datasets and automated and indirect labels like clicks, it is becoming ever more important to investigate and provide effective techniques handle noisy labels.
We revisit the classical method of filtering out suspicious training examples using k-nearest neigh- bors (k-NN) (Wilson 1972). Like Papernot & McDaniel (2018), we apply k-NN on the learned intermediate representation of preliminary model, which adds robustness. In fact, the k-nearest neighbor approach has recently been receiving attention for its robustness properties (Wang et al. 2018 Reeve & Kaban 2019) and as an auxiliary strategy for modern machine learning (Jiang et al.
2018
The main contributions of this paper are:
Experimentally showing that identifying mislabeled examples by k-NN executed on an in- termediate layer of a preliminary deep model works well compared state-of-art methods for handling noisy labels across noise levels, and is robust to the choice of k.
Theoretically showing that k-NN's predictions will only identify training example as clean its label is the Bayes-optimal label. We also provide finite-sample analysis in terms of the margin and how spread out the corrupted labels are (Theorem TT) rates of convergence for the margin (Theorem 2 and rates under Tsybakov's 's noise condition (Theorem with all rates matching minimax-optimal rates in the noiscless setting.
Our work shows that even though the preliminary neural network is trained with corrupted labels, still yields intermediate representations that are useful for k-nearest neighbor filtering. Given labels which are in high disagreement, one can either automatically remove them and retrain on the remaining, or send to a human operator for further review. This strategy is also be useful in human-in-thee -nho--loo--ooo systems where can warn the human annotator that a label is suspicious, and automatically propose new labels based on its nearest neighbors' labels.
In addition strong empirical performance, deep A-NN filtering has couple of advantages. Firstly, many methods require a clean set of samples whose labels can be trusted. Here we show that the k-NN based method is robust and does not require such a clean set of samples. Second, while k-NN does introduce the hyperparameter k, we will show that deep k-NN filtering is stable to the choice of k: such robustness to hyperparameters highly desirable as optimal tuning for this problem is often not available in practice (i.e. when no clean validation set is available).
2 RELATED WORK
We review relevant prior work in training on noisy labels and related k-NN theory.

---

Under review as a conference paper at ICLR 2020
2.1 TRAINING WITH NOISY LABELS
Methods to handle label noise can be classified into two main strategies: (i) explicitly identify and remove the noisy examples, and (ii) indirectly handle the noise with robust training methods.
Data Cleaning This proposal fits into the broad family of data cleaning methods, in that our pro- posal detects and filters dirty data (see Chu et al. (016) for a recent survey). The use of k-NN to "edit" training data has been popular since Wilson (9722) used it to throw away training examples that were not consistent with their k = 3 nearest neighbors. The idea of using a preliminary model to help identify mislabeled examples dates to least Guyon et al. (1994), who proposed using the model to compute an information gain for each example and then suspecting ones with high gain. Other early work used cross- valiidaiiot set-up to train a classifier on part of the data, then use to make a prediction on held-out training examples, and remove any examples if the prediction dis- agrees with the label; ensembles of models can also be used for the predictions. (Brodley & Freidl 1999).
Noise Corruption Estimation For multi-class problems, a popular approach is to account for noisy labels by applying confusion matrix after the model's softmax layer (Sukhbaatar et al. (2014). Such methods rely on a confusion matrix which is often unknown and must be estimated. Patrini et al. (017)) suggest deriving it from the softmax distribution of the model trained on noisy data while Goldberger & Ben-Reeven| (2016); Jindal et al. (2016); Han et al. (2018) give alternatives. Accurate estimates are generally hard attain when only untrusted data is available. Hendrycks et al. (2018) achieves more accurate estimates in the setting where some amount of known clean, trusted data is available. Xiao et al. (2013); Khetan et al. (2017): Vahdat (2017) use EM-type algorithms to estimate the clean label distribution.
Noise-Robust Training Natarajan et al. (213)) propose method make any surrogate loss func- tion noise-robust given knowledge of the corruption rates. Ghosh et al. (2017) proves that losses like mean absolute error (MAE) are inherently robust under symmetric or uniform label noise while Zhang & Sabuncu 2018) shows that training with MAE results in poor convergence and accuracy. They propose a new loss function based on the negative Box-Cox transformation that trades off the noise-robustness of MAE with the training efficiency of cross-entropy. Lastly, the ramp, unhinged, and savage losses have been proposed and theoretically justified be noise-robust for support vector machines (Brooks] 2011 Van Rooyen et al.) 2015: Masnadi-Shiran & Vasconcelos] 2009). Rolnick et al. (2017) empirically shows that deep learning models are robust to noise when there are enough correctly labeled examples and when the model capacity and training batch size are sufficiently large.
Auxiliary Models Veit et al. (2017) propose learning label cleaning network trusted data by predicting the differences between clean and noisy labels. Li et al. (2017) suggests training on a weighted average between noisy labels and distilled predictions of an auxiliary model trained on trusted data.
Example Weighting Here make a hard decision about whether keep training example, but one can also adapt the weights on training examples based on the confidence their labels. Liu & &Tao (2015) provides an importance-weighing scheme for binary classification. Ren et al. (2018) suggests upweighting examples whose loss gradient is aligned with those of trusted examples at every step training. Jiing et al. (2017) investigates a recurrent network that learns sample weighting scheme to give to the base model.
2.2 k-NEAREST NEIGHBOR THEORY
The theory of k-nearest neighbor classification has a long history, for example: Fix & Hodges Jr [1951]: [ooerr (1968); Stone (1777); Devroye et al. (1994): Chaudhuri & Dasguptal (2014). Much of the prior work focuses on K-NN's statistical consistency properties. However, with the growing interest in adversarial examples and learning with noisy labels, there have recently been analyses of
k-nearest neighbor methods in these settings. WWang et al. (2018) analyze the robusiness of K-NN classification and provide a robust variant of I-NN classification where their notion of robustness is that predictions of nearby points should be similar. Gao al. (2016) provides
analysis of the k-NN classifier under noisy labels and like us. show that K-NN can attain similar rates in the noisy setting as in the noiseless setting. Gao et al. (2016) assumes noise model where labels
2

---

Under review as a conference paper at ICLR 2020
corrupted uniformly at random, while assume an arbitrary corruption pattern and provide results based on a notion of how spread out the corrupted points are. Moreover, we provide sampe bounds borrowing recent advances in k-NN convergence theory in the noiscless setting (Jiang/ 2019) while the guarantees of Gao et al. (2016) are asymptotic. Reeve & Kaban (2019) provide stronger guarantees robust modification of k-NN proposed by Gao al. 62 To the best of our knowledge, we provide the first finite-sample rates of consistency for the classical k-NN method in the noisy setting with very little assumptions on the label noise.
ALGORITHM
We first define the k-nearest neighbor classifier:
Definition (K-NN), Let the k-NN radius of x X be rx(x)) inf(r: [B(x,)) k} where B == {a' E X |x x'I S r and the k-NN set of x E X be N&(x) = B(z,rx(xr) n.
Then for all X. the k-NN classifier function w.r.t. has discriminant function
m)(:=) = [N)
[y: v, 24 E (x))
with prediction (x)))) == arg max, (v)
Our method Algorithm assumes dataset D Dusisy with potentially noisy labels, along with a dataset Detean consisting of clean or trusted labels. Note that we allow Detenn to empty (i.e. instances where no such trusted data is available). We have found that having Datan becomes important when Dasisy has a high corruption rate; otherwise the representations learned by training on D Doois alone often reasonable enough. The procedure begins by training either Daoisy Leteaa Delcan For our experiments, we partition Dekenn into a training set Det and validation set Dev and train models on Dat and muiss D.t and choose the that performs better Dev-
We then filter examples that disagree with the k-NN classifier prediction, where the k-NN is com- puted on the final logit layer of the trained model (i.e. the layer right before softmax).
Algorithm 1 Filtering datapoints via deep k-NN.
Inputs: D Dosisy, Deleun: k
Train model M on either D nosss U D Delean or Delean-
Let / be the activations of D noisy U D clean on the logit layer of M. Diltered == {(x, y) E N: m) (a:) y), where nis is computed w.r.t. N.
Train final model on Dittered U De.
4 THEORETICAL ANALYSIS
For the theoretical analysis, we assume the binary classification problem with the features defined on compact set X RR_ We assume that points are drawn according distribution F as follows: the features come from distribution Pxx on X' and the labels are distributed according to the measurable
conditional probability function 17 : X - [0, 1]. That is, sample (X, Y) is drawn from F as follows: X is drawn according to Px and Y is chosen according to P(Y = 1 = x) = nTx).
The goal will be show that given corrupted examples, the k-NN disagreement method still able to identify the examples whose labels do not match that of the Bayes-optimal label.
We will make a few regularity assumptions for our analysis to hold. The first regularity assumption ensures that the support X' does not become arbitrarily thin anywhere. This is standard non- parametric assumption (e.g. [Sigh et al. (2009); Jiang Jrang (2019).
Assumption (Support Regularity). There exists w and ro > 0 such that Vol(X' n B(x, r)) 2 w. Vol ((, (z, r)) for all I E X and 0 < r < To, where B(z,r) = {x' E X - x'1 rr).
Let px be the density function corresponding to Px- The next assumption ensures that with a sufficiently large sample, will obtain good covering of the input space.
3

---

appropriately and provide rates of Under review as a conference paper at ICLR 2020
Assumption (px bounded from below). Px,0 infzex Px (a) > 0.
Finally, we make smoothness assumption on as done in other analyses of k-NN classification (e.g. (Chaudhuri & Dasgupta (2014); Reeve & Kaban (2019)
Assumption 3 (n Hölder continuous), There exists 0 < < and Co 0 such that (m(())
77(x"] C, - x/10 for all x, X.
We propose notion of how spread out set of points is based on the minimum pairwise distance between the points. This will be a quantity in the finite-sample bounds we will present. Intuitively, the more spread out contaminated set of points is, the less clean samples will be needed to overcome the contamination of that set.
Definition (Minimum pairwise distance).
S2(C) ==
min 2xx'ECa
J
a'1.
Also define the A-interior region of X' where there is at least A margin in the probabilistic label: Definition 3. Let A 220 O. Define X =- for E X n(x) 2 AJ.
We state the result, which says that with high probability uniformly on X'A when A is known, we have that the label disagrees with the k-NN classifier if and only if the label is not the Bayes-optimal prediction. Due space, all of the proofs have been deferred to the Appendix.
Theorem 1 (Fixed A). Let A > O and suppose Assumptions
and 3 hold. There exists constants K1, Ku > depending only on F such that the following holds with probability at least 1- 8. Let ((n] be (uncorrupted) examples drawn from the F and C be set of points with corrupted labels and denote our sample X == [x]]] U C. Suppose ls lies in the following range
1 Ki A log (1/8) logn S S Ku min(S2(C)) (ACCC)AAP100 A/003
then the following holds uniformly over x E X²: the k--N prediction computed w.r.t agrees with the label if and only the label is the Bayes-optimal label n1" (x) 1(n(x) 2 4).
In the last result, we assumed that A was fixed. We next show how we can make a similar guarantee but show that can take A as choose k convergence.
and 3 hold. There exist constants K₁, Kuy K O depending only F such that the following holds with probability at least 1 Let Xin] be n (uncorrupted) examples drawn from F, and C be a set of points with corrupted labels and denote sample X = Xmm) UC. Suppose l lies in the following range
Theorem (Rates of convergence for A). Let 8 > and suppose Assumptions
K: Log (1/5) - < K₂ S2(C)) n.
then the following holds uniformly over x E XA: the k-NN prediction computed w.r.. X agrees with the label if and only the label is the Bayes-optimal label 11" (x) 1[7(x) } where
log(1/6) k
k
a/D
A = K.
n2
Remark 1. Choosing = On (2a in the above result gives us A Ö(n aa (2a+t))) This rate for A is the minimax-optimal rate for k-nearest neighbor classification X given sample of size n (Chaudhuri & Dasgupta 2014) in the uncorrupted setting. Thus, our analysis is tight up logarithmic factors.
We next give results with an additional margin assumption, also known as Tsybakov's 's noise condi- tion (Mammen al. 1999 Tsybakov et al. 2004):
Assumption 4 (Tsybakov Noise Condition). The The following holds for some C3 and 3 and all A 0:
Px(x & x²) <Cg- 3
4

---

Under review as a conference paper at ICLR 2020
Training Samples, S/C0 0.5
Majoritty Vote K-NN Cipssifier, k-10
Clean Samples, For 90% Accuracy
140
Samples
Accuracy
1k Minimum Pairwise Distance (,())
Minimum Poirwise Distance S1())
Left: training samples. We observe that test accuracy improves S2(C) increases (middle) and that fewer clean training samples are needed to achieve an accuracy of 90% (right).
Figure 1:
Theorem (Rates under Tsybakov Noise Condition). Let 8 > O and suppose Assumptions 7 and hold. There exists constants K1, Kus K, K' > 0 depending only on F such that the following holds with probability at least 1 - 5. Let Xin n (uncorrupted) examples drawn from the and C be set of points with corrupted labels and denote our sample X == X(m] UC. Suppose & lies in the following range
K2 Kl (1/5) n Sk Ku S2(C)) m.
and define (x)x)= arg max, (1) Then,
P (()((x) & 1) (z)) SK. K. (v
(vben log + log(1/6)
k
a/D
+
k
17
logn n + (1/(1/8)
a/D
B+1
Rx - R R K'.
k
n7
where Rx= := E>(g((r)) # y) and R == Exlg" (x) + y) denote the risk of the k-NN method and Bayes optimal classifier, respectively.
Remark Choosing (n22a((2)))) in the above gives us a rate of 0(n= for the excess risk. This matches the lower bounds of Auddbbert et al. (2007) up logarithmic factors.
4.1 IMPACT OF MINIMUM PAIRWISE DISTANCE
The minimum pairwise distance across corrupted samples, S²(C),, is a key quantity in the theory presented in the previous section. We now empirically study its significance in a simulated binary classification task in 2 dimensions. Clean samples with label I. are generated by sampling i.i.d from N(L,, T2x2), where Ho (0, -2) and (41 (0, 2). The decision boundary is the line y 0. We take 100 samples uniformly spaced on a square grid centered about (0, 0) and corrupt them by flipping their true label. With this construction, S2(C)) is precisely the grid width, which let vary. The training set is union of 100 clean samples and the 100 corrupted samples. Using 1000 clean samples as test set we study the classification performance of a majority vote k-NN classifier, where k = 10. Results are shown in Figure As expected, we see that as S2(C) decreases, so does test accuracy and we need more clean training samples to compensate.
EXPERIMENTS
We evaluate the effectiveness of algorithm follows. We split each dataset's training set into two parts, Delean and Druiey- We then corrupt the labels of some fraction of examples in Dauisy by applying corruption matrix prescribed by one of the following methods.
Uniform: The label is flipped to any one of the labels (including itself) with equal proba-
bility.
Flip: The label is flipped to any other label with equal probability.
Hard Flip: With probability 1. we flip the label m to (m) where я is some predefined permutation of the labels.
5

---

Under review as a conference paper at ICLR 2020
UCI Phonernes Uniform 5%
UCI Phonermss -55%
UCI Phonemes Hard Flip 5%,
114
124
Forward
21-
Test Error
Test Error
GLC KINN
Full KNNN Classity
00
16
85
16
50
Noise
Noise
Noise
Figure 2: UCI Results. Error plots against amount of noise applied to the labels of Doiisy Delean contains 5% of the data. Each column a different corruption and each row is for different dataset. We that the k-NN method consistently chooses the best datapoints filter leading lower error. More results are in the Appendix.
We compare against the following baselines:
Gold Loss Correction (GLC) (Hendrycks et al. 2018) estimates the corruption matrix by averaging the softmax outputs of the clean examples on a model trained on noisy data.
Distill (Li et al., 2017) assigns each example in the combined dataset "soft" label that is a convex combination of its label and its softmax output from model trained solely on clean data.
Forward (Patrini al. 2017), similar in spirit to GLC, estimates the corruption matrix by training a model on noisy data and using the softmax output for prototype examples for each class. It does require clean dataset like other methods.
Clean. We define this training the clean data only.
Full. We define this as training on the full (clean and noisy) data.
k-NN Classify like "Full" except we use k-NN majority voting on the logits layer for classification test time.
We report test errors and show the average across multiple runs with standard error bands shaded. Errors are computed on uniformly distributed noise rates between 0 and inclusive. For the results shown in the main text, have that Detean is randomly selected and is 5% of the data. In the Appendix, we show results over different sizes of Detean- We implement all methods using the Tensorflow 2.0 Keras API and Scikit-Learn. We use the Adam optimizer with default learning rate 0.001 and a batch size of 128 across all experiments. For the UCI datasets, we set = 50 and set k 500 for all other datasets. We chose k = 50 for the UCI datasets because some of the datasets were of small size. However, we found that the k-NN method's 's performance was quite stable to the choice of which show in Section 5.4 the Appendix.
We describe the permutations used for hard flipping in
5.1 UCI AND MNIST RESULTS
We show the results for one of the UCI datasets in Figure and and Fashion MNIST in Figure 3 Due to space, results for MNIST and the remaining UCI datasets in the Appendix. For UCI, fully-connected neural network with a single hidden layer of dimension 100 with ReLUU activations and train for 100 epochs. For both MNIST datasets, use is two hidden-layer fully-connected neural network where each layer has 256 hidden units with ReLU activations. We train the model for epochs. We see that the k-NN approach attains models with low error rate across noise rates and either outperforms or is competitive with the next best method, GLC.
5.2 CIFAR RESULTS
For CIFAR10/100 we use ResNet-20, which we train from scratch on single NVIDIA P100 GPUs. We train CIFAR10 for 100 epochs and CIFAR100 for 150 epochs. We show results for CIFAR10 in Figure Saureeaaan and results for CIFAR100 in the Appendix. due to space. We see that the k--N method performs competitively. It generally outperforms the uniform and flip noise types but performs

---

Under review as a conference paper at ICLR 2020
Fashion MNIST Uniform- 5%
Fashion MNIST Flip -.5%
Low Fashiqn MNIST Hard Flip 5%%
12-
124
Forward
21-
Test Error
Error
GLC
KIEN
Full
KOIK Clocsity
16
16
Noise
Noise
Noise
Figure 3: Fashion MNIST. Each column is different corruption method. We that the k--N approach performs competitively. More results are in the Appendix.
CIFAR10
Uniform 5%
CIFAR10 Flip
CIFAR10 Hard Flip
Cean
Test Error
Test Error
Riell
GLC
Classity
22
16
Noise Rate
Noise Rate
Noise Rate
Figure 4: CIFARIO. Each column is different corruption method. We see that our k-NN method performs competitively or outperforms the uniform and flip noise types but performs worse for the hard flip noise type. More results are in the Appendix.
worse for the hard flip noise type. is not too surprising that k-NN would be weaker in the presence of hard flip noise (i.e. where labels are mapped based on pre-determined mapping between labels) as the noise is much more structured in that case making it more difficult to be filtered out by majority vote among the neighbors. In other words, unlike the uniform and flip noise types, we are no longer dealing with white label noise in the hard flip noise type.
5.3 SVHN RESULTS
We show the results in Figure We train ResNet-20 from scratch NVIDIA P100 GPUs for 100 epochs. As in the CIFAR experiments, we see that the k-NN method tends to be competitive in the uniform and flip noise types but does slightly worse in the hard flip.
5.4 ROBUSTNESS TO k
this section, we show that our procedure is stable in its hyperparameter The theoretical results suggest that wide range of & can give us statistical consistency guarantees and show that in practice a wide range of l gives us similar results for Algorithm (Figure 6). Such robustness in
SVHN Uniform 5%
SVHN - Flip 5%
SVHN Hard Flip 5%
122
224
139
Forward
Error
Test Error
XXN
66
60
10
06
Noise Rate
Noise Rate
Noise Rate
Figure 5: SVHN. We see that the K-NN method performs competitively on the uniform and flip noise types but performs worse for the hard flip noise type. More results the Appendix.
7

---

Under review as a conference paper at ICLR 2020
10 Dim
Poreet
XY LINET
DCC
XC INCEEIIS
DIZE
IEE
LWN
Ldan
4.3
2.1
210
121
176
179
233
2.52
150
226
140
100
151
185
144
1.44
2.56
11
170
11
1.50
2:58
1354
8.39
0.15
1.1
1.6
046
Sank
3.0
106
2.4
200
4.0
3.10
246
2.66
314
3.25
2.00
285
6+
110
131
100
155
1330
101
140
1.66
2.41
10837
2.31
6.5
0.30
0.11
0.4
8.50
3.41
0.36
3.46
1.0
Fallx V6477
CRAR000
1330
908
6.6
1845
2.4
140
1W9
Table 1: Area under the test error vs noise rate curve. Each row corresponds to a dataset and size of clean dataset Delean pair, where the size is a percentage of the total training set (5%, 10%, 20%). Each column shows the area under the error curve across noise rates for a particular method and noise type (Uniform, Flip, Hard Flip). We see that the k--N method consistently outperforms the other methods for Uniform and Flip and outperforms the other methods on Hard Flip on the smaller datasets.
hyperparameter is highly desirable because optimal tuning is often not available, especially when sufficient clean validation set is available.
UCI Phoneme
Uniifrmm 5%
UCJ Phoneme - Flip 55%
UCI Phoneme Hard Flip 5%,
k-50
k--50
Test Emro
k-300
k-153
I-350
k00
k-:nn
Test
030
Noise Rate
Noise Rate
Noise Rate
Figure 6: Performance across different values of k. Here we show that on a UCI dataset, the performance of Algorithm [ is stable when varying its hyperparameter k. Note that the y-axis has been zoomed in to better see the differences between the curves.
5.5 AREA UNDER ERROR VS NOISE LEVEL CURVE ACROSS DATASETS
In the figures shown so far, may be difficult to compare the curves in some cases so we report an area under the curve metric in T
Conclusions and Open Questions We conclude from our experiments and theory that the k-NN based method (Algorithm [T is relatively safe method to remove problematic training examples before training. While k--N methods can be sensitive to the choice of l when used with small datasets (Garcia et al. 2209), we hypothesize that with today's 's large datasets one can blithely set l to fixed practically medium-sized value (e.g. k 500) as done here and expect reasonable performance. Theoretically we provided some new results for how well k--N can identify clean versus corrupted labels. Open theoretical questions are whether there are alternate notions of how to characterize the difficulty of a particular configuration of corrupted examples and whether we can provide both upper and lower learning bounds under these noise conditions.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Jean-Yves Audibert, Alexandre B Tsybakov, et al. Fast learning rates for plug-in classifiers. The Annals of Statistics, 35(2):608-6333 2007.
Carla Brodley and Mark A. Freidl. Identifying mislabeled training data. Journal Artificial Intel- ligence Research, 1999.
J Paul Brooks. Support vector machines with the ramp loss and the hard margin loss. Operations Research, 59(2):467-479, 2011.
Kamalika Chaudhuri and Sanjoy Dasgupta. Rates of convergence for nearest neighbor classification. In Advances in Neural Information Processing Systems, pp. 3437-3444 3345, 2014.
Xu Chu, Ilhab F. Ilyas, Sanjay Krishnan, and Jiannan Wan. Data cleaning: Overview and emerging challenges. In SIGMOD, 2016.
Thomas M Cover. Rates of convergence for nearest neighbor procedures. In Proceedings of the Hawaii International Conference on Systems Sciences, pp. 413-415, 1968.
Luc Devroye, Laszlo Gyorfi, Adam Krzyzak, Gábor Lugosi, et al. On the strong universal consis- tency of nearest neighbor regression function estimates. The Annals of Statistics, 22(3):1371- 1385, 1994.
Evelyn Fix and Joseph L Hodges Jr. Discriminatory analysis- discrimination: consis- tency properties. Technical report, California Univ Berkeley, 1951.
Wei Gao, Xin-Yi Niu, and Zhi-Hua Zhou, On the consistency of exact and approximate nearest neighbor with noisy data. arXiv preprint arXiv:1607.07520 2016.
E. K. Garcia, S. Feldman, M. R. Gupta, and S. Srivastava. Completely lazy learning. IEEE Trans. on Knowledge and DataEngineering. 2009.
Aritra Ghosh, Himanshu Kumar, and PS Sastry. Robust loss functions under label noise deep neural networks. In Thirty-Firs/ AAAI Conference Artificial Intelligence, 2017.
Jacob Goldberger and Ehud Ben-Reuven. Training deep neural-networks using noise adaptation layer. 2016.
I. Guyon, N. Matic, and V. Vapnik. Discovering informative patterns and data cleaning. In AAAI Workshop on Knowledge Discovery Databases, 1994.
Bo Han, Jiangchao Yao. Gang Niu, Mingyuan Zhou, Ivor Tsang, Ya Zhang, and Masashi Sugiyama. Masking: A new perspective of noisy supervision. In Advances in Neural Information Processing Systems, pp. 5836-5846, 2018.
Dan Hendrycks, Mantas Mazeika, Duncan Wilson, and Kevin Gimpel. Using trusted data to train deep networks labels corrupted by severe noise. In Advances in neural information processing systems, pp. 10456-10465, 2018
H. Jiang, B. Kim, M. Y. Guan, and M. R. Gupta. To trust or not to trust a classifier. Advances in Neural Information Processing Systems (NeurIPS), 2018.
Heinrich Jiang, Non-asymptotic uniform rates of consistency for k-nn regression. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 3999-4006, 2019.
Lu Jiang, Zhengyuan Zhou, Thomas Leung, Li-Jia Li, and Li Fei-Fei. Mentornet: Regularizing very deep neural networks on corrupted labels. arXiv preprint arXiv: 172.0057/, 4, 2017.
Ishan Jindal, Matthew Nokleby, and Xuewen Chen. Learning deep networks from noisy labels with dropout regularization. In 2016 IEEE 16th International Conference Data Mining (ICDM), pp. 967-972. IEEE, 2016.
Ashish Khetan, Zachary Lipton, and Anima Anandkumar. Learning from noisy singly- data. arXiv preprint arXiv: 041200477 2017.

---

Under review as a conference paper at ICLR 2020
Yuncheng Li, Jianchao Yang, Yale Song, Liangliang Cao, Jiebo Luo, and Li-Jia Li. Learning from noisy labels with distillation. In Proceedings of the IEEE International Conference on Computer Vision, pp. 1910-1918, 2017.
Transactions on Pattern Analysis and Machine Intelligence, 38(3):447-405 2015. Tongliang Liu and Dacheng Tao. Classification with noisy labels by importance reweighting, IEEE
Enno Mammen, Alexandre B Tsybakov, et al. Smooth discrimination analysis. The Annals of Statistics, 27(6):1808- 1829, 1999.
Hamed Masnadi-Shirazi and Nuno Vasconcelos. On the design of loss functions for classification: theory, robustness to outliers, and savageboost. In Advances in Neural Information Processing Systems, pp. 1056, 2009.
Nagarajan Natarajan, Inderjit S Dhillon, Pradcep K Ravikumar, and Ambuj Tewari. Learning with noisy labels. In Advances in Neural Information Processing Systems, pp. 1196-1204, 2013.
Nicolas Paperot and Patrick McDaniel. Deep k-nearest neighbors: Towards confident, interpretable and robust deep learning. arXiv preprint arXiv: 04765, 2018.
Giorgio Patrini, Alessandro Rozza, Aditya Krishna Menon, Richard Nock, and Lizhen Qu Making deep neural networks robust to label noise: A loss correction approach. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 1954-1952, 2017.
Henry WJ Reeve and Ata Kaban. Fast rates for kNN classifier robust to unknown asymmetric label noise. arXiv preprini 190600/9966 2019.
Mengye Ren, Wenyuan Zeng, Bin Yang, and Raquel Urtasun. Learning to reweight examples for robust deep learning. arXiv preprint arXiv:/803.0900 2018.
David Rolnick, Andreas Veit, Serge Belongie, and Nir Shavit. Deep learning is robust to massive label noise. arXiv preprint arXiv: 1705. 10694, 2017.
Aarti Singh, Clayton Scott, Robert Nowak, al. Adaptive Hausdorff estimation of density level sets. The Annals of Statistics, 376$B):260-22882 2009.
Charles Stone. Consistent nonparametric regression. The Annals of Statistics, pp. 395-620, 1977.
Sainbayar Sukhbaatar, Joan Bruna, Manohar Paluri, Lubomir Bourdev, and Rob Fergus. Training convolutional networks with noisy labels. arXiv preprint arXiv: 140.2200000 2014.
Alexander B Tsybakov al. Optimal aggregation of classifiers in statistical learning. The Annals of Statistics, 32(1):135-166, 2004.
Arash Vahdat. Toward robustness against label noise in training deep discriminative neural networks. 2017.
In Advances in Neural Information Processing Systems, pp.
Brendan Van Rooyen, Aditya Menon, and Robert C Williamson. Learning with symmetric label noise: The importance of being unhinged. In Advances in Neural Information Processing Systems, pp. (0-18, 2015.
Andreas Veit, Neil Alldrin, Gal Chechik, Ivan Krasin, Abhinav Gupta, and Serge Belongie. Learning from noisy large-scale datasets with minimal supervision. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 839-847, 2017.
Yizhen Wang, Somesh Jha, and Kamalika Chaudhuri. Analyzing the robustness of nearest neighbors to adversarial examples. In International Conference on Machine Learning, pp. 5120-5129, 2018.
D. Wilson. Asymptotic properties of nearest neighbor rules using edited data. JEEE Trans. on Systems, Man and Cybernetics, 1972.
Tong Xiao, Tian Xia, Yi Yang, Chang Huang, and Xiaogang Wang. Learning from massive noisy labeled data for image classification. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2691-2699, 2015.
Zhilu Zhang and Mert Sabuncu. Generalized cross entropy loss for training deep neural networks with noisy labels. In Advances in Neural Information Processing Systems, pp. 5778-8788 2018.
10

---

Under review as a conference paper at ICLR 2020
A PROOFS
A.1
SUPPORTING THEORETICAL RESULTS
The following bounds тı (2) uniformly in X.
Lemma (Lemma of Jiang 2019)).
The following holds with probability at least 8/2. 1f
. (4/0) logn S 5 w Pxp UD TU
)
I/D ).P.
then su Tk(x)) -
(w-vD-n-xx.))
2
where uD is the volume of the unit ball in RRP.
The next result bounds the number of distinct k-NN sets over X.
Lemma 2 (Lemma 3 Jian (2019)) Let M be the number of distinct k-NN sets over X, that is, M = [x)( x E H. Then DDD.".
A.2 MINIMUM N-NN SPREAD
We propose more notion of how spread out set of points is than S2 which will be used in the theoretical analysis. This will allow us to more precisely characterize how difficult a configuration of incorrectly labeled examples will be work with in the k-NN context. For example, if such examples are spread out far apart, then there will be many correctly labeled examples nearby for the k-NN approach identify the incorrectly labeled examples. On the other hand, if the corrupted ex- amples are all close together, then it will be more difficult to identify them without many uncorrected examples that region. To this end, we define the minimum N--N spread:
Definition (minimum A--N spread).
Sc(C) = min T (Ir, C)2 ZEC
where (a C) denotes the distance from to the k-th closest neighbor in C. Note that this definition is consistent with the earlier definition of S2.
A.3 PROOF OF THROREM 1
Proof of Theorem ! Let 7,7, e > 0 be quantities that will be determined later. Suppose that for some x E XA, we have (xr) I and (((+-))ay(C) 2 т. Then, least I + 7 fraction of the points within I's k-nearest neighbors are not in the corrupted set C. Let A == Nx(x)). that is, the k-nearest neighbors of x that are in C. Then it is clear that A₂ is ko-nearest neighbor set of relative to X'C for some ko 2 [[2 + 7) kl. We have that Ag C X' @ where 4 r {o X' infacd |x ar-a I r). Let us consider without loss of generality that
(x)) 2 + A (call this set xA.t). The case X = fir E X TT()) < A} follows by
symmetry. Thus, we have (xx') 1 + A a for all x' An. By Hoeffing's inequality, have
< + A - CaT -c) -) < exp(-22e" kk).
PP
Σ x'EA,
Ax
2
x'
where y(xx)) is the label corresponding sample x. By Lemma D n such ne-nearest neighbor sets across all Ko in X\CC. That is, this is also a bound on the number of distinct A, for E X. Therefore, if we set
2 have that there at most
D log log (DD/8) (1+ 27)
then by union bound, we have that
inf TEXA.1
Σ
u(2')
< + A Cata ca 5
A
x' x'EAr
11

---

Under review as a conference paper at ICLR 2020
and thus, with probability at least 1 8/4, we have that [A_ Er E'' 2(x') 2 1/2 +
CO uniformly over x E x Similarly, with probability at least - 8/4 we have that [A.1 E''EA y S A + C. T + uniformly over XA.
Hence, in order for k-nearest neighbor prediction to predict the Bayes-optimal label on XA, suffices that
{1 + A CaT -c) ))
2 k
ko
2
Since kn 2 (2 + 7) k, we have that the above holds if
1 1-
A 2 T +
2(1 + 27)
We now choose the values of T, T, to upper bound each of the terms on the R.H.S. by 3/3 so that the above holds.
We can bound the last term by A/3 by setting:
3 2A
Y
2 3 2A
Next, taking
3(3 + 24)
k 2
Dogg n + log(4D/6))
2A
have that e < A/3. Now, by Lemma
1 we have that setting
I/D
2k
w Jw.up UD n Px,0
gives us that rx(x) & r for all x E X' with probubility at least - 8/22. It thus suffices to take
D/a
k Ι 2 3
W.UD UD Px,0
Co.
so that C S A/3. Now in order for Sic -g)ik can be accomplished by having the following hold:
& (C) 2 r, it suffices to have S2(C) 2 т. This
S 2 (2(C)) w.OD UD Px.0 n.
Thus, there exists positive constants K₁ and K, depending only on F such that if
K2 1 2 (1/82 log n) s K2, min() A AP/a n,
then the desired conditions hold.
A.4 PROOF OF THEBORM 2
Proof of Theoremp 2 The proof begins the same way as the proof Theorem As before, let
T > 0 be quantities that will be determined later. Like before, we are reduced to showing
1-27 27
A A2C + + 2(1 + 27)
as long as the conditions for Lemma
I and 2 hold and S2(x) 2 and rT(( S J where we choose
D log + log log(4D/8)
3 22
2k
1/D
6
7
(1 + ++) k
3 + 24
W up n. Pxxo
12

---

Under review as a conference paper at ICLR 2020
These conditions hold for some K, and K2 depending on F.. Then reduced to having
2
D logn log(4D/0)
2k
a/D
A
+ Ca
3
(1+ (7+
W. n Px,0
Since 2 0, it suffices to have
2
D nogn +
2k
a/D
2
+ Ca
3
k
w UD n Px.0
The desired form for A clearly follows for some choice of K depending only on D, w, px.0. C.. all of which depend only on F.
Finally, we must ensure that [(2 - 2 2 so that S(c_-))- (C) 2 S2(2). Given the expression
for 7, it is equivalent to have [(
24
k. 2 2. It suffices show that k 3(342A)
Given the
3+24
24
form of A in terms of n and k, we see that it suffices to have that
((V log + log(1/5)
2/D
9 K.
A:
k
+
k
12
which holds when 2 Ko (2x+))) for some Ko depending only on F, as desired.
A.5 PROOF OF THEOREM 3
The first part follows from Theorem 2 For the second part, we have by Theo- then the k-NN classifier and the Bayes-optimal classifier match with proba- bility 1 uniformly. Thus, have
Proof of Theorem
rem 2 that if æ E X
Rx R S Px x (E>(g((v) + g/a & x Exlg (z) + y/u g 1)
s Cp A (E>(gu(x) # y/æ & x Eylg (x) * u|o & x²)) S Cg A 24.
The result follows immediately from Theorem
B HARD FLIIP PERMUTATIONS
For Fashion MNIST we hard flip by swapping the following classes: TSHIRT <> SHIRT, TROUSER + DRESS, PULLOVER COAT, SANDAL ++ BAG, SNEAKER <> ANKLEBOOT. For CI-
FARI0 we swap the pairs: TRUCK ++ AUTOMOBILE, BIRD ++ AIRPLANE, DEER ++ HORSE, CAT <+ DOG, FROG SHIP. For CIFAR100, hard flip circularly (i.e. +(i) (i+1) mod K)
within each of the 20 superclasses. For all other datasets, we hard flip circularly.
C ADDITIONAL PLOTS
We provide the plots that were ommitted from the main text due to space constraints.
13

---

Under review as a conference paper at ICLR 2020
UCI Phonemes Uniform, 10%.
Phonemes Flip 10%
Phonemes Hard Flip 10%
Test Error
Test Test Error
Test Test Error
65g
Noise Rate
Noise Rate
Noise Rate
UCI Phonemes Uniform, 20%
Phonemes Flipp 20%
UCI Phonemes Hard Flip 20%
Error
Test Error
Test Error
06
Noise Rate
Noise Rate
Noise Rate
Figure 7: Plots for UCI Phonemes dataset at 10, 20% clean data and all corruption types.
UCI Letters Uniform 5%
UCI Letters Flip 5%
UCI Letters Hard Flip 5%
119
1E4
104
Error
Error
20
600
64
90
44
Noise Rate
Noise Rate
Noise Rate
UCI Letters Uniform 10%
UCI Letters Flip 10%
UCI Letters, Hard Flip 10%
110
1ea
Error
Error
620
44
Noise Rate
Noise Rate
Noise Rate
UCI Letters Uniform 20%
UCI Letters Flip 20%
UCI Letters, Hard Hlip 20%
Test Error
Test Error
Test
10
66
10
60
8
Noise Rate
Noise Rate
Noise Rate
Figure 8: Plots for UCI Letters dataset 5, 10, 20% clean data and all corruption types.
14

---

Under review as a conference paper at ICLR 2020
UCI Wilt Uniform 5%
UCI Wiit Flip 5%
UCI Wilt Hard Flip 5%
122
124
104
41-
Error
62-
Test Error
c9-
12.0
Noise Rate
Noise Rate
Noise Rate
UCI Wilt Uniform 10%
UCI Wijt Flip 10%
UCI Wilt Hard Flip 10%
Test Error
Test Test Error
6--
Test Test Error
42.5
14.3
Noise Rate
Noise Rate
Noise Rate
Unifom 20%
UCI Wilt Flip 20%
UCI Wilt Hard Flip 20%
Test Error
Error
Test Error
Noise Rate
Noise Rate
Noise Rate
Figure 9: Plots for UCI Wilt dataset at 5, 10, 20% clean data and all corruption types.
UCI Parkinsons Uniform 5%
UCI, Parkinsons, Flip 55%
UCI Parkinsons Hard Flip 5%
122
Test Error
Error
14%
Noise Rate
Noise Rate
Noise Rate
UCI Parkinsons Uniform, 10%
UCI Parkinsons Flip 10%
UCI Parkinsons Hard Flip 10%
Test Error
Test Error
Test Error
10
64
Noise Rate
Noise Rate
Noise Rate
JUII Parkinsons Upiform, 20%
UCI Parkinsons Flip 20%
UCI Parkinsons
Hard Flip 20%
Emror
Test Error
Error
Noise Rate
Noise Rate
Noise Rate
Figure 10: Plots for UCI Parkinsons dataset at 5, 10, 20% clean data and all corruption types.
15

---

Under review as a conference paper at ICLR 2020
UCI Seeds Uniform .5%
UCI Seeds Flip 5%
UCI Seeds, Hard Flip 5%
129
124
104
41-
Test Error
Error
55
50%
Noise Rate
Noise Rate
Noise Rate
UCI Seeds Unifprm 10%
UCI Seeds Flip 10%
UCI Seeds, Hard Filp -00%
Test Error
Test Test Error
Test Error
14
10%
Noise Rate
Noise Rate
Noise Rate
Seeds Unifprm 20%
UCI Seeds Hlip 20%
UCI Seeds, Hard Flip -00%
Error
Test Error
Error
Noise Rate
Noise Rate
Noise Rate
Figure 11: Plots for UCI Seeds dataset at 5, 10, 20% clean data and all corruption types.
UCI Iris: Uniform 5%6
UCI Iris
Flip 5%,
UCI Iris
Hard Flip 5%
112
104
Test Error
Error
6
Noise Rate
Noise Rate
Noise Rate
UCI Iris Uniform 10%
UCI Iris Flip 10%
UCI Iris Hard Flip 10%
Test Error
Test Error
Test
10
64-2
Noise Rate
Noise Rate
Noise Rate
UCI Uniform 20%
UCI Iris Flip 20%
UCI Iris Hard Flip 20%
Emror
Test Error
Error
Noise Rate
Noise Rate
Noise Rate
Figure 12: Plots for UCI Iris dataset at 5, 10, 20% clean data and all corruption types.
16

---

Under review as a conference paper at ICLR 2020
MNIST Uniform
MNIST Flip- 5%
MNIST Hard Flip- 55%
Test Test Error
Test Error
Noise Rate
Noise Rate
Noise Rate
MNIST Uniform 10%
MNIST Flip. 10%.
MNIST Hard Flip 10%
Error
Test Error
Error
00
00
Noise Rate
Noise Rate
Noise Rate
MNIST Uniform 20%
MNIST Flip, 20%
MNIST Hard Flip 20%
122
30.
104
Error
Error
6
Noise Rate
Noise Rate
Noise Rate
Figure 13: Plots for MNIST at 5, 10, 20% clean data and all corruption types.
1.. Fashion MNIST - Upiform, 10%,
Fashion MNIST FFlip 10%
sa Fashion MNIŞT Hard Flip 10%
1Ea
Error
Error
64
Noise Rate
Noise Rate
Noise Rate
Fashion MNIST Uniform, 20%
Fashion MNIST Flip 20%
Fashion MNIST Hard Flip 20%
Test Error
Test Error
Test
10
66g
10
60
10
Noise Rate
Noise Rate
Noise Rate
Figure 14: Plots for Fashion MNIST 10, 20% clean data and all corruption types.
17

---

Under review as a conference paper at ICLR 2020
CIFAR10 Uniform 10%
CIFAR10 Flip 10%
CIFARIO Hard Flip 10%
Test Error
Test Test Error
Test Test Error
65g
Noise Rate
Noise Rate
Noise Rate
CIFAR10 Uniterm 20%
CIFAR10 Flip 20%
CIFARIO Hard Flip 20%
Error
Test Error
Test Error
000
00
90
Noise Rate
Noise Rate
Noise Rate
Figure 15: Plots for CIFAR1O at 10, 20% clean data and all corruption types.
CIFAR100 Unitorm 5%
CIFAR100 Flip 5%
CIFAR100, Hard Flip-55%
114
144
1044
Error
Error
60
04
16
00
44
Noise Rate
Noise Rate
Noise Rate
CIFAR100 Uniform 10%
CIFAR10D Flip 10%
CIFAR100 Hard Flip 10%
12.2
162
16.
Test Error
Test Error
125
64
10
60
Noise Rate
Noise Rate
Noise Rate
CIFAR100 Uniform 20%
CIFAR100 Flip 20%
CIFAR100 Hard Flip 20%
Test Error
Test Error
Test
10
66g
60
6
Noise Rate
Noise Rate
Noise Rate
Figure 16: Plots for CIFAR100 5, 10, 20% clean data and all corruption types.
18

---

Under review as a conference paper at ICLR 2020
SVHN Uniformm 10%
SVHN Flip 10%
SYHN Hard Flip 10%
Enor
Error
Test Error
CA-
00
65
00
00
Noise Rate
Noise Rate
Noise Rate
SVHN Uniform 20%
SVHN Flip. 20%
SYHN Hard Flip 20%
122
104
104
Error
Error
16
00
84
Noise Rate
Noise Rate
Noise Rate
Figure 17: Plots for SVHN at 10, 20% clean data and all corruption types.
19


Reviews:
[{"review_id": "rkxFL70AYH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a k-NN method for identifying corrupted labels, and then applies this k-NN in the representation space of a deep neural net rather than the original feature space. Overall the paper is well written and the results look quite convincing\n\nThe theory appears to be important (if somewhat straightforward-looking) contributions of existing k-NN theory to the corrupted labels setting, based on the key quantity the authors defined as S_k, the minimum k-NN spread.\n\nSince the theory highly depends on this quantity, the authors should after Definition 2 justify why they chose to base their results around S_k, and why intuitively it is the right quantity.\n\n- I encourage another experiment where the label corruption is not completely at random, that is it depends on the values of x itself.  \n\n- In particular I encourage a synthetic experiment where the authors look at corruptions with varying S_k (minimum k-NN spread) values, to empirically verify the their theory holds and this really is a meaningful quantity to consider in the label-corruption setting.\n\n- Why don't the authors show the results for vanilla deep kNN trained on the full (noisy + clean) dataset in their experiments. This seems important to ascertain the benefits that might be attributed to simply switching to kNN.  Or is deep kNN generally worse that the original model trained on the full dataset?\n\n- Why didn't the authors show the original model trained on the full dataset?\nIs it because it always does worse than all the baselines considered in the paper?\nI would expect it sometimes does much better than Control (eg. when noise rates are low), and this is the straightforward approach must practitioners would use.\n\n- Why don't the authors present the accuracy of the k-NN method at identifying corrupted datapoints vs the other methods that aim to explicitly identify the corrupted datapoints?\nIn general, it seems the authors did not compare other filtering baselines, which would be more related to their method, for example:\n\nLearning with Confident Examples: Rank Pruning for Robust Classification with Noisy Labels\nNorthcutt et al. (2017). https://arxiv.org/abs/1705.01936\n\n\n- It would be valuable to the scientific community if the authors can comment on: \nRolnick et al. (2018). Deep Learning is Robust to Massive Label Noise. https://arxiv.org/pdf/1705.10694.pdf  \n\n- Some similar looking ideas have been proposed in: \n\nGao et al. (2018). On the Resistance of Nearest Neighbor To Random Noisy Labels\nhttps://pdfs.semanticscholar.org/4227/918020c15b719c415e93eb63d436583f1745.pdf\n\nParvin et al. (2010). A Modification on K-Nearest Neighbor Classifier.\nhttps://globaljournals.org/GJCST_Volume10/7-A-Modification-on-K-Nearest-Neighbor-Classifier.pdf\n\nso the authors should contrast their method/analysis against those papers.\n\n\n- In Thm 1: \"w.r.t. X\" should be \"w.r.t. x\" (lower case)\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "S1lnl2tCKB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose to apply k-NN on the intermediate representations of neural networks for data cleaning. They prove some theoretical properties of k-NN and demonstrate that the proposed data cleaning approach is effective for some tasks.\n\nIt is recommended to reject the paper, with the following concerns in mind.\n\n(1) The proposed approach is not deeply studied. For instance, what's the difference of applying k-NN on raw features, the earlier representations, the later representations, or even \"all\" representations? What's the effect of similarity/distance functions on the k-NN? Without the deeper study, Section 3 is at best a naive use of k-NN for data cleaning, and it is not clear whether the contribution is substantial.\n\n(2) The theoretical analysis does not seem related to applying k-NN to *deep learning* intermediate features. It seems more related to applying k-NN in general. If so, it is also not clear how the theoretical analysis advances current knowledge about k-NN. Are the results original or known? What are the best theoretical results in the literature to compare with?\n\nI thank the authors for answering about the originality. I agree that the original theoretical results is an important contribution on its own, but putting it in the context of deep learning is arguably not the best angle to present the contribution.\n\n(3) It is not clear whether the experiments are compared with respect to state-of-the-art (or at least it is hard to see from Section 2). It seems that rather straightforward baselines are being compared.\n\nI thank the authors for clarifying this.\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Bye4OdB4KS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper provided \"an empirical study showing that a simple k-nearest neighbor-based filtering approach on the logit layer of a preliminary model can remove mislabeled training data and produce more accurate models than some recently proposed methods\". Even though it has many theoretical analysis and experiments, the paper itself is poorly written. There is no intuitive discussion on what is missing in existing methods, why the proposed method can be better, and when the proposed method may also fail.\n\nNote that an important related work is missing, namely \"Robust Inference via Generative Classifiers for Handling Noisy Labels\" from ICML 2019 (see https://arxiv.org/abs/1901.11300). The idea of that paper is also making use of the learned representations of ANY discriminative neural classifier, where the geometric information of the hidden feature spaces can help to distinguish correctly and incorrectly labeled training data. That paper was a 20-min long oral presentation at Hall A (i.e., one of the most crowded sessions), and the authors should really compare with it both conceptually and experimentally.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposed and analyze a k-NN method for identifying corrupted labels for training deep neural networks.

Although a reviewer pointed out that the noisy k-NN contribution is interesting, I think the paper can be much improved further due to the followings:

(a) Lack of state-of-the-art baselines to compare.
(b) Lack of important recent related work, i.e., "Robust Inference via Generative Classifiers for Handling Noisy Labels" from ICML 2019 (see https://arxiv.org/abs/1901.11300). The paper also runs a clustering-like algorithm for handling noisy labels, and the authors should compare and discuss why the proposed method is superior.
(c) Poor write-up, e.g., address what is missing in existing methods from many different perspectives as this is a quite well-studied popular problem.

Hence, I recommend rejection.
Decision: Reject