Metraipolis › archive › dc_ad82cfd9ca54
Average-and Last-Iterate Lower Bounds for Optimistic Matrix Mirror-Prox in Quantum Zero-Sum Games — arXiv:2609.38835
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.38835
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T13:16:35.830Z
- SHA-256 of the archived text
8472cbbc719d19f6b2049cad14662147a02d5c77a4590a4a92ed76be8edcf883- Stable URL of this page
https://metraipolis.com/documento/dc_ad82cfd9ca54
How to cite
Average-and Last-Iterate Lower Bounds for Optimistic Matrix Mirror-Prox in Quantum Zero-Sum Games — arXiv:2609.38835 — arXiv (en), https://arxiv.org/abs/2609.38835 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ad82cfd9ca54 (Metraipolis archive dc_ad82cfd9ca54, sha256 8472cbbc719d19f6b2049cad14662147a02d5c77a4590a4a92ed76be8edcf883)
BibTeX
@misc{dcad82cfd9ca54,
title = {Average-and Last-Iterate Lower Bounds for Optimistic Matrix Mirror-Prox in Quantum Zero-Sum Games — arXiv:2609.38835},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.38835},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ad82cfd9ca54; sha256 8472cbbc719d19f6b2049cad14662147a02d5c77a4590a4a92ed76be8edcf883},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.38835. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Optimistic matrix mirror-prox (OMMP) computes $\epsilon$-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 $\Omega(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 $\Theta(1/t)$ and duality gap $\Theta(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 $\Theta(1/t)$, while the duality gap decays as $\Theta(1/t^2)$. Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-10-01 in cs.GT). Categorie arXiv: Quantum Physics (quant-ph) ; Computer Science and Game Theory (cs.GT); Machine Learning (cs.LG); Optimization and Control (math.OC). Pagina del lavoro: https://arxiv.org/abs/2609.38835 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-07T12:48:01.893Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-10-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).