Entropy contraction of the Gibbs sampler under log-concavity
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911385206652928 |
|---|---|
| author | Ascolani, Filippo Lavenant, Hugo Zanella, Giacomo |
| author_facet | Ascolani, Filippo Lavenant, Hugo Zanella, Giacomo |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_00858 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Entropy contraction of the Gibbs sampler under log-concavity Ascolani, Filippo Lavenant, Hugo Zanella, Giacomo Probability Statistics Theory Computation Machine Learning 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. |
| title | Entropy contraction of the Gibbs sampler under log-concavity |
| topic | Probability Statistics Theory Computation Machine Learning |
| url | https://arxiv.org/abs/2410.00858 |