Quasi-Monte Carlo Integration via Algorithmic Discrepancy Theory
- Dr. Haotian Jiang
- Time: 2025-04-14 10:00
- Host: Dr. Shaofeng Jiang
- Venue: Room 204, Courtyard No.5, Jingyuan
Abstract
A classical approach to numerically integrating a function f is Monte Carlo (MC) methods. Here, one evaluates f at random points and the estimation error scales as \sigma(f)/n^{1/2} with n samples, where \sigma(f) is the standard deviation of f. A different approach, widely used in practice, is using quasi-Monte Carlo (QMC) methods, where f is evaluated at carefully chosen deterministic points and the error scales roughly as 1/n. Both methods have distinctive advantages and shortcomings, and a key question has been to find a method that combines the advantages of both.
In this talk, I will introduce the fascinating area of QMC methods and their connections to various areas of mathematics and to geometric discrepancy. I will then show how recent developments in algorithmic discrepancy theory can be used to give a method that combines the benefits of MC and QMC methods, and even improves upon previous QMC approaches in various ways.
The talk is based on joint work with Nikhil Bansal (University of Michigan).
Biography
Haotian Jiang is an assistant professor in the Computer Science Department at the University of Chicago. Previously, he obtained his PhD from the University of Washington under the supervision of Yin Tat Lee, and he was a Postdoctoral Researcher at Microsoft Research Redmond. His research focus on algorithm design for optimization problems, discrepancy theory, and high dimensional probability. He has received various recognitions for his work, including a best student paper award in SODA 2021 and a best paper award in SODA 2025.