Conference abstracts

Session B4 - Learning Theory

July 13, 17:00 ~ 17:25 - Room B6

Learning determinantal point processes

Philippe Rigollet

M.I.T   -   rigollet@math.mit.edu

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. In this talk, I will present recent results related to this problem, specifically \begin{itemize} \item[(i)] Rates of convergence for the maximum likelihood estimator: by studying the local and global geometry of the expected log-likelihood function we are able to establish rates of convergence for the MLE and give a complete characterization of the cases where these are parametric. We also give a partial description of the critical points for the expected log-likelihood. \item[(ii)] Optimal rates of convergence for this problem: these are achievable by the method of moments and are governed by a combinatorial parameter, which we call the cycle sparsity. \item[(iii)] Fast combinatorial algorithm to implement the method of moments efficiently. \end{itemize} The necessary background on DPPs will be given in the talk.

Joint work with Victor-Emmanuel Brunel (M.I.T), Ankur Moitra (M.I.T) and John Urschel (M.I.T).

View abstract PDF



FoCM 2017, based on a nodethirtythree design.