题　目：Instance-dependent Sample Complexity for Bilinear Saddle-Point Optimization with Noisy Feedback

嘉　宾：姜嘉硕 助理教授 香港科技大学

主持人：许欢 教授 上海交通大学安泰经济与管理学院

时　间：2025年6月9日（周一）14:00-15:30

地　点：安泰楼B207室

内容简介：

In this work, we study the sample complexity of finding a Nash Equilibrium (NE) of two-player zero-sum matrix games with noisy feedback. We propose a novel algorithm based on resolving linear programs (LP), achieving an ξ\epsilonξ-approximate NE with an instance-dependent sample complexity for general ξm_1\times m_2ξ game matrices, while being robust by enjoying a worst-case sample complexity at the same time. To our knowledge, this result provides the first instance-dependent sample complexity for general-dimension matrix games under noisy feedback and non-unique NE. Our algorithm is inspired by recent advances in online resource allocation and includes two key components: first, identifying a support set of the NE, and second, determining the unique NE within this support. Both steps rely on a careful analysis of the performance of solving the LP constructed by noisy samples. This is a joint work with Mengxiao Zhang.

演讲人简介：

Jiashuo Jiang is currently an assistant professor at HKUST. He works at the intersection of machine learning, optimization, and operations management, with a focus on online decision making. Prior to joining HKUST, he obtains his PhD degree in Operations Research from NYU Stern School of Business, working with Prof Jiawei Zhang and Prof Will Ma.

欢迎广大师生参加！