Fault Tolerant Coresets

Milind Prabhu, Chris Schwiegelshohn, Sudarshan ShyamarXiv 2026 · arXiv

TL;DR

Standard data summaries (coresets) are highly efficient but notoriously fragile—corrupting just a few entries can ruin their accuracy. This paper introduces Fault Tolerant Coresets, proving that by adding a small, optimal amount of redundancy via sensitivity sampling, we can recover a highly accurate summary even after an adversary corrupts $f$ entries.

What Problem Does This Paper Address?

In the era of massive datasets, we often use coresets: small, weighted subsets of data that act as a "proxy" for the full set. For tasks like $k$-means clustering, a good coreset ensures that the cost of any set of centers on the summary is nearly identical to the cost on the original data.

However, coresets are designed for maximum compression, meaning they have almost zero redundancy. This makes them vulnerable. If a few weighted points are altered during storage or transmission (due to hardware faults, packet loss, or adversarial attacks), the entire summary can become useless. The authors ask: Can we build a coreset that is robust to $f$ adversarial corruptions without losing the benefits of compression?

Methods

The authors build upon the sensitivity sampling framework. In this standard approach, points are sampled with a probability proportional to their "sensitivity"—a measure of how much an individual point can influence the total clustering cost.

The Innovation: 1. Oversampling: Instead of the standard coreset size $m$, they show that adding an additive term of $O(fk/\varepsilon)$ points provides enough "buffer" to survive $f$ corruptions. 2. Iterative Peeling Decoder: To recover the coreset, they don't just look at the data once. They use an iterative algorithm that identifies the point with the highest sensitivity in the corrupted set, deletes it, and repeats this $f$ times.

The logic is elegant: if a corrupted point is "loud" enough to distort the clustering results, it will have a high sensitivity and be "peeled" away by the decoder. If its sensitivity is low, it’s "quiet" enough that it won't significantly hurt the final approximation.

Datasets

The researchers evaluated their approach on several standard machine learning benchmarks:

  • Adult: Census data (specifically the age coordinate).
  • Taxi: 1.7 million GPS endpoints from the Porto taxi dataset.
  • MNIST: The classic handwritten digit dataset.
  • CoverType: Forest cover type data.
  • Synthetic Simplex: A high-dimensional synthetic dataset designed to expose the weaknesses of "proxy" sensitivity scores.

Key Insights and Ideas

  • Redundancy doesn't have to be expensive: Traditionally, making something fault-tolerant involves multiplying its size (e.g., storing three copies of everything). This paper shows that for coresets, you only need an additive increase in size, which is much more efficient.
  • The Masking Effect: You cannot simply remove the $f$ most sensitive points in one shot. An adversary can use one "massive" corruption to hide other smaller corruptions. The iterative "peeling" approach is essential to uncover and remove these masked faults.
  • Sensitivity as a Robustness Metric: The same property that makes sensitivity sampling good for approximation (spreading out the "importance" of data points) makes it naturally suited for fault tolerance.

Key Results

  • Theoretical Optimality: The authors prove that their additive overhead of $O(fk/\varepsilon)$ is theoretically optimal for any algorithm that recovers a coreset by selecting a subset of the corrupted points.
  • Adversarial Recovery: In experiments on the Adult dataset ($k=2, f=5$), the raw corrupted coreset had a massive distortion of 46.875. After applying their iterative decoder, the distortion dropped to a near-perfect 1.072.
  • Superiority over Practical Baselines: On the Taxi dataset, their fault-tolerant sensitivity sampling achieved a mean distortion of 1.124, significantly outperforming popular coreset implementations like BICO (1.689) and StreamKM++ (1.686) under the same corruption budget.

Limitations and Future Work

  • Computational Complexity: Finding the exact sensitivity of a point for $k$-means is NP-hard. While the paper provides a reduction to "constrained $k$-means" to approximate it, this remains computationally intensive for very high-dimensional data.
  • Scope of Objectives: The current framework is tailored for "pointwise-loss" objectives like $k$-means and $k$-median. It is not yet clear if these results translate to more complex geometric problems (like directional width) or fair clustering objectives where sensitivity sampling isn't the standard tool.
  • Non-Subset Decoders: The lower bounds in this paper apply to decoders that only keep a subset of the points. Future work could explore "generative" decoders that might achieve even smaller sizes by synthesizing new points during recovery.

Summary updated

Abstract

Coresets are small weighted summaries of large datasets that help quickly evaluate some loss objectives on the input dataset. We mainly focus on coresets for the $k$-means objective, where the cost of the input dataset with respect to a set of $k$ centers is the sum of squared distances from each point to its closest center. A $k$-means $\varepsilon$-coreset $Ω$ satisfies $\mathrm{cost}(P,S)=(1\pm\varepsilon)\mathrm{cost}(Ω,S)$ for every set $S$ of $k$ centers, where $P$ denotes the input dataset. A long line of work has established near optimal $\varepsilon$-coreset size bounds for $k$-means. A key assumption in these works is that the coreset remains intact after construction. The question we ask is the following: if an adversary corrupts at most $f$ weighted entries of an $\varepsilon$-coreset, can we recover an $O(\varepsilon)$-coreset via a decoding algorithm that is given only the corrupted coreset. This models situations where entries of the coreset can be corrupted during storage or transmission, and recovery must proceed without access to the original dataset. Our main result shows that increasing the usual coreset size by an additive $O(fk/\varepsilon)$ yields a coreset that can be decoded into an $O(\varepsilon)$-coreset after any $f$ adversarial corruptions. This bound is achieved by sensitivity sampling, a widely used method for constructing coresets. Our result is optimal in the sense that any fault tolerant coreset, whose decoding algorithm only keeps a subset of the points must also have size $Ω(fk/\varepsilon)$. Our experiments demonstrate recovery under adversarial corruptions.
BibTeX
@misc{prabhu2026fault,
  author = {Milind Prabhu and Chris Schwiegelshohn and Sudarshan Shyam},
  title = {{Fault Tolerant Coresets}},
  year = {2026},
  eprint = {2611.17574},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.17574},
}
Figure