# Linear Convergence in Games with Delayed Feedback via Extra Prediction

arXiv: https://arxiv.org/abs/2602.17486 · HTML: https://mlsanity.com/paper/2602.17486/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 33 references that are in the map.
- First posted on arXiv 19 Feb 2026.

## Builds on (most cited first, 21 of 21)

- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [Optimization, Learning, and Games with Predictable Sequences](https://mlsanity.com/paper/1311.1869/) (2013)
- [Fast Convergence of Regularized Learning in Games](https://mlsanity.com/paper/1507.00407/) (2015)
- [A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach](https://mlsanity.com/paper/1901.08511/) (2019)
- [Online Learning under Delayed Feedback](https://mlsanity.com/paper/1306.0686/) (2013)
- [Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile](https://mlsanity.com/paper/1807.02629/) (2018)
- [Asynchronous Stochastic Gradient Descent with Delay Compensation](https://mlsanity.com/paper/1609.08326/) (2016)
- [Delay and Cooperation in Nonstochastic Bandits](https://mlsanity.com/paper/1602.04741/) (2016)
- [Stochastic Bandit Models for Delayed Conversions](https://mlsanity.com/paper/1706.09186/) (2017)
- [Multi-Agent Online Optimization with Delays: Asynchronicity, Adaptivity, and Optimism](https://mlsanity.com/paper/2012.11579/) (2020)
- [Beyond Time-Average Convergence: Near-Optimal Uncoupled Online Learning via Clairvoyant Multiplicative Weights Update](https://mlsanity.com/paper/2111.14737/) (2021)
- [A Nonparametric Delayed Feedback Model for Conversion Rate Prediction](https://mlsanity.com/paper/1802.00255/) (2018)
- [Bandit Online Learning with Unknown Delays](https://mlsanity.com/paper/1807.03205/) (2018)
- [A Feedback Shift Correction in Predicting Conversion Rates under Delayed Feedback](https://mlsanity.com/paper/2002.02068/) (2020)
- [Nonstochastic Bandits with Composite Anonymous Feedback](https://mlsanity.com/paper/2112.02866/) (2021)
- [Online Learning with Local Permutations and Delayed Feedback](https://mlsanity.com/paper/1703.04274/) (2017)
- [On the Last-iterate Convergence in Time-varying Zero-sum Games: Extra Gradient Succeeds where Optimism Fails](https://mlsanity.com/paper/2310.02604/) (2023)
- [Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Maps](https://mlsanity.com/paper/2301.03931/) (2023)
- [Last-iterate Convergence Separation between Extra-gradient and Optimism in Constrained Periodic Games](https://mlsanity.com/paper/2406.10605/) (2024)
- [Synchronization in Learning in Periodic Zero-Sum Games Triggers Divergence from Nash Equilibrium](https://mlsanity.com/paper/2408.10595/) (2024)
- [Learning from Delayed Feedback in Games via Extra Prediction](https://mlsanity.com/paper/2509.22426/) (2025)

## Abstract (arXiv)

Feedback delays are inevitable in real-world multi-agent learning. They are known to severely degrade performance, and the convergence rate under delayed feedback is still unclear, even for bilinear games. This paper derives the rate of linear convergence of Weighted Optimistic Gradient Descent-Ascent (WOGDA), which predicts future rewards with extra optimism, in unconstrained bilinear games. To analyze the algorithm, we interpret it as an approximation of the Extra Proximal Point (EPP), which is updated based on farther future rewards than the classical Proximal Point (PP). Our theorems show that standard optimism (predicting the next-step reward) achieves linear convergence to the equilibrium at a rate exp(-Theta(t/m5)) after t iterations for delay m. Moreover, employing extra optimism (predicting farther future reward) tolerates a larger step size and significantly accelerates the rate to exp(-Theta(t/(m2log m))). Our experiments also show accelerated convergence driven by the extra optimism and are qualitatively consistent with our theorems. In summary, this paper validates that extra optimism is a promising countermeasure against performance degradation caused by feedback delays.