Average-and Last-Iterate Lower Bounds for Optimistic Matrix Mirror-Prox in Quantum Zero-Sum Games
Abstract
Optimistic matrix mirror-prox (OMMP) computes ε-approximate Nash equilibria in quantum zero-sum games with an O(1/ε) average-iterate guarantee [arXiv:2311.10859]. We investigate whether this dependence on accuracy is tight and whether geometric last-iterate convergence can be guaranteed. We study these questions through explicit games with one qubit per player. First, we prove an Ω(1/ε) lower bound for the uniform-average output that includes the maximally mixed initial state, independently of the regularizer and step size. Second, we construct a fixed game on which optimistic gradient descent-ascent (OGDA), initialized at the maximally mixed state, has last-iterate Frobenius distance to equilibrium Θ(1/t) and duality gap Θ(1/t3) for every sufficiently small fixed step size. A separate fixed game exhibits arbitrarily long delays in reducing the initial error by a constant factor across a family of initial states. Finally, we give a fixed game with a unique, strictly complementary equilibrium on which optimistic matrix multiplicative weights updates (OMMWU) converge only polynomially from the maximally mixed state for every fixed positive step size. The last-iterate Frobenius distance and quantum relative entropy from the equilibrium to the iterates decay as Θ(1/t), while the duality gap decays as Θ(1/t2).
Related
- Non-asymptotic bounds for the average singular value of a complex Gaussian matrix
- Quantum lower bounds for convex optimization and real matrix-vector query problems
- Improved average and almost-all bounds for G(n)
- New upper bounds for average kissing numbers
- Uniform lower bounds for the average length of finite Pierce expansions
BibTeX
@misc{su2026averageand,
title = {{Average-and Last-Iterate Lower Bounds for Optimistic Matrix Mirror-Prox in Quantum Zero-Sum Games}},
author = {Yiheng Su and Emmanouil-Vasileios Vlatakis-Gkaragkounis and Pucheng Xiong},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.38835},
eprint = {2609.38835},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.38835},
}
RIS
TY - UNPB
TI - Average-and Last-Iterate Lower Bounds for Optimistic Matrix Mirror-Prox in Quantum Zero-Sum Games
AU - Yiheng Su
AU - Emmanouil-Vasileios Vlatakis-Gkaragkounis
AU - Pucheng Xiong
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2609.38835
UR - https://arxiv.org/abs/2609.38835
AB - Optimistic matrix mirror-prox (OMMP) computes ε-approximate Nash equilibria in quantum zero-sum games with an O(1/ε) average-iterate guarantee [arXiv:2311.10859]. We investigate whether this dependence on accuracy is tight and whether geometric last-iterate convergence can be guaranteed. We study these questions through explicit games with one qubit per player. First, we prove an Ω(1/ε) lower bound for the uniform-average output that includes the maximally mixed initial state, independently of the regularizer and step size. Second, we construct a fixed game on which optimistic gradient descent-ascent (OGDA), initialized at the maximally mixed state, has last-iterate Frobenius distance to equilibrium Θ(1/t) and duality gap Θ(1/t^3) for every sufficiently small fixed step size. A separate fixed game exhibits arbitrarily long delays in reducing the initial error by a constant factor across a family of initial states. Finally, we give a fixed game with a unique, strictly complementary equilibrium on which optimistic matrix multiplicative weights updates (OMMWU) converge only polynomially from the maximally mixed state for every fixed positive step size. The last-iterate Frobenius distance and quantum relative entropy from the equilibrium to the iterates decay as Θ(1/t), while the duality gap decays as Θ(1/t^2).
ER -