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

By Yuanhao Wang, Guodong Zhang, Jimmy Ba. 2019

107 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Management Science and Operations Research, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

In Optimization & Training

Citations in the corpus

Stochastic Hamiltonian Gradient Methods for Smooth Games (2020, background): “Some of them require the computation or inversion of a Jacobian which is a highly inefficient operation (Wang et al., 2019; Mazumdar et al., 2019).”
Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization (2020, background): “…on attaining improved rates [3, 4,19,21,26,29–31, In the nonconvex-nonconcave setting, research has focused on identifying different notions of local min-max solutions [14, 24, 34, 35] and studying the existence and (local) convergence properties of learning methods to these points [33, 34, 46].”
A Game Theoretic Framework for Model Based Reinforcement Learning (2020, methodology): “Such an approximation has proven effective in applications like meta-learning (Nichol et al., 2018), GANs (Heusel et al., 2017; Metz et al., 2017), and multiple timescale actor-critic methods (Konda & Borkar, 1999).”
Learning to Give Checkable Answers with Prover-Verifier Games (2021, unknown): “A Stackelberg equilibrium differs from the Nash equilibrium in that one of the players is deemed the “leader" and the other the “follower" [34].”