AltGDA Achieves Global O(1/T) Ergodic Convergence in Matrix Games
Abstract
Alternating gradient descent-ascent (AltGDA) is a simple and practically effective method for solving finite two-player zero-sum matrix games. However, the theory of AltGDA remains limited: existing results either apply only to unconstrained settings or require restrictive assumptions on the equilibrium in constrained settings. We show that AltGDA converges globally at an O(1/T) ergodic rate in every finite two-player zero-sum matrix game. Unlike prior results, our guarantee holds for every initialization and every horizon T: the uniform averages of the AltGDA iterates satisfy an O(1/T) duality-gap bound. Our proof is inspired by numerical results obtained using a novel performance estimation programming (PEP) framework for Lyapunov function search over compact convex sets. Additionally, we provide simple counterexamples showing that the last-iterate duality gap of AltGDA does not converge to zero. This justifies why averaging of iterates is indeed necessary to achieve an O(1/T) rate. We have formalized and machine-checked our global ergodic convergence result in Lean 4.
Related
- Analysis of a zeroth-order multiscale sampler: strong convergence, convergence of ergodic averages and weak convergence
- Pointwise convergence of bilinear ergodic averages for commuting transformations
- Pointwise Convergence of Random Ergodic Averages at the L1 Endpoint
- Halpern-Accelerated Majorized ADMM with Optimal Non-Ergodic Convergence under Degenerate Preconditioning
- Pointwise convergence of noncommutative ergodic averages along the primes
BibTeX
@misc{nan2026altgda,
title = {{AltGDA Achieves Global $O(1/T)$ Ergodic Convergence in Matrix Games}},
author = {Tianlong Nan and Garud Iyengar and Christian Kroer and Shuvomoy Das Gupta},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.32995},
eprint = {2609.32995},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.32995},
}
RIS
TY - UNPB
TI - AltGDA Achieves Global O(1/T) Ergodic Convergence in Matrix Games
AU - Tianlong Nan
AU - Garud Iyengar
AU - Christian Kroer
AU - Shuvomoy Das Gupta
PY - 2026
DA - 2026/09/26
PB - arXiv
DO - 10.48550/arxiv.2609.32995
UR - https://arxiv.org/abs/2609.32995
AB - Alternating gradient descent-ascent (AltGDA) is a simple and practically effective method for solving finite two-player zero-sum matrix games. However, the theory of AltGDA remains limited: existing results either apply only to unconstrained settings or require restrictive assumptions on the equilibrium in constrained settings. We show that AltGDA converges globally at an O(1/T) ergodic rate in every finite two-player zero-sum matrix game. Unlike prior results, our guarantee holds for every initialization and every horizon T: the uniform averages of the AltGDA iterates satisfy an O(1/T) duality-gap bound. Our proof is inspired by numerical results obtained using a novel performance estimation programming (PEP) framework for Lyapunov function search over compact convex sets. Additionally, we provide simple counterexamples showing that the last-iterate duality gap of AltGDA does not converge to zero. This justifies why averaging of iterates is indeed necessary to achieve an O(1/T) rate. We have formalized and machine-checked our global ergodic convergence result in Lean 4.
ER -