Timezone: »

 
Poster
Nearest-Neighbor Sample Compression: Efficiency, Consistency, Infinite Dimensions
Aryeh Kontorovich · Sivan Sabato · Roi Weiss

Mon Dec 04 06:30 PM -- 10:30 PM (PST) @ Pacific Ballroom #215
in Posters Mon »

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.

Keywords: Learning Theory · Classification
[ Paper] 

Author Information

Aryeh Kontorovich (Ben Gurion University)
Sivan Sabato (Ben Gurion University)
Roi Weiss (Weizmann institute of science)

More from the Same Authors