Data-driven Auction Design II: Progress via Statistical Learning Theory
- Prof. Zhiyi Huang, University of Hong Kong
- Time: 2023-09-20 19:00
- Host: Dr. Shaofeng Jiang
- Venue: Room 204, Courtyard No.5, Jingyuan
Abstract
The sample complexity of optimal auctions is a special case of the generalization problem in general learning (see, for example, the textbook formulation by Vapnik, 1998). Therefore, researchers have turned to statistical learning theory to understand the sample complexity of auctions. Conventional wisdom from learning theory asserts that the sample complexity is determined by the "degree of freedom" of the solution space, which in this case is the set of all possible auctions.
The second part of the lecture series will present a direct proof of an upper bound for the "degree of freedom" of single-item, multi-bidder auctions. As applications, we will derive sample complexity upper bounds for the single-item multi-bidder case. We will also mention several metrics for "degree of freedom" from learning theory that yield essentially the same bounds. Finally, we will explain how to extend the basic techniques from part one to establish lower bounds for the single-item, multi-bidder case. However, the upper and lower bounds will differ by a polynomial factor. We will have to wait for part three to resolve this gap and to further generalize the results to all single-parameter auctions and beyond.
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, with a focus on optimization and decision-making under uncertainty. 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, and a Morris and Dorothy Rubinoff Dissertation Award.