Linear Last-Iterate Convergence Rates for Optimistic Learning in Harmonic Games

John Lazarsfeld; Anas Barakat; Jacob Abernethy; Vidya Muthukumar; Georgios Piliouras; Andre Wibisono; Juba Ziani

cs.GTOct 13, 2026

Linear Last-Iterate Convergence Rates for Optimistic Learning in Harmonic Games

Authors: John Lazarsfeld, Anas Barakat, Jacob Abernethy, Vidya Muthukumar, Georgios Piliouras, Andre Wibisono, Juba Ziani

Organizations: Georgia Tech · SUTD · Google Research · Google DeepMind ·

Abstract

We prove that the last iterate of Optimistic Follow-The-Regularized-Leader (OFTRL) converges at a linear rate to a Nash equilibrium in multiplayer harmonic games. Our result holds under a mild game-regularity condition and for a large family of regularizers, including entropy, Tsallis, and log-barrier. Our analysis is based on a dual perspective of OFTRL: we prove that the interaction between optimism and the global structure of harmonic games leads to the dissipation of an energy function along the dual iterates, for which we establish tight quantitative bounds. Our result also holds for the Extragradient FTRL variant.

Figures & tables

Figure 1: Variants of FTRL (with entropy regularizer) on the 3-player harmonic game in A.4.1 . Left: two trajectories of OFTRL converging to their distinct analytic limits (in green) from Theorem 4.1 (i). Right: Bregman divergence from NE for the $t$ -th iterate of OFTRL, EGFTRL, and FTRL from a fixed initialization. OFTRL and EGFTRL converge linearly (Theorem 4.1 (ii)), while FTRL diverges at a geometric rate (Theorem 4.5 ).

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Figure 2: The sets $\textnormal{WMEQ}_{M}(G)$ and $\textnormal{NE}(G)\setminus\textnormal{WMEQ}_{M}(G)$ for the instantiation of Example 1 from Section A.4.1 with $m_{1}=3$ , $m_{2}=6$ , $m_{3}=4$ (left), and Example 2 from Section A.4.2 .

Last-Iterate Convergence

Last-iterate convergence studies whether an algorithm’s final update approaches an optimizer or equilibrium, rather than only its average.

See all 42 papers

When and Why is Optimistic Multiplicative Weights Slow? The Geometry of Energy Dissipation
May 13, 2026John Lazarsfeld, Anas Barakat, Georgios Piliouras +2Nash Equilibrium Last-Iterate Convergence
SUTD · Google DeepMind · NUS CQT +2
Constant regret in general games via higher-order optimism
Sep 3, 2026Omar Abbadi, Rida Laraki, Panayotis MertikopoulosFollow-the-Regularized-Leader Regret Minimization
Univ. Mohammed VI Polytechnic, CMSIS, MCGT, 11103 Rabat, Morocco · Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG, 38000 Grenoble, France
Constant Individual Regret in General Games
Aug 31, 2026Mingyang Liu, Gabriele Farina, Asuman OzdaglarGame Theory Follow-the-Regularized-Leader
LIDS, EECS, Massachusetts Institute of Technology

May 13, 2026J/K move · Enter open · S save

When and Why is Optimistic Multiplicative Weights Slow? The Geometry of Energy Dissipation

John Lazarsfeld, Anas Barakat, Georgios Piliouras, Antonios Varvitsiotis+1

SUTD · Google DeepMind · NUS CQT+2

Nash Equilibrium Last-Iterate Convergence Optimization Convergence Analysis Game Theory Zero-Sum Games Convergence Analysis+1

Open paper AskPDF arXiv

This paper studies the convergence of the Optimistic Multiplicative Weights Update algorithm (OMWU) in two player zero-sum games. Recent works have identified instances on which the last-iterate of OMWU can converge arbitrarily slowly, but understanding when and why this slow convergence occurs has remained open. In this work, we develop a new analysis framework that gives sharp, quantitative explanations for this behavior. Our analysis is based on viewing the algorithm's dual iterates as an optimistic skew-gradient descent with respect to an energy function. We prove over the dual iterates that energy is dissipative, and by establishing tight bounds on the magnitude of dissipation, our analysis quantifies the geometric bottlenecks that arise when the corresponding primal iterates are close to the simplex boundary. This further translates into a new linear last-iterate convergence rate in KL divergence on games with a unique and interior Nash equilibrium. Compared to prior work, this new rate contains a much sharper dependence on game-specific constants, and we prove this dependence is optimal. Moreover, these geometric insights further translate into new separations on uniform convergence rates for OMWU. On the one hand, we prove constant lower bounds on the uniform best-iterate convergence rate in KL divergence and total variation distance from Nash. On the other hand, we establish for the

2\times 2

setting a new

{\widetilde O}(T^{-1/2})

best-iterate rate in duality gap, improving substantially over prior work. Together, this shows in general that uniform convergence rate guarantees do not transfer across different measures of distance to Nash.

Abstract

Last-Iterate Convergence

Explore similar work

When and Why is Optimistic Multiplicative Weights Slow? The Geometry of Energy Dissipation

Constant regret in general games via higher-order optimism

Constant Individual Regret in General Games