mlsanityData to 7 Oct 2026

Characterizing Nash Equilibria in Zero-Sum Games: A Physics-Inspired, Parallelizable Approach with a Linear Number of Gradient Queries

arXiv 2507.11366 ↗First posted 15 Jul 2025cs.GT cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

We study online optimization methods for zero-sum games, a fundamental problem in adversarial learning in machine learning, economics, and many other domains. Traditional methods approximate Nash equilibria (NE) using either regret-based methods (time-average convergence) or contraction-map-based methods (last-iterate convergence). We propose a new method based on Hamiltonian dynamics in physics and prove that it can characterize the set of NE in a finite (linear) number of iterations of alternating gradient descent in the unbounded setting, modulo degeneracy, a first in online optimization. Unlike standard methods for computing NE, our proposed approach can be parallelized and works with arbitrary learning rates, both firsts in algorithmic game theory. Experimentally, we support our results by showing our approach drastically outperforms standard methods.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 17 of its 31 references that are in the map. First posted on arXiv 15 Jul 2025.

Builds on

17 of 31 references.

References · 17

  1. 2018Large Scale GAN Training for High Fidelity Natural Image Synthesiscited by 2,609
  2. 2017Training GANs with Optimismcited by 217
  3. 2016Precomputed Real-Time Texture Synthesis with Markovian Generative Adversarial Networkscited by 192
  4. 2017Cycles in adversarial regularized learningcited by 122
  5. 2018The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimizationcited by 98
  6. 2018Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimizationcited by 97
  7. 2021Near-Optimal No-Regret Learning in General Gamescited by 85
  8. 2021Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Normcited by 71
  9. 2020Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problemscited by 59
  10. 2020Vox2Vox: 3D-GAN for Brain Tumour Segmentationcited by 30
  11. 2019Finite Regret and Cycles with Fixed Step-Size via Alternating Gradient Descent-Ascentcited by 28
  12. 2022Accelerated Algorithms for Constrained Nonconvex-Nonconcave Min-Max Optimization and Comonotone Inclusioncited by 19
5 more
  1. 2018Multi-agent online learning in time-varying gamescited by 17
  2. 2019Multi-Agent Learning in Network Zero-Sum Games is a Hamiltonian Systemcited by 13
  3. 2020Bayesian Conditional GAN for MRI Brain Image Synthesiscited by 4
  4. 2020Deform-GAN:An Unsupervised Learning Model for Deformable Registrationcited by 3
  5. 2021Oleft(1/Tright) Time-Average Convergence in a Generalization of Multiagent Zero-Sum Gamescited by 3

Built on by

Not cited yet.