# Lazy and Fast Greedy MAP Inference for Determinantal Point Process

arXiv: https://arxiv.org/abs/2206.05947 · HTML: https://mlsanity.com/paper/2206.05947/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 54 references that are in the map.
- First posted on arXiv 13 Jun 2022.

## Builds on (most cited first, 19 of 19)

- [Lazier Than Lazy Greedy](https://mlsanity.com/paper/1409.7938/) (2014)
- [Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh Distributions and Determinantal Point Processes](https://mlsanity.com/paper/1602.05242/) (2016)
- [Exact sampling of determinantal point processes with sublinear time preprocessing](https://mlsanity.com/paper/1905.13476/) (2019)
- [Sampling from a k-DPP without looking at all items](https://mlsanity.com/paper/2006.16947/) (2020)
- [Faster Greedy MAP Inference for Determinantal Point Processes](https://mlsanity.com/paper/1703.03389/) (2017)
- [Non-monotone Submodular Maximization with Nearly Optimal Adaptivity and Query Complexity](https://mlsanity.com/paper/1808.06932/) (2018)
- [An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation](https://mlsanity.com/paper/1804.06355/) (2018)
- [The FAST Algorithm for Submodular Maximization](https://mlsanity.com/paper/1907.06173/) (2019)
- [Scalable Learning and MAP Inference for Nonsymmetric Determinantal Point Processes](https://mlsanity.com/paper/2006.09862/) (2020)
- [Non-monotone Submodular Maximization in Exponentially Fewer Iterations](https://mlsanity.com/paper/1807.11462/) (2018)
- [Parallel Algorithm for Non-Monotone DR-Submodular Maximization](https://mlsanity.com/paper/1905.13272/) (2019)
- [Composable Core-sets for Determinant Maximization: A Simple Near-Optimal Algorithm](https://mlsanity.com/paper/1907.03197/) (2019)
- [Non-Adaptive Adaptive Sampling on Turnstile Streams](https://mlsanity.com/paper/2004.10969/) (2020)
- [Fast Mixing Markov Chains for Strongly Rayleigh Measures, DPPs, and Constrained Sampling](https://mlsanity.com/paper/1608.01008/) (2016)
- [Exact Sampling of Determinantal Point Processes without Eigendecomposition](https://mlsanity.com/paper/1802.08429/) (2018)
- [Isotropy and Log-Concave Polynomials: Accelerated Sampling and High-Precision Counting of Matroid Bases](https://mlsanity.com/paper/2004.09079/) (2020)
- [Best of Both Worlds: Practical and Theoretically Optimal Submodular Maximization in Parallel](https://mlsanity.com/paper/2111.07917/) (2021)
- [Guarantees of Stochastic Greedy Algorithms for Non-monotone Submodular Maximization with Cardinality Constraint](https://mlsanity.com/paper/1908.06242/) (2019)
- [Some Inapproximability Results of MAP Inference and Exponentiated Determinantal Point Processes](https://mlsanity.com/paper/2109.00727/) (2021)

## Built on by (most cited first, 5 of 5)

- [RD-DPP: Rate-Distortion Theory Meets Determinantal Point Process to Diversify Learning Data Samples](https://mlsanity.com/paper/2304.04137/) (2023)
- [LDDR: Linear-DPP-Based Dynamic-Resolution Frame Sampling for Video MLLMs](https://mlsanity.com/paper/2605.11477/) (2026)
- [A Diversity Diet for a Healthier Model: A Case Study of French ModernBERT](https://mlsanity.com/paper/2602.22014/) (2026)
- [Adaptive Determinantal Client Scheduling in Federated Learning](https://mlsanity.com/paper/2609.23843/) (2026)
- [CORE: COverage CAlibration and Evicted-Mass REdistribution for KV Cache](https://mlsanity.com/paper/2610.02235/) (2026)

## Abstract (arXiv)

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.