REVIEW 1 major objections 5 minor 13 references
On the modes of convergence of Stochastic Optimistic Mirror Descent (OMD) for saddle point problems
T0 review · 1 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read Optimistic mirror descent converges to saddle points, but its monotone decrease begins only after a burn-in phase.
desk verdict A credible, honest correction of two over-claimed convergence results in a widely cited ICLR paper; the missing proof of the stochastic MD theorem keeps it from being complete. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The argument is carried by Bregman divergence $D(x,y)=h(y)-h(x)-\langle\nabla h(x), y-x\rangle$ for a $K$-strongly convex, $\nabla h$-Lipschitz distance-generating function $h$, together with the optimistic mirror descent recursion $Y_n = P_{X_n}(-\gamma_n \hat{g}_n)$, $X_{n+1} = P_{X_n}(-\gamma_n \hat{r}_n)$, and the coherence conditions (local and global Minty variational inequalities). A central tool is a one-step descent inequality (Lemma 1, restated from [1]) showing $D(p, X_{n+1}) \le D(p, X_n) - \tfrac{K}{2}(1-\alpha^2)\lVert Y_n - X_n\rVert^2$ for the special saddle point $p$ satisfying global MVI. The proof of eventual monotonicity combines this inequality with the Bregman projection's Lipschitz property, a subsequence argument, and a 'Bregman reciprocity condition' that converts convergence of $D(x^\ast, X_n)$ into norm convergence; the stochastic proofs add martingale convergence arguments.
What would settle it
Find a $K$-strongly convex, $\nabla h$-Lipschitz $h$ and a coherent saddle-point problem for which $D(x^\ast, X_n)\to 0$ yet $\lVert X_n - x^\ast\rVert$ does not converge to $0$; alternatively, run OMD with exact gradients on a coherent problem and observe whether the Bregman distance $D(x^\ast, X_n)$ decreases from the first iterate, which would contradict Theorem 1's $n_0$ correction. A cleaner test is to exhibit an $h$ on a compact polytope where the Bregman reciprocity condition fails while all other assumptions hold.
Extended reading notes
Core claim
The central claim is Theorem 1: for coherent saddle point problems with an $L_g$-Lipschitz gradient and step sizes satisfying $0 < \lim \gamma_n \le \sup_n \gamma_n < K/L_g$, the OMD iterates $X_n$ satisfy $\lim_{n\to\infty} X_n = x^\ast \in \mathcal{X}^\ast$, and there exists an $n_0$ such that the Bregman distance $D(x^\ast, X_n)$ decreases monotonically for all $n \ge n_0$. Theorems 2(a) and 3 assert that for strictly coherent problems with stochastic gradients satisfying the stated variance bounds, both MD and OMD converge with probability at least $1-\delta$ to within any tolerance $\epsilon$ after some finite time, meaning convergence with high probability rather than almost surely. The paper also records that for null-coherent problems the expected Bregman distance is non-decreasing only for the special saddle points satisfying the global Minty variational inequality, correcting a prior statement that applied to all saddle points.
Load-bearing premise
The proofs assume a 'Bregman reciprocity condition' that lets Bregman-distance convergence imply norm convergence, but this condition is never stated among the assumptions, proved, or referenced, and without it the convergence conclusions do not follow.
Editorial extensions
If this is right
- OMD with exact gradients on coherent problems is guaranteed to converge to some saddle point, but users should expect a burn-in phase before monotone improvement begins.
- For stochastic gradients, the correct guarantee is an event of probability at least $1-\delta$: the iterates eventually stay within an $\epsilon$-ball of the saddle set, and almost-sure convergence is not established.
- Step-size choices exhibit a trade-off between evolution speed (larger $\gamma_n$), accuracy (smaller $\epsilon$), and confidence (smaller $\delta$), as encoded in conditions (11) and (12).
- For null-coherent problems, the expected Bregman distance to a saddle point can increase or stay flat rather than decrease, and the non-decrease statement holds only for saddle points that satisfy global MVI.
Reading between the lines
- A testable extension is to construct explicit coherent problems where the burn-in phase $n_0$ is exponentially large; Theorem 1 as stated gives no bound on $n_0$, so practical convergence could be arbitrarily slow.
- The correction suggests that empirical successes of OMD in adversarial training should not be read as evidence of monotone convergence; the eventual-convergence guarantee is compatible with long periods of non-monotone behavior.
- If the Bregman reciprocity condition fails for a natural choice of $h$ (for instance, entropic regularization on a simplex), the norm-convergence conclusion in Theorem 1 may require an alternative proof strategy or an additional assumption.
- The high-probability bounds in Theorems 2 and 3 are qualitative; deriving explicit rates would require filling in the martingale concentration details that the paper leaves at the level of existence of finite limits.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies Mirror Descent (MD) and Optimistic Mirror Descent (OMD) for saddle point problems satisfying the coherence notion of Mertikopoulos et al. It states three corrected theorems: (Theorem 1) for coherent problems, exact-gradient OMD converges to a saddle point and the Bregman distance to the limit becomes monotone only after a sufficiently large number of iterations, not from the first iterate as claimed in [1]; (Theorem 2) for strictly coherent problems, stochastic MD converges with high probability (Theorem 2(a)), and for null-coherent problems the expected Bregman distance is non-decreasing only for saddle points satisfying global MVI (Theorem 2(b)); (Theorem 3) for strictly coherent problems, stochastic OMD converges with high probability. The OMD proofs are given in detail in the appendix; the MD proof is omitted, and the Bregman reciprocity used in the OMD proof is not stated as an assumption.
Significance. If the corrected statements are accepted, the paper makes a useful contribution by clarifying the actual mode of convergence for stochastic MD/OMD under coherence: high-probability eventual convergence rather than almost sure convergence, and by identifying the finite-time correction to monotonicity for exact OMD. The paper also corrects a sign in [1, (C.14)] and provides detailed derivations for the OMD case. The main weakness is that one of the central stochastic claims (Theorem 2(a) for MD) is asserted without proof, leaving the advertised correction incomplete.
major comments (1)
- [Section 4.2, Theorem 2(a)] The proof of Theorem 2(a) is a single sentence stating that the same technique as Theorem 3 can be used and omitting the details. This is load-bearing because Theorem 2(a) is one of the two stochastic convergence claims advertised in the abstract. The OMD proof in Theorem 3 relies on the extrapolated point Y_n for the drift inequality (24)-(26), the local MVI argument in (28), and the step-size condition (12); MD has no Y_n, so the recursion must be re-derived with X_{n+1} in place of Y_n, leading to different noise terms and requiring a separate verification that condition (11) suffices and that strict coherence yields a uniform positive drift. Please provide a full proof or a precise reduction to the OMD argument.
minor comments (5)
- [Section 4.1, proof of Theorem 1; Section 4.3 (iii)] The proof invokes a 'Bregman reciprocity condition' without stating it. Under the assumptions in (2) and the Lh-Lipschitzness of ∇h, one has D(x,y) ≥ (K/2)||x-y||^2 and, on the compact set X, D(x,y) ≤ (Lh/2)||x-y||^2, so both uses (D(x*,Xn)→0 implies ||Xn-x*||→0, and ||Xn-Yn||→0 implies D(Xn,Yn)→0) are justified. Please state this bound explicitly as a lemma.
- [Section 4.3 (iii), induction after (28)] The statement that D(x*,Xn) ≤ 4ǫ 'by (16)' implies D(x*,Yn) ≤ 4¯ǫ is not immediate, since (16) is proved for the level ǫ. Recomputing with D(x*,Xn) ≤ 4ǫ gives D(x*,Yn) ≤ (5+Lh diam(X))ǫ; with the scaling ǫ = ¯ǫ/(2+Lh diam(X)) this is still < ǫ0 for ¯ǫ sufficiently small, so the induction can be repaired.
- [Lemma 2] The statement 'for any y ∈ Y' is undefined; Y is not introduced. It should read 'for any y ∈ V*', and the domain 'dom ∂h' should be defined.
- [Section 4.2, proof of Theorem 2(b)] The proof uses ∇h^{-1}=∇h^*, which requires h to be essentially smooth/Legendre; this condition is not stated. Please add a remark or cite the relevant lemma from [1].
- [Proof of (20)] There is a sign typo: '||Xnk(ω)Ynk(ω)+Ynk(ω)-x*||' should be '||Xnk(ω)-Ynk(ω)+Ynk(ω)-x*||'.
Circularity Check
No circularity: the paper corrects external prior work using its own proofs and attributed lemmas.
full rationale
This paper does not fit parameters to data, does not rename a known result, and contains no self-citations: references [1] and [2] are by Mertikopoulos et al. and Zhou et al., not by the present authors. The central theorems are proved from the stated coherence, strong-convexity, Lipschitz, step-size, and stochastic-oracle assumptions. The one-step descent Lemma 1 is quoted from [1, Lemma D.1] as an external lemma, and Lemma 2 is proved in the text; reliance on prior lemmas is normal attribution, not circularity. The two invocations of a 'Bregman reciprocity condition' (Theorem 1 proof and Theorem 3 step (iii)) are not stated as assumptions, but they follow from the already assumed K-strong convexity (2) and Lh-Lipschitz continuity of ∇h, so they do not smuggle the conclusion in. Section 4.2 omits the proof of Theorem 2(a) ('we omit the details here'), but an omitted proof is a completeness or correctness risk, not a circular derivation. The paper's advertised corrections are new theorem statements that go beyond what [1] proved, so the derivation is self-contained rather than circular.
Assumptions & free parameters
assumptions (6)
- domain assumption The saddle point problem satisfies the coherence definition, including global SVI solutions being SP solutions, existence of a global MVI point p, and local MVI for all SP solutions within D(x*, x) at most epsilon0.
- domain assumption The distance-generating function h is K-strongly convex and its gradient is Lh-Lipschitz.
- domain assumption The gradient map g is Lg-Lipschitz on the compact domain X.
- domain assumption The stochastic gradient oracles are unbiased and have bounded second moments, yielding constants G, tau, and sigma in equations (6), (7), (9), and (10).
- ad hoc to paper A Bregman reciprocity condition holds, so that D(z_n, z) tending to 0 implies norm convergence z_n to z, and ||u_n - v_n|| tending to 0 implies D(u_n, v_n) tending to 0.
- standard math Martingale and super-martingale convergence theorems apply to the stochastic processes constructed in the proofs.
Cite this review
Pith. "Pith review of On the modes of convergence of Stochastic Optimistic Mirror Descent (OMD) for saddle point problems." pith.science (2026). https://pith.science/paper/GCJVC4JB
@misc{pith2026190801071,
author = {Pith},
title = {Pith review of: On the modes of convergence of Stochastic Optimistic Mirror Descent (OMD) for saddle point problems},
year = {2026},
howpublished = {\url{https://pith.science/paper/GCJVC4JB}},
note = {Machine review of arXiv:1908.01071}
}
read the original abstract
In this article, we study the convergence of Mirror Descent (MD) and Optimistic Mirror Descent (OMD) for saddle point problems satisfying the notion of coherence as proposed in Mertikopoulos et al. We prove convergence of OMD with exact gradients for coherent saddle point problems, and show that monotone convergence only occurs after some sufficiently large number of iterations. This is in contrast to the claim in Mertikopoulos et al. of monotone convergence of OMD with exact gradients for coherent saddle point problems. Besides highlighting this important subtlety, we note that the almost sure convergence guarantees of MD and OMD with stochastic gradients for strictly coherent saddle point problems that are claimed in Mertikopoulos et al. are not fully justified by their proof. As such, we fill out the missing details in the proof and as a result have only been able to prove convergence with high probability. We would like to note that our analysis relies heavily on the core ideas and proof techniques introduced in Zhou et al. and Mertikopoulos et al., and we only aim to re-state and correct the results in light of what we were able to prove rigorously while filling in the much needed missing details in their proofs.
Reference graph
Works this paper leans on
-
[1]
Optimistic mirror descent in saddle-point problems: Goin g the extra(-gradient) mile,
P. Mertikopoulos, B. Lecouat, H. Zenati, C.-S. Foo, V. Ch andrasekhar, and G. Piliouras, “Optimistic mirror descent in saddle-point problems: Goin g the extra(-gradient) mile,” in International Conference on Learning Representations (ICLR 201 9), 2019. 4
work page 2019
-
[2]
On the convergence of mirror descent beyond stochastic convex programming,
Z. Zhou, P. Mertikopoulos, N. Bambos, S. Boyd, and P. Glyn n, “On the convergence of mirror descent beyond stochastic convex programming,” arXiv preprint arXiv:1706.05681 , 2017
arXiv 2017
-
[3]
Trai ning gans with optimism.,
C. Daskalakis, A. Ilyas, V. Syrgkanis, and H. Zeng, “Trai ning gans with optimism.,” in International Conference on Learning Representations (ICLR 201 8), 2018
work page 2018
-
[4]
Variational inequalities and optimiza tion problems,
R. Ferrentino, “Variational inequalities and optimiza tion problems,” Applied Mathematical Sciences, vol. 1, pp. 2327–2343, 01 2007
work page 2007
-
[5]
Stochastic mirror de scent dynamics and their conver- gence in monotone variational inequalities,
P. Mertikopoulos and M. Staudigl, “Stochastic mirror de scent dynamics and their conver- gence in monotone variational inequalities,” Journal of optimization theory and applications , vol. 179, no. 3, pp. 838–867, 2018. 5 4 Appendix 4.1 Proof of Theorem 1 First, we restate [ 1, Lemma D.1]. Lemma 1. Suppose that (SP) is coherent and g is L-Lipschitz. For a...
work page 2018
-
[6]
Choose N1 sufficiently large such that ‖Xn − Yn‖ ≤ ǫ for all n ≥ N1, such choice is possible since we have proved that ‖Xn − Yn‖ → 0 as n → ∞
-
[7]
Choose N2 sufficiently large such that D(Xn, Yn) ≤ ǫ for all n ≥ N2, such choice is possible since by ‖Xn − Yn‖ → 0 and the Bregman reciprocity condition, we have D(Xn, Yn) → 0 as n → ∞
-
[8]
With such choice of n0, we will prove that D(x∗, Xn+1) ≤ ǫ for all n ≥ n0
Choose n0 ≥ max{N1, N2} such that D(x∗, Xn0 ) ≤ ǫ, such choice is possible since we have proved that lim k→∞ D(x∗, Xnk ) = 0. With such choice of n0, we will prove that D(x∗, Xn+1) ≤ ǫ for all n ≥ n0. First we show that for all n ≥ n0, D(x∗, Xn) ≤ ǫ =⇒ D(x∗, Yn) ≤ (2 + Lhdiam(X ))ǫ = ¯ǫ. (16) To see this, in [ 1, Lemma B.2], letting p = x∗, x′ = Yn, x = X...
Show all 13 references
-
[11]
Next we show (ii)
It follows that the RHS of ( 21) is finite almost surely when n → ∞ , which confirms our assertion stated in ( 22). Next we show (ii). Note that by definition of limit, the event being measured in (19) is equivalent to { ∃{Ynk }k, s.t. ∀ǫ > 0, ∃k0, s.t. inf x∗∈X ∗ ‖Ynk − x∗‖ ≤ ǫ,...
-
[13]
Let {Xnk }k denote a subsequence of {Xn}n and we notice that (i) and (ii) imply that P ( ∃{Xnk }k, s.t
holds. Let {Xnk }k denote a subsequence of {Xn}n and we notice that (i) and (ii) imply that P ( ∃{Xnk }k, s.t. lim k→∞ inf x∗∈X ∗ ‖Xnk − x∗‖ = 0 ) = 1. (20) To see this, denote the events considered in ( 18), (19), and ( 20) by E, EY , and EX , respectively. For any ω ∈ EY ∩ E...
-
[21]
also converges to a random variable almost surely and that random variable is finite with probability
-
[25]
(26) Note that the last three terms in (
and using ( 24), we have D(p, Xn+1) ≤ D(p, Xn0) − a n∑ k=n0 γk + n∑ k=n0 γkξ+ k+1 + n∑ k=n0 γ2 k 2K ‖ˆrk − ˆgk‖2 ∗ ≤ D(p, Xn0) − a n∑ k=n0 γk + n∑ k=n0 γkξ+ k+1 + 1 K n∑ k=n0 γ2 k‖ˆrk‖2 ∗ + 1 K n∑ k=n0 γ2 k‖ˆgk‖2 ∗. (26) Note that the last three terms in (
-
[26]
Note also that the first term in ( 26) is finite and does not change with n, moreover, the second term in ( 26) goes to −∞ as n → ∞
are similar to the last three term in ( 21) (only the lower limit of the summations is different), and so we can use the same method to show that they stay finite with probability 1 as n → ∞ . Note also that the first term in ( 26) is finite and does not change with n, moreover, t...
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.