  The pairwise influence matrix of Dobrushin has long been used as an
analytical tool to bound the rate of convergence of Gibbs sampling. In this
work, we use Dobrushin influence as the basis of a practical tool to certify
and efficiently improve the quality of a discrete Gibbs sampler. Our
Dobrushin-optimized Gibbs samplers (DoGS) offer customized variable selection
orders for a given sampling budget and variable subset of interest, explicit
bounds on total variation distance to stationarity, and certifiable
improvements over the standard systematic and uniform random scan Gibbs
samplers. In our experiments with joint image segmentation and object
recognition, Markov chain Monte Carlo maximum likelihood estimation, and Ising
model inference, DoGS consistently deliver higher-quality inferences with
significantly smaller sampling budgets than standard Gibbs samplers.
