Minimax Rate Optimal Adaptive Nearest Neighbor Classification And Regression

Abstract

k Nearest Neighbor (kNN) method is a simple and popular statistical method for classification and regression. For both classification and regression problems, existing works have shown that, if the distribution of the feature vector has bounded support and the probability density function is bounded away from zero in its support, the convergence rate of the standard kNN method, in which k is the same for all test samples, is minimax optimal. On the contrary, if the distribution has unbounded support, 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, in which different k is selected for different samples. Our selection rule does not require precise knowledge of the underlying distribution of features. The new proposed method significantly outperforms the standard one. We characterize the convergence rate of the proposed adaptive method, and show that it matches the min

Stats

• citations12
• S2 citations—
• github stars0
• HF likes0
• heat score8.35
• arxiv keyzhao2019minimax

Related papers

• An Adaptive Nearest Neighbor Rule For Classification (2019)0.00
• Minimax Optimal Algorithms With Fixed-\(k\)-nearest Neighbors (2022)0.00
• Adaptive Nearest Neighbor: A General Framework For Distance Metric Learning (2019)0.00
• Distributionally Robust Weighted \(k\)-nearest Neighbors (2020)0.00
• Interpretable Locally Adaptive Nearest Neighbors (2020)3.58
• Adaptive Estimation For Approximate K-nearest-neighbor Computations (2019)0.00
• A Fast And Easy Regression Technique For K-nn Classification Without Using Negative Pairs (2018)0.00
• On Convergence Of Nearest Neighbor Classifiers Over Feature Transformations (2020)0.00