cs.DSNov 9, 2026

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

Authors: Aravind Reddy

Organizations: Centre for Responsible AI, Wadhwani School of Data Science & AI, Indian Institute of Technology Madras

Abstract

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.

Figures & tables

Explore similar work

CardsList
  1. An interpretable Good--Turing restart criterion for k-means++

    Jul 9, 2026Renato Cordeiro de AmorimEarly StoppingClustering

  2. A (3+ε)(3+ε)-Approximation for Fair kk-Means and a Matching Lower Bound

    Sep 7, 2026Kangke Cheng, Guanlin Mo, Shihong Song +1ClusteringGroup Fairness