A Faster Approximation Algorithm for the Gibbs Partition Function

Abstract

We consider the problem of estimating the partition function $Z(\beta )={\sum }_x\exp (-\beta (H(x))$ of a Gibbs distribution with a Hamilton $H(\cdot )$, or more precisely the logarithm of the ratio $q=\ln Z(0)/Z(\beta )$. 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,\beta ]$. The current best known approach due to Huber [9] uses $O(q\ln n\cdot [\ln q+\ln \ln n+{\epsilon }^{-2}])$ oracle calls on average where $\epsilon$ is the desired accuracy of approximation and $H(\cdot )$ is assumed to lie in $\{0\}\cup [1,n]$. We improve the complexity to $O(q\ln n\cdot {\epsilon }^{-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(\frac{{\epsilon }^2}{q\ln n})$ variation distance from exact oracles. Finally, we prove a lower bound of $\Omega (q\cdot {\epsilon }^{-2})$ oracle calls under a natural model of computation.

References in corpus (1)

• Perfect Sampling Using Bounding Chains

Cited by in corpus (5)

• Approximately counting bases of bicircular matroids
• A Sublinear-Time Quantum Algorithm for Approximating Partition Functions
• Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion
• Approximate Counting for Spin Systems in Sub-Quadratic Time
• Making mean-estimation more efficient using an MCMC trace variance approach: DynaMITE