Title: DEEP K-NN FOR NOISY LABELS

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.

1. INTRODUCTION:

Machine learned models can only be as good as the data they were used to train on. With increasingly large modern datasets and automated and indirect labels like clicks, it is becoming ever more important to investigate and provide effective techniques to handle noisy labels.

We revisit the classical method of filtering out suspicious training examples using k-nearest neighbors (k-NN) (Wilson, 1972) . Like Papernot & McDaniel (2018) , we apply k-NN on the learned intermediate representation of a 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 intermediate layer of a preliminary deep model works well compared to 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 a training example as clean if 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 1), rates of convergence for the margin (Theorem 2) and rates under Tsybakov's noise condition (Theorem 3) with all rates matching minimax-optimal rates in the noiseless setting.

Our work shows that even though the preliminary neural network is trained with corrupted labels, it 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-the-loop systems where one can warn the human annotator that a label is suspicious, and automatically propose new labels based on its nearest neighbors' labels.

In addition to strong empirical performance, deep k-NN filtering has a 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 is 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.

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 proposal detects and filters dirty data (see Chu et al. (2016) for a recent survey). The use of k-NN to "edit" training data has been popular since Wilson (1972) 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 at 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 a cross-validation set-up to train a classifier on part of the data, then use it to make a prediction on held-out training examples, and remove any examples if the prediction disagrees 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 a 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. Natarajan et al. (2013) propose a method to make any surrogate loss function 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 to be noise-robust for support vector machines (Brooks, 2011; Van Rooyen et al., 2015; Masnadi-Shirazi & 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.

Noise-Robust Training:

Auxiliary Models Veit et al. (2017) propose learning a label cleaning network on 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 we make a hard decision about whether to keep a training example, but one can also adapt the weights on training examples based on the confidence in their labels. Liu & Tao (2015) provides an importance-weighting scheme for binary classification. Ren et al. (2018) suggests upweighting examples whose loss gradient is aligned with those of trusted examples at every step in training. Jiang et al. (2017) investigates a recurrent network that learns a 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); Cover (1968); Stone (1977) ; Devroye et al. (1994) ; Chaudhuri & Dasgupta (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. Wang et al. (2018) analyze the robustness of k-NN classification and provide a robust variant of 1-NN classification where their notion of robustness is that predictions of nearby points should be similar. Gao et al. (2016) provides an 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 a noise model where labels are corrupted uniformly at random, while we assume an arbitrary corruption pattern and provide results based on a notion of how spread out the corrupted points are. Moreover, we provide finite-sample bounds borrowing recent advances in k-NN convergence theory in the noiseless setting (Jiang, 2019) while the guarantees of Gao et al. (2016) are asymptotic. Reeve & Kaban (2019) provide stronger guarantees on a robust modification of k-NN proposed by Gao et al. (2016) . 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.

3. ALGORITHM:

We first define the k-nearest neighbor classifier:

Definition 1 (k-NN). Let the k-NN radius of x ∈ X be r k (x) := inf{r : |B(x, r) ∩ X| ≥ k} where B(x, r) := {x ∈ X : |x -x | ≤ r} and the k-NN set of x ∈ X be N k (x) := B(x, r k (x)) ∩ X.

Then for all x ∈ X , the k-NN classifier function w.r.t. X has discriminant function

η k (y; x) := 1 |N k (x)| n i=1 1 [y i = y, x i ∈ N k (x)] ,

with prediction η k (x) := arg max y η k (y; x).

Our method Algorithm 1 assumes a dataset D noisy with potentially noisy labels, along with a dataset D clean consisting of clean or trusted labels. Note that we allow D clean to be empty (i.e. in instances where no such trusted data is available). We have found that having D clean becomes important when 

4. THEORETICAL ANALYSIS:

For the theoretical analysis, we assume the binary classification problem with the features defined on compact set X ⊆ R D . We assume that points are drawn according to distribution F as follows: the features come from distribution P X on X and the labels are distributed according to the measurable conditional probability function η :

X → [0, 1]. That is, a sample (X, Y ) is drawn from F as follows: X is drawn according to P X and Y is chosen according to P(Y = 1|X = x) = η(x).

The goal will be to show that given corrupted examples, the k-NN disagreement method is 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 a standard nonparametric assumption (e.g. Singh et al. (2009) ; Jiang (2019) ).

Assumption 1 (Support Regularity). There exists ω > 0 and r 0 > 0 such that Vol(X ∩ B(x, r)) ≥ ω • Vol(B(x, r)) for all x ∈ X and 0 < r < r 0 , where B(x, r)

:= {x ∈ X : |x -x | ≤ r}.

Let p X be the density function corresponding to P X . The next assumption ensures that with a sufficiently large sample, we will obtain a good covering of the input space.

Assumption 2 (p X bounded from below). p X,0 := inf x∈X p X (x) > 0.

Finally, we make a smoothness assumption on η, as done in other analyses of k-NN classification (e.g. Chaudhuri & Dasgupta (2014) ; Reeve & Kaban ( 2019)) Assumption 3 (η Hölder continuous). There exists 0 < α ≤ 1 and

C α > 0 such that |η(x) - η(x )| ≤ C α |x -x | α for all x, x ∈ X .

We propose a notion of how spread out a 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 a contaminated set of points is, the less clean samples we will be needed to overcome the contamination of that set. Definition 2 (Minimum pairwise distance).

S 2 (C) := min x,x ∈C,x =x |x -x |.

Also define the ∆-interior region of X where there is at least ∆ margin in the probabilistic label:

Definition 3. Let ∆ ≥ 0. Define X ∆ := {x ∈ X : 1 2 -η(x) ≥ ∆}.

We now state the result, which says that with high probability uniformly on X ∆ when ∆ > 0 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 to space, all of the proofs have been deferred to the Appendix.

Theorem 1 (Fixed ∆). Let ∆, δ > 0 and suppose Assumptions 1, 2, and 3 hold. There exists constants K l , K u > 0 depending only on F such that the following holds with probability at least 1 -δ. Let X [n] be n (uncorrupted) examples drawn from the F and C be a set of points with corrupted labels and denote our sample X := X [n] ∪ C. Suppose k lies in the following range

K l • 1 ∆ 2 • log 2 (1/δ) • log n ≤ k ≤ K u • min{S 2 (C) D , ∆ D/α } • n,

then the following holds uniformly over x ∈ X ∆ : the k-NN prediction computed w.r.t. X agrees with the label if and only if the label is the Bayes-optimal label η * (x

) := 1[η(x) ≥ 1 2 ].

In the last result, we assumed that ∆ was fixed. We next show how we can make a similar guarantee but show that we can take ∆ → 0 as we choose k, n → ∞ appropriately and provide rates of convergence.

Theorem 2 (Rates of convergence for ∆). Let δ > 0 and suppose Assumptions 1, 2, and 3 hold. There exist constants K l , K u , K > 0 depending only on F such that the following holds with probability at least 1 -δ. Let X [n] be n (uncorrupted) examples drawn from F, and C be a set of points with corrupted labels and denote our sample X := X [n] ∪ C. Suppose k lies in the following range

K l • log 2 (1/δ) • n α α+D ≤ k ≤ K u • S 2 (C) D • n,

then the following holds uniformly over x ∈ X ∆ : the k-NN prediction computed w.r.t. X agrees with the label if and only if the label is the Bayes-optimal label η * (x 2α+D) ). This rate for ∆ is the minimax-optimal rate for k-nearest neighbor classification on X ∆ given a sample of size n (Chaudhuri & Dasgupta, 2014) in the uncorrupted setting. Thus, our analysis is tight up to logarithmic factors.

) := 1[η(x) ≥ 1 2 ] where ∆ = K • log n + log(1/δ) k + k n α/D . Remark 1. Choosing k = O(n 2α/(2α+D) ) in the above result gives us ∆ = O(n -α/(

We next give results with an additional margin assumption, also known as Tsybakov's noise condition (Mammen et al., 1999; Tsybakov et al., 2004) : Assumption 4 (Tsybakov Noise Condition). The following holds for some C β and β and all ∆ > 0: 

P X (x ∈ X ∆ ) ≤ C β • ∆ β .

K l • log 2 (1/δ) • n α α+D ≤ k ≤ K u • S 2 (C) D

• n, and define η k (x) := arg max y η k (y; x). Then,

P (η k (x) = η * (x)) ≤ K • log n + log(1/δ) k + k n α/D β , R X -R * ≤ K • log n + log(1/δ) k + k n α/D β+1

where R X := E F [g k (x) = y] and R * := E F [g * (x) = y] denote the risk of the k-NN method and Bayes optimal classifier, respectively.

Remark 2. Choosing k = O(n 2α/(2α+D) ) in the above gives us a rate of O(n -α(β+1)/(2α+D) ) for the excess risk. This matches the lower bounds of Audibert et al. (2007) up to logarithmic factors.

4.1. IMPACT OF MINIMUM PAIRWISE DISTANCE:

The minimum pairwise distance across corrupted samples, S 2 (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 L are generated by sampling i.i.d from N (µ L , I 2×2 ), where µ 0 = (0, -2) and µ 1 = (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, S 2 (C) is precisely the grid width, which we let vary.

The training set is a union of 100 clean samples and the 100 corrupted samples. Using 1000 clean samples as a test set we study the classification performance of a majority vote k-NN classifier,

where k = 10. Results are shown in Figure 1 . As expected, we see that as S 2 (C) decreases, so does test accuracy and we need more clean training samples to compensate.

5. EXPERIMENTS:

We evaluate the effectiveness of our algorithm as follows. We split each dataset's training set into two parts, D clean and D noisy . We then corrupt the labels of some fraction of examples in D noisy by applying a corruption matrix prescribed by one of the following methods.

• Uniform: The label is flipped to any one of the labels (including itself) with equal probability. • Flip: The label is flipped to any other label with equal probability.

• Hard Flip: With probability 1 2 , we flip the label m to π(m) where π is some predefined permutation of the labels. We see that the k-NN method consistently chooses the best datapoints to filter leading to 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 a "soft" label that is a convex combination of its label and its softmax output from a model trained solely on clean data. • Forward (Patrini et 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 not require a clean dataset like other methods. • Clean. We define this as training on the clean data only.

• Full. We define this as training on the full (clean and noisy) data.

• k-NN Classify is like "Full" except we use k-NN majority voting on the logits layer for classification at test time.

We report test errors and show the average across multiple runs with standard error bands shaded.

Errors are computed on 11 uniformly distributed noise rates between 0 and 1 inclusive. For the results shown in the main text, we have that D clean is randomly selected and is 5% of the data. In the Appendix, we show results over different sizes of D clean . 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 k = 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 performance was quite stable to the choice of k, which we show in Section 5.4. We describe the permutations used for hard flipping in the Appendix.

5.1. UCI AND MNIST RESULTS:

We show the results for one of the UCI datasets in Figure 2 and Fashion MNIST in Figure 3 . Due to space, results for MNIST and the remaining UCI datasets are in the Appendix. For UCI, we use a fully-connected neural network with a single hidden layer of dimension 100 with ReLU activations and train for 100 epochs. For both MNIST datasets, we use is a two hidden-layer fully-connected neural network where each layer has 256 hidden units with ReLU activations. We train the model for 20 epochs. We see that the k-NN approach attains models with a 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 4 and results for CIFAR100 in the Appendix, due to space. We see that the k-NN method performs competitively. It generally outperforms on the uniform and flip noise types but performs worse for the hard flip noise type. It 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 a 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 5 . We train ResNet-20 from scratch on 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:

In this section, we show that our procedure is stable in its hyperparameter k. The theoretical results suggest that a wide range of k can give us statistical consistency guarantees and we show that in practice a wide range of k gives us similar results for Algorithm 1 (Figure 6 ). Such robustness in 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 in the Appendix.

Under review as a conference paper at ICLR 2020 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-NN 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 no sufficient clean validation set is available. Here we show that on a UCI dataset, the performance of Algorithm 1 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, it may be difficult to compare the curves in some cases so we report an area under the curve metric in Table 1 .

Conclusions and Open Questions We conclude from our experiments and theory that the k-NN based method (Algorithm 1) is a relatively safe method to remove problematic training examples before training. While k-NN methods can be sensitive to the choice of k when used with small datasets (Garcia et al., 2009) , we hypothesize that with today's large datasets one can blithely set k to a 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-NN 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.

A PROOFS:

A.1 SUPPORTING THEORETICAL RESULTS

The following bounds r k (x) uniformly in x ∈ X . Lemma 1 (Lemma 2 of Jiang ( 2019)). The following holds with probability at least 1 -δ/2. If

2 8 • D log 2 (4/δ) • log n ≤ k ≤ 1 2 • ω • p X,0 • v D • r D 0 • n, then sup x∈X r k (x) ≤ 2k ω•v D •n•p X,0 1/D

, where v D is the volume of the unit ball in R D .

The next result bounds the number of distinct k-NN sets over X . Lemma 2 (Lemma 3 of Jiang (2019) ). Let M be the number of distinct k-NN sets over X , that is,

M := |{N k (x) : x ∈ X }|. Then M ≤ D • n D . A.2 MINIMUM k-NN SPREAD

We propose a more notion of how spread out a set of points is than S 2 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 to 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 to identify the incorrectly labeled examples. On the other hand, if the corrupted examples are all close together, then it will be more difficult to identify them without many uncorrected examples in that region. To this end, we define the minimum k-NN spread: Definition 4 (minimum k-NN spread). Note that this definition is consistent with the earlier definition of S 2 .

A.3 PROOF OF THEOREM 1:

Proof of Theorem 1. Let τ, γ, > 0 be quantities that will be determined later. Suppose that for some x ∈ X ∆ , we have r k (x) ≤ τ and S ( 1 2 -γ)•k (C) ≥ τ . Then, at least 1 2 + γ fraction of the points within x's k-nearest neighbors are not in the corrupted set C. Let A x := N k (x)\C, that is, the k-nearest neighbors of x that are not in C. Then it is clear that A x is a k 0 -nearest neighbor set of x relative to X\C for some k 0 ≥ ( 1 2 + γ) • k . We have that A x ⊆ X ∆ ⊕ τ where A ⊕ r := {x ∈ X : inf a∈A |x -a| ≤ r}. Let us consider without loss of generality that η(x) ≥ 1 2 + ∆ (call this set X ∆,+ ). The case X ∆,-:= {x ∈ X ∆ : η(x) ≤ 1 2 -∆} follows by symmetry. Thus, we have η(x ) ≥ 1 2 + ∆ -C α τ α for all x ∈ A x . By Hoeffing's inequality, we have

P 1 |A x | x ∈Ax y(x ) < 1 2 + ∆ -C α τ α - ≤ exp(-2 2 • k 0 ),

where y(x) is the label corresponding to sample x. By Lemma 2, we have that there are at most D • n D such k 0 -nearest neighbor sets across all k 0 in X\C. That is, this is also a bound on the number of distinct A x for x ∈ X . Therefore, if we set

= D log n + log(4D/δ) (1 + 2γ) • k ,

then by union bound, we have that

P inf x∈X ∆,+ 1 |A x | x ∈Ax y(x ) < 1 2 + ∆ -C α τ α - ≤ δ 4 .

and thus, with probability at least 1 -δ/4, we have that 1 |Ax| x ∈Ax y(x ) ≥ 1 2 + ∆ -C α τ αuniformly over x ∈ X ∆,+ . Similarly, with probability at least 1 -δ/4 we have that

1 |Ax| x ∈Ax y(x ) ≤ 1 2 -∆ + C α τ α + uniformly over x ∈ X ∆,-.

Hence, in order for k-nearest neighbor prediction to predict the Bayes-optimal label on X ∆ , it suffices that

k 0 1 2 + ∆ -C α τ α - ≥ k 2 . Since k 0 ≥ ( 1 2 + γ) • k, we have that the above holds if ∆ ≥ C α τ α + + 1 -2γ 2(1 + 2γ)

.

We now choose the values of τ, γ, to upper bound each of the terms on the R.H.S. by ∆/3 so that the above holds.

We can bound the last term by ∆/3 by setting:

γ = 1 2 • 3 -2∆ 3 + 2∆ . Next, taking k ≥ 3(3 + 2∆) 2∆ 2 (D log n + log(4D/δ)) ,

we have that ≤ ∆/3. Now, by Lemma 1, we have that setting

τ = 2k ω • v D • n • p X,0 1/D

gives us that r k (x) ≤ τ for all x ∈ X with probability at least 1 -δ/2. It thus suffices to take

k ≤ 1 2 ∆ 3 • C α D/α • ω • v D • p X,0 • n so that C α τ α ≤ ∆/3. Now in order for S ( 1 2 -γ)•k (C) ≥ τ , it suffices to have S 2 (C) ≥ τ .

This can be accomplished by having the following hold:

k ≤ 1 2 • S 2 (C) D • ω • v D • p X,0 • n.

Thus, there exists positive constants K l and K u depending only on F such that if

K u • 1 ∆ 2 • (log 2 (1/δ) • log n) ≤ k ≤ K u • min{S 2 (C) D , ∆ D/α } • n,

then the desired conditions hold.

A.4 PROOF OF THEOREM 2:

Proof of Theorem 2. The proof begins in the same way as the proof of Theorem 1. As before, let τ, γ, > 0 be quantities that will be determined later. Like before, we are reduced to showing

∆ ≥ C α τ α + + 1 -2γ 2(1 + 2γ) ,

as long as the conditions for Lemma 1 and 2 hold and S 2 (x) ≥ τ and r k (x) ≤ τ where we choose

= D log n + log(4D/δ) (1 + 2γ) • k , γ = 1 2 • 3 -2∆ 3 + 2∆ , τ = 2k ω • v D • n • p X,0 1/D .

These conditions hold for some K u and K l depending on F. Then we are reduced to having

2 3 ∆ ≥ D log n + log(4D/δ) (1 + 2γ) • k + C α 2k ω • v D • n • p X,0 α/D .

Since γ ≥ 0, it suffices to have

2 3 ∆ ≥ D log n + log(4D/δ) k + C α 2k ω • v D • n • p X,0 α/D .

The desired form for ∆ clearly follows for some choice of K depending only on D, ω, p X,0 , C α , all of which depend only on F.

Finally, we must ensure that ( 1 2 -γ) • k ≥ 2 so that S ( 1 2 -γ)•k (C) ≥ S 2 (x). Given the expression for γ, it is equivalent to have . Given the form of ∆ in terms of n and k, we see that it suffices to have that

k ≥ 9 2 • K • log n + log(1/δ) k + k n α/D -1

+ 3, which holds when k ≥ K 0 • n 2α/(2α+D) for some K 0 depending only on F, as desired.

A.5 PROOF OF THEOREM 3

Proof of Theorem 3. The first part follows from Theorem 2. For the second part, we have by Theorem 2 that if x ∈ X ∆ , then the k-NN classifier and the Bayes-optimal classifier match with probability 1 -δ uniformly. Thus, we have

R X -R * ≤ P(x ∈ X ∆ ) E F [g k (x) = y|x ∈ X ∆ ] -E F [g * (x) = y|x ∈ X ∆ ] ≤ C β • ∆ β • E F [g k (x) = y|x ∈ X ∆ ] -E F [g * (x) = y|x ∈ X ∆ ] ≤ C β • ∆ β • 2∆.

The result follows immediately from Theorem 2.

B HARD FLIP PERMUTATIONS:

For Fashion MNIST we hard flip by swapping the following classes: TSHIRT ↔ SHIRT, TROUSER ↔ DRESS, PULLOVER ↔ COAT, SANDAL ↔ BAG, SNEAKER ↔ ANKLEBOOT. For CI-FAR10 we swap the pairs: TRUCK ↔ AUTOMOBILE, BIRD ↔ AIRPLANE, DEER ↔ HORSE, CAT ↔ DOG, FROG ↔ SHIP. For CIFAR100, we 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. 

:



Figures and Tables:

D noisy has a high corruption rate; otherwise the representations learned by training on D noisy alone are often reasonable enough. The procedure begins by training on either D noisy ∪ D clean or D clean . For our experiments, we partition D clean into a training set D ct and validation set D cv and train models on D ct and D noisy ∪ D ct and choose the one that performs better on D cv . We then filter examples that disagree with the k-NN classifier prediction, where the k-NN is computed 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 noisy , D clean , k Train model M on either D noisy ∪ D clean or D clean . Let N be the activations of D noisy ∪ D clean on the logit layer of M. D filtered := {(x, y) ∈ N : η k (x) = y}, where η k is computed w.r.t. N . Train final model on D filtered ∪ D c .

Figure 1: Left: training samples. We observe that test accuracy improves as S 2 (C) increases (middle) and that fewer clean training samples are needed to achieve an accuracy of 90% (right).

Figure 2: UCI Results. Error plots against amount of noise applied to the labels of D noisy . D clean contains 5% of the data. Each column is a different corruption and each row is for a different dataset.We see that the k-NN method consistently chooses the best datapoints to filter leading to lower error. More results are in the Appendix.

Figure 3: Fashion MNIST. Each column is a different corruption method. We see that the k-NN approach performs competitively. More results are in the Appendix.

Figure 4: CIFAR10. Each column is a different corruption method. We see that our k-NN method performs competitively or outperforms on the uniform and flip noise types but performs worse for the hard flip noise type. More results are in the Appendix.

Figure 6: Performance across different values of k.Here we show that on a UCI dataset, the performance of Algorithm 1 is stable when varying its hyperparameter k. Note that the y-axis has been zoomed in to better see the differences between the curves.

S k (C) := min x∈C r k (x, C), where r k (x, C) denotes the distance from x to the k-th closest neighbor in C.

• k ≥ 2. It suffices to show that k ≥ 3(3+2∆) 2∆

Figure 7: Plots for UCI Phonemes dataset at 10, 20% clean data and all corruption types.

Figure 8: Plots for UCI Letters dataset at 5, 10, 20% clean data and all corruption types.

Figure 9: Plots for UCI Wilt dataset at 5, 10, 20% clean data and all corruption types.

Figure 10: Plots for UCI Parkinsons dataset at 5, 10, 20% clean data and all corruption types.

Figure 11: Plots for UCI Seeds dataset at 5, 10, 20% clean data and all corruption types.

Figure 12: Plots for UCI Iris dataset at 5, 10, 20% clean data and all corruption types.

Figure 13: Plots for MNIST at 5, 10, 20% clean data and all corruption types.

Figure 14: Plots for Fashion MNIST at 10, 20% clean data and all corruption types.

Figure 15: Plots for CIFAR10 at 10, 20% clean data and all corruption types.

Figure 16: Plots for CIFAR100 at 5, 10, 20% clean data and all corruption types.

Area under the test error vs noise rate curve. Each row corresponds to a dataset and size of clean dataset D clean pair, where the size is a percentage of the total training set (5%, 10%,

Table content: <table><tr><td/><td/><td>Uniform</td><td/><td/><td/><td/><td/><td/><td>Flip</td><td/><td/><td/><td/><td/><td/><td>Hard Flip</td><td/><td/><td/><td/></tr><tr><td>Dataset</td><td colspan="16">% Clean Forward Clean Distill GLC k-NN k-NN Classify Full Forward Clean Distill GLC k-NN k-NN Classify Full Forward</td><td colspan="5">Clean Distill GLC k-NN k-NN Classify Full</td></tr><tr><td/><td>5</td><td>4.55</td><td>3.16</td><td>2.48</td><td>2.33</td><td colspan="2">2.05 2.19</td><td>2.61</td><td>4.83</td><td>3.16</td><td>2.96</td><td>2.35</td><td>2.1</td><td>2.52</td><td>2.92</td><td>3.77</td><td>3.17</td><td>2.1</td><td>1.83</td><td colspan="2">1.82 1.82</td><td>2.52</td></tr><tr><td>Letters</td><td/><td>4.28</td><td>2.51</td><td>2.05</td><td>1.91</td><td colspan="2">1.78 1.79</td><td>2.23</td><td>4.45</td><td>2.52</td><td>2.12</td><td>1.92</td><td>1.8</td><td>2.06</td><td>2.49</td><td>3.63</td><td>2.52</td><td>1.85</td><td>1.6</td><td>1.6</td><td>1.64</td><td>2.36</td></tr><tr><td/><td/><td>3.77</td><td>2.06</td><td>1.76</td><td>1.57</td><td colspan="2">1.56 1.34</td><td>1.85</td><td>3.85</td><td>2.07</td><td>1.78</td><td>1.56</td><td colspan="2">1.58 1.42</td><td>1.93</td><td>3.35</td><td>2.05</td><td>1.62</td><td>1.38</td><td colspan="2">1.41 1.42</td><td>2.04</td></tr><tr><td/><td>5</td><td>7.89</td><td>1.91</td><td>1.79</td><td>2.12</td><td colspan="2">1.26 2.58</td><td>3</td><td>7.91</td><td>1.93</td><td>3.21</td><td>2.16</td><td colspan="2">1.34 3.97</td><td>4.31</td><td>6.6</td><td>1.92</td><td>1.77</td><td>1.96</td><td>1.2</td><td>1.78</td><td>2.7</td></tr><tr><td>Phonemes</td><td/><td>7.86</td><td>1.54</td><td>1.53</td><td>1.67</td><td colspan="2">1.16 2.28</td><td>2.85</td><td>7.95</td><td>1.54</td><td>2.75</td><td>1.69</td><td colspan="2">1.22 3.64</td><td>3.96</td><td>6.73</td><td>1.55</td><td>1.61</td><td>1.6</td><td colspan="2">1.15 1.62</td><td>2.58</td></tr><tr><td/><td/><td>7.72</td><td>1.34</td><td>1.33</td><td>1.35</td><td colspan="2">1.13 1.76</td><td>2.24</td><td>7.89</td><td>1.34</td><td>1.97</td><td>1.35</td><td colspan="2">1.16 2.87</td><td>3.28</td><td>6.36</td><td>1.33</td><td>1.45</td><td>1.3</td><td colspan="2">1.14 1.38</td><td>2.28</td></tr><tr><td/><td>5</td><td>5.18</td><td>0.56</td><td>0.85</td><td>0.54</td><td colspan="2">0.39 0.93</td><td>1.86</td><td>5.27</td><td>0.56</td><td>3.89</td><td>0.53</td><td colspan="2">0.52 5.15</td><td>4.95</td><td>4.6</td><td>0.55</td><td>0.73</td><td>0.58</td><td colspan="2">0.39 0.98</td><td>1.9</td></tr><tr><td>Wilt</td><td/><td>4.68</td><td>0.43</td><td>0.75</td><td>0.45</td><td colspan="2">0.32 0.77</td><td>1.77</td><td>5.63</td><td>0.44</td><td>3.14</td><td>0.43</td><td colspan="2">0.41 4.86</td><td>4.84</td><td>4.78</td><td>0.43</td><td>0.66</td><td>0.43</td><td colspan="2">0.31 0.78</td><td>1.81</td></tr><tr><td/><td/><td>4.31</td><td>0.36</td><td>0.86</td><td>0.35</td><td colspan="2">0.32 0.57</td><td>1.5</td><td>5.18</td><td>0.34</td><td>2.67</td><td>0.35</td><td colspan="2">0.34 4.23</td><td>4.32</td><td>5.63</td><td>0.34</td><td>0.61</td><td>0.36</td><td>0.3</td><td>0.57</td><td>1.49</td></tr><tr><td/><td>5</td><td>3.29</td><td>4.22</td><td>3.71</td><td>4.2</td><td colspan="2">3.08 2.87</td><td>2.71</td><td>5.13</td><td>4.33</td><td>5.56</td><td>4.39</td><td colspan="2">3.64 5.11</td><td>4.88</td><td>2.94</td><td>4.06</td><td>3.63</td><td>3.91</td><td colspan="2">2.99 2.84</td><td>3.01</td></tr><tr><td>Seeds</td><td/><td>3.43</td><td>3.04</td><td>2.84</td><td>2.99</td><td colspan="2">2.14 2.74</td><td>2.57</td><td>5.02</td><td>3.38</td><td>4.58</td><td>3.19</td><td colspan="2">2.65 4.9</td><td>4.73</td><td>2.75</td><td>3.42</td><td>2.96</td><td>3.14</td><td colspan="2">2.25 2.69</td><td>2.86</td></tr><tr><td/><td/><td>2.99</td><td>2.69</td><td>2.27</td><td>2.74</td><td colspan="2">1.72 2.44</td><td>2.2</td><td>4.41</td><td>2.56</td><td>3.57</td><td>2.65</td><td colspan="2">2.09 4.23</td><td>3.86</td><td>2.85</td><td>2.53</td><td>2.25</td><td>2.57</td><td colspan="2">1.62 2.43</td><td>2.49</td></tr><tr><td/><td>5</td><td>2.97</td><td>3.23</td><td>3.48</td><td>3.97</td><td colspan="2">2.46 1.72</td><td>2.05</td><td>5.25</td><td>3.38</td><td>5.15</td><td>4.03</td><td colspan="2">3.02 4.32</td><td>4.43</td><td>2.9</td><td>3.29</td><td>3.13</td><td>4.1</td><td colspan="2">2.32 1.14</td><td>1.35</td></tr><tr><td>Iris</td><td/><td>2.89</td><td>2.48</td><td>2.59</td><td>2.25</td><td colspan="2">1.32 1.26</td><td>1.55</td><td>5.06</td><td>2.53</td><td>4.58</td><td>2.24</td><td colspan="2">2.17 3.98</td><td>4.08</td><td>2.6</td><td>2.34</td><td>2.02</td><td>1.86</td><td colspan="2">1.15 0.91</td><td>1.16</td></tr><tr><td/><td/><td>2.46</td><td>1.85</td><td>1.97</td><td>1.52</td><td>0.6</td><td>0.96</td><td>1.32</td><td>4.46</td><td>1.51</td><td>3.45</td><td>1.38</td><td colspan="2">1.46 3.36</td><td>3.53</td><td>2.51</td><td>1.84</td><td>1.48</td><td>1.34</td><td colspan="2">0.58 0.65</td><td>1</td></tr><tr><td/><td>5</td><td>5</td><td>3.46</td><td>3.26</td><td>4.22</td><td>3.4</td><td>3.26</td><td>3.76</td><td>5.17</td><td>3.55</td><td>4.49</td><td>4.1</td><td colspan="2">3.36 5.34</td><td>5.35</td><td>4.98</td><td>3.71</td><td>3.56</td><td>4.59</td><td colspan="2">3.68 3.28</td><td>3.63</td></tr><tr><td>Parkinsons</td><td/><td>5.35</td><td>3.26</td><td>3.22</td><td>3.45</td><td colspan="2">3.21 3.22</td><td>3.82</td><td>5.43</td><td>3.38</td><td>4.25</td><td>3.44</td><td colspan="2">3.32 5.27</td><td>5.13</td><td>5.24</td><td>3.26</td><td>3.1</td><td>3.37</td><td colspan="2">3.11 3.12</td><td>3.82</td></tr><tr><td/><td/><td>4.88</td><td>3.01</td><td>3.08</td><td>3.1</td><td colspan="2">2.98 2.97</td><td>3.52</td><td>5.19</td><td>3.02</td><td>3.94</td><td>3.05</td><td colspan="2">2.95 4.99</td><td>5.06</td><td>5.1</td><td>2.98</td><td>3.01</td><td>2.98</td><td colspan="2">2.96 2.91</td><td>3.47</td></tr><tr><td/><td>5</td><td>2.88</td><td>0.69</td><td>1.03</td><td>0.5</td><td>0.4</td><td>2.72</td><td>2.75</td><td>3.6</td><td>0.69</td><td>1.91</td><td>0.5</td><td colspan="2">0.44 3.46</td><td>3.49</td><td>2.03</td><td>0.69</td><td>0.78</td><td>0.22</td><td colspan="2">0.29 0.65</td><td>2.14</td></tr><tr><td>MNIST</td><td/><td>2.57</td><td>0.5</td><td>0.85</td><td>0.41</td><td colspan="2">0.33 2.42</td><td>2.45</td><td>3.22</td><td>0.5</td><td>1.5</td><td>0.42</td><td colspan="2">0.35 3.1</td><td>3.14</td><td>1.86</td><td>0.5</td><td>0.67</td><td>0.21</td><td colspan="2">0.26 0.48</td><td>1.98</td></tr><tr><td/><td/><td>2.07</td><td>0.35</td><td>0.69</td><td>0.34</td><td colspan="2">0.27 1.97</td><td>2.03</td><td>2.48</td><td>0.35</td><td>0.86</td><td>0.34</td><td colspan="2">0.27 2.36</td><td>2.41</td><td>1.54</td><td>0.35</td><td>0.53</td><td>0.2</td><td colspan="2">0.22 0.36</td><td>1.67</td></tr><tr><td/><td>5</td><td>2.76</td><td>1.88</td><td>1.73</td><td>1.59</td><td colspan="2">1.56 2.53</td><td>2.54</td><td>3.55</td><td>1.87</td><td>2.55</td><td>1.59</td><td>1.6</td><td>3.3</td><td>3.31</td><td>2.3</td><td>1.87</td><td>1.62</td><td>1.44</td><td colspan="2">1.48 2.31</td><td>2.4</td></tr><tr><td>Fashion MNIST</td><td/><td>2.47</td><td>1.71</td><td>1.6</td><td>1.52</td><td colspan="2">1.52 2.21</td><td>2.3</td><td>3.14</td><td>1.71</td><td>2.13</td><td>1.53</td><td colspan="2">1.54 2.92</td><td>2.99</td><td>2.14</td><td>1.71</td><td>1.52</td><td>1.41</td><td colspan="2">1.46 2.19</td><td>2.22</td></tr><tr><td/><td/><td>2.07</td><td>1.56</td><td>1.48</td><td>1.45</td><td colspan="2">1.44 1.95</td><td>2.05</td><td>2.38</td><td>1.56</td><td>1.54</td><td>1.46</td><td colspan="2">1.46 2.17</td><td>2.27</td><td>1.92</td><td>1.56</td><td>1.43</td><td>1.38</td><td colspan="2">1.41 2.04</td><td>1.97</td></tr><tr><td/><td>5</td><td>6.74</td><td>7</td><td>6.86</td><td>5.43</td><td colspan="2">5.03 6.34</td><td>6.74</td><td>7.14</td><td>7.2</td><td>7.12</td><td>5.52</td><td colspan="2">5.35 6.71</td><td>7.12</td><td>5.08</td><td>7.13</td><td>5.85</td><td>3.76</td><td colspan="2">4.27 4.33</td><td>4.96</td></tr><tr><td>CIFAR10</td><td/><td>6.58</td><td>6.58</td><td>6.32</td><td>5.39</td><td colspan="2">5.27 6.11</td><td>6.55</td><td>6.82</td><td>6.56</td><td>6.72</td><td>5.62</td><td colspan="2">5.32 6.48</td><td>6.83</td><td>4.89</td><td>6.53</td><td>5.3</td><td>3.91</td><td>4.4</td><td>4.21</td><td>4.89</td></tr><tr><td/><td/><td>6.4</td><td>5.52</td><td>5.66</td><td>5.11</td><td colspan="2">4.57 5.93</td><td>6.36</td><td>6.62</td><td>5.59</td><td>5.9</td><td>5.16</td><td colspan="2">4.85 6.1</td><td>6.56</td><td>4.77</td><td>5.45</td><td>4.68</td><td>3.51</td><td colspan="2">3.82 4.03</td><td>4.75</td></tr><tr><td/><td>5</td><td>10.8</td><td>10.22</td><td>9.98</td><td>9.59</td><td colspan="2">9.57 9.17</td><td>9.29</td><td>10.79</td><td colspan="3">10.24 10.03 9.64</td><td colspan="2">9.66 9.2</td><td>9.29</td><td>10.64</td><td>10.23</td><td>9.88</td><td>8.58</td><td colspan="2">8.98 7.48</td><td>8.04</td></tr><tr><td>CIFAR100</td><td/><td>10.79</td><td>9.94</td><td>9.7</td><td>9.42</td><td colspan="2">9.63 9.09</td><td>9.25</td><td>10.81</td><td>9.89</td><td>9.68</td><td>9.46</td><td colspan="2">9.63 9.1</td><td>9.25</td><td>10.65</td><td>9.89</td><td>9.38</td><td>8.56</td><td colspan="2">9.19 7.44</td><td>7.99</td></tr><tr><td/><td/><td>10.78</td><td>9.38</td><td>9.15</td><td>9.06</td><td colspan="2">9.23 8.92</td><td>9.07</td><td>10.8</td><td>9.44</td><td>9.13</td><td>8.97</td><td colspan="2">9.17 8.92</td><td>9.09</td><td>10.66</td><td>9.41</td><td>8.65</td><td>8.07</td><td colspan="2">8.81 7.33</td><td>7.9</td></tr><tr><td/><td>5</td><td>5.04</td><td>3.52</td><td>3.56</td><td>1.99</td><td colspan="2">1.62 4.64</td><td>4.95</td><td>5.6</td><td>3.65</td><td>4.09</td><td>2.17</td><td colspan="2">2.05 5.23</td><td>5.52</td><td>3.04</td><td>4.17</td><td>2.16</td><td>0.89</td><td colspan="2">1.35 2.32</td><td>3.04</td></tr><tr><td>SVHN</td><td/><td>4.98</td><td>2.2</td><td>3.2</td><td>2.27</td><td colspan="2">1.34 4.51</td><td>4.82</td><td>5.5</td><td>2.28</td><td>3.72</td><td>2.29</td><td colspan="2">1.48 4.96</td><td>5.29</td><td>2.98</td><td>2.41</td><td>2.01</td><td>0.88</td><td colspan="2">1.04 2.16</td><td>2.98</td></tr><tr><td/><td/><td>4.32</td><td>1.83</td><td>2.67</td><td>2.14</td><td>1.2</td><td>3.96</td><td>4.41</td><td>4.85</td><td>1.83</td><td>3.09</td><td>1.9</td><td colspan="2">1.19 4.34</td><td>4.82</td><td>2.7</td><td>1.85</td><td>1.54</td><td>0.98</td><td colspan="2">0.98 1.83</td><td>2.74</td></tr></table>

Peer review (iclr2020):
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 The 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. Since 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. - I encourage another experiment where the label corruption is not completely at random, that is it depends on the values of x itself. - 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. - 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? - Why didn*t the authors show the original model trained on the full dataset? Is it because it always does worse than all the baselines considered in the paper? I 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. - 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? In general, it seems the authors did not compare other filtering baselines, which would be more related to their method, for example: Learning with Confident Examples: Rank Pruning for Robust Classification with Noisy Labels Northcutt et al. (2017). https://arxiv.org/abs/1705.01936 - It would be valuable to the scientific community if the authors can comment on: Rolnick et al. (2018). Deep Learning is Robust to Massive Label Noise. https://arxiv.org/pdf/1705.10694.pdf - Some similar looking ideas have been proposed in: Gao et al. (2018). On the Resistance of Nearest Neighbor To Random Noisy Labels https://pdfs.semanticscholar.org/4227/918020c15b719c415e93eb63d436583f1745.pdf Parvin et al. (2010). A Modification on K-Nearest Neighbor Classifier. https://globaljournals.org/GJCST_Volume10/7-A-Modification-on-K-Nearest-Neighbor-Classifier.pdf so the authors should contrast their method/analysis against those papers. - In Thm 1: *w.r.t. X* should be *w.r.t. x* (lower case)