Article Contents
Article Contents

# Geometric adaptive Monte Carlo in random environment

• * Corresponding author: Theodore Papamarkou
• Manifold Markov chain Monte Carlo algorithms have been introduced to sample more effectively from challenging target densities exhibiting multiple modes or strong correlations. Such algorithms exploit the local geometry of the parameter space, thus enabling chains to achieve a faster convergence rate when measured in number of steps. However, acquiring local geometric information can often increase computational complexity per step to the extent that sampling from high-dimensional targets becomes inefficient in terms of total computational time. This paper analyzes the computational complexity of manifold Langevin Monte Carlo and proposes a geometric adaptive Monte Carlo sampler aimed at balancing the benefits of exploiting local geometry with computational cost to achieve a high effective sample size for a given computational cost. The suggested sampler is a discrete-time stochastic process in random environment. The random environment allows to switch between local geometric and adaptive proposal kernels with the help of a schedule. An exponential schedule is put forward that enables more frequent use of geometric information in early transient phases of the chain, while saving computational time in late stationary phases. The average complexity can be manually set depending on the need for geometric exploitation posed by the underlying model.

Mathematics Subject Classification: Primary: 60K37, 62M09; Secondary: 60G57, 85A35.

 Citation:

• Figure 1.  Overlaid running means as a function of Monte Carlo iteration and overlaid linear autocorrelations of single chains corresponding to one of the twenty, six and eleven parameters of the respective t-distribution, one-planet and two-planet system. The black horizontal line in the t-distribution running mean plot represents the true mode

Figure 2.  Trace plots of single chains as a function of Monte Carlo iteration corresponding to one of the twenty and eleven parameters of the respective t-distribution and two-planet system. The same chains were used for generating the trace plots of figure 2 and the associated running means and autocorrelations of figure 1. The black horizontal lines in the t-distribution trace plots represent the true mode

Table 1.  General complexity bounds per step of MALA, SMMALA, MMALA and AM samplers, and two special cases of a log-target $f$ with linear complexity $\mathcal{O}(f) = \mathcal{O}(n)$ and of expensive log-targets $f$ with complexity $\mathcal{O}(f)>>\mathcal{O}(n)$

 Method General $\mathcal{O}(f)$ Special cases of $\mathcal{O}(f)$ $\mathcal{O}(f)=\mathcal{O}(n)$ $\mathcal{O}(f)>>\mathcal{O}(n)$ MALA $\mathcal{O}(\max{\{fn,n^2\}})$ $\mathcal{O}(n^2)$ $\mathcal{O}(fn)$ SMMALA $\mathcal{O}(\max{\{fn^2,n^3\}})$ $\mathcal{O}(n^3)$ $\mathcal{O}(fn^2)$ MMALA $\mathcal{O}(\max{\{fn^3,n^3\}})$ $\mathcal{O}(n^4)$ $\mathcal{O}(fn^3)$ AM $\mathcal{O}(\max\{f, n^{2.373}\})$ $\mathcal{O}(n^{2.373})$ $\mathcal{O}(f)$

Table 2.  Comparison of sampling efficacy between MALA, AM, SMMALA and GAMC for the t-distribution, one-planet and two-planet system. AR: acceptance rate; ESS: effective sample size; t: CPU runtime in seconds; ESS/t: smaller ESS across model parameters divided by runtime; Speed: ratio of ESS/t for MALA over ESS/t for each other sampler. All tabulated numbers have been rounded to the second decimal place, apart from effective sample sizes, which have been rounded to the nearest integer. The minimum, mean, median and maximum ESS across the effective sample sizes of the twenty, six and eleven parameters (associated with the respective t-distribution, one-planet and two-planet system) are displayed

 Student’s t-distribution Method AR ESS t ESS/t Speed min mean median max MALA 0.59 135 159 145 234 9.33 14.52 1.00 AM 0.03 85 118 117 155 17.01 5.03 0.35 SMMALA 0.71 74 87 86 96 143.63 0.52 0.04 GAMC 0.26 1471 1558 1560 1629 31.81 46.23 3.18 One-planet system Method AR ESS t ESS/t Speed min mean median max MALA 0.55 4 76 18 394 57.03 0.07 1.00 AM 0.08 1230 1397 1279 2035 48.84 25.18 378.50 SMMALA 0.71 464 597 646 658 208.46 2.23 33.45 GAMC 0.30 1260 2113 2151 3032 76.80 16.41 246.59 Two-planet system Method AR ESS t ESS/t Speed min mean median max MALA 0.59 5 52 10 377 219.31 0.02 1.00 AM 0.01 18 84 82 248 81.24 0.22 9.05 SMMALA 0.70 53 104 100 161 1606.92 0.03 1.37 GAMC 0.32 210 561 486 1110 328.08 0.64 26.39

Figures(2)

Tables(2)