Introduction
Clustering is a cornerstone of modern data analysis, used to organize large datasets into meaningful groups. However, standard clustering objectives—such as $k$-means or $k$-median—are notoriously sensitive to noise. A small number of outliers can disproportionately influence the placement of cluster centers, leading to suboptimal results. To address this, researchers utilize robust clustering models, specifically $(k, z, m)$-clustering, which allows an algorithm to ignore up to $m$ outliers to minimize the cost for the remaining points.
As datasets scale to billions of points, the computational overhead of robust clustering becomes prohibitive. This necessitates the use of coresets: small, weighted summaries of the original data that preserve the clustering cost for any set of potential centers. While coresets for "vanilla" (non-robust) clustering are well-studied, constructing efficient coresets for robust clustering has historically been an ad-hoc process resulting in coreset sizes that grow quadratically with the number of clusters ($k$). This paper introduces a novel "black-box" framework that transforms standard coreset algorithms into robust ones, achieving near-linear coreset sizes and enabling the first dynamic streaming algorithms for robust clustering.
The Robust Clustering Problem
In $(k, z, m)$-clustering, the goal is to find a set of $k$ centers $C$ that minimizes the sum of distances (raised to power $z$) from all points to their nearest center, excluding the $m$ points with the largest distances. The challenge in building coresets for this objective is that the set of $m$ outliers is not fixed; it changes depending on the choice of centers $C$.
Previous state-of-the-art methods for robust coresets suffered from a size complexity of $\Omega(k^2)$. This quadratic dependency on $k$ limits the utility of coresets in high-complexity scenarios where many clusters are required. This work seeks to bridge the gap between vanilla and robust clustering efficiency.
Methodology: Black-box Reductions
The authors propose a framework that treats existing vanilla coreset algorithms as a "black box." Instead of designing a new robust algorithm from scratch, they identify the conditions under which a vanilla coreset naturally handles outliers.
1. Dense Datasets and Sparse Partitions
The authors observe that if a dataset is "dense"—meaning points are clustered in large, tight groups—a vanilla coreset is inherently robust. In such cases, no small group of points (outliers) can significantly shift the total clustering cost. The framework uses an "almost-dense decomposition" to partition the data into a large dense component and a small sparse component, simplifying the robust approximation.
2. Size-Preserving Property
A key insight of the paper is that if a coreset algorithm preserves the number of points within different regions of the metric space (a "size-preserving" property), it can be adapted for robust clustering. To enforce this property across any vanilla algorithm, the authors introduce Separated Duplication. This technique mathematically "stretches" the metric space, effectively placing different segments of the data at an infinite distance from one another. This forces the vanilla algorithm to treat each segment independently, ensuring that the resulting coreset accurately represents the point distribution needed to identify outliers.
Key Results
Near-Linear Coreset Sizes
By applying this reduction, the authors achieve the first coresets for robust clustering with a size near-linear in $k$. In Euclidean space, for instance, the dependency is improved from $O(k^2)$ to $k \cdot \text{poly log}(k)$. This reduction in size significantly lowers the "price of robustness," showing that the overhead for handling outliers is much smaller than previously theorized.
Dynamic Streaming
The framework enables the first dynamic streaming algorithms for robust $k$-median and $k$-means. In a dynamic stream where points are both inserted and deleted, the algorithm maintains a coreset using space complexity of roughly $\tilde{O}(k + m)$. This is achieved through a consistent hashing technique that partitions the space into "buckets," allowing the algorithm to distinguish between dense regions and potential outliers on the fly.
Deterministic Construction
Unlike many coreset methods that rely on randomized sampling, this reduction is deterministic if the underlying vanilla coreset algorithm is deterministic. This provides a level of reliability and reproducibility valuable for sensitive data applications.
Conclusion and Future Work
This work provides a unified, theoretically grounded approach to robust clustering. By reducing the robust problem to the vanilla case, the authors have simplified the landscape of coreset construction and provided powerful new tools for big data analysis.
However, some challenges remain. The current coreset sizes grow exponentially with the power $z$, which may limit applications for higher-order clustering objectives. Additionally, the dynamic streaming implementation currently assumes a discrete grid, and extending this to continuous spaces without grid-dependency is a promising avenue for future research. Despite these limitations, the near-linear bounds and black-box flexibility represent a significant leap forward in the efficiency of robust machine learning.
Summary updated