# A faster approximation algorithm for the Gibbs partition function

V. Kolmogorov, in:, Proceedings of the 31st Conference On Learning Theory, PMLR, 2017, pp. 228–249.

Download

2018_PMLR_Kolmogorov.pdf
408.97 KB

*Conference Paper*|

*Published*|

*English*

Department

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

Proceedings Title

Proceedings of the 31st Conference On Learning Theory

Volume

75

Page

228-249

Conference

COLT: Annual Conference on Learning Theory

Conference Date

2018-07-06 – 2018-07-09

IST-REx-ID

### Cite this

Kolmogorov V. A faster approximation algorithm for the Gibbs partition function. In:

*Proceedings of the 31st Conference On Learning Theory*. Vol 75. PMLR; 2017:228-249.Kolmogorov, V. (2017). A faster approximation algorithm for the Gibbs partition function. In

*Proceedings of the 31st Conference On Learning Theory*(Vol. 75, pp. 228–249). PMLR.Kolmogorov, Vladimir. “A Faster Approximation Algorithm for the Gibbs Partition Function.” In

*Proceedings of the 31st Conference On Learning Theory*, 75:228–49. PMLR, 2017.V. Kolmogorov, “A faster approximation algorithm for the Gibbs partition function,” in

*Proceedings of the 31st Conference On Learning Theory*, 2017, vol. 75, pp. 228–249.Kolmogorov V. 2017. A faster approximation algorithm for the Gibbs partition function. Proceedings of the 31st Conference On Learning Theory. COLT: Annual Conference on Learning Theory vol. 75. 228–249.

Kolmogorov, Vladimir. “A Faster Approximation Algorithm for the Gibbs Partition Function.”

*Proceedings of the 31st Conference On Learning Theory*, vol. 75, PMLR, 2017, pp. 228–49.**Main File(s)**

File Name

2018_PMLR_Kolmogorov.pdf
408.97 KB

Access Level

Open Access

Last Uploaded

2020-05-12T09:23:27Z

### Export

Marked PublicationsOpen Data IST Research Explorer

### Sources

arXiv 1608.04223