On the Complexity of Optimization Problems with Game Structures

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.

About the speaker

Lesi Chen is a fourth-year Ph. D. student in the Institute for Interdisciplinary Information Sciences (IIIS), Tsinghua University, supervised by Prof. Jingzhao Zhang. He received a Bachelor's degree in the School of Data Science (SDS), Fudan University, advised by Prof. Luo Luo. His research areas lie in optimization (OPT), particularly at the intersection with artificial intelligence (AI), theoretical computer science (TCS), and game theory. His work has been awarded the COLT 2025 Best Student Paper and selected for an Oral Presentation at ICLR 2025.