15
$\begingroup$

Random walk Metropolis-Hasitings with symmetric proposal

$q(x|y)= g(|y-x|)$ has the property that the acceptance probability

$$P(accept\ y) = \min\{1, f(y)/f(x)\}$$

does not depend on proposal $g(\cdot)$.

Does that mean that I can change the $g(\cdot)$ as a function of previous performance of the chain, without affecting the markovianity of the chain?

Of particular interest to me is the adjustment of the scaling of Normal proposal as a function of acceptance rate.

Would also greatly appreciate if someone can point out to the adaptation algorithms used in practice for this type of problem.

Many thanks.

[edit: Starting with the references given by robertsy and wok I found the following references on MH adaptive algorithms:

Andrieu, Christophe, and Éric Moulines. 2006.
On the Ergodicity Properties of Some Adaptive MCMC Algorithms. The Annals of Applied Probability 16, no. 3: 1462-1505. http://www.jstor.org/stable/25442804.

Andrieu, Christophe, and Johannes Thoms.
2008. A tutorial on adaptive MCMC. Statistics and Computing 18, no. 4 (12): 343-373. doi:10.1007/s11222-008-9110-y. Link.

Atchadé, Y., G. Fort, E. Moulines, and P. Priouret. 2009.
Adaptive Markov Chain Monte Carlo: Theory and Methods. Preprint.

Atchadé, Yves. 2010.
Limit theorems for some adaptive MCMC algorithms with subgeometric kernels. Bernoulli 16, no. 1 (February): 116-154. doi:10.3150/09-BEJ199. Link.

Cappé, O., S. J Godsill, and E. Moulines. 2007.
An overview of existing methods and recent advances in sequential Monte Carlo. Proceedings of the IEEE 95, no. 5: 899-924.

Giordani, Paolo. 2010.
Adaptive Independent Metropolis–Hastings by Fast Estimation of Mixtures of Normals. Journal of Computational and Graphical Statistics 19, no. 2 (6): 243-259. doi:10.1198/jcgs.2009.07174. http://pubs.amstat.org/doi/abs/10.1198/jcgs.2009.07174.

Latuszynski, Krzysztof, Gareth O Roberts, and Jeffrey S Rosenthal. 2011.
Adaptive Gibbs samplers and related MCMC methods. 1101.5838 (January 30). http://arxiv.org/abs/1101.5838.

Pasarica, C., and A. Gelman. 2009.
Adaptively scaling the Metropolis algorithm using expected squared jumped distance. Statistica Sinica.

Roberts, Gareth O. 2009.
Examples of Adaptive MCMC. Journal of Computational and Graphical Statistics 18, no. 2 (6): 349-367. doi:10.1198/jcgs.2009.06134. http://pubs.amstat.org/doi/abs/10.1198/jcgs.2009.06134.

]

Improve this question
$\endgroup$
3
  • $\begingroup$ How come you don't have +100 bonus from your SO record? $\endgroup$
    – user88
    Commented Feb 16, 2011 at 10:57
  • $\begingroup$ @mbq, probably because I created this account long ago when I was 0 on OS as well...pity, 100 on CW looks like a big deal, since you must be a real chap to answer stuff in here :) $\endgroup$
    – VitoshKa
    Commented Feb 16, 2011 at 11:11
  • $\begingroup$ You can get the bonus by clearing all associations and then associating accounts again. $\endgroup$
    – Wok
    Commented Feb 16, 2011 at 15:37

4 Answers 4

Reset to default
7
$\begingroup$

I think that this paper from Heikki Haario et al. will give you the answer you need. The markovianity of the chain is affected by the adaptation of the proposal density, because then a new proposed value depends not only of the previous one but on the whole chain. But it seems that the sequence has still the good properties if great care is taken.

Improve this answer
$\endgroup$
1
  • $\begingroup$ thanks robertsy, for good reference. indeed the process is not markov. Even if acceptance probability is independent of the past, the transition kernel of the process is a function of the proposal density and thus depends on the whole chain. $\endgroup$
    – VitoshKa
    Commented Feb 16, 2011 at 16:07
3
$\begingroup$

You can improve the acceptance rate using delayed rejection as described in Tierney, Mira (1999). It is based on a second proposal function and a second acceptance probability, which guarantees the Markov chain is still reversible with the same invariant distribution: you have to be cautious since "it is easy to construct adaptive methods that might seem to work but in fact sample from the wrong distribution".

Improve this answer
$\endgroup$
3
$\begingroup$

The approaches suggested by users wok and robertsy cover the most commonly cited examples of what you're looking for that I know of. Just to expand on those answers, Haario and Mira wrote a paper in 2006 that combines the two approaches, an approach they call DRAM (delayed rejection adaptive Metropolis).

Andrieu has a nice treatment of various different adaptive MCMC approaches (pdf) which covers Haario 2001 but also discusses various alternatives that have been proposed in recent years.

Improve this answer
$\endgroup$
1
$\begingroup$

This is a bit of a shameless plug of a publication of mine, but we do exactly this in this work (arxiv). Amongst other things, we propose adapting the variance of the exponential distribution to improve the acceptance (step S3.2 in algorithm in the paper).

In our case, asymptotically the adaptation does not change the proposal distribution (which in the paper is when $f \rightarrow 1$). Thus, asymptotically, the process is still Markovian in the same spirit as the Wang-Landau algorithm. We numerically verify that the process is ergodic and the chain samples from the target distribution we choose (e.g. left bottom panel of Fig. 4).

We don't use information about the acceptance rate, but we obtain an acceptance independent of the quantity we are interested in (equivalent to the energy of a spin system, bottom-right of Fig. 4).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.