Simple and sharp analysis of k-means||

Thumbnail
Metadata only
Autor(in)
Rozhoň, Václav
Datum
2020
Typ
    Conference Paper
Abstract
We present a simple analysis of k-means|| (Bahmani et al., PVLDB 2012) - a distributed variant of the k-means++ algorithm (Arthur and Vassilvitskii, SODA 2007). Moreover, the bound on the number of rounds is improved from O(logn) to O(logn/loglogn), which we show to be tight.
Publikationsstatus
published
Externe Links
http://proceedings.mlr.press/v119/rozhon20a.html
Herausgeber(in)
Daumé III, Hal
Singh, Aarti
Zeitschrift / Serie
Proceedings of Machine Learning Research
Band
119
Seiten / Artikelnummer
8266 - 8275
Verlag
PMLR
Konferenz
37th International Conference on Machine Learning (ICML 2020) (virtual), Online, July 13-18, 2020
Organisationseinheit
09587 - Ghaffari, Mohsen / Ghaffari, Mohsen  
Anmerkungen
Due to the Coronavirus (COVID-19) the conference was conducted virtually.
Mehr
Alle Metadaten anzeigen
ETH Bibliographie
yes
Altmetrics