Reproduce “PolytopeWalk: Sparse MCMC Sampling over Polytopes” 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
Benny Sun, Yuansi Chen
PolytopeWalk is a new Python library designed for uniform sampling from high-dimensional, sparse polytopes, offering efficient implementations of barrier-based Markov Chain Monte Carlo algorithms. The library achieves significantly reduced per-iteration costs and robustly handles degenerate polytopes, outperforming existing tools on structured and real-world NetLib datasets.
Key insights
- Directly implementing MCMC algorithms for sparse, constrained polytope formulations significantly reduces per-iteration computational costs for high-dimensional problems.
- Robust preprocessing steps, like facial reduction, are essential for numerical stability and the ability to sample from degenerate real-world polytopes where other tools fail.
- Barrier-based MCMC algorithms (e.g., Dikin, Vaidya Walks), when implemented efficiently for sparsity, offer improved mixing rates compared to standard random walks, enhancing overall sampling efficiency.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.