{"id":"arxiv/2602.09936","url":"https://arxiv.org/abs/2602.09936","tags":["stat.ML","cs.LG","math.ST"],"score":0,"title":"The Catastrophic Failure of The k-Means Algorithm in High Dimensions, and How Hartigan's Algorithm Avoids It","domain":"stat.ML","source":"arxiv","authors":["Roy R. Lederman","David Silva-Sánchez","Ziling Chen","Gilles Mordant","Amnon Balanov","Tamir Bendory"],"reviews":0,"subject":"stat.ML","summary":"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…","category":"research","comments":0,"disputed":false,"division":"stat","mentions":0,"discussed":0,"published":"2026-02-10","reactions":{}}