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

arXiv: 2606.19411v2 [cs.LG], 22 Jul 2026

The paper addresses the computational intractability of Determinantal Point Process (DPP) MAP inference for large-scale data selection tasks. The authors state:

"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."

The DPP-MAP objective is defined as selecting a size- k subset S maximizing (L S), where L is a positive semidefinite similarity kernel over n candidates. The authors emphasize:

"DPPs give a principled, well-calibrated notion of diversity for this task, but their MAP objective—pick a size- k subset S maximizing (L S) —is NP-hard, and the standard greedy and sampling algorithms scale superlinearly in the ground-set size n."

The key computational bottleneck is that:

This cost is prohibitive precisely in the data-centric regime where diversity matters most, where n ranges over millions to hundreds of millions of candidate examples, features, or embeddings.

The paper's central contribution is a continuous spectral relaxation of DPP-MAP over the Stiefel manifold, whose first-order optimality conditions take the form of a Nonlinear Eigenvalue Problem with eigenvector dependency (NEPv).

The authors replace the discrete coordinate selector matrix V S = [e i 1,, e i k] in 0,1 n times k with an arbitrary orthonormal frame:

V S in 0,1 n times k, V S V S = I k V in St(n,k), V V = I k.

The continuous relaxation problem is:

[

V in St(n,k) f(V):= (V L V)

]

Proposition 1 establishes that the continuous relaxation has a closed-form spectral solution:

"Let L 0 have eigenvalues lambda 1(L) at least at least lambda n(L) at least 0. If lambda k(L) > 0, then

[

V in St(n,k) (V L V) = sum i=1 k lambda i(L),

]

and the maximum is attained by any orthonormal basis of the top- k eigenspace of L."

Theorem 1 derives the NEPv form. Define:

[

P(V):= V (V L V)-1 V L, H(V):= 1 over 2 (L P(V) + P(V) L)

]

Then:

"Every critical point of (P) satisfies the NEPv

[

H(V) V = V

]

with V V = I k and = V H(V)V in R k times k symmetric."

The authors note the gauge invariance property: H(VQ) = H(V) for any Q in O(k).

The paper proves that (P) is a genuine relaxation of (5):

• (a) Feasible embedding: Every discrete subset S can be encoded by a coordinate selector V S in St(n,k).

• (b) Same objective value: V S L V S = L S, so f(V S Q) = (L S) for all Q in O(k).

• (c) Relaxation bound: V in St(n,k) (V L V) at least S=k (L S).

The paper articulates three concrete advantages:

(A1) Orthogonality as a hard diversity constraint:

"In a simplex relaxation we represent a soft selection by weights x in [0,1] n and impose only the budget constraint sum i x i = k. This controls how much mass is selected, but not how similar the selected items are... Thus redundant items remain feasible; diversity enters only indirectly through the curvature of the log det objective."

(A2) V L V stays in the same currency as L S:

The discrete DPP-MAP objective is (L S), while the Stiefel relaxation evaluates (V L V). When V = V S is a coordinate selector, these two quantities are identical (Lemma 1).

(A3) Low-rank kernels L = plug in naturally:

The Stiefel relaxation only ever evaluates V L V = (V)(V), so the n times n matrix L is never formed; only the small d times k matrix V is needed.

This is the key technical lemma enabling the convergence analysis:

"Let L 0, and let V, in St(n,k) be aligned so that V 0. If the chordal distance eta:= (V,) F = d ch(V,) [

(V L V)-1 - (L)-1 2 at most 7 over 2L 2 over lambda(V L V) lambda(L) eta."

]

The paper proves local convergence of the idealized subspace map T sigma(V):= TopEigvecs k(H sigma(V)) where H sigma(V) = H(V) + sigma V V:

"If the chosen shift sigma at least 0 satisfies C DK(C H + sigma) < lambda k + sigma, then there is a neighborhood N Gr(n,k) of V such that the idealized iteration V t+1 = T sigma(V t) satisfies

[

d ch(V t+1, V) at most rho(sigma) d ch(V t, V), rho(sigma):= C DK C H + sigma over lambda k + sigma]

The proof structure is: (1) identify the fixed point and its eigengap gamma = lambda k(L) + sigma; (2) reduce convergence to one Davis–Kahan estimate; (3) control the inverse Gram matrix via Lemma 2; (4) prove the Lipschitz bound for H sigma; (5) combine Davis–Kahan with the Lipschitz bound; (6) choose an admissible shift.

The authors note important caveats:

"The theorem is a local statement for the idealized subspace map T sigma. It does not prove convergence of the damped/polar update in Algorithm 1. It also does not prove global convergence... The theorem only says that the top- k eigenspace is attracting from a sufficiently small neighborhood when (19) holds."

