# Uniform Concentration Bounds toward a Unified Framework for Robust Clustering

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 65 references that are in the map.
- First posted on arXiv 27 Oct 2021.

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

- [Empirical risk minimization for heavy-tailed losses](https://mlsanity.com/paper/1406.2462/) (2014)
- [When OT meets MoM: Robust estimation of Wasserstein Distance](https://mlsanity.com/paper/2006.10325/) (2020)
- [Statistical Properties of Convex Clustering](https://mlsanity.com/paper/1503.08340/) (2015)
- [Lecture Notes: Selected topics on robust statistical learning theory](https://mlsanity.com/paper/1908.10761/) (2019)
- [Robust k-means Clustering for Distributions with Two Moments](https://mlsanity.com/paper/2002.02339/) (2020)
- [Moment-based Uniform Deviation Bounds for k-means and Friends](https://mlsanity.com/paper/1311.1903/) (2013)
- [Regularization, sparse recovery, and median-of-means tournaments](https://mlsanity.com/paper/1701.04112/) (2017)
- [Excess risk bounds in robust empirical risk minimization](https://mlsanity.com/paper/1910.07485/) (2019)
- [Robust Bregman Clustering](https://mlsanity.com/paper/1812.04356/) (2018)
- [K-bMOM: a robust Lloyd-type clustering algorithm based on bootstrap Median-of-Means](https://mlsanity.com/paper/2002.03899/) (2020)
- [Biconvex Clustering](https://mlsanity.com/paper/2008.01760/) (2020)
- [Robust Principal Component Analysis: A Median of Means Approach](https://mlsanity.com/paper/2102.03403/) (2021)

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

- [Clustering above Exponential Families with Tempered Exponential Measures](https://mlsanity.com/paper/2211.02765/) (2022)
- [Gradient Based Clustering](https://mlsanity.com/paper/2202.00720/) (2022)
- [Convergence of online k-means](https://mlsanity.com/paper/2202.10640/) (2022)
- [Bregman Power k-Means for Clustering Exponential Family Data](https://mlsanity.com/paper/2206.10860/) (2022)
- [Robust Linear Predictions: Analyses of Uniform Concentration, Fast Rates and Model Misspecification](https://mlsanity.com/paper/2201.01973/) (2022)
- [DBGSA: A Novel Data Adaptive Bregman Clustering Algorithm](https://mlsanity.com/paper/2307.14375/) (2023)
- [Dirichlet Process-based Robust Clustering using the Median-of-Means Estimator](https://mlsanity.com/paper/2311.15384/) (2023)
- [A Unified Framework for Center-based Clustering of Distributed Data](https://mlsanity.com/paper/2402.01302/) (2024)
- [A New Framework for Convex Clustering in Kernel Spaces: Finite Sample Bounds, Consistency and Performance Insights](https://mlsanity.com/paper/2511.05159/) (2025)
- [Convex Clustering Redefined: Robust Learning with the Median of Means Estimator](https://mlsanity.com/paper/2511.14784/) (2025)

## Abstract (arXiv)

Recent advances in center-based clustering continue to improve upon the drawbacks of Lloyd's celebrated k-means algorithm over 60 years after its introduction. Various methods seek to address poor local minima, sensitivity to outliers, and data that are not well-suited to Euclidean measures of fit, but many are supported largely empirically. Moreover, combining such approaches in a piecemeal manner can result in ad hoc methods, and the limited theoretical results supporting each individual contribution may no longer hold. Toward addressing these issues in a principled way, this paper proposes a cohesive robust framework for center-based clustering under a general class of dissimilarity measures. In particular, we present a rigorous theoretical treatment within a Median-of-Means (MoM) estimation framework, showing that it subsumes several popular k-means variants. In addition to unifying existing methods, we derive uniform concentration bounds that complete their analyses, and bridge these results to the MoM framework via Dudley's chaining arguments. Importantly, we neither require any assumptions on the distribution of the outlying observations nor on the relative number of observations n to features p. We establish strong consistency and an error rate of O(n-1/2) under mild conditions, surpassing the best-known results in the literature. The methods are empirically validated thoroughly on real and synthetic datasets.