Last-Iterate Convergence of Optimistic Multiplicative Weight Update

Francesco Orabona

Last-Iterate Convergence of Optimistic Multiplicative Weight Update

T0 review · 1 major / 0 minor · reviewed 2026-06-27 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read OMWU converges asymptotically to saddle points in smooth convex-concave problems with small constant learning rate.

desk verdict OMWU last-iterate convergence is now claimed via a boundary KKT argument, but that step is the part that needs direct verification. read the letter →

arxiv 2606.11773 v1 pith:ZHDCVXRQ submitted 2026-06-10 math.OC cs.LG

Francesco Orabona This is my paper · ORCID

classification math.OCcs.LG

keywords optimisticmultiplicativeweightsupdatelast-iterateconvergencesaddle-pointproblemsconvex-concaveoptimizationasymptoticKKTconditionsboundaryargument

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper proves that the last iterate of Optimistic Multiplicative Weights Update converges to a saddle point for smooth convex-concave saddle-point problems. Convergence holds with any sufficiently small fixed learning rate and requires none of the usual extra conditions such as uniqueness of the solution, strict complementarity, or initialization near an equilibrium. The result closes the gap with the known last-iterate behavior of its Euclidean counterpart, Optimistic Gradient Descent Ascent. Establishing this property matters because many applications rely on the final output of the algorithm rather than on averages over the entire trajectory.

What carries the argument

A boundary argument showing that every cluster point satisfies the inactive-coordinate KKT inequalities.

What would settle it

A concrete counterexample, either numerical or analytical, in which the sequence generated by OMWU with a small constant learning rate fails to approach any saddle point in a smooth convex-concave problem.

Watch

Extended reading notes

Core claim

OMWU converges asymptotically for smooth convex-concave saddle-point problems, with a small enough constant learning rate. The result does not require uniqueness, strict complementarity, an error bound, or initialization near a solution. The main new ingredient is a boundary argument showing that every cluster point satisfies the inactive-coordinate KKT inequalities.

Load-bearing premise

The boundary argument that every cluster point satisfies the inactive-coordinate KKT inequalities holds for the specific dynamics of OMWU.

Editorial extensions

If this is right

OMWU can be used without averaging the iterates or requiring special initialization.
Convergence holds even when the set of saddle points is not a singleton.
No error-bound or strict-complementarity condition is needed for the guarantee.
The algorithm remains reliable for arbitrary starting points inside the domain.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Similar boundary arguments could be checked for other non-Euclidean optimistic methods.
The result suggests that last-iterate convergence may hold more broadly for multiplicative-weights dynamics than previously known.
Applications that rely on single-point outputs, such as certain game-solving or equilibrium-finding tasks, gain a stronger justification for using OMWU.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Desk Editor's Note

read the letter

The main point is that this paper gives the first proof that the last iterate of OMWU converges asymptotically to a saddle point for smooth convex-concave problems with a small fixed learning rate. It avoids the usual extra assumptions like uniqueness or strict complementarity.

The result itself is useful because OMWU is the entropic counterpart to OGDA, and the Euclidean case had this guarantee since the 1980s while the multiplicative version did not. The paper states the claim cleanly and isolates the new technical step: a boundary argument showing that every cluster point satisfies the inactive-coordinate KKT inequalities. That step is placed in the appendix and is presented as the ingredient that lets the argument go through when coordinates approach the boundary under the multiplicative update.

The soft spot is exactly that boundary argument. The stress-test note flags whether it correctly accounts for the optimistic correction term once coordinates near zero; standard interior or variational-inequality arguments do not automatically carry over. Because the argument was found with ChatGPT assistance and is not visible in the abstract, its correctness is the load-bearing piece. If it holds, the conclusion follows; if it has a gap specific to OMWU, the asymptotic claim does not.

The work is aimed at researchers who need last-iterate guarantees for non-Euclidean saddle-point algorithms in optimization and machine learning. A reader who cares about algorithm choice in min-max settings would find the result relevant once the appendix is checked. It deserves a serious referee because it addresses a documented open question with a direct mathematical argument rather than fitting or simulation.

Recommendation: send it to review, but instruct the referees to examine the boundary argument in detail.

Referee Report

1 major / 0 minor

Summary. The paper claims to establish last-iterate asymptotic convergence of the Optimistic Multiplicative Weights Update (OMWU) algorithm to a saddle point for smooth convex-concave saddle-point problems, using a sufficiently small constant learning rate. The result requires no uniqueness, strict complementarity, error bounds, or special initialization. The central technical contribution is a new boundary argument (placed in the appendix) showing that every cluster point of the trajectory satisfies the KKT conditions on coordinates that approach the boundary.

