Coresets for Clustering Under Stochastic Noise

AI summary

Overview

Research area: Theoretical machine learning and algorithmic data summarization — specifically coreset construction for (k,z)-clustering (a family that includes k-Median and k-Means) when the observed data is corrupted by stochastic noise drawn from a known distribution.

Technical level: Advanced. The paper is a theory-heavy contribution built on concentration inequalities (Bernstein condition), cost-stability assumptions, and coreset size/approximation tradeoff analysis, though the motivating problem is stated accessibly.

Scope in one sentence: The paper introduces a new surrogate error metric, Err_α, for evaluating clustering coresets built from noisy data, proves it yields smaller coresets and tighter guarantees than the classical Err metric, and validates the approach empirically on real-world datasets.

What This Paper Is About

Coresets are small weighted subsets of a dataset that approximately preserve clustering cost for all possible center sets, allowing large-scale clustering to be done on less data. Existing coreset constructions assume noise-free data, but real data is routinely corrupted by measurement error, transmission artifacts, or deliberately injected noise (for privacy or robustness). The paper asks whether classical coreset error measures still work when only a noisy version of the dataset is observable, and proposes a new error measure that accounts for how noise inflates clustering cost.

Key Contributions

1. First analysis of how coreset performance degrades under noise. The paper adapts the classical Err metric to a stochastic additive noise model and proves a bound on the coreset quality r_P(C(S)) (Theorem 3.1). The authors state this is the first result studying coreset degradation under noise.

2. A new surrogate metric, Err_α (the "approximation-ratio"). Defined in Equation (6) as the supremum over α-approximate center sets of the ratio r_P(C)/r_S(C) minus 1. It is defined independently of the noise distribution, yet its approximation guarantees scale with the noise level.

3. A cluster-wise sampling algorithm (Algorithm 1) that partitions the noisy dataset into k clusters and takes a uniform sample from each cluster, with guarantees under structural assumptions on the data (Theorem 3.3).

4. Provable size and quality improvements: under mild assumptions, enforcing an ε-bound under Err_α yields coresets smaller by a factor of up to poly(k) and tighter quality guarantees than classical metrics.

Main Findings

• Err_α corrects for noise-driven cost inflation. The classical Err metric compares absolute clustering cost deviation and is inflated by noise indiscriminately, producing overly pessimistic guarantees. Err_α compares relative quality on the clean dataset versus the coreset, which cancels out uniform inflation.

• Illustrative 1-Means counterexample (k = d = 1, z = 2, α = 1). With P split evenly between n/2 points at −1 and n/2 at 1 (OPT_P = n), and noise model I at θ = 1 with D_j = N(0,1), the noise inflates cost by roughly 2n for any center. This gives Err(P̂, P) ≈ 2n/3n = 2/3 and a bound r_P(P̂, 1) ≲ 25/9. In contrast, the empirical center satisfies C(P̂) ∈ [−√(1/n), √(1/n)] with high probability, so cost_z(P, C(P̂)) ≤ n + 1, giving Err_1(P̂, P) ≤ 1/n and r_P(P̂, 1) ≤ 1 + 1/n.

• Err-based guarantee (Theorem 3.1). If S ⊆ P̂ satisfies Err(S, P̂) ≤ ε and is produced by a size-A(ε) algorithm, then with probability at least 0.9, Err(S, P) ≤ ε + O(θnd/OPT_P + √(θnd/OPT_P)) and r_P(S, α) ≤ (1 + ε + O(θnd/OPT_P + √(θnd/OPT_P)))² · α. The additive term comes from the gap Err(P̂, P) and is described as overly conservative.

• Importance sampling size for the Err-based approach (Equation 7). Ã(ε) = Õ(min{k^1.5 ε^{−2}, k ε^{−4}}), matching state of the art in the noise-free setting.

