# varepsilon-Coresets for Clustering (with Outliers) in Doubling Metrics

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

## Key facts

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

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

- [IDEAL: Influence-Driven Selective Annotations Empower In-Context Learners in Large Language Models](https://mlsanity.com/paper/2310.10873/) (2023)
- [Towards Optimal Lower Bounds for k-median and k-means Coresets](https://mlsanity.com/paper/2202.12793/) (2022)
- [New Coresets for Projective Clustering and Applications](https://mlsanity.com/paper/2203.04370/) (2022)
- [Coresets for Vertical Federated Learning: Regularized Linear Regression and K-Means Clustering](https://mlsanity.com/paper/2210.14664/) (2022)
- [Refined Coreset Selection: Towards Minimal Coreset Size under Model Performance Constraints](https://mlsanity.com/paper/2311.08675/) (2023)
- [A Novel Sequential Coreset Method for Gradient Descent Algorithms](https://mlsanity.com/paper/2112.02504/) (2021)
- [An Empirical Evaluation of k-Means Coresets](https://mlsanity.com/paper/2207.00966/) (2022)
- [Robust and Fully-Dynamic Coreset for Continuous-and-Bounded Learning (With Outliers) Problems](https://mlsanity.com/paper/2107.00068/) (2021)
- [Coresets for Wasserstein Distributionally Robust Optimization Problems](https://mlsanity.com/paper/2210.04260/) (2022)
- [No Dimensional Sampling Coresets for Classification](https://mlsanity.com/paper/2402.05280/) (2024)
- [A Tight VC-Dimension Analysis of Clustering Coresets with Applications](https://mlsanity.com/paper/2501.06588/) (2025)
- [Coresets for constrained k-median and k-means clustering in low dimensional Euclidean space](https://mlsanity.com/paper/2106.07319/) (2021)
- [Is Simple Uniform Sampling Effective for Center-Based Clustering with Outliers: When and Why?](https://mlsanity.com/paper/2103.00558/) (2021)
- [Coresets for Relational Data and The Applications](https://mlsanity.com/paper/2210.04249/) (2022)
- [Randomized Greedy Algorithms and Composable Coreset for k-Center Clustering with Outliers](https://mlsanity.com/paper/2301.02814/) (2023)
- [On Robust Wasserstein Barycenter: The Model and Algorithm](https://mlsanity.com/paper/2312.15762/) (2023)
- [Sublinear Time Algorithms for Several Geometric Optimization (With Outliers) Problems In Machine Learning](https://mlsanity.com/paper/2301.02870/) (2023)
- [Universal Weak Coreset](https://mlsanity.com/paper/2305.16890/) (2023)
- [Coresets for Clustering Under Stochastic Noise](https://mlsanity.com/paper/2510.23438/) (2025)

## Abstract (arXiv)

We study the problem of constructing varepsilon-coresets for the (k, z)-clustering problem in a doubling metric M(X, d). An varepsilon-coreset is a weighted subset Ssubseteq X with weight function w : S rightarrow ℝ≥ 0, such that for any k-subset C ∈ [X]k, it holds that sumx ∈ Sw(x) · dz(x, C) ∈ (1 ± varepsilon) · sumx ∈ Xdz(x, C). We present an efficient algorithm that constructs an varepsilon-coreset for the (k, z)-clustering problem in M(X, d), where the size of the coreset only depends on the parameters k, z, varepsilon and the doubling dimension mathsfddim(M). To the best of our knowledge, this is the first efficient varepsilon-coreset construction of size independent of |X| for general clustering problems in doubling metrics. To this end, we establish the first relation between the doubling dimension of M(X, d) and the shattering dimension (or VC-dimension) of the range space induced by the distance d. Such a relation was not known before, since one can easily construct instances in which neither one can be bounded by (some function of) the other. Surprisingly, we show that if we allow a small (1±ε)-distortion of the distance function d, and consider the notion of τ-error probabilistic shattering dimension, we can prove an upper bound of O( mathsfddim(M)· log(1/varepsilon) +loglogfrac1τ ) for the probabilistic shattering dimension for even weighted doubling metrics. We believe this new relation is of independent interest and may find other applications. We also study the robust coresets and centroid sets in doubling metrics. Our robust coreset construction leads to new results in clustering and property testing, and the centroid sets can be used to accelerate the local search algorithms for clustering problems.