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

2022/09/05 by Afonso S. Bandeira, Antoine Maillard, Bandeira, Afonso S. +5 · 5 citations
Computer Science · Mathematics · #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (stat.ML) #Numerical Analysis (math.NA) #Probability (math.PR) #Statistics Theory (math.ST) #cs.NA #math.NA #math.PR #math.ST #stat.ML #stat.TH

paper · pdf · doi:10.48550/arxiv.2209.02001

27 pages, 5 figures, to appear in Philosophical Transactions of the Royal Society A

arxiv created 2022/11/19 · arxiv updated 2022/11/22

Abstract

We exhibit examples of high-dimensional unimodal posterior distributions arising in non-linear regression models with Gaussian process priors for which 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 initialised (`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 pCN and MALA.

Cited by

• Global polynomial-time estimation in statistical nonlinear inverse problems via generalized stability
• Reasoning with Sampling: Your Base Model is Smarter Than You Think
• Fast-Mixing Markov Chains without Gradients
• Reasoning with Sampling: Cutting at Decision Points
• On micromodes in Bayesian posterior distributions and their implications for MCMC

Related

• Fast Langevin based algorithm for MCMC in high dimensions
• Polynomial time guarantees for sampling based posterior inference in high-dimensional generalised linear models
• Gaussian Processes to speed up MCMC with automatic exploratory-exploitation effect
• On polynomial-time computation of high-dimensional posterior measures by Langevin-type algorithms
• On MCMC for variationally sparse Gaussian processes: A pseudo-marginal approach