• Err_α-based guarantee (Theorem 3.3). Under Assumption 3.2 and θ ∈ [0, OPT_P/(nd)], ε ∈ (0,1), α ∈ [1,2], a randomized algorithm constructs S ⊆ P̂ of size O(k log k/(ε − √(α−1)θnd/(α OPT_P)) + (α−1)k log k/(ε − √(α−1)θnd/(α OPT_P))²) with Err_α(S, P̂) ≤ ε holding with probability at least 0.99, and gives Err_α(S, P) ≤ ε + O(θkd/OPT_P + (√(α−1)/α)·(√(θkd OPT_P) + θnd)/OPT_P).

• Factor k/n improvement in the special case. At ε = 0 and α = 1, Err_α(S, P) = Err_1(P̂, P) = O(θkd/OPT_P), which is a factor k/n smaller than the Err-based rate O(θnd/OPT_P + √(θnd/OPT_P)).

• Coreset size comparison (ε = 1/poly(k), α = 1 + cε with 0 < c < 0.5). When √(α−1)θnd/(α OPT_P) < cε/2, the Err_α-based size is Õ(k/ε), improving over Õ(min{k^1.5/ε², k/ε⁴}) by a factor √k/ε. The r_P bound improves by at least poly(k). The stability parameter in Assumption 3.2 becomes γ = O(1 + log²(kd/ε)).

• General ε example. With α = 1 + ε and θ = OPT_P/(nd · poly(k)), the Err_α-based coreset size improves by a factor √k/ε and the error bound by at least poly(k).

• Structural assumptions needed (Assumption 3.2). (i) γ-cost-stability: OPT_P(k−1)/OPT_P(k) ≥ 1 + γ with γ = O(α)·(1 + θnd log²(kd/√(α−1))/OPT_P); (ii) limited outliers: r_i ≤ 8 r̄_i for all i ∈ [k], where r̄_i is the average radius (root mean squared distance to the optimal center) and r_i the maximum radius of cluster P_i. The paper notes the cost-stability assumption is also necessary to separate Err from Err_α: in a 3-means instance with γ = 1, Err(P̂, P) ≈ Err_1(P̂, P).

• Experiments support the theory beyond its assumptions. Results in Section 6 hold even for datasets that do not meet the theoretical assumptions (Table 2) and for non-i.i.d. noise across dimensions (Table 7). Table 1 shows real-world datasets satisfy r_i ≤ 8 r̄_i.

• Practitioner guidance. To achieve r_P(S, α) ≤ (1 + ε)·α, one can either run CN(ε′) with ε′ = ε − O(θnd/OPT_P + √(θnd/OPT_P)), or CN_α(ε_α) with ε_α = ε − O(θkd/OPT_P + (√(α−1)/α)·(√(θkd OPT_P) + θnd)/OPT_P). Both need an estimate of OPT_P, obtainable via an O(1)-approximate center set Ĉ for P̂ using cost(P̂, Ĉ) as a proxy; both algorithms already compute such a Ĉ as a first step, so no extra overhead.

Methodology in Plain English

Noise models. The authors assume each observed point is either untouched (with probability 1 − θ) or has independent noise added to every coordinate (with probability θ), where θ is a known noise parameter. In a second model, noise is added to every coordinate of every point with variance σ². Noise distributions must have mean zero and satisfy the Bernstein condition — a bounded-moment condition E[|X − μ|^i] ≤ (1/2) i! σ² b^{i−2} for i ≥ 3 that controls tail behavior and is satisfied by Gaussian, Laplace, sub-Gaussian, and sub-exponential distributions. A more general variant allows noise correlated across dimensions via a covariance matrix Σ ∈ R^{d×d}.

Why the old metric fails. The classical Err metric measures the worst-case absolute difference in clustering cost between the coreset and the dataset, normalized by the coreset cost. Under noise this gap gets dominated by the noise itself, producing loose bounds — illustrated by the 1-Means example where Err gives 25/9 but the truth is ≈ 1 + 1/n.

