Year: 2021

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 singlepass 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.

heading: 1 INTRODUCTION
text: Determinantal Point Processes (DPPs) were first introduced in the context of quantum mechanics (Macchi, 1975) and have subsequently been extensively studied with applications in 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 in 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-Beltrachini & Lapata, 2021), image processing (Launay et al., 2021), and learning in games (Perez-Nieves et al., 2021).
A DPP is a 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 to that subset in the kernel. Until very recently, most prior work on 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 et al., 2019; Brunel, 2018). 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 a product recommendation system would want the system to increase the probability of suggesting a router if a customer adds a modem to a shopping cart.
State-of-the-art algorithms for learning and inference on NDPPs (Gartrell et al., 2021) require storing the full data in 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 of users instantaneously.
This work makes the following contributions:
Streaming and Online Inference: We formulate streaming and online versions of maximum a posteriori (MAP) inference on fixed-size NDPPs and provide algorithms for solving these problems. In the streaming setting, 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 (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 a 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 a single pass over the data and using a fraction of the memory used by the offline algorithm.
Online Learning: 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-likelihood) to the state-of-the-art offline learning algorithm, while converging significantly faster in all cases (Figure 2). This is notable, since our algorithm uses only a single pass over the data, while using a tiny fraction of the memory.

heading: 2 RELATED WORK
text: 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.
A 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 kO(k) 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 in 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.

heading: 3 PRELIMINARIES
text: 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, 2, . . . , n}. A matrix M is said to be skew-symmetric if M = −M> where > is used to represent matrix transposition. A DPP is a probability distribution on all subsets of [n] characterized by a matrix L ∈ Rn×n. The probability of sampling any subset S ⊆ [n] i.e. Pr[S] ∝ det(LS) where LS is the submatrix of L
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 ∑ S⊆[n] det(LS) = det(L + In) (Kulesza & Taskar, 2012, Theorem 2.1). Therefore, Pr[S] = det(LS)
det(L+In) . For the DPP
corresponding to L to be a valid probability distribution, we need det(LS) ≥ 0 for all S ⊆ [n] since Pr[S] ≥ 0 for all S ⊆ [n]. Matrices which satisfy this property are known as P0-matrices (Fiedler & Pták, 1966). For any symmetric matrix L, det(LS) ≥ 0 for all S ⊆ [n] if and only if L is positive semi-definite (PSD) i.e. xTLx ≥ 0 for all x ∈ Rn. Therefore, all symmetric matrices which correspond to valid DPPs are PSD. But there are P0-matrices which are not necessarily symmetric
(or even positive semi-definite). For example, L = [
1 1 −1 1
] is a nonsymmetric P0 matrix.
Any matrix L can be uniquely written as the sum of a symmetric and skew-symmetric matrix: L = (L + L>)/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 skewsymmetric part as encoding positive correlations. Gartrell et al. (2019) proposed a decomposition which covers the set of all nonsymmetric PSD matrices (a subset of P0 matrices) which allowed them to provide a 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 >V + B>CB. Although both these decompositions only cover a subset of P0 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 = V >V + B>CB, we have V ,B ∈ Rd×n,C ∈ Rd×d and C is skewsymmetric. Here we can think of the items having having a latent low-dimensional representation (vi, bi) where vi, bi ∈ Rd. Intuitively, a low-dimensional representation (when compared to n) is sufficient for representing items because any particular item only interacts with a small number of other items in real-world datasets, as evidenced by the fact that the maximum basket size encountered in real-world data is much smaller than n.

heading: 4 STREAMING MAP INFERENCE
text: 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.

