In this paper, we study zeroth-order algorithms for nonconvex minimax problems with coupled linear constraints under the deterministic and stochastic settings, which have attracted wide attention in machine learning, signal processing and many other fields in recent years, e.g., adversarial attacks in resource allocation problems and network flow problems etc. We propose two single-loop algorithms, namely the zero-order primal-dual alternating projected gradient (ZO-PDAPG) algorithm and the zero-order regularized momentum primal-dual projected gradient algorithm (ZO-RMPDPG), for solving deterministic and stochastic nonconvex-(strongly) concave minimax problems with coupled linear constraints. The iteration complexity of the two proposed algorithms to obtain an $\varepsilon$-stationary point are proved to be $\mathcal{O}(\varepsilon ^{-2})$ (resp. $\mathcal{O}(\varepsilon ^{-4})$) for solving nonconvex-strongly concave (resp. nonconvex-concave) minimax problems with coupled linear constraints under deterministic settings and $\tilde{\mathcal{O}}(\varepsilon ^{-3})$ (resp. $\tilde{\mathcal{O}}(\varepsilon ^{-6.5})$) under stochastic settings respectively. To the best of our knowledge, they are the first two zeroth-order algorithms with iterative complexity guarantees for solving nonconvex-(strongly) concave minimax problems with coupled linear constraints under the deterministic and stochastic settings.

研究零阶算法求解非凸最小最大问题在确定性和随机设置下的紧密线性约束，为确定性和随机设置下求解非凸凹最小最大问题提出两种单环算法，即零阶原始--对偶交替投影梯度（ZO-PDAPG）算法和零阶正则化动量原始--对偶投影梯度算法（ZO-RMPDPG），其迭代复杂度被证明为Ο(ε^(-2))（非凸凹最小最大问题）和Ο(ε^(-4))（非凸凹最小最大问题），在确定性设置下，持有ε-稳定点，并且在随机设置下，迭代复杂度分别为Ο̃(ε^(-3))和Ο̃(ε^(-6.5))。据我们所知，它们是第一个能够解决确定性和随机设置下的非凸凹最小最大问题的零阶算法，并具有迭代复杂度保证。

零阶原始-对偶交替投影梯度算法用于带有耦合线性约束的非凸极小极大问题