Smooth markets: A basic mechanism for organizing gradient-based learners

Abstract

With the success of modern machine learning, it is becoming increasingly important to understand and control how learning algorithms interact. Unfortunately, negative results from game theory show there is little hope of understanding or controlling general n-player games. We therefore introduce smooth markets (SM-games), a class of n-player games with pairwise zero sum interactions. SM-games codify a common design pattern in machine learning that includes (some) GANs, adversarial training, and other recent algorithms. We show that SM-games are amenable to analysis and optimization using first-order methods.

18 pages, 3 figures

References in corpus (10)

• Graphical Models for Game Theory
• The Numerics of GANs
• Multiplicative Weights Update with Constant Step-Size in Congestion Games: Convergence, Limit Cycles and Chaos
• A Collaborative Mechanism for Crowdsourcing Prediction Problems
• Last-iterate convergence rates for min-max optimization
• Differentiable Game Mechanics
• A Closer Look at the Optimization Landscapes of Generative Adversarial Networks
• Global Convergence to the Equilibrium of GANs using Variational Inequalities
• Isoelastic Agents and Wealth Updates in Machine Learning Markets
• Online Monotone Games

Cited by in corpus (3)

• On the Impossibility of Global Convergence in Multi-Loss Optimization
• Learning in Matrix Games can be Arbitrarily Complex
• Exponential Convergence of Gradient Methods in Concave Network Zero-sum Games