主讲人
Lesi Chen
Tsinghua University
时间
2026年9月8日 星期二
上午 10:00-11:00
地点
学院104会议室
Abstract
In this talk, we present our recent progress on the complexity of game-structured optimization problems. Part I addresses minimax optimization for computing Nash equilibria in zero-sum simultaneous games. While optimal first-order/gradient complexity has been settled for twenty years, the optimal complexity for second-order/Newton methods remained open. We present a novel second-order algorithm achieving an $O(1/T^{1.75})$ convergence rate, surpassing the long-standing $O(1/T^{1.5})$ rate (Monteiro & Svaiter, 2012) previously conjectured to be optimal (Chen et al., COLT 2025 Best Student Paper). Part II examines the more general bilevel optimization for computing Stackelberg equilibria in general-sum sequential games. Prior optimal $O(1/T^{0.5})$ algorithms depended on a Hessian-vector-product (HVP) oracle, while fully first-order methods without HVP achieved only a suboptimal $O(1/T^{0.33})$ rate (Kwon et al., 2023). Through a tighter local smoothness control, we improve the latter fully first-order methods to optimal up to logarithmic factors (Chen et al., JMLR 2025). Finally, we introduce a new nested chain framework to establish new complexity lower bounds regarding condition-number dependence in bilevel optimization, unearthing fundamental limits and promising directions for future research.
Biography
