{"id":"4ad4dce0-8d50-4481-813c-662437b463d8","arxiv_id":"1908.05699","paper_version":4,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"For bilinear zero-sum games, the paper derives necessary and sufficient convergence conditions and optimal linear rates for generalized GD, EG, OGD, and momentum methods, with Gauss-Seidel updates converging in a larger region than Jacobi updates.","lead":"This paper gives exact conditions for when gradient-based optimization methods converge on bilinear zero-sum games, for both simultaneous and alternating parameter updates. It also finds the best possible convergence rates and shows that alternating updates generally converge on a larger set of parameter choices.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.3's central OGD containment claim rests on a single Mathematica Reduce call in Appendix C.4.5; an independent check is needed.","rationale":"The paper's main contribution is exact convergence conditions and a Stein-Rosenberg-type comparison. The OGD containment is the only nontrivial case where 'Jacobi region contained in GS region' requires a substantial proof; it is advertised in Table 1 and the abstract. The proof in Appendix C.4.5 is a black-box CAS implication. The paper does include Mathematica code and outputs, which is real evidence, but unlike a formal proof certificate it cannot be checked by a reader without re-running the same opaque tool; if the reduction or the CAS result is wrong, the central claim fails. My reading of the algebra suggests the implication is likely correct: the Schur conditions are correctly derived, and the case analysis is consistent. However, the paper's own appendix notes that the code 'can be verified manually using cylindrical algebraic decomposition' without performing that verification. The second concern, Theorem 4.3's numerical asymptotic, is explicitly not proven; the theorem should at least be labeled as numerically observed or supplied with an analytic proof. Neither issue is fatal: the results are probably correct, and the experimental checks in Figures 2-3 are consistent. Hence the verdict remains CONDITIONAL: require an independent check of the CAS implication (or an analytic proof) and a proof or explicit conjecture status for the Theorem 4.3 asymptotic before the exact-rate claims are taken as established.","tokens_in":30488,"tokens_out":16273,"duration_ms":135128,"concrete_test":"Re-run the Appendix C.4.5 Reduce command in an independent quantifier-elimination system (e.g., QEPCAD or Mathematica with a fresh kernel) and cross-check with a dense high-precision grid over (alpha,beta1,beta2) at sigma=1 for violations of the J=>GS implication. Also verify the derived J/GS polynomial conditions directly via Theorem 2.2 and Theorem C.1 on a random sample of parameters in the J region. If any counterexample or divergent output appears, Theorem 3.3's containment claim is unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim that GS OGD's convergence region strictly contains Jacobi's (Theorem 3.3, Table 1) is proved by reducing Schur stability to polynomial inequalities (3.8)/(3.9) and then invoking an unverified quantifier-elimination result: Appendix C.4.5's Reduce[ForAll[...]] returns True without a machine-checkable certificate. The surrounding case analysis (C.4.1-C.4.4) likewise uses Reduce outputs for inequalities C.28, C.29, and C.32. If the implication J=>GS is false for some (alpha,beta1,beta2) or the polynomial translation is unfaithful, the advertised GS-strictly-larger region for OGD fails. Separately, Theorem 4.3's claimed asymptotic r*~1-2/(9 kappa^2) for GS momentum is supported only by a numerical observation in Appendix D.3 ('Numerically, we find...'), not a proof; this does not endanger the containment claim but is a second unproven load-bearing component of the optimal-rate results.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper gives a systematic stability analysis of gradient-type algorithms for bilinear zero-sum games min_x max_y x^T E y. For generalized versions of gradient descent, extra-gradient (EG), optimistic gradient descent (OGD), and heavy-ball momentum, the authors derive characteristic polynomials for both simultaneous (Jacobi) and alternating (Gauss-Seidel) updates, invoke Schur stability conditions to obtain necessary and sufficient convergence conditions, and compare the Jacobi and Gauss-Seidel convergence regions. They also derive optimal linear rates for EG, for special cases of OGD, and for Gauss-Seidel momentum, and support the predictions with experiments on bilinear games and GANs. The advertised central claims are: exact convergence regions for these algorithms (Theorems 3.2-3.4), a Stein-Rosenberg-type containment of the Jacobi region in the Gauss-Seidel region (Theorem 3.3 and Table 1), and improved convergence rates for generalized parameter choices (Theorems 4.1-4.3 and Table 2).","tokens_in":30722,"tokens_out":15738,"duration_ms":147203,"significance":"If the theorems are correct, this is a substantial contribution: it provides the first exact, complete stability characterization for several widely used algorithms on the prototypical bilinear zero-sum game, with explicit characteristic polynomials, necessary and sufficient Schur conditions, and a unified Jacobi/Gauss-Seidel comparison that extends the classical Stein-Rosenberg insight to a non-monotone setting. The paper also ships reproducible experiments and a numerical search method for optimal rates. The main caveats are that one load-bearing containment proof relies on an unverified computer-algebra result and one advertised optimal rate is supported only by numerical observation; these issues are local but must be fixed before the results can be accepted as theorem-level claims.","major_comments":[{"comment":"The central containment claim that the Jacobi OGD convergence region is contained in the Gauss-Seidel region, advertised as 'yes' in Table 1, is discharged by a single quantified Mathematica Reduce call returning True, together with additional Reduce outputs in C.4.1-C.4.4. No independently checkable certificate is supplied, and the paper only notes that the result could in principle be verified manually via cylindrical algebraic decomposition. Since this containment is a load-bearing advertised result, please provide either a full human-readable algebraic proof of the implication from (3.8) to (3.9) or a machine-checkable certificate, and state the exact assumptions, options, and version of the computer algebra system used.","section":"C.4.5 (Theorem 3.3)"},{"comment":"Equation (4.1) cannot be correct as printed. Setting sigma_1 = 1 and letting sigma_n tend to 0 gives r_*^2 -> 1/2 + (1/4) sqrt(2 sqrt(8)) approximately 1.094, which is larger than 1, while the theorem simultaneously asserts r_* ~ 1 - 1/(6 kappa^2), which requires r_*^2 -> 1 from below. The displayed expression is also dimensionally inconsistent for a squared spectral radius. This is a load-bearing error in the claimed optimal Jacobi OGD rate; please re-derive the third case in D.2.1 and correct (4.1) and (D.18).","section":"Theorem 4.2 and Eq. (D.18)"},{"comment":"The claimed optimal rate r_* ~ 1 - 2/(9 kappa^2) for Gauss-Seidel momentum is supported only by the sentence 'Numerically, we find...' after Eq. (D.25). No proof of the asymptotic is given, yet Theorem 4.3 is presented without qualification and the rate appears in Table 2. Please provide an analytic derivation of the asymptotic, or explicitly reclassify this result as a numerical conjecture and state the supporting computation and accuracy.","section":"D.3 (Theorem 4.3)"}],"minor_comments":[{"comment":"After Eq. (D.15), the text says the minimum is achieved at alpha = 2 beta and then says 'From now on, we assume alpha <= 2 beta'. This is confusing; please clarify that the alpha >= 2 beta branch is minimized at its boundary alpha = 2 beta and that the remaining analysis covers the other branch.","section":"D.2.1"},{"comment":"The Reduce outputs labelled 'False.' and 'True.' should state that these are exact symbolic quantifier-elimination results rather than numerical evaluations, and should be accompanied by the Mathematica version and any relevant assumptions on the variables.","section":"C.4"},{"comment":"The optimal EG rate is described as being achieved at alpha -> 0; since alpha = 0 with beta fixed corresponds to a limiting idealized update, please state explicitly whether the rate is attained by any finite admissible parameter configuration or only approached in the limit, and adjust the wording in Table 2 accordingly.","section":"Theorem 4.1"},{"comment":"The notation 'taking alpha_2 -> lambda alpha_2' in the derivation of the Gauss-Seidel polynomials is terse; a short explanation that this is an application of Theorem 2.3 with the lower block-triangular part shifted would improve readability.","section":"Appendix C.1 and Theorem 2.3"}],"recommendation":"major_revision","confidential_remarks":"The paper is worth pursuing after a substantive revision. The main editorial burden is the OGD containment certificate and the correction of the Jacobi OGD rate formula; without those, the headline claims in Table 1 and Table 2 are not fully supported. I found no evidence of circularity in the main derivation: the convergence conditions and rates are derived from characteristic polynomials and parameter optimization, and the experiments are confirmatory rather than fitted. The paper would also benefit from an explicit statement about which claims are proven theorems and which are numerically observed asymptotics."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper is a genuine theory contribution: exact necessary and sufficient linear convergence conditions for generalized extra-gradient, optimistic gradient, and momentum methods on bilinear zero-sum games, under both Jacobi and Gauss-Seidel updates, plus optimal-rate formulas. The key new result is the Stein-Rosenberg-style containment: GS convergence regions contain Jacobi regions for OGD and momentum, and for EG under a stated condition. The derivations from characteristic polynomials to Schur stability are careful, and the experiments are appropriately secondary. This is the kind of work that gives min-max optimization a clean testbed.\n\nThe soft spots are narrow but real. Theorem 3.3's central containment claim for OGD is proved by reducing to polynomial inequalities and then running a Mathematica Reduce call in Appendix C.4.5, with no machine-checkable certificate or independent derivation. The stress-test note is right to flag this; it is not a routine algebra step, since the inclusion J-subset-GS for OGD is one of the advertised headline results. Similarly, Theorem 4.3's asymptotic rate r* ~ 1 - 2/(9 kappa^2) is supported by a numerical observation rather than a proof. Both are likely correct, but as written they are unverified computational support for load-bearing statements. A referee should ask for a certificate, an independent derivation, or a clear reframing of those statements as computational evidence rather than theorem.\n\nThe rest is in better shape. The EG and GD results, the quadratic and cubic Schur derivations, and the optimal EG and OGD rate formulas come from analytic arguments. The citation pattern is fair: the paper builds on prior sufficient conditions and special cases and says so. The experiments do not overclaim; they confirm predicted rates and illustrate behavior.\n\nBottom line: this paper deserves a serious referee. I would send it out, with the request that the two computational support points be tightened. The target audience is people working on min-max optimization and GAN dynamics; they will cite it, and they will get the correct picture from it as long as the CAS-dependent parts are either verified or explicitly flagged.","headline":"Solid theory paper: exact convergence conditions for gradient methods on bilinear games, but two load-bearing steps rest on unverified computer algebra and a numerical asymptotic.","tokens_in":31163,"tokens_out":1848,"would_cite":true,"duration_ms":19084,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91A05","90C47","65F10","65K05"],"pacs":[],"model":"deepseek-v4-flash","headline":"For bilinear zero-sum games, the paper proves exact necessary-and-sufficient conditions for linear convergence of extra-gradient, optimistic gradient descent, and momentum methods, and shows that alternating (Gauss-Seidel) updates…","keywords":["bilinear zero-sum games","extra-gradient method","optimistic gradient descent","momentum method","Gauss-Seidel vs Jacobi updates","Schur stability","linear convergence rates","saddle point"],"falsifier":"Run a rigorous independent check of the OGD inclusion: use exact computer algebra (or a certified interval method) to evaluate the universally quantified implication in Appendix C.4.5, or search for a concrete quadruple (α, β1, β2, σ) that satisfies the Jacobi conditions (3.8) but violates the Gauss-Seidel conditions (3.9). Finding such a parameter point would refute Theorem 3.3's containment; reproducing it with a certificate would confirm the paper's claim.","tokens_in":30317,"feed_emoji":"📉","tokens_out":7352,"duration_ms":58369,"temperature":0.7,"pith_summary":"The paper studies the simplest adversarial setting, bilinear zero-sum games min_x max_y x^T E y, and asks exactly when popular gradient algorithms converge. It proves necessary and sufficient conditions for linear convergence of generalized extra-gradient, optimistic gradient descent, momentum, and plain gradient descent, under both simultaneous (Jacobi) and alternating (Gauss-Seidel) parameter updates; the conditions are polynomial inequalities in the singular values of E and the algorithm's step-size and momentum parameters. The main comparative result is that alternating updates converge on a strictly larger set of parameters than simultaneous updates for OGD and momentum, and for extra-gradient under a stated condition. The paper also computes the optimal linear convergence rate for each algorithm as a function of the condition number of E, showing, for example, that Gauss-Seidel OGD improves the rate exponent from 1/($6κ^{2}$) to 1/$κ^{2}$ compared with Jacobi OGD. A reader should care because these are the first exact stability tests for this problem class, and they extend the classical Stein-Rosenberg theorem — that alternating beats simultaneous iteration — from linear systems to bilinear games.","feed_headline":"Alternating updates win on bilinear zero-sum games","feed_subtitle":"Exact convergence tests for gradient methods show Gauss-Seidel regions strictly contain Jacobi's.","key_machinery":"The load-bearing device is Schur's stability test (Theorem 2.2): a real polynomial has all roots inside the open unit disk — equivalently, the iterates converge linearly — iff a list of determinants constructed from its coefficients are all positive. For quadratic, cubic, and quartic polynomials the paper writes these out as explicit inequalities (Corollary 2.1). The second device is Theorem 2.3, which relates the characteristic polynomial of simultaneous (Jacobi) updates p(λ,1) to that of alternating (Gauss-Seidel) updates p(λ,λ), turning the algorithm comparison into a comparison of two one-variable polynomials. The paper then only needs to check the Schur inequalities for each algorithm.","core_discovery":"The paper's central claim is that for the bilinear zero-sum game min_x max_y x^T E y with invertible E, convergence of generalized gradient-family algorithms is fully governed by Schur stability of a polynomial in one variable derived from the update rule, so the exact convergence region in parameter space is a set of polynomial inequalities in the singular values of E. Specifically, extra-gradient and optimistic gradient descent converge linearly under explicitly stated inequalities (Theorems 3.2 and 3.3), Gauss-Seidel momentum converges exactly when a stated inequality system holds while Jacobi momentum and both variants of plain gradient descent never converge (Theorems 3.1 and 3.4). The paper further shows that for OGD the Gauss-Seidel convergence region strictly contains the Jacobi one, and for EG the containment holds when β1+β2+$α^{2}$ < 2/$σ1^{2}$ (Theorem 3.2). On rates, the paper computes the optimal linear convergence exponents: extra-gradient reaches ($κ^{2}$−1)/($κ^{2}$+1), Gauss-Seidel OGD reaches about 1−1/$κ^{2}$, Jacobi OGD about 1−1/($6κ^{2}$), and Gauss-Seidel momentum about 1−2/($9κ^{2}$) for large condition numbers κ.","pith_inferences":["The same Schur-polynomial machinery should transfer to local convergence analysis of smooth non-bilinear games, where the Jacobian at the saddle point plays the role of E; the paper's conditions would then be local and the GS-vs-Jacobi comparison would carry over near stable equilibria.","The singular-matrix appendix shows the exact conditions extend to rectangular E by projecting onto the range; one testable consequence is that the same convergence regions hold for the effective nonzero singular values.","The finding that momentum requires at least one negative momentum parameter in bilinear games suggests that the success of negative momentum in GAN training is not incidental, and that tuning β1 ≠ β2 asymmetrically could yield rates between the analyzed special cases."],"forward_implications":["For OGD, momentum, and EG (under its stated condition), any parameter choice that makes simultaneous updates converge also makes alternating updates converge — and often faster — so practitioners can safely switch to GS updates.","Since the conditions are exact, they provide a test for whether a given step-size and momentum choice will converge, without running the algorithm.","The optimal-rate results specify parameter settings that achieve the best linear exponent, including cases where the classical choice α = 2β for OGD is suboptimal.","The r-Schur scaling lemma gives a numerical procedure to locate the best linear rate for any of the studied algorithms by binary search on the spectral radius."],"supporting_citations":[{"why":"Supplies the determinant-inequality criterion that turns convergence into Schur stability of a polynomial.","marker":"[Schur, 1917]"},{"why":"The classical theorem that Gauss-Seidel iteration out-converges Jacobi for nonnegative linear systems, which this paper extends to bilinear games.","marker":"[Stein & Rosenberg, 1948]"},{"why":"Fixes the equivalence between spectral radius < 1 and linear convergence of any linear dynamical system.","marker":"[Gohberg et al., 1982]"},{"why":"Introduces the extra-gradient method whose generalized form is analyzed in Theorem 3.2.","marker":"[Korpelevich, 1976]"},{"why":"Introduces optimistic gradient descent, the base algorithm generalized and exactly characterized in Theorem 3.3.","marker":"[Popov, 1980]"},{"why":"Prior linear-convergence guarantee for generalized EG and OGD on bilinear games; the paper sharpens it from sufficient to necessary and sufficient.","marker":"[Liang & Stokes, 2019]"},{"why":"Prior analysis of negative momentum in games; Theorem 3.4 gives complete conditions instead of the special cases treated there.","marker":"[Gidel et al., 2019b]"}],"fun_headline_variants":["Alternating beats simultaneous in zero-sum games","Gauss-Seidel momentum converges, Jacobi never does","Plain gradient descent fails in bilinear zero-sum","Extra-gradient and OGD converge, plain doesn't","Min-max gradient dynamics: full convergence map"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The claim that the OGD Gauss-Seidel convergence region strictly contains the Jacobi region (Theorem 3.3) is finished by a computer-algebra verification of a quantified polynomial implication, without a machine-checkable certificate, so the claim depends on that computation (and the faithful reduction to polynomial conditions) being correct.","fun_headline_variants_meta":{"raw":{"variants":["Alternating beats simultaneous in zero-sum games","Gauss-Seidel momentum converges, Jacobi never does","Plain gradient descent fails in bilinear zero-sum","Extra-gradient and OGD converge, plain doesn't","Min-max gradient dynamics: full convergence map"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001461,"raw_usage":{"total_tokens":5847,"prompt_tokens":885,"completion_tokens":4962,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":501,"completion_tokens_details":{"reasoning_tokens":4890}},"tokens_in":501,"tokens_out":4962,"duration_ms":35498,"temperature":1.0,"reasoning_tokens":4890,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:07:32.993301+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run a rigorous independent check of the OGD inclusion: use exact computer algebra (or a certified interval method) to evaluate the universally quantified implication in Appendix C.4.5, or search for a concrete quadruple (α, β1, β2, σ) that satisfies the Jacobi conditions (3.8) but violates the Gauss-Seidel conditions (3.9). Finding such a parameter point would refute Theorem 3.3's containment; reproducing it with a certificate would confirm the paper's claim.","supporting_citations":[],"review_version":1}