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