Statistical and Computational Trade-Offs in Kernel K-Means
Abstract
We investigate the efficiency of k-means in terms of both statistical and computational requirements. More precisely, we study a Nystr\"om approach to kernel k-means. We analyze the statistical properties of the proposed method and show that it achieves the same accuracy of exact kernel k-means with only a fraction of computations. Indeed, we prove under basic assumptions that sampling $\sqrt{n}$ Nystr\"om landmarks allows to greatly reduce computational costs without incurring in any loss of accuracy. To the best of our knowledge this is the first result showing in this kind for unsupervised learning.
Cite
Text
Calandriello and Rosasco. "Statistical and Computational Trade-Offs in Kernel K-Means." Neural Information Processing Systems, 2018.Markdown
[Calandriello and Rosasco. "Statistical and Computational Trade-Offs in Kernel K-Means." Neural Information Processing Systems, 2018.](https://mlanthology.org/neurips/2018/calandriello2018neurips-statistical/)BibTeX
@inproceedings{calandriello2018neurips-statistical,
title = {{Statistical and Computational Trade-Offs in Kernel K-Means}},
author = {Calandriello, Daniele and Rosasco, Lorenzo},
booktitle = {Neural Information Processing Systems},
year = {2018},
pages = {9357-9367},
url = {https://mlanthology.org/neurips/2018/calandriello2018neurips-statistical/}
}