Rates of Convergence for Nearest Neighbor Classification

Abstract

Nearest neighbor methods are a popular class of nonparametric estimators with several desirable properties, such as adaptivity to different distance scales in different regions of space. Prior work on convergence rates for nearest neighbor classification has not fully reflected these subtle properties. We analyze the behavior of these estimators in metric spaces and provide finite-sample, distribution-dependent rates of convergence under minimal assumptions. As a by-product, we are able to establish the universal consistency of nearest neighbor in a broader range of data spaces than was previously known. We illustrate our upper and lower bounds by introducing smoothness classes that are customized for nearest neighbor classification.

References in corpus (1)

• Fast learning rates for plug-in classifiers

Cited by in corpus (31)

• Analyzing the Robustness of Nearest Neighbors to Adversarial Examples
• Does data interpolation contradict statistical optimality?
• Analysis of k-Nearest Neighbor Distances with Application to Entropy Estimation
• Class-Weighted Classification: Trade-offs and Robust Approaches
• An adaptive nearest neighbor rule for classification
• Universal consistency and rates of convergence of multiclass prototype algorithms in metric spaces
• Minimax Rate Optimal Adaptive Nearest Neighbor Classification and Regression
• Under-bagging Nearest Neighbors for Imbalanced Classification
• Nearest Neighbor and Kernel Survival Analysis: Nonasymptotic Error Bounds and Strong Consistency Rates
• Nearest-Neighbor Sample Compression: Efficiency, Consistency, Infinite Dimensions
• Classification with unknown class-conditional label noise on non-compact feature spaces
• Universal Bayes consistency in metric spaces
• Adaptive Non-Parametric Regression With the $K$-NN Fused Lasso
• Functions with average smoothness: structure, algorithms, and learning
• Deep k-NN for Noisy Labels
• On Convergence of Nearest Neighbor Classifiers over Feature Transformations
• Expressivity of expand-and-sparsify representations
• Fast rates in structured prediction
• Locally Adaptive Label Smoothing for Predictive Churn
• Optimal choice of $k$ for $k$-nearest neighbor regression
• Predictive Power of Nearest Neighbors Algorithm under Random Perturbation
• Distributed Nearest Neighbor Classification
• Nonparametric adaptive active learning under local smoothness condition
• Multiclass Classification via Class-Weighted Nearest Neighbors
• K-NN active learning under local smoothness assumption
• Fast and Bayes-consistent nearest neighbors
• Distributed Adaptive Nearest Neighbor Classifier: Algorithm and Theory
• Extrapolation Towards Imaginary $0$-Nearest Neighbour and Its Improved Convergence Rate
• Consistent Non-Parametric Methods for Maximizing Robustness
• A Nearest Neighbor Characterization of Lebesgue Points in Metric Measure Spaces
• Exploring Adversarial Examples for Efficient Active Learning in Machine Learning Classifiers