A Polynomial Time MCMC Method for Sampling from Continuous DPPs
We study the Gibbs sampling algorithm for continuous determinantal point processes. We show that, given a warm start, the Gibbs sampler generates a random sample from a continuous $k$-DPP defined on a $d$-dimensional domain by only taking $\text{poly}(k)$ number of steps. As an application, we design an algorithm to generate random samples from $k$-DPPs defined by a spherical Gaussian kernel on a unit sphere in $d$-dimensions, $\mathbb{S}^{d-1}$ in time polynomial in $k,d$.
Code (0)
등록된 구현이 없습니다.
Tasks
Point ProcessesSimilar Papers 제목 키워드 기반
Scalable MCMC Sampling for Nonsymmetric Determinantal Point Processes
A determinantal point process (DPP) is an elegant model that assigns a probability to every subset of a collection of $n$ items. While conventionally a DPP is parameterized by a symmetric kernel matrix, removing this sym…
Point ProcessesFast Mixing Markov Chains for Strongly Rayleigh Measures, DPPs, and Constrained Sampling
We study probability measures induced by set functions with constraints. Such measures arise in a variety of real-world settings, where prior knowledge, resource limitations, or other pragmatic considerations impose cons…
Point ProcessesZonotope hit-and-run for efficient sampling from projection DPPs
Determinantal point processes (DPPs) are distributions over sets of items that model diversity using kernels. Their applications in machine learning include summary extraction and recommendation systems. Yet, the cost of…
DiversityPoint ProcessesRecommendation SystemsDeterminantal point processes based on orthogonal polynomials for sampling minibatches in SGD
Stochastic gradient descent (SGD) is a cornerstone of machine learning. When the number N of data items is large, SGD relies on constructing an unbiased estimator of the gradient of the empirical risk using a small subse…
Point ProcessesStatistical Consistency of Discrete-to-Continuous Limits of Determinantal Point Processes
We investigate the limiting behavior of discrete determinantal point processes (DPPs) towards continuous DPPs when the size of the set to sample from goes to infinity. We propose a non-asymptotic characterization of this…
Point Processes