Approximation Preserving Coresets

Clustering in a big data setting is an intensively studied problem, with coresets emerging as one of the important paradigms in this line of work. Given a cost function $\text{cost}(P,S)$ mapping input points $P$ and a solution $S$ to an objective value, a coreset is a typically weighted sketch $\Omega\subseteq P$ such that $\text{cost}(\Omega,S)\approx \text{cost}(P,S)$. In practice, coreset sizes much smaller than those suggested by theoretical guarantees are often found to be sufficient. In this paper, we offer an explanation for this phenomenon. Smaller coreset sizes suffice if we only wish to preserve the costs of \emph{good} solutions, i.e., solutions with low cost. We define and devise \emph{approximation-preserving coresets}, which provide a weaker guarantee than strong coresets, which apply to all solutions, while providing stronger guarantees than weak coresets, which apply only to the optimum solution. We complement this result by showing that even a very small distortion in the approximation factor cannot admit coresets of this size.

Clustering algorithms help organize large datasets by grouping similar items together, but running them on millions of points can be slow and memory-intensive. A common shortcut is to first compress the data into a much smaller weighted sample, called a coreset, and then run the clustering algorithm on that summary. Traditional coresets are designed to preserve the quality of every possible clustering solution, including many unusual solutions that practical algorithms are unlikely to produce. This paper shows that we can often use smaller summaries if we only ask them to preserve the performance of the algorithm we actually run. We introduce approximation preserving coresets, which are designed so that any approximate solution found on the summary can be converted into a similarly good solution for the full dataset. For the widely used k-means clustering problem, this gives smaller theoretical summaries than worst-case strong coresets in Euclidean space. We also extend the idea to finite metric spaces. Experiments with k-means++ and local search show that these summaries can preserve solution quality while substantially reducing running time.