Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems

We consider nonconvex-concave minimax optimization problems of the form minbf xmax_bf y∈mathcal Y f(bf x,bf y), where f is strongly-concave in bf y but possibly nonconvex in bf x and mathcal Y is a convex and compact set. We focus on the stochastic setting, where we can only access an unbiased stochastic gradient estimate of f at each iteration. This formulation includes many machine learning applications as special cases such as robust optimization and adversary training. We are interested in finding an mathcal O(varepsilon)-stationary point of the function Phi(·)=max_bf y∈mathcal Y f(·, bf y). The most popular algorithm to solve this problem is stochastic gradient decent ascent, which requires mathcal O(kappa3varepsilon-4) stochastic gradient evaluations, where kappa is the condition number. In this paper, we propose a novel method called Stochastic Recursive gradiEnt Descent Ascent (SREDA), which estimates gradients more efficiently using variance reduction. This method achieves the best known stochastic gradient complexity of mathcal O(kappa3varepsilon-3), and its dependency on varepsilon is optimal for this problem.