Benefit of Interpolation in Nearest Neighbor Algorithms
Not on the map. Why?
Abstract (arXiv)
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 citepbelkin2018does 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) k-NN algorithm. In the end, the universality of our results, such as change of distance measure and corrupted testing data, will also be discussed.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 34 of its 52 references that are in the map. First posted on arXiv 23 Feb 2022.
Builds on
34 of 52 references.
References · 34
- 2016Understanding deep learning requires rethinking generalizationcited by 1,657
- 2018Reconciling modern machine learning practice and the bias-variance trade-offcited by 919
- 2017Spectrally-normalized margin bounds for neural networkscited by 681
- 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 655
- 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 572
- 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 562
- 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
- 2019Benign Overfitting in Linear Regressioncited by 544
- 2019Surprises in High-Dimensional Ridgeless Least Squares Interpolationcited by 508
- 2017A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networkscited by 309
- 2018Stronger generalization bounds for deep nets via a compression approachcited by 306
- 2018On the Optimization of Deep Networks: Implicit Acceleration by Overparameterizationcited by 280
22 more
- 2019Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networkscited by 221
- 2019Two models of double descent for weak featurescited by 194
- 2018On the Power of Over-parametrization in Neural Networks with Quadratic Activationcited by 102
- 2018Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolatecited by 99
- 2018Does data interpolation contradict statistical optimality?cited by 95
- 2020Finite-sample Analysis of Interpolating Linear Classifiers in the Overparameterized Regimecited by 81
- 2018Stability and Convergence Trade-off of Iterative Optimization Algorithmscited by 53
- 2021Risk Bounds for Over-parameterized Maximum Margin Classification on Sub-Gaussian Mixturescited by 48
- 2014Rates of Convergence for Nearest Neighbor Classificationcited by 45
- 2015Explaining the Success of AdaBoost and Random Forests as Interpolating Classifierscited by 45
- 2020Multiple Descent: Design Your Own Generalization Curvecited by 44
- 2020How benign is benign overfitting?cited by 40
- 2020The Curious Case of Adversarially Robust Models: More Data Can Help, Double Descend, or Hurt Generalizationcited by 39
- 2020Kernel regression in high dimensions: Refined analysis beyond double descentcited by 39
- 2017Analyzing the Robustness of Nearest Neighbors to Adversarial Examplescited by 36
- 2016Diverse Neural Network Learns True Target Functionscited by 33
- 2021Towards an Understanding of Benign Overfitting in Neural Networkscited by 29
- 2017Local nearest neighbour classification with applications to semi-supervised learningcited by 17
- 2017Achieving the time of 1-NN, but the accuracy of k-NNcited by 10
- 2018Statistical Optimality of Interpolated Nearest Neighbor Algorithmscited by 3
- 2020Predictive Power of Nearest Neighbors Algorithm under Random Perturbationcited by 2
- 2020Minimum-Norm Adversarial Examples on KNN and KNN-Based Modelscited by 2
Built on by
Citing papers per year: 2022: 1.
1 paper.