Markov Chain Monte Carlo

Also known as MCMC

Follow this topic Ask about this topic

Latest papers 145

27 papers in the last four weeks, up 50% on the four weeks before. 0.2% of all new papers.

Mar 30, 2026

From Independent to Correlated Diffusion: Generalized Generative Modeling with Probabilistic Computers

Diffusion models have emerged as a powerful framework for generative tasks in deep learning. They decompose generative modeling into two computational primitives: deterministic neural-network evaluation and stochastic sampling. Current implementations usually place most computation in the neural network, but diffusion as a framework allows a broader range of choices for the stochastic transition kernel. Here, we generalize the stochastic sampling component by replacing independent noise injection with Markov chain Monte Carlo (MCMC) dynamics that incorporate known interaction structure. Standard independent diffusion is recovered as a special case when couplings are set to zero. By explicitly incorporating Ising couplings into the diffusion dynamics, the noising and denoising processes exploit spatial correlations representative of the target system. The resulting framework maps naturally onto probabilistic computers (p-computers) built from probabilistic bits (p-bits), which provide orders-of-magnitude advantages in sampling throughput and energy efficiency over GPUs. We demonstrate the approach on equilibrium states of the 2D ferromagnetic Ising model and the 3D Edwards-Anderson spin glass, showing that correlated diffusion produces samples in closer agreement with MCMC reference distributions than independent diffusion. More broadly, the framework shows that p-computers can enable new classes of diffusion algorithms that exploit structured probabilistic sampling for generative modeling.

Nihal Sanjay Singh, Mazdak Mohseni-Rajaee, Shaila Niazi +1

Department of Electrical and Computer Engineering, University of California, Santa Barbara, Santa Barbara, CA, 93106, USA

Diffusion Models Physics-Informed Generative Modeling Markov Chain Monte Carlo

Mar 24, 2026

Algorithmic warm starts for Hamiltonian Monte Carlo

Generating samples from a continuous probability density is a central algorithmic problem across statistics, engineering, and the sciences. For high-dimensional settings, Hamiltonian Monte Carlo (HMC) is the default algorithm across mainstream software packages. However, despite the extensive line of work on HMC and its widespread empirical success, it remains unclear how many iterations of HMC are required as a function of the dimension

d

. On one hand, a variety of results show that Metropolized HMC converges in

O(d^{1/4})

iterations from a warm start close to stationarity. On the other hand, Metropolized HMC is significantly slower without a warm start, e.g., requiring

Ω(d^{1/2})

iterations even for simple target distributions such as isotropic Gaussians. Finding a warm start is therefore the computational bottleneck for HMC. We resolve this issue for the well-studied setting of sampling from a probability distribution satisfying strong log-concavity (or isoperimetry) and third-order derivative bounds. We prove that non-Metropolized HMC generates a warm start in

\tilde{O}(d^{1/4})

iterations, after which we can exploit the warm start using Metropolized HMC. Our final complexity of

\tilde{O}(d^{1/4})

is the fastest algorithm for high-accuracy sampling under these assumptions, improving over the prior best of

\tilde{O}(d^{1/2})

. This closes the long line of work on the dimensional complexity of MHMC for such settings, and also provides a simple warm-start prescription for practical implementations.

Matthew S. Zhang, Jason M. Altschuler, Sinho Chewi

UToronto · UPenn · Yale

Markov Chain Monte Carlo Sample Complexity Log-Concave Sampling

Mar 19, 2026

A Theoretical Comparison of No-U-Turn Sampler Variants: Necessary and Sufficient Convergence Conditions and Mixing Time Analysis under Gaussian Targets

The No-U-Turn Sampler (NUTS) is the computational workhorse of modern Bayesian software libraries, yet its qualitative and quantitative convergence guarantees were established only recently. A significant gap remains in the theoretical comparison of its two main variants: NUTS-mul and NUTS-BPS, which use multinomial sampling and biased progressive sampling, respectively, for index selection. In this paper, we address this gap in three contributions. First, we derive the first necessary conditions for geometric ergodicity for both variants. Second, we establish the first sufficient conditions for geometric ergodicity and ergodicity for NUTS-mul. Third, we obtain the first mixing time result for NUTS-BPS on a standard Gaussian distribution. Our results show that NUTS-mul and NUTS-BPS exhibit nearly identical qualitative behavior, with geometric ergodicity depending on the tail properties of the target distribution. However, they differ quantitatively in their convergence rates. More precisely, when initialized in the typical set of the canonical Gaussian measure, the mixing times of both NUTS-mul and NUTS-BPS scale as

O(d^{1/4})

up to logarithmic factors, where

d

denotes the dimension. Nevertheless, the associated constants are strictly smaller for NUTS-BPS.

