The Catastrophic Failure of *the* k-Means Algorithm in High Dimensions, and How Hartigan's Algorithm Avoids It

PACM Colloquium
  • Roy Lederman
  • Yale University
  • The Catastrophic Failure of *the* k-Means Algorithm in High Dimensions, and How Hartigan's Algorithm Avoids It
Sep 28, 2026
4:30 - 5:30 pm
214 FINE HALL

Abstract: 

Lloyd's $k$-means algorithm is one of the most widely used and well-known clustering methods. We prove that in high-dimensional, high-noise settings, the algorithm exhibits a surprising 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. We will discuss the general phenomenon and its connection to specific applications such as cryo-EM.