Deep $k$-NN Label Smoothing Improves Reproducibility of Neural Network Predictions
Authors: Dara Bahri
Heinrich Jiang
Venue:  (2021)
Keywords: $k$-nearest neighbors
neural networks
label smoothing
churn
reproducibility
stability
robustness

Abstract: Training modern neural networks is an inherently noisy process that can lead to high \emph{prediction churn}-- disagreements between re-trainings of the same model due to factors such as randomization in the parameter initialization and mini-batches-- even when the trained models all attain high accuracies. Such prediction churn can be very undesirable in practice. In this paper, we present several baselines for reducing churn and show that utilizing the $k$-NN predictions to smooth the labels results in a new and principled method that often outperforms the baselines on churn while improving accuracy on a variety of benchmark classification tasks and model architectures.

Under review as a conference paper at ICLR 2021
DEEP k:NN LABEL SMOOTHING IMPROVES STABIL- ITY OF NEURAL NETWORK PREDICTIONS
An Anonymous authors Paper under double-blind review
ABSTRACT
Training modern neural networks is an inherently noisy process that can lead to prediction churn- disagreements between re-trainings of the same model due to factors such as randomization the parameter initialization and mini-batches- even when the trained models all attain high accuracies. Such prediction churn can be very undesirable in practice. In this paper, we present several baselines for reducing churn and show that utilizing the k-NN predictions to smooth the labels results in new and principled method that often outperforms the baselines on churn while improving accuracy on a variety of benchmark classification tasks and model architectures.
INTRODUCTION
Deep neural networks (DNNs) have proved to be immensely successful at solving complex classifi- cation tasks across a range of problems. Much of the effort has been spent towards improving their predictive performance (i.e. accuracy). while comparatively little has been done towards improving the stability of training these models. Modern DNN training inherently noisy due to factors such as the random initialization of network parameters, the mini-batch ordering, and effects of various data augmentation or pre-proces peeprocesssng tricks, all of which are exacerbated by the non-convexity of the loss surface. This results in local optima corresponding to models that have very different predic- tions on the same data points. This may seem counter-intuitive, but even when the different runs all produce very high accuracies for the classification task, their predictions drastically as we will show later in the experiments. Thus, even an optimized training procedure can lead to high prediction churn, which refers to the proportion of sample-level disagreements between classifiers caused by different runs of the same training procedure
still differ quite
In practice, reducing such predictive churn can be critical. For example, in a production system, models are often continuously improved on by being trained or retrained with new data or better model architectures and training procedures. In such scenarios, a candidate model for release must be compared to the current model serving in production. Oftentimes, this decision is conditioned on more than just overall offline test accuracy- in fact, oftentimes the offline metries are not completely aligned with actual goal, especially if these models are used as part of a larger system (e.g. max- imizing offline click-through rate vs. maximizing revenue or user satisfaction). As a result, these comparisons oftentimes require extensive and costly live experiments, requiring human evaluation situations where the candidate and the production model disagree (i.e. in many situations, the true labels are not available without a manual labeler). In these cases, it can be highly desirable to lower prediction churn.
Despite the practical relevance of lowering predictive churn, there has been surprisingly little work done in this area, which we highlight in the related work section. In this work, we focus on predictive churn reduction under retraining the same model architecture on an identical train and test set. Our main contributions are as follows:
We provide one of the first comprehensive analyses of baselines to lower prediction churn, showing that popular approaches designed for other goals are effective baselines for churn reduction, even compared to methods designed for this goal.
'Concretely, given two classifiers applied to the same test samples, the prediction churn between them is the fraction of test samples with different predicted lahels.

---

Under review as a conference paper at ICLR 2021
We improve label smoothing, a global smoothing method popular for improving model confidence scores, by utilizzig the local information leveraged by the k-NN labels thus introducing k-NN label smoothing which show to often outperform the basclines wide range of benchmark datasets and model architectures.
We show new theoretical results for the k-NN labels suggesting the usefulness of the k--N label. We show under mild nonparametric assumptions that for wide range of k. the k- NN labels uniformly approximates the Bayes-optimal label and when k is tuned optimally, achieves the minimax optimal rate. We also show that when linear in n, the distri- bution implied by the K-NN label approximates the original distribution smoothed with an adaptive kernel.
RELATED WORKS
Our work spans multiple sub-areas of machine learning. The main problem this paper tackles is reducing prediction churn. In the process, we show that label smoothing is an effective baseline and we improve upon it in principled manner using deep k-NN label smoothing.
Prediction Churn. There are only a few works which explicitly address prediction churn. Fard et al. (2016) proposed training a model so that it has small prediction instability with future versions of the model by modifying the data that the future versions are trained on. They furthermore propose turning the classification problem into regression towards corrected predictions of an older model as well as regularizing the new model towards the older model using example weights. Cotter et al. (2019;; ; Goh et al.) (216)) constrained optimization to directly lower prediction churn across model versions. Simultancously training multiple identical models (apart from initialization) while tethering their predictions together via regularization has been proposed in the context of distilla- tion (Anil et af.] [2018] [Zhang et al., 2018 Zhh et al.] (2018) Song & Chail 2018) and robustness to label noise (Malach & Shalev-Shwartz] [017 Han et al., 2018). This family of methods was termed "co-distillation" " Anil et al. (2018), who also noted that it can be used to reduce churn in addition to improving accuracy. In this paper, we show much more extensively that co-distillation is indeed reasonable baseline for churn reduction.
Label smoothing. Label smoothing (Szegedy et al. 2016 is a simple technique that proposes to train a model the model on the soft labels obtained by convex combination of the hard true label and the soft uniform distribution across all the labels. It has been shown that it prevents the network from being over-confident and leads to better confidence calibration (Müller et al.) 2019). Here we show that label smoothing is a reasonable baseline for reducing prediction churn, and we moreover enhance it for this task by smoothing the labels locally via k-NN rather than a the pure global approach mixing with the uniform distribution.
k-NN Theory. The theory of K-NN classification has long history (e.g. Fix & Hodges Jr 1955 Cover (968);; Stone (1977): Devroye et al. (1994): Chaudhuri & Dasgupta (2014)). To our knowl- edge, the most relevant Æ-NN classification result is by Chaudhuri & Dasgupta (2014), who show statistical risk bounds under similar assumptions as used in our work. Our analysis shows finite- sample Lox bounds on the k-NN labels, which stronger notion of consistency as it provides uniform guarantee, rather than an average guarantee as is shown in previous works under standard risk measures such as Ly error. We do this by leveraging recent techniques developed in Tinng (2019) for N--N regression, which assumes an additive noise model instead of classification. Moreover, we provide to our knowledge the first consistency guarantee for the case where grows linearly with n.
Deep k-NN. h-NN is a classical method in machine learning which has recently been shown to be useful when applied to the intermediate embeddings of deep neural network (Papernot & Mc- Daniel 2018) to obtain more calibrated and adversarially robust networks. This is because standard distance measures are often better behaved in these representations leading to better performance of k-NN on these embeddings than on the raw inputs. Jiang et al. (2018) uses nearest neighbors on the intermediate representations to obtain better uncertainty scores than softmax probabilities and Bahri et al. (2020) uses the k-NN label disagreement to filter noisy labels for better training. Like these works, we also leverage k-NN on the intermediate representations but we show that utilizing the I:-N labels leads lower prediction chum.
2

---

