On Cyclical MCMC Sampling

• URL: http://arxiv.org/abs/2403.00230v1
• Date: Fri, 1 Mar 2024 02:20:44 GMT
• Title: On Cyclical MCMC Sampling
• Authors: Liwei Wang, Xinru Liu, Aaron Smith, Yves Atchade
• Abstract summary: We show that cyclical MCMC converges to the desired probability distribution in settings where the Markov kernels used are fast mixing. We also show that cyclical MCMC estimates well the local shape of the target distribution around each mode, even when we do not have convergence to the target.
• Score: 13.002470980542707
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Cyclical MCMC is a novel MCMC framework recently proposed by Zhang et al. (2019) to address the challenge posed by high-dimensional multimodal posterior distributions like those arising in deep learning. The algorithm works by generating a nonhomogeneous Markov chain that tracks -- cyclically in time -- tempered versions of the target distribution. We show in this work that cyclical MCMC converges to the desired probability distribution in settings where the Markov kernels used are fast mixing, and sufficiently long cycles are employed. However in the far more common settings of slow mixing kernels, the algorithm may fail to produce samples from the desired distribution. In particular, in a simple mixture example with unequal variance, we show by simulation that cyclical MCMC fails to converge to the desired limit. Finally, we show that cyclical MCMC typically estimates well the local shape of the target distribution around each mode, even when we do not have convergence to the target.

Related papers

• Symmetry-driven embedding of networks in hyperbolic space [0.4779196219827508]
  Hyperbolic models can reproduce the heavy-tailed degree distribution, high clustering, and hierarchical structure of empirical networks. Current algorithms for finding the hyperbolic coordinates of networks, however, do not quantify uncertainty in the inferred coordinates. We present BIGUE, a Markov chain Monte Carlo algorithm that samples the posterior distribution of a Bayesian hyperbolic random graph model.
  arXiv  Detail & Related papers  (2024-06-15T18:44:02Z)
• Convergence Bounds for Sequential Monte Carlo on Multimodal Distributions using Soft Decomposition [6.872242798058046]
  We prove bounds on the variance of a function $f$ under the empirical measure of the samples obtained by the Sequential Monte Carlo (SMC) algorithm. We show that bounds can be obtained in the truly multi-modal setting, with mixing times that depend on local MCMC dynamics.
  arXiv  Detail & Related papers  (2024-05-29T22:43:45Z)
• SpreadNUTS -- Moderate Dynamic Extension of Paths for No-U-Turn Sampling & Partitioning Visited Regions [0.0]
  This paper introduces modifications to a specific Hamiltonian Monte Carlo (HMC) algorithm known as the no-U-turn sampler (NUTS) NUTS aims to explore the sample space faster than NUTS, yielding a sampler that has faster convergence to the true distribution than NUTS.
  arXiv  Detail & Related papers  (2023-07-09T05:00:25Z)
• Reverse Diffusion Monte Carlo [19.35592726471155]
  We propose a novel Monte Carlo sampling algorithm called reverse diffusion Monte Carlo (rdMC) rdMC is distinct from the Markov chain Monte Carlo (MCMC) methods.
  arXiv  Detail & Related papers  (2023-07-05T05:42:03Z)
• 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)
• Bayesian Decision Trees Inspired from Evolutionary Algorithms [64.80360020499555]
  We propose a replacement of the Markov Chain Monte Carlo (MCMC) with an inherently parallel algorithm, the Sequential Monte Carlo (SMC) Experiments show that SMC combined with the Evolutionary Algorithms (EA) can produce more accurate results compared to MCMC in 100 times fewer iterations.
  arXiv  Detail & Related papers  (2023-05-30T06:17:35Z)
• Finite Sample Complexity of Sequential Monte Carlo Estimators on Multimodal Target Distributions [0.0]
  We prove finite sample complexities for sequential Monte Carlo (SMC) algorithms which require only local mixing times of the associated kernels. Our bounds are particularly useful when the target distribution is multimodal and global mixing of the kernel is slow.
  arXiv  Detail & Related papers  (2022-08-13T15:06:03Z)
• Deterministic Gibbs Sampling via Ordinary Differential Equations [77.42706423573573]
  This paper presents a general construction of deterministic measure-preserving dynamics using autonomous ODEs and tools from differential geometry. We show how Hybrid Monte Carlo and other deterministic samplers follow as special cases of our theory.
  arXiv  Detail & Related papers  (2021-06-18T15:36:09Z)
• Sampling in Combinatorial Spaces with SurVAE Flow Augmented MCMC [83.48593305367523]
  Hybrid Monte Carlo is a powerful Markov Chain Monte Carlo method for sampling from complex continuous distributions. We introduce a new approach based on augmenting Monte Carlo methods with SurVAE Flows to sample from discrete distributions. We demonstrate the efficacy of our algorithm on a range of examples from statistics, computational physics and machine learning, and observe improvements compared to alternative algorithms.
  arXiv  Detail & Related papers  (2021-02-04T02:21:08Z)
• MCMC-Interactive Variational Inference [56.58416764959414]
  We propose MCMC-interactive variational inference (MIVI) to estimate the posterior in a time constrained manner. MIVI takes advantage of the complementary properties of variational inference and MCMC to encourage mutual improvement. Experiments show that MIVI not only accurately approximates the posteriors but also facilitates designs of gradient MCMC and Gibbs sampling transitions.
  arXiv  Detail & Related papers  (2020-10-02T17:43:20Z)
• 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.