Resilient Coresets and Clustering

Ashkan Norouzi-Fard, Silvio Lattanzi, Mohammadhossein Bateni, Morteza MonemizadehICML 2026 · OpenReview

TL;DR

This paper introduces resilient coresets, a new type of data summary for clustering that remains stable even when data is slightly perturbed (e.g., by noise or dimensionality reduction). The authors provide a novel grid-based construction for these coresets and prove that achieving such stability inherently requires "bi-criteria" solutions—meaning you must open more than the standard $k$ centers to maintain a tight approximation.

What Problem Does This Paper Address?

In modern machine learning, data is rarely static. It is routinely transformed through dimensionality reduction (like PCA), random projections, feature embeddings, or privacy-preserving noise. While these transformations are designed to preserve the overall "geometry" of the data, they often fail a crucial test: algorithmic consistency.

If you run a clustering algorithm on a dataset and then run it again on a slightly perturbed version of that same data, you might get wildly different cluster assignments, even if the total "cost" of the clustering remains similar. This instability is a nightmare for downstream tasks that rely on stable point-to-cluster assignments.

The authors tackle this by extending the recently proposed notion of $\gamma$-resilience to coresets. A coreset is a tiny, weighted version of a massive dataset that acts as a proxy for optimization. The challenge is: can we build a coreset that is not only small and accurate but also "resilient"—meaning the assignments it produces don't flip-flop when the input data moves slightly?

Methods

The authors propose an algorithm called RESILIENTCORESET. Their approach is a significant evolution of standard grid-based coreset techniques:

  1. Random Shifting: To avoid "edge cases" where points sit right on a grid boundary, the entire dataset is shifted by a shared random vector.
  2. Hierarchical Quadtree Partitioning: The space is divided into a hierarchy of grids. Cells are classified as "heavy" (lots of points) or "light" (few points). Heavy cells are recursively subdivided.
  3. The "Pivot Grid" Innovation: This is the core technical contribution. In standard coresets, a point is usually represented by a center within its own small grid cell. This is unstable; a tiny nudge could push a point into a neighboring cell. Instead, the authors assign points to representatives in pivot grids—coarser ancestor cells in the hierarchy.
  4. Coupling and Shared Randomness: By using the same random bits across different versions of the data, the algorithm ensures that discrete decisions (like which point becomes a representative) are "coupled" and remain consistent across perturbations.

Datasets

This is a theoretical paper, so it does not evaluate performance on standard ML benchmarks like ImageNet or MNIST. Instead, the authors use:

  • Synthetic Hard Instances: To prove their lower bounds (hardness results), they construct specific 1-dimensional "path" graphs. These instances consist of well-separated clusters where small changes in edge weights force any stable algorithm to significantly change its behavior unless it uses extra centers.

Key Insights and Ideas

  • Stability has a Price: The most significant "aha moment" is the proof that resilience is fundamentally at odds with strict $k$-clustering. To get a $(1+\epsilon)$ approximation that is also stable, you must be willing to use more than $k$ centers (a bi-criteria solution).
  • Buffering via Coarseness: The use of pivot grids acts as a geometric buffer. By representing a group of points using a representative from a much larger "ancestor" cell, the algorithm makes it much less likely that a small perturbation will cause a point to be re-assigned to a different representative.
  • Pointwise vs. Objective Agreement: Classical approximation theory only cares if the final "score" (cost) is close. Resilience demands pointwise agreement, ensuring that individual data points are handled consistently. This is a much stricter and more practical requirement for real-world pipelines.

Key Results

  • The Positive Result: The authors provide a construction for a $\gamma$-resilient $(k, \epsilon)$-coreset for $k$-median and $k$-means clustering.
  • Size: The coreset size is $O(\epsilon^{-dk} \log \Delta + d^{d/2}\epsilon^{-2d-2}\log^2 \Delta)$, which is efficient for constant dimensions ($d$).
  • Resilience: They achieve a resilience factor of $\gamma = O\left(\frac{\sqrt{d}(1+\xi)}{\log \epsilon^{-1}}\right)$, meaning only a small fraction of assignments change under a $\xi$-perturbation.
  • The Hardness Result: They prove a lower bound showing that for any constant approximation, the resilience factor $\gamma$ cannot be better than $\Omega(\ln(1+\xi)/\xi)$ in 1D space. This justifies why their algorithm needs to open more centers to achieve high accuracy.

Limitations and Future Work

  • The Curse of Dimensionality: The current coreset construction has an exponential dependence on the dimension $d$. While standard for grid-based methods, it limits the approach to low-dimensional or projected spaces.
  • Bi-criteria Requirement: The necessity of using more than $k$ centers might be a deal-breaker for applications with a strict "budget" of clusters.
  • Future Directions: The authors suggest that exploring resilience in high-dimensional spaces (perhaps using dimensionality reduction techniques that are themselves resilient) is a promising next step. There is also an open question about whether these bounds can be tightened for specific metric spaces beyond Euclidean.

Summary updated

Abstract

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.
BibTeX
@inproceedings{norouzifard2026resilient,
  author = {Ashkan Norouzi-Fard and Silvio Lattanzi and Mohammadhossein Bateni and Morteza Monemizadeh},
  title = {{Resilient Coresets and Clustering}},
  booktitle = {International Conference on Machine Learning},
  year = {2026},
  url = {https://openreview.net/forum?id=9wVto5mXYd},
}
Figure