# Asymptotic Theory of Geometric and Adaptive k-Means Clustering

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 52 references that are in the map.
- First posted on arXiv 27 Feb 2022.

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

- [geomstats: a Python Package for Riemannian Geometry in Machine Learning](https://mlsanity.com/paper/1805.08308/) (2018)
- [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)
- [Medoids in almost linear time via multi-armed bandits](https://mlsanity.com/paper/1711.00817/) (2017)
- [Hybrid Wasserstein Distance and Fast Distribution Clustering](https://mlsanity.com/paper/1812.11026/) (2018)
- [Ultra Fast Medoid Identification via Correlated Sequential Halving](https://mlsanity.com/paper/1906.04356/) (2019)
- [Wasserstein K-Means for Clustering Tomographic Projections](https://mlsanity.com/paper/2010.09989/) (2020)
- [Convergence of the k-Means Minimization Problem using Gamma-Convergence](https://mlsanity.com/paper/1501.01320/) (2015)
- [On clustering uncertain and structured data with Wasserstein barycenters and a geodesic criterion for the number of clusters](https://mlsanity.com/paper/1912.11801/) (2019)
- [On the Consistency of Metric and Non-Metric K-medoids](https://mlsanity.com/paper/2010.09906/) (2020)

## Built on by (most cited first, 4 of 4)

- [Universal Regression with Adversarial Responses](https://mlsanity.com/paper/2203.05067/) (2022)
- [Consistency and inconsistency in k-means clustering](https://mlsanity.com/paper/2507.06226/) (2025)
- [K-means with learned metrics](https://mlsanity.com/paper/2603.14601/) (2026)
- [The Condition-Number Principle for Prototype Clustering](https://mlsanity.com/paper/2604.07744/) (2026)

## Abstract (arXiv)

We revisit Pollard's classical result on consistency for k-means clustering in Euclidean space, with a focus on extensions in two directions: first, to problems where the data may come from interesting geometric settings (e.g., Riemannian manifolds, reflexive Banach spaces, or the Wasserstein space); second, to problems where some parameters are chosen adaptively from the data (e.g., k-medoids or elbow-method k-means). Towards this end, we provide a general theory which shows that all clustering procedures described above are strongly consistent. In fact, our method of proof allows us to derive many asymptotic limit theorems beyond strong consistency. We also remove all assumptions about uniqueness of the set of optimal cluster centers.