Some Inapproximability Results of MAP Inference and Exponentiated Determinantal Point Processes
This work addresses fundamental complexity barriers for machine learning practitioners using DPPs, providing rigorous theoretical limits on approximation algorithms, though it is incremental in improving known inapproximability bounds.
The paper tackles the computational hardness of approximating maximum a posteriori inference and normalizing constants for exponentiated determinantal point processes, proving strong inapproximability results such as NP-hardness within factors like 2^(βn) with β=10^(-10^13), ruling out polynomial-factor approximation algorithms assuming P ≠ NP.
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 present several complexity-theoretic hardness results that explain the difficulty in approximating MAP inference and the normalizing constant for E-DPPs. We first prove that unconstrained MAP inference for an $n \times n$ matrix is $\textsf{NP}$-hard to approximate within a factor of $2^{βn}$, where $β= 10^{-10^{13}} $. This result improves upon the best-known inapproximability factor of $(\frac{9}{8}-ε)$, and rules out the existence of any polynomial-factor approximation algorithm assuming $\textsf{P} \neq \textsf{NP}$. We then show that log-determinant maximization is $\textsf{NP}$-hard to approximate within a factor of $\frac{5}{4}$ for the unconstrained case and within a factor of $1+10^{-10^{13}}$ for the size-constrained monotone case. In particular, log-determinant maximization does not admit a polynomial-time approximation scheme unless $\textsf{P} = \textsf{NP}$. As a corollary of the first result, we demonstrate that the normalizing constant for E-DPPs of any (fixed) constant exponent $p \geq β^{-1} = 10^{10^{13}}$ is $\textsf{NP}$-hard to approximate within a factor of $2^{βpn}$, which is in contrast to the case of $p \leq 1$ admitting a fully polynomial-time randomized approximation scheme.