# Entropy contraction of the Gibbs sampler under log-concavity

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 77 references that are in the map.
- First posted on arXiv 1 Oct 2024.

## Builds on (most cited first, 23 of 23)

- [A survey of the Schr"odinger problem and some of its connections with optimal transport](https://mlsanity.com/paper/1308.0215/) (2013)
- [Coordinate Descent Algorithms](https://mlsanity.com/paper/1502.04759/) (2015)
- [Theoretical guarantees for approximate sampling from smooth and log-concave densities](https://mlsanity.com/paper/1412.7392/) (2014)
- [Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithm](https://mlsanity.com/paper/1507.05021/) (2015)
- [Log-concave sampling: Metropolis-Hastings algorithms are fast](https://mlsanity.com/paper/1801.02309/) (2018)
- [Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradients](https://mlsanity.com/paper/1905.12247/) (2019)
- [Faster high-accuracy log-concave sampling via algorithmic warm starts](https://mlsanity.com/paper/2302.10249/) (2023)
- [Minimax Mixing Time of the Metropolis-Adjusted Langevin Algorithm for Log-Concave Sampling](https://mlsanity.com/paper/2109.13055/) (2021)
- [Coupling and Convergence for Hamiltonian Monte Carlo](https://mlsanity.com/paper/1805.00452/) (2018)
- [The query complexity of sampling from strongly log-concave distributions in one dimension](https://mlsanity.com/paper/2105.14163/) (2021)
- [When does Metropolized Hamiltonian Monte Carlo provably outperform Metropolis-adjusted Langevin algorithm?](https://mlsanity.com/paper/2304.04724/) (2023)
- [Convergence of coordinate ascent variational inference for log-concave measures via optimal transport](https://mlsanity.com/paper/2404.08792/) (2024)
- [Convergence of Gibbs Sampling: Coordinate Hit-and-Run Mixes Fast](https://mlsanity.com/paper/2009.11338/) (2020)
- [Scalable Bayesian computation for crossed and nested hierarchical models](https://mlsanity.com/paper/2103.10875/) (2021)
- [Convergence rate of random scan Coordinate Ascent Variational Inference under log-concavity](https://mlsanity.com/paper/2406.07292/) (2024)
- [MALA-within-Gibbs samplers for high-dimensional distributions with sparse conditional structure](https://mlsanity.com/paper/1908.09429/) (2019)
- [Hamiltonian Monte Carlo for efficient Gaussian sampling: long and random steps](https://mlsanity.com/paper/2209.12771/) (2022)
- [Langevin Monte Carlo: random coordinate descent and variance reduction](https://mlsanity.com/paper/2007.14209/) (2020)
- [Random Coordinate Langevin Monte Carlo](https://mlsanity.com/paper/2010.01405/) (2020)
- [Random Coordinate Underdamped Langevin Monte Carlo](https://mlsanity.com/paper/2010.11366/) (2020)
- [Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model](https://mlsanity.com/paper/2001.00303/) (2020)
- [Dimension-free mixing times of Gibbs samplers for Bayesian hierarchical models](https://mlsanity.com/paper/2304.06993/) (2023)
- [Scalability of Metropolis-within-Gibbs schemes for high-dimensional Bayesian models](https://mlsanity.com/paper/2403.09416/) (2024)

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

- [Sampling and Integration of Logconcave Functions by Algorithmic Diffusion](https://mlsanity.com/paper/2411.13462/) (2024)
- [Fast Mixing of Data Augmentation Algorithms: Bayesian Probit, Logit, and Lasso Regression](https://mlsanity.com/paper/2412.07999/) (2024)
- [A unified complexity bound for logconcave sampling](https://mlsanity.com/paper/2606.12694/) (2026)
- [Linear-cost unbiased posterior estimates for crossed effects and matrix factorization models via couplings](https://mlsanity.com/paper/2410.08939/) (2024)
- [A mixing time bound for Gibbs sampling from log-smooth log-concave distributions](https://mlsanity.com/paper/2412.17899/) (2024)
- [Local and Mixing-Based Algorithms for Gaussian Graphical Model Selection from Glauber Dynamics](https://mlsanity.com/paper/2412.18594/) (2024)
- [Mixing times of data-augmentation Gibbs samplers for high-dimensional probit regression](https://mlsanity.com/paper/2505.14343/) (2025)
- [Wasserstein Contraction of Coordinate Ascent Variational Inference](https://mlsanity.com/paper/2605.30253/) (2026)
- [Ballistic Convergence in Hit-and-Run Monte Carlo and a Coordinate-free Randomized Kaczmarz Algorithm](https://mlsanity.com/paper/2412.07643/) (2024)
- [Spectral gap of Metropolis-within-Gibbs under log-concavity](https://mlsanity.com/paper/2509.26175/) (2025)
- [A fast non-reversible sampler for Bayesian mixture models](https://mlsanity.com/paper/2510.03226/) (2025)
- [On McDiarmid's Inequality under Dependence via Approximate Tensorization of Entropy](https://mlsanity.com/paper/2606.12720/) (2026)
- [Mixing-Free and Signal-Optimal Learning of Gaussian Graphical Models from Glauber Dynamics](https://mlsanity.com/paper/2607.18559/) (2026)

## Abstract (arXiv)

The Gibbs sampler (a.k.a. Glauber dynamics and heat-bath algorithm) is a popular Markov Chain Monte Carlo algorithm which iteratively samples from the conditional distributions of a probability measure π of interest. Under the assumption that π is strongly log-concave, we show that the random scan Gibbs sampler contracts in relative entropy and provide a sharp characterization of the associated contraction rate. Assuming that evaluating conditionals is cheap compared to evaluating the joint density, our results imply that the number of full evaluations of π needed for the Gibbs sampler to mix grows linearly with the condition number and is independent of the dimension. If π is non-strongly log-concave, the convergence rate in entropy degrades from exponential to polynomial. Our techniques are versatile and extend to Metropolis-within-Gibbs schemes and the Hit-and-Run algorithm. A comparison with gradient-based schemes and the connection with the optimization literature are also discussed.