Samuel Gruffaz, Kyurae Kim, Fares Guehtar +2

Université Paris-Saclay, ENS Paris-Saclay, Centre Borelli, F-91190 Gif-sur-Yvette, France. · University of Pennsylvania

Markov Chain Monte Carlo

Mar 18, 2026

Tackling the Sign Problem in the Doped Hubbard Model with Normalizing Flows

The Hubbard model at finite chemical potential is a cornerstone for understanding doped correlated systems, but simulations are severely limited by the sign problem. In the auxiliary-field formulation, the spin basis mitigates the sign problem, yet severe ergodicity issues have limited its use. We extend recent advances with normalizing flows at half-filling to finite chemical potential by introducing an annealing scheme enabling ergodic sampling. Compared to state-of-the-art hybrid Monte Carlo in the charge basis, our approach accurately reproduces exact diagonalization results while reducing statistical uncertainties by an order of magnitude, opening a new path for simulations of doped correlated systems.

Dominic Schuh, Lena Funcke, Janik Kreit +2

Transdisciplinary Research Area (TRA) Matter, University of Bonn, Bonn, Germany · Helmholtz Institute for Radiation and Nuclear Physics (HISKP), University of Bonn, Bonn, Germany · Institute for Advanced Simulation 4 (IAS-4), Forschungszentrum Jülich, Jülich, Germany

Quantum Many-Body Physics Markov Chain Monte Carlo Normalizing Flows

Mar 18, 2026

Generative Replica-Exchange: A Flow-based Framework for Accelerating Replica Exchange Simulations

Replica exchange (REX) is one of the most widely used enhanced sampling methodologies, yet its efficiency is limited by the requirement for a large number of intermediate temperature replicas. Here we present Generative Replica Exchange (GREX), which integrates deep generative models into the REX framework to eliminate this temperature ladder. Drawing inspiration from reservoir replica exchange (res-REX), GREX utilizes trained normalizing flows to generate high-temperature configurations on demand and map them directly to the target distribution using the potential energy as a constraint, without requiring target-temperature training data. This approach reduces production simulations to a single replica at the target temperature while maintaining thermodynamic rigor through Metropolis exchange acceptance. We validate GREX on three benchmark systems of increasing complexity, highlighting its superior efficiency and practical applicability for molecular simulations.

Shengjie Huang, Sijie Yang, Jianqiao Yi +6

State Key Laboratory of Bioactive Molecules and Druggability Assessment, International Cooperative Laboratory of Traditional Chinese Medicine Modernization and Innovative Drug Discovery of Chinese Ministry of Education (MOE), School of Pharmacy, Jinan University, #855 Xingye Avenue, Guangzhou, 510632, China · Department of Biochemistry and Molecular Pharmacology, NYU Grossman School of Medicine, New York, NY 10016, USA · Howard Hughes Medical Institute, NYU Grossman School of Medicine, New York, NY 10016, USA +1

Molecular Dynamics Simulation Parallel Tempering Markov Chain Monte Carlo

Mar 10, 2026

A Generative Sampler for distributions with possible discrete parameter based on Reversibility

Learning to sample from complex unnormalized distributions is a fundamental challenge in computational physics and machine learning. While score-based and variational methods have achieved success in continuous domains, extending them to discrete or mixed-variable systems remains difficult due to ill-defined gradients or high variance in estimators. We propose a unified, target-gradient-free generative sampling framework applicable across diverse state spaces. Building on the fact that detailed balance implies the time-reversibility of the equilibrium stochastic process, we enforce this symmetry as a statistical constraint. Specifically, using a prescribed physical transition kernel (such as Metropolis-Hastings), we minimize the Maximum Mean Discrepancy (MMD) between the joint distributions of forward and backward Markov trajectories. Crucially, this training procedure relies solely on energy evaluations via acceptance ratios, circumventing the need for target score functions or continuous relaxations. We demonstrate the versatility of our method on three distinct benchmarks: (1) a continuous multi-modal Gaussian mixture, (2) the discrete high-dimensional Ising model, and (3) a challenging hybrid system coupling discrete indices with continuous dynamics. Experiments show that our framework accurately reproduces thermodynamic observables and captures mode-switching behavior across all regimes, offering a physically grounded and universally applicable alternative for equilibrium sampling.

Lei Li, Zhen Wang, Lishuo Zhang

School of Mathematical Sciences, Shanghai Jiao Tong University, Shanghai, 200240, P.R.China. · Institute of Natural Sciences, MOE-LSC, Shanghai Jiao Tong University, Shanghai, 200240, P.R.China.

Generative Modeling Markov Chain Monte Carlo

Mar 3, 2026

