Fault Tolerant Coresets

Coresets are widely used to compress large datasets into small weighted summaries. We mainly focus on the $k$-means objective where the cost is defined to be the sum of squared distances of every point to its closest center. A coreset approximately preserves the cost of every candidate set of $k$ centers up to a small $(1\pm \varepsilon)$ multiplicative error. By far the most flexible and powerful technique in this line of work is sensitivity sampling, where we pick points proportionate to their highest relative cost contribution in any solution. In general, the transmission and storage of these coresets are assumed to be reliable and always keep the coreset intact, without accounting for the possibility of corruptions. This raises a basic question: To what extent can coresets be made fault-tolerant? We study an adversarial fault model in which up to $f$ points of the coreset may be arbitrarily corrupted, including their weights, and the goal is to recover a valid coreset from the corrupted summary. Our main result shows that sensitivity sampling yields fault-tolerant coresets of size $O(f\cdot k/\varepsilon + m)$, where $m$ is the size of a non-fault-tolerant coreset computed via sensitivity sampling. This result is also optimal in that any fault-tolerant $k$-means coreset must have size $\Omega(f \cdot k/\varepsilon)$. The decoding algorithm computing a sanitized coreset from a corrupted one is efficient and we demonstrate practical viability via our experiments.