Derivative-Free Alternating Projection Algorithms for General Nonconvex-Concave Minimax Problems
Zi Xu, Ziqi Wang, Jingjing Shen, Yu‐Hong Dai
Abstract
.In this paper, we study zeroth-order algorithms for nonconvex-concave minimax problems, which have attracted much attention in machine learning, signal processing, and many other fields in recent years. We propose a zeroth-order alternating randomized gradient projection (ZO-AGP) algorithm for smooth nonconvex-concave minimax problems; its iteration complexity to obtain an \(\varepsilon\)-stationary point is bounded by \(\mathcal{O}(\varepsilon^{-4})\), and the number of function value estimates is bounded by \(\mathcal{O}(d_{x}+d_{y})\) per iteration. Moreover, we propose a zeroth-order block alternating randomized proximal gradient algorithm (ZO-BAPG) for solving blockwise nonsmooth nonconvex-concave minimax optimization problems; its iteration complexity to obtain an \(\varepsilon\)-stationary point is bounded by \(\mathcal{O}(\varepsilon^{-4})\), and the number of function value estimates per iteration is bounded by \(\mathcal{O}(K d_{x}+d_{y})\). To the best of our knowledge, this is the first time zeroth-order algorithms with iteration complexity guarantee are developed for solving both general smooth and blockwise nonsmooth nonconvex-concave minimax problems. Numerical results on the data poisoning attack problem and the distributed nonconvex sparse principal component analysis problem validate the efficiency of the proposed algorithms.Keywordsnonconvex-concave minimax problemzeroth-order algorithmalternating randomized gradient projection algorithmalternating randomized proximal gradient algorithmcomplexity analysismachine learningMSC codes90C4790C2690C30