Thermodynamic Regulation of Finite-Time Gibbs Training in Energy-Based Models: A Restricted Boltzmann Machine Study

Restricted Boltzmann Machines (RBMs) are typically trained using finite-length Gibbs chains under a fixed sampling temperature. This practice implicitly assumes that the stochastic regime remains valid as the energy landscape evolves during learning. We argue that this assumption can become structurally fragile under finite-time training dynamics. This fragility arises because, in nonconvex energy-based models, fixed-temperature finite-time training can generate admissible trajectories with effective-field amplification and conductance collapse. As a result, the Gibbs sampler may asymptotically freeze, the negative phase may localize, and, without sufficiently strong regularization, parameters may exhibit deterministic linear drift. To address this instability, we introduce an endogenous thermodynamic regulation framework in which temperature evolves as a dynamical state variable coupled to measurable sampling statistics. Under standard local Lipschitz conditions and a two-time-scale separation regime, we establish global parameter boundedness under strictly positive L2 regularization. We further prove local exponential stability of the thermodynamic subsystem and show that the regulated regime mitigates inverse-temperature blow-up and freezing-induced degeneracy within a forward-invariant neighborhood. Experiments on MNIST demonstrate that the proposed self-regulated RBM substantially improves normalization stability and effective sample size relative to fixed-temperature baselines, while preserving reconstruction performance. Overall, the results reinterpret RBM training as a controlled non-equilibrium dynamical process rather than a static equilibrium approximation.

Görkem Can Süleymanoğlu

Owner and Software Developer, Kuanka Publishing LLC, Turkey. · Ph.D. Student in Economics, Selçuk University, Institute of Social Sciences, Turkey.

Restricted Boltzmann Machines Energy-Based Models Statistical Physics of Learning Markov Chain Monte Carlo

Mar 2, 2026

Dimension-Independent Convergence of Underdamped Langevin Monte Carlo in KL Divergence

Underdamped Langevin dynamics (ULD) is a widely-used sampler for Gibbs distributions

π\propto e^{-V}

, and is often empirically effective in high dimensions. However, existing non-asymptotic convergence guarantees for discretized ULD typically scale polynomially with the ambient dimension

d

, leading to vacuous bounds when

d

is large. The main known dimension-free result concerns the randomized midpoint discretization in Wasserstein-2 distance (Liu et al.,2023), while dimension-independent guarantees for ULD discretizations in KL divergence have remained open. We close this gap by proving the first dimension-free KL divergence bounds for discretized ULD. Our analysis refines the KL local error framework (Altschuler et al., 2025) to a dimension-free setting and yields bounds that depend on

\mathrm{tr}(\mathbf{H})

, where

\mathbf{H}

upper bounds the Hessian of

V

, rather than on

d

. As a consequence, we obtain improved iteration complexity for underdamped Langevin Monte Carlo relative to overdamped Langevin methods in regimes where

\mathrm{tr}(\mathbf{H})\ll d

.

Shiyuan Zhang, Qiwei Di, Xuheng Li +1

Department of Computer Science, University of California, Los Angeles, CA 90095, USA

Markov Chain Monte Carlo Langevin Dynamics Convergence Analysis

Feb 24, 2026

Proximal-IMH: Proximal Posterior Proposals for Independent Metropolis-Hastings with Approximate Operators

We consider the problem of sampling from a posterior distribution arising in Bayesian inverse problems in science, engineering, and imaging. Our method belongs to the family of independence Metropolis-Hastings (IMH) sampling algorithms, which are common in Bayesian inference. Relying on the existence of an approximate posterior distribution that is cheaper to sample from but may have significant bias, we introduce Proximal-IMH, a scheme that removes this bias by correcting samples from the approximate posterior through an auxiliary optimization problem. This yields a local adjustment that trades off adherence to the exact model against stability around the approximate reference point. For idealized settings, we prove that the proximal correction tightens the match between approximate and exact posteriors, thereby improving acceptance rates and mixing. The method applies to both linear and nonlinear input-output operators and is particularly suitable for inverse problems where exact posterior sampling is too expensive. We present numerical experiments including multimodal and data-driven priors with nonlinear input-output operators. The results show that Proximal-IMH reliably outperforms existing IMH variants.

Youguang Chen, George Biros

Oden Institute for Computational Engineering and Sciences, The University of Texas at Austin, Austin, Texas, USA

Posterior Sampling Markov Chain Monte Carlo Bayesian Inverse Problems

Feb 24, 2026

Counterdiabatic Hamiltonian Monte Carlo

