Consistency and inconsistency in k-means clustering

Constraint-restored consistency of empirical clustering (30 Aug 2026)

Use

the closest published structure to DS15's Proposition 6 — constraints imposed at asymptotically negligible cost — and the reference to engage before any publication of the steering construction.

Does not transfer

their constraint repairs a moment pathology of the scalar-distortion objective; DS15's margin fights the profiled criterion's own drive to nuisance degeneracy, and no published theorem provides swap-steering to a side constraint at $\tilde O(N^{-3/4})$ cost.

Sources

Blanchard, Jaffe & Zhivotovskiy (arXiv:2507.06226, abstract): under only a finite first moment, empirical k-means centers can fail to converge even when the population optimum is unique — the failure mode is extreme cluster imbalance — and an a priori balance (minimum-size) constraint restores consistency. Kanungo et al. (2004, Comput. Geom. 28:89–112): single-swap local search with bounded worst-case cost. Bradley, Bennett & Demiriz (2000, MSR TR-2000-65): minimum-cluster-size constrained assignment via network flow.