Automatic Rao-Blackwellization for Sequential Monte Carlo with Belief Propagation

• URL: http://arxiv.org/abs/2312.09860v1
• Date: Fri, 15 Dec 2023 15:05:25 GMT
• Title: Automatic Rao-Blackwellization for Sequential Monte Carlo with Belief Propagation
• Authors: Wa\"iss Azizian, Guillaume Baudart, Marc Lelarge
• Abstract summary: Exact Bayesian inference on state-space models(SSM) is in general untractable. We propose a mixed inference algorithm that computes closed-form solutions using belief propagation as much as possible.
• Score: 4.956977275061968
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Exact Bayesian inference on state-space models~(SSM) is in general untractable, and unfortunately, basic Sequential Monte Carlo~(SMC) methods do not yield correct approximations for complex models. In this paper, we propose a mixed inference algorithm that computes closed-form solutions using belief propagation as much as possible, and falls back to sampling-based SMC methods when exact computations fail. This algorithm thus implements automatic Rao-Blackwellization and is even exact for Gaussian tree models.

Related papers

• 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)
• 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)
• 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)
• Interfacing branching random walks with Metropolis sampling: constraint release in auxiliary-field quantum Monte Carlo [8.618234453116251]
  We present an approach to interface branching random walks with Markov chain Monte Carlo sampling. We use the generalized Metropolis algorithm to sample a selected portion of the imaginary-time path after it has been produced by the branching random walk.
  arXiv  Detail & Related papers  (2023-05-16T16:12:56Z)
• Langevin Monte Carlo for Contextual Bandits [72.00524614312002]
  Langevin Monte Carlo Thompson Sampling (LMC-TS) is proposed to directly sample from the posterior distribution in contextual bandits. We prove that the proposed algorithm achieves the same sublinear regret bound as the best Thompson sampling algorithms for a special case of contextual bandits.
  arXiv  Detail & Related papers  (2022-06-22T17:58:23Z)
• 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)
• Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
  We consider the problem of learning the optimal policy for infinite-horizon Markov decision processes (MDPs) Some variant of Mirror Descent is proposed for convex programming problems with Lipschitz-continuous functionals. We analyze this algorithm in a general case and obtain an estimate of the convergence rate that does not accumulate errors during the operation of the method.
  arXiv  Detail & Related papers  (2021-02-27T19:28:39Z)
• Plug-And-Play Learned Gaussian-mixture Approximate Message Passing [71.74028918819046]
  We propose a plug-and-play compressed sensing (CS) recovery algorithm suitable for any i.i.d. source prior. Our algorithm builds upon Borgerding's learned AMP (LAMP), yet significantly improves it by adopting a universal denoising function within the algorithm. Numerical evaluation shows that the L-GM-AMP algorithm achieves state-of-the-art performance without any knowledge of the source prior.
  arXiv  Detail & Related papers  (2020-11-18T16:40:45Z)
• An adaptive Hessian approximated stochastic gradient MCMC method [12.93317525451798]
  We present an adaptive Hessian approximated gradient MCMC method to incorporate local geometric information while sampling from the posterior. We adopt a magnitude-based weight pruning method to enforce the sparsity of the network.
  arXiv  Detail & Related papers  (2020-10-03T16:22:15Z)
• On the Convergence of Reinforcement Learning with Monte Carlo Exploring Starts [5.137144629366217]
  A basic simulation-based reinforcement learning algorithm is the Monte Carlo Exploring States (MCES) method. We investigate the convergence of this algorithm for the case with undiscounted costs, also known as the shortest path problem. As a side result, we also provide a proof of a version of the supermartingale convergence theorem commonly used in approximation.
  arXiv  Detail & Related papers  (2020-07-21T16:19:09Z)
• Connecting the Dots: Numerical Randomized Hamiltonian Monte Carlo with State-Dependent Event Rates [0.0]
  We introduce a robust, easy to use and computationally fast alternative to conventional Markov chain Monte Carlo methods for continuous target distributions. The proposed algorithm may yield large speedups and improvements in stability relative to relevant benchmarks. Granted access to a high-quality ODE code, the proposed methodology is both easy to implement and use, even for highly challenging and high-dimensional target distributions.
  arXiv  Detail & Related papers  (2020-05-04T06:23:13Z)

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.