Title: BENEFIT OF INTERPOLATION IN NEAREST NEIGHBOR ALGORITHMS

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 kNN 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.

1. 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 even with over-fitting, 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 a (conventional) U-shaped curve, and as the level of overfitting increases, a second descent or even a second U-shaped testing performance curve occurs.

To theoretically understand the effect of over-fitting or data interpolation, Du & Lee (2018) ; Du et al. (2019; 2018) ; Arora et al. (2018; 2019) ; Xie et al. (2017) analyzed how to train neural networks under over-parametrization, and why over-fitting does not jeopardize the testing performance; Belkin et al. (2019c) constructed a Nadaraya-Watson kernel regression estimator which perfectly fits training 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 et al. (2019b) ; Bartlett et al. (2019) 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, we aim to provide theoretical reasons on whether, when and why the interpolated-NN performs better than the optimal kNN, by some sharp analysis. The classical kNN algorithm for either regression or classification is known to be rate-minimax under mild conditions (Chaudhuri & Dasgupta (2014) ), say k 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: where x (i) is the i-th closest neighbor to x with the corresponding label y(x (i) ). The parameter γ ≥ 0 controls the level of interpolation: with a larger γ > 0, the algorithm will put more weights on the closer neighbors. In particular when γ = 0 or γ = ∞, interpolated-NN reduces to kNN 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.

EQUATION

What is indeed more interesting is the preliminary numerical analysis (see Figure 1 ) conducted in the aforementioned paper, which demonstrates that interpolated-NN is even better than the rate minimax kNN in terms of MSE (regression) or mis-classification 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-parametrized regime."

In this study, we will theoretically compare the minimax optimal kNN and the interpolated-NN (under (1)) in terms of their multiplicative constants. On the one hand, we show that under proper smooth conditions, the multiplicative constant of interpolated-NN, as a function of interpolation level γ, is U-shaped. As a consequence, interpolation indeed leads to more accurate and stable performance when the interpolation level γ ∈ (0, γ d ) for some γ d > 0 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-interpolating" weighting schemes, such as OWNN, which can achieve an even better performance; see Section 3.4. More subtle results are summarized in the figure below. 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 Belkin et al. (2019a; b) . As complementary to Belkin et al. (2018); Xing et al. (2018) , we further show in appendix that interpolated-NN reaches optimal rate for both regression and classification under more general (α, β)-smoothness conditions in Section F.

In the end, we want to emphasize that our goal here is not to promote the practical use of this interpolation method given that kNN is more user-friendly. Rather, the interpolated-NN algorithm is 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 x, we define R k+1 (x) to be the distance between x and its (k + 1)th nearest neighbor. W.O.L.G, we let X 1 to X k denote the (unsorted) k nearest neighbors of x, and let {R i (x)} k i=1 to be distances between x and X i . Thus, based on the same argument used in Chaudhuri & Dasgupta (2014) and Belkin et al. (2018) , conditional on R k+1 (x), X 1 to X k are iid variables whose support is a ball centered at x with radius R k+1 (x), and as a consequence, R 1 (x) to R k (x) are conditionally independent given R k+1 (x) as well. Note that when no confusion is caused, we will write R i (x) as R i . Thus, the weights of the k neighbors are defined as

W i = R -γ i k j=1 R -γ j = (R i /R k+1 ) -γ k j=1 (R j /R k+1 ) -γ

, for i = 1, . . . , k and some γ ≥ 0.

For regression models, denote η(x) as the target function, and Y (x) = η(x) + (x) where (x) is an independent zero-mean noise with E (x) 2 := σ 2 (x). The regression estimator at x is thus

η k,n,γ (x) = k i=1 W i Y i .

For binary classification, denote η(x) = P (Y = 1|X = x), with g(x) = 1{η(x) > 1/2} as the Bayes estimator. The interpolated-NN classifier is defined as

g k,n,γ (x) = 1 k i=1 W i Y i > 1/2 0 k i=1 W i Y i ≤ 1/2 .

As discussed previously, the parameter γ controls the level of interpolation: a larger value of γ leads to a 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: MSE(k, n, γ) = E(( η k,n,γ (X) -η(X)) 2 ). Classification: Regret(k, n, γ) = P ( g k,n,γ (X) = Y ) -P (g(X) = Y ) .

3. QUANTIFICATION OF INTERPOLATION EFFECT:



3.1. MODEL ASSUMPTIONS:

Recent works by Belkin et al. (2018) and Xing et al. (2018) confirm the rate optimality of MSE and regret for interpolated-NN under mild interpolation conditions. Two deeper questions (hinted by Figure 1 ) 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 a d-dimensional random variable on a compact set X with boundary ∂X . A.2 For classification, S = {x|η(x) = 1/2} is non-empty. A.3 d -3γ ≥ C > 0 for some constant C.

A.4 For classification, η is continuous in some open set containing X . The third-order derivative of η is bounded when η(x) = 1/2 ± c 0 for a small constant c 0 > 0. The gradient η(x) = 0 when η(x) = 1/2, and with restriction on x ∈ ∂X , ∂η(x) = 0 if η(x) = 1/2 and x ∈ ∂X .

A.5 For classification, density of X, denoted as f , is twice differentiable and finite.

A.6 For regression, the third-order derivative of η is bounded for all x.

A.7 For regression, sup x∈X σ 2 (x) is finite and σ 2 (x) has finite first-order derivative in x.

The above assumptions (except A.3) are mostly derived from the framework established by Samworth et al. (2012) . Note that the additional smoothness required in η and f is needed to facilitate the asymptotic study of interpolation weighting scheme. We also want to point out that these assumptions 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 3 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 a function of (d, γ) only. In particular, a U-shaped curve is revealed where the ratio is smaller than 1 when γ ∈ (0, γ d ) for some γ d < d/3. Define the minimum MSE and Regret over k ∈ (n β , n 1-4β/d ) as follows:

MSE(γ, n) = min k∈(n β ,n 1-4β/d ) MSE(k, n, γ) and Regret(γ, n) = min k∈(n β ,n 1-4β/d ) Regret(k, n, γ).

Theorem 1 asymptotically compares the interpolated-NN and kNN, i.e., γ = 0, in terms of the above measures. Interestingly, it turns out that the performance ratio, defined as

PR(d, γ) := 1 + γ 2 d(d -2γ) 4 d+4 (d -γ) 2 (d + 2 -γ) 2 (d + 2) 2 d 2 d d+4

, is a function of d and γ only, independent of the underlying data distribution. Note that PR(d, γ) is just the ratio of multiplicative constants before the minimax rate of interpolated-NN and kNN.

Theorem 1 For regression, suppose that assumptions A.1, A.3, A.6, and A.7 hold. For classification, under A.1 to A.5, for any γ ∈ [0, d/3),

MSE(n, γ) MSE(n, 0) → PR(d, γ), and Regret(n, γ) Regret(n, 0) → PR(d, γ), as n → ∞.

Note that MSE(n, 0)/Regret(n, 0) is the optimum MSE/Regret for kNN.

The proof Theorem 1 are postponed to appendix (Section D).

