Multilinear extension of k-submodular functions
- Speaker
- Baoxiang Wang
- Affiliation
- assistant professor in the Chinese University of Hong Kong
- Date
- Time
- – Asia/Shanghai
- 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的研究解决了强化学习教科书中的开放问题，并证明
了强化学习中的混沌现象。
Schedule
- 10:00-11:00 (Time in Beijing)
- 15:00-16:00 (Time in Auckland)
- December 3, 2021 (Friday)