# Convex Clustering Redefined: Robust Learning with the Median of Means Estimator

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 47 references that are in the map.
- First posted on arXiv 12 Nov 2025.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Explainable k-Means and k-Medians Clustering](https://mlsanity.com/paper/2002.12538/) (2020)
- [Statistical and Computational Guarantees of Lloyd's Algorithm and its Variants](https://mlsanity.com/paper/1612.02099/) (2016)
- [Splitting Methods for Convex Clustering](https://mlsanity.com/paper/1304.0499/) (2013)
- [Statistical Properties of Convex Clustering](https://mlsanity.com/paper/1503.08340/) (2015)
- [Clustering subgaussian mixtures by semidefinite programming](https://mlsanity.com/paper/1602.06612/) (2016)
- [Lecture Notes: Selected topics on robust statistical learning theory](https://mlsanity.com/paper/1908.10761/) (2019)
- [Relax, no need to round: integrality of clustering formulations](https://mlsanity.com/paper/1408.4045/) (2014)
- [Regularization, sparse recovery, and median-of-means tournaments](https://mlsanity.com/paper/1701.04112/) (2017)
- [Recovering Trees with Convex Clustering](https://mlsanity.com/paper/1806.11096/) (2018)
- [Uniform Concentration Bounds toward a Unified Framework for Robust Clustering](https://mlsanity.com/paper/2110.14148/) (2021)
- [Scalable Spectral Clustering Using Random Binning Features](https://mlsanity.com/paper/1805.11048/) (2018)
- [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)
- [Convex clustering via ℓ1 fusion penalization](https://mlsanity.com/paper/1412.0753/) (2014)
- [A survey on feature weighting based K-Means algorithms](https://mlsanity.com/paper/1601.03483/) (2015)
- [Revisiting Random Binning Features: Fast Convergence and Strong Parallelizability](https://mlsanity.com/paper/1809.05247/) (2018)
- [On Medians of (Randomized) Pairwise Means](https://mlsanity.com/paper/2211.00603/) (2022)

## Abstract (arXiv)

Clustering approaches that utilize convex loss functions have recently attracted growing interest in the formation of compact data clusters. Although classical methods like k-means and its wide family of variants are still widely used, all of them require the number of clusters k to be supplied as input, and many are notably sensitive to initialization. Convex clustering provides a more stable alternative by formulating the clustering task as a convex optimization problem, ensuring a unique global solution. However, it faces challenges in handling high-dimensional data, especially in the presence of noise and outliers. Additionally, strong fusion regularization, controlled by the tuning parameter, can hinder effective cluster formation within a convex clustering framework. To overcome these challenges, we introduce a robust approach that integrates convex clustering with the Median of Means (MoM) estimator, thus developing an outlier-resistant and efficient clustering framework that does not necessitate prior knowledge of the number of clusters. By leveraging the robustness of MoM alongside the stability of convex clustering, our method enhances both performance and efficiency, especially on large-scale datasets. Theoretical analysis demonstrates weak consistency under specific conditions, while experiments on synthetic and real-world datasets validate the method's superior performance compared to existing approaches.