2022/10/19 by Lingxiao Huang, Huang, Lingxiao, Shaofeng H. -C. Jiang +5 · 4 citations
Business, Management and Accounting · Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #Domain Adaptation and Few-Shot Learning #FOS: Computer and information sciences #Facility Location and Emergency Management #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.2210.10394
openalex publication_date 2022/10/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 ⊂ ℝ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.