Beyond Worst-Case Coreset Bounds for $k$-Clustering via Determinantal Sampling

• The method is motivated by the need to summarize massive datasets while preserving clustering costs and by clustering's broad practical use.Coresets are weighted representative subsets intended to approximate clustering costs across center choices.Source: §1 · pp. 1–2
• Existing coreset upper and lower bounds are essentially tight in the worst case, motivating smaller coresets under assumptions reflecting real-world data.An earlier cost-stable clusterability assumption did not surpass the Ω(kε^-2) lower bound.Source: §1 · p. 2
• The paper introduces determinantal sampling, a correlated framework using determinantal point processes to improve coreset guarantees over standard independent sampling.Once constructed, a kernel can be reused to generate multiple coresets.Source: §1 · pp. 2–3
• ˜O_{d,z}(k^(d/(d+1)) ε^(-2d/(d+1))) is an efficiently constructible coreset-size bound for (k, z)-clustering under mild distributional assumptions.For constant d, its dependence on 1/ε has exponent below 2, improving on the Ω(ε^-2) worst-case lower bound [CALSS22].Source: §1 · p. 2
• The general result extends to Polish spaces when a determinantal point process satisfies the required variance bounds.For clustering, the loss family has effective parameter dimension ℓ = dk.Source: §1 · p. 3
• Synthetic experiments support the improved ε-dependence, while real-world benchmarks show smaller coresets than state-of-the-art methods at comparable clustering error.The real-world tests do not explicitly enforce the theory's assumptions.Source: §1 · p. 3

• A (k, z)-clustering instance chooses at most k centers to minimize the sum of each data point's distance to its nearest center raised to z.The metric space is assumed to be separable and complete, or Polish.Source: §2 · p. 3
• An ε-coreset is a weighted subset of the data that approximates the clustering objective for potential center sets.The goal is to bound the size of the smallest such subset.Source: §2 · p. 4
• A determinantal point process is specified by a kernel whose determinants characterize the point process.The kernel is called Hermitian when K(x, y) = K(y, x).Source: §2 · p. 4
• For a finite dataset, a discrete DPP uses a matrix indexed by data points to characterize the probability of selecting subsets.The passage introduces this finite-set setting as a natural representation of data points.Source: §2 · p. 4
• The determinantal coreset estimator samples with a DPP and weights each selected point by the inverse of its kernel diagonal value.This choice makes the estimator unbiased for the target sum.Source: §2 · p. 4

3.2 Euclidean (k, z)-Clustering

• For Euclidean clustering, the loss class meets the general assumptions with effective parameter dimension ℓ = dk when the candidate centers lie in a bounded domain.The nearest-center distance is Lipschitz under the Hausdorff metric on center sets.Source: §3.1 · p. 5, §3.2 · p. 7
• The non-degeneracy condition holds with high probability under mild distributional assumptions, including when data are drawn independently from a subgaussian measure.The paper identifies this condition with a uniform positive lower bound on the normalized loss.Source: §3.1 · p. 5, §3.2 · p. 7

3.1 General determinantal sampler guarantees

• The general guarantee assumes a bounded, finite-dimensional parameter space, uniformly Lipschitz root losses, non-degenerate data losses, and a DPP sampler with balanced marginals and bounded sample size.The theorem gives a uniform coreset bound for a general parametric loss class before specializing to clustering.Source: §3.1 · p. 5

3.2 Euclidean (k, z)-Clustering

• Corollary 3.2 gives a high-probability ε-coreset guarantee for Euclidean clustering when the stated DPP variance, marginal, sample-size, and data conditions hold.The guarantee is over the randomness of the coreset construction, with failure probability at most δ for sample sizes in the corollary's stated range.Source: §3.2 · pp. 6–7
• ε = O(m^-1/2-1/(2d)) for OPE-based coresets, compared with ε = O(m^-1/2) for independent sampling.The rate uses the variance bound V = O(m^-1-1/d) for the discretized multivariate OPE kernel.Source: §3.2 · pp. 7–8

Experimental setup

• The evaluation compares seven weighted samplers using mean relative error over 150 coreset draws and 150 fixed random query-center sets per dataset–k pair.The test collection includes six synthetic datasets and three real-world datasets; k = 5 throughout.Source: §4 · pp. 8–9

Results: RQ1

• Across all six synthetic datasets, DPP-OPE and DPP-Vandermonde show steeper log–log relative-error decay than Uniform, Sensitivity, and HLW.On d = 2 benchmarks, the empirical slope is consistent with m^-(1/2+1/4); on Gaussian Blobs 3D, the gap narrows to the expected m^-(1/2+1/6) regime.Source: §4 · p. 9, Figure 1 · p. 10

Results: RQ2

• DPP-Haar matches or exceeds polynomial DPPs on spatially regular data, while grid-based Stratified sampling degrades on clustered or strongly non-uniform data.On real benchmarks, DPP-OPE and DPP-Vandermonde are strongest on UCI Adult (PCA-2), whereas DPP-Haar performs best on Twitter GPS.Source: §4 · pp. 9–10
• On real-world benchmarks, at moderate and large coreset sizes, at least one DPP sampler reaches a given error with fewer points than independent baselines.Figure 2 reports relative error against coreset size for k = 5.Source: §4 · p. 9, Figure 2 · p. 10

