View abstract

Plenary talk

Tuesday, June 13, 9:30 ~ 10:30

On the computational complexity of high-dimensional MCMC in non-linear inverse problems

Richard Nickl

University of Cambridge, UK   -   This email address is being protected from spambots. You need JavaScript enabled to view it.

We discuss recent results, both positive and negative, about the run-time of Markov chain Monte Carlo (MCMC) algorithms that target posterior distributions arising from high-dimensional non-linear statistical regression models with Gaussian process priors. Prototypical applications include inverse problems with partial differential equations (PDEs). We show that cold-start local MCMC may not work (have `exponential in dimension’ runtime) even for target measures that are radially strictly decreasing away from their unique mode, but that warm-start Langevin type MCMC can achieve polynomial runtime for posterior computation under certain `gradient stability’ conditions that can be verified in a large class of relevant PDE models.

Joint work with Sven Wang (MIT), and for the lower bounds further with Afonso Bandeira (ETH Zürich), Antoine Maillard (ETH Zürich)..

View abstract PDF