We investigate the efficiency of k-means in terms of both statistical and computational requirements. More precisely, we study a Nystrom 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 oot pn Nystrom 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.
Statistical and Computational Trade-Offs in Kernel K-Means
Rosasco, L
2018-01-01
Abstract
We investigate the efficiency of k-means in terms of both statistical and computational requirements. More precisely, we study a Nystrom 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 oot pn Nystrom 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.File in questo prodotto:
File | Dimensione | Formato | |
---|---|---|---|
8147-statistical-and-computational-trade-offs-in-kernel-k-means.pdf
accesso aperto
Tipologia:
Documento in versione editoriale
Dimensione
461.91 kB
Formato
Adobe PDF
|
461.91 kB | Adobe PDF | Visualizza/Apri |
8147-statistical-and-computational-trade-offs-in-kernel-k-means-supplemental.zip
accesso aperto
Tipologia:
Altro materiale allegato
Dimensione
429.65 kB
Formato
Zip File
|
429.65 kB | Zip File | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.