The First Optimal Algorithm for Smooth and Strongly-Convex-Strongly-Concave Minimax Optimization

Authors

Dmitry Kovalev, Alexander Gasnikov

Year

2022

Preprint

Source

arXiv

Identifiers

arXiv 2205.05653

Abstract¶

In this paper, we revisit the smooth and strongly-convex-strongly-concave minimax optimization problem. Zhang et al. (2021) and Ibrahim et al. (2020) established the lower bound Omega(sqrt(kappa_xkappa_y) log frac1epsilon) on the number of gradient evaluations required to find an epsilon-accurate solution, where kappa_x and kappa_y are condition numbers for the strong convexity and strong concavity assumptions. However, the existing state-of-the-art methods do not match this lower bound: algorithms of Lin et al. (2020) and Wang and Li (2020) have gradient evaluation complexity O( sqrt(kappa_xkappa_y)log^(3)frac1epsilon) and O( sqrt(kappa_xkappa_y)log^(3) (kappa_xkappa_y)logfrac1epsilon), respectively. We fix this fundamental issue by providing the first algorithm with O(sqrt(kappa_xkappa_y)logfrac1epsilon) gradient evaluation complexity. We design our algorithm in three steps: (i) we reformulate the original problem as a minimization problem via the pointwise conjugate function; (ii) we apply a specific variant of the proximal point algorithm to the reformulated problem; (iii) we compute the proximal operator inexactly using the optimal algorithm for operator norm reduction in monotone inclusions.