Scalable Sampling for Nonsymmetric Determinantal Point Processes
Authors: Insu Han
Mike Gartrell
Jennifer Gillenwater
Elvis Dohmatob
amin karbasi
Venue: ICLR 2022 Spotlight (2022)
Keywords: determinantal point processes
sampling

Abstract: A determinantal point process (DPP) on a collection of $M$ items is a model, parameterized by a symmetric kernel matrix, that assigns a probability to every subset of those items.  Recent work shows that removing the kernel symmetry constraint, yielding nonsymmetric DPPs (NDPPs), can lead to significant predictive performance gains for machine learning applications. However, existing work leaves open the question of scalable NDPP sampling. There is only one known DPP sampling algorithm, based on Cholesky decomposition, that can directly apply to NDPPs as well. Unfortunately, its runtime is cubic in $M$, and thus does not scale to large item collections. In this work, we first note that this algorithm can be transformed into a linear-time one for kernels with low-rank structure.  Furthermore, we develop a scalable sublinear-time rejection sampling algorithm by constructing a novel proposal distribution.  Additionally, we show that imposing certain structural constraints on the NDPP kernel enables us to bound the rejection rate in a way that depends only on the kernel rank. In our experiments we compare the speed of all of these samplers for a variety of real-world tasks.

Published as a conference paper at ICLR 2022
SCALABLE SAMPLING FOR NONSYMMETRIC DETERMINANTAL POINT PROCESSES
Insu Han
Mike Gartrell Critco Al Lab
Jennifer Gillenwater
Yale University
Google Research
insu.han aasuhan@@yle.edu
m.gaatreil@crriee..cmm
jengi@google.com
Elvis Dohmatob
Amin Karbasi
Facebook AI Research
Yale University
dohmatob@fb.com
amin. karbasi@yale.ed.
ABSTRACT
A determinantal point process (DPP) on collection of M items is model, parameterized by symmetric kernel matrix, that assigns a probability to every subset of those items. Recent work shows that removing the kernel symmetry constraint, yielding nonsymmetric DPPs (NDPPs), can lead to significant predictive performance gains for machine learning applications. However, existing work leaves open the question of scalable NDPP sampling. There is only one known DPP sampling algorithm, based on Cholesky decomposition, that can directly apply to NDPPs as well. Unfortunately, its runtime is cubic in M, and thus does not scale large item collections. In this work, we first note that this algorithm can be transformed into linear-time one for kernels with low-rank structure. Furthermore, we develop scalable sublinear-tins rejection sampling algorithm by constructing a novel proposal distribution. Additionally, we show that imposing certain structural constraints on the NDPP kernel enables us to bound the rejection rate in a way that depends only the kernel rank. In our experiments of these samplers for a variety of real- world tasks.
compare the speed of all
INTRODUCTION
determinantal point process (DPP) on M items a model, parameterized by a symmetric kernel matrix, that assigns probability to every subset of those items. DPPs have been applied to wide range of machine learning tasks, including stochastic gradient descent (SGD) (Zhang et al., 2017), reinforcement learning (Osogami & Raymond, 2019; Yang et al., 2020), text summarization (Dupuy & Bach, 2018), coresets (Tremblay et al., 2019), and more. However, a symmetric kernel can only capture negative correlations between items. Recent works (Brunel, 2018; Gartrell et al., 2019) have shown that using a nonsymmetric DPP (NDPP) allows modeling of positive correlations as well, which lead to significant predictive performance gains. Gartrell al. (2021) provides scalable NDPP kernel learning and MAP inference algorithms, but leaves open the question of scalable sampling. The only known sampling algorithm for NDPPs the Cholesky-basee approach described in Poulson (2019), which has a runtime of ((M)) and thus does not scale to large item collections.
There a rich body of work on efficient sampling algorithms for (symmetric) DPPs, including recent works such as Derezinski et al. (2019); Poulson (2019); Calandriello et al. (2020). Key distinctions between existing sampling algorithms include whether they are for exact or approximate sampling, whether they assume the DPP kernel has some low-rank K & M,, and whether they sample from the space of all 2 subsets or from the restricted space of size-k subsets, so-called k-DPPs. In the context of MAP inference, influential work, including Summa et al. (2014); Chen et al. (2018); Hassani et al. (2019); Ebrahimi et al. (2017); Indyk et al. (2020), proposed efficient algorithms that the approximate (sub) duuedmnteminnnn maximization problem and provide rigorous guarantees. In this work we focus on exact sampling for low-rank kernels, and provide scalable algorithms for NDPPs. Our contributions are as follows, with runtime and memory details summarized in Table 1:
Lincar-time sampling (Section 3): We show how to transform the O(33) Cholesky- decomposition--assel sampler from Poulson (2019) into OMM)2) sampler for rank- K kernels.

---

