Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper proposes the acceleration implementations of the greedy-type algorithms for DPP MAP inference. Two algorithms are developed for the cardinality-constrained and unconstrained DPP MAP inference respectively.  The computational efficiency and accuracy are validated through experiments on simulated and real-world datasets. 
strengths_and_weaknesses: Originality: This paper incorporates the ideas of “lazy” and “fast” which are thought to be incompatible in the previous literature. 
Quality: The experiment results show that the algorithms are powerful.  The paper is generally well written in both aspects of grammar and technical discussion. 
Clarity: A lot of details of the experiment seem to be missing.
Significance: The proposed acceleration method does have effectiveness through validations on simulated and real datasets. 

questions: 1.	The authors propose two algorithms for the two different tests. What is the motivation to propose these two types? 
2.	The introduction section of the relevant background is unclear and needs more details and formalization. 
3.	In section 5.1, figure 2, we observe the runtime is not strictly increased when $n$ increases. Why do the authors get decreasing runtime values? 
4.	In section 5.2, please provide more synthetic data settings when $n$ and $k$ vary. 
5.	I suggest the authors demonstrate the experiment results in more detail and show the power of the purposed methods. 
6.	The authors review many existing methods in the introduction but only compare three methods in the simulation section. Why do you choose these three methods to make a comparison?

limitations: The authors mention the limitation that the method does not improve the worst-case time complexity. The proposed method can only fasten empirical runtimes.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper presents new greedy algorithms for maximum a posteriori (MAP) inference for determinantal point processes (DPPs).  MAP inference seeks to find the subset with the highest probability under the DPP.  The first major algorithm presented by the authors combines the ideas of “lazy” and “fast” greedy MAP inference algorithms from prior work.  This LazyFastGreedy algorithm has nearly the same time complexity as the fastest known FastGreedy algorithm from prior work, but runs faster in practice; it is applied to cardinality-constrained DPP MAP inference and extended to several other variants of greedy algorithms.  The second major algorithm presented by the authors is a fast version of the DoubleGreedy algorithm for unconstrained DPP MAP inference.  Finally, the authors present experimental results on synthetic and real datasets, demonstrating that their proposed algorithms can be significantly faster than the fastest known approaches from prior work.
strengths_and_weaknesses: Strengths:
* The new greedy DPP MAP inference algorithms presented by the authors appear sound, and are reasonably well explained. 
* The derived runtimes appear correct, although I have not carefully validated the proofs.  
* The experimental results do indeed demonstrate that the proposed algorithms can be significantly faster than the fastest known approaches from prior work, despite nearly equivalent time complexity (in the case of LazyFastGreedy).  Therefore, the contributions in this paper are significant.
* The discussion of related work is reasonably clear and thorough.

Weaknesses:
* For experiments on the real-world datasets (Netflix Prize and MovieLens), the authors don’t explain how the item vectors of the DPP B matrix are computed from each dataset.  This is an important missing detail that should be provided, since each of these datasets consists of users’ ratings of items (movies), and it is not obvious how each item vector was built from these ratings.
* Figure 1(b) is somewhat unclear.  This figure should be reworked to be more clear and interpretable.

questions: * On line 220, d >= n seems to be incorrect.  I suppose this should instead be d <= n.
* As indicated above, Figure 1(b) should be revised to be more clear.
* As indicated above, can you describe how the item vectors of the B matrix for the real-world datasets are computed?
* Nonsymmetric DPPs (NDPPs) have recently gained some attention.  Are the MAP inference algorithms presented in this paper appropriate for NDPPs?

limitations: A brief mention of the limitation of the LastFastGreedy algorithm not improving upon the worst-case time complexity of the greedy algorithm is included in the paper.  However, the authors should provide a somewhat more detailed discussion of any other known limitations, as well as the potential for negative societal impact, which is completely absent.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper studies a fast algorithm for greedy MAP inference of Determinantal Point Processes (DPPs). The authors first apply a lazy evaluation trick (widely used in submodular maximization) to the Cholesky-factorization-based greedy DPP MAP algorithm (FastGreedy). They analyze the runtime of the proposed algorithm for the best and worst cases. Although the worst-case runtime is no better than FastGreedy, it practically works well. They also apply the lazy evaluation trick to the double greedy algorithm, which guarantees a constant approximation ratio of unconstrained greedy maximization. Experimental results on both synthetic and real-world datasets verify the effectiveness of the proposed acceleration with a promising speedup.

strengths_and_weaknesses: Strengths:
- This paper is written well and easy to follow up on the methodology. 
- This paper fills the gap of the FastGreedy algorithm by adopting the lazy evaluation trick, and report the empirical speedup beyond the other algorithms for greedy submodular maximization.

