Parameter estimation for Gibbs distributions

Abstract

We consider Gibbs distributions, which are families of probability distributions over a discrete space $\Omega$ with probability mass function of the form ${\mu }_{\beta }^{\Omega }(\omega )\propto e^{\beta H(\omega )}$ for $\beta$ in an interval $[{\beta }_{\min },{\beta }_{\max }]$ and $H(\omega )\in \{0\}\cup [1,n]$. The partition function is the normalization factor $Z(\beta )={\sum }_{\omega \in \Omega }{e}^{\beta H(\omega )}$. Two important parameters of these distributions are the log partition ratio $q=\log \frac{Z({\beta }_{\max })}{Z({\beta }_{\min })}$ and the counts $c_x=|H^{-1}(x)|$. These are correlated with system parameters in a number of physical applications and sampling algorithms. Our first main result is to estimate the counts $c_x$ using roughly $\tilde{O}(\frac{q}{{\epsilon }^2})$ samples for general Gibbs distributions and $\tilde{O}(\frac{n^2}{{\epsilon }^2})$ samples for integer-valued distributions (ignoring some second-order terms and parameters), and we show this is optimal up to logarithmic factors. We illustrate with improved algorithms for counting connected subgraphs, independent sets, and perfect matchings. As a key subroutine, we also develop algorithms to compute the partition function $Z$ using $\tilde{O}(\frac{q}{{\epsilon }^2})$ samples for general Gibbs distributions and using $\tilde{O}(\frac{n^2}{{\epsilon }^2})$ samples for integer-valued distributions.

arXiv commentThis is a longer version which extends two previous papers "A Faster Approximation Algorithm for the Gibbs Partition Function" (arXiv:1608.04223), published in COLT 2018, and "Parameter estimation for Gibbs distributions" published in ICALP 2023