# Statistical and Computational Trade-Offs in Kernel K-Means

arXiv: https://arxiv.org/abs/1908.10284 · HTML: https://mlsanity.com/paper/1908.10284/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Aug 2019.

## Built on by (most cited first, 7 of 7)

- [Learning new physics efficiently with nonparametric methods](https://mlsanity.com/paper/2204.02317/) (2022)
- [Statistical and Computational Trade-offs in Variational Inference: A Case Study in Inferential Model Selection](https://mlsanity.com/paper/2207.11208/) (2022)
- [Collaborative Learning in Kernel-based Bandits for Distributed Users](https://mlsanity.com/paper/2207.07948/) (2022)
- [On Generalization Bounds for Projective Clustering](https://mlsanity.com/paper/2310.09127/) (2023)
- [An Efficient One-Class SVM for Anomaly Detection in the Internet of Things](https://mlsanity.com/paper/2104.11146/) (2021)
- [Nearly-Optimal Algorithm for Adversarial Kernelized Bandits](https://mlsanity.com/paper/2605.10299/) (2026)
- [Snacks: a fast large-scale kernel SVM solver](https://mlsanity.com/paper/2304.07983/) (2023)

## Abstract (arXiv)

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 √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 of this kind for unsupervised learning.