A Faster Approximation Algorithm for the Gibbs Partition Function Conference Paper


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: 2017-12-27
Start Page: 1
End Page: 17
Sponsor: The author is supported by the European Research Council under the European Unions Seventh Framework Programme (FP7/2007-2013)/ERC grant agreement no 616160.
URL:
Open access: yes (repository)
IST Austria Authors
Related IST Austria Work