Abstract

Markov Chain Monte Carlo (MCMC) is a simple, generic strategy for sampling from a probability distribution $\pi(x)$, $x\in\mathbb{R}^{n$, in any dimension $n$. The Gibbs sampler is the natural MCMC algorithm to use when the one-dimensional full conditional distributions of each coordinate $x_i$ of $x$ are known and easy to sample from. Although an asymptotic guarantee of convergence for this sampler has existed for some time, non-asymptotic guarantees that identify the dimension dependence of its convergence behavior have only just begun to emerge. Building on the recent work of Aditi Laddha and Santosh Vempala, in which they establish a mixing time bound for Gibbs sampling from a uniform distribution supported on a convex body that is polynomial in $n$, we present a high-probability mixing time bound for the same sampler for log-smooth and strongly log-concave distributions supported on $\mathbb{R}}n$. This bound is also polynomial in $n$ up to logarithmic factors. Its proof proceeds via a conductance argument and relies on a new high-probability $L_0$ isoperimetric inequality for subsets of a convex body.