Monday / CS Seminar

February 5th / 12:00 PM

In Person / Mudd 3514

Speaker

June Vuong, Stanford University

Talk Title

Towards optimal sampling algorithms

Abstract

Sampling is a fundamental task with applications in many different areas from probabilistic inference to generative artificial intelligence and fairness. Many sampling problems involve high-dimensional and complex target distributions, making naive heuristics ineffective. Markov chains are widely employed for sampling and are believed to be highly efficient. However, existing studies on Markov chains either provide suboptimal runtime guarantees or are limited to specific settings.

In this talk, I will give the best possible bound on the runtime of Markov chain algorithms in the most general setting possible using "entropic independence", a framework that I have developed in the past few years. My work results in simple and optimally fast algorithms and has settled many long-standing open problems. The technical tools I develop for analyzing Markov chains have also found unexpected applications in other algorithmic tasks such as learning and optimization.

Biography

Thuy-Duong "June" Vuong is a fifth-year PhD student at Stanford advised by Nima Anari and Moses Charikar. She completed her undergraduate at MIT in 2019, double majoring in Mathematics and Computer Science. Her research is in designing and analyzing algorithms for sampling, particularly Markov chains. Her research has been supported by a Microsoft PhD Fellowship.

Research Interests/Area

Theory, Algorithms Design, Algorithm for sampling, Markov chains