(L) [2015/03/27] [ost
by Paleos] [Useful Markov Chain Monte Carlo Papers to apply to Graphics] Wayback!Here are some Useful Markov Chain Monte Carlo papers that
I have come across when surfing the web, that I think have use in Metropolis Light Transport(MLT) Implementations
A general construction for parallelizing Metropolis−Hastings
This is a [LINK http://www.pnas.org/content/111/49/17408.full.pdf paper] for augmenting metropolis sampling with multiple proposals in a way that,
as opposed to earlier approaches such as multiple try metropolis and prefetching,
does not discard all but one of the proposals in one iteration.
Adaptive Markov Chain Monte Carlo
Adaptive Markov Chain Monte Carlo(AMCMC) methods adapt the parameters(usually those of the proposal distribution)
of the sampler to achieve an ideal acceptance ratio.
Exploring an Adaptive Metropolis Algorithm
This is a [LINK http://www.personal.psu.edu/bas59/papers/adaptive_techreport.pdf paper] on adapting the step size on a logarithmic scale,
which allows it to find a step size that fulfills the target acceptance ratio much faster than adapting the step size directly.
ROBUST ADAPTIVE METROPOLIS ALGORITHM WITH
COERCED ACCEPTANCE RATE
This [LINK http://www.stats.ox.ac.uk/~mvihola/vihola_-_ram.pdf paper] introduces a new
robust adaptive Metropolis algorithm estimating the shape of the target distribution and simultaneously coercing the acceptance rate.
Kernel Adaptive Metropolis-Hastings
A [LINK http://jmlr.org/proceedings/papers/v32/sejdinovic14.pdf Kernel Adaptive Metropolis-Hastings algorithm] is introduced, for the purpose of sampling
from a target distribution with strongly nonlinear support. The algorithm embeds the trajectory of the Markov chain into a reproducing kernel Hilbert space (RKHS), such that the feature space covariance of the samples informs
the choice of proposal. The procedure is computationally efficient and straightforward to implement, since the RKHS moves can be integrated out analytically: our proposal distribution in the original space is a normal distribution
whose mean and covariance depend on where the current sample lies in the support of the target distribution, and adapts to its local covariance structure.
[LINK https://github.com/karlnapf/kameleon-mcmc Link] to example code
Adaptive Metropolis Algorithm Using Variational
Bayesian Adaptive Kalman Filter
A new adaptive MCMC algorithm, called the [LINK http://arxiv.org/pdf/1308.5875 variational Bayesian
adaptive Metropolis] (VBAM) algorithm, is developed. The VBAM algorithm
updates the proposal covariance matrix using the variational Bayesian adaptive
Kalman filter (VB-AKF). A strong law of large numbers for the VBAM algorithm
is proven. The empirical convergence results for three simulated examples and for
two real data examples are also provided.
DRAM: Efficient adaptive MCMC
We [LINK http://www.math.helsinki.fi/reports/Preprint374.pdf propose] to combine two quite powerful ideas
that have recently appeared in the Markov chain Monte Carlo
literature: adaptive Metropolis samplers and delayed rejec-
tion. The ergodicity of the resulting non-Markovian sampler
is proved, and the efficiency of the combination is demon-
strated with various examples. We present situations where
the combination outperforms the original methods: adap-
tation clearly enhances efficiency of the delayed rejection
algorithm in cases where good proposal distributions are
not available. Similarly, delayed rejection provides a sys-
tematic remedy when the adaptation process has a slow
start.
[LINK http://helios.fmi.fi/~lainema/dram/ web page]
Learn From Thy Neighbor: Parallel-Chain and
Regional Adaptive MCMC
Starting with the seminal paper of Haario, Saksman and Tamminen (Haario
et al. (2001)), a substantial amount of work has been done to validate adaptive
Markov chain Monte Carlo algorithms. In this [LINK http://probability.ca/jeff/ftpdir/chao4.pdf paper] we focus on two practi-
cal aspects of adaptive Metropolis samplers. First, we draw attention to the
deficient performance of standard adaptation when the target distribution is
multi-modal. We propose a parallel chain adaptation strategy that incorpo-
rates multiple Markov chains which are run in parallel. Second, we note that
the current adaptive MCMC paradigm implicitly assumes that the adaptation is
uniformly efficient on all regions of the state space. However, in many practical
instances, different “optimal” kernels are needed in different regions of the state
space. We propose here a regional adaptation algorithm in which we account
for possible errors made in defining the adaptation regions.
[LINK http://www.utstat.toronto.edu/craiu/Talks/slides-ubc.pdf Slides]
Delayed Rejection
Delayed rejection schemes for efficient Markov-Chain Monte-Carlo
sampling of multimodal distributions
A number of problems in a variety of fields are characterised by target dis-
tributions with a multimodal structure in which the presence of several isolated
local maxima dramatically reduces the efficiency of Markov chain Monte Carlo
sampling algorithms. Several solutions, such as simulated tempering or the use
of parallel chains, have been proposed to facilitate the exploration of the relevant
parameter space. They provide effective strategies in the cases in which the di-
mension of the parameter space is small and/or the computational costs are not
a limiting factor. These approaches fail however in the case of high-dimensional
spaces where the multimodal structure is induced by degeneracies between re-
gions of the parameter space. In this [LINK http://arxiv.org/pdf/0904.2207v2 paper] we present a fully Markovian way
to efficiently sample this kind of distribution based on the general Delayed Re-
jection scheme with an arbitrary number of steps, and provide details for an
efficient numerical implementation of the algorithm.
Markov Chain Quasi Monte Carlo
Markov Chain Quasi Monte Carlo(MCQMC) methods reformulate Markov Chain Monte Carlo methods
to allow for the use of low discrepancy sequences instead of a pseudo-random number generator(PRNG).
Discrepancy bounds for uniformly ergodic
Markov chain quasi-Monte Carlo
In [Chen, D., Owen, Ann. Stat., 39, 673–701, 2011] Markov chain
Monte Carlo (MCMC) was studied under the assumption that the
driver sequence is a deterministic sequence rather than independent
U (0, 1) random variables. Therein it was shown that as long as the
driver sequence is completely uniformly distributed, the Markov chain
consistently samples the target distribution. The [LINK http://arxiv.org/pdf/1303.2423v2 present work] extends
these results by providing bounds on the convergence rate of the dis-
crepancy between the empirical distribution of the Markov chain and
the target distribution, under the assumption that the Markov chain
is uniformly ergodic.
In a general setting we show the existence of driver sequences for
which the discrepancy of the Markov chain from the target distribution
with respect to certain test sets converges with (almost) the usual
Monte Carlo rate of n^−1/2 .
CONSISTENCY AND CONVERGENCE RATE OF MARKOV
CHAIN QUASI MONTE CARLO WITH EXAMPLES
Markov Chain Monte Carlo methods have been widely used in various science areas
for generation of samples from distributions that are difficult to simulate directly.
The random numbers driving Markov Chain Monte Carlo algorithms are modeled
as independent U[0, 1) random variables. By constructing a Markov Chain, we are
able to sample from its stationary distribution if irreducibility and Harris recurrence
conditions are satisfied. The class of distributions that could be simulated are largely
broadened by using Markov Chain Monte Carlo.
Quasi-Monte Carlo, on the other hand, aims to improve the accuracy of estimation
of an integral over the unit cube [0, 1)k . By using more carefully balanced inputs,
under some smoothness conditions the estimation error can be shown to converge at a
speed of O(log^k n/n), while the plain Monte Carlo method can only give a convergence
rate of Op(1/√n).
The improvement is significant when n is large.
In other words, Markov Chain Monte Carlo is creating a larger world, and quasi-
Monte Carlo is creating a better world. Ideally we would like to combine these two
techniques, so that we can sample more accurately from a larger class of distributions.
This method, called Markov Chain quasi-Monte Carlo (MCQMC), is the main topic
of this [LINK http://statweb.stanford.edu/~owen/students/SuChenThesis.pdf work].
MARKOV CHAIN MONTE CARLO ALGORITHMS USING
COMPLETELY UNIFORMLY DISTRIBUTED DRIVING
SEQUENCES
The advantage of low-discrepancy sequences in lieu of random numbers for simple
independent Monte Carlo sampling is well-known. This procedure, known as quasi-
Monte Carlo (QMC), yields an integration error that decays at a superior rate to
that obtained by IID sampling, by the Koksma-Hlawka inequality. For the class of
Markov chain Monte Carlo (MCMC) samplers, little literature has been produced
examining the use of low-discrepancy sequences, and previous experiments have of-
fered no theoretical validation for this practice. The central result in this [LINK http://statweb.stanford.edu/~owen/students/SethTribbleThesis.pdf work] is
the establishment of conditions under which low-discrepancy sequences can be used
for consistent MCMC estimation. This condition of completely uniform distribution
(CUD) applies to a series of sequences that look like full outputs of a small random
number generator. A strategy for the incorporation of these sequences into a general
MCMC sampling scheme is thoroughly developed here, with attention to the preser-
vation of the CUD condition. The use of these sequences in a few MCMC examples
shows reductions in estimate error that are most significant in Gibbs samplers. From
these examples, the empirical benefits of CUD sequences in MCMC sampling are im-
mense, although no analog of the Koksma-Hlawka inequality has been produced for
MCMC to provide a general theoretical corroboration of these improvements.
A Quasi-Monte Carlo Metropolis
Algorithm
This [LINK http://statweb.stanford.edu/~owen/reports/qmcmcmc.pdf paper] presents a version of the Metropolis-Hastings algorithm using quasi-Monte Carlo inputs. We prove that the
method yields consistent estimates in some problems with
finite state spaces and completely uniformly distributed in-
puts. In some numerical examples, the proposed method is
much more accurate than ordinary Metropolis-Hastings sampling.
Interacting Markov Chain Monte Carlo
Parallel hierarchical sampling: a general-purpose
class of multiple-chains MCMC algorithms
This [LINK http://wrap.warwick.ac.uk/35224/1/WRAP_Rigat_09-37v2w.pdf paper] introduces the Parallel Hierarchical Sampler (PHS), a
class of Markov chain Monte Carlo algorithms using several interact-
ing chains having the same target distribution but different mixing
properties.