PaperlayerView exact revision on arXiv

Source-linked AI summary

Average-and Last-Iterate Lower Bounds for Optimistic Matrix Mirror-Prox in Quantum Zero-Sum Games

Yiheng Su, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Pucheng Xiong

arXiv:2609.38835v1quant-phcs.GTcs.LGmath.OC

TL;DR

It remains unclear whether uniform averaging retains an accuracy barrier despite rapidly converging individual iterates, or whether boundary curvature and eigenvector motion obstruct classical last-iterate guarantees for matrix strategies. The paper constructs explicit one-qubit games to analyze uniform averaging and the last-iterate behavior of OGDA and OMMWU. Uniform averaging needs Ω(1/ε) iterations; OGDA has distance Θ(1/t) and gap Θ(1/t^3), while OMMWU has distance and entropy Θ(1/t) and gap Θ(1/t^2).

  • Problem

    It remains unclear whether uniform averaging retains an accuracy barrier despite rapidly converging individual iterates, or whether boundary curvature and eigenvector motion obstruct classical last-iterate guarantees for matrix strategies.

    Source: §1.1 · p. 3

  • Method

    The paper constructs explicit one-qubit games to analyze uniform averaging and the last-iterate behavior of OGDA and OMMWU.

    Source: §2 · p. 6, §7 · p. 36

  • Results

    Uniform averaging needs Ω(1/ε) iterations; OGDA has distance Θ(1/t) and gap Θ(1/t^3), while OMMWU has distance and entropy Θ(1/t) and gap Θ(1/t^2).

    Source: §7 · p. 36

  • Takeaways & Limitations

    Uniqueness and strict complementarity do not ensure geometric convergence of unregularized OMMWU, and error rates depend on the measure and output rule.

    Source: §7 · pp. 36–37

    The lower-bound games do not admit full-rank Nash equilibria, so they do not rule out faster last-iterate convergence in games with such equilibria.

    Source: §7 · p. 37

Abstract

from arXiv · show

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

1 Introduction

The paper asks whether OMMP’s uniform-average accuracy dependence is tight and whether optimistic dynamics guarantee geometric last-iterate convergence in quantum games. Explicit one-qubit games show an averaging lower bound and polynomial last-iterate behavior, with distinct mechanisms for OGDA and OMMWU.

1 Introduction

  • The paper studies quantum zero-sum games whose strategies are density matrices in spectraplexes, where learning must track both eigenvalues and eigenspaces.The boundary includes a continuum of pure states, adding geometric features absent from classical matrix games.Source: §1 · p. 2

1.1 Prior works and a motivating question

  • Prior OMMP work gives an O(d/ε) averaged-equilibrium guarantee with negative von Neumann entropy and conjectures that its 1/ε dependence is tight.This builds on mirror-prox’s O(1/T) averaged gap guarantee for Lipschitz monotone problems.Source: §1.1 · p. 2
  • Classical geometric last-iterate results for optimistic methods do not settle quantum matrix strategies, where curved domains, boundary geometry, and eigenvector motion remain relevant.Prior diagonal quantum lower bounds do not settle the geometric-convergence conjecture for unregularized OMMWU.Source: §1.1 · pp. 3–4

1.2 Our contributions

  • The uniform-average output has an Ω(1/ε) iteration lower bound, independent of the update rule, regularizer, or step size.The construction uses a diagonal game with a unique pure equilibrium and retains the maximally mixed initial state in the average.Source: §1.2 · p. 4
  • OGDA from the maximally mixed state has distance Θ(1/t) and duality gap Θ(1/t^3) on a fixed game for each fixed step size 0 < η ≤ 1/8.A separate fixed game has arbitrarily long delays across initial states, although each fixed trajectory in that family admits a geometric bound.Source: §1.2 · p. 4
  • OMMWU has distance and equilibrium-to-iterate quantum relative entropy Θ(1/t), while its duality gap is Θ(1/t^2), despite a unique strictly complementary equilibrium.The same game works for every fixed positive step size.Source: §1.2 · pp. 4–5

