Name
Title | ||
|---|---|---|
A Polynomial Time MCMC Method for Sampling from Continuous Determinantal Point Processes |
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. |
Year | Venue | Field |
|---|---|---|
2019 | international conference on machine learning | Pattern recognition,Markov chain Monte Carlo,Computer science,Point process,Algorithm,Artificial intelligence,Sampling (statistics),Time complexity |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| A. Rezaei | 1 | 0 | 2.03 |
| Shayan Oveis Gharan | 2 | 323 | 26.63 |