LSB: Local Self-Balancing MCMC in Discrete Spaces
- URL: http://arxiv.org/abs/2109.03867v1
- Date: Wed, 8 Sep 2021 18:31:26 GMT
- Title: LSB: Local Self-Balancing MCMC in Discrete Spaces
- Authors: Emanuele Sansone
- Abstract summary: This work considers using machine learning to adapt the proposal distribution to the target, in order to improve the sampling efficiency in the purely discrete domain.
We call the resulting sampler as the Locally Self-Balancing Sampler (LSB)
- Score: 2.385916960125935
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Markov Chain Monte Carlo (MCMC) methods are promising solutions to sample
from target distributions in high dimensions. While MCMC methods enjoy nice
theoretical properties, like guaranteed convergence and mixing to the true
target, in practice their sampling efficiency depends on the choice of the
proposal distribution and the target at hand. This work considers using machine
learning to adapt the proposal distribution to the target, in order to improve
the sampling efficiency in the purely discrete domain. Specifically, (i) it
proposes a new parametrization for a family of proposal distributions, called
locally balanced proposals, (ii) it defines an objective function based on
mutual information and (iii) it devises a learning procedure to adapt the
parameters of the proposal to the target, thus achieving fast convergence and
fast mixing. We call the resulting sampler as the Locally Self-Balancing
Sampler (LSB). We show through experimental analysis on the Ising model and
Bayesian networks that LSB is indeed able to improve the efficiency over a
state-of-the-art sampler based on locally balanced proposals, thus reducing the
number of iterations required to converge, while achieving comparable mixing
performance.
Related papers
- Distributed Markov Chain Monte Carlo Sampling based on the Alternating
Direction Method of Multipliers [143.6249073384419]
In this paper, we propose a distributed sampling scheme based on the alternating direction method of multipliers.
We provide both theoretical guarantees of our algorithm's convergence and experimental evidence of its superiority to the state-of-the-art.
In simulation, we deploy our algorithm on linear and logistic regression tasks and illustrate its fast convergence compared to existing gradient-based methods.
arXiv Detail & Related papers (2024-01-29T02:08:40Z) - Adaptive importance sampling for heavy-tailed distributions via
$\alpha$-divergence minimization [2.879807093604632]
We propose an AIS algorithm that approximates the target by Student-t proposal distributions.
We adapt location and scale parameters by matching the escort moments of the target and the proposal.
These updates minimize the $alpha$-divergence between the target and the proposal, thereby connecting with variational inference.
arXiv Detail & Related papers (2023-10-25T14:07:08Z) - 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) - Optimization of Annealed Importance Sampling Hyperparameters [77.34726150561087]
Annealed Importance Sampling (AIS) is a popular algorithm used to estimates the intractable marginal likelihood of deep generative models.
We present a parameteric AIS process with flexible intermediary distributions and optimize the bridging distributions to use fewer number of steps for sampling.
We assess the performance of our optimized AIS for marginal likelihood estimation of deep generative models and compare it to other estimators.
arXiv Detail & Related papers (2022-09-27T07:58:25Z) - Optimal Scaling for Locally Balanced Proposals in Discrete Spaces [65.14092237705476]
We show that efficiency of Metropolis-Hastings (M-H) algorithms in discrete spaces can be characterized by an acceptance rate that is independent of the target distribution.
Knowledge of the optimal acceptance rate allows one to automatically tune the neighborhood size of a proposal distribution in a discrete space, directly analogous to step-size control in continuous spaces.
arXiv Detail & Related papers (2022-09-16T22:09:53Z) - 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) - Sampling from Discrete Energy-Based Models with Quality/Efficiency
Trade-offs [3.491202838583993]
Energy-Based Models (EBMs) allow for extremely flexible specifications of probability distributions.
They do not provide a mechanism for obtaining exact samples from these distributions.
We propose a new approximate sampling technique, Quasi Rejection Sampling (QRS), that allows for a trade-off between sampling efficiency and sampling quality.
arXiv Detail & Related papers (2021-12-10T17:51:37Z) - Variational Refinement for Importance Sampling Using the Forward
Kullback-Leibler Divergence [77.06203118175335]
Variational Inference (VI) is a popular alternative to exact sampling in Bayesian inference.
Importance sampling (IS) is often used to fine-tune and de-bias the estimates of approximate Bayesian inference procedures.
We propose a novel combination of optimization and sampling techniques for approximate Bayesian inference.
arXiv Detail & Related papers (2021-06-30T11:00:24Z) - Simpler Certified Radius Maximization by Propagating Covariances [39.851641822878996]
We show an algorithm for maximizing the certified radius on datasets including Cifar-10, ImageNet, and Places365.
We show how satisfying these criteria yields an algorithm for maximizing the certified radius on datasets with moderate depth, with a small compromise in overall accuracy.
arXiv Detail & Related papers (2021-04-13T01:38:36Z) - A Neural Network MCMC sampler that maximizes Proposal Entropy [3.4698840925433765]
Augmenting samplers with neural networks can potentially improve their efficiency.
Our network architecture utilizes the gradient of the target distribution for generating proposals.
The adaptive sampler achieves unbiased sampling with significantly higher proposal entropy than Langevin dynamics sampler.
arXiv Detail & Related papers (2020-10-07T18:01:38Z)
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.