🚀 go-pugleaf

In article <1992Oct4.192217.27919@news2.cis.umn.edu> charlie@umnstat.stat.umn.edu (Charles Geyer) writes:

>> ... Simulated annealing
>> is a technique that can be used in conjunction with Gibbs sampling 
>> (or other Markov chain methods, such as the Metropolis algorithm) 
>> in order to reach the final equilibrium distribution more quickly.
>
>Depends on how you think about Markov chain Monte Carlo.  The
>Metropolis-Hastings algorithm produces a Markov chain with a known
>stationary distribution.  This "annealing trick" doesn't.  So far
>from mixing MCMC and simulated annealing, it is not MCMC at all.

Perhaps I wasn't clear. 

The technique consists (in its simplest form) of splitting the
simulation up into several phases, each associated with a certain
"temperature", T. These temperatures decline, starting at a high
value, and ending at T=1. In each phase, a Markov chain that has an
equilibrium distribution proportional to P(x)^(1/T) is simulated,
where P(x) is the distribution we wish to sample from. The start state
for each phase is the final state from the previous phase.

Once a temperature of one is reached, or perhaps a bit later, one
starts using the states visited by this final chain (with T=1) to
calculate expectations with respect to the distribution given by
P(x). 

This procedure has as much, and as little, formal justification as
simply running a chain that has P(x) as its invariant distribution for
the same number of total steps before using the states to compute
expectations.  


>Are there any practically useful convergence results for such schemes
>once Markov chain theory is thrown out the window?

One doesn't throw Markov chain theory out the window, one simply
recognizes its limiations.

Generally, the easily obtainable bounds on convergence of the Markov
chain methods when applied to interesting problems do not justify
their practical use. It is indeed nice to know that convergence is
guaranteed asymptotically, but the warm feelings this gives are
equally available to those using annealing, since the annealing
phases, where T>1, occupy only a finite initial portion of the chain.
In practice, one is relying on intuition and empirical experience with
similar problems in the past, along with the knowledge that there
aren't any better techniques, so what else is one to do?

Empirically, the annealing procedure is often found to give better
convergence than just starting at T=1. There are no generally
applicable formal results. It is easy to construct problems for which
annealing makes things worse, and for which, in fact, it is better to
start at a temperature _less_ than one and gradually warm up to T=1.
However, deciding to do the whole simulation at T=1 is just as much
an "act of faith" as is using some annealing schedule.

    Radford Neal