{"id":"b563d1ce-50bf-4d47-9d72-3c18c8c15d3f","arxiv_id":"2509.04426","paper_version":2,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A deterministic algorithm computes an epsilon-approximate Nash equilibrium in zero-sum games using O~(epsilon^{-8/9}) matrix-vector oracle queries, improving the 20-year-old O~(epsilon^{-1}) bound.","lead":"This paper presents deterministic algorithms that compute approximate Nash equilibria of zero-sum games with fewer queries to a matrix-vector oracle than the previous best, improving the exponent from epsilon^{-1} to epsilon^{-8/9}. It also gives similar improvements for related minimax problems like linear classifiers and linear regression.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 4.2's proof overstates the total movement bound: the approximate DAPO error gives ΣV ≤ Γ + εS, not ΣV ≤ Γ, and Lemma 4.3's iteration bound relies on the stronger claim.","rationale":"The central claim is a deterministic ε^{-8/9}-query algorithm for ℓ1-ℓ1 games, with an ε^{-7/9} variant for ℓ2-ℓ1 games. The overall architecture is coherent: truncation, stability of regularized best responses, binary search for α, and smooth-until-guilty subproblem solving are connected in a plausible way. I checked the stability lemma flagged by the reader, Lemma 6.4, and did not find a fatal flaw: the multiplicative closeness follows from Lemmas 6.5 and 6.6 together with the KL-Pinsker bound, and the constants used in the binary search are consistent with that lemma. The most load-bearing insecurity I found is instead in the proximal-point analysis of Section 4. Lemma 4.2's claim that total movement is at most Γ is used critically in Lemma 4.3 to bound the number of kinetic iterations, but it is obtained by dropping the additive εS term coming from the approximate DAPO oracle. Without a bound on S, the displayed proof of Lemma 4.3 is incomplete. The patch using S_{K−1} < Γ/ε appears to preserve the iteration bound up to constants, so I am not claiming the main result is false. Rather, the paper needs a corrected proof of Lemma 4.3 before the result can be considered fully established. I credit the authors for a deterministic construction and a detailed framework, but the false inequality in a keystone lemma justifies conditional rather than unconditional acceptance.","tokens_in":64368,"tokens_out":51653,"duration_ms":440844,"concrete_test":"Repair and verify Lemma 4.3: (i) let S_{K−1} = Σ_{k<K} α_k^{-1} < Γ/ε; (ii) run Lemma 4.2's argument on the first K−1 iterates to obtain Σ_{k<K} V_k ≤ Γ + εS_{K−1} < 2Γ; (iii) redo the Hölder estimate for J'_b ⊆ [K−1] with 2Γ replacing Γ, and check whether the final bound is still K ≤ O((β/ε + ε^{-c/(c+1)})Γ + 2). If the corrected bound depends only on constants, the central ε^{-8/9} and ε^{-7/9} rates survive; if it acquires an extra factor involving the final α_K, the outer-loop iteration bound is unsupported. Also test the worst case of a final tiny α_K in Algorithm 6.2 to confirm that the corrected ΣV bound does not change the kinetic iteration count.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Lemma 4.2 claims that the iterates of Algorithm 4.1 satisfy Σ_{k∈[K]} V^r_{z_{k-1}}(z_k) ≤ Γ. This follows in the exact proximal-point setting, but the DAPO inequality (19) has an additive error ε. Multiplying by α_k^{-1}/S and summing gives regret ≤ (Γ − ΣV)/S + ε, so nonnegativity of regret only implies ΣV ≤ Γ + εS, not ΣV ≤ Γ. The proof of Lemma 4.2 drops the εS term. This matters in Lemma 4.3: the Hölder bound in (21) uses Σ_{k∈J'_b} α_k^c ≤ Σ_{k∈[K]} V_k ≤ Γ. Since S = Σ α_k^{-1} is only guaranteed to be ≥ Γ/ε at termination, and a final small α can make S much larger, εS is not bounded by O(Γ) in general. Thus the displayed proof of the iteration bound K ≤ (β/ε + ε^{-c/(c+1)})Γ + 2 does not follow as written. The gap appears repairable: applying the same argument to the first K−1 iterates, where S_{K−1} < Γ/ε, gives Σ_{k<K} V_k < 2Γ, which is enough for the Hölder step up to a constant factor. But the paper as written contains a false inequality in a keystone lemma of the outer loop.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the matrix-vector query complexity of computing ε-approximate solutions to zero-sum games and related saddle-point problems. Its main results are deterministic algorithms for ℓ1-ℓ1 games (zero-sum games) with O~(ε^{-8/9}) queries (Theorem 1.3), for ℓ2-ℓ1 games with O~(ε^{-7/9}) queries (Theorem 1.4), and for ℓ2-ℓ2 composite games with rates parameterized by Schatten-p norms (Theorem 1.5). The approach combines a smooth-until-proven-guilty mirror prox method, a proximal point outer loop with a dynamic approximate proximal oracle (DAPO), a binary search over regularization levels, and a local-norm approximation of KL divergence on stable regions. The paper provides full proofs and a substantial technical appendix.","tokens_in":64725,"tokens_out":20089,"duration_ms":182892,"significance":"If the advertised bounds hold, the paper gives the first asymptotic improvement over the twenty-year-old O~(ε^{-1}) matrix-vector query bound for zero-sum games, and it improves the analogous bound for ℓ2-ℓ1 games. The ℓ2-ℓ2 composite result also matches known lower bounds while being deterministic. The framework is original and plausibly useful beyond the specific matrix-game instances: it combines proximal point methods, binary search on regularization, and low-rank model updates in a way that is not present in the prior mirror-prox literature. The paper is also commendable for shipping full proofs of the technical lemmas and for setting its parameters analytically rather than fitting them to the target bound. I found no circular reasoning. However, I identified two proof gaps in load-bearing lemmas; both appear repairable with constant-factor or direction corrections, but they must be fixed before the theorems can be considered proven.","major_comments":[{"comment":"Lemma 4.2 claims that the iterates of Algorithm 4.1 satisfy Σ_{k∈[K]} V^r_{z_{k-1}}(z_k) ≤ Γ. The displayed proof does not establish this. From Eq. (20), nonnegativity of regret gives only 0 ≤ (Γ − Σ_k V_k)/S + ε, so Σ_k V_k ≤ Γ + εS; at the final iteration S is not bounded by O(Γ/ε), since the termination condition is checked before the last DAPO call. This matters because Lemma 4.3 uses the stronger claim Σ_{k∈[K]} V_k ≤ Γ in Eq. (21) to bound |J'_b| via Hölder's inequality. As written, the proof of the iteration bound K ≤ (β/ε + ε^{-c/(c+1)})Γ + 2 therefore does not follow. This gap is load-bearing for the outer-loop iteration bound and hence for Theorems 1.3 and 1.4. The issue is repairable: applying the same argument to the first K−1 iterates, where S_{K−1} < Γ/ε, yields Σ_{k<K} V_k ≤ 2Γ, which is enough for Eq. (21) up to a constant factor. The authors should either prove that corrected bound or revise Lemma 4.3 to absorb the extra factor.","section":"Section 4, Lemmas 4.2 and 4.3"},{"comment":"The proof of Lemma 5.6 asserts the lower bound V^r_w(z') + V^r_z(w) ≥ c2(∥z1_x∥²_{z_n^{-1}_x} + ∥z1_y∥²_{z_n^{-1}_y} + ∥z2_x∥²_{z_n^{-1}_x} + ∥z2_y∥²_{z_n^{-1}_y}) with c2 := c1²q_{c1⁴}, while Algorithm 5.1 sets c2 ← q_{c1}. This is inconsistent with Lemma 5.3, whose lower bound has the direction ∥x−x'∥²_{x_n^{-1}}/q_c ≤ KL(x'||x); the natural constant in a lower bound is 1/q_c, not q_c. For example, if w and z' are sufficiently close inside the stable region, the ratio between the KL divergence and the local norm is O(1), not Θ(q_{c1}). As written, the second branch of Lemma 5.6 does not prove that a non-smooth step is certified guilty by the Judge subroutine, and in the ℓ2-ℓ1 case the displayed lower bound also has coefficient 1 on the x-part before being replaced by c2 times the full sum. Because Corollary 5.7 and all of Section 5.2 depend on this step, the proof of the subproblem solver is not currently complete. I believe the high-level result survives if c2 is replaced by the correct reciprocal-type constant, since only absolute constants change, but the present text needs a corrected derivation.","section":"Section 5.1, Lemma 5.6 and Algorithm 5.1"}],"minor_comments":[{"comment":"In the second displayed inequality after Eq. (14), the denominator ∥w_y − z'_x∥_2 should presumably be ∥w_y − z'_y∥_2; as printed, the subscript is inconsistent with the other terms.","section":"Lemma 3.1, proof near Eq. (14)"},{"comment":"The proof says 'for each j∈[J]' the contraction V^r_{z*}(z_j) ≤ (1+α/τ)^{-1}V^r_{z*}(z_{j−1}) holds, but model-update iterations do not increment j and leave the current point unchanged. The contraction chain should be stated for the subsequence of smooth iterations, or the indexing should be adjusted to make this explicit.","section":"Theorem 5.8, proof"},{"comment":"Line 8 of Algorithm 6.2 calls GWF with arguments (…, ε, α_k²/10; Judge), while Definition 6.14 names the two tolerance parameters γ_v and γ_gb. The correspondence ε ↔ γ_v and α_k²/10 ↔ γ_gb should be stated explicitly to avoid ambiguity.","section":"Algorithm 6.2 and Definition 6.14"},{"comment":"The pseudocode defines c2 ← q_{c1} in Line 1, but the proof of Lemma 5.6 defines c2 := c1²q_{c1⁴}. The two definitions should be reconciled after the constant-direction issue in the major comment above is resolved.","section":"Algorithm 5.1 and Lemma 5.6"}],"recommendation":"major_revision","confidential_remarks":"Both issues are proof-level gaps rather than demonstrated counterexamples to the proposed algorithmic architecture. The Lemma 4.2/4.3 gap is a straightforward constant-factor repair, and I expect the Lemma 5.6 constant-direction issue can also be repaired without changing the exponents in the main theorems. Given the potential significance of the claimed results, I recommend asking the authors for corrected proofs of Lemma 4.3 and Lemma 5.6 before acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this is the real thing. It beats the twenty-year-old O~(ε^{-1}) barrier for zero-sum games with a deterministic O~(ε^{-8/9}) algorithm, and it brings a framework that also improves ℓ2-ℓ1 games and gives Schatten-norm dependent rates for ℓ2-ℓ2 composite games. That is worth a serious referee and a place in the literature.\n\nWhat is new: the smooth-until-proven-guilty mirror prox, combined with a kinetic dynamic approximate proximal oracle and a binary search for the right regularization level, is a genuinely new algorithmic idea. The paper explains the intuition well: you take large steps as if the bilinear form were smoother than it is, and when a step exposes a large component of A you peel it off and continue. The full proofs are there, the parameter choices are analytic rather than fitted to the target rate, and the complexity arithmetic checks out in the parts I verified in detail.\n\nThe soft spot is real, but not fatal. The stress-test note is correct: Lemma 4.2 claims the iterates satisfy ΣV ≤ Γ, but the additive ε error in the DAPO only gives ΣV ≤ Γ + εS. Because S is only guaranteed to be at least Γ/ε, the extra εS term is not bounded by Γ. Lemma 4.3's Hölder step then uses the stronger statement. However, the fix is straightforward: apply the same argument to the first K−1 iterates. The termination condition gives S_{K−1} < Γ/ε, so Σ_{k<K}V_k < 2Γ, and Lemma 4.3 only needs the sum over J'_b, which excludes the last iterate. The final rates survive up to a universal constant. This is an overstatement in a keystone lemma, not a hidden collapse.\n\nEverything else I looked at is consistent. The lower-bound discussion is accurate, the self-citation [28] is not load-bearing, and the paper is honest about what is open. I did not machine-check every line of the long proof, but the main structure holds together.\n\nWho is this for: anyone working on oracle complexity for matrix games, minimax optimization, or lower bounds that this result narrows. It deserves peer review; I would recommend acceptance after a minor revision that patches Lemma 4.2 and adjusts the constant in Lemma 4.3. I would also bring it to reading group.","headline":"First real improvement in 20 years for zero-sum game oracle complexity, with a fixable gap in the proximal-point lemma that should not block publication.","tokens_in":65225,"tokens_out":2806,"would_cite":true,"duration_ms":28000,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C47","91A05","68Q25"],"pacs":[],"model":"deepseek-v4-flash","headline":"A deterministic algorithm computes an $\\epsilon$-approximate Nash equilibrium of any zero-sum game with bounded payoff matrix using $\\widetilde{O}(\\epsilon^{-8/9})$ matrix-vector queries, the first improvement over the…","keywords":["zero-sum games","matrix-vector oracle","approximate Nash equilibrium","query complexity","mirror prox","proximal point method","smooth-until-proven-guilty","deterministic algorithms"],"falsifier":"Search over small payoff matrices $A$ with entries in $[-1,1]$, centers in the truncated simplex, and regularization levels $\\alpha$ for a triple satisfying $V_{z_c}(z^*_\\alpha) \\le c \\alpha^2$ with a small constant $c$ while the $\\alpha$-best response differs from $z^*_\\alpha$ by more than $\\exp(2\\sqrt{2c})$ in some coordinate. A brute-force search over discretized truncated simplices and small $m,n$ would either produce such a counterexample to Lemma 6.4 or give strong numerical evidence that the stability claim holds.","tokens_in":64221,"feed_emoji":"⚖️","tokens_out":8620,"duration_ms":78149,"temperature":0.7,"pith_summary":"The paper sets out to break a twenty-year-old query-complexity barrier: computing an $\\epsilon$-approximate Nash equilibrium of a zero-sum game with a matrix-vector oracle, long stuck at $\\widetilde{O}(\\epsilon^{-1})$ queries, can be done deterministically with $\\widetilde{O}(\\epsilon^{-8/9})$ queries. If correct, this is the first improvement over mirror prox and accelerated gradient methods for this basic problem, and it reopens the question of the true oracle complexity between the known $\\widetilde{\\Omega}(\\epsilon^{-2/5})$ lower bound and the old upper bound. The same framework gives $\\widetilde{O}(\\epsilon^{-7/9})$ for $\\ell_2$-$\\ell_1$ games such as linear classification and support vector machines, plus rates for $\\ell_2$-$\\ell_2$ composite games that depend on Schatten-$p$ norms and match known lower bounds in the $p=2$ case. The gain comes from treating the payoff matrix as smooth until a prox step proves otherwise, then projecting the discovered large component out of the oracle model, and wrapping this in a proximal-point outer loop that dynamically sets regularization so each subproblem stays stable.","feed_headline":"Zero-sum games solved in ~epsilon^{-8/9} matrix-vector queries.","feed_subtitle":"First asymptotic improvement in twenty years over mirror prox's one-over-epsilon rate for approximate Nash equilibria.","key_machinery":"The load-bearing mechanism is the kinetic dynamic approximate proximal oracle, or kinetic DAPO, used as the outer loop, together with the smooth-until-proven-guilty mirror prox step inside each subproblem. A DAPO call returns a point and a regularization level satisfying an approximate variational inequality, and it is kinetic when it certifies either a fixed minimum regularization level or a movement lower bound on the Bregman divergence; that movement lower bound turns divergence between consecutive iterates into a fast decay bound through H\\\"older's inequality. Inside each call, the algorithm takes composite mirror prox steps at a deliberately aggressive step size; when the local relative Lipschitzness condition fails, the failure itself exposes a large rank-one component of the payoff matrix, which a judge subroutine folds into an explicit model, reducing a Schatten norm of the remaining matrix and bounding the total number of such model-update steps. The extension to non-Euclidean $\\ell_1$-$\\ell_1$ and $\\ell_2$-$\\ell_1$ geometries relies on a stability lemma: when the regularized subproblem moves by $O(\\alpha^2)$ from its center, the one-step best response is entrywise multiplicatively close to the exact solution, so the subproblem can be restricted to a multiplicative ball, where the KL divergence is comparable to a reweighted Euclidean norm and the inner machinery applies.","core_discovery":"The paper's central claim is Theorem 1.3: for any payoff matrix $A$ with entries in $[-1,1]$, a deterministic algorithm can compute an $\\epsilon$-solution of $\\min_{x\\in\\Delta_n}\\max_{y\\in\\Delta_m} y^\\top A x$ using $\\widetilde{O}(\\epsilon^{-8/9})$ matrix-vector queries, improving the $\\widetilde{O}(\\epsilon^{-1})$ rate of mirror prox and accelerated smooth-softmax minimization. The authors also establish an $\\widetilde{O}(\\epsilon^{-7/9})$ rate for $\\ell_2$-$\\ell_1$ games and, for $\\ell_2$-$\\ell_2$ composite games, a rate $O(\\|A\\|_{S_p}^{p/(1+p)} \\epsilon^{-p/(1+p)})$; for $p=2$ this is $O(\\|A\\|_F^{2/3} \\epsilon^{-2/3})$, matching the known lower bound up to polylogarithmic factors. The proof runs through a general framework for matrix-vector games: smooth-until-proven-guilty mirror prox steps that either make progress on the game or detect and project out a large rank-one component of $A$, combined with a proximal-point outer loop whose dynamic approximate proximal oracle chooses the regularization $\\alpha$ so that the solution moves by $\\Theta(\\alpha^2)$ from the center. The load-bearing stability lemma states that, under such a movement bound, the $\\alpha$-best response is entrywise multiplicatively close to the exact regularized solution, so each subproblem can be confined to a multiplicative ball where the KL divergence behaves like a reweighted Euclidean norm.","pith_inferences":["Editorial extension: the same 'declare smooth until a step proves otherwise, then confiscate the discovered singular direction' pattern should transplant to other oracle models, such as row/column queries or entry queries, where a rank-one update can be folded into an explicit model and may yield sub-$\\epsilon^{-1}$ rates there as well.","Editorial extension: the kinetic DAPO recipe is a primal-dual analogue of existing acceleration frameworks, so the $\\epsilon^{-8/9}$ exponent is probably not the end of the line; improving the inner subproblem solver or choosing a different kinetic trade-off could push the exponent toward the known lower bound of $2/5$.","Editorial extension: the stability framework suggests a testable prediction for practical solvers: entropy-regularized matrix games tuned to the kinetic condition should show a visible oracle-query improvement at moderate accuracy, with the number of calls scaling like $\\epsilon^{-8/9}$ rather than $\\epsilon^{-1}$ on random low-rank payoff matrices."],"forward_implications":["A direct corollary of Theorem 1.3 is that every zero-sum game with bounded payoff matrix admits an $\\epsilon$-Nash equilibrium computable deterministically with $\\widetilde{O}(\\epsilon^{-8/9})$ matrix-vector queries, improving on the twenty-year-old $\\widetilde{O}(\\epsilon^{-1})$ barrier for both deterministic and randomized algorithms.","For linear separability and hard-margin support vector machines, the $\\ell_2$-$\\ell_1$ result gives $\\widetilde{O}(\\epsilon^{-7/9})$ matrix-vector queries, again improving the previous $\\widetilde{O}(\\epsilon^{-1})$ rate.","For $\\ell_2$-$\\ell_2$ composite games such as regularized regression, the $p=2$ case yields a deterministic $O(\\|A\\|_F^{2/3} \\epsilon^{-2/3})$ query bound, matching the known lower bound up to polylogarithmic factors; other $p$ give rates that adapt to the singular-value decay of $A$.","The information-theoretic gap for zero-sum games narrows from a lower-upper range of roughly $[\\widetilde{\\Omega}(\\epsilon^{-2/5}), \\widetilde{O}(\\epsilon^{-1})]$ to roughly $[\\widetilde{\\Omega}(\\epsilon^{-2/5}), \\widetilde{O}(\\epsilon^{-8/9})]$, making the exact optimal exponent a concrete open problem."],"supporting_citations":[{"why":"Supplies the mirror prox method and the $\\widetilde{O}(\\epsilon^{-1})$ baseline that the paper improves.","marker":"[39]"},{"why":"Supplies the accelerated smooth-softmax $\\widetilde{O}(\\epsilon^{-1})$ approach and frames zero-sum games as the motivating example.","marker":"[41]"},{"why":"Supplies the $\\widetilde{\\Omega}(\\epsilon^{-2/5})$ deterministic lower bound and the $\\widetilde{\\Omega}(\\epsilon^{-2/3})$ bound for $\\ell_2$-$\\ell_1$ games that set the target for improvement.","marker":"[30]"},{"why":"Supplies the local relative Lipschitzness condition that lets mirror prox progress when an aggressive step size is justified.","marker":"[18]"},{"why":"Supplies the distance-generating-function setups and proximal-mapping formalism used for all three game geometries.","marker":"[10]"},{"why":"Supplies the Schatten-norm Pythagorean identity used by the judge to project off discovered large rank-one components.","marker":"[4]"},{"why":"Supplies truncated-simplex approximation and stability tools used in the $\\ell_1$-$\\ell_1$ and $\\ell_2$-$\\ell_1$ reductions.","marker":"[16]"}],"fun_headline_variants":["Zero-sum games need only ~epsilon^-8/9 matrix-vector queries","First zero-sum game solver improvement in 20 years: eps^-8/9","Zero-sum games: query complexity dropped to eps^-8/9","Fewer matrix-vector products for zero-sum equilibria: eps^-8/9","Zero-sum games: from eps^-1 to eps^-8/9 matrix-vector calls"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole rate hangs on the stability claim in Lemma 6.4: if the regularized subproblem moves only a tiny, controlled amount from its center, namely a Bregman divergence of order the square of the regularization level, then the one-step best response is already entrywise close to the exact regularized solution. If a bounded payoff matrix breaks that closeness, the subproblem cannot be solved inside a small multiplicative ball, and the query count falls back to the old $\\epsilon^{-1}$ rate.","fun_headline_variants_meta":{"raw":{"variants":["Zero-sum games need only ~epsilon^-8/9 matrix-vector queries","First zero-sum game solver improvement in 20 years: eps^-8/9","Zero-sum games: query complexity dropped to eps^-8/9","Fewer matrix-vector products for zero-sum equilibria: eps^-8/9","Zero-sum games: from eps^-1 to eps^-8/9 matrix-vector calls"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000308,"raw_usage":{"total_tokens":1824,"prompt_tokens":1070,"completion_tokens":754,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":686,"completion_tokens_details":{"reasoning_tokens":649}},"tokens_in":686,"tokens_out":754,"duration_ms":6454,"temperature":1.0,"reasoning_tokens":649,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T16:28:51.850227+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Search over small payoff matrices $A$ with entries in $[-1,1]$, centers in the truncated simplex, and regularization levels $\\alpha$ for a triple satisfying $V_{z_c}(z^*_\\alpha) \\le c \\alpha^2$ with a small constant $c$ while the $\\alpha$-best response differs from $z^*_\\alpha$ by more than $\\exp(2\\sqrt{2c})$ in some coordinate. A brute-force search over discretized truncated simplices and small $m,n$ would either produce such a counterexample to Lemma 6.4 or give strong numerical evidence that the stability claim holds.","supporting_citations":[{"cited_title":"Smooth minimization of non-smooth functions","cited_arxiv_id":null,"evidence_quote":"Supplies the accelerated smooth-softmax $\\widetilde{O}(\\epsilon^{-1})$ approach and frames zero-sum games as the motivating example."},{"cited_title":"The oracle complexity of simplex-based matrix games: Linear separability and nash equilibria","cited_arxiv_id":null,"evidence_quote":"Supplies the $\\widetilde{\\Omega}(\\epsilon^{-2/5})$ deterministic lower bound and the $\\widetilde{\\Omega}(\\epsilon^{-2/3})$ bound for $\\ell_2$-$\\ell_1$ games that set the target for improvement."},{"cited_title":"Relative lipschitzness in extragradient methods and a direct recipe for acceleration","cited_arxiv_id":null,"evidence_quote":"Supplies the local relative Lipschitzness condition that lets mirror prox progress when an aggressive step size is justified."},{"cited_title":"Variance reduction for matrix games","cited_arxiv_id":null,"evidence_quote":"Supplies the distance-generating-function setups and proximal-mapping formalism used for all three game geometries."},{"cited_title":"Low-rank approximation with matrix- vector products","cited_arxiv_id":null,"evidence_quote":"Supplies the Schatten-norm Pythagorean identity used by the judge to project off discovered large rank-one components."},{"cited_title":"A whole new ball game: A primal accelerated method for matrix games and minimizing the maximum of smooth functions","cited_arxiv_id":null,"evidence_quote":"Supplies truncated-simplex approximation and stability tools used in the $\\ell_1$-$\\ell_1$ and $\\ell_2$-$\\ell_1$ reductions."}],"review_version":2}