Polynomial time guarantees for sampling based posterior inference
The Bayesian approach provides a flexible framework for a wide range of non-parametric inference problems. It relies crucially on computing functionals with respect to the posterior distribution, such as the posterior mean or posterior quantiles for uncertainty quantification. Since the posterior is rarely available in closed form, this is based on Markov chain Monte Carlo (MCMC) sampling algorithms. The runtime of these algorithms until a given target precision is achieved will typically scale exponentially in the model dimension and the sample size. In contrast, in this talk we will see that sampling based posterior inference in a general high-dimensional setup is feasible, even without global structural assumptions such as strong log-concavity of the posterior. Given a sufficiently good initialiser, we present polynomial-time convergence guarantees for a widely used gradient based MCMC sampling scheme. The key idea is to combine posterior contraction with the local curvature induced by the Fisher-information of the statistical model near the data generating truth. We will discuss applications to high-dimensional logistic and Gaussian regression, as well as to density estimation.