In this paper, we study second-order methods for solving convex-strongly concave minimax problems, which have attracted much attention in recent years due to their wide application in machine learning and related fields. We propose a minimax Levenberg–Marquardt (MLM) algorithm to solve convex-strongly concave minimax optimization problems, where the regularization coefficient is proportional to the root mean square of the gradient norm. The iteration complexity of the MLM algorithm to obtain an \(\varepsilon \) -optimal solution is bounded by \(\mathcal {O}(\ell ^{3/2}\rho ^{1/2}\mu ^{-3/2}\varepsilon ^{-1/2})\) , where \(\mu \) is the strongly concave coefficient, and \(\ell \) and \(\rho \) are the Lipschitz constants of the gradient and Jacobian matrix, respectively. We further develop an accelerated variant of the MLM algorithm (AMLM) through a novel “contracting proximal” framework, which improves the iteration complexity to \(\tilde{\mathcal {O}}(\ell \rho ^{1/3}\mu ^{-1}\varepsilon ^{-1/3})\) . To the best of our knowledge, the iteration complexity of the proposed AMLM algorithm is the best among the current second-order methods for solving convex-strongly concave minimax problems. Numerical results verify the efficiency of the proposed algorithm.
