Pith. sign in

REVIEW 2 major objections 4 minor 52 references

Solving Zero-Sum Games with Fewer Matrix-Vector Products

T0 review · 2 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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…

desk verdict 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. read the letter →

arxiv 2509.04426 v2 pith:NEFY5VRK submitted 2025-09-04 math.OC cs.DScs.GT

Ishani Karmarkar , Liam O'Carroll , Aaron Sidford This is my paper · ORCID
classification math.OCcs.DScs.GT MSC 90C4791A0568Q25
keywords zero-sumgamesmatrix-vectororacleapproximateNashequilibriumquerycomplexitymirrorproxproximalpointmethodsmooth-until-proven-guiltydeterministicalgorithms
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

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.

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 (2)
  1. [Section 4, Lemmas 4.2 and 4.3] 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.
  2. [Section 5.1, Lemma 5.6 and Algorithm 5.1] 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.
minor comments (4)
  1. [Lemma 3.1, proof near Eq. (14)] 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.
  2. [Theorem 5.8, proof] 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.
  3. [Algorithm 6.2 and Definition 6.14] 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.
  4. [Algorithm 5.1 and Lemma 5.6] 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.

Circularity Check

0 steps flagged · score 1.0 of 10

No circularity: the epsilon-dependence is derived from new proximal-point/DAPO analysis; overlapping-author citations are contextual, not load-bearing.

full rationale

The claimed query counts are not baked into the definitions. The only free parameters (regularization floor beta and smoothness threshold tau) are set analytically after the bounds are derived: beta <- epsilon^{1/3} and tau <- epsilon^{1/3} (Theorem 6.20) or tau <- epsilon^{2/9} (Theorem 1.4). The DAPO oracle (Definition 4.1) is a definition, but Lemma 4.3 derives the iteration bound from it via Holder's inequality rather than assuming the target rate. External benchmarks (Nemirovski 2004, Nesterov 2005, Kornowski-Shamir 2025) are used as comparisons, not as inputs. The overlapping-author citations are not load-bearing for the main theorem: [28] is cited only to note prior randomized work for the special p=2 rate, and [16] supplies auxiliary truncation and KL-divergence facts rather than the central reduction. No parameter is fitted to the final epsilon-dependence and then called a prediction, and no uniqueness theorem or ansatz is imported from the authors' prior work. I therefore find no circular step. One caveat, noted for completeness: the proof of Lemma 4.2 appears to claim sum V <= Gamma from an inequality that also contains an additive epsilon in equations (19)/(20); the same argument only yields sum V <= Gamma + epsilon S as written. This is a correctness gap that may affect Lemma 4.3, but it is not a case of the derivation reducing to its own inputs.

Assumptions & free parameters 3 free parameters · 2 assumptions · 0 invented entities

The central claim rests on standard convex analysis and linear algebra, plus the explicit boundedness assumptions on the payoff matrix. No exogenous parameters are fitted to data; all algorithm parameters are set analytically. No new entities are introduced.

free parameters (3)
  • smoothness threshold tau = Xi^{p/(p+1)} epsilon^{1/(3(p+1))} for Theorem 6.20; epsilon^{2/9} for Theorem 1.4
    Used in smooth-until-proven-guilty mirror prox to determine when a step is 'guilty'. It is chosen analytically to balance progress iterations and model-update iterations, not fitted to data.
  • minimum regularization level beta = epsilon^{1/3}
    Used as the minimum alpha in the kinetic DAPO oracle. It is set by optimizing the final query bound in Theorem 6.20 and Lemma 6.32.
  • truncation parameter nu = min(epsilon,1)/(8 max(m,n))
    From Lemma 6.2, nu is set to an inverse polynomial in m,n,1/epsilon to justify solving the truncated simplex and to ensure polylogarithmic factors are controlled.
