Efficient Classification with Adaptive KNN
Puning Zhao, Lifeng Lai
Abstract
In this paper, we propose an adaptive kNN method for classification, in which different k are selected for different test samples. Our selection rule is easy to implement since it is completely adaptive and does not require any knowledge of the underlying distribution. The convergence rate of the risk of this classifier to the Bayes risk is shown to be minimax optimal for various settings. Moreover, under some special assumptions, the convergence rate is especially fast and does not decay with the increase of dimensionality.
Ask about this paper
Your agent reads all of it.
Lune indexed this paper to the last equation, along with the top-tier papers that cite it. Ask a question and the answer quotes them.
Your agent calls
Luneget_paper_fulltext
Free to start. No credit card required.
Terminal
Install the CLIlune papers fulltext 2b35fdf3-94f4-4944-a566-360bb93ce98dCited by top-tier papers2
- Contextual Bandits for Unbounded Context DistributionsPuning Zhao, Rongfei Fan, Shaowei Wang, Li Shen et al.ICML 2025
- Enhancing Learning with Label Differential Privacy by Vector ApproximationPuning Zhao, Jiafei Wu, Zhe Liu, Li Shen et al.ICLR 2025
Related papers
- Extrapolation Towards Imaginary 0-Nearest Neighbour and Its Improved Convergence RateAkifumi Okuno, Hidetoshi ShimodairaNeurIPS 2020 · 2 citations
- A Two-Stage Active Learning Algorithm for k-Nearest NeighborsNicholas Rittler, Kamalika ChaudhuriICML 2023 · 3 citations
- Joint Evidential -Nearest Neighbor ClassificationChaoyu Gong, Yongbin Li, Yong Liu, Pei-hong Wang et al.ICDE 2022 · 4 citations
- Consistency of the kn-nearest neighbor rule under adaptive samplingRobi Bhattacharjee, Geelon So, Sanjoy DasguptaNeurIPS 2025
- On Convergence of Nearest Neighbor Classifiers over Feature TransformationsLuka Rimanic, Cédric Renggli, Bo Li, Ce ZhangNeurIPS 2020 · 18 citations
