Department of Statistics and Data Science Seminar
Andre Wibisono, Yale University
Title: On Bias and Discretization: Sampling under Isoperimetry via Langevin Algorithm
Information and Abstract:
Sampling is a fundamental algorithmic task. Many applications require sampling from probability distributions in high-dimensional spaces, and in modern problems the distributions are complicated and non-logconcave. While the setting of logconcave functions is well-studied, it is important to have efficient sampling algorithms with good convergence guarantees beyond logconcavity. In this talk we study sampling from the perspective of optimization in the space of distributions. We focus on the Langevin dynamics and the Unadjusted Langevin Algorithm (ULA) as a case study. We prove a biased convergence guarantee of ULA in KL divergence assuming the target distribution satisfies Log-Sobolev Inequality (LSI) and the log-density has bounded Hessian; notably, we do not assume convexity nor bounds on higher derivatives. We also show convergence guarantees in Rényi divergence assuming the biased limit satisfies LSI or Poincaré inequality. We investigate the source of the bias of ULA and consider how to remove the bias. We point out the difficulty is that the heat flow is exactly solvable, but neither its forward nor backward method is implementable in general