# Geodesic Walks in Polytopes

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jun 2016.

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

- [Diffusion Models for Constrained Domains](https://mlsanity.com/paper/2304.05364/) (2023)
- [Sampling with Riemannian Hamiltonian Monte Carlo in a Constrained Space](https://mlsanity.com/paper/2202.01908/) (2022)
- [Metropolis Sampling for Constrained Diffusion Models](https://mlsanity.com/paper/2307.05439/) (2023)
- [Convergence of the Riemannian Langevin Algorithm](https://mlsanity.com/paper/2204.10818/) (2022)
- [Mixing Time Guarantees for Unadjusted Hamiltonian Monte Carlo](https://mlsanity.com/paper/2105.00887/) (2021)
- [Condition-number-independent convergence rate of Riemannian Hamiltonian Monte Carlo with numerical integrators](https://mlsanity.com/paper/2210.07219/) (2022)
- [An Introduction to Hamiltonian Monte Carlo Method for Sampling](https://mlsanity.com/paper/2108.12107/) (2021)
- [Sampling with Barriers: Faster Mixing via Lewis Weights](https://mlsanity.com/paper/2303.00480/) (2023)
- [High-accuracy and dimension-free sampling with diffusions](https://mlsanity.com/paper/2601.10708/) (2026)
- [Unbiased constrained sampling with Self-Concordant Barrier Hamiltonian Monte Carlo](https://mlsanity.com/paper/2210.11925/) (2022)
- [Efficient Sampling on Riemannian Manifolds via Langevin MCMC](https://mlsanity.com/paper/2402.10357/) (2024)
- [Flows on convex polytopes](https://mlsanity.com/paper/2503.10232/) (2025)
- [Oracle-based Uniform Sampling from Convex Bodies](https://mlsanity.com/paper/2510.02983/) (2025)

## Abstract (arXiv)

We introduce the geodesic walk for sampling Riemannian manifolds and apply it to the problem of generating uniform random points from polytopes in R^n specified by m inequalities. The walk is a discrete-time simulation of a stochastic differential equation (SDE) on the Riemannian manifold equipped with the metric induced by the Hessian of a convex function; each step is the solution of an ordinary differential equation (ODE). The resulting sampling algorithm for polytopes mixes in O*(mn^{3/4}) steps. This is the first walk that breaks the quadratic barrier for mixing in high dimension, improving on the previous best bound of O*(mn) by Kannan and Narayanan for the Dikin walk. We also show that each step of the geodesic walk (solving an ODE) can be implemented efficiently, thus improving the time complexity for sampling polytopes. Our analysis of the geodesic walk for general Hessian manifolds does not assume positive curvature and might be of independent interest.