{"id":"51c0175c-18d1-41e3-a99c-83faf0118422","arxiv_id":"1908.08465","paper_version":2,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Single-call stochastic extra-gradient methods achieve O(1/t) ergodic convergence in deterministic monotone variational inequalities and O(1/t) last-iterate local convergence around regular solutions in stochastic non-monotone variational inequalities.","lead":"This paper proves that single-call variants of the extra-gradient method for variational inequalities, which use one gradient evaluation per iteration instead of two, keep the optimal 1/t convergence rate in deterministic monotone problems and achieve a 1/t local rate around stable solutions in stochastic non-monotone problems.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified.","rationale":"The reader's ACCEPT verdict is justified. I re-examined the proof of Theorem 6, the most technically demanding part of the paper, focusing on the conditional-bias argument, the recursion (C.49), the probability estimate for E_infinity, and the use of Chung's lemma. Each step is coherent: the indicator 1_{E_t} is F_t-measurable, so the noise term vanishes in expectation; the descent inequality yields a clean one-step recursion for a_t = E[||X_t - x*||^2 1_{E_{t-1}}]; and the leading constant matches the statement. The regularity assumption is indeed the key hypothesis, as the reader notes, but it is precisely stated and used only through Lemma A.4, which derives the needed local strong monotonicity. The only notable presentation flaw is the table/prose calling the stochastic ergodic strongly monotone rate O(1/t) when Theorem 5 gives O(log t/t); since the abstract and theorem statements are correct, this does not affect the validity of the central claim. I therefore see no load-bearing concern, and no change to the verdict is needed.","tokens_in":28136,"tokens_out":22729,"duration_ms":201745,"concrete_test":"Run a numerical simulation of PEG on a one-dimensional non-monotone VI with a regular solution, e.g., V(x) = x - x^3 on X = R with x* = 0, using step-size gamma_t = gamma/(t+b) with gamma > 1 and b chosen so that the iterates stay near 0 with high probability, and additive zero-mean noise with variance sigma^2. Verify that the empirical conditional squared error, averaged over trajectories that never leave a small neighborhood of 0, decays as ~C/t with C matching the leading constant in Eq. (16) up to a small factor. This would confirm the O(1/t) local rate and the dependence on alpha, M, sigma, and delta.","verdict_should_be":"UNCHANGED","load_bearing_attack":"After checking the proof of Theorem 6, I find the central claim to be internally consistent and well-supported. The local non-monotone result rests on the regularity condition (Definition 3, Eq. 12), which Lemma A.4 correctly converts into local strong monotonicity plus Lipschitz bounds on a neighborhood U. The proof of Theorem 6 carefully handles the conditioning on the stay-in-neighborhood event E_infinity: the recursion (C.49) bounds E[||X_t - x*||^2 1_{E_{t-1}}] using the zero-mean noise property with respect to the filtration and the indicator of the F_t-measurable event E_{t-1}; the final division by P(E_infinity) >= 1-delta is then valid because E_infinity is a subset of E_{t-1}. The probability bound P(E_infinity) >= 1-delta follows from the uniform bound P(H_T^c) <= Gamma M/epsilon, which goes to 0 as b is taken large; this is a standard high-probability argument. The unquantified 'large enough b' and the unspecified neighborhood sizes are limitations on explicit constants, but not gaps in the argument: the theorem's existential form is appropriate for a local convergence result. The ergodic rate in Theorem 5 is stated as O(log t/t), so the table/prose omission of the log factor is a presentation issue, not a correctness issue. Overall, no load-bearing concern invalidates the central claim.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies single-call extra-gradient (1-EG) methods for variational inequalities: Past Extra-Gradient (PEG), Reflected Gradient (RG), and Optimistic Gradient (OG). It develops a synthetic quasi-descent framework (Lemma 2) and uses it to prove that, in deterministic monotone problems with Lipschitz operators, all three variants achieve the optimal O(1/t) ergodic convergence rate (Theorem 1). It then analyzes the stochastic PEG variant: under strong monotonicity, it proves O(1/t) last-iterate convergence and O(log t/t) ergodic convergence (Theorem 5), and, near a regular solution of a possibly non-monotone VI, it proves a high-probability local O(1/t) last-iterate rate conditionally on the iterates staying in a neighborhood of the solution (Theorem 6). The appendix contains detailed proofs, including a careful event-based treatment of the conditioning bias in the stochastic local analysis.","tokens_in":28268,"tokens_out":12978,"duration_ms":120613,"significance":"If correct, the paper closes an important gap by showing that single-call extra-gradient methods retain the optimal rate of the two-call Extra-Gradient method in deterministic monotone problems, and it provides the first stochastic local rate guarantee for non-monotone variational inequalities under a second-order sufficient condition. The unified treatment of PEG, OG, and RG via Lemma 2 is a useful organizational contribution. The proof of Theorem 6 is careful and self-contained: it handles the zero-mean noise property under the stay-in-neighborhood filtration, controls the probability of the large-deviation events via a martingale-type recurrence, and only then applies Chung's lemma. The paper's rate claims are concrete and falsifiable, and the numerical experiments are consistent with the stated rates.","major_comments":[{"comment":"The statement of Theorem 1, Eq. (9), uses the error function Err_R defined in Eq. (4) with X_R = X ∩ B_R(0). However, the proof of Lemma 2 in Appendix B.1 explicitly replaces this by X_R = X ∩ B_R(X_1) (the ball centered at X_1). With the original definition, the bound should involve sup_{p in X∩B_R(0)} ||X_1 - p||^2, which depends on ||X_1|| and is not bounded by R^2 in general. Thus the theorem as stated is not valid under the paper's own definition of Err_R. This is load-bearing for the first contribution's quantitative claim, although the O(1/t) rate is preserved once the statement is corrected. Please either redefine Err_R in the theorem statement as centered at X_1 or adjust the right-hand side accordingly.","section":"Section 4.1, Theorem 1 and Appendix B.1"},{"comment":"Theorem 4 claims local geometric convergence for every 1-EG method under Definition 3 (regularity along rays tangent to X). But the proof in Appendix B.4 states that, since RG can evaluate V at infeasible points, the regularity condition (12) must be strengthened to hold for all z in the tangent span of X rather than only for z tangent to X. Therefore the theorem as stated overclaims for the RG variant. This is a genuine gap in the statement's generality; it should be fixed by either restricting Theorem 4 to PEG and OG or stating the stronger regularity condition for RG.","section":"Section 4.2, Theorem 4 and Appendix B.4"}],"minor_comments":[{"comment":"The abstract and Table 1 state an O(1/t) stochastic ergodic rate, while Eq. (14) gives O(log t / t) for the ergodic average. The table's footnote 'logarithmic factors ignored' softens this, but the main text near Theorem 5 says 'both the last iterate and the ergodic average of 1-EG achieve a O(1/t) convergence rate'; this should be reworded to avoid a strict misstatement.","section":"Abstract, Table 1, and Theorem 5"},{"comment":"The symbol M is overloaded: in the proof, M := 4M^2 + 4σ^2 + 4r^2σ^2 is introduced after using M = sup_{x in U} ||V(x)|| from Theorem 6. Please use a different symbol, e.g., M_bar, for the new constant to avoid confusion.","section":"Lemma C.2"},{"comment":"The condition 'large enough b' is left unquantified; the proof only shows existence via Γ ≤ δ ε / M. Since the theorem is an existential local result this is acceptable, but an explicit lower bound on b in terms of α, γ, r, M, σ, and δ would strengthen the statement.","section":"Theorem 6"}],"recommendation":"major_revision","confidential_remarks":"The central stochastic result, Theorem 6, appears correct and is well supported by the appendix; the event-based conditioning argument is sound. The main problems are the mismatches between theorem statements and proofs in the deterministic results (Theorem 1's Err_R definition and Theorem 4's applicability to RG). These are fixable, but they are load-bearing for the theorems as written. I see no issues of attribution or novelty; the paper is a solid contribution for a mathematical optimization or machine learning venue."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Worth a serious referee. The paper does something real: it gives a single quasi-descent inequality that covers Past Extra-Gradient, Reflected Gradient, and Optimistic Gradient, and it proves optimal O(1/t) ergodic rates for deterministic monotone VIs. The deterministic part overlaps with Mokhtari et al., but the paper acknowledges that and the unified proof is a clean organizing device on its own.\n\nThe genuinely new piece is Theorem 6: for non-monotone VIs with a regular solution, the last iterate of single-call stochastic PEG converges at O(1/t) locally, with high probability, despite the noise. I checked the proof structure and the stress test is right: the event-based argument correctly handles the conditioning bias, and Lemma A.4 legitimately converts the second-order condition into local strong monotonicity. The recursion (C.49) through (C.51) is sound. This is the first result of its kind for stochastic non-monotone problems, and it deserves credit.\n\nSoft spots, in proportion. First, the ergodic rate in Theorem 5 is log t / t, not 1/t. The abstract and theorem state it correctly, but the introduction says the stochastic rate is O(1/t) for both ergodic and last iterate, and Table 1 lists 1/t with a fine-print warning that log factors are ignored. That is a presentational overclaim, not a math error, but it should be fixed in revision. Second, Theorem 6 is existential: \"large enough b\" and the neighborhoods U and U1 are never quantified. That is normal for local results, and it does not undermine the claim, but it limits practical guidance. Third, the local rate conditions on the event that all iterates stay in U, which occurs only with probability 1-delta; the paper is honest about this, but readers should not come away thinking this is a global guarantee.\n\nCitation pattern is clean. Prior geometric convergence results are cited rather than re-derived, and the concurrent work by Mokhtari et al. is acknowledged. No circularity.\n\nWho gets value: anyone working on variational inequality algorithms, min-max optimization, or GAN training theory who wants to know whether one oracle call per iteration is enough. The paper is rigorous, self-contained, and the central claims hold up. Send it to review; the referee should flag the log/1/t wording and ask for a remark quantifying b, but I would expect acceptance after minor revision.","headline":"A genuinely useful unification of single-call extragradient variants, with a new local stochastic O(1/t) last-iterate result that appears correct; the main flaw is a presentation overclaim on the ergodic rate.","tokens_in":28926,"tokens_out":1786,"would_cite":true,"duration_ms":20434,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65K15","90C33","90C25","62L20"],"pacs":[],"model":"deepseek-v4-flash","headline":"Single-call extra-gradient keeps the optimal O(1/t) convergence rate.","keywords":["single-call extra-gradient","variational inequalities","stochastic approximation","non-monotone operators","last-iterate convergence","O(1/t) rate","regular solution","min-max optimization"],"falsifier":"Run Past Extra-Gradient on a smooth non-monotone variational inequality whose origin satisfies z^T Jac V(0) z > 0 for all tangent directions, with zero-mean bounded-variance noise and step-size γ/(t+b); if the fraction of trajectories that remain in the designated neighborhood U is less than 1 − δ for arbitrarily large b, or the conditional mean-square last-iterate error does not decay like 1/t, the theorem's claim is contradicted.","tokens_in":27847,"feed_emoji":"📉","tokens_out":7763,"duration_ms":72709,"temperature":0.7,"pith_summary":"The paper targets variational inequalities, a framework covering min-max and GAN-style problems that go beyond ordinary loss minimization. It aims to show that single-call extra-gradient methods, which use one gradient oracle call per iteration instead of two, do not sacrifice the optimal O(1/t) convergence rate. In deterministic monotone problems, it proves O(1/t) ergodic convergence for a common family of such methods. Its main new result is local: for non-monotone stochastic problems near a regular solution, the last iterate of the Past Extra-Gradient method still converges at O(1/t) with high probability. This matters because a second gradient call per step is often a major computational cost in deep learning, and no comparable stochastic guarantee existed for non-monotone variational inequalities.","feed_headline":"Single-call extra-gradient keeps the optimal O(1/t) rate","feed_subtitle":"Near a regular solution, the last iterate of Past Extra-Gradient still converges at 1/t even with noisy gradients.","key_machinery":"The load-bearing mechanism is the regularity condition: the Jacobian Jac V(x*) is positive definite along every nonzero tangent direction to the feasible set at x*. A technical lemma converts this into local strong monotonicity and local Lipschitz bounds on a small neighborhood U. The stochastic proof then wraps this local strong monotonicity in an event-stability argument: it constructs nested events that control weighted sums of noise and gradient norms, proves that these events force the iterates to remain in U, shows that this happens with probability at least 1 − δ for a large enough step decay offset b, and applies a one-dimensional recurrence lemma to the resulting quasi-Fejér inequality to extract the 1/t rate.","core_discovery":"The paper's central claim is that the single-call penalty vanishes asymptotically. Theorem 1 shows that in deterministic monotone Lipschitz variational inequalities, Past Extra-Gradient, Reflected Gradient, and Optimistic Gradient all achieve the optimal O(1/t) ergodic error with a constant step-size, matching the two-call Extra-Gradient method. The paper then goes beyond monotone problems: Theorem 6 states that if x* is a regular solution, meaning the Jacobian of the operator at x* is positive definite along every nonzero tangent direction, then the Past Extra-Gradient method run with a stochastic oracle and step-size γ/(t+b) satisfies E[||X_t − x*||^2 | E∞] ≤ $4γ^{2}$($M^{2}$ + $σ^{2}$)/((αγ − 1)(1 − δ)) · 1/t + o(1/t), where E∞ is the event that all iterates stay in a fixed neighborhood of x*, which occurs with probability at least 1 − δ. Thus, even with noise and non-monotonicity, the last iterate converges in mean square at the optimal local 1/t rate.","pith_inferences":["The same event-based template should carry over to the Reflected Gradient and Optimistic Gradient variants, since all three updates coincide in the unconstrained case; the paper's explicit stochastic analysis is written for Past Extra-Gradient only.","If the local theorem is right, near a stable equilibrium of a min-max game halving the gradient oracle cost costs nothing asymptotically; the missing practical ingredient is a computable rule for the decay offset b and the initialization ball, since the proof only says they must be large enough.","A testable extension would derive a non-asymptotic tail bound on the escape event E∞; the current result only guarantees P(E∞) ≥ 1 − δ and bounds the conditional mean-square error.","The proof technique suggests that local non-monotone convergence rates can be obtained for other stochastic methods with diminishing step-sizes, provided a local strong-monotonicity neighborhood can be certified."],"forward_implications":["In deterministic monotone variational inequalities, the single-call variants match the two-call Extra-Gradient method's optimal O(1/t) ergodic rate, halving the per-iteration gradient cost.","In stochastic strongly monotone problems, the last iterate of Past Extra-Gradient converges at mean-square O(1/t), and the ergodic average at O(log t / t), under a zero-mean bounded-variance oracle.","In non-monotone stochastic problems with a regular solution, the last iterate converges locally at O(1/t) conditioned on staying near the solution, which occurs with probability at least 1 − δ.","Because isotropic stochastic noise rules out geometric convergence, O(1/t) is the best possible order, so the single-call penalty disappears in the asymptotic rate."],"supporting_citations":[{"why":"Introduces the single-call 'modified Arrow–Hurwicz' update that becomes Past Extra-Gradient, the algorithm analyzed in Theorem 6.","marker":"[39]"},{"why":"Introduces the two-call Extra-Gradient method whose optimal rate the paper matches with one oracle call per iteration.","marker":"[24]"},{"why":"Provides the variational-inequality analysis of single-call methods in GAN-style settings and geometric last-iterate results that the paper extends to stochastic and non-monotone problems.","marker":"[19]"},{"why":"Supplies the Reflected Gradient variant and the deterministic monotone convergence tools used in the paper's unified proof.","marker":"[26]"},{"why":"Gives the stochastic O(1/√t) ergodic rate for reflected methods, the baseline that Theorem 5 improves to O(1/t).","marker":"[14]"},{"why":"Supplies the recurrence lemma that turns decayed-step recursions into O(1/t) bounds, used in both Theorem 5 and Theorem 6.","marker":"[11]"},{"why":"Provides the forward-backward-forward splitting framework whose inequalities underpin the deterministic quasi-descent proof.","marker":"[45]"}],"fun_headline_variants":["Single-call extra-gradient matches optimal rate","Stochastic extra-gradient last iterates hit O(1/t) locally","Optimal O(1/t) convergence without extra gradient step","Single-call methods preserve optimal convergence for VIs","Last-iterate single-call extra-gradient: optimal local rate"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the solution is regular, meaning the Jacobian there is positive definite on all tangent directions, and that the algorithm starts inside a small unquantified ball around it with a step decay offset b that is large enough but never given a concrete threshold.","fun_headline_variants_meta":{"raw":{"variants":["Single-call extra-gradient matches optimal rate","Stochastic extra-gradient last iterates hit O(1/t) locally","Optimal O(1/t) convergence without extra gradient step","Single-call methods preserve optimal convergence for VIs","Last-iterate single-call extra-gradient: optimal local rate"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000192,"raw_usage":{"total_tokens":1367,"prompt_tokens":985,"completion_tokens":382,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":601,"completion_tokens_details":{"reasoning_tokens":310}},"tokens_in":601,"tokens_out":382,"duration_ms":3532,"temperature":1.0,"reasoning_tokens":310,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:39:07.806030+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Past Extra-Gradient on a smooth non-monotone variational inequality whose origin satisfies z^T Jac V(0) z > 0 for all tangent directions, with zero-mean bounded-variance noise and step-size γ/(t+b); if the fraction of trajectories that remain in the designated neighborhood U is less than 1 − δ for arbitrarily large b, or the conditional mean-square last-iterate error does not decay like 1/t, the theorem's claim is contradicted.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces the single-call 'modified Arrow–Hurwicz' update that becomes Past Extra-Gradient, the algorithm analyzed in Theorem 6."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces the two-call Extra-Gradient method whose optimal rate the paper matches with one oracle call per iteration."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the variational-inequality analysis of single-call methods in GAN-style settings and geometric last-iterate results that the paper extends to stochastic and non-monotone problems."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the Reflected Gradient variant and the deterministic monotone convergence tools used in the paper's unified proof."},{"cited_title":"Shanbhag","cited_arxiv_id":null,"evidence_quote":"Gives the stochastic O(1/√t) ergodic rate for reflected methods, the baseline that Theorem 5 improves to O(1/t)."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the recurrence lemma that turns decayed-step recursions into O(1/t) bounds, used in both Theorem 5 and Theorem 6."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the forward-backward-forward splitting framework whose inequalities underpin the deterministic quasi-descent proof."}],"review_version":1}