Online MAP Inference and Learning for Nonsymmetric Determinantal Point Processes
Authors: Aravind Reddy
Ryan Rossi
Zhao Song
Anup Rao
Tung Mai
Nedim Lipka
Gang Wu
Eunyee Koh
Nesreen Ahmed
Venue: ICLR 2022 Submitted (2022)
Keywords: online algorithms
nonsymmetric determinantal point processes

Abstract: In this paper, we introduce the online and streaming MAP inference and learning problems for Non-symmetric Determinantal Point Processes (NDPPs) where data points arrive in an arbitrary order and the algorithms are constrained to use a single-pass over the data as well as sub-linear memory. The online setting has an additional requirement of maintaining a valid solution at any point in time. For solving these new problems, we propose algorithms with theoretical guarantees, evaluate them on several real-world datasets, and show that they give comparable performance to state-of-the-art offline algorithms that store the entire data in memory and take multiple passes over it.

Under review as a conference paper at ICLR 2022
ONLINE MAP INFERENCE AND LEARNING FOR NONSYMMETRIC DETERMINANTAL POINT PROCESSES
Anonymous authors Paper under double-bling review
ABSTRACT
In this paper, we introduce the online and streaming MAP inference and learning problems for Non-symmetric Determinantal Point Processes (NDPPs) where data points arrive in an arbitrary order and the algorithms are constrained to use single- pass over the data as well as sub-linear memory. The online setting has an additional requirement of maintaining valid solution at any point in time. For solving these new problems, we propose algorithms with theoretical guarantees, evaluate them several real-world datasets, and show that they give comparable performance to state-of-the-at offline algorithms that store the entire data in memory and take multiple passes over it.
INTRODUCTION
Determinantal Point Processes (DPPs) were first introduced in the context of quantum mechanics (Macchi, 1975) and have subsequently been extensively studied with applications several areas of pure and applied mathematics like graph theory, combinatorics, random matrix theory (Hough et al., 2006; Borodin, 2009), and randomized numerical linear algebra (Derezinski & Mahoney, 2021). Discrete DPPs have gained widespread adoption in machine learning following the seminal work of Kulesza & Taskar (2012) and there has been a recent explosion of interest in DPPs the machine learning community. For instance, some of the very recent uses of DPPs include automation of deep neural network design (Nguyen et al., 2021), deep generative models (Chen & Ahmed, 2021), document and video summarization Perez-Beltrachin & Lapata, 2021), image processing (Launay et al., 202 I), and learning in games (Perez-Nieves et al., 2021).
A DPP is probability distribution over subsets of items and is characterized by some kernel matrix such that the probability of sampling any particular subset is proportional to the determinant of the submatrix corresponding that subset in the kernel. Until very recently, most prior work DPPs focused on the setting where the kernel matrix is symmetric. Due to this constraint, DPPs can only model negative correlations between items. Recent work has shown that allowing the kernel matrix to be nonsymmetric can greatly increase the expressive power of DPPs and allows them to model compatible sets of items (Gartrell al., 2019; Brunel, 2). To differentiate this line of work from prior literature on symmetric DPPs, the term Nonsymmetric DPPs (NDPPs) has often been used. Modeling positive correlations can be useful in many practical scenarios. For instance, an E-commerce company trying to build product recommendation system would want the system to increase the probability of suggesting a router if a customer adds modem shopping cart.
State-of-the-art algorithms for learning and inference on NDPPs (Gartrell et al., 2021) require storing the full data memory and take multiple passes over the complete dataset. Therefore, these algorithms take too much memory to be useful for large scale data, where the size of the entire dataset can be much larger than the random-access memory available. These algorithms are also not practical in settings where data is generated on the fly, for example, in E-commerce applications where new items are added to the store over time, and more importantly, added to the carts users instantaneously.
This work makes the following contributions:
Streaming and Online Inference: We formulate streaming and online versions of maximum posteriori (MAP) inference on fixed-size NDPPs and provide algorithms for solving these problems. In the streaming setting, data points arrive in arbitrary order and the algorithms constrained to

---

Under review as a conference paper at ICLR 2022
single-pase paele-pass over the data well as sub-linear memory (i.e. memory that is substantially smaller than the size of the data stream). The online setting we consider has an additional restriction that we need to maintain valid solution at every time step. For both these settings, we provide algorithms which have comparable or even better solution quality than the offline greedy algorithm while taking only single pass over the data and using fraction of the memory used by the offine algorithm.
We introduce the online learning problem for NDPPs and provide an algorithm which solves this problem using a single-pass over the data and memory that is constant in m, the number of baskets in the training data (or equivalently the length of the stream). In comparison, the offline learning algorithm takes a large number of passes over the entire data and uses memory linear in m. Strikingly, our online learning algorithm shows comparable performance (log-likelihodd) to the state-of-the-are offline learning algorithm, while converging significantly faster in all cases (Figure 2). This is notable, since our algorithm uses only single pass over the data, while using a tiny fraction of the memory.
Online Learning:
Table I: Summary of our online learning and MAP inference algorithms for NDPPs. We omit O for simplicity. All algorithms use only a single-pass over the data.
NDPP Problem
Update Time
Total Time
Space
Streaming
STREAM- PARTITION (Alg. 1)
Tam d)
Tam (8. d)-n
k²
+
d
Inference
ONLINE-LSS (Alg. 2) Tam (K: d) (oogg(
Tam (Ki, d) (ak A (A))
A² + d'oog
Online
ONLINE 2-NEIGH (Alg. 3) Taes (Kr, d) (og)
Tass (k. d) (nk2 h2 (A))
+²+ dd dloga(
ONLINE- ONLINE-GREEDY (Alg. 5) Tam(F: d)-k
Tam (Fe, d) -)
+d
Online Learning
ONLINE-NDPP (Alg. 4) d +d'
mid" mdd
d² + d.
RELATED WORK
Even in the case of (symmetric) DPPs, the study of online and streaming settings is in a nascent stage. In particular, Bhaskara et al. (2020) were the first to propose online algorithms for MAP inference of DPPs and Liu et al. (2021) were the first to give streaming algorithms for the maximum induced cardinality objective proposed by Gillenwater et al. (2018). However, no work has focused on either online or streaming MAP inference or online learning for Nonsymmetric DPPs.
special subset of NDPPs called signed DPPs were the first class of NDPPs to be studied (Brunel et al., 2017). Gartrell et al. (2019) studied a more general class of NDPPs and provided learning and MAP Inference algorithms, and also showed that NDPPs have additional expressiveness over symmetric DPPs and can better model certain problems. This was improved by Gartrell et al. (2021) in which they provided a new decomposition which enabled linear time learning and MAP Inference for NDPPs. More recently, Anari & Vuong (2021) proposed the first algorithm with a (O)) approximation factor for MAP Inference on NDPPs where k is the number of items to be selected. These works are not amenable to the streaming nor online settings that are studied our paper. In particular, they store all data in memory and use multiple passes over the data, among other issues. In this work, we formally introduce the streaming and online MAP inference and online learning problems for NDPPs and develop online algorithms for solving these problems. To the best of our knowledge, our work is the first to study NDPPs in the streaming and online settings, and develop algorithms for solving MAP inference and learning of NDPPs in these settings.
PRELIMINARIES
Notation.
Throughout the paper, we use uppercase bold letters (A) to denote matrices and lowercase bold letters (a) to denote vectors. Letters in normal font (a) will be used for scalars. For any positive integer n, we use [n]] to denote the set {1, T.,...., n). A matrix M said to be skew-symme kemessy M - T where T is used to represent matrix transposition.
A DPP is a probability distribution on all subsets of [n] characterized by matrix E R"X", The probability of sampling any subset S C [m] i.e. Pr[S] (Lg) where Lg is the submatrix of L
2

---

