Near-Optimal Sample Compression for Nearest Neighbors
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.
Cite
Text
Gottlieb et al. "Near-Optimal Sample Compression for Nearest Neighbors." Neural Information Processing Systems, 2014.Markdown
[Gottlieb et al. "Near-Optimal Sample Compression for Nearest Neighbors." Neural Information Processing Systems, 2014.](https://mlanthology.org/neurips/2014/gottlieb2014neurips-nearoptimal/)BibTeX
@inproceedings{gottlieb2014neurips-nearoptimal,
title = {{Near-Optimal Sample Compression for Nearest Neighbors}},
author = {Gottlieb, Lee-Ad and Kontorovich, Aryeh and Nisnevitch, Pinhas},
booktitle = {Neural Information Processing Systems},
year = {2014},
pages = {370-378},
url = {https://mlanthology.org/neurips/2014/gottlieb2014neurips-nearoptimal/}
}