Timezone: »

 
Poster
Statistical and Computational Trade-Offs in Kernel K-Means
Daniele Calandriello · Lorenzo Rosasco

Thu Dec 06 07:45 AM -- 09:45 AM (PST) @ Room 517 AB #129
in Thu Poster Session A »
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.
Keywords: Clustering · Kernel Methods · Learning Theory · Matrix and Tensor Factorization
[ Paper] 

Author Information

Daniele Calandriello (LCSL IIT/MIT)
Lorenzo Rosasco (University of Genova- MIT - IIT)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors