Research map / Optimization / Nonconvex and smooth optimization
Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that optimistic FTRL algorithms (including OMWU, Tsallis, log-barrier, squared Euclidean regularizers) lack forgetfulness and thus admit constant duality gap after 1/δ rounds on a 2x2 game, so no game-independent last-iterate rate exists for them, unlike OGDA.
Problem
Whether the slow, game-dependent last-iterate convergence of optimistic multiplicative weights update (OMWU) in zero-sum games is inherent or an artifact of loose analysis, compared with OGDA's O(1/sqrt(T)) last-iterate rate.
Approach
Identifies a broad class of optimistic FTRL algorithms that do not forget past losses quickly and constructs a 2x2 hard game A_delta whose Nash equilibrium lies O(delta) from the boundary; the dynamics cycle with constant duality gap for ~1/delta rounds, and the result extends to 2n x 2n games by duplication.
Key results
- For OFTRL with entropy, Tsallis, log-barrier, or squared Euclidean regularizers (constant step size eta <= 1/(4L)), for any small delta there is a 2x2 zero-sum game where the last-iterate duality gap is at least a constant c_2 at some iteration t >= c_1/(3 eta L delta), so no rate f(d1,d2,T) with f-
- The negative result extends to 2n x 2m games for entropy regularizer by duplicating actions, with duality gap at least c_2 n^{-alpha}.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use OFTRL with a negative entropy regularizer (OMWU) | OMWU self-play · A_δ (2×2 zero-sum game) | last-iterate duality gap: at least c_2 at an iteration t ≥ c_1/(3ηLδ) | Hurt |
| Use OFTRL with a squared Euclidean regularizer instead of OGDA | Optimistic game-learning dynamics · A_δ (2×2 zero-sum game) | last-iterate duality gap: at least c_2 | Hurt |
| Replace the negative entropy regularizer with a squared Euclidean regularizer (ablation) | OFTRL · A_δ (2×2 zero-sum game) | last-iterate duality gap: at least c_2 | No clear effect |
| Replace the negative entropy regularizer with a log regularizer (ablation) | OFTRL · A_δ (2×2 zero-sum game) | last-iterate duality gap: at least c_2 | No clear effect |
| Replace the negative entropy regularizer with Tsallis entropy (ablation) | OFTRL · A_δ (2×2 zero-sum game) | last-iterate duality gap: at least c_2 | No clear effect |
| Use optimistic OMD/OGDA rather than non-forgetful OFTRL | Two-player zero-sum game self-play · Two-player zero-sum games | last-iterate duality gap: O(1/√T) | Helped |
| Extend OFTRL dynamics to duplicated, rescaled 2n-action games | OFTRL with Euclidean, entropy, Tsallis, or log regularizer · Â_δ (2n×2n zero-sum game) | last-iterate duality gap: at least c_2 n^{-α} | Hurt |
Surprising findings
- OMWU, despite its superior regret properties over OGDA, provably cannot achieve a game-independent polynomial last-iterate rate, contrary to a common belief.
- Forgetfulness, not regret, governs last-iterate speed: OFTRL cycles with shrinking semi-ellipses while OGDA spirals quickly to equilibrium.
Limitations
- Results hold only for fixed (constant) step sizes; dynamic step sizes are conjectured but not proven.
- Lower bound concerns last iterate only; best-iterate rates for OMWU/OFTRL are left open.
- Analysis of the 2n x 2n extension does not cover Euclidean and log regularizers due to differing row/column rescaling.
Experimental setup
Metrics: duality gap
Baselines: OGDA
Builds on: OMWU OGDA optimistic FTRL optimistic mirror descent
Closest papers by meaning
- On Last-Iterate Convergence Beyond Zero-Sum Games (ICML 2022 · similarity 0.94)
- From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications (NeurIPS 2025 · similarity 0.93)
- When and Why is Optimistic Multiplicative Weights Slow? The Geometry of Energy Dissipation (NeurIPS 2026 · similarity 0.92)
- Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actions (NeurIPS 2026 · similarity 0.92)
- Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games (ICLR 2025 · similarity 0.91)
- The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback (ICML 2025 · similarity 0.91)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.