mlsanityData to 14 Oct 2026

Entropy contraction of the Gibbs sampler under log-concavity

arXiv 2410.00858 ↗First posted 1 Oct 2024math.PR math.ST stat.COcited by 13

Not on the map. Why?

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.

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

23 of 77 references.

References · 23

  1. 2013A survey of the Schr"odinger problem and some of its connections with optimal transportcited by 292
  2. 2015Coordinate Descent Algorithmscited by 219
  3. 2014Theoretical guarantees for approximate sampling from smooth and log-concave densitiescited by 208
  4. 2015Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithmcited by 197
  5. 2018Log-concave sampling: Metropolis-Hastings algorithms are fastcited by 118
  6. 2019Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradientscited by 51
  7. 2023Faster high-accuracy log-concave sampling via algorithmic warm startscited by 45
  8. 2021Minimax Mixing Time of the Metropolis-Adjusted Langevin Algorithm for Log-Concave Samplingcited by 44
  9. 2018Coupling and Convergence for Hamiltonian Monte Carlocited by 36
  10. 2021The query complexity of sampling from strongly log-concave distributions in one dimensioncited by 18
  11. 2023When does Metropolized Hamiltonian Monte Carlo provably outperform Metropolis-adjusted Langevin algorithm?cited by 15
  12. 2024Convergence of coordinate ascent variational inference for log-concave measures via optimal transportcited by 14
11 more
  1. 2020Convergence of Gibbs Sampling: Coordinate Hit-and-Run Mixes Fastcited by 9
  2. 2021Scalable Bayesian computation for crossed and nested hierarchical modelscited by 9
  3. 2024Convergence rate of random scan Coordinate Ascent Variational Inference under log-concavitycited by 9
  4. 2019MALA-within-Gibbs samplers for high-dimensional distributions with sparse conditional structurecited by 8
  5. 2022Hamiltonian Monte Carlo for efficient Gaussian sampling: long and random stepscited by 8
  6. 2020Langevin Monte Carlo: random coordinate descent and variance reductioncited by 7
  7. 2020Random Coordinate Langevin Monte Carlocited by 7
  8. 2020Random Coordinate Underdamped Langevin Monte Carlocited by 6
  9. 2020Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Modelcited by 5
  10. 2023Dimension-free mixing times of Gibbs samplers for Bayesian hierarchical modelscited by 4
  11. 2024Scalability of Metropolis-within-Gibbs schemes for high-dimensional Bayesian modelscited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 6; 2025: 3; 2026: 4.

13 papers.

Sort:

  1. 2024Sampling and Integration of Logconcave Functions by Algorithmic Diffusioncited by 12
  2. 2024Fast Mixing of Data Augmentation Algorithms: Bayesian Probit, Logit, and Lasso Regressioncited by 3
  3. 2026A unified complexity bound for logconcave samplingcited by 3
  4. 2024Linear-cost unbiased posterior estimates for crossed effects and matrix factorization models via couplingscited by 2
  5. 2024A mixing time bound for Gibbs sampling from log-smooth log-concave distributionscited by 2
  6. 2024Local and Mixing-Based Algorithms for Gaussian Graphical Model Selection from Glauber Dynamicscited by 2
  7. 2025Mixing times of data-augmentation Gibbs samplers for high-dimensional probit regressioncited by 2
  8. 2026Wasserstein Contraction of Coordinate Ascent Variational Inferencecited by 1
  9. 2024Ballistic Convergence in Hit-and-Run Monte Carlo and a Coordinate-free Randomized Kaczmarz Algorithmcited by 0
  10. 2025Spectral gap of Metropolis-within-Gibbs under log-concavitycited by 0
  11. 2025A fast non-reversible sampler for Bayesian mixture modelscited by 0
  12. 2026On McDiarmid's Inequality under Dependence via Approximate Tensorization of Entropycited by 0
1 more
  1. 2026Mixing-Free and Signal-Optimal Learning of Gaussian Graphical Models from Glauber Dynamicscited by 0