A Catalyst Framework for Minimax Optimization

We introduce a generic two-loop scheme for smooth minimax optimization with strongly-convex-concave objectives. Our approach applies the accelerated proximal point framework (or Catalyst) to the associated dual problem and takes full advantage of existing gradient-based algorithms to solve a sequence of well-balanced strongly-convex-strongly-concave minimax problems. Despite its simplicity, this leads to a family of near-optimal algorithms with improved complexity over all existing methods designed for strongly-convex-concave minimax problems. Additionally, we obtain the first variance-reduced algorithms for this class of minimax problems with finite-sum structure and establish faster convergence rate than batch algorithms. Furthermore, when extended to the nonconvex-concave minimax optimization, our algorithm again achieves the state-of-the-art complexity for finding a stationary point. We carry out several numerical experiments showcasing the superiority of the Catalyst framework in practice. Algorithms Oracle Complexity number of loops prefix MINIMAX-APPA [24] O / √ µ log 3 (1/ ) 3 Yes can be attained by some existing algorithms. For example, extragradient method (EG) achieves the optimal O(1/ ) complexity for smooth convex-concave minimax problems, and the optimal O(κ log(1/ )) complexity for well-balanced strongly-convex-strongly-concave minimax problems, where the x-component and y-component of the objective share the same condition number κ [50].