THE CONFERENCE
FOR AUTHORS
FOR PARTICIPANTS

Timezone: »

 
Poster
Learning Determinantal Point Processes with Moments and Cycles
John C Urschel · Ankur Moitra · Philippe Rigollet · Victor-Emmanuel Brunel

Mon Aug 07 01:30 AM -- 05:00 AM (PDT) @ Gallery #62
in Posters Mon »

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.

Author Information

John C Urschel (Massachusetts Institute of Technology)
Ankur Moitra (MIT)
Philippe Rigollet (MIT)
Victor-Emmanuel Brunel (Massachusetts Institute of Technology)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors