CISE Seminar: Jonathan Weare, Professor of Mathematics, Courant Institute of Mathematical Sciences, New York University

Convergence of Unadjusted Langevin and HMC in High Dimensions: Delocalization of Bias

The unadjusted Langevin algorithm is commonly used to sample probability distributions in extremely high-dimensional settings. However, existing analyses of the algorithm for strongly log-concave distributions suggest that, as the dimension d of the problem increases, the number of iterations required to ensure convergence within a desired error in the W2 metric scales in proportion to d or its square root. In this paper, we argue that, despite this poor scaling of the W2 error for the full set of variables, the behavior for a small number of variables can be significantly better: a number of iterations proportional to K, up to logarithmic terms in d, often suffices for the algorithm to converge to within a desired W2 error for all K-marginals. We refer to this effect as delocalization of bias. We show that the delocalization effect does not hold universally and prove its validity for Gaussian distributions and strongly log-concave distributions with certain sparse interactions. Our analysis relies on a novel W2,ℓ∞ metric to measure convergence. A key technical challenge we address is the lack of a one-step contraction property in this metric. Our results cover both the underdamped and overdamped Langevin schemes as well as an unadjusted version of the popular Hybrid (or Hamiltonian) Monte Carlo algorithm.

Jonathan Weare is a professor of mathematics in the Courant Institute of Mathematical Sciences at New York University. Previously he was an associate professor in the statistics department and in the James Franck Institute at the University of Chicago and, before that, an assistant professor in the mathematics department there. Before moving to Chicago, Weare was a Courant Instructor of mathematics at NYU and a PhD student in mathematics at the University of California at Berkeley.

Faculty Host: Konstantinos Spiliopoulos

Student Host: Chae Woo Lim