Coresets for $k$-Means: When Does Uniform Sampling Suffice?

1 Introduction

• Coresets summarize clustering inputs, while uniform sampling avoids preprocessing but risks missing small clusters and cannot be assumed to provide strong guarantees.The paper studies when this data-oblivious construction succeeds, including β-balancedness, which requires each optimal cluster to contain at least a β/k fraction of the points.Source: §1 · pp. 1–2

1.1 Our contribution

• Θ(ϵ^-2δ^-1) samples suffice for stable 1-mean coresets, versus Θ(ϵ^-1δ^-1) for weak coresets in Hilbert space.The paper gives matching lower bounds for both notions and extends the stable 1-median guarantee to ℓ_p for p∈[1,2], with sample size O(ϵ^-2δ^-1).Source: §1.1 · pp. 2–3
• For k≥2, β-balanced and ρ-separated instances admit stable coresets over all O(1)-approximate solutions; bounded kurtosis strengthens the guarantee to a strong coreset.For constant success probability, the stable result matches prior sample-size dependence on k and improves dependence on ϵ from ϵ^-3 to ϵ^-2.Source: §1.1 · pp. 3–4

1.2 Technical overview

• For 1-mean, the stable-coreset analysis controls relative cost differences through the deviation of the sample mean, which is shared across candidate centers.For general k, the analysis localizes approximate solutions around optimal centers and bounds boundary-gain error using symmetrization, vector contraction, and a lifted displacement representation.Source: §1.2 · pp. 4–5

1.3 Related work

• The paper situates its results among clustering under structural assumptions, uniform-sampling algorithms, and coreset constructions, noting that many strong-coreset methods require a full scan.Prior strong coresets based on uniform sampling use ring partitioning and still require a linear scan, while related work also studies approximation-preserving coresets.Source: §1.3 · pp. 5–6

• The paper studies k-means in a Hilbert space, with an optimal center set inducing a Voronoi partition into clusters.Source: §2 · p. 6
• The König–Huygens identity decomposes a cluster’s cost into a bias term and a variance term.Source: §2 · p. 6
• Stable coresets approximately preserve the cost gap between a candidate center set and the fixed optimum across the input and sample.Source: §2 · p. 7
• An RCDA guarantee plus a bound on sample cost at the fixed optimum implies a stable coreset.Source: §2 · p. 7

3.1 RCDA in Hilbert space

• The RCDA error factors into a center-dependent term and the sample-mean deviation, so one concentration bound controls it for all centers.Source: §3.1 · p. 8

3.2 Proof of Theorem 1.1

• O(ϵ^-2δ^-1) samples give a stable (δϵ, 8ϵ)-coreset for 1-mean with probability at least 1−δ.Source: §3.2 · p. 8

3.3 Proof of Theorem 1.3

• O(ϵ^-1δ^-1) samples give a weak (δϵ, 8ϵ)-coreset for 1-mean with probability at least 1−δ.Source: §3.3 · p. 8

Experimental setup

• The datasets do not fully satisfy the analysis requirements; measured separation is ρ̂2 ≥ 0.866 and measured kurtosis is below 5 at every tested k.The experiments average results over 20 independent runs and show one standard deviation.Source: §4 · pp. 8–9

Experiment 1: Comparison with importance sampling

• Stable-coreset error is roughly an order of magnitude higher than weak-coreset error at every tested coreset size.The experiment measures both errors for 1-median in ℓ1 on Yellow Taxi NYC.Source: §4 · p. 9, Figure 1 · p. 9
• Uniform sampling and sensitivity sampling show no appreciable accuracy difference for either weak- or stable-coreset error on Yellow Taxi NYC.For 500 points, construction took 0.03 milliseconds with uniform sampling and 2,160 milliseconds with sensitivity sampling.Source: §4 · p. 9, Figure 1 · p. 9

Experiment 2: Strong coresets for k-means

