Kronecker Determinantal Point Processes
Determinantal Point Processes (DPPs) are probabilistic models over all subsets a ground set of N items. They have recently gained prominence in several applications that rely on "diverse" subsets. However, their applicability to large problems is still limited due to O(N 3 ) complexity of core tasks such as sampling and learning. We enable efficient sampling and learning for DPPs by introducing KRONDPP, a DPP model whose kernel matrix decomposes as a tensor product of multiple smaller kernel matrices. This decomposition immediately enables fast exact sampling. But contrary to what one may expect, leveraging the Kronecker product structure for speeding up DPP learning turns out to be more difficult. We overcome this challenge, and derive batch and stochastic optimization algorithms for efficiently learning the parameters of a KRONDPP.
The authors propose two efficient algorithms (learning and sampling) for determinantal point processes (DPP) in which the DPP-kernel matrix factors as the Kronecker product of smaller positive definite matrices. The first proposed algorithm learns a DPP-kernel which can be factored as the Kronecker product of two positive definite matrices in time quadratic in the number of items. This is an improvement over the existing algorithm [25] for learning a DPP-kernel matrix which runs in time cubic in the number of items -- however, the existing algorithm [25] works without assuming the Kronecker structure of the DPP-kernel. The stochastic version of the algorithm is even faster and requires time O(N^{1.5}), with N denoting the number of items. The second proposed algorithm is for sampling from a DPP with the DPP-kernel having the Kronecker structure. This algorithm runs in time O(N^{1.5}) and represents an improvement over more general DPP-sampling algorithms which do not assume the Kronecker structure of the DPP-kernel and require either cubic time in the number of items or a MCMC sampling with an impractical mixing bound.
The paper can be split into three major components: i) learning algorithm, ii) sampling algorithm, iii) experiments.  i) Learning algorithm: The algorithm works by maximizing the log-likelihood of the model over the space of positive definite matrices which factor as the Kronecker product of smaller positive definite matrices. It represents an extension of the algorithm for learning determinantal point processes proposed in [25] and which does not assume that the DPP-kernel has the Kronecker structure. The authors overcome the issue with the additional constraint on the DPP-kernel by performing the block-coordinate ascent. In Theorem 3.2 they show that the proposed optimization method makes the objective non-decreasing (a similar result was also shown in [25] for the algorithm which does not assume the Kronecker structure of the DPP-kernel). The authors also give guidelines how to generalize the algorithm for DPP-kernels which can be represented with the Kronecker product of more than two matrices. However, for the case of more than two matrices in the Kronecker product the authors do not show the computational gains over [25] and learning without assuming the Kronecker structure (see Theorem 3.3).  @LA1: The maximization of the log-likelihood is non-convex problem and while the proposed version of the block-coordinate ascent is guaranteed to result in non-decreasing objective there is no guarantee that the learned model is a globally optimal one. As this is a non-convex problem and, hence, highly dependent on the initial solution, it would be nice to have a heuristic or guidelines for initializing the solver in Algorithm 1. Has this aspect been tested thoroughly while empirically evaluating Kronecker DPPs? @LA2: It is not clear how constraining is the assumption that the DPP-kernel factors as the Kronecker product of two positive definite matrices (for this case, the authors give an efficient implementation). How does this assumption affect the capacity/properties of such DPP models?  ii) Sampling algorithm: The algorithm exploits the fact that the eigen-decomposition of DPP-kernels which factor as Kronecker products of smaller positive definite matrices can be performed by decomposing the smaller matrices (see Corollary 2.2).  @SA1: The proposed sampling algorithm is the standard DPP-sampling algorithm with an efficient eigen-decomposition which is possible due to the assumed Kronecker structure of the DPP-kernel.   iii) Experiments: The main focus of the experiments is to compare the learning algorithm to [25]. This is achieved via synthetic experiments and experiments on two real-world data sets. In one of the experiments with a real-world data set, the authors confirm that the Kronecker DPPs are less expressive than the DPPs with kernels not assuming such structure. The second experiment with a real world data set, shows a clear reduction in the training time of Algorithm 1 for Kronecker DPPs over [25], designed for standard DPP-learning.  @E1: It is very difficult to distinguish the plots when printed black-and-white. It would be nice if the authors could assign a different marker to each of the plots (e.g., circle, square etc.). @E2: Given the fact that the problem is non-convex it is rather difficult to empirically assess the loss in the expressiveness which comes as a result of the Kronecker structure assumption. However, in my opinion this is an important aspect of the Kronecker DPPs that was not addressed properly by the authors in the experiments.  Minor comments: -- line 40: Y \in \mathcal{Y} is just an element of the set of items and (1) can be misinterpreted (perhaps, to use the power set instead) -- line 43: L_Y is not introduced in the text around (2) -- line 85: bracket missing on Tr_1 -- line 112: notation with the composition of f and the Kronecker product looks suboptimal -- line 133: typo on `Generalization' -- lines 137-141: it would be nice to add more details to the appendix -- line 166: `by from' -- line 200: `true' kernel is not clear enough -- Appendix: Algorithm 3, `end forreturn ...' ------------------------------------------------------------------------------------  The paper is very well organized and extremely easy to follow. All the proofs are clear enough and the compressed parts can be derived easily. It is a solid paper with a very elegant theoretical part. Also, a very interesting observation was given in Section 6, where the authors observe that one of the two parts of the log-likelihood function is geodesically convex over the Riemannian manifold of positive definite matrices and it will be interesting to see how this idea develops in the future.