Scalable Algorithm Boosts Diversity-Aware Data Selection for ML

This research addresses a critical challenge in modern machine learning: efficiently selecting a small, diverse, and high-quality subset from an enormous pool of candidates. This task is fundamental for applications like data curation, coreset selection for model training, active learning, prompt selection, and retrieval diversification. Determinantal Point Processes (DPPs) offer a principled framework for defining diversity, but their Maximum A Posteriori (MAP) objective, which involves maximizing the log determinant of a submatrix, is computationally intractable (NP-hard) for large datasets. Existing greedy and sampling algorithms also scale superlinearly, becoming prohibitive when dealing with millions or billions of candidates. The paper proposes a novel approach by reformulating the DPP-MAP problem as a continuous optimization task on the Stiefel manifold. This reformulation reveals that its first-order optimality conditions correspond to a previously unstudied type of Nonlinear Eigenvalue Problem with eigenvector dependency (NEPv). To solve this, the authors introduce a self-consistent field (SCF) iteration, which comes with a local contraction guarantee based on the spectral gap. The resulting algorithm, referred to as OurMethod, provides a principled iterative solver where the diversity objective directly influences an eigenvector-dependent operator. Crucially, OurMethod achieves near-linear scaling in the ground-set size, running in `O((ndk+nk^2)t)` time for a small number of iterations `t`, where `n` is the ground-set size, `k` is the subset size, and `d` is the feature dimension. This efficiency is achieved by requiring only matrix-vector products with the kernel, making it compatible with low-rank and feature-map kernels commonly used in machine learning. This work focuses on the theoretical relaxation, solver, and scaling analysis, with empirical validation planned for future studies.