Hamiltonian Monte Carlo (HMC) is a state of the art method for sampling from distributions with differentiable densities, but can converge slowly when applied to challenging multimodal problems. Running HMC with a time varying Hamiltonian, in order to interpolate from an initial tractable distribution to the target of interest, can address this problem. In conjunction with a weighting scheme to eliminate bias, this can be viewed as a special case of Sequential Monte Carlo (SMC) sampling \cite{doucet2001introduction}. However, this approach can be inefficient, since it requires slow change between the initial and final distribution. Inspired by \cite{sels2017minimizing}, where a learned counterdiabatic term added to the Hamiltonian allows for efficient quantum state preparation, we propose Counterdiabatic Hamiltonian Monte Carlo (CHMC), which can be viewed as an SMC sampler with a more efficient kernel. We establish its relationship to recent proposals for accelerating gradient-based sampling with learned drift terms, and demonstrate on simple benchmark problems.

Reuben Cohn-Gordon, Uroš Seljak, Dries Sels

University of California, Berkeley · New York University

Markov Chain Monte Carlo

Feb 24, 2026

Deep unfolding of MCMC kernels: scalable, modular & explainable GANs for high-dimensional posterior sampling

Markov chain Monte Carlo (MCMC) methods are fundamental to Bayesian computation, but can be computationally intensive, especially in high-dimensional settings. Push-forward generative models, such as generative adversarial networks (GANs), variational auto-encoders and normalising flows offer a computationally efficient alternative for posterior sampling. However, push-forward models are opaque as they lack the modularity of Bayes Theorem, leading to poor generalisation with respect to changes in the likelihood function. In this work, we introduce a novel approach to GAN architecture design by applying deep unfolding to Langevin MCMC algorithms. This paradigm maps fixed-step iterative algorithms onto modular neural networks, yielding architectures that are both flexible and amenable to interpretation. Crucially, our design allows key model parameters to be specified at inference time, offering robustness to changes in the likelihood parameters. We train these unfolded samplers end-to-end using a supervised regularized Wasserstein GAN framework for posterior sampling. Through extensive Bayesian imaging experiments, we demonstrate that our proposed approach achieves high sampling accuracy and excellent computational efficiency, while retaining the physics consistency, adaptability and interpretability of classical MCMC strategies.

Jonathan Spence, Tobías I. Liaudat, Konstantinos Zygalakis +1

Maxwell Institute for Mathematical Sciences, Bayes Centre, 47 Potterrow, Edinburgh, Scotland, UK · School of Mathematical and Computer Sciences, Heriot-Watt University, Edinburgh, Scotland, UK · IRFU, CEA, Université Paris-Saclay, F-91191 Gif-sur-Yvette, France +1

Posterior Sampling Generative Adversarial Networks Markov Chain Monte Carlo Deep Unfolding Bayesian Inverse Problems

Feb 17, 2026

Robust Stochastic Gradient Posterior Sampling with Lattice Based Discretisation

Stochastic-gradient MCMC methods enable scalable Bayesian posterior sampling but often suffer from sensitivity to minibatch size and gradient noise. To address this, we propose Stochastic Gradient Lattice Random Walk (SGLRW), an extension of the Lattice Random Walk discretization. Unlike conventional Stochastic Gradient Langevin Dynamics (SGLD), SGLRW introduces stochastic noise only through the off-diagonal elements of the update covariance; this yields greater robustness to minibatch size while retaining asymptotic correctness. Furthermore, as comparison we analyze a natural analogue of SGLD utilizing gradient clipping. Experimental validation on Bayesian regression and classification demonstrates that SGLRW remains stable in regimes where SGLD fails, including in the presence of heavy-tailed gradient noise, and matches or improves predictive performance.

Zier Mensch, Lars Holdijk, Samuel Duffield +4

Institute of Physics, University of Amsterdam, Netherlands · Department of Physics, National Taiwan University, Taiwan · Department of Computer Science, University of Oxford, United Kingdom +4

Posterior Sampling Markov Chain Monte Carlo Stochastic Gradient Langevin Dynamics Stochastic Gradient Descent

Feb 16, 2026

Constrained and Composite Sampling via Proximal Sampler

We study two log-concave sampling problems: constrained sampling and composite sampling. First, we consider sampling from a target distribution with density proportional to

\exp(-f(x))

supported on a convex set

K \subset \mathbb{R}^d

, where

f

is convex. The main challenge is enforcing feasibility without degrading mixing. Using an epigraph transformation, we reduce this task to sampling from a nearly uniform distribution over a lifted convex set in

\mathbb{R}^{d+1}

. We then solve the lifted problem using a proximal sampler. Assuming only a separation oracle for

K

and a subgradient oracle for

f

, we develop an implementation of the proximal sampler based on the cutting-plane method and rejection sampling. Unlike existing constrained samplers that rely on projection, reflection, barrier functions, or mirror maps, our approach enforces feasibility using only minimal oracle access, resulting in a practical and unbiased sampler without knowing the geometry of the constraint set. Second, we study composite sampling, where the target is proportional to

