Lazy and Fast Greedy MAP Inference for Determinantal Point Process
Authors: Shinichi Hemmi
Taihei Oki
Shinsaku Sakaue
Kaito Fujii
Satoru Iwata
Venue: NeurIPS 2022 Accept (2022)
Keywords: determinantal point process
maximum a posteriori inference
submodular function maximization
greedy algorithm
Cholesky factorization

Abstract: The maximum a posteriori (MAP) inference for determinantal point processes (DPPs) is crucial for selecting diverse items in many machine learning applications. Although DPP MAP inference is NP-hard, the greedy algorithm often finds high-quality solutions, and many researchers have studied its efficient implementation. One classical and practical method is the lazy greedy algorithm, which is applicable to general submodular function maximization, while a recent fast greedy algorithm based on the Cholesky factorization is more efficient for DPP MAP inference. This paper presents how to combine the ideas of ``lazy'' and ``fast'', which have been considered incompatible in the literature. Our lazy and fast greedy algorithm achieves almost the same time complexity as the current best one and runs faster in practice. The idea of ``lazy + fast'' is extendable to other greedy-type algorithms. We also give a fast version of the double greedy algorithm for unconstrained DPP MAP inference. Experiments validate the effectiveness of our acceleration ideas.

Lazy and Fast Greedy MAP Inference for Determinantal Point Process
Shinichi Hemmi
Taihei Oki
The University of Tokyo, Tokyo, Japan hemmi shinichi@gman com
The University of Tokyo, Tokyo, Japan oki Cmiitmiiii....................im i.uto.yyo..oo..... ac. jp
Shinsaku Sakaue
Kaito Fujii
The University of Tokyo, Tokyo, Japan sakaue@mist. wwt.::.......ooooo u-tokyo. ac.
National Institute of Informatics, Tokyo, Japan jc.jp
Satoru Iwata
The University of Tokyo, Tokyo, Japan ICReDD, Hokkaido University, Sapporo, Japan iwatammist. i. w-tokyo...... jc.
Abstract
The maximum a posteriori (MAP) inference for determinantal point processes (DPPs) is crucial for selecting diverse items in many machine learning applications. Although DPP MAP inference NP-hard, the greedy algorithm often finds high- quality solutions, and many researchers have studied its efficient implementation. One classical and practical method the lazy greedy algorithm. which is applicable to general submodular function maximization, while recent fast greedy algorithm based on the Cholesky factorization is more efficient for DPP MAP inference. This paper presents how combine the ideas of "lazy" and "fast", which have been considered incompatible in the literature. Our lazy and fast greedy algorithm achieves almost the same time complexity practice. The idea of "lazy fast" is extendable to other greedy-type algorithms. We also give fast version of the double greedy algorithm for unconstrained DPP MAP inference. Experiments validate the effectiveness of our acceleration ideas.
the current best one and runs faster in
1 Introduction
Determinantal point processes (DPPs) offer a popular diversification model in machine learning. Macchi [34] first used DPPs represent repulsion in quantum physics, and later, DPPs have been used in various scenarios such as recommendation systems [13], document summarization [21, 31], and diverse molecule selection [39]. An important problem in the DPP applications the maximum posteriori (MAP) inference, which asks to find an item subset with the highest probability. Intuitively, each item associated with vector whose length and direction represent its importance and feature, respectively, then the aim of DPP MAP inference is to select items whose vectors form the largest volume parallelotope, thus selecting important and diverse items.
In DPPs, exact MAP inference is NP-hard [27]. Fortunately, however, the standard greedy algorithm (Greedy) for submodular function maximization [41] enjoys in terms of the log-determinant function value under the monotonicity assumption, and it often finds high-quality solutions in practice. naive implementation of GREEDY, however, incurs too much computation cost for large instances since evaluating the determinant of & x & matrix takes O(k))
approxxmxxiiioo guarantee
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