• Uniform sampling is comparable to sensitivity sampling and lightweight coresets for strong-coreset error, despite not satisfying the assumptions of Theorem 1.6.For a 1,000-point coreset at larger k, uniform sampling took 0.05 milliseconds, versus 20,000 and 127,000 milliseconds for sensitivity sampling and 90 and 900 milliseconds for lightweight coresets on Covertype and Census, respectively.Source: §4 · p. 10, Figure 2 · p. 10

Theorem 2.3

• An ϵ-RCDA and a sampled-optimum cost bound of factor α imply a stable (ϵ/α, 4ϵ)-coreset.The theorem assumes cost(C*, Q) ≤ α · cost(C*, P).Source: A Proof of Theorem 2.3 · p. 13

Proof

• The proof first bounds cost(C, Q) by (α + ϵ) cost(C, P) for every candidate center set C.This follows by combining the RCDA condition with the sampled-optimum cost assumption.Source: A Proof of Theorem 2.3 · p. 13
• Applying the pairwise comparison and rearranging yields a cost ratio at most 1 + 4ϵ when ϵ ≤ 1/5.The comparison uses the triangle inequality and the preceding sampled-cost bound.Source: A Proof of Theorem 2.3 · pp. 13–14

Theorem 1.3

• A uniform sample of size O(ϵ^-1δ^-1) is, with probability at least 1 − δ, a weak (δϵ, 8ϵ)-coreset for 1-mean.The theorem assumes ϵ ∈ (0, 1/10) and δ > 0.Source: B Proof of Theorem 1.3 · p. 14

Proof

• If a candidate is near-optimal on the sample, its distance from the sample mean is bounded by the sampled optimal cost.The proof uses this bound to relate the candidate to the population mean.Source: B Proof of Theorem 1.3 · p. 14
• The proof controls sample-mean deviation using the identity cost(µ, Q) = ∥∆∥^2 + VQ and Markov’s inequality.Together with the candidate-to-sample-mean bound, this yields the stated population-cost guarantee.Source: B Proof of Theorem 1.3 · p. 14

C Lower bounds for k = 1

• The stable lower-bound argument uses a two-point instance and controls the cost ratio between centers symmetric about the sample mean.In one case, the proof gives s ≥ 1/(3ϵ^2δ) as a necessary sample-size bound.Source: C Lower bounds for k = 1 · pp. 14–15

D.3 A good event and localization

• On a high-probability event, candidate solutions of interest are localized to a set V determined by the input, enabling subsequent bounds uniformly over V without conditioning.The event controls sampled cluster weights and sample-mean deviations; the localization lemma places candidates in V when its stated sampled-optimum and separation conditions hold.Source: D Upper bounds for k > 1 · p. 15, §D.3 · pp. 17–18

D Upper bounds for k > 1

• For k > 1, combining matched-cost and boundary-gain bounds with a one-sided sampled-optimum estimate yields an RCDA guarantee and then a stable coreset; bounded kurtosis strengthens the boundary-gain bound for strong coresets.The analysis separates these two guarantees by the conditions needed for the boundary-gain bound.Source: D Upper bounds for k > 1 · p. 15

D.1 Structural assumptions

• The structural assumptions include β-balancedness, requiring each optimal cluster to contain at least βn/k points, and ρ-separation, defined by OPTk ≤ ρ^2 OPTk−1.When ρ^2 ≤ 1/2, the minimum distance between optimal centers satisfies D^2 ≥ OPT/ρ^2.Source: §D.1 · pp. 15–16

D.2 Displacements and the master identity

• Candidates are parameterized by offsets from optimal centers, and the master identity separates matched-cost error from boundary-gain error.Boundary gain measures the improvement from serving a point by its nearest candidate center rather than the center displaced from its own optimal center.Source: §D.2 · pp. 16–17

D.4 Matched-cost error

• The weighted squared displacements satisfy sum_i w_i ||v_i||^2 <= 4ϵ cost(C(v), P).The proof derives the bound using (16) and (22).Source: §D.4 · p. 19
• The second contribution is at most (1 + ϵ)ϵ cost(C(v), P), using (E1) and (E2).This follows by bounding the ϵ^-1-weighted displacement term with the sampled bound (E2) and OPT <= cost(C(v), P).Source: §D.4 · p. 19
• Together, the two contributions in item (ii) are at most 5(1 + ϵ)ϵ cost(C(v), P).Source: §D.4 · p. 19

