Benefit of Interpolation in Nearest Neighbor Algorithms
Authors: Yue Xing
Qifan Song
Guang Cheng
Venue:  (2020)
Keywords: Data Interpolation
Multiplicative Constant
W-Shaped Double Descent
Nearest Neighbor Algorithm

Abstract: The over-parameterized models attract much attention in the era of data science and deep learning. It is empirically observed that although these models, e.g. deep neural networks, over-fit the training data, they can still achieve small testing error, and sometimes even outperform traditional algorithms which are designed to avoid over-fitting. The major goal of this work is to sharply quantify the benefit of data interpolation in the context of nearest neighbors (NN) algorithm. Specifically, we consider a class of interpolated weighting schemes and then carefully characterize their asymptotic performances. Our analysis reveals a U-shaped performance curve with respect to the level of data interpolation, and proves that a mild degree of data interpolation strictly improves the prediction accuracy and statistical stability over those of the (un-interpolated) optimal $k$NN algorithm. This theoretically justifies (predicts) the existence of the second U-shaped curve in the recently discovered double descent phenomenon. Note that our goal in this study is not to promote the use of interpolated-NN method, but to obtain theoretical insights on data interpolation inspired by the aforementioned phenomenon.

Under review as a conference paper at ICLR 2020
BENEFIT OF INTERPOLATION IN NEAREST NEIGHBOR ALGORITHMS
Anonymous authors Paper under double-blind review
ABSTRACT
The wver-parameterized models attract much attention in the era of data science and deep learning. It is empirically observed that although these models, e.g. deep neural networks, over-fit the training data, they can still achieve small testing er- ror, and sometimes even outperform traditional algorithms which are designed to avoid over-fitting The major goal of this work to sharply quantify the benefit of data interpolation in the context of nearest neighbors (NN) algorithm. Specif- ically, we consider class of interpolated weighting schemes and then carefully characterize their asymptotic performances. Our analysis reveals a U-shaped per- formance curve with respect to the level of data interpolation, and proves that a mild degree of data interpolation strictly improves the prediction accuracy and sta- tistical stability over those of the (un- (un-interpolated) optimal &NN algorithm. This theoretically justifies (predicts) the existence of the second U-shaped curve in the recently discovered double descent phenomenon. Note that our goal in this study of interpolated-NN method, but obtain theoretical insights on data interpolation inspired by the aforementioned phenomenon.
is not to promote the
INTRODUCTION
Classical statistical learning theory believes that over-fitting deteriorates prediction performance: when the model complexity is beyond necessity, the testing error must be huge. Therefore, various techniques have been proposed in literature to avoid over-fitting, such as early stopping, dropout and cross validation. However, recent experiments reveal that with over-fitiing many learning algorithms still achieve small generalization error. For instances, Wyner et al. (2017) explored the over-fitting in AdaBoost and random forest algorithms: Belkin et al. (2019a) discovered a double descent phenomenon in random forest and neural network: with growing model complexity, testing performance firstly follows (conventional) U-shaped curve, and as the level of overfitting increases, second descent even second U-shaped testing performance curve occurs.
To theoretically understand the effect of over-fitting or data interpolation, Du & Lee 2018); Du al. (2199 2018); Arora et al. (2018) 2019); Xie et al. (017)) analyzed how to train neural networks un- der overrparamettizztioo,, and why over-fitting does not jeopardize the testing performance; Belkin iet al. (2019c) constructed Nadaraya- Madaraya-Watson kernel regression estimator which perfectly fits train- ing data but is still minimax rate optimal; Belkin et al. 2018) and Xing et al. (2018) studied the rate of convergence of interpolated nearest neighbor algorithm (interpolated-NN) Belkin al., (2019b); Bartlett et al. (209)) quantified the prediction MSE of the linear least squared estimator when the data dimension is larger than sample size and the training loss attains zero Similar analysis is also conducted by Hastie et al. (2019) for two-layer neural network models with a fixed first layer.
In this work, aim provide theoretical reasons whether, when and why the interpolated-NNN performs better than the optimal ANN, by some sharp analysis. The classical ANN algorithm for either regression or classification is known be rate-minimax under mild conditions (Chaudhuri & Dasgupta (2014), say i diverges propoerly. However, can such a simple and versatile algorithm still benefit from intentional over-fitting? We first demonstrate some empirical evidence below.
Belkin et al. (2018) designed an interpolated weighting scheme as follows:
Σ
||0(]) - x1| ))(0))))()))
[(x)
(1)
Σ -= |10(3) - =

---

Under review as a conference paper at ICLR 2020
-2.00-
-38-
log(MSE)
-2.25
type
(nrrEr
3.7-
type
Interpolated
-2.50
Interpoiated
KNN
KNN
-39
-2.75
4.0
411-
log(n)
log(s)
Figure 1: Regression in Simulation (Left) and Classification in Real Data (Right), Comparison between KNN and Interpolated-NN (with logarithm weight) in Xing et al. (2018).
where Z()) is the i-th closest neighbor to x with the corresponding label (()())). The parameter Y 2 controls the level of interpolation: with a larger y > the algorithm will put more weights 0 or
on the closer neighbors. In particular when
oc, interpolated -NN reduces to ANN or 1-
NN, respectively. Belkin et al. (2018) showed that such an interpolated estimator is rate minimax in the regression setup, but suboptimal in the setting of binary classification. Later, Xing et al. (2018) obtained the minimax rate of classification by adopting a slightly different interpolating kernel. What is indeed more interesting is the preliminary numerical analysis (see Figure [ conducted in the aforementioned paper, which demonstrates that interpolated-NN is even better than the rate minimax ANN in terms of MSE (regression) or clssfiassiiicttoon rate (classification). This observation asks for deeper theoretical exploration beyond the rate of convergence. A reasonable doubt is that the interpolated-NN may possess a smaller multiplicative constant for its rate of convergence, which may be used to study the generalization ability within the "over-parameerrzed regime."
In this study, we will theoretically compare the minimax optimal ANN and the interpolated-NN (under (T) in terms of their multiplicative constants. On the one hand, we show that under proper smooth conditions, the multiplicative constant of interpolated-NN, as function of interpolation level % is U-shaped. As a consequence, interpolation indeed leads to more accurate and stable performance when the interpolation level y E (0. 72) for some Ra > only depending on the data dimension d. The amount of benefit (i.e.. the "performance ratio" defined in Section 2 follows exactly the same asymptotic pattern for both regression and classification tasks. In addition, the gain from interpolation diminishes as the dimension d grows to infinity, i.e. high dimensional data benefit less from data interpolation. We also want to point out that there still exist other "non-inter hooninterpollating weighting schemes, such OWNN, which can achieve even better performance; Section 3.4 More subtle results are summarized in the figure below.
Classical Regime
Over- fver--itting Regime (d = 2)
1NN (y oo)
Testing Error
Opt KNN (r 0)
'owNN
Interpolated NN
O=0
Ya d/3
Model Complexity/ hampllextty/nnterpllaatio
Interpolation Level
Figure 2:
Testing Error with Model Complexity Interpolation Level. The curve within over-fitting regime is depicted based the theoretical pattern of performance ratio given dl = 2.
From Figure 2 we theoretically justify (predict) the existence of the U-shaped curve within the "over-fitting regime" of the recently discovered double descent phenomenon by (elkin al.
2

---

Under review as a conference paper at ICLR 2020
2019a b). As complementary Belkin al. (2018): Xing al. (2018), further show in ap- pendix that interpolated-NN reaches optimal rate for both regression and classification under more general (a, B) smoothhess conditions in Section
In the end, we want to emphasize that our goal here not to promole the practical use of this interpolation method given that ANN is more user-friendly. Rather, the interpolated-NN algorithm used to precisely describe the role of interpolation in generalization ability so that more solid theoretical arguments can be made for the very interesting double descent phenomenon, especially in the over-fitting regime.
2 INTERPOLATION IN NEAREST NEIGHBORS ALGORITHM
In this section, we review the interpolated-NN algorithm introduced by Belkin et al. (2018) in more details. Given 2; define R (xx) to be the distance between and its (k+ 1h nearest neighbor: W.O.L.G, we let X1 to Xx denote the (unsorted) k nearest neighbors of x. and let [R (x(()) } to be distances between and X,. Thus, based the same argument used in Chaudhuui & Dasgupta (2014) and [Belkin et al. (2088,, conditional on (2)1 X1 to X are iid variables whose support a ball centered at with radius (x+1 and as a consequence, R1 (æ) R₂ (z) are conditionally
independent given R (x) well. Note that when no confusion is caused, we will write R₂ (x) as R. Thus, the weights of the neighbors are defined as
R
(Ba/Ra+1)
W
Σラ=1 Rj
(Rg/RR41))
for = 1,..., i and some ? 2 0.
For regression models, denote 77(x) as the target function, and (x) n)(x)) + <(x) where e(x) is
an independent zero-mean noise with [x(x) == (x). The regression estimator at i: is thus
nnm (x) = Σ w.Y
1=1
For binary classification, denote ry(x)) = P(Y 1|X = x), with g(x) = 1(n(x) > 1/2] as the Bayes estimator. The interpolated-NN classifier is defined
{
Σ W.Y 1/2
Tem (2)
0
Σ
W,Y, S 1/2
As discussed previously, the parameter 7 controls the level of interpolation: larger value of leads higher degree of data interpolation.
We adopt the conventional measures to evaluate the theoretical performance of interpolated-NN given a new test data (X,Y)
Regression: mS,((,,,,,)) B((T (x))))
Classification: Regret(k:, P (0k,n, (X) # Y) P (g(X) Y))
3
QUANTIFICATION OF INTERPOLATION EFFECT
3.1 MODEL ASSUMPTIONS
Recent works by Belkin al. 2018) and Xing al. (2018) confirm the rate optimality of MSE and regret for iNterpolated-NN under mild interpolation conditions. Two deeper questions (hinted by Figure we would like to address are whether and how interpolation strictly benefits NN algorithm, and whether interpolation affects regression and classification in the same manner.
To facilitate our theoretical investigation, we impose the following assumptions:
A.1 X is d-dimensional random variable compact set X' with boundary Ox
3

---

Under review as a conference paper at ICLR 2020
A.2 For classification, S = {=/n(x) 1/2} is non-empty.
A.3 d d- 3y 2 C 0 for some constant C.
A.4 For classification, is continuous in some open set containing X. The third-order derivative
of 1) is bounded when v7(x) 1/2 - co for small constant co > 0. The gradient rj(x) A when 7f()) = 1/2, and with restriction on a E 0X, Ön((x) * if n = 1/2 and x E aX.
A.5 For classification, density of X, denoted as is twice differentiable and finite.
A.6 For regression, the third-order derivative of is bounded for all
A.7 For regression, sup o
(x) )) is finite and o² (x) has finite first-order derivative in x.
=EX'
The above assumptions (except A.3) are mostly derived from the framework established by Sam- worth et al. (2012). Note that the additional smoothness required in 1y and f needed to facilitate the asymptotic study of interpolation weighting scheme. We also want to point out that these as- sumptions are generally stronger than those used in Chaudhuri & Dasgupta (2014), but necessary to figure out the multiplicative constant. Further discussions regarding the conditions can be found in Remark in appendix.
3.2
MAIN THEOREM
The following theorem examines the asymptotic performance ratios of MSE and Regret between interpolated-NN and kNN and discovers that these ratios (under their respective optimal choice of k) converges to function of 7d only. In partieular, a U-shaped curve revealed where the ratio is smaller than 1 when (0,ra) ra) for some "da < d/3. Define the minimum MSE and Regret over k E (ne 14/4///d as follows:
MSE(y, = min
MSE(K, 7) and Regret(y, n)) = min Regret(k, n, 7,))). kE(nf .n 4-444)
kE(w 48/4)
Theorem asymptotically compares the interpolated-NN and KNN, i.e., = O, in terms of the above measures. Interestingly, it turns out that the performance ratio, defined as
(d+ 2)2
PR(d, 7) = (1+ d(d 27)
2d+2-7)* d²
a function of d and y only, independent of the underlying data distribution. Note that PR(d, 7) is just the ratio of multiplicative constants before the minimax rate of interpolated-NN and &NN.
Theorem
For regression, suppose that assumptions A. A.3, A.6, and A.7 hold. For classification, under A.1 to A.5, for any 7. E [0, d/3),
MSE(n, 7) MSE(n, 0)
+ PR(d, ?), and Regret(n, + PR(d, 7):
as - oc.
Regret(n, 0)
Note that MSE(n, ()/Rerren(n, 0) is the optimum MSE/Regret for kNN
The proof Theorem are postponed to appendix (Section D
When à can be chosen adaptively based on 7. we can address the second question that interpolation
affects regression and classification in exactly the same manner through (R(d, 7)- In particular, this ratio exhibits an interesting U-shape of ? for any fixed d. Specifically. as y increases from
0, (R(d, 7) first decreases from 1 and then increases above 1; see Figures 2 and 3 Therefore, within the range (0, Tia) for some "a only depending on dimension d, PR PR(d, 7) < 1, that is, the interpolated-NN is strictly better than the kNN. Given the imposed condition that < d/3, Some
further calculations reveal that 7 < d/3 when < 3; Y = d/3 when 2
Remark It is easy to show that lim (min, <a/3 PR(d, d. 7) = 1. This indicates that high di- mensional model benefits less from interpolation. or said differently. high dimensional model is less affected by data interpolation. This phenomenon can be explained by the fact that, as d increases, R,/ R&+1 due to high dimensional geometry.
4

---

Theorem 2 below illustrates how CIS is affected by interpolation through k, and Under review as a conference paper at ICLR 2020
Remark 2 The optimum k, which leads the best MSE/regret, depends the interpolation level 7. Thus, we denote as kn. As shown in the appendix, Key x ko(:= ky=o) X n= but /k/ > 1 for > O, Le., interpolated-N3 needs to employ slightly more neighbors to achieve the best performance. Empirical support for this finding can be found in Section A of appendix.
If we insist using the same = n năo for interpolated-NN and kNN, we can still verify that MSE(K, n, n)/ //M//MMKK n. 0) < 1 and Regret(k; n, Regret n,0) < when 7 Yo for some The depending on the distribution of X and 1).
3.3 STATISTICAL STABILITY
In this section, we will explore how the interpolation affects the statistical stability of nearest neigh- bor classification algorithms. This is beyond the generalization results obtained Section 3.2, In short, if choose the best & in &NN and apply it to the interpolated-NNi then kNN will be more stable; otherwise, the interpolated-NN will be more stable for ? E (0, na) if the k is allowed to be chosen separately and optimally based on ?-
For a stable classification method, is expected that with high probability, the classifier can yield the same prediction when being trained by different data sets sampled from the same population. As result, [Snn et al. (2016) introduced a type of statistical stability, classification instability (CIS), which
different from the algorithmic stability in the literature (Bousquet & Elisseefl 2002). Denote D
and D2 as two i.i.d. training sets with the same sample size n. The CIS is defined as:
CISk,n(7) = PD..DA.X X (ōk, (I, Di) + Ik.n,y (2,
Hence, larger value of CIS indicates that the classifier is less statistically stable. In practice, need to take into account of mis-classification rate and classification instability at the same time. Therefore, we are interested in comparing the stability between interpolated-NN and k-NN only when the regrets of both algorithms reach their optimal performance under respective optimal choices.
Theorem Under the conditions in Theorem ! the CIS of interpolated-NN is derived as
(t)) = Bi 1
(X) +.
V
The proof of Theorem is postponed to Section in appendix.
Similarly, Corollary Bstilaryasyyyplllol asymptotically compares CIS between interpolated-NN and KNN.
Corollary Following the conditions in Theorem 2 when the same k value is used for kNN and interpolated-NN, then as n + 00,
CIS > 1. CIS (0)
On the other hand, if we choose optimum k's for kNN and interpolated-NN respectively, i.e. ky arg min, Regret(k: n, 7). when + oo, we have
CIS (7) PR(d, 7).
CISKo.n
Therefore, when y E Ya), interpolated-NN with optimal has higher accuracy and stability than k-NN at the same time.
From Corollary 3 the interpolated-NN is not stable as ANN if the same number of neighbors used in both algorithms. However, this is not the case an optimal is chosen separately. An intuitive explanation is that, under the same k. &NN has smaller variance (more stable) given equal weights for all & neighbors; on the other hand, by choosing an optimum k the interpolated can achieve much smaller bias, which offsets its performance lost in variance through enlarging k.
5

---

Under review as a conference paper at ICLR 2020
3.4 CONNECTION WITH OWNN AND DOUBLE DESCENT PHENOMENON
Samworth et al. 2 firstly worked out general form of regret using rank-based weighting scheme, and proposed the optimally weighted nearest neighbors algorithm (OWNN). The OWNN is the best nearest neighbors algorithm in terms of minimizing MSE for regression (and Regret for classification), when the weights of neighbors are only rank-based.
Combining Theorem with Samworth et al. (2012). we can further compare the interpolated-NN against OWNN as follows:
2d14
R(n, OWNN) 2 244 R(n.7)
(d+2
(1 1+ d(d ((d-22) 27)
7d (d+2)2
dd+4
(d+2->) d2
which always smaller than (just by definition). Here R(n OWNN denotes the MSE/Regret of OWNN given its optimum k; and R(,,7) denotes the one of interpolated-NN given its own optimum & choice. is interesting to note from the above ratio that that the advantage of OWNN is only reflected at the level of multiplicative constant, and further that the ratio converges to as d diverges (just as the case of PR(d, (d, y) see Remark []. Thus, under ultra high dimensional setting, the performance differences among KNN, Interpolated-NN and OWNN are almost negligible even at the multiplicative constant level.
We first describe the framework of the recently discovered double descent phenomenon (e.g..Belkin eet al. 2019a b), and then comment our contributions (summarized in Figure 2 to it in the context of nearest neighbor algorithm. Specifically, within the "classical regime" where exact data interpo- lation is impossible. the testing performance curve is the usual U-shape w.r.t. model complexity; once the model complexity is beyond a critical point it thus enters the "over-fitting regime," the test- ing performance will start to decrease again as severeness of data interpolation increases, which is so-call "double descend".
Belkin
In the context of nearest neighbors algorithms, different weighting schemes may be viewed as a surrogate of modeling complexity. For OWNN, though allocates more weights on closer neigh- bors, while none of the weights exceeds (1 + d/2)/k. Thus, OWNN is never an interpolation weighting scheme. From this aspect, k--N and OWNN both belong to the "classical regime," while interpolated-NNy is within the "over-fitting regime." In particular, the testing performance of OWNN reaches the minimum point of the U-shaped curve inside the "classical regime." " Deviation from this optimal choice of weight leads to the increase of the MSE/Regret within this "classical regime." After the "over-fitting regime" is reached by the interpolated-NN, say from y = in Figure [ the MSE/Regret decreases the interpolation level 7 increases within the range (0,7a) and ascends again when > "a (if the dimension allows " < d/3), forming the second U-shaped curve in Figure 2 Therefore, we obtain an overall W-shaped performance curve with theoretical guarantee, which coincides the empirical finding of Belkin et al. (2019b) for over- parameeeeedd linear models.
4 NUMERICAL EXPERIMENTS
In this section, we will present several simulation studies to justify theoretical discoveries for regression, classification and stability performances of the interpolated-No algorithm, together with some real data analysis.
4.1 SIMULATIONS
We aim to estimate the performance ratio curve by data simulation and compare it with the theo- retical curve PR(d, 7). The second simulation setting in Samworth al. (2012) is adopted here. Specifically, the joint distribution of (X (x y Y) follows P(Y = 1) P(Y = 0) 1/2. S(X|Y 0)- I1,15 1)) _ 2)] and s(X|y = 1) = II 1.5, + d (0); 2)]. where o(: u, o²) denotes the density of NN, o²). The sample size n = 20 and dimension d 5. The interpolated-No regressor and classifier were implemented under different choices of 7/d = O, 0.05, 0.1,.... 0.35 and k = 1,..., n. For regression, the MSE was estimated based on 100 repetitions, and for classification, the Regret
based 500 repetitions.
When n = 1024, the Regret/MSE ratio for different 7/d is shown in Figure 3 Here Regret ratio is defined by Regret(n, 7)/ (eg 0). the MSE ratio is defined by MSE 7) ///S/) 0). The

---

Under review as a conference paper at ICLR 2020
trends for theoretical value and simulation value mostly close. The small difference is mostly caused by the small order terms in the asymptotic result and shall vanish if larger n is used. Note that 7/d 0.35 is outside theoretical range y/d 1/3. but the performance is still reasonable in our numerical experiment.
Performance Ratio
Performance Ratio
1.1
1.0
1.0-
0.
0.0
0.1
0.2
0.3
0.0
0.1
0.2
0.3
gammald
gammard
Figure 3: Performance ratio curve for 1024 and d = 2 (left) and (right), solid line is theoretical
value (d(d. 7), dashed line simulation results for Regret ratio, dashed line with dots is simulation results for MSE ratio.
We further estimate CIS by training two classifiers based on two different simulated data sets of 1024 samples. The CIS estimated by calculating the proportion of testing samples that have different prediction labels, that is
1 Σ 1 (o.. D1) + F(r D2)).
CIS(c)
The CIS result is shown in Figure One can see that when y is small, the simulated CIS ratio
Performance Ratio
Performance Ratio
0.50
0.90
0.2
0.2
gammaid
gammaid
Figure 4: Comparison between theoretical CIS ratio / (PR(d, 7) (solid line) and simulated CIS ratio (dashed line), under d (left) and 5 (right).
decreases in a similar manner as the asymptotic value, while simulated value will increase when ? gets larger. This pattern is the same as the theoretical result predicted in Theorem
additional experiment is postponed to appendix, which shows how the MSE and optimum changes in y and n where = 2 for = 6....,10 10.
4.2 REAL DATA ANALYSIS
In real data experiment, we compare the classification accuracy of interpolated-NN with ANN
Five data sets were considered in this experiment. The data set HTRU2 from Lyon al. (2016) uses 17,897 samples with continuous attributes to classify pulsar candidates. The data set Abalone contains 4.176 samples with 7 attributes. Following WWang et al. (2018), number of rings is greater than 10. The data set Credit (Yeh & Lien 2009) has 30,000 samples with 23 attributes, and predicts whether the payment will be default in the next month given the current
predict whether the

---

Under review as a conference paper at ICLR 2020
Data
Error (Y 0)
Error (best 7/
best 7/
Abalone
7
0.22239
0.22007
0.3
HTRU2
8
0.02315
0.0226
0.2
Credit
23
0.1933
0.19287
0.05
Digit
64
0.01745
0.01543
0.25
MNIST
784
0,04966
0,04656
0,05
Table I: Prediction Error of ANN, interpolated-NN under the best choice of 7, together with the value of the best 7 for interpolated-NN.
payment information. The built-in data set of digits in sklearn (Pedregosa et al. 2011) contains 1,797 samples of 8x8 images. For images in MNIST are 26 26, we will part of it in experiment. Both the data set of digit and MNIST have ten classes. Here for binary classification we group 0 to 4 as the first class and 5
the second class.
For each data set, a proportion of data is used for training and the rest is reserved to test the accuracy of the trained classifiers. For Abalone, HTRU2, Credit and Digit, we use 25% data as training data and 75% as testing data. For MNIST, we use randomly choosen 2000 samples as training data and 1000 as testing data, which is sufficient for our comparison. The above experiment is repeated for 50 times and the average testing error rate is summarized in Table | For all data sets, the testing error of interpolated-NN (column "best r/d")) is always smaller than the &NN(column "y = 0"), which verifies that nearest neighbor algorithm actually benefits from interpolation.
5 CONCLUSION
Our work precisely quantifies how data interpolation affects the performance of nearest neighbor algorithms beyond the rate of convergence. We find that for both regression and classification prob- lems, the asympiotic performance ratios between interpolated-NN and kNN converge to the same value, which depends on d and only. More importantly, when the interpolation level 7/d is within reasonable range, the interpolated-NI is strictly better than &NN it has smaller multiplicative constant of the convergence rate, and it has a more stable prediction performance as well.
Classical learning framework opposes data interpolation as it believes that over-fitting means fitting the random noise rather than the model structures. However, in the interpolated-NN, the weight degenerating occurs only on a nearly-zero-measure set, and thus there is only "local over-fitting,, which may not hurt the overall rate of convergence. Technically, through balancing the variance and bias, data interpolation can possibly improve the overall performance. And our work essentially quantify such a bias-variance balance in very precise way. It is of great interest to investigate how our theoretical insights can be carried over to the real deep neural networks, leading more complete picture of double descent phenomenon.
REFERENCES
Sanjeev Arora, Nadav Cohen, and Flad Hazan. On the optimization of deep networks: Implicit ac- celeration by overparameterization. In Proceedings of the 35th International Conference on Ma- chine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 244-253, PMLR, 10-15 Jul 2018.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learming Research, pp. 322-332. PMLR, 2019.
Peter I. Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. arXiv preprint arXiv: 1906. //300, 2019.
Mikhail Belkin, Daniel Hsu, and Partha Mitra. Overfitting or perfect fitting? risk bounds for clas- sification and regression rules that interpolate. In Advances in Neural Information Processing Systems 3/, pp. 2300-2311, 2018.
8

---

Under review as a conference paper at ICLR 2020
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine learn- ing and the bias-varianee trade-off. Proceedings of the National Academy of Sciences, 116(32): 15854, 2019a. ISSN 0027-8424. doi: 10.1073//mas..1000071... 19030701 16.
Mikhail Belkin, Daniel Hsu, and Ji Xu. Two models of double descent for weak features. arXiv preprint AxXiv:9903.07777 2019b.
Mikhail Belkin, Alexander Rakhlin, and Alexandre B Tsybakov. Does data interpolation contradict statistical optimality? In Proceedings of Machine Learning Research, volume 89 of Proceedings of Machine Learning Research, pp. 1611-1619. PMLR, 16-18 Apr 2019c.
Olivier Bousquet and André Elisseeff. Stability and generalization. Journal of machine learning research, 2(Mar):499-526, 2002.
Timothy I Cannings, Thomas B Berrett, and Richard Samworth. Local nearest neighbour classifi- cation with applications to semi-supervised learning. arXiv preprint arXiv:/704.00642, 2017.
Kamalika Chaudhuri and Sanjoy Dasgupta. Rates of convergence for nearest neighbor classification. In Advances in Neural Information Processing Systems, pp. 3437-3445, 2014.
Simon S Du and Jason D Lee. On the power of over-parametrizztion in neural networks with quadratic activation. Proceedings of the 35th International Conference on Machine Learning. volume 80 of Proceedings of Machine Learning Research, pp. 1129-1338. PMLR, 10-15 Jul 2018.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. arXiv preprint arXiv:1810.02054, 2018.
Simon S Du, Jason D Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 1675-1685. PMLR, 09-15 Jun 2019.
Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. arXiv preprint arXiv: 011.9993300000 2019.
Robert J Lyon, BW Stappers, S Cooper, JM Brooke, and JD Knowles. Fifty years of pulsar candidate selection: from simple filters to a new principled real-time classification approach. Monthly Notices of the Royal Astronomical Society, 459(1): 104-1123, 2016.
Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, Thirion, O. Grisel, Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830, 2011.
Richard J Samworth al. Optimal weighted nearest neighbour classifiers. The Annals of Statistics, 40(5):2733-276 2012.
Will Wei Sun, Xingye Qiao, and Guang Cheng. Stabilized nearest neighbor classifier and its statis- tical properties. Journal of the American Statistical Association, 11 1116515):1254-116,, 2016.
Yizhen Wang, Somesh Jha, and Kamalika Chaudhuri. Analyzing the robustness of nearest neighbors to adversarial examples. In Proceedings of the 35th International Conference on Machine Learn- ing, volume 80 of Proceedings of Machine Learning Research, pp. 5133-5142. PMLR, 10-15 Jul 2018.
Abraham J Wyner, Matthew Olson, Justin Bleich, and David Mease. Explaining the success of ad- aboost and random forests as interpolating classifiers. The Journal of Machine Learning Research, 18( 15:8115115500 2017.
Bo Xie, Yingyu Liang, and Le Song. Diverse neural network learns true target functions. In Pro- ceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pp. 1216-1224. PMLR, 20-22 Apr 2017.

---

Under review as a conference paper at ICLR 2020
Yue Xing, Qifan Song, and Guang Cheng. Statistical optimality of interpolated nearest neighbor algorithms. arXiv preprint arX1::8800.0281,,2000
I-Cheng Yeh and Che-hui Lien. The comparisons of data mining techniques for the predictive accuracy of probability of default of credit card clients. Expert Systems with Applications, 36(2): 2473-2480, 2009.
10

---

Under review as a conference paper at ICLR 2020
The appendix is organized as follows. In section A, demonstrate additional simulation study which empirically shows that the performances of interpolated-NN and k-NN converge under the same rate, and interpolated-NN generally requires larger number of neighbors than k-NN. Section B- provide the proofs for the main theorems in the manuscript. Section C is for a preliminary theorem of Theorem Section D) provides the proof of Theorem [
Section E is the proof of Theorem 2
In Section F, we delivers a complementary result for rate optimality of interpolated in classifi- cation. Originally [Bllkin al. (2018) obtains the optimal MSE rate for regression task, but only sub-optimal rate of classification regret. We adopt some techniques introduced by Sammorth et al. (2012), and rigorously show that, under (a, (o, -smooohh condition (which more general than the smooth condition imposed in our main theorems), interpolated-We achieves optimal convergence rate for classification well.
A ADDITIONAL NUMERICAL EXPERIMENT
In this experiment, instead of taking n 2 only, we take n 2' fo to see how the performance ratio and optimum & changes in y for different n' The phenomenon for classification similar as regression so we only present regression. Figure [ summarizes the change of MSE and optimum choice of k with respect to different choices of n and 7/d, when d 2. The plot corresponding to d = 5 quite similar hence omitted here. This plot shows that with respect to the increase of n, interpolated-NN converges in the same rate as kNN, and interpolated-NN generally requires larger l than k-NN.
log2(n)
log2(n)
log2/MSE)
gammaid
gammald
Figure 5: Change of MSE and optimal
B PRELIMINARY PROPOSITION
This section provides an useful result when integrating c.d.f:
Proposition 4 From Lemma S.I in Sun et al. (2016), we have for any distribution function G,
a [ 3
(((bu - a) - 1(ucoo]du =
R
a² + 2 f &dG(t) + maGIT)
u[G[-bu a) - [eueop]du
12 2
C PROOF OF A PRELIMINARY THEOREM FOR THEOREM 1
Define P1 and Ps (density as fi, f2) as the conditional distributions X given 0, respectively, and Tı, are the marginal probability P(Y 0) and P(Y = 1), then take P P2 T2P2, P TPP, ToP2, f(x) (x) + (z)) and also denote (x:) (r) (2)

---

Under review as a conference paper at ICLR 2020
Theorem For regression, suppose that assumptions A.I, A.3, A.6, and A.7 hold. If k satisfies 3 S n 1-/8// for some | > O, we have
(R1/Re++ R
MS n,7)
ME
(Ra/ Rk+ )- o (x)
(Ei= l
R2 Rk+1) ~
+K? a (X)
X
+ o.
(R,/ Rk+1)
For classification, under A.I to A.5, the excess risk w.r.l. becomes
1
Bs (x) + 1 |1i(xx))l
f(xo) a² (o)) + o,
Regret(k, n. n.7) = 4k
where
I (100) (Vool=1(aa
Bi
[11
B(Bb// (LBB/BRH+ (Rx+1)
(x)
(E2(R1/ (Rx+1) )
T.R. (Ry (R/Rk+))
(Rk+1)
(x,),(())
[E (R
a(x)
(m(()))(())) + m=(())(()/2]
[(r)d
C.I REGRESSION
Rewrite the interpolated-NN estimate given the distance to the k + Ith neighbor Ra+ interpo- lation level y as
k
Sk Rk+1) Σ W.Y
where the weighting scheme is defined as
(Ra (B//R++1>
Wi Ex_( (Rs/ 1
For regression, we decompose MSE into bias square and variance, where
E[(Sk,n, (2, [z]))
k
Wa(n(X.) - n(x))
+ E
W, W,(Y; -xxx)) m(xx1))
which the bias square can be rewritten as
E
W((n(X,)) - -(((())))(())))))
(E(W) ((=))) - ()) m(xx))
and the variance can be approximated as
2
E
W.CY - -x(Y)-(xx))) -EE3o =ot +
Following a procedure similar as Step for classification, i.e., use Taylor expansion approximate the bias square, we obtain that for some function a, the bias becomes
(,,)) - 77(=)) = (W)) R2 +o.
As result, the MSE of interpolated-NN estimate given becomes. E[ (x. R++1) )==)) = EE + a R +
Finally we integrate MSE over the whole support.
Thhe notation "A o" understood A + ((1+)(1))
12

---

Under review as a conference paper at ICLR 2020
C.2
CLASSIFICATION
The main structure of the proof follows Samworth et al. (2012). As the whole proof is long, we provide brief summary in Section C.2. to describe things we will do each step, then in Section C.2.2 we will present the details in each step.
C.2.1
BRIEF SUMMARY
Step I: denote i..d random variables Zi(x, Rx+1) for = i..... k where
Zi Rk+1) = (R./RR+1) (X
B(R((t)/Ro+((t))
then the probability of classifying as 0 becomes
k
21z, Rkt1)) < <0)
P(Sk,nn 1122 =
The mean and variance of Zi Rk41) can be obtained through Taylor expansion of r) and density function of a::
B(Zi (I, Rx+1))
n(x) + a(x:)
E(R1/ (e/1))
1 (ER,, RR//) 2y
Var(Zi R&41))
4 E (R/ (RR//)++---
for some function a. The smoothness conditions are assumed in A.4 and A.5.
Note that on the denominator of Z; there is an expectation E (x) / (x)))" From later cal- culation in Corollary [] the value of this expectation in fact has little changes given without
condition of Rx+1 1, and it is little affected by either.
Step 2: One can rewrite Regret as
J
W.Y. S 1 1m100)/1/2) dP(x).
Σ
From Assumption A.2, A.4, the region where 7 is likely to make a wrong prediction is near {x|n(x>) 1/2), thus we use tube theory transform the integral Regret over the d-dimensional space into a tube. i.e.,
f.c. [WWn (P(
b W.Y. 1) - (((x)) < 1/2] dP(())
1
= (1+ [ (()))) (P(Se.(at)) < 1/2) [(t=)) dtdVold (xx) + o.
The term will be defined in detail in appendix. Basically, when is within suitable range, the integral over / will not depend on asymptotically.
Step 3: given Ret1 and the nearest k neighbors i.idd. random variables distributed in B(x, Rk+1), thus we use non-uniform Berry-Esseen Theorem to get the Gaussian approximation of the probability of wrong prediction:
f +| (2x)) (P(Sk.(45)) < 1/2) 1(t=0)) dtdVold-1(xx)
[ ( (
KEZ, (zi, R
V/Varr(a (2i R)+1)) - Lecoo didVol==1(z)) +
13

---

Under review as a conference paper at ICLR 2020
Step 4: take expectation over all R and integral the Gaussian probability the tube obtain
(8)
KEZZ (2t. Rk+1)
dtdVol"-
(1:0)
//Varr ar Z1( (2)) Rk+1))
/ / (100()0))1
(-(-)) (1)i(1)))l
E(R1/ Rk+1) (aat))
[(tc0)
dtdVol (xx) +o
V
B1 B(R2/RA -22
[100))]
Eº (R1/ Rk+11 R?
(x(
d'Vol (xro) +o
4k (2(R1/ (xx+1) 1-
E²(R1/ Rx+1)
(x)0)]
=
4k B,E
a² (1O)t
k,
+ 0.
C.2.2 DETAILS
Denote ag the Euclidean ball volume parameter
ad Vol(B(O, 1)) = (x/2))
Define p k/n and r2p sup (2))
Denote E be the set that there exists R such that
Ri > T2p, then for some constant e > 0,
2k
1/d
r2p
l/d 1/d ad
C
n
Hence from Claim A.5 in Belkin al. 2018). there exist e and oz satisfying
P(E) S cxkexp(o22k).
Step 1: in this step, we figure out the i.i.d. random variable in our problem, and calculate its mean and variance given Denote
(a, RB+1)= (R./R++1) (X,
(2)
B(R,/RA41))
then the dominant part we want to integrate becomes
(x, RB41)= S 1
P
p
Σ (R1/RE41)~9(Y(CC) 1/2) (
Σ Dim1 Zz Rk+1) - KEZ1 (I, Re+1)
-kEZ (x1, Re+1)
P VkVar ar (Z, Rx+1))
Rkt1
/kV (kVar(2) (Zi(Z, RR+1))
Therefore, one can adopt non-uniform Berry- Essen Theorem to approximate the probability using normal distribution. Unlike Samworth al. (2012) in which EY (X,) is calculated, since the i.i.d. item in non-uniform Berry-Essen Theorem is rather than Y, we now calculate mean and variance of Z. Under RE+1.
E(Rg/Rx43 ((XR///+))-(XXX,)---111
(x, BR+1) = EZi BE+1)
E(Ri (RR//)++--
E E(R1/R (R/+1)+1) (m((x)) 1/2)
BBRi RR
14

---

Under review as a conference paper at ICLR 2020
and
R R(Ri/ (RR+/++1) (xxX)) 1/2))
EZf (2, Re+1)
(2(R1 R
((R1)R++)) -27
4R2 (Rs/ R
ok o Rx+1) = Var(Z1(z, Rx+1)).
Then the mean and variance of Zi can be calculated as
Pk,n (1 RK+11 = 1. (2): Rk+1) + B(R1/Re++1) ( (X1)
+
E(R Rk+1)
2
E(RI/ Rx+1) 17 (1)(()) + (Xi -x/) = [}(=a()()) + 1 - Ti(z)) -x())
-
[K(R// R
n(ah)) + E(R1/ RR+1) (2 (X1 2//) (j((z))
B(R Rk+1)
1 1E(RI/ Rk+1) 3r (0j( (1/1) ((X1 -x1))) + +((R)
2
E( ( R
Fixing R3 and RE+I, we have
E((x1 =²6) T (2())))11
J (x- =t) (T(T((66))))))) (x)2z) Rx+1)dz
[(r =t) Tn((())) b R1) + I (woll R1) ( xnj) + ojdæ
0+ / ((0 (0- T(( (x6l)) R1) (x 20)er +o
=T)Tdst dx + ir (#(ob) Ri)T / ( - 2/)(
and
tr
2 (((b))
- ((x1-26)(X) ((:))
1 ((t / (00 (x - 2t)T fx]l=y R1)dr
= tr ((ilat)) / /(0 (x- (x - [ R1) + l'(oola Ri) [x x²)) + oldr
= tr [[atblegg R1) ((zz)) / (w==x))e -(0) dx +o,
(4)
2
Then taking function a(x) for such that
a R
E((x 2g)) (z) + tr (bx5)) (Xx, ((x,- =x)(X; 26) =b))(11)) o,
which can be satisfied through taking
d
a(x) {(x)
The difference caused by the value of Rí is only small order term.
15

---

Under review as a conference paper at ICLR 2020
Finally,
M Rk+1)
n(xx)) +])/(())))l a(zo)ta (Rk-1) +..
Step 2: in this step we construct a tube based on the set {अ](((>) 1/2], then figure out that the part of Regret outside this tube is remainder term.
Assume ck,n satisfies Sk,n,7 = =((kkm) and Ck,n = o then the residual terms throughout the following steps will be o(* k,n,, + k.,))) Hence although the choice of 6x,a is different among choices of and n, this does not affect the rate of Regret. Note that we ignore the arguments x and R&+1 as from A.2 and A.4, 6,,,,,7 Rk+1)= = 1/k and (,,,,,(a,, Rx+1) (k/n)2/4 for all while
RE+1 x (k, n)2/d in probability.
By Samworth et 2012)) recall that v(x) = d(Ti (1 - T2 (2))), then
1ec (pp( (P(E W.Y. S 1 2) (n(o)k1/21 dP(x)
Ewy
/ { (P(sk,n <1/2) ((<co) (td)ool=((xo)) ri,
+1+ [1+ o(1)}
=k.m
where
= Janoinn
Ewwx 2 1) [[(00)<1/23 dP(x)
( i==l
k
ERciI
P
Σ
Za(ar, RB+1) <0) -1(00><1/23 dP(x).
For TIs
k
0 2 Jensstannteettsee/aaa
Enn-1
P
Σ
Zi R Rk+1) =0) -1(00)<<12) dP(x))
Jeu1s9honneett)e1/1/ -
-
ERCHi
Za R kBZ (z. RB41) -KEZ (z,, Razi) dP(x).
Using non-uniform Berry-Essen Theorem, when (Zi RE+1) < i.e. < d/3, it becomes
P Σ Zilæ, RK+1) KEZi(z, Ra-1) 1) > -KEZ (x, Rem.)) aP(c)
Jannsuuanntslleec1111 ER
1=1
< [ JEAvSthnntalwnss11 ER
VkEZ, (z, Rk+1) dP(x)
Var Zi (I, Rk+1))
+c1 VK Ruy jupnssaantttmeeeep
Eny. 1 + /3/2 BZ (I,, R
dP(x),
where ((x) = (x)) Since (x, Rk41) = (o)k,,)), = 2l02.mnn (I, Rkt1)).
By the definition of ck,n, we have
exp( & / S (2, RR+1))
ols ols + o(1/k),
inf In(x) 1/2 S'RK.
C36
As a result, using Berstain inequality, F1 is smaller order term compared with s2 kn, when 2 2 (Ra-1) o(1), hence ri o(f.nn))
16

---

Under review as a conference paper at ICLR 2020
Step 3: now apply non-uniform Berre-Esseen Theorem. From Step 3, we have
1.. ER 1 (100)l (P(S),n(*)) < <1/2[ l,r20,) dldVoll-
[ -eE,o
kBZz (I Rk+1)
B Ba (2)))
+
((cco) dtdVoll + r2.
VkVar (Z) Rk-1))
where based on non non-uniform Berry- Berry-Esseen Theorem:
Σ i= Z Rx+1) RBZ1 (+ RK+1).
kBZ1 (3/: RK+1)
kBZ1 (s/: Rk+1)
P
VkVar (1 (1/) Rk+1))
v (War(ZZi(a (x/). Rk+1))
VkVar(Zi (Z) Rx+1))
Z (a/1 Rx+1)1
1
< //3/2V 233/Var3//2 3/2 ( (1 (z/) Re+1))
KBZ, Ra
Reaa)
1+
(1
and
1 1 1
ER (1 (200)
Z1 Rx+1)13 ar (xf, Rx+1))
1
dldVol d- (xx)
r2
(2)
1
//Var(21(2/.Re.1))
For 72+
kE Zı (2/: Rx+1)13
1
72 -
ER (())(()))
dtdVoll-1(xx
J8 - -kkm
/3/2V 3/2 (2 (Zi (1/, Rx+1))
-BZ (wh Re+1)
1
VkVar(2 (2/ Ret1))
C1
tkin
BR (2)0(
dtd
Vk Js
-ck.n
KEZ Rag.
1
/Vaar (xt.)
Vi Is UsSiiiennn
62
(z)) [l (xo)
Vi 1 I {))((=)))
dtd dtd
(0)
1 23/223
ol (.)..)))
Step 4: the integral becomes
/ ERC+
*()0(l)))ll
1AE77(1b Ret1))
I(rc0) dtdVol
V/VVrr22 (I/ Rk+1))
-ekm
|BReII
EReu1
-cx. (|(\())))1l ④
t|lii(z0)ll
B(R, /R+11) Pa(x))
Iteco) dedvorr
22 R (I, Ret1)/K
82 / (x,, Rx+1)/K
+ra +o
(--
| EReti [ {|(\((0))1|
tlli((20)1l
IE(R// CLRI/RAMA RE+1)) (Ra..)-"a(2"))) *a(x)))
1(se0)) dtdvol=-1(x))
V Rn (It, RB41)/K
1 (xr, Rkt1)/k
tr's + o
/// [1((())))1
(8) (0(-/ t||i(z0)|1
C(R1/Rx41)
a(xx)) / /sh,nn(x)) (x)/kk
Tteco) didvol
/oR,,, (x)/k
tras + 1
Bi E(R1/ (R3//R++) 27
+ ( f(20)
E² (2, RK+1) ~ RR
a² a2(x0)
d.Vol d + + + + rr +
4h (2 (R
[|(((x)))]'
E2 E2 RR//Rii Rx+1)
17

---

Under review as a conference paper at ICLR 2020
Note that does not affect the dominant parts. The term E((R1/ Rx41 )- Rk+1) is almost the same for all Rg+1. For the small order terms, following Samworth et al. 2012
2f(2)). The last step follows Proposition and the fact that Rk+1
we obtain
[s BR
- -kEZiiaa Re+1)
-CHm
a.Varr(211 (2/g: Rk+1))
t|]i(200)1l
B(R1/ (RI//R+1) -a((b))t
dtdvor"
2
(x, (x
/h (2,, Rk+1)/K
= o. + 12 tb
and
1s -s 11((2))]12
(x0)]
BRC+. Jest J
=
(- 1111((0001 V sh Phim
E( E(R1/ (R++))
t| (20((1
1(veo)
dedvol"-'(zo)
V /8h.na/k
o0 o(.k.n.))
The term rs is the difference between the normal probability given Re+1 and the one after taking expectation. Similar with Cannings et al. (2017), for each xc, when [t] 6,,n have
ER 1 (-
t tl1)(00)1l
B(R1/ ((R//Rat1) {a(z))
V //hn,,ya (z. Rk+1)/k
V /02 /22mm (xr, Rk+11) 1/++1//k
t||o((0))11
E(R1/ R4+1) a
= (- ( shmm Pennn(a (z,, Rk+1)/K
+ O (kV (kVar(t Re+1))) +
(1, Rx+1)/k
Following step 3 in Cannings et al. (2017) we obtain
-(t)) =0 (
Var(temn Rx+1)) <
12
For the case when |t] >> 8k,n, + Lanny differentiate normal edf twice still leads to very small probability, thus for each we have
f #1ERe 1 (- B2 (ar, Rk41)/kk
f(li((zo)]
E(R1/ F.R//AA RK+1) 7a(2))
dt
/o (a:.)(: (sr, Rat1l/K
f to (-Vorn (I., Rkt1)/k
t|bi((20)11
B(R1/ RR41)) 7 7a(z)))
dt + ol (h
V 1 (2, R441)/K
D PROOF OF THEOREM
To show the ratio MSE(y, n). MO, n) and Regret(y, n) Regret(O, n) asymptotically converges constant, need to figure the corresponding optimum for each scenario.
18

---

Under review as a conference paper at ICLR 2020
For classification, given know that if X follows multi-dimensional uniform distribution with density (z), for some constant Cu that only depends on d,
Rk+1
-2
d
E(R1/RA+1)
ER d
p dr
+o
+ o,
RA+1
d-21 27
d
B(R1/RA+1)
+0,
d d
2 d
K
B(R Rk+1) (0011)~0000
R2
B(R1/ Rk+1) (
Cd
nf(())
d -
Since R3 - O, this approximation still holds if X follow other distributions. result, through figuring out the optimum for O and 7, we have
Regret(n, 7)
(1
72
7d (d+22 -7)²
(d 232
Regret(n, 0)
d(d-27)
-
d²
For regression, one more step needed compared with classification is to evaluate
(R1/ (R/RR++1-22
RR Rk+1) (/BR//R++)>> R )
kE
(E (Ra/ (///1)+4))) Bx(X)² + K a (X))²²
1 ([//R441)- (
The sum of ratios Σ/m (Ra/ (Re/Re+11 R is hard to evaluated directly in the denominator, hence we use upper bound and lower bound on it. Since 3y > O, using non-uniform Berry-Essee Theorem, given RE+1, we have
P Σ (Re/ (Re/B441)~ -(EE)))
(VVVar((R) a ( RA+1)
-
E
Rx+1
5 (E/VR)3
Therefore, taking 8ykE(R1/ (R 7,
P
Σ RR/RRe4)) RR+1) > (6x + 1) RA/ Ret1)
Rett1
8n S 18++) Ru+1 Betl) + 1 (Vk0k)3
c
<
/Var((R) Re+11)
Note that (Ry Rk+1) 77 is always larger than 1, hence
(R1/ (1/R241) 1 27
E
(Raa RM++1) 72
BBBRg R -27
< En.
21 Ru/ R(+1)-
E R( RK+1) -22
+.ER 11
P
Ra/RRR Rx+1) << (1-88)kE(( (RE/)11)) -> Ra+1
+0
1.2
E(Rg RR41) 27
E(R RR++1) 27
6k GAVKE(R / (4
<
21 - )z)
E2(RI/ (RR/Rai 1
122
[Var([R]] /
ERRi/ /RR/RRAA Rx+1)
c
+o,
12
1 (Vkoy)3
while
(Rg (R//R4+1) -27
1
E(R ( - 27
E(R (R++) 22
+
1= (015/Re+1)-9
k2 + 5z
E2
(Rt
12
1
(VTo8,
19

---

Under review as a conference paper at ICLR 2020
Hence taking oy such that o2 - 0 while 6% V + 0o, we have
(R1/ RR++1)
1 (d=
E
+
ii=l (R4/ ( Rk+1)
22 d(d - 227)
and similarly
R2 (R/ Rx+1)
3 d-7 + o. d+3 2 -
(Rs/ B(+1)=
h
ff((z)
After figuring out the optimum &s for kNN and interpolated-NN -NN we finally obtain
MSE(n, 7) MSE(n, 0)
(1+
72
(d 7)2 (d + 2)² +
d(d - 27)
(d+ 2 - 2))
d?
E PROOF OF THEOREM 2
The proof is similar with Theorem in Sun et al. (2016).
From the definition of CIS, we have
S (15knn(0222 1/2) (1 P(Sa.n (0) (z) 1/2)) dP(x)
CIS(n)/2
[ (P(Sk 1/2) - (160))1121) dP(x)
- / (p2 2 1/2) (w(e)s122) dP(x). R
Based on the definition of Zx RB+1) in 2 the derivation (km Rx41) and Sk (x, Rx+1), follow the same procedures in Theorem obtain
/ (P(Skm)711) 2 1/2) (
R
[ -cx,
f(xb) (Ent_1 P (Sk. < <1/ <1/2| [e200) dtdVoll=((oo) +
(
-1(200) 2
[ [(x0) {rr + ( Vohmmy/
Enuti jR
( o,
V /shmma/
and similarly,
S (Pa 2 1/2(R) (((())1122) dP(x))
{ FRn [ f(xb) (p2 (Skm)(aa) < 1/22 -(120) } sttdVol=-1an +
-ekm
/ ERLHI { f(xu)) 2
+||i(a0))l /
E(R1/ RA+1) R (a(z)) 2 kk /h
I(020) dtdvoll- +
Adopting Proposition 4 and the fact that 5k,m, (I, RE41) ) is little changed by æ and Re41, treating and 22 as two distribution functions, we have
CIS(y) = Bi V S + T Vk
B
72 d(d - 27)
1+
+ t.
V
Vk
The optimum for kNN and interpolated-NN satisfies
k(7)
(d 2d
d
2+1
(d + 2) Finally obtain the asymptotic ratio of CIS'ss es.
k(0)
d(d - 27)
20

---

Under review as a conference paper at ICLR 2020
F INTERPOLATION DOES NOT AFFECT THE RATE OF CONVERGENCE
F.1 MODEL SETUP AND THEOREM
The results in Section are obtained based smooth 7/ and f. thus the Taylor expansions be calculated. In this section, we will provide a weaker result under weaker assumptions as those in Chaudhuri & Dasgupta (2014) and Belkin al. (2018).
We first setup some assumptions:
A.I' X is d-dimensional random variable on compact set and satisfies regularity condition: let À be the Lebesgue measure on R., then there exists positive (co, ro) such that for any x in the support X,
B(z, r)) rB),
for any 0 < <<<> <rSm ro-
A.4' Smoothness condition: (n(()) - m(y)1 S A - y| for some a > O.
A.5' The density of X is finite, and the model satisfies margin condition: P(I((X) 1/21 < t) S Bt
The regularity condition in A.1' is used to ensure the convergence of the distance of the k + 1th neighbor: if the density is infinite at some points, the neighbors will be the point itself. The smooth- ness condition A.4' describes how smooth the function ry is, which affects the minimax performance of ANN given class of 1) Assumption A.5' describes how far the samples are away from 1/2, and affects the minimax rate for binary classification. When is small, there is cluster of samples around 1/2, leading to a large prediction error rate.
In interpolated-NN. if the level of over-fitting is not strong, that is, y is within some suitable range, then excess risk of classification also reaches optimal:
Theorem 6 For regression, under A.I', A.3, A.4', A.S',
MSE(1, m) O(n 1onn-20/ -20/ (20-)))
For classification, under A.I', A.3, A.5',
Regret(y,, m) O(n On ((--a(8+1)/(24t)))
In addition, B 2 2, when d - xx((B)) > O, where k(ß) denotes the smallest even number that is greater than 8 + 1, then we have
Regret(", n) ((=+)((+))
The main proof of Theorem 6 follows the idea in Chaudhuri & Dasgupta (014), with Berstein inequality changing to non con-umfform Berry Esseen Thoerem. For the regression part, we refer readers to Belkin al. (2018) and Belkin al. (2019c).
From Theorem one can see that given a reasonable level of over-fitting, the performance of INterpolated-NN reaches the minimax rate for both regression and classification.
When B < and 3 2 2, we technically impose different restrictions on 7. A quick illustration on this is that we adopt non-uniform Berry-Essen Theorem to bound the probability. In non-uniform Berry-Essen Theorem, although the Gaussian probability itself has exponential tail, the residual part is only 1/(1 + ) As a result, when summing up 1 ,++1 /(1 + ( for I = 2 B should be smaller than 0 in order bound the summation.
Remark 3 As Chaudhuri & Dasgupta 2014; mentioned, our smoothness condition (A.4") is in fact a sufficient condition. Theorem what we really need is some constant a' such that
In(x) m(((2zr))
r)) S Lr
The result in Samworth et al. tr (x (EE xx)(X Za) in Theorem 5 which indicates that adopt smoothness d' 2, though a = 1. In addition, the margin condition parameter B = 1 under A.I to A.5 becomes 1. Therefore, the optimum rate of O(n -a't (8+1)/ +d)) is O(n -4((++d)). The over over-fitting weighting scheme in fact leads optimal rate for classification.
(212)) is a case where a & a'. We approximate ET(X)) as Tπ(20) +
21

---

Under review as a conference paper at ICLR 2020
F.2 PROOF OF THEOREM 6
Let 2k/n. Denote E (3R, >> Tp: i= 1, 1...., k). and E.R,, (x) (x)x) the excess risk. Then define
(k Rk+11)++) [B[(R]/RK+]] (()
as well
1
1
2. (x E x(((())
[((x)
2 + A, VR&+1 <12p(1))
2'
1
1
p. = fx E X(((z)
< [[xx)
S
- A < <r2p(z))
2
with the decision boundary area:
pp. X (X U
Given pp.d. A p. and P,ss similar with Lemma 8 in Chaudhuri & Dasgupta 2014 the event of g(x) * 0k, (r) can be covered as:
(()()))))mn(())) 2 1xE0ppat
+1 _ux n22
+1 (2) ((0
When [x)]) > 1/2 and X++ p. assume mm (x) < 1/2, then Me (2) (x|Rxx+) Rx++1 - n,) > ne (x) Rx+11 1/2 2 A.
The other two events are easy figure out.
In addition, from the definition of Regret, assume v7(x) < 1/2.
Y( n(x)
0|X 000-:000=0000000000--000-0000--- n1(
= -
77())
= {
# +z(=) -0) # +(x)| = 2) - 17(x)
(1 PQQ( * (()) = x),
similarly, when 7xx) > 1/2, we have
P( # Y = x) - + nxx) = (2n(x) - 1))((())) + x(x)|{ = x).
As result, the Regret can be represented as
Regret(k: 7) = E (|1 - ( + Ik, (X)))
For simplicity, denote p- k/n. We then follow the proof of Lemma 20 of Chaudhuri & Dasgupta 2014). Without loss of generality assume 17(x)) > 1/2. Define
D sup 7/(2 Rx+1) (xx) 0(r2,) O(k/n)//4
A(x) =
- -
then
7| Rx41) 2 11(x) Do + (A(z) Ao).
hence X+
22

---

Under review as a conference paper at ICLR 2020
From the definition of RR,n and R', when A(x) > Au. have
(2) 180 (x)
s 21(x) P(T(A+1) > v2p) Σ (X;(X;; [(([||++1)> > A(x) 20)]
#
1 exp((kk8) + +2)()) (XX)) > (+(z| + A(x) - Ao) Σ (Ra/ R
exp(-k/8) + (2)
Σ
(X(() R)
(([(||R+1) + A(x) Au) Σ -B( /E(R//R++2)
((T(a/Ru+1) + +(x) B (x(((())
= exp(-k/8) + 21(x) P
Ra/RR (X,( ((0|/(+11)
(A(()) Ao) Σ (R//Ro+1) -KE(RI/ -KE(RI/Be+1) 1++1)-
> kx)(2) Ao)E( RA+1)
Since
- Rk+1) (Xx()))) -((x()++1)) =
k
((A(x) xx) - Do) Σ (Ra/Rx+1)* - KE(RR/ (EG(R//R++))) Re
can Markov inequality to the power of x(3) bound the probability. Denote
Z,(x) = 14
for simplicity. Note that
Var(Zz(x)) O(A(z) Ao).
For different settings and 7, the following steps have the same logic but different details:
Case 1: < and 7 < d/3: Considering the problem that the upper bound can be much greater than when A Axx) is small, we define A, 2' Ao. taking io min > 1 (A; An) > 1/k). In this situation, since (Z)()) < co, we can adopt non-unifome Berry-Essee Essen Theorem for the proof:
ER (X) Rd (X)
E(R (X) - R² (X))
+E(R, (X) - R² (X))
2A, P(A(X) S Aio) + +exp(-k/8
Vk(A(z) - Ao)
)
+4E
WVr(Zi(X))A)
+4B
A(X)TAA <(()) Vk 1+ 13/2 A0)
C1
23

---

Under review as a conference paper at ICLR 2020
The two terms from Berr-EEssen Theorem becomes
C (((IX)))))
+ - A
A
8+1
1
V
1 A0)3
k0#+1)/2 (VRDit1) 8+1 a
13/2 A0)3:
together with
VE(A(1)- An)
E (XX))
(Var(2((X)
E (XX)I(A,<<(X))]
(SLVE(A(T) - Aul)
1
exp (-GGh( - -0)
Vi(A; Ao)
The upper bound is larger than if A, S co/vi. When A, > V//
A 1
A Ao) exp (-Gg(A,; - Ao)3)
2o) exp 1ap(-Gk(AA111 2o)3) = 28+1 28+12 20-
exp (-Ggk(s; 2o)
A
2 -
cs - Ao)
23 exp
(- Lkkk 4))
(2kh( Ao) <1/2.
exp
Therefore the sum of the excess risk can be bounded. When 8 < 2, B - 2 < 0, hence
C
Vk 1+ 13/2 (Zx) 3
1
0
[VR(A +1 -
k(8+2)/2
1210
0
1
(V 8-220(0-2)
R(8+2)/2
$240
A 8-2
0
1100
((0-2)/2
22/2
8-2
=0
1(0+2)/2
to
1.2
and
Vk(A(2) - Ao) )
E
A ~
(x)x)
A B+1
<
exp (-GG((A -00)3)
Ao)
12.0
0
A 1o+1 exp (-ozkAAi, - -u)))
Vi:
Recall that A,, > Do and A > 1/k, hence when A O(1/k), can obtain the minimum
upper bound
(8+1)/2
ER (X) (x) 3044 +0
2+1)
Taking t: x (n2a/(2atd)) the upper bound becomes On ((0=))))))/2))
24

---

Under review as a conference paper at ICLR 2020
Case 2: 7 < d/k(())
B (X) (X)
= (() - ((
+E(R (X) R* (A(x)>20)))
2A P(A(X) S Aio) exx((-k/8)
Σ si=l (((x)) 4(0)
+4
A(X) <1(01 (A(X) Do) (0)00100) (m Bx(A) RI/ Rk-1)
while for some constant C1 > 0,
Σ (x) K(3)
E
A(X))A)A (A(X) Ao) x((3) (x(0) [R) R
N(,)
# (x)
< E [A(X))
(A; Ao) (m10 (RI/Re+ (R++1)
K(1)
E
Σ 1= Zx(x)
AAAIP(A(X) S A441)
(A, (x))
(0))) (Ry Rx-1)
x(0)/2
8+1 41
/A: A0)
Ci
where the last inequality is obtained since x(3)7 O. Note that x(3) > thus for some / (A: - (n)
0 0<c<l,
6+1 /A A0)x(() <
(5)
Therefore the sum of the excess risk for can be bounded, where
E Z(() M(0)
E (A(X)
A(X)_1A <A(X))
(33) (n()) (R2/ 1R+1)
x(0)/2
0
Σ
41
8+1
/(A ())
(6)
121
< 0 A (+1
Recall that o, upper bound
Do and A 1/k, hence when A 0(1/k), obtain the minimum
ER (X) 50A) +o ((t) (8+1)/2)
Taking tt x (n) the upper bound becomes O(n (((+))))))(2aa
25


Reviews:
[{"review_id": "rklTS2CAKS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper is about interpolation schemes in the particular case of the\nNearest Neighbor algorithm. The authors investigate the bene\ft, mainly\ntheoretical, of the proposed interpolation. They study minimax rates of\nthe proposed interpolated-NN for both classi\fcation and regression. The\nstatistical stability of the Interpolated-NN is adressed.\nThe paper is easy to understand and correctly written. Nevertheless,\nIt is a particular case of ( \\Over\ftting or perfect \ftting? Risk bounds for\nclassi\fcation and regression rules that interpolate\", Belkin, M., Hsu, D.,\nand Mitra, P. (2018a)) with an explicit interpolation schemes given by the\neuclidien distance power gamma. It appears as an application of the above\npaper which brings only few theoretical advantages and not enough to justify,\nalthough intuitive, the choice of these weights. Only few discussions and\nno comparison to others bounds (as those in the above paper) of the main\ntheorem are given. The paper is too much incremental from the papers of\nBelkin et al. (2018) and Xing et al. (2018) and the bene\fts of the proposed\ninterpolation are limited. Furthermore, the empirical performance of the\ninterpolate-NN is clearly not convincing and show no signi\fcant practical\nadvantages of the proposed method. As the goal of the paper is clearly\ntheoretical, the 'real data analysis' part is not necessary in my opinion.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "rJl9DU5MoH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper studies theoretical perspective of double descent phenomenon for the interpolated K-NN classifier.\n\nThe paper is works in several interesting directions and gives theoretical reasoning to how interpolated K-NN could exhibit the double descent phenomenon. They give theoretical justifications albeit with strong assumptions.\n\nI think the paper is a good paper. However, I have concerns with the presentation quality of the paper. It is very tough to get through the paper till the end. \n\nIn my view, it would have been an Accept if the paper was well written.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "rJeZ9nU15S", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the interpolated k-nearest neighbors algorithm from a theoretical perspective. Specifically, it studies how the performance of the algorithm is affected by reweighting the k nearest neighbors according to their relative distance. This regime has been considered in prior work, particularly Belkin et al. (2018).\n\nUnder various niceness conditions, the paper proves error bounds for interpolated k-nearest neighbors for both regression (i.e. squared loss) and classification (i.e. 0-1 loss after thresholding).\n\nOverall, I have the impression that this paper contains interesting ideas, but the presentation is very poor. It should be revised and resubmitted before it can be accepted.\n\nIn particular, the paper does not make its contribution clear. The main theorem only appears on page 4 and the reader must consult the appendix to see the definition of all the terms that appear in the theorem. I have no idea how to interpret the (complicated) expression in the theorem. The theorem needs to be explained in intuitive terms. More context needs to be given by comparing the main theorem to prior works (which I am not familiar with). \n\n\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors show that data interpolation in the context of nearest neighbor algorithms, can sometime strictly improve performance. The paper is poorly written for an ICLR audience and the added value compared to extensive prior work in the area is not clearly demonstrated.
Decision: Reject