# Robust Bregman Clustering

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Dec 2018.

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

- [Uniform Concentration Bounds toward a Unified Framework for Robust Clustering](https://mlsanity.com/paper/2110.14148/) (2021)
- [Bregman Power k-Means for Clustering Exponential Family Data](https://mlsanity.com/paper/2206.10860/) (2022)
- [Universal Lower Bounds and Optimal Rates: Achieving Minimax Clustering Error in Sub-Exponential Mixture Models](https://mlsanity.com/paper/2402.15432/) (2024)
- [DBGSA: A Novel Data Adaptive Bregman Clustering Algorithm](https://mlsanity.com/paper/2307.14375/) (2023)
- [Topological Analysis for Detecting Anomalies (TADA) in Time Series](https://mlsanity.com/paper/2406.06168/) (2024)
- [Consistency and inconsistency in k-means clustering](https://mlsanity.com/paper/2507.06226/) (2025)
- [Convex Clustering Redefined: Robust Learning with the Median of Means Estimator](https://mlsanity.com/paper/2511.14784/) (2025)

## Abstract (arXiv)

Using a trimming approach, we investigate a k-means type method based on Bregman divergences for clustering data possibly corrupted with clutter noise. The main interest of Bregman divergences is that the standard Lloyd algorithm adapts to these distortion measures, and they are well-suited for clustering data sampled according to mixture models from exponential families. We prove that there exists an optimal codebook, and that an empirically optimal codebook converges a.s. to an optimal codebook in the distortion sense. Moreover, we obtain the sub-Gaussian rate of convergence for k-means 1 √ n under mild tail assumptions. Also, we derive a Lloyd-type algorithm with a trimming parameter that can be selected from data according to some heuristic, and present some experimental results.