When k can be chosen adaptively based on γ, we can address the second question that interpolation affects regression and classification in exactly the same manner through PR(d, γ). In particular, this ratio exhibits an interesting U-shape of γ for any fixed d. Specifically, as γ increases from 0, PR(d, γ) first decreases from 1 and then increases above 1; see Figures 2 and 3 . Therefore, within the range (0, γ d ) for some γ d only depending on dimension d, PR(d, γ) < 1, that is, the interpolated-NN is strictly better than the kNN. Given the imposed condition that γ < d/3, Some further calculations reveal that γ d < d/3 when d ≤ 3;

γ d = d/3 when d ≥ 4.

Remark 1 It is easy to show that lim d→∞ [min γ<d/3 PR(d, γ)] = 1. This indicates that high dimensional 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 i /R k+1 → 1 due to high dimensional geometry.

Remark 2 The optimum k, which leads to the best MSE/regret, depends on the interpolation level γ. Thus, we denote it as k γ . As shown in the appendix, k γ k 0 (:= k γ=0 ) n 4 d+4 , but k γ /k 0 > 1 for γ > 0, i.e., interpolated-NN 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 k n 4 d+4 for interpolated-NN and kNN, we can still verify that MSE(k, n, γ)/MSE(k, n, 0) < 1 and Regret(k, n, γ)/Regret(k, n, 0) < 1, when γ < γ x for some γ x depending on the distribution of X and η.

3.3. STATISTICAL STABILITY:

In this section, we will explore how the interpolation affects the statistical stability of nearest neighbor classification algorithms. This is beyond the generalization results obtained in Section 3.2. In short, if we choose the best k in kNN and apply it to the interpolated-NN, then kNN will be more stable; otherwise, the interpolated-NN will be more stable for γ ∈ (0, γ d ) if the k is allowed to be chosen separately and optimally based on γ.

For a stable classification method, it 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 a result, Sun et al. ( 2016) introduced a type of statistical stability, classification instability (CIS), which is different from the algorithmic stability in the literature (Bousquet & Elisseeff, 2002) . Denote D 1 and D 2 as two i.i.d. training sets with the same sample size n. The CIS is defined as:

CIS k,n (γ) = P D1,D2,X ( g k,n,γ (x, D 1 ) = g k,n,γ (x, D 2 )) .

Hence, a larger value of CIS indicates that the classifier is less statistically stable. In practice, we 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 k choices.

Theorem 2 below illustrates how CIS is affected by interpolation through k, n and γ.

Theorem 2 Under the conditions in Theorem 1, the CIS of interpolated-NN is derived as

CIS k,n (γ) = B 1 √ π 1 √ k Es k,n,γ (X) + o.

The proof of Theorem 2 is postponed to Section E in appendix.

Similarly, Corollary 3 asymptotically compares CIS between interpolated-NN and kNN.

Corollary 3 Following the conditions in Theorem 2, when the same k value is used for kNN and interpolated-NN, then as

n → ∞, CIS k,n (γ) CIS k,n (0) > 1.

On the other hand, if we choose optimum k's for kNN and interpolated-NN respectively, i.e.

k γ = arg min k Regret(k, n, γ), when n → ∞, we have CIS kγ ,n (γ) CIS k0,n (0) 2 → PR(d, γ).

Therefore, when γ ∈ (0, γ d ), interpolated-NN with optimal k has higher accuracy and stability than k-NN at the same time.

From Corollary 3, the interpolated-NN is not as stable as kNN if the same number of neighbors is used in both algorithms. However, this is not the case if an optimal k is chosen separately. An intuitive explanation is that, under the same k, kNN has a smaller variance (more stable) given equal weights for all k neighbors; on the other hand, by choosing an optimum k, the interpolated-NN can achieve a much smaller bias, which offsets its performance lost in variance through enlarging k.

3.4. CONNECTION WITH OWNN AND DOUBLE DESCENT PHENOMENON:

Samworth et al. ( 2012) firstly worked out a general form of regret using a 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 1 with Samworth et al. ( 2012), we can further compare the interpolated-NN against OWNN as follows:

R(n, OWNN) R(n, γ) → 2 4 d+4 d + 2 d + 4 2d+4 d+4 1 + γ 2 d(d -2γ) -4 d+4 (d -γ) 2 (d + 2 -γ) 2 (d + 2) 2 d 2 -d d+4 ,

which is always smaller than 1 (just by definition). Here R(n, OWNN) denotes the MSE/Regret of OWNN given its optimum k, and R(n, γ) denotes the one of interpolated-NN given its own optimum k choice. It 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 1 as d diverges (just as the case of PR(d, γ); see Remark 1). 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 et 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 interpolation 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 testing performance will start to decrease again as severeness of data interpolation increases, which is so-call "double descend".

