A Single-Loop Accelerated Extra-Gradient Difference Algorithm with Improved Complexity Bounds for Constrained Minimax Optimization

In this paper, we propose a novel extra-gradient difference acceleration algorithm for solving constrained nonconvex-nonconcave (NC-NC) minimax problems. In particular, we design a new extra-gradient difference step to obtain an important quasi-cocoercivity property, which plays a key role to significantly improve the convergence rate in the constrained NC-NC setting without additional structural assumption. Then momentum acceleration is also introduced into our dual accelerating update step. Moreover, we prove that, to find an (cid:15) -stationary point of the function f , our algorithm attains the complexity O ( (cid:15) − 2 ) in the constrained NC-NC setting, while the best-known complexity bound is (cid:101) O ( (cid:15) − 4 ) , where (cid:101) O ( · ) hides logarithmic factors compared to O ( · ) . As the special cases of the constrained NC-NC setting, our algorithm can also obtain the same complexity O ( (cid:15) − 2 ) for both the nonconvex-concave (NC-C) and convex-nonconcave (C-NC) cases, while the best-known complexity bounds are (cid:101) O ( (cid:15) − 2 . 5 ) for the NC-C case and (cid:101) O ( (cid:15) − 4 ) for the C-NC case. For fair comparison with existing algorithms, we also analyze the complexity bound to find (cid:15) -stationary point of the primal function φ for the constrained NC-C problem, which shows that our algorithm can improve the complexity bound from (cid:101) O ( (cid:15) − 3 ) to O ( (cid:15) − 2 ) . To the best of our knowledge, this is the first time that the proposed algorithm improves the best-known complexity bounds from O ( (cid:15) − 4 ) and (cid:101) O ( (cid:15) − 3 ) to O ( (cid:15) − 2 ) in both the NC-NC and NC-C settings