Parameter estimation for integer-valued Gibbs distributions

Abstract

A central problem in computational statistics is to convert a procedure for sampling combinatorial from an objects into a procedure for counting those objects, and vice versa. Weconsider sampling problems coming from *Gibbs distributions*, which are probability distributions of the form ${\mu }_{\beta }^{\Omega }(\omega )\propto e^{\beta H(\omega )}$ for $\beta$ in an interval $[β_\min, β_\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 are the log partition ratio $q = \log \tfrac{Z(β_\max)}{Z(β_\min)}$ and the vector of counts $c_x=|H^{-1}(x)|$. Our first result is an algorithm 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). We show this is optimal up to logarithmic factors. We illustrate with improved algorithms for counting connected subgraphs and perfect matchings in a graph. We develop a key subroutine for global estimation of the partition function. Specifically, we produce a data structure to estimate $Z(\beta )$ for \emph{all} values $\beta$, without further samples. Constructing the data structure requires $O(\frac{q\log n}{{\epsilon }^2})$ samples for general Gibbs distributions and $O(\frac{n^2\log n}{{\epsilon }^2}+n\log q)$ samples for integer-valued distributions. This improves over a prior algorithm of Kolmogorov (2018) which computes the single point estimate $Z(β_\max)$ using $\tilde{O}(\frac{q}{{\epsilon }^2})$ samples. We also show that this complexity is optimal as a function of $n$ and $q$ up to logarithmic terms.

arXiv commentSuperseded by arXiv:2007.10824 This version is obsolete