Session A7 - Stochastic Computation - Semi-plenary talk
July 11, 15:30 ~ 16:20 - Room B2
Competing sources of variance reduction in parallel replica Monte Carlo, and optimization in the low temperature limit
Brown University, USA - email@example.com
Computational methods such as parallel tempering and replica exchange are designed to speed convergence of more slowly converging Markov processes (corresponding to lower temperatures for models from the physical sciences), by coupling them through a Metropolis type swap mechanism with higher temperature processes that explore the state space more quickly. It has been shown that the sampling properties are in a certain sense optimized by letting the swap rate tend to infinity. This ``infinite swapping limit'' can be realized in terms of a process which evolves using a symmetrized version of the original dynamics, and then one produces approximations to the original problem by using a weighted empirical measure. The weights are needed to transform samples obtained under the symmetrized dynamics into distributionally correct samples for the original problem.
After reviewing the construction of the infinite swapping limit, we focus on the sources of variance reduction which follow from this construction. As will be discussed, some variance reduction follows from a lowering of energy barriers and consequent improved communication properties. A second and less obvious source of variance reduction is due to the weights used in the weighted empirical measure that appropriately transform the samples of the symmetrized process. These weights are analogous to the likelihood ratios that appear in importance sampling, and play much the same role in reducing the overall variance. A key question in the design of the algorithms is how to choose the ratios of the higher temperatures to the lowest one. As we will discuss, the two variance reduction mechanisms respond in opposite ways to changes in these ratios. One can characterize in precise terms the tradeoff and explicitly identify the optimal temperature selection for certain models when the lowest temperature is sent to zero, i.e., when sampling is most difficult.
Joint work with Jim Doll, Guo-Jhen Wu and Michael Snarski (Brown University, USA).