Last-iterate convergence rates for min-max optimization

Abstract

While classic work in convex-concave min-max optimization relies on average-iterate convergence results, the emergence of nonconvex applications such as training Generative Adversarial Networks has led to renewed interest in last-iterate convergence guarantees. Proving last-iterate convergence is challenging because many natural algorithms, such as Simultaneous Gradient Descent/Ascent, provably diverge or cycle even in simple convex-concave min-max settings, and previous work on global last-iterate convergence rates has been limited to the bilinear and convex-strongly concave settings. In this work, we show that the Hamiltonian Gradient Descent (HGD) algorithm achieves linear convergence in a variety of more general settings, including convex-concave problems that satisfy a "sufficiently bilinear" condition. We also prove similar convergence rates for the Consensus Optimization (CO) algorithm of [MNG17] for some parameter settings of CO.

References in corpus (11)

• Which Training Methods for GANs do actually Converge?
• The Numerics of GANs
• A Variational Inequality Perspective on Generative Adversarial Networks
• A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach
• The Mechanics of n-Player Differentiable Games
• Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile
• The Unusual Effectiveness of Averaging in GAN Training
• On Finding Local Nash Equilibria (and Only Local Nash Equilibria) in Zero-Sum Games
• "Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions
• Faster Rates for Convex-Concave Games
• Increasing Iterate Averaging for Solving Saddle-Point Problems

Cited by in corpus (26)

• Near-Optimal Algorithms for Minimax Optimization
• Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems
• Improved Algorithms for Convex-Concave Minimax Optimization
• Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems
• Last iterate convergence in no-regret learning: constrained min-max optimization for convex-concave landscapes
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization
• The limits of min-max optimization algorithms: convergence to spurious non-critical sets
• A Unified Analysis of First-Order Methods for Smooth Games via Integral Quadratic Constraints
• Robust Reinforcement Learning via Adversarial training with Langevin Dynamics
• Chaos, Extremism and Optimism: Volume Analysis of Learning in Games
• On the Impossibility of Global Convergence in Multi-Loss Optimization
• Tight last-iterate convergence rates for no-regret learning in multi-player games
• Generative Minimization Networks: Training GANs Without Competition
• Smooth markets: A basic mechanism for organizing gradient-based learners
• Finite Regret and Cycles with Fixed Step-Size via Alternating Gradient Descent-Ascent
• Extragradient Method: $O(1/K)$ Last-Iterate Convergence for Monotone Variational Inequalities and Connections With Cocoercivity
• Local and Global Uniform Convexity Conditions
• Poincaré Recurrence, Cycles and Spurious Equilibria in Gradient-Descent-Ascent for Non-Convex Non-Concave Zero-Sum Games
• Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domain
• A Tight and Unified Analysis of Gradient-Based Methods for a Whole Spectrum of Games
• Minimax Problems with Coupled Linear Constraints: Computational Complexity, Duality and Solution Methods
• Constants of Motion: The Antidote to Chaos in Optimization and Game Dynamics
• Primal-Dual First-Order Methods for Affinely Constrained Multi-Block Saddle Point Problems
• Quasi-Newton Methods for Saddle Point Problems and Beyond
• On the Impossibility of Convergence of Mixed Strategies with No Regret Learning
• Solving Min-Max Optimization with Hidden Structure via Gradient Descent Ascent