Parameter Estimation for Gibbs Distributions

A central problem in computational statistics is to convert a procedure for sampling combinatorial objects into a procedure for counting those objects, and vice versa. We consider sampling problems coming from Gibbs distributions, which are families of probability distributions over a discrete space Omega with probability mass function of the form ` V Omega (l)proportional to 4V(l ) for V in an interval [Vmin,Vmax]and ( l )is an element of{0}boolean OR[1, = ]. Two important parameters are the partition function, which is the normalization factor / (V) = & Iacute; l is an element of Omega 4 V (l ) and the vector of pre-image counts 2 G = | - 1 ( G )|. We develop black-box sampling algorithms to estimate the counts using roughly $ ( = 2 Y 2 ) samples for integer- valued distributions and $ ( Y @ 2 )samples for general distributions, where @ = log / ( V max ) / ( V min ) (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, independent sets, and perfect matchings. As a key subroutine, we estimate all values of the partition function using $ ( = 2 Y 2 ) samples for integer-valued distributions and $ ( Y @ 2 )samples for general distributions. This improves over a prior algorithm of Huber (2015) which computes a single point estimate / ( V max ) and which uses a slightly larger amount of samples. We show matching lower bounds, demonstrating this complexity is optimal as a function of = and @ up to logarithmic terms.