A Nearly Tight Analysis of Greedy k-means++
From Google TechTalks · 58:57
Show by Google TechTalks
A Google TechTalk, presented by Václav Rozhoň, 2023-04-13Abstract: The famous k-means++ algorithm of Arthur and Vassilvitskii is the most popular practical algorithm for solving the k-means problem. The algorithm is very simple and computes the k output centers as follows: it samples the first center as a uniformly random point in the dataset and each of the following k−1 centers is then always sampled with probability proportional to the squared distance to the currently closest center. Amazingly, the k-means++ algorithm is known to return a Θ(log k) approximate solution in expectation.In their seminal work, Arthur and Vassilvitskii asked about the guarantees of its following greedy variant: in every step, we sample ℓ candidate centers instead of one and then pick the one that minimizes the new cost. This is also how k-means++ is implemented in e.g. the popular Scikit-learn library. We analyze greedy k-means++: We prove that it is an O(ℓ^3 * log^3 k)-approximation algorithm and provide a near-matching lower bound.Uploaded 15-04-23Joint work with Christoph Grunau, Ahmet Alper Özüdoğru, Jakub Tětek arxiv: https://arxiv.org/abs/2207.07949Bio: Vaclav Rozhon is a PhD student at ETH Zurich advised by Mohsen Ghaffari. He works mostly on distributed and parallel algorithms; he also creates YouTube videos about algorithms (channel name: polylog). He has a young child and thus no hobbies.A Google Talk Series on Algorithms, Theory, and Optimization
More episodes of Google TechTalks
More episodes
- Java Posse Episode 100 (Live Special)
- Cascading Adversarial Bias from Injection to Distillation in Language Models
- Practical Common Lisp
- Cascading Adversarial Bias from Injection to Distillation in Language Models
- Security is Broken
- POPri: Private Federated Learning using Preference-Optimized Synthetic Data
- Everything is Miscellaneous
- Leveraging Per-Instance Privacy for Machine Unlearning
- Impact of Technology on Reducing Poverty and Alleviating...
- Disparate Privacy Risks from Medical AI - An Investigation into Patient-level Privacy Risk
PodSearch is a free, independent podcast search engine. Read about PodSearch, the privacy policy or contact us.