Zeroth-order single-loop algorithms for nonconvex-linear minimax problems

Nonconvex minimax problems have attracted significant interest in machine learning and many other fields in recent years. In this paper, we propose a new zeroth-order alternating randomized gradient projection algorithm to solve smooth nonconvex-linear problems and its iteration complexity to find an $$\varepsilon $$ ε -first-order Nash equilibrium is $${\mathcal {O}}\left( \varepsilon ^{-3} \right) $$ O ε - 3 and the number of function value estimation per iteration is bounded by $${\mathcal {O}}\left( d_{x}\varepsilon ^{-2} \right) $$ O d x ε - 2 . Furthermore, we propose a zeroth-order alternating randomized proximal gradient algorithm for block-wise nonsmooth nonconvex-linear minimax problems and its corresponding iteration complexity is $${\mathcal {O}}\left( K^{\frac{3}{2}} \varepsilon ^{-3} \right) $$ O K 3 2 ε - 3 and the number of function value estimation is bounded by $${\mathcal {O}}\left( d_{x}\varepsilon ^{-2} \right) $$ O d x ε - 2 per iteration. The numerical results indicate the efficiency of the proposed algorithms.