Fall 2021

Improved Dimension Dependence for the Metropolis-Adjusted Langevin Algorithm and Lower Bounds for Sampling

Monday, Sep. 27, 2021 2:00 pm2:40 pm PDT

Add to Calendar


Calvin Lab Auditorium and Zoom

The popular diffusion scaling heuristic predicts that the mixing time of the Metropolis-Adjusted Langevin Algorithm (MALA) should scale as d^{1/3}, where d is the dimension. However, the diffusion scaling limit requires stringent assumptions and is asymptotic in nature. In the first part of my talk, I will discuss our work on improving the state-of-the-art non-asymptotic mixing time bound for MALA on the class of log-smooth and strongly log-concave distributions from O(d) to O(d^{1/2}), under the additional assumption of a warm start. Our proof introduces a new technique based on a projection characterization of the Metropolis adjustment which reduces the study of MALA to the discretization analysis of the Langevin SDE. In the second part of my talk, I will discuss the elusive problem of obtaining lower bounds for sampling, including our recent work which establishes the first tight query complexity bound for sampling in one dimension.

PDF icon Slides1.1 MB