論文の概要: The Oracle Complexity of Simplex-based Matrix Games: Linear Separability and Nash Equilibria

• arxiv url: http://arxiv.org/abs/2412.06990v1
• Date: Mon, 09 Dec 2024 20:58:26 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-11 14:35:20.367692
• Title: The Oracle Complexity of Simplex-based Matrix Games: Linear Separability and Nash Equilibria
• Title（参考訳）: シンプルなxベースのマトリックスゲームにおけるOracleの複雑さ - 線形分離性とナッシュ平衡
• Authors: Guy Kornowski, Ohad Shamir,
• Abstract要約: 我々は、$max_mathbfwinmathcalWmin_mathbfpinDeltamathbfptopAmathbfw$という形式の行列ゲームを解く問題を研究する。 この問題は、線形セパレータの発見やゼロサムゲームにおけるナッシュ平衡の計算といった標準的なタスクをカプセル化する。
• 参考スコア（独自算出の注目度）: 37.300102993926046
• License:
• Abstract: We study the problem of solving matrix games of the form $\max_{\mathbf{w}\in\mathcal{W}}\min_{\mathbf{p}\in\Delta}\mathbf{p}^{\top}A\mathbf{w}$, where $A$ is some matrix and $\Delta$ is the probability simplex. This problem encapsulates canonical tasks such as finding a linear separator and computing Nash equilibria in zero-sum games. However, perhaps surprisingly, its inherent complexity (as formalized in the standard framework of oracle complexity [Nemirovski and Yudin, 1983]) is not well-understood. In this work, we first identify different oracle models which are implicitly used by prior algorithms, amounting to multiplying the matrix $A$ by a vector from either one or both sides. We then prove complexity lower bounds for algorithms under both access models, which in particular imply a separation between them. Specifically, we start by proving that algorithms for linear separability based on one-sided multiplications must require $\Omega(\gamma_A^{-2})$ iterations, where $\gamma_A$ is the margin, as matched by the Perceptron algorithm. We then prove that accelerated algorithms for this task, which utilize multiplications from both sides, must require $\tilde{\Omega}(\gamma_{A}^{-2/3})$ iterations, establishing the first oracle complexity barrier for such algorithms. Finally, by adapting our lower bound to $\ell_1$ geometry, we prove that computing an $\epsilon$-approximate Nash equilibrium requires $\tilde{\Omega}(\epsilon^{-2/5})$ iterations, which is an exponential improvement over the previously best-known lower bound due to Hadiji et al. [2024].
• Abstract（参考訳）: 我々は、$A$が行列であり$\Delta$が確率単純集合であるような、$\max_{\mathbf{w}\in\mathcal{W}}\min_{\mathbf{p}\in\Delta}\mathbf{p}^{\top}A\mathbf{w}$という形の行列ゲームを解決する問題を研究する。 この問題は、線形セパレータの発見やゼロサムゲームにおけるナッシュ平衡の計算といった標準的なタスクをカプセル化する。 しかし、おそらく意外なことに、その固有の複雑性 (Nemirovski と Yudin, 1983) はよく理解されていない。 本研究では,まず,前者のアルゴリズムが暗黙的に用いている異なるオラクルモデルを同定し,行列を一方または両側からベクトルで乗算する。 次に、両方のアクセスモデルの下でのアルゴリズムの複雑さの低いバウンダリを証明します。 具体的には、一方の乗法に基づく線形分離性のためのアルゴリズムは、パーセプトロンのアルゴリズムと一致するマージンとして$\Omega(\gamma_A^{-2})$の反復を必要とすることを証明することから始める。 そして、このタスクの高速化アルゴリズムは、双方の乗法を利用するため、$\tilde{\Omega}(\gamma_{A}^{-2/3})$の反復が必要であることを証明し、そのようなアルゴリズムの最初のオラクル複雑性障壁を確立する。 最後に、下界を$\ell_1$幾何に適応させることで、$\epsilon$-approximate Nash平衡の計算には$\tilde{\Omega}(\epsilon^{-2/5})$イテレーションが必要であることを証明します。

関連論文リスト

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan [49.1574468325115]
  ランク1テンソルを$otimes_i=1N mathbbRd$で完了する際のサンプルと計算複雑性を再考する。 本稿では,一対のランダム線形系上で,ガウス・ヨルダンに相当するアルゴリズムを許容する問題のキャラクタリゼーションを提案する。
  論文  参考訳（メタデータ） (2024-08-10T04:26:19Z)
• Structured Semidefinite Programming for Recovering Structured Preconditioners [41.28701750733703]
  正定値$mathbfK を mathbbRd times d$ と $mathrmnnz(mathbfK)$ の 0 でないエントリで与えられるアルゴリズムは、時間内に$epsilon$-optimal diagonal preconditioner を計算する。 我々は、行列辞書近似SDPと呼ばれる半定値プログラムのクラスに対して、新しいアルゴリズムを用いて結果を得る。
  論文  参考訳（メタデータ） (2023-10-27T16:54:29Z)
• Towards Characterizing the First-order Query Complexity of Learning (Approximate) Nash Equilibria in Zero-sum Matrix Games [0.0]
  正確な平衡は$O(fracln Kepsilon)$クエリの代わりに$O(fracln Kepsilon)$から効率的に計算できることを示す。 我々は下界に対する新しい手法を導入し、任意の$epsilon leq 1 / (cK4)$に対して$tildeOmega(frac1Kepsilon)$の下位境界を得ることができる。
  論文  参考訳（メタデータ） (2023-04-25T12:42:59Z)
• Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
  我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。 我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。 我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
  論文  参考訳（メタデータ） (2022-09-30T04:15:44Z)
• The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimization [88.91190483500932]
  本研究では,滑らかな凸最小化問題の解法として最適高次アルゴリズムを求めるための基本的オープンな問題について検討する。 この理由は、これらのアルゴリズムが複雑なバイナリプロシージャを実行する必要があるため、最適でも実用でもないからである。 我々は、最初のアルゴリズムに$mathcalOleft(epsilon-2/(p+1)right)$pthのオーダーオーラクル複雑性を与えることで、この根本的な問題を解決する。
  論文  参考訳（メタデータ） (2022-05-19T16:04:40Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。 また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
  論文  参考訳（メタデータ） (2022-04-13T22:18:47Z)
• The Fine-Grained Hardness of Sparse Linear Regression [12.83354999540079]
  この問題に対して、より優れたブルートフォースアルゴリズムは存在しないことを示す。 また,予測誤差が測定された場合,より優れたブラトフォースアルゴリズムが不可能であることを示す。
  論文  参考訳（メタデータ） (2021-06-06T14:19:43Z)
• Sublinear classical and quantum algorithms for general matrix games [11.339580074756189]
  行列ゲームに対する線形古典的および量子的アルゴリズムについて検討する。 任意の固定 $qin (1,2) に対して、$mathcalX$ が$ell_q$-norm 単位球である行列ゲームが加法誤差内で解決される。 同じタスクを時間内に解く、対応する部分線形量子アルゴリズムも提供する。
  論文  参考訳（メタデータ） (2020-12-11T17:36:33Z)

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

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