Fast Extra Gradient Methods for Smooth Structured Nonconvex-Nonconcave Minimax Problems

Modern minimax problems, such as generative adversarial network and adversarial training, are often under a nonconvex-nonconcave setting, and developing an efficient method for such setting is of interest. Recently, two variants of the extragradient (EG) method are studied in that direction. First, a two-time-scale variant of the EG, named EG, was proposed under a smooth structured nonconvex-nonconcave setting, with a slow \mathcal{O}(1/k) rate on the squared gradient norm, where k denotes the number of iterations. Second, another variant of EG with an anchoring technique, named extra anchored gradient (EAG), was studied under a smooth convex-concave setting, yielding a fast \mathcal{O}(1/k 2) rate on the squared gradient norm. Built upon EG and EAG, this paper proposes a two-time-scale EG with anchoring, named fast extragradient (FEG), that has a fast \mathcal{O}(1/k 2) rate on the squared gradient norm for smooth structured nonconvex-nonconcave problems; the corresponding saddle-gradient operator satisfies the negative comonotonicity condition.