Presenter
Kuang Xu
Associate Professor of Operations, Information and Technology,
Stanford Graduate School of Business
Abstract
I will discuss in this talk a new diffusion-asymptotic analysis for sequentially randomized experiments. Rather than taking sample size n to infinity while keeping the problem parameters fixed, we let the mean signal level scale to the order 1/\sqrt{n} so as to preserve the difficulty of the learning task as n gets large. In this regime, we show that the behavior of a class of methods for sequential experimentation converges to a diffusion limit. This connection enables us to make sharp performance predictions and obtain new insights on the behavior of Thompson sampling. Our diffusion asymptotics also help resolve a discrepancy between the Θ(log(n)) regret predicted by the fixed-parameter, large-sample asymptotics on the one hand, and the Θ(\sqrt{n}) regret from worst-case, finite-sample analysis on the other, suggesting that it is an appropriate asymptotic regime for understanding practical large-scale sequential experiments.
Reference
https://arxiv.org/pdf/2101.09855.pdf
Bio
Kuang Xu is an Associate Professor of Operations, Information and Technology at Stanford Graduate School of Business, and Associate Professor by courtesy with the Electrical Engineering Department, Stanford University. Born in Suzhou, China, he received the B.S. degree in Electrical Engineering (2009) from the University of Illinois at Urbana-Champaign, and the Ph.D. degree in Electrical Engineering and Computer Science (2014) from the Massachusetts Institute of Technology. His research primarily focuses on understanding fundamental properties and design principles of large-scale stochastic systems using tools from probability theory and optimization, with applications in queueing networks, healthcare, privacy and machine learning. He received First Place in the INFORMS George E. Nicholson Student Paper Competition (2011), the Best Paper Award, as well as the Kenneth C. Sevcik Outstanding Student Paper Award at ACM SIGMETRICS (2013), and the ACM SIGMETRICS Rising Star Research Award (2020). He currently serves as an Associate Editor for Operations Research.