CAM Colloquium: John Urschel (MIT) - Learning Determinantal Point Processes with Moments and Cycles

Friday, February 2, 2018 at 3:30pm

Frank H. T. Rhodes Hall, 655

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 in which 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. (Joint work with Victor-Emmanuel Brunel, Ankur Moitra and Philippe Rigollet.)

John Urschel is a doctoral candidate in applied mathematics at MIT, and an adjunct research associate in mathematics at Penn State. His research areas include spectral graph theory, numerical PDE's, matrix algebra, computational finance and mathematical physics. His work with L. Zikatanov regarding the connectedness of nodal decompositions of Fiedler vectors led to the Urschel-Zikatanov Theorem, and he currently has the fastest eigensolver for minimal Laplacian eigenvectors. Recently, he published a paper in SIAM Journal of Numerical Analysis on centroidal Voronoi tessellations.

Event Type

Lecture, Seminar


College of Engineering, Mathematics, Center for Applied Mathematics


engineering, math, center for applied math, cam, College of Engineering, mathematics, center for applied mathematics



John Urschel

Speaker Affiliation

Applied Mathematics, MIT (Doctoral Candidate)


Recent Activity