D.5 Boundary-gain error

• The proof handles the nonlinear boundary-gain term by separating its maximum over centers from its quadratic displacement terms.The maximum is handled by Maurer’s vector contraction inequality, while lifting makes the quadratic terms linear.Source: §D.5 · p. 19
• For each sampled far point, the boundary-gain function is 1-Lipschitz in the displacement vector under the ℓ∞, and hence ℓ2, norm.This enables the contraction step on the vector of candidate-center functions.Source: §D.5 · p. 19
• Appending one coordinate to each displacement makes the functions linear, expressing them as a single inner product in a direct-sum Hilbert space.The resulting inner-product representation allows Cauchy–Schwarz to finish the argument.Source: §D.5 · pp. 19–20

D.6 Stable coreset

• The sampled optimal-center cost is bounded above by (6/δ) OPT with failure probability at most δ/6.This is obtained by Markov’s inequality.Source: §D.6 · p. 20
• The uniform boundary-gain deviation is at most ϵ OPT with probability at least 1 − δ/2 under the stated separation condition.Source: §D.6 · p. 21
• With probability at least 1 − δ, Q is an 11ϵ-RCDA of P over S_γ(Q) ∪ S_γ(P).The proof combines the event controlling sampled optimal cost with the uniform boundary-gain bound and Lemma D.11.Source: §D.6 · p. 21, Proof of Theorem 1.5 · p. 21
• The matched-cost and boundary-gain components combine to bound |E(v)| by 11ϵ cost(C(v), P).The argument applies uniformly over v in V and uses OPT <= cost(C(v), P).Source: §D.6 · p. 21

D.7 Strong coreset

• The strong guarantee requires the additional assumption of bounded kurtosis for the input.Source: §D.7 · p. 21
• Under M-bounded kurtosis, a sample size at least 6Mk/(βϵ^2δ) controls failure of the sampled optimal-cost event to probability at most δ/6.The proof uses a variance bound and Chebyshev’s inequality.Source: §D.7 · pp. 21–22
• Under M-bounded kurtosis and the stated separation condition, the sample size is O(k^2M/(βϵ^2δ)) for the boundary-gain bound, which holds with probability at least 1 − δ/2.Source: §D.7 · p. 22
• The strong coreset guarantee bounds |cost(C, P) − cost(C, Q)| by 15ϵ cost(C, P) for the stated candidate class.The proof combines matched-cost and boundary-gain bounds, then uses OPT <= cost(C(v), P).Source: Proof of Theorem 1.6 · p. 22, §D.7 · p. 22

Kernel Clustering

• A uniform sample of size O(ϵ^-2δ^-1) is, with probability at least 1−δ, a stable (δϵ, 8ϵ)-coreset for kernel 1-mean.The guarantee holds for ϵ ∈ (0, 1/10) and δ > 0.Source: E Immediate Applications of Theorem 1.1 · p. 23

Clustering in ℓp for 0 < p ≤2

• For every p ∈ (0, 2], a uniform sample of size O(ϵ^-2δ^-1) is, with probability at least 1−δ, a stable (δϵ, 8ϵ)-coreset for the stated ℓp cost.The corollary applies to finite P ⊂ ℝ^d, ϵ ∈ (0, 1/10), and δ > 0; the section invokes an isometric embedding into Hilbert space for this range of p.Source: E Immediate Applications of Theorem 1.1 · p. 23

Approximation algorithms for k-median

• Improved stable coreset bounds translate directly into faster k-median approximation algorithms because the framework's running time depends exponentially on coreset size.The framework reduces k-median approximation to weak 1-median coreset guarantees through uniform sampling; a recent stable-coreset instantiation covers ℓ1 and its submetrics, including Kendall–tau and Jaccard.Source: E Immediate Applications of Theorem 1.1 · p. 23