Back to search

Georgia Institute of Technology

Informed Sampling in Discrete Space, and its Applications

Abstract

dc:description.abstract

Sampling has been an important problem in physics, statistics, computer science, and machine learning. When the target distribution is intractable, Metropolis-Hastings algorithms are widely used. Within the Metropolis-Hastings paradigm, informed sampling is defined as using the information of target distribution to guide the proposal distribution, which is typically referred to by gradient-based sampling in continuous space. Over the past decades, gradient-based sampling algorithms have significantly improved the sampling efficiency in continuous space from both theoretical and practical sides. However, the informed sampling in discrete space are less understood as the diffusion processes in continuous space do not apply in discrete space. In this thesis, we will introduce the recent advances of informed sampling in discrete space. Specifically \begin{itemize} \item {\bf Discrete Langevin Dynamics}\quad The Langevin dynamics, from which the gradient-based sampling algorithms in continuous space are designed, is the gradient flow to minimize the KL-divergence towards the target distribution on the Wasserstein manifold. Inspired by this connection, we derive the discrete Langevin dynamics as a continuous time Markov chain by leveraging the gradient flow on the Wasserstein manifold consisting of discrete distributions. \item {\bf Designing Informed discrete Samplers}\quad The discrete Langevin dynamics provide a principled framework to design the informed samplers in discrete space. We discuss the numerical methods regarding discrete time simulations of the discrete Langevin dynamics and the approximations of the target information to efficiently implement informed sampling in discrete space with the help of modern accelerators like GPUs. We also derive an asymptotic theorem that allows us to adaptively tune the parameters in informed samplers. \item {\bf Applications}\quad We investigate the applications of informed sampling in discrete space, including Monte Carlo integration, combinatorial optimization, and generative modeling. We demonstrate the excellent performance of informed sampling compared to classical methods like Gibbs sampling. We also build a benchmark of sampling in discrete space to facilitate future research. \end{itemize}

Degree

thesis:*
Level thesis:degree_level
Doctoral
Department dc:contributor.department
Mathematics
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2023

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Sun, Haoran
Advisor dc:contributor.advisor
  • Koltchinskii, Vladimir
Committee members dc:contributor.committeemember
  • Zhang, Xiuwei
  • Dai, Bo
  • Zhou, Haomin
  • Schuurmans, Dale

Subjects

dc:subject × 16

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/1853/72713

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Sun, Haoran. Informed Sampling in Discrete Space, and its Applications. Doctoral thesis, Georgia Institute of Technology, 2023. https://hdl.handle.net/1853/72713