\exp(-f(x)-h(x))

with closed and convex

f

and

h

. This composite structure is standard in Bayesian inference with

f

modeling data fidelity and

h

encoding prior information. We reduce composite sampling via an epigraph lifting of

h

to constrained sampling in

\mathbb{R}^{d+1}

, which allows direct application of the constrained sampling algorithm developed in the first part. This reduction results in a double epigraph lifting formulation in

\mathbb{R}^{d+2}

, on which we apply a proximal sampler. By keeping

f

and

h

separate, we further demonstrate how different combinations of oracle access (such as subgradient and proximal) can be leveraged to construct separation oracles for the lifted problem. For both sampling problems, we establish mixing time bounds measured in Rényi and

χ^2

divergences.

Thanh Dang, Jiaming Liang

Department of Computer Science, University of Rochester, Rochester, NY 14620. · Goergen Institute for Data Science and Artificial Intelligence (GIDS-AI) and Department of Computer Science, University of Rochester, Rochester, NY 14620

Log-Concave Sampling Markov Chain Monte Carlo

Feb 11, 2026

A Gibbs posterior sampler for inverse problem based on prior diffusion model

This paper addresses the issue of inversion in cases where (1) the observation system is modeled by a linear transformation and additive error, (2) the problem is ill-posed and regularization relies on a Bayesian strategy, (3)~the prior is modeled by a diffusion process adjusted on an available large set of examples. In this context, it is known that the issue of posterior sampling is a thorny one and the paper introduces a Gibbs algorithm. It appears that this avenue has not been explored, and we show that it is particularly effective and remarkably simple. In addition, it provides clear elements regarding convergence guarantees in a specific case and arguments supporting such guarantees in practical cases. The results are clearly confirmed by numerical simulations based on a toy example.

Jean-François Giovannelli

Groupe Signal-Image, IMS (Univ. Bordeaux, CNRS, BINP), Talence, France

Markov Chain Monte Carlo Bayesian Inverse Problems Posterior Sampling Diffusion-Based Inverse Problems Diffusion Posterior Sampling

Dec 19, 2025

Sampling from multimodal distributions with warm starts: Non-asymptotic bounds for the Reweighted Annealed Leap-Point Sampler

Sampling from multimodal distributions is a central challenge in Bayesian inference and machine learning. In light of hardness results for sampling -- classical MCMC methods, even with tempering, can suffer from exponential mixing times -- a natural question is how to leverage additional information, such as a warm start point for each mode, to enable faster mixing across modes. To address this, we introduce Reweighted ALPS (Re-ALPS), a modified version of the Annealed Leap-Point Sampler (ALPS) that dispenses with the Gaussian approximation assumption. We prove the first polynomial-time bound that works in a general setting, under a natural assumption that each component contains significant mass relative to the others when tilted towards the corresponding warm start point. Similarly to ALPS, we define distributions tilted towards a mixture centered at the warm start points, and at the coldest level, use teleportation between warm start points to enable efficient mixing across modes. In contrast to ALPS, our method does not require Hessian information at the modes, but instead estimates component partition functions via Monte Carlo. This additional estimation step is crucial in allowing the algorithm to handle target distributions with more complex geometries besides approximate Gaussian. For the proof, we show convergence results for Markov processes when only part of the stationary distribution is well-mixing and estimation for partition functions for individual components of a mixture.

Holden Lee, Matheau Santana-Gijzen

Markov Chain Monte Carlo

Oct 20, 2025

The Marked Edge Walk: A Novel MCMC Algorithm for Sampling of Graph Partitions

Novel Markov Chain Monte Carlo (MCMC) methods have enabled the generation of large ensembles of redistricting plans modeled as a graph partitioning problem. However, existing algorithms such as Reversible Recombination (RevReCom) and Metropolized Forest Recombination (MFR) have strong preferences for distributions related to the spanning tree measure. In this paper we introduce the Marked Edge Walk (MEW), a novel Markov chain proposal for sampling from the space of graph partitions. The walk operates on the space of spanning trees with marked edges, allowing for calculable transition probabilities for use in the Metropolis-Hastings algorithm. Empirical results on real-world dual graphs show convergence under a broad class of target distributions less constrained by spanning tree counts, including policy-based distributions, such as competitiveness on New Hampshire that are independent of spanning trees, and compactness and partisan symmetry distributions on New Hampshire and Texas that, while related to spanning trees, can now be properly targeted with a smaller degree of spanning tree bias, which represents an advancement in flexible ensemble generation.

Atticus McWhorter, Daryl DeFord

