Implicit Midpoint Gradient Descent: Fast and Learning rate free convergence for Zero-Sum Games
2026-07-10 • Computer Science and Game Theory
Computer Science and Game Theory
AI summaryⓘ
The authors study a basic type of game where two players compete in opposite ways without limits on their moves. They introduce a new method called implicit midpoint gradient descent, inspired by a continuous-time process, to find stable solutions faster and more reliably. Their method keeps the system stable regardless of how fast it learns and outperforms other popular methods in tests. This work is the first to combine these stability and speed benefits in such games using a standard online optimization approach.
bilinear zero-sum gamesonline learninggradient descentimplicit midpoint methodNash equilibriumsymplectic integrationergodic convergencelearning rateoptimization
Authors
Gaoqi Xue, James P. Bailey
Abstract
We study unconstrained bilinear zero-sum games, a fundamental model in online learning, adversarial optimization, and multi-agent decision-making. We introduce the implicit midpoint gradient descent rule, which we derive from continuous-time follow-the-regularized leader dynamics via symplectic integration methods. We prove that implicit midpoint gradient descent inherits several powerful properties from the continuous-time dynamics, including bounded orbits, fast ergodic convergence to Nash equilibria, and learning-rate-independent stability guarantees. This is the first traditional online optimization approach to simultaneously achieve these properties in unconstrained bilinear zero-sum games. Finally, computational experiments demonstrate that the proposed method significantly outperforms the standard methods, optimistic and alternating gradient descent.