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.
This paper is about interpolation schemes in the particular case of the
Nearest Neighbor algorithm. The authors investigate the benet, mainly
theoretical, of the proposed interpolation. They study minimax rates of
the proposed interpolated-NN for both classication and regression. The
statistical stability of the Interpolated-NN is adressed.
The paper is easy to understand and correctly written. Nevertheless,
It is a particular case of ( \Overtting or perfect tting? Risk bounds for
classication and regression rules that interpolate", Belkin, M., Hsu, D.,
and Mitra, P. (2018a)) with an explicit interpolation schemes given by the
euclidien distance power gamma. It appears as an application of the above
paper which brings only few theoretical advantages and not enough to justify,
although intuitive, the choice of these weights. Only few discussions and
no comparison to others bounds (as those in the above paper) of the main
theorem are given. The paper is too much incremental from the papers of
Belkin et al. (2018) and Xing et al. (2018) and the benets of the proposed
interpolation are limited. Furthermore, the empirical performance of the
interpolate-NN is clearly not convincing and show no signicant practical
advantages of the proposed method. As the goal of the paper is clearly
theoretical, the 'real data analysis' part is not necessary in my opinion.