Spectral DPPs via NEPv: A Scalable Continuous Relaxation of Determinantal MAP for Diversity-Aware Data Selection

• URL: http://arxiv.org/abs/2606.19411v1
• Date: Wed, 17 Jun 2026 15:40:25 GMT
• Title: Spectral DPPs via NEPv: A Scalable Continuous Relaxation of Determinantal MAP for Diversity-Aware Data Selection
• Abstract summary: Selecting a small, diverse, high-quality subset from a massive pool of candidates is a recurring primitive in modern machine learning.<n>This paper focuses on the relaxation, solver, and scaling analysis; full real-data benchmarking is left to a planned empirical study.
• Score: 6.555429729518591
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: Selecting a small, diverse, high-quality subset from a massive pool of candidates is a recurring primitive in modern machine learning -- data curation and coreset selection for training and fine-tuning large models, active-learning batch acquisition, prompt and exemplar selection for in-context learning, retrieval diversification, and experimental design. Determinantal Point Processes (\DPP s) give a principled, well-calibrated notion of diversity for this task, but their \emph{MAP} objective -- pick a size-$k$ subset $S$ maximizing $\logdet(L_S)$ -- is NP-hard, and the standard greedy and sampling algorithms scale superlinearly in the ground-set size $n$. This cost is prohibitive precisely in the data-centric regime where diversity matters most, where $n$ ranges over millions to billions of candidate examples, features, or embeddings. We recast \DPP-MAP as a continuous optimization problem over the Stiefel manifold, and show that its first-order optimality conditions form a \emph{Nonlinear Eigenvalue Problem with eigenvector dependency} (\NEPv) of a previously unstudied form. This \NEPv\ admits a self-consistent field (\SCF) iteration with a spectral-gap-based local contraction guarantee, giving a principled iterative solver where the diversity objective drives an eigenvector-dependent operator. The resulting algorithm, \OurMethod, requires only matrix-vector products with the kernel and runs in time $O\!\big((ndk+nk^2)\,t\big)$ for a small number of iterations $t$, scaling near-linearly in $n$ and integrating directly with low-rank and feature-map kernels common in ML. This paper focuses on the relaxation, solver, and scaling analysis; full real-data benchmarking is left to a planned empirical study.

Related papers

• Fair Multi-View Determinantal Coresets via Adaptive NEPv [6.555429729518591]
  In trademark curation, a subset should cover both the language used to describe marks and the visual space of their logos.<n>A single determinantal point process (DPP) kernel can hide failure in one view, and averaging kernels replaces the multi-view relaxation.<n>We formulate emphfair multi-view selection: maximize the weakest per-view log of a size-$k$ subset.
  arXiv  Detail & Related papers  (2026-08-18T02:32:32Z)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  A fundamental and long-standing challenge is their efficient approximation.<n>We develop a linear-space algorithm that requires $P(|hatboldsymbol-boldsymbol|_2geq)leq $ for all commonly used semi-values.<n>Our algorithm allows explicit minimization of the mean square error for each specific utility function.
  arXiv  Detail & Related papers  (2026-04-09T16:38:14Z)
• Turbocharging Gaussian Process Inference with Approximate Sketch-and-Project [12.874219128885064]
  We propose an approximate, distributed, accelerated sketch-and-project algorithm ($texttADASAP$) for solving linear systems.<n>We use the theory of determinantal point processes to show that the posterior mean induced by sketch-and-project rapidly converges to the true posterior mean.<n>$texttADASAP$ scales to a dataset with $> 3 cdot 108$ samples, a feat which has not been accomplished in the literature.
  arXiv  Detail & Related papers  (2025-05-19T20:46:26Z)
• GIST: Greedy Independent Set Thresholding for Max-Min Diversification with Submodular Utility [16.843606527688326]
  We study a novel subset selection problem called max-min diversification with monotone submodular utility ($textsfMDMS$)<n>Given a set of points in a metric space, the goal of $textsfMDMS$ is to maximize $f(S) = g(S) + lambda cdot textttdiv(S)$ subject to a cardinality constraint.<n>We show that $texttGIST$ outperforms state-of-the-art benchmarks for a single-shot data sampling task on ImageNet
  arXiv  Detail & Related papers  (2024-05-29T04:39:24Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  Single-Index Models are high-dimensional regression problems with planted structure. We show that computationally efficient algorithms, both within the Statistical Query (SQ) and the Low-Degree Polynomial (LDP) framework, necessarily require $Omega(dkstar/2)$ samples.
  arXiv  Detail & Related papers  (2024-03-08T18:50:19Z)
• Conditional mean embeddings and optimal feature selection via positive definite kernels [0.0]
  We consider operator theoretic approaches to Conditional Conditional embeddings (CME) Our results combine a spectral analysis-based optimization scheme with the use of kernels, processes, and constructive learning algorithms.
  arXiv  Detail & Related papers  (2023-05-14T08:29:15Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  We investigate the problem of best identification in discounted linear Markov+Delta Decision in the fixed confidence setting under a generative model. The lower bound as the solution of an intricate non- optimization program can be used as the starting point to devise such algorithms.
  arXiv  Detail & Related papers  (2022-08-11T04:12:50Z)
• Leverage Score Sampling for Tensor Product Matrices in Input Sparsity Time [54.65688986250061]
  We give an input sparsity time sampling algorithm for approximating the Gram matrix corresponding to the $q$-fold column-wise tensor product of $q$ matrices. Our sampling technique relies on a collection of $q$ partially correlated random projections which can be simultaneously applied to a dataset $X$ in total time.
  arXiv  Detail & Related papers  (2022-02-09T15:26:03Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  We present a meta-algorithm that adapts to the optimal complexity with $tildeO(L5/6 T2/3)$ regret. We also show that the meta-algorithm automatically admits significantly improved instance-dependent regret bounds.
  arXiv  Detail & Related papers  (2020-11-19T10:00:54Z)
• Sampling from a $k$-DPP without looking at all items [58.30573872035083]
  Given a kernel function and a subset size $k$, our goal is to sample $k$ out of $n$ items with probability proportional to the determinant of the kernel matrix induced by the subset (a.k.a. $k$-DPP) Existing $k$-DPP sampling algorithms require an expensive preprocessing step which involves multiple passes over all $n$ items, making it infeasible for large datasets. We develop an algorithm which adaptively builds a sufficiently large uniform sample of data that is then used to efficiently generate a smaller set of $k$ items.
  arXiv  Detail & Related papers  (2020-06-30T16:40:44Z)
• Scalable Learning and MAP Inference for Nonsymmetric Determinantal Point Processes [29.56615511158156]
  We develop a learning algorithm with space and time requirements linear in $M$ by introducing a new NDPP kernel decomposition. We also derive a linear-complexity NDPP maximum a posteriori (MAP) inference algorithm that applies not only to our new kernel but also to that of prior work.
  arXiv  Detail & Related papers  (2020-06-17T13:42:09Z)
• Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
  We give the first relative-error algorithms for column subset selection, subspace approximation, projective clustering, and volume on turnstile streams that use space sublinear in $n$. Our adaptive sampling procedure has a number of applications to various data summarization problems that either improve state-of-the-art or have only been previously studied in the more relaxed row-arrival model.
  arXiv  Detail & Related papers  (2020-04-23T05:00:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.