Near-Optimal Algorithms for Minimax Optimization

Current stateof-the-art first-order algorithms find an approximate Nash equilibrium using Õ(κ x κ y) [Tseng, 1995] or Õ(min{κ x κy, κ x κ y }) [Alkousa et al., 2019] gradient evaluations, where κ x and κ y are the condition numbers for the strong-convexity and strong-concavity assumptions. A gap remains between these results and the best existing lower bound Ω( κ x κ y) due to Zhang et al. [2019]. This paper presents the first algorithm with Õ( κ x κ y) gradient complexity, matching the lower bound up to logarithmic factors. Our new algorithm is designed based on an accelerated proximal point method and an accelerated solver for minimax proximal steps. It can be easily extended to the settings of strongly-convex-concave, convex-concave, nonconvex-strongly-concave, and nonconvexconcave functions. This paper also presents algorithms that match or outperform all existing methods in these settings in terms of gradient complexity, up to logarithmic factors.