# A PAC-Bayesian Analysis of Distance-Based Classifiers: Why Nearest-Neighbour works!

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 0 of its 16 references that are in the map.
- First posted on arXiv 28 Sep 2021.

## Abstract (arXiv)

Abstract We present PAC-Bayesian bounds for the generalisation error of the K-nearest-neighbour classifier (K-NN). This is achieved by casting the K-NN classifier into a kernel space framework in the limit of vanishing kernel bandwidth. We establish a relation between prior measures over the coefficients in the kernel expansion and the induced measure on the weight vectors in kernel space. Defining a sparse prior over the coefficients allows the application of a PAC-Bayesian folk theorem that leads to a generalisation bound that is a function of the number of redundant training examples: those that can be left out without changing the solution. The presented bound requires to quantify a prior belief in the sparseness of the solution and is evaluated after learning when the actual redundancy level is known. Even for small sample size (m ~ 100) the bound gives non-trivial results when both the expected sparseness and the actual redundancy are high.