Year: 2019

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.

heading: 1 INTRODUCTION
text: 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).

heading: 2 RELATED WORK
text: We review relevant prior work in training on noisy labels and related k-NN theory.

heading: 2.1 TRAINING WITH NOISY LABELS
text: 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. Patrini et al. (2017) suggest deriving it from the softmax distribution of the model trained on noisy data while Goldberger & Ben-Reuven (2016); Jindal et al. (2016); Han et al. (2018) give alternatives. Accurate estimates are generally hard to 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. (2015); Khetan et al. (2017); Vahdat (2017) use EM-type algorithms to estimate the clean label distribution.
Noise-Robust Training 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.
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.

heading: 3 ALGORITHM
text: We first define the k-nearest neighbor classifier:
Definition 1 (k-NN). Let the k-NN radius of x ∈ X be rk(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 Nk(x) := B(x, rk(x)) ∩ X . Then for all x ∈ X , the k-NN classifier function w.r.t. X has discriminant function
ηk(y;x) := 1
|Nk(x)| n∑ i=1 1 [yi = y, xi ∈ Nk(x)] ,
with prediction ηk(x) := arg maxy ηk(y;x).
Our method Algorithm 1 assumes a dataset Dnoisy with potentially noisy labels, along with a dataset Dclean consisting of clean or trusted labels. Note that we allow Dclean to be empty (i.e. in instances where no such trusted data is available). We have found that having Dclean becomes important when Dnoisy has a high corruption rate; otherwise the representations learned by training on Dnoisy alone are often reasonable enough. The procedure begins by training on eitherDnoisy∪Dclean orDclean. For our experiments, we partition Dclean into a training set Dct and validation set Dcv and train models on Dct and Dnoisy ∪ Dct and choose the one that performs better on Dcv . 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: Dnoisy, Dclean, k Train modelM on either Dnoisy ∪ Dclean or Dclean. Let N be the activations of Dnoisy ∪ Dclean on the logit layer ofM. Dfiltered := {(x, y) ∈ N : ηk(x) = y}, where ηk is computed w.r.t. N . Train final model on Dfiltered ∪ Dc.

heading: 4 THEORETICAL ANALYSIS
text: For the theoretical analysis, we assume the binary classification problem with the features defined on compact set X ⊆ RD. We assume that points are drawn according to distribution F as follows: the features come from distribution PX 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 PX 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 r0 > 0 such that Vol(X ∩B(x, r)) ≥ ω · Vol(B(x, r)) for all x ∈ X and 0 < r < r0, where B(x, r) := {x′ ∈ X : |x− x′| ≤ r}.
Let pX be the density function corresponding to PX . The next assumption ensures that with a sufficiently large sample, we will obtain a good covering of the input space.
Assumption 2 (pX bounded from below). pX,0 := infx∈X pX(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 (η Hö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).
S2(C) := min x,x′∈C,x6=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 Kl,Ku > 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
Kl · 1
∆2 · log2(1/δ) · log n ≤ k ≤ Ku ·min{S2(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) ≥ 12 ].
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 Kl,Ku,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
Kl · log2(1/δ) · n α α+D ≤ k ≤ Ku · S2(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) := 1[η(x) ≥ 12 ] where
∆ = K ·
(√ log n+ log(1/δ)
k +
( k
n
)α/D) .
Remark 1. Choosing k = O(n2α/(2α+D)) in the above result gives us ∆ = Õ(n−α/(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.
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 someCβ and β and all ∆ > 0:
PX (x 6∈ X∆) ≤ Cβ ·∆β .
Theorem 3 (Rates under Tsybakov Noise Condition). Let δ > 0 and suppose Assumptions 1, 2, 3 and 4 hold. There exists constants Kl,Ku,K,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 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
Kl · log2(1/δ) · n α α+D ≤ k ≤ Ku · S2(C)D · n, and define ηk(x) := arg maxy ηk(y;x). Then,
P (ηk(x) 6= η∗(x)) ≤ K ·
(√ log n+ log(1/δ)
k +
( k
n
)α/D)β ,
RX −R∗ ≤ K ′ ·
(√ log n+ log(1/δ)
k +
( k
n )α/D)β+1 where RX := EF [gk(x) 6= y] and R∗ := EF [g∗(x) 6= y] denote the risk of the k-NN method and Bayes optimal classifier, respectively.
Remark 2. Choosing k = O(n2α/(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.

heading: 4.1 IMPACT OF MINIMUM PAIRWISE DISTANCE
text: The minimum pairwise distance across corrupted samples, S2(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, I2×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, S2(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 S2(C) decreases, so does test accuracy and we need more clean training samples to compensate.

heading: 5 EXPERIMENTS
text: We evaluate the effectiveness of our algorithm as follows. We split each dataset’s training set into two parts, Dclean and Dnoisy. We then corrupt the labels of some fraction of examples in Dnoisy 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 12 , we flip the label m to π(m) where π is some predefined
permutation of the labels.
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 Dclean is randomly selected and is 5% of the data. In the Appendix, we show results over different sizes of Dclean. 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.

heading: 5.1 UCI AND MNIST RESULTS
text: 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.

heading: 5.2 CIFAR RESULTS
text: 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.

heading: 5.3 SVHN RESULTS
text: 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
hyperparameter is highly desirable because optimal tuning is often not available, especially when no sufficient clean validation set is available.

heading: 5.5 AREA UNDER ERROR VS NOISE LEVEL CURVE ACROSS DATASETS
text: 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.

heading: A PROOFS
text: A.1 SUPPORTING THEORETICAL RESULTS
The following bounds rk(x) uniformly in x ∈ X . Lemma 1 (Lemma 2 of Jiang (2019)). The following holds with probability at least 1− δ/2. If
28 ·D log2(4/δ) · log n ≤ k ≤ 1 2 · ω · pX,0 · vD · rD0 · n,
then supx∈X rk(x) ≤ ( 2k ω·vD·n·pX,0 )1/D , where vD is the volume of the unit ball in RD.
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 := |{Nk(x) : x ∈ X}|. Then M ≤ D · nD.
A.2 MINIMUM k-NN SPREAD
We propose a more notion of how spread out a 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 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).
Sk(C) := min x∈C rk(x,C),
where rk(x,C) denotes the distance from x to the k-th closest neighbor in C.
Note that this definition is consistent with the earlier definition of S2.
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 rk(x) ≤ τ and Sb( 12−γ)·kc(C) ≥ τ . Then, at least 1 2 + γ fraction of the points within x’s k-nearest neighbors are not in the corrupted set C. Let Ax := Nk(x)\C, that is, the k-nearest neighbors of x that are not in C. Then it is clear that Ax is a k0-nearest neighbor set of x relative to X\C for some k0 ≥ d( 12 + γ) · ke. We have that Ax ⊆ X
∆ ⊕ τ where A ⊕ r := {x ∈ X : infa∈A |x − a| ≤ r}. Let us consider without loss of generality that η(x) ≥ 12 + ∆ (call this set X
∆,+). The case X∆,− := {x ∈ X∆ : η(x) ≤ 12 − ∆} follows by symmetry. Thus, we have η(x′) ≥ 12 + ∆ − Cατ
α for all x′ ∈ Ax. By Hoeffing’s inequality, we have
P
( 1
|Ax| ∑ x′∈Ax y(x′) < 1 2 + ∆− Cατα −
) ≤ exp(−2 2 · k0),
where y(x) is the label corresponding to sample x. By Lemma 2, we have that there are at most D · nD such k0-nearest neighbor sets across all k0 in X\C. That is, this is also a bound on the number of distinct Ax 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 |Ax| ∑ 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
′) ≥ 12 + ∆ − Cατ
α − uniformly over x ∈ X∆,+. Similarly, with probability at least 1 − δ/4 we have that 1 |Ax| ∑ x′∈Ax y(x ′) ≤ 12 −∆ + Cατ α + uniformly over x ∈ X∆,−.
Hence, in order for k-nearest neighbor prediction to predict the Bayes-optimal label on X∆, it suffices that
k0
( 1
2 + ∆− Cατα −
) ≥ k
2 .
Since k0 ≥ ( 12 + γ) · 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
ω · vD · n · pX,0 )1/D gives us that rk(x) ≤ τ for all x ∈ X with probability at least 1− δ/2. It thus suffices to take
k ≤ 1 2
( ∆
3 · Cα
)D/α · ω · vD · pX,0 · n
so that Cατα ≤ ∆/3. Now in order for Sb( 12−γ)·kc(C) ≥ τ , it suffices to have S2(C) ≥ τ . This can be accomplished by having the following hold:
k ≤ 1 2 · S2(C)D · ω · vD · pX,0 · n.
Thus, there exists positive constants Kl and Ku depending only on F such that if
Ku · 1
∆2 · (log2(1/δ) · log n) ≤ k ≤ Ku ·min{S2(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 S2(x) ≥ τ and rk(x) ≤ τ where we choose
=
√ D log n+ log(4D/δ)
(1 + 2γ) · k , γ =
1 2 · 3− 2∆ 3 + 2∆ , τ =
( 2k
ω · vD · n · pX,0
)1/D .
These conditions hold for some Ku and Kl depending on F . Then we are reduced to having
2 3 ∆ ≥
√ D log n+ log(4D/δ)
(1 + 2γ) · k + Cα
( 2k
ω · vD · n · pX,0
)α/D .
Since γ ≥ 0, it suffices to have
2 3 ∆ ≥
√ D log n+ log(4D/δ)
k + Cα
( 2k
ω · vD · n · pX,0
)α/D .
The desired form for ∆ clearly follows for some choice of K depending only on D,ω, pX,0, Cα, all of which depend only on F . Finally, we must ensure that b( 12 −γ) ·kc ≥ 2 so that Sb( 12−γ)·kc(C) ≥ S2(x). Given the expression
for γ, it is equivalent to have b (
2∆ 3+2∆ ) · kc ≥ 2. It suffices to show that k ≥ 3(3+2∆)2∆ . 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 ≥ K0 · n2α/(2α+D) for some K0 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
RX −R∗ ≤ P(x 6∈ X∆) ( EF [gk(x) 6= y|x 6∈ X∆]− EF [g∗(x) 6= y|x 6∈ X∆] ) ≤ Cβ ·∆β · ( EF [gk(x) 6= y|x 6∈ X∆]− EF [g∗(x) 6= y|x 6∈ X∆] ) ≤ Cβ ·∆β · 2∆.
The result follows immediately from Theorem 2.

heading: B HARD FLIP PERMUTATIONS
text: For Fashion MNIST we hard flip by swapping the following classes: TSHIRT↔ SHIRT, TROUSER ↔ DRESS, PULLOVER ↔ COAT, SANDAL ↔ BAG, SNEAKER ↔ ANKLEBOOT. For CIFAR10 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.

heading: C ADDITIONAL PLOTS
text: We provide the plots that were ommitted from the main text due to space constraints.

Review summaries:
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.