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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11567/960022
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? 0
social impact