Research map / Optimization / Nonconvex and smooth optimization

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

NeurIPS 2026 · Optimization › Nonconvex and smooth optimization · approach: Equilibrium learning in zero-sum games · 0 citations (OpenAlex)

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.

Analyzes last-iterate convergence of optimistic multiplicative weights (OMWU) in zero-sum games via dual energy dissipation, giving tight universal KL rates, uniform lower bounds, and an O~(T^{-1/2}) best-iterate duality gap rate for 2x2 games.

Problem

Understanding when and why the last-iterate convergence of OMWU in two-player zero-sum games can be arbitrarily slow, with sharp quantitative dependence on game-specific constants and uniform rates across distance measures.

Approach

Views OMWU's dual iterates as optimistic skew-gradient descent on the log-sum-exp energy (conjugate of negative entropy); shows energy is dissipative with tight one-step bounds, and that energy change equals KL change in primal space, yielding sharp geometric explanations of slowdown near the simplex boundary.</ask>

Key results

• Proves a universal linear last-iterate KL rate for OMWU improving the prior bound by a factor exp(1/delta), with a matching lower bound in delta.
• Proves constant uniform best-iterate lower bounds for OMWU: min TV >= 1/3 and min KL >= 1/9 over T for some 2x2 games.
• Proves a new O~(T^{-1/2}) best-iterate rate in duality gap for 2x2 zero-sum games, improving the prior O(T^{-1/6}).

Surprising findings

• OMWU has no uniform best-iterate convergence rate in KL or TV, although a uniform best-iterate rate exists in duality gap for 2x2 games.

Limitations

• Uniform duality-gap rate O~(T^{-1/2}) proven only for 2x2 games; conjectured for higher dimensions.
• Universal KL rate still decays slowly as the minimum equilibrium coordinate delta shrinks.
• Analysis restricted to bilinear zero-sum games with unique interior Nash equilibrium.

Experimental setup

Metrics: KL divergence total variation distance duality gap convergence rate

Baselines: Wei et al. 2021 OMWU linear rate Lee et al. O(T^{-1/6}) best-iterate rate in duality gap Daskalakis-Panageas OMWU last-iterate

Builds on: OMWU optimistic FTRL Wei et al. 2021 universal last-iterate rate skew-gradient flow

Closest papers by meaning

• Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms (NeurIPS 2024 · similarity 0.92)
• Classic but Everlasting: Traditional Gradient-Based Algorithms Converge Fast Even in Time-Varying Multi-Player Games (ICLR 2025 · similarity 0.91)
• On Last-Iterate Convergence Beyond Zero-Sum Games (ICML 2022 · similarity 0.89)
• Asynchronous Gradient Play in Zero-Sum Multi-agent Games (ICLR 2023 · similarity 0.89)
• Convergence of $\text{log}(1/\epsilon)$ for Gradient-Based Algorithms in Zero-Sum Games without the Condition Number: A Smoothed Analysis (NeurIPS 2024 · similarity 0.89)
• Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence beyond the Minty Property (AAAI 2024 · similarity 0.87)