Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper studies the online inference and learning problems for nonsymmetric determinantal point processes (NDPPs). The authors use the online greedy algorithm for MAP inference and modify the learning objective for being suitable in the online setting. Experiments with real-world datasets show that the proposed online algorithms are comparable or even better than state-of-the-art offline algorithms.
main_review: Strengths:
- The paper studies a new problem of NDPPs under the online setting that has not been covered before. 
- The authors properly apply the prior online algorithm for greedy submodular maximization to the NDPPs
- Experimental results are convincing that the effectiveness of the proposed online inference and learning algorithms for NDPPs

Weaknesses:
- The writing quality needs to be improved. The manuscript contains several typos, notational abusements which are provided with minor comments (below). Also, the paper simply introduces the proposed algorithms without any justification or intuition, which is hard to understand how the authors deal with problems under the online settings.
- Moreover, some algorithms are already proposed in prior works, but there is no reference. For example, Algorithm 2 (Online-LSS) was proposed in [1].

  [1] Bhaskara et al., Online MAP Inference of Determinantal Point Processes, NeurIPS, 2019
- It is not clear how the streaming setting in section 4 is different from the online setting in section 5. Since both Algorithm 1 and 4 take sequential inputs (with random order or on-the-fly), it seems that both can be used for both settings. It would be great if more detailed descriptions of streaming and online settings are provided.
- In section 5, the authors provide 2 different algorithms, i.e., local search and 2-neighborhood local search. Comparing Theorem 5 and 7, the latter has no gain in terms of runtime complexity. However, it shows better empirical performance. What is the reason for it? Can the optimality of these algorithms be analyzed? 
- The authors propose the approximate objective (Eq (4)) for learning NDPPs under the online setting. However, this is somewhat very different from the log-likelihood of DPP because the objective contains $\log \det(L_S) -\log \det(L_S + I_S)$. Does learning this objective guarantee convergence of the ground-truth NDPP objective? How does the approximated objective Eq (4) relate to the offline version of the MLE objective?

Minor comments:

  - A comma is missing in the fourth line of the second paragraph on page 1.
  - Please edit “state-of-the-art” in the second paragraph on page 2.
  - Please edit “are minimize” -> “are minimizing” in the second last row on page 3.
  - It would be good to place Algorithm 4 in the main manuscript.
  - In Theorem 5 and 7, please edit $f(S) = \det( V_S^\top V_S + B_S^\top C B_S)$
  - What is $j_{\mathrm{\max}}$ in line 9 in Algorithm 1?

summary_of_the_review: Although this paper firstly studies new problems of online NDPPs, it has a lack of algorithm novelty, theoretical analyses as well as writing quality for addressing their methodology. Hence, the paper should be improved for acceptance.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper introduces the streaming and online MAP inference and learning problems for NDPPs.
- For streaming MAP inference, an algorithm is proposed with total time linear in $n$ and memory that is constant in $n$;
- For online MAP inference, several algorithms are proposed such that at any point in time a valid solution is maintained;
- For online learning algorithm, a single pass algorithm is proposed with memory that is constant in $m$;
- Experiments are conducted to show that these streaming and online algorithms achieves comparable performance to state-of-the-art offline algorithms.
main_review: The problems that this paper studies are very interesting. Several algorithms are proposed to solve these problems, and the effectiveness of the algorithms are verified through experiments.

The technical sections are a bit hard to follow, and a lot of details are omitted to save space. For example, for outline of Algorithm 2, the auxiliary set $T$ is defined but its size estimate is not given. It would be great to include some intuition in the main paper.
summary_of_the_review: Overall I think the problems that this paper studies are interesting and the proposed algorithm are effective.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper introduces MAP-inference and learning algorithms for nonsymmetric determinantal point processes (NDPPs) in the streaming and online settings. 

This paper provides the first analysis of NDPP-related algorithms within a streaming context; its contributions include the algorithms themselves, theoretical analyses (algorithm guarantees, space and time complexity), and experimental evaluation of these algorithms across several standard DPP-evaluation datasets.
main_review: ##  Strengths
- Clarity: this paper is well-exposed and the intuition behind the algorithms is clear (the background exposition on NDPPs is also very well written and accessible).
- Novelty: as the authors mention, this work provides the first analysis of MAP-inference and learning for the streaming settings of NDPPs.
- Empirical evaluation: the authors show that the online 2-neighbor greedy MAP algorithm improves upon _the offline algorithm_, which is a surprising and meaningful result.

