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:
- Random Shifting: To avoid "edge cases" where points sit right on a grid boundary, the entire dataset is shifted by a shared random vector.
- 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.
- 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.
- 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