Posts Tagged approximation algorithms
I am speaking in the statistics seminar at The Ohio State University next week. The title of my talk is “Fast approximation algorithms for partition functions of Gibbs distributions”. It will be held in the Eighteenth Avenue Building, Room 170 on Thursday, May 24th from 3:30 to 4:30 pm. More details can be found here.
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.