On polynomial-time computation of high-dimensional posterior measures by Langevin-type algorithms

Abstract

The problem of generating random samples of high-dimensional posterior distributions is considered. The main results consist of non-asymptotic computational guarantees for Langevin-type MCMC algorithms which scale polynomially in key quantities such as the dimension of the model, the desired precision level, and the number of available statistical measurements. As a direct consequence, it is shown that posterior mean vectors as well as optimisation based maximum a posteriori (MAP) estimates are computable in polynomial time, with high probability under the distribution of the data. These results are complemented by statistical guarantees for recovery of the ground truth parameter generating the data. Our results are derived in a general high-dimensional non-linear regression setting (with Gaussian process priors) where posterior measures are not necessarily log-concave, employing a set of local `geometric' assumptions on the parameter space, and assuming that a good initialiser of the algorithm is available. The theory is applied to a representative non-linear example from PDEs involving a steady-state Schrödinger equation.

arXiv comment70 pages; to appear in the Journal of the European Mathematical Society

References in corpus (10)

• Curse-of-dimensionality revisited: Collapse of the particle filter in very large scale systems
• Rates of contraction of posterior distributions based on Gaussian process priors
• Can local particle filters beat the curse of dimensionality?
• Sampling Can Be Faster Than Optimization
• On the Bernstein-von Mises phenomenon for nonparametric Bayes procedures
• Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithm
• Nonparametric Bayesian posterior contraction rates for discretely observed scalar diffusions
• Bernstein -- von Mises theorems for statistical inverse problems II: Compound Poisson processes
• Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices
• Convergence rates for Penalised Least Squares Estimators in PDE-constrained regression problems

Cited by in corpus (3)

• Nonparametric Bayesian inference for reversible multi-dimensional diffusions
• Consistency of Bayesian inference with Gaussian process priors for a parabolic inverse problem
• A splitting Hamiltonian Monte Carlo method for efficient sampling