  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 the $\mathcal 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.
