The Catastrophic Failure of *the* k-Means Algorithm in High Dimensions, and How Hartigan's Algorithm Avoids It
Roy Lederman, David Silva-Sánchez, Ziling Chen, Gilles Mordant, Amnon Balanov, Tamir Bendory
Abstract
Lloyd's k-means algorithm is one of the most widely used clustering methods. We prove that in high-dimensional, high-noise settings, the algorithm exhibits catastrophic failure: with high probability, essentially every partition of the data is a fixed point. Consequently, Lloyd's algorithm simply returns its initial partition — even when the underlying clusters are trivially recoverable by other methods. In contrast, we prove that Hartigan's k-means algorithm does not exhibit this pathology. Our results show the stark difference between these algorithms and offer a theoretical explanation for the empirical difficulties often observed with k-means in high dimensions.
BibTeX
@inproceedings{
lederman2026the,
title={The Catastrophic Failure of *the* k-Means Algorithm in High Dimensions, and How Hartigan's Algorithm Avoids It},
author={Roy R Lederman and David Silva-S{\'a}nchez and Ziling Chen and Gilles Mordant and Amnon Balanov and Tamir Bendory},
booktitle={Forty-third International Conference on Machine Learning},
year={2026},
url={https://openreview.net/forum?id=4CwO8At8Hw}
}