Fast approximation algorithms for partition functions of Gibbs distributions


Mark Huber, Claremont McKenna College


Eighteenth Avenue Building, Room 170


Abstract: Finding the partition function of Gibbs distributions has applications in model selection and building estimators for parameters of spatial models. This talk will present a new algorithm for estimating these partition functions. The method combines a well balanced cooling schedule created through a technique called TPA and a product importance sampler. One advantage of the algorithm over existing methods is the standard deviation of the estimate can be bounded theoretically. That is to say, unlike most algorithms where the standard deviation must itself be estimated, the standard deviation of this algorithm is fixed ahead of time by the use. The number of samples necessary to build a close estimate grows almost linearly in the logarithm of the partition function, making the approach suitable for high dimensional problems. The samples needed for the estimate can be generated rapidly by methods such as parallel tempering.