Solving Min-Max Optimization with Hidden Structure via Gradient Descent
Ascent
- URL: http://arxiv.org/abs/2101.05248v1
- Date: Wed, 13 Jan 2021 18:13:49 GMT
- Title: Solving Min-Max Optimization with Hidden Structure via Gradient Descent
Ascent
- Authors: Lampros Flokas, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Georgios
Piliouras
- Abstract summary: A class of non-concave zero-sum games functions hidden zero-sum games.
We prove convergence to the von-Neumann equilibrium of the "hidden" convex-concave game.
Our guarantees are non-local, which as far as we know is a first-of-its-kind type of result in non-concave games.
- Score: 40.99558326586079
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Many recent AI architectures are inspired by zero-sum games, however, the
behavior of their dynamics is still not well understood. Inspired by this, we
study standard gradient descent ascent (GDA) dynamics in a specific class of
non-convex non-concave zero-sum games, that we call hidden zero-sum games. In
this class, players control the inputs of smooth but possibly non-linear
functions whose outputs are being applied as inputs to a convex-concave game.
Unlike general zero-sum games, these games have a well-defined notion of
solution; outcomes that implement the von-Neumann equilibrium of the "hidden"
convex-concave game. We prove that if the hidden game is strictly
convex-concave then vanilla GDA converges not merely to local Nash, but
typically to the von-Neumann solution. If the game lacks strict convexity
properties, GDA may fail to converge to any equilibrium, however, by applying
standard regularization techniques we can prove convergence to a von-Neumann
solution of a slightly perturbed zero-sum game. Our convergence guarantees are
non-local, which as far as we know is a first-of-its-kind type of result in
non-convex non-concave games. Finally, we discuss connections of our framework
with generative adversarial networks.
Related papers
- Neural Population Learning beyond Symmetric Zero-sum Games [52.20454809055356]
We introduce NeuPL-JPSRO, a neural population learning algorithm that benefits from transfer learning of skills and converges to a Coarse Correlated (CCE) of the game.
Our work shows that equilibrium convergent population learning can be implemented at scale and in generality.
arXiv Detail & Related papers (2024-01-10T12:56:24Z) - Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games
with Bandit Feedback [49.1061436241109]
We focus on developing an algorithm that is uncoupled, convergent, and rational, with non-asymptotic convergence rates.
Our algorithm is related to [Chen et al., 2021, Cen et al., 2021] and also builds on the entropy regularization technique.
arXiv Detail & Related papers (2023-03-05T18:08:54Z) - Global Nash Equilibrium in Non-convex Multi-player Game: Theory and
Algorithms [66.8634598612777]
We show that Nash equilibrium (NE) is acceptable to all players in a multi-player game.
We also show that no one can benefit unilaterally from the general theory step by step.
arXiv Detail & Related papers (2023-01-19T11:36:50Z) - Last-iterate Convergence in Extensive-Form Games [49.31256241275577]
We study last-iterate convergence of optimistic algorithms in sequential games.
We show that all of these algorithms enjoy last-iterate convergence, with some of them even converging exponentially fast.
arXiv Detail & Related papers (2021-06-27T22:02:26Z) - Exponential Convergence of Gradient Methods in Concave Network Zero-sum
Games [6.129776019898013]
We study the computation of Nash equilibrium in concave network zero-sum games (NZSGs)
We show that various game theoretic properties of convex-concave two-player zero-sum games are preserved in this generalization.
arXiv Detail & Related papers (2020-07-10T16:56:56Z) - On the Impossibility of Global Convergence in Multi-Loss Optimization [10.081768261298098]
We prove that desirable convergence properties cannot simultaneously hold for any algorithm.
Our result has more to do with the existence of games with no satisfactory outcomes, than with algorithms per se.
It remains an open question whether such behavior can arise in high-dimensional games of interest to ML practitioners.
arXiv Detail & Related papers (2020-05-26T12:11:18Z) - Solving Non-Convex Non-Differentiable Min-Max Games using Proximal
Gradient Method [10.819408603463426]
Min-max saddle point descenders appear in a wide range of applications in machine leaning and signal processing.
We show that a simple multi-step LA-ascent algorithm is stronger than existing ones in the literature.
arXiv Detail & Related papers (2020-03-18T08:38:34Z) - Learning Zero-Sum Simultaneous-Move Markov Games Using Function
Approximation and Correlated Equilibrium [116.56359444619441]
We develop provably efficient reinforcement learning algorithms for two-player zero-sum finite-horizon Markov games.
In the offline setting, we control both players and aim to find the Nash Equilibrium by minimizing the duality gap.
In the online setting, we control a single player playing against an arbitrary opponent and aim to minimize the regret.
arXiv Detail & Related papers (2020-02-17T17:04:16Z) - A Limited-Capacity Minimax Theorem for Non-Convex Games or: How I
Learned to Stop Worrying about Mixed-Nash and Love Neural Nets [29.606063890097275]
Adrial training, a special case of multi-objective optimization, is an increasingly prevalent machine learning technique.
GAN-based generativeplay techniques have been applied to Poker games such as Go.
arXiv Detail & Related papers (2020-02-14T00:17:24Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.