Research map / Learning theory and algorithms / Prediction and decision losses
Lazy and Fast Greedy MAP Inference for Determinantal Point Process
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Combine lazy upper-bound updates with Cholesky-based fast greedy | Greedy DPP MAP inference · Synthetic DPP, L-input, n = k = 6000 | runtime (seconds): 37.4 -> 13.7 seconds | Helped |
| Use lazy row updates that compute Cholesky entries in cache-friendly blocks | FastGreedy · Synthetic DPP, n = 6000 | cache miss rate: 71.3\% -> 3.3\% | Helped |
| Use incremental Cholesky updates and inverse-kernel marginals | DoubleGreedy · Synthetic DPP, n = 6000 | solution construction runtime (seconds): 36233.1 -> 34.6 seconds | Helped |
| Use incremental Cholesky updates and inverse-kernel marginals | DoubleGreedy · Netflix Prize, unconstrained DPP | solution construction runtime (seconds): $> 86400.0$ -> $916.2$ seconds | Helped |
| Use incremental Cholesky updates and inverse-kernel marginals | DoubleGreedy · MovieLens, unconstrained DPP | solution construction runtime (seconds): $> 86400.0$ -> $6337.3$ seconds | Helped |
| Avoid redundant Cholesky off-diagonal calculations through lazy updates | LazyFastGreedy · Synthetic (ii) and real-world DPP settings | runtime | Helped |
| Use lazy updates in the B-input setting, where each off-diagonal requires a feature-vector computation | FastGreedy · Synthetic (ii) and real-world DPP settings | runtime | Mixed |
| Use LazyFast rather than Fast for RandomGreedy, StochasticGreedy, and InterlaceGreedy | Greedy-type DPP MAP inference algorithms · Synthetic and real-world datasets | runtime | Helped |
| Use LazyFast StochasticGreedy instead of LazyFastGreedy | StochasticGreedy · Synthetic and real-world datasets | objective value | Hurt |
Closest papers by meaning
- Faster Greedy MAP Inference for Determinantal Point Processes (ICML 2017 · similarity 0.94)
- Scalable Learning and MAP Inference for Nonsymmetric Determinantal Point Processes (ICLR 2021 · similarity 0.91)
- Fast Greedy MAP Inference for Determinantal Point Process to Improve Recommendation Diversity (NeurIPS 2018 · similarity 0.91)
- One-Pass Algorithms for MAP Inference of Nonsymmetric Determinantal Point Processes (ICML 2022 · similarity 0.90)
- Composable Coresets for Determinant Maximization: Greedy is Almost Optimal (NeurIPS 2023 · similarity 0.89)
- State-of-art minibatches via novel DPP kernels: discretization, wavelets, and rough objectives (NeurIPS 2026 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.