Beyond the First Hit: Towards Tight Guarantees for -means++
Organizations: Centre for Responsible AI, Wadhwani School of Data Science & AI, Indian Institute of Technology Madras
Abstract
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.
Figures & tables
| Value or bound | Where | |
|---|---|---|
| (classical, [ AV07 , Lemma 3.1] ) | Proposition 7.2 | |
| (supremum, not attained) | Theorem 7.3 | |
| (supremum, not attained) | Theorem 7.5 | |
| upper, | (computer-assisted) | Theorem 1.1 , Section 6 |
| upper, | (analytic) | Theorem 1.2 , Section 4 |
| lower, | Theorem 8.1 |
| Component | Statement | Size |
|---|---|---|
| Drift foundation | Proposition 5.4 | 12 gates, 15 intervals, 90 controls |
| Drift bootstrap ( stages) | Proposition 5.5 | 72 rectangles, 2,606 controls |
| High row | Proposition 6.6 | 7 shape cells, 169 bands, 4,841 domains, 48,410 controls |
| Low row: source allocation | Proposition 6.2 | 2,390 roots, 2,467 pieces, 783,516 source boxes |
| Low row: inherited physical reserves | Lemma 6.3 | 1,479 rectangles, 688,708 leaves, 17,395,180 controls |
| Low row: fresh physical reserves | Lemma 6.3 | 158 rectangles, 1,980,435 controls |
Clustering
Clustering groups data points by shared structure, developing methods to discover, validate, and interpret groups across diverse data and constraints.
See all 370 papers