Upper and lower bounds for gradient based sampling methods

This talk will talk about two results regarding gradient-based sampling methods.

First, I will present upper bounds for the problem of sampling from a distribution $p^{\ast }(x)\propto \exp (-U(x))$, where the potential function $U$ is smooth everywhere and strongly convex outside a ball of radius $R$, but potentially nonconvex inside this ball. We study both overdamped and underdamped Langevin MCMC and establish upper bounds on the number of steps required to obtain a sample from a distribution that is within $ϵ$ of the target distribution $p^{\ast }$ in 1-Wasserstein distance.

In the second part of the talk, I will talk about our recent work that establishes information theoretic lower bounds on the iteration complexity of stochastic gradient-based algorithms for sampling from strongly-log concave densities.

This is joint work with Yasin Abbasi-Yadkori, Peter Bartlett, Xiang Cheng, Michael Jordan and Philip Long.