Nesterov Meets Optimism: Rate-Optimal Separable Minimax Optimization
This work addresses optimization problems in machine learning and game theory, offering a novel algorithm with optimal rates, but it is incremental as it builds on existing gradient-based methods.
The authors tackled separable convex-concave minimax optimization by proposing the AG-OG algorithm, which combines Nesterov acceleration and optimistic gradient methods, achieving optimal convergence rates in deterministic and stochastic settings for various problem types, including bilinearly coupled strongly convex-strongly concave and convex-strongly concave cases.
We propose a new first-order optimization algorithm -- AcceleratedGradient-OptimisticGradient (AG-OG) Descent Ascent -- for separable convex-concave minimax optimization. The main idea of our algorithm is to carefully leverage the structure of the minimax problem, performing Nesterov acceleration on the individual component and optimistic gradient on the coupling component. Equipped with proper restarting, we show that AG-OG achieves the optimal convergence rate (up to a constant) for a variety of settings, including bilinearly coupled strongly convex-strongly concave minimax optimization (bi-SC-SC), bilinearly coupled convex-strongly concave minimax optimization (bi-C-SC), and bilinear games. We also extend our algorithm to the stochastic setting and achieve the optimal convergence rate in both bi-SC-SC and bi-C-SC settings. AG-OG is the first single-call algorithm with optimal convergence rates in both deterministic and stochastic settings for bilinearly coupled minimax optimization problems.