Near-optimal sample compression for nearest neighbors
Lee-Ad Gottlieb ⋅ Aryeh Kontorovich ⋅ Pinhas Nisnevitch
2014 Poster
Abstract
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.
Chat is not available.
Successful Page Load