Speaker:
Baoxiang Wang(assistant professor in the Chinese University of Hong Kong)
Time:
- 10:00-11:00 (Time in Beijing)
- 15:00-16:00 (Time in Auckland)
- December 3, 2021 (Friday)
Venue:
B1-518B, Research Building 4
Abstract:
A k-submodular function is a pairwise monotone function that given k
disjoint subsets outputs a value that is submodular in every orthant. In this paper, we provide a new framework for k-submodular maximization problems, by relaxing the optimization to the continuous space with the multilinear extension of k– submodular functions and a variant of pipage rounding that recovers the discrete solution. When the function is monotone, we propose a simple algorithm that achieves almost \frac{1}{2}-approximation for unconstrained maximization and maximization under total size and knapsack constraints. This result is asymptotically optimal. The multilinear extension introduces new insights to analyze and optimize k-submodular functions. Based on joint work with Huanjian Zhou.
Speaker Bio:
王趵翔现为香港中文大学（深圳）数据科学学院助理教授。王趵
翔于2014年在上海交通大学获信息安全专业工程学士学位；其后于2020年在香
港中文大学计算机科学与工程系获博士学位。就读博士期间，他曾在阿尔伯塔
大学和加拿大皇家银行长期访问。王趵翔的研究方向包括强化学习，在线学习，
和学习理论等。他的研究成果发表在ITCS, NeurIPS, ICML, ICLR等会议。他关于The Gambler’s problem的研究解决了强化学习教科书中的开放问题，并证明
了强化学习中的混沌现象。