Title: Informed Sampling in Discrete Space, and its Applications

Date: 07/18/2023

Time: 11:00 AM 

Location: https://gatech.zoom.us/j/7718148377?pwd=OWFleTNkNnhoUXJuQjk4NlpJdVFEZz09

Join our Cloud HD Video Meeting

Haoran Sun

Machine Learning Ph.D. Student

School of Mathematics
Georgia Institute of Technology

Committee

Vladimir Koltchinskii (Advisor)

Xiuwei Zhang    

Bo Dai

Haomin Zhou

Dale Schuurmans

Abstract

Sampling has been an important problem in physics, statistics, computer science, and machine learning. 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, informed sampling in discrete space is 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

• Discrete Langevin Dynamics, from which the gradient-based sampling algorithms in discrete space are designed.

• Algorithm Design, 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. 

• Applications, we investigate the applications of informed sampling in discrete space, including Monte Carlo integration, combinatorial optimization, and generative modeling.