Research map / Learning theory and algorithms / Prediction and decision losses

State-of-art minibatches via novel DPP kernels: discretization, wavelets, and rough objectives

NeurIPS 2026 · Learning theory and algorithms › Prediction and decision losses · approach: Determinantal point process inference · 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 wavelet-based continuous DPPs with improved variance rates and a general pipeline converting continuous projection DPP kernels into low-rank discrete DPPs on datasets for minibatches and coresets.

Problem

DPP-based minibatches and coresets need continuous DPPs with variance reduction for linear statistics (few known examples, limited to smooth test functions), and a principled way to transfer such variance decay to a discrete DPP defined on a given dataset.

Approach

Defines new projection DPPs from multiresolution wavelet scaling functions (Haar, periodized Daubechies-2) whose linear-statistic variance decays as n^{1-2s/d} for Hölder and Sobolev test functions, and converts any such continuous projection kernel into a discrete L-ensemble on the dataset using eigenfunctions and a density estimate, yielding a low-rank discrete kernel with provable variance tran

Key results

• Wavelet DPP variance bound Var <= C|f|_s^2 n^{1-2s/d}, matching the n^{1-2/d} rate at s=1 and improving the OPE rate n^{1-1/d}.
• On MNIST k-means coresets (d=2 PCA), haar and db2 wavelet discrete DPP samplers improve over uniform and OPE samplers.
• On MNIST 4-vs-9 Pegasos with minibatch size 32, DPP samplers beat iid on all metrics and db2 outperforms OPE most clearly.

Surprising findings

• The Haar-wavelet DPP coincides with stratified sampling in the continuum, and on the trimodal dataset the haar sampler regresses to OPE-level performance while db2 keeps its advantage.

Limitations

• Wavelet DPP cardinality grows as 2^{dj}, exponential in dimension, so experiments use PCA to d=2.
• Coupling of cardinality and dimension is fixed; authors note need to decouple them.
• Code promised only upon publication.

Experimental setup

Datasets: synthetic trimodal Gaussian mixture (1024 points) MNIST

Benchmarks: MNIST

Metrics: Q(0.9) relative error of coreset linear statistic test classification error full-batch sub-gradient norm parameter error

Baselines: iid uniform sampling vdm-dpp OPE discrete DPP Pegasos with iid minibatches

Builds on: multivariate orthogonal polynomial ensembles Pegasos vdm-DPP

Closest papers by meaning

• Small coresets via negative dependence: DPPs, linear statistics, and concentration (NeurIPS 2024 · similarity 0.92)
• Determinantal point processes based on orthogonal polynomials for sampling minibatches in SGD (NeurIPS 2021 · similarity 0.92)
• Sampling from a k-DPP without looking at all items (NeurIPS 2020 · similarity 0.91)
• DppNet: Approximating Determinantal Point Processes with Deep Networks (NeurIPS 2019 · similarity 0.91)
• Scalable Sampling for Nonsymmetric Determinantal Point Processes (ICLR 2022 · similarity 0.90)
• Scalable Discrete Diffusion Samplers: Combinatorial Optimization and Statistical Physics (ICLR 2025 · similarity 0.86)