Satoru Iwata

Shinichi Hemmi, Taihei Oki, Shinsaku Sakaue et al.

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.

Satoru Iwata, Haruto Konno

Symmetric submodular function minimization admits purely combinatorial algorithms using special orderings of the ground set. Extending the minimum-cut algorithm of Nagamochi and Ibaraki (1992), Queyranne (1998) showed that the maximum adjacency ordering yields a pendent pair, which can be used to find a nontrivial minimizer. Nagamochi (2010) later introduced the minimum degree ordering, which yields a flat pair and leads to the identification of extreme sets. Despite the apparent similarity between these two algorithms, their connection remained unclear. In this paper, we introduce yet another ordering called minimum capacity ordering, and extend it to a one-parameter family of orderings, called $α$-orderings, that unifies these two previously known orderings. We prove a general inequality for $α$-orderings, and our framework recovers the known pendent-pair and flat-pair results as special cases, corresponding to $α= -1$ and $α= 1$, respectively. For each $α\in [-1, 1]$, the last two elements of an $α$-ordering form a contractible pair, i.e., a pair whose contraction preserves the existence of a nontrivial minimizer, which leads to a contraction algorithm that finds a nontrivial minimizer of a symmetric submodular function in $O(n^3)$ oracle calls, where $n$ is the cardinality of the ground set. In addition, we discuss the ranges of $α$ that ensure $α$-ordering to obtain these special pairs.