2017/03/01 by John Urschel, Urschel, John, Victor-Emmanuel Brunel +5
Computer Science · Mathematics · #05C38 #60G55 #62C20 #62M30 #Computational Geometry and Mesh Generation #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Point processes and geometric inequalities #Statistics Theory (math.ST)
paper · pdf · doi:10.48550/arxiv.1703.00539
openalex publication_date 2017/03/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 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.