First-order Methods for Nonconvex–Nonconcave Minimax Optimization

Abstract: We study a class of nonconvex–nonconcave minimax problems in which the inner maximization problem satisfies a local Kurdyka–Łojasiewicz (KL) condition that may vary with the outer minimization variable. In contrast to the global KL or PL conditions commonly assumed in the literature—which are significantly stronger and often too restrictive in practice—this local KL condition accommodates a broader range of practical scenarios. However, it also introduces new analytical challenges. In particular, as an optimization algorithm approaches a stationary point, the region over which the KL condition holds may shrink, leading to a more intricate and potentially ill-conditioned landscape. To address this challenge, we show that the associated maximal function is locally generalized Hölder smooth. Leveraging this key property, we develop an inexact proximal gradient method for solving the minimax problem, where the inexact gradient of the maximal function is computed by applying a proximal gradient or sequential convex programming method to a KL-structured subproblem. Under mild assumptions, we establish complexity guarantees for computing an approximate stationary point of the minimax problem.

This is joint work with Xiangyuan Wang (University of Minnesota).
 

Bio: Zhaosong Lu is a Full Professor in the Department of Industrial and Systems Engineering at the University of Minnesota. He received his Ph.D. in Operations Research from Georgia Tech. His research focuses on the theory and algorithms of continuous optimization, with applications in data science and machine learning. Dr. Lu has published extensively in leading journals, and his research has been supported by major funding agencies, including AFOSR, NSF, and ONR. He has served on several prize committees, such as the INFORMS George Nicholson Prize Committee and the ICCOPT Best Paper Award Committee. He has also served as an Associate Editor for leading journals, including Mathematics of Operations Research, SIAM Journal on Optimization, Computational Optimization and Applications, and Journal of Global Optimization.