Ph.D. student Lesi Chen and Assistant Professor Jingzhao Zhang from 蜜桃app'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：
Editor: Li Han
