Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile

Abstract

Owing to their connection with generative adversarial networks (GANs), saddle-point problems have recently attracted considerable interest in machine learning and beyond. By necessity, most theoretical guarantees revolve around convex-concave (or even linear) problems; however, making theoretical inroads towards efficient GAN training depends crucially on moving beyond this classic framework. To make piecemeal progress along these lines, we analyze the behavior of mirror descent (MD) in a class of non-monotone problems whose solutions coincide with those of a naturally associated variational inequality - a property which we call coherence. We first show that ordinary, "vanilla" MD converges under a strict version of this condition, but not otherwise; in particular, it may fail to converge even in bilinear models with a unique solution. We then show that this deficiency is mitigated by optimism: by taking an "extra-gradient" step, optimistic mirror descent (OMD) converges in all coherent problems. Our analysis generalizes and extends the results of Daskalakis et al. (2018) for optimistic gradient descent (OGD) in bilinear problems, and makes concrete headway for establishing convergence beyond convex-concave games. We also provide stochastic analogues of these results, and we validate our analysis by numerical experiments in a wide array of GAN models (including Gaussian mixture models, as well as the CelebA and CIFAR-10 datasets).

26 pages, 14 figures

References in corpus (2)

• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method

Cited by in corpus (65)

• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems
• Game-Theoretic Multiagent Reinforcement Learning
• Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications
• The Unusual Effectiveness of Averaging in GAN Training
• Competitive Gradient Descent
• Near-Optimal Algorithms for Minimax Optimization
• Convergence of Learning Dynamics in Stackelberg Games
• A Decentralized Parallel Algorithm for Training Generative Adversarial Nets
• Last-iterate convergence rates for min-max optimization
• Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scaling
• On the convergence of single-call stochastic extra-gradient methods
• First-order Convergence Theory for Weakly-Convex-Weakly-Concave Min-max Problems
• A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problems
• On Solving Minimax Optimization Locally: A Follow-the-Ridge Approach
• Stochastic Variance Reduction for Variational Inequality Methods
• Finding Mixed Nash Equilibria of Generative Adversarial Networks
• Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization
• The limits of min-max optimization algorithms: convergence to spurious non-critical sets
• A Forward-Backward Splitting Method for Monotone Inclusions Without Cocoercivity
• A Unified Analysis of First-Order Methods for Smooth Games via Integral Quadratic Constraints
• Newton-type Methods for Minimax Optimization
• Chaos, Extremism and Optimism: Volume Analysis of Learning in Games
• Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization
• The Complexity of Nonconvex-Strongly-Concave Minimax Optimization
• A mean-field analysis of two-player zero-sum games
• Adaptive extra-gradient methods for min-max optimization and games
• Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibrium
• Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with $\mathcal{O}(1/k^2)$ Rate on Squared Gradient Norm
• Linear Last-iterate Convergence in Constrained Saddle-point Optimization
• A Decentralized Adaptive Momentum Method for Solving a Class of Min-Max Optimization Problems
• Finite Regret and Cycles with Fixed Step-Size via Alternating Gradient Descent-Ascent
• Gradient Descent-Ascent Provably Converges to Strict Local Minmax Equilibria with a Finite Timescale Separation
• Near-optimal Local Convergence of Alternating Gradient Descent-Ascent for Minimax Optimization
• Optimality and Stability in Non-Convex Smooth Games
• DIPPA: An improved Method for Bilinear Saddle Point Problems
• Poincaré Recurrence, Cycles and Spurious Equilibria in Gradient-Descent-Ascent for Non-Convex Non-Concave Zero-Sum Games
• Convergence Analysis of No-Regret Bidding Algorithms in Repeated Auctions
• A Tight and Unified Analysis of Gradient-Based Methods for a Whole Spectrum of Games
• Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domain
• Last-iterate Convergence in Extensive-Form Games
• A Game-Theoretic Approach to Multi-Agent Trust Region Optimization
• A Hölderian backtracking method for min-max and min-min problems
• Extragradient with player sampling for faster Nash equilibrium finding
• No-regret distributed learning in subnetwork zero-sum games
• On the One-sided Convergence of Adam-type Algorithms in Non-convex Non-concave Min-max Optimization
• Learning in Matrix Games can be Arbitrarily Complex
• An Optimistic Acceleration of AMSGrad for Nonconvex Optimization
• Consensus Multiplicative Weights Update: Learning to Learn using Projector-based Game Signatures
• Distributed stochastic optimization with large delays
• Online Markov Decision Processes with Non-oblivious Strategic Adversary
• Semi-Anchored Multi-Step Gradient Descent Ascent Method for Structured Nonconvex-Nonconcave Composite Minimax Problems
• On the modes of convergence of Stochastic Optimistic Mirror Descent (OMD) for saddle point problems
• Exponential Convergence of Gradient Methods in Concave Network Zero-sum Games
• Efficient Competitive Self-Play Policy Optimization
• Uncoupled Bandit Learning towards Rationalizability: Benchmarks, Barriers, and Algorithms
• Stochastic Projective Splitting: Solving Saddle-Point Problems with Multiple Regularizers
• Forward Looking Best-Response Multiplicative Weights Update Methods for Bilinear Zero-sum Games
• Optimal Analysis of Method with Batching for Monotone Stochastic Finite-Sum Variational Inequalities
• On the Impossibility of Convergence of Mixed Strategies with No Regret Learning
• An Exponentially Converging Particle Method for the Mixed Nash Equilibrium of Continuous Games
• Local AdaGrad-Type Algorithm for Stochastic Convex-Concave Optimization
• Parameter-free Gradient Temporal Difference Learning
• Solving Min-Max Optimization with Hidden Structure via Gradient Descent Ascent
• Constants of Motion: The Antidote to Chaos in Optimization and Game Dynamics