Sampling Algorithms for Gibbs Distributions

Speaker:Dr. Weiming Feng
        The Institute for Theoretical Studies
        ETH Zürich

Title:  "Sampling Algorithms for Gibbs Distributions"

Date:   Monday, 5 February 2024

Time:   4:00pm - 5:00pm

Venue:  Lecture Theater F
        (Leung Yat Sing Lecture; near lift 25/26), HKUST


Abstract:

The Gibbs distribution is a high-dimensional distribution defined by local
interactions. It has been extensively studied in probability theory,
statistical physics, computer science and machine learning, often under
different names such as the spin system or the Markov random field.
Sampling is the central computational task for Gibbs distributions, which
requires the algorithm to generate a random sample from the input
distribution in polynomial time.

In this talk, I will introduce my research on sampling algorithms for
Gibbs distributions. The Markov chain Monte Carlo (MCMC) is a simple and
widely used approach for sampling. I will introduce our recent works on
theoretical analysis of MCMC algorithms. In addition, I will describe a
new sampling technique based on projection, which gives fast sampling
algorithms when standard MCMC algorithms fail. Applications of the new
technique include sampling uniform CNF formula solutions under a local
lemma condition. Finally, I will briefly overview my research on
distributed/parallel sampling and approximate counting.


*****************
Biography:

Weiming Feng is a junior fellow at the Institute for Theoretical Studies,
ETH Zürich. In the fall of 2023, he was a research fellow at the Simons
Institute for the Theory of Computing, UC Berkeley. From Oct 2021 to Sep
2023, he was a research associate at The University of Edinburgh. He
received his PhD degree in computer science at Nanjing University in June
2021, where he was advised by Prof. Yitong Yin. His research interests lie
in theoretical computer science, with an emphasis on randomized
algorithms, approximate sampling and counting algorithms, and Markov chain
Monte Carlo (MCMC) theory.