Abstract
We study the computational complexity of two hard problems on determinantal point processes (DPPs). One is maximum a posteriori (MAP) inference, i.e., to find a principal submatrix having the maximum determinant. The other is probabilistic inference on exponentiated DPPs (E-DPPs), which can sharpen or weaken the diversity preference of DPPs with an exponent parameter $p$. We prove the following complexity-theoretic hardness results that explain the difficulty in approximating unconstrained MAP inference and the normalizing constant for E-DPPs. (1) Unconstrained MAP inference for an $n \times n$ matrix is NP-hard to approximate within a $2^{\beta n}$-factor, where $\beta = 10^{-10^{13}}$. This result improves upon a $(9/8-\epsilon)$-factor inapproximability given by Kulesza and Taskar (2012). (2) The normalizing constant for E-DPPs of any (fixed) constant exponent $p \geq \beta^{-1} = 10^{10^{13}}$ is NP-hard to approximate within a $2^{\beta pn}$-factor. This gives a(nother) negative answer to open questions posed by Kulesza and Taskar (2012); Ohsaka and Matsuoka (2020).
Introduction
Determinantal Point Processes (DPPs) have emerged as a powerful tool in machine learning for modeling diversity. By assigning probabilities to subsets based on the determinant of a kernel matrix, DPPs naturally favor sets of items that are dissimilar. They find applications in diverse fields such as document summarization, recommendation systems, and active learning. However, two fundamental computational tasks associated with DPPs have remained poorly understood in terms of their approximation limits: unconstrained Maximum A Posteriori (MAP) inference and the calculation of normalizing constants for Exponentiated DPPs (E-DPPs).
Closing the Gap in MAP Inference
MAP inference involves finding the subset $S$ that maximizes the determinant of the corresponding principal submatrix. While the size-constrained version (finding the best subset of size $k$) was known to be exponentially hard to approximate, the unconstrained version—where the subset can be of any size—lacked a strong lower bound. Previously, the best-known inapproximability result was a factor of $9/8$, while the best algorithms could only guarantee an $e^n$ approximation.
This work establishes that unconstrained MAP inference is NP-hard to approximate within a factor of $2^{\beta n}$ for a constant $\beta = 10^{-10^{13}}$. This result effectively closes the theoretical gap, showing that the problem is fundamentally as difficult as its size-constrained counterpart and that existing exponential-factor algorithms are near the theoretical limit of what is possible in polynomial time.
The Complexity Landscape of Exponentiated DPPs
Exponentiated DPPs (E-DPPs) introduce an exponent $p$ to the determinant, allowing for the tuning of diversity preferences. When $p \leq 1$, the model is well-behaved, admitting efficient randomized approximation schemes (FPRAS). However, the complexity for $p > 1$ has been an open question.
We demonstrate a stark phase transition in complexity. For a sufficiently large constant $p$ (specifically $p \geq 10^{10^{13}}$), approximating the normalizing constant (the partition function) becomes NP-hard within a $2^{\beta pn}$ factor. This result implies that for large exponents, not only is exact inference impossible, but even rough estimation and efficient sampling are computationally intractable.
Methodology
The proofs rely on sophisticated complexity-theoretic reductions. We utilize LabelCover problems and Raz’s parallel repetition theorem to construct a rigid hardness structure. This is then reduced to the geometric problem of Volume Maximization (VolMax). A key innovation in this work is the extension of these techniques from the size-constrained case to the unconstrained case, which requires a more delicate handling of the objective function across subsets of varying sizes.
Conclusion
By establishing exponential inapproximability for both unconstrained MAP inference and E-DPP normalizing constants, this research provides a definitive theoretical boundary for DPP-based models. While the constant $\beta$ identified is extremely small, its existence rules out the possibility of polynomial-factor approximation algorithms. Future work remains to bridge the "gray area" between $p=1$ and the massive threshold identified here, and to refine the constant $\beta$ to values more representative of practical problem scales.
Summary updated