time, where w' E [2.3] is the matrix- muttiiiiultiiiiiaaiionn exponent (usually w 3). To overcome this issue, researchers have studied techniques for implementing efficient greedy algorithms. One classical and powerful method is the so-called lazy greedy algorithm (LAZYGREEDDY [37], which avoids the redundant computation of function values by making good use of the submodularity. LAZYGREEDY is applicable to submodular function maximization, and it empirically runs much faster than naive GREEDY, although the worst-case running time is not improved. Chen et al. [13] proposed another notable pagllesk--factoiizatiiin
method, called the fast greedy algorithm (FASTGREEDY), Their algorithm is specialized for DPP MAP inference and provides the fastest (kkdd) implementation of GREEDY for selecting & out of items represented by d-dimensional vectors. Chen et al. [13] also experimentally showed that FASTGREEDY can run faster than LAZYGREEDY.
Since the study of [13], although a pre- pre-processing method for customized DPP MAP inference [23] and fast parallel algorithms for submodular function maximization [3, 4, 18, 8. 17, 14, 29] have been studied, no progress has been made that directly accelerates GREEDY for DPP MAP inference. Since real-world dataset sizes have been growing, a further speed-up of GREEDY eagerly awaited.
Our main contribution is to combine the two ideas, "lazy" and "fast", to develop an even faster implementation of GREEDY for DPP MAP inference, which we call LAZYFASTGREEDY, In the literature, the two ideas have been thought to be incompatible; in fact, experiments in [13] compared FASTGREEDY with LAZY without considering their combination. The core idea of "lazy + fast" is widely applicable to other greedy-type algorithms. Below is a summary of our results.
1. We present LAZYFASTGREEDY for cardinality-constrainee DPP MAP inference. It takes O(kn(d+log n)) time even in the worst case and is faster than FASTGREEDY in practice. We also extend the idea of "lazy + fast" to other greedy-type algorithms: RANDOMGREEDY [10],
STOCHASTICGREEDY [38, 43], and INTERLACEGREEDY [28].
2. We present a "fast" version of DOUBLEGREEDY [11] for unconstrained DPP MAP inference by extending the idea of [13] with Jacobi's complementary minor formula.
3. Experiments on synthetic and real-world datasets validate the empirical effectiveness of our acceleration techniques for the greedy-type algorithms. particular, our LAAZFAAT-- GREEDY runs up to about 17 times faster than FASTGREEDY in real-world settings.
Accelerating the greedy variants [10, 38, 28, 43], which enjoy approximation guarantees for non- monotone submodular function maximization, is worthwhile since the log-determinant function is non-monotone in general. Also, note that both cardinality-constriinn important in DPP MAP inference and require substantially different technical ideas. Therefore, we study the fast version of [1 I] separately from the algorithms for the cardinality-constraine setting, In short, we accelerate various important greedy-type algorithms for DPP MAP inference.
and unconstrained settings are
1.1 Related work
The greedy algorithm (GreEDy) is a popular approach to DPP MAP inference [31]. Han et al. [24] gave a fast but inexact implementation of GREEDY. Later, Chen et al. [13] gave exact implementation of GREEDY with the same time complexity as that of [24]. Han and Gillenwater [23] studied special cases where kernel matrices of DPPs generated via customization (or re- weighhttngg) of fixed feature vectors and developed a pre- pre-processing method for accelerating GREEDY. Note that this pre- pre-processing usually takes longer than the algorithm of [13] (see [23, Section 4J), while their algorithm after pre-processing is much faster. In summary, the algorithm of Chen et al. [13] has been the fastest greedy-style algorithm for general DPPs.
based 1/ 1/4aapprxiimation algorithm for general down-closed constraints was also studied [21]. Our implementation I INTERLACEGREEDS [28] yields a faster 1/ //d-approximation algorithm for a special case with a cardinality constraint. Approximation algorithms and inap- proximability results of DPP MAP inference (without log) have also been extensively studied [15, 35, 36, 6, 42]. Sampling is another important research subject in DPPs and has been widely studied [2, 33, 16, 22, 1, 12, 32]. Also, we leave extension of our algorithms to non-symmetric DPPs [20], which have recently gained increasing attention, for future work.
continuous-relaxate
Since the log-determinant function is known to be submodular [19], DPP MAP inference has close connection to submodular function maximization [41]. Besides LAZYGREEDY, STOCHASTIC- GREEDY [38, 43] is popular fast variant of GREEDY, which we will discuss later. A recent line of

---

work [3, 4, 18, 8. 17, 14, 29] has studied adaptive algorithms for submodular function maximization, where we are allowed to execute polynomially many queries in parallel to reduce the number of sequential rounds. Those studies consider oracle models of submodular functions, whereas we focus on the log-determinant functions and develop fast algorithms without such parallelization.
2 Background
Let [n] denote the set 21, for any E N. For any S C [n), 3 denotes its complement [n] \ S. We use O and O as all-zero vectors and matrices, respectively, and 1 as all-ones vectors (their sizes will be clear from the context). Let (., denote the inner product. For matrix L E R=*= and subsets S,T _ [n]. L(S, T is the submatrix of L indexed by S in rows and T in columns. For brevity, write [i,
[[ S] for any i E [n] and 5 S [n]- The determinant of L is denoted by det L. Set det L.00] = 1 by convention. For any M E R=xn, we suppose that M M is computed in O time, which implies that we can compute det M and M (if non-singular) in O(n)) time (see, e.g., [7, Chapter 2)).
T. [(), [1] L[S] L|SS, 5),, T.[S, i]
T.S,, ((]), and [
DPP MAP inference. Let L E Ruxn be positive semi-definite matrix. A probability measure P on 2 is called a determinantal point process (DPP) with a kernel matrix L if P[x S x det L[S] holds for all S S [n]] MAP inference for DPPs is the problem of finding a subset S [r]] with the largest det L[S] value. We suppose that each i E [na] is associated with vector Φ Rd and that a kernel matrix L. E R is given L B B, where B = [ $2...., Φn) E R i.e.,
L.j (Ø:, Φ5) for i.j [n]. Note that /det L[S] represents the volume of the parallelotope spanned by (Ø; E S}. Hence, if the length and direction of o indicate i's importance and feature, respectively, the larger value of det T.[S] implies that S contains more important and diverse items. In many situations, we want to select a limited number of items; let l E N denote the upper bound. Therefore, MAP inference for DPPs with cardinality constraint, k-DPP [30], is often considered. Note that since rank L S. min d}, we can assume k S min d} without loss of generality.
Submodular function maximization. For set function f: 2 R U fo--t-p {-oo), the marginal gain of E [x]] with respect to S S [n]] is defined by f((5) = f f(S - f(S). A set function f: 20) + IR U { {- is called monotone if (i(S) 2 for every SC [n] and i E
called
submodular if it has the diminishing returns property: ((() 2 S(()) for every S T C [n] and i E T. Since f(S) log det L[S] is submodular, DPP MAP inference can be written submodular function maximization: maxsex (S), where X' C 2 is family of feasible subsets. This paper mostly considers the eardinality-constraln
setting, i.e., X {5 C [M] ||| S k) for given N; in Section 4, we study the unconstrained setting, i.e., X 2|m The log-determinant function f is monotone if the smallest eigenvalue of L is at least (see, e.g.. [44]), but this is not always the case.
is well-known that the greedy algorithm (GREEDY) enjoys a (1 1/ppa-pproiiiittinnnn guarantee for constriinn monotone submodular function maximization with f(0) 2 0 [41]. This approximation ratio is optimal under the evaluation oracle model [40]. GREEDY works as follows:
setting 5(0) = 0. in each ith step (t = 1,..., k), choose jr E arg max (((((=1))) | i 5((-1))
and put 5(() ((t U (je). We call solution obtained in this way greedy solution.
Besides GREEDY, many algorithms [11, 10, 28, 43] achieve constant-factor approximations for submodular function maximization. These results motivate us algorithms to DPP MAP inference, although constant-
wwwpllyyycootttanned/nnnosssssss to apply www.rllarrfuunnttomaaaaaeeee factor approximations of the log- deg-deeermnnnnt value do not imply those of the determinant value.
2.1 Lazy greedy algorithm for submodular function maximization
LAZYGREEDY [37] is an efficient implementation of GREEDY for submodular function maximization. As explained above, GREEDY finds j. by computing marginal gains ((((tt))) for all i 1(1-1) LAZYGREEDY attempts to find je more efficiently by keeping an upper bound p; on f((S(t-1) for
each i ((t-1), which is old marginal gain, i.e., P: (((())) for some u; - 1. In each
Strictly speaking, this is the so-called L-ensemble DPP, but we here call it DPP for simplicity.
3

---

Algorithm 1 FASTGREEDY [13) for cardinality-constrained DPP MAP inference
1: V < O, d0 & T (Vi E [ml), ((0) t- 0
2: for t = k do
3: Take je E arg max, seSt-TT de d((-1)
P Terminate if d(-1) < 1 (i.e., (S(t- S 0)
4:
5(() + S (
Stt) = Un. ..................... Jr3
5: for in 5 do
> Skip Lines 5-7 (updates for the next step) if / k
6:
Vi - (In - (ili,,ut-11) V s(t-1())) (t-1) /
V(i,0) = 0 for any i E [n]]
dl0 + V /a(h- Visa
7:
8: return S(R)
b Return S(+ if terminates with t <
iteration, LAZYGREEDY picks E 50-11 with the largest pi value as the most promising element. then updates the pi value to the latest marginal gain fi (((())))) If ps is still the largest among pr for E 5(t-1) J.
all i' E 5)+-1), the diminishing returns property guarantees i E arg max fo (S(t-1)) and hence adds j: i 5(t-1), LAZYGREEDY thus constructs greedy solution, deferring updates of upper bounds of unpromising elements. If the upper bounds are managed by a priority queue, every single iteration computes the marginal gain only once and makes O(log n) comparisons (note that "iteration" is distinguished from "step" of GREEDY), With this contrivance, LAZY runs much faster than GREEDY in practice, even though it does not improve the worst-case complexity.
2.2 Fast greedy algorithm for DPP MAP inference
We turn to DPP MAP inference with kernel matrix L= B B and B E Rdx= If we apply GREEDY to f(S) = log det [[S], it takes O(k=+)n) n) time since computing an f value takes O(k)) time; in addition, computing T. at first takes Ommin(n nn2-lddn2d~-27 2²)==2) time. FASTGREEDY [13] provides an (knd)--imme implementation of GREEDY for cardinality
DPP MAP inference.
Algorithm describes the procedure of FASTGREEDY, which is based on the Cholesky factorization of L with maximum pivoting. The Cholesky decomposition produces a matrix V E R=x= such that L= VVT and PV is lower triangular for some permutation matrix P. We call V a Cholesky of L. In each 7th step, Lines 5-7 calculate the 7th column of PV via backward substitution (see Fig. la). The following Proposition 2.1 implies important fact that once V(ž S(0) is filled,
can obtain (S(()) from d!") computed Line 7, which equal to the diagonal V of the current Cholesky factor. Although the proposition is already proved in [13], we present proof sketch since it would be helpful to understand the subsequent discussion (see [13] for the complete proof).
Proposition 2.1 ([13)). For L = 0, 1,....... A 1, it holds that fi (S(0) 2 log d," for every E S(0)
Proof sketch. The proof is by induction on t. If 0, it holds that f((())) f(fi)) f(0)
log L,,; = 2 log d:0) for i E [m]. Given Cholesky factor V[S(") of L[S(O], for i E SKt), we have
L [ ([iis(o)
L[SW,0 o] Li,4
Vis(1) = Via s()
1
T VISWOT
Vii, Vii
L U [iH =
d(0
d(1)
O
Hence, we have log det L[$() U (i)) log (d!) det V ViS(1)) 2 2 log d. + log det L[S()), which implies log det Il(S(t) U {i}] - log det L[S = 2 log (( Thus, the statement holds. O
Therefore, by iteratively adding j. E arg max () d²-1)) to S(t-1) in Algorithm 1, we can obtain a greedy solution. Since Tz.j, = ( )b is computed in O(d) time and 2 k; Line 6 takes Od) time. This is repeated O(km) times, hence the total time complexity of O(knd).

---

[V)
[V)
t
PV
PV
(a) FASTGREEDY
(b) LAZYFASTGREEDY
Figure I: Images of Cholesky factors computed by FASTGREEDY and LAZYFASTGREEDY, Off- diagonals are shaded they are already computed, and arrows represent the direction which the computation of off- fff-diagonals proceeds. Diagonals are shaded if they give the latest marginal gains, each of which becomes available once | off-diagonals in the same row are computed (shaded). Diagonals with bold lines correspond elements that already selected.
3 Lazy and fast algorithms for cardinality-constraile DPP MAP inference
3.1 Lazy and fast greedy algorithm
We combine LAZYGREEDY and FASTGREEDY to obtain even faster LAZYFASTGREEDY.
As described above, LAZYGREEDS is designed for submodular function maximization under the oracle model, where marginal gain is computed for each E 5((-1), Meanwhile, the core idea of FASTGREEDY is to obtain marginal gains of all i E g efficiently by computing a new column of a Cholesky factor, in Fig. la. To combine these seemingly incompatible methods, we need to take closer look at how FASTGREEDY updates the entries in V. The following observation is obvious but elucidates the essential row-wise independence of the updates of Cholesky-facee factor entries.
Observation 3.1. each tth step in Algorithm for each E S(0,, ViJ. in Line 6 is computed from d'-"",, Li.j and (Hi S s(t-1)), Thus, conditioned on 5(t), the ith row of V(S()), s can be updated independently for each E SU) in a sense that computing Vr.j, only requires Vase for t' and VlJe, S(t-1)], which is included in the already fixed Cholesky factor V[S(0).
That is, in Fig. 1b, once (PV) is fixed, we update the ith independently for each Sir) In the words of submodular function maximization, we can compute ft ((())) if fjp (s(t'-1) and fa f(((te-1) for t' I available. This enables us to apply the idea of lazy updates to FASTGREEDY.
Algorithm describes our LAZY FAZYFASTGREEDD, and Fig. 1b illustrates how entries in V are updated. In each iteration, it picks the most promising element in Line 3, as with LAZYGREEDD Then, it calls UPDATEROW to compute the entries of Vli, S] via backward substitution. Once Vli, S] filled, the resulting d, computed in Line 12 satisfies 2 log d, = f.SS) by Proposition 2.1, thus obtaining the latest marginal gain of i. Lines 5-7 check whether the latest f(()) is still the largest among the (old) marginal gains of i' E S; if so, jis = i added to S. Note that the deferred updates of de (i' E S (i}) do not matter when deciding whether to add i to S due to the submodularity. Here, d (d1, (di...., dn)) plays the role of upper bounds (Pi..... Pa) of LAZYGREEDY and is maintained by priority queue. LAZYFASTGREEDY thus finds a greedy solution by exactly mimicking the behavior of LAZYGREEDY while computing marginal gains efficiently as with FASTGREEDY.
The vector u = (u)...., U,,) keeps track of when the upper bounds are last updated: specifically, each wy (0, 1, 1,..., k 1} indicates that the upper bound d, is last updated with respect to (ú (ji,..-JJv.] ie., 2 log d4 fe((fi....... )) Since UPDATEROW starts to fill Vli, S] from the (ug + 1)st entry, off-diagonals Vi,j. computed more than once in Line 11. Thus, the complexity of Algorithm depends on the number of computed off--iagonall We denote it by u = Eie
(m) Un with u, values at the end of Algorithm 2. The value changes in the range of [k:A 1)/2, k 1) k/2)] depending on how well the lazy update works and affects the overall time complexity as follows.
5

---

Algorithm 2 LAZYFASTGREEDY for cardinality-constriined DPP MAP inference
V 7, - (oudd((LL.)) (VL.,))iEo) iE|m)' u 0, -
d is maintained by a priority queue
2: while [S| < do
3: Take E arg y
D Terminate d, S (i.e., Si(S) - 0) Nothing is done if [S] = Otherwise insert d; into the priority queue
4: UPDATEROW(V, d, u; L)
5: if d 2 pa dy then
6: jss+1 6
7: S +1
8:
return S
9: function UPDATEROW d, u: S.
D {ii. f2. ................................ J b s(r-1) (i.,...,
10:
for 1= +1, + 2, 2........ |......|111111 do
Vij, t (In (V 11) Víj.. s((-
12:
di x v di² - Vi.ee
13:
Uj - |S|
This line is not needed in Algorithm
Theorem 3.2. Algorithum 2 returns greedy solution in O(nd uld n)) time. If the lazy update works best and worst, it runs in O((n + dd) and Okkn(d + logn)) time, respectively.
Proof. Algorithm returns greedy solution as explained above. We below discuss the running time.
At the beginning, we need (ndd) time to compute Li,- (.), for = 1,... n. In UPDATEROW, access Ix.j, in Line 11 takes O(d) time, and the inner product takes O(k) (S O(d) time. This computation is done u times, and thus the total computation time caused by UPDATEROW is O(ud). In Line 5, we need (log π²) time to update the priority queue de < es dy, which can hold only when at least off- off-diagonal is computed in UPDATEROW. Therefore, Line 5 takes O(u log time in total. Thus, the overall time complexity is O(nd + u(d + n)).
Let S be the output of Algorithm 2 and P permutation matrix such that (PV)[S) is lower triangular. In the best case, UPDATEROW is called up to times and u = k(k - 1)/2 off-diagonals of (PV)[S computed. Moreover, updates of the priority queue are done only up to & times, taking O(k log
(S O(nd) time in total. Thus, it runs in O( h22 )d time. In the worst case, Algorithm calculates the off-diagonals of [SV and all the entries V 13 S\ {ikJ]; the total number of those entries is
l: 1)/2 + (k- (n k) (k- 1) k/ 2/2 Hence, takes O(kn(d log n:) time. O
The best-case time complexity is better than (kkdd) of FASTGREEDY if k o(n). Even in the worse case, is as fast as FASTGREEDY d 22 n). Note that both i = o(n) and d (log are true in most practical situations. Experiments in Section demonstrate that LAZYFASTGREEDY can run much faster than FASTGREEDY in practice.
3.2 Extension to random, stochastic, and interlace greedy algorithms
The core idea of LAZYFASTGREEDY can be used for speeding up other greedy-type algorithms: RANDOMGREEDY [10], PROCHASTICGREED [38, 43], and INTERLACEGREED [28], which enjoy 1/e- 1/4-, and 1/ 1/4-approximation guarantees, respectively, for non-monotone submodular function maximization with a cardinality constraint. Note that the guarantees for the non-monotone case are essential in DPP MAP inference since the log deg-determinant function is non-monotone in general. Due to the space limitation, we present the details those extensions in Appendix A.
4 Fast double greedy algorithm for unconstrained DPP MAP inference
This section discusses unconstrained DPP MAP inference with a kernel matrix L = B, where B E RRdxn, In this setting, if /(S) log det [[ is monotone, S = [n) is trivial optimal solution. Thus, we suppose to be non-monotone. We also assume I. to positive definite since the algorithm of [11] discussed below requires f(S) -co for any S C [n]. Note that this implies d > n.

---

Algorithm 3 FASTDOUBLEGREEDY for unconstrained DPP MAP inference
1: Compute I. -= B and I.-1
2: V < O, W 0, d < (v semp et (V(L-))
S f 0
sE|n]
3: for i= 1 to n do
4: UPDATEROW(V d. d,
D S is sorted in order of 1, 1.2.....
.., n
5: UPDATEROW(W,eC e, 0; [i] )
>
M
\ S is sorted in order of 1,2, ,....,
6: a; f m log d, 0}. b, f- max ei, 0}
7: S+ (1} w.p. 0:/ (a: b.)
Implicity update T [m] \ S w.p. bz/(a; + bi)
8: return S
famous algorithm for unconstrained submodular function maximization is DOUBLEGREEDY [11], randomized 1/2 12-approximation algorithm. Although it calls an evaluation oracle only O(n) times, its naive implementation is too costly for large DPP MAP inference instances since computing the log- determinant function value takes O(n²) time, which will lead the total time of O(n"-1d -d n=+1) We below extend the idea of FASTGREEDY [13] to DOUBLEGREEDY and obtain its O( d n²)- time implementation for unconstrained DPP MAP inference.
DOUBLEGREEDY maintains two subsets and T, which are initially set to S 0 and T = [n]. For i = 1, .,.., n, it computes a; (S) 0} and 6; max{-fi {i)), 0}. and then either adds to 5 with probability a. a./(a;+b)) b,) or removes from T with probability b,/ b.). Note that T = [n] (f)) S) = [i] \ S always holds. Finally, it returns S (or equivalently T = [^] S = S).
As for the growing subset S, we efficiently compute marginal gains fi(S) by incrementally updating a Cholesky factor, as with FASTGREEDY. When it comes to the shrinking subset T. however, cannot directly naively compute it in each step, it takes O(n") time, resulting in the same time complexity as the naive implementation. Our key idea for overcoming this difficulty is to use the following Jacobi's complementary minor formula (see, e.g., (9)).
the efficient incremental update for computing - ff, {t)). If we
Proposition 4.1. Let L E x be non-singular matrix and 1, S [m]] be subsets with / ||| Then, it holds that det L J] = (-1) Jes det det [T,]
This formula provides lemma that enables us to compute (f: \ {i)) via incremental updates.
Lemma 4.2. Let L E Rax= be positive definite. For any S C [n)) define f(S) = log det L[S] and
(SS) = log det L [S]. Then, g(S (i)) g(S) = f(S \ {i}) - f(S) holds for any S C [n|] and
2 E [n].
Proof. By using Proposition 4.1, we can prove the claim as follows:
f(3 (i)) - f(5) = log det L[3 {i}] - log det L
log det L det L [ (S \ {+})] - log det L det L
[[x]]] ()
let [5- (i)) log det I, (
USU -(}))
Lemma 4.2 implics g(([i] \ S) U (i}) - [[{] S) f(i] (1)
f(T))
= (T)).
Therefore, by computing = B B and I-1 in O(n--ld) 12 O(n))) time in advance, we can compute -f( (i}) in each step by incrementally updating a Cholesky factor of size [[]] S).
Algorithm presents our FASTDOUBLEGREED second calls to UPDATEROW, defined in Algorithm 2, fill V S] and W [t, [o] \ S). respectively.
based on this idea. In each ith step, the first and
Hence, Proposition 2.1 and Lemma 4.2 imply 2 log dj (S) and 2 log e; ([ \ () = - f().. Thus, Algorithm 3 exactly mimics the behavior of DOUBLEGREEDY while efficiently computing marginal gains via incremental updates of Cholesky factors. UPDATEROW defined in Algorithm since I, and - are already computed, each V.,, is calculated in O(n) time; therefore, a single call to UPDATEROW takes O(n²) time. Since UPDATEROW is called 2n times, Lines 2-7 construct solution in ( time. In total, Algorithm runs in 0(n n²) time.
"The algorithm thus sequentially examines all elements, and hence there is room for the lazy update.
7

---

5 Experiments
We evaluate the effectiveness of our acceleration techniques on synthetic and real-world datasets. Section 5.1 examines speed-ups of GREEDY for cardinality-constrannee DPP MAP inference, and Section 5.2 focuses on DOUBLEGREEDY for the unconstrained setting. We present experimental results RANDOMGREEDY, STOCHASTICGRREEDY, and INTERLACEGREEDY in Appendix A.4.
The algorithms are implemented in C++ with library Eigen 3.4.0 for matrix computations. Exper- iments are conducted using a compiler GCC 10.2.0 on computer with 3.8 GHz Intel Xeon Gold CPU and 800 GB RAM.
We use synthetic and two real-world datasets, Netflix Prize [5] and Movielens [25]. Each dataset provides a matrix B _d consisting of column vectors Φ1, ....... .,. Dn E R of n items, which defines an n X n kernel matrix L = B B. Below we explain the item vectors of each dataset.
Synthetie datasets. We use the setting of [21]. Each entry of d, E I is independently drawn from the standard normal distribution, 0ij ~ (0, 1). As result, the kernel matrix L conforms to Wishart distribution with n degrees of freedom and an identity covariance matrix, i.e., ~ W(T, n, n). We consider various n values in the experiments below, and we always set the vector length d to
Real-world datasets. Both Nerflix Prize and Moviel datasets contain users' ratings of movies from one to five, where we regard movie as an item. Following [13], we binarize the ratings based on whether it is greater than or equal to four. After that, we eliminate movies that result in all-zero vectors and users who result in all-zero ratings since those are redundant. Consequently, the Netflix Prize dataset has π = 17770 movies and d = 478615 users with 56919190 ratings; the MovieLens dataset has n = 40858 movies and d 162342 users with 12452811 ratings.
B- and L-input settings. is important to care about whether L B B3 computed in advance or not. In practice, a matrix B E RR of item vectors is often given. Then, computing L = B B in advance takes O(min (mminnn=-dd, n d-))) time, which we should avoid when n large since the running time of LAZYFASTGRERT hand, we are sometimes given a pre-computed kernel matrix L, and we can access Li,, in ((1) time.
(and FASTGREEDY) increases only linearly in n. On the other
We below consider both settings, called B- and L-input settings, respectively. In the L-input setting, we exclude the time to compute I, = B B from consideration. Under this condition, FASTGREEDY takes O(k2n) n) time and LAZYFAST FASTGREEDY does O(n + u(k + log n)). where the first O(n) term is for constructing priority queue. By similar reasoning to that in the proof of Theorem 3.2, it runs in Onn + 13 + k log n) and (kn((k- + log n)) time if the lazy update works best and worst, respectively,
5.1 Greedy algorithm for cardinality-constrained DPP MAP inference
We compare the running time of GREEDY, LAZYGREEDY, FASTGREEDY, and LAZYFASTGREEDY, which we here call Naive, Lazy, Fast, and LazyFast, respectively, for short. As regards synthetic datasets, we consider two settings that fix either n or k: (i) n 6000 and k: = 1, 21.,.... n. and (ii) k 200 and = 1000, 2000. ... 10000. We set the timeout periods of (i) and (ii) 3600 and 60 seconds, respectively. Regarding k 1.2,..... n. We set the timeout period to 3600 seconds. With the Netflix (MovieLens) dataset, the objective value peaked with k = 17762 (k- = 18763), and thus we stopped increasing k after that.
datasets, n is fixed as explained above and we increase
Figures 2 and 3 present the results on synthetic and real- real-world datasets, respectively. The curves in the runtime figures represent that faster algorithms can return greedy solutions to instances with larger A values within the timeout periods. The rightmost figures present the number of off-diagonals of Cholesky factors computed by Fast and LazyFast. As explained in Section 1. while Fast always computes all the off-diagonals of V[[ra] SJ. LazyFast does not due to the lazy update.
LazyFast was the fastest in all the settings. particular, in the synthetic (ii) and wolld settings, LazyFast computed fewer off-diagonals than Fast, thus running the fastest. In the synthetic setting (i), although LazyFast computed almost all off-diagonals example, for the I.-input setting with k- = 6000, Fast and LazyFast took 37.4 and 13.7 seconds, respectively. This unexpected speed-up caused by the cache efficiency of LazyFast. Specifically, every call to UPDATEROW computes off-diagonals from V Visagt1 V Vidja by accessing entries only in
V[[m], S). it was still faster than Fast. For
8

---

8000
KT0
1.0
LaeryPoe
Computed of of-diagoma
0.5
Tomiine
0.0
200
120
Lazy Foct
Layy
Fint
Looo/ar
60000
2000
(a)
6000, B- B-input, Runtime
(b) 6000, L-input, Runtime
(c) 6000, Off Off-diagonals
XXUUP
Neiove Lasy Faet
10
Lasy
Luee
Rud
0.05
Computed affdingomai
Laig
Panntnne
2000
100
10000
1000
5000
(d) k = 200, B- inputt Runtime
(e) k = 200, L-input, Runtime
(0 1: 200, Off off-diagonals
four runtime figures, enlarged views of lower left parts are shown for visibility. In Figs. 2c and 2f, the gray band indicates the range of the possible number of computed off-diagonals: [k<I 1)/2, (k- 1)(n k/2)]-
Figure 2: Results on synthetic datasets.
V((i, Ju.+1......................... J) S((S1-1)). This process virtually creates blocks in Cholesky factor, enabling the eefhe-efficient computation of off-diago via blocking (see, e.g., [26, Section 2.3]). In fact, the cache miss rates of Fast and LazyFast for the above example were 71.3% and 3.3%, respectively.
Another interesting observation in the synthetic (ii) and real-world settings is that while Fast was often faster than Lazy in the L-input setting, the opposite occurred in the B-input setting. This is because computing an off-diagonal in the B-input setting costly relative the L-input setting. As result, avoiding the redundant computation of off off-diagonals by the lazy update tends to be more effective than computing marginal gains efficiently via the Cholesky factorization.
5.2 Double greedy algorithm for unconstrained DPP MAP inference
We compare naive DOUBLEGREEDY and our FASTDOUBLEGREEDY by applying them uncon- strained DPP MAP inference on three datasets: synthetic (n 6000), Netflix Prize, and MovieLens. Since kernel matrices L in the real-world datasets are singular, we use kernel matrices computed as L = 0.93 B + 0.17 in this section, ensuring that the resulting matrices are positive definite. In this section, we set the timeout period to one day (86400 seconds).
Table presents the results. Note that both algorithms require L to be computed in advance. Therefore, measured the time of computing B B (Product) separately from the time of constructing solutions (Greedy). Our FAST DOSBIOOUL.ER ..BEEED additionally requires 7,-1 to be computed in advance for accelerating the solution construction; therefore, also measured the time of computing T--1 (Inverse) separately. As in Table 1, naive DOUBLEGREEDY took so long for solution construction that failed to return solutions real-world instances one day. By contrast, our FASTDOUBLEGREEDY constructed solutions far faster and succeeded in returning solutions to all the instances.
Also, the computation of B B (Product) took considerably long time relative to the rumning time of LAZY item vectors is given and our goal is obtain greedy solution for small & o(n), should avoid computing the kernel matrix L B" B in advance.
the previous section. Therefore, as mentioned above, when a matrix of

---

8000
Laey
LaerPhe
Computed of ee-diagomas
Lang Haur
Tomsinn
120
Natre Lezy
Leze
1000
3.00
5000
15000
20000
1500
(a) Netflxx B-input, Runtime
(b) Netflix, Linput, Runtime
(c) Netflix, Off Off-diagonals
Compared off disggoaaas
LaeeyPoe
Runtion
Tuntion
1200
Naleo Lezs
1200
Nelve Lasy
Lezyfiet
3000
6000
5003
10000
15000
50000
10000
15000
(d) MovieLens, B-input, Runtime
(e) MovieLens, L-input Runtime
(1) MovieLens, Off-diagonals
Figure 3: Results on real-world datasets. In Figs. 3c and 3f, the gray band indicates the range of the possible number of computed off-diagonals: [k(k 1)/2, (k 1)(n k/2]]-
Table Running time [s] of DOUBLEGREEDY and FASTDOUBLEGREEDD
DOUBLEGREEDY
FASTDOURLEGREEDY
Dataset
Product
Greedy
Total
Product
Inverse
Greedy
Total
Synthetic
2000
1.1
258.6
259.7
1.1
1.8
0.7
3.6
n = 4000
8.7
5422.4
5431.1
8.7
16.9
10.0
35.6
6000
30.0
36233.1
36263.1
30.0
59.8
34.6
124.4
n 8000
70.2
86400.0
70.2
151.2
103.1
324.5
10000
137.9
86400.0
137.9
294.2
182.6
614.7
Netflix Prize Moviel.ens
20561.6
86400.0
20561.6
1706.7
916.2
23184.5
37829.5
86400.0
37829.5
21999.2
6337.3
66166.0
Acknowledgements
The authors thank anonymous reviewers for their valuable comments. This work was supported by JST ERATO Grant Number JPMJER190) and JSPS KAKENHI Grant Number 1722K
References
[1] N. Anari and M. Dereziński. Isotropy and log-concave polynomials: Accelerated sampling and high-precision counting of matroid bases. In Proceedings of the 2020 IEEE 61st Annual Symposium Foundations Computer Science (FOCS 2020), pages 1331-1344. IEEE, 2020.
[2] N. Anari, Oveis Gharan, and Rezaei. Monte Carlo Markov chain algorithms for sampling strongly Rayleigh distributions and determinantal point processes. In Proceedings of the 29th Annual Conference on Learning Theory (COLT 2016), volume 49, pages (13-115. PMLR,
2016.
10

---

[3] E. Balkanski, A. Breuer, and Y. Singer. Non-monotone submodular maximization in exponen- tially fewer iterations. In Advances Neural Information Processing Systems (NeurIPS 2018), volume 31. Curran Associates, Inc., 2018.
[4] E. Balkanski, A. Rubinstein, and Y. Singer. An exponential speedup in parallel running time for submodular maximization without loss in approximation. In Proceedings of the 2019 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), pages 283-302. SIAM, 2019.
[5] J. Bennett and S. Lanning. The Netflix prize. In Proceedings of KDD Cup and Workshop, 2007. URL https: / /www. kaggle. com dttp/atsaaeee/aaaeeeaaeeaaa wetaattsttt/etfii--ieeeeeee http:/etffiiiiieeeeeeeeeeeeeeett wwwerffixxiicnneeeliiii prize- data.
[6] A. Bhaskara, A. Karbasi, S. Lattanzi, and M. Zadimoghaddam. Online MAP inference of determinantal point processes. In Advances in Neural Information Processing Systems (NeurIPS 2020), volume 33, pages 3419-3429. Curran Associates, Inc., 2020.
[7] D. Bini and V. Y. Pan. Polynomial and Matrix Computations, volume 1. Birkhäuser Boston,
1994.
[8] A. Breuer, E. Balkanski, and Y. Singer. The FAST algorithm for submodular maximization. In Proceedings of the 37th International Conference on Machine Learning (ICML 2020). volume 119, pages 1 1134-1143 143. PMLR, 2020.
[9] R. A. Brualdi and H. Schneider. Determinantal identities: Gauss, Schur, Cauchy, Sylvester, Kronecker, Jacobi, Binet, Laplace, Muir, and Cayley. Linear Algebra and Its Applications, 52-53:769 1983.
[10] N. Buchbinder, M. Feldman, J. S. Naor, and R. Schwartz. Submodular maximization with cardinality constraints. In Proceedings of the 2014 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014), pages 1433-1452. SIAM, 2014.
[11] N. Buchbinder, M. Feldman, J. S. Naor, and R. Schwartz. A tight linear time (1/2)- approximation for unconstrained submodular maximization. SIAM Journal Computing, 44(5):1384-1403 2015.
[12] D. Calandriello, M. Derezinski, and M. Valko. Sampling from k-DPP without looking at all items. In Advances in Neural Information Processing Systems (NeurIPS 2020), volume 33, pages 6889-6899, Curran Associates, Inc., 2020.
[13] L. Chen, G. Zhang, and E. Zhou. Fast greedy MAP inference for determinantal point process to improve recommendation diversity. In Advances in Neural Information Processing Systems (NeurIPS 2018), volume 31. Curran Associates, Inc., 2018
[14] Y. Chen, T. Dey, and A. Kuhnle. Best of both worlds: Practical and theoretically optimal submodular maximization in parallel. In Advances in Neural Information Processing Systems (NeurIPS 202/), volume 34, pages 25528-25539. Curran Associates, Inc., 2021.
[15] A. Çivril and M. Magdon-Ismail. On selecting maximum volume sub-matrix of a matrix and related problems. Theoretical Computer Science, 410(47):480144811 2009.
[16] M. Derezinski, D. Calandriello, and M. Valko. Exact sampling of determinantal point processes with sublinear time preprocessing. In Advances in Neural Information Processing Systems (NeurIPS 2019), volume 32. Curran Associates, Inc., 2019.
[17] A. Ene and H. Nguyen. Parallel algorithm for non- non-monoeone DR-submodular maximization. In Proceedings of the 37th International Conference on Machine Learning (ICML 2020), volume 119, pages 2902-291 2911. PMLR, 2020.
[18] M. Fahrbach, V. Mirrokni, and M. Zadimoghaddam. Non-monotone submodular maximization with nearly optimal adaptivity and query complexity. In Proceedings of the 36th International Conference Machine Learning (ICMI. 2019), volume 97, pages 1833-1842. PMLR, 2019.
[19] K. Fan. An inequality for subadditive functions on distributive lattice, with application to determinantal inequalities. Linear Algebra and Its Applications, 1(1):33-38, 1968.
[20] M. Gartrell, I. Han, E. Dohmatob, J. Gillenwater, and V.-E. Brunel. Scalable learning and MAP inference for nonsymmetric determinantal point processes. In Proceedings of the 9th International Conference on Learning Representations (ICLR 2021), 2021.
[21] J. Gillenwater, A. Kulesza, and B. Taskar. Near-optimal MAP inference for determinantal point processes. In Advances in Neural Information Processing Systems (NeurIPS 2012), volume 25. Curran Associates, Inc.. 2012.
11

---

[22] J. Gillenwater, A. Kulesza, Z. Mariet, and S. Vassilvtiskii. A tree- bree method for fast repeated sampling of determinantal point processes. In Proceedings of the 36th International Conference on Machine Learning (ICMI. 2019), volume 97, pages 2260-22666 PMLR, 2019.
[23] I. Han and J. Gillenwater. MAP inference for customized determinantal point processes via maximum inner product search. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics (AISTATS 2020), volume 108, pages 2797-2807. PMLR, 2020.
[24] I. Han, P. Kambadur, K. Park, and J. Shin. Faster greedy MAP inference for determinantal point processes. In Proceedings of the 34th International Conference on Machine Learning (ICMI 2017), volume 70, pages 1384-1393. PMLR, 2017.
[25] F. M. Harper and J. A. Konstan. The Moviel datasets: History and context. ACM Trans- actions on Interactive Intelligent Systems, 5(4):1-19, 2015. URL btttps://grouplentt org/ moreeessmmovielee ens /25m/.
[26] I.. Hennessy and D. A. Patterson. Computer Architettree A Quantitative Approach. Elsevier, 6th edition, 2011.
[27] C.-W. Ko, J. Lee, and M. Queyranne. An exact algorithm for maximum entropy sampling. Operations Research, 43(4))684-691, 1995.
[28] A. Kuhnle. Interlaced greedy algorithm for maximization of submodular functions in nearly linear time. In Advances in Neural Information Processing Systems (NeurIPS 2019), volume 32. Curran Associates, Inc.. 2019.
[29] A. Kuhnle. Nearly linear-time, time, parallelizable algorithms for non- non-monotone submodular maxi- mization. In Proceedings of the 35th AAAI conference on artificial intelligence (AAAI 2021). volume 35, pages 8200-8208. AAAI Press, 2021.
[30] A. Kulesza and B. Taskar. k-DPPs: Fixed-size determinantal point processes. In Proceedings of the 28th International Conference on Machine Learning (ICML 2011), pages 1193-1200. Omnipress, 2011.
[31] A. Kulesza and B. Taskar. Determinantal point processes for machine learning. Foundations and Trends@ in Machine Learning, 5(2-3)):1332886 2012.
[32] C. Launay, B. Galerne, and A. Desolneux. Exact sampling of determinantal point processes without eigendecompooittinn. Journal of Applied Probability, 57(4):1198-122 2020.
[33] C. Li, S. Sra, and S. Jegelka. Fast mixing Markov chains for strongly Rayleigh measures, DPPs, and constrained sampling. In Advances in Neural Information Processing Systems (NeurIPS 2016), volume 29. Curran Associates, Inc., 2016.
[34] O. Macchi. The coincidence approach to stochastic point processes. Advances in Applied Probability, 7(1):83-122, 1975.
[35] S. Mahabadi, P. Indyk, S. O. Gharan, and A. Rezaci. Composable core-sets for determinant maximization: A simple near-optimal algorithm. In Proceedings of the 36th International Conference on Machine Learning (ICMI. 2019), volume 97, pages 4254 4263. PMLR, 2019.
[36] S. Mahabadi, I. Razenshteyn, D. P. Woodruff, and S. Zhou. Non-adaptive adaptive sampling on
turnstile streams. In Proceedings of the 52nd Annual ACM SIGACT Symposium Theory of Computing (STOC 2020), pages 1251-1264. ACM, 2020.
[37] M. Minoux. Accelerated greedy algorithms for maximizing submodular set functions. In Optimization Techniques, pages 234-243. Springer Berlin Heidelherg, 1978.
[38] B. Mirzasoleiman, A. Badanidiyuru, A. Karbasi, J. Vondrak, and A. Krause. Lazier than lazy greedy. In Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI 2015), volume 29, pages 1812-1818. AAAI Press, 2015.
[39] T. Nakamura, S. Sakaue, K. Fujii, Harabuchi, S. Maeda, and S. Twata. Selecting molecules with diverse structures and properties by maximizing submodular functions of descriptors learned with graph neural networks. Scientific Reports, 12(1): 124, 2022.
[40] G. L.. Nemhauser and I. A. Wolsey. Best algorithms for approximating the maximum of submodular set function. Mathematics of Operations Research, 3(3):177-188, 1978.
[41] G. Nemhauser, A. Wolsey, and M. L.. Fisher. An analysis of approximations for maximizing submodular set functions-1 -I. Mathematical Programming, 14(1):265-294 1978.
12

---

[42] N. Ohsaka. Some inapproximability results of MAP inference and exponentiated determinantal point processes. Journal of Artificial Intelligence Research, 73:709-733 -35, 2022.
[43] S. Sakaue. Guarantees of stochastic greedy algorithms for non-monotone submodular maxi- mization with cardinality constraints. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statisties (AISTATS 2020), volume 108, pages 11-21. PMLR, 2020.
[44] D. Sharma, A. Kapoor, and A. Deshpande. On greedy maximization of entropy. Proceedings of the 32nd International Conference on Machine Learning (ICML 2015), volume 37, pages 1330. PMLR, 2015.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] See Abstract and Section
(b) Did you describe the limitations of your work? [Yes] The remarkable limitation is that our LAZYFAST GREEDY does not improve the worst-case time complexity, and it is clear from the description Section 3.1.
(c) Did you discuss any potential negative societal impacts of your work? [No] This is purely algorithmic study, and negative societal impacts are expected.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section 2. Additional assumptions required in the unconstrained setting is described in Section
(b) Did you include complete proofs of all theoretical results? [Yes] All theoretical statements are followed by their proofs.
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material or as a URL)? [Yes] See the supplementary material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A] No training is performed in our experiments.
(c) Did you report error bars (e.g.. with respect the random seed after running experi-
ments multiple times)? [No] Although some algorithms are randomized, obvious that the randomness does not largely affect our experimental results.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Section 5.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] See [5, 25).
(b) Did you mention the license of the assets? [No] We used publicly available standard datasets.
(c) Did you include any new assets either the supplemental material or as URL? [Yes] The codes of the algorithms are provided in the supplementary material.
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [No] Since the datasets are publicly available standard ones, no such discussion seems be necessary.
(c) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [No] Since the datasets are publicly available standard ones, no such discussion seems to be necessary.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
13

---

(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "vyeB0tls9Ww", "reviewer": "Reviewer_RhmJ", "summary": "This paper presents new greedy algorithms for maximum a posteriori (MAP) inference for determinantal point processes (DPPs).  MAP inference seeks to find the subset with the highest probability under the DPP.  The first major algorithm presented by the authors combines the ideas of “lazy” and “fast” greedy MAP inference algorithms from prior work.  This LazyFastGreedy algorithm has nearly the same time complexity as the fastest known FastGreedy algorithm from prior work, but runs faster in practice; it is applied to cardinality-constrained DPP MAP inference and extended to several other variants of greedy algorithms.  The second major algorithm presented by the authors is a fast version of the DoubleGreedy algorithm for unconstrained DPP MAP inference.  Finally, the authors present experimental results on synthetic and real datasets, demonstrating that their proposed algorithms can be significantly faster than the fastest known approaches from prior work.", "questions": "* On line 220, d >= n seems to be incorrect.  I suppose this should instead be d <= n.\n* As indicated above, Figure 1(b) should be revised to be more clear.\n* As indicated above, can you describe how the item vectors of the B matrix for the real-world datasets are computed?\n* Nonsymmetric DPPs (NDPPs) have recently gained some attention.  Are the MAP inference algorithms presented in this paper appropriate for NDPPs?\n", "limitations": "A brief mention of the limitation of the LastFastGreedy algorithm not improving upon the worst-case time complexity of the greedy algorithm is included in the paper.  However, the authors should provide a somewhat more detailed discussion of any other known limitations, as well as the potential for negative societal impact, which is completely absent.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* The new greedy DPP MAP inference algorithms presented by the authors appear sound, and are reasonably well explained. \n* The derived runtimes appear correct, although I have not carefully validated the proofs.  \n* The experimental results do indeed demonstrate that the proposed algorithms can be significantly faster than the fastest known approaches from prior work, despite nearly equivalent time complexity (in the case of LazyFastGreedy).  Therefore, the contributions in this paper are significant.\n* The discussion of related work is reasonably clear and thorough.\n\nWeaknesses:\n* For experiments on the real-world datasets (Netflix Prize and MovieLens), the authors don’t explain how the item vectors of the DPP B matrix are computed from each dataset.  This is an important missing detail that should be provided, since each of these datasets consists of users’ ratings of items (movies), and it is not obvious how each item vector was built from these ratings.\n* Figure 1(b) is somewhat unclear.  This figure should be reworked to be more clear and interpretable.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "sUtG3fiuyDM", "reviewer": "Reviewer_LKp4", "summary": "This paper considers the problem of efficiently computing an approximation to the maximum a posteriori inference (MAP) of a discrete determinantal point process (DPP). Specifically, $L$-ensemble DPPs are considered, i.e., DPPs for which the likelihood of a point pattern has a simple formula using a likelihood matrix kernel $L\\succeq 0$.\n\nThis work combines two existing approaches: the lazy greedy algorithm for submodular function maximization and the fast greedy algorithm for DPP MAP inference. The latter relies on  Cholesky factorization updates of the likelihood kernel.\n\nTwo cases are discussed: cardinality-constrained and unconstrained DPP MAP inference.\n\nNumerical simulations illustrate the interest of this approach.", "questions": "Here are some comments and suggestions.\n\n- At line 87, I think it is worth mentioning that $L$ is the likelihood kernel of an $L$-ensemble DPP. Basically, the authors do not work with any DPP but they rather deal with a subclass of DPPs for which the correlation kernel has the form $L(L+\\mathbb{I})^{-1}$ and which are called $L$-ensemble DPPs. I suggest that the authors briefly mention this fact somewhere by possibly pointing to an extra paragraph in Supplementary Material.\n\n    \n- At line 105, it is mentioned that the log-determinant function $f$ is monotone if the smallest eigenvalue of $L$ is at least $1$.\nCould you give a pointer to a reference? For instance, Sharma, Deshpande, Kapoor ICML 2015. \n\n- At line 123, there is a typo: the authors write *hence it adds $j_t = i$ to $\\overline{S^{(t-1)}}$*.\n It should be *it adds $j_t = i$ to $S^{(t-1)}$*.\n\n- At line 240, there is a missing $\\det$. The correct expression should be $g(S) = \\log \\det L^{-1}[S]$.\n\nMinor comments:\n\n- Line 15: the use of the singular is strange. I suggest 'DPPs have been...'\n\n- Line 70: *to have the submodularity* &larr; to be submodular?\n\n- line 187: The notation $U$ (uppercase) is a bit misleading since $U$ is a real number and not a matrix (or a set). It is maybe better to use a lowercase letter.", "limitations": "The authors discuss the limitation of their results and summarize them in the checklist. I do not expect negative societal impacts from this algorithmic study.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "originality: To my knowledge, this idea has not yet been discussed elsewhere.\n\nquality: This paper is carefully written and understandable. It contains very few typos. Although it is not a big issue, there is no conclusion section.\n\nclarity: I found the text and the maths clearly written. A few suggestions of improvements are given below.\n\nsignificance: The results of this paper are probably useful in practice. On the other hand, this work combines two existing techniques and this combination may be appear as a weak contribution. However, since this combination is not straightforward,  this paper is interesting for the ML/DPP community.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Y2TyCGtH0gg", "reviewer": "Reviewer_f4YC", "summary": "This paper studies a fast algorithm for greedy MAP inference of Determinantal Point Processes (DPPs). The authors first apply a lazy evaluation trick (widely used in submodular maximization) to the Cholesky-factorization-based greedy DPP MAP algorithm (FastGreedy). They analyze the runtime of the proposed algorithm for the best and worst cases. Although the worst-case runtime is no better than FastGreedy, it practically works well. They also apply the lazy evaluation trick to the double greedy algorithm, which guarantees a constant approximation ratio of unconstrained greedy maximization. Experimental results on both synthetic and real-world datasets verify the effectiveness of the proposed acceleration with a promising speedup.\n", "questions": "Some explanations of [22] are missing. The algorithm studied in [22] can be essentially used for the size-constrained greedy DPP MAP. Although it is required a one-time preprocessing, its runtime is logarithmic in n (the size of the ground item), which is much beneficial for large n. And they reported up to x224 speedup than the FastGreedy algorithm. Hence, by simple comparison to FastGreedy (LazyFastGreedy shows x17 speedup), it is expected that the algorithm is still faster than LazyFastGreedy. Does the author have a chance to compare with it?", "limitations": "Mentioned in weakness", "rating": 4, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- This paper is written well and easy to follow up on the methodology. \n- This paper fills the gap of the FastGreedy algorithm by adopting the lazy evaluation trick, and report the empirical speedup beyond the other algorithms for greedy submodular maximization.\n\nWeaknesses\n- The novelty of this paper is fairly weak. The main contribution is a simple adaptation of the lazy evaluation to the greedy DPP MAP inference algorithms. Both the lazy evaluation trick and the fast greedy DPP MAP implementation (as well as the double greedy algorithm) have been studied prior. These contributions are under the bar of acceptance.\n- Although the proposed algorithm empirically works faster than other competitors, it is suspicious when it can be effective. Currently, the runtime complexity is lightly analyzed including only the best and worst scenarios. And the worst-case runtime is even worse than the previous FastGreedy algorithm (in the general case). This makes contributions of this work weak and it needs more careful analysis of the runtime, e.g., conditions that the LazyFastGreedy algorithm achieves for the best (or at least better) runtime.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Tby7BCcUUvb", "reviewer": "Reviewer_tSLD", "summary": "This paper proposes the acceleration implementations of the greedy-type algorithms for DPP MAP inference. Two algorithms are developed for the cardinality-constrained and unconstrained DPP MAP inference respectively.  The computational efficiency and accuracy are validated through experiments on simulated and real-world datasets. ", "questions": "1.\tThe authors propose two algorithms for the two different tests. What is the motivation to propose these two types? \n2.\tThe introduction section of the relevant background is unclear and needs more details and formalization. \n3.\tIn section 5.1, figure 2, we observe the runtime is not strictly increased when $n$ increases. Why do the authors get decreasing runtime values? \n4.\tIn section 5.2, please provide more synthetic data settings when $n$ and $k$ vary. \n5.\tI suggest the authors demonstrate the experiment results in more detail and show the power of the purposed methods. \n6.\tThe authors review many existing methods in the introduction but only compare three methods in the simulation section. Why do you choose these three methods to make a comparison?\n", "limitations": "The authors mention the limitation that the method does not improve the worst-case time complexity. The proposed method can only fasten empirical runtimes.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality: This paper incorporates the ideas of “lazy” and “fast” which are thought to be incompatible in the previous literature. \nQuality: The experiment results show that the algorithms are powerful.  The paper is generally well written in both aspects of grammar and technical discussion. \nClarity: A lot of details of the experiment seem to be missing.\nSignificance: The proposed acceleration method does have effectiveness through validations on simulated and real datasets. \n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept