Learning Determinantal Point Processes with Moments and Cycles
From MaRDI portal
Publication:6283790
arXiv1703.00539MaRDI QIDQ6283790FDOQ6283790
Authors: John C. Urschel, Victor-Emmanuel Brunel, Ankur Moitra, Philippe Rigollet 
Publication date: 1 March 2017
Abstract: Determinantal Point Processes (DPPs) are a family of probabilistic models that have a repulsive behavior, and lend themselves naturally to many tasks in machine learning where returning a diverse set of objects is important. While there are fast algorithms for sampling, marginalization and conditioning, much less is known about learning the parameters of a DPP. Our contribution is twofold: (i) we establish the optimal sample complexity achievable in this problem and show that it is governed by a natural parameter, which we call the emph{cycle sparsity}; (ii) we propose a provably fast combinatorial algorithm that implements the method of moments efficiently and achieves optimal sample complexity. Finally, we give experimental results that confirm our theoretical findings.
Inference from spatial processes (62M30) Point processes (e.g., Poisson, Cox, Hawkes processes) (60G55) Minimax procedures in statistical decision theory (62C20) Paths and cycles (05C38)
This page was built for publication: Learning Determinantal Point Processes with Moments and Cycles
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6283790)