assumptions (2)
  • standard math Standard properties of Bregman divergences and strongly convex distance-generating functions
    Used throughout the paper for mirror prox and proximal point arguments, for example in Definition 1.6 and Lemma 2.3.
  • domain assumption Bounded matrix assumptions: ||A||_max <= 1 for ell1-ell1 games and ||A||_{2->infinity} <= 1 for ell2-ell1 games
    These are part of the problem setup (Definition 2.1) and are used to bound Lipschitz constants and oracle query costs. They are not derived in the paper and are taken as given.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Solving Zero-Sum Games with Fewer Matrix-Vector Products." pith.science (2026). https://pith.science/paper/NEFY5VRK

@misc{pith2026250904426,
  author       = {Pith},
  title        = {Pith review of: Solving Zero-Sum Games with Fewer Matrix-Vector Products},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NEFY5VRK}},
  note         = {Machine review of arXiv:2509.04426}
}
abstract

In this paper we consider the problem of computing an $\epsilon$-approximate Nash Equilibrium of a zero-sum game in a payoff matrix $A \in \mathbb{R}^{m \times n}$ with $O(1)$-bounded entries given access to a matrix-vector product oracle for $A$ and its transpose $A^\top$. We provide a deterministic algorithm that solves the problem using $\tilde{O}(\epsilon^{-8/9})$-oracle queries, where $\tilde{O}(\cdot)$ hides factors polylogarithmic in $m$, $n$, and $\epsilon^{-1}$. Our result improves upon the state-of-the-art query complexity of $\tilde{O}(\epsilon^{-1})$ established by [Nemirovski, 2004] and [Nesterov, 2005]. We obtain this result through a general framework that yields improved deterministic query complexities for solving a broader class of minimax optimization problems which includes computing a linear classifier (hard-margin support vector machine) as well as linear regression.

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

52 extracted references · 46 canonical work pages

  1. [28]

    Reusing samples in variance reduction

    Yujia Jin, Ishani Karmarkar, Aaron Sidford, and Jiayi Wang. Reusing samples in variance reduction. In https://arxiv.org/abs/2509.02526, 2025

    arXiv 2025

  2. [1]

    Optimal methods for higher- order smooth monotone variational inequalities

    Deeksha Adil, Brian Bullins, Arun Jambulapati, and Sushant Sachdeva. Optimal methods for higher- order smooth monotone variational inequalities. In arXiv preprint arXiv:2205.06167, 2022

    arXiv 2022

  3. [2]

    Stochastic bias-reduced gradi- ent methods

    Hilal Asi, Yair Carmon, Arun Jambulapati, Yujia Jin, and Aaron Sidford. Stochastic bias-reduced gradi- ent methods. In Proceedings of the 35th International Conference on Neural Information Processing Systems, NIPS ’21, Red Hook, NY , USA, 2021. Curran Associates Inc

    work page 2021

  4. [3]

    Bailey and Georgios Piliouras

    James P. Bailey and Georgios Piliouras. Multiplicative weights update in zero-sum games. In 19th ACM Conference on Economics and Computation (EC), 2018

    work page 2018

  5. [4]

    Low-rank approximation with matrix- vector products

    Ainesh Bakshi, Kenneth L Clarkson, and David P Woodruff. Low-rank approximation with matrix- vector products. In 54th Annual ACM Symposium on Theory of Computing (STOC), 2022

    work page 2022

  6. [5]

    The gradient complexity of linear regression

    Mark Braverman, Elad Hazan, Max Simchowitz, and Blake Woodworth. The gradient complexity of linear regression. In 33rd Annual Conference on Computational Learning Theory (COLT), 2020

    work page 2020

  7. [6]

    Complexity of highly parallel non-smooth convex optimization

    S´ebastien Bubeck, Qijia Jiang, Yin Tat Lee, Yuanzhi Li, and Aaron Sidford. Complexity of highly parallel non-smooth convex optimization. Curran Associates Inc., Red Hook, NY , USA, 2019

    work page 2019

  8. [7]

    Near-optimal method for highly smooth convex optimization

    S´ebastien Bubeck, Qijia Jiang, Yin Tat Lee, Yuanzhi Li, and Aaron Sidford. Near-optimal method for highly smooth convex optimization. In Alina Beygelzimer and Daniel Hsu, editors, Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 492–507. PMLR, 25–28 Jun 2019

    work page 2019

