Learning Determinantal Point Processes in Sublinear Time

While most of these algorithms have polynomial-time complexity, determinantal point processes are too slow in practice for large number N of items to choose a subset from. Simplest algorithms have cubic running-time complexity and do not scale well to more than N 1000. Some progress has been made recently to reach quadratic or linear time complexity in N when imposing low-rank constraints, for both learning and inference [Mariet and Sra, 2016, Gartrell et al., 2016]. This is not enough, in particular for applications in continuous DPPs where the base set is infinite, and for modelling documents as a subset of all possible sentences: the number of sentences, even taken with a bag-of-word assumption, scales exponentially with the vocabulary size. Our goal in this paper is to design a class of DPPs which can be manipulated (for inference and parameter learning) in potentially sublinear time in the number of items N. In order to circumvent even linear-time complexity, we consider a novel class of DPPs which relies on a particular low-rank decomposition of the associated positive definite matrices.