Department of Mathematics, Dartmouth College, 1 College Street, Hanover, 03755, NH, USA · Department of Mathematics and Statistics, Vassar College, 124 Raymond Avenue, Poughkeepsie, 12604, NY, USA

Markov Chain Monte Carlo

Oct 20, 2025

Estimating Orbital Parameters of Direct Imaging Exoplanet Using Neural Network

In this work, we propose a flow-matching Markov chain Monte Carlo (FM-MCMC) algorithm for estimating the orbital parameters of exoplanetary systems, especially for those only one exoplanet is involved. Compared to traditional methods that rely on random sampling within the Bayesian framework, our approach first leverages flow matching posterior estimation (FMPE) to efficiently constrain the prior range of physical parameters, and then employs MCMC to accurately infer the posterior distribution. For example, in the orbital parameter inference of beta Pictoris b, our model achieved a substantial speed-up while maintaining comparable accuracy-running 77.8 times faster than Parallel Tempered MCMC (PTMCMC) and 365.4 times faster than nested sampling. Moreover, our FM-MCMC method also attained the highest average log-likelihood among all approaches, demonstrating its superior sampling efficiency and accuracy. This highlights the scalability and efficiency of our approach, making it well-suited for processing the massive datasets expected from future exoplanet surveys. Beyond astrophysics, our methodology establishes a versatile paradigm for synergizing deep generative models with traditional sampling, which can be adopted to tackle complex inference problems in other fields, such as cosmology, biomedical imaging, and particle physics.

Bo Liang, Hanlin Song, Chang Liu +9

Center for Gravitational Wave Experiment, National Microgravity Laboratory, Institute of Mechanics, Chinese Academy of Sciences, Beijing 100190, China · Taiji Laboratory for Gravitational Wave Universe (Beijing/Hangzhou), University of Chinese Academy of Sciences (UCAS), Beijing 100049, China · National Space Science Center, Chinese Academy of Sciences, Beijing 100190, China +6

Markov Chain Monte Carlo Simulation-Based Inference Bayesian Inference

Sep 2, 2025

Bouncy particle sampler with infinite exchanging parallel tempering

Markov chain Monte Carlo is one of the most useful tools for obtaining samples from complex distributions, such as posterior distributions in Bayesian inference. Bouncy particle sampler (BPS) is a method that performs sampling using uniform linear motion and elastic collisions. Since BPS does not require time discretization, it is expected to be more advantageous than the widely used Hamiltonian Monte Carlo (HMC) and Langevin Monte Carlo (LMC) for distributions with large curvature changes. To sample more efficiently from multimodal distributions, we propose BPS with parallel tempering (BPS-PT) in the infinite exchange limit, based on LMC-PT with the infinite exchange rate proposed in a previous study. Using a distribution with large curvature changes, BPS-PT showed estimation accuracy comparable to HMC-PT and LMC-PT, and achieved higher ESS per computational time. Therefore, BPS-PT is considered to be effective for distributions with large curvature changes.

Yohei Saito, Shun Kimura, Koujin Takeda

Center for Mathematics and Data Science, Gunma University · Graduate School of Science and Engineering, Ibaraki University

Markov Chain Monte Carlo Parallel Tempering

Aug 13, 2025

Comparison of D-Wave Quantum Annealing and Gibbs Monte Carlo for Sampling from a Probability Distribution of a Restricted Boltzmann Machine

A local-valley (LV) centered approach to assessing the quality of sampling from Restricted Boltzmann Machines (RBMs) was applied to the latest generation of the D-Wave quantum annealer. D-Wave and Gibbs samples from a classically trained RBM were obtained at conditions relevant to the contrastive-divergence-based RBM learning. The samples were compared for the number of the LVs to which they belonged and the energy of the corresponding local minima. No significant (desirable) increase in the number of the LVs has been achieved by decreasing the D-Wave annealing time. At any training epoch, the states sampled by the D-Wave belonged to a somewhat higher number of LVs than in the Gibbs sampling. However, many of those LVs found by the two techniques differed. For high-probability sampled states, the two techniques were (unfavorably) less complementary and more overlapping. Nevertheless, many potentially "important" local minima, i.e., those having intermediate, even if not high, probability values, were found by only one of the two sampling techniques while missed by the other. The two techniques overlapped less at later than earlier training epochs, which is precisely the stage of the training when modest improvements to the sampling quality could make meaningful differences for the RBM trainability. The results of this work may explain the failure of previous investigations to achieve substantial (or any) improvement when using D-Wave-based sampling. However, the results reveal some potential for improvement, e.g., using a combined classical-quantum approach.

Abdelmoula El-Yazizi, Yaroslav Koshka

