2025/05/23 by David G. Harris, Vladimir Kolmogorov, Harris, David G. +1
Computer Science · #Bayesian Methods and Mixture Models
paper · pdf · doi:10.48550/arxiv.2505.18324
We consider the problem of estimating the partition function Z(β)=∑x exp(β(H(x)) of a Gibbs distribution with the Hamiltonian H:Ω→\0\∪[1,n]. As shown in [Harris & Kolmogorov 2024], the log-ratio q=ln (Z(βmax)/Z(βmin)) can be estimated with accuracy ε using O((q log n)/(ε2)) calls to an oracle that produces a sample from the Gibbs distribution for parameter β∈[βmin,βmax]. That algorithm is inherently sequential, or \em adaptive: the queried values of β depend on previous samples. Recently, [Liu, Yin & Zhang 2024] developed a non-adaptive version that needs O( q (log2 n) (log q + log log n + ε-2) ) samples. We improve the number of samples to O((q log2 n)/(ε2)) for a non-adaptive algorithm, and to O((q log n)/(ε2)) for an algorithm that uses just two rounds of adaptivity (matching the complexity of the sequential version). Furthermore, our algorithm simplifies previous techniques. In particular, we use just a single estimator, whereas methods in [Harris & Kolmogorov 2024, Liu, Yin & Zhang 2024] employ two different estimators for different regimes.