Benefit of Interpolation in Nearest Neighbor Algorithms
From MaRDI portal
Abstract: In some studies citep[e.g.,][]{zhang2016understanding} of deep learning, it is observed that over-parametrized deep neural networks achieve a small testing error even when the training error is almost zero. Despite numerous works towards understanding this so-called "double descent" phenomenon citep[e.g.,][]{belkin2018reconciling,belkin2019two}, in this paper, we turn into another way to enforce zero training error (without over-parametrization) through a data interpolation mechanism. Specifically, we consider a class of interpolated weighting schemes in the nearest neighbors (NN) algorithms. By carefully characterizing the multiplicative constant in the statistical risk, we reveal a U-shaped performance curve for the level of data interpolation in both classification and regression setups. This sharpens the existing result citep{belkin2018does} that zero training error does not necessarily jeopardize predictive performances and claims a counter-intuitive result that a mild degree of data interpolation actually {em strictly} improve the prediction performance and statistical stability over those of the (un-interpolated) -NN algorithm. In the end, the universality of our results, such as change of distance measure and corrupted testing data, will also be discussed.
Recommendations
- Evaluation of Rounding Functions in Nearest Neighbor Interpolation
- Near-interpolation
- STABLE COMPUTATION OF NATURAL NEIGHBOR INTERPOLATION
- Computational Science and Its Applications – ICCSA 2004
- On computing the nearest neighbor interchange distance
- scientific article; zbMATH DE number 3972418
- scientific article; zbMATH DE number 1217658
- Some methods of replacing the nearest neighbor method
- Nearest neighbour approach in the least-squares data imputation algorithms
Cites work
- scientific article; zbMATH DE number 7370646 (Why is no real title available?)
- 10.1162/153244302760200704
- Benign overfitting in linear regression
- Convergence of the nearest neighbor rule
- Distribution-free exponential error bound for nearest neighbor pattern classification
- Fast learning rates for plug-in classifiers
- Fat-shattering and the learnability of real-valued functions
- Local nearest neighbour classification with applications to semi-supervised learning
- Optimal aggregation of classifiers in statistical learning.
- Optimal dual martingales, their analysis, and application to new algorithms for Bermudan products
- Optimal weighted nearest neighbour classifiers
- Reconciling modern machine-learning practice and the classical bias-variance trade-off
- Scikit-learn: machine learning in Python
- Surprises in high-dimensional ridgeless least squares interpolation
- Two models of double descent for weak features
Cited in
(6)- A local model reduction method based on k-nearest-neighbors for parametrized nonlocal problems
- Just interpolate: kernel ``ridgeless regression can generalize
- TNN: a transfer learning classifier based on weighted nearest neighbors
- A model reduction method for parametric dynamical systems defined on complex geometries
- scientific article; zbMATH DE number 7625163 (Why is no real title available?)
- A dynamic mode decomposition-based Kalman filter for Bayesian inverse problem of nonlinear dynamical systems
This page was built for publication: Benefit of Interpolation in Nearest Neighbor Algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5089734)
