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.