Coresets for Robust Clustering via Black-box Reductions to Vanilla Case
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913686255304704 |
|---|---|
| author | Jiang, Shaofeng H. -C. Lou, Jianing |
| author_facet | Jiang, Shaofeng H. -C. Lou, Jianing |
| contents | We devise $ε$-coresets for robust $(k,z)$-Clustering with $m$ outliers through black-box reductions to vanilla case. Given an $ε$-coreset construction for vanilla clustering with size $N$, we construct coresets of size $N\cdot \mathrm{poly}\log(kmε^{-1}) + O_z\left(\min\{kmε^{-1}, mε^{-2z}\log^z(kmε^{-1}) \}\right)$ for various metric spaces, where $O_z$ hides $2^{O(z\log z)}$ factors. This increases the size of the vanilla coreset by a small multiplicative factor of $\mathrm{poly}\log(kmε^{-1})$, and the additive term is up to a $(ε^{-1}\log (km))^{O(z)}$ factor to the size of the optimal robust coreset. Plugging in vanilla coreset results of [Cohen-Addad et al., STOC'21], we obtain the first coresets for $(k,z)$-Clustering with $m$ outliers with size near-linear in $k$ while previous results have size at least $Ω(k^2)$ [Huang et al., ICLR'23; Huang et al., SODA'25].
Technically, we establish two conditions under which a vanilla coreset is as well a robust coreset. The first condition requires the dataset to satisfy special structures - it can be broken into "dense" parts with bounded diameter. We combine this with a new bounded-diameter decomposition that has only $O_z(km ε^{-1})$ non-dense points to obtain the $O_z(km ε^{-1})$ additive bound. Another condition requires the vanilla coreset to possess an extra size-preserving property. We further give a black-box reduction that turns a vanilla coreset to the one satisfying the said size-preserving property, leading to the alternative $O_z(mε^{-2z}\log^{z}(kmε^{-1}))$ additive bound.
We also implement our reductions in the dynamic streaming setting and obtain the first streaming algorithms for $k$-Median and $k$-Means with $m$ outliers, using space $\tilde{O}(k+m)\cdot\mathrm{poly}(dε^{-1}\logΔ)$ for inputs on the grid $[Δ]^d$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_07669 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Coresets for Robust Clustering via Black-box Reductions to Vanilla Case Jiang, Shaofeng H. -C. Lou, Jianing Data Structures and Algorithms We devise $ε$-coresets for robust $(k,z)$-Clustering with $m$ outliers through black-box reductions to vanilla case. Given an $ε$-coreset construction for vanilla clustering with size $N$, we construct coresets of size $N\cdot \mathrm{poly}\log(kmε^{-1}) + O_z\left(\min\{kmε^{-1}, mε^{-2z}\log^z(kmε^{-1}) \}\right)$ for various metric spaces, where $O_z$ hides $2^{O(z\log z)}$ factors. This increases the size of the vanilla coreset by a small multiplicative factor of $\mathrm{poly}\log(kmε^{-1})$, and the additive term is up to a $(ε^{-1}\log (km))^{O(z)}$ factor to the size of the optimal robust coreset. Plugging in vanilla coreset results of [Cohen-Addad et al., STOC'21], we obtain the first coresets for $(k,z)$-Clustering with $m$ outliers with size near-linear in $k$ while previous results have size at least $Ω(k^2)$ [Huang et al., ICLR'23; Huang et al., SODA'25]. Technically, we establish two conditions under which a vanilla coreset is as well a robust coreset. The first condition requires the dataset to satisfy special structures - it can be broken into "dense" parts with bounded diameter. We combine this with a new bounded-diameter decomposition that has only $O_z(km ε^{-1})$ non-dense points to obtain the $O_z(km ε^{-1})$ additive bound. Another condition requires the vanilla coreset to possess an extra size-preserving property. We further give a black-box reduction that turns a vanilla coreset to the one satisfying the said size-preserving property, leading to the alternative $O_z(mε^{-2z}\log^{z}(kmε^{-1}))$ additive bound. We also implement our reductions in the dynamic streaming setting and obtain the first streaming algorithms for $k$-Median and $k$-Means with $m$ outliers, using space $\tilde{O}(k+m)\cdot\mathrm{poly}(dε^{-1}\logΔ)$ for inputs on the grid $[Δ]^d$. |
| title | Coresets for Robust Clustering via Black-box Reductions to Vanilla Case |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2502.07669 |