Regarding the level shift:

"The shift is best interpreted as a global stabilization device: away from V, it helps keep the currently selected subspace separated from competing eigenspaces. That global effect is useful numerically but is not quantified by this local theorem."

Algorithm 1 presents the SCF iteration:

Require: Symmetric positive definite kernel L in R n times n (or regularized low-rank kernel L = + epsilon I, epsilon > 0); target size k; tolerance epsilon; damping alpha in (0,1]; shift sigma at least 0.

1. Initialize V 0 from top- k eigenvectors of L (or random orthonormal).

2. for t = 0, 1, 2, do

3. Compute Gram G t from V t L V t in R k times k.

4. Solve A t from L V t G t-1 in R n times k.

5. Apply H(V t) X = A t (V t L X) implicitly.

6. H sigma(V t)(times) from H(V t)(times) + sigma V t(V t times).

7. t+1 from top- k eigenvectors of H sigma(V t) via LOBPCG/block Lanczos.

8. V t+1 from Polar (alpha t+1 + (1-alpha)V t).

9. if (V t+1, V t) F 10. end for

11. return V from V t+1.

Three variants are proposed: (i) Plain SCF (alpha = 1, sigma = 0); (ii) Damped SCF (alpha 0).

After obtaining the dense subspace V, the paper recovers a discrete subset via:

1. Compute leverage scores i = e i V 2 squared; note sum i i = k.

2. Sample of size 1.5k without replacement proportional to i.

3. Run at most 5 greedy swaps on to maximize (L), reducing to S = k.

The authors explicitly state:

This is a practical rounding rule motivated by leverage-score and volume-sampling ideas. We do not claim a theorem for this particular sample-then-swap procedure in the present version.

Define the spectral certificate U k:= sum i=1 k lambda i(L). The paper proves:

(i) Optimum floor: OPT k at least U k - k.

(ii) Greedy floor: If gamma i is the i th multiplicative gain of greedy, then gamma i at least lambda i(L)/(n-i+1), giving:

[

G k at least U k - n! over(n-k)! = U k - k - k!.

]

"Greedy, the discrete optimum, and the spectral certificate satisfy

[

U k - D k at most G k at most OPT k at most U k, U k - k at most OPT k at most U k,

]

where D k:= n! over(n-k)! = sum i=1 k (n - i + 1)."

The per-item agreement result states:

"For any such subset,

[

1 over k (L) - G k at most D k over k = 1 over k sum i=1 k (n - i + 1),

]

and the right-hand side is strictly decreasing in k."

For the exact optimum:

0 at most U k - OPT k over k at most 1 over k k at most 1 + n over k, where the middle bound vanishes at k = n and the outer bound 1 + n over k is strictly decreasing in k.

Exhaustive search returns OPT k exactly at cost (k C) where C = O(k 3). The bounds on the number of subsets are:

[

(n-k+1 over k) k at most k at most (k) (n over k) k

]

Corollary 1 states that any subset reaching the greedy floor trails the exact optimum by at most D k in total, or D k/k per item. The certificate also bounds the gap to the exhaustive optimum:

0 at most U k - OPT k at most k, with per-item gap 1 over k k at most 1 + n over k 0.

The paper claims the following complexity:

"The resulting pipeline, NEPv-DPP, requires only matrix–vector products with the kernel and runs in time O(ndk + nk 2)t 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."

Key scalability tricks include:

• Low-rank/Nyström: L = + epsilon I with in R n times d, d n, epsilon > 0. All operations cost O(ndk + nk 2) per iteration; the n times n matrix L is never formed.

• Kernel with quality scores: L ij = q i q j k(x i, x j) using random Fourier features or Nyström to obtain.

• Distributed: Shard V row-wise across GPUs; the only collective is the k times k Gram product V L V.

The paper reports four synthetic experiments comparing NEPv-DPP against two baselines: the softmax extension (x) = (I + diag(x)(L - I)) of Gillenwater et al. (2012), and the D-optimal simplex design relaxation (diag(x) + lambda I).

On 5 well-separated anchors plus diffuse noise, all three methods recover the anchors exactly – a sanity check.

"When each anchor is replaced by a cluster of 21 near-duplicates, NEPv-DPP still attains 5/5 cluster coverage and (L S) about 0, while the softmax extension drops to 3/5 (it wastes two picks on duplicates) and the D-optimal simplex relaxation collapses to 0/5 (it prefers the noise blob, whose feature embeddings span more directions than the duplicated clusters)."