In the context of nearest neighbors algorithms, different weighting schemes may be viewed as a surrogate of modeling complexity. For OWNN, though it allocates more weights on closer neighbors, while none of the weights exceeds (1 + d/2)/k. Thus, OWNN is never an interpolation weighting scheme. From this aspect, k-NN and OWNN both belong to the "classical regime," while interpolated-NN 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 γ = 0 in Figure 2 , the MSE/Regret decreases as the interpolation level γ increases within the range (0,γ d ) and ascends again when γ > γ d (if the dimension allows γ d < 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-parametrized linear models.

4. NUMERICAL EXPERIMENTS:

In this section, we will present several simulation studies to justify our theoretical discoveries for regression, classification and stability performances of the interpolated-NN 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 theoretical curve PR(d, γ). The second simulation setting in Samworth et al. ( 2012) is adopted here. Specifically, the joint distribution of (X = (

X (i) ) d i=1 , Y ) follows P (Y = 1) = P (Y = 0) = 1/2, f (X|Y = 0) = i [ 1 2 φ(X (i) ; 0, 1) + 1 2 φ(X (i) ; 3, 2)] and f (X|Y = 1) = i [ 1 2 φ(X (i) ; 1.5, 1) + 1 2 φ(X (i) ; 4.5, 2)]

, where φ(•; µ, σ 2 ) denotes the density of N (µ, σ 2 ). The sample size n = 2 10 and dimension d = 2, 5. The interpolated-NN regressor and classifier were implemented under different choices of γ/d = 0, 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 was based on 500 repetitions.

When n = 1024, the Regret/MSE ratio for different γ/d is shown in Figure 3 . Here Regret ratio is defined by Regret(n, γ)/Regret(n, 0), the MSE ratio is defined by MSE(n, γ)/MSE(n, 0). The trends for theoretical value and simulation value are 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 γ/d = 0.35 is outside our theoretical range γ/d < 1/3, but the performance is still reasonable in our numerical experiment. 

CIS(γ) = 1 n n i=1 1( g(x i , D 1 ) = g(x i , D 2 )).

The CIS result is shown in Figure 4 . One can see that when γ is small, the simulated CIS ratio 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 2.

An additional experiment is postponed to appendix, which shows how the MSE and optimum k changes in γ and n where n = 2 i for i = 6, . . . , 10.

4.2. REAL DATA ANALYSIS:

In real data experiment, we compare the classification accuracy of interpolated-NN with kNN.

Five data sets were considered in this experiment. 1 . For all data sets, the testing error of interpolated-NN (column "best γ/d") is always smaller than the kNN(column "γ = 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 problems, the asymptotic performance ratios between interpolated-NN and kNN converge to the same value, which depends on d and γ only. More importantly, when the interpolation level γ/d is within a reasonable range, the interpolated-NN is strictly better than kNN as it has a 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. The appendix is organized as follows. In section A, we 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-E provide the proofs for the main theorems in the manuscript. Section C is for a preliminary theorem of Theorem 1, Section D provides the proof of Theorem 1, Section E is the proof of Theorem 2.

In Section F, we delivers a complementary result for rate optimality of interpolated-NN in classification. Originally Belkin et al. (2018) obtains the optimal MSE rate for regression task, but only a sub-optimal rate of classification regret. We adopt some techniques introduced by Samworth et al.

(2012), and rigorously show that, under (α, β)-smooth condition (which is more general than the smooth condition imposed in our main theorems), interpolated-NN achieves optimal convergence rate for classification as well.

A ADDITIONAL NUMERICAL EXPERIMENT

In this experiment, instead of taking n = 2 10 only, we take n = 2 i for i = 6, . . . , 10 to see how the performance ratio and optimum k changes in γ for different n's. The phenomenon for classification is similar as regression so we only present regression. 

R [G(-bu -a) -1 {u<0} ]du = - 1 b a + R tdG(t) , R u[G(-bu -a) -1 {u<0} ]du = 1 b 2 a 2 2 + 1 2 R t 2 dG(t) + a R tdG(t) .

C PROOF OF A PRELIMINARY THEOREM FOR THEOREM 1

Define P 1 and P 2 (density as f 1 , f 2 ) as the conditional distributions of X given Y = 0, 1 respectively, and π 1 , π 2 are the marginal probability P (Y = 0) and P (Y = 1), then take

P = π 1 P 2 + π 2 P 2 , P = π 1 P 1 -π 2 P 2 , f (x) = π 1 f 1 (x) + π 2 f 2 (x)

, and also denote

Ψ(x) = π 1 f 1 (x) -π 2 f 2 (x).

Theorem 5 For regression, suppose that assumptions A.1, A.3, A.6, and A.7 hold. If k satisfies n β ≤ k ≤ n1-4β/d for some β > 0, we have 1

MSE(k, n, γ) = kE (R 1 /R k+1 ) -2γ ( k i=1 (R i /R k+1 ) -γ ) 2 σ 2 (X) +k 2 E a 2 (X)E 2 R 2 1 (R 1 /R k+1 ) -γ k i=1 (R i /R k+1 ) -γ X + o.

For classification, under A.1 to A.5, the excess risk w.r.t. γ becomes

Regret(k, n, γ) = 1 4k B 1 Es 2 k,n,γ (X) + S f (x 0 ) η(x 0 ) a 2 (x 0 )t 2 k,n,γ (x 0 )dVol d-1 (x 0 ) + o,

where

B 1 = S f (x 0 ) η(x 0 ) dVol d-1 (x 0 ), s 2 k,n,γ (x) = E(R 1 /R k+1 ) -2γ E 2 (R 1 /R k+1 ) -γ , t k,n,γ (x) = ER 2 1 (R 1 /R k+1 ) -γ E(R 1 /R k+1 ) -γ , a(x) = 1 f (x)d    d j=1 [η j (x)f j (x) + η j,j (x)f (x)/2]    .

C.1 REGRESSION:

Rewrite the interpolated-NN estimate at x given the distance to the k + 1th neighbor R k+1 , interpolation level γ as

S k,n,γ (x, R k+1 ) = k i=1 W i Y i ,

where the weighting scheme is defined as

W i = (R i /R k+1 ) -γ k i=1 (R i /R k+1 ) -γ

.

For regression, we decompose MSE into bias square and variance, where

E[(S k,n,γ (x, R k+1 ) -η(x)) 2 |x] = E k i=1 W i (η(X i ) -η(x)) 2 + E k i=1 W i (Y i -η(X i )) 2 ,

in which the bias square can be rewritten as

E k i=1 W i (η(X i ) -η(x)) 2 = kE(W 1 (η(X 1 ) -η(x))) 2 + (k 2 -k)E 2 (W 1 (η(X 1 ) -η(x))),

and the variance can be approximated as

E k i=1 W i (Y i -η(X i )) 2 = kEW 2 1 σ(X 1 ) 2 = kσ(x) 2 EW 2 1 + o.

Following a procedure similar as Step 1 for classification, i.e., use Taylor expansion to approximate the bias square, we obtain that for some function a, the bias becomes

EW 1 (η(X 1 ) -η(x)) = a(x)EW 2 1 R 2 1 + o. As a result, the MSE of interpolated-NN estimate given x becomes, E[(S k,n,γ (x, R k+1 ) -η(x)) 2 |x] = kσ(x) 2 EW 2 1 + k 2 a(x) 2 E 2 W 2 1 R 2 1 + o.

Finally we integrate MSE over the whole support.

C.2 CLASSIFICATION:

The main structure of the proof follows Samworth et al. (2012) . As the whole proof is long, we provide a brief summary in Section C.2.1 to describe things we will do in each step, then in Section C.2.2 we will present the details in each step.

C.2.1 BRIEF SUMMARY:

Step 1: denote i.i.d random variables Z i (x, R k+1 ) for i = 1, . . . , k where

Z i (x, R k+1 ) = (R i /R k+1 ) -γ (Y (X i ) -1/2) E(R i (x)/R k+1 (x)) γ

, then the probability of classifying as 0 becomes

P (S k,n,γ (x) < 1/2) = P k i=1 Z i (x, R k+1 ) < 0 .

The mean and variance of Z i (x, R k+1 ) can be obtained through Taylor expansion of η and density function of x:

E(Z 1 (x, R k+1 )) = η(x) + a(x) ER 2 1 (R 1 /R k+1 ) -γ E(R 1 /R k+1 ) -γ + o V ar(Z 1 (x, R k+1 )) = 1 4 E(R 1 /R k+1 ) -2γ E 2 (R 1 /R k+1 ) -γ + o,

for some function a. The smoothness conditions are assumed in A.4 and A.5.

Note that on the denominator of Z i , there is an expectation E(R i (x)/R k+1 (x)) γ . From later calculation in Corollary 1, the value of this expectation in fact has little changes given or without a condition of R k+1 , and it is little affected by x either.

Step 2: One can rewrite Regret as

R d P k i=1 W i Y i ≤ 1 2 -1 {η(x)<1/2} d P (x).

From Assumption A.2, A.4, the region where η is likely to make a wrong prediction is near {x|η(x) = 1/2}, thus we use tube theory to transform the integral of Regret over the d-dimensional space into a tube, i.e.,

R d P k i=1 W i Y i ≤ 1 2 -1{η(x) < 1/2} d P (x) = {1 + o(1)} S - t Ψ(x 0 ) P (S k,n (x t 0 ) < 1/2) -1 {t<0} dtdVol d-1 (x 0 ) + o.

The term will be defined in detail in appendix. Basically, when is within a suitable range, the integral over t will not depend on asymptotically.

Step 3: given R k+1 and x, the nearest k neighbors are i.i.d. random variables distributed in B(x, R k+1 ), thus we use non-uniform Berry-Esseen Theorem to get the Gaussian approximation of the probability of wrong prediction:

S - t Ψ(x 0 ) P (S k,n (x t 0 ) < 1/2) -1 {t<0} dtdVol d-1 (x 0 ) = S - t Ψ(x 0 ) E R k+1 Φ -kEZ 1 (x t 0 , R k+1 ) kV ar(Z 1 (x t 0 , R k+1 )) -1 {t<0} dtdVol d-1 (x 0 ) + o.

Step 4: take expectation over all R k+1 , and integral the Gaussian probability over the tube to obtain

S - t Ψ(x 0 ) E R k+1 Φ -kEZ 1 (x t 0 , R k+1 ) kV ar(Z 1 (x t 0 , R k+1 )) -1 {t<0} dtdVol d-1 (x 0 ) = S R t Ψ(x 0 )   Φ   - t η(x 0 ) s 2 k,n,γ /k - E(R 1 /R k+1 ) -γ a(x t 0 )R 2 1 s 2 k,n,γ /k   -1 {t<0}   dtdVol d-1 (x 0 ) + o = B 1 4k E(R 1 /R k+1 ) -2γ E 2 (R 1 /R k+1 ) -γ + S Φ(x 0 ) η(x 0 ) 2 a 2 (x 0 ) E 2 (R 1 /R k+1 ) -γ R 2 1 E 2 (R 1 /R k+1 ) -γ dVol d-1 (x 0 ) + o = 1 4k B 1 Es 2 k,n,γ + S Φ(x 0 ) η(x 0 ) 2 a 2 (x 0 )t 2 k,n,γ dVol d-1 (x 0 ) + o.

C.2.2 DETAILS:

Denote a d is the Euclidean ball volume parameter

a d = Vol(B(0, 1)) = (π/2) d/2 /Γ(d/2 + 1).

Define p = k/n and r 2p = sup

x ER 2k (x). Denote E be the set that there exists R i such that R i > r 2p , then for some constant c > 0,

r 2p = c a 1/d d c 1/d 0 2k n 1/d .

Hence from Claim A.5 in Belkin et al. (2018) , there exist c 1 and c 2 satisfying

P (E) ≤ c 1 k exp(-c 2 k).

Step 1: in this step, we figure out the i.i.d. random variable in our problem, and calculate its mean and variance given x.

Denote

EQUATION

)

then the dominant part we want to integrate becomes

P S k,n (x, R k+1 ) ≤ 1 2 = P k i=1 (R i /R k+1 ) -γ (Y (X i ) -1/2) < 0 R k+1 = P k i=1 Z i (x, R k+1 ) -kEZ 1 (x, R k+1 ) kV ar(Z 1 (x, R k+1 )) < -kEZ 1 (x, R k+1 ) kV ar(Z 1 (x, R k+1 )) R k+1 .

Therefore, one can adopt non-uniform Berry-Essen Theorem to approximate the probability using normal distribution. Unlike Samworth et al. ( 2012) in which EY (X i ) is calculated, since the i.i.d. item in non-uniform Berry-Essen Theorem is Z rather than Y , we now calculate mean and variance of Z. Under R k+1 ,

µ k,n,γ (x, R k+1 ) := EZ 1 (x, R k+1 ) = E(R 1 /R k+1 ) -γ (Y (X 1 ) -1/2) E(R 1 /R k+1 ) -γ = E(R 1 /R k+1 ) -γ (η(X 1 ) -1/2) E(R 1 /R k+1 ) -γ

, and

EZ 2 1 (x, R k+1 ) = E(R 1 /R k+1 ) -2γ (Y (X 1 ) -1/2) 2 E 2 (R 1 /R k+1 ) -γ = E(R 1 /R k+1 ) -2γ 4E 2 (R i /R k+1 ) -γ , σ 2 k,n,γ (x, R k+1 ) := V ar(Z 1 (x, R k+1 )).

Then the mean and variance of Z i can be calculated as

µ k,n (x t 0 , R k+1 ) = EZ 1 (x t 0 , R k+1 ) + 1 2 = E(R 1 /R k+1 ) -γ η(X 1 ) E(R 1 /R k+1 ) -γ + 1 2 = E(R 1 /R k+1 ) -γ η(x t 0 ) + (X 1 -x t 0 ) η(x t 0 ) + 1/2(X 1 -x t 0 ) η(x t 0 )(X 1 -x t 0 ) E(R 1 /R k+1 ) -γ + o(R 3 k+1 ) = η(x t 0 ) + E(R 1 /R k+1 ) -γ (X 1 -x t 0 ) η(x t 0 ) E(R 1 /R k+1 ) -γ + 1 2 E(R 1 /R k+1 ) -γ tr[η(x t 0 ) (X 1 -x t 0 )(X 1 -x t 0 ) ] E(R 1 /R k+1 ) -γ + O(R 3 k+1 ).

Fixing R 1 and R k+1 , we have

E((X 1 -x t 0 ) η(x t 0 )|R 1 ) = (x -x t 0 ) η(x t 0 )f (x|x t 0 , R k+1 )dx = (x -x t 0 ) η(x t 0 )[f (x t 0 |x t 0 , R 1 ) + f (x 0 |x t 0 , R 1 ) (x -x t 0 ) + o]dx = 0 + (x -x t 0 ) η(x t 0 )f (x t 0 |x t 0 , R 1 ) (x -x t 0 )dx + o = tr η(x t 0 )f (x t 0 |x t 0 , R 1 ) (x -x t 0 )(x -x t 0 ) dx + o (3)

and

EQUATION

Then taking function a(x) for x such that

a(x t 0 )R 2 1 = E((X 1 -x t 0 ) η(x t 0 )|R 1 ) + tr 1 2 η(x t 0 )E (X i -x t 0 )(X i -x t 0 ) |R 1 + o,

which can be satisfied through taking

a(x) = 1 f (x) 1+2/d d    d j=1 [ ηj (x) ḟj (x) + ηj,j (x)f (x)/2]    .

The difference caused by the value of R 1 is only a small order term.

Finally,

µ k,n,γ (x t 0 , R k+1 ) = η(x 0 ) + t η(x 0 ) + a(x 0 )t k,n,γ (R k+1 ) + o.

Step 2: in this step we construct a tube based on the set S = {x|η(x) = 1/2}, then figure out that the part of Regret outside this tube is a remainder term.

Assume k,n satisfies s k,n,γ = o( k,n ) and k,n = o(s k,n,γ k 1/2 ), then the residual terms throughout the following steps will be o(s 2 k,n,γ + t 2 k,n,γ ). Hence although the choice of k,n is different among choices of k and n, this does not affect the rate of Regret. Note that we ignore the arguments x and R k+1 as from A.2 and A.4,

s 2 k,n,γ (x, R k+1 ) 1/k and t k,,n,γ (x, R k+1 ) (k/n) 2/d for all x while R k+1 (k, n) 2/d in probability.

By Samworth et al. (2012) , recall that Ψ(x) = d(π 1 P 1 (x) -π 2 P 2 (x)), then

R d P k i=1 W i Y i ≤ 1 -1 {η(x)<1/2} d P (x) = {1 + o(1)} S k,n -k,n t Ψ(x 0 ) P (S k,n (x t 0 ) < 1/2) -1 {t<0} dtdVol d-1 (x 0 ) + r 1 ,

where

r 1 = R d \S k,n P k i=1 W i Y i ≤ 1 2 -1 {η(x)<1/2} d P (x) = R d \S k,n E R k+1 P k i=1 Z i (x, R k+1 ) < 0 -1 {η(x)<1/2} d P (x).

For r 1 ,

0 ≥ R d \S k,n ∩{x|η(x)<1/2} E R k+1 P k i=1 Z i (x, R k+1 ) ≤ 0 -1 {η(x)<1/2} d P (x) = - R d \S k,n ∩{x|η(x)<1/2} E R k+1 P k i=1 Z i (x, R k+1 ) -kEZ 1 (x, R k+1 ) > -kEZ 1 (x, R k+1 ) d P (x).

Using non-uniform Berry-Essen Theorem, when

EZ 3 1 (x, R k+1 ) < ∞, i.e. γ < d/3, it becomes - R d \S k,n ∩{x|η(x)<1/2} E R k+1 P k i=1 Z i (x, R k+1 ) -kEZ 1 (x, R k+1 ) > -kEZ 1 (x, R k+1 ) d P (x) ≤ R d \S k,n ∩{x|η(x)<1/2} E R k+1 Φ - √ kEZ 1 (x, R k+1 ) V ar(Z 1 (x, R k+1 )) d P (x) +c 1 1 √ k R d \S k,n ∩{x|η(x)<1/2} E R k+1 1 1 + k 3/2 |EZ 1 (x, R k+1 )| 3 d P (x), where Φ(x) = 1 -Φ(x). Since s k,n,γ (x, R k+1 ) = o( k,n ), r 1 = o(s 2 k,n,γ (x, R k+1 )). By the definition of k,n , we have exp(-2 k,n /s 2 k,n,γ (x, R k+1 )) = o(s 2 k,n,γ ) + o(1/k), inf x∈R d \S k,n |η(x) -1/2| ≥ c 3 k,n .

As a result, using Berstain inequality, r 1 is a smaller order term compared with s 2 k,n,γ when

s 2 k,n,γ (R k+1 ) = o(1), hence r 1 = o(s 2 k,n,γ ).

Step 3: now we apply non-uniform Berry-Esseen Theorem. From Step 3, we have

S k,n -k,n E R k+1 t Ψ(x 0 ) P (S k,n (x t 0 ) < 1/2|R k+1 ) -1 {t<0} dtdVol d-1 (x 0 ) = S k,n -k,n E R k+1 t Ψ(x 0 ) Φ -kEZ 1 (x t 0 , R k+1 ) kV ar(Z 1 (x t 0 , R k+1 )) -1 {t<0} dtdVol d-1 (x 0 ) + r 2 ,

where based on non-uniform Berry-Esseen Theorem:

EQUATION

r 2 ≤ S k,n -k,n E R k+1 t Ψ(x 0 ) kE|Z 1 (x t 0 , R k+1 )| 3 k 3/2 V ar 3/2 (Z 1 (x t 0 , R k+1 )) 1 1 + -kEZ1(x t 0 ,R k+1 ) √ kV ar(Z1(x t 0 ,R k+1 )) 3 dtdVol d-1 (x 0 ). For r 2 , r 2 ≤ S k,n -k,n E R k+1 t Ψ(x 0 ) kE|Z 1 (x t 0 , R k+1 )| 3 k 3/2 V ar 3/2 (Z 1 (x t 0 , R k+1 )) 1 1 + -kEZ1(x t 0 ,R k+1 ) √ kV ar(Z1(x t 0 ,R k+1 )) 3 dtdVol d-1 (x 0 ) = c 1 √ k S k,n -k,n E R k+1 t Ψ(x 0 ) 1 1 + -kEZ1(x t 0 ,R k+1 ) √ kV ar(Z1(x t 0 ,R k+1 )) 3 dtdVol d-1 (x 0 ) = c 2 √ k S |t|<s k,n,γ (x) t Ψ(x 0 ) dtdVol d-1 (x 0 ) + c 3 √ k S s k,n,γ (x)<|t|< k,n t Ψ(x 0 ) 1 1 + k 3/2 t 3 dtdVol d-1 (x 0 ) = o(s 2 k,n,γ ). Step 4: the integral becomes S E R k+1 k,n -k,n t Ψ(x 0 ) Φ -kEZ 1 (x t 0 , R k+1 ) kV ar(Z 1 (x t 0 , R k+1 )) -1 {t<0} dtdVol d-1 (x 0 ) = S E R k+1 k,n -k,n t Ψ(x 0 )   Φ   - t η(x 0 ) s 2 k,n,γ (x, R k+1 )/k - E(R 1 /R k+1 ) -γ a(x t 0 )R 2 1 s 2 k,n,γ (x, R k+1 )/k   -1 {t<0}   dtdVol d-1 (x 0 ) +r 3 + o = S E R k+1 R t Ψ(x 0 )   Φ   - t η(x 0 ) s 2 k,n,γ (x, R k+1 )/k - E(R 1 /R k+1 ) -γ a(x t 0 )R 2 1 s 2 k,n,γ (x, R k+1 )/k   -1 {t<0}   dtdVol d-1 (x 0 ) +r 3 + r 4 + o = S R t Ψ(x 0 )   Φ   - t η(x 0 ) s 2 k,n,γ (x)/k - E(R 1 /R k+1 ) -γ a(x t 0 )R 2 1 s 2 k,n,γ (x)/k   -1 {t<0}   dtdVol d-1 (x 0 ) +r 3 + r 4 + r 5 + o = B 1 4k E(R 1 /R k+1 ) -2γ E 2 (R 1 /R k+1 ) -γ + S f (x 0 ) η(x 0 ) a 2 (x 0 ) E 2 (R 1 /R k+1 ) -γ R 2 1 E 2 (R 1 /R k+1 ) -γ dVol d-1 (x 0 ) + r 3 + r 4 + r 5 + o.

Note that Ψ(x 0 ) / η(x 0 ) = 2f (x 0 ). The last step follows Proposition 4 and the fact that R k+1 does not affect the dominant parts. The term E((R 1 /R k+1 ) -γ |R k+1 ) is almost the same for all R k+1 . For the small order terms, following Samworth et al. ( 2012) we obtain

r 3 = S E R k+1 k,n -k,n t Ψ(x 0 ) Φ -kEZ 1 (x t 0 , R k+1 ) kV ar(Z 1 (x t 0 , R k+1 )) -Φ   - t η(x 0 ) s 2 (x, R k+1 )/k - E(R 1 /R k+1 ) -γ a(x t 0 )R 2 1 s 2 k,n,γ (x, R k+1 )/k   dtdVol d-1 (x 0 ), = o(s 2 k,n,γ + t 2 k,n,γ ),

and

r 4 = S Ψ(x 0 ) η(x 0 ) 2 E R k+1 R\[-k,n , k,n ] t Ψ(x 0 )   Φ   - t η(x 0 ) s 2 k,n,γ /k - E(R 1 /R k+1 ) -γ a(x t 0 )R 2 1 s 2 k,n,γ /k   -1 {v<0}   dtdVol d-1 (x 0 ) = o(s 2 k,n,γ ).

The term r 5 is the difference between the normal probability given R k+1 and the one after taking expectation. Similar with Cannings et al. ( 2017), for each x, when |t| < k,n , we have

E R k+1 Φ   - t η(x 0 ) s 2 k,n,γ (x, R k+1 )/k - E(R 1 /R k+1 ) -γ a(x t 0 )R 2 1 s 2 k,n,γ (x, R k+1 )/k   = Φ   - t η(x 0 ) s 2 k,n,γ (x, R k+1 )/k - E(R 1 /R k+1 ) -γ a(x t 0 )R 2 1 s 2 k,n,γ (x, R k+1 )/k   + O (kV ar(t k,n,γ (x, R k+1 ))) + o.

Following step 3 in Cannings et al. (2017) , we obtain

V ar(t k,n,γ (x, R k+1 )) ≤ 1 k 2 k j=1 E(η(X 1 ) -η(x)) 2 = O 1 k r 2 2p .

For the case when |t| s k,n,γ + t k,n,γ , differentiate normal cdf twice still leads to very small probability, thus for each x, we have

tE R k+1 Φ   - t η(x 0 ) s 2 k,n,γ (x, R k+1 )/k - E(R 1 /R k+1 ) -γ a(x t 0 )R 2 1 s 2 k,n,γ (x, R k+1 )/k   dt = tΦ   - t η(x 0 ) s 2 k,n,γ (x, R k+1 )/k - E(R 1 /R k+1 ) -γ a(x t 0 )R 2 1 s 2 k,n,γ (x, R k+1 )/k   dt + o(s 2 k,n,γ + t 2 k,n,γ ).

D PROOF OF THEOREM 1:

To show the ratio MSE(γ, n)/MSE(0, n) and Regret(γ, n)/Regret(0, n) asymptotically converges to a constant, we need to figure out the corresponding optimum k for each scenario.

For classification, given x, we know that if X follows multi-dimensional uniform distribution with density 1/f (x), for some constant c d that only depends on d,

E(R 1 /R k+1 ) -2γ = E R k+1 d R k+1 0 r R k+1 -2γ r d-1 dr + o = d d -2γ + o, E(R 1 /R k+1 ) -γ = d d -γ + o, E(R 1 /R k+1 ) -γ R 2 1 = E(R 1 /R k+1 ) 2-γ R 2 k+1 = c d k nf (x) 2 d d + 2 -γ + o.

Since R i → 0, this approximation still holds if X follow other distributions. As a result, through figuring out the optimum k for 0 and γ, we have

Regret(n, γ) Regret(n, 0) → 1 - γ 2 d(d -2γ) 4 d+4 (d -γ) 2 (d + 2 -γ) 2 (d + 2) 2 d 2 d d+4

.

For regression, one more step needed compared with classification is to evaluate

kE (R 1 /R k+1 ) -2γ ( k i=1 (R i /R k+1 ) -γ ) 2 Eσ(X) 2 + k 2 E a 2 (X)E 2 R 2 1 (R 1 /R k+1 ) -γ k i=1 (R i /R k+1 ) -γ

.

The sum of ratios k i=1 (R i /R k+1 ) -γ is hard to evaluated directly in the denominator, hence we use upper bound and lower bound on it. Since d -3γ > 0, using non-uniform Berry-Essen Theorem, given R k+1 , we have

P k i=1 (R i /R k+1 ) -γ -kE(R 1 /R k+1 ) -γ > ξ -Φ ξ kV ar((R 1 /R k+1 ) -γ ) R k+1 ≤ c 1 + (ξ/ √ k) 3 . Therefore, taking ξ = δ k kE(R 1 /R k+1 ) -γ , P k i=1 (R i /R k+1 ) -γ > (δ k + 1)kE(R 1 /R k+1 ) -γ R k+1 ≤ Φ δ k √ kE(R 1 /R k+1 ) -γ V ar((R 1 /R k+1 ) -γ ) R k+1 + c 1 + ( √ kδ k ) 3 .

Note that (R 1 /R k+1 ) -γ is always larger than 1, hence

E (R 1 /R k+1 ) -2γ ( k i=1 (R i /R k+1 ) -γ ) 2 ≤ E R k+1 E(R 1 /R k+1 ) -2γ (1 -δ k ) 2 k 2 E 2 (R 1 /R k+1 ) -γ +E R k+1 P k i=1 (R i /R k+1 ) -γ < (1 -δ k )kE(R 1 /R k+1 ) -γ R k+1 E(R 1 /R k+1 ) -2γ k 2 + o ≤ 1 k 2 (1 -δ k ) 2 E(R 1 /R k+1 ) -2γ E 2 (R 1 /R k+1 ) -γ + E(R 1 /R k+1 ) -2γ k 2 Φ δ k √ kE(R 1 /R k+1 ) -γ V ar((R 1 /R k+1 ) -γ ) + E(R 1 /R k+1 ) -2γ k 2 c 1 + ( √ kδ k ) 3 + o, while E (R 1 /R k+1 ) -2γ ( k i=1 (R i /R k+1 ) -γ ) 2 ≥ 1 k 2 (1 + δ k ) 2 E(R 1 /R k+1 ) -2γ E 2 (R 1 /R k+1 ) -γ - E(R 1 /R k+1 ) -2γ k 2 c 1 + ( √ kδ k ) 3 + o. Hence taking δ k such that δ k → 0 while δ k √ k → ∞, we have E (R 1 /R k+1 ) -2γ ( k i=1 (R i /R k+1 ) -γ ) 2 = 1 k 2 (d -γ) 2 d(d -2γ) + o,

and similarly

E R 2 1 (R 1 /R k+1 ) -γ k i=1 (R i /R k+1 ) -γ = 1 k k nf (x) 2 d d -γ d + 2 -γ + o.

After figuring out the optimum k for kNN and interpolated-NN, we finally obtain

MSE(n, γ) MSE(n, 0) → 1 γ 2 d(d -2γ) 4 d+4 (d -γ) 2 (d + 2 -γ) 2 (d + 2) 2 d 2 d d+4

.

E PROOF OF THEOREM 2:

The proof is similar with Theorem 1 in Sun et al. (2016) .

From the definition of CIS, we have

CIS(γ)/2 = R P (S k,n,γ (x) ≥ 1/2) (1 -P (S k,n,γ (x) ≥ 1/2)) dP (x) = R P (S k,n,γ (x) ≥ 1/2) -1 {η(x)≤1/2} dP (x) - R P 2 (S k,n,γ (x) ≥ 1/2) -1 {η(x)≤1/2} dP (x).

Based on the definition of Z i (x, R k+1 ) in ( 2), the derivation of µ k,n,γ (x, R k+1 ) and s k,n,γ (x, R k+1 ), follow the same procedures as in Theorem 5, we obtain

R P (S k,n,γ (x) ≥ 1/2) -1 {η(x)≤1/2} dP (x) = S k,n -k,n f (x t 0 ) E R k+1 P S k,n,γ (x t 0 ) < 1/2|R k+1 -1 {t<0} dtdVol d-1 (x 0 ) + o = S E R k+1 R f (x 0 )    Φ   - t η(x 0 ) s 2 k,n,γ /k - E(R 1 /R k+1 ) -γ a(x t 0 )R 2 1 s 2 k,n,γ /k   -1 {t<0}    dtdVol d-1 (x 0 ) + o,

and similarly,

R P 2 (S k,n,γ ≥ 1/2|R) -1 {η(x)≤1/2} d P (x) = S k,n -k,n f (x t 0 ) P 2 S k,n,γ (x t 0 ) < 1/2 -1 {t<0} dtdVol d-1 (x 0 ) + o = S E R k+1 R f (x 0 )    Φ 2   - t η(x 0 ) s 2 k,n,γ /k - E(R 1 /R k+1 ) -γ a(x t 0 )R 2 1 s 2 k,n,γ /k   -1 {t<0}    dtdVol d-1 (x 0 ) + o.

Adopting Proposition 4 and the fact that s k,n,γ (x, R k+1 ) is little changed by x and R k+1 , treating Φ and Φ 2 as two distribution functions, we have

CIS(γ) = B 1 √ π 1 √ k E s 2 k,n,γ (X) + o = B 1 √ π 1 √ k 1 + γ 2 d(d -2γ) + o.

The optimum k for kNN and interpolated-NN satisfies

k(γ) k(0) → (d + 2 -γ) 2 d(d -2γ) d 2 (d + 2) 2 d d+4

.

Finally we can obtain the asymptotic ratio of CIS'es.

F INTERPOLATION DOES NOT AFFECT THE RATE OF CONVERGENCE F.1 MODEL SETUP AND THEOREM:

The results in Section 3 are obtained based on smooth η and f , thus the Taylor expansions can be calculated. In this section, we will provide a weaker result under weaker assumptions as those in Chaudhuri & Dasgupta (2014) and Belkin et al. (2018) .

We first setup some assumptions:

A.1' X is a d-dimensional random variable on a compact set and satisfies regularity condition: let λ be the Lebesgue measure on R d , then there exists positive (c 0 , r 0 ) such that for any x in the support X , λ(X ∩ B(x, r)) ≥ c 0 λ(B(x, r)), for any 0 < r ≤ r 0 . A.4' Smoothness condition: |η(x) -η(y)| ≤ A x -y α for some α > 0.

A.5' The density of X is finite, and the model satisfies margin condition:

P (|η(X) -1/2| < t) ≤ 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 smoothness condition A.4' describes how smooth the function η is, which affects the minimax performance of kNN given a class of η's. 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 a 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, γ is within some suitable range, then excess risk of classification also reaches optimal:

Theorem 6 For regression, under A.1', A.3, A.4', A.5', MSE(γ, n) = O(n -2α/(2α+d) ). For classification, under A.1', A.3, A.4', A.5', Regret(γ, n) = O(n -α(β+1)/(2α+d) ). In addition, if β ≥ 2, when d -κ(β)γ > 0, where κ(β) denotes the smallest even number that is greater than β + 1, then we have Regret(γ, n) = O(n -α(β+1)/(2α+d) ).

The main proof of Theorem 6 follows the idea in Chaudhuri & Dasgupta (2014) , with Berstein inequality changing to non-uniform Berry Esseen Thoerem. For the regression part, we refer readers to Belkin et al. (2018) and Belkin et al. (2019c) .

From Theorem 6, 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 β < 2 and β ≥ 2, we technically impose different restrictions on γ. 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 a exponential tail, the residual part is only 1/(1 + |t| 3 ). As a result, when summing up t β+1 i /(1 + t 3 i ) for t i = 2 i , β -2 should be smaller than 0 in order to bound the summation. 2012) is a case where α = α . We approximate Eη(X) as η(x 0 ) + tr[η(x 0 )E(X -x 0 )(X -x 0 ) ] in Theorem 5, which indicates that we adopt smoothness α = 2, though α = 1. In addition, the margin condition parameter β = 1 under A.1 to A.5 becomes 1. Therefore, the optimum rate of O(n -α (β+1)/(2α +d) ) is O(n -4/(4+d) ). The over-fitting weighting scheme in fact leads to optimal rate for classification.

