A Polynomial Time MCMC Method for Sampling from Continuous Determinantal Point Processes
Alireza Rezaei, Shayan Oveis Gharan
Abstract
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.
BibTeX
@InProceedings{pmlr-v97-rezaei19a,
title = {A Polynomial Time {MCMC} Method for Sampling from Continuous Determinantal Point Processes},
author = {Rezaei, Alireza and Gharan, Shayan Oveis},
booktitle = {Proceedings of the 36th International Conference on Machine Learning},
pages = {5438--5447},
year = {2019},
editor = {Chaudhuri, Kamalika and Salakhutdinov, Ruslan},
volume = {97},
series = {Proceedings of Machine Learning Research},
month = {09--15 Jun},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v97/rezaei19a/rezaei19a.pdf},
url = {https://proceedings.mlr.press/v97/rezaei19a.html},
abstract = {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.}
}