Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 9: Top 15% of accepted papers, strong accept
review_content: This paper presented a novel kernel decomposition for nonsymmetric determinantal point processes, which enables linear time of inference and learning w.r.t. the cardinality of the ground set M. This is a significant improvement over previous arts and makes NDPP practical in relatively large datasets. The theoretical of the paper is solid and supportive to the main claim of the paper. This paper is well written and easy to follow. Even for readers without much theoretical background, this paper is still moderately friendly since the logic and insight are clear. I vote this paper a strong acceptance, except for some minor concerns as follows:

1) The authors employed a way to simplify the kernel decomposition below Theorem 1. However, it is unclear what the impact of this simplification is to the exactness of learning or inference. It would me a plus if the authors can give some theoretical analysis on the gap between such simplification and $P_0^+$.

2) I notice the authors provide both learning and inference procedures for NDPP. It seems these two procedures can formulate a way to learn latent NDPP in an Expectation-Maximization fashion. I would suggest the authors give some discussion about the feasibility of such integration, and this can be an interesting direction.

In general, I enjoy reading this paper and think this paper is insightful.
review_title: A good submission with sound theoretical support and practical potential. I vote a strong acceptance.

final_score: rating: 7: Good paper, accept
review_content: Nonsymmetric determinantal point processes (NDPPs) received some attention recently because they allow modeling of both negative and positive correlations between items. This paper developed scalable learning and MAP inference algorithms with space and time complexity linear in ground set size, which is a huge improvement compared to previous approaches. Experimental results show that the algorithms scale significantly better, and can roughly match the predictive performance of prior work.

This is a well written paper and I recommend its acceptance. Scalable learning and MAP inference algorithms are important for the application of the NDPPs model, which seems promising compared with its symmetric counterpart in experiments.

I have some (minor) comments listed below.

1. In Lemma 1, the result is only proved for skew-symmetric matrices with even rank. Does it hold for odd rank matrices? This is important to support the claim that the new decomposition covers the $P_0^+$ space.

2. Equation (3) uses notation $\lambda_i$, which is already used in Lemma 1. This could cause confusion.

3. In the paragraph after Theorem 1, it is proposed to set $B$ = $V$ and relax $C$. Is this used in Section 4? If not, I would suggest moving it to the experiments section, and adding some comparison in Table 2 to show the impact of this simplification.

4. I cannot quite understand the last sentence before Lemma 2. What can be computed in $O(K^2)$ time?

5. The footnote in Table 1 might cause confusion because it can be mis-interpreted as a square.

6. In G.1, the first sentence after equation (13), do you mean when $M$ is odd or when $\ell$ is odd?

7. In equation (24), $X$ should be $B^TXB$

8. The inverse of $C$ appears in the gradient of $Z$. Is $C$ guaranteed to be invertible in the learning algorithm? And how are $V$, $B$, $C$ initialized in the algorithm?

9. In equation (31), please double check if we need the reciprocal in the denominator.

review_title: Official Blind Review #4

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: This paper propose a decomposition for non-symmetric determinantal point process (NDPP) kernels (M*M) which reduces the requirements of storage and running to linear in cardinality (M). Additionally, they derive a NDPP maximum a posteriori inference algorithm that applies to both their proposed kernel and the previous work (NDPP). In their experiments, they show both learning kernels and the MAP inference for subset selection on real-life datasets. 

Pros:

	○ This paper is well-written and easy to follow.
	○ The author provide sufficient calculation process and relevant proofs of scalable NDPP.
	○ For the existing problems of traditional DPP method is time consuming, need large memory and could not apply to large set, the scalable NDPP really solves them (e.g., this method could run on Instacart and Million Song datasets). I think it is practical. 
	

Major Concern:

	○ I have some doubts about the authenticity of the experimental results in Table 2, for the following reason: in the previous work, i.e., [1] Learning Nonsymmetric Determinantal Point Processes. Gartrell et al. Neurips2019. The results under average MPR have signifcant difference with same datasets and same hyperparameter settings. However, in NDPP paper,  for Amazon: Apparel, the MPR of sym dpp is 77.42±1.12, MPR of nonsym DPP is 80.32±0.75, for uk retail,  the MPR of sym dpp is 76.79±0.6, MPR of nonsym DPP is 79.45±0.57.  In this paper,   for Amazon: Apparel, the MPR of sym dpp is 62.63±1.81, MPR of nonsym DPP is 72.2±3.07, for uk retail,  the MPR of sym dpp is 69.95±1.32, MPR of nonsym DPP is 74.17±1.37. There is a huge gap btw these two versions. I would like to know what causes this gap.
review_title: A good submission, it could be accepted once the author fix the bug in their experiments.

Meta-review: This paper proposes a technique of decomposing the nonsymmetric kernel of determinantal point processes, which enables inference and learning in time and space linear with respect to the size of the ground set.  This substantially improves upon existing work.  The proposed method is well supported both with theory and experiments.  All of the reviewers find that the contributions are significant, and no major flaws are identified through reviews and discussion.  The determinantal point process might not be one of the most popular topics in the ICLR community today but certainly is relevant.
Decision: Accept (Oral)