Simple and sharp analysis of k-means||
Authors: Václav Rozhoň
ICML 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this work we first provide a new, simple analysis of k-means|| , thus simplifying known proofs (Bahmani et al., 2012) and (Bachem et al., 2017). In particular, if we denote by µX the mean of X and ϕ the optimal solution, we prove in Section 3 that O(log ϕX(µX) /ϕ ) rounds of the k-means|| algorithm suffice to get expected constant approximation guarantee. |
| Researcher Affiliation | Academia | V aclav Rozhoˇn 1 1ETH, Zurich. Correspondence to: V aclav Rozhoˇn <rozhonv@ethz.ch>. |
| Pseudocode | Yes | Algorithm 1 k-means|| overseeding (...) Algorithm 2 k-means|| (Bahmani et al., 2012) |
| Open Source Code | No | The paper is theoretical and focuses on analysis; it does not mention releasing any source code for its method. |
| Open Datasets | No | This is a theoretical paper and does not involve training models on datasets. Therefore, no information on public dataset access is provided. |
| Dataset Splits | No | This is a theoretical paper and does not involve dataset splits (training, validation, test). Therefore, no information on validation splits is provided. |
| Hardware Specification | No | This is a theoretical paper focusing on algorithm analysis; it does not describe experimental setups or mention any hardware specifications. |
| Software Dependencies | No | This is a theoretical paper focusing on algorithm analysis; it does not describe experimental setups or list specific software dependencies with version numbers. |
| Experiment Setup | No | This is a theoretical paper presenting algorithm analysis and proofs, not experimental results. Therefore, no experimental setup details like hyperparameters or training settings are provided. |