Reviews: Fast Greedy MAP Inference for Determinantal Point Process to Improve Recommendation Diversity

Summary: This paper introduces an exact algorithm for greedy mode finding for DPPs which is faster by a factor of M (ground set size) than previous work on greedy MAP algorithms for DPPs; the authors also show that this algorithm can be further sped up when diversity is required over only a sliding window within long recommendations. As an additional contribution, the authors show that modeling recommendation problems with DPPs and generating recommendations via their algorithm outperforms other standard (non-DPP) recommender algorithms along various metrics. As the authors mention, a key advantage of DPPs is their ability to tractably balance quality and diversity requirements for most operations, with mode estimation being one of the only operations that remains NP-hard. Indeed, sampling from a DPP has been used in previous literature, presumably as a more scalable alternative to greedy MAP finding (e.g. for network compression). Although the usefulness of DPPs for recommender systems is now an accepted fact, the analysis provided in section 5 and 6.2 remains interesting, in particular thanks to the discussion of the tunable scaling of diversity and quality preferences and how it can easily be incorporated into the new formulation of the greedy algorithm.