![Geometric Methods in Optimization and Sampling_hi-res logo](/sites/default/files/styles/workshop_banner_sm_1x/public/2023-03/Geometric%20Methods%20in%20Optimization%20and%20Sampling_hi-res.jpg?h=b86da943&itok=A6FwVTMn)
Abstract
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.