Under review as a conference paper at ICLR 2021
3 ALGORITHM
Suppose that the task is multi-class classification with L classes and the training datapoints are (I1, y1,,... (In, Vn), where 2; E X, and X' a compact subset of RR and yi E K where repre- sents the one-hot vector encoding of the label- that is, if the i-th example has label j. then yi has the j-th entry and 0 everywhere else. Then we give the formal definition of the smoothed labels:
Definition (Label Smoothing). Given label smoothing parameter S a S then the smoothed label is (where 1,, denoles the vector of all 1 in RR-).
J.S == a) L 1 Vo
We next formally define the k--N label, which is the average label of the example's k-nearest neighbors in the training set. Let us use shorthand X = {II,,.., Jn and yi E R+- Definition 2 (k-NN label). Let the k-NN radius of x E X be (x) = inf(r where Bax, r) {xr X : S Sr} and the k-NN of E X be N₂(x) = ((5,)()))X
Then for all x E X, the k-NN label is defined as
1 mx(x) = (N&(T))
Σ
no 1 Nx(x))
The label smoothing method can be seen as performing a global smoothing. That is, every label is equally transformed towards the uniform distribution over all labels. While it seems almost de- ceptively simple, it has only recently been shown to be effective in practice, specifically for better calibrated networks. However, since this smoothing technique is applied equally to all datapoints, it fails to incorporate local information about the datapoint. To this end, we propose using the k-NN label, which smooths the label across its nearest neighbors. We show thcoretically that the k-NN label can be strong proxy for the Bayes-optimal label, that is, the best possible prediction one can make given the uncertainty. In other words, compared to the true label (or even the label smoothing), the k-NN label is robust to variability in the data distribution and provides a more stable estimate of the label than the original hard label which may noisy. Training on such noisy labels have been shown to hurt model performance (Bahri et al.) (020) and using the smoothed labels can help mitigate these effects. To this end, we define k--N label smoothing as follows:
Definition (k-NN label smoothing). Let S a, b S be k-NN label smoothing parameters. Then the k-NN smoothed label of datapoint (I, 3) is defined as:
ANN Da.b
(1 (1-a) a) a..
(b
1
1 +11 (1-b) -m(()))) (1-b)-mm(x))
We see that a is used to weight between using the true labels vs. using smoothing, and is used to weight between the global vs. local smoothing. Algorithm shows how k-NN label smoothing is applied to deep learning models. Like Bahri et al. (2020), we perform k-NN on the network's logits layer.
Algorithm Deep k-NN label smoothing
Inputs: < a. 1, Training data (I), 11.21 (1), )... .... (In, Vn). model training procedure M. Train model Mo on (11,y)),,. vI),..., (Im, Mn) with M.
Let 21,..., 2n E R be the logits of 31,..., Tns respectively, w.r.t. Mo
Let Yr be the k-NN smoothed label of (z4, y1) computed w.r.t. dataset (21, M1), (Zn, Vn). Train model M on (r,,,1,.... ..., (In, Fn) with M.
THEORETICAL ANALYSIS
In this section, we provide theoretical justification for why the k-NN labels may be useful. In particular, show results for two settings, where is the number of datapoints.
3

---

Under review as a conference paper at ICLR 2021
When & < n, show that with appropriate setting of k, the k-NN smoothed labels approximates the predictions of Bayes-optimal classifier at a minimax-optimat rate.
When = O(n), we show that the distribution implied by the k-NN smoothed labels is equivalent to the original distribution convolved with adaptive smoothing kernel.
Our results may also reveal insights into why distillation methods (the procedure of training a model on another model's predictions instead of the true labels) can work. Another way of considering the result is that the k-NN smoothed label is equivalent to the soft prediction of the k-NN classifier. Thus, one were to train on the k-NN labels, it would be essentially distillation on the k-NN classi- fier and our theoretical results show that the labels implied by k-NN approximate the predictions of the optimal classifier (in the k < n setting). Learning the optimal classifier may indeed be better goal than learning from the true labels, because the latter may lead to overfitting to the sampling noise rather than just the true signal implied by the optimal classifer. While distillation is not the topic of this work, our results in this section may be of independent interest that area.
For the analysis, we assume the binary classification setting, but it is understood that our results can be straightforwardly generalized the multi-class setting. The feature vectors are defined on compact support X' C IR P and datapoints are drawn as follows: the features vector is drawn from density px on X and the labels are drawn according to the label function 7) X [0, 1], i.e. ((x)= = P(Y = X|X z).
4.1
k <<n
We make a few mild regularity assumptions for our analysis to hold, which are standard in works analyzing non-parametric methods e.g. [Singh et al. (2009); Chaudhuri & Dasgupta (2014); Reeve & Kaban (2019): Doing (2019); Babri et al. (2020). The first part ensures that the support X does not become arbitrarily thin anywhere, the second ensures that the density does not vanish anywhere in
the support, and the third ensures that the label function 1) is smooth w.r.t. to its input.
Assumption 1. The following three conditions hold:
Support Regularity: There exists w > O and To > O such that Vol(X n B(x, r)) 2 w. Voll Vol(B(z, for all x E X and 0 < < ro, where B(x,r) {x' X | x' S r).
Non-vanishing density: Px,0 inf z (x O.
Smoothness of q. There exists < a S and C. > such that [n(œ)) - n(x')| S Calæ - xa for all x' EX
We have the following result which provides a uniform bound between the smoothed k--N label and the Bayes-optimal label n).
Theorem 1. Ler 0 and suppose that Assumption 7 holds and that is satisfies the following:
2
D (4/8)) log n s k - 2 w.. PP.o UD -ro
where uD = Ma/2+1] the volume of a D-dimensional unit ball. Then with probability at least
P/2
1 6, we have
2k
a/D
2 log (4D/8) + 2D log(n)
(m(x))) n(x)) Ca xEX
sup
w UD n Px.0
In other words, there exists constants C1, C2, C depending on y and 5 such that if & satisfies
C₂ log C2- n,
then with probability at least 1 8, ignoring logarithmic factors in and 1/8:
sup (m)( n(xx) s C. ((*) o/D 1 =xx
k
4

---

Under review as a conference paper at ICLR 2021
Choosing & (22//(2a+))) D), gives a bound of sup (2)2) (xx) - Ö(n D0(n=1/(2++)) 111(2+++)))))))))))))))))))))))) which the minimax optimal rate as established by Tsybakov et al. 1997
Therefore, the advantage of using the smoothed labels nh (x1), ... (xx)) instead of the true labels ....... Un, is that the smoothed labels approximate the Bayes-optimal classifier. Moreover, as shown above, with appropriate setting of k; the smoothed labels minimax-optimal estimator of the true label function 1). Thus, the smoothed labels provide as good of a proxy for as any estimator possibly can.
As suggested earlier, another way of considering this result is that the original labels may contain considerable noise and thus single label can be guaranteed reliable. Using the smoothed label instead mitigates this effect and allows us to train the model to match the label function 17.
4.2 : LINEAR IN π
In the previous subsection, we showed the utility of k-NN label smoothing as a theoretically sound proxy for the Bayes-optimal labels, which attains statistical consistency guarantees long as k grows faster than log n and k/n - O. Now, we analyze the case where grows linearly with n. In this case, the k-NN smoothed labels longer recover the Bayes-optimal label function 7, but instead an adaptive kernel smoothed version r7. We make this relationship precise here.
Suppose that k = |3 nl for some 0 < 3 <
1. We define the 8-smoothed label function:
Definition 4 (3-smoothed label function). Let ræ(x) inf > 0 P(B(x,r)) 2 8}. that is the radii of the smallest ball centered at x with probability mass B w.r.. Px. Then, let ()(x)) be the expectation of n (xx, (x)) w.r.. Px:
1 B B(z.g(())
(x) (
i
n(z) Px(x)dx.
We can view 77 as an adaptively kernel smoothed version of 7, where adaptivity arises from the density of the point (the more dense, the smaller the bandwidth we smooth it across) and the kernel based on the density.
We now prove the following result which shows that in this setting Y2 estimates (1)). It is worth noting that we need very little assumption on as compared to the previous result because the 3- smoothing of provides a more regular label function; moreover, the rates are fast i.e. (VDD)n). Theorem 2. Let < 8 and k = L3 nJ. Then with probability at leust 1 8, we have for n sufficiently large depending B, 8:
2 log (D/))) 2D log(n)
sup (x) 7)(x0] 33 #Ex
B
EXPERIMENTS
We now describe the experimental methodology and results for validating our proposed method.
5.1 BASELINES
We next detail the suite of baselines we compare against. We tune baseline hyper- paremeersssssss exten- sively, with the precise sweeps and setups available in the Appendix.
Control: Baseline where we train for accuracy without regards to lower churn.
Ep Regularization: We control the stability model's predictions by simply regularizing them (independently of the ground truth label) using classical ép regularization. The loss function given by:
Le, (2,, y1) L(x, v1) + all (x:
We experiment with both & and l regularization.

---

Under review as a conference paper at ICLR 2021
Bi-tempered: This is baseline by Amid et al. (2019), , originally designed for robustness to label noise. It modifies the standard logistic loss function by introducing two tempera- ture scaling parameters t and iz. We apply their "bi-tempered" loss here, suspecting that methods which make model training more robust to noisy labels may also be effective at reducing prediction churn.
This is based on a method proposed by Fard et al. (2016) specifically for churn re- duction, uses the predicted probabilities from preliminary model smooth the training labels of the second model. We first train preliminary model f fretim using regular cross- entropy loss. We then retrain the model using smoothed labels (1 a)
Anchor:
a)v; Wi + a af (atz), thus "anchoring" on a preliminary model's predictions. In our experiments, we train one preliminary model and fix across the runs for this baseline reduce prediction churn.
Co-distillation: We use the co-distillation approach presented by Anil et al. 2018), who touched upon its utility for churn reduction. We train two identical models Mr and M2 (but subject to different random initialization) in tandem while penalizing divergence between their predictions. The overall loss is
Leadisnll (Ta; 1/) L(f (11),, w)) + [(f2(1)), vo) + (F)))))
In their paper, the authors set to be cross-entropy:
(p) (2)) = >.olog(e
(E[K]
but they note KI divergence can be used. We experiment with both cross-entropy and KI. divergence. We also tune Woodistill- the number of burn-in steps of training before turning on the regularizer.
Label Smoothing: This is the method of Szegedy et al. (2016) defined carlier in the paper. Our proposed method augments global label smoothing by leveraging the local k-NN esti- mates. Naturally, we compare against doing global smoothing only and this serves key ablation model to see the added benefits of leveraging the k-NN labels.
Mixup: This method proposed by Zhang et al. (2017) generates synthetic training examples on the fly by convex combining random training inputs and their associated labels, where the combination weights are random draws from Beta(a, a) distribution. Mixup improves generalization, increases robustness to adversarial examples as well as label noise, and also improves model calibration (Thulasidasan et al. 2019).
Ensemble: Ensembling deep neural networks can improve the quality of their uncertainty estimation (Lakshminarayanan et al. 2017 Fort et al. 2019).. We consider the simple case where m identical deep neural networks are trained independently on the same training data, and inference time, their predictions are uniformly averaged together.
5.2 DATASETS AND MODELS.
For all datasets, we do not use any data augmentation in order to guarantee that the training data used to across different trainings is held fixed. For all datasets we use the Adam optimizer with default learning rate 0.001. We use a minibatch size of 128 throughout.
MNIST: We train two-layer MLP with 256 hidden units per layer and ReLU activations for 20 epochs.
Fashion MNIST:
We use the same architecture the one used for MNIST.
SVHN: We use LeNet5 CNN(L et al. 1998) for 30 epochs on the Google Street View Housing Numbers (SVHN) dataset, where each image cropped to be 32 32 pixels.
CelebA: CelebA (Liu et al. 2018) is large-scale face attributes dataset with more than 200k celebrity images, each with 40 attribute annotations. We use the standard train and test splits, which consist of 162770 and 19962 images respectively. Images were resized to be 28 x 28 x 3. We select the "smiling" and "high checkbone" attributes and perform binary classification, training LeNet5 for 20 epochs.
Phishing: To validate our method beyond the image classification setting, we train a two- layer MLP with 256 hidden units per layer UCI Phishing dataset (Dua & Graff) 2017). which consists of 7406 train and 3649 test examples on a 30-dimensional input feature.

---

Under review as a conference paper at ICLR 2021
Dataset
Method
Accuracy %
Churn %
Churn Correct
Churn Incorrect
K-NN LS (k=10, a=1, b=0.9)
88.98 (0.33)
10.98 (0.28)
4.64 (0.29)
62.23 (1.22)
Label Smoothing (a=0.9)
87.26 (0.73)
13,46 (0.62)
5.31 (0.57)
67.2 (1.44)
Anchor (a=1.0)
87.17 (0.16)
12.48 (0.39)
5.19 (0.2)
61.66 (1.85)
SVHN
Reg (a=0.5)
88.16 (0.35)
11.85 (0.35)
5.07 (0.16)
62.73 (2.1)
& Reg (a=0.2)
74.18 (3.41)
22.89 (3.74)
9.58 (4.04)
59.36 (5.7)
Co-distill (CE, a=0.5)
87.64 (0.64)
12.46 (0.48)
5.16 (0.51)
63.82 (1.67)
Co-distill (KI, a=0.5)
87.52 (0.45)
13.01 (0.3)
5.54 (0.33)
65.44 (1.46)
Bi-tempered (f.00.5 t2=l)
88.04 (0.5)
12.03 (0.3)
5.26 (0.3)
62.48 (1.83)
Mixup (a=0.5)
89.08 (0.18)
(0.16)
(0.15)
54.75 (0.95)
Control
86.64 (0.54)
14.64 (0.51)
6.03 (0.5)
69.59 (1.32)
K-NN LS (k=5, a=0.9, b=0.9)
98.23 (0.11)
1.52 (0.12)
0.7 (0.1)
(3.39)
Label Smoothing (a=0.9)
98.15 (0.07)
1.65 (0.05)
0.71 (0.07)
50.73 (2.62)
Anchor (a=1.0)
97.72 (0.11)
(0.2)
(0.14)
64.51 (4.13)
MNIST
Eg Reg (a=0.5)
98.08 (0.1)
1.67 (0.12)
0.8 (0.08)
46.65 (3.2)
& Reg (a=0.01)
97.67 (0.29)
2.51 (0.31)
1.3 (0.27)
56.8 (2.84)
Co-distill (CE, a=0.2, Namm 2k)
98.08 (0.06)
2.08 (0.11)
0.98 (0.07)
(3.911
Co-distill (KL, a=0.05, Twamm -amm=-lb
97.98 (0.14)
2.16 (0.16)
(0.13)
59.56 (3.64)
Bi-tempered (f1=0.9, 12=1.0)
98.09 (0.2)
(0.15)
1.07 (0.14)
55.82 (4.32)
Mixup (a=0.2)
98.17 (0.04)
(0.07)
0.74 (0.04)
47.8 (2.53)
Control
97.98 (0.13)
2.28 (0.13)
0.96 (0.07)
63.36 (2.55)
k-NN (k=10, a=1, b=0.5)
88.89 (0.14)
(0.18)
3.27 (0.15)
36.26 (1.09)
Label Smoothing (s=0.8)
88.46 (0.17)
7.2 (0.46)
3.32 (0.28)
36.63 (2.02)
Anchor (a=0.9)
88.55 (0.14)
7.53 (0.45)
3.6 (0.23)
37.78 (2.29)
Fashion MNIST
82 Reg (a=0.5)
88.52 (0.19)
7.86 (0.36)
3.59 (0.18)
40.38 (1.81)
E Reg (a=0.1)
86.88 (0.35)
8.24 (0.55)
3,88 (0.41)
36.81 (2.63)
Co-distill (CE, a=0.5, 7umm
(0.21)
(0.39)
3.67 (0.3)
37.98 (1.71)
Co-distill (KL, 0.5, 2k)
88.85 (0.35)
7.83 (0.43)
3.68 (0.29)
40.59 (2.4)
Bi-tempered 007, 22=
88.7 (0.29)
7.36 (0.47)
3.5 (0.19)
37.24 (3.04)
Mixup (a=0.4)
89.17 (0.10)
6.77 (0.29)
3.23 (0.15)
35.97 (1.43)
Control
88.95 (0.26)
(0.51)
4.42 (0.4)
46,99 (2.49)
E-NN LS (k=100, b=0.1, a=9.9)
90.02 (0.11)
5,46 (0.32)
2.97 (0.18)
(1.71)
Label Smoothing (a=0.05)
89.39 (0.29)
6.77 (0.41)
3.81 (0.26)
31.67 (2.34)
Anchor (a=0.8)
89.87 (0.14)
5.57 (0.28)
3.07 (0.21)
27.66 (1.38)
CelehA Smiling
Reg (a=0.01)
89.35 (0.16)
6.85 (0.34)
3.92 (0.27)
31.62 (1.21)
f Reg (a=0.5)
89.39 (0.26)
6.71 (0.26)
3.61 (0.22)
32.48 (1.35)
Co-distill (CE, 0.5, Twam==1 =1k)
89.59 (0.29)
6.31 (0.23)
3.66 (0.3)
29.47 (1.47)
Co-distill (KL, 0.5, Nham -2k
89.57 (0.22)
6.1 (0.23)
3.34 (0.26)
29.66 (1.47)
Bi-tempered 00,9, l2=2.)
89.88 (0.18)
6.44 (0.31)
3.56 (0.19)
31.96 (1.96)
Mixup (a=0.2)
89.71 (0.14)
(0.12)
3.51 (0.12)
29.37 (0.66)
Control
89.67 (0.19)
7.3 (0.45)
4.06 (0.27)
35.34 (2.35)
k-NN LS (k=1000, b=0.1, a=0.9)
84.48 (0.21)
7.7 (0.29)
4.64 (0.27)
24.44 (0.98)
Label Smoothing (a=0.005)
83.73 (0.17)
8.68 (0.46)
S.2 (0.35)
26.61 (1.28)
Anchor (a=0.9)
84.48 (0.2)
(0.39)
4.77 (0.22)
25.44 (1.58)
CelebA High
Eg Reg (a=0.001)
83.6 (0.14)
9.06 (0.32)
5.41 (0.24)
27.66 (1.03)
E Reg (a=0.01)
83.59 (0.26)
8.43 (0.23)
4.93 (0.23)
26.14 (1.16)
Checkbone
Co-distill (CE, a=0.5, #lkm=1k)
84.08 (0.21)
8.96 (0.37)
5.33 (0.36)
28.11 (0.88)
Co-distill (KT., a=0.5, mlmm=
84.31 (0.08)
8.57 (6.
5.06 (0.13)
27.39 (0.47)
Bi-tempered (f1=0.5, 12=4)
83.92 (0.13)
7.84 (0.32)
4.75 (0.21)
24.01 (1)
Mixup (a=0.4)
84.53 (0.14)
7.92 (0.47)
4.69 (0.31)
25.53 (1.54)
Control
83.93 (0.56)
10.18 (0.93)
6.2 (0.89)
31.1 (2.22)
I- (k=500, a=0.8, b=0.9)
96.69 (0.09)
1.04 (0.21)
0.54 (0.14)
15.81 (3.52)
Label Smoothing (a=0.8)
96.63 (0.09)
1.26 (0.26)
(0.17)
18.8 (3.42)
Anchor (a=0.9)
96.02 (0.25)
2.33 (0.25)
1.8 (0.15)
31,58 (5.11)
Phishing
& Reg (a=0.5)
96.51 (0.12)
1.35 (0.3)
0.7 (0.21)
19.37 (4)
E Reg (a=0.5)
95.38 (0.18)
1.48 (0.34)
0.83 (0.24)
14.95 (4.08)
Co-distill (CE, a=0.2, Mwam=
96.02 (0.19)
1.45 (0.26)
0.83 (0.21)
16.72 (4.13)
Co-distill (KL, a=0.001, - 11k
95.94 (0.33)
(0.2)
0.65 (0.18)
20.95 (6.14)
Bi-tempered =0,9, 12=1.0)
96.26 (0.37)
2.32 (0.69)
1.23 (0.53)
30.19 (8.51)
Mixup (a=0.1)
96.22 (0.23)
1.80 (0.33)
1.05 (0.28)
21.53 (4.25)
Control
96.3 (0.32)
2.25 (0.59)
1.21 (0.38)
29.05 (7.93)
Table 1: Results across all datasets and baselines under optimal hyperparameter tuning (settings shown). Note that we report the standard deviation of the runs instead of standard deviation of the mean (i.e. standard error) which is often reported instead. The former is higher than the latter by factor of the square root the number trials (10).
7

---

Under review as a conference paper at ICLR 2021
5.3 EVALUATION METRICS AND HYPERPARAMETER TUNING
For each dataset, baseline and hyper-parameter setting, we run each method on the same train and test split exactly 5 times. We then report the average test accuracy averaged across every possible pair (i,j) of runs (10 total pairs). To give a more complete picture of the sources of churn, we also slice the churn by the whether or not the test predictions of the first run in the pair were correct. Then, lowering the churn on the correct predictions is desirable (i.c. if the base model is correct, we clearly don't t want the predictions to be changing), while churn reduction on incorrect predictions is less relevant (i.e. if the base model was incorrect, then it may be better for there to be higher churn- however at the same time, some examples may be inherently difficult to classify or the label is such an outlier that we don't I expect an optimal model to correctly classify in which case lower churn may be desirable). This is why in the results for Table [] we bold the best performing baseline for churn correct examples, but not for churn on incorrect examples.
well as the test set churn
In the results (Table D for each dataset and bascline, we chose the optimal hyperparameter setting by first sorting by accuracy and choosing the setting with the highest accuracy, and if there were multiple settings with very close to the top accuracy (defined as within less than 0.1% difference in test accuracy), then we chose the setting with the lowest churn among those settings with accuracy close to the top accuracy. There is often no principled way to trade-off the two sometimes competing objectives of accuracy and churn (e.g. Cotter al.) (2019) offer a heuristic objectives in a more balanced manner on the Pareto frontier). However in this case, biasing towards higher accuracy is most realistic because in practice, when given choice between two models, it's usually best to go with the more accurate model. Fortunately, we will see that accuracy and churn are not necessarily competing objectives and our proposed method usually gives the best result for both simultaneously.
trade off the two
5.4 RESULTS
We see from T mixup and our method, k-NN label smoothing, are consistently the most competitive; mixup outperforms on SVHN and Fashion MNIST while l--N label smoothing outper- forms on all the remaining datasets. Notably, both methods do well on accuracy and churn metrics simultaneously, suggesting that there is no inherent trade-off between predictive performance and churn reduction. Due to space constraints, ablations on SVHN for our method's hyperparameters (a, b, and k)), along with results for the ensemble baseline can be found in the Appendix. While we found ensembling to be remarkably effective, it does come with higher cost (more trainable param- eters and higher inference cost), and we discourage direct comparison with other methods.
6 CONCLUSION
Modern DNN training is a noisy process: randomization arising from stochastic minibatches, weight initialization, and data preprocessing techniques can lead to models with drastically different predic- tions on the same datapoints when using the same training procedure- and this phenomenon happens even when all the models attain similarly high accuracies.
Reducing such prediction churn is important in practical problems as production ML. models are constantly updated and improved on. Since offline metrics usually can only serve as proxies to the live metrics, comparing the models in A/B tests and live experiments oftentimes must involve manual labeling of the disagreements between the models making it a costly procedure. Thus, controlling the amount of predictive churn can be crucial for more efficiently iterating and improving models in production setting.
Despite the practical importance of this problem, there has been little work done in the literature on this topic. We provide one of the first comprehensive analyses of reducing predictive churn arising from retraining the model on the same dataset and model architecture. We show that numerous meth- ods used for other goals such as learning with noisy labels and improving model calibration serve as reasonable baselines for lowering prediction churn. Moreover, we propose a new technique, A-NN label smoothing, which is shown to be a principled approach leveraging a local smoothing from the deep NN-N labels to enhance the global smoothing from the vanilla label smoothing procedure. We further show that it often outperforms the baselines across a range of datasets and model architec- tures.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Ehsan Amid, Manfred KK Warmuth, Rohan Anil, and Tomer Koren. Robust bi-tempered logistic loss based on bregman divergences. Advances in Neural Information Processing Systems, pp. 14987-14996, 2019.
Rohan Anil, Gabriel Pereyra, Alexandre Passos, Robert Ormandi, George E Dahl, and Geoffrey E Hinton. Large scale distributed neural network training through online distillation. arXiv preprint arXiv:: 1804.02443333 2018.
Dara Bahri, Heinrich Jiang, and Maya Gupta. Deep k-nn for noisy labels. ICMI, 2020.
Kamalika Chaudhuri and Sanjoy Dasgupta. Rates convergence for the cluster tree. In Advances in neural information processing systems, pp. 343 351, 2010.
Kamalika Chaudhuri and Sanjoy Dasgupta. Rates of convergence for nearest neighbor classification. In Advances in Neural Information Processing Systems, pp. 3437-3445, 2014.
Andrew Cotter, Heinrich Jiang, Maya R Gupta, Serena Wang, Taman Narayan, Seungil You, and Karthik Sridharan. Optimization with non non-differentiable constraints with applications to faimess, recall, churn, and other goals. Journal of Machine Learning Research, 20(172):1-59, 2019.
Thomas M Cover. Rates of convergence for nearest neighbor procedures. Proceedings of the Hawaii International Conference on Systems Sciences, pp. 413-415, 1968.
Lue 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.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. httthtt:///acchii
ics uci edu/ml
Mahdi Milani Fard, Quentin Cormier, Kevin Canini, and Maya Gupta. Launch and iterate: Reducing prediction churn. In Advances in Neural Information Processing Systems, pp. 3179-3187, 2016.
Evelyn Fix and Joseph L Hodges Jr. Discriminatory analysis-nonparametri discrimination: consis- tency properties. Technical report, California Univ Berkeley, 1951.
Stanislav Fort, Huiyi Hu, and Balaji Lakshminarayanan. Deep ensembles: A loss landscape per-
spective. arXiv preprint
2019.
Gabriel Goh, Andrew Cotter, Maya Gupta, and Michael P Friedlander. Satisfying real-world goals with dataset constraints. In Advances in Neural Information Processing Systems, pp. 2415-2423, 2016.
Bo Han, Quanming Yao, Xingrui Yu, Gang Niu, Miao Xu, Weihua Hu, Ivor Tsang, and Masashi Sugiyama. Co-teaching: Robust training of deep neural networks with extremely noisy labels. In Advances in neural information processing systems, pp. 8527-8533 2018.
H. Jiang, B. Kim, M. Y. Guan, and M. R. Gupta. To trust not to trust classifier. In 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.
Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predic- tive uncertainty estimation using deep ensembles. In Advances in neural information processing systems, pp. 6402-6413, 2017.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEFE, 86(11):2278-233) 1998.
Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Large-scale celebfaces attributes (celeba) dataset. Retrieved August, 15:2018, 2018.

---

Under review as a conference paper at ICLR 2021
Eran Malach and Shai Shalev-Shwartz Decoupling" when to update" from" how update". In Advances in Neural Information Processing Systems, pp. 960-970, 2017.
Rafael Müller, Simon Korbllihh, and Geoffrey E Hinton. When does label smoothing help? In Advances in Neural Information Processing Systems, pp. 4694-4703, 2019.
Nicolas Papernot and Patrick McDaniel. Deep k-nearest neighbors: Towards confident, interpretable and robust deep learning. arXiv preprint arXiv: 1803. 047600000465,. 2018.
Henry WJ Reeve and Ata Kaban. Fast rates for kNN classifier robust to unknown asymmetric label noise. arXiv preprint arXiv:1906.04542. 2019.
Aarti Singh, Clayton Scott, Robert Nowak, et al. Adaptive Hausdorff estimation of density level The Annaly of Statistics, 37($BB):760-27782 2009.
Guocong Song and Wei Chai. Collaborative learning for deep neural networks. In Advances in Neural Information Processing Systems, pp. 1832-18444 1841, 2018.
Charles Stone. Consistent nonparametric regression. The Annals of Statistics, pp. 595-620, 1977.
Christian Szegedy. Vincent Vanhoucke, Sergey loffe, Jon Shlens, and Zbigniew Wojna. Rethink- ing the inception architecture for computer vision. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2818-2826, 2016.
Sunil Thulasidasan, Tanmoy Bhattacharya, Jeff Bilmes, Gopinath Chennupati, and Jamal Mohd- Yusof. Combating label noise in deep learning using abstention. arXiv preprint arXiv: 1994,444 2019.
Alexandre B Tsybakov et al. On nonparametric estimation of density level sets. The Annals of Statistics, 25(3):948-966 969, 1997.
Hongyi Zhang, Moustapha Cisse, Yann N Dauphin, and David Lopez-Paz. mixup: Beyond empirical risk minimization. arXiv preprint arXiv:17/0.094422 2017.
Ying Zhang, Tao Xiang, Timothy M Hospedales, and Huchuan Lu. Deep mutual learning. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 4320- 4328, 2018
Xiatian Zhu, Shaogang Gong, al. Knowledge distillation by on-the-fly native ensemble. In Ad- vances neural information processing systems, pp. 7517-7527, 2018.
10

---

Under review as a conference paper at ICLR 2021
A
PROOFS
For the proofs, we make use of the following result from Jiang 2019) which bounds the number of distinct k-NN on the sample across all
Lemma (Lemma 3 of Jiang (2119). Let M be the number of distinct k-NN sets over X, that is, M = (x)(x) E H. Then M < D.
Proof of Theorem
We have by triangle inequality and the smoothness condition in Assumption
that:
Th (z) - n)(x) - Σ (m)(,t) n(x)) 1 [ E Ne(x))
+ Σ (m ((x))-
[ E Nx(x)] [Na(x)]
[Nx(z))
1
aa E Nn(x)]
S C. (2)
(3: ma;)))
(N+(2))
We now bound each of the two terms separately.
1/D
To bound (x())), let w------PX..
We have P(B(xrr)) winf winlgeB(arrn px (x()')
"Dr 2 wpx.oUprD 2k where P the distribution function w.r.t. px- By Lemma of Chaudhuri & Dasguptal (2010) and the condition on k, it follows that with probability 5/2, uniformly in E X. (i,, T)nx 2 k, where X is the sample of feature vectors, Hence, [x(x) <r for all x E X uniformly with probability least 1 6/2.
Define & == y: n(x;). Then, we have that -1 S & S 1 and thus by Hoeffding's inequality, we
have that A, = Σ (v: m)x))) Nz = & [Na(2)] (x))
(x()) satisfies P([Aa) > t/k) S
2 exp (-22/2k) Then setting /2k (og(4D/8) + +DDDDl log(()) gives
(DD/))/)) + 2D log(n)
8
A 2
S 2D n
k
By Lemma 3 of Diang 2019). the number unique random variables Ag across all æ X bounded by D -n". Thus, by union bound,
2og (D) + 2D log(n)) s 8/2.
P sup |A xEX
The result follows.
Proof of Theorem Let X be the sampled feature vectors and let X. Define K(x)
[X n B(x, (- We have:
[n<( 7a (z) S (x) - nx(2)) (mer))))))))))))) - ()))))
We bound each the two terms separately. We have
I (x) - k|
1|x e B(x,r(x))] Σ xEX
By Hoeffding's inequality we have
P((K((z) ka 2 (- < 1eexp(-2(m1)
Choosing / -
()g(4D/6)+ log(n)
gives us
2n
IP
|k' [k'(x)) kl 2 (log(4D/0) + Dlog()))
2D n
11

---

Under review as a conference paper at ICLR 2021
Dataset (m=5)
Accuracy ( (%)
Churn (%)
Churn Correct
Churn Incorrect
SVHN
90.34 (0.31)
6.61 (0.19)
2.75 (0.28)
43.12 (1.49)
MNIST
98.5 (0.07)
0.94 (0.14)
0.44 (0.09)
33.74 (4.39)
Fashion MNIST
89.71 (0.12)
4.05 (0.14)
1.85 (0.05)
23.16 (1.29)
CelebA Smiling
90.56 (0.09)
3.35 (0.16)
1.82 (0.11)
17.95 (0.99)
CelebA High Checkbone Phishing
85.12 (0.16)
4.95 (0.2)
2.87 (0.1)
16.81 (1.24)
96.11 (0.06)
0.54 (0.08)
0.29 (0.08)
6.77 (1.31)
Table 2: Ensemble results for all datasets. In all settings, the optimal m (number of subnerworks) We see that compared to the other methods presented, ensembling does well in both predictive performance and in reducing churn. It does come at cost, however: the model is effectively 5 times larger, making both training and inference more expensive.
By Lemma 3 of Jiang (2019). the number of unique sets of points consisting of balls intersected with the sample is bounded by D D and thus by union bound, we have with probability least 1 - 8/2:
sup (x)) kl S V (log(4D/0) Dlog(n)). #et
We now have
(x) - (x))
- h (xx)
min (k:, + min k k((x)
11: - -x-((x))
2 log (D/5)/1)11 + 2D log(n)
k [x))
B.n
where the first inequality follows by comparing the difference contributed by the shared neighbors among the k-NN and (<x)NNN (first term RHS) and contributed by the neighbors that not shared (second term on RHS).
For the second term, define A, := X X B(g, For any x' sampled from (z)),, have that the expected label is (x)) Since (a( (x) the mean label among datapoints in Ag. then have by Hoeffding's inequality that
P(n (x) π)(=)) 2 (xx) t) < 2exp (-t/2k).
Then setting t = V2k' Ilg 4D/8) + D (og((n) gives
(x) - (xx)) log( (DD/)) + 2D log(n)
k(xx)
2D nD
By Lemma of Jiang 2019) the number of unique sets A₂ across all x E X is bounded by D nnP Thus, by union bound, with probability at least 8/2L
2 logg (DD/)) + 2D log(n)
(e( - [)]=)) <
kx(x)
The result follows immediately for n sufficiently large.
B ENSEMBLE RESULTS
In Table 2 we present the experimental results for the ensemble baseline. The method performs remarkably well, beating the proposed method and the other baselines on both accuracy and churn reduction across datasets. We do note, however, that ensembling does come at a cost which may prove prohibitive in many practical applications. Firstly, having m times the number of trainable parameters, training time (if done sequentially) takes m times as long, as does inference, since each subnetwork must be evaluated before aggregation.
12

