Published on Fri Oct 05 2018

Statistical Optimality of Interpolated Nearest Neighbor Algorithms

Yue Xing, Qifan Song, Guang Cheng

In the era of deep learning, understanding over-fitting phenomenon becomes increasingly important. Over-fitting can greatly reduce the estimation bias, while not increasing the estimation variance too much. To illustrate the above idea, we prove that the proposed interpolated nearest neighbor algorithm achieves the optimal rate in both

0
0
0
Abstract

In the era of deep learning, understanding over-fitting phenomenon becomes increasingly important. It is observed that carefully designed deep neural networks achieve small testing error even when the training error is close to zero. One possible explanation is that for many modern machine learning algorithms, over-fitting can greatly reduce the estimation bias, while not increasing the estimation variance too much. To illustrate the above idea, we prove that the proposed interpolated nearest neighbor algorithm achieves the minimax optimal rate in both regression and classification regimes, and observe that they are empirically better than the traditional nearest neighbor method in some cases.

Wed Sep 25 2019
Machine Learning
Benefit of Interpolation in Nearest Neighbor Algorithms
Over-parameterized models attract much attention in the era of data science and deep learning. The major goal of this work is to sharply quantify the benefit of data interpolation. We consider a class of data-interpolated weighting schemes and then carefully characterize their performance.
0
0
0
Wed Oct 29 2008
Machine Learning
Choice of neighbor order in nearest-neighbor classification
The th-nearest neighbor rule is arguably the simplest and most intuitivelyappealing nonparametric classification procedure. We consider two models, Poisson and Binomial, for the training samples.
0
0
0
Tue Nov 04 2014
Machine Learning
Classification with the nearest neighbor rule in general finite dimensional spaces: necessary and sufficient conditions
The nearest neighbor rule is a popular flexible andintuitive method in non-parametric situations. We identify two necessary and sufficient conditions to achieve uniform consistency rates of classification and to derive sharp estimates.
0
0
0
Tue Oct 22 2019
Machine Learning
Minimax Rate Optimal Adaptive Nearest Neighbor Classification and Regression
K Nearest Neighbor (kNN) method is a simple and popular statistical method for classification and regression. We show that there is a gap between the convergence rate achieved by the standard kNN method and the minimax bound. To close this gap, we propose an adaptive kNN method,
0
0
0
Mon Jun 30 2014
Machine Learning
Rates of Convergence for Nearest Neighbor Classification
Nearest neighbor methods are a popular class of nonparametric estimators with desirable properties. Prior work on convergence rates for nearest neighbor classification has not fully reflected these subtle properties. We provideinite-sample, distribution-dependent rates of convergence under minimal assumptions.
0
0
0
Wed Mar 21 2007
Computer Vision
A Note on Approximate Nearest Neighbor Methods
0
0
0