# Maximum Margin Multiclass Nearest Neighbors

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Jan 2014.

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

- [Approximation-Generalization Trade-offs under (Approximate) Group Equivariance](https://mlsanity.com/paper/2305.17592/) (2023)
- [Reliable Estimation of KL Divergence using a Discriminator in Reproducing Kernel Hilbert Space](https://mlsanity.com/paper/2109.14688/) (2021)
- [Protecting Split Learning by Potential Energy Loss](https://mlsanity.com/paper/2210.09617/) (2022)

## Abstract (arXiv)

We develop a general framework for margin-based multicategory classification in metric spaces. The basic work-horse is a margin-regularized version of the nearest-neighbor classifier. We prove generalization bounds that match the state of the art in sample size n and significantly improve the dependence on the number of classes k. Our point of departure is a nearly Bayes-optimal finite-sample risk bound independent of k. Although k-free, this bound is unregularized and non-adaptive, which motivates our main result: Rademacher and scale-sensitive margin bounds with a logarithmic dependence on k. As the best previous risk estimates in this setting were of order √ k, our bound is exponentially sharper. From the algorithmic standpoint, in doubling metric spaces our classifier may be trained on n examples in O(n2log n) time and evaluated on new points in O(log n) time.