# 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.**All files available under the following license(s):**

**Creative Commons Attribution 4.0 International Public License (CC-BY 4.0):**

**Main File(s)**

File Name

2018_PMLR_Kolmogorov.pdf
408.97 KB

Access Level

Open Access

Date Uploaded

2020-05-12

MD5 Checksum

89db06a0e8083524449cb59b56bf4e5b

### Export

Marked PublicationsOpen Data IST Research Explorer

### Sources

arXiv 1608.04223