## Weaknesses
- The streaming context is novel for NDPPs. However, as the authors point out, there exists previous work looking into streaming for standard DPPs [1]. Comparing the proposed algorithms to [1] to verify that the lack of symmetry provides similar benefits in the streaming setting to those in the offline setting stands out as a missing comparison.
- The first streaming algorithm (Algorithm 1) is quite simplistic, and is more interesting as a baseline rather than as a contribution in of itself.
- The core idea behind the better performing MAP algorithms (online LSS, online 2-neighbor) lies in the construction of a "stash" of discarded items. This idea was introduced in [1] for the MAP inference of (symmetric) DPPs, but the explicit connection between these two works is not made in this paper. If there are crucial differences between the stashes introduced in [1] and the stash used in this work, this should be mentioned explicitly and in detail; if the two ideas are similar, this should be discussed prominently in this work. Similarly, the results in Theorem 5 are (as far as I can tell) almost identical to those of [1, Theorem 3.1]. Again, this should be discussed explicitly in this paper. (Relatedly, I think there is a confusion between $\epsilon$ (used in [1]) and $\alpha$ (used here) to describe Online LSS, since I believe the authors use $\epsilon$ to describe Online-LSS in the experimental section. 

## Questions / comments
- In [1], algorithm 1's dependency on Δ is an issue, since Δ can be arbitrarily small. Does a similar issue arise for Online LSS and Online 2-neighbor? If so, can this be addressed?
- More generally, being explicit about how the lack of symmetry in the DPP changes how the streaming setting must be approached would make for an interesting contribution of this work.
- Could 2-neighbor be extended to arbitrary sizes of subsets (3-neighbor, etc.)? Understanding at which point the degree of interactions cease to provide benefits that are worth the increase in memory/time constraints would be a valuable contribution to the DPP community: are pairwise interactions, as in 2-neighbor, sufficient to characterize most of the necessary DPP properties?
- The derivation of the gradient updates for the online algorithm can be removed from the main paper.
- Can the authors provide any insight into the stunning performance of the online learning algorithm? Compared to the offline algorithm, the online learning seems to converge almost an order of magnitude faster. It would be interesting to see if it's possible to switch from the online to the offline algorithm after the initial jump in log-likelihood, to achieve the best of both worlds (fast convergence, low NLL).
- Am I correct in understanding that Figure 1 reports the volume rather than the log volume? If so, the authors should consider log-warping the evaluation function $f$, since improvements in the range of $10^{-20}$ are difficult to gauge.
- Can you clarify the experimental conditions used for the offline learning algorithm (batch size, etc.)?

[1] Online MAP Inference of Determinantal Point Processes, Bhaskara et al., 2020
summary_of_the_review: This paper proposes the first analysis of MAP inference and learning of nonsymmetric DPPs in a streaming setting; the authors propose novel algorithms, provide guarantees and complexity analyses, and evaluate their algorithms empirically across a variety of benchmarks. Startlingly, the authors show that their online algorithms are competitive with (and often outperform) their offline equivalents.

My main concern with this paper is novelty: there is significant overlap between the MAP-inference section of this work and previous work by Bhaskara et al. (2020), both in terms of the key ideas (using a stash) and in how the algorithms are analyzed. If this overlap is only in appearance, the authors should discuss in detail where their contributions depart from this previous work. Currently, it is difficult to understand the extent of the novelty of this work.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes online and streaming algorithms for MAP inference and learning for nonsymmetric determinantal point processes (NDPPs).  For the streaming setting, data points arrive in an arbitrary order, and the algorithms are constrained to using a single pass over the data, along with requiring sublinear memory consumption.  In the online setting, there is the additional requirement of maintaining a valid solution at any time step.  The authors provide some theoretical guarantees for the proposed algorithms, and perform experiments that demonstrate that their performance is comparable to (or better than) offline algorithms for these tasks.

main_review: Strengths:
- The proposed online and streaming algorithms for MAP inference and learning appear to be novel, and in a number of cases empirically outperform state-of-the-art offline NDPP algorithms for these tasks.
- The proposed streaming MAP inference algorithm (Alg. 1) has theoretical guarantees for MAP approximation quality, and time and space complexity.  The proposed online MAP inference algorithms (Algs. 2 and 4) have theoretical guarantees for time and space complexity.
- The proposed online learning algorithm (Alg. 3) has theoretical guarantees for time and space complexity.
- The paper is reasonably well written and easy to follow.

Weaknesses:
- Some of the claims made in Sec. 6.1 regarding the state-of-the-art NDPP learning algorithm in Gartrell et al. (2021) appear to be incorrect.  Sec. 6.1 claims that the Gartrell et al. (2021) learning algorithm: 1) must store all training data in memory; 2) must make multiple passes over the data; and 3) subsets are not processed sequentially as they arrive.  However, the implementation of the learning algorithm in Gartrell et al. (2021) uses Adam (a variant of SGD), which can run with a batch size of 1, or with minibatches, and thus can be run in a streaming setting that does not require all data to be loaded into memory.  Thus, claims 1 - 3 seem to be incorrect.
- The normalization term, $Z(V_{S_t}, B_{S_t}, C)$, used in the approximate objective (Eq. 4) for the online learning algorithm is not equivalent to the standard normalization term for a NDPP ($Z(V, B, C)$), nor is it clear that this “approximate” normalization term actually provides a reasonable approximation to the true NDPP normalizer.  The authors do not address this issue in the paper, and thus the proposed online learning algorithm has no theoretical approximation guarantees when compared to standard NDPP learning algorithms.  Therefore, optimizing Eq. 4 appears to violate the requirements described in Definition 8, since the true NDPP regularized log-likelihood is not being maximized.  This seems to be a critical issue. 

summary_of_the_review: This paper has strong contributions in the area of streaming and online MAP inference algorithms.  However, there are some notable issues with the contributions regarding the online learning algorithm, including the comparison with prior work, and the correctness of the approximate optimization objective (Eq. 4), as described above.  Thus, unless the authors can address these issues in the rebuttal, it is hard to recommend this paper for acceptance.
review_title: null

Meta-review: This paper studies online MAP inference and learning for nonsymmetric determinantal point processes (NDPPs). The main contribution is an online greedy algorithm. Surprisingly they show that their algorithm outperforms various offline algorithms on real-world datasets. That said, the main concern was the novelty with respect to the prior work of Bhaskara et al. who gave an online approximation algorithm for MAP inference in DPPs. To compare the two works: (1) Bhaskara et al. give an algorithm for DPPs, and NDPPs are more complex (2) Bhaskara et al. give provable guarantees on the approximation ratio, but no such guarantees are known for NDPPs (3) And finally, some of the key ingredients in the online algorithm for NDPPs, like the stash, were already in the work of Bhaskara et al. Overall the reviewers felt that this submission would be improved with a clearer discussion of the contributions over prior work.
Decision: Reject