Author(s):

Kolmogorov, Vladimir

Title: 
A Faster Approximation Algorithm for the Gibbs Partition Function

Title Series: 
COLT

Affiliation 
IST Austria 
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.

Conference Title:

COLT: Annual Conference on Learning Theory

Conference Dates:

July 6  July 9, 2018

Conference Location:

Stockholm, Sweden

Publisher:

Unknown

Date Published:

20171227

Start Page: 
1

End Page:

17

Sponsor: 
The author is supported by the European Research Council under the European Unions Seventh Framework Programme (FP7/20072013)/ERC grant agreement no 616160.

URL: 

Open access: 
yes (repository) 