From the definition of R k,n and R * , when ∆(x) > ∆ 0 , we have

ER k,n (x) -R * (x) ≤ 2∆(x) P (r (k+1) > v 2p ) + P k i=1 W i Y (X i ) -η(x|R k+1 ) > ∆(x) -∆ 0 ≤ exp(-k/8) + 2∆(x)P k i=1 (R i /R k+1 ) -γ Y (X i ) > (η(x|R k+1 ) + ∆(x) -∆ 0 ) k i=1 (R i /R k+1 ) -γ = exp(-k/8) + 2∆(x)P k i=1 (R i /R k+1 ) -γ Y (X i ) -kE(R 1 /R k+1 ) -γ η(X 1 ) -(η(x|R k+1 ) + ∆(x) -∆ 0 ) k i=1 (R i /R k+1 ) -γ -E(R 1 /R k+1 ) -γ > k(η(x|R k+1 ) + ∆(x) -∆ 0 )E(R 1 /R k+1 ) -γ -kE(R 1 /R k+1 ) -γ η(X 1 ) = exp(-k/8) + 2∆(x)P k i=1 (R i /R k+1 ) -γ (Y (X i ) -η(x|R k+1 )) -(∆(x) -∆ 0 ) k i=1 (R i /R k+1 ) -γ -kE(R 1 /R k+1 ) -γ > k(∆(x) -∆ 0 )E(R 1 /R k+1 ) -γ . Since E k i=1 (R i /R k+1 ) -γ (Y (X i ) -η(x|R k+1 )) = 0, E(∆(x) -∆ 0 ) k i=1 (R i /R k+1 ) -γ -kE(R 1 /R k+1 ) -γ = 0,

we can use Markov inequality to the power of κ(β) to bound the probability. Denote

Z i (x) = (R i /R k+1 ) -γ (Y (X i )-η(x|R k+1 ))-(∆(x)-∆ 0 )(R i /R k+1 ) -γ +(∆(x)-∆ 0 )E(R 1 /R k+1 ) -γ

for simplicity. Note that V ar(Z 1 (x)) = O(∆(x) -∆ 0 ).

For different settings of β and γ, the following steps have the same logic but different details:

Case 1: β ≤ 1 and γ < d/3: Considering the problem that the upper bound can be much greater than 1 when ∆(x) is small, we define ∆ i = 2 i ∆ 0 , taking i 0 = min{i ≥ 1| (∆ i -∆ 0 ) 2 > 1/k}. In this situation, since EZ 3 1 (x) < ∞, we can adopt non-uniform Berry-Essen Theorem for the proof:

ER k,n (X) -R * (X) = E(R k,n (X) -R * (X))1 {∆(X)≤∆i 0 } +E(R k,n (X) -R * (X))1 {∆(X)>∆i 0 } ≤ 2∆ i0 P (∆(X) ≤ ∆ i0 ) + exp(-k/8) +4E ∆(X)1 {∆i 0 <∆(X)} Φ √ k(∆(x) -∆ 0 ) V ar(Z 1 (X)|X) +4E ∆(X)1 {∆i 0 <∆(X)} c 1 √ k 1 1 + k 3/2 (∆(x) -∆ 0 ) 3 .

