A first-order method for constrained nonconvex--nonconcave minimax problems under a local Kurdyka-Łojasiewicz condition
This provides theoretical convergence guarantees for a challenging class of minimax optimization problems, though it appears incremental as it extends existing methods with new assumptions.
The authors tackled constrained nonconvex-nonconcave minimax problems with complex inner constraints by developing an inexact proximal gradient method that uses sequential convex programming to compute gradients, establishing convergence rates and complexity guarantees for finding approximate stationary points under a local Kurdyka-Łojasiewicz condition.
We study a class of constrained nonconvex--nonconcave minimax problems in which the inner maximization involves potentially complex constraints. Under the assumption that the inner problem of a novel lifted minimax problem satisfies a local Kurdyka-Łojasiewicz (KL) condition, we show that the maximal function of the original problem enjoys a local Hölder smoothness property. We also propose a sequential convex programming (SCP) method for solving constrained optimization problems and establish its convergence rate under a local KL condition. Leveraging these results, we develop an inexact proximal gradient method for the original minimax problem, where the inexact gradient of the maximal function is computed via the SCP method applied to a locally KL-structured subproblem. Finally, we establish complexity guarantees for the proposed method in computing an approximate stationary point of the original minimax problem.