Simple parallel estimation of the partition ratio for Gibbs distributions
This provides more efficient parallel algorithms for statistical physics and machine learning applications, though it is incremental over prior work.
The paper tackles the problem of estimating the partition function ratio for Gibbs distributions, improving sample complexity to O(q log^2 n / ε^2) for non-adaptive algorithms and O(q log n / ε^2) for two-round adaptive algorithms, matching the sequential version.
We consider the problem of estimating the partition function $Z(β)=\sum_x \exp(β(H(x))$ of a Gibbs distribution with the Hamiltonian $H:Ω\rightarrow\{0\}\cup[1,n]$. As shown in [Harris & Kolmogorov 2024], the log-ratio $q=\ln (Z(β_{\max})/Z(β_{\min}))$ can be estimated with accuracy $ε$ using $O(\frac{q \log n}{ε^2})$ calls to an oracle that produces a sample from the Gibbs distribution for parameter $β\in[β_{\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 (\log^2 n) (\log q + \log \log n + ε^{-2}) )$ samples. We improve the number of samples to $O(\frac{q \log^2 n}{ε^2})$ for a non-adaptive algorithm, and to $O(\frac{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.