Under review as a conference paper at ICLR 2020

The two terms from Berry-Essen Theorem becomes E ∆(X)1 {∆i<∆(X)<∆i+1} c 1 √ k

1 1 + k 3/2 (∆(x) -∆ 0 ) 3 ≤ ∆ β+1 i+1 c 1 √ k 1 1 + k 3/2 (∆ i -∆ 0 ) 3 = 1 k (β+1)/2 ( √ k∆ i+1 ) β+1 c 1 √ k 1 1 + k 3/2 (∆ i -∆ 0 ) 3 , together with E ∆(X)1 {∆i 0 <∆(X)} Φ √ k(∆(x) -∆ 0 ) V ar(Z 1 (X)|X) ≤ E ∆(X)1 {∆i 0 <∆(X)} Φ c 3 √ k(∆(x) -∆ 0 ) ≤ c 4 ∆ β+1 i+1 √ k(∆ i -∆ 0 ) exp -c 2 3 k(∆ i -∆ 0 ) 2 .

The upper bound is larger than 1 if

∆ i ≤ c 5 / √ k. When ∆ i > c 5 / √ k, ∆ β+1 i+1 (∆i-∆0) exp -c 2 3 k(∆ i -∆ 0 ) 2 ∆ β+1 i (∆i-1-∆0) exp (-c 2 3 k(∆ i-1 -∆ 0 ) 2 ) = 2 β+1 2 i-1 -1 2 i -1 exp -c 2 3 k(∆ i -∆ 0 ) 2 exp (-c 2 3 k(∆ i-1 -∆ 0 ) 2 ) ≤ 2 β exp -c 2 3 k(∆ i -∆ 0 ) 2 exp (-c 2 3 k(∆ i-1 -∆ 0 ) 2 ) < 1/2.

