# Coresets for Clustering Under Stochastic Noise

arXiv: https://arxiv.org/abs/2510.23438 · HTML: https://mlsanity.com/paper/2510.23438/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 24 of its 87 references that are in the map.
- First posted on arXiv 27 Oct 2025.

## Builds on (most cited first, 24 of 24)

- [Certified Adversarial Robustness with Additive Noise](https://mlsanity.com/paper/1809.03113/) (2018)
- [Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering](https://mlsanity.com/paper/1807.04518/) (2018)
- [New Frameworks for Offline and Streaming Coreset Constructions](https://mlsanity.com/paper/1612.00889/) (2016)
- [A New Coreset Framework for Clustering](https://mlsanity.com/paper/2104.06133/) (2021)
- [Simultaneous Private Learning of Multiple Concepts](https://mlsanity.com/paper/1511.08552/) (2015)
- [Differentially Private Clustering: Tight Approximation Ratios](https://mlsanity.com/paper/2008.08007/) (2020)
- [Blind Universal Bayesian Image Denoising with Gaussian Noise Level Learning](https://mlsanity.com/paper/1907.03029/) (2019)
- [Towards Optimal Lower Bounds for k-median and k-means Coresets](https://mlsanity.com/paper/2202.12793/) (2022)
- [varepsilon-Coresets for Clustering (with Outliers) in Doubling Metrics](https://mlsanity.com/paper/1804.02530/) (2018)
- [Coresets for Vertical Federated Learning: Regularized Linear Regression and K-Means Clustering](https://mlsanity.com/paper/2210.14664/) (2022)
- [On the Local Structure of Stable Clustering Instances](https://mlsanity.com/paper/1701.08423/) (2017)
- [A flexible EM-like clustering algorithm for noisy data](https://mlsanity.com/paper/1907.01660/) (2019)
- [Approximation Schemes for Clustering with Outliers](https://mlsanity.com/paper/1707.04295/) (2017)
- [Fully-Dynamic Coresets](https://mlsanity.com/paper/2004.14891/) (2020)
- [Fairness for AUC via Feature Augmentation](https://mlsanity.com/paper/2111.12823/) (2021)
- [On Fair Selection in the Presence of Implicit and Differential Variance](https://mlsanity.com/paper/2112.05630/) (2021)
- [On Optimal Coreset Construction for Euclidean (k,z)-Clustering](https://mlsanity.com/paper/2211.11923/) (2022)
- [Coresets for Time Series Clustering](https://mlsanity.com/paper/2110.15263/) (2021)
- [Robust and Fully-Dynamic Coreset for Continuous-and-Bounded Learning (With Outliers) Problems](https://mlsanity.com/paper/2107.00068/) (2021)
- [Near-optimal Coresets for Robust Clustering](https://mlsanity.com/paper/2210.10394/) (2022)
- [Sensitivity Sampling for k-Means: Worst Case and Stability Optimal Coreset Bounds](https://mlsanity.com/paper/2405.01339/) (2024)
- [Differentially Private Location Privacy in Practice](https://mlsanity.com/paper/1410.7744/) (2014)
- [The Power of Uniform Sampling for k-Median](https://mlsanity.com/paper/2302.11339/) (2023)
- [Provably noise-robust, regularised k-means clustering](https://mlsanity.com/paper/1711.11247/) (2017)

## Abstract (arXiv)

We study the problem of constructing coresets for (k, z)-clustering when the input dataset is corrupted by stochastic noise drawn from a known distribution. In this setting, evaluating the quality of a coreset is inherently challenging, as the true underlying dataset is unobserved. To address this, we investigate coreset construction using surrogate error metrics that are tractable and provably related to the true clustering cost. We analyze a traditional metric from prior work and introduce a new error metric that more closely aligns with the true cost. Although our metric is defined independently of the noise distribution, it enables approximation guarantees that scale with the noise level. We design a coreset construction algorithm based on this metric and show that, under mild assumptions on the data and noise, enforcing an varepsilon-bound under our metric yields smaller coresets and tighter guarantees on the true clustering cost than those obtained via classical metrics. In particular, we prove that the coreset size can improve by a factor of up to poly(k), where n is the dataset size. Experiments on real-world datasets support our theoretical findings and demonstrate the practical advantages of our approach.