Non-asymptotic Results for Langevin Monte Carlo: Coordinate-wise and Black-box Sampling

  • 2019-03-14 14:52:37
  • Lingqing Shen, Krishnakumar Balasubramanian, Saeed Ghadimi
  • 0

Abstract

Discretization of continuous-time diffusion processes, using gradient andHessian information, is a popular technique for sampling. For example, theEuler-Maruyama discretization of the Langevin diffusion process, called asLangevin Monte Carlo (LMC), is a canonical algorithm for sampling from stronglylog-concave densities. In this work, we make several theoretical contributionsto the literature on such sampling techniques. Specifically, we first provide aRandomized Coordinate-wise LMC algorithm suitable for large-scale samplingproblems and provide a theoretical analysis. We next consider the case ofzeroth-order or black-box sampling where one only obtains evaluates of thedensity. Based on Gaussian Stein's identities we then estimate the gradient andHessian information and leverage it in the context of black-box sampling. Wethen provide a theoretical analysis of gradient and Hessian baseddiscretizations of Langevin and kinetic Langevin diffusion processes forsampling, quantifying the non-asymptotic accuracy. We also considerhigh-dimensional black-box sampling under the assumption that the densitydepends only on a small subset of the entire coordinates. We propose a variableselection technique based on zeroth-order gradient estimates and establish itstheoretical guarantees. Our theoretical contributions extend the practicalapplicability of sampling algorithms to the large-scale, black-box andhigh-dimensional settings.

 

Quick Read (beta)

loading the full paper ...