On Solving Minimax Optimization Locally: A Follow-the-Ridge Approach

Abstract

Many tasks in modern machine learning can be formulated as finding equilibria in \emph{sequential} games. In particular, two-player zero-sum sequential games, also known as minimax optimization, have received growing interest. It is tempting to apply gradient descent to solve minimax optimization given its popularity and success in supervised learning. However, it has been noted that naive application of gradient descent fails to find some local minimax and can converge to non-local-minimax points. In this paper, we propose \emph{Follow-the-Ridge} (FR), a novel algorithm that provably converges to and only converges to local minimax. We show theoretically that the algorithm addresses the notorious rotational behaviour of gradient dynamics, and is compatible with preconditioning and \emph{positive} momentum. Empirically, FR solves toy minimax problems and improves the convergence of GAN training compared to the recent minimax optimization algorithms.

arXiv comment21 pages

References in corpus (14)

• Unsupervised Representation Learning with Deep Convolutional Generative Adversarial Networks
• GANs Trained by a Two Time-Scale Update Rule Converge to a Local Nash Equilibrium
• Large Scale GAN Training for High Fidelity Natural Image Synthesis
• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems
• The Numerics of GANs
• Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods
• SBEED: Convergent Reinforcement Learning with Nonlinear Function Approximation
• Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications
• Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile
• On Finding Local Nash Equilibria (and Only Local Nash Equilibria) in Zero-Sum Games
• What is Local Optimality in Nonconvex-Nonconcave Minimax Optimization?
• Stochastic Variance Reduction Methods for Policy Evaluation
• Convergence of Learning Dynamics in Stackelberg Games
• Global Convergence to the Equilibrium of GANs using Variational Inequalities

Cited by in corpus (8)

• A Systematic Survey of Regularization and Normalization in GANs
• A Game Theoretic Framework for Model Based Reinforcement Learning
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization
• Local Stochastic Gradient Descent Ascent: Convergence Analysis and Communication Efficiency
• Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimization
• Delta-STN: Efficient Bilevel Optimization for Neural Networks using Structured Response Jacobians
• Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domain
• Exploiting the Hidden Tasks of GANs: Making Implicit Subproblems Explicit