跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.14573 · v1

Beyond the First Hit: Towards Tight Guarantees for $k$-means++

首次提交 2026-11-10 05:58
版本更新 2026-11-10 05:58
雷达观测 2026-11-13 10:10
arXiv ↗PDF ↗

摘要

Let RkR_k be the worst-case ratio between the expected cost of the kk seeds chosen by kk-means++ and the optimal kk-means cost. In their seminal paper introducing kk-means++, Arthur and Vassilvitskii (SODA 2007) showed that 2ln⁡k≤Rk≤8(ln⁡k+2)2\ln k\le R_k\le8(\ln k+2), and Makarychev, Reddy and Shan (NeurIPS 2020) improved the upper bound to 5(ln⁡k+2)5(\ln k+2). We prove Rk≤1163233+2.108 Hk−2R_k\le\frac{1163}{233}+2.108\,H_{k-2} for every k≥3k\ge3 by a computer-assisted argument, and Rk≤5+2.3139 Hk−2R_k\le5+2.3139\,H_{k-2} for every k≥2k\ge2 by a short analytic argument; here HjH_j is the jjth harmonic number. Since Hk−2≤1+ln⁡kH_{k-2}\le1+\ln k, this lowers the leading coefficient of ln⁡k\ln k from 55 to 2.1082.108. We also determine R2=5R_2=5 and R3=185/32R_3=185/32 exactly; both are suprema that are approached but not attained. On the lower side we prove Rk≥2(1+Hk−1)R_k\ge2(1+H_{k-1}) for every kk, and give a second family of lower bounds that is larger than this for 2≤k≤182\le k\le18. Previous analyses bound the expected cost of a cluster just after it is first sampled by a constant times its optimal cost, and then charge that cost for the rest of the run. We instead track how a cluster's cost evolves after its first hit: a cluster left with a large residual cost is likely to be sampled again before it accumulates much of the logarithmic charge, and each repeat repairs it.

作者备注:48 pages, 1 figure (3 panels). Exact-arithmetic certificate data and verification code included as ancillary files

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-10 05:58 · 最新观测版本

Beyond the First Hit: Towards Tight Guarantees for $k$-means++

Let RkR_k be the worst-case ratio between the expected cost of the kk seeds chosen by kk-means++ and the optimal kk-means cost. In their seminal paper introducing kk-means++, Arthur and Vassilvitskii (SODA 2007) showed that 2ln⁡k≤Rk≤8(ln⁡k+2)2\ln k\le R_k\le8(\ln k+2), and Makarychev, Reddy and Shan (NeurIPS 2020) improved the upper bound to 5(ln⁡k+2)5(\ln k+2). We prove Rk≤1163233+2.108 Hk−2R_k\le\frac{1163}{233}+2.108\,H_{k-2} for every k≥3k\ge3 by a computer-assisted argument, and Rk≤5+2.3139 Hk−2R_k\le5+2.3139\,H_{k-2} for every k≥2k\ge2 by a short analytic argument; here HjH_j is the jjth harmonic number. Since Hk−2≤1+ln⁡kH_{k-2}\le1+\ln k, this lowers the leading coefficient of ln⁡k\ln k from 55 to 2.1082.108. We also determine R2=5R_2=5 and R3=185/32R_3=185/32 exactly; both are suprema that are approached but not attained. On the lower side we prove Rk≥2(1+Hk−1)R_k\ge2(1+H_{k-1}) for every kk, and give a second family of lower bounds that is larger than this for 2≤k≤182\le k\le18. Previous analyses bound the expected cost of a cluster just after it is first sampled by a constant times its optimal cost, and then charge that cost for the rest of the run. We instead track how a cluster's cost evolves after its first hit: a cluster left with a large residual cost is likely to be sampled again before it accumulates much of the logarithmic charge, and each repeat repairs it.

查看此版本解读 →查看此版本原文 ↗