The new metric. Err_α instead asks: across all α-approximate center sets for the coreset, how much worse is the relative cost on the real dataset than on the coreset? Because both are ratios with respect to their own optima, uniform inflation cancels. This yields the clean bound r_P(S, α) ≤ (1 + Err_α(S, P)) · α, compared with r_P(S, α) ≤ (1 + Err(S, P))² · α for the classical metric.

Algorithms. The Err-based approach uses an existing importance-sampling coreset algorithm applied to the noisy data. The Err_α-based approach (Algorithm 1) first computes an approximate center set, partitions the noisy dataset into k clusters, and takes a uniform sample from each cluster. Structural assumptions (cost stability and bounded outliers) keep point-to-center assignments stable under noise so the two metrics can be cleanly separated.

Proof strategy for the Err bound. Show Err satisfies a composition bound Err(S, P) ≤ Err(S, P̂) + O(Err(P̂, P)) (Lemma 4.3), then bound Err(P̂, P) = O(θnd/OPT + √(θnd/OPT)) (Lemma 4.2) by controlling cost(P̂, C) − cost(P, C) ≤ Σ_{p∈P}(‖ξ_p‖² + ⟨ξ_p, p − c⟩) for all center sets C, using independence of the noise vectors and bounded higher moments.

Experiments. Validation on real-world datasets, including settings where the theoretical assumptions fail and where noise is non-i.i.d. across dimensions.

Why This Matters

Impact on research. The paper shifts the paradigm for noisy-data coresets from "detect and discard outliers" to "construct coresets that directly accommodate noise." Prior robust-coreset work assumes access to the clean dataset P or treats noise as identifiable outliers; this work assumes only the noisy P̂ is observable, with no oracle access to the clean distribution. It also introduces a metric (Err_α) that extends prior approximation-ratio-based coreset ideas to the noisy setting and may be of independent interest.

Real-world applications mentioned in the paper:

• Image segmentation, customer behavior analysis, and sensor data summarization (general clustering uses).
• Privacy-preserving data analysis: differential privacy's Gaussian mechanism (θ = 1 with Gaussian D_j) and deliberate Laplace/Gaussian noise injection in healthcare, location services, and financial analytics.
• Robustness in deep learning: injecting i.i.d. Gaussian noise to defend against adversarial attacks.
• Measurement error settings such as fluctuations in STEM exam scores across repeated exams, where mean and variance can be estimated from multiple exams.

Industry relevance. Coresets enable sublinear, streaming, distributed, and dynamic clustering because they can be merged and composed. Making coresets work when data is noisy (rather than requiring clean data or a separate filtering step) matters for any pipeline where sensor noise, transmission artifacts, or privacy mechanisms are built into data collection.

Future Directions

• Verifying assumptions on the observed data. Assumption 3.2 is stated on the unobservable P; the paper notes that P̂ often satisfies an approximate version and defers verification details to Section B.2, leaving practical detection as an open engineering question.
• Extending beyond the analyzed regime. The theoretical analysis is presented in detail for k-Means (z = 2) under noise model I, with extensions to other noise models and general (k,z)-clustering deferred to Section C.
• Removing the dependence on OPT_P. The coreset size bound depends on knowledge of OPT_P; the paper suggests proxy estimation via an O(1)-approximate center set but leaves the precise consequences to discussion in Section B.3.
• Behavior when cost stability is weak. The paper shows in Appendix B.1 that with weak stability (e.g., γ = 1 in a 3-means instance) the two metrics behave similarly, raising the question of what guarantees are achievable in that regime.

Target Audience

Theoretical machine learning and algorithms researchers working on coresets, clustering, and streaming/distributed optimization; privacy and robustness practitioners who need clustering on deliberately noised data; and applied scientists who must cluster noisy sensor, survey, or score data. Readers need comfort with approximation bounds, concentration inequalities, and (k,z)-clustering notation; the motivating narrative and empirical claims are accessible to a broader machine learning audience.

Authors’ abstract

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 $\mathrm{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.