On the (In)tractability of Computing Normalizing Constants for the Product of Determinantal Point Processes

摘要

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 input matrices are forced to have favorable structures. In particular, we prove the following: (1) Computing Σ_S det(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 & Taskar (2012). (2) Σ_S det(A_(S,S)) det(B_(S,S)) det(C_(S,S)) is NP-hard to approximate within a factor of 2~(O(|I|~(1-ε))) for any ε > 0, where |I| is the input size. This result is stronger than #P-hardness for the case of two matrices by Gillenwater (2014). (3) There exists a k~(O(k))|I|~(O(1))-time algorithm for computing Σ_S det(A_(S,S)) det(B_(S,S)), where k is "the maximum rank of A and B" or "the treewidth of the graph induced by nonzero entries of A and B." Such parameterized algorithms are said to be fixed-parameter tractable.