Department of Electrical and Computer Engineering, Mississippi State University, Starkville, MS 39762, USA

Markov Chain Monte Carlo Quantum Annealing Quantum Machine Learning Unsupervised Representation Learning Restricted Boltzmann Machines

Jul 16, 2025

CoCre-Sam (Kokkuri-san): Modeling Ouija Board as Collective Langevin Dynamics Sampling from Fused Language Models

Collective human activities like using an Ouija board (or Kokkuri-san) often produce emergent, coherent linguistic outputs unintended by any single participant. While psychological explanations such as the ideomotor effect exist, a computational understanding of how decentralized, implicit linguistic knowledge fuses through shared physical interaction remains elusive. We introduce CoCre-Sam (Collective-Creature Sampling), a framework modeling this phenomenon as collective Langevin dynamics sampling from implicitly fused language models. Each participant is represented as an agent associated with an energy landscape derived from an internal language model reflecting linguistic priors, and agents exert stochastic forces based on local energy gradients. We theoretically prove that the collective motion of the shared pointer (planchette) corresponds to Langevin MCMC sampling from the sum of individual energy landscapes, representing fused collective knowledge. Simulations validate that CoCre-Sam dynamics effectively fuse different models and generate meaningful character sequences, while ablation studies confirm the essential roles of collective interaction and stochasticity. Altogether, CoCre-Sam provides a novel computational mechanism linking individual implicit knowledge, embodied collective action, and emergent linguistic phenomena, grounding these complex interactions in the principles of probabilistic sampling.

Tadahiro Taniguchi, Masatoshi Nagano, Haruumi Omoto +1

Graduate School of Informatics, Kyoto University, Japan · Ritsumeikan University, Japan · University of Reading, UK

Emergent Communication Large Language Model-Based Social Simulation Langevin Dynamics Markov Chain Monte Carlo Energy-Based Models

Jul 11, 2025

Last Layer Hamiltonian Monte Carlo

We explore the use of Hamiltonian Monte Carlo (HMC) sampling as a probabilistic last layer approach for deep neural networks (DNNs). While HMC is widely regarded as a gold standard for uncertainty estimation, the computational demands limit its application to large-scale datasets and large DNN architectures. Although the predictions from the sampled DNN parameters can be parallelized, the computational cost still scales linearly with the number of samples (similar to an ensemble). Last layer HMC (LL-HMC) reduces the required computations by restricting the HMC sampling to the final layer of a DNN, making it applicable to more data-intensive scenarios with limited computational resources. In this paper, we compare LL-HMC against five last layer probabilistic deep learning (LL-PDL) methods across three real-world video datasets for driver action and intention. We evaluate the in-distribution classification performance, calibration, and out-of-distribution (OOD) detection. Due to the stochastic nature of the probabilistic evaluations, we performed five grid searches for different random seeds to avoid being reliant on a single initialization for the hyperparameter configurations. The results show that LL-HMC achieves competitive in-distribution classification and OOD detection performance. Additional sampled last layer parameters do not improve the classification performance, but can improve the OOD detection. Multiple chains or starting positions did not yield consistent improvements.

Koen Vellenga, H. Joe Steinhauer, Göran Falkman +2

University of Skövde & Volvo Car Corporation, Sweden · University of Skövde, Sweden · Volvo Car Corporation, Sweden

Bayesian Neural Networks Markov Chain Monte Carlo Uncertainty Quantification OOD Detection

Jun 26, 2025

Gaussian Invariant Markov Chain Monte Carlo

We develop sampling methods, which consist of Gaussian invariant versions of random walk Metropolis (RWM), Metropolis adjusted Langevin algorithm (MALA) and second order Hessian or Manifold MALA. Unlike standard RWM and MALA, we show that Gaussian invariant sampling can lead to ergodic estimators with improved statistical efficiency. This is due to a remarkable property of Gaussian invariance that allows us to obtain exact analytical solutions to the Poisson equation for Gaussian targets. These solutions can be used to construct efficient and easy to use control variates for variance reduction of estimators under any intractable target. We demonstrate the new samplers and estimators in several examples, including high dimensional targets in latent Gaussian models where we compare against several advanced methods and obtain state-of-the-art results. We also provide theoretical results regarding geometric ergodicity, and an optimal scaling analysis that shows the dependence of the optimal acceptance rate on the Gaussianity of the target.

Michalis K. Titsias, Angelos Alexopoulos, Siran Liu +1

Google DeepMind, UK · Athens University of Economics and Business, Greece · UCL, UK

Markov Chain Monte Carlo Variance Reduction

Apr 4, 2025

Quantum Speedups for Sampling and Non-convex Optimization with Stochastic Oracles

We present quantum speedups for sampling from distributions of the form

