Convergence of Gradient Methods on Bilinear Zero-Sum Games

Abstract

Min-max formulations have attracted great attention in the ML community due to the rise of deep generative models and adversarial methods, while understanding the dynamics of gradient algorithms for solving such formulations has remained a grand challenge. As a first step, we restrict to bilinear zero-sum games and give a systematic analysis of popular gradient updates, for both simultaneous and alternating versions. We provide exact conditions for their convergence and find the optimal parameter setup and convergence rates. In particular, our results offer formal evidence that alternating updates converge "better" than simultaneous ones.

Cited by in corpus (11)

• Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems
• Newton-type Methods for Minimax Optimization
• Near-optimal Local Convergence of Alternating Gradient Descent-Ascent for Minimax Optimization
• Optimality and Stability in Non-Convex Smooth Games
• Training Generative Adversarial Networks with Adaptive Composite Gradient
• Bridging Explicit and Implicit Deep Generative Models via Neural Stein Estimators
• Semi-Anchored Multi-Step Gradient Descent Ascent Method for Structured Nonconvex-Nonconcave Composite Minimax Problems
• A generic adaptive restart scheme with applications to saddle point algorithms
• Solving Min-Max Optimization with Hidden Structure via Gradient Descent Ascent
• Direct-Search for a Class of Stochastic Min-Max Problems
• Complex Momentum for Optimization in Games