----------------------------------------------------------------------------------------------------







     Department of Systems Engineering and Engineering Management



                        The Chinese University of Hong Kong



----------------------------------------------------------------------------------------------------



Date: Friday, March 14, 4:00 pm – 5:30 pm



Venue: ERB 513, The Chinese University of Hong Kong



Title: Online Ad Allocation via Relax-and-Round



Speaker: Professor Zhiyi Huang, University of Hong Kong



Abstract: We initiate the study of Stochastic Online Correlated

Selection (SOCS), a family of online rounding algorithms for the

general Non-IID model of Stochastic Online Submodular Welfare

Maximization and its special cases such as unweighted and

vertex-weighted Online Stochastic Matching, Stochastic AdWords, and

Stochastic Display Ads. At each time step, the algorithm sees the type

of an online item and a fractional allocation of the item, then

immediately allocates the item to an agent. We propose a metric called

the convergence rate that measures the quality of SOCS algorithms in

the above special cases. This is cleaner than most metrics in the

related Online Correlated Selection (OCS) literature and may be of

independent interest. Following this framework, we make progress on

numerous problems including two open questions related to AdWords.



This talk is based on a paper published in FOCS 2024

(https://arxiv.org/abs/2408.12524)





Bio: Zhiyi Huang is an Associate Professor of Computer Science at the

University of Hong Kong. Before joining HKU, he was a postdoc at

Stanford University from 2013 to 2014, working with Tim Roughgarden.

He earned his Ph.D. from the University of Pennsylvania under the

supervision of Sampath Kannan and Aaron Roth in 2013, and a bachelor's

degree in 2008 from the first "Yao Class" founded by Andrew Chi-Chih

Yao at Tsinghua University.



Zhiyi works broadly on algorithms, focusing on the role of

information—and its flip-side, uncertainty—in computation. He is

interested in algorithms for sequential decision-making under

uncertainty (online algorithms), learning based on different forms of

information (learning theory), incentivizing self-interested agents to

share private information (mechanism design), and disclosing one kind

of information while keeping the other confidential (differential

privacy).



Zhiyi's research was recognized by several Best Paper Awards,

including those from ESA 2024 (Track S), FOCS 2020, and SPAA 2015. He

was also the recipient of 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.