We consider the problem of estimating the partition function $Z(\beta)=\sum_x \exp(\beta(H(x))$ of a Gibbs distribution with the Hamiltonian $H:\Omega\rightarrow\{ 0\}\cup[1,n]$. As shown in [Harris & Kolmogorov 2024], the log-ratio $q=\ln (Z(\beta_{ \max})/Z(\beta_{ \min}))$ can be estimated with accuracy $\epsilon$ using $O(\frac{ q \log n}{ \epsilon^2})$ calls to an oracle that produces a sample from the Gibbs distribution for parameter $\beta\in[\beta_{ \min},\beta_{ \max}]$. That algorithm is inherently sequential, or { \em adaptive}: the queried values of $\beta$ depend on previous samples. Recently, [Liu, Yin & Zhang 2024] developed a non-adaptive version that needs $O( q (\log^2 n) (\log q + \log \log n + \epsilon^{ -2}) )$ samples. We improve the number of samples to $O(\frac{ q \log^2 n}{ \epsilon^2})$ for a non-adaptive algorithm, and to $O(\frac{ q \log n}{ \epsilon^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.
Categories: math.PR cs.DS