We consider the problem of estimating the partition function $Z(eta)=sum_x exp(-eta H(x))$ of a Gibbs distribution with a Hamilton $H(cdot)$, or more precisely the logarithm of the ratio $q=ln Z(0)/Z(eta)$. It has been recently shown how to approximate $q$ with high probability assuming the existence of an oracle that produces samples from the Gibbs distribution for a given parameter value in $[0,eta]$. The current best known approach due to Huber (2015) uses $O(qln ncdot[ln q + ln ln n+arepsilon^{-2}])$ oracle calls on average where $arepsilon$ is the desired accuracy of approximation and $H(cdot)$ is assumed to lie in ${0}cup[1,n]$. We improve the complexity to $O(qln ncdotarepsilon^{-2})$ oracle calls. We also show that the same complexity can be achieved if exact oracles are replaced with approximate sampling oracles that are within $O(rac{arepsilon^2}{qln n})$ variation distance from exact oracles. Finally, we prove a lower bound of $Omega(qcdot arepsilon^{-2})$ oracle calls under a natural model of computation.
展开▼