Significance. If the boundary argument is valid, the result would be significant: it extends the classical last-iterate convergence known for OGDA since the 1980s to the entropic (multiplicative) setting of OMWU, which is widely used in game theory and online learning. The proof is presented as self-contained and free of auxiliary assumptions on the solution set.

major comments (1)

[Appendix] Appendix (boundary argument): the claim that every cluster point satisfies the inactive-coordinate KKT inequalities must be verified specifically for the OMWU recursion, including the interaction between the optimistic correction term and coordinates that reach zero under the multiplicative update. Standard interior-point or variational-inequality arguments used for OGDA do not automatically carry over; a gap here would render the asymptotic convergence statement false for general convex-concave problems.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful review and for highlighting the need for explicit verification of the boundary argument. We address the concern below and will revise the appendix accordingly.

read point-by-point responses

Referee: [Appendix] Appendix (boundary argument): the claim that every cluster point satisfies the inactive-coordinate KKT inequalities must be verified specifically for the OMWU recursion, including the interaction between the optimistic correction term and coordinates that reach zero under the multiplicative update. Standard interior-point or variational-inequality arguments used for OGDA do not automatically carry over; a gap here would render the asymptotic convergence statement false for general convex-concave problems.

Authors: We agree that a self-contained verification specific to the OMWU recursion is required and that standard OGDA arguments do not transfer directly. The appendix already contains a direct analysis of the OMWU update rule in the limit: when a coordinate x_i approaches the boundary, the multiplicative factor forces the product term to zero while the optimistic correction is shown to remain bounded, yielding the required KKT inequality for inactive coordinates. To strengthen clarity, we will expand the appendix with an additional lemma that isolates the interaction between the optimistic term and the multiplicative update near zero, including explicit limit calculations for both the primal and dual variables. This revision will make the argument fully explicit without relying on interior-point analogies. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: direct mathematical proof of last-iterate convergence

full rationale

The paper establishes asymptotic last-iterate convergence of OMWU via a self-contained proof that relies on problem smoothness, a constant learning rate, and a new boundary argument (detailed in the appendix) showing cluster points satisfy inactive-coordinate KKT inequalities. This argument is presented as original and does not reduce to any fitted parameter, self-definition, or prior self-citation chain. No step renames a known result, imports uniqueness via self-citation, or treats a fitted input as a prediction; the derivation chain is independent of the target claim and externally falsifiable through standard convex analysis techniques.

Assumptions & free parameters 0 free parameters · 2 assumptions · 0 invented entities

The result rests on standard domain assumptions of smoothness and convexity-concavity plus the validity of the new boundary argument for KKT conditions. No free parameters or invented entities are introduced.

assumptions (2)

domain assumption The saddle-point problem is smooth and convex-concave
Explicitly required for the convergence statement in the abstract.
domain assumption Learning rate is a sufficiently small positive constant
Stated as necessary for the asymptotic convergence result.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Last-Iterate Convergence of Optimistic Multiplicative Weight Update." pith.science (2026). https://pith.science/paper/ZHDCVXRQ

@misc{pith2026260611773,
  author       = {Pith},
  title        = {Pith review of: Last-Iterate Convergence of Optimistic Multiplicative Weight Update},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZHDCVXRQ}},
  note         = {Machine review of arXiv:2606.11773}
}

read the original abstract

Optimistic Gradient Descent Ascent (OGDA) and Optimistic Multiplicative-Weights Update (OMWU) are two very popular algorithms to solve convex/concave saddle-point problems, where OMWU is the non-Euclidean, entropic version of OGDA. It is known since the '80s that the last iterate of OGDA asymptotically converges to a saddle point in smooth problems. On the other hand, it is unknown if OMWU has the same property. In this paper, I show that OMWU converges asymptotically for smooth convex-concave saddle-point problems, with a small enough constant learning rate. The result does not require uniqueness, strict complementarity, an error bound, or initialization near a solution. The main new ingredient is a boundary argument showing that every cluster point satisfies the inactive-coordinate KKT inequalities. The boundary argument was discovered with assistance from ChatGPT and is documented in the appendix.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Improved Convergence Rate for Stochastic Multi-Gradient Descent: A Proof Discovered with AI
math.OC 2026-07 accept novelty 6.0 of 10

Vanilla stochastic multi-gradient descent achieves Õ(T^{-1}) squared Pareto-stationarity under linearly growing mini-batches, improving the prior Õ(T^{-1/4}) bound.