"On n = 1000 points drawn uniformly from [-5,5] squared with k = 15 and no cluster structure... NEPv-DPP achieves the largest minimum pairwise distance (2.28 vs. 0.09 for the softmax extension and 1.27 for D-optimal simplex) and the largest (L S) = -15.6 (vs. -78.8 and-28.1)."

"When we scale to 15 cluster centers placed on a regular 3×5 lattice in the plane (equal spacing 4 in both axes) with 30 samples per center (n = 450, k = 15), NEPv-DPP and the softmax extension both cover all 15/15 clusters and achieve (L S) about 0; the D-optimal simplex relaxation covers only 9/15, attaining (L S) = -0.29 and allocating up to three of its 15 picks to the same cluster while leaving six clusters empty."

The paper explicitly states its scope:

This paper focuses on the relaxation, solver, and scaling analysis; full real-data benchmarking is left to a planned empirical study.

"The real-data evaluation is deliberately out of scope for this version. The natural next tests are wall-clock scaling, rounded (L S) quality on the original discrete objective, and downstream utility on data-selection benchmarks."

The authors also acknowledge:

"We do not claim a theorem for this particular sample-then-swap procedure in the present version: proving conditions under which it satisfies an additive or multiplicative gap relative to the spectral upper bound (V L V) is left as future work."

The paper situates itself relative to:

• DPP-MAP inference: NP-hard (Çivril & Magdon-Ismail, 2009); greedy and lazy-greedy algorithms widely used but too costly at modern scale.

• Continuous relaxations: The softmax extension of Gillenwater et al. (2012) and D-optimal design relaxations use simplex geometry; the Stiefel relaxation uses L squared-orthogonality instead.

• NEPv methods: Previously studied for Kohn–Sham DFT, trace-ratio problems, robust Rayleigh quotient minimization, and orthogonal CCA (Cai et al., 2018; Bai et al., 2022), but never for a log-det objective on the Stiefel manifold.

The paper claims three pillars of contribution:

"1. Spectral fixed-point viewpoint. No prior work, to our knowledge, frames the Stiefel relaxation of DPP-MAP as an NEPv-style fixed-point problem... the dependence of H(V) on (V L V)-1 (rather than on V V) requires a new perturbation lemma on inverse Gram matrices restricted to small geodesic balls on St(n,k)."

"2. A high-impact ML application. Data curation is a dominant cost lever in modern large-scale training... DPPs are the theoretically right tool, but until now their MAP infeasibility forced practitioners to coarser surrogates (clustering, k-center, scoring filters)."

"3. A clear path to empirical validation. The real-data evaluation is deliberately out of scope for this version."

Based on the paper, here are specific improvements to AI systems and their resulting capabilities:

Improvement: Replace current clustering/k-center/random sampling methods for data curation with the NEPv-DPP pipeline (Stiefel relaxation + SCF solver + leverage-score rounding).

Capability: Select a diverse, high-quality subset of size k from pools of 106–108 candidates in near-linear time O(ndk + nk2)t, where d is embedding dimension and t is iteration count (typically < 30). This directly enables:

• Training data curation: Pick coresets that maximize coverage of semantic space while avoiding near-duplicates, improving model generalization at fixed compute budget.

• Active learning batch acquisition: Choose a batch that spans diverse uncertainty regions rather than redundant high-uncertainty points.

• In-context learning exemplar selection: Select few-shot examples that are mutually dissimilar yet high-quality, improving prompt performance.

Improvement: Use the closed-form upper bound Uk = Σi=1k log λi(L) as an a-posteriori optimality certificate.

Capability: After any selection method (greedy, clustering, random), compute the gap Uk − log det(L S) to know exactly how far the chosen subset is from the continuous optimum—without solving NP-hard DPP-MAP. This enables:

• Quality control: Reject selections whose gap exceeds a threshold, triggering re-selection or increased budget.

• Method comparison: Objectively benchmark different selection algorithms on the same kernel by their gap to the certificate.

• Early stopping: In iterative selection, stop when the marginal gain in log-det falls below a fraction of the remaining certificate slack.

Improvement: The Stiefel relaxation enforces orthogonality as a hard constraint, unlike simplex relaxations that only softly penalize redundancy.

Capability: When the ground set contains many near-duplicates (e.g., web-scraped text with template variants, image datasets with near-identical crops), the system:

• Automatically avoids selecting multiple items from the same cluster (as shown in synthetic tests: 5/5 cluster coverage vs. 3/5 for softmax and 0/5 for D-optimal design).

• Maintains high log-det values even when clusters are tight (std 0.08), where simplex methods collapse to log-det ≈ −∞.

