Research map / Learning theory and algorithms / Clustering

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

NeurIPS 2026 · Learning theory and algorithms › Clustering · approach: Coresets and dynamic clustering · 0 citations (OpenAlex)

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.

Proposes determinantal sampling, a DPP-based correlated sampler for coresets, proving an epsilon-coreset for (k,z)-clustering in R^d with size exponent 2d/(d+1) under subgaussian data assumptions, and showing gains on synthetic and real benchmarks.

Problem

Worst-case coreset lower bounds of Omega(k eps^-2) (k-means) and Omega(k eps^{-z-2}) make small coresets impossible in general for (k,z)-clustering; the paper asks whether natural distributional assumptions on the data can beat these bounds.

Approach

Use determinantal point process samplers (OPE / Vandermonde kernels on the data) as correlated samplers with variance reduction, so that coreset error decays faster than i.i.d. sampling; under subgaussian data this yields coreset size k^{d/(d+1)} eps^{-2d/(d+1)} in fixed dimension.

Key results

• Theory: coreset size scales as k^{d/(d+1)} eps^{-2d/(d+1)} under subgaussian data, beating the eps^-2 worst-case barrier for fixed d.
• Empirically, DPP-OPE and DPP-Vandermonde show steeper log-log error decay than i.i.d. baselines (Uniform, Sensitivity, HLW) on the d=2 synthetic benchmarks.
• On real data, at least one DPP sampler reaches a given error with fewer points than i.i.d. baselines for moderate and large m; gains are smaller on 3D Road Network.

Surprising findings

• The gains on 3D Gaussian blobs narrow to the m^{-(1/2+1/6)} regime, indicating the advantage degrades with dimension.
• Stratified sampling degrades on clustered or non-uniform datasets, despite improving over uniform on well-spread data.

Limitations

• Theoretical guarantee relies on subgaussian data and a DPP kernel with variance bound V=O(m^{-1-1/d}) that is only proven for the OPE kernel on hypercube-supported data.
• Dimension-dependent exponent; the advantage vanishes or narrows as d grows and the OPE construction is restricted to d<=6.
• Experiments use only k=5 and evaluate average-case error over a fixed random query family rather than worst-case clustering cost.

Experimental setup

Datasets: Uniform 2D (synthetic) Trimodal 2D (synthetic) Gaussian Blobs 2D Gaussian Blobs 3D Anisotropic Gaussians 2D BIRCH benchmark 3D Road Network UCI Adult (PCA-2) Twitter GPS

Benchmarks: Uniform 2D Trimodal 2D Gaussian Blobs 2D Gaussian Blobs 3D Anisotropic Gaussians 2D BIRCH 3D Road Network UCI Adult (PCA-2) Twitter GPS

Metrics: mean relative error of coreset cost estimates supremum variance 0.9-quantile supremum relative error log-log decay slope

Baselines: Uniform sampling Sensitivity sampling HLW Stratified sampling DPP-Haar

Builds on: sensitivity sampling determinantal point processes DPPy Hermitian DPP concentration (Bardenet and Hardy style)

Closest papers by meaning

• Near-optimal Coresets for Robust Clustering (ICLR 2023 · similarity 0.92)
• Coresets for Clustering Under Stochastic Noise (NeurIPS 2025 · similarity 0.91)
• Universal Weak Coreset (AAAI 2024 · similarity 0.90)
• Near-Optimal $k$-Clustering in the Sliding Window Model (NeurIPS 2023 · similarity 0.90)
• Small coresets via negative dependence: DPPs, linear statistics, and concentration (NeurIPS 2024 · similarity 0.87)
• Coreset for Robust Geometric Median: Eliminating Size Dependency on Outliers (NeurIPS 2025 · similarity 0.87)