論文の概要: Average-and Last-Iterate Lower Bounds for Optimistic Matrix Mirror-Prox in Quantum Zero-Sum Games

• arxiv url: http://arxiv.org/abs/2609.38835v1
• Date: Wed, 30 Sep 2026 02:54:14 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-01 18:57:27.059818
• Title: Average-and Last-Iterate Lower Bounds for Optimistic Matrix Mirror-Prox in Quantum Zero-Sum Games
• Title（参考訳）: 量子ゼロサムゲームにおける最適行列ミラープロクスのための平均及び最終Iterate下界
• Abstract要約: 量子ゼロサムゲームにおける$$$-approximate Nashlibriaを$O(1/varepsilon)$ average-iterate guaranteeで調べる。 最大混合初期状態を含む一様平均出力に対して、$ (1/varepsilon)$低い境界を証明します。 分離された固定ゲームは、初期状態の族間での定数係数による初期誤差を減少させるのに、任意に長い遅延を示す。
• 参考スコア（独自算出の注目度）: 2.7340036787711646
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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)$.
• Abstract（参考訳）: Optimistic matrix mirror-prox (OMMP) は、量子ゼロサムゲームにおいて、$O(1/\varepsilon)$ average-iterate guarantee [arXiv:2311.10859] で$ε$-approximate Nash equilibriaを計算する。 我々は、この精度への依存がきついのか、幾何的最終点収束が保証できるのかを考察する。 プレイヤー1人当たり1キュービットの明示的なゲームを通してこれらの質問を学習する。 まず、正則化子とステップサイズとは独立に、最大混合初期状態を含む一様平均出力に対して$Ω(1/\varepsilon)$下界を証明する。 第二に、最大混合状態において初期化される楽観的勾配降下度(OGDA)が、平衡$ (1/t)$ と双対性ギャップ$ (1/t^3)$ であるような固定ゲームを構築する。 分離された固定ゲームは、初期状態の族間での定数係数による初期誤差を減少させるのに、任意に長い遅延を示す。 最後に、楽観行列乗法重み更新(OMMWU)が任意の正のステップサイズに対して最大混合状態から多項式的に収束する、一意で厳密な相補的な平衡を持つ固定ゲームを与える。 最後のイテレートのフロベニウス距離と、平衡からイテレートへの量子相対エントロピーは$1/t)$として崩壊し、双対性ギャップは$1/t^2)$として崩壊する。

関連論文リスト

• Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
  重み付き確率変数に対する新しい量子平均推定器を開発した。 尾指数>4/3$のより強い下界を導出し、次元への非自明な依存が避けられないことを示す。 凸目的関数に対して,量子射影勾配降下法を提案する。
  論文  参考訳（メタデータ） (2026-07-28T09:29:37Z)
• Convergence of Regret Matching in Potential Games and Constrained Optimization [85.55969013318627]
  RM$+$の交互収束は、$O_epsilon (1/epsilon4)$の後に$Epsilon$-KKT点に収束し、それが音で高速な一階数であることを示す。 我々の下界は、ポテンシャルゲームにおける粗相関平衡への収束が、ナッシュ平衡への収束よりも指数関数的に速いことを示している。
  論文  参考訳（メタデータ） (2025-10-20T00:45:47Z)
• Breaking $1/ε$ Barrier in Quantum Zero-Sum Games: Generalizing Metric Subregularity for Spectraplexes [2.7340036787711646]
  我々は、$textitNesterov の反復滑らか化の行列変種が、量子零サムゲームにおいて線形速度で終点収束を達成することを証明した。 副産物として、厳密な正の半定値プログラムの並列近似のための古典的ジャイナ・ワトラス [arXiv:0808.2775] 法を指数関数的に高速化する。
  論文  参考訳（メタデータ） (2025-09-25T20:51:13Z)
• A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games [95.50895904060309]
  最適行列乗算重み更新(OMMWU)アルゴリズムを導入し,平均収束複雑性を$mathcalO(d/epsilon)$ to $epsilon$-Nash equilibriaとする。 この二次的なスピードアップは、量子ゼロサムゲームにおける$epsilon$-Nash平衡の計算のための新しいベンチマークを定めている。
  論文  参考訳（メタデータ） (2023-11-17T20:38:38Z)
• Local Convergence of Gradient Methods for Min-Max Games: Partial Curvature Generically Suffices [0.5439020425819]
  2つのプレイヤーゼロサム微分可能なゲームに対する勾配法の局所的ナッシュ平衡の収束について検討する。 偏曲のおかげで、円錐粒子法 -- 重みを最適化し、混合戦略をサポートする -- は、固定支持法よりも一般的に収束する。
  論文  参考訳（メタデータ） (2023-05-26T21:43:56Z)
• Thinking Outside the Ball: Optimal Learning with Gradient Descent for Generalized Linear Stochastic Convex Optimization [37.177329562964765]
  我々は凸リプシッツ損失を伴う線形予測、あるいはより一般に一般化線型形式の凸最適化問題を考える。 この設定では、初期反復が明示的な正規化や投影を伴わずにグラディエント Descent (GD) を停止し、過大なエラーを最大$epsilon$で保証することを示した。 しかし、標準球における一様収束は、$Theta (1/epsilon4)$サンプルを用いた最適下界学習を保証できることを示しているが、分布依存球における一様収束に依存している。
  論文  参考訳（メタデータ） (2022-02-27T09:41:43Z)
• Quasi-polynomial time algorithms for free quantum games in bounded dimension [11.56707165033]
  2プレイヤフリーゲームの値に対する加法$epsilon$-approximationsを計算するために、$exp(mathcalObig(T12(log2(AT)+log(Q)log(AT))/epsilon2big))という半定値プログラムを与える。 量子分離性問題と接続し、線形制約を伴う改良された多部量子デ・フィネッティ定理を用いる。
  論文  参考訳（メタデータ） (2020-05-18T16:55:08Z)
• A Simple Convergence Proof of Adam and Adagrad [74.24716715922759]
  我々はAdam Adagradと$O(d(N)/st)$アルゴリズムの収束の証明を示す。 Adamはデフォルトパラメータで使用する場合と同じ収束$O(d(N)/st)$で収束する。
  論文  参考訳（メタデータ） (2020-03-05T01:56:17Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。