# Distributionally Robust K-Means Clustering

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 33 references that are in the map.
- First posted on arXiv 13 Apr 2026.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Distributionally Robust Stochastic Optimization with Wasserstein Distance](https://mlsanity.com/paper/1604.02199/) (2016)
- [Wasserstein Distributionally Robust Optimization: Theory and Applications in Machine Learning](https://mlsanity.com/paper/1908.08729/) (2019)
- [Wasserstein Distributionally Robust Kalman Filtering](https://mlsanity.com/paper/1809.08830/) (2018)
- [Robust k-means Clustering for Distributions with Two Moments](https://mlsanity.com/paper/2002.02339/) (2020)
- [Robust Trimmed k-means](https://mlsanity.com/paper/2108.07186/) (2021)
- [Improved Outlier Robust Seeding for k-means](https://mlsanity.com/paper/2309.02710/) (2023)
- [Wasserstein Distributionally Robust Regret-Optimal Control in the Infinite-Horizon](https://mlsanity.com/paper/2312.17376/) (2023)
- [Clustering High-dimensional Data via Feature Selection](https://mlsanity.com/paper/2210.15801/) (2022)
- [Adaptively Robust and Sparse K-means Clustering](https://mlsanity.com/paper/2407.06945/) (2024)

## Abstract (arXiv)

K-means clustering is a workhorse of unsupervised learning, but it is notoriously brittle to outliers, distribution shifts, and limited sample sizes. Viewing k-means as Lloyd--Max quantization of the empirical distribution, we develop a distributionally robust variant that protects against such pathologies. We posit that the unknown population distribution lies within a Wasserstein-2 ball around the empirical distribution. In this setting, one seeks cluster centers that minimize the worst-case expected squared distance over this ambiguity set, leading to a minimax formulation. A tractable dual yields a soft-clustering scheme that replaces hard assignments with smoothly weighted ones. We propose an efficient block coordinate descent algorithm with provable monotonic decrease and local linear convergence. Experiments on standard benchmarks and large-scale synthetic data demonstrate substantial gains in outlier detection and robustness to noise.