Approximation algorithms for the normalizing constant of Gibbs distributions

Abstract

Consider a family of distributions $\{\ddot{I}{€}_{\hat{I}}^2\}$ where $X\sim \ddot{I}{€}_{\hat{I}}^2$ means that $\mathbb{P}(X=x)=\exp (-{\hat{I}}^{2}H(x))/Z({\hat{I}}^2)$. Here $Z({\hat{I}}^2)$ is the proper normalizing constant, equal to ${\sum }_x\exp (-{\hat{I}}^{2}H(x))$. Then $\{\ddot{I}{€}_{\hat{I}}^2\}$ is known as a Gibbs distribution, and $Z({\hat{I}}^2)$ is the partition function. This work presents a new method for approximating the partition function to a specified level of relative accuracy using only a number of samples, that is, $O(\ln (Z({\hat{I}}^2))\ln (\ln (Z({\hat{I}}^2))))$ when $Z(0)\ge 1$. This is a sharp improvement over previous, similar approaches that used a much more complicated algorithm, requiring $O(\ln (Z({\hat{I}}^2))\ln (\ln (Z({\hat{I}}^2)){)}^5)$ samples.

Published in at http://dx.doi.org/10.1214/14-AAP1015 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)