# Local nearest neighbour classification with applications to semi-supervised learning

arXiv: https://arxiv.org/abs/1704.00642 · HTML: https://mlsanity.com/paper/1704.00642/

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Apr 2017.

## Built on by (most cited first, 17 of 17)

- [Contextual Bandits for Unbounded Context Distributions](https://mlsanity.com/paper/2408.09655/) (2024)
- [Optimal Binary Classification Beyond Accuracy](https://mlsanity.com/paper/2107.01777/) (2021)
- [Nearest Neighbor Sampling for Covariate Shift Adaptation](https://mlsanity.com/paper/2312.09969/) (2023)
- [Adaptive transfer learning](https://mlsanity.com/paper/2106.04455/) (2021)
- [Unlabeled Data Help: Minimax Analysis and Adversarial Robustness](https://mlsanity.com/paper/2202.06996/) (2022)
- [Learning with User-Level Local Differential Privacy](https://mlsanity.com/paper/2405.17079/) (2024)
- [Nearest neighbor empirical processes](https://mlsanity.com/paper/2110.15083/) (2021)
- [Sharp-SSL: Selective high-dimensional axis-aligned random projections for semi-supervised learning](https://mlsanity.com/paper/2304.09154/) (2023)
- [Enhancing Learning with Label Differential Privacy by Vector Approximation](https://mlsanity.com/paper/2405.15150/) (2024)
- [Learning Counterfactual Distributions via Kernel Nearest Neighbors](https://mlsanity.com/paper/2410.13381/) (2024)
- [Benefit of Interpolation in Nearest Neighbor Algorithms](https://mlsanity.com/paper/2202.11817/) (2022)
- [Fast and Multiphase Rates for Nearest Neighbor Classifiers](https://mlsanity.com/paper/2308.08247/) (2023)
- [Adaptively-weighted Nearest Neighbors for Matrix Completion](https://mlsanity.com/paper/2505.09612/) (2025)
- [Comments on Leo Breiman's paper 'Statistical Modeling: The Two Cultures' (Statistical Science, 2001, 16(3), 199-231)](https://mlsanity.com/paper/2103.11327/) (2021)
- [Profitable Strategy Design for Trades on Cryptocurrency Markets with Machine Learning Techniques](https://mlsanity.com/paper/2105.06827/) (2021)
- [Bagged k-Distance for Mode-Based Clustering Using the Probability of Localized Level Sets](https://mlsanity.com/paper/2210.09786/) (2022)
- [N2: A Unified Python Package and Test Bench for Nearest Neighbor-Based Matrix Completion](https://mlsanity.com/paper/2506.04166/) (2025)

## Abstract (arXiv)

We derive a new asymptotic expansion for the global excess risk of a local-k-nearest neighbour classifier, where the choice of k may depend upon the test point. This expansion elucidates conditions under which the dominant contribution to the excess risk comes from the decision boundary of the optimal Bayes classifier, but we also show that if these conditions are not satisfied, then the dominant contribution may arise from the tails of the marginal distribution of the features. Moreover, we prove that, provided the d-dimensional marginal distribution of the features has a finite ρth moment for some ρ > 4 (as well as other regularity conditions), a local choice of k can yield a rate of convergence of the excess risk of O(n-4/(d+4)), where n is the sample size, whereas for the standard k-nearest neighbour classifier, our theory would require d ≥ 5 and ρ > 4d/(d-4) finite moments to achieve this rate. These results motivate a new k-nearest neighbour classifier for semi-supervised learning problems, where the unlabelled data are used to obtain an estimate of the marginal feature density, and fewer neighbours are used for classification when this density estimate is small. Our worst-case rates are complemented by a minimax lower bound, which reveals that the local, semi-supervised k-nearest neighbour classifier attains the minimax optimal rate over our classes for the excess risk, up to a subpolynomial factor in n. These theoretical improvements over the standard k-nearest neighbour classifier are also illustrated through a simulation study.