Some Inapproximability Results of MAP Inference and Exponentiated Determinantal Point Processes

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 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 $\text{NP}$-hard to approximate within a factor of $2^{\beta n}$, where $\beta =10^{-10^{13}}$. This result improves upon the best-known inapproximability factor of $(\frac{9}{8}-\epsilon )$, and rules out the existence of any polynomial-factor approximation algorithm assuming $\text{P}\ne \text{NP}$. We then show that log-determinant maximization is $\text{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 $\text{P}=\text{NP}$. As a corollary of the first result, we demonstrate that the normalizing constant for E-DPPs of any (fixed) constant exponent $p\ge {\beta }^{-1}=10^{10^{13}}$ is $\text{NP}$-hard to approximate within a factor of $2^{\beta pn}$, which is in contrast to the case of $p\le 1$ admitting a fully polynomial-time randomized approximation scheme.

28 pages. This is an extended version of our conference paper presented at AISTATS 2021. Has been accepted for Journal of Artificial Intelligence Research

References in corpus (6)

• Determinantal point processes for machine learning
• Learning Determinantal Point Processes
• Batch Active Learning Using Determinantal Point Processes
• Inapproximability of Combinatorial Optimization Problems
• Large-Margin Determinantal Point Processes
• Flexible Modeling of Diversity with Strongly Log-Concave Distributions

Cited by in corpus (2)

• On the Parameterized Intractability of Determinant Maximization
• Computational Complexity of Normalizing Constants for the Product of Determinantal Point Processes