Therefore the sum of the excess risk can be bounded. When β < 2, β -2 < 0, hence E ∆(X)1 {∆i<∆(X)<∆i+1} c 1 √ k

1 1 + k 3/2 (∆(x) -∆ 0 ) 3 ≤ O 1 k (β+2)/2 i≥i0 [ √ k(∆ i+1 -∆ i )] β-2 ≤ O 1 k (β+2)/2 i≥i0 ( √ k∆ i0 ) β-2 2 i(β-2) = O 1 k (β+2)/2 k (β-2)/2 ∆ β-2 i0 = O ∆ β-2 i0 k 2 ,

and

E ∆(X)1 {∆i 0 <∆(X)} Φ √ k(∆(x) -∆ 0 ) V ar(Z 1 (X)|X) ≤ O 1 √ k i≥i0 ∆ β+1 i+1 (∆ i -∆ 0 ) exp -c 2 3 k(∆ i -∆ 0 ) 2 = O 1 √ k ∆ β i0+1 exp -c 2 3 k(∆ i0 -∆ 0 ) 2 .

Recall that ∆ i0 > ∆ 0 and ∆ 2 i0 > 1/k, hence when ∆ 2 i0 = O(1/k), we can obtain the minimum upper bound

ER k,n (X) -R * (X) ≤ O(∆ β+1 0 ) + O 1 k (β+1)/2

