Simple and sharp analysis of k-means||

Part of Proceedings of the International Conference on Machine Learning 1 pre-proceedings (ICML 2020)

Bibtex »Metadata »Paper »

Bibtek download is not availble in the pre-proceeding


Vaclav Rozhon


<p>We present a truly simple analysis of k-means|| (Bahmani et al., PVLDB 2012) -- a distributed variant of the k-means++ algorithm (Arthur and Vassilvitskii, SODA 2007) -- and improve its round complexity from O(log (Var X)), where Var X is the variance of the input data set, to O(log (Var X) / log log (Var X)), which we show to be tight. </p>