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

Aravind ReddyarXiv 2026 · arXiv

TL;DR

This paper significantly tightens the theoretical guarantees for the $k$-means++ algorithm, lowering the leading coefficient of the logarithmic approximation ratio from 5 to 2.108. By accounting for the "self-repairing" nature of clusters—where clusters left with high residual costs are more likely to be sampled again and improved—the author provides the most precise bounds to date, including exact values for $k=2$ and $k=3$.

What Problem Does This Paper Address?

$k$-means++ is the industry standard for initializing the $k$-means clustering algorithm. It uses a "seeding" procedure called $D^2$ sampling, which chooses new cluster centers with a probability proportional to their squared distance from the nearest existing center. Since its introduction in 2007, researchers have known that its expected cost is at most $O(\log k)$ times the optimal cost.

However, the exact "worst-case ratio" ($R_k$) has remained elusive. The original analysis provided a leading coefficient of 8 for the $\ln k$ term, which was later improved to 5. Yet, lower bounds suggested the true coefficient might be as low as 2. This paper tackles the challenge of narrowing this gap, moving us closer to a "tight" guarantee that reflects the algorithm's actual performance in the worst case.

Methods

The author introduces a more nuanced accounting framework that moves beyond the traditional "first hit" analysis.

  • The Repair Mechanism: Previous proofs typically bounded the expected cost of a cluster immediately after its first center was sampled and assumed that cost remained static. This paper recognizes that a cluster with a high residual cost is actually more likely to be sampled again in later rounds. Each "repeat hit" acts as a repair, further reducing the cluster's cost.
  • Literal Clocks: The analysis uses "literal clocks" to track the exact number of remaining draws in the seeding process. This allows for a more precise finite induction than previous methods that relied on looser, continuous-time approximations.
  • Computer-Assisted Proof: To achieve the tightest bound (2.108), the author employs a computer-assisted argument. The problem is reduced to a finite set of polynomial inequalities (over 780,000 in one case) which are rigorously verified using exact rational arithmetic and Bernstein positivity certificates.
  • Analytic Proof: For a more traditional approach, a shorter, purely analytic proof is provided that still improves the coefficient to 2.3139.

Datasets

As a theoretical work in computational geometry, this paper does not use standard machine learning datasets. Instead, it utilizes specific geometric constructions to establish lower bounds:

  • The Reservoir: A regular simplex construction used to show $R_k \ge 2(1 + H_{k-1})$.
  • The Hub: A construction involving a central "hub," a "core," and "outliers" that provides stronger lower bounds for small $k$ ($2 \le k \le 18$).

Key Insights and Ideas

  • Large Residuals are Self-Correcting: The core "aha moment" is realizing that leaving a cluster with a large cost isn't a terminal failure of the algorithm. Because $D^2$ sampling is proportional to cost, a "heavy" cluster effectively puts a target on itself for future centers.
  • Local vs. Global: While a "local lemma" shows that a single hit on a cluster results in a cost at most 5 times its optimal cost (a bound that is tight in isolation), the global logarithmic factor can be much smaller than 5 because of the repair mechanism.
  • Exactness at the Bottom: The paper determines the exact worst-case ratios for $k=2$ ($R_2=5$) and $k=3$ ($R_3=185/32 \approx 5.78$). These are suprema that are approached by specific, adversarial point sets but never actually attained.

Key Results

The paper provides a significant tightening of the bounds for $k$-means++, as visualized in the comparison plots:

Comparison of the new upper and lower bounds against previous work (MRS20 and AV07).
  • New Upper Bound: $R_k \le 4.99141 + 2.108 H_{k-2}$ for $k \ge 3$. This lowers the leading coefficient of $\ln k$ from 5 to 2.108 (where $H_j$ is the $j$th harmonic number).
  • New Lower Bound: $R_k \ge 2(1 + H_{k-1})$ for all $k$, matching the leading coefficient of 2 from the original 2007 paper but with a more precise additive term.
  • Small $k$ Gap Closed: For $k=2$ and $k=3$, the paper's upper and lower bounds meet exactly at 5 and 5.78125, respectively.

Limitations and Future Work

The author notes that while the leading coefficient is now narrowed to the interval $[2, 2.108]$, the bounds for $k \ge 4$ are likely still not perfectly optimal. The computer-assisted portion of the proof is massive and relies on an automated audit for verification, which highlights a growing trend in complex mathematical proofs. Future work could aim to close the remaining gap to the coefficient of 2 or find a purely analytic proof for the 2.108 bound.

Summary updated

Abstract

Let $R_k$ be the worst-case ratio between the expected cost of the $k$ seeds chosen by $k$-means++ and the optimal $k$-means cost. In their seminal paper introducing $k$-means++, Arthur and Vassilvitskii (SODA 2007) showed that $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)$. We prove $R_k\le\frac{1163}{233}+2.108\,H_{k-2}$ for every $k\ge3$ by a computer-assisted argument, and $R_k\le5+2.3139\,H_{k-2}$ for every $k\ge2$ by a short analytic argument; here $H_j$ is the $j$th harmonic number. Since $H_{k-2}\le1+\ln k$, this lowers the leading coefficient of $\ln k$ from $5$ to $2.108$. We also determine $R_2=5$ and $R_3=185/32$ exactly; both are suprema that are approached but not attained. On the lower side we prove $R_k\ge2(1+H_{k-1})$ for every $k$, and give a second family of lower bounds that is larger than this for $2\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.
BibTeX
@misc{reddy2026beyond,
  author = {Aravind Reddy},
  title = {{Beyond the First Hit: Towards Tight Guarantees for $k$-means++}},
  year = {2026},
  eprint = {2611.14573},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.14573},
}
Figure