Making mean-estimation more efficient using an MCMC trace variance approach: DynaMITE

Abstract

We introduce a novel statistical measure for MCMC-mean estimation, the inter-trace variance ${\mathrm{trv}}^{({\tau }_{rel})}(\mathcal{M},f)$, which depends on a Markov chain $\mathcal{M}$ and a function $f:S\to [a,b]$. The inter-trace variance can be efficiently estimated from observed data and leads to a more efficient MCMC-mean estimator. Prior MCMC mean-estimators receive, as input, upper-bounds on ${\tau }_{mix}$ or ${\tau }_{rel}$, and often also the stationary variance, and their performance is highly dependent to the sharpness of these bounds. In contrast, we introduce DynaMITE, which dynamically adjusts the sample size, it is less sensitive to the looseness of input upper-bounds on ${\tau }_{rel}$, and requires no bound on $v_{\pi }$. Receiving only an upper-bound ${\mathcal{T}}_{rel}$ on ${\tau }_{rel}$, DynaMITE estimates the mean of $f$ in $\tilde{\mathcal{O}}(\frac{{\mathcal{T}}_{rel}R}{\epsilon }+\frac{{\tau }_{rel}\cdot {\mathrm{trv}}^{(\tau rel)}}{{\epsilon }^2})$ steps, without a priori bounds on the stationary variance $v_{\pi }$ or the inter-trace variance ${\mathrm{trv}}^{(\tau rel)}$. Thus we depend minimally on the tightness of ${\mathcal{T}}_{mix}$, as the complexity is dominated by ${\tau }_{rel}{\mathrm{trv}}^{(\tau \mathrm{rel})}$ as $\epsilon \to 0$. Note that bounding ${\tau }_{\mathrm{rel}}$ is known to be prohibitively difficult, however, DynaMITE is able to reduce its principal dependence on ${\mathcal{T}}_{rel}$ to ${\tau }_{rel}$, simply by exploiting properties of the inter-trace variance. To compare our method to known variance-aware bounds, we show ${\mathrm{trv}}^{(\tau rel)}(\mathcal{M},f)\le v_{\pi }$. Furthermore, we show when $f$'s image is distributed (semi)symmetrically on $\mathcal{M}$'s traces, we have ${\mathrm{trv}}^{(\tau rel)}(\mathcal{M},f)=o(v_{\pi }(f))$, thus DynaMITE outperforms prior methods in these cases.

References in corpus (10)

• Batch means and spectral variance estimators in Markov chain Monte Carlo
• Mixing times of lozenge tiling and card shuffling Markov chains
• Approximation algorithms for the normalizing constant of Gibbs distributions
• Hoeffding's lemma for Markov Chains and its applications to statistical learning
• A Faster Approximation Algorithm for the Gibbs Partition Function
• Adaptive Multi-GPU Exchange Monte Carlo for the 3D Random Field Ising Model
• Phase transition for the mixing time of the Glauber dynamics for coloring regular trees
• Estimating the Spectral Gap of a Reversible Markov Chain from a Short Trajectory
• Estimating accuracy of the MCMC variance estimator: a central limit theorem for batch means estimators
• Estimating Monte Carlo variance from multiple Markov chains