heading: 4.1 STREAMING MAP INFERENCE PROBLEM
text: We study the MAP Inference problem in low-rank NDPPs in the streaming setting where we see columns of a 2d × n matrix in order (column-arrival model). Given some fixed skew-symmetric matrix C ∈ Rd×d, consider a stream of 2d-dimensional vectors (which can be viewed as pairs of d-dimensional vectors) arriving in order:
(v1, b2), (v2, b2), . . . , (vn, bn) where vt, bt ∈ Rd,∀ t ∈ [n]
The main goal in the streaming setting is to output the maximum likelihood subset S ⊆ [n] of cardinality k at the end of the stream assuming that S is drawn from the NDPP characterized by L = V >V + B>CB i.e.
S = argmax S⊆[n],|S|=k det(LS) = argmax S⊆[n],|S|=k
det(V >S VS + B > SCBS) (1)
For any S ⊆ [n],VS ∈ Rd×|S| is the matrix whose each column corresponds to {vi, i ∈ S}. Similarly, BS ∈ Rd×|S| is the matrix whose columns correspond to {bi, i ∈ 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 as k-DPPs (Kulesza & Taskar, 2011).
Usually, designing a streaming algorithm can be viewed as a dynamic data-structure design problem. We want to 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-RAM model, and use number of words* to measure it. *In word-RAM, we usually assume each word is O(logn) bits.
Algorithm 1 Streaming Partition Greedy MAP Inference for low-rank NDPPs 1: Input: Length of the stream n and a stream of data points {(v1, b1), (v2, b2), . . . , (vn, bn)} 2: Output: A solution set S of cardinality k at the end of the stream. 3: S0 ← ∅, s0 ← ∅ 4: while new data (vt, bt) arrives in stream at time t do 5: i← d tkn e 6: if f(Si−1 ∪ {t}) > f(Si−1 ∪ {si}) then 7: si ← t 8: if t is a multiple of nk then 9: Si ← Si−1 ∪ si 10: si ← ∅ 11: return Sk
• Update time: time to update our data-structure whenever we see a new arriving data point.
• Total time: total time taken to process the stream.
Definition 1. Given three matrices V ∈ Rd×k,B ∈ Rd×k and C ∈ Rd×d, let Tdet(k, d) denote the running time of computing
det(V >V + B>CB).
Note that Tdet(k, d) = 2Tmat(d, k, d) + Tmat(d, d, k) + Tmat(k, k, k) where Tmat(a, b, c) is the time required to multiply two matrices of dimensions a× b and b× c. We have the last Tmat(k, k, k) term because computing the determinant of a k × k matrix can be done (essentially) in the same time as computing the product of two matrices of dimension k × k (Aho et al., 1974, Theorem 6.6).
We will now describe a streaming algorithm for MAP inference in NDPPs, which we call the "Streaming Partition Greedy" algorithm.

heading: 4.2 STREAMING PARTITION GREEDY
text: Outline of Algorithm 1: Our algorithm picks the first element of the solution greedily from the first seen nk elements, the second element from the next sequence of n k elements and so on. As described in Algorithm 1, let us use S0, S1, . . . , Sk to denote the solution sets maintained by the algorithm, where Si represents the solution set of size i. In particular, we have that Si = Si−1 ∪ {si} where si = arg maxj∈Pi f(S ∪ {j}) and Pi denotes the i’th partition of the data i.e. Pi := { (i−1)·nk + 1, (i−1)·n k + 2, . . . , i·n k }.
(v1, b1), (v2, b2), ..., (vn/k, bn/k)︸ ︷︷ ︸ P1 , . . . , (vn−(n/k)+1, bn−(n/k)+1), ..., (vn, bn)︸ ︷︷ ︸ Pk
(2)
Theorem 2. For a random-order arrival stream, if S is the solution output by Algorithm 1 at the end of the stream and σmin > 1 where σmin and σmax denote the smallest and largest singular values of LS among all S ⊆ [n] and |S| ≤ 2k, then
E[log det(LS)] ≥ ( 1− 1
σ (1− 1e )·(2 log σmax−log σmin) min
) log(OPT)
where LS = V >S VS + B > SCBS and OPT = max R⊆[n], |R|=k det(V >R VR + B > RCBR).
We defer the proofs of the above and the following theorem to Appendix A.
Theorem 3. For any length-n stream (v1, b1), . . . , (vn, bn) where (vt, bt) ∈ Rd×Rd ∀ t ∈ [n], the worst-case update time of Algorithm 1 is O(Tdet(k, d)) where Tdet(k, d) is the time taken to compute f(S) = det(V >S V + B > SCB) for |S| = k. The total time taken is O(n · Tdet(k, d)) and the space used at any time step is O(k2 + d2).
Algorithm 2 ONLINE-LSS: Online MAP Inference for low-rank NDPPs with Stash. 1: Input: A stream of data points {(v1, b1), (v2, b2), . . . , (vn, bn)}, and a constant α ≥ 1 2: Output: A solution set S of cardinality k at the end of the stream. 3: S, T ← ∅ 4: while new data point (vt, bt) arrives in stream at time t do 5: if |S| < k and f (S ∪ {t}) 6= 0 then 6: S ← S ∪ {t} 7: else 8: i← arg maxj∈S f(S ∪ {t} \ {j}) 9: if f (S ∪ {t} \ {i}) > α · f(S) then 10: S ← S ∪ {t} \ {i} 11: T ← T ∪ {i} 12: while ∃ a ∈ S, b ∈ T : f (S ∪ {b} \ {a}) > α · f(S) do 13: S ← S ∪ {b} \ {a} 14: T ← T ∪ {a} \ {b} 15: return S

heading: 5 ONLINE MAP INFERENCE FOR NDPPS
text: We now consider the online MAP inference problem for NDPPs, which is natural in settings where data is generated on the fly. In addition to the constraints of the streaming setting (Section 4.1), our online setting requires us to maintain a valid solution at every time step. In this section, we provide two algorithms for solving this problem.

heading: 5.1 ONLINE LOCAL SEARCH WITH A STASH
text: Outline of Algorithm 2: 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 t ∈ [n] (after t ≥ k), our algorithm maintains a candidate solution subset of indices S of cardinality k from the data seen so far i.e. S ⊆ [t] s.t. |S| = k in a streaming fashion. Additionally, it also maintains two matrices VS ,BS ∈ Rd×|S| where the columns of VS are {vi, i ∈ S} and the columns of BS are {bi, i ∈ S}. Whenever the algorithm sees a new data point (vt, bt), it replaces an existing index from S with the newly arrived index if doing so increases f(S) at-least by a factor of α ≥ 1 where α is a parameter to be chosen (we can think of α being 2 for understanding the algorithm). Instead of just deleting the index replaced from S, it is stored in an auxiliary set T called the “stash" (and also maintains corresponding matrices VT ,BT ), which the algorithm then uses to performs a local search over to find a locally optimal solution.
We now define a data-dependent parameter ∆ 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| = k that can be achieved in the stream without any swaps be valnz i.e. till S reaches a size k, any index seen is added to S if f(S) remains nonzero even after adding it. Let us define ∆ := OPTkvalnz where OPTk = maxS⊆[n],|S|=k det(V > S VS + B>S CBS).
Theorem 5. For any length-n stream (v1, b1), . . . , (vn, bn) where (vt, bt) ∈ Rd×Rd ∀ t ∈ [n], the worst case update time of Algorithm 2 is O(Tdet(k, d) · k log2(∆)) where Tdet(k, d) is the time taken to compute f(S) = det(V >S V + B > SCB) for |S| = k. Furthermore, the amortized update time is O(Tdet(k, d) ·(k+ k log 2(∆) n )) and the space used at any time step is at mostO(k 2 +d2 +d logα(∆)).
We defer the proof for the above theorem and all following theorems in this section to Appendix B.

heading: 5.2 ONLINE 2-NEIGHBORHOOD LOCAL SEARCH ALGORITHM WITH A STASH
text: 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.
Algorithm 3 ONLINE-2-NEIGHBOR: Local Search over 2-neighborhoods with Stash for Online MAP Inference of low-rank NDPPs.
1: Input: A stream of data points {(v1, b1), (v2, b2), . . . , (vn, bn)}, and a constant α ≥ 1 2: Output: A solution set S of cardinality k at the end of the stream. 3: S, T ← ∅ 4: while new data (vt, bt) arrives in stream at time t do 5: if |S| < k and f (S ∪ {t}) 6= 0 then 6: S ← S ∪ {t} 7: else 8: {i, j} ← arg maxa,b∈S (f(S ∪ {t} \ {a}), f(S ∪ {t− 1, t} \ {a, b})) 9: fmax ← maxa,b∈S (f(S ∪ {t} \ {a}), f(S ∪ {t− 1, t} \ {a, b}))
10: if fmax > α · f(S) then 11: if two items are chosen to be replaced: then 12: S ← S ∪ {t− 1, t} \ {i, j} 13: T ← T ∪ {i, j} 14: else 15: S ← S ∪ {t} \ {i} 16: T ← T ∪ {i} 17: while ∃ a, b ∈ S, c, d ∈ T : f (S ∪ {c, d} \ {a, b}) > α · f(S) do 18: S ← S ∪ {c, d} \ {a, b} 19: T ← T ∪ {a, b} \ {c, d} 20: return S
Definition 6 (Nr(S, T )). For any natural number r ≥ 1 and any sets S, T we define the rneighborhood of S with respect to T
Nr(S, T ) := {S′ ⊆ S ∪ T | |S′| = |S| and |S′ \ S| ≤ r}
Outline of Algorithm 3: Similar to Algorithm 2, our new algorithm also maintains two subsets of indices S and T , and corresponding data matrices VS ,BS ,VT ,BT . Whenever the algorithm sees a new data-point (vt, bt), it checks if the solution quality f(S) can be improved by a factor of α by replacing any element in S with the newly seen data-point. Additionally, it also checks if the solution quality can be made better by including both the points (vt, bt) and the data-point (vt−1, bt−1). Further, the algorithm tries to improve the solution quality by performing a local search on N2(S, T ) 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 in 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, b1), . . . , (vn, bn) where (vt, bt) ∈ Rd × Rd ∀ t ∈ [n], the worst case update time of Algorithm 3 is O(Tdet(k, d) · k2 log3(∆)) where Tdet(k, d) is the time taken to compute f(S) = det(V >S V + B > SCB) for |S| = k. The amortized update time
is O ( Tdet(k, d) · ( k2 + k 2 log3(∆) n )) and the space used at any time step is at most O(k2 + d2 +
d logα(∆)).

