# Moment-based Uniform Deviation Bounds for k-means and Friends

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Nov 2013.

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

- [Stochastic linear optimization never overfits with quadratically-bounded losses on general data](https://mlsanity.com/paper/2202.06915/) (2022)
- [Uniform Concentration Bounds toward a Unified Framework for Robust Clustering](https://mlsanity.com/paper/2110.14148/) (2021)
- [Uniform Mean Estimation for Heavy-Tailed Distributions via Median-of-Means](https://mlsanity.com/paper/2506.14673/) (2025)
- [Bregman Power k-Means for Clustering Exponential Family Data](https://mlsanity.com/paper/2206.10860/) (2022)
- [Consistency of Lloyd's Algorithm Under Perturbations](https://mlsanity.com/paper/2309.00578/) (2023)
- [Coresets for Relational Data and The Applications](https://mlsanity.com/paper/2210.04249/) (2022)
- [On uniqueness of the set of k-means](https://mlsanity.com/paper/2410.13495/) (2024)
- [Distribution free optimality intervals for clustering](https://mlsanity.com/paper/2107.14442/) (2021)
- [Information-theoretic Generalization Analysis for VQ-VAEs: A Role of Latent Variables](https://mlsanity.com/paper/2505.19470/) (2025)
- [Task-Driven Discrete Representation Learning](https://mlsanity.com/paper/2506.11511/) (2025)
- [The Condition-Number Principle for Prototype Clustering](https://mlsanity.com/paper/2604.07744/) (2026)

## Abstract (arXiv)

Suppose k centers are fit to m points by heuristically minimizing the k-means cost; what is the corresponding fit over the source distribution? This question is resolved here for distributions with p≥ 4 bounded moments; in particular, the difference between the sample cost and distribution cost decays with m and p as m^min-1/4, -1/2+2/p. The essential technical contribution is a mechanism to uniformly control deviations in the face of unbounded parameter sets, cost functions, and source distributions. To further demonstrate this mechanism, a soft clustering variant of k-means cost is also considered, namely the log likelihood of a Gaussian mixture, subject to the constraint that all covariance matrices have bounded spectrum. Lastly, a rate with refined constants is provided for k-means instances possessing some cluster structure.