Zeroth-Order and First-Order Minimax Cubic Newton Algorithms for Nonconvex–Strongly Concave Minimax Problems

期刊论文
发表日期：

2025年10月13日

查看全文

Zhuo-Jin Zhong,
Jun-Lin Wang,
Zi Xu

摘要

Minimax problems have gained significant attention recently due to their broad applicability in fields like machine learning. While many existing optimization algorithms solve such problems using gradient and Hessian information, these derivatives can be computationally prohibitive or unavailable in certain applications. This paper introduces a zeroth-order minimax cubic Newton (ZO-MCN) method and a first-order minimax cubic Newton (FO-MCN) method for nonconvex–strongly concave minimax optimization. ZO-MCN employs zeroth-order gradient estimators, while FO-MCN utilizes first-order Hessian estimators for variable updates. Each iteration performs multiple gradient ascent steps to update the variable y and applies cubic regularization steps to update the variable x. We establish that both algorithms achieve the best known iteration complexity $\mathcal {O}(\varepsilon ^{-1.5})$ $O (ε^{- 1.5})$ for finding an $\varepsilon $ $ε$ -first-order stationary point, matching the state-of-the-art second-order methods for solving nonconvex–strongly concave minimax optimization problems.