Entropy contraction of the Gibbs sampler under log-concavity

• URL: http://arxiv.org/abs/2410.00858v1
• Date: Tue, 1 Oct 2024 16:50:36 GMT
• Title: Entropy contraction of the Gibbs sampler under log-concavity
• Authors: Filippo Ascolani, Hugo Lavenant, Giacomo Zanella,
• Abstract summary: We show that the random scan Gibbs sampler contracts in relative entropy and provide a sharp characterization of the associated contraction rate. Our techniques are versatile and extend to Metropolis-within-Gibbs schemes and the Hit-and-Run algorithm.
• Score: 0.16385815610837165
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 $\pi$ of interest. Under the assumption that $\pi$ 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 $\pi$ needed for the Gibbs sampler to mix grows linearly with the condition number and is independent of the dimension. If $\pi$ 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.

Related papers

• Diffusion at Absolute Zero: Langevin Sampling Using Successive Moreau Envelopes [52.69179872700035]
  We propose a novel method for sampling from Gibbs distributions of the form $pi(x)proptoexp(-U(x))$ with a potential $U(x)$. Inspired by diffusion models we propose to consider a sequence $(pit_k)_k$ of approximations of the target density, for which $pit_kapprox pi$ for $k$ small and, on the other hand, $pit_k$ exhibits favorable properties for sampling for $k$ large.
  arXiv  Detail & Related papers  (2025-02-03T13:50:57Z)
• A mixing time bound for Gibbs sampling from log-smooth log-concave distributions [0.8702432681310401]
  We study the behavior of the Gibbs sampler on the class of log-smooth and strongly log-concave target distributions. We show that the Gibbs sampler requires at most $Ostarleft(kappa2 n7.5left(maxleft1,sqrtfrac1nlog frac2Mgammarightright2right)$ steps to produce a sample with error no more than $gamma$ in total variation distance from a distribution with condition number $kappa$.
  arXiv  Detail & Related papers  (2024-12-23T19:00:02Z)
• Parallel simulation for sampling under isoperimetry and score-based diffusion models [56.39904484784127]
  As data size grows, reducing the iteration cost becomes an important goal. Inspired by the success of the parallel simulation of the initial value problem in scientific computation, we propose parallel Picard methods for sampling tasks. Our work highlights the potential advantages of simulation methods in scientific computation for dynamics-based sampling and diffusion models.
  arXiv  Detail & Related papers  (2024-12-10T11:50:46Z)
• Path integral Monte Carlo in a discrete variable representation with Gibbs sampling: dipolar planar rotor chain [0.0]
  We propose a Path Integral Monte Carlo (PIMC) approach based on discretized continuous degrees of freedom and rejection-free Gibbs sampling. We show that using Gibbs sampling is advantageous compared to traditional Metroplolis-Hastings rejection importance sampling.
  arXiv  Detail & Related papers  (2024-10-17T15:04:39Z)
• Linear Complexity Gibbs Sampling for Generalized Labeled Multi-Bernoulli Filtering [4.186094981300538]
  Generalized Labeled Multi-Bernoulli (GLMB) densities arise in a host of multi-object system applications analogous to Gaussians in single-object filtering. We propose a tempered Gibbs sampler that exploits the structure of the GLMB filtering density to achieve an $mathcalO(T(P+M))$ complexity. This innovation enables the GLMB filter implementation to be reduced from an $mathcalO(TP2M)$ complexity to $mathcalO(T(P+M+log T)+PM)
  arXiv  Detail & Related papers  (2022-11-29T09:26:43Z)
• Convergence for score-based generative modeling with polynomial complexity [9.953088581242845]
  We prove the first convergence guarantees for the core mechanic behind Score-based generative modeling. Compared to previous works, we do not incur error that grows exponentially in time or that suffers from a curse of dimensionality. We show that a predictor-corrector gives better convergence than using either portion alone.
  arXiv  Detail & Related papers  (2022-06-13T14:57:35Z)
• Mean-Square Analysis with An Application to Optimal Dimension Dependence of Langevin Monte Carlo [60.785586069299356]
  This work provides a general framework for the non-asymotic analysis of sampling error in 2-Wasserstein distance. Our theoretical analysis is further validated by numerical experiments.
  arXiv  Detail & Related papers  (2021-09-08T18:00:05Z)
• Tightening the Dependence on Horizon in the Sample Complexity of Q-Learning [59.71676469100807]
  This work sharpens the sample complexity of synchronous Q-learning to an order of $frac|mathcalS|| (1-gamma)4varepsilon2$ for any $0varepsilon 1$. Our finding unveils the effectiveness of vanilla Q-learning, which matches that of speedy Q-learning without requiring extra computation and storage.
  arXiv  Detail & Related papers  (2021-02-12T14:22:05Z)
• Complexity of zigzag sampling algorithm for strongly log-concave distributions [6.336005544376984]
  We study the computational complexity of zigzag sampling algorithm for strongly log-concave distributions. We prove that the zigzag sampling algorithm achieves $varepsilon$ error in chi-square divergence with a computational cost equivalent to $Obigl.
  arXiv  Detail & Related papers  (2020-12-21T03:10:21Z)
• Faster Convergence of Stochastic Gradient Langevin Dynamics for Non-Log-Concave Sampling [110.88857917726276]
  We provide a new convergence analysis of gradient Langevin dynamics (SGLD) for sampling from a class of distributions that can be non-log-concave. At the core of our approach is a novel conductance analysis of SGLD using an auxiliary time-reversible Markov Chain.
  arXiv  Detail & Related papers  (2020-10-19T15:23:18Z)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  Asynchronous Q-learning aims to learn the optimal action-value function (or Q-function) of a Markov decision process (MDP) We show that the number of samples needed to yield an entrywise $varepsilon$-accurate estimate of the Q-function is at most on the order of $frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$ up to some logarithmic factor.
  arXiv  Detail & Related papers  (2020-06-04T17:51:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.