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

Zhang et al. (2021) and Ibrahim et al. (2020) established the lower bound \Omega\left(\sqrt{\kappa_x\kappa_y} \log \frac{1}{\epsilon}\right) on the number of gradient evaluations required to find an ϵ-accurate solution, where κx and κ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 \mathcal{O}\left(\sqrt{\kappa_x\kappa_y} \log 3 \frac{1}{\epsilon}\right) and \mathcal{O}\left( \sqrt{\kappa_x\kappa_y}\log 3 (\kappa_x\kappa_y)\log\frac{1}{\epsilon}\right), respectively. 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.