Ph.D. student Lesi Chen and Assistant Professor Jingzhao Zhang from Tsinghua University's Institute for Interdisciplinary Information Sciences have received the Best Student Paper Award at the 2025 Conference on Learning Theory (COLT), a top-tier venue in theoretical machine learning. Their winning work is titled "Solving Convex-Concave Problems with O( ε^-4/7) Second-Order Oracle Complexity".
The paper tackles a fundamental challenge in numerical optimization: solving convex-concave (min-max) problems. These problems involve computing saddle points of functions that are convex in one variable and concave in another. Such formulations arise in diverse applications, including finding Nash equilibria in two-player zero-sum games, solving Lagrangian duals of constrained optimization problems, distributionally robust optimization, and adversarial training in machine learning.
The min-max problem has a long history. In 1976, Russian mathematician Korpelevich introduced the extragradient method, which remains widely used and achieves an optimal O( ε^-1) complexity among first-order (gradient-based) methods. In 2012, Monteiro and Svaiter extended this to second-order methods, leveraging both gradients and Hessians, and achieved an improved complexity of O (ε^-2/3). Despite further research over the past decade, no better rate had been found for second-order methods, leading prominent scholars like Michael I. Jordan and Yurii Nesterov to suggest that O (ε^-2/3) might be the fundamental limit.
Challenging this belief, Chen and co-authors developed a novel algorithm that finds an ε-approximate saddle point with a second-order oracle complexity of O (ε^-4/7), improving upon the long-standing bound. The key innovation lies in applying a high-order momentum acceleration technique—originally introduced by Monteiro and Svaiter—simultaneously to both the minimization and maximization variables. This reduces the original problem to solving O (ε^-4/7) well-conditioned subproblems, each of which can be handled using existing solvers.
This breakthrough result shows that once second-order information is available, one can indeed outperform the extragradient method, reshaping the theoretical understanding of min-max optimization and providing a foundation for faster algorithmic development.
Lesi Chen, a Ph.D. student admitted in 2023, is the first author of the paper. The corresponding author is Jingzhao Zhang. Additional co-authors include Chengchang Liu, a Ph.D. student at The Chinese University of Hong Kong, and Luo Luo, a junior research fellow at Fudan University.
Paper Link：//arxiv.org/abs/2506.08362
Correspondent: Yueliang Mona Jiang
Editor: Xiamin Lv
Reviewer: Xiongfeng Ma
