← 研踪 PaperTrailarXiv: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
摘要
Let be the worst-case ratio between the expected cost of the seeds chosen by -means++ and the optimal -means cost. In their seminal paper introducing -means++, Arthur and Vassilvitskii (SODA 2007) showed that , and Makarychev, Reddy and Shan (NeurIPS 2020) improved the upper bound to . We prove for every by a computer-assisted argument, and for every by a short analytic argument; here is the th harmonic number. Since , this lowers the leading coefficient of from to . We also determine and exactly; both are suprema that are approached but not attained. On the lower side we prove for every , and give a second family of lower bounds that is larger than this for . 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
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-10 05:58 · 最新观测版本
Beyond the First Hit: Towards Tight Guarantees for $k$-means++
Let be the worst-case ratio between the expected cost of the seeds chosen by -means++ and the optimal -means cost. In their seminal paper introducing -means++, Arthur and Vassilvitskii (SODA 2007) showed that , and Makarychev, Reddy and Shan (NeurIPS 2020) improved the upper bound to . We prove for every by a computer-assisted argument, and for every by a short analytic argument; here is the th harmonic number. Since , this lowers the leading coefficient of from to . We also determine and exactly; both are suprema that are approached but not attained. On the lower side we prove for every , and give a second family of lower bounds that is larger than this for . 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.
查看此版本解读 →查看此版本原文 ↗