Kernel Matrix Estimation of a Determinantal Point Process from a Finite Set of Samples: Properties and Algorithms
Authors: Marc Castella
Jean-Christophe Pesquet
Venue: Accepted by TMLR ()

Abstract: Determinantal point processes (DPPs) on finite sets have recently gained popularity because of their ability to promote diversity among selected elements in a given subset. The probability distribution of a DPP is defined by the determinant of a positive semi-definite, real-valued matrix. When estimating the DPP parameter matrix, it is often more convenient to express the maximum likelihood criterion using the framework of L-ensembles. However, the resulting optimization problem is non-convex and N P-hard to solve.

In this paper, we establish conditions under which the maximum likelihood criterion has a well-defined optimum for a given finite set of samples. We demonstrate that regularization is generally beneficial for ensuring a proper solution. To solve the resulting optimization
problem, we propose a proximal algorithm which minimizes a penalized criterion. Through simulations, we compare our algorithm with previously proposed approaches, illustrating their differing behaviors and providing empirical support for our theoretical findings.

Published in Transactions on Machine Learning Research (03/2026)
Kernel Matrix Estimation of a Determinantal Point Process from a Finite Set of Samples: Properties and Algorithms
Mare Castella
marc.csstellaa@teeecoo.
SAMOVAR, Télécom SudParis, Institut Polytechnique de Paris, 91120 Palaisean, France
Jean- Christoprit Pesquet
OPIS Inria, CentruleSSuelle, Université Paris-Suclag, France
Reviewed on OpenReview: https: // opwpr/veenee...... net/ formm? id- Cyz9L
Abstract
Determinantal point processes (DPPs) finite sets have recently gained popularity bo- cause of their ability to promole diversity among selected elements in a given subset. The probability distribution of a DPP is defined by the determinant of a positive semi-definite, real-valued matrix. When estimating the DPP parameter matrix, it is often more convenient to express the maximum likelihood criterion using the framework of L-ensembles. However, the resulting optimization problem non-convex and A'P-hard solve.
In this paper, we establish conditions under which the maximum likelihood criterion has a well-defined optimum for a given finite set of samples. We demonstrate that regularization is generally beneficial for ensuring a proper solution. To solve the resulting optimization problem, we propose a proximal algorithm which minimizes a penalized criterion. Through simulations, we compare our algorithm with previously proposed approaches, illustrating their differing behaviors and providing empirical support for our theoretical findings.
1 Introduction
Many modern application domains require to generate or promote diversity in samples. This is for example the case in document summarization (Lin & Bilmes 2012), recommender systems (Zhou et al. 2010) but also in optimization and learning (Zhang et al. 2017]. Spatial statistics yet another domain where diversity can play an important role, for example for sensor placement (Krause et al., 2008), cellular networks [Miyoshi & Shirai 2014; Torrisi & Leonardi 2014). Determinantal Point Processes (DPPs) are precisely probabilistic models for random sets that promote diversity. Indeed, DPPs are known to encode repulsion between elements, meaning that sets containing points that are close similar to each other are less likely to occur.
DPPs already appeared in the 60's and were later identified in Macchi 1975 where they were called 'fermion processes'. They also naturally appear in several situations such as random matrix theory (Soshnikov) 2000 or quantum theory. Since then, they have been quite extensively studied by mathematicians (Hough et al. 2009 Borodin, 2015) and they appear in many places probability, algebra, and combinatorics. Besides they have been considered both in continuous setting as point processes, or in a discrete setting subsets of given finite set.
Recently, they have gained renewed attention in the data science community Kulesza & Taskar 2012 and related applications such as recommendation systems (Gartrell et al. (2/7) document or data sunmarization Burt et al. 2020 Tremblay et al. 2019). image processing (Launay et al. 2021, random design (Derezinski ct al. 2022 ... particularly appealing property of DPPs that can explain their incrcasing popularity that many inference tasks can be performed efficiently. As a consequence, the problem of learning the parameters of DPP appears crucial although it is considered challenging problem. A common approach relies

---

Published in Transactions on Machine Learning Research (03/2026)
upon the maximum likelihood estimator. It has been conjectured by Kulesza in his thesis that the problem is -PP-comllete, a proof of which recently appeared in Grigorescu et al. (2022). The explored solutions to this issue either try to learn the full underlying kernel or a few parameters encoding it.
The first class of approaches for inference on DPPs consider a parametrized form of the kernel and make specific assumptions (Kulesza Taskar, 2011 Affandi et al.) 2014 Bardenet & Titsias, 2015). To tackle the continuous case, such a parametrized approach has been the most natural; see e.g. [Biccio & Lavancier (2117) for minimum contrast estimation technique and other works from the same authors. In the second class of approaches, which aim to learn the full kernel, carefully designed methods are required. Gillenwater ct al. (2014) proposed first approach and in [Affandi et al. (2014) a Bayesian MCMC method was used. Alternatively, methods based on optimization are likely to play a prominent role as described in the next section. A somewhat intermediate route consists in imposing a modeling structure on the kernel matrix. For example, a common framework assumes low rank matrices (Dupuy & Bach 2016 Gartrell et al. (017). but other structures exist (Marict & Sra 2016). Note that more general models have drawn attention and learning based on maximum likelihood has also been addressed for non symmetrical DPPs in Gartrell et al. (2019).
This paper addresses the problem of umparametrized DPP parameter estimation on finite sets, starting from a maximum likelihood (ML) formulation to learn a DPP kernel from an optimization perspective. We begin by showing that a minimizer of the ML objective does not necessarily exist. More precisely, the criterion infimum can only be approached when the norm of the estimated parameter goes to infinity. Beyond computational complexity, this issue suggests that alternative models may be better suited, or that one must settle for an approximate model. We here consider the latter possibility and explore the introduction of a regularization term. Regularization techniques are well-established in statistics and closely related to the Maximum a Posteriori (MAP) estimation framework (see, e.g., [ishhop (2006); Hastie et al. (2009)). Within this context, we demonstrate the relevance of using proximal algorithms, which are well-suited for solving large-scale, potentially nonsmooth optimization problems where the objective splits into the sum of multiple terms. In view of the variely of penalization terms that can be handled by proximal methods, this paves the way to the development of more accurate estimation criteria.
1.1 Related works
The work in this paper has been motivated by works from different streams: optimization, DPP kernel parameter estimation, and DPP models in lesser way.
Several optimization methods related to our problem have been developed, starting from the EM like method Giilennwater et al., 2014) which tries to infer the marginal kernel of the DPP. Adopting the slightly less general model of an L-ensemble, the (log)-ikelihhod criterion simplifies. A particularly efficient algorithm based on a fxxen-point iteration has been proposed in Mariet Sral (2015) and interpreted as a minimization- maximization like algorithm. In Kawashima & Hino (2023), based on the latter viewpoint, a tighter local majorizer has been derived and an accelerated version of the algorithm has been introduced. However, difficulties in the convergence of the iterates were not deeply investigated. Both works only deal with full- rank DPPs, whereas some other works try to promote some structure (Mariet & Sra. 2016). The low-rank assumption remains the most common assumption explicitly made (Gartrell et al. [017]] 2018). Yet another trend in this line of works is to introduce some regularization terms in the criterion (Dupuy & Bach 2016). The additional penalization term has been reported to allow good predictive performance of the estimated model in Gartrell et al. (2017). For continuous DPPs, a nonparametric cstimation based on kernel methods has also been proposed and has led to similar criteria in Fanuel & Bardenet, (2021). The mentioned works are a non exhaustive list of the many proposed approaches.
Despite the varicty of methods proposed for infering DPPs, the basic properties of the maximum likelihood estimator have received little atlention. Exceptions not directly related to our work are Lavancier el al. (2015;; Biscio & Lavancier (2017). which make strong parametric assumptions, and Baraud (2013) which makes smoothness assumptions. More closely, the authors in Brunel al. (2017) study the properties of the expected log-likelihood function and show that it has exponentially many saddle points. They establish condition under which the global optima have strictly positive, but arbitrarily small, strong convexity
2

---

Published in Transactions on Machine Learning Research (03/2026)
constant. Finally, they prove several convergence rates for the maximum likelihood estimator. Our approach differs in that we consider a finite number of samples without making any additional specific assumptions. In other words, we work with the finite-sample likelihood rather than the expected likelihood function. Let
us also mention that other approaches exist such as in Urschel et al. (2017): Brunel & Urschel 2024). which are based on moments and the principal minor assignment problem.
1.2 Organization of the paper
The addressed problem is described in Section 2 with introductory elements about DPPs. Novel properties about the maximum likelihood estimator in the case of a finite sample set are stated in Section 3 The proposed regularization and corresponding optimization algorithms are then described in Sections and Simulation results are given in Section G and Section i concludes the paper.
Notation:
N.. For any For any subset X = {V1,...., jtiin S X, where V1 < ... < VI we define selection matrix Ux N by Ux ley...... Cyx I where ej is the hth unit vector of RN (i.e., element of its canonical basis).
Throughout all the paper, N > 1 is fixed integer and define the set X' {I,...,NN; set X C X, its cardinality is [X|.
For any matrix M E N and any subsets R,C C, X, we denote Ma.c ||| the submatrix obtained by keeping in M rows indexed in and columns indexed in C. We will use the shorthands MR. when all columns are kept (C X), M.c when all rows are kept (R = X), and finally Mx Mx,x for any principal submatrix with columns and rows given by X C X. Accordingly, have Mx Ux MUx and Mx,: = Ux M.
S. denotes the space of real-valued symmetric matrices of size N x N. while SN is the cone of positive definite matrices in Sº, For any matrix M, det(M) is its determinant. If M e SN, X is its htth real eigenvalue, ordered by increasing values. Finally, Iy is the identity matrix of size N x N.
2 Problem statement
2.1 Determinantal point processes
In this section, we introduce some definitions and properties about DPPs (see Kulesza & Taskar (2012) for more detailed introduction). We will consider DPPs only the finite ground set X. A DPP on X is random variable X with values in the set 2 of all subsets of X, such that
(
P(X 2 A) d
(1)
The above definition requires matrix K E N called the marginal kernel of the DPP whose components are indexed by the elements of X. Then, K^ [Kajkaea keja is the principal submatrix of K with indices in the set A. For simplicity, we assume in this paper that K is symmetric as well as satisfying a necessary condition for its validity: 0 = K <I IN.
From this definition, one can see that the diagonal elements of K are Pli E X) Kg the marginal probabilities of inclusion in X for individual elements of X. In addition,
K2s Kay K3,
P(X 2 (i.i))
Pii X)P(j X) -K2
K3,
This proves that the probability of co-occurrence of two elements smaller than in the independent case, especially for large values of Ki,, which corresponds to highly similar items and j. DPPs are hence diversifying in the sense that they tend not to select similar items.
3

---

Published in Transactions on Machine Learning Research (03/2026)
Manipulating inclusion probabilities in [1] is more complicated than manipulating the joint probability distribution. Whenever all eigenvalues of K are strictly smaller than 1, another slightly less general definition can be given. For a fixed symmetric positive semi-definite matrix L E RNXN, we call L-ensemble random variable X with values in 2x such that
det(LA) det(L. + IN)
(VA C X) P(X - A)
(2)
where the denominator is the normalizing factor to ensure unit mass of the probability distribution. It is known that an L-ensemble is DPP and its marginal kernel is
K = L + IN) = -
A DPP with marginal kernel K is an L-ensemble only if I is invertible. In this case, L K ( K) A thorough detailed description of the set of all DPPs has been discussed in Tremblay et al. 20233 another representation corresponding to the set of all DPPs has been introduced and called extended T--ensmblees. In particular, it has been proved that the limits of some L-ensembles are no more L-ensembles, but extended L-ensembles or DPPs. More precisely, extended L-ensembles can represent DPPs which have a strictly positive number of elements with probability one (or equivalently, the probability of the emptyset is zero). This in contrast with T-ensembles for which the emptyset having zero probability only a limit case. In this paper, we tackle the problem of parameter estimation based on the L-ensemble description, which is more natural for expressing probabilities and formulating the maximum likelihood problem. However, the mentionned fact about cardinality of L-ensembles guided us in this work, it will appear in the next section.
2.2 Maximum likelihood (ML) criterion and estimation
Our learning task is to fit DPP kernel L to a collection of observed subsets. Let our training data be Xi,..., Xn S X' which are supposed to be independent and identically distributed and to follow a DPP distribution. We want to estimate a DPP kernel consistent with this dataset. For all X S X, let us define px = P(X X) and its empirical counterpart Px E 1(X, = X) which is the empirical probability of det(Lx,) and the normalizod occurrence of cach set X C X in the training samples. The likelihood I det(I+TTx) negative log-likelihood hence reads:
fL)(L)= = Σ px log det(L (L IN) - log det (Lx)].
(4)
XEX
Note that the above criterion is lower-bounded by zero since it is the negative logarithm of probability between 0 and 1. Whenever it exists, the maximum likelihood estimator given by any minimizer of fML- As a differonce of convex (DC) functions, fML not convex and the corresponding optimization problem was recently proved to be Aar-hard in Grigorescu et al. (2022), as conjectured in Kulesva (2012). Let us first investigate properties of the maximum likelihood estimator, before considering optimization algorithmic issucs.
3 Properties of ML estimator
The matrix defining an L-ensemble is required to be positive semi-definite. However, when it comes to minimizing fuL in { the stronger condition that L is positive definite is often assumed. Also, the existence of a well defined minimizer (i.e., the existence of a maximum likelihood estimator) is often overlooked. We first prove some propertics which apply any finite set of samples, which will provide insight on this question. It will then appear that, in applications, an additional penalization term can be beneficial.
3.1 Non coercive behavior
In order to define a maximum likelihood estimator, the minimum value of the criterion fMr. should be reached. A sufficient condition for this is that the criterion is coercive] We show that unfortunately neither of these
This means that fMn +oo when [[]]| +00.
4

---

Published in Transactions on Machine Learning Research (03/2026)
conditions guaranteed to be satisfied, based on the specific analysis of the case when two elements are in the groundset X.
Proposition 1 Suppose that the groundset contains N = 2 elements. ip = 0, that is if X, o D for all E (I,...,n), n), then, for any given positive definite matrix L,, there erists such that
(L) (L) and | |1||.
This implies that the loglkkegiie
4 non coercive.
The proof in Appendix A relics constructing the matrix L such that all principal minors of L are scaled by factor > 1. As a consequence, the criterion fML does not reach its minimum and no maximum likelihood estimator exists whenever PO = 0. Intuitively, this is in accordance with the fact that, for T-ensembles, the empty set has necessarily strictly positive probability, corresponding to the usual convention det(Lg) = 1. This in contrast with DPPs, which are slightly more general model allowing zero probability for the emplyset. In order to properly define maximum likelihood estimator, the emply should hence be contained in the training data samples.
3.2 Necessary/suuffcient conditions for existence of positive definite minimizer
We now give necessary condition for the criterion fMI in 4 to have positive definite minimizer, in the general case of any size N of the groundset X' and of the matrix L. The proof in Appendix B relies simple algebra on determinants.
Proposition posilive deforile misémiiee of the neg-loglikelihood 4 can only exist if the following two conditions are satisfied:
U
(ii)
X; = 0.
1=1
Equivalently, a positive definite minimizer of can erist only if, for all elements in E X, the following two condilions are sulisfied:
(1) (3X in X and px 0 ( (3X in & X and px > 0.
Note that in Kawashima Hino (2023). it has been observed that condition (i) above is necessary for avoiding convergence issues of the algorithm minimizing fML. From the above statement, it is now clear that this phenomenon happens for fundamental reasons and not for numerical ones. Below is sufficient condition for SMI. to be coercive, which is proved in Appendix C
Proposition 3 If po > 0, then the negative log- likelikeld fML in is coercive.
3.3 Particular case with explicit minimization
We now consider the particular case when only n = sample X, available in the training set. In this simple situation, which has been considered another context in Barthelmé et al. (2019), the minimum value of fML can be explicitly characterized. This will help both understanding the properties of fML and its minima and, later, the behavior of optimization algorithms. Note that the conditions of Proposition 2 are not fulfilled and, as expected, we will show that maximum likelihood estimator does not exist.
The maximum likelihood criterion can be written in terms of the eigendecomposition L = VAVT where V is orthogonal (VVT= = VTV = Iv) and A = Diag ((A)) Since det(VAVT + I) = det(A + I), Equation [ can reexpressed as
faa(L) log (e + Iw)
px log det XCX
Σ
(5)
For n 1, a unique term with px, appears above and minimization with respect can be performed explicitly (see Appendix D.

---

Published in Transactions on Machine Learning Research (03/2026)
Proposition 4 If single sample X1 of cardinality -= [Xx] is available, the negotive loglikelihood fML is non coercive. The infomam of JM. is zero and it is opproached by matrices I. of rank r and such that the principal submatrir Lx, reads Lx, = V Diag (Aff)==HISIEN)) VT, where V is any orthogonal matrix and all eigenvalues NN+) go to infinity.
One can note that the infimmum can be approached in a non unique way since there are many possible choices for the matrix V. However, it is in particular reached for V being identity and hence for diagonal matrices L A. Intuitively, it scems natural that from a unique sample, one cannot infer about repulsion between different elements and hence one cannot distinguish a diagonal DPP (in fact, Bernoulli process) from non diagonal one.
4 Regularized criterion and minimization algorithm
A practical consequence of the above results is that the maximum likelihood estimator is likely not to exist in the class of L-ensembles when the empty set does not appear in the training data set. A possible solution to circumvent the problem, is to add a term P(L) called penalization or regularization term. Preferably, the regularization term should promote some prior information on the matrix to be estimated. Possible choices for PL) classically include the & norm || = Enj=1 Layle which promotes sparse L or the nuclear
norm | >m' X which promotes low-rank L. In Gartrell al. 2017 2018), the regularization is imposed on the columns of a low-rank decomposition and has been justified to avoid large parameter values and overfitting. More precisely, taking a singular value decomposition T. = VAVT, it reads P(T.) Ee F AVV.1. = -E A H where ti -Exxxxxxxxx Px is the empirical probability of occurrence of element i. This regularization criterion can be seen as weighted l norm on the vector of eigenvalues, also sometimes called weighted nuclear norm deg + IN) will be considered and interpreted in Section
2 (see Gu et al. (2016)). Alternatively a regularization term Importantly, the existence of a minimizer is guaranteed if the chosen term P(L.) is coercive, which is the case for the three previous examples. For minimizing the resulting criterion, we propose to use Forward-BBacwarrd algorithm (FB) which is well- known and widely used in proximal optimization, with broad range of applications in inverse problems and machine learning [Combettes & Pesquet 2021; Sra et al.) 2012). It is suited for minimizing functions which can be split as the sum of two terms, one of them being differentiable and the other convex:
= g
(6)
It consists in generating a sequence (L)) by alternating a gradient step and a proximal step as described below in Alg. When the first function non convex, the following theorem, which is an immediate
Alg. 1 FB algorithm Initialization: Ln E S.N
for k = 0, 1.... do
Lx+1 = , (Lx - 7t (g())) end for
with 7 E (0, 2)
outcome of Chouzenoux et al. (2014), provides convergence guarantees of FB algorithm. Comments on this theorem given below.
Thcorem Suppose that the function to be minimized Lojasiewicz inequality (KL) and can be splil as in (6). Assume also that g is differentiable function with an a a-Lipschitzian gradient (a > 0) and h is a proper lower semi- continuous conver function. Then, the sequence (Lx) generated by Alg. converges to a critical point of f-
SN + (-x0+ satisfies the Kurdyka-
The splitting as in 6 will be detailed next, but note first that there are no convexity assumption and the theorem applies in our case. For convergence guarantees of FB the nonconvex case, see also Attouch et al.
IIt. incorrectly called norm, since generally non convex because the eigenvalues depend nonlinearly on Considering such term is far of the scope of the paper.

---

Published in Transactions on Machine Learning Research (03/2026)
2011 Attouch & Bolte (2007 The result states convergence to critical point only and one may expect more powerful guarantees. However, to the best of our knowledge, there exists no result in the literature proving the convergence of proximal methods to a global minimizer when applied to nonconvex criteria. Finally, note that assuming that f safistics (KL) is a very weak requirement which is here satisfied. Indeod, by considering an o-minimal structure which contains log, exp, and all semi-algebraii functions, one can prove that the regularization functions of interest satisfy (KL) (Bolte et al. 2007).
In Theorem 1 the function f is defined over the Hilbert space S.. The original maximum likelihood problem positive semi-definite matrices. As already mentioned, to deal with this constraint, we will consider that the minimization problem is over the set of positive definite matrices. Therefore, we choose to add an indicator function that guarantees to stay in S Given > 0 (small and close to zero), we define the closed convex set S.N = {L E EN L = eIN} and its indicator function AN SN - (-oc, tool, given by
however requires minimization
0 IL (that is, if 2 cIx) too otherwise.
ESN (T.)
Finally, given constants μ 2 0, 2 0, and e 0, our algorithm will minimize the function:
(L) = fLL + μ log det + IN) + (P(L) + 1sx (L) (L)
(7)
= + nd) log (L IN)- ) Σ XCX
px del + uP(L) (L),
Our algorithm applics for any function PLL) such that its proximity operator known; more generally P(L) could be sum of functions with known proximity operator. Although our algorithm can handle the gemeral
case, will consider for purpose only one penalization term: either the & norm (v > 0, P(L) = ||/|
and μ = 0), or the nuclear norm (v > 0, P(L) |[]] and μ 0), or log (et(L++ IN) penalization (μ > 0 and V = 0, P(L) = 0). The latter case will be also discussed in Section using another algorithm.
In the following sections, we describe how it is possible to split the function fAL and the above fpoee guided by the fact that in Equation ( the differentiable part may concave, whereas the part making use of the proximity operator convex. We successively consider the concave and differentiable part of the criterion g and then the convex part h.
4.1 Splitting the objective function: concave part and gradient
For splitting the criterion as in 16, we first choose define the function g : SN + (oo) as
(L)) (1+ + n)) log det (L + IN) if L 0
(8)
+00
otherwisc.
To apply the FB algorithm, the gradient of g is needed. Moreover, its Lipschitz constant a is necessary for choosing step-sizes (Yk)eN that ensure convergence (y E (0, 2)). We have the following result, which is proved in Appendix
Proposition 5 The function g is differentiable in SN with
(VI (VLE
Vo(L) = (1 +1) In)-
In addition, the gradient of g is (1 + p) Lipschitzian s.y
4.2 Splitting the objective function: convex part and proximity operator
According the above choice for g, the function g in the decomposition of fpeee = g + h reads
h(L) = Σ
px log det( + vp((L) + + (L).
(9)
xeX

---

Published in Transactions on Machine Learning Research (03/2026)
In Algorithm 1 evaluation of the proximity operator of h is required for y 0 and L SN, whose definition
is
(M(N)) + 1L M
1 27
prox (L) arg min MESa
(10)
Due to the indicator function in h, since e > 0, the proximity operator of necessarily returns a positive definite matrix. This ensures
(Vy > 0) (AL E S*) prox, >
and the iterates (I=)220 defined in Alg. 1 are hence guaranteed to be positive definite. Writing the optimality conditions for the problem in Equation 110 yields an equation seemingly impossible to solve analytically, We propose in the next section compute the proximity operator numerically by an inner optimization procedure. Note that, fortunately, results in Chouzenoux et al. (2014) are stronger than Theorem and the convergence to critical point also holds for inexact FB algorithm, when using approximation to the proximity operator.
4.3 Evaluating prox: dual bookkcoooddinte -wrkwd
Rewriting prox computation We now propose algorithm to compute numerically the proximity operator h. Multiplying by y, can rewrite the minimization (10 depending on the chosen regularization. If P(L) = -|I,I,, it reads:
min.
(152 (M)
Σ XCX
vdx (- dex MUX)) + (MUx)
M + MIF
(11)
MEBN
ba+1(1f)
and if P(L) Il.), it reads:
((ze) + ts (L)) + MESN
min.
Σ XEX
(12)
Σ hy(US
In both cases, the criterion takes the same form in (Abboud el al. 2017 Eq. (25)), where the linear TiyTMU MUG. The Dual Block Coordinate Norward-Backwarr (DBCFB) algorithm proposed in this paper leverages this structure and provides an efficient algorithm for minimizing such a function, so computing the proximity operator of a sum of convex functions involving linear operators. The main ingredient required for implementing DBCFB the proximity operator of each of the above involved functions.
operators inside each function hy is given by M + U2
Proximity operators of the involved terms The proximity operators of ts,, log det, ||-I|ı and II-IIme are precisely known and recalled in Appendix F In the second equation above, the sum of the nuclear norm and the indicator has been considered simultaneously as single term to avoid unnecessary computations, since the prox of this sum known. Note that additional terms can be added under the condition that the proximity operator known. This paves the way to considering many additional constraints penalization that can be added to or to the initial objective function.
Description of the algorithm The DBCFB algorithm is described in Appendix G both in the cases of Equations 11] and (12 (see Scctions G.1 and G.2 respectively). Each itcration cycle consists in taking the proximity operator of the first. function which involves isN, taking the proximity operator of one of the functions h, and performing linear combinations. From the proximity operator involving the indicator functions, which projects onto S.N. the iterates always remain definite positive. In addition, when using the DBCFB algorithm, we systematically used a warm-restart initialize the variables at the value obtained the previous outer iteration during prox computation.
8

---

Published in Transactions on Machine Learning Research (03/2026)
4.4
Complexity and alternative dual block coordinate forward-backwart backward
The complexity of our algorithm is O(N3). Indeed, in the previously described DBCFB algorithm, computing the proximity operator of the terms AS or (rr/ll-llmue + +2g requires diagonalizing the matrix, which costs
O(N)). Our complexity is hence similar to other existing algorithms (Mariet & Sra 2015 Kawashima &
Hino 2023 Gillenwater et al. 2014) but it remains challenge for all existing methods. We shortly discuss
below potential directions for improving the computational efficiency.
First, the computationally intensive projection can be activated less frequently. Indeed, another possibility consists in incorporating the latter functions in the sum of the functions h2 in Equations (11) 12 (or equiv- alently in (Abboud al.
2017 Eq. (25))). This precisely what has been done for obtaining the algorithm given in [Abboud et al. 2017 Eq. (37)). This allows us to do smaller number of projections onto S and thus reduce the computational complexity. This algorithm converges to the sought proximity operator, mentioned in Abboud ct al. (2017). Note also that according to the latter work, more sophisticated strategies are allowed in order to activate the most computation demanding proximity operators less frequently, e.g. using quasi-cyclic rules. Other empirical strategies could be developed, such as fine-tuning the inner-loop for approximate convergence. Another option would be to exploit the full possibilities offered by a variable metric in the FB algorithm as in Chouzenoux et al. (2014). To address large N sccnarios, a rescarch direction would be to resort to proximal interior point methods (Chouzenoux et al., 2020). Alternatively, stochastic gradient based approaches have been proposed (Osogami et al. 2018). Note finally that for DPPs with very large N but samples with much smaller cardinality, using low-rank factorization of L could be beneficial at the cost of loosing the global structure of the optimization problem.
5 Minimization with log det penalization
We now focus on the particular case when 0 in Equation 7 that is the penalization P(L.) is dropped. The FB algorithm described in the previous section remains valid. If we further drop the indicator function As,, we obtain the criterion
fu(Z) - +1+ log
Σ px log det( XCX
(13)
where y O is a regularization parameter. Up a scaling of the objective function by 1 + ,r, adding the y log det(L + IN) regularization term amounts to modifying the empirical probability and replace each px by px + μt), whereas the probability of 0 is set to the value /=(1 + p)) instead of zero. To minimize fur particularly efficient algorithms can be considered as in Mariet & Sra (2055): Kawashima & Hino 2023). The
latter algorithms have been designed and used with l O, although according to Section I the maximum likelihood estimator is likely not to exist in the class of L-ensembles when the empty set does not appear in the training data set. In practice, the iterations are usually stopped when the progress of the objective function falls below a given tolerance, overlooking the difficulty inherent to the objective function.
Pixed-point algorithm For minimization of fus we make a few comments about the algorithm in Mariet & Sra 2015 which is referred to as the "fixed-poins algorithm', its iterations being given by
(Ak E N) L La 7 V (Lx)
(14)
The above iterations were introduced by considering fixed-point equation after changing the optimization variable and working with L- Importantly, in doing so, it can be guaranteed that the successive iterates of the algorithm remain positive definite, provided that the initial point Lo is positive definite. The iterations were also interpreted as an MM (Majorization- Minimization) procodure. We further show in Appendix H that the iteration [14 can be interpreted as a variable metric preconditioned gradient descent algorithm. This metric is actually also called affine invariant metric and considering it amounts to endowing the set of positive definite matrices with a Riemannian structure (Boumal, 2023). As an important remark, from Equation [4] and the expression of the gradient in Appendix H it can be seen that if the initial Lo is diagonal, then all (T& ken are diagonal in the sequence provided by the fixed-point algorithm. In this case,
9

---

Published in Transactions on Machine Learning Research (03/2026)
the algorithm converges to stationary point of the criterion which is diagonal DPP kernel, that is only Bernoulli process is identified, which models no repulsion between points, contrary to sought DPP in general.
Gradient with low-rank factorization Another algorithm for minimizing fu has been proposed in Gartrell et al. (2017) and consists of gradient iterations combined with a low-rank factorization of the kernel matrix L We have also used this algorithm in our simulations.
6 Simulations
We provide some simulations to confirm the properties stated in Section 3. and to illustrate the effectiveness and limitations of the different algorithms for minimizing the considered criteria. More precisely, we consid- ered the fixed-point algorithm in Mariet & Sra (2015), the low-rank algorithm from Gartrell et al. (2017) and our FB algorithm as described Section 4 We have also tested the algorithm in Kawashima & Hino (2023) and it systematically converged with incrcasod convergence speed to the same result as the fixed-point algo- rithm. We hence only reported about the latter, since convergence speed of the algorithms not the main topic addressed in this paper. Keeping in mind the objective of estimating DPP probability law, we con- sidered the total variation (TV) distance between any two probability distributions over subsets of X::
(px)
(1)
PP
XCX
xcx
d(p
(1)
P2) 2
Σ X
Px (
xx
(15)
In the above definition, hence also defines a distance to an L-ensemble.
(xx
(1)
(2) Px
can also be given by a matrix according to (2 and it
xex
XCX
Non coercivity For N = 2, generated probability law on the subsets of X = (1,2) by drawing randomly P(1)-((2) ((12) > 0 that sum up to one and hence Pu = 0. To minimize fu in [13 we ran the fixed-point and low-rank algorithms for the values μ = 0, = 0.01, and μJ 0.05. The criterion value f (Tx), the norm of the iterate | |r and the distance to the true law are plotted on Figure [ as function of the iteration number k. The criterion value indeed converges in all cases. However, for 0, the norm of the
Fixed point algorithm with different regulanization parameter
Low-rnn algorithm
with different regulari zation perameter
Cricetton
p
Dist, true DPP NormL) Cricerton
p--
3.0
3.5
p=0.01
Dist, trun DPP Normil)
400
102
201
230
428
62
1000
20-1
Algorithi iterations
Algorithm Iterations
Figure 1: Non-coerciveness of the maximum likelihood criterion for N = 2: criterion and distance to true DPP decrease, whereas norm of the iterates increase.
iterates go to infinity, while the distance to the true law to be estimated always decreases. This observation confirms Proposition [ More generally, we observed experimentally the ilerates going to infinity, as soon as Pv = O. In our simulations, the parameter has been manually tuned. To provide a guideline, Figure 2 shows for two randomly drawn DPPs with ground set of cardinality N -=3 and
the distance to the
true DPP as a function of μ. It seems that an approximately correct value of p is p (1 10--p Pp), corresponding
to Pa = #/(1 μ4) as discussed in Section
10

---

Published in Transactions on Machine Learning Research (03/2026)
Ground set of cardinaliyy N=3
Ground set of cardinality N=
p=
Pa
On set to zero samples
6.22
n=100 samples
Dist: true DPP
Diot. true DPe
Polll -Pal
0.18
0.25
0.55
Pa set to zero n-200 samples
n=100 samples
3.0
3.55
0.33
0.15
0.20
0.25
0.30
0:35
0.30
0.55
6.5
6.15
0.50
0.25
0.0
025
Figure 2: Distance to true DPP as function of μ on two examples. The estimated kernel matrix given by the fixed point algorithm minimization of fu- Solid line: artificially set Pa = 0 and renormalizing other probabilities. Dashed line: empirical estimation with 200 samples. Dashed-dot line: empirical estimation with 100 samples. Vertical dots indicates Pa/(1 (1- Pa).
As yet another illustrative example, we reproduced the simulations on the Amazon Baby Registry datasel, as considered in Mariet & Sra (2015) but for many more iterations. We systematically observed that the critcrion value converges, whereas the norm of the itcrates goes to infinity, as shown on Figure for two calegories. The experimental results in this section hence motivate the necessity to add regularization term in implementations.
Amazon baby registry set: Category Likelhood citterion: (1))
Amazon baby registry Category likelhood crberion: (l)))))
20
1066
2002
2000
8003
500e
25.6
1003
7566
10000
12500
1260
2000
heeates: Il.b
Berates: Mall
25
53
50
1006
2002
8200
12503 1000
23ice 2000 1200 2066
10000
Figure 3: Non-coercivity of the maximum likelihood criterion: the norm of the iterates of the fixed point algorithm on the Amazon Baby Registry dataset diverges, while the criterion value decreases.
Influence of the indicator function Our algorithm requires additional indicator function in fumee compared to Jx- The influence of this indicator and of the choice of is illustrated in Table [ through two examples: denoting L. the final value of the algorithm for given value of we reported the relative difference || / 1o0=lr/ /
where L1o- was considered a reference value. Systematically, we observed that small values of e only slightly perturb the optimization result, which guided our choice e = 10 4 in the following section.
|[ - -10-olle
Table 1: Influence of on the final value of the FB algorithm minimizing fumei for two randomly driven example (N = 10, n = 50 samples), the values of - Lio-> Lio-=|le/||Loo-o1// || are reported.
1.0 10-5
1.0 10-1
1.0 10-3
1.0 10-2
1.0 10-1
11 = 0 # pp/(1 (1 pp) # 2.41 10
2.33 10-1
2.57 10-4
2.60 x 10-3
2.72 x 10-2
4.26 x 10 10-T
2.65 10
2.71 x 10-3
2.81 x 10
4.37 10-1
11

---

Published in Transactions on Machine Learning Research (03/2026)
Behavior of the algorithms with respect to local minima For N 8, based on Proposition we illustrate the difficulty of the classical fixed-point algorithm to deal with local minima. Considering single sample X1 C X we minimized fML with the three considered algorithms by initializing the algorithm randomly. We also initialized the algorithms with the identity matrix. The results are shown on Figure
We observe that, with random initialization, the fixed-point algorithm systemalically converges to local
Reud-point algorithm
Low-rank algorithm [Cartrell al. 2017]
FB algorithm
Randem int Dtagonal
Random
Random
Diagonal
Diagonal Inst.
Cituario
Criveion
Citteron
185
383
209
a2c
20c
493
55
Aiger hhm iterations
Algerithm iterations
Alg Agarithm iterations
Figure 4: With n = 1 sample, for different identical initializations, criterion values of the algorithms depend- ing on iterations. The fixed-point algorithm clearly shows local minima.
minimum and does not approach the global infinuum which is known to be zero. On the contrary, in accordance to the result from Proposition I| and the remark in the previous subsection, the infirumm is approached by the algorithm with a diagonal initialization. In the general case however, such a diagonal initialization should not be used because the algorithm only provides diagonal iterates, which have no reasons to be global minimizers.
We compared the minimization of fy.P.. in 7 with v = 0, c= 10-4 by our FB algorithm and the minimization of fg in (13 by the fixed-point and low-rank algorithms. Both criteria are hence identical up to the indicator in Ju.ue-- With a random positive definite I,, we drew n = 20 samples according to (2), discarding emply sets. For both algorithms, we have set = (det(L + Iv) - 1)-1 which amounts to assigning to Pa its theoretical value. We considered the same training set and the same random initialization points for all algorithms (more precisely a Cholesky factor of the same initial L was used for the low-rank algorithm). Figure 5 illustrates our observation that the FB algorithm appears to be less sensitive to the initialization point. We were not able to identify a best initialization strategy for any algorithm, but running the algorithms with few random initializations appears to slightly improve performance.
Fieedppoitt algorithm
algorittem [Gartrell 2017)
algorithm
Random init. Diagonal ink.
Rardom inll Diagonal nit.
Rundom
6.00
Diagonal intt.
Critarion
1.22
Algoftti Beratiors
Algerithm ka tarationn
Algorkti lterations
Figure 5: With n = 20 sample, for different identical initializations, criterion values of the algorithms depending on iterations. Fixed-point algorithm seems more sensitive to local minima.
Other penalization We drew random positive definite matrix L of size N = 20 and generated 100 and n 300 DPP samples according to this matrix. From the samples, we tried to infer L and performed minimization of f/ in Equation [3] and of fp.ce in Equation 77. In the latter case, we tried both & and nuclear norm penalization and choose e 10-1, We considered the obtained minimizer as estimate f.
12

---

Published in Transactions on Machine Learning Research (03/2026)
of the true L and quantified the distance between them using the TV distance in 15
The results given
Figure 0 for 100 and 300 samples. One can see that using & nuclear norm regularization with an adequate regularization parameter, one is likely to obtain a better estimate.
Number of samples n=100
Number sam pls 30000
regularization
1, regularization
nuclea regulatization logdeti++1 regularization
nucleat regularication
Ingdent, +1] regulrizzaion
Distance to touu DPP
0-44
040
6.5
0.22
0.64
0.66
0.24
0.24
0:36
0.00
0.12
0.14
Regularization parameter
Regularization parameter
Figure 6: Distance to true DPP depending on regularization choice and parameter μ or V.
7 Conclusion
In this paper, we addressed the problem of estimating the parameters of a DPP from set of observed samples. Starting with a maximum likelihood approach, we modeled the samples as realizations of L- ensembles. We highlighted significant theoretical challenges, particularly the potential non-existence of the maximum likelihood estimate due to the non-coercivity the objective function. To overcome this issue, we introduced regularization term and minimized the resulting criterion using proximal algorithms, which offer flexibility in handling various regularization terms. Our simulations demonstrate the advantages of different penalization strategics and the effectivencss of approach. Future work should explore ways to accelerate these proximal algorithms through an adaptive choice of the underlying metric.
References
Feriel Abboud, Emilie Chouzenoux, Jean-Christophe Pesquel, Jean-Hugues Chenot, and Louis Laborelli. Dual block-coordinate forward-backward algorithm with application to deconvolution and deinterlacing of video sequences. J. Math. Imaging Vision, 59(3):415 431, January 2017.
Raja Hafiz Affandi, Emily B. Fox, Ryan P. Adams, and Ben Taskar. Learning the parameters of determinantal point process kernels. CoRR, 2014.
Hedy Attouch and Jérôme Bolte. On the convergence of the proximal algorithm for nonsmooth functions involving analytic features. Mathematical Programming, 116(1-2):5-16, 2007.
Hedy Attouch, Jérôme Bolte, and Benar Fux Svaiter. Convergence of descent methods for semi-algebraic and tame problems: Proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods. Mathematical Programming, 137(112):91-12) 2011.
Yannick Baraud. Estimation of the density of determinantal process. Confluentes Mathematici, 5(1):3-23. -33 2013.
Rémi Bardenct and Michalis Titsias. Inference for determinantal point processes without spectral knowledge. In Neural Information Processing Systems (NIPS), December 2015.
Simon Barthelmé, Pierre-Olivier Amblard, and Nicolas Tremblay. Asymptotic equivalence of fixed-size and varying-size determinantal point processes. Bernoulli, 25(4B):3555 -3455555555,,,,, 2019.
Heinz H. Bauschke and Patrick L. Combettes. Conver Analysis and Monotone Operator Theory in Hilbert
Spaces. Vering GmbH, 2017.
13

---

Published in Transactions on Machine Learning Research (03/2026)
Christophe Ange Napoléon Biscio and Frédéric Lavancier. Contrast estimation for parametric stationary determinantal point processes. Scandinavian Journal of Stolistics, 44(1):204-22) 2017.
Christopher M. Bishop. Pattern Recognétion and Machine Learning. Springer- Ppringer-Verlag New York Inc., 2006.
Jérôme Bolte, Aris Danillidis, Adrian Lewis, and Masahiro Shiota. Clarke subgradients of stratifiable functions. SIAM Journal on Optimization, 18(2):556-55) 572, 2007. doi: 10.1137/060670000. URL
https://doi.org wt.///..////.. 1177006600000
Alexei Borodin. Determinantal point processes. In The Oxford Handbook of Random Matriz Theory. Oxford University Press, 2015.
Nicolas Boumal. An Introduction to Optimization Smooth Manifolds. Cambridge University Press, 2023.
Vietor-Emmanuel Brunel and John Urschel. Recovering a magnitude-symmetricc matrix from its principal minors. CoRR, 2024.
Victor-Emmanuel Brunel, Ankur Moitra, Philippe Rigollet, and John Urschel. Maximum likelihood estima- tion of determinantal point processes. CoRR, 2017.
David R. Burt, Carl Edward Rasmussen,, and Mark van der Wilk. Convergence of sparse variational inference in gaussian processes regression. Journal of Machine Learning Research, 21(11)): 63, 2020.
Emilic Chouzenoux, Mean-Christophe Pesquet, and Audrey Repetti. Variable metric forward-backwar algo- rithm for minimizing the sum of differentiable function and a convex function. Journal of Oplimization Theory and Applications, 162(():107-133) 2014.
Emilie Chouzenoux, Marie-Caroline Corbineau, and Jean-Christophe Pesquet. A proximal interior point algorithm with applications to image processing. Journal of Mathematical Imaging and Vision, 62:919- 940, July 2020.
Patrick L. Combettes and Jean- Christhhit Pesquet. Fixed point strategies in data science. IEEE Transac- tions Signal Processing, 69:3878-385 3905, 2021.
Michal Dereziíski, Manfred K. Warmuth, and Daniel Hsu. Unbiased estimators for random design regression. Journal of Machine Learning Research, 23(167): 2022.
Christophe Dupuy and Francis Bach. Learning determinantal point processes in sublinear time. CoRR, 2016.
Michaël Fanuel and Rémi Bardenet. Nonparametric estimation of continuous DPPs with kernel methods. In Advances in Newral Information Processing Systems (NeurIPS), volume 34, pp. 24124 24136, 2021.
Mike Gartrell, Urrchh Paquet, and Noam Kocnigstcin. Low-rank factorization of determinantal point pro- cesses. In AAAI, 2017.
Mike Gartrell, Elvis Dohmatob, and Jon Alberdi. Deep determinantal point processes. CoRR, 2018.
Mike Gartrell, Victor Emmtanel Brunel, Elvis Dohmatob, and Syrine Krichene. Learning nonsymmetric de- terminantal point processes. In Advances in Neural Information Processing Systems (NeurIPS), volume 32, 2019.
Jennifer Gillenwater, Alex Kulesza, Emily Fox, and Ben Taskar. Expectation maximization Expertationmaxxiniattonn for learning determinantal point processes. CoRR, 2014.
Elena Grigorescu, Brendan Juba, Karl Wimmer, and Ning Xie. Hardness of maximum likelihood learning of DPPs. In Proceedings of Thirty Fifth Conference on Learning Theory, volume 178, pp. 3800-3819, July 2022.
Shuhang Gu, Qi Xie, Deyu Meng, Wangmeng Zuo, Xiangehu Feng, and Lei Zhang. Weighted nuclear norm minimization and its applications to low level vision. International Journal of Computer Vision, 121(2): 183 20-2 2016.
14

---

Published in Transactions on Machine Learning Research (03/2026)
Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The Elements of Statistical Learning: Dato. Mining, Inference, and Prediction. Springer, 2nd edition, 2009.
J. Ben Hough, Manjunath Krishnapur, Yuval Peres, and Bálint Virág. Zeros of Gaussion Analytic Functions and Determinantal Point Processes, volume 51 of University Lecture Series. AMS, 2009.
Takahiro Kawashima and Hideitsu Hino. finorizationnmaxiiiiatte for learning determinantal point pro- cesses. Transactions on Machine Learning Research, 2023.
Andreas Krause, Ajit Singh, and Carlos Guestrin. Near-optimal sensor placements gaussian processes: Theory, efficient algorithms and empirical studies. Journal of Machine Learning Reseorch, 9(8):335 284, 2008.
Alex Kulesza and Ben Taskar. Learning determinantal point processes. In Proceedings of the 27th Conference Uncertainty in Artificial Intelligence, 2011.
Alex Kulosza and Ben Taskar. Determinantal point processes for machine learning. Foundations and Trends0 in Machine Learning, 5(2-3):123-22) -2-222862 2012.
John A. Kulesza. Learning with determinantal point processes. PhD thesis, Faculties of the University of Pennsylvania, 2012.
Claire Launay, Aguès Desolneux, and Bruno Galerne. Determinantal point processes for image processing, SIAM Journal on Imaging Sciences, 14(1):304-345 -440444,, 2021.
Frédéric Lavancier, Jesper Moller, and Ege Rubak. Determinantal point process models and statistical inference. Journal of the Royal Stalistionl Sociely: Series B, 77(4):853 877, 2015.
Hui Lin and Jeff Bilmes. Learning mixtures of submodular shells with application to document summa- rization. In Proceedings of the Sovetty-ighhte Conference Uncertainty in Artificial Intelligence, pp. 2012.
Odile Macchi. The coincidence approach to stochastic point processes. Advances in Applied Probability, 7 (1):83-122, 1975.
Zelda Marict and Suvrit Sra. Fixed-point algorithms for learning doterminantal point processes. CoRR, 2015.
Zelda Mariel and Suvrit Sra. Kronecker determinantal point processes. In D. D. Lee, M. Sugiyama, U. V. Luxburg, 1. Guyon, and R. Garnett (eds.), Advances in Neural Information Processing Systems (NIPS), pp. 2694 2702. 2016.
Naoto Miyoshi and Tomoyuki Shirai. A cellular network model with ginibre configured base stations. Ad- vances in Applied Probabilily, 46(3):832 845, 2014.
Takayuki Osogami, Rudy Raymond, Akshay Goel, Tomoyuki Shirai, and Takanori Machara. Dynamic determinantal point processes. In AAAI Conference on Artificial Intelligence, 2018.
A Soshnikov. Determinantal random point fields. Russsian Mathematical Surveys, 55(5):923 975, 2000.
Suvrit Sra, Sebastian Nowozin, and Stephen J. Wright (eds.). Oplimization for Machine Learning. MIT Press, 2012.
Giovanni Luca Torrisi and Emilio Leonardi. Large deviations of the interference in the Ginibre network model. Stochastic Systems, 4(1):173-200 205, 2014.
Nicolas Tremblay, Simon Barthelme, and Pierre- Olivier Amblard. Determinantal point processes for coresets. Journal of Machine Learning Research, November 2019.
15

---

Published in Transactions on Machine Learning Research (03/2026)
Nicolas Tremblay, Simon Barthelmé, Konstantin Usevich, and Pierre- Olivier Amblard. Extended L- ensembles: a new representation for determinantal point processes. The Arnals of Applied Probabilily, 33 (1)mll, 2023.
John Urschel, -omoonnem Brunel, Ankur Moitra, and Philippe Rigollet. Learning determinantal point processes with moments and eycles. CoRR, 2017.
Cheng Zhang, Hedvig Kjellstrom, and Stephan Mandt. Determinantal point processes for mini-batch diver- sification. CoRR, 2017.
Tao Zhou, Zoltán Kuscsik, Jian-Guo Liu, Matús Medo, Joseph Rushton Wakeling, and Yi-Cheng Zhang, Solving the apparent diversity-accurace dilemma recommender systems. Proceedings of the National Academy of Sciences, 107(11):4511-511, 2010.
A Proof of Proposition
x 2)
Let us write the x 2 matrix L
==
0, y and |2| vzy. Dropping the term X 0 for with
y
which = 0, criterion
4
reads:
(L) log(1 + xy-ry--- =²)
111 log(x)
612) log(u) (11 r
log(zy =3)
- log(1
+
1
+
- ry 2
(12) log(1
+
zy
y
y
x
1
+ P(1.2) log(1 (1
+
+
22 xy
xy xy 2
2
For a: 1, consider 7. [ : det(L) = axz 2²) 0. A simple calculus yields
where ox, ÿ ay and z Vala 1)0y az?.
We have then
1 (t) = log(1 +
xy 22
T
+ xy 22
+ +
+ ((2) log(1
1 + y
+
ay
y
1
+ +(12) log(1
+ xy z2 alzy 22)
+
ry 22
One can then check that (La < (L) and, in addition, || + to0 as a - +00. enough, we hence can choose L as stated in Proposition
With a large
B Proof of Proposition 2
Suppose that there is an element in E X' \ Xi, Equivalently, px = 0 for all X C X' that contain ig. One can see that the right term in [ does not depend on the ig-th row Lin: and column L, that
(L)(L) log det(L= + IN) + terms independent of Ligh/ Li,io
16

---

Published in Transactions on Machine Learning Research (03/2026)
We the linearity of the determinant with respect the du-th row and column, that det(L + 1) is minimum when both the ig-th row and column are zero. With no loss of generality, let us write it for io 1:
L11 +1
L12
LIN
121
L22
+
det(L L + I) det
LN1
LNN +1
Ln
L12
LiN
L12
LIN
L2
L22 +
L22 +
det
+ det
LNi
LnN +
INN +
In
L12
TAN
T.22 +1
L23
L2N
L21
L22 +
La2
L33 +
1
det
+ det
LN1
LNN +1
LN2
LNN +
The above right term does not depend on the first row/column, whereas the determinant on the left is nonnegative and vanishes when the first row now/column zero. Having zero column and row yiclds non definite positive matrix. Condition (i) in the above proposition is hence necessary for positive definite minimizer.
Condition (ii) is obtained by considering the complement L-ensemble, the kernel of which is given by L-!
C Proof of Proposition 3
Remind that by convention, the determinant of an empty matrix Lgg(Lg) is one (scc e.g., Kulesza & Taskar (2012)). Now, all the terms in the sum Equation (4) are nonnegative since the brackets are the negative logarithm of a probability. Therefore, keeping only the term with X = yields
fL 2 Po log det(L + IN) Po Σ log(1 l X().
Under the assumption Po > 0, the term on the right hand-side goes to infinity as || + co.
Proof of Proposition
Remind that fLL(L) =
log det(A + det (Lx,) = log det(A + I) - log det (Vx,, 7).
Using the
Cauchy-Binct formula, we obtain:
N
AV. ) Σ
dee()s))))de((AAss)) $
Σ
det(Vxn.sh
II
Scx,1s|=r
SCX,1S|=r
N=N-rtH
det(Vxx, T)=1
X
In addition, equality the above apper-bound is obtained by choosing the matrix Vx block-wise as Vx = o V]. where RrxN-r has only zero entrics and V Rexx orthogonal, i.c., VVT I,.. As a consequence, taking Vx..: as defined above, the following bound for faL is obtained:
N
N
fML(L) 2
Σ lo + x4)
Σ
log(A = Σ
log(1 + x4 +
Σ -+1
log(1 +
i=N r+1
17

---

Published in Transactions on Machine Learning Research (03/2026)
The above lower bound is reached for matrix L of the form given in the proposition and it can be seen that the infimum of the lower bound can only be approached with X = 0 for i E {I,..., N r) and X > + for E {N - + 1r..,.., This concludes the proof.
E Proof of Proposition 5
The derivation of the gradient follows from classical calculations. For convenience, us consider the function T.gg. g. Denoting by |-l|p the Frobenius norm and by I1-llo the spectral norm, we have for L, R s.
1
I+ (D( Vo(R)]I +I - (R (R+IN) II)
( In) - (N++
||( + + (R IN) |F
I II(L + IN) || Rlll I1 IN) 1lop
||n|llp || Rl|r |Ix|lop
| R||r-
This completes the proof.
F Proximity operators
We recall some known proximity operators. A useful reference is for example Bauschke & Combettes 2017 Let g be positive integer and consider real-valued symmetric matrices of size q. Define the operator forming a diagonal matrix Diag(.) and, for any real-valued symmetric matrix A E 84, write its diagonalized form
A [DDig(A)){=))P1
(16)
where the (Ax)k=1 are its cigenvalues and P E Rox9 is orthogonal.
Property Let h So + (-o0, tool given by
log
M olherwise
h(M)= =
t00
Write A E @d as in Equation 16
Then, for any > 0,
prox n (A) = p Diag da + v A2 +
447 k=11
PT.
Property Let A E St and write it in Equation 16 Then,
prox, (A) = Diag (max (A), PT. ())
Note that for any 7 > 0, scaling the indicator function by > 0 has consequence (1Sy Pgyy) and hence prox, SN (A) = prox, (A).
Property Let A E 8y and write it as in Equation g1 + (-oo, too] defined by + v I.lluuc + ssy (I.) (where v > 0) is given by:
16
Then, the pronimily operator of the function
prox (vll (A) (A) = Diag (max (A) - v, v,e)) PT
18

---

Published in Transactions on Machine Learning Research (03/2026)
G Details on the DBCFB algorithms
We give more details on the DRCFB algorihms allowing to compute the proximity operator in (10) Tn each case, it is guaranteed that the corresponding sequence (E+)aen converges to prox,A (L). In the following subsections, also denole N₂ the number of columns of each matrix (Uz)}=1 that appears in [1
12
G.1 DBCFB, case of Equation 11
The algorithm described here corresponds to (Abboud et al. 2017 Eq. (34a)-)34b), when applied for the minimization problem [1]. The function Asy in this paper corresponds the function. f in (Abboud al. 2017 Eq. (25)) and there are J lerms involving the functions hy. We choose a particular case to sweep and activate sequentially the proximity operators of the functions (hz) J+1 The algorithm is given Algorithm 2 below with the notation of this paper. For consistency, we also have N N and U = IN.
Alg. 2 Dual block-coordinate FB, version
Initialization: Y3 1515J+1
E S N; and Zo = - E/
for k = 0, L.... do
E = prox, NN (L + Zn)
is = k mod (J+1)
C E (c, 2 - c)
+ ck Ujr TR
yJ k+1 Gic
Ck prox / Mic (1
Ye Y2 (Vj + jkb
ZK+1 Zu Un (Y:t
Y2²1) Uju
end for
G.2 DBCFB, case of Equation 112)
The algorithm described here corresponds to (Abboud et al. 2017 Eq. (34b)-(34b),, when applied for the minimization problem 12 The function " + AsN in this paper corresponds to the function f Abboud et al., 2017 Eq. (25)) and there are terms involving the functions hy. We choose as a particular case to sweep and activate sequentially the proximily operators of the functions (hy) The procedure is given in Algorithm
3 below with the notation of this paper.
Alg. 3 Dual block-coordinate FB, version
Initialization: (x))
(xd)
E E N, and Zo = Eje U,
1815J
for k 0, 1... do
Eg prox -llllll
(L Zz)
je = k mod
Cs E (c, 2 c)
f 1/ + Ck UÍ TEgUie
1 = yiv Ck prox nok مرhي 1i
V2 Y/ (Vj + j&)
Ze+1 Zz U3 (Y - -Ysl Usa
end for
19

---

Published in Transactions on Machine Learning Research (03/2026)
H Comments on the lixedppoint algorithm of Mariet & Sra (0015)
The fixed point algorithm in Marict & Sra 2015 can be used for minimizing
fu(D) (1 11) log det + IN)
Σ xex
px log det Lx.
In the original paper, the additional penalization term 4 loog dct(L IN) did not appear, but the adaptation is immediate as shown below. Decomposing Lx as Ux LUx, we can also wrile
(a(T) = (1 + (4) log ( + In) - Σ
Px log dUx LUx)
XEx
and the gradient reads
= (L+)++=++ Σ ExxxxUU D
LUx)
XEX
Now, given step-size y > 0 the iterations of the fixed-point algorithı are given by
(vk E N)
LE+1 = La - L S Lx
(17)
2015 when μ 0, it is guaranteed that the above itcration 17 yields a descent algorithm when 7 = 1. Note that by scaling the objective function and considering I+a JN instead, one can obtain that the algorithm is a descent algorithm when ? = I+#"
According to Marict & Sra
The above iterations in 17 can be interpreted as a variable metric preconditioned gradient descent algorithm. If a symmetric positive definite matrix and we define the linear operator A(N) = A let
(M, A(N)) AM,A-'NA-)) TT(MA-
(18)
This defines an inner product (see Lemma | next in Section H.1 and hence induces a new metric. Let us denote by Af the gradient f with respect to the metric (.. We easily deduce from the gradient definitions that (V.f(L). = (Vf(L),.) and hence we have the relation:
Vaf(L) AVF(L)A
This leads to the corresponding preconditioned gradient descent. iterations:
(Ak N)
La+1
Lx A[)( I AVV((L=A
The iterations in 14 or 17 hence correspond to variable metric preconditioned gradient descent algorithm where, at each step, the metric changed by substituting A for Lt.
H.1 Justification of the inner product (...)A
Lemma 1 For A > 0, let A(N) = A-- and consider (...)A as in 18 Then, (..)) is an inner
product.
Proof:
Clearly, .. is bilinear and symmetric because (M, TI(MA- = - = (N, M)A- In addition, we have:
(M, TT(M(A-MMA-)) = =ve((M) T veo Veoo-eoooA'"""
-vo((M)
(vcc(M) 20
Above, voc(-) the column vector obtained by concatcnating the columns of the matrix and & is the Kronecker matrix product. Finally, since A-1 @ --1 0 for positive definite A we have (M, M) Of and only if M is the zero matrix. This concludes the proof.
20


Reviews:
[{"review_id": "jd4akIzypq", "reviewer": "Reviewer_bWjR", "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": "", "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": "The paper studies the problem of maximum likelihood estimation (MLE) for Determinantal Point Processes (DPPs), where the kernel matrix is learned without parametric assumptions. The authors show that the standard maximum likelihood objective may fail to admit a solution when the coercivity condition is not satisfied. To address this issue, the paper argues that regularization is essential rather than optional in order to make the optimization problem well posed. The authors propose a regularized ML framework and develop a proximal forward–backward algorithm to solve the resulting optimization problem. Empirical results further demonstrate improved stability and estimation quality when regularization is employed.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The paper makes strong theoretical and methodological contributions to the problem of learning Determinantal Point Processes (DPPs):\n\n1. The paper clearly demonstrates failure cases of the maximum likelihood objective for L-ensemble DPPs, in particular the non-coercivity of the objective. It provides both empirical evidence illustrating this non-coercive behavior and theoretical analysis identifying conditions under which coercivity may or may not hold.\n\n2. Motivated by the lack of coercivity, the paper theoretically shows that certain regularization terms guarantee coercivity of the objective. As a result, regularization is shown to be necessary rather than optional for well-posed DPP learning.\n\n3. The authors further propose a proximal forward–backward algorithm to solve the resulting regularized MLE problem and empirically demonstrate improved performance compared to existing methods, including reduced sensitivity to initialization and improved behavior with respect to local minima.", "audience_yn": "Yes", "audience_explanation": "This paper will be of interest to researchers working on problems that can be addressed using Determinantal Point Processes, such as recommendation systems. The proposed approach clearly improves upon previous methods for learning DPPs, while providing strong theoretical guarantees.", "requested_changes": "1. For both the proposed method and existing approaches, computational efficiency remains a primary challenge, as these methods typically have $O(N^3)$ complexity. While this does not weaken the contribution of the paper, it would be valuable if the authors could discuss potential directions for improving the computational efficiency or scalability of the algorithm.\n\n2. In the experimental section, it would be helpful if the authors could include additional experiments or discussion regarding the tuning of hyperparameters $\\mu, \\epsilon, \\nu$, to provide guidance on their practical selection.", "broader_impact_concerns": "No concern.", "additional_comments": "I am not an expert in the DPP literature, and it is possible that I may have missed some important related work that could affect the assessment of this paper’s contribution. I am open to revising my opinion in light of points raised by other reviewers.", "extra_scores": {}, "extra_text": {}}, {"review_id": "faE8QhOdb3", "reviewer": "Reviewer_VE63", "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": "", "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": "The paper studies the problem of the kernel matrix estimation of a determinantal point process from a finite set of samples. Firstly, the paper gives the properties, including the non-coercive behavior, conditions for the existence of the minimizer, and particular cases with explicit minimization. Secondly, the paper provides a forward-backward algorithm for computing the regularized criterion.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The papers contain theorems and propositions with accurate proof.", "audience_yn": "Yes", "audience_explanation": "People who are working on the determinantal processes and recommendation systems may be interested in knowing the findings of this paper.", "requested_changes": "The following are the concerns/questions/requested changes upon this paper:\n1. How to choose the regularization parameter of the regularized criterion?\n2. The authors claim that, as stated in the title, the contributions are the properties and algorithm. However, are these contributions leading to a better solution to the DPP. Since the regularized criterion is already studied in the literature and the proximal algorithm is also a standard approach for solving the regularized optimization problem, the author is suggested to clarify how this paper can push forward the frontier. \n3. In the abstract, the author has the wording \"to address this challenge.\" What is the challenge? \n4. Please add more details or discussions for Theorem 1.\n5. How does the algorithm behave when N is very large?", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "51r5pL8HDG", "reviewer": "Reviewer_2ckL", "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": "", "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": "The paper's core contributions revolve around addressing the numerical instability of Maximum Likelihood (ML) estimation for Determinantal Point Processes (DPPs), which is designed to select subsets that exhibit high volume, i.e., diversity through its determinant. The model is parameterized by a positive semi-definite matrix, often called the kernel matrix $L$, where high off-diagonal values, i.e., high similarity, result in a lower probability of selecting both corresponding items, enforcing the repulsion/diversity property.\n\nThe problem was already shown to be NP-hard by Grigorescu et. al. (2002), but in this paper the authors provide a rigorous theoretical diagnosis for the persistent numerical issues seen in prior work, proving that the standard (unregularized) ML objective function for the $L$-ensemble is non-coercive, i.e., unbounded below, under typical conditions, especially when the empty set is not observed in the data. This non-coercive property is intuitively the reason why algorithms often fail to produce a finite, stable kernel matrix $L$ in this setting. \n\nTo solve this problem of existence and stability, the paper establishes that regularization is necessary to ensure the ML criterion has a well-defined optimum. Their main algorithmic contribution is the development of a robust, provably convergent optimization scheme based on proximal Forward-Backward splitting (specifically, a Dual Block-Coordinate Forward-Backward approach). This new algorithm efficiently minimizes the regularized log-likelihood, giving a stable, finite estimate for the DPP kernel matrix.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The claims presented in the submission appear to be well-substantiated by the evidence provided. The paper successfully argues that the standard maximum likelihood estimator is numerically unstable due to the non-coercive property. Thus, the authors propose a regularization approach and introduce a new algorithm along with convergence guarantees. This approach is then empirically complemented by showing good kernel recovery where previous unregularized methods fail.", "audience_yn": "Yes", "audience_explanation": "Although DPPs are not necessarily a broadly applied tool, the paper seems to handle a meaningful challenge for researchers who work on DPP learning and run into issues of numerical instability of the maximum likelihood estimation for L-ensembles. This work provides a clear theoretical explanation for the issue and introduces a proximal optimization framework that offers a stable alternative. For researchers interested in submodular optimization, kernel methods, and probabilistic modeling, e.g., in tasks like document summarization or recommendation systems, this work seems to offer a useful contribution by addressing a known challenge. The topic is fairly specialized, but the results could be quite relevant for researchers working in this area", "requested_changes": "There are no suggestions for critical changes that immediately comes to mind, but to strengthen the paper, perhaps the authors could discuss the computational trade-offs of their proximal method, comparing its per-iteration cost with that of simpler but unstable fixed-point iteration. It would also be helpful to motivate regularization more clearly and highlight why the non-coercive property is a more immediate, practical barrier to DPP learning than the known barriers for NP-hardness. Finally, adding a sensitivity analysis in the experiments to show how the choice of the regularization parameter $\\lambda$ affects stability, convergence speed, or final kernel accuracy could further strengthen the empirical results, but again, I don't think it's a critical change.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)