arXiv:2609.38835
Average-and Last-Iterate Lower Bounds for Optimistic Matrix Mirror-Prox in Quantum Zero-Sum Games
Yiheng Su, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Pucheng Xiong
Abstract
Optimistic matrix mirror-prox (OMMP) computes $ε$-approximate Nash equilibria in quantum zero-sum games with an $O(1/\varepsilon)$ 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/\varepsilon)$ 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)$.
AI Summary
The paper asks whether the $O(1/\varepsilon)$ average-iterate guarantee for optimistic matrix mirror-prox (OMMP) in quantum zero-sum games is tight, and whether its Euclidean and entropy-based variants inherit geometric last-iterate convergence from classical matrix games. It studies explicit, fixed games with one qubit per player. For uniform averaging that includes the maximally mixed initial state, a diagonal game gives $G(\bar\Psi_T)\ge 1/T$ for every feasible sequence, independently of the update rule, regularizer, or step size. The proof makes the duality gap affine, so the initial error alone supplies the lower bound; this is an obstruction to the specified averaging rule, not an algorithm-independent complexity bound. For the two-projection optimistic gradient descent–ascent (OGDA) formulation, a game with a unique pure equilibrium yields distance $\sim4/(\eta t)$ and gap $\sim4/(\eta^3t^3)$ from maximally mixed initialization, for fixed $0<\eta\le1/8$. Bloch-ball projection reduces the boundary dynamics to a quadratic scalar recurrence, adapting a known curved-domain example. A separate game demonstrates initialization-dependent delays, despite geometric bounds for each fixed trajectory. For optimistic matrix multiplicative weights, a unique, strictly complementary equilibrium still permits distance and equilibrium-to-iterate relative entropy $\Theta(1/t)$, and gap $\Theta(1/t^2)$, for every fixed positive step size. Exact score-matrix formulas show exponential eigenvalue concentration but only $1/t$ eigenvector alignment. Numerical experiments check the rates and constants. All constructions have singular equilibrium strategies. The results leave open faster convergence under full-rank equilibrium assumptions and do not exclude improvements through alternative algorithms or averaging rules.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 38 pages, 6 figures