# Near-optimal Coresets for Robust Clustering

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Oct 2022.

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

- [IDEAL: Influence-Driven Selective Annotations Empower In-Context Learners in Large Language Models](https://mlsanity.com/paper/2310.10873/) (2023)
- [Refined Coreset Selection: Towards Minimal Coreset Size under Model Performance Constraints](https://mlsanity.com/paper/2311.08675/) (2023)
- [On Robust Wasserstein Barycenter: The Model and Algorithm](https://mlsanity.com/paper/2312.15762/) (2023)
- [Data-Efficient Training by Evolved Sampling](https://mlsanity.com/paper/2509.23461/) (2025)
- [Coresets for Clustering Under Stochastic Noise](https://mlsanity.com/paper/2510.23438/) (2025)

## Abstract (arXiv)

We consider robust clustering problems in ℝd, specifically k-clustering problems (e.g., k-Median and k-Means with m outliers, where the cost for a given center set C subset ℝd aggregates the distances from C to all but the furthest m data points, instead of all points as in classical clustering. We focus on the ε-coreset for robust clustering, a small proxy of the dataset that preserves the clustering cost within ε-relative error for all center sets. Our main result is an ε-coreset of size O(m + poly(k ε-1)) that can be constructed in near-linear time. This significantly improves previous results, which either suffers an exponential dependence on (m + k) [Feldman and Schulman, SODA'12], or has a weaker bi-criteria guarantee [Huang et al., FOCS'18]. Furthermore, we show this dependence in m is nearly-optimal, and the fact that it is isolated from other factors may be crucial for dealing with large number of outliers. We construct our coresets by adapting to the outlier setting a recent framework [Braverman et al., FOCS'22] which was designed for capacity-constrained clustering, overcoming a new challenge that the participating terms in the cost, particularly the excluded m outlier points, are dependent on the center set C. We validate our coresets on various datasets, and we observe a superior size-accuracy tradeoff compared with popular baselines including uniform sampling and sensitivity sampling. We also achieve a significant speedup of existing approximation algorithms for robust clustering using our coresets.