π\propto e^{-f}

on

\mathbb{R}^d

. We consider two stochastic oracle models: a stochastic gradient oracle, where

f=\frac{1}{n}\sum_{i=1}^n f_i

and component gradients

\{\nabla f_i\}_{i \in [n]}

are available, and a stochastic evaluation oracle, where only noisy values of

f

are available. Our framework accelerates classical stochastic Langevin Monte Carlo (LMC) and Hamiltonian Monte Carlo (HMC) algorithms by replacing stochastic gradient estimators with variance-controlled quantum mean estimation and gradient estimation subroutines. Unlike quantum walk based approaches, our algorithms do not require reversibility or exact gradients, and they preserve the structure of the underlying Markov chain. In the finite-sum setting, quantum mean estimation combined with classical variance-reduction techniques improves the stochastic gradient-query complexity for the approximate sampling task. In the stochastic zeroth-order setting, we develop gradient estimators robust to noisy function evaluations, yielding improved evaluation complexity for LMC and HMC. These results apply to strongly log-concave and/or non-log-concave distributions satisfying a log-Sobolev inequality, with convergence guarantees in Wasserstein distance and Kullback--Leibler divergence. We also show that faster sampling methods lead to quantum speedups for optimization, including for non-smooth and approximately convex objectives.

Guneykan Ozgul, Xiantao Li, Mehrdad Mahdavi +1

Department of Computer Science and Engineering, Pennsylvania State University, University Park, PA, USA · Department of Mathematics, Pennsylvania State University, University Park, PA, USA

Markov Chain Monte Carlo Stochastic Gradient Langevin Dynamics Nonconvex Optimization

Jun 25, 2024

Variance Reduction for Independent Metropolis

Assume that we would like to estimate the expected value of a function

F

with respect to an intractable density

π

, which is specified up to some unknown normalising constant. We prove that if

π

is close enough under KL divergence to another density

q

, an independent Metropolis sampler estimator that obtains samples from

π

with proposal density

q

, enriched with a variance reduction computational strategy based on control variates, achieves smaller asymptotic variance than i.i.d. sampling from

π

. The control variates construction requires no extra computational effort but assumes that the expected value of

F

under

q

is analytically available. We illustrate this result by calculating the marginal likelihood in a linear regression model with prior-likelihood conflict and a non-conjugate prior. Furthermore, we propose an adaptive independent Metropolis algorithm that adapts the proposal density such that its KL divergence with the target is being reduced. We demonstrate its applicability in a Bayesian logistic and Gaussian process regression problems and we rigorously justify our asymptotic arguments under easily verifiable and essentially minimal conditions.

Siran Liu, Petros Dellaportas, Michalis K. Titsias

Department of Statistical Science, University College London, UK. · Department of Statistics, Athens University of Economics and Business, Greece. · Google DeepMind, UK.

Markov Chain Monte Carlo Variance Reduction

Feb 18, 2024

Monte Carlo with kernel-based Gibbs measures: Guarantees for probabilistic herding

Kernel herding belongs to a family of deterministic quadratures that seek to minimize the maximum mean discrepancy (MMD), that is, the worst-case integration error over a reproducing kernel Hilbert space (RKHS). These MMD minimization procedures come with strong experimental support, but comparatively less theoretical footing. In particular, apart from recent progress in distribution compression, little has been proved in favor of an improvement of MMD minimization over classical Monte Carlo quadrature when the RKHS is infinite-dimensional. In this paper, we study a joint probability distribution over quadrature nodes, a tailored Gibbs distribution, whose support intuitively tends to concentrate around MMD minimizers as a temperature parameter is decreased. Our main contribution is to prove that drawing integration nodes from our distribution does outperform i.i.d Monte Carlo. While our bounds on the worst-case integration error feature the same rate as i.i.d. Monte Carlo, we do obtain a tighter concentration inequality as the temperature parameter decreases. This means smaller confidence intervals as the number of quadrature nodes increases. While arguably a first step, our results demonstrate that the mathematical toolbox developed around Gibbs measures can help understand to what extent kernel herding and its variants improve on computationally cheaper methods. There remains the issue of sampling from our Gibbs distribution. In our numerical experiments, we demonstrate that a simple MCMC chain already yields approximate samples that lead to improved confidence intervals around the target integrals, as supported by our theoretical results.

Martin Rouault, Rémi Bardenet, Mylène Maïda

1Univ. Lille, CNRS, Centrale Lille, UMR 9189 – CRIStAL, 59651 Villeneuve d’Ascq, France · 2Univ. Lille, CNRS, UMR 8524 – Laboratoire Paul Painlev´e, F-59000 Lille, France

Markov Chain Monte Carlo Maximum Mean Discrepancy