5 Conclusion and Future Work

• Determinantal sampling yields stronger coreset guarantees than standard independent sampling under natural assumptions on the input distribution.The paper frames this as a beyond-worst-case approach to substantially smaller coresets for (k, z)-clustering.Source: §5 · pp. 10–11
• Experiments on standard datasets support the efficacy of the determinantal-sampling method.Source: §5 · p. 11
• Open directions include relaxing the distributional assumptions and extending the approach to broader clustering settings or other coreset problems.The paper specifically raises general metric spaces, high-dimensional settings without dimensionality reduction, and regression or subspace approximation.Source: §5 · p. 11

A.1 A simple algebraic identity

• For ε ≤ 1, the algebraic argument bounds the sum by 2z after retaining a nonnegative i = 0 term.Source: §A.1 · p. 17

A.2 Concentration bounds of DPP

• The appendix restates a DPP concentration theorem from [BGSOT24] for a Hermitian kernel on a Polish space.The supplied theorem passage begins by specifying a bounded-function condition.Source: §A.2 · p. 17

B.1 Proof of Corollary 3.2

• The proof represents each center set by a loss function given by the distance to the set raised to z.Source: §B.1 · p. 18
• The loss is controlled through the Hausdorff distance between center sets, and a u-net of the bounded center region provides a covering bound.The proof uses this covering argument to verify the entropy condition with exponent kd.Source: §B.1 · p. 18
• The theorem's accuracy condition is met when ε = O(m^-1/d), using the stated bound on V.Source: §B.1 · p. 18
• The proof gives a sufficient condition for failure probability at most δ and absorbs constants and logarithmic factors into the ˜O notation.Source: §B.1 · pp. 18–19

B.2 Discussion on Assumption (B.1)

• For i.i.d. samples from a subgaussian measure with positive population k-point z-cost, Theorem B.2 establishes a uniform empirical lower bound with explicit constants.The constants depend on z, q, σ, and, for n0, also k and d.Source: §B.2 · p. 19, R. Since KR ⊆K+ · p. 22
• The proof truncates the domain to a ball around the mean and uses an enlarged center region; centers outside it give in-ball points z-cost greater than q.Source: §B.2 · p. 20

R. Since KR ⊆K+

• Projecting arbitrary centers onto the enlarged region does not increase distances for in-ball points, allowing the bound to extend to unrestricted centers.Source: R. Since KR ⊆K+ · pp. 21–22

C On Polish spaces.

• A Polish space has a topology induced by a complete separable metric, and every compact metrizable space is Polish.Thus, for compact metric data domains, the Polish-space assumption adds no extra restriction.Source: C On Polish spaces · p. 22
• The cube [0, 1]^d is compact metric, so it covers normalized images at fixed resolution and is Polish.The passage identifies a fixed-resolution normalized image space with [0, 1]^3.Source: C On Polish spaces · p. 22
• Finite label spaces with the discrete metric and probability simplices are compact metric, hence Polish.The simplex is a closed subset of the compact cube [0, 1]^k.Source: C On Polish spaces · p. 22

D The Average Squared Distance Objective

• The average squared-distance objective uses the average squared distance to a k-center set instead of minimum distance to the nearest center.The supplied passage introduces this as an alternative to standard k-means clustering.Source: D The Average Squared Distance Objective · p. 23
• The objective-function class has a linear span of dimension d + 2, independent of k.Its functions are affine combinations of squared norm, coordinate functions, and the constant function.Source: D The Average Squared Distance Objective · p. 23
• The cited theorem gives ε = O(m^-1/d) for expected coreset size m, and the resulting size bound is independent of k.The bound hides constants and lower-order logarithmic factors.Source: D The Average Squared Distance Objective · p. 23

E Supplementary Benchmark Plots

• The appendix reports supplementary diagnostics for all nine datasets, pairing average relative error with three metrics to compare variance, slope, and average-case versus worst-case behavior.It fixes 150 independent coreset draws and 150 random query center sets per dataset-k pair.Source: E Supplementary Benchmark Plots · pp. 23–24
• The 0.9-quantile supremum relative error summarizes worst-query performance exceeded in only 10% of independent coreset draws.The text describes it as more stable than the hard maximum across repetitions.Source: E Supplementary Benchmark Plots · p. 24

F License •

• The appendix lists Twitter GPS, 3D Road Network, and UCI Adult as CC BY 4.0 datasets, and BIRCH as generated code following its cited procedure.The Twitter GPS release excludes tweet text.Source: F License • · p. 28
• DPPy is used for MultivariateJacobiOPE under the MIT License, and scikit-learn for PCA and baseline clustering utilities under BSD 3-Clause.The remaining listed synthetic datasets are generated by the authors' code without third-party data or assets.Source: F License • · p. 28