Technical Summary: Spectral DPPs via NEPv

1. Problem Statement

The paper addresses the computational intractability of Determinantal Point Process (DPP) Maximum A Posteriori (MAP) inference for large-scale data selection.

• Context: Selecting a diverse, high-quality subset of size $k$ from a massive ground set of $n$ candidates (where $n$ ranges from millions to billions) is critical for data curation, coreset selection, and active learning.
• Objective: The goal is to maximize $\log \det(L_S)$, where $L_S$ is the principal submatrix of a positive semidefinite similarity kernel $L$ indexed by the subset $S$.
• Challenge: This optimization problem is NP-hard. Standard discrete solvers (greedy, lazy-greedy) scale superlinearly ($O(kn^2)$ to $O(kn^3)$), making them infeasible for the "data-centric" regime where diversity is most needed. Existing continuous relaxations (e.g., simplex-based softmax extensions) often fail to enforce diversity constraints effectively or do not scale well with low-rank kernels common in machine learning.

2. Methodology

The authors propose NEPV-DPP, a framework that recasts the discrete DPP-MAP problem as a continuous optimization problem on the Stiefel manifold, leading to a novel Nonlinear Eigenvalue Problem with eigenvector dependency (NEPV).

2.1 Stiefel Manifold Relaxation

Instead of relaxing the binary membership vector $x \in \{0,1\}^n$ to fractional weights in a simplex (as in prior work), the paper relaxes the discrete coordinate selector matrix $V_S \in \{0,1\}^{n \times k}$ to an arbitrary orthonormal frame $V \in \mathbb{R}^{n \times k}$ such that $V^\top V = I_k$.

• Objective: Maximize $f(V) = \log \det(V^\top L V)$ subject to $V \in \text{St}(n, k)$.
• Geometric Advantage: The orthogonality constraint ($V^\top V = I_k$) acts as a "hard" diversity constraint. Unlike simplex relaxations where redundant items can receive fractional weights, the Stiefel relaxation forces selected directions to be mutually orthogonal, naturally penalizing redundancy before the objective is even evaluated.
• Low-Rank Compatibility: If $L = \Phi \Phi^\top$ (a low-rank kernel common in ML), the algorithm never forms the $n \times n$ matrix $L$. It only operates on the $d \times k$ matrix $\Phi^\top V$, enabling near-linear scaling in $n$.

2.2 The NEPV Formulation

By deriving the KKT conditions for the Stiefel relaxation, the authors show that the first-order optimality conditions form a new class of NEPV:
$$H(V) V = V \Lambda$$
where the operator $H(V)$ depends on $V$ through the inverse Gram matrix $(V^\top L V)^{-1}$:
$$H(V) = \frac{1}{2} \left( L P(V) + P(V)^\top L \right), \quad P(V) = V (V^\top L V)^{-1} V^\top L$$
This dependence on the inverse Gram matrix distinguishes it from standard NEPV applications (e.g., in Density Functional Theory) where the operator typically depends on $VV^\top$.

2.3 Solver: SCF Iteration with Guarantees

The paper proposes a Self-Consistent Field (SCF) iteration to solve this NEPV, specifically Algorithm 1 (NEPV-DPP):

1. Initialization: Start with the top-$k$ eigenvectors of $L$.
2. Iteration:
   • Compute the Gram matrix $G_t = V_t^\top L V_t$.
   • Solve for $A_t = L V_t G_t^{-1}$.
   • Construct the operator $H(V_t)$ implicitly.
   • Apply level-shifting ($\sigma$) and damping ($\alpha$) to stabilize convergence.
   • Update $V_{t+1}$ by taking the top-$k$ eigenvectors of the shifted operator and projecting back to the Stiefel manifold via polar retraction.
3. Rounding: Convert the continuous solution $V^\star$ back to a discrete subset $S$ using leverage-score sampling followed by a local greedy refinement.

2.4 Convergence Theory

The authors prove a local contraction theorem for the SCF iteration.

• Key Lemma: They establish a perturbation bound for the inverse Gram matrix $(V^\top L V)^{-1}$ on the Stiefel manifold, showing that small changes in the subspace (measured by the chordal distance $\|\sin \Theta\|_F$) result in bounded changes in the inverse Gram matrix.
• Result: Under a spectral gap assumption ($\lambda_k(L) > \lambda_{k+1}(L)$) and with sufficient level-shifting, the iteration converges linearly (geometrically) to a local critical point. The convergence rate depends on the eigengap and the level-shift parameter.

3. Key Contributions

1. Mathematical Novelty: The paper identifies that continuous DPP-MAP relaxation on the Stiefel manifold yields a previously unstudied NEPV form where the operator depends on the inverse of the projected kernel. This requires new perturbation analysis for inverse Gram matrices.
2. Algorithmic Scalability: The resulting NEPV-DPP algorithm requires only matrix-vector products with the kernel (or low-rank factors), scaling as $O((ndk + nk^2)t)$ for $t$ iterations. This makes it feasible for $n$ in the millions, unlike $O(kn^3)$ discrete methods.
3. Superior Diversity Constraints: The Stiefel relaxation enforces diversity via $L_2$-orthogonality, which is shown to be more robust against redundancy than simplex-based relaxations.
4. Empirical Validation (Synthetic): The paper provides synthetic benchmarks demonstrating that NEPV-DPP outperforms softmax extensions and D-optimal simplex relaxations in regimes with high redundancy (near-duplicates) and rank-deficient structures, achieving better coverage of distinct clusters and higher log-determinant values.

4. Results and Claims

• Synthetic Performance: In experiments with $n=1000$ to $n=450$ and varying cluster structures:
  • Redundancy Regime: NEPV-DPP successfully selected one representative from each of 5 clusters of near-duplicates (5/5 coverage), whereas the softmax extension selected duplicates (3/5 coverage) and the D-optimal simplex relaxation failed entirely (0/5 coverage).
  • Uniform Regime: NEPV-DPP achieved the largest minimum pairwise distance and the highest log-determinant value compared to baselines, avoiding the "corner-clumping" behavior of simplex methods.
• Scalability: The method integrates directly with low-rank kernels and feature maps, avoiding the formation of the full $n \times n$ kernel matrix.
• Modest Scope: The paper explicitly states that full real-data benchmarking, downstream-quality measurements, and production-scale wall-clock comparisons are left for a planned empirical study. The current work focuses on the relaxation, the solver, and the scaling analysis.

5. Significance

The paper claims to remove the algorithmic barrier preventing the use of principled DPP-based selection in large-scale data curation. By transforming an NP-hard discrete problem into a tractable continuous NEPV with a provably convergent solver, it enables the selection of diverse, high-quality subsets from massive candidate pools (millions to billions) where previous methods were computationally prohibitive. The work bridges the gap between the theoretical appeal of DPPs and the practical constraints of modern machine learning pipelines.