Coresets for Robust Clustering via Black-Box Reductions to Vanilla Case Article Swipe

MAKE IMPACT

Shaofeng H.-C. Jiang , Jianing Lou · YOU? · · 2025 · Open Access · · DOI: https://doi.org/10.4230/lipics.icalp.2025.101

We devise ε-coresets for robust (k,z)-Clustering with m outliers through black-box reductions to vanilla clustering. Given an ε-coreset construction for vanilla clustering with size N, we construct coresets of size N⋅ polylog(kmε^{-1}) + O_z(min{kmε^{-1}, m ε^{-2z}log^z(kmε^{-1})}) for various metric spaces, where O_z hides 2^{O(zlog z)} factors. This increases the size of the vanilla coreset by a small multiplicative factor of polylog(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 recent vanilla coreset results of [Cohen-Addad, Saulpic and Schwiegelshohn, STOC'21; Cohen-Addad, Draganov, Russo, Saulpic and Schwiegelshohn, SODA'25], 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²) [Huang, Jiang, Lou and Wu, ICLR'23; Huang, Li, Lu and Wu, 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 sufficient condition requires the vanilla coreset to possess an extra size-preserving property. To utilize this condition, we further give a black-box reduction that turns a vanilla coreset to the one that satisfies the said size-preserving property, and this leads to the alternative O_z(mε^{-2z}log^{z}(kmε^{-1})) additive size bound. We also give low-space implementations of our reductions in the dynamic streaming setting. Combined with known streaming constructions for vanilla coresets [Braverman, Frahling, Lang, Sohler and Yang, ICML'17; Hu, Song, Yang and Zhong, arXiv'1802.00459], we obtain the first dynamic streaming algorithms for coresets for k-Median (and k-Means) with m outliers, using space Õ(k + m) ⋅ poly(dε^{-1}log Δ) for inputs on a discrete grid [Δ]^d.

Type

preprint

Language

en

Landing Page

http://arxiv.org/abs/2502.07669

PDF

https://arxiv.org/pdf/2502.07669

OA Status

green

Related Works

10

OpenAlex ID

https://openalex.org/W4407425769

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W4407425769

Canonical identifier for this work in OpenAlex

DOI

https://doi.org/10.4230/lipics.icalp.2025.101

Digital Object Identifier

Title

Coresets for Robust Clustering via Black-Box Reductions to Vanilla Case

Work title

Type

preprint

OpenAlex work type

Language

en

Primary language

Publication year

2025

Year of publication

Publication date

2025-01-01

Full publication date if available

Authors

Shaofeng H.-C. Jiang, Jianing Lou

List of authors in order

Landing page

https://arxiv.org/abs/2502.07669

Publisher landing page

PDF URL

https://arxiv.org/pdf/2502.07669

Direct link to full text PDF

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://arxiv.org/pdf/2502.07669

Direct OA link when available

Concepts

Cluster analysis, Black box, Computer science, Mathematics, Artificial intelligence

Top concepts (fields/topics) attached by OpenAlex

Cited by

0

Total citation count in OpenAlex

Related works (count)

10

Other works algorithmically related by OpenAlex

Full payload