Skip to content
conftrace_
2020 ICML ICML 2020

Simple and sharp analysis of k-means||

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(\log n)$ to $O(\log n / \log\log n)$, which we show to be tight.

🌉 Interdisciplinary Bridge - Artificial Intelligence and Computer Science and Data Science & Analytics and Mathematics & Optimization

Authors

Vaclav Rozhon

Topics

Machine Learning > Core Methods > Clustering Machine Learning > Optimization & Theory > Optimization Data Science & Analytics > Applications > Clustering Mathematics & Optimization > Optimization > Combinatorial Optimization Computer Science > Foundations > Algorithms

Keywords

k-means clustering distributed clustering algorithm analysis clustering algorithm distributed algorithm approximation bound k-means algorithm
Download PDF

More from ICML 2020

All ICML 2020 papers →
Certified Robustness to Label-Flipping Attacks via Randomized Smoothing
Revisiting Training Strategies and Generalization Performance in Deep Metric Learning
FetchSGD: Communication-Efficient Federated Learning with Sketching
Bayesian Optimisation over Multiple Continuous and Categorical Inputs
Inter-domain Deep Gaussian Processes
Bio-Inspired Hashing for Unsupervised Similarity Search