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öm 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öm 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.

Cited by in corpus (7)

• An Efficient One-Class SVM for Anomaly Detection in the Internet of Things
• Kernel methods through the roof: handling billions of points efficiently
• Kernel k-Means, By All Means: Algorithms and Strong Consistency
• Gaussian Process Optimization with Adaptive Sketching: Scalable and No Regret
• Nearly Optimal Clustering Risk Bounds for Kernel K-Means
• Gaussian Sketching yields a J-L Lemma in RKHS
• Regularized ERM on random subspaces