Weaknesses
- The novelty of this paper is fairly weak. The main contribution is a simple adaptation of the lazy evaluation to the greedy DPP MAP inference algorithms. Both the lazy evaluation trick and the fast greedy DPP MAP implementation (as well as the double greedy algorithm) have been studied prior. These contributions are under the bar of acceptance.
- Although the proposed algorithm empirically works faster than other competitors, it is suspicious when it can be effective. Currently, the runtime complexity is lightly analyzed including only the best and worst scenarios. And the worst-case runtime is even worse than the previous FastGreedy algorithm (in the general case). This makes contributions of this work weak and it needs more careful analysis of the runtime, e.g., conditions that the LazyFastGreedy algorithm achieves for the best (or at least better) runtime.

questions: Some explanations of [22] are missing. The algorithm studied in [22] can be essentially used for the size-constrained greedy DPP MAP. Although it is required a one-time preprocessing, its runtime is logarithmic in n (the size of the ground item), which is much beneficial for large n. And they reported up to x224 speedup than the FastGreedy algorithm. Hence, by simple comparison to FastGreedy (LazyFastGreedy shows x17 speedup), it is expected that the algorithm is still faster than LazyFastGreedy. Does the author have a chance to compare with it?
limitations: Mentioned in weakness
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper considers the problem of efficiently computing an approximation to the maximum a posteriori inference (MAP) of a discrete determinantal point process (DPP). Specifically, $L$-ensemble DPPs are considered, i.e., DPPs for which the likelihood of a point pattern has a simple formula using a likelihood matrix kernel $L\succeq 0$.

This work combines two existing approaches: the lazy greedy algorithm for submodular function maximization and the fast greedy algorithm for DPP MAP inference. The latter relies on  Cholesky factorization updates of the likelihood kernel.

Two cases are discussed: cardinality-constrained and unconstrained DPP MAP inference.

Numerical simulations illustrate the interest of this approach.
strengths_and_weaknesses: originality: To my knowledge, this idea has not yet been discussed elsewhere.

quality: This paper is carefully written and understandable. It contains very few typos. Although it is not a big issue, there is no conclusion section.

clarity: I found the text and the maths clearly written. A few suggestions of improvements are given below.

significance: The results of this paper are probably useful in practice. On the other hand, this work combines two existing techniques and this combination may be appear as a weak contribution. However, since this combination is not straightforward,  this paper is interesting for the ML/DPP community.
questions: Here are some comments and suggestions.

- At line 87, I think it is worth mentioning that $L$ is the likelihood kernel of an $L$-ensemble DPP. Basically, the authors do not work with any DPP but they rather deal with a subclass of DPPs for which the correlation kernel has the form $L(L+\mathbb{I})^{-1}$ and which are called $L$-ensemble DPPs. I suggest that the authors briefly mention this fact somewhere by possibly pointing to an extra paragraph in Supplementary Material.

    
- At line 105, it is mentioned that the log-determinant function $f$ is monotone if the smallest eigenvalue of $L$ is at least $1$.
Could you give a pointer to a reference? For instance, Sharma, Deshpande, Kapoor ICML 2015. 

- At line 123, there is a typo: the authors write *hence it adds $j_t = i$ to $\overline{S^{(t-1)}}$*.
 It should be *it adds $j_t = i$ to $S^{(t-1)}$*.

- At line 240, there is a missing $\det$. The correct expression should be $g(S) = \log \det L^{-1}[S]$.

Minor comments:

- Line 15: the use of the singular is strange. I suggest 'DPPs have been...'

- Line 70: *to have the submodularity* &larr; to be submodular?

- line 187: The notation $U$ (uppercase) is a bit misleading since $U$ is a real number and not a matrix (or a set). It is maybe better to use a lowercase letter.
limitations: The authors discuss the limitation of their results and summarize them in the checklist. I do not expect negative societal impacts from this algorithmic study.
review_title: null

Meta-review: metareview: Although the reviewers gave a wide range of ratings to this paper, they all agreed that it is well-written and presents two novel, sound algorithms that perform well in practice. The main concern was that the algorithms merely combine existing techniques, which is true. However, given that the resulting algorithms are elegant, well-motivated, and highly performant, and that achieving the combinations is not trivial, I believe this paper makes a significant contribution to an active field of research and deserves acceptance.

The authors should take the reviewers' comments into account as they prepare their final revision. In particular, I would encourage them to more explicitly describe their reasons for presenting two different algorithms (cardinality constrained/unconstrained). Currently, it feels like the two parts of the paper are somewhat disconnected.
confidence: Certain
Decision: Accept