Minorization-Maximization for Learning Determinantal Point Processes
Authors: Takahiro Kawashima
Hideitsu Hino
Venue: Accepted by TMLR ()

Abstract: A determinantal point process (DPP) is a powerful probabilistic model that generates diverse random subsets from a ground set. Since a DPP is characterized by a positive definite kernel, a DPP on a finite ground set can be parameterized by a kernel matrix. Recently, DPPs have gained attention in the machine learning community and have been applied to various practical problems; however, there is still room for further research on the learning of DPPs. In this paper, we propose a simple learning rule for full-rank DPPs based on a minorization-maximization (MM) algorithm, which monotonically increases the likelihood in each iteration. We show that our minorizer of the MM algorithm provides a tighter lower-bound compared to an existing method locally. We also generalize the algorithm for further acceleration. In our experiments on both synthetic and real-world datasets, our method outperforms existing methods in most settings. Our code is available at https://github.com/ISMHinoLab/DPPMMEstimation.

Published in Transactions on Machine Learning Research (11/2023)
Minorizaion-MMxxiiiaatoon for Learning Point Processes
Determinantal
Takahiro Kawashima
tkawa @ism.ac.jp
Deportment of Statistical Science The Groduate Universily for Advanced Studies, SOKENDAI
Hidcitsu Hino
hino @ism.ac..p
The Institute of Statistical Mathematics RIKEN Center for Aduanced Intelligence Project
Reviewed on OpenReview: https: openrevee.....eee.e net/ forum? id= 66A2NN173
Abstract
determinantal point process (DPP) is a powerful probabilistic model that generates diverse random subsets from a ground set. Since DPP characterized by positive definite kernel, DPP on finite ground set can be parameterized by kernel matrix. Recently, DPPs have gained attention in the machine learning community and have been applied to various practical problems; however, there is still room for further rescarch on the learning of DPPs. In this paper, we propose a simple learning rule for full-rank DPPs based on minorization cinnoriztion-maxiizzztooo (MM) algorithm, which monotonically increases the likelihood in cach itcration. We show that our minorizer of the MM algorithm provides a tighter nower-bound compared to an existing method locally. We also generalize the algorithm for further acceleration. In our experiments on both synthetic and real-world datasets, our method outperforms existing methods in most settings. Our code is available httpss: cwm/ Bettlai....//MMMiaaaaaPPPPPPaaaa
1 Introduction
A determinantal point process (DPP) is a probabilistic model that represents the occurrence probability of random subsets of ground set. Initially, DPPs were originated in statistical mechanics describe the probabilistic behavior of fermions (Macchi 1975). In recent. years, broader applications of DPPs have been developed in the machine learning community (Kulesza & Taskar 2012).
An important feature of DPPs is the presence of negative dependence (Boreaa et al. 2009). There exists some characterizations of negative dependence (Mariet 2019), and here we consider (pairwise) negative correlation as an example. Letting A be a random subset, P P( C A) < P(i E A)P(j E A) holds for any pair of items j.j in a ground set when P(.) is defined as a DPP. This means that DPPs can take into account inter-element repulsion, which encourages the occurrence of diverse subsets. This feature aligns with variety of machine learning applications, such as diversity-promoting image scarch (Kulesza Taskar (011), recommender systems (Gillenwater al. 2014), base station configuration for cellular networks (Miyoshi & Shirai 2014)., random design regression Dereziński et al. 2022). and locating inducing points of sparse variational Gaussian process regression [Burt et al. 2020).
A natural problem on DPPs is efficient learning of the parameters. Since a DPP defined on a finite ground set is parameterized by a positive semidefinite kernel matrix, the learning methods are roughly classified into thrce approaches: (a) assuming the kernel matrix full-rank and having no additional structure (full- rank DPPs), (b) assuming the kernel matrix is low-rank (low-rank DPPs), or (c) assuming other tractable structure for the kernel matrix.

---

