{"id":"aabfedc8-f2d2-4e18-98d2-d0df44fd7fde","arxiv_id":"1908.01071","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper revises Mertikopoulos et al.'s MD/OMD convergence theorems: for coherent problems monotone decrease is only eventual, and stochastic guarantees are high-probability rather than almost sure.","lead":"This paper corrects earlier convergence claims for optimistic mirror descent and mirror descent in saddle-point problems, showing that monotone convergence only begins after enough iterations and that stochastic-gradient convergence is guaranteed with high probability, not almost surely. The corrected guarantees matter because these algorithms are widely cited for training GANs and other adversarial optimization.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2(a), a central correction for stochastic MD, is stated without proof; the Bregman-reciprocity worry raised by the reader is resolvable from the paper's own strong-convexity and Lipschitz assumptions.","rationale":"The reader's verdict is CONDITIONAL, and I agree that a conditional verdict is appropriate, but for a different primary reason. The reader's weakest_assumption is the unstated Bregman reciprocity condition; that concern does not land because the needed implications follow from the paper's stated assumptions (K-strong convexity in (2) and Lh-Lipschitz continuity of ∇h). The actual load-bearing gap is Theorem 2(a): the proof is explicitly omitted, and the claimed high-probability convergence of stochastic MD is a central part of the paper's correction. Since the same technique as Theorem 3 is asserted rather than demonstrated, the result is not established as written. This does not require REJECT: Theorem 1 and Theorem 3 are proved in detail, and the MD proof is plausibly a routine adaptation. It does require CONDITIONAL acceptance, conditioning on a complete proof of Theorem 2(a) (or an explicit downgrade of that claim). The reader's rationale did note the omitted proof, but selected Bregman reciprocity as the weakest assumption; my read shifts the emphasis to the omitted MD proof. Therefore the verdict stays CONDITIONAL/UNCHANGED, with the concrete condition being the completion of the MD proof along the lines described.","tokens_in":12129,"tokens_out":13595,"duration_ms":139639,"concrete_test":"Complete the proof of Theorem 2(a) by specializing Lemma 3 ([1, Prop. B.4(b)]) to MD with y1 = y2 = -γ_n ĝ_n and x1+ = x2+ = X_{n+1}. Derive the resulting inequality D(p,X_{n+1}) ≤ D(p,X_n) - γ_n⟨g(X_n), X_n-p⟩ + γ_n ζ_{n+1} + O(γ_n^2), identify the martingale difference ζ_{n+1}, and verify its conditional-zero-mean and variance bounds. Then check whether the drift lower bound (24) holds with X_n in place of Y_n and whether the high-probability maximal inequalities used for OMD go through unchanged to produce (13) with constants matching (11). If the derivation produces the same summability and probability bounds, Theorem 2(a) is established; if an extra O(γ_n^2) term or the lack of an extrapolated point changes the constants or requires a different step-size condition, Theorem 2(a) as stated is not supported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's advertised correction to [1] covers both MD and OMD, but Theorem 2(a) for stochastic MD is asserted with a one-sentence proof: 'The same technique used for proving (ii) and (iii) in Theorem 3 can also be used to prove the convergence of mirror descent (MD) algorithm; we omit the details here' (Section 4.2). This is load-bearing because Theorem 2(a) is one of the two stochastic convergence claims that motivate the paper, and the OMD proof does not transfer verbatim: the OMD argument in Theorem 3 repeatedly uses the extrapolated point Y_n, both for the almost-sure subsequence step via the drift inequality (24)-(26) and for the eventual local-MVI argument in (28). For MD there is no Y_n, so the analogue must be re-derived with X_{n+1} in place of Y_n, leading to different noise terms and additional O(γ_n^2) cross terms. As written, the reader cannot verify that the step-size condition (11) is sufficient or that strict coherence supplies a uniform positive drift in the MD case. This is an explicit missing proof, not a cosmetic omission. By contrast, the Bregman-reciprocity condition flagged by the reader is not a genuine gap: under the stated K-strong convexity (2) and Lh-Lipschitzness, D(x,y) ≥ (K/2)||x-y||^2 and, on compact X, D(x,y) ≤ (Lh/2)||x-y||^2, so D(x*,X_n)->0 implies ||X_n-x*||->0 and ||X_n-Y_n||->0 implies D(X_n,Y_n)->0. Those two uses can be justified from the stated assumptions without adding a new condition.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":12540,"tokens_out":10558,"duration_ms":94677,"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":[{"comment":"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.","section":"Section 4.2, Theorem 2(a)"}],"minor_comments":[{"comment":"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":"Section 4.1, proof of Theorem 1; Section 4.3 (iii)"},{"comment":"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.","section":"Section 4.3 (iii), induction after (28)"},{"comment":"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":"Lemma 2"},{"comment":"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].","section":"Section 4.2, proof of Theorem 2(b)"},{"comment":"There is a sign typo: '||Xnk(ω)Ynk(ω)+Ynk(ω)-x*||' should be '||Xnk(ω)-Ynk(ω)+Ynk(ω)-x*||'.","section":"Proof of (20)"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read this if you cite Mertikopoulos et al. (ICLR 2019) for OMD/MD convergence. The paper does what its title says: it re-derives the proofs and corrects the claims. The main new content is (1) a proof that OMD with exact gradients converges to a saddle point and that the Bregman distance to the limit is eventually, not immediately, monotone, and (2) a demonstration that the almost-sure guarantees in the original paper are not supported, and what one can actually prove is a high-probability bound. Along the way they catch a sign typo in the original proof of the null-coherence monotonicity claim, which is a real catch.\n\nThe proofs of Theorem 1 and Theorem 3 are detailed and, as far as I can tell, correct. The martingale/supermartingale argument for the high-probability bound is sound. The authors are transparent about leaning on [1,2].\n\nThe soft spots are real but two are fixable. Theorem 2(a) — the stochastic MD high-probability claim — is stated without a proof. The sentence saying 'same technique as Theorem 3' does not transfer verbatim, because the OMD proof uses the extrapolated point Y_n in essential places; the MD analogue has different noise terms and extra cross terms. This is a load-bearing gap, and the paper should not present Theorem 2(a) as proved until that proof appears. Second, the paper invokes a 'Bregman reciprocity condition' without stating it. Under the paper's own assumptions (K-strong convexity and Lh-Lipschitz ∇h), D(x,y) ≥ (K/2)||x-y||² and D(x,y) ≤ (Lh/2)||x-y||² on the compact domain, so both uses are justified. This is a presentation gap, not a correctness gap. A one-line lemma would close it. Third, a minor constant mismatch in Theorem 3: the proof concludes D ≤ 4ε while the theorem states ε; the stated step-size condition (12) should use ε/4 on the right. This is easily fixed.\n\nWho gets value: anyone doing saddle-point or GAN convergence theory, and anyone who needs to know whether the original ICLR claims are safe to cite. The paper deserves a serious referee — the corrections are substantive — but the missing MD proof is a genuine blocker for acceptance in the current form.","headline":"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.","tokens_in":13034,"tokens_out":5488,"would_cite":true,"duration_ms":54260,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","90C47","49J40"],"pacs":[],"model":"deepseek-v4-flash","headline":"Optimistic mirror descent converges to saddle points, but its monotone decrease begins only after a burn-in phase.","keywords":["saddle point problems","optimistic mirror descent","mirror descent","Bregman divergence","coherence","stochastic gradients","high-probability convergence","variational inequalities"],"falsifier":"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.","tokens_in":11918,"feed_emoji":"🎯","tokens_out":5295,"duration_ms":47606,"temperature":0.7,"pith_summary":"This paper re-examines convergence guarantees for Mirror Descent (MD) and Optimistic Mirror Descent (OMD) on saddle-point problems that satisfy a coherence condition introduced in earlier work. It proves that OMD with exact gradients does converge to a saddle point, but the Bregman distance to the solution becomes monotone decreasing only after a sufficiently large number of iterations, not from the first iterate as previously claimed. For strictly coherent problems with stochastic gradients, the paper shows that only high-probability eventual convergence to within any tolerance can be rigorously established, rather than almost-sure convergence. The practical upshot is a more careful, slightly weaker set of guarantees for algorithms used in adversarial training and game-theoretic settings.","feed_headline":"Optimistic mirror descent converges to saddle points — eventually","feed_subtitle":"A correction to prior proofs: stochastic OMD gives high-probability, not almost-sure, convergence.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the coherence definition, the original OMD and MD convergence claims, and the proof techniques that the paper re-examines and corrects.","marker":"[1]"},{"why":"Provides the core proof ideas and the step-size condition technique used in the stochastic convergence analysis.","marker":"[2]"},{"why":"Establishes the equivalence between saddle-point solutions and Stampacchia/Minty variational inequalities used to characterize convergence targets.","marker":"[4]"},{"why":"Supplies the stochastic mirror descent convergence analysis and martingale arguments on which the high-probability bounds are built.","marker":"[5]"}],"fun_headline_variants":["OMD converges, but monotone only after many iterations","Stochastic OMD: high-probability, not almost-sure convergence","Correcting OMD proofs: high-probability for stochastic case","Saddle point OMD: late monotonicity and proof repairs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["OMD converges, but monotone only after many iterations","Stochastic OMD: high-probability, not almost-sure convergence","Correcting OMD proofs: high-probability for stochastic case","Saddle point OMD: late monotonicity and proof repairs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000193,"raw_usage":{"total_tokens":1370,"prompt_tokens":988,"completion_tokens":382,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":604,"completion_tokens_details":{"reasoning_tokens":307}},"tokens_in":604,"tokens_out":382,"duration_ms":4618,"temperature":1.0,"reasoning_tokens":307,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:25:03.903086+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Optimistic mirror descent in saddle-point problems: Goin g the extra(-gradient) mile,","cited_arxiv_id":null,"evidence_quote":"Supplies the coherence definition, the original OMD and MD convergence claims, and the proof techniques that the paper re-examines and corrects."},{"cited_title":"Variational inequalities and optimiza tion problems,","cited_arxiv_id":null,"evidence_quote":"Establishes the equivalence between saddle-point solutions and Stampacchia/Minty variational inequalities used to characterize convergence targets."},{"cited_title":"Stochastic mirror de scent dynamics and their conver- gence in monotone variational inequalities,","cited_arxiv_id":null,"evidence_quote":"Supplies the stochastic mirror descent convergence analysis and martingale arguments on which the high-probability bounds are built."}],"review_version":1}