Approximation algorithms for the normalizing constant of Gibbs distributions

Abstract

Consider a family of distributions $\{{\pi }_{\beta }\}$ where $X\sim {\pi }_{\beta }$ means that $\mathbb{P}(X=x)=\exp (-\beta H(x))/Z(\beta )$. Here $Z(\beta )$ is the proper normalizing constant, equal to ${\sum }_x\exp (-\beta H(x))$. Then $\{{\pi }_{\beta }\}$ is known as a Gibbs distribution, and $Z(\beta )$ is the partition function. This work presents a new method for approximating the partition function to a specified level of relative accuracy using only a number of samples, that is, $O(\ln (Z(\beta ))\ln (\ln (Z(\beta ))))$ when $Z(0)\ge 1$. This is a sharp improvement over previous, similar approaches that used a much more complicated algorithm, requiring $O(\ln (Z(\beta ))\ln (\ln (Z(\beta )){)}^5)$ samples.

Published in at http://dx.doi.org/10.1214/14-AAP1015 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (2)

• MCMC using Hamiltonian dynamics
• Perfect Sampling Using Bounding Chains

Cited by in corpus (11)

• Quantum speedup of Monte Carlo methods
• Simpler (classical) and faster (quantum) algorithms for Gibbs partition functions
• A Faster Approximation Algorithm for the Gibbs Partition Function
• Optimal quantum algorithm for Gibbs state preparation
• Approximately counting bases of bicircular matroids
• A Sublinear-Time Quantum Algorithm for Approximating Partition Functions
• Amplitude Ratios and Neural Network Quantum States
• Improving Monte Carlo randomized approximation schemes
• Rapid Mixing for Colorings via Spectral Independence
• Fewer colors for perfect simulation of proper colorings
• Making mean-estimation more efficient using an MCMC trace variance approach: DynaMITE