# Consistency and inconsistency in k-means clustering

arXiv: https://arxiv.org/abs/2507.06226 · HTML: https://mlsanity.com/paper/2507.06226/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 40 references that are in the map.
- First posted on arXiv 8 Jul 2025.

## Builds on (most cited first, 11 of 11)

- [Fast Computation of Wasserstein Barycenters](https://mlsanity.com/paper/1310.4375/) (2013)
- [Wasserstein Regression](https://mlsanity.com/paper/2006.09660/) (2020)
- [Differentiable Deep Clustering with Cluster Size Constraints](https://mlsanity.com/paper/1910.09036/) (2019)
- [Robust k-means Clustering for Distributions with Two Moments](https://mlsanity.com/paper/2002.02339/) (2020)
- [Robust clustering tools based on optimal transportation](https://mlsanity.com/paper/1607.01179/) (2016)
- [Robust Bregman Clustering](https://mlsanity.com/paper/1812.04356/) (2018)
- [Convergence of the k-Means Minimization Problem using Gamma-Convergence](https://mlsanity.com/paper/1501.01320/) (2015)
- [Robust Trimmed k-means](https://mlsanity.com/paper/2108.07186/) (2021)
- [Asymptotic Theory of Geometric and Adaptive k-Means Clustering](https://mlsanity.com/paper/2202.13423/) (2022)
- [On the Consistency of Metric and Non-Metric K-medoids](https://mlsanity.com/paper/2010.09906/) (2020)
- [An Observation on Lloyd's k-Means Algorithm in High Dimensions](https://mlsanity.com/paper/2506.14952/) (2025)

## Abstract (arXiv)

A celebrated result of Pollard proves asymptotic consistency for k-means clustering when the population distribution has finite variance. In this work, we point out that the population-level k-means clustering problem is, in fact, well-posed under the weaker assumption of a finite expectation, and we investigate whether some form of asymptotic consistency holds in this setting. As we illustrate in a variety of negative results, the complete story is quite subtle; for example, the empirical k-means cluster centers may fail to converge even if there exists a unique set of population k-means cluster centers. A detailed analysis of our negative results reveals that inconsistency arises because of an extreme form of cluster imbalance, whereby the presence of outlying samples leads to some empirical k-means clusters possessing very few points. We then give a collection of positive results which show that some forms of asymptotic consistency, under only the assumption of finite expectation, may be recovered by imposing some a priori degree of balance among the empirical k-means clusters.