A mixing time bound for Gibbs sampling from log-smooth log-concave distributions

2024/12/23 by Neha S. Wadia, Wadia, Neha S. · 1 voice · 2 citations
Mathematics · Computer Science · #Markov Chains and Monte Carlo Methods #Bayesian Methods and Mixture Models #Statistical Methods and Inference

paper · pdf · doi:10.48550/arxiv.2412.17899

Abstract

The Gibbs sampler, also known as the coordinate hit-and-run algorithm, is a Markov chain that is widely used to draw samples from probability distributions in arbitrary dimensions. At each iteration of the algorithm, a randomly selected coordinate is resampled from the distribution that results from conditioning on all the other coordinates. We study the behavior of the Gibbs sampler on the class of log-smooth and strongly log-concave target distributions supported on ℝⁿ. Assuming the initial distribution is M-warm with respect to the target, we show that the Gibbs sampler requires at most O^⋆(κ² n^7.5(max\1,√(1)/(n)log \frac2Mγ\)²) steps to produce a sample with error no more than γ in total variation distance from a distribution with condition number κ.

Cited by

• Convergence analysis of data augmentation algorithms in Bayesian lasso models with log-concave likelihoods
• Mixing Time Bounds for the Gibbs Sampler under Isoperimetry

Discussions

• many lovely papers online this morning: arxiv.org/abs/2412.17899 'A mixing time bound for Gibbs sampling from log-smooth log-concave distributions' - Neha S. Wadia [bsky, 25 points, 3 comments]

Related

• Convergence of Gibbs Sampling: Coordinate Hit-and-Run Mixes Fast
• Entropy contraction of the Gibbs sampler under log-concavity
• Mixing Time Bounds for the Gibbs Sampler under Isoperimetry
• Scan Order in Gibbs Sampling: Models in Which it Matters and Bounds on How Much
• Mixing time of an unaligned Gibbs sampler on the square