A faster approximation algorithm for the Gibbs partition function

V. Kolmogorov, in:, Unknown, 2017, pp. 1–17.

Conference Paper | Epub ahead of print | English
Department
Series Title
COLT
Abstract
We consider the problem of estimating the partition function Z(β)=∑xexp(−β(H(x)) of a Gibbs distribution with a Hamilton H(⋅), or more precisely the logarithm of the ratio q=lnZ(0)/Z(β). 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,β]. The current best known approach due to Huber [9] uses O(qlnn⋅[lnq+lnlnn+ε−2]) oracle calls on average where ε is the desired accuracy of approximation and H(⋅) is assumed to lie in {0}∪[1,n]. We improve the complexity to O(qlnn⋅ε−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(ε2qlnn) variation distance from exact oracles. Finally, we prove a lower bound of Ω(q⋅ε−2) oracle calls under a natural model of computation.
Publishing Year
Date Published
2017-12-27
Page
1 - 17
Conference
COLT: Annual Conference on Learning Theory
IST-REx-ID

Cite this

Kolmogorov V. A faster approximation algorithm for the Gibbs partition function. In: Unknown; 2017:1-17.
Kolmogorov, V. (2017). A faster approximation algorithm for the Gibbs partition function (pp. 1–17). Presented at the COLT: Annual Conference on Learning Theory , Unknown.
Kolmogorov, Vladimir. “A Faster Approximation Algorithm for the Gibbs Partition Function,” 1–17. Unknown, 2017.
V. Kolmogorov, “A faster approximation algorithm for the Gibbs partition function,” presented at the COLT: Annual Conference on Learning Theory , 2017, pp. 1–17.
Kolmogorov V. 2017. A faster approximation algorithm for the Gibbs partition function. COLT: Annual Conference on Learning Theory , COLT, 1–17.
Kolmogorov, Vladimir. A Faster Approximation Algorithm for the Gibbs Partition Function. Unknown, 2017, pp. 1–17.

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar