The limits of min-max optimization algorithms: convergence to spurious non-critical sets

Abstract

Compared to ordinary function minimization problems, min-max optimization algorithms encounter far greater challenges because of the existence of periodic cycles and similar phenomena. Even though some of these behaviors can be overcome in the convex-concave regime, the general case is considerably more difficult. On that account, we take an in-depth look at a comprehensive class of state-of-the art algorithms and prevalent heuristics in non-convex / non-concave problems, and we establish the following general results: a) generically, the algorithms' limit points are contained in the ICT sets of a common, mean-field system; b) the attractors of this system also attract the algorithms in question with arbitrarily high probability; and c) all algorithms avoid the system's unstable sets with probability 1. On the surface, this provides a highly optimistic outlook for min-max algorithms; however, we show that there exist spurious attractors that do not contain any stationary points of the problem under study. In this regard, our work suggests that existing min-max algorithms may be subject to inescapable convergence failures. We complement our theoretical analysis by illustrating such attractors in simple, two-dimensional, almost bilinear problems.

References in corpus (17)

• Adam: A Method for Stochastic Optimization
• Robust Adversarial Reinforcement Learning
• A Variational Inequality Perspective on Generative Adversarial Networks
• The Mechanics of n-Player Differentiable Games
• Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile
• Gradient descent GAN optimization is locally stable
• What is Local Optimality in Nonconvex-Nonconcave Minimax Optimization?
• Reducing Noise in GAN Training with Variance Reduced Extragradient
• Competitive Gradient Descent
• Convergence of Learning Dynamics in Stackelberg Games
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems
• Last-iterate convergence rates for min-max optimization
• Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scaling
• Robust Reinforcement Learning via Adversarial training with Langevin Dynamics
• Stabilizing Adversarial Nets With Prediction Methods
• Gradient Descent-Ascent Provably Converges to Strict Local Minmax Equilibria with a Finite Timescale Separation
• Limiting Behaviors of Nonconvex-Nonconcave Minimax Optimization via Continuous-Time Systems

Cited by in corpus (7)

• No-regret learning and mixed Nash equilibria: They do not mix
• On the Impossibility of Global Convergence in Multi-Loss Optimization
• Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domain
• Limiting Behaviors of Nonconvex-Nonconcave Minimax Optimization via Continuous-Time Systems
• Learning in Matrix Games can be Arbitrarily Complex
• On the One-sided Convergence of Adam-type Algorithms in Non-convex Non-concave Min-max Optimization
• Minimax Optimization with Smooth Algorithmic Adversaries