Accelerated Primal-dual Scheme for a Class of Stochastic Nonconvex-concave Saddle Point Problems

Stochastic nonconvex-concave min-max saddle point problems appear in many machine learning and control problems including distributionally robust optimization, generative adversarial networks, and adversarial learning. In this paper, we consider a class of nonconvex saddle point problems where the objective function satisfies the Polyak-Lojasiewicz condition with respect to the minimization variable and it is concave with respect to the maximization variable. The existing methods for solving nonconvex-concave saddle point problems often suffer from slow convergence and/or contain multiple loops. Our main contribution lies in proposing a novel single-loop accelerated primal-dual algorithm with new convergence rate results appearing for the first time in the literature, to the best of our knowledge. In particular, in the stochastic regime, we demonstrate a convergence rate of mathcal O(ε-4) to find an ε-gap solution which can be improved to mathcal O(ε-2) in deterministic setting.