← Back to papers
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 — Data Science & Analytics and Mathematics & Optimization
🧭 Keyword Pioneer — k-means algorithm
🐝 Cross-Pollinator — Artificial Intelligence, Computer Vision, Data Science & Analytics, Deep Learning, Healthcare & Medicine, Interdisciplinary, Machine Learning, Mathematics & Optimization, Natural Language Processing, Security & Privacy

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

Related papers

Correlation Clustering with Asymmetric Classification Errors 2020
Learning Portable Representations for High-Level Planning 2020
Proving the Lottery Ticket Hypothesis: Pruning is All You Need 2020
Minimax Pareto Fairness: A Multi Objective Perspective 2020
DeepMatch: Balancing Deep Covariate Representations for Causal Inference Using Adversarial Training 2020