Computational Complexity of Normalizing Constants for the Product of Determinantal Point Processes
share
We consider the product of determinantal point processes (DPPs), a point process whose probability mass is proportional to the product of principal minors of multiple matrices, as a natural, promising generalization of DPPs. We study the computational complexity of computing its normalizing constant, which is among the most essential probabilistic inference tasks. Our complexity-theoretic results (almost) rule out the existence of efficient algorithms for this task unless the input matrices are forced to have favorable structures. In particular, we prove the following: (1) Computing ∑_S( A_S,S)^p exactly for every (fixed) positive even integer p is UP-hard and Mod_3P-hard, which gives a negative answer to an open question posed by Kulesza and Taskar. (2) ∑_S( A_S,S)( B_S,S)( C_S,S) is NP-hard to approximate within a factor of 2^O(|I|^1-ϵ) or 2^O(n^1/ϵ) for any ϵ>0, where |I| is the input size and n is the order of the input matrix. This result is stronger than the #P-hardness for the case of two matrices derived by Gillenwater. (3) There exists a k^O(k)n^O(1)-time algorithm for computing ∑_S( A_S,S)( B_S,S), where k is the maximum rank of A and B or the treewidth of the graph formed by nonzero entries of A and B. Such parameterized algorithms are said to be fixed-parameter tractable. These results can be extended to the fixed-size case. Further, we present two applications of fixed-parameter tractable algorithms given a matrix A of treewidth w: (4) We can compute a 2^n/2p-1-approximation to ∑_S( A_S,S)^p for any fractional number p>1 in w^O(wp)n^O(1) time. (5) We can find a 2^√(n)-approximation to unconstrained MAP inference in w^O(w√(n))n^O(1) time.
READ FULL TEXT