.

Taking k (n 2α/(2α+d) ), the upper bound becomes O(n -α(β+1)/(2α+d) ).

Case 2: γ < d/κ(β):

ER k,n (X) -R * (X) = E(R k,n (X) -R * (X))1 {∆(X)≤∆i 0 } +E(R k,n (X) -R * (X))1 {∆(X)>∆i 0 } ≤ 2∆ i0 P (∆(X) ≤ ∆ i0 ) + exp(-k/8) +4E   ∆(X)1{∆ i 0 <∆(X)} E k i=1 Z i (X) κ(β) (∆(X) -∆ 0 ) κ(β) k κ(β) E κ(β) (R 1 /R k+1 ) -γ    ,

while for some constant c 1 > 0,

E   ∆(X)1{∆ i<∆(X )≤∆i+1} E k i=1 Z i (X) κ(β) (∆(X) -∆ 0 ) κ(β) k κ(β) E κ(β) (R 1 /R k+1 ) -γ    ≤ E ∆(X)1 {∆i<∆(X)≤∆i+1} E k i=1 Z i (X) κ(β) (∆ i -∆ 0 ) κ(β) k κ(β) E κ(β) (R 1 /R k+1 ) -γ ≤ ∆ i+1 P (∆(X) ≤ ∆ i+1 ) E k i=1 Z i (X) κ(β) (∆ i -∆ 0 ) κ(β) k κ(β) E κ(β) (R 1 /R k+1 ) -γ ≤ c 1 1 k κ(β)/2 ∆ β+1 i+1 /(∆ i -∆ 0 ) κ(β) ,

where the last inequality is obtained since d -κ(β)γ > 0. Note that κ(β) > β + 1, thus for some 0 < c < 1, ∆ β+1 i+1 /(∆ i -∆ 0 ) κ(β) ∆ β+1 i /(∆ i-1 -∆ 0 ) κ(β) < c.

(5)

Therefore the sum of the excess risk for can be bounded, where

E   ∆(X)1{∆ i 0 <∆(X)} E k i=1 Z i (X) κ(β) (∆(X) -∆ 0 ) κ(β) k κ(β) E κ(β) (R 1 /R k+1 ) -γ    ≤ O 1 k κ(β)/2 i≥i0 ∆ β+1 i+1 /(∆ i -∆ 0 ) κ(β) (6) ≤ O ∆ β+1 i0 .

Recall that ∆ i0 > ∆ 0 and ∆ 2 i0 > 1/k, hence when ∆ 2 i0 = O(1/k), we can obtain the minimum upper bound

ER k,n (X) -R * (X) ≤ O(∆ β+1 0 ) + O 1 k (β+1)/2

.

Taking k (n 2α/(2α+d) ), the upper bound becomes O(n -α(β+1)/(2α+d) ).

:

The notation "A + o" is understood as A + o = A(1 + o(1)).

Figures and Tables:

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).

Figure 2: Testing Error with Model Complexity / Interpolation Level. The curve within over-fitting regime is depicted based on the theoretical pattern of performance ratio given d = 2.

Figure 3: Performance ratio curve for n = 1024 and d = 2 (left) and 5 (right), solid line is theoretical value PR(d, γ), dashed line is simulation results for Regret ratio, dashed line with dots is simulation results for MSE ratio.

Figure 4: Comparison between theoretical CIS ratio PR(d, γ) (solid line) and simulated CIS ratio (dashed line), under d = 2 (left) and 5 (right).

Figure 5 summarizes the change of MSE and optimum choice of k with respect to different choices of n and γ/d, when d = 2. The plot corresponding to d = 5 is 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 k than k-NN.

Figure 5: Change of MSE and optimal k

As Chaudhuri & Dasgupta (2014) mentioned, our smoothness condition (A.4') is in fact a sufficient condition. In Theorem 6, what we really need is some constant α such that |η(x) -η(B(x, r))| ≤ Lr α . The result in Samworth et al. (

Prediction Error of kNN, interpolated-NN under the best choice of γ, together with the value of the best γ for interpolated-NN. payment information. The built-in data set of digits in sklearn(Pedregosa et al., 2011) contains 1,797 samples of 8×8 images. For images in MNIST are 26 × 26, we will use part of it in our 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 to 9 as 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

Table content: <table><tr><td colspan="3">Under review as a conference paper at ICLR 2020</td><td/><td/></tr><tr><td>Data</td><td>d</td><td colspan="3">Error (γ = 0) Error (best γ/d) best γ/d</td></tr><tr><td>Abalone</td><td>7</td><td>0.22239</td><td>0.22007</td><td>0.3</td></tr><tr><td>HTRU2</td><td>8</td><td>0.02315</td><td>0.0226</td><td>0.2</td></tr><tr><td>Credit</td><td>23</td><td>0.1933</td><td>0.19287</td><td>0.05</td></tr><tr><td>Digit</td><td>64</td><td>0.01745</td><td>0.01543</td><td>0.25</td></tr><tr><td colspan="2">MNIST 784</td><td>0.04966</td><td>0.04656</td><td>0.05</td></tr></table>

And our work essentially quantify such a bias-variance balance in a 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 to a more complete picture of double descent phenomenon. Yue Xing, Qifan Song, and Guang Cheng. Statistical optimality of interpolated nearest neighbor algorithms. arXiv preprint arXiv:1810.02814, 2018. 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.

Table content: <table/>

Peer review (iclr2020):
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). Under 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). Overall, 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. In 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).