1.3 Our techniques

  • OGDA’s polynomial rate arises from boundary curvature: after reaching the boundary, the update tangent to it is quadratic in the current error.Tracking both projections gives a scalar recurrence whose reciprocal grows linearly, while the duality gap is cubic in distance along the trajectory.Source: §1.3 · p. 5
  • For initialization-dependent delays, an off-support population r creates an off-diagonal entry of order √r, whose slow contraction delays error reduction by at least order 1/(η√r).For OMMWU, accumulated off-diagonal score terms keep Alice’s leading eigenspace tilted, so eigenvalue concentration alone does not ensure alignment.Source: §1.3 · pp. 5–6

2 Preliminaries and Notations

The section sets notation for one-qubit density-matrix games and specifies the equilibrium and error measures and optimistic updates used in the analysis.

2 Preliminaries and Notations

  • OGDA and OMMWU are studied as OMMP methods on one-qubit games, using squared Frobenius norm and negative von Neumann entropy regularizers, respectively.“Last iterate” means the played strategy pair Ψt.Source: §2 · p. 6

2.1 Density matrices and Bloch vectors

  • Qubit states are represented as Bloch vectors; pure states have unit-length vectors, and nonzero off-diagonal entries are called coherence in the fixed basis.D2 is the set of 2×2 Hermitian positive semidefinite matrices with unit trace.Source: §2.1 · p. 6

2.2 Games, equilibria, and error measures

  • Equilibria satisfy saddle inequalities; strict complementarity is defined by ranks of equilibrium strategies and slacks, while the section defines error measures including gap, distance, and relative entropy.An ε-Nash equilibrium uses the convention G(Ψ) ≤ ε.Source: §2.2 · p. 7

2.3 Optimistic updates

  • OMMP uses a strongly convex regularizer and updates played and auxiliary pairs; Frobenius projection gives OGDA, while negative von Neumann entropy gives OMMWU.For OMMWU, the updates use the normalized matrix exponential Λ.Source: §2.3 · pp. 7–8

3 An Average-Iterate Lower Bound for OMMP

A fixed one-qubit game yields an inverse-accuracy lower bound for OMMP’s uniform-average output. The bound follows from retaining the maximally mixed initial iterate, regardless of regularizer or step size.

3.1 Game construction

  • The constructed one-qubit game has a unique Nash equilibrium (P, P), value −1/2, and a duality gap affine in the strategy pair.Its game, dimension, and initialization are fixed independently of T and ε.Source: §3 · p. 8, §3.1 · p. 9, §3.2 · p. 10

3.2 Lower bound for the uniform average

  • T ≥ 1/ε averaged iterates are necessary for an ε-Nash equilibrium, giving an Ω(1/ε) update lower bound independently of OMMP’s regularizer and step size.The average includes the maximally mixed initial iterate, whose weight leaves gap 1/T even if every later iterate is exactly the equilibrium; the bound concerns uniform averaging, not last iterates or modified rules.Source: §3 · p. 8, §3.2 · p. 10
  • The lower-bound game uses a diagonal observable that embeds a classical two-action zero-sum game, so its obstruction does not rely on noncommutativity.Source: §3.2 · p. 10

4 Last-Iterate Lower Bounds for OGDA

This section establishes OGDA last-iterate lower bounds through fixed games: one exhibits arbitrarily long convergence delays across initial states, while another converges polynomially from the maximally mixed state. The results distinguish these trajectory-specific behaviors from finite-time convergence under the same initialization in the preceding game, without extending the claims to other initial states or state-dependent rate constants.

