Research map / Learning theory and algorithms / Prediction and decision losses
Small coresets via negative dependence: DPPs, linear statistics, and concentration
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.
Shows that determinantal point process (DPP) based coresets can provably beat independent sampling, via concentration inequalities for linear statistics of DPPs (including non-symmetric and vector-valued statistics).
Problem
Whether DPP-based randomized coresets can have fundamentally smaller cardinality than independently sampled coresets (which need O(eps^-2)), and how to obtain concentration inequalities for linear statistics of general DPPs.
Approach
Views the coreset loss as a linear statistic of a DPP and derives Laplace-transform-based concentration inequalities valid for general Hermitian, non-symmetric and vector-valued statistics; combined with a discretized multivariate OPE kernel with near-optimal variance decay, this yields coresets of size O(eps^{-2/(1+delta)}).
Key results
- Theory: DPP coresets with discretized multivariate OPE achieve relative error rate m^{-(1/2+1/(2d))-} versus m^{-1/2} for i.i.d. sampling.
- Experiments on uniform 2D data: i.i.d. baselines decay as m^{-1/2}, while stratified decays as m^{-1} and OPE/m-DPP-type samplers show faster decay (Vdm-DPP and Gaussian m-DPP reach about m^{-3/4}).
- On MNIST after PCA to dimension 4, the DPP samplers (OPE, Vdm-DPP) show faster decay than independent methods, but the advantage disappears as dimension increases beyond 4.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the OPE coreset sampler instead of independent sampling | Coreset sampling · Synthetic uniform, d=2 | Q_S(0.9) decay rate: m^{-1/2} to m^{-1-1/d} | Helped |
| Use stratified sampling instead of independent sampling | Coreset sampling · Synthetic uniform, d=2 | Q_S(0.9) decay rate: m^{-1/2} to m^{-1} | Helped |
| Use Gaussian m-DPP sampling instead of independent sampling | Coreset sampling · Synthetic uniform, d=2 | Q_S(0.9) decay rate: m^{-1/2} to m^{-3/4} | Helped |
| Use Vdm-DPP sampling instead of independent sampling | Coreset sampling · Synthetic uniform, d=2 | Q_S(0.9) decay rate: m^{-1/2} to m^{-3/4} | Helped |
| Increase the Gaussian kernel bandwidth | Gaussian m-DPP · Synthetic uniform, d=2 | Q_S(0.9) decay rate | Helped |
| Use determinantal samplers instead of independent sampling | Coreset sampling · Trimodal dataset | Q_S(0.9) decay rate | Helped |
| Use OPE or Vdm-DPP instead of independent sampling | Coreset sampling · MNIST PCA dimension 4 | Q_S(0.9) decay rate | Helped |
| Increase the data dimension beyond 4 | OPE and Vdm-DPP coreset sampling · MNIST | Q_S(0.9) decay rate | Hurt |
Surprising findings
- The advantage of the DPP samplers progressively disappears as the PCA dimension increases beyond 4 on MNIST.
Limitations
- Improvement relies on the i.i.d. data assumption and a good density estimate (KDE), which is costly.
- Improvement over independent sampling scales as 1/d and vanishes in high dimension.
- Concentration range for epsilon is restricted, and sampling DPPs still costs O(nm^2).
Experimental setup
Datasets: synthetic uniform data in [-1,1]^2 (n=1024) trimodal synthetic dataset MNIST (PCA to dimension 4)
Benchmarks: synthetic uniform dataset trimodal synthetic dataset MNIST PCA-4
Metrics: 0.9-quantile of worst-case relative error of k-means coreset
Baselines: uniform sampling sensitivity sampling Gaussian m-DPP Vdm-DPP stratified sampling
Builds on: DPP coresets (Tremblay et al.) Breuer-Duits concentration for DPP linear statistics sensitivity-based importance sampling coresets multivariate orthogonal polynomial ensembles
Closest papers by meaning
- State-of-art minibatches via novel DPP kernels: discretization, wavelets, and rough objectives (NeurIPS 2026 · similarity 0.92)
- Determinantal point processes based on orthogonal polynomials for sampling minibatches in SGD (NeurIPS 2021 · similarity 0.89)
- Sampling from a k-DPP without looking at all items (NeurIPS 2020 · similarity 0.89)
- Composable Coresets for Determinant Maximization: Greedy is Almost Optimal (NeurIPS 2023 · similarity 0.89)
- Learning Determinantal Point Processes with Moments and Cycles (ICML 2017 · similarity 0.88)
- Beyond Worst-Case Coreset Bounds for $k$-Clustering via Determinantal Sampling (NeurIPS 2026 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.