Published as a conference paper at ICLR 2022
Table I: Runtime and memory complexities for sampling algorithms developed in this work. M is the size of the entire item set (ground set), and K is the rank of the kernel (often K < M in practice). We use & by the size of the sampled set (often k < K in practice), E [o, 1] is data-dependent constant (with our specific learning scheme, w < 1). The sublinear-time rejection algorithm includes one-time preprocessing step, after which each successive sample only requires "sampling time".
Sampling algorithm
Preprocessing time
Sampling time
Memory
Linear- time Cholesky-baser Sublincar-time rejection
O(MK3) Oikk log + ks + 1I ))
O(MK)
O(M K2)
O(M
This assumes some orthogonality constraint on the kernel.
Sublinear-time sampling (Section 4): Using rejection sampling, we show how to leverage existing sublinear- time samplers for symmetric DPPs to implement a sublinear-time sampler for a subclass of NDPPs that we call orthogonal NDPPs (ONDPPs).
Learning with orthogonality constraints (Section 5): We show that the scalable NDPP kernel learning of Gartrell et al. (2021) can be slightly modified to impose an orthogonality constraint, yielding the ONDPP subclass. The constraint allows to control the rejection sampling algorithm's rejection rate, ensuring its scalability. Experiments suggest that the predictive performance of the kernels is not degraded by this change.
For a common large-scale setting where M is 1 million, our sublinear-time sampler results in runtime that is hundreds of times faster than the linear-time sampler. In the same setting, our linear-time sampler provides runtime that is millions of times faster than the only previously known NDPP sampling algorithm, which has cubic time complexity and is thus impractical in this scenario.
2 BACKGROUND
Notation. We use [M] == (1....,,) M} to denote the set of items through M. We use Ix to denote the K K-by-K identity matrix, and often write I := Ias when the dimensionality should be clear from context. Given L E RMM we use Lij to denote the entry in the i-th row and j-th column, and LA,B E || for the submatrix formed by taking rows A and columns B. We also slightly abuse notation to denote principal submatrices with single subscript, LA := LA,A-
Kernels. As discussed carlier, both (symmetric) DPPs and NDPPs define a probability distribution over all 2M subsets of ground set [M]. The distribution is parameterized by kernel matrix L IR. M and the probability of a subset Y S [M] is defined to be Pr(Y)) xx (yy) For this to define a valid distribution, it must be the case that (Ly) 2 for all Y. For symmetric DPPs, the non-negativity requirement is identical to a requirement that L be positive semi-definite (PSD). For nonsymmetric DPPs, there is no such simple correspondence, but prior work such as Gartrell et al. (2019; 2021) has focused on PSD matrices for simplicity.
Normalizing and marginalizing. The normalizer of a DPP or NDPP distribution can also be written as a single determinant: Σy CIM] det(Ly) = det(L + I) (Kulesza & Taskar, 2012, Theorem 2.1). Additionally, the marginal probability of subset can be written as a determinant: Pr(A C Y) det( K A), for K = I - (L + r) (Kulesza & Taskar, 2012, Theorem 2.2)", where K is typically called the marginal kernel.
Intuition. The diagonal element K,,; is the probability that item i is included in a set sampled from the model. The 2-by-2 determinant det( K (i.s)) K ; K jز K Kjj is the probability that both i and j are included in the sample. A symmetric DPP has a symmetric marginal kernel, meaning K,; j. and hence K,,Ki including both i and j in the sampled set cannot be greater than the product of their individual inclusion probabilities. Hence, symmetric DPPs can only encode negative correlations. In contrast, NDPPs can have K, and K j,a with differing signs, allowing them to also capture positive correlations.
j.j K. < K,, This implies that the probability of
2.1 RELATED WORK
Learning. Gartrell et al. (2021) proposes a low-rank kernel decomposition for NDPPs that admits tnear-time learning. The decomposition takes the form L VV B(D D D B for
"The proofs in Kulesza & Taskar (2012) typically assume symmetric kernel, but this particular one does rely the symmetry.
2

---

Published as a conference paper at ICLR 2022
Algorithm I Cholesky-based NDPP sampling (Poulson, 2019, Algorithm 1)
procedure SAMPLECHOLESKKCCK)
marginal kernel factorization Z, W
2:
Y 4-D 0
Q + W
3:
for to M do < K
4:
P: t 2, Qz
5:
4 uniform(0,) 1)
6:
if u S pj then Y +- Y U [?]
7:
else p: - P: -1
8:
Ka Kn K,, for A == (i 1,.1,.... M}
Q
Q21z Q
P1
pt
9: return
V. E MRK and D RRKK, The VV component is rank-K symmetric matrix, which can model negative correlations between items. The B(D - D
DD ""B" component is rank-K skew-
symmetric matrix, which can model positive correlations between items. For compactness of notation,
will write L ZX TT, where Z [V B E M and X
Ix 0
R22
o D-D"
The marginal kernel in this case also has a rank-2K decomposition, as can be shown via application of the Woodbury matrix identity:
I=
Zx (I2x Z zx) z
Note that the matrix to be inverted can be computed from and X in O(M K2) time, and the inverse itself takes O(K3) time. Thus, K can be computed from L in time O(M)3). We will develop version it. We compactly write K ZWz
sampling algorithms for this decomposition, as well as an orthogonality.conster
use W = x (I2K + Z zx) in what follows so that
Sampling. While there are a number exact sampling algorithms for DPPs with symmetric kernels, the only published algorithm that clearly can directly apply to NDPPs is from Poulson (2019) (see Theorem 2 therein). This algorithm begins with an empty set Y = 0 and iterates through the M items, deciding for each whether not to include it in Y based all of the previous inclusion/exclusion decisions. Poulson (2019) shows, via the Cholesky decomposition, that the necessary conditional probabilities be computed follows:
PrijEYliet Pr([i.j} SY) -Kj--KK, (K), /Ki,: Pr
(2)
PrijE P)(j - Pr((is)) K2J (K K (K,,
P)
Algorithm/ (left-hand side) gives pseudocode for this Cholesky-based sampling algorithm There has also been some recent work on approximate sampling for fixed-size k-NDPPs: Alimoham- madi et al. (2021) provide Markov chain Monte Carlo (MCMC) algorithm and prove that the overall runtime to approximate 8-close total variation distance is bounded by O M2 log(1/C Pr(Y)))), where Pr(Yo is probability of initial state Yo. Improving this runtime is interesting avenue for future work, but for this paper we focus on exact sampling.
LINEAR-TIME CHOLESKY-BASED SAMPLING
In this section, we show that the ((M3) runtime of the Cholesky-based sampler from Poulson (2019) can be significantly improved when using the low-rank kernel decomposition of Gartrell et al. (2021). First, note that Line 8 of Algorithm I, where all marginal probabilities are updated via an (M i)-by-(M i) matrix subtraction, the most costly part of the algorithm, making overall time and memory complexities ((M3) and O(M2), respectively. However, when the DPP kemel is given by a low-rank decomposition, we observe that marginal probabilities can updated by matrix-vector
'Cholesky decomposition is defined only for symmetric positive definite matrix. However, we use the term "Cholesky" from Poulson (2019) to maintain consistency with this work, although Algorithm is valid for nonsymmetric matrices.
3

---

Published as a conference paper at ICLR 2022
Algorithm 2 Rejection NDPP sampling
(Tree-based sampling)
procedure PREPROCESS(V B, D)
2: {(o,, M25-11 V2y ) + YOULADECOMPOSE(B. DY
3: X diag [K 1 0k/....0///0.KK/
4: Z < V1....... .K]
((s, 2,) 2 + EIGENDECOMPOSE (ZX
T + CO [=),..., _2x] )
5:
return Z, X
return T, [();, 2;
6: procedure SAMPLEREJECTVV, B, D, Z, X)
D tree T, eigen pair {(A, 2, ) of 2X2
7:
while true do
8:
Y + SAMPLEDPP (2PP) T
Y + SAMPLEDPP(T, {(A,, =;))
9:
4- (niform(0, 1)
- det(.VVT -BDDDD
10:
det((zXZ'ly)
S then break
12: return
multiplications of dimension 2K, regardless of M. In more detail, suppose we have the marginal kernel K ZW2 Z in Eq. (1) and let zj be the j-th row vector Z. Then, for of j:
(W W2,)( W)
irV) = Kjj (K K. K.
K2, 2
W
2j.
(4)
2, Wz
W z, (2. W) 2 W
P = x w
Zz.
(5)
The conditional probabilities in Eqs. (4) and (5) of bilinear form, and the zj do not change during sampling. Hence, is enough to update the 2K-by-2K inner matrix at each iteration, and obtain the marginal probability multiplying this matrix by 2,. The details are shown on the right-hand side of Algorithm 1. The overall time and memory complexities are OMMK3) and O (MMR K), respectively.
SUBLINEAR-TIME REJECTION SAMPLING
Although the Cholesky-basee based sampler runs in time linear in M, even this is too expensive for the large M that are often encountered in real-world datasets. To improve runtime, we consider rejection sampling (Von Neumann, 1963). Let p be the target distribution that aim to sample, and let q be any distribution whose support corresponds to that of pt we call q the proposal distribution. Assume that there is universal constant U such that p(x) Uq(x) for all z. In this setting, rejection sampling draws a sample from and accepts with probability p(x) (Ug()), repeating until an acceptance occurs. The distribution of the resulting samples is p. It important choose good proposal distribution so that sampling is efficient and the number of rejections is small.
4.1 PROPOSAL DPP CONSTRUCTION
Our first goal is to find a proposal DPP with symmetric kernel É that can upper-bound all probabilities of samples from the NDPP with kernel L within a constant factor. To this end, we expand the determinant of principal submatrix, det Ly), using the spectral decomposition of the NDPP kernel. Such decomposition essentially amounts to combining the eigendecomposition of the symmetric part of L with the Youla decomposition (Youla, 1961) of the ikem-symmetric part.
Specifically, suppose {aa). 92/-1, 32 ) is the Youla decomposition of B(D - D D (see Appendix D for more details), that is,
K/2 B(D 10-DDT DJ Σ oj (y2j 192; y25W22j11 j=1
(6)
Ppseudo-code of YOUL DECOMPPOE provided in Algarithm 4. See Appendix
4

---

Published as a conference paper at ICLR 2022
Then simply write L ZXZ
for Z
[V. y1 ................................ ykl E R Mx2K
and
σ1
0K/2
X = diag
Ix
K/22
Now, consider defining related but symmetric PSD kernel L zXz with X =
diag (Ix, 01, k/2 K/22). All determinants of the principal submatrices of L Z Z Z upper-bound those of L, as stated below.
Theorem 1. For every subset Y S [M] it holds that det(Ly) S det (y). Moreover, equality holds when the size Yf is equal to the rank of L.
Proof sketch: From the Cauchy-Bing -innet formula, the determinants of Ly and By for all Y S [M, 2K can be represented as
det(Lx)=
E
Σ
det ( det (xx,)) det (Yr,),
(8)
(S(K), JEN
det (E) =
E
(0)( Zr.1)²
Many of the terms in Eq. (8) are actually zero due the block-diagonal structure of X. For example, note that if 1 E I but 1 & J, then there is an all-zeros row in X1,J. making det (x.()) = 0. We show block-diagona matrix with diagonal entries among toy, or -oy o With this observation, we can prove that det (e.() ) upper-bounded by det(X),
that each X, IJ with nonzero determinant
or det(X X> r). Then, through application of the rearrangement inequality, we can upper-bound the sum of the (e,()) det Zy.r) del Zv..) in Eq. (8) with sum over det { r) del Zy Finally, we show that the number of non-zero terms in Eq. (8) is identical to the number of non-zero terms in Eq. (9). Combining these gives us the desired inequality dct(Ly) I det dct(Lyy). The full proof of Theorem is in Appendix E.
Now, recall that the normalizer of DPP (or NDPP) with kernel L is det + I). The ratio of probability of the NDPP with kernel L to that of DPP with kernel É is thus:
PY)(Y) det(Ly)/ det + I) det( i I) Prg(Y) det(Ly)/ det + det( +
where the inequality follows from Theorem 1. This gives us the necessary universal constant U boper-bounding the ratio of the target distribution to the proposal distribution. Hence, given a sample Y drawn from the DPP with kernel É, we can use acceptance probability Prz(Y) Prz (Y)) (et(Ly), / (E)( Pseudo-codes for proposal construction and rejection sampling are given in Algorithm 2. Note that to derive from L it suffices to run the Youla decomposition of B D because the difference is only in the skew-symmetrie part. This decomposition can run in O(M time; more details are provided in Appendix D. Since L is symmetric PSD matrix, we apply existing fast DPP sampling algorithms to sample from it. In particular, in the next section we combine fast tree-based method with rejection sampling.
4.2 SUBLINEAR-TIN TREE-BASED SAMPLING
There several DPP sampling algorithms that in sublinear time, such tree-based (Gillenwater et al., 2019) and intermediate (Derezinski et al., 2019) sampling algorithms. Here, we consider applying the former, a bree-based approach, to sample from the proposal distribution defined by Ż.
We give some details of the sampling procedure, as in the course of applying it we discovered an optimization that slightly improves on the runtime of prior work. Formally, let {(A,, =)) be the eigendecomposition of L and Z = [æ1,..., #2 E Mx2K As shown in Kulesza & Taskar (2012, Lemma 2.6), for every Y S [M]][V] < 2K, the probability of Y under DPP with È can be written:
det dEx Pry (Y) det(L II)
X
Σ
det Let, ZT,
II IEE
(10)
A
+
A+1
IEE
5

---

Published as a conference paper at ICLR 2022
Algorithm 3 Tree-based DPP sampling (Gillenwater et al., 2019)
1: procedure (A,, Z)
10:
procedure CONSTRUCTTREE(M 2)
2: if A [i} then
11: return BRANCH(M 2)
3: T.A - (5]. T. < Z Zj:
4: return T
5:
A, Split A in half
6:
T.left +- BRANCH(Ap; Z)
7:
Trigght BRANCH(A,,. Z)
8: T.E < T-T.left. + -Trright.
9:
return T
12: procedure SAMPLEDPP(T, (,,
21: procedure SAMPLEITEM(T QV, E)
13:
E 0, Y +- 0. Q'
-0
22: T is leaf then return T.A
14:
= ,.... K do
23:
Pe + (T.left. Eg, Q"
15:
E [i) w.p. A,((x; +1)
24:
Pr f (T.right.Er, Q')
16:
for k = -....., E do
25:
u f uniform(0, (0
17:
j SAMPLEITEM T,Q%,E)
26:
if S petp, then
18:
Y Yu)
27:
return Lelf,,, QK
19:
I Z (Zy,eZy.E)
ZY.F
28:
else
20:
return Y
29:
return SAMPLELTEM(T Q"
matrix of the form E Z,, elementary DPP. Hence, Eq. (10) can be thought of as DPP probabilities expressed as a mixture of elementary DPPs. Based on this mixture view, DPP sampling can be done two steps: (1) choose an elementary DPP according to its mixture weight, and then (2) sample subset from the selected elementary DPP. Step (1) can be performed by 2K independent random coin tossings, while step (2) involves computational overhead. The key idea of tree-based sampling is that step (2) can be accelerated by traversing a binary tree structure, which can be done in time logarithmic in M.
E can be a valid marginal kernel for a special type of DPP, called an
More specifically, given the marginal kernel K Z., ZT where E' is obtained from step (1), start from the empty set Y and repeatedly add an item to Y with probability:
Pr(j E S S S) Kjj K,Y (K (Ky))Kyy;; Zj,EQ* 23 =QQ" OZ,. (,))), (11)
where some final selected subset, and Q I |
ZT. (Zv -1 Zy Consider a binary tree whose root includes a ground set [M]. Every non-leat node contains a subset C [M] and stores 2K-by-2K matrix Σjea Zz,Z, Zj:- A partition A₃ and A,, such that A = A, A,A, 0. are passed to its left and right subtree, respectively. The resulting tree has M leaves and each has exactly single item. Then, one can sample a single item by recursively moving down to the left node with probability:
(Q" -DEA (z). (Q", ESEA Zz 2,)
(12)
or to the right node with probability 1 Pc. until reaching a leaf node. item in the leaf node is chosen with probability according to Eq. (11). Since every subset in the support of an elementary DPP with rank-k kernel has exactly & items, this process is repeated for EE| iterations. Full descriptions of tree construction and sampling are provided in Algorithm 3. The proposed tree-based rejection sampling for an NDPP outlined on the right-side of Algorithm 2. The one-time pre- pre-prceessing step of constructing the tree (CONsTRUCTTREE requires K?) time. After proppeccss,ngg the procedure SAMPLEDD involves E2] traversals of a tree of depth Olog M), where in each node a O(FF(2) operation is required. The overall runtime is summarized in Proposition and the proof can be found in Appendix E.2.
Proposition 1. The tree-based sampling procedure SAMPLEDPP in Algorithm 3 runs in time O(K + 1.3 log M + k4), where is the size of the sampled set².
"Computing pt via Eq. (12) improves Gillenwater al. (2019)'s Ol** log M) runtime for this step.

---

Published as a conference paper at ICLR 2022
4.3 AVERAGE NUMBER OF REJECTIONS
We now return to rejection sampling and focus on the expected number of rejections. The number of rejections of Algorithm 2 is known to be a geometric random variable with mean equal to the constant U used to upper-bound the ratio of the target distribution to the proposal distribution: det / det((L L + T). If all columns in V and B are orthogonal, which we denote V B, then the expected number of rejections depends only on the eigenvalues of the skew-symmetric part of the NDPP kernel.
Theorem 2. Given NDPP kernel L = VV + B DD for V. V.B. B D (1/2 be the positive
I k consider the proposal kernel L as proposed in Section 4.1. Let {az))=i
eigenvalues obtained from the Youla decomposition of B(D- B(D-DT)B D. IfV 1 B, then det(L+1] deu
K12
20; -.41 $ (1+w) K/2, where w = ΣØ= of
E 1..
Proof sketch: Orthogonality between V and B allows deet + I) to be expressed just in terms of the eigenvalues of VV and B D )T, Since both L and L share the symmetric part VVT, the ratio of determinants only depends on the skew-symmetric part. A more formal proof appears in Appendix E.3.
Assuming we have a kernel where V 1. B, we can combine Theorem 2 with the tree-based rejection sampling algorithm (right-side in Algorithm 2) to sample in time O((K k log M M+ k/2K) Hence, we have sampling algorithm that is sublinear in M, and can be much faster than the Cholesky- based algorithm when (1 + w) K/2 < M. In the next section,
introduce learning scheme with the V B constraint, as well as regularization to ensure that w is small.
5 LEARNING WITH ORTHOGONALITY CONSTRAINTS
We aim to learn a NDPP that provides both good predictive performance and a low rejection rate. We parameterize our NDPP kernel matrix L VV
+ B D )B" by
D diag (80
01
0
0K/2
(13)
0
for o, 2 B. = I, and, motivated by Theorem 2, require V 0 We call such orthogonality-consrai
NDPPs "ONDPPs". Notice that if V 1 B, then L has the full rank of 2K, since the intersection of the column spaces spanned by V and by B is empty, and thus the full rank available for modeling ensuring that ONDPPs use the full rank available to them.
be used. Thus, this constraint can also be thought of simply
Given example subsets (Yi...., Y. training data, learning done by minimizing the regularized negative oog-likelhhooe
del(L + det(L 1)
M
U f4
M
b
K/2
20,
min V.B,a,)
log
3
log
1 1
K/2
A4
of +1
1=
(14)
where a, 8, 7 > O are hyperparameters, is the frequency of item in the training data, and v; and b, represent the rows of V and B, respectively. This objective is very similar that of Gartrell et al. (2021), except for the orthogonality constraint and the final regularization term. Note that this regularization term corresponds exactly to the logarithm of the average rejection rate, and therefore should help to control the number of rejections.
EXPERIMENTS
We first show that the orthogonality constraint from Section 5 does not degrade the predictive performance of learned kernels. We then compare the speed of our proposed sampling algorithms.
project V according constraint, we apply QR decomposition on B. Note that both operations require O(M)?) time. (Constrained learning and sampling code is provided at https:/ htth///gtttuu.... com wwt.e/ooooieeeeeeeeeeeeeeeeeeeee /tnsuunnnn/nnnnni nonsy mmmtricmme dpp-samming......iiigii..... We use Pytorch's linalg. solve to avoid the expense of explicitly computing the (B" B) inverse.) Hence, our learning time complexity is identical to that of Gartrell al. (2021).
TTechnical details: To learn NDPP models with the constraint V B
to: V B(B T B) "B" T V). For the B
7

---

Published as a conference paper at ICLR 2022
Table 2: Average MPR and AUC, with 95% confidence estimates obtained via bootstrapping, test log-like sogliikl,,ood, and the number of rejections for NDPP models. Bold values indicate the best MPR, outside of the confidence intervals of the two bascline methods.
UK Retail
Recipe M=7,993
Instacart M=49,677
Million Song M=371,,400
Low-rank DPP Models
Metric
M=3,941
M=1,059,437
MPR
76.42 0.97
95.04 0.69
93.06 +: 0.92
90.00 1.18
72.54 4: 2.03
Symmetric DPP (Gartrell et al., 2017)
AUC
0.74 + 0.01
0.99 = 0.01
0.86 4: 0.01
0.77 = 0.01
0.70 0.01
Log-Likelihood
-104,89
-44.63
-73.22
-310.14
-149.76
MPR
77.09 1.10
95.17
0.67
92.40 + 1.05
89.00 1.11
72.98 + 1.46
NDPP (Gartrell et al., 2021)
AUC
+ 0.01
0,99
0.87 0.01
0.01
0.74 0.01
Log-Likelihood
-99.09
-4..22
-74.94
-314.12
-149.93
of Rejections
4.136 x10
78.95
6.806 x10*
3,907 x x10"
9,245x
MPR
78.43 0.95
95.40 +: 0.62
92.80 + 0.99
93.02 0.83
75.35 +: 1.83
ONDPP without regularization
AUC
0.71 +: 0.00
0,99
0.01
0.83 0.01
0.77 +: 0.01
0.64 0.01
Likelikeld of Rejections
-99.45
-44.60
-72.69
-302.64
-140.53
1.818 x109
103.81
128.96
5.563 x10?
682.22
MPR
77.12 0.98
95.50
0.59
92.99 4: 0.95
92.86 0.80
75.73 + 1.84
ONDPP with regularization
AUC LoggLikeld of Rejections
+ 0.01
0.99
0.01
0.01
0.64 0.01
-103.83
-44.56
-72.72
-305.66
-140.67
26.09
21.59
79.74
45.42
61.10
6.1 PREDICTIVE PERFORMANCE RESULTS FOR NDPP LEARNING
We benchmark various DPP models, including symmetric (Gartrell et al., 2017), nonsymmetric for scalable learning (Gartrell et al., 2021). as well as our ONDPP kernels with and without rejection rate regularization. We use the scalable NDPP models (Gartrell et al., 2021) baseline'. The kernel components of each model are learned using five real-world recommendation datasets, which have ground set sizes that range from 3,941 to 1, ,059,447 items (see Appendix A for more details).
Our experimental setup and metrics mirror those of Gartrell et al. (2021). We report the mean percentile rank (MPR) metric for next-item prediction task, the AUC metric for subset discrimination, and the log-likelihood of the test set; see Appendix B for more details on the experiments and metrics. For all metries, higher numbers are better. For NDPP models, we additionally report the average rejection rates when they apply to rejection sampling.
In Table 2. we observe that the predictive performance of our ONDPP models generally match or sometimes exceed the bascline. This is likely because the orthogonality constraint enables more effective use of the full rank-2K feature space. Moreover, imposing the regularization on rejection rate, as shown in Eq. (14), often leads to dramatically smaller rejection rates, while the impact on predictive performance is generally marginal. These results justify the ONDPP and regularization for fast sampling. Finally, we observe that the learning time of our ONDPP models is typically bit longer than that of the NDPP models, but still quite reasonable (e.g., the time per iteration for the NDPP takes 27 seconds for the Book dataset, while ONDPP takes 49.7 seconds).
Fig. I shows how the regularizer 7 affects the test log- ligeliidd and the average number of rejections. We see that y degrades predictive performance and reduces the rejection rate when set above certain threshold; this behavior seen for many datasets. However, for the Recipe dataset we observed that the test log-likelihood is not very sensitive y, likely because all models in our experiments achieve very high performance on this dataset. In general, we observe that 7 can be set to a value that results in small rejection rate, while having minimal impact on predictive performance.
6.2 SAMPLING TIME COMPARISON
We benchmark the Cholesky-based sampling algorithm (Algorithm 1) and tree-based rejection sampling algorithm (Algorithm 2) on ONDPPs with both synthetic and real-world data.
We use the code from https://gtthub corn/ senn//aartrel/scaabbll nonsymmetric- Deaeetrrrr----sssss DPPs for the NDPP baseline, which is made available under the MIT license. To simplify learning and MAP inference, Gartrell et al. (2021) set B = V in their experiments. However, since we have the V 1 B constraint in our ONDPP approach, we cannot set B = V. Hence, for a fair comparison, do not set B V for the NDPP baseline in our experiments, and thus the results in Table differ slightly from those published in Gartrell et al. (2021).
8

---

Published as a conference paper at ICLR 2022
average of rejections
30
test log sillkllhhodd
sampling time (soc)
107
Cholesky-baaee Rejection
preprocessing ing time (sec)
10"
-+-
Speciral decomposiion
Tree constuction
1001
10'
10"
104
107
104
10'
10" 10-3 10-1
10 10
10"
10
10
10
212
244
24
2
2
243
2
regularizer 7
regularizer y
ground size M
ground set size
(a)
(b)
(a)
(b)
Figure I: Average number of rejections and test Figure 2: Wall-clock time (sec) for synthetic data
log-likelhhod with different values of the regu- for (a) NDPP sampling algorithms and (b) prepro- larizer for ONDPPs trained on the UK Retail cessing steps for the rejection sampling. Shaded dataset. Shaded regions are 95% confidence inter- regions are 95% confidence intervals from 100 independent trials.
vals of 10 independent trials.
Table 3: Wall-clock time (sec) for preprocessing and sampling ONDPPs trained on real-world data, and speedup of the tree-based sampler over the Cholesky-basee one. We K 100 and provide average times with 95% confidence intervals from 10 independent trials for the Cholesky-base based algorithm and 100 trials for the rejection algorithm. Memory usage for the tree is also reported.
UK Retail
Recipe M=7,933
Instacart
Million Song
Book
M=3,941
M=49.677
Md371.410
M=1.059.437
Spectral decomposition
0.209
0.226
0.505
2.639
7.482
Tree construction
0.997
1.988
12.65
119.0
340.1
Cholesky-busee sampling
5,572 + 0.056
11,36 = 0.098
71.82 + 1.887
545.8 : 8,776
1,631 = 1184
Tree-based rejection sampling (Speedup)
2.463 0.417
1,331 + 0.241
5.962 + 1.049
14.72 :: 2.620
6.627 1.294
(x2.262)
(x8.535)
(x (x.00)5)
(x 37.08)
(x246.1)
Tree memory usage
630.5 MB
1.279 GB
7,948 GB
59.43 GB
169.5
Synthetic datasets. We generate non-uniform random features for V, B done by (Han & Gillenwater, 2020). In particular, we first sample .i..... 2100 from (00, 12x 22x/(2K) (2K)), and integers ti...., 1100 from Poisson distribution with mean 5, rescaling the integers such that Σ; t, M. Next, we draw & random vectors from N(x; 12k) ), and assign the first K --dimensiinal vectors as the row vectors of V and the latter vectors as those of B. Each entry of D is sampled from N(0 1). We choose K = 100 and vary M from 22 to 220
Fig. 2(a) illustrates the runtimes of Algorithms 1 and 2. We verify that the rejection sampling time tends to increase sub-linearly with the ground set size M, while the Cholesky- sampler runs linear time. In Fig. 2(b), the runtimes of the preprocessing steps for Algorithm 2 (i.e., spectral decomposition and tree construction) are reported. Although the rejection sampler requires these additional processes, they are one-time steps and run much faster than single run of the Choleksy- based method for M = 220
Real-world datasets. In Table 3, we report the runtimes and speedup of NDPP sampling algorithms for real- world datasets. All NDPP kernels are obtained using learning with orthogonality constraints, with rejection rate regularization as reported in Section 6.1. We observe that the tree-based rejection sampling runs up 246 times faster than the Cholesky-based algorithm. For larger datasets, expect that this gap would significantly increase. As with the synthetic experiments, we see that the tree construction pre-processing time is comparable to the time required draw single sample via the other methods, and thus the tree-based method is often the best choice for repeated sampling""
7 CONCLUSION
In this work we developed scalable sampling methods for NDPPs. One limitation of our rejection sampler is its practical restriction the ONDPP subclass. Other opportunities for future work include the extension of our rejection sampling approach to the generation of fixed-size samples (from k-NDPPs). the development of approximate sampling techniques, and the extension of DPP samplers along the lines of Derezinski et al. (2019); Calandriello et al. (2020) to NDPPs. Scalable sampling also opens the door to using NDPPs as building blocks in probabilistic models.
'WWe note that the tree can consume substantial memory, e.g., 169.5 GB for the Book dataset with K = 100. For settings where this scale of memory use is unacceptable. we suggest use of the intermediate sampling algorithm (Calandriello al., 2020) in place of tree-based sampling. The resulting sampling algorithm may be slower, but the O(M K) memory cost is substantially lower.

---

Published as a conference paper at ICLR 2022
8 ETHICS STATEMENT
In general, our work moves in a positive direction by substantially decreasing the computational costs of NDPP sampling. When using our constrained learning method to learn kernels from user data, we recommend employing technique such as differentially-prrvatl SGD (Abadi et al., 2016) help prevent user data leaks, and adjusting the weights on training examples balance the impact of sub-groups groups of users so as to make the final kemel as fair as possible. As far as we are aware, the datasets used in this work do not contain personally identifiable information or offensive content. We were not able to determine if user consent was explicitly obtained by the organizations that constructed these datasets.
REPRODUCIBILITY STATEMENT
We have made extensive effort to ensure that all algorithmic, theoretical, and experimental contribu- tions described in this work are reproducible. All of the code implementing constrained learning and sampling algorithms is publicly available ?t The proofs for our theoretical contributions are available in Appendix E. For experiments, all dataset processing steps, experimental procedures, and hyperparameter settings are described in Appendices A, B, and C, respectively.
10 ACKNOWLEDGEMENTS
Amin Karbasi acknowledges funding in direct support of this work from NSF (IS-1145032) and ONR (N00014-19-1-2406).
REFERENCES
Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep Learning with Differential Privacy. In Conference on Computer and Communications Security, 2016.
Yeganch Alimohammadi, Nima Anari, Kirankumar Shiragur, and Thuy-Duong Vuong. Fractionally log-concave and sector-stable polynomials: counting planar matchings and more. In Symposium on the Theory of Computing (STOC), 2021.
Brunel. Learning Signed Determinantal Point Processes through the Principal Minor Assignment Problem. In Neural Information Processing Systems (NeurIPS), 2018.
Daniele Calandriello, Michal Derezinski, and Michal Valko. Sampling from k-DPP without looking at all items. In Neural Information Processing Systems (NeurIPS), 2020.
Daqing Chen, Sai Laing Sain, and Kun Guo. Data mining for the online retail industry: A case study of RFM model- based customer segmentation using data mining. Journal of Database Marketing & Customer Strategy Management, 2012.
Laming Chen, Guoxin Zhang, and Eric Zhou. Fast greedy MAP inference for Determinantal Point Process to improve recommendation diversity. Neural Information Processing Systems (NeurlPS), 2018.
Michal Derezinski, Daniele Calandriello, and Michal Valko. Exact sampling of determinantal point processes with sublinear time preprocessing, Neural Information Processing Systems (NeurIPS), 2019.
Christophe Dupuy and Francis Bach. Learning determinantal point processes in sublinear time. In Conference Artificial Intelligence and Statistics (AISTATS), 2018.
Javad Ebrahimi, Damian Straszak. and Nisheeth Vishnoi. Subdeterminant maximization via noncon- vex relaxations and anti-connentrattion, Foundations of Computer Science (FOCS), 2017.
10

---

Published as a conference paper at ICLR 2022
Mike Gartrell, Ulrich Paquet, and Noam Koenigstein. Low-Rank Factorization of Determinantal Point Processes. In Conference on Artificial Intelligence (AAAI), 2017.
Mike Gartrell, Victor-Emmanur 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 Vassilvtiskii. A Tree-Based Method for Fast Repeated Sampling of Determinantal Point Processes. In International Conference on Machine Learning (ICML), 2019.
Insu Han and Jennifer Gillenwater. MAP Inference for Customized Determinantal Point Processes via Maximum Inner Product Search. Conference on Artificial Intelligence and Statistics (AISTATS), 2020.
Hamed Hassani, Amin Karbasi, Aryan Mokhtari, and Zebang Shen. Stochastic conditional gradient++. SIAM Journal on Optimization (SIOPT), 2019.
Yifan Hu, Yehuda Koren, and Chris Volinsky, Collaborative Filtering for Implicit Feedback Datasets. In International Conference on Data Mining (ICDM), 2008
Piotr Indyk, Sepideh Mahabadi, Shayan Oveis Gharan, and Alireza Rezaci. Composable core-sets for determinant maximization problems via spectral spanners. In Symposium on Discrete Algorithms (SODA), 2020.
Instacart. The Instacart Online Grocery Shopping Dataset, 2017. URL https://www.instaaaar com/ datasets/ grooery-ssopppee 200ppinnnn-........
2017. Accessed May 2020.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International
Conference on Learning Representations (ICLR), 2015.
Alex Kulesza and Ben Taskar. Determinantal Point Processes for Machine Learning. Foundations and Trends in Machine Learning, 2012.
Yanen Li, Jia Hu, ChengXiang Zhai, and Ye Chen. Improving One-class Collaborative Filtering by Incorporating Rich User Information. In Conference on Information and Knowledge Management (CIKM), 2010.
Bodhisattwa Prasad Majumder, Shuyang Li. Jianmo Ni, and Julian J McAuley. Generating Person- alized Recipes from Historical User Preferences. In Empirical Methods in Natural Language Processing (EMNLP), 2019.
Brian McFee, Thierry Bertin-Mahieux, Daniel PW Ellis, and Gert RG Lanckriet. The million song dataset challenge. In International Conference on the World Wide Web (WWW), 2012.
Yuji Nakatsukasa. The low-rank eigenvalue problem. arXiv preprint arXiv:1905.1 1490, 2019.
Takayuki Osogami and Rudy Raymond. Determinantal reinforcement learning. In Conference on Artificial Intelligence (AAAI), 2019.
Jack Poulson. pirf-peerormance sampling of generic Determinantal Point Processes. arXiv preprint 1rXiv:1905.00165. 2019.
Jocelyn Quaintance. Combinatorial Identities: Table I: Intermediate Techniques for Summing Finite Series, volume 3. 2010.
Marco Di Summa, Friedrich Eisenbrand, Yuri Faenza, and Carsten Moldenhauer. On largest volume simplices and sub-determinants. In Symposium on Discrete Algorithms (SODA), 2014.
Nicolas Tremblay, Simon Barthelmé, and Fierre-Olivier Amblard. Determinantal Point Processes for Coresets, Journal of Machine Learning Research (JMLR), 2019.
11

---

Published as a conference paper at ICLR 2022
John Von Neumann. Various techniques used in connection with random digits. John von Neumann, Collected Works, 1963.
Mengting Wan and Julian McAuley. Item recommendation on monotonic behavior chains. In Conference Recommender Systems (RecSys), 2018.
Yaodong Yang, Ying Wen, Jun Wang. Liheng Chen, Kun Shao, David Mguni, and Weinan Zhang. Multi-agent determinantal q-learning. In International Conference on Machine Learning (ICML), 2020.
DC Youla. normal form for a matrix under the unitary congruence group. Canadian Journal of Mathematics, 1961.
Cheng Zhang, Hedvig Kjellströmm and Stephan Mandt. Determinantal Point Processes for Mini-Batch Diversification. In Conference on Uncertainty in Artificial Intelligence (UAI), 2017.
12

---

Published as a conference paper at ICLR 2022
A FULL DETAILS ON DATASETS
We perform experiments on several real-world public datasets composed of subsets:
UK Retail: This dataset (Chen al., 2012) contains baskets representing transactions from online retail company that sells all-occasion gifts. We omit baskets with more than 100 items, leaving us with dataset containing 19,762 baskets drawn from catalog of M 3,941 products. Baskets containing more than 100 items are in the long tail of the basket-size distribution, so omitting these is reasonable, and allows us to use a low-rank factorization of the NDPP with K 100.
This dataset (Majumder et al., 2019) contains recipes and food reviews from Food.com (formerly Genius Kitchen) fr. Each recipe ("basket") is composed of a collection of ingredients, resulting in 178,265 recipes and catalog of 7,993 ingredients.
Recipe:
Instacart: This dataset (Instacart, 2017) contains baskets purchased by Instacart users We omit baskets with more than 100 items, resulting in 3.2 million baskets and a catalog of 49,677 products.
Million Song: This dataset (McFee al., 2012) contains playlists ("baskets"") of songs from Echo Nest us R We trim playlists with more than 100 items, leaving 968,674 playlists and a catalog of 371,410 songs.
Book: This dataset (Wan & McMAlley, 2018) contains reviews from the Goodreads book review website, including variety of attributes describing the items" For each user we build subset ("basket") containing the books reviewed by that user. We trim subsets with more than 100 books, resulting in 430,563 subsets and catalog of 1,059,437 books.
As as we are aware, these datasets do not contain personally identifiable information or offensive content. While the UK Retail dataset is publicly available, we were unable to find a license for it. Also, we were not able to determine if user consent was explicitly obtained by the organizations that constructed these datasets.
B FULL DETAILS ON EXPERIMENTAL SETUP AND METRICS
We use 300 maddomly-selccter baskets held-out validation set, for tracking convergence during training and for tuning hyperparameters. Another 2000 random baskets are used for testing, and the rest are used for training. Convergence is reached during training when the relative change in validation log- log-liielhhood is below a predetermined threshold. We use PyTorch with Adam (Kingma & Ba, 2015) for optimization. We initialize D from the standard Gaussian distribution ((, 1), while V and B are initialized from the uniform(0, 1) distribution.
Subset expansion task. We use greedy conditioning do next-item prediction (Gartrell et al., 2021, Section 4.2). We compare methods using standard recommender system metric: mean percentile rank (MPR) (Hu et al., 2008; Li al., 2010). MPR of 50 equivalent to random selection; MPR of 100 means that the model perfectly predicts the next item. See Appendix B.1 for complete description of the MPR metric.
Subset discrimination task. We also test the ability of a model to discriminate observed subsets from randomly generated ones. For each subset in the test set, we generate a subset of the same length by drawing items uniformly at random (and we ensure that the same item is not drawn more than once for a subset). We compute the AUC for the model on these observed and random subsets, where the score for each subset is the log-likelihood that the model assigns to the subset.
#See https://wwwt https//www.ker. www.:aawww...c//agagggg////ooooa http://///ooooooooooeeeeeeeeeeee www--ooiooo------eeeeeeeeeeeeeee aaccipe--nn---eer-ineeatttii for the cense for this public dataset.
#This public dataset is available for non-commercial use; see http://wwwwinnttaart.coomm
procery-shoppinge 2017 for the license.
caaeet.cm/aa//////e for the license for this public dataset. ""This public dataset is available for academic use only; see https:/ /stps:///steee.eeeeeeesseee
"See http:/ ht///mmiln htt/mmmllooooonnaaeeee
http:://steesggogge.commmme uww..edu..uuuu
ucadbookgraph home for the license.
13

---

Published as a conference paper at ICLR 2022
B.1 MEAN PERCENTILE RANK
We begin our definition of MPR by defining percentile rank (PR). First, given a set J, let Pi,J Pr(JUpp J). The percentile rank of an item given a J is defined
PR.J Eves 1(P 2 pV.J)
100%
DM
where V indicates those elements in the ground set y that are not found J.
For our evaluation, given test set Y, we select a random element i E Y and compute PR, ( We then average over the of all test instances T to compute the mean percentile rank (MPR):
MPR
Σ YET
PR.Y
C HYPERPARAMETERS FOR EXPERIMENTS
Preventing numerical instabilities: The det (e,(Ly;) in Eq. (14) will be zero whenever |Y]] K, where Y; is an observed subset. To address this in practice we set to the size of the largest subset observed in the data, K', in Gartrell al. (2017). However, this does not entirely fix the issue, as there is still chance that the term will be zero even when |Y, S K. In this case though, we maximum, since the value of the objective function -00. Numerically, to prevent such singularities, in our implementation we add small cI correction to each Ly, when optimizing Eq. (14) (c 10-5 5 in our experiments).
know that we are
We perform grid search using a held-out validation set to select the best best-performing hyperparameters for each model and dataset. The hyperparameter settings used for each model and dataset are described below.
Symmetric low-rank DPP (Gartrell al., 2017). For this model, we use K for the number of item feature dimensions for the symmetric component V, and for the regularization hyperparameter for V. use the following hyperparameter settings:
UK Retail dataset: K = 100, 1.
Recipe dataset: K = 100, a 0.01
Instacart dataset: K = 100, a 0.001.
Million Song dataset: K 100, a 0.0001.
Book dataset: K 100, 0.001
Scalable NDPP (Gartrell et al., 2021). As described in Section 2.1, we use to denote the number of item feature dimensions for the symmetric component V and the dimensionality of the nonsymmetric component D. a and (3 are the regularization hyperparameters. We use the following hyperparameter settings:
UK dataset: K = 100, a = 0.01.
Recipe dataset: K 100, a 3 0.01.
Instacart dataset: K 100, 0.001.
Million Song dataset: K = 100, 0.01.
Book dataset: K = 100, a 3 0.1
ONDPP. As described in Section 5, we use K denote the number of item feature dimensions for the symmetric component V and the dimensionality of the nonsymmetric component C. a, B, and are the regularization hyperparameters. We use the following hyperparameter settings:
UK dataset: K = 100, a = 3 0.01, 7 = 0.5.
Recipe dataset: K = 100, a = = 0.01, 0.1.
Instacart dataset: K 100, a B 0.001, 0.001.
Million Song dataset: K 100,
0.01, = 0.2.
14

---

Published as a conference paper at ICLR 2022
Book dataset: K 100, 3 y 0.1.
For all of the above model configurations and datasets, we use a batch size 800 during training.
D YOULA DECOMPOSITION: SPECTRAL DECOMPOSITION FOR SKEW-SYMMETRE MATRIX
We provide some basic facts on the spectral decomposition of skew-symmetric matrix, and introduce an efficient algorithm for this decomposition when it is given by low-rank factorization. We write = V-1 and " as the conjugate transpose of CM and denote Ro(2) and Im(2) by the real and imaginary parts of a complex number 2, respectively.
Given E RM and D R k consider a mankKK skew-symmetric matrix B DT) Note that all nonzero eigenvalues of real-valued skew-symmetric matrix are purely imaginary. Denote i i0 .......... i K/2: - i0 K/2 by its nonzero eigenvalues where each of aj is real, and a + i a1 161.... 0k/2 + ibx k/2 ak/2 ibx/2 by the corresponding eigenvectors for aj. by RM, which come in conjugate pairs. Then, can write
K/2
B(D D D
Σ
lo ia + ib,) + ib,) io,(a; ibb) ib,)*
(15)
K/2
Σ 20, (a,b) - bb,a)]
(16)
K/2
> [aj bj aj by]
-o 0
oj
a i b a + bj
(17)
Note that 01 + b Kk/2 + bk/2 are real-valued orthonormal vectors, because a1 b1,..... Kk/2 bK/2 are orthogonal to each other and |aa + byll = ||ay12 + |b, for
all j. The pair {(o a, - bj. aj b,) K/2 is often called the Youla decomposition (Youla, 1961) of B(D - D D BBB To efficiently compute the Youla decomposition of rank-K matrix, we use the following result.
Proposition 2 (Proposition 1, Nakatsukasa (2019)). Given A, B E MM the nonzero eigenvalues of AB MM and B A Ck are identical. In addition, if (X, v) an eigenpair of B A with X + 0, then Av |Aul)))) is an eigenpair of AB"
From the above proposition, one can first compute (D - D B and then apply the eigende- composition that K-by-K matrix. Taking the imaginary part of the obtained eigenvalues gives us the oyys 's, and multiplying B by the eigenvectors gives us the eigenvectors of B D B T In addition, this can be done in O(M K2 + K3) time; when M > K it runs much faster than the eigendecomposition of B(D D DJBB" T, which requires O(M3) time. The pseudo-code of the Youla decomposition is provided in Algorithm
Algorithm 4 Youla decomposition of low-rank skew-symmetric matrix procedure YOULLDECCOPPSSTION... D)
2:
(();,;), (1,, 2,) ) -- eigendecomposition of BB
3: for j = -,, K/2 do
4:
oy <- ImIm(,,) for j 1, 1,... K/2
5:
Im (z) 22)) y2j B (Re(zy) [Im(z,)
y2j-1 -- B (Re(z,)
6:
7:
Yj + // ||æ for =l..... K
8:
return {(o 12 y2;) |
K/2
15

---

Published as a conference paper at ICLR 2022
E PROOFS
E.1 PROOF OF THEOREM
Theorem For every subset Y S [M, it holds that det(Ly) S det LLy). Moreover, equality holds when the size of Y is equal to the rank of L.
Proof of Theorem 1. is enough to fix Y S [M such that 1 Σ |Y] - 2K, because the rank of both L and L is up to 2K. Denote k = | and (2x)) (T _ [K]] || = k) for h S 2K. We recall the definition L: given V, B, D such that L VV B DDD )BB let {(ps ) be the eigendecompposiionn of VVT and {(o,, V2j y22) 1==1
be the Youla decomposition of B(D DT Denote [11..... oK, y1,....... ................................ yk ] E RMx2K and
K/2
0
0
KK/22
X = diag ,.....PK:
01
KK/2
X = diag pl....,, PKi
01
ØK/2
01
0K/2
Applying the Cauchy- Binee formula twice, we can write the determinant of the principal submatrices of both and L:
so that L T
T and i Z
det(Lr) Σ
Σ
det(X,,)) det (Zx,)) det
(18)
TE(PR)) JE ((a)))
det(Ir)) = Σ
det(Xx,,)) det (et
IE 1E((K) ((x)
(2K1)
Σ
det(X det Zy
(19)
(E(P)))
where Eq. (19) follows from the fact that X is diagonal, which means that det X f,J) = 0 for 1 + J.
When the size of is equal to the rank of (i.e., k = 2K), the summations Eqs. (18) and (19)
simplify to single terms: det (Ly) = (dt((X] det( Zy..)² and det((y) = det( ()) det Zy Now,
observe that the determinants of the full X and X matrices are identical: det XX) = del X) K/2 II Pe I o3. Hence, holds that det Ly) det(Ey). This proves the second statement of
the theorem.
To prove that det(Ly)) S det( (L)) for smaller subsets Y. we will use the following:
Claim 1. For every J, E (12K)) such that det(( (.)) O, there exists a (nonempty) collection of subset pairs S(I,J) S (2K)) x (22k)) such that
Σ
det(X1,J) det (Zv.)) det Zv
Σ
det(S 1.1) det Zy.1)²
(20)
(P.J))ES(T,J)))
(PLJ')S((L.))
Claim 2. The number of nonzero terms Eq. (18) is identical to that in Eq. (19).
Combining Claim with Claim 2 yields
det(Ly)=
Σ det(Xx,,)) det(X det(Zy,)))))))) det (Zy.)
Σ det( dot (Zx,)) det dot(Lyy.
(.JE((K)))
TE(
We conclude the proof of Theorem 1. Below we provide proofs for Claim and Claim 2.
Proof of Claim 1. Recall that X is a block-diagonal matrix, where each block is of size either 1-by-1, containing Ps. 2-by-2, containing both o, and -o, in the form
0 o A submatrix -ay
X I k with rows 7 and columns J will only have nonzero determinant if contains
16

---

Published as a conference paper at ICLR 2022
all-zero column. Hence, any X1,J with nonzero determinant will have the following form (or some permutation of this block diagonaa)
Pp
0
0
to
X1,J
Io 1
dr.
rr
0
0
(21)
and denote pT. = {p1...., Pprt.... P1p QT.:==. (q1..... (Q...... 9/ and R = {ri...... Pl }. Indices p E pT. yield diagonal matrix with entries Pp. For such p. both I and J must contain index p. Indices r E RI yield a block-diagonal matrix of the form [-0. J. For such r, both I and must contain a pair of indices, (K + 2r 1, K + 2r). Finally, indices q E Q yield diagonal matrix with entries of toa (the sign be + -). For such q. contains K + 2q and J must contain the other. Note that there is intersection between QJ:J and R!...
K 24.
If Q is an empty set (i.e., I = J), then (et det( (.,) and
det (Xi,)) det (Zv,r) det (yyJ) = dett X det Zy
(22)
Thus, the terms in Eq. (18) in this case appear in Eq. (19). Now assume that Q + 0 and consider the following set of pairs:
S(I = (('' p p QQ = QU'""" R = R²"''.
In other words, for (I', J). the diagonal Xy contains Pp. [-- o. exactly as in Xy,J- However, the signs of the a, 's may differ from XI,J. Combining this observation with the definition of X.
Idet(X (det(X1,))) d)t(X,) ret(Xx)) det(X,) det (e)t(x)))..
(23)
Therefore,
Σ
det(Xr,,)) det (ex()
(24)
(P.J)SS(LJ)
<
Σ
[det(X det( (y.rr det( Zy.,')
(25)
(1(J)SSU)J)
())
Σ
det( Zx.1.) dot (Zy,
(26)
det((i))
Σ
det det(Zx..1))
(27)
(P,))ES(1,))
Σ
det( det 2
(28)
where the third line comes from Eq. (23) and the fourth line follows from the rearrangement inequality. Note that application of this inequality does not change the number terms in the sum. This completes the proof of Claim 1.
17

---

Published as a conference paper at ICLR 2022
Proof of Claim 2. In Eq. (19), observe that det(Xx)) det Zy,,)² 2 * Of and only if det(X,) * 0. Since all pt's and oj 's are positive, the number of I - [2 [T] k such that det(X, (X,) * is equal to (2k). Similarly, the number of nonzero terms in Eq. (18) equals the number of possible
choices of I, (ox)) such that (ett(X,,))) * O. This can be counted as follows: first choose i items in {0l, [p for i O,... , k; then, choose ý items in {1-2 o I.... - xx/2 } for j = O,..., - lastly, choose i 2j of (#0g: 4 & R!.'), J. then choose the sign for each of these (o,, -g)) Combining all of these choices, the total number of nonzero terms is:
K/2
K/2 - 2 t - 2j
Σ
(29)
choice of
choice of
d- -ar 0
choice of dior
k
K
Σ
(30)
k
-
1=0
(2
(31)
k
where the second line comes from the fact that (2n)
ا -
-
2- 2m for any integers
n, m E N such that m < 2n (see (1.69) in Quaintance (2010)). and the third line follows from the fact
that Ei (T) (.") ("+:") for n, m, N (Vandermonde's 's identity). Hence, both the number
of nonzero terms in Eqs. (18) and (19) is equal to (2K). This completes the proof of Claim 2. O
E.2 PROOF OF PROPOSITION
Proposition 1. The tree-based sampling procedure SAMPLEDPP in Algorithm 3 runs in time O(K + kad log M + k*), where k is the size of the sampled set" st
Since computing Pe takes Ok2)) from Eq. (12), and since the binary tree has depth (log M), SAMPLEITEM in Algorithm 3 runs in O log M) time. Moreover, the query matrix Q' can be updated (1a)) time as it only requires a k-by-k matrix inversion. Therefore, the overall runtime of the tree-based elementary DPP sampling algorithm (after pre-processing) is O(k3 log M + )=). This improves the previous O log M) runtime studied in Gillenwater et al. (2019). Combining this with elementary DPP selection (Line 15 in Algorithm 3), we can sample set in O(K + k33 log M + k4) time. This completes the proof of Proposition! 1.
Proof of Proposition
E.3 PROOF OF THEOREM
Theorem 2. Given NDPP kernel L VV + BB(D B for VBB RM K/2
V.BRRMKK D
R consider the proposal kernel L as proposed in Section 4.1. Let {az} be the positive
eigenvalues obtained from the Youla decomposition of B D D)BT. . 1 B, then dea(Lt det(L
K/2 11
20
2 Σ K/2 20, & (1 (1+ where w = K j=l off
E (0,1).
Proof of Theorem Since the column spaces of V and B are orthogonal, the corresponding eigenvectors are also orthogonal, i.e., ZT Z = 12k. Then,
det( L + I) det ZXz + I) det x Z + Iak) = det(X + I2k)
(32)
K
(pt + 1) II det ([ 0.
K/2
07 1
(33)
i=1
#=1
K
K/2
I 1=1
(px
+ 1)
II (o} 11)
(34)
3=1
tf'Comptiin pe via Fq. (12) improves Gillenwater al. (2019)'s O(** (ook<1og log M) runtime for this step.
18

---

Published as a conference paper at ICLR 2022
and similarly
K
R/2
det L + + = II
(os + 1)
II j=1
(a + 1)2.
(35)
i=1
Combining Eqs. (34) and (35), we have that
K/2
det(L I
K/2
11
K/2
20 of
K/2
20
del(L I)
II j=1
+0++1)
II
1
+1
<
1
K
+3
(36)
j=l
where the inequality holds from the Jensen's inequality. This completes the proof of Theorem
19


Reviews:
[{"review_id": "vJ7XdZOPGF6", "reviewer": "Reviewer_MEEx", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "The paper is well written, clear, and interesting to read. They are the first to give efficient algorithms for exact sampling from NDPPs (the previous sampling algorithm takes time cubic in ground set size, which is impractical for real-world data). Their work can lead to more applications of NDPPs in practical settings. It is also timely and adds to the growing literature on NDPPs.\n\nSome comments:\nFor equations 2 and 3 (and similar probabilities elsewhere in the paper which only involve singleton sets), it might help the reader if you use Pr$(i \\in Y\\ |\\ j \\in Y)$ rather than Pr$({i} \\subseteq Y\\ |\\ \\{j\\} \\subseteq Y)$. Also, for these specific equations, you mention that Poulson (2019) shows them via the Cholesky decomposition but that seems overkill. For these specific equations (2 and 3), you can just derive equation 2 by computing $\\frac{Pr(i,j \\subseteq Y)}{Pr(j \\subseteq Y)} = \\frac{\\det (K_{i,j})}{\\det(K_{j})}$ and equation 3 also by $\\frac{Pr(i \\in Y, j \\notin Y)}{Pr(j \\in Y)} = \\frac{Pr(i \\in Y) - Pr (i,j \\subseteq Y)}{Pr(j \\in Y)} = \\frac{\\det (K_{i}) - \\det (K_{i,j})}{\\det(K_{j})}$. It seems like Poulson (2019) uses LU decomposition (in Proposition 3 and 5) because their propositions are more general and apply to disjoint subsets (possibly having more than one element). Also, I'm not very familiar with these factorizations but seems like LU decomposition is different from Cholesky decomposition (at least from my understanding reading the wiki for Cholesky decomposition). Experts might be irritated by this (or maybe it's fine in which case, please let me know).", "summary_of_the_paper": "The paper provides efficient (linear time in item set size) algorithms for exact sampling from Nonsymmetric Determinantal Point Processes (NDPPs) using a new NDPP decomposition which was introduced recently in an ICLR 2021 Oral (Gartrell et.al) and also a learning algorithm to learn NDPP kernels which are more amenable to some of their sampling algorithms. They also provide empirical results comparing their learned kernels with previous works and compare times for their various sampling algorithms.", "summary_of_the_review": "Overall, I like the paper and recommend acceptance. This is the first paper to give efficient algorithms for exact sampling from NDPPs (which can be used in a variety of real-world applications like recommender systems etc) and thus this paper can have a good impact.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and 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": "hAWgLkvmspM", "reviewer": "Reviewer_Tzr3", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "This paper is overall well-written, easy to understand and both the theoretical and empirical results presented in this paper are very exciting.\n\nCompared to the linear-time Cholesky-decomposition-based sampler, the rejection-sampling-based method is definitely the main focus of the paper. Though the rejection-sampling method is not strictly sub-linear-time in general, the theoretical result presented in this paper (Theorem 2) directly implies that in practice, we can easily allow efficient sampling by bounding the expected # of rejections in learning NDPPs (ONDPPs); more importantly, the authors conducted comprehensive experiments to show that in learning NDPPs, by imposing the constraints (orthogonality & extra regularization term) we need for efficient sampling, we are not losing the expressive power of NDPPs. Experiments also show that compared to the linear-time sampling algorithm, the rejection-sampling method scales much better on both synthetic and real-world datasets.\n\nNDPPs are a strictly more expressive class compared to DPPs but the absence of efficient sampling algorithms puts a major barrier from replacing DPPs by NDPPs in large-scale applications. By proposing an efficient \"sub-linear-time\" sampling algorithm for NDPPs, this paper makes substantial progress in scaling up NDPPs and opens up new avenues for applying NDPPs to various real-world scenarios. \n\nCons:\n1. Compared to the rejection-sampling method, the linear-time algorithm is not as interesting and novel and somewhat deviating from the main story. Authors might want to consider presenting the linear-time algorithm without getting into the technical details. Of course, the experiments that compares the rejection-sampling method against the linear-time algorithm is still important.\n\n2. Section 4.2 is a little bit difficult to follow for those who are not familiar with the tree-based sampling algorithm for DPPs. Authors might want to expand this section a little bit.\n", "summary_of_the_paper": "This paper studies the problem of sampling from non-symmetrical Determinantal Point Processes (NDPPs); in particular, this paper focuses on exact sampling for low-rank NDPPs.\n\nThe main contributions of this paper are:\n1. This paper proposes to adapt the Cholesky-decomposition-based sampler for DPPs to a linear-time sampler for low-rank NDPPs (rank of NDPP << size of the ground set)\n2. This paper proposes to use rejection sampling to implement a \"sub-linear-time\" (assuming that the # of rejections are bounded by a small constant) sampler for a subclass of NDPPs called orthogonal NDPPs (ONDPPs), by leveraging an existing sub-linear-time sampler for DPPs.\n3. This paper shows that empirically, in terms of modeling real-world datasets, ONDPPs are as effective as the general NDPPs and more importantly, we can efficiently learn ONDPPs in a way such that when it comes to rejection sampling, the # of rejections is bounded by a small number.", "summary_of_the_review": "By proposing an efficient (sub-linear-time under certain assumptions) exact sampling algorithm for NDPPs, this work makes substantial progress in scaling up NDPPs to real-world applications. This paper is overall well-written and easy to follow, and it also demonstrates a decent amount theoretical novelties.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and 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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "f1YZ9lUd8yN", "reviewer": "Reviewer_ccEk", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "The paper is well-written. Even though it is a somewhat straightforward mix of ideas from Gartrell et al. (motivating such NDPPS), Gillenwater et al. (sublinear sampling algorithm of symmetric DPPs), and Poulson (Cholesky-based sampling of DPPs and NDPPs); I believe that the results are interesting enough for acceptance. The main contribution of the paper is, to my eyes, to have found a symmetric DPP that is well-suited for rejection sampling. The proof that $\\forall Y, det(L_Y)\\leq det(\\hat{L}_Y)$, essential for the rejection sampling framework to work, is an interesting contribution (and could be used in other works on DPPs as well). In passing, I find the proof hard to follow and suggest to the authors to do their best to find ways of simplifying it as much as possible for the camera-ready version. The simpler the proof, the more easily it could be transferred to other scenarios, increasing the potential impact of the paper.\n\nAs for Theorem 2, the orthogonality constraint is frustrating and I would imagine that further efforts could lift this constraint and obtain a bound that depends on how orthogonal both subspaces are (and recovering the current bound when they are indeed orthogonal). On the other hand, ONDPPs can indeed be motivated for learning as they indeed ensure that the full \"available rank\" is put to contribution. The empirical results tend to validate this intuitive argument.", "summary_of_the_paper": "This paper gives an exact sampling algorithm to sample from DPPs based on non-symmetrical, low-rank, kernel matrices of the form $L=VV^\\top + B(D-D^\\top)B^\\top$ where $V$ and $B$ are of size $M$ by $K$ and $D$ is square, non-symmetric and of size $K$ by $K$. The marginal kernel of such a DPP may be written in the form $K=ZWZ^\\top$ with $Z$ a $M$ by $2K$ matrix and $W$ a square matrix of size $2K$ that is not symmetric. The authors then:\n- discuss in Section 2 how Poulson's algorithm is adapted to sample from such NDPPS\n- in Section 3: show that, as L is low-rank, the generic $O(M^3)$ cost of Poulson's algorithm can be reduced to $O(MK^2$ as updates of the marginal kernel can be efficiently done by only updating the inner $W$ matrix\n- in Section 4: give a sublinear-time rejection-sampling based algorithm adapting the tree-based algorithm of Gillenwater et al. In this section, they:\n\t* propose a well-adapted, DPP based on a symmetric kernel $\\hat{L}$ that is easy-to-sample (it is a DPP based on a symmetric PSD kernel and can be sampled from many different fast existing algorithms), and for which any set $Y$ verifies $det(L_Y)\\leq det(\\hat{L}_Y)$ where the upper-bound is actually attained (Thm 1). In order to exactly control the rejection rate of their proposed algorithm (that is equal to $det(\\hat{L}+I) / det(L+I)$, the authors simplify the model by supposing that $V$ and $B$ are orthogonal to each other (Thm 2)\n\t* in passing, the authors observe that the complexity of Gillenwater et al's algorithm can in fact be easily improved by a factor $k$ where $k$ is the size of the sampled set \n- in Sections 5 and 6, experiments are provided comparing their samping method with the state-of-the-art", "summary_of_the_review": "All in all, the small lack of true originality is compensated by two useful theorems that can prove useful to the community.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and 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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "YD9bu96vyR", "reviewer": "Reviewer_uhQa", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "This paper proposes two scalable sampling algorithms for NDPPs, one for low-rank kernel, and the other for low rank orthogonal kernel. The efficiency of the proposed algorithms are verified through experiments, and the predictive performance is not degrade. This paper is well written, and the studies could benefit relevant researches on NDPPs.\n\nI have some minor comments which should be easy to fix or answer:\n- For Equ (4) and Equ (5), please give a definition of ${\\bf z}_j$.\n- In section 4.1, the eigendecomposition of ${\\bf V}{\\bf V}^T$ is not used in Algorithm 2. Could we remove it to avoid the confusion?\n- In section 4.1, the dimensions of $\\bf Z$ and $\\bf X$ do not match when K is odd.\n- In section 5, could you elaborate on why if ${\\bf V}\\not\\perp{\\bf B}$, $\\bf L$ will have rank $<2K$? What happens if ${\\bf V}={\\bf V}_1+{\\bf B}$ where ${\\bf V}_1\\perp{\\bf B}$?\n", "summary_of_the_paper": "This paper studies scalable sampling methods for NDPPs:\n- By assuming low-rank structure of the kernel, the paper proposes a linear-time sampling method, which is faster than previous sampling algorithm with cubic runtime for general kernel.\n- Furthermore, this paper develops a scalable sub-linear-time rejection sampling algorithm for a subclass of low-rank NDPPs that are called ONDPPs.\n- Through experiments, it is shown that the predictive performance of ONDPPs is not degraded compared to NDPPs. By adding a regularization term in the optimization, the rejection probability is greatly reduced.", "summary_of_the_review": "Overall I think this is a well written paper. My only concern is that the more scalable sampling algorithm is achieved by imposing more restrictions on the kernel, which might limit its usage. However, this might not be a big issue because it is shown in the experiments that its predictive performance is not degraded.", "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": {}}]

Author rebuttal:

Meta-review: This is an exciting paper that provide the efficient algorithms for exact sampling from NDPPs along with theoretical results that are very pertinent in and out themselves. The AC agree with the reviewers that the authors satisfactorily addressed the concerns raised in the reviews, and is convinced that the revised version will be greatly appreciated by the community. We very much encourage the authors to pursue this line of work and in particular to overcome the practical restriction to the ONDPP subclass.
Decision: Accept (Spotlight)