{"id":"37c615a5-f158-4c3c-9235-864861239d46","arxiv_id":"2607.09950","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":1,"one_line_summary":"Implicit midpoint gradient descent preserves distance to every Nash equilibrium and achieves O(1/(ηT)+1/T) time-average convergence in unconstrained bilinear zero-sum games for any η>0.","lead":"The paper introduces Implicit Midpoint Gradient Descent (IMGD), a symplectic discretization of continuous-time gradient dynamics for unconstrained bilinear zero-sum games. It yields bounded orbits and O(1/T) ergodic convergence to Nash equilibria for every positive learning rate, outperforming optimistic and alternating gradient descent in experiments.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The strongest claim rests on elementary linear algebra that is fully spelled out: G skew-symmetric implies Φ_η is orthogonal, hence Euclidean distance to any fixed point of the affine map is invariant for every η > 0. The subsequent ergodic bound follows by a one-line telescoping sum and the same invariance. Both steps are short, self-contained, and free of analytic estimates that could hide regularity assumptions. The existence hypothesis is an explicit premise, not a silent gap; when it fails the claims are simply inapplicable, which the paper already flags. Experiments correctly amortize the inverse and still show clear gains over AGD/OGD. Consequently the reader's ACCEPT verdict stands; no adjustment is warranted.","tokens_in":20032,"tokens_out":457,"duration_ms":6897,"concrete_test":"Independently recompute Φ_η = (I − (η/2)G)^{-1}(I + (η/2)G) for a random skew-symmetric G of size 40 and verify ||Φ_η^⊤ Φ_η − I||_F < 1e-12 for η ∈ {0.1,1,10,1e5}; if the identity fails for any tested η the orbit-preservation claim collapses.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The reader's weakest_assumption (existence of a Nash equilibrium) is correctly noted but is not load-bearing against the paper's central claim. Theorems 1–2 and Proposition 3 are conditioned on existence; when the set is empty the distance-preservation statement is simply vacuous rather than false. The algebraic core—orthogonality of Φ_η arising from G^⊤ = −G (Theorem 1 proof), the telescoping residual bound (Theorem 2), and the fixed-point equivalence (Proposition 3)—holds unconditionally once a solution of Gx + c = 0 is assumed. The two sufficient conditions in Proposition 1 cover the generic cases used in the literature and experiments. No hidden gap appears in the skew-symmetry argument, the Schur decomposition reduction, or the experimental accounting of the O(k^{3}) inverse.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The paper studies unconstrained bilinear zero-sum games and proposes Implicit Midpoint Gradient Descent (IMGD), obtained by applying the implicit midpoint (symplectic) integrator to continuous-time gradient/FTRL dynamics. The central claims are that the resulting map preserves Euclidean distance to every Nash equilibrium for every learning rate η>0 (Theorem 1), therefore has bounded orbits, that its time averages satisfy an O(1/(ηT)+1/T) residual bound (Theorem 2), and that a two-step average residual is O(1/η) (Theorem 4). Fixed points coincide with Nash equilibria (Proposition 3). The dynamics decompose via real Schur form into independent planar rotations (Theorems 5–7). Numerical comparisons against AGD and OGD on random 20×20 bilinear instances report smaller residuals under both fixed-iteration and fixed-time budgets, with the O(k^{3}) inverse cost included in wall-clock accounting.","tokens_in":20190,"tokens_out":764,"duration_ms":9242,"significance":"If the claims hold, IMGD is the first standard online first-order method that simultaneously delivers exact orbit preservation, learning-rate-independent stability, and fast ergodic rates in unconstrained bilinear zero-sum games. The algebraic core is short and self-contained: orthogonality of Φ_η follows from skew-symmetry of G, the residual bound is a telescoping identity, and the large-η two-step rate follows from planar rotations under the real Schur decomposition. Experiments report 95% confidence intervals over 30 seeds and correctly amortize the inverse. These are concrete, checkable contributions that strengthen the geometric-integrator viewpoint on game dynamics and give a clean baseline for later constrained or normal-form extensions.","major_comments":[],"minor_comments":[{"comment":"Proposition 1 gives only two sufficient conditions for existence of a Nash equilibrium. A short remark that the main theorems are conditioned on existence (and are vacuous when the set is empty) would make the scope fully explicit without changing any claim.","section":null},{"comment":"Section 6.2 sketches a hybrid support-identification + IMGD pipeline for normal-form games but leaves open when recomputation of the reduced inverse remains practical. A sentence quantifying the expected frequency of support changes, or a pointer to existing support-identification heuristics, would help readers assess implementability.","section":null},{"comment":"Figures 3–6 are described as “smoothed” by taking running maxima; the precise smoothing rule should be stated in the captions so that residual curves are reproducible from the text alone.","section":null},{"comment":"Table 1 lists representative guarantees for several methods; a footnote clarifying that the listed step-size bounds are the common literature choices (not necessarily the sharpest known) would avoid over-reading the comparison.","section":null},{"comment":"Minor notation: the stacked gradient field is written both as Gx+c and as the pair of player gradients; a single consistent symbol for the residual Gx+c throughout Theorems 2 and 4 would improve readability.","section":null}],"recommendation":"accept","confidential_remarks":"The algebraic arguments are short and appear correct on a careful reading; the existence assumption is standard and correctly conditioned. I see no load-bearing gap that would justify major revision. The paper is a clean, self-contained contribution suitable for a theory-oriented CS/OR venue."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"The real news is Theorem 1: the midpoint map Φ_η is orthogonal because G is skew-symmetric, so Euclidean distance to every Nash is exactly conserved for every η > 0. That immediately gives bounded orbits with no step-size restriction, plus the O(1/(ηT) + 1/T) ergodic residual (Theorem 2) and the two-step O(1/η) residual via the Schur 2-D rotations. Those three properties together are new relative to AGD (approximate energy) and OGD (step-size caps). The algebra is short and checks out; the fixed-point equivalence is clean.\n\nWhat they do well: they treat the unconstrained bilinear model as the local testbed it actually is, derive the update three ways (midpoint, stacked, two half-steps + shrinkage), and put the O(k^{3}) inverse cost into the wall-clock budgets. Experiments are modest (k=40, 30 seeds, 95 % CIs) but properly controlled and show clear gaps versus AGD/OGD. The discussion of hybrid support-identification for normal-form games is honest about the practical bottleneck.\n\nSoft spots are real but proportional. Existence of a Nash is assumed for the main theorems; they only give two sufficient conditions. When the set is empty the claims are vacuous, not false, and that matches standard practice in this literature. Scope is deliberately unconstrained bilinear; no last-iterate, no nonlinear payoffs, no public code. The large-η two-step claim is neat but mainly of theoretical interest once you already pay for the inverse. None of that undercuts the stated results.\n\nThis is for people who care about geometric integrators and learning dynamics in games. A serious referee should see it; the core math is tight enough that revision, not rejection, is the right path. I would cite the distance-preservation argument and the comparison table.","headline":"Clean symplectic discretization of bilinear game dynamics that actually preserves distance for every step size; solid methods paper, limited scope.","tokens_in":20828,"tokens_out":481,"would_cite":true,"duration_ms":4989,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.5","headline":"A midpoint rule for zero-sum games keeps every orbit the same distance from every Nash equilibrium for any step size and drives time averages to equilibrium at rate O(1/T).","keywords":["zero-sum games","implicit midpoint gradient descent","Hamiltonian dynamics","symplectic integrators","bounded orbits","ergodic convergence","learning-rate free","bilinear saddle-point problems"],"falsifier":"Run IMGD on a concrete bilinear instance that admits a known Nash point and check whether the Euclidean distance from successive iterates to that point remains constant (to machine precision) for several large learning rates; any systematic growth falsifies the central theorem.","tokens_in":20912,"feed_emoji":"⚖️","tokens_out":644,"duration_ms":6070,"temperature":0.7,"pith_summary":"Unconstrained bilinear zero-sum games are the basic model for how two opposing agents update strategies by gradient methods. Continuous-time follow-the-regularized-leader dynamics stay on perfect energy shells around Nash equilibria, but ordinary discrete updates either inflate that energy and diverge or demand carefully small step sizes. This paper derives Implicit Midpoint Gradient Descent by applying the classical implicit-midpoint symplectic integrator to those continuous dynamics. The resulting discrete map is orthogonal, so the Euclidean distance from every iterate to every Nash point is exactly conserved for every learning rate; orbits therefore remain bounded with no upper restriction on step size. Time averages of the iterates converge to the Nash residual at rate O(1/ηT + 1/T), and a single two-step average already yields residual O(1/η). Numerical comparisons on random bilinear instances show the method reaches substantially smaller residuals than optimistic and alternating gradient descent under both fixed-iteration and fixed-time budgets.","feed_headline":"Midpoint rule keeps game orbits fixed distance from every Nash","feed_subtitle":"Any step size works; time averages reach residual O(1/T) and beat optimistic and alternating gradient descent","key_machinery":"The orthogonal map Φ_η = (I − (η/2)G)^(−1)(I + (η/2)G), where G is the skew-symmetric bilinear payoff operator; distance preservation follows at once from Φ_η^⊤ Φ_η = I, and the same identity supplies the telescoping sum that proves the ergodic rate.","core_discovery":"Implicit Midpoint Gradient Descent, obtained by the implicit-midpoint integrator of continuous gradient dynamics, exactly preserves Euclidean distance to every Nash equilibrium for every learning rate η > 0, produces bounded orbits, and yields O(1/ηT + 1/T) ergodic convergence to the set of Nash equilibria—the first traditional online method to obtain all three properties simultaneously in unconstrained bilinear zero-sum games.","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["Implicit midpoint GD keeps fixed distance to every Nash for any η","Midpoint rule yields rate-free bounded orbits and O(1/T) Nash averages","Symplectic midpoint inherits continuous FTRL: distance to Nash fixed forever","First traditional online method with all three: bound, speed, rate-free stability","Implicit midpoint beats optimistic and alternating GD on bilinear zero-sum"],"cache_read_input_tokens":16512,"weakest_assumption_plain":"The game must possess at least one Nash equilibrium; without it the distance-preservation statement becomes empty.","fun_headline_variants_meta":{"raw":{"variants":["Implicit midpoint GD keeps fixed distance to every Nash for any η","Midpoint rule yields rate-free bounded orbits and O(1/T) Nash averages","Symplectic midpoint inherits continuous FTRL: distance to Nash fixed forever","First traditional online method with all three: bound, speed, rate-free stability","Implicit midpoint beats optimistic and alternating GD on bilinear zero-sum"]},"model":"grok-4.5","effort":"low","cost_usd":0.004502,"raw_usage":{"total_tokens":1231,"prompt_tokens":673,"num_sources_used":0,"completion_tokens":99,"cost_in_usd_ticks":45020000,"prompt_tokens_details":{"text_tokens":673,"audio_tokens":0,"image_tokens":0,"cached_tokens":128},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":459,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":673,"tokens_out":99,"duration_ms":4331,"temperature":1.0,"reasoning_tokens":459,"cache_read_input_tokens":128,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-14T14:21:30.430348+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Run IMGD on a concrete bilinear instance that admits a known Nash point and check whether the Euclidean distance from successive iterates to that point remains constant (to machine precision) for several large learning rates; any systematic growth falsifies the central theorem.","supporting_citations":[],"review_version":1}