Making mean-estimation more efficient using an MCMC trace variance approach: DynaMITE
share
The Markov-Chain Monte-Carlo (MCMC) method has been used widely in the literature for various applications, in particular estimating the expectation 𝔼_π[f] of a function f:Ω→ [a,b] over a distribution π on Ω (a.k.a. mean-estimation), to within ε additive error (w.h.p.). Letting R ≐ b-a, standard variance-agnostic MCMC mean-estimators run the chain for Õ(TR^2/ε^2) steps, when given as input an (often loose) upper-bound T on the relaxation time τ_ rel. When an upper-bound V on the stationary variance v_π≐𝕍_π[f] is known, Õ(TR/ε+TV/ε^2) steps suffice. We introduce the DYNAmic Mcmc Inter-Trace variance Estimation (DynaMITE) algorithm for mean-estimation. We define the inter-trace variance v_T for any trace length T, and show that w.h.p., DynaMITE estimates the mean within ε additive error within Õ(TR/ε + τ_ rel v_τ rel/ε^2) steps, without a priori bounds on v_π, the variance of f, or the trace variance v_T. When ϵ is small, the dominating term is τ_ rel v_τ rel, thus the complexity of DynaMITE principally depends on the a priori unknown τ_ rel and v_τ rel. We believe in many situations v_T=o(v_π), and we identify two cases to demonstrate it. Furthermore, it always holds that v_τ rel≤ 2v_π, thus the worst-case complexity of DynaMITE is Õ(TR/ε +τ_ rel v_π/ε^2), improving the dependence of classical methods on the loose bounds T and V.
READ FULL TEXT