Entropy-Based Burn-in Time Analysis and Ranking for (A)MCMC Algorithms in High Dimension

.Many recent and often (adaptive) Markov chain Monte Carlo (A)MCMC methods are associated in practice to unknown rates of convergence. We propose a simulation-based methodology to estimate and compare MCMC's performance in terms of shortest burn-in time, using a Kullback divergence criterion requiring an estimate of the entropy of the algorithm densities at each iteration, computed from i.i.d. simulated chains. In previous works, we proved some consistency results in an MCMC setup for an entropy estimate based on Monte Carlo integration of a kernel density estimate proposed in L. Györfi and E. C. Van Der Meulen, An entropy estimate based on a kernel density estimation, in Limit Theorems in Probability and Statistics, North-Holland, Amsterdam, 1989, pp. 229–240, and we investigate an alternative nearest neighbor (NN) entropy estimate from L. Kozachenko and N. N. Leonenko, Problemy Peredachi Informatsii, 23 (1987), pp. 9–16. This estimate has been used mostly in univariate situations until recently, when entropy estimation in higher dimensions has been considered in other fields like neuroscience or system biology. Unfortunately, in higher dimensions, both estimators converge slowly with a noticeable bias. The present work goes several steps further, with bias reduction and automatic (A)MCMC burn-in time analysis in mind. First, for bias reduction, we apply in our situation a "crossed NN-type" nonparametric estimate of the Kullback divergence between two densities, based on i.i.d. samples from each, introduced by Q. Wang, S. R. Kulkarni, and S. Verdú, A nearest-neighbor approach to estimating divergence between continuous random vectors, in IEEE International Symposium on Information Theory, Seattle, WA, 2006, pp. 242–246, Q. Wang, S. R. Kulkarni, and S. Verdú, IEEE Trans. Inform. Theory, 55 (2009), pp. 2392–2405. We prove the consistency of these entropy estimates under recent uniform control conditions, for the successive densities of a generic class of MCMC algorithm to which most of the methods proposed in the recent literature belong. Second, we propose an original solution based on a PCA for reducing relevant dimension and bias in even higher dimensions whenever PCA is efficient. Our algorithms for MCMC simulation and entropy estimation are progressively added to the R package EntropyMCMC, taking advantage of recent advances in high-performance (parallel) computing.Keywordsadaptive MCMC algorithmsBayesian modelentropyKullback divergenceMetropolis–Hastings algorithmnearest neighbor estimationnonparametric statisticMSC codes60J2262F1562G0562G0765C05