On free energy barriers in Gaussian priors and failure of cold start MCMC for high-dimensional unimodal distributions

Abstract

We exhibit examples of high-dimensional unimodal posterior distributions arising in nonlinear regression models with Gaussian process priors for which Markov chain Monte Carlo (MCMC) methods can take an exponential run-time to enter the regions where the bulk of the posterior measure concentrates. Our results apply to worst-case initialized ('cold start') algorithms that are local in the sense that their step sizes cannot be too large on average. The counter-examples hold for general MCMC schemes based on gradient or random walk steps, and the theory is illustrated for Metropolis-Hastings adjusted methods such as preconditioned Crank-Nicolson and Metropolis-adjusted Langevin algorithm. This article is part of the theme issue 'Bayesian inference: challenges, perspectives, and prospects'.

Keywords: Bayesian inference; Gaussian processes; MCMC; computational hardness.

Figure 1.

Two possible sources of MCMC hardness in high dimensions: multi-modal likelihoods and entropic barriers. (a) In low dimensions (here $D=1$), MCMC hardness usually arises because of a non-unimodal likelihood, creating an ‘energy barrier’, even though the maximum likelihood is attained at $\theta ={\theta }_0$. The MCMC algorithm is assumed to be initialized in the set $\mathcal{S}$ containing a local maximum of the likelihood. (b) Illustration of the arising of entropic (or volumetric) difficulties, here in dimension $D=3$: the set of points close to ${\theta }_0$ has much less volume than the set of points far away. As $D$ increases, this phenomenon is amplified: all ratios of volumes of the three sets $\mathcal{T},\mathcal{W},\mathcal{S}$ scale exponentially with $D$. (Online version in colour.)

Figure 2.

Illustration of a free-energy barrier (or free-entropy well) arising with a unimodal posterior. The model is an ‘averaged’ version of the spiked tensor model, with log-likelihood ${\ell }_n(\theta )=\lambda {⟨\theta ,{\theta }_0⟩}^3/2$ and uniform prior $\Pi$ on the $n$-dimensional unit sphere ${\mathbb{S}}^{n-1}$. ${\theta }_0$ is chosen arbitrarily on ${\mathbb{S}}^{n-1}$. The posterior is $\mathrm{d}\Pi (\theta |Y)\propto \exp \{n{\ell }_n(\theta )\}\hspace{0.17em}\mathrm{d}\Pi (\theta )$, for $\theta \in {\mathbb{S}}^{n-1}$. Up to a constant, the free entropy $F(r)=(1/n)\log \int \hspace{0.17em}\mathrm{d}\Pi (\theta |Y)\delta (r-||\theta -{\theta }_0|{|}_2)$ can be decomposed as the sum of ${\ell }_n(\theta )$ (that only depends on $r=||\theta -{\theta }_0|{|}_2$) and the ‘entropic’ contribution $(1/n)\log \int \hspace{0.17em}\mathrm{d}\Pi (\theta )\delta (r-||\theta -{\theta }_0|{|}_2)$. In the figure we show $\lambda =2.1$. (Online version in colour.)