heading: 6 ONLINE LEARNING
text: 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.

heading: 6.1 ONLINE SETTING
text: The online learning problem for NDPPs is formally defined as follows: Definition 8 (Online NDPP Learning). Given a continuous stream of observed sets {S1, . . . , St, . . . , } of items from [n], the online learning problem is to maintain an NDPP kernel
Algorithm 4 ONLINE-NDPP-LEARNING: Online learning for low-rank NDPPs 1: Input: Stream of sets {S1, S2, . . . , St, . . .} arriving in an online fashion (in some arbitrary
order), embedding size d for NDPP model matrices 2: Output: low-rank NDPP kernel L(t) at any time t (and V (t), B(t), C(t) if warranted) 3: Initialize matrices V , B, C 4: while new set St = {a1, a2, ...} arrives in stream do 5: Update VSt ,BSt ,C using∇VStψt,∇BStψt,∇Cψt (Eqs. 9, 10, 11) respectively. 6: return low-rank NDPP kernel L(t) at time t
Lt = (V >V + B>CB)t for every time step t that maximizes the regularized log-likelihood:
φt(V ,B,C) = 1
t t∑ i=1 log det ( V >SiVSi + B > SiCBSi ) − log det ( V >V + B>CB+ I ) −R(V ,B) (3)
where VSi ,BSi ∈ Rd×|Si| denote sub-matrices of V and B which are formed by the columns that correspond to the items in Si, and the regularizer R(V ,B) = α ∑n i=1 1 µi ‖vi‖22 + β ∑n i=1 1 µi ‖bi‖22 where µi is the number of occurrences of the item i in all the training data (subsets), α, β > 0 are tunable hyperparameters.

