Sample Complexity of Optimal Auctions

Speaker: Dr. Zhiyi HUANG
         Department of Computer Science
         University of Hong Kong

Title:  "Sample Complexity of Optimal Auctions"

Date:   Monday, 27 February 2023

Time:   10:00am - 11:00am

Venue:  Room 1511 (near lift 27/28), HKUST


Abstract:

Classical optimal auction theory assumes that bidders' values are drawn
from a known distribution. In reality, the source of such prior
information is really past data. Cole and Roughgarden (2014) modeled past
data as i.i.d. samples from the value distribution and asked: How many
samples are sufficient/necessary to learn a near optimal auction? This
talk introduces a unified theory that yields tight sample complexity
bounds for auctions with homogeneous goods, and gives state-of-the-art
sample complexity bounds for auctions with heterogeneous goods. The theory
further extends to several Bayesian optimization problems in optimal
stopping, including Prophet Inequality and Pandora's Box. Unlike
conventional statistical learning theory which focuses on the complexity
of hypothesis classes, our new theory relies on the simplicity of data
distributions and a monotonicity property of these problems.


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

Zhiyi is an associate professor of Computer Science at the University of
Hong Kong. He works broadly on Theoretical Computer Science and
Algorithmic Game Theory. Before joining HKU, Zhiyi was a postdoc at
Stanford University from 2013 to 2014, working with Tim Roughgarden. He
obtained his Ph.D. from the University of Pennsylvania under Sampath
Kannan and Aaron Roth in 2013. During grad school, Zhiyi interned at
Microsoft Research Redmond under Nikhil R. Devanur in the summers of 2011
and 2012. Before that he got a bachelor degree from the first "Yao Class"
under Andrew Yao at Tsinghua University in 2008. Zhiyi was the recipient
of the Best Paper Awards of FOCS 2020 and SPAA 2015, an Excellent Young
Scientists Fund (HK & Macau) by NSFC, an Early Career Award by RGC Hong
Kong, a Morris and Dorothy Rubinoff Dissertation Award, and a Simons
Graduate Fellowship in Theoretical Computer Science.