• Produces selections with minimum pairwise distance 2.28 vs. 0.09 (softmax) and 1.27 (D-optimal) on uniform data—directly improving diversity metrics.

Improvement: The algorithm never forms the n×n kernel matrix; it only requires matrix-vector products with L = ΦΦT + εI, where Φ ∈ Rnˣd is the embedding matrix.

Capability: Directly work with:

• Precomputed embeddings from any encoder (BERT, CLIP, etc.) without materializing similarity matrices.

• Nyström or random Fourier feature approximations for non-linear kernels.

• Quality-weighted variants L = diag(q)ΦΦTdiag(q) by rescaling rows.

This makes the method deployable in production pipelines where n = 108 and d = 1024–4096, with memory footprint O(nd + nk) instead of O(n2).

Improvement: Shard the embedding matrix row-wise across GPUs; the only collective operation is the k×k Gram product VTLV.

Capability: Scale to hundreds of millions of candidates by distributing the SCF iteration across multiple devices, with communication cost O(k2) per iteration—negligible compared to the O(ndk) local computation. This enables:

• Real-time data selection during training loops.

• Multi-dataset curation across federated or sharded storage.

Improvement: The local contraction theorem (Theorem 2) provides a convergence rate ρ(σ) = C DK(C H + σ)/(λk + σ) for the SCF iteration.

Capability: For a given kernel and shift σ, compute the guaranteed per-iteration error reduction factor. This allows:

• Predictable runtime: Estimate the number of iterations needed to reach tolerance ε as log(ε/d0)/log(ρ).

• Shift tuning: Choose σ to balance convergence speed vs. stability (larger σ stabilizes but may slow local convergence).

• Warm-starting: Initialize with top-k eigenvectors of L (cheap via Lanczos) to start within the contraction basin.

Improvement: The rounding step computes per-item leverage scores li = ‖eiTV⋆‖22, which sum to k.

Capability: Beyond selecting the subset, the system outputs a diversity score for every candidate, enabling:

• Explainability: Identify which items are most representative of the selected subspace.

• Budget flexibility: If k changes mid-pipeline, re-round using the same scores without re-running the solver.

• Hybrid selection: Combine leverage-score sampling with domain-specific filters (e.g., difficulty scores) by reweighting li before sampling.

Improvement: Corollary 1 provides computable bounds on the gap between any rounded subset and the exact DPP-MAP optimum: 0 ≤ OPTk − log det(L Ŝ) ≤ Dk, where Dk = log(n!/(n−k)!).

Capability: For validation sets (n ≤ 104, k ≤ 100), the system can:

• Certify that a selection is within Dk/k per item of the true optimum, even though exact enumeration is infeasible.

• Compare against exhaustive search on small problems to empirically validate the rounding procedure.

• Provide instance-specific guarantees that are tighter than worst-case (1−1/e) bounds from submodularity.

Improvement: The theory applies to L ε = L + εI with ε > 0, and the algorithm uses this regularized kernel internally.

Capability: Work with:

• Kernels from embeddings with d < n (always rank-deficient).

• Kernels with exact duplicates (zero eigenvalues).

• Kernels with numerical rank deficiency from floating-point rounding.

The regularization ε acts as a ridge that stabilizes the inverse Gram matrix * (VTLV)−1* without changing the selection qualitatively for small ε.

Improvement: The same NEPv-DPP pipeline handles any task where the objective is log-det of a principal submatrix.

Capability: Deploy one system for:

• Maximum-volume subsampling (e.g., selecting diverse rows for matrix sketching).

• D-optimal experimental design (selecting experiments that maximize information gain).

• Quasi-optimal trial subspace selection in meshless PDE solvers (as in Ling 2016).

• Diverse ensemble selection for model ensembling (pick models whose predictions are mutually uncorrelated).

Concrete deployment example: An AI system for large-scale text deduplication and coreset selection could: (1) embed all 50M documents with a sentence-transformer, (2) form Φ ∈ R50Mˣ384, (3) run NEPv-DPP with k = 10,000 in 30 SCF iterations (≈ 15 minutes on 8 GPUs), (4) output a diverse subset with a certificate showing it is within Dk/k of the optimal log-det, and (5) use the leverage scores to explain which documents were selected and why.

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 (s) give a principled, well-calibrated notion of diversity for this task, but their MAP objective -- pick a size- k subset S maximizing (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-MAP as a continuous optimization problem over the Stiefel manifold, and show that its first-order optimality conditions form a Nonlinear Eigenvalue Problem with eigenvector dependency of a previously unstudied form. This admits a self-consistent field 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,, requires only matrix-vector products with the kernel and runs in time O! ((ndk+nk 2),t) 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.