Oral
A Polynomial Time MCMC Method for Sampling from Continuous Determinantal Point Processes
Alireza Rezaei · Shayan Oveis Gharan

Thu Jun 13th 10:05 -- 10:10 AM @ Room 101

We study the Gibbs sampling algorithm for discrete and continuous $k$-determinantal point processes. We show that in both cases, the spectral gap of the chain is bounded by a polynomial of $k$ and it is independent of the size of the domain. As an immediate corollary, we obtain sublinear time algorithms for sampling from discrete $k$-DPPs given access to polynomially many processors. In the continuous setting, our result leads to the first class of rigorously analyzed efficient algorithms to generate random samples of continuous $k$-DPPs. We achieve this by showing that the Gibbs sampler for a large family of continuous $k$-DPPs can be simulated efficiently when the spectrum is not concentrated on the top $k$ eigenvalues.

Author Information

Alireza Rezaei (University of Washington)
Shayan Oveis Gharan (University of Washington)

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

More from the Same Authors