Structures of Spurious Local Minima in k-Means

The$k\text {-means}$clustering problem concerns finding a partition of the data points into$k$clusters such that the total within-cluster squared distance is minimized. This optimization objective is non-convex, and not everywhere differentiable. In general, there exist spurious local solutions other than the global optimum. Moreover, the simplest and most popular algorithm for$k\text {-means}$, namely Lloyd’s algorithm, generally converges to such spurious local solutions both in theory and in practice. In this paper, we investigate thestructuresof these spurious local solutions under a probabilistic generative model with$k$ground truth clusters. As soon as$k=3$, spurious local minima provably exist, even for well-separated clusters. One such local minimum puts two centers at one true cluster, and the third center in the middle of the other two true clusters. We prove that this is essentially theonlytype of spurious local minima under a separation condition. In particular, any local minimum solution only involves a configuration that puts multiple centers at a true cluster, and one center in the middle of multiple true clusters. Our results pertain to the$k\text {-means}$formulation for mixtures of Gaussians or bounded distributions, and hold in the over- and under-parametrization regimes where the number of centers in$k\text {-means}$may not equal to the number of true clusters. Our theoretical results corroborate existing empirical observations and provide justification for popular heuristics for$k\text {-means}$clustering.