heading: An online learning algorithm for NDPPs needs to:
text: • 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 {Si ⊆ [n] | i = 1 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 in 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 state-of-the-art learning algorithm Gartrell et al. (2021) has the following limitations that make it fundamentally offline: First, it stores all training data in memory and so uses O(td′) space where d′ = maxi |Si| is the size of the largest subset in the stream {S1, . . . , St}. 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 an update time of O(pnd2 + ptd′3), which is too much for the online setting.

heading: 6.2 ONLINE ALGORITHM
text: We present our online learning approach for NDPPs in Algorithm 4. To update (V ,B,C) at every time step t, we use the gradient of the following objective function ψt, which is an approximation of the regularized log-likelihood φt(V ,B,C). Let us define Z(V ,B,C) := log det ( V >V + B>CB+ I ) . Our approximate objective
ψt(V ,B,C) = log det ( V >StVSt + B > StCBSt ) − Z(VSt ,BSt ,C)−R(VSt ,BSt) (4)
For every time step t, we only update VSt ,BSt ,C using the gradient of ψt i.e. ∇VSt ,BSt ,C ψt. We defer the gradient derivations to Appendix D.
We defer the proof of the following theorem to Appendix D.
Theorem 9. Algorithm 4 uses O(d′2 + d2) space †. Also, the update time for a single subset St arriving at time t in the stream is O(d3 + d′3) where d′ is the size of the largest set in the stream.
For every new subset St arriving in the stream, Algorithm 4 updates only the columns of V and B corresponding to the elements in St, hence, VSt ,BSt . It uses total space O(nd+ d ′2), which is
†Note that the O(nd + d2) required to store the matrices V , B, and C are omitted for simplicity (since these terms are common to all algorithms).
independent of the stream length (and is therefore sub-linear in it as well); takes a single pass over the stream; updates the NDPP model only using the subset St and then discards St; has an O(d3 + d′ 3 ) update time. This is in contrast to the offline learning algorithm that uses O(md′) space where m is the length of the stream and d′ is the size of the largest set (m d, d′, n).

heading: 7 EXPERIMENTS
text: Our experiments are designed to 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.

heading: 7.1 ONLINE INFERENCE
text: As a point of 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 k passes over the dataset and in each round, picks the data point which gives the maximum marginal gain in solution value. Online-Greedy replaces a point in the current solution set with the observed point if doing so increases the objective. See Algorithm 5 in Appendix B 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 d = 100 is used. We perform MAP inference by running our algorithms on the learned B,C, and V . For all the following results, we set α = 1.1 and k = 8.
MAP Inference results for a variety of different datasets are provided in Figure 1. Surprisingly, the solution quality of our online algorithms compare favorably with the offline greedy algorithm while using only a single-pass over the data, and a tiny fraction of memory. In most cases, Online2-neighbor (Algorithm 3) performs better than Online-LSS (Algorithm 2) which in turn performs better than the online greedy algorithm (Algorithm 5). Strikingly, our online-2-neighbor 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 a system-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 be found in Appendix F. We summarize the main findings here. The number of determinant computations of Online-LSS is comparable to that of Online Greedy but the number of swaps performed is significantly smaller. Online-2-neighbor is the most time-consuming but superior performing algorithm in terms of solution quality.
We also investigate the performance of 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, we see that Online-LSS and Online-2-neighbor have nearly identical performance and are always better than Online-Greedy 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 of determinant computations, and the number of swaps increase as α decreases (Figure 7). We also see that as k increases, the solution value decreases across all values of α (Figure 8). This is in accordance with our intuition that the probability of larger sets should be smaller.

heading: 7.2 ONLINE LEARNING RESULTS
text: Here, we compare our online learning algorithm for NDPPs with the state-of-the-art offline learning algorithm. In Figure 2, we compare our online learning algorithm to the offline algorithm using negative log-likelihood over time. In all cases, the offline learning algorithm uses significantly more time, usually taking between 6x to 15x more time to converge. Furthermore, the negative log-likelihood from our online learning algorithm decreases significantly faster compared to the offline.

heading: 8 CONCLUSION
text: 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 state-of-the-art offline algorithms. We believe our work opens up completely new avenues for practical application of NDPPs and can lead to deployment of NDPPs in many more real-world settings.
REPRODUCIBILITY STATEMENT
For all of our theoretical results, we have provided clear explanations of all the assumptions in the main text (Sections 4, 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.

heading: A STREAMING MAP INFERENCE DETAILS
text: Theorem 2. For a random-order arrival stream, if S is the solution output by Algorithm 1 at the end of the stream and σmin > 1 where σmin and σmax denote the smallest and largest singular values of LS among all S ⊆ [n] and |S| ≤ 2k, then
E[log det(LS)] ≥ ( 1− 1
σ (1− 1e )·(2 log σmax−log σmin) min
) log(OPT)
where LS = V >S VS + B > SCBS and OPT = max R⊆[n], |R|=k det(V >R VR + B > RCBR).
We will first give a high-level proof sketch for our this theorem.
Proof sketch. For a random-order arrival stream, the distribution of any set of consecutive n/k elements is the same as the distribution of n/k elements picked uniformly at random (without replacement) 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(LS) nor log det(LS) are submodular. Instead, Gartrell et al. (2021)[Equation 45] showed that log det(LS) is “close” to submodular when σmin > 1 where this closeness is measured using a parameter known as “submodularity ratio” (Bian et al., 2017). Using this parameter, we can prove a guarantee for our algorithm.
We will now provide a more complete proof.
Proof. As described in Algorithm 1, we will use S0, S1, . . . , Sk to denote the solution sets maintained by the algorithm, where Si represents the solution set of size i. In particular, we have that Si = Si−1 ∪ {si} where si = arg maxj∈Bi f(S ∪ {j}) and Bi denotes the i’th partition i.e. Bi := { (i−1)·nk + 1, (i−1)·n k + 2, . . . , i·n k }.
For i ∈ [k], let us use Xi := [Bi ∩ (S∗ \ Si−1) 6= ∅] 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 Bi and λi := |S∗ \ Si−1|. Then,
Pr[Xi] = 1− Pr[Xci ]
= 1− (1− λi n )(1− λi n− 1 ) . . . (1− λi n− nk + 1 )
≥ 1− (
1− λi n
)n k
≥ 1− e− λi k ≥ λi k · ( 1− 1 e ) Here we use the facts: ex ≥ 1+x for all x ∈ R, 1−e−λk is concave as a function of λ, and λ ∈ [0, k]. For any element s ∈ [n] and set S ⊆ [n], let us use f(s | S) := f(S ∪ {s}) − f(S) to denote the marginal gain in f obtained by adding the element s to the set S. For any round i ∈ [k], we then have that f(Si)− f(Si−1) = f(si | Si−1). Note that
E[f(si | Si−1) | Xi] ≥ ∑ ω∈OPT\Si−1 f(ω | Si−1) |OPT \ Si−1| .
This happens due to the fact that conditioned on Xi, every element in S∗ \ Si−1 is equally likely to be present in Bi and the algorithm picks si such that f(si | Si−1) ≥ f(s | Si−1) for all s ∈ Bi.
E[f(si | Si−1) | Si−1] = E[f(si | Si−1) | Si−1, Xi] Pr[Xi] + E[f(si | Si−1) | Si−1, Xci ] Pr[Xci ] ≥ E[f(si | Si−1) | Si−1, Xi] Pr[Xi]
≥ λi k
( 1− 1
e ) · ∑ ω∈S∗\Si−1 f(ω | Si−1) |S∗ \ Si−1|
= λi
|S∗ \ Si−1|
( 1− 1
e ) · 1 k · ∑ ω∈S∗\Si−1 f(ω | Si−1)
= ( 1− 1
e ) · 1 k · ∑ ω∈S∗\Si−1 f(ω | Si−1)
≥ (
1− 1 e ) · 1 k · γ · (f(Si−1 ∪ S∗)− f(Si−1))
≥ (
1− 1 e ) · 1 k · γ · (OPT− f(Si−1))
For the last 2 inequalities, we use the fact that f(S) = log det(LS) is monotone non-decreasing and has a submodularity ratio of γ = ( 2 log σmaxlog σmin − 1 )−1 when σmin > 1 (Gartrell et al., 2021)[Eq. 45].
Taking expectation over all random draws of Si−1, we get E[f(si | Si−1)] ≥ (
1− 1 e ) · γ k (OPT− E[f(Si−1)])
Combining the above equation with f(si|Si−1) = f(Si)− f(Si−1), we have
E[f(Si)]− E[f(Si−1)] ≥ (
1− 1 e ) · γ k · (OPT− E[f(Si−1)])
Next we have −(OPT− E[f(Si)]) + (OPT− E[f(Si−1)]) ≥ (
1− 1 e ) · γ k · (OPT− E[f(Si−1)])
Re-organizing the above equation, we obtain OPT− E[f(Si)] ≤ ( 1− (
1− 1 e ) · γ k ) (OPT− E[f(Si−1)])
Applying the above equation recursively k times, OPT− E[f(Sk)] ≤ ( 1− (
1− 1 e ) · γ k )k (OPT− E[f(S0)])
= ( 1− ( 1− 1
e ) · γ k )k OPT
where the last step follows from f(S0) = 0.
Re-organized the terms again, we have
E[f(Sk)] ≥ ( 1− ( 1− ( 1− 1
e ) · γ k )k) OPT
≥ ( 1− e−γ(1− 1e ) ) OPT
When we substitute γ = ( 2 log σmaxlog σmin − 1 )−1 , we get our final inequality:
E[f(Sk)] ≥ ( 1− 1
σ (1− 1e )·(2 log σmax−log σmin) min
) OPT
Theorem 3. For any length-n stream (v1, b1), . . . , (vn, bn) where (vt, bt) ∈ Rd×Rd ∀ t ∈ [n], the worst-case update time of Algorithm 1 is O(Tdet(k, d)) where Tdet(k, d) is the time taken to compute f(S) = det(V >S V + B > SCB) for |S| = k. The total time taken is O(n · Tdet(k, d)) and the space used at any time step is O(k2 + d2).
Proof. For any particular data-point (vt, bt), Algorithm 1 needs to compute f(Si−1 ∪ {t}), which takes at most Tdet(k, d) time. All the other comparison and update steps are much faster and so the worst-case update time is O(Tdet(k, d)). The space needed to compute det(V >S V + B>S CBS) is at mostO(k2+d2) where S = Si−1∪{t}. The algorithm also needs to store Si−1, si and f(Si−1∪{si}) but all of these are dominated by O(k2 + d2) space needed to compute the determinant.

heading: B ONLINE MAP INFERENCE DETAILS
text: Theorem 5. For any length-n stream (v1, b1), . . . , (vn, bn) where (vt, bt) ∈ Rd×Rd ∀ t ∈ [n], the worst case update time of Algorithm 2 is O(Tdet(k, d) · k log2(∆)) where Tdet(k, d) is the time taken to compute f(S) = det(V >S V + B > SCB) for |S| = k. Furthermore, the amortized update time is O(Tdet(k, d) ·(k+ k log 2(∆) n )) and the space used at any time step is at mostO(k 2 +d2 +d logα(∆)).
Proof. For every iteration of the while loop in line 4: It takes at most Tdet(k, d) time for checking the first if condition (lines 5-6). The argmaxj∈S f(S ∪ {t} \ {j} step takes at most k · Tdet(k, d) time. The while loop in line 12 takes time at most |S| · |T | · Tdet(k, d) for every instance of an increase in f(S). Note that f(S) can increase at most logα(∆) times since the value of f(S) cannot exceed OPTk. Therefore, the update time of Algorithm 2 is at most Tdet(k, d) + k · Tdet(k, d) + logα(∆) · (|S| · |T | · Tdet(k, d)) ≤ Tdet(k, d) · ( k + 1 + k log2α(∆) ) since |S| ≤ k and |T | ≤ logα(∆). Notice that the cardinality of T can increase by 1 only when the value of f(S) increases at least by a factor of α and so |T | ≤ logα(∆). During any time step t, the algorithm needs to store the indices in S, T and the corresponding matrices VS ,BS ,VT ,BT . Since |S| ≤ k, |T | ≤ logα(∆) and it takes d words to store every vi and bi, we need at most k+ logα(∆) + 2dk+ 2d logα(∆) words to store all these in memory. The space needed to compute det(V >S VS + B > SCBS) is at most O(k
2 + d2). We compute all such determinants one after the other in our algorithm. So the algorithm only needs space for one such computation during it’s run. Therefore, the space required by Algorithm 2 is O(k2 + d2 + d logα(∆)).
Theorem 7. For any length-n stream (v1, b1), . . . , (vn, bn) where (vt, bt) ∈ Rd × Rd ∀ t ∈ [n], the worst case update time of Algorithm 3 is O(Tdet(k, d) · k2 log3(∆)) where Tdet(k, d) is the time taken to compute f(S) = det(V >S V + B > SCB) for |S| = k. The amortized update time
is O ( Tdet(k, d) · ( k2 + k 2 log3(∆) n )) and the space used at any time step is at most O(k2 + d2 +
d logα(∆)).
Proof. It takes at most Tdet(k, d) time for lines 5-6 (same as in LSS). The arg maxa,b∈S (f(S ∪ {t} \ {a}), f(S ∪ {t− 1, t} \ {a, b})) step takes at most k2 · Tdet(k, d) time. The while loop in line 18 takes time at most |S|2 · |T |2 · Tdet(k, d) for every instance of an increase in f(S). Similar to LSS, f(S) can increase at most by a factor of logα(∆) since the value of f(S) cannot exceed OPTk. Therefore, the update time of Algorithm 3 is at most Tdet(k, d)+k2·Tdet(k, d)+logα(∆)· ( |S|2 · |T |2 · Tdet(k, d) ) ≤ Tdet(k, d)· ( k2 + 1 + k2 log3α(∆)
) since |S| ≤ k and |T | ≤ logα(∆).
Algorithm 5 ONLINE-GREEDY: Online Greedy MAP Inference for NDPPs 1: Input: A stream of data points {(v1, b1), (v2, b2), . . . , (vn, bn)} 2: Output: A solution set S of cardinality k at the end of the stream. 3: S ← ∅ 4: while new data (vt, bt) arrives in stream at time t do 5: if |S| < k and f (S ∪ {t}) 6= 0 then 6: S ← S ∪ {t} 7: else 8: i← arg maxj∈S f(S ∪ {t} \ {j}) 9: if f (S ∪ {t} \ {i}) > f(S) then 10: S ← S ∪ {t} \ {i} 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 to be stored in memory. Therefore, the space needed is (nearly) the same for both the algorithms.

heading: C HARD INSTANCE FOR ONLINE MAP INFERENCE OF NDPPS
text: Outline: 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 we have a total of 2d items consisting of pairs of complementary items like modem-router, printer-ink cartridge, pencil-eraser etc. Let us use {1, 1c, 2, 2c, . . . , d, dc} to denote them. Any item i is independent of every item other than it’s complement ic. Individually, Pr[{i}] = Pr[{ic}] = 0 . And Pr[{i, ic}] = x2i with xi > 0 for all i ∈ [d]. Also, we have Pr[{i, j}] = 0 for any i 6= j. Suppose any of our online algorithms are given the sequence {1, 2, 3, . . . , d, rc} where r ∈ [d] is some arbitrary item and the algorithm needs to pick 2 items i.e. k = 2. Then, OPT > 0 whereas all of our online algorithms (Online LSS, Online 2-neighbor, Online-Greedy) will fail to output a valid solution.
Details: Let 0 < x1 < x2 < · · · < xd. Suppose
C =  0 x1 −x1 0 0 x2 −x2 0
. . . 0 xd −xd 0  C ∈ R2d×2d is a skew-symmetric (i.e. C = −C>) block diagonal matrix where the blocks are of the
form [
0 xi −xi 0
] . Suppose we have a total of 2d items consisting of d pairs of complementary items.
We use {1, 1c, 2, 2c, . . . , d, dc} to denote them. Let vi = vic = 0 ∀ i ∈ [d] and b1 = e1, b1c = e2, . . . , bdc = e2d where e1, e2, . . . , e2d are the standard unit vectors in R2d i.e. B = I2d.
For a pair of complementary items S = {i, ic}, f(S) = x2i . Without loss of generality, consider S = {1, 1c}. Then we can compute B>SCBS as follows:
B>SCBS = [e1 e2] > C [e1 e2]
= [ 0 x1 0 0 · · · 0 −x1 0 0 0 · · · 0 ] · [e1 e2]
= [ 0 x1 −x1 0 ]
In this case, we have f(S) = x21.
For any pair of non-complementary items S = {i1, i2} where the indices are distinct, f(S) = 0. Without loss of generality, we can consider S = {1, 2}. Then,
B>SCBS = [e1 e3] > C [e1 e3]
= [ 0 x1 0 0 · · · 0 0 0 0 x2 · · · 0 ] · [e1 e3]
= [ 0 0 0 0 ] And so, we have that f(S) = 0.

heading: D LEARNING DETAILS
text: Our approximate objective ψt(V ,B,C) = log det ( V >StVSt + B > StCBSt ) − Z(VSt ,BSt ,C)−R(VSt ,BSt) (5)
We will now provide a derivation of i.e. ∇VSt ,BSt ,C ψt. Let us first look at the gradient of the first term
∇VSt log det ( V >StVSt + B > StCBSt ) = 2VSt ( V >StVSt + B > StCBSt )−1 ∇BSt log det ( V >StVSt + B > StCBSt ) = 2CBSt ( V >StVSt + B > StCBSt
)−1 ∇C log det ( V >StVSt + B > StCBSt ) = BSt ( V >StVSt + B > StCBSt )−1 B>St
Now, we consider the gradient of Z(VSt ,BSt ,C), which consists of three parts: ∇VStZ,∇BStZ,∇CZ. Let X = I − V > St (Id + VStV > St )−1VSt . Note that
Z = log det ( Id + VStV > St ) + log det ( C−1 + BSt(I − V >St (Id + VStV > St ) −1VSt)B > St ) + log det(C)
We refer the reader to (Gartrell et al., 2021, Eqn 19) for a derivation of the above form of Z. Then,
∇VStZ = 2V > St (Id + VStV > St ) −1
−XB>St((C −1 + BStXB > St) −1 + (C−> + BStXB > St) −1)BStXV > St (6)
∇BStZ = XB > St ( (C−1 + BStXB > St) −1 + (C−> + BStXB > St) −1) (7)
∇CZ = C−> −C−>(C−1 + BStXB>St) −>C−> (8)
Since we only have one subset at a time step, R(VSt ,BSt) = α ∑ i∈St ‖vi‖ 2 + β ∑ i∈St ‖bi‖
2. Therefore, ∇VStR = 2αVSt ,∇BStR = 2βBSt . We can then substitute ∇Z from Equations 6,7,8 in the following equations to get the gradient required for updates∇ψt:
∇VStψt = 2VSt ( V >StVSt + B > StCBSt )−1 −∇VStZ − 2αVSt (9) ∇BStψt = 2CBSt ( V >StVSt + B > StCBSt
)−1 −∇BStZ − 2βBSt (10) ∇Cψt = BSt ( V >StVSt + B > StCBSt )−1 B>St −∇CZ (11)
Theorem 9. Algorithm 4 uses O(d′2 + d2) space ‡. Also, the update time for a single subset St arriving at time t in the stream is O(d3 + d′3) where d′ is the size of the largest set in the stream.
‡Note that the O(nd + d2) required to store the matrices V , B, and C are omitted for simplicity (since these terms are common to all algorithms).
Proof. To compute∇VStZ, it takes space at most O(d ′2 + d2) as it involves matrix multiplications and inversions of matrices of sizes d′ × d, d× d, d′ × d′. Similarly for ∇BStZ,∇CZ. Computing the gradient of the first term in Equation 4 requires inversion of a d′ × d′ matrix, which takes at most O(d′ 2 ) space. And the gradient of the sum of norms term in Equation 4 takes at most O(d′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×d, d′×d′, and d′×d. All of these can be done in time O(d3 +d′3).
Theorem 10. Given a stream of subsets {S1, S2, . . . , Sm} of length-m, Algorithm 4 learns an NDPP kernel L = V >V + B>CB of rank-d using only a single-pass over the stream in O(md′3 +md3) time where d′ = maxt(|St|) n. Note V ,B ∈ Rd×n, C ∈ Rd×d, 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-streaming), they use all available data at once to update the embedding matrices of the NDPP model. Notice that log det ( V >StVSt + B > St CBSt ) in Eq. 3 is computed for every subset, thus taking O(md′) time for all m sets in the stream where d′ is the size of the largest set in the stream. Furthermore, log det ( V >V + B>CB+ I ) (2nd term in Eq. 3) takes O(nd2) 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).

heading: E DATASETS
text: We use several real-world datasets composed of sets (or baskets) of items from some ground set of items.
• UK Retail: This is 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.
• 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 a 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).
• Instacart: 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.
• Million Song: This is a 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 et al., 2020). Each dashboard represents a 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 a 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.

heading: F ADDITIONAL EXPERIMENTAL RESULTS
text: F.1 NUMBER OF DETERMINANT COMPUTATIONS
We perform several experiments comparing the number of determinant computations (as a systemindependent 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 as a function of the number of data points analyzed for a variety of datasets are provided in Figure 3. Online-2-neighbor 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.
F.2 NUMBER OF SWAPS
Results comparing the number of swaps (as a measure of solution consistency) of all our online algorithms can be found in Figure 4. 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 to Online-LSS.
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 do this 100 times and report the average of solution values in Figure 5 and the average of number of determinant computations and swaps in Figure 6. We observe that Online-2neighbor 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 ∈ {0.05, 0.1, 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.
.
F.5 ABLATION STUDY VARYING SET SIZE k AND
In this set of experiments on the Amazon-Apparel dataset using Online-LSS, we study the choice of set size k and on 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 k increases, the solution value decreases across all values of . This is in 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 k across different values of .
F.6 ONLINE LEARNING RESULTS
Figure 9 shows that the heat maps of the kernel matrices learned by our online learning algorithm and the offline learning algorithm are quite similar. We use the Amazon Apparel dataset for this set of experiments.

Review summaries:
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.

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.