Improved Algorithms for Convex-Concave Minimax Optimization

This paper studies minimax optimization problems minx maxy f(x,y), where f(x,y) is mx-strongly convex with respect to x, my-strongly concave with respect to y and (Lx,Lxy,Ly)-smooth. Zhang et al. provided the following lower bound of the gradient complexity for any first-order method: OmegaBigl(√fracLxmx+fracLxy2mx my+fracLymyln(1/ε)Bigr). This paper proposes a new algorithm with gradient complexity upper bound tildeOBigl(√fracLxmx+fracL· Lxymx my+fracLymylnleft(1/εright)Bigr), where L=maxLx,Lxy,Ly. This improves over the best known upper bound tildeOleft(√fracL2mx my ln3left(1/εright)right) by Lin et al. Our bound achieves linear convergence rate and tighter dependency on condition numbers, especially when Lxyll L (i.e., when the interaction between x and y is weak). Via reduction, our new bound also implies improved bounds for strongly convex-concave and convex-concave minimax optimization problems. When f is quadratic, we can further improve the upper bound, which matches the lower bound up to a small sub-polynomial factor.