Xiaoming Sun (Institute of Computing Technology, Chinese Academy of Sciences)
Title: Optimization from Structured Samples for Coverage and Influence Functions
Abstract: The optimization from samples (OPS) model studies how to optimize objective functions directly from sample data. For the maximum coverage problem, previous results showed that we cannot obtain a constant approximation ratio using polynomially many independent samples, even though coverage functions are PMAC learnable. In this talk, to circumvent the impossibility result of OPS, we propose a stronger model called optimization from structured samples (OPSS), where the data samples encode the structural information of the functions. Under three general assumptions on the sample distributions, we show that we can design efficient OPSS algorithms that achieve a constant approximation for the maximum coverage problem. We further prove constant lower bound under these assumptions, which is tight when the computational efficiency is not considering. We also extend our study to the task of influence maximization from cascade samples (IMS), and present constant approximation algorithms for this task under mild conditions on the seed set distribution. Comparing with prior solutions, our network inference algorithm requires weaker assumptions and does not rely on maximum-likelihood estimation and convex programming.
Bio: Xiaoming Sun is a professor at Institute of Computing Technology (ICT), Chinese Academy of Sciences (CAS). He got his bachelor and Ph. D. degree from computer science department, Tsinghua University China in 2001 and 2005, respectively. After graduated, he worked at Center for Advanced Study, Tsinghua University as an assistant professor (2005) and associate professor (2008). In 2011, he joined ICT, CAS as a professor. His research interests include quantum computing, decision tree complexity, communication complexity and approximation algorithms. He is currently the director of CCF Technical Committee on Theoretical Computer Science. He serves on the steering committee of COCOON conference and as an editorial board member of JCST, Journal of Software, Frontiers of Computer Science, and SCIENCE CHINA: Information Sciences.
Zhiyi Huang (University of Hong Kong)
Title: Recent progress in online matching
Abstract: Originated from the seminal work by Karp, Vazirani, and Vazirani (1990), online matching has been established as one of the most fundamental topics in the literature of online algorithms. This talk presents the basics of online matching, and surveys the recent progress in two directions:
1. Open problems about online advertising: AdWords and Display Ads are generalizations of the online bipartite matching problem by Karp et al. These problems capture online advertising which generates tens of billions of US dollars annually. This year, we introduce a new technique called online correlated selection, and design the first online algorithms for the general cases of AdWords and Display Ads outperforming greedy, which has remained the state of the art for more than 10 years, despite many attempts to find better alternatives.
2. General arrival models: Traditional online matching models consider bipartite graphs and assume knowing one side of the bipartite graph upfront. The matching problems in many modern scenarios, however, do not fit into the traditional models. In the problem of matching ride-sharing requests, for instance, the graph is not bipartite in general, and all vertices arrive online. There has been much progress in the past three years on online matching models beyond the traditional ones, including the fully online model, the general vertex arrival model, and the edge arrival model.
Bio: Zhiyi Huang is an associate professor of Computer Science at the University of Hong Kong. He works broadly on theoretical computer science. Before joining HKU, Zhiyi was a postdoc at Stanford University from 2013 to 2014, working with Tim Roughgarden. He obtained my 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, and an Early Career Award by RGC Hong Kong.