Mini-batch $k$-means terminates within $O(d/\epsilon)$ iterations
Authors: Gregory Schwartzman
ICLR 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our results are the first to show extremely fast termination guarantees for mini-batch k-means with early stopping conditions. Surprisingly, we need not require the learning rate to go to 0. We analyze the mini-batch k-means algorithm described above (Sculley, 2010), where the algorithm terminates only when the improvement in the quality of the clustering for the sampled batch is less than some threshold parameter ϵ. |
| Researcher Affiliation | Academia | Gregory Schwartzman Japan Advanced Institute of Science and Technology (JAIST) greg@jaist.ac.jp |
| Pseudocode | Yes | Algorithm 1: Generic mini-batch k-means |
| Open Source Code | No | The paper mentions checking the scikit-learn (sklearn) python library's implementation and links to its GitHub, but does not provide concrete access to source code specifically for the methodology described in this paper by the authors. |
| Open Datasets | No | The paper is theoretical and focuses on algorithm analysis and termination guarantees, rather than empirical evaluation using specific training datasets. |
| Dataset Splits | No | The paper is theoretical and focuses on algorithm analysis and termination guarantees, rather than empirical evaluation using specific validation datasets. |
| Hardware Specification | No | The paper is purely theoretical and does not describe any experiments that would require specific hardware specifications. |
| Software Dependencies | No | The paper is theoretical and focuses on mathematical analysis; it does not mention specific software dependencies with version numbers needed to replicate any experimental results. |
| Experiment Setup | No | The paper focuses on theoretical analysis and proofs, and therefore does not include details on experimental setup such as hyperparameters or training configurations. |