# Fast MCMC sampling algorithms on polytopes

arXiv: https://arxiv.org/abs/1710.08165 · HTML: https://mlsanity.com/paper/1710.08165/

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Oct 2017.

## Built on by (most cited first, 17 of 17)

- [A Proximal Algorithm for Sampling from Non-smooth Potentials](https://mlsanity.com/paper/2110.04597/) (2021)
- [A Proximal Algorithm for Sampling](https://mlsanity.com/paper/2202.13975/) (2022)
- [Counterfactual inference in sequential experiments](https://mlsanity.com/paper/2202.06891/) (2022)
- [Fast sampling from constrained spaces using the Metropolis-adjusted Mirror Langevin algorithm](https://mlsanity.com/paper/2312.08823/) (2023)
- [Quantum State Generation with Structure-Preserving Diffusion Model](https://mlsanity.com/paper/2404.06336/) (2024)
- [Fast John Ellipsoid Computation with Differential Privacy Optimization](https://mlsanity.com/paper/2408.06395/) (2024)
- [Unadjusted Langevin algorithm for sampling a mixture of weakly smooth potentials](https://mlsanity.com/paper/2112.09311/) (2021)
- [Margin-distancing for safe model explanation](https://mlsanity.com/paper/2202.11266/) (2022)
- [R'enyi-infinity constrained sampling with d3 membership queries](https://mlsanity.com/paper/2407.12967/) (2024)
- [Fast Mixing of Data Augmentation Algorithms: Bayesian Probit, Logit, and Lasso Regression](https://mlsanity.com/paper/2412.07999/) (2024)
- [Log-concave Sampling from a Convex Body with a Barrier: a Robust and Unified Dikin Walk](https://mlsanity.com/paper/2410.05700/) (2024)
- [Beyond the d2.5-mixing bound for Dikin walks on polytopes](https://mlsanity.com/paper/2607.13943/) (2026)
- [Autoregressive Policy Optimization for Constrained Allocation Tasks](https://mlsanity.com/paper/2409.18735/) (2024)
- [ReLU Networks as Random Functions: Their Distribution in Probability Space](https://mlsanity.com/paper/2503.22082/) (2025)
- [Polyra Swarms: A Shape-Based Approach to Machine Learning](https://mlsanity.com/paper/2506.13217/) (2025)
- [Beyond Averaging in John Ellipsoid Approximation: High-Accuracy Algorithms in the Leverage-Score Model](https://mlsanity.com/paper/2606.20082/) (2026)
- [On two proofs of d2 mixing of weighted Dikin walks](https://mlsanity.com/paper/2608.28566/) (2026)

## Abstract (arXiv)

We propose and analyze two new MCMC sampling algorithms, the Vaidya walk and the John walk, for generating samples from the uniform distribution over a polytope. Both random walks are sampling algorithms derived from interior point methods. The former is based on volumetric-logarithmic barrier introduced by Vaidya whereas the latter uses John's ellipsoids. We show that the Vaidya walk mixes in significantly fewer steps than the logarithmic-barrier based Dikin walk studied in past work. For a polytope in ℝd defined by n >d linear constraints, we show that the mixing time from a warm start is bounded as O(n0.5d1.5), compared to the O(nd) mixing time bound for the Dikin walk. The cost of each step of the Vaidya walk is of the same order as the Dikin walk, and at most twice as large in terms of constant pre-factors. For the John walk, we prove an O(d2.5·log4(n/d)) bound on its mixing time and conjecture that an improved variant of it could achieve a mixing time of O(d2·polylog(n/d)). Additionally, we propose variants of the Vaidya and John walks that mix in polynomial time from a deterministic starting point. The speed-up of the Vaidya walk over the Dikin walk are illustrated in numerical examples.