Optimization Online


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

Lingqing Shen (lingqing.shen***at***smail.nju.edu.cn)
Krishnakumar Balasubramanian (kbala***at***ucdavis.edu)
Saeed Ghadimi (sghadimi***at***princeton.edu)

Abstract: Euler-Maruyama and Ozaki discretization of a continuous time diffusion process is a popular technique for sampling, that uses (upto) gradient and Hessian information of the density respectively. The Euler-Maruyama discretization has been used particularly for sampling under the name of Langevin Monte Carlo (LMC) for sampling from strongly log-concave densities. In this work, we make several theoretical contributions to the literature on such sampling techniques. Specifically, we first provide a Randomized Coordinate wise LMC algorithm suitable for large-scale sampling problem and provide a theoretical analysis. We next consider the case of zeroth-order or black-box sampling where one only obtains evaluates of the density. Based on Gaussian Steinís identities we then estimate the gradient and Hessian information and leverage it in the context of black-box sampling. We provide a theoretical analysis of the proposed sampling algorithm quantifying the non-asymptotic accuracy. We also consider high-dimensional black-box sampling under the assumption that the density depends only on a small subset of the entire coordinates. We propose a variable selection technique based on zeroth-order gradient estimates and establish its theoretical guarantees. Our theoretical contributions extend the practical applicability of sampling algorithms to the large-scale, black-box and high-dimensional settings.

Keywords: Langevin Monte Carlo, Sampling, Black-box optimization, Diffusion process

Category 1: Applications -- Science and Engineering (Statistics )

Category 2: Nonlinear Optimization


Download: [PDF]

Entry Submitted: 02/05/2019
Entry Accepted: 02/05/2019
Entry Last Modified: 03/14/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society