Zeroth-order primal-dual alternating projection gradient algorithms for nonconvex minimax problems with coupled linear constraints

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 zeroth-order primal-dual alternating projected gradient algorithm and the zeroth-order regularized momentum primal-dual projected gradient (ZO-RMPDPG) algorithm, for solving deterministic and stochastic nonconvex-(strongly) concave minimax problems with coupled linear constraints. The iteration complexities of the two proposed algorithms to obtain an <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="epsilon"> <mml:semantics> <mml:mi> ε </mml:mi> <mml:annotation encoding="application/x-tex">\varepsilon</mml:annotation> </mml:semantics> </mml:math> </inline-formula> -stationary point are proved to be <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper O left-parenthesis epsilon Superscript negative 2 Baseline right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">O</mml:mi> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:msup> <mml:mi> ε </mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo> − </mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathcal {O}(\varepsilon ^{-2})</mml:annotation> </mml:semantics> </mml:math> </inline-formula> (resp. <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper O left-parenthesis epsilon Superscript negative 4 Baseline right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">O</mml:mi> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:msup> <mml:mi> ε </mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo> − </mml:mo> <mml:mn>4</mml:mn> </mml:mrow> </mml:msup> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathcal {O}(\varepsilon ^{-4})</mml:annotation> </mml:semantics> </mml:math> </inline-formula> ) for solving nonconvex-strongly concave (resp. nonconvex-concave) minimax problems with coupled linear constraints under deterministic settings and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="ModifyingAbove script upper O With tilde left-parenthesis epsilon Superscript negative 3 Baseline right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mover> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">O</mml:mi> </mml:mrow> <mml:mo stretchy="false"> ~ </mml:mo> </mml:mover> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:msup> <mml:mi> ε </mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo> − </mml:mo> <mml:mn>3</mml:mn> </mml:mrow> </mml:msup> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\tilde {\mathcal {O}}(\varepsilon ^{-3})</mml:annotation> </mml:semantics> </mml:math> </inline-formula> (resp. <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="ModifyingAbove script upper O With tilde left-parenthesis epsilon Superscript negative 6.5 Baseline right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mover> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">O</mml:mi> </mml:mrow> <mml:mo stretchy="false"> ~ </mml:mo> </mml:mover> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:msup> <mml:mi> ε </mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo> − </mml:mo> <mml:mn>6.5</mml:mn> </mml:mrow> </mml:msup> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\tilde {\mathcal {O}}(\varepsilon ^{-6.5})</mml:annotation> </mml:semantics> </mml:math> </inline-formula> ) 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. The proposed ZO-RMPDPG algorithm, when specialized to stochastic nonconvex-concave minimax problems without coupled constraints, outperforms all existing zeroth-order algorithms by achieving a better iteration complexity, thus setting a new state-of-the-art.