{"id":"f5d6a381-6798-4b85-bf3a-24549a738960","arxiv_id":"2501.00511","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"SEG-FFA achieves O~(1/K^{1/3}) convergence in convex-concave and O~(1/nK^4) in strongly-convex-strongly-concave finite-sum minimax problems, with lower bounds showing the gain over SGDA/SEG with random reshuffling.","lead":"This paper introduces SEG-FFA, a stochastic extragradient method that uses flip-flop shuffling plus an anchoring step, and proves that it converges on convex-concave finite-sum minimax problems where prior stochastic extragradient variants can diverge. The method is also shown to converge provably faster in strongly-convex-strongly-concave settings.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The advertised rates are conditional on the Lipschitz-Hessian assumption on component saddle gradients; without Assumption 3.3(ii) the O(eta^3) second-order matching is unsupported, so the claimed improvements are not established beyond that function class.","rationale":"The reader correctly identified Assumption 3.3(ii), the Lipschitz continuity of each component saddle gradient's derivative, as the most fragile premise. Tracing through the proof confirms it is structurally load-bearing: the O(eta^3) deterministic error bound in Theorem E.1, which is the foundation for both Theorem 5.4 and Theorem 5.5, is obtained by bounding second-order Taylor remainders of the form F_j w_j - F_j z_0 - DF_j(z_0)(w_j - z_0). Lemma C.6 is the exact tool that converts a Lipschitz Hessian into an O(eta^3) contribution; without it, the best available control is lower order. So the concern is genuine as a scope limitation. However, it is not an internal inconsistency: the theorems explicitly assume M-smoothness, and the authors transparently state in Section 3 that the assumption is strong and that relaxing it is future work. The paper also gives independent support in the form of detailed proofs, explicit constants, and experiments on quadratics, although the experiments do not stress the M-smoothness assumption. I find no concrete flaw in the main mathematical argument beyond this well-acknowledged premise. The reader's CONDITIONAL verdict already captures the fragility, so no verdict change is warranted; the condition can be understood as 'conditional on accepting M-smoothness as a reasonable scope restriction.'","tokens_in":76723,"tokens_out":22994,"duration_ms":216221,"concrete_test":"Independently re-derive the per-epoch error bound, Proposition 5.3 and Theorem E.9, without invoking Assumption 3.3(ii), replacing the Lemma C.6 bound on term (62b) with the best possible bound using only L-smoothness. If the error exponent a drops from 3 to 2, the claimed rates are indeed conditional on the Lipschitz-Hessian premise. A complementary numerical probe: run SEG-FFA on a finite-sum monotone problem whose components are L-smooth but have non-Lipschitz Hessians, e.g., F_i(z) = z + epsilon z^3/(1+z^2) arranged so the full operator is monotone, and compare the observed epoch-wise error decay against the O(1/K^{1/3}) prediction.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central rates rely on the within-epoch error bound in Theorem E.1. For SEG-FFA, the proof shows a deterministic error of order eta^3 n^3 (a=3 in the notation of Theorem E.1) only by controlling the term (62b), -eta/2 sum_j [F_j w_j - F_j z_0 - DF_j(z_0)(w_j - z_0)], via Lemma C.6, which uses the M-smoothness of each F_j (Assumption 3.3(ii)). Without a Lipschitz bound on DF_j, that Taylor remainder is only o(eta) per term, so the whole term is o(eta^2) rather than O(eta^3); the exponent a would drop to at most 2. Consequently, the monotone rate in Theorem 5.4, O((log K)^2 / K^{1/3}), and the strongly monotone speedup in Theorem 5.5, O((log(n^{1/4}K))^4 / (n K^4)), would not follow, and SEG-FFA would be no better than SEG-RR in the error-order hierarchy. This is not a hidden contradiction: the paper explicitly acknowledges in Section 3 that M-smoothness is a strong assumption and leaves its relaxation to future work. The concern is therefore about scope: the central claim of provable improvements applies only to component saddle gradients with Lipschitz Hessians, and the experiments use quadratics, where M=0 and the assumption holds trivially.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies same-sample stochastic extragradient (SEG) variants with shuffling schemes for unconstrained finite-sum minimax problems. It first proves, via a two-component bilinear counterexample, that SEG with uniform sampling, random reshuffling, and flip-flop shuffling can all diverge in monotone problems. The authors then identify a second-order Taylor-matching condition that separates convergent from divergent SEG variants, and propose SEG-FFA, which combines flip-flop shuffling with an anchoring step. Under (star-)monotonicity, smoothness, and a component-variance assumption, SEG-FFA is shown to attain min_{k<=K} E||F z^k_0||^2 = O((log K)^2/K^{1/3}); under strong monotonicity it attains E||z^K_0 - z*||^2 <= exp(-c mu omega n K)||z^0_0 - z*||^2 + O((log(n^{1/4}K))^4/(nK^4)). The paper also proves Omega(1/(nK^3)) lower bounds for SGDA-RR and SEG-RR on quadratic strongly monotone instances, establishing a separation in the K-exponent. The proof is supported by detailed appendices, and experiments on random quadratics match the theory.","tokens_in":77032,"tokens_out":11142,"duration_ms":105423,"significance":"If the results are correct, SEG-FFA is a meaningful advance: it provides an explicit convergence rate for a same-sample shuffling-based SEG in unconstrained convex-concave finite-sum problems, and it identifies a design principle, second-order matching with anchoring, that could be reused. The paper's strengths include complete proofs with explicit constants, clean divergence counterexamples, and lower-bound constructions tailored to the assumptions. The upper and lower bounds are internally consistent, and the experiments corroborate the qualitative predictions. The main reservation is scope: the advertised improvements are conditional on the Lipschitz-Hessian assumption on each component saddle gradient (Assumption 3.3(ii)), and the numerical validation is limited to quadratics, where that assumption holds trivially. The contribution is nonetheless solid within its stated assumptions.","major_comments":[{"comment":"The advertised rates in Theorems 5.4 and 5.5 are load-bearing on Assumption 3.3(ii), the M-smoothness of each Fi. In the proof of Proposition 5.3 and Theorem E.1, the O(eta^3) within-epoch error for SEG-FFA depends on controlling the Taylor remainder in Eq. (62b) via Lemma C.6, which requires a Lipschitz bound on DF_j. Without Assumption 3.3(ii), that remainder is only o(eta) per term, so the error exponent a in Theorem E.1 drops to at most 2 and the monotone rate O((log K)^2/K^{1/3}) and the strongly monotone speedup O((log(n^{1/4}K))^4/(nK^4)) do not follow. The paper itself acknowledges this in Section 3, but the abstract and Section 1.1 present the rates without this qualification, and Section 6 validates only quadratic problems where M=0. Please state the M-smoothness requirement prominently in the abstract and contributions, add at least one non-quadratic experiment satisfying Assumption 3.3(ii) with M>0, or explicitly state that the empirical validation does not exercise the key assumption.","section":"Section 3, Proposition 5.3, Theorem E.1"},{"comment":"The paper's novelty claim of being the first same-sample SEG with an explicit monotone convergence rate rests on the assertion that the monotone SEG-RR result of Emmanouilidis et al. [18] is flawed. The critique, that Jensen's inequality is applied to weights 1/G^k that do not sum to 1, is plausible, but it is given in one paragraph without reproducing the exact equation from [18] and without showing that the surrounding argument cannot be repaired. Since Theorem 4.1 of the present paper directly contradicts the monotone claim of [18], the appendix should present a self-contained, step-by-step exposition of the flaw, including the exact equation in [18] and why the corrected inequality cannot restore the claimed convergence.","section":"Appendix B.4"},{"comment":"Theorem 5.6 as stated in the main text omits the condition L/mu >= 2 that is required by the constructions in Theorem H.6 and by the Safran-Shamir lower bound cited in Appendix H.3.1. Without this condition, the case analysis in Appendix H.3.3, in particular the bound in Case 3 that uses L/mu >= 2, does not cover the full parameter range. Please either add this condition to the theorem statement or extend the argument to the regime 1 <= L/mu < 2.","section":"Theorem 5.6"}],"minor_comments":[{"comment":"It would be helpful to give an explicit example of a non-quadratic component satisfying Assumption 3.3(ii) with M>0, to show that the assumption is not vacuous outside the quadratic case.","section":"Section 3, Assumption 3.3"},{"comment":"The O-tilde notation in Table 1 and the main theorems should clarify that the hidden constants depend on n, sigma, rho, and the problem data; a reader could otherwise read the rates as depending only on K.","section":"Table 1 and Theorems 5.4-5.5"},{"comment":"The experimental section reports only geometric means over five random instances without error bars or ranges; since the paper is primarily theoretical this is acceptable, but the captions and text should state explicitly that no statistical significance is claimed.","section":"Section 6"},{"comment":"The statement of Theorem 5.5 says the constant omega is independent of eta, but the proof in Theorem F.5 defines omega as a minimum of constants depending on the problem data and on the initial gradient bound; this quantification should be stated precisely in the main theorem.","section":"Theorem 5.5 and Appendix F.5"},{"comment":"There are occasional typographical and phrasing issues, for example 'the results of the geometric mean' in Section 6 and the incomplete sentence after Eq. (102) in Appendix F; a careful proofreading pass would improve readability.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The paper is technically solid within its assumptions, and I do not see an internal inconsistency; the main issue is scope. The central rates depend essentially on the Lipschitz-Hessian assumption, and the experiments do not test that assumption. I recommend major revision focused on framing and on providing at least one non-quadratic experiment, as well as on a fuller documentation of the critique of [18]. The editor may also wish to verify the Appendix B.4 claim, since it affects the paper's novelty statement."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Chae, Yun, and Kim have a genuinely new result here: SEG-FFA is, to my knowledge, the first same-sample shuffling-based SEG with an explicit convergence rate for unconstrained convex-concave finite-sum problems. The rate O~(1/K^{1/3}) may look modest, but it beats the divergence of SEG-US/RR/FF, which they prove with a clean 2-component counterexample. The strongly monotone rate O~(1/nK^4) with a matching lower bound of Omega(1/nK^3) for SGDA-RR and SEG-RR is a real gap, and the lower-bound construction is careful.\n\nThe design principle is the best part. Framing the problem as matching the Taylor expansion of EG up to second order explains why RR and FF fail, and why adding an anchoring step fixes it. The unified error analysis in Theorem E.1, with the exponent a distinguishing methods, is a useful contribution in itself. The proofs are long and I haven't line-checked them, but the structure is coherent and the constants are explicit.\n\nNow the soft spots. The main one is exactly what the stress-test note flags: the O(eta^3) within-epoch error that powers both Theorem 5.4 and 5.5 depends on Assumption 3.3(ii), the M-smoothness (Lipschitz Hessian) of each component Fi. Without it, the Taylor remainder term (62b) is only o(eta^2), the exponent a drops from 3 to 2, and SEG-FFA is no better than SEG-RR. This is not a hidden flaw—the paper says in Section 3 that this is a strong assumption and leaves relaxation to future work—but it does mean the advertised 'provable improvements' are only proven for a function class that, in practice, is essentially quadratics. The experiments are all on quadratics, where M=0, so they don't test the assumption at all. The lack of error bars and public code in the arXiv version is minor but annoying for a paper whose empirical section is meant to support the theory.\n\nOne more thing: the ablation in Appendix I.2 shows SEG-RRA with alpha=beta/2—just random reshuffling plus anchoring, no flip-flop—seems to converge empirically, and the authors conjecture it achieves second-order matching in expectation. That slightly undercuts the 'flip-flop is necessary' narrative, though they are honest that they have no proof.\n\nWho's this for? Anyone working on shuffling-based stochastic methods or minimax optimization theory. It deserves a serious referee; the conditional acceptance from the reader is about right. The main thing I'd want from the authors in revision is a clearer statement of what happens without M-smoothness—does the method still converge at a slower rate, or can the assumption be relaxed?—and ideally one non-quadratic experiment.\n\nI'd send it to review.","headline":"Solid theory result with a real advance, but the headline rates rest on a Lipschitz-Hessian assumption that confines the practical claims to quadratics.","tokens_in":77587,"tokens_out":2131,"would_cite":true,"duration_ms":20510,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C47","65K10","49J40","68W20"],"pacs":[],"model":"deepseek-v4-flash","headline":"Two simple modifications to stochastic extragradient give it provable convergence in convex-concave minimax problems and a faster strongly-monotone rate.","keywords":["stochastic extragradient","flip-flop shuffling","anchoring","convex-concave minimax","random reshuffling","strongly monotone variational inequalities","second-order matching","finite-sum optimization"],"falsifier":"Construct a finite-sum monotone minimax problem whose components are L-smooth but have non-Lipschitz Hessians (for example, a piecewise-quadratic saddle function that is still convex-concave overall) and measure the within-epoch error $\\|z^{k+1}_0 - (z^k_0 - \\eta_k n F(z^k_0 - \\eta_k n F z^k_0))\\|$; if it scales as $\\eta^2$ rather than $\\eta^3$, then Theorem 5.4's $O((\\log K)^2/K^{1/3})$ rate cannot hold for that class, directly contradicting the paper's claim that M-smoothness suffices.","tokens_in":76531,"feed_emoji":"⚖️","tokens_out":4478,"duration_ms":45143,"temperature":0.7,"pith_summary":"The paper tries to establish that a minimal modification of stochastic extragradient (SEG), combining flip-flop shuffling with an anchoring step, makes the method converge in unconstrained convex-concave finite-sum minimax problems with an explicit rate, while also provably speeding up convergence in the strongly convex-strongly concave case. It shows that shuffling alone, either random reshuffling or the recent flip-flop scheme, is not enough: those SEG variants can diverge in the convex-concave setting. The paper provides a design principle, second-order matching to the deterministic extragradient method, explains why previous stochastic methods fail it, and proves that SEG-FFA fulfills it.","feed_headline":"Flip-flop shuffling plus anchoring fixes stochastic extragradient","feed_subtitle":"It provably converges where shuffling-based SEG diverges, and beats baseline rates when the problem is strongly monotone.","key_machinery":"The central device is second-order matching: within one epoch, SEG-FFA's update is shown to match the deterministic extragradient update EG up to error $O(\\eta^3)$, whereas SEG-RR only matches to first order (error $O(\\eta^2)$) and flip-flop-only SEG would require parameters that make EG+ diverge. Flip-flop sampling (two passes through the components in reversed order) supplies all the cross terms $DF_j(z_0)F_i z_0$ needed in the Taylor expansion, and the anchoring step of averaging $z^N$ with $z^0$ divides the coefficients appropriately so that the epoch update becomes EG with the correct stepsize ratio $\\eta_1=\\eta_2$.","core_discovery":"The paper claims that SEG-FFA, stochastic extragradient with flip-flop sampling and anchoring, achieves in the (star-)monotone setting the bound $\\min_{k=0,\\dots,K} \\mathbb{E}\\|F z^k_0\\|^2 = O((\\log K)^2 / K^{1/3})$ when stepsizes are chosen as $\\beta_k = O(1/k^{1/3}\\log k)$ and $\\alpha_k = \\beta_k/2$, and in the $\\mu$-strongly monotone setting achieves $\\mathbb{E}\\|z^K_0 - z_*\\|^2 \\le \\exp(-c \\mu \\omega nK)\\|z^0_0 - z_*\\|^2 + O((\\log(n^{1/4}K))^4/(nK^4))$ for a constant $\\omega$ independent of the stepsize. It also proves that with the same problem settings, SEG-US, SEG-RR, and SEG-FF all diverge on a quadratic monotone counterexample, and that SGDA-RR and SEG-RR suffer $\\Omega(1/(nK^3))$ lower bounds, so SEG-FFA provides a provable speedup.","pith_inferences":["The same second-order-matching design principle could likely be applied to other stochastic operator-splitting methods (e.g., optimistic gradient or proximal point variants) to fix divergence in monotone settings, though the paper does not explore this.","The $O(1/K^{1/3})$ rate in the monotone setting may not be tight; the analysis suggests that more aggressive stepsize decay or variance reduction could push the rate toward $O(1/K^{1/2})$, but this is an editor's guess, not a claim of the paper.","The M-smoothness assumption (Lipschitz-Hessian of each component) is a genuine restriction; if it fails, the epoch-error drops to $O(\\eta^2)$ and the provable speedup disappears, so testing SEG-FFA on piecewise-smooth or nonsmooth-Hessian problems is a natural stress test.","The anchoring step is a fixed-point averaging reminiscent of Krasnoselskii-Mann iteration; combining it with Halpern-type anchoring on the initial point, which the paper explicitly distinguishes, could yield further acceleration, but the paper leaves that open."],"forward_implications":["SEG-FFA converges in unconstrained finite-sum convex-concave minimax problems with an explicit $\\widetilde{O}(1/K^{1/3})$ rate on squared-gradient norm, removing the need for bounded domains, increasing batch sizes, or uniformly bounded gradient variance.","In strongly monotone problems, SEG-FFA attains $\\widetilde{O}(1/(nK^4))$ last-iterate error, a polynomial order faster than the $\\Omega(1/(nK^3))$ lower bounds shown for SGDA-RR and SEG-RR.","The paper's counterexample (Theorem 4.1) shows that SEG-US, SEG-RR, and SEG-FF can diverge in expectation for any positive stepsizes on a simple quadratic monotone problem, so anchoring, not just shuffling, is essential for convergence.","The unified analysis in Theorem F.5 implies that any other stochastic method achieving the same second-order matching to EG would automatically enjoy the same convergence guarantees, not just SEG-FFA itself."],"supporting_citations":[{"why":"Supplies the extragradient method that SEG-FFA is designed to match and whose nonexpansiveness Lemma C.10 is used in the convergence analysis.","marker":"[29]"},{"why":"Provides the flip-flop shuffling scheme, the second pass in reversed order that makes all required cross terms appear in the second-order Taylor expansion.","marker":"[46]"},{"why":"Defines EG+ and its convergence condition $\\eta_1 \\ge \\eta_2$, which motivates the stepsize ratio that anchoring fixes.","marker":"[17]"},{"why":"Establishes the Taylor-expansion matching principle connecting EG to the proximal point method, the key design heuristic used here.","marker":"[38]"},{"why":"Gives the SGDA-RR $\\widetilde{O}(1/(nK^2))$ rate that SEG-FFA outperforms, and supplies the baseline for lower-bound comparison.","marker":"[15]"},{"why":"Provides the SEG-RR strongly-monotone rate ($\\widetilde{O}(1/(nK^2))$) that SEG-FFA improves upon, and whose claimed monotone convergence is analyzed and questioned in Appendix B.4.","marker":"[18]"},{"why":"Introduces the averaging/anchoring iteration idea (Krasnoselskii-Mann) that the anchoring step in SEG-FFA is built on.","marker":"[30, 33]"},{"why":"Supplies the shuffling variance bounds (Lemma 1 of that paper) used to control the epoch error terms in the proof of Theorem E.1.","marker":"[35]"}],"fun_headline_variants":["Anchored flip-flop SEG provably converges and speeds up","SEG-FFA beats shuffling SEG: converges + faster rates","Flip-flop + anchoring fixes SEG divergence, boosts rates","Provable speedup: anchored flip-flop shuffling rescues SEG"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof that one epoch of SEG-FFA tracks deterministic extragradient to third order requires every component Fi to have a Lipschitz-Hessian (M-smoothness, Assumption 3.3(ii)); if that fails, the error drops to second order and both the monotone convergence rate and the strongly-monotone speedup are lost.","fun_headline_variants_meta":{"raw":{"variants":["Anchored flip-flop SEG provably converges and speeds up","SEG-FFA beats shuffling SEG: converges + faster rates","Flip-flop + anchoring fixes SEG divergence, boosts rates","Provable speedup: anchored flip-flop shuffling rescues SEG"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000214,"raw_usage":{"total_tokens":1450,"prompt_tokens":996,"completion_tokens":454,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":612,"completion_tokens_details":{"reasoning_tokens":375}},"tokens_in":612,"tokens_out":454,"duration_ms":4863,"temperature":1.0,"reasoning_tokens":375,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T22:49:03.537225+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a finite-sum monotone minimax problem whose components are L-smooth but have non-Lipschitz Hessians (for example, a piecewise-quadratic saddle function that is still convex-concave overall) and measure the within-epoch error $\\|z^{k+1}_0 - (z^k_0 - \\eta_k n F(z^k_0 - \\eta_k n F z^k_0))\\|$; if it scales as $\\eta^2$ rather than $\\eta^3$, then Theorem 5.4's $O((\\log K)^2/K^{1/3})$ rate cannot hold for that class, directly contradicting the paper's claim that M-smoothness suffices.","supporting_citations":[{"cited_title":"Korpelevich","cited_arxiv_id":null,"evidence_quote":"Supplies the extragradient method that SEG-FFA is designed to match and whose nonexpansiveness Lemma C.10 is used in the convergence analysis."},{"cited_title":"Permutation-based SGD: Is random optimal? In International Conference on Learning Representations, 2022","cited_arxiv_id":null,"evidence_quote":"Provides the flip-flop shuffling scheme, the second pass in reversed order that makes all required cross terms appear in the second-order Taylor expansion."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines EG+ and its convergence condition $\\eta_1 \\ge \\eta_2$, which motivates the stepsize ratio that anchoring fixes."},{"cited_title":"A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach","cited_arxiv_id":null,"evidence_quote":"Establishes the Taylor-expansion matching principle connecting EG to the proximal point method, the key design heuristic used here."},{"cited_title":"Sampling without replacement leads to faster rates in finite-sum minimax optimization","cited_arxiv_id":null,"evidence_quote":"Gives the SGDA-RR $\\widetilde{O}(1/(nK^2))$ rate that SEG-FFA outperforms, and supplies the baseline for lower-bound comparison."},{"cited_title":"Stochastic extragradient with random reshuffling: Improved convergence for variational inequalities","cited_arxiv_id":null,"evidence_quote":"Provides the SEG-RR strongly-monotone rate ($\\widetilde{O}(1/(nK^2))$) that SEG-FFA improves upon, and whose claimed monotone convergence is analyzed and questioned in Appendix B.4."},{"cited_title":"Random reshuffling: Simple analysis with vast improvements","cited_arxiv_id":null,"evidence_quote":"Supplies the shuffling variance bounds (Lemma 1 of that paper) used to control the epoch error terms in the proof of Theorem E.1."}],"review_version":1}