Research map / Learning theory and algorithms / Clustering

Coresets for Clustering Under Stochastic Noise

NeurIPS 2025 · Learning theory and algorithms › Clustering · approach: Coresets and dynamic clustering

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Constructs coresets for k-means under known stochastic additive noise by using a new approximation-ratio surrogate error metric (err_alpha) and a noise-aware cluster-wise uniform sampling algorithm (CN_alpha), with guarantees scaling with the noise level.

Problem

Coreset construction for (k,z)-clustering when the observed dataset is corrupted by known stochastic additive noise, so the true clean dataset and its clustering cost are unobserved and coreset quality cannot be directly evaluated.

Approach

Replace the classical relative-error surrogate err (which inflates under noise) with err_alpha, which compares the relative quality of center sets on the true versus coreset data; a noise-aware algorithm removes highly noisy points, partitions into k clusters and uniformly samples from each, yielding smaller coresets and tighter guarantees when cost stability and limited-outlier assumptions hold.

Key results

• Theory: err_alpha-based algorithm CN_alpha gives coreset size about O~(k/eps) versus O~(min{k^1.5/eps^2, k/eps^4}) for classical CN, improving by a factor of sqrt(k)/eps when noise is small.
• Bound on the true-cost approximation ratio improves by at least a poly(k) factor over the err-based bound (noise term O(theta k d/OPT) vs O(theta n d/OPT + sqrt(theta n d/OPT))).
• Synthetic 3-means example: err ~0.41 versus err_1 ~0.74 at beta=2.5, showing the two metrics diverge.

Measured effects reported in the paper

Surprising findings

• The classical err metric is nearly insensitive to cluster-geometry changes under noise, while err_alpha tracks them.

Limitations

• Requires cost-stability and limited-outlier assumptions on the underlying data for the improved guarantees.
• Requires known noise level theta and OPT_P (estimated via O(1)-approximate center set); the theory covers only the regime theta <= OPT_P/(nd).
• Composition of err_alpha is not straightforward and mergeability holds only under structural similarity conditions.

Experimental setup

Datasets: real-world datasets (unspecified in provided text)

Benchmarks: real-world datasets (names not given in provided text)

Metrics: coreset size approximation ratio r_P err err_alpha

Baselines: CN (classical err-based coreset) importance sampling coreset

Builds on: importance sampling coresets for k-means classical relative-error coreset metric cost stability Bernstein condition

Closest papers by meaning

• Coresets for Clustering Using Noisy Comparisons and Few Distance Queries (NeurIPS 2026 · similarity 0.92)
• Beyond Worst-Case Coreset Bounds for $k$-Clustering via Determinantal Sampling (NeurIPS 2026 · similarity 0.91)
• Near-optimal Coresets for Robust Clustering (ICLR 2023 · similarity 0.91)
• Universal Weak Coreset (AAAI 2024 · similarity 0.89)
• Coreset for Robust Geometric Median: Eliminating Size Dependency on Outliers (NeurIPS 2025 · similarity 0.87)
• Faster Approximation Algorithms for k-Center via Data Reduction (ICML 2025 · similarity 0.86)