Nearest-neighbor Sample Compression: Efficiency, Consistency, Infinite Dimensions

Abstract

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.

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keykontorovich2017nearest

Related papers

• Fast And Bayes-consistent Nearest Neighbors (2019)0.00
• On High-dimensional Modifications Of The Nearest Neighbor Classifier (2024)0.00
• Adaptive Nearest Neighbor: A General Framework For Distance Metric Learning (2019)0.00
• An Adaptive Nearest Neighbor Rule For Classification (2019)0.00
• Nearest Neighbor And Kernel Survival Analysis: Nonasymptotic Error Bounds And Strong Consistency Rates (2019)0.00
• High-dimensional Approximate Nearest Neighbor Search: With Reliable And Efficient Distance Comparison Operations (2023)13.44
• Universal Consistency Of The \(k\)-nn Rule In Metric Spaces And Nagata Dimension (2020)2.26
• Fast And Multiphase Rates For Nearest Neighbor Classifiers (2023)0.00