Solving Zero-Sum Games through Alternating Projections

In this work, we establish near-linear and strong convergence for a natural first-order iterative algorithm that simulates Von Neumann's Alternating Projections method in zero-sum games. First, we provide a precise analysis of Optimistic Gradient Descent/Ascent (OGDA) -- an optimistic variant of Gradient Descent/Ascent -- for unconstrained bilinear games, extending and strengthening prior results along several directions. Our characterization is based on a closed-form solution we derive for the dynamics, while our results also reveal several surprising properties. Indeed, our main algorithmic contribution is founded on a geometric feature of OGDA we discovered; namely, the limit points of the dynamics are the orthogonal projection of the initial state to the space of attractors. Motivated by this property, we show that the equilibria for a natural class of constrained bilinear games are the intersection of the unconstrained stationary points with the corresponding probability simplexes. Thus, we employ OGDA to implement an Alternating Projections procedure, converging to an ε-approximate Nash equilibrium in widetildeO(log2(1/ε)) iterations. Our techniques supplement the recent work in pursuing last-iterate guarantees in min-max optimization. Finally, we illustrate an -- in principle -- trivial reduction from any game to the assumed class of instances, without altering the space of equilibria.