Lower Bounds on Metropolized Sampling Methods for Well-Conditioned Distributions

Sampling from a continuous distribution in high dimensions is a fundamental problem in algorithm design. As sampling serves as a key subroutine in a variety of tasks in machine learning [AdFDJ03], statistical methods [RC99], and scientific computing [Liu01], it is an important undertaking to understand the complexity of sampling from families of distributions arising in applications. The more restricted problem of sampling from a particular family of distributions, which we call "well-conditioned distributions," has garnered a substantial amount of recent research effort from the algorithmic learning and statistics communities. This specific family is interesting for a number of reasons. First of all, it is practically relevant: Bayesian methods have found increasing use in machine learning applications [Bar12], and many distributions arising from these methods are wellconditioned, such as multivariate Gaussians, mixture models with small separation, and densities arising from Bayesian logistic regression with a Gaussian prior [DCWY18].