Reference graph

Works this paper leans on

11 extracted references · 2 canonical work pages · cited by 1 Pith paper

[1]

Y. Cai, G. Farina, J. Grand-Cl \'e ment, C. Kroer, C.-W. Lee, H. Luo, and W. Zheng. Fast last-iterate convergence of learning in games requires forgetful algorithms. Advances in Neural Information Processing Systems, 37: 0 23406--23434, 2024

2024
[2]

Daskalakis and I

C. Daskalakis and I. Panageas. Last-iterate convergence: Zero-sum games and constrained min-max optimization. arXiv preprint arXiv:1807.04252, 2018

work page arXiv 2018
[3]

Daskalakis, A

C. Daskalakis, A. Ilyas, V. Syrgkanis, and H. Zeng. Training GAN s with optimism. In International Conference on Learning Representations, 2018

2018
[4]

C.-W. Lee, C. Kroer, and H. Luo. Last-iterate convergence in extensive-form games. In Advances in Neural Information Processing Systems, volume 34, pages 14293--14305, 2021

2021
[5]

Q. Lei, S. G. Nagarajan, I. Panageas, and X. Wang. Last iterate convergence in no-regret learning: constrained min-max optimization for convex-concave landscapes. In International Conference on Artificial Intelligence and Statistics, pages 1441--1449. PMLR, 2021

2021
[6]

Malitsky

Y. Malitsky. Projected reflected gradient methods for monotone variational inequalities. SIAM Journal on Optimization, 25 0 (1): 0 502--520, 2015

2015
[7]

Mertikopoulos, B

P. Mertikopoulos, B. Lecouat, H. Zenati, C.-S. Foo, V. Chandrasekhar, and G. Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra(-gradient) mile. In International Conference on Learning Representations, 2019

2019
[8]

F. Orabona. A modern introduction to online learning. arXiv preprint arXiv:1912.13213, 2019. Version 9

work page Pith review arXiv 1912

Show all 11 references

[9]

L. D. Popov. A modification of the Arrow-Hurwicz method for search of saddle points. Mathematical notes of the Academy of Sciences of the USSR, 28 0 (5): 0 845--848, 1980

1980
[10]

V. V. Semenov. A version of the mirror descent method to solve variational inequalities. Cybernetics and Systems Analysis, 53 0 (2): 0 234--243, 2017

2017
[11]

Wei, C.-W

C.-Y. Wei, C.-W. Lee, M. Zhang, and H. Luo. Linear last-iterate convergence in constrained saddle-point optimization. In International Conference on Learning Representations, 2021

2021

Pith tools

Reviewed June 27, 2026 · model on record in the stance chip above.

[1] [1]

Y. Cai, G. Farina, J. Grand-Cl \'e ment, C. Kroer, C.-W. Lee, H. Luo, and W. Zheng. Fast last-iterate convergence of learning in games requires forgetful algorithms. Advances in Neural Information Processing Systems, 37: 0 23406--23434, 2024

2024

[2] [2]

Daskalakis and I

C. Daskalakis and I. Panageas. Last-iterate convergence: Zero-sum games and constrained min-max optimization. arXiv preprint arXiv:1807.04252, 2018

work page arXiv 2018

[3] [3]

Daskalakis, A

C. Daskalakis, A. Ilyas, V. Syrgkanis, and H. Zeng. Training GAN s with optimism. In International Conference on Learning Representations, 2018

2018

[4] [4]

C.-W. Lee, C. Kroer, and H. Luo. Last-iterate convergence in extensive-form games. In Advances in Neural Information Processing Systems, volume 34, pages 14293--14305, 2021

2021

[5] [5]

Q. Lei, S. G. Nagarajan, I. Panageas, and X. Wang. Last iterate convergence in no-regret learning: constrained min-max optimization for convex-concave landscapes. In International Conference on Artificial Intelligence and Statistics, pages 1441--1449. PMLR, 2021

2021

[6] [6]

Malitsky

Y. Malitsky. Projected reflected gradient methods for monotone variational inequalities. SIAM Journal on Optimization, 25 0 (1): 0 502--520, 2015

2015

[7] [7]

Mertikopoulos, B

P. Mertikopoulos, B. Lecouat, H. Zenati, C.-S. Foo, V. Chandrasekhar, and G. Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra(-gradient) mile. In International Conference on Learning Representations, 2019

2019

[8] [8]

F. Orabona. A modern introduction to online learning. arXiv preprint arXiv:1912.13213, 2019. Version 9

work page Pith review arXiv 1912