Fast MCMC Sampling Algorithms on Polytopes
Authors: Yuansi Chen, Raaz Dwivedi, Martin J. Wainwright, Bin Yu
JMLR 2018 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | The speed-up of the Vaidya walk over the Dikin walk are illustrated in numerical examples. ...In Section 4, We discuss the computational complexity of the different random walks and demonstrate the contrast between the random walks for several illustrative examples... 4.2 Simulations We now present simulation results for the random walks in Rd for d = 2, 10 and 50... |
| Researcher Affiliation | Collaboration | Yuansi Chen , EMAIL Raaz Dwivedi , EMAIL Martin J. Wainwright , , EMAIL Bin Yu , EMAIL Department of Statistics Department of Electrical Engineering and Computer Sciences University of California, Berkeley Voleon Group , Berkeley |
| Pseudocode | Yes | Algorithm 1: Vaidya Walk with parameter r (VW(r)) Algorithm 2: John Walk with parameter r (JW(r)) |
| Open Source Code | Yes | We provide implementations of the Dikin, Vaidya and John walks in python and a jupyter notebook at the github repository https://github.com/rzrsk/vaidya-walk. |
| Open Datasets | No | We now present simulation results for the random walks in Rd for d = 2, 10 and 50 with initial distribution µ0 = N(0, σ2 d Id) and target distribution being uniform, on the following polytopes: Set-up 1 : The set [ 1, 1]2 defined by different number of constraints. Set-up 2 : The set [ 1, 1]d for d {2, 3, 4, 5, 6, 7} for n = {2d, 2d2, 2d3} constraints. Set-up 3 : Symmetric polytopes in R2 with n-randomly-generated-constraints. Set-up 4 : The interior of regular n-polygons on the unit circle. Set-up 5 : Hyper cube [ 1, 1]d for d = 10 and 50. These setups describe how the data (polytopes) for simulations were generated or defined, rather than referring to external, publicly available datasets. |
| Dataset Splits | No | The paper uses synthetic or procedurally defined geometric shapes (polytopes, hypercubes) for its simulations, not traditional datasets that would typically require train/test/validation splits for model evaluation. Therefore, there is no mention of dataset splitting methodologies. |
| Hardware Specification | No | The paper describes simulation setups and theoretical results but does not provide any specific details about the hardware (e.g., CPU, GPU models, memory) used to run these simulations or experiments. |
| Software Dependencies | No | We provide implementations of the Dikin, Vaidya and John walks in python and a jupyter notebook at the github repository https://github.com/rzrsk/vaidya-walk. While 'python' and 'jupyter notebook' are mentioned, no specific version numbers for Python or any libraries are provided. |
| Experiment Setup | Yes | We choose σd such that the warmness parameter M is bounded by 100. We provide implementations of the Dikin, Vaidya and John walks in python and a jupyter notebook at the github repository https://github.com/rzrsk/vaidya-walk. We use the following three ways to compare the convergence rate of the Dikin and the Vaidya walks: (1) comparing the approximate mixing time of a particular subset of the polytope smaller value is associated with a faster mixing chain; (2) comparing the plot of the empirical distribution of samples from multiple runs of the Markov chain after k steps if it appears more uniform for smaller k, the chain is deemed to be faster; and (3) contrasting the sequential plots of one dimensional projection of samples for a single long run of the chain less smooth plot is associated with effective and fast exploration leading to a faster mixing (Yu and Mykland, 1998). |