# Robust k-means Clustering for Distributions with Two Moments

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

## Key facts

- Cited by 14 papers in the map (data through 7 Oct 2026).
- First posted on arXiv 6 Feb 2020.

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

- [Distribution-Free Robust Linear Regression](https://mlsanity.com/paper/2102.12919/) (2021)
- [Uniform Concentration Bounds toward a Unified Framework for Robust Clustering](https://mlsanity.com/paper/2110.14148/) (2021)
- [Fat-Shattering Dimension of k-fold Aggregations](https://mlsanity.com/paper/2110.04763/) (2021)
- [Robust Principal Component Analysis: A Median of Means Approach](https://mlsanity.com/paper/2102.03403/) (2021)
- [Asymptotic Theory of Geometric and Adaptive k-Means Clustering](https://mlsanity.com/paper/2202.13423/) (2022)
- [Adversarially robust clustering with optimality guarantees](https://mlsanity.com/paper/2306.09977/) (2023)
- [Consistency of Lloyd's Algorithm Under Perturbations](https://mlsanity.com/paper/2309.00578/) (2023)
- [Adaptively Robust and Sparse K-means Clustering](https://mlsanity.com/paper/2407.06945/) (2024)
- [Robust Linear Predictions: Analyses of Uniform Concentration, Fast Rates and Model Misspecification](https://mlsanity.com/paper/2201.01973/) (2022)
- [Robustifying Markowitz](https://mlsanity.com/paper/2212.13996/) (2022)
- [Dirichlet Process-based Robust Clustering using the Median-of-Means Estimator](https://mlsanity.com/paper/2311.15384/) (2023)
- [Consistency and inconsistency in k-means clustering](https://mlsanity.com/paper/2507.06226/) (2025)
- [The Condition-Number Principle for Prototype Clustering](https://mlsanity.com/paper/2604.07744/) (2026)
- [Distributionally Robust K-Means Clustering](https://mlsanity.com/paper/2604.11118/) (2026)

## Abstract (arXiv)

We consider the robust algorithms for the k-means clustering problem where a quantizer is constructed based on N independent observations. Our main results are median of means based non-asymptotic excess distortion bounds that hold under the two bounded moments assumption in a general separable Hilbert space. In particular, our results extend the renowned asymptotic result of Pollard, 1981 who showed that the existence of two moments is sufficient for strong consistency of an empirically optimal quantizer in ℝd. In a special case of clustering in ℝd, under two bounded moments, we prove matching (up to constant factors) non-asymptotic upper and lower bounds on the excess distortion, which depend on the probability mass of the lightest cluster of an optimal quantizer. Our bounds have the sub-Gaussian form, and the proofs are based on the versions of uniform bounds for robust mean estimators.