Show all 52 references
  1. [8]

    Distributionally robust optimization via ball oracle acceleration

    Yair Carmon and Danielle Hausler. Distributionally robust optimization via ball oracle acceleration. In arXiv preprint arXiv:2203.13225, 2022

    2022 arXiv

  2. [9]

    Convex until proven guilty: dimension- free acceleration of gradient descent on non-convex functions

    Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Convex until proven guilty: dimension- free acceleration of gradient descent on non-convex functions. In 34th International Conference on Machine Learning (ICML), 2017

    2017

  3. [10]

    Variance reduction for matrix games

    Yair Carmon, Yujia Jin, Aaron Sidford, and Kevin Tian. Variance reduction for matrix games. In Advances in Neural Information Processing Systems 32 (NeurIPS), 2019

    2019

  4. [11]

    Acceleration with a ball optimization oracle

    Yair Carmon, Arun Jambulapati, Qijia Jiang, Yujia Jin, Yin Tat Lee, Aaron Sidford, and Kevin Tian. Acceleration with a ball optimization oracle. In Advances in Neural Information Processing Systems 33 (NeurIPS), 2020

    2020

  5. [12]

    Coordinate methods for matrix games

    Yair Carmon, Yujia Jin, Aaron Sidford, and Kevin Tian. Coordinate methods for matrix games. In 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2020

    2020

  6. [13]

    Thinking inside the ball: Near-optimal minimization of the maximal loss

    Yair Carmon, Arun Jambulapati, Yujia Jin, and Aaron Sidford. Thinking inside the ball: Near-optimal minimization of the maximal loss. In 34th Annual Conference on Computational Learning Theory (COLT), 2021

    2021

  7. [14]

    Optimal and adap- tive monteiro-svaiter acceleration

    Yair Carmon, Danielle Hausler, Arun Jambulapati, Yujia Jin, and Aaron Sidford. Optimal and adap- tive monteiro-svaiter acceleration. In Proceedings of the 36th International Conference on Neural Information Processing Systems, NIPS ’22, Red Hook, NY , USA, 2022. Curran Associates Inc

    2022

  8. [15]

    Resqueing parallel and private stochastic convex optimization

    Yair Carmon, Arun Jambulapati, Yujia Jin, Yin Tat Lee, Daogao Liu, Aaron Sidford, and Kevin Tian. Resqueing parallel and private stochastic convex optimization. In 64th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 2031–2058. IEEE, 2023. 49

    2023

  9. [16]

    A whole new ball game: A primal accelerated method for matrix games and minimizing the maximum of smooth functions

    Yair Carmon, Arun Jambulapati, Yujia Jin, and Aaron Sidford. A whole new ball game: A primal accelerated method for matrix games and minimizing the maximum of smooth functions. In 35th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2024

    2024

  10. [17]

    Sublinear optimization for machine learning

    Kenneth L Clarkson, Elad Hazan, and David P Woodruff. Sublinear optimization for machine learning. In Journal of the ACM (JACM), 2012

    2012

  11. [18]

    Relative lipschitzness in extragradient methods and a direct recipe for acceleration

    Michael B Cohen, Aaron Sidford, and Kevin Tian. Relative lipschitzness in extragradient methods and a direct recipe for acceleration. In 11th Conference on Innovations in Theoretical Computer Science (ITCS), 2020

    2020

  12. [19]

    Near-optimal no-regret algorithms for zero-sum games

    Constantinos Daskalakis, Alan Deckelbaum, and Anthony Kim. Near-optimal no-regret algorithms for zero-sum games. In 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2011

    2011

  13. [20]

    Composite objective mirror descent

    John C Duchi, Shai Shalev-Shwartz, Yoram Singer, and Ambuj Tewari. Composite objective mirror descent. In 23rd Annual Conference on Computational Learning Theory (COLT), 2010

    2010

  14. [21]

    Adaptive game playing using multiplicative weights

    Yoav Freund and Robert E Schapire. Adaptive game playing using multiplicative weights. In Games and Economic Behavior, 1999

    1999

  15. [22]

    Generative adversarial nets

    Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in Neural Information Processing Systems 27 (NeurIPS), 2014

    2014

  16. [23]

    A sublinear-time randomized approximation algorithm for matrix games

    Michael D Grigoriadis and Leonid G Khachiyan. A sublinear-time randomized approximation algorithm for matrix games. In Operations Research Letters, 1995

    1995

  17. [24]

    On lower complexity bounds for large-scale smooth convex optimization

    Crist´obal Guzm´an and Arkadi Nemirovski. On lower complexity bounds for large-scale smooth convex optimization. In Journal of Complexity, 2015

    2015

  18. [25]

    Towards characterizing the first-order query complexity of learning (approximate) nash equilibria in zero-sum matrix games

    H´edi Hadiji, Sarah Sachs, Tim van Erven, and Wouter M Koolen. Towards characterizing the first-order query complexity of learning (approximate) nash equilibria in zero-sum matrix games. In Advances in Neural Information Processing Systems 37 (NeurIPS), 2024

    2024

  19. [26]

    Mirror prox algorithm for multi-term composite minimization and semi-separable problems

    Niao He, Anatoli Juditsky, and Arkadi Nemirovski. Mirror prox algorithm for multi-term composite minimization and semi-separable problems. In Computational Optimization and Applications, 2015

    2015

  20. [27]

    Closing the computational-query depth gap in parallel stochastic convex optimization

    Arun Jambulapati, Aaron Sidford, and Kevin Tian. Closing the computational-query depth gap in parallel stochastic convex optimization. In Annual Conference Computational Learning Theory, 2024

    2024

  21. [29]

    Stich, and Martin Jaggi

    Sai Praneeth Karimireddy, Sebastian U. Stich, and Martin Jaggi. Global linear convergence of newton’s method without strong-convexity or lipschitz gradients. In arXiv preprint arXiv:1806.00413, 2018

    2018 arXiv

  22. [30]

    The oracle complexity of simplex-based matrix games: Linear separability and nash equilibria

    Guy Kornowski and Ohad Shamir. The oracle complexity of simplex-based matrix games: Linear separability and nash equilibria. In 38th Annual Conference on Computational Learning Theory (COLT), 2025

    2025

  23. [31]

    Tianyi Lin and Michael I. Jordan. Perseus: a simple and optimal high-order method for variational inequalities. Mathematical Programming, 209(1):609–650, Jan 2025. 50

    2025

  24. [32]

    The weighted majority algorithm

    Nick Littlestone and Manfred K Warmuth. The weighted majority algorithm. In Information and computation, 1994

    1994

  25. [33]

    Accelerated gradient algorithms with adaptive subspace search for instance-faster optimization

    Yuanshi Liu, Hanzhen Zhao, Yang Xu, Pengyun Yue, and Cong Fang. Accelerated gradient algorithms with adaptive subspace search for instance-faster optimization. In arXiv preprint arXiv:2312.03218, 2023

    2023 arXiv

  26. [34]

    Towards deep learning models resistant to adversarial attacks

    Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In 5th International Conference on Learning Representations (ICLR), 2017

    2017

  27. [35]

    A study of local approximations in information theory

    Anuran Makur. A study of local approximations in information theory. Master’s thesis, Massachusetts Institute of Technology, Cambridge, MA, June 2015. Submitted to the Department of Electrical Engineering and Computer Science

    2015

  28. [36]

    A logical calculus of the ideas immanent in nervous activity

    Warren S McCulloch and Walter Pitts. A logical calculus of the ideas immanent in nervous activity. In The bulletin of mathematical biophysics, 1943

    1943

  29. [37]

    Renato D. C. Monteiro and B. F. Svaiter. An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods. SIAM Journal on Optimization, 23 (2):1092–1125, 2013

    2013

  30. [38]

    Randomized block krylov methods for stronger and faster approximate singular value decomposition

    Cameron Musco and Christopher Musco. Randomized block krylov methods for stronger and faster approximate singular value decomposition. In Advances in Neural Information Processing Systems 28 (NeurIPS), volume 28, 2015

    2015

  31. [39]

    Prox-method with rate of convergence o(1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems

    Arkadi Nemirovski. Prox-method with rate of convergence o(1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1):229–251, 2004

    2004

  32. [40]

    Problem complexity and method efficiency in optimization

    Arkadij Semenovi ˇc Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. In Wiley-Interscience, 1983

    1983

  33. [41]

    Smooth minimization of non-smooth functions

    Yu Nesterov. Smooth minimization of non-smooth functions. In Mathematical programming, 2005

    2005

  34. [42]

    Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems

    Yuyuan Ouyang and Yangyang Xu. Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems. Mathematical Programming, 185(1):1–35, Jan 2021

    2021

  35. [43]

    Stochastic variance reduction methods for saddle-point problems

    Balamurugan Palaniappan and Francis Bach. Stochastic variance reduction methods for saddle-point problems. In Advances in Neural Information Processing Systems 29 (NeurIPS), 2016

    2016

  36. [44]

    Optimization, learning, and games with predictable sequences

    Sasha Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable sequences. Advances in Neural Information Processing Systems, 26, 2013

    2013

  37. [45]

    Estimation of high-dimensional low-rank matrices

    Angelika Rohde and Alexandre B Tsybakov. Estimation of high-dimensional low-rank matrices. In arxiv, 2011

    2011

  38. [46]

    The perceptron: a probabilistic model for information storage and organization in the brain

    Frank Rosenblatt. The perceptron: a probabilistic model for information storage and organization in the brain. In Psychological review, 1958

    1958

  39. [47]

    Online learning and online convex optimization

    Shai Shalev-Shwartz. Online learning and online convex optimization. Found. Trends Mach. Learn., 4 (2):107–194, February 2012. ISSN 1935-8237. 51

    2012

  40. [48]

    A smooth perceptron algorithm

    Negar Soheili and Javier Pen˜na. A smooth perceptron algorithm. SIAM Journal on Optimization, 22(2): 728–737, 2012

    2012

  41. [49]

    A note on preconditioning by low-stretch spanning trees

    Daniel A Spielman and Jaeoh Woo. A note on preconditioning by low-stretch spanning trees. In arXiv preprint arXiv:0903.2816, 2009

    2009 arXiv

  42. [50]

    Tight complexity bounds for optimizing composite objectives

    Blake E Woodworth and Nati Srebro. Tight complexity bounds for optimizing composite objectives. In Advances in Neural Information Processing Systems 29 (NeurIPS), 2016

    2016

  43. [51]

    Saddle points and accelerated perceptron algorithms

    Adams Wei Yu, Fatma Kilinc-Karzan, and Jaime Carbonell. Saddle points and accelerated perceptron algorithms. In Eric P. Xing and Tony Jebara, editors, Proceedings of the 31st International Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research, p...

    2014

  44. [52]

    On lower iteration complexity bounds for the convex concave saddle point problems

    Junyu Zhang, Mingyi Hong, and Shuzhong Zhang. On lower iteration complexity bounds for the convex concave saddle point problems. Mathematical Programming, 194(1):901–935, Jul 2022. 52 A Technical lemmas on regret In this section, we provide two technical lemmas regarding regre...

    2022

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.