Resilient Coresets and Clustering

Many machine learning problems are geometric at their core, relying on metric representations of data for tasks such as clustering, prototype selection, nearest-neighbor search, and graph-based learning. Furthermore, data is constantly evolving and it is routinely transformed through dimensionality reduction, random projections, feature embeddings, compression, or privacy-preserving mechanisms. These transformations are designed to preserve geometry approximately. As a result, they preserve objective values for many geometric optimization problems, but they fail to guarantee that algorithmic outcomes remain consistent. In this work, we study \emph{resilient data summaries} for geometric optimization. Building on the notion of \emph{$\gamma$-resilient algorithms} from Ahmadian, we introduce $\gamma$-resilient coresets. A $\gamma$-resilient $(k,\varepsilon)$-coreset is a compact, weighted summary that guarantees a $(1+\varepsilon)$ approximation to the objective and enforces stability at the level of assignments. We complement our positive result with a lower bound showing that to obtain a tight approximation for resilient clustering it is necessary to use a bi-criteria solution.

Many machine learning tasks, such as grouping similar items or finding representatives, depend on measuring distances between data points. However, real-world data is often transformed — through compression, privacy protection, or other methods — in ways that approximately preserve distances. While these transformations preserve the quality of the final solution, they can cause the actual outputs (like which point is chosen as a representative) to change unpredictably. This inconsistency is a problem when decisions must be stable and interpretable. We introduce a new type of data summary called a resilient coreset. A coreset is a small, weighted subset of the data that captures its essential structure. Our resilient coreset guarantees both high accuracy and stable assignments: even when the data is slightly perturbed or transformed, the resulting summary and the way points are assigned to it remain mostly the same. Our work provides the theoretical guarantees for stable data summaries under geometric transformations. This helps make machine learning systems more reliable and interpretable, which is especially important when data is noisy or when decisions must be audited and trusted.