On the mixing time of coordinate Hit-and-Run

Abstract

We obtain a polynomial upper bound on the mixing time $T_{CHR}(\epsilon )$ of the coordinate Hit-and-Run random walk on an $n-$dimensional convex body, where $T_{CHR}(\epsilon )$ is the number of steps needed in order to reach within $\epsilon$ of the uniform distribution with respect to the total variation distance, starting from a warm start (i.e., a distribution which has a density with respect to the uniform distribution on the convex body that is bounded above by a constant). Our upper bound is polynomial in $n,R$ and $\frac{1}{\epsilon }$, where we assume that the convex body contains the unit $\Vert \cdot {\Vert }_{\infty }$-unit ball $B_{\infty }$ and is contained in its $R$-dilation $R\cdot B_{\infty }$. Whether coordinate Hit-and-Run has a polynomial mixing time has been an open question.

Close to the final published version

Cited by in corpus (2)

• Truncated Log-concave Sampling with Reflective Hamiltonian Monte Carlo
• Sampling from convex sets with a cold start using multiscale decompositions