Lazy and Fast Greedy MAP Inference for Determinantal Point Process
The maximum a posteriori (MAP) inference for determinantal point processes
(DPPs) is crucial for selecting diverse items in many machine learning
applications. Although DPP MAP inference is NP-hard, the greedy algorithm often
finds high-quality solutions, and many researchers have studied its efficient
implementation. One classical and practical method is the lazy greedy
algorithm, which is applicable to general submodular function maximization,
while a recent fast greedy algorithm based on the Cholesky factorization is
more efficient for DPP MAP inference. This paper presents how to combine the
ideas of "lazy" and "fast", which have been considered incompatible in the
literature. Our lazy and fast greedy algorithm achieves almost the same time
complexity as the current best one and runs faster in practice. The idea of
"lazy + fast" is extendable to other greedy-type algorithms. We also give a
fast version of the double greedy algorithm for unconstrained DPP MAP
inference. Experiments validate the effectiveness of our acceleration ideas.