---

Under review as a conference paper at ICLR 2021
Fixed
Ablated
Accuracy (%)
Churn (%)
Churn Correct
= 10, a=
b b
86.54 (0.67)
13.43 (0.58)
5.86 (0.57)
b = 0.05
87.37 (0.38)
12.22 (0.31)
5.34 (0.31)
b
86.94 (0.65)
13.41 (0.39)
5.69 (0.57)
b 0.5
88.48 (0.52)
11.12 (0.5)
4.37 (0.35)
b 0.9
88.98 (0.33)
10.98 (0.28)
4.64 (0.29)
k= 10, a 0.5
b= 0
84,44 (2.43)
(..3992.3)
6.73 (2.47)
79.64 (3.1)
(5.15)
10.28 (4.06)
b=0.1
79.88 (2.63)
$3.5993.59
10.25 (1.85)
b=5
84.44 (2.54)
14.33 (1.78)
6.52 (2.83)
b 0.9
81.06 (2.35)
20.53 (4.52)
8.68 (3.36)
k= 10, b= 0.9
a = 0.005
73.91 (3.01)
28.02
13.85 (4.82)
0.01
72.41 (4.86)
75.57
13.66 (7.01)
a 0.02
72.03 (1.79)
31.25 (7.25)
17.26
a 0.05
73.2
30.41 (6.2)
17.96 (6.04)
a 0.1
75.28 (1.98)
23.96 (4.76)
10.13 (4.25)
a 0.5
81.06 (2.35)
20.53 (4.52)
8.68 (3.36)
0.8
85.99 (0.73)
13.76 (0.75)
6 (0.83)
a = 0.9
87.27 (0.41)
13.72 (0.41)
5.68 (0.32)
1.0
88.98 (0.33)
10.98 (0.28)
4.64 (0.29)
k= 10, b = 0.5
a = 0.005
71.45 (3.81)
24.37)
(5.46)
0.01
74.73 (6.24)
25.24 (3.84)
8.28 (4.35)
a 0.02
73.59 (3.72)
29.47 (6.89)
17.52 (6.13)
0.05
74.17 (3.88)
20.26 (4.15)
5.79 (3.7)
a 0.1
72.43 (2.75)
25.77 (5.41)
13.42 (4.89)
a 0.5
84.44 (2.54)
14.33 (1.78)
6.52 (2.83)
0.8
87.26 (0.41)
1..6
4.62 (0.21)
a = 0.9
86.85 (0.54)
12.54 (0.44)
5,25 (0.48)
1.0
88.48 (0.52)
11.12 (0.5)
4.37 (0.35)
a= 1, b= 0.9
k 10
88.98 (0.33)
10.98 (0.28)
4.64 (0.29)
k 100
88.19 (0.19)
11.15 (0.23)
4.67 (0.17)
k 500
87.98 (0.62)
11.33 (0.35)
4.72 (0.55)
Table 3: Ablation on k-NN label smoothing's hyperparameters: b, and k for the SVHN dataset.
C ABLATION STUDY
In T report SVHN results ablating k--N label smoothing's hyperparameters: k. and b. We observe the following trends: with fixed to 1, both accuracy and churn improve with increasing and similar relationship holds increases with b fixed to 0.9. Lastly, both key metrics stable with respect to k.
D HYPERPARAMETER SEARCH
Our experiments involved performing grid search over hyperparameters. We detail the search ranges per method below.
k-NN label smoothing.
k E [5, 10, 100, 500]
a [0.005, 0.01, 0.2, 0.05, 02,,00,0,,0,,,,,,,,,,,,,,,,,,,,,
[0, 0.05, 0.1,0,..
Anchor.
a [0.005, 0.01, 0.02, 0.05, 0.1, 0.5, 0.8, 0.9, 1.0)
13

---

Under review as a conference paper at ICLR 2021
1, l2 Regularization.
a [0.001, 0.01, 0.05, 0.1,
Co-distill
[0.001, 0.01, 0.05, 0.1, 0.5,
Nwarm E [0000
Bi-tempered
1 [0.3, 0.7,
l [1., 2., 3., 4.]
Mse always set to 5.
Mixup
a E 0.4,0,
Ensemble
E [3,
14


Reviews:
[{"review_id": "aaTYXO-9Ah", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper condsidered the problem of churn reduction in DNN training,  and proposed to  utilize the k-NN predictions to smooth the labels results. Theorectical  analysis  and empirical  comparison results were given to validate the proposed  idea. \n\nOverall, the paper is well written. Main ideas and key contributions are clearly conveyed.  In my opinion, the studied churn reduction problem is of considerable interest in both academical and practical aspects.  \n\nMy main concerns are about the contribution significance and practical effectiveness of the proposed method for general problems. While I'm not an expert on theoretical knn analysis, from my understanding, the thoeretical analysis seems straightforward extension/application of previous work, which may limit the technical contribution of this paper. \n\nSecondly,  for the empirical validation, it's not clearly explained how the experiment setting, e.g., the model architechture, the train epochs,  the hyperparamter selection criteria, are designed, which hurts the reliability of the experiment results. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "RQRzIksaC6", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The main objective of this paper is to reduce the model stability, in particular, the prediction churn of neural networks. The prediction churn is defined as the changed prediction w.r.t. model randomness, e.g. multiple runs of networks. The paper proposed to use a interpolated version of global label smoothing and k-NN label smoothing. Theoretically it is shown that k-NN rule converges to the Bayes rule when k is small, and converges to a kernel smoothed version of Bayes rule when k is linear in n. Experiments are conducted that show the proposed method gives highest test accuracy and lowest churn rate in most cases.\n\nThe problem is interesting and the the paper is writen clearly. However, I think it is a little bit tricky that the main objective of this paper is not well addressed, and the originality seems limited. \n\n1) Originality: The idea of using k-NN in label smoothing has been proposed in (Dara Bahri, Heinrich Jiang, and Maya Gupta. Deep k-nn for noisy labels. ICML, 2020), and I don't find much difference with the method in this paper (except for the interpolation with global smoothing). That paper, though does not has 'neural networks' in the title, also reported their experiments on deep learning models. Therefore, I think the submission is not very original in terms of methodology.\n\n2) Theory: The main objective of the paper is to deal with model stability, i.e. the churn rate. Thus, I would expect some results particularly regarding that aspect. However, the theorem 1 and 2 both only state the relationship between the k-NN rule and Bayes rule. What's the relatioinship between these results and the churn rate? If such results (at least any insight) can be discussed more, the paper would be better. The current theorems, to some extend, are like independent results on k-NN theory, stating that k-NN rule converges to the Bayes rule, which is already known in literature (perhaps under different assumptions). Taking a closer look I found that theorem 1 is actually pretty similar to the results provided in (Deep k-nn for noisy labels, ICML'20). I suggest the authors to highlight the difference and signifiacnce of the theorems, compared to many existing convergence restuls in literature. Also, the results are all for Definition 2, while Definition 3 is actually used. What can we say about Definition 3?\n\n3) Experiments: I suggest also provide loss and accuracy curves in figures, instead of only the test accuracy at the end. I'm aware that two more parameters, a and b, are fine tuned in the proposed method. Since only the best result is reported, I'm wondering how does it perform when a and b is not tuned very carefully? For example, it might be convenient to set some default a and b value. It would be helpful to see some results (on different a and b) in the appendix.\n\nOverall, in my understanding the key of this submission is to argue that k-NN label smoothing helps with model stability, on neural networks (otherwise the originality would be very poor). However, the discussion and results on this respect seems insufficient. Though the empirical performance is OK, I think the paper needs to improve the theoretical results and provide more insight and implication on model stability.\n\n===================================================\n\nI have read the author response, and I have to downgrade my score to 3 because of the validity of experiments. A minor issue is that the theoretical result is not impressive since the technique is basically the same as ICML'20 paper, except that expectation is taken here which makes things easier.\n\nMy major concern is about the experimental results. The additionally provided Table 3 makes me question the implementation of the experiments. For example, a=0.005 should be very close to the true label (by Definition 3), but the accuracy is only around 70%. For LeNet on SVHN dataset, the accuracy of training with true label y should approach 90%, e.g. see the report in [Coverage Testing of Deep Learning Models using DatasetCharacterization, 2019]. Indeed, currently best model would give <5% test error. Such a big gap is questionable. The only reason I can think of is that this is a typo and larger 'a' should actually mean more weight on y. Then, the results say that a=1 (corresponds to the true label without smoothing) gives best performance (around 90% which makes sense). However, this actually means that the proposed method is ineffective. In any case, for me the validity of experiments is poor.\n\nI'm fairly confident in my evaluation. However, if any reviewer or area chair points out that I made a mistake, please kindly correct me and I will re-evaluate the work. Currently, since the experimental results are questionable for me, I would suggest a rejection of this paper. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "RM3DvuQX9w", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##########################################################################\nSummary: \n\nDNNs from multiple runs each of which follows the same training procedure produces different predictions that lead to prediction churn despite the higher accuracies of the deep models. The paper proposes a k-NN label smoothing approach in order to reduce the churn as opposed to the traditional label smoothing.   \n\n##########################################################################\n\nReasons for score: \n \nOverall, I vote for below the acceptance threshold in its current form. The idea of improving the prediction churn is encouraging. The k-NN label smoothing with theoretical guarantees for the bounds sounds interesting. However, the paper has serious drawbacks in the experimental evidence. The paper requires some proofreading. The state-of-the-art on label smoothing is not upto date. My concerns are further detailed in the comments below. Hopefully the authors will address these concerns in the rebuttal period. \n##########################################################################\n\n\nPros:\nOverall, the paper is written reasonably fine with a few grammatical errors, easy to follow and understandable. \n\nThe motivation for the paper comes from the inherent noise in random initialization, batch ordering, data augmentations and/or other preprocessing tricks. \n\nThe L_{\\infinity} bounds with uniform guarantee is a positive compared to the average case in the literature.\nk-NN label smoothing is interesting\n\nCons:\n“... even when the trained models all attain high accuracies” does not flow well, correct it.\n\n“... labels results in a new and principled ...” contains a mistake in plural and/or tense, please correct\n\nNot clear why preprocessing is inherently noisy. Better point out to a specific preprocessing or a class of those kinds of techniques. Because, for example the normalization of data to 0 mean and 1 standard deviation is proved to smoothen the optimization plain and is more useful rather than being so bad on the loss surface.\n“... train a model the model on the soft labels ...” does not flow well, correct it.\n\n“... rather than a the pure global ...”, needs a fix.\n\nOne of the reasons from the motivation behind the churn is data augmentations. However, none of the augmentations are experimented in the results section.\n\nIn fact, the recent augmentation, MixUp is supposed to perform better in terms of calibration or improving the confidence in predictions. \n\nZhang, H., Cisse, M., Dauphin, Y.N. and Lopez-Paz, D., 2018, February. mixup: Beyond Empirical Risk Minimization. In International Conference on Learning Representations.\n\n“Guo, C., Pleiss, G., Sun, Y. and Weinberger, K.Q., 2017, July. On Calibration of Modern Neural Networks. In International Conference on Machine Learning (pp. 1321-1330).”\n\n“Sunil Thulasidasan, Tanmoy Bhattacharya, Jeff A. Bilmes, Gopinath Chennupati, Jamal Mohd-Yusof: Combating Label Noise in Deep Learning using Abstention. ICML 2019: 6234-6243.”\n \nThulasidasan et al, showed that MixUp returns well calibrated confidence scores compared to label smoothing. In which case, it might be worth comparing against the state-of-the-art rather simply the label smoothing. Note that Mixup has a kind of label smoothing effect.\n \nMore recent techniques such as AugMix and Deep Ensembles are said to be better in producing highly confident predictions. \n \nHendrycks, D., Mu, N., Cubuk, E.D., Zoph, B., Gilmer, J. and Lakshminarayanan, B., 2019. Augmix: A simple data processing method to improve robustness and uncertainty. arXiv preprint arXiv:1912.02781.\n \n“Lakshminarayanan, B., Pritzel, A. and Blundell, C., 2017. Simple and scalable predictive uncertainty estimation using deep ensembles. In Advances in neural information processing systems (pp. 6402-6413).”\n \nFort, S., Hu, H. and Lakshminarayanan, B., 2019. Deep ensembles: A loss landscape perspective. arXiv preprint arXiv:1912.02757.\n \nThe question is does the churn happen even with the ensemble approaches, which is supposed to produce stable predictions? It will be interesting, if the motivation behind this paper is to show that these more advanced models still suffer from the churn problem and then show the reductions, etc. \n \nThe benchmarks are small, may be showing the method working on ImageNet scale data will strengthen the paper.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "FunrtNCMGyL", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "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": "My enthusiasm for this paper remains fairly high after reading through the other reviews and responses: I think the results (in the main body of the paper) look strong. In particular, this approach is competitive with MixUp, and I prefer this simpler label-only approach to MixUp. I don't think this work is duplicative with the ICML 2020 deep knn paper cited by another reviewer (that paper filters out noisy examples, rather than smoothing labels). And I think the theory is novel in its synthesis oof KNN theory with label noise.\n\nHowever, I am unnerved by something that Rev 2 pointed out about the ablation results in the new Table 3 in the appendix: in Definition 3, the weight given to the assigned (\"true\") label is $(1-a)$, so we'd expect to see higher (or at least competitive) accuracy for lower values of $a$ when label noise is not too severe. For SVHN, at least, this seems like it should be true since we know the SOTA accuracy is in the 90s. \n\nInstead we see the highest accuracy is for the highest values of $a$. That makes me suspect the order is reversed. However, if this method works, we should expect to see lower churn for higher values of $a$, which we do, which would indicate that things are in the right order. This apparent contradiction is disconcerting since some of these numbers are cited in the comparison in Table 1 in the main paper.\n\nIn an ideal world, it'd be nice to have one more round of discussion with the authors about Table 3. Because it was added to the appendix late in the review process and no further discussion is possible, I am electing to leave my score as is. However, I urge the authors to take a look at Table 3 and verify that there is no error. If it is possible for the authors to post a public comment and/or contact the AC with an explanation, they should do so.\n\nI'm also lowering my confidence to reflect my uncertainty about Table 3.\n\n-----\n\nThis submission studies the problem of \"prediction churn,\" in which independently trained models possessing equivalent accuracy produce different predictions for individual (usually novel, sometimes out-of-sample) samples. It proposes a solution built around a \"local\" K-nearest neighbor (KNN) variant of \"label smoothing\" and demonstrates in fairly thorough experiments that it outperforms (roughly) half a dozen alternatives. The intuition for its success is that KNN label smoothing reduces label noise (but with greater precision than global smoothing). The paper backs up this argument with theory from KNN, providing a uniform bound between the KNN smoothed label and the Bayes optimal label.\n\nI enjoyed this paper, and I tentatively support its inclusion in the conference. The manuscript conveniently summarizes its claims in the introduction:\n1. A (first of its kind?) thorough empirical comparison of (roughly) half a dozen approaches (plus some variants) to reducing prediction churn, including several that were introduced in other contexts, as well as the proposed approach.\n2. A proposed solution to churn based on a local (KNN) variant of label smoothing that consistently outperforms the included baselines in the described experiments.\n3. A non-trivial theoretical analysis that supports intuitive explanation for the success of KNN label smoothing.\n\nIn my view, these claims are justified, though I should add some caveats. I cannot fully substantiate (1), but a cursory skim of the referenced literature and a brief Google Scholar search suggest that this is indeed the first such direct empirical comparison of the included baselines specifically for the problem of churn. For (2), the proposed method is clever and well-motivated and appears effective in practice. For (3), I was not previously familiar with the recent theory on KNN models (especially Jiang 2019), and I did not rigorously check either Theorem or the proofs in the appendix.\n\nThe introduction does a nice job of motivating the problem of prediction churn, which I suspect will resonate with practitioners. The text argues (correctly, in my opinion) that this problem can be highly vexing -- and costly -- in production machine learning settings but has received proportionally little attention in the academic literature. \n\nThe proposed method is a non-trivial extension of an existing method (global label smoothing) that was simpler and designed to address calibration, rather than churn. The extension is intuitive but does not immediately follow from previous work: mix hard labels with a more informative distribution based on each data point's neighborhood of samples, rather than a uniform distribution. The discussion and theoretical analysis provide context for previous work and deepens understanding of, in particular, label smoothing.\n\nThe experiments are well-designed and thorough: they include five different datasets and do a rigorous job of tuning each model sufficiently to ensure a fair comparison. The proposed churn \"metrics\" are well-motivated and sensible. I especially like the separate quantifications of correct and incorrect churn rates. The proposed method consistently outperforms the included alternatives, though admittedly not always by a substantive margin. As the paper observes, it was heartwarming to see that for at least the studied datasets, there is not always a meaningful tradeoff between accuracy and churn.\n\nThe theoretical analysis is very interesting, especially its connection to existing theory for KNN models (and my non-expert interpretation is that this research in fact builds on previous results). I especially appreciated the last two paragraphs of Section 4.1, which provide an intuitive interpretation of the theory in terms of reducing label noise in a way that should be optimal in the limit under non-onerous conditions.\n\nMy enthusiasm for the submission is somewhat diminished by a handful of flaws (none fatal), mostly to do with clarity of exposition or missing details. These flaws should be addressable by the authors.\n\nFor one, it is not entirely clear from the body of the paper in which space the nearest neighbors are computed: the original feature space, an intermediate representation from a hidden layer of a neural net, etc. Line 4 of Algorithm 1 suggests the neighbors are computed using the logits $z_i$, but this is not reinforced in the prose, nor in the theoretical analysis. It's a crucial implementation detail and should be stated clearly. If there is a choice, then the pros and cons of each should be discussed explicitly.\n\nOn a that note, if there is a choice (inputs, hidden layers, logits), then this suggests an additional experiment comparing results for each.\n\nThe theory is dense, particularly for readers not previously familiar with the KNN literature. The prose at the end of Section 4.1 helps, but there is a still a gap between the bounds shown in the Theorems and the prose explanation. I would suggest adding some additional language that explicitly connects the intuitive conclusion to the bounds themselves.\n\nFinally, the fact that 4/5 datasets are images leaves me to wonder whether and how these results generalize to other domains. This becomes even more important if the label smoothing is based on nearest neighbors in the original input space: designing a distance for, e.g., a mix of continuous and categorical features is tricky. According to the UCI repository, the Phishing dataset is relatively low dimensional (30 features) and homogeneous. I would suggest adding at least one dataset with higher dimensional, sparse or heterogeneous input spaces, which are common in the production machine learning settings that the manuscript uses to motivate this work.\n\nMy initial recommendation is to accept this submission, but I reserve the right to revise my rating up or down, especially if the other reviewers discover key flaws that I missed. I urge the authors to seize the opportunity to improve the manuscript.\n\nI have a few lingering questions:\n- How sensitive is this method to choice of K?\n- How sensitive is this method to the choice of similarity/distance or \"quality\" of the nearest neighbors? Suppose you start injecting spurious (or \"adversarial\") neighbors?\n- Since the text connects label smoothing to label noise, how robust is this method to (a) higher rates of noise and (b) non-uniform label noise, e.g., class conditional or even feature-dependent noise?\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a k-NN smoothing procedure for dealing with the problem of churn prediction. The idea is interesting and is based on theoretical foundations. The reviews have raised some limitations in the significance and in the experiments. The rebuttal provided by the authors have addressed some concerns. However, the new experimental evaluation have raised new concerns about the results, in particular with respect to results given in Table 3. Some typo may exist, but even some doubts remain on the experimental evaluation and results and thus on the effectiveness of the results.
Authors' rebuttal was too late to allow another round of discussion.
Considering the current concerns and uncertainties on the paper, I have to recommend rejection.
Decision: Reject