Published in Transactions on Machine Learning Research (11/2023)
So far, some learning methods have been designed for full-rank DPPs. Gillenwater et al. (2014) pioneered the learning problem of DPPs; they developed an EM algorithm for full-rank DPPs. Mariet & Sra (2015)
later proposed a fixed-point algorithm for full-rank DPPs. They derived a simple update rule for the kernel
matrix and showed its monotonicity by finding its equivalence with a minorization maximization (MM)
algorithm. Their experiments also showed that the fixed-point algorithm is more efficient and stable than
the EM algorithm.
Gartrell al. (2017) introduced low-rank DPPs. Learning of low-rank DPPs involves gradient-based opti- mization. Mariet et al. (019) proposed contrastive estimation as alternative of the maximum likelihood estimation (MLE), while Osogami et al. (2018) incorporated temporal dynamics into low-rank DPPs. A Bayesian extension of low-rank DPPs was also proposed in (Gartrell et al. 2016).
In principle, without special structures, it is difficult to overcome the O(N3) time complexity for full-rank DPPs and O(N for low-rank DPPs, where N is the size of the ground set and K is the rank of the kernel matrix. To go beyond these complexities, DPPs with special structure are developed, such as Kronecker DPPs (Mariet & Sra 2016) and the tspegonal+speciall low-rank" structure (Dupuy & Bach 2018
Our study focuses on learning of full-rank DPPs. While full-rank DPPs are sometimes not suitable for problems with a large ground set, we often want to conduct an exact inference for small to medium-sized problems. For example, consider a hypothetical application of a DPP. The first step in the data analysis is to assess whether DPP-based modeling is appropriate for our task or not. Even our final goal is to handle large data, we typically take relatively small data collected provisionally during this assessment phase. In such a situation, we hope to utilize ready-made learning algorithm: requiring less hyperparameter tuning, casily implementable, well-behaved, and good convergence speed. However, the cxisting methods for full-rank DPPs have some dilficulties; the EM algorithm (Gillenwater et al. 2014) internally requires optimization on Stiefel manifold, making the learning procedure complicated and unstable. In (Mariet & Sra 2015). the authors introduced a step size in order to accelerate the fixed-point. algorithm, but the step size was fixed throughout the learning.
In this paper, we propose a simple yet powerful learning rule for full-rank DPPs based on the MM algorithm. Our method increases the log-likelihood monotonically and stably, and locally provides tighter minorizer than the fixed-point algorithm. Our minorizer is concave while the fixed-point algorithm maximizes non- concave minorizer in the iteration. This means it has no concern about optimization failure in each iteration. Moreover, we also develop an accelerated version of the proposed MM algorithm. Although the accelerated algorithm requires fixed hyperparameters, the step size is determined adaptively in each iteration. We conduct experiments with both synthetic and real-world datasets and our method outperforss the existing methods in most settings.
In summary, our main contributions in this paper are:
We present an easy-to-ime toyyleemmmeeennt learning method for full-rank DPPs based on the MM algorithm. By the property of MM algorithms, our method monotonically increases the likeliool
We compare the tightness of the minorizers between the existing and proposed methods. The fixed-point algorithm for DPPs proposed in (Mariet & Sral 2015) can also be viewed as an MM algorithm. Our result indicate that our minorizer locally provides a tighter lower-bound than the existing method. Moreover, our method provides a concave minorizer unlike the exsiting method.
We derive generalized form of the minorizer and develop accelerated algorithm. We also provides an adaptive method to determine the step size values in the iterations for the accelerated algorithm.
We conduct experiments evaluate learning algorithms for full-rank DPPs using both synthetic and real-world datasets. Our empirical results show superiority of our method in convergence speed and stability.
2

---

Published in Transactions on Machine Learning Research (11/2023)
2
Determinantal Point Processes
Let :) be a kernel function on ground set Q. A determinantal point process (DPP) with the kernel function k(.,-) is a point process on f whose joint intensities are formed as
Po (a 22, ................................ k.) det K (n));
where 21, ................................ In Ω and [n] (k(z,, 2 ji (Hough et al. 2009). The following theorem gives sufficient condition for the existence and uniqueness of DPP:
Theorem 2.1 (Soshnikov (2000); Shirai & Takahashi (2000)) ). Let K. be self-adjoint integral operator
determined by kernel function k and be of locally frace class. Then, the kernel function k(;,-) determines a DPP if and only if all the eigenvalues of K are in [0, 1].
If the restriction of an operator K. to an arbitrary compact subset of Ω is of trace class, K. is said to be locally trace class. Roughly speaking, Theorem 2.1 states that a positive definite kernel k(.,)) defines a DPP under appropriate scaling which ensures the resulting probabilities in [0, 1].
In the context of machine learning, DPPs on a finite ground set y = 21. N) are typically considered. On the finite ground set V, a point process P(-) DPP with kernel matrix K S if
P(S S A) det (K]s)
for a random subset. A C y drawn by and an arbitrary 8 y. [K]s (Ky)ajes E s/Si denotes the principal submatrix of K and the kernel matrix must be 0 K 3 I from an analogy with the DPPs on general ground set A DPP a finite ground set has an alternative representation called the L-ensemble [Borodin & Rains 2005 which defines the occurrence probability of random subset A C y as
det((L]A) (L(A) det( L + +I)
where L E S is positive semidefinite kernel matrix. We can commute between K and L using the K invertible. In this paper, we develop
equation K = L(L+ 1)-1 or its inversion = K(I - K)-1 1 if a learning algorithm for L.
3 Learning Algorithm
Given M samples A2,,2,.... S y, our goal is to solve MLE. That is, to find a maximizer of the log-likelihood
1 M
S(L) =
Σ
log dct((L],A...) log det
M
m=
M
Σ
log det (U AU, LU A.m) log det(L LL + I),
(1)
M
where Am in Am.
E Am. 10. is the submatrix of I obtained by keeping the rows corresponding the elements
3.1 MM Algorithm
A minorization- maximization (MM) algorithm is a powerful algorithm for finding local maximizer mnnorization-mmxiimizatooo
of generally non-concave objective f(0) (Hunter & Lange 2004 [unn et al. (017)). The MM algorithm consists of two steps: (i) find minorizer (( of f(0) that satisfies
We K. 3. and & in the sense of positive (semi- )defnite ordering.
3

---

Published in Transactions on Machine Learning Research (11/2023)
f(0) o(010(0)
f(0()) g(0())000))
for all 0 and g( within a feasible region. Then, (ii) maximize the minorizer g(0)0(+) with respect 0 and set g(++1) arg max g(0)0(t)) Repeating this process, obtain sequence of the parameters {0(t) which monotonically increases the objective value, because
[(0(++1) 2 g(0((+)))0()) 2 )(0(0)0(0)= = -((())
(2)
holds.
Since det)))) is concave on S++, the objective function L is combination of concave and convex functions. From the concavity of log det,,,, the following linear upper bound is derived with the first-order Taylor expansion
log del( S log del (Y) + tr(Y - (x- = log (Y) + tr (r(Y -
(3)
for any X, Y S"
N, and by swapping X and Y.
log det
log det Y) - tr (Y - X)} log dY) - (Y) +
(4)
also holds. From with
> and Y L ((+1) I, we have
log dot 1) 2 log det (L (9) + +1 (z (
(5)
which yields choice for minorizing the objective
This method is referred to as the concave-convex procedure (CCCP) (Yuille & Rangarajan 2001], special case of MM algorithms. However, the minorizer derived by the CCCP has no closed-form maximizer in our case, therefore, we devise an easy-to-optimize alternative.
3.2 Proposed Algorithm
In the proposed minorizer of 1 the convex part is lower-bounded linearly by 5 and the concave part log degdet[[L],, = log (U Am AUA..) is also lower-bounddd. The following proposition provides the concrete form of our proposed minorizer.
Am,
Proposition 3.1. Let ((L) be given by and
(L)
Σ
IL 1 ( tr((L + +1 1)- ()I
(6)
M
where
()) 1 M
Σ log de (UA.. AL (U A.n. Amml log (1) +1) - tr((L() + -1)
M m=1
is a constant term. Then, f(L) 2 ()) and f((( = (L hold for any L, (t) E SN
Proof. For any positive definite P. P. > 0 and any square or tall non-generated matrix A, the following
matrix inequality holds (Sun et al. 2016 2017
(APA ) 1 R, AP,P- A PAA R,
Rg = A
and thus we have
(<((APA)--S) 5 St AP:P- A R
(7)
4

---

Published in Transactions on Machine Learning Research (11/2023)
Algorithm 1: Ninotiattoon-Maxiiizzaton (MM)
Input: Training set {A1, A2. Aas) initial value L O, and machine epsilon & 2 0
Output: L
for t t= to do
A O= O;
M
Q. + L
Σ
EU
UUA
UAm
L L+
M
Am
m=1
G - I-+
L + SolveCARE(A. Q., // Solve Equation 12
end
for any appropriately sized and positive semidefinite
> O. Using the lower-bound 4 with the sub-
stitutions X + UA LU Am Y
Un L U Am and 7 with A Un P + L.P. + (t) and
S S-U
U Am I Um. we have
log (U Am. LU Am Am + log (U
A, U A. -- (r((t
LU - U I U
Am
Am log det
Am A..
4 U -
[A u (t) L -
(8)
Combining the lower-bounds 5 and
we can construct the minorizer of F(L) as 6
In order to obtain the maximizer of we iteratively optimize the proposed minorizer g (() by solving the first-order optimality condition for / 1....,"" T. Since [ concave because of the convexity of tr(X-1) for X > 0, stationary point of g ( is also its global maximizer.
Proposition 3.2. A global mazimizer of (L satisfies
(O + - Q/ =0
(9)
where
M
Q = (()
Σ
U [1 Unn I(0)
(10)
M
Am
A.
m=1
Proof. Noting that Vxtr(AX) and A, the optimality condition of (6 is
A and Vxtr(AX -(x - for appropriate matrices X
V Vig - - (L + -1-1==0
(11)
By multiplying both sides of 11 by L, we can see that the stationary points of ((L satisfy 9 From the concavity of ("), we obtain the result.
The matrix quadratic equation
is a special case of the continuous algebraic Riccati equation (CARE):
A XA XGX + +Q=0,
(12)
where X E N is unknown, and G,Q E SN, A E NNN are fixed coefficient. matrices. The CARE is well-studied in control engineering and is solvable by some numerical methods such as the Schur method [aubb 1979) and Newton's method (Bini el al.) 20111; Benner & Byers 1998). It. worth noting that
CARE solvers are available in most programming languages through packages for scientific computation; for example, SciPy in Python and MatrixEquations. jl in Julia.
In addition, confirm the following statement corollary of Proposition 3.2

---

Published in Transactions on Machine Learning Research (11/2023)
Corollary 3.1. With the same notation in Proposition 3.2 and positive definite initial value L (0) 0, we have rank (Ln ( = rank rank(Q()) for
1,......
Proof. Since (0) is positive definite, (I + -)- 1 is non-singular. Therefore, from the optimality condition
rank(L +1) = rank(L = rank (11))
By applying similar operations recursively, the result can be confirmed.
From the assumption in Corollary 3.1 we find that L (0) should be initialized by some positive definite matrix. See the experimental settings described in Section for examples of the initialization. Corollary 3.1 also says that if Q degenerated, the solution of (9 must also be degenerated. This means that when (t) is
singular, the solution of (9) falls outside the feasible region S This problem arises when some elements
of y are never observed in the given data A2. Ar, that is, U & y holds. To avoid this issue and stabilize numerical computation, we recommend solve
L +1) 10 +
with a machine epsilon e > instead of 9 We note that the choice of the machine epsilon e does not affect the estimate significantly; we use 10-10 throughout this paper. The procedure for the proposed MM-based learning is summarized in Algorithm
3.3
Relation the Existing Method
Mariet Sra (2015) derived the following update rule to maximize
as fixed-point algorithm:
[(++)) = (t) aL ())
(13)
1
Vf(L) M
EU A. U -L+1)-
where a > 0 is a step size. For a = 1, they also show that the update rule 13 can also regarded as an MM algorithm with the non-concave minorizer
M Σ T m=1
h(L] = M
(1 U ( L-
log det (L( -1)- {(L
(14)
where ()) ) is a constant term and explicitly given in Appendix A Comparing with 6 we can see that the lower-bounds for the first term in ① are the same, and those for the second term only differ. With respect to these minorizers, the following proposition holds.
Proposition 3.3. For (!) defined in 6 and (t) defined in
14 it holds that
(( 2 (() for L in the 8-ncighborhood of ((); (L(
{L()) + 6M
M is a symmetric matrix whose eigenvalues are all in [-1, with sufficiently small 5 > 0.
Proof. We have the following inequality:
(() - ()) 2 (L I) 1) - (1-
(15)
where the derivation is shown in Appendix
If L (L((L() (1)), we have
20 L 1-1 2.
(16)
The details of the derivation can be found in the appendix. Applying the approximation conclude the proposition.
16 to
we

---

Published in Transactions on Machine Learning Research (11/2023)
16.30
TEL. (objective) h/t (Lt) Woxed-poiig g(L(UZ) (MM)
htL (fxxed pointtpont gtL. (MM)
FILI lobjective)
-0.008
objective value
objective value
-16.35
-16.40
16.45
-0.014
0.010
0.000
0.005
0.010
0.75
5
(a) Neighborhood of L(),
(b) Non-neighborhood of L(0)
Figure 1: Behavior of minorizers.
The proposition 3.3 states that the proposed minorizer gives tighter lower-bound of the objective than that of the existing method locally. This leads to tighter leftmost inequality in (2) making it likely that the proposed method will produce better (++1), Figure [ shows the behavior of the minorizers in the neighborhood and non-neighborhood of (O) The proposed minorizer becomes looser as L moves farther away from (d), but the experimental results in Section 5 show that the proposed method converges faster in most cases. Note that the minorizer of the fixed-point algorithm is non-convex as seen in Figure I(b) This implies that the fixed-point algorithm is possible to get trapped in poor stationary points of h L ()).
3.4 Computational Costs
In our method, the total computational cost per iteration is O + Nº), where k = max Aml. It
is computed as follows; the compulation of Q in ( requires 0 1/Em=1/4 |mm] 1s + N3) O(M + N3)
operations, including the evaluation of ["] for all m 1.2...., M and the matrix multiplications of (t) -) and solving the CARE also cost O(N*).
N N matrices. The inversion (L
The computational complexity of our method is equal to that of the fixed-point algorithm (Mariet & Sra 2015 Although our method incurs additional O(N3) computations due to the CARE, the experimental results in Section show faster convergence of our method in computational time. We note that the gradient- based learning of low-rank factorized DPP also takes the same OMM**+NM per iteration the factorization is full-rank GGartrlll et al. 2017 Osogami al. 2018).
4
Generalization and Acceleration
In this section, we develop generalization of the minorizer the algorithm.
and the CARE 9 for further acceleration of
4.1 Generalizing the Minorizer
By adding penalty term to the mean log-likelihood 1 we can generalize the objective
f00 [L (L) = - ((L)
(17)
where ((0) 2 0 is a non-nogative coefficient and d(-Il-) (|+)) is an appropriate divergence defined on SN XS The additional penalty term ( (D) effects to prevent big change from ( to ((+1), By the definition
7

---

Published in Transactions on Machine Learning Research (11/2023)
Algorithm 2: Accelerated MM
Input: Training set {A1 A2.... Ass), ), initial value O, machine epsilon 2 0, tolerance (0, 1), and accelcration steps Tace E {0, (....T
Output: L
for == to T do
H 1
U Am L Um
M
if & I Tace then
μ f min {max { 1/>xax (HLL+ I)). -1} 6,0%;
end clse
+ O; end
A <- O;
Qu.e + (1 11+DLLH++8 +el;
GN + μH (L+ +1
L SolveCARE/ A, Queer Gμ); // Solve Equation
12
end
of a divergence, (") 2 for any L, (() E st+ and the equality holds and only if (t) This means that the generalized objective Sates (o) also works the minorizer of S(L). Specifically, such a scheme is called as the proximal point algorithm if the divergence d(-Il-) is the squared Fuclidean distance Parikkh & Boyd 2014). Or it is also called mirror ascent (descent) or Bregman minorization (majorization)
if d a Bregman divergence (Nemirovsky. 1983 Beck & Teboulle 2003 Lange et al. 2021
In our case, we consider logdet divergence:
(ia(X = log (X) + log del((Y)))))) ur(Y-111 -Y},
and define d(-ll-) as
1 M ((LI)(()) = M m=1
Σ
( A..
(18)
The defined d(-ll-) in 118 satisfies the definition of a divergence if and only if Um Am y holds. The divergence 18] leads the following minorizer of J(L) and sain (L)
Proposition 4.1. Let f(L) be defined in 1 and Sacn (L)()) be defined in 17 with 11()) 2 0 and the
divergence Then, the concave function
9um (L) = 1 (1)
M
Σ
tr tr
(0)
(1 U L 1-)
M
Am Am
m=1
(0
(11 ur( + -11'' L) Sut0 (I))),
M
where Goo (1) is constant lerm, is the minorizer of J(L) and fass ()).
See Appendix for the proof.
We maximize Spte (.) by solving CARE in the same manner Proposition 3.2 Proposition 4.2. global mazimizer of 9,00 (1) satisfies the CARE
L { H (1 + +1) L + (1 (1 H (t) (1) O,
(19)
8

---

Published in Transactions on Machine Learning Research (11/2023)
where
H (1)
1 M
Σ
U
Am 1 UAm Am
M
m==
degenerates if Um== Am & y holds as well as Q (0) H (t) defined 10 For v = 0, we have gut0 (L ()) and the update rule 19h comes down to the original CARE 9 For p1()) > O, the update rule [19 also works as the MM iteration but the convergence may become slower by the penalty term.
H 10
M
4.2 Acceleration and Hyperparameter Determination
What happens the coefficient p(()) is set to nogative? Then, face (L (()) and 9ac0 (L) can no longer be regarded as the minorizers, but it expected that the update rule produces a bigger change from
(t)
to (1+1) and the learning speed may become faster. However, similar to the learning rate of gradient descent, a too large absolute value for y(9) < 0 may lead bad convergence. What is worse, the solution of
the CARE (19 can even not exist, Our approach to decide the negative 1((1) < is to ensure that there is at least a feasible solution to the CARE 19).
Lemma 4.1. Let G SNN and Q + be fixed coefficients and X S. be unknown. Then, the following equation
XGX Q
(20)
has solution in + if and only if G > O.
Proof. If G is not positive definite, any X does not satisfy 20 By taking the contrapositive, if is the
solution of 20 G must be positive definite. Conversely, if G is positive definite, G O exists and the = x We thus have XG =Q and the equation has the solution
equation (20 becomes
X Q G SN
Proposition 4.3. Suppose H. M > O. Then, the CARE 19 has a solution in S if
( > max -1/Amux H M (L + +))),
(21)
where Amax X) denotes the largest eigenvalue of X.
Proof. The right-hand side of the following CARE
L fu H AO + (I + (1=+
H ( L (())
(22)
is positive definite by the conditions. For 1(0) 2 0, the solution of (22) immediately exists by Lemma When -1 (()) O, we can see that the solution exists if and only if
4.1
(1) H0 (L -
also from Lemma
Then, we have
1 (()) M
+ (L (0) + 1 0
((1) H M (I (0) (0- (1)) -
(0) (0-
(9) H
00
M
M
I (t) (1) (1)- 100++10 - (1)-
00
M
M
(1) 1 - H (1) (0) +1)- 0-1
111 I - H (1)-1 (I +1
(1()) > >mmax ( (- (1-11 + I) -1)
(1()) > -1 --1
11/Amax H (0) +
9

---

Published in Transactions on Machine Learning Research (11/2023)
In the accelerated algorithm, the inequality (2 should be satisfied strictly. Algorithm
2 shows the entire
procedure of our MM-based learning with acceleration on the basis of Proposition 4.3 In Algorithm 2 we introduce two hyperparameters, one is a tolerance 0 > 0 that guarantees the inequality (21) strictly and Tace E 10.1....,77 denotes up to how many iterations the accelcration is applied. We can automatically adjust the slep size coellicient p(()) at each iteration the algorithm with fixed d > 0. while user-defined fixed step size coefficients are used in the existing fixed-point algorithm (Marict & Sra 2015). In the resulting algorithm, we decide the step size by
= min max { -1/ 1//maxx
( (
+ +1) -1] + +0,0]
to ensure 21 and prevent (0 > 0, which may provide monotonic but slower convergence than n1 O. Since only the largest eigenvalue of H H (L") incorporates in the inequality (21 determining pl0 takes less computational time than solving the CARE.
5
Experiments
5.1
Experimental Settings
We evaluate performance of the learning methods for full-rank DPPs through experiments on synthetic and
real-world datasets. For references, we take the fixed-point algorithm (FP) (Mariel & Sra 2015) and Adam
Kingma Ba 2015) as a representative gradient- based method. For Adam, we factorize the kernel matrix by V N and optimize V with the low-rank DPPs (Gartrell et al.
as
L VV
2017 Osogami
al.
2018
We adopt full-batch learning for all the algorithuns.
We provide the following two initialization schemes with reference to Mariet & Sra 2015
WISHART: We sample an initial value from the Wishart distribution as ( W(N,I)/N
BASIC: We uniformly sample Vig p()),
(0) U(00, V2/N) for i,j 1,2,..., ...,, N and initialize as L (0)
The WISHART initialization provides a near-identity matrix, while BASIC provides unstructured matrix for I [))
We adopt the acceleration schemes for each algorithm. We set the step size a 1.3 for the fixed-point algorithme] and the tolerance 8 0.15 for the proposed MM algorithm. For Tace < t, we use the default parameter 1 for the fixed-point algorithm, which monotonically incrcases the objective but no accel- eration is applied, and the same way is used for the proposed MM. In Adam optimization, default values 31 = 0.999, 82 = 0.9 for the decay rates, and the machine epsilon steps Tace of the fixed-point and MM algorithms and the learning rate of Adam are set to be different with
employ the 10-8 The acceleration
the initialization schemes: Tace = 5. 17 = 0.1 for WISHART initialization and Tace = 10, = 0.01 for BASIC initialization.
In each experiment, we stop the learning when the criterion ((L "i
dest is satisfied. We set daa 10-4 the relative tolerance for all the experiments reported below. We implemented all the experiments in Julia, and all our experiments were a Linux Mini system with 32GB of RAM and an Intel Core 10-10900K CPU @ 3.70GHz.
If(L
5.2 Datasets
We compare the learning algorithms with the following three datasets.
2This is possibly large value that does fail optimization in our datasets.
10

---

Published in Transactions on Machine Learning Research (11/2023)
Synthetic
We make true parameters as L' V*V-T with ii ~ U(0, 10/N) for i.j = 1,,, and sample M realizations from the DPP Pr. (.). We consider three different problem sizes: (N, M) = (32, 2,500), (N, W,M) ) (32, 10,000), and (N, M) (128, 2,500). Because the true parameters are constructed from the uniform distribution, they are likely to have clear structure. Using this Synthetic dataset, test. the general applicability of our method.
In Synthetic, true parameters L' are available; we assess goodness of estimation using not only log- likelihoods but also the von Neumann divergences DoN DL,(L,L) (L, L") = tr( log L L log L' L"), which is Bregman divergence for positive definite matrices.
Nottingham
We apply our method to the Nottingham music datasot which was used in [Boulanger-Lovaadoossd et al. 2012 Osogami al. 2018). The dataset contains more than 1,000 folk tracks the ABC format in which a sequence of chords is stored. We treat each chord in the tracks an i.i.d sample of DPP on the ground set {1,2,... 88), where N = 88 is the number of keys. We randomly pick 25 tracks and that yields M 6,364 samples average.
In Nottingham, there is large disparity in the probability of each item appearing, with very low- and high- pitched keys being rarely used. Moreover, music theory prohibits certain key combinations within a chord. From these facts, the optimal L' of the Nottingham dataset is expected to have unknown but particular structure.
Amazon Baby Registry
Amazon baby registry has served as a benchmark for learning methods of DPPs since Gillenwater el al. 2014). It contains 13 categories of child care products, including "feeding" and "carseats," " and on average, has N 71 items and M 8,585 samples, respectively. We run experiment each of the 13 categories to assess performance of the learning methods for medium-sized recommender systems.
5.3 Experimental Results
Synthetic
The final mean log-likelihoods, runtimes, and von-Neumann divergence values of the Synthetic datasets with the acceleration are presented in Table For each experiment, we conducted 30 trials with different L' and [ and calculated the average and standard deviation. As shown in Table [ our method (MM) achieves the best runtimes for all the settings. While the final log- likellodd values are almost equivalent by the algorithms in WISHART initialization, those obtained by the proposed MM tend to be larger in BASIC initialization. Furthermore, our method also produces the best von Neumann divergences DeN with BASIC initialization and moderately performs with WISHART initialization. The results show good stablity of our method; the proposed algorithm is cousidered to be favorable standard siluations. The result of the Synthetic datasets without the acceleration is also shown in Appendix C
In Figure 2 show the learning curves with and without acceleration. While the fixed-point algorithm convergences stably yet slightly slow without the acceleration, the accelerated version becomes competitive in WISHART initialization. The Adam optimizer may temporarily fall into poor local optima, depending on the initial value. On the other hand, the proposed MM algorithm consistently indicates stable and rapid convergence both with and without the acceleration.
3 Available http:://bbe.ennceefrg....et
11

---

Published in Transactions on Machine Learning Research (11/2023)
Table 1: Final mean log- log-likelihoods, runtimes, and von Neumann divergences DvN (L, L3) of the Synthetic datasets. Each value computed from the average or standard deviation of 30 trials with the accelerated settings.
WISHART Runtime (s)
BASIC Runtime (s)
Data Size
Method
Log-likelihock
vN div.
Log-likellhood
vN div.
FP
15.588 = 0.15
0.39 + 0.03
38.22 + 1.85
15.61 + 0.20
1.46 = 0.31
41.39 + 4.17
N 32
M 2,500
Adam
15.55 0.16
0.36 0.23
56.77 9.40
15.64 + 0.34
0.71 + 0.37
33.42 3.13
MM
-15.58 = 0.15
0.18 + 0.07
42.63 2.38
15.45 + 0.20
0.21 + 0.03
30.16 + 1.97
FP
15.58
0.17
1.32 0.14
38.05 + 2.01
15.77 0.14
5.59 0.85
40.79 +: 3.29
N 32
M = 10,000
Adam
-15.58
0.17
1.23 0.56
49.35 4.54
15.70 0.22
3.05 1.45
32.50 2.11
MM
15.58 + 0.18
0.48 + 0.09
42.53 + 2.43
15.55 + 0.14
0.77 + 0.09
29.75 + 1.52
FP
-30.14 0.18
0.22
36.17 + 0.45
30.34 0.19
6.37 0.48
52.62
N 128
M 2,500
Adam
-30.18 = 0.22
2.50 0.40
44.88 + 1.53
30. + 1.08
2.30 = 0.56
39.44 + 5.54
MM
30.11 + 0.18
0.69 = 0.05
42.54 + 0.53
30.08 = 0.19
1.27 = 0.21
32.15 + 0.55
regarvv TORE 1S Pi Neliood
Ieethoo
meeget hee mesee loge -owe frodd
parne.
parter
WISHART
megatve main optlothoos
BASIC
CRU time 1st
CPU mimemmee
CRU time 351
(a) N = 32, M = 2,500
(b) = 32, M = 10,000
(c) N 128, M = 2,500
Figure Learning curves of the Synthetic datasets. Results with the default parameters (Tace = 0 for fixed-point and MM, and r = 0.001 for Adam) are also shown.
Nottingham
The results of the Nottingham dataset with the acceleration are presented in Table 2 and the learning curves with and without acceleration are showed in Figure g The convergence of Adam remarkably rapid in the Nottingham dataset.
Under the BASIC initialization, the fixed-point and MM algorithms get stuck in poor local optima. Since the optimal L is considered to have particular structure, the BASIC initialization may not be compatible with Nottingham. We can also find the acceleration scheme of the MM algorithm does not perform well in Figure (see also the result. without the acceleration shown in Appendix Cp. This may be because the assumption U Am y for the accelerated MM is not satisfied in the Nottingham dataset.
Amazon Baby Registry
In Table 3 we show the results with the accelerated algorithms in all the 13 categories of Amazon baby registry. Overall, our algorithm achieves moderately better log-likelihood values and outstanding con- vergence speeds most categories. Adam tends produce the best final log-likelihoods but they are not statistically significant. in most. cases. Especially, when the sample size is relatively large, such M > 10,000,
12

---

Published in Transactions on Machine Learning Research (11/2023)
Table 2: Final mean log-likelihoone and runtimes of the Nottigham dataset. Each value is computed from the average or standard deviation of 30 trials with the accelerated settings.
WISHART
BASIC
Method
Log-likelihood
Runtime (s)
Log-likelihood
Runtime (s)
FP
-8.31 0.22
40.68 2.86
-10.13 0.27
33.19 + 8.08
Adam
-7.84 + 1.02
9.01 + 1.59
7.92 + 0.64
21.05 + 6.75
MM
9.51 + 0.24
19.69 4.89
9.58 + 0.21
19.11 + 5.49
negative mean log-llke lhood
Acam (dellau 1)
negative mean log -l-llike ihood
Adamm (defaul))
MM (default)
MM (default)
(occe orated]
10f-22
(aceclerated)
crated)
MM (accel craced)
1g1/2
MM (acceloratee))
10
10
10
20
60
40 CPU time (s)
CPU time (s)
(a) WISHART
(b) BASIC
Figure 3: Learning curves of the Nottingham dataset. Results with the default parameters (Tace 0 for fixed-point and MM, and 17 0.001 for Adam) are also shown.
our algorithm outperforms in the convergence speed that is about 5-10 times faster than the fixed-point al- gorithm.
Although the convergences of the MM algorithm seems be slow in some of the smaller categories in Table that is not very serious. In these cases, the MM algorithm quickly reaches near optimum value, but takes longer to meet the stopping criterion. By managing the stopping criterion, we may be able to stop its learning much carlier.
6 Conclusion and Future Work
In this paper, developed efficient learning method for full-rank DPPs based the MM algorithm. Compared with the existing methods, our algorithm has many advantages: it has guaranteed convergence and monotonicity, requires no bothersome hyperparameters, convergences rapidly and stably, and is easy to implement. Upon considering the performance of our algorithm, we revealed that our algorithm provides a locally tighter minorizer than the existing method. We also assessed the empirical performance of our method through experiments on both synthetic and real-world datasets, outperforming in terms of convergence speed and reaching a better estimate in most experimental settings.
We believe that our algorithm is a strong candidate for learning full-rank DPPs at the present moment, but there is still much future work to be done. First, we need to deepen our understanding of the performance of our method. Proposition 3.3 partially addresses this question, but it is just an implication. One considerable future direction is establishing general recipes for comparing MM with different minorizers. Second, scaling up our method for large N is a crucial issue. Several numerical algorithms for solving large-sized CARE (12) have been proposed based on some structure of a problem: low-rank structure and/or sparsity (Bini et al. 2011 Simonncin] 20166) On the other hand, our CARE g formed by full-rank and dense matrices, therefore, exploring a good CARE solver considered to be essential task.
13

---

Published in Transactions on Machine Learning Research (11/2023)
Table 3: Final mean log-likelihoods and runtimes the Amazon baby registry dataset. Each value is computed from the average or standard deviation of 30 trials with the acceleratod scttings and initialized by WISHART.
Category
Method
Log-likelihodd
Runtime (s)
Category
Method
Log-likelihood
Runtime (s)
Apparel
10.20 0.00
24.54 + 0.69
Gear
-9.27 + 0.00
30.54 0.90
N 100
Adam
10.08 + 0.26
17.99 + 2.61
N = 100
Adam
-9.16 0.41
25.85 + 5.74
M 14,970
MM
10.17 = 0.00
3.13 + 0.30
M 16,823
MM
9..44 + 0.00
2.02 + 0.38
Bath
FP
-8.79 0.00
26.51 = 0.47
Health
FP
-7.59 0.00
13.22 = 0.35
N 100
Adam
8.72 0.79
17.97 + 4.84
N 62
Adam
-7.37 = 0.27
10.06 + 1.66
= 14,542
MM
8.75 0.00
2.06 1 0.47
M = 14,057
MM
7.55 0.00
2.16 0.44
Bedding
FP
-.799 0.00
2.733
Media N 58
FP
8.50
4.01 + 0.67
N 100
Adam
-8.59 + 0.18
23.26
Adam
0.19
2.97 1.07
M 16,370
MM
8.77 +: 0.00
4.79 +: 1.10
M 5,904
MM
8.52 0.01
1.75 + 0.75
Carscats
FP
5.18 0.06
5.04 + 3.27
Safety
FP
1.16
8.93 + 7.46
N = 34
Adam
4.82 + 0.29
2.03 + 0.33
N 36 M = 8,892
Adam
4.30 0.00
2.28 + 0.10
M = 7,566
MM
-5.00 0.05
4.96 + 1.45
MM
+.57
6.19 + 2.10
Diaper
FP
10.71 = 0.00
27.16 + 0.83
Strollers
FP
-5.66 + 0.06
4.58 + 3.21
100
Adam
10.61 = 0.35
25.75 5.96
N 40 M 7,393
Adam
5..5 = 0.38
2.35 0.39
= 16,759
MM
100.67 0.00
3.21 + 0.53
MM
-5.46 + 0.05
6.12 + 2.39
Feeding
FP
12.17 0.00
28.97 0.36
Toys
FP
-8.10 0.00
7.65 + 0.71
N 100
Adam
12.17 = 0.27
18.38 + 5.11
N 62
Adam
-7.94 =: 0.27
5.77 + 1.25
M 19,001
MM
- 12.15 = 0.00
3.11 0.39
M 10,073
MM
-8.07 + 0.00
1.45 + 0.34
Furniture
FP
-4.86 + 0.13
4.93 = 4.75
N 32
Adam
-4.40 + 0.00
1.88 0.05
M 7,093
MM
4.65 1:5:000000
5.37 + 1.78
Acknowledgements
We thank anonymous reviewers for insightful comments and suggestions. Part of this work is supported by NEDO grant number JPNP18002, JST grant number JPMJFS2136, JST CREST JPMJCR2015, and JSPS KAKENHI JP22H03653.
References
Amir Beck and Mare Teboulle. Mirror Descent and Nonlinear Projected Subgradient Methods for Convex Optimization. Operations Research Letters, 3373:16771775 May 2003. ISSN 0167-6377. doi: 10.1016/ 50167-66377002)00223-6
P. Benner and R. Byers. An Exact Line Search Method for Solving Generalized Continuous Time Algebraic Riccati Equations. IEEE Transactions on Automatic Control, 43(1):101- 107, January 1998. ISSN 1558- 2523. doi: 10.1109/9.654499
Dario Bini, Bruno lamnazzo, and B. Meini. Numerical Solution of Algebraic Riccoti Equations. Society for Industrial and Applied Mathematics, Philadelphia, 2011. ISBN 978-1-61197-208-5.
Julius Borcea, Petter Brändén, and Thomas M. Liggett. Negative Dependence and the Geometry of Poly- nomials. Journal of the American Mathematical Society, (2(2):521 2009. ISSN 0894-0347.
Alexci Borodin and Eric M. Rains. Eynard Mehhta Theorem, Schur Process, and Their Pfaffian Analogs. Journal of Statistical Physics, 121(3):291-311 November 2005. ISSN 1572-9613. doi: 10.1007/ 510955-005-75883
14

---

Published in Transactions on Machine Learning Research (11/2023)
Nicolas
Yoshua Bengio, and Pascal Vincent. Modeling Temporal Dependencies in High-Dimensional Sequences: Application to Polyphonic Music Generation and Transcription. In Proceed- ings of the 29th International Conference on Machine Learning, ICML'12, pp. 1881-1888 Madison, W1, USA, 2012. Omnipress. ISBN 1--1---53--2-880
David R. Burt, Carl Edward Rasmussen, and Mark der Wilk. Convergence of Sparse Variational Inference in Gaussian Processes Regression. Journal of Machine Learning Research, 21(131):1-63, 2020. ISSN 1533-7928.
Michal Dereziński, Manfred K. Warmuth, and Daniel Hsu. Unbiased Estimators for Random Design Re- gression. Journal of Machine Learning Research, 23(76)):1 46, 2022. ISSN 1533-7928.
Christophe Dupuy and Francis Bach. Learning Determinantal Point Processes in Sublinear Time. In Proceed- ings of the Twenly-FFirs First International Conference on Artificial Intelligence and Statistics, pp. 244 257. PMLR, March 2018.
Mike Gartrell, Ulrich Paquet, and Noam Koenigstein. Bayesian Low-Rank Determinantal Point Processes. In Proceedings of the 10th ACM Conference on Recommender Systems, pp. 349-356, Boston Massachusetts USA, September 2016. ACM. ISBN 978-1-4503-4435-9
doi: 10. 00.1145//959100.2999177
Mike Gartrell, Ulrich Paquet, and Noam Koenigstein. Low-Rank Factorization of Determinantal Point Processes. Proceedings of the AAAI Conference on Artificial Intelligence, 31(1), February 2017. ISSN
2374-3468, 2159-5399.
doi: 10.1609/ aaaaaiiiv v311..191...
Jennifer Gillenwater, Alex Kulesza, Emily Fox, and Ben Taskar. Expectation-Maxiine Maximizatiinn for Learning Determinantal Point Processes. In Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014.
J. Hough, Manjunath Krishnapur, Yuval Peres, and Bálint Virág. Zeros of Gaussian Analytic Functions and Delerminantal Point Processes, volume 51 of Universily Lecture Series. American Mathematical Society, Providence, Rhode Island, October 2009. ISBN 978-0-8218-4373 978-1-47044166-111 051.
doi: 10.1090/ 10.00///llctt/
David R. Hunter and Kenneth Lange. A tutorial on MM algorithms. The American Statistician, 58(1):30-33 February 2004. ISSN 0003-1305, 1537-2731. doi: 10.1198/0003130042255
Diederik Kingma and Jimmy Ba. Adam: A Method for Stochastic Optimization. Conference on Learning Represenlations. arXiv, 2015. doi: 10.48550/arXivv1411
International
Alex Kulesza and B. Taskar. K-Dpps: Fixed-Size Determinantal Point Processes. In International Conference on Machine Learning, June 2011.
Alex Kulesza, and Ben Taskar. Determinantal Point Processes for Machine Learning. Foundations and Trends@ in Machine Learning, 5(2-3):123 286, 2012. ISSN 1935-8237, 1935-8245. doi: 10.1561/ 2200000044.
Kenneth Lange, Joong-Ho Won, Alfonso Landeros, and Hua Zhou. Nonconvex Optimization via MM Al- gorithms: Convergence Theory. In Wiley StatsRef: Slatistics Reference Online, pp. 22. John Wiley & Sons, Ltd, 2021. ISBN 978-1-118-4451122 doi: 10.1002/9781118444 100711118511122s000002205 12.st
A. Laub. A Schur Method for Solving Algebraic Riccati Equations. JEEE Transactions on Audomatic Control, 24(6):913 921, December 1979. ISSN 1558-2523. doi: 19t.:/TTA..9..111092909
Odile Macchi. The Coincidence Approach to Stochastic Point Processes. Advances in Applied Probability, 7 (1):83-122, 1975. ISSN 0001-8678. doi: 10.2307/1425881
Zelda Marict and Suvrit Sra. Fixod-Point Algorithms for Learning Determinantal Point Processes. In Proceedings of the 32nd International Conference on Mochine Learning, pp. 2389 2397. PMLR, June 2015.
15

---

Published in Transactions on Machine Learning Research (11/2023)
Zelda Mariet, Mike Gartrell, and Suvrit Sra. Learning Determinantal Point Processes by Corrective Negative Sampling. In Proceedings of the Twenty-Second International Conference on Arlificial Intelligence and Statistics, pp. 2251 2260. PMLR, April 2019.
Zelda E. Mariet and Suvrit Sra. Kronecker Determinantal Point Processes. In Advances in Neural Information Processing Systems, volume 29. Curran Associates, Inc., 2016.
Zelda Elaine Marict. Learning with Generolized Negative Dependence Probabilistic Models of Diversity for Machine Learning. Thesis, Massachusetts Institute of Technology, 2019.
Naoto Miyoshi and Tomoyuki Shirai. A Cellular Network Model with Ginibre Configured Base Stations. Advances in Applied Probability, 46(3):832 845, September 2014. ISSN 0001-8678, 1475-6064. doi: 10. 1239 1239/aap/ /a/////////119995555
Arkadi Nemirovsky. Problem Complerity and Method Efficiency in Optimization. Wiley-Interscience Series in Discrete Mathematics. New York: Wiley, 1983. ISBN 978-0-471-10345-5.
Takayuki Osogami, Rudy Raymond, Akshay Goel, Tomoyuki Shirai, and Takanori Maehara. Dynamic Determinantal Point Processes. Proceedings of the AAAI Conference on Artificial Intelligence, 32((), April 2018. ISSN 2374-3468.
doi: 10.1609/ 20.1669/aaai.v32i11 v32i..3221
Neal Parikh and Stephen Boyd. Proximal Algorithms. Found. Trends Optim., 1(3):127-239) January 2014. ISSN 2167-3888. doi:
Tomoyuki Shirai and Yoichiro Takahashi. Fermion Process and Fredholm Determinant. In Proceedings of the Second ISAAC Congress, pp. 15 23. Springer, 2000.
V. Simoncini. Computational Methods for Linear Matrix Equations. SIAM Review, 58(3):377 441, January 2016. ISSN 0036-1445, 1095-7200. doi: 10.1137 10.1137/13011283! 130912899.
A Soshnikov. Determinantal Random Point Fields. Russian Mathematical Surveys, 55(5):923 975, October 2000. ISSN 0036-0279, 1468-4829. doi: (0.107//RM200005500AABBEEH0O
Ying Sun, Prabhu Babu, and Daniel Palomar. Robust Estimation of Structured Covariance Matrix for Heave-Tailed Elliptical Distributions. IEEE Transactions on Signal Processing, 64(14):3576 3590, July 2016. ISSN 1941-0476. doi: 10.1109/TSS Stt.//TS......2....2 2246222..
Ying Sun, Prabhu Babu, and Daniel P. Palomar. Majorization-Miniiize. ing, Communications, and Machine Learning. IEEE Transactions on Signal Processing, 65(3):794 816, February 2017. ISSN 1053-587X, 1941-0476.
Algorithms in Signal Process-
doi: 10.1109/TSP.216..22
Alan L Yuille and Anand Rangarajan. The Concave- Concave-Convex Convex Procedure (CCCP). In Advances in Neural Information Processing Systems, volume 14. MIT Press, 2001.
A Proof of Proposition 3.3
A.1 Derivation of Equation 115
In 14h, ; the constant term is given by
1 M
()) = M
log dU A., U.A)) +mmml log det (L + - (L + +1)-
m=1
By the following inequality from the Taylor expansion
log det((L 2 log dL) tr((L tr -)}.
16

---

Published in Transactions on Machine Learning Research (11/2023)
have
110000000--000000001110000100-01 --- -- log (Lt log det L (0)
-r [r(
-
( L}}
= -1-"""L1------'"
- tr ( - N
=
A.2 Derivation of Equation (66)
Let L ()) 6M, where 5 > O is sufficient small coefficient and M is symmetric matrix whose
all eigenvalues are in [-1.1] 1]. Then, can approximale the matrix inverse as L-1 (L + 6M)
(t) ML (+)-1 by the Taylor expansion. Using this approximation, we have
2L L L (1 (L 8M) (I + L
= 21 (0) (L -5M) 10 (Z (1-
=0.
B Proof of Proposition 4.1
Proof- Sato (I) can be minorized
futes (1)
1
(log (L).()) (00) log det det(( (L]]A.. - -u (r(()()
(1) [A(
log (L (L+11 +I)
+const.
majorizing by 33) w/
majorizing by 3 w/
x + D A)
X - + I.
+ [L [Am
Y - L (1) +1
log det [LJA.)
-0 te((LL (LAm)) 100tr(LL)
1Am )) (1)
tr((L + +1)++++11 - + const.
M
minorizing by (4) w/
X
Am
(1)
M
Σ (1+ 10)) tr([L)]], (Am) +u 1 1L (bIAm)) -r(( + const.
2 M
m=1
majorizing by 7 w/
APA Am
S + [1( Am
2 1 1 (9) M
M Σ
UT Am 1 UA, L-1 L-11
m=1
((0) M
(r(
Am [I]Am.) Lr (r( -)) + const.
M m=1
9pto (1).
C Additional Experimental Results
Table C.1
shows the learning result of the Synthetic dataset with the default (non-accelerated) settings.
Tace for fixed-point and MM and n 0.001 for Adam are used the default, settings. We find the
17

---

Published in Transactions on Machine Learning Research (11/2023)
Table C.1: Final mean log-likelihoods, runtimes, and von Neumann divergences DL, L'* the Synthetic datasets. Each value computod from the average or standard deviation of 30 trials with the non-accelerated settings.
WISHART Runtime (s)
BASIC Runtime (s)
Data Size
Method
Log-likelthood
div.
Log-likelihood
vN div.
FP
15.58 + 0.15
0.43 0.06
38.20 + 1.84
15.61 + 0.21
1.69 + 0.22
42.19 + 4.19
N 32
M 2,500
Adam
15.63 0.15
3.29 0.25
63.07 + 5.71
15.54 0.20
3.41 + 0.17
29.51 1.85
MM
15.58 0.15
0.40 0.06
43.94 + 2.62
15.46 0.20
0.32 + 0.03
30.15 1.99
FP
15.58
0.18
1.32 = 0.17
38.03 + 2.00
15.72 0.14
5.53 + 0.96
41.61 + 3.30
N = 32
10,000
Adam
15.66
0.17
12.83 1.11
61.41 + 5.40
1 0.14
14.50 0.56
29.08 1.23
MM
15.58 + 0.18
1.22 0.16
43.95 + 2.58
- 15.56 0.14
1.00 + 0.11
29.74 + 1.47
FP
3.70 0.18
36.20 + 0.44
-30.35 0.19
6.56 + 0.45
53.47
N 128
M 2,500
Adam
-30.05 + 0.19
24.05 0.78
85.47 + 4.02
- 30.112 0.19
5.84 + 0.23
33.44 + 0.56
MM
0.11
1.39 = 0.08
44.68 + 0.62
30.10 0.19
1.29 + 0.07
32.26 + 0.50
Table C.2: Final mean log-likelihoods and runtimes of the Nottigham dataset. Each value is computed from the average standard deviation of 30 trials with the non-accelerated settings.
WISHART
BASIC
Method
Log-likelihood
Runtime (s)
Log-likelihood
Runtime (s)
FP
-8.30 + 0.22
40.92 + 3.01
- 110.14 + 0.28
33.75 + 6.84
Adam
-7.81 = 0.25
68.12 4.94
-8.02 + 0.26
103.27 = 15.57
MM
-9.51 0.25
21.73 6.04
-9.59 + 0.22
19.95 + 3.59
proposed MM algorithm with the default setting still performs better than the other algorithms with the accelerated settings, shown in Table
Table C.2 shows the result of the Nottingham dataset with the default settings which is the same to the Synthetic experiments. In contrast to Synthetic, the performance of the MM algorithm with and without the acceleration is not much different (cf. Table 2. This may be due to the absence of the assumption required in the accelerated MM algorithm. We need that Um Am y in Section 4 but Nottingham does not satisfy that as described in Section
18


Reviews:
[{"review_id": "mAYq2g1Ern", "reviewer": "Reviewer_EE9h", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I like the vibe of the paper, but I have some qualms about the quality of the evidence supporting their proposed algorithm. This leads me to a borderline review of the paper.\n\nAt a high level:\n- The principle behind the algorithm is nice and simple.\n- The theoretical proofs in the paper are too short and hard to follow. I'm not completely convinced of their correctness, despite their brevity.\n- Their algorithm computes a lower bound for the likelihood at each iteration. Their core theoretical result claiming that the proposed algorithm outperforms the prior work claims that their computational lower bound is tighter than the lower bound used in a prior work's algorithm. However, this claim only holds in a small neighborhood of the current iterate, and their algorithm may look outside this neighborhood at each iteration. That is, this claim seems a bit mismatched for the algorithm.\n- Also, it's not clear to me, even without worrying about this neighborhood, why a tighter lower bound here would translate to a better algorithm.\n- The algorithm is very straightforward and easy to implement (top of page 5)\n- The experiments show the proposed algorithm often outperforms the existing algorithms.\n\nMy overall take is that, if I can be assuaged of my technical concerns about the proof, then I'm inclined to accept the paper as a good fit for TMLR.\n\n---\n\nNow let's get into the weeds of it.\n\n### On the Theoretical Results\n\nThe proposed algorithm is based on taking the log-likelihood function (equation 1 on page 3) and taking a taylor approximation of both terms in the sum, producing a lower bound on the actual log-likelihood. Equation 3 on page 3 shows one of these lower bounds, done by Taylor approximation. This approximation is fine, but the approximation for the other term (equations 5 and 6 on page 4), are completely opaque to me. I don't understand how the proof works. _I sort of softly expect there to be an error here even, since the Taylor approximation is used to give both an upper and lower bound on the log determinant across pages 3 and 4, so I'm not clear how that works_.\n\nThe math in the paper often skips showing their work, and there are other important lines in the math that I don't follow. I also don't understand how Corollary 3.1 on page 5 is proven, for instance. I'm not a big fan of that, though their claims are not very strong, so I wouldn't be surprised if the math is correct. I don't think they explain it enough though.\n\nThe weight of the theoretical results are a bit unclear to me; a bit of a mixed bag. They give three core theoretical guarantees:\n- (Prop 3.1 on page 4) Their lower bound on the likelihood is of the right form to be used in an MM style algorithm.\n- (Corol 3.1 on page 5) The $L$ matrix and $Q$ matrix in their algorithm have the same rank.\n- (Prop 3.3 on page 6) The lower bound in the proposed algorithm is tighter than the lower bound in a prior work, but only in a small enough neighborhood of the current iterative.\n\nThe first result is essential for the correctness of their algorithm. The second result is used as evidence suggesting that the algorithm without any regularization would return a degenerate kernel matrix (i.e. with some eigenvalues exactly equal to zero). This is a bit shakey, but I'm okay with it.\n\nThe third result... I'm not really sure what it serves to prove. Is there any reason that being tighter in a small enough neighborhood should mean that this nonconvex optimization algorithm should perform better than another nonconvex optimization algorithm? I don't really even see an intuition for why this should be the case. It's certainly not fully argued in the paper. The authors do specifically note that the lower bound (\"minorizer\") in the prior work is non-convex, which \"implies that the [prior work] algorithm is possible [sic] to get trapped in poor stationary points\". This point is especially weak of a justification because:\n- The proposed algorithm is also a non-convex optimization strategy. It just happens to have one step within it which is convex.\n- The other bound being non-convex does not imply that it has spurious minima. The plot in Figure 1(b) on page 6 makes the function look quasiconvex, with no evidence of spurious minima in sight.\n\n### On the Empirical Results\n\nThe paper has a nice suite of experiments over a nice set of synthetic and empirical problems. I'm overall pretty happy with it, and it does suggest that the proposed algorithm is at least competitive, and often a good deal better than both the prior work on learning DDPs and the out-of-the-box adam optimizer.\n\nThe paper places some emphasis on algorithms can are parameter-free, and easy to work implement as a result. The proposed algorithm is mostly parameter free (it has an epsilon regularization which they recommend setting around machine epsilon; not a big deal). The ADAM optimizer has a good deal of parameters, which they use fairly default values for. The prior work algorithm has a step-size parameter which they set to $a=1$. I take some issue with this.\n- They use $a=1$ because the prior work only guarantees that their algorithm converges monotonically when $a=1$. However, the authors of this paper make it clear that the prior work did this in order to improve the empirical performance of their algorithm (page 2, the sentence starting with \"In (Mariet & Sra), ...\"). The experiments section should acknowledge the empirical techniques used to make the prior work algorithm work better, and it feels odd to not even engage with that in the writing of the experiments section.\n\nBeyond this issue, the experiments are nice, and show that the proposed algorithm typically outperforms the other algorithms considered. They consider a nice spread of experiments, with different initialization techniques. They report parameters well with easy to read plots and tables. It's largely well put together. I've got some pedantry to discuss in the experiments (in the \"requested changes\" section below), but it's nice and compelling. It especially shows that the proposed algorithm is faster and better performing than the prior work and ADAM algorithms for larger datasets. Often, this isn't a huge speedup relative to the ADAM optimizer, but it's still a win I suppose. It's good stuff.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a Minorization-Maximization (MM) style algorithm for learning a kernel matrix that represents a discrete determinantal point process (DPP) on $n$ points. That is, we are given a base set of size $n$, and a training dataset which is a list of subsets of $[n]$. For some kernel matrix $K$, we can use DPP sampling to sample some subset of $[n]$. Our goal is to learn a kernel matrix $K$ that, when using DDP sampling, maximizes the likelihood of the training dataset.\n\nThe proposed algorithm is an iterative nonconvex optimization algorithm, which requires inverting a matrix and solving a \"continuous algebraic Ricatti equation\" in each iteration. These linear algebra tasks are computable at the moderately-large-data scale, but not the truly big data scale, which the paper owns.\n\nThe paper has some theoretical and a good deal of experimental evidence. The theoretical results show that the approximation to the likelihood used by the proposed algorithm is more accurate than the lower bound used in a prior work's algorithm, but this claim only holds in a neighborhood of the current iterate. The experimental evidence suggests that the algorithm works well in practice, but the claim that it outperforms other algorithms it a bit messier.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I listed my big picture qualms above, in the \"strengths and weaknesses\" section. I'll be extremely concrete here. Afterwards, I'll write the list of typos / minor recommended edits.\n\n1. [Proof of Prop 3.1] Explain the inequalities used more. What is $P_t$, $R_t$, and $P$? What is the exact taylor approximation being used? What is happening in this proof? It's completely unfollowable.\n1. [Proof of Prop 3.2] Consider showing more work in how you prove equation (8). It's not super important here, but this one is a bit more work to do on your own. Feel free to ignore this point.\n1. [Proof of Corol 3.1] I have no idea how the first equality between the ranks holds. Just because $L^{(0)} + I$ is invertible, it doesn't mean that $L^{(1)}$ can't be a low-rank matrix whose span gets rotated by $(L^{(0)} + I)^{-1}$ to lie in the nullspace of $L^{(1)}$.\n1. [Page 6, paragraph before section 3.4] This whole paragraph is kinda important, but also kinda weak justifications. I don't really know why the tighter inequality makes \"it likely that the proposed method with produce better $L^{(t+1)}$\" or why the fixed point's non-convexity (but plausible quasiconvexity) would mean that it's possible for it to get stuck in spurious minima.\n1. [Page 7] Why should the basic distribution be \"unstructured\". It's also a Wishart matrix that's concentrated around some (maybe scaled?) identity matrix. It's well studied in random matrix theory. It's gonna have some similar structure to the \"Wishart\" scheme, no? This is a particular issue for [Page 9], where the you describe the Basic and Wishart schemes as being fundamentally different for the Nottingham dataset.\n1. [Page 7] I'm not familiar with the Nottingham dataset. Without an introduction, the paragraphs about Nottingham are incomprehensible. What is the dataset about, what are tracks, what are samples, what are folk tracks in the ABC format, and more questions remains unclear. The baby registry is very well explained, for a point of reference.\n1. [Page 9] You say that ADAM is at an advantage for the Nottingham data because it's allowed to be non-monotonic. But it was your choice as authors to force the fixed-point algorithm to be non-monotonic by setting $a=1$. Why pick this values of $a$ if the monotonicity hurts you?\n1. [Page 10] The benefit of the proximity term is not clear at all. What do you think will be the upside of using such an algorithm?\n\n---\n\nTypos and minor recommended edits.\n1. [Page 1] Replace \"Suppose A and B\" with \"If A and B\", and replace \"ground set, P(A \\cup B)\" with \"ground set, then P(A \\cup B)\"\n1. [Page 2] Replace \"virtual\" with \"hypothetical\"\n1. [Page 2] Replace \"intensities\" with \"density\" (unless this is a technical term I'm unfamiliar with)\n1. [Page 3] Replace \"ground set have\" with \"ground set has\"\n1. [Page 3] Replace \"MLE, that is,\" with \"MLE. That is,\"\n1. [Page 3] Replace \"is a submatrix\" with \"is the submatrix\"\n1. [Page 4] Replace \"multiplying the both\" with \"multiplying both\"\n1. [Page 5] Write $L$ and $\\varepsilon$ as inputs to the algorithm... because they are inputs. Otherwise, it's completely unclear how to initialize these parameters until well later (like well into the experiments section).\n1. [Page 5] Just before section 3.3, describe some idea on how to initialize L. It's sufficient to say you'll discuss it in the experiments section, but at least acknowledge it.\n1. [Page 6] Be more rigorous in the statement \"in the neighborhood\". Specifically, say the order of quantification. I think it's something like \"for each L, there exists a small enough neighborhood around L such that every M with eigenvalues between -delta and +delta has g(L+M) > h(L+M)\", or something like that.\n1. [Page 6] In Section 3.4, include the number of iterations in the big-Oh, or describe the big-Oh as the cost-per-iteration, rather than the cost of the method.\n1. [Page 7] Capitalize the section 4 title\n1. [Page 7] Define the fancy U as the uniform distribution.\n1. [Page 9] You say that your algorithm achieves better log-likelihood values, but it's by a rather narrow lead. Maybe acknowledge how small that lead is? Up to you, but it felt a bit underwhelming to start by reading that you get better log-likelihoods just to look at the tables and see all methods produce very similar log-likelihoods.\n1. [Page 10] \"it is not enough\" -- be more concrete. What would be enough, and why is this result too weak? What would you hope to be able to prove, for instance?", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ShPp4VBXaz", "reviewer": "Reviewer_qfjS", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n\n* The learning problem under study is important. DPPs are relevant models in machine learning due to their ability to model negative dependence, thus, encouraging the occurrence of diverse subsets and making them suitable for various applications.\n\n* The proposed approach results from a simple application of the MM algorithm. Thus, the paper is easy to follow.\n\n* Practical applicability. The proposed learning algorithm offers several positive properties: easy to implement, hyperparameter-free, and well-behaved. It can be readily used for exact inference on small to medium-sized datasets, making it suitable for various machine learning tasks that require diverse subset generation.\n\n* The code was easy to run and reproduce the experiments.\n\n### Weaknesses\n\n* The technical contribution, in general, is rather incremental. \n\n* It is unclear how the proposed minorizer truly affects the convergence rate. The authors claim that their method attains faster convergence empirically. However, in several cases, such as in Table 3, I noticed that Adam obtains faster runtimes than MM (the proposed approach) and comparable log-likelihoods to MM.  \n\n* I believe the paper would benefit from additional proof and experiment details. For example, in the proof of Proposition 3.1, a matrix inequality is recalled from Sun et al. (2016) and Sun et al. (2017). It would be much easier to either provide an explicit reference to the inequality in those papers or elaborate more on what $A$ and $P_t$ are. For the latter, are A and $P_t$ any matrix, or are they both required to be positive definite? In the experiments, it was not clear whether batch or minibatch was used for Adam, and I had to look at the code to clear my doubts.\n\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces a new method for learning full-rank Determinantal Point Processes (DPPs). \n\n1. The paper's main contribution is introducing a simple learning recipe based on the minorization-maximization (MM) algorithm. The proposed method allows for efficient and stable learning, increasing the log-likelihood monotonically at each iteration.\n\n1. The authors compare the (local) tightness of the minorizers between the existing and proposed methods. The existing fixed-point algorithm for DPPs (Mariet & Sra, 2015) can also be viewed as an MM algorithm. The results indicate that the proposed minorizer provides a tighter lower bound **locally** than the existing method. Furthermore, the proposed method's minorizer is concave; in contrast, the existing method maximizes a non-concave minorizer during each iteration.\n\n1. The paper conducts experiments to evaluate learning algorithms for full-rank DPPs using synthetic and real-world datasets. The authors focus on convergence speed and performance in terms of log-likelihood to compare against existing methods.\n\n", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Expanding on the weaknesses mentioned above:\n\n* I believe using only $a=1$ for the fixed-point method is unfair. Looking at the paper by Mariet & Sra (2015), I noticed that they rarely set $a=1$. While their convergence guarantee is shown for $a=1$, they also suggest that values $a>1$ also often work well. I would help to see what happens with their method for, say, $a \\in \\\\{1.3, 1.5, 2\\\\}$? Similarly, for the Adam method, it would help to see what happens for $\\eta = 10^{-8}$. The authors state that they observe failures in the optimization for $\\eta \\geq 10^{-7}$, yet they decided to set $\\eta = 10^{-9}$. Given that the proposed method barely improves over Adam in terms of runtime, I am curious if this change would result in Adam being faster than MM in more settings.\n\n* While the code was easy to run, it would help to clarify a few things: I noticed that in the file `dpp_utils.jl` the function `mle_mm` does not call the function `compute_minorizer_mm`, which was confusing to me. Similarly, for the function `compute_minorizer_fp`. I am not an expert on Julia so I might have missed something here.", "broader_impact_concerns": "No concerns here.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "SbUOp2AgfF", "reviewer": "Reviewer_ENwe", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n- The proposed algorithm is elegant, and also subsumes prior work as a special case\n- The algorithm requires no hyperparameters to tune, and is guaranteed to improve the log-likelihood at each step\n- Under the evaluated experimental conditions, MM almost always significantly cuts down on the runtime of (Mariet & Sra, 2016).\n- The experimental validation is well presented, and the conclusions are clear.\n\n# Weaknesses\n- Clarity: there are a couple of statements that should be clarified. \n  + I believe that the concept of \"negative dependence\" (second paragraph of the introduction) is in fact a precise concept that is not equivalent to $P(A \\cup B) < P(A) P(B)$ (c.f. _Negative dependence and the geometry of polynomials_, Borcea et al., 2007). Given the importance of negative dependence as a motivator for the use of DPPs in the community, I would recommend the authors use more precise terminology here.\n  + Could you clarify the inequality $P(A \\cup B) < P(A) P(B)$? It almost looks like the \"negative association\" condition (_Negative dependence and the geometry of polynomials_, Borcea et al., 2007), but that one requires a disjoint set of coordinates. Also, should it be a loose $\\leq$, in the case where A and B are independent?\n  + It might be worth clarifying for non-expert readers that the requirement $0 \\leq K \\leq I$ is necessary to ensure that the resulting probabilities $0 \\leq P(K_S) \\leq 1$.\n  + Not all DPPs admit a formulation with kernel $L$; if I remember correctly, this is only true if $K$ has all eigenvalues < 1, which is equivalent to $P(\\emptyset) > 0$. \n  + At the end of the introduction, could you clarify why the concavity of the minorizer is important?\n \n- Experimental validation\n  + I am confused by the process by which the \"best\" performance is bolded in the tables. Often, different algorithms will have the exact same performance, but only one will be bolded (seemingly randomly, e.g., in the synthetic datasets).\n  + Nottingham analysis: it seems like MM (and FP) converge poorly for both initializations, not just BASIC. I'd be interested in a more in-depth analysis of what could be causing this. The authors mention expecting a specific structure for the optimal kernel L. Could it also be that the MM-based algorithms (including FP) perform less well for large $N$, or that they converge to almost singular matrices?\n\n# Questions for the authors\n- Would it be possible to introduce a step size $a$ in the same way that (Mariet & Sra) do?\n- Would MM be amenable to specific structures such as low-rank or Kronecker constraints?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a novel algorithm to learn the (full-rank) kernel matrix that parameterizes a determinantal point process (DPP).\n\nTaking advantage of the fact that the DPP log-likelihood is a sum of concave and convex functions, the authors propose a learning procedure based on minorization-maximization (MM). The authors compare their method to (Mariet & Sra, 2015) -which relied upon a similar decomposition of the log-likelihood - and show that the MM procedure relies upon a tighter approximation to the true log-likelihood in the neighborhood of the current iteration.\n\nEach MM learning iteration has a computational cost equal to that of (Mariet & Sra), but the authors show on synthetic and the Amazon Baby registry (a canonical experimental dataset for DPPs) datasets that MM converges in significantly less CPU time.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please address the comments above.", "broader_impact_concerns": "n/a", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This manuscript considers the problem of learning a determinantal point process (DPP) from observations. The setting considered is observing a set of samples from the DPP (which are subsets of elements from a ground set) and we seek to estimate the kernel matrix of the DPP to maximize the likelihood of the observed samples. The authors propose a minorization-maximization algorithm for this estimation problem and prove a lower bound on the likelihood it achieves. The lower bound is tighter than the best-known bound for this problem and appears to perform well in a series of experiments.

The reviewers tend to agree that the work presented in this manuscript is high quality and of interest to the TMLR audience, and the majority of them recommend acceptance.

Throughout the review and discussion period, the reviewers provided feedback and suggestions that the authors have faithfully incorporated into the manuscript. I believe these changes have considerably strengthened the work. I commend both authors and reviewers for their engagement throughout this process.

Although I am recommending that this manuscript be accepted as is, I would like to invite the authors to consider the further refinements recommended by reviewer EE9h in their official recommendation.
Decision: Accept (poster)