4 Last-Iterate Lower Bounds for OGDA

  • OGDA has last-iterate equilibrium distance Θ(1/t) and duality gap Θ(1/t^3) on a separate game from the maximally mixed state.The section introduction identifies this as a second fixed game.Source: §4 · p. 10
  • The delay game has value zero and equilibrium set {P} × D2; its duality gap is Tr[Qα], and its Frobenius distance to equilibrium is determined by α.Its observable is normalized and its saddle-point operator is 1-Lipschitz.Source: §4 · p. 11

4.2 Why the construction delays convergence

  • Alice’s initially zero gradient and weak coherence contraction combine with Bob’s slow motion to create the delay across initial states.Population and squared coherence are comparable, while Bob’s population is bounded by ηrt/2; a fixed coherence reduction requires Ω(1/(η√r)) iterations.Source: §4.2 · pp. 12–13

4.2.1 Projection on D2

  • For a real pure qubit input under a nonnegative shift, Frobenius projection preserves purity and bounds the output coherence by c/(1+h) ≤ c′ ≤ c.This projection bound explains why small shifts only weakly reduce coherence.Source: §4.2.1 · p. 14

4.3.2 Iteration complexity and dependence on initialization

  • For 0 < ε ≤ 1/16 the initial state is Ψ0 = (ρ4ε, P), while for 0 < ε ≤ 1/4 it is Ψ0 = (ρ4ε2, P); the game, dimension, payoff normalization, and step size are fixed.Source: §4.3.2 · p. 17
  • No initialization-independent geometric distance estimate holds for the fixed delay game, although each fixed trajectory in the family admits a geometric convergence bound.As the initialization approaches equilibrium, the time to halve the initial error becomes arbitrarily large.Source: §4 · p. 10, §4.3.2 · p. 17
  • In game (4.1), OGDA reaches an exact equilibrium by iteration ⌈2/η⌉ from the maximally mixed state.This does not rule out a logarithmic bound restricted to that initialization or a geometric rate whose constants depend on the starting state.Source: §4.3.2 · p. 18

4.4 A lower bound from maximally mixed initialization

  • For every fixed 0 < η ≤ 1/8, OGDA from (I/2, I/2) has distance Θ(1/t) and duality gap Θ(1/t^3), ruling out geometric distance convergence on this trajectory.The game and initialization are fixed independently of target accuracy; the corresponding hitting-time complexities are Θ(ε^-1) for distance and Θ(ε^-1/3) for gap.Source: §4.4 · pp. 20, 23, 24
  • The polynomial-rate game has the unique equilibrium (P, P), and strict complementarity fails because both slack matrices vanish there.Every finite played iterate has positive distance and positive gap; the distance lower-bound constant is independent of iteration and target accuracy.Source: §4.4 · pp. 20, 24

5 Last-Iterate Lower Bounds for OMMWU

A fixed qubit game makes unregularized OMMWU converge only polynomially from the maximally mixed state, despite a unique, strictly complementary equilibrium. The construction traces this slowdown to accumulated off-diagonal updates, and establishes polynomial rates and iteration lower bounds for every fixed positive step size.

5.1.1 Why the construction delays convergence

  • The construction combines a diagonal payoff favoring P for both players with a coupling term that adds a positive X component to Alice’s gradient while Bob deviates.That coupling contribution vanishes when Bob plays P.Source: §5.1.1 · p. 26
  • Bob’s deviations from equilibrium are positive and summable, while Alice’s accumulated off-diagonal score retains a nonzero limit and makes her state’s direction approach equilibrium only as 1/t.Alice’s radial concentration toward a pure state is exponential, but the direction of that state changes at rate 1/t.Source: §5.1.1 · pp. 26–28

5 Last-Iterate Lower Bounds for OMMWU

  • From the maximally mixed state, OMMWU on the fixed game has Frobenius distance and relative entropy Θ(1/t), and duality gap Θ(1/t^2), despite a unique, strictly complementary equilibrium.These rates hold with the game, step size, and initialization fixed.Source: §5 · p. 25, §5.2.1 · p. 28

5.2.1 Exact iterates and asymptotic rates

  • Unrolling the updates yields exact score-coordinate iterates, including the optimistic correction, without assuming commutativity or restricting the qubit states to real or diagonal matrices.The displayed forms follow from the updates themselves.Source: §5.2.1 · pp. 28–29
  • The exact-rate proof shows that a positive limiting off-diagonal coefficient drives the polynomial errors, while the optimistic correction tends to zero.The error rates follow from the exact iterates and their asymptotic expansions.Source: §5.2.1 · pp. 29–30

5.2.2 Explicit lower bounds and iteration complexity

  • The hitting times are Θ(ε^-1) for distance and relative entropy and Θ(ε^-1/2) for the gap; none of the three errors admits a geometric estimate.The result concerns unregularized dynamics with the Nash target, and does not establish an averaged-output lower bound.Source: §5.2.2 · pp. 31–32

6 Experiments

The experiments illustrate initialization-dependent delays for OGDA and polynomial last-iterate decay for both OGDA and OMMWU on fixed games. Across the plotted runs, the observed curves and fitted slopes agree with the predicted rates and asymptotes.

6.1 Numerical illustration of Theorem 4.3

  • For coherent OGDA starts, the four tested theorem horizons were 12, 40, 126, and 400 iterations, while the mixed start reached equilibrium at iteration 13 on the same game.Across the coherent runs, the gap stayed above half its initial value through the corresponding theorem horizon; the observed half-gap hitting times were 33, 100, 316, and 998.Source: §6.1 · pp. 33–34, Figure 3 · p. 33

6.2 Numerical illustration of Theorem 4.9

  • For OGDA on the fixed game from the maximally mixed state, fitted slopes of −0.9998 for distance and −2.9993 for gap agree with the predicted 1/t and 1/t^3 decay.The theorem’s dashed asymptotes use constants 32/t for distance and 2048/t^3 for gap.Source: §6.2 · pp. 34–35, Figure 5 · p. 35

6.3 Numerical illustration of Theorem 5.2

  • For OMMWU on the fixed game, fitted slopes of −1, −2, and −1 agree with the predicted decay of distance, gap, and relative entropy as 1/t, 1/t^2, and 1/t.At t = 10^5, the rescaled errors agree with the reference values to within 5 × 10^-9 relative error.Source: §6.3 · p. 36, Figure 6 · p. 36

7 Conclusion and Discussion

The paper establishes polynomial-convergence lower bounds for optimistic methods in one-qubit-per-player quantum games, including for uniform averaging and for last iterates. All constructions have singular equilibrium strategies, so the bounds do not rule out faster last-iterate convergence when a full-rank equilibrium exists.

7 Conclusion and Discussion

  • The uniform average including the maximally mixed initial iterate needs Ω(1/ε) iterations to attain gap at most ε, regardless of regularizer or step size.For OGDA, the paper also gives arbitrarily long delays across initializations and a fixed trajectory with distance Θ(1/t) and gap Θ(1/t^3); for OMMWU, distance and relative entropy decay as Θ(1/t) and the gap as Θ(1/t^2).Source: §7 · p. 36
  • None of the constructions has a full-rank Nash equilibrium, so the lower bounds do not exclude faster last-iterate convergence in games admitting one.The paper identifies equilibrium rank and the smallest positive eigenvalues as directions for further study.Source: §7 · pp. 36–37
  • Full-rank best responses at equilibrium do not remove the lower bound: Theorem 4.9 has full-rank best-response sets at its singular equilibrium, while the full-rank-equilibrium condition is stronger.At non-equilibrium profiles, at least one player's best-response set consists entirely of singular states; this fact alone does not characterize slow convergence.Source: §7 · p. 37
  • The average-iterate lower bound isolates the 1/T weight on the initial error, a distinct issue from last-iterate convergence.That contribution persists even if all subsequent iterates are already equilibria; alternative averaging rules and structural conditions for fast last-iterate convergence address different limitations.Source: §7 · p. 37
Loading 2609.38835v1…