Timezone: »

 
Oral
Lower Bounds on Metropolized Sampling Methods for Well-Conditioned Distributions
Yin Tat Lee · Ruoqi Shen · Kevin Tian

Tue Dec 07 12:40 AM -- 12:55 AM (PST) @
in Oral Session 1: Theory »
We give lower bounds on the performance of two of the most popular sampling methods in practice, the Metropolis-adjusted Langevin algorithm (MALA) and multi-step Hamiltonian Monte Carlo (HMC) with a leapfrog integrator, when applied to well-conditioned distributions. Our main result is a nearly-tight lower bound of $\widetilde{\Omega}(\kappa d)$ on the mixing time of MALA from an exponentially warm start, matching a line of algorithmic results \cite{DwivediCW018, ChenDWY19, LeeST20a} up to logarithmic factors and answering an open question of \cite{ChewiLACGR20}. We also show that a polynomial dependence on dimension is necessary for the relaxation time of HMC under any number of leapfrog steps, and bound the gains achievable by changing the step count. Our HMC analysis draws upon a novel connection between leapfrog integration and Chebyshev polynomials, which may be of independent interest.
Keywords:

Author Information

Yin Tat Lee (UW)
Ruoqi Shen (University of Washington)
Kevin Tian (Stanford University)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors