Reproduce “Zonotope hit-and-run for efficient sampling from projection DPPs” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Guillaume Gautier, Rémi Bardenet, Michal Valko
This research introduces a Markov chain Monte Carlo sampler for projection Determinantal Point Processes, transforming the discrete sampling problem into a continuous one on a zonotope using a hit-and-run algorithm. The method yields faster mixing and more decorrelated samples per iteration compared to existing discrete MCMC approaches, proving advantageous for applications with costly objective function evaluations.
Key insights
- The set of bases for a linear matroid, which defines a projection DPP, can be uniquely associated with a tiling of a zonotope into parallelotopes, allowing a continuous geometric representation of the discrete sampling space.
- By appropriately weighting the continuous sampling distribution on the zonotope by the volume of these parallelotopes, the discrete bases can be sampled with probabilities proportional to their squared volumes, achieving projection DPP sampling.
- Using a hit-and-run MCMC on the continuous zonotope facilitates more 'global' moves between discrete bases, potentially leading to faster decorrelation of samples compared to local discrete state space transitions.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.