conference paper
A faster approximation algorithm for the Gibbs partition function
published
yes
Vladimir
Kolmogorov
author 3D50B0BA-F248-11E8-B48F-1D18A9856A87
VlKo
department
COLT: Annual Conference on Learning Theory
Discrete Optimization in Computer Vision: Theory and Practice
project
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.
https://research-explorer.app.ist.ac.at/download/274/7820/2018_PMLR_Kolmogorov.pdf
application/pdfno
https://creativecommons.org/licenses/by/4.0/
PMLR2017
eng
Proceedings of the 31st Conference On Learning Theory
1608.04223
75228-249
Kolmogorov, Vladimir. “A Faster Approximation Algorithm for the Gibbs Partition Function.” In <i>Proceedings of the 31st Conference On Learning Theory</i>, 75:228–49. PMLR, 2017.
Kolmogorov V. A faster approximation algorithm for the Gibbs partition function. In: <i>Proceedings of the 31st Conference On Learning Theory</i>. Vol 75. PMLR; 2017:228-249.
V. Kolmogorov, in:, Proceedings of the 31st Conference On Learning Theory, PMLR, 2017, pp. 228–249.
Kolmogorov, Vladimir. “A Faster Approximation Algorithm for the Gibbs Partition Function.” <i>Proceedings of the 31st Conference On Learning Theory</i>, vol. 75, PMLR, 2017, pp. 228–49.
Kolmogorov, V. (2017). A faster approximation algorithm for the Gibbs partition function. In <i>Proceedings of the 31st Conference On Learning Theory</i> (Vol. 75, pp. 228–249). PMLR.
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.
V. Kolmogorov, “A faster approximation algorithm for the Gibbs partition function,” in <i>Proceedings of the 31st Conference On Learning Theory</i>, 2017, vol. 75, pp. 228–249.
2742018-12-11T11:45:33Z2021-01-12T06:59:23Z