# Nearest-Neighbor Sample Compression: Efficiency, Consistency, Infinite Dimensions

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 May 2017.

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

- [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)
- [Information Complexity of Stochastic Convex Optimization: Applications to Generalization and Memorization](https://mlsanity.com/paper/2402.09327/) (2024)
- [Survival Kernets: Scalable and Interpretable Deep Kernel Survival Analysis with an Accuracy Guarantee](https://mlsanity.com/paper/2206.10477/) (2022)
- [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)
- [Weighted Distance Nearest Neighbor Condensing](https://mlsanity.com/paper/2310.15951/) (2023)
- [Learning by Compression: Risk Estimates Attain the Law-of-Large-Numbers Rate](https://mlsanity.com/paper/2610.13442/) (2026)

## Abstract (arXiv)

We examine the Bayes-consistency of a recently proposed 1-nearest-neighbor-based multiclass learning algorithm. This algorithm is derived from sample compression bounds and enjoys the statistical advantages of tight, fully empirical generalization bounds, as well as the algorithmic advantages of a faster runtime and memory savings. We prove that this algorithm is strongly Bayes-consistent in metric spaces with finite doubling dimension --- the first consistency result for an efficient nearest-neighbor sample compression scheme. Rather surprisingly, we discover that this algorithm continues to be Bayes-consistent even in a certain infinite-dimensional setting, in which the basic measure-theoretic conditions on which classic consistency proofs hinge are violated. This is all the more surprising, since it is known that k-NN is not Bayes-consistent in this setting. We pose several challenging open problems for future research.