# Near-optimal sample compression for nearest neighbors

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Apr 2014.

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

- [A Theory of PAC Learnability of Partial Concept Classes](https://mlsanity.com/paper/2107.08444/) (2021)
- [Optimal Learners for Realizable Regression: PAC Learning and Online Learning](https://mlsanity.com/paper/2307.03848/) (2023)
- [Optimal Binary Classification Beyond Accuracy](https://mlsanity.com/paper/2107.01777/) (2021)
- [Federated Nearest Neighbor Classification with a Colony of Fruit-Flies: With Supplement](https://mlsanity.com/paper/2112.07157/) (2021)
- [Sample Compression Scheme Reductions](https://mlsanity.com/paper/2410.13012/) (2024)
- [On Error and Compression Rates for Prototype Rules](https://mlsanity.com/paper/2206.08014/) (2022)
- [Enhanced Nearest Neighbor Classification for Crowdsourcing](https://mlsanity.com/paper/2203.00781/) (2022)
- [Weighted Distance Nearest Neighbor Condensing](https://mlsanity.com/paper/2310.15951/) (2023)
- [Boolean Nearest Neighbor Language in the Knowledge Compilation Map](https://mlsanity.com/paper/2410.06332/) (2024)

## Abstract (arXiv)

We present the first sample compression algorithm for nearest neighbors with non-trivial performance guarantees. We complement these guarantees by demonstrating almost matching hardness lower bounds, which show that our bound is nearly optimal. Our result yields new insight into margin-based nearest neighbor classification in metric spaces and allows us to significantly sharpen and simplify existing bounds. Some encouraging empirical results are also presented.