Characterizing Dependence of Samples along the Langevin Dynamics and Algorithms via Contraction of $Φ$-Mutual Information

• URL: http://arxiv.org/abs/2402.17067v2
• Date: Sat, 08 Feb 2025 18:00:36 GMT
• Title: Characterizing Dependence of Samples along the Langevin Dynamics and Algorithms via Contraction of $Φ$-Mutual Information
• Authors: Jiaming Liang, Siddharth Mitra, Andre Wibisono,
• Abstract summary: We study the question of how fast the samples become approximately independent along popular Markov chains for continuous-space sampling. Our proof technique is based on showing the Strong Data Processing Inequalities (SDPIs) hold along the Markov chains.
• Score: 16.54557731304283
• License:
• Abstract: The mixing time of a Markov chain determines how fast the iterates of the Markov chain converge to the stationary distribution; however, it does not control the dependencies between samples along the Markov chain. In this paper, we study the question of how fast the samples become approximately independent along popular Markov chains for continuous-space sampling: the Langevin dynamics in continuous time, and the Unadjusted Langevin Algorithm and the Proximal Sampler in discrete time. We measure the dependence between samples via $\Phi$-mutual information, which is a broad generalization of the standard mutual information, and which is equal to $0$ if and only if the the samples are independent. We show that along these Markov chains, the $\Phi$-mutual information between the first and the $k$-th iterate decreases to $0$ exponentially fast in $k$ when the target distribution is strongly log-concave. Our proof technique is based on showing the Strong Data Processing Inequalities (SDPIs) hold along the Markov chains. To prove fast mixing of the Markov chains, we only need to show the SDPIs hold for the stationary distribution. In contrast, to prove the contraction of $\Phi$-mutual information, we need to show the SDPIs hold along the entire trajectories of the Markov chains; we prove this when the iterates along the Markov chains satisfy the corresponding $\Phi$-Sobolev inequality, which is implied by the strong log-concavity of the target distribution.

Related papers

• Efficiently learning and sampling multimodal distributions with data-based initialization [20.575122468674536]
  We consider the problem of sampling a multimodal distribution with a Markov chain given a small number of samples from the stationary measure. We show that if the Markov chain has a $k$th order spectral gap, samples from the stationary distribution will efficiently generate a sample whose conditional law is $varepsilon$-close in TV distance to the stationary measure.
  arXiv  Detail & Related papers  (2024-11-14T01:37:02Z)
• Fast Convergence of $Φ$-Divergence Along the Unadjusted Langevin Algorithm and Proximal Sampler [14.34147140416535]
  We study the mixing time of two popular discrete-time Markov chains in continuous space. We show that any $Phi$-divergence arising from a twice-differentiable strictly convex function $Phi$ converges to $0$ exponentially fast along these Markov chains.
  arXiv  Detail & Related papers  (2024-10-14T16:41:45Z)
• Convergence of Score-Based Discrete Diffusion Models: A Discrete-Time Analysis [56.442307356162864]
  We study the theoretical aspects of score-based discrete diffusion models under the Continuous Time Markov Chain (CTMC) framework. We introduce a discrete-time sampling algorithm in the general state space $[S]d$ that utilizes score estimators at predefined time points. Our convergence analysis employs a Girsanov-based method and establishes key properties of the discrete score function.
  arXiv  Detail & Related papers  (2024-10-03T09:07:13Z)
• Ito Diffusion Approximation of Universal Ito Chains for Sampling, Optimization and Boosting [64.0722630873758]
  We consider rather general and broad class of Markov chains, Ito chains, that look like Euler-Maryama discretization of some Differential Equation. We prove the bound in $W_2$-distance between the laws of our Ito chain and differential equation.
  arXiv  Detail & Related papers  (2023-10-09T18:38:56Z)
• Adaptive Annealed Importance Sampling with Constant Rate Progress [68.8204255655161]
  Annealed Importance Sampling (AIS) synthesizes weighted samples from an intractable distribution. We propose the Constant Rate AIS algorithm and its efficient implementation for $alpha$-divergences.
  arXiv  Detail & Related papers  (2023-06-27T08:15:28Z)
• Enabling Quantum Speedup of Markov Chains using a Multi-level Approach [0.0]
  Quantum speedup for mixing a Markov chain can be achieved based on the construction of slowly-varying $r$ Markov chains. We show that the density function of a low-resolution Markov chain can be used to warm start the Markov chain with high resolution.
  arXiv  Detail & Related papers  (2022-10-25T15:17:52Z)
• Score-Based Diffusion meets Annealed Importance Sampling [89.92133671626327]
  Annealed Importance Sampling remains one of the most effective methods for marginal likelihood estimation. We leverage recent progress in score-based generative modeling to approximate the optimal extended target distribution for AIS proposals.
  arXiv  Detail & Related papers  (2022-08-16T12:13:29Z)
• A rapidly mixing Markov chain from any gapped quantum many-body system [2.321323878201932]
  We consider a bit string $x$ from a $pi(x)=|langle x|psirangle|2$, where $psi$ is the unique ground state of a local Hamiltonian $H$. Our main result describes a direct link between the inverse spectral gap of $H$ and the mixing time of an associated continuous-time Markov Chain with steady state $pi$.
  arXiv  Detail & Related papers  (2022-07-14T16:38:42Z)
• A Matrix Chernoff Bound for Markov Chains and Its Application to Co-occurrence Matrices [30.49132891333353]
  We prove a Chernoff-type bound for sums of matrix-valued random variables sampled via a regular (aperiodic and irreducible) finite Markov chain. Our proof is based on the matrix expander (regular undirected graph) Chernoff bound [Garg et al. STOC '18] and scalar Chernoff-Hoeffding bounds for Markov chains. Our matrix Chernoff bound for Markov chains can be applied to analyze the behavior of co-occurrence statistics for sequential data.
  arXiv  Detail & Related papers  (2020-08-06T05:44:54Z)
• 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)
• Targeted stochastic gradient Markov chain Monte Carlo for hidden Markov models with rare latent states [48.705095800341944]
  Markov chain Monte Carlo (MCMC) algorithms for hidden Markov models often rely on the forward-backward sampler. This makes them computationally slow as the length of the time series increases, motivating the development of sub-sampling-based approaches. We propose a targeted sub-sampling approach that over-samples observations corresponding to rare latent states when calculating the gradient of parameters associated with them.
  arXiv  Detail & Related papers  (2018-10-31T17:44:20Z)

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.