An Efficient Stochastic First-Order Algorithm for Nonconvex--Strongly Concave Minimax Optimization beyond Lipschitz Smoothness

Abstract

In recent years, nonconvex minimax problems have attracted significant attention because of their broad applications in machine learning, including generative adversarial networks, robust optimization and adversarial training. Most existing algorithms for nonconvex stochastic minimax problems are developed under the standard Lipschitz smoothness assumption. In this paper, we study stochastic minimax problems under a generalized smoothness condition and propose an algorithm, NSGDA-M, which simultaneously updates the inner variable by stochastic gradient ascent and updates the outer variable by normalized stochastic gradient descent with momentum. When the objective function is nonconvex--strongly concave, we show that NSGDA-M finds an \(ε\)-stationary point of the primal function within \(\mathcal O(ε^{-4}\log(1/(εδ)))\) stochastic gradient evaluations with probability at least \(1-δ\). Moreover, we establish an expected stationarity guarantee of \(\mathcal O(δ^{-3/4}T^{-1/4})+G_Φδ\), which gives a convergence rate \(\mathcal O(T^{-1/7})\). Here \(G_Φ\) bounds the primal gradient norms along the iterates. Numerical experiments on a distributionally robust optimization problem demonstrate the effectiveness of the proposed algorithm.

24 pages, 9 figures