Exact and Approximate MCMC for Doubly-intractable Probabilistic Graphical Models Leveraging the Underlying Independence Model

• URL: http://arxiv.org/abs/2510.03587v1
• Date: Sat, 04 Oct 2025 00:34:25 GMT
• Title: Exact and Approximate MCMC for Doubly-intractable Probabilistic Graphical Models Leveraging the Underlying Independence Model
• Authors: Yujie Chen, Antik Chakraborty, Anindya Bhadra,
• Abstract summary: We develop a method that does not require perfect or sequential sampling, and can be applied to both classes of methods: exact and approximate MCMC.<n>The innovation turns out to be crucial for scalability in high dimensions.
• Score: 11.347301021078438
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Bayesian inference for doubly-intractable probabilistic graphical models typically involves variations of the exchange algorithm or approximate Markov chain Monte Carlo (MCMC) samplers. However, existing methods for both classes of algorithms require either perfect samplers or sequential samplers for complex models, which are often either not available, or suffer from poor mixing, especially in high dimensions. We develop a method that does not require perfect or sequential sampling, and can be applied to both classes of methods: exact and approximate MCMC. The key to our approach is to utilize the tractable independence model underlying an intractable probabilistic graphical model for the purpose of constructing a finite sample unbiased Monte Carlo (and not MCMC) estimate of the Metropolis--Hastings ratio. This innovation turns out to be crucial for scalability in high dimensions. The method is demonstrated on the Ising model. Gradient-based alternatives to construct a proposal, such as Langevin and Hamiltonian Monte Carlo approaches, also arise as a natural corollary to our general procedure, and are demonstrated as well.

Related papers

• FBMS: An R Package for Flexible Bayesian Model Selection and Model Averaging [14.487258585834374]
  The FBMS package implements an efficient Mode Jumping Markov Chain Monte Carlo (MJMCMC) algorithm.<n>Within this framework, the algorithm maintains and updates populations of transformed features, computes their posterior probabilities, and evaluates the posteriors of models constructed from them.<n>We demonstrate the effective use of FBMS for both inferential and predictive modeling in Gaussian regression, focusing on different instances of the BGNLM class of models.
  arXiv  Detail & Related papers  (2025-08-31T09:04:01Z)
• Online Variational Sequential Monte Carlo [49.97673761305336]
  We build upon the variational sequential Monte Carlo (VSMC) method, which provides computationally efficient and accurate model parameter estimation and Bayesian latent-state inference. Online VSMC is capable of performing efficiently, entirely on-the-fly, both parameter estimation and particle proposal adaptation.
  arXiv  Detail & Related papers  (2023-12-19T21:45:38Z)
• Accelerating Markov Chain Monte Carlo sampling with diffusion models [0.0]
  We introduce a novel method for accelerating Markov Chain Monte Carlo (MCMC) sampling by pairing a Metropolis-Hastings algorithm with a diffusion model. We briefly review diffusion models in the context of image synthesis before providing a streamlined diffusion model tailored towards low-dimensional data arrays. Our approach leads to a significant reduction in the number of likelihood evaluations required to obtain an accurate representation of the posterior.
  arXiv  Detail & Related papers  (2023-09-04T09:03:41Z)
• Differentiating Metropolis-Hastings to Optimize Intractable Densities [51.16801956665228]
  We develop an algorithm for automatic differentiation of Metropolis-Hastings samplers. We apply gradient-based optimization to objectives expressed as expectations over intractable target densities.
  arXiv  Detail & Related papers  (2023-06-13T17:56:02Z)
• Automatically Marginalized MCMC in Probabilistic Programming [12.421267523795114]
  Hamiltonian Monte Carlo (HMC) is a powerful algorithm to sample latent variables from Bayesian models. We propose to use automatic marginalization as part of the sampling process using HMC in a graphical model extracted from a PPL.
  arXiv  Detail & Related papers  (2023-02-01T16:34:07Z)
• Low-variance estimation in the Plackett-Luce model via quasi-Monte Carlo sampling [58.14878401145309]
  We develop a novel approach to producing more sample-efficient estimators of expectations in the PL model. We illustrate our findings both theoretically and empirically using real-world recommendation data from Amazon Music and the Yahoo learning-to-rank challenge.
  arXiv  Detail & Related papers  (2022-05-12T11:15:47Z)
• MCCE: Monte Carlo sampling of realistic counterfactual explanations [2.156170153103442]
  MCCE is a novel on-manifold, actionable and valid counterfactual explanation method. It generates on-manifold, actionable and valid counterfactuals by modeling the joint distribution of the mutable features. We compare MCCE with a range of state-of-the-art on-manifold counterfactual methods using four well-known data sets.
  arXiv  Detail & Related papers  (2021-11-18T16:40:44Z)
• Sampling from Arbitrary Functions via PSD Models [55.41644538483948]
  We take a two-step approach by first modeling the probability distribution and then sampling from that model. We show that these models can approximate a large class of densities concisely using few evaluations, and present a simple algorithm to effectively sample from these models.
  arXiv  Detail & Related papers  (2021-10-20T12:25:22Z)
• PSD Representations for Effective Probability Models [117.35298398434628]
  We show that a recently proposed class of positive semi-definite (PSD) models for non-negative functions is particularly suited to this end. We characterize both approximation and generalization capabilities of PSD models, showing that they enjoy strong theoretical guarantees. Our results open the way to applications of PSD models to density estimation, decision theory and inference.
  arXiv  Detail & Related papers  (2021-06-30T15:13:39Z)
• 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)
• Community Detection in the Stochastic Block Model by Mixed Integer Programming [3.8073142980733]
  Degree-Corrected Block Model (DCSBM) is a popular model to generate random graphs with community structure given an expected degree sequence. Standard approach of community detection based on the DCSBM is to search for the model parameters that are the most likely to have produced the observed network data through maximum likelihood estimation (MLE) We present mathematical programming formulations and exact solution methods that can provably find the model parameters and community assignments of maximum likelihood given an observed graph.
  arXiv  Detail & Related papers  (2021-01-26T22:04:40Z)
• Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
  We adapt an algorithm of Klivans and Meka based on the method of multiplicative weight updates. The algorithm enjoys a sample complexity bound that is qualitatively similar to others in the literature. It has a low runtime $O(mp2)$ in the case of $m$ samples and $p$ nodes, and can trivially be implemented in an online manner.
  arXiv  Detail & Related papers  (2020-02-20T10:50:58Z)

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.