AISTATS 2018poster0 citations
Achieving the time of 1-NN, but the accuracy of k-NN
Abstract
We propose a simple approach which, given distributed computing resources, can nearly achieve the accuracy of k-NN prediction, while matching (or improving) the faster prediction time of 1-NN. The approach consists of aggregating denoised 1-NN predictors over a small number of distributed subsamples. We show, both theoretically and experimentally, that small subsample sizes suffice to attain similar performance as k-NN, without sacrificing the computational efficiency of 1-NN.
BibTeX
@InProceedings{pmlr-v84-xue18a,
title = {Achieving the time of 1-NN, but the accuracy of k-NN},
author = {Xue, Lirong and Kpotufe, Samory},
booktitle = {Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics},
pages = {1628--1636},
year = {2018},
editor = {Storkey, Amos and Perez-Cruz, Fernando},
volume = {84},
series = {Proceedings of Machine Learning Research},
month = {09--11 Apr},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v84/xue18a/xue18a.pdf},
url = {https://proceedings.mlr.press/v84/xue18a.html},
abstract = {We propose a simple approach which, given distributed computing resources, can nearly achieve the accuracy of k-NN prediction, while matching (or improving) the faster prediction time of 1-NN. The approach consists of aggregating denoised 1-NN predictors over a small number of distributed subsamples. We show, both theoretically and experimentally, that small subsample sizes suffice to attain similar performance as k-NN, without sacrificing the computational efficiency of 1-NN. }
}