Parameter estimation for Gibbs distributions
Preprint
Abstract
We consider Gibbs distributions, which are families of probability distributions over a discrete space $\Omega$ with probability mass function of the form $\mu^\Omega_\beta(\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 \tfrac{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}{\varepsilon^2})$ samples for general Gibbs distributions and $\tilde O( \frac{n^2}{\varepsilon^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}{\varepsilon^2})$ samples for general Gibbs distributions and using $\tilde O(\frac{n^2}{\varepsilon^2})$ samples for integer-valued distributions.
Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- Tight bounds for popping algorithmsRandom Structures & Algorithms, 2020
- A Polynomial-Time Approximation Algorithm for All-Terminal Network ReliabilitySIAM Journal on Computing, 2019
- Approximation algorithms for the normalizing constant of Gibbs distributionsThe Annals of Applied Probability, 2015
- Using TPA for Bayesian Inference*2011
- Adaptive simulated annealing: A near-optimal connection between sampling and countingJournal of the ACM, 2009
- Monte Carlo Simulations of Proteins in Cages: Influence of Confinement on the Stability of Intermediate StatesBiophysical Journal, 2009
- Accelerating Simulated Annealing for the Permanent and Combinatorial Counting ProblemsSIAM Journal on Computing, 2008
- Wang-Landau algorithm: A theoretical analysis of the saturation of the errorThe Journal of Chemical Physics, 2007
- Efficient, Multiple-Range Random Walk Algorithm to Calculate the Density of StatesPhysical Review Letters, 2001
- Approximating the PermanentSIAM Journal on Computing, 1989