# Fast Doubly-Adaptive MCMC to Estimate the Gibbs Partition Function with Weak Mixing Time Bounds

arXiv: https://arxiv.org/abs/2111.07372 · HTML: https://mlsanity.com/paper/2111.07372/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 73 references that are in the map.
- First posted on arXiv 14 Nov 2021.

## Builds on (most cited first, 17 of 17)

- [Mixing time estimation in reversible Markov chains from a single sample path](https://mlsanity.com/paper/1708.07367/) (2017)
- [Scan Order in Gibbs Sampling: Models in Which it Matters and Bounds on How Much](https://mlsanity.com/paper/1606.03432/) (2016)
- [On Mixing of Markov Chains: Coupling, Spectral Independence, and Entropy Factorization](https://mlsanity.com/paper/2103.07459/) (2021)
- [Fractionally Log-Concave and Sector-Stable Polynomials: Counting Planar Matchings and More](https://mlsanity.com/paper/2102.02708/) (2021)
- [Ensuring Rapid Mixing and Low Bias for Asynchronous Gibbs Sampling](https://mlsanity.com/paper/1602.07415/) (2016)
- [Minibatch Gibbs Sampling on Large Graphical Models](https://mlsanity.com/paper/1806.06086/) (2018)
- [Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model](https://mlsanity.com/paper/2001.00303/) (2020)
- [Function-Specific Mixing Times and Concentration Away from Equilibrium](https://mlsanity.com/paper/1605.02077/) (2016)
- [A Faster Approximation Algorithm for the Gibbs Partition Function](https://mlsanity.com/paper/1608.04223/) (2016)
- [Poisson-Minibatching for Gibbs Sampling with Convergence Rate Guarantees](https://mlsanity.com/paper/1911.09771/) (2019)
- [Rapid Mixing for Colorings via Spectral Independence](https://mlsanity.com/paper/2007.08058/) (2020)
- [Rapidly Mixing Gibbs Sampling for a Class of Factor Graphs Using Hierarchy Width](https://mlsanity.com/paper/1510.00756/) (2015)
- [Projecting Markov Random Field Parameters for Fast Mixing](https://mlsanity.com/paper/1411.1119/) (2014)
- [Mixing Time for Some Adjacent Transposition Markov Chains](https://mlsanity.com/paper/1604.00870/) (2016)
- [Parameter estimation for Gibbs distributions](https://mlsanity.com/paper/2007.10824/) (2020)
- [Making mean-estimation more efficient using an MCMC trace variance approach: DynaMITE](https://mlsanity.com/paper/2011.11129/) (2020)
- [Sampling from the Gibbs Distribution in Congestion Games](https://mlsanity.com/paper/2105.12982/) (2021)

## Built on by (most cited first, 3 of 3)

- [Solving Boltzmann Optimization Problems with Deep Learning](https://mlsanity.com/paper/2401.17408/) (2024)
- [Feynman-Kac Operator Expectation Estimator](https://mlsanity.com/paper/2407.02010/) (2024)
- [Asymptotically Optimal Change Detection for Unnormalized Pre- and Post-Change Distributions](https://mlsanity.com/paper/2410.14615/) (2024)

## Abstract (arXiv)

We present a novel method for reducing the computational complexity of rigorously estimating the partition functions (normalizing constants) of Gibbs (Boltzmann) distributions, which arise ubiquitously in probabilistic graphical models. A major obstacle to practical applications of Gibbs distributions is the need to estimate their partition functions. The state of the art in addressing this problem is multi-stage algorithms, which consist of a cooling schedule, and a mean estimator in each step of the schedule. While the cooling schedule in these algorithms is adaptive, the mean estimation computations use MCMC as a black-box to draw approximate samples. We develop a doubly adaptive approach, combining the adaptive cooling schedule with an adaptive MCMC mean estimator, whose number of Markov chain steps adapts dynamically to the underlying chain. Through rigorous theoretical analysis, we prove that our method outperforms the state of the art algorithms in several factors: (1) The computational complexity of our method is smaller; (2) Our method is less sensitive to loose bounds on mixing times, an inherent component in these algorithms; and (3) The improvement obtained by our method is particularly significant in the most challenging regime of high-precision estimation. We demonstrate the advantage of our method in experiments run on classic factor graphs, such as voting models and Ising models.