A Polynomial Time MCMC Method for Sampling from Continuous Determinantal Point Processes

Alireza Rezaei, Shayan Oveis Gharan
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:5438-5447, 2019.

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.

Cite this Paper

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.} }
Endnote
%0 Conference Paper %T A Polynomial Time MCMC Method for Sampling from Continuous Determinantal Point Processes %A Alireza Rezaei %A Shayan Oveis Gharan %B Proceedings of the 36th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Ruslan Salakhutdinov %F pmlr-v97-rezaei19a %I PMLR %P 5438--5447 %U https://proceedings.mlr.press/v97/rezaei19a.html %V 97 %X 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.
APA
Rezaei, A. & Gharan, S.O.. (2019). A Polynomial Time MCMC Method for Sampling from Continuous Determinantal Point Processes. Proceedings of the 36th International Conference on Machine Learning, in Proceedings of Machine Learning Research 97:5438-5447 Available from https://proceedings.mlr.press/v97/rezaei19a.html.

Related Material