Under review as a conference paper at ICLR 2022
obtained by keeping only the rows and columns corresponding to indices in S. The normalization constant for this distribution can be computed efficiently since we know that Esgiml det(Ls) =
Let(Ls) [s) For the DPP det + I.) (Kulesza & Taskar, 2012, Theorem 2.1). Therefore, Pr[S] det(L+
corresponding L be valid probability distribution, need det (st 2 for all = [n]] since Pr[S] 2 0 for all 5 C [n]. Matrices which satisfy this property are known as Po-matrices (Fiedler & Pták, 1966). For any symmetric matrix L, det Ls) 2 0 for all S S [r] if and only if L is positive semi-definite (PSD) i.e. x: Læ 2 O for all æ E RR. Therefore, all symmetric matrices which correspond to valid DPPs are PSD. But there are Po-matrices which are necessarily symmetric
(or even positive semi-definite.. For example, L [ 1
is nonsymmetric Po matrix.
-1
Any matrix L can uniquely written as the sum of a symmetric and skew-symmetric matrix: == (L L 1/2 (L L )/2. For the DPP characterized by L, the symmetric part of the decomposition can be thought of as encoding negative correlations between items and the skew- symmetric part encoding positive correlations. Gartrell et al. (2019) proposed decomposition which covers the set of all nonsymmetric PSD matrices (a subset of Po matrices) which allowed them to provide cubic time algorithm (in the ground set size) for NDPP learning. This decomposition is L V V + (BC' - CB Gartrell et al. (2021) provided more efficient (linear time) algorithms for learning and MAP inference using a new decomposition L V + B C.B. Although both these decompositions only cover a subset of Po matrices, it turns out that they are quite useful for modeling real world instances and provide improved results when compared to (symmetric) DPPs.
For the decomposition L = VVV + BT CBB we have V, B E Rdx" C E Rdxd and C' is skew- symmetrie. Here we can think of the items having having latent low-dimensional representation (u; b.) where vi, b, E Rd. Intuitively, a low-dimensional representation (when compared to n) is sufficient for representing items because any particular item only interacts with small number of other items in real-world datasets, as evidenced by the fact that the maximum basket size encountered real-world data is much smaller than n.
STREAMING MAP INFERENCE
In this section, we formulate the streaming MAP inference problem for NDPPs and design an algorithm for this problem with guarantees on the solution quality, space, and time.
4.1 STREAMING MAP INFERENCE PROBLEM
We study the MAP Inference problem in low-rank NDPPs in the streaming setting where we columns of a 2d x n matrix order (column-arrival model). Given some fixed skem-symmetric matrix C 1xx consider stream of 2d-dimensional vectors (which can be viewed as pairs of d-dimensional vectors) arriving in order:
(v), b2), (V2, b2), ..., (Vn, b.) where v., b, Rd, V [m]]
The main goal in the streaming setting is to output the maximum likelihood subset S C [n] of cardinality the end of the stream assuming that S is drawn from the NDPP characterized by - + B CB i.c.
S= argmax det(Ls) argmax det(VV Vs + CBBBs)
SC(m),81=k
For any S C [m]] Vs E ddx[s| is the matrix whose each column corresponds {,,, S). Similarly, Bs d is the matrix whose columns correspond to (b;, S). In the case of symmetric DPPs, this maximization problem in the non-streaming setting corresponds to MAP Inference in cardinality constrained DPPs, also known A-DPPs (Kulesza & Taskar, 2011).
Usually, designing a streaming algorithm can be viewed as a dynamic data-structure design problem. We want maintain a data-structure with efficient time and small space over the entire stream. Therefore, the secondary goals are to minimize the following:
Space: We consider word-R RAM model, and use number of words" to measure it.
'In Word-RAM, we usually assume each word Ollog n) bits.
3

---

Under review as a conference paper at ICLR 2022
Algorithm Streaming Partition Greedy MAP Inference for low-rank NDPPs
1: Input: Length of the stream n and a stream data points {(v), b1), (v2, b2),... (Un, bn]}
2: Output: A solution set S of cardinality k the end of the stream.
3: Su 6 0, So +- 0
4: while new data (ve, by) arrives in stream at time do
5:
i 1
6:
if
(t) f(S,-1 u ) then
7:
8, +
8:
i is multiple of & then
9:
S f 5 Us
8; 0 6
return S
Update time: time update our data-structure whenever we new arriving data point.
Total time: total time taken to process the stream.
Definition 1. Given three matrices E IR" dxk B E
dd and C E Raxd, let Tett (k, d) denote the
running time of computing
det(V T V+B
Tmae (d, d, k) Tmaat (k, k. k) where Tinat (a. b, c) is the time required to multiply two matrices of dimensions x b and x c. We have the last Tuna (k. k, k) term because computing the determinant of k k matrix can be done (essentially) in the same time as computing the product of two mairices of dimension k x k (Aho et al., 1974, Theorem 6.6).
k., d) Note that Taat (k, md,
We will now describe a streaming algorithm for MAP inference in NDPPs, which we call the "Streaming Partition Greedy" algorithm.
4.2 STREAMING PARTITION GREEDY
Outline of Algorithm 1:
Our algorithm picks the first element of the solution greedily from the
first seen E elements, the second element from the next sequence of & elements and on. As described in Algorithm 1, let us use Sp Si,..,, algorithm, where S, represents the solution of size i. In particular, we have that S, S U {s: where 8; = arg maXjEP. f(S U {i}) and P, denotes the i'th partition of the data i.e. P. =
, S₁ to denote the solution sets maintained by the
(1- +1. (i-1)m +2, 2.....
k
(0), b1), (02, b2), ... (Un/ke bnjk).... (tn-(r/k)+1 bn (m/K)+1), ... (Un, b..)
P1
P
Theorem 2.
For a random-order arrival stream, S is the solution output by Algorithm at the end of the stream and mmin where minn and maxx denote the smallest and largest singular values of Ls among all C [n] and [S] < 2k, then
(1-
E[log (Le)] >
log(OPT)
(1- (1- dmax log omin)
Qmin
where Ls V Vs + CBC and OPT
det( Vn B
max RC =
defer the proofs of the above and the following theorem to Appendix A.
Theorem 3. For any length-n stream (v) bj)..., (Vay b,) where (wi, b.) E Rd x Rd a E [n], the worst-case update time of Algorithm I is O(Tae (k, d)) where Taae (k, d) is the time taken compute f(S) = det dV V + B_ C for [S| = k. The total time taken is O(n Tace (k, d)) and the space used any time step Ō + d2).
4

---

Under review as a conference paper at ICLR 2022
Algorithm 2 ONLINE-LSS: Online MAP Inference for low-rank NDPPs with Stash.
Input: A stream of data points {(1),b) b1). (02, b2)..... (Un, ba)]. and constant a 2
2: Output: A solution set S of cardinality k at the end of the stream.
3: S, -
4: while new data point (ot, by) arrives in stream time do
5: if ||| < and f (SU {t]) + 0 then
6:
S S {t)
7: else
8:
i arg jas (SS (t) \ (i))
9:
ir I (i)) a- f(S) then
S (t (i)
11:
T
while 8 b::::e::: f \ (a))
a. f(S) do
13:
S - SU(b) (a)
14:
T T Tu (6)
15:
return S
5
ONLINE MAP INFERENCE FOR NDPPs
We now consider the online MAP inference problem for NDPPs, which is natural in settings where data generated on the fly. In addition to the constraints of the streaming setting (Section 4.1), our online setting requires to maintain valid solution at every time step. In this section, provide two algorithms for solving this problem.
5.1 ONLINE LOCAL SEARCH WITH A STASH
On a high-level, our algorithm is a generalization of the Online-LS algorithm for DPPs from Bhaskara et al. (2020). At each time step [n]] (after t 2 k), our algorithm maintains a candidate solution subset of indices S of cardinality k from the data seen so far i.e. 5 [1] s.t. |S]
Outline of Algorithm 2:
in streaming fashion. Additionally, also maintains two matrices Vs, B3 [S where the columns of Vg are {v,, S) and the columns of Bg are {b,, i S)- Whenever the algorithm sees a new data point (v,, br). it replaces an cxisting index from S with the newly arrived index if doing so increases fSS) at-least by factor of a 2 where is a parameter to be chosen (we can think of a being 2 for understanding the algorithm). Instead of just deleting the index replaced from S, is stored an auxiliary set T called the "stash" (and also maintains corresponding matrices Vr, Br), which the algorithm then uses to performs local search over to find a locally optimal solution.
We now define data-dependent parameter A which we will need to describe the time and space used by Algorithm 2.
Definition 4. Let the first non-zero value of f(S) with |S|
that can achieved the stream without any swaps be valaz i.e. till S reaches size k. any index seen is added to S if (S) remains non-
zero even after adding it. Let us define A = OPT2 vale:
where OPT; max det V3 Vs
B CBs).
Theorem 5. For any length-n stream (v), be),b,......
..., (Va, b,) where (Ve, b.) E Rdd x RR [n], the worst case update time of Algorithm 2 ( d) logg(()) where Taee (k, is the time taken
to compute ((S) = (V. V B C) for [S] = k. Furthermore, the amortized update time is
O(Taor (k, d)- (k+ (og) )) and the space used at any time step is at most O(k2 + + log (A)):
We defer the proof for the above theorem and all following theorems in this section to Appendix B.
5.2 ONLINE 2-NEIGHBORHOOD LOCAL SEARCH ALGORITHM WITH STASH
Before we describe our algorithm. we will define a neighborhood of any solution, which will be useful for describing the local search part of our algorithm.
5

---

Under review as a conference paper at ICLR 2022
Algorithm 3 ONLINE-2-NEIGIINEE
Local Search over 2-neighborhoods with Stash for Online MAP Inference low-rank NDPPs.
Input: A stream of data points {(v, b1), (V2, b (Un, b, and constant 2 1
2: Output: A solution set S of cardinality k at the end of the stream.
3: S. S. <
4: while new data (ve, b.) arrives in stream at time & do
and f (()) A 0 then 5: if [|] S (t}
6:
7:
else
8:
{i.j} arg max hEs (f(S (t)
fa)), 1,t] (a,b))) (a, (a,b)))
9:
Imax - Max (f(SU ( (1 if maxx > ((S) then
10:
11:
if' two items are chosen to be replaced: then
S S--SUR (t 1, \ {i.j}
13:
T TU
else
15:
S S+ \0 T+ while Bai ((u (a,b)) a(5) do
17:
S S Sufdd ba.b] Tu fadd
19:
return 8
Definition 6 (S, T)). For any natural number and any sets S,T define the neighborhood of S with respect to T
N, = (S' CSUT = and |s' S sr}
Outline of Algorithm 3: Similar to Algorithm 2, our new algorithm also maintains two subsets of indices and T, and corresponding data matrices Vs. Bs. Vr, Br. Whenever the algorithm sees a new data-point (v,, b;), it checks if the solution quality f(S) can be improved by factor of by replacing any element in with the newly seen data- data-point. point. Additionally, it also checks if the solution quality can be made better by including both the points (v,, b,) and the data-point (#t-1, b,-1). Further, the algorithm tries to improve the solution quality by performing a local search on (S, 7) i.e. the neighborhood of the candidate solution S using the stash T' by replacing at most two elements of S. There might be interactions captured by pairs of items which are much stronger than single items NDPPs (see example 5 from Anari Vuong (2021)).
A full description of Algorithm 3 can be found in Appendix B.
Theorem 7, For any length-n stream (V1, bt),...,,1u) bn) where (v,, bi) E Rd x Rd V Vtt [n], (TTee d) k22 log
3 (A)) where Taet (k, d) is the time taken compute f(S) det( V + B CB) for |S| k. The amortized update time
the worst case update time of Algorithm
is O (Taet(k, (I22 log ) d llooo. (A)).
and the space used any time step is most O,k² d2
ONLINE LEARNING
In this section, we will first formally introduce the online learning problem for NDPPs and then develop an online algorithm for this new setting with theoretical guarantees. To the best of our knowledge, this is the first work to study the online learning setting for NDPPs.
6.1 ONLINE SETTING
The online learning problem for NDPPs is formally defined as follows:
Definition 8 (Online NDPP Learning). Given a continuous stream of observed sets St, of items from (n), the online learning problem is maintain NDPP kernel

---

Under review as a conference paper at ICLR 2022
Algorithm 4 ONLINE-NDPP-LEARNNN
Online learning for low-rank NDPPs
1: Input: Stream of sets {Si, 15,,S,... .t............ St....}
arriving in an online fashion (in some arbitrary order), embedding size d for NDPP model matrices
2: Output: low-rank NDPP kernel (+) at any time t (and ((A,, B((),, C(+) if warranted)
3: Initialize matrices V. B,
4: while new set S, = (a1, ... arrives in stream do
5: Update Vs, Bs. , C' using Vvs, dtt, Bs,, Vt. Voti (Eqs. 9, 10, II) respectively.
6: return low-rank NDPP kernel L (1) at time
L. = (V= + +BBCB for every time step t that maximizes the regularized log- oollikelihood:
1 VVV,BOL C) - Σ log det (Vs.Vs. Vs. + B log det (VV++B' - R(V,B) (3)
where Vs., Bs. E Rdx Sil denote sub-matrices of V and B which are frrmedd by the columns that
correspond to the items in S,, and the regularizer R(V (V, = a Ex=1 1
js. 111/vlli 112 + Σi=1 1
where pr is the number of occurrences of the item i all the training data (subsets), a, 3 are tunable hyperparameters.
An online learning algorithm for NDPPs needs to:
Use space that is independent of the length of the stream seen so far.
Use only a single sequential pass over the stream of subsets {S; S [n]] | to t).
Update the NDPP model upon arrival of the subset St at time t, then discards it.
Have a fast update time that is sub-linear the number of unique items n.
Our online setting is the natural setting to be studied for learning NDPPs in the real-world, as new subsets are generated continuously over time, for instance in an E-commerce application. In contrast, the sfate-o--the-ar learning algorithm Gartrell et al. (2021) has the following limitations that make it fundamentally offfine: First, it stores all training data in memory and so uses O(td') space where d' max; |S,| is the size of the largest subset in the stream (Si,..., S.). Second, it takes multiple passes over the data. Third, subsets are not processed as they arrive sequentially, instead that algorithm requires all data to be stored in memory, and updates a large group of points simultaneously over multiple rounds. Thus, incurring a large processing time that is not amenable to the online learning setting. Finally, it also incurs update time of O Opnd? + ptd' which is too much for the online setting.
6.2 ONLINE ALGORITHM
We present our online learning approach for NDPPs in Algorithm 4. To update (V, B,C) C) at every time step f, we use the gradient of the following objective function th which is an approximation of the regularized log-likelihood d. B,C). Let us define Z(V, B, C) = log det( V T V TTCB CB+ 1).
Our approximate objective
dh V. B, C) = loo det (V5. Vs. + B3, Z(Vs,, Bs. C) - R(Vs, Bs.) (4)
For every time step t, we only update Vs., Bs., C uusing the gradient of th, ie. Vv., Bs, th. We defer the gradient derivations to Appendix D.
We defer the proof of the following theorem to Appendix
Theorem 9. Algorithm 4 uses Odd² + d²) space' ", Also, the update time for single subset Se arriving at time I. in the stream is O + d where d' is the size of the largest set in the stream.
For every new subset St arriving in the stream, Algorithm updates only the columns of V and B corresponding to the elements in S, hence, Vs., Bs. It uses total space O(nd + d²2), which is
'Note that the Ond + d)) required to store the matrices V. B, and C are omitted for simplicity (since these are common all algorithms).
7

---

Under review as a conference paper at ICLR 2022
independent of the stream length (and is therefore sub-linear in it as well); takes single pass over the stream; updates the NDPP model only using the subset St and then discards S has O d²²) update time. This is in contrast to the offline learning algorithm that uses (mdd") space where m is the length of the stream and d' the size of the largest (m > d, d', n).
EXPERIMENTS
Our experiments are designed evaluate the effectiveness of the proposed online inference and learning algorithms for NDPPs. Experiments are performed using a standard desktop computer (Quad-Core Intel Core i7, 16 GB RAM) using many real-world datasets. Details of the datasets can be found in Appendix E.
7.1 ONLINE INFERENCE
As a point comparison, we also use the state-of-the-art offline greedy algorithm from Gartrell et al. (2021). This algorithm stores all data in memory and makes & passes over the dataset and in each round, picks the data point which gives the maximum marginal gain in solution value. Online-Greedy replaces point in the current solution set with the observed point if doing increases the objective. See Algorithm 5 in Appendix for more details.
We first learn all the matrices B, C, and V by applying the offline learning algorithm. The learning algorithm takes as input a parameter d, which is the embedding size for V. B, C. We use d = 10 for all datasets other than Instacart, Customer Dashboards, Company Retail where d 50 is used and Million Song, where = 100 is used. We perform MAP inference by running our algorithms on the learned B, C, and V. For all the following results, set 1.1 and k:
UK Retail
MovieLens
Amrizon Apparel
Onl he relphbor
Ordine neighoir
Oel 2-nelgtber
Ontins LS2
Orline LSS
Ontine LSS
Onrine Oreely
3.0-:9
Orline Greedy
Oelie Greedy
Solution
Solution
4.0-19
Solution
1.0w
8.0w
9.0=-1
2.0w
2.0:10
4.0a
17
2.0090
5.
0.0e+00
3.e400
532
1000
:500
p020 2500 3500 4002
2000 4002 s000 neto 10020 12000
20
62
20
100
Data points ainalyzed
Data points analyzed
Data points anallzeed
category 2iretproor
Millon Song
2.5e
Brwightor
59:
36-02
2.00.44
Offine
5.0e: 50
Offine
Salttion
Seluton
12--28
4.0n-0
1.0m
5.0005
326-07
38e-00
20003
3
Data points analyzed
points analyzed
Data points analyzod
Dashboands
Web Logs
Company
1.
7.0w07
Online USS
Solution
6.0
Orline Ancigbtr
2.8+200
Soluttoo
1.2e20
offine
Online Gready
3.w
1.3-200
07
1.0e200
Online L55
Online 2- 2-1elg7
5.0w2:
Site21
Creedy
2:5e:1
420
2202
1050
2000
5000
1230 Data points analyzed
Data points analyzed
points analyzed
Figure 1: Solution quality i.e. objective function value as function the number of data points analyzed for all our online algorithms and also the offline greedy algorithm. All online algorithms give comparable (or even better) performance to offline greedy using only a single pass and a small fraction of the memory.
8

---

Under review as a conference paper at ICLR 2022
MAP Inference results for variety of different datasets are provided in Figure 1. Surprisingly, the solution quality of our online algorithms compare favorably with the offline greedy algorithm the data, and tiny fraction of memory. In most cases, Online-
while using only pangle-pass,. 2-neighbor (Algorithm 3) performs better than Online-LSS (Algorithm 2) which in turn performs better than the online greedy algorithm (Algorithm 5). Strikingly, online-2-neighhor algorithm performs even better than offline greedy in many cases. Furthermore, in some cases the other online algorithms also perform better than the offline greedy algorithm.
We also perform several experiments comparing the number of determinant computations (as system- sestem-independent proxy for time) and the number of swaps (as a measure of solution consistency) of all our online algorithms. Results for determinant computations (Figure 3) and swaps (Figure 4) can found in Appendix F. We summarize the main findings here. The number of determinant computations of Online-LSSS is comparable to that of Online Greedy but the number of swaps performed is significantly smaller. Online-2-neighhor is the most time-consuming but superior performing algorithm in terms of solution quality.
We also investigate the performance our algorithms under the random stream paradigm, where we consider a random permutation of some of the datasets used earlier. Results for the solution quality (Figure 5), number of determinant computations and swaps (Figure 6) can be found in Appendix F.3. In this setting, see that Online-LSS and Online-2-neighber have nearly identical performance and are always better than Online-Greede in terms of solution quality and number of swaps.
We study the effect of varying in Online-LSS (Algorithm 2) for various values of set sizes k in Appendices F.4 and F.5. We notice that, in general, the solution quality, number determinant computations, and the number of swaps increase as a decreases (Figure 7). We also see that increases, the solution value decreases across all values of a (Figure 8). This is in accordance with our intuition that the probability of larger sets should be smaller.
7.2 ONLINE LEARNING RESULTS
Here, we compare our online learning algorithm for NDPPs with the state-of-the-art offline learning algorithm. In Figure 2, compare our online learning algorithm the offline algorithm using negative log-likelihood over time. In all cases, the offline learning algorithm uses significantly more time, usually taking between 6x 15x more time converge. Furthermore, the negative log- ligliikli from our online learning algorithm decreases significantly faster compared to the offline.
Moviel.nns
Instacart
Learring
negative log-llkelhood
600
negattve log Tog-ilkalhhod
7000
offinn
5:00
6.00
4.00
500
300
400
200
100
1000 1250
15650 20500
time
Figure 2: Results comparing online NDPP learning algorithm to the offline learning algorithm. Strikingly, our online learning algorithm shows comparable performance, while converging signifi- cantly faster in all cases. Furthermore, it also uses only single pass, while using small fraction of the space. See text for discussion.
8 CONCLUSION
In this paper, we formulate and study the streaming and online MAP inference and learning problems for Nonsymmetric Determinantal Point Processes. To the best of our knowledge, this is the first work to study these problems in these practical settings. We design new algorithms for these problems, prove theoretical guarantees for them in terms of space required, time taken, and solution quality for our algorithms, and empirically show that they perform comparably or (sometimes) even better than mate-of--he-ant offline algorithms. We believe work opens up completely new avenues for practical application of NDPPs and can lead to deployment of NDPPs in many more real-world settings.

---

Under review as a conference paper at ICLR 2022
REPRODUCIBILITY STATEMENT
For all of our theoretical results, we have provided clear explanations of all the assumptions in the main text (Sections 5, and 6) and have also provided complete proofs in the corresponding sections in the Appendix (Sections A, B, and D). For our experimental results, we have provided all details needed to reproduce our results (like the setup etc) in the main text (Section 7) and have also provided details of the datasets used in our experiments in Appendix E.
REFERENCES
A. Aho, J. Hopcroft, and J. Ullman. The Design and Analysis of Computer Algorithms. Addison- Wesley, 1974.
Nima Anari and Thuy-Duong Vuong. From Sampling to Optimization on Discrete Domains withAp- plications to Determinant Maximization. arXiv:2102.05347, 2021.
Aditya Bhaskara, Amin Karbasi, Silvio Lattanzi, and Morteza Zadimoghaddam. Online MAP Inference of Determinantal Point Processes. Advances in Neural Information Processing Systems 33 (NeurIPS 2020), 2020.
Andrew An Bian, Joachim M. Buhmann, Andreas Krause, and Sebastian Tschiatschek. Guarantees for Greedy Maximization of Non-submodular Functions with Applications. In International Conference on Machine Learning (ICML), 2017.
Alexei Borodin. Determinantal point processes. The Oxford Handbook of Random Matrix Theory.
Oxford University Press, 2009.
Brunel. Learning Signed Determinantal Point Processes through the Principal Minor Assignment Problem. In Neural Information Processing Systems (NeurIPS), 2018.
Victor-Emmanuel Brunel, Ankur Moitra, Philippe Rigollet, and John Urschel. Rates of estimation for determinantal point processes. In Conference on Learning Theory, pp. 343-345, 2017
Daqing Chen, Sai Laing Sain, and Kun Guo. Data mining for the online retail industry: case study of RFM model-basee customer segmentation using data mining. Journal of Database Marketing & Customer Strategy Management, 2012.
Wei Chen and Facz Ahmed. PaDGAN: A Generative Adversarial Network for Performance Aug- mented Diverse Designs. Journal of Mechanical Design, 143(3):031703, 2021.
Michat Derezinski and Michael W Mahoney. Determinantal point processes in randomized numerical linear algebra. Notices of the American Mathematical Society, 68( 08(1):34-45, 2021.
Miroslav Fiedler and Vlastimil Pták. Some generalizations of positive definiteness and monotonicity. Numerische Mathematik, 9(2):163-177 1966.
Mike Gartrell, Victor-Emmanuel Brunel, Elvis Dohmatob, and Syrine Krichene. Learning Non- symmetric Determinantal Point Processes. In Neural Information Processing Systems (NeurIPS), 2019.
Mike Gartrell, Insu Han, Elvis Dohmatob, Jennifer Gillenwater, and Victor-Emmanuel Brunel. Scalable Learning and MAP Inference for Nonsymmetric Determinantal Point Processes. In International Conference on Learning Representations (ICLR), 2021.
Jennifer Gillenwater, Alex Kulesza, Zelda Mariet, and Sergei Vassilvitskii. Maximizing induced car- dinality under a determinantal point process. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 6911-6920, 2018.
J Ben Hough, Manjunath Krishnapur, Yuval Peres, and Bálint Virág, Determinantal Processes and Independence. Probability surveys, 3:206-229, 2006.
Instacart. The Instacart Online Grocery Shopping Dataset, 2017. URL https:/ /www. instacart.c wwm bestacatt.com/sstatee///rrrrrere
2017. Accessed August 2021.
10

---

Under review as a conference paper at ICLR 2022
Alex Kulesza and Ben Taskar. k-DPPs: Fixed-size Determinantal Point Processes. In International Conference on Machine Learning (ICML), 2011.
Alex Kulesza and Ben Taskar. Determinantal Point Processes for Machine Learning. Foundations and Trends@ in Machine Learning. 2012.
Claire Launay, Agnès Desolneux, and Bruno Galerne. Determinantal point processes for image processing. SIAM Journal on Imaging Sciences, 14(1):304-385 348, 2021.
Paul Liu, Akshay Soni, Eun Yong Kang, Yajun Wang, and Mehul Parsana. Diversity the Go! Streaming Determinantal Point Processes under a Maximum Induced Cardinality Objective. In Proceedings of the Web Conference 202/, pp. 1363-1372, 2021.
Odile Macchi. The Coincidence Approach Stochastic Point Processes. Advances in Applied Probability, 7(1):83-122, 1975.
Brian McFee, Thierry Bertin- Mahieux, Daniel PW Ellis, and Gert RG Lanckriet. The million song dataset challenge. In Proceedings of the 21st International Conference on World Wide Web, 2012.
Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, Amin Karbasi, Jan Vondrák, and Andreas Krause. Lazier Than Lazy Greedy. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 29, 2015.
Vu Nguyen, Tam Le, Makoto Yamada, and Michael A Osborne. Optimal Transport Kernels for Sequential and Parallel Neural Architecture Search. In International Conference on Machine Learning, pp. 8084-8095. PMLR, 2021.
Laura Perez-Beltrachin and Mirella Lapata. Multi-Document Summarization with Determinantal Point Process Attention. Journal of Artificial Intelligence Research, 71:371-399, 2021.
Nicolas Perez-Nieves, Yaodong Yang, Oliver Slumbers, David H Mguni, Ying Wen, and Jun Wang. Modelling Behavioural Diversity for Learning in Open-Ended Games. In International Conference on Machine Learning, pp. 8514-8524. PMLR, 2021.
Xin Qian, Ryan A Rossi, Fan Du, Sungchul Kim, Eunyee Koh, Sana Malik, Tak Ycon Lee, and Joel Chan. ML-based Visualization Recommendation: Learning Recommend Visualizations from Data. 1rXiv:2009.12316 2020.
Mohit Sharma, F Maxwell Harper, and George Karypis. Learning from Sets of Items in Recommender Systems. ACM Transactions on Interactive Intelligent Systems (TiiS), 9(4):1-26, 2019.

---

Under review as a conference paper at ICLR 2022
A STREAMING MAP INFERENCE DETAILS
Theorem 2. For a random-order arrival stream, if is the solution output by Algorithm at the end of the stream and minn 1 where min and max denote the smallest and largest singular values of Lg among all _ [n] and |S] I 2k, then
(1-
Ellog det Ls)] 2
log(OPT)
(1- (1 log Taax - log mmin)
min
where Ls Vs Vs + BBCBs and OPT
Vs
max RC [R
det R VR BBCBB)
We will first give high-level proof sketch for our this theorem.
Proof sketch. For random-order arrival stream, the distribution of any set of consecutive n/k elements is the same as the distribution of n/ elements picked uniformly at random (without replace- ment) from [n]. If the objective function f is submodular, then this algorithm has an approximation guarantee of (1 2/e) by Mirzasoleiman et al. (2015). But neither det [L) nor log del (Ls) are submodular. Instead, Gartrell al. (2021) [Equation 45] showed that log det (et(Lg) is "close" to sub- modular when min > where this closeness is measured using a parameter known as "submodularity ratio" (Bian al., 2017). Using this parameter, we can prove guarantee for our algorithm.
We will now provide complete proof.
Proof. As described in Algorithm I, we will use So, Si,..., Sy to denote the solution sets maintained by the algorithm, where S; represents the solution set of size In particular, we have that S, = S U { where s; arg ja f(S U {i}) and B; denotes the i'th partition i.e. B; == (1-1)- h + ((-1)mm + 2,.....
im
For E [6], let use X; [B; n (S. S;-1) + 0] to denote the event that there is at least one element of the optimal solution which has not already been picked by the algorithm in the batch B; and X; S, \ S.-1l. Then,
Pr[X,] 1 - Pr(XF)
X;
A
A
= =1 - (1
)1
(1
A B
21
2
\
k
Here use the facts: ex 2 1+ for all x E R. 1 2 is concave a function of X, and À [0, k).
For any element E [m] and set C [n]. let us use f(s S) = f(S {s}) - f(S) to denote the marginal gain in f obtained by adding the element to the set S. For any round E [k]], we then have that (S.) f(S-11) = f(x S:-1).
Note that
EweoPr,s,_ f(w Si-1)
[s[ S5-1) X,)
[PPT 8
12

---

Under review as a conference paper at ICLR 2022
This happens due to the fact that conditioned on X,, every element in S. \ S is equally likely to
be present in B, and the algorithm picks 8; such that f(; 5;-1) 2 f( S,-1) for all s E B,
[x]( 5 | S--1]
[x 1 1; Pr|
+ [0] [S--) S;-1, Pr[x;]
2 [s;
[(--1) X; Pr[X;]
A;
(1-1
Ewes. \SS-,, [(w] S
2 k
1
e
S, S
X
1
1
E
flwl S
S.
\ \S-11
e
WES.
(1
1
Σ
1(w1S:1)
WES. \8:-1
1
7 (f(S,-1 U.S.) f(S.-1))
8
1
7 (OPT ,(S-1))
k
For the last 2 inequalities, we use the fact that f(S) log det Ls) is monotone non-decreasing and has submodularity ratio of 7 2
jog dmaa log aiin
1) when min > 1 (Gartrell et al., 2021)[Eqq. 45].
Taking expectation over all random draws of 5 we get
[sx S:-1)] 2 1 1 ))
7 k
(OPT- (()()))))))
Combining the above equation with [(si|Si = s(S:) ((Si-i), we have
B[S(S.)) E((((--)) (1- 1 2 k
(OPT - -(((S--)))
Next we have
-OOPT- ((PT) + (OPT- (((T-E((()-)))) 2 (1 (1-1) 1) 7 (OPT E[f(S,-))))
1
e)
Re-orgamizing the above equation, we obtain
OPT O[(SE(((.)] - (1- (1-2) x -PTT-E)((S-D)))
Applying the above equation recursively is times,
7
OP]-E(((SA] < 1 - 1
-
(OPT - ((((s)
T
k
1
OPT
T
where the last step follows from f(o) 0.
Re-organized the terms again, we have
1 ( 1 (1-2)= 2)) OPT
E[((S)] 2
1
-1-e (1-))) OPT
13

---

Under review as a conference paper at ICLR 2022
When substitute log -1 -1)² log mmnn
we get final inequality:
B][(S}]
OPT
(1-2) 2- log mmax -log mminn)
min
Theorem 3. For any length-n stream (1), bi)...., (Bas bn) where (Ve, bi) E R vte [n], the
worst-case update time of Algorithm I is ( (k, d)) where Tace (k, d) is the time taken to compute f(S) d V + B C for |5| k. The total time taken is Onn- Taee (k, d)) and the space used at any time step is O(k² + )²).
Proof. For any partieular data-point (ve; be). Algorithm 1 needs to compute f(S,-1 (t)), which takes at most Taet(k (k, d) time. All the other comparison and update steps are much faster and so the worst-case update time is (Tdet (ks, d)). The space needed compute det V V + +B is at most O(k++d where S = 1 Utt}. The algorithm also needs to store S and ((S,-1U(s;))
but all of these are dominated by O + dd) space needed to compute the determinant.
B ONLINE MAP INFERENCE DETAILS
Theorem 5. For any length-n stream (v), bi).... (Un, bn) where (Ve, b.) E IRd I2 V [n], the worst case update time of Algorithm 2 is (T (ki, d) (o)) where Taor (k, d) is the time taken ) for |S| = k. Furthermore, the amortized update time is O(Tae d) (k+ 1s (oog)( )) and the space used at any time step is most O(k? + af d (A)).
to compute fSS) det(V, +B CB)
Proof. For every iteration of the while loop in line 4: It takes at most Taet d) time for checking the first if condition (lines 5-6). The argmaxjes S(S U (1) \ (i) step takes at most k Tacr (ki, d) time. The while loop in line 12 takes time at most [S| [T] TTaes (k, d) for every instance of an increase in f().. Note that f(S) can increase at most log,, (A) times since the value of f(S) cannot exceed OPTR. Therefore, the update time of Algorithm 2 is at most Taet (ki, d) + k Taee (k, d) log, (A) (18)-17)) Tatn (k, d)) S Tast (ki, d). (k + 1 + k log2 (A)) since |S] S k and [T] S loga (A). Notice that the cardinality of T can increase by 1 only when the value of f(S) increases at least by factor of a and so [T| S log, (A).
During any time step f, the algorithm needs to store the indices in S, T and the corresponding matrices Vs, Bs, Vr, Br. Since |S| < k. [T] < log,, (A) and takes words store every v; and b,, we need at most k ++ (A) + 2dk + 2d log,, (A) words to store all these in memory. The space needed to compute dVs s Vs + B3 CBs)) is at most O + d²). We compute such determinants one after the other in our algorithm. So the algorithm only needs space for such computation during it's run. Therefore, the space required by Algorithm 2 O + d² + dolog, (A)).
Theorem 7. For any length-n stream (vi, "i,)),,,,(,,, bn) where (ve, b.) E Rd x RRV [m] the worst case update time of Algorithm is O (k, d) k2 log log3(A)) where Taes (k, d) is the The amortized update time
time taken to compute [(S) = (es V B3 CB for |S|
O (k, (k2 122 k2 log" )) and the space used any time step is at most O(k2 d² n
d logg(()))
Proof. It takes at most (k, time for lines 5-6 (same as in LSS). The arg max (fSSUr (t) \ time. The while loop in line 18 takes time most |s|a 17|22 Taet (k: d) for every instance of an increase in S(S). Similar to LSS, S(S) can increase at most by factor of log, (A) since the value of f(S) cannot exceed ÓPT.. Therefore, the update time of Algorithm 3 is at most 1og (A))
\ fa, b))) step takes most 222 Tast (ke, d)
Taa (Is, -22 (ks +og. (A) (1s)2 (I] Taai(k: d)) S Tact (k, dd- dd)-(k2
since [S| < l: and [T| loga (A).
14

---

Under review as a conference paper at ICLR 2022
Algorithm 5 ONLINE-GREEDY, Online Greedy MAP Inference for NDPPs
1: Input: A stream data points {(V1, b1), (12, bz)..... (Un, bn)]
2: Output: A solution set S of cardinality k at the end of the stream.
3: S 5
4: while new data (vt, b,) arrives in stream at time do
5: if |S| < and f (S U {t)) + 0 then
6:
S (1)
7: else
8:
arg jss f(S (i) ir ( (i)) f(S) then
9:
S Su (r)
11:
return S
Although Algorithm 3 executes more number of determinant computations than Algorithm 2, all of them are done sequentially and only the maximum value among all the previously computed values in any specific iteration needs be stored in memory. Therefore, the space needed is (nearly) the same for both the algorithms.
C HARD INSTANCE FOR ONLINE MAP INFERENCE OF NDPPs
We will now give a high-level description of a hard instance for online MAP inference of NDPPs (this is inspired by (Anari & Vuong, 2021, Example 5)) Suppose have total of 2d items consisting of pairs of complementary items like modem-router printer-ink ink cartridge, pencil-erasee (1, 1 2, 2 ,.... .d. d²) denote them. Any item is independent of every item other than it's complement i Individually, Pr[[t)] Pr[{;')] = O And Pr[(i, { x with x; > 0 for any # j. Suppose any of our online algorithms are where E [d] is some arbitrary item and the algorithm needs pick items i.e. k 2. Then, OPT whereas all of online algorithms (Online LSS, Online 2 2-neighbor, Online (reine-Greedy) will fail to output a valid solution.
Outline:
Let
for all E [d]. Also, we have Pr[{i.j]] given the sequence {1, 2, ...., d. r_
Details: Let 21 < x2
< Id. Suppose
11
0
T22
C
0
Fdd 0
C' e 2ddx2 is a symmeric (i.e. = TT block diagonal matrix where the blocks are the
form
F; -i 0
Suppose we have total of 2d items consisting of d pairs of complementary items.
We use (1, 15 2f........ d, ) } to denote them. Let v; U/ 0 V [d] and b e1, bye e2 ....... by = Ezd where e1, e e2s are the standard unit vectors in 2d ie. B Iza-
For pair of complementary items S {i, 2f. Without loss of generality, consider S = (1, 19). Then we can compute B CB3 as follows:
Bg CBs
[ei
E2]
C
[ei
22]
Ø1
0
0
0
Jei
ea]
0
0
0
0
0
15

---

Under review as a conference paper at ICLR 2022
In this case, have f(5) = =
For any pair of non-complementary items S
{[1, i2) where the indices are distinct, f(5) =
Without loss of generality, we consider S [1, Then,
Bş CBs = [ei
e3]
C
[e
ea]
0
31
0
0
lei
eal
0
x2
0
0
0
And so, we have that f(S) = 0.
D LEARNING DETAILS
Our approximate objective
(V. B,C) = log det (Vs, Vs. + Bs, CBs.) Z(Vs.. Bs. C) R(Vs. Bs.)
(5)
We will now provide a derivation of i.e. VV, the Let us first look at the gradient the first term
Vs, det V.S Vs. + +B, CBss) 2Vs, (V3, Vs. + Bs, CB.)
Bs, log det s. Vs + BB, CBs)) = 2CBs (Vs, s. Vs. B5. CBs.)
Vc log det (Vs. Vs. + Bs, CBs.) = Bs, (... Vs. + B CBs.) Bs.
Now, we consider the gradient of ( Bs. C)2 which consists of three parts:
V Vs, Z, v Bs, Z, VcZ. X =I V3. [I + Vs. V Vs, Note that
Z = log det (Ia + Vs, Vs.) + log det (C-1+ + Bs, V Vs.
+ log det(C))
We refer the reader to (Gartrell et al., 2021, Eqn 19) for a derivation of the above form Z. Then,
Vvs, Z = 2 La + Vs, V3.))=
-XB ((C -X Bs, - + BB,,
Bs, Z= XBJ. ((C-1 + Bs, 3B) + (C-T, + Bs, BB,,
(7)
Vc C- -C-T(C-1 + Bs, XB
(8)
Since we only have one subset at a time step, R(Vs, Bs.) = a Eies, ||0,112 + 3EEs, bill
Therefore, Vvs, R 2o Vs., V Bs, R = 2
We can then substitute VZ from Equations 6,7,8 in the following equations to get the gradient required for updates Vih.:
Vvs v. 2Vs, (V5, Vs, CBs.) Vvs 2 -
(9)
V Bs, v. 2CBs, (V.. S. Vs, + +B, CBs.) V Z -23Bs,
(10)
Vot. Bs, (Vs, Vs, BJ, CBs.) B5, Vc%
(11)
Theorem 9. Algorithm 4 uses 2 + d²) space" $ Also, the update time for single subset S
arriving at time t in the stream is O d where d' is the size of the largest in the stream.
NNte that the Ond + d)) required to store the matrices V. B, and C are omitted for simplicity (since these all algorithms).
16

---

Under review as a conference paper at ICLR 2022
Proof. To compute V.. Z, it takes space most Odd² + dd) as it involves matrix multiplications and inversions of matrices of sizes d' x d, d d, d' x d'. Similarly for VB, Z, vcZ. Computing the gradient of the first term in Equation 4 requires inversion of a d' x d' matrix, which takes at most (dd)) space. And the gradient of the sum of norms term in Equation 4 takes at most ((d' space to compute.
As described in the proof of the previous lemma, we will need to compute matrix multiplications and inversions of size at most d x d, d' x d', and d' d. All of these can be done in time Oid + d'')
Sm. } of length-m, Algorithm 4 learns an NDPP Theorem 10. Given a stream of subsets (S1, ,
kernel L V V + CB of d using only single-pass passspassssss over the stream in Omdd md3) time where = max, (|S(l) & n. Note V B E Rdx= C E Rddd and d & n.
In comparison, the offline learning algorithm (Gartrell et al., 2021) takes at most Tmax passes over the entire data (m subsets), and since all m subsets are stored in memory (offline, non- non-streaming), they use all available data at once to update the embedding matrices of the NDPP model. Notice that log det ( S, Vs, + B3, CBs,) in Eq. is computed for every subset, thus taking ((md") time for all m sets the stream where d' is the size of the largest set in the stream. Furthermore, log det (V VVVV V B' CB+ + 1) (2nd term in Eq. 3) takes O(nd²) time where n < m, and this can be computed a constant number of times with respect to m. Similarly for the regularization term R(V.B).
E DATASETS
We use several real-world datasets composed of sets (or baskets) of items from some ground set of items.
This an online retail dataset consisting of sets of items all purchased together by users (in a single transaction) (Chen et al., 2012). There are 19,762 transactions (sets of items purchased together) that consist of 3,941 items. Transactions with more than 100 items are discarded.
UK Retail:
MovieLens: This dataset contains sets of movies that users watched (Sharma et al., 2019).
There are 29,516 sets consisting of 12,549 movies.
Amazon Apparel: This dataset consists of 14,970 registries (sets) from the apparel category of the Amazon Baby Registries dataset, which is public dataset that has been used in prior work on NDPPs (Gartrell et al., 2021; 2019). These apparel registries are drawn from 100 items in the apparel category.
Amazon 3-category: We also use a dataset composed of the apparel, diaper, and feeding categories from Amazon Baby Registries, which are the most popular categories, giving us 31,218 registries made up of 300 items (Gartrell et al., 2019).
This dataset represents sets of items purchased by users on Instacart (Instacart, 2017). Sets with more than 100 items are ignored. This gives 3.2 million total item-sets from 49,677 unique items.
Instacart:
Million Song: This is dataset of song playlists put together by users where every playlist is a set (basket) of songs played by Echo Nest users (McFee et al., 2012). Playlists with more than 150 songs are discarded. This gives 968,674 playlists from 371,410 songs.
Customer Dashboards: This dataset consists of dashboards or baskets of visualizations created by users (Qian al., 2020). Each dashboard represents set of visualizations selected by a user. There are 63436 dashboards (baskets/sets) consisting of 1206 visualizations.
Web Logs: This dataset consists of sets of webpages (baskets) that were all visited in the same session. There are 2.8 million baskets (sets of webpages) drawn from 2 million webpages.
Company Retail: This dataset contains the set of items viewed (or purchased) by user in a given session. Sets (baskets) with more than 100 items are discarded. This results in 2.5 million baskets consisting of 107,349 items.
The last two datasets are proprietary company data.
17

---

Under review as a conference paper at ICLR 2022
F ADDITIONAL EXPERIMENTAL RESULTS
F.1 NUMBER OF DETERMINANT COMPUTATIONS
We perform several experiments comparing the number of determinant computations (as system- independent proxy for time) of all our online algorithms. We do not compare with offline greedy here because that algorithm doesn't explicitly compute all the determinants. Results comparing the number of determinant computations a function of the number of data points analyzed for variety of datasets are provided in Figure 3. Daline-2-neighhee requires the most number determinant computations but also gives the best results in terms of solution value. Online-LSS and Online- use very similar number of determinant computations.
Online-Greedy Greedy
Appare!
200200
Online 2-negytee
520032
O18ie 3-regghoo
14002
On chosr
Online LSG online Grendy
520032
016ine Greedy
On8re
12003
On LSS
Online l'relly
125350
8003
100000
320005
75300
50200
200030
4002
0002
1:0000
1000
2300
Data points analyzed
Data points analyzed
Data points analyzed
1/
Song
Amazon 3-category
instacart
2-10 ghito
50032
Ghiin LSS
Orline ne ghoor
3200200
Onlinc LSS
Orline neighorr
1.2
Online Croudy
40002
Cready
3000200
Online Greedy
2500300
compun
0.8
0.8
20032
1500300
1000300
30002
0.
500200
0.0
50000
points analyzed
Data analyzed
Dala points analyzed
Customer Das Dashboards
Web
Company Rotail
O1iin nine ghoor
200300
Orline 2 nncghur
140003
Onlicc 2 neightor
0
Onirnc L:5
Oréne Groady
Orline Grealy
Online LSS
120002
Online Greedy
Online LSS
250300
100200
60003
50000
40003
20003
2000
2000
points analyzed
points analyzed
points analyzed
Figure 3: Results comparing the number of determinant computations function of the number of data points analyzed for all our online algorithms. Online-2- --neghbbrr requires the most number of determinant computations but also gives the best results in terms of solution value. Online-LSS and Online-Greedy use very similar number of determinant computations.
18

---

Under review as a conference paper at ICLR 2022
F.2 NUMBER OF SWAPS
Results comparing the number of swaps (as measure of solution consistency) of all our online algorithms can be found in Figure Online-Greedy has the most number of swaps and therefore the least consistent solution set. On most datasets, the number of swaps by Online-2-neighbor is very similar Online-LSS.
MovieLans
Amazoon Apparel
50
40
Owline 1S5
Online Grousy
42
Swaps
Swaps
2 reiseor
10
Online 2 rely/bo /oo
Orline LS5
Online LS5
Online Greedy
Online Gready
500
1063 1500 2320 2000 3020 3500 4020 Data points analyzed
2000
4002
6220
2000
10500
12003
20
40
60
80
100
Data points anelyzed
Data points anelyzed
Millin Sang
Amazon 3-rategory
instacart
32
Swaps
Swaps
Swaps
46-
Celine 2enigher
Celine LBs
On
Online
0
Celine Gready
Data points analyzed
100
150
203
160
10003
Data points analyzed
22003
3010o
10003
50200
10000115000 20000000000000000000000000000000
Data points analyzed
Customer Dashboards
Web Logs
Company Retall
25
Swaps
Swaps
16-
2e glos
6-
On
1000
1020
Data points analyzed
Data points analyzed
Data points analyzed
Figure 4: Results comparing the number of swaps of all online algorithms. Online-Grecde does the most number swaps and therefore has the least consistent solution set. On most datasets, the number of swaps by Online-2-neighha is very similar Online-LSSS.
F.3 RANDOM STREAMS
We also investigate our algorithms under the random stream paradigm. For this setting, we use some of the previous real-world datasets, and randomly permute the order in which the data appears in the stream. We this 100 times and report the average of solution values Figure 5 and the average of number of determinant computations and swaps in Figure 6. We observe that Online-2- neighbor and Online-LSS give very similar performance in this regime and they are always better than Online-Greedy.
F.4 ABLATION STUDY VARYING
To study the effect of in Online-LSS (Algorithm 2), we vary E {0.05, 0.3, 0.5} and analyze the value of the obtained solutions, number of determinant computations, and number of swaps. We notice that, in general, the solution quality, number of determinant computations, and the number of swaps increase as decreases. Results are provided in Figure 7.
19

---

Under review as a conference paper at ICLR 2022
Amazon
Amazon
Oréioo 2eeiyfoo
10a-10
Ontinu LS0
Ohilnn Grandy
80o-11
Saluton
Crira 2-nighier
E0e-11
Gnire LSS
4.b011
54a-10
24b-11
23w-10
03e-38
Data
Data analyzed
Figure 5: Solution quality function of the number of data points analyzed in the random stream paradigm. Online-2-nen 2nniie---neihhbor and Online-LSS give very similar performance in this setting and they are always better than Online- Greedy.
Amazon 3-category
3-oategory
50000
30
Del. computeltone
Onlins Gready
25
42600
22000
Online 2-rekhowr LSS
Gmodly
Data points analyzad
Dala points analyzed
Figure 6: Number determinant computations and swaps as a function of the number of data points analyzed in the random stream setting. Online-2-Neighte needs more determinant computations than Online-LSS but has very similar number of swaps in this setting. Note that
UK Ratail
UK Retail
Rotall
EG2
Soluton
2.8
Swaps
2.000
2.5
1000
3.0
500
1000
3587
points analyzed
2006 2538 1000 2500 4300
2010 3500 analyned
2000 2008 2000 analyred
Amazon Appanel Reg.
Amazon Apparel Reg.
1400
Solution
Swapp
206
Data points analyzed
46
6
103
20
antlyccd
60
33
108
20
points analyced
50
30
358
Amazon Baby Reg.
Amazon Baby Reg.
20
Soluton
Seaps
20
2000
Ince-
1.0 Data points analyzed
358
200
250
30
200 Dalaa points analyzed
1.30
1550
250
300
50
100
15:3
200
300
300
Data points anallppd
Figure 7: Performance of Online-LSSS varying for & Solution quality, number of determinant computations, and number of swaps seem to increase with decreasing c.
20

---

Under review as a conference paper at ICLR 2022
F.5 ABLATION STUDY VARYING SET SIZE & AND
In this set of experiments on the Amazon-Apparel dataset using Online-LSS, we study the choice of set size & and the solution quality, number of determinant computations, and number of swaps while fixing all other settings to be same as those used previously in Figure 5. We can see that as increases, the solution value decreases across all values of e. This accordance with our intuition that the probability of larger sets should be smaller. In general, the number of determinant computations and swaps increases for increasing i across different values
10
16
16
13
-3
20100
3000
15
14
12
12
Swet
-12
13
11
144
100k
1.2mh
130m
1:440:
1006
12
11
6/
8.5
10
1.mm
620
02
35
03
(a) Solution
(b) # det computations
(c) # swaps
Comparing the effect of set size & and on the solution, number of determinant computa- tions, and number of swaps for ONLINE--LSS.
Figure 8:
F.6 ONLINE LEARNING RESULTS
Figure shows that the heat maps of kernel matrices learned by our online learning algorithm and the offline learning algorithm quite similar. We use the Amazon Apparel dataset for this set of experiments.
On NDFP Model Leanting
O1 NDPP Made Leanting
(a) d 10
(b) 30
Leaming
(c) 10
(d) 30
Figure 9: Heatmaps of the kernel matrices learned by our online algorithm (top) looks very similar to the ones learned offline using all data (bottom).
21


Reviews:
[{"review_id": "tRjOnHfVDHz", "reviewer": "Reviewer_FZX8", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nThe 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_paper": "This paper introduces the streaming and online MAP inference and learning problems for NDPPs.\n- For streaming MAP inference, an algorithm is proposed with total time linear in $n$ and memory that is constant in $n$;\n- For online MAP inference, several algorithms are proposed such that at any point in time a valid solution is maintained;\n- For online learning algorithm, a single pass algorithm is proposed with memory that is constant in $m$;\n- Experiments are conducted to show that these streaming and online algorithms achieves comparable performance to state-of-the-art offline algorithms.", "summary_of_the_review": "Overall I think the problems that this paper studies are interesting and the proposed algorithm are effective.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "sKfvH-miYj3", "reviewer": "Reviewer_NfZW", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "##  Strengths\n- 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).\n- Novelty: as the authors mention, this work provides the first analysis of MAP-inference and learning for the streaming settings of NDPPs.\n- 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.\n\n## Weaknesses\n- 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.\n- The first streaming algorithm (Algorithm 1) is quite simplistic, and is more interesting as a baseline rather than as a contribution in of itself.\n- 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. \n\n## Questions / comments\n- 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?\n- 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.\n- 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?\n- The derivation of the gradient updates for the online algorithm can be removed from the main paper.\n- 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).\n- 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.\n- Can you clarify the experimental conditions used for the offline learning algorithm (batch size, etc.)?\n\n[1] Online MAP Inference of Determinantal Point Processes, Bhaskara et al., 2020", "summary_of_the_paper": "This paper introduces MAP-inference and learning algorithms for nonsymmetric determinantal point processes (NDPPs) in the streaming and online settings. \n\nThis 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.", "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.\n\nMy 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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "fevVCOB6bEr", "reviewer": "Reviewer_9kPN", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n- 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.\n- 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.\n- The proposed online learning algorithm (Alg. 3) has theoretical guarantees for time and space complexity.\n- The paper is reasonably well written and easy to follow.\n\nWeaknesses:\n- 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.\n- 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. \n", "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.\n", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "-EmM2xm8cfz", "reviewer": "Reviewer_J9Ht", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n- The paper studies a new problem of NDPPs under the online setting that has not been covered before. \n- The authors properly apply the prior online algorithm for greedy submodular maximization to the NDPPs\n- Experimental results are convincing that the effectiveness of the proposed online inference and learning algorithms for NDPPs\n\nWeaknesses:\n- 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.\n- Moreover, some algorithms are already proposed in prior works, but there is no reference. For example, Algorithm 2 (Online-LSS) was proposed in [1].\n\n  [1] Bhaskara et al., Online MAP Inference of Determinantal Point Processes, NeurIPS, 2019\n- 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.\n- 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? \n- 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?\n\nMinor comments:\n\n  - A comma is missing in the fourth line of the second paragraph on page 1.\n  - Please edit “state-of-the-art” in the second paragraph on page 2.\n  - Please edit “are minimize” -> “are minimizing” in the second last row on page 3.\n  - It would be good to place Algorithm 4 in the main manuscript.\n  - In Theorem 5 and 7, please edit $f(S) = \\det( V_S^\\top V_S + B_S^\\top C B_S)$\n  - What is $j_{\\mathrm{\\max}}$ in line 9 in Algorithm 1?\n", "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.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

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