Minimax Rate Optimal Adaptive Nearest Neighbor Classification and Regression

DOI10.1109/TIT.2021.3062078MaRDI QIDQ5001608zbMATH OpenOpenAlexFDO

Authors Puning Zhao, Lifeng Lai

Publication date 22 July 2021

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1910.10513

zbMATH Keywords

adaptive \(k\) nearest neighbor (kNN) methodclassificationconvergence rateminimax lower boundregression

Mathematics Subject Classification ID

Nonparametric regression and quantile regression (62G08) Classification and discrimination; cluster analysis (statistical aspects) (62H30)

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 minimax lower bound.

Cited in

(8)

• Adaptive covariate acquisition for minimizing total cost of classification
• TNN: a transfer learning classifier based on weighted nearest neighbors
• Robust minium bias iteration algorithms for classification ratemaking and loss reserving
• scientific article; zbMATH DE number 6999890 (Why is no real title available?)
• scientific article; zbMATH DE number 7583836 (Why is no real title available?)
• Classical and fast parameters tuning in nearest neighbors with stop condition
• Conditional mean embedding and optimal feature selection via positive definite kernels
• Minimum discrepancy principle strategy for choosing k in k-NN regression

This page was built for publication: Minimax Rate Optimal Adaptive Nearest Neighbor Classification and Regression

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5001608)