Strong Consistency of K-Means Clustering

Pollard (1981, 1982) and the k-means consistency cluster

Does not transfer

every member assumes a fixed source-independent metric and per-point additive distortion; none covers a solution-dependent semimetric (the fitted $G_s$) or a determinant/Schur functional of aggregated cell moments; center-convergence uniqueness conditions have no log-det analogue.

Papers

Strong Consistency of K-Means Clustering (Ann. Statist. 9:135–140); A Central Limit Theorem for k-Means Clustering (Ann. Probab. 10:919–926); Quantization and the Method of k-Means (IEEE IT 28:199–205). Refinements: Abaya & Wise (1984, SIAM J. Appl. Math. 44:183–189, optimal quantizers under weakly converging sources); Sverdrup-Thygeson (1981, Ann. Statist. 9:141–145); Cuesta-Albertos & Matrán (1988, PTRF 78:523–534); Lember (2003, J. Approx. Theory 120:20–35, minimizing sequences / non-unique optima); Linder (2000, CISM 464 survey, VC/covering-number finite-sample bounds).

Use (triangulated 28 Aug 2026 for the DS14 bridge)

the two-step "uniform LLN over configuration classes + argmin continuity" skeleton is the direct template for DS14 Steps 3–5; Lember/Abaya–Wise handle non-unique optima (needed for the Ds tie degeneracy DS11(c)).