Implementation of Random Walks on Polytopes

C++ implementation with python wrapper of Vaidya walk and John walk introduced by the paper "Fast MCMC Algorithms on Polytopes" https://arxiv.org/abs/1710.08165 by Yuansi Chen, Raaz Dwivedi, Martin J. Wainwright, Bin Yu

Use Guide

• Preparation: make sure you have boost (https://www.boost.org/) (TODO)
• Use recursive to pull the repo as follows, so that you get the external package Eigen (https://eigen.tuxfamily.org/). Otherwise, you have to download Eigen yourself and put it in the folder polytopewalk/src/external

git clone --recursive https://github.com/yuachen/polytopewalk.git

• To install the package to default python

pip install .

• Import the library

import polytopewalk

• Example

import polytopewalk as pw
# dimension
d = 2
(A, b) = pw.define_polytope(d, rep=0)
# radius 
r = 0.5
nb_samples = 10
nb_iters = 20

# generate samples with vaidya and john walk
samples_vaidya = pw.run_vaidya_walk(nb_samples, nb_iters, A, b, r)
samples_john = pw.run_john_walk(nb_samples, nb_iters, A, b, r)

License and Citation

Code is released under MIT License. Please cite the following paper if the code helps your research:

@article{chen2018fast,
  title={Fast MCMC sampling algorithms on polytopes},
  author={Chen, Yuansi and Dwivedi, Raaz and Wainwright, Martin J and Yu, Bin},
  journal={The Journal of Machine Learning Research},
  volume={19},
  number={1},
  pages={2146--2231},
  year={2018},
  publisher={JMLR. org}
}